Research map / Reinforcement learning / RL from feedback

Sharp Analysis for KL-Regularized Contextual Bandits and RLHF

NeurIPS 2025 · Reinforcement learning › RL from feedback · approach: Theory of RLHF · 0 citations (OpenAlex)

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.

Gives a sharp O(eta/epsilon) sample complexity analysis for reverse-KL-regularized contextual bandits and RLHF, with matching lower bounds, via a two-stage mixed-policy sampling algorithm whose coverage dependence is additive.

Problem

Existing theory for reverse-KL-regularized contextual bandits and RLHF gives O(1/epsilon^2) sample complexity, the same as without KL regularization, so the statistical benefit of KL regularization and the role of reference-policy coverage in online RLHF are unclear.

Approach

A fine-grained decomposition of suboptimality exploiting the strong convexity of the reverse-KL objective (via a second-order Taylor expansion of the log-partition function) yields a bound quadratic in reward error under the intermediate policy; a two-stage mixed sampling scheme (reference policy then the intermediate KL-regularized policy) then gives O(eta/epsilon) sample complexity with additive

Key results

• Lower bound Omega(min(eta log N/epsilon, log N/epsilon^2)) for KL-regularized contextual bandits and preference RLHF, showing sample complexity O(1/epsilon) when epsilon is small.
• Two-stage mixed sampling achieves O(max(eta^2 D^2, eta/epsilon) log N(epsilon/delta)) sample complexity with additive coverage dependence, versus multiplicative dependence in prior analyses.
• Synthetic experiments show mixed-policy sampling reduces suboptimality gap by a large margin relative to offline sampling from pi_0 at equal sample sizes.

Measured effects reported in the paper

Surprising findings

• Under the stated lower bound construction, the KL-regularized problem can have lower sample complexity than standard contextual bandits when epsilon is small, contrary to the expectation that regularization only adds difficulty.

Limitations

• Local-coverage result still has multiplicative dependence on the coverage coefficient; additive dependence under local coverage is left open.
• Analysis restricted to contextual bandits and assumes a planning oracle; the MDP setting is left for future work.
• Constant factors such as e^B in RLHF sample sizes can be exponentially large in the reward bound B.

Experimental setup

Datasets: synthetic contextual bandit and preference data (projected Gaussian contexts, |A|=5, 10-dim features)

Benchmarks: synthetic contextual bandit synthetic RLHF preference problem

Metrics: suboptimality gap sample complexity scaling

Baselines: Previous KL-regularized RLHF analysis with O(1/epsilon^2) sample complexity offline sampling from reference policy

Builds on: Bradley-Terry model F-design G-optimal design KL-regularized RLHF theory

Closest papers by meaning

• Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability (NeurIPS 2026 · similarity 0.95)
• Logarithmic Regret for Online KL-Regularized Reinforcement Learning (ICML 2025 · similarity 0.93)
• On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization (NeurIPS 2026 · similarity 0.93)
• Demonstration-Regularized RL (ICLR 2024 · similarity 0.90)
• Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint (ICML 2024 · similarity 0.89)
• Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimization (ICLR 2025 · similarity 0.89)