# Tracking Most Significant Arm Switches in Bandits arXiv: https://arxiv.org/abs/2112.13838 · HTML: https://mlsanity.com/paper/2112.13838/ ## Key facts - Cited by 27 papers in the map (data through 14 Oct 2026). - Builds on 12 of its 30 references that are in the map. - First posted on arXiv 27 Dec 2021. ## Builds on (most cited first, 12 of 12) - [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019) - [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021) - [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018) - [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019) - [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017) - [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016) - [The Pareto Frontier of model selection for general Contextual Bandits](https://mlsanity.com/paper/2110.13282/) (2021) - [On Abruptly-Changing and Slowly-Varying Multiarmed Bandit Problems](https://mlsanity.com/paper/1802.08380/) (2018) - [Open Problem: Model Selection for Contextual Bandits](https://mlsanity.com/paper/2006.10940/) (2020) - [Generalized non-stationary bandits](https://mlsanity.com/paper/2102.00725/) (2021) - [Distribution-dependent and Time-uniform Bounds for Piecewise i.i.d Bandits](https://mlsanity.com/paper/1905.13159/) (2019) - [On Slowly-varying Non-stationary Bandits](https://mlsanity.com/paper/2110.12916/) (2021) ## Built on by (most cited first, 27 of 27) - [A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits](https://mlsanity.com/paper/2201.06532/) (2022) - [An Information-Theoretic Analysis of Nonstationary Bandit Learning](https://mlsanity.com/paper/2302.04452/) (2023) - [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023) - [A Stability Principle for Learning under Non-Stationarity](https://mlsanity.com/paper/2310.18304/) (2023) - [Adaptive Experimentation in the Presence of Exogenous Nonstationary Variation](https://mlsanity.com/paper/2202.09036/) (2022) - [Non-stationary Bandits and Meta-Learning with a Small Set of Optimal Arms](https://mlsanity.com/paper/2202.13001/) (2022) - [ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2210.14322/) (2022) - [Event-Triggered Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2208.10790/) (2022) - [When Can We Track Significant Preference Shifts in Dueling Bandits?](https://mlsanity.com/paper/2302.06595/) (2023) - [Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs](https://mlsanity.com/paper/2601.01069/) (2026) - [Discounted Thompson Sampling for Non-Stationary Bandit Problems](https://mlsanity.com/paper/2305.10718/) (2023) - [Adaptive Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2407.08654/) (2024) - [Non-Stationary Lipschitz Bandits](https://mlsanity.com/paper/2505.18871/) (2025) - [A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity](https://mlsanity.com/paper/2307.15154/) (2023) - [Variance-Dependent Regret Bounds for Non-stationary Linear Bandits](https://mlsanity.com/paper/2403.10732/) (2024) - [Non-Stationary Dueling Bandits Under a Weighted Borda Criterion](https://mlsanity.com/paper/2403.12950/) (2024) - [Adversarial Bandits against Arbitrary Strategies](https://mlsanity.com/paper/2205.14839/) (2022) - [MNL-Bandit in non-stationary environments](https://mlsanity.com/paper/2303.02504/) (2023) - [Tracking Most Significant Shifts in Infinite-Armed Bandits](https://mlsanity.com/paper/2502.00108/) (2025) - [Non-stationary Bandit Convex Optimization: A Comprehensive Study](https://mlsanity.com/paper/2506.02980/) (2025) - [Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Losses](https://mlsanity.com/paper/2602.07418/) (2026) - [Revisiting Weighted Strategy for Non-stationary Parametric Bandits](https://mlsanity.com/paper/2303.02691/) (2023) - [Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Bandits](https://mlsanity.com/paper/2410.05734/) (2024) - [A Modularized Framework for Piecewise-Stationary Restless Bandits](https://mlsanity.com/paper/2604.10177/) (2026) - [On Non-Stationary Dynamic Pricing: Adaptivity and Optimality](https://mlsanity.com/paper/2607.24115/) (2026) - [Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary](https://mlsanity.com/paper/2609.13547/) (2026) - [Future Information-Directed Sampling for Bayesian Nonstationary Bandits](https://mlsanity.com/paper/2609.33981/) (2026) ## Abstract (arXiv) In bandit with distribution shifts, one aims to automatically adapt to unknown changes in reward distribution, and restart exploration when necessary. While this problem has been studied for many years, a recent breakthrough of Auer et al. (2018, 2019) provides the first adaptive procedure to guarantee an optimal (dynamic) regret √LT, for T rounds, and an unknown number L of changes. However, while this rate is tight in the worst case, it remained open whether faster rates are possible, without prior knowledge, if few changes in distribution are actually severe. To resolve this question, we propose a new notion of significant shift, which only counts very severe changes that clearly necessitate a restart: roughly, these are changes involving not only best arm switches, but also involving large aggregate differences in reward overtime. Thus, our resulting procedure adaptively achieves rates always faster (sometimes significantly) than O(√ST), where Sll L only counts best arm switches, while at the same time, always faster than the optimal O(V^frac13T^frac23) when expressed in terms of total variation V (which aggregates differences overtime). Our results are expressed in enough generality to also capture non-stochastic adversarial settings.