mlsanityData to 7 Oct 2026

When Can We Track Significant Preference Shifts in Dueling Bandits?

arXiv 2302.06595 ↗First posted 13 Feb 2023cs.LG stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

The K-armed dueling bandits problem, where the feedback is in the form of noisy pairwise preferences, has been widely studied due its applications in information retrieval, recommendation systems, etc. Motivated by concerns that user preferences/tastes can evolve over time, we consider the problem of dueling bandits with distribution shifts. Specifically, we study the recent notion of significant shifts (Suk and Kpotufe, 2022), and ask whether one can design an adaptive algorithm for the dueling problem with O(√KtildeLT) dynamic regret, where tildeL is the (unknown) number of significant shifts in preferences. We show that the answer to this question depends on the properties of underlying preference distributions. Firstly, we give an impossibility result that rules out any algorithm with O(√KtildeLT) dynamic regret under the well-studied Condorcet and SST classes of preference distributions. Secondly, we show that SST cap STI is the largest amongst popular classes of preference distributions where it is possible to design such an algorithm. Overall, our results provides an almost complete resolution of the above question for the hierarchy of distribution classes.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 18 of its 43 references that are in the map. First posted on arXiv 13 Feb 2023.

Builds on

18 of 43 references.

References · 18

  1. 2015Contextual Dueling Banditscited by 101
  2. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  3. 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
  4. 2014Reducing Dueling Bandits to Cardinal Banditscited by 62
  5. 2015Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problemcited by 51
  6. 2016Double Thompson Sampling for Dueling Banditscited by 42
  7. 2015Copeland Dueling Banditscited by 36
  8. 2020Adversarial Dueling Banditscited by 33
  9. 2016A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Banditscited by 31
  10. 2015Sparse Dueling Banditscited by 29
  11. 2022A New Look at Dynamic Regret for Non-Stationary Stochastic Banditscited by 28
  12. 2021Tracking Most Significant Arm Switches in Banditscited by 27
6 more
  1. 2016Copeland Dueling Bandit Problem: Regret Lower Bound, Optimal Algorithm, and Computationally Efficient Algorithmcited by 16
  2. 2017Dueling Bandits With Weak Regretcited by 15
  3. 2022Batched Dueling Banditscited by 10
  4. 2021Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Banditscited by 9
  5. 2022ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Banditscited by 8
  6. 2022Non-Stationary Dueling Banditscited by 7

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 1; 2025: 3.

5 papers.

  1. 2025Non-Stationary Lipschitz Banditscited by 3
  2. 2024Non-Stationary Dueling Bandits Under a Weighted Borda Criterioncited by 2
  3. 2025Tracking Most Significant Shifts in Infinite-Armed Banditscited by 1
  4. 2025Constrained Feedback Learning for Non-Stationary Multi-Armed Banditscited by 1
  5. 2023Identifying Copeland Winners in Dueling Bandits with Indifferencescited by 0