Monte Carlo Methods

Introduction and Context

Monte Carlo (MC) methods estimate reinforcement-learning quantities from complete episodes. Unlike dynamic-programming methods, which require a known transition model, MC methods learn directly from sampled experience. Unlike temporal-difference methods, which update after each transition, standard MC methods wait until an episode terminates and then use the observed return as a target.

This makes MC methods especially attractive when an environment is easy to sample but difficult to model. Applications include game playing, simulated robotics, recommendation systems, and operational decision-making. Their principal limitation is that they require episodic tasks: an observed return cannot be calculated until the relevant episode has ended.

The central objective is to estimate value functions and improve policies using sampled returns. This chapter develops first-visit and every-visit prediction, importance sampling for off-policy learning, and on-policy and off-policy control.

Learning Objectives

By the end of this chapter, you should be able to:

1. Define returns and explain how Monte Carlo estimates value functions.

2. Distinguish first-visit and every-visit MC prediction.

3. Use incremental averaging to update estimates efficiently.

4. Explain on-policy and off-policy learning.

5. Derive and apply ordinary and weighted importance sampling.

6. Construct MC control algorithms using policy improvement and exploring starts or soft behavior policies.

7. Evaluate the practical strengths, limitations, and governance implications of MC reinforcement learning.

Episodic Returns and Value Estimation

Consider an episodic Markov decision process (MDP) with states S, actions A, reward R, discount factor gamma (0 <= gamma <= 1), and terminal time T. If a state or state-action pair is visited at time t, its return is

G_t = R_(t+1) + gamma R_(t+2) + gamma^2 R_(t+3) + ... + gamma^(T-t-1) R_T.

Equivalently,

G_t = sum from k=t+1 to T of gamma^(k-t-1) R_k.

Here, G_t is the discounted cumulative reward from time t until termination. If gamma = 1, the return is undiscounted, provided the episode terminates and the sum is finite. Discounting is useful when immediate rewards matter more than distant rewards or when infinite-horizon problems are approximated by finite episodes.

For a policy pi, the state-value function is

v_pi(s) = E_pi[G_t | S_t = s],

and the action-value function is

q_pi(s,a) = E_pi[G_t | S_t = s, A_t = a].

The expectation is over trajectories generated by following pi. MC prediction estimates these expectations by sample averages. If observed returns following visits to state s are G_1, G_2, ..., G_N, then

V_N(s) = (1/N) sum from i=1 to N of G_i.

Under standard sampling conditions, the sample mean converges to v_pi(s) as N increases. This is a statistical estimate, not an exact value; its reliability depends on the number and variability of returns.

First-Visit and Every-Visit Prediction

First-visit MC prediction includes only the first occurrence of a state in each episode. Every-visit MC prediction includes every occurrence. For first-visit prediction, if state s first occurs at time t in an episode, the algorithm adds G_t once. For every-visit prediction, it adds G_t for each time t at which S_t = s.

Both approaches estimate the same policy value under appropriate conditions. The observations within an episode are not necessarily independent, so finite-sample behavior differs. First-visit estimates often have simpler statistical interpretation, whereas every-visit methods use more data and can be computationally efficient. Neither is universally superior.

Prediction Algorithm

A generic MC prediction procedure is:

1. Initialize V(s) arbitrarily and initialize an empty return list for each state.

2. Generate an episode using policy pi.

3. For each relevant visit to state s, calculate the return G_t.

4. Append G_t to the return list for s.

5. Set V(s) to the average of the stored returns.

6. Repeat over many episodes.

The first-visit version processes only the first visit to each state. The every-visit version processes all visits. In implementation, storing all returns is unnecessary; incremental averaging is preferable.

If V_n(s) is the mean after n returns and the next return is G, then

V_(n+1)(s) = V_n(s) + (1/(n+1))[G - V_n(s)].

The term G - V_n(s) is the prediction error, and 1/(n+1) is the exact step size for a sample mean. This update is numerically stable and requires only a count and the current estimate.

Worked Example: MC Prediction

Suppose a state s is observed in three episodes. Under an undiscounted setting, the returns are 4, 0, and 2. The first-visit estimate is

V(s) = (4 + 0 + 2)/3 = 2.

Using incremental updates:

