mlsanityData to 14 Oct 2026

A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation

arXiv 2311.15238 ↗First posted 26 Nov 2023cs.LG math.OC stat.MLcited by 14

Not on the map. Why?

Abstract (arXiv)

The exploration-exploitation dilemma has been a central challenge in reinforcement learning (RL) with complex model classes. In this paper, we propose a new algorithm, Monotonic Q-Learning with Upper Confidence Bound (MQL-UCB) for RL with general function approximation. Our key algorithmic design includes (1) a general deterministic policy-switching strategy that achieves low switching cost, (2) a monotonic value function structure with carefully controlled function class complexity, and (3) a variance-weighted regression scheme that exploits historical trajectories with high data efficiency. MQL-UCB achieves minimax optimal regret of tildeO(d√HK) when K is sufficiently large and near-optimal policy switching cost of tildeO(dH), with d being the eluder dimension of the function class, H being the planning horizon, and K being the number of episodes. Our work sheds light on designing provably sample-efficient and deployment-efficient Q-learning with nonlinear function approximation.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). Builds on 51 of its 65 references that are in the map. First posted on arXiv 26 Nov 2023.

Builds on

51 of 65 references.

References · 51

  1. 2015Continuous control with deep reinforcement learningcited by 3,407
  2. 2016Neural Architecture Search with Reinforcement Learningcited by 1,499
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  5. 2018Is Q-learning Provably Efficient?cited by 487
  6. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  7. 2013Learning to Optimize Via Posterior Samplingcited by 256
  8. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  9. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  10. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  11. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  12. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
38 more
  1. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  2. 2021Reinforcement learning based recommender systems: A surveycited by 188
  3. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  4. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  5. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  6. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  7. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  8. 2020Deployment-Efficient Reinforcement Learning via Model-Based Offline Optimizationcited by 120
  9. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  10. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  11. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  12. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  13. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  14. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  15. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  16. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  17. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  18. 2020Sequential Batch Learning in Finite-Action Linear Contextual Banditscited by 63
  19. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  20. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  21. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  22. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
  23. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  24. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  25. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  26. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
  27. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  28. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  29. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 32
  30. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  31. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  32. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  33. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 19
  34. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  35. 2022Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Samplingcited by 10
  36. 2023Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPscited by 9
  37. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  38. 2023Low-Switching Policy Gradient with Exploration via Online Sensitivity Samplingcited by 6

50 most cited of 51 All 51 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 5; 2025: 5; 2026: 4.

14 papers.

Sort:

By area:

  1. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 33
  2. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learningcited by 22
  3. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  4. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  5. 2024Uncertainty-Aware Reward-Free Exploration with General Function Approximationcited by 5
  6. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 4
  7. 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
  8. 2025Sample and Computationally Efficient Continuous-Time Reinforcement Learning with General Function Approximationcited by 3
  9. 2025Beyond-Expert Performance with Limited Demonstrations: Efficient Imitation Learning with Double Explorationcited by 1
  10. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theorycited by 1
  11. 2026The Horizon Threshold in Cooperative Multi-Agent Reward-Free Explorationcited by 0
  12. 2026Provably Efficient Offline-to-Online Value Adaptation with General Function Approximationcited by 0
2 more
  1. 2026Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Setcited by 0
  2. 2026Provable Benefits of Regularization: Fast Rates for Adversarial Imitation Learningcited by 0