Research map / Reinforcement learning / MDPs and planning

Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability

NeurIPS 2026 · Reinforcement learning › MDPs and planning · approach: Policy optimization theory · 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.

Shows that pessimistic offline contextual bandits with forward-KL regularization achieve O~(eta/epsilon) sample complexity under single-policy concentrability (tabular and function approximation), with matching lower bounds, via a convex-conjugate suboptimality decomposition.

Problem

Statistical rate of offline decision making under forward-KL-regularized objectives, which prior work only analyzed with slow O(1/eps^2) rates or required all-policy concentrability.

Approach

A convex-analytic suboptimality decomposition for forward-KL-regularized objectives (via convex conjugates and a self-bounding argument using pessimism) that bypasses mean-value-theorem arguments, yielding fast 1/eps rates under single-policy concentrability.

Key results

• Tabular upper bound O~(eta (C^{pi*})^2 |S||A| / eps) for pessimistic forward-KL-regularized CBs.
• Function approximation upper bound O~(eta C^{pi*} D^2_{pi*} log N / eps) under single-policy concentrability.
• Minimax lower bound Omega(eta |S||A| / n) matching linear-in-eta fast rate in the high-regularization regime.

Surprising findings

• The mean-value-theorem based analysis that works for reverse KL fails for forward KL, since the relevant derivative's sign is indefinite.

Limitations

• Lower bounds only for tabular settings with uniform reference policy.
• Necessity of single-policy concentrability for forward KL remains open.
• Phase transition threshold in eta not exactly matched by upper and lower bounds.

Experimental setup

Metrics: suboptimality gap sample complexity

Baselines: forward KL-regularized RLHF (prior O~(eps^-2) analysis)

Builds on: pessimism-based offline RL reverse-KL fast-rate analyses D^2 concentrability

Closest papers by meaning

• Sharp Analysis for KL-Regularized Contextual Bandits and RLHF (NeurIPS 2025 · similarity 0.95)
• On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization (NeurIPS 2026 · similarity 0.92)
• Logarithmic Regret for Online KL-Regularized Reinforcement Learning (ICML 2025 · similarity 0.91)
• Learning to Trust Bellman Updates: Selective State-Adaptive Regularization for Offline RL (ICML 2025 · similarity 0.88)
• Iteratively Refined Behavior Regularization for Offline Reinforcement Learning (NeurIPS 2024 · similarity 0.88)
• Behavior-Regularized Diffusion Policy Optimization for Offline Reinforcement Learning (ICML 2025 · similarity 0.88)