Monte Carlo Methods

Dynamic programming solves a Markov decision process by leaning hard on the model: every update sweeps the dynamics $p(s^{\prime },r\mid s,a)$, expanding the exact expectation in the Bellman equation over all successors. Monte Carlo methods throw that model away. They require only experience — sampled sequences of states, actions, and rewards from actual or simulated interaction — and yet they can still estimate value functions and find optimal policies.¹ The trade is exact expectation for sampling: where DP computes ${\mathbb{E}}_{\pi }[G_t\mid S_t=s]$ from a known distribution, Monte Carlo averages the returns $G_t$ it actually observes.

The idea is the definition of a value function read literally. The value $v_{\pi }(s)$ is the expected return from $s$ under $\pi$. An expectation is a long-run average, so the most direct estimate imaginable is: follow $\pi$, and every time you pass through $s$, record the return that followed; the running average of those returns converges to $v_{\pi }(s)$. Nothing about the dynamics is needed — the environment supplies the samples, and the law of large numbers does the rest.

Because a return only makes sense once an episode has ended, we restrict Monte Carlo to episodic tasks: experience divides into episodes that terminate no matter what actions are chosen, and value estimates change only on the completion of an episode. Monte Carlo is thus incremental episode-by-episode, but not step-by-step.¹ Each state acts like a separate bandit problem — sample and average a signal — except the problems are coupled: the return after acting in one state depends on the actions taken in later states of the same episode, so as the policy changes underneath, each state's bandit is nonstationary.

Monte Carlo prediction

Fix a policy $\pi$ and suppose we want $v_{\pi }(s)$ from a batch of episodes generated by following $\pi$. Each occurrence of state $s$ in an episode is a visit to $s$. A single episode may visit $s$ several times; the first one is the first visit. Two estimators split on which visits to count:²

The two are close cousins but have slightly different theory. First-visit MC is the classic, studied since the 1940s: each first-visit return is an independent, identically distributed, unbiased estimate of $v_{\pi }(s)$ with finite variance, so by the law of large numbers the average converges, and the standard deviation of its error falls as $1/\sqrt{n}$ in the number of returns $n$. Every-visit MC is biased for finite $n$ (returns from repeated visits within one episode are correlated) but its bias also vanishes asymptotically, and it extends more naturally to function approximation and eligibility traces.²

The first-visit algorithm walks each episode backward, which lets it accumulate the return $G_t=R_{t+1}+\gamma G_{t+1}$ with one multiply-add per step.

Delete the unless $S_t$ appears earlier line and the same loop becomes every-visit MC: it records every step's return, first visit or not.

A worked averaging trace

For example, run the backward loop on one short episode. Take $\gamma =0.9$ and the observed trajectory

so state $A$ is visited twice (at $t=0$ and $t=2$). Running the loop from $t=3$ down to $0$ accumulates $G\leftarrow \gamma G+R_{t+1}$:

First-visit MC records the return only from the earliest occurrence of each state. State $A$'s first visit is $t=0$, so it contributes $G_0=9.09$; the later visit at $t=2$ with return $9$ is skipped. States $B$ and $C$ each occur once and contribute $10.1$ and $10$. Every-visit MC instead records both of $A$'s returns, so $A$ gets the two-sample average $(9.09+9)/2=9.045$ from this single episode. The two estimators already disagree after one episode; the gap is the within-episode correlation that makes every-visit MC biased for finite $n$. Now suppose a second episode gives a first-visit return of $7.5$ for $A$. The running first-visit estimate becomes $(9.09+7.5)/2=8.295$ — a plain average of independent samples, exactly the law-of-large-numbers estimator converging to $v_{\pi }(A)$.

The backup diagram: one trajectory, no bootstrap

The contrast with DP is sharpest in the backup diagram — the picture of which future outcomes an update draws on. A DP backup for $v_{\pi }$ roots at a state and branches over every one-step successor, weighting each by the model; it is one level deep and exhaustive. A Monte Carlo backup roots at a state and follows the single sampled trajectory all the way down to the terminal state; it is one path wide and full-episode deep.²

Two facts fall out of that picture. First, Monte Carlo does not bootstrap: the estimate for one state is built from realized returns, never from the current estimate of another state. DP's every update reuses neighbors' estimates; MC's uses none. Second, the estimates for different states are independent — the cost of estimating one state's value is independent of the number of states. If you care about the value of only a handful of states, you can generate episodes starting from just those states and average their returns, ignoring the rest of the state space entirely.² DP has no such option; it must sweep everything.

Blackjack

