Monte Carlo Control

Monte Carlo control finds good actions without any model by finishing full episodes, averaging the returns each action earned, and switching to the winners.

Two finished episodes move Q values to 4.6 for the safe action and 8.0 for the risky one, so the greedy policy switches to risky

Why Does This Exist?

Dynamic programming finds optimal policies only when the transition probabilities $P(s' \mid s, a)$ are known. In robotics, games, and trading systems they are not. Worse, improving a policy from state values $V(s)$ alone still needs a one step lookahead through those unknown probabilities, so $V(s)$ cannot pick actions by itself.

Monte Carlo control fixes both gaps at once. It evaluates action values $Q(s, a)$ directly from finished episodes, then makes the policy greedy in $Q$ , which needs no model at all:

\pi'(s) = \arg\max_{a} Q(s, a)

Unlike temporal difference learning, nothing here bootstraps from a guessed successor value. Every update uses a true sampled return $G_t$ , so there is no bootstrapping bias to diverge. The price is patience: learning waits for episodes to terminate. This page covers the control loop. Its building blocks are Monte Carlo action values and exploring starts.

The one idea you need first

Generalized policy iteration alternates evaluation with improvement: estimate how good the current policy is, then act greedily in those estimates. See generalized policy iteration for the full loop. Monte Carlo control is that loop with complete episode returns as the evaluator.

Think of It Like This

A golfer who only changes strategy at the clubhouse

A golfer tests a new swing by playing full 18 hole rounds with it. Mid fairway guesses do not count. Back at the clubhouse the scorecard shows the true total, and the golfer compares which club choices from which lies produced the lowest totals, then commits to the winners for the next round.

Two rounds can flip a decision: a safe layup strategy totals 4.6 over par while one bold drive totals 8.0 under the same scoring, so the bold drive becomes the new plan. Where it stops: golf lies are nearly repeatable, while stochastic environments need many rounds averaged before a total is trustworthy, plus deliberate experimentation so a mediocre first round does not lock in forever.

How It Actually Works

An episode $\tau = (S_0, A_0, R_1, \dots, S_T)$ under policy $\pi$ gives a discounted return per step:

G_t = R_{t+1} + \gamma G_{t+1}, \qquad G_{T} = 0

Here $R_{t+1}$ is the reward after step $t$ , $\gamma$ is the discount in $[0, 1]$ , and $G_t$ is the true total from $t$ onward. First visit Monte Carlo keeps the $G_t$ from each pair's first appearance per episode and averages:

Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \frac{1}{N(S_t, A_t)}[G_t - Q(S_t, A_t)]

where $N(s, a)$ counts visits. Improvement then sets $\pi(s)$ to the action with the highest $Q$ . By the policy improvement theorem this greedy step never hurts expected returns, so repeated evaluation plus greedification climbs toward the optimal policy. One guardrail is mandatory: every pair must keep being visited, through exploring starts or an epsilon greedy policy, or unvisited actions freeze at stale values.

Worked example

State $s_0$ offers $a_{\text{safe}}$ and $a_{\text{risky}}$ with $\gamma = 0.9$ . All values start at 0.

Episode 1 follows the safe route: $(s_0, a_{\text{safe}}, R_1 = 1.0)$ then $(s_1, a_{\text{proceed}}, R_2 = 4.0)$ to termination. Working backward:

G_1 = 4.0, \qquad G_0 = 1.0 + 0.9 \times 4.0 = 1.0 + 3.6 = 4.6

So $Q(s_1, a_{\text{proceed}}) = 4.00$ and $Q(s_0, a_{\text{safe}}) = 4.60$ . The greedy policy at $s_0$ still picks safe, since risky sits at 0.

Episode 2 explores: $(s_0, a_{\text{risky}}, R_1 = 8.0)$ straight to termination, giving $G_0 = 8.0$ and $Q(s_0, a_{\text{risky}}) = 8.00$ . Now $8.00$ beats $4.60$ , so $\pi(s_0)$ switches from safe to risky on sampled evidence alone, with no transition model consulted.

Code

This snippet replays both episodes with first visit updates and prints the values and the policy after each one.

1def backward_returns(rewards: list[float], gamma: float = 0.9) -> list[float]:2    g = 0.03    out = []4    for r in reversed(rewards):5        g = r + gamma * g6        out.append(round(g, 2))7    return list(reversed(out))8
9
10print(backward_returns([1.0, 4.0]))  # -> [4.6, 4.0]11print(backward_returns([8.0]))       # -> [8.0]12
13q = {("s0", "safe"): 4.6, ("s0", "risky"): 8.0}14print(max(["safe", "risky"], key=lambda a: q[("s0", a)]))  # -> risky

The first print shows $G_0 = 4.6$ for the safe route. The second shows $8.0$ for the risky episode. The greedy pick over the two $Q$ values is risky, exactly the policy switch in the worked example.

Watch Out For

Episodes that never end stall all learning

Monte Carlo control updates only after termination, because $G_t$ is defined backward from the final step. In continuing tasks or loops that rarely terminate, transitions pile up in memory while the policy never changes.

Symptom: a growing trajectory buffer with zero updates and flat performance. Fix: cap episodes with an explicit horizon and reset, or switch to a bootstrapping method such as one step TD that updates every transition.

Greedy improvement locking onto a mediocre action

After one lucky episode a mediocre action can lead $Q(s, a)$ while better actions sit at 0, and a fully greedy policy then never samples the alternatives, freezing their values forever.

Symptom: fast early convergence to a policy that is clearly improvable yet never changes. Fix: keep exploration alive with exploring starts where simulators allow resets, or an epsilon greedy schedule that decays but never hits exactly zero during learning.

The Quick Version

Monte Carlo control learns $Q(s, a)$ from finished episodes, so greedy action choice needs no transition model.
Each update averages true sampled returns $G_t$ , which removes bootstrapping bias but forces waiting for termination.
In the worked example, safe scores $1.0 + 0.9 \times 4.0 = 4.6$ while risky scores $8.0$ , so the policy switches to risky.
Evaluation plus greedification repeats as generalized policy iteration and climbs toward the optimal policy.
Exploring starts or epsilon greedy exploration is mandatory, or unvisited actions never get corrected.