# Self-Tuning Bandits over Unknown Covariate-Shifts

arXiv: https://arxiv.org/abs/2007.08584 · HTML: https://mlsanity.com/paper/2007.08584/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2020.

## Built on by (most cited first, 12 of 12)

- [Transfer Learning for Contextual Multi-armed Bandits](https://mlsanity.com/paper/2211.12612/) (2022)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [Adversarial Rewards in Universal Learning for Contextual Bandits](https://mlsanity.com/paper/2302.07186/) (2023)
- [Optimal Adaptive Experimental Design for Estimating Treatment Effect](https://mlsanity.com/paper/2410.05552/) (2024)
- [Adaptive Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2407.08654/) (2024)
- [Batched Nonparametric Contextual Bandits](https://mlsanity.com/paper/2402.17732/) (2024)
- [Hypothesis Transfer in Bandits by Weighted Models](https://mlsanity.com/paper/2211.07387/) (2022)
- [Contextual Bandits and Optimistically Universal Learning](https://mlsanity.com/paper/2301.00241/) (2022)
- [An adaptive transfer learning perspective on classification in non-stationary environments](https://mlsanity.com/paper/2405.18091/) (2024)
- [Locally Private Nonparametric Contextual Multi-armed Bandits](https://mlsanity.com/paper/2503.08098/) (2025)
- [Vector preference-based contextual bandits under distributional shifts](https://mlsanity.com/paper/2508.15966/) (2025)
- [The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margin](https://mlsanity.com/paper/2511.03708/) (2025)

## Abstract (arXiv)

Bandits with covariates, a.k.a. contextual bandits, address situations where optimal actions (or arms) at a given time t, depend on a context xt, 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.