State-Action-Reward-State-Action

본 게시글은 인하대학교 유상조 교수님의 Reinforcement Learning Tutorial Seminar

수강 후 정리를 위한 포스팅입니다.

모든 포스팅의 저작관은 유상조 교수님에게 있음을 사전 공지합니다.

---

Before This Episode

https://jinwoo-jung.tistory.com/30

Temporal Difference Method

---

 

지난 시간까지 MC, TD에 대하여 살펴 보았다.

Optimal Policy를 얻기 위해 Policy Evaluation - Policy Improvement를 진행해야 하며, 이때, MDP 없이는 state-value가 아닌 action-value가 더 유용함을 알 수 있었다. 

 

이때, $\pi$에 근거하여 Evaluation을 통해 Q를 estimation하고 그에따라 Improvement를 하는데, Q가 가장 높은 action에 대하여 greedy action을 수행 함으로써 Policy를 Update 한다.

$$Q_{k+1}(s,a) \leftarrow Q_k(s,a) + \alpha [R_{t+1} + \gamma  \underset{a'}{max} Q(s',a') - Q_k(s,a)]$$

이때, target은 action-value가 가장 큰 action $a'$에 대하여 greedy하게 진행되고, current는 $Q_k(s,a)$이다. 

 

하지만 Expoloration을 위한 $ \varepsilon $-greedy의 경우 Target Policy를 따르지 않고 Behavior Policy를 따르게 된다. 결국, Target과 Behavior가 같지 않는 off-policy임을 알 수 있다.

 

만약 Target과 Behavior Policy를 같게 할 순 없을까?

 

이전에서 Update하는 과정과 달리 action $a$에 의해 state $S'$으로 이동했을 때,  $\varepsilon$-greedy로 선택되어 진 action $a'$을 이용하여 state-value를 update 하면 된다.

$$Q_{k+1}(s,a) \leftarrow Q_k(s,a) + \alpha [R_{t+1} + \gamma Q(s',a') - Q_k(s,a)]$$

따라서 실제 Behavior에 의한 $a'$로 target을 설정하고 update 하기 때문에 결국 target=behavior인 on-Policy가 된다. 이 method가 SARSA(State-Action-Reward-State-Action)이다.

 

SARSA

 

Target Policy를 다시 정의하면 optimal policy를 위해 Evaluation에 사용되는 Policy이고, Behavior Policy는 실제 action(Behavior)를 진행하기 위한 policy이다. 뒤에 예시들을 통해 두 차이를 더 잘 이해할 수 있을 것이다.

SARSA(State-Action-Reward-State-Action)

SARSA action-value estimation은 다음과 같이 진행된다.

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t, A_t)]$$

 

SARSA Sudo-Code

 

sudo-code와 함께 살펴보면, state $S$에서  $\varepsilon$-greedy에 의해 선택된 action $A$를 수행 후 reward $R$을 관측하고 변화된 state $S'$에서 역시 $\varepsilon$-greedy에 의해 $A'$을 선택한 후 해당 value를 가지고 $Q(S,A)$를 Update한다. 

 

SARSA는 $\varepsilon$-greedy에 의해 특정 action $a'$을 선택한다. 하지만 $\varepsilon$-greedy에 의해 선택한다는 것은 각 action의 확률을 알고 있기에 가능하다. 따라서 각 action에 대한 $Q(S',a')를 계산하고 평균을 낸 value로 Target을 정하는 것이 Expected SARSA이다.

 

Expected SARSA

Expected SARSA Example

 

각 action에 대한 action-value를 알기 때문에, 특정 action 하나만 계산하는 것이 아닌, 전체를 계산하여 평균을 내는 value를 이용한다. 위 예시는 $\varepsilon$이 0.3이라는 가정하에 계산된다.

Comparison

 

따라서 각각을 비교 해 보면, SARSA는 $S_{t+1}$에서 $\varepsilon$-greedy에 의한 특정 action만 고려하고, Expected SARSA는 각 action에 대하여 평균 값을 이용한다.

뒤에서 배울 Q-Learning의 경우 $Q(S',a')$에 대하여 max인 action을 선택하는 greedy 방식의 method 이다. 이는 max를 고려하기 때문에 실제 행동(behavior)과는 policy가 다르므로 Off-Policy 이다.

 

따라서 전체적인 Model을 비교 해 보면 아래와 같다.

Comparison Reinforcement Learning Models

 

Bias and Variance in RL

 

이전에 학습한 MC와 TD Methods의 경우 target value의 Bias와 Variance를 고려해야 한다.

 

추정치 $\hat{\theta}$의 Bias는 예측 평균($E[ \hat{\theta}]$)과 실제 true value($\theta$)의 차이로 정의된다. MC와 TD에서 추정한 $v_{\pi}(S_t)$에 적용하면, Bias는 다음과 같이 정의된다.

$$Bias = E[target] - v_{\pi}(S_t)$$

 

MC의 state-value function의 정의를 보면, $v_{\pi}(s) = E_{\pi}[G_t|S_t = s]$로, target value인 $G_t$의 평균이 결국 true value이기 때문에 unbiased라고 할 수 있다.

하지만, TD의 경우 $v_{\pi} = E_{\pi}[R_{t+1} + \gamma v_{\pi}(S_{t+1})|S_t = s]$로, target value에 Bootstrapping에 의한 추정치가 사용되기에 true value와 같아진다고 할 수 없어 biased라 할 수 있다.

 

state-value를 update하는 과정을 보면, MC의 경우 $v_{k+1} \leftarrow v_k(S_t) + \alpha[G_t - v_k(S_t)]$ Terminal state 까지 Episode를 모두 진행한 후 거꾸로 Return을 계산하기 때문에 variance가 크다고 할 수 있다.

하지만, TD의 경우 $v_{k+1} /leftarrow v_k(S) + \alpha [R_{t+1} + \gamma v_k(S') - v_k(S)]$로 이번 action에 의해 얻어진 return에 의존하기에 variance가 낮다고 할 수 있다.

Comparison MC and TD about Bias and Variance

 

그렇다면 어떤게 더 좋은 method라고 할 수 있을까?

 

state-value를 update하는 과정은 결국 optimal policy를 구하는 목적이 있다. 이 과정에서 value가 max인 action이 선택되기에 결국 Bias보단, Varience가 더 중요하다고 할 수 있다.

 

MC, TD 각 method가 수렴하는 그래프를 보면, TD는 Variance가 작지만, Bias가 존재하고, MC는 Variance가 크지만, Bias가 거의 없이 수렴함을 알 수 있다. Iteration이 증가할수록, MC가 더 좋아보이는 것은 맞지만, 실제 수행하는 과정에서 횟수의 Limitation이 존재하고, 그때 Variance가 크면 운이 좋지 않아 더 낮은 값을 취할 수 있기 때문에 TD가 더 좋다고 할 수 있다.