mlsanityData to 7 Oct 2026

Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret

arXiv 2104.11186 ↗First posted 22 Apr 2021cs.LG stat.MLcited by 34

Not on the map. Why?

Abstract (arXiv)

We study the problem of learning in the stochastic shortest path (SSP) setting, where an agent seeks to minimize the expected cost accumulated before reaching a goal state. We design a novel model-based algorithm EB-SSP that carefully skews the empirical transitions and perturbs the empirical costs with an exploration bonus to induce an optimistic SSP problem whose associated value iteration scheme is guaranteed to converge. We prove that EB-SSP achieves the minimax regret rate tildeO(Bstar √S A K), where K is the number of episodes, S is the number of states, A is the number of actions, and Bstar bounds the expected cumulative cost of the optimal policy from any state, thus closing the gap with the lower bound. Interestingly, EB-SSP obtains this result while being parameter-free, i.e., it does not require any prior knowledge of Bstar, nor of Tstar, which bounds the expected time-to-goal of the optimal policy from any state. Furthermore, we illustrate various cases (e.g., positive costs, or general costs when an order-accurate estimate of Tstar is available) where the regret only contains a logarithmic dependence on Tstar, thus yielding the first (nearly) horizon-free regret bound beyond the finite-horizon MDP setting.

Key facts. Cited by 34 papers in the map (data through 7 Oct 2026). Builds on 25 of its 47 references that are in the map. First posted on arXiv 22 Apr 2021.

Builds on

25 of 47 references.

References · 25

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  4. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  5. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  6. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  7. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  8. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  9. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  10. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  11. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  12. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
13 more
  1. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
  2. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  3. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  4. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  5. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 38
  6. 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
  7. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  8. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  9. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  10. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  11. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  12. 2020Improved Sample Complexity for Incremental Autonomous Exploration in MDPscited by 9
  13. 2017The Stochastic Shortest Path Problem : A polyhedral combinatorics perspectivecited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 13; 2023: 8; 2024: 3; 2025: 3; 2026: 1.

34 papers.

Sort:

  1. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  2. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  3. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  4. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
  5. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  6. 2022Policy Optimization with Linear Temporal Logic Constraintscited by 19
  7. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  8. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  9. 2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15
  10. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  11. 2022Policy Optimization for Stochastic Shortest Pathcited by 13
  12. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
22 more
  1. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  2. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  3. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  4. 2022Exploration, Exploitation, and Engagement in Multi-Armed Bandits with Abandonmentcited by 5
  5. 2021Adaptive Multi-Goal Explorationcited by 4
  6. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
  7. 2023Online Reinforcement Learning with Uncertain Episode Lengthscited by 4
  8. 2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4
  9. 2022Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimalitycited by 3
  10. 2022Multi-armed Bandit Learning on a Graphcited by 3
  11. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 3
  12. 2022Near-Optimal Algorithms for Autonomous Exploration and Multi-Goal Stochastic Shortest Pathcited by 2
  13. 2022A Unified Algorithm for Stochastic Path Problemscited by 1
  14. 2023Multi-Agent Congestion Cost Minimization With Linear Function Approximationscited by 1
  15. 2024Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Pathcited by 1
  16. 2024Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learningcited by 1
  17. 2025Stochastic Shortest Path with Sparse Adversarial Costscited by 1
  18. 2022Convex duality for stochastic shortest path problems in known and unknown environmentscited by 0
  19. 2023Layered State Discovery for Incremental Autonomous Explorationcited by 0
  20. 2025Learning The Minimum Action Distancecited by 0
  21. 2025Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problemscited by 0
  22. 2026Dijkstra as an Oracle for Online Stochastic Shortest Path Navigation with Provable Guaranteescited by 0