Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits

In many real-world decision-making scenarios, such as medical treatment planning or resource allocation, learners must optimize multiple objectives with strict priority levels using matrix-valued actions. Existing generalized low-rank matrix bandit algorithms are primarily designed for scalar rewards and often rely on batch estimation techniques that are computationally prohibitive for long-horizon online learning. This paper addresses the challenge of designing a computationally efficient algorithm that can handle prioritized multi-objective feedback while exploiting the low-rank structure of the parameter matrices.

The authors introduce Lexi-LowGLM, an algorithm that operates in two main phases. First, it performs objective-specific subspace estimation to identify the row and column subspaces of the parameter matrices. Second, it utilizes these subspaces to construct transformed feature representations, allowing the learner to perform lexicographic learning in a reduced-dimensional space. Unlike previous methods that recompute a batch generalized linear estimator at every round—incurring O(T^2) complexity—Lexi-LowGLM employs an online Newton-type proximal update, which reduces the cumulative estimator-update complexity to O(T).

The study establishes that Lexi-LowGLM achieves an objective-wise regret bound of O(W_i^lex * sqrt(m * (d1+d2)r * T)), where W_i^lex represents the lexicographic trade-off effect. This bound is significant because it depends on the effective low-rank dimension (d1+d2)r rather than the ambient dimension d1*d2, matching the performance of state-of-the-art single-objective algorithms. Numerical experiments confirm that the proposed method is both effective at managing prioritized objectives and computationally efficient compared to batch-based alternatives.

This work bridges the gap between low-rank matrix bandit theory and multi-objective decision-making. By enabling efficient online updates, the algorithm makes it feasible to apply low-rank matrix bandit models to complex, high-dimensional, and long-horizon problems where multiple competing objectives must be satisfied according to a strict hierarchy.