mlsanityData to 14 Oct 2026

Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs

arXiv 2205.11507 ↗First posted 23 May 2022cs.LG math.OC stat.MLcited by 52

Not on the map. Why?

Abstract (arXiv)

Recent studies have shown that episodic reinforcement learning (RL) is not more difficult than contextual bandits, even with a long planning horizon and unknown state transitions. However, these results are limited to either tabular Markov decision processes (MDPs) or computationally inefficient algorithms for linear mixture MDPs. In this paper, we propose the first computationally efficient horizon-free algorithm for linear mixture MDPs, which achieves the optimal tilde O(d√K +d2) regret up to logarithmic factors. Our algorithm adapts a weighted least square estimator for the unknown transitional dynamic, where the weight is both variance-aware and uncertainty-aware. When applying our weighted least square estimator to heterogeneous linear bandits, we can obtain an tilde O(d√sumk=1K σk2 +d) regret in the first K rounds, where d is the dimension of the context and σk2 is the variance of the reward in the k-th round. This also improves upon the best-known algorithms in this setting when σk2's are known.

Key facts. Cited by 52 papers in the map (data through 14 Oct 2026). Builds on 32 of its 51 references that are in the map. First posted on arXiv 23 May 2022.

Builds on

32 of 51 references.

References · 32

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  5. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  6. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  7. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  8. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  9. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  10. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  11. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  12. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
20 more
  1. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  2. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  3. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  4. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  5. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 76
  6. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  7. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  8. 2019Nearly Minimax-Optimal Regret for Linearly Parameterized Banditscited by 54
  9. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  10. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  11. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  12. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  13. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 35
  14. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  15. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  16. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  17. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  18. 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26
  19. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 18
  20. 2019Tight Regret Bounds for Infinite-armed Linear Contextual Banditscited by 17

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 17; 2024: 14; 2025: 11; 2026: 8.

52 papers.

Sort:

By area:

  1. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  2. 2024Reinforcement Learning from Human Feedback with Active Queriescited by 43
  3. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
  4. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 31
  5. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 29
  6. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  7. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 17
  8. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 16
  9. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 15
  10. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 14
  11. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  12. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
38 more
  1. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  2. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  3. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  4. 2023On the Model-Misspecification in Reinforcement Learningcited by 7
  5. 2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximationcited by 7
  6. 2025Replicable Reinforcement Learning with Linear Function Approximationcited by 7
  7. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  8. 2024Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimizationcited by 6
  9. 2024Horizon-Free Regret for Linear Markov Decision Processescited by 6
  10. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  11. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPscited by 6
  12. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  13. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Banditscited by 5
  14. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 4
  15. 2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4
  16. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  17. 2023Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximationcited by 4
  18. 2025Variance-Dependent Regret Lower Bounds for Contextual Banditscited by 4
  19. 2025Vector-valued self-normalized concentration inequalities beyond sub-Gaussianitycited by 4
  20. 2023SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Banditscited by 3
  21. 2023Federated Linear Bandits with Finite Adversarial Actionscited by 3
  22. 2024Variance-Aware Linear UCB with Deep Representation for Neural Contextual Banditscited by 3
  23. 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
  24. 2024Variance-Dependent Regret Bounds for Non-stationary Linear Banditscited by 2
  25. 2025Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Explorationcited by 2
  26. 2025Variance-Aware Feel-Good Thompson Sampling for Contextual Banditscited by 2
  27. 2024Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Pathcited by 1
  28. 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Spancited by 1
  29. 2025Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimationcited by 1
  30. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
  31. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 1
  32. 2024Misspecified Q-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Errorcited by 0
  33. 2025Towards Optimal Differentially Private Regret Bounds in Linear MDPscited by 0
  34. 2025Adaptive Resolving Methods for Markov Decision Processes with Function Approximationscited by 0
  35. 2025Second-Order Bounds for [0,1]-Valued Regression via Betting Losscited by 0
  36. 2026Stochastic Linear Bandits with Parameter Noisecited by 0
  37. 2026Learning to Attack: A Bandit Approach to Adversarial Context Poisoningcited by 0
  38. 2026Improved Model-based Reinforcement Learning with Smooth Kernelscited by 0

50 most cited of 52 All 52 (JSON)