Finally Rank-Breaking Conquers MNL Bandits: Optimal and Efficient Algorithms for MNL Assortment
Authors: Aadirupa Saha
Pierre Gaillard
Venue: ICLR 2025 Poster (2025)
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
Primary area: reinforcement learning

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.

Published as a conference paper at ICLR 2025
FINALLY RANK-BREAKING CONQUERS MNL BANDITS: OPTI- MAL AND EFFICIENT ALGORITHMS FOR MNL ASSORTMENT
Aadirupa Saha
Department of Computer Science
University of Minoii, Chicago com
Pierre Gaillard
Univ. Grenoble Alpes, Inria, CNRS Grenoble INP, LJK, 38000 Grenoble, France pierre.ga gaillard@inria.f.
ABSTRACT
We address the problem of active online assortment optimization problem with preference feedback, which is framework for modcling 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 prob- lem, although has been studied in the past, lacks an intuitive and practical solution approach with simultaneously efficient algorithm and optimal re- gret guarantce. 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 Mullinomial Logit (MNL) based user choices. We designed a novel concentration guarantee for estimating the score parameters of the PL model using Pairwise Mank-Breaking which builds the foundation our proposed algorithms. Moreover, our methods are practical, provably optimal, and devoid of the aforementioned limitations. Empirical evaluations corroborate our findings and outperform the existing basclines.
INTRODUCTION
Studics have shown that it is often casier, faster and less expensive to collect feedback on a relative scale rather than asking ratings
an absolute scale. E.g,, to understand the liking for a given pair of items, say (A,B), 3 it is easier for the users to answer preference-basel queries like: "Do you prefer Item A over B?", rather than their absolute counterparts: "How much do you score items A and B in a scale of [0-10]?" (Musallam et al. 2004 Kahneman & Tversky 1982). Due to the widespread applicability and case of data collection with relative feedback, learning from preferences has gained much popularity in the machine-learning community, especially the active learning literature which has applications in Medical surveys, Al tutoring systems, Multi-player sports/ games, any real-world systems that have ways to collect leedback terms of preferences. The problem is famously studied as the Dueling- Bandit (DB) problem in the active learning community Yue et al. (2012): y Ailon al. (2014): Zoghi et al. (2014a b. 2015), which is an online learning framework for identifying a set of "good' items from fixed decision-space (set of items) by querying preference feedback of actively chosen item-pairs. Consequently, the generalization of mmeling-Bandiin with subset-wise preferences has also been developed into an active field of research. For instance, applications like Web search, language models, online shopping, recommender systems (e.g. Youtube, Netflix, Google News/ News/Maps, Spotify) typically involve users expressing preferences
Part of the work was done while author was Apple, MT. Research

---

