# Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 57 references that are in the map.
- First posted on arXiv 2 Oct 2023.

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

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [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)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem](https://mlsanity.com/paper/1506.02550/) (2015)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs](https://mlsanity.com/paper/2111.03289/) (2021)
- [Double Thompson Sampling for Dueling Bandits](https://mlsanity.com/paper/1604.07101/) (2016)
- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models](https://mlsanity.com/paper/2202.04593/) (2022)
- [Copeland Dueling Bandits](https://mlsanity.com/paper/1506.00312/) (2015)
- [Adversarial Dueling Bandits](https://mlsanity.com/paper/2010.14563/) (2020)
- [Sparse Dueling Bandits](https://mlsanity.com/paper/1502.00133/) (2015)
- [Regret Analysis for Continuous Dueling Bandit](https://mlsanity.com/paper/1711.07693/) (2017)
- [Approximate Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1801.01253/) (2018)
- [Efficient-UCBV: An Almost Optimal Algorithm using Variance Estimates](https://mlsanity.com/paper/1711.03591/) (2017)
- [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)
- [Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits](https://mlsanity.com/paper/2202.13603/) (2022)

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

- [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)
- [Optimal Design for Reward Modeling in RLHF](https://mlsanity.com/paper/2410.17055/) (2024)
- [ActiveDPO: Active Direct Preference Optimization for Sample-Efficient Alignment](https://mlsanity.com/paper/2505.19241/) (2025)
- [Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback](https://mlsanity.com/paper/2404.10776/) (2024)
- [How Does Variance Shape the Regret in Contextual Bandits?](https://mlsanity.com/paper/2410.12713/) (2024)
- [Neural Dueling Bandits: Preference-Based Optimization with Human Feedback](https://mlsanity.com/paper/2407.17112/) (2024)
- [LLM Routing with Dueling Feedback](https://mlsanity.com/paper/2510.00841/) (2025)
- [Active Preference Learning for Ordering Items In- and Out-of-sample](https://mlsanity.com/paper/2405.03059/) (2024)
- [Allocation Stability and Wald Inference under Variance-Aware UCB](https://mlsanity.com/paper/2412.08843/) (2024)
- [Active Human Feedback Collection via Neural Contextual Dueling Bandits](https://mlsanity.com/paper/2504.12016/) (2025)
- [Online Clustering of Dueling Bandits](https://mlsanity.com/paper/2502.02079/) (2025)
- [Learning from Imperfect Human Feedback: a Tale from Corruption-Robust Dueling](https://mlsanity.com/paper/2405.11204/) (2024)
- [Federated Linear Dueling Bandits](https://mlsanity.com/paper/2502.01085/) (2025)
- [Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration](https://mlsanity.com/paper/2506.01250/) (2025)
- [Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options](https://mlsanity.com/paper/2510.18713/) (2025)
- [Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/2511.02123/) (2025)
- [Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptions](https://mlsanity.com/paper/2604.22161/) (2026)
- [Learning to Attack: A Bandit Approach to Adversarial Context Poisoning](https://mlsanity.com/paper/2603.00567/) (2026)
- [Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptions](https://mlsanity.com/paper/2605.01752/) (2026)
- [On the Complexity of Preference-Based Bandits](https://mlsanity.com/paper/2609.39351/) (2026)

## Abstract (arXiv)

Dueling bandits is a prominent framework for decision-making involving preferential feedback, a valuable feature that fits various applications involving human interaction, such as ranking, information retrieval, and recommendation systems. While substantial efforts have been made to minimize the cumulative regret in dueling bandits, a notable gap in the current research is the absence of regret bounds that account for the inherent uncertainty in pairwise comparisons between the dueling arms. Intuitively, greater uncertainty suggests a higher level of difficulty in the problem. To bridge this gap, this paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM). We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound tilde Obig(d√sumt=1Tσt2 + dbig), where σt is the variance of the pairwise comparison in round t, d is the dimension of the context vectors, and T is the time horizon. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an tilde O(d) regret. We perform empirical experiments on synthetic data to confirm the advantage of our method over previous variance-agnostic algorithms.