Monte Carlo Control
이제 Monte Carlo estimation이 control 문제에서 최적의 정책을 근사(approximate)하기 위해 어떻게 사용되는지 알아볼 것이다. Monte Carlo Control은 전반적으로 GPI의 아이디어와 비슷하다. GPI에서는 현재 정책에 대한 가치함수를 근사하고, 그 가치함수를 가지고 정책을 개선했었는데, 아래 그림처럼 이를 반복해가면서 최적의 정책과 가치함수를 찾았다고 볼 수 있다.
Monte Carlo도 이와 같이 policy iteration으로 본다면, policy evaluation과 policy iteration으로 나누어 볼 수 있다.
Policy evaluation에서는 많은 에피소드에 걸쳐 경험(experience)을 해서 행동 가치함수를 근사해 나간다. (이 때, 에피소드는 무한한 수이고, exploring starts이라고 가정한다.) 결국 임의의 $\policy_k$에 대한 행동 가치함수 $q_{\pi_k}$를 경험으로 구하는 것이다.
Policy improvement에서는 마찬가지로 현재 가치함수를 가지고 policy greedy로 새로운 정책을 구한다.
이전 절에서 얘기했던 것처럼 이렇게 greedy하게 policy improvement를 할 경우 가치함수가 더 높게 나옴을 얘기했었다.
따라서 Monte Carlo 방법은 환경의 dynamic에 대한 정보 없이 오로지 episode들을 가지고 최적의 정책을 찾을 수 있다.
그런데 위에서 했던 두 가정(에피소드가 무한하며 exploring starts)은 실제로 사용하려면 제거해야한다. 다만 exploring starts에 대해서는 나중으로 미룬다. 일단 에피소드가 무한해야한다는 가정에 대해서 얘기해보자면, 상대적으로 쉽게 없앨 수 있다. 사실 DP에서 policy evaluation 방법도 가치가 true value에 도달하려면 무한히 많이할수록 좋았다. 이 두 방법 다 해결할 방법이 두 가지가 있다.
첫 번째 방법은 DP 알고리즘에서 나왔던 것과 비슷하다. DP 알고리즘에서 $\Delta$를 두어 가치함수의 변화가 일정 미만이 될 때까지 policy evaluation을 했었다. 즉, 어느 정도 수렴했다 싶으면 멈추는 방법으로, 근사 수준(level of approximation)을 정해두는 것이다. 하지만 실제 문제에서는 많은 에피소드가 걸릴 수도 있고 실제 문제가 아니더라도 그렇지 않을거란 보장이 없기 때문이다.
두 번째 방법은 policy evaluation의 횟수를 제한하는 것이다. 말 그대로 무한히 하지않고 몇 번하고 가치함수가 true value에 도달하지 않았더라도, 거기서 멈추고 policy improvement하는 것이다. 예를 들어 이전의 value iteration처럼 policy evaluation 한번, policy improvement 한 번, 이렇게 policy evaluation 횟수를 줄이는 것이다.(극단적으로 1번이지만 수렴했었다)
위에서 얘기한 policy evaluation과 policy improvement는 Monte Carlo policy iteration으로 본다면 매 step마다가 아니라 episode가 끝날 때마다 하는 것으로 바꿀 수 있다. 에피소드가 끝나면 return의 값으로 policy evaluation을 하고 이것이 끝나면 policy를 개선하고 끝나면 다시 에피소드 시작하는 것이다. 아래 의사 코드는 이를 반영한 Monte Carlo ES(Exploring Starts)이다.
