Core idea. Monte Carlo reinforcement learning estimates value functions from complete sampled episodes instead of from a known transition model. The mathematical object being estimated is still a conditional expectation:
The difference from dynamic programming is not the target. The difference is the information available. Dynamic programming assumes the transition law \(P\) and reward model \(r\) are known. Monte Carlo methods assume that we can sample trajectories and average observed returns.
12.1 Learning goals
After reading this chapter, students should be able to:
define episodic tasks, stopping times, returns, and sampled episodes;
explain Monte Carlo prediction as estimation of a conditional expectation;
distinguish first-visit and every-visit Monte Carlo evaluation;
derive the incremental sample-mean update;
implement Monte Carlo prediction for state values and action values;
explain why Monte Carlo methods are model-free but usually require complete episodes;
describe Monte Carlo control with exploring starts and with \(\epsilon\)-greedy exploration;
explain on-policy and off-policy Monte Carlo learning;
derive ordinary and weighted importance sampling estimators;
compare Monte Carlo error, variance, and bias with dynamic programming and temporal-difference learning;
use AI tools responsibly to check algorithms, diagnose variance problems, and critique experimental design.
12.2 9.1 Why Monte Carlo methods enter reinforcement learning
In Chapters 5–8, we studied Bellman equations under the assumption that the model is known. For example, policy evaluation solves
This equation is exact, but it requires \(P_\pi\) and \(r_\pi\). In many applications, those quantities are unknown. A robot can try actions. A recommendation system can observe user responses. A tutoring system can observe student progress. But the full transition kernel is rarely available.
Monte Carlo methods replace exact expectation by empirical averaging. If we observe returns
\[
G_1(s),G_2(s),\ldots,G_n(s)
\]
from visits to state \(s\), then the Monte Carlo estimator is
This is the same statistical idea as estimating a population mean from samples. What makes reinforcement learning different is that the samples are generated by a policy interacting with a Markovian environment. Therefore the returns are random variables built from long trajectories, not independent one-step labels.
Monte Carlo RL should be read as conditional expectation estimation from dependent sequential data. The algorithmic update is simple averaging, but the mathematical interpretation depends on states, actions, stopping times, and policies.
12.3 9.2 Episodic tasks and returns
Monte Carlo methods are most natural for episodic problems. An episode begins at time \(0\) and ends at a random terminal time \(T\). The terminal time is a stopping time with respect to the observed history:
The finite terminal time makes \(G_t\) well-defined even when \(\gamma=1\). In continuing tasks, one usually requires \(0\leq\gamma<1\) or uses average-reward methods, which are treated later in Chapter 21.
For a fixed policy \(\pi\), the state-value and action-value functions are
These definitions are the same as in earlier chapters. Monte Carlo methods only change how the expectations are approximated.
12.3.1 Interactive: distribution of sampled returns
A value function is an expectation, but Monte Carlo methods observe individual random returns. The following Plotly figure shows a simple simulated return distribution and its sample average.
12.4 9.3 Monte Carlo prediction as conditional mean estimation
Suppose a policy \(\pi\) is fixed. The prediction problem is to estimate \(V^\pi\) or \(Q^\pi\) from episodes sampled under \(\pi\).
For a state \(s\), let
\[
\mathcal I_n(s)=\{i: \text{episode } i \text{ contains at least one visit to } s\}.
\]
For each selected episode \(i\), choose a return sample \(G_i(s)\) associated with a visit to \(s\). Then
Instead, it estimates the expectation defining \(V^\pi(s)\) directly.
12.4.1 First-visit and every-visit samples
There are two common ways to define the samples.
First-visit Monte Carlo. For each episode, use only the return following the first time state \(s\) appears. If
\[
\tau_i(s)=\min\{t:S_t^{(i)}=s\},
\]
then the sample is
\[
G_i(s)=G_{\tau_i(s)}^{(i)}.
\]
Every-visit Monte Carlo. Use the return following every visit to \(s\) in the episode. If state \(s\) appears at times \(t_1,t_2,\ldots,t_m\), then the samples are
First-visit Monte Carlo often has a cleaner statistical interpretation because there is at most one sample per episode for a given state. Every-visit Monte Carlo can use more data, but returns within the same episode are dependent.
12.4.2 Interactive: first-visit versus every-visit Monte Carlo
This figure compares the convergence behavior of first-visit and every-visit averages in a small episodic process.
12.5 9.4 Incremental averaging
Monte Carlo estimates are usually updated online. Suppose \(X_1,X_2,\ldots\) are observed returns for a fixed state or state-action pair. The sample average after \(n\) observations is
More generally, one may use a constant step size \(\alpha\), giving
\[
V(S_t)\leftarrow V(S_t)+\alpha(G_t-V(S_t)).
\]
The sample-average update is appropriate for a stationary target. The constant-step-size update is often used when the environment, policy, or data distribution changes over time.
12.5.1 Interactive: Monte Carlo sample mean convergence
The following Plotly figure shows the sample mean of noisy returns converging to the true expected return.
12.6 9.5 Python example: Monte Carlo prediction in a random-walk environment
Consider a small random-walk process with terminal states at the left and right ends. The nonterminal states are
\[
\{1,2,3,4,5\}.
\]
At each nonterminal state, the agent moves left or right with equal probability. Reaching the right terminal state gives reward \(1\); all other rewards are \(0\). With \(\gamma=1\), the value is the probability of eventually reaching the right terminal state.
import numpy as npimport pandas as pdrng = np.random.default_rng(7339)nonterminal_states = np.array([1, 2, 3, 4, 5])left_terminal =0right_terminal =6def generate_episode(start_state=3):"""Generate one random-walk episode. Return a list of (state, reward_after_action) pairs for nonterminal states. The reward attached to state s_t is R_{t+1}. """ s = start_state episode = []while s notin (left_terminal, right_terminal): step = rng.choice([-1, 1]) next_s = s + step reward =1.0if next_s == right_terminal else0.0 episode.append((s, reward)) s = next_sreturn episodedef returns_from_episode(episode, gamma=1.0): G =0.0 returns = []for s, r inreversed(episode): G = r + gamma * G returns.append((s, G)) returns.reverse()return returns# First-visit Monte Carlo predictionV = {s: 0.0for s in nonterminal_states}N = {s: 0for s in nonterminal_states}num_episodes =5000for _ inrange(num_episodes): episode = generate_episode(start_state=3) returns = returns_from_episode(episode, gamma=1.0) visited =set()for s, G in returns:if s notin visited: visited.add(s) N[s] +=1 V[s] += (G - V[s]) / N[s]true_values = {s: s /6for s in nonterminal_states}summary = pd.DataFrame({"state": nonterminal_states,"MC estimate": [V[s] for s in nonterminal_states],"true value": [true_values[s] for s in nonterminal_states],"visits": [N[s] for s in nonterminal_states]})summary
state
MC estimate
true value
visits
0
1
0.165094
0.166667
2968
1
2
0.335479
0.333333
3729
2
3
0.504400
0.500000
5000
3
4
0.669321
0.666667
3768
4
5
0.834547
0.833333
3022
The true value here is known because the process is a simple symmetric random walk. For general reinforcement learning problems, the true value is not known. The point of the example is to show how the estimator is built from complete returns.
12.7 9.6 Monte Carlo action-value prediction
For control, estimating \(V^\pi(s)\) is not enough. A policy chooses actions, so the agent needs to compare actions. The action-value function is
If every state-action pair is visited infinitely often, then the estimates can converge to the true action values under suitable conditions.
The phrase visited infinitely often is not a computational detail. It is a mathematical assumption about exploration. Without enough visits to an action, no sample-based method can estimate its value reliably.
12.8 9.7 Monte Carlo control with exploring starts
Monte Carlo control tries to improve the policy using the estimated action values. A conceptually clean version assumes exploring starts: every state-action pair has positive probability of being the initial pair of an episode.
The algorithm alternates between two operations:
generate an episode using the current policy;
update \(Q(s,a)\) using returns;
improve the policy greedily:
\[
\pi(s)\in\arg\max_a Q(s,a).
\]
This is a sample-based analogue of generalized policy iteration. Instead of exact evaluation, it uses Monte Carlo estimates. Instead of waiting for exact convergence, it continuously improves the policy as estimates change.
Monte Carlo control with exploring starts
Initialize \(Q(s,a)\) arbitrarily and initialize a policy \(\pi\).
For each episode:
choose an initial pair \((S_0,A_0)\) with positive probability for all pairs;
generate an episode following \(\pi\) after the start;
compute returns \(G_t\) backward from the episode;
for each first visit to \((S_t,A_t)\), update the average estimate of \(Q(S_t,A_t)\);
for each visited state \(s\), set \(\pi(s)\) to a greedy action with respect to \(Q(s,\cdot)\).
Exploring starts are mathematically convenient but often unrealistic. In most applications, the initial state distribution is not under the designer’s control, and the first action may not be freely randomized over all possibilities.
12.9 9.8 On-policy Monte Carlo control with epsilon-greedy policies
A more practical approach is to use an exploratory policy throughout learning. An \(\epsilon\)-greedy policy with respect to \(Q\) chooses a greedy action most of the time and a random action sometimes.
This policy is stochastic. It balances exploitation of the current best action with exploration of other actions.
A common theoretical condition is called GLIE, meaning greedy in the limit with infinite exploration. It requires that all state-action pairs continue to be visited infinitely often while the policy becomes greedy in the limit. Informally,
\[
\epsilon_t\to 0
\]
but not so quickly that exploration stops too early.
12.9.1 Interactive: epsilon-greedy exploration
The next Plotly figure shows how \(\epsilon\) changes action probabilities and how decay schedules affect exploration over time.
12.10 9.9 Python example: Monte Carlo action-value control in a tiny MDP
The following example uses a small episodic MDP. The agent begins in state \(0\). From each nonterminal state it chooses action \(0\) or \(1\). Rewards are stochastic, so Monte Carlo averaging is needed.
import numpy as npimport pandas as pdrng = np.random.default_rng(2026)states = [0, 1, 2]actions = [0, 1]terminal =3def step(s, a):"""Tiny stochastic episodic MDP."""if s ==0:if a ==0:return1, rng.normal(0.0, 0.2)return2, rng.normal(0.1, 0.2)if s ==1:if a ==0:return terminal, rng.normal(1.0, 0.2)return terminal, rng.normal(0.2, 0.2)if s ==2:if a ==0:return terminal, rng.normal(0.4, 0.2)return terminal, rng.normal(1.3, 0.2)return terminal, 0.0def epsilon_greedy_action(Q, s, epsilon):if rng.random() < epsilon:returnint(rng.choice(actions))returnint(np.argmax(Q[s]))def generate_episode(Q, epsilon): s =0 episode = []while s != terminal: a = epsilon_greedy_action(Q, s, epsilon) next_s, r = step(s, a) episode.append((s, a, r)) s = next_sreturn episodeQ = np.zeros((len(states), len(actions)))N = np.zeros_like(Q)gamma =1.0def update_first_visit_Q(episode, Q, N): G =0.0 visited =set()for t inreversed(range(len(episode))): s, a, r = episode[t] G = r + gamma * G pair = (s, a)if pair notin visited: visited.add(pair) N[s, a] +=1 Q[s, a] += (G - Q[s, a]) / N[s, a]for k inrange(5000): epsilon =max(0.05, 1.0/ np.sqrt(k +1)) episode = generate_episode(Q, epsilon) update_first_visit_Q(episode, Q, N)policy = {s: int(np.argmax(Q[s])) for s in states}q_table = pd.DataFrame(Q, columns=["action 0", "action 1"])q_table.insert(0, "state", states)print("Greedy policy:", policy)q_table
Greedy policy: {0: 1, 1: 0, 2: 1}
state
action 0
action 1
0
0
1.001152
1.377881
1
1
1.024678
0.176235
2
2
0.438143
1.298328
This example illustrates a common pattern. The algorithm never estimates the transition probabilities. It learns action values directly from experience.
12.11 9.10 Off-policy Monte Carlo prediction
So far, the data-generating policy and the policy being evaluated have been the same. This is called on-policy learning.
In off-policy learning, we distinguish two policies:
the target policy\(\pi\), whose value we want;
the behavior policy\(b\), which generates the data.
The central difficulty is distribution shift. Episodes generated by \(b\) are not distributed as episodes generated by \(\pi\). Importance sampling corrects this mismatch by reweighting returns.
For a trajectory segment from time \(t\) to time \(T-1\), define the importance ratio
This estimator is usually biased for finite \(n\), but it often has much lower variance and is consistent under standard assumptions.
12.11.3 Interactive: ordinary versus weighted importance sampling
The following Plotly figure shows why off-policy Monte Carlo can be unstable. Ordinary importance sampling may have large spikes when a few trajectories receive very large weights.
12.12 9.11 Variance and confidence intervals
For a fixed state \(s\), Monte Carlo prediction estimates a mean. If the sampled returns have variance
provided the central limit approximation is reasonable. In sequential data, this approximation should be treated carefully because samples from one long trajectory can be dependent.
12.13 9.12 Monte Carlo versus dynamic programming and TD learning
Monte Carlo methods differ from dynamic programming in one fundamental way: they do not require a model. They differ from temporal-difference methods in another fundamental way: they wait for complete returns.
Method
Uses model \(P,r\)?
Uses complete return?
Bootstraps?
Typical target
Dynamic programming
yes
no
yes
Bellman expectation or optimality equation
Monte Carlo
no
yes
no
empirical return average
Temporal difference
no
no
yes
one-step bootstrapped target
The Monte Carlo target is
\[
G_t.
\]
The TD(0) target, introduced in the next chapter, is
\[
R_{t+1}+\gamma V(S_{t+1}).
\]
Monte Carlo methods are unbiased for the return target but can have high variance. TD methods introduce bootstrapping bias but often have lower variance and can update before the episode ends.
Monte Carlo and TD learning estimate the same value function but use different statistical targets. Monte Carlo estimates a full conditional expectation directly. TD estimates a fixed point through local one-step consistency.
12.14 9.13 AI-assisted learning components
AI tools can be helpful in this chapter, especially for checking logic and debugging simulations. They should not replace mathematical verification.
AI prompt: distinguish estimator and estimand
Give an AI system the following question:
In first-visit Monte Carlo prediction, what is the estimand and what is the estimator? Explain the role of the return \(G_t\) and why averaging returns estimates a conditional expectation.
A strong answer should clearly identify \(V^\pi(s)\) as the estimand and \(\widehat V_n(s)\) as the estimator. It should also state the assumptions needed for consistency.
AI prompt: audit an off-policy experiment
Ask an AI system to review an off-policy Monte Carlo experiment and identify whether the support condition
\[
\pi(a\mid s)>0\implies b(a\mid s)>0
\]
is satisfied. Then ask it to explain what can go wrong if the condition fails.
AI prompt: debug return computation
Give an AI system a Python function that computes returns from an episode. Ask it to check whether the code correctly implements
\[
G_t=R_{t+1}+\gamma G_{t+1}.
\]
Then verify the response manually on a short episode with known rewards.
12.15 9.14 Common pitfalls
Confusing value with reward. The value \(V^\pi(s)\) is an expected sum of future rewards, not the immediate reward.
Averaging rewards instead of returns. Monte Carlo prediction averages \(G_t\), not just \(R_{t+1}\).
Ignoring repeated visits. First-visit and every-visit methods use different sampling conventions.
Stopping exploration too early. Monte Carlo control needs enough visits to state-action pairs.
Using off-policy data without support. Importance sampling cannot repair missing actions.
Treating all samples as independent. Returns from the same trajectory are often dependent.
Forgetting variance. A Monte Carlo estimate can be unbiased and still practically unreliable if its variance is large.
12.16 9.15 Summary
Monte Carlo methods are the first fully sample-based reinforcement learning methods in this book. They estimate value functions by averaging complete observed returns. The mathematical foundation is conditional expectation and the law of large numbers.
Monte Carlo control combines return averaging with policy improvement, usually through exploring starts or \(\epsilon\)-greedy exploration. Off-policy Monte Carlo uses importance sampling to correct distribution mismatch, but this may introduce high variance.
The next chapter introduces temporal-difference learning, which replaces the full return \(G_t\) with a one-step bootstrapped target. That change is one of the most important algorithmic ideas in reinforcement learning.
12.17 Exercises
12.17.1 Conceptual exercises
Explain why Monte Carlo prediction is model-free.
Explain why Monte Carlo methods are naturally suited to episodic tasks.
Compare first-visit and every-visit Monte Carlo prediction.
Explain why \(G_t\) is a random variable even when the policy is fixed.
Explain the difference between on-policy and off-policy Monte Carlo learning.
Why can ordinary importance sampling have high variance?
Explain why an unbiased estimator is not necessarily a useful estimator in finite samples.
under the assumption that \(b(a\mid s)>0\) whenever \(\pi(a\mid s)>0\).
Show that an \(\epsilon\)-greedy policy assigns positive probability to every action when \(\epsilon>0\).
12.17.3 Computational exercises
Implement first-visit and every-visit Monte Carlo prediction for the random-walk example.
Estimate the empirical standard error of the Monte Carlo value estimate for each state.
Modify the random-walk example so that \(\gamma=0.9\). Compare the estimated values with the undiscounted case.
Implement Monte Carlo action-value prediction for a fixed stochastic policy in a small MDP.
Implement Monte Carlo control with an \(\epsilon_t=1/\sqrt{t}\) exploration schedule.
Simulate ordinary and weighted importance sampling in a two-action bandit-style episodic problem.
Plot the distribution of returns for a selected state and explain why the variance is large or small.
12.17.4 AI-assisted exercises
Ask an AI system to generate pseudocode for first-visit Monte Carlo prediction. Then check whether it correctly handles repeated visits in an episode.
Ask an AI system to explain GLIE in plain language and then rewrite the explanation mathematically.
Give an AI system an incorrect return-computation function and ask it to identify the bug.
Ask an AI system to compare ordinary and weighted importance sampling. Then verify whether it correctly distinguishes finite-sample bias from consistency.
Ask an AI system to design a Monte Carlo experiment for a small gridworld. Critique whether the proposed experiment has enough exploration.
12.18 Notes for instructors
For MA Applied Math students, emphasize conditional expectation, stopping times, sample-average convergence, and the connection to generalized policy iteration. For MS Statistics students, emphasize estimation, variance, importance sampling, support conditions, and dependence among trajectory samples.
A good lecture sequence is:
start from \(V^\pi(s)=\mathbb E_\pi[G_t\mid S_t=s]\);
define first-visit and every-visit estimators;
derive the incremental mean update;
run the random-walk Python example;
introduce action values and Monte Carlo control;
close with off-policy learning and importance sampling variance.
Monte Carlo methods are conceptually simple but statistically rich. They provide an ideal bridge from exact dynamic programming to sample-based reinforcement learning.