Online (Multinomial) Logistic Bandit: Improved Regret and Constant Computation Cost
Authors: Yu-Jie Zhang
Masashi Sugiyama
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Logistic Bandit
Generalized Linear Bandit
Regret Bound
Computation Cost

Abstract: This paper investigates the logistic bandit problem, a variant of the generalized linear bandit model that utilizes a logistic model to depict the feedback from an action. While most existing research focuses on the binary logistic bandit problem, the multinomial case, which considers more than two possible feedback values, offers increased practical relevance and adaptability for use in complex decision-making problems such as reinforcement learning. In this paper, we provide an algorithm that enjoys both statistical and computational efficiency for the logistic bandit problem. In the binary case, our method improves the state-of-the-art binary logistic bandit method by reducing the per-round computation cost from $\mathcal{O}(\log T)$ to $\mathcal{O}(1)$ with respect to the time horizon $T$, while still preserving the minimax optimal guarantee up to logarithmic factors. In the multinomial case, with $K+1$ potential feedback values, our algorithm achieves an $\tilde{\mathcal{O}}(K\sqrt{T})$ regret bound with $\mathcal{O}(1)$ computational cost per round. The result not only improves the $\tilde{\mathcal{O}}(K\sqrt{\kappa T})$ bound for the best-known tractable algorithm—where the large constant $\kappa$ increases exponentially with the diameter of the parameter domain—but also reduces the $\mathcal{O}(T)$ computational complexity demanded by the previous method.

