mlsanityData to 7 Oct 2026

DP-Dueling: Learning from Preference Feedback without Compromising User Privacy

arXiv 2403.15045 ↗First posted 22 Mar 2024cs.LG cs.CRcited by 1

Not on the map. Why?

Abstract (arXiv)

We consider the well-studied dueling bandit problem, where a learner aims to identify near-optimal actions using pairwise comparisons, under the constraint of differential privacy. We consider a general class of utility-based preference matrices for large (potentially unbounded) decision spaces and give the first differentially private dueling bandit algorithm for active learning with user preferences. Our proposed algorithms are computationally efficient with near-optimal performance, both in terms of the private and non-private regret bound. More precisely, we show that when the decision space is of finite size K, our proposed algorithm yields order optimal OBig(sumi = 2KlogfracKTDeltai + fracKεBig) regret bound for pure ε-DP, where Deltai denotes the suboptimality gap of the i-th arm. We also present a matching lower bound analysis which proves the optimality of our algorithms. Finally, we extend our results to any general decision space in d-dimensions with potentially infinite arms and design an ε-DP algorithm with regret tildeO left( fracd6kappa ε + frac d√T kappa right), providing privacy for free when T gg d.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 47 of its 76 references that are in the map. First posted on arXiv 22 Mar 2024.

Builds on

47 of 76 references.

References · 47

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2017Deep reinforcement learning from human preferencescited by 3,846
  3. 2023Safe RLHF: Safe Reinforcement Learning from Human Feedbackcited by 630
  4. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  5. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  6. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  7. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  8. 2015Contextual Dueling Banditscited by 101
  9. 2018Preference-based Online Learning with Dueling Bandits: A Surveycited by 100
  10. 2018Differentially Private Contextual Linear Banditscited by 82
  11. 2023Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimismcited by 69
  12. 2020Preference-based Reinforcement Learning with Finite-Time Guaranteescited by 65
35 more
  1. 2014Reducing Dueling Bandits to Cardinal Banditscited by 62
  2. 2019Dueling Posterior Sampling for Preference-Based Reinforcement Learningcited by 56
  3. 2017The Price of Differential Privacy For Online Learningcited by 44
  4. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  5. 2015Copeland Dueling Banditscited by 36
  6. 2017Multi-dueling Bandits with Dependent Armscited by 35
  7. 2022Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Modelscited by 35
  8. 2020Adversarial Dueling Banditscited by 33
  9. 2016A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Banditscited by 31
  10. 2018PAC Battling Bandits in the Plackett-Luce Modelcited by 27
  11. 2019Preference-Based Learning for Exoskeleton Gait Optimizationcited by 23
  12. 2017Regret Analysis for Continuous Dueling Banditcited by 21
  13. 2018Active Ranking with Subset-wise Preferencescited by 21
  14. 2019Combinatorial Bandits with Relative Feedbackcited by 19
  15. 2020ROIAL: Region of Interest Active Learning for Characterizing Exoskeleton Gait Preference Landscapescited by 19
  16. 2018PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Boundscited by 17
  17. 2022Private Online Prediction from Experts: Separations and Faster Ratescited by 17
  18. 2016Multi-Dueling Bandits and Their Application to Online Ranker Evaluationcited by 16
  19. 2021APReL: A Library for Active Preference-based Reward Learning Algorithmscited by 14
  20. 2018Efficient and Trustworthy Social Navigation Via Explicit and Implicit Robot-Human Communicationcited by 12
  21. 2020Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewardscited by 11
  22. 2022Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Banditscited by 11
  23. 2019From PAC to Instance-Optimal Sample Complexity in the Plackett-Luce Modelcited by 9
  24. 2021Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Banditscited by 9
  25. 2022ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Banditscited by 8
  26. 2022Non-Stationary Dueling Banditscited by 7
  27. 2023Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedbackcited by 7
  28. 2023Dueling Optimization with a Monotone Adversarycited by 7
  29. 2020Best-item Learning in Random Utility Models with Subset Choicescited by 6
  30. 2021Dueling Bandits with Adversarial Sleepingcited by 5
  31. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  32. 2022Dueling Convex Optimization with General Preferencescited by 5
  33. 2022One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Banditscited by 3
  34. 2024Stop Relying on No-Choice and Do not Repeat the Moves: Optimal, Efficient and Practical Algorithms for Assortment Optimizationcited by 3
  35. 2023Faster Convergence with Multiway Preferencescited by 2

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024Multi-Player Approaches for Dueling Banditscited by 2