Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 37 ยท Monte Carlo and Temporal Difference

Monte Carlo Prediction: Learning Values from Episodes

Learn Monte Carlo prediction: estimate value functions by averaging sampled returns, first-visit versus every-visit, incremental means, with a grid world and a blackjack simulator in Python.

Dynamic programming needed the model. Monte Carlo (MC) methods do not: they learn from experience, complete episodes of interaction, and need nothing but the ability to sample them. The idea is almost embarrassingly simple. The value of a state is the expected return that follows it, so run many episodes, record the returns that followed the state, and average them. This is what you did by hand in Policies and Value Functions; now we organize it into an algorithm that learns every state from the same episodes.

Key properties

  • Model-free. No p(s', r | s, a) needed, only sampled trajectories (from a real environment or a simulator).
  • Episode-based. Updates happen after an episode ends, so MC needs episodic tasks.
  • No bootstrapping. A value is estimated from actual returns, not from other estimated values. That makes MC unbiased, but its estimates are noisy because a return depends on many random steps.
  • Focused. You can estimate the value of just the states you care about; DP always needs all of them.

First-visit and every-visit

A state can occur several times in one episode. There are two ways to use the returns:

  • First-visit MC uses only the return following the first time s appears in the episode.
  • Every-visit MC uses the return following every occurrence.

Both converge to v_pi(s) as the number of episodes grows. First-visit gives independent, unbiased samples and is easier to analyze, so it is the textbook default. Each episode gives one sample per visited state.

flowchart TD
    A["generate an episode with policy pi"] --> B["walk backwards: G = r + gamma * G"]
    B --> C{"first visit of this state?"}
    C -->|"yes"| D["append G to Returns(s); V(s) = mean"]
    C -->|"no"| E["skip (first-visit)"]
    D --> A
    E --> A

Algorithm

  1. Initialize V(s) arbitrarily, Returns(s) empty.
  2. Generate an episode S0, A0, R1, ..., ST following pi.
  3. Set G = 0. For t = T-1 down to 0: G = gamma * G + R_{t+1}; if S_t does not appear earlier, record G and update V(S_t).

Walking backward uses the recursive return and computes every G_t in one pass, exactly like in Returns and Discounting. The incremental mean V <- V + (G - V) / n avoids storing lists.

Monte Carlo on the grid world

We run first-visit MC for the uniform random policy on the 4x4 grid and compare with the exact values obtained by the linear solve. Every sample is a whole episode, and one episode updates many states at once.

Python First-visit MC prediction on the grid world

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The error shrinks as episodes accumulate (roughly like 1 / sqrt(n), the usual law for averages). Compare the two printed tables: the learned values land close to the exact ones without ever touching a transition table.

A case with no model: blackjack

Blackjack is the classic MC example: the rules are easy to simulate but awkward to write as a transition table. The state is (player sum, dealer's showing card, usable ace). The player's policy is fixed: stick on 20 or 21, otherwise hit. We estimate its value by playing 40,000 hands. Rewards are +1 for a win, 0 for a draw, -1 for a loss, with an infinite deck (drawing with replacement). The dealer hits until reaching 17.

Python Evaluating a simple blackjack policy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see clearly negative values for sums of 12 to 18 (about -0.5 to -0.7 without a usable ace: this policy hits until 20 and often busts, and 18 loses because it must keep hitting), turning strongly positive at 20 and 21, where sticking wins most hands. Usable-ace states are rarer and noisier (a state never visited would print nan), a typical MC issue: states that are rarely visited are estimated poorly, which is why exploration matters in the next lesson.

Bias, variance and bootstrapping

MC estimates are unbiased (each return is a true sample of what follows), but each return sums many random rewards, so the variance is high and learning is slow for long episodes. Methods that bootstrap, like TD learning in TD(0) prediction, trade a little bias for much lower variance.

Common mistakes

  • Averaging returns that start before the state's first visit. The return must begin at the visit.
  • Applying MC to a task that never ends, or to a policy that loops forever (cap the episode length and treat it as truncation).
  • Using every-visit and first-visit statistics interchangeably in a comparison; they differ slightly for finite samples.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does Monte Carlo prediction average?

    The value is the expected return, so MC averages sampled returns following visits to each state.
  2. 2. Which statement about MC methods is true?

    MC uses real returns from finished episodes, so it needs no model and no bootstrapping.
  3. 3. What is the difference between first-visit and every-visit MC?

    Both converge to v_pi, but first-visit uses one independent sample per state per episode.
  4. 4. Why is MC variance high?

    Every random step contributes noise to the full return.

Summary

  • MC prediction estimates v_pi(s) by averaging the returns observed after visiting s, with no model.
  • Compute returns by walking each episode backwards; use first-visit (or every-visit) updates and an incremental mean.
  • It requires episodic tasks, is unbiased but high-variance, and does not bootstrap.
  • Rarely visited states get poor estimates, so control methods must make sure all states are explored.

Next: Monte Carlo Control