Improved Confidence Regions and Optimal Algorithms for Online and Offline Linear MNL Bandits
Authors: Yuxuan Han
Jose Blanchet
Zhengyuan Zhou
Venue: NeurIPS 2025 poster ()
Keywords: MNL Bandits
Assortment Optimization
SupCB
Primary area: general_machine_learning

Abstract: In this work, we consider the data-driven assortment optimization problem under the linear multinomial logit(MNL) choice model.
We first establish a improved confidence region for the maximum likelihood estimator (MLE) of the $d$-dimensional linear MNL likelihood function that removes the explicit dependency on a problem-dependent parameter $\kappa^{-1}$ in previous result  (Oh and Iyengar, 2021), which scales exponentially with the radius of the parameter set.
Building on the confidence region result, we investigate the data-driven assortment optimization problem in both offline and online settings. In the offline setting, the previously best-known result scales as $\tilde{O}\left(\sqrt{\frac{d}{\kappa n_{S^\star}}}\right)$, where $n_{S^\star}$ the number of times that optimal assortment $S^\star$ is observed  (Dong et al., 2023). We propose a new pessimistic-based algorithm that, under a burn-in condition, removes the dependency on $d,\kappa^{-1}$ in the leading order bound and works under a more relaxed coverage condition, without requiring the exact observation of $S^\star$. In the online setting, we propose the first algorithm to achieve $\tilde{O}(\sqrt{dT})$ regret without a multiplicative dependency on $\kappa^{-1}$. In both settings, our results nearly achieve the corresponding lower bound when reduced to the canonical $N$-item MNL problem, demonstrating their optimality.

