Optimal, Efficient and Practical Algorithms for Assortment Optimization

Thanks for your review

Weaknesses --

Q1. Non supported claims in line 21

-- Sudies in brain, psychology and cognitive neuroscience corroborate the fact. We will add references such as:

• Kahneman and Tversky. The psychology of preferences. Scientific American 1982

• Musallam, Corneil, Greger, Scherberger, and Andersen. Cognitive control signals for neural prosthetics. 2004.

Q2. Reference issues

• About [11]. We believe that [11] is a valid reference for Battling bandits (BB). First, DB is a special case of BB. More importantly, if you note Tables 8,9 of [11] that mentions BB algorithms in details, in general Sec 6 of [11] elaborately discusses BB.

• Note also that [45,46] are valid references for DB, in fact, we cited [41, 3, 45, 46, 44] as DB in Line 31, where we introduced DB for the first time.

• About using consistent citations. Thanks for the suggestion, will make sure to cite accordingly.

Q3. Differences between the algorithms in Table 1

-- See global rebuttal

Q4. Generalization to other models

-- See global rebuttal

Q5. Misalignment between platform and user utilities

-- Please note we have a concept of revenue/weights ($r_i$ for each item $i \in [K]$) that captures the utility of the sellers, while $\theta_i$ captures the utility of the customers. So the MNL formulation does consider the utility of both users and the customers.

However, if the reviewer is asking how to develop an algorithm that simultaneously offers the `best-valued' assortment to the customers while maximizing the revenue of the sellers, that can be either (i) formulated as a multi-objective problem that balances the tradeoff between both utility notions or (ii) simply assume the seller weights/reviews ($w_i$s) are an increasing function of the customer scores/values ($\theta_i$s), in which case maximizing one notion will, in turn, maximize the other with our Wtd-Top-m ($Reg_T^{wtd}$) objective. Please let us know if you have any other questions in mind

Q6. Computation cost of the argmax

-- Please note this step is efficient since it is just a static assortment optimization problem under MNL model with known parameters, as already established in the literature:

• Avadhanula, Bhandari, Goyal, Zeevi. 2016. On the tightness of an LP relaxation for rational optimization and its applications. Operations Research Letters.

• Rusmevichientong, Shen, DShmoys. 2010. Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Operations research.

Thanks for the comment, we will add the citations in the final draft.

Q7. Intuition behind the algorithm

-- Please see the global rebuttal

Q8. Experiments reflecting the problem

-- We are unaware of any open-source datasets suitable for validating our algorithms in this specific problem setting. The challenge lies in the inability to know the ground truth parameters $(\boldsymbol{\theta})$ of the MNL model, making it difficult to evaluate regret performance. This is why prior works, such as [1] and [24], either did not report experiments or only used synthetic data. While [2] claims to use the UCI Car Evaluation Dataset, they actually conducted a synthetic experiment by modifying item features and assigning synthetic scores to the PL parameters (see Sec 7.3 [2]).

Also our primary focus has been theoretical and experiments support our theory. If the reviewer knows of any suitable datasets, we would be happy to report comparative performance on those.

We will enlarge the figures. Thanks for the suggestions

Q9. Other algorithms in the experiments

-- As we elaborated in the global rebuttal, the algorithms of [2] and [24] for our problem setting are the same. Further [1] is only a TS variant of [2] with an identical algorithm structure which thus suffers from the same issues. We will be however happy to add MNL-TS in our experiments.

Questions --

Q10. How the framework applies to the applications in the Intro?

As per the examples discussed in Sec1, e.g. Web search, online shopping 36 (Amazon, App stores, Google Flights), recommender systems (Youtube, Netflix, Google News/Maps, Spotify), typically involve users expressing preferences by choosing one result from a subset of offered items in terms of a purchase or click which we capture thought the MNL-choice model.

On the other hand, the system (algorithm) designer, which could be the platform or the seller, may want to converge to the ‘most-profitable’ or `revenue-maximizing' set, which is captured through our regret objective: Top-m ($Reg_T^{top}$) could be relevant for Google, Netflix, Spotify, News/Maps Recommendation etc (to maximize click through rates), while Wtd-Top-m ($Red_T^{wtd}$) could be relevant for Amazon, Walmart, Google Flights, App Stores where the objective is to maximize the total revenue.

