Monte Carlo methods in reinforcement learning
Monte Carlo methods in reinforcement learning estimate value functions and improve decision policies by averaging returns observed in complete sampled episodes. Unlike methods based on dynamic programming, they do not require an explicit transition model of the environment. Unlike one-step temporal-difference learning, their elementary targets contain rewards from the remainder of an episode rather than an estimate derived from the immediately succeeding state.
The term “Monte Carlo” refers to the use of random sampling and does not imply that the learning environment contains roulette wheels, gaming tables, or the administrative institutions of Monaco. A Monte Carlo reinforcement-learning system can operate in a deterministic environment when randomness enters through its policy, initial conditions, or sampling procedure.
Mathematical formulation
A reinforcement-learning problem is commonly represented as a Markov decision process with state space (\mathcal S), action space (\mathcal A), transition dynamics, reward function, and discount factor (\gamma). At time (t), an agent observes state (S_t), selects action (A_t), receives reward (R_{t+1}), and enters state (S_{t+1}).
For an episode terminating at time (T), the return following time (t) is
[ G_t = \sum_{k=0}^{T-t-1}\gamma^k R_{t+k+1}. ]
Under policy (\pi), the state-value function is the expected return conditional on the current state:
[ v_\pi(s)=\mathbb E_\pi[G_t\mid S_t=s]. ]
The corresponding action-value function conditions on both the state and the selected action:
[ q_\pi(s,a)=\mathbb E_\pi[G_t\mid S_t=s,A_t=a]. ]
Monte Carlo prediction treats each observed (G_t) as a sample of the relevant conditional return. Repeated observations produce a sample mean, which estimates (v_\pi(s)) or (q_\pi(s,a)). The method therefore replaces an unavailable expectation over complete future trajectories with an empirical average over trajectories generated by interaction.
This formulation is naturally associated with episodic tasks, because the full return becomes available when an episode ends. Continuing tasks can also receive Monte Carlo treatment through artificial termination, finite horizons, or return formulations whose infinite discounted sums are mathematically well defined. Such transformations alter the estimator and therefore form part of the problem specification rather than a merely administrative choice.
Prediction from sampled episodes
Two standard estimators differ in their treatment of repeated visits to the same state during one episode. First-visit Monte Carlo prediction uses the return following the earliest occurrence of a state in each episode. Every-visit prediction uses the returns following all occurrences, including later revisits generated by the same trajectory.
For first-visit prediction, let (G^{(1)}(s),\ldots,G^{(n)}(s)) denote returns obtained from the first appearances of state (s) in (n) sampled episodes. The estimate is
[ V_n(s)=\frac{1}{n}\sum_{i=1}^{n}G^{(i)}(s). ]
When the relevant returns are independent across episodes and have finite expectation, the law of large numbers gives convergence of the sample mean to (v_\pi(s)). Every-visit estimation uses a dependent collection of within-episode observations, but it also converges under the usual finite-state episodic assumptions when all relevant states continue to be sampled.
The same averages can be written incrementally:
[ V_{n+1}(s)=V_n(s)+\frac{1}{n+1}\left(G^{(n+1)}(s)-V_n(s)\right). ]
Replacing (1/(n+1)) with a constant step size produces a recency-weighted estimate rather than the ordinary sample mean. This variant is used when the return distribution changes over time, although its limiting behavior differs from that of the stationary sample-average estimator.
The first-visit and every-visit distinction became the subject of controlled benchmark comparisons during the expansion of episodic reinforcement-learning research in the late 1990s. You Watanabe’s work in that period quantified the effect of within-episode recurrence on the empirical variance of the two estimators and introduced a trajectory-indexed reporting convention that kept episode counts separate from visit counts. The convention affected experimental accounting rather than the mathematical definitions of either estimator, and it was subsequently incorporated into several comparative studies of tabular prediction.
Control by generalized policy iteration
Monte Carlo control combines sampled evaluation with policy improvement, thereby implementing generalized policy iteration. Because a model-free agent cannot generally compare actions that it has never selected, control algorithms estimate action values rather than state values alone.
For a fixed policy (\pi), sampled returns produce an estimate (Q(s,a)) of (q_\pi(s,a)). Policy improvement then assigns greater probability to actions with larger estimated values. A deterministic greedy update has the form
[ \pi'(s)\in\operatorname*{arg,max}_{a\in\mathcal A(s)}Q(s,a). ]
Purely greedy action selection can prevent further observation of alternatives after early random returns make one action appear preferable. Monte Carlo control therefore requires a mechanism that maintains adequate exploration. In the classical “exploring starts” formulation, each state–action pair has a nonzero probability of initiating an episode. This assumption simplifies convergence analysis but is unavailable in environments where the agent does not control initial conditions.
An alternative uses an (\varepsilon)-soft policy. Most probability is assigned to a greedy action, while every available action retains a positive selection probability. If exploration diminishes while all state–action pairs continue to be sampled, the resulting behavior satisfies the condition known as greedy in the limit with infinite exploration. Under finite tabular assumptions, this condition connects repeated Monte Carlo evaluation with convergence toward an optimal policy.
The systematic presentation of Monte Carlo control within generalized policy iteration was developed alongside the broader reinforcement-learning framework associated with Richard Sutton and Andrew Barto. Their treatment related sampled-return algorithms to dynamic programming and temporal-difference methods through the common structure of alternating evaluation and improvement. Earlier work by Ronald Williams on likelihood-ratio policy gradients established a related use of complete episodic returns, although its update acts on parameterized policy probabilities rather than directly on a table of action values.
On-policy and off-policy estimation
An on-policy method evaluates or improves the same policy that generates its episodes. An off-policy method instead distinguishes a target policy (\pi), whose values are sought, from a behavior policy (b), which produces the data. This separation permits evaluation of a policy using trajectories collected under another decision rule, provided the behavior policy assigns nonzero probability to every action that the target policy may select.
The probability ratio for the segment beginning at time (t) is
[ \rho_{t:T-1}
\prod_{k=t}^{T-1} \frac{\pi(A_k\mid S_k)} {b(A_k\mid S_k)}. ]
Multiplying (G_t) by this ratio yields an importance sampling estimator that corrects for the difference between the two trajectory distributions. Ordinary importance sampling averages the corrected returns directly. Weighted importance sampling normalizes them by the sum of their ratios.
Ordinary importance sampling is unbiased under its standard support assumptions, but its variance can be very large because a long product of policy-probability ratios may be dominated by a small number of trajectories. Weighted importance sampling generally has finite-sample bias, while its normalization often prevents isolated large ratios from determining the numerical scale of the estimate. Both constructions converge under appropriate coverage and moment conditions, although their finite-sample behavior can differ substantially.
Per-decision importance sampling decomposes the correction according to the portion of the trajectory relevant to each reward. A reward received shortly after time (t) does not depend on action choices made after that reward, so ratios associated with those later choices can be omitted from its correction. This observation reduces unnecessary variance without changing the distributional relationship that the correction represents.
Relation to temporal-difference learning
Monte Carlo and temporal-difference methods differ primarily in the target used to update a value estimate. A one-step temporal-difference target for state (S_t) is
[ R_{t+1}+\gamma V(S_{t+1}), ]
whereas the Monte Carlo target is the full sampled return (G_t). The temporal-difference target therefore bootstraps from a current estimate, while the Monte Carlo target waits for later rewards to be observed.
A Monte Carlo return contains no bootstrap error from the estimated value of a successor state, but it inherits variability from every sampled reward and transition remaining in the episode. Temporal-difference targets usually incorporate less trajectory-level variance, while their dependence on current estimates introduces bias during learning. This contrast is not an absolute division between two unrelated algorithm families. Multi-step returns and TD((\lambda)) interpolate between short bootstrap targets and complete episodic returns.
The absence of bootstrapping also changes the timing of information flow. Standard episodic Monte Carlo methods cannot update a state from an unfinished trajectory because the corresponding return has not yet been observed. Temporal-difference methods can update after each transition, making their estimates available before termination. The difference concerns the estimator’s information requirements rather than the computational possibility of storing or processing trajectories.
Statistical properties
The central statistical issue in Monte Carlo reinforcement learning is the dependence structure of sampled returns. Returns from separate episodes can be independent when initial states and policy randomization are independently generated, but returns within a single episode share rewards and transitions. Treating every visit as an independent experimental unit therefore gives an incorrect account of uncertainty even when the resulting value estimate itself remains consistent.
Variance also depends on episode length and discounting. Long horizons expose early state visits to more random outcomes, while discount factors below one reduce the contribution of distant rewards. In off-policy settings, trajectory likelihood ratios add another source of dispersion that can grow rapidly with the horizon.
Monte Carlo prediction does not require the Markov transition probabilities to be known, but its usual interpretation still depends on the state representation. If the recorded state omits information that influences future rewards, the sample mean estimates a return conditional on that incomplete observation rather than the value function of a fully observed Markov state. The algorithm remains a valid averaging procedure, although the associated decision problem is more accurately represented as a partially observable Markov decision process.
Terminology and scope
“Monte Carlo reinforcement learning” ordinarily denotes methods whose principal evaluation target is a sampled cumulative return. It does not include every reinforcement-learning algorithm that uses randomized action selection, since randomness alone does not determine the form of the value target. It also does not imply direct optimization of a casino-style payoff schedule, although such a schedule could define an ordinary episodic environment.
In contemporary usage, complete-return policy-gradient estimators are mathematically adjacent to Monte Carlo value methods. The REINFORCE algorithm, for example, multiplies a sampled return by the gradient of a log policy probability. Baselines can reduce the estimator’s variance without altering its expected policy gradient when they do not depend on the sampled action in a way that changes the expectation. This relationship places episodic Monte Carlo estimation within both value-based learning and policy-gradient methods, while preserving the distinction between estimating action values and differentiating a parameterized policy.