Monte Carlo Control without Exploring Starts
Exploring starts라는 가정을 없애려면 어떻게 해야할까? 바로 에이전트가 계속 탐험을 할 수 있도록, 즉, 해보지 않은 행동에 대해서도 가끔 선택할 수 있도록 해야 한다. 그러한 방법에는 두 가지가 있는데 하나는 on-policy, 다른 하나는 off-policy가 있다. on-policy는 결정했던 행동들을 가지고 정책 평가와 발전을 하지만 off-policy는 다른 방법에 의해 만들어진 데이터로 정책 평가와 발전을 한다. Monte Carlo ES 또한 on-policy이며, 이번 절에서는 Monte Carlo control를 exploring starts 없이 어떻게 만드는지 보인다. off-policy는 다음 절에서..
on-policy control 방법은 정책이 soft하다. soft하다는 말은 정책의 모든 확률이 0 이상, 즉 모든 행동을 일정 확률로 할 가능성이 있다는 뜻이다. 하지만 점점 결정적인 최적의 정책(deterministic optimal policy)으로 바뀌고 만다. 챕터 2에서 다루었던 $\epsilon$-greedy가 해결책으로 사용될 수 있다. $\epsilon$-greedy는 가끔 일정 확률 $\epsilon$에 따라 랜덤하게 행동을 선택하고 그 외 대부분($1-\epsilon$)은 agent의 정책에 따라 행동하는 것을 말한다. 랜덤하게 행동을 선택할 확률 최소값은 $\frac{\epsilon}{|\mathcal{A}(s)|}$이며, 나머지 확률 $1-\epsilon+\frac{\epsilon}{|\mathcal{A}(s)|}$로, greedy 행동을 취한다. (여기서 $1-\epsilon$에 $\frac{\epsilon}{|\mathcal{A}(s)|}$를 추가한 이유는 랜덤하게 하는 행동 중 하나가 이 greedy 행동을 할 것이기 때문이다.)$\epsilon$-greedy 정책은 확률이 $\pi(a|s) \ge \frac{\epsilon}{|\mathcal{A}(s)|}$로, $\epsilon$-soft policy의 한 예다.
on-policy Monte Carlo control도 마찬가지로 GPI에 속한다. Monte Carlo ES가 그랬듯이, action-value를 estimate하기 위한 방법으로 first-visit MC를 사용할 것이다. 하지만 exploring starts 가정 없이는 탐험을 할 수 없기 때문에 무작정 가치를 따라 greedy하게 행동하도록 할 수는 없다. 따라서 on-policy는 $\epsilon$-greedy로 할 것이다. 아래 알고리즘이 바로 그 예이다.
$\epsilon$-greedy policy 또한 정책 개선 이론에 따라 확실히 개선된다고 할 수 있다. $\pi'$를 $\epsilon$-greedy policy라고 하자. 정책 개선 이론을 적용하면,
(합은 weighted average가 1이고, 가장 큰 수보다 작거나 같다. 참고로 맨 아래 식은 모든 행동에 대한 확률의 합이 1이 되도록 한 식이다.)
결국 정책 x 가치의 합이기 때문에 이는 상태 가치함수와 같다. 결국 $q_\pi(s, \pi'(s)) \ge v_\pi(s)$이므로, 정책 개선 이론에 따라 $\pi' \ge \pi$ (즉, $v_{\pi'}(s) \ge v_\pi(s)$)가 된다.
이제 $\epsilon$-soft policy인 경우도 동일한 지 증명한다. 기존 환경과 동일하지만 $\epsilon$-soft가 들어갔다는 차이밖에 없다. 동일한 행동과 상태들, $\epsilon$에 따라 랜덤한 행동을 하는 것까지. $\tilde{v}_\ast$와 $\tilde{q}_\ast$를 새로운 환경에서의 최적의 가치함수들이라 하자. 그렇다면 $\epsilon$-soft policy는 $v_\pi=\tilde{v}_\ast$라면 $\pi$는 최적이라 할 수 있을 것이다. 따라서 정의에 따라 최적의 해는 다음과 같이 구할 수 있다.
$v_\pi$를 $\tilde{v}_\ast$로 바꾸면,
policy iteration은 $\epsilon$-soft policy에서도 적용이 된다는 것을 보였다. $\epsilon$-soft policy에 greedy policy를 적용하면 매 step마다 개선이 확실히 된다는 것을 보이며, exploring starts를 제거했다.
