mlsanityData to 7 Oct 2026

Sample Complexity of Kernel-Based Q-Learning

arXiv 2302.00727 ↗First posted 1 Feb 2023cs.LG cs.AI stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

Modern reinforcement learning (RL) often faces an enormous state-action space. Existing analytical results are typically for settings with a small number of state-actions, or simple models such as linearly modeled Q-functions. To derive statistically efficient RL policies handling large state-action spaces, with more general Q-functions, some recent works have considered nonlinear function approximation using kernel ridge regression. In this work, we derive sample complexities for kernel based Q-learning when a generative model exists. We propose a nonparametric Q-learning algorithm which finds an ε-optimal policy in an arbitrarily large scale discounted MDP. The sample complexity of the proposed algorithm is order optimal with respect to ε and the complexity of the kernel (in terms of its information gain). To the best of our knowledge, this is the first result showing a finite sample complexity under such a general model.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 25 of its 50 references that are in the map. First posted on arXiv 1 Feb 2023.

Builds on

25 of 50 references.

References · 25

  1. 2018QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulationcited by 730
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2017On Kernelized Multi-armed Banditscited by 348
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  6. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  7. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  8. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  9. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  10. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  11. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 87
  12. 2017Uncertainty-Aware Reinforcement Learning for Collision Avoidancecited by 86
13 more
  1. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 77
  2. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  3. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  4. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  5. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  6. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 38
  7. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 36
  8. 2020Kernel-Based Reinforcement Learning: A Finite-Time Analysiscited by 23
  9. 2020The Elliptical Potential Lemma Revisitedcited by 23
  10. 2021Uniform Generalization Bounds for Overparameterized Neural Networkscited by 21
  11. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  12. 2021Open Problem: Tight Online Confidence Intervals for RKHS Elementscited by 13
  13. 2018Online learning with kernel lossescited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 3; 2025: 1; 2026: 3.

8 papers.

  1. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  2. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithmcited by 6
  3. 2024RL-STaR: Theoretical Analysis of Reinforcement Learning Frameworks for Self-Taught Reasonercited by 4
  4. 2024Leveraging Unlabeled Data Sharing through Kernel Function Approximation in Offline Reinforcement Learningcited by 2
  5. 2025Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learningcited by 1
  6. 2026Sample Efficient Active Algorithms for Offline Reinforcement Learningcited by 0
  7. 2026Improved Model-based Reinforcement Learning with Smooth Kernelscited by 0
  8. 2026Learning Kernel-Based MDPs from Episodic Preferential Feedbackcited by 0