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

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

## Key facts

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

## Builds on (most cited first, 21 of 21)

- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [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)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Planning with Goal-Conditioned Policies](https://mlsanity.com/paper/1911.08453/) (2019)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Online Convex Optimization in Adversarial Markov Decision Processes](https://mlsanity.com/paper/1905.07773/) (2019)
- [Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs](https://mlsanity.com/paper/2006.08040/) (2020)
- [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020)
- [Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies](https://mlsanity.com/paper/1905.11527/) (2019)
- [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)
- [Confidence-Budget Matching for Sequential Budgeted Learning](https://mlsanity.com/paper/2102.03400/) (2021)
- [Improved Sample Complexity for Incremental Autonomous Exploration in MDPs](https://mlsanity.com/paper/2012.14755/) (2020)

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

- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints](https://mlsanity.com/paper/2202.00150/) (2022)
- [Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies](https://mlsanity.com/paper/2203.12922/) (2022)
- [Learning Stochastic Shortest Path with Linear Function Approximation](https://mlsanity.com/paper/2110.12727/) (2021)
- [Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments](https://mlsanity.com/paper/2301.13446/) (2023)
- [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)
- [Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environments](https://mlsanity.com/paper/2205.13044/) (2022)
- [Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2305.07911/) (2023)
- [Horizon-Free Regret for Linear Markov Decision Processes](https://mlsanity.com/paper/2403.10738/) (2024)
- [Exploration, Exploitation, and Engagement in Multi-Armed Bandits with Abandonment](https://mlsanity.com/paper/2205.13566/) (2022)
- [A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponent](https://mlsanity.com/paper/2109.03396/) (2021)
- [Adaptive Multi-Goal Exploration](https://mlsanity.com/paper/2111.12045/) (2021)
- [Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path](https://mlsanity.com/paper/2210.04946/) (2022)
- [Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes](https://mlsanity.com/paper/2210.11604/) (2022)
- [Minimax Optimal Reinforcement Learning with Quasi-Optimism](https://mlsanity.com/paper/2503.00810/) (2025)
- [A Unified Algorithm for Stochastic Path Problems](https://mlsanity.com/paper/2210.09255/) (2022)
- [Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path](https://mlsanity.com/paper/2402.08998/) (2024)
- [Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2410.02994/) (2024)
- [Stochastic Shortest Path with Sparse Adversarial Costs](https://mlsanity.com/paper/2511.00637/) (2025)
- [Convex duality for stochastic shortest path problems in known and unknown environments](https://mlsanity.com/paper/2208.00330/) (2022)
- [Layered State Discovery for Incremental Autonomous Exploration](https://mlsanity.com/paper/2302.03789/) (2023)
- [Improved Model-based Reinforcement Learning with Smooth Kernels](https://mlsanity.com/paper/2605.07218/) (2026)

## 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.