# Stop Relying on No-Choice and Do not Repeat the Moves: Optimal, Efficient and Practical Algorithms for Assortment Optimization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 36 references that are in the map.
- First posted on arXiv 29 Feb 2024.

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

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Preference-based Online Learning with Dueling Bandits: A Survey](https://mlsanity.com/paper/1807.11398/) (2018)
- [Reducing Dueling Bandits to Cardinal Bandits](https://mlsanity.com/paper/1405.3396/) (2014)
- [MNL-Bandit: A Dynamic Learning Approach to Assortment Selection](https://mlsanity.com/paper/1706.03880/) (2017)
- [Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models](https://mlsanity.com/paper/2202.04593/) (2022)
- [Copeland Dueling Bandits](https://mlsanity.com/paper/1506.00312/) (2015)
- [Multi-dueling Bandits with Dependent Arms](https://mlsanity.com/paper/1705.00253/) (2017)
- [On the Theory of Reinforcement Learning with Once-per-Episode Feedback](https://mlsanity.com/paper/2105.14363/) (2021)
- [PAC Battling Bandits in the Plackett-Luce Model](https://mlsanity.com/paper/1808.04008/) (2018)
- [Active Ranking with Subset-wise Preferences](https://mlsanity.com/paper/1810.10321/) (2018)
- [Combinatorial Bandits with Relative Feedback](https://mlsanity.com/paper/1903.00543/) (2019)
- [PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Bounds](https://mlsanity.com/paper/1806.02970/) (2018)
- [Multi-Dueling Bandits and Their Application to Online Ranker Evaluation](https://mlsanity.com/paper/1608.06253/) (2016)
- [Multinomial Logit Bandit with Linear Utility Functions](https://mlsanity.com/paper/1805.02971/) (2018)
- [A Nearly Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Model](https://mlsanity.com/paper/1707.08238/) (2017)
- [Data-driven Rank Breaking for Efficient Rank Aggregation](https://mlsanity.com/paper/1601.05495/) (2016)
- [A Note on a Tight Lower Bound for MNL-Bandit Assortment Selection Models](https://mlsanity.com/paper/1709.06109/) (2017)
- [Competitive analysis of the top-K ranking problem](https://mlsanity.com/paper/1605.03933/) (2016)
- [Assortment optimisation under a general discrete choice model: A tight analysis of revenue-ordered assortments](https://mlsanity.com/paper/1606.01371/) (2016)
- [Assortment Optimization under a Single Transition Model](https://mlsanity.com/paper/1702.03700/) (2017)

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

- [Learning an Optimal Assortment Policy under Observational Data](https://mlsanity.com/paper/2502.06777/) (2025)
- [Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options](https://mlsanity.com/paper/2510.18713/) (2025)
- [DP-Dueling: Learning from Preference Feedback without Compromising User Privacy](https://mlsanity.com/paper/2403.15045/) (2024)
- [Learning in Position-Aware Multinomial Logit Bandits: From Multiplicative to General Position Effects](https://mlsanity.com/paper/2605.17238/) (2026)

## Abstract (arXiv)

We address the problem of active online assortment optimization problem with preference feedback, which is a framework for modeling user choices and subsetwise utility maximization. The framework is useful in various real-world applications including ad placement, online retail, recommender systems, fine-tuning language models, amongst many. The problem, although has been studied in the past, lacks an intuitive and practical solution approach with simultaneously efficient algorithm and optimal regret guarantee. E.g., popularly used assortment selection algorithms often require the presence of a `strong reference' which is always included in the choice sets, further they are also designed to offer the same assortments repeatedly until the reference item gets selected -- all such requirements are quite unrealistic for practical applications. In this paper, we designed efficient algorithms for the problem of regret minimization in assortment selection with Plackett Luce (PL) based user choices. We designed a novel concentration guarantee for estimating the score parameters of the PL model using `Pairwise Rank-Breaking', which builds the foundation of our proposed algorithms. Moreover, our methods are practical, provably optimal, and devoid of the aforementioned limitations of the existing methods. Empirical evaluations corroborate our findings and outperform the existing baselines.