[Remark] Sarsa와 Q-learning 비교하기

---

---

[Remark] Sarsa와 Q-learning 비교하기

 

강화학습의 목적은 Reward 혹은 Return을 최대화하는 Policy를 학습하는 것이다. 마리오 게임에서 내 손으로 게임을 하면 버섯을 밟기도 하고, 장애물에 빠지기도 하면서 게임 플레이 시간이 오래걸리거나 혹은 도착지에 도달하지 못할 수도 있다.

 

그러나 충분히 학습된 인공신경망 policy를 이용하면, 게임을 쉽게 깰 수 있다. 물론 초기상태에서는 내 손보다 게임을 못하겠지만, 지속적으로 플레이하면서 점점 policy가 발전할 것이다. 물론 내 손으로 플레이 하는 것도 점차적으로 실력이 향상될 것이다. 내 손과 인공신경망 policy를 비교하기 위해서는 policy를 평가해야 한다. 강화학습에서는 이를 policy evaluation 라고 한다. Policy로 게임을 하면서 받게 되는 보상으로 Return 이라는 값, 혹은 Q-value라는 값을 생각할 수 있다.

• Return : 주어진 상태에 도달했을 때, 앞으로 받을 보상까지 몽땅 고려한 값
• Q-value : 주어진 상태에서 특정 행동을 했을 떄, 앞으로 받을 보상까지 몽땅 고려한 값

 

두 가지의 차이는 행동이 고려되는지의 여부이다. policy evaluation은 주어진 policy $\pi$로 환경에서 Reward를 얻으면서, 해당 값을 계산하는 방식으로 이루어진다. 만일 두 개의 policies $\pi_1$과 $\pi_2$가 있다면, 더 높은 값을 가지는 policy가 더 좋은 policy이다. Return 값의 평균은 state-value function $V(s)$ 그리고 Q-value 값은 state-action value function $Q(s,a)$이라고 불린다.

• $V^{\pi_1}(s) > V^{\pi_2}(s)$ : $\pi_1$ 이 더 좋은 policy
• $Q^{\pi_1}(s,a) > Q^{\pi_2}(s,a)$ : $\pi_1$ 이 더 좋은 policy

---

Policy Evaluation

주어진 policy $\pi$에 대해서 $V^\pi (S)$과 $Q^{\pi}(s,a)$ 값을 정확하게 찾는 방법은 무엇일까? 또한 해당 값은 딱 하나 있을까? 이에 대해서 Bellman은 Bellman Oprerator라는 연산자로 두 가지에 대해서 답한다.

 

$$T^\pi V(s) = \mathbb{E}[R] + \gamma \mathbb{E}_{P} V(s’) $$

$$T^\pi Q(s,a) = \mathbb{E}[R(s,a)] + \gamma \mathbb{E}_{P, \pi} Q(s’, a’)$$

 

Bellman operator $T$ 는 $V$ 와 $Q$의 값을 업데이트 하는 연산자로 생각할 수 있다. 위의 예제에서 게임에 대한 주어진 policy $\pi$ 를 평가할 때, $V=V_0$ 와 $Q=Q_0$를 초기화하고, $T$로 업데이트 하는 것이다. 만일 업데이트를 4번 한다면, $Q_0$값은 $Q_4(s,a) = T^4 Q_0 (s,a) $ 로 업데이트 되는 것이다. 이 과정에서 Q-value값은 policy에 적당한 값으로 수렴해 나간다. 그림으로 표현하면 다음과 같다.

 

 

한 가지 의문점은 반복적으로 값을 업데이트하면 어떤 값으로 수렴하는가이다. 놀랍게도 contraction property에 의해서 해당 알고리즘은 초기값에 상관없이 특정한 값으로 수렴한다. 이렇게 Q-value를 업데이트 하는 과정에서 만일, $\gamma \mathbb{E}{P, \pi} Q(s’, a’)$ 부분 대신에 $a’ = \arg\max{a} Q(s,a)$로 선택하게 된다면, Q-value값은 점진적으로 커지게 된다. 이로부터 우리는 두 가지 컨트롤 기법을 생각할 수 있다.

---

Control

Sarsa (state-action-reward-state-action) 방식은 주어진 $Q-value$에서 $\epsilon-\text{greedy}$ 와 같은 방식으로 action $a’$을 샘플링하여, Q-value 값을 업데이트 한다. 이 때, 단순히 다음 state에 대해서만 추정한 $R+\gamma Q(s’,a’)$ 값과 현재 action $a$에 Q-value $Q(s,a)$의 차이 $R + \gamma Q(s’, a’) - Q(s,a)$ 값을 더해서 업데이트 한다.

 

Q-learning은 Q-value값을 가장 크게 업데이트하고, 이로부터 다음 action을 샘플링 하는 방식이다. 여기서 가장 크게 업데이트 한다는 표현은 Bellman optimal equation 으로부터 유도된 것으로, Q-value를 가장 크게 키우는 행동을 선택하는 것이다.

 

두 가지 알고리즘은 Sutton 책에 실려있는 것을 가져왔다. 두 개의 알고리즘은 눈을 씻고 찾아봐도 다른 점이 거의 없어 보이며, 많은 사람들을 헷갈리게 한다.

 Sarsa 

 Q-learning 

두 알고리즘은 굉장히 유사하다. 차이점은, Q-value값을 업데이트 하는 부분과 action을 샘플링 하는 부분에 있다.

 

1. Sarsa: $(S,A)$ 에 대해서 다음 state-action $(S',A’)$ 을 얻는다. → $Q$-값을 업데이트 한다.
2. Q-learning: $S$로부터 Action $A$를 얻는다. → $Q$-값을 업데이트 한다.

Sarsa는 (S,A, S’) 를 가지고 있는 상태에서 다음 행동을 샘플링한 뒤에, 두 가지 Q-value값의 차이를 이용해서 한다. 따라서 주어진 상태에 대해서 다음 상태값과 행동이 중요하며, 이를 통해서 Q-value가 점진적으로 수렴하는 것이다. 이와 다르게 Q-learning은 그냥 주어진 상태에서 Q-value값이 최대가 되는 행동을 선택한다. 게임으로 비유하자면 마리오로 점프를 하고 버섯을 밟은 뒤, 다음 행동을 버섯을 밟은 것까지 고려해서 샘플링 하는 것이다. 이로부터 연속적인 사고가 요구된다. 그러나 Q-learning은 버섯을 밟은 뒤, 다음 행동은 버섯을 밟은 것과 상관없이 Q-value값을 최대화하는 방향으로 뽑힌다.

 

 

Contact: bumjin@kaist.ac.kr