Contextual Multinomial Logit Bandits with General Value Functions

Authors: mengxiao  zhang
haipeng  luo
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 11:03:28

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.

Main paper: 
 introduction: 
 As assortment recommendation becomes ubiquitous in real-world applications such as online retailing and advertising, the multinomial (MNL) bandit model has attracted great interest in the past decade since it was proposed by Rusmevichientong et al. [24] . It involves a learner and a customer interacting for T rounds. At each round, knowing the reward/profit for each of the N available items, the learner selects a subset/assortment of size at most K and recommend it to the customer, who then purchases one of these K items or none of them according to a 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 a 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 a 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 a contextual MNL bandit model with a general value function class that contains the ground truth (a standard realizability assumption), and develop a suite of algorithms for different settings and with different computation-regret trade-off.More specifically, in Section 3, we first consider a stochastic setting where the context-reward pairs are i.i.d. samples of an unknown distribution. Following the work by Simchi-Levi and Xu [25] for contextual bandits, we reduce the problem to an easier offline log loss regression problem and propose two strategies using an offline regression oracle: one with simple and efficient uniform exploration, 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 Table 1 : Comparisons of results for contextual MNL bandits with T rounds, N items, size-K assortments, and a d-dimensional linear value function class with norm bounded by B. All previous results depend on a problem-dependent constant κ that is exp(2B) in the worst case, while ours (in gray) do not. The notation O(•) hides logarithmic dependency on all parameters. In the last column, ✓ means polynomial runtime in all parameters; ✓ means polynomial only when K is a constant; and means not polynomial even for a small K. rate regression result (Lemma 3.1), a "reverse Lipschitzness" for the MNL model (Lemma 3.3), and a certain "low-regret-high-dispersion" property of the log-barrier regularized strategy (Lemma 3.6).ContextNext, in Section 4, we switch to the more challenging adversarial setting where the context-reward 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 Decision-Estimation Coefficient (DEC) [10, 14] . We then show that, somewhat surprisingly, the same log-barrier regularized strategy we developed for the stochastic setting leads to a 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-dispersion property, which to our knowledge is 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 running 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 to five new results, summarized in Table 1 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 a problem-dependent constant κ that can be exponentially large in the norm of the weight vector B, none of our results depends on κ. In fact, our best results (Corollary 4.8) even has only logarithmic dependence on B, a potential doubly-exponential improvement compared to prior works. 1 • The regret bounds of our two algorithms that make use of an online regression oracle are dimension-free, despite not having the optimal √ T -dependence (Corollary 4.4 and Corollary 4.7).• Our results are the first to handle completely adversarial context-reward pairs. 2 1 One caveat is that, following [5, 9, 18] , we assume that no-purchase is the most likely outcome by normalizing the range of the values to [0, 1], making it only a subclass of the one considered in [19, 7, 20] . However, we emphasize that the bounds presented in Table 1 have been translated accordingly to fit our setting. Also note that the κ dependence in [23] is in the form of √ T /κ + κ (so not necessarily increasing in κ), but it only holds for uniform rewards. 2 Agrawal et al. [2] also considered adversarial contexts and rewards, but there is a technical issue in their analysis as pointed out by the authors. Even if corrected, their results still depend on κ while ours do not.Related works. The (non-contextual) MNL model was initially studied in [24] , followed by a line of improvements [3, 4, 6, 5, 22] . Specifically, Agrawal et al. [3, 5] introduced a UCB-type algorithm achieving O( √ N T ) regret and proved a lower bound of Ω( N T /K). Subsequently, Chen and Wang [6] enhanced the lower bound to Ω( √ N T ), matching the upper bound up 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, 2] , and uniform reward over items [23] . However, as mentioned, all these works consider (generalized) linear value functions, and our work is 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 a general function class. Due to space limit, we defer the discussion to Appendix A. 