Improved Confidence Regions and Optimal Algorithms for Online and Offline Linear MNL Bandits
Yuxuan Han New York University yh60610stern.ny nyu. edu
Jose Blanchet Stanford University jose. blanchet@@tanfordd.. edu
Zhengyuan Zhou New York University zzhou@stern, nyu. edu
Abstract
In this work, we consider the data-driven assortment optimization problem un- der the linear multinomial logit (MNL) choice model. We first establish an im- proved confidence region for the d-dimensional linear MNL likelihood function that removes the explicit depen- dency on a problem-dependent parameter x in previous result [42), which scales exponentially with the radius of the parameter set. Building on the confidence region result, we investigate the data-driven assortment optimization problem in both offline and online settings. In the offline setting, the previously best-known
(MLE) of the
A7g- where ni.- denote the number of times that optimal assortment S* is observed [26]. We propose
result scales as Ö
pessimistic-bait based algorithm that, under burn-in condition, removes the dependency on d, k in the leading order bound and works under more relaxed coverage condition, without requiring the exact observation of S* In the online setting, we propose the first algorithm to achieve Ö(VTT) regret without a multiplicative dependency on x-1 In both settings, our results nearly achieve the corresponding lower bound when reduced to the canonical N-item MNL problem, demonstrating their optimality.
1 Introduction
In modern data-driven decision- decision-making problems, a key challenge for sellers, often managing a large inventory, is determining subset of products, also referred to assortment, display to customers. For instance, when customers search for "laptops" on an e-commerce platform, the system must select an assortment from thousands of options to present. Due to space constraints cognitive overload, only a limited number of items-at most K c-can be displayed at a time. This motivates the study of assortment optimization with cardinality constraints, where the seller aims identify the optimal assortment of K items to display in order to maximize revenue.
The revenue of an assortment S depends both the revenue of each item i S and the final choice made by the customer after observing S. While the revenue of individual items is often known to the seller, the customer's choice behavior is unknown and must be estimated from data. A large body of work has focused on modeling customer choice behavior in the context of assortment optimization
22 25 [2). Among these models, the multinomial logit (MNL) model and its linearly parametrized variant stands out as a widely used approach and serves as a foundation for understanding more complex models due to its clear mathematical structure, computational simplicity, and case of calibration [T]].
40 52
In the linear MNL choice model with N items, each item E [N] is associated with an d-dimensional feature 2;, and its utility, presenting its attraction to customers, is given by f/ = x.! 0* for some
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Learning
Leoding Order Upper Bound
Lower Bound
Remark
26
Oi Dapteeoss]] O[K/vae)
Rig 1(Su 8-)
O(K/v/o)
N-item setting, millgge Zomm 1(8
O Encs M48 (e (1 Aes
condition may may puties sig.llllllgy
Our work
21 Eies (u("")p(("))
Og Zics pil5 (a15") T (api
Online Learning
Lending- Order Upper Bound
Lower Bound
Remark
3
O(VNT)
Rt/N7/K
N-item setting
Riv
N-item setting
Otay?)
R(vT/RK
Advensrial context initial explonation
O(e-)va log
Advensorial contest with inidial explonation
((KiVT)
Adversanial context with uniform reward
Oçdy?"
((A/7)
consext
Our work
Ö (vZT"ogg))
Pixed design
Adversarial context with initial exploration
Table 1: Comparison of offline and online assortment optimization results, where P;(S) denote the choice probability of item under assortment S; only leading-order terms are presented for notational simplicity.
i The k' notation in 26 defined in different way those in other works, but the still suffers from the exponential dependency on ||0*| || in the worst case.
When consider the canonical N-item setting with 2;, e,, d N, the ((vNT) result in 17 implies this
result.
We leave the related algorithm design and proof to Appendix E.4 space limitation.
underlying 0* E Rd. After given an S, the choice of the customer then follows the standard multinomial distribution as described in (1). While data-driven assortment optimization with the linear MNL model has been extensively studied [4 46
5 48), most of the existing literature focuses on the online learning setting. The current best- regret bounds are given as O(dvT Ax VTT N). When specialized to the canonical N-item setting (d N x; = e; being the canonical basis), the regret either exhibits an additional vd dependence or incurs multiplicative dependence on x problem-dependen quantity defined in (2) which may scales exponentially with ||0*]. Besides the online setting, the only known works in the offline learning setting [26 29
50
either focus on the canonical N-item setting or rely on restrictive assumptions about the coverage of the data.
Motivated by these gaps, we propose new algorithms in this work that achieve improved online regret and offline sample complexity guarantees. Our methods build on sharper analysis of the linear MNL likelihood function, which serves as the foundation for most existing approaches under the linear MNL model. We compare our results with previous works in Table T and summarize our contributions as follows:
1.1 Our Contributions
Sharper Confidence Region result for Maximum Likelihood Estimator. Our first result is an improved confidence region for the linear MNL maximum likelihood estimator (MLE), which incorporates variance information and avoids explicit dependency on к. More precisely, given the conditional independence of the observed choice dataset D == {is, S 1 we show that the corresponding maximizer Ô of the linear MNL likelihood function, under burn-in condition, satisfies V||ar|| S 1, with Hp the Hessian matrix of the log- ligliikeddood function given D. Our result provides an non-asympiotic variant of the large-sample asymptotic v. T (0 - 0*) - (O, || (r which holds for general M-estimators under certain conditions [37]. and improves the best previous non-asymptotic result under the same assumptions, stated as (0- 0*) I Ō ([===|[[[]]->> [42 since it always holds that (0()) > xV. Our improvement stems from novel variance-awane analysis combined with careful exploration of the eelf-concordant-like properties of the MNI. likelihood function, which is inspired by recent developments for MNL likelihood with adaptively collected data 44 3 35).
that with high probability, |a: (Ø- 0*)l 0(1

---

Offline Assortment Optimization with Item-wise Coverage. Based on the sharp confidence region result, we then consider the offline assortment optimization problem, where the seller can access to a dataset D> = { St. = and aim to find the assortment that maximize the revenue. In this setting, we provide an pessimistic-basee
algorithm and show that under a basic coverage number of each items, it can achieve the sub-optimality gap that scales with O(Eies P:(S") (po(s))
in the leading-order term. Notably, we show that (. (P (1 2 n, 11/2 for Wi := E
1 1 E Sx), thus it suffices for each E S* to be covered by S₁ sufficiently many times
in order ensure that ||=:|]| (()))) becomes small. In contrast, the best-known result for linear MNL
model prior to ours, presented in 26),. scales as Ô (V
d where nig- == Ex=
Ss).
Kngg This result has additional d-dependency and a multiplicative -e-eddeennynny compared to ours. More importantly, their approach requires the optimal assortment S* to be exactly observed sufficiently many times, which imposes restrictive coverage requirement on D. Finally, we show that, when reduced to the canonical N-item setting with uniform item-wise rewards, our result matches the (max; / /K/n:) lower bound recently developed in [29]. This demonstrates that the proposed item-wise coverage measure, (Po))))( (0-)) is an appropriate metric for sample complexity in the offline setting.
Improved Regret for Online Assortment Optimization. In the online assortment optimization setting, where the seller starts without prior knowledge but can interact with arriving customers over 7 rounds, we design an algorithm based on the SupCB framework [8] that achieves a regret of Ö(vaT log N + 1d) This result improves upon the previous regret bound of Ö(K VdT'log N) in by reducing the dependency on k x- Our result also improves the Ö(dvT + ==dd) result in
35 on the dependency of when N = o(24). Especially, our result nearly optimal in the sense that nearly matches the 12( ((VdT) lower bound in [1 when reduced to the canonical N-item setting.
1.2 Related Works
Data-Driven Assortment Optimization. The online assortment optimization problem under the MNL choice model has been extensively studied in the literature [14
Among these works, 5 and 17 were the first to close the θ ( /NT) minimax optimal regret for the canon- ical -iteem setting. In the lincar MNL setting, 18 44 proposed algorithms achieving regret of d d d). but these algorithms are computationally intractable. While 44] proposed com- putationally tractable algorithms for the same setting with a regret of Ö(k dV A VVT NV. their results depend on x in a multiplicative manner. The only known computationally tractable algorithm achieving ((v/T) regret with additive dependency on - is that of [35] Our result contributes to this direction by improving the best-known regret bound with additive x dependency
from (dv/T) to (dd T A VaT'log log N). ). For the offline assortment optimization problem, the only known works are [26] and 29 266 were the first design sessimiistic-baseee algorithm for the linear MNL setting. Their algorithm is based on the assortment-wis. pessimistic principle, and its performance bound scales to n5. 1/2 with ng- the number of times the optimal assortment S* is exactly observed in the dataset. On the other hand, [29] studied the canonical N-item setting using R an ttse pessimistic principle. They showed that the minimax rate in this setting is /minces* n.
where n; is the covering time of item i by the observed assortments, thus relaxing the requirement in 26 The algorithm design in our work can be seen as generalization of the item-wise pessimistic principle in (29) to the linear setting, with a new concept of item-wise covering introduced. Finally, beyond the MNL setting, learning problems involving additional constraints (20 10 15 or other
choice models AK 39 56 55
have also been explored.
Offline Learning via Pessimistic Principle. Our design of offline algorithms follows the same
spirit as the pessimistic (conservative) methods [34] in offline bandit and reinforcement learning. The sample efficiency of pessimistic algorithms under partial coverage in the offline setting has been
3 also proposed a computationally tractable algorithm with similar regret; but their proof contains a technical error, as discussed in Appendix L of (35).
3

---

demonstrated in series of studies [3 45 57
Unfortunately, the setting considered in these works directly applicable the assortment problem, due to differences in the feedback structure.
Online Learning with Bandit Feedback. The algorithm design in most online MNI. works draws from the optimistic principle, concept extensively explored in online bandit learning g 23 [1 34]
In particular, the logistic bandit problem can be viewed as special case of the online assortment problem with K I, which faces a similar challenge of eliminating the multiplicative dependency on a problem dependent parameter similar to x motivating number of studies 12 27 28 31 In
particular, the confidence region result our work can be regarded as a generalization of the MNL setting and our improvement over 42 parallels that of 31 for 38
2 Preliminary
Revenue Maximization under the Linear MNL Model. We study the assortment optimization problem, which models the interaction between seller and customer. Let {l..... N denote the set of N available products/items. An assortment
{i..... NN represents the subset of products that the seller offers the customer. When presented with assortment S, the customer chooses a product from the choice set S+ {0) S. where {0) represents the no-purchase option. In the N-item MNL model, each item has attraction value v, 2 0. When customer encounters assortment S, the probability that he/she will choose product i E S given by
U/
Pr(Slo) 1+ ExE
1
Each item generates revenue when purchased, while the no-purchase option generates no revenue: To = The seller's goal is to maximize the expected revenue from the selected assortment, defined as
Eies T:Us 1+ Ejes
R(Slv)= = Σ Cnpi(S|o)=
In the d-dimensional linear MNI. model with fixed design, each item i [N] is further associated with a vector 2; E IRd and there exists underlying parameter 0* E Rd so that 0s exp(x: (n: 0*). With X (Ii,...,, R(S(0*) = R(S|exp(X (*)) to denote their dependence 8" when there is ambiguity.
RNxd we also abuse the notation (S((0)) =- (S)eexx((X x and
Following standard research conventions, we consider the assortments S where |S| s K. In the following context, we denote Sς the set consist of all K K-sized assortments and S* argmax R(S))) the optimal assortment.
Throughout the paper, we assume that the attraction values u, and the underlying parameter norm ||0*| bounded by constants V and W, respectively. We also introduce the problem parameter
min min P. pp((p'))))))))
SE5x
it can be seen that x- scale with exp W') even when V is small. It is worth noting that series of previous works on MNL bandits [18 44 35) focus on improving the dependency on x -1 the sample complexity.
Offline Assortment Optimization. In the offline assortment optimization setting, the seller does not know the underlying parameter 0* but can access to a pre-collected dataset {ir. St)n consisting of the choice-assortment pairs, where for each given S,, the corresponding i is sampled independently from the linear MNL choice model with parameter (**, The seller's goal is to approximate the optimal assortment based on those observed data, the learning objective the sub-optimality gap, defined as
SubOpt(S) = (0*) R(S(0*),
which measures the gap between the revenue of assortment S and the best-possible revenue.
Online Assortment Optimization. In online learning setting, the seller can interact with the coming customers for 7' rounds. At each time step I, the seller provides an assortment S, E Sx to the customer and then receives a feedback i, drawn according to the distribution specified in (T). The goal of the seller is to design policy π (Ti...., TT), where each n, adaptively selects the

---

assortment St based on the historical observations, to minimize the cumulative regret over T, defined as
Reg (T) = Su))pt(S:)I.
which measures the total sub-optimality of the policy и over T rounds.
Notations Through out the paper, for any real numbers b we use the notion V b to denote max(a, (a, 6), and we use the notation a S b if there exists some absolute constant c that cb. For matrices and vectors, given any vector
R' and A Rdxd we denote ||-|| the E--norm, and | = VxT Ax, we also denote AT the pseudo inverse of A.
3 Improved Confidence Region for the Linear MNL MIE
In this section, we present our main result on the improved confidence region for the linear MNL MLE. While we focus on the fixed design setting in the main text, where each item's feature x; remains unchanged throughout
allow the observed feature Tıi to vary across rounds in the dataset to ensure generality this section's result, and we denote X; := ( throughout this the linear MNL log-likelihood function is defined
section. Given any dataset = {it, Xt, S. as
(D( = Σ
Σ
Ytj ( 0)),
t=1 JE(S))
lif = j}. In the following context, for any À 0 denote O3 the X-regularized where yt MLE, i.e.,
argmax 1101
Our first result establishes confidence interval for x T with any |>||| < 1 given the following conditional independence assumption:
Assumption 1. Condition on {(X,, S:)) the observed choices (fe) are mutually independent.
Theorem 1. Given D == {4,, X,, St and 0 the X-regularized MLE under D. Suppose Assumption 7 then for any x E R with | S 1, if we denote H the Hessian matrix of &p at O HB == (0) + XI, and Neg as the total number of distinct vectors appeared (ski)jEss,Ks we have condition on
max | (1R))BBA000 64
kSLJESk
/dlog(Ner/ VAW'
it holds that with probability at least 1 8 i)
HH) 3 (0
2
ti)
Nej + 64VAW).
x (0) 8*) |1 (36)/ log(
8
Technically, our proof of Theorem]] I detailed in Appendix B, builds on extended framework for proving Theorem of (3T]. But several new ideas that rely on the geometry and self-concordant structure of the K-MNL loss are introduced. These structural properties have recently attracted much attention in the theoretical study of MNL bandits and are essential to our argument. The main technical contribution appears in 66 where we use the curvature of the MNL loss to design confidence region that does not depend explicitly on K or K. This result improves upon [42, which is the only previous work giving d-free confidence bounds under the independence condition, and parallels the refinement technique in [36]. which developed for obtaining sharp variance-dependent bounds.
5

---

Comparison to Previous Dimension-Free Result. Prior to our result, the only confidence interval for the linear MNL MLE achieving vd-free rate is stated in 42 Their confidence region result scales as Oxx +xlly,)))) under the burn-in condition
Amin (Vi) 2 K dd
= Σ Σ
Tk.
KEL
By the relation H²(0") = KV; and
|| 1| (0-) I (NiAmin (Vi))
max kSt.ES
our result provides an improvement over in both the confidence interval and the burn-in condition.
Comparison to other Confidence Bound Results. Besides [42]. a line recent works have focused on It is worth mentioning that results in 44 3 35 no longer require the burn-in condition or the conditional independence
deriving confidence regions for the MLE that are independent of 44 3 35
assumption, with price of introducing an additional factor of v in the resulting confidence interval. The requirement of burn-in condition achieve sharp dependency on d first appears in the logistic linear bandit literature, where such condition arises as [31 38) refine the results of [27] 28 by
improving the dependeney on vd factor. This corresponds to special case of our setting with K Appendix F.I we present several comparison experiments those burn-in time free bounds to discuss the sensitivity to burn-in condition of Theorem 1
Offline Assortment Optimization with Linear MNL Choices
In this section, based the confidence interval result in Theorem 1 we present the algorithm for offline assortment optimization problem and the corresponding theoretical guarantee.
Throughout this section, assume W.L.O.G. that Hp (O*) is invertible to maintain notational clarity; otherwise, we consider the X-regularized MLE and its corresponding confidence region for À very close to 0, which does not affect the theoretical results.
4.1 The LCB-LinearMMNA Algorithm
For the offline assortment optimization problem. we propose the LCB-LinearMNL algorithm, as detailed in Algorithm [
The design of Algorithm i is inspired by the lower-confidencc-bburg technique, also known the pessimistic principle, which has been shown be theoretically effective in the offline policy learning literature [30 45 57 The LCB-LinearMi algorithm consists of two steps, the pessimistic estimation step and the revenue maximization step.
Algorithm L.CB-LinearMNNI
1: Input: Dataset D = ((i,,S))} feature set X'
2: Compute the MLE 0 = argmax,6,,0 (0)
3: Compute the pessimistic value L.CBB as in for each i [N].
4: Select the pessimistic assortment: gLCB argmax LCB)
5: Return: SLCB
Pessimistic Estimation In the pessimistic estimation step, with the MLE θp. the algorithm first compute
LCB = x x,TOp 72 (0) Vloe (log(Nen/))
then takes the pessimistic value estimation for each item E [N] via
if i UJ otherwise
LCB
(3)
The confidence region result provided in Theorem ensures the pessimistic property holds for LCC i.c. J.C 2 = c² for all i [N] with high probability.

---

Revenue Maximization After computing the pessimistic values for each item, the algorithm proceeds the revenue maximization step. where it selects the assortment that maximizes revenue under c..CB This step can be efficiently solved using several well-studied polynomial-time algorithms 46 24
4.2 Sub-optimality Gap Guarantee
Now present the sub-optimality gap guarantee of Algorithm
Theorem 2. Suppose the burn-in condition 64 mnal/es..ttwlllellrrstoo $ (ddlog(Not/))) 1/2 holds, then with probability at least we have
SubOpt(SLOB) 36
Σ JES
36 max H5'(00)
(0-)"
JES
up logarithmic factors.
Theorem 2 shows that the leading-order complexity of the sub-optimality gap depends on the summation of py(5* (S)0))))p(S""" [[=]||= over j S*, which measures how well the items the optimal assortment are covered by the observed assortment data. Here we provide upper bound of the this quantity with respect to item-wise coverage numbers to make the Theorem 2 more transparent:
Proposition 1. Denote n, == EkE(M) 1(ie Sk} and n* == minges n4y then it holds that
1 EkES,, Uk
Σ
max v V(I +1+ Uk)m
jES
Based on Proposition we can further obtain the following sub-optimality guarantee of Algorithm)
Corollary 1. Denote n, == Ekejal i E S&} and n* == minjes n4, then holds that under the same condition on Theorem we have with probability at least 1 5,
1+ EkES.. Uk [1++Ees- Uz)
K
SubOpt(sLLBB S max
+
kn*
up logarithmic factors
Results under Fixed Data Collecting Policy. In the setting that (5.) is sampled i.i.d. from some fixed exploration policy - the burn-in condition Theorem 2 always holds as n +oo. Then Theorem implies the following large-sample asymptotic
SB =Ō Ejes- P, (oo 11
Had
with Hof : Essror [Eies po (o((5)))) (SS)) )x,,.] as +oc.
Comparison to Previous Results. Prior to our work, the sample complexity of offline assortment optimization under the linear MNL model was largely unexplored. The only known result, from
which depends on how often the optimal assortment S* is sampled. In contrast, our result avoids multiplicative dependence on d and -1 in the leading term and does not require full coverage of S*. Instead, suffices for S* to be explored through assortments with non-orthogonal feature overlap.
26 considers fixed policy S, Toff and yields complexity of Ō (V [=))
4/K
Result in the Canonical N-item setting and the Optimality. In the canonical N-item MNL setting, a special case of the linear MNL setting with d = N and z; ej. very recent work [29] shows similar result Corollary where the coverage condition for each item is sufficient for learning of the optimal assortment. Their algorithm design shares the same spirit as ours in employing an item- wise pessimistic principle. However, their algorithm and analysis rely heavily on the rank-breaking technique [48] 49 32] which is challenging to extend to the general linear MNL setting. More
specifically, they propose (K// V/n) complexity result and O K K/n*) complexity result in the
7

---

uniform reward setting (r; = 1). In particular, Proposition implies the a Ō /v2////nn upper bound in general setting and an improved O O(VK/n' K/n*) bound in the uniform reward setting, since S consists of the top-K K items by value. The uniform reward setting result, together with lower bound established
in 12 suggests corresponding lower bound of S
V /Ejes P5 (S+ 10~ (5= 1 (0t)
for the offline linear MNL bandits for uniform reward setting.
Eliminating the Burn-in Condition. The burn-in condition in Theorem stems from the confidence region requirement in Theorem] [ The item-wise pessimistic estimation in Algorithm is flexible and can incorporate alternative confidence bounds by replacing (3). In particular, using confidence regions for adaptively collected data (e.g.. [2 yields a burn-in- free guarantee at the cost of an additional V factor. We state the main result below and defer the proof to Appendix D.2
Proposition 2. There exists plug-in confidence region result that when replacing the pessimistic estimation step in (3) by this result, the output Algorithm 7 satisfies
SubOpt(sLCB)
Vd. (p)((S)))) 0+) 1| 1| (0"
d max
[emax|12g11 [=y1 (07)
SES
JES
with probability at least up to logarithmic
5
Online Linear MNL Bandits
5.1
The SupLimearMNL algorithm
In this section, we propose linear MNL bandit algorithms by leveraging the confidence region result established in Theorem [ A detailed description of our algorithm is provided in Algorithm 2 To effectively balance the exploration-exploitatii
trade-off while keeping the independence of collected samples, we apply the SupCB framework of [8), incorporating a sophisticated action set elimination procedure and sample splitting procedure, as in [21 38 31 42]. However, several modifications have been made to our algorithm to ensure the burn-in condition of Theorem [ and to utilize the first-order geometry of the revenue functions, as described below.
The SupCB Framework. Similar to the standard framework in [8), Algorithm 2 divides the collected samples into S bins, denoted V v...... aas+1 To maintain independence while accounting for the first-order geometry, we add an additional bin, V 5+ as in [31], which contains a rough estimator for approximating the first-order coefficients of R. After an initial pure-exploration period of length T-ensuring that each bin collects sufficient samples, as explained in the next paragraph-the algorithm enters adaptive elimination phase conducted through a multi-layer procedure that loops over the first S bins.
Initial Exploration Phase. The initial exploration phase is designed to ensure the burn-in condition in Theorem More precisely, the initial exploration phase ensures that max]e[N]]l=z (o.) is well controlled for every E [S+1] 1] with high probability. Note that since (0*)(00) m K KVr.e, with Vr, == EeSroew, ExEs, T. it suffices to ensure that maXje[N] k x///3||=,]llv is well bounded for every f. To achieve this goal with finite sample complexity, the algorithm repeatedly taking the exploration assortments containing uncertain items until
512x 1/2 maxx|=yllv..
Vilog(NT)
W
holds for all l. Careful readers may notice that to compute 4 we need prior knowledge of x as an input to Algorithm 2 which is problem-dependee we can instead use the parameter radius W (or its upper bound) to provide a conservative estimate. In particular, exp(- KW) can be used worst-case bound for It should be noted that there may exist problem instances where k is strictly smaller than its worst-case bound. Designing algorithms that achieve the same regret guarantee while fully adapting to an unknown K, as in [44 35), is left for future work.
quantity. When the exact value of unknown,
Adaptive Elimination Phase. After entering the adaptive elimination phase, the algorithm stops allocating samples to L 1441. The MLE
0o argmax.e D...t,
(5)
8

---

Algorithm 2 SupLinearMNL
1: Input: Time horizon T. problem-dependent factor k.
2: initialize M log2 T, T I, 1,
V M-+1 0. 3: while 4 is not satisfied for some & E [M] and j E [N] do
4: Select arbitrary assortment that contains item j. add into L
5: T ++++1
6: end while
7: Vo + 0, compute 8g as in (5)
8: for t = 1..... do
9: set A, Sk, St 0, 0
10: while S. do
11:
Compute W f.s. 1 VS E Ar as in 7
if W. > 2-d for some S E A then
13:
select such S E Ar. V 4 V, [t} else if W I 1/T for all S E Ar then take the action S. = argmax RUCB (S)
14:
16:
17:
Lo t L
else
19:
R + maxsEA: Ri, (S)
Ae+1 + { SE Ar, RUCB (S) 2 R 2-2+7
20:
21:
(+
end if
23:
end while
end for
computed based the data in Vs41 collected during the first rounds and is fixed in all subsequent
time steps.
At each during the f-th loop, the algorithm calculates the confidence level term
wf,= 72| (1))))) (log(NT))
(6)
for E USEALS, with Dr,e the data collected the é-th bin up to time t and we simply denote A by HAA-- Then, based the value of W4,; for each i, the assortment-we wise confidence level for S, written
Wh.s =
16p (s)
+ max (
#ES
VES
is calculated for each S E As. Then the algorithm takes one of the following steps based on (W( (Wts)
Step (a). Exploration of Uncertain Items: If there exists some uncertain assortment (i.e., W7.
2 2-)), the algorithm selects this assortment to explore it further.
Step (b). Output UCB Assortment: If all assortments are sufficiently certain (i.e., W t,s < L/T for
all Ae). the algorithm outputs the assortment with highest UCB value, computed as
RUCB RUCB((S) P
with UUCB = exp (a. DD.e + wf,)).
Vi E [N].
Step (c). Assortment Elimination: Otherwise, the algorithm performs assortment elimination over Ae- Specifically, it first computes the maximum UCB value R. Next, it eliminates all assortments S such that the UCB value gap, R
exceeds 2- Finally, the algorithm loops to the (E 1) bin with the eliminated item set Ae+1-

---

5.2 Regret Guarantee of Algorithm 2
Now we show the regret guarantee of Algorithm 2
Theorem 3. With probability least - 1/T, we have Algorithm satisfies
Reg(T) E v dT (NT) + n td - + dW) log(dNTW))
Theorem establishes a Ō D(VdT + +x regret bound. Compared to the Ö( Vdd) in
and + in 35 our result is the first to achieve Õ(v log N) regret in the linear MNL setting with a second-order dependence on x-1, However, due the need enumerate over A in the elimination (Line 20) and confidence computation (Line 11) steps- each takes ((N times computation in worst-case, similar to [18 42 the
the algorithm is computationally inefficient theoretical benchmark, and we leave designing efficient algorithms with similar guarantees as a future direction.
Thus, Theorem 3 serves primarily
Problem-Dependerd Regret with Uniform Revenue. While above results consider the non-uniform revenue setting for general [0, 1] We can show that in the uniform revenue setting where r; 1 as in 44 35
an improved problem-dependen rate is possible: Denote
Ejes (1+ Ejes U2)
E,,(5 (1)) JES
we have the following guarantee of Algorithm 2
Theorem 4. In the uniform revenue selling Ta = 1, Vi E [N], Algorithm satisfies
Reg(T) S log log(T) x (d + dW) log(dW
Noticing that in the good scenario where all (1) in 35 we have the above bound simply
turns Õ /dT/K) result, improving / K factor than previous best known results. Appendix, we further show 11x***** / /T) problem-dependen lower bound for a large range of kt, implying the optimality of Theorem
Acknowledgments. This work is generously supported by NSF CCF-2419564, NSF CCF-23122044 NSF CCF-23 12205, ONR-13983263, ONR-13983111, and 2026 New York University Center for Global Economy and Business grant.
References
[1] Yasin Abbasi- Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24, 2011.
[2] Marc Abeille, Louis Faury, and Clément Calauzènes. Instance-wise mniimmax-optimg algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 3691-3699, PMLR, 2021.
[3] Priyank Agrawal, Theja Tulabandhula, and Vashist Avadhanula. A tractable online learning algorithm for the multinomial logit contextual bandit. European Journal of Operational Research, 310(2):737-750, 2023.
[4] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the ban-ba In Conference learning theory, pages 76-78. PMLR, 2017.
[5] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Mnl-bandit: dynamic learning approach to assortment selection. Operations Research, 6755):1453-1485, 2019.
AA natural question whether heuristic algorithms as main challenge lies in the assortment space Ar. which is exponentially large and unstructured. Unlike (88. where feasibility can be verified simply by checking the size of S, determining whether S E As may require enumerating storing all [Ae]] elements, making heuristic design particularly difficult.
can developed for our setting. The
10

---

[6] Aydın Alpiekinoglu and John H Semple. The exponomial choice model: A new alternative for assortment and price optimization. Operations Research, 64(1):79-99 2016.
[7] Arthur Asuncion, David Newman, et al. Uci machine learning repository, 2007.
[8] Peter Auer. Using confidence bounds for exploitation-exxloraiion trade-offs. Journal of Machine Learning Research, 3(Nov):397 422, 2002.
[9] 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, 44(5):612-617, 2016.
[10] Abdellah Aznag, Vineet Goyal, and Noemie Perivier. Mnl-bandit with knapsacks. arXiv preprint arXiv:2106.01135, 2021.
[11] Gerardo Berbeglia, Agustín Garassino, and Gustavo Vulcano, A comparative empirical study of discrete choice models in retail operations. Management Science, 68(6):4005-4025 2022.
[12] Jose Blanchet, Guillermo Gallego, and Vineet Goyal. A markov chain approximation to choice modeling. Operations Research, 64(4):886-90) 2016.
[13] Jose Blanchet, Renyuan Xu, and Zhengyuan Zhou. Delay-adapticn learning in generalized linear contextual bandits. Mathematics of Operations Research, 49(1):326-345, 2024.
[14] Felipe Caro and Jérémie Gallien. Dynamic assortment with demand learning for seasonal consumer goods. Management science, 53(2):276-22) 292, 2007.
[15] Xi Chen, Mo Liu, Yining Wang, and Yuan Zhou. A re-solving heuristic for dynamic assortment optimization with knapsack constraints. arXiv preprint arXiv:2407.05564, 2024.
[16] 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.
[17] Xi Chen and Yining Wang. note on a tight lower bound for capacitated mnl-bandit assortment selection models. Operations Research Letters, 46(5):534 537,, 2018.
[18] Xi Chen, Yining Wang, and Yuan Zhou. Dynamic assortment optimization with changing contextual information. Journal of machine learning research, 21(216): 2020.
[19] Xi Chen, Yining Wang, and Yuan Zhou. Optimal policy for dynamic assortment planning under multinomial logit models. Muthematics of Operations Research, 46(4):163-116657, 2021.
[20] Wang Chi Cheung and David Simchi-Levi. Assortment optimization under unknown multino- mial logit choice models. arXiv preprint arXiv: 1eo.ii:::0040000 1704.00108 2017.
[21] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 208-214. JMLR Workshop and Conference Proceedings, 2011.
[22] Carlos Daganzo. Multinomial probit: the theory and its application to demand forecasting. Elsevier, 2014.
[23] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In COLT, volume page 3, 2008.
[24] James Davis, Guillermo Gallego, and Huseyin Topaloglu. Assortment planning under the multinomial logit model with totally unimodular constraint structures. Work in Progress, 2013.
[25] James M Davis, Guillermo Gallego, and Huseyin Topaloglu. Assortment optimization under variants of the nested logit model. Operations Research, 62(2):250 2014.
[26] Juncheng Dong, Weibin Mo, Zhengling Qi, Cong Shi, Ethan X Fang, and Vahid Tarokh. Pasta: pessimistic assortment optimization. International Conference on Machine Learning, pages 2295. PMLR, 2023.

---

[27] Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. International Conference on Machine Learning, pages 3052-3060. PMLR, 2020.
[28] Louis Faury, Marc Abeille, Awang-Sung Jun, and Clément Calauzènes, Jointly efficient and optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 546-580. PMLR, 2022.
[29] Yuxuan Han, Han Zhong, Miao Lu, Jose Blanchet, and Zhengyuan Zhou. Learning optimal assortment policy under observational data, arXiv preprint arXiv:2502.06777, 2025.
[30] Ying Jin, Zhuoran Yang. and Zhaoran Wang. Is pessimism provably efficient for offline rI? In International Conference Machine Learning, pages 5084-5096. PMLR, 2021.
[31] Kwang-Sune Jun, Lalit Jain, Blake Mason, and Houssam Nassif. Improved confidence bounds for the linear logistic model and applications to bandits. In International Conference on Machine Learning, pages 5148-5157 PMLR, 2021.
[32] Ashish Khetan and Sewoong Oh. Data-driven rank breaking for efficient rank aggregation. Journal of Machine Learning Research, 17(193):1-54, 2016.
[33] Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems, 33:1 33:1179- 1191, 2020.
[34] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[35] Joongkyu Lee and Min-hwan Oh. Nearly minimax optimal regret for multinomial logistic bandit. arXiv preprint (ttt::2405008831,, 2024.
[36] Joongkyu Lee and Min-hwan Oh. Improved online confidence bounds for multinomial logistic bandits. arXiv preprint arXiv:2502.10022 2025.
[37] Erich I. Lehmann and George Casella. Theory of point estimation. Springer Science & Business Media, 2006.
[38] Lihong Li, Yu Lu, and Dengyong Zhou, Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-2080. PMLR, 2017.
[39] Shukai Li, Qi Luo, Zhiyuan Huang, and Cong Shi. Online learning for constrained assortment optimization under markov chain choice model. Available SSRN 4079753, 2022.
[40] R Duncan Luce. Individual choice behavior, volume 4. Wiley New York, 1959.
[41] Daniel McFadden and Kenneth Train. Mixed mnl models for discrete response. Journal of applied Econometrics, 15(5):447-470, 2000.
[42] Min-hwan Oh and Garud Iyengar. Multinomial logit contextual bandits: Provable optimality and practicality. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 9205-9213, 2021.
[43] Mingdong Ou, Nan Li, Shenghuo Zhu, and Rong Jin. Multinomial logit bandit with linear utility functions. arXiv preprint arXiv:1805.0299 2018.
[44] Noemie Perivier and Vineet Goyal. Dynamic pricing and assortment under contextual mnl demand. Advances in Neural Information Processing Systems, 35:3461-3474, 2022.
[45] Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: tale of pessimism. Advances in Neural Information Processing Systems, 34:1 1702-11716, 2021.
[46] Paat Rusmevichientong. Zuo-Jun Max Shen, and David B Shmoys. Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Operations research, 586)) 2010.
12

---

[47] Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
[48] Aadirupa Saha and Pierre Gaillard. Stop relying on no-choice and do not repeat the moves: Optimal, efficient and practical algorithms for assortment optimization. arXiv preprint 18811 2024.
[49] Aadirupa Saha and Aditya Gopalan. Active ranking with subset-wise preferences. In The 22nd International Conference Artificial Intelligence and Statistics, pages 3312-3321, PMLR, 2019.
[50] Denis Sauré and Assaf Zeevi. Optimal dynamic assortment planning with demand learning. Manufacturing & Service Operations Management, 15(3):387-404, 2013.
[51] Aleksandrs Slivkins al. Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1-2):1-286 2019.
[52]
Kenneth E Train. Discrete choice methods with simulation. Cambridge university press, 2009.
[53] Dong Yin, Botao Hao, Yasin Abbasi Yadkor,, Nevena Lazié, and Csaba Szepesvári. Efficient local planning with linear function approximation. In International Conference on Algorithmic Learning Theory, pages 1165-1122 PMLR, 2022.
[54] Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. Advances in Neural Information Processing Systems, 13:14129-144 14142, 2020.
[55] Mengxiao Zhang and Haipeng Luo. Contextual multinomial logit bandits with general value functions. arXiv preprint arXiv:2402.08/26, 2024.
[56] Yu-Jie Zhang and Masashi Sugiyama. Online (multinomial) logistic bandit: Improved regret and constant computation cost. Advances in Neural Information Processing Systems, 36, 2024.
[57] Han Zhong, Wei Xiong, Jiyuan Tan, Liwei Wang, Tong Zhang, Zhaoran Wang, and Zhuoran Yang. Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets. In International Conference on Machine Learning, pages 27117-27142 PMLR, 2022.
13

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
Contributions of the paper are accurately stated in the abstract and introduction. made in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Potential limitations are discussed below the main theorems.
14

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't ' acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions are claimed in Section
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: No experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
15

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
No experiment.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (nttps://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 /ttppp.cc/pbllc/guudeeee http://odeubibiiiioooooooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
16

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: No experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: No experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: No experiment.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
17

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: htt
Answer: [Yes]
Justification: This theoretical work involves no sensitive data or human subjects and fully complies with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This is pure theoretical paper and there is socictal impact of the work
performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
18

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This work does not use any existing code, data, other external assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperssithcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
19

---

Answer:
[NA]
Justification:
This work does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non stanndaddrrd components.
Please refer to our LLM policy (https://neut) /cC////reeeeccc//222//////////// for what should or should not be described.
20

---

A Technical Overview and Proof of Main Results
A.1 New Perturbation Results of Revenue Functions
As in previous works, to eliminate the multiplicative dependency on H k-1, we follow an improved analysis that uses second-order expansion of the revenue function R(S e*) with respect to := x 0. However, when K 2 2, the presence of multiple items in S introduces significant challenges. To handle this, a careful perturbation analysis is required to bound the resulting error. For example, noted in [351, Equation (16) in [3] incorrectly extends the perturbation result from the logistic bandit( K = 1) setting, causing their analysis to fail. On the other hand, [4 provides a promising direction for handling such perturbations, though their result only applies to the uniform revenue case where r; = 1. The only promised development for non- non-uniform revenue setting is given by the recent work [35). where approach based on centralizing the context features are provided in the proof of their Theorem 4. However, this argument is somewhat complex and requires a careful auxiliary analysis.
In this section, we present several simpler and general perturbation results for revenue functions for the purpose of analyzing Algorithm [ and Algorithm 2 As byproduct, we can show that a straightforward plug-in argument based on our lemma allows us to extend the regret analysis which previously applied only the uniform revenue case to the general non-uniform dd) regret, we leave the detail to Section E.5
in 44
revenue setting, achieving the optimal Ö(dVT ==
Proposition 3. For any fixed revenue vector r and utility vectors u' E RR,, denote u := log(v) and w = u' u, v' :- enL, .then i) it holds for any So E SK that
|R(Sol0)) - R(Solo)]
Σ JESU
oylr - R(Solo)3
Σ
(S(Solu))0(0000000 + max wf. 2 JESo
V
jESa
ti) In addition, So satisfies ry 2 R(Solv) for all j E So, then
|R(Solo0) - [ <
Σ
P3 (000)))))0(666)))) + max w3- JE88
w3.
JESO
Based on Proposition 3. we can further present the following result for the analysis of elimination- based Algorithm 2
Proposition 4. Suppose for some ú 2 v it holds that R(SolT) 2 R()* E, then for w = ū u
we have
(((S)))))())))>2
2
Σ
(1(()
+ 5 max w3 + 28.
SESo
jESO
A.2 Proof of Theorem
Proof. Throughout the proof, we denote & : ::==7//=lll,,,1 (6)) (log(Net/)),, Op by θ for simplicity. With above notation, we have
Eies (x Ex) AS SK-
(B) = R(S))LCR)
1+ Eies exp(x. Ex)
Now we have for exp(X (*), it holds by Theorem that with probability at least 1 - 8 that ,LCB < v. Under such a condition, we have then
R(S*)0*) - R(S(0*)= Sa R(S*(o)- - R(S) u LCB) Sun R(S+(v) - R(S* (..CB)
Σ (S((*10))0(5*11)) + 3 max w/- JES-
San
JES
Where (i) is by the monotone property of a at its the revenue maximizer(see e.g. Lemma A.3 of (ii) is by R(S (CBB S (LB), (iii) is by the statement ii) of Proposition 3 and the fact ry S b), e St. This finishes the proof.
D
21

---

A.3 Proof of Theorem 3
We first show the following exploration length upper bound result:
there exits some absolute constant co so that the exploration phase will stop after at most CrMR d(Vd (No)) V w)² log(dNTW) iterations, and it holds that
Lemma 1. In Algorithm 2
1
1
512 max [ '(0)) S JE(N]
Vdlog(NT) A
W
for every E [M 1].
In particular, Lemma [ verifies the burn-in condition in Theorem | with À 1. Consequently, it can be applied in subsequent time steps long the independence assumption is satisfied, which is guaranteed by the SupCB elimination framework.
Based on our exploration of order -d K2 log() and the burn-in condition in Theorem is satisfied for all bins. So it remains to bound the regret incurred from 7 + to under the event
analysis in Lemma] 1 we have the exploration phase incurs regret
[n3 (0,, 8*)l s (72 (T2//og((TT)
Vt r,j E [N]. [M]
(9)
and
H H1,)(0)) = Hi,e(0o) (H),) AA T [M].
(10)
which holds with probability at least (1/T))
We would also note that
(9) and TT) together with 44) also implies
72 + 128
|r] (00 - 0*)l < (72 log(NT)) + 128W) bry b(00) S
S Vj
512
thus for any S and E S,
ee
pp(()0)))) v
S Sp((S)
S
eカ, S pp
1+ EfEee
1 Σ
with ū. == == As a result,
W Ejes P3 ()(S)))po(Slu)]z
2 2-
S 2
(II)
Hil
for any f, and 2 T.
Lemma 2. For every and S AA holds under 9 and 10 that
|R|C - ((()) - Wi. + + 1+1
Proof of Lemma
We divide the proof into two steps:
Step 1: S* E A for each f. At each t 2 т, we first show that S* E Ag for all The claim holds
for { = 0 since Au Sx. Now suppose 5* A for some & > then suppose the algorithm
enters the step (c) at the ê-th loop, it holds that by vi. 2 exp( X 0*) under ( and (1)).
UCB
RUCB RUCB((*) 2 R(S > R())
for S. = argmax SEA, RiyC (S). On the other hand, we cannot directly apply Proposition to obtain perturbation bound for Se. since it maximizes the optimistic revenue over an unstructured ser Ae rather than the structured set Sx-
For Se, holds that by statement i) of Proposition 3
RUCH R(3,00*) S
vylr, - R(Sclo)2. Σ
Σ p, (3(()l)) + max w JeS.
3
EE
JES.
22

---

Now if we denote
= Ui E B,, 2 ((Su 3= \
then it holds that
Σ oglr, - R(Sc 2
Σ
Uslry R(Srlu)]= Σ
1y(r, R(Selo)) Σ
vz(r, R((
JES.
JESc
EEŠ7
JES,
=2
Σ
,y(r, - R(S,lu)) - R(Splv)= 2
Σ
ny(r, Ri, (St) + Σ
by ( (5x) - R(Splo))
jESt
jEST
jESt
s 2
Σ 0y(ry RUB (Be) + 2po (R (St) R(Selv))
jESt
2
Σ 05(r; (o)) 2pp (Se ( (St) ((Sa((()))
JES
s 28( 2p 2p (Sc (S:) R(Sr(v)) u)).
where in the last second incquality we have used
RUCB 1 (Se) 2 R (S*) 2 R(S*10*) 2 R(S.)0))
by S E Ar. As a consequence, for A : R (Si) - R(3a(0)) we get
A (2( + 2pp 2 (Sclo)A
Σ (1(((l)) + max w),
2 JES.
jeS.
Using the elementary inequalities
A +
A + 4B
2² < B -
I A B B = 2A2 +BB
2
for A, B, 2 0, we get then
A < Σ (S() +4
Σ jeB,
Py (Se (Seelu))) + max w/ < 2 t.s, 22-466
jeB.
JE
where the last second inequality is by and the last inequality is by Algorithm 2 does not enter step (a) in f-th loop. Now we get
RUCB (S*) 2 R(Se(0") 2 RLCB (St) 2-46
thus then RUCB((S* Ae, as desired.
Step 2: Bound the regret of assortments in Ae Noticing that by the selection of Ae, we have
SE = R RUCB 2 LCB (Se) 2-777 2 RUCB ((*))((*) - -
R(S|v) 2 R( - -
where in the last line we have used Lemma desired.
Similar to the proofs in 38
we can bound the regret of Algorithm Zi a layer-wise approach: Lemma 3. For each round > let e, denote the value of l when S, is selected. Then, under
and 10 it holds that
(4.2-448
S is selected in step (a), if S is selected in step (b).
R(S*)
14/VT,
23

---

Proof. We have by St E Al..
R(S, 2 R2, -1.4-11551 (S:) W.. 2- 2 R - 2 2-
R - -2 4,, R(5 2 2-4
this shows the first inequality. To show the second inequality, noticing that by Lemma the condition of step (b) implies
[R(S) - RUCB (S) - 8/T, vS E Ar,-
Then by
RUCR R(S.) 2 Ri (S.) 8//T R R (S*) 8/T R(S") - 11= 8/T,,
the desired result holds.
Now with Lemma 3 precisely, we have
we can bounding the regret of Algorithm for each bin V separately, More
Lemma 4, For each E [S], we have condition on E2,
d
R(S") R(()) S v CT log NT) Jog(NT)
(12)
Proof. We divide the time indices in V into
Ta.: (1 E Vr, l T, S, is selected at step (a)),
To. (t E Ve, r, St selected at step (b)).
By Lemma and 2 We f.s. for all j E St and & Ta, have
Σ R(S*) - R(Si) < Σ 4 4-2-
TET,,r
TET..
(13)
<
Σ
(S)S))) B (0-) log NT + (inx(722//0g NT x3 (o))
JES.
AET.,
jES,
To bound the above summation over Ta,t, we apply the following linear MNL version elliptical potential lemma:
Lemma (Lemma E.2 in
351). For À 1, it holds that
ΣxeTa Ejes,
Il S 2d log(1 +
[Ta.e 2dx
| ΣieTa, maxies, | n!! $ 2dx - log(11 + [Ta.ll).
dA
Applying this Lemma and Cauchy-Schward inequality in 13 then leads to
Σ R(S*) R(S)) |oTTa. log(1 T/d)
2d
+ Tdd)
this provides the regret bound for the summation over Ta.t- On the other hand, by Lemma we have taking summation over E To. naturally leads to
Σ R(S*) R(S,) 8log T.
1ET
combining the upper bounds for Ta,e, To. and taking summation over then finishes the proof.

---

B Proof of Theorem I
We begin with the following Lemma:
Lemma 6. Suppose the same independence structure as in Theorem 1 and denote
max | ((() = 65 -1 (05-1 - 1)(1
: 3:3
10 -,"), ::=
max mst.jESm
mst.jeSm
5
we have x (0)
(Vlog(1/0) + (log(1/0) ((() (Vdlog(1/0) + dK log(1/6) + vAW) V
8112|| (12))
Proof of Lemma Since in this formulation the feature vector 2m, may change for each m, we introduce the notation Pm, to represent the probability that item j is chosen given Sm and am. We also denote (07) by H², (0*) by H, for simplicity.
Noticing that by 0 maximizes b we have
Ven (0))
Tmm (pm)(00)) = pmmm((") - yms)) + 10 =
m= JES
Σ
Tm.j (Pm)(03) - Pms((0) 1100 -0)
Σ
Um.j (ymj pmj (0a))
~X0
JESm
jESm
:= :=mmm
Now we denote
Lm =
Σ
Im.Pmil (0),
jESm
then for any it holds that
Σ
Imms (p(j; Sm, 3m, 0) Pmmj (0*))
JESm
= =mm((0) - Tum (0m = S:² Dfm + +000- =000-0)))( - 0*)ds
= =DLm(0")()) - -8") + (1' DLm + s(B 6*)) DL (8" )ds) (0 8*),
with
DLm (0) = Σ
Pinj (0n(())mmaz)))
Pmn (0)
JESm.
IESm.JES..
Now notice that H = Et DLm (0*) + Al and for
/ D0m + s00 0y))
E, = Σ
DLm )ds
m=1
we have
① 0-)
x THH, + E. -
Σ
Σ Im.j.lm.j 20*
m=
JESm
= = - + 1))
Σ Σ
Imsmmm - A0*
m= 1jmm
= x -
+ E.) E.) Σ Σ
Imm - Ax T THA + Ex)-10 11
Zm imm. x
M= JES
m=1 jesm
:=
(14)
25

---

The first term J1
The first term can be bounded by variance-aware concentration results using conditional independence in previous works obtaining sharp bounds for logistic setting [3T] the main difference between the logistic setting is the dependency across Mm. for j E Sm For every we have
Zm
Σ x xT(H.) JESm
Fm.
is centered and bounded as
1mmll I max (H²
2m
Σ
mma S 2maxxx' (H²)) Lmmsl
3
jE8m
With variance
B| E[Z2| = Σ (HT xm (HAA)
( smm,) Ama).
KJES
By
B Blnmmss Pend (0n)) (0*) B(Tm,,
PPmi (0*) P (0*)
we have
B[Z21] = x (1H,)--
mm pmi(0*))) - iEsm
Σ
Σ Im, a I.. (0" (0)) (Hi?) 'z,
==0m
now by Ei Um = H,, we have Σn, E|Z = x T apply the following Bernstein inequality:
x (H²))*a) STHA) now we
Lemma 7 (Bernstein's Inequality). Let XI...., Xn be independent zero-mean random variables. Suppose that Xx|| & M almost surely, for all i. Then, for all positive t,
fu²
Σ
X1 2 u
I Sexp
(-E
" 2im
E
[
Mu
to obtain that
u
IP (PJI u) S exp
2/|x012 (1
max max x (H²-)
xmm 1u
equivalently, with probability at least 1 -5, 5,
J < 2||=!|10/)11 (Vlog(1/0)+ + max [1mmp]lez7)-100((11 log(1/0)) mst.je9..
(15)
The second term J2
For the second term, we have denote
Σ Ejesm. Im.jDmn.jj then
J2l = |z T (HA) E,)
< [1
-E>' 1 11))))))
26

---

Bounding 1 (E((H))'11)
Given any vector w, if we denote
Amj == my w, bmg =
T mmj (0) - Pm) == Pms (0 + +00 0*)),
and
Um) (5) = mng (0* + s00) 0))), Umg (5) = (+)
for j E Sm and set 0m0 = 0m0 um 0, 1mo = 1 for convenience. Then we have as shown in 35
Ejesm Eiesm (Ams - amg) Umel ())mm))mm)))
| DL (0- (0=
(1 Ejes.. Um/ (8))²
It can be verified by calculation that
w ( +.(03 -013) -..93
ds
Ejesm. EsE(Sm) (ami Umz)))n(()))m Σ Eke(sm)) )+ (bms bmj 2bmx )
(1+ ΣjEsm Umn [8))
Ejes.. Eie(Sm)+ (ami amz) )m U (omss(s)ug (s)mms()
3v2 max [mmyl JESm
(1 L1ESs Umm (s))
3 max (myll || DLm (0+ +0(0) -0))) jeSm
As result, (s) = log|| 12 (0m -0.)) satisfies [v)( < 3/2 max lbm which then
leads to
3v2 maxjesm |mmlls w| (r..) (0.) S ||l|| DI.,. DI. (0- 0.1) -0,1 S c 333 Mmu M DI....
(16)
Now have for any w E IRd, by taking summation over m,
T E w / Σ
w
DLm (0 + = -0*) - -DLm((0)) dsw
mse
1 / (ete 1)ds|Iwllis 1 (o5 -11 (6-1-11
this leads
H. -1)
( -1 11111
(6 (
E, 3
- 1) H.a
(17)
C
On the other hand, we have by
H Es
Σ
DI (0" s - 0*))ds
mst
(18)
c ds He 2 1- 1-c c
1
H₂ > 1 H
where the last inequality is by the elementary inequality 1-e 2 + x > O. With 17 and 18 we arrive at
11H2) E, (HH))
1/2
1w.T (H/ -1/2
max ||
c 1
1 -1 -1] S
e5 - $2( =2(05-11 1),
I+
C
and thus
(e- ( ||(1 + -
J/ 22|2||11(
27

---

Bounding [I + E)
zellma? -
By 18 we have
H2 (1 + (H, + Fi)) = (H, + F.t) H (H) + Fit) = (1 + () + B) 3 + H.
thus it holds that
(H + E) 2 li 2.- (H) + E.) H + Ea)
(1 2) c ||
To control [0l|1187)) 1, we have for any unit vector w, it holds that
w (HH)) 1/22,
((H2) (H²))
:=
which has the same form as when we replace by æ, thus by the same argument as in bounding Jr, we have (15) still holds: with probability at least 1 8',
|w T (11)) 1/22// zel S 2 |
(/oo((188)) + max mSAJESm
|| (
=|w]==1
now taking w over the 1/2-net of the unit ball and taking union bound with selecting 8' > 4 leads
to with probability at least 1 6,
|| (132)) s 8 dlog(1/8) (1)))(1/6)
max | mSi.EEs,.
Further introduce the notation
5 = max (( in Lemma we have then
|| | S (1 (logglg Sde log(1/)))
(19)
Now we arrive at
-1 (
6 (
J2 S ||
(1 () (v /log(110)) + (log(
=C(C)
In the above proof of (17 we borrow the calculation in (35), which was used to verify the celc-conncrdantllikc property of the linear MNL-likelihood function. The key distinction in our approach is that we retain the dmg term throughout the calculation, whereas (35) directly apply the bound [bms S 110) 12... This difference allows derive bound Eg that depends only on maxm. (m (ØD 0*},, rather than on 100/ 0-112- worth noting that a very recent work 1361 also uses similar argument to establish refined self-concordunt-lice llkee property for the MNL likelihood function (specifically, the to selffconcordant--ie property their Proposition B.3) obtain sharper confidence bounds, and the bound in 17 can also be derived from their Proposition B.3.
Remark 1.
While the above proof primarily focuses on the relation between HD (0:) and HD()"), the inequality in [6) can also imply a dominance relation between (D) and HD for general f. We summarize this general result in the following proposition for future applications.
Proposition S. Given any 0 E Rd, > 2 0, denoting Co = 3v max le TT (0 - 0-) )1 then it holds that
1 + (G)(Co)
HD( - (0) = (1 (4((
Proof of Proposition
By taking in [6
get
| (0)) < | ||| - e (ewlllo
for any unit vector w, thus it holds that
6o HD((*) = HD( = 50 HD())).
Now by
1 + 24((G) 1 2(1 + Go) 5o -
S0
- 1) = Φou + (c5o - (e) + 2
2
50
So
So
2
the claim holds.
28

---

The last ferm J3
For the last term in
we have by
1
He E + 1+(
He + AI =
H
1 1+
J3 S |Ax (A + =,) (A & v () (1)))
Combining all bounds
Now combining all above bounds, get
| (0) -00-
(Vlog(1/0) + (log(1/6)) p(() (Vdlog(1/0) + dlog(1/8) g+ - v
8| (1)))-
as desired.
Lemma 6 provides an upper bound on the ratio between T (0) (r) and | However, the upper bound involves both & and Ç simultancously. Our next lemma shows that when & is well-controlled. the Ç factor can be bounded by E.
Lemma 8. Under the condition
{ S min
64 (olologNNa/ 64VAW
we have
(p() SC S 16( 1 log((No/))) 22WW)& + 165 Nog(NNg// Nog/6).
(20)
Proof. Applying Lemma 6 to each Tm.j. we have then with probability at least - 6,
(Vlog(Nan/o) + &
+ (()) (Vdlog(Nan/d)) + d dooo(( Net/o) . + vAW) + VA(++
86
Now by the elementary inequality
3 g)
c" s1+ r Vr E (0,
holds that
S = (1 0) 1 -
8 50 5
1) S
S
we get when Ç S 3 3. the above inequality can be reduced to
(1-
+ de (on()Nn)))) + vAW)) & 8( (ol//oooo//e//// + /2AW) + 88² log(NNn
As result, it holds simultancously that
Ç S 5.
< & min
32 log( 32v AW
then
< S 16( Vlo((Nar/0) + 22WW) + 16g² log(Non/0))
On the other hand, by 19 it always holds that with probability at least 1 - 5,
Ç S
E O
0" 1, EH E 10
< + (H,) - 20 (1/
{(1 (((1+)] / 8d (1/0) + vXW)
29

---

As consequence,
}
$ min
< S 165( ( + vAW/16)
lolog(100)
64 64/dlog(1/0) 64VAW
64 +
1 3/5.
4
4
That verifies 5 S min
sufficient for
20 holds, as desired.
(4//dlo((Na/)) 64vAW
Now combining the results in Lemma and Lemma we have & ES min 64 /dl/ Naa
64VAW
implies that
x ( 0-)1
8||0|| (H+2) (1))))
p(() (Vdlog(1/0) dlog(1/6) + VĀW) VA(1+ + Vlo((1/8) {log(1/8)
s 165((1+ + 6AVd Vlog(Non// (0) V2AW) - (Vdlog(1/0) + dlog(1/8) E+ vAW)
/2XW + Vlog(1 (1/0(1/))++ + (og((10)
1) + VA( + C + 2lglo1(1/8) 1 log( (Nen/)) V2AW). (16 256
((1 64vd
< 2 lolgoo(NNaa (Nett)) 0)) + 32v 2XW.
This finishes the proof of the confidence bound result under the burn-in condition.
Moreover have by (() S 3/5, Proposition 5erpposiiionniimpaa implies
H 1+ 2 H H E, 22(+))(()H+ 3HH
This finishes the proof of Theorem
T
C Perturbation Results for Revenue Functions
Before proving results in Section 4 and Section we first introduce several perturbation results on the revenue function R with respect to the utility function u.
To emphasis its dependency the utility variable u, the following notation throughout this section for given S and r: S) : Q) R(S)ey) I+ Ejese" en
Ejestje
(21)
Since is fixed throughout the whole paper, denote Q(u; S) by Q(u; S) for simplicity. We first recall the following first-order and second-order derivative results, originally proved in 44 and refined in 35), we provide the detailed proof only for completeness.
Proposition 6 (Lemma E.3 of (5)). Given r E [0, 1 and S c fixe, if we denote
Wij jES
WS =
(22)
10, j S
for w E N. Then any u RN we have
(VQ S), w) = Σ (:(eee - Quu; S))w,
(23)
iES
w
V2Q(u; Slwl < 3 max w
(24)
iES
30

---

Proof of Proposition 6 During the proof S is fixed, thus we simply omit the notation and simply denote Q u; S) as (u)
To prove
23 noticing that for every $ S, Q(u)
= 0 and for every i E S, we have
rzen:
e" EEEs Tye"s
0u.Q(u)
1+ Ejes en (1+ Ljes t.t
=p:(S}c") -Q(u))
Thus
(VQ(u), = Σ Qu,u(, (r( -Q(u))
EE
EES
as desired.
To prove (24.. noticing that 02, au Q(u) = 0f
& S. When i, S, we have on, a., Quu) = 0n, (m() =i,,
- -x(Sle")) - Q(u)).
Noticing that for i,j
(S(()) ifj
Ou,Pi(S)ee) -1 (1==)(((")))((11 if =
Thus
oy Q()) = 20x Q(u)),
and for j $1,
Dn, Q(u) = (St
+T, -
As a result,
w T Q2Q(u)
l |1 Ou, Q(u))
1,es
wi
12 (S(e)) +2 +
Σ (x
iES
tJAJES
$ Σ
w/ (Spe)) +
Σ
(wf + u
iES
iAAijs
3
Σ
W/l m (S(ee)))
< 3 max
iES
This finishes the proof.
Based on the first and second-orde -oderr derivatives of Q, we now introduce the following perturbation result:
Proposition (Proposition 3, restated). For any fixed r and u, u' E RNN, denote w == u. then it holds for any So E S that
[Q(u': So) Q(u:
Σ uylr, Quu; So)12. JESO
Σ (S((ulo)pu(So(1))u + max wi.. jeSo
3
Je
ii) In addition, if So is the maximizer of R(S; e over S for some ū 2 u element-wisely, then
QQu'::)) S)1
(So (Sole + 3 max w JESo
JESn
tii) In the uniform-reward setting, where r; 1, Vi [N], we have
3 max w JESU
[Q(u':S) - Q(; < Σ P, "pe
jESo
31

---

Proof. We have by Proposition 6
[Q(u': So) Quu; So) (VQ(u; ,
=QQ(u)) Quu: (VQ(u; So), w)) S
max w/. JES0
On the other hand, we have
(vQQ(u So). w| - Σ
Py(Solu))r - Q(u: Su)]|ay]
JES0
U5lry (u;;
(1 + Σ Cjes, U₁)
JESu
JESu
eylry Quu:2
Σ P:((ole)po(Suu)))) JESS
JESO
This finishes the proof of the statement (i).
To prove the second inequality, suffices to provide upper bound of Σ U5|r3 Quu; So)]: We first recall the following structural result of the revenue maximizer:
Proposition 8 (Lemmaa A.3, [5).. For any given denote S argmax Q(u; S), then it holds that
1. r2 2 Q(u: S), E For any u' S u point-wisely, it holds that Quu; 5) 2 (
By So is the maximizer of R(S;0), we have ry 2 @ for all j So by Proposition 8 We further have
Q(u: So) S max R(S:v) < max R( Q(ū),
3
thus then by
EjesTyus
Quu:5) 1 Ejes Uy
Σ
ey(r, Q(u;))) Quu: S),
we have
Σ uylr, Q(u; So)l <
Σ
0y(rg Q(u; So)) = Q(u; So) S 1.
JESo
JES
This finishes the proof of statement (ii).
Finally for statement (iii), we have by
E JES Vi = po(Sulo),
T3 - Qu; So) = 1+ Djeso 1/j
(o), < Σ
()(oolo)]rg - Quu: So)l
JE80
Σ
jeSo
this finishes the proof.
The proof of the above result relies on the condition that r, 2 R(S:e") for all j E S, which holds only when S is the best assortment under some ū 2 u. However, this does not apply to Algorithm 2 which based on elimination. assortments, which can be applied for analyzing climination- based algorithms.
handle this, we extend the result to a class of near-optimal
32

---

Proposition 9 (Proposition 4 restated), Under the same notation of Proposition 7 and suppose for some u 2 u it holds
R(So:e 2
max e(S:e") E, SES
then for c²,, w ū u and S seg we have
:(S":0) - R(So; v) 2
Pj (:((olu))o((oll)03 + 5 max wî + 28.
JESU
JES0
Proof. We have by statement (i) of Proposition
7
e(" - R(So; e²) Q(u: Quu: 5o)
- Q 5* - Q(ū;; So) + Q(ū;; So) - Quu;; So)
S E + [Q(ū; So) So)l
(25)
3
S +
Σ 0y(r, Quu: So))
Σ
py (Sole)) + jESo
max wz.
jESO
jESo
Denote
5/ = EjE E So: :j 2 Q(u; = == So: < So);
then by
Σ uj(r, Q(u: +
Σ
u5(r, So)) = Quu:
JES
JES
we have
Σ
0ylr, - Q(uuSu))
JES
Σ (5 (uu: - Σ (15(t--((u; Q(u:
JES
JE9
= 2 Σ (r(r; Q(u: 8o)) Quu So)
jEST
$ 2 Σ ug(r, S(u:St)) +2 Σ uy(Q(u:5t) (uu:So)
JES
JES
< 2Q(uu; S*) + 2p (So (Q(u - So)),
where in the last line we have used
Quu: = argmax seSx
Σ
Enltr Q S))
JES
and 0y 51+EEEs, 1/ = Po (Solv).
Denoting A = (Q(u; S*) Quu;; So)), we have then
25 reduces to
A < + V 22 + 2p ((o))))
Σ
(Sn (00 + max vn3
JE
JES.
< Σ (S(
+ max w/
3
+
Σ
(5(Solo) VA.
2 SE
JESO
JESO
Now using the elementary inequality for quadratic equation solutions:
B 1 + 4A
x² A+ 1 Bx
x
+ x B + VA
= 23 +2
33

---

for all x 2 0. We have
A $ 2B 22
Σ jESu
Ps (S + max wā 28, JESo
V
as desired.
D Proof of Results in Section
D.1 Proof of Proposition I and Corollary 1
Proof. For each j E S* and any À > 0, assume W.L.O.G. that j is exactly contained in ,
then by
H + E
Σ
ps(Sm))o(Smmmaae + XI
m= KeSm
Σ
Σ
Pa P + +
Σ
mDn, KESm
mSa;
:=25
we have then
|| - =
(Zg + イイzコІm5))
Ij x
(1-
2 13 03
1
(1
1
x. Zi Øj
1
$ $1/95
Tyar 7500 2,,,,
7
Y5or Zzzzz
Taking limit as Xy O and using the continuity of ||> 11211(00(00)))))>> leads || HT' (0+) S 5/5' Finally, by
Σ (p("))) (0)))) S (p((S))p jES
jes
V/
Vi Eijesmi (1+ ΣnES 0x)
(1 + Eres 1/
jeS
U/
Vj E1beemm (1+E bk)
(1 + ErES 11
JES.
1i maxjes,, (1 + Exesm )2
n2(1 + Ekes nx)
JES
max (1 ExES., 22) miny n1 (1 + E vR)
This finishes the proof of Corollary and the second inequality implies Proposition |
D.2 Details of Proposition 2
In this section we provide the detail on how to plug other confidence region results in Algorithm to achieve num--in-free offline learning guarantee. In [44), confidence region results with the radius (VVd|l=,,lH,,* (0-))) are available and we take the result in [44) establish the confidence region for example. Here we first restate the confidence region bound of 4E1
'it should noted that the original result in 44 includes an additional K dependency due to the self- concordant coefficient they established for the MNL likelihood function. This coefficient was later refined by [35] and incorporating their result eliminates the K dedeenddnccyy in (44.
34

---

Lemma (Proposition 3.3 and Lemma C.4 in 44
With the selection X /d/W and denoting
Dis == {r 0: [ - VI (0))
I 4 ( W) log(4Knd/0))
(26)
it holds that with probability at least 1 6,
|00b3 0* ( I 4v d(1 + W)3 logllogg(ga0 4Knd/6).
With Lemma 9 and 26 we now assign the LCB values for each j E [N] as
LCC == 2 Djj: of exp(a) if E Sk: J.CB 0 otherwise.
can be seen from Lemma that with probability at least 5,
5 u3
LCB S vd(1 3 (ogg(4Kn))) (5) [2; (D(
Now replacing the term üy by u uBCB the right-hand-side upper bound our analysis in Section A.3 leads to Proposition 2 as desired."
E Proof of Results in Section 5
E.1 Proof of Lemma
Lemma T is direct corollary of the following result from 47 53
Lemma 10. For any given X C {or E R ||a||| S }} threshold > 0 and regularizer X >> O, the following procedure starting with C 0:
while Fr X so that ||>||
| for Va = Evec 22 T AI do: add this x to
will stop at most
1 1 11
log (1+ p2)
:) + log
[+ (1+ 1
Cmax
e
steps.
Applying this lemma with
1 64W
A 1,
64V (T)g(T))
to each l separately then leads to the desired result.
E.2 Proof of Theorem 4
Based on the burn-in condition established in Lemma [ which incurs at most poly-logarithmic regret in T, remains bound the regret incurred from 7 T.
Again, suffices to perform regret analysis under the inequalities p and 100.. under which we can show that
W
2-8
S 28
EjEs P3 (S1))))
E Ene (SS1))
holds using the same argument for establishing
11
Now noticing that with the uniform revenue assumption ri = F for some S 1, statement i) in Proposition 3 can be refined to
[R(S v') R(Solv)) <
Σ Sp
Uglr, - R(Solv)1
Σ JeSo
Ps (550e))p(( (So + max w
2 JES.
3 + max w 2 JeSo
(1(
JES0
JESo
35

---

where the last inequality is by
Ejeso Vy
)
)²
12 3² DEjEs V/
Σ uylry R(Solo)) JESo
Σ JESO
Pug
1
jES,
Σ
Po ( o)p5 (So v).
1 Ejeso Vij
(1 Ejes, U3)
With this result, have the following analogue of Lemma directly in this setting: For every é and E Ae it holds under (9) and (10) that
R (S) R(S)0-) s 2 1,5
(27)
Plugging the subsequent analysis in the proof of Theorem 3 then leads
3
Σ -(S))-R(S)) 5
Σ
(o(S))o)ps(Sclu)- JES.
Σ
Ps (S: (S0) )2 + 2 JES.
max w )²
TETu.e
TETu.e
JES
Σ (S(l))
Σ Σ TET JES.
TET.. Σ
max max(wi wL ) JES,
Σ (S(l)) (d W) log(NT) + dlog(NN))
24
IETo.
Σ R(S*) R(S))) W)) log(TT) + dllog(NT)) TET
2A
(
where the last line is by Lemma 11 of 42 apply the fact
Now if we denote A = EleT., R(S*) R(S,) and
AS BB with A = (d + log(T) and B W)T + dlog(NN)) the desired result holds.
A $ AVA+B
E.3 Proof of Theorem 5
In this section, we show the following problem-dependent lower bound result:
Dependent Lower Bound). For any given 0 < R. < 1, we can find a class of problem instances V with uniform revenue and d-dimensional linear MNL choice feedback so that for any instance in V the corresponding parameter x² S R and for any policy n, there exists some instance in V so that
Theorem
Reg(T) 2 VRdT
over such instance.
The construction of hard instance for proving Theorem T only on minor modification of the proof in [17), and we just provide the detailed proof here for completeness.
Step 1: Construction of Hard Instances. We let 71 later, and given any K-sized assortment S, we consider the corresponding attraction value construction as
IN for all instances constructed
(1+E)
i 5, otherwise.
K
And we define the problem instance set as
Vx = {u.) S Sk).
can be seen that we always have S* (x = for every v, and
n+(1 e)
(S((*)
< 2n
(1+*0(1 +))²
36

---

holds for every o by definition.
Since there exists one-to-one correspondence between Sx and Vx via S - v interchangeably use the notations e and S for convenience.
Step 2: Verifying the Separation Condition. We have the following separation result over S Proposition 10. For every fixed So E S and corresponding uo E Vx. it holds for any S E S that
SubOpt(S)o80) 2
9K
as desired.
Proof of Proposition 10 Denoting R(-1uSu) by R(-) thorough the proof for simplicity, we have
R(Sa) = n²' +
+ K* (1 + E)
and for any S,
K (1 + nSn Sole/K K)
R(S) = 1 K² (1 + 1 inns Sol /ol//K
thus
R(Sa) R(S) (0 (1 + +))
(1 (1+ 10 (1+ (1+ (1x
<e -E))
(1+ x 1+ 2
9
N (K IS n Sol)e
9K
Step 3: Decomposing the Regret. Based Proposition T0
have
T
max Reg, (T; 2 vEVx
E. [SubOpt(SS;e))
SKk
DE
8*8
Es[K S (t))ll
9K Sk
SESx t=1
Nº
(T
Es[((i S.H))
9
K
SESK
iES t=1
8' T
Σ
Σ
Es (N.).
K[Skl
SESk YES
s(i K-1
Now for each i, we define
SK n {S c [N] : i $ S), then it holds that
N
ΣΣ
Es[N.- = Σ
Es(N.
Σ
[s
SESK iES
1= SESIcIES
stest
Σ
(Es -Es
Es|NN
+ Σ
[N.]
1=1 ('ES())
1=1
K-1
37

---

Now for the second term, we have
N
Σ
Σ S'EST
[s
= Σ
Σ
EN S ST
S'ESx-1 18S
For the first term, by Pinsker's inequality, denoting the probability induced by environment S' U (1) as P and induced by S' as Q, then
T
E [Buun - Es [Na]]
Ps (N₂ = Qs- t)
$ T
KL(PIIQ)-
As result, we have
max Reg
(T: 2
1-6 (T
ΣΣ [s(N..)
vEVK
9
K|Sk|
SESK iES
SK-
T
(T'
Σ Σ
(Qs))))0ss))
9
Skl
V2K
|2KSSK
SK
i=
S'EStO K-1
KT
2
1
Σ
(L((P))1Qs))
3
K|SK]
S'es
Where the last line is by
N
SK-1
K K
|Sx
N
1 3
when 4K & N.
Step 4: Upper Bounding the KL Divergence. We have for every S' SK-1 it holds that
(L((s>11Qs)) S
Σ
Es (XS))))
SES
Σ
<
SESHES$
Where the last line is by KL. ((15) as long as i $ S.
For every 3 containiig i, we have denote K' |S| and p, = (s)()))) (s(5) for j E S+.
then
For j =0,
K
K
Po %ol = K + xtt (K' S's''sss)
K+ x* (K' + (1
Kr
R"
K + xºt (K' +
1SS S'()
K
ii) For j # i,
(1 + 8)
22x*)2e
lpj - 1961 5
Po %0l <
K
K2
iii) For j =i, i,
1²* x111+3 +
R²
1p: qil
K + n² K"' + (1S 8' 1)$)
K *+** R² K'' + (')
eK*
(K CK*(K
+ x* (K' + +
K*C
2Ek*
K²
K
Now applying the following Proposition from
38

---

Proposition 11. Let P and Q be two categorical distributions on J items, with parameters Pı," ,P
and q IJ respectively. Denote also E = Pj -9j Then (L()))Q) E}=1 53/93-
we get
Σ SESIER
E2
4= (x*))
24=2x*
LE
Eg [Ni]
k*Ka
K*K
K
Final Step: Putting All Together. Using the above upper bound of KI. divergence, we get
kTeT 2
Σ
KL((Ps>1QQs) (1
9
KSK
K
i=
S' S'ES K-1
K* T
2
1
Σ
Es [No]] [Ni]
24
9
3
K|SK|
K
S'ES R-1
2
1
Σ
E
[
24
9
3
K|SK|
2
K
S'ESK
1 LigS'
K* Kt
2
1
Σ
Σ
Es [N:]
24s²
9
3
KISK|
K
S'ESK-1
iES'
2
|SK-1|
V12NTE2K*
9
3
K|SK
R² ET
2
1
K ET 2
VI2NTERR*)
2
/NT==*k/N)
9
3
N - K+
9 3
Selecting
e2
N
then leads to the (VVENN) lower bound, as desired.
512
V
Tex
E.4
Extension to Time- Varying Contexts
Another problem setting widely adopted in linear MNL and generalized linear bandit frameworks is the adversarial context setting with an initial exploration period [38 18, 31 42). In this setting, instead of always using the same feature map 2j. we allow the feature vector 2t,5 to vary with t. Furthermore, during the initial exploration period, the observed features Tt,j drawn i.i.d. from some distribution Po with Amin (Ez~P, [x= })> 2 oo for some do 0. In general. The fixed action setting does not fit this framework as it violates the eigenvalue lower bound assumption, making previous exploration-phan fixed feature set setting, can be readily extended to the time-varying context setting, achieving a regret of Õ(VaT + x- dd K). This holds under the same stochastic context assumption during the initial exploration phase and allows for an even simpler design the exploration phase, thanks the generality of Theorem]]
designs inapplicable. While our algorithmic description focuses on the
In this section, we extend Algorithm 2 to the setting that the observed context at each round can be different vectors in IRd, more precisely, at each time f, the i-th item is associated with a feature map Tz. à Rd And we impose the following eigenvalue assumption in the exploration phase, as in 42
Assumption 2. For some given tu, (=r,heeMM.eett)) are generated i.i.d. from some unknown distri-
bution P supported on the d-dimensional unit ball, with Amin (E [xx T1) 2 for some og >
We first present the modified algorithm for time-varying contexts in Algorithm 3 with modifications highlighted in blue. the elimination phase, the only change that item-wise uncertainty levels are computed over J4, instead of x; for each i, which then affects W and the UCB revenues. Thus the same analysis as in Section A.3 can be conducted to derive the same regret bound once the burn-in condition can be verified.
39

---

The main difference lies in the initial exploration phase, where any K-sized assortment can be selected for efficient exploration due Assumption
Algorithm 3 SupLinearMNL with Time- Varying Contexts
1: Input: Time horizon T, exploration length rp.TT
initialize log T, V1
5s+1 0.
2: for = ............ (S + 1) do
3: Select arbitrary assortment in Sk. add into pt/r]
4: end for
5: Vo - 0, compute 0g as (5).
6: for / = +S+ 1..... do
7: set A₁ = Sk S. = - 1
8: while S, do
9:
Compute W RUCB (S), VS E A as in 7
with wf,, := 72|1 m., (0)) V log(NNT
10:
if W.W. L. > 2- for some S E A then select such S Ac.
12:
V + De U {t}
13:
else if Wi, S 11/VT for all S E Ae then take the action argmax se RUCB (S)
Vo c LoU(1
16:
else
R maxsEA Ri,
RUCB(S)
Aet1 + { S Ae, R, (S) 2 R - 2-24+22
18:
19:
1+1+1
20:
end if
21:
end while
22:
end for
Now it sufficient to prove the following burn-in condition guarantee:
Lemma 11. With the selection =M "Moni[ddogp [d T/oo + /dlog(NT) K-1 WW), it holds that with probability at least 2/T, the event & n E with
: = 1 1 ((,,, 1 (0.) = (0'), (
8 (1oT,(0r. 0*)l 72 Lor/log(NNT)) T2V/
W W>r,j [N], [S]}
holds.
Proof. We need only show that with probability at least - 1/T, after the exploration phase, it holds for every that
Amin (H,,((0))) 2 64K / 64VW,
(28)
From this, we obtain
|0)l 64K / (N))
64 V|aa||2 $
which then allows the result follow naturally from Theorem 1 and Proposition
Now to prove (28). we simply recall the following result in and 38
Proposition 12 (Proposition in 42 & Proposition 1 in (3 ) For any constant B > 0, there exists
some abvolute constant C1, C2 so that with the selection
2
c vd c2v2log
2B
+
Kao
it holds with probability least 1 - 1/T that He,)(0*) 2 BI.
40

---

Now selecting T as in Proposition 12 with B = 64K (dlog(NT) V 64VW then finishes our proof.
E.5 Extension of OFU-MNL 44
In this section, we show that a simple plug-in argument based on the developed perturbation result Proposition 3 can extend the result in Theorem 3.4 of 44 for uniform revenue setting to the general revenue setting:
Theorem 6. The OFU-MNL algorittm (Algorithm 2,
44 satisfies the regret
RTg(T) S dvT + K d
up to logarithmic factors.
Proof of Theorem 6
Simply noticing that the OFU-MNI. algorithm always taking the optimistic
action
S = argmaxses, R(S UCB
for
UCB Un
max exp(xx.0) dE6
Vi [N],
with C. specified as in Lemma 9
Proposition 3.3 in [44] has shown that UCC 2 v vt [T'] with probability least 1 O(1/T), thus then we have under such event, it holds that 2 R(S.|o, 2 R(S*vv) Now denote UCB Wey = t
Vtj, we have then
T Σ
(Tg(T)) (( - R(S,vv) &
LCB R((S,l))
t=1
R(S (CC)) - R(S.lv) So
Σ JES.
Pj (Se ()) 3 max wiy
JES.
t=1
d Σ ( l1 ((0-) + 3d max(| (1,, '(0-)'
Sai
JESt
JES.
where (i) by statement ii) of Proposition by Proposition 3.3 and Lemma Finally, applying the elliptic potential lemma presented in Lemma leads to the desired result.
Experiment Results
In this section, present additional numerical results illustrate the effect of the burn-in condition and to compare Algorithm| with existing offline assortment optimization benchmarks.
F. Sensitivity to Burn-in Condition
To better understand the trade-off between the tightness of our confidence intervals (CIs) and the burn-in condition, we conduct set numerical experiments comparing our bound Theorem with that of 44 Our CIs are theoretically tighter than those in 35 3
in that the confidence radius is smaller by v factor, but requires additional burn-in condition and a conditional independence assumption. The following simulation demonstrates how violating the burn-in condition may lead to the failure of our CI guarantee, while satisfying it yields improved tightness.
F.1.1 Evaluation and Results
We compare the empirical tightness of the two confidence bounds using the following ratio:
10 0,
CI Ratio
max CI at eq
41

---

where the denominator corresponds to the theoretical confidence radius at coordinate e;. A smaller CI ratio indicates a tighter alignment between the theoretical CI and the actual estimation error, and thus lower likelihood of CI violation.
We evaluate the CI ratio under different burn-in constants, defined
max Snn
| (
Theoretically, our CI guarantee in Theorem requires Ç S 1/ 1/Vd, whereas the bound in 44 imposes no such restriction.
Value of Ç
0.130
0.134
0.141
0.160
0.335
CI ratio (Theorem 1)
2.563
2.831
3.147
4.052
5.617
CI ratio (44)
3.495
3,480
3,420
3.270
2.852
Table 2: Comparison of CI ratios under varying burn-in constants.
We present the result in Table 2 and defer the detailed experiment setup in the next section. As increases, our CI ratio grows noticeably, reflecting a higher risk of CI violation when the burn-in condition is not met. In contrast, the ratio for [22 remains stable across consistent with its mucory-independen nature. This comparison highlights a fundamental trade-off: our CI achieves tighter bounds under well-conditioned data but more sensitive to initialization.
F.1.2 Experimental Setup
We describe below how the feature map, parameter, and assortment are constructed to obtain results in Table
Feature Set and Parameters. For given K)) (assuming d even) and parameter radius W > 0. we define the item features as follows:
Type-1 items: For i S d 1, =; (canonical basis vectors).
Type-2 item: F. (1, 1)/vd.
The true parameter is set as 0* = (W, W.... .,, Wd
Assortment Sets. We consider two types of assortments:
Type-1 assortment: Sn = (d) containing only the Type-2 item.
Type-2 assortments: Let [d/K]. For each
define
S ((m 1) K (m 1)K ... min(mk,d)).
Observed Data. Given integers R4, n22 generate nı copies of S Si..... Sm and na copies of So. with choices sampled under the linear MNL model parameterized by (X, as above.
Relation Between W and Burn-in Constant. Under this construction, Ç increases monotonically with W. The mapping between W and { used in our experiments shown below.
Value of W
0.5
0.841
1.41
2.37
4.0
Value of Ç
0.130
0.134
0.141
0.160
0.335
Table 3: Mapping between W and burn-in constant Ç.
All results reported in Table are are based on d = 6, = 3, and n1 n2 = 500. This setup allows us to systematically vary W and thus Ç, thereby illustrating the relationship between burn-in strength and confidence interval validity.
42

---

F.2 Results for Offline Assortment Optimization
Since in online setting, Algorithm 2 is computationally inefficient. We focus on Algorithm in the offline setting. We consider two variants of our approach based on different confidence intervals: one derived from Theorem and the other from Lemma [ denoted by LCB-MLE and LCB-MLE-v2 respectively. These experiments are designed to examine the trade-off between statistical conservativeness and empirical performance, and to compare our results with the PASTA algorithm [26].
We evaluate the empirical performance of our proposed confidence-based algorithms under four representative settings that differ in coverage and model specification conditions. Settings and examine performance under varying coverage levels in the standard linear MNL model, while Settings and 4 study robustness under misspecified mixture-MNL environments.
Setting Full Coverage. In this setting, both the item features X and the true parameter 0 independently drawn from spherical uniform distributions. The observed assortments are uniformly sampled from all K-sized subsets of [NV] ensuring that every item is well covered. The experimental parameters are N = 30, d = K = 10, and W 1, and results are averaged over 10 repetitions.
LCB-MLE
LCB-MLE-v2
PASTA
100
0.0073
0.0087
0.0077
300
0.0056
0.0088
0.0048
500
0.0051
0.0082
0.0041
1000
0.0051
0.0069
0.0046
Table 4: Comparison of SubOpt Gap (smaller is better) under full coverage, N 30, d = K 10,
W = 1, over 10 repetitions.
Under full coverage, PASTA slightly outperforms both LCB-MLE variants. Moreover, LCB-MLE- v2-with its larger nower-confidence penalty- shows higher conservativeness and thus lower empiri- cal efficiency. This observation aligns with our theoretical insight: when all items are well explored, excessive conservativeness can lead under-selection and higher SubOpt gaps.
Setting 2: Partial Coverage. We next consider setting with partial coverage to examine robustness when the observation set does not fully span the item space. We use the same setup for (X, 0", N, K, and d as in Setting 1, and fix the total number of observations at n = 500. For each n", assortments constructed by including n² items from the optimal set and filling the remaining K n= items with randomly sampled non-optimal ones. Increasing n²* therefore improves the effective coverage of the optimal set.
n per S
LCB-MLE
LCB-MLE-v2
PASTA
0.0050
0.0057
0.0047
4
0.0004
0.0004
0.0021
0.0007
0.0000
0.0022
8
0.0003
0.0000
0.0019
Table 5: Comparison of SubOpt Gap (smaller better) under partial coverage.
Under partial coverage, both LCB-MLE variants consistently outperform PASTA. In particular, LCB-ML.E-v2 achieves the smallest SubOpt Gap, suggesting that stronger conservativeness improves robustness when data coverage is limited. These results reveal complementary pattern: LCB-MLE performs well in well-covered settings, whereas LCB-MLE-v2 is more effective in partially observed regimes.
Setting 3: Misspecification under mixture of MNL I. In this setting, we consider mixture MNL. model with two subgroups, where the second subgroup is selected with probability μ4, and the total sample size is fixed at 500. The generation of (X, 0*) and parameters (N, K, d) follows
43

---

μ
LCB-MLE
LCB-MLE-v2
PASTA
0.05
0.9312
0,9280
0.9316
0.20
0,9279
0,9248
0.9277
0.50
0.9246
0.9234
0.9246
0.70
0.9263
0.9267
0.9262
0.90
0.9312
0.9312
0.9309
Table 6: Comparison of Expected Revenue (larger is better) under mixed MNL model I.
the same configuration as in Setting 1. Each assortment consists of 5 items sampled from the first subgroup's 's optimal set and from the rest.
Since computing the true optimal assortment under a mixture MNL intractable, we evaluate performance using the expected revenue instead of SubOpt Gap. As μ approaches 0.5, model misspecification becomes more severe and the performance of all methods slightly degrades. Overall, all three algorithms perform comparably, showing that confidence based methods remain stable under mild model mismatch.
8
LCB-MLE
LCB-MLE-v2
PASTA
0.1
0,9332
0,9338
0,9326
0.2
0.9328
0.9330
0.9322
0.5
0,9313
0.9316
0,9308
0.7
0.9311
0.9314
0.9307
Table Comparison of Expected Revenue (larger is better) under mixed MNL model II.
Setting 4: Misspecification under mixture of MNL II. This experiment uses the same parameter setup as in Setting 3, with the mixing probability fixed at = 0.5. The distance between the two subgroups' parameters 6* is controlled by parameter As increases, model misspecification becomes more pronounced and overall performance declines. In this case, LCB-MLE-v2 slightly out- performs LCB-MLE and PASTA, indicating that stronger conservativeness may improve robustness under severe model mismatch.
44


Reviews:
[{"review_id": "rNNu5jkGiO", "reviewer": "Reviewer_nFhi", "summary": "In this paper, the authors consider the data-driven assortment optimization problem under the linear multinomial logit (MNL) choice model. \nThe first main result of the paper is the derivation of an improved confidence set associated with a regularized MLE of the parameter $\\theta^*$. This improvement is achieved by keeping track of the behavior of the empirical Hessian instead of relying on the worst-case condition number parameter as in prior work. Using this CI, the authors first propose and analyze an LCB-based offline assortment optimization algorithm, and then develop a sample-splitting based online regret minimization algorithm.", "questions": "**Q1 Empirical comparison of the new CI:** You mentioned in Line 174 that there exist CIs that do not require the burn-in conditions but have to pay an extra $\\sqrt{d}$ factor. Can you include some small-scale numerical experiments that compare your CI with that of [44, 3, 35] to see how they behave before and after the burn-in periods.   \n\n**Q2 Comparison with [31]:** At a glance, the general form of the confidence set derived in Theorem 1 looks similar to the one derived by Jun et al. [31] in their Theorem 1 for the case of $K=1$. Can you include some discussion on the main challenges in generalizing the ideas of [31] for any $K \\geq 1$. This will help us better understand the technical contributions of the paper. \n\n**Q3 Algorithmic details:** Perhaps I missed it in my reading, but how is the  \"exploration length $n_0$\" used in Algorithm 2? Also, the condition (4) seems to require the knowledge of the parameter $\\kappa$. Is that something that is usually known? Also, in Line 293 it is mentioned that Algorithm 2 is \"computationally inefficient\": can you present the exact computational complexity of the algorithm? \n\nMinor Questions/Comments \n\n* In the abstract the abbreviations MNL and MLE are used without introduction. Can you fix that? \n* Line 3: \"that removing the explicit\": Should it be \"that removes the explicit\"? \n* Line 8: \"where $n_{S^\\*}$ the number of times\": Should it be \"where $n_{S^*}$ denotes the number of times\"? \n* Line 162: What is $i$ in the displayed equation? Should it be $\\log p_j$ instead of $\\log p_i$?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths \n\n* The derivation of a more refined concentration result for the MLE that does not depend on the worst-case condition parameter $\\kappa$ is an interesting contribution. \n\n* By leveraging the improved concentration result of Theorem 1, the authors obtain tighter suboptimality gap (Theorem 2) bound in the offline setting, and an improved regret bound (Theorem 3) in the online setting. \n\nWeaknesses \n\n* While I did not observe any significant weaknesses, I think the results in this paper may not be immediately useful from a practical perspective. This is because they require a potentially large burn-in period to ensure Hessian conditioning, and furthermore, both the offline and online algorithms may become computationally infeasible in larger-scale problem instances.", "was_revised": true, "final_justification": "I am satisfied with the response of the authors to my questions, and I now have a better understanding of the technical contributions (w.r.t. [31] for example). Overall, my impression of the paper is positive, and I will retain my score as I think this is a nice incremental contribution to the literature.", "rebuttal": "Thank you for your valuable questions and suggestions! We greatly appreciate your feedback and provide our point-by-point responses below.\n\n\n**Q1. Empirical comparison of CI results.**\n\nWhen comparing our confidence interval results with those in [44, 3, 35], our bounds are consistently tighter in the sense that the confidence radius is smaller, due to a $\\sqrt{d}$-factor improvement. However, this comes at the potential cost of requiring an additional burn-in condition and a conditional independence assumption.\n\n\nIn the following simulation, we compare our confidence bounds with those in [44] under varying burn-in constants to illustrate the potential failure of our bounds when the burn-in condition is violated. We hope this illustration can help understand the underlying trade-off between CI tightness and risk of violation. Below, we first present the results and discussion, followed by the experimental setup.\n\n- **Result and Comments:**\n\nIn the table below, we compare the CI ratio, defined as \n\n$$\n\\text{CI ratio}:= \\max\\_i  \\frac{\\lvert \\hat\\theta_i  - \\theta^\\star \\rvert }{\\text{CI at }e_i} \n$$\nfor confidence interval results derived in our Theorem 1 and [44]. \nThe CI ratio measures how tightly the theoretical confidence bound captures the actual estimation error. A smaller CI ratio indicates a lower likelihood of violating the theoretical CI guarantee.\n\n\nWe make the test under different burn-in constants:\n$$\n\\zeta := \\max\\_{k\\leq n,j \\in S\\_k} \\lVert x_{kj} \\rVert\\_{H^{-1}(\\theta^\\star) }.\n$$\n\nTheoretically, our CI result in Theorem 1 requires  $\\zeta \\lesssim 1/\\sqrt{d}$ to holds and the CI result in [44] have no restriction on $\\zeta$.\n\n|     value of  $\\zeta$           | 0.130   | 0.134   | 0.141   | 0.160   | 0.335   |\n|--------------------|---------|---------|---------|---------|---------| \n| CI ratio in Theorem 1 | 2.563   | 2.831   | 3.147   | 4.052   | 5.617   |\n| CI ratio in [44]   | 3.495   | 3.480   | 3.420   | 3.270   | 2.852   |\n\nWe observe that as $\\zeta$ increases, our CI ratio in Theorem 1 also increases, indicating a higher likelihood of violating the theoretical bound. In contrast, the CI ratio in [44] remains stable as $\\zeta$ grows, which aligns with the differing theoretical requirements of the two confidence bounds.\n\n- **Experiment Setup - Feature Set and Parameter:** For a given $d,K$(W.L.O.G. suppose $d$ is even) and $\\beta >0$,  we construct the item-associated feature map set with $N = d$  as the following:\n\n- *Type-1 Items:* The first d-1 features $x_i$ for $i\\leq d-1$ are given by the canonical basis $x\\_i = e\\_{i}$.\n\n- *Type-2 Items* The last feature $x\\_{d}$ is given by $x\\_{i} = (1,1,...,1)/\\sqrt{d}$.\n\n- *Underlying Parameter $\\theta^\\star$* Given radius $W > 0,$ the $\\theta^\\star $ is set as $\\theta^\\star = (W,W,...,W)/\\sqrt{d}.$\n\n- **Experiment Setup - Assortment Sets:** With above construction of feature sets, we construct two types of assortments as the following:\n\n- *Type-1 Assortment:* A single-item assortment containing only the type-2 item $S_0 = \\{ d \\}$ as a single-item set that only contains item $d$.\n- *Type-2 Assortments:* Denote $m = \\lceil d/K \\rceil$, then for every $1\\leq k\\leq m,$ we set the $k$-th type-2 assortment as\n$$ S\\_k:= [ (m-1)K + 1, (m-1)K + 2, ..., \\min ( mK, d )  ] $$\n\n- *Observed assortment sets.* With above types of assortment sets. Given any number $n_1,n_2$, the observed assortment sets(and corresponding features and choices generated by linear MNL model with $X,\\theta^\\star$ above) is set as $n_1$ copies of $\\{S_1,..., S_m\\}$  and $n_2$ copies of $S_0.$\n\nWith above construction, we can fix the value of $n_1, n_2$ and moving $W$ to generate different environments with different level of burn-in constants $\\zeta$. In particular, under our construction $\\zeta$ is increasing as $W$ increases, as we shown in the table below:\n\n| Value of $W$ | 0.5   | 0.841 | 1.41  | 2.37  | 4     |\n|--------------------------|-------|-------|-------|-------|-------|\n| Value of $\\zeta$         | 0.130 | 0.134 | 0.141 | 0.160 | 0.335 |\n\n\nThis explains how we obtain environments to generate the results presented in table 1. Specfically, we select $d = 6, K = 3$ and $n1 = n2 =  500$ in the above experiment.\n\n \n**Q2. Technical comparison with [31].**\n\n\nThank you for raising this suggestion and question! We would acknowledge that our analysis follows the same overall framework in generalizing Theorem 1 of [31]. However, the detailed calculations require new arguments that explore the geometric landscape and self-concordant properties of $K$-MNL losses, which is a central topic in recent theoretical studies on MNL bandits.\n\nMore precisely, our main technical contribution lies in Lemma 6, where we carefully explore the curvature of the MNL loss to derive a confidence region that avoids dependencies on $K$ and $\\kappa$. This improves previous arguments in [42]( the only prior work that considers $d$-free confidence bounds under the independence condition), and parallels the refinement technique in [36], which is developed for different purpose( to obtain sharp variance-dependent bounds).\n\n\n**Q3.  Algorithmic details**\n\n-**Initial length $n_0$ in Algorithm 2** Thank you for pointing out this issue! It should not be an input to Algorithm 2, and we will remove it in the revised version. We apologize for the confusion caused.\n\n-**Prior knowledge of $\\kappa$** In general, we cannot assume a strong prior on $\\kappa$. However, it is relatively reasonable to assume prior knowledge of an upper bound $W$ on the parameter norm, as is common in previous work. Given this, we can derive a conservative lower bound on $\\kappa$ that scales as $\\exp(-K W)$, which is sufficient to serve as an algorithm input.\n\n-**Computation Complexity.** The elimination step of the algorithm 2 requires to search over the whole $\\mathcal{A}_l$, whose complexity scales as $O(N^K)$ in the worst case.\n\n**Q4. Writing Suggestions and Typos.**\n\nThank you so much for the suggestion and pointing out those typos! You are absolutely right on the problems in line 3, 8, 162, we will correct those problems in the revised version. We will also clarify the terms 'MLE', 'MNL' when they first appears to improve clarity."}, {"review_id": "w9ayc9goh4", "reviewer": "Reviewer_iMxr", "summary": "The paper studies the assortment optimization problem: choosing a maximizing subset (of revenue) of size K among N arms.The authors provide a new, sharper, confidence bound for the multinomial logit based on a variance-aware analysis. The authors then use the improved confidence region of the algorithm to estimate the optimal subset using a pre-collected dataset $\\mathcal{D}$. Then they propose an algorithm for an online variant of the problem: SupCB when the number of arms scales exponentially with d.", "questions": "There is theoretical motivation for this work but given the advances in other fields, how does this work practically compare with others? How well does this method do in recommendation on existing datasets?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "While the work is theoretical, given the advances in adjacent fields, it would be good to do comparisons on existing algorithms and even benchmarks that aren't related to bandits. Suppose you are given a subset of featurized data points and you are asked to estimate the optimal subset, you could use a neural network based algorithm to rank the top K items. This will not have any guarantees like the user provides but how would it perform in practice compared to this algorithm? Given the motivation for the work it would help determine if this paper is of purely theoretical value: the improved, sharper confidence bound or if there is a more practical application.\n\nClarity: $\\kappa$ is mentioned in the abstract and introduction without a formal definition. This makes the paper harder to read as one of the improvements is on the dependence on that parameter.", "was_revised": true, "final_justification": "The authors comments and the detailed discussion and responses have made me increase my score", "rebuttal": "Thank you for raising these important empirical concerns and suggestion on introducing formal definition of $\\kappa$ in abstract and introduction! \n\nWe will add a brief definition of $\\kappa$ to improve clarity in the revised version. \n\nRegarding the practical applications, we acknowledge that our work has limitations in terms of direct applicability to real-world systems such as recommendation engines. A key assumption in our setting is the **presence of a known linear feature representation of items**, where the only unknown is the linear interaction parameter $\\theta^\\star$.\nThis contrasts with the broader literature on recommendation systems, where representation learning plays a central role, and the optimal recommendations are often learned jointly with the representations—typically through end-to-end models such as deep neural networks, as the reviewer mentioned.\n\nThis fundamental difference limits the direct applicability of our algorithm and theoretical results to the types of problems addressed in modern recommendation systems. In particular, the challenge of learning feature representations from data is central in those systems but falls beyond the scope of our work, which focuses on the linear MNL bandit setting with known features. We view integrating feature learning into this framework as an important and promising direction for future research, which could potentially start with neural network–based MNL bandit formulations, such as the recent work [R1]—but this is beyond the scope of the present study.\n\nFinally, although our emphasis is primarily theoretical, we have included several synthetic experiments that we hope will be of interest to reviewers. These include: \n\n- evaluating how the burn-in condition affects the confidence interval in Theorem 1, discussed in our response to reviewer nFhi;\n\n- comparing our method with the PASTA algorithm, a benchmark from prior work on offline linear MNL models, discussed in our response to reviewer LNHW;\n\n- assessing the robustness of our method under model misspecification, discussed in our response to reviewer LNHW.\n\nWe hope these additional experiments can provide several empirical supports for our theoretical work.\n\n[R1] Bae, Seoungbin, and Dabeen Lee. \"Neural Logistic Bandits.\" arXiv preprint arXiv:2505.02069 (2025)."}, {"review_id": "KYdXwfz2Bd", "reviewer": "Reviewer_LNHW", "summary": "This paper studies data-driven assortment optimization under the MNL model. The authors first propose sharper confidence regions for the MLE of the linear MNL model, which improves upon the best known result by far. Based on these confidence regions, they design (a) a pessimistic (lower confidence bound) algorithm for the offline setting, which requires only item-level coverage rather than full assortment coverage; (b) an online version using a modified SupCB framework. These contributions represent theoretical advancements in both offline and online assortment optimization under the linear MNL model.", "questions": "1) While Theorem 1 assumes a burn-in condition, Proposition 2 suggests it can be relaxed at the cost of an additional \\sqrt{d} factor. Could you clarify how sensitive the algorithm performance is to the tradeoff of using/relaxing this condition?\n\n2) You note the algorithm is computationally inefficient due to the enumeration of assortments. Could the proposed method be adapted to more practical heuristics while retaining theoretical guarantees?\n\n3) If the linear MNL model is misspecified (e.g., user choice follows a nested logit or a mixture model), how would the proposed methods degrade? Are there robustness guarantees?\n\n4) While the work is theoretical, are there plans to validate the findings on synthetic or real-world e-commerce datasets to demonstrate actual performance improvements and coverage requirements? Moreover, could the analysis framework extend beyond assortment optimization, e.g., to recommendation systems or pricing models with similar choice structures?", "limitations": "Yes, the authors discuss key limitations throughout, particularly the dependency on the burn-in condition for tight bounds and the computational inefficiency of the SupCB-based algorithm.\n\nThis is a pure theoretical paper so no potential negative societal impact of their work.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strength: (1) The theoretical results are solid, clearly stated, and well-justified. The paper is relatively well written and easy to follow, despite the heavy amount of math. (2) The work pushes the boundary of what is known in both online and offline linear MNL bandits. Its improvements over prior state-of-the-art in both theory and algorithm design. I believe this paper makes a valuable contribution to the field.\n\n\nWeakness: (1) The analysis requires a “burn-in” condition for sharper bounds, though this is partially addressed with a workaround at the cost of a \\sqrt{d} factor. Practical implications (e.g., computational scalability in real-world settings) are briefly mentioned but not deeply explored. (2) Due to its technical depth, some sections (especially in the online algorithm) are dense and could benefit from additional intuition or streamlining for a broader audience. But overall none of the weakness is significant; this is a clearly a good paper and makes novel contribution.", "was_revised": true, "final_justification": "Good paper. I’ll retain my positive rating.", "rebuttal": "Thank you for your valuable questions and suggestions! We greatly appreciate your feedback and provide our point-by-point responses below.\n\n**Q1: The sensitivity of algorithm performance under burn-in conditions and the trade-off.**\n\nThank you for this insightful question. In the revised version, we have included several numerical studies examining the sensitivity of our confidence interval (CI). Below, we highlight some key observations related to this issue and refer the reviewer to our response to Reviewer nFhi for additional details. For clarity, we denote the burn-in factor as\n$$ \\zeta:= \\max\\_{k\\leq t, j \\in S\\_k} \\lVert x\\_{kj} \\rVert\\_{H^{-1}(\\theta^\\star)} $$\nfor simplicity.\n\n- **Sensitivity of CI result in Theorem 1.** While there is no clear phase-transition threshold $\\alpha^\\star$ for the burn-in constant $\\zeta$—i.e., no sharp point at which the CI fails for $\\zeta > \\alpha^\\star$ and holds for $\\zeta < \\alpha^\\star$—our results show that the CI ratio increases with $\\zeta$. This trend may indicate a potential violation of the our CI guarantee in Theorem 1 in the large $\\zeta$ regime.\n\n- **Stability of the CI bound in Proposition 2( from [44]).** The CI ratio of [44] remains stable as $\\zeta$ increases. This aligns with the theoretical guarantee in Proposition 2, which does not require a burn-in condition.\n\n- **Better Trade-off between the two CI in algorithm design.** In practice, we may wish to adaptively select between the two confidence intervals to perform well in both small and large $\\zeta$ regimes.\n\nOne way to enable such adaptivity is by computing a data-driven upper bound on $\\zeta$: First, note that $V_t$, defined in line 170 of our paper, is computable. From the dominance relation $H_t(\\theta^\\star) \\succeq \\kappa V_t$, we have\n$$ \\zeta = \\max\\_{k\\leq t, j \\in S\\_k} \\lVert x\\_{kj} \\rVert\\_{H_t^{-1}(\\theta^\\star)} \\leq  \\kappa^{-1/2} \\max\\_{k\\leq t, j \\in S\\_k} \\lVert x\\_{kj} \\rVert\\_{V_t^{-1}}. $$\nLetting\n $$\\hat{\\zeta}:= \\max\\_{k\\leq t, j \\in S\\_k} \\lVert x\\_{kj} \\rVert\\_{V_t^{-1}},$$\nwe arrive at a fully data-driven quantity. Then for any threshold $\\alpha > 0$, a sufficient condition for $\\zeta \\leq \\alpha$ is $\\hat{\\zeta} \\leq \\kappa^{1/2} \\alpha$. Moreover, if an upper bound on the parameter norm $W$ is available, we can obtain a (possibly conservative) lower bound on $\\kappa$, making this condition verifiable from observed data.\n\nIn particular, we can simply switch to the CI from Theorem 1 if and only if $\\hat{\\zeta} \\leq \\kappa^{1/2} \\alpha$, where $\\alpha$ could be, for example, the burn-in threshold in Theorem 1. We hope this provides a practical guideline for balancing the two types of confidence bounds.\n\n\n**Q2: Practical heuristics to improve computational efficiency for Algorithm 2.**\n\nThank you for this interesting question! While several heuristics have been proposed in the MNL setting to improve enumeration efficiency in MNL bandits (e.g., the DP-based approach and greedy swapping heuristics discussed in Section 5 of [18]), **we believe that developing similar heuristics in our setting may be significantly more challenging.**\n\nThe main difficulty lies in the nature of the assortment space $\\mathcal{A}\\_\\ell$: Unlike [18], where enumeration is performed over all $K$-sized assortments—a well-structured and easily verifiable set—the collection $\\mathcal{A}\\_\\ell$ in our setting is exponentially large and *unstructured*. This means that for any given assortment $S$, determining whether it belongs to $\\mathcal{A}_\\ell$ may require searching through (or storing) all $\\lvert \\mathcal{A}\\_\\ell \\rvert$ elements. In contrast, in [18], one can simply check whether $S$ is of size $K$ to verify feasibility. This lack of structure makes heuristic design for our setting particularly difficult.\n\nWe will include the above discussion in the revised version to clarify the challenges involved.\n\n\n**Q3\\& Q4(a): Empirical studies and performance under model misspecification.**\n\nWe thank the reviewer for pointing out direction for taking numerical studies. While our algorithm 2 is computationally in-efficient thus hard to take empirical studies. We have added several numerical studies on our Algorithm 1 in the offline setting. We have compared Algorithm 1 with two types of CI( Theorem 1 and Proposition 2), denoted by LCB-MLE and LCB-MLE-v2, to illustrate the trade-off author raised in question 1. We have also compared our result with the PASTA algorithm in [26]. We have conduct the experiment in 4 different settings, as detailed below:\n\n\n**Setting 1: Full Coverage Setting.**\n\n**Table 1: Comparison of SubOpt Gap (smaller is better) under full coverage, $N = 30, d = K =10, W = 1$, over 10 repetitions.**\n\n\n| n | LCB-MLE | LCB-MLE-v2 | PASTA  |\n|---------|---------|------------|--------|\n| 100     | 0.0073  | 0.0087     | 0.0077 |\n| 300     | 0.0056  | 0.0088     | 0.0048 |\n| 500     | 0.0051  | 0.0082     | 0.0041 |\n| 1000    | 0.0051  | 0.0069     | 0.0046 |\n\n\nIn this setting, both the item features $X$ and the true parameter $\\theta^\\star$ are independently drawn from spherical uniform distributions. The observed assortments are sampled uniformly from all possible $K$-sized subsets of $[N]$. Under this setup, every item is guaranteed to be sufficiently covered. We observe that PASTA outperforms both LCB-MLE algorithms, and that LCB-MLE-v2—with its larger LCB penalty—performs worse than LCB-MLE. A possible explanation is that the increased penalty in LCB-MLE-v2 results in overly conservative decisions in this well-covered setting.\n\n\n\n\n**Setting 2: Partial Coverage Setting.**\n\n**Table 2: Comparison of SubOpt Gap (smaller is better) under partial coverage**\n\n| $n^\\star$  | LCB-MLE | LCB-MLE-v2 | PASTA  |\n|------|---------|------------|--------|\n| 2    | 0.0050  | 0.0057     | 0.0047 |\n| 4    | 0.0004  | 0.0004     | 0.0021 |\n| 6    | 0.0007  | 0.0000     | 0.0022 |\n| 8    | 0.0003  | 0.0000     | 0.0019 |\n\nIn this setting, we use the same $X$ and $\\theta^\\star$ generation and $N,K,d$ as in Setting 1, with a fixed sample size of $n = 500$. For each $n^\\star$, assortments are constructed by sampling $n^\\star$ items from the optimal set and the remaining $K - n^\\star$ from other items, creating partial coverage. As $n^\\star$ increases, coverage of the optimal set improves. We observe that both LCB-MLE algorithms outperform PASTA, with LCB-MLE-v2 performing best, likely due to its stronger conservativeness under partial coverage.\n\n\n**Setting 3: Misspecification under mixture of MNL I.**\n\n**Table 3: Comparison of Expected Revenue (larger is better) under mixed MNL model I.**\n| $\\mu$ | LCB-MLE | LCB-MLE-v2 | PASTA  |\n|-------------|---------|------------|--------|\n| 0.05        | 0.9312  | 0.9280     | 0.9316 |\n| 0.20        | 0.9279  | 0.9248     | 0.9277 |\n| 0.50        | 0.9246  | 0.9234     | 0.9246 |\n| 0.70        | 0.9263  | 0.9267     | 0.9262 |\n| 0.90        | 0.9312  | 0.9312     | 0.9309 |\n\nIn this setting, we consider a mixture MNL model with two subgroups, where the second group is selected with probability $\\mu$, and total sample size is $n = 500$. The generation of $X$, $\\theta^\\star$, and parameters $N$, $K$, $d$ follows Setting 1. Each assortment consists of 5 items sampled from the first group's optimal set and 5 from the rest.\n\nSince computing the optimal assortment under a mixture MNL is intractable, we evaluate performance using expected revenue instead of SubOpt.\n\nAs $\\mu$ approaches 0.5, model misspecification increases and performance degrades. All three algorithms perform similarly across settings.\n\n**Setting 4: Misspecification under mixture of MNL II.**\n \n**Table 4: Comparison of Expected Revenue (larger is better) under mixed MNL model II.**\n| Delta | LCB-MLE | LCB-MLE-v2 | PASTA  |\n|-------|---------|------------|--------|\n| 0.1   | 0.9332  | 0.9338     | 0.9326 |\n| 0.2   | 0.9328  | 0.9330     | 0.9322 |\n| 0.5   | 0.9313  | 0.9316     | 0.9308 |\n| 0.7   | 0.9311  | 0.9314     | 0.9307 |\n\nIn this setting, we use the same parameter setup as in Setting 3, with $\\mu$ fixed at $0.5$. The distance between the two subgroups' parameters $\\theta^\\star$ is controlled by a parameter $\\delta$.\n\nAs $\\delta$ increases, model misspecification becomes more severe and performance degrades. In this setting, LCB-MLE-v2 outperforms LCB-MLE, which outperforms PASTA. This suggests that stronger conservativeness may improve performance under this type of misspecification.\n\n**Q4(b): Extensions the analysis framework to other settings with similar structure.**\n\nYes, our results can be extended to other settings. One promising direction is the joint assortment and pricing framework considered in [R1, R2], where actions include both assortment selection and item pricing $p$. In this model, the final choice outcome can still be viewed as a sample from a linear MNL model incorporating both utility parameters and prices. This suggests that our Theorem 1, particularly the confidence bound construction, can also apply.\n\nHowever, this extension poses computational challenges, as optimizing over both assortments and prices increases the overall complexity. Combining this with UCB/LCB-based algorithm design, as discussed in [R1, R2], may introduce further complexity and warrants future investigation.\n\n\n[R1] Miao, Sentao, and Xiuli Chao. \"Dynamic joint assortment and pricing optimization with demand learning.\" Manufacturing & Service Operations Management 23.2 (2021): 525-545.\n\n[R2] Erginbas, Yigit Efe, Thomas Courtade, and Kannan Ramchandran. \"Online Assortment and Price Optimization Under Contextual Choice Models.\" The 28th International Conference on Artificial Intelligence and Statistics."}, {"review_id": "oMMyo93uT6", "reviewer": "Reviewer_NL9u", "summary": "This paper addresses the assortment-optimization problem under a linear-utility multinomial logit (MNL) choice model. It develops algorithms for both the offline setting—where previously collected data are used to minimize the suboptimality gap—and the online setting—where sequential interactions are used to minimize cumulative regret. First, the authors establish an improved confidence region for the unknown true MNL parameter. In the offline setting, they propose a pessimistic algorithm based on per-item coverage and establish an improved suboptimality-gap bound that, unlike prior bounds, does not depend on the feature dimension $d$ or the problem-dependent constant $\\kappa$ and does not require full coverage of the optimal assortment $S^*$. In the online setting, they design a SupCB-based algorithm that achieves cumulative regret $O(\\sqrt{d T\\log N})$.", "questions": "1. How does Assumption 1 differ from assuming $\\set{(X_t,S_t)}$ are i.i.d.? Can you give an example where $(X_t,S_t)$ may be dependent over time but the $i_t$ remain conditionally independent?\n\n2. In Line 172, what precisely is the improvement in the burn-in condition compared to [42]? Does satisfying [42]’s burn-in condition imply that the condition of this paper also holds?\n\nMinor Comments\n\n1. **Typo** (Line 65): “shows” → “show.”\n2. **Typo** (Line 297): “a improved” → “an improved.”\n3. **Missing Definition** (Line 167): $H^\\lambda\\_D(\\theta^*)$\n4. **Notation Inconsistency** (Line 203): Clarify $p_j(S^*)$ notation.", "limitations": "The authors acknowledge the computational inefficiency of the SupCB algorithm in Section 5.2, which may hinder real-world adoption.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "[Quality]\n- The theoretical proofs for the paper’s main contributions (Theorems 1, 2, and 3) are presented in detail in the appendix, and the necessary auxiliary lemmas are explained clearly. Due to time constraints, I did not rigorously verify every proof in the appendix; I focused mainly on the proof of Theorem 1 and did not find any obvious technical errors. Moreover, the advantages of the proposed methods over prior work in both the offline and online settings are well articulated, and the tightness of the algorithms is supported by the lower bound in the uniform‐revenue case (Theorem 4).\n\n[Clarity]\n- The main text is relatively well written and easy to understand, but it would be beneficial to include a proof sketch before each main‐theorem proof in the paper or appendix. I also recommend a thorough grammar check, as there are minor grammatical errors. Additionally, adding a Conclusion section to the main text would improve readability.\n\n\n[Significance & Originality]\n- This paper proposes improved statistical guarantees for offline and online settings based on an MLE‐derived confidence region for the true MNL choice parameter. While recent MNL‐bandit literature has explored $\\kappa$‐improved regret bounds, most use online‐update methods or incur an extra $\\sqrt{d}$ factor when using MLE. In contrast, this work establishes $\\kappa$- and $d$-independent improvements under an MLE framework, representing a meaningful theoretical advance.\n\n__Weaknesses__\n- There is no experimental validation to support the theoretical results.\n- Although the paper achieves $\\kappa$-improved sub-optimality gaps and regret bounds in both settings, verifying the burn-in condition (e.g., whether Eq. (4) holds) requires prior knowledge of $\\kappa$, which may not be available in practice. This represents a critical weakness compared to \\[35, 44].\n- As noted by the authors, SupCB‐type algorithms are computationally inefficient. Moreover, Algorithm 2’s regret bound depends on the total number of items $N$, limiting applicability when $N$ is very large (or infinite). Thus, although tight in $d$, the proposed algorithm may be impractical for large‐scale problems.", "was_revised": true, "final_justification": "The author-reviewer discussion has satisfactorily addressed my questions, and I appreciate that the authors have appropriately conducted the additional experiments requested by other reviewers. However, I believe that improvements in the readability of the current manuscript are still needed. Therefore, I will maintain my current evaluation.", "rebuttal": "Thank you for your valuable questions and suggestions! We greatly appreciate your feedback and provide our point-by-point responses below.\n\n**Q1: Difference between Assumption 1 and i.i.d. assumption.**\n\nCompared to the i.i.d. assumption over $(X_t,S_t)$, Assumption 1 requires only **independence among $(i\\_t)\\_{t=1}^T$ conditional on $\\{ (X\\_t,S\\_t) \\} \\_{t=1}^T$**. This still allows complicate dependence among $(X\\_t,S\\_t)$ across $t$.  \n\nAn example of generating samples that satisfy conditional independence in $i_t$ is the SupCB algorithm we present in Section 4, originally inspired by [8]. The key to achieving this property is ensuring that the decision-making process does not depend on past choice observations. After the warm-up phase, each layer of Algorithm 2 uses only the $(X_t, S_t)$ information from samples collected during step (a) to compute the confidence region, which then guides future exploration actions in subsequent rounds of step (a). This design ensures that the samples used to construct the confidence region are independent of the observed choices at this layer, thereby satisfying the conditional-independence requirement on $(i_t)$.\n\n\n**Q2: Comparison of our burn-in condition to those in [42].**\n\nUnder our notation with $\\lambda = 0$, the confidence bound result in [42] can be stated as follows:\n\nUnder the burn-in condition,\n$$ \\lambda\\_{\\min}(V_t) \\gtrsim \\kappa^{-4}d^2 \\text{ with }  V_t = \\sum_{k=1}^t \\sum_{j\\in S_t} x_{k,j}x_{k,j}^\\top, \\tag{R1}$$\n\nit holds with probability at least $1-\\delta$ that\n\n$$ \\lvert x^\\top(\\hat\\theta_D - \\theta^\\star) \\rvert \\lesssim \\kappa^{-1} \\lVert x \\rVert_{V_t^{-1}} \\tag{R2}.$$\n\nNow we compare the result in [42] with ours:\n- **Burn-in condition.** Comparing the burn-in condition in (R1) and the corresponding confidence bound in (R2) with our results, note that from the inequality\n$$ H_t(\\theta^\\star) \\succeq \\kappa V_t,  \\tag{R3} $$\nwe have \n\n$$\\text{(R1) holds }\\implies  \\lambda_{\\min}(H_t(\\theta^\\star)) \\geq  \\kappa  \\lambda_{\\min}(V_t) \\gtrsim  \\kappa^{-3} d \\gtrsim d \\implies  \\lVert x \\rVert_{H_t(\\theta^\\star)^{-1}} \\lesssim 1/\\sqrt{d}, \\forall \\lVert x \\rVert_2\\leq 1.  $$\n\nTherefore, the burn-in condition required in [42] holds implies that our burn-in condition is also satisfied.\n\n- **Confidence interval length.** By (R3), we have for any $x$, \n\n$$ \\lVert x\\rVert_{H_t^{-1} (\\theta)}  \\lesssim  \\kappa^{-1} \\lVert x \\rVert_{V_t^{-1}} ,$$\n \nthis shows our confidence interval length is smaller than (R2) result provided in [42].\n\n**Typos.**\n\nWe thank the reviewer for pointing out the typos and limitations mentioned in the weaknesses and minor comments. We will correct the typos and further acknowledge the limitations regarding the $\\kappa$ prior in the revised version. Specifically, we will discuss the related results from [35, 44] below our theoretical guarantee for the initialization phase in Algorithm 2 to improve clarity.\n\n**Empirical results**\n\nRegarding the experiment results, we have added several numerical experiments, including the \n\n- *Illustration of burn-in condition:* We provide an empirical illustration of our confidence bounds under varying burn-in constants, demonstrating the sensitivity to the burn-in condition in Theorem 1. Please refer to our response to Reviewer nFhi for detailed results and setup.\n\n- *Offline MNL bandits:* We compare our approach with the PASTA algorithm [26] for offline linear MNL bandits under full coverage, partial coverage, and misspecified settings. Details can be found in our response to Reviewer LNHW.\n\nWe hope these additional experiments can offer empirical evidence to complement our theoretical contributions."}]

Author rebuttal:

Meta-review: This paper improves the performance bound of Linear MNL Bandits.

The contribution is very clear and solid. The improved concentration result is very relevant and a meaningful progress.
Decision: Accept (poster)