Monte Carlo methods: Visual walkthrough — AI-ML deep dive

This page rebuilds the heart of Monte Carlo methods from nothing. The parent note tells you to "average the returns." Here we watch, picture by picture, why that average lands exactly on the true value of a state — and how the incremental update falls out of simple arithmetic.

We assume you know only what a Markov Decision Process is: an agent sits in a state, takes an action, gets a reward (a number), and moves to a new state, until the game ends.

Step 1 — What is one episode, and what is a "return"?

WHAT. An episode is one complete game, played from a start state until the game ends (a "terminal" state). Along the way we collect a chain of rewards — one number after each move.

WHY. Monte Carlo refuses to guess about the future. It waits until the game is over, so every number it uses is a real, observed outcome — never an estimate of an estimate.

PICTURE. Look at the timeline. Circles are states $S_{0}, S_{1}, S_{2}, S_{3}$ . Between them, above each arrow, sits the reward $R$ you collected on that move. The last state $S_{3}$ is a square: the game ended there.

Step 2 — Why multiply future rewards by $γ$ ?

WHAT. We attach a shrinking weight to rewards that arrive later. The weight is powers of a number $γ$ (gamma) between $0$ and $1$ : $G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + \dots + γ^{T - t - 1} R_{T}$

WHY this tool and not plain addition? Two reasons. First, a reward far in the future is less certain — the world is random, so we trust it less. Second, if a game could run forever, a plain sum could blow up to infinity; multiplying by $γ^{k}$ (which shrinks toward $0$ ) keeps the total finite. The discount factor $γ$ is the dial that trades off "care about now" versus "care about later."

PICTURE. Each bar is one reward. The height of the faded bar shows how much of that reward actually counts after multiplying by its $γ$ power. Near rewards keep almost their full height; distant rewards are squashed.

Reading the exponents where they sit:

$γ^{0} = 1$ multiplies $R_{t + 1}$ — the very next reward counts fully.
$γ^{1}$ multiplies $R_{t + 2}$ — one step away, shrunk once.
$γ^{T - t - 1}$ multiplies $R_{T}$ — the terminal reward, shrunk the most.

Edge cases of $γ$ :

$γ = 0$ : only $R_{t + 1}$ survives (every later term is multiplied by $0$ ). The agent is "myopic" — cares only about the immediate reward.
$γ \to 1$ : nothing shrinks; the far future matters almost as much as now ("far-sighted").

Step 3 — The recursive shortcut (peeling one reward off the front)

WHAT. The return at time $t$ can be written using the return at the next step: $G_{t} = R_{t + 1} + γ G_{t + 1}$

WHY. We derive this because computing $G$ for every step from scratch wastes effort — this form lets us build all returns in one backward sweep (last step first). It also makes the algebra of the next steps clean.

PICTURE. Start from the full sum. Pull one $γ$ out of every term except the first; the whole leftover bracket is exactly the return that starts one step later.

$G_{t} = R_{t + 1} + = γ (R_{t + 2} + γ R_{t + 3} + \dots) = γ G_{t + 1} γ R_{t + 2} + γ^{2} R_{t + 3} + \dots$

$R_{t + 1}$ — kept as-is, the reward you get right now.
$γ G_{t + 1}$ — everything after, packaged as "next step's whole future, discounted once."

This is why in code we compute returns backwards: start with $G_{T} = 0$ , then $G_{t} = R_{t + 1} + γ G_{t + 1}$ .

Step 4 — One episode gives ONE noisy sample of the truth

WHAT. The true value of a state $s$ under a policy $π$ is the average return you'd get from $s$ if you replayed the game infinitely many times: $v_{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]$

Reading the symbols:

$v_{π} (s)$ — the "true worth" of state $s$ under policy $π$ . A single fixed number.
$E_{π} [\cdot]$ — "the expected value," i.e. the long-run average over all possible games generated by policy $π$ .
$G_{t} ∣ S_{t} = s$ — the return, given that at time $t$ we were sitting in state $s$ .

WHY we cannot just read $v_{π} (s)$ off one game. A single game is random. One return might be lucky and high, the next unlucky and low. Any one $G_{t}$ is a sample, not the truth.

PICTURE. Three different episodes all pass through the same state $s$ . Each hands us a different return (a red dot on the number line). The true value $v_{π} (s)$ (dashed line) sits somewhere among the scatter — no single dot is it.

Step 5 — Why the average of samples finds the truth

WHAT. Collect many returns from state $s$ — call them $G^{(1)}, G^{(2)}, \dots, G^{(n)}$ — and take their mean: $V (s) = \frac{1}{n} \sum_{i = 1}^{n} G^{(i)}$

WHY this exact tool — the sample mean? The law of large numbers guarantees that the average of independent samples of a random quantity converges to that quantity's expected value. Since each $G^{(i)}$ is a genuine sample of $G_{t} ∣ S_{t} = s$ , their average must slide toward $E_{π} [G_{t} ∣ S_{t} = s] = v_{π} (s)$ . That is the entire justification for Monte Carlo.

PICTURE. As we fold in more dots, the running average (yellow curve) wobbles a lot at first, then settles down onto the dashed true value. Early estimates are noisy; later ones are steady.