notations and preliminary: 
 Notations. Throughout this paper, we denote the set {1, 2, . . . , N } for some positive integer N by [N ] and {0, 1, 2, . . . , N } by [N ] 0 . For a vector u ∈ R N , we use u i to denote its i-th coordinate, and for a matrix W ∈ R N ×M , we use W j to denote its j-th column. For a set S, we denote by ∆(S) the set of distributions over S, and by conv(S) the convex hull of S. Finally, for a distribution µ ∈ ∆([N ] 0 ) and an outcome i ∈ [N ] 0 , the corresponding log loss is ℓ log (µ, i) = -log µ i .We consider the following contextual MNL bandit problem that proceeds for T rounds. At each round t, the learner receives a context x t ∈ X for some arbitrary context space X and a reward vector r t ∈ [0, 1] N which specifics the reward of N items. Then, out of these N items, the learner needs to recommend a subset S t ⊆ S to a customer, where S ⊆ 2 [N ] is the collection of all subsets of [N ] with cardinality at least 1 and at most K for some K ≤ N . Finally, the learner observes the customer purchase decision i t ∈ S t ∪ {0}, where 0 denotes the no-purchase option, and receives reward r t,it , where for notational convenience we define r t,0 = 0 for all t (no reward if no purchase). The customer decision i t is assumed to follow an MNL model:EQUATIONwhere f ⋆ : X → [0, 1] N is an unknown value function, specifying the costumer's value for each item under the given context. The MNL model above implicitly assumes a value of 1 for the nopurchase option, making it the most likely outcome. This is a standard assumption that holds in many realistic settings [5, 9, 18] .To simplify notation, we define µ :S × [0, 1] N → ∆([N ] 0 ) such that µ i (S, v) ∝ v i 1[i ∈ S ∪ {0}]with the convention v 0 = 1. The purchase decision i t is thus sampled from the distribution µ(S t , f ⋆ (x t )). In addition, given a reward vector r ∈ [0, 1] N (again, with convention r 0 = 0), we further define the expected reward of choosing subset S ∈ S under context x ∈ X asR(S, v, r) = E i∼µ(S,v) [r i ] = i∈S µ i (S, v)r i = i∈S r i v i 1 + i∈S v i .The goal of the learner is then to minimize her regret, defined as the expected gap between her total reward and that of the optimal strategy with the knowledge of f ⋆ :Reg MNL = E T t=1 max S∈S R(S, f ⋆ (x t ), r t ) - T t=1 R(S t , f ⋆ (x t ), r t ) .To ensure that no-regret is possible, we make the following assumption, which is standard in the literature of contextual bandits.The learner is given a function classF = {f : X → [0, 1] N } which contains f ⋆ .Our hope is thus to design algorithms whose regret is 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 to Alg off and obtain f m . Define a stochastic policy q m : X × [0, 1] N → ∆(S) via either Eq. ( 4) or Eq. (5) .for t = τ m + 1, • • • , τ m+1 doObserve context x t ∈ X and reward vector r t ∈ [0, 1] N . Sample S t ∼ q m (x t , r t ) and recommend it to the customer. Observe customer's purchase decision i t ∈ S t ∪ {0}, drawn according to Eq. (1). context x t and the reward x t are chosen. In the next two sections, we will discuss both the easier stochastic case where (x t , r t ) is jointly drawn from some fixed and unknown distribution, and the harder adversarial case where (x t , r t ) can be arbitrarily chosen by an adversary.We first prove the following lemma, which shows that the expected reward function R(S, v, r) is 1-Lipschitz in the value vector v.Lemma B.1 Given r ∈ [0, 1] N and S ⊆ [N ], function R(S, v, r) = i∈S rivi 1+ i∈S vi satisfies that for any v ′ , v ∈ [0, ∞) N , |R(S, v, r) -R(S, v ′ , r)| ≤ i∈S |v i -v ′ i |.Proof Taking derivative with respect to v j for j ∈ S, we know that∇ vj R(S, v, r) = r j (1 + i∈S v i ) -j∈S r j v j (1 + i∈S v i ) 2 ≤ max r j 1 + i∈S v i , i∈S v i (1 + i∈S v i ) 2 ≤ 1,where both inequalities are because r j ∈ [0, 1]. This finishes the proof. □Next, we restate and prove Lemma 3.2.Lemma B.2 For any deterministic policy π : X × [0, 1] N → S and any epoch m ≥ 2, we have|R m (π) -R(π)| ≤ V (q m-1 , π) • E (x,r)∼D,S∼qm-1(x,r) i∈S (f m,i (x) -f ⋆ i (x)) 2 .Proof We proceed as:EQUATION)EQUATION)where the first inequality uses the convexity of the absolute value function and Lemma B.1. □Next, to prove Lemma 3.3, we first prove the following key technical lemma (where 1 denotes the all-one vector).Lemma B.3 Let h(a) = a 1+1 ⊤ a for a ∈ [0, 1] d . Then, for any a, b ∈ [0, 1] d , we have 1 2(d + 1) 4 a -b 2 2 ≤ h(a) -h(b) 2 2 .Proof The Jacobian matrix of h isH(a) = 1 1 + 1 ⊤ a I - 1a ⊤ (1 + 1 ⊤ a) 2 .Therefore, there exists z ∈ conv({a, b}) such that h(a) -h(b) 2 = H(z)(a -b) 2 . It thus remains to figure out the minimum singular value of H(z), which is equal to the reciprocal of the spectral norm of H(z) -1 . By Sherman-Morrison formula, we know thatH(z) -1 = (1 + 1 ⊤ z)(I + 1z ⊤ ).Therefore, we haveH(z) -1 H(z) -⊤ = (1 + 1 ⊤ z) 2 (I + 1z ⊤ )(I + 1z ⊤ ) ⊤ = (1 + 1 ⊤ z) 2 (I + 1z ⊤ + z1 ⊤ + z ⊤ z11 ⊤ ).Note that for any u that is perpendicular to the subspace spanned by {z, 1}, we haveH(z) -1 H(z) -⊤ u = (1 + 1 ⊤ z) 2 u.Therefore, there are d -2 identical eigenvalues 1 for the matrix1 (1+1 ⊤ z) 2 H(z) -1 H(z) -⊤ . Let the remaining two eigenvalues of 1 (1+1 ⊤ z) 2 H(z) -1 H(z) -⊤ be λ 1 and λ 2 . Note that λ 1 λ 2 = det (I + 1z ⊤ )(I + z1 ⊤ ) = (1 + 1 ⊤ z) 2 , λ 1 + λ 2 = Trace(I + 1z ⊤ + z1 ⊤ + z ⊤ z11 ⊤ ) -(d -2) = 2 + 21 ⊤ z + z ⊤ z1 ⊤ 1 = 2 + 21 ⊤ z + d • z ⊤ z ≤ 2 + 2d + d 2 .Therefore, we know that max{λ 1 , λ 2 } ≤ λ 1 + λ 2 ≤ 2 + 2d + d 2 , meaning thatH(z) -1 H(z) -⊤ 2 ≤ 2(1 + 1 ⊤ z) 2 (1 + d + d 2 ) ≤ 2(1 + d) 2 (d 2 + d + 1) ≤ 2(d + 1) 4 .This further means that the minimum singular value of H(z) is at least1 √ 2(d+1) 2 . Therefore, we can conclude that h(a) -h(b) 2 ≥ 1 √ 2(d + 1) 2 a -b 2 , leading to h(a) -h(b) 2 2 ≥ 1 2(d + 1) 4 a -b 2 2 .□ Next, we restate and prove Lemma 3.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 t ∈ [T ], x t and r t are jointly drawn from a fixed and unknown distribution D. Following the literature of contextual bandits, we aim to reduce the problem to an easier and better-studied offline regression problem and only access the function class F through some offline regression oracle. Specifically, an offline regression oracle Alg off takes as input a set of i.i.d. context-subsetpurchase tuples and outputs a predictor from F with low generalization error in terms of log loss, formally defined as follows.Assumption 2 Given n samples D = {(x k , S k , i k )} n k=1 where each (x k , S k , i k ) ∈ X × S × [N ] 0 is an i.i.d. sample of some unknown distribution H and the conditional distribution of i k is µ(S k , f ⋆ (x k )), with probability at least 1 -δ the offline regression oracle Alg off outputs a function f D ∈ F such that:EQUATION)for some function Err log (n, δ, F) that is non-increasing in n.Given the similarity between MNL and multi-class logistic regression, assuming such a 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 ℓ log (µ(S, f (x)), i), when seen as a function of f , satisfies the so-called strong 1-central condition [17, Definition 7] , which might be of independent interest; see Appendix B.1 for details.Lemma 3.1 The ERM strategy f D = argmin f ∈F (x,S,i)∈D ℓ log (µ(S, f (x)), i) satisfies Assumption 2 for the following two cases:• (Finite class) F is a finite class of functions with image [β, 1] N for some β ∈ (0, 1) and Err log (n, δ, F) = O log K /β log |F | /δ n . • (Linear class) X ⊆ {x ∈ R d×N | x i 2 ≤ 1, ∀i ∈ [N ]}, F = {f θ,i (x) = e θ ⊤ xi-B | θ 2 ≤ B},andErr log (n, δ, F) = O dB log K log(Bn) log 1 δ n, for some B > 0. Given Alg off , we now outline a natural algorithm framework that proceeds in epochs with exponentially increasing length (see Algorithm 1): At the beginning of each epoch m, the algorithm feeds all the context-subset-purchase tuples from the last epoch to the offline regression oracle Alg off and obtains a value predictor f m . Then, it decides in some way using f m a stochastic policy q m , which maps a context x and a reward vector r ∈ [0, 1] N to a distribution over S. With such a policy in hand, for every round t within this epoch, the algorithm simply samples a subset S t according to q m (x t , r t ) and recommend it to the customer.We will specify two concrete stochastic policies q m in the next two subsections. Before doing so, we highlight some key parts of the analysis that shed light on how to design a "good" q m . The first step is an adaptation of Simchi-Levi and Xu [25, Lemma 7] , which quantifies the expected reward difference of any policy under the ground-truth value function f ⋆ versus the estimated value function f m . Specifically, for a deterministic policy π : X × [0, 1] N → S mapping from a context-reward pair to a subset, we define its true expected reward and its expected reward under f m respectively as (overloading the notation R):R(π) = E (x,r)∼D [R(π(x, r), f ⋆ (x), r)] , R m (π) = E (x,r)∼D [R(π(x, r), f m (x), r)] . (3)Moreover, for any ρ ∈ ∆(S), define w(ρ) ∈ [0, 1] N such that w i (ρ) = S∈S:i∈S ρ(S) is the probability of item i being selected under distribution ρ, and for any stochastic policy q, further define a dispersion measure for a deterministic policy π as V (q, π) = E (x,r)∼D i∈π(x,r)1wi(q(x,r)) (the smaller V (q, π) is, the more disperse the distribution induced by q is). Using the Lipschitzness (in v) of the reward function R(S, v, r) (Lemma B.1), we prove the following. |R m (π) -R(π)| ≤ V (q m-1 , π) • E (x,r)∼D,S∼qm-1(x,r) i∈S (f m,i (x) -f ⋆ i (x)) 2 .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. 4 i∈SLemma 3.3 For any S ∈ S and v, v ⋆ ∈ [0, 1] N , we have 1 2(K+1)(v i -v ⋆ i ) 2 ≤ µ(S, v) -µ(S, v ⋆ ) 2 2 ≤ 2E i∼µ(S,v ⋆ ) [ℓ log (µ(S, v), i) -ℓ log (µ(S, v ⋆ ), i)] .The first equality establishes certain "reverse Lipschitzness" of µ and is proven by providing a universal lower bound on the minimum singular value of its Jacobian matrix, which is new to our knowledge. It implies that if two value vectors induce a 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, it suffices to control their log loss difference, which is exactly the job of the offline regression oracle.Therefore, combining Lemma 3.2 and Lemma 3.3, we see that to design a good algorithm, it suffices to find a stochastic policy that "mostly" follows argmax S R(S, f m (x t ), r t ), the best decision according to the oracle's prediction, and at the same time ensures high dispersion for all π such 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.As a warm-up, we first introduce a simple but efficient ε-greedy-type algorithm that ensures reasonable dispersion by uniformly exploring all the singleton sets. Specifically, at epoch m, given the value predictor f m from Alg off , q m (x, r) ∈ ∆(S) is defined as follows for some ε m > 0:EQUATIONIn other words, with probability 1 -ε, the learner picks the subset achieving the maximum reward based on the reward vector r and the predicted value f m (x); with the remaining ε probability, the learner selects a uniformly random item i ∈ [N ] and recommend only this item, which clearly ensures V (q m , π) ≤ KN εm for any π. Based on our previous analysis, it is straightforward to prove the following regret guarantee. Theorem 3.4 Under Assumption 1 and Assumption 2, Algorithm 1 with q m defined in Eq. ( 4) and the optimal choice of ε m ensures Reg MNL =⌈log 2 T ⌉ m=1 O 2 m (N KErr log (2 m-1 , 1/T 2 , F)) 1 3.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, we immediately obtain the following corollary: Corollary 3.5 Under Assumption 1, Algorithm 1 with q m defined in Eq. ( 4), the optimal choice of ε m , and ERM as Alg off ensuresReg MNL = O (N K log K β log(|F|T )) 1 3 T 2 3for finite class and While these O(T 2 /3 ) regret bounds are suboptimal, Theorem 3.4 provides the first computationally efficient algorithms for contextual MNL bandits with an offline regression oracle for a general function class. Indeed, computing argmax S ⋆ ∈S R(S ⋆ , f m (x), r) can be efficiently done in O(N 2 ) time according to [24, Section 2.1] . Moreover, for the linear case, the ERM oracle can indeed be efficiently (and approximately) implemented because it is a convex optimization problem over a simple ball constraint. Importantly, previous regret bounds for the linear case all depend on a problemdependent constant κ = max ∥θ∥≤B,S∈S,i∈S,t∈[T ] 1 µi(S,f θ (xt))µ0(S,f θ (xt)) , which is exp(2B) in the worst case [7, 20, 23] , but ours only has polynomial dependence on B.Reg MNL = O (dBN K log K)Next, we show that a more sophisticated construction of q m in Algorithm 1 leads to better exploration and consequently improved regret bounds. Specifically, q m is defined as (for some γ m > 0):EQUATION)The first term of the optimization objective above is the expected reward when one picks a subset according to ρ and the value function is f m , while the second term is a certain log-barrier regularizer applied to ρ, penalizing it for putting too little mass on any single item. This specific form of regularization ensures that q m enjoys a low-regret-high-dispersion guarantee, as shown below.Lemma 3.6 For any x ∈ X and r ∈ [0, 1] N , the distribution q m (x, r) defined in Eq. ( 5) satisfies:EQUATION)∀S ∈ S, i∈S 1 w i (q m (x, r)) ≤ N + γ m (K + 1) 4 max S ⋆ ∈S R(S ⋆ , f m (x), r) -R(S, f m (x), r) . (7)Eq. ( 6) states that following q m (x, r) does not incur too much regret compared to the best subset predicted by the oracle, and Eq. (7) states that the dispersion of q m (x, 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 a large dispersion while a bad one can have a smaller dispersion since we do not care about estimating its true reward very accurately. Such a refined dispersion guarantee intuitively provides a much more adaptive exploration scheme compared to uniform exploration. This kind of low-regret-high-dispersion guarantees is in fact very similar to the ideas of Simchi-Levi and Xu [25] for contextual bandits (which itself is similar to an earlier work by Agarwal et al. [1] ). 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 a 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 it in poly(|S|) = poly(N K ) time since it is a concave problem over ∆(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 Theorem 3.7 Under Assumption 1 and Assumption 2, Algorithm 1 with q m defined in Eq. ( 5) and the optimal choice of γ m ensuresReg MNL = O ⌈log 2 T ⌉ m=1 2 m K 2 N Err log (2 m-1 , 1/T 2 , F) .Similar to Section 3.1, we instantiate Theorem 3.7 using the following two concrete classes: Corollary 3.8 Under Assumption 1, Algorithm 1 with q m defined in Eq. ( 5), the optimal choice of γ m , and ERM as Alg off ensures Reg MNL = O K 2 T log K β log(|F|T ) for the finite class andReg MNL = O K 2 dBN T log(BT )The dependence on T in these O( √ T ) regret bounds is known to be optimal [6, 7] . Once again, in the linear case, we have no exponential dependence on B, unlike previous results. 
