Monte Carlo Exploring Starts

Why Does This Exist?

A greedy policy has a blind spot: it only visits what it already likes. If early estimates are wrong, the truly best action never gets tried, so its value never improves, so it never gets tried. The loop seals shut. This is the classic exploration problem in Monte Carlo control, where values are learned from full episodes with no model to query about untried branches.

Exploring starts breaks the loop at the root. Sutton and Barto (Chapter 5) assume every state action pair $(s, a)$ has nonzero probability of opening an episode. After that forced first step, the agent follows its deterministic greedy policy all the way to termination. Randomize the opening, keep everything else greedy, and every choice gets sampled infinitely often in the limit, which is what lets plain averaging converge to optimal values in episodic tasks. When forced openings are impossible, the successor is on-policy first-visit MC control, which explores with soft policies instead.

The one idea you need first

Values here are action values $Q(s, a)$: the expected return after taking action $a$ in state $s$. Returns $G_t$ are discounted sums of rewards to the end of the episode, $G_t = R_{t+1} + \gamma G_{t+1}$, with $\gamma$ discounting later rewards. The full treatment of estimating them from episodes is in Monte Carlo action values.

Think of It Like This

How It Actually Works

Initialize $Q(s, a)$ arbitrarily and $\pi(s)$ as any deterministic policy. Then repeat:

Open. Draw $S_0$ and $A_0$ so that every pair keeps positive probability, $P(S_0 = s, A_0 = a) > 0$ for all $s$ and $a$.

Roll. From $t = 1$ onward act greedily, $A_t = \pi(S_t)$, until termination at time $T$.

Score. Walk backward accumulating $G_t = R_{t+1} + \gamma G_{t+1}$.

Update. For the first visit of each pair in the episode, with $N(s, a)$ counting visits so far:

Improve. For each visited state, set $\pi(s) \leftarrow \arg\max_a Q(s, a)$.

No exploration parameter appears anywhere after step zero. The policy stays fully greedy because the opening carries the whole exploration burden.

Worked example

Two states, actions Left and Right, $\gamma = 0.90$. Current values at $S_1$: $Q(S_1, \text{Left}) = 2.0$, $Q(S_1, \text{Right}) = 1.0$, so $\pi(S_1) = \text{Left}$. Exploring starts forces the opening $(S_1, \text{Right})$. The episode runs: $R_1 = 4.0$ into $S_2$, then the greedy policy earns $R_2 = 10.0$ and terminates.

The pair $(S_1, \text{Right})$ was seen once before, so $N$ goes $1$ to $2$:

Now $\arg\max$ compares $2.0$ against $7.0$, so $\pi(S_1)$ flips to Right. One forced opening found a $13.0$ line the greedy policy would never have touched. The diagram draws this exact episode.

Code

This snippet replays the worked example with type hints: accumulate the return backward, then apply the averaging update.

1def episode_return(rewards: list[float], gamma: float) -> float:2    """Discounted return G0 for one episode's reward sequence."""3    g = 0.04    for r in reversed(rewards):5        g = r + gamma * g6    return g7
8
9def mc_update(q: float, n: int, g: float) -> tuple[float, int]:10    """Fold one first-visit return into the running average."""11    n_new = n + 112    return q + (g - q) / n_new, n_new13
14
15g0 = episode_return([4.0, 10.0], 0.90)16print(f"G0={g0:.4f}")  # -> G0=13.000017q_new, n_new = mc_update(1.0, 1, g0)18print(f"Q={q_new:.4f} N={n_new}")  # -> Q=7.0000 N=2

The printout matches the hand computation: $G_0 = 13.0$ and $Q$ moves $1.0$ to $7.0$, flipping the greedy choice.

Watch Out For

The Quick Version

• Exploring starts forces every state action pair to keep a nonzero chance of opening an episode.
• After the forced first step the policy is purely greedy and deterministic, with no exploration parameter.
• Episodes are scored backward into returns $G_t$, and first visits update $Q$ with a running average.
• Each visited state's policy is reset to the current greedy best, which is what drives improvement.
• It fits simulators and episodic tasks, not physical systems with unsafe starts or tasks that never terminate.

What to Read Next

• Monte Carlo Control
• Monte Carlo Action Values
• On-Policy First-Visit MC Control