Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits

arXiv:2608.04324v1 Announce Type: cross Abstract: 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 extsc{Lexi-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, extsc{Lexi-LowGLM} updates each objective-specific estimator via an online Newton step, reducing the estimator-update complexity over T rounds from O(T^2) to O(T). We establish a regret bound of widetilde Oleft(W_i^{rm lex}sqrt{m},(d_1+d_2)rsqrt{T}right) for each objective iin[m], where r is an upper bound on the ranks of the objective-specific parameter matrices and W_i^{rm lex} characterizes the lexicographic trade-off effect. This bound depends on the effective low-rank dimension (d_1+d_2)r rather than the ambient dimension d_1d_2. Numerical experiments further validate the effectiveness and computational efficiency of the proposed method.

Source: arXiv cs.AI | 2026-08-06