contextual mnl bandits with adversarial contexts and rewards: 
 In this section, we move on to consider the more challenging case where the context x t and the reward vector r t 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.In the first approach, we follow a 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 Alg on that follows the protocol below: at each round t ∈ [T ], Alg on outputs a value predictor f t ∈ conv(F); then, it receives a context x t , a subset S t , and a purchase decision i t ∈ S t ∪ {0}, all chosen arbitrarily, and suffers log loss ℓ log (µ(S t , f t (x t )), i t ). 4 The oracle is assumed to enjoy the following regret guarantee.The predictions made by the online regression oracle Alg on ensure:E T t=1 ℓ log (µ(S t , f t (x t )), i t ) - T t=1 ℓ log (µ(S t , f ⋆ (x t )), i t ) ≤ Reg log (T, F),for any f ⋆ ∈ F and some regret bound Reg log (T, F) that is non-decreasing in T .While most previous works on contextual bandits assume a squared loss online oracle, log loss is more than natural for our MNL model (it was also used by Foster and Krishnamurthy [11] to achieve first-order regret guarantees for contextual bandits). The following lemma shows that Assumption 3 again holds for the finite class and the linear class.• (Finite class) Hedge [16] with Reg log (T, F) = O( T log |F| log K β );• (Linear class) Online Gradient Descent [32] with Reg log (T,F) = O(B √ T ).Unfortunately, unlike the offline oracle, we are not able to provide a "fast rate" (that is, O(1) regret) 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 as an 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, a natural algorithm framework works as follows: at each round t, the learner first obtains a value predictor f t ∈ conv(F) from the regression oracle Alg on ; then, upon seeing context x t and reward vector r t , the learner decides in some way a distribution q t ∈ ∆(S) based on f t (x t ) and r t , and samples S t from q t ; finally, the learner observes the purchase decision i t and feeds the tuple (x t , S t , i t ) to the oracle Alg on (see Algorithm 2 in Appendix C). To shed light on how to design a good sampling distribution q t , we show a general lemma that holds for any q t . Lemma 4.2 Under Assumption 1 and Assumption 3, Algorithm 2 (with any q t ) ensuresReg MNL ≤ E T t=1 dec γ (q t ; f t (x t ), r t ) + 2γReg log (T, F)for any γ > 0, where dec γ (q; v, r) is the Decision-Estimation Coefficient (DEC) defined asmax v ⋆ ∈[0,1] N max S ⋆ ∈S R(S ⋆ , v ⋆ , r) -E S∼q [R(S, v ⋆ , r)] -γE S∼q µ(S, v) -µ(S, v ⋆ ) 2 2. (Our DEC adopts the idea of Foster et al. [14] for general decision making problems: the termR(S ⋆ , v ⋆ , r) -E S∼q [R(S, v ⋆ , r)]represents the instantaneous regret of strategy q against the best subset S ⋆ with respect to reward vector r and the worst-case value vector v ⋆ , and the termE S∼q [ µ(S, v) -µ(S, v ⋆ ) 2 2] is the expected squared distance between two distributions induced by v and v ⋆ , which, in light of the second inequality of Lemma 3.3, lower bounds the instantaneous log loss regret of the online oracle. Therefore, a small DEC makes sure that the learner's MNL regret is somewhat close to the oracle's log loss regret Reg log , formally quantified by Lemma 4.2. With the goal of ensuring a small DEC, we again propose two strategies similar to Section 3.Uniform Exploration. We start with a simple uniform exploration approach similar to Eq. ( 4):EQUATION)where ε > 0 is a parameter specifying the probability of uniformly exploring the singleton sets. We prove the following results for this simple algorithm.Theorem 4.3 The strategy defined in Eq. ( 9) guarantees dec γ (q t ; f t (x t ), r t ) = O( N K γε + ε). Consequently, under Assumption 1 and Assumption 3, Algorithm 2 with q t calculated via Eq. ( 9) and the optimal choice of ε and γ ensures Reg MNL = O (N KReg log (T, F))1 3 T 2 3 .Combining this with Lemma 4.1, we immediately obtain the following corollary.Corollary 4.4 Under Assumption 1, Algorithm 2 with q t defined in Eq. ( 9) and the optimal choice of ε and γ ensuresReg MNL = O (N K log K β ) 1 3 T 5 6for the finite class (with Hedge as Alg on ) andReg MNL = O (N KB) 1 3 T 5 6for the linear class (with Online Gradient Descent as Alg on ).While these regret bounds have a large dependence on T , the advantage of this algorithm is its computational efficiency as discussed before.Better Exploration. Can we improve the algorithm via a strategy with an even smaller DEC? In particular, what happens if we take the extreme and let q t be the minimizer of dec γ (q; f t (x t ), r t )? 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 in 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 γ (q t , f t (x t ), r t ) ≤ O N K 4 γ :EQUATION)A 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-barrier 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 to the case for contextual bandits where the same inverse gap weighting strategy works for both cases [10, 25] , but to 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-dispersion property of Lemma 3.6, which is a 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-high-dispersion property.Combining Theorem 4.5 with Lemma 4.2, we obtain the following improved regret.Theorem 4.6 Under Assumption 1 and Assumption 3, Algorithm 2 with q t calculated via Eq. ( 10) and the optimal choice of γ ensuresReg MNL = O K 2 N T Reg log (T, F) .Corollary 4.7 Under Assumption 1, Algorithm 2 with q t defined in Eq. (10) and the optimal choiceof γ ensures Reg MNL = O K 2 N log K β T 3 4 (log |F|) 1 4for the finite class (with Hedge as Alg on )andReg MNL = O K 2 √ N BT 3 4for the linear class (with Online Gradient Descent as Alg on ).We remark that if the "fast rate" discussed after Lemma 4.1 exists, we would have obtained the optimal √ T -regret here. Despite having worse dependence on T , however, our result for the linear case enjoys three advantages compared to 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 1 again for detailed comparisons.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.1). In terms of the dependence on T , Algorithm 3 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, a potential doubly-exponential improvement compared to prior works. The caveat is that there is no efficient way to implement the algorithm even for the linear case and even when K is a constant (unlike all our other algorithms). We leave the question of whether there exists a 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 a general value function class under a realizability assumption. For both the stochastic and the adversarial settings, we propose a suite of algorithms with different computational-regret trade-off. Notably, none of our regret bounds suffers from the exponentially large dependence on some problem dependent constant in the case with linear value functions. One interesting future direction is to improve the poly(K, N ) dependence in our regret upper bounds, which seems to require new techniques. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: This paper does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal 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 societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: This paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (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, paperswithcode.com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: As mentioned, our work is closely related to the recent trend of designing contextual bandits algorithms for a 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 are two lines of works. The first one reduces the contextual bandit problem to online regression [10, 11, 14, 31, 29] , while the second one is based on the ability to sample from a certain distribution over the function class using Markov chain Monte Carlo methods [30, 28] . We follow and greatly extend the ideas of all these approaches to design algorithms for contextual MNL bandits.We start by proving Lemma 3.1, which shows that ERM strategy satisfies Assumption 2 for the finite class and the linear function class.Proof [of Lemma 3.1] We first show that our log loss function ℓ log (µ(S, f (x)), i) satisfies the socalled strong 1-central condition (Definition 7 of Grünwald and Mehta [17] ), which states that there exists f 0 ∈ F , such that for any f ∈ F ,E (x,S,i)∼H [exp(-(ℓ log (µ(S, f (x)), i) -ℓ log (µ(S, f 0 (x)), i)))] ≤ 1.Indeed, by picking f 0 = f ⋆ , we know thatE (x,S,i)∼H [exp(-(ℓ log (µ(S, f (x), i)) -ℓ log (S, f ⋆ (x), i)))] = E (x,S) E i∼µ(S,f ⋆ (x)) µ i (S, f ) µ i (S, f ⋆ ) = E (x,S)   i∈S∪{0} µ i (S, f )   = 1,certifying the strong 1-central condition.Now, we first consider the case where F is finite. Since f i (x) ≥ β for all x ∈ X and i ∈ [N ], we know that for any i ∈ [N ] 0 , we have (defining f 0 (x) = 1)ℓ log (µ(S, f (x)), i) = log 1 + j∈S f j (x) f i (x) ≤ log K + 1 β .Therefore, according to Theorem 7.6 of [26] , we know that given n i.i.d samples D = {(x k , S k , i k )} k∈[n], ERM predictor f D guarantees that with probability 1 -δ:E (x,S,i)∼D ℓ log (µ(S, f D (x)), i) ≤ E (x,S,i)∼D [ℓ log (µ(S, f ⋆ (x)), i)] + O log K β log |F | δ n .Next, we consider the linear function class. In this case, we know thatx ⊤ i θ -B ∈ [-2B, 0] for all x i . Therefore, ℓ log (µ(S, f (x)), i) is bounded by 2B + 2 ln N for all x ∈ X , f ∈ F , S ∈ S and i ∈ [N ] since ℓ log (µ(S, f (x)), i) = log 1 + j∈S exp(x ⊤ j θ -B) exp(x ⊤ i θ -B) ≤ log 1 + K e -2B ≤ 2B + 2 log K,and the same bound clearly holds as well for i = 0. Moreover, since∇ θ log 1 + j∈S exp(x ⊤ j θ -B) exp(x ⊤ i θ -B) 2 = j∈S exp(θ ⊤ x j -B)x j 1 + j∈S exp(θ ⊤ x j -B) -x i 2 ≤ 2,we know that the ε-covering number ofℓ log •F ≜ {ℓ f log : f ∈ F } is bounded by 16B ε d, where with an abuse of notation, we define Z ≜ (x, S, i) and denote ℓ log (µ(S, f (x)), i) by ℓ f log (Z). Therefore, according to Theorem 7.7 of [26] , we know that given n i.i.d samplesD = {(x k , S k , i k )} k∈[n] ,ERM predictor f D guarantees that with probability 1 -δ:E (x,S,i)∼D ℓ log (µ(S, f D (x)), i) ≤ E (x,S,i)∼D [ℓ log (µ(S, f ⋆ (x)), i)] + O dB log K log(Bn) log 1 δ n . □ B.For any S ∈ S and v, v ⋆ ∈ [0, 1] N , we have 1 2(K+1) 4 i∈S(v i -v ⋆ i ) 2 ≤ µ(S, v) -µ(S, v ⋆ ) 2 2 ≤ 2E i∼µ(S,v ⋆ ) [ℓ log (µ(S, v), i) -ℓ log (µ(S, v ⋆ ), i)] .Proof The first inequality follows directly from Lemma B.3 using the fact that |S| ≤ K for all S ∈ S. Consider the second inequality. For any µ, µ ′ ∈ ∆([K]), by definition of ℓ log (µ, i), we know thatE i∼µ [ℓ log (µ ′ , i) -ℓ log (µ, i)] = E i∼µ log µ i µ ′ i = KL(µ, µ ′ ) ≥ 1 2 µ -µ ′ 2 1 ≥ 1 2 µ -µ ′ 2 2 ,where the first inequality is due to Pinsker's inequality. □ B.3 Omitted Details in Section 3.1In 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 to the case with infinite support following a similar argument in Appendix A.7 of [25] . Define Ψ : X ×[0, 1] N → S as the set of all deterministic policy. Following Lemma 3 in [25] , we know that for any context x ∈ X and reward vector r ∈ [0, 1] N , and any stochastic policy q : X × [0, 1] N → ∆(S), there exists an equivalent randomized policy Q ∈ ∆(Ψ) such that for all S ∈ S, x ∈ X , andr ∈ [0, 1] N , q(S|x, r) = π∈Ψ {π(x, r) = S}Q(π).Let Q m be the randomized policy induced by q m . Define Reg(π) and Reg m (π) as:EQUATIONwhere R(π) and R m (π) are defined in Eq. ( 3) and π f is the policy that maps each (x, r) to the one-hot distribution supported on argmax S∈S R(S, f (x), r).Following the analysis in [25] , we show that to analyze our algorithms expected regret, we only need to analyze the induced randomized policies implicit regret.For any round t in this epoch, we haveE (xt,rt)∼D,St∼qm(xt,rt) [R(π f ⋆ (x t , r t ), f ⋆ (x), r t ) -R(S t , f ⋆ (x), r t )] = π∈Ψ Q m (π)Reg(π).Proof Direct calculation shows thatE (xt,rt)∼D,St∼qm(xt,rt) [R(π f ⋆ (x t , r t ), f ⋆ (x), r t ) -R(S t , f ⋆ (x), r t )] = E (xt,rt)∼D R(π f ⋆ (x t , r t ), f ⋆ (x), r t ) - S∈S q m (S|x t , r t )R(S, f ⋆ (x), r t ) = E (xt,rt)∼D R(π f ⋆ (x t , r t ), f ⋆ (x), r t ) - S∈S π∈Ψ {π(x t , r t ) = S}Q m (π)R(S, f ⋆ (x), r t ) = E (x,r)∼D S∈S π∈Ψ {π(x, r) = S}Q m (π) (R(π f * (x, r), f ⋆ (x), r) -R(S, f ⋆ (x), r)) = E (x,r)∼D π∈Ψ Q m (π) (R(π f * (x, r), f ⋆ (x), r) -R(π(x, r), f ⋆ (x), r)) = π∈Ψ Q m (π)E (x,r)∼D [R(π f * (x, r), f ⋆ (x), r) -R(π(x, r), f ⋆ (x), r)] = π∈Ψ Q m (π)Reg(π),which finishes the proof. □To prove our main results for Algorithm 1, we define the following good event:Event 1 For all epoch m ≥ 2, f m satisfies E (x,r)∼D,S∼qm-1(x,r),i∼µ(S,f ⋆ (x)) [ℓ log (µ(S, f m (x)), i) -ℓ log (µ(S, f ⋆ (x)), i)] ≤ Err log (τ m -τ m-1 , 1/T 2 , F).According to Assumption 2, Event 1 happens with probability at least 1 -1 T since there are at most T epochs.Although now we have all ingredients to analyze our ε-greedy-type algorithm defined Eq. ( 4), to get the exact result in Theorem 3.4, we will in fact need a refined version of Lemma 3.2, which eventually provides a tighter regret guarantee.Lemma B.6 Suppose that Event 1 holds. Algorithm 1 with q t defined in Eq. ( 4) satisfies that for any deterministic policy π ∈ Ψ and any epoch m ≥ 2, we have|R m (π) -R(π)| ≤ 8 N K ε m-1 • Err log (2 m-2 , 1/T 2 , F).Proof Following Eq. ( 11) in the proof of Lemma 3.2, we know thatEQUATION)Since f m is the output of Alg off with i.i.d tuples {(x t , S t , i t )} τm t=τm-1+1 , according to Lemma 3.3 and Event 1, we know that64Err log (τ m -τ m-1 , 1/T 2 , F) ≥ 32E (x,r)∼D,S∼qm-1(x,r) µ(S, f m (x)) -µ(S, f ⋆ (x)) 2 2 (Lemma 3.3) ≥ 32ε m-1 N N i=1 E (x,r)∼D µ({i}, f m (x)) -µ({i}, f ⋆ (x)) 2 2(according to Eq. ( 4))≥ ε m-1 N N i=1 E (x,r)∼D N i=1 (f m,i (x) -f ⋆ i (x)) 2 .(using Lemma B.3 with d = 1)Plugging the above inequality back to Eq. ( 14) and noticing that τ m = 2 m-1 -1, we know that|R m (π) -R(π)| ≤ 8 N K ε m-1 • Err log (2 m-2 , 1/T 2 , F).Now we are ready to prove Theorem 3.4Theorem 3.4 Under Assumption 1 and Assumption 2, Algorithm 1 with q m defined in Eq. ( 4) and the optimal choice of ε m ensures Reg MNL =⌈log 2 T ⌉ m=1 O 2 m (N KErr log (2 m-1 , 1/T 2 , F)) 1 3.Proof Consider the regret within epoch m ≥ 2. Under Event 1, we know that for any π ∈ Ψ,EQUATION)where the first inequality is because R m (π fm ) ≥ R m (π f ⋆ ) by definition and the second inequality is due to Lemma B.6. Taking summation over all rounds within epoch m and picking ε m = (N K)1 3 Err 1 3 log (2 m-2 , 1/T 2 , F), we know that E τm+1 t=τm+1 max S∈S R(S, x t , f ⋆ (x t )) -R(S t , x t , f ⋆ (x t )) = (τ m+1 -τ m )E π∈Ψ Q m (π)Reg(π) (Lemma B.5) (i) ≤ 2 m-1 • E [((1 -ε m )Reg(π fm ) + ε m )] (ii) ≤ 2 m-1 T + 2 m-1 E ((1 -ε m )Reg(π fm ) + ε m ) Event 1 holds (iii) ≤ 2 m-1 T + 2 m-1 ε m + 16 N K ε m-1 • Err log (2 m-2 , 1/T 2 , F) (iv) = 2 m-1 T + O 2 m-1 N KErr log (2 m-2 , 1/T 2 , F) 1 3, where (i) is due to τ m = 2 m-1 -1 and the construction of q m (x, r) defined in Eq. ( 4); (ii) is because Event 1 holds with probability at least 1 -1 T ; (iii) uses Eq. ( 15); and (iv) is due to the choice of ε m . Taking summation over all m = 2, 3, . . . log 2 T + 1 epochs, we can obtain that First, we restate and prove Lemma 3.6, which shows that q m defined in Eq. ( 5) enjoys a low-regrethigh-dispersion guarantee.Reg MNL = ⌈log 2 T ⌉ m=1 O 2 m N KErr log (2 m-1 , 1/T 2 , F)Lemma B.7 For any x ∈ X and r ∈ [0, 1] N , the distribution q m (x, r) defined in Eq. ( 5) satisfies:EQUATION)∀S ∈ S, i∈S 1 w i (q m (x, r)) ≤ N + γ m (K + 1) 4 max S ⋆ ∈S R(S ⋆ , f m (x), r) -R(S, f m (x), r) . (7)Proof It is direct to see that solving Eq. ( 5) is equivalent to solving the following optimization problem:EQUATION)Moreover, relaxing the constraint ρ from ∆(S) to ρ ∈ [0, 1] S : S∈S ρ(S) ≤ 1 in Eq. ( 16) does not change the solution, since for any ρ ∈ [0, 1] S such that S∈S ρ(S) < 1, putting the remaining 1 -S∈S ρ(S) probability mass on argmax S ⋆ ∈S R(S ⋆ , f m (x), r) 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 ρ(S) to zero. We obtainEQUATIONwhere λ ≥ 0 and λ(S) ≥ 0, S ∈ S are the Lagrangian multipliers. Let ρ ⋆ ∈ ∆(S) be the optimal solution of Eq. ( 16). Replacing ρ by ρ ⋆ in Eq. ( 17), multiplying Eq. ( 17) by ρ ⋆ (S) for each S ∈ S, and taking the summation over S ∈ S, we know that S∈S ρ ⋆ (S) maxS ⋆ ∈S R(S ⋆ , f m (x), r) -R(S, f m (x), r) - (K + 1) 4 γ m S∈S ρ ⋆ (S) i:i∈S 1 w i (ρ ⋆ ) - S∈S ρ ⋆ (S)λ(S) + λ = 0.Rearranging the terms, we know that S∈S ρ ⋆ (S) maxS ⋆ ∈S R(S ⋆ , f m (x), r) -R(S, f m (x), r) = (K + 1) 4 γ m S∈S ρ ⋆ (S) i: i∈S 1 w i (ρ ⋆ ) + S∈S ρ ⋆ (S)λ(S) -λ = (K + 1) 4 γ m N i=1 1 w i (ρ ⋆ ) S∈S: i∈S ρ ⋆ (S) -λ (complementary slackness) = N (K + 1) 4 γ m -λ ≤ N (K + 1) 4 γ m ,proving Eq. ( 6). The above also implies that λ ≤ N (K+1)4 γm since S∈S ρ ⋆ (S) max S ⋆ ∈S R(S ⋆ , f m (x), r) -R(S, f m (x), r) ≥ 0.Therefore, Eq. ( 17) implies that for any S ∈ S, i: i∈S1 w i (ρ ⋆ ) = γ m (K + 1) 4 max S ⋆ ∈S R(S ⋆ , f m (x), r) -R(S, f m (x), r) -λ S + λ ≤ γ m (K + 1) 4 max S ⋆ ∈S R(S ⋆ , f m (x), r) -R(S, f m (x), r) + N,where the last inequality uses the fact that λ ≤ N (K+1) 4 γm and λ S ≥ 0. This proves Eq. (7) . □ Now, to prove Theorem 3.7, we first prove the following lemma, which shows that the regret with respect to the true value function f ⋆ and the one respect to the value predictor f m is within a factor of 2 plus an additional term of order N (K+1) 4 γm .policies π ∈ Ψ, with γ m = max 1, N (K+1) 4Err log (2 m-2 ,1/T 2 ,F ) and λ = 33, we haveReg(π) ≤ 2 • Reg m (π) + λN (K + 1) 4 γ m , Reg m (π) ≤ 2 • Reg(π) + λN (K + 1) 4 γ m .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(π) ≤ 2Reg m (π) + λN (K+1) 4 γm for all deterministic policy π ∈ Ψ. This holds trivially ifN (K+1) 4 Err log (2 m-2 ,1/T 2 ,F ) ≤ 1 since Reg(π) ≤ 1. Consider the case in which γ m = N (K+1) 4Err log (2 m-2 ,1/T 2 ,F ) . Specifically, we haveEQUATION)where (i) is because R m (π fm ) ≥ R m (π f ⋆ )4(K + 1) 4 Err log (2 m-2 , 1/T 2 , F) ≥ 2(K + 1) 4 E (x,r)∼D, S∼qm-1(x,r) µ(S, f m (x)) -µ(S, f ⋆ (x)) 2 2 (Lemma 3.3) ≥ E (x,r)∼D, S∼qm-1(x,r) i∈S (f m,i (x) -f ⋆ i (x)) 2 . (Lemma B.3)Plugging the above back to Eq. ( 18), we obtain thatEQUATIONEQUATION)where the last equality is becauseγ m = N (K+1) 4Err log (2 m-2 ,1/T 2 ,F ) . According to Lemma 3.6, we know that for all π ∈ Ψ,EQUATION)Using Eq. ( 21), we bound the first and the second term in Eq. ( 20) as follows(K + 1) 4 V (q m-1 , π) 8γ m ≤ N (K + 1) 4 8γ m + γ m-1 Reg m-1 (π) 8γ m ≤ N (K + 1) 4 8γ m + γ m-1 2Reg(π) + λN (K+1) 4 γm-1 8γ m ≤ 1 4 Reg(π) + λ + 1 8γ m • N (K + 1) 4 , (since γ m-1 ≤ γ m ) (K + 1) 4 V (q m-1 , π f ⋆ ) 8γ m ≤ N (K + 1) 4 8γ m + γ m-1 Reg m-1 (π f ⋆ ) 8γ m ≤ N (K + 1) 4 8γ m + γ m-1 2Reg(π f ⋆ ) + λN (K+1) 4 γm-1 8γ m ≤ λ + 1 8γ m • N (K + 1) 4 . (since Reg(π f ⋆ ) = 0 and γ m-1 ≤ γ m )Plugging back to Eq. ( 20), we know thatReg(π) -Reg m (π) ≤ 1 4 Reg(π) + 16N (K + 1) 4 γ m + λ + 1 4γ m N (K + 1) 4 .Rearranging the terms, we know thatEQUATION)where the last inequality uses λ = 33.For the other direction, similar to Eq. ( 20), we know thatEQUATION)where(i) is again because γ m = N (K+1) 4Err log (2 m-2 ,1/T 2 ,F ) . Applying Eq. ( 21) to the first term in Eq. ( 23), we know that(K + 1) 4 V (q m-1 , π fm ) 8γ m ≤ N (K + 1) 4 8γ m + γ m-1 Reg m-1 (π fm ) 8γ m ≤ N (K + 1) 4 8γ m + γ m-1 2Reg(π fm ) + λN (K+1) 4 γm-1 8γ m (i) ≤ λ + 1 8γ m • N (K + 1) 4 + 1 4 2Reg m (π fm ) + λN (K + 1) 4 γ m (ii) = 1 + 3λ 8γ m N (K + 1) 4 ,where (i) is because γ m-1 ≤ γ m and Eq. ( 22), and (ii) is due to Reg m (π fm ) = 0. Plugging the above back to Eq. ( 23), we obtain thatReg m (π) ≤ Reg(π) + 2 + 4λ 8γ m N (K + 1) 4 + 1 4 Reg(π) + 16N (K + 1) 4 γ m ≤ 2Reg(π) + λN (K + 1) 4 γ m , (since λ = 33)which finishes the proof. □ Now we are ready to prove Theorem 3.7.Input: an online regression oracle Alg on satisfying Assumption 3. for t = 1, 2, . . . , T do Obtain value predictor f t from oracle Alg on .Receive context x t ∈ X and reward vector r t ∈ [0, 1] N . Calculate q t ∈ ∆(S) based on f (x t ) and r t , via either Eq. ( 9) or Eq. ( 10). Sample S t ∼ q t and receive purchase decision i t ∈ S t ∪ {0} drawn according Eq. ( 1). Feed the tuple (x t , S t , i t ) to the oracle Alg on .Theorem 3.7 Under Assumption 1 and Assumption 2, Algorithm 1 with q m defined in Eq. ( 5) and the optimal choice of γ m ensuresReg MNL = O ⌈log 2 T ⌉ m=1 2 m K 2 N Err log (2 m-1 , 1/T 2 , F) . Proof Choose γ m = max 1, N (K+1) 4 Err log (2 m-2 ,1/T 2 ,F ) for all m ≥ 2. Consider the regret within epoch m ≥ 2. We first show that π∈Ψ Q m (π)Reg m (π) ≤ N (K+1) 4 γm. Concretely, according to Lemma 3.6 and Lemma B.5, we know thatEQUATION)Now consider the regret within epoch m. Since Event 1 holds with probability at least 1 -1 T , we know thatE τm+1 t=τm+1 max S∈S R(S, x t , f ⋆ (x t )) -R(S t , x t , f ⋆ (x t )) = (τ m+1 -τ m )E π∈Ψ Q m (π)Reg(π) ≤ τ m+1 -τ m T + (τ m+1 -τ m )E π∈Ψ Q m (π)Reg(π) Event 1 holds (since Event 1 holds with probability at least 1 -1 T ) (i) ≤ τ m+1 -τ m T + (τ m+1 -τ m )E π∈Ψ Q m (π) 2Reg m (π) + 33N (K + 1) 4 γ m Event 1 holds ≤ τ m+1 -τ m T + (τ m+1 -τ m ) • 35N (K + 1) 4γ m (using Eq. ( 24))= O τ m+1 -τ m T + 2 m-1 K 2 N Err log (2 m-2 , 1/T 2 , F) ,where (i) uses Lemma B.8. Taking summation over m = 2, 3, . . . , log 2 T + 1 , we conclude thatReg MNL = O   ⌈log 2 T ⌉ m=1 2 m K 2 N Err log (2 m-1 , 1/T 2 , F)   .□ C Omitted Details in Section 4.1In this section, we show omitted details in Section 4.1.We first show that there exists efficient online regression oracle for the finite class and the linear class.Lemma C.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 Reg log (T, F) = O( T log |F| log K β );• (Linear class) Online Gradient Descent [32] with Reg log (T,F) = O(B √ T ).Proof We first consider the finite function class. Since for any S ∈ S, i ∈ S ∪ {0}, and x ∈ X , we have f i (x) ≥ β, we know that ℓ log (µ(S, f (x)), i) ≤ log K+1 β . Therefore, Hedge [16] guarantees that Reg log (T,F) = O log K β T log |F| .For the linear class, we first prove that given S ∈ S, i ∈ S ∪ {0} and x ∈ R d×N , for anyf θ ∈ F , ℓ log (µ(S, f θ (x)), i) is convex in θ. Specifically, for u ∈ R d , h(u) = log( d i=1 e ui ) is convex in u since for any α ∈ R d , α ⊤ ∇ 2 u h(u)α = α ⊤ 1 1 ⊤ u diag(u) - 1 (1 ⊤ u) 2 uu ⊤ α = ( d k=1 u k α 2 k )( d k=1 u k ) -( d k=1 u k α k ) 2 (1 ⊤ u) 2 ≥ 0,where the last inequality is due to Cauchy-Schwarz inequality. Define x 0 = 0 ∈ R d to be the d-dimensional all-zero vector. Then, we know that ℓ log (µ(S,f θ (x), i)) = log e θ ⊤ x0 + j∈S e θ ⊤ xj -B -(θ ⊤ x i -B) • {i = 0} is convex in θ. Moreover, direct cal- culation shows that ∇ θ ℓ log (µ(S, f θ (x)), i) 2 = j∈S e θ ⊤ xj -B • x j 1 + j∈S e θ ⊤ xj -B -x i • {i = 0} 2 ≤ 2.Therefore, Online Gradient Descent [32] guarantees that Reg log (T,F) = O(B √ T ), since θ 2 ≤ B.□For completeness, we restate and prove Lemma 4.2, which is extended from the analysis in [14, 15] .Reg MNL ≤ E T t=1 dec γ (q t ; f t (x t ), r t ) + 2γReg log (T, F)for any γ > 0, where dec γ (q; v, r) is the Decision-Estimation Coefficient (DEC) defined asEQUATION)Proof Following the regret decomposition in [14, 15] , we decompose Reg MNL as follows:EQUATION)where the last equality is by the definition of dec γ (q t ; f t (x t ), r t ). According to Lemma 3.3, we know thatEQUATION)Combining Eq. ( 25) and Eq. ( 26) finishes the proof. □Next, we prove Theorem 4.3, which shows that similar to the stochastic environment, a simple but efficient ε-greedy strategy achieves O T 2 /3 (N KReg log (T, F)) 1 /3 expected regret.Theorem 4.3 The strategy defined in Eq. ( 9) guarantees dec γ (q t ; f t (x t ), r t ) = O( N K γε + ε). Consequently, under Assumption 1 and Assumption 3, Algorithm 2 with q t calculated via Eq. ( 9) and the optimal choice of ε and γ ensures Reg MNL = O (N KReg log (T, F))1 3 T 2 3 .Proof We first prove that q t defined in Eq. ( 9) guarantees dec γ (q t ; f t (x t ), r t ) ≤ O N K γε + ε . Specifically, for any S ⋆ ∈ S and v ⋆ ∈ [0, 1] N , we know thatR(S ⋆ , v ⋆ , r t ) - S∈S q t (S)R(S, v ⋆ , r t ) -γ S∈S q t (S) µ(S, f t (x t )) -µ(S, f ⋆ (x t )) 2 2 (i) ≤ i∈S ⋆ |v ⋆ i -f t,i (x t )| + S∈S q t (S) i∈S |µ i (S, v ⋆ i ) -µ i (S, f t (x t ))| + R(S ⋆ , f t (x t ), r t ) - S∈S q t (S)R(S, f t (x t ), r t ) -γ S∈S q t (S) µ(S, f t (x t )) -µ(S, v ⋆ ) 2 2 (ii) ≤ i∈S ⋆ |v ⋆ i -f t,i (x t )| + 2K γ + R(S ⋆ , f t (x t ), r t ) - S∈S q t (S)R(S, f t (x t ), r t ) - γ 2 S∈S q t (S) µ(S, f t (x t )) -µ(S, v ⋆ ) 2 2 (iii) ≤ i∈S ⋆ |v ⋆ i -f t,i (x t )| + 2K γ + ε + R(S ⋆ , f t (x t ), r t ) -max S∈S R(S, f t (x t ), r t ) - γε 2N N i=1 µ({i}, f t (x t )) -µ({i}, v ⋆ ) 2 2 (iv) ≤ i∈S ⋆ |v ⋆ i -f t,i (x t )| + 2K γ + ε + R(S ⋆ , f t (x t ), r t ) -max S∈S R(S, f t (x t ), r t ) - γε 64N N i=1 (f t,i (x t ) -v ⋆ i ) 2 (v) ≤ 16N K γε + 2K γ + ε ≤ O N K γε + ε ,where (i) uses Lemma B.1, (ii) is due to AM-GM inequality and |S| ≤ K, (iii) is according to the construction of q t and R(S, v, r) ∈ [0, 1], (iv) uses Lemma B.3 with d = 1, and (v) is uses AM-GM inequality and the fact that|S ⋆ | ≤ K. Taking maximum over all S ⋆ ∈ S and v ⋆ ∈ [0, 1] N proves that dec γ (q t ; f t (x t ), r t ) ≤ O N K γε + ε .Combining the above result with Lemma 4.2, we know thatReg MNL = O N KT γε + εT + γReg log (T, F) .Picking γ and ε optimally finishes the proof. □ C.3 Proof of Theorem 4.5 and Theorem 4.6In this section, we restate and prove Theorem 4.5, which proves that q t calculated via Eq. ( 10) guarantees that dec γ (q t ; ft (x t ), r t ) ≤ O N K 4 γ .Theorem 4.5 The following distribution satisfies dec γ (q t , f t (x t ), r t ) ≤ O N K 4 γ :EQUATION)Proof Since the construction of q t is the same as Eq. ( 5) with f m replaced by f t and γ m replaced by γ, according to Lemma 3.6, we know that q t satisfies that maxEQUATION)EQUATION)Using Eq. ( 27) and Eq. ( 28), we know that for anyS ⋆ ∈ S and v ⋆ ∈ [0, 1] N , R(S ⋆ , v ⋆ , r t ) - S∈S q t (S)R(S, v ⋆ , r t ) -γ S∈S q t (S) µ(S, f t (x t )) -µ(S, f ⋆ (x t )) 2 2 ≤ i∈S ⋆ |v ⋆ i -f t,i (x t )| + S∈S q t (S) i∈S |v ⋆ i -f t,i (x t )| (according to Lemma B.1) + R(S ⋆ , f t (x t ), r t ) - S∈S q t (S)R(S, f t (x t ), r t ) -γ S∈S q t (S) µ(S, f t (x t )) -µ(S, v ⋆ ) 2 2 ≤ i∈S ⋆ |v ⋆ i -f t,i (x t )| + N i=1 w i (q t ) • |v ⋆ i -f t,i (x t )| (by definition of w i (q)) + R(S ⋆ , f t (x t ), r t ) - S∈S q t (S)R(S, f t (x t ), r t ) -γ S∈S q t (S) µ(S, f t (x t )) -µ(S, v ⋆ ) 2 2 . ≤ i∈S ⋆ |v ⋆ i -f t,i (x t )| + N i=1 w i (q t ) • |v ⋆ i -f t,i (x t )| + R(S ⋆ , f t (x t ), r t ) - S∈S q t (S)R(S, f t (x t ), r t ) - γ 2(K + 1) 4 S∈S q t (S) i∈S (v ⋆ i -f t,i (x t )) 2(according to Lemma 3.3)= i∈S ⋆ |v ⋆ i -f t,i (x t )| + N i=1 w i (q t ) • |v ⋆ i -f t,i (x t )| + R(S ⋆ , f t (x t ), r t ) - S∈S q t (S)R(S, f t (x t ), r t ) - γ 2(K + 1) 4 N i=1 w i (q t )(v ⋆ i -f t,i (x t )) 2 ≤ N (K + 1) 4 γ + i∈S ⋆ (K + 1) 4 γw i (q t ) + R(S ⋆ , f t (x t ), r t ) - S∈S q t (S)R(S, f t (x t ), r t ) (AM-GM inequality) = N (K + 1) 4 γ + i∈S ⋆ (K + 1) 4 γw i (q t ) -max S0∈S R(S 0 , f t (x t ), r t ) -R(S ⋆ , f t (x t ), r t ) + max S0∈S R(S 0 , f t (x t ), r t ) - S∈S q t (S)R(S, f t (x t ), r t ) ≤ N (K + 1) 4 γ + (K + 1) 4 γ N + γ (K + 1) 4 max S0∈S R(S 0 , f t (x t ), r t ) -R(S ⋆ , f t (x t ), r t ) -max S0∈S R(S 0 , f t (x t ), r t ) -R(S ⋆ , f t (x t ), r t ) + N (K + 1) 4 γ(according to Eq. ( 27) and Eq. ( 28))= 3N (K + 1) 4 γ .Taking maximum over all S ⋆ ∈ S and v ⋆ ∈ [0, 1] N finishes the proof. □ Combining Lemma 4.2 and Theorem 4.5, we are able to prove Theorem 4.6.Theorem 4.6 Under Assumption 1 and Assumption 3, Algorithm 2 with q t calculated via Eq. (10) and the optimal choice of γ ensures Reg MNL = O K 2 N T Reg log (T, F) .Proof Combining Lemma 4.2 and Theorem 4.5, we know that Algorithm 2 with q t calculated via Eq. ( 10) satisfies thatReg MNL = O N K 4 γ + γReg log (T, F) . Picking γ = K 2 N T Reg log (T,F )finishes the proof. □In this section, we provide examples on regression oracles for a broader Lipschitz function class satisfying Assumption 2 and Assumption 3. Proof We first consider the ERM strategy. For notational convenience, let Z ≜ (x, S, i) and with an abuse of notation, we denote ℓ log (µ(S, f (x)), i) by ℓ f log (Z). According to Theorem 7.7 in [26] ,Lemma D.1 Suppose that F is a 1-Lipschitz function class defined as F = {f θ,i (x) ∈ [β, 1] | θ ∈ [0, 1] d } where β > 0 and f θ1,i -f θ2,i ∞ ≤ θ 1 -θ 2 ∞ for all θ 1 , θ 2 ∈ [0, 1] d and i ∈ [N ]. Then, ERM strategy f D = argmin f ∈F (x,S,i)∈D ℓ log (µ(S, f (x)), i) satisfies Assumption 2 with Err log (n, δ, F) = O d log K β log n β log 1we know that for any F = {f : X → [β, 1] N } such that the ε-covering number of {ℓ f log : f ∈ F} is N (ε), ERM predictor f D guarantees that with probability 1 -δ:EQUATION)Now we show that for the 1-Lipschitz function class, N (εEQUATION)where the second inequality is by log(1 + x) ≤ x for x ≥ 0 and the triangular inequality, and the third inequality is due to the Lipschitz property and the lower bound β on all values. Therefore, weknow that N (ε) ≤ |C(ε)| ≤ 1 + 2 βε d. 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 ℓ log (µ(S, f (x)), i) ≤ log K+1 β for all context x, S ∈ S, and i ∈ S ∪ {0}, Hedge guarantees that E T t=1 ℓ log (µ(S t , f θt (x t )), i t ) - T t=1 ℓ log (µ(S t , f θ (x t )), i t ) ≤ O log K β T log |C(1/T )| = O log K β dT log(T /β) , for all θ ∈ C(1/T ). Picking θ = argmin θ∈C(1/T ) θ -θ ⋆ ∞ where f ⋆ ≜ f θ ⋆ andEQUATIONUpdate p t+1,f ∝ p t,f • exp(-η ℓ t,f ).p t and selects the subset S t that maximizes the expected reward with respect to the value function f t and the reward vector r t . After receiving the purchase decision i t , the algorithm constructs a loss estimator ℓ t,f for each f ∈ F as defined in Eq. ( 31), and updates the distribution p t using a standard multiplicative update with learning rate η. See Algorithm 3.The idea of the loss estimator Eq. ( 31) is as follows. The first term measures how accurate f is via the squared distance between the multinomial distribution induced by f and the true outcome.The second term, which is the highest expected reward one could get if the value function was f , is subtracted from the first term to serve as a form of optimism (the "feel-good" part), encouraging exploration for those f 's that promise a high reward.We extend the analysis of Zhang [30] and combine it with our technical lemmas (such as Lemma 3.3 and Lemma B.1) to prove the following regret guarantee, where the term Z T should be interpreted as a certain complexity measure for the class F.Theorem E.1 Under Assumption 1, Algorithm 3 with learning rate η ≤ 1 ensures Reg MNL ≤ 32ηN (K + 1) 4 T + 4ηT + Z T η , whereZ T = -E[log E f ∼p1 [exp(-η T t=1 ( ℓ t,f -ℓ t,f ⋆ ))]].Proof First, we decompose the regret as follows:EQUATION)where (i) is because S t = argmax S∈S R(S, f t (x t ), r t ) according to Algorithm 3 and (ii) is using Lemma B.1. Here, "Feel-Good" term FG t measures the difference between the expected reward of the best subset given the value predictor f t and that of the true value predictor f ⋆ .Next, we analyze the first termT t=1 i∈St |f t,i (x t ) -f ⋆ i (x t )|.Given any context x ∈ X , reward vector r t ∈ [0, 1] N , and a value predictor f ∈ F , let S(f (x), r) = argmax S∈S R(S, f (x), r). According to Algorithm 3, we have S t = S(θ t , x t ). With a slight abuse of notation, for distribution p t over F, let w t,i = E f ∼pt [{i ∈ S(f (x t ), r t )}] be the probability that item i is included in the selected set at round t. Let q t ∈ ∆(S) be the distribution over S induced by p t , meaning that q t (S) = E f ∼pt [{S(f (x t ), r t ) = S}]. Then, for each i ∈ [N ], for any µ > 0,EQUATION)Taking a summation over all i ∈ [N ], we know that for any µ > 0,EQUATION)where (i) uses Eq. ( 33) and (ii) is by definition of w t,i and q t .Let LS t = i∈St (f i (x t ) -f ⋆ i (x t )) 2 ("Least Squares"). Combining Eq. (32) with Eq. (34), we know thatEQUATION)To bound the last two terms in Eq. (35), using Lemma B.3 and the fact that i t is a drawn from the distribution µ(S t , f ⋆ (x t ), r t ) and, we show in Lemma E.2 thatEQUATIONTherefore, picking µ = 1 128η(K+1) 4 and combining Eq. ( 35) and Eq. (36), we know thatReg MNL ≤ 32ηN (K + 1) 4 T + 4ηT - 1 η E T t=1 log E it|xt,St E f ∼pt exp -η ℓ t,f -ℓ t,f ⋆ (37)To bound the last term in Eq. (37), we use the exponential weight update dynamic of p t . Following a classic analysis of exponential weight update, we show in Lemma E.3 thatEQUATIONwhereZ t ≜ -E log E f ∼p1 exp -η t τ =1 ℓ t,f -ℓ t,f *. Combining Eq. (37) and Eq. (38), we arrive atReg MNL ≤ 32ηN (K + 1) 4 T + 4ηT + 1 η T t=1 (Z t -Z t-1 ) ≤ 32ηN (K + 1) 4 T + 4ηT + Z T η ,where the last inequality uses the fact that Z 0 = 0. □ Lemma E.2 Suppose that η ≤ 1. For any distribution p t over F, we have1 128η(K + 1) 4 E f ∼pt [LS t ] -E ft∼qt [FG t ] ≤ - 1 η log E it|xt,St E f ∼pt exp(-η( ℓ t,f -ℓ t,f ⋆ )) + 4η,where LS t and FG t are defined in the proof of Theorem E.1, and ℓ t,f is defined in Eq. (31) .Proof For notational convenience, define c t,i = {i = i t } for all i ∈ [N ]. Let ε t,i = c t,i - µ i (S t , f ⋆ (x t)) for all i ∈ S t and ε t ∈ R N +1 is the corresponding vector. Consider the term-η ℓ t,f -ℓ t,f ⋆ for an arbitrary f ∈ F . -η ℓ t,f -ℓ t,f ⋆ = - 1 16 i∈St (µ i (S t , f (x t )) -c t,i ) 2 + 1 8K i∈St (µ i (S t , f ⋆ (x t )) -c t,i ) 2 + η • max S∈S R(S, f (x t ), r t ) -η • max S∈S R(S, f ⋆ (x t ), r t ) = - 1 16 i∈St (µ i (S t , f (x t )) -µ i (S t , f ⋆ (x t )))(2c t,i -µ i (S t , f (x t )) -µ i (S t , f ⋆ (x t ))) + η • max S∈S R(S, f (x t ), r t ) -η • max S∈S R(S, f ⋆ (x t ), r t ) = - 1 16 i∈St (µ i (S t , f (x t )) -µ i (S t , f ⋆ (x t )))(µ i (S t , f ⋆ (x t )) -µ i (S t , f (x t )) + 2ε t,i ) LSt + ηFG t (f ),where we define the first term as LS t , which we will show later how this term is related to LS t , and the second term FG t (f ) = max S∈S R(S, f (x t ), r t ) -max S∈S R(S, f ⋆ (x t ), r t ) (so FG t = FG t (f t )). Consider the log of the expectation of the exponent on both sides.EQUATION)where the first inequality is by Cauchy-Schwarz inequality and the second inequality is becauseE[x] 2 ≤ E[x 2 ]. Next, we consider bounding each of the two terms. For the first term, since 2 2 -sub-Gaussian random variable given x t and S t , meaning that1 4 i∈St (µ i (S t , f (x t )) -µ i (S t , f ⋆ (x t )))ε t,i ) ≤ µ(S t , f (x t )) -µ(S t , f ⋆ (x t )) 2 2 √ 2 ≤ 1 2 , we know that -1 4 (µ(S t , f ⋆ (x t ) -µ(S t , f (x t ))) ⊤ ε t is a zero-mean, 1 8 µ(S t , f (x t )) - µ(S t , f ⋆ (x t ))E ct|xt,St exp - 1 4 (µ(S t , f ⋆ (x t ) -µ(S t , f (x t ))) ⊤ ε t ≤ exp 1 16 µ(S t , f (x t )) -µ(S t , f ⋆ (x t )) 2 2 .Therefore, we know thatE ct|xt,St exp - 1 8 LS t = exp - 1 8 µ(S t , f (x t )) -µ(S t , f ⋆ (x t )) 2 2 E ct|xt,St exp - 1 4 (µ(S t , f ⋆ (x t ) -µ(S t , f (x t ))) ⊤ ε t ≤ exp - 1 16 µ(S t , f (x t )) -µ(S t , f ⋆ (x t )) 2 2 .Then, since 1 16 µ(S t , f (x t )) -µ(S t , f ⋆ (x t )) 2 2 ≤ 1 8 , using the fact that exp(x) ≤ 1 + x 2 for x ∈ [-1, 0], we know that E ct|xt,St exp - 1 8 LS t ≤ 1 - 1 32 µ(S t , f (x t )) -µ(S t , f ⋆ (x t )) 2 2 ≤ 1 - 1 64(K + 1) 4 i∈St (f i (x t ) -f ⋆ i (x t )) 2 = 1 - 1 64(K + 1) 4 LS t ,where the second inequality is because Lemma B.3. Further using the fact that log(1 + x) ≤ x for all x ≥ -1, we haveEQUATION)Consider the second term in Eq. (39). Since η ≤ 1 and |FG t (f )| ≤ 1, using e x ≤ 1 + x + 2x 2 for x ≤ 1, we know that1 2 log E f ∼qt [exp(2ηFG t (f ))] ≤ 1 2 log 1 + 2ηE f ∼qt [FG t (f )] + 2(2η) 2 ≤ ηE f ∼qt [FG t (f )] + 4η 2 (log(1 + x) ≤ x) = ηE ft∼qt [FG t ] + 4η 2 . (f t is drawn from q t )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.-E E St∼qt log E ct|xt,St E f ∼pt exp(-η( ℓ t,f -ℓ t,f * )) ≤ Z t -Z t-1 ,whereZ t = -E log E f ∼p1 exp -η t τ =1 ℓ t,f -ℓ t,f * and q t ∈ ∆(S) satisfies that q t (S) = E f ∼pt [{S = argmax S ′ ∈S R(S ′ , f (x t ), r t )}]. Proof Let G t,f ≜ exp -η t τ =1 ℓ t,f -ℓ t,f * . According to Algorithm 3, we know that p t,f = exp -η t-1 τ =1 ℓ τ,f f ′ ∈F exp -η t-1 τ =1 ℓ τ,f ′ df ′ = G t-1,f f ′ ∈F G t-1,f ′ df ′ .Then, according to the definition of Z t , we haveZ t-1 -Z t = E log f ∈F G t,f df f ∈F G t-1,f df = E log f ∈F G t-1,f exp(-η( ℓ t,f -ℓ t,f * ))df f ∈F G t-1,f df = E log E f ∼pt exp(-η( ℓ t,f -ℓ t,f * ) ≤ E E St∼qt log E ct|xt,St E f ∼pt exp(-η( ℓ t,f -ℓ t,f * ) ,where the last inequality is due to Jensen's inequality. Rearranging the terms finishes the proof. □ Proof For a finite function class F, since q 1 is uniform, we haveZ T = -E   log f ∈F 1 |F| exp -η T t=1 ℓ t,f -ℓ t,f ⋆   ≤ -E log 1 |F| exp -η T t=1 ℓ t,f ⋆ -ℓ t,f ⋆ = log |F|.Combining with Theorem E.1 and picking η = 1K 2 N log |F | T, we prove the first conclusion.To prove our results for the linear class, we first show a more general results for parametrized Lipschitz function class. Suppose that F is a d-dimensional parametrized function class defined as:EQUATIONDirect calculation shows that the linear function class we consider is an instance of Eq. ( 41) with α = 1. For function class satisfying Eq. (41), we aim to show that Z T = O(Kη + d log(αBT )). Specifically, we consider a small ℓ 2 -ball around the true parameter θ ⋆ :Ω T = {θ : θ -θ * 2 ≤ 1 αT K }.Since F is α-Lipschitz with respect to • 2 , we know that for any x ∈ X , and any i ∈EQUATION)Therefore, for any θ ∈ Ω T ,-η( ℓ t,f θ -ℓ t,f θ ⋆ ) = - 1 16 i∈St (f θ,i (x t ) -c t,i ) 2 + 1 16 i∈St (f θ,i (x t ) -c t,i ) 2 + η • max S∈S R(S, f θ (x t ), r t ) -η • max S∈S R(S, f θ ⋆ (x t ), r t ) ≥ - 1 8 i∈St |f θ,i (x t ) -f θ ⋆ ,i (x t )| + η • max S∈S R(S, f θ (x t ), r t ) -η • max S∈S R(S, f θ ⋆ (x t ), r t ). (43) Let S(f θ ⋆ (x t ), r t ) = argmax S∈S R(S, f θ ⋆ (x t ), r t ).Then, we can further lower bound Eq. (43) as follows:- With the optimal choice of η = 1 EQUATION• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.Justification: The authors have reviewed the NeurIPS Code of Ethics. The research conducted in this paper conforms with it 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).We call this a linear class (even though it is technically log-linear) because, when combined with the MNL model Eq. (1), it becomes the standard softmax model with linear policies. Also note that the bias term -B in the exponent makes sure f θ (x) ∈ [0, 1] N . Following[23], we assume ∥θ∥2 ≤ B instead of ∥θ∥2 ≤ 1 to ensure the representation power of the function class, since we already normalize the contexts and restrict them to be within the unit ball.In fact, for our purpose, it is always sampled from µ(St, f ⋆ (xt)), instead of being chosen arbitrarily, but the concrete oracle examples we provide in Lemma 4.1 indeed work for arbitrary it. 


Decision: 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)

Reviews: review: paper_summary: paper_summary: The paper presents three primary contributions for the contextual multinomial logit bandits considering both stochastic and adversarial contexts and rewards.

-  a suite of algorithms proposed each with a different computation-regret trade-off.

- advances existing regrets by removing the dependence on certain problem-dependent constants.

- extends existing works to study a general value function class (1-Lipschitz function class).
strength_weakness: strength_weakness: - No experiments and simulation results are provided. But to be fair, there are other theoretical papers without experimental illustrations.

- 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}})$.
questions: questions: - Is this the first MNL bandit paper considering adversarial context and reward with online regression oracle?

