Smoothness-Adaptive Contextual Bandits
  We study a non-parametric multi-armed 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 non-adaptive policies. We establish that for problem settings
with either differentiable or non-differentiable 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.