Q11. Comparing MNL-UCB [2]

-- Pls see Q3 or Global Rebuttal

---

We urge you to kindly reconsider the score based on the rebuttal

Dear Reviewer L6d3,

I am writing you to kindly request your feedback on our rebuttal. As the discussion phase is currently underway and we have a limited timeline, I am eager to address any remaining concerns you may have. We believe to have answered all your queries and are happy to provide any further clarifications in the hope of potentially raising your scores.

Requesting you to kindly engage in a discussion at your earliest convenience.

Thank you for your consideration of this matter.

Thanks, Authors

While the above discussion establishes the novelties of Alg1, we also observe a potential limitation of our Alg1 that paved the path for our final algorithm Alg2 (AOA-RBPL-Adaptive,Sec4). But it will be worth understanding the limitation of Alg1 first before we proceed to the intuition behind Alg2.

---

Limitation of Alg1 (for certain realizations of MNL parameters $\boldsymbol{\theta}$): While Alg1 carves out the basic building block of our $\theta_{i,t}^{ucb}$, one caveat lies in its concentration rate which shrinks at the rate of $O(1/\sqrt{n_{i0,t}})$ --- as established is Lem8, $n_{i0,t}$ being the number of rank-broken pairs of $(i,0)$ till time $t$ (Line174-175). Thus ideally we would need $n_{i0,t}$ to grow fast for a fast and tight convergence of $\theta_{i,t}^{ucb}$ to $\theta_i$. However, as Lem2 reflects, this might not be true unless either $0$ (NC) or $i$ is a `strong item' with sufficiently large MNL parameters (comparable to $\theta_{\max}$). This is since, as Lem2 shows $n_{i0,t}$ (roughly) grows proportional to $\frac{(\theta_i + \theta_0)}{\theta_{\max}}$ which could be quite small if both Item-i and 0 (NC) happens to be a "weak-items" in terms of their MNL scores, i.e. $\max\{\theta_i,\theta_0\} << \theta_{\max}$. If we think, this is also intuitive since, if both $\theta_i$ and $\theta_0 = 1$ are small compared to $\theta_{\max}$, chances are very low that either of them will be picked as a winner of any round $t$, even if $i \in S_t$ and as a result they will never be "rank-broken" against each other resulting in a very small value of $n_{i0,t}$, weaker UCB estimates $\theta_{i,0}^{ucb}$ and finally a weighted regret bound of $Reg_T^{wtd} = \tilde O(\sqrt{\theta_{\max} KT})$ (Thm5) which could be large when $\theta_{\max}$ is large!

---

Understanding the problem, we remedy this with Alg2 (AOA-RBPL-Adaptive) in Sec4, where we devised a smarter UCB estimate of $\boldsymbol{\theta}$, while still keeping the basic intuitions from Alg1 (AOA-RBPL) intact:

$\boldsymbol{\theta}\_t^{ucb}$ justification for Alg2: As explained above, we realized "pivoting" on the NC for estimating $\theta_i$ could be a bad idea, especially if $1 = \theta_0 << \theta_{\max}$. Towards this, we made the following (seemingly interesting) observations:

• (1) We first note that: $\theta_i = \frac{\theta_i}{\theta_0} = \frac{\theta_i}{\theta_j} \frac{\theta_j}{\theta_0}$ for any $j \in [K] \setminus \\{i\\}$.

• (2) Then drawing motivation from the UCB estimates of Alg1, we further set $\theta_{i,t}^{ucb} = \gamma_{ij,t}^{ucb}\gamma_{j0,t}^{ucb}$, where $\gamma_{ij,t}^{ucb} = \frac{p_{ij,t}^{ucb}}{(1 - p_{ij,t}^{ucb})_+}, ~\forall i,j \in [K]\cup\{0\}$ (display after Line252).

• (3) The hope is if we can find a "strong element j" and pivot our rank-broken pairwise estimates ($p_{ij,t}^{ucb}$s) around $j$ for all $i \in [K] \cup \{0\}$, hopefully the that will remedy the caveat of Alg1 as detailed above.

• (4) To find such a "strong pivot j" (such that $\theta_j$ is comparable to $\theta_{\max}$), we set a dynamic $j = \arg\min_{j \in [K] \cup\{0\}} \gamma_{ij,t}^{ucb} \gamma_{j0,t}^{ucb}$ for each item $i \in [K]$ and time $t$, which by definition happens to be a relatively stronger item than Item-$i$ and 0 (NC).

• (5) Further, similar to Lem1, we also find the rate of concentration of our new UCB estimates $\theta_{i,t}^{ucb}$ in Lem10 (see Appendix B.6), which, as intuitive, is shown to shrink at the rate of $O(\frac{1}{\sqrt{n_{i,j,t}n_{j0,t}}})$. The nice trick was to note that this yields a sharp concentration for $\theta_{i,t}^{ucb}$ owing to our clever choice of the dynamic pivot j as described in the point above -- this saves us from the caveat arose in Alg1 due to a poor choice of the static NC pivot (Item-0).

• (6) Finally the above sharp concentration of $\theta_{i,t}^{ucb}$ in Lem10 ensures the final weighted regret of $Reg_T^{wtd} = \tilde O(\sqrt{\min\\{\theta_{\max},K\\} KT})$ (Thm6), which could be notably at most $\tilde O(K\sqrt T)$ even if $\theta_{\max} \to \infty$. Here lies the drastic improvement of our algorithm compared to [1,2,24] which either needs to assume $\theta_{\max} = \theta_0 = 1$ or their regret scales as $O(\sqrt{\theta_{\max}KT})$ which yields a trivia regret as $\theta_{\max} \to \infty$ or even if $\theta_{\max} = \Omega(T)$. We detailed this after Thm6, as well as empirically validated in Sec6.

---

---

We hope that was helpful and clarifies your doubts around our choice of UCB estimates $\boldsymbol{\theta}_t^{ucb}$ for both Alg1 (AOA-RBPL, Sec3) and Alg2 (AOA-RBPL-Adaptive, Sec4).

Finally, we would like to convey that, we have put considerable effort into developing our work as well as addressing the reviewers' questions. We hence urge you to kindly reconsider your scores based on the above clarifications if you find them useful. Please let us know if you need any further explanation or any remaining clarification you may require.

Thanks, Authors

Dear Reviewer L6d3,

Thanks for considering our rebuttal and your question. We apologize for the confusion regarding Q3 or R2 (we meant "our answer of Q3 of Reviewer-mX9J"). We explain below the intuition behind $\theta_{i,t}^{ucb}$ in detail:

Note 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}, \forall 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]$. Further note, 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 Line153).

---

How $\boldsymbol{\theta}^{ucb}$ was used in the regret analysis (Thm5, Thm 6): 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 Thm5 and Thm3 (resp. for Alg1 and Alg2):

• (1) Towards this, an important observation to note is both our regret proofs (i.e. proof of Thm5 and Thm6) use 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 inequalities used in the displays of Eq14 and Eq18, in proof of Thm5 and Thm6 resp., 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 Lem4: Essentially it shows 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 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 some important properties of the MNL model before that.

---

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

• (1) 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 of MNL choice model (Eq1).

• (2) But since $\theta_0 = 1$ (Line153), this implies $\textbullet ~\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 (Please see our response to Q5 of Reviewer-dQv5 for details). We denoted them by $\hat p_{ij,t}$ at round $t$ (see Line171).

---

We first understand the rationale behind our choice of $\boldsymbol{\theta}$ 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 Lem8 (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), 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 8 in Appendix B.1, B.2).

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

---

Alg1 contributes to our basic intuition behind dynamically estimating $\boldsymbol{\theta}_{t}^{ucb}$s using the novel rank-breaking technique and alleviates the problem of repeatedly querying same subsets $S_t$ in consecutive rounds as used in the previous works to estimate MNL parameters $\boldsymbol{\theta}$ along this line [1,2,24]. We detailed this in Line105-107 as well as in our Global Rebuttal (please see Limitations of previous algorithms).

Thanks for your positive detailed review and the insightful questions.

Q1. Missing terms in the regret bounds in Table 1

-- You are right. We only included the main leading term for conciseness, ignoring logarithmic and constant terms. We will clarify this in the caption.

Q2. Multinomial vs Plackett Luce

-- Thanks for the suggestion, we will call the model as MNL throughout the paper to avoid any confusion.

Q3. Justification for defining $\theta^{ucb}$ (after line 253)

Since we compare i with 0 through j, when j is a "strong item" that is often selected as the winner, both $\gamma_{ij,t}^{ucb}$ (that estimates $\theta_i/\theta_j$ by above) and $\gamma_{j0,t}^{ucb}$ (that estimates $\theta_j/\theta_0$ by above) are sharp estimators. Hence, $\theta_{i,t}^{ucb} = \min_j \gamma_{ij,t}^{ucb} \gamma_{j0,t}^{ucb}$ is a sharp upper confidence bound for $\theta_i$.

This definition of $\theta_{i,t}^{ucb}$ in turn satisfies the condition of Lem4, which requires $\theta_{i,t}^{ucb} \geq \theta_i$ for $Reg(S^*, \boldsymbol{\theta}) \leq Reg(S^*, \boldsymbol{\theta}^{ucb})$ to hold good. Lem 4 is further crucially used our final proof of Thm6 (see the inequality used in Eq18, Appendix B.6). This Lemma would not hold if we used $\gamma_{ij,t}^{ucb}$ directly without multiplying by $\gamma_{j0,t}^{ucb}$ since it would not be a valid upper bound of $\theta_i$.

Q4. The title is quite general

-- We understand. We will be happy to include the term "online assortment optimization" and also "MNL model" to the title. Thanks for the suggestion.

Minor: Line 196 which should be $\tilde O (\sqrt{KT})$

-- Yes, that is correct, thank you for noting the typo, will update accordingly.

---

We thank you again for your positive review, please let us know if we could clarify anything else.

Dear Reviewer mX9J,

Thank you for taking the time to read our rebuttal, we appreciate your time and attention. We would also like to draw your attention to our "Follow-up clarification for Reviewer-L6d3 (Intuition behind $\theta_{i,t}^{ucb}$)" where we provide a very detailed explanation of the rationale behind our specific choices of $\theta_{i,t}^{ucb}$, both for Alg1 (AOA-RBPL, Sec3) and Alg2 (AOA-RBPL-Adaptive), from an intuitive viewpoint. If you have time, please go over it as you may find it useful for your Q3 as well.

Thanks again for your feedback, Authors

We thank the reviewer for the comments.

Weaknesses --

Q1. "Drawbacks may not be real. .. very limited value"

-- We respectfully but absolutely disagree. We strongly believe the comment 'the drawbacks may not be real' only depicts a very personal viewpoint of the reviewer which we believe should be considered unfair. Especially since the reviewer did not provide any justification behind such claims. The likelihood of "No Choice" (NC) varies by application. It may not always exist, and its preference depends on the context:

• In recommender systems like YouTube, Spotify or Netflix, users typically make choices.
• In news, music, flight, or Google Maps recommendations, NC is unlikely, almost never selected as the person needs to commute or book a flight nevertheless!
• Similarly, in many language models or chatbot applications, NC is improbable.

-- This is also the reason the original MNL-UCB paper tried to relax the assumption of \theta_0 = \theta_\max but their regret bound stands vacuous in the regime of small $\theta_0$. A key motivation of our contribution is that our algorithm (Alg 2, AOA-RBPL-Adative) works in the $\theta_0 \to 0$ regime (equivalently $\theta_{\max} \to \infty$) (see Thm 7) where we achieved largely improved regret bound of $\tilde O()$ compared to the vacuous $\infty$ regret bound of Agrawal et al (2019). It is also supported by our experiments (please see Fig 2, Sec 5).

Thus we believe it is unfair to overlook the merits and nice ideas we offered in this work that help us to overcome the limitations of the previous works. Please also refer to the Global Rebuttal for a detailed comparison of our algorithm and results with that of state-of-the-art approaches (in Table1).

Q2. "It seems that this regret bound is weaker ... last comment".

• Continuing from Q1, reviewers point of view and fairness is still on question. Firstly this statement "regret bounds proposed by the paper is actually $K\sqrt{T}\log T$" is incorrect. In the MNL bandit setting of [2] where $\theta_0 = 1 = \theta_{\max}$, our regret is actually $\tilde O(\sqrt{KT})$. Further in the limit of large $\theta_{\max}\rightarrow \infty$, our $\tilde O(K\sqrt{T})$ regret bound (Thm6) is way too better compared to the vacuous infinite regret bound of [2]. Despite the attempt of [2] to lift the assumption of $\theta_0 = 1 = \theta_{\max}$ (Sec6.2, [2]), they derived a vacuous bound and failed to achieve our regret bound of Thm6. It seems totally unfair and unjustified that the reviewer questions our improved bounds under relaxed assumptions, rather than appreciating the novel techniques we offered to achieve our results.

Q3. Experiments conducted on specific values of $\theta$ and hence not very convincing

-- Again, we believe the comment is unreasonable. Synthetic experiments have to be reported for some specific choices of the parameters by virtue; same has been done in the [2,24] as well where they forcefully set $\theta_0 = 1$ which is specific to their problem assumption. If that is justified, we only relaxed that assumption in our experiments, adhering to our problem setting, as expected. And clearly, the previous work performs poorly in those regimes, due to their restrictive assumptions. This is the genuine way to corroborate the claims of any theoretical guarantees, we are completely unable to see the rationale behind the reviewer's point of content, once again!

Questions ---

Q4. Feedbacks from the same customer may be correlated

-- By definition of the MNL-AOA problem, it assumes at each round, given $S_t$ the choice-feedback is sampled independently from the underlying MNL$(\boldsymbol{\theta})$ choice-model. Assuming correlated feedback deviates from the MNL assumption, leads to a different choice model. There are several ways to model such dependencies including (but not limited to) taking cues from rotting/rising/restless/sleeping bandits theory. Each of these directions are an independent body of work and will lead to new research problems of AOA. But it simply lies beyond the scope of this work.

Q5. Explain the differences and novelties of your algorithm compared to the classic UCB?

-- Please check our Global Rebuttal for a detailed discussion on our algorithmic and analytical novelties over classic UCB algorithms.

---

We understand the reviewer is inclined to reject the paper, but we do not see a single rationale or logical argument behind the decision. In particular, claiming that `generalizing a setting' will not be helpful (even with clear experimental backup) seems to be a personal viewpoint and unjustified. A personal view can not be pitted against facts that we presented through our examples, relaxing the limitations of the previous works, theorems, and experiments. We urge the reviewer to kindly clarify from a technical (and not a personal) viewpoint if there are any remaining concerns you may have or would you kindly reconsider the score, please?

