aiqbench analysis
This research introduces a novel algorithm for stochastic contextual bandits that achieves fast best-in-class regret rates without relying on realizability assumptions. By minimizing a pessimistic objective with variance penalties and leveraging entropy assumptions, the method delivers polylogarithmic convergence in parametric settings. The theoretical advance is significant for agnostic learning scenarios where model restrictions are absent or too strong.
Fast Best-in-Class Regret for Contextual Bandits
arXiv:2510.15483v3 Announce Type: replace-cross 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\"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.
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.
Machine Learning (stat.ML); Machine Learning (cs.LG)
arXiv:2510.15483 [stat.ML]
(or arXiv:2510.15483v3 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2510.15483 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 236 words
Related coverage
The Surrogate Is Not the Reward: Post-Surrogate Primary-Outcome Acquisition in Contextual Bandits
arXiv · Oct 6, 2026
State of the Field: AI for Epistemics and Coordination
LessWrong · Oct 2, 2026
Vanilla Policy Optimization Is Both Optimal and Differentially Private for Stochastic Contextual Bandits
arXiv · Sep 30, 2026
[AINews] not much happened today
Latent Space · Sep 10, 2026