Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits

This paper studies generalized low-rank matrix bandits with multiple prioritized objectives. At each round, the learner selects a matrix-valued arm and observes a vector-valued reward, whose components correspond to multiple objectives with different priority levels. Each objective is governed by an objective-specific generalized low-rank matrix model, and the learner evaluates arms according to a lexicographic preference order, prioritizing higher-level objectives before lower-level ones. We propose textscLexi-LowGLM, an efficient online algorithm that first estimates objective-specific low-rank subspaces and then performs lexicographic learning in the reduced feature spaces. Unlike existing single-objective algorithms that repeatedly solve a batch generalized linear estimator using all historical observations, textscLexi-LowGLM updates each objective-specific estimator via an online Newton step, reducing the estimator-update complexity over T rounds from O(T2) to O(T). We establish a regret bound of widetilde Oleft(Wirm lex√m,(d1+d2)r√Tright) for each objective i∈[m], where r is an upper bound on the ranks of the objective-specific parameter matrices and Wirm lex characterizes the lexicographic trade-off effect. This bound depends on the effective low-rank dimension (d1+d2)r rather than the ambient dimension d1d2. Numerical experiments further validate the effectiveness and computational efficiency of the proposed method.