mlsanityData to 7 Oct 2026

Minimax Regret for Stochastic Shortest Path

arXiv 2103.13056 ↗First posted 24 Mar 2021cs.LGcited by 30

Not on the map. Why?

Abstract (arXiv)

We study the Stochastic Shortest Path (SSP) problem in which an agent has to reach a goal state in minimum total expected cost. In the learning formulation of the problem, the agent has no prior knowledge about the costs and dynamics of the model. She repeatedly interacts with the model for K episodes, and has to minimize her regret. In this work we show that the minimax regret for this setting is widetilde O(√ (B_star2 + B_star) |S| |A| K) where B_star is a bound on the expected cost of the optimal policy from any state, S is the state space, and A is the action space. This matches the Omega (√ B_star2 |S| |A| K) lower bound of Rosenberg et al. [2020] for B_star ≥ 1, and improves their regret bound by a factor of √|S|. For B_star < 1 we prove a matching lower bound of Omega (√ B_star |S| |A| K). Our algorithm is based on a novel reduction from SSP to finite-horizon MDPs. To that end, we provide an algorithm for the finite-horizon setting whose leading term in the regret depends polynomially on the expected cost of the optimal policy and only logarithmically on the horizon.

Key facts. Cited by 30 papers in the map (data through 7 Oct 2026). Builds on 27 of its 45 references that are in the map. First posted on arXiv 24 Mar 2021.

Builds on

27 of 45 references.

References · 27

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  4. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  5. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  6. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  7. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  8. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  9. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  10. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  11. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  12. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
15 more
  1. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  2. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  3. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  4. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  5. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  6. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
  7. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  8. 2020Reinforcement Learning with Trajectory Feedbackcited by 40
  9. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 38
  10. 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
  11. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  12. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  13. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  14. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  15. 2021Confidence-Budget Matching for Sequential Budgeted Learningcited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 10; 2023: 4; 2024: 4; 2025: 4; 2026: 1.

30 papers.

Sort:

  1. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  2. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  3. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
  4. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  5. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  6. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  7. 2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15
  8. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  9. 2022Policy Optimization for Stochastic Shortest Pathcited by 13
  10. 2023Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximationcited by 9
  11. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  12. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
18 more
  1. 2024Delay as Payoff in MABcited by 6
  2. 2022Exploration, Exploitation, and Engagement in Multi-Armed Bandits with Abandonmentcited by 5
  3. 2021Adaptive Multi-Goal Explorationcited by 4
  4. 2022Cooperative Online Learning in Stochastic and Adversarial MDPscited by 4
  5. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
  6. 2023Online Reinforcement Learning with Uncertain Episode Lengthscited by 4
  7. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learningcited by 4
  8. 2024Risk-averse Total-reward MDPs with ERM and EVaRcited by 4
  9. 2022Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimalitycited by 3
  10. 2022A Unified Algorithm for Stochastic Path Problemscited by 1
  11. 2023Multi-Agent Congestion Cost Minimization With Linear Function Approximationscited by 1
  12. 2024Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Pathcited by 1
  13. 2025Stochastic Shortest Path with Sparse Adversarial Costscited by 1
  14. 2022Convex duality for stochastic shortest path problems in known and unknown environmentscited by 0
  15. 2025Bayesian Graph Traversalcited by 0
  16. 2025Risk-Averse Total-Reward Reinforcement Learningcited by 0
  17. 2025Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problemscited by 0
  18. 2026Dijkstra as an Oracle for Online Stochastic Shortest Path Navigation with Provable Guaranteescited by 0