Exploring Starts and Epsilon-Soft Policies

Monte Carlo control estimates the action-value function $q_\pi(s,a)$ from returns observed after visiting $(s,a)$ in sampled episodes, then improves the policy by acting greedily with respect to these estimates: $\pi(s) = \arg\max_a q(s,a)$. The generalized policy iteration (GPI) framework alternates evaluation and improvement and is known to converge to $q_*$ and $\pi_*$ provided every $(s,a)$ pair is evaluated infinitely often. This is not a minor technical footnote — it is the linchpin of the convergence proof. If a pair $(s,a)$ is visited only finitely many times (or not at all), its value estimate can remain arbitrarily wrong, and greedy improvement built on a wrong estimate can permanently avoid the action that was actually best.

Exploring starts (ES) is the assumption that every episode begins in a state-action pair $(s_0, a_0)$ drawn so that all pairs have nonzero probability of being the start — typically sampled uniformly over $\mathcal{S} \times \mathcal{A}$. After that random first step, the agent follows its current policy $\pi$ for the rest of the episode. Because the start distribution has full support and episodes repeat forever, every pair is visited infinitely often in the limit, which is exactly the condition GPI requires. Exploring starts is elegant in theory but demands a simulator (or environment) that lets you reset into any state-action pair on command — true in board games like blackjack or in Monte Carlo tree search, but false in most real interactive systems, where the agent cannot simply teleport into an arbitrary state.

Epsilon-soft policies solve the same problem without needing special resets. A policy $\pi$ is called $\varepsilon$-soft if

for some small $\varepsilon > 0$. The most common instance is the epsilon-greedy policy: with probability $1-\varepsilon$ it takes the greedy (currently best-estimated) action, and with probability $\varepsilon$ it picks uniformly at random among all actions (including possibly the greedy one again). Because every action retains probability at least $\varepsilon/|\mathcal{A}(s)|$ at every visited state, and every state is visited with positive probability under a reasonable environment, every $(s,a)$ pair is sampled infinitely often over an infinite stream of episodes — satisfying the same visitation requirement, but through the policy's own randomness rather than through artificial episode starts.

Monte Carlo Exploring Starts (MC-ES) modifies ordinary first-visit Monte Carlo control by randomizing the initial state-action pair of every episode, then following the current greedy policy thereafter, updating $Q$ and improving $\pi$ after each episode. ``` Algorithm: Monte Carlo Control with Exploring Starts (first-visit) Initialize: Q(s, a) <- arbitrary, for all s in S, a in A(s) Returns(s, a) <- empty list, for all s, a pi(s) <- arbitrary action in A(s), for all s Repeat forever (for each episode): Choose S0 in S and A0 in A(S0) uniformly at random # exploring start Generate episode: S0, A0, R1, S1, A1, R2, ..., S_{T-1}, A_{T-1}, R_T following policy pi from step 1 onward (A_t = pi(S_t) for t >= 1) G <- 0 For t = T-1, T-2, ..., 0: G <- gamma * G + R_{t+1} Unless the pair (S_t, A_t) appears in S0,A0,...,S_{t-1},A_{t-1}: Append G to Returns(S_t, A_t) Q(S_t, A_t) <- average(Returns(S_t, A_t)) pi(S_t) <- argmax_a Q(S_t, a) # greedy improvement ```

On-policy first-visit Monte Carlo control with an epsilon-soft policy replaces the artificial random start with an epsilon-greedy policy followed from a (fixed or randomly chosen, but not necessarily exhaustive) initial state. ``` Algorithm: On-policy first-visit MC control (epsilon-soft) Input: small epsilon > 0 Initialize: Q(s, a) <- arbitrary, for all s, a Returns(s, a) <- empty list, for all s, a pi <- an arbitrary epsilon-soft policy (e.g., uniform random) Repeat forever (for each episode): Generate episode using pi: S0, A0, R1, S1, A1, ..., S_{T-1}, A_{T-1}, R_T G <- 0 For t = T-1, T-2, ..., 0: G <- gamma G + R_{t+1} Unless (S_t, A_t) appears earlier in the episode: Append G to Returns(S_t, A_t) Q(S_t, A_t) <- average(Returns(S_t, A_t)) A <- argmax_a Q(S_t, a) # break ties consistently For all a in A(S_t): if a == A: pi(a | S_t) <- 1 - epsilon + epsilon / |A(S_t)| else: pi(a | S_t) <- epsilon / |A(S_t)| ``` The only structural difference from ordinary MC control is the final block: instead of collapsing to a deterministic greedy action, the policy is updated to the epsilon-greedy distribution* around the current best action. This single change is what removes the need for exploring starts, since the policy itself keeps every action alive with probability at least $\varepsilon/|\mathcal{A}(s)|$ at every state it visits, for as long as the algorithm runs.