Thanks for your review. Please see our responses below. Please note the misunderstanding and we tried our best to clarify it. We will be glad to clarify any further questions.

Q1. Clarification of variable $x$ in In Eq3

-- $x$ is the input to the algorithm. It can be any positive number for which Lem1 holds good. In Thm1 we specifically mentioned the choice of $x = 2\log T$ for the regret bound of Alg1. We agree, we should not have used a forward reference and will add the line ``$x> 0$ can be any positive number as defined in Lem1" before Eq3 Thanks for noting this.

Q2. What is the + sign between line 176 and 177

-- For any real number $a \in \mathbb R$, $a_+ := \max(a,0)$. We assumed the notation is standard in bandit literature, but we will certainly clarify this in the notation section to avoid any confusion.

Q3. Upper bound on $\hat p_{ijt}$ in Eq3 and Lem1

-- Please note there is a misunderstanding as you seem to have confused definitions (Eq3) and concentration bounds (Lem1). Firstly, (a) By Eq3, you may mean the display after Eq.3 that defines $\theta\_{i,t}^{ucb} = p\_{i0,t}^{ucb}/(1-p\_{i0,t}^{ucb})\_+$. Please note this is the definition of $\theta_{i,t}^{ucb}$. Similarly, Eq3 gives the definition of $p_{ij,t}^{ucb}$. These turn out to be both upper bounds for $p_i$ and $\theta_i$ respectively as proved in the proof of Lem1 (AppB.2). Only the one of $\theta_i$ is important in the rest of the analysis and thus displayed in Lem1.

