Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span
Not on the map. Why?
Abstract (arXiv)
This paper proposes a computationally tractable algorithm for learning infinite-horizon average-reward linear mixture Markov decision processes (MDPs) under the Bellman optimality condition. Our algorithm for linear mixture MDPs achieves a nearly minimax optimal regret upper bound of widetildeO(d√sp(v^*)T) over T time steps where sp(v^*) is the span of the optimal bias function v^* and d is the dimension of the feature mapping. Our algorithm applies the recently developed technique of running value iteration on a discounted-reward MDP approximation with clipping by the span. We prove that the value iteration procedure, even with the clipping operation, converges. Moreover, we show that the associated variance term due to random transitions can be bounded even under clipping. Combined with the weighted ridge regression-based parameter estimation scheme, this leads to the nearly minimax optimal regret guarantee.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 33 of its 47 references that are in the map. First posted on arXiv 19 Oct 2024.
Builds on
33 of 47 references.
References · 33
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
- 2019A Survey of Autonomous Driving: Common Practices and Emerging Technologiescited by 373
- 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
- 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
- 2019Provably Efficient Exploration in Policy Optimizationcited by 203
- 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
- 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
- 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
- 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
- 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
- 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
- 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
21 more
- 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
- 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
- 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
- 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
- 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
- 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
- 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
- 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
- 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
- 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
- 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
- 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
- 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
- 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
- 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
- 2020Tightening Exploration in Upper Confidence Reinforcement Learningcited by 24
- 2020Improved Analysis of UCRL2 with Empirical Bernstein Inequalitycited by 18
- 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
- 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 13
- 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
- 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
Built on by
Citing papers per year: 2026: 1.
1 paper.