• Initially V_0(s) = 0.
• After return 4: V_1(s) = 0 + 1(4 - 0) = 4.
• After return 0: V_2(s) = 4 + (1/2)(0 - 4) = 2.
• After return 2: V_3(s) = 2 + (1/3)(2 - 2) = 2.

Now suppose a single episode visits s twice, with returns 5 and 3. First-visit MC contributes only 5 from that episode. Every-visit MC contributes both 5 and 3. The distinction concerns which samples are included, not how each return is calculated.

MC Estimation and Statistical Considerations

MC estimates are unbiased for the expected return when the sampled episodes are generated under the policy being evaluated and the sample-selection procedure is correctly specified. “Unbiased” does not mean that an estimate equals the true value in a small sample. High-variance returns can produce substantial temporary errors.

The variance of returns is influenced by reward variability, episode length, discounting, and policy stochasticity. Discounting generally reduces the influence of distant rewards, but it does not automatically eliminate high variance. Longer episodes also increase computation and delay updates.

A useful engineering practice is to monitor confidence intervals or repeated-run variability rather than relying on a single estimate. In safety-critical applications, optimistic point estimates should not be treated as guarantees of performance.

On-Policy and Off-Policy Learning

On-policy learning evaluates or improves the same policy that generates data. If the target policy is pi, episodes are generated using pi. This is conceptually simple but can be inefficient: a policy being evaluated may not explore enough actions.

Off-policy learning separates two policies:

• The target policy pi is the policy whose value or quality is estimated.
• The behavior policy b generates the data.

Off-policy learning is useful when historical data, a safe exploratory controller, or an existing operational policy supplies the episodes. It also supports learning about a greedy target policy while behavior remains exploratory.

For off-policy estimation, every action selected by pi must have positive probability under b whenever the target policy may select it. This is the coverage, or absolute-continuity, condition:

pi(a|s) > 0 implies b(a|s) > 0.

Without coverage, a target trajectory may require actions absent from the data, making its value unidentifiable from those samples.

Importance Sampling

Suppose a trajectory segment from time t onward is generated by b, but we want to estimate the return distribution under pi. The likelihood ratio for the segment is

rho_(t:T-1) = product from k=t to T-1 of [pi(A_k|S_k) / b(A_k|S_k)].

The ratio reweights behavior-policy trajectories so that, in expectation, they represent target-policy trajectories. For a target policy that is deterministic, pi(A_k|S_k) is either 0 or 1. Any trajectory containing an action different from the target action receives weight zero.

Ordinary Importance Sampling

For state s, suppose N sampled returns G_i have weights rho_i. Ordinary importance sampling estimates the target value as

V_ordinary(s) = (1/N) sum from i=1 to N of rho_i G_i.

Under coverage and appropriate integrability conditions, this estimator is unbiased. However, its variance can be very large, particularly for long episodes or when behavior and target policies differ substantially. Products of many ratios can become extremely large or zero.

Weighted Importance Sampling

Weighted importance sampling normalizes by the total weight:

V_weighted(s) = [sum from i=1 to N of rho_i G_i] / [sum from i=1 to N of rho_i],

provided the denominator is nonzero. It is generally biased for finite samples but consistent under standard conditions, and it often has lower variance than ordinary importance sampling.

The distinction is important: ordinary importance sampling preserves unbiasedness under its assumptions, while weighted importance sampling trades finite-sample bias for variance reduction. Neither method is automatically best; selection depends on the risk of variance, sample size, and the application.

Worked Example: Importance Sampling

Two episodes provide returns 6 and 2 for a state. Their trajectory weights under the target policy are 0.5 and 1.5.

Ordinary estimate:

(0.5 x 6 + 1.5 x 2)/2 = (3 + 3)/2 = 3.

Weighted estimate:

(0.5 x 6 + 1.5 x 2)/(0.5 + 1.5) = 6/2 = 3.

The estimates happen to agree in this example. If the returns were 6 and 4, ordinary sampling would give (3 + 6)/2 = 4.5, whereas weighted sampling would give 9/2 = 4.5 again. Agreement is not guaranteed in general; it occurs here because the weighted average is also 4.5. For returns 6 and 0, ordinary sampling gives 1.5, while weighted sampling gives 3/2 = 1.5. In general, differences emerge when the average weight is not one.

Monte Carlo Control

Prediction estimates values for a fixed policy. Control seeks an improved policy. The central policy-improvement principle is to choose actions with the greatest estimated action value:

