Nearly Minimax Optimal Regret for Multinomial Logistic Bandit
Authors: Joongkyu Lee
Min-hwan Oh
Venue: NeurIPS 2024 poster (2024)
Keywords: Bandit
Contextual Bandit
Multinomial Logistic Bandit
Minimax Regret
Primary area: bandits
TL;DR: In this paper, we investigate an adversarial contextual multinomial logit (MNL) bandit problem and establish minimax optimal lower and upper regret bounds.

Abstract: In this paper, we study the contextual multinomial logit (MNL) bandit problem in which a learning agent sequentially selects an assortment based on contextual information, and user feedback follows an MNL choice model.
There has been a significant discrepancy between lower and upper regret bounds, particularly regarding the maximum assortment size  $K$. Additionally, the variation in reward structures between these bounds complicates the quest for optimality. Under uniform rewards, where all items have the same expected reward, we establish a regret lower bound of $\Omega(d\sqrt{\smash[b]{T/K}})$ and propose a constant-time algorithm, OFU-MNL+, that achieves a matching upper bound of $\tilde{\mathcal{O}}(d\sqrt{\smash[b]{T/K}})$. 
We also provide instance-dependent minimax regret bounds under uniform rewards.
Under non-uniform rewards, we prove a lower bound of $\Omega(d\sqrt{T})$ and an upper bound of $\tilde{\mathcal{O}}(d\sqrt{T})$, also achievable by OFU-MNL+. Our empirical studies support these theoretical findings. To the best of our knowledge, this is the first work in the contextual MNL bandit literature to prove minimax optimality --- for either uniform or non-uniform reward setting --- and to propose a computationally efficient algorithm that achieves this optimality up to logarithmic factors.

