# Fast Best-in-Class Regret for Contextual Bandits

arXiv: https://arxiv.org/abs/2510.15483 · HTML: https://mlsanity.com/paper/2510.15483/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 34 of its 77 references that are in the map.
- First posted on arXiv 17 Oct 2025.

## Builds on (most cited first, 30 of 34)

- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [OpenML Benchmarking Suites](https://mlsanity.com/paper/1708.03731/) (2017)
- [Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling](https://mlsanity.com/paper/1802.09127/) (2018)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Doubly Robust Policy Evaluation and Optimization](https://mlsanity.com/paper/1503.02834/) (2015)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Optimal and Adaptive Off-policy Evaluation in Contextual Bandits](https://mlsanity.com/paper/1612.01205/) (2016)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [Open Bandit Dataset and Pipeline: Towards Realistic and Reproducible Off-Policy Evaluation](https://mlsanity.com/paper/2008.07146/) (2020)
- [Offline Multi-Action Policy Learning: Generalization and Optimization](https://mlsanity.com/paper/1810.04778/) (2018)
- [A Contextual Bandit Bake-off](https://mlsanity.com/paper/1802.04064/) (2018)
- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [Balanced Policy Evaluation and Learning](https://mlsanity.com/paper/1705.07384/) (2017)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [Anytime-valid off-policy inference for contextual bandits](https://mlsanity.com/paper/2210.10768/) (2022)
- [Doubly Robust Distributionally Robust Off-Policy Evaluation and Learning](https://mlsanity.com/paper/2202.09667/) (2022)
- [Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality](https://mlsanity.com/paper/2212.09900/) (2022)
- [Optimal Off-Policy Evaluation from Multiple Logging Policies](https://mlsanity.com/paper/2010.11002/) (2020)
- [Semi-Parametric Efficient Policy Learning with Continuous Actions](https://mlsanity.com/paper/1905.10116/) (2019)
- [Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes](https://mlsanity.com/paper/1909.02553/) (2019)
- [Empirical entropy, minimax regret and minimax risk](https://mlsanity.com/paper/1308.1147/) (2013)
- [Policy Learning with Adaptively Collected Data](https://mlsanity.com/paper/2105.02344/) (2021)
- [Online learning with kernel losses](https://mlsanity.com/paper/1802.09732/) (2018)
- [Contextual bandits with surrogate losses: Margin bounds and efficient algorithms](https://mlsanity.com/paper/1806.10745/) (2018)
- [Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning](https://mlsanity.com/paper/2106.01723/) (2021)
- [Second Order Bounds for Contextual Bandits with Function Approximation](https://mlsanity.com/paper/2409.16197/) (2024)
- [Efficient online algorithms for fast-rate regret bounds under sparsity](https://mlsanity.com/paper/1805.09174/) (2018)

## Abstract (arXiv)

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"olderian 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.