acceptodds
Under review as a conference paper at ICLR 2027

Efficient Multinomial Logistic Bandit via Robust Frequent Directions

Abstract

This paper studies efficient online algorithms for multinomial logistic bandits (MLogB), where the feedback distribution over outcomes follows a multinomial logistic model of -dimensional action vectors. A representative UCB-type algorithm, OFUL-MLogB, achieves a regret bound of , but still requires time and space per round due to parameter estimation and optimistic reward construction, which is prohibitive in high-dimensional settings. To address this limitation, we propose EOFD-MLogB, an efficient algorithm integrating robust frequent directions matrix sketching. By maintaining a low-rank SVD sketch of the Hessian matrix from online Newton step (ONS)-based parameter estimation, we make both nonlinear estimation and optimistic reward construction efficient: the constrained ONS parameter update is reduced to a one-dimensional root-finding problem, while the spectral-norm computation in the optimistic reward is reduced to a eigenvalue problem. This yields dominant per-round time complexity and space complexity , where is the sketch size. We further prove a regret bound of , where the sketching error factor is controlled by the -truncated spectral tail of the ONS Hessian. Thus, when the ONS Hessian is approximately low-rank, the regret remains close to that of OFUL-MLogB. Experiments validate the computational efficiency and competitive performance.

Primary area:
optimization
Keywords:
online learning, bandits, matrix sketching

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_EyGSOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the Multnomial Logistics Bandits, aiming to address the computational and storage bottlenecks faced by existing algorithms due to the maintenance and operation of high-dimensional Hessian matrices. The author proposes EOFD-MLogB to maintain the low-rank spectrum representation of cumulative Hessian, and transform the high-dimensional spectrum norm calculation in optimistic reward into an eigenvalue problem of K×KK\times K. Theoretically, this method reduces the main calculation complexity and spatial complexity of each round to O(Kd(m+K)2)O(Kd(m+K)^2) and O(Kd(m+K))O(Kd(m+K)) respectively, and gives the regret bound of sketching error controlled by Hessian truncated spectral tail. Experimental results show that EOFD-MLogB can significantly reduce running time and memory overhead on synthetic data and multiple real data sets, while maintaining a regret performance close to OFUL-MLogB.

Critical strengths
  • The research problem is well motivated and has practical significance.
  • The paper provides theoretical analysis and relatively thorough experimental evaluation.
Critical weaknesses

Theorem 1 requires a relatively large regularization parameter λ\lambda, which scales at least linearly with KdKd. For instance, under the multinomial synthetic setting (K=4,d=100,S=5,D=1)(K=4,d=100,S=5,D=1), this condition requires λ≥105\lambda\ge 10^5, whereas Appendix C.1 reports using λ=1\lambda=1. More importantly, under the theoretical choice of λ\lambda, the accumulated Hessian MtM_t's norm is relative small compared to such large λ\lambda, suggesting that the full Hessian matrix Ht=λI+MtH_t=\lambda I+M_t is already close to an isotropic matrix and that its directional curvature information may have limited influence.

This raises a concern about the connection between the theoretical guarantees and the empirical benefits of Hessian sketching. In the theory, this work requires in a extremly large regularization parameter where preserving the principal Hessian directions may be less important. Moreover, the experiments use a much smaller regularization parameter outside the stated theoretical conditions. It would be valuable to clarify this gap and examine whether the proposed method maintains its empirical advantages under theoretically admissible regularization parameters.

Questions for authors

see weakness part

1 comment

