Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning
On the map: Deep reinforcement learning methods → RL theory and sample complexity
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.
Key facts. Cited by 1 paper 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.
Builds on
18 of 36 references.
References · 18
- 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
- 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 106
- 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
- 2020Fast active learning for pure exploration in reinforcement learningcited by 92
- 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
- 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
- 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
- 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
- 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 18
- 2021Bandits with many optimal armscited by 17
- 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
- 2022Policy Optimization for Stochastic Shortest Pathcited by 13
6 more
- 2020On the Convergence of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learningcited by 10
- 2018On the convergence of optimistic policy iteration for stochastic shortest path problemcited by 9
- 2020On the Convergence of Reinforcement Learning with Monte Carlo Exploring Startscited by 9
- 2023Towards Instance-Optimality in Online PAC Reinforcement Learningcited by 7
- 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
- 2022On the Convergence of Monte Carlo UCB for Random-Length Episodic MDPscited by 2
Built on by
Citing papers per year: 2025: 1.
1 paper.
- 2025Reinforcement Learning with Random Time Horizonscited by 2
- 2025Reinforcement Learning with Random Time Horizons1 Jun 2025
Similar, not cited
Close in wording, no citation either way
- 2026Exploring Starts Are Not Enough: Counterexamples and a Fix for Monte Carlo Exploring Starts
- 2026The Sample Complexity of Policy Learning with Mu-Resets
- 2024Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise
- 2024Optimized Monte Carlo Tree Search for Enhanced Decision Making in the FrozenLake Environment
- 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterization
- 2025Improving Reinforcement Learning Sample-Efficiency using Local Approximation
- 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
- 2026Achieving ε-2 Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions