Improved Online Confidence Bounds for Multinomial Logistic Bandits
Authors: Joongkyu Lee
Min-hwan Oh
Venue: ICML 2025 poster (2025)
Keywords: Bandit
Multinomial Logistic Bandit
Confidence Bound
Regret
Online Mirror Descent
Primary area: theory->online_learning_and_bandits
TL;DR: We establish an improved online confidence bound for MNL models and, leveraging this result, propose a constant-time algorithm that achieves the tightest variance-dependent optimal regret in contextual MNL bandits.

Abstract: In this paper, we propose an improved online confidence bound for multinomial logistic (MNL) models and apply this result to MNL bandits, achieving variance-dependent optimal regret. Recently, Lee & Oh (2024) established an online confidence bound for MNL models and achieved nearly minimax-optimal regret in MNL bandits. However, their results still depend on the norm-boundedness of the unknown parameter $B$ and the maximum size of possible outcomes $K$. To address this, we first derive an online confidence bound of $\mathcal{O}(\sqrt{d \log t} + B \sqrt{d} )$, which is a significant improvement over the previous bound of $\mathcal{O} (B \sqrt{d} \log t \log K )$ (Lee & Oh, 2024). This is mainly achieved by establishing tighter self-concordant properties of the MNL loss and applying Ville’s inequality to bound the estimation error. Using this new online confidence bound, we propose a constant-time algorithm, **OFU-MNL++**, which achieves a variance-dependent regret bound of $\mathcal{O} \Big( d \log T \sqrt{ \sum_{t=1}^T \sigma_t^2 } \Big) $ for sufficiently large $T$, where $\sigma_t^2$ denotes the variance of the rewards at round $t$, $d$ is the dimension of the contexts, and $T$ is the total number of rounds. Furthermore, we introduce a Maximum Likelihood Estimation (MLE)-based algorithm, **OFU-M$^2$NL**, which achieves an anytime $\operatorname{poly}(B)$-free regret of $\mathcal{O} \Big( d \log (BT) \sqrt{ \sum_{t=1}^T \sigma_t^2 } \Big) $.

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Joongkyu Lee"
Min-hwan Oh
Abstract
ment selection problems. At every round an agent offers assortment of at most K items among total N items and receives feedback only for the chosen decisions. The user choice probability follows an MNL model (McFadden, 1977). This framework is widely deployed in industry, with applications ranging from news recommendation systems to online retail, where assortment selections are optimized based on user-choice feedback from the offered options. In such applications, the agent often has access to item fea- tures and, potentially, contextual information about the user. This setup is referred to as the contextual MNL bandit prob- lem (Agrawal et al., 2019; 2017: Ou et al., 2018; Chen et al., 2020; Oh & Iyengar, 2019; 2021; Perivier & Goyal, 2022; Oh, 2024).
In this paper, we propose an improved online con- fidence bound for multinomial logistic (MNL) models and apply this result MNL bandits, achieving variance-dependent optimal regret. Re- cently, Lee & Oh (2024) established online confidence bound for MNL models and achieved nearly minimax ootimmll regret in MNL bandits. However, their results still depend on the norm- boundedness of the unknown parameter and the maximum size of possible outcomes K. To address this, first derive online confidence bound of O (Volog/+ + Bvd), which sig- nificant improvement over the previous bound of OBVVlog log K) (Lee & Oh, 2024). This is mainly achieved by establishing tighter self- concordant properties of the MNL. loss and ap- plying Ville's inequality to bound the estimation error. Using this new online confidence bound, we propose a constant- constant-time algorithm, OFU-MNL++, which achieves a variance-dependent regret bound of O Od lolo TV of) for sufficiently large T. where of denotes the variance of the re- wards at round
Agrawal et al., 2023; Lee
Recently, in contextual MNL bandits, Lee & Oh (2024) proposed constant-timg algorithm and obtained regret of O B3/22d dd log K (log 3)3/2 /T). Although this result is nearly minimax optimal when ignoring B and logarithmic terms, it still depends on the maximum assortment size K and the norm- hoen--bouddddesss of the parameter B. Intuitively, larger may provide more information (Lee Oh, 2024), suggesting that the regret should scale with any factor involving K. Moreover, while poly (B)-free regret bound has been established for generalized linear model (GLM) bandits (Lee et al., 2024b) using the MLE, it remains unclear whether such bound can be obtained while maintaining a constant per-round computational cost.
is the dimension of the con- texts, and T is the total number of rounds. Fur- thermore, introduce a Maximum Likelihood Estimation (MLE)-basee algorithm, NL. which achieves anytime poly (B))-ree regret of O (dlog(BT) E
Our main goal is to design constant- time algorithm that achieves improved regret with respect to poly (B) and K. The main challenge in achieving such regret lies in deriving tight confidence bound. Currently, the best-known online confidence bound is O(Bvdd log log K) (Lee & Oh, 2024), which explicitly depends on both B and log K. This depen- dency poses a significant bottleneck for obtaining improved regret. Furthermore, the best of our knowledge, there no variance- regret in contextual MNL bandits. Hence, the following research questions arise:
1. Introduction
The multinomial logistic (MNL) bandit framework (Rus- mevichientong et al., 2010; Sauré & Zeevi, 2013; Agrawal et al., 2017; 2019; Oh & Iyengar, 2019; 2021; Perivier & Goyal, 2022: Agrawal et al., 2023; Lee Oh, 2024) pro- vides a principled approach tackling sequential assort-
Can we derive B, K. K-improved confidence bound for online parameter estimation in MNL models?
'Scoul National University, Scoul, Korca. Correspondence to: Min-hwan Oh <minoh@ an
Can we design a constant-time algorithm that achieves B, K K-improved (or free) and variance variance-dependeri re- gret contextual MNL bandits?
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
In the first part of our main results (Section 4.1), we con- struct K-free online confidence bound with improved dependence on B, which depends a update condition parameter a. This significantly improves upon previous re- sults in online parameter estimation in MNI. models (Zhang & Sugiyama, 2024; Lee & Oh, 2024). To achieve this, we first establish self-concordant like properties with respect to the -nomm (instead of the traditional lz-norm) (Proposi- tions B.3 to B.6). This improvement enhances the existing self-concordant properties of MNL models (Tran-Dinh et al., 2015), which is of independent interest. Then, unlike Zhang & Sugiyama (2024); Lee & Oh (2024), we apply Ville's inequality (Ville, 1939) to bound estimation errors, thereby avoiding the need for a smoothing technique (Foster et al., 2018), which would otherwise lead O( /loo t log K) looser confidence bound.
B K) (Lee & Oh, 2024). More importantl, when the parameter is updated within specific space where the update condition parameter a is bounded by a constant, we achieve a confidence bound of O(ydlog Byd), which is completely independent of poly(B) (B) and K.
New B-improved, K-free, variance-dependent re- gret bound: To apply our new online confidence bound to MNL bandits and achieve tighter regret in terms of poly(B) and K, we propose an algorithm called OFU-MNL++. In addition, through a novel regret decomposition, we derive a variance-deeendent opti- mal regret of O (dlog + Bdylog V |
where of & 1 represents the variance of the rewards at round t. For sufficiently large T,, we obtain a Ó 0(dv T - of) regret. To the best of our knowledge, this is the first B, K-free and variance-dependent opti- mal regret bound in contextual MNL bandits.
In the second part (Section 4.2), we propose constant-time algorithm, called OFU-MNL++, that achieves B-improved, K-free, and variance-dependent regret. This algorithm up- dates the parameter only within a specific space constructed during the adaptive warm-up rounds. With high probabil- ity, this space contains the true parameter w', while also shrinking sufficiently relative to the current feature set X,. This is the key to kceping the update condition parame- ter a of the online confidence bound small (or constant). Note that since the parameter is updated in a fully online manner, the computational cost per round of OFU-MNL++ remains constant throughout all rounds. Furthermore, we introduce novel regret decomposition, which ultimately allows us to achieve a variance-dependenn regret bound of o Id T + (ol/TogT) V / o?) where of denotes the variance of the (chosen) rewards at round t.
Completely poly(B), (B), K K-freee confidence and regret bound using MLE: We propose an MLE- based algorithm, OFU-M which achieves pBly Kfrree variance-dependent optimal regret of O [ollog(BT) ET= ( of) by leveraging B-free MLE confidence bound.
2. Related Work
Logistic bandits. The logistic bandit problem (Dong et al., 2019; Faury et al., 2020; Abeille et al., 2021; Faury et al., 2022; Lee et al., 2024a;b) is special case of the MNL bandit problem. In this setting, the agent offers only single item (i.e., K" = 1) and receives 0-1 binary feed- back, restricting the problem to the uniform rewards setting, As summarized in Table 1, recent works have successfully climinated the harmful dependency on 1/k (which can be exponentially large) in the leading term, achieving instance- dependent regret (i.e., ki -eeeenddent regret). However, most of these approaches still suffer from unnecessary depen- dency on the norn-boundedness of the unknown parameter, poly(B), While a recent work by Lee et al. (2024b) suc- cessfully eliminated the poly( factors, their approach incurs per-round computational cost that grows linearly with 1. Thus, the question of whether is possible to design B-free, computationally efficient algorithm remains open.
In the final part (Section 4.3), as an independent contri- bution and inspired by Lee et al. (2024b), we propose an MLE-based algorithm, NL,, that leverages an MLE confidence bound and achieves completely poly BB), K-free regret with only log B dependence. However, note that the per-round computational cost of OFU-M-NL increases lin- early with due to the use of the MLE, whereas the per- round computational cost of OFU-MNL++ remains constant.
Our main contributions are summarized as follows:
Sharper online confidence bound for the MNL mod- els: We first establish a confidence bound for on- line parameter updates in MNL models, which de- pends on the update condition parameter a (detined later). In Theorem 4.2, when the parameter is updated over the entire space Bd(B) as is common in prior works (Faury et al., 2022; Zhang & Sugiyama, 2024; Lee & Oh, 2024), we achieve a confidence bound of O(Bydlog + B3/2 + B²), significantly improv- ing upon the previous bound of O(Bv DOBydloo log t log K +
MNL bandits. The MNL bandits (Agrawal et al., 2019; 2017; Ou al., 2018; Chen et al., 2020; Oh & Iyengar, 2019; 2021; Perivier & Goyal, 2022; Agrawal et al., 2023; Lee & Oh, 2024) address more sophisticated problems compared to logistic bandits, as they involve selecting a set of items (thus highlighting their combinatorial nature) and consider
2

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Table 1: Comparisons of regret bounds in recent works on contextual logistic and MNL bandits with '' rounds, the maximum size of assortments K, d-dimensional feature vectors, the norm-boundedned of the unknown parameter B, problem-dependent constants 1/x- O(K² and : - Pe(i]S;, w w")p:(O|s; w*) & 1, and the variance of the rewards of & 1 at round t (formally defined in (9)). For the computational cost (abbreviated as "Comput."", " consider only the dependence on i. The term "Intractable" refers to computational runtimes that are non-polynomial.
Algorithm
Regret
Rewards
Comput per Round
Abeille et al. (2021)
o Bl T
Li
Uniform
Intractable
(OFUL.gg)
Abeille et al. (2021)
Blog Tv
Uniform
((f)
Logistic Bandits
(OFULog-r)
Faury et al. (2022)
Bdlog Ei=1 16)
Uniform
(log t)
Pada-OFU-To OPU-ECOLog)
Lee et al. (2024b)
dlog(BT)) 2m-1137
Uniform
O(t)
(OFUGLB)
Chen al. (2020)
Bdlog(kT))))
Uniform/Non-Unifeen
Intractable
(NLE-UCB) UCB)
Oh & Iyengar (2021)
[llogTVT) = O (K*e"dlogTVT)
Uniform/Non
Cetoom//on-Unffomm Uniform
O(t)
(UCB-MM) NNL)
MNL Bandits
Perivier & Goyal (2022)
BKdlog(KT) (T)) Ei'n m77
Uniform
Intractable
(OFU-NNL)
Lee & Oh (2024)
B K T)///
Uniform/Non-Uniae
(
(OFU-NM) NNL+)
This work
(dlogT + Bdglog T)
V /2T11 o?
Uniform/Non Ciniom/m/on-Uiffomm
O(1)
(OFU-NNLL ++, Theorem 4.5)
This work
d (ogg(BT) E Ei=1
Uniform/Non Uniforrm
O(f)
(OFU-NXXL, Theorem 4.12)
non-uniform rewards rather than binary feedback. Recently, Lee & Oh (2024) made significant progress by resolving the long-standing open problem of establishing the mini- max optimal regret (ignoring factors of and logarithmic terms) with computational efficiency. However, shown in Table 1, all existing regret bounds increase with B and K. Furthermore, the tightest regret bound by Lee & Oh (2024) includes an additional (log 1/2 term, arising from a loose confidence bound. To address these limitations, in this paper, we construct the sharper online confidence bound to date and, leveraging this, achieve (asymptotically) B, K-free regret while maintaining computational efficiency.
pendency on L/x e in their regret bounds. Park et al. (2024) further extended this direction to the infinite- horizon setting.
3. Preliminaries
Notations. For a positive integer n, define [n] as the set 11,2,..., The l2- and foom of a vector x is denoted by |-|2 and |>>| respectivll. For a positive semi- definite matrix A and a vector æ, we use ||æ]]A to represent
V Az. For any two symmetric matrices A and B of the same dimensions, A Z B indicates that A - B a positive semi-definite matrix. Finally, we define as the set of candidate assortments with a size constraint of at most K, i.e., S (S [N] |S| < K3.
RL with MNL models. There has been growing interest in incorporating MNI. models into reinforcement learning (RL). One line of work extends MNL bandits to the RL setting. Recently, Lee & Oh (2025) proposed a new frame- work, called combinatorial RL with preference feedback, in which the agent selects a subset of items in each round maximize long-term cumulative reward based on MNL- modeled preferences, and established the minimax-optimal regret bound in linear MDPs (Jin et al., 2020).
3.1. Problem Setting
We consider the contextual MNL bandit problem, where an agent selects assortments (sets of items) and receives feedback based on user choices. Specifically, each round t, the agent receives a feature vector 24s Rd and re- ward rti for every item i e [N]. Note that the feature set X; = { and rewards (ru) can be arbitrarily cho- sen by an adversary. The agent then offers an assortment S. (4,.... i) E S, where & K. After presenting the assortment, the agent observes the user's purchase decision
Another direction focuses on RL with MNL-based transition models. Hwang & Oh (2022) introduced MNI-MDPs, a class of MDPs where the transition probabilities are param- eterized by an MNL model. Building on this, Cho et al. (2024) and Li al. (2024) concurrently improved the de-
3

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Ct St U (0), where (0) represents the "outside option", in- dicating that the user did not choose any item from S₁. The user choices are modeled using the Multinomial Logistic (MNL) framework (McFadden, 1977), where the probability of selecting an item i E St u (0) is defined as:
& Tyengar, 2021; Perivier & Goyal, 2022), we follow the
approach of Zhang & Sugiyama (2024); Lee & Oh (2024) and adopt the online mirror descent (OMD) algorithm for parameter estimation. To begin, we define the multinomial logistic loss function for round & as:
exp(x),w" w Pr(i w") = 1+ Ljes, exp(a,,,") w-)
(w)) == Σ VE
Yu log po w).
(I)
where w' E Rd is an unknown parameter and Z10 =
In this paper, we present a general description of online pa- rameter estimation. We consider a (possibly) rime-varying compact convex search space W; S Rd and allow for occa- sional updates to the parameter rather than requiring updates at every round. We denote T = [T] as all the update rounds. At the update round t E T, the true parameter w is esti- mated as follows:
The choice response for each item i E Se U {0} is defined as Yts (e: = i) E {0, Hence, the choice feedback vector Y: == (yto, Yti. (ea)) is sam-
pled from the multinomial (MNL) distribution yt ~ MNL(1, (O)s,, w') w'),.... PP,...,,((inn St, w"))], where the pa- rameter 1 indicates that y, is a single-trial sample, meaning yoo + Ei=1 Yei. = 1. Then, the expected revenue of an assortment S is defined as:
w/ argmin ||w-| - -well,, weW,
(projection onto W,)
1 |w willi, (2) 2n
Eieg exp(1x] ("" I+E exp(1r)) w*)
Wx+1 argmii
a (Vl(ww)) w> + weW,
R,(S, Σ (ilS, IES
where 7 > 0 is the step-size parameter, and W; S Rd is the compact convex set, which will be specified later. The matrix H, is defined as HI, := Hr + (w((), where H₂ == AI ESETY (W with X > 0.
We denote Si as the optimal assortment at time t, i.e. S == argmaxses Re(S. w"). The goal of the agent is to minimize the cumulative regret over the T rounds:
Regr(w")=
Σ Re(S;, w*) - Re(S,, w").
If no update is performed, we, Hr and H₂ remain unchanged. Formally, let l' E T denote the last update round prior to t (i.e., 1' < t). Then, we have we+1 He+1 = ................................ = Hr, and H1:11 = =.... Hr.
When K and rr1 1, the MNL bandit reduces to the bi- nary logistic bandit with R&(S- {xx, w") = a (x w=) 1/(1 + exp(-x" xxp)- where (.) is the sigmoid function.
W.,
In the optimization problem (2), we first solve the uncon- strained optimization problem in closed form, obtaining W(+1 Then, we project w'-1 back into the feasible set.
We will work under the standard boundedness assumption. Assumption 3.1 (Bounded assumption). We assume that, for all t > ee e [M] [a & and I' e [o, 1]. There exists a known constant such that [w"] E B,
W = w/ "i-nn,,'((((
W1+1 = argmin ||w w'tl
weW,
Following the previous contextual MNL bandit litera- ture (Oh & Iyengar, 2021; Perivier & Goyal, 2022; Zhang & Sugiyama, 2024; Lee & Oh, 2024), we introduce the problem-dependent constant:
This estimator is efficient in both computation and storage. Remark 4.1 (Computational cost). For general convex set We. the projection optimization problem (e.g., Equation (3)) can be solved up to e >> O accuracy using the Projected Gra- dient Descent algorithm (c.g.. Algorithm 2 in (Hazan et al., 2016)), requiring computational cost of O(K log (1))). As a special case, if W; is an ellipsoid, the optimization problem can be solved in a single projection step (via closed-form projection), which needs only O(Kd)) cost.
Definition 3.2. Let W = {w& Rd| ||| & B). There exists K > 0 such that, for any E S. S e S, and / E [T]. we have minwew (i)S, (OSS, w) 3 K.
small k signifies greater deviation from the linear model. Notably, 1/K can be exponentially large, growing on the order of ( Therefore, it is crucial to ensure that our regret bound does not depend on 1/k.
In terms of storage, the estimator avoids retaining all his- torical data, as H2, and H, can be updated incrementally, requiring only (dd)) storage.
4. Main Results
Our first main contribution is the development of an im- proved online confidence bound for MNL bandits, which depends on the update condition parameter a. The proof is deferred to Appendix C.
4.1. Sharper Online Confidence Bound for MNL Model
Instead of performing Maximum Likelihood Estimation
(MLE) as done in previous studies (Chen et al., 2020; Oh
4

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Theorem 4.2 (Improved online confidence bound). Let 8 (0, 1] and = [T] denote the set of update rounds. For all tE T, we assume the following update conditions hold:
respect to the -norm (rather than the f--norm, as shown in Tran-Dinh et al. (2015)), which may be of independent in- terest. This result enables to set 1) = (Proposition C.5), making it independent of B and K.
|=/[(w- - [[[[-=)]]= & a, ViE St.
sup wEW,
2) Intermediary term. Inspired by Zhang & Sugiyama (2024); Lee & Oh (2024), we introduce an intermediary parameter:
where We is a compact convex set, and a > O. We see
= (1+ + 3//aa)/2 and X = max 144nd, 2}.
Then, under Assumption 3. with probability at least 6, we have:
:- o, (Ew-p, [o=, ((x2)))
w) ())esss)))
where or, is the softmax function, o is its pseudo-inverse. and P. is multivariate normal distribution with mean w' and covariance clt,1 for some c > 0. Then, we decom- pose the sum of loss gaps appearing in the first term of Equation (4) as follows:
[w - w" =
(ay -0
(log(t//) + BVA).
Remark 4.3 (Condition of Theorem 4.2). Note that the con- dition in Theorem 4.2 is easy to satisfy and has already been addressed in prior works (Faury et al., 2022; Zhang & Sugiyama, 2024; Lee & Oh, 2024). Specifically, if the parameter is updated at every round (i.e., T = [T]) over the entire parameter space (i.c., W, = W). as is common in previous works (Faury et al., 2022; Zhang & Sugiyama, 2024: Lee Oh, 2024), it follows directly that B.
Σ (fa(w") - -f((W++)) 8ETr+1
Σ (ca(w")- - lo(2))
+ Σ (Lo(2x) ls (ww+))))
SET1+1
se Te+1
(a)
(b)
Discussion of Theorem 4.2. When the parameter is updated at every round (so a = 2B) and À is set to À = O(Bd + B²), we obtain a completely K-free confidence bound of O(V/llogt + B + B²). Compared to the re- cently established confidence bound O (BBv d log / log K + B3/2 log K) (Lee& & Oh, 2024), our bound is tighter by a factor of Vlog log K in the leading term.
3) Tighter bound for term (a) via Ville's inequality. In Zhang & Sugiyama (2024); Lee & Oh (2024), term (a) is bounded using a Bernstein-type inequality. However, the intermediary parameter cannot be used directly, as it is generally unbounded (Foster et al., 2018). To address this, they employ a smoothed version of the parameter, but this leads to a bound of Olog (log 2)² for term (a), resulting in a significantly looser confidence bound.
More importantly, and perhaps more interestingly, if we can construct W/ such that a remains small (or constant) and updates occur only when this condition is met, we achieve a confidence bound of dogl + BVd). For sufficiently large t, i.e., t > O(e ). this further simplifies to (V representing a significant improvement over the previous bound O(Bv d log log K) (Lee & Oh, 2024),
In contrast, we apply Ville's 's inequality (Ville, 1939) without resorting to smoothing. To do so, we first show that the following quantity forms supermartingale:
Σ ((w'))((((3))) SET
A = exp
with no dependence B or K.
Proof sketch of Theorem 4.2. We provide proof sketch and highlight the technical novelties of Theorem 4.2.
Then, by Ville's inequality, with probability at least 1 - 8 (set â x f), we can bound term (a) as follows:
Following the previous works (Zhang& & Sugiyama, 2024; Lee & Oh, 2024), we first bound the estimation error be- tween W and w' as follows:
Σ (c(w") - (Z.)) log ~ logt, TE
(5)
which is an improvement by a factor of Olog K log t) com- pared to Olog K (log ()²) (Zhang & Sugiyama, 2024; Lee
[We1 - w w Hog1 S1 17 Σ (la(w))-4 la (
seT
& Oh, 2024).
(4)
On the other hand, we can bound term (b) by applying LemmaF.3 of Lee et al. (2024a) (or Lemmal4 of Zhang & Sugiyama (2024)):
where Te+1 T is the set of update rounds prior to t + 1.
1) B, K-independent step size n) In Zhang & Sugiyama (2024); Lee & Oh (2024), 17 is set as 17 = log K + B. based on Lemma 4 from Jézéquel et al. (2021). To eliminate the dependency on B and log K, we establish Proposition B.3, which shows that the MNL. loss 3,
Σ (L.(Z.) - Ee (W & ad logt. TE
(6)
with
Combining (4), (5), and (6), we complete the proof.
5

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Algorithm 1 OFU-MNL++
Input: failure level 6, confidence radii Br 6) and (e(d). 2: Initialize: WF
222 3v2B, À 144d, W, H1 AIa, H IiI, W1, wi W, 7 1, 17th A :- max (12 21)" B, 14,444) d, 2). T2 = 6v (G)
3: for round . I do
4: Observe feature set X₂ { and rewards (Fti);=1-
5: if maxzexx, || (18)) 2 1/T then
Adaptive warm-up
6: Offer S, = (ir), where Tti, = argmax,ex, ||0| (#r))1 and observe yt- Update (W 11) RS-OMD (W,, 4, Hy" ;7") by Algorithm 2. Calculate ( { w e F | w wirlleg (t+1(0))
7:
8:
9:
Update Hz+1 + H, and Wi+1 - Wt
10:
else
t Planning & Learning
11:
Offer St = argmaax (S) and observe yc-
12:
Update (W,+1, H++1) < RS- RS-OMD(WW) (W) (6), le He, Wt. 11) by Algorithm 2. Update H8 Ht"", W w.". and W (6) (o).
14:
end if
15:
end for
Algorithm 2 RS-OMD Restricted Space OMD
feature X, the quantity |=] is greater than equal to the threshold 1/T? (as specified in Equation (7)), we do not update our current estimate Wr- Instead, we update a separate warm-up parameter w to ensure that the condition in (7) is more likely to hold in the future.
1: Input: convex set W, L, Hi, Wt.
2: Update H, - H, + 17 2, (w.).
3: Calculate Wi+1 by Equation (2).
4: Update Hz+1* < H, + (we(1)))).
5:
Return: Wi+1, H411.
In such cases, we offer only the single item that maximizes | (Line 6). Subsequently, update the warm-up parameter w by invoking Restricted Space Online Mirror Descent (RS-OMD, Algorithm 2) subroutine (Line 7), Then, we construct the following parameter set (Line 8):
4.2. Online Update with Adaptive Warm-Up
In this subsection, we introduce OFU-MNL++ (Algorithm I), which employs a novel two-phase online update approach leveraging the improved confidence bound from Theo- rem 4.2 to achieve the tightest regret bound in MNL bandits. Note that the feature set Xr can be arbitrarily given at each round t, without imposing any distributional assumptions on the exogenous contexts.
W = Rd |ww w wiillly, & =6+1(0))
where (4+1(0) (B B Vd B²). This ellipsoid is then used in the RS-OMD procedure during the Planning & Learning rounds (Line 11- 13). Note that, since the search space is the entire parameter space W, we can set
Intuition. Theorem 4.2 indicates that a constant, a confidence bound of (V can be obtained for suf- ficiently large t. Our primary objective is to design the search space W, to ensure that remains constant in most rounds. To achieve this, we enforce the condition by reject- ing, on-the-fly, any X; that might violate the constancy of a. Specifically, it is sufficient to verify the following condition:
for the condition of Theorem 4.2 to obtain the warm-up confidence bound Ç++1 (5). The quantities H, and w, remain unchanged during the warm-up rounds (Line 9).
Parameter update within restricted space (f" When the condition in Equation (7) does not hold, the parame- ter w; is updated by searching only within W using RS-OMD as a subroutine (Line 12). In this scenario, a can be as a constant (with high probability), leading a con- fidence bound of OVVllgt + Bv/d) (by Theorem 4.2).
max ||0|| xEN,
(HT) 1/T2.
where == + EpETw Pe " +1) is the warm-up version of Hr, i.e., the regularized sum of Hes- sians corresponding to all assortments played during the adaptive warm-up rounds T Here, is a carefully chosen threshold and x > 0 regularization parameter.
Corollary 4.4 (Informal, B-improved & K-free line confidence bound). Let 8 e [0,1] and 3,(5) O Vd log(t/)) + BVd). Suppose w e (Tr for all > Define the following confidence set as follows:
C,(6) {w E Rdd |w wella, & BBc(6)).
Online adaptive warm-up. round f,, given Xr, for any
6

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Then, we have Pr Pr[Vi > 1, w' e C(())] > 1-6.
Discussion of Theorem 4.5. For sufficiently large, i.e., T a O + + B dl), OFU-MNL++ achieves a regret of O dlogTT E / is the first variance-dependent and poly(B), K- K-free regret bound in contextual MNL bandits. Compared to the recent minimax optimal result of O (B3/2d (llo T)3/2//7 by Lee & Oh (2024), our method improves the regret by a factor of O (B log K <logT)) Moreover, the (vVT) term in Lee & Oh (2024) replaced in our result by OVV22
Efficient assortment selection. Given the confidence set in Corollary 4.4, we calculate the optimistic utility UCB; as:
To the best of our knowledge, this
UCB := Ny W. + |e(0)||mulll;) H, Vi [N].
If the true parameter w lies within the confidence set (6), the value UCB,, serves as an upper bound for =y. w*. w.."". Using UCB we define the optimistic expected revenue for an assortment S as:
Since of < always holds, this repre- sents a strict improvement over VT. (8)
R,(S): = Lies exp(UB..))) I+ jes
Remark 4.6 (Computational cost of OFU-MNL++). The pro- posed algorithm, OFU-MNL++, maintains constant compu- tational cost per round of O(Kd + poly(N)), which is entirely independent of t. For parameter updates, we utilize the linearized loss, inspired by Zhang & Sugiyama (2024), and work within ellipsoidal search spaces (W and (6) in both phases. As result, the update process incurs only cost of O [ [d'). Moreover, the assortment optimization problem be solved in (ppoly(N)) (Davis et al., 2014). Remark 4.7 (Lower bound and optimality). For the worst- case regret, we achieve ((d'T) (since d; = (1)), which matches the minimax lower bound of (dv/T) established by Lee & Oh (2024). When the rewards are uniform, i.e., Tri 1, we obtain (dd/T/K), as of = (o),) w") = 1/K. This result also matches the uniform reward minimax lower bound of ((d/T/KK (Lee & Oh, 2024).
where Tus E [0, We then offer the assortment St that maximizes (S). i.e. St = srgmax (S) (Line 11). The quantities H!!", w.", and W! remain unchanged dur- ing the planning & learning rounds (Line 13). Note that the optimization problem in (8) can be efficiently solved in polynomial time. (ppoy(NN)), independent of t (Rus- mevichientong et al., 2010; Davis et al., 2014).
Variance-dependent optimal regret. We establish a variance-dependent optimal regret bound through a novel regret decomposition. Specifically, we show that the re- gret is bounded by the sum of covariances between ru and ||atsl H given S,. Thus, with some slight notational abuse (as the expressions do not strictly denote random variables), the regret can be bounded as follows:
Comparison to related works. While our approach shares some similarities with previous works (Faury et al., 2022; Sawarni et al., 2024) that also use a similar warm-up phase, there are significant differences.
Regr( (w' (T)
Σ
Cov, (resll(eeoler))))
$ (T(10)
Σ 1TT
Velru)
Σ #TT
Ve(loulH.))
Remark 4.8 (Comparison to Faury et al. (2022)). Faury et al. (2022) incurs (B) dependence in the leading term, whereas our method avoids this entirely by exploiting the self-concordant structure of the MNL loss (see Appendix B). A Additionally, their use of MLE in the adaptive warm-up phase results in a per-round computation cost that grows lin- early with the number of warm-up rounds. In contrast, our method uses an online update rule, resulting in significantly better computational efficiency. Finally, their approach re- quires prior knowledge of k, which is often unknown or hard to estimate in practice.
where -) and Vr(-) is the covariance and variance, respectively, given Sy. For simplicity, rewrite (r(ra) as
of:= (i- (ru- St Irx,)) (9)
where 1:0 O. By applying the elliptical potential lemma (Lemma D.7) to the sum of the variances of [ati и, 1, we derive variance-dependent regret bound. The complete proof is provided in Appendix D.
Remark 4.9 (Comparison to Sawarni et al. (2024)). Unlike Sawarni et al. (2024), which requires prior knowledge of k-an impractical assumption in real-world scenarios-our approach does not rely on knowing i in advance. Addi- tionally, their method fully updates parameters using MLE rather than an online update. As a result, the per-round computation cost of their algorithm scales linearly with i, while ours remains constant.
Theorem 4.5. Let 8 (0, 1), and assume that Assump- tion 3.1 holds. Then, with probability at least 8, the regret of OFU-MNL++ (Algorithm 1) satisfies
T Σ
Reg, (w")& (dlogT T + /dvlog T
of
+ Bd (logT)² + Bd Bdd
1
Discussion on instance-dependent regret. As a special
K

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
UCB-MNL
TS-MNL
OFU MNL+
+FU_MML++ (ours)
OFU-MANL (ours)
B=2.0, N=50, K=5, d=2
B=3.0, 5=50, K=5, d=2
B=4.0, 5=50, K=5, d=2
B=5.0, N=50, K=5, d=2
1000
Cumulative Regret
600
400
200
0
1000
1500
2000
2500
500
1000
1500
2500
1500
2000
3000
500
1000
2000
2500
Round
Round (3)
Round
Round
Figure 1: Cumulative regret for varying the norm-boundedness of the unknown parameter B.
UCB-MNL
TS-MNL
(ours)
OFU-M'NL (ours)
B=2.0, N=50, K=5, d=2
B=3.0, N=50, K=5, d=2
6=4.0, N=50, K=5, d=2
8=5.0, N=50, K=5, d=2
Time (Seconas)
0.4
0.2
1000
2000
Figure 2: Runtime per round for varying the norm-boundedness of the unknown parameter B.
case, if the rewards are uniform (i.e., Fts 1), can establish an instance-dependent regret bound.
probability at least 1 have:
Iw"" - Wellg, =0 (Vdlog(Bt)
Proposition 4.10. Under the same conditions as Theo- rem 4.5 and assuming uniform rewards, for sufficiently large T, OFU-MNL++ achieves a regret of Ö dy DT Et=nkt) where Kq Lies Pe w (O w*).
Note that 9, is used solely for analytical purposes. The algorithm and proofs are provided in Appendix F.
Theorem 4.12. Let E (0, 1]. Then, under Assumption 3.1, with probability at least (Algorithm F.1) is bounded as follows:
6, the regret of OFU-M'NL
This result improves upon the previous instance-dependent regret Ô e d - kū (Proposition Lee & Oh (2024)), by a factor of eB_ The proof and further discussions are provided Appendix
Regr(w") dllog BT)
Σ
of
dl (log (log(BB))² 2 k
Discussion of Theorem 4.12. Theorem 4.12 shows that OFU-M enjoys completely poly (B)-free regret for any T. indicating that its regret is tighter than that of OFU-XNL++ by factor of O(poly(B) B)) in the non-leading term. How- ever, its asymptotic regret still depends on log B, whereas the asymptotic regret of OFU-MNL++ remains entirely inde- pendent of B. Additionally, the per-round computational cost of OFU-M increases linearly with t, while that of OFU-MNL-+ remains constant.
4.3. MLE-Based Approach
Inspired by Lee et al. (2024b), who proposed poly(B)- free confidence bound using the MLE for generalized linear models (GLM) (but for MNL models), we introduce an MLFE-based algorithm that achieves poly K K-free regret. To this end, first define the MLE estimator w; follows:
W. = argmin (w(w, where L((w)= WEW
Σ e, (w))
5. Numerical Experiments
Lemma 4.11 (Informal, Improved MLE confidence bound). Let G, = (1 v) L, + v(w"- wu + sBs Ig. Then, for any if Assumption 3.1 holds, then with
We empirically evaluate the performance of our algo- rithms, OFU-MNL++ and OFU-M NL, by measuring cumu- lative regret over T 3000 rounds. The algorithms are

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
tested 20 independent instances, and we report the aver- age performance along with shaded area representing two standard deviations. In each instance, the true underlying parameter w" is uniformly sampled from the d-dimensional ball [Bd B) of radius B, and the context features zii are drawn from a BB (1). The rewards are sampled from a uni- form distribution in each round, i.e., Tri (n, 1).
munications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. RS-2025- 02263754), and by AI-Bio Research Grant through Seoul National University.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none which we feel must be specifically highlighted here.
The baselines are the practical and state-of-the-ar al- gorithms: the UCB-based algorithm, UCB-MNLL (Oh & Iyengar, 2019), the Thompson Sampling-based algorithm, TS-MNL (Oh & Iyengar, 2019), and the constant-time algo- rithm, OFU-MNL+ (Lee & Oh, 2024). Figure shows that both of our algorithms significantly outperform the baseline algorithms. Although OFU-XNL++ incurs high regret in the early rounds due the adaptive warm-up phase (with the number of such rounds depending on B), its regret stabilizes after a certain point, exhibiting the lowest slope. Therefore, we believe that OFU-MNL++ achieves the best asymptotic performance among all algorithms. This aligns with our theoretical results, which show that the asymptotic regret of OFU-MNL++, Og T TT), is entirely independent of B (even in logarithmic terms), whereas other algorithms ex- hibit B-dependence. Additionally, OFU-X demonstrates the most robust performance, maintaining its superiority even as B increases, particularly in the early rounds. For more details and additional results, refer to Appendix G.
References
Abeille, M., Faury, I.,, and Calauzènes, C. Instance- wise minimax-optimal algorithms for logistic bandits. In Inter- national Conference on Artificial Intelligence and Statis- tics, pp. 3691-3699 PMLR, 2021.
Agrawal, P., Tulabandhula, T., and Avadhanula, V. A tractable online learning algorithm for the multinomial logit contextual bandit. European Journal of Operational Research, 310(2):737-750, 2023.
Agrawal, S., Avadhanula, V., Goyal, V., and Zeevi, A. In Conference
Thompson sampling for the on learning theory, pp. 76-78. PMLR, 2017.
Agrawal, S., Avadhanula, V., Goyal, V., and Zeevi, A. Mnl- bandit: A dynamic learning approach to assortment selec- tion. Operations Research, (5:5311443-11 1485, 2019.
Furthermore, Figure 2 shows that the online update meth- ods (OFU-MNL+ and OFU-NNL++) maintain constant run- time per round, while the others exhibit a linear increase with & due to their use of MLEE-based parameter estima- tion. Among them, our MLE-based approach, OFL,M"NL, is the most computationally expensive, as it solves convex optimization problem to compute the optimistic parame- ter unlike the others, which rely on closed-form UCBs (see Line 6 in Algorithm F.I).
Campolongo. N. and Orabona, Temporal variability in implicit online learning. Advances in neural information processing systems, 33:12377- 2020.
Chen, X., Wang. Y., and Zhou, Y. Dynamic assortment optimization with changing contextual information. The Journal of Machine Learning Research, 21(1):8918 118)81991- 2020.
6. Conclusion
Cho, W., Hwang, T., Lee, J., and Oh, M.-h. Random- ized exploration for reinforcement learning with multi- nomial logistic function approximation. arXiv preprint arXiv:2405.22 20165, 2024.
In this work, we construct the sharper online confidence bound for MNL models, with improvements in terms of log K and (B) dependencies. Leveraging this result, we propose a constant-ting time algorithm, OFU-MNL++, that achieves B, K-free regret in an asymptotic sense. Addi- tionally, we introduce MLE-based algorithm, OFU-M"NL, which ensures poly(B) K-free regret every round.
Davis, J. M., Gallego, G., and Topaloglu, H. Assortment optimization under variants of the nested logit model. Operations Research, 62(2))250-273, 2014.
Dong, S., Ma. T., and Van Roy, B. On the performance of thompson sampling on logistic bandits. In Conference on Learning Theory, pp. 1160. PMLR, 2019.
Acknowledgments
We sincerely thank Yu-Jie Zhang and Jungyhun Lee for their valuable discussions. This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2022-NR071 1853 and RS RSS-0023000222663) by Institute of Information & com-
Faury, L., Abeille, M., Calauzènes, C., and Fercoq, O. Im- proved optimistic algorithms for logistic bandits. In In- ternational Conference on Machine Learning, pp. 3052- 3060. PMLR, 2020

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Faury, L., Abeille, M., Jun, K.-S., and Calauzênes, C. Jointl efficient and optimal algorithms for logistic bandits. In International Conference Artificial Intelligence and Statistics, pp. 546-580 PMLR, 2022.
Oh, M.-h. and Iyengar, G. Multinomial logit contextual bandits: Provable optimality and practicality. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9205-990990 (005-921,,40 2021.
Foster, D. J., Kale, S., Luo, H., Mohri, M., and Sridharan, K. Logistic regression: The importance of being improper. In Conference on learning theory, pp. 167-208. PMLR, 2018.
Ou, M., Li, N., Zhu, S., and Jin, R. Multinomial logit ban- dit with linear utility functions. In Proceedings of the Twenty-Sevent International Joint Conference on Artifi- cial Intelligence, IJCAI-18, pp. 2602-2608 International Joint Conferences on Artificial Intelligence Organization, 2018.
Hazan, E. et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157- 325, 2016
Park, J., Kwon, J., and Lee, D. Infinite-horizon reinforce- ment learning with multinomial logistic function approxi- mation. arXiv preprint arXiv:2406. 13633, 2024.
Hwang, T. and Oh, M.-h. Model- based reinforcement learn ing with multinomial logistic function approximation. arXiv preprint ar arXiv:2212.135400 2022.
Perivier, N. and Goyal, V. Dynamic pricing and assortment under contextual mnl demand. Advances in Neural Information Processing Systems, 35:3461-3474, 2022.
Jézéquel, R., Gaillard, P., and Rudi, A. Mixability made efficient: Fast online multiclass logistic regression. Ad- vances in Neural Information Processing Systems, 34: 23692-23702, 2021.
Rusmevichientong. P., Shen, Z.-J. M., and Shmoys, D. B.
Dynamic assortment optimization with multinomial logit choice model and capacity constraint, Operations reseurch, 58(6): 666-1680, 2010.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. Provably efficient reinforcement learning with linear function ap- proximation. In Conference on Learning Theory, pp- 2137-2143. PMLR, 2020.
Sauré, D. and Zeevi, Optimal dynamic assortment plan- ning with demand learning. Manufacturing Service Operations Management, 15(3):387 2013.
Lee, J. and Oh, M.-h. Nearly minimax optimal regret for multinomial logistic bandit. In The Tiihtt-eighth Annual Conference on Neural Information Processing Systems, 2024.
Sawarni, A., Das, N., Barman, S., and Sinha, G. Gen- eralized linear bandits with limited adaptivity. In The Thirtyy-ighhtl Annual Conference on Neural Information Processing Systems, 2024. URL https://openreviev. net/forum? fifformm?id-FFPPBOuT444
Lee, J. and Oh, M.-h. Combinatorial reinforcement learning with preference feedback. arXiv preprint arXiv:2502.10158, 2025.
Tran-Dinh, Li, Y.-.., and Cevher, Composite convex minimization involving self-concordant-likc cost func- tions. In Modelling, Computation and Optimization in Information Systems and Management Sciences: Proceed- ings of the 3rd International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences-MCO 2015-Part 1, pp. 155- 168. Springer, 2015.
Lee, J., Yun, S.-Y., and Jun, K.-S. Improved regret bounds of (multinomial) logistic bandits via regret-to-confidencc- set conversion. In International Conference on Artificial Intelligence and Statistics, pp. 4474-4482. PMLR, 2024a.
Lee, J., Yun, S.-Y., and Jun, K.-S. A unified confidence sequence for generalized linear models, with applications to bandits. arXiv preprint 2rX1v:2407.13977, 2024b.
Ville, J. Étude critique de la notion de collectif, volume 3. Southier-Villany Paris, 1939.
Li, L.-F., Zhang, Y.J.,, Zhao, P., and Zhou, Z.-H. Provably efficient reinforcement learning with multi- nomial logit function approximation. arXiv preprint 17X10 2024.
Zhang, Y.-. and Sugiyama, M. Online (multinomial) logis- tic bandit: Improved regret and constant computation cost. Advances in Neural Information Processing Systems, 36, 2024.
McFadden, D. Modelling the choice of residential location. 1977.
Oh, M.-h. and Iyengar, G. Thompson sampling for multi- nomial logit contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
10

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Appendix
A. Notation
Let be the total number of rounds, with e [T] representing the current round. We denote as the total number of items, K' the maximum size of assortments, the dimension of feature vectors, and B as the upper bound on the norm the unknown parameter. For ease of reference, we provide Table A.1.
Table A.1: Symbols
Fti
feature vector for item given round
Tti
reward for item given at round assortment chosen by an algorithm at round t
S:
Kr
: -S size of chosen assortment at round
outside option
Yei
choice response for each item i E S, {0) round t
(. w")
Eies Sr w "res expected revenue of the assortment S at round t
(<(w)
= Eies, Uti log
exp(xT;w) jes, exp(a))
loss function at round
(z()
= -- -Ees, log
exp(au)
loss function at round t, 2ts = w.w
1+ Hyys exp(21))
T
set of adaptive warm-up rounds
W.
online parameter estimate at round
w/
projection of w, onto the current search space W; adaptive warm-up parameter estimate round
W?
= 1, step-size parameter for w.
17
= + 3 step-size parameter for w
= 144d, regularization parameter
n
= max "n B, 144n"" d, 2} regularization parameter for adaptive warm-up
(24(w)
ExEs, Pr( St. w) x Ess, Ejes, Pe(i]S,, w)p:(jlS, w)xa2l
Hi
AL4 E - I]:T" (Wot1)
Hr
H. + 1/ (V
Hi(w")
AL E (eea(w")
H.
= XLI + E (w.+1)
B((0)
= (log(1/5) + Bvd confidence radius for w, at round
(()
O BV d log(t/)) 33/2 + B²) confidence radius for w at round
T
6v (C), threshold for determining whether implement adaptive warm-up
UCB#
T. + (0) salll I optimistic utility of item at round
Re(S)
Lnnr exp(UUC...))))) optimistic expected revenue of assortment S at round t
I+E eXp(UCB.,)
of
= E (rw -
variance of rewards given S, at round
For notational simplicity, we express the loss function in two different forms throughout the proof, using them interchangeably

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
needed:
exp(2 w) 1+2iess exppzz,, (.)
((w)) Σ ieS.
Yta log pe (ilSs, w)
Σ
Yti log
VES:
exp(z(s)
(z(z)) Σ Yes log ieS.
1+ Ljes, exp(2(s)
wwl(w) Σ (pr w)
yti) vis.
iS
Velezz)) = oz(2;) - Yr.
(wl(w) Σ Pi()S w) Σ
Σ pr(ils, w)p, w)
iES.
iES, JES,
(il(z))) = diag(o (z))) (z)
(A.1)
where zu Z.[,, (Eu)ess, E |l and y: (yu)es BlS,, Hence, it is clear that ((w) (((z)).
B. Cell-Concordant Properties of MNL Function
In this section, we present several key properties of self-concordant-lik functions that are essential for proving the main theorems in this paper.
For simplicity, will work with the MNL loss in the form of rather than & throughout this section. However, it is important to note that the properties introduced in this section also apply to l. Whenever these properties used in the proofs of other lemmas or theorems, we will explicitly demonstrate their applicability to f.
We begin by revisiting the definition of self-concordant-like functions.
Definition B. (Seff-concordant-lik function, Tran-Dinh et al. 2015). convex function f E C RRK - M-self- concordant-like function with constant M
(0"(s) < M b)
for IR and M where p(s) = f(a + sb) for any a, b R
To derive tighter confidence bound in Theorem 4.2 and tighter regret bound in Theorem 4.5, redefine the concept of self-concordant-like functions specifically for the MNL. loss function f.
Definition B.2 nnom eelf-concordant-like MNL loss). The MNL loss function f(z) R.K IR is M-self-conccrraat- like function with constant M if:
(s)) < M o)b)==*((ss)
for E IR and M > O, where d(s) = f(a + sb) for any a, b beRe K
Note that because |x|| & |||| for any vector w R.K the new definition of self-concordant-lik function (Definition B.2),
which is specifically designed for the MNL loss function, is tighter than the original definition (Definition B.1).
Using this new definition, we show that the MNL loss defined in (1) is 3v sellffcoocordaat--iee function.
Proposition B.3 (Constant self concordat-kd MNL loss). For any [T], the multinomial logistic loss E, defined in Equation (A.1), 3 2-see/f-coocorrummtllle function under Definition B.2.
Proof of Proposition B.3. Recall that the loss &e is defined as:
(z) = Σ
Jes + log
1+
Σ T1
ies;
ieS,
linear
:f (z)
12

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Since & consists of the linear term and f(z) RR55 - I,, and the third derivatives of the linear term are zero, it suffices show that [() is 3v s-seef-conncrrran-lii function.
Fix any e [T]. For simplicity, let K = |Sal. We define:
K 1+
K
((s) == f(a sb) = log
Σ i=1
cartobe log Σ
eartabe
where [ai. , axl TT RK and b [b1.... .......,]]] TT RRK and an bo O. Then, by simple calculus, have
0"(s) Eiey(be Peartshi
0,
E//o eaitsbb) 2
and
Eiss(h: (4. - bb))
Ea
Ex- + +be by- 2bb) eert tob
<
>k= (b; + bj -2xx) (
(s)
(s)s).
SK 2i cartsbb)
Σ car
(B.1)
Note that for all i,j.k O,..., K,
16: + bj 22bll & v6 b3 +b2 < 3v22 max |6:].
-.....KK
Hence, we obtain
K
Σ (b: bj a
$
br by 2hxl taut & x322
[b;] Σ
eartsbi
(B.2)
(=0....KK
0
0
1=0
Plugging in (B.2) into (B.1), we derive that
(²(s) & 3 max [b:10(s)) b/l t=
By Definition B.2, we conclude that the MNL loss is 3/--sse---onccordan--ik
definition (Definition B.2), we establish several fundamental properties of the self-concordant-like MNL loss function. The following proposition is analogous to Theorem 3 of Tran-Dinh et al. (2015), However, Proposition B.4 provides a tighter result specifically tailored to the MNL loss function (though it may be extendable to other functions).
Building
Proposition B.4. For convex function fe E C3 R R, we define [x) u. u] (D3 [ux) u). Then, if f is the MNL loss function, i.e., f = E, for any x, Un E RK we have:
| f(x)[u,, u2 uell < 3v u 12)
Proof of Proposition B.4. Let d(s) f(a + sb). Then, have
d"(s) V f(a sb)b b, ("(s)= D' D's((a+++bbbbbbbb bj.
By Definition B.2 and Proposition B.3, know that
1 (s) = b/ 3M (s).
By substituting 0, x, and b Uj we get
13 {(x()) un un] =lo < 3v2 11ll 3v2/|ui V ('f()uz un.
13

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
which can be equivalently expressed
3 ui V2 - = =
Therefore, for any u2 RK we have
[()) <32 un 1 Un (2)(x)u2
- [x) U2 uz] x 3v2 unlx u2 /2l
This concludes the proof.
Proposition B.5, variant of Theorem 4 in Tran-Dinh et al. (2015), establishes a key inequality for the Hessian of the MNL loss, which plays a crucial role in eliminating B-dependency.
Proposition B.5. For any t E [T], the Hessian of the multinomial logistic loss le R Sxl IR satisfies that, for any 21, Zg E R Sd,, we have:
3/22222 1V2121-2ll~?(((11) = (2(((z)) I -
Proof of Proposition B.5. We denote 2, + s(z2 z1) for notational convenience, where s E [0, We define the function (s)) == u (2,)) = | Note that (0) |u|| ()) and ab(1) = ||u])e, Then, by
Proposition B.4, we have
[V(()) D't,(2))22 - u, & 33/2/22 100--zia 21)00((8),
which can be equivalently written as follows:
d In (s)
< 33/2/22 21
ds
By integrating both sides over s e [0, 1], we conclude the proof.
Additionally, we introduce an improved version of Proposition Perivier & Goyal (2022), which serves as a useful tool for the subsequent proofs.
Proposition B.6. For any i E [T]. the Hessian of the multinomial logistic loss Sel R satisfies the following for any u, 21, Z2 RR l
u (fa-s) V) s(22 21)]ds)
1 u (z)((
2 3//22z2 2ı1lo
Proof of Proposition B.6. From Proposition B.5, we have
uT ( (1- ()-s) + s(22 2)))ds u T (et(zz)
(1 - s)e -V
c 0-3/2[ (00(22-=1)la 21) 1
u (2i((z)u
3/22 21)100
(3v2)((z2 21)1100)
u v26í(z))u
1
2 3/2[(2z zz 21)lla
where in the third incquality, we use the fact that 1 x (1+ 2+2
for all x > 0.
C. Proof of Theorem 4.2
In this section, we provide the proof of Theorem 4.2. We begin with the main proof of the theorem, followed by the proof of the technical lemma that is used within the main argument.
14

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
C.I. Main Proof of Theorem 4.2
Proof of Theorem 4.2. The overall proof structure is similar the analysis presented in Zhang & Sugiyama (2024); Lee & Oh (2024). However, explained in the main paper, several novel analytical techniques introduced to derive B- B-improved, K-frree confidence bound, including:
1. B, K indeepeend step size 17 by leveraging improved colf-concordant properties, 2. Ovylog log K) via a sharper analysis using Ville's inequality (Ville, 1939).
Throughout the proof of Theorem 4.2, we denote T = [T] as the set of total update rounds. For any round & E [T], we denote Ti | T as the set of update rounds that occur before t, i.e., Te = {s e T :8 t) = Tvtt, 1...., T). We assume following conditions hold:
Condition C.1 (Update condition). For all & e T, we assume that
sup weW,
[w - ww)l St.
where W, is compact convex set, and O.
We also denote the size of the assortment at round as K₁, i.c., K₁ = |St] & K. Lemma C.1. Suppose Condition C.I holds. The update rule for the parameter at round is defined as:
w = argmin |w wellee
wEW,
1
Wr+1 argmin (w) + |w wEW.
-
27
where ((())= (e(w)) + (w- W/: (l((w)) / (ill Lei 1 3x2 and À > 12 Then, under Assumption 3, for any update round T, we have
Wi+1 - w0 12e < 2m
Σ TET
(o(w") Σ (((Wot)) + 4B2x SET
Σ 8E TTT
- w/ -
(C.1)
2
The proof is deferred to Appendix C.2.1. Following the approach of Faury et al. (2022); Zhang & Sugiyama (2024); Lee Oh (2024), bound the first term in Equation (C.1), we introduce an intermediary parameter that is F.-measurable. Note that W is F. measuraaae
To do so, we first define the softmax function at round t, denoted as (z))) K: - Ke, as follows:
exp([z],)
[o.())];
Vi [K,].
(C.2)
K. k- exp([z]<)
where [-]x denotes i'th element of the input vector. The probability of choosing the outside option is denoted
[o.(z)]o
1 Σ (2)cc
Although [z)( is not part of the output vector of the softmax function (z), it is expressed in similar form to (C.2) for simplicity. Then, the MNI user choice model can be equivalently expressed as (i(iS w) [a, ([x]]w)jee ];
for all i [K,] and SO,S. w) = [ar ((xT) w))es:)l Furthermore, the loss function in (1) can also be expressed as
(()..y))
K. 1 [yra 1} log [..(,.)].
We also define pseudo-invers function of (.(.) as af K. - R RK, where [at( = log (g/(1 [[qll)) for any e {p E [0, 10: K: ||l| < 13. Then, we define the intermediary parameter as follows:
n a, (Ew~r, [a, ((x w))
(C.3)
15

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
where := N (w,:; cH, )) is multivariate normal distribution with mean w, and covariance cH Here, c is positive constant be specified later. Note that 2, is F--mesuurable unlike Ws+1 (Ws+1 is $ In general, 2, cannot be expressed as linear function of the features (Jss) Then, the first term in Equation (C.1) can be decomposed into two terms as follows:
Σ
(w(w))
Σ SET
(Z.) +
Σ SET+-1
(Z.)
Σ
(w(++))
RE BE7e+1
BET
(6)
First, we demonstrate that the term (a) is bounded by O (log b)) with high probability.
Lemma C.2. Let å E (0, 1]. Assume that Condition C.I holds. Define the intermediary parameter as Equation (C.3) with and c > 0. Then, for any t E T, with probability at least - 6, we have
Σ (s(w))
Σ
1 8' (,(2,) < log
SE T
SE TET++1
The proof is deferred to Appendix C.2.2. By setting } = O(t). we obtain the bound Eee la(w") -EE (z(z) Ologg). f). Compared to Lemma of Lee Oh (2024), which bound the similar term by O ((log 2 log K), Lemma C.2 improves the bound by a factor of log t log K. This improvement primarily due the use of a more refined analysis based on Ville's inequality (Ville, 1939), rather than the Bernstein-type inequality with smoothed intermediate term adopted in Zhang & Sugiyama (2024); Lee & Oh (2024). The latter approach incurs additional log (tt factor, which ultimately leads to the looser bound of O (logt)) f)² log K) for the term (a).
Now, we bound the term (b) by the following lemma:
Lemma C.3. Let and max 72ed]. Then, for all T, we have
Σ (3..)
Σ
l.(w (.(w++1)
& 2c SET
1
Σ
W willi, + Voodlog (1 + 2).
SET
SET
SETri1
The proof is deferred to Appendix C.2.3.
Finally, by combining Lemma C.I, Lemma C.2, and Lemma C.3, we derive that
Wi+1 w²
H
$ 2n log
Σ sETe+1
W w.l + Onon (t 2) + 4B2
1
Σ
W
-..l
2
sET
1
2n 1og z
4v 2 (t 2) 4
(Set 27)
O (a² dlog(t/0) B²A).
(n
1+3/2a
This implies that for all t Tttti. where t denote the first update round, we have
Wt w H. & O (av (log(t/)// + +BB()))))BBBB++.
(C.4)
For 1 E T, we know that [w;, w' H, & BVX. Thus, Equation (C.4) holds for all e This concludes the proof of Theorem 4.2.
C.2. Proofs of Lemmas for Theorem 4.2
C.2.1. PROOF OF LEMMA C.1
Proof of Lemma C.I. For any update round s To (an update round occurring before T), let (,(w) = (a(w)) +
(Vl((w)) w + w w Wal be second-order approximation of the original function e, (w() at the point w
16

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
where w wew, ||w walla, is the projection of w, onto Wg. Then, the update rule in (2) can be equivalently rewritten as follows:
1
w+1 argmin (Ve((Wa). w
w
w Ht
wEW.
2n
1
argmin (Ve((W)), w) weW,
w' (we) + |w w'll
2
27
1
argmin (w) + w w', li wEW.
27
Then, by applying Lemma C.4, get
(Vl((we+1) wo+1 - -ww>
$
2nj (Iw's - -w, - ||Wa+11 w'lli,, - -l|W++1 - w' 1t.)
1
(1 [/w, w ||W w || w' w(lHH.)
(C.5)
2n
where the last inequality holds due to the nonexpansive property of the projection mapping Pw., i.e., l| - w w'
[[w,, (w,) Pw, (w"), & - w' H.. On the other hand, by applying Lemma C.5, which based on our improved seff-concordant-like property (Proposition B.4), obtain:
1
(w(w++1) (s(w)) & (Vla(wss)) Ws41 w*)
| - (wo+)))
(C.6)
2 3/
2a
Let = 1+ 3v2 2 a. Then, by combining (C.5) and (C.6), we obtain that
(((w+1)) lo(w") & (Ve((wst)) Vl,(w, Ws+1 - -w")
1 (|w.-w'|lz
(Iw,-
w 11.. ||W5+1 w w'1...... |||w++1 w'llzs) -w.11,)
(C.7)
2rj
In the inequality above, the first term the right-hand side can be further bounded as:
(Vl,(we+1) vi,(---))) Wa-1 w")
<V - VlG(w') - V2Lo(W') - -W.), Wot1 - -w>
= <D'Ls((s)) WW.w1 w'](ws+1 wW),, Ws+1 w*)
(Taylor expansion)
- - Wo41 W/. Ws+1 w'J.
(C.8)
where in the second equality, we use the Taylor expansion by introducing w., which is convex combination of Wa+1 and w". Recall that by the definition of loss (see Equation (A.1)), the loss fa(w.) can be expressed as Eo(Z,), where (I (.+1) 1ies, z (x]] wiees, and z" = (I. wes, Then, by
7, = [o] w.)ies, E IR S. Moreover, let 2,+1
simple calculus, we get
D w W w'] 13L,(Ze)) [Ze)] z", 1,+1 1zy, Zo+1 z 2² 20 [2.41 - 2/11 2/122"8_1E0
< 3v <3v2 20+1 23/211
(Proposition B.4)
< 2v max Tx (W w w*)]l 211 zEi.
< 33/2allz44 1 22
-3/2all w-- w'llFze, (w.)
(Definition of (C.9)
3 W--1 w'll3.
17

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
where the last inequality holds because
(w,, = Σ
Pr(isS,: W.) - Σ Σ 1eS, JES,
(ils,,,, w.)p, Wa
i
Σ
Ps (ilS,, Wa)arsir Σ
Pa(iSSe, Wa)a
Σ IES.
pa w.)
iES,
iES.
Σ pa W. = La.
(F20s & 1, Assumption 3.1)
i
Hence, by plugging (C.8) and (C.9) into (C.7), and summing over E Te+1, we obtain
Σ (o(w++))-
Σ (s(w")
SET
SETe+1
< 3/2a
Σ
|ss1 - w'll2 + 2n sETi+
Σ
(Iw, - w'Ili, (ww--"Ilk, - ||W5+1 w''l -
|| -w'l??,
eETx+1
3/22
Ws+1
w'll2
|| w'llir, -| w
|ws+1 w'll
2n
SET++1
SET
where in the equality, 4 E T represents the first update round. Additionally, we use the fact that the parameter wa, and the matrices H2 and H₃ remain unchanged during non-update rounds. By rearranging the terms and using the fact that I[W, - w & Al[w,, w'12 & 4B²X, we get
Wi+1 - w'll w'llit
(s(w") Σ (W(W+)))
+ +BB
|w-1
w'lli, +6v2no
Σ 8ET1+1
|| -w11
sETe+1
sEt141
sET
& 2m
Σ (w())) Σ
(o(wo)1)
+ +4B²>
1
Σ
W
w''
2
sET
SET
sET2+1
where the last inequality holds because, by setting À b 12v/naa we have 6y 2njo We+1 w'll3 < f/ - w'l
C.2.2. PROOF OF LEMMA C.2
Proof of Lemma C.2. Recall the definition of 2, in Equation (C.3). Then, by definition of the pseudo-inverse function of, we have of (2,) Ew--p, [or ((x1)) w) )] Let is E Sy o {0} denote the (random) index such that Yos, 1; in other words, i is the item selected in round t. Then, we express exp (fe(z)) follows:
exp (-L((Z)) = exp (log (Io, (ž.)).)) = [o, (Z.)l., = BEw-P. lor ((IT)w))Es)))
(C.10)
Similarly, denoting z = (x"] w') )ess, E RR we can also express exp (- (c((")) as follows:
jes,
exp (-e(()))")) = exp (-Ex(2;) = exp (log (Io, (z) ),,)) = [a, (z)))..
(C.11)
Here, note that [ox (zi)le, = Pe(ielSi, w*).
Now, we define
A, exp
Σ la(w") Σ Ec(Em))
seT
seT
18

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
For completeness, define Ag filtration F, a (1.... St). If t is an update round, we have:
First, show that (At)ss is nonnegative supermartingale with respect the
Ew-Pi Pi for ((x)) l
TEE exp (-),(
exp (-b((2))
A,
A exp(-l((w*)) A
NLET:: exp (-(s(w'))
For (2;),
(Eqn. (C. and (C.11))
Note that the term Ew fou w)sssll
/ lo,, (zi)l,, is measurabee Further, we get
Ew P3 For ((xTT jes))]
E [A FJJ A E
is F,
(ox (zi)li,
Bown (or ((ss))
A
Σ (E)
St w*)
(o,)),
E Ew [or, (IzT) w) w)
A
Σ
For (2;)
-Pr(i]Se, w*))
[o: (z;),,
(ES
-
Σ (E)
E Ew- P3 [or ((x))) w) w) = Ac-1.
Moreover, if is not an update round, we simply set A, = At-1. follows that (At)ss indeed a martingale, and hence also supermartingale. Since (At)es a nonnegative supermartingale, we can apply Ville's inequality (Ville, 1939) to obtain:
P
Σ (o(w") Σ (2(2)) 2 log
=
A 3 8
NET
seT
sup A 3 ))
< P
[[A]]
(Ville's inequality)
8,
(Ao = 1)
which concludes the proof.
C.2.3. PROOF OF LEMMA C.3
Proof of Lemma C.3. The proof closely follows Lemma F.3 of Lee & Oh (2024) (or Lemma 14 of Zhang & Sugiyama (2024)), with the only difference being that the summation is taken over the subset of rounds T++1 S [t], rather than the full set of rounds [t]. For completeness, we include the full proof below.
To begin with, the proof builds on an observation from Proposition of Foster et (2018), which states that é, serves as an aggregation forecaster for the logistic function. Accordingly, for any T the following holds:
E. (ā..) & -log (Fw-rr [e=R((m)]] log ( Zg JRd
e (wlo(w)dw)
(C.12)
where (ww : (o(w) + 2c w - will?r, and Zg := Sge e fllw-walls.d dw.
We define the the quadratic approximation of (w) as follows:
1 w w
L.(w)= (w(w+))) + <VL wo+1)+
2c
19

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Then, by Lemma C.6 and considering the fact that lg (3//=sel--connordant--- function by Proposition B.3, get
(w) & (w)) 18/w-w. w.t || Wosillleee
(w (wo+1)' (w.+3))
(C.13)
Furthermore, we define the function fs+1: W - IR as
(- 1 lIw w 11 1 w. Wo+zllvae,
fs+1(w)= exp
2c
Then, we can then derive lower bound for the expectation in Equation (C.12) as follows:
E. [e [(())
1
(w))w))d
Zg JRd
1
(w) cd8lwww..il -- oww--++11 wot1l ve, 1)ddw
(Eqn. (C.13))
Z
Rd
exp(
(,(WW.1)
fo+1(w)- -ex((= w w w-w++1)ddw. (Definition of f++1(w)) (w))
Zo
Jdd
Moreover, we define Z.+1 Sgu fot1( (w+1(w)dwwrr < +00, and denote the distribution whose density function is ff+1(w)) Z
P.+1. Then, have
exp( - (.s+ Zot1
Ep-P, |c [e(((w)
E Batt (exp(-(VL,(Wstt)) ws+1))]
Zo
exp( - Lo (W++ +1 Za+1
exp
(-B [-Ew-P [
(VL,(Wo+1)) Ws+1>|
(Jensen's inequality)
Z,
exp( L. (W,+ 1) 12
(C.14)
Z,
where the equality holds because Ps+1 symmetric around Ws+1- Plugging (C.14) into (C.12), we get
(Z.) & (W.+1) 2/ ll'' w 1r,, + +og Z. log Zo+1.
We can further bound the term
log Zo41 as follows:
- -log Zo-1 = - log (f
1
w Wotallir, 181l wi W Petil dw
exp
3d
2c
- log
[Zo41 .E
Pres
exp
w- W W (lze
& - log 2ot1 + E B
[11/ wot W
(Jensen's inequality)
where in the second equality, we define Poti N(Ws+1,cH,,") and 2041 = San www dw. Hence, we get
(Z..) & (W++1)) + w/, w.+ + log Zos1
2.
+ B BarPrun [ 181 w Ws+ 1still
(C.15)
2c
To bound
2_ in Equation (C.15), have Z.+1
SEd e 1o |w- wwwww wi
See e 2o /// li dw
Z.
2,41
Sga www dw
See e to | Pi dw
which indicates that
2.
log
0.
(C.16)
Z,+1
20

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Now, we bound the last term in Equation (C.15), Using the Cauchy-Schwarz inequality, we have
B w
e 18|w
w.
Ws+1 (we,(()..))
Pats
B ww Po+s
[e:00] foolw-wo11lh
wo
B Bw P.ts
[Iw wa+ wot (
(C.17)
(b)-1
(b)-2
Then, there exist orthogonal bases ej, ed E Id such that w Ws+1 follows the same distribution as Ps+1. and can be expressed as:
cd (Hot) where X, Lid. NO 1), E [d].
(C.18)
and X3 () denotes the j-th largest eigenvalue of H Now, we bound the term (b) -1 (C.17) as follows:
V W
E
Pots
= Ex, [c w- Wo
36c (H. 1)x3
d Ex,
(c), (115 & c/
j=1
[x
& Exax² [8ed/Ax]
(Jensen's inequality)
where x2 represents the chi-square distribution. By setting À b 72cd, get
R.
P..1 [036
R xx=x²
e
$
V2,
(C.19)
where the last inequality holds because the moment-generrting function of the didtttirbbttion satisfies Ex xxa [e & 1/v11 2/ for all & 1/2.
To bound the term (b) 2 in (C.17), let M, = (7 largest eigenvalue of the matrix eM, Then, we have
and X₁ = >, (cM51) be the j-th
B Bu- 11
[w - Wstil (e =
Bu-N vee, =
E w [///]////]/] [/]
Furthermore, by performing an analysis similar that Equation (C.18), we obtain
Σ xx33)
d
)
V W [[w]]]]
Ex,~M((01)
Σ N2x,,
Ex,-
d
X (3333
d
(Ex Ex., & & Vj.j' e [d]
/ Tr (M
E X3 Tr (cM,t)
Here, Tr(A) denotes the trace of the matrix A.
21

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Define the matrix Q++1 := I LEET... (Woy())))) By setting 2, we can ensure that V (P (++1) Ia & L As a result, we have Q++1 N aIa + WET, (w = H.. Using this relationship, we can bound the trace as follows:
Tr (M; Tr (H 1 (w.+ < Tr (Q74) (2(,(w+11)
det (Q++1)
Tr (Q.+1 (Q.+1 - Q.)) & log
where in the last inequality, we apply Lemma 4.5 of Hazan al. (2016). Hence, we get
E P [[w
- ( & v3clog det(Qe+1)
(C.20)
det(Q...
By substituting (9.19) and (C.20) into (C.17), combining the result with (C.15) and (C. and summing over 8 Te+1, we obtain
det(Qu+1)
Σ (.(..))
Σ
la(wst) &
Σ
Iw/
w
+ Vbc
Σ log sET
2c sET(1l
dct(Qx)
SET.11
SET
det( (1+(1)+1)
I W 11. v Be log
2c
del (ŽIa)
sETe+1
Σ
Iw, w + Vod (t + 2).
2c TET
This concludes the proof.
C.3. Technical Lemmas for Theorem 4.2
Lemma C.4 (Proposition 4.1 of Campolongo & Orabona 2020). Let the We+1 be the solution of the update rule
W 1++ = arg min (w) + (ws....)))
we
where V S W S Rd is non-empty convex set and (w W2) (ww)) v((2)) - (Ve((w2) W1 W1- w1- is the Bregman
Divergence w.r.l. strictly convex and continuously disferentiable function 1b W - R. Further supposing s/(w) is 1-strongly convex w.r.t. a certain norm || in W, then there exists gi dle such that
We4t1) <n.g's W+11 - u) & (Ve(w.)) Vi((we1),, W441 - u)
for any E W.
Lemma C.5. For any 1. E [T] and w, w' E Ted such that maxies, [ - w')l & a, the multinomial logistic loss 4: Rdd - R, defined in (1), satisfies the following property:
(w - (WW'') (Ve(((')) w') ((()) > le(w') + Vee(w') (w- w') + 2 20x
Proof of Lemma C.5. Recall that by definition (see Equation (A.1)), the loss ( can be rewritten as (z()), where 24 (IE,,),ES, e RlS.. Similarly, & (ww) = Ez(z... Then, by second order Taylor expansion, we have
(1(z)) = [z2, + V(((2)) (zi - =1) + (ze zi) T (f. (1(1-s)) ((1-s)(2(( 2) + s((z= - z;)) (ze - -2,)
> ((4)) Vi((Z)) (4-) + + 3 3/2llzz - zilloo (ze zi) (ole(())) (zi- - zi),
(C.21)
where the inequality holds by Proposition B.6. Moreover, by definition, we know that
Vi((z)) (zt z Vls(w') T (w (w-w)) and (z: zi) (2()(z/) (ze-z), z1) (w (V(((w'(( ww).
22

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Hence, we can rewrite Equation (C.21) equivalently follows:
(((w)= > (((w') + Vl((w') T (w- - w') + 2 3v maxies, 12, - w(ll (w
w)
> (((w') Vl((w'))(())) -w) + 2 3v22
(w - (wwww)
w')
which concludes the proof.
Lemma C.6 (Lemma 18 of Zhang& & Sugiyama 2024). For any H, 2 0, let L((w) (((w) w wellin Assume that le a M- --seef-conccrdantt like function. Then, for any w, We e W, the quadratic approximation L((w) = [w(++1)) + L (We11) w W2+1) + l We+1 lH,, satisfies
Le(w)= L((w) e w w We+1 (w..))))
D. Proof of Theorem 4.5
In this section, we present the proof of Theorem 4.5, To begin, we define set of adaptive warm-up rounds as follows:
T : EE [T] max
| > 1/7?
(D.1)
DEdt
where we define the threshold 7; as:
= 6V2(((0) = (BVdlog(tt/)) (BVVa)))=B + B3/2/d + B²)
Moreover, we define the following two confidence sets for all f E [T]:
(,) == {w E Rd [w - willl (()) and
C, = {w E Rd |w welle, < (()))
(D.2)
where
(6 = V 2m 22 log 416(1)))2dogg (1 +) 4
o By dlog(t/8) 3/2 /d B²), (set a 2B, 17" = =1 3v2a), X" = mmx 21 144n" 21)
and
Bc(5) V 2n log 4v dn (t + 2) 4B²A
V /dlog(1/0) + BVd)
(set a 3//2 1/ 1, = max((12/2ryo, 144rd, 2} = 144d)
Then, the true parameter w' lies within both confidence sets with high probability. Corollary D.1 (Confidence set for adaptive warm-up). Let 8 1]. max 2m o, 144mj" d, 2}. Then, we have
We set 17th [1 + 3V2BB and X
Pr[vt 1, w e ([) > 1-
The proof can be found in Appendix D.2.1.
Corollary D.2 (Restatement of Corollary 4.4, Confidence set for planning & learning). Let (0, 1]. We set n 1.
144d, and π. 6v2(,(0) o (B (Bydlog(t/o) B3/2 /d B Then, if (i) for all 3 L, we have
Pr Pr[Vt 1, C+(5) > 5.
23

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
The proof is provided in Appendix D.2.2.
Furthermore, introduce several useful lemmas. Lemma D.3 shows that UCB,, provides optimistic estimate of the true utility.
Lemma D.3 (Lemma E.1 of Lee & Oh 2024). Lei UCB,, ",W,,, + (666)][=ulllrr Assume that w Ce(o), where (,) = {w W/ [W; w| w|H, & (.())). Then, we have
UCB I w. 23,(8)) Fn "al nr
Lemma D.4 shows that (S.), defined in (8), is an upper bound of the true expected revenue of the optimal assortment, Re(S): w"). Lemma D.4 (Optimism, Lemma 4 of Oh & Iyengar 2021). Let R₂(S) Ens exp(UUB.))) And suppose S. 14Lses exp(UCR..))
argmaxses RS).). for every item e St, UCB e w,w,, then for all t > 1, the following inequalities hold:
R w*) (,())) RS.)))
important to note that Lemma D.4 does not assert that the expected revenue a monotonic function general. Rather, specifically states that the expected revenue associated with the "optimal" assortment increases the MNL parameters increase (Agrawal et al., 2019; Oh & Iyengar, 2021; Lee & Oh, 2024).
Lemma D.5 shows that (S,) increases as the utility values of the items in S. further grow.
Lemma D.5 (Overly optimism, Lemma H.2 of Lee & Oh 2024). We define Rs(S) = Ene exp(UCCU) argmaxses (S). Assume UCB,; UCB, for all i [N]. Then, we have
I+2 1 exp(UCB..) and S.
Lies, exp(UUB,,)r)
R,(S,) & 1 Ejes, exp(UCB:,)
Moreover, demonstrate that the rewards for the chosen assortment, Tu for all i e St satisfy the condition Rs w*). Lemma D.6. For all round e [T', we have
Th Re(Se, w"), Vie S..
The proof is provided in Appendix D.2.3.
We introduce elliptical potential lemma that will be used in our proof.
Lemma D.7 (Elliptical potential lemma). Define He(w) AI EeEL--IITT V2l((w). If 1 (1) $ 2 for all i S, and e [1], then we have
Σ
Σ
ps PilisSon w) |i w)) (w))- & 2d I+ d
VT
(0)
The proof is deferred to Appendix D.2.4.
Lemma D.8 shows that H, and He(w") remain similar when updated only for &$ T Lemma D.8. Let He = AIa + E V2t, (Ws+1) and H, (www) = 2 + ExE(--ITT vll(ww)). Then, we have
1 Hi(w") x He < eHi(w").
The proof is provided in Appendix D.2.5.
Additionally, we present useful lemma that will be employed to bound the second-order term of the regret.
24

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Lemma D.9 (Lemma E.3 of Lee & Oh 2024). Define Q :
RRK IR, such that for any Then, for all i E [K], we have Let Pi(u) = 1+Σ exp(ux))
(#1, ( wk) R
Q(u) -i=1 ->> exp(ur 1+I exp(ux)
exp(ur)
Q
(p)
if ii=j. j. if i j.
Øidj
(p.(
The size of the set T is bounded as described in the following lemma: Lemma D.10. The size of the set T defined in Equation (D.1), is bounded as follows:
2 T & -id log (1+ dd
1+ T
The proof is deferred to Appendix D.2.6.
We are now ready to provide the proof of Theorem 4.5.
D.1. Main Proof of Theorem 4.5
Proof of Theorem 4.5. Throughout the proof of the theorem, assume the following event holds:
(v > 1, w' e (5) U (vt > 1, e C(()))
(D.3)
which occurs with probability of at least 1 25 by Corollary D.1 and D.2.
From the definition of T (see Equation (D.1)), we decompose the regret as follows:
Rs(S; w') Re(Se, w') Reg..( ww))
Σ Rs w*) Re w*)
Σ 1²T
Re(Si,w") Re(S,, w*)
( +
Σ
Re(St, w*) - RR(S,, w")
(Ra(S;, - R&SS, w*) & 1)
1
2 log
(+ I di
+ Σ R. w') - RS w"), L
(D.4)
K
where the last inequality holds by Lemma D.10. Next, we concentrate on deriving bound for the last term. We define
UCB UCB x, w=ww"_ 26) mull. Under the event in Equation (D.3), by Lemma D.3, we have
UCB, < II xJ[W'' 233(6) Tal H, =: UCB,,
Then, define the overly optimistic expected revenue, Ry (St), as (.().) = EiEs, exp((UC,,rrr I+2 eXp((UB.,))
Using this definition and applying the optimism lemmas, we can derive an upper bound for the regret as follows:
Σ
R&(S w") Re(S,, w*) Σ R.(S.) Re(S,, w")
(Lemma D.4)
T
Σ (,.))) Re(S,, w*).
(Lemma D.5)
T
Now, we define function Q S( R. such that for all (Wi...., uss T E | Q(u)
1S
exp My))
k=
1+ St exp(u,)
Here, we denote S, = -ii...., }|s,1} for simplicity. Additionally, let u, (u " = (UCB,,,....
UCB
(iss
and I (uig, .... " )T (I w"...., TT TT
25

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Then, by second order Taylor expansion, we derive
Σ Re(S.) RS w Σ
Q(u)) - Q(ui)
T
6 T0
vQ(u;) (u ui) Σ TTT
(u: - (ou-w,) (i uf).
(D.5)
where U, = (ut,, 1 T e R (Sd is the convex combination of u, and u.
First, we bound the term /.
vi(u)) - u,)) TT
Σ
exp( Lo w ru
exp(ar, w")rs Eies, exp(xT(w")
Iras
(ues un/))
JESt (1+ Exes, exp(x1e w)) (ue 27,)
Σ
Σ kes, expl (2 wx)
#7 tES:
Σ
Σ
Sr w (rss uit Σ Σ
Pr(i]Se, w w")rupe(ilSs, w w")(us) viy)
#T th Se..
JeS,
Σ
Σ
St w")r
(us 1 und Σ
Piliss (") - nit))
17 iES.
jES,
Σ 23)(6)
Σ p((i))
|INL Σ p w
T iES.
JES.
20
< 237(0) Σ Σ 4T seSt
PiliSSe, wiew"""rr"
[Icellle..
Σ
PrlisS,, w "(lll)ll
(Bx(8) is non-decreasing)
jeSr
where in the last inequality, we use the fact that (5) is non-decreasing and that the following holds:
Σ St w w")rr (12ull Σ (rl... w (=)||=11)1113"
JES.
(ru
= Σ
Pr(isS w w H.
Σ
Pr w )res
2 O.
(Lemma D.6)
KES
JESt
Let v 0 and rzo 0. For simplicity, we denote EW [ax]] = By-re (-S [aee and [re] -Ej-pe(-Si, s., [ru].
[ru). Here,
EY represents the expectation taken with respect to the distribution Pa(-1Se, w). Note that EW [rwi] R. w). Then, we can rewrite the above inequality in the following form:
Σ 18T
vQ(u)) - -1;)
(8r(6)
Σ
(
res Jrr I1 EW
Tes LEW" |1am)ll 1)
(010 0ro 0)
18T
= 28)((8)
Σ
E. [Ta EW (reil)
(Icalllee. - E,"" (1zeelle;
(D.6)
between Taz Isees b. given
By Lemma D.6, we know that Fra 2 RS, w*)
Ey [ree] for all E S.. Therefore, we can bound the term inside the
26

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
expectation in (D.6) follows:
Thi Ey (mta])
[|acssll11, Bey" [ H. 1) < (FNi Ey" (rws]) (Iewilllr. |
[s H
2 by Lemma
(Jensen's 's inequality)
(rzi E [ | BY [m)s]] 1r
(D.7)
where the last inequality holds due to the fact that ||a|| laa b bl| a bl |b] for any vectors a, b E R Plugging (D.7) into (D.6), we obtain
vQ(u;)) (u: -,))
$ (3)(6)
Σ
E
(ru E, (res]) pess - E,"" [xts]]
< 2,37(1))
Σ
(ree - E." [ris])
Σ E.p.
E [ [mns]ll mr,1
(Cauchy-Schwarr) inequality)
-V [ri)]:aa?
=23r(0)
Σ of NTTW
Σ T (0)
Σ Pr(i w*) Ia EY" [s 2 A.
(D.8)
where in the last equality, we define the variance of the rewards under w', given S,, as of : V7 [ri]] By [Ir - Ey [r+s]) We define He(w") = I + E vela(w"). Using this definition, we further bound
the right-hand side of Equation (D.8) as follows:
Σ
Σ
Pr(isS w*) Tts E. [mes]]
$ Σ
Σ
Pr(t)St,, w*) |oss EW [xes]]
H.
H.(w*) 1
EFT (0)
T& (E
(Lemma D.8)
Pr(iiSe, w*) |1000  Byy [xts] 2
Σ
Σ
Hi(w+)-1
T* H (ESou(0)
(1+ eT'
< 2edlog
(Lemma D.7)
dd
where when applying the elliptical potential lemma (Lemma D.7), verify the condition [ 12 (. & for all i S. as follows:
| ( el|azs/ H, < E
1 & 2
(Lemma D.S, A = 144d)
144d
Therefore, bound the term I in Equation (D.5) follows:
eT [+
vi(ut) (u. -u) (8)
of 2edlog
(D.9)
dA
Now, we bound the term 12 in (D.5). We define function S
Q St R. such that for all u (u Uis,) 11S.).
Q(u)=
exp(u;; ا exp(u;)
Then, it is clear that
80Q Jsej
since Fre [0, 1]. Hence, get
20ey
1 Σ (u: - u;) " V'QQ(u)) ui)
6²Q (urj
2
2
Σ
(ws
0idj
uiz)
NT"
NT Se jeS.
1
ΣΣΣ
|eei wirl
8²Q
wiyl.
(ra E [0. ID
2
Oidj
1=1 SES,
JES.
27

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Furthermore, we denote pi(ū))
exp(er) Pe exp(Rex)
Then, we have
1+
1
T
8²Q Bidj
Σ
U4i
widl
Uej - uiyl
2
iE JES.
62Q
1
122Q
luei -uil
+
uiil
Ue u
Ōidj
2 L-
δiei
[-1 i jESL,
iES:
T
T
Uu - (Gllp(())) - -Wūن
Σ
Σ
(us
ui:)'
(Lemma D.9)
2
Se Se:iit
ies.
uui (ilpp((u)pps/( -uijl +
3 Σ
Σ
(uei pp (c))
2 1-1 St
Σ
(wu (m.))(()))), + Σ Σ
(ur - " (
(AM-GM inequality)
iE jES,
ieS, JES.
3
+
(un u/a) (ū.))
2
1=
1
5 (uu
Σ
(=1
Therefore, we can bound the term 12 in Equation (D.5) as follows:
Σ u Ui) TVQ().)) uz)
(uri pr(e)))))))
T
t= i
= 10 Σ
Σ Sc
p: (x,)))
1 ( H.
(definitions of u, and u²)
10 Σ
max B, (6) 2 1
< (0) ==1
Σ
max
||
iES,
20 < (r())
T
1+
(D.10)
dA
Finally, by substituting (D.9) and (D. 10) into (D.4), and setting X = 144d, ग. = (lodlog(())) + B3/2 + B²) Bvd).
and 3r( = O (v (Vllog(T/o)+ BBd)) we obtain
2 (w") & 2 log (1
1
T dx
+ (3)(0)
Σ o7 2ed log
(1+ eT
+ Br (8)
20
(1
( d
T
d)
k
=0 ( Bdy Bdylog
Σ
of + -
B (log (logT)² + BBullog
By setting 8 5/2, we complete the proof of Theorem 4.5.
28

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
D.2. Proofs of Corollaries and Lemmas for Theorem 4.5
D.2.1. PROOF OF COROLLARY D.I
Proof of Corollary D.I. Theorem 4.2, we consider the case where W/ W (w E R |wlle B3 for all >> 1 and the Hessian matrix H
Condition: sePweW, (w- ([-)[w) & for all e S.
2B.
We set 2B, shown below:
sup
[ w"]l sup weW
[ w')l o sup
| w < 2BB
weW;
weW
Substituting a = 2B (which gives 1/= + 3v2B) into Theorem 4.2, while setting = mmxx112221)) 144n d, 2). for LE T we obtain
=
|w" wl Ce(0) o
(c)0)=o@vvdlogtee (Bydlog(t/o) B BB)
For T the confidence set (6), along with w and H remains unchanged. Thus, the proof is complete.
D.2.2. PROOF OF COROLLARY D.2
Proof of Corollary D.2. As with Corollary D.I, we prove this using Theorem 4.2. Let W3- W/ (6) and let the Hessian matrix be H,.
Condition: seP [ w -w") & for il St
1
3/2
We set a 3+2' as shown below:
sup (w w*)l weW,
sup [T - w*)l wEW? (6)
max I ((-))) nEAt
max (8)
|w w [HE + lww"" - w'1
(Hölder's inequality)
mnax weWr (8)
||w -
ww 1 + I/,"" - w'll 17:1"
(t $ T
(Gr(0) + ww(l
(Definitions of 7, and ())
(g)
(()))
(Corollary D.1)
3 3C2((())
3
Plugging 1 (which implies 17 = #1+3//20 1) into Theorem 4.2, while setting À = max(12v22 144nd, 2} 3/2 144d, for tarte & T derive
Iw w H. & B((5) (V Bvd).
For t E T", the confidence set (6), along with and H,, remains the same. This conclude the proof of Corollary D.2.
D.2.3. PROOF OF LEMMA D.6
Proof of Lemma D.6. By the definition of the optimal assortment and Lemma D.4, we have
Re(S,, w²) & R, w') < R(()) & (S))
Thus, is sufficient to show that res > ((())) for all S..
29

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
We prove this by contradiction. Suppose there exists item i e Sy such that ru < Rs())). If we remove item from the assortment St, it would result in higher expected revenue. This contradicts the optimality of S. argmaxses (S). Hence, we conclude
Tu 2 R(())), vie St.
which completes the proof.
D.2.4. PROOF OF LEMMA D.7
Proof of Lemma D.7. For simplicity, let EE [m]]]] = E)-p [1tz]] and vio = 0. Then, we can express (2e,(w) as follows:
(e)((w)= Σ Pa(iss,: W)
Σ
Pa(iss.. w)ps(ilSs, w)
iES,
Pa(i W)
Σ (0) jOS,.u)))
Po(iss,, W)p.
(0)
1 [x - [x
[an (E [xx:])
= E.W (Tes - EN [x (2 E. [
= Σ
Ps (ils, w)( - E [x - [x,,))
(ES
Using the definition H.(w) AL E 2e
V+(,(w), follows that for any update round E [[TT", we have
det (Hs+1) = det (H,)
1+
Σ VES,
Pa(iss,, w) Jasi R [ [[ss][HH(ww)] H.(w)
By the assumption that || 11, (w) 1/2 for all e S., we know that (0) Pa(i]S,, Po w) |000 [ (w) - 1. Then, using the fact that = & 2 log(1 + 2) for any 2 E [0, 1], we obtain
Σ Σ
(ilS,, w) || - E. [xag]] 1l (w)---
#E[TTT" (0)
Σ log 1+ Σ (o(iss., w) (ist [=[[2>)) H. H,(w)
< 2
st =e[t]TTT
(ES,
dot(Hs+1))
2
Σ log
det(HH)
sE[t]TT
det(H(+1)
2 log
det(HH))
(tr(He (r(H+41)
2d (1+141.
< 2d
dA
which concludes the proof.
D.2.5. PROOF OF LEMMA D.8
Proof of Lemma D.8. For any E [t [f--11 T let X, E IR S:Ixd be the matrix whose i'th row is x.. Then, by the equivalent
notation of the loss (see Equation (A.1)). we have
V2t
(Eqn. (A.1))
3022 X (2L,(;))
(Proposition B.5)
(12s+1 - 21100 & 3/2
=eV'l(w)),
30

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
where the last inequality holds because, for any 8 T", the following holds:
12++1
2,10
max iES,
( (W -w"l
max [is (Hx) (l wall + l!w"" w" (mw))
(Hölder's inequality)
is
(|w++1 w + Iw"" w'(
(8 $ T
75
(So(d) + Iw" -wwl
(Definitions of T, and Ws+1 E (6))
6v 6v)(,(6)
(o(5)
(Corollary D.1)
3 (g)
3
Thus, we get
H, = X
Σ V'e,w.+1)) 3 te
Σ vel((w")= eH,(w").
SE -E
st(t-1]iTT
To prove the other inequality, we use similar line of reasoning:
v'e, xx, VXVV2ll(2))) 3v X.VVVVVV Vila s sex, sex (2) eV2R.(w.+t))
which implies that
H₂ = AIa+ +
Σ sT[t-I]TT"
1 ve(,(wo+1) 2 AI++ Σ v&la(w") 2 H.(w") e
TT
This concludes the proof.
D.2.6. PROOF OF LEMMA D.10
Proof of Lemma D.10. Recall that by the definition of Hi",, we have
H AIa +
Σ
(STWYft (t.........
ALa
Σ
po(ialfis), w. (olllttie), (esffi))ws+))pee (p Ws41)
SET "tT..
PI +
Σ
po(ielli)), wetl)))))w wst1)
NETW
where ig is the index of the item such that Fet = argmax | Then, we get
Σ max
-
Σ
(zu, argmax |
(nn for t E 7
T
Pe(delfie), (eff))(0ffte) wetz)lleaall2a ((pp))
(Definition of k)
te7
Pe(telfee) wc-1)p we+1)l P }
Σ min 2
TM
(1 1 & _t 1 & AM > 2)
2 dlog
T dA
1+
(Lemma D.11)
k
31

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
On the other hand, by the definition of the update rule in Algorithm 1, we have
Σ
max I x
(
Σ
T
(T is non-decreasing)
17
LET"
By combining the results above, obtain
2 & 77
T di
T
1+
which concludes the proof.
D.3. Technical Lemmas
Lemma D.11 (Lemma F22 and H.3 of Lee & Oh 2024). Let H, = Xl + V' Define Toi == Esi
(ls. If [= n, & for all e St and s e [t]. then the following statements hold true:
(1) E.=1 Eies, Po(iss., (0) Wo+1)llzal? n-
2dlog (1 d.).
(2) Σs-1 Eies, paliss., wo+1)lliad H, & 2d (1 2x,
(3) E.-1 maxies, | + & dog (1 + )
(4) Σ maxies, | H, & dog (1 + axx)
E. Instance- Deennden Regret
As special case, if the rewards are uniform (i.e., 1), we can establish an instance-dependent regret bound.
Proposition E.1 (Restatement of Proposition 4.10 Instance-dependent regret under uniform rewards). Define x² Eiest S7 w (O)S;, w*). Under the same conditions as Theorem 4.5 and assuming uniform rewards, the regret of OFU-MNL++ is upper bounded by
Reg, (w")= = ((IDEET + Bdy logT)
Bdv/ogg
Σ ki
1 Bdd (log (logT)² + 1 B'dllog
E.1. Proof Proposition 4.10
In this section, we present the proof of Proposition 4. 10. In the case of uniform rewards, where Pr=11 for all [N], the of term be upper-bounded by is plus additive term.
Proof of Proposition 4.10. From Theorem 4.5, have
Regy(w") ((aDETT + Bdyloggl
1 B& (log 2)2 1 -Bd'oo )
T
of
n
k
32

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
When rewards uniform, can rewrite the Σ of term follows:
T
T
(1is ()-
(l
2
(
Σ Pe(l w")r
Pe(i)Se, w w")rs'
veS,
T
Σ (rlls w" w')p: w
(ru 1)
ieS,
Σ k4 + Reg, (w").
where the last incquality holds by the following lemma:
Lemma E.2 (Lemma of Perivier & Goyal 2022). Let K = Lies; Pe(i]s;, w')p((0|St w*). Then, we have
T
T w'(ilS,,'')pp(000 w (0)S, w') $ Σ mc + Regg(w").
Σ
ieS.
Hence, we get
O ((IDEET + Bdy logT
Regr (w") =0
Σ
Regr(w")) - & (logT)² + BB log
k
Solving the above equation completes the proof of Proposition 4.10.
E.2. Discussion on Instance-Dependen Regret
In this subsection, we further discuss about the instance-dependent parameter xy and the variance of rewards d
True meaning of k;. The instance-dependent parameter <j, which appears in the regret bounds of many existing (multinomial) logistic and GLM bandits (Abeille et al., 2021; Faury et al., 2022; Perivier & Goyal, 2022; Lee & Oh, 2024; Sawarni et al., 2024), is indeed the variance of the uniform rewards given S contrast, of denotes the variance of general rewards (including both uniform and non-uniform) for the offered assortment S, Under uniform rewards, as shown in the analysis of Proposition 4.10, iyz and of are closely related, as the assortment size remains the same and the rewards identical.
Possibility of Instance-Dependee Regret under Non-Uniform Rewards. Readers might expect an instance-dependent regret bound for general non-uniform rewards. However, we cautiously argue that establishing such a bound in the non- uniform case is non-trivial using existing analytical approaches. Unlike prior works on binary logistic bandits (Abeille et al., 2021; Faury et al., 2022), uniform rewards MNL bandits (Perivier Goyal, 2022; Lee & Oh, 2024), and generalized linear bandits (Sawarni al., 2024), the size and rewards of the offered assortment S* and the optimal assortment S are different. This fundamental discrepancy makes it impossible bound quantities related S, using those related to S
F. Proof of Theorem 4.12
In this section, we provide the proof of Theorem 4.12. For ease of reference, Table F.1 summarizes the notations used for OFU-M"NL.
We define (w( as the negative log likelihood of w with respect data collected up to and w, the corresponding maximum likelihood estimate (MLE) estimate:
(((w)=
Σ (w(w)
Σ
Σ Uta po w), := argmin (w).
1.
weW
33

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Table F.1: Symbols for OFU-M"NL
(.(w)
:- ----I- - yts logps (i),,, w).
Wr
maximum likelihood estimate (MLE) estimate at round
AMLE
8732 regularization parameter for MLE
HNLLE
> (+(((w) I
VI
parameter that satisfies l|w" Wellve = Iw" -w (F
(BMLE( (5)
o (Vdlog( B1/8)
= 23, (8)2 +1
(8)
fwe W: : La(w) (wr)) < (6)²)
WH
argmaax argmax (8) N. w. optimistic utility of item round
(S)
Eiey exp(= Wedre optimistic expected revenue of assortment S at round t
1+2 exp(xi, wes)"
of
(- (-1e,,w))
(rus B, B. (rees)) 21
variance of rewards given S, at round
And the confidence set is defined as follows:
MME CAILE(0) ()) = fWEW W: L((w) (.(W) & MLE (8)2)
where
1 + dlog max e, 4e 4eB(t-11] 1) SMIEE() == log 8
d
The confidence radius (J) follows directly from Theorem 3.1 in Lee al. (2024b). This result is derived by incorporating the Lipschitz constant for the MNL loss, i.e. L. maxxew [L,(w))l2 & {1 (0-11 [V((()) 2(1 1) (under Assumption 3.1).
Lemma F.1 (Unified CS for generalized linear models (GLMs), Theorem 3.1 of Lee et al. 2024b). Let L == max /L, (w)]ll be the Lipschitz constant of Le(.), which may depend on ra)l Then, we have Pr[Vt. 2 1. w E CMT.(() > 6, where
CALE (8) W W: W: (. & (8)= log dlog max {e. e, 2 1)
Then, offer assortment S, that maximizes the optimistic expected revenue R.M follows:
Σies exp(x wa)ra
S: argmax (M) argmax
where Wes argmax 2 W.
(F.1)
SES
SES
EEes exp(x,, w.y)"
WECMLE(
Additionally, we define the Hessian of the regularized loss w as:
H.
MLFF
Σ Vel + A MT. where MLFF
8B2.
Now, we present useful lemmas that will be used in the proof of Theorem 4.12.
Lemma F2 (Restatement of Lemma 4.11, Improved MLE confidence bound). For any E [T]. we define Vž
such that |w" w. <.lb=<c(0))) =|[ l|ww - +v(w" w.)ddo and (TMLE()??) VZLi(u)) + XMLET
Σ'=1 (2((())) + X Let MLL. 8B2. Then, for any > if w E (M).(()) and Assumption 3.1 holds, then we have
l|w" Welleapea(y))) & 2,3 (8)2 + O (d
(5)²
34

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Algorithm F.1 NL, OFU-Maximum Likelihood Estimation MNL
1: Input: failure level 6, confidence radius ()).
2: for round = ... do
3: Observe feature set Xr
4: Calculate the norm-constraines MLE: W. - argmin wew (((w).
5: Update (5) {w E W: ((()) (w:) ) & St GMLB (8)²). (M)))
6: Set We - wrggaawwachuu Z. w for all [N].
7: Offer S. argmaXses (S) and observe y
8: end for
The proof is provided in Appendix F.2. By Lemma F.2, we define the ellipsoidal version of the confidence radius as follows:
max 4e 4eB(t-1))
111 +1= -V
(8) 2 2l 2d
d
Additionally, we present useful technical lemmas.
Lemma F3. For any E [T], W1: W2 E (Ó), and Wes 2 O, we have
Σ
Po(j]S., Se w2)l Wit AL (6) max max | (M)) seS,
iES,
SES
The proof is deferred to Appendix F.2.2.
F.1. Main Proof of Theorem 4.12
Proof of Theorem 4.12. We follow reasoning process similar to that used in the proof of Theorem 4.5.
First, we define the set of large elliptical potential rounds as follows:
MIE = LE [T] ||o (A 2 2. vie s
To
Furthermore, we define V. = EseTME set J. + ALL where i, is any item in S, (for example i, argmaxjes, ||== (pp .). and Zej = (Pl(s (z (O)p: Dz)xsi Then, the following inequality holds:
dA MLE. [T
MLE
d
Tr(VT)
W
U & 1)
d
d
det(Vr)
(AM-GM inequality)
det(Vo)
I MET
1 + |late 12--.
(rank-1 1 update equality for det.)
det(Vo) I |lares (eppne(ey) ))
(H (v;) 2 Vi
MET
det(Vo)
I[ M
(1
+ K|a0 1 Popee(e)))
(Definition of k)
(ME))) (1+ 2
(1 T.
35

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
where the third inequality holds because
H. (2,)) =
(2,(( + I
Σ Pa(iiSs: 20) ieS,
- Σ Σ
(i A
ieS, jES,
Σ p. 1i)
Σ
(i) (Iaee + Iajazs)
+ A
2 iES, JES,
iES,
Σ Pa(i v1 (1 IES.
T
Pa(ilS.. vi)p vi) (Faittse + Infae
IL
iES, JES
(xx + yu 2 ay yx for any x, E TR.))
Σ Σ Pa(ilS.. v1i)
1 Σ Polils.. vi)
Tolatd + ML.F I
jES.
Σ iE
22 + I
[-1
A Vi.
Thus, we have
T
To
MLE
log(1 1 + x/2) log 1+
(F2)
d.MLFFF
Hence, by Equation (F.2), we can decompose the regret as follows:
T Reg, (w") Σ
Re Re(St, w') (Sc, w")
TT
MLE
Σ
Ri(St ('),:w") - (s w")
d
T
log 1+
Σ
Ra(S w*) (S w"),
(F.3
log(1 (1 + x/2)
dAMLE
CETALE
Next, we bound the second term of Equation (F.3). Let UCB,; =/W 78
MLE (6)1lelelll and UCB, UCB,, :=
J. w
2- MLB ( u. Then, for all E [N] and > we have
Te Wa F w & UCB.. "/ow" w < 2% 2YMLE (8) aes (1))))
(Definition of Wts. Lemma F.2)
which implies v..,. & UCB Thus, by Lemma D.5, we get
(MLE(S))) (S,),
(F.4)
where FAMLE(S))
Eies, exp(UUB... E+Ssses, eXp(UCBB.))
Define a function Q :lS + IR, such that for all u (ui,..., (us)) E RlS.), Q(u) -1 exp(un)ras For simplicity, we write S. (is...;(ss.)) Furthermore, we denote u, (ups.... Uti T (UCB.,).... UCB
1+ exp(u,))
Ba
T
36

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
1... ..... Thi ) (Iiti w 3 Fihss w²) Then, we have and uz (uh
Σ Re(S;, - RS, w") TALE
Σ (St) Ro( w")
(Lemma D.4)
TT
Σ MLE (St) -Re w*)
(Eqn. (F.4))
*
Σ #T
(u,,) Q(ui)
=
Σ vQ(u,) (u: - u,) + Σ
(u: (u) ( 47),
(F.5)
T
where u, (Uea.... ..... ) RSS is the convex combination of u, and u.
We first bound the term Iz. For simplicity, let [x:s]] (==) and [r[r (. Then, get
Σ
vi(ut) ui)
1
explsr w )rii
exp(2 (el w') Dres Eies, exp(xT(w")
Σ
1+ LKES. exp(x w.) (Uei und)
Σ
(1 + Exes, exp(xx/ w)) (ui vie)
$77 MLE SES.
JES.
Σ
Σ
PrlilSes whi 2 ()) Ie (M
Σ
Pr(jS w )2% MLE [z)s (L)
1$7 MLE SeS.
jeS.
< 2 (O)
Σ
Σ
pr(i]Se, w'rre (10ill
Σ jeS.
Prli, wx ""lloryllmann
THT SeS.
[ Ey (resi) (Iecellepprooe) 1 Ey
[ (1me)llam*())) 11]
2 2LEEE(() (0)
Σ Ey"
(#10 0, rro 0)
TET
& MLE(() (0)
Σ
Ey
(TH- EY (resl) |oos BY [wrs]] maa
(Similar Eqn.(D.7))
MLE
We further decompose the last term as follows:
(m (Ma-EE [raj]) Des Err-"Er' [ m
Ew"
18 TTALL
Σ Σ
VellisS w (p(((s)))) (ra- EEW [res]) |ois E [ mmpe
NTTALL ieS,
Σ (P((i(Se, w*) - ( v Pr(lisee. w (ra- E (res)) Iee Ex [ mppreeyy
16 (T iES.
+ Σ (ilSe, w') (ra-EE Ex' (ros) (1oms - Ey [mrs]] m - -1aees E [ [areill ( (F.6)
RET SES.
37

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
Then, the first term in (F.6) can be bounded follows:
Σ Σ
Vpi(is w pi((s.)) (ru - EW Tress)
[21s]
1470 St
Σ
Pr(i w*) (ro EY (res])
Σ ATTO seS.
Σ pa(i)Se. an BB [1rtg] (1)
2
of
MIE S
Souchy-Schwarz inequality)
T of
2dlog (1 1+ d.MLLEE
T
(Lemma D.7)
Note that when applying the elliptical potential lemma (Lemma D.7), we ensure that the condition [10s)188.000))-- < 1/2 holds for all & & TOLLE Additionally, the second term in (F.6) can be bounded as follows:
Σ Σ 14 TT St
(. - (((( v Vpi(i]St,.')
(TH - EN lresl) |res Weis (anol) sTpuE(uz)-
Se w*) pe pr(i v2)l
Vi((iSee w*) Tee - B [crss] [ mapeeey
Pr S., w*) + V (1)).,
1$ T
Pr (i)Ss, w") - (i)S wi)l
174 R.t [mte]] (w;)
1$ T
4-/ MLE
max
T [cres]]
max sES,
Jets (SpuE
(Lemma F.3)
IES;
of TFT
4 (8)
Σ
max JES,
Jei - E5 [Fee]] (1N
Σ
max NESt
Iee 2 (o)
(Cauchy-Schwaad inequality)
MLE
AETUULE
(6) 1T
Σ
Σ
pelilSe, v2) | - E²¹ [ree]]] ( lemms v
Σ
max | (a (pp seSt
(Definition of x)
K
LTTAMEE i iEs.
8
(M) log
MLB
(1
T
(Lemma D.7 and 1.1
K 1T
dAMLE
Finally, we bound the last term in (F.6). Using the inequality ||a] - |bll E ||a
bll for any vectors a, b E Rdd we get
Σ Σ Pa(i)SS,, w*) (TH- BY
BY' (res)) (1oee - ByY [crss]] ppp res EE [mrs]] snpua((e)) .)
MLEE S.
Σ Σ Pr(ilSe, w*)
Σ (pe(iSS PrCiiSe, w w')e
$$ T MLE VeS.
JeS.
(2))
4 MLE (8)
[pr(i)Se. v - (élSee w')l |
6 MALE IES.
4
MLE (8)
>
max
Des 2 (
(Lemma F:3)
VES.
8 MLB (8)d
1+ T
7I
dAMLE
(Lemma D.11)
K
38

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
By combining the three results above, we establish bound for /3-
Σ vQ(u;) (u: -0: u²) & 2 T
(8)
T Σ
2
2d
1+
T dAMLE
+
36 'T
(d)
T d'MLE
(F.7)
On the other hand, the term 1 in Equation (F.5) can be bounded by following the same process in Equation (D.10) in Appendix D.
20 MIE (d) (1+ - - & Σ (u, VVQ(a)
(F.8)
2
dAMLE
Plugging (F.7) and (F.8) into (F.3), and setting MLE
and TT (8) O Ol (BT), obtain
8B2
T
Σ
Re(S,, w") - -R(SS,. & 27
(
Σ
2
2d log
1+
dAMLE
d log(1 + k/2)
T
56
T d
log
dAMLE
+
TT
MLE
(5)
1+
K
=0 (diog(B7))
Σ
o + - de (log(BT))²
F.2. Proof of Lemmas for Theorem 4.12
F.2.1. PROOF OF LEMMA F.2
Proof of Lemma F22. By using Taylor expansion and applying the first-order optimality condition for a convex function, we obtain
C((w") L.(w)) = (VL((W)..' we) + ((w" - -we) ([-1-1))22 1-- + +eww" - -wi)ddo (w" -w,)
20, first order optimality condition
ww
(el
(Definition of 2²)
w- wel (elliaan(e)) A MLE
(Definition of H.MB( (v)))
By setting L, 2(1 - 1) and MLE
SB and applying Lemma F.I, we derive
Iw' Wel Wellppe $ 2og 5 + 2d max e, 4eB(t - 1) 1) +1 11.22,,ML
2,3ME (8) +
d
which concludes the proof.
39

---

Improved Online Confidence Bounds for Multinomial Logistic Bandits
F.2.2. PROOF LEMMA F.3
Proof of Lemma F.3. By the mean value theorem, there exists (1 Wi cW2 for some (0, 1) such that
Σ
( w1) - Pt w2)l Wes
S.
Vp.(ilSe, () w2) wii
ieS.
Σ I
Pr(d]Se, ()= -P(((S.)) Σ Pr(jISt,
(w1 W2)
wes
JES,
Σ
Pe(i]SSr St. <) [= ( wes
Σ
Pt (i E)
Σ Dc ())).
12,2, (1 w2)
ieS.
jESc
2%t
MLF.
MLE
2
MLE
Σ (e E)w
Σ
Pe(jiSe, ( 3) (1))
i.
ieS.
jES.
(W1, W2 (M) Lemma F.2)
$ 4% (L)
max max 188,
Iti (=)))
iES:
which concludes the proof.
G. Experiment Details and Additional Results
UCB-MNL
TS-MNL
[FU_MNL++ (ours)
OFU-M'NL (ours)
8=2.0,
50, K=5, d=10
Bw3.0, N=50, K=5, d=10
B=4.0, 5550, K=5, d=10
B=5.0, N=50, K=5, d=10
1500
Cumulative Regret
1000
750
0
500
1000
1500
2000
2500
3000
500
1000
1500
2000
2500
3000
500
1000
1500
2000
2500
3000
500
1000
1500
2000
2500
3000
Round (t)
Round (t)
Round (t)
Round (t)
Figure G.1: Cumulative regret for different values of B when d 10.
For each instance, we sample the parameter w' uniformly from a d-dimensional Euclidean ball of radius B, denoted by (B). Similarly, each context feature zn is independently and identically distributed (i..d.) from unit ball, denoted as (1). This ensures that ||w*||2 & B and ||æeel| & 1, satisfying Assumption 3.1. The rewards are sampled independently in each round from a uniform distribution, i.e., Tri ~ Unif(0, 1). We set the number of items to N 50 and the maximum assortment size to = 5. For each instance, we conducted 20 independent runs and reported the average cumulative regret (Figures 1 and G.I) as well as the average runtime per round (Figure 2) for each algorithm. In our experiments, since the threshold T; too conservative in practice, we empirically tuned the hyperparameter т, for OFU-MNL++ by searching over a certain range of values while maintaining its inverse relationship with a (i.e., a higher Tı corresponds lower a).
As additional experiment, Figure G.1 presents results for larger value of d, specifically continue to outperform other baselines. While the performance of OFU-MNL++ is somewhat sensitive to the values of B and d, primarily due to the adaptive warm-up rounds, its asymptotic performance appears to be the best. Notably, the slope of the regret curve the smallest for large f. Additionally, OFU-MNL++ enjoys a constant computational cost, similar to OFU-MNL+. In contrast, NL is the slowest among the algorithms, as requires solving a convex optimization problem compute the optimistic parameter Wy. as described in Equation (F.1).
10. Our algorithms
40


Reviews:
[{"review_id": "L382nF1Fuw", "reviewer": "Reviewer_nHs2", "summary": "The main contribution of this paper is proposing an improved online confidence bound for multinomial logistic models. Moreover, the authors applied their results to MNL bandits to achieve an enhanced result. Further, they also showed numerical experiments.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your positive support and recognition of the value of our work! We truly hope that this research helps to illuminate a new direction for MNL models and bandit algorithms. Please feel free to reach out if you have any further questions.", "claims_and_evidence": "I verified the correctness of some theorems. Moreover, numerical experiments make sense to me.", "methods_and_evaluation_criteria": "The evaluation criteria are natural.", "theoretical_claims": "I verified the correctness the theoretical results in Appendix C.", "experimental_designs_or_analyses": "The experimental results make sense to me.", "relation_to_broader_scientific_literature": "Bandits are a fundamental topic in learning theory. Any good result in this context will be valuable. This paper provides a new tool, namely a confidence bound for multinomial logistic and applies it to MNL bandits to achieve improved results. This is a solid theoretical paper. I think it is a good contribution to the field of statistical learning theory.", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "I like the writing of the paper. In particular, I like proof sketches and intuitions.", "other_comments_or_suggestions": "-", "questions_for_authors": "I do not have any specific question.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "-"}}, {"review_id": "GY4J2BfQ5m", "reviewer": "Reviewer_qKeK", "summary": "This paper studies the multinomial logistic bandits problem, in which the learner submits an assortment of at most $K$ arms and then receives binary feedback following the MNL model. The main contribution of the paper is the proposal of an improved method for this problem, yielding an online confidence set of $O(\\sqrt{d\\log t}+B)$, which improves upon previous work by factors of $\\log t$, $\\log K$, and $B$. In addition, the paper provides a variance-dependent bound for the multinomial logistic bandit model and an MLE-based method that completely removes the dependence on $B$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper and provide valuable feedback.\n\nWe would like to clarify that our main contribution is the development of the **first $B,K$-free, variance-dependent optimal** regret bound for MNL bandits, which cannot be achieved by existing algorithms such as those proposed by Faury et al. (2022) or Lee and Oh (2024). We provide detailed explanations below and sincerely hope this clarification helps convey the novelty of our approach.\n\n---\n### **Comparison to Faury et al. (2022)**\n\nWhile our algorithm shares some conceptual similarities with Faury et al. (2022)—notably the adaptive warm-up strategy—it fundamentally differs from their method in several key aspects beyond just the use of online updates:\n\n- **Decision rule**: The decision rule used in the adaptive algorithm (ada-OFU-ECOLog) by Faury et al. (2022) does **NOT** yield a $B$-free confidence bound. Their confidence bound, $\\eta_t(\\delta)$ (defined in Equation (15) of their paper), has an order of $\\mathcal{O}(B d \\log t)$. This $B$-dependence arises primarily because their method does not guarantee that the diameter of the search space, $\\text{diam}_{\\mathcal{A}}(\\Theta_t)$, remains small or bounded by a constant over time.\n\n    This is notably distinct from their non-adaptive algorithm (OFU-ECOLog, fixed-arm setting), which achieves a tighter confidence bound $\\sigma_t(\\delta)$ of order $\\mathcal{O}(d \\log t + B)$.  We believe the reviewer may have inadvertently confused the confidence bound of ada-OFU-ECOLog with that of the non-adaptive version (OFU-ECOLog).\n\n    In contrast, our proposed decision rule **always** guarantees a confidence bound that is completely **independent of $B$**. Combined with our new decision rule and the novel online confidence bound established in Theorem 4.2—which incorporates several technical novelties such as $\\ell_\\infty$-norm self-concordance, bounded intermediate terms, and a $d$-free regularization parameter—we successfully achieve a $B$-free regret bound.\n\n- **Prior knowledge of $\\kappa$:** Faury et al. (2022) **require prior knowledge** of $\\kappa$, which is often impractical or even impossible to know beforehand in real-world settings. In contrast, our algorithm does not rely on any prior knowledge of $\\kappa$, making it significantly more practical.\n\n- **Gram matrix update:** In Faury et al. (2022), the Gramm matrix $V^{\\mathcal{H}}\\_t$ is updated  **overly conservatively** using a weight parameter $\\kappa$ as $V^{\\mathcal{H}}\\_t \\leftarrow \\sum_{ a\\in \\mathcal{H}\\_{t+1}} \\kappa a a^\\top + \\gamma_t(\\delta)I_d$. Since $\\kappa$ is very small—specifically, $\\kappa = \\mathcal{O}(e^{-3B})$ in logistic bandits, and even smaller in MNL bandits with $\\kappa = \\mathcal{O}(K^{-2} e^{-3B})$—the updates become too conservative. As a result, their search space $\\Theta_t$ shrinks too slowly. In contrast, our algorithm does **NOT** apply such conservative updates to the warm-up Hessian matrix $H^w_{t+1}$. Instead, we update it using the second derivative of the loss, which enables the search space $\\mathcal{W}^w_t(\\delta)$ to shrink more rapidly and tightly.\n\n---\n### **$\\ell_\\infty$-norm self-concordance**\n\nOur self-concordant property is constructed with respect to the $\\ell_\\infty$-norm, whereas Lee and Oh (2024) use the $\\ell_2$-norm. This distinction is crucial: naively applying an $\\ell_2$-norm-based self-concordant property leads to a step size $\\eta$ that depends on $K$ and $B$, which in turn causes the confidence bound to also depend on these parameters.\n\nWe believe this novel $\\ell_\\infty$-norm self-concordant property is of independent theoretical interest and has potential applicability beyond bandits, extending more broadly into the literature on MNL models. \n\n---\n### **Variance-dependent bound**\n\nIt appears the reviewer may be confusing the definition of variance used in the cited papers [1,2]. To clarify, similar to our setting—where variance depends on the selected assortment $S_t$—**the variance in [1,2] also explicitly depends on the chosen arm $x_t$**. Moreover, the regret bounds in both our work and [1,2] are **not** dependent on the learner’s predictions—they depend solely on the variance under the **true** parameter.\n\n---\n### **Tightness of $B$ in non-leading term**\n\nSince Theorem 4.12 (MLE version) achieves a regret bound with a non-leading term that is free of any polynomial dependence on $B$, we believe that the $B$-dependence in the non-leading term of Theorem 4.5 is likely not optimal. Eliminating this dependency is an interesting direction for future work. We appreciate the insightful question that brought attention to this issue.\n\n---\n> We sincerely believe that we have addressed all of your concerns. If you agree, we would greatly appreciate it if you could kindly reconsider your evaluation. Additionally, please feel free to reach out if you have any further questions or require clarification on any point.", "claims_and_evidence": "From my perspective, the paper's claims are supported by clear evidence.", "methods_and_evaluation_criteria": "The regret bound is used as the standard metric for the logistic bandit problem.", "theoretical_claims": "The proofs seem sound, although I haven't verified the details exhaustively.", "experimental_designs_or_analyses": "From my perspective, the experimental comparison is adequate.", "relation_to_broader_scientific_literature": "This paper presents an improved confidence set for the MNL bandit problem. Its primary results improve on the work of Lee and Oh (2024) by factors of $O(\\log K)$ and $O(\\log T)$, and the previously multiplicative term involving $B$ is now an additive term.", "essential_references_not_discussed": "The related work is appropriately cited and discussed; however, the technical contribution relative to Faury et al. (2022) remains somewhat ambiguous. Please refer to the strengths and weaknesses section for further details.", "other_strengths_and_weaknesses": "**Strengths of this Paper:**\n- The paper offers several improvements over previous work on MNL bandits, with improved dependence on $\\log T$, $\\log K$, and $B$. Additionally, it introduces a variance-dependent regret bound.\n- Experiments are provided to demonstrate the effectiveness of the proposed methods.\n\n**Weaknesses of the Paper:**\nAlthough the improvements are interesting, my main concern pertains to the overall significance of the results and the technical contribution.\n- Regarding the improvement in the dependence on $B$, the warm-up technique employed here appears closely related to that of Faury et al. (2022). As discussed in Remark 4.8, the primary difference is that the previous work utilises MLE, while the current study adopts online mirror descent. However, since Faury et al. (2022) also propose an adaptive method to verify the condition on the fly, it remains unclear how challenging this extension would be for the MNL problem.\n- Concerning the improvement in $K$, one of the main techniques is the constant self-concordant property of the MNL loss, which was already established by Lee and Oh (2024).\n- The variance-dependent optimal bound is interesting; however, it is unclear how large the term $\\sigma_t^2$ may be, given that it depends on $S_t$, the set of arms selected by the learner. This dependence is somewhat unfavourable, as previous variance-dependent bounds in linear bandits are typically independent of the learner’s predictions [1,2].\n\n[1] Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP. NeurIPS 2021.  \n[2] Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs. NeurIPS 2022.", "other_comments_or_suggestions": "Please see the comments above.", "questions_for_authors": "- Could you further emphasize the challenges of extending the warm-up technique from Faury et al. (2022) from an offline to an online setting?\n- Could you provide more discussion on the significance of the variance-aware bound in cases where $\\sigma_t$ depends on $x_t$?\n- Although Theorem 4.5 successfully removes ${B}$ from the leading term, the dependence on the remaining term appears large compared to Lee et al. (2024). Could you elaborate on the tightness of the dependence on $B$?\n\nI would be happy to increase my score if the above concerns are adequately addressed.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vXNmiuQ1Zz", "reviewer": "Reviewer_ji1C", "summary": "This work extends the MLE-based $\\text{poly}(B)$-free online confidence sequences for generalized linear models, where $B$ is the norm-bound of the parameter set; to the setting of multinomial bandits to give a statistically SOTA algorithm (in terms of the dependence on $B$ and), which is also variance-dependent. The work also provides a computationally optimal algorithm under the relatively well-known \"online Newton step\" framework base on ellipsoidal confidence sets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive evaluation of our paper and for your valuable feedback! Below is our response to your question:\n\n> *The online confidence sequence is claimed to be the \"tightest\", so could the authors provide some lower bounds on the width confidence radius itself, or at least some intuition on why couldn't we do better?*\n\nWhen we referred to our result as the \"sharpest online confidence bound,\" we meant that, to the best of our knowledge, it is the sharpest among existing works—not that it is fundamentally optimal or cannot be further improved. In the final version, we will clarify this point to prevent any potential misunderstanding or impression of overclaiming. We sincerely appreciate your constructive feedback, and please don’t hesitate to reach out if you have any further questions.", "claims_and_evidence": "Although the \"tightest\" confidence sequence is a bit \"over-claimed\" (without a concrete lower bound), the mathematical results themselves are very clear and correct.", "methods_and_evaluation_criteria": "N/A for this theoretical paper.", "theoretical_claims": "The results for both the computationally optimal algorithm and the statistically SOTA algorithm are well-supported by theorems and lemmas. The paper is well-written and easy to follow.", "experimental_designs_or_analyses": "The simulation results are consistent with the theoretical claims. The proposed algorithm even outperforms Thompson-sampling-based baselines in simulation even down to constant factors, which is surprising.", "relation_to_broader_scientific_literature": "The setting of multinomial bandits is well-motivated in operations research and well-established in the literature, either UCB based or posterior sampling based. The paper fits well in this line of research.\n\nThe techniques on mirror descent fits in the line of classic online convex optimization, which is also a well-established area.\n\nThe statistical techniques on the sharp confidence intervals for generlized linear models are recently developed, and the paper fits well in this line of research.", "essential_references_not_discussed": "No significant oversight.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- The online confidence sequence is claimed to be the \"tightest\", so could the authors provide some lower bounds on the width confidence radius itself, or at least some intuition on why couldn't we do better?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4EtSy0chof", "reviewer": "Reviewer_Zip2", "summary": "This paper enhances the regret bound for multinomial logistic bandits. The multinomial logistic bandit problem is a contextual bandit setting where each item is associated with a context vector, the player can select up to K items simultaneously, and the reward is determined probabilistically by a logistic model. Specifically, the reward distribution is governed by multiple logits, each computed as the inner product between an item’s context vector and a hidden environment vector. To maximize rewards, the player must simultaneously learn this hidden vector while selecting high-reward items. A common approach involves an optimistic strategy, which first constructs a confidence set that is likely to contain the hidden vector and then acts as if the best possible vector within this set is the true environment vector. This paper introduces a refined confidence set that is tighter than existing ones, leading to improved regret guarantees. The authors analyze the regret of playing with this confidence set and demonstrate that it achieves better regret bounds with reasonable computational cost, maintaining constant per-round complexity.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review! We are very pleased that the reviewer appreciates the significance of our technical contributions. In particular, we’re delighted that you found our proposed $\\ell_\\infty$-norm self-concordant property interesting. We hope this new property will inspire further research on MNL models, extending beyond the MNL bandit setting.\n\nPlease find our responses to your questions below:\n\n---\n### **Motivation and Applications**\n\nThe MNL bandit model offers a powerful and flexible framework for modeling choice behavior in sequential decision-making settings, where a decision-maker presents a subset of items (an assortment) and observes user selections based on relative utilities. This structure naturally arises in a wide range of real-world applications, making the study of MNL bandits both practically relevant and theoretically important. Some key domains include:\n\n- **E-commerce and Online Retail**: Platforms choose a subset of products to display to each customer. The customer's purchase behavior is naturally modeled using discrete choice models such as MNL.\n\n- **Recommender Systems**: Services like Netflix or Spotify present a small selection of items (e.g., movies or songs), and the user selects one. Modeling this behavior with an MNL model enables the system to learn user preferences and optimize engagement.\n\n- **Online Advertising**: Ad platforms select a set of ads to display, aiming to maximize click-through rate (CTR) or conversions. The MNL model captures how user choice probabilities depend on both the ad features and the composition of the ad set.\n\n- **Dynamic Pricing and Assortment Optimization**: Retailers dynamically select assortments subject to pricing or inventory constraints. The MNL model reflects how customer choices shift in response to changes in availability and pricing.\n\n- **Potential Application to RLHF**: The MNL bandit framework also has promising applications in Reinforcement Learning from Human Feedback (RLHF). Human preferences in RLHF are often modeled using BTL or Plackett-Luce (PL) models. Since MNL generalizes BTL to multi-choice settings and serves as a building block for PL (ranking models), it provides a natural and flexible foundation for modeling richer forms of preference feedback in RLHF.\n\nWe believe that the MNL bandit model provides not only a unifying theoretical framework but also a practically impactful tool for real-world sequential decision-making. We will consider expanding this motivation section in the final version. We sincerely appreciate the suggestion to highlight these broader applications.\n\n---\n### **Variance-dependent lower bound**\n\nAs discussed in Remark 4.7, our proposed algorithm achieves a regret upper bound that is nearly minimax optimal in both uniform and non-uniform reward settings, when compared to the worst-case (variance-independent) lower bounds established by Lee and Oh (2024). To the best of our knowledge, a formal variance-dependent lower bound has not yet been established for MNL bandits. The most closely related result is the instance-dependent lower bound (specifically, $\\kappa^\\star_t$-dependent) proposed by Lee and Oh (2024); see Proposition 1 in their paper. Here, $\\kappa^\\star_t$ is the variance of the optimal assortment $S^\\star_t$ under uniform rewards (see Appendix E.2 of our paper for further discussion), rather than the assortment $S_t$ selected by an algorithm.\n\nThus, whether a fully variance-dependent lower bound can be derived in the MNL bandit setting remains an open question. Very recently (less than three weeks ago), He and Gu (2025) [1] established the first variance-dependent lower bound for general variance sequences in linear contextual bandits [1]. Their techniques may be adaptable to the MNL setting, and we view this as an interesting direction for future research.\n\n[1] He, Jiafan, and Quanquan Gu. \"Variance-Dependent Regret Lower Bounds for Contextual Bandits.\" arXiv preprint arXiv:2503.12020 (2025).", "claims_and_evidence": "All of their claims are supported by theoretical proofs.", "methods_and_evaluation_criteria": "The proposed methods make sense.", "theoretical_claims": "The proofs of all the theorems appear to be correct, although I have not verified every detail. In the proof of Theorem 4.2, the observation that self-concordance holds with respect to the $\\ell_\\infty$ norm is particularly interesting, and the introduction of a novel intermediary term effectively completes the proof. The proof technique is non-trivial and highly insightful. Other theorems are also well-developed and thoroughly discussed.", "experimental_designs_or_analyses": "The experimental results are limited, as they only consider synthetic environments. However, given the theoretical nature of this work, this limitation is not a significant concern.", "relation_to_broader_scientific_literature": "I believe the proof technique could be applicable to other bandit settings.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "**Strengths**\n\n1.\tThis paper improves the regret bound for the Multinomial Logistic Bandit without increasing computational complexity.\n\n2.\tThe proof is not merely a combination of existing ideas but introduces novel techniques.\n\n**Weaknesses**\n\n1.\tThe paper would benefit from a more detailed discussion on the motivations and potential applications of the multinomial logistic bandit.\n\n2.\tIncluding discussions on real-world scenarios and experimental evaluations could further strengthen the paper.", "other_comments_or_suggestions": "None", "questions_for_authors": "1.\tCould you provide more applications where the multinomial logistic bandit can be utilized? Discussing real-world use cases would help strengthen the motivation for this work.\n\n2.\tIs there a known lower bound on the regret? Additionally, can you discuss whether the variance-dependent term has an optimal form?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper made solid contributions on improving the bounds. The paper is well-written, provides nice sketches and intuitions, and numerical experiments show the effectiveness of their methods.
Decision: Accept (poster)