mlsanityData to 14 Oct 2026

Learning Stochastic Shortest Path with Linear Function Approximation

arXiv 2110.12727 ↗First posted 25 Oct 2021cs.LG math.OC stat.MLcited by 23

Not on the map. Why?

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.

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

40 of 66 references.

References · 40

  1. 2021Convex optimizationcited by 2,515
  2. 2017Hindsight Experience Replaycited by 1,136
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  5. 2018Is Q-learning Provably Efficient?cited by 487
  6. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  7. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  8. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  9. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  10. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  11. 2019Planning with Goal-Conditioned Policiescited by 149
  12. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
28 more
  1. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  2. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  3. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  4. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  5. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  6. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  7. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  8. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  9. 2020Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regretcited by 58
  10. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  11. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  12. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
  13. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  14. 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
  15. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  16. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  17. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  18. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  19. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  20. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  21. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  22. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
  23. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
  24. 2021Robust Risk-Aware Reinforcement Learningcited by 18
  25. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  26. 2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15
  27. 2020Improved Sample Complexity for Incremental Autonomous Exploration in MDPscited by 9
  28. 2017The Stochastic Shortest Path Problem : A polyhedral combinatorics perspectivecited by 7

Built on by

Cited by year

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

23 papers.

Sort:

By area:

  1. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  2. 2022Learn to Match with No Regret: Reinforcement Learning in Markov Matching Marketscited by 16
  3. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  4. 2022Policy Optimization for Stochastic Shortest Pathcited by 13
  5. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  6. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  7. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  8. 2023Pure Exploration in Asynchronous Federated Banditscited by 6
  9. 2021Adaptive Multi-Goal Explorationcited by 4
  10. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
  11. 2023Finding Regularized Competitive Equilibria of Heterogeneous Agent Macroeconomic Models with Reinforcement Learningcited by 4
  12. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
11 more
  1. 2022Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimalitycited by 3
  2. 2022Cascaded Gaps: Towards Gap-Dependent Regret for Risk-Sensitive Reinforcement Learningcited by 2
  3. 2022A Unified Algorithm for Stochastic Path Problemscited by 1
  4. 2023Multi-Agent Congestion Cost Minimization With Linear Function Approximationscited by 1
  5. 2024Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Pathcited by 1
  6. 2025Reinforcement Learning with Anticipation: A Hierarchical Approach for Long-Horizon Taskscited by 1
  7. 2022Age of Semantics in Cooperative Communications: To Expedite Simulation Towards Real via Offline Reinforcement Learningcited by 0
  8. 2023Convergence of SARSA with linear function approximation: The random horizon casecited by 0
  9. 2025Bayesian Graph Traversalcited by 0
  10. 2025Convergent Reinforcement Learning Algorithms for Stochastic Shortest Path Problemcited by 0
  11. 2025Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problemscited by 0