Self-Tuning Bandits over Unknown Covariate-Shifts
arXiv:2007.08584
Abstract
Bandits with covariates, a.k.a. contextual bandits, address situations where optimal actions (or arms) at a given time , depend on a context , e.g., a new patient's medical history, a consumer's past purchases. While it is understood that the distribution of contexts might change over time, e.g., due to seasonalities, or deployment to new environments, the bulk of studies concern the most adversarial such changes, resulting in regret bounds that are often worst-case in nature. Covariate-shift on the other hand has been considered in classification as a middle-ground formalism that can capture mild to relatively severe changes in distributions. We consider nonparametric bandits under such middle-ground scenarios, and derive new regret bounds that tightly capture a continuum of changes in context distribution. Furthermore, we show that these rates can be adaptively attained without knowledge of the time of shift nor the amount of shift.
References in corpus (12)
- Fast learning rates for plug-in classifiers
- Contextual Bandits with Similarity Information
- Efficient Contextual Bandits in Non-stationary Worlds
- Nonparametric Bandits with Covariates
- Learning Contextual Bandits in a Non-stationary Environment
- BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits
- Sequential Transfer in Multi-armed Bandit with Finite Set of Models
- An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits
- A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
- Hedging the Drift: Learning to Optimize under Non-Stationarity
- Nonparametric Stochastic Contextual Bandits
- The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates