[Monte Carlo methods - 2] GPI with Monte Carlo methods

Generalized Policy Iteration (GPI)

Monte Carlo methods를 사용하여 control tasks를 풀기위해서 GPI를 사용한다. 초기에는 임의의 Policy로 시작한다. Agent는 첫 episode의 처음부터 끝까지 초기 Policy를 사용하면서 trajectory를 생성한다. 이후 각 시간에서의 return이 rewards의 discounted sum으로 계산된다.

$$ S_0, A_0, R_1, S_1, A_1, R_2, ..., R_T $$

$$ G_t = R_{t+1} + \gamma R_{t+2}+\gamma^2 R_{t+3} + ... + \gamma^{T-t-1} R_T $$

$$ G_{t+1} = R_{t+2} + \gamma R_{t+3}+\gamma^2 R_{t+4} + ... + \gamma^{T-t-1} R_T $$

$$ ... $$

위에서 얻은 return들로 이전에 해당 State 혹은 Action의 return들과 평균을 내는 방식으로 Value Function의 estimate한다. (Policy Evaluation) 이후, Estimate된 Value function을 기반으로 Policy를 개선한다.(Policy Improvement)

Problem

DP에서는 transition probability와 expected rewards를 통해서 아래의 식으로 가장 높은 return을 주는 action을 찾을 수 있었다. DP와는 다르게, Monte Carlo methods에서는 model of environments를 사전에 알지 못하기 때문에 아래 식에서의 $v_\pi(s')$를 사용할 수 없다.

$$ \pi'(s) = \arg\max_a\sum_{s',r}p(s',r|s,a)[r+\gamma v_\pi(s')] $$

이를 해결하기 위해 States의 Value를 estimate하는 대신 각 State에서 개별 Action을 행할 때의 expected return을 estimate하는것이 좋은 방법이다. 이후 각 Action의 expected returns의 estimates를 비교하여 가장 높은 expected return을 가진 action을 찾으면 된다. (Q-value의 기능) 왜냐하면, 아래 식에서 볼 수 있듯이, Action의 expected return 즉, Q-value($q_\pi(s, a)$)가 내재적으로 $v_\pi(s')$을 내재하고 있으므로 우리는 $v_\pi(s')$를 몰라도 되며 Q-value가 높은 Action을 선택하면된다. (Q-value에 환경의 dynamics가 내재되어있다는 뜻)

$$ q_\pi(s,a) = \sum_{s', r}p(s',r|s,a)[r+\gamma v_\pi(s')] $$

즉, Monte Carlo에서는 State Value($V(s)$) 대신 Q-value($Q(s, a)$)를 keep a table 할 것이다.

$$ \pi'(s) = \arg\max_a q_\pi(s,a) $$

GPI에서 Policy Evaluation 단계에서 Q-value를 사용할 것이며, Policy Improvement 단계에서도 Q-value function의 estimate를 update하며 Policy를 개선할 것이다.

The Importance of Exploration

위의 Q-value를 사용한 GPI 과정을 진행할 때 명심해야할 점은 $Q(s, a)$는 Estimate라는 점이다. 이는 Agent가 Policy를 따르면서 Environments와 상호작용하며 얻은 경험에 기반한다. 따라서 Estimate가 학습 초기 단계에서는 정확하지 않을 수도 있다. 이렇게 학습 초기에 정확하지 않은 Estimate가 만약 Optimal인 선택지의 Estimate를 낮게 측정한다면, Agent는 해당 선택지를 절대 선택하지 않을 것이며 이는 결국 Optimal인 선택지의 Estimate를 옳게 수정할 기회조차 없게될 수 있다는 것을 의미한다. 이것을 방지하는 방법은 모든 action을 explore하고 계속 estimate Q(s,a)를 update하는 방법이 유일하다. 이로써 밝혀지지 않은 가능한 optimal actions를 놓치지 않을 수 있다.

Two options

1. Exploring starts
   : Agent가 environment를 직면할 때 마다 random initial State에서 시작하고, random initial Action을 취하는 것으로 시작하는 것이다. 하지만, 이는 tasks의 수가 많아진다면 사용할 수 없기때문에 현실적이지 않다.
2. Stochastic policies
   
   : Policy에서 모든 action이 선택될 확률을 0보다 크게 하는 것이다. 이를통해 때때로 task를 개선 하기위해 optimal이 아니라고 생각되는 선택지를 선택하게 보장할 수 있다. 이를 통해 결과가 나쁠 것이라고 생각됐던 action이 optimal이 될 수도 있다. 이것이 첫번째 option보다 더 현실적이고 쉬워보인다.

• Stochastic policies는 2가지 다른 방법으로 구현될 수 있다.
  1. On-policy learning
     : Optimize할 때와 Explore할 때 같은 Policy를 사용한다.
  2. Off-policy learning
     : Optimize할 때와 Explore할 때 다른 Policy를 사용한다. 결국 총 2가지 Policy를 사용한다.