Time and space complexity. For a tabular MDP with $|\mathcal{S}|$ states and $|\mathcal{A}|$ actions per state, both algorithms store $Q$ and `Returns` as tables of size $O(|\mathcal{S}|\cdot|\mathcal{A}|)$; maintaining running averages instead of full return lists keeps the space at $O(|\mathcal{S}|\cdot|\mathcal{A}|)$ rather than growing without bound. Per episode of length $T$, generating the trajectory costs $O(T)$ environment steps, and the backward return/update pass costs $O(T)$ time (with a first-visit check implementable in $O(1)$ amortized time per step using a `seen` hash set, or $O(T)$ worst case with a naive scan), plus $O(|\mathcal{A}(s)|)$ per visited state to redo the epsilon-greedy distribution update. So one episode costs $O(T \cdot |\mathcal{A}|)$ time in the epsilon-soft variant and $O(T)$ in the ES variant (policy update is $O(1)$, just overwrite the greedy action). Neither algorithm has a fixed iteration bound — convergence is asymptotic, driven by the law of large numbers on sample returns, so total time to reach a given accuracy scales with the number of episodes needed for the averages to concentrate, which is problem-dependent and not expressible as a closed-form function of $|\mathcal{S}|$, $|\mathcal{A}|$ alone.

Correctness of Monte Carlo Exploring Starts. The proof sketch runs by analogy to classical policy iteration. Fix the current policy $\pi_k$. Each episode's first-visit return is an unbiased sample of $q_{\pi_k}(s,a)$ for the pair $(s,a)$ visited first in that episode (standard Monte Carlo estimation argument: the return is a sample path realization of the random variable whose expectation defines $q_\pi$). Because exploring starts guarantees every $(s,a)$ pair is the initial pair with positive probability at every episode, the strong law of large numbers implies

Once $Q_k$ is (in the idealized limit) exactly $q_{\pi_k}$, the greedy update $\pi_{k+1}(s) = \arg\max_a Q_k(s,a)$ is precisely the policy improvement step of policy iteration, and the policy improvement theorem guarantees $q_{\pi_{k+1}}(s,a) \ge q_{\pi_k}(s,a)$ for all $(s,a)$, with strict improvement somewhere unless $\pi_k$ is already optimal. Iterating this argument, and noting the sequence of value functions is bounded above by $q_*$, gives convergence to $q_*$ and an optimal $\pi_*$ — this is the argument given (with the appropriate technical care about interleaving evaluation and improvement per episode rather than waiting for full convergence at each step) in the classical treatment of MC-ES.

Correctness of on-policy epsilon-soft control. Here the target changes. Define $\Pi_\varepsilon$ as the set of all epsilon-soft policies. The claim is not that the algorithm converges to $\pi_*$ (which is deterministic and hence not epsilon-soft for $\varepsilon>0$), but that it converges to the best policy within $\Pi_\varepsilon$. The key step is a modified policy improvement lemma: for any epsilon-soft $\pi$, define $\pi'$ as the epsilon-greedy policy with respect to $q_\pi$. Then

can be shown to be $\ge v_\pi(s)$ for every state $s$, by writing $\pi'$'s expectation as a convex combination — $\varepsilon$ worth of uniform exploration plus $(1-\varepsilon)$ worth of the greedy action — and using the fact that a weighted average of $q_\pi(s,a)$ values, when the weights match $\pi(a|s)$ scaled appropriately, cannot exceed the maximum term. Concretely,

