Finally Rank-Breaking Conquers MNL Bandits: Optimal and Efficient Algorithms for MNL Assortment

Authors: Aadirupa Saha, Pierre Gaillard
Primary area: reinforcement learning
Keywords: Active online assortment optimization, Preference feedback, Subsetwise utility maximization, Assortment selection algorithms, Plackett Luce model, Regret minimization, Pairwise Rank-Breaking, Concentration guarantee, Practical algorithms, Empirical evaluations

Abstract:
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, and fine-tuning language models, amongst many others. 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 \emph{Plackett Luce} (PL) based user choices. We designed a novel concentration guarantee for estimating the score parameters of the PL model using `\emph{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.

Decision: accept (poster)
Reviewer scores: 6, 6, 6, 5

Reviews and discussion:
<thread>
creation date:
1730398139430

thread_type:
official_review

<thread_object>
creator: reviewer_jq9h

<content>
summary:
In this paper, the authors addressed the problem of active online assortment optimization with preference feedback. The authors worked with a general AOA model where the no-choice item does not necessarily have the highest preference score. They then designed an algorithm using rank-breaking MNL-parameter estimation, and provided theoretical guarantees for their algorithm for both Top-m and Wtd-Top-m objectives. The authors also numerically evaluated the effectiveness of their algorithm.

strengths:
Overall, the paper is well structured. The theoretical results appear sound and the authors provided detailed proof sketches. The authors have also provided a comprehensive overview of the existing literature and summarized their limitations.

weaknesses:
1. I'm not sure what's the main motivation behind the model studied. In MNL bandits, the assumption of having a no-choice item with the highest preference score is usually well justified. For example, in an e-commerce setting where multiple items are present, the majority of the customers are simply browsing the pages before making the purchase. In what kind of applications would this new AOA model be helpful?
2. Following the point above, if the rank-breaking algorithm is applied to a setting where the no-choice item does dominate, how does the algorithm compare to MNL-bandits? It seems that MNL-bandit should achieve a better regret bound in that case, and from Fig 2. it seems that the performance is also somewhat similar. 
3. In terms of practicality, I am wondering if the authors could also comment on how the rank breaking algorithm can be applied in real-world settings. The authors suggest that the proposed model can be potentially helpful in "web search, language models, online shopping, recommender systems". I wonder if the authors can comment more on how the proposed model can assist these applications. Experiments on real-world data could also be helpful here, as only synthetic experiments have been conducted so far.

Overall, I find this paper well written with nice theoretical results, but I'm mostly concerned about (1) the necessity of studying an AOA model without the NC item assumption and (2) the practicality of the proposed algorithm in a realistic setup.

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730477644845

thread_type:
official_review

<thread_object>
creator: reviewer_x5yt

<content>
summary:
This paper considers the problem of online assortment optimization from bandit feedback. More specifically, they assume a setting where there are k arms or items (along with a special item corresponding to the no-selection option), each associated with an unknown quality, and the learner can select m items in each trial to present to the user. Feedback is received in the form of a single choice or selection from the presented set of arms, which is assumed to be drawn from the classical MNL model where the probability of an item selection is proportional to the underlying item quality. In this framework, they consider two main objectives: a top-m selection objective where the per-round regret is defined as the difference in the total quality of the set of m arms with the highest quality (optimal action in hindsight), and the set of arms presented to the user by the learner in that round, and a weighted top-m objective (revenue maximization), where each arm is additionally associated with a revenue, and the corresponding regret is the difference between the expected revenue of the set of arms with the highest expected revenue, and the expected revenue of the presented subset. This general problem is commonly studied in both the machine learning and operations research literature, but prior work has some notable limitations, such as assuming the arm corresponding to the no choice option has the highest weight/quality, and is present in every set of arms presented. This work resolves some of these deficiencies by proposing a relatively simple and intuitive algorithm based on rank breaking, which is a common idea explored in the past for breaking multiway comparisons into multiple pairwise comparisons to compute estimates of the qualities of the underlying items. The authors show that rank breaking is able to obtain sharp estimates of the underlying qualities, and as a consequence, are able to show that their approach theoretically obtains a regret bound that scales as roughly $O(\sqrt{T})$ for both settings - top-m and revenue maximization, and has improved dependence on certain parameters such as the quality of the best item. They corroborate the theory with experiments on synthetic data.

strengths:
I think the paper is very well written. The exposition is clear, and the authors do a good job of placing their work relative to other related research. The claims are accompanied with technical proofs, which I have verified to be correct. The algorithm is also very intuitive, and simple enough to be used in practice.

weaknesses:
Despite the strengths, I do not believe this result is very novel. While some of the limitations of existing works are legitimate, such as assuming that the no choice option has the highest weight, and removing this assumption is an important contribution, other points made, such as existing work requiring the same set to be probed multiple times to get a good estimate of the item qualities are not. Practically, you are not playing this online learning game with a single user, but rather a huge number of users, in which case it is perfectly reasonable to be able to display the same set multiple times. Moreover, there is value in repeatability and predictability: for example being shown the same set of options or at least a similar set of options every time a user queries something. For example, imagine a user is comparing between different offerings for a particular kind of product across different websites, and eventually deciding to pick one after comparing all their options. Now if they return to a website to select something they think to be best after comparing all their options, but the website shows them a completely different set of options this time around, it is reasonable to expect the user would get annoyed, since they would have to restart their comparison process all over again. Therefore, an argument can be made in either direction, and I don’t believe “not repeating options” is a strength. Moreover, the other limitation which you pointed out where some results require you to converge to the top arm being duplicated m times is not really a limitation. It is due to the notion of regret used in their work and not an algorithmic limitation. It is perfectly reasonable when your arms are really higher level categories, which can contain multiple different instances of that arm type instead of duplicates (e.g. an arm might be a particular brand or service provider, and the ‘m’ copies might be different offerings by the same brand or provider).

On a more technical front, I am fairly certain this result can be obtained via a combination of Accelerated Spectral Ranking (Agarwal et al, ICML 18), and the batching idea for bandits with limited adaptivity (Esfandiari et al, AAAI 21, Gao et al Neurips 19, Perchet et al, Annals of Statistics 16). Basically, break the set of items into subsets of size m each, and play these batches in epochs of geometrically increasing lengths, using the ASR algorithm to compute estimates of the item qualities at the end of each epoch. Since we can select which arms are in each subset, we can force a reference arm to be placed in all subsets (either no-choice arm if it has sufficiently high weight, or some other arm of your choice that has weight comparable to the highest weight arm). The estimation guarantees of ASR are in terms of TV norm, but due to the nature of that bound, you can simply use it as an L_\infty bound instead, and use it to eliminate arms that have a clear separation from the top m arms, and repeat this process with the surviving arms, doubling the epoch length in each round. I am fairly certain this will give essentially the same regret bound, if not a better one. I will try to work out the proof when I can find some time to verify my suspicion.

questions:
Look at the last point in my weaknesses. To me, it seems like this problem should be solvable via known results in bandits + parameter estimation for MNL.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730708842843

thread_type:
official_review

<thread_object>
creator: reviewer_kjyh

<content>
summary:
The paper revisits MNL bandit problems, and designs efficient algorithms for the problem of regret minimization in assortment selection. The authors propose a novel concentration guarantee for estimating the score parameters of the model using ‘Pairwise Rank-Breaking’, which builds the foundation of the proposed algorithm. The provided regret upper bound is quite comparable with state-of-the-art, with numerical simulations verifying their theoretical results.

strengths:
* The paper proposed a new perspective to tackle the MNL bandit problem, which is interesting in the literature while sharing a quite comparable regret performance as Agrawal et al. 2019.

weaknesses:
See Questions section.

questions:
* In Line 315, I'm not sure if a regret bound of $\tilde{O}(\sqrt{KT})$ is optimal in the proposed model setting, as the lower bound of stochastic bandit is known as $\Omega(\log T)$ from Lai & Robbins (1985) [1], while $\Omega(T^{1/2})$ is known as the regret lower bound of adversarial bandit setting.
* How does the regret result relate to the maximum of assortment size $m$? In extreme case where $m=1$, the problem reduces to a standard bandit problem with a "no choice" action. How to understand the impact of $m$ on the regret?

[1] https://core.ac.uk/download/pdf/82425825.pdf
</content>
</thread_object>

</thread>
<thread>
creation date:
1731481381630

thread_type:
official_review

<thread_object>
creator: reviewer_t5dy

<content>
summary:
This paper revisits the Active Optimal Assortment (AOA) problem, and proposes two algorithms: $\mathrm{AOA-RB_{PL}}$ (Algorithm 1) and $\mathrm{AOA-RB_{PL}-Adaptive}$ (Section 4). Regret bounds have been established (Theorem 3, 4, 5) and preliminary experiment results have been demonstrated in Section 5.

strengths:
- To the best of my knowledge, the proposed algorithms in this paper are novel, and they are based on some new insights like Rank-Breaking (proposed in Khetan & Oh (2016)) and Adaptive Pivot Selection (proposed in this paper).

- The analyses in this paper seem to be rigorous and highly non-trivial. I have not checked the analyses line by line, but the derived regret bounds make sense to me.

- The authors have done a good job of literature review and have well positioned this paper with respect to relevant literature.

weaknesses:
- The writing of this paper can be further improved. Section 3 and Section 4 are too technical and a little bit hard to read.

- All the experiments in this paper are synthetic. Might the authors add some experiment results based on real-world datasets?

- [typo] for Arith50 environment, $\theta_i = 1-(i-1) \times 0.2$ for $i \in [50]$. This seems to be a typo since $\theta_i$ can be negative.

questions:
Please address the weaknesses above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732701711998

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
[In response to the questions raised by Reviewer X5Yt] Revisiting the key Ideas of our main algorithm (Adaptive AOA-RBPL, Sec 4) and its regret Analysis

comment:
We gave two algorithms, (**Alg1**) AOA-RBPL in Sec3, and (**Alg2**) AOA-RBPL-Adaptive, in Sec4, both of which use two different estimates of $\{\theta_{i,t}^{ucb}\}_{i \in [K]}$, $\theta_{i,t}^{ucb}$ being the upper confidence bound (UCB) estimate of the MNL parameter $\theta_i$ at round $t$, for all $i \in [K]$. *Due to the scale independence of the MNL model, we always assume that the parameter of the no-choice (NC) item is always $\theta_0 = 1$* (see Line 204).

**How $\boldsymbol{\theta}^{ucb}$ was used in the regret analysis (Thm 3, Thm5):** We will explain the intuition of $\theta_{i,t}^{ucb}$ for Alg1 and Alg2, but before that let us understand how $\theta_{i,t}^{ucb}$ were used in the regret analysis of Thm3 and Thm5 (resp. for Alg1 and Alg2): 

- (1) Towards this, an important observation to note is both our regret analyses (i.e. proof of Thm5 and Thm6) uses a **key wtd-utility inequality** $\mathcal R(S^*, \boldsymbol{\theta}) \leq  \mathcal R(S^*, \boldsymbol{\theta}^{ucb})$, where $\mathcal R(S^*, \boldsymbol{\theta})$ and $\mathcal R(S^*, \boldsymbol{\theta}^{ucb})$ respectively denote the weighted-utility of set $S^*$ under MNL parameters $\boldsymbol{\theta}$ and $\boldsymbol{\theta}^{ucb}$ (see Eq2): Please see the in proof of Thm3 and Thm6 respectively, to note how we used the above key inequality to derive the final regret upper bound ($Reg_T^{wtd}$) for Alg1 and Alg2). 

- (2) However, to achieve the above property we need to ensure, $\theta_i^{ucb} \geq \theta_i$ as we showed in Lem8: Essentially Lem8 shows that if $\theta_i^{ucb}$ is a valid UCB of $\theta_i, ~\forall i \in [K]$, then the estimated wtd-utility $\mathcal R(S^*, \boldsymbol{\theta}^{ucb})$ is also a valid UCB of $\mathcal R(S^*, \boldsymbol{\theta})$.

- (3) Hence the question is how to assign the values of $\theta_i^{ucb}$ so that they represent a valid and tight UCB of the corresponding (true) MNL parameters $\theta_i$s?  

We will now justify our choice of $\theta_i^{ucb}$s for all $i \in [K]$ for which the above properties are satisfied, both for Alg1 and Alg2. But let us understand an important property of the MNL model before that.

**$\boldsymbol{\theta}$ estimate from MNL pairwise preferences:** 

- (1) Thanks to the property of the MNL model, we first note that $\textbullet $ For any two items $i, j \in [K]\cup \{0\}$, the pairwise preference of $i$ over $j$ is $p_{ij} = \frac{\theta_i}{\theta_i + \theta_j}$ by definition (see Eq1). 

- (2) But since $\theta_0 = 1$ (Line204), this implies $\textbullet (ii) ~\theta_{i} = \frac{p_{i0}}{1 - p_{i0}}, ~\forall i \in [K]$.

- (3) *However $p_{i0}$ is unknown, but can we estimate it?* Here we have a **key idea** that by exploiting the *Independence of Irrelevant Alternatives (IIA)* property of MNL model once can indeed maintain unbiased pairwise preference estimates ($p_{ij}$s) of any pair $(i,j)$, $i,j \in [K]\cup\{0\}$ using Rank-Breaking. We denoted them by $\hat p_{ij,t}$ at round $t$ (Eq.3).

Let us now first understand the rationale behind our choice of $\boldsymbol{\theta}_t^{ucb}$ for Alg1. 

> $\boldsymbol{\theta}_t^{ucb}$ justification for Alg1 (uses the NC item as pivot):

- (1) Upon realizing $\theta_i = \frac{p_{i0}}{1 - p_{i0}}$ and having access to $\hat p_{i0,t}$, the unbiased estimates of $p_{i0}$ derived through rank breaking as described above, we first find a **good upper confidence bound** (UCB) estimate of $p_{i0}$, denoted by $p_{i0,t}^{ucb}$ as described in Eq3. Further, we derive the concentration rate (tightness) of the UCB estimate $p_{i0,t}^{ucb}$ in Lem7 (Appendix B.1). 

- (2) The next idea was to use $p_{i0,t}^{ucb}$ to define a natural estimate of $\theta_{i,t}^{ucb} = \frac{p_{i0,t}^{ucb}}{[1 - p_{i0,t}^{ucb}]+}$ (see the display after Eq3, we are unable to construct the right display with the openreview markdown), drawing inspiration from $\theta_i = \frac{p_{i0}}{1 - p_{i0}}$. Further, Lem1 establishes the rate of concentration of the UCB estimate $\theta_{i,t}^{ucb}$ using Lem8 (see proof of Lem1 and 7 in Appendix B.1, B.2).

This concludes our intuition behind our choice of $\theta_{i,t}^{ucb}$, which provably yields a UCB estimate of the true MNL parameters $\theta_i$ for all $i \in [K]$.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper studies  Active Optimal Assortment (AOA) problem under MNL bandit feedback. The authors proposes two algorithms based on a  concentration guarantee for estimating the score parameters of the model using ‘Pairwise Rank-Breaking’. Theoretical analysis of regret bounds and synthetic experiments validated the effectiveness of proposed methods. The reviewers recognized the following strengths:
- The proposed algorithms are novel and intuitive.
- Theoretical analyses are sound.
- Paper organization and presentation are clear.

The reviewers raised several questions and concerns:
- Technical novelty and challenge, especially comparing to deriving similar results by combining existing techniques.
- Experiments are synthetic, lack of experiments on real-world data.
- Clarification questions regarding motivating examples, regret bounds, comparison to other approaches.

Three reviewers are positive about the paper after discussion with the authors and one reviewer did not engage in discussion. The key remaining concern is whether we can derive similar results by combining existing techniques raised by Reviewer X5Yt. I see this as a valid question and thank the authors and the reviewer for multi-round thorough discussion. I recommend acceptance considering the paper's strengths and reviewers' positive opinions, and strongly suggest the authors to include detailed discussion regarding this issue in final version.