Q4. Comparision with [2]

-- We describe the intuition of our algorithm in detail in the global rebuttal, as well as pinpoint our algorithm novelties and advantages over [2].

Q5. Confusion about by the high probability upper bounds in Eq (3)

-- Please read Q3 above, as detailed, Eq3 does not provide any high probability upper bound but a definition of $p_{ij,t}^{ucb}$. Let us know if anything is not clear still.

Q6. Explanation about rank-breaking (RB), how that make your work different from [2], and how it show up in Eq(3).

• Please note RB is described in Appendix A.2. It is the idea that involves extraction of consistent pairwise comparisons from (partial) ranking data, as obtained by treating each pairwise-comparison in the (partial)-ranking independently. E.g. in a set $S = {1,2,3,4}$ if 1 is the choice winner, then RB extracts the pairs $(1 \succ 2)$, $(1 \succ 3)$, $(1 \succ 4)$. Similarly for a full ranking feedback, e.g. $4 \succ 2 \succ 3 \succ 1$, RB extracts all the 6 pairwise comparisons $(4 \succ 2)$, $(4 \succ 3)$, $(4 \succ 1)$, $(2 \succ 3)$, $(2 \succ 1)$, $(3 \succ 1)$.

• RB is used to derive our empirical pairwise estimates $\hat p\_{ij,t} = w\_{ij,t}/n\_{ij,t}$ (Eq3), where $w_{ij,t}$ and $n_{ij,t}$ denotes the total pairwise win counts of item i over j after rank-breaking and total number of rank broken pairs of $(i,j)$ respectively, till time $t$. We will add these descriptions in the main draft (in Sec 3.1) for ease of exposition.

