Monte Carlo methods: Worked examples — AI-ML deep dive

This page is a drill floor. The parent note taught you the machinery: returns $G_{t}$ , first-visit vs every-visit averaging, and the incremental update. Here we push that machinery through every kind of input it can meet — every sign of reward, the degenerate one-step episode, the loop that revisits a state, the extreme discount factors $γ = 0$ and $γ = 1$ , and a real word problem.

Before we compute anything, four symbols we lean on, so nothing appears unearned.

Definition The symbols we track

$T$ = the terminal time step: the step at which the episode ends. Episodes in Monte Carlo must be finite, so $T$ is a real, reached number (e.g. if the agent takes 4 steps then stops, $T = 4$ ). All returns sum rewards only up to $T$ .
$G_{t}$ = the return from time $t$ : the running total of rewards from step $t$ up to the terminal step $T$ , each future reward shrunk by a factor of $γ$ per step. Think of it as "how the story ended, seen from where I was standing at time $t$ ."
$V (s)$ = our current estimate of the true value $v_{π} (s)$ : literally the running average of all the $G_{t}$ values we ever collected while sitting in state $s$ .
$N (s)$ = the visit counter: a plain integer that counts how many returns we have collected for state $s$ so far. It starts at $0$ . Each time we observe a new return $G$ for state $s$ , we first increment $N (s) \leftarrow N (s) + 1$ , and only then use it in the update. That "increment first" rule is what guarantees $N (s) \geq 1$ whenever we divide by it — so we never divide by zero.

Every example below does the same three-move dance: (1) compute a $G$ , (2) bump $N (s)$ up by one, (3) fold $G$ into the average using $\frac{1}{N ( s )}$ .

The scenario matrix

Every Monte Carlo estimate is a return folded into an average. The things that can change between problems are: the sign of rewards, the discount $γ$ , whether a state is revisited (first- vs every-visit), and whether the episode is degenerate (length 1) or long. The table below enumerates the case classes. Each worked example is tagged with the cell it covers, and after the examples we tick every cell off in a coverage checklist.

Cell	Case class	What is unusual	Example
A	Single-step / terminal-adjacent	$T - t = 1$ , only one reward in $G$	Ex 1
B	Multi-step, all rewards equal sign (negative)	step-cost accumulation	Ex 2
C	Discounting bites ( $0 < γ < 1$ )	geometric weighting matters	Ex 3
D	$γ = 0$ (myopic) vs $γ = 1$ (undiscounted) — the two extremes	limiting behaviour	Ex 4
E	State revisited in one episode	first-visit ≠ every-visit	Ex 5
F	Mixed-sign rewards (positive and negative)	cancellation inside $G$	Ex 6
G	Incremental average across episodes	the $\frac{1}{N}$ nudge over time	Ex 7
H	Real-world word problem	translate story → returns	Ex 8
I	Exam twist: $Q (s, a)$ control update & why not $V$	argmax with no model	Ex 9

Worked example Ex 1 — Cell A: the shortest possible episode

Statement. An agent is in state $S$ , takes one action, receives reward $R_{1} = + 5$ , and the episode terminates ( $T = 1$ ). Use $γ = 0.9$ . What return $G$ does $S$ get, and what is $V (S)$ after this single episode (starting from $V (S) = 0$ , $N (S) = 0$ )?

Forecast: Guess — does the $0.9$ do anything here?

Write the return sum. From the general formula with $t = 0$ , $T = 1$ , the top limit is $T - t - 1 = 0$ , so the sum has just the $k = 0$ term: $G = γ^{0} R_{1} = R_{1}$ . There is no $R_{2}$ because the episode ended.
- Why this step? $G$ is defined only over rewards that actually occur up to $T$ ; a terminal state contributes nothing further. We must not invent rewards past $T$ .
Evaluate. $G = 5$ . The discount $γ$ multiplies future rewards; there are none, so $γ$ is idle. Caution: do not multiply this single reward by $γ$ — the immediate reward $R_{t + 1}$ always sits at exponent $γ^{0} = 1$ . Discounting only starts at the second reward. If you ever see $γ R_{t + 1}$ , you have shifted the whole sum by one step and every answer will be wrong.
- Why this step? This is the degenerate limit that catches beginners — they discount the only reward there is. $γ^{0} = 1$ protects us.
Increment then update. First bump the counter: $N (S) \leftarrow 0 + 1 = 1$ . Now the nudge fraction is $\frac{1}{1} = 1$ : $V (S) \leftarrow 0 + 1 \cdot (5 - 0) = 5$ .
- Why this step? Incrementing before dividing is what makes $\frac{1}{N ( S )}$ well-defined on the very first sample; first sample = the whole average.

