Research map / Bandits and online learning / Multi-armed bandits

On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization

NeurIPS 2026 · Bandits and online learning › Multi-armed bandits · approach: Pure exploration algorithms · 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.

Sharp analysis of a pessimistic KL-regularized offline bandit algorithm (KL-PCB adapted to multi-armed contextual bandits) with matching-up-to-logs lower bounds in large and small regularization regimes.

Problem

Determining the exact sample complexity of offline KL-regularized decision making, which remains uncharacterized in terms of regularization strength, number of arms, contexts and single-policy concentrability.

Approach

Uses a pessimistic (per-arm, standard MAB-style) reward penalty with a closed-form KL-regularized Gibbs policy; shows an eta*SAC/n rate for large regularization and sqrt(SAC/n) for small regularization, and proves matching lower bounds via new instance constructions, including a pairing-and-counting argument for bandits with multiple optima.

Key results

• Pessimistic KL-regularized algorithm achieves suboptimality O~(eta S A C^{pi*}/n) under large regularization (eta^2 = O~(n/(SAC))).
• Under small regularization (eta^2 = Omega~(n/(SAC))) the upper bound is O~(sqrt(SAC^{pi*}/n)), i.e. O~(eps^-2) sample complexity.
• Matching lower bounds Omega~(eta SAC/n) and Omega~(sqrt(SAC/n)) show near-minimax optimality up to logarithmic factors in both regimes.

Surprising findings

• Offline bandits with K suboptimal arms among A have sample complexity O~(K^2/(A eps^2)), which can be far smaller than the standard A/eps^2 when many arms are optimal.

Limitations

• Analysis restricted to multi-armed (contextual) bandits; not extended to linear or general function approximation.
• Lower bounds require C* bounded by exp(poly(eta)) and specific parameter ranges (e.g., eta > 4 log 2).

Experimental setup

Metrics: suboptimality gap sample complexity

Baselines: KL-PCB TMPS Greedy Sampling

Builds on: KL-PCB single-policy concentrability Le Cam / Fano / Assouad lower bound techniques

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.92)
• Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling (NeurIPS 2026 · similarity 0.88)
• Regret minimization in Linear Bandits with offline data via extended D-optimal exploration. (NeurIPS 2026 · similarity 0.87)
• Leveraging (Biased) Information: Multi-armed Bandits with Offline Data (ICML 2024 · similarity 0.87)
• On Interpolating Experts and Multi-Armed Bandits (ICML 2024 · similarity 0.87)