pi_new(s) in argmax over a of Q(s,a).

If Q accurately represents q_pi and all actions are considered, a greedy policy is at least as good as pi under the policy-improvement theorem. In finite problems, repeated evaluation and improvement can approach an optimal policy.

On-Policy MC Control with Exploring Starts

Exploring starts assume that every state-action pair can be the starting pair of an episode with nonzero probability. Episodes then follow the current policy. After returns are collected, Q(s,a) is updated and the policy is made greedy with respect to Q.

The procedure is:

1. Initialize Q(s,a) and a policy pi.

2. Generate an episode whose initial state-action pair is sufficiently exploratory.

3. For each first visit to a state-action pair, calculate G_t.

4. Update Q(s,a) by averaging observed returns.

5. Set pi(s) to an action maximizing Q(s,a).

6. Repeat.

Exploring starts are theoretically convenient but often unrealistic. A deployed system may not be able to force arbitrary initial state-action pairs.

On-Policy Control with Soft Policies

An alternative is to maintain exploration throughout learning. An epsilon-greedy policy chooses a maximizing action with probability 1 - epsilon and distributes epsilon among actions. For m actions, one common rule assigns

1 - epsilon + epsilon/m

to a maximizing action and epsilon/m to each nonmaximizing action, with adjustments when there are multiple maximizers.

Because every action has positive probability when epsilon > 0, the behavior policy explores and can support off-policy comparisons. In an on-policy algorithm, the same epsilon-greedy policy generates episodes and is improved gradually. A decaying epsilon may shift from exploration toward exploitation, but it must not decay so quickly that potentially useful actions are never adequately sampled.

Off-Policy MC Control

Off-policy MC control commonly uses an exploratory behavior policy b and a greedy target policy pi. After an episode is generated, returns are processed backward. Q-values are updated using importance sampling, and the target policy is made greedy with respect to Q.

A practical backward scheme maintains a cumulative weight C(s,a). For each relevant state-action pair:

C(s,a) <- C(s,a) + W

Q(s,a) <- Q(s,a) + [W/C(s,a)] [G - Q(s,a)]

where W is the cumulative importance ratio for the suffix being processed. After updating, the target policy selects an action maximizing Q. If the observed action is not greedy under the target policy, earlier updates may receive zero weight because a deterministic target policy assigns probability zero to that action. This is one reason off-policy MC control can discard much of an episode.

A Detailed Applied Case: Inventory Replenishment

Background

Consider a retailer that must decide each day how much inventory to order. Demand is uncertain, shortages cause lost sales, and holding excess stock creates storage cost. The retailer has historical records generated by an existing ordering policy.

Problem

Management wants to evaluate and improve a new ordering policy without immediately deploying it. The data are episodic: an episode is one selling season. A reward may combine sales margin, holding cost, ordering cost, and shortage penalties. Because the historical policy differs from the proposed policy, direct averaging of historical returns does not estimate the proposed policy’s value.

Analysis

The historical policy is the behavior policy b, and the proposed policy is the target policy pi. For each season, the analyst identifies the sequence of observed states, orders, and rewards. MC returns summarize the season’s consequences. Importance ratios reweight seasons according to how likely their actions would have been under pi.

The coverage condition must be checked. If the historical system always orders zero in a particular state, a target policy that orders ten units in that state cannot be evaluated from these records. The organization must collect additional exploratory data or restrict the target policy to supported actions.

Approach and Solution

First, use first-visit or every-visit MC prediction to estimate the value of the historical policy. Next, use weighted importance sampling to estimate candidate policies, reporting effective sample size and sensitivity to extreme weights. For control, an exploratory ordering policy can generate additional simulated or real episodes, while Q-values are updated from complete seasons. The target ordering policy is improved only when estimates are sufficiently reliable and operational constraints are satisfied.

Outcome

A policy that appears profitable under a few heavily weighted seasons should not be deployed automatically. The retailer should compare average return, shortage frequency, inventory risk, and worst-case performance. A conservative policy may be selected if the cost of stockouts or customer harm is high.

Learning Points

1. MC methods naturally handle delayed seasonal consequences.

2. Off-policy evaluation depends critically on behavior-policy coverage.

3. Variance and data quality matter as much as the point estimate.