• Re. How RB is used and give us advantage over [2]: We figured the novel Rank-Breaking (RB) technique to derive an important key idea which (roughly) says that the empirical pairwise preferences of item pair $(i,j) \in [\tilde K]\times [\tilde K]$, see $\hat p_{ij,t}$ in Eq3, gives an unbiased estimate of the true pairwise preference $p_{i,j}: = \theta_i/(\theta_i + \theta_j)$. This leads to sharper and more efficient UCB estimator of $\theta_i$, given by $\theta_{i,t}^{ucb} = \min_{j \in [K] \cup \{0\}}\gamma_{ij,t}^{ucb}\gamma_{j0,t}^{ucb}$ where $\gamma\_{ij,t}^{ucb}:=p\_{i0,t}^{ucb}/(1-p\_{i0,t}^{ucb})\_+$ (Line 253). We further prove in Lem9 and Lem10 how $\theta_{i,t}^{ucb}$ yields a much sharper and flexible UCB estimator of $\theta_i$ for each $i \in [K]$ without the requirement of $\theta_0 > \max_{i \in [K]}\theta_i$ unlike all the previous works. Please also see Q3 of R-mX9J to get more intuition of our $\theta_{i,t}^{ucb}$ estimate --- Here really lies our main contribution that helps us to overcome the existing limitations of the previous works (see Table1) and leads to multiple advantages as listed in the global rebuttal.

