# Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits

arXiv: https://arxiv.org/abs/2608.04324 · HTML: https://mlsanity.com/paper/2608.04324/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 41 references that are in the map.
- First posted on arXiv 5 Aug 2026.

## Builds on (most cited first, 18 of 18)

- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Low-Rank Generalized Linear Bandit Problems](https://mlsanity.com/paper/2006.02948/) (2020)
- [Multi-objective Bandits: Optimizing the Generalized Gini Index](https://mlsanity.com/paper/1706.04933/) (2017)
- [Multi-objective Contextual Bandit Problem with Similarity Information](https://mlsanity.com/paper/1803.04015/) (2018)
- [Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems](https://mlsanity.com/paper/2401.07298/) (2024)
- [Lexicographic Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2212.13769/) (2022)
- [Multi-objective Contextual Multi-armed Bandit with a Dominant Objective](https://mlsanity.com/paper/1708.05655/) (2017)
- [Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2407.17466/) (2024)
- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Pareto Regret Analyses in Multi-objective Multi-armed Bandit](https://mlsanity.com/paper/2212.00884/) (2022)
- [Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits](https://mlsanity.com/paper/2402.11156/) (2024)
- [Low-Rank Contextual Reinforcement Learning from Heterogeneous Human Feedback](https://mlsanity.com/paper/2412.19436/) (2024)
- [Thresholded Lexicographic Ordered Multiobjective Reinforcement Learning](https://mlsanity.com/paper/2408.13493/) (2024)
- [Optimal Scalarizations for Sublinear Hypervolume Regret](https://mlsanity.com/paper/2307.03288/) (2023)
- [Low-rank Matrix Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2404.17709/) (2024)
- [Multi-task Representation Learning for Pure Exploration in Bilinear Bandits](https://mlsanity.com/paper/2311.00327/) (2023)
- [Generalized Low-Rank Matrix Contextual Bandits with Graph Information](https://mlsanity.com/paper/2507.17528/) (2025)
- [Thompson Sampling for Multi-Objective Linear Contextual Bandit](https://mlsanity.com/paper/2512.00930/) (2025)

## Built on by (most cited first, 2 of 2)

- [Few-for-Many Best-Arm Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2610.16840/) (2026)
- [When More Objectives Make Identification Easier: The Role of Preferences and Feedback](https://mlsanity.com/paper/2610.18577/) (2026)

## Abstract (arXiv)

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.