# Non-Stationary Dueling Bandits Under a Weighted Borda Criterion

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 57 references that are in the map.
- First posted on arXiv 19 Mar 2024.

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

- [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)
- [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)
- [Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem](https://mlsanity.com/paper/1506.02550/) (2015)
- [Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards](https://mlsanity.com/paper/1405.3316/) (2014)
- [Double Thompson Sampling for Dueling Bandits](https://mlsanity.com/paper/1604.07101/) (2016)
- [Copeland Dueling Bandits](https://mlsanity.com/paper/1506.00312/) (2015)
- [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)
- [Sparse Dueling Bandits](https://mlsanity.com/paper/1502.00133/) (2015)
- [A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits](https://mlsanity.com/paper/2201.06532/) (2022)
- [Tracking Most Significant Arm Switches in Bandits](https://mlsanity.com/paper/2112.13838/) (2021)
- [Approximate Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1801.01253/) (2018)
- [Borda Regret Minimization for Generalized Linear Dueling Bandits](https://mlsanity.com/paper/2303.08816/) (2023)
- [Copeland Dueling Bandit Problem: Regret Lower Bound, Optimal Algorithm, and Computationally Efficient Algorithm](https://mlsanity.com/paper/1605.01677/) (2016)
- [Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2301.12366/) (2023)
- [Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2111.03917/) (2021)
- [ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2210.14322/) (2022)
- [Factored Bandits](https://mlsanity.com/paper/1807.01488/) (2018)
- [On Slowly-varying Non-stationary Bandits](https://mlsanity.com/paper/2110.12916/) (2021)
- [Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2202.00935/) (2022)
- [Finding Optimal Arms in Non-stochastic Combinatorial Bandits with Semi-bandit Feedback and Finite Budget](https://mlsanity.com/paper/2202.04487/) (2022)
- [When Can We Track Significant Preference Shifts in Dueling Bandits?](https://mlsanity.com/paper/2302.06595/) (2023)
- [Duelling Bandits with Weak Regret in Adversarial Environments](https://mlsanity.com/paper/1812.04152/) (2018)

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

- [Non-Stationary Lipschitz Bandits](https://mlsanity.com/paper/2505.18871/) (2025)
- [Reinforcement Learning from Adversarial Preferences in Tabular MDPs](https://mlsanity.com/paper/2507.11706/) (2025)

## Abstract (arXiv)

In K-armed dueling bandits, the learner receives preference feedback between arms, and the regret of an arm is defined in terms of its suboptimality to a textitwinner arm. The textitnon-stationary variant of the problem, motivated by concerns of changing user preferences, has received recent interest (Saha and Gupta, 2022; Buening and Saha, 2023; Suk and Agarwal, 2023). The goal here is to design algorithms with low em dynamic regret, ideally without foreknowledge of the amount of change. The notion of regret here is tied to a notion of winner arm, most typically taken to be a so-called Condorcet winner or a Borda winner. However, the aforementioned results mostly focus on the Condorcet winner. In comparison, the Borda version of this problem has received less attention which is the focus of this work. We establish the first optimal and adaptive dynamic regret upper bound tildeO(tildeL1/3 K1/3 T2/3 ), where tildeL is the unknown number of significant Borda winner switches. We also introduce a novel textitweighted Borda score framework which generalizes both the Borda and Condorcet problems. This framework surprisingly allows a Borda-style regret analysis of the Condorcet problem and establishes improved bounds over the theoretical state-of-art in regimes with a large number of arms or many spurious changes in Condorcet winner. Such a generalization was not known and could be of independent interest.