Contextual Multinomial Logit Bandits with General Value Functions
Authors: Mengxiao Zhang
Haipeng Luo
Venue: NeurIPS 2024 poster (2024)
Keywords: Contextual Bandits
Multinomial Logit Bandit
Online Learning
Primary area: bandits

Abstract: Contextual multinomial logit (MNL) bandits capture many real-world assortment recommendation problems such as online retailing/advertising. However, prior work has only considered (generalized) linear value functions, which greatly limits its applicability. Motivated by this fact, in this work, we consider contextual MNL bandits with a general value function class that contains the ground truth, borrowing ideas from a recent trend of studies on contextual bandits. Specifically, we consider both the stochastic and the adversarial settings, and propose a suite of algorithms, each with different computation-regret trade-off. When applied to the linear case, our results not only are the first ones with no dependence on a certain problem-dependent constant that can be exponentially large, but also enjoy other advantages such as computational efficiency, dimension-free regret bounds, or the ability to handle completely adversarial contexts and rewards.

Contextual Multinomial Logit Bandits with General Value Functions
Mengxiao Zhang University of Iowa mengxiac wwwngguuiow.....ooom menggiiao-zhaan@eulvvaa
Haipeng Luo University of Southern California haipeng @usc. edu
edu
Abstract
Contextual multinomial logit (MNL) bandits capture many real-world assortment recommendation problems such online retailing/adverisinng. However, prior work has only considered (generalized) linear value functions, which greatly lim- its its applicability. Motivated by this fact, in this work, we consider contextual MNL bandits with a general value function class that contains the ground truth, borrowing ideas from recent trend of studies on contextual bandits. Specifically, we consider both the stochastic and the adversarial settings, and propose a suite algorithms, each with different computation- linear case, our results not only are the first ones with no dependence on certain wroblem-dependen constant that can be exponentially large, but also enjoy other advantages such as computational efficiency, dimension-free regret bounds, or the ability to handle completely adversarial contexts and rewards.
trade-off. When applied to the
Introduction
As assortment recommendation becomes ubiquitous in real-world applications such as online retail- ing and advertising, the multinomial (MNL) bandit model has attracted great interest in the past decade since was proposed by Rusmevichientong et al. [24]. involves learner and a customer interacting for 7' rounds. At each round, knowing the reward/profit for each of the N available items, the learner selects subset/assortment of size most K and recommend it to the customer, who then purchases one of these K items or none of them according to multinomial logit model specified by the customer's valuation over the items. The goal of the learner is to learn these unknown valuations over time and select the assortments with high reward.
To better capture practical applications where there is rich contextual information about the items and customers, a sequence of recent works study contextual MNL bandit model where the customer's valuation is determined by the context via an unknown (generalized) linear function [8, 21, 7, 19, 20, 23, 2]. However, there are no studies on general value functions, despite many recent breakthroughs for classic contextual multi-armed bandits using general value function class with much stronger representation power that enables fruitful results in both theory and practice [1, 10, 27, 11, 25).
Contributions. Motivated by this gap, we propose contextual MNL bandit model with general value function class that contains the ground truth (a standard realizability assumption), and develop suite of algorithms for different settings and with different computation-regtt trade-off.
More specifically, in Section 3, we first consider a stochastic setting where the context-reward pairs i.i.d. samples of unknown distribution. Following the work by Simchi-Levi and Xu [25] for contextual bandits, we reduce the problem to an casier offline log loss regression problem and pro- pose two strategies using an offline regression oracle: one with simple and efficient uniform explo- ration, and another with more adaptive exploration (and hence improved regret) induced by a novel log-barrier regularized strategy. Our results rely on several new technical findings, including a fast
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Comparisons of results for contextual MNL bandits with "" rounds, N items, size-K as- sortments, and a d-dimensional linear value function class with norm bounded by B. All previous results depend on problem-dependent constant that is cxp(2B) in the worst case, while ours (in gray) do not. The notation ((.) hides logarithmic dependency all parameters. In the last column, means polynomial runtime in all parameters; * means polynomial only when K a constant; and X means not polynomial even for a small K.
Context 2; & reward
Regret
Efficient?
((dBNK) (/T (Corollary 3.5)
Stochastic (x))
O(K2 VIKVVBBNT (Corollary 3.8)
Adversarial 24, F2
OldK /T/K d d
R)
[23]
x
OldvT K** [7]
Stochastic øt Adversarial
OlNvdT K²)
[20]
x
OldVKT + x²)
[20]
!(maxt V di, dv d (T/KK) [7]
N/A
O(NNKB) // (Corollary 4.4)
Adversarial (Ia, rt)
O(K² (NK3/N (Corollary 4.7)
K
V(K'VNNT) (Corollary 4.8)
x
rate regression result (Lemma 3.1), a "reverse Lipschitzness" for the MNL model (Lemma 3.3), and a certain hoo--regee-hiigh-ddssessoioo property of the log-barrier regularized strategy (Lemma 3.6).
Next, in Section 4, we switch to the more challenging adversarial setting where the context-rew pairs can be arbitrarily chosen. We start by following the idea of [10, 11] for contextual bandits and reducing our problem to online log loss regression, and show that it suffices to find a strategy with a small
Coefficient (DEC) (10, 14]. We then show that, somewhat surprisingly, the same log-barrier regularized strategy we developed for the stochastic setting leads to small DEC, despite the fact that it is not the exact DEC minimizer (unlike its counterpart for contextual bandits [13]). We prove this by using the same aforementioned low-regret-high. high-sssei prop- crty, which to our knowledge a new way to bound DEC and reveals why log-barrier regularized strategies work in different settings and for different problems. Finally, we also extend the idea of Feel-Good Thompson Sampling [30] and propose a variant for our problem that leads to the best regret bounds in some cases, despite its lack of computational efficiency.
Throughout the paper, we use two rumning examples to illustrate the concrete regret bounds our different algorithms achieve: the finite class and the linear class. In particular, for the linear class, this leads five new results, summarized in Table together with previous results. These results all have their own advantages and disadvantages, but we highlight the following:
While all previous regret bounds depend on groblem-depende constant that can be exponen- tially large in the norm of the weight vector B, none of our results depends on K. fact, our best results (Corollary 4.8) even has only logarithmic dependence on B, potential doubly-exponential improvement compared to prior works."
The regret bounds of our two algorithms that make of online regression oracle dimension-free, despite not having the optimal V'T-eeeedeence (Corollary 4.4 and Corollary 4.7).
Our results are the first to handle completely adversarial context-reward pairs.?
'One caveat is that, following [5, 9, 18], we assume that no-purchase is the most likely outcome by normal- izing the range of the values [0, 1), making it only subclass of the considered in [19, 7, 20]. However, we emphasize that the bounds presented Table have been translated accordingly to our setting. Also note that the dependence [23] is in the form of / T/r + (so not necessarily increasing in k). but it only holds for uniform rewards.
"Agrawal et al. [2] also considered adversarial contexts and rewards, but there is technical issue in their analysis pointed out by the authors. Even if corrected, their results still depend on & while ours do not.

---

Related works. The (non- con-cooneettal) MNL model was initially studied in [24]. followed by a line of improvements [3, 4, 6, 22]. Specifically, Agrawal et al. [3, 5] introduced UCB-type algorithm achieving OTVNT) regret and proved a lower bound of D(VNT//K Subsequently, Chen and Wang [6] enhanced the lower bound to l (T)) matching the upper bound to log factors.
Cheung and Simchi-Levi [8] first extended MNL bandits to its contextual version and designed a Thompson sampling based algorithm. Follow-up works consider this problem under different settings, including stochastic context [7, 19, 20), adversarial context 21, and uniform reward over items [23]. However, as mentioned, all these works consider (generalized) linear value functions, and our work the first to consider contextual MNL bandits under a general value function class.
Our work is also closely related to the recent trend of designing contextual bandits algorithms for general function class. Due to space limit, defer the discussion to Appendix A.
2 Notations and Preliminary
Notations. Throughout this paper, we denote the set {1, 2....,N] N} for some positive integer N by [N] and (0, 1, .......... .) by [N]o- For vector u E R we u, to denote its i-th coordinate, and for a matrix W E N we use W to denote its j-th column. For a set S, we denote by ASS) the set of distributions over S, and by conv(S) the convex hull of S. Finally, for a distribution a E {[[])) and an outcome E [N]o. the corresponding log loss is (jog( i) = log pi,
We consider the following contextual MNL bandit problem that proceeds for T rounds. At each round f, the learner receives context 2; X' for some arbitrary context space X and a reward vector E [0, 1] which specifics the reward of N items. Then, out of these N items, the learner needs to recommend subset S₁ C S to customer, where S S 2[M] is the collection of all subsets of [N] with cardinality at least and at most for some S N. Finally, the learner observes the customer purchase decision & E S, U (0}, where 0) denotes the no-purchase option, and receives reward ft, where for notational convenience we define 7r,0 = for all (no reward if no purchase). The customer decision i, is assumed to follow an MNL model:
((e)) 1+ 1+E (R+)
if E St.
Pr[ie é St,
=
1+E (,))
if =0 0, otherwise,
where ft X' + 1j is an unknown value function, specifying the costumer's value for each item under the given context. The MNL model above implicitly assumes value of 1 for the no- purchase option, making it the most likely outcome. This standard assumption that holds in many realistic settings [5, 9, 18).
To simplify notation, we define μ S [0, + A(lV)o) such that (s(S, v) x v,1li S U {O) with the convention = 1. The purchase decision i, is thus sampled from the distribution (f In addition, given a reward vector r e [0, M (again, with convention ro 0), we further define the expected reward of choosing subset S E S under context E X' as
Eies T:0l I+ Eiess t
R(S, v, r) (x
[rd] Σ Em(
The goal of the learner then to minimize her regret, defined as the expected gap between her total reward and that of the optimal strategy with the knowledge of ft:
T max R(S F(S,f Σ ((SS,,((Zz))
T
RegMNL = E
SES
To ensure that no-regret is possible, we make the following assumption, which is standard in the literature of contextual bandits.
Assumption The learner is given function class J = ( X [0, 1 which contains f*
Our hope is thus to design algorithms whose regret sublinear in T and polynomial in N and some standard complexity measure of the function class F. So far, we have not specified how the
3

---

Algorithm Contextual MNL Algorithms with an Offline Regression Oracle
Input: offline regression oracle Algoff satisfying Assumption
Define: epoch schedule To = and Tm = 2 1 for all m = 1.2.....
for epoch m 1.. do
Feed {2z, St, 4
) 15m
t= 1+1 to Algoft and obtain fm-
Define stochastic policy 9m : 10, - ((8) via either Eq. (4) Eq. (5).
for 1 = =T Tm + 1, mm+1 do
Observe context 2, E X and reward vector r; E [0. 1].
Sample St 4m (3a, and recommend it to the customer.
Observe customer's purchase decision ét E S, (0), drawn according to Eq. (1).
context 2t and the reward are chosen. In the next sections, will discuss both the easier stochastic case where (Ig, is jointly drawn from some fixed and unknown distribution, and the harder adversarial case where TT) can be arbitrarily chosen by an adversary.
3 Contextual MNL Bandits with Stochastic Contexts and Rewards
In this section, we consider contextual MNL bandits with stochastic contexts and rewards, where at each round f [T]. 2g and r, are jointly drawn from fixed and unknown distribution Following the literature of contextual bandits, we aim to reduce the problem to easier and better-studied offline regression problem and only access the function class F through some offline regression oracle. Specifically, an offline regression oracle Algorr takes as input a set of i.i.d. context-subset- purchase tuples and outputs predictor from JF with low generalization error in terms log loss, formally defined as follows.
Assumption Given n samples D == {[1K, Sk. ix) where each (Ik. Sk, ix) E X x S [N] is an i.i.d. sample of some unknown distribution H. and the conditional distribution of in is p(S,, f (xx)). with probability least 1 the offtine regression oracle Algatt outputs func- tion fD E such that:
B(H,S,)HHH [Log fo(x)) (L,( s Erriog (n, (n, F)F,
(2)
for some function Erriog (n, 8, F) that is non-increasing in n.
Given the similarity between MNL and multi-class logistic regression, assuming such log loss regression oracle is more than natural. Indeed, in the following lemma, we prove that for both the finite class and a certain linear function class, the empirical risk minimizer (ERM) not only satisfies this assumption, but also enjoys a fast 1/n rate. The proof is based on the observation that our loss function fing (u(S, f(x)), i), when seen function of f, satisfies the so-called strong 1-central condition [17, Definition 7], which might be of independent interest; see Appendix B. for details.
Lemma 3.1 The ERM strategy F = argminfer ElE.S lan (M(S, satisfies Assump- tion 2 for the following two cases:
(Finite class) F is a finite class of functions with image 13,11" for some E (0, and 5, (n,
Errig (n,
F) O
log K/O log Aife)
(Linear class) X' C {u E B and ErTiog (n, 8, = 0 dBlog log( (Bn) log b). for some B > 0.3
(o,(()) = -0 aTa, ||011 S B}.
"We call this linear class (even though it is technically log-linean because, when combined with the MNL model Eq. (1), becomes the standard softmax model with linear policies. Also note the bias term -B in the exponent makes sure fo fa( E [0, 1 Following [23]. we assume ||0||2 < B instead of ||@|| < to ensure the representation power of the function class, since we already normalize the contexts and restrict them be within the unit ball.

---

Therefore, combining Lemma 3.2 and Lemma 3.3, we see that to design good algorithm. it suf- fices to find stochastic policy that "mostly" follows argmaxg R(S, Jm (are), rt), the best decision according to the oracle's prediction, and at the same time ensures high dispersion for all such Due to space limit, we only use these two simple function classes as running examples throughout the paper, but we emphasize that our results can be applied to any class as long as regression feasible. For additional examples, see Appendix D.
Given Algoft we outline natural algorithm framework that proceeds in epochs with exponen- tially increasing length (see Algorithm 1): At the beginning of each epoch m, the algorithm feeds all the context-subset-pucce purcchccce tuples from the last epoch the offline regression oracle Alg and obtains a value predictor fm- Then, it decides in some way using fm a stochastic policy qm which maps a context z and reward vector r E [0, 1] hand, for every round within this epoch, the algorithm simply samples a subset St according to qm (24, r1) and recommend it to the customer.
distribution over S. With such a policy in
We will specify two concrete stochastic policies qm in the next two subsections. Before doing so, highlight some key parts of the analysis that shed light on how to design a "good" 4m- The first step is an adaptation of Simchi-Levi and Xu [25, Lemma 7J, which quantifies the expected reward difference any policy under the ground-truth value function f versus the estimated value function fm- Specifically, for a deterministic policy π : X x [0, 1j + S mapping from a context-reward pair a subset, we define its true expected reward and its expected reward under f' respectively as (overloading the notation R):
(3) Moreover, for any E ASS), define w(p) E 1J such that w: EsESHeS P(S) is the prob- ability of item i being selected under distribution p. and for any stochastic policy q, further define
R(T) = ((,,))
(m) (ass) [R(T[ ()
dispersion measure for deterministic policy as V(g, T (a.rr)> EiEx(e w((g(z.r)) (the
smaller V (g, T) is, the more disperse the distribution induced by q is). Using the Lipschitzness (in v) of the reward function R(S,v, v) (Lemma B.1), we prove the following.
Lemma 3.2 For any deterministic policy π X x [0, 1| + S and any epoch m 2 2, we have
|mm - R(T)] S SVVVVVVVR (V(m-1,,
E D.S.))
Σ (fmml())f((a))) LES
If the learner could observe the true value of each item in the selected subset (or its noisy version), then doing squared loss regression on these values would make the squared loss term in Lemma 3.2 small; this is essentially the case in the contextual bandit problem studied by Simchi-Levi and Xu [25]. However, in our problem, only the purchase decisions are observed but not the true values that define the MNL model. Nevertheless, one of our key technical contributions is to show that the offline log-loss regression, which only relies on observing the purchase decisions, in fact also makes sure that the squared loss above is small.
Lemma 3.3 For any and v. vi E [0, 1]N, we have
E(u; 0²)² (| p(S, ot v1) 2E 2Eir)(S,or) [kig (M(S, flog (oo(H(( LES
The first equality establishes certain "reverse Lipschitzness" of l and is proven by providing universal lower bound on the minimum singular value of its Jacobian matrix, which is new to our knowledge. It implics that if two value vectors induce pair of close distributions, then they must be reasonably close as well. The second equality, proven using known facts, further states that to control the distance between two distributions, suffices to control their log loss difference, which exactly the job of the offline regression oracle.
that the oracle's predicted reward for any policy is close to its true reward. The design of our two algorithms in the remaining of this section follows exactly this principle.
5

---

3.1 A Simple and Efficient Algorithm via Uniform Exploration
As warm-up, we first introduce a simple but efficient & e-greddy-type algorithm that ensures reason- able dispersion by uniformly exploring all the singleton sets. Specifically. at epoch m, given the value predictor fm from Algart 9m (2, A(S) is defined as follows for some Em >
9m (5(p, = (1 - Em) argmax R(S", (m)
+ 6m 1 (1] N
In other words, with probability based on the reward vector r and the predicted value fm (2); with the remaining e probability, the learner selects a uniformly random item i E [N] and recommend only this item, which clearly ensures V (gm, T) I KNN for any æ. Based on our previous analysis, it is straightforward to prove the following regret guarantee.
the learner picks the subset achieving the maximum reward
Em
Theorem 3.4 Under Assumption and Assumption 2, Algorithm I with 9m defined Eq. (4) and the optimal choice of m. ensures RegMNL
=> E1log I1 O (N (2 1 F))+)
To better interpret this regret bound, we consider the finite class and the linear class discussed in Lemma 3.1. Combining it with Theorem 3.4, immediately obtain the following corollary:
Corollary 3.5 Under Assumption 1, Algorithm with defined in Eq. (4), the optimal choice of K ETR and ERM as Algotr ensures RegMNL 0 ((N 8 (og((F(T)) for finite class and RegmNL = O (dDBNK log K)&T log( (T) log T) for linear class (see Lemma 3.1 for defini- tions).
While these O(T%)s regret bounds suboptimal, Theorem 3.4 provides the first computationally efficient algorithms for contextual MNL bandits with an offline regression oracle for a general func- tion class. Indeed, computing argmaxs-es R(S*, f'm (mr,, r) can be efficiently done in ((N2) time according to [24, Section 2. Moreover, for the linear case, the ERM oracle can indeed be effi- ciently (and approximately) implemented because it is convex optimization problem over simple ball constraint. Importantly, previous regret bounds for the linear case all depend on a problem- dependent constant max [o|s $.$$8, (. (S. which is exp(2B) in the worst case [7, 20, 23], but ours only has polynomial dependence B.
3.2 Better Exploration Leads to Better Regret
Next, we show that a more sophisticated construction of Jm in Algorithm leads to better explo- ration and consequently improved regret bounds. Specifically, Qo is defined (for some 7m 0):
Qm (x,, r) argmax Espp fm().r) (K + 1)a
log
(EA(S)
I'
(p(p)
The first term of the optimization objective above is the expected reward when one picks subset according to p and the value function fm. while the second term a certain log-barrier regularizer applied to p, penalizing it for putting too little mass on any single item. This specific form of regularization ensures that 9n enjoys www-regret-highe sighrtttigg--ispersionn guarantee, as shown below.
Lemma 3.6 For any x E X and r E 11 the distribution 9m (x, defined in Eq. (5) satisfies:
max R(S* fm((),r) ES (a.r) fm)) N(K +3 S*ES
(6)
7m
VS E S, Σ Σ ies
w (2,
N
Ym (K +1+
max R(S" fm((),, R(S, fm())))))
(7)
Eq. (6) states that following qm (Ic, r) does not incur too much regret compared to the best subset predicted by the oracle, and Eq. (7) states that the dispersion of 4m (2,r) on any subset is controlled

---

by how bad this subset is compared to the best one in terms of their predicted reward - a good subset has large dispersion while a bad one can have smaller dispersion since we do not care about estimating its true reward very accurately. Such refined dispersion guarantee intuitively provides a much more adaptive exploration scheme compared to uniform exploration.
This kind of low-regret- -eggrretthihh-iiee high-dispersion guarantees is in fact very similar to the ideas of Simchi-Levi and Xu [25] for contextual bandits (which itself is similar an earlier work by Agarwal al. [T]). While Simchi-Levi and Xu [25] were able to provide a closed-form strategy with such a guarantee for contextual bandits, we do not find similar closed-form for MNL bandits and instead provide the strategy as the solution of an optimization problem Eq. (5), Unfortunately. we are not aware of an efficient way to solve Eq. (5) with polynomial time complexity. but one can clearly solve in poly([S)) = poly(N time since it is concave problem over A(S). Thus, the algorithm is efficient when K' is small, which we believe is the case for most real-world applications.
Combining Lemma 3.2 and Lemma 3.6, we prove the following regret guarantee, which improves the Err 1/3 log term in Theorem 3.4 to Err 1/2 (proofs deferred to Appendix B).
Theorem 3.7 Under Assumption 1 and Assumption 2, Algorithm 1 with qm defined in Eq. (5) and
the optimal choice of Tm ensures RegMNL = O E [log,21 21 2 K2 K2v /NVrrirgggg (2m- 11/22, F)).
Similar to Section 3.1, we instantiate Theorem 3.7 using the following two concrete classes:
Corollary 3.8 Under Assumption 1, Allgorithm with qm defined in Eq. (5), the optimal choice of Ymo and ERM as Algon ensures RegMNL = O K22 TTlog K 3 log((F(T)) for the finite class and RegMNL = O (K² CVBNNTTogg BT) log for the linear class (see Lemma 3.1 for definitions).
The dependence on T in these ((VT) regret bounds is known to be optimal [6, 7J. Once again, in the linear case, we have no exponential dependence on B, unlike previous results.
4 Contextual MNL Bandits with Adversarial Contexts and Rewards
In this section, we move on to consider the more challenging case where the context 2, and the reward vector can both be arbitrarily chosen by an adversary. We propose two different approaches leading to three different algorithms, each with its own pros and cons.
4.1 First Approach: Reduction to Online Regression
In the first approach, we follow recent trend of studies that reduces contextual bandits to online regression and only accesses F through an online regression oracle [10, 11, 15, 31, 29]. More specifically, we assume access to an online regression oracle Algon that follows the protocol below: each round t E [T', Algon outputs a value predictor fa conv(F); then, it receives a context It. a subset S,, and a purchase decision i, E S; U {0}. all chosen arbitrarily, and suffers log loss (og(u(S (u(S,, fe(xre),, it). The oracle is assumed to enjoy the following regret guarantee.
Assumption The predictions made by the online regression oracle Algon ensure:
T
E
Σ
(no ((
(e < Regiog (T,F),
for any frr E F and some regret bound Regiog FT,F) that is non-decreasing T.
While most previous works on contextual bandits assume squared loss online oracle, log loss is more than natural for our MNL model (it was also used by Foster and Krishnamurthy [11] I] to achieve first-order regret guarantees for contextual bandits). The following lemma shows that Assumption again holds for the finite class and the linear class.
In fact, for our purpose, i, is always sampled from ( (xx)). instead of being chosen arbitrarily, but the concrete oracle examples provide in Lemma 4.1 indeed work for arbitrary
7

---

Lemma 4.1 For the finite class and the linear class discussed in Lemma 3.1, the following concrete oracles satisfy Assumption 3:
(Finite class) Hedge [16] with Regiog (, log F log ))
(Linear class) Online Gradient Descent [32] with Regiog (I, =
not able to provide "fast rate" (that is, Ó(1) re- gret) for these two cases, because our loss function does not appear to satisfy the standard Vovk's mixability condition or any other sufficient conditions discussed in Van Erven et al. [26]. This is in sharp contrast to the standard multi-class logistic loss [12]. despite the similarity between these two models. We leave
Unfortunately, unlike the offline oracle,
open problem whether fast rates exist for these two classes, which would have immediate consequences to our final MNL regret bounds below.
With this online regression oracle, natural algorithm framework works as follows: at each round t, the learner first obtains value predictor St conv(F) from the regression oracle Algon then, upon seeing context and reward vector vz. the learner decides in some way a distribution q: E A(S) based on ((( and ry, and samples S, from q: finally, the learner observes the purchase decision and feeds the tuple (æz, St. to the oracle Alg (see Algorithm 2 in Appendix C). To shed light
on how to design a good sampling distribution qr. we show a general lemma that holds for any qr.
Lemma 4.2 Under Assumption 1 and Assumption 3, Algorithm 2 (with any qe) ensures
T
RegMNL S
E
dec-(ae fe(ax) Reggo (T,F)
for any > O, where (q;,(q; is the Decision-Estimanee Estimation Coefficient (DEC) defined as { (R(S*, w² .r) "U""","",r" of o'E[0,1] S*
Es-g [R(S, vr,r,,) ,r]] 7Bs- [Il((S))) u(S,
max max
(8)
Our DEC adopts the idea of Foster al. [14] for general decision making problems: the term R(S", .².r) r) - EEsg [R(S, r']] represents the instantancous regret of strategy against the best subset S* with respect to reward vector and the worst-case value vector v", and the term Eswalllu((.,) v) (S,, u*) )[2] is the expected squared distance between two distributions induced by e and v", which, in light of the second inequality of Lemma 3.3, lower bounds the instantancous log loss regret of the online oracle. Therefore, small DEC makes sure that the learner's MNL regret is somewhat close to the oracle's log loss regret Regiog: formally quantified by Lemma 4.2. With the goal of ensuring a small DEC, we again propose two strategies similar to Section
Uniform Exploration. We start with a simple uniform exploration approach similar to Eq. (4):
(= - (1- S argmax R(S*, fe(2).)
1 (i)
S*ES
where is a parameter specifying the probability of uniformly exploring the singleton sets. We prove the following results for this simple algorithm.
The strategy defined in Eq. (9) guarantees (ec,(95 fe(ee), O NK + Con- sequently, under Assumption I and Assumption 3, Algorithm with qu calculated via Eq. (9) and the optimal choice of and 7 ensures RegMNL O(N K (T, $33
Theorem 4.3
ve NK
Combining this with Lemma 4.1, we immediately obtain the following corollary.
Corollary 4.4 Under Assumption Algorithm 2 with qe defined in Eq. (9) and the optimal choice of and ensures RegMNL = O =O(NN log K $ { for the finite class (with Hedge as Algon) and
RegMNL = o ( for the linear class (with Online Gradient Descent as Algon)
While these regret bounds have large dependence on T, the advantage of this algorithm is its computational efficiency discussed before.

---

Better Exploration. Can we improve the algorithm via strategy with an even smaller DEC? In particular, what happens if we take the extreme and let q be the minimizer of dec, (q: fi (z+), r,)? Indeed, this is exactly the approach in several prior works that adopt the DEC framework [13, 29], where the exact minimizer for DEC is characterized and shown to achieve a small DEC value.
On the other hand, for our problem, it appears quite difficult to analyze the exact DEC minimizer. Somewhat surprisingly, however, we show that the same construction Eq. (5) for the stochastic environment in fact also achieves a reasonably small DEC for the adversarial case:
Theorem 4.5 The following distribution satisfies dec, (gt. fe(2)), S
NK*
qt = argmax Ess [R(S, [(())))))) (K 1)
N
log
(10)
1=1 Wi; (q)
qEA(S)
couple of remarks are in order. First, while for some cases such as the contextual bandit problem studied by Foster et al. [13], this kind of log-barries regularized strategies is known to be the exact DEC minimizer, one can verify that this is not the case for our DEC. Second, the fact that the same strategy works for both the stochastic and the adversarial environments is similar contextual bandits where the same inverse gap weighting strategy works for both cases [10, 25), but our knowledge, the connection between these tWO cases is unclear since their analysis is quite different. Finally, our proof (in Appendix C) in fact relies on the same low-regret-high high---ssd-diooiioon property Lemma 3.6, which is new way to bound DEC as far as we know. More importantly. this to some extent demystifies the last two points: the reason that such log-barrier regularized strategies work regardless whether they are the exact minimizer or not and regardless whether the environment is stochastic or adversarial is all due to their inherent low-regret-hin sregret-highddisprsiion property.
the case for
Combining Theorem 4.5 with Lemma 4.2, we obtain the following improved regret.
Theorem 4.6 Under Assumption I and Assumption 3, Algorithm 2 with qe calculated via Eq. (10) and the optimal choice of y ensures RegMNL = O I2 0(K² (NTReging
Corollary 4.7 Under Assumption 1, Algorithm 2 with qu defined in Eq. (10) and the optimal choice o ensures RegMNL OK3 N log K (log (FI) for the finite class (with Hedge as Algan) and RegMNL = O(K2/NBBT for the linear class (with Online Gradient Descent as Algon)
We remark that if the "fast rate" discussed after Lemma 4.1 exists, we would have obtained the optimal VT-regret here. Despite having worse dependence on T, however, our result for the linear case enjoys three advantages compared prior work [7, 20, 23]: 1) no exponential dependence on B (as in all our other results), 2) no dependence at all on the dimension d, and 3) valid even when contexts and rewards are adversarial. We refer the reader to Table again for detailed comparisons.
4.2 Second Approach: Feel-Good Thompson Sampling
The second approach we take is to extend the idea of the Feel-Good Thompson Sampling algorithm of Zhang [30] for contextual bandits. Due to space limit, we defer the algorithm and its analysis to Appendix E, and only state its regret bounds for the finite class and the linear class (a corollary of a more general regret bound in Theorem E.
Corollary 4.8 Under Assumption 1, Algorithm 3 wensures RegMNL -(K2 COK2VNTT log FF) for the finite class and RegMNL = O OK2 /dNT (ogglo))))) for the linear class.
NT
In terms of the dependence on T, Algorithm achieves the best (and in fact optimal) regret bounds among all our results. For the linear case, it even has only logarithmic dependence on B, potential doubly-exponentiee
improvement compared to prior works. The caveat is that there no efficient way to implement the algorithm even for the linear case and even when K is constant (unlike all our other algorithms). We leave the question of whether there exists computationally efficient algorithm (even only for small K) with a /T-regret bound that has no exponential dependence on B as a key future direction.

---

Conclusion and Future Directions
In this work, we consider contextual MNL bandits with general value function class under re- alizability assumption. For both the stochastic and the adversarial settings, we propose a suite of algorithms with different computational-regre trade-off. Notably, none of our regret bounds suffers from the exponentially large dependence on some problem dependent constant in the case with lin- ear value functions. One interesting future direction is to improve the poly(K, N) dependence in regret upper bounds, which seems to require new techniques.
Acknowledgments and Disclosure of Funding
The authors were supported by NSF Award IIS- 1944097
References
[1] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. International Confer- ence on Machine Learning. 2014.
[2] Priyank Agrawal, Theja Tulabandhula, and Vashist Avadhanula. tractable online learning algorithm for the multinomial logit contextual bandit. European Journal of Operational Re- search, 2023.
[3] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. A near-optimal exploration-exploitation approach for assortment selection. Proceedings of the ACM Confer- ence on Economics and Computation, 2016.
[4] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the man-ba Conference on Learning Theory, 2017.
[5] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Mnl-bandit: A dynamic learning approach assortment selection. Operations Research, 67(5). 2019.
[6] Xi Chen and Yining Wang. A note on a tight lower bound for capacitated mnl-bandit assort- ment selection models. Operations Research Letlers, 46(5), 2018
[7] Xi Chen, Yining Wang, and Yuan Zhou, Dynamic assortment optimization with changing contextual information. The Journal of Machine Learning Research, 21(1), 2020.
[8] Wang Chi Cheung and David Simchi-Levi, Thompson sampling for online personalized as- sortment optimization problems with multinomial logit choice models. Available at SSRN 3075658, 2017.
[9] Kefan Dong, Yingkai Li, Qin Zhang, and Yuan Zhou. Multinomial logit bandit with low switching cost. International Conference on Machine Learning, 2020.
[10] Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. International Conference Machine Learning, 2020.
[11] Dylan J Foster and Akshay Krishnamurthy. Efficient first-order contextual bandits: Predic- tion, allocation, and triangular discrimination. Conference on Advances in Neural Information Processing Systems, 2021.
[12] Dylan J Foster, Satyen Kale, Haipeng Luo, Mchryar Mohri, and Karthik Sridharan. Logistic regression: The importance of being improper. Conference On Learning Theory, 2018
[13] Dylan Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to misspecifi- cation in contextual bandits. Conference on Neural Information Processing Systems, 2020.
[14] Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13488) 2021.
10

---

[15] Dylan J Foster, Alexander Rakhlin, Ayush Sekhari, and Karthik Sridharan. On the complexity of adversarial decision making. Conference on Advances Neural Information Processing Systems, 2022.
[16] Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1), 1997.
[17] Peter D Grünwald and Nishant A Mehta. Fast rates for general unbounded loss functions: from erm generalized bayes. The Journal of Machine Learning Research, 2020.
[18] Yanjun Han, Yining Wang, and Xi Chen. Adversarial combinatorial bandits with general non- linear reward functions. International Conference on Machine Learning, pages 4030-4039, 2021.
[19] Min-hwan Oh and Garud Iyengar. Thompson sampling for multinomial logit contextual ban- dits. Conference on Advances in Neural Information Processing Systems, 32, 2019.
[20] Min-hwan Oh and Garud Iyengar. Multinomial logit contextual bandits: Provable optimality and practicality. Proceedings of the AAAI conference on artificial intelligence, 35(10), 2021.
[21] Mingdong Ou, Nan Li, Shenghuo Zhu, and Rong Jin. Multinomial logit bandit with linear utility functions. Proceedings of the International Joint Conference on Artificial Intelligence, 2018.
[22] Yannik Pecters, Arnoud V den Boer, and Michel Mandjes. Continuous assortment optimization with logit choice probabilities and incomplete information. Operations Research, 70(3), 2022.
[23] Noemie Perivier and Vineet Goyal. Dynamic pricing and assortment under contextual mnl demand. Conference on Advances in Neural Information Processing Systems, 35, 2022.
[24] Paat Rusmevichientong, Zuo-Jun Max Shen, and David B Shmoys. Dynamic assortment opti- mization with a multinomial logit choice model and capacity constraint. Operations research, 58(6), 2010.
[25] David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 2021.
[26] Tim Van Erven, Peter Grunwald, Nishant Mehta, Mark Reid, Robert Williamson, et al. Fast rates in statistical and online learning. Journal of Machine Learning Research, 54(6), 2015.
[27] Yunbei Xu and Assaf Zeevi. Upper counterfactual confidence bounds: new optimism princi- ple for contextual bandits. arXiv preprint arXiv:2007.07876 2020.
[28] Mengxiao Zhang and Haipeng Luo. Online learning in contextual second-price pay-per-click auctions. International Conference on Artificial Intelligence and Statistics, 2024.
[29] Mengxiao Zhang, Yuheng Zhang, Olga Vrousgou, Haipeng Luo, and Paul Mineiro. Practi- cal contextual bandits with feedback graphs. Conference on Neural Information Processing Systems, 2023.
[30] Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, 4(2). 2022.
[31] Yinglun Zhu and Paul Mineiro. Contextual bandits with smooth regret: Efficient learning in continuous action spaces. International Conference on Machine Learning, 2022.
[32] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. International Conference Machine Learning, 2003.
11

---

A Additional Related Works
As mentioned, our work is closely related to the recent trend of designing contextual bandits algo- rithms for general function class. Specifically, under stochastic context, Xu and Zeevi [27], Simchi- Levi and Xu [25] designed algorithms based on an offline squared loss regression oracle and achieved optimal regret guarantees. Under adversarial context, there two lines of works. The first one reduces the contextual bandit problem to online regression [10, 11, 14, 31, 29], while second one is based on the ability sample from certain distribution over the function class using Markov chain Monte Carlo methods [30, 28J. We follow and greatly extend the ideas of all these approaches to design algorithms for contextual MNL bandits.
B Omitted Details in Section 3
B.1 Offline Regression Oracle
We start by proving Lemma 3.1, which shows that ERM strategy satisfies Assumption for the finite class and the linear function class.
Proof [of Lemma 3.1] We first show that our log loss function f satisfies the so- called strong 1-central condition (Definition of Grünwald and Mehta [17]), which states that there exists fo E F, such that for any f F,
B,2,8,i) (exp(-((1on)) (Aano)((oo(((SSS1111 - (ng( 0)) <
Indeed, by picking fo -,, we know that
(x, (S (S)
[s(S,
(s(
Es,s))
Σ (ESU(O)
pr(S, f)
=1
certifying the strong 1-central condition.
Now, we first consider the case where F is finite. Since [1(x) 2 for all x X' and E [N], we know that for any E [N]o, we have (defining fo(x)) 1)
= log 1 + EjEs f5(z)
K+1
S log 3
f((z)
Therefore, according to Theorem 7.6 of [26]. we know that given n i.id samples D ((1,, Ss, ix) ]kk()) ERM predictor fo guarantees that with probability 1 - d:
log log
E (a, (log (M(S
(x)),
n
Next, we consider the linear function class. In this case, we know that 2, - B [-200 for all
Ty. Therefore, boog (1(S, (x)) bounded by 2B + 2 N for all E X, f E F. and
i [N] since
boog (H(S, = log 1+ Eees exp(x) (z) 0 B)
1+K
< log
e-2B < 2B + log K,
exp(x, B)
and the same bound clearly holds as well for = O. Moreover, since
1 1 Ejes exp(x1.0 0 B)
Ejes exp(OT xj B)rr
Vo log
2,
exp(2,0 0 B)
Ejes exp(O' 2, B)
12

---

know that the e-covering number of king oF - an abuse of notation, define Z é (x, and denote flog ( by e (Z). Therefore, according Theorem 7.7 of [26], we know that given n i..d samples {(T,, Sk, ix) ke(n] ERM predictor fo guarantees that with probability 1 1 6:
( E is bounded by ( (161) where with
dB log K Koog( Bn) log 1
((,,,s) ( S B (1))
n
B.2 Analysis of Algorithm 1
We first prove the following lemma, which shows that the expected reward function R(S, u, r) is 1-Lipschitz in the value vector
Lemma B.1 Given E 1J and S C [N], function R(S, v, v', E [0, oo) u,)), R(S, r)] Eies l0; 10-- off-
Eies Tatl, I+ vi satisfies that for any
Proof Taking derivative with respect Uj for E S, we know that
V., R(S, (5 + Eies") U1) Ejes TyUg
Eies Vi (1+ Lies 0;)3
Tj
max
S1.
(1 ++EEss u²)2
11EEis is
where both inequalities are because r, E [0, 1]. This finishes the proof.
Next, we restate and prove Lemma 3.2. Lemma B.2 For any deterministic policy X 1] + S and any epoch m 2 2, we have
Rm (TT R(x) & V ((mm-1,77)
D. 1(0,))
-((11)))
Proof We proceed as:
(T) R(T)]
= [E( fm. R((()))) ((),
< <((,D)
Σ 1 (i ((mmm(( [t(
(11)
N 1fi E (()
N E
< Ba
we w.(gm-1la. (fm,(z)- (x))²
wi(9m-1l2,1
N i E ([x
N
$
B
E (a
Wi (0:(m-ilzzr) (fm.)(x) ft)))
we wilgm-11zz (2,T)
(CauchySchwarz ingubyaa inequality)
N
= VV
E(er))D
Σ
we (a((mm1lz,r) (mm:(x)-
= -VV((m-1,7
Σ (Uma(t)- ieS
(12)
where the first inequality uses the convexity of the absolute value function and Lemma B.I.
Next, to prove Lemma 3.3, we first prove the following key technical lemma (where denotes the all-one vector).
13

---

Lemma B.3 Let h(a) = 141 for a E [0, 1]". Then, for any a, b E [0, 11 we have
1
l1a -b12 - [I((a) - h(b)ll
2(d + 1)4
Proof The Jacobian matrix of h is
T
H(a) = 1+1 (1+1 a
Therefore, there exists 2 E conv((a,b) (]) such that |/(aa) - h(bil22 = (=) - b) It thus remains to figure the minimum singular value of (z)., which equal to the reciprocal of the spectral norm of Hz By Sherman-Morrison formula, we know that
H(z)-* = (1+ 2)(1+1:]]
Therefore, we have
(1 (1+ +1=+=(==2)) 12
= (1++1'=)([++13 1= +21 = =1=11
Note that for any u that is perpendicular to the subspace spanned by {-, 1}, we have (()) (1 uu. Therefore, there are d 2 identical eigenvalues 1 for the matrix [1+1 (()) Let the remaining two eigenvalues of 51+ (())- be λ
and X2. Note that
(1 (1+1 A + A2 = Trace [ + 12 +21 + =11]111] - (d (d-2
2 = det ((I (I )I =)
= = 21 2++21 =
2 2.
2d+2d+d* d.
Therefore, we know that max (λ1 A2) S \ X2 2 dd, meaning that
H())) s 2(1 +1 22 2 + d s 2(1 dd² + d +) 2(d 1)
This further means that the minimum singular value of (z) is least v2(d+1)² Therefore, can conclude that
[M((a) M(b)ll2 2 /2(d + 1)2 a bl(2,
leading to
[M(()) A(b)113 2 2(d 1)a |a b112.
Next, restate and prove Lemma 3.3.
Lemma B.4 For any S E S and v, E [0, 11ah we have
E(u- x2)² < [|p(S, v) p(S, v² 112 < 2Rin((S, Klo (M(S,v). Glo(H v²) (").))
iES
Proof The first inequality follows directly from Lemma B.3 using the fact that |S| K for all S E S. Consider the second inequality. For any μ, μí' E A([K)), by definition of fiog (M, i), we know that
Eizgy [log (p/,1) loog (n, :)] Erpp log [4 44
KL( 2 1lI 1'l1 2 || 11112.
where the first inequality is due to Pinsker's incquality.
14

---

B.3 Omitted Details in Section 3.1
In this section, we show omitted details in Section 3.1. For ease of presentation, we assume that the distribution over context-reward pair D has finite support. All our results can be directly generalized the case with infinite support following similar argument in Appendix A.7 of [25]. Define V X'x x [0. 1J > S as the set of all deterministic policy. Following Lemma 3 in [25], we know that for any context æ E X' and reward vector r E [0, 1J% and any stochastic policy q : X' x [0, 1] ->
A (S), there exists an equivalent randomized policy Q E (()) such that for all S E 8, x E A, and
r E [0, 1]%
(( = Σ -1( SQQ(().
NEW
Let Qm be the randomized policy induced by 4m- Define Reg(z) and Regm (TT) as:
Reg(z)= R( R(x), Regm Rm (TT Rm (m)) where R(x) and Rm (x) are defined Eq. (3) and a is the policy that maps each (æ, r) to the one-hot distribution supported on argmaxses R(S, r))
(13)
Following the analysis in [25]. show that analyze algorithms expected regret, only need to analyze the induced randomized policies implicit regret.
Lemma B.5 Fix any epoch m. For any round in this epoch, we have
(. (w...)) [R(T (2)) R(S,, (())) Σ Qm
Proof Direct caleulation shows that
= =B
R(T (1)) - Σ (1
SES
= =Barrr~
BlTp)(e,,1)) - 1 [
SES
Σ E 1att R(S))
SES NEW
Qm (it
NEW
Σ Qm (T)(
R(T(E))) (
NEW
Σ Reg(T)
which finishes the proof.
To prove main results for Algorithm 1, we define the following good event:
Event 1 For all epoch m 2 fm satisfies
(ttp://DDSmmmmmr......... < Erriog (Tm - Tm Tm 1/T²
(Log((((S i) (()))
According to Assumption 2, Event happens with probability at least since there at most epochs.
Although now we have all ingredients to analyze our e-greedy-type algorithm defined Eq. (4), to get the exact result in Theorem 3.4, we will in fact need refined version of Lemma 3.2, which eventually provides a tighter regret guarantec.
15

---

Lemma B.6 Suppose that Event I holds. Algorithm I with 9t defined in Eq. (4) satisfies for any deterministic policy y and any epoch m we have
NK
(T) R(T)) 1 8
Erring 2 1/T2,F)
Em-1
Proof Following Eq. (LI) in the proof of Lemma 3.2, we know that
[R((T) -[()
< (aan)DD
N NifiE x()
< (
Σ
Em-1
-
mm-1
N
(CauchySchwarz/ inequuuull inequality)
N ((1)))(0))))
N
< BlaryD
Bia,riDD
Em-1 (fm,i
(Jm,(())5((t)) (x))
6m-1
N
(CauchySchwarz inequualh inequality)
NK
Σ N
N
Em-1
- (fm:(())(((x))
(14)
Em-1
Since fm is the output of Algoft with i..d tuples {(1r, Se, it) im) according to Lemma 3.3 and Event we know that
64Err 64Err (m mm 1/T2,
32B (..) (2.r) [[) fm)))) ((8,f -
(Lemma 3.3)
32
B( (llu(f(), - -((()) (according Eq. (4))
N
N
N
mm-1
Σ
(using Lemma B.3 with d = 1)
N
Plugging the above inequality back to Eq. (14) and noticing that Tm = 2 1, we know that
NK
[mm((T) [[(T] 88,
8
Erriog (2m 2m (2m-211/12,
5m-1
Now are ready to prove Theorem 3.4
Theorem 3.4 Under Assumption 1 and Assumption 2, Algorithm 1 with qm defined in Eq. (4) and the optimal choice of Em ensures RegMNL > [[oga T o 2mmh (NKKErr (2m- ())
Proof Consider the regret within epoch m 2. Under Event we know that for any V,
Reg(s)) = R(TT.)) R(TT)
(R(TT-)) (mn(),)))) (Rm(T)) Rm (m + (Rm (x) R(T))
- (R(TT)-) ) -Rm ( )) (Rm (T)m)) - Rm((T) (T)) + (Rm (T)) - R(TT)
NK
5 (Re -Rm (x)) + 16
Erring (2m-2 1,//22,
(15)
Em-1
16

---

where the first inequality is because (m) 2 Rm(TT) by definition and the second in- equality is due Lemma B.6. Taking summation over all rounds within epoch m and picking cm (NK) Erring log
(2m-2, 1/T2, F),, we know that
Fo
E
Σ
max 11, I1, ((xa))
BE8
1= +1
-fmm+1 TR)
Σ
Qm (T)
(Lemma B.5)
NEWW
8
2m-1.B .B[(( - mm (Te((Tsm) Em)
(10)
2
+
((1 - El Reg((e ) + Em)
Event holds
T
(15)) 2m-1
NK
+ + 2
Em - 161
Erriog
T
6m-1
(iv)
2
2 (NKErrio (2m-2 1/T2 O
+
T
where (i) is due Tm 2 1 and the construction of gm (x, defined in Eq. (4); (ti) is because Event 1 holds with probability at least 1 T (iit) uses Eq. (15); and (iv) is due to the choice of m-- Taking summation all = 2, 3. ... [log2 T + epochs,
obtain that
Mlgg 77
RegMNL = Σ
0 2m (NKErT 12m-1,1/²2, 11),, (2m
m=1
B.4
Omitted Details in Section 3.2
First, we restate and prove Lemma 3.6, which shows that Jm defined in Eq. (5) enjoys a low-regret- high-dispersion guarantee.
Lemma B.7 For any x E X and r E [0, 1]N, the distribution qm (m( r) defined in Eq. (5) satisfies:
N(K + 1)a
max R(S*, [m(x), - (x.r) (m S*ES
(6)
7m
VS E S, Σ
E wi(gm (x, S N
Pm
max R(S SSES
R(S, fm()))))
(7)
K + 11
KES
Proof
It is direct that solving Eq. (5) is equivalent solving the following optimization
problem:
argmin Es-p max R(S*, sm,()) - (m))),)())))) r)] +
(K + 1)a
N Σ
log wx(p)
(16)
(ED(S)
S*ES
7m
i=1
Moreover, relaxing the constraint p from A(S) to {pe 11. : P(S) < 1) in Eq. (16) does not change the solution, since for any p 1]s such that Esesp(() < putting the remaining
1 Eses P(S) probability mass on argmax R(S*, (m)()) can only make the objective smaller.
Now, consider the Lagrangian form of Eq. (16) over this relaxed constraint and set the derivative with respect to p(S) zero. We obtain
(K (K+ 1)a
max R(S* fm((),r) R(S, (m)))) S*ES
Σ
A(S) + - 0, (17)
7m
wy w.(p)
17

---

Specifically, we have where À M 0 and A(S) 2 S, E S are the Lagrangian multipliers. Let p² E A(S) be the optimal solution of Eq. (16). Replacing p by p" Eq. (17), multiplying Eq. (17) by p² for each S, and taking the summation over S E S, we know that
Σe' ES)
max R(S" fm(=)) - R(S, (m STES
SES
1) (S) Σ wi(p*)
Σ SES
((((S)A(S) + A= O.
7m
Rearranging the terms, know that
Σ (S)
max R(S" (m(),)) - R(S, R(S,fm(()).))
S*ES
SES
(K + 1)t
Σ (S)
Σ
ΣP((S)A(S) -
Im
wi(p*)
SES
SES
(K + 1)4
N
Σ P((S) -
(complementary slackness)
w:(
I=1
SES: iES
N(K 1)a
N(K 11)
Tm
Ymm
N(K+1)*
proving Eq. (6). The above also implies that X x
since
Tm
Σ (S)
max R(S" (((s R(5, 2
STES
SES
Therefore, Eq. (17) implies that for any 5 S.
Σ SES
7m
max R(S" ((S, As A2)
wi(p')
(K + 1)
S.ES
T'm
max R(S" fm(().r) R(S, R(S,fm(()) + +N,
(K + 1)4
S*ES
where the last inequality uses the fact that X < N(K+1)* and As 2 0. This proves Eq. (7). The Now, to prove Theorem 3.7, we first prove the following lemma, which shows that the regret with respect to the true value function I* and the one respect to the value predictor fm within factor of 2 plus an additional term of order N(K+1)
7'm
Lemma B.8 Suppose that Event holds. For all epochs m 2, all rounds in this epoch, and all policies E V, with 7mm max {1, Erriog 2,1/T2.F) and À 33, we have
N(K+
Reg(T) 2 Regm (T) + AN(K 1)4
7m
Regm (T) 2. Reg(z)+ + AN(K 1)4
7mm
Proof We prove this by induction. The base case holds trivially. Suppose that this holds for all epochs with index less than m. Consider epoch m. We first show that Reg(T) < 2Reg, (T))
AN(K+1)* for all deterministic policy π E V. This holds trivially if V Errw 2.1/T2.5) S Tm
NIK+1M
N(K+1)* since Reg(z) < 1. Consider the case in which Tm = Erriog (2m 2,1/44,
Reg(z) - Reg... (TT) (R(TT-) R(TT) (Rm( Rm (T))
18

---

(R(TT-) ) - R(x)) - (Tg.))))) (m))
(mm((TT)) R((T))) + [ R((T)]
(1)
V (9m-111 ( (,,,D)),,, Smam-1(arr)
Σ (fm.(z))
LiES
V(4m-1. E(r.)) 8-am 1(2.))
Σ (fma(t)) LiE
(18)
where (i) is because Rm (mT 2 Rm(TT-) by definition and (ii) follows Lemma 3.2. Next, using Lemma 3.3 and Lemma B.3, since Event holds, we know that
4(K + 1)a ErrErriog (2th²2 ,172",
(Z,)) S-qm- ((a,r) fm())) MSS, (z))l 2 2(K + (
(Lemma 3.3)
Σ (mm)
2 (ar))DD Smmm (m,r))
(Lemma B.3)
LISS
Plugging the above back to Eq. (18), we obtain that
Reg(T) Regm (T)
(19)
S 2(K + 1)2 V (1m-1, TT. E (2 (2m-,,17 F)
+ 2(K + 1)² ((mm-1, x Err (2m-2 2,//T2,
(K V 19m TTx.)
(K + 1)² 19m-1, 1,
16 Erriog (2 2 1/T2,F)
87
8m
(AM-GM inequality)
(K 1) (9m--1,7
(K VV)V((m-z) 16N(K + 1)
(20)
87mm
8m
7m
where the last equality is because 7m that for all V
N(K+1) Erriog (2th 211/
According Lemma 3.6, we know
V ((mm-1, B(2,))-D
Σ wil 1il4m-1let (1 r)
iEn(arr)
7m-1
max R(S* ,r, (m- R(S, (m( (10))
B(z,r)
N + (K 11d
STES
7m-1 Rog Rogm-1(
= N +
(21)
(K + 1)4 1)4
Using Eq. (21), we bound the first and the second term in Eq. (20) follows
(K + V))(V((m-VVV)
N(K + 11*
I' Regm-1(m)
<
+
8%m
87m
8%m
(2Reg(T) + AN(K+1)
N(K + 1)2
Pm-1
mm-1
8%mm
8%m
X+1 -N(K + 1)4,
< 4
Rog(T)) +
(since Tince-m-11 S 7m
8%mm
(K 1) (gm TTp.)
N N(K (K 1)*
7m RReg. (TT
87/m
87mm
8mm
N(K 1)4
7m-1
(2Rog( (T.)) +
AN(K-1)**
7m-1
+
87mm
8mm
19

---

A+1
N(K + 1)²
(since Reg( 0 and 7m-1 S mm)
87m
Plugging back to Eq. (20), we know that
16N(K + 1)2
X+1 N(K 1)2
(T) Regm (TT)
Reg(T)) +
mm
4mm
Rearranging the terms, we know that
Reg(T) 4 Regm (TI)
12N(K + 1)a
X+1 N(K + 1)*
3mm
AN(K + 1)a
<2Regm (T)+
(22)
7mm
where the last inequality uses À = 33.
For the other direction, similar to Eq. (20), we know that
Regm (x) Rcg(TT)
(Rm (T (T(( )= Rm (T)) - (R((T))) - R(TT)
(R(TTm) R(T)) (R(TT R(T))
S 1Rm (T R(T (mm)smm)) Rm (T) - R[(T]]
2(K 1)²v (gm-1, Tm ErTioR (2 -2, 2,mm-,,//17 1/T2, F)
+ 2(K 1)2 V V(mm- Erriog (2m-2 2 1/T2,
(K
(K 1) ())VV((() (1m-1, (0n/V((mm1
+ 116m Errig (2 1/T2,
8m
87m
(AM-GM inequality)
(K + V (gm 1, fm.
(K + V) (1m-1, 16N(K + 11²
(23)
8m
8m
7m
where (1) is again because 7m
Errios (2m-2 F. Applying Eq. (21) to the first term in
N(K+1)
Eq. (23), know that
(K + V)*VV(m-11 (9m-1, Fm
8mm
N(K 1)a
7m 7m-1Rege Regm- (m
8mm
87m
7m- 1 (2Reg(TT..) + AN(K+1)"
N(K + 1)4
7mn-1
87m
87m
(8) X+1 1
2Reg AN(K + +1
N(K + 1)11 +
87
Ym
(6)
+ 3A
N(K + +1),
8mmm
where (1) is because 7m-1 S 7m and Eq. (22), and (ii) is due to Regm (TT 0. Plugging the above back to Eq. (23), we obtain that
+ 4A
16N + 1)4
Regm (T) < Reg(T) +
N(K + 1)
Reg(T))
8mm
4
Ym
AN(K + 1)*
2Rog(()) +
(since À -33)
7m
which finishes the proof.
Now we are ready to prove Theorem 3.7.
20

---

Algorithm 2 Contextual MNL Algorithms via an Online Regression Oracle
Input: online regression oracle Algon satisfying Assumption 3.
for f = 1, ...... . do
Obtain value predictor fe from oracle Algan-
Receive context H, E X and reward vector 7r E [0, 1j
Calculate yr E ASS) based on f((zz) and via either Eq. (9) or Eq. (10),
Sample S, ~ qt and receive purchase decision i, E St U (0) drawn according Eq. (1).
Feed the tuple (zz, St. it) to the oracle Algon-
Theorem 3.7 Under Assumption and Assumption 2, Algorithm with qm defined in Eq. (5) and the optimal choice of 7m ensures RegMNL
[log Σ
11 2 K2 / (2th 1
m=1
Proof Choose
max {I, Erriox (2 211/22
NIK+1J
for all m 2 2. Consider the regret within
epoch m 2 2. We first show that Enew Qm( Regm (TT) < to Lemma 3.6 and Lemma B.5, we know that
N(K+1) Concretely, according 7m
Σ (m (T) nEW
Σ (m(x)))))
max R(S", (m()))) R(S. ((S.sa(()))))) S*ES
N(K + +1
B
(24)
Ym
LSES
Now consider the regret within epoch m. Since Event I holds with probability at least 1 - 7, we know that
E
max R(S, 21, - R(S,, 21, 5r (zx)) SES
T= +1
(Tm+1 Tm Σ Qm (T)g()
Tm+1
Tm + (fm+1
Tm Tm)
Σ Qm (T Reg(()
Event holds
7'
LEE
(since Event holds with probability at least 1
2Regm + 33N (K + )
Tm-1
Tm
+ (Tm+1 Tm
Σ mm (T))
Event holds
T
Ym
LEEW
Tm++1
Tm
35/N (K +1
+ (Tm+1 Tm)
(using Eq. (24))
T
Ym
O
Tm+1 Tm + 2 2²
NErr (2m-2, (2m-2,1/22, 21
where (1) uses Lemma B.8. Taking summation over m = =2.3.... [log2 + 17. we conclude that
[log 27
RegMNL =0
Σ m=1
2m 2²
NErTlog (2m-1,14 11/T2,1/1
C Omitted Details in Section 4.1
In this section, we show omitted details in Scction 4.1.
21

---

C.1 Online Regression Oracle
We first show that there exists efficient online regression oracle for the finite class and the linear class.
Lemma C.1 For finite class and the linear class discussed in Lemina 3.1, the following concrete oracles satisfy Assumplion 3:
(Finite class) Hedge [16] with Reg = log log K
(Linear class) Online Gradient Descent [32] with Regiog (T,F)= O
Proof We first consider the finite function class. Since for any S E SE (0), and X, we have f((x)) 2 B, we know that flog f())) & log K+1 8
Therefore, Hedge [16] guarantees
that Regiog F) O (log K VTglog [F])
For the linear class, we first prove that given S E S, i SU (0} and x E RdxN, for any fo E F. (1SS fz)) is convex in f. Specifically, for Rd, h(u) log( ext) is convex in since for any a Rdd
T Vah(uaa= = a 1
( diag(u)
(1 (1Ju)² u)2 un )
EE uxa (MO Ei=1 uk)
(E u20rg)2
0,
u)²
where the last inequality is due to Cauchy-Schwar inequality. Define Rdd be the d-dimensional all-zero vector. Then, we know that biog (1,, Jo(r), i))
0 E
log (e so + Eyes e a--B (0Tx, B) lfi + 0} is convex in 0. Moreover, direct cal-
culation shows that
Ejes
B
Ij i)1, 1 Ejes n
1 0}
2
Therefore, Online Gradient Descent [32] guarantees that Regiog (T,F) O(BV)) since ||0||2 < B.
For completeness, we restate and prove Lemma 4.2, which is extended from the analysis in [14, 15]. Lemma C.2 Under Assumption I and Assumption 3, Algorithm 2 (with any qı) ensures
T
RegMNL <
E
dec f((x))) 2yReeing (T,F)
for any > O, where (g; v. is the Decision-Estimaatio Coefficient (DEC) defined as
[R(S" u.. r) - Esng [R(S, v", r)] - -EBs [I - ((S,u*))) (8)
max max U STES
Proof Following the regret decomposition in [14, 15), we decompose RegMNL as follows:
RegMNL
E
max R(S, ((S,,(((za)) (*x),, - Σ f
1=1
E
max R(S "(S"", (xx)))))) Σ (S)) ST
Σ
7
22

---

+ E
Σ SES
(AS, f
T
T
R(S", (R(S, ;01,,0",, Σ ((1))
< E
max
6S,' ES
de ((S))l((S,S((z))) u1s, o')1
SES
+7 E
Σ (u(ss,)((E))) - -
E
(gei f((
+7-1E EE
Σ
Ip(S,. - fr (25)
where the last equality by the definition of dac fe(ax))rr)) know that
According to Lemma 3.3, we
((((s, - ((
T
2E
Eoog (St. f((x))), 4)
(e - 2Regin (T,F).
(26)
Combining Eq. (25) and Eq. (26) finishes the proof.
C.2 Proof of Theorem 4.3
Next, we prove Theorem 4.3, which shows that similar to the stochastic environment, a simple but efficient e-greedy strategy achieves O (TT//(N K RRegiggTT (T, ()) expected regret.
Theorem 4.3
2 sequently, under Assumption I and Assumption 3, Algorithm with calculated via Eq. (9) and the optimal choice of E and ensurey RegMNL O(NNKReg, (T, ())
The strategy defined in Eq. (9) guarantees (q:3 fe(ax), = O NK + Con-
Proof We first prove that gt defined in Eq. (9) guarantees dec (2: fe(()), Specifically, for any S* and u* E [0, 1]N, know that
O
NK 75
R(S* . vr, Σ (S) v", Σ
-
SES
SES
(1)
10
f(.(Zz))+ + Σ (() Σ (u(S, u()) - (((s)f((x)))
SES
iES
+ R(S", f((()))))
Σ (() - E
- ((S,
SES
SES
2K
10 f1,((x:) +
S
+ R(S* f((2))))) Σ (())))( 7 Σ ((S)) uSS)
-1E
2
SES
SES
(18)
2K
10 fr,(2x)) + + + R(S ((()))))) max R(S, fe(x)))
SES
iE9.
N
7/E
(In((().fe(xz)))) - -
2N
23

---

(in)
2K
1 - f(,((1) +
+ f((e))(( SES
max R(S, fr(
EES*
7
(fes(e)) u2)²
64N
16NK
2K
+
78
NK
+E
7E
where (1) uses Lemma B.1, (it) is due to AM-GM inequality and |S| v K, (Mi is according to the
construction of q and R(S, v, E [0, 1]. (ir) uses Lemma B.3 with 1, and (v) is uses AM-GM
inequality and the fact that |S*| I K. Taking maximum over all 5 E S and 8* E [0, 1] proves
that dec., (g: fe(x)), rt) S
NK TE
+ +E)
Combining the above result with Lemma 4.2, we know that
RegMNL = O [
+ =T +
RRegin (T.F))
7
Picking y and optimally finishes the proof.
C.3 Proof of Theorem 4.5 and Theorem 4.6
In this section, we restate and prove Theorem 4.5, which proves that calculated via Eq. (10) guarantees that (ge r)) s O (NK*)
Theorem 4,5 The following distribution satisfies dec, (yt. Je(ss), SO ( NK
= argmax Es-g Je(s), (K + 1)4 N (EA(S)
log
(10)
(4)
Proof Since the construction of is the same as Eq. (5) with fm replaced by fe and 7m replaced by y, according Lemma 3.6, we know that qr satisfies that
max R(S f((()))))) - Σ (S) R(S, ((()))))) N(K + 1)a S*ES
(27)
7
SES
VS E 8, Σ Σu w.(g))
S N +
max
R(S" f((a)), RSS, f(()))))
(28)
(K + 1)a
55ES
iES
Using Eq. (27) and Eq. (28), we know that for any S* E and v' E [0, 1j
R(S", -. rr) - Σ (S) rd) - Σ (())) - M(S, (xx)))
SES
SES
< Σ 10 - ft,((x))) + Σ (() Σ 10 - St,(xz))
(according to Lemma B.
VESt
SES
iES
+ R(S* f((x)),rr) - Σ (S) fe(zz), - Σ ((() p(SSv*)11
SES
SES
N
Σ 10 fe,((z)) + Σ
wi(w:) - 10 - f(,(
(by definition of w. (v))))
+ R(S* R(S" f((2)),T1)
Σ (S)))((S - Σ (()) p(S, v² vl).
SE$
24

---

N
$
10 - fe,((+)) + Σ
wi(+t) 10 - fx,((())
1ES*
1=1
+
Je("),)))),)))) - Σ
qe (s (((3)))))
7 2(K + +14
Σe (r())
-vt (e,(x))
SES
SES
IES (according to Lemma 3.3)
Σ 10 - f(,(()))+ Σ ux(()) 10 - f(,((x))
EES*
N
+ R f((2)),)1) - Σ ((( f((z),, - 2(K + 1)a
7
Σ
w. wr(a))(t - ((xxe))
SES
2=1
N(K + 1)¹
(K [K+1) 1)a
+ R(S fc(x)).))) - Σ ((S))((
7
(w)
iES
SES
(AM-GM inequality)
N(K + 1)4
(K 1)+
max I((a),)) R(S" ((())))))) S.ES
7
(a)(
+ max R(So, fe( SoES
Σ ((())R(
SES
N(K + 1)at + (K+ +1 N
max R(So, fe(2)), - R(S" R(S". fa(()))))))) S0ES
(K + 1)a
max R(So, f((z),, R(S", f(((s)) N(K+1) 80ES
(according to Eq. (27) and Eq. (28))
3N(K + 1)
Taking maximum over all S* E S and v* E [0, 1 finishes the proof. Combining Lemma 4.2 and Theorem 4.5, able prove Theorem 4.6.
Theorem 4.6 Under Assumption and Assumption 3, Algorithum 2 with qi calculated via Eq. (10)
and the optimal choice of 7 ensures RegMNL = =0 K2 oT
Proof Combining Lemma 4.2 and Theorem 4.5, we know that Algorithm with a calculated via Eq. (10) satisfies that RegMNL = O NK* + Reeggg (T. Picking 7 = K2
Reging (T.)
finishes the proof.
D Regression Oracle for More Function Classes
In this section, we provide examples on regression oracles for broader Lipschitz function class satisfying Assumption 2 and Assumption
Lemma D.1 Suppose that F is a 1-Lipschitz function class defined as (fos(z) E { [3,1] [o, 1]d} where 3 0 and llfer, - fezulloo I ||01 - 02loo for all 01, O2 E [0, and i E [N]. Then, ERM strategy fo aargnin EGrSSie liog (ugg(u(S, f(x)), i) satisfies Assumption 2 with
Erriog (n, F)F) = dolg log 3 log 1
Moreover, there exists an algorithu satisfying Assump-
n tion 3 with Regiog -T (voa (TB) (o/3/)/)))
Proof We first consider the ERM strategy. For notational convenience, let Z (x, S, and with an abuse of notation, denote f(x), i) by ef (Z). According Theorem 7.7 in [26].
25

---

we know that for any == (f: 18.111 such that the e-covering number of ( :f F} is (e)), ERM predictor In guarantees that with probability - 6:
log log (V( ( n²
log(N
log
EzND (gg (Z)
(fog (2)
EznD
+ +
(29)
n
2 d
Now we show that for the 1-Lipschitz function class, .N()) 2 1
58 Specifically, define the
2 -rid of [0, 1jd as C(s) {0 e [0, 11d 0, E {0, _ "e,,..,, 1,, [N]]. For any 01 E [0, 1ja let 02 argmingec(e) ||0 01 By definition, we know that ||0 - 02 S f.. Given any = S.i).
Be
yog (Z) elog (2)
Phoog(u(S (Ir), 2) - Blog(1 (u(,, foz
1 Ejes S
+ log ( (0),(2))
< log
1fi + 0}
+ Ejes 10 (16)
1 + max 2 jES fo.. (x), iiEs f62 (2)}
+ log max(fe for 1 + #
log
+ min EEES jES/ S0., (1)), Ejes 80 (r)}
min (x), S0g (1)
Ejes s (2) Ejes fo)
loo
1+
Saim(Ejes fo. (z), EjeS f02,(1)}}
(1+
(5),( (a))
+ log
miin(Jrrs (x)) #1
( fo, (z)
+ l(i * 0) (fo, f0r (x) minn fo.
+ min
(Ejes for E (e)s
jE8
1
|S |S|BE
A5
$ 2
1 + B|S
2
S,
(30)
where the second incquality is by log(1 + < x for x 2 0 and the triangular inequality, and the third inequality is due to the Lipschitz property and the lower bound / on all values. Therefore,
know that.N(s ((s) S [C(=) S (1 n
Plugging in this to Eq. (29) proves the claim.
Next, we consider the adversarial environment. Consider applying Hedge [16] on the discretized set C(1/T). Since ( i) < log K+1 for all context æ, S S, and E {0), Hedge guarantees that
E
Σ
Eing (M (xxe),
foge (u (g(te)))
t=1
K
log /T log (((/TT)
K
o log df log(T/3)
for all θ C(/TT). Picking 0 argmingect//r) ||0 loo where f A for and applying Eq. (30) to and 6* finishes the proof.
E Omitted Details in Section 4.2
In this section, we show omitted details in Section 4.2. We start by deseribing the algorithm: maintains distribution pt over the value function class F, and each round samples f. from
26

---

Algorithm 3 Feel-Good Thompson Sampling for Contextual MNL bandits
Input: learning rate 17 O.
Initialize P1 E (FF) to be the uniform distribution over F.
for f = 1.2...... T do
Sample value function fi from Pt-
Receive context 2, and reward vector E [0, 1]N.
Select S, argmaxses R(S, (x()), rt) and receive feedback i, E (0).
Define the loss estimator f,, for each f E Fas
C.5 = 167 VESt
Σ (mi(S,, - [i =(])²=
max [(:))
(31)
SES
Update pt+1,f & Pt,f cxxp(-1fa,5))
Pt and selects the subset Sy that maximizes the expected reward with respect to the value function fi and the reward vector r.. After receiving the purchase decision de, the algorithm constructs a loss estimator f for each f E JF as defined in Eq. (31), and updates the distribution pr using a standard multiplicative update with learning rate r). See Algorithm 3.
The idea of the loss estimator Eq. (31) is follows. The first term measures how accurate f is via the squared distance between the multinomial distribution induced by and the true outcome. The second term, which is the highest expected reward one could get if the value function was f. subtracted from the first term serve as form of optimism (the "feel-good" part), encouraging exploration for those fss that promise high reward.
We extend the analysis of Zhang [30] and combine it with our technical lemmas (such Lemma 3.3 and Lemma B. to prove the following regret guarantee, where the term Zr should be interpreted certain complexity measure for the class F.
Theorem E.1 Under Assumption 1, Algorithm 3 with learning rate < 1 ensures RegMNL I (2 1YTT + 4n/T Zr, where Zr B [exp( -1) Σ1- (Pe, (el
Proof First, we decompose the regret as follows:
T
RegMNL = E
(max R(S, f(2,), R(S, (()).)()))))))) SES
E
(R(S f(()).))) - R
E
- max R(S, R ((s
E
(R(S, f((x)).)) R(S,, R(S).
E
max R(S, ((( max R(S (x2))
SES
SES
BFG.
(i)
T
T
E
Σ Σ (1.(( IES.
E
FG.
(32)
where (z) is because S. argmaxses R(S, fe((())))))) r²) according to Algorithm 3 and (ii) is using Lemma B.I. Here, "Feel-Good" term FG, measures the difference between the expected reward of the best subset given the value predictor ft and that of the true value predictor f*
27

---

Next, we analyze the first term Ei=1 Eies, (f) fi Given any context I' E 2. reward vector rt [0, 1]8, and value predictor f F, let S(f(x),)) argmaxses f(S, r). According to Algorithm 3, we have S, = -S(,, With a slight abuse of notation, for distribution Pt over F, let wx,i = Ey-n, [1 (()( be the probability that item is included in the selected set at round i. Let gr E A(S) be the distribution over S induced by Pt. meaning that (S) grpp, (L()((((((()))) = S}. Then, for each E [AV] for any μ 0, Exppi [1fa(z))) - (x() 1ii S((()))
1fi E S(f())), ww,((f((x)) ((()))
sope
(AM-GM inequality)
4pwar
+ frop [(f(())) (=)))
(33)
4u Taking a summation over all E [NV] we know that for any μ > O,
[(ra((r)) - (7(1)) (7
SES
- (3())) - S(J((A)) (1(
E
EE
Σ Eypp -z 1f1 (Hi
(4)
N
+
μE
Wr, Wr,ilBy-pe
Σ - (((a))))((a)))
4j
(68)
+ p.ess ru E prpe
(f(()) (x())
(34)
4p
LiS
where (1) uses Eq. (33) and (it) is by definition of we, and gr-
Let LS; Eies, (fi(z)) f² (2x))² ("Least Squares"). Combining Eq. (32) with Eq. (34), we
know that
NT 4u
T +
RegMNL I
FE
Σ
Es Es E Jmp, [SS]] - E Σ
FG.
(35)
To bound the last two terms in Eq. (35), using Lemma B.3 and the fact that é, is a drawn from the distribution ((,,, (xxe, re) and, we show in Lemma E.2 that
128n(K K 1)1 E Bymp, [LS,] Esi [FG,] S log E.i... Esapi Texp(-n(te, - Ee. + 4n.
(36)
Therefore, picking μ 128 and combining Eq. (35) and Eq. (36), we know that
RegMNL
Σ log E, 1, Eymps exp (-n (Pes (fes--eer)) ))]
T
< 32n +1 4n/T
E 17
(37)
To bound the last term in Eq. (37), we use the exponential weight update dynamic of pt. Following classic analysis of exponential weight update, we show in Lemma E.3 that
log Ei, (m,,s Esape EE
[exp(-n(E - -(, < Z. Z,-1
(38)
where Z, A -E log Eym exp (-17 Σt= (Eas - - ))]l Combining Eq. (37) and Eq. (38),
arrive at
T (Z. Z.-1)
RegMNL S N2n + +) + 4n7
28

---

Zr " where the last inequality uses the fact that Zo = 0.
s (K + 1)*T + 4n/"+
Lemma E.2 Suppose that 17 S 1. For any distribution Pt over F, we have
128n(K K + 114 By-p. [LS,] - E.se [FG,] S - --log B. Bypp, [exp(-n(e Fa.s))) 1]] + 4n,
where LS, and FG, are defined in the proof of Theorem E.I, and fe, is defined in Eq. (31).
Proof For notational convenience, define Ct,s = 1 it} for all i E [N]. Let Et, Ce.i f (xx)) for all i E St and E RN+1 is the corresponding vector. Consider the term -n (las (h.s-Eay -la..) for an arbitrary f E F.
11 (Fes Ress.)
1
Σ (Hu(S) f(xx)) - -c,i)²
1
( - 22,)
16 KES.
8K
1) max f(5,f(z))..) - max R(S, (xx),
1 Σ (St. f(x)) (x=)),(())))))))))))))))))))))))
16
iES.
+ max R(S, r() - max
(())))))
SES
SES
1
(ur f(x)) - f (a)),, (u + 28,,s)
16
iES:
LSp
+ (f).
where we define the first term as LS,, which we will show later how this term is related LS,, and the second term FG,(f) maxses R(S, f*x), r2) maxses R(S, rz))) (so FG, = (f))..). Consider the log of the expectation the exponent on both sides.
(Ce, - -R.. )
log Eyrp, S,
exp (m
LS, + nFGe(F) }
= log E, Snpp E St
exp
16
LS, ]&
(-16
< log E yrpp
2
exp
16
+
2 log Eymp, [exp (2nFG,(f))
- LS, )1)
< 2
log E J~upi
exp
log E~p (exp (2)FG
(39)
where the first inequality is by Cauchy-Sehwarz inequality and the second inequality is because E|r]² < E[ Next, we consider bounding each of the two terms. For the first term, since
Σ ((x()) - (f < [|n(Sr, f(x))) - ( (x:))) - 2'
2
iES,
we know that - (M(S,, (*(z) (x:)) & is a zero-mean, 1lln(S,, f(x)) -uuuu--aussaannn random variable given is and S,, meaning that
((Se, f- (xx)) ( -uu- Gaussian
- (u(S, (1(s,, (xxx))
u(S., ((x)))) e1) < exp (1 (1 IllSs, (xxx)) - (xs),
exp
29

---

Therefore, we know that
exp ( LS, )
S.
[ll(Ste ((xr)) (s ((.))) Ballees exp (- MSS, (o:)))
)
= =exp
"Tolll(S f(+))) - M(S,, (f (2)))))
exp
Then, since 1o (s f(x+)) mS f (xr)) < 5/4 using the fact that exp(x) & + n for [-1,0]. know that
(
Se
exp
(
$ 1
[p(Se, f(x))) u(Se, f (z:)))
32
1
< 1
-f(())))((=)))
64(K + 1)4
iESt
1 LSt:
64(K + 1)
where the second inequality because Lemma B.3. Further using the fact that log(1 x) s x for all 1, we have
1 exp (-gLis)) LiS:) )1) - 128(K + 1)a
log E Jope
LS..
(40)
2
Consider the second term in Eq. (39). Since v S 1 and [FG((f) & 1, using e" S x 2x for 1, we know that
1
log Esa [exp(2n)
- log (1 21)l + 2(2n)
2
2
S Tル ~~q [F) + 4nj²
(log(1 + x) S x)
, [FG,] + 4r72
(fe is drawn from ).)
Plugging the last bound and Eq. (40) into Eq. (39) and rearranging finishes the proof. The next lemma follows the classic analysis of multiplicative weight update algorithm. Lemma E.3 Algorithm guarantees that for each t E [T].
[exp(( Sxpp--n(ees - Pu.. < Ze Ze-1,
-E Es log Eeg |m,.8, Esape
where Ze -E log Eypps exp n Et (Ba)- and qe A(S) satisfies that
(S) Es-p. [1 5 argmaxg'es R(S', ((te),
Proof Let G., A exp (-1 (Rns (ast )) According to Algorithm 3, know that exp (n Erist
GI-1,f
Pt.
JPEF exp (-n (r.)) df JyEr GI-1,y
Then, according to the definition of Z,, we have
Z Z,
JIEr Gr
log
Jfer GL-1,5df
30

---

JYEF (xp1,/ep((n1f11 le d)df
log
JIEF Gr
log Eppp
eexp(-n(ee) - Re.s
S E Es log Be Sppppp exp( -nlem -L,
where the last inequality is due Jensen's inequality. Rearranging the terms finishes the proof. Next, we restate and prove Corollary 4.8.
Corollary E.4 Under Assumption 1, Algorithm 3 wensures RegMNL = =O(²² /NTTTIIN log Fl) for the finite class and RegMNL = O / log (BTK)) for the linear class.
Proof For finite function class F, since yi uniform, we have
T
Css - R
Zr = E log
exp
Σ
F
SEF
==1
1
Ee.g - Ee.s
E
log
exp
17
log |F].
F
t=1
Combining with Theorem E. and picking
log
we prove the first conclusion.
K
To prove our results for the linear class, we first show a more general results for parametrized Lips- chitz function class. Suppose that Fis d-dimensional parametrized function class defined
F = (Jo X + 10 1|01 s B, fo.s is a-Lipschitz with respect to || lll for all E [N])
(41)
Direct calculation shows that the linear function class we consider is an instance of Eq. (41) with
For function class satisfying Eq. (41), we aim show that Z, O(Kn + dlog(aBT)).
Specifically, we consider a small balbal around the true parameter 0": 22 (0 |10 0" ||
. ). Since F is a-Liisccitz with respect || ||2, we know that for any x E X, and any E [N].
[f,x(2) - fo- TK
(42)
Therefore, for any E Qr,
- - -Ze,orr
Σ (f0,(11) -4,1)
(lo,(()) - -2.))
16
16
VeS.
tES.
+ n max (o(:))) - max R(S, fo- (It), rt)
SES
SES
2
Σ (a.) for (xx)) +
max
R fe(r))) - max fe-
(43)
8
SES
SES
SES
Let S(fo- (xt). r+) argmaxses R(S, for (xt), rt). Then, we can further lower bound Eq. (43) as follows:
nle,, - Ee.lor)
(x,) - (t)
- 1 max R(S, for (x1),
SES
VES.
(
Σ
( fer Σ
(o,( ferx(1e)l
iES.
iES(J (2e).re)
(1)
1
8T T
31

---

where (1) is because Lemma B.1 and (iz) uses Eq. (42). This means that
)) )
Zr = E log E frng exp
79
Σ
Essoo
1=1
T
(1,50 Fe.tor))
S - (TT
inf exp BEir
S <dlog(aBB)
+
-1 = +
With the optimal choice of r R tees that for linear function class
Ndlog(aBTK) T
Theorem E.I shows that Algorithm 3 guaran-
=K(K3 RegMNL = (K2V VdNT (og(
32

---

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:
See 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.
fine to include aspirational goals as motivation as long as it 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: See Section
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 au- thors 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 ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because 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 ad- dress problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might 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]
33

---

Justification:
See Assumption 1, Assumption 2, Assumption 3, and the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proof's provided in appendix or supplemental material. Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does 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 novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to 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 a 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 sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
34

---

Answer:
[NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https: /ttss:/nniippeee cc/ des CodeSulomi i ssi iisionoolioo cy) for more details.
publ / guides/
While we encourage the release of code and data, we understand that this might not be possible, so No an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //niss. cc/
wttppcccppppccccccctccccc.cccc.a publpcplc/./o wwwp///gusss/ee/eeeoeooo /Codee////eeasee Code Sueeiusbiii. ssissiinn aeiionoooccyy for more details.
The authors should provide instructions on data access and preparation, including how 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information 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: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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 appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
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, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
35

---

is OK to report 1-sigma error bars, but one should state it. The authors should prefer- ably 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 figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, 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 or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /tps:://nerrri http//eerrspppppppeee/eee httpp//c//ppppcccctt/eteutueuuae
inee?
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code Ethics. The research con- ducted in this paper conforms with in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: This work is mostly theoretical, and we do not foresee any negative ethical or societal outcomes.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no socictal 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 spe- cific groups), privacy considerations, and security considerations.
36

---

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 as 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 mitiga- tion strategies (e.g., gated release of models, providing defenses addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility 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:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions 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 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 (e.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, pape rswi thcode 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.
37

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is 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 pa- per include the full text instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution 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, tion, or other labor should be paid at least the minimum wage 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 an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "rOuYWCneN0", "reviewer": "Reviewer_z4QH", "summary": "The paper presents three primary contributions for the contextual multinomial logit bandits considering both stochastic and adversarial contexts and rewards.\n\n-  a suite of algorithms proposed each with a different computation-regret trade-off.\n\n- advances existing regrets by removing the dependence on certain problem-dependent constants.\n\n- extends existing works to study a general value function class (1-Lipschitz function class).", "questions": "- Is this the first MNL bandit paper considering adversarial context and reward with online regression oracle?\n\n- Could you please address the second point in Weakness?\n\n- It is understandable that Algorithm 1 uses a doubling trick. But removing sampling history when feeding to offline regression oracle (4th line in Algorihtm 1) is not sensible in my opinion. Could you address this issue without affecting much of the analysis?\n\n- Since the paper studied MNL bandit with a general value function class (1-Lipschitz function class), do you think the regret guarantee can be characterized via eluder dimension?\n\nThe next two questions are related.\n\n- It is claimed after Corollary 3.5 that Algorithm 1 achieves a smaller regret dependence on $B$. Why is $B$ a parameter related to regret or $\\textbf{Err}_{\\log}$? According to the definition of linear class in Lemma 3.1, it is equivalent to assigning weight $e^{\\theta^\\top x_i}$ to item $i$ and $e^B$ to no-purchase. Since it is required that $\\lVert x_i \\rVert_2 \\leq 1$ and $\\lVert \\theta \\rVert_2 \\leq B$, it seems that all $B > 0$ are equivalent. \n\n- It is understandable the paper follows  [5, 9, 18] to assume the no-purchase option is the most likely outcome. Is this a necessary assumption without which the algorithm could fail? Is it possible to relax the assumption to something like \"the probability (or the weight in equation 1) of no-purchase is lower bounded by some $\\Delta>0$\"? I could imagine that the regrets are related to $\\Delta$ (other than $B$ ) since it can be hard to learn $f$ with a large probability of the no-purchase option. \n\nSome minor issues:\n\n- In line 173, should \"$\\epsilon \\rightarrow \\epsilon_m$\"?\n\n- The optimal choice of $\\epsilon_m$ and $\\gamma_m$ are given in Appendix. I suggest including them in the Algorithm sections to make the main paper self-contained.\n\n- If extending contextual MNL bandits to a general value function class setup is a major contribution, I would suggest to move the paragraph into the main paper.", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This seems to be the first contextual multinomial logit bandit paper considering adversarial context and reward with online regression oracle. I think the community will find this interesting.\n\n- The paper is generally well-written and technically solid.", "weaknesses": "- No experiments and simulation results are provided. But to be fair, there are other theoretical papers without experimental illustrations.\n\n- For stochastic contexts and adversarial rewards, [20] show there exists an efficient algorithm achieving $O(\\sqrt{T})$ regret. The adversarial reward setup is more general than the stochastic reward. So it is fair to compare it to corollary 3.5. Algorithm 1 has a larger regret upper bound $O( T^{\\frac{2}{3}})$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: For stochastic contexts and adversarial rewards, [20] show there exists an efficient algorithm achieving $𝑂(\\sqrt {𝑇})$ regret. The adversarial reward setup is more general than the stochastic reward. So it is fair to compare it to corollary 3.5. Algorithm 1 has a larger regret upper bound $O(T^{2/3})$.**\n\nA: Note that we did compare to [20] in the discussion after Corollary 3.5 (Line 195 more specifically) and highlighted that the regret bound of [20] depends on $\\kappa$ which can be exponential in $B$ in the worst case, while our bound only has polynomial dependence on $B$. We will add that our bound indeed has a worse dependence on $T$ as suggested.\n\n**Q2: Is this the first MNL bandit paper considering adversarial context and reward with online regression oracle?**\n\nA: Yes, to the best of our knowledge, our work is the first one considering the case where both the context and the reward can be adversarial (with or without regression oracles).\n\n**Q3: It is understandable that Algorithm 1 uses a doubling trick. But removing sampling history when feeding to offline regression oracle (4th line in Algorithm 1) is not sensible in my opinion. Could you address this issue without affecting much of the analysis?**\n\nA: While it might seem sensible to feed all the sampling history to the offline regression oracle due to the stochasticity of contexts and rewards, it does not work since the oracle requires **i.i.d. inputs of context-subset-purchase tuples** (not i.i.d. context-reward), and different epochs of our algorithm create different distributions over these tuples.\n\n**Q4: Since the paper studied MNL bandit with a general value function class (1-Lipschitz function class), do you think the regret guarantee can be characterized via eluder dimension?**\n\nA: Our regret bounds explicitly depend on the generalization error of ERM oracle in the stochastic environment, and the online regression regret (Algorithm 2) or the log partition function (Algorithm 3) in the adversarial environment. It is unclear to us how these quantities are directly related to the eluder dimension of a function class.\n\n**Q5: It is claimed after Corollary 3.5 that Algorithm 1 achieves a smaller regret dependence on $𝐵$. Why is $𝐵$ a parameter related to regret or $\\text{Err}_{\\log}$? According to the definition of linear class in Lemma 3.1, it is equivalent to assigning weight to item 𝑖 and $𝑒^𝐵$ to no-purchase. Since it is required that $||x_i||_2\\leq 1$ and $\\|\\|\\theta\\|\\|_2\\leq B$, it seems that all $𝐵>0$  are equivalent.**\n\nA: Your reparameterization is correct. However, a larger parameter $B$ makes the lowest possible weight for each item, $e^{-B}$ under your parameterization, smaller, which in turns makes the scale of the log loss larger and naturally increases the generalization error $\\text{Err}_{\\log}$.\n\n**Q6: It is understandable the paper follows [5, 9, 18] to assume the no-purchase option is the most likely outcome. Is this a necessary assumption without which the algorithm could fail? Is it possible to relax the assumption to something like \"the probability (or the weight in equation 1) of no-purchase is lower bounded by some $\\Delta>0$\"? I could imagine that the regrets are related to $\\Delta$ (other than $𝐵$) since it can be hard to learn $𝑓$ with a large probability of the no-purchase option.**\n\nA: If the weight for no-purchase is lower bounded by $\\Delta\\in(0,1)$ instead of $1$, all our regret bounds still hold with an extra factor of $1/\\Delta$ (explained below). Note that this is the opposite to what the reviewer suggested — while a large no-purchase probability seemingly makes it harder to learn $f^\\star$ at first glance, it in fact makes it easier because it leads to a better reverse Lipschitzness of $\\mu$, and consequently the difference in value is better controlled by the difference in log loss. As an extreme example, suppose that the no-purchase weight is 0. Then, no matter what value an item has, it will always be purchased by the customer if the selected subset contains only this item, revealing no information to the learner at all.\n\nTo see why our bounds hold with an extra factor of $1/\\Delta$, note that the only modification needed is Lemma B.3 (reverse Lipschitz Lemma): in this case we need to show the reverse Lipschitzness for $h(a) = a/(\\Delta+1^\\top a)$, and via a similar calculation, it can be shown that $\\Omega(\\Delta^2/d^4)\\|\\|a-b\\|\\|^2 \\leq \\|\\|h(a)-h(b)\\|\\|^2.$ The remaining analysis remains the same. \n\nThanks for pointing this out; we will add this discussion to the next version.\n\n\nThanks for the other suggestions and pointing out the typos. We will incorporate these in the next revision.", "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": "RSlY8XrFpM", "reviewer": "Reviewer_8kDH", "summary": "This paper introduces a couple of algorithms for contextual multinomial logit bandits under two different assumptions: i) stochastic contexts and rewards; ii) adversarial contexts and rewards. The theoretical analysis for algorithms for these two setups is pretty solid. Despite the contribution of this study, I believe that this paper needs more work to be done for acceptance.", "questions": "What is the relationship between \\pi and q_m?\n\nI am interested in how to apply the feel-good TS [30] for this setup.", "limitations": "Thank the authors for mentioning some limitations in the manuscript. The reviewer also agreed that solving eq (5) with polynomial time complexity is not easy work.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The setups for this work are pretty inclusive, representing that the contributions of the work can be significant. The literature review is also solid as well.", "weaknesses": "The paper seems incomplete, possibly due to page limits. Some algorithms and results are not fully described, and there is a lack of experimental validation to support the theoretical findings. The authors should better organize and present their work, focusing on the most important results. Additionally, many terms and mathematical notations are used without proper definitions or introductions.\n\nIn spite of repeated appearances of log loss regression, its definition has not been stated.\nThe definitions of Err_log, Reg_log, and ERM are missing.\nFor the function class F, what is the definition of |F| in Lemma 3.1? \nI think that many things other than these are missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: The paper seems incomplete, possibly due to page limits. Some algorithms and results are not fully described. Additionally, many terms and mathematical notations are used without proper definitions or introductions.**\n\nA: We strongly disagree with this comment. Could the reviewer kindly point out what algorithms and results are not fully described in this paper? For your examples of “terms and mathematical notations used without proper definitions or introductions”, they are in fact all explicitly defined (see below).\n\n**Q2: In spite of repeated appearances of log loss regression, its definition has not been stated.**\n\nA: This is not true. The definition of log loss regression is in Assumption 2 (offline) and Assumption 3 (online), with the definition of log loss in line 77.\n\n\n**Q3: The definitions of Err_log, Reg_log, and ERM are missing.**\n\nA: $\\text{Err}_{\\log}$ is defined in Assumption 2 and meant to be an abstract generalization error bound of the offline regression oracle, whose concrete form depends on its three arguments:\n$n$ (the number of samples), $\\delta$ (the failure probability), and $\\mathcal{F}$ (the function class) and is instantiated clearly in Lemma 3.1 and Lemma D.1 for three examples. \n\nSimilarly, $\\text{Reg}_{\\log}$ is defined in Assumption 3 and meant to be an abstract regret bound of the online regression oracle. Again, its concrete form for three examples are provided in Lemma 4.1 and Lemma D.1. \n\nWe also emphasize that deriving regret bounds with a general generalization error or regret bound of the regression oracle and then instantiating them for concrete examples is very common in this line of work; see [10, 11, 14, 25, 27, 29, 31].\n\nERM, “empirical risk minimizer” (line 119), is explicitly defined in Lemma 3.1 (line 123).\n\n**Q4: For the function class $\\mathcal{F}$, what is the definition of $|\\mathcal{F}|$ in Lemma 3.1?**\n\nA: $|\\mathcal{F}|$ represents the cardinality of the finite set $\\mathcal{F}$ (which is a rather standard notation).\n\n**Q5: What is the relationship between $\\pi$ and $q_m$?**\n\nA: $q_m: (\\mathcal{X}\\times r) \\mapsto \\Delta(\\mathcal{S})$ is a stochastic policy (mapping from a context-reward pair to a distribution over subsets (line 136)) that Algorithm 1 decides in each epoch m, while $\\pi: (\\mathcal{X}\\times r) \\mapsto \\mathcal{S}$ is a deterministic policy (mapping from a context-reward pair to a subset (line 143)) that appears in our analysis. We are not very certain about what specific “relationship” the reviewer is asking about.\n\n**Q6: I am interested in how to apply the feel-good TS [30] for this setup.**\n\nA: All details on applying feel-good TS to our setup can be found in Appendix E (as mentioned in Sec 4.2).", "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": "BYSuVh8xwc", "reviewer": "Reviewer_a6sS", "summary": "This paper addresses the problem of contextual multinomial logit (MNL) bandits with general value functions across both stochastic and adversarial settings. The authors develop a suite of algorithms for different settings and with different computation-regret trade-offs. The application to the linear case surpasses previous works in terms of both statistical and computational efficiency.", "questions": "1. Zhang and Sugiyama (2023) developed a computationally efficient algorithm for MLogB bandit problem. As MLogB and MNL are similar, how might their approach be adapted to the MNL bandit problem addressed in this paper to enhance computational efficiency?\n2. The authors claim that to ensure that no regret is possible, they make Assumption 1 in Line 96. Does this imply that achieving no regret is impossible in unrealizable scenarios? Could the authors provide some intuition about the reason?\n\nRef: Yu-Jie Zhang and Masashi Sugiyama. Online (Multinomial) Logistic Bandit: Improved Regret and Constant Computation Cost. In NeurIPS 2023.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Novelty of the Setting**: This paper is the first to explore contextual MNL bandits with general value functions, representing a significant expansion in the scope of MNL bandit problems. The setting is both novel and interesting.\n2. **Innovative Techniques**: The introduction of several new techniques to tackle the complexities introduced by general value functions is commendable. The methods may inspire the following works and be useful in other areas.\n3. **Improved Efficiency**: The application of these methods to linear cases shows improvements over previous works in both statistical and computational efficiency, making this a valuable contribution to the field.", "weaknesses": "1. **Computational Inefficiency**: The Feel-Good Thompson sampling algorithm, as discussed, lacks computational efficiency, even for linear cases, which could limit its practical applicability.\n2. **Lack of Experimental Validation**: The absence of empirical experiments to verify the theoretical claims weakens the paper's impact. Experimental results are crucial for validating the effectiveness and practicality of the proposed methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: Computational Inefficiency: The Feel-Good Thompson sampling algorithm, as discussed, lacks computational efficiency, even for linear cases, which could limit its practical applicability.**\n\nA: We acknowledge that the Feel-Good Thompson sampling is not efficient theoretically. However, empirically, as mentioned in [30], one can apply stochastic gradient Langevin dynamic (SGLD) to approximately sample a value function.\n\n**Q2: [Zhang and Sugiyama, 2023] developed a computationally efficient algorithm for MLogB bandit problem. As MLogB and MNL are similar, how might their approach be adapted to the MNL bandit problem addressed in this paper to enhance computational efficiency?**\n\nA: While MLogB and MNL share some common components, their setups are in fact quite different: MNL considers the case where multiple items (decision) are chosen at each round and one of these items is selected according a multinomial distribution, while MLogB considers the case where a single item (decision) is chosen at each round but the outcome is one of the $K+1$ different possible outcomes (including the no-purchase outcome) following a multinomial distribution. Since the computational inefficiency for MNL usually comes from the fact that the number of possible subsets is large, we do not see how ideas from MLogB can be utilized to improve the computational efficiency of our algorithms. \n\n**Q3: The authors claim that to ensure that no regret is possible, they make Assumption 1 in Line 96. Does this imply that achieving no regret is impossible in unrealizable scenarios? Could the authors provide some intuition about the reason?**\n\nA: Making a realizability assumption is standard for bandit problems with function approximation [10, 11, 14, 29, 31], usually for the purpose of obtaining efficient algorithms via reduction to regression, but it does not imply that no regret is impossible without it. In fact, for contextual bandits, applying the classical (but inefficient) Exp4 algorithm [Auer et al., 2002] achieves the optimal regret even without the realizability assumption.\n\n[Auer et al., 2002]: Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire, The Nonstochastic Multiarmed Bandit Problem, SIAM Journal on Computing, 2002.", "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": "hKxQqeTkQX", "reviewer": "Reviewer_AgtJ", "summary": "This paper considers MNL bandits with a general value function. The authors first examine the case of stochastic contexts and rewards. They suggest an epoch-based algorithm with an offline regression oracle. With uniform exploration, the algorithm achieves a regret bound, specifically $T^{2/3}$ for finite and linear classes. By utilizing better exploration, it achieves $\\sqrt{T}$ for these classes. Next, they consider adversarial contexts and rewards. With uniform exploration, the algorithm achieves a regret bound of $T^{5/6}$ for finite or linear classes. With better exploration, it achieves $T^{3/4}$. Lastly, by using Thompson sampling, it achieves a $\\sqrt{T}$ regret bound. Importantly, the suggested algorithms do not depend on $\\kappa$, implying better dependency on $B$.", "questions": "1. Is there any insight about how regret bounds do not include the dependency on $\\kappa$ for linear class? Or does it include $\\kappa$ when it is applied to the standard contextual MNL model?\n\n2. Feel-good Thompson sampling algorithm seems to outperform other algorithms including stochastic or adversarial cases. Is there a benefit to using epoch-based algorithms over the Thompsom sampling method?", "limitations": "I could not find a discussion on the limitations of this work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper first considers a general value function for MNL bandits. \n\n- They propose algorithms for stochastic or adversarial context and rewards and provide regret analysis.\n\n- The regret bound has better dependency on $B$ (without including $\\kappa$) compared to previously suggested ones.", "weaknesses": "1. The regret bound has supper linear dependency on $K$ for $\\sqrt{T}$ in Corollayr 3.8, 4.7, 4.8.\n2. It does not provide regret lower bounds so it is hard to know the tightness of the achieved regret upper bounds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: Is there any insight about how regret bounds do not include the dependency on 𝜅 for linear class? Or does it include 𝜅 when it is applied to the standard contextual MNL model?**\n\nA: The intuition on why we do not have $\\kappa$ dependency is that most previous MNL works (e.g. [7,20,23]) adopt a UCB-type approach, which first approximates the true weight parameter $\\theta$ via MLE and constructs a confidences set based on this approximation. The $\\kappa$ dependence will unavoidably appear from this approximation step. Different from previous approaches, we reduce the learning problem to a regression problem, and show that the regret directly depends on the regression error. This key step enables us to remove the dependency on $\\kappa$.\n\n**Q2: Feel-good Thompson sampling algorithm seems to outperform other algorithms including stochastic or adversarial cases. Is there a benefit to using epoch-based algorithms over the Thompson sampling method?**\n\nA: As shown in Table 1, while Feel-good Thompson sampling outperforms other algorithms in terms of regret upper bound, it is not computationally efficient (even for a small $K$) since it is unclear how to sample the value function at each round efficiently. On the other hand, our other algorithms, including those epoch-based algorithms, are computationally efficient (at least for small $K$).\n\n**Q3: I could not find a discussion on the limitations of this work.**\n\nA: We do discuss the limitations of our work in various places (as acknowledged by other reviewers), such as the assumption on the no-purchase option, the inefficiency of solving Eq. (5) when K is large (Lines 214-215), and the disadvantage of FGTS algorithm (Lines 322-326),", "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:

Meta-review: The paper is the first to address the contextual multinomial logit bandit problem with general value functions. New algorithms are proposed under two settings, the stochastic iid setting and the adversarial setting. Algorithms using regression oracles and the log-barrier regularized strategy are proposed, which are the first that do not depend on problem-specific constant that can be exponentially large in the norm of weights. 

Reviewers acknowledge the innovativeness of the proposed method and the contribution to the more challenging setting (with general value function class) than the setting addressed before (with generalined linear function class).

Authors are encouraged to incorporate the following comments in their final version of the paper:

- super-linear dependency in K : while the proposed method removes dependency on $\kappa$ in the regret bound, it has super-linear dependency on K. This limitation should be mentioned in the text.
- reason why iid assumption is needed should be stated in detail
- reason why dependence on B is unavoidable should be stated in detail (ex, as the authors stated in their rebuttal, further normalizing theta would restrict the representation power of the function class)
Decision: Accept (poster)