Research map / Bandits and online learning / RL theory and MDPs
Logarithmic Regret for Online KL-Regularized Reinforcement Learning
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 optimism-based KL-regularized UCB for contextual bandits and KL-regularized LSVI-UCB for MDPs, proving O(log T) regret bounds in the standard online setting without coverage assumptions.
Problem
Regret of online KL-regularized RL (RLHF-style objectives) has only been analyzed with O(sqrt(T)) rates or under strong coverage assumptions; it is open whether KL regularization yields faster online learning than standard RL.
Approach
Decompose suboptimality via a functional gap in the normalization term (Gibbs policy) of the proxy reward, use the monotone derivative structure induced by KL regularization together with optimistic reward estimates to bound regret by squared bonuses, yielding eluder-dimension-based logarithmic regret; for MDPs, use a multi-step policy decomposition to bound regret by squared Bellman errors.
Key results
- KL-UCB achieves O(η log(N_R T) · d_R) regret for KL-regularized contextual bandits, logarithmic in T, versus the prior O(√T) bound.
- KL-regularized LSVI-UCB achieves O(η H^2 d_F log T · log N) regret for KL-regularized MDPs, claimed as the first O(log T) bound for this setting.
- Both results are obtained without the global coverage assumption required by prior bandit analyses.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use KL-UCB with optimism and the refined regularized suboptimality decomposition | KL-regularized contextual bandits · KL-regularized contextual bandits | regret: \mathcal{O}(\sqrt{T}) -> \mathcal{O}\big(\eta\log(N_{\mathcal R}T)\cdot d_{\mathcal R}\big) | Helped |
| Use KL-LSVI-UCB with the multi-step policy decomposition | KL-regularized MDPs · KL-regularized MDPs | regret: \mathcal{O}(\log T) | Helped |
| Avoid the global coverage assumption | KL-UCB for contextual bandits · KL-regularized contextual bandits | regret | Helped |
Limitations
- MDP bound carries an extra H^2 factor (horizon dependence) that is not optimized.
- Analysis is theoretical with finite function classes; no experiments are reported.
- Uses absolute reward feedback rather than preference feedback.
Experimental setup
Metrics: regret sample complexity
Baselines: Two-Stage Mixed-Policy Sampling Online Iterative M-GSHF XPO Online Iterative GSHF
Builds on: UCB / optimism principle LSVI-UCB eluder dimension Gibbs policy closed form
Closest papers by meaning
- Sharp Analysis for KL-Regularized Contextual Bandits and RLHF (NeurIPS 2025 · similarity 0.93)
- Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability (NeurIPS 2026 · similarity 0.91)
- Catastrophic Goodhart: regularizing RLHF with KL divergence does not mitigate heavy-tailed reward misspecification (NeurIPS 2024 · similarity 0.91)
- Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimization (ICLR 2025 · similarity 0.90)
- Greedy Sampling Is Provably Efficient For RLHF (NeurIPS 2025 · similarity 0.90)
- Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint (ICML 2024 · similarity 0.90)
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.