Abstract
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 O(Kd√T), but still requires O(K³d³) time and O(K²d²) 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, which integrates frequent directions matrix sketching into OFUL-MLogB. By maintaining a low-rank SVD sketch of the accumulated Hessian, constrained online Newton updates in parameter estimation and Kd × K spectral-norm computations in the reward bonus are reduced to one-dimensional root-finding tasks and K × K eigenvalue computations, respectively. This yields dominant per-round time complexity O(Kd(m+K)²) and space complexity O(Kd(m+K)), where m ≪ d is the sketch size. We further prove a regret bound of O(Δ_T(KdlnΔ_T+m)√T), where the sketching error factor Δ_T is controlled by the m-truncated spectral tail of the Hessian. Thus, when the Hessian is approximately low-rank, the regret is close to that of OFUL-MLogB. Experiments validate the computational efficiency and competitive performance.