We thank the reviewer for their appreciation of our work and raising this concern. We will take the opportunity to clarify the typo and gap between theorems and experiments.

  1. Typo in Appendix C.1. We miss-reporting "l=0.75,e=0.75l=0.75,e=0.75" as "λ=1.0,η=0.5\lambda=1.0,\eta=0.5" in line 1805--1807 of Appendix C.1 , which has been corrected in the revision. The original experiments used the hyperparameter values reported in Table 2, which agree with the released code. Appendix C.1 correctly describes the grid search: we set (λ,ε)=((Kd)lλ0,(Kd)eη0)(\lambda, \varepsilon) = ((\sqrt{K}d)^l \lambda_0, (\sqrt{K}d)^e \eta_0), where we search (l,e)(l, e) in the grid {0,0.25,0.5,0.75,1}2\{0, 0.25, 0.5, 0.75, 1\}^2, and λ0,η0\lambda_0, \eta_0 are recommend experimental setting in [1].
  2. Experiments under the parameter choices of Theorem 1. We provide main experiments with λ,η\lambda,\eta set to theoretical number in the Appendix C.9 in the revision. We can see the regret of EOFD-MLogB consistently close to that of OFUL-MLogB, while preserving a large number of computational resources.
  3. Theoretical analysis. Theorem 2 and Theorem 4 of [1] guarantee for worst case upper bound for all TT, including T≫λT \gg \lambda. Although initially Ht=λI+MtH_t=\lambda I+M_t is close to λI\lambda I when ∣Mt∣2/λ\\|M_t\\|_2/\lambda is small, the Hessian MtM_t will become increasingly anisotropic over time. The confidence guarantee in Theorem 1 holds uniformly over tt. Since each update to MtM_t is positive semidefinite, each ordered eigenvalue of MtM_t is nondecreasing in tt. Thus, even when regularization dominates in early rounds, the λi(Mt)\lambda_i(M_t) can become comparable to λ\lambda along some directions later in the run. The spectrum of Mt/λM_t/\lambda measures this effect directly.
  4. Additional experiments. In a separate long-horizon experiment, we ran OFUL-MLogB with K=4K=4, d=20d=20, and λ,η\lambda,\eta set to the theoretical setting. We will include the spectrum of Mt/λM_t/\lambda in Appendix C.10 of the revision. At t=500,000t=500{,}000, approximately one quarter of the eigenvalues of MtM_t exceeded λ\lambda. The smallest and largest eigenvalues of Mt/λM_t/\lambda were approximately 0.150.15 and 1.661.66, respectively. Hence, the eigenvalues of HtH_t ranged from approximately 1.15λ1.15\lambda to 2.66λ2.66\lambda, giving a condition number of about 2.32.3. In this run, the accumulated curvature exceeded the regularization along several directions while remaining well below it along others.

[1] Yu-Jie Zhang and Masashi Sugiyama. Online (multinomial) logistic bandit: Improved regret and constant computation cost. In Advances in Neural Information Processing Systems, volume 36, pages 29741–29782, 2023.

Reviewer_7scNOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper aims to improve the computational and memory efficiency of a second-order multinomial logistic bandit algorithm in high-dimensional settings while preserving decision quality. It achieves this by sketching the Hessian maintained by the algorithm and redesigning the parameter updates and exploration-bonus computations accordingly.

Critical strengths

The theoretical analysis is generally well developed. The paper clearly explains the intuition behind EOFD-MLogB, including how the benefits of retaining Hessian information vary across settings. These differences are reflected in the regret bound, and the paper provides detailed comparisons with related work. The experimental evaluation covers both synthetic and real-world datasets. The results demonstrate improvements in runtime and memory usage while maintaining competitive regret.

Critical weaknesses

I see two areas for improvement:

  1. Clarifying the dependence of ΔT\Delta_T on TT. Since ΔT\Delta_T itself depends on TT, the stated regret bound does not directly imply O~(T)\widetilde{O}(\sqrt{T}) scaling. Although the authors provide a bound in terms of the spectral tail, it remains unclear which quantitative conditions on the growth of the cumulative spectral tail are sufficient to guarantee sublinear regret when the sketch size is fixed. The authors should clarify the dependence of ΔT\Delta_T on TT and distinguish guarantees under favorable spectral conditions from those available in general settings.

  2. Expanding the experimental baselines. The experimental evaluation includes relatively few baselines and would benefit from comparisons with additional relevant methods.

Questions for authors

Please check the two comments in Critical Weaknesses.

2 comments