- Could you please address the second point in Weakness?

- 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?

- 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?

The next two questions are related.

- 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. 

- 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. 

Some minor issues:

- In line 173, should "$\epsilon \rightarrow \epsilon_m$"?

- 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.

- 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: limitations: The authors adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

In spite of repeated appearances of log loss regression, its definition has not been stated.
The definitions of Err_log, Reg_log, and ERM are missing.
For the function class F, what is the definition of |F| in Lemma 3.1? 
I think that many things other than these are missing.
questions: questions: What is the relationship between \pi and q_m?

I am interested in how to apply the feel-good TS [30] for this setup.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. **Computational Inefficiency**: The Feel-Good Thompson sampling algorithm, as discussed, lacks computational efficiency, even for linear cases, which could limit its practical applicability.
2. **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.
questions: 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?
2. 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?

Ref: Yu-Jie Zhang and Masashi Sugiyama. Online (Multinomial) Logistic Bandit: Improved Regret and Constant Computation Cost. In NeurIPS 2023.
limitations: limitations: NA
paper_summary: paper_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$.
strength_weakness: strength_weakness: 1. The regret bound has supper linear dependency on $K$ for $\sqrt{T}$ in Corollayr 3.8, 4.7, 4.8.
2. It does not provide regret lower bounds so it is hard to know the tightness of the achieved regret upper bounds.
questions: 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?