The casino game of blackjack makes a clean episodic MDP. The player draws cards to get a hand sum as close to 21 as possible without exceeding it; face cards count 10, and an ace counts 11 unless that would bust, in which case it counts 1 (a usable ace is one still counting as 11). The player hits (draws) or sticks (stops); busting loses. Each game is an episode with reward $+1$, $-1$, or $0$ for win, loss, or draw, all intermediate rewards zero and $\gamma =1$, so the terminal reward is the return. A state is the triple (current sum $12$–$21$, dealer's one showing card, usable ace or not) — 200 states in all.³

Take the policy stick on 20 or 21, otherwise hit. There is no easy way to apply DP here: you would need $p(s^{\prime },r\mid s,a)$ — for instance the probability of finishing with $+1$ given the dealer shows a 6 and you stick on 14 — and computing all those distributions in advance is delicate and error-prone. But simulating games is trivial. So we play many episodes under the policy and average the returns following each state. After 500,000 games the value function is well approximated; states with a usable ace stay noisier, because they arise less often.³ This is a real advantage even here, where the dynamics are technically known: Monte Carlo needs only a sample model — something that generates transitions — not the full distribution DP demands.

Estimating action values

Without a model, state values alone are not enough. With a model you can turn $v_{\pi }$ into a policy by a one-step lookahead — for each action, combine the reward and the successor's value, pick the best — but that lookahead needs the dynamics. Without them, $v_{\pi }(s)$ tells you how good a state is but not which action gets you somewhere good. So the primary target of Monte Carlo control is the action-value function $q_{\pi }(s,a)$: with $q$ in hand, the greedy policy is just $\arg {\max }_{a}q(s,a)$, no model required.⁴

Estimating $q_{\pi }$ is the same averaging, indexed by pairs. A state–action pair $(s,a)$ is visited in an episode if $s$ is visited and $a$ is taken there; first-visit MC averages returns following the first such visit in each episode, every-visit MC averages all of them. Both converge to $q_{\pi }(s,a)$ as visits to each pair go to infinity.

The complication is exploration. Many state–action pairs may never be visited at all. If $\pi$ is deterministic, then following it you observe returns for only one action per state — the one $\pi$ chooses — and the estimates for the other actions never improve. But comparing alternatives is the whole point of estimating action values: to improve a policy you must know the value of actions it does not currently take.

One way to force coverage is the assumption of exploring starts: episodes begin in a state–action pair chosen so that every pair has nonzero probability of being the start. Over infinitely many episodes every pair is then visited infinitely often.⁴

Exploring starts is a crutch. It works for simulated episodes but cannot be relied on in general. The two ways to drop it — keep the behaving policy stochastic everywhere (on-policy), or learn about one policy while behaving by another (off-policy) — organize the rest of the lesson.

Monte Carlo control

To find optimal policies, Monte Carlo slots evaluation into generalized policy iteration (GPI): maintain a policy and a value function, repeatedly push the value toward $q_{\pi }$ (evaluation) and repeatedly make the policy greedy in the current value (improvement). The two chase each other to a joint fixed point that is optimal.⁵ The classical version alternates complete evaluations and improvements,

where $\stackrel{\text{E}}{\to }$ is a full MC policy evaluation and $\stackrel{\text{I}}{\to }$ is greedy improvement. Improvement needs no model: for any action-value function $q$, the greedy policy is $\pi (s)\doteq \arg {\max }_{a}q(s,a)$. Why does going greedy in $q$ help? Because the greedy action is, by definition, the best-scoring action, so switching to it can only raise the value at that state — the same logic as in DP, now with $q$ instead of a one-step model lookahead. The policy improvement theorem applied to ${\pi }_{k+1}=\text{greedy}(q_{{\pi }_k})$ makes this precise:

so each ${\pi }_{k+1}$ is uniformly at least as good as ${\pi }_k$, and the process converges to ${\pi }_{\ast }$ and $q_{\ast }$ from sample episodes alone.⁵

Two unrealistic assumptions bought that clean guarantee: exploring starts, and infinitely many episodes per evaluation. The second is easy to relax. Rather than run each evaluation to convergence, we can evaluate toward $q_{{\pi }_k}$ without finishing — exactly the move value iteration makes for DP. For Monte Carlo the natural rhythm is episode-by-episode: after each episode, average the observed returns to update $Q$ at the visited pairs, then immediately make the policy greedy at those states. This gives Monte Carlo ES (Exploring Starts).⁵

Applied to blackjack — where exploring starts is trivial to arrange, since we simply deal random opening states and pick the first action at random — Monte Carlo ES recovers essentially the known optimal strategy. (That Monte Carlo ES converges at all is intuitively clear: a fixed point requires both policy and value to be mutually consistent, which happens only at the optimum. A formal proof remains one of the open theoretical questions in the field.)⁵

On-policy control with ε-soft policies

To drop exploring starts on-policy, we keep the behaving policy soft: every action retains some probability everywhere, $\pi (a\mid s)>0$ for all $s,a$, shifting only gradually toward determinism. The standard choice is $\epsilon$-greedy: with probability $1-\epsilon$ take the greedy action, and with probability $\epsilon$ pick uniformly at random among all actions.⁶ So every nongreedy action keeps probability $\epsilon /|\mathcal{A}(s)|$, and the greedy action gets the rest, $1-\epsilon +\epsilon /|\mathcal{A}(s)|$.

Now GPI cannot push the policy all the way to greedy — that would kill exploration. Instead, improvement moves the policy toward the $\epsilon$-greedy policy for the current $Q$. The policy improvement theorem still applies: any $\epsilon$-greedy policy with respect to $q_{\pi }$ is an improvement over any $\epsilon$-soft $\pi$.

The catch is that this converges only to the best policy among $\epsilon$-soft policies, not to the unconstrained optimum — the price of forcing perpetual exploration into the policy you actually follow. That residual suboptimality is what off-policy learning removes.

This continues in Monte Carlo Methods: Off-Policy Learning, which removes that ceiling: it learns about a greedy target policy from data generated by a soft behavior policy, using importance sampling to correct for the mismatch, and closes by placing Monte Carlo on the model/bootstrap map beside dynamic programming and temporal-difference learning.