# Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 37 references that are in the map.
- First posted on arXiv 6 Nov 2021.

## Builds on (most cited first, 22 of 22)

- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Preference-based Online Learning with Dueling Bandits: A Survey](https://mlsanity.com/paper/1807.11398/) (2018)
- [Contextual Dueling Bandits](https://mlsanity.com/paper/1502.06362/) (2015)
- [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)
- [Reducing Dueling Bandits to Cardinal Bandits](https://mlsanity.com/paper/1405.3396/) (2014)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem](https://mlsanity.com/paper/1506.02550/) (2015)
- [Double Thompson Sampling for Dueling Bandits](https://mlsanity.com/paper/1604.07101/) (2016)
- [Copeland Dueling Bandits](https://mlsanity.com/paper/1506.00312/) (2015)
- [Multi-dueling Bandits with Dependent Arms](https://mlsanity.com/paper/1705.00253/) (2017)
- [Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions](https://mlsanity.com/paper/2106.02436/) (2021)
- [Adversarial Dueling Bandits](https://mlsanity.com/paper/2010.14563/) (2020)
- [A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits](https://mlsanity.com/paper/1601.03855/) (2016)
- [Best arm identification in multi-armed bandits with delayed feedback](https://mlsanity.com/paper/1803.10937/) (2018)
- [PAC Battling Bandits in the Plackett-Luce Model](https://mlsanity.com/paper/1808.04008/) (2018)
- [Active Ranking with Subset-wise Preferences](https://mlsanity.com/paper/1810.10321/) (2018)
- [Combinatorial Bandits with Relative Feedback](https://mlsanity.com/paper/1903.00543/) (2019)
- [PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Bounds](https://mlsanity.com/paper/1806.02970/) (2018)
- [Multi-Dueling Bandits and Their Application to Online Ranker Evaluation](https://mlsanity.com/paper/1608.06253/) (2016)
- [Best-item Learning in Random Utility Models with Subset Choices](https://mlsanity.com/paper/2002.07994/) (2020)

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

- [ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2210.14322/) (2022)
- [Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2202.00935/) (2022)
- [Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences](https://mlsanity.com/paper/2202.06694/) (2022)
- [When Can We Track Significant Preference Shifts in Dueling Bandits?](https://mlsanity.com/paper/2302.06595/) (2023)
- [Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resources](https://mlsanity.com/paper/2312.17229/) (2023)
- [Non-Stationary Dueling Bandits Under a Weighted Borda Criterion](https://mlsanity.com/paper/2403.12950/) (2024)
- [DP-Dueling: Learning from Preference Feedback without Compromising User Privacy](https://mlsanity.com/paper/2403.15045/) (2024)
- [Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits](https://mlsanity.com/paper/2509.15073/) (2025)
- [Identifying Copeland Winners in Dueling Bandits with Indifferences](https://mlsanity.com/paper/2310.00750/) (2023)

## Abstract (arXiv)

We study the problem of dynamic regret minimization in K-armed Dueling Bandits under non-stationary or time varying preferences. This is an online learning setup where the agent chooses a pair of items at each round and observes only a relative binary `win-loss' feedback for this pair, sampled from an underlying preference matrix at that round. We first study the problem of static-regret minimization for adversarial preference sequences and design an efficient algorithm with O(√KT) high probability regret. We next use similar algorithmic ideas to propose an efficient and provably optimal algorithm for dynamic-regret minimization under two notions of non-stationarities. In particular, we establish tO(√SKT) and tO(VT1/3K1/3T2/3) dynamic-regret guarantees, S being the total number of `effective-switches' in the underlying preference relations and VT being a measure of `continuous-variation' non-stationarity. The complexity of these problems have not been studied prior to this work despite the practicability of non-stationary environments in real world systems. We justify the optimality of our algorithms by proving matching lower bound guarantees under both the above-mentioned notions of non-stationarities. Finally, we corroborate our results with extensive simulations and compare the efficacy of our algorithms over state-of-the-art baselines.