Monte Carlo Method

Definition

Monte Carlo method (MC) is tabular updating and model-free. MC policy iteration adapts GPI based on episode-by-episode (sample multi-step backup) of PE estimating $Q(s,a)=q_{\pi }(s,a)$ and $ϵ$-greedy PI.

MC Prediction (Policy Evaluation)

Learn $q_{\pi }$ from entire episodes of real experience under policy $\pi$.

Empirical Mean

MC policy evaluation uses empirical mean return $Q(s,a)$ instead of expected return. $Q(s,a)=\frac{S(s,a)}{n(s,a)}$ where $S(s,a)$ is increment total return and $n(s,a)$ is incremental count.

The mean return converges to true action-value function as incremental count increases. ${\lim }_{n(s,a)\to \infty }Q(s,a)=q_{\pi }(s,a)$

Incremental MC Update

The incremental mean can be expressed in a recursive manner: ${\mu }_k={\mu }_{k-1}+\frac{1}{k}(x_k-{\mu }_{k-1})$

Thus, for each state-action pair $(S_t,A_t)$ with return $G_t$, after one episode, the mean return $Q(s,a)$ can be calculated as: $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\frac{1}{n(S_t,A_t)}[G_t-Q(S_t,A_t)]$

Constant-$\alpha$ MC Policy Evaluation

It substitutes the weights, $\frac{1}{n(S_t,A_t)}$ used for incremental MC, with constant step-size $\alpha$. $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [G_t-Q(S_t,A_t)]=(1-\alpha )Q(S_t,A_t)+\alpha G_t$

MC Control ($ϵ$-Greedy Policy Improvement)

Choose the greedy action with probability $1-ϵ$ and a random action with probability $ϵ$. ${\pi }^{\prime }(a|s)=\{\begin{array}{ll}1-ϵ+\frac{ϵ}{|\mathcal{A}(s)|}& a=\underset{a^{\prime }}{\mathrm{argmax}}{Q}^{\pi }(s,a^{\prime })\\ \frac{ϵ}{|\mathcal{A}(s)|}& \text{otherwise}\end{array}$

For any $ϵ$-greedy policy $\pi$, $ϵ$-greed policy ${\pi }^{\prime }$ with respect to $q_{\pi }$ is always improved i.e. $v_{{\pi }^{\prime }}(s)\ge v_{\pi }(s)$.

$ϵ$-greedy policy is GLIE if ${ϵ}_k\to 0$ e.g. ${ϵ}_k=\frac{1}{k}$

Algorithm

1. Initialize $\forall s\in \mathcal{S},a\in \mathcal{A}(S),Q(S,A)$ arbitrarily, terminal $Q=0$, and arbitrary $ϵ$-soft policy $\pi$ (non-empty probability).
2. Repeat for each episode:
   1. Generate an episode following the policy $\pi$: $S_0,A_0,R_1,S_1,\dots ,S_{T-1},A_{T-1},R_T$.
   2. $G\leftarrow 0$
   3. Repeat for each step of an episode, $t=T-1,T-2,\dots ,0$ (MC Prediction):
      1. $G\leftarrow \gamma G+R_{t+1}$
      2. If $(S_t,A_t)$ is a first visit ($(S_t,A_t)\notin \{(S_i,A_i)|i=0,\dots ,t-1\}$), then $Q(S_t,A_t)\leftarrow AVG(\{G_t|t\in \{0,1,\dots ,T\},s=S_t,a=A_t\})$ where $AVG$ can be either incremental MC or constant-$\alpha$ MC.
   4. For each visited state $S_t$ in the episode (MC Control):
      1. $A^{\ast }\leftarrow \underset{a}{\mathrm{argmax}}Q(S_t,a)$
      2. $\pi (a|S_t)=\{\begin{array}{ll}1-ϵ+\frac{ϵ}{|\mathcal{A}(S)|}& a=A^{\ast }\\ \frac{ϵ}{|\mathcal{A}(S)|}& \text{otherwise}\end{array}$
3. If policy is stable, then stop and return $\pi \approx {\pi }_{\ast }$.

Facts

MC is less harmed by violations of Markov Property because it updates value estimates based on true Return $G_t$ (not based on value estimates of successor states).