2. 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: limitations: I could not find a discussion on the limitations of this work.

Comments: title: Response
Response to rebuttal
Thank you for your response.
Thank you for your rsponse.
Thank you for your response
comment: I thank the authors for their detailed response. I will make some changes in my evaluation based on this.
We thank the reviewer for the questions again. They are indeed very helpful, and we will add more explanation to the paper. Specifically: 

**Why IID is necessary for the algorithm? We can still compute $\text{Err}_{\log}$ given $S$. It is known IID assumption with fixed $q_m$ is not a requirement for Thompson sampling. So it is not very intuitive to me. What aspects of the problem make it necessary here?**

- It is necessary to have i.i.d. data in our algorithm design solely because we assume that our oracle requires i.i.d. data as inputs. It is completely possible that to solve the problem itself, using the entire history is a feasible solution, but note that the weaker the oracle assumption we make, the stronger our result is, so we choose to assume that the oracle only works with i.i.d. data.

**The relationship between $\Delta$ and $B$ still gives me contradictory information. Bigger $B$ and $\Delta$ result in a lower probability of item $i$ being selected. Why does the regret increase with $B$ but decrease with $\Delta$?**

- Technically, $\Delta$ and $B$ have opposite effects because a larger $\Delta$ makes it easier for the learner to identify the value difference from the realized item selection, while a larger $B$ makes the regression on the item selection probability harder. This is a great question though, and we will add more intuitive explanations to the paper.
Thanks to the authors for their response and for making these points clear. Now it is clear how $B$ affects regret and what iid means here. I hope the authors can explain the following questions in the revised paper. At least they are not very intuitive to me.

