[RL] Expected SARSA

(해당 포스트는 Coursera의 Sample-based Learning Methods의 강의 요약본입니다)

이전 포스트를 통해 배울 수 있었던 것은 크게 다음과 같다.

• Episode가 끝나야 Value function을 update할 수 있었던 Monte Carlo Method와 다르게 TD Learning은 BootStrapping 기법을 사용해서 Value function을 update할 수 있었다.
• TD Learning 중에서도 Target Policy와 Behavior Policy의 일치여부에 따라서 On-policy method인 SARSA와 Off-policy method인 Q-learning으로 나눠볼 수 있다.

 아무튼 두가지 방법 모두 state action value를 활용한 Bellman equation으로부터 시작된 알고리즘이다.

$$ q_{\pi}(s,a) = \sum_{\color{red}{s'}, r} p(s', r|s,a) \big( r + \gamma \sum_{\color{red}{a'}} \pi(a'|s') q_{\pi}(s', a') \big) $$

위의 bellman equation을 보면 알겠지만 현재의 \(q_{\pi}(s,a)\)를 update하기 위해서 next state \(s'\)과 next action \(a'\)에 대한 \(q_{\pi}\)가 필요하다. 그리고 SARSA에서도 이런 관계는 그대로 적용된다.

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

이때 next state \(S_{t+1}\)는 environment로부터, next action \(A_{t+1}\)는 environment상에서 동작하는 agent의 policy로부터 sampling된다. 

$$ \begin{align} S_{t+1} &\sim p(s', r|s, a) \\ A_{t+1} &\sim \pi(a'|s')  \end{align} $$

그런데 사실 agent의 policy \(\pi\)가 중간에 변화하지 않는 이상, next action \(A_{t+1}\)은 \(\pi\)에 의해서 결정되어 있기 때문에 굳이 sampling할 필요가 없다. 다시 말해 굳이 \(A_{t+1}\)을 구하지 않고 \(a'\)이 나올 확률인 \(\pi(a'|s')\)를 그대로 활용해도 된다는 것이다. 대신 나올 수 있는 next action이 여러개이기 때문에 이에 대한 평균(expectation)을 취하게 된다.

$$ Q(S_{t+1}, A_{t+1}) \rightarrow \sum_{a'}\pi(a'|S_{t+1})Q(S_{t+1}, a') $$

이를 이용해서 기존의 SARSA에 사용됬던 Bellman equation을 변형해보면 아래와 같다.

$$ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \big(R_{t+1} + \gamma \color{red}{ \sum_{a'} \pi(a'|S_{t+1})Q(S_{t+1}, a')} - Q(S_t, A_t)\big) $$

 생긴 것은 SARSA의 Bellman equation과 비슷하게 생겼지만 TD Error를 구하는 부분이 \(Q(S_{t+1}, A_{t+1})\)이 아닌 전체 Q value의 expectation을 취하는 형태로 바뀐 것을 볼 수 있다. 이게 바로 Expected SARSA 이고, Expected라는 이름이 붙는 이유도 평균을 취하기 때문인 것이다. 그럼 이게 SARSA와 비교했을 때 어떤 부분이 바뀐 것이냐 궁금할 수 있는데, SARSA는 이전에 다뤘던대로 On-policy method이고, 다시 말해 Target Policy와 Behavior Policy가 동일한 케이스이다. 이 경우 Agent가 어떤 policy를 가지고 있어도 policy improvement를 하기 위해서는 무조건 해당 environment에서 돌려야한다. 그리고 이렇게 Improve가 된 policy를 가지고 evaluation을 하는 경우 value function 또한 update되기 때문에 이전에 사용했던 value function을 다시 사용할 수 없는 케이스가 발생한다. 당연히 Data Efficiency가 떨어진다. 반면 Off-policy는 Target Policy와 Behavior Policy가 다르기 때문에 on-policy에서 문제가 되는 Data Efficiency를 높일 수 있다. 궁극적으로는 Agent를 임의의 Simulator 상에서 학습시키고, 그걸 실제 환경에 적용해보는 일련의 과정이 Off-policy라서 가능한 것이다.

 결국 Expected SARSA는 On-policy인 SARSA를 Off-policy 형태로 변환한 형태이다. 그래서 SARSA의 action은 어느정도의 stochastic을 띄는데 비해, expected SARSA의 action은 Q-value의 expectation을 취함으로써 어느 정도의 deterministic을 띄는 점에서 Q-learning과 유사하다고 볼 수 있다.물론 Q-learning은 Q-value의 maximum을 취하는 action을 취하는 부분에서 deterministic을 띄기 때문에 이 부분에서 expected SARSA와 차이가 있다. 이렇게 SARSA와 Q-learning의 절충점을 가지면서 몇가지 특징을 가진다. 우선 action이 deterministic을 띄기 때문에 SARSA에 비해서 action에 대한 variance가 적고, 그만큼 update도 stable하게 이뤄진다. 대신 문제는 다음 state를 update할 때마다 모든 action에 대한 Q-value를 update하면서 연산량이 증가한다는 것이다. 상식적으로 생각해도 SARSA는 그냥 취한 action 그대로 따라가면 되지만, Expected SARSA는 모든 action에 대해서 Q-value를 구해야 expectation을 구해야하기 때문에 그만큼 연산량이 늘어나고, update도 늦게 될 것이다. 그리고 한가지가 더 있는데, expectation을 취할 때의 action이 현재의 policy \(\pi\) 로부터 나오는데, 이게 굳이 behavior policy를 따로 구할 필요가 없어지는 것이고, 이는 곧 두 개의 policy의 distribution 차이를 보정하기 위해 필요한 값인 Importance Sampling이 필요없다는 것을 의미한다. 참고로 sutton책에서는 이런 과정을 다음과 같이 설명하고 있다.

Expected SARSA was used on-policy, but in general it might use a policy different from the target policy \(\pi\) to generate behavior, in which case it becomes off-policy algorithm (p.134)