Nearly Minimax Optimal Regret for Multinomial Logistic Bandit
Joongkyu Lee Seoul National University Seoul, South Korea jklee0717@smu .c.
Min-hwan Oh Seoul National University Scoul, South Korea minoh@snu. ac. kr
Abstract
In this paper, we study the contextual multinomial logistic (MNL) bandit problem in which a learning agent sequentially selects an assortment based on contextual information, and user feedback follows an MNL choice model. There has been a significant discrepancy between lower and upper regret bounds, particularly regarding the maximum assortment size K. Additionally, the variation in reward structures between these bounds complicates the quest for optimality. Under uni- form rewards, where all items have the same expected reward, we establish a regret lower bound of ((d'T//) and propose a constant-time algorithm, OFU-MNL+, that achieves a matching upper bound D(d/T/K)) We also provide instance- dependent minimax regret bounds under uniform rewards. Under non-uniform rewards, prove lower bound of ((dvTT) and upper bound of (dvTT), also achievable by OFU-MNL+ Our empirical studies support these theoretical findings. To the best of our knowledge, this is the first work in the contextual MNL bandit literature to prove minimax optimality for either uniform or non-um non-uniform reward setting and propose computationally efficient algorithm that achieves this optimality up to logarithmic factors.
Introduction
The multinomial logistic (MNL) bandit framework 47 48
5 53 describes sequential
assortment selection problems in which an agent offer sequence of assortments of at most K item from set of N possible items and receives feedback only for the chosen decisions. The choice probability of each outcome is characterized by an MNL. model (37]. This framework allows modeling of various real-world situations such as recommender systems and online retails, where selections of assortments are evaluated based on the user-choice feedback among offered multiple options.
5) where the features of items and possibly contextual information about a user at each round are available. previous studies have proven the minimax optimality of contextual MNL bandits. Chen et al. [16] proposed regret lower bound of R(dvT) T/ K). where d is the number of features, T is the total number of rounds, and K is the maximum size of assortments, assuming the uniform rewards, i.c., rewards are all same for each of the total N items. Furthermore, Chen and Wang [15] established regret lower bound of R(v NT) in the non-contextual setting (hence, dependence on N appears instead of d), which is tighter in terms of K. It important note the difference in the assumptions for the attraction parameter for the outside option Ug. Chen and Wang [15] assumed for the attraction parameter for the outside option Up K, whereas Chen et al. [16] assumed Un Therefore, it remains an open question whether and how the value of Up affects both lower and upper bounds of regret.
In this paper, we study the contextual MNL bandit problem
16 40
44
Despite many recent advances, [T6] 40
24 (5) however,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Comparisons of lower and upper regret bounds in related works on MNL bandits with T rounds, N items, the maximum size of assortments K, d-dimensional feature vectors, and problem- dependent constants 1/K (K²) and k' - O)) Ô represents big-O notation up to logarithmic factors. For the computational cost (abbreviated as "Comput."), we consider only the dependence on the number of rounds t. "Intractable" means non-polynomial runtime. The notation denotes
not applicable. The starred (*) papers only consider the non-contextual setting.
Regret
Contexts
Rewards
9p
Comput. per Round
Chen et al. [66
Ríd/T/Ki
Uniform
@(1)
Agrawal et al. 8
((/NT/K)
Uniform
((K)
Lower Bound
Chen and Wang 15
NT
Uniform
((K)
This work (Theorem
RO dv'T)
Uniform
Any value
This work (Thcorem
((d/T)
Non-uniform
@[1]
Chen et al. [16
Oldv')
Stochastic
Non-uniform
0(1)
Intractable
Oh and Tyengar 41
((d)T/k)
Stochastic
Non-uniform
@(1)
O(1)
Upper Bound
Oh and Tyengar 40
Adversarial
Non-uniform
@(1)
O(t)
Perivier and Goyal 44
VRT)
Adversarial
Uniform
e(1)
Intractable
This work (Thcorem)
Ô LanK dvT)
Adversarial
Uniform
Any value
O(1)
This work (Theorem
ŌldvT)
Adversarial
Non-uniform
@(1)
O(1)
Regarding regret upper bounds, Chen et al. [16] proposed an exponential runtime algorithm that achieves a regret of (dv/T) in the setting with stochastic contexts and the non-uniform rewards.
Under the same setting, Oh and Iyengar [41] and Oh and Iyengar (40) introduced polynomial-time
algorithms that attain regrets of (dvTT/)) and Odd /T/kk) respectively, where 1/x ((K)
is a problem-dependent constant. Recently, Perivier and Goyal 44 improved the dependency on
R in the adversarial context setting, achieving a regret of ((dK)TT)) where k' = O K). However, their approach focuses solely the setting with uniform rewards, which is special case of non-uniform rewards, and currently, there is no tractable method to implement the algorithm.
As summarized in Table I there has been gap between the upper and lower bounds in the existing works of contextual MNL bandits. No previous studies have confirmed whether lower or upper bounds tight, obscuring what the optimal regret should be. This ambiguity is further exacerbated because many studies introduce their methods under varying conditions such as different reward structures and values of to. without explicitly explaining how these factors impact regret. Additionally, there is currently no computationally efficient algorithm whose regret does not scale with 1/k = O(3) or directly with K. Intuitively, increasing K provides more information least in the uniform reward setting, potentially leading to a more statistically efficient learning process. However, no previous results have reflected such intuition. Hence, the following research questions arise:
What is the optimal regret lower bound contextual MNL. bandits?
Can we design a computationally efficient, nearly minimax optimal algorithm under the adversarial context setting?
In this paper, we affirmatively answer the questions by first tackling the contextual MNL bandit problem separately based on the structure of rewards-unin uniform and non-uniform and the value of the outside option up. In the setting of uniform rewards, we establish the tightest regret lower bound, explicitly demonstrating the dependence of regret on vp- Specifically, we prove a regret lower bound of 22d TTK)
when = O(1), common assumption in contextual settings [6] 18 43
40 41
9
44 5
33 53
(see Appendix C. for more details), and lower bound of Q(dv T) when
(KK).
Furthermore, in the adversarial context setting, we introduce computationally efficient and provably optimal (up to logarithmic factors) algorithm, OFU-MNL+, We prove that our proposed algorithm achieves regret of ((d//T/K) when
((1) and ((dTT) when = (K). each of which matches the respective lower bounds that we establish up logarithmic factors. Furthermore, the non uon-unifomm reward setting, we provide the optimal lower bound of ((dVT) assuming Up O(1). In the same setting, our proposed algorithm also attains a matching upper bound of ((d/T) up to logarithmic factors. Our main contributions are summarized as follows:

---

Under uniform rewards, we establish a regret lower bound of 9 (V (wn + K)dyTT) (Theorem D. which the tightest known lower bound in contextual MNL bandits. We propose, for the first time, computationally efficient and provably optimal algorithm. OFU-MNL+, achieving matching upper bound of O( V + K)dyT) (Theorem 2 up to logarithmic factors, while requiring only a constant computation cost per round. The results indicate that the regret improves as the assortment size K increases, unless "n = (K).. To the best of our knowledge, this is the first study to demonstrate the dependence of regret on the attraction parameter for the outside option and to highlight the advantages of a larger assortment size which aligns with intuition. That is, this the first work to show that regret upper bound (in either contextual or non-contextual setting) decreases as K increases. Additionally, we provide mistance-dependent minimax regret bounds (Proposition I and 2. up to logarithmic factors.
Under non-uniform rewards, with setting Up 18
( following the convention in contextual
MNL bandits 66
43
8 40
44 5 53 331, we establish a regret lower bound of
M(dy TT) (Theorem 3 To the best of our knowledge, this is the first and tightest lower bound established under non-uniform rewards. Moreover. OFU-MNL+ also achieves matching
upper bound (up logarithmic factors) of (ddTT) (Theorem 4) in this setting.
We also conduct numerical experiments and show that our algorithm consistently outper- forms the existing MNL bandit algorithms while maintaining a constant computation cost per round. Furthermore, the empirical results corroborate our theoretical findings regarding the dependence of regret on the reward structure, Un and K.
Overall, our paper addresses the long-standing open problem of closing the gap between upper and lower bounds for contextual MNL bandits. Our proposed algorithm is the first to achieve both provably optimality (up to logarithmic factors) and practicality with improved computation.
2 Related Work
Lower bounds of MNL bandits. In contextual MNL bandits, to the best of our knowledge, only Chen
al. [16] proved lower bound of (2(dv / K) with the attraction parameter for the outside option set
at on = 1. However, in the non-contextual setting, there exist improved lower bounds in terms of K.
X demonstrated a lower bound of Q NT/K),, and Chen and Wang [15) established a lower bound of R(vNT). By setting d N, one can derive equivalent lower bounds for the contextual setting, specifically 2(V dT dT/K) and O /dT) respectively. However, Agrawal et al. [8] and Chen and Wang [5] assumed Vy = K when establishing their lower bounds, which differs from the setting used by Chen et al. [16), where Up = 1. Moreover, the best of our knowledge, all existing works Chen et al. [16). Agrawal et al. [8) Chen and Wang [15] have established the lower bounds under uniform rewards. Consequently, it remains unclear what the optimal regret is, depending on the value of un and the reward structure.
Agrawal et al.
Upper bounds of contextual MNL bandits. Ou et al. 4 formulated a linear utility model and achieved (dd /T) regret; however, they assumed that utilities are fixed over time. Chen et al. [16] considered contextual MNL bandits with changing and stochastic contexts, establishing a regret of Ö(dyT + d2 K2). However, they encountered computational issues due to the need to enumerate all possible (N choose K) assortments. To address this, Oh and lyengar 41 proposed a polynomial-time assortment optimization algorithm, which maintains the confidence bounds in the parameter space and then calculates the upper confidence bounds of attraction parameter for each item, achieving regret of Ödd'T kt), where 1/K- O(K2) is a problem-dependent constant. Perivier and Goyal 44] considered the adversarial context and uniform reward setting and improved the dependency on k to (ddKVR'T + d2 / where = (L/ However, their algorithm is intractable. Agrawal et al. 3 considered a uniform rewards setting (with up = 1) and achieved a regret of Ö(dVT). However, due significant technical errors in their paper (refer Appendix L). we do not include comparison with their results in this work.
53 utilized an online parameter update to construct a constant time algorithm. However, they consider a multiple-parument choice model in which the learner estimates K parameters and shares the contextual information 2; across the items in the assortment. This model
Recently, Zhang and Sugiyama
3

---

differs from ours; we use a single- parameter choice model with varying the context for each item in the assortment. Additionally, they make a stronger assumption regarding the reward than we do (see Assumption Tb. Moreover, while they fix the assortment size at K, we allow it to be smaller than or equal to K. On the other hand, Zhang and Luo [22 considered a general function approximation, achieving a regret bound of (V[K26V/dNT
However, this bound scales with K and N, and the proposed algorithm is not tractable. To the best of our knowledge, all existing methods fail to show that the regret upper bound can improve as the assortment size K increases.
Problem Setting
For real-valued matrix A, we denote ||Al|2 == suPr:|=|2-1 |rlll as the maximum singular value of A. For two symmetric matrices, V and W of the same dimensions, V 2 W means that V W is positive semi-definite. Finally, we define S to be the set of candidate assortment with size constraint at most K, i.e., S= {S = [N] |S] & K). While, for simplicity, we consider both S and the set of items [MV to be stationary in this paper, is important to note that both S and [N] can vary over time.
Notations. For positive integer, n, we denote [m] ==
Contextual MNL bandits. We consider a sequential assortment selection problem which is defined as follows. At each round f. the agent observes feature vectors Iı; R for every item i E [N]. Based on this contextual information, the agent presents an assortment St = (i...... 4 E S, where & K, and then observes the user purchase decision C é St o {0), where (0) represents the "outside option" which indicates that the user did not select any of the items in S.. The distribution of these selections follows multinomial logistic (MNI)) choice model (37,, where the probability of choosing any item ig E St (or the outside option) is defined as:
exp(#11, w") Ps (e w*) :- vo 2 JeS, exp(x],w")' (O]S,, w") : UD
UO
JES, exp(xI,w) w
where Up is a known attraction parameter for the outside option and w E Rd is an unknown parameter.
Remark 1. In the existing literature on MNL bandits, is commonly assumed that uo 140 +1 44 5 53/. On the other hand, Chen and Wang [T5]. Agrawal et al. (8) assume that uh = K to
induce a tighter lower bound in terms of K. Later, we will explore how these differing assumptions create fundamentally different problems, leading to different regret lower bounds (Subsection 5.7)
The choice response for each item i E St U {0} is defined as yr := 1(c, = i) E [0. Hence, the choice feedback variable y. == (Yro, Pti. Vti,) ) is sampled from the following multinomial (MNL) distribution: y: ~ 11 (p:(0) w w".....; (r S,, w w"))], where the parameter I indicates that Yt is a single-trial sample, i.c., Bio + - Mtis = 1. For each i E S₁ U {0). we define the noise Eri := Yta Pi(i]S w*). Since each ezi bounded random variable in [0, 1J. en is 1/ 1/4-sub- Gaussian. At every round f, the reward res for each item i is also given. Then, we define the expected revenue of the assortment
Eies exp(x w "ro Uo to D jes exp(x.], w*)
= E w )ra XES
and define St as the offline optimal assortment at time t when w' is known a prior, i.c., S argmaxses RS, w*). Our objective is to minimize the cumulative regret over the T periods:
T
Reg, (w") = Σ Ri(S w') - RS
When K- = 1, F11 1. and 0o 1, the MNL bandit recovers the binary logistic bandit with R.(S = {z), w") o w*) = 1/(1 + exp( w*)) )), where a(-) is the sigmoid function.
Consistent with previous works MNL. bandits 41
53 make the following assumptions:
Assumption 1 (Bounded assumption). We assume that | l|2 < 1, and for all t > 1, i E [N], ||r.s] | & and ru E [0, 1].
'Chen and Wang 15 indeed set = 1 and Un...., ex = O(1KK). However. this is equivalent to the setting with vo- K and .., UN e()).

---

Assumption 2 (Problem-dependent constant). There exist K. > O such that for every item i S and any S E S. and all round t, min Pt [0) w) > K, where W {w F |w/l2 < 1).
In Assumption we assume that the reward for each item is bounded by constant, allowing the norm of the reward vector to depend on K, e.g.. ||:ll2 & VK. In contrast, Zhang and Sugiyama [53] assume that the norm of the reward vector P: [re.. ................................ "'...... Fajs, || IR Sil is bounded by constant, independent of K, c.g., | E 1. Thus, assumption regarding rewards is weaker than theirs.
Assumption 2 is common in contextual MNL bandits [16 41 44 [3]. Note that 1/xx depends on the maximum size of the assortment K, i.e., 1/K = O(K²). One of the primary goals of this paper is to show that as the assortment size K increases, we can achieve an improved (or at least not worsened) regret bound. To this end, we design dynamic assortment policy that enjoys improved dependence on n. Note that our algorithm does not need know a priori, whereas Oh and Iyengar 40 do.
4 Existing Gap between Upper and Lower Bounds in MNL Bandits
The primary objective of this paper is to establish minimax regrets in contextual MNL bandits. To explore the optimality of regret, we analyze how it depends the attraction parameter for the outside option uo. the maximum assortment size K, and the structure of rewards.
Dependence on Up. Currently, the established lower bounds are ((dvT/K) by Chen et al. [[6],
0(vdT K) by the contextual version of Agrawal et al. 88. and ((vTT). which is the tightest in terms of K, by the contextual version of Chen and Wang [15] These results can be misleading, as many subsequent studies 41
17 52 have claimed that a K-independent regret is achievable, without clearly addressing the influence of the value of to- In fact, the improved regret bounds (in terms of K) obtained by Agrawal et al. [8) and Chen and Wang [5) were possible when to = K. However, in the contextual setting, it is more common to set uo (1). This is because, given the context for the outside option Zan. it is straightforward to construct an equivalent choice model where 20 @(1) (refer Appendix C.1 In this paper, we rigorously show the regret dependency on the value of Up. In Theorem
39
L we establish regret lower bound of Q (Vrg + K)dy'T), which implies that the value of up. indeed, affects the regret. Then, in Theorem [ we show that our proposed computationally efficient algorithm, OFU-MNL+ achieves a regret of O (VroK/(uu + K)dvT). which is minimax optimal up to logarithmic factors terms of all d, T, K and even Vp.
Dependence on K & Uniform/Non-unifora rewards. To the best of our knowledge, the regret bound in all existing works in contextual MNL bandits does not decrease the assortment size K' increases more information because we receive more feedback. Therefore, it makes sense that regret could be reduced as K increases, at least in the uniform reward setting. Under uniform rewards, the expected revenue (to be specified later) increases as more items are added in the assortment. Consequently, both the optimistically chosen assortment and the optimal assortment always have a size of K. Thus, the agent obtain information about exactly K items in each round. This phenomenon is also demonstrated empirically in Figure [ In the uniform reward setting, as K increases, the cumulative regrets of not only our proposed algorithm but also other baseline algorithms decrease. This indicates that the existing regret bounds are not tight enough in terms of K. Conversely, in the non-uniform reward setting, the sizes of both the optimistically chosen assortment and the optimal assortment can be less than K, so performance improvement is not guaranteed. In this paper, we show that the regret dependence on K varies by case: uniform and non-uniform rewards. When Up = O(1), we obtain a regret lower bound of Q(dvT/R (Theorem 1) and a regret upper bound of ((dVT/K) (Theorem 2 under uniform rewards. Additionally, we achieve regret lower bound of (Theorem) and regret upper bound of (dv/T) (Theorem 4 under non-uniform rewards.
16 40 41
However, intuitively, as the assortment size increases, we can gain
Algorithms and Main Results
In this section, we begin by proving the tightest regret lower bound under uniform rewards (Subsec- tion 5.1). explicitly showing the dependence on the attraction parameter for the outside option up. We then introduce OFU-MNL+, an algorithm that achieves minimax optimality, up to logarithmic factors, under uniform rewards (Subsection 5.2 Notably, OFU-MNL+ is designed for efficiency, requiring
5

---

only constant computation and storage costs. Finally, we establish the tightest regret lower bound and a matching minimax optimal regret upper bound under non non-untooonn uniform rewards (Subsection 5.3
5.1 Regret Lower Bound under Uniform Rewards
In this subsection, we present a lower bound for the worst-case expected regret in the uniform reward setting (F's = 1). This covers all applications where the objective is maximize the appropriate "click-through rate" by offering the assortment.
Theorem 1 (Regret lower bound, Uniform rewards). Let d be divisible by 4 and let Assumption 7 hold true. Suppose T z C. du + / K for some constant C. > O. Then, in the uniform reward setting, for any policy n, there exists worst-cuse problem instance with N = O(K 24) items such that the worst-case expected regret of is lower bounded us follows:
VoOK 00 K
sup Bw Regr [w]]=]] =
dvT
Discussion of Theorem If un (1), Theorem 1 demonstrates regret lower bound of Q(dvT/K). This indicates that, under uniform rewards, increasing the assortment size K leads an improvement in regret. Compared to the lower bound ((v/T/K) proposed by Chen et al. [16], our lower bound is improved by a factor K. This improvement is mainly due to the establishment of tighter upper bound for the KL divergence (Lemma Notably, Chen et al. [16] also considered uniform rewards with Vp = (1). On the other hand, Chen and Wang [15] and Agrawal et al. g established regret lower bounds of Q(vNT) and Ω ((vNT /NT/ K), respectively, in non-contextual MNL bandits with uniform rewards, by setting Up K achieve these regrets. Theorem [ shows that if Uo ())),
obtain a regret lower bound of (idv'T), which consistent with the K K-independent regret in Chen and Wang [5]. To the best of our knowledge, this result is the first to explicitly show the dependency of regret the attraction parameter for the outside option Ug- The proof is deferred to Appendix
5.2 Minimax Optimal Regret Upper Bound under Uniform Rewards
In this subsection, we propose new algorithm OFU-MNL+, which enjoys minimax optimal regret up to logarithmic factors the case of uniform rewards. Note that, since the revenue is an increasing function when rewards are uniform, maximizing the expected revenue R, w) over all S e S always yields exactly K items, i..., |S|] = |S:|| = K.
Our first step involves constructing the confidence set for the online parameter.
Online parameter estimation. Instead of performing MLE in previous works 16 41 44
inspired
by Zhang and Sugiyama [53], we use the online mirror descent algorithm to estimate parameter. We first define the multinomial logistic loss function at round t as:
& (w) = Σ IE
Yta log (i]S, w).
(2)
In Proposition C.I we will show that the loss function has the constant parameter self-concordaant-lke property. We estimate the true parameter w as follows:
W argmin Vl( w
2n |w well?, Vt > 1,
(3)
weW
where 7) 0 is the step-size parameter to be specified later, and H, = H. + (wee), where
G((w) = Σ St, w) I
Σ Σ PilS, w)p,GiSS, w)
Se
iES, jeS,
and H, :- AI Σ G.(w...) Note that Gr(w) (w). This online estimator is efficient terms of both computation and storage. By a standard online mirror descent formulation 42 optimization problem in ( can be solved using single projected gradient step through the following equivalent formula:
w/ 2+1 w, -,, VV, and W = argmin ||w w
(4)
weW

---

Algorithm 1 OFU-MNL+
1: Inputs: regularization parameter X, probability 6, confidence radius Br(5), step size n).
2: Initialize: H1 A and W1 as any point in W.
3: for round / 1,2, - do
4: Compute Ot F& We + (6) म, for all [N].
5: Offer S. argmax Se5 (S) and observe yt-
6: Update H. = H4 + 1/9 (w.), (w,), and update the estimator W1+1 by (3)
7: Update He+1 = H₂ + (W1+1).
8:
end for
which enjoys computational cost of only O(Kd), completely independent of [38] [3]. Regarding storage costs, the estimator does not need to store all historical data because both H, and H, can be updated incrementally, requiring only (de) storage.
Furthermore, the estimator allows for a k-independent confidence set, leading to an improved regret.
Lemma 1 (Online parameter confidence set). Let ô (0, 1]. Under Assumption 7 with 7 log(K' (K' 1) + 2 and X 84v 34v/2n, define the following confidence set
C,(ō) (WEW l|w, w|n, & Be())),
where Be(8) O (Vologg i log K)g... Then, we have Pr[ve 1, w C,(8)] > 6.
Armed with the online estimator, construct the computationally efficient optimistic revenue.
Computationally efficient optimistic expected revenue. To balance the exploration and exploitation trade-off, we use the upper confidence bounds (UCB) technique, which have been widely studied in many bandit problems, including K-arm bandits [1] 32) and linear bandits [ 20).
At each time f, given the confidence set in Lemma] 1 we first calculate the optimistic utility ou as:
ag = -4 We + [(00)l= Vi [M].
(5)
The optimistic utility Oee is composed of two parts: the mean utility estimate xi. w, and the standard deviation [aa) H.- In the proof of the regret upper bound, we show that serves as an upper
bound for o w" assuming that the true parameter w falls within the confidence set (o). Based on Ott, we construct the optimistic expected revenue for the assortment S, defined follows:
Eie exp((xii an)) 1o Ejes exp(oej)
R.((S)
(6)
where Tu 1. Then, offer the S, that maximizes the optimistic expected revenue, S, argmax SEs RS).). Given our assumption that all rewards are of unit value, the optimization problem is equivalent to selecting the items with the highest optimistic utility Orgs. Consequently, solving the optimization problem incurs a constant computational cost of O(N).
Remark 2 (Comparison to Zhang and Sugiyama (53)). In Zhang and Sugiyama (53), 3, the MNL choice model is outlined with a shared context xt and distinct parameters wi..... w for each choice. Conversely, our model employs single parameter w* across all choices and has varying contexts for each item in the assortment S, T.1.... Tti Due to this discrepancy in the choice model, directly applying Proposition I from Zhang and Sugiyama (53), which constructs the optimistic revenue by adding bonus terms to the estimated revenue, incurs an exponential computational cost in our problem setting. This complexity arises because the optimistic revenue must be calculated for every possible assoriment S E S; therefore, it is necessary to enumerate all potential assortments (N choose K) identify the one that maximizes the optimistic revenue As a result, extending the approach in Zhang and Sugiyama (53) to our setting is non-trivial, requiring a different analysis.
We now present the regret upper bound of OFU-MNL+ in the uniform reward setting.
Theorem 2 (Regret upper bound of OFU-MNL+, Uniform rewards). Let 8 E (0, 1] and Assumptions 7
and 2 hold. In the uniform reward setting, by setting n log(K' + 1) + 2 and À = 84v 84v2dm with
7

---

probability at least 1 - 8, the cumulative regret of OFU-MNL+ is lupper-buuddrr by
V Vork Up + K
Regr(w") = =Ö
dvT+ dc
K
Discussion of Theorem 2. I 3 O + /)2//(2200 0g K)), Theorem shows that our al- gorithm OFU-MNL+ achieves minimax optimal regret (up to logarithmic factor) in terms of all d. T. K, and even vo- To the best of our knowledge, ignoring logarithmic factors, our proposed algorithm is the first computationally efficient, minimax optimal algorithm in (adversarial) con- textual MNL bandits. When vo = (1), which is the convention in existing MNL bandit litera- ture [40
44 53). OFU-MNL+ obtains (dd / regret. This represents an improvement over which is Ö(dK Vn'T + d dKK*/K) /K), where n' = (L) by a factor of K. This improvement can be attributed to two key factors: an improved. constant, self-concordant -irkk property of the loss function (Proposition C.T and a K--free elliptical potential lemma (Lemma F.2). Furthermore, by employing an improved bound for the second derivative of the revenue (Lemma E.3), we achieve an enhancement in the regret for the second term, d² /2KK, by a factor of K in comparison to Perivier and Goyal 44. Unless vo (K). Theorem 2 indicates that the regret decreases as the assortment size K increases. To the best of our knowledge, this is the first algorithm in MNL bandits to show that increasing K results in a reduction regret. Moreover, when reduced to the logistic bandit, i.e., K = TMi 1, and Up 1, our algorithm can also achieve a regret of ('d kT) by Corollary in Zhang and Sugiyama [53] which is consistent with the results in Abeille et al. [4]. Faury et al. [23]. The proof is deferred to Appendix E
the previous upper bound of Perivier and Goyal
Remark (Efficiency of OFU-MNL+). The proposed algorithm is computationally efficient in both parameter updates and assorfment selections. Since we employ online parameter estimation, akin to Zhang and Sugiyama (53], our algorithm demonstrates computational efficiency parameter estimation, incurring only incurring (KKd)) computation cost and O ((d²) storage cost, which are completely independent of Furthermore, naive approach to selecting the optimistic assortment requires enumerating all possible (N choose K) assortments, resulting in exponential computational cost [o]. However, by constructing the optimistic expected revenue according to (6) (inspired by Oh and Iyengar [41]), our algorithm needs only (NN) computational cost.
5.3 Regret Upper& & Lower Bounds under Non-Uniform Rewards
In this subsection, propose regret upper and lower bounds in the non-uniform reward setting. In this scenario, the sizes of both the chosen assortment S,, and the optimal assortment, S are not fixed K. Therefore, we cannot guarantee an improvement in regret even as K increases.
We first prove the regret lower bound in the non-uniform reward setting.
Theorem 3 (Regret lower bound, Non-uniform rewards). Under the same conditions as Theorem let the rewards be non-uniform and to @(1). Then, for any policy there exists worst-case problem instance such that the worst-case expected regret of a is lower bounded as follows:
sup E [Regr = - (dvT).
w
Discussion of Theorem 3] In contrast to Theorem D which considers uniform rewards, the regret lower bound is independent of the assortment size K. Note that Theorem 3 does not claim that non-uniform rewards inherently make the problem more difficult. Rather, it implies that there exists an instance with adversarial non non-uniform rewards, where regret does not improve even with an increase in K. Moreover, the assumption that vo ((1) is common in the existing literature on 5 53 (refer Appendix C.Tb. To the best of our knowledge, this is the first established lower bound for non-uniform rewards in MNL bandits, even in the non-contextual
contextual MNL bandits 40 41 44
setting. The proof is deferred to Appendix G
We also prove matching upper bound up to logarithmic factors. The algorithm OFU-MNL+ is also applicable in the case of non-uniform rewards. However, because the optimistic expected revenue Rs(S) no longer an increasing function ats, optimizing for S, = argmaxses R&(S) no longer equates to simply selecting the top K items with the highest optimistic utility, Instead, we employ
2 Perivier and Goyal
44 also consider the uniform rewards (ru 1) with vg 1.
8

---

assortment optimization methods introduced in Rusmevichientong et al. 477 Davis et al. [21, which are efficient polynomial-timg (independent of a allgorithms available for solving this optimization problem. Therefore, our algorithm is also computationally efficient under non-uniform rewards.
Theorem 4 (Regret upper bound of OFU OFU-MNL+, non-uniform rewards). Under the same assumptions and parameter settings as Theorem if the rewards are non-unin non-uniform and vo ( then with probability at least - 8, the cumulative regret of OFU-MNL+ is upper-bounded by
Reg, (egy(w") 0 dv
-0(d 1+++1d d
Discussion of Theorem IT > O(d/n²2,, our algorithm achieves regret of Ödd when the reward for each item is non-uniform, demonstrating that OFU-MNL+ is minimax optimal up to logarithmic factor. Recall that we relax the bounded assumption on the reward compared to Zhang and Sugiyama [53] (refer Assumption[[P []]: thus, we allow the sum of the squared rewards in the assortment to scale with K. Consequently, we need novel approach to achieve the regret that does not scale
with K. To this end, we centralize the features, i.e., Izz Zzi Ey (...p.--S....... [Ttz] and propose a novel elliptical potential lemma for them, as detailed in Lemma H.3] Note that our algorithm capable of achieving 1/ freereee regret (in the leading term) under both uniform and non-uniform rewards. In contrast, the algorithm in Perivier and Goyal [44] is limited to achieving this only in the uniform reward setting. Furthermore, compared to the regret bound in Chen et al. [16], which is OdV'T), our regret bounds has the same order of regret with theirs. However, their algorithm is computationally intractable as it requires enumerating all possible assortments, whereas our algorithm incurs only constant computational cost per round. The proof is deferred to Appendix H
6 Instance-Dependent Bounds
In this section, we show that instance-dependen upper and lower bounds are also achievable under uniform rewards. We define the degree of non-linearity for the optimal assortment St round t under the true parameter w' KG == S;s; Pr(i w (0)Stt w*). We first establish the instance-dependen lower bound under uniform rewards.
Proposition 1 Mustance-dependerr regret lower bound, Uniform rewards). Under the same conditions as Theorem for any policy स and for T è dir, there exists worst-case problem instance such that the worst-case expected regret of is lower bounded follows:
T
sup E [Reg, = dd
Σ
The proof is deferred to Appendix ! We also provide the matching upper bound.
Proposition 2 (nstance-deppndenn regret upper bound of OFU-MNL+, Uniform rewards). Under the same assumptions, parameter settings, and reward structure as Theorem 2 with a probability at least 1- 8, the cumulative regret of OFU-MNL+ is upper-boune by
T
Reg (w") Ö
d
8
The proof is deferred Appendix For sufficiently large T, the regret upper bound (Proposition 2 matches the regret lower bound (Proposition []. up to logarithmic factor. To the best of our knowledge, these are the first minimax distance-eepeden regret bounds under uniform rewards. Note that, in the worst case, Ky Ö(vooK/( K/v(n + K)), which indicates that these results provide striet improvement over the worst-case bounds given in Theorems and
Some readers may expect instance-dependent regret bounds for non-uniform rewards as well. Unfor- tunatcly, we were unable to establish these. Recall that og represents the degree of non-linearity for
An interior point method would generally solve the problem with computational complexity of ((N3.5).

---

N=110, K-5. de5, Uniform
K--0,, Unfomm
N=100: Uniform
N=100; Unfoom
13
2500
57
300
150
No-Unntom
16.000
16..03 51
Figure 1: Cumulative regret (left three, = 5, 10, 15) and runtime per round (rightmost one, K 15) under uniform rewards (first row) and non-uniform rewards (sccond row) with vop 1.
the optimal assortment ST. However, in the proofs for regret bounds, we encounter terms associated with the chosen assortment S,, such as Lies; Pe (i] St, w w")p;(() (O w*). To address this, we use the mean value theorem-based analysis (Lemma(L.5) to replace this quantity with xiç. Under non-uniform rewards, however, the mean value theorem does not apply because the sizes and rewards of S and S, may differ. Addressing this problem would be an interesting direction for future research.
Numerical Experiments
In this section, empirically evaluate the performance of algorithm OFU-MNL+, We measure cumulative regret over 7 3000 rounds. For each experimental setup, we run the algorithms across 20 independent instances and report the average performance. In each instance, the underlying parameter w is randomly sampled from a dddimensional uniform distribution, where each element of w' lies within the range [-1/v /d, 1/vd] and is not known to the algorithms. Additionally, the context features Tui drawn from d-dimensional multivariate Gaussian distribution, with each element of Ies clipped to the range [- 1/V2, 1/vdj. This setup ensures compliance with Assumption | In the uniform reward setting (first row of Figure []. the combinatorial optimization step to choose the assortment reduces to sorting items by their utility estimate. In the non-uniform reward setting (second row of Figure T. the rewards are sampled from uniform distribution each round, i.c.. Pes ~ (0, 1). Refer Appendix K for more details.
We compare the performance of OFU-MNL+ with those of the practical and state-of-the-art algorithms: the Upper Confidence Bound-base based algorithm, UCB-MNL [40], and the Thompson Sampling based algorithm, TS-MNL [40]. Figure demonstrates that our algorithm significantly outperforms other baseline algorithms. In the uniform reward setting, as K increases, the cumulative regrets of all algorithms tend decrease. In contrast, this trend is not observed in the non-uniform reward setting. Furthermore, the results also show that our algorithm maintains a constant computation cost per round, while the other algorithms exhibit linear dependence on In Appendix K additional runtime curves (Figure K.T as well as the regret curves of the other configuration where Vo θ(K) (Figure K.2
we present the
All of these empirical results align with our theoretical results.
8 Conclusion
In this paper, propose minimax optimal lower and upper bounds for both uniform and non-uniform reward settings. We propose a computationally efficient algorithm, OFU-MNL+, that achieves regret of (dvTT/K) under uniform rewards and (dvTT) under non-uniform rewards. We also prove matching lower bounds of ((dvT/K) and ((dyT) for each setting, respectively. Moreover, our empirical results support our theoretical findings, demonstrating that OFU-MNL+ is not only provably but also experimentally efficient.
10

---

Acknowledgements
This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea governmen((MSTT) (No. (022RICIC10666 2022R 1 IAAAA1330579 and RS-2023-002226633 and by AI-Bio Research Grant through Seoul National University.
References
[1] Yasin Abbasi- Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 11-2312-232) 2011.
[2] Naoki Abe and Philip M Long. Associative reinforcement learning using linear probabilistic concepts. In ICML, pages 3-11 11. Citeseer, 1999.
[3] Marc Abeille and Alessandro Lazaric. Linear Thompson Sampling Revisited. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 176-184, PMLR, 20 22 Apr 2017.
[4] Marc Abeille, Louis Faury, and Clément Calauzènes. Instance-wis wise minimax -opiima algorithms for logistic bandits. In International Conference Artificial Intelligence and Statistics, pages 3691-3699. PMLR, 2021.
[5] Priyank Agrawal, Theja Tulabandhula, and Vashist Avadhanula. A tractable online learning algorithm for the multinomial logit contextual bandit. European Journal of Operational Research, 310(():737-755) 2023.
[6] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pages 127-135. PMLR, 2013.
[7] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the bandit In Conference on learning theory, pages 76-78. PMLR, 2017.
[8] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Mnl-bandit: A dynamic learning approach to assortment selection. Operations Research, 6755):14533 2019.
[9] Sanae Amani and Christos Thrampoulidis. Ueb-based algorithms for multinomial logistic regression bandits. Advances in Neural Information Processing Systems, 34:2913-2924, 2021.
[10] Peter Auer. Using confidence bounds for exploitation-exxplraaio trade-offs. of Machine Learning Research, 3(Nov):397 422, 2002.
[11] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-255 2002.
[12] Nicolo Campolongo and Francesco Orabona. Temporal variability in implicit online learning. Advances in neural information processing systems, 33:12377-12388 2020.
[13] Junyu Cao and Wei Sun. Tiered assortment: Optimization and online learning. Management Science, 70(8):5481-55
2024.
[14] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. International conference on machine learning, pages 159- PMLR, 2013.
[15] Xi Chen and Yining Wang. A note on tight lower bound for capacitated mul-bandit assortment selection models. Operations Research Letters, 46(5):534-537, 2018.
[16] Xi Chen, Yining Wang, and Yuan Zhou Dynamic assortment optimization with changing contextual information. The Journal of Machine Learning Research, 21(1):89188896 2020.
[17] Xi Chen, Yining Wang, and Yuan Zhou. Optimal policy for dynamic assortment planning under multinomial logit models. Mathematics of Operations Research, 46(4):1639-1657, 2021.
11

---

[18] Wang Chi Cheung and David Simchi-Leve Thompson sampling for online personalized assortment optimization problems with multinomial logit choice models, Available at SSRN 3075658, 2017.
[19] Hyun-jun Choi, Rajan Udwani, and Min-hwan Oh. Cascading contextual assortment bandits. Advances in Neural Information Processing Systems, 36, 2024.
[20] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208-214, JMLR Workshop and Conference Proceedings, 2011.
[21] James M Davis, Guillermo Gallego, and Huseyin Topaloglu. Assortment optimization under variants of the nested logit model. Operations Research, 62(2):250-273, 2014.
[22] Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference Machine Learning, pages 3052-3060. PMLR, 2020.
[23] Louis Faury, Marc Abeille, Swaan-SSng 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.
[24] Sarah Filippi, Olivier Cappé, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Proceedings of the 23rd International Conference on Neural Information Processing Systems- Volume 1, NIPS' 10, page 586-594, Red Hook, NY, USA, 2010. Curran Associates Inc.
[25] Dylan J Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan. Logistic regression: The importance of being improper. In Conference on learning theory, pages 167-208. PMLR, 2018.
[26] Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325, 2016.
[27] Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scalable gen- eralized linear bandits: Online computation and hashing. Advances in Neural Information Processing Systems, 30, 2017.
[28] Abbas Kazerouni and Lawrence M Wein. Best arm identification in generalized linear bandits. Operations Research Letters, 49(3)366--371, 2021.
[29] Wonyoung Kim, Kyungbok Lee, and Myunghee Cho Paik. Double doubly robust thompson sampling for generalized linear contextual bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 200,3377,20233
[30] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight regret bounds for stochastic combinatorial semi-bandits. In Artificial Intelligence and Statistics, pages 535-543.
PMLR, 2015.
[31] Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 2066-2076. PMLR, 2020.
[32] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[33] Junghyun Lee, Se- Youn Yun, and Kwang-Sung Jun. Improved regret bounds of (multinomial) logistic bandits via regret-to- sennettto-coffienceeeseee conversion. In International Conference on Artificial Intelligence and Statistics, pages 4474 4482. PMLR, 2024.
[34] Junghyun Lee, Se- Young Yun, and Kwang-Sung Jun. A unified confidence sequence for generalized linear models, with applications to bandits. arXiv preprint arXiv:2407.13977 2024.
[35] 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.
12

---

[36] Xutong Liu, Jinhang Zuo, Siwei Wang, John CS Lui, Mohammad Hajiesmaili, Adam Wierman, and Wei Chen. Contextual combinatorial bandits with probabilistically triggered arms. In International Conference on Machine Learning, pages
PMLR, 2023.
[37] Daniel McFadden. Modelling the choice of residential location. 1977.
[38] Zakaria Mhammedi, Wouter M Koolen, and Tim Van Erven. Lipschitz adaptivity with multiple learning rates in online learning. In Conference on Learning Theory, pages 2490-2511. PMLR, 2019.
[39] Sentao Miao and Xiuli Chao. Dynamic joint assortment and pricing optimization with demand learning. Manafacturing & Service Operations Management, 23(2):225-545, 2021.
[40] Min-hwan Oh and Garud Iyengar. Thompson sampling for multinomial logit contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
[41] Min-hwan Oh and Garud Iyengar. Multinomial logit contextual bandits: Provable optimality and practicality. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 2205-9213, 2021.
[42] Francesco Orabona. modern introduction to online learning. arXiv preprint arXiv: 1rXiv:1912.13221 2019.
[43] Mingdong Ou, Nan Li, Shenghuo Zhu, and Rong Jin. Multinomial logit bandit with linear utility functions. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pages 2602-2608. International Joint Conferences on Artificial Intelligence Organization, 2018
[44] Noemie Perivier and Vineet Goyal. Dynamic pricing and assortment under a contextual mnl demand. Advances in Neural Information Processing Systems, 155:341134777 2022.
[45] Lijing Qin, Shouyuan Chen, and Xiaoyan Zhu. Contextual combinatorial bandit and its appli- cation on diversified online recommendation. In Proceedings of the 2014 SIAM International Conference on Data Mining, pages 461 -69. SIAM, 2014.
[46] Idan Rejwan and Yishay Mansour. Top-k combinatorial bandits with full-bandit feedback. In Aryeh Kontorovich and Gergely Neu, editors, Proceedings of the 31st International Conference on Algorithuicc Learning Theory, volume 117 of Proceedings of Machine Learning Research, pages 752-776. PMLR, 08 Feb-11 11 Feb 2020.
[47] Paat Rusmevichientong, Zuo-Jun Max Shen, and David B Shmoys. Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Operations research, 1866):166611680 2010.
[48] Denis Sauré and Assaf Zeevi. Optimal dynamic assortment planning with demand learning. Manufacturing & Service Operations Management, 15(3):387-404, 2013.
[49] Quoc Tran-Dinh, Yen-Huan Li, and Volkan Cevher. Composite convex minimization involving self-comcordant-like cost functions. In Modelling, Computation and Optimization in Information Systems and Management Sciences: Proceedings of the 3rd International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences- MCO 2015-Part I, pages 155-168. Springer, 2015.
[50] Alexandre B Tsybakov. Introduction to Nonparametric Estimation. Springer Science & Business Media, 2008 doi: https://doi.org// 10. 1007/b
[51] Lijun Zhang, Tianbao Yang, Rong Jin, Yichi Xiao, and Zhi-Hua Zhou. Online stochastic linear optimization under one- bit feedback. In International Conference on Machine Learning, pages 392-401. PMLR, 2016.
[52] Mengxiao Zhang and Haipeng Luo. Contextual multinomial logit bandits with general value functions, arXiv preprint arXiv:2402.08726 2024.
[53] Yu-Jie Zhang and Masashi Sugiyama. Online (multinomial) logistic bandit: Improved regret and constant computation cost. Advances in Neural Information Processing Systems, 36, 2024.
13

---

[54] Shi Zong. Hao Ni, Kenny Sung, Nan Rosemary Ke, Zheng Wen, and Branislav Kveton. Cas- cading bandits for large-scale recommendation problems. In Proceedings of the Therty-Second Conference on Uncertainty in Artificial Intelligence, page 835-844. AUAI Press, 2016.
14

---

Appendix
Table of Contents
Further Related Work
B Notation
17
Propertics of MNL function
17
C.I
Attraction parameter for Outside Option: to ( is Common in Contextual
MNL. Bandits
Sell-concordant-lite Function
18
D Proof Theorem |
D.I Adversarial Construction and Bayes Risk
19
D
2 Main Proof of Theorem
20
Proofs Lemmas for Theorem
22
E Proof of Theorem 2
24
Proof Theorem
E.2 Proofs of Lemmas for Theorem
30
F Proof of L
32
F Main Proof of Lemmall
32
Proofs of Lemmas for Lemmal
34
Technical Lemmas for Lemmal
39
Proofs Theorem
41
Adversaria Rewards Construction
41
2 Main Proof of Theorem
41
G.3 Proofs Lemmas for Theorem
42
H Proofs of Theorem 4
43
Proof Theorem
2 Proofs of Lemmas for hhorem
48
Proof Proposition
I.1
Main Proof of Proposition
50
1.2
Proofs Lemmas for Proposition
52
1.3 Technical Lemmas for Proposition
53
Proof Proposition 2
53
K
Experiment Details and Additional Results
56
Technical Errors in Agrawal et al. 5
57
Limitations
57
15

---

A Further Related Work
In this section, we discuss additional related works that complement Section 2 For simplicity, we consider only the dependence on the number of rounds for a computation cost in big-O notation.
focuses on environments with bi- nary rewards and explores the impact of non-linearity on the exploration.explootation trade-off for parametrized bandits. The main research interest has been the algorithmss' dependence on the degree of non-linearity K, which can grow exponentially in terms of the diameter of the decision domain W. Zhang et al. [51] introduced the first efficient algorithm for binary logistic bandits with a (11 computation cost, achieving a regret of O(dvTTRK). Faury et al. [2] enhanced the regret to ((d/T/K) with O(t) computation cost. However, their regret bounds still suffered from a harmful dependence on 1/k. Abeille et al. 4 addressed this by achieving the tightest regret upper bound of Ö(dy RT) with a O(1) computation cost, while Faury et al. [23] achieved the same regret with an improved computation cost of O(log l). More recently. Zhang and Sugiyama [53] proposed a jointly efficient algorithm that achieves the optimal regret with constant ((1) computation cost. Note that
Logistie Bandits. The logistic bandit model 24
the logistic bandit is special case of the multinomial logistic (MNL) bandit. When the maximum assortment size is one (K = 1), rewards are uniform (Tr = 1), and the attraction parameter for the outside option is one v 1, the MNL bandit reduces to the logistic bandit. In this logistic bandit setting, our proposed algorithm, OFU-MNL+, can achieve a regret upper bound of O(dy kT') with constant (11) computation cost, consistent with the result in Zhang and Sugiyama [53]
Multinomial Logistic (MNL) Bandits. There are two main approaches to multinomial logistic (MNL) bandits: the multiple- parammeer choice model and the single-parameter choice model. In the multiple-parameter choice model, the learner estimates parameters for each choice in the assortment
(wi.... w with a shared context Ty. this setting, Amani and Thrampoulidis [9] proposed a feasible algorithm that achieves a regret upper bound of ((dKVKT) with a (tt) computation cost. They also proposed an intractable algorithm that achieves an improved regret of ((dK32VT)) Zhang and Sugiyama (53) introduced a computationally and statistically efficient algorithm that obtains regret of (ddKTT). Recently, Lee et al. (33 further improved the regret by factor of VK, achieving O(dv KT) regret. In the
case, the regret's dependence on K is unavoidable since the number of unknown parameters depends on K.
On the other hand, the single-parameed choice model, closely related ours, shares the parameter w cross the choices, with varying contexts for each choice. The learner offers a set of items St with |S < K at each round. This setting involves combinatorial optimization to choose the assortment S,, making it more challenging to devise a tractable algorithm. As extensively discussed in Section 2 no previous studies have definitively confirmed whether the existing lower or upper bounds are tight. As shown in Table I many studies have presented their results in inconsistent settings with varying reward structures and values of vg. adding to the ambiguity about the bounds' optimality. In this paper, we address these issues by bridging the gap between the lower and upper bounds of regret through a careful categorization of the settings. We propose an algorithm that is both provably optimal, up to logarithmic factors, and computationally efficient, significantly enhancing the theoretical and practical understanding of MNL bandits.
Generalized Linear Bandits. In generalized linear bandits 24
27 B5
34 the
expected rewards modeled using generalized linear model. These problems generalize logistic bandits by incorporating general exponential family link function instead of the logistic link function. The algorithms proposed for generalized linear bandits also exhibit dependence on the nonlinear term k. However, our problem setting (single-paramene MNL bandits) considers a more complex state space where multiple arms are pulled simultaneously.
Combinatorial Bandits. Another related stream of literature is combinatorial bandits 14
45 30
54
46 36), particularly top-k combinatorial bandits 46). In top-k combinatorial bandits, the decision set includes all subsets of size I out of n arms, and the reward for each action is the sum of the rewards of the l selected arms. In this framework, the rewards are assumed to be independent of the entire set of arms played in round t. In contrast, in our setting, the reward for each individual arm depends on the whole set of arms played.
Recently, Choi et al. 19) Cao and Sun 13 have considered the cascading assortment bandit problem, which encompasses the MNL bandit problem as special case where the cascading length
16

---

is 1. However, these works do not strictly encompass our results. Choi et al. [19] only consider uniform rewards, and achieve a regret upper bound of (dvTT), which avoids dependence on both the cascading length and k. When the cascading length our result (Theorem 2) improves upon theirs by a factor of v K. Moreover, their computation cost per round is O(t) since they employ MLE to estimate the parameter. Cao and Sun [13] consider non-une non-uniform rewards, and achieve regret upper bound of Ohh2do / where M is the cascading length and p(ilS.w)
p(I[S.w) for all w, w' W, S E S, and i E S o {0). However, their regret bound still suffers from a harmful dependence on h², which can be exponentially large.
B
Notation
We denote as the total number rounds and t E [T] as the current round. We denote as the total number of items, K as the maximum size of assortments, and the dimension of feature vectors.
For notational simplicity, we define the loss function in two different forms throughout the proof:
exp(xx! Uo + Djes, exp(xres )
(x()
Σ seS.
Yes pr w)
Σ
Yti log
ieS.
exp(z1x)
Y1)
Yes log S...
Σ
Up + LjEs, (xp((z1)
where Zzi z,,, Z, (ss)) E | and y: (Bis)ies, BlSd Thus, ((w)) f(Zz,ye)
We offer a Table for convenient reference.
Table B.1: Symbols
feature vector for item given at round / reward for item given at round t
S,
assortment chosen by algorithm at round t outside option
Yri
choice response for each item i E S. (0) round
(S, w*)
EEES (i]SS w* "rree expected revenue of the assortment round
((w))
[) EiS, Vui log Lnt,, (x w) loss function round
Lies. Uti log
exp(s(e)
loss function at round f, =u x.
Bot (xp()))))
A
regularization parameter
G((w)
= Lies, Pr(i)S,, w) w) Eies, Ejes, Pr(i)S,, w)pr(iSs, w)
He
= ALa + (.
He
= H, + (7G((w))
ai
xT., (((5 F Iull optimistic utility for item at round
(,(
o (Válogg / log K) confidence radius at round t
RR(())
Ens )ra Not Eies )
optimistic expected revenue for the assortment round
C Properties of MNL function
In this section, we present key properties of the MNL. function and its associated loss, which are used throughout the paper.
17

---

C.1 Attraction parameter for Outside Option: = (1) is Common in Contextual MNL Bandits
In this subsection, we explain why the assumption that to = ((1) is made without loss of generality, Let the original feature vectors be d/, IR: for every item i E [N] Suppose that a context for the outside option #40 is given and the probability of choosing any item i E (0) is defined as
exp((a'Aa) w*)
Pr St w*) 2) exp((<(g)) " w*)
Then, by dividing the denominator and numerator by exp ((<%)) " ww". and defining dri := z/u T20
we obtain the MNL probability in the form presented in (I) with exp(0) = 1. Note that this division does not change the probability. Therefore, vo (1) is natural and common in contextual MNL bandit literature.
C.2 Seff-concordant-like Function
Definition C.1 coaff-oooooratt-lkk like function, Tran-Dinh et al. 44). A convex e C (R M -esseff-concoraant like function with constant M if:
[s)( < M 2
for s E R and M > 0, where o(s) := f(a sb) for any a, b E R".
Then, the MNL loss defined in 2 is
like function.
Proposition C.1. For any e [T. the multinomial logistic loss fe(w), defined in (2) is 3-2-lllff
concordant-like.
Proof. Consider the function (08) :- log (Ei elistbi), where [ao...., an] R and
b [bo.... ................................ bn] T p=+1, Then, by simple calculus, we have
d"(s) Eies(a; (a: - a,) ( ee
0,
(Ein eaiotd))
and
(s))) Eiey(a; - a;))cerotbb casotb, [_knp + aj 20x 20x se
(C.1)
Ex=0 eaisthi)
Note that for all i,j,k O,....n,
la: + ag -2xl & vby + az ah < <32 max las/.
(C.2)
==0.....
Therefore, have
Σ R-0
(a: aj- 2ax)e 2ax)earotby
aa; + aj -anl - 3/2
max
Jai]
Σ
casttbe
k-0
k=0
(C.3)
Plugging in C.33 into C.1
we obtain
(s) 3 max lajl"(s)). --
(C.4)
Now, we are ready to prove the proposition. For any f E [T], let = 1S. and C Iti C2
Tti.- Define function f C3 Rd IR [(0) log Uo 5n c 0 Let
Ftig.
On Cn
8 Rd and let f(e + sō) log yo Σ e 0 o) log EE cas+tb) d(s). where
a; = c. 8. by = of for = I,..., n, and 0; = and b; log uo for = 0. Then, by C.4 we get
(s) & 3/2 max D...,,
(a) 3v2 max i-I...m
u (s)
3/2 max |0:12||0 (s) < 3/2 20 (s),
1
18

---

K, i.e., n = 1S & K. In contrast, we bound the same term by a constant, max;-l....n |as] 2. which allows property. This key difference accounts where the last inequality holds due to Assumption | that |cs]/2 |Teg ll2 < 1. Then, by Defini-
tion C.I f is -of-sell-conncordan--iii Since l is the sum of and linear operator, which has function.
third derivatives equal to zero, it follows that & is also
Remark C.1. Contrary the findings of Perivier and Goyal [44], which suggest that the MNL loss function V6K- selffconccrdant-lic like, our loss function is 3v 2-seeff-ooncorddnt improved regret bound the order of (V The improvement arises due to K K-independent self-concortant- llike property of tt, as shown in Proposition [.I] Perivier and Goyal (44), Lemma 4 from Tran-Dinh et al. [49] used, which describes /6 all2 self-concordant like property. However, in the analysis of C.2 we show that their analysis is not tight because they bound the term v Val + aj + og by | VViL dzz thus making its upper bound dependent
This yields
our loss function to exhibit a constant 3v "2-self-concortone
for the v K improvedd regret.
Lemma C.1 (Theorem of Tran- Daan-inhh et al. 49). A convex function l C3 Rd M M-self- concordant-like if and only for any v, u1 U2, Ug E Rd, we have
(DD((y)/u u & M M ////////////// wel////lllleeee /alp
D Proof of Theorem I
In this section, we provide the proof of Theorem [ The proof structure is similar to the one presented in Chen et [66. However, unlike their approach, we explicitly derive a bound that includes ro-- Furthermore, by establishing tighter upper bound for the KI. divergence (Lemma D.2), we derive bound that is tighter than the one provided by Chen al. [6
D.1 Adversarial Construction and Bayes Risk
Let 10.1/dvd) be small positive parameter to be specified later. For every subset S [d]. we define the corresponding parameter Wy Rdd as [wy]; for all j V, and [wv], for all j V. Then, we consider the following parameter set
WEW : (wy V Vaja) = (wV V = [d] [V| = d/4),
where VN denotes the class of all subsets of [<] whose size is k. Moreover, note that d/4 is a positive integer, d is divisible by by construction.
The context vectors (xn)) are constructed be invariant across rounds f. For each and U Vaja. K identical context vectors To are constructed as follows:
[xuli = 1/vd for j U; [ao = 0 for $ U.
For all V e Vas. can be verified that wy and zy satisfy the requirements of a bounded assumption [ as follows:
ww < dd < laull & V =/d=
Therefore, the worst-case expected regret of any policy म can be lower bounded by the worst-case expected regret of parameters belonging to W, which can be further lower bounded by the "average"
'Recall that K is the maximum allowed assortment capacity.
19

---

regret over a uniform prior over W as follows:
sup Ew
[Regr(w)
sup Ew
R(S", w) R(S,,
max E Wy
R(S", wv)
R(Sc, wv)
T Σ
Σ
E
R(S", wv)
R(Se, wv)
Vajal
VeVa'a
t=1
1
Σ
E
Σ
T
Σ LES
p(ils" wv) pilse wv)
(D.1)
Vaaa
VEVaya
ieSt
This reduces the task of lower bounding the worst-case regret of any policy the task of lower bounding the Bayes risk of the constructed parameter set.
D.2 Main Proof of Theorem
Proof of Theorem 7 For any sequence of assortments (8:) produced by policy π, we denote an alternative sequence (8:)2= that provably enjoys less regret under parameterization Wv.
...,,,.......................... FUr be the distinct feature vectors contained in assortments S, (if S; = 2. then one may choose an arbitrary feature zty) with UI..... U2 E Vay4. Let U be the subset among U...... Un that maximizes 27 wv, ie.. U argmaxye(U,....tj, zy wy. where wy is the underlying parameter. Then, we define S; as the assortment consisting of all K items corresponding to feature xy, i.e., S, = (TU
K
Since the expected revenue is increasing function, have the following observation:
Proposition D.1 (Proposition I in Chen et al. 16).
Σ pils,, wv) & Σ p(ils,, wv).
ieS,
D.I implies that Eies- p(1| wv) Eies, SiisSr, wv) > Eies+ piiss wvv Lie, p(i]S Wr). Hence, it is sufficient to bound Lies. p(i]S", - p(i]Sc, wv) instead of Eiss P(iS wv) -EEs, p(ilSe, wv).
Proposition
To simplify notation, we denote U, as the unique U Vaja in Sy. We also use Ey and Py to denote the expected value and probability, respectively, as governed by the law parameterized by wy and under policy x. Then, we can establish lower bound for E p(i]S" wy) Σxes, p()) wy) as follows:
Lemma D.1. Suppose e (0,1/dvd) and define = d/4-10: n VI. Then, we have -
K de (vo
Σ S
Σ S
p(i p(i Wv) >
Ke)²
2vd
For any j E V, define random variables M, : Σ/ 1(j E Út). Then, by Lemma D.1 for all
V Vaja, have
Ey Σ pilss" wv) pilSe wv) (vo + Ke)²
t K
(T
Σ
Bv(M))
(D.2)
2vd
S Se..
JEV
20

---

Furthermore, we define ) {V E Vaj4 ie V) and Vaj4-1 == & [d] | d/4- By
laking the average of both sides of Equation (D22 with respect all V Vala. we obtain
1
Σ
Ev
Σ
p(iss", wV) Σ p()s wv)
Vaja
VEVa/4
iES*
i
vo
df
Σ jEV
By [M,]
(2) + Ke)²
2vd
[ajal
VEVa/4
wok
dT
Σ Vevin d/4
Ey [ylMM
-w0 (v0 + Ke)² 2vd
4
Vala
j=1
NoK
dT
Σ
Σ
By Brog)|M
-wo + Ke)²
2
4
|aaaal
VeVage- HEV
(wD + Ke)2
vok
2dd
e
dT
4
[Vd/s11
[aja
max VEVa/e-1
Σ 1BV
Ev EvognLMM
vo
dT
|Va/-11
Ev Ev[M, [M,] + Evog)[M]] Ev
(20 + Ke)²
2
4
Vajal
VeVai-11
jFV
Pala-1
For any fixed V. we get ΣØev Ey [M[M Ey < dT/4. Also, we have
Vara
(4/4-1/((a))
d/4 3d/4+I
& 1 Consequently, we derive that
Σ Ey Σ p(iss", Σ
p(isSe, wv)
Va/4
VeVa/a
iEš,
VoK
dT
Σ jæV
-B
By[M)]
(D.3)
(vo Ke)² 2Vd
VeVait-1
Now bound the term E Evon) Ev [M,] in D.3 for any Ve Va/4-1- For simplicity, let
P = Pv and Q Proms denote the laws under wv and wr respectively. Then, we have
T
Ep[M1 EqlMi <
t
PJM, -1-Q =t]
0-/
T
TT.
Σ
PLM t] QIM,
TP-IP-QQ1 < ST.V KL(PIQ),
(D.4)
where |P - QV = supA IP(A) Q(A) is the total variation distance between P and Q KL(PI|Q (log dP/dd)ddPP is s the Kullback-Leibler (KL) divergence between P and Q. and the last inequality holds by Pinsker's inequality. Now, we bound the KI divergence term using the following Lemma.
Lemma D.2. For any V e VaJa-1 and j e [d], there exists positive constant CKL. > 0 such that
VoK
Ey Ey[M,
KL((v/\Qvot)) CKL
(vo K)2
d
21

---

Therefore, combining D.3 D.4) and Lemma D.2
we have
Ev
pl wv)
Σ
p( wv)
Va/4
VeVa24
iES*
No K
dT
voK
Bv [M
T
OKL
(UD + Ke)² 2dd
(vo K)2
voK
df
Tvd.
Σ
CKL
voK
Ev Ev
(vD + Ke)² 2/d
(wo + K)²
voo
dT
OKL
vo
Tvd
Te²
(wD + Ke)² 2dd
6
V
4
(vo + KY²
where the second inequality due to the Cauchy- Schwartz inequality and the last inequality holds because Σラ-1 [M[M]] & d4/4. Let CKLL = CRT./4.
By setting e = V 144Ck. T
d
(1o+
we have
dT
VnK VCu
sup Ew
[weg((w]]
(wo + K)2 dTe2
(vo + Ke)²
2vd
WoK
(uD + K)2
1 dvT
(vo Ke)2
vork
288 V /Ckt
Von K
Up + K dvT)
This concludes the proof of Theorem
D.3 Proofs of Lemmas for Theorem
1
D.3.1 Proof of Lemma D.1
Proof of Lemma D.I Let x = IV and à &J, be the corresponding context vectors. Then, we have
K exp (s ww) pi|S wy) - Σ piils wv) = up + K exp (x wy) 0o + K exp (+T ww)
K exp (i (TWw
Σ
ie..
in (exp (I T wv) - exp (i wv)) (vp + K exp (I WV)) (Ub + K exp (Ø wv))
Hoo (exp (x (w) exp (w)v))
(D.5)
(No + Ke)²
where the inequality holds since max fexp (xr wv). exp exp rinht-hand side of (D.5). we use the fact that 1 + a & e" & $1+a a + 2 for all a [o, 1], which can be easily shown by Taylor expansion. Thus, we get
(x T wy)] & e. To further bound the
KoK ((x - 8) Wv (8T w2)2
Σ S wv) - Σ pilSS, wy) > VE
(vo + -Ke²
153,
Oo (8E/Vd - 2/2)
(vo + Ke)²
KoK
2 2v + Ke)2
where the last inequality holds because (vde)2 de/ vi when E (0, 1/dv This concludes the proof.
D
22

---

D.3.2 Proof of Lemma D.2
Proof of Lemma D.2 Fix round t, an assortment Sp, and U.. Let U U.. Define m)(St)
ExveS, 1 UJ/K. Let (0) and (0)) be the probabilities of choosing item i under parameterizations wy and Wyo(j), respectively. Then, have
KT. (PV(1S)))Pvven)(13.) - Σ
Pt & Pc log
Σ (E
Pi 4
Σ
(pi 9:)²
qi
9i
qi
iES
xES,
where the first inequality holds because log(1 1 + x)) & x for all 1.
Let zg. Now, we separately upper bound (p: / by analyzing the following three cases:
Case 1. The outside option, =
For i = 0, x0 Re.
Thus, we have
U0
v0
Pt Víl
Uo X S
exp (z. wv)
vo + ie exp (z. wyol))
Up
Up
0o + K exp ( wv)
vo K exp ( wyobl)
exp (f wv) exp (& wwobiil
(vo + K/e)²
c. (i
(xTWV Wv x wwvul))
(uo + K/e)3
Ko
Ke
m (S.)e
my
T (wv - wrost)l (vo + K/e)2
(No + K/e)a
vd
where the third equality holds by applying the mean value theorem for the exponential function, with T = (1 - () wv) u( wyu()) for some u e (0, 1). Then, there exist an absolute constant
Co such that
(S,())) 6²
(po 00)2
of K2
Un Ke
90
(vo + K/e)4
U0
ko
my (S,)e
< Co (vo + K)3
(D.6)
d
where the last incquality holds since my(3.) & 1.
Case 2. i E S, and j $ U.
Then, for any i S, corresponding s; - and & U, we have
exp ( wyub)) 0o + exp (+ Wv) 2/ + exp (& wy
exp c Wv)
0,
where the last equality holds because exp (e wv) exp (wTwoo))) given that j $ U. Thus, we get
(pr - q,) 0,
Σ
(D.7)
JEU
Case i S, and j U.
23

---

Recall that for any i St, q: 2 have
Then, for any i Sz corresponding to 5 and j E U, we
oo+
exp (i wv)
cxp (# (TT wvol))
pps
q:l
to K exp (& wv)
cb K exp (+T wvu())
exp (o2)
-t (wV- wyuust
exp (20g)
I (wv - wroul)
vo K exp (02)
(0o K exp (iz))
exp (02) no
- (wy- - -wvo())l
(oo + K exp (o2))
my
K/e)2 1 - wwv (oo + (/o)a
Uhe
Ube
vd
the second equality holds by applying the mean value theorem, with 82 == (1 - wv) +
u(t (w for some u (0, 1). Then, there exist an absolute constant C₁ such that
mms(S))
6
Σ
(p. --)²
Km)(ši)
oge²
to Ke
(vo + K/e)a
d
fe J
K
my(S:)e²
Ci
(D.8)
(vo K)3
d
where the last inequality holds since my(S)) (S)) & 1. Combining
D.6.
DD.7
and (D.8), we derive that
(p:
q:)²
u2K2
Σ
& Co (wo + K)3
+ C
(vo + K)3
d
(0)
m,(Se)c²
< maxx(Co Ci
(vo KY²
d
vo ms)(e
CKL
(uo + K)² d
where CKL max{Co. C1). Since M, = Et= 1 (St) by definition, and subsequently summing over all t 1 to we have
KL (PvllQrun))
Σ Ev KL
Vo
Ev Er[M,
CKL
(vo
K)²
where the equality holds by the chain rule of relative entropy (ef. Exercise 14.11 of Lattimore and Szepesvári (32). This concludes the proof.
E Proof of Theorem 2
In this section, we present the proof of Theorem 2 Note that when the rewards are uniform, the revenue inereases function of the assortment size. Therefore, maximizing the expected revenue R.(S, w) across all possible assortments S E S always contains exactly K items. In other words, the size of the chosen assortment St and the size of the optimal assortment S both equal K.
E.1 Main Proof of Theorem 2
Before presenting the proof, we introduce useful lemmas, whose proof can be found in Appendix F.2 Lemma E.I shows the optimistic utility for the context vectors.

---

Lemma E.1. Let ae = z.,,, + [,s6][ If E Cτ()), then we have
E au w & 23((6) Ius H.
Lemma E.3 is K-free elliptical potential lemma that improves upon the one presented in
Lemma I0 of Perivier and Goyal [4 in terms of K. Lemma 10 of Perivier and Goyal
states: Σ Eies, Pa(i]S,. w (O) w")|[zss ll, (w & 2d log (Ae+1 + 22 and
===1 maxies, || (t,)) & 2d (K + 1) log (Ae+1 + 22), where Hz(w) = E. +
AgI--
Lemma E.2. Let He PyK + - G.(w.+)) where Go(w) YEES, Pa(i)S,, w w) Lies, Ejes, Pa(i]Ss; ()pss w) w) Suppose 1. Then the following statements hold true:
(1) D._ Lies, Po(issa, W Ws+1)pa(0 Ws+1)larsi H, 2d (1 2x).
(2) Σ maxies, | 1 < d (1 d.).
Moreover, we provide a tighter bound for the second derivative of the expected revenue than that presented in Lemma 12 of Perivier and Goyal Lemma 12 of Perivier and Goyal 44 states:
Q
5.
210y
Lemma E.3. Define Q B.K I, such that for any (Ui,...,uxg RK Q(u)
DK
exp(u.)
Let p;()) vo+ exx(ux))
exp(u.)
Then, for all e [K], we have
+yk exp(ux)
Q²Q didj
(3p((u)
if fi=1 j, if i j.
<
(p:
Now, we are ready prove Theorem
Proof of Theorem 2 First, we bound the regret as follows:
T
Re(S,, w - RR,S,, w*)
Σ
pr(is w")
Σ
Pe(lSSe w*)
ieSt
SES.
Evesp exp(xr(w") w')
EsS,, explxTow>
Un + Ejes; exp(1r)) w+)
Un + Ejes, exp(x1) w()
Eies; exp(an))
Ess,, explxT_w' w*)
Up + Ejes; exp(a15)
to + jisss exp(x1g)0) w*)
Eies, exp(ox)
EiEs, exp(xT.ww)
W
R.((S)) Ro(Se, w"),
Up + Ejes, exp(ars)
Up + Ejes, exp(x w.+ w*)
where the first inequality holds by Lemma and the last inequality holds by the assortment selection of Algorithm I
Now, we define Q RKK - R. such that for all u (u u e R Q(u) = exp(us)
Σ E R. exp(uy)' Noting that S, always contains K elements since the expected revenue is increasing function in the uniform reward setting, over, for all > 1, let u, (Uth..... .... Usix)) (ath .ett, attx) T and u (ub uixg)
write S, {ir...., ix). More-
25

---

(I72, w", w"...... Fxix w*) Then, by second order Taylor expansion, we have
(s.)) - Re(Si, w")
Q(u:) Q(u,)
1 T
VQ(u:) (1;
u1)
2 I
Q()))( - -u)),
t=1
(A)
(E.1)
where i, .......... (tigg) First, we bound the term (A).
E TR the convex combination of u, and u..
VQ(u)) u,)
exp(x1, w*)
exp(xi,.") w*) "exp(/)))) w*)
(Uet wij)
Σ Σ
(Ug Ebes. exp(x w ))2 (uei whs)
Exes. exp(21 w
1- iES;
iES; jES,
T
Σ
Σ
Pi(SS w - u1+)
Σ Σ
(ii w "p w*) - u(()
ies,
ieS, JeS,
T Σ Σ Pr(isS w') (1-Y pr(isSe, w'))
Σ
(ui =(n
tEs
JES,
T T
Σ Pe(i (ei(S,,.")pptfee w')p: w w*) - uis))
isS,
Σ Pe(i]S,, (0)S, w (2)00())))),,))))ccllllr
< (3)
Σ 1
Sr w")p, (00.)0//.w"")) wzlll,, 2,
(E.2)
where the first inequality holds by Lemma E.1 and the last inequality holds because (5( is increasing for e [T'.
Now we bound the term (B). Let p.(ūe)
(xp) t exp(ūsx)
Then, we have
1 T (u VV*Q(n)((
uz)) -
2
T
82Q Ziōj
Uui wid
(ui wiz))
2 ieS, JES,
1
Σ
Σ
(wei wng 62 Q
(us
(.y))
+
1 T
Σ Σ
upn) 22Q
(uti wie)
2 1- 8 ji
bidj
2
[-1 ieS.
T Σ
T
lua - ( utyl +
(wei - Pp: (E.3)
Je.ij
i.S.
26

---

where the inequality is by Lemma E.3 inequality, we get
To bound the first term in E.3 by applying the AM-GM
Σ
leu (ut)p uiyl
S JESr.f
T
144 (Mlp((u))pp(()))lu - wZs1
ie5 jeS,
Σ
(uei (u.
1 Σ Σ
(uej -ny (u:))((
2
2
1= Se
se.; SeS JeS.
T
Un u pi Ut).
(E.4)
t=lis
By plugging E.4 into E.3 have
T
5 T [r ui) QuQ( uz) <
Σ
(Uei pp()))((ū
2
2
(= iES:
T
10
Σ p1(()))((68)((zzz
t-1 ieS,
T
$ 10
max (8)) Jee H. KESt
103r(6)²
Σ
max
Eis H,
(E.5)
iES,
where the second inequality holds by Lemma E.I (B), with probability least 1 - d, we have
Combining the upper bound for the terms (A) and
T
R....) RA,S,, w') (0)
Σ Σ pr (i]s, w (0)S, "")l=,,
1=1 vES,
T
+ (6) max
(E.6)
1
xES,
Now, we bound each term of (E.6) respectively. For the first term, we decompose it as follows:
T
Σ
(ii(is w (O)Ss, w (')l
(ilS ((i)s),.::+)p:(((333))) wert)//ll...
S
Σ
w141)) (r -
- pr(i)Si,
w
se
Σ
Si w*) (pr(O)Se, w*) - (0)S) w++1)) | malm
(E.7)
27

---

To bound the first tern on the right-hand side of E. we apply the Cauchy-Schward inequality.
T
Pe( (11)s,,w4))p((/..5.
we+1)l m,
S
Σ pe(ils, ((t)), We+1), W(i))
Σ Σ
Pr(iss, Wot2)p, wet1) n,!
VooK (00 KE 1) VT
Po(ilSe, wr41)pe(0|Ss, We+1)l H;
t:
Veek (v0 + Ke-
2dlog T.2dlog (1+
T)
T
(E.8)
di
where the last inequality holds by Lemma F.2
Now, we bound the second term on the right-hand side of F..7 Let the virtual context for the outside option be z20 O. Then, by the mean value theorem, there exists & (1 c)w" + cWa+1 for some C (0, 1) such that
Σ (pr(i)Se, Se w.+1)) (0)S, we+ill SES.
(pi(i]se, -w:+1)p:0015. (
x5St
Σ
pr(i)St, & (i)) Σ Pr((SS..))mm) (w" (w"- we+1)p w JESt
sES,
Σ Pr(i]S Ei) [of(w" w (O w xes m.ln.
sES.
Σ (i) &,) (.)lll Σ Pr(s (w'((w- - (e(t)),,,,e+)))
iES;
jeS.
< Σ
(i Ee)l H,
|||w" w +
Σ
Sr &.) l|w wetillH.
seS,
Then, since Teo O, we can further bound the right-hand side as:
(e] {:) (:) ) llw - wetalle.
Σ
St (.)l 2 /w- WetilHH. +
Σ
ieS.
ieS.
Σ
Si (e)1 / -we-1l H. +
Σ Pr(iiSe, E lww" - wesill
=
isS
<
Σ
Si Ex 1..0l 1ww- - -wetll m +
Sr Il ,||w* we
SeSt
< 2 Σ
Si {r) [ P.-.. Iw" - w
SeS.
x (0) Σ (i)Se, (o) m0) & 2,3(()
max
| 2 H,
reS
iES.
28

---

where the first inequality holds due to Jensen's inequality and the second-to-lase inequality holds by Lemma Hence, we get
(pe(i)S,,, w*) prlSs pe Wx+1)l H," & 28T(o)
Σ
max ieS,
|| 1 11,
4d
(1
T
Br( log
2
dd
(F.9)
where the last inequality holds by Lemma
Finally,
we bound the third term on the right-hand side of (E.7 By the mean value theorem, there
exists 4 (1 -''''w + d'w441 for some (0, 1) such that
Σ St w*) (pe(O)S,, w") - pr(O, Ws+1)) |
iES.
Σ Pe(i)S,, Vp: (w" we+1) H;
=
S.
Σ Po(lSS (O < Σ (.) (w" Wata)
isS.
JES.
Po(i)S xrs H, (p +
Σ
Pe(jiSe, () n, s/ww Wetill..
jES.
Σ S.
Po(i)S w w*)l H, Σ PrliS 4) H. || W14illH
< (,(0)
Σ Pr(SSee; w*) | H.
Σ
Pr(jiSes 4 peell
jes,
< 3.(0)
max [xss|] H, Br) max sES:
Tri f1,
ieS.
where the third inequality holds by Lemma and the last inequality holds since (max, a:)²
max; of for any a, b 0. Therefore, we have
T
T
Sr(i w*) (pr(0)Se, w*) (O)S,, w(+1)) | H, < BT( 1-1iES,
Σ Σ
Σ
max
Tee
IESt
H.
2d
T
3r( log
1
(E. 10)
where the last inequality holds by Lemma E.2 multiplying (6), we get
By plugging
E..8
E.9 and
E.10 into
E.7 and
T
())
Σ ie
Σ
Si w (p)SS,, w²) xas I
2 V
T (Up Ke Ke-1) 3r (0) dT log (1+
12d
T
3T
(0)2 log
1+
(E.11)
dx
Moreover, by applying Lemma
E.2 we can directly bound the second term of (E.6).
2
T 1+
103r(5)2
max SE
| 1|
< 10)3
d
(E.12)
dd
Finally, plugging E.11 and E. into E.
obtain
T
32d
1 T
(w") < 2
Br Br(o) log 1+
(r)
log
(vo + Ke-1)
d)
dx
V 100 R
=
dv T 62
Uu K
29

---

where Br(()= -00)=0(p) (oyloogloog) This concludes the proof of Theorem
Remark E.1. If the boundedness assumption on the parameter is relaxed to ||w]2 & B, since Be(6) O (Bvdlog t log K B3/2 Vdllv K) (refer Corollary F.Dy we have Regr (w") Ô (B yooK PotK
d 2.fe It's important to note that one of our main goals is to explicitly demonstrate the regret depends on and up- deriving such a result, the dependence on eB unavoidable to our best knowledge. Note that for non-uniform rewards, the regret bound does not depend on eB (refer Remark H.1
E.2 Proof' of Lemmas for Theorem 2
E.2.1 Proof of Lemma
Proof of Lemma E.1 Under the condition w E Ce(d), we have
J Wi x, w" < || /|/w w Ila, & Br(0) n,*;
where the first inequality is by the Hölder's inequality, and the last inequality holds by Lemma 1 Hence, it follows that
Ohs Tee w = x.W., - x.ww" + [B(()) & 223(6) mail
Moreover, from 21,, W. wwww > -B:(6)) H, also have
Ots x.|w" = We "//w'' + ==(0)]]=aellm 3 0.
This concludes the proof.
E.2.2
Proof of Lemma E.2
Proof of Lemma
E.2
Since 2:.
yy syyT yxu for any x, y Rd, it follows that
Go(We+1)
Si W Wst1) Σ
Σ Σ ie S, jeS,
Po(i]S., (11 (1s
s.
Σ
Si Wst1)0as
Σ ieS, jeS,
w. (et + xz)2!!)
seS
z Σ Si] 1411)000111
Σ 8e., jeS,
Σ
Pa(i We41)p W. + ).j=T))
ieS,
Si W.+1) SS
Σ
Σ
Σ
Pa(i (j11), Watt)
SE JES,
Hence, we have
G.(w++1) 2 Σ PilSS, Wst1) (1 1- Σ
PaliiSas wott)) mnites JES.
xES
Σ
Po(SS (o+1)pp(0Ss, W.
(E.13)
sES,
which implies that
Het1 z H,+ + Σ
St w1+1)p((|SSs a
teS,
Then, get
dct (H++1) > det (Hi)
1+ Σ
(ilSe, we=1)o0( wet)) ies.
30

---

Since b 1, for all t > 1, we have EiS, Po (c( Wot1)po(dSss wo41)llwwl < 1. Then, using the fact that = & 2 loo((1 + 2) for any = E [0. 1J. we get
Σ Σ
Pa(i Ws+1)p,(0|s,,, w.+1)l H
s=1 ies.
log (1 p. Wo+1)p wat aal HT¹
(det(Hz+1)) dot(H.)
$ 2 Σ log
s=1
(tr(He++1 dd
(1+
< 2d
& 2d
di
This proves the first inequality. To establish the proof for the second inequality, we return to E.13)
Ge (wo+)) = Σ Pa Ws+1)p w. W. 2 n 2
Izc sit
sES
iE
which implies that
H41 He Gi(w++)) 2 He Σ
sES,
Since 1, for all / 1, we have maxies, |ara H K. We then conclude the same way:
max Fet 2
2
Σ log 1 max
iES,
dot(Hs+1)) del(Hs)
< 2d dl (1+ 1
log
which proves the second inequality.
E.2.3
Proof of Lemma
Proof of Lemma
E.3
Let i,j
[K]. We first have
aQ
t
2h=1 e
Pi
Up
Lk=1
(vo
2k=1 e²
Then, get
o²Q didj
1 linjeth (Σx= eu
1 1
+ 6
+ ΣK 6"
(vo + 5K =x=1 c4
(wo + Σ enxa22
e4 k
k= eua
2e 1p + Ex E'
(wo + ΣK
1 1 (Iit,, ohu tetie"s
6% Exk_e"d 20 )
1 E:
elee
+ Σk=1 c.
(wo + D 2t=1 )2
(vo + Σk= enu)2
(vo + E e3
31

---

Let (u)
e": and Po(u)
of
For i = j. we have
wo- Lini e*
1o+21-1 6m
Q
kk E
pp(()) - ps(())p(()) -Pi(u)
(u(u)pp(()
didj
U0 Σ e
> 2k-1 E
2p:(u)p;(u)
V0 + =k==1 e.
> k- t
pi(u)po(u) (p:(u)p,(uu) + +pp(())p
vo kー
cuu
pp(())p(u)) (u)
< (u.(u)
For i # j, we have
Z
Σ ct
pr(u)p,(u) (u( + (p:(u)p;(u)
θiōj
tp + >k 6%
(u)pu(u)
(u)
This concludes the proof.
F Proof of Lemma
In this section, we provide the proof of Lemma 1 First, we present the main proof of Lemma | followed by the proof the technical lemma utilized within the main proof.
F. Main Proof of Lemma 1
Proof of Lemmal 7 The proof is similar to the analysis presented in Zhang and Sugiyama 533 However, their MNL choice model constructed using shared context 2, and varying parameters across the choices wi. w k- whereas our approach considers an MNL choice model that shares across the choices and has varying contexts for each item in the assortment S, the parameter Moreover, Zhang and Sugiyama [53] only consider a fixed assortment size, whereas Tel. E.l....de st si
we consider more general setting where the assortment size can vary in each round We denote
K, = [S|] in the proof of Lemma] Note that K, & K for all > 1.
Lemma E.l. Let the update rule be
W++1 argmin Eo (w)
|ww welli..
WEW
2n
where (w) lo(we) + (w- W. Vlo(we))+ 3 well and Hi Pla+ Σt=1 G.(w.+1).
Let 17 2 log( K + 1) + 2 and x > 0. Then, have
11 < 2m Σ (x(w)) - Σ ((wss)))) )
W
+ + + 12v2n Σ || W - w.12
Σ W wsll?,
(F.I)
We first bound the first term in For simplicity, we define the softmax function at round
(z(z) R.K - Ke as follows:
exp([z);) Vie [Kt]
[or(2)] + Like exp((z]<)
(F.2
32

---

where [-]s denotes i'th element of the input vector. We denote the probability of choosing the outside option as [o,( vo Eed exp([z],) Although [o, (z)]o is not the output of the softmax
Up
function (z),), we represent it in a form similar to that in F22 for simplicity. Then, the user choice model in [ can be equivalently expressed as St w) = [a,, jes)), for all E [Ko] and Pr (0] w) [o+ ((x1 ()ss; Furthermore, the loss function (2) can also be written as f(z,, Vr) E 1 {ye 1 log (o.(2.)le)
Define a pseudo-inverse function of (+(.)) as oi RK: RK. where [a (q)]:
log (g:(11 - llq])) for any q E {p e [0, [p] < 1}. Then, inspired by the previous studies on binary logistic bandit [23]. we decompose the regret into two terms by introducing an intermediate term.
lo(w") Σ (We+1) = Σ ((()) - Σ
+ (o)
Σ (Z.. - Σ E (We+1)) (F.3)
==1
(a)
where ū. := o (Ew~P, Io, ((x)) w)jes.))) and P. == (W,,.H.," is the Gaussian distribution with mean w, and covariance matrix elt,', where e is a positive constant to be specified later.
We first show that the term (a) is bounded by O (log K (log ?) with high probability.
Lemma F.2. Let 8 E (0, Under Assumptions for all t E [7]. with probability at least 1 - 8, we have
(2v1+ + 2
eeww")) Σ Ys) & 11 11- logg(1 + (K + 1)t) 3) log
2.
Furthermore, we can bound the term (b) by the following lemma.
Lemma F.3. For any 0, let X max 72ed). Then, under Assumption 7 for all t 3 have
Σ (s)).))s) - (1)+1) &
w. - wo + Vod 1 ++++1
2c
2x
Now, we are ready to prove the Lemma] derive that
By combining Lemma
Lemma
F2 and Lemma
H
Wi+1
w 1
22v1+ 28
+ 2 + Ved 1+ t
+++++
11 (3log(1 + (K + 1)t) + log < 27
8
2A
+41+ 12 Σ W w-12 (7
(1-1)
Wo+1 -w,12 w.
12vI+ 20
+ + Vodd 1+ t ++1+
< 2n
11 111.33 (3log(1 + (K + 1)t) + 3) log
8
2x
+ +4 (0)= = O (dl (d(log & log k))),
(F.4)
where the second inequality holds because by setting 7n/6 and X > max(84v 84d1), we obtain:
12 21j W.-1 - ="
wall2
Ws+1 - walli.
W2+1 wsll2 1
12v2n Σ
W wal? H.
x-1
2 >
1)
& 12v2n
Ws+1 -wal < 0,
33

---

where the first inequality holds since Hg ALd- By setting 7 = log(K + 1) + 2 and X = 2dn we derive that
l|,, 1m,, & W. We+illa, + || w'l H,
Ww W + || w'l 1y41
[: W + 1
(6) = Bc( = (Vdlog log K).
where third inequality follows from the definition (f in Equation and the last inequality holds by Lemma F9
This concludes the proof of Lemma
Corollary F.1. If the boundedness assumption on the parumeter relaxed to ||w||2 B, then (((8) O Bogloggtoo K B3/2 / /d K).
Proof of Corollary F.7 When |w|2 & B, following the same analysis as in Lemma 1 we can set 7 log(K (K + 1, c 7n/6, and X = O(dB log K).. Under these settings, we have
||1111 w'
2v
+ 2 + God (1+ 1 1+11 2A
< 2n
11 (3log(1 + (K + 1)t) + 3) log
+4B²X
BBVdlog t log K + B3/2 v dlog K
which concludes the proof.
F22
Proofs of Lemmas for Lemmal 1
F2211
Proof of Lemma F1
Proof of Lemma F.
Let (w) l. f.(w.) + (VS,(ws), w (w, w wsll? be second-
order approximation of the original function f, (w) at the point w The update rule (3) can also be expressed as
W argmin (w)
2n l|w walli..
weW
Then, by Lemma F.4 we have
(VL, W
(|w,
w/ 1
|| - w'llir, || - -w.lir.) (F.5)
2m
To utilize Lemma F6
rewrite the loss function ((IJw) (o(w). Consequently, according to Lemma F.6 it follows that
(.(w++1)- - (, (ww)) < (VL, (W.+1) We41 -w") - -ww=I1-WTTEReem..... (F.6)
where Ç log(( + 4. Then, by combining (.5) and (F.6), we have
(.(w++1) - -c((w") < (Vl, -
Wo+1 - w*)
1 c |lw. w111 | wi | wollir).
34

---

In above, we can further bound the first term of the right-hand side as:
(Ve,(w+1)) Vlg (W++1), Ws+1 -w")
(Vlo(Wo+1) - Vlo(w.) -Wsts(s))WWaa - -We), Wo+1 w')
(D'
Ws][Ws+1 Ws), Ws+1 wn)
< 33/2/Wo41 - ww -w'12/ - woll
6v Ws+1 wollfre,ee...)
E 6v Ws+1 w
where in the second equality, we apply the Taylor expansion by introducing Es+1, a convex combina- tion of W and Wa. The first inequality follows from Lemma C.I and Proposition C.I the second inequality holds by Assumption | and the last incquality holds because
V2l (oEoEt))1 Go(E.+1)
Σ Eot1s.,
Σ Σ EottsSss.
iES,
1E9, JES,
Σ iE8,0(0)
Pa(i]S,, E0+1)
Σ
Σ (.11)e... (..
xES jeS
[
[ ((s...)))) [x
E.-ps C.-pp(11S..e. (1))))++1)
DesT st Id.
where the third equality holds by setting F&0 for all 1. Now, by taking the summation over s and rearranging the terms, we obtain
|w+11 w' w'1 lite
la (w") Σ la (Wstt)) + [[wi - - GV Σ Wx+1 w.l2
|W Wallt.
Σ (aww))
Σ (wsr))) 42 +4x+ 6v2c
Σ
Ws+1 w.l2 Σ Ws+1 w
s=1
where the last inequality holds since |w1 w' $ A//wi conclude the proof.
w'12 12 & 4A. Plugging in Ç 2n,,
F.2.2 Proof of Lemma F2
Proof of Lemma F22 Since the of 2, tt (Ew-r, [ax ((x) jes, )]) is unbounded general, as suggested by Foster et al. 25). we use the smoothed version z o (smooth" Ew-P, [o, (Ir, jes)) as an intermediate-term, where the smooth function is defined by smooth" = (1 p)q + pl (K, + 1). where 1 E R is an all one vector.
Note that 20 a (smooth ar, (Z.)) (2.))) ))) by the definition of the pseudo inverse function of such that a. (o.()) for any q E {p E [0, 1] K, ||]] < 1}. Then, by Lemma R7 we have
Σ E
(G v.) 2pd, and
ا log(1 (K + 1)/p).
(F.7)
Hence, to prove the lemma, we need only to bound the gap between the loss of w and ž.. To enhance clarity in our presentation, let ((2). ys) = E.( (w"), where 2 = (xI, wx) jes, E KRK,, Then,
35

---

we have
Σ e (w")
> ==1
( b Ys)
Elz Ys) - Σ
((
==1
1
E Yo), (/5)
Cp
==1
Σ (os (2.) 2. 2nd
Σ
- 11
(F.8)
where C₁ log( (K + 1) + 2 log(1 + (K + 1)/m) + 2, the incquality holds by Lemma F. and the last equality holds by a direct calculation of the first order and Hessian of the logistic loss follows:
V_l(z,,
(z.) y (.ll,, diag ar, (z.)) (z,
We first bound the first term of the right-hand side. Define d, (z; /(c, + 1). Let d', be d, extended with zero padding. Specifically, we define d' = [d] 0, ..., 0] R where the zeros appended to increase the dimension of d, to K. Similarly, we also extend o oz(z,) ys with zero padding and define s, = [(o,(z*)) y ........ RR
Then, one can easily verify that || & since |2]|e & maxses, ||ا w 12 & and | & log(1 +KK + 1)/k). On other hand, d', is F,, F--meauurable since z and 2y are independent of y.. Moreover, we have [ 15C1 [d. Elio, (x;) (t)
||d (x.))) and
|lo,((2) - yslli & Thus, by Lemma F55 with probability least ō, for any > 1, we have
Σ 0. (z,) V,, =
(eu + 1) Σ
(z.zzz) ys.
(cp + 1) Σ
(E., d')
mm1
V
2
1 1t
ddll (o (x²)
4
(cp
+ 1)g
7 Σ
d, 2 (x;)
log
4
1=1
V
12v1+22 21
(cp + 1)
x Σ
d (x))
log
(F.9)
where in the second inequality, we set Ā 1, and the last inequality holds because ||d ||d,ll
d Vo, (z,)d, 2. Then, combining F.8)) and F.9
obtain
C ww) Σ
( ys)
s=1
& (cp 1)
A + Σ
d 2 (x;)
V
+
4
log
2 1 + 21
Σ 1 25 vz;)))
4
X
s=1 Cp
==1
V
4
12v1 + 2t
< (cp +1g
λ+ Σ
d. 2 (x)()
+
log
- (c, + 1) Σ
|d (o,
4
V
8
V
< (cn +1)
1+ Σ
d [d.ll3
+cn + 1)
log
(2 1 21.
8
(c,
Σ
|.d.ll2
17
2v1+
2t
16
2211+ + 2t
2
=(c 11)
2 log
+
log
(F.10)
16
8
X
8
36

---

where the third inequality holds due to the AM-GM inequality. Finally, combining FF.7 and (F.0O). by setting μ = 1/t and
vI7 log
2
we have
2v1 2
(lo(w") ((Z,, & (cp + () +) log
+ 2
5
12vI+
< 11 (3log( + (K + 1)() + 3) log
+
8
where the last inequality holds by the definition of c/ = log( + 1) + 2og + (K + 1)/p) This concludes the proof.
0
F.2.3 Proof of Lemma
Proof of Lemmal F.3 The proof with an observation from Proposition in Foster et al. 225 which notes that 22 is an aggregation forecaster for the logistic function. Hence, it satisfies
yo) & -log (Ew-P,
(e<(((w)) = -llog
Z, Jzc
1 e (-b,(w)dw)
(F.11)
where L.s (w) : (w) + w wsll and Zs V (27) H.71
Then, by the quadratic approximation, we get
w.+1> [w()) = I., (w++1) + (VLL w -ww.11) + 1
|w - wotilli..
(F.12)
2c
Applying Lemma F.8 and considering the fact that l, is 3//2self-concordaa-iik function by Proposition C.I we have
L,(w) [,(w) 18// w wotzll
(F.13)
We define the function fo41 W - R as
[s+i(W)= = exp
w 112, 18 18 weell
Ws+1 Wstillere
2c
Then, can establish lower bound for the expectation in
(.II) follows:
E.-r, [ (w)
exp( - [.s(w))dw
Z,
Jud
1
exp(-L.(w) 1.l w
Z.
JRd
exp( - [.,(w,+1))
fsti(w): (e, -
Zg
Rd
(F.14)
where the first inequality holds by (F.13) and the last equality holds by F.112) We define Zot1 = Sp Jo+1 (W))(())www & +00. Moreover, we denote the distribution whose density function is f (w)/ /2t1 as Pat1. Then, we can rewrite Equation
F. F.14g as follows:
(w: exp(- L.(...Ww.............. (1++)))22 1)) Ew P.12 [exp( (VVL w
Ew-P, P. E ((((()))
Z.
exp( L, L.(W.+1 22,11
exp (-Ew (VL,(W w Wo+1>l)
Z.
exp( -Lo w.+ (1)+)))) 1))2411
(F.15)
Z,
where the second inequality follows from Jensen's inequality, and the equality holds because P.+. symmetric around Wa+1, thus E Ew- P.., [VL., (w..141))) W 0.
37

---

By plugging (F.15 into (F.IT) we have
y,), & (W(+++)) 1) + log 2. - log 2
(F.16)
In the above, we can bound the last term.
log Zs+1, by
- -log 2s+1 = log (Jee exp
(-1
1 ||
Ws+1 1 - e 18/w w - wo dw
2c
= log (Zo+1 B
-
Pats
exp (-ee 18/w w wat Ilse (()))))))
< -log Zo+1 + E w.
18 @18/ w wotalleze,
Ps+i
R 1 Po1s = -- log 7.
18/w 1180w/ w
(F.17)
where Pa+1- NN(wst1,cH, and Zo+1 SR exp (- 2/4 w w i1. dw. In (F.17, the
inequality holds due to Jensen's inequality, and the last inequality is by the fact that 2,+1 Ja exp (- |w w dw (12m)ddHH²) Z..
By applying the Cauchy-Schward inequality, we can further bound the second term on the right-hand side of (F.77 by
( 218lwww.112 w w.+ 1ltillaee
B Batt
B P w3llww
wotnl
E
w Pats
[iw-
(F.18)
(a)-1
(a)-2
Note that, since Ps+1 = N(w.+1 cH,²), there exist orthogonal bases e1, E Rd such that Ws41 follows the same distribution
Ves (Ho X,,,,
(He where X, hid. N(O, 1), Vj. ejv [d].
(F.19)
and X; (H,)) denotes the j-th largest eigenvalue of H. 1, Then, we can bound the term (a) -1
(F.18) as follows:
d I
V E Ban Pass [030 Ex,
e 36c2 (66))((H+
I Ex, e x
36g
x²
&
j-1
j-1
2 [ (efxe))
= (xxax²
Ex-xa 1ocd x
where the first inequality holds since x (H, < J. In the second equality, x2 denotes the chi- square distribution, and the last inequality is due to Jensen's inequality. By setting À > 72ed, we get
VBW~AR [630|w-
Exxx²
22,
(F.20)
where the last inequality holds due to the fact that the moment-generating function for disttribbt bounded by Ex Exxx=(ee* [ & 1/v1 27 for all / & 1/2.
Now, we bound the term (a) in F.18).
VB BuwnPorn
w W F2e, F22, (wa-))
V E Ww || (m..))
E /w.-No,ccf, [1
38

---

where H, = ((++)() 1/2 Let X = Xy (cft,") be the j-th largest eigenvalue of the matrix - Then, conducting an analysis similar to that in equation (.19 yields that
E W [[w]l]]]
E ,
Σ
e
21
d
Σ X2x3
E xx,~N(0011)
Σ
Xj X x3x33]
1-11
Xi = Tr (
where the inequality holds due to Ex, , ((on, < for all j.j' E [d]. and the last equality holds because nd X5 'I (c. Here, Tr(A) denotes the trace of the matrix A.
We define the matrix Ms+1 :- AL//2 + Σ Vet (P(((w++1). Under the condition À > 2, for any [T' and w W, we have (w) La La Thus, we have HI M Then, we can bound the trace as follows:
Tr (115') 'r (2,
L w Tr (M (2
det (M,())
Tr
M,)) < log det(M))
where the last inequality holds by Lemma 4.5 of Hazan et al. [26] Therefore can bound the term (a) -2) as
v 33llog dct(1)+1)
E
w-
Pe+s
[w
Wotlll
det( (Ma)
(F21))
By plugging
(F20)
and
F221
into F.18
we have
del(M
E
Pota
18|w
Wst (
v Vellg
dct(M, (M,)
(F.22)
Combining
F.16
F.17
and
F.2
and taking summation over 8, we derive that
(w.11 + Vcc log dct(Ms+1)
Σ (( Vo
det(M,)
to (We+1) +
1
Σ
|/w, - w + /ee
det det(M log det(M,)
2c
(w +
1
>
1
||, - w.+1 12,, + V6elog
dde((M+1))
2c
det (2I
1
(1+ t
(w +
| w.. 12, + Voc dlog
2c
21
By rearranging the terms, we conclude the proof.
F33
Technical Lemmas for Lemma
Lemma F.4 (Proposition 4.1 of Campolongo and Orabonal 12). Let the We-1 be the solution of the update rule
We+1 arg min (ele(w) Dolw, w.),
we
39

---

where V = W = Rd is a non-empry convex set and Dw(W1.W3 (Ve(w2), W W2) is the Bregman Divergence w.r. strictly convex and continuously dif- ferentiable function vo W - R.. Further supposing (p(w) is 1-strongly convex w.El a certain norm || W, then there exists a gi (le(()+)) such that
vb(1) (w2)
(n.g We+1 u) (Vb(w.)) Vul(wz1)) W u)
for any W.
Lemma F.5 (Lemma 15 of Zhang and Sugiyama 53). Let (Ft) be filtration. Let (2))== be stochastic process B2(K)) {z TRKK |1 & 11 such that 2, is Ft measurable. Let {Ei]i=1 be martingale difference sequence such that e, E IRK is Fe+1 measurable. Furthermore, assume that, conditional on Fr, we have | & almost surely. Let Ee E[E,e [F]. and O. Then, for any 2 1 define
U. =
Σ (E, n.)
and H, = x Σ 12.133..
Then, for any d (0, 1], we have
Vx + VI
He
4
(2)
Pr H
log
+
log
6
<d.
vx
Lemma F.6 (Lemma 1 of Zhang and Sugiyama 53). one-hot vector and b E R Then, we have
Let C > a [-C, y RK+1 be
((a,)) y(b,y) + y) (a- b) log( K 1) 2(C (a- ba
Lemma F.7 (Lemma of Zhang and Sugiyama 53). Let z R.K be a K K-dimensional vector. Let y) Σ 1// 1) log (()()]]))) where y .kk E gk+1, and the softmax function (z) : R - R is defined as [o(z)]; No Di-1 (xp((x]N) for all i E [K]. Define z² == a- (omoolhy(o())) where smooth, = ()++ W + 1). Then, for μ [0, 1/21, we have
exp((x]
og and [o] # exp([z)a)
((zl, y) E(z.y) 241
We also have | log(1 (K + 1).
Lemma E88 (Lemma 18 of Zhang and Sugiyama 53). Let Le(w) Ex(w) 2% - Assume that Ee a M-sseffconncrdtatt-ik function. Then, for any w, W. E W. the quadratic approximation T.(w) [((we-1) + (V2L, (We+))) w we+1) + ze [w We+1 121, satisfies
[w()) & (.(w)= + e M I9 -ww-werllll - wetilleemmm.
Lemma F9. Let Wc+1 = argmin W (Ve((w)), w) 1 well? Then, we have
w.llu, Vle(()))mm Vil((w))) 2n
W wil1-w.lla
Proof of Lemma F.9
We make slight improvement to Lemma 20 of Zhang and Sugiyama 53
Lemma F.10 (Lemma 20 of Zhang and Sugiyama 53). Under the same conditions as Lemma the following holds:
We+1 - wellm, & n/ (e())ll & 1 II W
In the proof of Lemma 20 by Zhang and Sugiyama [53] the bound for (we)( was given as [[V&&(:))lz & 2/K. However, tighter bound can established: [VL(w,,)) & Using this
tighter bound, we can refine and derive the improved result.
D
40

---

G Proofs of Theorem 3
In this section, we provide the proof of Theorem addition to the adversarial construction presented in Section D.1 we construct the adversarial non-uniform rewards.
G.1 Adversarial Rewards Construction
Under the adversarial construction Section D.I we observe that there are K identical context vectors, invariant across rounds t. Therefore, in total, there are N K (a/s) items. Let the rewards be also inverinvariant. Given wy, we define a unique item a" E [M] as an item that maximizes a. wy, i.e., Zi+ zy, and has reward of 1, i.e., Pi+ 1. Then, construct the non-uniform rewards as follows:
1, for i 1" ( for th i"
Vi
(G.1)
where we define y as
7 min mines exp(x; wv) SES vo minies exp(x; wv)
1
Un
Note that 7 1.
G.2
Main Proof of Theorem
3
Proof of Theorem 3 Given the rewards construction as G.I any reward in the optimal assortment S is larger than the expected revenues.
Eiess exp(a wy)r: no to Ejes exp(x exp(=]/v)"
Lemma G.1. Let wv)
Then, we have
r4 > R(S",)
Vie
Lemma G. implies that S* contains only one item it This is because if S* {xr;-) adding any item * to the assortment results in lower expected revenue, since r; < R(S" {2r)) w.).
Furthermore, we can bound the expected revenue for any assortment as follows:
Lemma G.2. Under the same parameters and context vectors as those in Section D if the rewards are constructed according to Equation (G.I). for any S, we have
R(S, wy) < max exp (z) wy)
+ maXies exp(x. wy)
Let Zü....., TU.. be the distinct feature vectors contained in assortments S, with UI...., Un Vala- Let U be the subset among Ul...., Uy that maximizes a/.vv i.e. U* argmax Dy,,, where Wy is the underlying parameter. For simplicity, we denote Un as the unique U E Vaja in St. Then, we have
T
(xp(xTwv) vn exp(xxTwr) wv)
Σ R(S* wv) R(S,, wy)
R(S,, wy)
exp(xTwy)
max exp(x. (2.] wy)
Vn exp(xTwy)
No maxiss, exp(x. wy)
exp(xTwy) Up exp(x wy) To exp(1 ( wv)
exp(x) wr)
where the first equality holds becauset S* contains only one item by Lemma G. (and recall that Iy- .V). and the inequality holds by Lemma G.2 Hence, the problem is not easier than solving
41

---

the MNL bandit problems with the assortment size 1, i.e., K = 1. By putting K and 2 ((1) in Theorem
L
we derive that
sup B [egg ww] w
1
Σ
E
Σ
R(S", wv) R(S,,
Valal
VeVaj4
1
exp(xTwv)
exp(x w.) By + exp(x G. wv)
E
Vajal
Ub (v)(=(/wv)
VEVar4
= Ω (dvT)
This concludes the proof of Theorem
G.3 Proofs of Lemmas for Theorem
3
G.3.1 Proof of Lemma G.1
Proof of Lemma G.7 We prove by contradiction. Assume that there exists i S* such that R(S", Wy). Then, removing the item from the assortment 5* yields higher expected revenue. This contradicts the optimality of S*. Thus, we have
Ti wv)), Vie S*.
This concludes the proof.
G.3.2 Proof of Lemma
Proof of Lemma G.2 We provide proof by considering the following cases:
Case 1. 8' S.
Recall that, by the construction of rewards, have
7 min mings exp(x. wy) SES Up + min exp(x] wy) Up + minjes exp(x wv)
mings exp(x. wy) exp(x.. Wv)
(G.2)
Up + exp(xx..ww)
This implies that
Σ exp(x, wv) ) 7 (no exp(2x. wr))
Σ
exp(x; wv) eesp(st.v))
1es)
(xp(x,.wv) + Σ exp(xx wr)> (oo exp(xx..
(ES((())
& eex((x.wv)
+ explax wv)
Σ exp(2 (V))
(EST(M)
(xp(x,..v) + EsEST( (xpss((()pppp] exp(x. wvhy Uo Yies exp(x. wy) Therefore, for all S E S, we have
exp(sx. wv)
(G.3)
+ .v)
Eies exp(x, wr)r
exp(x,..vv) + ExESY exp(x] wy)r
R(S,wy) 0o exp(xx_ wv) + max exp(x: wy)
Cu Lies exp(x, wv)
Up + Lies exp(x) wy) max exp(x. wy)
exp(xxT.v))
where the first inequality holds by G.3). and the last inequality holds since f(x) increasing function.
is an
to
42

---

Case 2. 1" 4 S.
*o Eics exple, wr) Eies exp(z, wy) y m exp(2) 2 Wy) which is equivalent to
Let us return to G.2p. Since
for any S S, we have
min exp(2 (2, Wy)
do + Eies exp(x?} (ap(oo/.v)
Up + minge exp(x; wv)
vo + minges exp(x; wv) Eies exp(xx) [xxp(a/[T)) wv)
Eies exp(x, wayy
mines exp(x: wv)
vo Lies expl2, wv) & + minis exp(2, wv)
Hence, for all S S get R(S, wV) Eng wr)y Uo Exes exp(x;; wv)
minjs exp(x, wv)
msX exp (2)) wv)
to minies exp(2; wv)
vo max exp(2;) Wv)
This concludes the proof.
H Proofs of Theorem 4
In this section, we provide the proof of Theorem Since consider the case of non-uniform rewards, the sizes of both the chosen assortment S,, and the optimal assortment, S are no longer fixed at K.
We begin the proof by introducing additional useful lemmas. Lemma H.1 shows that R, defined in (6). is an upper bound of the true expected revenue of the optimal assortment, R w").
Liee )re oa Lses explass)) And suppose S, argmaxses ses (S). If for every item E Sú, an 3 I w", then for all 2 1, the following inequalities hold:
Lemma H.1 (Lemma 4 in Oh and Iyengar 41). Let RS)
Re(S;, w") & R((S;) & R((S.).
Note that Lemma H.1 does not claim that the expected revenue is a monotone function in general. Instead, it specifically states that the value of the expected revenue, when associated with the optimal assortment, increases with an increase in the MNL parameters [ 41.
Lemma H.2 shows that (St) increases as the utilities of items in S, increase.
Lemma H.2. Let Re(S) = Eies exp(au)re and Sy argmax Re(S). Assume d4 > au 2 vo Lijes exp(or)))
for all i e [N]. Then, we have
EiS,, exp(al,)ra Ra(S,)
Uo + Ejes, exp(a?)))
Furthermore, provide novel elliptical potential Lemma H. for the centralized context vectors It..
Lemma H.3. Let H. = AL + XT=1 1W), where G.(w) = Eis,, Po(i)Ss, w J
Eies, Ejes, Pe(iSS., (il,,, w). Define i Dst Es-p (is.. Suppose
A 2 2. Then the following statements hold true:
(1) Σt= Eies, (cl., w W 2d (1+ + 4
(2) Σ maxies, 1 H & dloo (1+ + d.).
Now, prove the Theorem
43

---

H.1 Proof of Theorem 4
Proof of Theorem Let d/ x/['" + +3,,()][==l11;;" If Co(o), then, by Lemma E.1
have
0n v x/ + 2286(0] = d/3-
We denote Rsi)
Lus, explaidru tot exp(oly))
Then, we can bound the regret follows:
T Re(St, R w*)
T Σ R((S)) Re(S, w') Re(S.) Re(Se: w"),
T
where the first inequality holds by Lemma H.T and the last inequality holds by Lemma H.2
Now, define Q IRi IR, such that for all (uI,..., "1s. RiSd, Quu) exp(ux)rus vo 22 S. exp(u,)
Let S. 1 (s..)- Moreover, for all 3 1, let u,
(wei..... ".ys, ) = (abs).... ..... dnjo, ) and i (u,,.... "0...... " (I74) w...... T w²)
Then, by applying second order Taylor expansion, we obtain
T (S.))) - Rs,S, w*) = Q(ux) - Q((,))
T
vQ(u;) (u, - (0;--;)) + 2
Σ
mn
[ - -u²),
ut)
(C)
(D)
where (wrig...... Utijs T IR Sel is the convex combination of and u..
We first bound the term (C).
vi(u)) ui)
explx w "r
Σ (ip(zi][")ra Eies, exp(xx]."')
(ue (uu- - (u))-wp)=
(vo + Exes. exp(2 (x,[[=[,) w)2 (ues (fs))
Uo EKES. exp(x [o w+)
S
jeS.
Σ Σ
St) w (reci und)
Σ
Si w w")rexPe()SSp w w")(ur- wiz)
t=1 ie
S:
Σ i
Sr w")r (us (i))
Σ
Pr(jsS, w (tz)
jES,
Σ Σ
Si) w")
23.(0) 1
Σ
pr(jlSe, w (6)
1=1 ieS.
jES.
T Σ (6(6) Σ (ilSs W'r [
Σ w')]sss (atesll.)))))
ieS.
JES.
44

---

Let 2 = 0. Then, we can further bound the right-hand side as follows:
T
2
3e(6)
Σ
St w')re
(1atslllr, Σ pi(jiSi, w
ieS,
JES.
2
(6) Σ
PrlSs w w")r
Σ
PrlilSe, w 1lressl 15
1=1
1ESt
JES.u
2 (6) Σ Pr(S, wrrr (Rezellerr - (l (Ioeellez,1) ))
1=1
kESt
(8) Σ Pr(i)s w") (Ieul1,.* (1-m [1walllr
2
KES,
T
< 23)
Σ pe(ils,. w") (Ieeilll,, - B)-pr((s I (xeslee,1) 1I)
iES!
< (8)
Σ Σ PelilSi. w") (Izzlllm.* (B)-n(()) (xes)llaTT)
iEst
< (0) Σ Σ pr(ilS., w [|sl///-Bsssssss... Bs-p(tss..w)) [ ler."
iESt
T & (0)
Σ Σ Pa(i)Se, w") 204 Es-p(((s. [xeillla
ieS.
where, in the first inequality, we define St S S₁ as the subset of items in S, such that the term Naae n, E)-p(((s...' || In > and Tu e [o, 1]. the second inequality holds because (5) & ..... & (5), the third inequality holds due to Jensen's 's inequality, and the second-to-lan inequality holds due the fact that ||a] ||a b + bl ||a bl + |b] for any vectors a, b RR..
For simplicity, we denote Ew[res] = (s.. [rey]. Let Fee Di Ew- Ew-[s and Z.s Tu
Then, we have
T Σ Prli (())ss. w - -)-p(((1..w>> [rns]] n
T
Σ Σ Prlie w "iaall
SeS.
JeS.
- Tesl H.
St. w 11
SE
Σ
Pr w') Teal m
Σ
(p) w') - (pr( we+1)) |
S.
Se.i we+s)
(H.1)
se
45

---

where the inequality holds by the triangle inequality. Now, we bound the terms on the right-hand side of (H.I individually. For the first term, we have
T
Σ SE
Se. w wl)l - Faille,.
Pr(i/Se; wx) |Bwe [1ne]] - Ew [ [ H.
Σ
Pe(ilSe: w")
Σ pillll, w w")) rzj jes.
where the last equality holds due to the setting of z = 0. By the mean value theorem, there exists E. (1 c)w" + oW2+1 for some (0, 1) such that
Σ (pelilS,, wo+1) Pe(iSSe. w')) Dz5 jES.
Vpe(i)S..E))
(we+1 (wee+++ w 20))
H
jES.
H.
[pr(j(s,; (weet -ww)==="||l<s)lrrrrr"
jeS.
Σ
Pr(j]Se, E,),, - pe (.).,
Σ
(Wert - w")
jeS.
keS.
Σ Pr(isSr, 6.) | (we+1- - w
Σ Pr(s, 5.) | Σ Pc Ex) (eeee - w*)l
+
JES.
kES,
Σ PrOiSS (.)/wet11 - -w'l. | P
JESr
+
Σ
Pr(jis 6,) |, Σ
(A (iee Hr [ee11 - ww...
jeS.
ReS.
Σ P((j)S(. Ei) mmsllir, Betz(0) (
< (0+)(())
PililSSe Ei) |وااا jES,
Σ
JES.
< (3)
Σ
JeS
< ( max
2 n
JES,
where the fourth inequality holds by Lemma Jand the second- ca-s-tt--lstt inequality holds due to Jensen's inequality. Hence, we have
T
Σ Σ pr(iss,, w" Tell Julm. H. $ 3-
Σ
1
Σ
Sr(iiSe, w*) max
|
JESt
1=1 1eSt
[=1
ieS.
T
< 2,3
Σ
max iE9t
2 H.
T'
T
B1+2
1+
(H.2)
dd
where the last inequality holds by Lemma F.2 Using similar reasoning, we can bound the second term of (H.1) By the mean value theorem, there exists E (1-c')w" +c'we+1 for some e' (0,
46

---

such that
Σ (po(4)S,. -
pr(iss,, w.+1)) |. = Σ
" Vpr(ils;,E)) E.) 'w'" - Welllleeellrr
iESs
ieS.
Σ iES.
Pr(i]Se, Ei)= pr Σ
Pr (t) (w" - We+ H,*
heS.
< (6)
Σ er (.0...5(1)01 (xee 11, +1@e1|2eol11,.
VESI
+ (6)
Σ
Pe PP(il St, < +1x1l==ll Σ
pe (k:Se, (.) 1 mr
ieS.
keS.
< (8+1(()
max
Iual म, | n."
B (8) max
max
a H,
VESt
iES:
kES:
Then, by applying the AM-GM inequality to each term, we obtain
(0) max | || + Bc+1(6) max S:S:
[Bssll,, max [aaelllrr keS.
se
mmaxies || .) + (maxses, || H. 1) 2
| 11,1 + | m1, (ot)(0)
< (8) max iES, (8) max lESt
| 12 W1!1
+ | 1T, + (6)
maxies, | [i nr + maxtes, | 12 H1,
2
< 1 max
max iES.
12 n,
max ieS,
Tei Hr.
where the equality holds since (max, a,)² max; as for any as 2 0. Thus, by Lemma H.3 (or
Lemma E.2 we get
T
Σ Σ
(i w*) - Peli We+1)) ((elll
iES.
T 1+ di
& 2B (8) max
max ieS;
|
H. H.
max seSt
|
H.
-
1
(H.3)
Finally, we bound the third term of H.I.. By the Cauchy-Schward inequality, we have
Σ Σ Si wesl) 1= te
Σ
Pe(iiSe, Wr+1)
Σ
Σ
Pr
1=1 ie
St
T
vT 2d
(H.4)
dA
where the last inequality holds by Lemma
H.3 Plugging HH.2)
H.3
and H.4 into H.
get
T
Σ
(ilS
w [z E)>p(((S).w)) [1ns] 1,
LES.
(1+ T (1+ dt
+ 8 =31+2(0)dlog
T dA
< VT 2d log
1
K
Thus, we can bound the term (c) as follows:
Σ vQ(ui) Tu, - (3T(0) 2d
1+
T dx
16
(T)
(0)ddlog
(1+
T
(H.5)
47

---

Now, we bound the term (D). Define Q : RI
R, such that for all (W1,.... U1s R|
(uu) E
exp(
Then, have
2
since ras [0, 1]. By following the
- exp(a,)
Neej
similar reasoning from Equation
F..3
(F.5
in Section
E.1
we have
0²Q
u u,) V²Q(())) ui) =
Uns
((s)
Utj - wiz)
dioj
jES.
2
|utj
uizl
1= IESt JES:
< 10 2
max | St
(H.6)
2Q dady
where the first inequality holds because
$
Combining H..5
and H.6
we derive that
Regr((")) < (83
2d
1+
T dA
16
(r()))r+1
(0) 1 (1+
T
k
dA
(8)2
max LeSt 1-1
Σ
T'ss
H
- dd''T -ō
_22
where (r( O (Vdlog K). This concludes the proof of Theorem
Remark H.1. If the boundedness assumption the parameter is relaxed |w|2 & B, since B((8) = O (Bydlogt tog K B3/2 B3/22//loo vdlog K) (refer Corollary E. we have Regr(w")
Ô dd).
H.2 Proofs of Lemmas for Theorem
H.2.1 Proof of Lemma
H2
Proof of Lemma 11.2 We prove the result by first showing that for any i S,, we have rıs > ((,). This can be proven similarly to Lemma G.1 Suppose that there exists i e S, for which rıs < (a.).. Removing item i from the assortment S, results in a higher expected revenue. Consequently, S. # argmaxses (S),, which contradicts the optimality St. Thus, have
Te > Re(S.), Vi S..
we increase Oni to of for all e St, the probability of selecting the outside option decreases. In other words, the sum of probabilities of choosing any E S, increases. Since rss > R((S,) for all i Sr, this results in increase in revenue. Hence, we get.
R,(S.) = Lies, exp(an:)ru vo + Ejes, exp(a2;)
Lies, exp(a())rs vo + Ejes, exp(al,)
This concludes the proof.
48

---

log H.2.2 Proof of Lemma H.
Proof of Lemma H.3 For notational simplicity, let Ew [xty]] B5-m ( Let tzo 0. We can rewrite G. (w) in the following way:
(w(w++1)
Σ Ps(iiSs: W Ws+ 1151)
Σ
Σ
(H.7)
1e5. jeS,
Σ Pa(isSos Ws+1)
Σ
Σ
Po(i Ws+1)p,(i|Ss, Ws+1)
(0S,
ieS, (0),, JeS
BAw,1 [Tstl T
Bw 1 [Jsi] (Bws1 [Ixi]]
81
Baot1
[[Tzt Ro [Tmm) (Fit Ew [fmmm] ]
Bw [20
Σ Pa(ilS,: Ws+1) 2
Σ
Pa(SS Wst1)2sr
isS
This means that
H4r He + Ge(we+1) 2 He+ Σ
(H.8)
ieS,
Hence, can derive that
det (H++1) det (Hi) (1+ Σ PclilSe Wet1)
VeS.
Since 1, for all > we have Eies, Pe (ilSs, wet1)ll $ 1 maxis, @ & 1. Then, using the fact that z < 2 log(1 + z) for any E [0, 1]. we get
S. w.t1)l H.
$ 2
log Pa(iS.., ws+1)l
#=1 LES
8=1
/det(Hs+1)
2
det(HH)
s-1
ddt(HH++1)
2og
det(H,)
(t (tn(H(41)
1+ #t)
< 2d log
2d
dA
dx
This proves the first inequality. To show the second inequality, we come back to equation (.8).
By the definition of K, we get
H He G.( = H, +
Σ
S w
ieS:
2 He + Σ T.iTT
Thus, we obtain that
det (H+1) > det (H))
[+ k Σ
|| H,1
> det (Hi)
(1+
n max ( leS.
veS.
49

---

Since À > 1, for all t > 1 we have max || H.
< Ellžeollz & k. We then reach the
conclusion the same manner:
2
max ES
H
K
log
1 max iES.
[
2
det(Hs+1)
log
dot(HH))
==1
2
(de((H)+1)
log
det(HH1)
2
(Ir(H+1)
1 1+ (1+ dd
dloog
$ dlog
dA
This proves the second inequality.
I Proof of Proposition
I
L1 Main Proof of Proposition
Proof of Proposition 7 We construct the parameters and features in the same way as in Section D.I Recall that, by Proposition D.1, it is sufficient to bound Eiss p(i]S" wv) - Eies, p(i]S wy). We denote Ug as the unique U Vaj4 in Sy. We define a function μ R [o, 1] such that for
K exp(z) any R. pl2) vo+ exp(s) Since all items in S (and in S2) are identical, we express Eies' p(i]S*, wv) (and Exes, P(i)S wy)) as follows:
K Kexp(xTwy)
Σ pi|s"" wv) i
v0 + exp(x,.vv) u(alwv);
_ K Kexp(x] wv)
Σ pils wv) WD + exp(x1 Ve
G. wv) u(ab wv).
Given wy. we define Kt (wv) :- Eies Sr(is wv (OOSS" w Since the context vectors {zn} are constructed to be invariant across rounds f, k((wv) is also independent of f, i.e., ki(w)) = 1G7 (wv). Therefore, omit the index for simplicity. Note that, in instance construction, k* <"(w)) p (z=Twv) (1 m(z[wv)) ((zTTv) Wv).
We hypothesize that for all V Vaja, the regret is dominated by dyf (WV).. If this assump- tion does not hold, then by definition, there exists some V Vaja such that Ey [Reg, (wv)]
Q (d (wv) thereby completing the proof.
Hypothesis. There exists a constant C > 0 such that:
Ey [Regr(wy)) & C d (WV)T, VV E Vaja-
(1.1)
Additionally, we set w argmaxwy xn (Wv), thus, we have n² 13 k=(w") maxwy 18 (Wv).
To establish an instance-dependent lower bound for u(zTwv) u(IF wv). we use the following lemma in place of Lemma D.I
Lemma I.1. Suppose 1/,1/d// d) and define 5 = d/4 - LÜ Vl.
Then, have
k² <Wv) de
u(xTwv) - M(xTT wv) 2
3 Va
For any j V, define random variables Mr = D l E Ú.}. Then, by Lemma [.1 V Vaja. we get
for all
Ey Σ p(is wv) - r(]Se wv) x*(wv) 3
dT
Ev [M]]]
(1.2)
Vd
S
jeV
50

---

Additionally, define v00)
{V Vaja : j E Vj and Vaja-1 (V s [d]
V d/4 -
By averaging both sides of Equation L.2 similar to that in the proof of Theorem we get
with respect to all Vaja. and by following reasoning
Σ
By Σ p(i wv) -
Σ p(ilSe, wv)
Vala
VeVara
K** (wv)
e
dT
max VEVa/4
Σ
(1.3)
vd
6
WVV
For simplicity, let Py and Q P Prult. Then, we can bound the term in (I.3 for any V E Va/4-1.
EvoGilAM
EVIMA
[p[M,] - Bol
&
Σ t. PLM; CHIM, =t] t-
<T ||- QITv ET VV2 KL(PIQ).
(I.4)
where |P - Q1 SupA (P()) Q(A)) I is the total variation distance between P and Q. (L(PIIQ) = [(log P the Kullback-Leibler (KL) divergence between P and Q, and the last inequality holds by Pinsker's inequality. We can derive the instance-dependent bound for the KL divergence term in (I.4) by the following lemma:
Lemma 1.2. For any V E Vana-1 and j E [d]. there exists positive constant CKI. >> O such that
Σ KT.(PVlQQUC)) & CKL e (n"(wv))
Plugging 1.4
into L.3 we get
1
Σ Ey
Σ
- Σ p(ilSs.
Vajul VEVaN
IES
ieS.
K (Wv)
é
dT
T
(L((P(Q)
3
Vd
6
R² (Wv)
dT
1 d
Tvd.
1 KL(PIIQ)
3
Vd
6
Kat (wv)
dT
1 / CRI. (xx((w))
Tvd
V
3
Vd
where the second inequality is due to the Cauchy-Schwartz inequality, and the last inequality is by Lemma 1.2
By setting
72Cki )TT have
d
1
Σ Ey P(iss"
[[i] - Σ
p(i) wv)
Var1
VeVai4
R² (Wv)
d
dT
3
Vd
72CKL k*(wy)T
12
Ω dv n² (Wv)T)
Recall that by construction, K² complete the proof of Proposition
maxwy 1²" (WWv. Thus, by taking the maximum over wy, we
0
51

---

1.2
Proofs of Lemmas for Proposition 1
I.2.1
Proof of Lemmal
.
Proof of Lemma L. For simplicity, let r zv and T0, Then, by the mean value theorem, we
have
p(x
wv) (()
pu( wv)
(x wy o(0 - x)) [w]]) (xc 2) wy
ju(x" (()
(x (x-5) wv
1 [ Twy]
A wv)
(xr ()) Wv
(Wv)
(x - 8) T wv
(wv) òe
Vd
where in the first equality, & is the convex combination of x and á, the first inequality holds by Lemma [.3 the second inequality holds by the bounded assumption (Assumption T. and the last
inequality holds by the definition of 5 d/4 U o VI.
1.2.2 Proof of Lemma I.2
Proof of Lemma 1.2 Consider fixed round t, an assortment S, and the set U. Let U U. Define mj(S,) = Ex 1(j UY/K, which captures the average presence of j E U across the
K expl= wyoral Then, K exp(z]wwy) and g to exp(= wy assortment S. For simplicity, we denote p wotk exp(:////y
we get
KL (Pv(18)))P x 2 (
x² (Bernoulli (p) Bernoulli (q))
9)²
(p-9)² q)
1-
(p -22
q(1 -q)
(u(IT.wv) u(xTTwoUn)))
MaTTwoOD)
(M(TTwro)) 2 (cTwvot) (x) (wV -wv
where in the first inequality, we used KL x² (Tsybakov (50]. Chapter 2), where x² is chi-square divergence, the second equality holds by the expression of the chi-square divergence for Bernoulli random variables, and the last equality holds by the mean value theorem, where Wy,j is convex combination of wy and wyud)- Then, by Lemma L.4 we can further bound the last term as follows:
KL (Pv(1)))IP
< W
(wr (wwrswwo
(ot (wv wr
< we 3/18 (XT (WV - wV
jaz we)e (IU (wV - -wo 2
where the second-to-the last inequality holds based on the assumption that d > 4. and the last inequality holds since mS, & 1.
52

---

Now, let us consider t varying over the round t E [T]. Then, we obtain
T
(L(Py)1Qvun))
Σ
Σ
Ev
KL
(Pr((13))PPvoss)
j=1t=1
2²
d
1/4
Ey [ wv) my my((s))
d
iM wv) Σ mm,(5s) )
1/4
By
d
==1
1/4
Ev
cl(z)) wv)
4
e²
2/4
(M(xTwy)T + Ey (weg)((v))
4
e²
2/4
(m (w'(w)) + Ev [Regr (wv))
4
2² (
CKL
2
the equality follows from the chain rule of relative entropy (cf. Exercise 14.11 of Lattimore and Szepesvári (32)). the second inequality holds because Σ (S,) & á. second-to-the last in- equality holds by Lemma I.5 and the last inequality holds by the hypothesis (Equation (IT) with CKL O.
Furthermore, by the definition of (Assumption 2 we know that 1²* (wv) τ. Hence, given the assumption that T > d'jn 3/ d'/is" (f//"((v))) (Wv), we derive that
(L(Pv)QQ & OKL -xx
which concludes the proof.
I.3 Technical Lemmas for Proposition]]
Lemma 1.3 (Lemma 7 of Abeille al. (4). Let f be strictly increasing function such that 1f < and let be any bounded interval of R. Then, for all 21, 22 E Z:
Sh f u 21)) do 3
i(=)
for (21,
1 |21 - z2!
Lemma 1.4 (Lemma 9 of Abeille al. 4). Let be strictly increasing function such that I.A| & j. and let Z be any bounded interval of RR. Then, for all 21, E Z:
f(22) exp(-1zg 21)) f(2)) < f(zz) exp(122 21)).
Lemma 1.5 (Lemma 11 of Perivier and Goyal 44
Let K = Eies; Pe(i w (') w*).
Then, we have
T
ΣΣ w")ps w*) <
k + Regy(w")).
les.
J Proof of Proposition
In this section, we provide the proof of Proposition proof.
We introduce useful lemmas support the
53

---

Lemma J.1 (Theorem 4 of Tran-Dinh et al. 49 Let f: /:R. R - R be cofooooaoo function and let æ, E dom(f), then:
My f v
Proof of Proposition
We begin the proof with Equation E..2) from the proof of Theorem
T
T
vQ(u)) - uz) & (6)
Σ Σ Se
p w")ps w*) W")loulll
(J.1)
We then divide the total rounds into two disjoint sets, J1 and J2, such that J1 U = [7]. Specifically, let J1 = {t E [T] Exes, Pr(i]Se, w") (")p:(0SSs w*) >> Σves, Se Wr+1 Wr+1)p((0f) (0 W and
J2 [T]. For a better presentation, we also define that:
(5; w)
Σ Pe (OIS, w)llslll LE
Then, rewrite the right-hand side of J.1
follows:
T
2
Σ Σ
Se w
(p:ss w w")][==ill
ieS,
=08r(0)
Σ go(S w")
23r(())
Σ
gr(S:: + 23r(6) teJs
Σ
ge(Sii w")
thh
To bound EreJ, Ie (Se w*), , by the mean value theorem, we get
Σ g((S::")) = Σ TEJi
((S w(+1) +
Σ Vw. TEJ,
(. we+1),
(J.2)
seji
where W, the convex combination and W The first term of J.2 can be bound by
Σ (S w IEJ.
Σ Prii (e W(t1). IeJi ieS,
Σ
Σ (i ( We+1)ll
LEJi iES.
Σ Σ (i)lS,,."'pp(0)5s.. w-) (va) AEJ, iES,
+ Regr(wt) ((V)(
(J.3)
where the second-to-the last inequality holds by the definition of Jn and the elliptical potential lemma (Lemmal E.2 and the last inequality holds by the following Lemma:
54

---

Moreover, the second term of U.2 can be bounded as follows:
WSer We) (w" w(+1)
Σ Pe(O we)
Σ
pe (i] wo) We+1)|
ieSt
(0 Wr)
Σ
(r we) H,
Σ
Pr(ilSe, We) - wet1)
ieS.
jeSz
< (r) Σ Σ reJı iES,
Pe(i] w. well= + +3r(1)
Σ
Σ
Pe(iiSe. we)l H7)
teji
Jes
& (T())
Σ
max #es:
| 1 H.
+ 223((8)
Σ
max ieS,
Fzsl m1;)
tEJi
tEJ,
< (8)
Σ
max K.
2 H. - (d)22k))
(J.4)
where the first inequality holds by Lemmal T and the last inequality holds by Lemma E.2 ing (J.3)
Combin-
and J.4. we can bound the term LiEJ, (S1; w*) as follows:
Σ g( w') & Ō teJ.
Va.
Σ
K + Regr + 83.2/
(J.5)
Now, we bound EiE, (S w*). We define H; = AL + Σx= Ce(w)) Recall that (W) = (w( and lg is 3/ seseelf-onnc function (Proposition C.1 Then, by Lemma J.1 get
H, 2 Hie 3322, With this fact, we can now bound the term Σie,, ge (S::
Σ (e w*) E
Σ Σ Je S.
(i(Sss w (prSSSee w*)
Σ
Pr( w*)p:(O|S,, w*) Ie H." i.
Σ
12
K Regr
St
k RegT
c3v2
Σ (((lSS),"')p<(00 ( [o
1=1
1=1 Ve
Vd.
M
Kc + Regr
(J.6)
where the second inequality follows from Lemma I.5
second-to-the last inequality holds because
H, 2 H-e-3/2 and the last inequality is obtained by slight modification of Lemma E.2 with
WI,.... WT w*.
Now, by plugging (_5) and (J66) into J.1 and using the fact that (r) Ö(vV), obtain that
(0) Σ Σ (i w (O,S,, w w*) [[)llll H. - (0(a Σ K (w*) d3//2
Furthermore, by applying the same analysis as in the proof of Theorem in order to bound the second-order term in the Taylor expansion (term (B) in E.I 1), get
Reg, Regr(w") - (((
Σ x Reg,(w*) + d//x
55

---

By solving the above equation, we conclude the proof of Proposition
K
Experiment Details and Additional Results
N-100, K=5, d-5, Uniform
N-100, K-10, d- Uniform
N-100, K-15, d-5, Uniform
Tim (Secondee
Dalcondii
0.23
0.22
6.32
0.22
500
1200
1203
3000
2300
3003
500
1000
1500
2000
2300
3002
0.08
500
1000
2507
2000
2500
3002
Round
N-100, K-5, d-5, Non-Uniform R
N-10D, K- 10, d-5, Non-Uniform R
N- 100, K- 15, d-5, Non-Uniform R
Uime (haconet)
0.45
Now (oskarnss)
0.42
0:42
0.35
6:35
0.35
3200
1597
2010
2500
3007
1000
1507
2010
2500
3007
500
1.000
3507
2020
25.00
3003
Figure K.1: Runtime per round under uniform rewards (first row) and non-uniform rewards (second
row).
N=100, K=S, d=5,, Uniform R, 0=1.0
1=100, K=10, d=s,, Uniform R, v 0=2.0
N=100, K=15, d=S, Uniferm R, 0=3.0
Curusatve Regeet
Luruattve Roarot
22
22
22-
UZB-MAN
1507
2300
Round
Figure K.2: Cumulative regret under uniform rewards with vo O(K).
For each instance, sample the true parameter w from uniform distribution in 1-1/ 1/Va For the context features THis we sample each my; independently and identically distributed (i.i.d.) from a multivariate Gaussian distribution (O0,, Ia) and clip it to range [-1/v 1/Val Therefore, we ensure that |w & 1 and |atas l & satisfying Assumption 1 For each experimental configuration, we conducted 20 independent runs for each instance and reported the average cumulative regret (Figure 1 and runtime per round (Figure K.I) for each algorithm. The error bars in Figure [ and K.2 represent the standard deviations (1 (1-sigma error). We have omitted the error bars in Figure K. because they minimal.
In the uniform reward setting where Tu = 1. the combinatorial optimization step to select the assortment simply involves sorting items by their utility estimate. In contrast, in the non-uniform reward setting, rewards are sampled from uniform distribution each round, i.c., Tts ~ Unif(O, 1). For combinatorial optimization in this setting, solve equivalent linear programming (LP) problem that is solvable in polynomial-tinn 6226R CPU @ 2.90GHz (16 cores).
47 21
The experiments are run on Xeon(R) Gold
Figure K. presents additional empirical results on runtime per round. Our algorithm OFU-MNL+ demonstrates constant computation cost for each round, while the other algorithms exhibit linear dependence on also noteworthy that the runtime for uniform rewards is approximately 10 times faster than that for non-uniform rewards. This difference arises because use linear
56

---

programming (LP) optimization for assortment selection in the non-uniform reward setting, which is more computationally intensive.
Furthermore, Figure K.2 illustrates the cumulative regrets the proposed algorithm compared to other baseline algorithms under uniform rewards with Uo K/5. Since vo is proportional to K, increase in K does not improve the regret. This observation is also consistent with our theoretical results.
L Technical Errors in Agrawal al. 5
In this section, we discuss the technical errors in Agrawal et al. S errors: There are mainly two significant errors:
There are two main significant
1. Equation (16).
01, 0', = (x(X),00) (000))(,(3333333 (x(33,
(L.1)
where Xs, is design matrix whose columns are the attribute vectors 24, of the items in the assortment Sy and (x( S. 0) P,( 0).
It appears that the authors may have intended to derive this equation using a first-order exact Taylor expansion. However, in MNL bandits, this equation generally does not hold. Consider counterexample where Zυi = O, Tıj * O for j * i, and 0 * 0g. Then, the left-hand side of (L.I) equals to 0 (since Zng 0), but the right-hand side of LLII not 0, because the denominators of each (X, S, (*) and μ4 (X3, 8,) differ. This equation only holds in special cases, such as when
K 1, which corresponds the logistic bandit case. Equation (16) in Agrawal al. [5] serves as the foundation for the entire proof in their paper. Consequently, all subsequent results derived from it are also incorrect.
2. Cauchy-Schward inequality in the regret analysis (Page 46)
When using the Cauchy-Schward inequality on the regret before applying the elliptical potential lemma, they indeed incur additional K factor:
Σ min
Σ |
min Σ
Hence, their regret should actually be Ödv KT + dR/R), which is worse than the result in our Theorem (upper bound under uniform rewards) by factor of K.
M Limitations
To determine the optimistic assortment in line 5 of Algorithm I we must calculate the optimistic utility Oie for each item [N]. Consequently, the computational cost for each round scales polynomially with N, the number of items. If N is very large, infinite, our proposed algorithm becomes intractable. It important to that much of the existing literature on contextual bandits 2 10 24 20 6 16 40 41 also requires enumerating all items to select the item for each round.
57

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Abstract and Section 1
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
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 to 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: Section Min Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create 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 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, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't '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]
58

---

Justification:
Assumption and 2
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be 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 affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Secion
7 and Section
Guidelines:
The answer NA means that the paper does not include experiments.
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 a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS 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) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either 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 to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers 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?
59

---

Answer: [No]
Justification: We have included the code in the supplementary material. After our paper is accepted, will provide open access to the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is 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 to reproduce the results. See the NeurlPS code and data submission guidelines (https
ssiicyolicy) 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, preserve anonymity, the authors should release anonymized versions (if applicable).
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
Question: 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?
Answer: [Yes]
Justification: Section and Section Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of 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, or as 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: [Yes]
Justification: Figure I and K.2
We omitted the error bars in Figure K.I because they are too
minimal to be significant.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are 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 capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall 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).
60

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. 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 are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in 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 reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section
K
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs 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 Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:p/pw..eaaoo.oooo/ooo//o/aaa
Answer: [Yes]
Justification:
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations 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: impacts.
This paper focuses on theoretical results and therefore does not discuss societal
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 or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
61

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No risks.
Guidelines:
The answer NA means that the paper poses 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 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does 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 is used and, if possible, include URL.
The name of the license (c.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 use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
62

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part 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 an 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)?
Answer: [NA]
Justification: This 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.
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 Ethics, 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 or Equivalent for Research with Human Subjects
Question: 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not 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 expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
63


Reviews:
[{"review_id": "M9YPZzBsjm", "reviewer": "Reviewer_bygC", "summary": "The authors consider the problem of sequentially picking assortments of items in an online manner over a horizon of $T$ rounds, where a user then selects from the items or not according to a multinomial logit model with a fixed unknown preference vector.  The items are represented as (known) feature vectors which can change adversarially from round to round.  The authors prove tighter cumulative regret lower bounds for both uniform and non-uniform cases and propose an algorithm with matching upper bounds.  The authors account for the probability of a user not choosing from the given options in the bounds.  The authors also run experiments to compare their algorithm to baselines.", "questions": "(some questions are included above in comments made in “Weaknesses”)", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "### Major\n- Improved lower bounds for contextual MNL bandits in the uniform-reward setting, accounting for the impact of the probability of the null action.\n- improved lower bounds also in the non-uniform reward setting.\n- A tractable algorithm is proposed with matching regret upper bounds for both uniform and non-uniform reward setting\n\n### Minor\n- The authors include experiments for non-uniform rewards, showing significant improvements in both run-time and cumulative regret for included baselines.\n- Good discussions and remarks on effects of problem setup, such as $v_0$ and whether rewards are uniform or not on regret bounds, and relations with prior works (among those discussed to some length). \n- Overall I found the writing to be good.  Table 1 is helpful.", "weaknesses": "### Minor\n1. Zhang and Luo “Contextual Multinomial Logit Bandits with General Value Functions” [48] is only mentioned once in line 128 in a sentence about past works claiming $K$-independent regret lower bounds while not accounting for $v_0$ (with the next sentence pointing out issue that several lower bounds used $v_0 = K$.  However, in [48] they propose algorithms and show regret bounds for a harder problem (adversarial contexts and adversarial rewards and for more general settings than MNL models) that avoid $\\kappa$ dependence in the leading term, though for the simpler problem studied in the current paper may have loose assortment size $K$ dependence.  In [48] it looks to me like they consider $v_0=1$ not $v_0=K$ as implied by the current paper.  Thus, while [48] is cited, to me it seems to be improperly cited and the results should be more thoroughly discussed, and unless some justification should be included in Table 1.\n2. State of the art upper bounds for non-contextual MNL are not discussed.   Non-contextual MNL lower bounds are included in Table 1 and discussed, but unless I overlooked it did not see anything on upper bounds, even from papers like Agrawal et al. (2019) “MNL-bandit...” [8] that were discussed for lower bounds.  (Or do the contextual upper bounds with $d=N$ recover them in current state of the art?)\n3. Agrawal et al. “A tractable ..” 2023 [5] is cited in a few places regarding the problem setting (like in line 186 for assumptions 1 and 2, line 282 for $v_0$, …), but not included in Table 1 or discussed in detail.  They achieve improved regret upper bound dependence on $\\kappa$ from prior works using a reportedly tractable algorithm.  Agrawal et al. [5] consider a (contextual) combinatorial assortment problem using an MNL model with adversarial contexts and uniform rewards and $v_0 = 1$. \n4. Choi et al. “Cascading Contextual Assortment Bandits” in NeurIPS 2023 is not cited.  How would their results compare?  Their regret upper bound (specialized to the non-cascading setting you consider) looks competitive for $v_0=1$ and uniform reward setting.  Another cascading assortment paper by Cao and Sun “Tiered Assortment: Optimization and Online Learning” in Management Science is also not cited, though they acknowledge in their Remark 2 that in the special case of a single tier, their result matches Agrawal et al. (2019) “MNL-bandit...” [8].  \n5. The authors consider the parameter vector $\\textbf{w}$ bounded by $1$ instead of bounded by a known constant $S$ like in previous works (such as Agrawal et al. 2023 [5] and Lee et al. 2024 [32]).  As pointed out by Leet et al. 2024 [32], “These quantities [$\\kappa$] can scale exponentially in S in the worst-case (Faury et al., 2020).” How would the results be impacted accounting for such a known bound instead of setting it to 1?\n6. A clearer discussion on the computational complexity of the methods listed as “intractable” (in particular Goyal and Perivier 2022 [24]) would be better, both worst-case and (if not included in experiments) conjecture whether where they would have been in Fig. I.1 (eg even for those instances would it have been so slow as to be off the charts?).  \n\n### Very Minor\n- [24] cites an arxiv version of a NeurIPS 2022 paper", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your insightful and valuable feedback. As we start our discussition, we first would like to ask for your patience for our lengthy responses. We have much to share as we have genuinely appreciated your feedback and look forward to our discussion with you! We will ensure that all the following discussions are included in our final version.\n\n---\n### **Regading Zhang and Luo (2024)**\nFirst, we would like to clarify that **our setting also considers adversarial contexts and adversarial rewards.** In our work, the term \"the non-uniform rewards\" is equivalent to the adversarial rewards. Thus, apart from the fact that Zhang and Luo (2024) [48] use a \"general value function\", other problem settings in [48] are not necessarily harder than ours.\n\nEven though their tightest regret bound (Corollary 17) $\\tilde{\\mathcal{O}}(K^{2.5}\\sqrt{dNT})$ avoids dependence on $\\kappa$ based on the general value function, their regret still scales with $K$ and the number of items $N$. Moreover, as they mentioned in their paper, there is no efficient way to implement the algorithm.\n\nTo clarify, in Line 128, our point in citing [48] was to **emphasize that previous studies' oversight of $v_0$'s impact on regret lower bounds has caused substantial confusion in the field.** They stated that $\\Omega(\\sqrt{NT})$ in the non-contextual setting is optimal; however, this claim only holds true when $v_0=\\Theta(K)$. \n\n---\n### **Upper bounds for non-contextual MNL bandits**\nWe plan to discuss the upper bounds in the non-contextual setting to clearly illustrate how previous studies have derived regret bounds under varying conditions, such as different $v_0$ values and reward structures. For instance, Agrawal et al. (2019) achieved an  $\\tilde{\\mathcal{O}}(\\sqrt{NT})$ upper bound with \"$v_0=1$ and non-uniform rewards\". However, the known tightest lower bound, $\\Omega(\\sqrt{NT})$, was proven under settings of \"$v_0=K$ and uniform rewards\".\n\n---\n### **Comparison to Agrawal et al. (2023)**\nIn fact, their paper contains **significant technical errors** (see **Section A in the comments below**), rendering a direct comparison to our work meaningless. This is the main reason we initially chose not to compare our results with theirs. \n\nEven if all errors were corrected, our result (Theorem 2) still shows an **improvement over theirs in terms of $K$.** Agrawal et al. (2023) considered a **uniform rewards setting** (with $v_0=1$) and achieved a regret of $\\tilde{\\mathcal{O}}(d\\sqrt{T} + d^2/\\kappa)$. However, the corrected regret should be $\\tilde{\\mathcal{O}}(d\\sqrt{KT} + d^2/\\kappa)$.\n\n---\n### **Comparison to cascading assortment problems**\nRecently, both works have considered the cascading assortment bandit problem, which encompasses the MNL bandit problem as a special case where the cascading length is $1$. However, these works do not encompass our results for the following reasons.\n* **vs Choi et al. (2023)**: They consider **uniform rewards**, and achieve a regret upper bound of $\\tilde{\\mathcal{O}}(d\\sqrt{T})$, which avoids dependence on both the cascading length and $\\kappa$ in the leading term. When the cascading length is $1$, our result (Theorem 2) **improves upon theirs by a factor of $\\sqrt{K}$**. Moreover, their computation cost per round is $\\mathcal{O}(t)$ since they employ MLE to estimate the parameter. \n* **vs Cao and Sun (2023)**: They consider **non-uniform rewards**, and achieve a regret upper bound of $\\tilde{\\mathcal{O}}(h^2d\\sqrt{MT})$, where $M$ is the cascading length and $h \\geq \\frac{p(i \\mid S, \\mathbf{w})}{p(i \\mid S, \\mathbf{w'})}$ for all $\\mathbf{w}, \\mathbf{w}' \\in \\mathcal{W}$, $S\\in \\mathcal{S}$, and $i \\in S \\cup \\{0\\}$. However, their regret bound still suffers from a **harmful dependence on $h^2$, which can be exponentially large**. \n\n---\n### **What happens if $\\\\|\\mathbf{w}\\\\|_2 \\leq B$? (+ problem-dependent bounds)**\nWhen $\\\\|\\mathbf{w}\\\\|_2 \\leq B$ (we use $B$ instead of $S$ to avoid notational overlap), the confidence bound $\\beta_t(\\delta)$ is $\\tilde{\\mathcal{O}}(B \\sqrt{d})$. Consequently, the **regret upper bounds** are as follows:\n- **Uniform rewards**: $\\tilde{\\mathcal{O}}(B e^{B} \\frac{\\sqrt{v_0 K}}{v_0 + K} d \\sqrt{T})$. It's important to note that one of our main goals is to explicitly demonstrate the regret depends on $K$ and $v_0$. In deriving such a result, the dependence on  $e^B$ is unavoidable to our best knowledge. Note that for the instance-dependent regret, the regret bound does not depend on $e^B$ (see below).\n- **Non-uniform rewards**: $\\tilde{\\mathcal{O}}(B d \\sqrt{T})$.   \n\nAnd the regret lower bounds remain the same, because we can always construct an instance where  $\\\\| \\mathbf{w}^\\star\\\\|_2 \\leq 1$ even if $B \\gg 1$. Note that a small norm of $\\mathbf{w}^\\star$ typically indicates a more challenging instance, as it becomes harder to identify the optimal arm. Overall, **our upper and lower bounds in terms of $K$, $d$ and $T$ (and $v_0$) are still tight**, maintaining the (near) minimax optimality in terms of those problem parameters, which is our main focus.\n\nMoreover (as per other reviewers' request), it turns that **instance-dependent upper and lower bounds** under uniform rewards (without dependence on $e^B$) are achievable. By making some modifications to previous results, we can easily achieve this. See **Section B in the comments below** for the proofs.\n\n---\n### **Computational complexity of Goyal and Perivier (2022)**\nThe computational bottleneck of Goyal and Perivier (2022) [24] is to find an optimistic parameter $\\tilde{\\theta}\\_t = \\arg\\max\\_{\\theta \\in \\mathcal{C}(\\delta)} x\\_{ti}^\\top \\theta$. However, since the confidence set $\\mathcal{C}(\\delta)$ is non-convex, computing $\\tilde{\\theta}_t$ is extremely expensive,  and the worst-case cost is not well-defined.\nA possible solution could be a convex relaxation, as suggested by Proposition 3 in Abeille et al. (2021) [4], though exploring this is beyond the scope of our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q3tDDdBKlN", "reviewer": "Reviewer_8Ks7", "summary": "The paper studies the contextual multinomial logit bandit problem. In this problem a learner interacts with the environment over a sequence of rounds. At each round, the learner receives features for $N$ arms and decides to select up-to $K$ of them (called an assortment) and play them. The environment might select one of these arms with a probability determined by a multinomial distribution and the learner receives a reward for the selected arm. The goal is to select the optimal assortment at each round that minimizes the cumulative regret of the algorithm.\n\nThe authors design algorithms for cases when the rewards are uniform (same for each arm) and non-uniform. They also provide matching lower bounds (for large enough $T$). Finally numerical experiments are performed to demonstrate the practical performance of the algorithm.", "questions": "Is the problem dependent constant $\\kappa$ in line 189 same as the non-linearity $\\kappa$ defined in prior work for logistic bandits (See [4,20,21]). It seems to be slightly differently defined here so I was curious to see if it meant the same at least in the logistic case.", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors do a great job of explaining the problem statement and prior work and position their work appropriately. I believe this is a very important direction since bandit algorithms have recently started getting popular in practical settings where the assumption of linear rewards no longer holds. Getting optimal regret guarantees for such non-linear models has gained good attention recently and the paper contributes to this in a clear non-trivial way.\n\nIt's great to see that the authors prove matching lower bounds for the uniform case (for general $v_0$) and for non-uniform case (for bounded $v_0$). This adds further credibility to their algorithm and the upper bound.", "weaknesses": "I am not an expert on the MNL problem but I was wondering if the algorithm offers anything new to the logistic bandit setting. Recently lot of work has happened in obtaining computationally efficient algorithms with optimal regret (independent of a problem non-linearity parameter $\\kappa$). It would be good to see if anything new can be said about that setting using the results in this paper. Also, empirical comparisons on both regret and time complexity (for logistic bandit i.e. K=1 as well as larger K) can be a good addition to the paper.\n\nMinor comment - Typo on line 183. The correct definition should be $S_t^\\star = \\arg\\max_{S\\in \\mathcal{S}} R_t(S, w^\\star)$.\n\nMy expertise in this topic is limited and I will wait to see what the other reviewers think as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for acknowledging the value of our \bwork and providing a positive evaluation. We will address your questions below and make improvements to our paper based on your suggestions.\n\n---\n### **Anything new to the logistic bandit** \n\nThere are interesting points that can be said about the logistic bandit setting: \n\n   **1. The MNL bandit is better than the logistic bandit (under uniform rewards).**  \n    According to Theorem 2 in our paper, a large $K$ can be beneficial under uniform rewards. This suggests that in recommendation systems, it is advantageous to recommend multiple items (MNL bandit) rather than just a single item (logistic bandit). This aligns with the intuition that offering multiple items allows us to gather more information from user feedback. However, in real-world scenarios, offering a large assortment might lead to user fatigue. It would be interesting for future research to consider this user fatigue and determine an appropriate size of the assortment $K$.\n\n   **2. As value of the utility for outside option $v_0$ increases, both the upper and lower bounds of regret for the logistic bandit decrease.**  \nWhen $K=1$, our setting simplifies to the logistic bandit scenario. In this case, the upper and lower bounds are $\\tilde{\\mathcal{O}}(d\\sqrt{T/v_0})$ and $\\Omega(d\\sqrt{T/v_0})$ respectively. This highlights an interesting aspect about how the value of $v_0$ influences the regrets in the logistic bandit.\n\n---\n### **Additional empirical comparison**\n\nFollowing your suggestion, we have conducted additional experiments for the logistic bandit case  (K=1) and  cases with larger $K$ ($K=20, 30$). See the \"global\" response above. These additional results also corroborate our theoretical claims. Particularly, under uniform rewards, we observed that regret decreases as $K$ increases, aligning with Theorems 1 and 2. In contrast, under non-uniform rewards, regret remains unchanged regardless of changes in $K$, consistent with Theorems 3 and 4.\n\nWe are pleased to provide these additional results that further substantiate the claims in our paper. Thank you very much!\n\n---\n### **Typo**\nThank you very much for identifying the typo. We will make the necessary correction and ensure it is reflected in the final version of the paper. Your attention to detail is greatly appreciated.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6bQ4zJgXDT", "reviewer": "Reviewer_FJtD", "summary": "The paper closes the gap between upper and lower bounds for contextual MNL bandits over various scenarios, including for varying $v_0$ and uniform/non-uniform rewards. Furthermore, the paper proposes a computationally efficient algorithm that achieves such nearly optimal upper bound, which is validated numerically as well.", "questions": "**Questions**\n- In Remark 2, the authors mention that the optimistic bonus incurs exponential computational cost. But, disregarding the computational complexity, is there any advantage of doing so from the statistical/theoretical perspective? Somewhat related, although the authors have avoided the MLE-based approach for computational complexity, does using MLE with the intuitions provided here could lead to better regret guarantees in other dependencies?\n- In the regret upper bounds, there is a transient term $\\frac{d^2}{\\kappa}$. Is this an artifact of the proof? Or is there a hidden warmup phase done implicitly by the OFU-MNL+? Then, if one is okay with incurring such transient terms anyhow, is there potential for doing even better through forced exploration-type approaches (e.g., [1,2] for logistic bandits)?\n- Although the $1$-boundedness of $w^\\star$ is standard in MNL bandits, if we relax this to $B$-boundedness for some $B > 0$, then does this imply that $\\kappa$ may scale exponentially in $B$, like logistic bandits [3]?\n- Can the lower bound in Theorem 1 be written as a local minimax lower bound (e.g., Theorem 2 of [3]) centered around a specific instance? This seems like a better presentation than the current representation, which seems to be a generic minimax, where the max is over all possible problem instances. Also, the lower-bound construction, although inspired by prior works on MNL bandits, resembles a bit of [3] as well. I encourage the authors to check Appendix D of [3], especially the Averaging Hammer technique, and if applicable, include some discussions on this as well. Such instance-specific local minimax lower bound may make the result stronger.\n\n\n**Suggestions**\n- In the main text, for all the theorem statements, please include (hyper)ref for where the full proof is in the Appendix.\n- Although a bit complex, for practitioners, it might be beneficial to include the precise constants for the $\\beta_t(\\delta)$ in Lemma 1 (or point to the Appendix with the constants). A follow-up question: for the experiments, do the authors use the precise parameter as specified theoretically?\n- Might be beneficial to move the problem setting to earlier part of the paper, but not too sure here.\n\n\n[1] https://arxiv.org/abs/2404.06831\n\n[2] https://arxiv.org/abs/2202.02407\n\n[3] https://proceedings.mlr.press/v130/abeille21a.html", "limitations": "Yes", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Clearly, very well-written\n- Clear-cut contributions that close all the gaps remaining in the contextual MNL bandits\n- Numerical verification\n- Various technical contributions, mainly for the analysis but also for the algorithm design (Eqn. (6))", "weaknesses": "- Nothing noticeable; see questions", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive evaluation of our paper and for your insightful and valuable feedback. Each question you raised is an intriguing research topic, shedding light on new areas for future study.\n\n---\n### **Advantage of optimistic bonus**\n\nFirst, we want to clarify that the simple adaptation of Zhang and Sugiyama [49] to our method incurs \"exponential computational cost\" -- this is NOT an inherent drawback of our method. To the best of our knowledge, the adaptation of an optimistic bonus, as done in Zhang and Sugiyama [49], to our method does not provide any statistical advantage, despite the exponential computation cost.\n\n---\n### **Does using MLE with the intuitions provided here could lead to better regret guarantees in other dependencies?**\n\nTo the best of our knowledge, given that our regret upper bound is minimax optimal (up to logarithmic factors), we believe that the use of MLE may not improve our regret bound polynomially. However, it might be possible to affect the bound logarithmically, which could be of future interest.\n\n---\n### **Regarding $d^2/\\kappa$ and the potential for forced exploration-type approaches**\n\nThe term $d^2/\\kappa$ is an \"artifact\" of the proof, resulting from the second-order Taylor expansion of the regret. We do not have any warm-up phase or forced exploration in the algorithm.\nHence, we are not sure whether forced exploration-type approaches can be beneficial.\nBased on your feedback, we considered adding an initial/intermediate forced-sampling step, but we do not believe the regret can be improved (in our current analysis). This would be an interesting area for future work.\n\n---\n### **If we relax the bound of $\\\\|\\mathbf{w}^\\star\\\\|_2$ to $B$-boundedness for some $B>0$, then does this imply that $\\kappa$ may scale exponentially in $B$, like logistic bandits [3]?**\n\nYes, by the deifinition, $\\kappa$ is affected by $B$. Specficially, $1/\\kappa$ (which appears in the lower-order term in our upper bounds) scales with $\\exp(B)$.\n\n---\n### **Instance-specific local minimax lower bound**\n\nAs you suggested, we have checked the Averaging Hammer technique and found that an instance-dependent lower bound is indeed achievable. Thank you very much for your valuable feedback. Your insights have greatly strengthened our paper!\n\nWe can achieve a regret lower bound of $\\Omega(d\\sqrt{\\kappa^\\star T})$ by applying Theorem 2 from Abeille et al. (2021), where $\\kappa^\\star := \\sum_{i \\in S^\\star} p(i \\mid S^\\star, \\mathbf{w}^\\star)  p(0 \\mid S^\\star, \\mathbf{w}^\\star)$.\n\n\nIn the proof of Theorem 1, both the optimal assortment $S^\\star$ and an alternative assortment $\\tilde{S}_t$ (only has feature vectors that maximizes the utility in $S_t$) have the same feature vectors for each assortment. Let $S^\\star = \\\\{x,\\dots,x \\\\}$ and $\\tilde{S}_t = \\\\{\\hat{x}, \\dots, \\hat{x}\\\\}$. Then, by Proposition D.1, we have\n\n>$\n\\sum_{i \\in S^\\star} p(i \\mid S^\\star, \\mathbf{w}^\\star)  -  \\sum_{i \\in S_t} p (i \\mid S_t, \\mathbf{w}^\\star)\n\\geq \\sum_{i \\in S^\\star} p(i \\mid S^\\star, \\mathbf{w}^\\star)  -  \\sum_{i \\in \\tilde{S}_t} p (i \\mid \\tilde{S}_t, \\mathbf{w}^\\star)\n=: f(x;\\mathbf{w}^\\star) - f(\\hat{x};\\mathbf{w}^\\star).\n$\n\nHere, $f(x;\\mathbf{w}^\\star) = \\frac{ K\\exp(x^\\top\\mathbf{w}^\\star ) }{v_0 + K \\exp(x^\\top \\mathbf{w}^\\star)}$ maps from $\\mathbb{R}^d$ to $\\mathbb{R}$. Since the input to the function $f$ is a single vector $x$, $f$ can be regarded as a logistic function. This characteristic allows us to follow the proof of Theorem 2 from Abeille et al. (2021) [4], resulting in a regret lower bound of $\\Omega(d\\sqrt{\\kappa^\\star T})$. We will include this result in our final paper.\n\n---\n### **Suggestions**\n\nWe appreciate all your suggestions and will incorporate them into the paper as you proposed. \n\nTo answer your additional question about whether we used precise parameters in the experiments: **yes**, we used the exact values.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WvCU3yX5jC", "reviewer": "Reviewer_SF7h", "summary": "This paper studies MNL bandit problem and proposes computationally efficient algorithms in both uniform and non-uniform settings. The authors present lower bounds for these two settings and show their results are minimax optimal up to logarithmic factors.", "questions": "1. Can the proposed algorithms be directly applied to achieve the optimal results for binary logistic bandits? It would be beneficial for the paper to discuss this applicability.\n2. The empirical performance shown in Figure 1 suggests UCB outperforms TS in non-uniform settings, contrary to the fact that TS usually achieves better empirical performance than UCB in the literature. Moreover, though OFU-MNL+ outperforms the two other baselines, all algorithms appear to incur linear regret in specific scenarios (e.g., (N=100, K=10, d=5, Uniform R)). Could the authors provide some intuition for these phenomena?", "limitations": "\\", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper achieves the minimax optimal results for the MNL bandit problem in both uniform and non-uniform settings, contributing new findings to the community.\n2. This paper introduces computationally efficient algorithms that enhance the computational complexity over prior works.\n3. Empirical evidence provided by the authors convincingly demonstrates the effectiveness of the proposed algorithms, strengthening the paper's claims with solid experimental validation.", "weaknesses": "1. My main concern is about the contribution and technical novelty of this paper. From the statistical perspective, the regret for the uniform setting does not advance beyond the results presented in Goyal and Perivier (2021) and the $\\kappa$-independent bound for the non-uniform setting has been achieved in Agrawal et al. (2023) (A comparison with Agrawal et al. (2023) in the table would be beneficial for highlighting any improvement). The main contribution of this paper is the improvement of the computational complexity. However, this enhancement comes from the online parameter estimation, which is almost the same as that in Zhang and Sugiyama (2023), with only minor modifications. As MNL bandits considered in this paper and MLogB bandits are quite similar, this modification is not significant.\n2. The claim that \"This complexity arises because the optimistic revenue...requiring a different analysis\" in Remark 2 seems overstated. The issue of assortment optimization to maximize optimistic revenue has been previously addressed by Oh and Iyengar (2021). The approach in the paper does not deviate from their method, which makes the purported contribution questionable.\n3. The presentation of lower bounds for both settings to demonstrate result optimality is appreciated, yet the inclusion of a problem-dependent lower bound that illustrates the influence of the problem-specific parameter $\\kappa$ would have added significant value, as seen in studies on logistic bandits.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your time to review our paper and your feedback.\nWe would like to clarify some of the possible misunderstandings regarding our main contributions.\nOur main contributions are to establish **the first minimax regret for MNL bandits**, along with providing several **novel insights related to variables such as $v_0$ and reward structures**. We strongly believe that our results significantly advance what have been knwon in the field of MNL bandits. \nWe will address your feedback point by point below. We sincerely hope to clarify any  misunderstandings.\n\n---\n### **Regarding our main contributions**\nOur main contribution is **NOT** the improvement of computational complexity (although it is still an advantage of our proposed method). While we employ the online parameter estimation adapted from Zhang and Sugiyama [47], it is important to note that new analyses based on improved self-concordant-like properties and considering varying assortment sizes are introduced in our work. \n\nWe clearly emphasize that our main constributions are **closing the gap between the upper and lower bounds in contextual MNL bandits for the first time** and **proposing a nearly minmax optimal algorithm**. Additionally, we believe it is a significant and novel insight that the regret: 1) varies depending on the value of $v_0$ and 2) is influenced by the reward structure (uniform versus non-uniform), and 3) can improve as the assortment size $K$ increases under uniform rewards. Our contributions can be summarized as follows:\n\n1) First minimax results in terms of $d,T,K$ and even $v_0$\n2) First proofs demonstrating how regret varies with $v_0$ and reward structure\n3) First lower bound under non-uniform rewards\n4) First tractable $\\kappa$-free uppder bound under non-uniform rewards\n5) Adaptation of the online parameter estimation while maintaining the above regret bound \n\nEach of our results tackles distinct non-trivial challenges, which we have successfully resolved in our paper. For instance, we have enhanced the self-concordance-like properties and the elliptical potential method, and introduced novel \"centralized features\" to prove the upper bound for non-uniform rewards. Please refer to the discussions for each theorem for more details.\n\nFurthermore, our regret bound (Theorem 2) is a **clear improvement** over those presented by Goyal and Perivier (2021) and Agrawal et al. (2023).\n\n* **vs Goyal and Perivier (2021) [24]**: We have improved upon the regret results of Goyal and Perivier (2021) **by a factor of $K$**: reducing it from $\\tilde{\\mathcal{O}}(d\\sqrt{KT} + d^2K^4/\\kappa )$ (let $\\kappa^\\star = \\mathcal{O}(1/K)$ in the leading term) to $\\tilde{\\mathcal{O}}(d\\sqrt{T/K} + d^2/\\kappa )$. This advancement was achieved by enhancing the **self-concordant-like property of the loss function (Proposition C.1)** and refining the **elliptical potential lemma (Lemma E.2)**. Moreover, we significantly improved the regret associated with the transient term, reducing it from $d^2K^4/\\kappa$ to $d^2/\\kappa$, by utilizing an **improved bound for the second derivative of the revenue (Lemma E.3)**. For further details, please refer to the discussion of Theorem 2 in our paper.\n\n* **vs Agrawal et al. (2023) [5]**: In fact, their paper contains **significant technical errors** (refer **Section A in the comments below**), rendering a direct comparison to our work meaningless. This is the main reason we initially chose not to compare our results with theirs. Nevertheless, in response to requests from some reviewers, we will consider including a discussion about this in our camera-ready version. Even if all errors were corrected, our result (Theorem 2) still shows an **improvement over theirs in terms of $K$.** Agrawal et al. (2023) considered a **uniform rewards setting** (with $v_0=1$) and achieved a regret of $\\tilde{\\mathcal{O}}(d\\sqrt{T} + d^2/\\kappa)$. However, the corrected regret should be $\\tilde{\\mathcal{O}}(d\\sqrt{KT} + d^2/\\kappa)$).\n\n---\n### **Remark 2 is intended solely for comparing our setting with that of Zhang and Sugiyama [47].**\nThe purpose of Remark 2 is to **explain** that our setting fundamentally differs from those described by Zhang and Sugiyama [47], necessitating a different analysis. Therefore, this distinction should **NOT** be viewed as a weakness. Again, our main contribution is proving the first minimax results in MNL bandits.\n\n---\n### **Problem-dependent ($\\kappa$) lower bound**\nThe main goal of this paper is to **explicitly show how the values of $K$ and $v_0$ affect the regrets** (both upper and lower bounds). To clearly demonstrate the dependency of regret on these values, we have presented the results in terms of $K$ and $v_0$, rather than  $\\kappa$. \n\nAs per your request, we believe that a problem-dependent lower bound can be easily derived from our intermediate results. In the proof of Theorem 1, both the optimal assortment $S^\\star$ and an alternative assortment $\\tilde{S}_t$ (which only includes feature vectors that maximizes the utility in $S_t$) have the same feature vectors for each assortment. Given that the input to the MNL probability function is a single feature vector, our problem can be reduced to the logistic bandit problem. Subsequently, using similar analyses to those in the proof of Theorem 2 from Abeille et al. (2021) [4], we can derive a regret lower bound of $\\Omega(d\\sqrt{\\kappa^\\star T})$ where $\\kappa^\\star :=  \\sum\\_{i \\in S^\\star} p(i \\mid S^\\star, \\mathbf{w}^\\star)  p(0 \\mid S^\\star, \\mathbf{w}^\\star)$. See **Section B in the comments below** for more detailed proof.\n\nWe are more than happy to include this lower bound. However, we do **NOT believe that not stating the problem-dependent lower bound should be considered a weakness**, as our focus is to show the regret dependence on $K$ and $v_0$.\n\n>Due to space limitations, we will address your questions in the following comments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gtYOj8CKGG", "reviewer": "Reviewer_NbJU", "summary": "This paper studied the minimax optimal regret for a series of contextual MNL bandit problems, covering rewards—uniform and non-uniform cases and varying the value of the outside option $v_0$. The authors first derive the regret lower bound that provides explicit dependence on the key parameters. Then they propose efficient algorithm OFU-MNL+ that achieves a matching upper bound up to a logarithm term. Simulations were conducted to demonstrate the tight dependence of the derived bounds.", "questions": "see Weakness", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Despite many recent advances in contextual MNL bandit problems, however no previous studies have proven the minimax optimality. There has been a significant discrepancy between lower and upper regret bounds, particularly regarding the feature dimension $d$ and the maximum assortment size $K$. This paper closes this gap. The technical contribution is strong and sufficient. \n\n2. In spite of a theoretical paper, it is well written and is easy to follow. I enjoy reading the paper.", "weaknesses": "1. My major question is about Assumption 2, which requires the uniform lower bound for every item $i\\in {\\cal S}$ and any assortment set and all round $t$. Requiring $\\kappa$ to be a constant would be a strong assumption in practice. Since $\\min_i p_t(i|S,w) \\le 1/K$, $\\kappa$ would naturally depend on the size $K$. In this case, would it be possible to derive more tighter results by explicitly including $\\kappa$ in the lower and upper bounds? \n\nBelow are a few minor suggestions: \n\n2. I would suggest to introduce Section 4 (Problem Setting) before Section 3 (Existing Gap). Readers who are not familiar with the contextual MNL bandit problems might be confusing while reading Section 3. \n\n3. Section 3 overlaps with many discussions in the Introduction section. It might be helpful to shorten the discussion and add more discussions on (1) why proving the new lower and upper bound results is non-trivial; (2) providing some proof outlines on the key steps used in the proof. \n\n4. In the Introduction, line 31 on page 1, it is helpful to add some clarification on the definition of $v_0$. The current terminology \"utility of the outside option\" is not very clear. \n\n5. In line 162 on page 4, the authors mentioned that the set of items $[N]$ can vary over time. While I understand the assortment set $\\cal S$ could change over time, I am confused how $[N]$ could vary over time. The notation $[N]$ means $\\{1, \\ldots, N\\}$. What do you mean this set varies over time? Do you allow new items to enter the market or some items to be removed over time?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are delighted that you enjoyed reading our paper and appreciated the value of our contributions. Thank you very much for your valuable feedback. Based on your detailed and insightful suggestions, we will make further improvements to our paper.\n\n---\n### **Regarding Assumption 2**\n\nWe would like to clarify that the existence of a **non-zero $\\kappa$ in our Assumption 2 should NOT be considered a weakness**. It is important to note that $\\kappa$ is always non-zero, as all MNL probabilities are non-zero for bounded feature vectors and bounded parameters, and $\\kappa$ represents the minimum value of the product of two MNL probabilities. Thus, it is more appropriate to \"define\" $\\kappa$ rather than assuming its existence. In Goyal and Perivier (2021), $\\kappa$ is also defined rather than assumed. For clarity, we will revise Assumption 2 to be a Definition in our final version.\n\nMoreover, this is a **common assumption** in logistic, MNL, and generalized linear model (GLM) bandits, and should NOT be considered a unique limitation of our work.\n\nMore interestingly, although $\\kappa$ can be exponentially small, our algorithm does **not need to know $\\kappa$**. And we avoid the $\\kappa$-dependence in the leading term of our regret analysis, making our algorithm much more practical.\n\n---\n### **Problem-dependent regret bounds**\n\nIt turns that **problem-dependent upper and lower bounds** under uniform rewards are achievable. By making some modifications to our results, we can easily achieve this. \n\n**1. Upper bound**  \nBy adapting Theorem 2 from Faury et al. (2022) [21] to the multinomial and online parameter setting, we can achieve a regret upper bound of $\\tilde{\\mathcal{O}}\\left( d \\sqrt{\\sum_{t=1}^T \\kappa_t^\\star} + d^2/\\kappa \\right)$, where $\\kappa_t^\\star = \\sum_{i \\in S_t^\\star} p_t(i \\mid S_t^\\star, \\mathbf{w}^\\star)p_t(0 \\mid S_t^\\star, \\mathbf{w}^\\star)$. See **Section A in the comment below** for the proof.\n\n**2. Lower bound**  \nWe can also derive a regret lower bound of $\\Omega(d\\sqrt{\\kappa^\\star T})$ by applying Theorem 2 from Abeille et al. (2021).\n\nIn the proof of Theorem 1, both the optimal assortment $S^\\star$ and an alternative assortment $\\tilde{S}_t$ (only has feature vectors that maximizes the utility in $S_t$) have the same feature vectors for each assortment. Let $S^\\star = \\\\{x,\\dots,x \\\\}$ and $\\tilde{S}_t = \\\\{\\hat{x}, \\dots, \\hat{x}\\\\}$. Then, by Proposition D.1, we have\n\n>$\n\\sum_{i \\in S^\\star} p(i \\mid S^\\star, \\mathbf{w}^\\star)  -  \\sum_{i \\in S_t} p (i \\mid S_t, \\mathbf{w}^\\star)\n\\geq \\sum_{i \\in S^\\star} p(i \\mid S^\\star, \\mathbf{w}^\\star)  -  \\sum_{i \\in \\tilde{S}_t} p (i \\mid \\tilde{S}_t, \\mathbf{w}^\\star)\n=: f(x;\\mathbf{w}^\\star) - f(\\hat{x};\\mathbf{w}^\\star).\n$\n\nHere, $f(x;\\mathbf{w}^\\star) = \\frac{ K\\exp(x^\\top\\mathbf{w}^\\star ) }{v_0 + K \\exp(x^\\top \\mathbf{w}^\\star)}$ maps from $\\mathbb{R}^d$ to $\\mathbb{R}$. Since the input to the function $f$ is a single vector $x$, $f$ can be regarded as a logistic function. This characteristic allows us to follow the proof of Theorem 2 from Abeille et al. (2021) [4], resulting in a regret lower bound of $\\Omega(d\\sqrt{\\kappa^\\star T})$.\n\n---\n### **Suggestions**\n\n**1. Introducing Section 4 before Section 3**: That’s a great suggestion. Thank you for your input. We will incorporate these changes into the final version.\n\n**2. More discussion on (1) why proving the new lower and upper bounds is non-trivial; (2) providing some proof outlines for the key steps used in the proofs**: Due to the page limit, we have briefly outlined the technical novelties used in each proof in the discussions section of the main paper, while providing more comprehensive details in the Appendix. If we receive an extra page for the camera-ready version, as you suggested, we will expand the discussions to further emphasize the importance of our bounds and elaborate on the key steps used in the proofs.\n\n**3. Clear definition of $v_0$**: The utility for the outside option $v_0$ is the *attraction parameter* for not choosing any item, and it is used to construct the MNL probability. For better presentation, we will include a reference to the definition of MNL probabilities (Eq.1) when we first introduce the term $v_0$ and provide additional explanation about $v_0$.\n\n**4. The meaning of \"the set of items $[N]$ can vary over time\" (Line 162)**: The statement indicates that we allow for the entry of new items into the market or the removal of existing items over time, which could also lead to changes in the total number of items, denoted as $N_t$. For clarity, we need to define the item set at time $t$ as $\\mathcal{I_t}:= \\\\{ i_{t1}, \\dots, i_{tN_t} \\\\}$. Thus, the item set $\\mathcal{I_t}$ can vary over time. Thank you for pointing this out. We will clarify this notation in the final version of our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to express our heartfelt thanks to all the reviewers for their constructive feedback. Your insights and suggestions are greatly appreciated.

In response to Reviewer 8Ks7's request, we conducted additional experiments for the logistic case  ($K=1$) and for larger values of $K$ ($K=20,30$).  The results of these experiments are detailed in the attached PDF.
These results also support our theoretical claims. Specifically, under uniform rewards, we observe that the regret decreases as $K$ increases, aligning with Theorems 1 and 2. Conversely, under non-uniform rewards, the regret remains unaffected by changes in $K$, consistent with Theorems 3 and 4.

We are pleased to provide additional results that further strengthen the claims in our paper. Thank you very much!

Meta-review: This paper explores the problem of contextual multinomial logit (MNL) bandits, an elegant abstraction that captures many real-world decision-making scenarios. Previous research has shown a clear theoretical gap between upper and lower bounds, particularly with respect to the maximum assortment size $K$. The authors thoroughly investigate this issue and propose several innovative algorithms with provable regret bounds, demonstrating their results' near-minimax optimality. These findings are very nice, and the reviewers unanimously recognize the value of these results. On the other hand, they also highlight several points for improvement. Key points include addressing experimental issues and providing clearer distinctions between the paper’s contributions and earlier work, such as Zhang and Luo [48] and Zhang and Sugiyama [49]. The authors are encouraged to revise the manuscript to incorporate the reviewers' suggestions and enhance its impact on the field.
Decision: Accept (poster)