aiqbench analysis
This research resolves a decades-old open problem in reinforcement learning by demonstrating that Monte Carlo Exploring Starts can converge to suboptimal solutions without specific algorithmic adjustments. The authors provide a concrete fix involving state-by-state scaling of learning rates, which guarantees convergence even for large-scale problems requiring value function approximation. These findings are critical for practitioners relying on standard exploration strategies, confirming that the mere presence of exploring starts is insufficient for optimality in tabular settings.
Exploring Starts Are Not Enough: Counterexamples and a Fix for Monte Carlo Exploring Starts
arXiv:2606.15247v1 Announce Type: new Abstract: 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.
Abstract: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.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
arXiv:2606.15247 [cs.LG]
(or arXiv:2606.15247v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2606.15247 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 306 words
Related coverage
Adaptive Parallel Reasoning: The Next Paradigm in Efficient Inference Scaling
BAIR Blog · May 8, 2026
Extreme Event Likelihoods with Guided Generative Models
NVIDIA · Jul 13, 2026
Interview with Matthias Troyer, Vice President & Technical Fellow at Microsoft
Quantum Computing Report · Sep 23, 2026
Guest Post: What a High School Student Found When He Stress-Tested a Quantum Benchmark
The Quantum Insider · Jul 22, 2026