강화학습 sutton ch2 Multi-armed Bandit] #5

이번 챕터는 우왁...

이전에 봤을 때는 이런게 있었나 싶은데 엄청난 수학이 밀려온다. 그냥 그러려니하고 보고 빨리 다음 장으로 넘어가야지...

Gradient Bandits

지금까지는 행동 가치를 추측하고 이를 이용해서 행동을 선택하는 방법에 대해서 다루었다. 좋은 방법이긴 하지만 다른 방법들도 있다. 그 중 하나인 우선순위(preference) $H_t(a)$에 대해서 다룬다.

그래서 이 우선순위를 가지고 행동을 선택하는 데 그 중 하나는 softmax 분포로 결정하는 것이다.

여기서 새로운 표기 $\pi_t(a)$이 등장한다. t 시점에서 행동 a를 할 확률을 의미한다. softmax를 계산하게 되면 확률이 나오기 때문에 이를 이용한 것이다. 초기에 확률을 동일하게 주기 위해서 모든 우선순위는 동일하다(예를 들어 0이라던가)

이 우선순위를 업데이트 하는 방법은 다음과 같다.

• step-size $\alpha > 0$
• t시간 까지 받은 보상들의 평균 $\bar R_t \in \mathbb{R}$ (2.3, 2.4 참고)

여기서 $\bar R_t$는 보상과 비교하기 위한 baseline으로 사용된다. baseline보다 높다면 현재 행동의 우선순위가 높아지고 다른 행동의 우선순위가 낮아진다. 만약에 baseline보다 낮다면 반대로 적용된다.

baseline이 필요한 이유는 좀 더 안정적으로 학습하기 때문이다. 만약 이전 10-armed testbed에서 보상의 분포가 평균이 0이 아니라 +4로 했을 때(분산은 그대로 1), 성능을 비교한 것이다.

gradient ascent을 위해 확률적 근사(stochastic approximation)의 관점에서 보자면, $H_t(a)$는 성능($\mathbb{E}[R_t]$)을 증가시키는 것에 비례하여 증가한다.

여기서 성능 측정은 기대되는 보상(expected reward)으로 한다.

즉, performance = ((행동할 확률) x (행동의 가치)) 의 합으로 볼 수 있다. 위 미분 식을 좀 더 자세히 보자면, 어떤 항을 하나 추가할 수 있다.

여기서 $X_t$는 b에 의존하지않고 어떤 스칼라 값이든 될 수 있다. 모든 행동에 대한 gradient합이 0 (${{\sum_b \partial\pi_t(b)}\over\partial H_t(a)} = 0$)이기 때문에 가능한 일이다. (참고로 $\pi_t(b)$만 미분에 들어가는 이유는 $H_t(a)$에 대한 식으로 이루어져 있기 때문이다. $\pi$정의를 다시 보기)

$H_t(a)$에 따라 행동 확률은 변하겠지만 변화율의 합은 0일 것이다. 왜냐하면 확률의 합이 1이니 한쪽이 X만큼 변하면 다른 쪽에서 X만큼 변할 것이기 때문이다.

$\pi_t(b)$를 곱하고 나누어서(이러면 식에 변화는 없다) 기대값의 표현으로 나타낼 수 있다.

$\mathbb{E}[R_t]=q(A_t)$이고 다른 요소들은 랜덤이 아니기 때문에 $X_t=\bar R_t$로, $R_t$는 $q(A_t)$로 대체할 수 있다. ${\partial\pi_t(b)\over\partial H_t(a)}=\pi_t(b)(\mathbb{I}_{a=b}-\pi_t(a))$ 라 할 것이다.(밑에서 증명) 여기서 $\mathbb{I}_{a=b}$는 $a=b$일 때 1, 아니면 0이라 정의된 것이다. 지금까지의 가정으로 봤을 때, 다음과 같이 나온다.

지금까지 무엇을 하려 한거냐면 각 step마다 샘플링할 수 있는 기대값 형태로 sample에 비례하여 증가하는 성능(performance) gradient를 만드는 것이다.

기존에 맨 처음 식과 동일하다는 것을 알 수 있다.

이제 $\partial\pi_t(b)\over\partial H_t(a) = \pi_t(b)(\mathbb{I}_{a=b}-\pi_t(a))$를 증명하는 것만 남았다. 미분에서 표준 몫 법칙(quotient rule)은 생각해보자.

(고등학교 때 미분 법칙이 기억 난다.) 이를 사용하면 다음과 같이 쓸 수 있다.

여기서 $e^x$은 $x$에 대해 미분해도 그대로다. (고등학교 수학이 도움될 때가...) 근데 $\partial e^{H_t(b)}\over\partial H_t(a)$는 a와 b 다른 행동에 대한 식이다. 그러니 다른 행동이라면 상수 취급하여 미분했을 때 0이다. 하지마 만약 같은 행동이라면 위에처럼 $e^x$에 대한 미분처럼 하여 그대로 값이 나올 수 있다. 즉, $e^{H_t(a)}$이 나온다. 이를 정리하면 다음과 같이 나오고 조금 정리하면 다음과 같이 나온다.

잘 보면 softmax와 똑같다. 그래서 정리하면 결국 다음과 같이 된다.

지금까지 gradient-bandit 알고리즘 업데이트가 기대되는 보상의 gradient와 같아서 결국 stochastic gradient ascent의 일종임을 밝혔다. 그렇기에 강하게(robust) 수렴한다는 특징을 가지고 있다. 또 baseline에 어떤 것을 넣어도 식에 변화는 없지만 간단한 보상 평균을 넣어봄으로써 성능이 좋아지는 것을 보았다.

다음 시간에는

다음 챕터에서 Associative Search와 Summary를 끝으로 2장을 마무리할 예정이다. 사실 본격적인 것은 3장이기에 그냥 그러려니 넘기는 챕터였다..

p.s. 사실 쓰면서도 이게 맞는 말인가 싶다. 미래의 나여. 여긴 그냥 지나가게 언젠가 필요할 때 봐. 지금은 아니지만...