On-Policy First-Visit MC Control

Learn the best way to act straight from full episodes, with no model and no staged starts, by keeping every action slightly possible and improving the same policy you play.

A backward return of 12.7 lifts Q(s, a2) from 1.0 to 4.9 and hands the greedy 0.80 to a2

Why Does This Exist?

Without a model of the environment you cannot plan ahead, so you must learn action values $Q(s, a)$ from experience and then act greedily in them. That creates a trap: a deterministic policy always picks the same action per state, so rival actions never get sampled, their values never get learned, and the agent can never find out it is wrong.

Theory papers dodge the trap with exploring starts, the assumption that every episode begins at a random state-action pair. Real systems cannot do that. A car cannot start mid-crash, a plant cannot boot into a fault, chess always opens from the same board. This page removes the assumption with epsilon-soft policies: every action keeps at least $\varepsilon / |\mathcal{A}(s)|$ probability everywhere, so every reachable pair gets sampled infinitely often from ordinary fixed starts.

The price and the payoff both matter here. For the starting assumption this replaces, see Monte Carlo with exploring starts. For the prediction half of the machinery, see Monte Carlo control. For the exploration device itself, see epsilon-greedy.

The one idea you need first

Generalized policy iteration alternates evaluation (refresh $Q$ toward the current policy's values) with improvement (point the policy at the best $Q$ ). Monte Carlo evaluation needs complete episodes, because the return $G_t$ is only known at the end. First-visit counting keeps one return per state-action pair per episode, the earliest one, so correlated repeats inside loopy episodes do not pose as fresh data.

Think of It Like This

The touring comic with a fixed experiment budget

A comic plays a hundred identical theater dates. The crowd paid for laughs, which argues for the proven set every night. But proven-only means the act fossilizes, and the televised special needs new killers. Teleporting into the middle of an untested bit is not an option: every show starts at the same microphone check.

So the comic fixes a budget: 85 percent proven closers, 15 percent notebook experiments, every single night. A new bit that bombs tanks its own average on the spot, because the comic is sampling on-policy and feels the silence. A bit that erupts climbs the ranking and displaces an old closer within a week.

Where it stops: the comic drops the experiment budget to zero for the special. A fixed-epsilon agent never does. It keeps testing 15 percent of the time forever, which means it converges to the best stay-curious policy, not the best act it ever found.

How It Actually Works

An $\varepsilon$ -soft policy satisfies $\pi(a \mid s) \ge \varepsilon / |\mathcal{A}(s)|$ for every state and action. The $\varepsilon$ -greedy version piles the remaining mass on the current best action $a^* = \arg\max_a Q(s, a)$ :

\pi(a \mid s) = \begin{cases} 1 - \varepsilon + \varepsilon / |\mathcal{A}(s)| & a = a^* \\ \varepsilon / |\mathcal{A}(s)| & a \neq a^* \end{cases}

Improvement is safe inside this family. If $\pi'$ is $\varepsilon$ -greedy in $q_\pi$ , a short argument shows $q_\pi(s, \pi'(s)) \ge v_\pi(s)$ at every state: the uniform exploration baseline cancels out of both sides, and no weighted average can beat the maximum it is averaged against. The policy improvement theorem then gives $v_{\pi'} \ge v_\pi$ everywhere. Each update either gains or holds still, and stillness means optimal among $\varepsilon$ -soft policies.

The loop per episode: roll one trajectory under $\pi$ , walk it backward accumulating $G \leftarrow \gamma G + R$ , and on the first visit of each $(s, a)$ pair update $Q \leftarrow Q + (G - Q) / N(s, a)$ , then re-greedy the policy at that state.

Worked example

State $s$ has three actions, $\varepsilon = 0.3$ , $\gamma = 0.9$ . The exploration share per action is $0.3 / 3 = 0.10$ , so the greedy action holds $1 - 0.3 + 0.10 = 0.80$ . Current table: $Q(s, a_1) = 2.0$ with 4 visits, $Q(s, a_2) = 1.0$ with 2 visits, $Q(s, a_3) = 0.5$ with 1 visit. Greedy action is $a_1$ at 0.80.

This episode an exploration roll picks $a_2$ at $t = 0$ , then collects rewards 1, 4, 10. Walking backward:

$G_2 = 10.0$
$G_1 = 4.0 + 0.9(10.0) = 13.0$
$G_0 = 1.0 + 0.9(13.0) = 1.0 + 11.7 = 12.7$

Pair $(s, a_2)$ appears once, so its first visit counts: visits $2 \to 3$ , and $Q(s, a_2) = 1.0 + (12.7 - 1.0) / 3 = 1.0 + 3.9 = 4.9$ . Now $4.9 > 2.0$ , the greedy action flips to $a_2$ , and the 0.80 mass moves with it: $\pi(a_2 \mid s) = 0.80$ , $\pi(a_1 \mid s) = \pi(a_3 \mid s) = 0.10$ . One lucky exploration found a better action and the policy followed the evidence the same episode.

Code

These two helpers replay the episode arithmetic above:

1def backward_returns(rewards: list[float], gamma: float = 0.9) -> list[float]:2    """Discounted return from each step, computed back to front."""3    running = 0.04    out: list[float] = []5    for reward in reversed(rewards):6        running = reward + gamma * running7        out.append(round(running, 2))8    out.reverse()9    return out10
11
12def update_q(old_q: float, visits: int, new_return: float) -> tuple[int, float]:13    """First-visit incremental mean update for one state-action pair."""14    visits = visits + 115    return visits, round(old_q + (new_return - old_q) / visits, 2)16
17
18print(backward_returns([1.0, 4.0, 10.0]))  # -> [12.7, 13.0, 10.0]19print(update_q(1.0, 2, 12.7))  # -> (3, 4.9)

The returns match the hand walk, and the $Q$ update lands exactly on 4.9 with 3 visits.

Watch Out For

A fixed epsilon never reaches the deterministic optimum

This method converges to the best $\varepsilon$ -soft policy, not the best policy. With $\varepsilon = 0.3$ the agent keeps playing a random action 30 percent of the time at every state, forever, including states where a mistake is expensive. Near a cliff edge it learns a wide detour, because its values correctly price in its own future randomness.

If you need the deterministic optimum, anneal $\varepsilon$ toward zero across episodes so exploration dies out, or switch to an off-policy method where the behavior stays curious and the target goes fully greedy.

Updating every visit leaks correlated returns

Inside one loopy episode the same pair can appear three times with three overlapping returns. Updating on all three treats one episode as three independent samples and biases early values, because the later returns contain the earlier ones. The backward walk must check each step against the pair's first-visit index and skip the repeats.

Record first-visit positions on the way forward, then gate the update on the way back. If your $Q$ values oscillate in mazes but behave in hallways, a missing first-visit gate is the first suspect.

The Quick Version

Epsilon-soft policies give every action at least $\varepsilon / |\mathcal{A}(s)|$ probability, so all pairs get sampled without staged exploring starts.
The method is on-policy throughout: it evaluates and improves the same $\varepsilon$ -greedy policy that gathers the episodes.
Epsilon-greedy improvement cannot lose value: each step moves to the best $\varepsilon$ -soft policy or stays optimal.
Returns accumulate backward per episode and update $Q$ once per pair at its first visit; here 12.7 takes $Q(s, a_2)$ from 1.0 to 4.9 and flips the greedy action.
A fixed epsilon converges below the deterministic optimum, so anneal it when the final policy must stop exploring.