Monte Carlo Prediction

Recall that the value of state $s$ under policy $\pi$ is defined as the expected return starting from $s$ and following $\pi$ thereafter:

where $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$ is the Return — the discounted sum of future rewards from time $t$ to the end of the episode. Monte Carlo prediction estimates this expectation directly from data: run the policy $\pi$ to generate complete episodes, record the return that follows each visit to $s$, and average those returns. As more episodes are collected, this sample average converges to the true expectation by the law of large numbers — no model of the environment's transition or reward dynamics is ever consulted. This is fundamentally different from dynamic programming approaches to the same problem, which compute $v_\pi$ by solving the Bellman Equation using a known model $p(s', r \mid s, a)$. Monte Carlo prediction instead treats the environment as a black box that can only be sampled, one episode at a time. It is also different from bootstrapping methods, which we have not yet introduced, in that Monte Carlo never uses one value estimate to update another — it only uses actual, realized returns. This makes each Monte Carlo estimate for a given state independent of the estimates of all other states, a property that will matter later when comparing bias and variance against TD methods. Two bookkeeping conventions exist because a single episode may visit the same state multiple times (in problems with cycles). First-visit MC counts, for each episode, only the return following the first time $s$ is entered, and averages these across episodes. Every-visit MC counts the return following every occurrence of $s$ within an episode. Both converge to $v_\pi(s)$, but they have different statistical properties: first-visit returns from different episodes are independent and identically distributed samples of $G_t \mid S_t=s$, giving a classical unbiased estimator; every-visit returns within the same episode are correlated, so the every-visit estimator is only asymptotically unbiased, though in practice it usually has lower variance because it uses more data per episode.

The mechanism has three moving parts: a way to generate episodes under the policy being evaluated, a per-state return accumulator, and an averaging step. Concretely: 1. Generate an episode. Starting from some initial state, follow policy $\pi$ (which may be stochastic) until a terminal state is reached, recording the sequence $S_0, A_0, R_1, S_1, A_1, R_2, \ldots, S_{T-1}, A_{T-1}, R_T, S_T$. 2. Compute returns backward. Walk the episode from the end to the start, maintaining a running return $G \leftarrow R_{t+1} + \gamma G$. This computes all $G_t$ values in a single backward pass in $O(T)$ time instead of recomputing each sum from scratch. 3. Update the average for each visited state, either only on first visit or on every visit, using an incremental mean update so no growing list of past returns needs to be stored. Here is the full first-visit Monte Carlo prediction algorithm, followed by the small modification needed for every-visit. ``` Algorithm: First-Visit Monte Carlo Prediction Input: policy π to be evaluated, discount factor γ ∈ (0,1] Initialize: V(s) ← arbitrary, for all states s # value estimate N(s) ← 0, for all states s # visit counter Returns_sum(s) ← 0, for all states s # running sum of returns Repeat for each episode: Generate an episode following π: S0, A0, R1, S1, A1, R2, ..., S_{T-1}, A_{T-1}, R_T (terminal at time T) G ← 0 visited_in_this_episode ← empty set for t = T-1 downto 0: G ← γ G + R_{t+1} if S_t is NOT in visited_in_this_episode: add S_t to visited_in_this_episode N(S_t) ← N(S_t) + 1 Returns_sum(S_t) ← Returns_sum(S_t) + G V(S_t) ← Returns_sum(S_t) / N(S_t) Output: V ≈ v_π ``` ``` Algorithm: Every-Visit Monte Carlo Prediction (identical, but remove the "if S_t is NOT in visited_in_this_episode" guard — update N(S_t) and Returns_sum(S_t) on every occurrence of S_t in the episode) ``` An equivalent and more memory-friendly formulation avoids storing `Returns_sum` explicitly and instead uses the incremental sample-mean update: ``` N(S_t) ← N(S_t) + 1 V(S_t) ← V(S_t) + (1 / N(S_t)) (G - V(S_t)) ``` This is mathematically identical to recomputing the mean of all returns seen so far, but it only requires $O(1)$ extra memory per state rather than storing every past return. It also generalizes naturally to a constant step-size variant, `V(S_t) ← V(S_t) + α (G - V(S_t))`, which trades the guarantee of exact averaging for the ability to track a slowly changing (non-stationary) policy or environment — a preview of ideas used heavily in Monte Carlo control and TD learning.

Time complexity. Generating one episode of length $T$ under policy $\pi$ costs $O(T)$ environment steps (this cost is intrinsic to sampling, not to the algorithm). Computing all returns via the backward pass is $O(T)$, since each step does $O(1)$ work (`G ← γG + R`) and there are $T$ steps. Updating the value table with the incremental-mean formula is $O(1)$ per visited state, so first-visit MC costs $O(T)$ total per episode (each state contributes at most once), and every-visit MC also costs $O(T)$ total per episode (each of the $T$ time steps contributes exactly one update). Over $N$ episodes, total time is $O(N \bar{T})$ where $\bar{T}$ is average episode length — linear in the total amount of experience generated, which is optimal since every reward must be read at least once.

Space complexity. The algorithm needs one counter $N(s)$ and one value $V(s)$ per state, so space is $O(|\mathcal{S}|)$, independent of the number of episodes — this is the payoff of the incremental-mean update over naively storing every observed return. If the state space is continuous or function-approximated, this becomes $O(d)$ where $d$ is the number of parameters, but that extension belongs to later material.

