Efficient Multinomial Logistic Bandit via Frequent Directions

arXiv:2606.11968v1 Announce Type: new 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 ilde{O}(Kdsqrt{T}), but still requires O(K^3d^3) time and O(K^2d^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, 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 imes K spectral-norm computations in the reward bonus are reduced to one-dimensional root-finding tasks and K imes K eigenvalue computations, respectively. This yields dominant per-round time complexity O(Kd(m+K)^2) and space complexity O(Kd(m+K)), where m ll d is the sketch size. We further prove a regret bound of ilde{O}(Delta_T(KdlnDelta_T+m)sqrt{T}), where the sketching error factor Delta_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.

Source: arXiv cs.LG | 2026-06-11