9 · Monte Carlo prediction
Dynamic programming needed the model (P and R). Monte Carlo throws that away: estimate V(s) by just averaging the actual returns observed after visiting s across many sampled episodes.
Monte Carlo prediction estimates V(s) = E[G_t | s] by sampling whole episodes and averaging the actual returns that followed each visit to s. No transition model P, no reward function R — just experience.
Without this:
Without a model-free method you can only evaluate policies when you already know P and R — useless for the real RL setting where the agent must learn purely from what it experiences.
In Chapter 3 we evaluated and improved policies with dynamic programming, but that required the full model: the transition probabilities P(s'|s,a) and rewards R(s,a). In the real RL setting the agent does not know P and R — it can only sample the environment by calling step() and seeing what comes back. This chapter is model-free prediction: estimating the value function V^π(s) from experience alone.
The first idea is beautifully direct. Recall the definition of value:
V^π(s) = E[ G_t | S_t = s ]
— the expected return when you start in state s and follow policy π. An expectation is just an average over many samples. So Monte Carlo (MC) prediction does exactly that: it runs many complete episodes, and for every state visited it records the actual return G_t that followed. The estimate of V(s) is simply the average of those returns.
The recipe:
- Run an episode to termination under π, recording the sequence of (state, reward).
- Walk backwards through the episode accumulating the discounted return
Gat each step (G = r + γ·G). - For each visited state, append
Gto that state's list of observed returns. - Repeat for many episodes;
V(s)= mean of the returns collected fors.
This is first-visit MC if you only count the first time s appears in an episode, or every-visit if you count every occurrence. Both converge to V^π as the number of episodes grows, by the law of large numbers. Crucially: MC never touches P or R — it learns straight from sampled trajectories.
Python (in browser)
First-visit Monte Carlo: run episodes, accumulate returns backwards, average per state. The estimate matches the analytic V(s)=s/6 with no knowledge of the model.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Storing every return and re-averaging is wasteful. A standard trick rewrites the average as an incremental update. If V(s) is the current mean of n returns and a new return G arrives, the new mean is:
V(s) ← V(s) + (1/n) · ( G − V(s) )
This is the prototype of every learning rule in RL: old estimate + step-size × (target − old estimate). The term (G − V(s)) is the error, and 1/n is the step size. If we replace 1/n with a small constant α, we get a running average that gently forgets old episodes — useful when the policy or environment is changing, and the exact form temporal-difference learning will use next lesson.
Python (in browser)
Incremental MC: V(s) ← V(s) + (1/n)(G − V(s)). The estimate of the centre state converges toward its true value 0.5 as episodes accumulate.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Why is Monte Carlo prediction called 'model-free'?
- Monte Carlo prediction estimates V^π(s) = E[G_t|s] by averaging the actual returns observed after visiting s across many sampled episodes — no model needed.
- Compute returns by walking each episode backwards: G = r + γ·G; first-visit counts s once per episode, every-visit counts each occurrence; both converge to V^π.
- The incremental form V(s) ← V(s) + step·(G − V(s)) — old estimate + step-size × error — is the template for every RL learning rule.
Monte Carlo return estimates underlie REINFORCE and policy-gradient methods, and the 'average the sampled returns' idea reappears in every model-free value estimator.
If you remove it: Without model-free prediction you could only evaluate policies when P and R are known, which is almost never the case in real environments.