◾Intro

🔻references

◾Main

🔻개념

🔸의미

• Monte Carlo = MC

• Monte Carlo란? 반복적인 랜덤 샘플링(repeated random sampling)을 사용하여 특정한 수치 결과(numerical result)를 얻어내는 계산 방법(computations).

  computations relied on repeated random sampling to obtain numerical results.

• 강화학습에는 크게 MC와 TD(temporal difference) 방식이 존재한다.

🔸Method

• 모든 RL이 tabular updating method를 사용하듯 MC도 마찬가지이다.

  • RL = Rainforcement Learning
  • tabular = action-value function에 대한 table을 의미 = 간단히 Q-table이라 하기도 한다.

• model-free : state transition probability에 대해 모르는 상태이다.

• MC Policy Iteration은 GPI(Generalized Policy Iteration)을 기반으로 한다. 다른 RL과의 차이점은 episode-by-episode로 샘플을 업데이트한다는 점이다. (MC는 한 episode가 끝나면 그것을 기반으로 PE, PI를 진행하기 때문에 episode-by-episode인 것.)

  Episode-by-episode GPI means that PE and PI are alternately repeated every episode.

  • episode task란? 유한한 시간 안에 종료되는 task
  • continuous task? 끝이 없는, 계속 진행되는 task
  • PE = Policy Evaluation
    • MC의 PE는 $\mathcal{Q}(s,a)=q_\pi(s,a)$를 평가
  • PI = Policy Improvement
    • MC의 PI는 $\epsilon\text{-greedy PI}$를 사용

• sample multi-step backup

  • 하나의 step이 terminal state까지 이동해야 episode 하나가 끝나는 구조.

    

⇒ MC learns from the entire trajectories(궤적) of sampled episodes of real experiences by updating after every single episode.

• Q Value = average of returns $G_t$ of sampled episodes

🔸특징

• 장점

  • MC뿐만 아니라 강화학습의 전반적인 장점은 ‘효율성’이다. 모든 경우의 수를 확인하는 dinamic programming과 달리 MC는 전체(state space) 중에서 샘플링한 것(small subset)에만 초점을 두고 해당 샘플들을 기반으로 value function을 업데이트한다. 이는 실제로 일어날 법한 경우의 수에 초점을 두고, 대부분의 쓸모없는 경우의 수는 무시하는 것이라고 해석할 수 있다.

    → Go game처럼 하나의 게임이 끝난후 reward를 평가를 하는 방식.

  • MC만의 장점으로 Markov property를 어느정도 충족하지 못해도 좋은 성능을 보여준다.

    +) Bootstrapping : Q-value를 업데이트할 때 $G_t$(true value, model-based에서 모든 경우의 수를 계산하여 얻은 expected return) 와 $R_{t+1}+\gamma Q(S_{t+1},A_{t+1})$(estimates, approximates. 근사치) 를 사용하는 두가지 방법이 있다(참고). bootstrapping은 이중 근사치를 사용하여 업데이트하는 방식이다.

    • MC는 bootstrapping이 아니다. bootstrapping에서는 markov property가 아주 중요하다고 한다. 그래서 bootstrapping을 사용하는 TD에서는 markov property가 지켜지는 것이 중요. 그러나 MC는 그렇지 않다고 하는데 아직 잘 이해 안 됨…