Incremental Implementation
Monte Carlo 또한 이전의 episode별로 해서 incremental implementation을 할 수 있다. 이는 2.4절에 나왔었다.
다만 차이점은 average reward가 아닌 average return으로 한다는 점이다. 그 외에는 거의 똑같이 on-policy Monte Carlo 방법에 적용된다. 하지만 off-policy Monte Carlo에서는 importance sampling(ordinary or weighted)이 고려되어야 한다.
먼저 ordinary importance sampling 같은 경우, importance sampling ratio를 구하고,
이전처럼 importance sampling ratio를 적용해 scaling된 가치로 보고
Incremental implementation을 적용한다. (아래 식은 책에 없지만 내 추측이 이럴 거 같다. 여기서 $C_n$은 각 상태에 대해 방문 횟수를 더한 것이다.)
$$V_{n+1}= V_n + \frac{1}{n} \left [ \frac{ \rho_{n:T(n)-1}G_n}{|\mathcal{J}(s)|} - V_n \right ] $$
weighted importance sampling은 조금 다르게 적용되어야 하는데, 이전에 적용했던 식을 다시 보면 다음과 같았다.
여기에 importance sampling ratio를 $W_i=\rho_{t_i:T(t_i)-1}$로 치환해서 나타내면, 다음과 같다.
여기에 incremental implementation을 적용하면 다음과 같게 된다. (뭔가 되는 것 같은데 수학적 머리가 잘 안돌아가서 직접 풀어보진 않음)
여기서 $C_0 \doteq 0$부터 $V_1$는 임의의 값으로 시작한다. 일단 weighted importance sampling으로 적용했지만 target과 behavior policy가 같다면($\pi=b$), W가 1이 되어 분모 분자가 제거되어 on-policy를 적용한 경우가 된다. 행동 가치함수 ($Q$)로 해도 수렴한다.
