Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path
Not on the map. Why?
Abstract (arXiv)
We study the Stochastic Shortest Path (SSP) problem with a linear mixture transition kernel, where an agent repeatedly interacts with a stochastic environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the cost function or an upper bound of the expected length for the optimal policy. In this paper, we propose a new algorithm to eliminate these restrictive assumptions. Our algorithm is based on extended value iteration with a fine-grained variance-aware confidence set, where the variance is estimated recursively from high-order moments. Our algorithm achieves an tildemathcal O(dB_*√K) regret bound, where d is the dimension of the feature mapping in the linear transition kernel, B_* is the upper bound of the total cumulative cost for the optimal policy, and K is the number of episodes. Our regret upper bound matches the Omega(dB_*√K) lower bound of linear mixture SSPs in Min et al. (2022), which suggests that our algorithm is nearly minimax optimal.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 26 of its 41 references that are in the map. First posted on arXiv 14 Feb 2024.
Builds on
26 of 41 references.
References · 26
- 2017Hindsight Experience Replaycited by 1,096
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
- 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
- 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
- 2019Planning with Goal-Conditioned Policiescited by 144
- 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
- 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
- 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
- 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
- 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
- 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
- 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
14 more
- 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
- 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
- 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
- 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
- 2021Minimax Regret for Stochastic Shortest Pathcited by 30
- 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
- 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
- 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
Built on by
Citing papers per year: 2024: 1.
1 paper.