Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities
Authors: Taehyun Hwang
Dahngoon Kim
Min-hwan Oh
Venue: NeurIPS 2025 poster ()
Keywords: multinomial logit choice model
contextual bandit
non-linear function approximation
regret analysis
Primary area: theory
TL;DR: We propose a computationally tractable multinomial logit contextual bandit algorithm, which is designed to handle generic non-linear parametric utility functions.

Abstract: We study the _multinomial logit_ (MNL) contextual bandit problem for sequential assortment selection. Although most existing research assumes utility functions to be linear in item features, this linearity assumption restricts the modeling of intricate interactions between items and user preferences. A recent work (Zhang & Luo, 2024) has investigated general utility function classes, yet its method faces fundamental trade-offs between computational tractability and statistical efficiency. To address this limitation, we propose a computationally efficient algorithm for MNL contextual bandits leveraging the upper confidence bound principle, specifically designed for non-linear parametric utility functions, including those modeled by neural networks. Under a realizability assumption and a mild geometric condition on the utility function class, our algorithm achieves a regret bound of $\tilde{\mathcal{O}}(\sqrt{T})$, where $T$ denotes the total number of rounds. Our result establishes that sharp $\tilde{\mathcal{O}}(\sqrt{T})$-regret is attainable even with neural network-based utilities, without relying on strong assumptions such as neural tangent kernel approximations. To the best of our knowledge, our proposed method is the first computationally tractable algorithm for MNL contextual bandits with non-linear utilities that provably attains $\tilde{\mathcal{O}}(\sqrt{T})$ regret. Comprehensive numerical experiments validate the effectiveness of our approach, showing robust performance not only in realizable settings but also in scenarios with model misspecification.

Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities
Taehyun Hwang Scoul National University th. hwanwwnn@enn... kc
Dahngoon Kim Scoul National University dahngoon. k@snu. ac
Min-hwan Oh
Scoul National University minoh@snu, ac.kr kr
Abstract
We study the multinomial logit (MNL) contextual bandit problem for sequential assortment selection. Although most existing research assumes utility functions to be linear in item features, this linearity assumption restricts the modeling of intricate interactions between items and user preferences. A recent work [41] has investigated general utility function classes, yet its method faces fundamental trade- offs between computational tractability and statistical efficiency. To address this limitation, we propose computationally efficient algorithm for MNL contextual bandits leveraging the upper confidence bound principle, specifically designed for non-linear parametric utility functions, including those modeled by neural networks. Under a realizability assumption and a mild geometric condition on the utility function class, our algorithm achieves regret bound of Ö ((VT), where denotes the total number of rounds. Our result establishes that sharp O ((VT))-regre is attainable even with neural network- -ased utilities, without relying on strong assumptions such neural tangent kernel approximations. To the best of our knowledge, our proposed method the first computationally tractable algorithm for MNL contextual bandits with non-linear utilities that provably attains ((VT) regret. Comprehensive numerical experiments validate the effectiveness of approach, showing robust performance not only in realizable settings but also in scenarios with model misspecification.
Introduction
The multinomial logit (MNL) contextual bandit [5, 30, 28, 4] is a model for sequential assortment selection under uncertainty prevalent in applications such as online recommendation systems, person- alized marketing, and online retailing. this setting, an agent repeatedly selects subsets of items to present to users, where user choice behavior is modeled using the MNL model [27]. Specifically, the probability that a user selects an item determined by its latent utility, which typically depends on contextual features associated with items and possibly user characteristics. The primary goal is to minimize expected regret, defined as the cumulative difference rewards obtained by the algorithm compared to oracle that knows the true utility parameters in advance.
Almost all prior studies on MNL contextual bandits assume the item utility functions to be linear in contextual features [5, 30, 28, 4, 29, 32, 2. 44, 20, 21J. Although the linearity assumption simplifies computations and theoretical analyses, it significantly limits the expressive power required to capture complex and nonlinear user behaviors typically observed in real-world scenarios. Recent work by Zhang and Luo [41] addresses this limitation by considering more general utility functions. How- ever, they encounter critical trade-offs: algorithms with computational tractability yield suboptimal regret (c.g., (T2333 in stochastic and ( in adversarial settings), whereas their statistically efficient approaches become computationally infeasible due to non-convex optimization challenges.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Consequently, designing computationally efficient algorithms that achieve optimal statistical guaran- tees under general, non-linear utility functions remains an open and significant challenge.
Motivated by these fundamental limitations, we investigate the MNL contextual bandit problem with utilities represented by general, non-linear parametric models, such neural networks. This setting introduces several fundamental challenges compared to the linear case. First, the negative log-liked ongllikelhhod function used for parameter estimation lacks the self-concordant-like properties crucial for theoretical analysis in linear utility functions [36]. Second, gradient-based analyses that rely on gradients in linear models do not extend naturally to the non-linear setting, as gradients become gurameter-dependeer and more intricate. Lastly, non- con-linear utility functions typically induce non-convex optimization landscape characterized by multiple global minima due to symmetries (c.g., neuron permutations in neural networks), complicating both the optimization process and subsequent regret analysis.
Despite these challenges, this paper presents a computationally tractable algorithm for MNL contex- tual bandits that can handle non-linear utility functions and achieve a sharp regret bound. Our key contributions are as follows:
We propose an upper confidence bound (UCB)-based algorithm designed explicitly for MNL contextual bandits with non-linear utilities. Under realizability assumption and newly proposed generalized geometric condition, our algorithm achieves a regret bound of O(VT). To our knowledge, this constitutes the first algorithm with such near-optimal regret guarantees independent of the total number of items N in this non-linear utility setting.
Unlike the existing approach [41], which either compromise statistical efficiency or compu- tational feasibility, our algorithm simultaneously attains computational tractability and the sharp Õ(VT) regret bound under non- non-linear utility settings.
To overcome technical challenges arising in parameter learning for non-linear utility based MNL models, we introduce novel generalized geometric condition on the squared error of the utility function (Assumption 4). This condition significantly generalizes and weakens assumptions used in previous studies [25, 22, 34] and accommodates broad classes of non-linear functions, including neural networks. Moreover, we derive a new concentration inequality for parameter estimation in MNI. models, independent of the regularization parameter up to logarithmic factors. These technical advancements allow us to construct computationally tractable, optimistic utility estimators suitable for efficient exploration.
Crucially, our approach cireumvents the commonly used neural tangent kernel (NTK) as- sumptions [18], eliminating the impractical requirement of extensive over-parameetrizzatoo prevalent in NTK- analyses.
We demonstrate the superior performance of our algorithm through extensive numerical experiments. While benchmark methods suffer significant performance degradation in non- linear utility scenarios, our proposed method maintains robust performance in both realizable and misspecified contexts, underscoring its practical effectiveness and adaptability.
2
Preliminary
For a positive integer N E N, we denote the set (1,.... NN by [N]. For vector x E Rd, its fn-norm is defined as ||x|p (2) i (/)// for 1 S < co, and its loo -oom is defined as ||x||oo = max |zy]. For matrix A, its operator norm is denoted by ||A For vector x E Rd and a symmetric positive semi-definite matrix A Rdxd, we define ||x||A := Vx Ax. We denote a real-valued function defined on X' and parameterized by w as fw X - R, and denote its gradient and Hessian with respect to w by V and 42 sw. respectively. Throughout, we use standard big-O notation to hide universal constants, and notation to additionally hide logarithmic and logarihitt factors.
Notations.
2.1 Problem Setting
MNL contextual bandits. We consider sequential assortment selection problem in which, at each round the agent observes a set of feature vectors for all items, denoted by X₃ == {x XIN C

---

Table I: Comparison of results and main assumptions for prior MNL contextual bandits with non- linear utilities. Zhang and Luo [41] consider a bounded and Lipschitz-continnne whereas our work assumes bounded, Lipschitz, and smooth utility class. The geometric condition (Assumption 4) is imposed in Phase I to establish the convergence rate of the pilot estimator. In contrast, the analysis in [41] relies on the generalization error of the (offline online) regression oracle, measured in terms of log-loss, rather than the distance between the estimattr and the true parameter. The dimensionality dw appearing in the regret bounds of [41] corresponds to the dimension of the Lipschitz function parameter, which may differ from the context dimension d.
utility class,
Algorithm
Utility
Assumptions
Tractability'
Regret (K
6-greedy [41]
Lipschitzness
Offline reg. oracle
log-barrier regularizer [41]
Lipschitzness
Offline reg. oracle
X
Vd NT) 1(
E-greedy [41]
Lipschitzness
Online reg. oracle
J
Feel-Good TS [41]
Lipschitzness
Online reg. oracle
X
O(K2VOON 20 d d.vVT
ONL-MNL (this work)
Smoothness
Geometric condition
Traatability of cach method refers to the computational fcasibility of the exploration strategy, i.c., the process of selecting an assortment given eurrent utility estimator. The computation required obtain our pilot estimator is comparable to what is already used in [41]. Following [41]. any tractable empirical risk minimization method (e.g.. SGD) sufficient for computing our pilot estimator in practice.
RRd where each feature vector belongs to general context space X' C IRd. Based on this information, the agent selects assortment S, {úi, : it) E S {S C [N] |S| S K), where s K, and observes user choice i, E Se U {0}, where 0 denotes the "outside option". i.e., the user chooses none of the offered items. The user's selection it E U {0) is modeled by the MNL choice model:
exp(Sw- (X+x)
(i Xr, St) =: p(i Xr, w*)
I+ ++>Es, exp(Sw- (xp(sw-(Xxj))
1
Pi; = Xx, S.) =: p(0 X, St w*)
::):):::l
1+ Ejes, exp(sw-(Xx5)
where fw-() : X R is unknown utility function, specifying the user's value for each item under the given context. At each round f, the agent receives feedhack in the form of a choice response indicating which item from the offered set S, {0) was selected. The choice outcome is represented as one-hot vector y; == (yro. Vrl,.... Mz),, where Uts = 1 if item i was chosen and 0 otherwise. By definition of the model, this choice is drawn according the following MNL distribution:
yr Multinomial {1, [p(0 Xx, St, p(1 Se, w"), .....
w......, p(u Xe, w"]]
where 1 denotes y, is single-trial sample, i.e., Vio + Ekm Vik 1.
For given revenue parameter vector F, [Feo, , where Tıo 0 denotes the revenue associated with the outside option and ru is the revenue for item E [N], the expected reward of offering an assortment 5 E S under the context feature set X, is defined
exp(fw- (Xxi))
Rx.,,, (") =: Re(Sww))
p(i S.. Σe(E iES
Σ 1+ Ejes exp(sw" (Xtr)) iES
The goal of the agent is minimize the cumulative regret over T rounds, defined as the total difference expected reward between the offline optimal assortment S = argmaxses RS, w*)
T
and the assortment chosen by the agent, Regrety
Σ (RA(S, w*) - (S.. w*)]
Non-linear parametric functions. We consider a parametric function class F ;= (w :x w E W). where W C & may be highly non-convex and is not necessarily differentiable with respect to the context vector x E X, but we assume differentiable with respect to the parameter w. We further assume that the function class F is expressive enough to contain the true (unknown) utility function fw".
set of dim-ddimenioonal parameter vectors. Each function fw E F
3

---

Assumption 1 (Realizability). We assume w E W and F is given to the agent.
Assumption is standard in the contextual bandit literature using general function approximation [13, 12, 35, 25, 41]. While this assumption is necessary for our theoretical guarantees, we will also demonstrate empirically that our proposed algorithm performs well even under model misspecification, particularly when the function class under consideration has high representational capacity, such as neural networks.
We also define the equivalence set W C W as the set of parameter vectors that yield the same function values as fw- for all x E X, ie.. W := {w E W fw (x) = fw (x) for all x X.. This equivalence set arises naturally in expressive function classes such as neural networks. For instance, consider two-layer neural network defined as fw (x) = Ex=1 o(x [xTWW) where w = [wi...., w..] E Rdxm is the weight matrix, and a denotes the activation function. Any column permutation of w yields the same function output fw- Therefore, rather than recovering w exactly, it suffices to identify any parameter within the equivalence set W"
Following prior work on contextual bandits [1, 28, 9, 20, 25, 22, 34), we make the following boundedness assumption.
Assumption 2 (Boundedness). For all 2 1 and E [N], we assume that ||x S and ra E [o. 1]. and || [l2 < 1 for all w E W. Also, we assume that there exist constants Cj, Cg. Ch > 0 such that for all x E and w E W, it holds that
If S Cy,
[VVS S CCg,
[w) S Ch.
where V (x) and 2 (x(x) denote the gradient and Hessian of fw with respect to w.
2.2 Challenges of Learning in Non-Linear Utility
Learning utility parameters in non-linear MNL bandit models presents significant challenges com- pared linear models. In linear utility settings, the negative log-likeling likeelioddood function exhibits a self-concordant-lkke property [36], simplifying theoretical analysis and enabling tight regret bounds [32, 20J. Non-linear utility models, however, typically lack this property, complicating analysis significantly. Another key difference lies in the gradient structure. In linear models, gradi- ents are simply feature vectors, independent of parameters, allowing straightforward concentration inequalities. In contrast, non- lon-linear gradients depend explicitly on unknown parameters, complicating the application of these analytical methods. Moreover, the optimization landscape for non-linear utilities is notably more complex. Linear models yield convex loss functions with unique minima, whereas non-linear models (e.g., neural networks) produce highly non-convex loss surfaces. Addi- tionally, symmetries like neuron permutations cause multiple global minima, further complicating optimization and thcoretical analysis in non-linear settings.
3
Main Results
In this section, we introduce an algorithm for the MNL bandit problem with a non-linear parametric utility function that is both computationally tractable and statistically efficient. We begin by explaining the key design principles of the algorithm, and then present its regret bound along with the main technical components of the analysis.
3.1 Algorithm: ONL-MNL
We propose ONL-MNL, an algorithm that leverages optimistic estimates derived from non lon-linear utility functions to guide exploration. The complete procedure is presented in Algorithm 1, which consists of two main stages.
Uniform exploration phase. The first stage (Phase I) is uniform exploration phase that lasts for in rounds. During this phase, the agent selects an assortment size most K, uniformly random. The goal of this exploration phase is to obtain "pilot" estimate of the unknown parameter w* or any parameter the equivalence set that is, good initial estimator. At the end of Phase I, the agent invokes regression oracle to estimate the initial parameter wo based on the data collected

---

Algorithm 1 ONL-MNL (Optimistic Non-Linear Utility for Contextual MNL Bandit)
1: Inputs: Regularization parameter X, confidence radius (3:)211 exploration length lo. number of rounds T
2: for t= ...,. do
Phase I: Uniform exploration
3:
Observe X; = {x..,..., x.NJ. offer St ~ Un) and observe it
4: end for
5: Compute Wo = argmin C(w)
6: Initialization: V. = AId..
7: for t = tu + 1. ..... do
> Phase II: Optimistic exploration
8:
Observe X, (x11..... X,N)
9:
Compute W, = argmin l (w)
10:
Compute zt: = fwr((e)) + V V fw (xx))ll,, +
P.C. for all [M]
11:
Offer S. argmaxses (S) and observe is
12:
Update Vi+1 V, Eies, V (xes) Vfr. (X
13:
end for
during the exploration rounds. This is done by minimizing the negative log- legelikelioood of the observed item choices under the MNL model in Eq. (1) defined as follows:
argminn L(w) == Σ logpli: Xe. S.. wEW
W0
Here, L(w) denotes the empirical loss over the first t0 rounds, where it is the item chosen from assortment S, with the context set X,. Using standard results from empirical risk minimization over Lipschitz function classes, together with the reverse Lipschitz property of the MNL model, we show that the minimum squared eπror of the pilot estimator wo with respect to the equivalence set W namely min
|| w| converges at a rate of (11/t) (Lemma 1).
Optimistic exploration phase. In the second stage (Phase II), adopt more sophisticated strategy to balance exploration and exploitation. In particular, we construct a confidence region for the parameter in the equivalence set W that closest the pilot estimator wo. We then estimate the utility parameters within W by minimizing the following regularized negative log-likelihood:
A ||w woll
W. argmin (w) == wEW
Σ
Σ
Yoi log p(i Ss, w)
(2)
2
#=fo+1 FES,
where p(1 Xx, Se, w) is a linearized MNL model given by
exp(fw, + V fw. (xei) (w - -w,)) p(i 1 S,, w) 1+ Ejes, exp(ffr. (Xej) + Vww. (Xaj) T w.))
The key intuition is that we apply first-order Taylor approximation of the non-linear utility function fw (-) around the estimate W., since are dealing with general non-linear model. Moreover, instead of regularizing around the origin 02 we regularize around the pilot estimator Wo. as provides meaningful reference point that is already close to the parameters in W Based on the estimated parameter W,, we define the confidence set C, as follows:
C = (w& E W: ||w we 12 S 3.)
where 3g pre-defined monotonically inereasing sequence specified later, and V. : AL Et= Eies, Vf, (X.:) (x.i)T is the Gram matrix. With suitably set 3r, we will show that with high probability, argmin [|w - wllp E C, i... the equivalent utility parameter in W that is cloest to the pilot estimator we lies within the constructed confidence set C, Based on this observation, we compute the optimistic utility estimate zn as follows:
2ti fw. (Xx) + / F (xx)) (xxa)ly, B.Cn
Vi [N].
5

---

Figure 1: Example of highly non-convex loss (wy(W) that satisfies Assumption 4. The solid line shows the lower bound given by the pointwise mini- mum of the strong convexity and growth conditions over the equivalence set W For neural networks, the squared loss may have multiple global minima due parameter symmetries or over parametterrii This highlights that Assumption 4 is strictly weaker than prior geometric conditions, enabling to cover a wider range of utility functions.
Pepeeted aquard lise
couvesity bomdury
Growis coudition boundary
(ww)
The optimistic utility zu is composed of the parts: the mean utility estimate Sw. (X1s) and the uncertainty estimate V V fw, (xx)llyz + S.Ch, We will show that žii an optimistic estimate of the true utility fw (xa), assuming wrw- l wl12 E C. Based on Zts, we construct the exp(zu))u
optimistic expected reward for the assortment, defined as RS) = Σ 1+ Ejes exp(21)) Then,
iES
we offer the set St that maximizes the optimistic expected reward, i.e., S. = argmax Rs(S).
3.2
Regret Bound
In this section, we present the cumulative regret upper bound for the proposed algorithm. First, we introduce technical assumptions used derive the regret bound.
Assumption 3 (Stochastic context in Phase I). We assume that during Phase the context feature vectors X, == (X11...., Xx,N } are independently and identically distributed (i..d.) samples drawn from unknown distribution 'D supported on X.
Assumption 4 (Generalized geometric condition on the squared loss). Let
E(m(x;) - Sw (w;()x))? LiES
Exq (w) =
be the expected squared loss function over both the context feature distribution D and a uniformly sampled assortment. For the equivalence set W*, we assume that leg (w) satisfies either a (T, x)- growth condition or p-local strong convexity with respect to W i.e. Vw E W W
min WEW-
1 + lsg w),
[|w w11 + Can (w) s (wn(w),
for constants μ > 0 and 0 < 2.
Discussion of assumptions. Assumption 3 is used to bound the difference between the expected negative log-likelihoods of the true utility parameter w and the pilot estimator Wo. type of assump- tion commonly used in the empirical risk minimization literature [37, 41J. Note that Assumption 3 is only required for Phase after Phase I, the context vectors may be chosen even adversarially.
Assumption is on the expected squared loss between utility functions over the context distribution, rather than the unknown true utility function fw- itself. Assumption 4 is also required in Phase I to establish the convergence rate of the pilot estimator wo- The growth condition assumes that any utility function fw, whose parameters lie far from the equivalence set W cannot approximate the true utility function well over the context distribution. The local strong convexity condition assumes that the expected loss exhibits quadratic growth within local neighborhood around the cquivalence set W Notably, this condition is strictly weaker than the global strong convexity assumptions commonly adopted in prior work on parametric bandits- as linear and generalized linear bandits [11, 1] since it does not require the squared loss to be convex outside the local region near the optimal parameters. Moreover, Assumption 4 more general than the geometric conditions employed in prior works [25, 22, 34]. That is, any function satisfying the geometric conditions in [25, 22, 34] also satisfies ours, but converse does not necessarily hold. Previous geometric assumptions typically require the existence of unique global minimum, whereas we explicitly allow for multiple equivalent minima. As previously discussed, this is more realistic assumption in settings such neural networks, where the squared error loss can admit multiple

---

global minima- e.g., due to parameter symmetries or overparameterization. This flexibility allows our framework accommodate highly non-convex and non-linear expected loss landscapes, which may contain arbitrarily many spurious local minima and multiple global minima (Figure 1).
Now we are ready state our main result that upper bounds the cumulative regret of the Algorithm 1.
Theorem 1 (Regret Bound of ONL-MNL). Suppose Assumptions 1, 2, 3 and 4 hold. For any Ô E (0,1),
if we set the algorithmic parameters in Algorithm I follows: T 2 CK-1 -
B = 26=00 (μ (n=2x where C is a universal p(0 X, S, w)p(i X.S, w). and, Ç is the logarithmic term depending on K, to. Cg. 1/8, then with probability at least 1 - 25, Algorithm I achieves the following cumulative regret:
to = [n/ vT,, A = pp
constant, :== == WW..WE.....SE..
Regret, = =6 -8(1~3/2d VT + x= 2 VT)
In terms of the total time step T. Algorithm achieves Ö(VT) cumula- tive regret. This implies that Algorithm 1 is a no-regret algorithm, limy-+00 Regretr/"T 0.
Discussion of Theorem 1.
When the utility function family consists of neural networks, our proposed method still achieves regret bound of Ö(VT) without relying on the NTK assumption, which is commonly used in the neural wetwork-based bandit analysis [45, 43, 17], and thus eliminates the impractical requirement of extensive over- ower-parameterizauteee parameterization prevalent in NTK-based analyses. In particular, existing neural bandits [38, 15, 39] that do not rely on NTK assumptions still require restrictive conditions -uch as specific network architectures (e.g.. two-layered ReI.U networks with fixed second-layer weights set to one [39], or networks with quadratic activation functions [38]) specific context distributions (e.g., Gaussian [15], or uniform distribution over the unit sphere [39]). In contrast, our approach applies to a broader class of neural networks that satisfy Assumption 4, without imposing such architectural or distributional constraints.
Compared to the existing contextual MNL bandit algorithms with general utility functions [41], our algorithm is both computationally tractable and statistically efficient. While the uniform exploration method in Zhang and Luo [41] is computationally tractable, it results in sub-optimal regret- for example, ((14/3) in the stochastic setting and ((T5/6) in the adversarial setting. Their other methods-llog-arric regularization-based exploration and the Feel-Good Thompson Sampling [42] approach-atd are computationally intractable, meaning they cannot be solved in polynomial time. In contrast, our algorithm operates within polynomial time. The main computational cost lies in minimizing the regularized negative likeliiidoood, which can be efficiently approximated using gradient-based methods such as gradient descent with per-round complexity of O(t) [10]. The assortment selection step is also tractable: by combining the optimistic utility estimates zn with efficient assortment optimization techniques [33, 8), as done in Oh and lyengar [28, 291, it can be solved with (N) computational cost. In terms of regret bounds, although our regret depends on a reeeeenddependett instance factor it does not scale directly with the total number of items N or directly with the assortment size K. In contrast, the computationally intractable algorithm with
Ö(VT) -regret by Zhang and Luo [41] has super-linear dependence on K --specificalll O O(K?)- and additionally depend polynomially on N, limiting their applicability in settings with a large set of items, hence restricting real-world applications. To the best of our knowledge, our method is the only known algorithm that is both computationally tractable and provably achieves (VVT) regret in the contextual MNL bandit with non-lineat utility functions.
By definition, x= can scale as O(K2) in the worst-case scenario. However, in practice, the behavior of x is often much more favorable. For example, as shown in the experiments of Lee and Oh [20] (Figure in [20]). the gap between the regret of K deependnn algorithms [28, 29] and that of k -improved algorithu [20] does not grow significantly with K, even as K increases. This observation suggests that equating k with K2 or treating it as equivalent to K is overly pessimistic. Also, we note that the exponential dependence in can be adjusted by rescaling the utility values. For instance, Zhang and Luo [41] define the MNL probability model using bounded utilities without applying the exponential transformation.
Remark 1.
7

---

3.3 Regret Analysis
In this section, we present key technical ingredients that enable the regret bound of Algorithm 1, as established in Theorem 1. All the detailed proofs are provided in the appendix.
Convergence of We- The purpose of Phase I in Algorithm 1 is explore the unknown utility function Ww- through la rounds of uniform sampling and to obtain a pilot estimate Wo that is sufficiently accurate. We establish convergence guarantee for wo relative the equivalence set W specifically, we bound the quantity minwew- llwo 11
Lemma 1 (Convergence rate of wo). Suppose Assumptions 1, 3 and 4 hold. There exist an absolute constant C > O such that after to rounds in Phase I of Algorithm where to satisfies dd to 2 'Ck 2u,= C3
7272 T) with probability at least 6, we have
min llw - -w12 < C 16 C3
wEW
pto
where := SES p(O) S.S,w)p(t X.S.wi and Ç is the logarithmic term depending on K,to, Cg. 1/8.
Compared to the contextual multi-armed bandit setting with general reward function [12, 35], one of the key challenges in estimating the utility parameter in the MNL bandit is that the agent does not receive direct feedback on the utility of each item. Instead, it only observes the user's 's choice from the offered assortment. Despite this challenge, in Lemma 1, we first adapt existing generalization error bounds of the empirical risk minimizer under i.i.d. sampling, expressed in terms of the log- loss [37, 41J. Then, leveraging the reverse Lipschitz property of the MNL model (Lemma 4), we lower bound the difference in log-likelite likelihoods by the squared error between the utility values. Unlike Zhang and Luo [41]. which derives lower bound based on the assortment size K, our analysis incorporates a problem-dependent instance factor K.
Confidence set & Optimism. Although the 1/to convergence rate of wo is quite tight, it is not sufficient on its own. For example, Xu et al. [38] show that in the contextual bandit setting, one can achieve a regret of (322/3) by first learning the parameters of quadratic neural network through to rounds of uniform exploration (yielding a 1/4o convergence rate), and then switching entirely to exploitation using the learned parameters. In contrast, we go beyond this by constructing confidence set for parameters in equivalence set W* We then use an optimistic estimate of the true utility within this set to guide assortment selection, ultimately achieving a regret of Õ(VT). The following lemma explains how this confidence set is constructed.
Lemma (Confidence set). Suppose Assumptions 1, 2, 3 and 4 hold. If we choose to = [d -32 VT2 and X = (x0x3/2pp1 V VT), then Vt 2 to + -1 in Phase Il of Algorithm 1, with probability least 28, the following holds:
min || WEW-
Wl I Br = -01--2 (0-2--dd
The construction of the confidence set in Lemma relies on two key components. The first the careful choice of the exploration phase length to and the regularization parameter X, both of which play a critical role in ensuring the confidence radius 3, scales as O(log T),, which essential for achieving a cumulative regret ((VT).
The second challenge is that for À = (VVT). existing concentration results for utility parameter estimation in MNL GLM bandits [9, 32] are longer applicable. This is because these results rely on Bernstein-type inequalities, which yield confidence radius of order O (VX + d vX
T where d the dimension of the context feature vector. To ensure the confidence radius is O T), these bounds require X = (dd log 7'), which limits their applicability when λ = O (TVT). To overcome this, we first establish new concentration inequality for the utility parameter the MNL choice model that is independent of A (up to logarithmic factors), presented in Lemma 5. Combined with carefully chosen values of and fo, we then use mathematical induction argument show that for all rounds in Phase II, the estimation error satisfies minwew- || w12 ( Finally, we prove that this implies min || w < 3r.

---

For 1
Gaussian,
Fex nbx
70
UCB-AWL
40
T5 MNL
60-
T5-MML
OFU-NNUL
Cumulative Regret
50
30-
6 -ereeddd--leee -MLL
-NLL
60
-rrrddyyyyyoo RAM
Curmulstive
30-
20
10
10
(a) Realizability (Gaussian)
(b) Misspecification (Gaussian)
Cumulative regret comparison between ONL-MNL (ours) and baselines under Gaussian contexts. The results for the uniform context distribution are provided in Figure 4.
Figure 2:
Next, based on the confidence radius 3, established in Lemma we show that the optimistic utility estimate Zςi is greater than or equal to the true utility fw (Xxs) as follows:
Lemma (Optimistic utility). Suppose Assumptions
3 and 4 hold and minwew- 1| w Iiv S
for all to + 1 S < T. Then. for all to + 1 S s T and i So. we have
28,Ch.
0 S Zzi fw. (xx) 2 V. (x
Unlike the linear utility case [29], our optimistic utility estimate for fw- introduces an item- independent term of the form 23,C ChCh/aa /// This term arises as residual from the first-order approx- imation of the unknown utility function fw-, and unlike standard deviation terms /V (xx)lly; it does not vanish over time. As result, it poses an additional challenge in achieving cumulative regret of Ō O(VT). Nevertheless, we show that with regularization parameter À = O(VT), it is still possible to achieve both optimism and cumulative regret of ((VT) We then show that the expected reward of the assortment S,, chosen based on the optimistic utility estimates 2ti, exceeds the true expected reward of the optimal assortment S with high probability.
4 Numerical Experiments
MNL choice model with non-linear utilities. In this section, we present numerical experi- ments evaluate the performance of the proposed algorithm ONL-MNL. As baselines,
pare with algorithms for contextual MNL bandits with linear utilities-UCB-NNL [29], TS-MNL [28], and OFU-MNL+ [20]-as well as 3-greedy-MNL [41], regression-oracie-baasss method with uni- form exploration designed for general utilities. Each experiment was conducted independently over 30 random seeds, and we report the mean and standard deviation of the cumulative regret. We set N = 100, K = 5, = 3. and Tu = 1. Experiments were performed under two dif- ferent context distributions:
(N(O,, and x; Unif[-3, 3), Vi [d]. We use a two- layered neural network with sigmoid activation as the estimator f for our proposed algorithm, i.e., f(x = 1 (inear2(ss (s immoid (nleann (x))).
For the realizable setting, the true utility function fw- is defined as a two-layer neural network with the same architecture as f. and set the number of neurons in the hidden layer 3. Each entry of the true utility parameter w independently sampled from the uniform distribution over the interval [].. We set the length of Phase to 50 and ran experiments for T 1000.
For the misspecified setting, the true utility function is defined as fw- (x) = cos(2 (x <w*))
[x w"), which differs in form from the estimator architecture. To account for this increased complexity, set the number of neurons in the hidden layer of the estimator 15. Accordingly, also increase the length of Phase to to = 100.
The experimental results in Figure 2 clearly demonstrate the effectiveness of our proposed algorithm, ONL-MNL, in both realizable and misspecified settings. Existing linear utility-based methods exhibit steadily increasing regret under non-linear utilities, they fail to capture the complex structure of the

---

X- Caussion, hut.::/www..iiiiiaaraeaaaaaaaaaa
X- Uniform, (x)= Linear22 (sinnedd Linearl
grgeedy MNL (N-100)
(N-100)
X- IN-800)
=-groody-MNL IN-800)
Curuuaatue Regrot
ONL MNL (N-100)
Curmulativs Regret
ONL (N-100)
-00)
Round (t)
Round
Gaussian
Uniform
Figure 3: Cumulative regret comparison between ONL-MNL (ours) and e --greddy-MNL [41] under
varying number of items N.
true utility function. Compared the s-greedy-MNL algorithm designed for general utilities [41], our approach is not only statistically efficient-achieving low cumulative regret-but also exhibits robust and consistently strong performance across different scenarios in both realizable and misspecified settings. See Appendix G for additional experimental results and details.
Efffet of the number of item on regret performance. To further highlight the distinct advantages of our proposed algorithm, ONL-MNL, over the s M-L [41], we compare the performances of those algorithms the total number of items N increases. Beyond being computationally tractable, key advantage of our algorithm is that its regret bound is independent of N, whereas the regret bound for E e-greedy-MMin grows polynomially with N. To verify this, we conduct experiments under realizable setting where the true utility function is two-layer neural network with sigmoid activation and hidden neurons. We evaluate the cumulative regret both algorithms at T 500 for different values N {100, 800}. Following [41], where the optimal exploration rate satisfies O(N133) (Theorem 3.4 in [41]), we set 0.1 and 0.2 for N = 100 and 800, respectively.
Figure 3-(a) and (b) show the results under Gaussian and uniform context distributions, respectively. As expected, the cumulative regret of <- e-greedy- MNL increases as N grows, which aligns with its theoretical regret bound that scales polynomially with N. While our algorithm also exhibits slight increase in cumulative regret as grows, this is primarily due to the increased regret incurred during the uniform exploration phase (Phase 1). As the total number of items increases, the size of the assortment set S also grows, leading to a larger gap between the expected reward of a uniformly sampled assortment and that of the optimal assortment. Nevertheless, in Phase II, our algorithm consistently converges toward the optimal policy, regardless of the value of N. In other words, the slope of the regret curve during Phase II remains relatively stable across different values of N, indicating that the learning efficiency of our method is unaffected by the size of the item set. These results demonstrate that our method not only offers provable computational and statistical efficiency but also remains robust and effective even in settings with extremely large item pools.
5 Conclusion
We studied contextual MNL bandits with non-linear parametric utilities and proposed a UCB-based algorithm that is both computationally tractable and statistically efficient. Our algorithm attains ((VT) regret independent of the number of items, the best of our knowledge the first tractable method with this guarantee for non-linear utilities. Relative to prior approaches for general utility models, our result achieves the same Ö ((T)) rate while remaining implementable under non non-linearity,
Looking ahead, the current regret bound depends the problem-dependent instance factor k; reduc- ing or removing this dependence in the non-linear setting likely requires new analytical techniques and remains important direction. Another promising avenue to extend framework MNL MDPs [16], where the transition kernel is specified by an MNL model. Prior work analyzes only the case in which the logit is a linear function of state-action features [16, 24, 31]; generalizing to non-linear parameterization while preserving computational tractability and performance guarantees would broaden the scope and impact of this line of research.
10

---

Acknowledgements
This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2022-NR071853 and RS-2023-00222663) by Institute of Information communications Technology Planning & Evaluation (ITP)) grant funded by the Korea government (MSIT) (No. RS-2025-022637555 and by AI-Bio Research Grant and Ascending SNU Future Leader Fellowship through Seoul National University.
References
[1] Y. Abbasi- Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24:2312-2320, 2011.
[2] P. Agrawal, T. Tuulabandhula, and V. Avadhanula. A tractable online learning algorithm for the multinomial logit contextual bandit. European Journal of Operational Research, 2023.
[3] S. Agrawal, V. Avadhanula, V. Goyal, and A. Zeevi. Mnl-bandit: A dynamic learning approach to assortment selection. Operations Research, 67(5): 2019.
[4] X. Chen, Y. Wang, and Y. Zhou. Dynamic assortment optimization with changing contextual information. Journal of machine learning research, 2020.
[5] W. C. Cheung and D. Simchi-Levi. Thompson sampling for online personalized assortment optimization problems with multinomial logit choice models. Available at SSRN 3075658, 2017.
[6] W. Cho, T. Hwang, J. Lee, and M.-h. Oh. Randomized exploration for reinforcement learning with multinomial logistic function approximation. Advances in Neural Information Processing Systems, 37:76643-76720, 2024.
[7] V. Dani, T. P. Hayes, and M. Kakade. Stochastic linear optimization under bandit feedback. pages 355-366, 2008. URL
cs thessinki.ff... woriifff/pppppp httppppprs//O--Daaa pdf.
[8] M. Davis, G. Gallego, and Topaloglu. Assortment optimization under variants of the nested logit model. Operations Research, 62(2):250 2733,,,, 2014.
[9] L. Faury, M. Abeille, C. Calauzènes, and O. Fercoq, Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning, pages 3052-3060. PMLR, 2020.
[10] L. Faury, M. Abeille, K.-S. Jun, and C. Calauzènes, Jointly efficient and optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 546-580, PMLR, 2022.
[11] S. Filippi, O. Cappé, A. Garivier, and C. Szepesvári. Parametric bandits: The generalized linear case. In Proceedings of the 23rd International Conference on Neural Information Processing Systems Volune NIPS 10, page 386-594, Red Hook, NY, USA, 2010. Curran Associates Inc.
[12] D. Foster and A. Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International conference on machine learning, pages 3199-3210. PMLR, 2020.
[13] D. Foster, A. Agarwal, M. Dudik, H. Luo, and R. Schapire. Practical contextual bandits with regression oracles. In International Conference on Machine Learning, pages 1339-1548, PMLR, 2018.
[14] A. Freedman, On tail probabilities for martingales. the Annals of Probability, pages 100-118 118, 1975.
[15] B. Huang, K. Huang, S. Kakade, J. D. Lee, Lei, R. Wang, and J. Yang. Going beyond linear rl: Sample efficient neural function approximation. Advances in Neural Information Processing Systems, 34:8968-899 2021.

---

[16] T. Hwang and M.-h. Oh. Model-based reinforcement learning with multinomial logistic function approximation. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pages 7971-7979, 2023.
[17] T. Hwang, K. Chai, and M.-h. Oh. Combinatorial neural bandits. In Proceedings of the 40th International Conference on Machine Learning. PMLR, 2023.
[18] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kerne:: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, volume 31, pages 8571-8580, 2018.
[19] P. Kassraie and A. Krause. Neural contextual bandits without regret. In International Conference on Artificial Intelligence and Statistics, pages 240-278. PMLR, 2022.
[20] J. Lee and M.-h. Oh. Nearly minimax optimal regret for multinomial logistic bandit. In The Thirtt-eighth Annual Conference Neural Information Processing Systems, 2024.
[21] Lee and M.-h. Oh. Improved online confidence bounds for multinomial logistic bandits. In Proceedings of the 42nd International Conference on Machine Learning, volume 267, pages 33576-338 33615. PMLR, 13-19 Jul 2025.
[22] C. Li, C. Liu, and Y.-X. Wang. Communication--ffiiin federated non- non-linear bandit optimiza- tion. In The Twelfth International Conference Learning Representations, 2024.
[23] L. Li, Y. Lu, and D. Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-2080 PMLR, 2017.
[24] L.-F. Li, Y.-J. Zhang, P. Zhao, and Z.-H. Zhou. Provably efficient reinforcement learning with multinomial logit function approximation. Advances in Neural Information Processing Systems, 37:58539-5888 58573, 2024.
[25] C. Liu and Y.-X. Wang. Global optimization with parametric function approximation. In International Conference on Machine Learning, pages 22113-221366 PMLR, 2023.
[26] A. Maas, R. E. Daly, P. T. Pham, D. Huang, A. Y. Ng, and C. Potts. Learning word vectors for sentiment analysis. Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies, pages 142-150, 2011.
[27] D. McFadden et al. Modelling the choice of residential location. 1978.
[28] M.-h. Oh and G. Iyengar. Thompson sampling for multinomial logit contextual bandits. Ad- vances in Neural Information Processing Systems, 32:3151-3161, 2019.
[29] M.-h. Oh and G. Iyengar. Multinomial logit contextual bandits: Provable optimality and practicality, Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9205-9213, 2021.
[30] M. Ou, N. Li, S. Zhu, and R. Jin. Multinomial logit bandit with linear utility functions. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 2602-2608, 2018
[31] Park, J. Kwon, and Lee. function approximation. In International Conference on Artificial Intelligence and Statistics, pages 361-369. PMLR, 2025.
reinforcement learning with multinomial logit
[32] N. Perivier and V. Goyal. Dynamic pricing and assortment under a contextual mnl demand. Advances in Neural Information Processing Systems, 35:3461-3474 2022.
[33] Rusmevichientong, Z.-J, M. Shen, and D. B. Shmoys. Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Operations research, 58(6): 1666-1680, 2010.
[34] 7.5 Siam, C. Guan, and Liu. Quantum non-linear bandit optimization. arXiv preprint arXiv:2503.03023, 2025.
12

---

[35] D. Simchi-Levi and Y. Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 47(3):1904-1999 2022.
[36] Q Tran-Dinh, Y-H. Li, and V. Cevher. Composite convex minimization involving self- concordant-lig cost functions. arXiv preprint arXiv:1502.0106: pages 155-168, 2015.
[37] T. Van Erven, P. D. Grünwald, N. A. Mehta, M. D. Reid, and R. C. Williamson. Fast rates in statistical and online learning. The Journal of Machine Learning Research, (6()):1733-161,, 2015.
[38] K. Xu, H. Bastani, and O. Bastani. Robust generalization of quadratic neural networks via function identification. arXiv preprint arXiv:2109.109. 2021.
[39] K. Xu, Bastani, S. Goel, and O. Bastani. Stochastic bandits with relu neural networks. In Forty-first International Conference on Machine Learning. 2024.
[40] P. Xu, Z. Wen, H. Zhao, and Q Gu. Neural contextual bandits with deep representation and shallow exploration. In International Conference on Learning Representations, 2021.
[41] M. Zhang and H. Luo. Contextual multinomial logit bandits with general value functions. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[42] T. Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, 4(2):834-857, 2022.
[43] W. Zhang, D. Zhou, L. Li, and Q. Gu. Neural thompson sampling. In International Conference on Learning Representation (ICLR), 2021.
[44] Y.-J Zhang and M. Sugiyama. Online (multinomial) logistic bandit: Improved regret and constant computation cost. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[45] D. Zhou, L. Li, and Q. Gu. Neural contextual bandits with ucb-based exploration. In Interna- lional Conference on Machine Learning, pages 1 11492-11502. PMLR, 2020.
13

---

Contents of Appendix
Related Works
14
B Proof of Lemma
15
B.1 Proofs of Technical Lemmas
17
B.1.1 Proof of Lemma 4
17
C Proof of Lemma 2
17
C.1 Proofs of Technical Lemmas
22
C.I.1 Proof of Lemma 5
22
C.1.2 Proof of Lemma 6
24
C.1.3 Proof of Lemma
25
C.1.4 Proof of Lemma 8
26
D Proof of Lemma 3
26
Proof of Theorem
27
F Auxiliary Lemmas
28
G Details on Experiments & Additional Results
29
A Related Works
Contextual MNL bandits. For contextual MNL bandits under linear utility assumptions, et al. [30] consider setting in which the item-context features remain fixed over time and achieve O(d VT) regret bound. Chen et al. [4] extended the fixed context setting to stochastic and time-varying contexts, deriving regret bound of (dvT d2 k²); however, their method is computationally intractable due to the need to enumerate all possible assortments. Oh and Iyengar [29] introduced polynomial-time algorithm that maintains confidence bounds the parameter space and computes UCB scores for each item, achieving regret ÖddK /T/R), where λ is the problem- dependent instance factor. Perivier and Goyal [32] further refined this under adversarial contexts and non-uniform rewards, improving the dependency on and achieving Ō(dKVR*T d2 d /K), but their method is not computationally tractable. Zhang and Sugiyama [44] proposed computationally efficient algorithm using online parameter updates for a multi parameer setting, where a shared contextual feature vector is used across items, but each item is associated with its own utility parameter. Lee and Oh [20] proposed a computationally efficient algorithm that achieves minimax optimal regret (up to logarithmic factors) in the kinglepparamee setting.
Extending beyond the linearity assumption, Zhang and Luo [41] is. to the best of our knowledge, the only work that addresses contextual MNL bandits with general function class. For the stochastic context setting, they proposed offline regression oracle-based algorithms. Assuming the function class Lipschitz,
uniform exploration method achieves a regret bound of ((dK ((dKK))////a//)) while the log-barrier regularization method achieves a tighter bound of adversarial context setting, they proposed two online regression oracle-based algorithms. Under the same Lipschitz assumption, the uniform exploration algorithm attains a regret of (((N))233755 and the log-barrier method again achieves O V2NT3/1) Additionally, they showed that a variant of Feel-Good Thompson Sampling [42] achieves a regret of O(K² Even though these results offer significant theoretical insights for general utility function classes, the log-barrier regularized exploration and Thompson sampling-bast based algorithms not computationally tractable- that is,
For the
14

---

they cannot be solved in polynomial time. Furthermore, all of their algorithms exhibit polynomial dependence on the total number of items N, limiting their applicability to environments with large or infinite item sets. In contrast, our proposed algorithm is not only computationally tractable but also achieves regret bound of O(VT), which remains independent of N, even in the presence of non-linear utilities.
Beyond linear models in contextual bandits. For generalized linear reward models, a growing body of work has provided algorithms with provable guarantees [11, 23, 9, 10]. Most of these methods achieve a regret bound of Odd'T), with subsequent improvements focusing on instance- dependent analysis and computational efficiency. For more general parametric reward models, Liu and Wang [25] consider the infinite-armed bandit setting and establish a regret bound of Odl, vT). where du denotes the dimension of the parameterized reward model. Their analysis also relies on a geometric condition on the squared loss of the parametric model, but erucially assumes a unique global minimum stronger condition than our Assumption 4.
Beyond parametric reward models, there has been a surge of interest in bandit algorithms utilizing neural networks [45, 40, 43, 19). However, these works typically rely on the assumption that the reward function lies in the reproducing kernel Hilbert space and heavily depend Moreover, regret bounds derived under NTK assumptions are known to suffer from unfavorable - worst-case information gain of order Ö(T**), leading to regret bound of O ), which is
NTK theory.
significantly worse than the standard sublinear regret of ((VT) [19]. Without relying on NTK theory, Xu et al. [38] analyze a quadratic neural network with a single hidden layer and establish a regret bound of ((T2/3). Huang et al. [15] consider two-layer ReLU neural network with fewer hidden units than input dimensions under the assumption of Gaussian input distributions. Xu et al. [39] study specific two-layer ReLU architecture in which all second- leyee weights are fixed to one, assuming a unit sphere context distribution. While these approaches achieve provably efficient algorithms without relying on NTK assumptions, their dependence on specific network architectures and restrictive context distributions limits their applicability to more general settings.
B Proof of Lemma
Proof of Lemma 1. For notational simplicity, we abbreviate the following process:
X~ D,
USi i Multinomial (1, [p(D] "...s"".......pppps X,S, w)),
w
(3)
as (X, 1) ~ H. Under Assumption 2, each function fw E F is Lipschitz continuous with constant Cy- Then, by the regression oracle guarantee for Lipschitz function classes (Lemma 9), there exists
constant C > 0 such that, with probability at least 1 - 8, the following bound holds:
duy C7S
E(x,s,)) [log X, w*) - log(( X, S, wo)l s Ci
40
where Ç -= log K log(to Cg) (o)g(1)))) is the logarithmic term S E S, and w E W, we define
For any X =
p(X, w) = [p(i] X. K.S.w),... p(1ss X,S, w)]
Po w) = [p(0 x,S, p(ph | ..... p(iss) |X
Then, we have
C1 575
2 E [(xs,)>> [log( X.S. log X,S. wo)l
to
Ex,s
[ENpo(XXS, [log((i X,S, w*) logp(i S,S. wo) |X
= Ex,s
S, X, S, wa))
X.
> Ex,s
|ol Sp - po (S wo)ll X,
2
2 Ex.s
ip(X,S,w")) pX S. wo |x,5
15

---

where the second inequality follows from Pinsker's inequality, and the final inequality follows from the definitions of p and Po- For the next step, we introduce the following lemma showing reverse Lipschitzness of the MNI. model. The proof of Lemma 4 is provided in Section B.1.
Lemma 4 (Reverse Lipschitzness of the MNL model), For E A = {x E R ||x|| S C}, let
h(a) - (a), ..... ha(a)] be defined
exp(a:)
h,(a) 1+ "
Then, for any a, A.
[l(aa) h(b)ll 2 Kolla a bll2,
where Ko min minield h,(a)(1 Σ/= hy(a))
Note that if we denote f(X,S, S. w) == [ (x, j E RI then we have (, p(X, S, w). Therefore by applying Lemma Eq. (4) can be further bounded by
x²
(4) 2 Ex,s
Σ (fmo(x))) Sw (x;))² x jES
(wg)
Therefore, we have
lag (Wo) S 20 R: 2-2
40
On the other hand, let w argmin llwo :Wll2. Then, by the condition on la.
12 11/12-2))
to 2 2x 075 72/(2-3)
(5)
where C' = 4C1, can obtain
Wo w/ S (T/U) (1/1))((223)
We can prove it by contradiction. Suppose that
I w"ll2 (T/1)
Then, have
Wo w
1
2 Wo
W "1
(6)
which implies that the (r, groowt condition holds by Assumption 4. On the other hand, by the (growth condition in Assumption 4, Eq. (6) implies
K 2-2 C7C
Wo w 113 S (wo) - (wn lan (Wo) S 20
to
By the condition on to in Eq. (5), this implies
ww - w S (2/1)
which leads to a contradiction. This shows that when to satisfies Eq. (5), then we lies in the region where the local strong convexity of (-q(-) at w holds. Therefore, we obtain
2-2d C75
Wo - w1 < lsq (wo) leg (w") = (wg - -lg(ww") 20
which results
| w/ < C x C3S
ytoo
where we again denote C' 4C₁.
16

---

B.1 Proofs of Technical Lemmas
B.1.1 Proof Lemma
Proof of Lemma 4. For any a, b E A, by the mean value theorem there exists conv(a, b) such that
h(a) h(b) Vh(c) (a (a-ba b).
Now, it suffices to show that Amin (V(h(c)T) 2 Kg. Since Vh(c) - (ha)) h(c)h(c)", for any x E Id {0d}.
x (xlc)x=x/diag(h/ee (x hxc))
h₂(c)a²
Σ
h,(c)
(c())=7
Σ hs(c)
Σ h((c)a?
(1
d
hi(c)a?
1
Σ
hi(c)
==1
hs(c)
-- Σ
hx(c)
xa
i=1
where the first inequality uses Sauchy-Schward inequality, and the last inequality follows by the definition of Kg. This concludes the proof.
C Proof of Lemma 2
Proof of Lemma 2. Let W argmin Ww w|12. And for notational simplicity, we will abbreviate p(i Xt, St, w) as Prs( (w), and p(i Xx, St, w) as Pr((w) in this proof. Recall that & (w) the regularized negative log-likelihood defined
Usi log (sg(ss(w) X ||w woll
((w): Σ
Σ
s=to SES
Since w, = argmin le (w),, we have (l((w)) = Od... and this implies
t-1
Σ Σ (w)(We) V fw. (x.i) + A(w; wo) =
Σ
Yos V fw. (X.i).
8=ta iES.
Let us define gr (w)))= = Et Eies, (el (xx) + Aw. Then, from Eq. (7) we have
g((w)) - B((ww)) Σ
(yst - Per (w)) fw. (xx:) A(wo w").
S
Note that since E/g Fel + fwa(W"), we cannot apply conventional self normalzzad martingale inequality used in previous MNL bandit [28, 29, 32, 44, 20]. Instead since Elysa FF] = Pss (w))
we add and subtract pail w*) as follows:
g: (w.) -g:(w (w"
Σ
Σ
(ysi - Pai Pa((w)) V (xxt) +
Σ Σ (p=:(W") - Por (w()))) V fw. (X.i)
sito
s
+\Wwo -
17

---

By inequality (a + b +)+ c)2 - 4a² - -4b2 + 4c², we have
(w,) g:(w")ll ")l
< 4 Σ
(usi ps:(W)) Viw. (xse)
+4
ΣΣ
(pei(w
Dzi(wr)) V Svc. (xxi)
s=tot
12
w 1 4
For the term I1 introduce the following lemma.
Lemma 5. For all 1 to with probability at least 6,
Σ
Σ
(ysi Po:(w=)) fw. (xxi)
S 0
s IES
where a, C. log(1 + TC2 (dr, log(t 1o? for an absolute constant C₂ 0.
If we denote each Poi (w" as Esi and note E[eai] = 0, the quantity E Eies, (ysi psi(w*)) V Vlv (Xai)
corresponds the self-normalized vector- V Yadkori et al. [1]. However, due to correlations among items within each selected assortment {esi Jis,,, standard seff-normalized inequalities cannot be directly applied. To address this, Perivier and Goyal [32] introduced an analysis based on a global random vec- tor z, := Eies, e V fw. (X.:), which, combined with Bernstein-type tail inequality for the logistic
valued martingale term
bandit (Theorem in Faury et al. [9]), yields a concentration bound of order Ô (VX+ log
VA
(Theorem C.6 in Perivier and Goyal [32]). As result, achieving regret bound of ((VT) requires the regularization parameter as À = (d T). contrast, by adapting techniques from Dani et al. [7], derive concentration result with bound that is independent of À (up to logarithmic factors). The proof of Lemma 5 provided in Section C.I.
For the term I2. we introduce several notations to facilitate understanding. Let K2 = S.S.l denote the size of the assortment selected at round s. Then we can write S, = (ii,..., , iK, J. Now we define G Rddx,, K, as the matrix whose k-th column is the gradient of fxxst) evaluated w,, i.c.
G,
V fw. (Xeir) ...., fwv (Xsin, )]
RR
For any vector [ur,... uk.l T R. we define h,) = [h (u), ..... hu, (u)] where each by is given by:
exp(ux)
hu(u): = 1+ Σドn exp(u,)
In addition, we define:
ú [ūsi:: Usix, I E R.K. where usiz fw. (Xsix) + (w- (w.) T (Xs())
u. = [ 4º sin.
T E KR where u = fw (Xoix)
18

---

Now we bound 12 as follows:
1 = 4
Σ G.(h,(ú.)- - h.(w²)))
#=
2
4
Σ
G. G.Vh.(ū))(uu. -
u,))
+=
V.
2
<
(,, -, =.'llv="'
$
/ (ũs - -,;)l +
where the first inequality follows from the triangle inequality, and the second inequality uses the following bound: for any matrices A, B, V E Rmxm and vector E R"
|AAx|| V (ABx) V(ABx) (Bx) AAA Amax (A VA Bx
| [x
On the other hand, we can bound each Vh, ( T (ú, - u2)ll2 as follows:
|h, (ū.) (ú, 22)l22 S [V, 1,0, ( -1ill0
where the norm loo, defined as follows:
|| supfllAx||2: |xx| S 1}.
Since Vh, (ū.) diag(h, h, (ū.))) h, i1 1h, (ū.) for any [0n sx. I with ||x||>>
we have
1h, T 2 | h, (ū.))x (h, (ū.) Tx)h, (ū,))(())
2
K.
hu Nu(ūū)
Σ Eg (ūs)
he (ūs)
2
K,
K,
hg (ū.)
Σ
x (ūo)
j=1
we denote Σnn h2 (ū.) =: since ||x||00 I 1, for all S S Ks we have
K.
K2
Σ (ū,) 11+
Σ
h (.))
$1
Then, (V,) Tx|3 can be further bounded as
VV, (ū,) T x||
h (ū, + 9)2 S (1 +
2 <
max p(1 + p)²
< 4,
(E().1)
1=1
19

---

where the fourth inequality holds because 0 q < 1. This implies Vh, (ū.) 1oo,2 S 2 for all therefore we bound the term 1 as follows:
12 16
Σ Letta+
G G. - uillo
16
|Gell,
max IskSk.
[ūsic Uoss
#=6++1
t-1
16
Σ
|Gallv;'
max 1ES,
=1l - w' far (xanc)
s=to+1
1-1
2
S 4c
Σ
[w - wo1 |G
+=
where the third equality follows from the second-ordes Taylor's theorem with w, lying between w. and W and the final inequality follows from Assumption 2.
For Ig, we have
4ACK Cd
4xa Wo
w V- S 4A//wo - w1
pto
For next step, we introduce the following lemma, whose proof provided in Section C.I.
Lemma 6. For any to + 1 t < T, it holds:
| w w 1R2 - (1+6v2)3 "lg.. (w:, Br(Ww)
Combining Lemma 6 with the bounds of /1, 1z, we have
(1+ 2x
|/,, w 11 <
(w,, - gr gr(Ww)
À
2
4(1 + 6.6622) 22
dn
Σ
[Gallv.:111. - -w
+
ulo
1s=1o+1
aa X
Co
t-1
2
Con 3on-3du
lllll,
(w - w
+
A
plo
+=
(8)
where we denote Co = 4(1 + 6/2)22 now proceed by induction to establish the convergence
rate of l/w, w 113 for every time step t to + 1...., T. Recall that by Lemma 1, with probability at least 1 - 8, we have
Ww w111 < CK Cn-2dn0C3s
juto
To formally set up the inductive argument, assume that at round there exists universal constant Č' such that, with probability least 1 28, the following holds:
ČK 2d
|W, 1
pto
Then, we want to show that at round t + with probability at least 28,
Ök- 2dn
| w1
udo
20

---

From Eq. (8), at round 7 + 1, we have
Wr+1 - w
Cok Tan-aam ax+1 COCA
2
Con 3o
Σ
|G v=
[w w
pto
s=to+1
Con Cox + Ap2to
CoRROR 3
2
Con On
Σ
G. vlll
pto
4=to+1
2
Cox a +
Cun Con O7C
|G,1| v=l rt
Ap
pto
a=to+1
s=fo+1
aat-1 C2 k
5 &e C/5
|Gsll
+
A1213
1+1
pdo
$ CONT +
C C
Cure O75
(9)
uto
where the last inequality invokes the following lemma, with its proof provided in Section C.I. Lemma 7. For all to + +1stsT,
Σ
|G I dw.
#1
Now, our goal is to show that there exist universal constant C such that the following bound holds:
Cax- CoCRE2x -5
Cox On-
(10)
Api2t
uto
uto
For notational simplicity, let denote a₁ CaduSi, where denotes logarithmic term that depends on T, dw. A, and 8. Then, Eq. (10) can be rewritten as:
CoC.x-'da + Co
Cok Con-&dn Cd
S
(11)
plo
1lo
Note that the left-hand side of Eq. (11) is monotonically increasing in r, and therefore the inequality must also hold at 5 = Ti; that is,
CoCar di
Co k & C5ST +
Con
Con-aduCp
ČK Cdu
S
ulo
ulo CoCax 'n 50.
(COCRK 2d
00- (x-(x0000))
Con dn
0+
+
Ap21
ulo
plo
A
feasible choice of T must satisfy the following condition:
K Rd
2
CoCRR - o 3T
(Con C7C
CoCax duli 2 0.
+
pdo
14.21
pto
By substituting X = CA CAVT and tg = 332 de VT, this condition becomes:
K x-1/2096 2
(Com Con-3122C4 CoČ.n= d
20
NVT
CLVT
nVT
CAVT
(N - -7/2 d/2 - -AC3CC 2, 20.
21

---

Solving the above quadratic inequality for C2, it suffices to choose
2n 3/2 (C0O9OnS+ + VOgOgORMAS + CartuPs
C2 2
Note that C2 depends only logarithmically T, and this choice guarantees that Eq.(11) holds, thereby confirming the existence of a universal constant Č. Hence, by induction, we conclude that for all to + 1 S & I T, there exists a universal constant C such that, with probability at least 1 - 25, the desired bound holds:
Cx dd
w
pto
Finally, combining again the results of Lemma 6 and similar argument used in Eq. (9), we have
Iw: w "II.
(1+ 6V2) x ((ve( - gi I
An 2d
4 6V2)2n1
01 (4+C3 C₁
Σ
|G.llv.:
1l
$113 +
uto
+=1o+1
CHOOKx - 0222
An
2d 2 OJS pto
Son
[Gullv,
+
1P888
Ax Ax- 2d 2n O75
S Con
Σ
Σ
(4
12t8
pto
s=to+1
s=ta+
C2OºR K
t-1 Σ
An C75
S Con
01
1211
pdo
8-1u+1
2d
C36
S Con
(4
1.21g
+
pto
=Ō 1k-p2 dhw))
where, in the last inequality, we substitute az = Ö(dw), A = CAVT = 0(x
5/2 - dn, VT).
to d -
C.1 Proofs of Technical Lemmas
C.1.1 Proof of Lemma 5
Proof of Lemma 5. If we denote 8; -'- Eies, (Usi Pool Pas(w")) V faa (Xs:), then,
St+1 8t +
(yis Pti P(((")) (W (xx: St Φ..
where we denote Φ. = Eiss, (yit Pes (ww))) V... (x,)). Then, we have
| = ($141 + Φ.) T V 2+1 ($t+1 + Φ,))
=s V-1 Vi + 2s V + Φ. V V ST vi 5:41 + 2s V 0. + o. V, %
where the last inequality follows by V, 2 V Using this argument recursively, we have
| 2
Φ +
Σ
2Φ. V-1 s..
(12)
22

---

Now we will define a martingale difference sequence. { [|
We start to define an event E,
S BB, Vs I J. and define
Jr = 2F V St-
Then, we have B[J Fi) = 2 T Fil
= O. And since we have
jJl S 0 V
22, D V 1/2
V 12
V 1/2
srl12
=2Eiy Φ. V 1+1 P.V
V 14
- 2E Φ. V Φ. s V St - 2 /
where the last inequality follows trivially when E, 0, and by definition of E, when E, 1. Additionally this gives us a family of uniform upper bound:
|4l| S 2 Vs
Now we bound the conditional variance of J, as follows:
V1 =
Var(J, (o....,,.-.))) S
Σ
4Egaal0ssll..
11o+1
4 as)
11 lll
SSt
s=to+
S 16at
max iES,
VV (x,1)
s1o++
where the last inequality uses the following inequality
|| ldallvv I
Σ is
Jesil V fw. (Xsi)llv3'
Med Il V.w. (xx:
+
Σ
Pai ( (xx))llv.)
JES.
ieS.
< 2 max iES.
V fw, (xsi)ll,.
For the next step, introduce the following lemma: Lemma 8. For any / 2 to + 1, it holds that
1-1
tC2 d
1, max VES,
fw. (x (R: < 2d log (1+
min
Lemma conceptually similar to the elliptical potential lemma commonly used in the linear utility setting [28, 29, 20]. As result, the proof of Lemma 8 can be readily extended from its linear counterpart, For completeness, we provide the proof of Lemma 8 at the end of this section. Suppose that À 2 Cg. which guarantees that fw, (x.)lR < 1 for all t 2 to + 1 and i E [N]. By using
Lemma 8, we bound V, as follows:
V I 32 log(1 + TC2/ (dg =: Ut-
Now we have established the sum of conditional variance of martingale difference sequence, denoted by Ve, is bounded by 2 Ö(a,dw). Then, by Freedman's 's inequality (Lemma 10) with parameters
23

---

at/2,b = 2 and 22, we have
1-1
6-1
IP
Σ
Jo 2220
=P
Σ
2 01/2, Vi S Ft
8=to-1
-000/2)²
< exp
20, + 2(1x/22) (2 (22)//22/06)/33 /3
og
/
exp
max
160,
16
8
x²x²
where the last inequality holds if we set
0t 2 Cıde log(1 +
(13)
for some absolute constant C₁ > satistying that
a 2 16v, log(t2 + (16/3) log (12x2 10))
By taking union bound,
(-1
[-1
3t
Σ =
J. 0t
$
Σ
Σ
J,
04
2
2
11
1=
0t 2
P
J
1=
s=
8
π
7
5
6
t=t++
Until now, have established the event (Ai lo + 11 + J. 02/22 holds with probability at least 1 - 8. Now we will show that the event E, = 1 under the event (A) 2 tu + 1, 1. Je S o1/ a1/2]. We prove this by induction t. Recall that E, 1 [||s,11 12, a,, Vtg
S t). For
the base case (t = to + 1), by definition of st++1 Oa... it holds that || 11 12 1
S 0t For
1011
the induction step, suppose that E. 1 for to + 1 S s < t. By Eq. (12),
| 5
Σ
2Φ V-1 8+18
min
[1, ||,,1110 12 }+ +
ar
2
amto++1
< 2dw log(1 + TC, (dw + 0t.
2
where we invoke Lemma 8 again for the second inequality. Then, with Eq. (13), if we have
at dh log(1 + (d., log(
for sufficiently large constant C. > then we have || S az. This completes the proof.
C.1.2 Proof of Lemma 6
Proof of Lemma 6. For any W1, We W. by the mean value theorem, have
g: (W1) (w2) = Vl((w2) (li)w)) = ( V'l((w + + - wi))dsx) (w2 - wi).
24

---

This implies
l1g. (g.(ww) gr (w2)))la; ' (w) [| W
(14)
where we denote Gw( w2) := So ( ( w))d.. On the other hand, Lee and Oh [20] show that the multinomial logistic loss with linear utility is 3 2-seef-concorrant-lie (Lemma 11), then by the property of self-concordant-like function (Lemma 12), we have
Pe z(W2 w1)) = exp (-3v2] -w1)l2)) (el((w))
This implies
Gr(WI, w2) = exp (33v2|1z(w2 - wi)lla) dz d=Vie,(wi)
1 exp (l/22- w2ll2) (2(((w1)
3v2 W2 - w1ll2
(e((w))
1+3v2 -
- will2
1 22l (w1)
2 1+
where the third inequality uses the inequality 1-exp(-z) Eq. (14), we obtain
for x 2 0. By applying this to
It
[wi- w2ll
$ (1 + 6v2) -
$ (1+ (1+ (g: g:(w2) G. ','(w1,
< (1 6v2) (8. (gr(()))
(: ((
(15)
On the other hand, since
(e((w)= = Alde + Σ
Σ
Pai (w) Σ
s
jES.
iES.
VES.
AId, + Σ
Σ VIAVS EVe.
where we abbreviate Vw, (xxi) Ssa. Then, by applying this to Eq. (15) we have || welki, < (1 6v2) llg. (w1) (r2)))
Substituting W = w, and W2 * completes the proof.
C.1.3 Proof of Lemma 7
Proof of Lemma 7. Note that
G
Σ
Amax G. (
G.)
v.
H
v.G. G.)
#1
fw. (Xxi) V V.w. (xxi)
Σ tr VJ.. (x.i) V V fir. (x,i))
s= iES,
tr Σ Σ
(xei) T
sito+
25

---

If we denote A1.... Adw the eigenvalues of Ex Eies. Vfwa (Xes) Mlsss/.w. V.w. (xxs)², tten we have
[-1
dy
V
Σ
EVs (x.s) ( (xxs))
Vs.
///(2/ + A) dn
1 iES,
/=1
C.1.4 Proof of Lemma 8
Proof of Lemma 8. For notational simplicity, we abbreviate V.w, (xu) as V Sri. Note that
V V+1 = V. + Σ
VSaVSa
SE
which results
det Ve+1 det V 1 Σ /Vsully : )
(1
det V,
max iESt
iESt
2 deI
II
1 max iES,
s=1o+
Then, we have
det V(+1
Σ
1 + max
/fsil S log det (AIa)
IES,
#1++1
Using the inequality & s 2 2og
+ 2) for E [0, 1], we have
min
m,x iES.
V V.
2log
1 max sES,
VSsi 12:
to
smta
det V4+1
< 2 2log det(ALa.))
1 (t + L)02 d
S 2dw log
where the last inequality follows by the determinant-trace inequality (Lemma 13).
D Proof of Lemma 3 Proof of Lemma 3. Note that
Zt4 sw- (xii) = (xes) - Sw (xic) + / Bell V (x:)ll + 8.0h
A
+ 3cCh
= =(w, w TV + v
(16)
A
= -(w, w') (V.. + (w: w (V - V v.n.
B.Cn
+ / B.B.IV for (x.)ll, + A
BrCh
2 (w. ww" (VAAm()))) {x,((x)s)) +
X
(w, w') T Tw (xw) w.) + 3,Cr
(17)
-| ll, VVl (xx) 1/2 1/1 ||| wellv, +
B.Ch
X
0,
where Eq. (16) applies the mean value theorem with w lying between w, and w*, Eq. (17) uses it again for W lying between w and w,, and the last inequality follows from the bound ||w wellv, S
lwW- w llv.. I BB. The upper bound can be derived by the similar argument.
26

---

E Proof of Theorem 1
Proof of Theorem I. Suppose that Lemma 2 holds. Then, by Lemma 3, for all to +1 S T and E St, we have fw (X+)) I Zti- By Lemma 14, the expected reward corresponding to the optimal assortment Si is monotone in the MNL utilities, for all f to + I,,,,? we have
Re (St w") S ((())) - (S.).
(18)
If we denote z/4 = fw- (xt) + 2 V fw. k,, + 23,Cn/A, A, by Lemma 15, which states that the optimistic expected reward (S) is monotonically increasing with respect to the utilities of the items S, and by Lemma 3 we have 2ts I 2/6 which implies
(S)) = Σ
exp(2
Σ EE
exp Dr
(19)
D jes exp(2t)
1+
jes, exp(21)
iES,
Let w' == argmin llwo wll2 denote the parameter in the equivalence set W that is closest to Wy. By combining Eq. 18 and Eq. 19, we bound the cumulative regret in Phase as follows:
E R, w') - (S, w')
Σ t=
RS, w*) (S,, w*)
T
(.,) - Ro(Ss, W*)
t
Eies, explzti)re
Eies, exp(fa- (xx))rrss
+ EjEs, exp(x/)
+ Ejes. expls (X1z))
(1
T
max 2 fw- (xx:i E8
(20)
2 V.. (xn))ll + 28,Cn
Σ t=to+1
where Eq. (20) follows by Lemma 16. By applying Cauchy- inequuall
inequality, we have
28,Ca A
(2 (2/B.llV/...x (xm)lly 28:Ca A
Σ
(x.)ly, +
S
T
Σ
1=
1=
8,3002 12
T
+
1=t++1
T
8,3,C222
837T
(xn))
X²
t=t++1
16T Br log(1 (1 + +T + 11C3//((cc)) + 83
X²
= 16 22 dr -d
where the second inequality uses the inequality (a + 6)2 < 2a + 262, the third inequality uses the monotonicity of S,, and the last inequality follows by Lemma and the final bound is obtained by pz - TT. Then, the cumulative regret incurred over
setting 3T = (1s - dd -2), x 5/2
Phases and II is bounded by
Regret, = to + + n 16-2pp-1d du VT) =0 (1-2/22 dn VT + K -2 p -w VT).
27

---

F Auxiliary Lemmas
Lemma (Lemma D.1 Zhang and Luo [41]). Let X be an instance space, Y a target space, and ply x) = =f (a y) be the true conditional density for (x, y) E X x V, where f E F. Assume -unipsihiizfuunciin
F {fo X x y + [3. 1] 0
E [0.1]. 3 > 0} is a 1-Lipschitz, function class in the parameter
E [0, ie., |e (x.)) So, (x, 0c I ||0, - 0211so for all 0,, 0 E [0, 1] and x E X. Let D [1 w:)]i=1 be i.i.d. samples with H (unknown) and ys p(- 2.). and define
the empirical risk minimizer f argmin Ei=1 loog (xi, wi). Then for any 6 (0, 1), with probability at least - 8,
D d 3
log log 1
B...H.v log fzz y) log (z. v)1 s
n
Lemma 10 (Freedman's inequality [14]). Suppose X1....,Xp is martingale difference sequence with Xx] & for all t E [T]. Let V denote the sum of conditional variances,
Var(X; ,
Then, for every a, u O,
a
P
Σ x, 2x.
S exp 2v + 2ab/3
Lemma 11 (Proposition C.1 in Lee and Oh [20]). Let fw fx(xx) =x_ w. Then the loss ((()) in Eq. (2)
Lemma 12 (Theorem 4 in Tran-Dime et al. [36]). Let f 1 + R be - function and let x, E dfm(f), then it holds:
exp (-M x112)
f3y)
Lemma 13 (Lemma 10 in Abbasi Yadkori al. [1]). Let , E Rd with ||x&|12 I L for any any 1 1 S Let V, Ma Ex=1 x,x for some 0. Then,
det V, S (A tT? /
Lemma 14 (Lemma A.3 in Agrawal et al. [3]). Letv = [uI,..., UN| E R be a utility vector and [ri,..., T E R. revenue vector. The expected revenue of an assoriment S C [N] under the utility vector defined as
R(S.v) = Σ
T:
1+
iES
Let - -uuu...... u E R be another utility vector such that 0 2s us for all i E [N). Then the following holds:
R(S,, v) R(Sv, u) S R(Su, u)
where S, == argmax R(S.v) and S. == argmax R(S, u).
Lemma 15 (Lemma H.2 in Lee and Oh [20]). Ler [ri,... ... ................... ,N
R.N with 0 S SL,E [N]
be given. For v (U,,...,uN) E RN and 5 C [N], let R(S.v)
Enss exp(v:)r;
Thenfor any
T T+ exp(os)
Wi, uN] R with for all E [N], the following holds:
R(S,, v) < R(Sv.u)
where Sy = argmaxscIM R(S,v) v). Lemma 16 (Lemma 3 in Oh and Iyengar (28)). Let (u1,..., ud], [Mi, ( vi) Rdd Then for any [r....,, ral E Rdd with Iril 1
Σ E exp(((s
E ri exp(x:)
< max u4 vzl- sEid]
+ Σ J= exp(u;)
1 Ej= exp(r;)
28

---

(wtraarr(siiiiiido (inepoool Linearli)))
Uniforn. (x)00) cost2 W 1/2
50
UCB-AVL
40
15 MNL
40
15-MAL
OFU-NNUL
Curulativv Regret
0FU-MRXL
6 gready-MMM
groady RAML
30
MNIL
30
Curmulstive
20
20
10-
(a) Realizability (Uniform)
(b) Misspecification (Uniform)
Figure 4: Cumulative regret comparison between ONL-MNL (ours) and baselines under realizable and misspecified settings with uniform context distributions.
G Details on Experiments & Additional Results
In this section, we provide additional details on the experimental settings and results discussed in the main text, All experiments are run on computing cluster with Intel Xeon Gold 6526R (16-core, 2.8 GHz, 37.5 MB cache, 3 UPI, 195 W).
Additional experiments under varying parameters. We conduct experiments over a wide range of values for K and d. The experimental setup is identical to that described in Section 4. Figures and present additional evaluations of our proposed algorithm and baseline methods under Gaussian and uniform context distributions, respectively. The results provide strong evidence that our proposed algorithm consistently outperforms existing MNL contextual bandit algorithms.
Semi-synthetic experiment with real-world dataset. In this section, we provide an additional semi-synthetic experiment leveraging real-world dataset. We used the IMDB Large Movic Review dataset [26]. which consists of 50,000 movie reviews in text form, each labeled as either positive negative. To evaluate online assortment selection algorithms, choice probabilities for given assortments, which are typically unobservable real-world datasets. To address this, first transformed the review texts into vector representations using TF-IDF (Term Frequency-Inven Inverse Document Frequency), implemented via the 'TidfVectorizer" from scikit-learn. We then applied truncated SVD reduce the dimensionality of the vectors to d 30. This process yielded a dataset consisting of 50,000 context feature vectors with corresponding binary labels.
needs access ground-truth
We then used 40,000 of these samples training data to fit binary classification model. Specifically, we trained a two-layered neural network with 32 hidden nodes to classify the binary labels. The learned model was subsequently used to define the true utility for each movic based its extracted context feature, allowing us to formulate an online assortment selection task. We then evaluated both the MNL bandit baselines and proposed algorithm under this setting.
At each round of the online experiment, we randomly sampled 10,000 held-out samples, and asked the algorithm to choose assortment of size K = 5. As in our main experiments, we used a uniform revenue for each item the assortment (since revenue information is not given in the dataset). The experimental results (cumulative regret over time step 1000) are presented Figure 5.
100 movies from the remaining
As shown in Figure 5, our proposed algorithm significantly outperforms the baseline methods. These results demonstrate that our proposed algorithm not only achieves superior performance synthetic benchmarks but also generalizes effectively to cemi-synthetic settings constructed from real- world data. The consistent performance advantage over existing baselines highlights the superior ability of our approach to learn complex, non-linear utility structures, demonstrating strong robustness and adaptability to realistic, high-dimensional feature representations. This experiment thus provides empirical evidence that our method can handle complex contextual structures beyond linear utility assumptions, supporting its potential applicability real-world recommendation and decision-n makinn environments.
29

---

N = 100, = 5, d = 30
80
UCB - MNL
TS MNL
Cumulative Regret
OFU - L +
60
3 - g reedy MNL
ONL MNL
40
20
0
200
400
600
800
1000
Round (t)
Figure 5: Cumulative regret comparison between ONL-MNL (ours) and baseline methods in the semi-synthetic experimental setting based on the IMDB Large Movie Review dataset [26].
Implementation of e-greedy-MNL. We implement M-Mreedy-MNL [41] based on the e-greedy- style method described in (4) of Zhang and Luo [41]. Since the official code for e- E-greedy-MMi not publicly available, we tailor the implementation to our problem setting. To isolate and assess the effectiveness of the exploration strategy, we set the utility function class of c-greedy--ee match the true utility function-a two-layer neural network with sigmoid activation. We adopt an epoch-based update schedule, where the first epoch starts with length 1, and each subsequent epoch doubles in length. That is, after time step / 2 (k: = 1, 2, 3,..... .). we update the utility parameter for the next epoch using observations collected in the current epoch. We approximate the offline regression oracle using the Adam optimizer with a learning rate of 10 44 over 2000 iterations. The parameter starts at 0.1 and decays multiplicatively by factor of 0.995 after each step, with minimum threshold of 0.001.
to
Implementation of ONL-MNL. After Phase the pilot estimator Wa is approximated by minimizing the negative log- likelihood using the Adam optimizer with a learning rate of 10 -4 for 2000 iterations. The regularization parameter À is set as = cx x 3/2 d/ /T, and the confidence radius 8 set as Bt ca x x T- Both scaling constants, ex and ca, selected via grid search.
30

---

Gauss Lan. fw" (x) Linear (inesiggoonnnnnnnnnlee
Gaussian, cos(2mix Tw")
UCD MALL
30-
T5 15LL
60
T5 -PRAL
Cumulattv Ragres
23
OFU
-30
6 gr -rwedy- MNLL
greedy MNL
20-
ONL
60
ONL
Cumulattr
2.-
20
20
10
0
200
400
600
800
1000
0
200
400
600
800
1000
Round (t)
Round (t)
(a) N 100, d K
10
(b) N 100, d 3, K
10
Gauss fwr1 Lineannnnniinnnnnnn Linearl(()) (1x)))
fyr
UCB MIL
T5 NILL
Cuimlaatve Regret
0FUI-MAL
Cumulative Rogret
30
0FU--MAL
15
c- greedy-MM HWLL
grredy MML
ONI -P9L.
10
100
200
400
600
800
1000
0
200
400
600
800
1000
Round (t)
Round (t)
(c) N = 100, d 3, K
(d) N 100, d 3, K 15
Gouselan, htwp:a.....0000ii2222222immm (nnarrl(())
for (X) mon 3)
60
UCB-HB
ANIL
-PVIL
Cumutatve Regret
25
greedy MNL
150
QFU-MAL-
greedy
20-
ONL MMLL
Cumalative
15
30
10
20
10-
200
400
600
800
1000
0
200
400
600
800
1000
Round (t)
Round
(e) 100,
(0) 100, d K
Gaussian, far 1inea (x0))1(00)
f. (K) mos 3) 1/12
UCB MIL
UKB-MMA
TS -Hil
TS-N
Cumulative Regret
30
.50
OFU-MALL
greedy HM.
gready
ONL MBLL
20
Cumuistive
30
20
10
200
400
600
800
1000
200
400
600
800
1000
Round (t)
Round
(g) N 100, d 10,
(h) 100, = 10, 10
Figure 6: Cumulative regret comparison between ONL-MNL (ours) and baseline methods under
Gaussian contexts with varying context feature dimensions E {3. 5, 10} and assortment sizes K (10, 15). The left column shows results under the realizable setting, while the right column corresponds to the misspecified setting. Each curve represents the average cumulative regret over 10 independent runs.
31

---

X- --nnfform (x) Linear2(ssgnoooiiee htw.reerr/ssiiioioineeeeeeeeee
Unifforn (x()) cosi2mix' "w
1/2
UCB MAL
80
TS -PRIL
Cumulativo Ragret
OFU-MAUL
Cumulstivs Regret
OFU-MPR
greedy MNL
F greedy MNL
ONL MIL.
40
200
400
1000
200
400
800
1000
Round (t)
Round (t)
(a) N 100, d 3, K
10
(h) N 100, d = 3, K 10
Unniforn, -x)
Uniforr, 5x cont2mix 1) (x 122
UCB
TS PNNL
Curulaaivv Ragret
0FU
20
<- greedy-MML
greedy-MM
ONI HBu.
ONL
15-
Cumulstivc
20
0
200
400
600
800
1000
0
200
400
600
800
1000
Round (t)
Round (t)
(c) N 100, d K
15
(d) N 100, d 3, K 15
liniforn. (2) a (M
Uniiforr, 5x)0 cosi2nix 11 (x
UCB-MAA
T5-MHiL
-INNL
Cumul brive Regret
0FU-MAL+
Cumulative Regret
2 gr greedy MNL
grgedyedy MNL
ONL HNL-
Cumulattvv
20
10
20
200
400
600
800
1000
200
400
600
800
1000
Round (t)
Round (U)
(e) N 100, d 5, K
10
(1) N 100, d 5, K 10
Uniffrrn (x) Linear2 (tn.ssiiiiiiiiinnni1aaaaaal (Linear1(x)))
Uniforr,
UCB MNL
-NIL.
-50
TS -NNNL
Cumuiative Regret
8 greedy MNI.
60
gr-grreeyyy- MNL
ONL HAL
Cumulsatvv
30
20
20
10
200
400
600
800
1000
0
200
400
600
800
1000
Round (t)
Round (t)
(g) N 100, d 10, K
(h) N 100, d= 10. K 10
Figure 7: Cumulative regret comparison between ONL (ours) and baseline methods under uniform contexts with varying context feature dimensions d E (3, 5, 10} and assortment sizes E (10, 15). The left column shows results under the realizable setting, while the right column corresponds to the misspecified setting. Each curve represents the average cumulative regret over 10 independent runs.
32

---

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

---

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

---

Justification: We provide numerical experiments in Section 4 and the detailed information of experiments in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make 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 new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibilityy 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 faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have attached the data and code with sufficient instructions to reproduce the main experimental results in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/ mablic/guides /ttgg//dd////duuunneeee (CodeSubmissionP Policy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: wttp://wwwcggucp///e////////e/// //nips. ctatps.cccpubbice http:ppullllggpl httggguddee//C/// Ceweiidde//ooeeumbmmeeeeee wttpssmmmmiiiooooooooiooooi for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
35

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide the detailed explanations for the experimental setting in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: report error bars our experiments shown Section 4.
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, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
If error bars are reported in tables or plots. The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
36

---

We provide sufficient information on the computer resources needed to repro- duce the experiments in the appendix.
Justification:
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 the paper (e.g., preliminary or failed experiments that didn't Iidntt make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: ptttps:/nnurre http///eurrrp.ppeee http:///cccpppccccccccccctiaaaa.
Answer: [Yes]
Justification: The research conducted in this paper adheres to the NeurlPS Code of Ethics in all aspects.
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., 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 societal impacts of the work performed?
Answer: [NA]
Justification: here is negative societal impacts of the work performed because this research focuses on theoretical aspects.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologics 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 tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it 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, 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 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 unintentional) misuse of the technology.
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 system learns from feedback over time, improving the efficiency and accessibility of ML).
37

---

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:
The research conducted in this paper does not pose any such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses 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 use any external assets such code, data, models.
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 used and, if possible, include 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.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. www.coo//aaao.oe com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
38

---

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


Reviews:
[{"review_id": "fpfPIOdGxz", "reviewer": "Reviewer_FLnn", "summary": "This paper tackles the contextual multinomial logistic (MNL) bandit problem, a key model for sequential assortment selection in applications like online recommendation and retail. Most prior work assumes linear utility functions, which limits expressiveness. The authors propose a new algorithm—ONL-MNL—that:\n\n1. Handles general non-linear parametric utility functions (e.g., neural networks),\n2. Achieves a regret bound of the square root of T. \n3. Is computationally tractable (unlike prior work that trades off tractability for statistical efficiency),\n4. Avoids reliance on neural tangent kernel (NTK) assumptions or overparameterization.\n\nThe algorithm uses a two-phase strategy: uniform exploration followed by optimistic exploration using a novel confidence set construction. Theoretical guarantees are supported by a new generalized geometric condition and a concentration inequality. Empirical results validate the method under both realizable and misspecified settings.", "questions": "Refer to weaknesses.", "limitations": "Refer to weaknesses.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The problem is relevant and well-motivated.\n2. The regret bound is great. However, I did not check the math in great detail.\n\n**Weaknesses:**\n\n1. Can you provide some real-world numerical evaluations? Experiments are limited to synthetic settings with fixed N, K, and d.\nThere is no exploration of scalability (e.g., larger N or deeper networks), nor any real-world datasets.\n2. As there can be multiple global minima, the convergence rate of the algorithm may depend on which global minima the algorithm finds. This may affect the regret bound. Did you consider this in the design and analysis of your algorithm?\n3. The paper is dense and highly technical. Some sections (e.g., the regret analysis) could benefit from more intuition.\n4. The regret bound depends on a problem-specific parameter $\\epsilon$, which may be small in worst-case scenarios.\n5. The baselines are mostly linear or from a single prior work on general utilities. Recent advances in neural bandits (e.g., NeuralUCB, NeuralTS) are not included.", "was_revised": true, "final_justification": "Based on the rebuttal, I have decided to maintain my score.", "rebuttal": "Thank you for taking the time to review our paper and for your thoughtful and valuable feedback. We deeply appreciate your recognition of our work and the constructive comments you have provided. Below, we address each of your comments and questions in detail:\n\n---\n[__Real-world dataset__ (W1)]\n\nSince the sequential assortment selection problem addressed in our paper involves online decision making, it is inherently challenging to obtain real-world datasets that exactly match our problem setting.\nFirst, ground-truth choice probabilities are typically unobservable in real-world environments.\nSecond, suppose there are $N$ total base items that a user can choose from. In practice, a real-world dataset would not contain responses for all combinatorially many assortments (at least $N$ choose $K$ combinations).\nIf we only have responses for a small subset of these assortments, _it becomes unclear how to evaluate an algorithm when it selects an assortment for which no feedback is available in the dataset_.\n\nFurthermore, even if suitable offline datasets exist, semi-synthetic experiments are still necessary to compute online regret—an essential evaluation metric in our setting.\nFor these reasons, we—along with the majority of prior MNL bandit work [2, 3, 4, 17, 22, 23, 24, 25, 37]—rely on synthetic datasets that simulate realistic choice behavior, enabling reliable and consistent comparisons between algorithms.\nAdditionally, we emphasize that we evaluate our method under _model misspecification_, where the true utility function differs from the estimated model, in order to better reflect practical scenarios.\n\n---\n[__Scalability__ (W1)]\n\nWe conducted experiments across a wide range of values for $K$, $d$, and different network structures, as much as time permitted.\nWe adopted the default configuration used in the original paper, setting $N = 100$, $K = 5$, $d = 3$, $L = 2$, and $m = 3$ where $L$ denotes the number of layers and $m$ denotes the number of hidden units per layer.\nIn each experiment, we varied one or more of these parameters to assess performance of the algorithms.\nWe report the cumulative regret at $T = 1000$, averaged over 5 independent runs.\n| Parameters | True utility \\& Context | $\\texttt{ONL-MNL}$ (__ours__) | $\\texttt{UCB-MNL}$ | $\\texttt{TS-MNL}$ | $\\texttt{OFU-MNL+}$ | $\\varepsilon \\texttt{-greedy-MNL}$ |\n|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| **K=10** | NN & Gaussian | __5.70__ | 25.93 | 30.01 | 25.36 | 18.49 |\n|  | NN & uniform | __11.60__ | 33.45 | 41.04 | 31.93 | 27.20 |\n|  | cos & Gaussian | __13.79__ | 33.20 | 55.32 | 30.04 | 23.38 |\n|  | cos & uniform | __10.73__ | 24.23 | 70.05 | 19.46 | 17.40 |\n| **K=15** | NN & Gaussian | __4.29__ | 17.64 | 20.16 | 16.93 | 16.02 |\n|  | NN & uniform | __5.53__ | 23.15 | 27.35 | 22.01 | 20.48 |\n|  | cos & Gaussian | __9.33__ | 21.52 | 34.64 | 19.53 | 20.66 |\n|  | cos & uniform | __6.18__ | 16.67 | 45.20 | 12.32 | 15.00 |\n| **K=10, d=5** | NN & Gaussian | __7.01__ | 23.78 | 27.60 | 23.35 | 18.40 |\n|  | NN & uniform | __8.20__ | 28.84 | 34.15 | 27.96 | 19.12 |\n|  | cos & Gaussian | __11.82__ | 31.91 | 54.45 | 29.05 | 17.52 |\n|  | cos & uniform | __6.56__ | 19.33 | 65.45 | 15.27 | 12.03 |\n| **K=10, d=10** | NN & Gaussian | __11.54__ | 38.11 | 43.65 | 37.70 | 21.28 |\n|  | NN & uniform | __12.81__ | 41.97 | 49.71 | 41.45 | 18.89 |\n|  | cos & Gaussian | __9.04__ | 28.96 | 52.84 | 28.31 | 17.09 |\n|  | cos & uniform | __4.36__ | 14.13 | 50.74 | 12.92 | 10.17 |\n| **L=3, m=20** | NN & Gaussian | __11.54__ | 57.77 | 179.70 | 62.62 | 16.50 |\n|  | NN & uniform | __8.05__ | 55.81 | 191.43 | 58.03 | 14.42 |\n|  | cos & Gaussian | __38.85__ | 60.86 | 112.21 | 64.62 | 51.41 |\n|  | cos & uniform | __24.11__ | 39.47 | 133.57 | 41.40 | 39.80 |\n| **L=5, m=20** | NN & Gaussian | __29.11__ | 112.91 | 156.37 | 116.29 | 82.12 |\n|  | NN & uniform | __17.26__ | 95.73 | 178.60 | 96.70 | 33.35 |\n|  | cos & Gaussian | __37.48__ | 60.85 | 110.66 | 65.28 | 55.02 |\n|  | cos & uniform | __28.38__ | 37.81 | 138.50 | 42.02 | 68.51 |\n\nAcross all tested settings, our algorithm consistently achieves lower cumulative regret than baselines.\nWe also note that experiments with larger $N$ are already provided in Appendix G for the reviewer’s reference.\n\n---\n[__Multiple global minima__ (W2)]\n\nThe existence of multiple global minima does not affect the main regret bound presented in Theorem 1.\nThis is because our regret analysis depends not on convergence to a particular global minimizer, but rather on how quickly the algorithm approaches the equivalence set $\\mathcal{W}^{\\ast}$.\nBased on Assumption 4, which characterizes the local geometry of the expected loss around the equivalence set $\\mathcal{W}^{\\ast}$ (as opposed to the unknown utility parameter $\\mathbf{w}^{\\ast}$), we establish a convergence guarantee for the pilot estimator $\\hat{\\mathbf{w}}\\_0$ relative to $\\mathcal{W}^{\\ast}$.\nSubsequently, the construction of the confidence set and the computation of the optimistic utility are both based on this convergence behavior with respect to the equivalence set.\nThus, the regret bound remains valid no matter which global minimum the algorithm converges to.\n\n---\n[__Density__ (W3)]\n\nSince non-linear utility functions in the MNL bandit setting have not been extensively explored in prior literature, we aimed to provide as much technical detail as possible to clearly convey the challenges of learning non-linear utilities within this framework. We respectfully believe that this level of depth is a strength rather than a weakness of the paper.\n\nIn response to the reviewer's concern, we have supplemented the intuition behind our regret analysis.\nAs the reviewer is likely aware, the core technical components of the UCB algorithm involve:\n\n(i) constructing a confidence set for the unknown true parameter (see Lemmas 1 and 2), and\n\n(ii) computing an optimistic estimate within that confidence set (see Lemma 3).\n\nIn Section 3.3, we explain how these two elements are instantiated in the context of MNL bandits with non-linear utility functions.\nIf additional space becomes available at the camera-ready stage, we would be happy to further incorporate intuition and discussion behind our regret analysis.\n\n---\n[$\\kappa$ __dependence__ (W4)]\n\nSince we do not use an $\\varepsilon$ in our manuscript, we believe the reviewer’s question as referring to the problem-dependent instance $\\kappa$.\nIndeed, our current regret bound depends on $\\kappa$.\nThis type of dependence has also been observed in prior work on MNL bandits with linear utilities [10, 19, 22, 23], and only recently have algorithms been proposed that achieve regret bounds with improved dependence on $\\kappa$ [8, 17, 37].\nA key ingredient such improvements were possible is that the negative log-likelihood in the linear MNL model exhibits a self-concordant-like property. However, this property is generally not expected to hold in non-linear utility settings, because it requires the underlying utility function to satisfy a strong third-order smoothness condition—specifically, that the third derivative is controlled by the second derivative. \nSuch functions constitute a very restricted class.\nTherefore, we believe that developing regret bounds with weaker $\\kappa$-dependence in the non-linear utility setting remains an open and challenging problem, likely requiring new analytical tools.\n\n---\n[__Baselines__ (W5)]\n\nTo the best of our knowledge, except for Zhang \\& Luo [34], almost all prior work on contextual MNL bandits assumes a linear utility function [5, 24, 22, 4, 23, 25, 2, 37, 17].\nThis is why the baselines we compare against are predominantly based on linear models.\n\nMeanwhile, _reward models used in neural bandits are fundamentally mismatched with the MNL bandit setting_. Neural bandit algorithms are designed for _multi-armed bandit problems_ that learn reward functions for individual arms, whereas MNL bandit algorithms are designed for _assortment selection problem_, where the goal is to model choice probabilities over item sets.\nThis model mismatch is also why standard linear contextual bandits like LinUCB or LinTS are not typically included in comparisons within the linear MNL bandit literature.\nHowever, we would be happy to include additional baselines if the reviewer could suggest any methods that handle non-linear utilities in the MNL setting; we are more than willing to run further experiments within the remaining review period!"}, {"review_id": "V3jj1IdeNU", "reviewer": "Reviewer_6z6s", "summary": "This paper studies the contextual multinomial logistic (MNL) bandit problem with non-linear utility function. Based on upper confidence bound (UCB) principle, a novel computationally efficient algorithm for contextual MNL is provided. Such algorithm is applicable for utility functions modelled by neural network, and achieves a near-optimal regret $O(\\sqrt{T})$ without relying on over-parameterized neural tangent kernel approximations. Numerical experiments are conducted to validate the effectiveness and robustness of the proposed algorithm, in both the realizable setting and model misspecification scenarios.", "questions": "(1)\tCould you please give more examples to show the reasonableness of Assumptions 2 and 4 ?\n\n(2)\tCould you please give more fair comparisons (i.e. the assumptions used to derive regret bounds) with related works (e.g. [34]) in the discussion of Theorem 1 ?\n\n(3)\tCould you please show empirically the value of the hyperparameter $\\kappa$ ?", "limitations": "(1)\tIt seems that the used Assumption 2 is very strong, and more examples of neural network-based bandit model (except logit bandit with negative loss) are missing.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n(1)\tThis paper proposes for multinomial logistic bandit problem a novel UCB-based algorithm, which is computationally tractable and statistically efficient. The regret bound of $\\tilde{O}(\\sqrt{T})$ is near optimal under non-linear utility settings.\n\n(2)\tThe algorithm uses two-phase optimization: in the first phase it runs uniform exploration and empirical risk minimization strategy to output a pilot estimator as the initial utility parameter for the second phase; in the second phase, the algorithm adopts a sophisticated strategy, uses the estimated parameter $\\hat{\\boldsymbol{w}} _{t}$ to construct a tight confidence set and the optimistic utility estimate, then construct the optimistic reward based on the optimistic utility estimate, finally chooses an assortment set by maximizing the optimistic expected reward.\n\n\n(3)\tIn the design of negative log-likelihood in MNL model, the authors apply a first-order Taylor approximation of the non-linear utility function to circumvent the non-linear challenges.\n\n(4)\tThe proofs are technical. I check the proofs as far as I can, the crucial technique is to leverage Lemma D.1 in Zhang and Luo [34] and the quadratic growth condition in Assumption 4 to derive high-probability convergence rate $O(1/n)$ (via induction) for $\\min _{\\boldsymbol{w} \\in \\mathcal{W}^{\\star}} \\lVert \\hat{\\boldsymbol{w}} _{t} - \\boldsymbol{w}\\rVert _{2}^{2}$, use it to set the upper confidence bound on $\\min _{\\boldsymbol{w} \\in \\mathcal{W}^{\\star}} \\lVert \\hat{\\boldsymbol{w}} _{t} - \\boldsymbol{w}\\rVert _{\\mathbf{V} _{t}}^{2}$, and eliminate the dependence on the number $N$ of items. Finally, use this upper confidence bound to derive the near-optimal regret $O(\\sqrt{T\\log{T}})$.\n\n\n(5)\tExperiments on the realizable and misspecification settings further validate the effectiveness and lower regret of the proposed algorithm.\n\n**Weaknesses**\n\n(1)\tThe major concern lies in whether the used assumptions are reasonable enough to derive improved results. For example, the boundedness of loss function/its gradient/its Hessian in Assumption 2 is a very strong assumption, especially in the non-convex deep neural network settings. It is not very clear whether such assumption is used in the related MNL works, or holds in the neural network-based bandit setting.\n\n(2)\tThe comparisons with related works are not fair enough. It is true that this work obtains sharper regret bound than that in Zhang and Luo [34], but in referent [34] their theoretical results do not rely on the very strong boundedness assumption as in Assumption 2 of this work. Besides, [34] does not use generalized geometric condition in Assumption 4 either (although I know Assumption 4 is the key assumption to derive improved regret bound of this paper). Therefore, I would suggest authors to list a table (like Table 1 in [34]) in the main paper or appendix, to explicitly compare the necessary assumptions and regret bounds of existing works and this work. \n\n(3)\tThe quadratic growth condition in Assumption 4 is the key to derive tighter confidence bound. However, more concrete examples (especially in the non-convex deep neural network bandit setting) should be added to explain the reasonableness of this assumption.\n\n(4)\tIn Theorem 1, $\\kappa=\\min _{\\boldsymbol{w}, X,S,i}p(0|X,S,\\boldsymbol{w})p(i|X,S,\\boldsymbol{w})$ is the minimum of many probability, and its value affects the number of iteration $n/T$. Will it be close to zero, and more experiments for the value of this hyperparameter should be added.", "was_revised": true, "final_justification": "Thanks authors for their detailed explanations. I have read the rebuttal and others' reviews, and most of my concerns have been addressed. This is a nice work and i still keep my positive evaluation.", "rebuttal": "Thank you for taking the time to review our paper and for your thoughtful and valuable feedback. We deeply appreciate your recognition of our work and the constructive comments you have provided. Below, we address each of your comments and questions in detail:\n\n---\n[__Reasonableness of assumptions__ (W1, W3, Q1)]\n\nWe thank the reviewer for providing us with the opportunity to clarify this point. \nFirst, we respectfully clarify that _Assumption 2 is a condition on the utility function $f$ itself, not on the loss function_.\nThe properties in Assumption 2—boundedness, differentiability, and smoothness—are standard in the bandit literature that employs parametric reward models [1, 8, 9, 10, 18, 19, 20, 27], and they are also satisfied in NTK-based neural bandits [36, 38].\nFor instance, in over-parameterized neural networks, both the gradient and the Hessian are bounded; see Lemmas B.6 and C.2 in [38].\nMoreover, in most existing MNL bandit literature [17, 22, 23, 25, 37], the utility function is assumed to be linear, in which case Assumption 2 holds trivially.\n\nWe also clarify that _Assumption 4 does not require a quadratic growth condition_.\nInstead, it introduces local strong convexity and a $(\\tau, \\gamma)$-growth condition (for $0 < \\gamma < 2$) on the expected loss $\\ell(w)$ around the equivalence set.\nAlso, Assumption 4 is satisfied by a broad class of neural networks studied in prior work.\nFor example, the local strong convexity of the population risk has been shown for two-layered neural networks (Zhong et al., 2017), quadratic neural networks [31], and ReLU networks (Zhang et al., 2019), all of which fall within the scope of our assumption. \nThese models typically involve multiple global minimum (due to symmetries), and thus fall outisde the scope of earlier geometric conditions that rely on uniqueness of the global minimum.\nWe will add this comment on the revised version.\n\nNow, we would like to reiterate that Assumption 4 is strictly weaker than the global strong convexity assumed in prior parametric bandits [1, 8, 9, 10, 19], and does not require the existence of a unique global minimum [18, 20, 27].\nThis allows for an arbitrary number of spurious local minima and global minima in the landscape of the expected loss, enabling our analysis to cover highly non-convex and non-linear utility functions.\nIn summary, _the function class covered by Assumption 4 generalizes the parametric function classes studied in prior bandit literature, and additionally includes a broader family of non-linear, non-convex functions that have not been addressed in earlier works_.\n\n(References)\n\n- Zhong et al. (2017), \"_Recovery Guarantees for One-hidden-layer Neural Networks_\", ICML\n- Zhang et al. (2019), \"_Learning One-hidden-layer ReLU Networks via Gradient Descent_\", AISTATS\n\n---\n[__Comparison with Zhang \\& Luo (2024)__ (W2, Q2)]\n\nWe appreciate the reviewer's suggestion and will include a table that compares the assumptions and regret bounds of prior work and ours.\n|  | Utility class | Assumptions | Tractability | Regret |\n|:---:|---|---|---|---|\n| Corollary 3.5 [34] | Boundedness, Lipschitzness | Stochastic context, offline regression oracle | O | $\\tilde{O}\\left( (d N K)^{1/3} T^{2/3} \\right)$ |\n| Corollary 3.8 [34] | Boundedness, Lipschitzness | Stochastic context, offline regression oracle | X | $\\tilde{O} \\left( K^2 \\sqrt{d N T} \\right)$ |\n| Corollary 4.4 [34] | Boundedness, Lipschitzness | Adversarial context, online regression oracle | O | $\\tilde{O} \\left( (N K)^{1/3} T^{5/6} \\right)$ |\n| Corollary 4.8 [34] | Boundedness, Lipschitzness | Adversarial context, online regression oracle | X | $\\tilde{O} \\left( K^2 \\sqrt{d N T} \\right)$ |\n| This work | Boundedness, Lipschitzness, smoothness | geometric condition, stochastic context (Phase I) | O | $\\tilde{O} \\left(\\kappa^{-2} \\mu^{-1} d_w \\sqrt{T} \\right)$ |\n\n\nWe would like to clarify that Zhang \\& Luo [34] also make boundedness and Lipschitz continuity assumptions.\nAs mentioned in the main text, Assumption 4 is required in Phase I to establish the convergence rate of the pilot estimator.\nIn contrast, the analysis in [34] relies on the generalization error of the (offline or online) regression oracle measured in terms of log-loss (Assumption 2 \\& 3 in [34]), rather than on the distance between the estimator and the true parameter.\nThis implies that _even if a geometric condition like our Assumption 4 were imposed in the setting of [34], it would not yield any advantage in terms of computational tractability_.\n\nOn the other hand, under the same generalization error rate of $O(1/n)$ established in [34], we show that, when combined with Assumption 4, this is sufficient to guarantee a fast convergence rate of the estimator.\nThe main contribution of our work lies in _proposing an algorithm for MNL bandits with non-linear utilities that is both computationally tractable and statistically efficient, under Assumption 4, which is satisfied by a broad class of parametric models and neural networks_.\nWe believe it remains an open question how large the class of utility functions is in practical scenarios where Assumption 4 does not hold, and whether a suitable regression oracle, as required in [34], exists for such function classes.\n\n---\n[__About__ $\\kappa$ (W4, Q3)]\n\nBy definition, $\\kappa^{-1} = O(K^2)$ in the worst-case scenario, and we use $\\kappa = \\frac{\\exp(-1)}{(1 + K \\exp(1))^2}$ in our numerical experiments.\nWe would like to note that in our current analysis, the dependence of $n$ or $T$ on $\\kappa$ serves as a sufficient condition for achieving the $\\tilde{O}(\\sqrt{T})$ regret bound.\nHowever, as shown in our experiments, the algorithm performs well even with a small number of pure exploration rounds, suggesting that the theoretical $\\kappa$-dependence may be overly conservative in practice.\nWe believe that closing this gap, or deriving regret bounds with improved dependence on $\\kappa$ in the context of non-linear MNL models, remains a valuable direction for future research."}, {"review_id": "Ot2Q48luBh", "reviewer": "Reviewer_iMPD", "summary": "This paper studies the multinomial logit bandit problem with parameterized non-linear utility functions. Unlike prior works on this problem, computational and statistical efficiency are simultaneously achieved; the authors propose a new algorithm that achieves the order-optimal $\\sqrt{T}$ rate while allowing tractable implementation. The algorithm has two phases: the first is a random exploration phase where an initial estimate of the latent parameter defining the utility function is learned, while in the second phase, a UCB approach is adopted. The estimated parameter vector is refined in the second phase via minimizing at each round a regularized negative log-likelihood function that employs a linear relaxation of the utility function, while the predictions (assortments) are chosen so as to maximize the expected reward when using optimistic estimates for the utility values. The achieved regret bound does not depend on the number of arms nor the cardinality constraint, but depends on a problem-specific constant $\\kappa$.", "questions": "* Can you argue for the tractability of solving the optimization problem through which the initial estimate is obtained?\n* Why is the dependence on $\\kappa$ preferred over a dependence on $K$ or $N$? Are there interesting cases that can motivate this?\n* Do you believe that assumption 4 is necessary for obtaining a sharp regret rate efficiently?", "limitations": "The authors acknowledge that the dependence of the regret on (the reciprocal of) $\\kappa$ can be a limitation. No other limitations/shortcomings seem to be highlighted in the paper.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "On the positive side, by proposing a provably statistically efficient and tractable algorithm, the paper seems to bring forth a significant contribution to a challenging but practically relevant problem that combines a combinatorial structure with complex utility function and feedback mechanism. The paper also seems to provide new technical contributions like employing a linearized MNL model and establishing a new concentration result. The presentation of the paper is mostly clear and the writing is of good quality.\n\nOn the other hand, maybe I missed this, but it does not seem that the authors have established the tractability of solving the optimization problem through which the initial estimate is obtained. In fact, it has been mentioned on two occasions that the negative log-likelihood function lacks important properties here compared to the linear case, but only its effect on the analyses is highlighted. Moreover, it is not entirely clear if the dependence of the regret on $\\kappa$ is in any way natural, it also seems that Zhang and Luo [34] argue that this could result in an exponential dependence on some problem parameters. This limitation is mentioned in the conclusion, but elsewhere it is asserted that this is preferred over depending on the number of arms or the cardinality constraint as in [34]. Maybe the authors can elaborate more on why this is the case. It is also worth mentioning that in obtaining their results, the authors employ extra assumptions compared to [34], even as the relative mildness of which is extensively argued for. Lastly, it seems that a similar 'reverse Lipschitz' property has already been established in [34, Lemma 3]; hence, some credit should be given. Maybe the paper could benefit from a more explicit comparison with the techniques in [34].", "was_revised": true, "final_justification": "After reading the other reviews and the rebuttal, I maintain my positive evaluation of the paper as the contributions seem significant. I hope the authors will incorporate the discussion about the worst-case behaviour of $\\kappa$ and the computation required for obtaining the pilot estimator in the revised version.", "rebuttal": "Thank you for taking the time to review our paper and for your thoughtful and valuable feedback. We deeply appreciate your recognition of our work and the constructive comments you have provided. Below, we address each of your comments and questions in detail:\n\n---\n[__Computation tractability__ (W, Q1)]\n\nWe are glad to address this comment.\nWe would like to clarify that the notion of tractability in both Zhang \\& Luo [34] and our work refers to the _computational feasibility of the exploration strategy_, i.e., the _process of selecting an assortment given a current utility estimator_.\nThe computation required for obtaining our pilot estimator is comparable to what is already used in [34]; for instance, their use of offline regression oracles in the stochastic setting and online regression oracles in the adversarial setting (see Assumptions 2 and 3 in [34]).\nAs in [34], any tractable empirical risk minimization method (e.g., SGD) is sufficient for computing our pilot estimator in practice.\nWe will incorporate this point into the revised manuscript.\n\n---\n[$\\kappa$ __dependence__ (W, Q2)]\n\nWe are happy to answer this question. \nBy the definition of $\\kappa$, we have $\\kappa^{-1} = O(K^2)$ in the worst-case scenario.\nNote that the exponential dependence can be adjusted by rescaling the utility values. Zhang \\& Luo [34], for instance, define the MNL probability model using bounded utilities without applying the exponential transformation; see Eq. (1) in [34].\nConsequently, our reverse Lipschitzness result (Lemma 4) can be used to recover the reverse Lipschitz bound in [34] (Lemma B.3).\nNevertheless, we adopt a $\\kappa$-dependent analysis because, while $\\kappa^{-1}$ can scale as $O(K^2)$ in the worst case, its behavior is often far more favorable in practice.\nFor example, as shown in the experiments of Lee \\& Oh [17] (Figure 1), the gap between the regret of $\\kappa^{-1}$-dependent algorithms (e.g., UCB-MNL [23], TS-MNL [22]) and that of $\\kappa^{-1}$-improved algorithm (e.g., OFU-MNL+ [17]) diminishes as $K$ increases.\nThis implies that  the regret of $\\kappa^{-1}$-dependent algorithms [22, 23] does not grow significantly with $K$, even as $K$ increases.\nThis suggests that equating $\\kappa$ with $1/K^2$ or treating it as equivalent to $K$ is overly pessimistic.\n\nIn contrast, the dependence on $N$—the total number of items—is a more serious limitation.\nAs discussed in the main text, our regret bound is independent of $N$.\nHowever, all algorithms in [34] exhibit polynomial dependence on $N$, regardless of tractability.\nThis poses a significant obstacle for real-world applications involving large item sets—for example, platforms like Amazon, where the number of items can reach into the millions.\n\n---\n[__Assumption 4__ (W, Q3)]\n\nEven though Assumption 4 is used as a sufficient condition to establish the fast convergence rate of the pilot estimator, we do not believe it a necessary condition.\nWe expect that comparable convergence rates could still be achieved without relying on Assumption 4, if one instead uses parametric models with specific structures—such as one-hidden-layer neural networks with ReLU activation [31] or quadratic activation [32]—rather than broad classes of non-linear parametric functions.\nHowever, it is worth noting that even with such structural assumptions, existing convergence analyses often require the context vectors to be sampled from specific distributions (e.g., uniform over the unit sphere [31]), which limits their applicability in practical settings."}, {"review_id": "lO2SBOfBlp", "reviewer": "Reviewer_ZnVB", "summary": "The paper studies multinomial logistic bandits where the action is a set of $N$ items and the feedback is the item chosen. The choice model is a logistic model where the utility of an item depends on the context and the item. The utility function is assumed to be a non-linear parametric function and the learner has access to the parametric function class. The paper proposes a two-stage algorithm where the first state does uniform exploration and the second stage uses the principle of optimism to select the most optimistic set of items. A naive explore-then-commit type of algorithm gives suboptimal regret bound. The paper introduces novel regularization and accompanying analysis to get the optimal $\\sqrt{T}$ regret bound.", "questions": "Q1) What if the parameter $\\kappa$ in the regret bound is very small? Is there a trivial lower bound on $\\kappa$? What is the intuition for the dependence on $\\kappa^{-1}$? For example, why would the presence of an item that is rarely chosen make the problem harder?\n\nQ2) In Line 194, the paper says the context vectors after Phase I may be chosen adversarially. This questions the role of Phase I. What if the context distribution is only along one direction, and the contexts are chosen adversarially to be orthogonal to that direction? In this case, wouldn't the data in Phase I be obsolete?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper is clearly written and the algorithm is well-motivated by its accompanying analyses.\n\nWeaknesses:\n\nThere are some parts of the results presented that raise some questions. (See below).", "was_revised": true, "final_justification": "Authors have addressed my concerns: question on problem-dependent constant $\\kappa$ and the clarification on the assumption.\nThe submission is technically strong with clear theoretical contribution.", "rebuttal": "Thank you for taking the time to review our paper and for your thoughtful and valuable feedback. We deeply appreciate your recognition of our work and the constructive comments you have provided. Below, we address each of your comments and questions in detail:\n\n---\n[__Dependence on__ $\\kappa$ (Q1)]\n\nBy the definition of $\\kappa$, $\\kappa$ is lower bounded by $\\Omega(1/K^2)$, i.e., $\\kappa^{-1} = O(K^2)$.\nHowever, we would like to emphasize that its behavior is often far more favorable in practice.\nFor example, as shown in the experiments of Lee \\& Oh [17] (Figure 1), the gap between the regret of $\\kappa^{-1}$-dependent algorithms (e.g., UCB-MNL [23], TS-MNL [22]) and that of $\\kappa^{-1}$-improved algorithm (e.g., OFU-MNL+ [17]) diminishes as $K$ increases.\nThis implies that  the regret of $\\kappa^{-1}$-dependent algorithms [22, 23] does not grow significantly with $K$, even as $K$ increases.\nThis suggests that equating $\\kappa$ with $1/K^2$ or treating it as equivalent to $K$ is overly pessimistic.\n\nFor intuition behind $\\kappa$, the parameter $\\kappa$ is closely related to the curvature of the expected negative log-likelihood function.\nConsider the expected loss defined as $L(\\mathbf{w}) = \\mathbb{E}[- \\log p(i \\mid X, S, \\mathbf{w})]$.\nThen, the Hessian of $L(\\mathbf{w})$ is given by\n$$\n    \\nabla^2 L(\\mathbf{w}) = \\mathbb{E}\\left[ \\sum\\_{i \\in S} p(i \\mid X, S, \\mathbf{w}) \\nabla f\\_{\\mathbf{w}}(\\mathbf{x}\\_i) \\nabla f\\_{\\mathbf{w}}(\\mathbf{x}\\_i)^\\top - \\sum\\_{j \\in S} \\sum\\_{k \\in S} p(j \\mid X, S, \\mathbf{w}) p(k \\mid X, S, \\mathbf{w}) \\nabla f\\_{\\mathbf{w}}(\\mathbf{x}\\_j) \\nabla f\\_{\\mathbf{w}}(\\mathbf{x}\\_k)^\\top \\right] .\n$$\nUsing standard calculations (see Lemma B.5 in [25]), this Hessian can be lower-bounded as:\n$$\n    \\nabla^2 L(\\mathbf{w}) \\succeq \\mathbb{E} \\left[ \\sum\\_{i \\in S} p(i \\mid X, S, \\mathbf{w}) p(0 \\mid X, S, \\mathbf{w}) \\nabla f\\_{\\mathbf{w}}(\\mathbf{x}\\_i) \\nabla f\\_{\\mathbf{w}}(\\mathbf{x}\\_i)^\\top \\right],    \n$$\nwhere $p(0 \\mid X, S, \\mathbf{w})$ denotes the probability of outside option.\nIn this context, $\\kappa$ serves as a uniform lower bound on the product $p(i \\mid X,S, \\mathbf{w}) p(0 \\mid X,S, \\mathbf{w})$, and therefore provides a lower bound on the minimum eigenvalue of $\\nabla^2 L(\\mathbf{w})$.\nSince smaller eigenvalues indicate a more ill-conditioned log-loss landscape, a smaller $\\kappa$ implies that the learning problem is more challenging.\n\nAlternatively, we can think of how the probability of outside option relate to learning difficulty as follows. \nConsider the following example with two items $i_1, i_2$:\n- [Case 1] $p(0) = 0.3, \\quad p(i_1) = 0.35, \\quad p(i_2) = 0.35, \\quad \\kappa = 0.3 \\times 0.35 = 0.105$\n- [Case 2] $p(0) = 0.9, \\quad p(i_1) = 0.09, \\quad p(i_2) = 0.01, \\quad \\kappa = 0.9 \\times 0.01 = 0.009$\n\nIn Case 2, the high probability of the outside option reduces the likelihood of observing for items $i_1$ and $i_2$.\nAs a result, the expected number of rounds needed to observe feedback for those items is significantly higher than in Case 1. \nThis demonstrates that small value of $\\kappa$ require more samples to gather informative feedback on individual items, thus increasing the overall sample complexity of learning. \n\n---\n[__Role of Phase I__ (Q2)]\n\nWe are happy to answer your question.\nAs described in Assumption 3, the context distribution is assumed to be supported on the context space $\\mathcal{X}$.\nThis implies that the distribution in Phase I is not restricted to a single direction.\nTherefore, the case where all Phase I contexts lie along a single direction—rendering them obsolete when Phase II contexts are orthogonal to that direction—would not occur."}]

Author rebuttal:

Meta-review: The paper introduces a new optimistic algorithm and stronger regret guarantees for multinomial logistic bandits with nonlinear values. This is a very general and practically important setting, and the theoretical and algorithmic contributions are significant. These results are derived under strong Lipschitz‐continuity and smoothness conditions, which often scale poorly in deep networks. Furthermore, the authors should clarify the role of \kappa in their regret bound as well as the computational cost of their algorithm.
Decision: Accept (poster)