What You'll Learn
- Estimate value functions by averaging complete returns from sampled episodes
- Distinguish first-visit from every-visit MC and state their bias properties
- Explain why model-free control needs Q-values and an exploration mechanism
- Implement ε-greedy Monte Carlo control on GridWorld
- Use importance sampling to learn about one policy from another’s episodes
Dynamic programming gave us exact value functions—but only because we handed it the full transition model . Now take blackjack: could you write down the probability of every next hand, for every action, from every configuration of cards? In principle, maybe. In practice, nobody does. What you can do is play. Deal a hand, follow your strategy, see how it ends. Then deal another.
Monte Carlo methods turn that into a learning algorithm: play complete episodes, record the returns you actually got, and average. No model, no equations to solve—just experience. In the demo below, an agent wanders a small random walk and estimates each state’s value purely by averaging returns. Watch the MC estimates converge toward the true values as episodes accumulate—and notice that they only move at the end of each episode. (The demo also shows a TD learner; that’s the subject of the next chapter, so keep your eyes on the Monte Carlo curve for now.)
TD(0) vs Monte Carlo Learning
Compare how TD and MC learn value estimates on the Random Walk problem.
- TD(0) updates after every step using bootstrap estimates (V(s) depends on V(s'))
- Monte Carlo waits until episode end to update, using actual returns
Where Monte Carlo Sits
Monte Carlo methods occupy a specific spot in the RL landscape, defined by three properties:
p(s’|s,a)—the environment itself does the sampling.Compare this with the dynamic programming methods you just saw:
Computes values from the model: sweep all states, apply Bellman backups over every possible transition.
Needs p(s’|s,a) for everything. Exact, but only as good as the model—and most real problems don’t come with one.
Estimates values from experience: run episodes, average the returns you observed.
Needs only the ability to interact. Noisy at first, converges with data. Can focus effort on states you actually visit.
One more difference matters in practice: DP updates every state on every sweep, whether or not it’s relevant. MC only spends effort on states that appear in real episodes. In a huge state space where your policy visits a tiny corner, that’s a feature, not a bug.
Methods that estimate value functions and improve policies by averaging complete sampled returns. The name comes from the casino: any estimation technique built on repeated random sampling is called a Monte Carlo method.
Chapter Overview
The chapter follows the same prediction-then-control arc as dynamic programming, then adds a third idea—learning about one policy from another’s data—that will echo through the rest of the book:
Monte Carlo Prediction
Estimate value functions by averaging returns: first-visit, every-visit, and the law of large numbers
Monte Carlo Control
From values to policies: exploring starts, ε-greedy control, and why Q beats V without a model
Off-Policy Monte Carlo
Behavior vs target policies and importance sampling—the vocabulary behind Q-learning
Throughout, we use the same 4×4 GridWorld from Value Functions: wall at (1,1), goal at (3,3), −1 per step, +10 for reaching the goal, . Because we solved that grid exactly with DP, we can check every Monte Carlo estimate against the true answer.
Monte Carlo’s one non-negotiable requirement: episodes must end. A blackjack hand ends, a maze run ends, a game of Go ends. A server that runs forever doesn’t—and for that you’ll need TD learning, which is exactly where this book goes next.
Summary & Check Your Understanding
Key Takeaways
V(s) is defined as the expected return from s. Monte Carlo estimates it the obvious way: run episodes, average the returns you observed. The law of large numbers does the rest.p(s’|s,a) and never builds estimates from other estimates. The price: updates wait until the episode ends, and the targets are noisy (unbiased, high variance).V requires a model to look one step ahead; being greedy with respect to Q is just an argmax. And since MC only learns about what it visits, ε-greedy exploration keeps every action’s estimate alive.Quick Quiz
V(s). What does MC need from the environment that DP doesn’t, and vice versa?Show answer
MC needs the ability to interact: it must generate complete episodes, so the environment (or a simulator) has to be runnable, and episodes must terminate. DP needs the full model: the transition probabilities p(s’|s,a) and rewards for every state-action pair, but it never runs a single episode. That’s the trade: MC swaps knowledge of the model for samples from it.
Show answer
First-visit MC uses only the return following the first occurrence of the state—one sample from this episode. Every-visit MC averages the returns following all three occurrences—three samples, but they overlap (they share future rewards), so they’re correlated. That correlation is why first-visit is unbiased while every-visit is slightly biased—though both converge to the true V(s) as episodes accumulate.
Q(s,a) instead of V(s)?Show answer
To act greedily using V, you must compute “which action leads to the best next state?”—which requires knowing where each action leads, i.e., the model. With Q, the greedy action is just argmax_a Q(s,a): a table lookup, no model required. Model-free control therefore estimates action values directly.
Show answer
When you need an unbiased estimate—for example, inside another estimator whose analysis assumes unbiasedness, or when averaging over many independent problems where errors cancel. Ordinary IS is unbiased at any sample size; weighted IS is biased in finite samples (its first estimate is just the observed return, regardless of the weight) but consistent, with much lower variance. In most practical settings weighted IS wins, which is why it’s the default recommendation.