Smoothness-Adaptive Contextual Bandits

Understand

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.