// the one-minute version
Monte Carlo (MC) methods learn from complete sampled episodes without knowing p(s′,r|s,a) and without bootstrapping. After termination, the observed return Gt is a target for V(St) or Q(St,At). First-visit MC uses the first occurrence per episode; every-visit uses each occurrence. For control, action values and persistent exploration are essential. On-policy MC uses an ε-soft policy for both data and improvement. Off-policy MC evaluates or improves a target policy using trajectories from a different behavior policy, correcting the mismatch with importance-sampling ratios. Ordinary importance sampling is unbiased but high variance; weighted importance sampling is biased initially but often far more stable.
Asha discovers the simulator's traffic model is wrong. Rather than trust it, she lets the robot complete safe deliveries and records every state, action, and reward. Only when a delivery ends can she see whether an early shortcut helped or merely moved delay elsewhere. Dynamic programming asked the model to average every possible future. Monte Carlo asks completed experience: “What return actually followed?” The answer is noisy, but it is real.
01 From expected backups to sampled returns
DP needs a distribution model and computes E[R+γV(S′)]. MC needs only episodes. For each visit to a state at time t, compute Gt from the rewards that followed and average these returns. By the law of large numbers, the average approaches vπ(s) when episodes are generated under π and visits continue.
MC does not bootstrap: Gt contains observed rewards through termination rather than another current value estimate. This removes bootstrap bias but requires waiting and usually increases variance.
02 First-visit and every-visit prediction
First-visit MC updates a state's value only from the return following its first occurrence in an episode. Every-visit MC updates from every occurrence. Both are consistent under standard episodic assumptions, but their samples are correlated differently.
For a delivery trajectory Dock→Aisle→Dock→Charge→Terminal, first-visit uses the return from the initial Dock only. Every-visit also uses the later Dock return. The latter supplies more updates but not independent evidence.
An incremental sample average uses α=1/N(s). A constant α tracks nonstationarity. The same “old plus step-size times error” structure from bandits returns, but the target is now a full multi-step return.
03 Blackjack and why MC fits naturally
The chapter's blackjack example has states defined by player sum, dealer showing card, and whether the player has a usable ace. Actions are hit or stick; terminal reward is +1, 0, or −1. The transition model is awkward to enumerate but episodes are cheap to sample.
Under a fixed policy—stick on 20 or 21, hit otherwise—first-visit MC estimates a value surface. A usable ace changes risk because it can count as 1 or 11. The learned surface exposes where the policy is strong or fragile without ever calculating card probabilities explicitly.
Fig 1 — Monte Carlo credit flows backward only after an episode terminates.
04 Why control needs action values
Without a model, V(s) cannot tell Asha which action leads to which successor distribution. Q(s,a) directly estimates return after a specified action, so greedy improvement is possible from experience alone.
Exploring starts assumes every state–action pair can begin an episode with nonzero probability. Then alternate MC evaluation of Q with greedy improvement. The assumption yields clean convergence intuition but is unrealistic when starts cannot be chosen.
The practical substitute is persistent stochastic exploration. An ε-soft policy assigns every action at least ε/|A(s)| probability. Evaluation estimates its action values; improvement moves probability toward greedy actions while retaining coverage.
05 On-policy Monte Carlo control
On-policy means the policy being improved also generates the episodes. After each episode, update Q for visited pairs, then make π ε-greedy with respect to Q. This is GPI with sampled complete returns.
The resulting policy is optimal among ε-soft policies, not necessarily among deterministic policies, because it must continue exploring. Annealing ε can become greedier, but convergence then depends on ensuring infinite exploration while greediness increases—often summarized as GLIE.
Asha constrains actions for safety first, then applies ε-soft exploration only within the allowed set. “On-policy” describes data-policy alignment; it does not supply operational safety.
06 Off-policy learning and importance sampling
Off-policy methods separate a target policy π, which is evaluated or improved, from a behavior policy b, which generates data. This lets Asha evaluate a new route policy from logs collected by an older, safer exploratory policy.
A trajectory is more or less likely under π than b. The importance-sampling ratio from t through T−1 is:
Multiplying Gt by ρ corrects expectations if coverage holds: whenever π can choose an action, b must give it nonzero probability. If one denominator is zero, the data cannot answer the target-policy question.
07 Ordinary, weighted, and incremental estimators
Ordinary importance sampling averages ρG. It is unbiased when assumptions hold, but even its variance can be infinite. Weighted importance sampling divides the weighted returns by the sum of weights. It is biased at finite sample sizes but consistent, bounded in the episodic-return range, and commonly lower variance.
Weighted estimates can be updated incrementally with cumulative weight C:
For deterministic greedy target policies, off-policy control can work backward through an episode. Once a behavior action differs from the greedy target action, earlier importance weights become zero and the backward loop stops.
08 Discounting-aware and per-decision corrections
The chapter's starred sections refine importance sampling. A discounted return can be interpreted as random termination, suggesting ratios need not always extend to the physical episode end. Per-decision importance sampling attaches correction only to the reward terms whose probability depends on the mismatched actions preceding them.
These derivations matter because they reveal where variance enters: correction should cover exactly the policy-dependent part of the target, not blindly multiply unrelated future factors. Later off-policy n-step and trace methods reuse this principle.
common catches & gotchas
- Calling MC “random search” — Monte Carlo means estimating expectations from samples; policy choice can be structured.
- Using MC on nonterminating episodes — Basic methods need complete returns. Truncate carefully or use continuing formulations.
- Improving V without a model — State values alone do not expose action consequences; learn Q for model-free control.
- Violating coverage — Logged data cannot evaluate target actions the behavior policy never selected.
- Trusting unbiasedness over variance — An unbiased estimator with enormous variance may need impractical data.
- Reusing exploratory training reward as evaluation — Evaluate the final target policy separately from the behavior policy that gathered data.
09 Questions master's students should answer
What exactly makes MC model-free?
The update uses observed returns and never queries transition probabilities or expected rewards. It still needs an environment or dataset that supplies complete episodes.
Why is MC unbiased but high variance?
A sampled complete return is an unbiased sample of expected return under the policy, but it contains every random transition and reward between the visit and termination.
First-visit or every-visit?
Both converge in common episodic settings. First-visit gives one return per state per episode; every-visit uses more correlated samples. Compare empirically and state the choice.
Why can weighted importance sampling be preferred if biased?
Its normalization prevents rare huge weights from dominating as violently. Finite-sample mean-squared error often matters more than asymptotic unbiasedness.
When should I avoid off-policy MC?
When episodes are long, target and behavior differ substantially, or coverage is weak. TD, n-step, model-based, or specialized offline methods may use data more effectively.
10 Key takeaways
- MC replaces model expectations with complete sampled returns and does not bootstrap.
- First-visit and every-visit methods estimate policy values by averaging returns after visits.
- Model-free control needs Q(s,a), exploration, and repeated evaluation/improvement.
- On-policy control improves the same ε-soft policy that generates its episodes.
- Off-policy learning separates behavior b from target π and requires coverage.
- Importance ratios correct distribution mismatch but products can cause extreme variance.
- Ordinary estimation is unbiased; weighted estimation trades finite-sample bias for stability.
prediction
control
correction
11 Wrapping up and source trail
Asha no longer trusts a complete model; complete deliveries are enough to learn. But waiting until termination wastes information available after every transition. Chapter 6, temporal-difference learning, combines MC's sampling with DP's bootstrapping so predictions can improve online before an episode ends.
These are independent companion notes written in original language. Primary references: the authors' book page, the author-hosted open-access draft, the MIT Press edition page, and the official contents.