The multi-armed bandit problem with covariates

By Vianney Perchet, Philippe Rigollet. 2011

193 citations recorded by the source corpus.

We consider a multi-armed bandit problem in a setting where each arm produces a noisy reward realization which depends on an observable random covariate. As opposed to the traditional static multi-armed bandit problem, this setting allows for dynamically changing rewards that better describe applications where side information is available. We adopt a nonparametric model where the expected rewards are smooth functions of the covariate and where the hardness of the problem is captured by a margin parameter. To maximize the expected cumulative reward, we introduce a policy called Adaptively Binned Successive Elimination (abse) that adaptively decomposes the global problem into suitably “localized” static bandit problems. This policy constructs an adaptive partition using a variant of the Successive Elimination (se) policy. Our results include sharper regret bounds for the se policy in a static bandit problem and minimax optimal regret bounds for the abse policy in the dynamic problem.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Balanced Linear Contextual Bandits (2018, background): “, the general bounds of (Russo and Van Roy 2014), the bounds of (Rigollet and Zeevi 2010), (Perchet and Rigollet 2013), (Slivkins 2014) in the case of non-parametric function of arm rewards), has demonstrated successful applications (e.”
Estimation Considerations in Contextual Bandits (2017, neutral): “, the general bounds of [51], the bounds of [50, 49, 56] in the case of non-parametric function of arm rewards), has demonstrated successful applications (e.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “In fact, the core idea is more transparent when expressed in terms of gains, and so we turn to the gain version of the problem.”
Efficient Policy Learning (2017, neutral): “2Our setup, where we want to learn a policy based on already collected observational data, is in contrast to the online “contextual bandit” setup where the practitioner seeks to learn a decision rule while actively making treatment allocation decisions for incoming subjects (e.g., Agarwal et al., 20”
Bandit Algorithms (2020, unknown): “[1971], while a more modern text is by Peskir and Shiryaev [2006], which includes a proof of Theorem 35.”
Online Decision Making with High-Dimensional Covariates (2020, unknown): “For example, a marketing campaign may be considering a set of new promotions, or a clinical trial may be considering several uncertain treatments.”
An Asymptotically Optimal Multi-Armed Bandit Algorithm and Hyperparameter Optimization (2020, methodology): “In the literature, most researchers only considered a one-parameter exponential family (Perchet and Rigollet, 2013; Chan, 2019).”