Verify: With one data point the mean equals that point: $mean {5} = 5$ . ✓ And $γ$ never touched an immediate reward — sanity holds.

Worked example Ex 2 — Cell B: many steps, all rewards negative (step cost)

Statement. A grid-world agent takes $- 1$ reward per step and reaches the goal in $4$ steps: rewards $- 1, - 1, - 1, - 1$ (so $T = 4$ ). Undiscounted ( $γ = 1$ ). Find $G_{0}$ (return from the start) and $G_{2}$ (return from the third state).

Forecast: Which is bigger (less negative), $G_{0}$ or $G_{2}$ ? Why?

Return from the start. With $t = 0$ , $T = 4$ , the top limit is $T - t - 1 = 3$ , so four rewards: $G_{0} = - 1 - 1 - 1 - 1 = - 4$ .
- Why this step? Every step costs the same and $γ = 1$ means no shrinking, so the return is just the count of remaining steps, negated.
Return from state at $t = 2$ . Top limit $T - t - 1 = 1$ , so only two rewards remain: $G_{2} = - 1 - 1 = - 2$ .
- Why this step? $G_{t}$ sums forward from $t$ . Later states have fewer costly steps left, so their return is less negative.
Check the recursion. $G_{0} = R_{1} + γ G_{1} = - 1 + G_{1}$ , and $G_{1} = - 1 + G_{2} = - 1 + (- 2) = - 3$ , so $G_{0} = - 1 + (- 3) = - 4$ .
- Why this step? Confirms the recursive form $G_{t} = R_{t + 1} + γ G_{t + 1}$ ties the individual returns together.

Verify: $G_{0} = - 4$ equals $- (steps to goal) = - 4$ . ✓ States nearer the goal have larger (less negative) returns — that is exactly why value increases toward the goal.

Worked example Ex 3 — Cell C: discounting actually changes the answer

Statement. Rewards along an episode from time $t$ are $R_{t + 1} = 2$ , $R_{t + 2} = 0$ , $R_{t + 3} = 10$ , then terminate. Discount $γ = 0.5$ . Find $G_{t}$ .

Forecast: The big reward ( $10$ ) is two steps away. Guess: will it dominate or be squashed?

Weight each reward by its power of $γ$ . Using $G_{t} = \sum_{k} γ^{k} R_{t + k + 1}$ : the first reward ( $k = 0$ ) gets $γ^{0} = 1$ , the second ( $k = 1$ ) gets $γ^{1} = 0.5$ , the third ( $k = 2$ ) gets $γ^{2} = 0.25$ .
- Why this step? Look at the figure: each reward bar is scaled by a shrinking factor. This is why we use a geometric weight — it encodes "reward now is worth more than reward later" with a single tunable knob $γ$ .
Multiply and add. $G_{t} = 1 \cdot 2 + 0.5 \cdot 0 + 0.25 \cdot 10 = 2 + 0 + 2.5 = 4.5$ .
- Why this step? This is the definition $\sum_{k} γ^{k} R_{t + k + 1}$ made concrete.
Interpret. The distant $10$ contributed only $2.5$ — squashed to a quarter. The red bar in the figure shows how much survived.
- Why this step? Shows discounting's meaning: a $γ = 0.5$ world is quite myopic.

Verify: Recompute with the recursion. $G_{t + 2} = 10$ ; $G_{t + 1} = 0 + 0.5 \cdot 10 = 5$ ; $G_{t} = 2 + 0.5 \cdot 5 = 4.5$ . ✓ Matches.

Worked example Ex 4 — Cell D: the two extreme discounts

$γ = 0$ and $γ = 1$ Statement. Same reward stream as Ex 3 ( $2, 0, 10$ ). Compute $G_{t}$ once with $γ = 0$ (myopic) and once with $γ = 1$ (undiscounted). Contrast.

Forecast: Predict both before reading.

