Introduction
Contextual bandits are a cornerstone of sequential decision-making in applications ranging from personalized recommendations to clinical trials. Traditionally, contexts in these problems are treated as flat vectors. However, in many real-world scenarios, contexts naturally form matrices—such as a recommendation system representing a user-item interaction as the outer product of user and item feature vectors.
Flattening these matrices into massive vectors ignores their inherent low-rank structure, leading to computationally prohibitive algorithms with poor performance. While recent works have explored "low-rank matrix bandits," they often assume simple linear rewards, restrict action spaces, or require computationally impossible steps. Prior to this paper, existing algorithms for generalized (non-linear) low-rank matrix bandits suffered from suboptimal theoretical regret bounds—scaling with $d^{3/2}$ (where $d$ is the matrix dimension)—and were too slow for practical use.
To address this, the authors propose two novel two-stage algorithms, G-ESTT and G-ESTS. These frameworks tackle the generalized low-rank matrix bandit problem by achieving both computational feasibility and an optimal theoretical regret bound, significantly outperforming existing methods in speed and accuracy.
Methodology: Explore-Then-Commit Frameworks
The authors propose two "Explore-Then-Commit" style frameworks that operate in two distinct stages:
- Stage 1: Subspace Exploration. The algorithm randomly pulls arms to estimate the underlying low-rank structure (the row and column subspaces) of the true reward matrix. To handle non-linear rewards (Generalized Linear Models, or GLMs), the authors use a novel adaptation of Stein’s method combined with nuclear norm regularization. This clever workaround allows the algorithm to accurately estimate the subspace without requiring strict sub-Gaussian assumptions on the context data, needing only a finite second-moment score.
- Stage 2: Exploitation. Once the low-rank subspace is identified, the problem is transformed to focus on this smaller space. The authors offer two approaches:
- G-ESTT (Generalized Explore Subspace Then Transform): This method rotates the feature space and applies a modified GLM-UCB algorithm. It uses a specialized regularization penalty to suppress non-informative dimensions (the subspace orthogonal to the true parameters).
- G-ESTS (Generalized Explore Subspace Then Subtract): A more radical and efficient approach. Instead of penalizing the non-informative dimensions, it explicitly drops them entirely. This "dimension reduction" step reduces the massive matrix problem into a standard, low-dimensional bandit problem, which can then be solved using any fast, off-the-shelf bandit algorithm (like SGD-TS). Exclusion proves to be vastly superior to penalization in practice.
Key Results and Theoretical Breakthrough
By properly isolating the low-rank subspace, the authors close a significant theoretical gap. Both G-ESTT and G-ESTS achieve a regret bound of $\tilde{O}((d_1+d_2)r\sqrt{T})$. This improves upon the previous state-of-the-art bound of $\tilde{O}((d_1+d_2)^{3/2}\sqrt{rT})$ by a factor of $\sqrt{d}$, matching the known theoretical lower bound for this problem and proving asymptotic optimality.
The authors evaluated their algorithms using simulated datasets, generating random matrices of size $10 \times 10$ and $12 \times 12$ with rank $r=1$ and $r=2$. Rewards were generated using a logistic model to test non-linear GLM capabilities.
Empirically, both G-ESTT and G-ESTS consistently achieved lower cumulative regret than baselines like LowESTR (a linear low-rank bandit algorithm) and a naive SGD-TS algorithm that flattens the matrices. Furthermore, G-ESTS demonstrated massive computational speedups. In the $d=10, r=1$ simulation, G-ESTS took only ~39 minutes to run, compared to ~516 minutes for G-ESTT and ~401 minutes for LowESTR. This ~10x speedup highlights G-ESTS as highly practical for real-world deployment.
Limitations and Future Work
While theoretically sound, G-ESTT still requires calculating Maximum Likelihood Estimates (MLE) in high-dimensional spaces, making it computationally heavy—which motivated the development of G-ESTS. Additionally, the two-stage "explore-then-commit" design is somewhat rigid, as it fixes the subspace estimation early on without subsequent updates.
For future work, the authors suggest extending this low-rank structure to modern neural contextual bandits, moving beyond Generalized Linear Models. They also propose developing fully online algorithms that continuously update the subspace estimation on-the-fly (e.g., via online SVD) rather than relying on a strict two-stage split.
Summary updated