Efficient Multinomial Logistic Bandit via Robust Frequent Directions

This paper studies efficient online algorithms for multinomial logistic bandits (MLogB), where the feedback distribution over $K+1$ outcomes follows a multinomial logistic model of $d$-dimensional action vectors. A representative UCB-type algorithm, OFUL-MLogB, achieves a regret bound of $\tilde{\mathcal{O}}(Kd\sqrt{T})$, but still requires $\mathcal{O}(K^3{d}^3)$ time and $\mathcal{O}(K^2{d}^2)$ 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 $Kd\times K$ spectral-norm computation in the optimistic reward is reduced to a $K\times K$ eigenvalue problem. This yields dominant per-round time complexity $\mathcal{O}(Kd(m+K{)}^2)$ and space complexity $\mathcal{O}(Kd(m+K))$, where $m\ll d$ is the sketch size. We further prove a regret bound of $\tilde{\mathcal{O}}({\Delta }_T(Kd\ln {\Delta }_T+m)\sqrt{T})$, where the sketching error factor ${\Delta }_T$ is controlled by the $m$-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.