Monte Carlo methods: Exercises — AI-ML deep dive

Before we start, three reminders the whole page rests on.

(1) The return $G_{t}$ — the total discounted reward from time $t$ until the episode ends at time $T$ :

$G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + \dots + γ^{T - t - 1} R_{T}$

Here $R_{t + 1}$ is the reward you receive just after being at time $t$ , $γ$ (the discount factor, a number between $0$ and $1$ ) shrinks rewards that arrive later, and $T$ is the final step. Everything below is either computing this sum, or averaging it.

(2) The recursive form of the return. Factor a single $γ$ out of every term after the first:

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

The bracket is exactly the return starting one step later, i.e. $G_{t + 1}$ . So

$G_{t} = R_{t + 1} + γ G_{t + 1}$

Why we bother: this lets us build a whole episode's returns from the last step backwards without re-summing the tail each time — one multiply-and-add per step. We use it in L2.2.

(3) The action-value $Q (s, a)$ . Where $v_{π} (s)$ answers "how good is state $s$ ?", the action-value $Q (s, a)$ answers "how good is taking action $a$ in state $s$ , then following the policy?" It is the expected return starting from $s$ , committing to $a$ first:

$Q (s, a) = E [G_{t} ∣ S_{t} = s, A_{t} = a]$

MC estimates it the same way it estimates $V$ : average the observed returns that followed each $(s, a)$ pair, using the incremental-mean update. We use $Q$ in L4.1 and L5.2.

