Skip to content

5.1 — Monte Carlo Prediction

Chapter 5: Monte Carlo Methods · Book section: §5.1 Previous: 4.4 — Async DP, GPI & Efficiency · Next: 5.2 — MC Action Values & Exploring Starts

🌱 The Big Picture

Dynamic programming needed a perfect model of the environment. Monte Carlo (MC) methods need no model at all — they learn value functions purely from experience: actual (or simulated) sequences of states, actions, and rewards.

Core idea: the value of a state is the expected return from it — so just average the actual returns observed after visiting that state. As more returns are seen, the average converges to the true value. That's it!

MC methods here are for episodic tasks: returns are only known once an episode ends, so MC updates happen episode-by-episode (not step-by-step like TD will).

🧮 The algorithm: First-visit MC prediction

Goal: estimate \(v_\pi\) from episodes generated by following π.

Input: policy π
Initialize: V(s) arbitrary; Returns(s) = empty list, for all s

loop forever (for each episode):
    generate an episode following π:  S0, A0, R1, S1, A1, R2, ..., S_{T-1}, A_{T-1}, R_T
    G = 0
    for t = T−1, T−2, ..., 0:              # walk backwards through the episode
        G = γ·G + R_{t+1}                   # accumulate the return
        unless S_t appeared earlier in the episode:    # "first-visit" check
            append G to Returns(S_t)
            V(S_t) = average(Returns(S_t))

Two variants:

First-visit MC Every-visit MC
Averages returns following… only the first visit to \(s\) in each episode every visit to \(s\)
Bias Unbiased; each return is i.i.d. Slightly biased (visits within an episode are correlated) but still converges
Convergence \(V(s) \to v_\pi(s)\) as visits → ∞ (standard error falls as \(1/\sqrt{n}\)) also converges

Both work; first-visit is the more studied classic; every-visit extends more naturally to function approximation and eligibility traces.

🃏 Worked example: Blackjack (book Example 5.1)

Blackjack is a perfect MC showcase because writing down the full transition probabilities \(p(s',r|s,a)\) is a nightmare (what's the probability of a +1 reward as a function of the dealer's showing card? 🤯), but simulating games is trivial.

  • States (200 of them): player's current sum (12–21), dealer's showing card (A–10), do I hold a usable ace?
  • Actions: hit or stick. Reward: +1/−1/0 for win/lose/draw at episode end.
  • Policy evaluated: stick on 20 or 21, else hit.

Run MC over hundreds of thousands of simulated games → smooth value surfaces emerge showing exactly how good every situation is under that policy. With 500,000 episodes, the estimates are essentially exact.

💡 Lesson: the ability to generate sample episodes is a much weaker requirement than knowing full transition probabilities — and MC needs only the former. This is a huge practical advantage. (Same reason MC can estimate the value of a single interesting state in a huge game by simulating from it.)

⚖️ MC vs DP — three important differences

  1. No model needed. MC learns from experience; DP computes from probabilities.
  2. No bootstrapping. Each state's MC estimate is built from real returns — it does not depend on the value estimates of other states. (DP's estimates lean on each other.)
  3. Cost independent of state-space size. The cost of estimating one state's value doesn't depend on the total number of states! You can evaluate only the states you care about, e.g., states actually encountered, and ignore the rest. (Backup diagram: DP shows all one-step transitions; MC shows one complete episode to termination.)

🎯 Key Takeaways

  1. MC prediction = average actual returns after visiting a state; converges to \(v_\pi\).
  2. Works from sample episodes only — no transition probabilities, no model.
  3. First-visit vs every-visit: both converge; first-visit is the classic.
  4. MC does not bootstrap: estimates for each state are independent of other states' estimates.
  5. Updates available only at episode end (a weakness TD will fix in Ch. 6).

➡️ Next: 5.2 — MC Estimation of Action Values & Exploring Starts — without a model we need \(q\) values, not \(v\) values… and that creates an exploration problem.