[강화학습] 4. Monte Carlo Methods

Monte Carlo Methods (MC)

앞서 MDP에서는 environment의 dynamics를 정확히 알고 있을 때 Bellman equation이라는 좋은 모델을 사용해서 optimal value와 policy를 dynamic programming으로 planning 하였다.

이번 포스팅에서는 environment의 dynamics를 완전히 모른다고 가정하고, 이에 대한 해결책으로 Monte Carlo method로 learning하는 방법에 대해 알아본다.

MC는 DP에서 계산에 필요했던 dynamics와 Bellman equation과 같은 함수를 사용하지 않는대신, (그래서 model free method라고도 한다.)

경험(experience)(실제로 환경과 상호작용하면서 주고받은 state와 action, reward)이 필요하다. 

어쩌면 dynamics를 모르는 환경에서 순수한 경험(experience), 시행착오(try-and-error)를 거치며optimal policy를 찾는 것이 진정한 의미의 RL이란 생각도 든다. 

※ 실제로 MDP를 Planning, Monte Carlo를 Learning으로 구분한다.

하지만 General Policy Iteration(GPI) 처럼 가치를 계산해서 정책을 개선한다는 점은 변함이 없다. 다만 가치를 계산할 때 MDP의 dynamics + BE가 아닌 Return들의 평균을 이용할 뿐이다.

위 그림은 sample based의 간단한 grid word 예제를 보여준다.

A, D가 각각 -10, +10의 reward를 갖고, 그 외에는 -1의 reward를 가질때, 각 state-value를 계산한 결과이다.

예를 들어 C를 start state로 했을 때 얻은 return는 각각 +9, +9, +9, -11이므로 그 평균인 +4가 state C의 state value가 된다.

Monte Carlo는 위 예제와 같이 return을 평균시키는 방법을 기반하고 있기 때문에, episodic task라는 전제를 깔고 진행된다. (terminal state 혹은 종료 조건이 있다.) 

즉, MC는 episode가 끝났을 때 value estimate와 policy improvement가 일어난다. 그래서 step-by-step(online)이 아닌 episode-by-episode로 볼 수 있다.

이제 MC에 대해서 본격적으로 알아볼텐데, 결론부터 말하자면

"Monte Carlo = Sample mean"

위 문장을 기억하고 아래 포스팅을 읽으면 왜 이렇게 표현했는지 금방 이해될 것이다.

앞으로 다룰 내용인 MC method의 process는 아래와 같다.

• Prediction problem : policy π가 주어지면 value function을 계산한다.

• Policy improvement problem : 계산된 value function으로 better policy π를 찾는다.

• Control problem : GPI(general policy iteration)을 이용해 optimal policy를 찾는다.

Monte Carlo Prediction

MC의 prediction의 목표는 DP와 마찬가지로 π가 주어졌을 때 state-value function을 구하는 것이다. 

