# Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 33 references that are in the map.
- First posted on arXiv 4 May 2021.

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

- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions](https://mlsanity.com/paper/2010.01374/) (2020)
- [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020)
- [Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2007.11849/) (2020)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (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)
- [Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2102.07301/) (2021)

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

- [Learning Stochastic Shortest Path with Linear Function Approximation](https://mlsanity.com/paper/2110.12727/) (2021)
- [A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2106.01577/) (2021)
- [Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP](https://mlsanity.com/paper/2112.09859/) (2021)
- [Optimistic Planning by Regularized Dynamic Programming](https://mlsanity.com/paper/2302.14004/) (2023)
- [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)
- [Exploration, Exploitation, and Engagement in Multi-Armed Bandits with Abandonment](https://mlsanity.com/paper/2205.13566/) (2022)
- [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)
- [Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality](https://mlsanity.com/paper/2206.04921/) (2022)
- [A Unified Algorithm for Stochastic Path Problems](https://mlsanity.com/paper/2210.09255/) (2022)
- [Multi-Agent Congestion Cost Minimization With Linear Function Approximations](https://mlsanity.com/paper/2301.10993/) (2023)
- [Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path](https://mlsanity.com/paper/2402.08998/) (2024)
- [Convergence of SARSA with linear function approximation: The random horizon case](https://mlsanity.com/paper/2306.04548/) (2023)
- [Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems](https://mlsanity.com/paper/2511.04594/) (2025)

## Abstract (arXiv)

We propose an algorithm that uses linear function approximation (LFA) for stochastic shortest path (SSP). Under minimal assumptions, it obtains sublinear regret, is computationally efficient, and uses stationary policies. To our knowledge, this is the first such algorithm in the LFA literature (for SSP or other formulations). Our algorithm is a special case of a more general one, which achieves regret square root in the number of episodes given access to a certain computation oracle.