# Borda Regret Minimization for Generalized Linear Dueling Bandits

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 47 references that are in the map.
- First posted on arXiv 15 Mar 2023.

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

- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba](https://mlsanity.com/paper/1803.02349/) (2018)
- [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)
- [Algorithms for multi-armed bandit problems](https://mlsanity.com/paper/1402.6028/) (2014)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [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)
- [Meta-Prod2Vec - Product Embeddings Using Side-Information for Recommendation](https://mlsanity.com/paper/1607.07326/) (2016)
- [Sparse Dueling Bandits](https://mlsanity.com/paper/1502.00133/) (2015)
- [Approximate Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1801.01253/) (2018)
- [Maximum Selection and Ranking under Noisy Comparisons](https://mlsanity.com/paper/1705.05366/) (2017)
- [Copeland Dueling Bandit Problem: Regret Lower Bound, Optimal Algorithm, and Computationally Efficient Algorithm](https://mlsanity.com/paper/1605.01677/) (2016)
- [On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons](https://mlsanity.com/paper/1909.03194/) (2019)
- [Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons](https://mlsanity.com/paper/2110.04136/) (2021)

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

- [Self-Play Preference Optimization for Language Model Alignment](https://mlsanity.com/paper/2405.00675/) (2024)
- [Making RL with Preference-based Feedback Efficient via Randomization](https://mlsanity.com/paper/2310.14554/) (2023)
- [Reinforcement Learning from Human Feedback with Active Queries](https://mlsanity.com/paper/2402.09401/) (2024)
- [Sharp Analysis for KL-Regularized Contextual Bandits and RLHF](https://mlsanity.com/paper/2411.04625/) (2024)
- [Feel-Good Thompson Sampling for Contextual Dueling Bandits](https://mlsanity.com/paper/2404.06013/) (2024)
- [Beyond Bradley-Terry Models: A General Preference Model for Language Model Alignment](https://mlsanity.com/paper/2410.02197/) (2024)
- [Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits](https://mlsanity.com/paper/2310.00968/) (2023)
- [Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback](https://mlsanity.com/paper/2404.10776/) (2024)
- [Active Preference Learning for Ordering Items In- and Out-of-sample](https://mlsanity.com/paper/2405.03059/) (2024)
- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)
- [Contextual Bandits and Imitation Learning via Preference-Based Active Queries](https://mlsanity.com/paper/2307.12926/) (2023)
- [Non-Stationary Dueling Bandits Under a Weighted Borda Criterion](https://mlsanity.com/paper/2403.12950/) (2024)
- [Reinforcement Learning from Adversarial Preferences in Tabular MDPs](https://mlsanity.com/paper/2507.11706/) (2025)
- [Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options](https://mlsanity.com/paper/2510.18713/) (2025)
- [Contextual bandits with entropy-based human feedback](https://mlsanity.com/paper/2502.08759/) (2025)
- [Thompson Sampling in Online RLHF with General Function Approximation](https://mlsanity.com/paper/2505.23927/) (2025)
- [Learning Kernel-Based MDPs from Episodic Preferential Feedback](https://mlsanity.com/paper/2605.23650/) (2026)

## Abstract (arXiv)

Dueling bandits are widely used to model preferential feedback prevalent in many applications such as recommendation systems and ranking. In this paper, we study the Borda regret minimization problem for dueling bandits, which aims to identify the item with the highest Borda score while minimizing the cumulative regret. We propose a rich class of generalized linear dueling bandit models, which cover many existing models. We first prove a regret lower bound of order Omega(d2/3 T2/3) for the Borda regret minimization problem, where d is the dimension of contextual vectors and T is the time horizon. To attain this lower bound, we propose an explore-then-commit type algorithm for the stochastic setting, which has a nearly matching regret upper bound tildeO(d2/3 T2/3). We also propose an EXP3-type algorithm for the adversarial linear setting, where the underlying model parameter can change at each round. Our algorithm achieves an tildeO(d2/3 T2/3) regret, which is also optimal. Empirical evaluations on both synthetic data and a simulated real-world environment are conducted to corroborate our theoretical analysis.