Monte Carlo Methods

Why Monte Carlo?

• Requires only experience — sample sequences of states, actions, rewards from actual interaction (no model at all) or simulated interaction (a sample model that only generates transitions, not the full distributions DP needs).
• Defined here only for episodic tasks, so well-defined returns exist. Values and policies change only at the end of an episode — incremental episode-by-episode, not step-by-step.
• Like bandits, MC averages samples per state–action pair — but now there are many interrelated "bandits": the return after an action depends on later actions, which are also being learned ⇒ nonstationary from the earlier state's viewpoint. Handled with GPI.

5.1 Monte Carlo prediction

Estimate $v_\pi(s)$ by averaging the returns observed after visits to $s$. The first occurrence of $s$ in an episode is its first visit.

Input: a policy π to be evaluated
Initialize:
    V(s) ∈ ℝ, arbitrarily, for all s ∈ S
    Returns(s) ← an empty list, for all s ∈ S
Loop forever (for each episode):
    Generate an episode following π: S₀, A₀, R₁, S₁, A₁, R₂, …, S_{T−1}, A_{T−1}, R_T
    G ← 0
    Loop for each step of episode, t = T−1, T−2, …, 0:
        G ← γG + R_{t+1}
        Unless S_t appears in S₀, S₁, …, S_{t−1}:      // drop this check → every-visit MC
            Append G to Returns(S_t)
            V(S_t) ← average(Returns(S_t))

Example 5.1 — Blackjack

