Search papers, labs, and topics across Lattice.
This paper introduces EOFD-MLogB, an efficient online algorithm for multinomial logistic bandits that leverages frequent directions matrix sketching to significantly reduce the computational burden of parameter estimation and reward construction. By maintaining a low-rank SVD sketch of the Hessian, the method achieves a per-round time complexity of $\mathcal{O}(Kd(m+K)^2)$ and space complexity of $\mathcal{O}(Kd(m+K))$, where $m$ is the sketch size. The proposed algorithm demonstrates a regret bound of $\tilde{\mathcal{O}}(螖_T(Kd\ln螖_T+m)\sqrt{T})$, maintaining competitive performance while improving efficiency in high-dimensional settings.
By integrating frequent directions matrix sketching, EOFD-MLogB slashes the computational costs of multinomial logistic bandits without sacrificing performance.
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^3d^3)$ time and $\mathcal{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 \times K$ spectral-norm computations in the reward bonus are reduced to one-dimensional root-finding tasks and $K \times K$ eigenvalue computations, respectively. 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}}(螖_T(Kd\ln螖_T+m)\sqrt{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.
UW