Monte Carlo methods · reinforcement learning

Also known as: Monte Carlo reinforcement learning

On this page 7

Monte Carlo methods in reinforcement learning are a family of model-free algorithms that estimate value functions and improve policies by averaging the returns of complete episodes. Instead of relying on a model of the environment or on bootstrapped estimates, an agent following Monte Carlo reinforcement learning plays an episode to its end, computes the actual discounted return from each visited state or state-action pair, and uses those sample returns as unbiased estimates of value.

The name comes from the general Monte Carlo principle of approximating expectations with random samples. In this setting, the samples are trajectories of experience, and the methods apply to episodic tasks only, because a return can be computed only once an episode terminates. Not to be confused with Monte Carlo tree search, which is a planning method that uses simulated rollouts inside a search tree.

How Monte Carlo methods estimate value

Monte Carlo methods estimate the value of a state as the mean of the returns observed after visiting it. By the law of large numbers, this average converges to the true expected return under the policy that generated the episodes. The procedure for Monte Carlo prediction is straightforward.

  1. Generate a complete episode by following the current policy until a terminal state is reached.
  2. Working backward from the end, compute the return G as the reward plus the discount factor times the following return.
  3. For each visited state or state-action pair, add G to its list of returns and update the estimate as the running average.

The incremental form of the update moves the estimate a fraction of the way toward each new return: V(s) is replaced by V(s) plus a step size times the difference between G and V(s). A constant step size gives more weight to recent episodes, which helps in nonstationary problems where the policy keeps changing.

The two classic variants differ in how they treat repeated visits within one episode.

VariantWhich visits countStatistical property
First-visit Monte CarloOnly the first visit to a state per episodeUnbiased, independent samples
Every-visit Monte CarloEvery visit to a state in an episodeBiased but consistent, often lower variance
First-visit and every-visit Monte Carlo prediction

Monte Carlo control and exploration

Monte Carlo control finds a good policy by alternating evaluation and improvement in the pattern of generalized policy iteration. Because no environment model is available, the agent must estimate action values Q(s, a) rather than state values; a state value alone does not reveal which action leads to it without knowing the transition dynamics.

The central difficulty is maintaining exploration. If the policy becomes greedy too early, some actions are never tried and their values are never estimated. Three standard solutions address this problem, and they lead to the variants summarized below.

ApproachMechanismMain limitation
Exploring startsEvery episode begins from a random state-action pairRarely possible in real environments
On-policy epsilon-soft controlActs greedily except with probability epsilonConverges to the best epsilon-soft policy only
Off-policy controlLearns a greedy target policy from a behavior policyHigh variance from importance weights
Approaches to exploration in Monte Carlo control

In off-policy Monte Carlo, returns generated by an exploratory behavior policy are reweighted by the importance sampling ratio, the product of probability ratios between target and behavior policies along the trajectory. Ordinary importance sampling is unbiased but can have unbounded variance; weighted importance sampling introduces a small bias that vanishes over time and is usually preferred in practice.

Monte Carlo compared with temporal difference learning

Monte Carlo methods and temporal difference learning sit at opposite ends of a spectrum defined by how far an update looks ahead. Monte Carlo waits for the full return, whereas TD methods such as SARSA and Q-learning bootstrap from the current estimate of the next state after a single step.

PropertyMonte CarloTemporal differenceDynamic programming
Needs environment modelNoNoYes
BootstrapsNoYesYes
Update timingEnd of episodeEvery stepFull sweeps
Bias of targetUnbiasedBiased by current estimateExact given model
Variance of targetHighLowNone from sampling
Works in continuing tasksNoYesYes
Monte Carlo methods compared with neighboring approaches

The bias-variance trade-off is the decisive difference. Monte Carlo targets are unbiased but noisy, because each return sums many random rewards. Monte Carlo is also less sensitive to violations of the Markov property, since it never uses the value of a successor state. n-step returns and TD(lambda) with eligibility traces interpolate between the two extremes, and lambda equal to 1 recovers Monte Carlo behavior.

Where Monte Carlo returns appear in modern algorithms

Pure tabular Monte Carlo control is rare in production systems, but Monte Carlo return estimates remain central to many modern algorithms. The policy gradient method REINFORCE uses complete-episode returns to weight the log-probability gradient of each action, and it is often described as a Monte Carlo policy gradient.

  • REINFORCE multiplies each action gradient by the observed return, often minus a learned baseline to reduce variance.
  • Generalized advantage estimation with lambda near 1 approaches Monte Carlo advantage estimates.
  • Reward modeling for language models frequently scores complete generated sequences, which is a Monte Carlo signal.
  • Evaluation of trained policies commonly reports average episodic return from many rollouts.

Practical limitations and common mistakes

Monte Carlo methods are simple and robust, but several practical constraints limit where they work well. The table below lists typical problems, their causes and standard remedies.

SymptomCauseRemedy
Very slow learningHigh variance of long returnsUse baselines, more episodes or n-step TD
Method cannot be appliedTask has no terminal stateSwitch to TD or truncate episodes
Some actions never valuedPolicy became greedy too earlyKeep epsilon above zero or use off-policy learning
Exploding off-policy estimatesLong products of importance ratiosUse weighted importance sampling or per-decision ratios
Poor credit assignmentSingle return covers many actionsAdd reward shaping or advantage estimation
Typical problems with Monte Carlo methods and their remedies

A frequent conceptual mistake is to expect Monte Carlo updates to improve behavior during a long episode. Because learning happens only after termination, an agent in a task with episodes of thousands of steps receives feedback rarely, which makes sample efficiency a serious concern.

The short version

Monte Carlo methods teach an agent by letting it play a whole round and then look back at how it went. After each round, the agent notes the total reward it collected from every situation. It then keeps a running average.

Think of choosing a route home. You only know how good a route was after you arrive. You note the total travel time for each route you try. Over many evenings, the averages show which choices are best. The approach is honest and simple. However, it needs many complete rounds before the averages become reliable.

Where it makes a difference

A research group builds a simulated warehouse robot that must pick items from shelves within a fixed time limit of 200 steps per episode. Each episode ends when the robot finishes the order or runs out of time, which makes the task naturally episodic. The group uses on-policy Monte Carlo control with an epsilon of 0.1, a discount factor of 0.99 and a table of action values over a discretized grid of positions and loads.

After about 50,000 simulated episodes, the averaged returns identify routes that avoid congested aisles, and the average completion time falls noticeably compared with a hand-written rule. Because the Monte Carlo estimates do not depend on an imperfect model of aisle traffic, the learned policy transfers more reliably to a slightly different shelf layout, which the group then uses as a baseline for a faster temporal difference agent.