and since $\max_a q_\pi(s,a) \ge \sum_a \frac{\pi(a|s) - \varepsilon/|\mathcal{A}(s)|}{1-\varepsilon} q_\pi(s,a)$ (a weighted average bounded by the max, using that these adjusted weights sum to 1 and are non-negative because $\pi$ is $\varepsilon$-soft), substituting back shows the right side collapses exactly to $v_\pi(s)$. Hence $v_{\pi'}(s) \ge v_\pi(s)$ for all $s$, by the standard policy improvement theorem applied within the constrained class. Iterating produces a monotonically improving sequence of epsilon-soft policies bounded above by the best epsilon-soft policy, which (by the same GPI convergence argument, now restricted to $\Pi_\varepsilon$) converges to that constrained optimum. The visitation guarantee is immediate: since $\pi(a|s) \ge \varepsilon/|\mathcal{A}(s)| > 0$ for every reachable $(s,a)$ at every iteration, and episodes repeat forever, every pair is sampled infinitely often with probability 1, satisfying GPI's requirement without ever needing a special reset.

Honest tradeoffs. Exploring starts gives a cleaner asymptotic target ($\pi_*$ itself) but an assumption that is often physically impossible to satisfy — you cannot reset a real robot or a live user session into an arbitrary state-action pair. Epsilon-soft control works with an ordinary environment interface but pays a permanent price: even the final, converged policy still acts randomly an $\varepsilon$ fraction of the time, so the actual behavior is never truly optimal, only optimal-within-the-soft-class. Shrinking $\varepsilon$ toward 0 over time (a GLIE — greedy in the limit with infinite exploration — schedule) can recover convergence to $\pi_*$ itself, but this reintroduces a scheduling hyperparameter and a slower, less clean convergence guarantee.

Consider a tiny two-state MDP used to make the exploration argument concrete. States $\{s_1, s_2\}$, two actions per state $\{a_1, a_2\}$, deterministic transitions and rewards chosen so that the truly best action at $s_1$ is $a_2$, but a poorly initialized greedy policy would never discover this without exploration:

Suppose $Q$ is initialized to zero everywhere, and the initial (arbitrary) policy happens to pick $\pi(s_1) = a_1$. Under plain greedy Monte Carlo control with no exploration mechanism, every episode starts at $s_1$, takes $a_1$ (the only action the policy ever tries at $s_1$), transitions to $s_2$, takes $\pi(s_2)$, and terminates. The pair $(s_1, a_2)$ is never sampled, so $Q(s_1,a_2)$ stays at its initial value of 0 forever, and the policy never switches to the truly optimal action, even though its value (10.0) is obviously better than $a_1$'s (4.0) — the agent simply never gets the evidence. Now trace exploring starts. Over many episodes, the start pair is drawn uniformly from all four $(s,a)$ combinations. On episodes that start at $(s_1, a_2)$:

After just one sweep touching all four pairs, $Q(s_1,a_2)=10 > Q(s_1,a_1)=4$, so the greedy improvement step immediately sets $\pi(s_1) \leftarrow a_2$ — the optimal action — something plain greedy MC could never have discovered. Now trace epsilon-soft control with $\varepsilon = 0.2$, $|\mathcal{A}|=2$, starting from the same bad policy bias. Every episode starts at $s_1$ (no artificial reset), but at $s_1$ the epsilon-greedy policy still assigns probability $\varepsilon/2 = 0.1$ to $a_2$ even while $a_1$ looks greedy. So roughly 1 in 10 episodes samples $(s_1, a_2)$ purely from the policy's own randomness:

After enough episodes, $Q(s_1,a_2)$ converges to 10, overtakes $Q(s_1,a_1)=4$, and the epsilon-greedy policy flips to assigning probability $0.9$ to $a_2$ and $0.1$ to $a_1$ — no reset to $(s_1,a_2)$ was ever needed, because the policy's own 10% exploration rate did the job. The final behavior is still not fully deterministic (it retains a 10% chance of the suboptimal action forever, unless $\varepsilon$ is annealed), which is exactly the tradeoff discussed above.

The exploration/exploitation tension long predates reinforcement learning as a field, tracing back to the multi-armed bandit problem studied in sequential statistics. Its formalization inside Monte Carlo control, and the epsilon-soft/epsilon-greedy machinery specifically, was consolidated in the modern reinforcement learning framework built by Richard Sutton and Andrew Barto, whose textbook treatment of Monte Carlo methods made exploring starts and epsilon-soft policies standard vocabulary for the field.

Epsilon-greedy exploration, the direct descendant of epsilon-soft policies, is the default exploration mechanism in most practical value-based reinforcement learning systems, including DQN and its successors used for game-playing agents, resource allocation, and simulated robotic control. Exploring starts, while rarely usable in production systems, remains the cleanest theoretical device for teaching why Monte Carlo control converges, and it appears in practice inside self-play training pipelines and Monte Carlo tree search variants (such as in game engines), where random rollout starts or random opening moves are used deliberately to guarantee coverage of the game tree. Both mechanisms are direct ancestors of the exploration bonuses, optimistic initialization, and upper-confidence-bound strategies used in modern bandit algorithms and in exploration-heavy deep RL research. Understanding the ES-versus-epsilon-soft distinction is also the natural on-ramp to the broader question of On-Policy vs Off-Policy Learning: on-policy methods like Sarsa must keep the acting policy epsilon-soft to keep exploring, while off-policy methods like Q-learning can behave epsilon-greedily during data collection while learning about a separate, fully greedy target policy — decoupling exploration from the policy being optimized. This connects directly back to core ideas in Temporal-Difference Learning and to the general convergence theory of Generalized Policy Iteration.

Ask the tutor: How does the modified policy improvement theorem change if the epsilon-soft policy is replaced by a softmax (Boltzmann) exploration policy instead?