Fast Best-in-Class Regret for Contextual Bandits

Samuel Girard, Aurélien Bibaut, Jill-Jênn Vie, Arthur Gretton, Nathan Kallus, Houssam Zenati
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:1695-1724, 2026.

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 propose \textit{Online Pessimistic Policy Learning} and 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. Our analysis is driven by a novel sequential self-normalized maximal inequality for bounded martingale empirical processes, which yields uniform variance-adaptive confidence bounds and guarantees pessimism under adaptive data collection.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-girard26a, title = {Fast Best-in-Class Regret for Contextual Bandits}, author = {Girard, Samuel and Bibaut, Aur\'{e}lien and Vie, Jill-J\^{e}nn and Gretton, Arthur and Kallus, Nathan and Zenati, Houssam}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {1695--1724}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/girard26a/girard26a.pdf}, url = {https://proceedings.mlr.press/v337/girard26a.html}, 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 propose \textit{Online Pessimistic Policy Learning} and 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. Our analysis is driven by a novel sequential self-normalized maximal inequality for bounded martingale empirical processes, which yields uniform variance-adaptive confidence bounds and guarantees pessimism under adaptive data collection.} }
Endnote
%0 Conference Paper %T Fast Best-in-Class Regret for Contextual Bandits %A Samuel Girard %A Aurélien Bibaut %A Jill-Jênn Vie %A Arthur Gretton %A Nathan Kallus %A Houssam Zenati %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-girard26a %I PMLR %P 1695--1724 %U https://proceedings.mlr.press/v337/girard26a.html %V 337 %X 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 propose \textit{Online Pessimistic Policy Learning} and 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. Our analysis is driven by a novel sequential self-normalized maximal inequality for bounded martingale empirical processes, which yields uniform variance-adaptive confidence bounds and guarantees pessimism under adaptive data collection.
APA
Girard, S., Bibaut, A., Vie, J., Gretton, A., Kallus, N. & Zenati, H.. (2026). Fast Best-in-Class Regret for Contextual Bandits. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:1695-1724 Available from https://proceedings.mlr.press/v337/girard26a.html.

Related Material