Online (Multinomial) Logistic Bandit: Improved Regret and Constant Computation Cost
Yu-Jie Zhang' Masashi Sugiyama??
1 The University of Tokyo, Chiba, Japan
2 RIKEN AIP, Tokyo, Japan
Abstract
This paper investigates the logistic bandit problem, a variant of the generalized linear bandit model that utilizes logistic model to depict the feedback from an action. While most existing research focuses on the binary logistic bandit problem, the multinomial case, which considers more than two possible feedback values, offers increased practical relevance and adaptability for use in complex decision- making problems such as reinforcement learning. In this paper, we provide an algorithm that enjoys both statistical and computational efficiency for the logistic bandit problem. In the binary case, our method improves the state-of-the off-the-art binary logistic bandit method by reducing the per-round computation cost from Olog T) to O(1) with respect to the time horizon T, while still preserving the minimax optimal guarantee up logarithmic factors. In the multinomial case, with K + 1 potential feedback values, our algorithm achieves Ō (T) regret bound with (1) computational cost per round. The result not only improves the Ö(K VET) bound for the best-known tractable Aggrittm-wwhee the large constant increases exponentially with the diameter of the parameter domain- but also reduces the (TT) computational complexity demanded by the previous method.
1 Introduction
The stochastic linear bandit (SLB) 2 3 problem is natural generalization of the classic stochastic multi-armed bandit problem 4 by incorporating side information into the decision maaiing process. In the SLB problem, a linear model is used to characterize the relationship between the reward r. E .R and the learner's action x, E X C IRd whereas such assumption is not always satisfied in real-world applications. Consequently, various models have been developed to account for the non-linear reward, including the generalized linear bandit (GLB) model [5] and kernelized bandit model (6). The logistic bandit is a specific kind of GLB model by connecting the learner's d- dimensional action and the reward with a logistic model. Most existing work focuses on the binary 10 The reward r. E {0, 1} exhibits a binary value and the probability is modeled x = o( xt), where (2) = 1/(1 + exp(-2)) is a non-linear link function and w, E W C IR an unknown parameter. Compared to the SLB model, the logistic bandit model provides more precise representation for a wide range of real-world application problems, where feedback exhibits discrete behavior. Moreover, from a theoretical perspective, it also serves as basic setting for understanding the impact of non-linearity of the reward on the decision decision-making process. In this paper, we investigate a more general multinomial logistic bandit (MLogB) problem (IT), in which the learner's 's action x, results in feedback yı that could have K + possible outcome values. each outcome is characterized with a logistic model (the formal definition is
case 7 g 9
by Pr
The probability provided in Section 2.1 The MLogB model is of more practical interest compared to the binary case. For example, in the real-world application such as online advertising, there could be multiple possible feedback from customers, including "buy now", "add cart", "view related item", and
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Comparison in terms of the regret bound, computation cost and storage cost. For the regret bound, the logarithmic dependence on the time horizon T' is hidden by the (-)) (-)-nnotaion, As for the computational cost (abbreviated as "Comput.") and storage cost, we only keep the dependence on the time step t. Notation =." denotes that the algorithm is intractable for implementation.
Setting
Algorithm
Regret
Comput. Round
Storage Cost
Improved x Constant Cost
LCgistic-UUB-I
O(viz)
(I))
(())
OFULog-r
((VTja)
O())
O(t)
binary
OFla)-OFU-EOOLog 10
((VTja.)
O(log ()
0(1)
x
OL2M 7 GLOC
Ö(KVT)
0(1)
((1)
OFU-MLogB (Corollary
O(VT)K.)
0(1)
O(1)
MNI.
Ö(KVOT)
00)
(())
multinomial
Improved MNL-UCB
0(177T7)
(()
OFUL MLoggB (Theorem
Ö(KVT)
0(1) ((1)
just leave without any click. Beyond addressing practical demands, studying the MLogB problem can shed light on other decision-making problems. For instance, in the theoretical reinforcement learning research 22 13 the transition matrix approximated using a linear model, which enables the application of the SLB method for balancing the exploration-expl exploitaatio trade-off. Since the transition matrix is inherently a probability matrix, the multinomial logistic model may be a more suitable structure for modeling transition probabilities between states.
As shown in T the logistic bandit problem has received much attention in the binary case. There are two main focuses arising from the non-linearity of the reward function: statistical efficiency and resource overhead. Regarding the statistical efficiency, a main focus is the algorithms' dependence on K = m WeE 1/o' x), a crucial parameter capturing the non-linearity of the reward function. Since the binary logistic bandit is special case of the generalized linear model, the result from 5 implies an ((eVT) bound. However, the parameter k: grows exponentially in terms of the diameter of the decision domain W and action space X, making the linear dependence unfavorable. A pivotal advancement is made by 191, where the paper presents an algorithm that achieves the nearly minimax optimal bound (Txx..... Here, K. = 1//'(ww,, x.) is the non non-linear parameter associated with the best action x. = arg x [w),,, x), suggesting that non-linearity might be advantageous for statistical efficiency, rather than hindrance. Alongside statistical efficiency considerations, the non-linearity of the feedback raises concerns about the algorithms' computation and storage efficiency, The methods 3 9 with improved dependence on x usually require storing and optimizing over all historical data to estimate the unknown parameter, leading to an (t)) computation and storage cost at round & E [7]. The pioneering work (7] provided the first efficient solution for binary logistic bandit with constant computation and storage costs and [14] further proposed an efficient algorithm for generalized linear bandit, but their regret bounds still exhibit a linear dependence on k. Recently, a jointly efficient algorithm was proposed by [10], which achieves the optimal dependence on K with a (log t) computation cost and constant storage cost per round. However, remains open whether the minimax optimal bound is achievable with constant computation cost independent of the time t.
Regrading the multinomial logistic bandit, the best-known feasible algorithm was proposed by (II). This method achieves an 5(K VKT') regret bound, bearing an ((VK) dependence on the exponen- tially large constant. Moreover, it still demands (tt) computation and storage costs to optimize over all past data. The same study also introduced an ((33/2/T) bound with improved dependence on Yet, this solution leans heavily towards theoretical insights and is intractable in implementation [I] Section 2.6]. Designing a practical or more efficient algorithm with improved dependence on is still an unsolved challenge. More discussions on the related work and topics can be found in Section
Our Results. In this paper, we provide algorithm with both statistical and computational efficiency.
For the multinomial logistic bandit, we propose OFUL-MLOGB, a jointly efficient method attaining an Ö(K regret bound with (11) in computation and storage cost per round. The result improves the previous work on the dependence of the large constant k.
For the binary case, our proposed OFUL-MLOGB can achieve the Ō(vT/ optimal bound up to logarithmic factors. Besides, our method reduces the computation cost of the state-of-the-ar binary method [10] from Ollog 1) to ((1) per round.

---

2 Multinomial Logistic Bandit with Improved Regret
This section provides preliminaries on the multinomial logistic bandit problem and optimistic al- gorithms, beginning with the problem formulation and notations. Then, we revisit the optimistic algorithms for the MLogB problem. Specifically, we investigate the previously best-known feasible algorithm, MNL-UCB algorithm [T] and propose an improved version with better dependence on the exponentially large constant a and the number of outcome values K.
2.1 Problem Formulation
The multinomial logistic bandit (MLogB) problem studies a T round decision-making process between the learner and the environment. At the beginning of the iteration the learner will first select an action X, E X' from the feasible action set X' C R and then submit it to the environment. After that, a response y/ E {0} [K] with K + 1 possible outcomes (like "buy now", "add to chart", or "do nothing") is returned based on the learner's choice, where K E N. Specifically, the MLogB problem assumes that each outcome & E [K] is associated with ground-truth parameter w!!) and the probability of the outcome Pr(ye = k xx] follows the logistic model,
(k) R
exp ((w!
)xx+
K
Pr[s- = k: xx]
and Pr[ye = 0 x1] = 1- Priye = k xt].
1 Σj= exp (w T
For notational simplicity, we denote by W. = (w)))
w W E Rxdd the matrix for the
unknown parameter and define the softmax function RK + [0. 1|i by
exp([z]<)
[z(2) 1+ E exp((z)))
for all & E [K] and [ar()]lo 1 E exp([z],)
(I)
where FI denotes the k-th entry of the input vector. Then, the probability of the outcome can also be written in concise way Pr(y: = k x,] jo (W.WWx))]k Besides, each outcome is associated with a fixed and known reward. We denote by E RR, the reward for the outcome k E [K], and let Po for the outcome 3/2 0. Therefore, the expected reward of the learner's action X, is defined as r(x.) = Ek- Pr(y: = x,] Pk = p o (W.x.). Let x., = arg maxxe. p (WWx)). The goal of the learner to maximize the cumulative reward, which is equivalent to minimizing the regret
T
Regr = Σ pT (o(.xx))oo(W.))))) (=1
(2)
When K = and = 1, MLogB recovers the binary logistic bandit by r(x) = o(w.xx = 1/(1 + (pppp.. x)), where w, E Rd a unknown parameter.
Exponentially Large Constant x. In the logistic bandit problem, the non-linearity of the reward function is captured by the gradient of the link function Vo E TRd di)g(a(z)) - (z) The analysis typically that requires that the gradient term is bounded from below and thus one would define the constant к 1/ m/miiwew.ee Amin (Vo(Wx)) such that LTa < Vo(Wx) for any W E W and X, where Amin R + R2* is the minimum eigenvalue of the input matrix. In the binary case (K = 1), one can show that x = maxwew.xex + exp(w x) + exp(- x)} = ((eSx), where S and X are the diameters of the parameter space W and action space X. In the multinomial case, the paper [I] Section 3] also shows that is exponentially large constant with respect to S and X. Thus, an algorithm with improved dependence on x is demanded.
2.2 Assumptions and Notations
Same as the previous work for multinomial logistic bandit [1], we use the following assumptions. Assumption 1. The norm of the action is bounded by 1, i... ||*||| S 1 for any x E X.
Assumption 2. The reward vector p E RRKK and its norm is bounded by R, i.e., ||p||2 R. Assumption 3. The norm the parameter W. E R Kxd bounded by S, i.e. | S S, where ||-l| denotes the Frobenius norm of a matrix.
3

---

Assumption 4. Let (z(z) E IR + - For all x E d' and W e W. we have Amin (Vx)
x 1/x and Amax (Va((x)) I L. where Amax R E and Amin : RRXK + IR K take the maximum and minimum eigenvalues of the input, respectively.
Other Notations. The following notations are used in the paper. Given a K-by-d matrix W, we denote by W its Kd-dimensional vectorization. For any positive semi-definite H E KddkK we define the norm |WIl V(W, HW). The notation @ is used for the standard Kronecker product.
When the input is vector W RKd, we treat it as a Kd 1 matrix. Moreover, for any symmetric matrix A, B E R Kdxx kd we denote by A + B that A - B is semi-positive definite matrix. We use F, = (x1, 91, ................................ 1. xx) to denote the filtration, which encodes the information collected so far before receiving V/- Finally, (()) is used to highlight the dependence on d. K, K. and T. With (() -notatinn, further hide the dependence the dimension d and logarithmic factors.
2.3 Optimistic Algorithm with Improved Bound
This part revisit the principle of optimism in the face of uncertainty (OFU) [5] and introduces an improved version of the MNL-UCB algorithm [1] with better dependence on K and K.
Optimism in the Face of Uncertainty. The OFU principle is fundamental paradigm for addressing the exploration-exploittiioo dilemma in bandits. At each iteration i, the algorithm selects the arm by the rule x, arg maxxex T (x), where (x(x) is an optimistic estimate of the true reward r(x) satisfying (x) 2 r(x) for all x E X. Based on the OFU rule, one can show that Regr S 2/_,(F(x4 rxx))), indicating that tighter optimistic estimate Fe will lead tighter regret bound. Therefore, designing a tight optimistic estimate Fe is essential for the OFU algorithm.
In the context of the logistic bandit, a common practice is to construct a confidence set C2 C R R which is supposed to contain the true parameter W. with high probability, As such, the learner can obtain the optimistic reward for each arm x E X' by Ti (x) arg max P or (Wx). A tighter confidence set will lead to tighter optimistic reward, and thus resulting a better regret bound.
Improved Concentration Set. Given the reward is generated by the multinomial logistic model, we can employ the maximum likelihood estimation (MLE) method learn the unknown parameter W.. Specifically, after observing the action- feedbback pairs {(x,, yz) )=)) one can train the model by
t-1
X (W) + 2
WALEE = arg min L (W) WERKxd
WIE.
(3)
where (WW) Σk= (v=- }} log (Wx))( is the multiclass logistic loss established over (x,, Bt) and X > 0 is the regularization parameter. Let W R'd be the vectorized parameter. We also define the gradient g: (W) and the Fisher information matrix H.(W) of the logistic loss by
g: (
VL and H((W) & XI + Vo s x,
where W E Kd is the vectorized parameter and Vo: + diag(a(z)) (Z) the first order derivative of the reward vector or (z). Then, we are ready to present our confidence set for the maximum likelihood estimator, which exhibits O(VK) improvement over that in M.
Theorem 1. Set the parameter X = OdK log(t/5)) with a certain & E (0, 1]. For each iteration t e [T), we define the confidence set
C( A
W WEW
(s)(WW) (WALE)
(W) $ {.(
where (,(6) = 4v Kd(1+ + 5) log (2(1+t/d) /8) = O(VdK logt) is the radius of the set and
W = (W E kxdd ||]|= < S). Then, we have Pr Pr[vt 2 1, W. C()))
2 21-6. 11-6. 8.
One advantage of the confidence set (4) is that radius (6) independent of the exponentially large constant k and thus is much tighter than the confident set constructed for the generalized

---

Algorithm MNL-UCB+
Input: regularization coefficient A, probability 8.
1: Initialize H1 ATaa and WALEE as any point W
2: for / := 1, do
3: Construct F; and select the arm by (5). Then, the learner receives yt-
4: Train the estimator W by (3) and construct the confidence set C++1
5:
end for
linear bandit [5]. whose radius exhibits linear dependence The r-independent set first
established by [8] for the binary logistic bandit problem and then adapted to multinomial setting by [T] with refined analysis the self-normalized martingale tail-inequality for multinomial noise.
Our confidence set is tighter than that in [TI by improving the radius from (o) O(K Vd t) to ()) ( /dk t). The improvement based on a slightly refined nelf-normalized tail- inequality for the multinomial case, whose formal description is provided in Appendix C.I.
Construction of Optimistic Reward. Based on the confidence set reward and select the arm for each iteration by
construct the optimistic
T (x) arg wax PT (Wx) and
X arg max (x))..
We have following guarantee for the algorithm based on the MIE 3 and the selection rule specified in and ( We summarize the algorithmic procedure in Algorithm
Theorem 2. Under the same conditions as Theorem 1 Let 8 E (0, 1]. Algorithm 7 ensures
Regr I O (min(dlog RKT, dK TVTT + Rdl K log T))
with probability at least when we set the parameter À = O(dK log(
Remark 1 (Improved dependence on K and k). Our method achieves the Ö(VKKT) and Ö(KTT) regret bounds for MLogB problem simultaneously. The first bound slightly improves the Ō(K guarantee of the MNL-UCB algorithm [11 by an O(VK) factor while the second one is independent of the exponentially large constant K in its leading term. An ŌKK² /T) bound also attained by [I]] However, their proposed method is intractable as its confidence set is established all minimal elements of partially Loewner-ordered set C6()) n [] Appendix DJ. The computation cost of identifying all minimal elements and projecting onto the proposed confidence set is prohibitive. Our solution free from such demands by using a different rule to construct the optimistic reward.
Jointly Efficient Algorithm
In this section, we introduce OFUL-MLogB, an algorithm with jointly computational and statistical efficiency for the MLogB problem. We will first discuss the efficiency concern of the existing methods in the literature and then introduce our algorithm, followed by technical highlight.
3.1 Efficiency Concerns
The algorithms for logistic bandit crucially rely on two components ensure the statistical efficiency: the MLE (3) and the optimistic rule (5) for constructing Tz. However, the implementation of both components could be inefficient by requiring O(t) computation cost per online iteration.
Computation and Storage Cost of Maximum Likelihood Estimation. For logistic bandit or even the generalized linear bandit problem 3 g II) MLE is widely used tool to learn the unknown parameter. To solve the optimization problem, the gradient-based method, e.g. the projected gradient descent [16), are usually applied. However, discussed in 110), the optimization of the MLE problem typically requires (t log(1/c) gradient step to achieve c-accuracy. Besides, the loss function L, is established on all historical data ((x,, y resulting in an (tt) gradient query complexity for each gradient step and (l) storage cost, and thus is inefficient.
Computation and Storage Cost of Optimistic Reward Construction. The construction of the optimistic reward 7, (x) requires to solve the optimization problem (5). However, the objective
5

---

Algorithm 2 OFUL-MLogg
Input: regularization coefficient A, probability 6, step size n,
1: Initialize 11 Alga and W as any point in W
2: for = 1,.... T do
3: Select the arm by X; = arg x i (x) and receive yr-
4: Update H, H, + V (W? @ x
5: Update the estimator o [+1 for the next iteration by (6)
6: Update H1+1 = H, + (o
++1 xx) @ xxx! and
7: Construct the optimistic reward by (x) = p o (W + + + and (x) as
8
8:
end for
function p a0 (Wx) non-concave and the decision domain (, non-convex, making the maximization problem (x(x) arg ec. p D'oo(W>) computationally challenging. In the binary case, the paper g proposed a convex relaxation of the confidence set Cx()), whereas the
relaxed confidence set is still established on all historical data, resulting in O time complexity and (t) storage cost at iteration The optimistic estimate construction in the previous work for multinomial logistci bandits [11 is computationally efficient without involving any optimization
problem solving. However, it will lead to inferior regret bound of Ö (VVTT)
In the binary case, the work 110 proposed a jointly efficient algorithm, which achieved nearly minimax optimal bound with Olog t) computation cost per iteration and (11) storage cost. However, as we will discuss in Section 3.3
hard to apply their analysis to the multinomial case.
3.2 Efficient Algorithm
In this section, we proposed novel algorithm which only requires O(1) computation cost per iteration and (11) storage cost. The algorithm can achieve the best known results both for binary and multinomial logistic bandits. We have introduced new ingredients both on the algorithm design and regret analysis to achieve the jointly efficient algorithm.
Efficient Online Estimation. Instead of performing MLE, we run an online mirror descent algorithm to estimate parameter:
WOL (+1
arg min( OL W)
1
V
WEW
21
where 77 > 0 is the step size to be specified later and the first iteration model W can be initialized
as any point in the domain W = ( E Rdd [ I S}. We set the matrix as Hg =
H, + Vo [W @ x,x,, where H, = AI + Σ f-1 be updated incrementally.
s=1 (W x1xx)) x.x_ Both H. and He can
We show the online estimator (6) enjoys computational. storage, and statistical efficiency. Since (6) exhibits standard online mirror descent formulation (17). can be solved with a single projected gradient step with the following equivalent formulation by
2 1+1 WoL nii, - (W
and
OL ++1
arg min ww W| - Z.H1ll..
For the gradient descent step above, the most time- operation is maintaining the inverse of the matrix He, Since (o, x.x is rank-K matrix, it can be calculated by the Sherman- Morrison- Woodbury
Morrison-ooddurry formula with (dd K3) cost per round. As for the projection step, since H, is
positive semi-definite matrix, it can be solved in O(K3 dd) [18] Section 4] As consequence, our algorithm achieves light update with ((1) cost per round. Regarding storage cost, our proposed estimator eliminates the need to store all historical data and updates in a one-pass fashion, requiring only (11) storage cost throughout the learning process. Moreover, the estimator is also statistically efficient. We can construct the following K- k-independent confidence set similar to that in Theorem
"In the high dimensional case, one can also employ Lemma 13 of 10 to perform the projection step, which ensures 1 error with (d log r) computation complexity per iteration.

---

Theorem 3. Let ò E (0,1) and a = 2(1 + S) + In(K + +1). Set the parameter a/2 and À max (axx22 TvBoS). For each iteration t E [T], we define the confidence set as
(8) - WeW New
| -ift--Wil Wln, S 80 (6) {
where ( (log K log tv /Kd). Then, we have Pr|Vt 1, W. E C((5) 2 Moreover, the computation cost of solving (6) is ((1) per round.
Remark 2 (Comparison with the online estimator [0O.. Our algorithm design is inspired by the online estimator [10] developed for the binary case, while achieving even lighter cost by novel algorithm ingredients and analysis. As discussed in Section [3.]] the analysis for the binary setting is hard to be applied the multinomial case. Specifically, the paper (IO) has proposed an intermediary decision W, in the analysis to prove the statistical efficiency of the proposed estimator. However, the favorable property of the intermediate decision only holds in the binary case. To this end, we have proposed new intermediary decisions, which not only help to prove the statistically efficient of our estimator but also eliminate the requirement of the exploration step. Besides, we have also introduced novel algorithm ingredient to further speed-up the algorithm. Instead of learning with original loss function as in [10]. by a more refined exploitation of the negative term in the analysis,
we show it is sufficient to learn with the first order approximate (W. W" of E (W) with the adjusted local norm ||- M. Our new algorithm not only enjoys a computation efficiency improvement from (log t) in [0]] to (1), but also is free from any exploration step required by the previous work. We provide a technical highlight in Section 3.3
Efficient Optimistic Reward Construction. Although the confidence set (6) is convex, the optimistic rule by (x) arg win p (Wx) still involves inefficient non-concave optimization problem solving. In this part, we propose novel optimistic reward that can be solved in a constant time per round.
Proposition 1. For any x E X and iteration E [T', the optimistic reward is constructed by (x) = pT or (" + et (x) + +e, (x).
(8)
In above, <t (x)((x)= = (g ||,, (TK @ Vo (Plx)))ll2 and and (x) = 3R (8 [( ?
x H, 1/2 are the bonus. Then, we have (x) 2 p (o.... for all t 2 1 and x E X' with probability at least 8.
Proposition constructs the optimistic reward by adding the "bonus" to the reward empirically estimated by Wit. Different from the term used in [1I, our bonus terms are independent of the exponentially large constant and thus can lead rule 88) does not involve any optimization problem solving and can be calculated in an ((1) cost.
improved Ö(K VT) bound. The optimistic
Overall Algorithm and Guarantees. We overall procedures in Algorithm 2 For the general multinomial setting, it ensures an Ö(K VT) regret guarantec and ((1) computation cost. Theorem 4. Under the same condition as Theorem 3 Algorithm ensures
Regr = O ( ldlog log K (log 2 + kK & &(og K)² (log T) = Ö(KVT).
The computation cost of Algorithm 2 bounded by O(1) for each round 1 [7].
Remark 3 (On the Ō( Ö(vT/K.) bound). In the binary setting,
9
TO
show that O(VT/K) R..)
minimax optimal achievable with K. = 1//o (w. x.). However, due to the multinomial behavior of the feedback, it is unclear how to achieve such rate in MLogB case (see the discussion in Appendix C.5). Besides, also raises concerns about efficiency when applying the method devel- oped for binary case to multinomial setting. In particular, the Ō (V/T/R.) is achieved by the rule arg maxxex (WC, o (ww" T x) in g [0]. The optimization can be efficiently solved in the binary case since one can simply eliminate the non- non-linearity of the reward function by the relationship (211) > (22) for any 21 E R > 22 E R. Such a condition does not hold in MLogB problem.
When reduced to the binary case K 1, our algorithm can also achieves the minimax regret bound. Corollary 1. When K = 1, the multinomial logistic bandit reduces to the binary logistic bandit problem. Then, under the same conditions as Theorem Algorithm 2 with the optimistic rule
4
Fx( arg (CX w x ensures Regr S 56 k..) with probability at least 1 8.
7

---

3.3 Analysis
This section presents the proof sketch for Theorem which plays an key role in the analysis for Algorithm 2
For notational simplicity, we will drop the superscript OL in this section.
Leveraging Negative Terms for Efficient Update. If update the model with the original loss function by W 1++1 = arg new (<W)) + ž I -Wxil's -Welli, the arguments in [00 shows that the
estimation error between W e+1 and W. can be bounded by their gap on the loss function
- 11i S Σ C(W.) Σ (Ws+))).
However, the update rule with original loss will lead to an (log computation cost per itera- tion. To facilitate more efficient algorithm, we introduce the update rule with the linearized loss (V&((W,) :), W) and the adjusted norm H. as 66. As we have shown in the proof of Lemma 12
in Appendix C.1 Denote by (WW) = (V& .), W) I Wn (W.)) the second-order surrogate of (W)). The efficient update rule will introduce additional term
Σ (Ve, s vē, (
W s+ W.).
We handle the additional term by the self-concordant property of the logistic loss and exploiting negative term ignored in the previous analysis. Since the logistic loss V function [9] Lemma 4], then Theorem of [19 indicates that the additional term can be bounded by
VellW .+1) vū, (W++),
VKS s+1 W W.IRRRe
where E, IR. Kd on the line connecting W 6+1 and W Besides, by refined analysis of the online mirror descent (OMD) update (6), we identify an additional negative term - -E | ++1 W 11? on the right hand side of (9). By properly choosing the coefficient one can cancel the additional term by the negative term and achieves (9) with the efficient update. We note that the negative term in the OMD analysis also found crucial in the gradient-variatio regret of non-stationary online learning 20 21
as well as its applications game theory [22] and the SEA model 23
Novel construction of the intermediary prediction. Then, we can further bound the right hand side of O by inserting an intermediary loss E, (WW)) as
(.W... Σ Ca +1)
Σ (W.) Σ (.W
Σ L.W.) Σ (W
term (A)
tern (B)
In the binary case, inspired by the study [2 for the binary online logistic regression, 10 propose (5,0) 0) + |w w where & the binary logistic loss and W, is a shrank decision domain. Then, both term (A) and term (B) can be bounded without the dependence on k. However, the analysis for term (B) crucially relies on the condition |a [W] x.) yol lo(w x.) - 1 1 ya = o' d'(w" x.) to eliminate the dependence on where ys [0, 1} is the micddimensional feedback. It is hard to show such an relationship in the multinomial case since the feedback y, has multiple value. A similar challenge is also observed in the recent study on online multiclass logistic regression (25 Appendix F]. One might consider whether
to construct w, arg min & fo(w" X,, +1) + ls (s(wT> x,,
is possible to construct W, with the update rule developed in [25]. However, since the online update rule of 25 requires to perform over R the learned parameter would become unbounded, which makes is hard to provide an upper bound for term (A).
To this end, we design a new intermediary term by (ā,,, Va). where l, is the multiclass logistic loss. The prediction is constructed by 2, = + (Ew~P, (W xx))) with the Gaussian distribution
P. =NWW sHHH, where o is a pseudo inverse function of the sigmoid function Such

---

an integral construction 2, ot (Bw~P, lo (Wx))) is previously used in the online logistic regression literature 27 but we tailored the tool to our analysis with different construction of the distribution P.. Lemma 13 and Lemma 14 in Appendix C.1 shows that
term (A) - (log K + log t) logt and term (B) S
W W W+till?,, + Kdl K logt,
Then, combining the upper bound of term (A) and term (B) and eliminating the additional term Ci=illW, -+1 ll2 with the negative term obtained by a refined analysis of online mirror descent, complete the proof of Theorem
4 More Discussions and Related Work
This section begins with a discussion on the tightness of the proposed bounds.
On the Tightness of Our Bounds. In this paper, we introduced OFUL-MLogB, a jointly efficient algorithm that simultaneously achieves regret bounds of ((VRKT) and D(KVT)) The tightness of these bounds. with respect to x and T, was detailed in Remark 3 Regarding the number of feedback values K, | claimed the optimality of a linear dependence on K. However, our findings revealed nuanced interplay between & and K. The Ó (VVrKT) bound does not conflict with the lower bound argument by .T given that the non-linear constant is also associated with K. Beyond k, the norm of the unknown parameter S and maximum norm of the reward vector p can also depend on K based on the problem's 's specifies. It is interesting direction understand the interrelation of these constants by establishing a lower bound. Additionally, our method has a lincar dependence on In the finite-arm case, an O(vi dd) dependence might be attainable with a SupLin-typp algorithm 28
Below, we introduce more related works on logistic bandit and the related topics.
Logistic Bandit. While the logistic bandit specific instance of the generalized linear bandit 31.32
33 (34,, the algorithms proposed for GLB tend to exhibit a linear dependence on the nonlinear term K. which is exponentially large in the logistic bandit case. Therefore, addressing the non-linearity of the reward function warrants specialized consideration. Besides the UCB- type algorithms [8] g mentioned in Section I for the N-arm case, [35] proposed an experimental design-based algorithm providing an O( log NT/K.) regret bound with better dependence on d. However, the previous methods were built upon the MLE estimator, whose optimization demands (l) computation and storage complexity for the /-th iteration. To the best of our knowledge, the only known jointly computational and statistical efficient algorithm was proposed by [10], which achieves a nearly minimax optimal regret bound with computation cost of O t) per round. In addition to the frequentist bounds, there are also researches on logistic bandit from the Bayesian view. 36 showed the Bayesian regret of the Thompson sampling method is independent of k (even in the lower order term) when the feasible domain is identical to the parameter domain, i.e., X' = W. (37 further proved the x-independent bound with weaker conditions.
model 5 29 30
32
Multinomial Logit (MNL) Bandit, Another relevant line of research is the multinomial logit 41 42), which generalizes the binary logistic bandit by allowing the learner to submit a subset of arms S. (xx, 1== E X' to the users. The expected reward
contextual bandit problem [88
39
40
function is also modeled by the multinomial logit model: E|rr [S.] = Ex,,es, Pt.i Pt,i exp [ x1,
Ex,,ES, exp(w, x), where Pt.; is the reward for arm Xt,; and w. E IRd is an unknown parameter. There are also studies on the MNL bandit problem concerning the exponentially large constant k. 42 proposed an optimistic algorithm with (dv/T) regret bounds without x in its leading term, which improves the O(dr bound with better dependence on Considering uniform reward, i.e., Pr.s = 1 for all t [T') and E [N], 43 further showed Ö(d/T/KR.) bound. To the best of our knowledge, all the existing methods with improved k are established on the MLE estimator. It would be an interesting future direction develop jointly efficient algorithm for the MNL bandit problem.
'Theorem 5 in Appendix C.3.2 shows that OFUL-MLogB also attains the Ō(vRKT) regret bound.

---

3017
Time (occonte
10-
Lagbeni
Beggest
Beggees
BlU-OUU OFU:Miogh
OFU-Mllagk
OFU-Moggh
Iteration
fteration
Iteratio
Algorithmms
(a) configuration
(b) configuration 2
(c) configuration 3
(d) total running time
Figure 1: Performance and computation cost comparison for binary logistic bandit.
and Loc
sec 1ith
Time (soronds
MNLLOSS OEU-N
Regrest
Regrest
Itentionn
Iteration
Berraion
Algorithums
(a) configuration
(b) configuration 2
(c) configuration 3
(d) total running time
Figure 2: Performance and computation cost comparison for multinomial logistic bandit.
5 Experiments
This section validates the statistical and computation efficiency of the proposed method by experi- ments. We conduct a bandit learning for 7 3000 iterations. In each experiment, we run experiments on 6 random configurations, in which the arm set and the underlying parameter randomly sampled. Specially, X = 20 actions are randomly sampled from a 2-dimensional sphere radius 1. In the binary case, the norm of the unknown parameter w. is set S = 5. In the multinomial case, we set K = with S = 1. The reward vector is set as p [0.25, 0.5, 0.75, 5, 1]. For each configuration, we report the averaged results over 10 trials. More details can be found in Appendix D
Experimental Results. Figure provides a comparison performance and computation costs the binary case. The algorithm C2LM 77]. which has constant computational cost per iteration, is used as a comparison baseline. Our algorithm demonstrates a time complexity akin to O2LM, affirming its computational efficiency. Compared to the state-of-the-ee binary logistic bandit algorithm ada-OFU-ECOLoG 100, our OFU-MLOgB method has lighter computational overheads while preserving similar empirical performance. Figure 4 illustrates the comparison in the multinomial setting. Our algorithm around 50 times faster than MNL-UCB [I]] for running T 3000 iterations and achieves better empirical performance. More experimental results other con gonftinuations and the running time curve that increases along the iterations can be found in Appendix D
6 Conclusion
This paper proposed a jointly efficient algorithm OFUL-MLogB for both binary and multinomial logistic bandit problems with constant computation cost per round and improved regret guarantees. For the multinomial setting, our method improves over the best-known feasible algorithm both on the dependence of and the computation cost. When reduced to the binary case, OFUL-MLogB also contributes to improve the computation cost of previous method from O(logt) to O(1) per round while still preserving the Ø( ((VT/K.. minimax optimal bound up to logarithmic factors. A promising future direction to consider the multinomial logit model in reinforcement learning. Besides, is still open on how to achieve the ((VT/R.. bound for the multinomial case.
Acknowledgments
YJZ and MS were supported by the Institute for Al and Beyond, UTokyo. YJZ was also supported by Todai Fellowship. The authors would thank Peng Zhao for helpful discussions and Jing Wang for the assistance in experiments.
10

---

References
[1] Peter Auer. Using confidence bounds for exploitation-exxloortion trade-ofTs. of Machine Learning Research, 3:397-422, 2002.
[2] Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In Proceedings of the 21st Annual Conference on Learning Theory (COLT), pages 355-366, 2008
[3] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24 (NeurIPS), pages 2312-2320, 2011.
[4] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235-22 2-62,55--6,600 2002.
[5] Sarah Filippi, Olivier Cappé, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems 23 (NeurIPS), pages 586-594, 2010.
[6] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 844-853, 2017.
[7] Lijun Zhang, Tianbao Yang, Rong Jin, Yichi Xiao, and Zhi-Hua Zhou. Online stochastic linear optimization under one-bit feedback. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pages 392-401 222-401,22 2016.
[8] Louis Faury, Marc Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. Proceedings of the 37th International Conference on Machine Learning (ICML), pages 3052-3060. PMLR, 2020.
[9] Marc Abeille, Louis Faury, and Clément Calauzènes. Instance-wise minimax-optimal algorithms for logistic bandits. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3691-3699, 2021.
[10] Louis Faury, Mare Abeille, Kwang-Sung Jun, and Clément Calauzènes. Jointly efficient and optimal algorithms for logistic bandits. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 546-580, 2022.
[11] Sanae Amani and Christos Thrampoulidis. CCCB-based algorithms for multinomial logistic regression bandits. In Advances in Neural Information P Processing Systems 34 (NeurIPS), 2021.
[12] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Proceedings of the 33rd Conference on Learning Theory (COLT), pages 2137-2143, 2020.
[13] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvári. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Proceedings of the 34th Conference on Learning Theory (COL.T), pages 4532-45766 2021.
[14] Kwang-Sung Jun, Aniruddha Bhargava, Robert D. Nowak, and Rebecca Willett. Scalable generalized linear bandits: Online computation and hashing. In Advances in Neural Information Processing Systems 30 (NeurIPS), pages 99-109, 2017.
[15] Tor Lattimore and Csaba Szepesvári. Bandit Algorithuns. Cambridge University Press, 2020.
[16] Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimiza- tion, 2(3-4):157-325, 2016.
[17] Francesco Orabona. 1912.13213, 2019.
A modern introduction to online learning. ArXiv preprint, arXiv:
[18] Zakaria Mhammedi, Wouter M. Koolen, and Tim van Erven. Lipschitz adaptivity with multiple learning rates in online learning. In Proceedings of the 32nd Annual Conference on Learning Theory (COLT), pages 2490-2511 2511, 2019.
[19] Quoe Tran-Dinh, Yen-Huan Li, and Volkan Cevher. Composite convex minimization involving self-conccrdanttllke cost functions. In Proceedings of the 3rd International Conference on Modelling, Computation and Optimization Information Systems and Management Sciences, pages 155-168, 2015.
11

---

[20] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zui-Hua Zhou. Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 12510-12520, 2020.
[21] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zui-Hua Zhou. Adaptivity and non- stationarity: mroblem-dependee dynamic regret for online convex optimization. ArXiv preprint, arXiv:2112.44688, 2021.
[22] Mengxiao Zhang, Peng Zhao, Haipeng Luo, and Zhi-Hua Zhou. No-regret learning in time- varying zero-sum games. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 26772-26808. 2022.
[23] Sijia Chen, Wei-Wei Tu, Peng Zhao, and Lijun Zhang. Optimistic online mirror descent for bridging stochastic and adversarial online convex optimization. In Proceedings of the 40th International Conference Machine Learning (ICML), pages 5002-5035, 2023.
[24] Rémi Jézéquel, Pierre Gaillard, and Alessandro Rudi. Efficient improper learning for online logistic regression. In Proceedings of the 33rd Conference on Learning Theory (COLT), pages 2085-2108, 2020.
[25] Naman Agarwal, Satyen Kale, and Julian Zimmert. Efficient methods for online multiclass logistic regression. In Proceedings of International Conference on Algorithmic Learning Theory (AL.T), pages 3-33, 2022.
[26] Dylan J. Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan. Logistic regression: The importance of being improper. In Proceedings of the 31st Conference On Learning Theory (COLT), pages 167-208, 2018.
[27] Rémi Jézéquel, Pierre Gaillard, and Alessandro Rudi. Mixability made efficient: Fast online multiclass logistic regression. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages
2021.
[28] Wei Chu, Lihong Li, Lev Reyzin, and Robert E. Schapire. Contextual bandits with linear payoff functions. In Proceedings the 14th International Conference Artificial Intelligence and Statistics (AISTATS), pages 208-214, 20,-214,2011 2011.
[29] Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In Proceedings of the 34th International Conference on Machine Learning (ICML). pages 2071-2080, 2017.
[30] Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems 26 (NeurIPS), pages 2256- 2264, 2013.
[31] Daniel Russo and Benjamin Van Roy. Learning to optimize via information-direeted sampling. In Advances in Neural Information Processing Systems 27 (NeurIPS), pages 1583-1591, 2014.
[32] Mare Abeille and Alessandro Lazaric. Linear Thompson sampling revisited. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pages
176-184, 2017.
[33] Branislav Kveton, Manzil Zaheer, Csaba Szepesvári, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2066-2076 2020.
[34] Peng Zhao, Lijun Zhang, Yuan Jiang, and Zhi-Hua Zhou A simple approach for non- non-stationary linear bandits. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 746-755, 2020.
[35] Blake Mason, Kwang-Sung Jun, and Lalit Jain. An experimental design approach for regret minimization in logistic bandits. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI). pages 7736-7743, 2022.
[36] Shi Dong, Tengyu Ma, and Benjamin Van Roy. On the performance of thompson sampling on logistic bandits. In Proceedings of the 32nd Annual Conference on Learning Theory (COLT), pages 1158-1160. 2019.
[37] Gergely Neu, Iuliaa Olkhovskaia, Matteo Papini, and Ludovic Schwartz. Lifting the information ratio: An information- theoretic analysis of thompson sampling for contextual bandits. In Advances in Neural Information Processing Systems 36 (NeurIPS), 2022.
12

---

[38] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the mul-bandit, In Proceedings of the 30th Annual Conference on Learning Theory (COLT), pages 76-78, 2017.
[39] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Mnl-bandit: A dynamic learning approach assortment selection. Operations Research, 67(5):1453-1485 2019.
[40] Min-hwan Oh and Garud Iyengar. Thompson sampling for multinomial logit contextual bandits. In Advances in Neural Information Processing Systems 32 (NeurIPS), pages 3145-3155, 2019.
[41] Wang Chi Cheung and David Simchi-Levi, Thompson sampling for online personalized assortment optimization problems with multinomial logit choice models, Available at SSRN 3075658, 2017.
[42] Priyank Agrawal, Theja Tulabandhula, and Vashist Avadhanula. A tractable online learning algorithm for the multinomial logit contextual bandit. European Journal of Operational Research, 2023.
[43] Noémic Périvier and Vineet Goyal. Dynamic pricing and assortment under contextual MNL demand. In Advances Neural Information Processing Systems 36 (NeurIPS), 2022.
[44] Yurii E. Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms convex programming. STAM, 1994.
[45] Francis Bach. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4:384-414, 2010.
[46] Tianxiao Sun and Quoc Tran-Dinh: Generalized celf-coneordant functions: recipe for newton-
type methods. Mathematical Programming, 178(1):145-21 2019.
[47] Yasin Abhasi-Yadkori, Dávid Pál, and Csaba Szepesvári. mnline-to-comfidenc-sst conversions and application sparse stochastic bandits. In Proceedings of the 15th International Conference
on Artificial Intelligence and Statistics (AISTATS), pages 1-9, 2012.
[48] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[49] Nicolò Campolongo and Francesco Orabona. Temporal variability in implicit online learning. In Advances in Neural Information Processing Systems 33 (NeurlPS), 2020.
13

---

A Properties of the Logistic Regression
This section collects several key properties of the logistic loss used throughout the paper.
A.1 Multiclass Logistic Loss
We have the following property of the multiclass logistic loss.
Property 1. Let y E Y with y {0} [K] and RK x y be the multiclass logistic loss defined by
K
((2. v) = Σn ity= = kj log [o]))] )
(10)
k=0
where RRK - 10 K is the vector valued link function defined by [o] = E exp(z))) and (or (z)]o exp(zx)/(1 Σx= exp(z;)). Let y [ (y 1),..., 1
KH E R and Øz(z) = (o(z)) the k-th entry of (z). Then the first, second and third derivations w.r.t. the first argument of the loss function can be wrillen
V=((z,8) (z) y, V)l(z,) diag(o((z) (Z2)o((2)
Vell,))lu Σ (2) (20(2))o(z) -diag(o(z)) (L) oz)ee Fx))
where us is the k--th entry of the vector E R and Eg E R a "one-hot" matrix whose (k, k)-th entry equals to I while others equaling to O. Besides, is the one-hot vector whose k-th entry equals to 1. In the above, Val(z, y)(u] lim t- [V2 (V2 + tu, y) ( y)).
When we train linear model with the logistic regression loss, we can calculate its gradient and Hessian as follows.
Property 2. Denote by the logistic loss defined over the data point (x ve) x y by
((W) = E(Wx, v) = Σ El = k3 log (1)))
(11)
Then, the gradient (e,(W) E Rd and the Hessian (22 E Kdxkd of the loss function with respective to the vectorized model W is given by
(e,(W) = (WW)) yı) xx and VWG(W)- (Wxx)) oW & xxx]
Besides, we can obtain the gradient of the vector-valued link function as follows.
Property Let the sigmoid function o R + 1 be defined and oz denote the k-th entry of (z). We have
(z) = (z) (ck oz());
22 = (z) (z) diag(o(z)) - CL) - + Ex),
In above, Es E K is an all zero matrix except that its (k, k) entry is 1. For the first order derivation, we can write into more concise formulation by the notation Vo(z) .R g k
Öz Oz
V
diag(ar -2))
We have the following lemma for the logistic loss function. Lemma 1. Let C E [|C y E (0) [K] and RK Then, we have
((a, 3) 2 {(,, v) + Vi(b, 3) T(a b) + log K + +1 2(C +1) (a T² (a -b).
14

---

Proof. Lemma 1 is essentially the Lemma 4 of [27] with a slightly different definition of the logistic loss. The K 1-class logistic loss used by 27 is defined as (( v) Σ 1
}} log (E == exp(()))) (xp(( (]))) where ū I k+ is K - 1-dimensional input. One can connect the two logistic losses by E((z; 0], y) = {(z, v). Then, we can prove Lemma by directly
applying Lemma 4 of 27 with the augmented vectors ä aa: 0] and = [b; 0j.
L
A.2 Self-concordant--ike Function
Then, introduce the notion of self-concordant-like function, which generalizes the standard self- concordant notion. The celf-connordant function is first introduced by [4] in the study of inner- algorithm and the notion is further generalized by the following work 45] Newton-step methods. The self-concordant function enjoys several nice properties, which plays an important role our local analysis. comprehensive study for self-concordance function provided by [46. Here, we present the definition and necessary lemmas for our analysis.
for analyzing the
Definition (Theorem 3 of (9).. ). A convex function E C3
Rd >>
is M-self-cononn self--connordan--likk
and only if for any x; U1, U2 U3 Rd. we have
(D)((z)(u))u us) - M un ||2|||/ /2//2//|111 l
where ||u||2 == Vu V2 fz)u the local norm over the Hessian (²((z).
The logistic loss vf-self-conccrdaat-ikk function.
Lemma (Lemma 4 of 19 The logistic loss defined as is
The seff-concordant function enjoys favorable properties, which help conduct local analysis for the logistic bandit problem. We list useful lemmas as follows.
Lemma (Bound of Hessian Map. Theorem 4(b) of [9). Let e: Rd IR an M M-self-concordant- like function. Then, for any 21, E dom((f) we huve
M zall ((z))) & V²((z2) & M =
(12)
The following lemma is a consequence of the bound of the Hessian map.
Lemma 4 (Corollary of (46)). Let é: Rd + be an M www..fffoncrdaant-iiiii fine Then, for any 21, Zg dom(E), é), we have
1 e- M zalla
(i((z)) & / Vil(zz + +1(22 z1))dr
M [a] =2212
{(z))
M z z2
M Z1 z2/12
We can also have the bound on the function value of the self-concordant functions.
Lemma 5 (Proposition 10 of (46). Let l Rdd RR. be --sseff-ommcrrdant-iic function. Then, for any Z1, E dem()), we have
c(-M [|] 102 12 ||z - 211,2, S {((z)) f(z)) v[(z)) -z1) S c(Myllz) - z2l12) 1112 zz 21lla,
where c: R + R is the coefficient function defined as c(x) (e* 1)/2².
B Omitted Proofs for Section 2.3
B.1 Proof of Theorem 1
This section we present the proof of Theorem
B.I.1
Main Proof
Before introducing the main proof, we introduce a key lemma on an improved self-normalized martingale tail inequality for the multinomial noise, which helps to save an O(VK) factor compared to the one obtained by [II. The proof of Lemma is provided in Appendix B.1.2
15

---

Lemma 6. Let (Fili=1 be a filtration. Let {x be a stochastic process in (2(d) fx E Rd ||x,ll2 S }} such that x is Fr measurable. Let (Et)== be martingale difference sequence such that Et E RK is Fi+1 measurable. Furthermore, assume that conditional on Ft. we have ||e||| S 2 almost surely, and denoted by E, - Elere Ft.. Let X and for any t 2 1 define
A-1
S. =
Σ
E, 2 Xs and H, = Alaa + Σ
E. 8 xxx,
Then for any E (0, 11, we have
H2,11/2 82K4/2
Pr t > 1, 1 4
log
(2) 86.
Lemma 6 is counterpart of the variance-aware self-normalized tail inequality g Theorem 1] for the multinominal case. In comparison with the previously established result by [1]. our inequality more effectively leverages the geometric structure of the noise in the multinomial logistic bandit problem, as indicated by the condition ||==|]| < 2. The previous paper's 's condition, ||æx|22 S vK, relatively loose, ultimately resulting an additional O(VK) term in the concentration inequality. Then, we introduce the main proof of Theorem !
Proof of Theorem 7
The optimality of the MLE estimator indicates that ge (WILE)
V.
0. such a case, we have
1-1 y 0x ox) AF
1-1
ge ( - (W.) = gg:( = Σ
Σ
E, X xx - A'
where E, = -W. -y the noise with bounded Loo norm as we have l1calloo $ (lo(Wxxs)loo lo 2. Then, bound the gap between WALE and W. by
|| (W, - (W.)ll,, P(W.)
+ +IIAW. .ll, '(W.)
E X2
H, ((W)
+ VXS
Ex
X
H, ((W.)
V
1/2
log
+
Kdllg(() + VAs, (13) VX
VX
0XKd/2
with probability at least 1 - 8 for all 2 1. In above, the matrix H.(W.) is defined as H.W..) =
XKa + E E(W. x, x) The first inequality is due to the relationship H, (W.) < 1/X Ixa- The last inequality is by Lemma since
Σ(W.x,) = diag(o(W.x.)) - (W.,,))o =E(E,E] [Fs1))
Then, we can bound the determinate of H,(W.) by
Tr(H.)
Kd
AKd+ - 1-1 K
En ( (W, X
Kd
Hel
{1+t//d)kd (14)
(A
Kd
Kd
Plugging
14 into
13 we have
(++ V
(1 1
2Kd
t
4Kd
2
Ig (W; (. ( (W.)
log
1+
+
log
(15)
VX
Ad
VX
By setting
4Kdlog(2 (1 + +t/d) 18) (dK log(1/6)),
(16)
111
we have
|g (W.LE) - B:(WW))l (WW.)ll,,((w.)) S bela, (8) 2 4 Kd(1 S) log (/d)))))8)
which completes the proof.
16

---

B.1.2 Useful Lemmas
Lemma 6. Let (F be a filtration. Let {x be stochastic process in (2(d) fx E R" [|xe|le 2 S 1 such that X is Fs measurable. Let {Et) 1 be martingale difference sequence such that Et E R& is Fet1 measurable. Furthermore, assume that conditional Fr, we have ||e/]1 S almost surely, and denoted by Et - E Fi]. Let and for any 2 1 define
S.
E
00 x, and H, Alka + Σ x
Then for any 5 E (0, 11. we have
VA 4
|2/11/2 8XKd/2
4
3 > 1, | | W. Pr
2
log
Kdlog(2)
VX
VA
Proof of Lemma The proof follows the pipeline the analysis of the self celf-normalized tail inlluaityylttyy
the previous studies
Letting H, Σ.= F. 6 x,x! we define the function
M.(E) - exp(E T S. | R.
for any t 2 and RRR, Rd. For Fort=00 0, let ME(E) 0.
By Lemma 7 in Appendix B.1.2. we can show that { (M, is non-negative super-martingale for any & E 1 B2 (kd). We note that our Lemma 7 is an imporved version of Lemma 7 in [11, which relaxs restriction
the feasible domain of from & vे B2(d) to g E B2 resulting in
saving O(v K)) factor in the bound.
Then, let (E) be a probability density with support on (B and define
[{ MI(E)dM(E)
M₁ A
exp(E S. -
||E - dh((E)
for all 2 1. Lemma 20.3 of [15] shows that M, is also a non-negative super-martingale and [[Ma] = 1. Then, the maximal inequality (Theorem 3.9 of (15) shows that
sup log(M.) log ) = sup M, LINN
Pr
5.
(17)
LIEN
Next, we turn to exam the formulation of M, and subsequently establish a connection with the we aim to bound, 11 Hr Let h(E) be the density of an isotropic normal distribution with precision
matrix 2A/Ka truncated on } (Kd)) and N (h) be its normalization constant. Furthermore, let g(E) be the density of the normal distribution with precision matrix 2H, that is truncated on the ball (Kd). Following the arguments the proof [8] Theorem I] (more precisely the arguments in deriving (11) in (8), for any t 1, one show that
N(g)
M, 2 exp(E" T S, - [IE))
N(h)
for any & E (Kd)). Let Eo A H. St
||
Vx
One can check ||
S vx
1
Vx < 1/4. Then, we
can further have
N N(h)
VĀ
X
((g)
log(M (M, 2 5o S,
|1lll + log
|
+ log
(18)
16
N(h))
Combining (17 and (8). for any / 1, we have
X
4
((h)
Pr
S |
<
log
21-6.
3N(g)
We complete the proof with Lemma of 8 such that
((h)
[H,
log
< log
Kd// + Kdlog(2).
[N()
17

---

Lemma 7. For all & E (K())) the sequence (M) is non-negative super-martingale.
Proof of Lemma prove 1 6) have
To show that (M, a non-negative super-martingal it is sufficient to Fi) I Mc(E) for any > 1 and & E (dd). By the definition of (E), we
B[M++ (E) [T] E eep(( T S441 || He+1 1 Ft
[exple (E. 8 xx) - < (E, @ x,X; ]5) F.] Mc(5)
E [exple; (Ix @ x, ) - - (E, @ x,x, ) Fi]
Mc(5).
(19)
Let 5 = :.:: : and & E Rd is the vector containing (I: 1)d + 1-th to kd-th elements of g. We further check that
l,, (IK @ x Del S ||ell1 [[(T @ x, El ||=x||1
max kEK
E x S 1.
where the first inequality is due to the Höler's inequality. The last inequality is by the condition
||=|]] I 2 and ||&x $ ||El|2 I 1/2 for any & E [K]. Then, we can further bound the expectation
term in 19 by
E [ _ (4x @ x, ) -
(2, @ x )6) Fi]
E lexp(e (Ix @ x ]k] Fi exp(- & (E, @ xxxx }
S exp(E T (Ix x [ x )E) exp(- E (E, xxx!] )E)
= exp(E T (E, @ x ) exp( 5 (E, @ x,x, ) 1,
where the first inequality is due to Lemma 8 and the last equality is due to mixed-produre property of the Kronecker product. Therefore, we can show E[M (E) Fi] S (E and complete the proof.
Lemma (Lemma of [I]). Let R.K be a zero-mean random vector with covariance matrix Σ. Then, for any vector a E RK such that E [Tal I 1, we have E[exp(s [a)] S exp(a Ea).
B.2
Proof of Theorem
This section provides the proof for Theorem
2
B.2.1
Main Proof
Proof of Theorem 2 We prove the proposed algorithm can achieve O(dlogTVnKT] and OdK log TVT + nd K2 22 log²T) bounds simultaneously. Before presenting the proofs, we in- troduce matrix that measures the local curvature of the loss function and will be used in the rest part of the proof:
A(x, W2, =
Vo (1 W2x)der
(20)
0=
1-1
G.(W1, W2) = Alka+
Σ
A(xs, W,, W2) 2 X
(21)
Analysis for the Odd I VRKT)
Bound.
The regret can be bounded by
T
T
Regr Σ
p TTo (W.x))
Σ (W,xs)
t=1
<
Σ
p (W.OPTx xx)
Σ pt a (W.x))
T
Σ
p A(x,, W.,
W.)x,
1=1
18

---

Il. ll(w w.))x W.,,
ell2 [1( Wx. (V.xxellA(xx,,W..
S R (w W, W...xellaax......o
In the above, the term A(x,, W., W is defined as 20 and the first inequality is a consequence of the optimistic rule ( such that (x,, W = arg max (8) p "a(WWx x) and the first equality due to the mean value theorem for the vector valued function. The second inequality is due the Cauchy-Schwar inequality and we can obtain the the last second inequality by the fact Vo * Tx for any z E K.K. The last inequality due to Assumption 2
Let Ge 2 (W1, W2) be defined as 21 We can proceed to handle the gap between W and W. by
[W.PT W. -W))W: (...)xXlAAXx....W.
[[WWPPT W.)xxll2
Σ [Ix xxx) (WerT W-)l2
Σ [[ 2 x 10, (W., woeT) G (W., ( W-)ll2
[1 2 x J0, (W., ) | (W., W.orT) ) W.)lla
[[x & x VV, ll |I (W., _ W W. .112
mm1
T [T @ v
G (W., worr) W .)12.
(22)
tezu (a)
tern (b)
where the first inequality is due to the fact A(x,, W., WrPT) * I and the second inequality is due to the Cauchy-Schwarz inequality. Since both W., WPPT E W, the third inequality by the condition
G.,,, WPFT) > V. A AT + 1 - Tx @ x, We can show the last inequality by using Sauchy-Schwarz inequality again.
Then, proceed bound term (a) and term (b) respectively.
[Txx @ xT), 1 112
term (a)
t=1
T
Amax Xmxx((Ux 8x]]V, (Ix @ xx))
1-1 [ Ald + k
-xxx]] ))
Amax(U1F 8 xJ)
(lx xx))
19

---

T
1 1
Amax
IK xx
(Ale
Σ
X
X
T
t-1
Σ Xi
Nld
+
Σ
X,XX
Xt
t=1
==1
T KAd
Rd log
1
(23)
In above, we denote by Amax the maximum eigenvalue of the input matrix. The second inequality is due the property of the maximum eigenvalue such that Amax (amx(ACC) Amax (BCA) for matrix A, B and C. The last second equality is due to the mixed product property of the the Kronecker product and (A & B)-1 A & B for matrix A and B. In the last inequality, we can bound the term with the standard arguments of the elliptical potential lemma
3 Lemma 11].
It remains to bound term (b). Since Theorem I shows that W. E C,) with probability at least 1 d for all > 1 and the optimistic rule (5) ensures W E (6), Lemma 9 in Appendix B.2.2 indicates that the distance between W, and Wreer can be bounded by
||G (W.. W.TT)
W. >ll2 s 2 (6).
Then, plugging the above displayed equation into term (b), we can bound this term by
T
term (b) < 211+22 2S
Σ 2 (1++5))3,;00) = 0 a logg/))))T/))
where the last inequality holds because (5( is a non-decreasing function with respect to t. A combination of the upper bound for term (a) and term (b) leads
2(1 + T/d)
loog (1+ T) (MddlogTVnKY
Regr S <8(1+ 25)+ RKT log
Analysis for the OlKllo TVT + kKd log T) Bound. Inspired by the analysis for binary logistic bandit problem [9] Appendix CJ. we employ different decomposition compared to the one used in the first part of the analysis
Regr
pa (ox -
( xx) (W.x())
T
K
Pk (W.x,) (WWPT -W,)x, +
Pull - W. W.)xx11. 12...
Pk Vox (Wxx.)) (W:PTT W=)x
Pall(WoPT - W. W.)x( E
tern
tern (d)
where oF + (x)] is the k-th output of the vector-valued function (x) and Ex, = f: V + p(W W.))x, ))))))x)d. In the above, the first inequality is due to the optimistic rule (5) and the last equality is due the integral formulation of the Taylor series. Then, we proceed to handle term (c) and term (d) respectively.
As for term (c), we have
T
term (c) = Σ (W..)) ((W.PT W.)x,
20

---

(Vo(W.x)) 8 & w.)
[Vo(W.,s) 8 (4x GoT (W,, W,rt) G. (W,, W )( w.)
WOPT
W Wwllo, ||, (W., W. (Ix @ Vo.V
1=1
S
2 (8)
Σ G (W (I) Vo)))((W.))))ll
(24)
where the first inequality holds by Cauchy-Schward inequality and the last one due to Lemma
Let Amax (.) denote the maximum eigenvalue of the matrix. We can further bound 24 by
Σ G2 b (W,, (Ix [x)
Vot 2 (W, xl)ll ||G (W.. (I @ Vor
Amax (Vot((.x)) 2 xx]])))))))))))) (V 0xx)
R
Ammax (Vo &
xxxx)) (VV[V.x))xxx (?r,
R
T Amax
< RVT
(Vo & x Gr, (W., " Woer)
S RVV (1 + KdIn
1+ 2A
(25)
where the first inequality is due to the fact that ||/b|]2 S ||||2 ||b]| for matrix A and vector b. The second inequality is due to the definition of the induced norm || / Amaax A) and the mixed- mixeedproducct property the Kronecker production. The last equality is due to the cycle property of the maximum eigenvalue such that (ABC( Amax (CAB) for matrices A, B and C and use the mixed-prode -rxeuctroduuct property again. The last inequality is due to Lemma 10 in Appendix B.2.2
Combining
24 and 25
we arrive
T log 2(1 2(1+)/d) log (1+
T
term (c) < 8/( + 2 VT
O(d log TVT). (26)
2d
Then, turn handle term (d). Lemma 11 indicates that
E = [ (1 - v)V + uWWorT W. W.))x;)dv x 3Ik
(1 - v)du =x  3lx. (27)
As a consequence, we can bound term (d) by
term (d)
Pk (W:PP - W. W..x
t=1
T
<3
- W.)x
21

---

I 3R
[(WPPPT w.)x:112
I (0)
E
[lk @ 8x, vV $12
T
1
kAd
where the first inequality is due Assumption and the second inequality is due 27 The last second inequality can be obtained by a similar argument in obtaining (22) obtained by the same argument (23)
The last inequality can be
Combining (26 and 26 we obtain
2(1+ Q(1+T/d)
Regr S 88R(1+ + 25) dk / T log
/
log 1 +
6
2d
2(1 + T/d)
T
+ +-88R11 SS log
loog
1
8
2d
O(d log TVT + kdl K log T).
We have completed the proof.
B.2.2 Useful Lemma
This section provides the lemmas used in the main proof.
Lemma 9. IfW. E Cr(8), then for all W E (o):
|[G (W., W W. .))ll2 S 221
where Be(5) 4 Kd(1 + log (2 t/d) /5) O (lvak logt) is defined in Theorem /
Proof of Lemma
Lemma in I| shows that
ge (W B: B.(W) G. WW -W),
for any W C,()). Then, we have
|I. (W., W W ll2
lls.(W".) .) gr (W) (W)loo (w..W)
[l..(W..) -g (W lll. (W..w) (l)
MLE (:(WE (
)lo,, (W..W)
< v + 25 [lg:(W". (W.)
MLL (w.) + (l:: - g: MLE (w)
2 (5)
where the last second inequality due to generalized self-concordant properties of the logistic loss as shown by Lemma 13 of [1I]. The last inequality is due to Theorem T and the condition that W is contained in the confidence set C,))).
Lemma 10. When the regalarization parameter
have
T
Amax
((Vo(W.x.) ).,
x (W., WrPT)) < <1+225)kdl
1+
T 2x
Proof of Lemma 10
Denoting by Tr(A) the trace of matrix A, We have
T
Amax (Vo
x,x x
W.PT)
22

---

r
To simplify the notation, exclude the (VVVV((W.))))xx// (W., W.(rT)
$
T
Σ Tr (Vo( @ xxx HH (W.)):
- (1 25)
where the last inequality is due to Lemma 4 of such that (1 - 2 W.PT) & H.(W.).
Let M,(W.)= = IKa + E Vo(W.x..) @ x.x. Then, we can further bound the last line of the above displayed equations by
Σ Tr Th (Vo((..x))xxxxx
(1 2S)
T
25)
Σ
Tr (M,(W.) M,- (W.) (WW))
(W.))
t=1
T
& (1+ + 25)
Σ
Tr (M.(W)) - -W. (W.)
1=1
T
I.M(WW)]
< (1 + 25)
Σ
log
(M-))(W.)
1=1
T
$ (1 + 25)KdIn
1+
2A
The first inequality is by the fact HW.)) > M,W.) under the condition À 2 2. The last second inequality is due Lemma 4.5 of 16
Lemma 11. Let ak z (x)) E RR by the k-th output of the vector-valued fintorovalueeeennntoon (z). Then, for any E R we have V2
31K for any k E [K].
Proof of Lemma 11 For any z E RKK we have
3Ix (z)x(z)
=3Ik + (z(z). (diag(o((z)) + + 20x (z) (z(z)),
> 3IK - (zz (zz + tz(ze Es)
(28)
= =3IK (z) - azx(z((((z)
(z) - -e)] > 0
(29)
where we denote by Eg as the matrix where the entry at the (k, k-)tth position is 1, and other entries are O. In the above, the first inequality is due to the definition of ag. The second inequality holds since di)g(or()) semi-positive defined matrix. The last inequality a consequence of the fact that the maximum eigenvalue of (z) (z) is bounded by ox (z) cx) (z) -ck) T is less than 1. The maximum eigenvalue of a% (z) (x)(O(z) ex) is bounded by 2.
C Omitted Proofs for Section 3
This section presents the omitted details for Section superscript OL in all the proofs within this section.
C.1 Proof of Theorem
This section provides the proof of Theorem 3 We will first provide the main proof of Theorem S and the prove the technical lemma used in the main proof.
23

---

C.1.1 Main Proof
Proof of Theorem
3 The proof shares the similarity with the coline-to-comfidenneeee conversion
technique [47 14]. where the estimation error of the online estimator W is bounded by the regret.
However, we have introduced novel algorithm and analysis ingredient achieve jointly statistical and computation efficiency.
The following lemma provides the estimation error analysis. Drawing inspiration from the modern analysis of OMD [23], explicitly extract the negative term Σ I[ ++1 W Ill in the upper bound, which is pivotal for our subsequent theoretical analysis and the algorithm design.
Lemma 12. Under Assumptions
7
and 3
consider the estimator update rule
W
t+1 arg min WEW
{Z(WW)
1 W 2n
W (ll...
where (W) (VL.(W))) x)
1 W W elll T (T.,,(W.) and He Alaa Σ1=1 V2C. X
X,X Then, letting a = In(K + 1) + 2(5 + 1) and X > O, we have
W ++ W. 111., S Σ (W.)) [((W+t)) + 4XS
+
Vi..s 8+1 - Walli
W
Il
==1
when the step size set as 17 a/2.
Then, we focus on the first term of the right hand side. Inspired by the previous studies on binary logistic bandit [10 decompose the regret into two part by inserting an intermediate decision.
(.W.)
L (W++1)
(WW)
c( Us) +
C( Us)
(.
tern (8)
term (B)
where the 2, is an aggregating forecaster for logistic loss defined by 2, o+ (Ew~P,, (o(x..)) and
P. = =VWW a. (1 + 1 ) the Gaussian distribution with mean W. and covariance matrix c/ where 0 is a constant be specified. In above, o+ A + R is a pseudo-inverse function of
(-) whose k-th output is jo (p)] log (px/(1 - (|I]|æ)) for any p E {q E [0, 1| ||||]] < 1}.
We bound the above two terms respectively. First, we show that the term (A) is bounded by O (llg" t) with high probability.
Lemma 13. Let 8 E (0, 1). Under Assumptions and
we have
Pr VL 1,
(.W.))
((2,, Us) S (0)
2 1 -6
(4+4108 4+21
where the confidence radius is oo (log([+))=2log(((((()) O ((log K + log t) log
+2
Besides, the term (b) can be bounded by the following lemma, Lemma 14. Under Assumptions and for any > have
Σ E(Z.. va) - Σ (W < Σ W w 11,,, + +1((0),
24

---

by setting X z dcc In the above. 2(()) V6cKd (1+ (1t1)) and L
maxwERK4,0 (W) the smooth parameter of the logistic loss.
Combining Lemma
12
Lemma 13 and Lemma 14 we arrive at
|| 1+1 W. 11111
4182 +at ane + ( 1) Σ ++1 Woll..
Voas > W
W xxx,x W
Woll
4X52 + ont + oni
(1
vi + 2t 5
4AS2 =O(Klogg))
+a(3log K + logt)
log
+ 2 Kdl (1
=O(Kdlog² log
=O((log Kloog 1) t)
(8).
For the last second inequality. we eliminate the additional term by the parameter setting a/2, == 7a / and X 2 (7v6aS, 28K ] and due to the fact that 1x @x.x, * Ka under the condition |xxll2 1 for any E [T]. In the above, we have X OoKllog K) and Olog K). Then, we can show [W 2+1 W -1.4 I (8) (log K log t Kd), which completes the proof.
n
C.1.2 Proof of Lemma 12
Proof of Lemma 12
Let (W) (W.)
Vl, .)) + 3 - (w,, be
second order approximation of the original function (.(W) at the point W The update rule (6) can be equally written as
W
arg min (W)
I
W H.
(30)
++1
WEW
2m
which is an implicit online mirror descent update with the loss function L. Then, according to Lemma [6 the model We+1 ensures,
(V,, (W+1)., st1 W.> s 2n
( W. I|
Walle. - 1| W. .1l
(31)
One the other hand, let = log(1 1 + K) + 2(1 S). Since |W,Xelloo = max [|xe|12] I S and (W) = E(W x., Vs), Lemma 1 shows
(. - (,W.)) < (ve, (W.+1), W ++1 W.)
1 W e+1 W. WellEre,
(32)
By setting 7 a/2, the combination of 31 and (32 shows
(s(We+1) - (W.) < (Vl, (W,+1)
.+1)
VÝ,(W ++1 W s+1 - W.)
(33)
+ 1 (I W. 112
V .+ - W.12
I s+1 W. W.llH.)
In above, we can further bound inner product term by
(VL,(W++1) V(, / s+1 W W (VL,(W++1) - Ve,(W.) -V(, V2 ,) *+1 W W s+1 W.
(D"ES(E++)) s+1 W.W(W: W.), W *+1 W.
= (DD2C(ES++)) #+1 W. W s+1 W )) w e-1 W.
25

---

v6 2+1 W., 111
|| a+1 W. (ellese,(e.1)))
S S W s+1 W. ,11xxxxxx
(34)
In above Ex+1 is certain point on the line connecting W. and W e+ The notation is defined as D&e (W) [W] = lima-ga-1 (V2 +T) - (W)) The first inequality is due to the definition of Lg and the second inequality is by the Taylor series for the vector- vector-valued function. The third inequality is because the third order derivative of the logistic loss is a symmetric tensor as shown in Property| The last second incquality is by Definition | since the multiclass logistic loss is v6 self-concordant-like function. The last inequality is by the boundedness of the decision domain W and bounded action such that |x|22 S for any x E X under Assumption !
Combining 33 and 34
we have
(, (+1)= - l, (W.)
1 a
||. W.Wlll Ilr.
I
++1 W.I.
|| ++1 W. W.lli.) v6slIW s+1 W ox.
Taking the summation of the above inequality over t rounds and rearranging the term, have
W 1+ W. W.1liam
Sa
Σ (W.)
Σ (L(
+I[ W. 111....
(BasS s+1 -Wllla W s+1 W.ll 11.z.
Σ (W.) Σ (((oor)) + 42S²
S a
+ Σ
W s+1 W.ll
I 8+1 Wolli..)
which completes the proof.
C.1.3 Proof of Lemma
13
Proof of Lemma 13 Since the norm of the intermediate decision 2, a (EtWE- (W )]) generally unbounded, as suggested by (26). we use the smoothed version 2 a (smooth,, (E ([.x,) (x)))) as an intermediate term in the analysis. In above, the smooth function smooth,, [0, 1]k + j0, 1]K with parameter μ [0. 1/2] is defined by smooth, (p)
(1 μ)P + w1/(K 1). where 1 IR is all one vector.
Given the construction of the pseudo inverse function a+ such that (p)+ = p for any p E {q E [0, 1| ||لوا| < 1}, one can check that ž = a+ (smooth,(o(Z..)) Then, Lemma 17 shows that
Σ (3 Us) Σ E(Z,, ys) S 2pl.
(35)
Besides, Lemma 17 also shows that |لحا| llo S log(1 (K + 1)/m). Therefore, prove the lemma, it is sufficient bound the gap between the loss of W, and 2 By the definition of the loss function E., we have f, (.W.) f(zz, y.). where " W_ x,, Then, we have
Σ l. (W.)
Σ E07 v.)
Σ
El2 ys)
Σ (Gr,u.)
elzzz (12y,19. v.), 2 Bi
12
2
S
26

---

1
Σ (x()) Ys, 2: こリ
Σ
1 Sp
1z
2 (x;;))
11
(36)
where S₁ = log(K + +1)+ 2og((1 (K + 1)/m). In above, the first inequality is due to Lemma The second equality is by a direct calculation of the first order and Hessian of the logistic loss as shown in Property 1
To bound the first term of the right hand side, we require the following lemma, which adapts lemma 6 to one-dimension case and whose proof is provided C.I.5
Lemma 15. Let (Fe) be a filtration. Let {ze] be a stochastic process in (2) {z E R | S. }} such that Ze is Fr measurable. Let {Et] be a martingale difference sequence such that E, E 12* is Fe+1 measurable. Furthermore, assume that conditional on Fs, we have ||=:|| I
almost surely, and denote by Σ, == BlErE, [Fi]. Let X > 0 for any 2 define
S. =
(e)) and H, = A Σ 12.1..
==1
==1
Then for any 8 E (0, 1), we have
VA +
4
H
4
]]
Pr > 1, 2
H
log V x
+
1og(2/0)
VX
To check the condition of Lemma
15 we let d, = (z (S + S). Since || I
| lcc I log(1 + (K + 11/p), one can verify that |d S 1. Besides, since 2 and z is independent of y.. the variable d, is F, measurable. Furthermore,
max |w! (4x ||a||xe|le ||l I S and
can check that (z,)) y.) (a))) yz)" [F]] = (z))z) and ||]) yslli S 2. Thus,
direct application of Lemma 15 shows that, with probability at least 1 - 8, we have
Σ (zzt) - Ns. 2,. )!")
(37)
#=1
-Spp + 5) Σ (zz)) Vo, de)
e=1
VT
4
1
Σ Semlldallaasss
S (Sp + 5)
A+ 1=1
d. 2 Vo(e;)
+
log
4
Vx
8
VX
VI+ + 21
$ (Sp +5) A+ Σ d. 2 Vo(z;)
+
log
(38)
V/
8
for any 2 1. In above, the second inequality is consequence of the fact |d, (izz)) d Vo(2z) d, < 2. Then, combining 366 and (38) and setting À = 1, we arrive
Σ (WW)
107 yo)
[V+ + 21 5
S (5, + $)
1
d. 14.12 (2))
+ 4og
- (Sp + S)
Σ | | ((())
8=1
8=1
1 + log
VI /1+2 2/
))
S (S, + 5) (1+) D d. [xx())
+ (S, + 5)
(Sp + S) Σ
d. 2 ((x)
5
5 (S, + 5) + 4(S, + 5) log
VI+ 2t
<
(39)
5
'We note that the here is irrelevant of the algorithm, we set it any value.
27

---

where the second inequality is due to AM-GM inequality. Finally, combining (35) and
39
we have
t ee(w.) Σ (Z.. ys) - (S, + + + 4(5, + log
VI+
+ jt
5 + 4 log
<1 +1 21
)) + +
- 3 1 + (1+ K)t)
where the last inequality is by the parameter setting = 1/t and, as a consequence, Sμ. = log K) log(1 (K + 1)t). We have completed the proof.
C.1.4 Proof of Lemma 14
Proof of Lemmal 14 Our proof starts with the observation made by [26, Proposition 2] that 2, is an aggregating forecaster 44 Chapter, 3.5] for the logistic function, which satisfies
((7., ya) S In (Ew-r,,e (e=))
Then, direct calculation with the definition of Gaussian distribution P. NNW "H gives
y&) S In (EwwPr [o- --nn In ( c o-L,(Wad y
(40)
Zs JRKd
where we define the loss function L.(W) (.W) + (2c) -1
W. allis,, and Z.
V (2*) being the normalization factor.
Then, we consider the following quadratic approximation,
(W, I., (W,+1) + (W.,,( W W s+1) 2c
W W s+1
(41)
According to Lemma 18 we have
(W) s (W) + 6
W W W.tille
sttllle,,
Then, we can low bound the term in the expectation by
Ew-r [e-c,(0)]
LOWW)
7g 2kk
Z, JRKU
L.(W.+1)
[w+)(W) WV
(42)
Ze
DRa
where we define the function
fo W W R as
F++I(W) = exp (- W W 1711 122 - G| IW -Wotelleee
1
Denote by Zo+1 = SweRka Jo41 Ja+I(W)dW S +oo the normalization factor and P... the distribution
whose density function is (W) /Z can further rewrite the last line of the above displayed equation as
eLb,(War1) 7
Ew~P, [e [c-611]]] >
e (W.)))
E Bw
Z,
28

---

(.(W++))
Zo41
(-B (V +11), W - W Ws+ll))
Z exp
L, (Wo11) 1z+1
(43)
Z.s
where the second inequality is due to the Jensen's inequality and the last equality comes from the fact that (W)) Z is symmetry around W s+1 and thus E LVV., W W s+1)]
Plugging
43
into
440) we arrive
y.) (W .+1) In Z. In 7,+1;
(44)
where we further convert the last term
In 2011
de ll
wi i- W : 1F2
- -In Zo+1
IIn
1,+:111111111111 18
?ot1 I8 W In
In -In +Ew E.
B1 1111 W W s+1 || (w.-))
In Zo B
B1l W.+
W
W s+1 (
(45)
where Pst1 = N(W s+1, 1H and 2u41 Sance - +1lli
dWW dW. above, the first equality is by definition of Z and the second one comes from the definition of P.+1. The last second inequality is due to the Jensen's 's inequality such that In(Ela)) 2 E[In al for the random variable a E R. The last equality by the fact Z.+1 = Sgka C 2:11 W --1 M. dW Z,.
Combining 44 and 45 and taking the summation overt iterations, we have
(.). Σ (W + Σ agn
(46)
Following similar argument in 277 can bound the last term as follows. Specifically, by the Cauchy-Schwarz inequality, we can decompose the term Ω2 as
22 S
12 +
[[ W W Il
torn (a-1)
torm (a:2)
Then, remarking that P.+1 = N -N (W,+I,cH, the key observation here is that W W s+1 also follows the same distribution as
Kd
Σ
cde Vxe (1e
where X; i.dd N(O,,) 1), Vi E [Kd],
(47)
where (e, E RRKd Kd
[=1 is set of certain orthogonal basis and X; := A,( denotes the i-th largest bound the first term of term (a-1) by
eigenvalue of H, Then,
term (a-1) < Exx [ K x2
< K[Kd x2
K4
[xx~x² e x x2xx))
S Exxxx
[e Gardo x
where x is the chi-square distribution and the last second inequality is due to H2 > XIaa and thus X; < 1/A. The last inequality is due to the Jensen's inequality since Kd > 1. Then, by further requiring À 2 24Kdc, we have
term (a-1) S Exxxa [
S 22,
(48)
29

---

where the last inequality is because the mommet--gnnratingg function for x diiditbrbnttion is bounded
by Ex=xa [c'*]= - 1/VI- 2t for all S 1/2.
Then, we consider the second on the upper bound term (b). A direct calculation gives,
E ww.N(o,af." [
term (a-2) E (w.r(o,att
where 11, (V (
+. Then, let X, Xo (cll.
be the i-th largest
eigenvalue of the matrix. A similar decomposition as (47) shows that
Kd
Kd
21 )
term (a-2) = Ex.-N(0.1
Σ
Axx,c;
Ex.~N(O.1)
Σ Exx? Xx2y v3eTT(HH
Kd
X x, x S
where the last inequality is due to Ex, V S 3 for all i,j e [Kd] and the last equality comes from the fact that Em X5 Tr(cH,")) The notation Tr(A) is used to denote the trace of the matrix A.
Then, we proceed to bound the trace Tr 1) with H, = H,V%,, (W++1). Recall the definition of H. Alxa + E==1 vee, ( We define M,+1 Alka/2 + Σラ= Vee, (W,+1) Under the condition X 2 for any e [T'], we have (W) & Lkd S [ for any s [2'] and W W.
Then, we have H, > M Then, we can bound the trace by
Tr 1) Tr H ( S Tr M ('L
M
=Tr M MT+ (M Ma)) < log
where the last inequality is due to Lemma 4.5 of [6]. As a consequence, we have term (a-2) S V which leads to
[|Mo+1]
Ωg S term (a-1) term (a-2) I Vbeln
(49)
|Mal
Combining (46) and (49), we obtain that
((Z.)ya) e. (1W++)) <
1 Σ W
W s+ 1lir, + V6c Σ In
[Ma+1]]
[Ma]]
C
W can further bound the last term of the displayed equality by E. In (IMs+1l/|
C V
In (1M+zl/12/2 Txal) s Kdln (1 + (++1)..) which completes the proof.
C.1.5
Useful Lemmas
Proof of Lemma
15 The proof of Lemma 15 shares the same spirit as that Lemma Let H;
Σ 2
12,
We can also defined the function
Mc(E) = exp(ES, - - H₂)
for any t and & E IR. Fort = 0, we let Mo(E) = Following the similar arguments in the proof of Lemma one show that the sequence {M{(E) [2,))) is non-negative super-martingale when < 2. Then, let h(E) be the density of the normal distribution with precision 2 truncated on the 1-dimensional ball (1). We can define
M, / exp(ES, - (H)))E(EE)
30

---

By the similar arguments in deriving 17 we have
()) Pr sup M, 2 S 8.
1
Pr sup log M,) 2 log
(50)
IEN
IEN
Following the arguments in the proof of [ Theorem 1]. for any 12 1, we have
((g)
M, 2 exp(ES, - g²H
(()
for any |5| $ 1/4. In the above, g is the normal distribution with precision 2H, truncated on the interval [-1/4, Then, let Eo 1 v m. have Eu I 1/4 since H₃ 2 A. We can obtain that
(N(9) ((h))
VA
S.
A
(N(g)
log(M, 2 EoS, - 50 H, log
+ log
(51)
4
v H
16
N(hh)
A combination of (50) and 51 shows that
St
(()) N(h)
< log 1
Pr 1A 11211
+
log
- -,
/ H,
16
which indicates
4
(h))
))
Pr
VI 2 1,S, < v He
log
2
xN(c))
We complete the proof with Lemma 6 of 8
which shows that log (N)))/N(()) S log ((2 H/,/H///))
11
Lemma 16 (Proposition 4.1 of 49 )
Let the Wi+1 be the solution of the update rule
*++ arg min (la(w) + Dw we),
WEV
where V W C Rdd is non-empty convex set and (w1 w2) vb(1)) ) (Vo(W2), W1 W2) is the Bregman Divergence w.r.. strictly convex and continuously dif- W1
(Ww2)
ferentiable function vi W + R. Further supposing vb(w) is I-strongly convex w.rlt certain norm ||-Il in W, then there exists a g' E 06, (le(w such that
(meg' Wi+1 u) (Vu((w:) - Ve((w+1)) WH+1 -
for any W.
Lemma 17. Let {(2, y) -Ek 1ly k:} log ( and R.K be K K-dimensional vector. Define z A o+ (smooth,(orz))), where smooth, = -1-H)) + p1/(K + 1). Then, for μ E [0, 1/2), we have
{(z",y) E(z,8) S 2p
for any y E [K]. We also have ||00||00 log(K, (K/p).
Proof of Lemma 17 The proof of Lemma 17 is extracted from the proof of (26. Lemma 3] with slight modification to the logistic loss used in this paper. According the definition of z" and the fact that o (p)) = p for any E {q E [0, ||]]|||||ll < 1}. we have (zz²) =
- (p)o(z) + p1/(K + 1). Then, we have
o (z))a
((z*,v) - ((2,9)
Σ f - k) log k=0
S log(1 p1) 2p,
11) (Z)) + /
where the first inequality is due to Ex 1 = k} 1 and the last inequality is due to log log(1/( (1/(1 a)) 5 for [0, 1/2]. Besides, let p (z)). According to the definition of zz have
(1 - 10)p + //(K
|| = max
log
KE[K]
KH/(K + 1)) - μ1) |
31

---

Since the term inside the logarithmic function can be bounded by
(1 (1- 41u + 1/(K +
11+ K+1
1 K(1 11) S log
-1-
and w/(1+ K(1 11) 1, we have
110 S log(1 + (K + 1)/m).
Lemma 18. Let (,W - (.(W) 2.2 | - W .lli.r Then, for any W, W .+1 E W, the quadratic
approximation L.V - (. (VL.(W++)) w .+1
+
Zc W - W s+1 &+1ll,, defined
1
as (41 satisfies
L.(W) - ( W- + W W s (l
Proof of Lemma 18
According to 19 Lemma 4], Cg a -f-self-comcorraattiik function. Then, by Lemma and the fact c(z)
S e"
for any 2 0, then for any W W. we have
(,W S && (W, W W s+1) Mlll
W s+1 (W
(52)
Besides, since g. (W) = 1 W. W Il2 is quadratic function, we have
Vg. (W W .+1) + W W *+1 11
9.(W) = 9o (W++1)
(53)
2c
Then combing
(22) and 53
obtain upper bound of (,( (W) + gs (W) by
L.(W) S L,
W
s+1 VL, .1) W W .+1)
I W 1+11 + e 6||l -111 W W W011l
+ 2c
< L. (W) c W- - 11: W W.+1llEr 1l
We have complete the proof.
C.2 Proof of Proposition
1
This section presents the proof of Proposition] !
C.2.1 Main Proof
p (W\xx) to show (Pl (x) = =p" (W,x)) + =x*(() + c=nd(x) (x) is an optimistic estimate, it is sufficient to prove that
Proof of Proposition 7 Since p pTo (To(Wx)) < p
lp ToTTT(WWWa (W.x) - p (Wx)) S (x) (end(x) We have the following decomposition:
1p (W.x) p -T ((Wxx)
K
pa(on (W.x) -wxx))
Σ Pk (Wx (W. w,)x
pkl Pkll(W w2)x
K
K
Pk: Vox (W.- Wx)x
+
Pxl(WW. -
term (3)
torm (b)
32

---

where x (x)] is the k-th output of the vector- valued function (x) and Ex = S (W wi))x)dv. In the above, the last equality is due to the integral formulation
of the Taylor series.
Then, we proceed to analyze term (a) and term (b), respectively.
term (a) = p (W. - Wi)x
pp (o(Wix) @ _ \ W
1p" (o(W @ x ))H, (W. W.)l
||W. - W.llm. |H, (Ix @ (X)xx\()))
S (0) 1111 (4x 8 (W)x))
4
rat (x),
where the last inequality is due Theorem Then, we upper bound term (b) by e with the following arguments. For notation simplicity, we denote by Ér,u W,x + vWW Wx)x. Then, Lemma 11 indicates that
k / (1 V & <37x μ=ル
I (1 - v)du $ 3lk.
As consequence, we can bound term (b) by
K
term
(b) 3
Σ
Pk (lW - W,)x
k=1
S 3R, w
3R @ x T T) W.W .)13
== 3R|WW. - W Welli. [1(Ix @ x )H, $12
3 $12 - 3R (300) 2 1l @ 0xT)Hi (x),
where the first inequality is due to Assumption 2 and the last inequality is due to Theorem Combining the upper bound for term (a) and term (b), have
3
(W.x) p (W,x)) tat (x) + and (x), for any x e X. We complete the proof by p (W.x)) < oTox) to - ooTooWxx)
(54)
C.3 Proof of Theorem
Proof of Theorem 4
We first prove the regret bound and then discuss the computation cost.
C.3.1
Main Proof
Regret Analysis.
We can bound the regret by two times of the bonus term over X,-
Regr
TT ((o...)) p oo(W))))
Σ (pT (Wixx) + "x,, + and (xx) -p (.ox)-poo(WWa))) (oo(xx))))
(p To(xxx))) + + +x(==(x))) (x+) + + (x²) - p² -p-a o(W)).))
33

---

T S 2
T
Σ rst (xt) 2 4
Σ and (xt):
(55)
where the first inequality is due to Proposition and the second inequality is due to the rule of constructing the optimistic reward. The last inequality is due to (54).
Then, we turn to analyze the upper bound for the first term and second term respectively.
det (xt)
Σ 1=1
(8)
|H, & (x)))))\(
S 50 (8)
H (Ix @ @x)))o(Wxx))l
T
T Σ
$ 5 (8)
Σ
HH, & & x (
H (Ix 8 x - (o pllz.
term (b)
(56)
For the first term, have
term (a) s
pll ( ||H, (Ix @ x, (W(+xx)l
R
Amax (Voi x Hi (Vo (Vo: @ x()
R
Amax (Vo(W.+Ix) HHi1
RVT
Amax
(Vo((W++Xx)) &xx, H
< RVT
Kdln (1+
TT. 2
where the first inequality is due to the fact that ||Ab||2 l < ||A|2 : ||b]| for a matrix and vector b. The second inequality is due to the definition of the induced norm for the matrix is defined as || / Amaax( (A") A) and the mixed- -rxouut property of the Kronecker production. The first equality is (Caxx(CBB) for
due to the cycle property of the maximum cigenvalue such that AABx(AAC)) matrices A, and C. The last second inequality due to the Cauchy-Schie Schchy-Schwazz inequality. Finally, we can obtain the last inequality by Lemma 19 which can be seen as a matrix version of the elliptical potential lemma.
Then, we can bound term (b) as follows.
term (b) S
Σ H (Ix & x:)1l2 (lVo Vo((.-1x))) pll2
T
K
Σ
H1 (Ix 8 x:)12
Σ (u(Vox(Wxx.) - -Vo((w++x1))
Σ
m1 (Ix @ x:)l2
Pk (WooO W
34

---

I = - 1He (Ix @ x
K Σ Ph (x w 21)
(57)
In the above, the second equality due to mean-value theorem, where denote by f., E RR certain point on the line connecting W,x, and W4+1X,. We can further bound the second term of the right hand side of the above displayed inequality by
K
( @ 8x XW W Wetl)
K
Σ
H2 (W, W Wet1)
Ps
K
Σ
Pa
(E 8x
I W wall
avK
K
Σ Pk 4 ('oLL(E)) @ 8x H,
avK
K
Pk: Po
(1x )H,
3aKR X
| 2 x 11
u $11
(58)
where the first inequality is by the fact |Ab l2 S ||A||2 |lbll for any matrix and vector b.
The second inequality is due to Lemma 20 The last inequality is due to Lemma II such that
(z)(z)) & 31g for any z E F.K and ΣK Ph: S V.R.
Then plugging
58 into 577. we can bound term (b) by
3aKR
3kKdRR
T
term (b)
ur (Ix x1
In
1
where the last inequality is due to Lemma 21 Combining the upper bound for term (a) and term (b) and plugging them into (56). we have
TL 2
))
3xK 3xKdRa.9))))) In 1
T
fot (x,) s (8)
RVT Kddn
1+
A
=0 =o Kdllg K(log T) VT sk d (log K)² ()o()
(59)
As for the term Σ and (xt), we have
and (x,) = 3R ( 2, [1 xx, )H
< 3R (3 2 kd (1+
T
O (kKd (log ()ogl
(60)
Combining 59
and 600)
with 55 we have
Regr S
(x)) +
and (x,(
TL
6kK 3x
T Ax
< (6) dln [1
+
In
1+
2X
A
35

---

T
6R ) kd in 1+
Ane
= ld K (log T) VT KK dl (log K) (log T)²)
which completes the proof for the regret bound.
C.3.2 Additional Guarantee for Algorithm
This part shows that the OFUL-MLogB (Algorithm Theorem 5. Under the same condition Theorem
also achieves an Ö(VRKT) regret bound. Algorithu ensures
Regr S O (d log K (log T) VKT xK dd (log K) (log
Proof of Theorem 3 The proof of Theorem is almost the same as that for Theorem We can
decompose the regret as
Regr S 2
tat E
(xt)
E
and (xt)
following the same arguments in (55 with different arguments based the local matrix V, & Alga + E.= IK % X,X,
55
The only difference is that we can bound the Σt= (x,(
Iet (xt)
Σ B (8). |H, (Tx 10 (ox))
T
s R (8)
V.- (Ix x1
RdT log log 1+ T
I Rp (6),
kdd
Odlog K (log 3 VRKKT
(61)
where the first inequality is by the fact that He > V.. (o(Wi, < Ix. and |ll|l2 S R. The second inequality be obtained snd with the same arguments (60):
T
Σ
and (x) S 0 (sKd 2 7)
We completed the proof by combining the above three displayed bounds.
C.3.3 Useful Lemmas
Lemma 19. Let He Alaa Et=l (Wo+1X)) X,x_. Then, when we have
Amax (VVo(W++1X))) & x (1,11) < Kdln 1+
TL 2X
where L maxxxx WEW Amax Amax (Vo(Wx))
Proof of Lemma 19
Let Mr Aka + E (o( @ Xx Then, we have H, - MM; (o),)))) & X Since ( & Iga. we have H, & M, when À > 2.
Il Vo(W
Then, have
Amax (xx[W+ixx)xxxx]]]
@
36

---

Tr ((Vo((W(+ @ x xxx,)H11
Tr (Mr - Mo
|M
log
|MM-1l
TL
S Kd
1+
2Λ
where denote by [r(A) the trace of matrix A. The second inequality is by the condition H, > M,. The last second inequality is due to Lemma 4.5 of [16].
Lemma 20. Ler W. W+1 arg min (W,,W.) () W) + a 11ll3g
Then, we have
W +11 - W.l S a Ve,(Ww))) 1l - aVK 2A
A
Proof of Lemma 20 Let F((W) = (VG 1) / |
W 11 fr
Since W We+1 =
arg mew F(WW), have F.(Wi.H 241) F F.(W ,) which implies
c+1 W.llf, (V W. W w11)).
Then, by the Hölder's ' inequality, can further bound the inner product term by (V&(W.) J. W. - W e1) < M| [++11 -
IV -Ve. (V
which indicates that
| 4+1 W dl S Va
Since He > H, and H.! 1 & Ixd/X X, we can further have,
| 2+1 Wellm. < W 2+1 W R. <a//V/ - 2X VV .)l2 avK
where the last inequality due to the definition of V(,(W.. (W.) yt) & x, such that [[ 2ll2 s KVK.
Lemma 21. Let He Alka + E:=l (o(W++1x.)) @ xx.x..
Then, we have
11, (Ix @ x:)1 s sdlnn (1+ T Σ 1=1
Xx
where X >> 2.
Proof of Lemma
21
The proof of Lemma 21 shares the same spirits with that of Lemma 19 Let
V. = 2 2 Jka +
s=1 Ix @ x, We have H, > V. when À > We can prove the lemma by
T
Σ
H
1 (Ix @ x,)12
Amax
xx))
37

---

T
Amax
(II ( 8x (1x
'lx (xx))
Xmax
(Ix xx,x
1K (lla
+ 1 Σ
Exxx)
xxxx
(Ix @ xi)
t=
s=1
T
1 Σ xXX
max
IK 2
X2 Nld
+
x:
[=1
==1
= Ald +
Σ [xxx]
kdln 1+ T A rr
where the first inequality due to H, > V. The second equality is due to the definition of V. and the third equality is due to the mixed-product property of the Kronecker product. The last inequality can be obtain by the standard elliptical potential lemma 3
Lemma 11].
C.3.4
Computation Cost of Algorithm
Algorithm 2 OFUL-MMogg
Input: regularization coefficient X, probability 8, step size v)-
1: Initialize H1 Al and W, as any point in W
2: for = 1,..,, do
3: Select the arm by x, arg x 7i (x) and receive y4-
4: Update H1 = H, + 1) V o (W;x) & x,x;
5: Update the estimator W (+1 for the next iteration by (6)
6: Update Hi+1 = H, + (WiWW41 @ x,x, and
7: Construct the optimistic reward by Tx)(()) = p To (W((1)) (44 (x) and (x) as
fat
8: end for
Here, we discuss about the computation cost of the Algorithm 2 For each iteration, our algorithm requires to maintain the inverse of matrix H++1 H, + Vo @ x.x! and H, He (W, @ x,,x7 Since (W @ x and Wo(WW @ x, are both rank- K matrix, then one can main H, and H, with O(33d)) computation cost per iteration by the Woodbury formula. Given the H, and H,-, we discuss the computation cost of the construction of the optimistic rewardBann the update rule for the estimator (6).
Computation Cost of the Estimator 6 rule 6 is identical to
As shown by the discussion in Section 3.2 the update
- -
++1 = arg min|| W Wew
Ž 24ll.
and
Given the H, we can perform the gradient step with O(K2d) time complexity. As for the projection step. the optimization problem can be solved in O(K3d)) time [18 Section 4]. As consequence, the overall time complexity for obtaining the estimator is O(K3
Computation Cost of Building Optimistic Reward. As shown by (8) we construct the optimistic
reward by PBL (x) = p (w?"x + +ff (x) enn (x). We can compute eftt (x) with the following equivalent formulation
< #st (x) 300 (8) ||, (JK @ (W.)))l
(0) p (Vo((x P (VVx(())) @ x)p.
Given H, it will take 2()2d to calculate fee (x). As for the term <x*"(x), it can also be rewritten as
(x) 3R (B 2 [I @ x THH,
38

---

3R (3 /Amaa (Ux & xx )x,
would take ()) time to perform the eigenvalue decomposition. Given there are [X] arm, the time complexity for identify the arm x; arg maxxex (x( is in total ((
Overall, Algorithm can be implemented in O([2) time, which independent of T.
C.4 Proof of Corollary
C.4.1 Main Proof
In the binary case, we select the arm by (x,, We) arg maxxex, WEc.(( w x. In such case, we show Algorithm [ achieves an /R.) bound with a constant computation cost. The proof is almost the same as that of [10] Theorem 2]. The main difference is that complete the proof with the confidence set of the efficient online estimator (Theorem 3 self-containedness.
We present the proof here for
Proof of Corollary 7
When K = 1 and P = 1, the Mlog problem recovers the binary logistic
bandit problem with the feedback yt (0, }} and the reward model Pr(y 1|x] o(w x). In such a case, we can decompose the regret by
T
T
Regr Σ olw
x.)
Σ
o(w xx)
1=1
T
<
Σ
(w x1)
Σ
o(w, x1)
1=1
Σ
o o'(w, xx)(( w.) xx Σ o" (Exx)) w.) xx)²
Σ d'w, [w, w.) NEh
X Σ
o' x1 ( w.) X
d" ((())))((w; - -w.) w.) Tx)xx,)? x,)
(a)
torn (b)
tern (c)
where the first inequality is due to the arm selection rule. The first equality is due to the Taylor series and & Rd is certain point on the line connecting W. and w.. For the last equality, we divide the
time horizon into two parts Jı = (t E [7] (w. x,) 2 [wWT41x)) and I2 = [7]/I.
For term (a), we have
term (a)
Σ o' (W, (W -w.)xx x,
tEh
Σ
o W xx) <w, wa) + Σ (Ww11- w.) JT [xxe(WW w.) xx
teh
Σ teh
(w((W(41X1) ||w, w.llm, |ly (1
(a-1)
| |xx||,,-111 w.lla,
wellHar
tern
(a-2)
where the first inequality is due to the mean value theorem and the condition that (a"(2) < 1 for any z R. The second inequality due to the Cauchy- Schwwaz inequality and H. x Hes1. We can further bound term (a-1) by
term (a-1)
Σ t1
Vo((WTnIx))
|| walla, a.l.la.lllooo (x
39

---

< <28r())
Σ LET1
d'(Wi+1x1)
ll 0 ( X xxx
Iel1
228r(6)
o' (w, d'I, X1)
Il o 1
KET
TET
dlog(11 + 3t
$ 443(()) V Regr +To'(w.
(62)
where the first inequality is due to W, and w. are both contained in (, and (3( Ollg t) is the radius of (ō) as shown in Theorem
The last second inequality is by the condition such that a'ww, xx) 2 d'(n d'(w(+1x)) for all t IT Then, following the same argument the proof [0 Theorem 2], one show
3
Σ o'(wTxx) s
[d'(wTx)) s
sissv/eee Regr +T'' (w, x.),
(63)
tEN
IET
which leads to the last inequality. We also use the elliptical potential lemma Lemma 9] in the last inequality.
As for term (a-2), have
term (a-2)
S (3r(6))
Σ [xellr, S kd) In(1 + Xm 1E
(64)
where the first inequality holds because w. and W, are contained in (6). The second inequality can be obtained following the similar argument in obtaining (60). Combining the upper bound for term (a-1) and term (a-2), we have
term (a) < (3) dlog(1 + T 7), (w.xx;)
T An
Regr +To x.) + (d( In(1 +
As for term (b), we have 0' o'ww, xx) < o' O'(wII x,) for all t E I2. Then, we have
term (b) s Σ (w(,.x))) -l - - wll.. o x1 1r
te
< Σ
a'( x1) 1l - wella. o x1) x1)x
t
s 4 dlgg(1+ + Regr +To'(w, x.),
where the second inequality is due the condition of (w. x²) can be obtained using similar arguments as those used to derive (62
o'(w W xx) and the last inequality
Regarding term (c), the application of similar arguments used to derive equation 62) demonstrates.
T
term (c) & nd(33(6)) In(1 +
Ax
Then, combining the upper bounds for term (a), term (b) and term (c), we have
Regr S (83)(0)) d doog(1 + F) V Regr +Too--TTowwwrrr + 2nd( (nd In(1 +
T Am
Resolving the above displayed inequality leads to
Regr < 32.3r(6) d dlog(1 + T X F) TTT(wxxx) + (8x 64))((3(6))) In(1
T )
In the binary case, (5) = =(V T). Then we have Regr (d T TT/R t/ log T).
which completes the proof.
40

---

C.4.2 Computation Cost for Binary Case
Since the binary logistic bandit is special case of the MLogB problem, the time complexity analysis in Appendix CC3.4 is also applicable in the binary case. The only difference that we select the arm as (x,, wt) arg maxx E X, W C,(5) x the binary case. As C₂(8) & (w E W ||w w. m. S [o) is an ellipsoid, the optimization can be rewritten as:
arg max XEX
w x
[|W www-w.la, SPc(8)
arg max
max
W x +
[|u||, (8)
arg max W, + (0) | H,
XEX
Given H the above optimization problem can solved in (cP) time.
C.5 On the Minimax Optimal Bound for the MLogB
In the binary case, we have achieved the minimax dynamic regret bound (VVT/R.) up logarithmic factor in terms of T. In the MLogB problem, the best-known result OKK))). A natural question arises: can we obtain similar minimax optimal result in the MLogB problem? However, we find that it remains challenging both in terms of regret analysis and the design of efficient algorithms.
Challenge in Regret Analysis. To establish the minimax optimal bound for the binary case, as demonstrated in [9 [0] and we restate in (63), critical step involves showing
d' x.) S Regr +I''' x.).
IET
In the MLogB problem, in order to obtain similar result to the minimax optimal bound achieved in the binary case, it is sufficient to demonstrate
T p Vo(W..))p
V
2R Regr Σ p I(W.)..p. t=1
(65)
However, it is unclear how prove such a relationship as the binary case. Indeed, denoting by (W.x.) (W..x, the reward vector and Ft. by its k-th entry, we can further rewrite the k-th entry of the vector p [(W.x)) can be further written as
(p [(W.x:)] (W.x.x)))) (ex (W.x:))
[Wxx(W,..) rt,k) (ax (W,x.) - r(,k)p (o(Wxx.) rr)
= =ox(W.x,)pp - (W, o (W.x.)
(W.(W. T r re t (o.(xx)) -ek)
= BoTT.W..,p + o (W.x.) p r + Tt,pP
-ex).
In such case, we can bound the left hand side of 65 by
K
I[(Wxx)p=
p (TE(W...) pTr, pT (o(W.))) + +o(xx.)))
pirep
k=1
5
Σ F(W....) 2R Regr
(66)
[=1
In the binary case, the binary case, the additional term becomes thereby resulting in the derivation of (63) Nevertheless, in the context of the MLogB problem, this particular term has the potential to assume positive values, posing challenges determining an upper bound for it.
Dt =
Regr <
41

---

AayAESI CLTM
Time fsecombss
Reggeet
Beggres
Iteratinn
(teration
Iteration
Algorithim
(a) configuration 4
(b) configuration 5
(c) configuration 6
(d) running time
Figure 3: More results for binary logistic bandit.
MCS coe
Nitt-cic MPUMMayg
Time (secembbs
100
Reggee
Dergret
2000
100
Iteaaion
Iteration
Ieeration
Algorithma
(a) configuration 4
(b) configuration 5
(c) configuration 6
(d) running time
Figure 4: More results for multinomial logistic bandit.
Challenge in Efficient Algorithm Design. When extending algorithms that achieve minimax opti- mal bounds from the binary case to the multinomial case, there are computational concerns to address. the minimax optimal regret bound relies constructing optimistic reward through (x) = arg wec, o (ww" x). Since o (z) is an increasing function, the optimization problem can be simplified to
In the binary
F
arg max W x; (
which becomes convex optimization problem when (6) is convex However, when applying this analysis to the multinomial case, solving the problem requires optimizing
Fr (x)
arg max o (WW). WEC.(5)
Here, the loss function is non-concave, rendering the maximization problem challenging to effi- ciently solve. Consequently, new approaches for constructing the optimistic reward function may be necessary.
D Omitted Details for Experiments
In this section, we presents more empirical results for other configurations and introduced the parameter configurations for the contenders.
Experimental Details. For each configuration, both the arm set A' and the underlying unknown parameter W. randomly selected. In the binary case, the of the unknown parameter is 5. As for the multinomial case, each row of W. are randomly sampled with |w (k) ||2 5 for all [K] with š 1. The parameter of all contenders are set according to their order as suggested in the corresponding paper. We use À = d log(?") for Log-UCBI, for OL2M, À 1 for ada-OR MiL--FF--EOLLO and X = VKa for OFU-MLogB. The step size for OFU- MLogB set as 7) = S/2 + In(K + 1)/4. The experiments are run on Xeon E-2288G processors (8 cores, 3.7GHz base, 5.0GHz boost).
as || w = S with
More Results. Figure [euurepprooo provides additional empirical results for the binary logistic bandit problem. These results align with the trends observed in the main paper, wherein our OF U-MMLLgB algorithm shows performance comparable to
but with reduced computational overhead. Meanwhile, more results for the multinomial case are provided by Figure The cumulative running time for MNI-UCE increase at a rate of ((12). In contrast, the running time for our OFU-MI.OgB exhibits a linear dependence with t, attributable to the constant computation cost per round.
42


Reviews:
[{"review_id": "vlBUMQU6Xx", "reviewer": "Reviewer_XVWd", "summary": "\nThis paper examines multinomial logistic bandits (MLogB), a problem where the learner's action $x_t$ produces feedback $y_t$ with $K+1$ possible outcomes. The probabilities of these outcomes are modeled using a logistic model. In real-world scenarios like online advertising, customers may provide various types of feedback, such as 'buy now', 'add to cart', 'view related item', or simply leave without any click.\n\n The MLogB problem assumes that at each time $t$, the learner selects an action $x_t$ from $\\mathcal{X}$. Each outcome $k\\in[K]$ is associated with a latent parameter $w_*^{(k)}\\in \\mathbb{R}^d$ and the probability of the outcome $P[y_t=k|x_t]$ follows the logistic model, \n$P[y_t|x_t]=exp((w_*^{(k)})^\\top x_t)/(1+\\sum_j exp((w_*^{(j)})^\\top x_t))=\\sigma(z)_k$. \n\nThen the expected reward of the learner's action is defined$ \\sum_t  \\rho^\\top \\sigma (W_* x_t)$ where $\\rho$ is a known rewards vector. \n\nThe authors first introduce an improved version of MNL UCB algorithm [12] with the optimal dependency on K. With an improved concentration set for OFU in Theorem1, MLE based algorithm achieves $O(Kd \\log(T)\\sqrt{\\kappa ST})$ in theorem 2. \n\nIn the next section, they present an efficient and improved algorithm (OFU-MlogB). For the efficiency, they address the computation cost of MLE and OFU methods. Instead of using MLE, they suggest using online mirror descent algorithm to estimate $W$, incurring $O(1)$ cost per round and achieving $\\kappa$=independent confidence set in Theorem 3 (similar to theorem 1).  For the optimistic reward construction, they suggested a novel optimistic reward that can be solved in a constant time per round by introducing bonus terms for exploration in proposition 1.  This method archieves an improved regret bound of $\\tilde{O}(Kd\\sqrt{T})$ in Theorem 4 and constant computation cost compared to $\\tilde{O}(K^{5/6}\\sqrt{\\kappa T})$ regret bound and $O(T)$ computation cost in [12]. In the binary setting where $K=1$ the proposed algorithm archives a minimax regret bound of $O(\\sqrt{T/\\kappa_*})$ with an optimistic rule similar to [9,10] while maintaining lower computation cost. \n\nIn their analysis for theorem 3, they leverage negative terms from the efficient update of mirror descent and a novel intermediary prediction construction designed for multiclass logistic loss.\n\nLastly, they provide experimental results for both binary and multi-class settings. In the binary case, the proposed algorithm demonstrates lower computational overhead while delivering comparable performance to the state-of-the-art algorithm, ada-OFU-ECOLog[10]. For the multinomial setting, the proposed algorithm exhibits improved computational efficiency compared to MNL-UCB [12], while achieving similar performance in terms of regret.\n\n", "questions": "1. In corollary 1, what is the reason the optimistic rule follows a linear model, $\\arg\\max_w w^\\top x$, rather than $\\arg\\max_w \\rho^\\top \\sigma(w^\\top x)$? \n\n2. Is the computation cost for the matrix inverse and projection of the proposed algorithm, which is O(K^3d^3), commonly observed in previous literature like [10]? Otherwise, it appears that the improvement in computation cost mainly applies to scenarios with small values of K and d.\n\n3. In the conducted experiments, why was the time horizon set to $T=1200$, which is relatively smaller compared to the larger time steps typically used in conventional bandit literature?\n\n4. Furthermore, in the experimental results (a), what could be the possible explanation for the observation that the proposed algorithm exhibits linearly increasing regret, while ada-OFU-ECOLog demonstrates sublinear regret?\n\n\n\n", "limitations": "1. The details regarding the method mentioned in Corollary 1 may not be clear (question 1).\n\n2. The experimental results do not seem to provide clear evidence of regret for the proposed algorithm due to linearly increasing patterns and small $T$. (questions 3,4)\n\nI am open to revising my evaluation if these concerns are addressed.\n\nMinor comments:\n\n1.line 99,112: should it be changed from $diag(z)$ to $diag(\\sigma(z))$?\n\n2. line 333 ,336: $O(log1)$-> $O(1)$; $O(T/\\kappa^*)$-> $O(\\sqrt{T/\\kappa^*})$\n\n", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. In the binary case, the proposed algorithm attains the minimax optimal guarantee while reducing the computation cost per round from $O(\\log T)$ to $O(1)$.\n\n2. In the multinomial case, the proposed algorithm achieves a regret bound of $\\tilde{O}(K\\sqrt{T})$ with constant computation cost, surpassing the performance of the best-known algorithm which achieves a regret bound of $\\tilde{O}(K^{5/4}\\sqrt{\\kappa T})$ with $O(T)$ computation cost per round.\n\n3. The authors present empirical evidence demonstrating the improved computation cost of the proposed algorithm.\n", "weaknesses": "1. Algorithm 1 requires the computation of the matrix inverse and projection, resulting in computational costs of $O(d^2K^3)$ and $O(K^3d^3)$ per round. \n\n2. In the binary case, it appears that achieving optimal regret in Algorithm 1 necessitates the use of a linear optimistic rule (as stated in Corollary 1), rather than relying on an efficient optimistic reward with a bonus term. It is not clear why a linear model works (details are in Question 1).\n\n3. In the experimental evaluation, concerning the binary case, the proposed algorithm exhibits regret that increases linearly, while the previously suggested algorithm, ada-OFU-ECOLog, demonstrates sublinear regret. Regarding the multinomial case, although the proposed algorithm achieves a theoretically superior regret bound considering $K$ and $\\kappa$, it shows similar performance to MNL-UCB. This observation does not provide a clear validation of the theoretical analysis.\n\n4. In the multinomial case, there might exist a difference between the attained regret bound of $\\sqrt{T}$ and a regret lower bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. We will address your questions below and make enhancements to the paper based on your valuable suggestions.\n\n---\n\n**Q1:** what is the reason the optimistic rule follows a linear model.\n\n**A1:** We are grateful to the reviewer for highlighting the ambiguity in our presentation. We will now clarify the equivalence between $\\arg\\max w^\\top x$ and $\\arg\\max \\rho^\\top\\sigma(w^\\top x)$ in the binary case. We will now clarify this relationship. Specifically, as we discussed in line 96-97, the binary logistic bandit is a special case of MLogB with $K=1$ and $\\rho =1$. In such a case, the reward function is exactly $r(x) = \\sigma(w^\\top x)$, where $\\sigma:\\mathbb{R}\\rightarrow\\mathbb{R}$ is a 1-dim function.  Given $\\sigma$ is a monotonically increasing, we can solve $\\arg\\max \\rho^\\top\\sigma(w^\\top x)$ by  $\\arg\\max w^\\top x$.  We provide more detailed will make the equivalence of the two equations clear in the revision.\n\n---\n\n**Q2:** Is the computation cost for the matrix inverse and projection of the proposed algorithm, which is $O(K^3d^3)$, commonly observed in previous literature like [10]? \n\n**A2:** Thank you for the insightful comments. As demonstrated in the proof of [10, Proposition 8], previous literature also necessitates maintaining the **matrix inverse** and performing $O(\\log t)$ **projected gradient steps** (PGD) at each iteration to solve their optimization problem. In contrast, the main computational advantage of our algorithm lies in provably reducing the required PGD steps from $O(\\log t)$ to $O(1)$.\n\nSpecifically, both [10] and ours share the same matrix inverse cost of $O(d^2)$ in the binary case. For each of the $O(\\log t)$ PGD times, [10] employ a distinct method to project the unconstrained solution onto an ellipsoid [10, Lemma 13], resulting in a computational cost of $O(d^2\\log t)$. While this projection operation saves a $d$ factor, it incurs an additional cost of $O(\\log t)$ when compared to our $O(d^3)$ cost. In scenarios with large dimensions, where $d = \\Omega(\\log T)$, we can also utilize the same projection method found in [10] to have improved the dependence on dimension. We will provide a more detailed discussion of the computational cost of projection in the revision. Thanks!\n\n---\n\n**Q3:** The experimental results do not seem to provide clear evidence of regret for the proposed algorithm due to linearly increasing patterns and small $T$ (question 3 and 4).\n\n**A3:** Thank you for the suggestion. During the rebuttal period, we reorganized the experiments for the binary case with a longer running time $T$ and presented the results in a more suitable way. Please kindly refer to the global response for more details. Thanks!  "}, {"review_id": "tv6z3TfxTV", "reviewer": "Reviewer_Ru1r", "summary": "This paper has addressed multinomial logistic bandits whose feedback has multiple choices. This paper improves the regret bound in terms of $K$ and reduces the computation cost into constant complexity with respect to $T$. In experiments, the results support that the proposed method is much faster than the prior work.", "questions": "**Questions**\n\n1. What is the memory complexity of each algorithm?\nWhile this paper reduces the algorithm's time complexity, it may lead to requirements for more memory.\nSince there is a general trade-off between time complexity and memory complexity, it would be better to discuss the memory complexity of this algorithm (and others).\n\n2. Does this algorithm match the lower bound?\nIs there any analysis for the lower bound of this setting?\n\n3. What causes the improvement of the regret bound?\nFrom the new analysis scheme? or finding better parameters?\nIf I correctly understand the paper, the improvement of the regret bound is just caused by changing the condition on $\\epsilon$ from $\\| \\epsilon \\| _{2} \\leq \\sqrt{K}$ to $\\|\\epsilon \\| _{1} \\leq 2$.\n\n**Minor comments**\n\nTable 1: the column \"Constant Cost\" is unnecessary part since we can check it in the column \"Cost Per Round\"\n\nline 112: $\\textnormal{diag}(z)$ -> $\\textnormal{diag}(\\sigma(z))$", "limitations": "Increasing the memory complexity might be a limitation of this work.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "**Computational Complexity**\n\nThis paper reduces the time complexity into $O(K^{3}d^{3})$, which is independent on $T$.\nThe experimental results also support that computational time is dramatically reduced in practice.\n\n**Regret Bound**\n\nThe regret bound of the proposed method is $O(K\\sqrt{T})$. This result is a substantial improvement over the best-known regret bound of $O(K^{5/4}\\sqrt{\\kappa T})$, where $K$ is the number of feedback values and $\\kappa$ is a constant that increases exponentially in terms of the diameter of the parameter domain.\nThe proof seems to be correct.", "weaknesses": "**Lower Bounds**\n\nImproving the regret bound with respect to $K$ seems like a minor contribution. Especially, since there is no comparison with the lower bound on regret, it is unclear if the improvement in the regret bound with respect to K is theoretically significant.\n\n**Novelty of Analysis Techniques**\n\nMost of the techniques used in this paper are quite similar to the generalized linear bandits (GLB).\nEspecially, the proof scheme of the Theorem 1 is almost the same as logistic bandits or GLB.\nFurthermore, in Theorem 1, Lemma $6$ plays a crucial role, however, as mentioned in the Appendix, the difference from previous research lies solely in the bound on the norm of the error.\nThe remaining parts of the proof of Theorem 1 heavily depend on Abbasi-Yadkorietal. (2011).\nIt cannot be considered as a significant theoretical contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the careful review. In the following, we will first highlight the technical contribution of the paper then address your questions. If your concerns have been properly addressed, please consider updating your score to this paper. Thanks!\n\n---\n\n**Q1:** novelty of analysis techniques\n\n**A1:** We would like to note that there are two parts of the paper:\n\n- an inefficient algorithm with improved $K$ (Section 2.3)\n- efficient algorithm with further improved dependence on $\\kappa$. (Section 3)\n\nFor the first part of the paper, we agree with your comments. While we believe the improvement on $K$ is worthy of the community's attention, we recognize that the result is somewhat built upon standard analysis from existing logistic bandit literature, with refined conditions on $\\epsilon_t$. The result is not considered a main contribution of this work as we have chosen not to include it in the Introduction section.\n\nThe main contribution of this paper lies in **the second part**, where we developed novel efficient algorithms for both binary and multinomial logistic bandits problems with improved bounds. Developing a computationally efficient algorithm that also maintains statistical efficiency is a non-trivial task. Most previous methods [8,9,12]  with improved dependence on $\\kappa$ crucially rely on the inefficient MLE estimator. The only joint efficient algorithm is developed in the binary case and can hardly be extended to the multinomial setting. Additionally, even in the binary case, our method improves the computational efficiency of [10] from $O(\\log T)$ to $O(1)$. We have highlighted the technical challenge and our contribution in Remark 2 with more details explained in Section 3.3. \n\nIn summary, we recognize the reviewer's concern about the novelty of the first part but feel the second part, our main contribution, has been somewhat overlooked. This might be because we have spent slightly more pages than expected on the first part. In the next version, we will consider your comments and further emphasize the main contribution of the paper.\n\n---\n\n**Q2:** What is the memory complexity of each algorithm? \n\n**A2:**  At every iteration, our method requires to maintain the matrices $H_t,\\tilde{H}\\_t,\\nabla\\sigma(W)$ , the single round data point $(x,y)\\in \\mathbb{R}^d\\times\\mathcal{Y}$ and the model $W\\_{t+1}\\in\\mathbb{R}^{K\\times d}$. Therefore, the storage complexity of our algorithm is $O(K^2d^2)$,  a constant in terms of $T$. In the binary case, the storage complexity becomes $O(d^2)$ which is the same as the joint efficient algorithm [10]. \n\nHowever, the situation is different for the MLE-based algorithm [8,9,12]. This method requires storing all historical data to solve the optimization problem, leading to a storage complexity $O(dt)$ for round $t$. Additionally, the MLE-based algorithm must store the matrix $H_t^{-1}(W)\\in\\mathbb{R}^{Kd\\times Kd}$ to perform the optimistic rule, as dictated by equation (4). Therefore, the total storage complexity of the MLE-based method amounts to $O(dt + K^2d^2)$. \n\nIn summary, the storage complexity of our algorithm is the same as [10] and substantially improves the MLE-based method [8,9,12]. Thank you for the comments. We will add more discussion on the storage comparison in the revision.\n\n---\n\n**Q3:** Does this algorithm match the lower bound? Is there any analysis for the lower bound of this setting?\n\n**A3:** Since the binary logistic bandit problem is a special case of the multinomial logistic bandit, the lower bound established in the binary case also holds for the multinomial case. First, as outlined in Remark 3, the minimax optimal rate for the binary case is $O(\\sqrt{T/\\kappa_*})$  as established by [9]. Our method can achieve this rate up to logarithmic factors. Besides, in Remark 3, we also provide a discussion on the tightness of the bound in terms of $\\kappa$ for the multinomial case. While we admittedly found it challenging to achieve the $O(\\sqrt{T/\\kappa_*})$ bound, our algorithm has already achieved **the best known result** for the problem. It is an intriguing open question whether the $O(\\sqrt{T/\\kappa_*})$ regret bound is achievable in the MLogB problem. Furthermore, as we mentioned in Remark 1, the optimality of the $O(K)$ dependence has been discussed in [12] (the paragraph under Theorem 3), which demonstrates the tightness of our bound. \n\n---\n\n**Q4:** What causes the improvement of the regret bound? From the new analysis scheme? or finding better parameters? If I correctly understand the paper, the improvement of the regret bound is just caused by changing the condition...\n\n**A4**: As we have discussed in response to Q1, the main contribution of this paper is to provide an **efficient algorithm** with an improved bound. The improvement of our algorithm crucially relies on novel analyses, which we highlight in Remark 2. First, to achieve the improved dependence on $\\kappa$ in the MLogB problem, we introduce a novel intermediary decision that helps us prove a tight confidence set for the efficient online estimator. Besides, to reduce the computational complexity of the algorithm from $O(\\log T)$ to $O(1)$, we carefully exploit a negative term in the analysis, which helps to eliminate the requirement of learning with the original loss, thus speeding up the algorithm. Thank you for the comment. We will further highlight the related part to make the technical contributions of this paper more accessible."}, {"review_id": "gcr3ESAfwm", "reviewer": "Reviewer_Rks7", "summary": "This paper considers a generalization of the (binary) logistic bandit problem to the multinomial setting, significantly improving the state of the art for that problem and even for the special binary.  For the binary logistic bandit problem, many (earlier) algorithms proposed were not optimal; their regret bounds depended on a potentially large problem dependent parameter $\\kappa$ capturing the nonlinearity of the reward function.   Recent works were able to remove regret dependence on that parameter $\\kappa$, though had high per-round computation (depending on the horizon $T$).  \n\nThe authors propose an algorithm that (up to $\\log$ terms) achieves optimal regret bounds even when specialized to the well-studied binary logistic bandit setting with per round constant computation.  Furthermore, compared to prior work for the more general multinomial setting, they not only both obtain better regret (independent of the parameter $\\kappa$) but do so with faster per-round computation (constant instead of $O(T)$).\n", "questions": "\n#### Minor editing suggestions\n- For Table 1, I’d suggest including a comment in the caption about $\\kappa$ and $\\kappa_*$ (in addition to the later discussion in the main text).\n- In the problem formulation explicitly mention whether or not there are there any assumptions about $\\mathcal{X}$ (finite, convex, etc.).\n- I’d suggest re-ordering lemmas in C.1.2 (proof of lemma 6 depends on lemma 7, proof of lemma 7 depends on lemma 8)\n- For experiments, does MNL-UCB reduce to LogUCB1? If not, I’d (mildly) suggest including it in Figs 1 (a)-(b) for further reference of how well state-of-the-art multinomial methods perform against methods specifically designed for binary setting.\n#### Spelling, grammar \n- Line 52 argmax subscript ‘$x \\in W$’\n- line 276 ‘linearlized’\n- line 289 ‘logistc’\n- line 312 ‘radio’\n- Line 953 ‘trails’\n- line 537 ‘on the an’\n - Line 571 ‘anlaysis’\n- there were more I did not bother to list\n", "limitations": "It is fine", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- For the multinomial setting, the proposed algorithm significantly improves on the state-of-the-art both in terms of regret bounds (esp. removing the dependence on $\\kappa$) and computation (from $O(T)$ per round computation to $O(1)$).  In simple experiments, this is backed up with a (slight) reduction in empirical cumulative regret but much faster run-time.\n- Impressively, the proposed algorithm even improves on the state of the art for the (binary) logistic bandit setting.  Among computationally efficient ($O(1)$ per-round complexity) methods it has better regret bounds (also in simple experiments significantly lower empirical cumulative regret with competitive run-time).  Compared to ada-OFU-ECOLog the results are more nuanced (the proposed method has better regret for small horizons but worse regret for large horizons; takes half as long for a horizon of $T=1200$).\n- The algorithm and regret analyses do build on recent advances in (binary) logistic bandits, but non-trivially so.\n- Overall I found the writing clear and well-organized.   Table 1 and the remarks throughout comparing and contrasting to closely related works were helpful.  \n", "weaknesses": "\n#### Major\nI do not have any major concerns.\n\n#### Minor\n- Appendix A includes discussion on differences between the problem set up of multinomial logistic bandits considered in this paper and the problem of multinomial Logit (MNL) bandits which has been considered in several recent works.  This is only a minor concern, but given close connections of both to binary logistic bandit problems, a slightly more detailed discussion of similarities (if any) with OFU based methods and analyses (like with [33] Agrawal et al.) could be helpful.\n\n\n- There is an experimental design based approach for the binary setting (Mason et al. “An Experimental Design Approach for Regret Minimization in Logistic Bandits” in AAAI 2022) that I don’t think is cited.  I did not look carefully into it regarding time complexity so do not know whether it would be competitive with (ada)-OFU-ECOLog or not. \n\n- For the experiments, the $\\sqrt{T}$ dependence does not kick in for the horizon $T=1200$ (i.e. the regret appears linear).  For Fig 1(a) ada-OFU-ECOLog is initially worse but its regret is visibly concave and catches up around $t=800$.  I would suggest additional experiments with a longer horizon (maybe just with  ada-OFU-ECOLog and OFU-MLogB) to examine how long OFU-MLogB exhibits near-linear regret (and consequently how big that regret gap can grow).   Just to be clear, I think it is impressive that OFU-MLogB is better for smaller $t$ and $t$ on the scale of $10^4$ or $10^5$ might be unrealistic for applications, but the linear regret is a bit concerning. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your great appreciation and brining the related work to us! In the following, we will address your questions. We will further improve the paper according to your suggestions.\n\n---\n\n**Q1**: a slightly more detailed discussion of similarities (if any) with OFU based methods and analyses (like with [33] Agrawal et al.) could be helpful.\n\n**A1**: Thank you for the constructive commons. We provide more detailed comparison between MNL and MLogB problem as follows. \n\n- From the problem setup view, both settings utilize the multinomial logistic regression model to capture the probability of feedback, and they can be seen as generalizations of the binary logistic bandit problem. However, the main difference is in the mechanism to generate the feedback. The MLogB problem considers the case where there could be multiple feedbacks for the selected arm. While the MNL problem focuses on situations where the algorithm can submit multiple arms, but the feedback exhibits a binary value.\n\n- For the algorithm design view, the optimistic in the face of uncertainty (OFU) principle can be applied to both settings. However, the different problem setup leads to different algorithm design details and challenges. For instance, when analyzing the concentration property of the parameter estimator, one of the main challenges of MLogB is to handle the multinomial random noise $\\epsilon_t\\in\\mathbb{R}^{K}$ while MNL has to tackle the potentially related arm set for each iteration.\n\n- The previous work [33] proposed a UCB-type algorithm with an improved $\\tilde{O}(\\sqrt{T})$ bound for the MNL problem. Apart from the differences in problem setup, the main distinction between our work and [33] is that the previous work still employs an MLE-based algorithm, requiring $O(T)$ time complexity to solve the optimization problem. We believe extending our algorithm to the MNL setting to achieve the $\\tilde{O}(\\sqrt{T})$ bound with constant computational cost would be an interesting direction.\n\n---\n\n**Q2**: There is an experimental design based approach for the binary setting.\n\n**A2:** Many thanks for sharing the paper! We were not aware of it and will add the result to Table 1 for a more comprehensive comparison. In the paper, the experimental design approach has to solve a min-max optimization problem to select the arm (line 12 of Algorithm 2). It still seems unclear how to solve this min-max optimization problem efficiently.\n\n---\n\n**Q3**:  I would suggest additional experiments with a longer horizon (maybe just with ada-OFU-ECOLog and OFU-MLogB) to examine how long OFU-MLogB exhibits near-linear regret.\n\n**A3**: Thanks for the suggestions. We agree that the time step is somewhat short in the current experiments. We have conducted additional experiments with a longer $T$ to test our method. Please kindly refer to the global rebuttal for more details. Thanks!\n\n---\n\n\n**Q4**: For experiments, does MNL-UCB reduce to LogUCB1?\n\n**A4**: Yes, MNL-UCB can be seen as a counterpart of LogUCB1 for MLogB problem. We will make this clear in the revision.\n\n---\n\n**Q5:** about other editing suggestions and grammar:\n\n**A5:** We sincerely thank the reviewer for the detailed check of our paper. We will revise the paper according to your suggestions. Many thanks!"}, {"review_id": "5g5d0k4YGo", "reviewer": "Reviewer_6tgu", "summary": "This paper considers Multinomial Logistic bandits (the extension of the usual logistic bandit model to a setting where there are more than two possible outcomes - e.g. in advertising one picks an action in response to a context and may observe 'no click'/'click'/'save for later'/etc instead of just 'no click'/'click'). \n\nThis problem has been previously considered in work such as Amani and Thrampoulidis (2021) where an optimistic algorithm with near optimal dependence on T (up to logarithmic factors) has been derived, but the focus of this paper is on algorithms with improved computational efficiency, and optimal dependence on the parameter $\\kappa$. Dependence on this parameter $\\kappa$ has been the focus of a series of recent papers on bandit problems involving the logistic function, as many algorithms with an optimal dependence on $T$ can nonetheless have a poor dependence on $\\kappa$ which in turn brings an exponential dependence (in terms of worst-case performance) on other problem parameters.\n\nThe present paper first improves the MNL-UCB algorithm of Amani and Thrampoulidis by providing a sharper tail-inequality for the MLE under the multinomial model, before providing the main contribution: the OFU-MLogB algorithm, and analysis of its regret and efficiency. The proposed algorithm avoids costly inference by replacing maximum likelihood estimation with online mirror descent, and avoids costly optimisation for the confidence set via an alternative construction of reward. The result is an algorithm with no leading order dependence on $\\kappa$ and $O(1)$ computational cost per round.", "questions": "- What do you see as the utility of the algorithm presented in Section 2.3 over OFUMlogB? If there is not one particularly, and it is just a way to introduce important concepts and provide a correction to [12] and/or state an improved concentration result, potentially of independent interest, can you make that clearer from the outset?\n\n- I think Theorem 2 is slightly informal: I guess that you mean the sequence of arms selected by the algorithm using decision rule (5) achieves this regret, but how is this algorithm initialised? What is its first selection, or selections until such a point as the parameter estimates are well defined?\n\n- Which MNL-UCB are you testing in the experiments? The original from [12] or the improved one analysed in Theorem 2?\n\n- The confidence bands on the regret presented in the Appendix are very wide. They suggest less of a statistically significant difference than the plots in the main body. I think you need to move a discussion of this to the main text, and offer some discussion as to whether the ordering of the algorithms remains stable across trials, or whether that is random also. I feel that this experiment probably could have been better designed, and would be yet more satisfied if it was possible to provide a more extensive experiment from which more meaningful conclusions could be drawn.\n\n- Minor: at line 167, I don't think you ever really define 'feedback number' as a piece of terminology. I suggest that you should.\n- Minor: at line 255, should say 'condition as Theorem 3'\n- Minor: at line 67, it may be worth making clear that MNL-bandits (which people could confuse this model with) specifically will be addressed in Appendix A, it was something I was concerned was missing until I got to the end.\n- Minor: at line 312: radio -> radius\n", "limitations": "Appropriate for the nature of the paper.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This is a welcome contribution for the literature on contextual bandits. Improvements regards to dependence on $\\kappa$ have been important steps forward in this area for various logistic bandit problems in recent years and this development is also likely to be impactful and useful.\n\nI find the paper to be well researched and written. There are a few minor points as discussed below, but I think the paper is generally thoughtfully structured. For instance I liked how the OFU-MLogB algorithm was motivated in terms of certain concerns about efficiency and these same headings were used to frame the discussion of the algorithm's structure. \n\nAs far as I can tell the theoretical results are derived correctly, and the analytical work is sound. I have not had as much time as one would like to be 100% confident in this, so this does impact my confidence score.", "weaknesses": "I don't have too much to criticise in terms of the originality and significance of the paper: its contribution is an improvement upon flawed but still somewhat practically useful algorithms, so it is not a revolutionary one, but I think it is nonetheless meaningful and appropriate for NeurIPS.\n\nI have a few points for clarification regards to the writing, experimental work, and points that I think would benefit from extra detail which I describe below, and if these are adequately addressed I should be able to increase my score following rebuttal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive evaluation and constructive comments for this paper! In the following, we will address your questions. We will further improve the paper according to your suggestions.\n\n---\n\n**Q1**: What do you see as the utility of the algorithm presented in Section 2.3 over OFUMlogB?\n\n**A1**: Thank you for the helpful comments! As you have mentioned in the review, we regard the jointly efficient algorithm OFU-MLogB as the main contribution of this paper. The purpose of Section 2.3 is first to introduce the important concept of logistic bandit and then state the improved concentration results that can be potentially useful. In the next version, we will highlight the utility of section 2.3 at the beginning of the section. Thanks!\n\n---\n\n**Q2:** I think Theorem 2 is slightly informal: I guess that you mean the sequence of arms selected by the algorithm using decision rule (5) achieves this regret, but how is this algorithm initialised? What is its first selection, or selections until such a point as the parameter estimates are well defined?\n\n**A2:** Thank you for pointing this issue out. For the first round, the learner can randomly select any arm for the decision set $\\mathcal{X}$. After that, the decision rule (5) is well-defined. We will provide a more formal description of the algorithm in the revision.\n\n---\n\n**Q3:** Which MNL-UCB are you testing in the experiments? The original from [12] or the improved one analysed in Theorem 2?\n\n**A3:** We implemented the original algorithm from [12]. As discussed in Q1, the purpose of the algorithm in Section 2.3 is to first introduce important concepts for the MLE-based logistic bandit method and then to bring the issue of the dependence on $K$ to the community's attention. Therefore, we initially did not consider the algorithm in Section 2.3 as a contender to be tested in the experiments. However, we admit that an empirical comparison between MNL-UCB and the improved version could further help us understand how significant the improvement on $K$ will be. We will take this as future work.\n\n---\n\n\n**Q4:** The confidence bands on the regret presented in the Appendix are very wide....a more extensive experiment from which more meaningful conclusions could be drawn.\n\n**A4：**Thank you for the thoughtful comment! During the rebuttal phase, we realized that there could be a better way to organize our experimental results. In the original experiments, we randomly selected the arm set for each set of 20 trials, leading to a high variance in the results. We have provided a new version of our experiments for the binary case, in which we still run the algorithm for 20 trials, but the arm set is fixed. Please kindly refer to the PDF file attached to the global response for more details.\n\n---\n\n**Q5:** it may be worth making clear that MNL-bandits (which people could confuse this model with) specifically will be addressed in Appendix A\n\n**A5:** Thank you for the suggestions. In the next version, we will include part of the related work discussion with the MNL setup in the main text. \n\n---\n\n**Q6:** other comments on the minor issues:\n\n**A6:** We sincerely thank the reviewers for the detailed check. We will revise the paper accordingly."}, {"review_id": "ImqFRi1XZT", "reviewer": "Reviewer_oJs3", "summary": "This paper proposes a computationally efficient algorithm for multinomial logistic bandit with improved regret and computation cost. The algorithm uses online mirror descent and new approximation to efficiently compute consistent estimator and construct optimistic reward. Experimental results show improved regrets and computational costs of the proposed algorithm.", "questions": "1. Is there any trade-offs between the computational efficiency and the accuracy of the estimator?\n2. Could you explain why the slope of the regret of MLogB increases in Figure 1 (c)?\n3. If the number of iterations $T$ increases, can the proposed algorithm find a better policy to reduce the increment of the regret?", "limitations": "Yes. This work is mostly theoretical and potential negative societal impact is unseen.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The contributions are clear, concrete, and well-presented. Improving the regret and computation cost and extending binary cases to multinomial is significant. Applying online mirror decent, novel approximation, and novel construction of optimistic reward to reduce the computation cost are novel and significant in contextual bandits under the parametric model.", "weaknesses": "1. Discussion and experimental results on whether there is a trade-off to gaining efficiency would be helpful.\n2. In experimental results, while the reduction of the computation cost is significant, the reduction of regret seems minor. More experiments are needed to validate the improvement of the proposed algorithm in terms of regret.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive evaluation of this paper and the insightful common! In the following, we will address your questions and will improve the paper according to your suggestions.\n\n---\n\n**Q1:** Discussion and experimental results on whether there is a trade-off to gaining efficiency would be helpful.\n\n**A1:** Thank you for the insightful question. There is indeed a trade-off between computational efficiency and the quality of the estimator. This trade-off can be observed by comparing our update rule $W_{t+1} = \\arg\\min\\_{W\\in\\mathcal{W}}\\langle \\nabla\\ell_t(W_t),W\\rangle + \\frac{1}{2}\\Vert W-W_t\\Vert_{\\tilde{H}\\_t}^2$  with the one $W_{t+1} = \\arg\\min\\_{W\\in\\mathcal{W}}\\ell_t(W) + \\frac{1}{2}\\Vert W-W_t\\Vert_{H_t}^2$ used in [10]. The former is known as a standard online mirror descent (OMD), while the latter is referred to as implicit OMD, which updates on the original loss function instead of the linearized approximation.\n\nIn the online learning literature, both algorithms attain the $O(\\sqrt{T})$ minimax regret bound. However, implicit OMD has been observed to enjoy superior empirical performance [1] and has been proven to perform better than OMD when $\\{\\ell_t\\}_{t=1}^T$ is stable [2]. The price for the better performance of implicit OMD is increased computational complexity, as it has to solve a convex optimization and requires $O(\\log T)$ time complexity. \n\nOur experiments (especially the updated ones during the rebuttal phase) further demonstrate this trade-off, as the performance of our algorithm is slightly inferior to ada-OFU-ECOLog proposed by [12], but with improved computational efficiency. In the next version, we will add more discussion on the trade-off between computational efficiency and statistical efficiency.\n\n**Ref:** \n\n[1] Kulis and Bartlett. Implicit online learning. ICML 2010.\n\n[2] Campolongo and Orabona. Temporal variability in implicit online learning. NeurIPS 2020.\n\n---\n\n**Q2:** Could you explain why the slope of the regret of MLogB increases in Figure 1 (c)?\n\n**A2:** We think there are two reasons: the first is the time horizon $T$ could be somewhat short to reflect sublinear regret. Even in the binary case, the contenders (OFU-MLogB, LogUCB1 and OL2M) appear to exhibit a linear regret within $T=1200$. The second reason might be that the results are averaged over 20 trails with randomly selected arm set. As shown in the additional experiments, the performance of all contenders are highly affected by the shape of the arm set. The reported averaged result could have a high variance.\n\nTo better illustrate the performance of our algorithm, we have conducted additional experiments with longer time horizon $T=6000$ and fixed the arm set. Due to the limited time,the experiments are  conducted on the binary case. We are happy to provide more results for the multinomial case latter. Please refer to the global response for more details. Thanks!\n\n---\n\n**Q3:** If the number of iterations $T$ increases, can the proposed algorithm find a better policy to reduce the increment of the regret?\n\n**A3:** Thanks for the suggestions. We have conducted additional experiments with a longer $T$ to test our method. Please kindly refer to the global rebuttal for more details. Thanks!"}]

Author rebuttal:
We would express our heartfelt thanks to all reviewers for their careful review and constructive feedback. After carefully considering the comments from reviewers XVWd, Rks7, 6tgu, and ojs3, we conduct additional experiments to support the effectiveness of our algorithm by a more suitable way of organizing the results. The results are presented in the attached PDF.

**Setup for original experimental**. In Section 4, we report the average performance of all compared algorithms over 20 trials. As detailed in Appendix E (sorry for that, we should mention this in the main text), the arms are randomly sampled in each trial of our experiments, which finally leads to a result with an inherently large variance. 

**Setup for additional Experiments**: During the rebuttal, to more accurately present the empirical performance of the compared algorithms, we reorganized the experiments by **fixing the arm set** for the 20 trials. In the attached PDF, we report the mean and variance of the compared algorithm across these 20 trials, under 6 different configurations of the randomly generated arm set. Additionally, we extended the experiment for a longer time horizon with **$T=6000$**. The results show that OFU-MLogB is comparable (slightly worse) with the state-of-the-art joint efficient algorithm for the binary case (ada-OFU-ECOLog), but achieves much better performance than O2LM.

Due to time constraints, we were only able to conduct the experiments for the binary case. We are happy to provide additional results for the multinomial case at a later date. Thanks!

Meta-review: On the fundamental problem of online multi-class logistic bandits, this paper makes a solid contribution of improving the regret bound significantly and improving the computational complexity.
Decision: Accept (spotlight)