4. Business constraints must be incorporated into the action set or policy-selection process.

5. Safe deployment requires monitoring after learning, not merely a high estimated return.

Strengths, Limitations, and Best Practices

MC methods are model-free, conceptually direct, and free from bootstrapping bias: the target is an observed return rather than an estimate based on another value estimate. They can learn from complete trajectories and are useful when delayed outcomes are central.

Their limitations include delayed learning, high variance, episodic-task requirements, and potentially expensive storage or simulation. Off-policy methods add sensitivity to distribution mismatch and extreme importance weights. First-visit and every-visit observations within an episode may also be statistically dependent.

Recommended practices include:

• Define termination and reward conventions precisely.
• Verify discount-factor units and the timing of rewards.
• Track visit counts and return variability, not only point estimates.
• Check action coverage before off-policy evaluation.
• Monitor importance-weight distributions and effective sample size.
• Use clipping or normalized methods cautiously, documenting the bias introduced.
• Separate training, validation, and test episodes.
• Compare learned policies with baselines and safety constraints.
• Use reproducible seeds, logged policies, and versioned data.
• Avoid deploying a policy solely because its estimated mean return is high.

Ethical, Governance, and Professional Considerations

A reinforcement-learning policy can amplify biases in historical data. If behavior data reflect unequal service, discriminatory decisions, or selective access, off-policy learning may reproduce those patterns. Governance should therefore include data provenance, subgroup performance analysis, and documentation of unsupported actions.

In domains such as healthcare, finance, employment, and public services, exploration can impose real costs or risks. Exploration should be constrained, approved, and monitored. Human oversight, rollback procedures, audit logs, and explicit accountability are essential. Estimates should communicate uncertainty and coverage limitations to decision-makers rather than presenting model output as certainty.

Contemporary Developments

Modern MC practice often combines complete-return learning with deep function approximation, replay datasets, simulation, and offline reinforcement learning. These combinations introduce additional challenges: neural networks can extrapolate poorly outside the data distribution, and importance ratios may become unstable in long trajectories. Practical systems therefore use conservative policy improvement, behavior regularization, uncertainty estimation, and extensive offline evaluation. The fundamental MC concepts—returns, coverage, averaging, and policy improvement—remain the basis for understanding these advanced systems.

Chapter Summary

Monte Carlo methods estimate value functions from complete sampled returns rather than from a known model or one-step bootstrapped targets. The return is the discounted reward sequence from a visit until episode termination. First-visit MC uses the first occurrence of a state or state-action pair in each episode; every-visit MC uses all occurrences. Incremental averaging provides an efficient exact sample-mean update.

On-policy methods learn about the policy generating data. Off-policy methods distinguish a target policy from a behavior policy and require coverage. Importance sampling corrects distribution mismatch using trajectory likelihood ratios. Ordinary importance sampling is unbiased under suitable conditions but may have high variance; weighted importance sampling often reduces variance while introducing finite-sample bias.

MC control alternates evaluation and policy improvement. Exploring starts provide theoretical exploration, while epsilon-greedy and other soft policies provide practical exploration. Successful professional use requires attention to episode design, variance, data coverage, uncertainty, safety, ethics, and governance.

Key Terms

Return: Discounted cumulative reward from a time step until episode termination.

Episodic task: A task consisting of finite trajectories ending in terminal states.

Monte Carlo prediction: Estimation of value functions from sampled complete returns.

First-visit MC: A method using only the first visit to a state or state-action pair in each episode.

Every-visit MC: A method using every visit to a state or state-action pair in each episode.

Incremental mean: A sequential update that maintains a sample average without storing all samples.

State-value function: Expected return from a state under a specified policy.

Action-value function: Expected return after taking an action in a state and then following a policy.

On-policy learning: Learning about the policy used to generate experience.

Off-policy learning: Learning about a target policy using data from another behavior policy.

Behavior policy: Policy that generates observed episodes.

Target policy: Policy whose value or performance is being estimated or optimized.

Importance sampling: Reweighting samples using likelihood ratios to correct policy mismatch.

Ordinary importance sampling: Importance sampling using the arithmetic mean of weighted returns.

Weighted importance sampling: Normalized importance sampling using total weights as the denominator.

Coverage: Requirement that every target action with positive probability has positive behavior-policy probability.

Exploring starts: Assumption that every state-action pair can begin an episode with nonzero probability.