Correctness argument. Fix a state $s$ that has nonzero probability of being visited under $\pi$. Under first-visit MC, each episode in which $s$ occurs contributes exactly one return sample $G^{(i)}$, and these samples across episodes $i = 1, 2, \ldots$ are independent and identically distributed draws from the conditional distribution of $G_t \mid S_t = s$ (independence follows because episodes are generated independently of one another, assuming the policy and environment are fixed and memoryless given the state). By definition,

The sample mean after $n$ visits is

By the strong law of large numbers, $V_n(s) \to v_\pi(s)$ almost surely as $n \to \infty$, provided the returns have finite variance (guaranteed when rewards are bounded and $\gamma < 1$, or when $\gamma = 1$ but the episode is guaranteed to terminate in finite expected time). Moreover $V_n(s)$ is an unbiased estimator of $v_\pi(s)$ for every finite $n$, since $\mathbb{E}[V_n(s)] = v_\pi(s)$ exactly — this is the classical unbiasedness of a sample mean of i.i.d. draws. For every-visit MC the argument is subtler: within a single episode, multiple returns following repeated visits to $s$ are not independent (they share tail rewards and later states). The estimator is therefore biased for small $n$, but it remains consistent: as the number of episodes grows, the bias vanishes and $V_n(s) \to v_\pi(s)$ almost surely, a result that follows from a law of large numbers for suitably mixing/martingale sequences rather than the plain i.i.d. case. In practice both estimators are used, and the every-visit version is often preferred with function approximation because it makes more efficient use of each episode's data.

Key tradeoff versus dynamic programming and TD. Monte Carlo prediction needs no model, unlike DP. It has zero bias (first-visit) because it never bootstraps off a possibly-wrong current estimate, unlike TD(0), which we build toward next. But it pays for this with two costs: it needs the episode to actually terminate before any update can happen, so it cannot be used in continuing (non-episodic) tasks without modification, and its variance can be large because a single return accumulates noise from an entire trajectory of random rewards and transitions, whereas TD updates use only one step of real reward plus a bootstrapped estimate.

Consider a tiny episodic gridworld-like problem simplified to a single Markov chain with states $\{A, B, C, \text{terminal}\}$, a fixed policy $\pi$ (deterministic transitions given here for concreteness), discount factor $\gamma = 1$, and the following three sampled episodes (state sequence with rewards received on each transition):

We compute first-visit MC estimates for $V(A)$, $V(B)$, $V(C)$.

Episode 1: sequence $A,B,A,C,\text{term}$ with rewards $2,1,0,3$. Backward pass ($\gamma=1$, so $G \leftarrow G + R$):

First-visit rule: A's first visit is at $t=0$ with $G=6$; the later revisit of A at $t=2$ (giving $G=3$) is ignored. B's only visit gives $G=4$. C's only visit gives $G=3$. Contributions from episode 1: $A \to 6$, $B \to 4$, $C \to 3$.

Episode 2: sequence $B, C, \text{term}$ with rewards $-1, 4$.

Contributions: $B \to 3$, $C \to 4$.

Episode 3: sequence $A, C, B, C, \text{term}$ with rewards $2,1,0,2$.

First-visit C is at $t=1$ with $G=3$ (the later occurrence at $t=3$, $G=2$, is discarded). B's only visit gives $G=2$. A's only visit gives $G=5$. Contributions: $A \to 5$, $B \to 2$, $C \to 3$.

Averaging across episodes (first-visit):

These are the first-visit Monte Carlo estimates after just three episodes. Note how episode 1 contributed only one A-sample (6, from the first visit) even though A was visited twice — this is exactly the first-visit rule in action. An every-visit version would additionally fold in the second A-return (3) from episode 1, giving $N(A)=3$ and $V(A) = (6+3+5)/3 = 4.67$ — noticeably different at this small sample size, illustrating why the two estimators can disagree substantially before convergence, even though both converge to the same $v_\pi(A)$ in the limit.

Monte Carlo estimation as a general numerical technique predates reinforcement learning by decades, but its formal integration into value-function estimation for sequential decision problems was crystallized in the reinforcement learning literature of the late 20th century, building on decades of work in stochastic approximation, statistics, and simulation.

Monte Carlo prediction is the conceptual seed for Monte Carlo control, where the same return-averaging idea is applied to action-value functions $q_\pi(s,a)$ and combined with policy improvement to learn optimal behavior directly from episodes — used historically in classic game-playing agents and still taught as the cleanest bridge from prediction to control. It is also the direct comparison point for temporal-difference learning: TD(0), which replaces the full-episode return with a one-step bootstrapped target, trading some bias for dramatically reduced variance and the ability to learn online without waiting for episode termination; understanding Monte Carlo prediction thoroughly is what makes the tradeoffs of TD learning legible. In applied systems, Monte Carlo estimation of value functions underlies Monte Carlo Tree Search (MCTS), the search technique behind AlphaGo and its successors, where rollouts to the end of a simulated game are averaged to estimate the value of a board position exactly as in Monte Carlo prediction. Return-averaging ideas also appear in off-policy evaluation for recommendation systems and clinical trial analysis, where historical logged episodes (user sessions, treatment courses) are used to estimate the value of a candidate policy before it is ever deployed, precisely because no accurate simulator of user behavior or patient physiology exists. Any setting where an agent or analyst has only logged trajectories, and not a model, is a natural home for Monte Carlo prediction or its variance-reduced cousins.

Ask the tutor: How does the bias–variance tradeoff between Monte Carlo prediction and TD(0) actually play out in a concrete multi-state example?