mlsanityData to 14 Oct 2026

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

arXiv 2606.15247 ↗First posted 13 Jun 2026cs.LG cs.AIcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

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.

Builds on

7 of 15 references.

References · 7

  1. 2016Safe and Efficient Off-Policy Reinforcement Learningcited by 264
  2. 2020On the Convergence of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learningcited by 10
  3. 2018On the convergence of optimistic policy iteration for stochastic shortest path problemcited by 9
  4. 2020On the Convergence of Reinforcement Learning with Monte Carlo Exploring Startscited by 9
  5. 2023On The Convergence Of Policy Iteration-Based Reinforcement Learning With Monte Carlo Policy Evaluationcited by 9
  6. 2021Optimistic Policy Iteration for MDPs with Acyclic Transient State Structurecited by 5
  7. 2026Convergence of Monte Carlo Optimistic Policy Iteration: Beyond Uniform State-Action Updatescited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning
  2. 2024Model-Free Active Exploration in Reinforcement Learning
  3. 2024Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning
  4. 2024Beyond Optimism: Exploration With Partially Observable Rewards
  5. 2025Auto-exploration for online reinforcement learning
  6. 2025Efficiency of Parallel and Restart Exploration Strategies in Model Free Stochastic Simulations
  7. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  8. 2025Harnessing the Power of Reinforcement Learning for Adaptive MCMC