Model-Free Policy Evaluation

Monte-Carlo Learning

Monte-Carlo Learning is a Model-Free Policy Evaluation method. it is unbiased..? (i think every visit is biased?)

Intuition: Takes averages of actual returns over episodes. As more returns are observed, the average should converge to the expected value.

• MC methods learn directly from episodes of experience
• MC learns from complete episodes: no bootstrapping
  • Caveat: This means that we can only apply it to episodic MDPs, i.e. all episodes must terminate
• Handles non-markovian domains

MC Policy Evaluation

Goal: learn $v_{\pi }$ from episodes of experience under policy $\pi$ $S_1,A_1,R_2,...,S_k\sim \pi$

Monte-Carlo policy evaluation uses empirical (the actual) mean return instead of expected return as we saw in Policy Iteration.

• Updates $V$ at the end of each episode
  • $V$ is an estimate of the value function using sample of return to approximate the expectation

First-Visit Monte-Carlo Policy Evaluation

For each state $s$ visited in episode $i$,

• The first time-step $t$ that state $s$ is visited in episode $i$
  • Increment counter $N(s)\leftarrow N(s)+1$
  • Increment total return $G(s)\leftarrow G(s)+G_{i,t}$
  • Value is estimated by mean return $V(s)=G(s)/N(s)$
  • By Law of Large Numbers, $V(s)\to v_{\pi }(s)$ as $N(s)\to \infty$

Properties:

• $V_{\pi }$ estimator is an unbiased Estimator of true ${\mathbb{E}}_{\pi }[G_t|S_t=s]$

Every-Visit Monte-Carlo Policy Evaluation

Same a first-visit, but update is done every time-step $t$ that state $s$ is visited in episode $i$.

Properties:

• $V_{\pi }$ every-visit MC estimator is a biased estimator of $V_{\pi }$ but consistent estimator and often has better MSE.

Incremental Monte-Carlo (MC)

Monte-Carlo methods can be implemented incrementally by using the Incremental Mean.

• Update $V(s)$ incrementally after episode $S_1,A_1,R_2,...,S_T$
• For each state $S_t$ with return $G_t$ $N(S_t)\leftarrow N(S_t)+1$ $V(S_t)\leftarrow V(S_t)+\frac{1}{N(S_t)}(G_t-V(S_t))$

We can replace $\frac{1}{N(S_t)}$ with $\alpha$ to get a more general Incremental MC Policy Evaluation: $V(S_t)\leftarrow V(S_t)+\alpha (G_t-V(S_t))$

• If we set $\alpha >\frac{1}{N(S_t)}$, then we attribute higher weight to newer data

Next

• Monte-Carlo Control