Fast Best-in-Class Regret for Contextual Bandits
Samuel Girard, Aurelien Bibaut, Arthur Gretton, Nathan Kallus, Houssam Zenati
stat.ML, cs.LG
Submitted: 2026-08-19
Updated: 2026-08-20
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study the problem of stochastic contextual bandits in the agnostic setting, where the goal is to compete with the best policy in a given class without assuming realizability or imposing model
Terminology
Abstract
We study the problem of stochastic contextual bandits in the agnostic setting, where the goal is to compete with the best policy in a given class without assuming realizability or imposing model restrictions on losses or rewards. In this work, we establish the first fast rate for regret relative to the best-in-class policy. Our proposed algorithm updates the policy at every round by minimizing a pessimistic objective, defined as a clipped inverse-propensity estimate of the policy value plus a variance penalty. By leveraging entropy assumptions on the policy class and a Hölderian error-bound condition (a generalization of the margin condition), we achieve fast best-in-class regret rates, including polylogarithmic rates in the parametric case. The analysis is driven by a sequential self-normalized maximal inequality for bounded martingale empirical processes, which yields uniform variance-adaptive confidence bounds and guarantees pessimism under adaptive data collection.
Sources
- Efficient Optimal Learning for Contextual Bandits
- Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
- Sequential Off-Policy Learning with Logarithmic Smoothing
- Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality
- Second Order Bounds for Contextual Bandits with Function Approximation
- Estimating means of bounded random variables by betting
- Policy Learning with Adaptively Collected Data
Related papers
- Behavior of prediction performance metrics with rare events
- Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
- A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
- Scalable Posterior Uncertainty for Flexible Density-Based Clustering
- Efficient quadratic entropy with distance sketches
- Embedding-Bias in Conditional Independence Testing