- Why IID is necessary for the algorithm? We can still compute $Err_{\log}$ given $S$. It is known IID assumption with fixed $q_m$ is not a requirement for Thompson sampling. So it is not very intuitive to me. What aspects of the problem make it necessary here?

- The relationship between $B$ and $\Delta$ still gives me contradictory information. Bigger $B$ and $\Delta$ result in a lower probability of item $i$ being selected. Why does the regret increase with $B$ but decrease with $\Delta$?

I hope these questions are helpful. Again, I'll maintain my rating on this paper.
We thank the reviewer for the further discussions and we address your questions as follows.

**Q3: A iid requirement is incorrect. There is no identical distribution. I guess the author means conditionally independent given the recommendation actions. So the entire history can be used in my opinion.**

A: No, we indeed mean that the tuples $(x, S, i)$ collected within epoch $m$ are i.i.d. drawn from the same distribution. This is true since the selection of $S$ follows a **fixed** conditional distribution $q_m(x,r)$ given the context $x$ and the reward $r$ within epoch $m$ (and $(x,r)$ are i.i.d. of course). 

On the other hand, this i.i.d. property does not hold for tuples coming from different epochs since $q_m(x,r)$ is different for different epochs. This is why we cannot use the entire history.

**Q5: I still believe 𝐵 should not be included in the regret upper bound and used in comparison with other algorithm. It is a free parameter and reparameterization does not change the problem definition. A larger 𝐵 will not affect log loss since 𝜃 will also scale up. If this is right, the comparison with [20] should either be removed or revised.**

