arXiv AI

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

The paper presents the first ≥O(ε^{-1}) upper bounds for offline contextual bandits with forward-KL regularization under single-policy concentrability, covering both tabular and general function approximation settings. It introduces a convex-analytical approach that leverages pessimism in a novel way, avoiding previous mean value theorem-based proofs. The authors also provide matching lower bounds, showing the tightness of their rates and that the forward-KL sample complexity reverts to the unregularized slow rate when regularization is weak.

arXiv Machine Learning
Sep 30

Provable Benefits of Regularization: Fast Rates for Adversarial Imitation Learning

The paper introduces Dually Regularized AIL, a model‑free algorithm for adversarial imitation learning that jointly applies KL policy regularization and a quadratic reward penalty based on expert and learner occupancies. It proves fast convergence rates, achieving a ×O(1/K+1/N) bound on the regularized imitation gap in finite‑horizon MDPs with general function approximation, and establishes the first algorithm to attain ×O(1/ε) sample complexity in both expert demonstrations and online interactions for this regularized objective.

By Hanbin Zhou, Shangzhe Li, Alexander Braverman, Weitong Zhang
arXiv Machine Learning
1d ago

Offline KL-Regularized Reinforcement Learning with Stochastic Transitions

The paper investigates offline KL‑regularized reinforcement learning in finite discounted Markov decision processes with unknown stochastic transitions. It establishes lower bounds on sample complexity for estimators covering the regularized optimum and proposes a pessimistic soft value iteration algorithm that achieves near‑optimal rates under certain temperature and concentrability conditions. The study also highlights the limitations of plug‑in estimators on reference‑policy data and the impact of temperature on sample requirements.

By Andrew Liu
arXiv Machine Learning
Jun 19

Stabilizing Bandits using Regularization: Precise Regret and A Quantitative Central Limit Theorem

arXiv:2603. 10184v2 Announce Type: replace-cross Abstract: Statistical inference with bandit data presents fundamental challenges owing to adaptive sampling, which violates the independence assumptions underlying classical asymptotic theory.

By Budhaditya Halder, Ishan Sengupta, Koustav Chowdhury, Samya Praharaj, Koulik Khamaru
arXiv Machine Learning
Oct 16

Transfer Learning in Bandits from Unknown Adaptive Policies: Problem-Dependent Lower and Upper Bounds

The paper investigates transfer learning in stochastic multi‑armed bandits when historical data come from an unknown adaptive policy. It establishes asymptotic problem‑dependent lower bounds and introduces the KL‑UCB‑Transfer algorithm, which combines online and historical data to achieve logarithmic regret with an improved constant under certain mean‑gap conditions. The study also relaxes the source‑target discrepancy assumption to a one‑sided condition, demonstrating that logarithmic regret can still be achieved under misspecification and identifying regimes of improvement, degradation, or loss of guarantee.

By Adrien Prevost, Timothee Mathieu, Waris Radji, Odalric-Ambrym Maillard