The multi-armed bandit problem with covariates
  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.