Myopic case $γ = 0$ . Every power $γ^{k}$ for $k \geq 1$ is $0$ ; only $γ^{0} = 1$ survives. $G_{t} = 2 + 0 + 0 = 2$ .
- Why this step? $γ = 0$ literally means "I only care about the immediate reward." The agent is blind to the $10$ waiting two steps out. This is the lower limiting behaviour of the discount.
Far-sighted case $γ = 1$ . All powers equal $1$ ; nothing shrinks. $G_{t} = 2 + 0 + 10 = 12$ .
- Why this step? $γ = 1$ counts distant rewards at full value. This is the upper limit, valid only because the episode terminates (otherwise the sum could blow up).
Contrast. As $γ$ slides $0 \to 1$ , $G_{t}$ sweeps from $2$ (Ex 4a) through $4.5$ (Ex 3) to $12$ (Ex 4b).
- Why this step? Shows $γ$ is a dial between short-sighted and long-sighted valuation, and $G_{t}$ moves monotonically with it here (all rewards non-negative).

Verify: At $γ = 0$ : $G = R_{t + 1} = 2$ . ✓ At $γ = 1$ : $G = 2 + 0 + 10 = 12$ . ✓ Both bracket the $γ = 0.5$ answer $4.5$ . ✓

Worked example Ex 5 — Cell E: a revisited state, first-visit vs every-visit disagree

Statement. Episode: $S_{1} R = - 1 S_{2} R = - 1 S_{1} R = + 4 S_{T}$ (so $T = 3$ ). Undiscounted $γ = 1$ . State $S_{1}$ appears at $t = 0$ and $t = 2$ . Compute the first-visit and every-visit estimates of $V (S_{1})$ from this single episode.

Forecast: Will the two flavors give the same number here?

Return at the first $S_{1}$ (t=0). Rewards from $t = 0$ : $- 1, - 1, + 4$ . $G_{0} = - 1 - 1 + 4 = 2$ .
- Why this step? First-visit MC uses only this one, since it is $S_{1}$ 's first appearance in the episode. See the top red arrow in the figure covering all three rewards.
Return at the second $S_{1}$ (t=2). Rewards from $t = 2$ : only $+ 4$ . $G_{2} = 4$ .
- Why this step? From the second occurrence there is just one reward left — the shorter red arrow in the figure. Every-visit MC also collects this sample.
First-visit estimate. One return collected, so $N (S_{1}) = 1$ : $V (S_{1}) \leftarrow 0 + \frac{1}{1} (2 - 0) = 2$ .
Every-visit estimate. Two returns collected in this one episode. Fold them in order: bump $N (S_{1})$ to $1$ , $V \leftarrow 0 + \frac{1}{1} (2 - 0) = 2$ ; then bump $N (S_{1})$ to $2$ , $V \leftarrow 2 + \frac{1}{2} (4 - 2) = 3$ .
- Why this step? Every-visit treats each occurrence as a data point, so one episode yields two samples — and because we increment $N (S_{1})$ once per occurrence, the running average lands on the plain mean $\frac{2 + 4}{2} = 3$ . The two flavors give 2 vs 3, the case the parent's blackjack example could not show (there all returns were equal).

Verify: First-visit $= 2$ , every-visit $= \frac{2 + 4}{2} = 3$ . ✓ They disagree because the two returns $2 \neq = 4$ differ, exactly as predicted.

Worked example Ex 6 — Cell F: mixed-sign rewards cancel inside one return

Statement. From state $S$ : rewards $+ 10, - 3, - 3, - 3$ then terminate, $γ = 1$ . Compute $G$ , and note whether the sign of $G$ tells the whole story.

Forecast: Positive or negative return?

Sum with cancellation. $G = 10 - 3 - 3 - 3 = 1$ .
- Why this step? $G$ is a signed sum; a big early bonus can survive several small penalties. We must add signs carefully, not just count steps.
Sub-return check. From $t = 1$ onward: $- 3 - 3 - 3 = - 9$ . So $G_{0} = R_{1} + G_{1} = 10 + (- 9) = 1$ .
- Why this step? Shows the same recursion holds with mixed signs — nothing special about negatives.
Interpretation. $V (S)$ built from such returns can be small-positive even though most steps punish, because the up-front reward dominates.
- Why this step? Warns against reading value from step-count alone when rewards are mixed.

Verify: $10 - 9 = 1$ . ✓ Sign of $G$ is positive despite three negative rewards.

Worked example Ex 7 — Cell G: the incremental average across three episodes

