# Pure Exploration with Structured Preference Feedback

arXiv: https://arxiv.org/abs/2104.05294 · HTML: https://mlsanity.com/paper/2104.05294/

## Key facts

- Cited by 1 papers in the map (data through 14 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.

## Placed in

- LLM alignment / RLHF / preference optimisation / [Reward modeling and RLHF](https://mlsanity.com/alignment/reward-modeling-and-rlhf/)

## Builds on (most cited first, 19 of 19)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [MNL-Bandit: A Dynamic Learning Approach to Assortment Selection](https://mlsanity.com/paper/1706.03880/) (2017)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [Fully adaptive algorithm for pure exploration in linear bandits](https://mlsanity.com/paper/1710.05552/) (2017)
- [Thompson Sampling for the MNL-Bandit](https://mlsanity.com/paper/1706.00977/) (2017)
- [Dynamic Assortment Optimization with Changing Contextual Information](https://mlsanity.com/paper/1810.13069/) (2018)
- [Top-k Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/1905.12624/) (2019)
- [PAC Battling Bandits in the Plackett-Luce Model](https://mlsanity.com/paper/1808.04008/) (2018)
- [PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Bounds](https://mlsanity.com/paper/1806.02970/) (2018)
- [A Nearly Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Model](https://mlsanity.com/paper/1707.08238/) (2017)
- [Combinatorial Pure Exploration of Dueling Bandit](https://mlsanity.com/paper/2006.12772/) (2020)
- [Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners](https://mlsanity.com/paper/2006.07562/) (2020)
- [Towards Optimal and Efficient Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/1911.01695/) (2019)

## Built on by (most cited first, 1 of 1)

- [Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification](https://mlsanity.com/paper/2605.25592/) (2026)

## 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.