A: Note that we already normalize the contexts so that they are within the unit $\ell_2$ ball, so further normalizing $\theta$ is not without loss of generality and is restricting the representation power of the function class.

We also do not understand the comment “A larger 𝐵 will not affect log loss since 𝜃 will also scale up”. Specifically, a larger $B$ in our formulation can lead to a lower probability of item $i$ being selected since the value of this item can be as low as $e^{-2B}$, which eventually makes the scale of the log loss to be of order $B$ as shown between Line 425 and Line 426.

**Q6: This is just a suggestion. The paper could benefit from introducing our discussion on Δ into the problem definition and analysis. An intuitive explanation of how it affects regret could give readers a better understanding of the MNL bandit problem.**

A: Thanks for your suggestion. We will incorporate this into our next revision.
We thank the authors for their response. I am maintaining my score since it is the first MNL bandit paper considering adversarial context and reward with online regression oracle. However, I hope the authors could address the following issues or give better explanation.

- Q3: A iid requirement is incorrect. There is no identical distribution. I gues the author means conditional independent given the recommendation actions. So the entire history can be used in my opinion.

- Q5: I still believe $B$ should not be included in the regret upper bound and used in comparison with other algorithm. It is a free parameter and reparameterization does not change the problem definition. A larger $B$ will not affect log loss since $\theta$ will also scale up. If this is right, the comparison with [20] should either be removed or revised.