Please also read the Global Rebuttal which summarizes the existing algorithms and how we overcome the limitations of the state of the art methods ([1,2,14], etc).

---

We believe we have answered all your questions, please let us know if you have further questions. Otherwise, kindly reconsider your scores in light of the clarifications.

Dear Reviewer dQv5,

We are writing you to kindly request your feedback on our rebuttal. As the discussion phase is currently underway and we have a limited timeline, I am eager to address any remaining concerns you may have. We believe to have answered all your queries and are happy to provide any further clarifications in the hope of potentially raising your scores.

Requesting you to kindly engage in a discussion at your earliest convenience.

Thank you for your consideration of this matter.

Thanks, Authors

Dear Reviewers,

By Q3 of R2 in our global rebuttal above, we meant "our response for Q3 of Reviewer-mX9J".

We would also like to draw your attention to our "Follow-up clarification for Reviewer-L6d3 (Intuition behind $\theta_{i,t}^{ucb}$)" where we provide a very detailed explanation of the rationale behind our specific choices of $\theta_{i,t}^{ucb}$, both for Alg1 (AOA-RBPL, Sec3) and Alg2 (AOA-RBPL-Adaptive), from an intuitive viewpoint. Please refer to that response for an in-depth understanding of our algorithmic novelties, new parameter estimation ideas, as well as the logical sequence of proof techniques (for Thm 5 and Thm6).

Thanks Authors