mlsanityData to 7 Oct 2026

Tracking Most Significant Shifts in Nonparametric Contextual Bandits

arXiv 2307.05341 ↗First posted 11 Jul 2023stat.ML cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

We study nonparametric contextual bandits where Lipschitz mean reward functions may change over time. We first establish the minimax dynamic regret rate in this less understood setting in terms of number of changes L and total-variation V, both capturing all changes in distribution over context space, and argue that state-of-the-art procedures are suboptimal in this setting. Next, we tend to the question of an adaptivity for this setting, i.e. achieving the minimax rate without knowledge of L or V. Quite importantly, we posit that the bandit problem, viewed locally at a given context Xt, should not be affected by reward changes in other parts of context space cal X. We therefore propose a notion of change, which we term experienced significant shifts, that better accounts for locality, and thus counts considerably less changes than L and V. Furthermore, similar to recent work on non-stationary MAB (Suk & Kpotufe, 2022), experienced significant shifts only count the most significant changes in mean rewards, e.g., severe best-arm changes relevant to observed contexts. Our main result is to show that this more tolerant notion of change can in fact be adapted to.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 34 of its 58 references that are in the map. First posted on arXiv 11 Jul 2023.

Builds on

34 of 58 references.

References · 34

  1. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  2. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  3. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 114
  4. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  5. 2018Practical Contextual Bandits with Regression Oraclescited by 92
  6. 2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 75
  7. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  8. 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
  9. 2017Efficient Contextual Bandits in Non-stationary Worldscited by 62
  10. 2018Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Banditcited by 49
  11. 2017A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problemcited by 48
  12. 2019Hedging the Drift: Learning to Optimize under Non-Stationaritycited by 46
22 more
  1. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  2. 2019Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adaptingcited by 42
  3. 2014Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewardscited by 41
  4. 2019Variational Regret Bounds for Reinforcement Learningcited by 32
  5. 2020Dynamic Regret of Policy Optimization in Non-stationary Environmentscited by 32
  6. 2020A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescited by 32
  7. 2018A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitionscited by 29
  8. 2022A New Look at Dynamic Regret for Non-Stationary Stochastic Banditscited by 28
  9. 2021Tracking Most Significant Arm Switches in Banditscited by 27
  10. 2018Learning Contextual Bandits in a Non-stationary Environmentcited by 26
  11. 2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
  12. 2019Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimescited by 25
  13. 2022Transfer Learning for Contextual Multi-armed Banditscited by 24
  14. 2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
  15. 2018Nonparametric Stochastic Contextual Banditscited by 17
  16. 2018The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariatescited by 16
  17. 2018On Abruptly-Changing and Slowly-Varying Multiarmed Bandit Problemscited by 15
  18. 2019Randomized Allocation with Nonparametric Estimation for Contextual Multi-Armed Bandits with Delayed Rewardscited by 15
  19. 2019Smoothness-Adaptive Contextual Banditscited by 15
  20. 2020Self-Tuning Bandits over Unknown Covariate-Shiftscited by 12
  21. 2019Distribution-dependent and Time-uniform Bounds for Piecewise i.i.d Banditscited by 7
  22. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 4; 2025: 4; 2026: 2.

10 papers.

  1. 2024Contextual Bandits for Unbounded Context Distributionscited by 8
  2. 2024Adaptive Smooth Non-Stationary Banditscited by 4
  3. 2024Batched Nonparametric Contextual Banditscited by 3
  4. 2025Non-Stationary Lipschitz Banditscited by 3
  5. 2025Tracking Most Significant Shifts in Infinite-Armed Banditscited by 1
  6. 2025Constrained Feedback Learning for Non-Stationary Multi-Armed Banditscited by 1
  7. 2026Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Lossescited by 1
  8. 2024Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Banditscited by 0
  9. 2025Learn to Bid as a Price-Maker Wind Power Producercited by 0
  10. 2026Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversarycited by 0