REINFORCE

Policy Gradient Algorithms (tistory.com)

Policy Gradient Algorithms

 

본문에 표기된 알고리즘은 다음과 같습니다.

 

1. Policy Parameter $\theta$를 랜덤으로 초기화합니다.
2. Policy $\pi_\theta$의 경로 하나를 생성합니다. : $S_1, A_1, R_2, S_2, A_2, \cdots, S_T$
3. For t=1, 2, $\cdots$, T:
   1. Return $G_t$를 측정합니다.
   2. Policy Paramters $\theta$를 갱신합니다. : $\theta \leftarrow \theta+\alpha\gamma^tG_t\nabla_\theta\ln\pi_\theta(A_t,S_t)$

이 알고리즘에서 $G_t$를 손보면 Advantage 함수를 구할 수 있습니다. 일반적으로 Advantage를 $A(s,a)=Q(s,a)-V(s)$ 수식을 통하여 구하라고 하는데 REINFORCE 알고리즘의 경우 Q-Value를 사용하지 않으므로 그냥 Baseline을 처리하면 되는데, 이는 얻게되는 값들의 평균값을 제거하면 됩니다.

 

rewards = rewards - rewards.mean()

 

위에서도 서술하였으나, 다시 언급하자면 평균값을 구하는 방식으로 할 경우 Parameter 업데이트가 비교적 적기 때문에 학습속도는 굉장히 늦습니다.

 

## REINFORCE 구현 코드 예정 ##

 

 

 

※ 참고 1

REINFORCE를 진행할 때 $\ln\pi_\theta(A_t,S_t)$ 처럼 log를 사용하는 이유를 정리하고자합니다. (log 씌우는 부분 전부 적용 가능합니다.) 알 수 없는 실제 분포와 우리가 학습하는 가상의 분포가 있습니다. 이 두 분포간의 차이를 두는데 KL-발산이라는 식을 사용합니다. 실제 분포 P를 가상의 분포 Q가 얼마나 비슷한지 계산하는 방식입니다.

$$
\begin{aligned}
D_{KL}(P||Q)
&=\sum_i P(i)\log\cfrac{P(i)}{Q(i)}\\
&=\sum_i P(i)\log P(i) - \sum_i P(i)\log Q(i)\\
&= \biggl(- \sum_i P(i)\log Q(i) \biggl) - \biggl( - \sum_i P(i)\log P(i) \biggl)\\
&=H(P,Q) - H(P)
\end{aligned}
$$

여기서 $H(P,Q)$는 Cross Entropy이며 $H(P)$는 Entropy 입니다. 그런데 Entropy의 $P(i)$ 식은 항상 참입니다. 왜냐하면 이 확률이 정답이라고 생각하고 학습하기 때문입니다. 그래서 $P(i)=1$이므로 $H(P)=0$이 됩니다. 그러면 결국 Cross Entropy인 $H(P,Q)$만 남는데 $P(i)=1$라고 하였으니, $H(P,Q)=-\sum_i \log Q(i)$가 됩니다. 우리가 알고리즘에 적용할 때 log를 씌우고 -를 넣어야 KL-발산을 정상적으로 적용하다는 것을 뜻하며, 이 값을 경사하강법(Gradient Descent)로 학습해야합니다.

 

※ 참고 2

기술적으로 $G_t$를 구할 때는 $\sum_{k=0}^\infty \gamma^k R_{t+k+1}$을 구해야하는데 이를 풀어쓰면 다음과 같습니다.

$$\begin{aligned}&G_1=R_2 +\gamma R_3 + \gamma R_4 +\cdots\\&G_2=R_3  \gamma R_4 + \cdots\\&G_3=R_4 + \cdots\\&\quad\vdots\end{aligned}$$

위 식을 역순으로 연산하면 재귀형태로 변경되기 때문에 간단하게 코드를 다음과 같이 작성할 수 있으므로 실제 코드에 아래와 같이 적용하였습니다.

$$\begin{aligned}&\quad\vdots\\&G_3=R_4 + \gamma G_4\\&G_2=R_3 + \gamma G_3\\&G_1=R_2 + \gamma G_2\end{aligned}$$

rewards = []
G = 0
for trajectory in reversed(trajectories):
	G = trajectory.reward + GAMMA * G
	rewards.insert(0, G)

다른 곳을 검색해보면 trajectories[::-1] 이런식으로 구현되어있는데, 같은 것이니 상관 없습니다.