Research map / Reinforcement learning / MDPs and planning
Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes KUCB-RL, an optimistic kernel ridge regression algorithm for infinite-horizon average-reward RL, with a new confidence interval for kernel-based expected value prediction and no-regret bounds for polynomial-eigendecay kernels.
Problem
Regret minimization in infinite-horizon average-reward (undiscounted) MDPs with nonlinear function approximation via kernel ridge regression, where prior guarantees were limited to tabular or linear models.
Approach
An optimistic UCB proxy built from kernel ridge regression predictions of the expected value function, updated in windows of length w, with a new confidence interval valid for arbitrary regularization rho and a lemma bounding sums of standard deviations under delayed (batched) updates.
Key results
- Regret bound O(T/w + (w + (w/sqrt(rho)) sqrt(gamma(T;rho)+log(T/delta))) sqrt(rho T gamma(T;rho) + rho^2 w^2 gamma(T;rho) gamma(T/w;rho))) with high probability, yielding O~(d^{1/2} T^{3/4}) for linear kernels, improving the linear bound by d^{1/4}.
- For SE (exponential eigendecay) kernels the regret is O~(T^{3/4}).
- For p-polynomial eigendecay kernels (Matern, NT) regret is O~(T^{(3p+5)/(4p+4)}), a no-regret guarantee; Matern gives T^{(3nu+4d)/(4nu+4d)}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use KUCB-RL with a linear kernel instead of OLSVI.FH | Infinite-horizon average-reward RL · Bellman optimality equation, linear | regret: $\Oct((dT)^{3/4})$ -> $\Oct\left(d^{\frac{1}{2}}T^{\frac{3}{4}}\right)$; improving by a factor of $d^{\frac{1}{4}}$ | Helped |
| Use KUCB-RL with a kernel having exponential eigendecay | KUCB-RL · Infinite-horizon average-reward RL (kernel-based, exponential eigendecay) | regret: $\Oct\left(T^{\frac{3}{4}}\right)$ | Helped |
| Use KUCB-RL with a kernel having polynomial eigendecay | KUCB-RL · Infinite-horizon average-reward RL (kernel-based, polynomial eigendecay) | regret: $\Oct(T^{\frac{3p+5}{4p+4}})$ | Helped |
| Use KUCB-RL with a Matérn kernel | KUCB-RL · Infinite-horizon average-reward RL (Matérn kernel) | regret: $\mathcal{O}\left( T^{\frac{3\nu+4d}{4\nu+4d}} \right)$ | Helped |
Limitations
- Relies on an optimistic closure assumption on the value function class that is somewhat restrictive.
- Computational complexity O(T^4/w) due to repeated matrix inversion; sparse approximations are not analyzed here.
- Regret rates are likely suboptimal relative to bandit lower bounds; optimality not established.
Experimental setup
Metrics: regret
Baselines: UCB-AVG OLSVI.FH MDP-Exp2 GP-UCB
Builds on: GP-UCB OLSVI.FH Kernel-based episodic RL (Yang et al. kernel UCRL) Abbasi-Yadkori linear bandit confidence sets Bellman optimality equation assumption from linear MDP work
Closest papers by meaning
- Kernelized Reinforcement Learning with Order Optimal Regret Bounds (NeurIPS 2023 · similarity 0.92)
- Reward-Free Kernel-Based Reinforcement Learning (ICML 2024 · similarity 0.92)
- Logarithmic Regret for Online KL-Regularized Reinforcement Learning (ICML 2025 · similarity 0.89)
- Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning (ICLR 2024 · similarity 0.89)
- A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward (ICML 2025 · similarity 0.88)
- Exploration-Driven Policy Optimization in RLHF: Theoretical Insights on Efficient Data Utilization (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.