Smooth Contextual Bandits: Bridging the Parametric and Nondifferentiable Regret Regimes

Yichun Hu (), Nathan Kallus () and Xiaojie Mao ()
Additional contact information
Yichun Hu: Cornell University, New York, New York 10044
Nathan Kallus: Cornell University, New York, New York 10044
Xiaojie Mao: Tsinghua University, 100084 Beijing, China

Operations Research, 2022, vol. 70, issue 6, 3261-3281

Abstract: We study a nonparametric contextual bandit problem in which the expected reward functions belong to a Hölder class with smoothness parameter β . We show how this interpolates between two extremes that were previously studied in isolation: nondifferentiable bandits (β at most 1), with which rate-optimal regret is achieved by running separate noncontextual bandits in different context regions, and parametric-response bandits (infinite β ), with which rate-optimal regret can be achieved with minimal or no exploration because of infinite extrapolatability. We develop a novel algorithm that carefully adjusts to all smoothness settings, and we prove its regret is rate-optimal by establishing matching upper and lower bounds, recovering the existing results at the two extremes. In this sense, our work bridges the gap between the existing literature on parametric and nondifferentiable contextual bandit problems and between bandit algorithms that exclusively use global or local information, shedding light on the crucial interplay of complexity and regret in contextual bandits.

Keywords: Machine Learning and Data Science; contextual bandits; local polynomial regression; minimax regret; margin condition (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2237 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:6:p:3261-3281

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().