mlsanityData to 7 Oct 2026

ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits

arXiv 2210.14322 ↗First posted 25 Oct 2022cs.LG stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

We study the problem of non-stationary dueling bandits and provide the first adaptive dynamic regret algorithm for this problem. The only two existing attempts in this line of work fall short across multiple dimensions, including pessimistic measures of non-stationary complexity and non-adaptive parameter tuning that requires knowledge of the number of preference changes. We develop an elimination-based rescheduling algorithm to overcome these shortcomings and show a near-optimal tildeO(√S^textttCW T) dynamic regret bound, where S^textttCW is the number of times the Condorcet winner changes in T rounds. This yields the first near-optimal dynamic regret algorithm for unknown S^textttCW. We further study other related notions of non-stationarity for which we also prove near-optimal dynamic regret guarantees under additional assumptions on the underlying preference model.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 28 of its 53 references that are in the map. First posted on arXiv 25 Oct 2022.

Builds on

28 of 53 references.

References · 28

  1. 2013Non-stationary Stochastic Optimizationcited by 173
  2. 2015Contextual Dueling Banditscited by 101
  3. 2018Preference-based Online Learning with Dueling Bandits: A Surveycited by 100
  4. 2019Weighted Linear Bandits for Non-Stationary Environmentscited by 84
  5. 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
  6. 2014Reducing Dueling Bandits to Cardinal Banditscited by 62
  7. 2017Efficient Contextual Bandits in Non-stationary Worldscited by 62
  8. 2015Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problemcited by 51
  9. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  10. 2016Double Thompson Sampling for Dueling Banditscited by 42
  11. 2015Copeland Dueling Banditscited by 36
  12. 2017Multi-dueling Bandits with Dependent Armscited by 35
16 more
  1. 2020Adversarial Dueling Banditscited by 33
  2. 2016A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Banditscited by 31
  3. 2022A New Look at Dynamic Regret for Non-Stationary Stochastic Banditscited by 28
  4. 2018PAC Battling Bandits in the Plackett-Luce Modelcited by 27
  5. 2021Tracking Most Significant Arm Switches in Banditscited by 27
  6. 2018Learning Contextual Bandits in a Non-stationary Environmentcited by 26
  7. 2020Algorithms for Non-Stationary Generalized Linear Banditscited by 23
  8. 2019Combinatorial Bandits with Relative Feedbackcited by 19
  9. 2022Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Banditscited by 11
  10. 2019From PAC to Instance-Optimal Sample Complexity in the Plackett-Luce Modelcited by 9
  11. 2021Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Banditscited by 9
  12. 2022Non-Stationary Dueling Banditscited by 7
  13. 2020Best-item Learning in Random Utility Models with Subset Choicescited by 6
  14. 2021Dueling Bandits with Adversarial Sleepingcited by 5
  15. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  16. 2013Preference Elicitation For General Random Utility Modelscited by 3

Built on by

Cited by year

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

8 papers.

  1. 2023When Can We Track Significant Preference Shifts in Dueling Bandits?cited by 5
  2. 2023Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resourcescited by 3
  3. 2025Non-Stationary Lipschitz Banditscited by 3
  4. 2024Non-Stationary Dueling Bandits Under a Weighted Borda Criterioncited by 2
  5. 2024DP-Dueling: Learning from Preference Feedback without Compromising User Privacycited by 1
  6. 2025Tracking Most Significant Shifts in Infinite-Armed Banditscited by 1
  7. 2025Constrained Feedback Learning for Non-Stationary Multi-Armed Banditscited by 1
  8. 2023Identifying Copeland Winners in Dueling Bandits with Indifferencescited by 0