그리고 우린 앞서 state-value function을 구하는 방법을 이미 배웠다. 다만 차이점이 있다면 dynamics p(s', r | s, a) 를 모르기 때문에 DP때 처럼 BE로는 prediction 할 수가 없다. 

그래서 MC method는 value와 return의 original 정의를 사용하여, 

value를 expected return대신 곽측되는 reward의 empirical mean return(=sample mean)를 사용해 policy를 평가한다.

사실 우리는 이 과정을 이미 한번 해 봤다.

바로 앞서 설명한 이 예제이다. 여기에 first time visit이라는 개념만 추가하면 완벽히 MC prediction의 원리를 보여준다.

위 예제는 아쉽게도 모든 state를 1번씩만 방문했는데, 

만약 vπ(state=C)를 구하기 위한 또 다른 sample episode 5가 B→C→B→C→D와 같은 경로였다면, state C의 first time visit MC는 바로 파란색 지점을 기준으로 return을 구한다.

위 pseudo code의

• Loop for each step of episode, t = T-1, T-2, ..., 0은 terminal state에서 거꾸로 오면서 return을 더하기 위함이고,

• Unless St appears in S0, ... 이 first visit이 나타날 때까지 누적된 return을 평균내기 위한 조건문이다.

여기서 MC의 중요점은,

• state-value를 expected value를 사용해 구한 DP와 달리, sample의 return평균으로 구했음으로 bootstrap 방식이 아니다.

• 동일한 이유로, 각 state의 가치 estimate 결과는 서로 독립적이다.
  예를 들면 v(s1)에 대한 update에 v(s2)는 관여하지 않고, 오로지 v(s1) return의 평균으로만 update한다.

• 그리고 굳이 처음부터가 아니라 관심있는 state를 start state로 하는 부분 episode로 부터 관심 있는 state의 가치를 구할 수 있다.
  (바둑에서 특정 구역에서의 policy를 더욱 정교하게 만들고 싶을 때를 예로 들 수 있다.)

Monte Carlo Estimation of Action Values

state-value에 대해 평가 했다면, 이제 better policy를 찾기 위해 action-value를 estimate할 차례이다.

[DP에서 사용한 state-value vs. action-value간 관계식]

다만, DP에서는 Bellman equation을 통해 state-value를 action-value equation에 대입해서 쉽게 구했지만, MD에서는 여전히 dynamic를 모르기 때문에 다시 한번 action-value qπ(s, a)를 estimate할 수 밖에 없다. 다만 이 때, 한가지 문제가 있다.

p(s, a) > 0, for all s, and a (assumption of exploring start)

qπ(s, a)를 estimate하려면 모든 state s에서 action a를 한 사건이 최소 한번은 있어야 한다. 그래서 일단 MD에서는 위와 같이 모든 사건이 episode에서 관측된다는 가정을 가지고 action-value estimation한다. 

estimate하는 방법은 state-value를 estimate한 것과 같이 sample mean을 활용할 텐데, 조금 뒤에 pseudo-code에서 간단히 설명하도록 한다.

Monte Carlo Control

이제 estimated action-value를 이용해 optimal policy를 근사할 것이다.

물론 전반적인 아이디어는 GPI아이디어와 동일한데, DP 문제에서는 state-value function을 이용해 policy evaluate한 다음, 그 함수를 가지고 policy를 improve했는데, MD에서도 evaluate-improve의 반복원리를 그대로 따른다.

다만 다른점이 있다면, MC의 policy evaluation은 action-value function을 근사한 것이고,

※ DP는 state-value function을 evaluate했다.

policy improvement는 DP와 동일하게 greedy policy로 새로운 policy를 구한다.

그리고 앞서 greedy 하게 policy improvement를 했을 때 better policy임을 증명했음으로,

Monte Carlo 방법은 환경의 dynamics에 대한 정보 없이 오로지 episode들을 가지고 optimal policy를 찾을 수 있단 것을 알 수 있다.

다만 앞서, 조금 찝찝한 가정을 2개 했었다.

• 모든 state가 에피소드에 등장한다. (exploring start)

• 굉장히 많은 episode가 존재한다.

일단 episode의 수에 대한 문제는 적절한 시점을 converge했다고 인정하기 위한 δ를 사용하거나, max-iteration 을 정의해서 쉽게 해결할 수 있다.

골치 아픈 가정은 바로 exploring start인데, 일단 이 가정을 만족한다치고, MC의 pseudo code를 먼저 살펴보자.

사실 위 pseudo code는 DP의 pseudo code와 거의 유사한데,

• 모든 state와 action에 대한 return의 평균으로 Q(St, At)를 근사화 하고, (average(Returns(S, A))

• Q를 최대화 하는 action을 policy로 update하는 모습을 확인할 수 있다. (argmax)

Monte Carlo Control without Exploring Start

특히 exploring start는 현실 문제에 적용하기에는 너무 practical한 제약조건이다.

일단, 모든 state를 방문한 sample episode을 마련하는 것은 현실적으로 불가능하기 때문에,

차라리 agent가 학습하지 못한 상황에서도 계속 탐험할 수 있도록(exploring) 이끌어야 한다. 그리고 이러한 방법에는 on-policy와 off-policy approach가 있다.

• on-policy method 
   : 현재 policy π를 사용해서 나온 action들로부터 action-value function을 배우는 개념
     (앞서 다룬 MC with ES가 여기 속한다.)

• off-policy method
   : 현재 policy가 아닌 다른 action(ex. random action)들로 부터 action-value function을 배우는 개념.
• 
  

지금껏 policy iteration에 채택하고 있는 greedy policy는 사실 굉장히 deterministic 한 정책이다. 한치의 타협없이 가장 가치가 큰 action을 결정할 확률을 1.0, 아닌 것은 0.0으로 둔다. 

그래서 사실 π(a | s) 이렇게 표기할 필요도 없다. 왜냐하면 π(s) 가 이미 deterministic하게 결정되어 있기 때문이다.

그래서 만약에 s가 전혀 가보지 못한 새로운 state라면 greedy policy는 아무런 action을 취하지 못한다. 그래서 이 정책을 조금 soft한 policy로 바꿔줄 필요가 있고, 그 방법중 하나가 앞서 배운 ε-greedy method이다.

[ ε-greedy는 사실 ε-soft의 special case이다.]

위 soft policy를 적용해서 first-visit으로 action-value를 estimate하는 MC control의 pesudo code는 아래와 같다.

pseudo code는 MC with exploring start와 모두 동일하고 마지막에 policy를 update할 때 ε-greedy policy를 적용했음을 확인할 수 있다.

이 때, 한가지 아이디어를 떠올릴 수 있는데, Q를 evaluate하는 부분

Q(S, A) ← average(Returns (St, At))

이 부분을, episode에서 관측된 Return이 아니라, update 과정에서 발생한 policy π가 주는 action a'를 이용해 학습하면 바로 on-policy의 대표 알고리즘인 SARSA 알고리즘이 된다.

혹은 아래와 같이 π와 상관없이 가능한 모든 action의 최대 가치로 학습할 수도 있다.

아래 알고리즘이 바로 off-policy의 대표 알고리즘인 Q-Learning이다.

Summary

• Monte Carlo method는 experience(=sample episode)로부터 optimal policy를 배운다.

• 즉, DP는 dynamics가 있어야 하지만 MC는 episode가 주어진다면 학습이 가능하다.

• 이 때 사용하는 value evaluate 방법은 sample mean이다.

• MC는 estimate value들로 부터 policy를 estimate하는게 아니고 sample로부터 직접 estimate하기 때문에 으로 bootstrap이 아니다. 

• 하지만 episode-by-episode방식이라 episode가 길거나 끝나지 않으면 policy는 update되지 않는다.

• 예를 들어 Atari game은 episode가 굉장히 길기 때문에 episode를 모으는 것도 어렵고, learning할 때 많은 시간이 걸린다. (MC의 가장 큰 단점이다.)

• 주어진 episode로만 policy를 찾기 때문에 sample episode에 과적합 될 수 있다. variance를 낮춰 주기 위해 large number of sample episode가 필요하다.