$n$ small → wild swings (each new dot moves the mean a lot).
$n$ large → each new dot barely nudges the mean; it has converged.

Step 6 — Turning the mean into an incremental update

WHAT. We want to update $V (s)$ after each new return without storing all past returns. Algebra turns the plain average into a one-line update: $V_{n} = V_{n - 1} + \frac{1}{n} (G^{(n)} - V_{n - 1})$

WHY. Storing every return forever is wasteful. This form keeps only two things: the current estimate $V (s)$ and the count $n$ . It's mathematically identical to recomputing the full mean.

PICTURE. The new return $G^{(n)}$ sits to one side of the old estimate. The gap $G^{(n)} - V_{n - 1}$ is the error. We step the estimate a fraction $\frac{1}{n}$ of the way across that gap.

The derivation, one factor at a time: $V_{n} = \frac{1}{n} \sum_{i = 1}^{n} G^{(i)} = \frac{1}{n} [old sum (n - 1) V_{n - 1} + G^{(n)}] = V_{n - 1} + \frac{1}{n} (G^{(n)} - V_{n - 1})$

$G^{(n)} - V_{n - 1}$ — the error: how surprised we are by the newest sample.
$\frac{1}{n}$ — the step size: shrinks as samples pile up, so old evidence isn't overturned by one new game.
Written generally as $V (s) \leftarrow V (s) + α (G - V (s))$ , where $α = 1/ n$ gives the true mean, and a fixed small $α$ tracks a changing target instead.

Step 7 — Edge case: what if a state appears twice in one episode?

WHAT. Sometimes one episode visits state $s$ more than once (e.g. you wander back to the same room). Two rules:

First-visit MC: use the return only from the first time $s$ appears.
Every-visit MC: use the return from every appearance.

WHY it matters. First-visit gives each episode one independent sample per state (cleaner to prove convergence). Every-visit squeezes more samples out of one episode but they're correlated. Both still converge to $v_{π} (s)$ .

PICTURE. The episode $S_{1} \to S_{2} \to S_{1} \to S_{3}$ . State $S_{1}$ is highlighted twice. First-visit keeps only the return from the earliest $S_{1}$ (green tick); every-visit keeps both (green + yellow).

Worked from the parent's chain, undiscounted ( $γ = 1$ ), reward $+ 1$ only on reaching $S_{3}$ :

First $S_{1}$ (step 0): $G_{0} = 0 + 0 + 1 = 1$
Second $S_{1}$ (step 2): $G_{2} = 1$
First-visit estimate for $S_{1}$ : $1$
Every-visit estimate for $S_{1}$ : $\frac{1 + 1}{2} = 1$

Here they agree; with different intermediate rewards they generally would not.

Step 8 — Degenerate cases you must never trip over

WHAT / WHY / PICTURE. A quick tour of the boundary situations, so no scenario surprises you.

A state never visited ( $n = 0$ ): its $V (s)$ stays at its initial value (often $0$ ). Monte Carlo can only learn about states it actually experiences.
An episode that never ends: MC is stuck — there is no $G_{t}$ until the game terminates. This is why MC is for episodic tasks only.
$γ = 0$ : every return collapses to $G_{t} = R_{t + 1}$ . The value is just the expected immediate reward.
First update, $n = 1$ : step size $α = 1/1 = 1$ , so $V \leftarrow V + 1 \cdot (G - V) = G$ . The very first estimate simply is the first observed return — exactly what a one-sample mean should be.

The one-picture summary

The full pipeline compressed: play a whole episode → read off the actual return $G$ from each state → average returns over many episodes → the average slides onto the true value $v_{π} (s)$ , one incremental step at a time.

Recall Feynman retelling — say it back in plain words

Suppose you want to know how good a certain chess position really is. You can't calculate it, and nobody will give you a rulebook of odds. So you just play. Every time a game passes through that position, you wait until the game finishes and write down your final score counted from that moment — that's the "return." Distant points count a little less because the future is fuzzy; that's the discount. One game tells you almost nothing — it might've been lucky. But play a hundred games, average all the returns you saw from that position, and the average stops jumping around and settles on the position's true worth. Instead of hoarding every score, you keep a running average: each new game nudges your estimate a fraction of the way toward the new score, and the nudges shrink as evidence piles up. If you happen to hit the same position twice in one game, you either count only the first time (first-visit) or both (every-visit) — both work. And if a game never ends, or you never see the position, you get nothing — Monte Carlo learns only from finished, lived-through experience.

Recall Self-check

What quantity does averaging returns converge to, and why? ::: The true state value $v_{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]$ , because by the law of large numbers the mean of independent samples of a random variable approaches its expected value. In the update $V \leftarrow V + α (G - V)$ , what is $G - V$ ? ::: The error — how much the newly observed return differs from the current estimate. Why must $γ < 1$ (or the task be episodic)? ::: To keep the total discounted return finite; otherwise an unending sum of rewards could diverge. On the first visit ever ( $n = 1$ ), what does $V (s)$ become? ::: Exactly the first observed return $G$ , since $α = 1/1 = 1$ .