Smoothness-Adaptive Contextual Bandits

Yonatan Gur (), Ahmadreza Momeni () and Stefan Wager ()
Additional contact information
Yonatan Gur: Graduate School of Business, Stanford University, Stanford, California 94305; Electrical Engineering Department, Stanford University, Stanford, California 94305
Ahmadreza Momeni: Electrical Engineering Department, Stanford University, Stanford, California 94305
Stefan Wager: Graduate School of Business, Stanford University, Stanford, California 94305

Operations Research, 2022, vol. 70, issue 6, 3198-3216

Abstract: We study a nonparametric multiarmed bandit problem with stochastic covariates, where a key complexity driver is the smoothness of payoff functions with respect to covariates. Previous studies have focused on deriving minimax-optimal algorithms in cases where it is a priori known how smooth the payoff functions are. In practice, however, the smoothness of payoff functions is typically not known in advance, and misspecification of smoothness may severely deteriorate the performance of existing methods. In this work, we consider a framework where the smoothness of payoff functions is not known and study when and how algorithms may adapt to unknown smoothness. First, we establish that designing algorithms that adapt to unknown smoothness of payoff functions is, in general, impossible. However, under a self-similarity condition (which does not reduce the minimax complexity of the dynamic optimization problem at hand), we establish that adapting to unknown smoothness is possible and further devise a general policy for achieving smoothness-adaptive performance. Our policy infers the smoothness of payoffs throughout the decision-making process while leveraging the structure of off-the-shelf nonadaptive policies. We establish that for problem settings with either differentiable or nondifferentiable payoff functions, this policy matches (up to a logarithmic scale) the regret rate that is achievable when the smoothness of payoffs is known a priori.

Keywords: Machine Learning and Data Science; contextual multi-armed bandits; Hölder smoothness; self-similarity; nonparametric confidence intervals; nonparametric estimation; experiment design (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.2215 (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:3198-3216

Access Statistics for this article

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