mlsanityData to 7 Oct 2026

Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation

arXiv 2105.01593 ↗First posted 4 May 2021cs.LG stat.MLcited by 15

Not on the map. Why?

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.

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

Builds on

20 of 33 references.

References · 20

  1. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  2. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  3. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  4. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  5. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  6. 2017Deep Exploration via Randomized Value Functionscited by 155
  7. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  8. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  9. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  10. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  11. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  12. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
8 more
  1. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  2. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  3. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  4. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  5. 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
  6. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  7. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  8. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18

Built on by

Cited by year

Citing papers per year: 2021: 4; 2022: 5; 2023: 4; 2024: 1; 2025: 1.

15 papers.

Sort:

  1. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  2. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  3. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  4. 2023Optimistic Planning by Regularized Dynamic Programmingcited by 8
  5. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  6. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  7. 2022Exploration, Exploitation, and Engagement in Multi-Armed Bandits with Abandonmentcited by 5
  8. 2021Adaptive Multi-Goal Explorationcited by 4
  9. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
  10. 2022Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimalitycited by 3
  11. 2022A Unified Algorithm for Stochastic Path Problemscited by 1
  12. 2023Multi-Agent Congestion Cost Minimization With Linear Function Approximationscited by 1
3 more
  1. 2024Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Pathcited by 1
  2. 2023Convergence of SARSA with linear function approximation: The random horizon casecited by 0
  3. 2025Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problemscited by 0