SARSA, Q-Learning, REINFORCE, AC

SARSA

On-policy TD 기법으로 행동 가치(Action Value) $Q(S,A)$를 갱신하기 위한 방법은 다음과 같다.

현재 상태 $S_t$에서 행동 $A_t$을 취했을 때 받는 보상 $R_t$과 새로운 상태 $S_{t+1}$로부터 $\epsilon$ -greedy policy를 통해 다음 행동 $A_{t+1}$을 구하여 행동 가치를 갱신한다.

$$Q(S,A) = Q(S,A) + \alpha \left( R + \gamma Q(S', A') - Q(S,A)\right)$$

 

Q-Learning

Off-policy TD 기법으로, 다음 행동을 선택할 때 Action policy $\mu$을 이용해서 고르며 ($A_{t+1} \sim \mu (\cdot | S_t) $)

Action value $Q(S_t ,A_t )$는 대안 행동의 가치를 통해 갱신한다.

$$Q(S_t ,A_t) \leftarrow Q(S_t ,A_t ) +\alpha \left( R_{t+1} + \gamma Q(S_{t+1} , A' ) -Q(S_t, A_t) \right) $$

behavier policy $\mu$와 target policy $\pi$을 모두 향상시키고자

target policy $\pi$이 Action value $Q(s,a)$를 최대화 한다면

$$\pi(S_{t+1}) = \text{argmax}_{a'} Q(S_{t+1} ,a')$$

behavier policy $\mu$도 action value $Q(s,a)$를 최대화 한다면 Q-learning의 target은 다음과 같다.

$$Q^T =R_{t+1} + \gamma Q \left(S_{t+1} + A'\right)$$

$$=R_{t+1} +\gamma Q\left(S_{t+1} , \text{argmax}_{a'} Q(S_{t+1} ,a') \right)$$

$$=R_{t+1}+ \gamma \text{max}_{a'} \gamma Q\left(S_{t+1} ,a'\right)$$

SARSA의 구조 넣으면 

$$Q(S_t ,A_t) \leftarrow Q(S_t ,A_t ) +\alpha \left( {Q^T} -Q(S_t, A_t) \right) $$

$$Q(S_t ,A_t) \leftarrow Q(S_t ,A_t ) +\alpha \left( R_{t+1}+ \gamma \text{max}_{a'} \gamma Q\left(S_{t+1} ,a'\right) -Q(S_t, A_t) \right) $$

 

REINFORCE (Monte-Carlo Policy Gradient)

매개변수로 $\theta$를 가지는 policy $\pi_\theta$를 따라 행동을 선택할 때 return $r$의 기댓값은 수식으로 다음과 같이 쓸 수 있다.

$$J(\theta) = \mathbb{E}_{\pi_\theta} [r]$$

return의 기댓값을 최대화 하는게 학습의 목적이 되는데 이를 Policy objective function $J(\theta)$라고 한다. 그렇다면 objective function을 최대화하는 방향으로 매개변수 $\theta$를 움직이면 결국에 objective function $J(\theta)$가 최댓값이 될 것이다.

$$J(\theta) = \mathbb{E}_{\pi_\theta} [r] =\sum_{s\in \mathcal{S}} d(s) \sum_{a\in\mathcal{A}} \pi_\theta (s,a) \mathcal{R}_{s,a}$$

$$\nabla_\theta J(\theta) =\nabla_\theta \left[ \sum_{s\in \mathcal{S}} d(s) \sum_{a\in\mathcal{A}} \pi_\theta (s,a) \mathcal{R}_{s,a}\right]$$

매개변수 $\theta$에 종속된 부분만으로 정리하면

$$\nabla_\theta J(\theta) =\sum_{s\in \mathcal{S}} d(s) \sum_{a\in\mathcal{A}} \nabla_\theta \left[\pi_\theta (s,a)\right] \mathcal{R}_{s,a}$$

다시 기댓값 형태로 식을 변환하기 위해 다음과 같이 식을 변형한다.

$$\nabla_\theta \left[\pi_\theta (s,a)\right]=\pi_\theta (s,a) \frac{\nabla_\theta \pi_\theta(s,a)}{\pi_\theta (s,a)}$$

$$\nabla_\theta \left[\pi_\theta (s,a)\right]=\pi_\theta (s,a) \nabla_\theta \text{log} \pi_\theta (s,a)$$

그렇다면 다시 objective function을 다음으로 정리할 수 있다.

$$\nabla_\theta J(\theta) =\sum_{s\in \mathcal{S}} d(s) \sum_{a\in\mathcal{A}} \pi_\theta (s,a) \left[ \nabla_\theta \text{log} \pi_\theta(s,a) \right] \mathcal{R}_{s,a}$$

$$\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta} [\nabla_\theta \text{log} \pi_\theta(s,a)r]$$

policy gradient $\nabla_\theta \pi_\theta$를 해석적으로 계산할 수 있고, policy $\pi_\theta$가 미분가능하고 0이 아니라면 Stochastic gradient ascent를 이용해서 target policy $\pi_\theta$의 매개변수 $\theta$를 갱신 할 수 있다. policy gradient theorem으로부터,

$$\Delta \theta_t = \alpha \nabla _\theta \text{log}\pi_\theta (s_t ,a_t) v_t $$

$$\theta \leftarrow \theta + \alpha \nabla_\theta \text{log} \pi_\theta (s_t, a_t ) v_t $$

 

Actor-Critic Algorithm

Monte-Carlo policy gradient는 여전히 큰 분산을 가진다. 그래서 action-value function을 추정하는 critic을 사용한다.

$$Q_w (s,a) \approx Q^{\pi_\theta} (s,a)$$

그래서 Actor-Critic algorithm은 두 개의 매개변수 집합을 사용하며

• Critic은 action-value function의 매개변수 $w$을 갱신한다. Stata-Action value estimator 이다.
• Actor는 critic이 제안하는 방향으로 policy parameter $\theta$를 갱신한다. State value estimator 이다.

근사적 policy gradient를 따른다.

$$\nabla_\theta J(\theta) \approx \mathbb{E}_{\pi_\theta} [\nabla_\theta \text{log} \pi_\theta(s,a) Q_w (s,a)]$$

$$\Delta \theta_t = \alpha \nabla _\theta \text{log}\pi_\theta (s_t ,a_t) Q_w (s,a)$$