mlsanityData to 7 Oct 2026

Feel-Good Thompson Sampling for Contextual Dueling Bandits

arXiv 2404.06013 ↗First posted 9 Apr 2024cs.LG math.OC stat.MLcited by 23

Not on the map. Why?

Abstract (arXiv)

Contextual dueling bandits, where a learner compares two options based on context and receives feedback indicating which was preferred, extends classic dueling bandits by incorporating contextual information for decision-making and preference learning. Several algorithms based on the upper confidence bound (UCB) have been proposed for linear contextual dueling bandits. However, no algorithm based on posterior sampling has been developed in this setting, despite the empirical success observed in traditional contextual bandits. In this paper, we propose a Thompson sampling algorithm, named FGTS.CDB, for linear contextual dueling bandits. At the core of our algorithm is a new Feel-Good exploration term specifically tailored for dueling bandits. This term leverages the independence of the two selected arms, thereby avoiding a cross term in the analysis. We show that our algorithm achieves nearly minimax-optimal regret, i.e., tildeO(d√ T), where d is the model dimension and T is the time horizon. Finally, we evaluate our algorithm on synthetic data and observe that FGTS.CDB outperforms existing algorithms by a large margin.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). Builds on 26 of its 49 references that are in the map. First posted on arXiv 9 Apr 2024.

Builds on

26 of 49 references.

References · 26

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 244
  3. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
  4. 2015Contextual Dueling Banditscited by 101
  5. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  6. 2023LMFlow: An Extensible Toolkit for Finetuning and Inference of Large Foundation Modelscited by 58
  7. 2019Dueling Posterior Sampling for Preference-Based Reinforcement Learningcited by 56
  8. 2015Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problemcited by 51
  9. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  10. 2016Double Thompson Sampling for Dueling Banditscited by 42
  11. 2015Copeland Dueling Banditscited by 36
  12. 2017Multi-dueling Bandits with Dependent Armscited by 35
14 more
  1. 2022Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Modelscited by 35
  2. 2020Adversarial Dueling Banditscited by 33
  3. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
  4. 2015Sparse Dueling Banditscited by 29
  5. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  6. 2017Regret Analysis for Continuous Dueling Banditcited by 21
  7. 2017Maximum Selection and Ranking under Noisy Comparisonscited by 18
  8. 2018PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Boundscited by 17
  9. 2023Borda Regret Minimization for Generalized Linear Dueling Banditscited by 17
  10. 2016Copeland Dueling Bandit Problem: Regret Lower Bound, Optimal Algorithm, and Computationally Efficient Algorithmcited by 16
  11. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 14
  12. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problemscited by 12
  13. 2016Data-driven Rank Breaking for Efficient Rank Aggregationcited by 10
  14. 2022Finding Optimal Arms in Non-stochastic Combinatorial Bandits with Semi-bandit Feedback and Finite Budgetcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 6; 2025: 13; 2026: 4.

23 papers.

Sort:

By area:

  1. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 32
  2. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 27
  3. 2025Accelerating RL for LLM Reasoning with Optimal Advantage Regressioncited by 23
  4. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learningcited by 20
  5. 2024Sample-Efficient Alignment for LLMscited by 16
  6. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  7. 2025ActiveDPO: Active Direct Preference Optimization for Sample-Efficient Alignmentcited by 9
  8. 2024Neural Dueling Bandits: Preference-Based Optimization with Human Feedbackcited by 7
  9. 2024Online Bandit Learning with Offline Preference Data for Improved RLHFcited by 6
  10. 2025LLM Routing with Dueling Feedbackcited by 6
  11. 2025Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Samplingcited by 4
  12. 2025Active Human Feedback Collection via Neural Contextual Dueling Banditscited by 4
11 more
  1. 2025Bayesian Optimization from Human Feedback: Near-Optimal Regret Boundscited by 3
  2. 2025Federated Linear Dueling Banditscited by 2
  3. 2025Online Clustering of Dueling Banditscited by 2
  4. 2025Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Explorationcited by 2
  5. 2025Variance-Aware Feel-Good Thompson Sampling for Contextual Banditscited by 1
  6. 2025Multi-Objective Reward and Preference Optimization: Theory and Algorithmscited by 0
  7. 2025DT-PBO: an Interpretable Tree-based Surrogate Model for Preferential Bayesian Optimizationcited by 0
  8. 2026A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedbackcited by 0
  9. 2026Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptionscited by 0
  10. 2026Linear and Neural Dueling Bandits with Delayed Feedbackcited by 0
  11. 2026On the Complexity of Preference-Based Banditscited by 0