mlsanityData to 7 Oct 2026

Provably Efficient Kernelized Q-Learning

arXiv 2204.10349 ↗First posted 21 Apr 2022cs.LG stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

We propose and analyze a kernelized version of Q-learning. Although a kernel space is typically infinite-dimensional, extensive study has shown that generalization is only affected by the effective dimension of the data. We incorporate such ideas into the Q-learning framework and derive regret bounds for arbitrary kernels. In particular, we provide concrete bounds for linear kernels and Gaussian RBF kernels; notably, the latter bound looks almost identical to the former, only that the actual dimension is replaced by a different notion of dimensionality. Finally, we test our algorithm on a suite of classic control tasks; remarkably, under the Gaussian RBF kernel, it achieves reasonably good performance after only 1000 environmental steps, while its neural network counterpart, deep Q-learning, still struggles.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 38 of its 72 references that are in the map. First posted on arXiv 21 Apr 2022.

Builds on

38 of 72 references.

References · 38

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2017On Kernelized Multi-armed Banditscited by 348
  6. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  7. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  8. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  9. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  10. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  11. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  12. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
26 more
  1. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  2. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  3. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  4. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  5. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  6. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  7. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  8. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  9. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  10. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  11. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  12. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  13. 2019Nearly Minimax-Optimal Regret for Linearly Parameterized Banditscited by 54
  14. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
  15. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  16. 2018Massively scalable Sinkhorn distances via the Nystr"om methodcited by 40
  17. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 39
  18. 2019On Online Learning in Kernelized Markov Decision Processescited by 32
  19. 2020Kernel-Based Reinforcement Learning: A Finite-Time Analysiscited by 23
  20. 2019√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcited by 20
  21. 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19
  22. 2020Regret Bounds for Discounted MDPscited by 19
  23. 2019Tight Regret Bounds for Infinite-armed Linear Contextual Banditscited by 17
  24. 2014Practical Kernel-Based Reinforcement Learningcited by 14
  25. 2017Second-Order Kernel Online Convex Optimization with Adaptive Sketchingcited by 13
  26. 2019Efficient online learning with kernels for adversarial large scale problemscited by 12

Built on by

Cited by year

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

4 papers.

  1. 2022Near-optimal Policy Identification in Active Reinforcement Learningcited by 7
  2. 2024Tighter Confidence Bounds for Sequential Kernel Regressioncited by 7
  3. 2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5
  4. 2023Kernel-Based Distributed Q-Learning: A Scalable Reinforcement Learning Approach for Dynamic Treatment Regimescited by 0