Statement. State $S$ collects returns $G = 4$ , then $G = 10$ , then $G = - 2$ across three episodes. Apply the increment-then-update rule each time (start $V = 0$ , $N = 0$ ). Show every step and confirm the final $V$ equals the plain mean.

Forecast: Guess the final $V$ before computing.

Episode 1. Increment first: $N (S) \leftarrow 1$ , nudge $= \frac{1}{1}$ : $V \leftarrow 0 + 1 (4 - 0) = 4$ .
- Why this step? First sample sets the estimate outright, weight $1$ — and the increment guarantees no $\frac{1}{0}$ .
Episode 2. Increment: $N (S) \leftarrow 2$ , nudge $= \frac{1}{2}$ : $V \leftarrow 4 + \frac{1}{2} (10 - 4) = 4 + 3 = 7$ .
- Why this step? The new sample $10$ pulls the mean halfway from $4$ toward $10$ . Watch the red dot in the figure jump from $4$ to $7$ .
Episode 3. Increment: $N (S) \leftarrow 3$ , nudge $= \frac{1}{3}$ : $V \leftarrow 7 + \frac{1}{3} (- 2 - 7) = 7 - 3 = 4$ .
- Why this step? A negative sample drags the estimate back down; the shrinking $\frac{1}{3}$ weight means later samples move it less.

Verify: Plain mean $= \frac{4 + 10 - 2}{3} = \frac{12}{3} = 4$ . ✓ Incremental result $4$ matches the batch mean — the whole point of the identity.

Worked example Ex 8 — Cell H: real-world word problem (elevator dispatch)

Statement. An elevator controller earns reward $- 1$ for every 10 seconds a passenger waits and $+ 20$ when the passenger is delivered. One episode: passenger waits three 10-second blocks ( $- 1, - 1, - 1$ ) then is delivered ( $+ 20$ ), so $T = 4$ . With $γ = 0.9$ , compute the return $G_{0}$ from the moment the passenger appeared, and update $V ("passenger waiting")$ assuming three such observations already happened (so $N = 3$ before this one) with prior $V = 8$ .

Forecast: Will $γ = 0.9$ noticeably erode the $+ 20$ delivery reward?

Translate story to a reward stream. $R_{1} = - 1$ , $R_{2} = - 1$ , $R_{3} = - 1$ , $R_{4} = + 20$ .
- Why this step? MC is model-free — we just record what actually happened, no elevator physics needed.
Discounted return. Using $G_{0} = \sum_{k = 0}^{3} γ^{k} R_{k + 1}$ : $G_{0} = γ^{0} (- 1) + γ^{1} (- 1) + γ^{2} (- 1) + γ^{3} (20)$ .
- Compute: $- 1 + 0.9 (- 1) + 0.81 (- 1) + 0.729 (20) = - 1 - 0.9 - 0.81 + 14.58 = - 2.71 + 14.58 = 11.87$ .
- Why this step? The delivery reward is three steps out, weighted by $γ^{3} = 0.729$ , so $20$ becomes $14.58$ — eroded but still dominant.
Increment then update. Bump the counter: $N \leftarrow 3 + 1 = 4$ , nudge $= \frac{1}{4}$ : $V \leftarrow 8 + \frac{1}{4} (11.87 - 8) = 8 + \frac{1}{4} (3.87) = 8 + 0.9675 = 8.9675$ .
- Why this step? Fold the new experience into the running value estimate; the increment to $4$ makes this the fourth-visit average.

Verify: $γ^{3} = 0. 9^{3} = 0.729$ ; $0.729 \times 20 = 14.58$ ; $- 1 - 0.9 - 0.81 = - 2.71$ ; sum $= 11.87$ . ✓ Update: $8 + 3.87/4 = 8.9675$ . ✓

Worked example Ex 9 — Cell I: exam twist — why

$Q (s, a)$ , not $V (s)$ , for control Statement. In state $s$ two actions have Monte-Carlo estimates $Q (s, left) = - 4$ and $Q (s, right) = - 2$ . Under an $ε$ -greedy policy with $ε = 0.2$ and 2 actions, (a) which action is greedy, (b) what is the probability the policy actually takes the greedy action, and what probability does the other action get? (c) Explain why we could not answer this from $V (s)$ alone.

Forecast: Greedy prob — is it just $1 - ε = 0.8$ ?

