mlsanityData to 13 Oct 2026

Pure Exploration with Structured Preference Feedback

arXiv 2104.05294 ↗First posted 12 Apr 2021cs.LGcited by 1

On the map: LLM alignment / RLHF / preference optimisation → Reward modeling and RLHF

Abstract (arXiv)

We consider the problem of pure exploration with subset-wise preference feedback, which contains N arms with features. The learner is allowed to query subsets of size K and receives feedback in the form of a noisy winner. The goal of the learner is to identify the best arm efficiently using as few queries as possible. This setting is relevant in various online decision-making scenarios involving human feedback such as online retailing, streaming services, news feed, and online advertising; since it is easier and more reliable for people to choose a preferred item from a subset than to assign a likability score to an item in isolation. To the best of our knowledge, this is the first work that considers the subset-wise preference feedback model in a structured setting, which allows for potentially infinite set of arms. We present two algorithms that guarantee the detection of the best-arm in tildeO (fracd2K Delta2) samples with probability at least 1 - δ, where d is the dimension of the arm-features and Delta is the appropriate notion of utility gap among the arms. We also derive an instance-dependent lower bound of Omega(fracdDelta2 log frac1δ) which matches our upper bound on a worst-case instance. Finally, we run extensive experiments to corroborate our theoretical findings, and observe that our adaptive algorithm stops and requires up to 12x fewer samples than a non-adaptive algorithm.

Key facts. Cited by 1 paper in the map (data through 13 Oct 2026). Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation. Builds on 19 of its 49 references that are in the map. First posted on arXiv 12 Apr 2021.

Builds on

19 of 49 references.

References · 19

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 281
  2. 2016Optimal Best Arm Identification with Fixed Confidencecited by 235
  3. 2013lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Banditscited by 148
  4. 2014Best-Arm Identification in Linear Banditscited by 99
  5. 2019Sequential Experimental Design for Transductive Linear Banditscited by 88
  6. 2020Optimal Best-arm Identification in Linear Banditscited by 70
  7. 2020Gamification of Pure Exploration for Linear Banditscited by 61
  8. 2017MNL-Bandit: A Dynamic Learning Approach to Assortment Selectioncited by 50
  9. 2020An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Banditscited by 45
  10. 2017Fully adaptive algorithm for pure exploration in linear banditscited by 43
  11. 2017Thompson Sampling for the MNL-Banditcited by 35
  12. 2018Dynamic Assortment Optimization with Changing Contextual Informationcited by 28
7 more
  1. 2019Top-k Combinatorial Bandits with Full-Bandit Feedbackcited by 28
  2. 2018PAC Battling Bandits in the Plackett-Luce Modelcited by 27
  3. 2018PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Boundscited by 17
  4. 2017A Nearly Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Modelcited by 12
  5. 2020Combinatorial Pure Exploration of Dueling Banditcited by 8
  6. 2020Explicit Best Arm Identification in Linear Bandits Using No-Regret Learnerscited by 6
  7. 2019Towards Optimal and Efficient Best Arm Identification in Linear Banditscited by 3

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identificationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Learning a Ranking from Human Feedback in Log-Concave Random Utility Models
  2. 2026On the Complexity of Preference-Based Bandits
  3. 2024Bandits with Preference Feedback: A Stackelberg Game Perspective
  4. 2024Enhancing Preference-based Linear Bandits via Human Response Time
  5. 2025Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
  6. 2023Reward Learning as Doubly Nonparametric Bandits: Optimal Design and Scaling Laws
  7. 2024Neural Dueling Bandits: Preference-Based Optimization with Human Feedback
  8. 2024Comparing Few to Rank Many: Active Human Preference Learning using Randomized Frank-Wolfe