Q-Learning, SARSA

안녕하세요.
화공공대생입니다.
이전 포스팅에서 대략적인 Temporal Difference(TD) Method에 대한 내용을 다뤘습니다. 해당 글은 여기 참조해주세요.

Q-Learning 은 TD Method에서 off policy인 경우에 해당합니다. 먼저 On policy인 Sarsa에 대해서 소개드리고, Q-Learning에 대하여 소개 드리겠습니다.

SARSA

SARSA는 State Action Reward State Action의 약어 입니다. 이는 Q Value를 표현하는데로 부터 나오게 되었습니다. Q Value의 업데이트 순서를 보면 다음과 같습니다.
State Action(Qvalue(old)), reward, State and Action(Qvalue(New))
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 알고리즘

On policy라고 했으니, Policy는 \epsilon -greedy 같은 알고리즘을 써줘서 평가 해볼 수 있겠습니다.

알고리즘의 내용은 다음과 같습니다.

1. State에 대해서 정의
2. State s에서 Q policy에 따라 Action a 선택.
   2.1 loop (모든 에피소드에 대하여 다음과 같이 평가)
   2.1.1 모든 Action에 따라 변화되는 State 및 Reward를 확인
   2.1.2 s’에 따라 action a’ 선택 (Q-policy)
   2.1.3 Q-Value Update (SARSA)
   2.1.4 State , Action set update.

Action value를 평가하는 알고리즘의 핵심은 2.1.1 라고 볼 수 있습니다. 또한, 방식은 2.1.3을 따라 Q-value 들을 평가 해줄 수 있게 됩니다. 여기서 조금 헷갈리 실 수 있는데, Q-policy는 Q-Value에 따라서 Action의 Probability가 달라지게 됩니다.

즉, On policy로 Policy와 Action value는 동시에 이뤄지게 된다는 장점이 있습니다. 또한, On policy와 off policy의 장단점은 MC와 유사합니다. 해당 내용은 여기에서 확인할 수 있습니다.

Q-Learning

Q-Learning 은 TD의 off policy 과정입니다. off policy는 Episode를 얻는 Behavior policy와 평가하는 Optimal policy가 다르다는 특징이 있습니다. 이에 SARSA와 Q value update하는 방식이 조금 상이 합니다.
\begin{aligned}& Q-Learning &&Q(s_t,a_t) \leftarrow Q(s_t,a_t)+\alpha[r_{t+1} +\gamma max_{a} Q(s_{t+1},a)-Q(s_t,a_t)] \\& SARSA && 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)]\end{aligned}

Q-value를 업데이트 하는 방식을 보면, max가 되는 Q를 선택하는 것이 Optimal policy를 평가하는 가정이 됩니다. 또한, 이러한 데이터는 e-greedy와 같은 Behavior policy로 얻어 지게됩니다.

Q-Learning 알고리즘

다음 Q_leraning 알고리즘을 보게되면 SARSA와 조금의 차이가 있는 것을 확인할 수 있습니다.

여기서 차이점은 Q value에 대한 Data는 e-greedy로 부터 얻게 되고, Q value의 Update에서 e-greedy와 상관 없이 Maxmize하는 action을 선택해서 Q value function을 update 하는 것을 알 수 있습니다.

Cliff Example

절벽 예제는 최종 골로가는 Optimal path가 있지만, Optimal path에서 우측으로가면 절벽으로 떨어지게 되어 Reward를 왕창 잃는 예제 입니다. 조금.. 잔인하죠 ㅠㅠ?

이 결과를 보면 조금 흥미롭습니다.

Q-Learning의 경우 SARSA보다 Total Reward 값이 낮은데, 이는 바로바로 Policy를 평가를 하기 때문이라고 볼 수 있습니다. Q value를 Update하는 과정에서 Maximize하는 Action만 선택하다 보니, Optimal path로 가는 경향이 있어서 절벽으로 떨어질 확률이 높아지게 됩니다. 반면, SARSA는 여러가지 경우의 수가 생겨서 조금 더 safe한 Path로 갈 수 있게 됩니다.

Dobule QLearning

마지막으로 Double Q Learning 입니다. A의 Action 오른쪽으로 가면 바로 Goal이 되고, 왼쪽으로 가는 여러가지 Path의 Reward는 기대치는 -0.1 이고 분산이 1인 경우를 거쳐 최종 Goal도 도착 합니다.

Maxmize하는 좋은 경우는 바로 우측으로 이동하는 경우가 됩니다. 하지만, Reinforcement Learning은 하는 경우 왼쪽이 최선의 선택이다라는 경우가 많이 나올 수 있습니다.

만약, 왼쪽으로 갔는데 -0.1 + 1 = 0.9인 Reward로 받고, 다음엔 우측을 선택하면 Reward가 0이 되서, Optimal path로 자꾸 왼쪽을 선택하게 될 것입니다.

이러한 선택을 조금 더 도와주기 위해서 우리는 Double Q Learning을 사용하게 됩니다.

결과를 보자면, Double Q Learning이 빠르게 Optimal에 다가가는 것을 확인해 줄 수 있습니다. 이에 대한 기본 아이디어는 두 사람이서 케잌을 먹는상황을 생각해보겠습니다. 먼저 자르고 먼저 먹는 경우가 Q-learning이 되겠습니다. 반면, 먼저 자르는 사람이 나중에 먹게 되는 상황이 Double Q Learning의 기본 아이디어입니다.

뭔가,Balance가 있게 Learning을 할 수 있을 것 같습니다. 그럴 듯 한거 같죠?? 수식으로 보자면 다음과 같습니다.

Q_1(s_t,a_t) \leftarrow Q_2(s_t,a_t)+\alpha(r_{t+1}+\gamma Q_2(s_{t+1},argmax_a Q_1 (s_{t+1},a))-Q_1(s_t,a_t))

여기서 Q_2 가 케잌을 자르는 사람입니다.
여기까지, Q-learning에 대하여 알아보았습니다.
감사합니다.

참고문헌

1. Sutton, R. S., Bach, F., & Barto, A. G. (2018). Reinforcement learning: An introduction. MIT Press Ltd.