(4) Two model symbols used only in L3.2. A model of the environment is described by two functions. $R (s, a)$ is the expected immediate reward you get for taking action $a$ in state $s$ . $P (s^{'} ∣ s, a)$ is the transition probability — the chance of landing in next-state $s^{'}$ after taking $a$ in $s$ . "Model-free" means we do not know either of these; we only see samples. Keep these two definitions in mind for L3.2.

Level 1 — Recognition

Recall Solution

Answer: (b).

(a) updates before the episode ends and uses its own estimate $V (s^{'})$ — that is bootstrapping (Temporal-Difference learning), not MC.
(c) uses a known model $P$ — that is Dynamic Programming, not model-free.
(b) waits for the complete episode, then averages actual returns — this is exactly the Monte Carlo definition: episode-based, model-free, uses real outcomes.

Recall Solution

$G_{0} = R_{1} + R_{2} + R_{3} = 0 + 0 + 1 = 1$ With $γ = 1$ nothing is shrunk, so the return is just the plain sum of all rewards. Answer: $G_{0} = 1$ .

Level 2 — Application

Recall Solution

Plug straight into the definition, one power of $γ$ per step: $G_{0} = R_{1} + γ R_{2} + γ^{2} R_{3} + γ^{3} R_{4}$ $G_{0} = 2 + (0.5) (0) + (0.25) (4) + (0.125) (1) = 2 + 0 + 1 + 0.125 = 3.125$ Answer: $G_{0} = 3.125$ .

Recall Solution

From step 2, only $R_{3}$ and $R_{4}$ remain: $G_{2} = R_{3} + γ R_{4} = 4 + (0.5) (1) = 4.5$ Now rebuild $G_{0}$ backwards with the recursive form $G_{t} = R_{t + 1} + γ G_{t + 1}$ , applied twice: $G_{1} = R_{2} + γ G_{2} = 0 + (0.5) (4.5) = 2.25$ $G_{0} = R_{1} + γ G_{1} = 2 + (0.5) (2.25) = 2 + 1.125 = 3.125 ✓$ Matches L2.1 — the recursion and the direct sum must always agree, since one was derived from the other. Answer: $G_{2} = 4.5$ , and the recursion reproduces $G_{0} = 3.125$ .

Recall Solution

This is the 6th visit, so the step size is $α = \frac{1}{N ( s )} = \frac{1}{6}$ : $V (s) \leftarrow V (s) + \frac{1}{6} [G - V (s)] = - 0.4 + \frac{1}{6} [- 1 - (- 0.4)]$ $= - 0.4 + \frac{1}{6} (- 0.6) = - 0.4 - 0.1 = - 0.5$ Answer: $V (s) = - 0.5$ . Sanity check: the average of the running mean $- 0.4$ (weight 5) and the new $- 1$ (weight 1) is $\frac{5 ( - 0.4 ) + ( - 1 )}{6} = \frac{- 3}{6} = - 0.5$ . Identical, as it must be.

Level 3 — Analysis

Recall Solution

Step 1 — return at each visit (undiscounted, so just sum remaining rewards).

First $S_{1}$ (time $t = 0$ ): $G_{0} = R_{1} + R_{2} + R_{3} = 0 + 2 + 3 = 5$ .
Second $S_{1}$ (time $t = 2$ ): $G_{2} = R_{3} = 3$ .

Step 2 — First-visit MC: use only the first occurrence of $S_{1}$ : $V_{first} (S_{1}) = G_{0} = 5$

Step 3 — Every-visit MC: average all occurrences of $S_{1}$ : $V_{every} (S_{1}) = \frac{G _{0} + G _{2}}{2} = \frac{5 + 3}{2} = 4$

Answer: first-visit $= 5$ , every-visit $= 4$ . Unlike the parent note's example, here the two returns differ, so the methods disagree on this episode. Both would still converge to the same $v_{π} (S_{1})$ over infinitely many episodes.

Recall Solution

Greedy policy improvement with $V$ requires $π^{'} (s) = ar g max_{a} [R (s, a) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) V (s^{'})] .$ Both $R (s, a)$ (expected immediate reward) and $P (s^{'} ∣ s, a)$ (transition probability) appear explicitly — but model-free MC does not know them, so this maximisation cannot be evaluated. Fix: estimate the action-value $Q (s, a)$ instead (defined in reminder (3)). Then improvement collapses to $π^{'} (s) = ar g max_{a} Q (s, a),$ which needs no model — $Q (s, a)$ already bundles the expected reward and the expected discounted future into one learned number. That is precisely why MC control learns $Q$ , not $V$ .

Recall Solution

Unbiased. By definition $v_{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]$ . A single return $G_{t}$ is one sample of that random variable, and the expectation of a sample equals the quantity it samples — so on average it hits the true value; no systematic error. High variance: each $G_{t}$ is one whole path through a stochastic environment — every random action choice, every random transition, every random reward along the entire episode is baked into that one number. Long episodes accumulate many independent random effects, so returns scatter widely. Averaging many episodes shrinks this scatter (law of large numbers), which is why MC needs many samples.

Level 4 — Synthesis

Recall Solution

Step 1 — count steps remaining. Each move costs $- 1$ , $γ = 1$ , so the return from a state is simply $- (number of moves left)$ . The figure below draws the path on the grid and labels each arrow with the return credited to that move — so you can see how the return grows more negative (deeper) the earlier in the path a move sits.

Move from	Steps remaining	Return $G$
$(0, 0)$ right	6	$- 6$
$(0, 1)$ down	5	$- 5$
$(1, 1)$ down	4	$- 4$
$(2, 1)$ right	3	$- 3$
$(2, 2)$ right	2	$- 2$
$(2, 3)$ down	1	$- 1$

Figure: the same episode as a picture. Each coral arrow is a move; its label is the return $G$ credited to that move (equal to the negative of the moves still remaining). Notice the returns get deeper — from $- 1$ at the last move up to $- 6$ at the very first — because earlier moves must "pay for" every step that follows.

Step 2 — update $Q ((0, 0), right)$ (recall $Q (s, a)$ = expected return after taking $a$ in $s$ , from reminder (3)). With $α = 1$ from initial $0$ : $Q \leftarrow 0 + 1 \cdot (- 6 - 0) = - 6$ Answer: $Q ((0, 0), right) = - 6$ , and each earlier state-action gets credit for the return measured from when it was taken (the table and figure above).

Recall Solution

The random branch (probability $ε$ ) picks uniformly among all $4$ actions, so every action — greedy included — gets an extra $ε /∣ A ∣$ from it.

Greedy action: $(1 - ε) + \frac{ε}{∣ A ∣} = 0.8 + \frac{0.2}{4} = 0.8 + 0.05 = 0.85$ .
Each non-greedy action: $\frac{ε}{∣ A ∣} = \frac{0.2}{4} = 0.05$ .

Check: $0.85 + 3 (0.05) = 0.85 + 0.15 = 1.00 ✓$ — a valid probability distribution. Answer: greedy $= 0.85$ , each other $= 0.05$ .

Common mistake L4 trap — forgetting the random branch can re-pick greedy

The wrong instinct: greedy probability $= 1 - ε = 0.8$ , each other $= ε / (∣ A ∣ - 1) = 0.2/3$ . Why it feels right: it feels like the $ε$ mass should be shared only among the non-greedy actions. The fix: two conventions exist, and you must know which one a source uses. (i) The convention on this page and in the parent note: the random branch is uniform over all $∣ A ∣$ actions, so the greedy action also receives $ε /∣ A ∣$ → greedy $= (1 - ε) + ε /∣ A ∣$ . (ii) An alternative convention spreads $ε$ only over the $∣ A ∣ - 1$ non-greedy actions → greedy $= 1 - ε$ , each other $= ε / (∣ A ∣ - 1)$ . Both are valid distributions; they just differ. Mixing them (using convention-(ii) numbers while claiming convention-(i)) is the actual error. Always state the convention, as we did in the problem.

Level 5 — Mastery

Recall Solution

After each episode the visit count $N (s)$ goes up by one, so the step size is $α = 1/ N (s) = 1/ (episode number)$ .

Episode 1 ( $N = 1$ , $α = 1$ , return $G^{(1)} = 4$ ): $V \leftarrow 0 + 1 \cdot (4 - 0) = 4.$ Episode 2 ( $N = 2$ , $α = \frac{1}{2}$ , return $G^{(2)} = 0$ ): $V \leftarrow 4 + \frac{1}{2} (0 - 4) = 4 - 2 = 2.$ Episode 3 ( $N = 3$ , $α = \frac{1}{3}$ , return $G^{(3)} = 2$ ): $V \leftarrow 2 + \frac{1}{3} (2 - 2) = 2 + 0 = 2.$ Answer: $V (s) = 2$ . Plain average check: $\frac{G ^{(1)} + G ^{(2)} + G ^{(3)}}{3} = \frac{4 + 0 + 2}{3} = \frac{6}{3} = 2 ✓$ . The incremental mean lands exactly on the plain average at every step — that is precisely what the $α = 1/ N$ choice guarantees.

Recall Solution

(a) Greedy $= ar g max_{a} Q (s, a)$ . Since $- 3 > - 5$ , the greedy action is $a_{1}$ . (b) $P (a_{1}) = (1 - ε) + \frac{ε}{2} = 0.9 + 0.05 = 0.95$ ; $P (a_{2}) = \frac{ε}{2} = 0.05$ . (Sum $= 1.00 ✓$ .) (c) Third visit → $α = 1/3$ : $Q (s, a_{2}) \leftarrow - 5 + \frac{1}{3} [- 1 - (- 5)] = - 5 + \frac{1}{3} (4) = - 5 + 1.333 \dots = - 3.667$ Now $Q (s, a_{1}) = - 3$ and $Q (s, a_{2}) = - 3.667$ . Since $- 3 > - 3.667$ , the greedy action is still $a_{1}$ — but the gap shrank from $2$ to about $0.67$ . A couple more good returns for $a_{2}$ (only reachable because $ε > 0$ let us explore it) could flip the policy. Answer: $Q (s, a_{2}) \approx - 3.667$ ; greedy unchanged this step.

Recall Solution

Step 1 — MC only updates what it visits. The incremental-mean update touches $Q (s, a)$ only for pairs that actually occur in an episode. A pair never sampled keeps its initial value forever.

Step 2 — pure greedy self-censors. With $ε = 0$ the policy always plays the current $ar g max_{a} Q (s, a)$ . So any action that starts with a poor or merely un-tried estimate is never chosen, hence never sampled, hence never updated — even if it were truly the best. The agent locks onto whatever action first looked good, and has no mechanism to discover it was wrong.

Step 3 — the convergence condition. The guarantee that on-policy MC control reaches $π_{*}$ requires every $(s, a)$ pair to be visited infinitely often. A fixed $ε > 0$ delivers exactly this: from every state each action keeps probability $\geq ε /∣ A ∣ > 0$ , so no action is ever starved of samples. $ε = 0$ breaks the condition on line one, so the proof no longer applies and sub-optimal lock-in is possible.

Answer: pure greedy can freeze exploration and trap the policy; a fixed $ε > 0$ restores the "infinitely often" visitation that the convergence theorem needs.

Recall Self-test checklist (reveal after finishing)

Return exponent starts at $γ^{0}$ on $R_{t + 1}$ ::: yes — first reward is undiscounted Incremental step size for the $n$ -th visit ::: $α = 1/ n$ Method that averages full-episode returns ::: Monte Carlo (not TD, not DP) Why control learns $Q$ not $V$ ::: $ar g max_{a} Q$ needs no model ε-greedy probability of the greedy action (uniform-over-all convention) ::: $(1 - ε) + ε /∣ A ∣$ Reason for exploration ( $ε > 0$ ) ::: visit every $(s, a)$ infinitely often → convergence