We thank the reviewer for their appreciation of our work. We will improve our work and answer your questions point by point in the following.

  1. Dependence of ΔT\Delta_T on TT. For a fixed sketch size mm, the regret remains sublinear if the cumulative Hessian's spectral tail grows at most as O(T1/2−ε)\mathcal{O}(T^{1/2-\varepsilon}) for some 0<ε<1/20<\varepsilon<1/2. Specifically, let MT=∑s=1T∇2ℓs(Ws+1)M_T=\sum_{s=1}^T \nabla^2 \ell_s(W_{s+1}) denote the cumulative Hessian. If ∑i≥mλi(MT)=O(T1/2−ε)\sum_{i\ge m}\lambda_i(M_T)=\mathcal{O}(T^{1/2-\varepsilon}), then (27) gives ρ1:T=O(T1/2−ε)\rho_{1:T}=\mathcal{O}(T^{1/2-\varepsilon}). For fixed λ\lambda, we thus have ΔT=1+2ρ1:T/λ=O(T1/2−ε)\Delta_T=1+2\rho_{1:T}/\lambda=\mathcal{O}(T^{1/2-\varepsilon}), and Theorem 2 yields a sublinear regret bound. Similarly, SOFUL's regret bound for linear bandits [4] is likewise sublinear if the spectral tail of the cumulative action covariance grows as O(T1/3−ε)\mathcal{O}(T^{1/3-\varepsilon}) for some 0<ε<1/30<\varepsilon<1/3.
    Here we provide an example on the favorable spectral conditions: suppose all actions lie in a common rr-dimensional subspace UU with Kr<mKr<m, e.g. when each At\mathcal{A}_t is drawn from a fixed dataset A\mathcal{A} whose action embeddings span UU. Each Hessian update is supported on the same KrKr-dimensional subspace RK⊗U\mathbb{R}^K\otimes U. Hence rank⁡(MT)≤Kr\operatorname{rank}(M_T)\le Kr, and (27) gives ρ1:T=0\rho_{1:T}=0 and ΔT=1\Delta_T=1, recovering the O~(T)\widetilde{\mathcal{O}}(\sqrt{T}) regret rate. Classical UCB analysis also provides intuition for why the spectral tail can grow slowly. In a stochastic multi-armed bandit, the expected number of times UCB selects each suboptimal arm ii is O(log⁡T/Δi2)\mathcal{O}(\log T/\Delta_i^2) [2], where Δi\Delta_i is its reward gap. This suggests that, when a UCB-type algorithm for MLogB explores certain directions only through infrequently selected suboptimal actions, little curvature may accumulate in those directions.
    We thank the reviewer for pointing this out again, and we will add those discussion in the revision.

  2. Additional baselines. We provide more baseline (MNL-UCB [1], MNL-UCB+, OFULog+ [5], ada-OFU-ECOLog [3]) in the Appendix C.8 in the revision. The performance of EOFD-MLogB is close to that of OFUL-MLogB, while MNL-UCB little large regret compared to OFUL-MLogB. OFULog+ and OFU-ECOLog show comparable performance to OFUL-MLogB. The computational resources used by MNL-UCB, OFULog+, and ada-OFU-ECOLog are generally higher than OFUL-MLogB and EOFD-MLOgB. This phenomena is consistent with Section 5 and Appendix D of [6].

[1] Sanae Amani and Christos Thrampoulidis. UCB-based algorithms for multinomial logistic regression bandits. In Advances in Neural Information Processing Systems, volume 34, pages 2913–2924, 2021.

[2] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235–256, 2002.

[3] Louis Faury, Marc Abeille, Kwang-Sung Jun, and Clement Calauzenes. Jointly efficient and optimal algorithms for logistic bandits. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151, pages 546–580, 2022.

[4] Ilja Kuzborskij, Leonardo Cella, and Nicolò Cesa-Bianchi. Efficient linear bandits through matrix sketching. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 177–185, 2019.

[5] Junghyun Lee, Se-Young Yun, and Kwang-Sung Jun. Improved regret bounds of (multinomial) logistic bandits via regret-to-confidence-set conversion. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238, pages 4474–4482, 2024.

[6] Yu-Jie Zhang and Masashi Sugiyama. Online (multinomial) logistic bandit: Improved regret and constant computation cost. In Advances in Neural Information Processing Systems, volume 36, pages 29741–29782, 2023.

Thank you for your response and improvements on writing and experiment. I do not have any further questions.

Reviewer_FxmBOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The authors aim to reduce the per round time complexity of OFUL-MLogB [1] from O(K3d3)\mathcal{O}(K^3d^3) to O((K3+mK2+dmK)+dK(m+K)2)\mathcal{O}((K^3+mK^2+dmK)+dK(m+K)^2). They propose EOFD-MLogB, a more time- and space-efficient algorithm based on Frequent Directions (FD). By exploiting the structure of the Hessian matrix, they maintain a low-rank approximation instead of the full Hessian. They also theoretically and empirically demonstrate that the regret of EOFD-MLogB remains close to that of the original OFUL-MLogB when the sketching error is sufficiently small.

Critical strengths
  1. The authors successfully apply FD to the MNL bandit setting and theoretically characterize the effect of the sketching error on the final regret bound.

  2. They empirically validate the regret performance as well as the improvements in time and space complexity.

Critical weaknesses
  1. The novelty of the paper is unclear. A related exploitation of the structural properties of the MNL Hessian appears in [3]. The objective of that work is different: it concerns limited policy adaptivity rather than computational acceleration through Hessian sketching. Nevertheless, the structural observation and factorization are closely related to those used here. The authors should discuss this relationship and clarify which aspects of their construction are new. Since FD has already been used to improve the computational efficiency of bandit algorithms [2], the authors do not sufficiently establish what is novel about their proposed approach beyond adapting existing techniques to the MNL bandit setting.

  2. While the paper discusses why previous applications of FD to linear bandits cannot be directly extended to MNL bandits, the challenges involved in deriving the final regret bound are not sufficiently clear. The authors should better explain which parts of the confidence-set and regret analyses require new technical arguments beyond existing sketching-based bandit analyses and explicitly identify any novel theoretical insights arising from this extension.