- Q6: This is just a suggestion. The paper could benefit from introducing our discussion on $\Delta$ into the problem definition and analysis. An intuitive explaination on how it affects regret could give readers a better understanding of the MNL bandit problem.
I appreciate your detailed explanation addressing the concern regarding $\kappa$. However, the regret bound has a superlinear dependency on $K$, which reduces the benefit of removing $\kappa$ when the norm of the parameter is bounded by 1. Given my primary concern about the tightness of the bound, I am maintaining my score.
I thank the authors for their response and have no further questions.
To clarify, the reason why most previous MNL works using UCB-type approach (e.g. [7,20,23]) have this $\kappa$ dependency is that their analysis depends on the confidence width constructed via MLE (e.g.Theorem 2 in [20]). However, different from previous approaches, we show that the regret directly depends on the **regression error**. Moreover, while the ERM oracle may involve parameter approximation, importantly its regression error **does not** explicitly depends on the distance between the estimation and the true parameter, because making accurate predictions is in a sense easier than making accurate estimation of the parameter (an inaccurate estimation on the parameter could still lead to an accurate prediction).


As for the covering number, we show in Appendix B.1 (line 427) that the $\epsilon$-covering number is bounded by $\left(\frac{16B}{\epsilon}\right)^d$, with no dependence on $\kappa$.
For the $\kappa$, it is still not clear how to avoid this term. For the regression with linear class, ERM seems to minimize log-loss to estimate parameters as in the previous MNL model, which includes approximate parameter. Could you provide any helpful comments regarding this? I'm also wondering about that the $\epsilon$-covering number does not need to include $\kappa$.