mlsanityData to 14 Oct 2026

Kernel-Based Reinforcement Learning: A Finite-Time Analysis

arXiv 2004.05599 ↗First posted 12 Apr 2020cs.LG stat.MLcited by 23

Not on the map. Why?

Abstract (arXiv)

We consider the exploration-exploitation dilemma in finite-horizon reinforcement learning problems whose state-action space is endowed with a metric. We introduce Kernel-UCBVI, a model-based optimistic algorithm that leverages the smoothness of the MDP and a non-parametric kernel estimator of the rewards and transitions to efficiently balance exploration and exploitation. For problems with K episodes and horizon H, we provide a regret bound of widetildeOleft( H3 K^frac2d2d+1right), where d is the covering dimension of the joint state-action space. This is the first regret bound for kernel-based RL using smoothing kernels, which requires very weak assumptions on the MDP and has been previously applied to a wide range of tasks. We empirically validate our approach in continuous MDPs with sparse rewards.

Key facts. Cited by 23 papers in the map (data through 14 Oct 2026). First posted on arXiv 12 Apr 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 2; 2023: 6; 2024: 5; 2025: 5; 2026: 4.

23 papers.

Sort:

By area:

  1. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  2. 2023Unlocking the Power of Representations in Long-term Novelty-based Explorationcited by 9
  3. 2023Sample Complexity of Kernel-Based Q-Learningcited by 8
  4. 2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
  5. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  6. 2022Near-optimal Policy Identification in Active Reinforcement Learningcited by 7
  7. 2024No-Regret Reinforcement Learning in Smooth MDPscited by 6
  8. 2023Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraintscited by 5
  9. 2022Provably Efficient Kernelized Q-Learningcited by 4
  10. 2024Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPscited by 4
  11. 2023A Kernel Perspective on Behavioural Metrics for Markov Decision Processescited by 3
  12. 2025Quantizer Design for Finite Model Approximations, Model Learning, and Quantized Q-Learning for MDPs with Unbounded Spacescited by 2
11 more
  1. 2021UVIP: Model-Free Approach to Evaluate Reinforcement Learning Algorithmscited by 1
  2. 2024Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learningcited by 1
  3. 2025Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learningcited by 1
  4. 2024Provably Adaptive Average Reward Reinforcement Learning for Metric Spacescited by 0
  5. 2025Reinforcement Learning Using known Invariancescited by 0
  6. 2025SHAP-Guided Kernel Actor-Critic for Explainable Reinforcement Learningcited by 0
  7. 2025Generalisation in Multitask Fitted Q-Iteration and Offline Q-learningcited by 0
  8. 2026Fitted Q-Iteration with Continuous Actions and Adaptive Data: Smoothed Coverage and Minimax Ratescited by 0
  9. 2026Improved Model-based Reinforcement Learning with Smooth Kernelscited by 0
  10. 2026Kernel-Based Safe Exploration in Deep Reinforcement Learningcited by 0
  11. 2026Mathematical methods of reinforcement learningcited by 0