[Monte Carlo methods - 1] Intro

Monte Carlo methods

Monte Carlo mehods는 경험에 기반한 알고리즘들 중 하나이다. 경험에 기반한 알고리즘들은 Agent가 환경과 상호작용하면서 모은 samples of experience를 기반으로 $v_*(s)$(optimal state-value)혹은 $q_*(s,a)$(optimal q-value)를 학습한다.

 

학습 초기에, Agent는 임의의 Policy를 따른다. Agent는 trace of experience(trajectory)를 생성하면서 episode가 끝날 때 까지 현재 Policy를 따라 task를 수행한다.

$$ S_0, A_0, R_1, S_1, A_1, ... , S_{T-1}, A_{T-1}, R_T $$

Episode가 끝났을 때, 모든 방문한 State로부터 얻어진 return을 계산한다.

$$ G_t = \sum_{k=0}^{T-t-1}\gamma^k R_{t+k+1} $$

Episode가 끝났을 때, 각 State의 Value는 현재 Policy를 따랐을 때의 expected return이다. 따라서 매 Episode마다 어떤 State에 대한 새로운 return을 얻었을 때, 해당 State에서 얻었던 returns들의 평균을 추정치로 갱신한다.

$$ V_\pi(s) = {1\over N}\sum_{k=1}^N G_{s_k} $$

Q-value에서도 똑같은 process가 적용된다. (action마다 해당 State에서 해당 action의 returns에 대한 평균을 추정치로 갱신)

$$ G_t = \sum_{k=0}^{T-t-1}\gamma^k R_{t+k+1} $$

$$ q_\pi(s,a) = E_\pi[G_t|s_t=s, A_t=a] $$

$$ Q_\pi(s,a) = {1\over N}\sum_{k=1}^N G_{s,a_k} $$

Law of large numbers

• 큰수의 법칙에 따라 우리가 observe하는 State나 Action이 많아질수록 그것들의 기댓값(State value / Q-value)에 더욱 더 근사된다.

Advantages of Monte Carlo methods

1. Estimate of State Value가 다른 estimate of State Value의 영향을 받지 않는다.
   • 이는 State Value를 추정하는데 필요한 complexity가 task의 state 수에 상관없음을 의미한다. (컴퓨팅 리소스 적음)
   • DP의 경우 다른 State들의 Value를 bootstrap하여 State Value를 estimate한다. 따라서 States들의 수에 따라서 complexity가 기하급수적으로 증가한다.
   • Bootstrap: 현재 상태의 추정치를 계산하기 위해 다른 추정치들을 사용하는 방법
2. Goal에 연관된 State들의 Value에만 자원을 집중할 수 있다.
   • 앞선 단원에서 실습했던 Maze를 예시로 하면, 도착지점까지가는 지점(State)들의 Value만 보면 된다.
   • DP의 경우 어떤 State의 중요도와 관계없이 모든 States를 순회(Sweep)하며 업데이트한다.
3. Model of the environment가 필요없다.(가장 중요!)
   • Dynamics of the environment는 이미 우리의 추정치에 내재되어있다.