Yu-Jie Zhang¹ Masashi Sugiyama 2,1 1 The University of Tokyo, Chiba, Japan ² RIKEN AIP, Tokyo, Japan
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 O (log T ) to 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 Ö ( K √ T ) regret bound with O (1) computational cost per round. The result not only improves the Õ ( K √ κ T ) bound for the best-known tractable algorithm—where the large constant κ increases exponentially with the diameter of the parameter domain—but also reduces the O ( T ) computational complexity demanded by the previous method.
1
Introduction
The stochastic linear bandit (SLB) [1, 2, 3] problem is a natural generalization of the classic stochastic multi-armed bandit problem [4] by incorporating side information into the decision-making process. In the SLB problem, a linear model is used to characterize the relationship between the reward r t ∈ R and the learner's action x t ∈ X ⊂ R d , whereas such an 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 case [7, 8, 9, 10]. The reward r t ∈ {0, 1} exhibits a binary value and the probability is modeled by Pr[r t = 1 | x t ] = σ( w ξ x t ), where σ( z ) = 1/(1 + exp(−z)) is a non-linear link function and w ∗ ∈ W ⊂ R d is an unknown parameter. Compared to the SLB model, the logistic bandit model provides a 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 a basic setting for understanding the impact of non-linearity of the reward on the decision-making process. In this paper, we investigate a more general multinomial logistic bandit (MLogB) problem [11], in which the learner's action x t results in feedback y t that could have K + 1 possible outcome values. The probability of each outcome is characterized with a logistic model (the formal definition is 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 to cart", "view related item", and
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 [12, 13], the transition matrix is approximated using a linear model, which enables the application of the SLB method for balancing the exploration-exploitation 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 Table 1, 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 κ = maxxεχ,wεW 1/σ′( w T x ), a crucial parameter capturing the non-linearity of the reward function. Since the binary logistic bandit is a special case of the generalized linear model, the result from [5] implies an Î ( κ √ T ) bound. However, the parameter κ 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 [9], where the paper presents an algorithm that achieves the nearly minimax optimal bound Ö( √ T / κ ⋆ ). Here, κ ⋆ = 1 /σ ′ ( w ⋆ x ⋆ ) is the non-linear parameter associated with the best action x 。 = arg max x ∈ x σ ( w ∗ x ), suggesting that non-linearity might be advantageous for statistical efficiency, rather than a hindrance. Alongside statistical efficiency considerations, the non-linearity of the feedback raises concerns about the algorithms' computation and storage efficiency. The methods [8, 9] with improved dependence on κ usually require storing and optimizing over all historical data to estimate the unknown parameter, leading to an O ( t ) computation and storage cost at round t ∈ [ T ]. 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 κ . Recently, a jointly efficient algorithm was proposed by [10], which achieves the optimal dependence on κ with a O (log t ) computation cost and constant storage cost per round. However, it 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 [11]. This method achieves an Ö ( K √ R T ) regret bound, bearing an O ( √ R ) dependence on the exponen- tially large constant. Moreover, it still demands O(t) computation and storage costs to optimize over all past data. The same study also introduced an Ö ( K 3/2 √ T ) bound with improved dependence on κ . Yet, this solution leans heavily towards theoretical insights and is intractable in implementation [11, 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 4. Our Results. In this paper, we provide an algorithm with both statistical and computational efficiency.
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 [11], and propose an improved version with better dependence on the exponentially large constant κ and the number of outcome values K .
Problem Formulation
2.1
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 t , the learner will first select an action x t ∈ X  from the feasible action set X ⊆ R 2 and then submit it to the environment. After that, a response y t ∈ { 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 ∈ N . Specifically, the MLogB problem assumes that each outcome k ∈ [ K ] is associated with a ground-truth parameter w ( k ) ∈ R d and the probability of the outcome Pr [ Y t = k | X t ] follows the logistic model,
RK×d the matrix for the For notational simplicity, we denote by W, unknown parameter and define the softmax function σ
where [ ] k denotes the k -th entry of the input vector. Then, the probability of the outcome can also be written in a concise way as Pr [ y t = k | x t ] = [σ(W ∗ x t )] k . Besides, each outcome is associated with a fixed and known reward. We denote by ρ k ∈ R + the reward for the outcome k ∈ [ K ], and let ρ 0 = 0 for the outcome θ t = 0. Therefore, the expected reward of the learner's action x f is defined as r(x t ) = ∑ k = 0 Pr(y t = k | x t ] · ρ k = ρ T σ(W ∗ x t ). Let x ｡ = arg max x ∈ x ρ T σ(W ∗ x ). The goal of the learner is to maximize the cumulative reward, which is equivalent to minimizing the regret
When K = 1 and ρ 1 = 1, MLogB recovers the binary logistic bandit by r(x) = σ(w , x) = 1/(1 + exp( − w , x)), where w x ∈ R d is a unknown parameter. Exponentially Large Constant κ . In the logistic bandit problem, the non-linearity of the reward function is captured by the gradient of the link function ∇σ : z ∈ R d → diag(σ(z)) − σ(z)σ(z) T The analysis typically that requires that the gradient term is bounded from below and thus one would define the constant κ W ∈ W and x ∈ X , where λ min : RK×K → RK is the minimum eigenvalue of the input matrix. In the binary case ( K = 1), one can show that κ = maxwεW,xεx {1 + exp(w Tx ) + exp(−w Tx )} = O( e S X ), where S and X are the diameters of the parameter space W and action space X . In the multinomial case, the paper [11, Section 3] also shows that κ is an exponentially large constant with respect to S and X . Thus, an algorithm with improved dependence on κ is demanded.
2.2  Assumptions and Notations
Same as the previous work for multinomial logistic bandit [11], we use the following assumptions. Assumption 1. The norm of the action is bounded by 1, i.e., ‖ x ‖ 2 ≤ 1 for any x ∈ X . Assumption 2.  The reward vector ρ ∈ R ξ  and its norm is bounded by R , i.e., ∥ ρ ∥ 2 ≤ R . Assumption 3.  The norm of the parameter W* ∈ R K × d is bounded by S , i.e., ||W*||F ≤ S , where || || F denotes the Frobenius norm of a matrix. Assumption 4.  Let ∇σ(z) : z ∈ R d → diag(σ(z)) − σ(z)σ(z) T . For all x ∈ X and W ∈ W , we have λmin(∇σ(W×)) ≥ 1/κ and λmax(∇σ(W×)) ≤ L, where λmax : RK×K → RK and → R K take the maximum and minimum eigenvalues of the input, respectively. Amin：RK×K Other Notations. The following notations are used in the paper. Given a K -by-d matrix W , we denote by W ′ its K d -dimensional vectorization. For any positive semi-definite H ∈ R Kd×Kd , we define the norm ||W || H = /〈 W , HW 〉 . The notation ® is used for the standard Kronecker product. When the input is a vector W ∈ R K d , we treat it as a K d × 1 matrix. Moreover, for any symmetric use F t = σ ( x 1 , y 1 , . . , y t − 1 , x t ) to denote the filtration, which encodes the information collected so far before receiving y t . Finally, O( · ) is used to highlight the dependence on d , K , κ , and T . With O( · )-notation, we further hide the dependence on the dimension d and logarithmic factors.
Optimistic Algorithm with Improved Bound
2.3
This part revisit the principle of optimism in the face of uncertainty (OFU) [15] and introduces an improved version of the MNL-UCB algorithm [11] with better dependence on κ and K . Optimism in the Face of Uncertainty. The OFU principle is a fundamental paradigm for addressing the exploration-exploitation dilemma in bandits. At each iteration t , the algorithm selects the arm by the rule x t = arg max x ∈ x  ř t ( x ), where ř t ( x ) is an optimistic estimate of the true reward r ( x ) satisfying ñ t (x) ≥ r (x) for all x ∈ X . Based on the OFU rule, one can show that Reg T ≤ ( f = 1 ( ñ ( X t ) − r ( X t )), indicating that a tighter optimistic estimate ñ t will lead to a tighter regret bound. Therefore, designing a tight optimistic estimate  r t is essential for the OFU algorithm. In the context of the logistic bandit, a common practice is to construct a confidence set C t ⊂ R K×d 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 ∈ X by ñ i (x) = arg max W ∈ c, ρ T σ ( Wx ). A tighter confidence set will lead to a tighter optimistic reward, and thus resulting in 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 to learn the unknown parameter W *. Specifically, after observing the action-feedback pairs {( x s , y s )} ξ = 1 , one can train the model by
where ℓ t (W) = ∑ k = 0 1 { y t = k } · log (1/[ σ (W × t )] k ) is the multiclass logistic loss established over ( x t , Y t ) and λ > 0 is the regularization parameter. Let W ∈ R K d be the vectorized parameter. We also define the gradient g t ( W ) and the Fisher information matrix H t ( W ) of the logistic loss by
where W ∈ R K d is the vectorized parameter and ∇ σ : z → diag(σ(z)) − σ(z)σ(z) T is the first order derivative of the reward vector σ (z). Then, we are ready to present our confidence set for the maximum likelihood estimator, which exhibits O ( √ K ) improvement over that in [11]. Theorem 1. Set the parameter λ = O(dK log( t/δ )) with a certain δ ∈ (0,1). For each iteration t ∈ [T], we define the confidence set as
where β t (δ) = 4 √ K d (1 + δ) log (2 (1 + t/d) /δ) = O (√ ∂K log t) is the radius of the set and W = {W ∈ R K × d | ||W || F ≤ S } . Then, we have Pr [∀t ≥ 1,W ∗ ∈ C t (δ)] ≥ 1 − δ. One advantage of the confidence set (4) is that its radius β t (δ) is independent of the exponentially large constant κ and thus is much tighter than the confident set constructed for the generalized Algorithm 1 MNL-UCB+ Input:  regularization coefficient λ, probability δ. 1:  Initialize H 1 = λ I κ d and W MLE as any point in W 2:  for t = 1, . . . , T do Construct r t and select the arm by (5). Then, the learner receives y t . 3: 4: Train the estimator W t +1 by (3) and construct the confidence set C t +1 (δ) as (4). 5:  end for linear bandit [5], whose radius exhibits a linear dependence on κ . The κ -independent set are first established by [8] for the binary logistic bandit problem and then adapted to multinomial setting by [11] with refined analysis on the self-normalized martingale tail-inequality for multinomial noise. Our confidence set is tighter than that in [11] by improving the radius from β t (δ) = O ( K √ d log t ) to β έ (δ) = O (√ α K log ī ). The improvement is based on a slightly refined self-normalized tail- inequality for the multinomial case, whose formal description is provided in Appendix C.1. Construction of Optimistic Reward. Based on the confidence set (4), we can construct the optimistic reward and select the arm for each iteration by ñ t (x) = arg maxw ∈ c t ( δ ) P T σ ( W x)     and     x t  = arg max × ∈ W ñ t (x).
We have following guarantee for the algorithm based on the MLE (3) and the selection rule specified in (4) and (5). We summarize the algorithmic procedure in Algorithm 1. Theorem 2.  Under the same conditions as Theorem 1. Let δ ∈ (0,1]. Algorithm 1 ensures Reg T ≤ O (min{d log T √ κ K T , dK log T √ T + κd² K log ² T } ) with probability at least 1 − δ when we set the parameter λ = O(dK log(T/δ)). Remark 1 (Improved dependence on K and κ ). Our method achieves the O ( √ κ K T ) and O ( K √ T ) regret bounds for MLogB problem simultaneously. The first bound slightly improves the Ö( K √ RT ) guarantee of the MNL-UCB algorithm [11] by an O( √ K ) factor while the second one is independent of the exponentially large constant κ in its leading term. An O ( K ž √ T ) bound is also attained by [11]. However, their proposed method is intractable as its confidence set is established on all minimal elements of partially Loewner-ordered set C t (δ) ∩ W [11, Appendix D]. The computation cost of identifying all minimal elements and projecting onto the proposed confidence set is prohibitive. Our solution is free from such demands by using a different rule to construct the optimistic reward.
3
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 a technical highlight.
Efficiency Concerns
3.1
The algorithms for logistic bandit crucially rely on two components to ensure the statistical efficiency: the MLE (3) and the optimistic rule (5) for constructing  r t . 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, 8, 9, 11], MLE is a 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, as discussed in [10], the optimization of the MLE problem typically requires O ( t log(1/c)) gradient step to achieve ε -accuracy. Besides, the loss function L t is established on all historical data {( x s , y s )} s =1 , resulting in an O( t ) gradient query complexity for each gradient step and O ( t ) storage cost, and thus is inefficient. Computation and Storage Cost of Optimistic Reward Construction. The construction of the optimistic reward ī t (x) requires to solve the optimization problem (5). However, the objective Algorithm 2 OFUL-MLogB Input:  regularization coefficient λ , probability δ , step size η . 1:  Initialize H 1 = λ I κ d and W 1 ⁄ αs any point in W 2:  for t = 1, . . . , T do Select the arm by x t = arg max x ∈ x̃r t (x) and receive y t . 3: Update H t = H t + η∇σ (W t − x t ) → x t − 4: Update the estimator W f +1 for the next iteration by (6) 5: Update H t +1 = H t + ∇ σ (W t +1 × t ) ⊗ x t × T and 6: Construct the optimistic reward by ñ t +1(x) = ρ T σ (W ξ 1 ×) + εξ t 1(x) + εξ t 1(x) as (8). 7: 8:  end for function ρ T σ ( W x ) is non-concave and the decision domain C t ( δ ) is non-convex, making the maximization problem ñ t (x) = arg maxw ∈ c t ( δ ) ρ T σ ( W x ) computationally challenging. In the binary case, the paper [9] proposed a convex relaxation of the confidence set C t ( δ ), whereas the relaxed confidence set is still established on all historical data, resulting in O ( t ) time complexity and O(t) storage cost at iteration t . 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 an inferior regret bound of Ö( √ RT ). In the binary case, the work [10] proposed a jointly efficient algorithm, which achieved a nearly minimax optimal bound with O (log t ) computation cost per iteration and O (1) storage cost. However, as we will discuss in Section 3.3, it is hard to apply their analysis to the multinomial case.
3.2  Efficient Algorithm
In this section, we proposed a novel algorithm which only requires O (1) computation cost per iteration and O (1) 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:
where η > 0 is the step size to be specified later and the first iteration model W ′ 9 L can be initialized as any point in the domain W = {W ∈ R κα | ||W||2 ≤ S}. We set the matrix as H t = be updated incrementally. We show the online estimator (6) enjoys computational, storage, and statistical efficiency. Since (6) exhibits a standard online mirror descent formulation [17], it can be solved with a single projected gradient step with the following equivalent formulation by
For the gradient descent step above, the most time-consuming operation is maintaining the inverse of the matrix H t . Since ∇ σ ( W f − x t ) ⊗ x t × t is a rank-K matrix, it can be calculated by the Sherman- Morrison-Woodbury formula with O ( d 2 K 3 ) cost per round. As for the projection step, since H t is positive semi-definite matrix, it can be solved in O ( K 3 d 3 ) [18, Section 4] . * As a consequence, our algorithm achieves a light update with O (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 O (1) storage cost throughout the learning process. Moreover, the estimator is also statistically efficient. We can construct the following κ -independent confidence set similar to that in Theorem 1. Theorem 3. Let δ ∈ (0,1) and α = 2(1 + S ) + ln(K + 1). Set the parameter η = α /2 and λ = max{28K dα,7√δαS}. For each iteration t ∈ [T], we define the confidence set as
where βሮ(δ) = O ( log K log t √ K d ). Then, we have Pr [ ∀t ≥ 1, W ∗ ∈ C t (δ)] ≥ 1 − δ. Moreover, the computation cost of solving (6) is O (1) per round. Remark 2 (Comparison with the online estimator [10]). 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.3, the analysis for the binary setting is hard to be applied to the multinomial case. Specifically, the paper [10] has proposed an intermediary decision W t 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 a 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 a 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 {∇ ℓ t ( W f ), W } of ℓ t ( W ) with the adjusted local norm ‖ ‖ ♯ , . Our new algorithm not only enjoys a computation efficiency improvement from O (log t ) in [10] to O (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 C fL ( δ ) is convex, the optimistic rule (5) by ñ t (x) = arg min W ∈ c π ( δ ) ρ T σ ( W x) still involves inefficient non-concave optimization problem solving. In this part, we propose a novel optimistic reward that can be solved in a constant time per round. Proposition 1.  For any x ∈ X  and iteration t ∈ [T], the optimistic reward is constructed by r or (x) = ρ T σ(W ε or x) + εξ π τ(x) + εξ π d(x). (8) In above, εξπτ(x) = βft(δ) · ‖ H t − ² (I κ & x)∇σ(Wft(x)ρ‖ ² and εξπα(x) = 3R(βft)² · ‖ (I κ & x T ) H − 1 / 2 || ≥ are the bonus. Then, we haveﾃfl (x) ≥ ρ T σ (W ∗ x) for all t ≥ 1 and x ∈ X with probability at least 1 – δ. Proposition 1 constructs the optimistic reward by adding the "bonus" to the reward empirically estimated by W α . Different from the term used in [11], our bonus terms are independent of the exponentially large constant and thus can lead to an improved O ( K √ T ) bound. The optimistic rule (8) does not involve any optimization problem solving and can be calculated in an O (1) cost. Overall Algorithm and Guarantees.   We overall procedures in Algorithm 2. For the general multinomial setting, it ensures an Ö ( K √ T ) regret guarantee and an O (1) computation cost. Theorem 4.  Under the same condition as Theorem 3, Algorithm 2 ensures Reg T = O ( K d log K (log T ) * √ T + κ K * d 2 (log K ) 2 (log T ) 3 ) = Õ ( K √ T ). The computation cost of Algorithm 2 is bounded by O (1) for each round t ∈ [ T ]. Remark 3 (On the Ö( √ T / κ x ) bound). In the binary setting, [9, 10] show that an Ö( √ T / κ x ) minimax optimal is achievable with κ ⋆ = 1/σ ′ ( w T x ∗ ). However, due to the multinomial behavior of the feedback, it is unclear how to achieve such a rate in MLogB case (see the discussion in Appendix C.5). Besides, it also raises concerns about efficiency when applying the method devel- oped for binary case to multinomial setting. In particular, the O ( √ T / κ x ) is achieved by the rule arg max x ∈ X , w ∈ C t ( δ ) σ ( w ' x ) in [9, 10]. The optimization can be efficiently solved in the binary case since one can simply eliminate the non-linearity of the reward function by the relationship σ( z 1 ) > σ( z 2 ) for any z 1 ∈ R > z 2 ∈ 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 4, Algorithm 2 with the optimistic rule ñ t (x) = arg max w ∈ c π ( s ) w T × ensures Reg T ≤ Õ ( √ T / κ ⋆ ) with probability at least 1 − δ .
Analysis
3.3
This section presents the proof sketch for Theorem 3, 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 we update the model with the original loss function by W t+1 = arg min W ∈ W ℓ t (W) +予‖ W − W t ‖ H t , the arguments in [10] shows that the estimation error between W t+1 and W * can be bounded by their gap on the loss function
However, the update rule with original loss will lead to an O (log t ) computation cost per itera- tion. To facilitate a more efficient algorithm, we introduce the update rule with the linearized loss (∇ℓ t (W t ), W ) and the adjusted norm H t as (6). As we have shown in the proof of Lemma 12 in Appendix C.1. Denote by ℓ t (W) = (∇ℓ t (W t ), W) + f ‖ W − W t ‖ π ² ℓ t (W t ) the second-order surrogate of ℓ t ( W ). The efficient update rule will introduce an additional term
We handle the additional term by the self-concordant property of the logistic loss and exploiting a negative term ignored in the previous analysis. Since the logistic loss is a √ δ -self-concordant-like function [19, Lemma 4], then Theorem 3 of [19] indicates that the additional term can be bounded by
where ξ s ∈ R K d is on the line connecting W s +1 and W s . Besides, by a refined analysis of the online mirror descent (OMD) update (6), we identify an additional negative term − ∑ t = 1 ||W 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 is also found crucial in the gradient-variation regret of non-stationary online learning [20, 21] as well as its applications to game theory [22] and the SEA model [23]. Novel construction of the intermediary prediction. Then, we can further bound the right hand side of (9) by inserting an intermediary loss ℓ ε ( W ε ) as
In the binary case, inspired by the study [24] for the binary online logistic regression, [10] propose to construct ˜ w s = arg min w ∈ W s ℓ b ( w ¹ x s , 0) + ニm w − w s ∥ H s , where ℓ b is the binary logistic loss and W s  is a shrank decision domain. Then, both term (A) and term (B) can be bounded without the dependence on κ . However, the analysis for term (B) crucially relies on the condition |σ( ŵ¸¸ x s ) − y s | · |σ( ŵ¸¸¸ x s ) − 1 + y s | = σ ′ ( ŵ¸¸¸ x s ) to eliminate the dependence on κ, where y s ∈ {0, 1} is the one-dimensional feedback. It is hard to show such an relationship in the multinomial case since the feedback y s 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 it is possible to construct W t with the update rule developed in [25]. However, since the online update rule of [25] requires to perform over R K × d , the learned parameter would become unbounded, which makes it is hard to provide an upper bound for term (A). To this end, we design a new intermediary term by ℓ π ( Z s, Y s), where ℓ π is the multiclass logistic loss. The prediction is constructed by ˜ s = σ + ( Ew ~ ρ [σ( W × s )]) with the Gaussian distribution Ps, = N(Ws,αHz-1), where σ + is a pseudo inverse function of the sigmoid function σ. Such an integral construction ž s = σ + (EW~P s [σ(Wxs)]) is previously used in the online logistic regression literature [26, 27] but we tailored the tool to our analysis with a different construction of the distribution P s . Lemma 13 and Lemma 14 in Appendix C.1 shows that
Then, combining the upper bound of term (A) and term (B) and eliminating the additional term ∑ ξ = 1 || W s − W s+1 || H s with the negative term obtained by a refined analysis of online mirror descent, we complete the proof of Theorem 3.
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 Ö( √ RKT ) and Ö( K √ T ). † The tightness of these bounds, with respect to κ and T , was detailed in Remark 3. Regarding the number of feedback values K , [11] claimed the optimality of a linear dependence on K . However, our findings revealed a nuanced interplay between κ and K . The O( √ κ KT ) bound does not conflict with the lower bound argument by [11], given that the non-linear constant κ is also associated with K . Beyond κ , the norm of the unknown parameter S and maximum norm R of the reward vector ρ can also depend on K based on the problem's specifics. It is an interesting direction to understand the interrelation of these constants by establishing a lower bound. Additionally, our method has a linear dependence on d . In the finite-arm case, an O ( √ d ) dependence might be attainable with a SupLin-type algorithm [28]. Below, we introduce more related works on logistic bandit and the related topics. Logistic Bandit. While the logistic bandit is a specific instance of the generalized linear bandit model [5, 29, 30, 31, 32, 33, 34], the algorithms proposed for GLB tend to exhibit a linear dependence on the nonlinear term κ , 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, 9] mentioned in Section 1, for the N -arm case, [35] proposed an experimental design-based algorithm providing an Ö( √ d log NT / κ ⋆ ) regret bound with better dependence on d . However, the previous methods were built upon the MLE estimator, whose optimization demands O( t ) computation and storage complexity for the t -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 (log 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 κ (even in the lower order term) when the feasible domain is identical to the parameter domain, i.e., X = W . [37] further proved the κ -independent bound with weaker conditions. Multinomial Logit (MNL) Bandit.  Another relevant line of research is the multinomial logit contextual bandit problem [38, 39, 40, 41, 42], which generalizes the binary logistic bandit by allowing the learner to submit a subset of arms S t = { x t, i } {= 1 ∈ X to the users. The expected reward function is also modeled by the multinomial logit model: E [ r t | S t ] = ∑ x t , i ∈ S t , P t , i exp(w , ' x t , i )/(1+ E x t, i ∈ S t exp(w , t x t, i )), where ρ t, i is the reward for arm x t, i and w ∗ ∈ R d is an unknown parameter. There are also studies on the MNL bandit problem concerning the exponentially large constant κ . [42] proposed an optimistic algorithm with O ( d √ T ) regret bounds without κ in its leading term, which improves the O ( dκ √ T ) bound with better dependence on κ . Considering uniform reward, i.e., ρ t,i = 1 for all t ∈ [ T ] and i ∈ [ N ], [43] further showed an Ö ( d √ T / κ ∗ ) bound. To the best of our knowledge, all the existing methods with improved κ are established on the MLE estimator. It would be an interesting future direction to develop jointly efficient algorithm for the MNL bandit problem.
5
Experiments
This section validates the statistical and computation efficiency of the proposed method by experi- ments. We conduct a bandit learning for T = 3000 iterations. In each experiment, we run experiments on 6 random configurations, in which the arm set and the underlying parameter are randomly sampled. Specially, | X | = 20 actions are randomly sampled from a 2-dimensional sphere of radius 1. In the binary case, the norm of the unknown parameter w s is set as S = 5. In the multinomial case, we set K = 4 with S = 1. The reward vector is set as ρ = [0.25,0.5,0.75,1]. For each configuration, we report the averaged results over 10 trials. More details can be found in Appendix D. Experimental Results. Figure 4 provides a comparison of performance and computation costs in the binary case. The algorithm O2LM [7], which has a 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-art binary logistic bandit algorithm ada-OFU-ECOLog [10], our OFU-MLogB method has lighter computational overheads while preserving similar empirical performance. Figure 4 illustrates the comparison in the multinomial setting. Our algorithm is around 50 times faster than MNL–UCB [11] for running T = 3000 iterations and achieves better empirical performance. More experimental results on other configurations 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 (log t ) to O (1) per round while still preserving the O( √ T/ κ x ) minimax optimal bound up to logarithmic factors. A promising future direction is to consider the multinomial logit model in reinforcement learning. Besides, it is still open on how to achieve the Ö( √ T / κ ⋆ ) bound for the multinomial case.
Acknowledgments
YJZ and MS were supported by the Institute for AI 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. [1] Peter Auer. Using confidence bounds for exploitation-exploration trade-offs. Journal 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–256, 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, 2016. [8] Louis Faury, Marc Abeille, Clément Calauzènes, and Olivier Fercoq.  Improved optimistic algorithms for logistic bandits. In 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, Marc 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. UCB-based algorithms for multinomial logistic regression bandits. In Advances in Neural Information 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 (COLT), pages 4532–4576, 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 Algorithms. Cambridge University Press, 2020. [16] Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimiza- tion, 2(3-4):157–325, 2016. A modern introduction to online learning.  ArXiv preprint , arXiv: [17] Francesco Orabona. 1912.13213, 2019. [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, 2019. [19] Quoc Tran-Dinh, Yen-Huan Li, and Volkan Cevher. Composite convex minimization involving self-concordant-like cost functions.  In Proceedings of the 3rd International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences , pages 155–168, 2015. [20] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-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 Zhi-Hua Zhou. Adaptivity and non- stationarity: Problem-dependent dynamic regret for online convex optimization. ArXiv preprint , arXiv:2112.14368, 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 on 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 (ALT), 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 23692–23702, 2021. [28] Wei Chu, Lihong Li, Lev Reyzin, and Robert E. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS) , pages 208–214, 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-directed sampling. In Advances in Neural Information Processing Systems 27 (NeurIPS) , pages 1583–1591, 2014. [32] Marc 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-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, Iuliia 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. [38] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the mnl-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 to 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émie Périvier and Vineet Goyal. Dynamic pricing and assortment under a contextual MNL demand. In Advances in Neural Information Processing Systems 36 (NeurIPS), 2022. [44] Yurii E. Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms in convex programming. SIAM, 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 self-concordant functions: a recipe for newton- type methods. Mathematical Programming , 178(1):145–213, 2019. [47] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Online-to-confidence-set conversions and application to 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 (NeurIPS), 2020. This section collects several key properties of the logistic loss used throughout the paper. We have the following property of the multiclass logistic loss. Property 1. Let y ∈ Y with Y = {0} ∪ [K] and ℓ : RK × Y ↔ R be the multiclass logistic loss defined by
where σ : R K → [0, 1] K is the vector valued link function defined by [σ(z)] k = exp(z k )/(1 + ( ∑ j=1 exp(z j )) and [σ(z)] 0 = exp(z k )/(1 + ∑ j=1 exp(z j )). Let y = [1{y = 1}, . . , 1{y = K}] ∈ RK and σ k (z) = [σ(z)]k be 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 written as
where u k is the k-th entry of the vector u ∈ R K and E k ∈ R K×K is a "one-hot" matrix whose ( k, k )-th entry equals to 1 while others equaling to 0. Besides, e k is the one-hot vector whose k-th entry equals to 1. In the above, ∇ ž ℓ ( z, y )[u] = lim ℓ→ 0 t − 1 (∇ ž ℓ ( z + tu, y ) − ∇ ž ℓ ( z, y )) When we train a 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 t , Y t ) ∈ X × Y by
Then, the gradient ∇ℓ t (W) ∈ R K d and the Hessian ∇ 2 ℓ t (W) ∈ R K d×K d of the loss function with respective to the vectorized model W is given by ∇ℓｫ(W) = (σ(Wx t) − Yt) S x t  and  ∇ 2 ℓ t (W) = diag(σ(Wx t)) − σ(Wx t)σ(Wx t) Besides, we can obtain the gradient of the vector-valued link function as follows. Property 3.  Let the sigmoid function σ : RK → [0, 1] K  be defined as (1) and σ k (z) denote the k-th entry of σ(z). We have
In above, E k ∈ RK×K  is an all zero matrix except that its ( k, k )-th entry is 1. For the first order derivation, we can write it into a more concise formulation by the notation ∇σ(z) : RK → RK×
We have the following lemma for the logistic loss function. Lemma 1.  Let C > 0, a ∈ [−C, C] K , y ∈ {0} ∪ [K] and b ∈ R K . Then, we have
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 ℓ( Z, y ) = ∑ k = 0 1{ y = k} log (∑ k=0 exp([ž] j )/exp([ž] k ) , where ž ∈ RK+1 is a K + 1-dimensional input. One can connect the two logistic losses by ξ ([ z; 0], y ) = ℓ ( z, y ). Then, we can prove Lemma 1 by directly applying Lemma 4 of [27] with the augmented vectors ã = [a; 0] and b = [b; 0]. ● Then, we introduce the notion of self-concordant-like function, which generalizes the standard self- concordant notion. The self-concordant function is first introduced by [44] in the study of inner-point algorithm and the notion is further generalized by the following work [45, 19, 46] for analyzing the Newton-step methods. The self-concordant function enjoys several nice properties, which plays an important role in our local analysis. A comprehensive study for self-concordance function is provided by [46]. Here, we present the definition and necessary lemmas for our analysis. Definition 1 (Theorem 3 of [19]). A convex function ℓ ∈ C 3 : R d → R is M -self-concordant-like if and only if for any x , u 1 , u 2 , u 3 ∈ R d , we have
where ‖u‖z := √ u ¹ ∇ 2 f (z)u is the local norm over the Hessian ∇ 2 ℓ (z). The logistic loss is √6-self-concordant-like function. Lemma 2 (Lemma 4 of [19]). The logistic loss defined as (11) is √ 6 || x t || 2-self-concordant-like. The self-concordant function enjoys favorable properties, which help us to conduct local analysis for the logistic bandit problem. We list useful lemmas as follows. Lemma 3 (Bound of Hessian Map, Theorem 4(b) of [19]).  Let ℓ : R d → R be an M -self-concordant- like function. Then, for any z 1 , z 2 ∈ dom( ℓ ), we have e-M||z1-z2||2V2l(z1) < V2l(z2) < eM||z1-z2||2V2l(z1)
The following lemma is a consequence of the bound of the Hessian map. Lemma 4 (Corollary 2 of [46]). Let ℓ : R d → R be an M-self-concordant-like function. Then, for any z 1 , z 2 ∈ dom( ℓ ), we have
We can also have the bound on the function value of the self-concordant functions. Lemma 5 (Proposition 10 of [46]). Let ℓ : R d → R be an M-self-concordant-like function. Then, for any z 1 , z 2 ∈ dom( ℓ ), we have c( − M || Z 1 − Z 2 || 2 ) · || Z 2 − Z 1 || Z 2 ) − ℓ( Z 1 ) − ∇ ℓ( Z 1 ) T ( Z 2 − Z 1 ) ≤ c( M f || Z 1 − Z 2 || 2 ) · || Z 2 − Z 1 || Z 1 , where c : R → R is the coefficient function defined as c(x) = (e x − x − 1)/x 2 . This section we present the proof of Theorem 1. 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( √ K ) factor compared to the one obtained by [11]. The proof of Lemma 6 is provided in Appendix B.1.2 Lemma 6. Let { F i } i=1 be a filtration. Let { X i } i=1 be a stochastic process in B 2 ( d )  = { x ∈ R d | ||× t ||2 ≤ 1} such that x t is F t measurable. Let { ε t } t=1 be a martingale difference sequence such that Et E RK is Ft+1 measurable. Furthermore, assume that conditional on Ft, we have
Then for any δ ∈ (0, 1], we have
Lemma 6 is a counterpart of the variance-aware self-normalized tail inequality [8, Theorem 1] for the multinominal case. In comparison with the previously established result by [11], our inequality more effectively leverages the geometric structure of the noise in the multinomial logistic bandit problem, as indicated by the condition || ε t || 1 ≤ 2. The previous paper's condition, || ε t || 2 ≤ √ K , is relatively loose, ultimately resulting in an additional O( √ K ) term in the concentration inequality. Then, we introduce the main proof of Theorem 1 Proof of Theorem 1. The optimality of the MLE estimator indicates that g t ( W i NLE ) = ∇ A
The last inequality is by Lemma 6 since Σ(W*xs) = diag(σ(W*xs)) − σ(W*xs)σ(W*xs) Γ = E[eses T | Fs_
∥g t (W t − − g t (W ∗ ) ∥ H − 1 (W ∗ ) ≤ beta t (δ) = 4 t − K d (1 + S) log (2 (1 + t /d) /δ), which completes the proof . □ Lemma 6. Let { F i } ∞ 1 be a filtration. Let { X i } ∞ 1 be a stochastic process in B 2 ( d )  = { x ∈ R d | ||× t ||2 ≤ 1} such that x t is F t measurable. Let { ε t } t=1 be a martingale difference sequence such that E t ∈ R K is F t +1 measurable. Furthermore, assume that conditional on F t , we have
Proof of Lemma 6.  The proof follows the pipeline in the analysis of the self-normalized tail-inequality in the previous studies [3, 8, 11]. Letting H t = [ s = 1 Σ s ⊕ x s × s ] , we define the function M t (ξ) = exp(ξ ¹ S t − ∥ ξ∥ ξ, ) for any t ≥ 1 and ξ ∈ R K d . For t = 0, let M 0 (ξ) = 0. By Lemma 7 in Appendix B.1.2, we can show that { M t ( ξ )} ∞ 1 is a non-negative super-martingale for any ξ ∈ ξ B 2 ( K d ). We note that our Lemma 7 is an imporved version of Lemma 7 in [11], which relaxs restriction on the feasible domain of ξ from ξ ∈  ξ B 2 ( K d ) to ξ ∈ ξ B 2 ( K d ), resulting in saving an O( √ K ) factor in the bound. Then, let h(ξ) be a probability density with support on ≒ B 2 ( K d ) and define
E[Mo] = 1. Then, the maximal inequality (Theorem 3.9 of [15]) shows that
we aim to bound, || S t || H − 1 . Let h ( ξ ) be the density of an isotropic normal distribution with precision matrix 2 λ I K d truncated on ξ B 2 ( K d ) and N ( h ) be its normalization constant. Furthermore, let g ( ξ ) be the density of the normal distribution with precision matrix 2 H t that is truncated on the ball 2 B 2 ( K d ). Following the arguments in the proof of [8, Theorem 1] (more precisely the arguments in deriving Eq.(11) in [8]), for any t ≥ 1, one can show that
⭐ ·̸̸̸≥ 1/4. Then, we - . ☁️. One can check ‖ ξο‖ 2 ≤ for any ξ ∈  ξ B 2 ( K d ). Let ξ 0 ║S ε ║ H − 1
Combining (17) and (18), for any t ≥ 1, we have
We complete the proof with Lemma 6 of [8] such that
● Lemma 7.  For all ξ ∈ ž B 2 (K d), the sequence { M t (ξ )} ∞ 1 is a non-negative super-martingale. Proof of Lemma 7. To show that { M t ( ξ )}ニ1 is a non-negative super-martingale, it is sufficient to prove E[ M t +1( ξ ) | F t ] ≤ M t ( ξ ) for any t > 1 and ξ ∈  ł B 2 ( K d ). By the definition of M t +1( ξ ), we have
We can further check that
where the first inequality is due to the Höler's inequality. The last inequality is by the condition ||∈ t ||1 ≤ 2 and ||ξ k ||2 ≤ ||ξ||2 ≤ 1/2 for any k ∈ [ K ]. Then, we can further bound the expectation term in (19) by
where the first inequality is due to Lemma 8 and the last equality is due to mixed-product property of the Kronecker product. Therefore, we can show E [ M t +1 ( ξ ) | F t ] ≤ M t ( ξ ) and complete the proof. Lemma 8 (Lemma 6 of [11]). Let ε ∈ R K  be a zero-mean random vector with covariance matrix E. Then, for any vector a ∈ R K such that | ε T a | ≤ 1, we have E [exp(ε T a)] ≤ exp(a T Σ a). This section provides the proof for Theorem 2. Proof of Theorem 2. We prove the proposed algorithm can achieve O(d log T √ κ K T ) and O(dK logT√T + κd²K 2 log²T ) bounds simultaneously. Before presenting the proofs, we in- troduce two matrix that measures the local curvature of the loss function and will be used in the rest part of the proof:
Analysis for the O (d log T √ κ K T ) Bound. The regret can be bounded by
In the above, the term A( x t , W ∗ , W ′ o P T ) is defined as (20) and the first inequality is a consequence of the optimistic rule (5) such that ( x t , W ′ ∂ρτ ) = arg max x ∈ x , W ∈ C t ( δ ) ρ T σ ( W x ) and the first equality is due to the mean value theorem for the vector valued function. The second inequality is due to the Cauchy-Schwarz inequality and we can obtain the the last second inequality by the fact ∇ σ (z) ⇔ 1 κ for any z ∈ R K . The last inequality is due to Assumption 2. Let G − * ( W 1 , W 2 ) be defined as (21). We can proceed to handle the gap between W ′ 0PT and W ∗ by
where the first inequality is due to the fact A(x t , W * , W * , W * ) ≪ I K and the second inequality is due to G t (W ∗ , W opt) ≥ V t = λ I κ d + = ∑ t = 1 I κ ⊗ x s x T . We can show the last inequality by using Cauchy-Schwarz inequality again. Then, we proceed to bound term (a) and term (b) respectively.
19
In above, we denote by λ max the maximum eigenvalue of the input matrix. The second inequality is due to the property of the maximum eigenvalue such that λ max ( ABC ) = λ max ( 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− 1 ⊗ B− 1 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 1 shows that W ⋆ ∈ C t (δ) with probability at least 1 − δ for all t > 1 and the optimistic rule (5) ensures W ( PT E C t ( δ ), Lemma 9 in Appendix B.2.2 indicates that the distance between W * and W opt can be bounded by Then, plugging the above displayed equation into term (b), we can bound this term by
where the last inequality holds because β t ( δ ) is a non-decreasing function with respect to t . A combination of the upper bound for term (a) and term (b) leads to
Analysis for the O ( K d log T √ T + κ K d 2 log 2 T ) Bound. Inspired by the analysis for binary logistic bandit problem [9, Appendix C], we employ a different decomposition compared to the one
ν)∇²σκ ((W* + ν(W*))x t )dν. In the above, the first inequality is due to the optimistic rule (5) and the last equality is due to the integral formulation of the Taylor series. Then, we proceed to handle term (c) and term (d) respectively. As for term (c), we have
Let λ max ( · ) denote the maximum eigenvalue of the matrix. We can further bound (24) by
where the first inequality is due to the fact that ‖ Ab ‖ 2 ≤ ‖ A‖ 2 · ‖ b‖ for a matrix A and vector b. The second inequality is due to the definition of the induced norm || A || 2 = √ λ max ( A 1 ⁄ A ) and the mixed-product property of the Kronecker production. The last equality is due to the cycle property of the maximum eigenvalue such that λ max ( ABC ) = λ max ( CAB ) for matrices A, B and C and we use the mixed-product property again. The last inequality is due to Lemma 10 in Appendix B.2.2. Combining (24) and (25), we arrive
Then, we turn to handle term (d). Lemma 11 indicates that
where the first inequality is due to Assumption 2 and the second inequality is due to (27). The last second inequality can be obtained by a similar argument in obtaining (22). The last inequality can be obtained by the same argument as (23). Combining (26) and (26), we obtain
We have completed the proof. This section provides the lemmas used in the main proof. Lemma 9.  If W x  ∈ C t (δ), then for all W  ∈ C t (δ):
Proof of Lemma 9.  Lemma 3 in [11] shows that
for any W ∈ C t (δ) . Then, we have
where the last second inequality is due to generalized self-concordant properties of the logistic loss as shown by Lemma 13 of [11]. The last inequality is due to Theorem 1 and the condition that W is contained in the confidence set C t ( δ ). ● Lemma 10.  When the regularization parameter λ > 2, we have
Proof of Lemma 10. Denoting by Tr( A ) the trace of matrix A , We have ●
where the last inequality is due to Lemma 4 of [11] such that (1 + 2 S ) G t (W ∗ , W ′ ρ σ τ ) ≥ H t (W ∗ ). =1 ∇σ(W*x s ) ⊗ x s x T . Then, we can further bound the last line of the Let M t (W ∗ ) = ⇌ I κ d + ∑ t s above displayed equations by
The first inequality is by the fact H t (W ∗ ) ≥ M t (W ∗ ) under the condition λ ≥ 2. The last second inequality is due to Lemma 4.5 of [16]. ● Lemma 11. Let σ k : z → [σ(x)] k ∈ R by the k-th output of the vector-valued function σ(z). Then, for any z ∈ R K , we have ∇ 2 σ k ( z ) ≤ 3 K for any k ∈ [ K ]. Proof of Lemma 11.  For any z ∈ R K , we have
where we denote by E k as the matrix where the entry at the ( k , k )-th position is 1, and all other entries are 0. In the above, the first inequality is due to the definition of σ k . The second inequality holds since diag( σ(z)) is semi-positive defined matrix. The last inequality is a consequence of the fact that the maximum eigenvalue of σκ(z)σ(z) T is bounded by σκ(z)(σ(z) − e k )(σ(z) − e k ) T is less than 1. The maximum eigenvalue of σ k (z) (σ(z) − e k )(σ(z) − e k ) ⊥ is bounded by 2. ● This section presents the omitted details for Section 3. To simplify the notation, we exclude the superscript OL in all the proofs within this section. This section provides the proof of Theorem 3. We will first provide the main proof of Theorem 3 and the prove the technical lemma used in the main proof. Proof of Theorem 3.  The proof shares the similarity with the online-to-confidence-set conversion technique [47, 14], where the estimation error of the online estimator W [ 1 ' is bounded by the regret. However, we have introduced a novel algorithm and analysis ingredient to achieve jointly statistical and computation efficiency. The following lemma provides the estimation error analysis. Drawing inspiration from the modern analysis of OMD [23], we explicitly extract the negative term − ∑ s = 1 ‖ W s+1 − W s ‖ Z j  in the upper bound, which is pivotal for our subsequent theoretical analysis and the algorithm design. Lemma 12.  Under Assumptions 1 and 3, we consider the estimator update rule
where ξ t (W) = {∇ ℓ t (W) ∇²ℓ t (W t ) and H t = λΙκα x s x T . Then, letting α = ln( K + 1) + 2( S + 1) and λ > 0, we have when the step size is set as η = α /2. Then, we focus on the first term of the right hand side. Inspired by the previous studies on binary logistic bandit [10], we decompose the regret into two part by inserting an intermediate decision.
where the ˜ z s  is an aggregating forecaster for logistic loss defined by ˜ z s = σ + ( Ew ~ p [σ( W x s )]) and P s = N ( W s , (1 + cH s −1 ) is the Gaussian distribution with mean W s and covariance matrix cH s 1 where c > 0 is a constant to be specified. In above, σ + : Δ H R K is a pseudo-inverse function of σ( · ) whose k -th output is [σ + (p)] k = log (p k /(1 − ||p||1)) for any p ∈ {q ∈ [0,1] k |||q||1 < 1}. We bound the above two terms respectively. First, we show that the term (A) is bounded by O ( log 2 t ) with high probability. Lemma 13.  Let δ ∈ (0, 1).  Under Assumptions 1 and 3, we have
Besides, the term (b) can be bounded by the following lemma, Lemma 14.  Under Assumptions 1 and 3, for any c > 0, we have by setting λ ≥ max{2,24Kdc}. In the above, ηξ(δ) = √δcKdln(1+( ( ξξ x λ ≥ and L := maxWERKd,tE[T] ∇ 2 ℓ t (W) is the smooth parameter of the logistic loss. Combining Lemma 12, Lemma 13 and Lemma 14, we arrive at
ll
For the last second inequality, we eliminate the additional term by the parameter setting η = α/2, c = 7α/6 and λ ≥ {7√6αS, 28K dα} and due to the fact that I K ⊗ x s xך≪ I K d under the condition ∥ x έ ∥ 2 ≤ 1 for any t ∈ [ T ]. In the above, we have λ = O ( K d log K ) and α = O (log K ). Then, we ● can show ‖ W t+1 − W ∗ ‖ H t+1 ≤ β気(δ) = O(log K log t √ K d ), which completes the proof. Proof of Lemma 12.  Let ξ s (W) = ℓ s (W s ) + (W − W s , ∇ℓ s (W s )) +ﾎ∥ W − W s ∥ δ 2 t , (W s ) be a second order approximation of the original function ℓ s ( W ) at the point W s . The update rule (6) can be equally written as
which is an implicit online mirror descent update with the loss function ℓ s . Then, according to Lemma 16, the model W t +1 ensures,
One the other hand, let α = log(1 + K) + 2(1 + S). Since ∥ W ∗ x t ∥ ∞ = max k ∈ [ K ] {∥ W ∗ γ ∥ 2 + ||× ε || 2} ≤ S and ℓ s (W) = ℓ (W x s , Y s ), Lemma 1 shows
By setting η = α /2, the combination of (31) and (32) shows
In above, we can further bound inner product term by
In above ξ s +1 is a certain point on the line connecting W t and W t +1 . The notation is defined as D³ℓ¸(W)[U] = lima→oα−¹ (∇²ℓ¸(W + αU) − ∇²ℓ¸(W)). The first inequality is due to the definition of ℓ s  and the second inequality is by the Taylor seriés for the vector-valued function. The third inequality is because the third order derivative of the logistic loss is a symmetric tensor as shown in Property 1. The last second inequality is by Definition 1 since the multiclass logistic loss is a √ δ self-concordant-like function. The last inequality is by the boundedness of the decision domain W and bounded action such that ‖ × ‖ 2 ≤ 1 for any x ∈ X under Assumption 1. Combining (33) and (34), we have
Taking the summation of the above inequality over t rounds and rearranging the term, we have
● Proof of Lemma 13. Since the norm of the intermediate decision ˜ z s = σ + ( Ew~p , [σ( Wx s )]) is generally unbounded, as suggested by [26], we use the smoothed version " , σ + (smooth μ ( EW ~P ε [σ( W x ε )])) as an intermediate term in the analysis. In above, the smooth function smooth μ : [0, 1] K → [0, 1] K with parameter μ ∈ [0, 1/2] is defined by smooth μ (p) = (1 − μ)ρ + μ1/(K + 1), where 1 ∈ R K is an all one vector. Given the construction of the pseudo inverse function σ + such that σ(σ + (p)) = p for any p ∈ {q ∈ [0, 1] κ | ||q||1 < 1}, one can check that ˜ = σ + (smooth μ (σ( Z s ))). Then, Lemma 17 shows that
it is sufficient bound the gap between the loss of W s and Z s . By the definition of the loss function ℓ s , we have ℓ s (W*) = ℓ(z*, ys), where z* = W*xs. Then, we have
where S μ = log( K + 1) + 2 log(1 + ( K + 1)/ μ ). In above, the first inequality is due to Lemma 1. 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 a one-dimension case and whose proof is provided C.1.5. Lemma 15. Let { F t } ∞ 1 be a filtration. Let { Z t } ∞ 1 be a stochastic process in B 2 ( K ) = { Z ∈ R K ||z||∞ ≤ 1} such that z t is F t measurable. Let { ει } ≥ 1 be a martingale difference sequence such that E t ∈ R K is F t +1 measurable. Furthermore, assume that conditional on F t , we have ∥ ε t ∥ 1 ≤ 2 almost surely, and denote by Σ t := Ε [ ε t ∈ t ]. Let λ > 0 and for any t ≥ define
Then for any δ ∈ (0, 1], we have
To check the condition of Lemma 15, we let d s = ( z ξ − ˜ z ξ )/( S μ + S ). Since ∥ z ξ ∥ ∞ ≤ max k ∈ [ k ] || w { k ) || 2 || x ] || 2 ≤ S and || Z ε || ∞ ≤ log(1 + ( K + 1 )/ μ ), one can verify that || d s || ∞ ≤ 1 . Besides, since z * and ˜ ı g is independent of y s , the variable d s is F s measurable. Furthermore, we can check that E [(σ( z *) − y s )(σ( z *) − y s ) ⊥ | F s ] = ∇σ( z *) and ‖ σ( z *) − y s ‖ ≤ 2. Thus, a direct application of Lemma 15 shows that, with probability at least 1 – δ , we have
d T ∇σ( z ∗ )d s ≤ 2. Then, combining (36) and (38) and setting λ = 1, we arrive ¥
where the second inequality is due to AM-GM inequality. Finally, combining (35) and (39), we have
□ K ) + 2 log(1 + ( K + 1) t ). We have completed the proof. Proof of Lemma 14.  Our proof starts with the observation made by [26, Proposition 2] that ž s is an aggregating forecaster [48, Chapter, 3.5] for the logistic function, which satisfies
Then, we consider the following quadratic approximation,
According to Lemma 18, we have
Then, we can low bound the term in the expectation by
whose density function is f s+1 (W) / Z s+1 , we can further rewrite the last line of the above displayed equation (42) as
where the second inequality is due to the Jensen's inequality and the last equality comes from the fact that f s +1(W)/Z s +1 is symmetry around W s +1 and thus E W ~ β . . [(VL s (W s +1),W − W s +1)] = 0. Plugging (43) into (40), we arrive
where ˆ P s+1 = N ( W s+1, cH g+1 = f s+1 = f s+1 e − ± lW − equality is by definition of Ž s+1 and the second one comes from the definition of  β s+1 . The last second inequality is due to the Jensen's inequality such that ln( E [ a ]) ≥ E [ln a ] for the random S RKd e-zllW-w ×÷ï¨¨ H× dW = Z s variable a ∈ R . The last equality is by the fact Z s Combining (44) and  (45) and taking the summation overt t iterations, we have
Following a similar argument in [27], we can bound the last term as follows. Specifically, by the Cauchy-Schwarz inequality, we can decompose the term Ω 5 as
Then, remarking that ˆ β s+1 = N ( W s+1 , cH s − 1 ), the key observation here is that W − W s+1 also follows the same distribution as
where { e i ∈ R K d } K d  is a set of certain orthogonal basis and λ i := λ i ( H − 1 ) denotes the i -th largest
λ i ≤ 1/λ . The last inequality is due to the Jensen's inequality since K d > 1. Then, by further requiring λ ≥ 24K dc , we have
where the last inequality is because the moment-generating function for χ 2 -distribution is bounded by E x ~ x 2 [e t X ] ≤ 1/√1 − 2t for all t ≤ 1/2. Then, we consider the second on the upper bound of term (b). A direct calculation gives,
cH −1 be the ż -th largest eigenvalue of the matrix. A similar decomposition as (47) shows that
comes from the fact that ∑ i=1 λ i = Tr(cH − 1 ). The notation Tr( A ) is used to denote the trace of the matrix A. Then, we proceed to bound the trace Tr( H = 1 ) with ˜ H s = H s ∇ 2 ℓ s ( W s+1 ). Recall the definition of H s = λΙκα + ∑ t =1 ∇ 2 ℓ τ (W τ+1). We define M s +1 = λΙκα/2 + ∑ vr=1 ∇ ² ℓ ≠ ( W ≠ +1 ). Under the condition λ ≥ 2 for any s ∈ [ T ], we have ∇ 2 ℓ s ( W ) ≪ I κ a ≤ ≥ I κ d for any s ∈ [ T ] and W ∈ W . Then, we have H s ≥ M s +1. Then, we can bound the trace by
√3c ln(| M s +1 |/ | M s |), which leads to
Combining (46) and (49), we obtain that
W can further bound the last term of the displayed equality by ∑ s =1 ln ( | M s +1 |/ | M s |) V ln (|Mt+1|/|入/2 · Ika|) ≤ Kdln (1 + |t+1) ≥ 1 , which completes the proof. 2入Proof of Lemma 15.  The proof of Lemma 15 shares the same spirit as that of Lemma 6. Let H t = ∑ s=1 || z s || ξ . We can also defined the function M t (ξ) = exp(ξS t − ξ 2 H t ) for any t ≥ 1 and ξ ∈ R. For t = 0, we let M 0 (ξ) = 0. Following the similar arguments in the proof of Lemma 7, one can show that the sequence { Mt (ξ)} ≥ 1 is a non-negative super-martingale when ξ ≤み. Then, let h (ξ) be the density of the normal distribution with precision 2λ truncated on the 1-dimensional ball ≒B(1). We can define
By the similar arguments in deriving (17), we have
for any | ξ | ≤ 1/4. In the above, g ( ξ ) is the normal distribution with precision 2 H t truncated on the interval [−1/4, 1/4]. Then, let ξ 0 =ﾌ√̸/̸/ , we have ξ 0 ≤ 1/4 since H t ≥ λ . We can obtain that
A combination of (50) and (51) shows that
which indicates
We complete the proof with Lemma 6 of [8], which shows that log ( N ( h )/ N ( g ))  ≤ log ((2√ R t )/ λ ). Lemma 16 (Proposition 4.1 of [49]).  Let the w t +1 be the solution of the update rule W t +1 = arg min ηℓ t (w) + D (w, w t ), where V ⊆ W ⊆ R d is a non-empty convex set and D ψ (w 1 ,w 2 ) = ψ (w 1 ) − ψ (w 2 ) − (∇ψ(w 2 ), w 1 — w 2 ) is the Bregman Divergence w.r.t. a strictly convex and continuously dif- ferentiable function ψ : W ↔ R. Further supposing ψ (w) is 1-strongly convex w.r.t. a certain norm ||-|| in W , then there exists a g t ∈ ∂ ℓ t ( W t +1 ) such that {mtg't; wt+1 - u} < {∇ψ(wt) - ∇ψ(wt+1); wt+1 - u} for any u ∈ W. Lemma 17.  Let ℓ(z, y) = ∑ k- k=0 1 { y = k} · log ( [ བ( z ] [ z ] and z ∈ R K be a K -dimensional vector. Define zዞै σ + (smooth μ (σ (z))), where smooth μ (p) = (1 − μ ) ρ + μ 1 /(K + 1). Then, for μ ∈ [0, 1/2], we have
for any y ∈ {0} ∪ [K]. We also have ‖ z f ‖ ∞ ≤ log(K/μ). Proof of Lemma 17. The proof of Lemma 17 is extracted from the proof of [26, Lemma 3] with a slight modification to the logistic loss used in this paper.  According to the definition of z l r and the fact that σ(σ + (ρ)) = ρ for any ρ ∈ {q ∈ [0,1] K |||q||1 < 1}, we have σ(z k ) = (1 − μ)σ(z) + μ1/( K + 1). Then, we have
k=0 1{y = k} = 1 and the last inequality is due to log(1/(1 − where the first inequality is due to ∑ k - a)) ≤ a for α ∈ [0, 1/2]. Besides, let p = σ(z). According to the definition of z t t , we have
Since the term inside the logarithmic function can be bounded by
● Lemma 18. Let L s (W) = ℓ s (W) + ξ ∥ Ψ − Ψ s ∥ H , Then, for any W,W s +1 ∈ W, the quadratic
approximation ∑ s (W) = L s (W s +1) + (V L s (W s +1),W − W s +1 ∥ H , defined as (41) satisfies
Proof of Lemma 18.  According to [19, Lemma 4], ℓ s is a √ 6-self-concordant-like function. Then, by Lemma 5 and the fact c(x) ≤ e z  for any x ≥ 0, then for any W ∈ W , we have
Besides, since g s (W) = ニ∥ W −  W s ∥ H z  is a quadratic function, we have
Then combing (52) and (53), we can obtain an upper bound of L s ( W ) = ℓ s ( W ) + g s
We have complete the proof.
This section presents the proof of Proposition 1. Proof of Proposition 1.  Since ρ Tσ(W έ x) ≤ ρ Tσ(W έ x) + |ρ Tσ(W έ x) − ρ Tσ(W έ x)|, to showﾃﾞｨ(x) = ρ Γ σ (W ε x) + εξ π τ (x) + εξ π α (x) is an optimistic estimate, it is sufficient to prove that |ρ T σ(W*x) − ρ T σ(W t x)| ≤ εξ π t(x) + εξ π d(x). We have the following decomposition:
where σ k : x → [σ(x)] k is the k -th output of the vector-valued function σ(x) andニk,t = f,l=0(1 − ν)∇²σκ ((W t + ν(W ∗ − W t ))x)dν . 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.
where the last inequality is due to Theorem 3. Then, we upper bound term (b) by ε ž n d with the following arguments. For notation simplicity, we denote by ξ t,ν = W tx + ν(W ∗ − W t )x. Then, Lemma 11 indicates that
where the first inequality is due to Assumption 2 and the last inequality is due to Theorem 3. Combining the upper bound for term (a) and term (b), we have
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 f .
where the first inequality is due to Proposition 1 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.
The second inequality is due to the definition of the induced norm for the matrix is defined as || A || 2 ＝ √λmax( A T A ) and the mixed-product property of the Kronecker production. The first equality is due to the cycle property of the maximum eigenvalue such that λ max ( ABC ) = λ max ( CAB ) for matrices A, B and C . The last second inequality is due to the Cauchy-Schwarz 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.
34
certain point on the line connecting W t x t and W t +1 × t . We can further bound the second term of the
∇σk(z) ⇔ 3Ik for any z ∈ RK and ∑ k =1 Pk ≤ √ K R. Then plugging (58) into (57), we can bound term (b) by
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
As for the term ∑ t =1 c ε nd ( x t ), we have
Combining (59) and (60) with (55), we have
This part shows that the OFUL-MLogB (Algorithm 2) also achieves an Ö(√ κ KT ) regret bound. Theorem 5.  Under the same condition as Theorem 3, Algorithm 2 ensures
Proof of Theorem 5.  The proof of Theorem 5 is almost the same as that for Theorem 4.  We can decompose the regret as
following the same arguments (55). The only difference is that we can bound the Σ T c fst (x t ) in (55) with a different arguments based on the local matrix V t I K  S x , x,
inequality can be obtained c ε π d with the same arguments as (60):
Useful Lemmas C.3.3 Lemma 19.  Let H t = λ I κ a +
where L = maxxex,WeW λmax(∇σ(Wx)) Proof of Lemma 19.  Let M t =ミュニス+ ∑ f =1 ∇σ(W s+1x s) ⊗ x s x s . Then, we have H t − M t − ☆ I k a − ∇ σ ( W t +1 x t ) ⊗ x t x T . Since ∇ σ ( W t +1 x t ) ⊗ x t x T ≪ I k a , we have H t ≫ M t when λ > 2. Then, we have
where we denote by Tr( A ) the trace of matrix A. The second inequality is by the condition H t ≥ M t . The last second inequality is due to Lemma 4.5 of [16]. ● Lemma 20.  Let W t+1 = arg minw ∈ W (∇ℓ t (W t ), W ) + H (W − W t ll͡x then, we have
Proof of Lemma 20.  Let  F t (W)   =   (∇l t (W t ),W)  +  cllW  −  W llW Since W t+1  = arg min w ∈ W F t ( W ), we have F t ( W t +1) ≤ F t ( W t ), which implies
Then, by the Hölder's inequality, we can further bound the inner product term by (∇ℓt(W t),W t − W t+1) ≤ ∥W t+1 − W t ∥ = , · ∥∇ℓt(W t)∥ = , · which indicates that
Since Ň t ≥ H t and Ň t 1 ≤ I κ d/λ, we can further have,
where the last inequality is due to the definition of ∇ℓ t (W t ) = ( σ t (W t ) − y t ) ⊗ × t such that ● ||∇ℓ t (W t )||2 ≤ 2√K. Lemma 21.  Let H t = λ I κα + ∑ t − 1 ∇ σ ( W s + 1 x s ) ⊗ x s x T . Then, we have
where λ > 2. Proof of Lemma 21.  The proof of Lemma 21 shares the same spirits with that of Lemma 19. Let Vt = $ I Kd + $ ∑ s =1 I K & x s x s T . We have Ht ≥ Vt when λ > 2. We can prove the lemma by
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]. D Input:  regularization coefficient λ , probability δ , step size η . l:  Initialize H 1 = λ I κ d and W 1 as any point in W 2:  for t = 1, . . . , T do Select the arm by x t = arg max x ∈ x ř t (x) and receive y t . 3: Update Ã¢ = H¢ + η∇σ(W¢x¢) ⊗ ×¢X† 4: 5: Update the estimator W t +1 for the next iteration by (6) Update H t +1 = H t + ∇ σ ( W t +1 × t ) ⊗ × t × t +1 and 6: 7: Construct the optimistic reward by ř t +1(x) = ρ ⸢ σ (W t +1x) + c ξ t t t (x) + c ξ t t (x) as (8). 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 t +1 = H t + ∇ σ (W t +1 x t ) ⊗ x t x T and ˙ H t = H t + η∇σ(W έ x έ ) ⊗ x έ x į . Since ∇σ(W έ +1 x έ ) ⊗ x έ x į and ∇ σ(W έ x έ ) ⊗ x έ x į are both rank-K matrix, then one can main H t and H t with O ( K 3 d 2 ) computation cost per iteration by the Sherman-Morrison- Woodbury formula. Given the H r 1 and H r 1 , we discuss the computation cost of the construction of the optimistic reward 8 and the update rule for the estimator (6). Computation Cost of the Estimator (6).  As shown by the discussion in Section 3.2, the update rule (6) is identical to
Given the H − 1 , we can perform the gradient step with O ( K 2 d 2 ) time complexity.  As for the projection step, the optimization problem can be solved in O(K 3 d 3 ) time [18, Section 4]. As a consequence, the overall time complexity for obtaining the estimator (6) is O( K 3 d 3 ). Computation Cost of Building Optimistic Reward.  As shown by (8), we construct the optimistic reward byﾃft(x) = ρ T σ (W ρ 1 x) + εξ π τ (x) + ε επ α (x). We can compute εξ π τ (x) with the following equivalent formulation
Given H i − 1 , it will take O ( K 2 d 2 ) to calculate εξ π t ( x ). As for the term εξ π t ( x ), it can also be rewritten as
It would take O( K 3 d 3 ) time to perform the eigenvalue decomposition. Given there are | X | arm, the time complexity for identify the arm x t = arg max x ∈ x ř t ( x ) is in total O ( | X | K ³ d ³). Overall, Algorithm 2 can be implemented in O ( | K ³ d ³ ) time, which is independent of T . In the binary case, we select the arm by ( x t , W t ) = arg maxx ∈ x , w ∈ C t ( δ ) w T x. In such a case, we show Algorithm 2 achieves an Õ(T/ κ x ) bound with a constant computation cost. The proof is almost the same as that of [10, Theorem 2]. The main difference is that we complete the proof with the confidence set of the efficient online estimator (Theorem 3). We present the proof here for self-containedness. Proof of Corollary 1. When K = 1 and ρ 1 = 1, the MLogB problem recovers the binary logistic bandit problem with the feedback y t = {0,1} and the reward model Pr[y = 1|x] = σ(w ī x). In
time horizon into two parts I 1 = { t ∈ [ T ] | σ ′ ( w ∗ x ε ) ≥ σ ′ ( w ∗ +1 x ε )} and I 2 = [ T ] / I 1 .
any z ∈ R . The second inequality is due to the Cauchy-Schwarz inequality and H t ≤ H t +1 . We can further bound term (a-1) by
the radius of C t ( δ ) as shown in Theorem 3. The last second inequality is by the condition such that σ ′ ( w , x t ) ≥ σ ′ ( w t +1x t ) for all t ∈ I 1 . Then, following the same argument in the proof of [10, Theorem 2], one can show
last inequality. As for term (a-2), we have
where the first inequality holds because w ∗ and w t are contained in C t ( δ ). 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
As for term (b), we have σ ′ ( w ∗ x t ) < σ ′ ( w i +1 × t ) for all t ∈ I 2 . Then, we have
where the second inequality is due to the condition σ ′ ( w , x t ) < σ ′ ( w , + 1 x t ) and the last inequality can be obtained using similar arguments as those used to derive (62). Regarding term (c), the application of similar arguments used to derive equation (62) demonstrates.
Then, combining the upper bounds for term (a), term (b) and term (c), we have
● which completes the proof. Since the binary logistic bandit is a special case of the MLogB problem, the time complexity analysis in Appendix C.3.4 is also applicable in the binary case. The only difference is that we select the arm as ( x t , ŵ t ) = arg max x ∈ X , W ∈ C t ( δ ) w T x in the binary case. As C t ( δ )   = {w ∈ W | ||w − w*|| H, ≤ βι (δ)} is an ellipsoid, the optimization can be rewritten as:
Given H − 1 , the above optimization problem can be solved in O ( d 2 ) time. In the binary case, we have achieved the minimax dynamic regret bound O( √ T / κ ⋆ ) up to a logarithmic factor in terms of T . In the MLogB problem, the best-known result is Õ ( K √ T ). A natural question arises: can we obtain a 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, 10] and we restate in (63), a critical step involves showing
In the MLogB problem, in order to obtain a similar result to the minimax optimal bound achieved in the binary case, it is sufficient to demonstrate
However, it is unclear how to prove such a relationship as the binary case.  Indeed, denoting by r t = σ(W*x*) − σ(W*x t ) the reward vector and r t,k by its k -th entry, we can further rewrite the k-th entry of the vector ρ T Σ(W*x t ) can be further written as
In the binary case, In the binary case, the additional term becomes – T — Regr < 0, 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 in determining an upper bound for it. 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. In the binary case, the minimax optimal regret bound relies on constructing an optimistic reward through ñ t ( x ) = arg max w ∈ C t ( δ ) σ ( w T x ). Since σ ( z ) is an increasing function, the optimization problem can be simplified to
which becomes a convex optimization problem when C t ( δ ) is a convex set. However, when applying this analysis to the multinomial case, solving the problem requires optimizing
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. 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 X and the underlying unknown parameter W s  are randomly selected. In the binary case, the norm of the unknown parameter is set as ‖ w ∗ ‖ 2 ＝ S with S ＝ 5. As for the multinomial case, each row of W ∗ are randomly sampled with ||w ( k ) || 2 = Š for all k ∈ [ K ] with Š = 1. The parameter of all contenders are set according to their order as suggested in the corresponding paper. We use λ = d log( T ) for Log-UCB1, λ = d for OL2M, λ = 1 for ada-OFU-ECOLog and λ = √ K α S for OFU-MLogB. The step size for OFU- MLogB is set as η = S/2 + ln( K + 1)/4. The experiments are run on Xeon E-2288G processors (8 cores, 3.7GHz base, 5.0GHz boost). More Results. Figure 3 provides additional empirical results for the binary logistic bandit problem. These results align with the trends observed in the main paper, wherein our OFU-MLogB algorithm shows performance comparable to ada-OFU-ECOLog but with reduced computational overhead. Meanwhile, more results for the multinomial case are provided by Figure 4. The cumulative running time for MNL-UCB increase at a rate of O ( t 2 ). In contrast, the running time for our OFU-MLogB exhibits a linear dependence with t , attributable to the constant computation cost per round.