mlsanityData to 7 Oct 2026

Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models

arXiv 2202.04593 ↗First posted 9 Feb 2022cs.LG stat.MLcited by 35

Not on the map. Why?

Abstract (arXiv)

We consider the regret minimization task in a dueling bandits problem with context information. In every round of the sequential decision problem, the learner makes a context-dependent selection of two choice alternatives (arms) to be compared with each other and receives feedback in the form of noisy preference information. We assume that the feedback process is determined by a linear stochastic transitivity model with contextualized utilities (CoLST), and the learner's task is to include the best arm (with highest latent context-dependent utility) in the duel. We propose a computationally efficient algorithm, textttCoLSTIM, which makes its choice based on imitating the feedback process using perturbed context-dependent utility estimates of the underlying CoLST model. If each arm is associated with a d-dimensional feature vector, we show that textttCoLSTIM achieves a regret of order tilde O( √dT) after T learning rounds. Additionally, we also establish the optimality of textttCoLSTIM by showing a lower bound for the weak regret that refines the existing average regret analysis. Our experiments demonstrate its superiority over state-of-art algorithms for special cases of CoLST models.

Key facts. Cited by 35 papers in the map (data through 7 Oct 2026). Builds on 16 of its 40 references that are in the map. First posted on arXiv 9 Feb 2022.

Builds on

16 of 40 references.

References · 16

  1. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  2. 2015Contextual Dueling Banditscited by 101
  3. 2018Preference-based Online Learning with Dueling Bandits: A Surveycited by 100
  4. 2017Preferential Bayesian Optimizationcited by 72
  5. 2014Reducing Dueling Bandits to Cardinal Banditscited by 62
  6. 2016Double Thompson Sampling for Dueling Banditscited by 42
  7. 2017Provably Optimal Algorithms for Generalized Linear Contextual Banditscited by 38
  8. 2017Multi-dueling Bandits with Dependent Armscited by 35
  9. 2020Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffscited by 25
  10. 2017Regret Analysis for Continuous Dueling Banditcited by 21
  11. 2019Old Dog Learns New Tricks: Randomized UCB for Bandit Problemscited by 21
  12. 2019Combinatorial Bandits with Relative Feedbackcited by 19
4 more
  1. 2016Multi-Dueling Bandits and Their Application to Online Ranker Evaluationcited by 16
  2. 2019Rank Aggregation via Heterogeneous Thurstone Preference Modelscited by 12
  3. 2019On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problemscited by 10
  4. 2019Preselection Banditscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 12; 2025: 12; 2026: 6.

35 papers.

Sort:

By area:

  1. 2023Making RL with Preference-based Feedback Efficient via Randomizationcited by 46
  2. 2024Reinforcement Learning from Human Feedback with Active Queriescited by 39
  3. 2024Prompt Optimization with Human Feedbackcited by 35
  4. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 23
  5. 2024Optimal Design for Reward Modeling in RLHFcited by 23
  6. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  7. 2023Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewardscited by 11
  8. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  9. 2025ActiveDPO: Active Direct Preference Optimization for Sample-Efficient Alignmentcited by 9
  10. 2024Neural Dueling Bandits: Preference-Based Optimization with Human Feedbackcited by 7
  11. 2024Active Preference Learning for Ordering Items In- and Out-of-samplecited by 6
  12. 2024Online Bandit Learning with Offline Preference Data for Improved RLHFcited by 6
23 more
  1. 2024Hybrid Preference Optimization for Alignment: Provably Faster Convergence Rates by Combining Offline Preferences with Online Explorationcited by 6
  2. 2025LLM Routing with Dueling Feedbackcited by 6
  3. 2024Conversational Dueling Bandits in Generalized Linear Modelscited by 5
  4. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  5. 2025Active Human Feedback Collection via Neural Contextual Dueling Banditscited by 4
  6. 2023Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resourcescited by 3
  7. 2024Stop Relying on No-Choice and Do not Repeat the Moves: Optimal, Efficient and Practical Algorithms for Assortment Optimizationcited by 3
  8. 2025Bayesian Optimization from Human Feedback: Near-Optimal Regret Boundscited by 3
  9. 2025FedPOB: Sample-Efficient Federated Prompt Optimization via Banditscited by 3
  10. 2025Federated Linear Dueling Banditscited by 2
  11. 2025Online Clustering of Dueling Banditscited by 2
  12. 2025Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Explorationcited by 2
  13. 2025Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Optionscited by 2
  14. 2024DP-Dueling: Learning from Preference Feedback without Compromising User Privacycited by 1
  15. 2025Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorizationcited by 1
  16. 2023Identifying Copeland Winners in Dueling Bandits with Indifferencescited by 0
  17. 2025Recycling History: Efficient Recommendations from Contextual Dueling Banditscited by 0
  18. 2025DT-PBO: an Interpretable Tree-based Surrogate Model for Preferential Bayesian Optimizationcited by 0
  19. 2026A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedbackcited by 0
  20. 2026Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptionscited by 0
  21. 2026Learning Kernel-Based MDPs from Episodic Preferential Feedbackcited by 0
  22. 2026Linear and Neural Dueling Bandits with Delayed Feedbackcited by 0
  23. 2026On the Complexity of Preference-Based Banditscited by 0