Monte Carlo Exploring Starts

Why Does This Exist?

In model-free reinforcement learning, finding an optimal policy requires learning action values $Q(s, a)$. However, if an agent acts deterministically according to its current greedy policy, it will only ever experience the actions it already believes are best. Suboptimal early estimates can permanently lock the agent into choosing poor actions, leaving genuinely optimal paths unvisited.

Without an environment transition model, you cannot compute expectations across untried branches. The classic solution is the Exploring Starts assumption: guaranteeing that every possible state-action pair $(s, a)$ has a strictly positive probability of being chosen as the initial step of an episode. This ensures infinite exploration across all choices in the limit, allowing the agent to follow a purely greedy deterministic policy for all subsequent steps.

Think of It Like This

How It Actually Works

The Exploring Starts Protocol and Policy Iteration

Monte Carlo with Exploring Starts (MCES) alternates between sample-based policy evaluation and greedy policy improvement:

1. Episode Initialization: Select $S_0 \in \mathcal{S}$ and $A_0 \in \mathcal{A}(S_0)$ such that $P(S_0 = s, A_0 = a) > 0$ for all $s, a$.
2. Deterministic Trajectory: For $t = 1, 2, \dots, T-1$, sample actions strictly according to the current deterministic policy: $A_t = \pi(S_t)$
3. Return Computation: Backward iterate from terminal time $T$ to compute returns: $G_t = R_{t+1} + \gamma G_{t+1}$
4. Value Update (First-Visit): For each pair $(s, a)$ appearing in the episode, record the first occurrence time $\tau$: $Q(s, a) \leftarrow Q(s, a) + \frac{1}{N(s, a)} \left[ G_\tau - Q(s, a) \right]$
5. Greedy Improvement: Update the policy immediately for each state visited: $\pi(s) \leftarrow \arg\max_{a} Q(s, a)$

Because exploring starts handles the exploration burden on step $0$, the policy $\pi$ does not need an exploration parameter like $\varepsilon$. It remains purely deterministic and greedy.

Worked numerical example

Consider a simplified grid navigation task with states $S_1, S_2$ and actions $\{\text{Left}, \text{Right}\}$. The discount factor is $\gamma = 0.90$.

Suppose initial estimates are $Q(S_1, \text{Left}) = 2.0$, $Q(S_1, \text{Right}) = 1.0$, meaning the initial greedy policy is $\pi(S_1) = \text{Left}$.

• Episode 1: Exploring starts selects $S_0 = S_1$ and forces exploratory action $A_0 = \text{Right}$.
  • The transition yields reward $R_1 = +4.0$ and transitions to $S_2$.
  • From $S_2$, the agent follows $\pi(S_2) = \text{Right}$, receives $R_2 = +10.0$, and reaches the terminal state.
• Return Calculation:
  • $G_1 = 10.0$
  • $G_0 = R_1 + \gamma G_1 = 4.0 + 0.90 \times 10.0 = 13.0$
• Value Update:
  • Prior $N(S_1, \text{Right}) = 1$, prior $Q = 1.0$.
  • New count $N = 2$.
  • Updated $Q(S_1, \text{Right}) = 1.0 + \frac{1}{2}(13.0 - 1.0) = 7.0$.
• Policy Improvement:
  • Compare $\arg\max_a \{ Q(S_1, \text{Left})=2.0, Q(S_1, \text{Right})=7.0 \}$.
  • The greedy policy updates: $\pi(S_1) \leftarrow \text{Right}$.

The forced initial exploration discovered a path worth $13.0$ that the initial greedy policy would have ignored forever.

Code

1from collections import defaultdict2import random3
4class MonteCarloExploringStarts:5    def __init__(self, states: list[str], actions: list[str], gamma: float = 0.9):6        self.states = states7        self.actions = actions8        self.gamma = gamma9        self.Q = defaultdict(float)10        self.returns_count = defaultdict(int)11        self.policy = {s: random.choice(actions) for s in states}12
13    def generate_episode(self, env_step_fn) -> list[tuple[str, str, float]]:14        # Exploring starts: pick S0 and A0 uniformly at random15        s0 = random.choice(self.states)16        a0 = random.choice(self.actions)17        trajectory = []18
19        s = s020        a = a021        while True:22            next_s, reward, done = env_step_fn(s, a)23            trajectory.append((s, a, reward))24            if done:25                break26            s = next_s27            a = self.policy[s]  # Strictly follow deterministic policy thereafter28        return trajectory29
30    def update_policy(self, trajectory: list[tuple[str, str, float]]) -> None:31        G = 0.032        visited = set()33        # Backward return accumulation34        for s, a, r in reversed(trajectory):35            G = self.gamma * G + r36
37        # First-visit MC update for the starting pair38        s0, a0, _ = trajectory[0]39        self.returns_count[(s0, a0)] += 140        n = self.returns_count[(s0, a0)]41        self.Q[(s0, a0)] += (G - self.Q[(s0, a0)]) / n42
43        # Greedy policy improvement44        best_action = max(self.actions, key=lambda act: self.Q[(s0, act)])45        self.policy[s0] = best_action46
47# Simulated 2-state environment step48def dummy_env(s: str, a: str) -> tuple[str, float, bool]:49    if s == "S1" and a == "Right":50        return "S2", 4.0, False51    return "Terminal", 10.0, True52
53agent = MonteCarloExploringStarts(states=["S1", "S2"], actions=["Left", "Right"])54sample_traj = [("S1", "Right", 4.0), ("S2", "Right", 10.0)]55agent.update_policy(sample_traj)56print("Updated Q(S1, Right):", agent.Q[("S1", "Right")])57print("Updated Policy for S1:", agent.policy["S1"])58# -> Updated Q(S1, Right): 13.059# -> Updated Policy for S1: Right

Watch Out For

The Quick Version

• Exploring Starts guarantees that every state-action pair $(s, a)$ has non-zero probability of being the initial step of an episode.
• By guaranteeing exploration on step $t=0$, the policy $\pi$ can remain strictly deterministic and greedy on all subsequent steps.
• Monte Carlo updates wait for episode termination and compute unbiased returns by backward accumulation.
• The assumption is viable in simulators and games but physically impractical in real-world robotics and industrial control.

What to Read Next

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