# On the Convergence of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2020.

## Built on by (most cited first, 10 of 10)

- [On The Convergence Of Policy Iteration-Based Reinforcement Learning With Monte Carlo Policy Evaluation](https://mlsanity.com/paper/2301.09709/) (2023)
- [Online Learning of Decision Trees with Thompson Sampling](https://mlsanity.com/paper/2404.06403/) (2024)
- [Improved Exploring Starts by Kernel Density Estimation-Based State-Space Coverage Acceleration in Reinforcement Learning](https://mlsanity.com/paper/2105.08990/) (2021)
- [Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs](https://mlsanity.com/paper/2205.09056/) (2022)
- [Applications of Reinforcement Learning in Finance -- Trading with a Double Deep Q-Network](https://mlsanity.com/paper/2206.14267/) (2022)
- [On the Convergence of Monte Carlo UCB for Random-Length Episodic MDPs](https://mlsanity.com/paper/2209.02864/) (2022)
- [Convergence of Monte Carlo Optimistic Policy Iteration: Beyond Uniform State-Action Updates](https://mlsanity.com/paper/2606.10580/) (2026)
- [Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2410.02994/) (2024)
- [Exploring Starts Are Not Enough: Counterexamples and a Fix for Monte Carlo Exploring Starts](https://mlsanity.com/paper/2606.15247/) (2026)
- [Scalar-Stepsize Nonuniform Monte Carlo Optimistic Policy Iteration: A Certified Counterexample](https://mlsanity.com/paper/2606.15978/) (2026)

## Abstract (arXiv)

A simple and natural algorithm for reinforcement learning (RL) is Monte Carlo Exploring Starts (MCES), where the Q-function is estimated by averaging the Monte Carlo returns, and the policy is improved by choosing actions that maximize the current estimate of the Q-function. Exploration is performed by "exploring starts", that is, each episode begins with a randomly chosen state and action, and then follows the current policy to the terminal state. In the classic book on RL by Sutton & Barto (2018), it is stated that establishing convergence for the MCES algorithm is one of the most important remaining open theoretical problems in RL. However, the convergence question for MCES turns out to be quite nuanced. Bertsekas & Tsitsiklis (1996) provide a counter-example showing that the MCES algorithm does not necessarily converge. Tsitsiklis (2002) further shows that if the original MCES algorithm is modified so that the Q-function estimates are updated at the same rate for all state-action pairs, and the discount factor is strictly less than one, then the MCES algorithm converges. In this paper we make headway with the original and more efficient MCES algorithm given in Sutton & Barto (1998), establishing almost sure convergence for Optimal Policy Feed-Forward MDPs, which are MDPs whose states are not revisited within any episode when using an optimal policy. Such MDPs include a large class of environments such as all deterministic environments and all episodic environments with a timestep or any monotonically changing values as part of the state. Different from the previous proofs using stochastic approximations, we introduce a novel inductive approach, which is very simple and only makes use of the strong law of large numbers.