# Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 49 references that are in the map.
- First posted on arXiv 10 Oct 2022.

## Builds on (most cited first, 30 of 37)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Towards Instance-Optimal Offline Reinforcement Learning with Pessimism](https://mlsanity.com/paper/2110.08695/) (2021)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020)
- [Nearly Horizon-Free Offline Reinforcement Learning](https://mlsanity.com/paper/2103.14077/) (2021)
- [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)
- [Minimax Regret for Stochastic Shortest Path](https://mlsanity.com/paper/2103.13056/) (2021)
- [Stochastic Shortest Path with Adversarially Changing Costs](https://mlsanity.com/paper/2006.11561/) (2020)
- [Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case](https://mlsanity.com/paper/2102.05284/) (2021)
- [Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition](https://mlsanity.com/paper/2012.04053/) (2020)
- [Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies](https://mlsanity.com/paper/2203.12922/) (2022)
- [Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/2007.03760/) (2020)
- [Nearly Minimax Optimal Reward-free Reinforcement Learning](https://mlsanity.com/paper/2010.05901/) (2020)
- [Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path](https://mlsanity.com/paper/2106.08377/) (2021)
- [Learning Stochastic Shortest Path with Linear Function Approximation](https://mlsanity.com/paper/2110.12727/) (2021)
- [A Provably Efficient Sample Collection Strategy for Reinforcement Learning](https://mlsanity.com/paper/2007.06437/) (2020)
- [Online Learning for Stochastic Shortest Path Model via Posterior Sampling](https://mlsanity.com/paper/2106.05335/) (2021)
- [Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation](https://mlsanity.com/paper/2105.01593/) (2021)
- [Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP](https://mlsanity.com/paper/2112.09859/) (2021)
- [Policy Optimization for Stochastic Shortest Path](https://mlsanity.com/paper/2202.03334/) (2022)

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

- [Finding good policies in average-reward Markov Decision Processes without prior knowledge](https://mlsanity.com/paper/2405.17108/) (2024)
- [Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2410.02994/) (2024)
- [Layered State Discovery for Incremental Autonomous Exploration](https://mlsanity.com/paper/2302.03789/) (2023)
- [Dijkstra as an Oracle for Online Stochastic Shortest Path Navigation with Provable Guarantees](https://mlsanity.com/paper/2608.17703/) (2026)

## Abstract (arXiv)

We study the sample complexity of learning an ε-optimal policy in the Stochastic Shortest Path (SSP) problem. We first derive sample complexity bounds when the learner has access to a generative model. We show that there exists a worst-case SSP instance with S states, A actions, minimum cost cmin, and maximum expected cost of the optimal policy over all states Bstar, where any algorithm requires at least Omega(SABstar3/(cminε2)) samples to return an ε-optimal policy with high probability. Surprisingly, this implies that whenever cmin=0 an SSP problem may not be learnable, thus revealing that learning in SSPs is strictly harder than in the finite-horizon and discounted settings. We complement this result with lower bounds when prior knowledge of the hitting time of the optimal policy is available and when we restrict optimality by competing against policies with bounded hitting time. Finally, we design an algorithm with matching upper bounds in these cases. This settles the sample complexity of learning ε-optimal polices in SSP with generative models. We also initiate the study of learning ε-optimal policies without access to a generative model (i.e., the so-called best-policy identification problem), and show that sample-efficient learning is impossible in general. On the other hand, efficient learning can be made possible if we assume the agent can directly reach the goal state from any state by paying a fixed cost. We then establish the first upper and lower bounds under this assumption. Finally, using similar analytic tools, we prove that horizon-free regret is impossible in SSPs under general costs, resolving an open problem in (Tarbouriech et al., 2021c).