# Learning Stochastic Shortest Path with Linear Function Approximation

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 66 references that are in the map.
- First posted on arXiv 25 Oct 2021.

## Builds on (most cited first, 30 of 40)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [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)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [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)
- [Planning with Goal-Conditioned Policies](https://mlsanity.com/paper/1911.08453/) (2019)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [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)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Corruption-robust exploration in episodic reinforcement learning](https://mlsanity.com/paper/1911.08689/) (2019)
- [Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret](https://mlsanity.com/paper/2006.13827/) (2020)
- [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs](https://mlsanity.com/paper/2010.00587/) (2020)
- [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)
- [Variance-Aware Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2106.11960/) (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)

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

- [Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2205.13589/) (2022)
- [Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets](https://mlsanity.com/paper/2203.03684/) (2022)
- [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)
- [Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation](https://mlsanity.com/paper/2305.06446/) (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)
- [Pure Exploration in Asynchronous Federated Bandits](https://mlsanity.com/paper/2310.11015/) (2023)
- [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)
- [Finding Regularized Competitive Equilibria of Heterogeneous Agent Macroeconomic Models with Reinforcement Learning](https://mlsanity.com/paper/2303.04833/) (2023)
- [Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback](https://mlsanity.com/paper/2311.07876/) (2023)
- [Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality](https://mlsanity.com/paper/2206.04921/) (2022)
- [Cascaded Gaps: Towards Gap-Dependent Regret for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2203.03110/) (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)
- [Reinforcement Learning with Anticipation: A Hierarchical Approach for Long-Horizon Tasks](https://mlsanity.com/paper/2509.05545/) (2025)
- [Age of Semantics in Cooperative Communications: To Expedite Simulation Towards Real via Offline Reinforcement Learning](https://mlsanity.com/paper/2209.08947/) (2022)
- [Convergence of SARSA with linear function approximation: The random horizon case](https://mlsanity.com/paper/2306.04548/) (2023)
- [Bayesian Graph Traversal](https://mlsanity.com/paper/2503.05963/) (2025)
- [Convergent Reinforcement Learning Algorithms for Stochastic Shortest Path Problem](https://mlsanity.com/paper/2508.13963/) (2025)
- [Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems](https://mlsanity.com/paper/2511.04594/) (2025)

## Abstract (arXiv)

We study the stochastic shortest path (SSP) problem in reinforcement learning with linear function approximation, where the transition kernel is represented as a linear mixture of unknown models. We call this class of SSP problems as linear mixture SSPs. We propose a novel algorithm with Hoeffding-type confidence sets for learning the linear mixture SSP, which can attain an tildeO(d Bstar1.5√K/cmin) regret. Here K is the number of episodes, d is the dimension of the feature mapping in the mixture model, Bstar bounds the expected cumulative cost of the optimal policy, and cmin>0 is the lower bound of the cost function. Our algorithm also applies to the case when cmin = 0, and an tildeO(K2/3) regret is guaranteed. To the best of our knowledge, this is the first algorithm with a sublinear regret guarantee for learning linear mixture SSP. Moreover, we design a refined Bernstein-type confidence set and propose an improved algorithm, which provably achieves an tildeO(d Bstar√K/cmin) regret. In complement to the regret upper bounds, we also prove a lower bound of Omega(dBstar √K). Hence, our improved algorithm matches the lower bound up to a 1/√cmin factor and poly-logarithmic factors, achieving a near-optimal regret guarantee.