[1] Zhang, Y.-J., and Sugiyama, M. "Online (Multinomial) Logistic Bandit: Improved Regret and Constant Computation Cost." NeurIPS 2023.

[2] Kuzborskij, I., Cella, L., and Cesa-Bianchi, N. "Efficient Linear Bandits through Matrix Sketching." AISTATS 2019.

[3] Midigeshi, S. P., Goyal, T., and Sinha, G. "Achieving Limited Adaptivity for Multinomial Logistic Bandits." Reinforcement Learning Journal, 2025.

Questions for authors

Please see weaknesses

4 comments

We thank the reviewer for bringing this reference [3] into our vision. We will take the opportunity to highlight our technical contribution and provide a more detailed discussion on the novelty compared with previous work [3].

  1. Clarification of novelty.
  • Comparison with [3]. We agree that the per-round Hessian square-root factorization in our Algorithm 1 is closely related to that in [3] (Eq. (8) and Lemmas 7.11 and 8.10). However, our work has a different goal and faces distinct technical challenges. Specifically, unlike [3], which focuses on limited policy adaptivity, our work addresses computational efficiency through Hessian sketching. This requires new techniques for efficient ONS updates and second-order UCB bonus computation, as well as additional regret arguments to control the resulting sketching errors, which are not addressed in [3].
  • Comparison with linear case [2]. Although [2] provide how to leverage the FD in linear bandits on both parameter estimation and bonus calculation, there are substantial challenge for going from linear to MLogB due to the non-linear structure of the reward.
    • ONS update: unlike linear bandits, where there exists the closed-form solution for parameter estimation, our constrained ONS update requires solving a nonlinear projection problem (QCQP). To tackle this, we reduce this non-linear problem to an 11-dimensional root-finding task, and reduce the one-step sketching errors to a telescoping term ρ1:t−ρ1:t−1\rho_{1:t}-\rho_{1:t-1} in the corresponding proof.
    • Second-order UCB bonus: unlike linear bandits [2], whose UCB bonuses involve only a first-order linear term, our UCB construction incorporates an additional second-order term to account for the nonlinear MNL reward, which involves a high-dimensional spectral norm. To address this, Lemma 1 reduces its computation to a K×KK\times K eigenvalue problem using the sketched Hessian, while Lemma 5 controls the corresponding exploration widths in the regret analysis. Those challenges are not studied neither in [2] nor in [3].

We will cite [3] in Section 3.2.1 and highlight the similarity and difference in the revision.

  1. Technical arguments for the confidence and regret bounds. Applying RFD to MNL introduces additional challenges in deriving the confidence-set and the final regret bound.
    • Accumulated sketching error in the confidence radius: in the proof of Theorem 1, Eq. (32) controls the estimation error in the metric Zt+∇2ℓt(Wt+1)Z_t+\nabla^2\ell_t(W_{t+1}), while the next ONS update requires Zt+1Z_{t+1}. We use Lemma 3 to control squared estimation error across rounds by a telescoping term ρ1:t−ρ1:t−1\rho_{1:t}-\rho_{1:t-1}, and incorporate its contribution into the confidence bound in Eq. (33) to quantify the effect of the sketching.
    • Uniform control of squared exploration widths: Lemma 5 applies the RFD spectral error bound to the full regularized Hessian HtH_t accumulated along the same iterates, giving Ht⪯(1+ρ1:t−1/(λ+ρ1:t−1))Zt⪯2ZtH_t\preceq (1+\rho_{1:t-1}/(\lambda+\rho_{1:t-1}))Z_t\preceq 2Z_t. Thus, the squared exploration widths under Zt−1Z_t^{-1} are at most twice those under Ht−1H_t^{-1}, a bound used in Theorem 2 and Proposition 1. For FD in [2], the corresponding factor Δt\Delta_t in Ht⪯ΔtZtH_t\preceq\Delta_tZ_t grows with the cumulative sketching error.

Together, these bounds show that cumulative sketching error enters the MNL confidence radius, while the comparison factor for squared exploration widths remains uniformly bounded.

