Monte Carlo Methods
이전 챕터와 다르게 이번 챕터에서는 환경에 대해서 완전히 모른다고 가정한다. 이에 대한 해결책으로 Monte Carlo라는 방법을 사용한다. 이 방법은 경험(experience)(실제로 환경과 상호작용하면서 주고받은 상태와 행동, 보상들)이 필요한 대신 DP에서 계산에 필요했던 dynamic(상태나 보상에 대한 확률들)을 사용하진 않는다. 하지만 General Policy Iteration(GPI) 처럼 가치를 계산해서 정책을 개선한다는 점은 변함이 없다. 다만 가치를 계산할 때 MDP의 dynamic이 아닌 MDP에 의해 나온 return들의 평균을 이용할 뿐이다.
Monte Carlo는 return 샘플들을 평균시키는 방법을 기반하고 있기 때문에, episodic task라는 전제로 내용을 진행한다. (그리고 어떤 행동을 하든지 결국 episode가 종료된다고 하자) 이 방법은 episode가 끝났을 때에야 가치 추측(estimate)과 정책 변화가 일어난다. 그래서 step-by-step(online)이 아닌 episode-by-episode로 볼 수 있다.
Monte Carlo Prediction
우선 주어진 정책에 대한 상태 가치함수를 학습하는 Monte Carlo 방법을 볼 것이다. 상태 가치함수를 경험으로 구하는 방법은 그 상태에서 얻었던 return들의 평균을 내는 것이다. 당연히 얻은 return이 많을 수록 실제 expected value에 수렴한다. 좀 더 구체적으로, 어떤 정책 $\pi$에 따라 $v_\pi(s)$를 estimate하고 싶고, 어떤 상태에 가게 되면 이를 방문(visit)했다고 하자. 당연히 어떤 상태에 여러번 방문할 수도 있다. first-visit MC 방법은 처음 방문했던 것에 대한 return만 구하고, every-visit MC 방법은 방문한 모든 return을 고려한다. 둘 다 무한히 하면 $v_\pi(s)$에 수렴하지만, 이론적으로 다르다. First-visit MC 방법은 이전부터 많이 연구가 되어 왔던 것이며, 이번 챕터에서 다룰 내용이다. 그리고 Every-visit은 나중에 나올 function approximation(ch 9)과 eligibility trace(ch 12)에 더 잘 맞다.
First-visit MC가 어떻게 동작하는 지 보기가 쉽다. return의 평균이 편향된 것은 아니지만(unbiased estimate) 편차는 존재하는 데, $1/\sqrt{n}$ ($n$은 return의 수) 만큼의 표준편차를 가진다. 반면 Every-visit MC는 조금 덜 직관적이지만, 더 빨리 수렴한다.
책에서는 블랙잭의 예제를 나타내지만 생략한다. 앞으로도 예제들은 다 생략할 예정. 이론적인 내용에 집중할 것이다.
복잡한 환경에서 DP는 매번 모든 확률을 가지고 복잡하고 틀릴수도 있는 계산을 한다. 반면, MC는 그저 경험을 가지고 샘플링할 뿐이라 쉽다.
이 알고리즘 또한 backup diagram으로 표현할 수 있다. 맨 위 root 노드에서 시작해서 종료 상태(terminal state)까지 이동(transition)하는 것을 다음과 같이 표현한다. DP에서는 1-step 뒤에 모든 상태에 대한 가치를 고려해서 업데이트 했지만, MC는 종료 상태까지 갔다가 지나간 경로의 상태들의 가치만 업데이트하는 것을 볼 수 있다.
MC에 있어 중요한 점 중에 하나는 각 상태에 대한 가치 estimate는 독립적이라는 것이다. $v(s_1)$에 대한 업데이트에 $v(s_2)$는 필요 없다. 오로지 Return의 평균으로 업데이트 하기 때문이다. 즉, DP와 달리 bootstrap을 하지 않는다. 그러다보니 한 상태에 대한 가치를 구할 때도, 굳이 다른 상태 가치에 대한 계산이 필요하지 않다. 또한 굳이 처음이 아니라 중간부터 시작해서 중간 지점에 대한 가치를 구할 수도 있다.
