Data to 14 Oct 2026

Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP

arXiv 2112.09859 ↗First posted 18 Dec 2021cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

We introduce two new no-regret algorithms for the stochastic shortest path (SSP) problem with a linear MDP that significantly improve over the only existing results of (Vial et al., 2021). Our first algorithm is computationally efficient and achieves a regret bound widetildeOleft(√d3Bstar2Tstar Kright), where d is the dimension of the feature space, Bstar and Tstar are upper bounds of the expected costs and hitting time of the optimal policy respectively, and K is the number of episodes. The same algorithm with a slight modification also achieves logarithmic regret of order Oleft(fracd3Bstar4cmin2gapminln5fracdBstar Kcmin right), where gapmin is the minimum sub-optimality gap and cmin is the minimum cost over all state-action pairs. Our result is obtained by developing a simpler and improved analysis for the finite-horizon approximation of (Cohen et al., 2021) with a smaller approximation error, which might be of independent interest. On the other hand, using variance-aware confidence sets in a global optimization problem, our second algorithm is computationally inefficient but achieves the first "horizon-free" regret bound widetildeO(d3.5Bstar√K) with no polynomial dependency on Tstar or 1/cmin, almost matching the Omega(dBstar√K) lower bound from (Min et al., 2021).

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). Builds on 32 of its 45 references that are in the map. First posted on arXiv 18 Dec 2021.

Builds on

32 of 45 references.

References · 32

2017Minimax Regret Bounds for Reinforcement Learningcited by 503
2018Is Q-learning Provably Efficient?cited by 487
2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101

20 more

2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
2021Minimax Regret for Stochastic Shortest Pathcited by 30
2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15

Built on by

Cited by year

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

14 papers.

Sort:

By area:

2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
2022Policy Optimization for Stochastic Shortest Pathcited by 13
2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4
2022Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimalitycited by 3
2024Sample Efficient Myopic Exploration Through Multitask Reinforcement Learning with Diverse Taskscited by 2
2022A Unified Algorithm for Stochastic Path Problemscited by 1
2024Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Pathcited by 1
2025Stochastic Shortest Path with Sparse Adversarial Costscited by 1

2 more

2023Layered State Discovery for Incremental Autonomous Explorationcited by 0
2023Convergence of SARSA with linear function approximation: The random horizon casecited by 0