# Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 47 references that are in the map.
- First posted on arXiv 23 Feb 2022.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Preferential Bayesian Optimization](https://mlsanity.com/paper/1704.03651/) (2017)
- [Reducing Dueling Bandits to Cardinal Bandits](https://mlsanity.com/paper/1405.3396/) (2014)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [Multi-dueling Bandits with Dependent Arms](https://mlsanity.com/paper/1705.00253/) (2017)
- [Multi-Armed Bandits with Correlated Arms](https://mlsanity.com/paper/1911.03959/) (2019)
- [A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits](https://mlsanity.com/paper/1601.03855/) (2016)
- [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)
- [Online Learning with Gaussian Payoffs and Side Observations](https://mlsanity.com/paper/1510.08108/) (2015)
- [A Nearly Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Model](https://mlsanity.com/paper/1707.08238/) (2017)
- [Multi-Armed Bandits with Dependent Arms](https://mlsanity.com/paper/2010.09478/) (2020)
- [Data-driven Rank Breaking for Efficient Rank Aggregation](https://mlsanity.com/paper/1601.05495/) (2016)
- [Best-of-K Bandits](https://mlsanity.com/paper/1603.02752/) (2016)
- [Cheap Bandits](https://mlsanity.com/paper/1506.04782/) (2015)
- [Best-item Learning in Random Utility Models with Subset Choices](https://mlsanity.com/paper/2002.07994/) (2020)

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

- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Iterative Data Smoothing: Mitigating Reward Overfitting and Overoptimization in RLHF](https://mlsanity.com/paper/2401.16335/) (2024)
- [ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2210.14322/) (2022)
- [Neural Dueling Bandits: Preference-Based Optimization with Human Feedback](https://mlsanity.com/paper/2407.17112/) (2024)
- [One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Bandits](https://mlsanity.com/paper/2210.14998/) (2022)
- [Faster Convergence with Multiway Preferences](https://mlsanity.com/paper/2312.11788/) (2023)
- [Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resources](https://mlsanity.com/paper/2312.17229/) (2023)
- [Online Clustering of Dueling Bandits](https://mlsanity.com/paper/2502.02079/) (2025)
- [Federated Linear Dueling Bandits](https://mlsanity.com/paper/2502.01085/) (2025)
- [DP-Dueling: Learning from Preference Feedback without Compromising User Privacy](https://mlsanity.com/paper/2403.15045/) (2024)
- [The Power of Active Multi-Task Learning in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2405.11226/) (2024)

## Abstract (arXiv)

We introduce the Correlated Preference Bandits problem with random utility-based choice models (RUMs), where the goal is to identify the best item from a given pool of n items through online subsetwise preference feedback. We investigate whether models with a simple correlation structure, e.g. low rank, can result in faster learning rates. While we show that the problem can be impossible to solve for the general `low rank' choice models, faster learning rates can be attained assuming more structured item correlations. In particular, we introduce a new class of Block-Rank based RUM model, where the best item is shown to be (ε,δ)-PAC learnable with only O(r ε-2 log(n/δ)) samples. This improves on the standard sample complexity bound of tildeO(nε-2 log(1/δ)) known for the usual learning algorithms which might not exploit the item-correlations (r ll n). We complement the above sample complexity with a matching lower bound (up to logarithmic factors), justifying the tightness of our analysis. Surprisingly, we also show a lower bound of Omega(nε-2log(1/δ)) when the learner is forced to play just duels instead of larger subsetwise queries. Further, we extend the results to a more general `noisy Block-Rank' model, which ensures robustness of our techniques. Overall, our results justify the advantage of playing subsetwise queries over pairwise preferences (k=2), we show the latter provably fails to exploit correlation.