Published as a conference paper at ICLR 2025
by choosing one result (or handful of results) from subset of offered items and often the objective of the system is to identify the 'most-profitable" subset to offer to their users. The problem, popularly termed as 'Assortment Optimization' is studied in many interdisciplinary literature, e.g. Online learning and bandits [Bengs et al. (2021a), Operations research Talluri & Van Ryzin| (2004); Agrawal et al. (2019). Game theory Chatterji et al. (2021) RLHF
Christiano et al. [2017]: Ouyang et al. (2022), to name a few.
Problem (Informal): Active Optimal Assortment (AOA) Active Assortment Op-
uimization (a.k.a. UGility Maximization with Subset Choices) [erbeglia & Joret (0166);
Agrawal et al. (2019): Désir et al.) (2016b/a) is an active learning framework for find- profit-maximiiing
subset. Formally, assume we have decision set of 2, ... K of K items, with each item being associated with the score (or utility) parameters 0 = (01, 02....,0.. .Ox) (without loss of generality assume 0 2 0₂ 2... 0x 2 0). At each round t= 1, ..., the learner or the algorithm gets to query an assortment (typically subsets containing up to m-items) S. S [K], upon which it gets to see some (noisy) relative preferences across the itemss in St, typically generated according to an underlying Multinomial Logit (MNL) model with parameters o Further, to allow the event where items are selected, we also model a No-Choice (NC) item, indexed by item-O, with PL parameter 0o I...
ing the 'optimal'
(Objective 1.) Top-m: identify the top-m item-set: (01,..., 0m for some m E [1, K].
(Objective 2.) Wtd-Top-m: A more general objective could also consider a weight (or price) r. E R. associated with the item E [K], and the goal could be to identify the assortment (subset) with maximum weighted utility as detailed in Sec. 2
Related Works and Limitations: As stated above, the problem of AQA is fundamental in many practical scenarios, and thus widely studied in multiple research areas, including Online ML/learning theory and operations research.
In the Online ML literature, the problem is well-studied as Multi- Dueling Bandits Sui al. (2017): Brost et al. (2016), or Battling Bandits Saha & Gopalan (2019a) 2018): 8); Bengs et al. (2221)) which is an extension of the famous Dueling Bandit problem Zoghi et al. (2014b a).
The main limitation of this line of work is the lack of practical objectives, which either aim to identify the 'best-item' 1(= arg m 0.) within a PAC (probably approximately
correct) framework [Saha & Gopalan| (2019b): Chen et al. 2017 2018); Ren et al. (2018) or quantifying regret against the best items Saha & Gopalan 2019a ; Bengs et al. 2022). J. Note
the latter actually leads to the optimal subset choice of repeatedly sclecting the optimal item,
arg max; 6,, m times, i.c. 11,,,...)) 1), which is unrcalistic from the viewpoint of real-world system design. Selecting an assortment of distinct lop-m iterss (Top-m-AOA) or maximum expected utility (Wud-Top-m-AOA) makes more sense.
On the other hand, a similar line of the problem has been studied in operations research and dynamic assortment selection literature, where the goal is to offer subset of items to the customers in order to maximize expected revenue. The problem has been studied under different user choice models, e.g. PL or Multinomial-Logit models (Agrawal et al. 2019), Mallows and mixture of Mallows (Désir et al. 2016a). Markov chain-based choice models (Désir et al.) 2016b), single transition model (Nip et al. 2017) etc. While these works indeed consider a more practical objective of finding the best assortment (subset)) with the highest expected utility for a regret minimization objective, (1) major drawback in their approach lies in the algorithm design which requires to keep on querying the same set multiple times, e.g. [Agraall et al. (2019); Ou al. (2018); : Chen et al. (2021); Agrawal et al. (2017). Such design techniques could be impractical to be deployed in real systems where users could casily get annoyed if the same items are shown again and again. For example, in ad-placement, music//mvvie / /nwws/ news/tweets// htt/tttets//reeeee /reclss//ssssssee recommendations, offering the same assortment could increase user dissatisfaction and disengagement.
(2) The second major drawback of this line of work lies in the struclural assumption of their underlying choice models which requires the eristence of a fierence/defoall item, that
This is equivalent to finding the set with maximum expected revenue when 7:8 represents the price of item Agrawal et al. (2019)
2

---

Published as a conference paper at ICLR 2025
needs to be part of every assortment St. This leads to assuming a No-Choice item, typically denoted as item-0, which is a default choice of any assortment S,. Further a stronger and more unrealistic assumption lies in the fact that they require to assume that the above pivot is stronger than the rest of the K items, i.e. A 2 max 0,, i.e. the No-Choice (NC) action is the most likely outcome of any assortment S. This is often unrealistic, e.g., during user interactions with language models, online shopping, users typically make choices as the user needs to commute or book a flight and a NC action is highly improbable, e.g. in recommender systems like YouTube,, Spolify, Netflix or even Yahoo News, users lypically make choices as they actually wanted to consume a video, new article or song, etc. Similarly, in shopping recommendations like flghhts (Expedia or Google flights), hotel (Booking.com) restaurants (Grubhub), or Google Maps recommendations, NC is unlikely. In fact, in some applications, NC might not even be an available (feasible) option, e.g. while interacting with ChatGPT/ Gemini, the language model often requests the users to definitivcly select one outcome in order to procoed with the thrcad; Similarly, in robotics applications, training of autonomous vehicles, more generally in any preference-basee RL (a.k.a. PbRL) applications, the teacher/ demonsstrtor human feedback provider must choose an option out of the multiple options (or RL trajectories) towards training the RL policy, Consequently, such assumption limits the use in real-systems. In the existing literature Agrawal et al. (2019 : Oh & Lyengar (219)) Agrawal et al. (2017); Grant & Leslie
maps recommendation,
(0023 such assumptions are primarily adapted solely for theoretical needs, precisely for maintaining concentration bounds of the PL parameters 0, and hence not well justified from
a practical viewpoint.
Agrawal et al. (2019) is the classical MNL- estimate the true PL parameter 0 = (0,, 0x )8 by repeatedly querying the same set (i.e. assortment St) multiple times and keeping a count of the average number of times an item i EE [K] is selected until no items (NC) are selected. They further maintain a UCB of the estimated PL parameters, (01...., xx), and the assortment of the next phase optimistically based on the UCB est est istimats.. The process is repeated until time step T. Agrawal et al. 2017 is a follow-up work of Aggraal el al. (2019) from the same group of authors and hence Their algorithm MNL-TS is almost the same as MNL-UCB above, with the exception of using Thompson Sampling (TS) with Beta posteriors, instead of the UCB estimates. The regret guarantee and set of restrictive assumptions imposed on the MNL model is also identical to that of Agrawal et al. (2019). The objective of Grant & Leslie (2023) is slightly different from that of above two as their objective is 'learning to rank' (LTR), i.c. to find the best ordered subset based on some position bias A; > 0 for position E [m]. More generally, their preference model is different which assumes the probability of the item played at position-k getting selected (or clicked) for any m-length ordered set S = (S(1)..... s=(S(1),
work with MNL-UCB: The idea is to
((m)) is given by
+E Jemm Xy0s))) where usual 9, is the score parameter of the no-choice item. We summarize these existing works in Table [
P(k SS) := X
Some recent developments also generalized the AOA problem to linear MNL scores to incorporate large actions embedded in d-dimension Zhang & Ji (2019): Zhang & Sugiyama (2024); Oh & Iyengar (2019), however, their approaches are either limited to the above restrictions or suller sub-optimal regret guarantees without those assumptions (e.g. the regret bound of Oh & Iyengar (2019) is (TT which is suboptimal by d-factor). Considering the above limitations of the AOA literature, we set to answer two questions:
(1) Can we consider a general AOA model where the default item, like the NC item defined above, is not necessarily the strongest one, i.c. 6g 2 max 0,?
(2) Can we design a practical and regret optimal algorithm for the AOA framework, without needing to play the same repetitive actions and yet converge to the optimal assortment?
3

---

Published as a conference paper at ICLR 2025
Work
Framework
Assume fg Mmax
Regret
Our (Alg.
MNL. model (Ohj.
No
/min ( (m KJKT Tog
Agrawal et 22019
Thr
MNL model (Ohj.
Yes
/K7 log
Agrawal et al.
2019
(Tmm 4)
MNL model [Obj.
No
v / maxe K' log?
Agrawal et al.
2017
MNL model (Obj. 2)
Yes
R'T log (mT)
Grant & Leslie 2023
MNL model with
No
V mine ty log T
KT
constraints (Obj. 2)
Our Contribution vs the Existing Results in the K-armed MNL-Assortment literature. The regret statements inchude only the leading asymptotic term, ignoring constant factors.
Table 1:
Contributions We answer these questions in the affirmative and present best of all scenarios. We design practical algorithms on practical AOA framework with practical objectives Unlike the existing approaches of the AOA, literature Agrawal et al. (2019); Chen al. (2021), we do not have to keep playing the same assortment multiple times, neither require strongest default item (like NC satisfying Gu 2 maxie(K] 02). Morcover, our objectives do not require us to converge to a multiset of replicated arms like (1, (...... 1), but converge to the millitt-maximizing set of distinct items. We list our contributions below:
1. A General AOA Setup: We work with general problem of AOA for PL model, which requires no additional structural assumption of the parameters such as 0g 2 max; 0,, unlike the existing works. We designed algorithms for two separate objectives Top-m and Wtd--To-m as discussed above (Soc. 2
2. Efficient and Optimal Algorithm using Rank- Bank-Brekking MNL-Parameter Esti- mation: In Sec. 3 we give a practical, efficient and optimal algorithm for MNL Assortment (up to log factors and the magnitude of maxx). The regret bound our algorithm AOA-RBpI. (Alg. [ yields Ö(VKT) regret for both Top-m and Wul-Top-m objective. Our algorithms use a novel parameter estimation technique for discrete choice models based on the con- cept of Rank- Breaking (RB) which is one of our key contributions towards designing the efficient and optimal algorithm. This enables our algorithm to perform optimally without requiring the No-Choico item to be the strongest. Appendix A details the key concept of our parameter cstimation technique exploiting the concept of RB. Our resulting algorithm plays optimistically based on the UCB estimates of PL parameters and does not require repeating the same subset. multiple times, justifying our title.
3. Improvement with Adaptive Pivots: In Sec. we refine the performance of our algorithm hm by employing the novel idea of 'adaptive pivots' (a reference item) and proposed AOA-RB AOA-RByy-Adaptive
this removes the asymptotic dependence on 0max max, 0 in the regret analysis. This enables the algorithm to work effectively in scenarios where the No-Choice item is less likely to be selected, i.e., 0max > 1. This leads to huge improvement in our experiments, especially in the range of low Oo, where AOA-RBpL-Adaptive drastically outperforms over the existing bascline. Comparison of our regret bound with existing work is detailed in Table
Performance-wer
4. Emperical Analysis. Finally, corroborate theoretical results with empirical evaluations (Sec. 5), which certify our superior performance in the general AOA setups.
It is also worth mentioning that our proposed algorithm and their respective regret analysis could be extended to any general random utility (RUM) based preference models Soufiani et al. (2014); Saha & Gopalan (2020), , explained in Rem. 1 the techniques. However, to keep the tocus on the AOA problem and case the presentation, we stick to the special case of MNL choice model based preferences.
2 PROBLEM SETUP
We write [n] = 21,2, ..., n} and 1(-) denotes the indicator function. The symbol S. employed in the proof sketches, represents coarse incquality.
We consider the sequential decision-making problem of Active Optimal Assortment (AOA), with preference/choice leedback. Formally, the learner is given [K], a finite set of K items
4

---

Published as a conference paper at ICLR 2025
(K > 2). At each decision round t = .. the learner selects subset S. S [K] of up to m items, and receives some (stochastic) feedback about the item preferences St. drawn according to some unknown underlying MNL choice model [ with parameters = (01, .1,00.....0x E RRK We assume 01 2 02 2 2 0x without loss of generality. An interested reader may check App. A..] for detailed discussion on PT. models. Given any assortment St we also consider the possibility of 'no-selection" of any items given an S.. Following the literature of Agrawal al. (2019), we model this mathematically as No-Choice (NC) item, indexed by item-0, and its corresponding PL utility parameter Bu- Unlike most existing literature on assortment selection, we are not assuming Bu A ma 0z- Further, since the PL model is scale independent, we set 0g = I and scale the rest of the PL parameters.
Feedback model The feedback model formulates the information received (from the 'environment') once the learner plays subset S, S [K] of at most m items. Given S consider the algorithm receives a winner feedback (or index of an item) is E St U (0), drawn according to the underlying PL choice model as:
P(:: = = 6./(00 Ejes, U3), Vi e S..
(1)
We consider the following two objectives for the learner:
Top-m-Ojective One simple objective could be identify the top-m item-set: (0I...., } for some m E [1, K]. The performance of the learner can be captured by minimizing the following regret:
T Os- Os
Regr
top
where
S = SC SCIKSS Sm
argmax
{os = 0. IES
m
1=1
2. Wtd-Top-m- ToddToT---jjtttivee
Here, each item-i is associated with weight (for example price) ri E R+, and the goal to identify the set of size at most m with maximum weighted utility. One could measure the regret of the learner as:
r2 Ejes''
Regit = Σ (R(S* R(S,, 0)), where R(S,0) Σ
AA S [K], (2)
Go
denotes S* == argmaxsc R(S,0) is the optimal maximtima subset. This
objective corresponds to the standard objective in the MNT. litterature Agrawal et al. (0099
3
A PRACTICAL AND EFFICIENT ALGORITHM FOR AOA WITH PT.
3.1
ALGORITIM DESIGN
Main Idea. The crux of our novelty lies in our PL parameter estimation technique which maintains estimate of pairwise scores of Pt, 0,40, for each pair of item (i.j) using Rank- Breaking (RB) Khetan Oh (0016) a classical technique extracting pairwise comparisons from choice (or partial ranking) feedback by breaking each win-loss pair independently in the choice data. A formal description is given in App.[A.2] More precisely, using rank- brnk-breaking we estimate the relative (pairwise) strength Pij.e of each item pair (i.j) at round I, as explained in (3). Further, noting 0, = Pso/(1 Pto) (as 0 = 1), we use Pio,t to estimate the MNL score B.. of the i-th item using the NC (0-th item) the 'pivot' item to benchmark against. Next, we prove a crucial concentration result in Lemma showing indeed 0,,, a 'sharp' estimate of 0,, which is then subsequently used to prove the final regret guarantees Theorem 3 and Thcorem respectivcly. Our proposed algorithm Alg. [ is described below:
0
Estimate pupper-coffidence-buuddd @uch from Pairwise Estimates. At each time t, our algorithm (Alg. []] maintains a pairwise preference matrix P, E [o, 1|axn, whose (i. (ith entry Pij.e records the empirical probability of i having beaten j in pairwise duel, and
5

---

Published as a conference paper at ICLR 2025
corresponding upper confidence bound p.gh- (i.5) [K] [K],
Let [K]
[K] (0). We define for each pair
pch Pij,t Pigae + 201j,(1 Pej.e)
3r
Waj.t
where
Pij.
(3)
Tigie
nij.a
where pairwise wins of item-i over j a alter rank-breaking and naj.t = wij.t + Wjit being the total
an imput of Alg. and wigs E lii i,j j E S.} denotes the number of
number of times (i.j) has been 'rank- broken' till time (details in App. A.2 Noting that
0 = Pio/(1 Pro), the above UCB estimates piy, are further used to design UCB estimates
of the PL parameters 0, follows
0 = Pao.1/ /1
ncb
(1- - uch
P
where (.)+ max
Optimistic Assortment Selection The estimates o are then used to select the set St, that maximizes the underlying objective. This optimization problem transforms into a static assortment optimization problem with upper confidence bounds 0acb as the parameters, and efficient solution methods for this case are available (sec c.g., Avadhanula et al. (2016): Davis et al. 2013 Rusmevichientong al. (2010)).
A Agoorihhm 1 AOA for PL model with RB (AOA-RBPI.)
1: input: x x> 0
2: init: K +- K + 1, [K] = [K] WT + [0
3: for t= 1,2,3,..., do
W. 4: Set N, W.+ WT, and P, N.
Denote N. [mijAR and P, -FojdRRR ij
5: Define for all i, ucb
2 and for all i,j E {
ucb Pij.t = Pos + [2prial1 (Pan))))))
1/2
+
3r
Deg.e
6:
1,2
=
Pio,t / Pso,t
Top-m items from argsort((01.,...... for Top-m objective argmaxsc[K][SSSs R(S, (uch), for Wtd-Top-m objective
7:
S.
8: Play S,
9: Receive the winner i, E [K] (drawn per
10: Update: W.+1 [wij++1]&x 8.l. wige+t Wait +1 S
11:
end for
3.2
ANALYSIS: CONCENTRATION LEMMAS
We start the analysis by providing two technical lemmas, whose proofs are deferred to the appendix and that provide confidence bounds for the O,,
Lemma 1. Let T and æ > 0. Then, with probability at least 1 - 3Ke for all t e [T] and i E [K] 0, guch atleast one of the following two inequalities is satisfied
20,0,r
+ 22x(0n + 0,)
n.o.2 < 69x + 0,) or gucb <0, + 4400 + B.) 140.
7100,
The above lemma depends on 4.o.s the number of times items have been compared with item up round The latter is controlled using the following lemma:
Lemma 2. Let T 2 and x > 0. Then, with probability at least 1 KTe= simultancously for all I [T] and E [K]
(6o + 0.)
Tsa < 2z(0g + Os.)2 or noo.t 2
(4)
2(0. + Og.))
where Ti.t
Σ1=1 (i S.} denotes the number of rounds item got selected before round t.

---

Published as a conference paper at ICLR 2025
3.3 ANALYSIS: ToP-m OBJECTIVE:
We are now ready to provide the regret upper bound for Algorithm 1 with Top-m objective.
Theorem 3 (Top-m Objective). Let 0max 2 1. Consider any instance of PL model on K items with parameters 8 E [0, m 80 = L. The regret of Alg. with parameter z = 2 log T bounded as
( v KT KTlogg) log top RegT
when T 00.
The above rate of Ö(VKT) is optimal (up to log-
lower bound can be derived from standard multi-armed bandits [Auer (2000): Auer et al. (2002). We only state here a The detailed proof is deferred to the App.
sketch of the proof of Theorem 3
Proof Skelch of Theorem
Let us define for any S S [K],
Σ 0,, and Og iES
Σ 0.cb.
iES
Let & be the high-pne hig--probability event such that both Lemma 1 and holds true. Then, P(()) 2
1 - 4== Let us first assume that & holds true. Then, by Lemina which yields
Og. S O O
T Σ t=1
T
T
Regi
top
0g-
Euch Os. S TO Σ Os
(0
(Ts 2 To
m (=1 tE
where To 1m + 1) max corresponds to an exploration phase needed for the confidence
upper bounds of Lem [ and to be satisfied. Then, noting that if E holds true, we show
by Lemma 2 that (T, 2 TO S [ 2 69x(fo + 0.). Therefore, we can apply Lemma that entails,
(guch (T,, n0
Σ ieS.
(0o + +0))
0g0,0
{ 2 Tot)
777
m
nhs,tt
iES.
Lem.
K
03/2 max
03/2
max maraa S max .KT
Tit
Em
IES.
where used Σ 1/v1 < n/ and Σ, The mf together with Jensen's 's inequality in the last inequality. We thus have under the event that Regr top < <0 VxKT) and the proof is concluded by taking the expectation with 2 log T to control P(E9).
3.4 ANALYSIS: WTD-TOP-M OBJECTIVE
In this section we analyze the regret guarantee of Alg, | for Wtd-Top-m objective 2
Theorem (Wid-Top-m Objective). Let Omax 2 1. Then, for any E [0, 0 K and weights E [0, 1]K, the weighted regrel of AOA-RBei (Alg. 1 with log
Reyse utd
O(V 0 0max KT KTlog T)
when T 0o.
The complete proof is postponed App. B The rate D(VKT) is optimal as proved by the lower bound in Chen & Wang (0117) for MNL bandit problems for 6max = 1. Our result recovers (up to factor vlog? 7') the one of Agrawal et al. (2019) when 0 = 1. However, their algorithm relies on more sophisticated estimators that necessitate epochs repeating the same assortment until the No-Choice item is selected. Note for our problem setting, where is possible to have 0 max >> 0g 1, the length of these epochs could be of O(K0max), which could be potentially very large when fmax >> 1. This reduces the number of effective epochs, leading to poor estimation of the PL parameters. We see this tradeoff in experiments (Sec. (5) where the MNL-UCB algorithm of Agrawal et al. (0199) yields linear O(T) regret for such choice of the problem parameters.

---

Published as a conference paper at ICLR 2025
Proof sketch of Thm. are satisfied. Then,
4
Let & be the high-probability event such that both Lemma
I and
T
T
Regt
utd
Σ
B[R(S" ,) R(S,,0) 2 Σ 1=1
BR(SS - R(SEE)) +TF(E)
==1
E (R(Ss, 01 - () + TP(E")
(5)
because R(S Bpch)) R(S", ) 2 R(S", 8) under the event & by Lemma upper-bound the first term of the right-hand-side
We now
Σ (R(S), (0.00) R(S
0)) 118)
Σ
E
r,0;
118)
Go
S.t
8u + Os
VE
T
rs ( 0:)
E
N11}
0o + Os.
1=1
iESt
Because S 2 Ss, under the event & by Lemma Then, using r; S 1, we further upper-
bound using an exploration parameter Tp = Ollog (T) so that the uppor-coffidenc-bounds in Lemmas 1 and 2 are satisfied
K
T
11i E S,, 0 0.l 0o + Os,
((((S), 0,0h)) - R(S., 0)) 0))) [{8}
K
Ba 021
O
E
1 E St, Tue
To. E}
Oo Os:
1=1
K
fi
Oucb - 0,
200 + Os.
50(TT)+
E
1 T.
The 2 To,
8)
On Os:
0o + Us 0,
=1Ar(1)
(6)
where the last inequality is by Cauchy-Schward inequality. Now, the term Ar(i) above may be soper-bounded. using Lemmas D and 2
(0 0,)² 0,(00 + Os.)
T
(Op + 0,)
(1 = E
lii E Su, E.
E
l E Se)
140,
Os,))
(Oo +.) (0g Os, )4
fif (i,0). E
0
E
0 2
S 0 log T
110.0
where in the last inequality we used that Σ n= S + log T. Substituting into (6) Jensen's inequality entails,
T 0,1 S
Σ e (F (F)( $ O(T0++B
Omaxx log T Σ
0o + Os.
The proof finally concluded by applying Cauchy- Schnnar-- inequality which yields:
K Σ
(i E S.)
1= 011ii S.}
K
S VKT.
8. + Os.
Bu + +ss
Finally, combining the above result with 5 and concludes the proof
Reg TTP(E) O TTax T Choosing 2og ensures TP(E*) < 0(1) and To s O(log T)-
8

---

Published as a conference paper at ICLR 2025
4 IMPROVED DEPENDANCE ON max WITH ADAPTIVE PIVOT SELECTION
problem with Algorithm
1 stems from estimating all 0g based on pairwise comparisons
with item O. When 0max
> 0o 1, item 0 may not be sampled enough the winner,
leading to poor estimators. This deficiency contributes to the suboptimal dependence on mmxx observed in Theorems 3 and and in prior work, such as Agrawal et al. (2019). We propose the following fix to optimize the pivot. For all i,j E [K] we define %ij 8j'
Ni.i
pcb ucb Pij.t/ Pij.a)
ucb)
and
ucb Vai,
= 11
where puch are defined in For all rounds 1, the algorithm AOA- AOA-RBri.Adaptine selects
S. argmax R(S, (lcb)
where
@ucb jE(K]U{0}
min
750,t
ucb ucb
mm
With the above definition of Puck any item i is compared to the base item 0 through the best possible item j. When j is a strong item that is often selected both kj.. sharp upper-bounds of Yi and 750, making 0rep itself sharp upper-confidence bound for 0,, This definition in turn also satisfies the condition 0i 2 8g required by Lemma S and crucial for our analysis. The condition would not hold if we only used Vij.t without the Yj0,t factor.
ucb and uub are
We offer below a regret bound that underscores the value optimizing the pivot when mmxx > K. Note that while the algorithm and analysis are presented for the weighted objective with winner feedback only, it can be adapted to other objectives by replacing R(S, 0) with the new objective in the analysis, as long as Lemma S remains valid.
Theorem 5. Let O 1. For any 0 E [0, m K and weights regret of COA-RByL-Adaptee is upper-bounded as
1], the weighted
Regt O K) KT K log
as 0o for the choice x 2 2og (when definining pi5.))
The proof of Theorem is deferred to the App. with a key step relying on selecting the pivot je argmax upper-bounds with an s dependence on fmax leveraging the fact that 0,, 2 0,. Due to the varying pivot over time, telescoping argument introduces additive factor VK.
fj. The use of l 0,1 S husb 0,1 provides confidence
When mmx is constant, the regret is /o T). eliminating any asymptotic dependence on O 0max- This allows for handling scenarios where the No-Choice item is highly unlikely, unlike previous works such as Agrawal el al. (2019 2017). Agrawal et al. (2019) did attempt to relax the assumption of 6max = 0, and shows bound of order O max (maax /0. /KT), which unfortunately blows to oo as Oo - (equiv. mmax + 00).
Remark 1 (Beyond MNL Assortment: Extending any general RUM based Choice Models).
Although, in this paper, primarily focused on MNL based choice models, our proposed algorithms may be generalized to more general random utility-based models (RUMs) Azari
et al. 20122); Saha & Ghoshal (2022) purswing the ideas from Saha & Goopalan (2020) that
extends the R.B based parameter estimation technique to any RUM(O) choice models: Precisely, using the RB based RUM-parameter estimation technique of Saha & Gopalan (2020). we
show a regret bound of Ö( maxx K) KT) for our proposed algorithm AOA-RBPLE where Crum is the parameter associated to the mindmum advantage ratio (min-AB of the underlying RUM(O) model, as defined in Thm. of Saha & Gopalaa (2020). In particular, Crum can shown to be a constant given fixed RUM model, e.g. Crum 1/4 for Exp(1), Gamsna(2, 1), Cram = 11(44)) for Gumbell μ. o), Crum = =X4 for Weibull(A) 1), Crum = 1/3 for Gaussian(O, 1), elc (using Cor. 5 of Saha & Gopalan 2020)).
5 EXPERIMENTS
We experiments to compare the performance of our method with the state-of-thi ttr methods. All results are averaged across 100 runs. We evaluate the performance of our main algorithm MaA-RBpp.-ddaptti (Sec. 4 referred "Our Alg-1 (Adaptive Pivot)", with the
9

---

the Published as a conference paper at ICLR 2025
following algorithms: AOA-RBpL (Sec. 8 referred "Our Alg-2 (No-Chotee Choice Pivot)', and MNL-UCB, the state-of-the-art algorithm for AOA (Agrawal et al. (2019). Alg. 1).
Different PL (0) Environments. We report experiment results on two datasets with
K 50 items: (1) Arith50 with PL parameters 0; = - (i 1)0.02, vi E [50]. (2) Bad50 with PL parameters 0, 0.6, Vi E [50] (25) and 025 0.8. For simplicity of computing the assortment choices S,, we assume r; = 1, E [
(1). Averaged Regret with weak NC (f / 1) (Fig. 1) In first experiment,
we set m = and 0p/0max 0.01 and report the average regret of the above three algorit for two objectives.
1960
2013
Lotk 4CB
1000
8000
1900
5000
19000
4000
Figure 1: Averaged Regret for 5, 0g 0.01
Fig. 1 shows that our algorithm AOA-RBeL-Adaptiin (with adaptive pivot) significantly outperforms the other two algorithms, while our algorithm AOA-RBpL with no-choice (NC) pivot still outperforms MNL-UCB.
(2). Averaged Regret No-Choice PL Parameter (0max/00 10)) (Fig. 2): In this experiment, we evaluate the regret performance of our algorithm AOA-RBrL-Adapive. We report the experiment Artith50 PL dataset and set the subsetsize 01, 0.1, 0.05, 0.01, 0.005, 0.001 J. Fig. shoows the increase in the performance gap between our algorithm AOA-RBpp Addapttte (with adaptive pivot) with decreasing 0,/ max.
5, maxx/0 /00
Ma30 28
Figure 2: Comparative performance for varying f0/0max, m m=
Figure 3: Tradofff: Averaged Regret
length of the rank-ordered feedback
(3). Averaged Regret vs Length the rank-ordered feedback (k) (Fig. 3): We also rum thought experiment to understand the tradeoff between learning rate with k-length rank-ordered feedback, where given any assortment S, S [K] of size m, the learner gets to the top-k draws (k S m) from the PL model without replacement. This is stronger feedback than the winner (i.e. top-1 for = 1) feedback and, as expected, we see in Fig. 3 improved regret (for both notions) when increasing k. The experiment are Artith50 dataset with m = 30 and k E (1,2,4,8)
CONCLUSSOON
We study the Active Optimal Assortment Selection problem under PL choice models, introducing a framework (AOA). Our algorithm uses a novel Baan-Brrekiie technique for tight parameter estimation, ensuring efficiency, optimality (up to log factors), and practicality without restrictive assumptions on the default (no-choice) item.
Future Works. Among many interesting questions to address in the future, will be interesting to understand the role of the No-Choice (NC) item in the algorithm design An intriguing direction is whether similar results can be achieved or improved using recent parameter istimation technique for MNL models such as the one from Agarwal et al. (0018) instead of rank- bank-breaking. However, as currently formulated, their technique suffers from an undesirable dependence that scales with (fmax/Ou)². This dependence might be mitigated in their analysis by employing batches estimate the parameters 6,, However, it remains unclear whether their approach can completely eliminate the dependence on 0
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Arpit Agarwal, Prathamesh Patil, and Shivani Agarwal. Accelerated spectral ranking. Tn Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 70 79, PMLR, 10 15 Jul 2018. URL attps::/prroceecingg .ml. aatss//v8//ggrraallaaaa html
Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the mul-bandit, In Conference learning theory, pp. 76 78. PMLR, 2017.
Shipra Agrawal, Vashist Avadhanula, Vineet, Goyal, and Assal Zeevi. Mnl-bandit: A dynamic learning approach to assortment, selection. Operations Research, (5)):1453314533 2019.
Nir Ailon, Zohar Karnin, and Thorsten Joachims. Reducing dueling bandits to cardinal bandits. In International Conference on Machine Learning, pp. 856 864. PMLR, 2014.
Jean- Yves Audibort, Rémi Munos, and Csaba Szepesvári. Exploration tradcoff using variance estimates in multi-armed bandits. Theoretical Computer Science 410(19): 1976-1902, 2009.
Peter Auer. Using upper confidence bounds for online learning. In Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, pp. 270-279. IEEE, 2000.
Peter Auer, Nicolo bandit problem. Machine learning, 47(2-3):235-222 2002.
and Paul Fischer. Finite-time analysis of the multiarmed
Vashist Avadhanula, Jalaj Bhandari, Vineet Goyal, and Assaf Zeevi. On the tightness of an Ip relaxation for rational optimization and its applications. Operations Research Letters, (11)))17266 2016.
Hossein Azari, David Parkes, and Lirong Xia. Random utility theory for social choice. In Advances in Newral Information Processing Systems, pp. 126-134, 2012a.
Hossein Azari, David Parks, and Lirong Xia. Random utility theory for social choice. Advances in Neural Information Processing Systems, 25, 2012b.
Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Paul, and Eyke Hüllermeier. Preference- based online learning with dueling bandits: survey. Journal of Machine Learning Research, 2021a.
Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Paul, and Eyke Hüllermeier. Preference- based online learning with dueling bandits: A survey. J. Mach. Learn. Res., 22:7 1, 2021b.
Viktor Bengs, Aadirupa Saha, and Eyke Hüllermeier. Stochastic contextual ducling bandits under linear stochastic transitivity models. In International Conference on Machine Learning, pp. 1764 1786. PMLR, 2022.
Gerardo Berbeglia and Gwenaël Joret. Assortment optimisation under general dis- crete choice model: A tight analysis of revenue-ordered assortments. arXiv preprint arxio:1666. 01371, 2016.
Brian Brost, Yevgeny Seldin, Ingemar J. Cox, and Christina Lioma. Multi-dueling bandits and their application to online ranker evaluation. CoRR, abs/1608.06251 2016.
Niladri S Chatterji, Aldo Pacchiano, Peter L, Bartlett, and Michael T Jordan. On the theory of reinforcement learning with once-per-episode feedback. arXiv preprint arXim:2105. 14363, 2021.
Xi Chen and Yining Wang. note on tight lower bound for mul-bandit assortment selection models. arXie preprint ar 1799: 009.00609, 2017.
Xi Chen, Sivakanth Gopi, Jieming Mao, and Jon Schneider. Competitive analysis of the top-k ranking problem. In Proceedings of the aventy-Eightte Annual ACM-SIAM Symposium on Discrete Algorithms, pp.
STAM, 2017.
11

---

Published as a conference paper at ICLR 2025
Xi Chen, Yuanzhi Li, and Jieming Mao. A nearly instance optimal algorithm for top-k ranking under the multinomial logit model. In Proceedings of the Twenty-Nin Ninth Annual ACM-SIAM Symposium Discrete Algorithms, pp. 7504-2520 SIAM, 2018.
Xi Chen, Chao Shi, Yining Wang, and Yuan Zhou. Dynamic assortment planning under nested logit models. Production and Operations Management, 30(1):85-102, 2021.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei.
Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
James Davis, Guillermo Gallego, and Huseyin Topaloglu. Assortment planning under the multinomial logit model with totally unimodular constraint structures. Work in Progress, 2013.
Antoine Désir, Vineet Goyal, Srikanth Jagabathula, and Danny Segev. Assortment optimiza- lion under the mallows model. In Advances in Neural Informalion Processing Systems, pp- 4700-4708, 2016a.
Antoine Désir, Vincet Goyal, Danny Segev, and Chun Ye, Capacity constrained assortment optimization under the markov chain based choice model. Operalions Research, 2016b.
James A Grant and David SS Leslie. Learning to rank under multinomial logit choice. Journal of Machine Learning Research, 24(260):1-49, 2023.
Minje Jang, Sunghyun Kim, Changho Suh, and Sewoong Oh. Optimal sample complexity of m-wise data for top-k ranking. In Advances in Neural Information Processing Systems, pp- 1685-1695, 2017.
Daniel Kahneman and Amos Tversky. The psychology of preferences. Scientific American, 246(1):160 173, 1982.
Ashish Khetan and Sewoong Oh. Data-driven rank breaking for efficient rank aggregation. Journal of Machine Learning Research, 171193):1-54, 2016.
Sam Musallam, BD Corneil, Bradley Greger, Hans Scherberger, and Richard Andersen. Cognitive control signals for neural prosthetics. Science, 305(5681):258 262, 2004.
Kameng Nip, Zhenbo Wang, and Zizhuo Wang. Assortment optimization under single transition model. 2017.
Min-hwan Oh and Garud lyengar. Thompson sampling for multinomial logit contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
Mingdong Ou, Nan Li, Shenghuo Zhu, and Rong Jin. Multinomial logit bandit with linear utility functions. arXiv preprint arXiv:1805.022 1805.09959 2018
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730-27 27744, 2022.
Wenbo Ren, Jia Liu, and Ness B Shroff. PAC ranking from pairwise and listwise queries: Lower bounds and upper bounds. arXiv preprint arXiv:1800 02970, 2018
Paat Rusmevichientong, Zuo-Jun Max Shen, and David B Shmoys. Dynamic assortment optimization with multinomial logit choice model and capacity constraint. Operations research, 5866):1666-1680, 2010.
Aadirupa Saha and Suprovat Ghoshal. Exploiting correlation to achieve faster learning rates in low-rank preference bandits. In International Conference on Artificial Intelligence and Statistics, pp. 456-482. PMLR, 2022.
Aadirupa Saha and Aditya Gopalan. Active ranking with subset-wiss wise preferences. Interna- lionl Conference on Artificial Intelligence and Statistics (AISTATS), 2018.
12

---

Published as a conference paper at ICLR 2025
Aadirupa Saha and Aditya Gopalan. Combinatorial bandits with relative feedback. In Advances in Neural Information Processing Systems, 2019a.
Aadirupa Saha and Aditya Gopalan. PAC Battling Bandits in the Plackett-Luce Model. In Algorithmic Learning Theory, pp. 700 737, 2019b.
Aadirupa Saha and Aditya Gopalan. Best-item learning random utility models with subset choices. In International Conference on Artificial Intelligence and Statistics, pp. 4281-4291. PMLR, 2020.
Hossein Azari Soufiani, David C Parkes, and Lirong Xia. Computing parametric ranking models via rank-breaking. In ICML, pp. 360-368, 2014.
Yanan Sui, Vincent Zhuang, Joel Burdick, and Yisong Yue. Multi-dueling bandits with dependent armss In Conference on Uncertainty in Artificial Intelligence, UAI'17, 2017.
Kalyan Talluri and Garrett Van Ryzin. Revenue management under a general discrete choice model of consumer behavior. Management Science, 50(1):15 33, 2004.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 1835):1538-1566 2012.
Yu-Jie Zhang and Masashi Sugiyama. Online (multinomial) logistic bandit: Improved regret and constant computation cost. Advances in Newral Information Processing Systems, 36, 2024.
Zihan Zhang and Xiangyang Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function. In Advances in Neural Information Processing Systems, pp. 2827 2836, 2019.
Masrour Zoghi, Shimon Whiteson, Remi Munos, Maarten de Rijke, et al. Relative upper confidence bound for the k-armed dueling bandit. problem. In JMLR Workshop and Conference Proceedings, number 32, pp. 10-18. JMLR, 2014a.
Masrour Zoghi, Shimon A Whiteson, Maarten De Rijke, and Remi Munos. Relative confidence sampling for efficient on-line ranker evaluation. In Proceedings of the 7th ACM international conference on Web search and data mining, pp. 73 82. ACM, 2014b.
Masrour Zoghi, Zobar S Karnin, Shimon Whiteson, and Maarten De Rijke. Copeland dueling bandits. In Advances in Neural Information Processing Systems, pp. 307 315, 2015.
13

---

Published as a conference paper at ICLR 2025
SUPPLEMENTARY: FINALLY RANK-BREAKING CONQUERS MNL BANDITS: OPTIMAL AND EFFICIENT ALGORITHMS FOR MNL ASSORTMENT
A PRELIMINARIES: SOME USEFUL CONCEPTS FOR PL CHOICE MODELS
A.1 MNL: A DISCRETE CHOICE MODEL
A discrete choice model specifies the relative preferences of two or more discrete alternatives in a given set. A widely studied class of discrete choice models the class of Random Utilily Models (RUMs), which assume a ground-truth utility score 0, E R for each alternative i [m], and assign a conditional distribution D-(,),) for scoring item i. To model a winning alternative given any set S S [n], one first draws random utility score X, D.(+)0)) for each alternative in S, and selects an item with the highest random score.
One widely used RUM is the Multinomial-Loge (MNL) or Plackett-Luce model (PL), where the D,s are taken to be independent Gumbel distributions with parameters 8 (Azri et al. 2012a 2a L.e,, with probability densities
(a, (x----0)e -1,--)
(=, = -
0f R. Vi [m].
Moreover assuming 8 0, 0, 0 Vi e [n], it can be shown in this case the probability that an alternative emerges as the winner in the set S 3 becomes: P(i]S) = Eses"; "
Other families of discrete choice models can be obtained by imposing different probability distributions over the utility scores X,, e-g. if (X1,... X,) ~ (),,A) are jointly normal with mean 0 = (f Ox) and covariance A E Raax,, then the corresponding RUM-based choice model reduces to the Multinomial Probit (MNP).
A.2 RANK BREAKING
Rank breaking (RB) is well-understood idea involving the extraction of pairwise comparisons from (partial) ranking data, and then building pairwise estimators on the obtained pairs by treating each comparison independently (Khetan & Ohl 2016 Jang et al. 2017), e.g., winner a sampled from among a, b, c is rank- broken into the pairwise preferences a > 6, a > c. We use this idca to devise cstimators for the pairwise win probabilities P.y P(i for our problem setting. We used the idca of RB in both our algorithms (AOA-RBpL and HEA-RBpi-Adaptiiee
(0, +8))
to update the pairwise win-count estimates Wajj. for all the item pairs (i.j) E [K] x [K], which is further used for deriving the empirical pairwise preference estimates Pej,r, any time
A.3 PARAMETER ESTIMATION WITH PL BASED PREFERENCE DATA
Lomma 6 (Pairwise win- cin-probability estimates for the PL model (Saha & Gopalan 2018 ).
Consider MNL model with paramelers 0 0= 00(0,, O2....,0.. and for two items i, E nn]. Let SI....,Ty ST be a sequence of (possibly random) subsels of [m] of size at least 2, where T is a positive integer, and i1....,iT a sequence of random items with each in S,, 15 T, such that for each 1 S t S T', (a) St depends only on ST and (b) ig is distributed as and St, and (c) Vt: (i.j) S S. with probability 1. Let (T) = Σt= P(4, = i) and (Ty(T) = Σt P(fe E (1,H)). Then,
the MNL. winner of the subset St, given S1,i1...., St-1,
for any posilive integer v, and 1) E (0,1),
n; (T)
0:
P
2 n. (T) 22) S 20n²
(
nuy (T)
0, + 0
nz (T)
0:
TP
S -n, (T)
se -2n 20n²
(T)
0, 0
14

---

Published as a conference paper at ICLR 2025
B OMITTED PROOFS FROM SEC. B AND SEC. 4
B.1 A CONCENTRATION BOUNDS FOR THE Pig.
We first prove below a concentration incquality based on Bernstein's incquality for the estimators Pija-
Lemma 7. Let (1,5) E [K] x [K]. Let T 2 and x > 0. Then, with probability at least 1 >
2p (1 -Pis)
11x
Pij S
uch Pija
S Pij + V
nij.e
nij.t
simultaneously for all t [T].
Proof of Lemma Let 2 1, x and i.j [K]. Applying Thm. of Audibert et al.
2009), with probability at least 1 - 3(x, T), we get simultaneously for all t E [T].
2p (1 D(ya)
3x
Pisse Pol s
niga
Rij.t
where B(x,T) 3 3nf min {
T S 3"e Note that the inequality holds true although nij.a is random variable. This, shows the first inequality
log loga
Pij S Pij.
For the second incquality,
9
implics
2P Deg,)
Pij.t = Pisit +
V
nija
Maj.r
2Pi
Dij,)
$ Pij + 1
(10)
nija
naj
Furthermore, because x + x(1 x) 1- 1-Lipschitz on [0, 1], we have
|p.j - Pija)) (15 Pit) S |eej.t Pij
2p. D.j.))x 3z
Nsj..
naj.
Therefore,
25 D)g,e)x
3x
Pis.(1 - (ps,1) & Pts (1 p(s) +
+
nij.
<Vpr((1 pıj) + V
3x.
2
|nss.e
which yields
Pis -Ds,e) S (1 P(s)
3x
(11)
V
nijet
Plugging back into
10
we get
2p piz)xr
11x
Pij. < 2
Mij.e
nij.t
n
15

---

Published as a conference paper at ICLR 2025
B.2 PROOF OF LEMMA
Proof. Let i E [K] and x > Then, by a union bound on Lemma and 2 with probability
at least 1 47'e" x2 S and 4 hold true for all / E [T]. We consider this high-probabillty event in the rest. of the prool. Define the function f I + x/(1 x)+ on [0, 0J (with the
convention f(1) +50); that Oucb f(poo,)) and 0: = I (Pto). Because non-decreasing,
and Pio. 2 Pro by we have
0 2 0z
(12)
Furthermore, denote
2p1p (1 Piş)
11x
20g0,z
11x
A=:= 2
2/ (0o 0.)2
(13)
n40,t
n40,t
nso,t
In the rest of the proof we assume, n4o,t 2 69x since Oo 1, it implies
-,)). Then, using that 0o0, s 0o + 0,
20,0,0r
11x + 0:)
(0o - 0,) 2
T40,2
740,2
2
and
0,
0, + 1/2
Peo + Di,
D S
80 + 02
0, +
Thus, because f is non-decreasing
02 = (p - ((Pua)
f(100 - A1,,) - (Ps0)
Pio + Ase
PiO
1 Pio Di,
1 Pio
Ai,
(1 Pio) Pio A.,e)
(6o 0,)
1- (0o + +O:)
< 2(00 + +0,)² 00)²
13
2000,0
22x(60 + 0.)2
4(00 + -.))
110.tt
7140.
which concludes the proof.
B.3 PROOF OF LEMMA 2
Proof. Let T2 1 and E [K]. Recall that Tie = E 1 (i E S.} is the number of times i
was played at the start of round and m40, = Ee 1i E {ē, 0), E St) is the number of times or 0 won up to round t when played together. or i to win is
When is played the probability
0. +
0 + 8
P(ie E (i,0HS.)) eu + Os.
8 + +
Therefore, applying Chernoff-Hocfdiigg incquality together with union bound (to deal with the fact that Taa is random), we have with probability at least 1 - T
0 0,
T
n. 2
8o + As. Te,t
2
simultaneously for all E [T]. Noting that
0. 0,
T1
0
0, + O Ti.
Ti,t
2
2(0 + Os-)
if Tu. 2 2r(0u )
2n(0, +0 10.
concludes the proof.
16

---

Published as a conference paper at ICLR 2025
B.4 PROOF OF THEOREM g
Proof. Let us define for any $ - [
g
Σ 0, ES
and Og
0.cb
Tet & be the brob--boba event such that both Lemma and 2 holds true. Then,
P(E) 2 47 Let us first assume that holds true. Then, by Lemma
T
1
Reg
top
Os.
m
t=1
T
min s. OucD Os. < because Os- S <0g < O.. under the event &
T
min
Os.
S,t
t=1
iES.
K
1
T40
+
0,)1 (T.e (Buc 1t
Ti, 2 Fi²)
m
m
FE
where 7io = 200 + Og-) ma + O5-, 69} < 138x(m + 1) max: where 0 :- max; O;. Then, noting that if & holds true, by Lemmn which yields
we also have n,o. 2 2(0+0gg.) (0p + 0,)
1[ 700 ( 2 69x(0o + 0.)).
Therefore, we can apply Lemma that entails,
(ree 2 t.0
t= EESt
Lem
20g0zær
22x((0 + 0,)2
4(00 + +..)
(n:0, 2 60x + 0.))
m
72,0,8
iES.
Lem
(0o + O [00 + 0.)000.0
41z(00 + Os- )(0 04)
m
Ti.t
Tτ,
ieS.
K
K Σ
16 (0o + Os. (80) 0g 0,)000,aT,,r + 44r(6n + Os.)
(oo + 01) + log(n.r))
1=1
where used E 1/Vi5 2 and Ei i-1 < 1 logn. We thus have
Reg < 138x(m 1)² K83 max
1
1683/2 V (m + +1)TT,
m
+ 44x(m + 1)(1 + 0max Σ (1 + log(Ti.))
< 138r(m + 1)2 K03
1603/2 max
2r 88.(m + K)K max
(1 + log
mm.
max
K
Therefore,
E Reg top
S 2rmKK 2 + 1603/2
2xKT + 38rmK0f Prax (1+ log
mf
+ 4m 4mm4KK 2 e- 0maxx
Choosing 2lg T concludes the proof.
17

---

Published as a conference paper at ICLR 2025
B.5 PROOF OF THEOREM 4
We start by noting a result that shows that the expected utility R(S",)) that corresponds to the optimal assortment S [argnaass(<K])SSis R(S,0) non-decreasing in the parameters 8.
Lemma 8 (Lemina A.3 of Agrawal et al. 2019 ). Let S = argmmxxc(iK),s|55 R(S,0) 0). Assume 0ucc 2 0, for all i E [], then Ri5". B) ,
Proof of Theorem 4 Let be the high-probabality event such that Lemma satisfied, so that P(E) 2 1- - 4KTe ". Then, denoting x A yy: min(2.y.
and are
Reg
xtd
B B[R(S" -R(S,,))
(14)
[R((S 0) ((5))))((()++(())))) R(S, ((S
Σ [(R(S) 01cb) - R(S,, 0)) R(S" ()) + + (C(S",)1(E"))
$
because R(S,, 0 2 R(S", (eec) 2 R(S" 0) under the event & by Lemma Then, using R(S", 0) max; S 1, get
T
Regr ut4
E ((R(S), R(S,, 0)) ^ +) + +
T
S 4T KE " +
Σ
E ((((S,,
(,00) - (()).))) A x1)
Let us upper-bound the second term of the right-hand-side
r
( (R(See, ,ee0) R(S., 0)) ^ 1{8}
(15)
T
ryOucb
r;0;
E
1181
1(8)
1o + Oueb
S..t
Oo + Os.
1ESt
1: 0.) )
111 118)
because Uuc 2 Os, under
0u + Os.
lucb ist
0:l
11 118
because S 1
0o Os,
FES.
K
T
(Jucb
Osl
E
^
fn - Os
1=1
Jucb 1,1
0cl
138rm² KB2
max
E
0o + Os.
lfe E S,, 2 138x(m + 1) max {8}
1=
T
80
+ + S.}
138rm KO2
E
max
On + Os.
1=1
8,1 Po + Os,
(uuc
20g + Os.
E.
(i E St Tue 2 138m(m 1) n {{{}
Au + 0;
Ar)
(16)
18

---

Published as a conference paper at ICLR 2025
where the last inequality is by Cauchy-Schwane inequality. Now, the term Ar(i) above may be upper- bounded as follows
0 - 0il
2 0o + Os
Ar(1)
Σ
E
{ Th, 2 138r(m + 1) max 118}
0o + O,
Mn + 0,
(0 0.)2
E
1ii St, T4. 2 138x(m + 1) max 118}
0:)00 + Os
Now, since under the event & by Lemma T4a 138x(m 1) mma implies
n0 2 69r + 0:)(m + max 2 69x + 0,).
Therefore, we can apply Lemma which further upper-bounds
2 0,)2
202 + 0,)²
(1 1
740.1
2 ( 0:)
11 ii St, Tie 138x(m
1) max) {8)
Go + Os.
20 2,
15x (0u + 0,)3
1 E St)
1183
x Go + Os.
T40.2
12 max 10o + m0,)
1=1
where used n40,2 2 69xx(00 0:)m0ma max in the last inequality. Then, we get
(0o + 0,)2x
30z(0o + 0.) n4o.t
1 5
(1 $ E
0o Os. 1 (8)
740,1
(0n 0,) S.}
$ (94 + 640.)az
E
(0u + Os, n
li (i,0), S.}
(94 + 640,)aE
= (94 + 640.)z1
1 + log (T))
< m580 + log
Substituting into 16 we then obtain using Cauchy-Schward inequality,
(,0)) R(S,,0)) -
Go + 0.) S
138am² 108am?K00 KQ2 max 13 0 mmxxx (1 + log T')
E
Oo + +0+0s.
ΣK
(0o + 0 0.) 1l S.}
< 138xm² 2 K82 max + 13 0 m1 log Tog
E
K
-
0o + Os.
138am² 2 max 13 0 01 log TT
Finally, replacing into Inequality
15 yields
Reg < 2 + 138zm2 2 K82 max + 13 mmaxx(1 + log TTT
Choosing 2og concludes the proof.
19

---

Published as a conference paper at ICLR 2025
B.6 PROOF OF THEOREM 5
The proof follows the one Theorem except that the concentration lemmas should be generalized to any pairs (i,j) instead of only with respect item whose proofs left to the reader and closely follows the one Lemma [ and 2 For simplicity, this proof is performed up to universal multiplicative constants, using the rough inequality S
Lemma 9. Let T 1 and > O. Then, with probability at least 1 - 3K(K + 1)Te"* simaltaneously for all t [T] and i + j in [K] Ni 0a ucb and one of the following two inequalities is satisfied
Vigt
22x("/i 1)2
nija < 69x 7(4)
ucb S Vap 4 + 1
nij.
nijat
Lemma 10. Let 2 and x O. Then, with probability least 3K(K 1)Te Huch 4,
simultaneousll for all & E [T] and i E [K]
2 0; and for all j one of == miny 7ij.t 20,2
ucb,, Nch
the following two inequalities is satisfied
naja S xx1 + 7())
nyo.t S x=(1+0,)20
or
(1(00 + 0,)
(0, Miij.
(1 + 0z) Oz)) n1o.tt
(0. + 0,)zz
Tky Th + (1++0))22
sch McB. 13j.t 150, 0₂ S (7is + 1)0,z
(V
+ +
nija
nyo,e
Proof of Lemma 10 The proof follows from Lemma g Cr(1+ + +,) for some large enough constant C, we have
If majaa > Cx(1 + 7is) and nyo,
2 nijut
22x(Ti + 1)²
S 7a + 4(708 + + 7aj.
ueb
+
Rij.et
and
27,02
22x(770 + 1)2
70.t I 950 + 4(750 + 1)
ucb
+
< 2750-
n-3.tt
nyo.t
This implies,
ucb Tig. 7j0,t
0:
Vij.t 1j0,t
ucb ucb
150 (1
Vkg 1
7i5 -30)
s 2(
ucb
Vio Kig))o0 + Tiy (65(730.1
730)
2x0 44 + 1)2
< 8730(1ij + +1V
Niget
nigut
27,02
22x7/5 + 1)2
+ 4730 + +1
nyo,t
Nyj0tt
Replacing "a 0,/0, and 750 0g concludes the proof.
Lemma 11. Let 2 1 and x > Then, with probability at least - K(K + 1)Te-*
(0p + O5-)²
(0, + 0,)
Tija < 2x
or nij.t 2
(17)
0, + 0
2(0 + +
where Tija = E ((i,)) C S.} simultaneously for all E (T) and i j [K].
Let & be the high-probabality event of Lemmas T0 and satisfied, that TP(E) > - First, note that since have under the event. E, @ueb glcb our procedure also satisfies the regret upper-bound
Proof of Theorem 5
Reg vtd
< O( 0max KT log T)
20

---

Published as a conference paper at ICLR 2025
of Theorem 4 Indeed, all upper-bounds of the proof of Theorem 4 remain valid upper- upper-bounde bounds except the probability of the event E which is O(T-1) ') for x = T.
Let us now prove that we also have R S O(KyTlogg with no asymptotic dependonce on i max when T + 00.
Then,
vtd Regt
Σ
E [ -
() R)
(18)
t=1
Σ
E (R((SS, 0) R(S. ()) + (R(S", 8) ()
T
$
Σ
((R(S), - R(S,,0) A R(S", ()) + R(5", (() ((5",0)1(E"))
1=1
Then, using R(S",0) 0) S max; ri 1, we get
7
Regt std
1
(IR(S,, 0,c - R(S,, 8)) A +
S <TTK(K+
Σ
(R((),, R(S,, A 11)
(19)
Follow the proof of Theorem upper-bound the second term of the right-hand-side
of
E
((R(S,, R(S,, 0)) A A 1{8)]
(20)
r,Oaco
Ejes, 0,) ^l A1)
r,0;
1183
min jE(K]
ieS, 1+ Ejes, Juch
ri (0 - 0i)
E
^I 118)
because
@ucb
2 0ss under E
0o + Os.
rES.
10ncb 0:1)
1 A1) A1)1181 1[8)
because ri <
Ou Os,
IES.
K
Oucb 0:l
^ 11 11) (i(iEs))11))
Oo + Os.
K
Aige.t "j.... 0:l
ucb
Oo + Os. ^1 ) L
S,)1(8}
where je je 8j. where the last inequality is by definition of @och. Now, from Lemma 10 paying additive exploration cost to ensure that nijat 2 xx + 75)) and
nyo.t 2 x(1 + 0, 20 for all j E St such that 0g 0. From Lemma I1 this is satisfied if for
some constant C 0
Tig. Cm max
Such a condidtion can be wrong for couple (i,j) S at most during 2 O(log T) rounds (since Tij, increases then). Thus, for C large enough,
m Z
T
(RR(S, Jnob) R(S,, ^ 11)
21

---

Published as a conference paper at ICLR 2025
K
ueb ueb Jfjed J.0,e
Ozl
& O 7) +
1iiE Se, Tajert A Teet 2 Cam2
max {1{
8o + Oss
1=1
(0: + (0:+
+0,)
(1 + 0j) R'j0,t
< OlogT)) +
E
V (Tige + 1)0,0 (V
Bije,t
(0: + Oje )x
Nij. (1 + 0j.)
1 E Si}
+ (7b5e + 1)
nije.t
M).0,t
9o + Oss 1 S
K
(0, + (g.)
0z.))
S O T)
V (75, + 1)0,z(
Mijeit
0o + Os.
where the last inequality is because using that {i, 0} E Se: we have
T
1+ 1+0
T
K
li E {i.0}}
1 = 103 s (o1
(1
Os. )nj.0.1
nyo,e
j=
and
T
0, + 0j
T
lle E (1,0))
14j = 311 $ <K(1 + log T)-
E
Oo, )rij..
nz0,t
Then, by Cauchy-Schwarz inequality we further get
(R(S R(S,, 0)) A 11)]
E
K
(ee + 1)0; E S.Jar
$ TlogTT) +
E
(21)
Ou + Os.
T
(0s + 0g.).
(1+
1 lfi s.}
x
I
Mijie
0g + Os,
K
T
(Nes, + 1)0,1fiE E S.ke
< OloggT +
E
K logT
Oo + Os.
K
8,1 Site
+ $ OllogT)
Σ
E
K logT (because Yi S 1 by definition of jr)
Go + Os.
= O( OKKTT
(22)
where the last inequality is by Jensen's 's inequality and the equality by setting x 2 2og T to control the probability that E occurs. This concludes the proof.
22


Reviews:
[{"review_id": "07sw08Sisb", "reviewer": "Reviewer_t5dy", "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.", "questions": "Please address the weaknesses above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "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).\n\n- 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.\n\n- 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.\n\n- All the experiments in this paper are synthetic. Might the authors add some experiment results based on real-world datasets?\n\n- [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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5Iwa4vA5Sm", "reviewer": "Reviewer_KjYH", "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.", "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.\n* 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?\n\n[1] https://core.ac.uk/download/pdf/82425825.pdf", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "icS3Iws2Zs", "reviewer": "Reviewer_X5Yt", "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.", "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.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "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).\n\nOn 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7uYGtEvWzN", "reviewer": "Reviewer_Jq9h", "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.", "questions": "See weaknesses.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "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?\n2. 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. \n3. 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.\n\nOverall, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)