mlsanityData to 14 Oct 2026

Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learning

arXiv 2502.07715 ↗First posted 11 Feb 2025cs.LGcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Reinforcement Learning (RL) problems are being considered under increasingly more complex structures. While tabular and linear models have been thoroughly explored, the analytical study of RL under nonlinear function approximation, especially kernel-based models, has recently gained traction for their strong representational capacity and theoretical tractability. In this context, we examine the question of statistical efficiency in kernel-based RL within the reward-free RL framework, specifically asking: how many samples are required to design a near-optimal policy? Existing work addresses this question under restrictive assumptions about the class of kernel functions. We first explore this question by assuming a generative model, then relax this assumption at the cost of increasing the sample complexity by a factor of H, the length of the episode. We tackle this fundamental problem using a broad class of kernels and a simpler algorithm compared to prior work. Our approach derives new confidence intervals for kernel ridge regression, specific to our RL setting, which may be of broader applicability. We further validate our theoretical findings through simulations.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 34 of its 68 references that are in the map. First posted on arXiv 11 Feb 2025.

Builds on

34 of 68 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learning21 Jun

Other references · 33

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,920
  3. 2017Curiosity-driven Exploration by Self-supervised Predictioncited by 1,194
  4. 2016Unifying Count-Based Exploration and Intrinsic Motivationcited by 639
  5. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  6. 2018Is Q-learning Provably Efficient?cited by 487
  7. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  8. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 269
  9. 2018Provably Efficient Maximum Entropy Explorationcited by 242
  10. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  11. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  12. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
21 more
  1. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  2. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  3. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  4. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  5. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  6. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
  7. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  8. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 57
  9. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  10. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
  11. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 52
  12. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  13. 2019On Online Learning in Kernelized Markov Decision Processescited by 35
  14. 2023On the Sublinear Regret of GP-UCBcited by 26
  15. 2020Kernel-Based Reinforcement Learning: A Finite-Time Analysiscited by 23
  16. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  17. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  18. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  19. 2023Sample Complexity of Kernel-Based Q-Learningcited by 8
  20. 2020Value Function Approximations via Kernel Embeddings for No-Regret Reinforcement Learningcited by 7
  21. 2024Demystifying Linear MDPs and Novel Dynamics Aggregation Frameworkcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Improved Model-based Reinforcement Learning with Smooth Kernelscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm
  2. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  3. 2024Leveraging Unlabeled Data Sharing through Kernel Function Approximation in Offline Reinforcement Learning
  4. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
  5. 2025Statistical and Algorithmic Foundations of Reinforcement Learning
  6. 2024Towards Sample-Efficiency and Generalization of Transfer and Inverse Reinforcement Learning: A Comprehensive Literature Review
  7. 2022On Practical Reinforcement Learning: Provable Robustness, Scalability, and Statistical Efficiency
  8. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?