Epsilon-greedy policy: Policy that mostly chooses a highest-valued action but explores with probability epsilon.

Policy improvement: Replacing a policy with one that selects actions according to estimated action values.

Variance: Statistical dispersion of estimates or sampled returns around their mean.

Review Questions

Short Answer Questions

1. What is the defining difference between Monte Carlo and temporal-difference learning?

2. How do first-visit and every-visit MC prediction differ?

3. What is the purpose of the behavior policy in off-policy learning?

4. State the coverage condition required for importance sampling.

5. Why can importance-sampling ratios have high variance?

Long Answer Questions

1. Explain how MC prediction estimates a state-value function, including the role of complete episodes and incremental averaging.

2. Compare ordinary and weighted importance sampling in terms of bias, variance, and practical use.

3. Describe an on-policy MC control algorithm using an epsilon-greedy policy.

4. Explain exploring starts and discuss why they may be unrealistic in deployed systems.

5. Discuss the strengths, limitations, and governance requirements of MC methods in real applications.

Analytical / Application Questions

1. An episode visits state s twice and produces returns 8 and 2. Explain which return first-visit MC uses and which returns every-visit MC uses. Discuss why their estimates may differ after few episodes.

2. A behavior policy assigns probability 0.25 to an observed action, while the target policy assigns probability 0.5. Calculate the one-step importance ratio and explain its interpretation.

3. A company wants to evaluate a target policy using logs from a behavior policy that never selected one action in a particular state. Determine whether ordinary importance sampling can reliably evaluate a target policy that selects that action, and justify your answer.

Multiple Choice Questions with Answers

Question 1

What does a Monte Carlo return represent?

A. The immediate reward only

B. The discounted rewards from a time step until episode termination

C. The maximum possible reward in an MDP

D. The difference between two value estimates

Correct Answer: B. The discounted rewards from a time step until episode termination

Question 2

Which visits are included by first-visit Monte Carlo prediction?

A. Only the last visit in each episode

B. Every visit across all episodes

C. The first visit to a state in each episode

D. Only visits with positive rewards

Correct Answer: C. The first visit to a state in each episode

Question 3

What is the incremental update for a sample mean after observing return G?

A. V <- V + n(G - V)

B. V <- V + (1/n)(G - V)

C. V <- G/n

D. V <- V - (1/n)(G + V)

Correct Answer: B. V <- V + (1/n)(G - V)

Question 4

In off-policy learning, which policy generates the data?

A. The target policy

B. The greedy policy only

C. The behavior policy

D. The optimal policy

Correct Answer: C. The behavior policy

Question 5

What condition is required for importance sampling coverage?

A. b(a|s) = 0 whenever pi(a|s) > 0

B. b(a|s) > 0 whenever pi(a|s) > 0

C. The two policies must be identical

D. The target policy must be deterministic

Correct Answer: B. b(a|s) > 0 whenever pi(a|s) > 0

Question 6

Which statement about ordinary importance sampling is generally correct?

A. It is unbiased under suitable conditions but can have high variance

B. It always has lower variance than weighted sampling

C. It requires no behavior policy

D. It can be used without policy coverage

Correct Answer: A. It is unbiased under suitable conditions but can have high variance

Question 7

How does weighted importance sampling differ from ordinary importance sampling?

A. It ignores trajectory probabilities

B. It normalizes by the sum of importance weights

C. It uses only negative rewards

D. It requires a known transition model

Correct Answer: B. It normalizes by the sum of importance weights

Question 8

What is the main purpose of an epsilon-greedy policy?

A. To eliminate all exploration

B. To guarantee exact value estimates

C. To balance exploitation and exploration

D. To make every action equally likely

Correct Answer: C. To balance exploitation and exploration

Question 9

If the discount factor is gamma = 1 in a finite episodic task, what return is used?

A. Only the first reward

B. The undiscounted sum of rewards until termination

C. Zero for every episode

D. Only the terminal reward

Correct Answer: B. The undiscounted sum of rewards until termination

Question 10

Why are exploring starts useful in theoretical MC control?

A. They ensure every state-action pair can be sampled as an initial pair

B. They remove the need for rewards

C. They make all policies identical

D. They prevent policy improvement

Correct Answer: A. They ensure every state-action pair can be sampled as an initial pair