mlsanityData to 7 Oct 2026

Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resources

arXiv 2312.17229 ↗First posted 28 Dec 2023cs.LG stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

We consider the problem of reward maximization in the dueling bandit setup along with constraints on resource consumption. As in the classic dueling bandits, at each round the learner has to choose a pair of items from a set of K items and observe a relative feedback for the current pair. Additionally, for both items, the learner also observes a vector of resource consumptions. The objective of the learner is to maximize the cumulative reward, while ensuring that the total consumption of any resource is within the allocated budget. We show that due to the relative nature of the feedback, the problem is more difficult than its bandit counterpart and that without further assumptions the problem is not learnable from a regret minimization perspective. Thereafter, by exploiting assumptions on the available budget, we provide an EXP3 based dueling algorithm that also considers the associated consumptions and show that it achieves an tildeOleft(fracOPT(b)BK1/3T2/3right) regret, where OPT(b) is the optimal value and B is the available budget. Finally, we provide numerical simulations to demonstrate the efficacy of our proposed method.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 40 of its 69 references that are in the map. First posted on arXiv 28 Dec 2023.

Builds on

40 of 69 references.

References · 40

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2017Deep reinforcement learning from human preferencescited by 3,846
  3. 2021PEBBLE: Feedback-Efficient Interactive Reinforcement Learning via Relabeling Experience and Unsupervised Pre-trainingcited by 298
  4. 2013Bandits with Knapsackscited by 163
  5. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  6. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  7. 2015Contextual Dueling Banditscited by 101
  8. 2018Preference-based Online Learning with Dueling Bandits: A Surveycited by 100
  9. 2014Bandits with concave rewards and convex knapsackscited by 83
  10. 2015Linear Contextual Bandits with Knapsackscited by 82
  11. 2018Adversarial Bandits with Knapsackscited by 73
  12. 2023Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimismcited by 69
28 more
  1. 2014Reducing Dueling Bandits to Cardinal Banditscited by 62
  2. 2017MNL-Bandit: A Dynamic Learning Approach to Assortment Selectioncited by 50
  3. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  4. 2015An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectivescited by 43
  5. 2015Copeland Dueling Banditscited by 36
  6. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 36
  7. 2017Multi-dueling Bandits with Dependent Armscited by 35
  8. 2022Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Modelscited by 35
  9. 2020A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraintscited by 34
  10. 2020Adversarial Dueling Banditscited by 33
  11. 2016A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Banditscited by 31
  12. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  13. 2017Regret Analysis for Continuous Dueling Banditcited by 21
  14. 2018Active Ranking with Subset-wise Preferencescited by 21
  15. 2019Combinatorial Bandits with Relative Feedbackcited by 19
  16. 2018PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Boundscited by 17
  17. 2016Copeland Dueling Bandit Problem: Regret Lower Bound, Optimal Algorithm, and Computationally Efficient Algorithmcited by 16
  18. 2022Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oraclescited by 12
  19. 2022Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Banditscited by 11
  20. 2021Preference learning along multiple criteria: A game-theoretic perspectivecited by 9
  21. 2021Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Banditscited by 9
  22. 2022ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Banditscited by 8
  23. 2023Dueling Optimization with a Monotone Adversarycited by 7
  24. 2020Best-item Learning in Random Utility Models with Subset Choicescited by 6
  25. 2021Dueling Bandits with Adversarial Sleepingcited by 5
  26. 2022Dueling Convex Optimization with General Preferencescited by 5
  27. 2019Simple Algorithms for Dueling Banditscited by 3
  28. 2022One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Banditscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Online Convex Optimization with Dueling Feedbackcited by 1
  2. 2026Replicable Bandits with UCB based Explorationcited by 0
  3. 2026Multi-Task Representation Learning for Conservative Linear Banditscited by 0