# Exploring Starts Are Not Enough: Counterexamples and a Fix for Monte Carlo Exploring Starts

arXiv: https://arxiv.org/abs/2606.15247 · HTML: https://mlsanity.com/paper/2606.15247/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 7 of its 15 references that are in the map.
- First posted on arXiv 13 Jun 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 7 of 7)

- [Safe and Efficient Off-Policy Reinforcement Learning](https://mlsanity.com/paper/1606.02647/) (2016)
- [On the Convergence of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2002.03585/) (2020)
- [On the convergence of optimistic policy iteration for stochastic shortest path problem](https://mlsanity.com/paper/1808.08763/) (2018)
- [On the Convergence of Reinforcement Learning with Monte Carlo Exploring Starts](https://mlsanity.com/paper/2007.10916/) (2020)
- [On The Convergence Of Policy Iteration-Based Reinforcement Learning With Monte Carlo Policy Evaluation](https://mlsanity.com/paper/2301.09709/) (2023)
- [Optimistic Policy Iteration for MDPs with Acyclic Transient State Structure](https://mlsanity.com/paper/2102.00030/) (2021)
- [Convergence of Monte Carlo Optimistic Policy Iteration: Beyond Uniform State-Action Updates](https://mlsanity.com/paper/2606.10580/) (2026)

## Abstract (arXiv)

The asymptotic behaviour of Monte Carlo Exploring Starts (MCES) is a long-standing open question in reinforcement learning, even in the tabular setting. We investigated the convergence properties of tabular MCES by constructing examples in which the algorithm converges to suboptimal solutions. This paper presents new counterexamples for both initial-visit and first-visit MCES and gives a convergence-restoring modification for the initial-visit case. We show that stable suboptimal solutions may exist for initial-visit MCES with sample-average updates even when greedy actions are updated more often than non-greedy actions on average. However, by scaling learning rates inversely to update frequencies on a state-by-state basis, convergence to optimality is guaranteed. Unlike previous uniformisation methods, this modification is applicable to large-scale problems that require approximating the estimated value function. We then extend the example to show that sample-average first-visit MCES may also converge to suboptimal solutions. This largely settles a fundamental open problem and shows that exploring starts alone do not guarantee convergence to optimality. More broadly, these results highlight that convergence depends critically on the relative size and frequency of updates applied to different actions, making the choice of learning rates and the balance between exploration and exploitation central to the analysis of MCES and the implementation of scalable Monte Carlo control methods.