mlsanityData to 13 Oct 2026

Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path

arXiv 2106.08377 ↗First posted 15 Jun 2021cs.LG stat.MLcited by 23

Not on the map. Why?

Abstract (arXiv)

We introduce a generic template for developing regret minimization algorithms in the Stochastic Shortest Path (SSP) model, which achieves minimax optimal regret as long as certain properties are ensured. The key of our analysis is a new technique called implicit finite-horizon approximation, which approximates the SSP model by a finite-horizon counterpart only in the analysis without explicit implementation. Using this template, we develop two new algorithms: the first one is model-free (the first in the literature to our knowledge) and minimax optimal under strictly positive costs; the second one is model-based and minimax optimal even with zero-cost state-action pairs, matching the best existing result from [Tarbouriech et al., 2021b]. Importantly, both algorithms admit highly sparse updates, making them computationally more efficient than all existing algorithms. Moreover, both can be made completely parameter-free.

Key facts. Cited by 23 papers in the map (data through 13 Oct 2026). Builds on 21 of its 43 references that are in the map. First posted on arXiv 15 Jun 2021.

Builds on

21 of 43 references.

References · 21

  1. 2017Hindsight Experience Replaycited by 1,104
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 501
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  5. 2019Planning with Goal-Conditioned Policiescited by 145
  6. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  7. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  8. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  9. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  10. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  11. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  12. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
9 more
  1. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 38
  2. 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
  3. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  4. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  5. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  6. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  7. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  8. 2021Confidence-Budget Matching for Sequential Budgeted Learningcited by 11
  9. 2020Improved Sample Complexity for Incremental Autonomous Exploration in MDPscited by 9

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 4; 2022: 9; 2023: 4; 2024: 3; 2025: 2; 2026: 1.

23 papers.

Sort:

By area:

  1. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  2. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  3. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  4. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  5. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 18
  6. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  7. 2022Policy Optimization for Stochastic Shortest Pathcited by 13
  8. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  9. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  10. 2024Horizon-Free Regret for Linear Markov Decision Processescited by 6
  11. 2022Exploration, Exploitation, and Engagement in Multi-Armed Bandits with Abandonmentcited by 5
  12. 2021Adaptive Multi-Goal Explorationcited by 4
11 more
  1. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
  2. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 4
  3. 2021A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponentcited by 3
  4. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2
  5. 2022A Unified Algorithm for Stochastic Path Problemscited by 1
  6. 2024Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Pathcited by 1
  7. 2024Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learningcited by 1
  8. 2025Stochastic Shortest Path with Sparse Adversarial Costscited by 1
  9. 2022Convex duality for stochastic shortest path problems in known and unknown environmentscited by 0
  10. 2023Layered State Discovery for Incremental Autonomous Explorationcited by 0
  11. 2026Improved Model-based Reinforcement Learning with Smooth Kernelscited by 0