(a) Greedy action = argmax of $Q$ . $max (- 4, - 2) = - 2$ , achieved by right.
- Why this step? Control needs to compare actions, and $Q (s, a)$ already stores the value of each action, so the best one is a plain argmax.
(b) $ε$ -greedy probability of the greedy action. With probability $1 - ε$ we take the greedy action; with probability $ε$ we pick uniformly at random among all $2$ actions, which also lands on the greedy action with chance $\frac{1}{2}$ .
- Greedy total $= (1 - ε) + ε \cdot \frac{1}{2} = 0.8 + 0.2 \cdot 0.5 = 0.8 + 0.1 = 0.9$ .
- The other (non-greedy) action gets only the random branch: $ε \cdot \frac{1}{2} = 0.2 \cdot 0.5 = 0.1$ .
- Why this step? The subtle exam point: the greedy action's total probability is not $0.8$ ; the random branch can re-select it, pushing it to $0.9$ .
(c) Why $Q$ and not $V$ ? $V (s)$ is a single number summarising the state — it cannot rank two actions. To improve a policy from $V$ you would need $π^{'} (s) = ar g max_{a} [r (s, a) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) V (s^{'})]$ , which requires the reward model $r$ and the transition model $P$ . MC is model-free: we have neither. With $Q (s, a)$ the improvement is just $π^{'} (s) = ar g max_{a} Q (s, a)$ — no model needed, because $Q$ already bakes in the expected future.
- Why this step? This is the whole reason MC control estimates $Q$ rather than $V$ .

Verify: Greedy prob $= 1 - ε + ε /2 = 0.9$ ; other action prob $= ε /2 = 0.1$ ; they sum to $1$ . ✓ And no transition model $P (s^{'} ∣ s, a)$ was ever needed — argmax over $Q$ sufficed.

Matrix check — every cell covered

We claimed the matrix enumerated every case class. Here is the tick-list tying each cell back to the example that filled it:

✓ Cell A (single-step) → Ex 1: one reward, $γ^{0} = 1$ , $V = 5$ .
✓ Cell B (all-negative multi-step) → Ex 2: step costs give $G_{0} = - 4$ .
✓ Cell C ( $0 < γ < 1$ bites) → Ex 3: distant $10$ squashed to $2.5$ , $G = 4.5$ .
✓ Cell D (extremes $γ = 0, 1$ ) → Ex 4: $G = 2$ vs $G = 12$ .
✓ Cell E (revisited state) → Ex 5: first-visit $2$ vs every-visit $3$ .
✓ Cell F (mixed signs) → Ex 6: $+ 10$ survives three $- 3$ 's, $G = 1$ .
✓ Cell G (incremental average) → Ex 7: $4 \to 7 \to 4$ equals batch mean $4$ .
✓ Cell H (word problem) → Ex 8: elevator, $G_{0} = 11.87$ , $V = 8.9675$ .
✓ Cell I (control, $Q$ not $V$ ) → Ex 9: greedy prob $0.9$ , model-free argmax.

Every row of the table above now has a worked, verified example — nothing left unshown.

Recall Quick self-test

How is $N (s)$ defined and when do we increment it? ::: It counts returns collected for state $s$ ; we increment it by one before computing $\frac{1}{N ( s )}$ , which keeps the division safe. In the return formula, what exponent multiplies the first reward $R_{t + 1}$ ? ::: $γ^{0} = 1$ — the immediate reward is never discounted; the sum index $k$ starts at $0$ . Return from a 3-step undiscounted episode with rewards $- 1, - 1, - 1$ ? ::: $G = - 3$ . With rewards $2, 0, 10$ and $γ = 0.5$ , what is $G_{t}$ ? ::: $2 + 0 + 0.25 \cdot 10 = 4.5$ . One episode has $S_{1}$ twice with returns $2$ and $4$ ; first-visit $V (S_{1})$ ? ::: $2$ (only the first). Every-visit? ::: $3$ . Under $ε$ -greedy with $ε = 0.2$ , 2 actions, probability of the greedy action? ::: $0.9$ . Why does control estimate $Q (s, a)$ rather than $V (s)$ ? ::: Because argmax over $Q$ improves the policy with no model, whereas improving from $V$ needs $P$ and $r$ .

Prerequisite backbone for all of the above: the state/return/policy vocabulary of 5.1-Markov-Decision-Processes, and the parent Monte Carlo methods note.