# Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 18 of its 36 references that are in the map.
- First posted on arXiv 3 Oct 2024.

## 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, 18 of 18)

- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020)
- [No-Regret Exploration in Goal-Oriented Reinforcement Learning](https://mlsanity.com/paper/1912.03517/) (2019)
- [Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret](https://mlsanity.com/paper/2104.11186/) (2021)
- [Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path](https://mlsanity.com/paper/2106.08377/) (2021)
- [Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning](https://mlsanity.com/paper/2111.00633/) (2021)
- [Bandits with many optimal arms](https://mlsanity.com/paper/2103.12452/) (2021)
- [Optimistic PAC Reinforcement Learning: the Instance-Dependent View](https://mlsanity.com/paper/2207.05852/) (2022)
- [Policy Optimization for Stochastic Shortest Path](https://mlsanity.com/paper/2202.03334/) (2022)
- [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)
- [Towards Instance-Optimality in Online PAC Reinforcement Learning](https://mlsanity.com/paper/2311.05638/) (2023)
- [Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path](https://mlsanity.com/paper/2210.04946/) (2022)
- [On the Convergence of Monte Carlo UCB for Random-Length Episodic MDPs](https://mlsanity.com/paper/2209.02864/) (2022)

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

- [Reinforcement Learning with Random Time Horizons](https://mlsanity.com/paper/2506.00962/) (2025)

## Abstract (arXiv)

Monte Carlo Exploring Starts (MCES), which aims to learn the optimal policy using only sample returns, is a simple and natural algorithm in reinforcement learning which has been shown to converge under various conditions. However, the convergence rate analysis for MCES-style algorithms in the form of sample complexity has received very little attention. In this paper we develop a finite sample bound for a modified MCES algorithm which solves the stochastic shortest path problem. To this end, we prove a novel result on the convergence rate of the policy iteration algorithm. This result implies that with probability at least 1-δ, the algorithm returns an optimal policy after tildeO(SAK3log3frac1δ) sampled episodes, where S and A denote the number of states and actions respectively, K is a proxy for episode length, and tildeO hides logarithmic factors and constants depending on the rewards of the environment that are assumed to be known.