A key insight is that, Lemma 5 shows that the resulting squared exploration widths remain at most twice their full-Hessian counterparts along the same iterates, independently of the accumulated sketching error, whereas the corresponding comparison factor Δt∣x∣Zt−1\Delta_t\\|x\\|_{Z_t^{-1}} in [2] depends on the cumulative sketching error. This exhibits more robustness in the exploration widths of MNL, while the MNL cumulates effect to the squared confidence radius despite more accurate RFD sketching (ρ1:t−ρ1:t−1\rho_{1:t}-\rho_{1:t-1} term). This highlights the importance of exploiting the curvature of the multinomial logistic loss to control parameter estimation error when constructing the UCB in MNL.

We thank the reviewer for raising this point. We will revise Section 3.3 and Appendix B.2 to explain these two steps and clarify which parts of the analysis rely on existing sketching results.

[1] Zhang, Y.-J., and Sugiyama, M. "Online (Multinomial) Logistic Bandit: Improved Regret and Constant Computation Cost." NeurIPS 2023.

[2] Kuzborskij, I., Cella, L., and Cesa-Bianchi, N. "Efficient Linear Bandits through Matrix Sketching." AISTATS 2019.

[3] Midigeshi, S. P., Goyal, T., and Sinha, G. "Achieving Limited Adaptivity for Multinomial Logistic Bandits." Reinforcement Learning Journal, 2025.

Dear Reviewer,

Thank you again for your review. We would appreciate your timely feedback on our rebuttal. For ease of reference, we briefly summarize the key distinctions from prior work [2,3] below.

Our work focuses on alleviate the online computational burden in high-dimensional settings, while [3] focus on amortize the total computation to reduce the increasing batch estimation. Specifically, building on the per-round Hessian factorization (also used in [3]), we use the spectral-form sketch to enable the efficient ONS update and efficient calculations for the second-order bonus, which is not covered in [3], and is the main technical gap between [2] and MNL. Those are new aspects in our construction.

Our rebuttal also identifies a step beyond the linear-bandit analysis in the proof of [2]. Eq. (32) controls the estimation error before sketching, while the next ONS update requires the compressed metric. To bridge this gap, we bound those errors to get a telescoping term, and sum over tt to get the squared confidence radius in Eq. (33). Additionally, we use our new Lemma 5 to estimate the Hessian HtH_t using the sketch in our regret analysis, instead of the technique used in [2]. Those techniques in proof, together with our ONS and second-order bonus adaption that allow RFD computations in MNL, is novel beyond adapting existing techniques [2] to the MNL bandit setting.

Further details are provided in our previous rebuttal. We would appreciate your feedback on whether these clarifications address your concerns about the novelty of our construction and analysis. We would be happy to elaborate on any remaining questions. Could you please let us know whether our rebuttal addresses your concerns about novelty, or which specific concerns remain?

Best regards,

Authors

Reviewer_FxmBOpenReview ↗

Thanks

Thanks for the answers. I'm not sure about significance of the novelty in the ONS update and the second order UCB bonus that has been highlighted by you. Specifically, what is the main challenge that you face in doing these two and why you think it is non-trivial.

  1. In other sketched ONS methods [4,5], the updates are assumed to be either unconstrained or to admit closed-form solutions, so they can be computed efficiently. In our setting, however, the update is constrained and has no closed-form solution. Directly passing the sketched matrix ZtZ_t to a solver would still require O(1/ϵ)O(1/\epsilon) iterations, each involving operations on WW and ZtZ_t whose cost depends on dd. In high-dimensional settings, performing these operations so many times remains too expensive. We reduce this computation to a one-dimensional problem.

  2. Directly evaluating ∥Zt−1/2(IK⊗x)∥22\|Z_t^{-1/2}(I_K\otimes x)\|_2^2 using the original formula requires constructing the full Kd×KKd\times K matrix and then computing its spectral norm. This still requires a spectral computation on a large matrix. We reduce it to a computation on a small matrix.

  3. [2] uses FD, whereas we use RFD, so the two algorithms cannot be treated as equivalent.

  4. [2] relies on a self-normalized bound for vector-valued martingales, whereas our MNL setting uses an OMD analysis. These are two entirely different analytical techniques.

[4] Sifan Yang, Yuanyu Wan, Peijia Li, Yibo Wang, Xiao Zhang, Zhewei Wei, and Lijun Zhang. Dimension-free adaptive subgradient methods with frequent directions. In Proceedings of The 42nd International Conference on Machine Learning, 2025.

[5] Haipeng Luo, Alekh Agarwal, Nicolò Cesa-Bianchi, and John Langford. Efficient second order online learning by sketching. In Advances in Neural Information Processing Systems, volume 29, 2016.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.