• Episodic, undiscounted (γ = 1); reward +1 win, −1 lose, 0 draw (also the return). Actions: hit or stick. Infinite deck. Dealer sticks on ≥ 17.
• State = (player sum 12–21, dealer's showing card A–10, usable ace?) → 200 states. A usable ace counts as 11 without busting.
• Evaluate the policy "stick only on 20 or 21". Even though we know the rules completely, computing $p(s',r\mid s,a)$ for DP would be complex and error-prone; generating sample games is easy.

Backup diagram and key properties

5.2 Monte Carlo estimation of action values

Same methods, but visits are to state–action pairs. Problem: under a deterministic π, only one action per state is ever observed, so other actions' estimates never improve. This is the problem of maintaining exploration.

Exploring starts (ES): every episode starts in a state–action pair, and every pair has non-zero probability of being the start ⇒ all pairs visited infinitely often. Useful in simulation, but cannot be relied on when learning from real interaction.

5.3 Monte Carlo control

Policy improvement is greedy w.r.t. the current action-value function — no model needed:

Two unrealistic assumptions give the easy convergence guarantee: (1) exploring starts, (2) infinitely many episodes per evaluation. Remove (2) like value iteration does — don't complete evaluation; alternate evaluation and improvement episode by episode:

Initialize:
    π(s) ∈ A(s) (arbitrarily), for all s ∈ S
    Q(s,a) ∈ ℝ (arbitrarily), for all s ∈ S, a ∈ A(s)
    Returns(s,a) ← empty list, for all s ∈ S, a ∈ A(s)
Loop forever (for each episode):
    Choose S₀ ∈ S, A₀ ∈ A(S₀) randomly such that all pairs have probability > 0
    Generate an episode from S₀, A₀, following π: S₀, A₀, R₁, …, S_{T−1}, A_{T−1}, R_T
    G ← 0
    Loop for each step of episode, t = T−1, T−2, …, 0:
        G ← γG + R_{t+1}
        Unless the pair S_t, A_t appears in S₀, A₀, S₁, A₁, …, S_{t−1}, A_{t−1}:
            Append G to Returns(S_t, A_t)
            Q(S_t, A_t) ← average(Returns(S_t, A_t))
            π(S_t) ← argmax_a Q(S_t, a)

5.4 Monte Carlo control without exploring starts (on-policy)

On-policy control uses soft policies: $\pi(a\mid s)>0$ for all $s,a$, gradually shifted toward a deterministic optimal policy. ε-soft: $\pi(a\mid s)\ge\varepsilon/|\mathcal A(s)|$. ε-greedy policies (non-greedy actions get $\varepsilon/|\mathcal A(s)|$, greedy gets $1-\varepsilon+\varepsilon/|\mathcal A(s)|$) are the ε-soft policies closest to greedy.

GPI only requires moving the policy toward greedy, so we move it to ε-greedy:

Algorithm parameter: small ε > 0
Initialize:
    π ← an arbitrary ε-soft policy
    Q(s,a) ∈ ℝ (arbitrarily), for all s ∈ S, a ∈ A(s)
    Returns(s,a) ← empty list, for all s ∈ S, a ∈ A(s)
Repeat forever (for each episode):
    Generate an episode following π: S₀, A₀, R₁, …, S_{T−1}, A_{T−1}, R_T
    G ← 0
    Loop for each step of episode, t = T−1, T−2, …, 0:
        G ← γG + R_{t+1}
        Unless the pair S_t, A_t appears in S₀, A₀, …, S_{t−1}, A_{t−1}:
            Append G to Returns(S_t, A_t)
            Q(S_t, A_t) ← average(Returns(S_t, A_t))
            A* ← argmax_a Q(S_t, a)                       (with ties broken arbitrarily)
            For all a ∈ A(S_t):
                π(a|S_t) ← 1 − ε + ε/|A(S_t)|   if a = A*
                           ε/|A(S_t)|           if a ≠ A*

Any ε-greedy policy π′ w.r.t. $q_\pi$ is an improvement over any ε-soft π:

(The max is ≥ any weighted average with non-negative weights summing to 1.) Equality holds only when π is optimal among ε-soft policies — shown by "moving the ε-softness inside the environment" (with prob. ε the environment re-picks the action at random); the best general policy there equals the best ε-soft policy here. Trade-off: we only reach the best ε-soft policy, but we no longer need exploring starts.

5.5 Off-policy prediction via importance sampling

Coverage assumption: $\pi(a\mid s)>0 \Rightarrow b(a\mid s)>0$. So $b$ must be stochastic wherever it differs from π; π may be deterministic (typically greedy).

The unknown dynamics cancel — the ratio depends only on the two policies and the observed sequence. It corrects the expectation:

Number time steps continuously across episodes; $\mathcal T(s)$ = time steps at which $s$ is visited (first visits only for first-visit), $T(t)$ = first termination after $t$.

Example 5.5 — infinite variance

One state $s$; right → terminate with reward 0; left → back to $s$ w.p. 0.9, or terminate with +1 w.p. 0.1. Target: always left ⇒ $v_\pi(s)=1$. Behaviour: left/right ½ each. Episodes ending with right have ρ = 0; an episode of $k+1$ lefts has ρ = $2^{k+1}$. The second moment of the scaled return:

Ordinary IS estimates fail to converge even after millions of episodes; weighted IS gives exactly 1 after the first episode ending with left. Trajectories with loops easily cause this.

5.6 Incremental implementation

On-policy MC and ordinary IS: use the Chapter 2 incremental mean on (scaled) returns. Weighted IS needs a weighted average. With returns $G_1,\dots,G_{n-1}$ and weights $W_k$ (e.g. $\rho$):

Exercise 5.10 derivation: $V_{n+1}=\frac{C_{n-1}V_n+W_nG_n}{C_n}=\frac{(C_n-W_n)V_n+W_nG_n}{C_n}=V_n+\frac{W_n}{C_n}(G_n-V_n)$. Note the step size here is $W_n/C_n$ — a data-dependent, decreasing step size.

Input: an arbitrary target policy π
Initialize, for all s ∈ S, a ∈ A(s):
    Q(s,a) ∈ ℝ (arbitrarily)
    C(s,a) ← 0
Loop forever (for each episode):
    b ← any policy with coverage of π
    Generate an episode following b: S₀, A₀, R₁, …, S_{T−1}, A_{T−1}, R_T
    G ← 0
    W ← 1
    Loop for each step of episode, t = T−1, T−2, …, 0, while W ≠ 0:
        G ← γG + R_{t+1}
        C(S_t,A_t) ← C(S_t,A_t) + W
        Q(S_t,A_t) ← Q(S_t,A_t) + (W / C(S_t,A_t)) [G − Q(S_t,A_t)]
        W ← W · π(A_t|S_t) / b(A_t|S_t)

5.7 Off-policy Monte Carlo control

Initialize, for all s ∈ S, a ∈ A(s):
    Q(s,a) ∈ ℝ (arbitrarily)
    C(s,a) ← 0
    π(s) ← argmax_a Q(s,a)                 (with ties broken consistently)
Loop forever (for each episode):
    b ← any soft policy
    Generate an episode using b: S₀, A₀, R₁, …, S_{T−1}, A_{T−1}, R_T
    G ← 0
    W ← 1
    Loop for each step of episode, t = T−1, T−2, …, 0:
        G ← γG + R_{t+1}
        C(S_t,A_t) ← C(S_t,A_t) + W
        Q(S_t,A_t) ← Q(S_t,A_t) + (W / C(S_t,A_t)) [G − Q(S_t,A_t)]
        π(S_t) ← argmax_a Q(S_t,a)         (with ties broken consistently)
        If A_t ≠ π(S_t) then exit inner Loop (proceed to next episode)
        W ← W · 1 / b(A_t|S_t)

5.8–5.9 *Discounting-aware and per-decision importance sampling

Discounting-aware IS: if γ < 1 and episodes are long, scaling $G_0$ by all 100 ratio factors is wasteful — with γ = 0, $G_0=R_1$ only needs $\pi(A_0|S_0)/b(A_0|S_0)$. Treat discounting as a probability of termination and decompose the return into flat partial returns $\bar G_{t:h}\doteq R_{t+1}+\dots+R_h$:

Each $\bar G_{t:h}$ is then scaled only by the truncated ratio $\rho_{t:h-1}$ (estimators 5.9 ordinary, 5.10 weighted). Identical to §5.5 when γ = 1.

Per-decision IS (works even with γ = 1): each reward $R_{t+k}$ only needs the ratios up to the action that produced it, because later factors have expected value 1: $\E\big[\tfrac{\pi(A_k|S_k)}{b(A_k|S_k)}\big]=\sum_a b(a|S_k)\tfrac{\pi(a|S_k)}{b(a|S_k)}=1$ (5.13).

$V(s)=\sum_{t\in\mathcal T(s)}\tilde G_t/|\mathcal T(s)|$ is unbiased (first-visit) with possibly lower variance. No consistent per-decision weighted version is known.

5.10 Summary — MC vs DP

Four advantages of MC over DP: (1) learn from actual interaction with no model; (2) work with simulation/sample models; (3) easy to focus on a small subset of states; (4) less harmed by violations of the Markov property.

Hyperparameters and design choices

Self-test

Chapter quiz — check your understanding

Scored quiz: pick an answer (or type a number) to get instant feedback and an explanation. Questions marked Exam-style give you values to interpret (sweeps, logs, returns, learning curves), the way exam problems do. Your best score is saved in this browser and shown on the home page. "Shuffle & restart" re-orders the questions.