Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm
On the map: Deep reinforcement learning methods → RL theory and sample complexity
Abstract (arXiv)
Reinforcement learning utilizing kernel ridge regression to predict the expected value function represents a powerful method with great representational capacity. This setting is a highly versatile framework amenable to analytical results. We consider kernel-based function approximation for RL in the infinite horizon average reward setting, also referred to as the undiscounted setting. We propose an optimistic algorithm, similar to acquisition function based algorithms in the special case of bandits. We establish novel no-regret performance guarantees for our algorithm, under kernel-based modelling assumptions. Additionally, we derive a novel confidence interval for the kernel-based prediction of the expected value function, applicable across various RL problems.
Key facts. Cited by 6 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 29 of its 52 references that are in the map. First posted on arXiv 30 Oct 2024.
Builds on
29 of 52 references.
Closest ancestors · 1
Same direction, newest first
Other references · 28
- 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
- 2018QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulationcited by 743
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
- 2017On Kernelized Multi-armed Banditscited by 352
- 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
- 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
- 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
- 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
- 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
- 2017Uncertainty-Aware Reinforcement Learning for Collision Avoidancecited by 88
- 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
- 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
16 more
- 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
- 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
- 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
- 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 39
- 2020A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescited by 32
- 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
- 2023On the Sublinear Regret of GP-UCBcited by 26
- 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
- 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
- 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
- 2022Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Timescited by 13
- 2019On Batch Bayesian Optimizationcited by 12
- 2023Delayed Feedback in Kernel Banditscited by 10
- 2023Sample Complexity of Kernel-Based Q-Learningcited by 8
- 2020Value Function Approximations via Kernel Embeddings for No-Regret Reinforcement Learningcited by 7
- 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
Built on by
Citing papers per year: 2025: 2; 2026: 4.
6 papers.
- 2025No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processescited by 4
- 2025Kernel Based Maximum Entropy Inverse Reinforcement Learning for Mean-Field Gamescited by 3
- 2026Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spacescited by 2
- 2026One-Step Bellman Alignment Enables Provably Efficient Transfer in Online RLcited by 1
- 2026Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learningcited by 1
- 2026Learning Kernel-Based MDPs from Episodic Preferential Feedbackcited by 0
- 2026Learning Kernel-Based MDPs from Episodic Preferential Feedback22 May 2026
- 2026Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learning11 May 2026
- 2026Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces9 Mar 2026
- 2026One-Step Bellman Alignment Enables Provably Efficient Transfer in Online RL29 Jan 2026
- 2025No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes23 Oct 2025
- 2025Kernel Based Maximum Entropy Inverse Reinforcement Learning for Mean-Field Games19 Jul 2025
Similar, not cited
Close in wording, no citation either way
- 2025Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learning
- 2026Improved Model-based Reinforcement Learning with Smooth Kernels
- 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learning
- 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning
- 2026Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecification
- 2024Prior-dependent analysis of posterior sampling reinforcement learning with function approximation
- 2023Reward Learning as Doubly Nonparametric Bandits: Optimal Design and Scaling Laws
- 2020Average-reward model-free reinforcement learning: a systematic review and literature mapping