mlsanityData to 14 Oct 2026

Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learning

arXiv 2406.15250 ↗First posted 21 Jun 2024cs.LGcited by 2

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

Abstract (arXiv)

Reinforcement Learning (RL) has shown great empirical success in various application domains. The theoretical aspects of the problem have been extensively studied over past decades, particularly under tabular and linear Markov Decision Process structures. Recently, non-linear function approximation using kernel-based prediction has gained traction. This approach is particularly interesting as it naturally extends the linear structure, and helps explain the behavior of neural-network-based models at their infinite width limit. The analytical results however do not adequately address the performance guarantees for this case. We will highlight this open problem, overview existing partial results, and discuss related challenges.

Key facts. Cited by 2 papers 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 9 of its 12 references that are in the map. First posted on arXiv 21 Jun 2024.

Builds on

9 of 12 references.

References · 9

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2017On Kernelized Multi-armed Banditscited by 352
  4. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  5. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  6. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
  7. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 39
  8. 2023On the Sublinear Regret of GP-UCBcited by 26
  9. 2020Value Function Approximations via Kernel Embeddings for No-Regret Reinforcement Learningcited by 7

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 1.

2 papers.

  1. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithmcited by 6
  2. 2025Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learningcited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2026Improved Model-based Reinforcement Learning with Smooth Kernels
  2. 2024Prior-dependent analysis of posterior sampling reinforcement learning with function approximation
  3. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds
  4. 2026Mathematical methods of reinforcement learning
  5. 2024Horizon-Free Regret for Linear Markov Decision Processes
  6. 2026Variance-Adaptive Optimal Algorithm for Reinforcement Learning with Multinomial Logit Function Approximation
  7. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learning
  8. 2026Limiting-Kernel Q(λ): Bridging Short and Long Horizons