Abstract
In the stochastic contextual low-rank matrix bandit problem, the expected reward of an action is given by the inner product between the action's feature matrix and some fixed, but initially unknown d₁ by d₂ matrix Θ^* with rank r ≪ {d₁, d₂}, and an agent sequentially takes actions based on past experience to maximize the cumulative reward. In this paper, we study the generalized low-rank matrix bandit problem, which has been recently proposed in \cite{lu2021low} under the Generalized Linear Model (GLM) framework. To overcome the computational infeasibility and theoretical restrain of existing algorithms on this problem, we first propose the G-ESTT framework that modifies the idea from \cite{jun2019bilinear} by using Stein's method on the subspace estimation and then leverage the estimated subspaces via a regularization idea. Furthermore, we remarkably improve the efficiency of G-ESTT by using a novel exclusion idea on the estimated subspace instead, and propose the G-ESTS framework. We also show that G-ESTT can achieve the O(√(d₁+d₂)MrT) bound of regret while G-ESTS can achineve the O(√(d₁+d₂)^3/2Mr^3/2T) bound of regret under mild assumption up to logarithm terms, where M is some problem dependent value. Under a reasonable assumption that M = O((d₁+d₂)²) in our problem setting, the regret of G-ESTT is consistent with the current best regret of O((d₁+d₂)^3/2 √rT/D_rr)~\citep{lu2021low} (D_rr will be defined later). For completeness, we conduct experiments to illustrate that our proposed algorithms, especially G-ESTS, are also computationally tractable and consistently outperform other state-of-the-art (generalized) linear matrix bandit methods based on a suite of simulations.