The multi-armed bandit problem with covariates

Abstract

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.

Published in at http://dx.doi.org/10.1214/13-AOS1101 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Fast learning rates for plug-in classifiers
• Contextual Bandits with Similarity Information
• Woodroofe's one-armed bandit problem revisited

Cited by in corpus (8)

• Batched bandit problems
• Ranking and Selection with Covariates for Personalized Decision Making
• Statistical Inference for Online Decision-Making: In a Contextual Bandit Setting
• Efficient Learning for Clustering and Optimizing Context-Dependent Designs
• Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneity
• An adaptive multiclass nearest neighbor classifier
• Functional Sequential Treatment Allocation with Covariates
• Maximal Objectives in the Multi-armed Bandit with Applications