Nonparametric Bandits with Covariates

By Philippe Rigollet, Assaf J. Zeevi. 2010

118 citations recorded by the source corpus.

We consider a bandit problem which involves sequential sampling from two populations (arms). Each arm produces a noisy reward realization which depends on an observable random covariate. The goal is to maximize cumulative expected reward. We derive general lower bounds on the performance of any admissible policy, and develop an algorithm whose performance achieves the order of said lower bound up to logarithmic terms. This is done by decomposing the global problem into suitably "localized" bandit problems. Proofs blend ideas from nonparametric statistics and traditional methods used in the bandit literature.

Subfields: Artificial Intelligence, Management Science and Operations Research, Marketing

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

In Marketing

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.”
Semiconvex Regression for Metamodeling-Based Optimization (2014, methodology): “Estimation methods include linear combinations of basis functions [44], discretization the state space [56], random histograms, nearest neighbors [76] or adaptive partitioning [66].”
Contextual Bandits with Similarity Information (2009, methodology): “With this trick in mind, we will assume ﬁxed time horizon throughout this paper.”
On the Fundamental Limits of Adaptive Sensing (2011, background): “ results from [29] to establish a bound on the minimax rate for binary classication (see the references therein for additional literature on active learning). Other examples include the recent paper [26], which derives lower bounds for bandit problems, and [24] which develops an information theoreti”
Exploiting the Natural Exploration In Contextual Bandits (2017, background): “For example, [Sli14, PR + 13, RZ10] prove general regret bounds where the arm rewards are given by any smooth, non-parametric functions of the contexts.”
Budgeted Learning for Developing Personalized Treatment (2014, background): “subgroups or biomarker profiles) have been studied under the name of contexual bandits or bandit with covariates, [8], [9].”
Offline Multi-Action Policy Learning: Generalization and Optimization (2018, background): “First, the AIPW estimators (Robins et al. (1994)), sometimes also called doubly robust estimators, are a well-known family of estimators that are widely used in the literature on the estimation of causal effects. In particular, doubly robustness refers to the following property of estimators: a doub”
The multi-armed bandit problem with covariates (2011, methodology): “Such questions were partially addressed in Rigollet and Zeevi (2010) where near-optimal bounds on the regret are proved in the case of a two-armed bandit problem under only two assumptions on the underlying functional form that governs the arms’ responses.”
Online Decision Making with High-Dimensional Covariates (2020, unknown): “For example, Slivkins (2014), Perchet et al. (2013), Rigollet and Zeevi (2010) prove regret bounds where the arm rewards are smooth, non-parametric functions of the contexts, Langford and Zhang (2008) considers a practical epoch-greedy algorithm whose regret scales with the complexity of the…”