Paper deep dive
Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits
Bo Xue, Ji Cheng, Haodong Jing, Hongzong Li, Shuang Qiu
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/9/2026, 3:21:19 AM
Summary
This paper introduces Lexi-LowGLM, an efficient online algorithm for generalized low-rank matrix bandits with multiple prioritized objectives. The algorithm estimates objective-specific low-rank subspaces and performs lexicographic learning in reduced feature spaces. It utilizes online Newton steps to update estimators, reducing computational complexity from O(T^2) to O(T) and achieving a regret bound dependent on the effective low-rank dimension rather than the ambient dimension.
Entities (6)
Relation Signals (5)
Lexi-LowGLM → solves → Generalized Low-Rank Matrix Bandits
confidence 95% · This paper studies generalized low-rank matrix bandits... We propose Lexi-LowGLM
Lexi-LowGLM → uses → Online Newton Step
confidence 92% · Lexi-LowGLM updates each objective-specific estimator via an online Newton step
Lexi-LowGLM → achieves → Regret Bound
confidence 90% · We establish a regret bound of O~(...) for each objective
Lexi-LowGLM → optimizes → Lexicographic Preference
confidence 90% · the learner evaluates arms according to a lexicographic preference order... Lexi-LowGLM... performs lexicographic learning
Online Newton Step → reduces → Computational Complexity
confidence 85% · reducing the estimator-update complexity over T rounds from O(T^2) to O(T)
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 \textsc{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, \textsc{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 O\left(W_i^{\rm lex}\sqrt{m}\,(d_1+d_2)r\sqrt{T}\right)$ for each objective $i\in[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.
Tags
Links
- Source: https://arxiv.org/abs/2608.04324v1
- Canonical: https://arxiv.org/abs/2608.04324v1
PDF not stored locally. Use the link above to view on the source site.
Full Text
114,101 characters extracted from source content.
Expand or collapse full text
22footnotetext: Corresponding Author Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits Bo Xue Ji Cheng Haodong Jing Hongzong Li Shuang Qiu† City University of Hong Kong. Email: boxue4-c@my.cityu.edu.hkCity University of Hong Kong. Email: J.Cheng@my.cityu.edu.hkXi’an Jiaotong University. Email: jinghd@stu.xjtu.edu.cnNorthwestern Polytechnical University. Email: lihongzong@nwpu.edu.cnCity University of Hong Kong. Email: shuanqiu@cityu.edu.hk 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 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, Lexi-LowGLM updates each objective-specific estimator via an online Newton step, reducing the estimator-update complexity over T rounds from O(T2)O(T^2) to O(T)O(T). We establish a regret bound of O~(Wilexm(d1+d2)rT) O (W_i lex m\,(d_1+d_2)r T ) for each objective i∈[m]i∈[m], where r is an upper bound on the ranks of the objective-specific parameter matrices and WilexW_i lex characterizes the lexicographic trade-off effect. This bound depends on the effective low-rank dimension (d1+d2)r(d_1+d_2)r rather than the ambient dimension d1d2d_1d_2. Numerical experiments further validate the effectiveness and computational efficiency of the proposed method. 1 Introduction Contextual bandits provide a fundamental framework for sequential decision-making under uncertainty (Robbins, 1952; Lai and Robbins, 1985; Auer, 2002), with widespread applications in personalized recommendation (Li et al., 2010), online advertising (Schwartz et al., 2017), and resource allocation (Khansa et al., 2021). At each round, the learner observes a context, selects an action, and receives feedback only for the chosen action. In many applications, however, actions are more naturally represented as matrices rather than vectors, especially when rewards depend on pairwise interactions between two feature groups, such as users and items in recommendation, flights and hotels in bundle selection, or agents and tasks in matching platforms (Jun et al., 2019; Kang et al., 2022). Although matrix-valued actions can be vectorized and handled using standard bandit algorithms (Dani et al., 2008; Filippi et al., 2010), such a reduction discards their intrinsic structural information and may lead to substantial statistical and computational inefficiency in high-dimensional problems. To address this challenge, generalized low-rank matrix bandits assume that the unknown parameter matrix has low rank (Jun et al., 2019). Specifically, the expected reward of an arm X∈ℝd1×d2X ^d_1× d_2 is modeled as μ(⟨X,Θ∗⟩)μ( , ^* ), where μ(⋅)μ(·) is an inverse link function and Θ∗ ^* is an unknown rank r matrix. By exploiting the row and column subspaces of Θ∗ ^*, existing methods achieve regret bounds that scale with the effective low-rank dimension, roughly (d1+d2)r(d_1+d_2)r, rather than the ambient dimension d1d2d_1d_2 (Jang et al., 2021; Lu et al., 2021). However, existing generalized low-rank matrix bandit algorithms are mainly developed for scalar rewards (Kang et al., 2024; Wang et al., 2025), which limits their applicability to online decision-making problems involving multiple objectives. In many applications, the learner observes vector-valued feedback that captures several objectives to be optimized jointly, and these objectives often have different priorities. For example, radiation treatment planning jointly considers target coverage and the protection of organs at risk, with target coverage typically assigned higher priority (Jee et al., 2007). Similarly, water resource planning involves competing objectives such as flood protection, irrigation shortage reduction, and electricity generation, whose importance is naturally ordered by practical needs (Weber et al., 2002). These examples motivate the use of lexicographic preferences (Ehrgott, 2005), under which higher-priority objectives are optimized first and lower-priority objectives are considered only among arms that remain competitive with respect to all higher-priority objectives. Although lexicographic bandits have been studied in various settings (Tekin and Turgay, 2018; Hüyük and Tekin, 2021; Xue et al., 2025b), existing methods do not account for generalized low-rank matrix structures. Directly applying them to vectorized matrix arms would cause both regret and computational complexity to scale with the ambient dimension d1d2d_1d_2, thereby losing the advantages of low-rank modeling. Conversely, existing generalized low-rank matrix bandit algorithms primarily focus on scalar rewards (Kang et al., 2022) and therefore cannot directly accommodate multiple objectives with strict priorities. Beyond the challenge of jointly exploiting low-rank structures and coordinating decisions according to lexicographic priorities, computational efficiency poses an additional challenge. Existing generalized low-rank matrix bandit methods typically recompute a batch generalized linear estimator using all historical observations at every round (Kang et al., 2022). Although this approach facilitates theoretical analysis, it repeatedly processes past data and incurs a cumulative estimator-update complexity of O(T2)O(T^2) over T rounds, making it unsuitable for long-horizon online learning. Therefore, a natural question arises: Can we design a computationally efficient algorithm for lexicographic generalized low-rank matrix bandits? In this paper, we study lexicographic generalized low-rank matrix bandits, an online learning problem with matrix-valued arms and multiple prioritized objectives. Our main contributions are summarized as follows. • Problem formulation. To the best of our knowledge, we are the first to formulate generalized low-rank matrix bandits with multi-objective feedback, moving beyond the conventional scalar-reward matrix bandits to settings in which multiple objectives are optimized simultaneously. • Efficient algorithm. We propose Lexi-LowGLM, an efficient lexicographic learning algorithm that exploits objective-specific low-rank structure while updating estimators online. By replacing repeated batch estimation with an online Newton-type proximal update, Lexi-LowGLM reduces the cumulative estimator-update complexity over T rounds from O(T2)O(T^2) to O(T)O(T). • Regret guarantee. We establish an objective-wise regret bound for Lexi-LowGLM. Specifically, for each objective i∈[m]i∈[m], the regret scales as O~(Wilexm(d1+d2)rT) O(W_i lex m\,(d_1+d_2)r T), where Wilex=1+w+⋯+wi−1W_i lex=1+w+·s+w^i-1 quantifies the effect of lexicographic priority propagation. This result matches the state-of-the-art dependence on the horizon and the effective low-rank dimension in the single-objective setting (Kang et al., 2022), while simultaneously controlling the regret of all objectives. When w=0w=0, we have Wilex=1W_i lex=1 for all i∈[m]i∈[m], so the lexicographic structure incurs no additional priority-propagation penalty, yielding a uniform regret guarantee across all objectives. • Empirical validation. We conduct numerical experiments to verify the effectiveness and computational efficiency of the proposed algorithm. 2 Related Work In this section, we review related work on matrix bandits and multi-objective bandits. Matrix Bandits. Matrix bandits extend contextual linear bandits (Abbasi-yadkori et al., 2011; Chu et al., 2011) to matrix-valued arms by exploiting structural assumptions on the unknown parameter matrix. A representative line of work focuses on low-rank structure, where the goal is to avoid the ambient-dimensional dependence incurred by vectorizing matrix arms. Jun et al. (2019) introduced bilinear bandits and proposed an explore-subspace-then-refine strategy. Subsequent works improved this line by leveraging the geometry of the action space (Jang et al., 2021), studying pure exploration with shared representations (Mukherjee et al., 2023), and developing robust algorithms under heavy-tailed rewards (Kang et al., 2024). More recent works consider generalized low-rank matrix bandits, where the expected reward follows a generalized linear model. Lu et al. (2021) studied this problem beyond the bilinear setting, but their covering-based algorithm can be computationally expensive. Kang et al. (2022) improved computational tractability through Stein-type subspace estimation and low-rank generalized linear bandit learning. Other extensions further exploit arm-set geometry (Jang et al., 2024), graph information (Wang et al., 2025), or low-rank structures in related feedback models (Lee et al., 2026). However, these works focus on scalar rewards and do not address prioritized multi-objective feedback, which is the focus of this paper. Multi-Objective Bandits. Multi-objective bandits study online decision-making with vector-valued rewards. A common approach is to aggregate multiple objectives into a scalar reward (Drugan and Nowe, 2013). Busa-Fekete et al. (2017) optimized the generalized Gini index in multi-objective bandits, while more recent work studied nonlinear scalarizations such as hypervolume scalarization and established sublinear hypervolume regret for multi-objective stochastic linear bandits (Zhang, 2024). Another line of work adopts Pareto optimality as the preference model. Early studies considered Pareto regret in multi-objective Multi-Armed Bandits (MABs) and contextual bandits (Turgay et al., 2018; Lu et al., 2019; Cai et al., 2023), and recent work further developed Pareto regret analysis for both stochastic and adversarial multi-objective MABs (Xu and Klabjan, 2023; Park et al., 2025). Related pure-exploration studies aim to identify the Pareto front with sample-complexity guarantees (Auer et al., 2016; Crepon et al., 2024). Moreover, recent studies on multi-objective reinforcement learning with bandit feedback (Qiu et al., 2024) further extend multi-objective MABs to the multi-objective Markov decision processes. Another important formulation for multi-objective decision-making is based on lexicographic preferences, which explicitly encode priority relations among objectives. Under lexicographic ordering, objectives are optimized sequentially according to their importance, so that lower-priority objectives are considered only after higher-priority objectives have been sufficiently addressed. Lexicographic preferences have been studied in multi-objective MABs (Hüyük and Tekin, 2021), contextual bandits (Tekin and Turgay, 2018), and stochastic linear bandits (Xue et al., 2025b). Related lexicographic preference models have also been explored in reinforcement learning (RL), including lexicographic multi-objective RL (Skalse et al., 2022; Alperen Tercan, 2024) and lexicographic linear MDPs (Xue et al., 2025a). However, these methods do not consider low-rank matrix structures. 3 Preliminaries In this section, we formulate the lexicographic generalized low-rank matrix bandit problem and introduce several auxiliary tools for handling the low-rank structure. Notations. Let [n]=1,2,…,n[n]=\1,2,…,n\ for any positive integer n. Given a vector x∈ℝdx ^d, ‖x‖2\|x\|_2 denotes its Euclidean norm, and for a positive definite matrix V∈ℝd×dV ^d× d, its weighted norm is ‖x‖V=x⊤Vx\|x\|_V= x Vx. For a matrix A∈ℝd1×d2A ^d_1× d_2, ‖A‖F\|A\|_F, ‖A‖op\|A\|_op, and ‖A‖nuc\|A\|_nuc denote its Frobenius norm, operator norm, and nuclear norm, respectively. The inner product between two matrices A,B∈ℝd1×d2A,B ^d_1× d_2 is defined as ⟨A,B⟩=trace(A⊤B) ,B =trace(A B). vec(A)vec(A) denotes the vectorization of AA obtained by stacking its columns, and O~(⋅) O(·) hides logarithmic factors. Learning Model. Lexicographic generalized low-rank matrix bandits consider a T-round sequential decision-making problem. At each round t∈[T]t∈[T], the learner first observes the arm set ⊆ℝd1×d2X ^d_1× d_2, selects an arm Xt∈X_t , and then receives a stochastic reward vector yt=(yt,1,…,yt,m)∈ℝmy_t=(y_t,1,…,y_t,m) ^m, where m is the number of objectives. For each objective i∈[m]i∈[m], the expected reward is modeled by an objective-specific generalized low-rank matrix model: E[yt,i∣Xt]=μi(⟨Xt,Θi∗⟩),E[y_t,i _t]= _i\! ( _t, _i^* ), where μi(⋅) _i(·) is an inverse link function, and Θi∗∈ℝd1×d2 _i^* ^d_1× d_2 is an unknown low-rank parameter matrix. Equivalently, the observed reward can be written as yt,i=μi(⟨Xt,Θi∗⟩)+ηt,i,i∈[m],y_t,i= _i\! ( _t, _i^* )+ _t,i,i∈[m], where ηt,i _t,i is zero-mean noise. Lexicographic Preference and Regret. For any two arms X,X′∈X,X , we say that XX lexicographically dominates X′X if there exists an objective index i∈[m]i∈[m] such that μj(⟨X,Θj∗⟩) _j\! ( , _j^* ) =μj(⟨X′,Θj∗⟩),∀j∈[i−1], = _j\! ( , _j^* ),∀ j∈[i-1], μi(⟨X,Θi∗⟩) _i\! ( , _i^* ) >μi(⟨X′,Θi∗⟩). > _i\! ( , _i^* ). An arm X∗∈X_* is lexicographically optimal if it is not lexicographically dominated by any other arm in X. We evaluate the performance of the learner using the objective-wise cumulative regret with respect to the lexicographically optimal arm X∗X_*. Specifically, for each objective i∈[m]i∈[m], the cumulative regret is defined as Ri(T)=∑t=1T[μi(⟨X∗,Θi∗⟩)−μi(⟨Xt,Θi∗⟩)].R_i(T)= _t=1^T [ _i\! ( _*, _i^* )- _i\! ( _t, _i^* ) ]. This quantity measures the cumulative loss on objective i incurred by selecting XtX_t instead of the lexicographically optimal arm X∗X_*. The goal is to design an algorithm that achieves sublinear growth of Ri(T)R_i(T) for every objective i∈[m]i∈[m], thereby ensuring that the learner approaches the lexicographic optimal arm while controlling the regret of every objective. We impose the following assumptions, which are standard in the literature on generalized low-rank matrix bandits (Kang et al., 2024; Wang et al., 2025) and lexicographic bandit learning (Xue et al., 2025b). Assumption 1 (Low-rank structure) For each objective i∈[m]i∈[m], the unknown parameter matrix Θi∗ _i^* is of rank at most r, i.e., rank(Θi∗)≤rrank( _i^*)≤ r, where r≪mind1,d2r \d_1,d_2\. Assumption 2 (Bounded parameters and arms) There exists a constant S>0S>0 such that ‖Θi∗‖F≤S\| _i^*\|_F≤ S for all i∈[m]i∈[m]. The arm set is normalized so that ‖X‖F≤1\|X\|_F≤ 1 for all X∈X . Assumption 3 (Regular link functions) For each objective i∈[m]i∈[m], the inverse link function μi(⋅) _i(·) is continuously differentiable. There exist constants 0<cμ≤Lμ0<c_μ≤ L_μ such that, over the relevant domain, cμ≤μi′(z)≤Lμ,∀i∈[m]c_μ≤μ _i(z)≤ L_μ,∀ i∈[m]. Assumption 4 (Bounded rewards and noise) There exist constants U,R>0U,R>0 such that |μi(z)|≤U| _i(z)|≤ U over the relevant domain and |yt,i−μi(⟨Xt,Θi∗⟩)|≤R,∀t∈[T],i∈[m] |y_t,i- _i\! ( _t, _i^* ) |≤ R,∀ t∈[T],\ i∈[m]. Assumption 5 (Lexicographic trade-off) There exists w≥0w≥ 0 such that, for every i∈2,…,mi∈\2,…,m\ and any X∈X , μi(⟨X,Θi∗⟩)−μi(⟨X∗,Θi∗⟩) _i ( , _i^* )- _i ( _*, _i^* ) ≤w⋅maxj∈[i−1]μj(⟨X∗,Θj∗⟩)−μj(⟨X,Θj∗⟩). ≤ w· _j∈[i-1] \ _j ( _*, _j^* )- _j ( , _j^* ) \. Auxiliary Tools for Subspace Estimation. We introduce several auxiliary tools for estimating the low-rank row and column subspaces. These tools follow the Stein-type subspace estimation approach developed for generalized low-rank matrix bandits (Kang et al., 2022). Let p:ℝ→ℝp:R denote a univariate probability density function. Its corresponding score function is defined by Sp(x)=−∇xlogp(x)=−∇xp(x)p(x),x∈ℝ.S^p(x)=- _x p(x)=- _xp(x)p(x), x . For a random matrix A∈ℝd1×d2A ^d_1× d_2 with entrywise density =(pij):ℝd1×d2→ℝd1×d2p=(p_ij):R^d_1× d_2 ^d_1× d_2, its score function is S(A)=(Spij(Aij))i,j∈ℝd1×d2.S^p(A)= (S^p_ij(A_ij) )_i,j ^d_1× d_2. When the underlying exploration distribution is clear from the context, we simply write S(A)S(A). Assumption 6 (Exploration distribution) There exists a sampling distribution D over X such that, for X∼X with associated entrywise density p, E[(S(X))ij2]≤M,∀(i,j)∈[d1]×[d2].E\! [ (S^p(X) )_ij^2 ]≤ M,∀(i,j)∈[d_1]×[d_2]. Moreover, either the rows or the columns of XX are pairwise independent. We also introduce the Hermitian dilation operator. For any matrix A∈ℝd1×d2A ^d_1× d_2, define ℋ(A)=(0A⊤0)∈ℝ(d1+d2)×(d1+d2).H(A)= pmatrix0&A\\ A &0 pmatrix ^(d_1+d_2)×(d_1+d_2). Moreover, for any real-valued function g:ℝ→ℝg:R and any symmetric matrix A=UDU⊤A=UDU , define g(A)=Udiag(g(D11),…,g(Ddd))U⊤.g(A)=Udiag (g(D_11),…,g(D_d) )U . To obtain a robust matrix estimator under the finite-moment condition in Assumption 6, we use the truncation function ψ(x)=log(1+x+x2/2),x≥0,−log(1−x+x2/2),x<0.ψ(x)= cases (1+x+x^2/2),&x≥ 0,\\ - (1-x+x^2/2),&x<0. cases Given ν>0ν>0, define the matrix-valued truncation operator ψ~ν(A)=1ν[ψ(νℋ(A))]1:d1,(d1+1):(d1+d2). ψ_ν(A)= 1ν [ψ ( (A) ) ]_1:d_1,\,(d_1+1):(d_1+d_2). (1) Specifically, ψ~ν(⋅) ψ_ν(·) first applies ψ(⋅)ψ(·) to the Hermitian dilation of a rectangular matrix and then extracts its upper-right block. This operator serves as a key component in constructing robust estimators of the objective-specific low-rank subspaces. 4 Algorithms This section presents our algorithms. We first introduce a robust objective-specific subspace estimation procedure to construct transformed feature representations. Based on this, we develop two algorithms. The first, Scalar-LowGLM, is a straightforward scalarized extension of the single-objective algorithm (Kang et al., 2022), retaining its batch estimator updates. The second, Lexi-LowGLM, directly exploits lexicographic preferences through sequential candidate filtering and online estimator updates, leading to improved regret guarantees and lower computational complexity. 4.1 Objective-Specific Subspace Estimation We begin by estimating the objective-specific low-rank row and column subspaces. To this end, during the first T1T_1 rounds, the learner samples arms independently from the exploration distribution D over X and observes the corresponding reward vector. These exploration samples are then used to construct a separate low-rank estimator for each objective. For each objective i∈[m]i∈[m], define the empirical loss LT1,i(Θ)=⟨Θ,Θ⟩−2T1∑t=1T1⟨ψ~ν(yt,i⋅S(Xt)),Θ⟩,L_T_1,i( )= , - 2T_1 _t=1^T_1 ψ_ν\! (y_t,i· S(X_t) ), , (2) where S(Xt)S(X_t) is the score function associated with the exploration distribution D, and ψ~ν(⋅) ψ_ν(·) is the matrix-valued truncation operator defined in Eq. (1). The objective-specific estimator is then obtained by solving the nuclear-norm regularized optimization problem Θ^i=argminΘ∈ℝd1×d2LT1,i(Θ)+λT1‖Θ‖nuc, _i= _ ^d_1× d_2 \L_T_1,i( )+ _T_1\| \|_nuc \, (3) where the nuclear norm promotes low-rank structure. We set ν=2log(2m(d1+d2)/δ)(4R2+U2)MT1(d1+d2)ν= 2 (2m(d_1+d_2)/δ)(4R^2+U^2)MT_1(d_1+d_2) and λT1=42(4R2+U2)M(d1+d2)log(2m(d1+d2)/δ)T1. _T_1=4 2(4R^2+U^2)M(d_1+d_2) (2m(d_1+d_2)/δ)T_1. After computing Θ^i _i, we take its singular value decomposition Θ^i=[U^i,U^i,⟂]D^i[V^i,V^i,⟂]⊤, _i=[ U_i, U_i, ] D_i[ V_i, V_i, ] , where U^i U_i and V^i V_i contain the leading r left and right singular vectors, respectively. These matrices provide estimates of the objective-specific row and column subspaces for constructing the transformed feature representations. Algorithm 1 Objective-Specific Subspace Estimation 0: ,T1,r,,δX,T_1,r,D,δ 1: for t=1,2,…,T1t=1,2,…,T_1 do 2: Sample Xt∼X_t and observe yt=(yt,1,…,yt,m)y_t=(y_t,1,…,y_t,m) 3: end for 4: for i=1,2,…,mi=1,2,…,m do 5: Define the loss function LT1,i(Θ)L_T_1,i( ) as in Eq. (2) 6: Compute Θ^i _i by solving Eq. (3) 7: Compute the SVD Θ^i=[U^i,U^i,⟂]D^i[V^i,V^i,⟂]⊤ _i=[ U_i, U_i, ]\, D_i\,[ V_i, V_i, ] 8: Define the transformed feature map fi(⋅)f_i(·) as in Eq. (4) 9: end for 10: return fi(⋅)i=1m\f_i(·)\_i=1^m Transformed Feature Representation. For each objective i∈[m]i∈[m], define the rotation operator ℛi(A):=[U^i,U^i,⟂]⊤A[V^i,V^i,⟂].R_i(A):=[ U_i, U_i, ] A[ V_i, V_i, ]. The rotated matrix is then partitioned according to the estimated rank-r row and column subspaces. We define the projection operator Πr(A):=[vec(A1:r, 1:r)vec(Ar+1:d1, 1:r)vec(A1:r,r+1:d2)vec(Ar+1:d1,r+1:d2)], _r(A):= bmatrixvec(A_1:r,\,1:r)\\ vec(A_r+1:d_1,\,1:r)\\ vec(A_1:r,\,r+1:d_2)\\ vec(A_r+1:d_1,\,r+1:d_2) bmatrix, which vectorizes the four resulting blocks. The transformed feature map for objective i is therefore given by fi(X):=Πr(ℛi(X)).f_i(X):= _r\! (R_i(X) ). (4) The first k=(d1+d2)r−r2k=(d_1+d_2)r-r^2 coordinates correspond to the estimated low-rank subspace, while the remaining coordinates capture the complementary directions. This representation allows the next stage to exploit the estimated low-rank structure through anisotropic regularization. 4.2 Scalarized Batch Method: Scalar-LowGLM Algorithm 2 presents a natural baseline that extends the single-objective low-rank matrix bandit algorithm (Kang et al., 2022) to the multi-objective setting. After estimating the objective-specific low-rank subspaces using Algorithm 1, Algorithm 2 performs bandit learning in the transformed feature spaces fi(X):X∈i=1m\f_i(X):X \_i=1^m. Let p=d1d2,k=(d1+d2)r−r2.p=d_1d_2, k=(d_1+d_2)r-r^2. The first k coordinates of fi(X)f_i(X) correspond to the estimated low-rank subspace, while the remaining p−kp-k coordinates represent its orthogonal complement. To exploit this structure, we use the anisotropic regularization matrix Λ=diag(λ0Ik,λ⟂Ip−k), =diag( _0I_k, _ I_p-k), where λ⟂≫λ0 _ _0. Thus, directions outside the estimated low-rank subspace are regularized more heavily, encouraging learning to concentrate on the informative low-rank subspace. For each objective i∈[m]i∈[m], we maintain a design matrix Vt,iV_t,i and a parameter estimator θ^t,i θ_t,i in the transformed feature space. They are initialized as V1,i=ΛV_1,i= and θ^1,i=0 θ_1,i=0, with confidence radius β1=Lμ⋅(λ0S+λ⟂S⟂) _1=L_μ·( _0S+ _ S_ ). At round t, the predicted reward and confidence width of arm X∈X under objective i∈[m]i∈[m] are given by y^t,i(X)=μi(fi(X)⊤θ^t,i),ct,i(X)=βt‖fi(X)‖Vt,i−1. y_t,i(X)= _i\! (f_i(X) θ_t,i ),\ c_t,i(X)= _t\|f_i(X)\|_V_t,i^-1. (5) Here, ct,i(X)c_t,i(X) quantifies the uncertainty associated with the estimated reward. Scalar-LowGLM then forms a scalarized upper confidence bound by aggregating the objective-wise optimistic estimates as follows: UCBt(X,w)=∑i=1m(1+w)m−i(y^t,i(X)+ct,i(X)).UCB_t(X,w)= _i=1^m(1+w)^m-i ( y_t,i(X)+c_t,i(X) ). (6) The scalarization encodes the priority among objectives by assigning larger weights to higher-priority objectives. The algorithm then plays the arm with the largest scalarized UCB value, i.e., Xt=argmaxX∈UCBt(X,w)X_t= *argmax_X UCB_t(X,w). Algorithm 2 Scalar-LowGLM 0: T,T1,δ,r,w,λ0,λ⟂,S⟂T,T_1,δ,r,w, _0, _ ,S_ 1: Run Algorithm 1 for T1T_1 rounds and obtain fi(⋅)i=1m\f_i(·)\_i=1^m 2: Set p=d1d2p=d_1d_2 and k=(d1+d2)r−r2k=(d_1+d_2)r-r^2 3: Set Λ=diag(λ0Ik,λ⟂Ip−k) =diag( _0I_k, _ I_p-k) 4: Initialize V1,i=ΛV_1,i= and θ^1,i=0 θ_1,i=0 for all i∈[m]i∈[m], and set the confidence radius β1=Lμ⋅(λ0S+λ⟂S⟂) _1=L_μ·( _0S+ _ S_ ) 5: for t=1,…,T−T1t=1,…,T-T_1 do 6: Compute y^t,i(X) y_t,i(X) and ct,i(X)c_t,i(X) for all X∈X by Eq. (5) 7: Compute UCBt(X,w)UCB_t(X,w) for all X∈X by Eq. (6) 8: Play Xt=argmaxX∈UCBt(X,w)X_t= *argmax_X UCB_t(X,w) 9: Observe reward vector yt=(yt,1,yt,2,…,yt,m)y_t=(y_t,1,y_t,2,…,y_t,m) 10: for i=1,…,mi=1,…,m do 11: Compute the estimator θ^t+1,i θ_t+1,i by Eq. (7) 12: Update Vt+1,i=Vt,i+cμ2fi(Xt)fi(Xt)⊤V_t+1,i=V_t,i+ c_μ2f_i(X_t)f_i(X_t) 13: end for 14: Compute βt+1 _t+1 by Eq. (8) 15: end for After observing the reward vector yt=(yt,1,…,yt,m)y_t=(y_t,1,…,y_t,m), the estimator for each objective i∈[m]i∈[m] is updated by solving the following regularized empirical risk minimization problem over all observations collected up to round t: θ^t+1,i=argmin‖θ‖2≤S∑τ=1tℓτ,i(θ)+12‖θ‖Λ2, θ_t+1,i= *argmin_\|θ\|_2≤ S _τ=1^t _τ,i(θ)+ 12\|θ\|_ ^2, (7) where ℓτ,i(θ)=bi(fi(Xτ)⊤θ)−yτ,i⋅fi(Xτ)⊤θ _τ,i(θ)=b_i\! (f_i(X_τ) θ )-y_τ,i· f_i(X_τ) θ and bi(⋅)b_i(·) is the cumulant function associated with the link function μi(⋅) _i(·), i.e., bi′(x)=μi(x)b_i (x)= _i(x). Since the estimator is recomputed from scratch at every round, the cumulative update cost grows quadratically with the time horizon, making this approach computationally inefficient for large-scale online learning. The corresponding confidence radius is given by βt+1=LμRLt,k+2log(m/δ)+β1, _t+1=L_μR L_t,k+2 (m/δ )+ _1, (8) where Lt,k=klog(1+tk)+cμt2λ⟂L_t,k=k (1+ tk )+ c_μt2 _ . We now present the regret guarantee of Scalar-LowGLM. The following theorem shows that, with an appropriate exploration length and anisotropic regularization, the algorithm achieves sublinear regret for every objective. Theorem 1 Suppose that Assumptions 1–6 hold. For each objective i∈[m]i∈[m], let Drr,iD_r,i denote the r-th largest singular value of the objective-specific parameter matrix Θi∗ _i^*, and define Drr=mini∈[m]Drr,iD_r= _i∈[m]D_r,i. Run Algorithm 2 with T1≍M(d1+d2)rTlog((d1+d2)m/δ)Drr,T_1 M(d_1+d_2)rT ((d_1+d_2)m/δ)D_r, and set λ0=max1,cμ/2,λ⟂=cμTklog(1+cμT/(kλ0)), _0= \1,c_μ/2\, _ = c_μTk \! (1+c_μT/(k _0) ), where k=(d1+d2)r−r2k=(d_1+d_2)r-r^2. Furthermore, set S⟂=M(d1+d2)rlog(m(d1+d2)/δ)Drr2T.S_ = M(d_1+d_2)r (m(d_1+d_2)/δ)D_r^2T. Then, with probability at least 1−2δ1-2δ, for every objective i∈[m]i∈[m], the cumulative regret satisfies Ri(T)=O~(Wsca⋅(d1+d2)rT),R_i(T)= O\! (W sca·(d_1+d_2)r T ), where Wsca=∑i=1m(1+w)i−1W sca= _i=1^m(1+w)^i-1. Remark 1 When m=1m=1, Theorem 1 indicates Scalar-LowGLM achieves a regret bound of O~((d1+d2)rT) O((d_1+d_2)r T), matching the rate in single-objective settings (Kang et al., 2022). Compared with vectorizing matrix arms and applying lexicographic linear bandit methods (Xue et al., 2025b), our bound replaces the ambient dimension d1d2d_1d_2 with the intrinsic low-rank dimension (d1+d2)r(d_1+d_2)r. The factor WscaW sca captures the cost of fixed scalarization: when w=0w=0, we have Wsca=mW sca=m and hence only linear growth in the number of objectives; when w>0w>0, Wsca=(1+w)m−1wW sca= (1+w)^m-1w, which grows geometrically with the number of objectives. 4.3 Lexicographic Online Method: Lexi-LowGLM Algorithm 3 Lexi-LowGLM 0: T,T1,δ,r,w,λ0,λ⟂,S⟂T,T_1,δ,r,w, _0, _ ,S_ 1: Run Algorithm 1 for T1T_1 rounds and obtain fi(⋅)i=1m\f_i(·)\_i=1^m 2: Set p=d1d2p=d_1d_2 and k=(d1+d2)r−r2k=(d_1+d_2)r-r^2 3: Set Λ=diag(λ0Ik,λ⟂Ip−k) =diag( _0I_k, _ I_p-k) 4: Initialize V1,i=ΛV_1,i= and θ^1,i=0 θ_1,i=0 for all i∈[m]i∈[m], and set the confidence radius β1=Lμ⋅(λ0S+λ⟂S⟂) _1=L_μ·( _0S+ _ S_ ) 5: Initialize the candidate arm set 1=X_1=X 6: for t=1,…,T−T1t=1,…,T-T_1 do 7: Compute y^t,i(X) y_t,i(X) and ct,i(X)c_t,i(X) for all X∈tX _t by Eq. (5) 8: Select (Xt,it)=argmaxX∈t,i∈[m]ct,i(X)(X_t,i_t)= _X _t,i∈[m]c_t,i(X) 9: Set t0=tX_t^0=X_t 10: for i=1,2,…,mi=1,2,…,m do 11: Xt,i=argmaxX∈ti−1y^t,i(X)X_t,i= _X _t^i-1 y_t,i(X) 12: ti=X∈ti−1:y^t,i(Xt,i)−y^t,i(X)≤Wi⋅ct,it(Xt)X_t^i=\X _t^i-1: y_t,i(X_t,i)- y_t,i(X)≤ W_i· c_t,i_t(X_t)\ with Wi=2+4w+⋯+4wi−1W_i=2+4w+·s+4w^i-1 13: end for 14: Play XtX_t and observe yt=(yt,1,yt,2,…,yt,m)y_t=(y_t,1,y_t,2,…,y_t,m) 15: for i=1,2,…,mi=1,2,…,m do 16: Compute the gradient ∇ℓt,i(θ^t,i)∇ _t,i( θ_t,i) by Eq. (9) 17: Update the estimator θ^t+1,i θ_t+1,i by Eq. (10) 18: end for 19: Compute the confidence radius βt+1 _t+1 by Eq. (11) 20: Set t+1=tmX_t+1=X_t^m 21: end for Algorithm 3 is our proposed online method. It shares the same subspace-estimation and low-rank feature initialization steps as Scalar-LowGLM: first run Algorithm 1 to construct the transformed feature maps fi(⋅)i=1m\f_i(·)\_i=1^m, and then initialize the anisotropic regularization matrix Λ , the covariance matrices V1,ii=1m\V_1,i\_i=1^m, the estimators θ^1,ii=1m\ θ_1,i\_i=1^m, and the confidence radius. Beyond this shared initialization, Lexi-LowGLM maintains an active candidate set tX_t, initialized as 1=X_1=X, and progressively refines it throughout the learning process. Unlike Scalar-LowGLM, which scalarizes the vector-valued reward into a single score, Lexi-LowGLM explicitly preserves the lexicographic preference by sequentially eliminating statistically suboptimal arms objective by objective. At each round, Lexi-LowGLM computes the predicted reward and confidence width for every candidate arm under each objective using Eq. (5), and selects the most uncertain arm-objective pair in the current candidate set: (Xt,it)∈argmaxX∈t,i∈[m]ct,i(X).(X_t,i_t)∈ *argmax_X _t,\,i∈[m]c_t,i(X). The confidence width ct,it(Xt)c_t,i_t(X_t) serves as a common tolerance threshold for the subsequent lexicographic filtering procedure. To preserve the lexicographic preferences, the algorithm progressively filters the candidate arm set according to the objective priority. Starting from t0=tX_t^0=X_t, for each objective i=1,2,…,mi=1,2,…,m, Lexi-LowGLM first selects the empirically best arm in the current candidate set: Xt,i=argmaxX∈ti−1y^t,i(X).X_t,i= *argmax_X _t^i-1 y_t,i(X). It then removes arms whose estimated rewards are significantly inferior to that of Xt,iX_t,i under the i-th objective. Specifically, the candidate set is updated as ti=X∈ti−1:y^t,i(Xt,i)−y^t,i(X)≤Wi⋅ct,it(Xt),X_t^i= \X _t^i-1: y_t,i(X_t,i)- y_t,i(X)≤ W_i· c_t,i_t(X_t) \, where Wi=2+4w+⋯+4wi−1W_i=2+4w+·s+4w^i-1. The tolerance factor WiW_i accounts for the cumulative trade-off induced by the lexicographic structure. Since the candidate set is refined sequentially from objective 11 to objective m, higher-priority objectives are enforced before lower-priority ones. Consequently, the final candidate set tmX_t^m contains the arms that remain promising across all objectives. After all objectives have been processed, Lexi-LowGLM plays arm XtX_t and observes the reward vector yt=(yt,1,yt,2,…,yt,m)y_t=(y_t,1,y_t,2,…,y_t,m). Unlike Scalar-LowGLM, which recomputes the estimator from all historical observations, Lexi-LowGLM updates each objective-specific estimator via an online Newton-type proximal step. For each objective i∈[m]i∈[m], it first computes the gradient of the instantaneous loss at the current estimator, ∇ℓt,i(θ^t,i)=(μi(fi(Xt)⊤θ^t,i)−yt,i)⋅fi(Xt),∇ _t,i( θ_t,i)=( _i(f_i(X_t) θ_t,i)-y_t,i)· f_i(X_t), (9) and updates the covariance matrix by Vt+1,i=Vt,i+cμ2fi(Xt)fi(Xt)⊤.V_t+1,i=V_t,i+ c_μ2f_i(X_t)f_i(X_t) . The new estimator is then obtained by solving the following constrained proximal problem: θ^t+1,i=argmin∥θ∥2≤S∥θ−θ^t,i∥Vt+1,i22+⟨θ,∇ℓt,i(θ^t,i)⟩. θ_t+1,i= *argmin_ θ _2≤ S θ- θ_t,i ^2_V_t+1,i2+ θ,∇ _t,i( θ_t,i) . (10) Since each update depends only on the current observation, it avoids repeated batch optimization and substantially improves computational efficiency. After updating all objective-specific estimators, the confidence radius is set to βt+1=Lμ(4(U+R)Lt,k+Lt,δcμ+cμ2)+β1, _t+1=L_μ (4(U+R) L_t,k+L_t,δc_μ+ c_μ2 )+ _1, (11) where Lt,δ=log(m1+4S2tδ)L_t,δ= ( m 1+4S^2tδ ). Finally, the candidate set for the next round is updated as t+1=tmX_t+1=X_t^m. In this way, Algorithm 3 gradually eliminates statistically suboptimal arms while updating the objective-specific estimators in the estimated reduced feature spaces. We next establish the regret guarantee of Lexi-LowGLM. The following theorem shows that, despite the sequential lexicographic filtering and online estimator updates, the algorithm achieves sublinear regret for every objective. Theorem 2 Suppose that Assumptions 1–6 hold, and run Algorithm 3 with the same parameters as specified in Theorem 1. Then, with probability at least 1−2δ1-2δ, for every objective i∈[m]i∈[m], the cumulative regret satisfies Ri(T)=O~(Wilexm⋅(d1+d2)rT), R_i(T)= O (W_i lex m·(d_1+d_2)r T ), where Wilex=1+w+⋯+wi−1W_i lex=1+w+·s+w^i-1. Remark 2 Theorem 2 shows that Lexi-LowGLM matches the horizon and effective-dimension dependence achieved in the single-objective setting (Kang et al., 2022), while jointly learning all objectives. Compared with the scalarized baseline in Theorem 1, the improvement lies in the objective-dependent factor. In particular, the regret for the highest-priority objective is independent of the trade-off parameter w. When w=0w=0, we have Wilex=1W_i lex=1 for all i∈[m]i∈[m], whereas Wsca=mW sca=m. Thus, lexicographic filtering improves the dependence on the number of objectives from m to m m. When w>0w>0, WilexW_i lex remains more refined than WscaW sca since WilexW_i lex grows with the prefix length i rather than the total number of objectives m, and uses powers of w instead of powers of 1+w1+w. This highlights the benefit of explicitly exploiting the sequential structure of lexicographic preferences. In addition, Lexi-LowGLM uses online estimator updates instead of recomputing a batch estimator from all historical samples, which improves computational efficiency and makes it more suitable for large-scale online learning. 5 Experiments We conduct numerical experiments to evaluate the statistical and computational performance of the proposed methods. In particular, we compare their objective-wise regret and running time on synthetic lexicographic generalized low-rank matrix bandit instances with different matrix ranks. Figure 1: Regret comparison of our algorithms versus G-ESTT and MTLO for rank 11. Baselines. We compare Scalar-LowGLM and Lexi-LowGLM with two representative baselines: G-ESTT (Kang et al., 2022) and MTLO (Xue et al., 2025b). G-ESTT is designed for single-objective generalized low-rank matrix bandits and is therefore applied to the highest-priority objective. It exploits the low-rank matrix structure but does not account for multiple objectives. MTLO is a lexicographic linear bandit algorithm applied to the vectorized matrix features vec(X)∈ℝd1d2vec(X) ^d_1d_2. It captures lexicographic preferences but operates in the ambient dimension d1d2d_1d_2 without exploiting the underlying low-rank structure. We set the horizon to T=10,000T=10,000, the exploration length to T1=3,000T_1=3,000, and consider ranks r∈1,2r∈\1,2\. Each experiment is repeated over 1010 independent trials, and the regret curves report the average performance across trials. Full details of the synthetic instances and hyperparameter settings are provided in the appendix. The results and discussion for the rank-two setting are also deferred to the appendix. Figure 1 compares the objective-wise cumulative regret of all algorithms. G-ESTT effectively controls the regret on Objective 1, but its regret grows nearly linearly on Objectives 2 and 3. This behavior is expected because G-ESTT is designed for single-objective learning, without explicitly accounting for the lower-priority objectives. MTLO achieves the smallest regret on Objective 1 during the early rounds because it operates directly on the fixed finite arm set and avoids the T1T_1 rounds of continuous subspace exploration required by the low-rank methods. Nevertheless, its regret continues to increase over time because of the model mismatch: MTLO is developed for linear bandits, whereas our instances follow a generalized linear reward model. Both proposed methods achieve substantially smaller regret on Objectives 2 and 3 than G-ESTT and MTLO. The relatively larger Objective 1 regret of Lexi-LowGLM is partly attributable to the initial subspace-exploration phase. Scalar-LowGLM stabilizes shortly after this exploration phase and attains the smallest empirical regret on the two lower-priority objectives. Although the theoretical bound of Lexi-LowGLM has a more favorable objective-dependent factor WilexW_i^lex, this does not imply that its finite-horizon regret must be uniformly smaller than that of Scalar-LowGLM. The bounds suppress constants and additional terms arising from confidence radii, regularization, and subspace-estimation error. Hence, the theoretical comparison concerns worst-case asymptotic guarantees rather than a strict empirical ordering at T=10,000T=10,000. The observed sublinear growth of the regret curves is nevertheless consistent with the theoretical guarantees. Table 1: Mean total wall-clock time in seconds. Algorithm Runtime Algorithm Runtime G-ESTT 87.899 Scalar-LowGLM 227.555 MTLO 4.349 Lexi-LowGLM 4.070 Table 1 reports the mean wall-clock time required to complete a rank-one trial over 10,00010,000 rounds. Lexi-LowGLM finishes in only 4.0704.070 seconds, making it approximately 21×21× faster than G-ESTT and 55×55× faster than Scalar-LowGLM. This gap reflects their different estimator-update mechanisms: G-ESTT repeatedly refits a batch estimator for the highest-priority objective, while Scalar-LowGLM performs batch refitting for all three objectives. By contrast, Lexi-LowGLM updates each estimator online using only the current observation, thereby avoiding repeated processing of the full history. MTLO and Lexi-LowGLM have similar running times because both rely on online updates. However, MTLO is designed for linear rewards and does not accommodate the generalized linear setting, resulting in linear regret on Objectives 2 and 3. Overall, Lexi-LowGLM achieves the lowest mean runtime while substantially outperforming MTLO on the lower-priority objectives. 6 Conclusion and Future Work We studied lexicographic generalized low-rank matrix bandits, extending generalized low-rank matrix bandits from scalar rewards to multiple prioritized objectives. We proposed two algorithms: Scalar-LowGLM and Lexi-LowGLM. Scalar-LowGLM serves as a natural scalarized batch baseline, while Lexi-LowGLM combines objective-specific subspace estimation, lexicographic filtering, and online Newton-type updates. Theoretically, we established objective-wise regret bounds of order O~(Wilexm(d1+d2)rT) O(W_i lex m(d_1+d_2)r T), showing that the regret depends on the intrinsic low-rank dimension r. Moreover, compared with repeated batch re-estimation (Kang et al., 2022), Lexi-LowGLM reduces the cumulative estimator-update complexity from O(T2)O(T^2) to O(T)O(T), substantially improving computational efficiency. Future work will focus on extending the framework to rank-adaptive learning, and more challenging feedback models such as non-stationary, delayed, or heavy-tailed rewards. Another interesting direction is to derive matching lower bounds for lexicographic low-rank matrix bandits. References Y. Abbasi-yadkori, D. Pál, and C. Szepesvári (2011) Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24, p. 2312–2320. Cited by: Appendix B, Appendix B, Appendix C, §2. Y. Abbasi-Yadkori, D. Pal, and C. Szepesvari (2012) Online-to-confidence-set conversions and application to sparse stochastic bandits. In Proceedings of the 15th International Conference on Artificial Intelligence and Statistics, p. 1–9. Cited by: Appendix C. V. S. P. Alperen Tercan (2024) Thresholded lexicographic ordered multiobjective reinforcement learning. In Proceedings of the 27th European Conference on Artificial Intelligence, p. 3006–3014. Cited by: §2. P. Auer, C. Chiang, R. Ortner, and M. Drugan (2016) Pareto front identification from stochastic bandit feedback. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, p. 939–947. Cited by: §2. P. Auer (2002) Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research 3 (11), p. 397–422. Cited by: §1. R. Busa-Fekete, B. Szörényi, P. Weng, and S. Mannor (2017) Multi-objective bandits: optimizing the generalized Gini index. In Proceedings of the 34th International Conference on Machine Learning, p. 625–634. Cited by: §2. X. Cai, P. Zhang, L. Zhao, B. Jiang, M. Sugiyama, and A. J. Llorens (2023) Distributional pareto-optimal multi-objective reinforcement learning. In Advances in Neural Information Processing Systems 36, Cited by: §2. W. Chu, L. Li, L. Reyzin, and R. Schapire (2011) Contextual bandits with linear payoff functions. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, p. 208–214. Cited by: §2. É. Crepon, A. Garivier, and W. M Koolen (2024) Sequential learning of the Pareto front for multi-objective bandits. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, p. 3583–3591. Cited by: §2. V. Dani, T. P. Hayes, and S. M. Kakade (2008) Stochastic linear optimization under bandit feedback. In Proceedings of the 21st Annual Conference on Learning, p. 355–366. Cited by: §1. M. M. Drugan and A. Nowe (2013) Designing multi-objective multi-armed bandits algorithms: a study. In The 2013 International Joint Conference on Neural Networks, p. 1–8. Cited by: §2. M. Ehrgott (2005) Multicriteria optimization. Springer-Verlag, Berlin, Heidelberg. Cited by: §1. S. Filippi, O. Cappe, A. Garivier, and C. Szepesvári (2010) Parametric bandits: the generalized linear case. In Advances in Neural Information Processing Systems 23, p. 586–594. Cited by: §1. E. Hazan, A. Agarwal, and S. Kale (2007) Logarithmic regret algorithms for online convex optimization. Machine Learning 69 (2-3), p. 169–192. Cited by: Appendix C. A. Hüyük and C. Tekin (2021) Multi-objective multi-armed bandit with lexicographically ordered and satisficing objectives. Machine Learning 110 (6), p. 1233–1266. Cited by: §1, §2. K. Jang, K. Jun, S. Yun, and W. Kang (2021) Improved regret bounds of bilinear bandits using action space analysis. In Proceedings of the 38th International Conference on Machine Learning, p. 4744–4754. Cited by: §1, §2. K. Jang, C. Zhang, and K. Jun (2024) Efficient low-rank matrix estimation, experimental design, and arm-set-dependent low-rank bandits. In Proceedings of the 41st International Conference on Machine Learning, p. 21329–21372. Cited by: §2. K. Jee, D. L. McShan, and B. A. Fraass (2007) Lexicographic ordering: intuitive multicriteria optimization for imrt. Physics in Medicine & Biology 52, p. 1845–1861. Cited by: §1. K. Jun, R. Willett, S. Wright, and R. Nowak (2019) Bilinear bandits with low-rank structure. In Proceedings of the 36th International Conference on Machine Learning, p. 3163–3172. Cited by: §1, §1, §2. Y. Kang, C. Hsieh, and T. C. M. Lee (2022) Efficient frameworks for generalized low-rank matrix bandit problems. In Advances in Neural Information Processing Systems 35, p. 19971–19983. Cited by: Appendix B, Appendix B, Appendix B, Appendix C, Appendix C, 3rd item, §1, §1, §1, §2, §3, §4.2, §4, §5, §6, Remark 1, Remark 2. Y. Kang, C. Hsieh, and T. C. M. Lee (2024) Low-rank matrix bandits with heavy-tailed rewards. In Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, p. 1863–1889. Cited by: §1, §2, §3. A. A. Khansa, R. Visoz, Y. Hayel, and S. Lasaulce (2021) Resource allocation for multi-source multi-relay wireless networks. In Ubiquitous Networking, p. 62–75. Cited by: §1. T. L. Lai and H. Robbins (1985) Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics 6 (1), p. 4–22. Cited by: §1. S. J. Lee, W. W. Sun, and Y. Liu (2026) Low-rank contextual reinforcement learning from heterogeneous human feedback. External Links: 2412.19436, Link Cited by: §2. L. Li, W. Chu, J. Langford, and R. E. Schapire (2010) A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, p. 661–670. Cited by: §1. S. Lu, G. Wang, Y. Hu, and L. Zhang (2019) Optimal algorithms for lipschitz bandits with heavy-tailed rewards. In Proceedings of the 36th International Conference on Machine Learning, p. 4154–4163. Cited by: §2. Y. Lu, A. Meisami, and A. Tewari (2021) Low-rank generalized linear bandit problems. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, p. 460–468. Cited by: §1, §2. S. Mukherjee, Q. Xie, J. Hanna, and R. Nowak (2023) Multi-task representation learning for pure exploration in bilinear bandits. In Advances in Neural Information Processing Systems 36, p. 47816–47827. Cited by: §2. S. Park, H. Ann, and M. Oh (2025) Thompson sampling for multi-objective linear contextual bandit. In Advances in Neural Information Processing Systems 38, p. 84523–84555. Cited by: §2. S. Qiu, D. Zhang, R. Yang, B. Lyu, and T. Zhang (2024) Traversing pareto optimal policies: provably efficient multi-objective reinforcement learning. arXiv preprint arXiv:2407.17466. Cited by: §2. H. Robbins (1952) Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society 58 (5), p. 527–535. Cited by: §1. E. Schwartz, E. Bradlow, and P. Fader (2017) Customer acquisition via display advertising using multi-armed bandit experiments. In Marketing Science, p. 500–522. Cited by: §1. J. Skalse, L. Hammond, C. Griffin, and A. Abate (2022) Lexicographic multi-objective reinforcement learning. In Proceedings of the 31st International Joint Conference on Artificial Intelligence, p. 3430–3436. Cited by: §2. C. Tekin and E. Turgay (2018) Multi-objective contextual multi-armed bandit with a dominant objective. IEEE Transactions on Signal Processing 66 (14), p. 3799–3813. Cited by: §1, §2. E. Turgay, D. Oner, and C. Tekin (2018) Multi-objective contextual bandit problem with similarity information. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, p. 1673–1681. Cited by: §2. Y. Wang, J. Li, Y. Kang, S. Gao, and Z. Xiao (2025) Generalized low-rank matrix contextual bandits with graph information. External Links: 2507.17528, Link Cited by: §1, §2, §3. E. Weber, A. E. Rizzoli, R. Soncini-Sessa, and A. Castelletti (2002) Lexicographic optimisation for water resources planning: the case of lake verbano, italy. In Integrated Assessment and Decision Support - Proceedings of the 1st Biennial Meeting of the International Environmental Modelling and Software Society, p. 235–240. Cited by: §1. M. Xu and D. Klabjan (2023) Pareto regret analyses in multi-objective multi-armed bandit. In Proceedings of the 40th International Conference on International Conference on Machine Learning, p. 38499–38517. Cited by: §2. B. Xue, D. Bu, J. Cheng, Y. Wan, and Q. Zhang (2025a) Multi-objective linear reinforcement learning with lexicographic rewards. In Proceedings of the 42nd International Conference on Machine Learning, Cited by: §2. B. Xue, X. Lin, X. Zhang, and Q. Zhang (2025b) Multiple trade-offs: an improved approach for lexicographic linear bandits. In Proceedings of the 39th AAAI Conference on Artificial Intelligence, p. 21850–21858. Cited by: §1, §2, §3, §5, Remark 1. Q. (. Zhang (2024) Optimal scalarizations for sublinear hypervolume regret. In Advances in Neural Information Processing Systems 37, p. 39963–39999. Cited by: §2. Appendix A Experimental Setup and Rank-Two Results A.1 Detailed Experimental Setup We set d1=d2=10d_1=d_2=10, consider m=3m=3 objectives, and examine matrix ranks r∈1,2r∈\1,2\. Each problem instance contains K=10K=10 fixed matrix arms. For each k∈[K]k∈[K], define the objective-specific latent scores g1(k) g_1(k) =1−min|k−1|,|k−4|,|k−8|, =1- \|k-1|,|k-4|,|k-8|\, g2(k) g_2(k) =1−min|k−3|,|k−7|, =1- \|k-3|,|k-7|\, g3(k) g_3(k) =1−|k−8|. =1-|k-8|. Thus, arms 11, 44, and 88 maximize the first objective. Among these arms, 44 and 88 remain optimal under the second objective, while the third objective uniquely identifies arm 88. Hence, arm 88 is the unique lexicographically optimal arm. Let ejj=110\e_j\_j=1^10 denote the canonical basis of ℝ10R^10. For each objective i∈[m]i∈[m], define the unknown parameter matrix as Θi⋆=1r∑ℓ=1rei+3(ℓ−1)eℓ⊤. _i = 1 r _ =1^re_i+3( -1)e_ . By construction, rank(Θi⋆)=r and ‖Θi⋆‖F=1.rank( _i )=r and \| _i \|_F=1. The k-th fixed arm is defined as Xk=1κrr∑ℓ=1r∑i=1mgi(k)ei+3(ℓ−1)eℓ⊤,X_k= 1 _rr _ =1^r _i=1^mg_i(k)e_i+3( -1)e_ , where κr=maxk∈[K]1r∑i=1mgi(k)2. _r= _k∈[K] 1r _i=1^mg_i(k)^2. This normalization ensures that ‖Xk‖F≤1\|X_k\|_F≤ 1 for every k∈[K]k∈[K]. Moreover, ⟨Xk,Θi⋆⟩=1κrrgi(k), _k, _i = 1 _r rg_i(k), so the resulting matrix construction preserves the rankings and ties specified by the latent scores. After selecting arm XtX_t, the learner observes yt,i=μ(⟨Xt,Θi⋆⟩)+ηt,i,μ(z)=11+exp(−z),y_t,i=μ\! ( _t, _i )+ _t,i, μ(z)= 11+ (-z), where the noise variables ηt,i∼Uniform[−0.1,0.1] _t,i [-0.1,0.1] are independent across rounds and objectives. During the first T1T_1 rounds, the low-rank methods sample arms from a continuous exploration distribution. Let a=1/d1d2.a=1/ d_1d_2. For each entry, we independently draw Zuv∼Beta(3,3)Z_uv (3,3) and set (Xt)uv=−aZuv.(X_t)_uv=-aZ_uv. This construction guarantees ‖Xt‖F≤1\|X_t\|_F≤ 1. The corresponding entrywise score function is S(Xt)uv=−2(a+2(Xt)uv)(Xt)uv(a+(Xt)uv).S(X_t)_uv=- 2 (a+2(X_t)_uv )(X_t)_uv (a+(X_t)_uv ). The exploration radius is chosen such that X8X_8 remains the comparator among the fixed arms. After the exploration phase, the low-rank methods select from the ten fixed arms, whereas MTLO operates on the fixed candidate set from the beginning. We set the horizon to T=10000T=10000 and the exploration length to T1=3000T_1=3000. The exploration radius, bounded-noise half-width, confidence-radius scaling factor, Beta shape parameter, and Stein nuclear-penalty scaling factor are set to 11, 0.10.1, 0.0040.004, 33, and 10−510^-5, respectively. Each experiment is repeated over 1010 independent trials, with matched random seeds across methods. The regret curves report the mean over all trials. Runtime is measured as the total wall-clock time required to complete one 1000010000-round trial, including exploration, arm selection, reward generation, and estimator updates. A.2 Additional Rank-Two Results Figure 2: Regret comparison of our algorithms versus G-ESTT and MTLO for rank 22. Figure 2 shows that the qualitative ordering observed for rank one largely persists when the rank increases to two. Scalar-LowGLM reaches nearly flat curves on all three objectives after the exploration phase and achieves the smallest lower-priority regret. Its first-objective curve almost overlaps with that of G-ESTT. Both methods share the same subspace-estimation stage and batch GLM update for Objective 1, and, on this instance, the additional scalarized objectives do not change the arm preferred by Scalar-LowGLM on the highest-priority objective. The batch refitting of all three objective models then enables Scalar-LowGLM to identify arm 88 and correct temporary estimation errors using the complete observation history. In contrast, G-ESTT accumulates almost linear regret on Objectives 2 and 3. Under Objective 1, arms 11, 44, and 88 are tied, so a method that observes only the primary objective has no information with which to resolve this set according to the lower-priority objectives. MTLO also maintains relatively small Objective-1 regret because it starts directly on the fixed arm set and prioritizes the first objective, thereby avoiding the initial continuous exploration cost. However, it must learn in the ambient d1d2d_1d_2-dimensional space under a linear reward model, while the data are generated by a generalized low-rank model. This model and dimension mismatch slows its sequential candidate refinement; consequently, its Objective-2 regret continues to grow and its Objective-3 regret is the largest among all methods. Lexi-LowGLM substantially reduces the lower-priority regret relative to G-ESTT and MTLO. Its Objective-2 curve approaches a plateau, indicating that objective-specific low-rank learning and lexicographic filtering successfully eliminate most arms that are inconsistent with the first two priority levels. Its Objective-3 curve also has a visibly smaller and decreasing slope, but it does not fully flatten within 1000010000 rounds. Rank two is statistically harder than rank one because the effective transformed dimension increases from (d1+d2)r−r2=19(d_1+d_2)r-r^2=19 to 3636. The resulting larger subspace and parameter uncertainty keeps multiple candidate arms active for longer. Hence Lexi-LowGLM continues to explore among arms that are nearly indistinguishable under the higher-priority objectives instead of selecting arm 88 exclusively. Appendix B Proof of Theorem 1 Proof roadmap. The proof has three components. First, we use the Stein-type estimator to control the objective-specific subspace estimation error and then translate this error into a bound on the coordinates outside the estimated low-rank subspace. Second, we establish a uniform confidence bound for the batch generalized linear estimators under anisotropic regularization. Third, we show that the scalarized regret dominates every objective-wise regret, apply optimism and the elliptical-potential argument, and finally substitute the prescribed choices of T1T_1, λ⟂ _ , and S⟂S_ . Step 1: Subspace estimation and tail-coordinate control. Lemma 1 Suppose that Assumptions 2–4 and 6 hold. Let X1,…,XT1X_1,…,X_T_1 be sampled independently from D over X. For each objective i∈[m]i∈[m], let Θ^i _i be the solution to the nuclear-norm regularized problem (3). Set ν=2log(2m(d1+d2)/δ)(4R2+U2)MT1(d1+d2)ν= 2 (2m(d_1+d_2)/δ)(4R^2+U^2)MT_1(d_1+d_2) and λT1=42(4R2+U2)M(d1+d2)log(2m(d1+d2)/δ)T1 _T_1=4 2(4R^2+U^2)M(d_1+d_2) (2m(d_1+d_2)/δ)T_1. Then, with probability at least 1−δ1-δ, the following bound holds for all i∈[m]i∈[m]: ‖Θ^i−μi∗Θi∗‖F2≤C1M(d1+d2)rlog(2m(d1+d2)/δ)T1\| _i-μ^*_i ^*_i\|^2_F≤ C_1M(d_1+d_2)r (2m(d_1+d_2)/δ)T_1 for C1=36(4R2+U2)C_1=36(4R^2+U^2) and μi∗=E[μi′(⟨X,Θi∗⟩)]≥cμ>0μ^*_i=E[μ _i( X, _i^* )]≥ c_μ>0. Proof. Under Assumptions 2–4 and 6, the observations associated with objective i constitute a low-rank generalized linear model satisfying the conditions of Kang et al. [2022, Theorem 4.1]. Applying this theorem to objective i with confidence level δ′=δ/mδ =δ/m gives Pr(ℰi)≥1−δ′,Pr(E_i)≥ 1-δ , where ℰi:=‖Θ^i−μi∗Θi∗‖F2≤C1M(d1+d2)rlog(2(d1+d2)/δ′)T1,E_i:= \ \| _i- _i^* _i^* \|_F^2≤ C_1M(d_1+d_2)r \! (2(d_1+d_2)/δ )T_1 \, with C1=36(4R2+U2)C_1=36(4R^2+U^2) and μi∗=EX∼[μi′(⟨X,Θi∗⟩)] _i^*=E_X [μ _i ( , _i^* ) ]. Since δ′=δ/mδ =δ/m, we have log(2(d1+d2)δ′)=log(2m(d1+d2)δ). ( 2(d_1+d_2)δ )= ( 2m(d_1+d_2)δ ). Consequently, the regularization parameters become v=2log(2m(d1+d2)/δ)(4R2+U2)MT1(d1+d2)v= 2 \! (2m(d_1+d_2)/δ )(4R^2+U^2)MT_1(d_1+d_2) and λT1=42(4R2+U2)M(d1+d2)log(2m(d1+d2)/δ)T1. _T_1=4 2(4R^2+U^2)M(d_1+d_2) \! (2m(d_1+d_2)/δ )T_1. Finally, by the union bound, Pr(⋂i=1mℰi)=1−Pr(⋃i=1mℰic)≥1−∑i=1mPr(ℰic)≥1−∑i=1mδm=1−δ. ( _i=1^mE_i )=1-Pr ( _i=1^mE_i^c )≥ 1- _i=1^mPr(E_i^c)≥ 1- _i=1^m δm=1-δ. Thus, with probability at least 1−δ1-δ, the claimed estimation bound holds simultaneously for all i∈[m]i∈[m]. Furthermore, under the assumed uniform lower bound μi′(z)≥cμ _i(z)≥ c_μ over the relevant parameter domain, μi∗=E[μi′(⟨X,Θi∗⟩)]≥cμ>0 _i^*=E [μ _i ( X, _i^* ) ]≥ c_μ>0 for every i∈[m]i∈[m]. This completes the proof. □ After acquiring the estimated Θ^i _i in Algorithm 1, we can obtain the corresponding SVD as Θ^i=[U^i,U^i,⟂]D^i[V^i,V^i,⟂]⊤, _i=[ U_i, U_i, ] D_i[ V_i, V_i, ] , where U^i∈ℝd1×r,U^i,⟂∈ℝd1×(d1−r),V^i∈ℝd2×r,V^i,⟂∈ℝd2×(d2−r). U_i ^d_1× r, U_i, ^d_1×(d_1-r), V_i ^d_2× r, V_i, ^d_2×(d_2-r). And we assume the SVD of the matrix Θi∗ ^*_i can be represented as Θi∗=UiDiVi⊤, ^*_i=U_iD_iV_i , where Ui∈ℝd1×rU_i ^d_1× r and Vi∈ℝd2×rV_i ^d_2× r. To transform the original generalized matrix bandits into generalized linear bandit problems, we penalize those covariates that are complementary to U^i U_i and V^i V_i. Specifically, we could orthogonally rotate the inherent parameter Θi∗ _i^* as Θi′=[U^i,U^i,⟂]⊤Θi∗[V^i,V^i,⟂]. _i=[ U_i, U_i, ] _i^*[ V_i, V_i, ]. Define the total dimension and the effective dimension as p=d1d2,k=d1d2−(d1−r)(d2−r).p=d_1d_2, k=d_1d_2-(d_1-r)(d_2-r). For each objective i∈[m]i∈[m], let Drr,iD_r,i denote the r-th largest singular value of the objective-specific parameter matrix Θi∗ _i^*, and define Drr=mini∈[m]Drr,iD_r= _i∈[m]D_r,i. Then, for the true parameter θi∗θ^*_i after transformation, we denote the last p−kp-k entries as θi,k+1:p∗θ^*_i,k+1:p, such that θi,k+1:p∗=vec((Θi′)r+1:d1,r+1:d2).θ^*_i,k+1:p=vec (( _i)_r+1:d_1,\;r+1:d_2 ). Lemma 2 (Subspace perturbation to tail control) Let A=UDV⊤A=UDV have rank r and smallest nonzero singular value σr(A)>0 _r(A)>0. Let A A be any matrix, and let U U and V V contain its leading r left and right singular vectors. Then ‖U^⟂⊤U‖F,‖V^⟂⊤V‖F≤2‖A^−A‖Fσr(A)\| U_ U\|_F,\,\| V_ V\|_F≤ 2\| A-A\|_F _r(A) and ‖U^⟂⊤UDV⊤V^⟂‖F≤4‖D‖op‖A^−A‖F2σr(A)2.\| U_ UDV V_ \|_F≤ 4\|D\|_op\| A-A\|_F^2 _r(A)^2. Proof. Let A^r A_r be the best rank-r approximation of A A. Because A has rank r, the Eckart–Young theorem gives ‖A^−A^r‖F≤‖A^−A‖F\| A- A_r\|_F≤\| A-A\|_F. Therefore, ‖U^⟂⊤A‖F≤‖A^−A‖F+‖A^−A^r‖F≤2‖A^−A‖F.\| U_ A\|_F≤\| A-A\|_F+\| A- A_r\|_F≤ 2\| A-A\|_F. On the other hand, ‖U^⟂⊤A‖F≥σr(A)‖U^⟂⊤U‖F\| U_ A\|_F≥ _r(A)\| U_ U\|_F. This proves the left-subspace bound; applying the same argument to A⊤A proves the right-subspace bound. Finally, ‖U^⟂⊤UDV⊤V^⟂‖F≤‖U^⟂⊤U‖F‖D‖op‖V⊤V^⟂‖F,\| U_ UDV V_ \|_F≤\| U_ U\|_F\|D\|_op\|V V_ \|_F, and substituting the two subspace bounds proves the result. □ Lemma 3 Suppose that the conditions of Lemma 1 hold. Then, with probability at least 1−δ1-δ, simultaneously for all i∈[m]i∈[m], ∥θi,k+1:p∗∥2≲M(d1+d2)rT1Drr2log(m(d1+d2)δ)=:S⟂. \| _i,k+1:p^* \|_2 M(d_1+d_2)rT_1D_r^2 ( m(d_1+d_2)δ )=:S_ . Proof. Set Ai=μi∗Θi∗A_i= _i^* _i^* and Ei=Θ^i−AiE_i= _i-A_i. Since μi∗>0 _i^*>0, AiA_i and Θi∗ _i^* have the same singular subspaces, and σr(Ai)=μi∗Di,rr _r(A_i)= _i^*D_i,r. Moreover, the last p−kp-k coordinates of θi∗ _i^* are the vectorization of U^i,⟂⊤Θi∗V^i,⟂ U_i, _i^* V_i, . Lemma 2 therefore gives ‖θi,k+1:p∗‖2≤4‖Di‖op‖Ei‖F2(μi∗)2Di,rr2.\| _i,k+1:p^*\|_2≤ 4\|D_i\|_op\|E_i\|_F^2( _i^*)^2D_i,r^2. By Lemma 1, the event ‖Ei‖F2≤C1M(d1+d2)rlog(2m(d1+d2)/δ)T1\|E_i\|_F^2≤ C_1M(d_1+d_2)r (2m(d_1+d_2)/δ)T_1 holds simultaneously for all objectives. Using μi∗≥cμ _i^*≥ c_μ, Di,rr≥DrrD_i,r≥ D_r, and ‖Di‖op≤Dmax\|D_i\|_op≤ D_ , and suppressing constants depending on C1C_1, cμc_μ, and DmaxD_ , proves the claim. □ Step 2: Confidence bound for the batch estimators. The next lemma converts the batch estimation error into a reward confidence interval that holds uniformly over rounds, objectives, and arms. Lemma 4 Suppose Assumptions 2–4 hold. Then, with probability at least 1−δ1-δ, for all t≥1t≥ 1, all objectives i∈[m]i∈[m], and all arms X∈X , we have |μi(fi(X)⊤θi∗)−μi(fi(X)⊤θ^t,i)|≤βt‖fi(X)‖Vt,i−1, | _i\! (f_i(X) _i^* )- _i\! (f_i(X) θ_t,i ) |≤ _t\|f_i(X)\|_V_t,i^-1, where βt+1=Lμ(Rklog(1+tk)+cμt2λ⟂+2log(mδ)+(λ0S+λ⟂S⟂)). _t+1=L_μ (R k (1+ tk )+ c_μt2 _ +2 ( mδ )+ ( _0S+ _ S_ ) ). Proof. Fix an objective i∈[m]i∈[m] and write xτ,i=fi(Xτ),x=fi(X).x_τ,i=f_i(X_τ), x=f_i(X). For notational simplicity, we omit the subscript i when there is no ambiguity. At the beginning of round t, the estimator θ^t,i θ_t,i is computed from the observations collected in the previous t−1t-1 rounds. Define gt,i(θ)=∑τ=1t−1μi(xτ,i⊤θ)xτ,i+Λθ.g_t,i(θ)= _τ=1^t-1 _i(x_τ,i θ)x_τ,i+ θ. Since θ^t,i θ_t,i minimizes the regularized negative log-likelihood, the first-order optimality condition gives gt,i(θ^t,i)=∑τ=1t−1yτ,ixτ,i.g_t,i( θ_t,i)= _τ=1^t-1y_τ,ix_τ,i. Moreover, gt,i(θi∗)−gt,i(θ^t,i)=−∑τ=1t−1ητ,ixτ,i+Λθi∗,g_t,i( _i^*)-g_t,i( θ_t,i)=- _τ=1^t-1 _τ,ix_τ,i+ _i^*, where ητ,i=yτ,i−μi(xτ,i⊤θi∗). _τ,i=y_τ,i- _i(x_τ,i _i^*). Next, by the fundamental theorem of calculus, gt,i(θi∗)−gt,i(θ^t,i)=Gt,i(θi∗−θ^t,i),g_t,i( _i^*)-g_t,i( θ_t,i)=G_t,i( _i^*- θ_t,i), where Gt,i=∫01∇gt,i(sθi∗+(1−s)θ^t,i)s.G_t,i= _0^1∇ g_t,i\! (s _i^*+(1-s) θ_t,i )ds. Since μ˙i(⋅)≥cμ μ_i(·)≥ c_μ, we have Gt,i⪰cμ∑τ=1t−1xτ,ixτ,i⊤+Λ⪰Vt,i=cμ2∑τ=1t−1xτ,ixτ,i⊤+Λ.G_t,i c_μ _τ=1^t-1x_τ,ix_τ,i + _t,i= c_μ2 _τ=1^t-1x_τ,ix_τ,i + . Using the Lipschitzness of μi(⋅) _i(·), we obtain |μi(x⊤θi∗)−μi(x⊤θ^t,i)| | _i(x _i^*)- _i(x θ_t,i) | ≤Lμ|x⊤(θi∗−θ^t,i)| ≤ L_μ |x ( _i^*- θ_t,i) | =Lμ|x⊤Gt,i−1(gt,i(θi∗)−gt,i(θ^t,i))| =L_μ |x G_t,i^-1 (g_t,i( _i^*)-g_t,i( θ_t,i) ) | ≤Lμ‖x‖Vt,i−1‖gt,i(θi∗)−gt,i(θ^t,i)‖Vt,i−1. ≤ L_μ\|x\|_V_t,i^-1 \|g_t,i( _i^*)-g_t,i( θ_t,i) \|_V_t,i^-1. Substituting the expression of gt,i(θi∗)−gt,i(θ^t,i)g_t,i( _i^*)-g_t,i( θ_t,i) gives |μi(x⊤θi∗)−μi(x⊤θ^t,i)|≤Lμ‖x‖Vt,i−1(‖∑τ=1t−1ητ,ixτ,i‖Vt,i−1+‖Λθi∗‖Vt,i−1). | _i(x _i^*)- _i(x θ_t,i) |≤ L_μ\|x\|_V_t,i^-1 ( \| _τ=1^t-1 _τ,ix_τ,i \|_V_t,i^-1+\| _i^*\|_V_t,i^-1 ). (12) We now bound the two terms inside the parentheses. Since the noise is bounded by R, it is conditionally R-sub-Gaussian. By the self-normalized martingale inequality [Abbasi-yadkori et al., 2011], with probability at least 1−δ/m1-δ/m, simultaneously for all t≥1t≥ 1, ‖∑τ=1t−1ητ,ixτ,i‖Vt,i−1≤Rlogdet(Vt,i)det(Λ)+2log(m/δ). \| _τ=1^t-1 _τ,ix_τ,i \|_V_t,i^-1≤ R (V_t,i) ( )+2 (m/δ). (13) To bound the log-determinant term, Lemma C.5 of Kang et al. [2022], λ0≥cμ/2 _0≥ c_μ/2, and log(1+x)≤x (1+x)≤ x give logdet(Vt,i)det(Λ)≤klog(1+tk)+cμt2λ⟂. (V_t,i) ( )≤ k (1+ tk )+ c_μt2 _ . Substituting this bound into (13) gives ‖∑τ=1t−1ητ,ixτ,i‖Vt,i−1≤Rklog(1+tk)+cμt2λ⟂+2log(mδ). \| _τ=1^t-1 _τ,ix_τ,i \|_V_t,i^-1≤ R k (1+ tk )+ c_μt2 _ +2 ( mδ ). (14) For the regularization bias term, since Vt,i⪰Λ,V_t,i , we have ‖Λθi∗‖Vt,i−1≤‖θi∗‖Λ.\| _i^*\|_V_t,i^-1≤\| _i^*\|_ . By the construction of the transformed feature space, ‖(θi∗)1:k‖2≤S,‖(θi∗)k+1:p‖2≤S⟂.\|( _i^*)_1:k\|_2≤ S, \|( _i^*)_k+1:p\|_2≤ S_ . Thus, ‖Λθi∗‖Vt,i−1≤‖θi∗‖Λ≤λ0S+λ⟂S⟂.\| _i^*\|_V_t,i^-1≤\| _i^*\|_ ≤ _0S+ _ S_ . (15) Taking the Eq. (14) and Eq. (15) into Eq. (12), with probability at least 1−δ/m1-δ/m, for the fixed objective i and all t≥1t≥ 1, all X∈X , |μi(fi(X)⊤θi∗)−μi(fi(X)⊤θ^t,i)|≤Lμ(Rklog(1+tk)+cμt2λ⟂+2log(mδ)+(λ0S+λ⟂S⟂))‖fi(X)‖Vt,i−1. | _i(f_i(X) _i^*)- _i(f_i(X) θ_t,i) |≤ L_μ (R k (1+ tk )+ c_μt2 _ +2 ( mδ )+ ( _0S+ _ S_ ) )\|f_i(X)\|_V_t,i^-1. Taking a union bound over all objectives i∈[m]i∈[m] completes the proof. □ Step 3: Scalarized optimism and objective-wise regret. We first relate the objective-wise gaps to a single scalarized gap. This step is where the factor WscaW sca enters the analysis. Lemma 5 Suppose Assumption 5 holds. For any arm X∈X and objective i∈[m]i∈[m], define the objective-wise gap Δi(X)=μi(⟨X∗,Θi∗⟩)−μi(⟨X,Θi∗⟩). _i(X)= _i\! ( _*, _i^* )- _i\! ( , _i^* ). Let q=1+wq=1+w. Then, for every objective i∈[m]i∈[m] and every arm X∈X , Δi(X)≤∑j=1mqm−jΔj(X)=∑j=1m(1+w)m−jΔj(X). _i(X)≤ _j=1^mq^m-j _j(X)= _j=1^m(1+w)^m-j _j(X). Consequently, for any sequence of arms Xtt=1T2\X_t\_t=1^T_2, Ri(T2)=∑t=1T2Δi(Xt)≤∑t=1T2∑j=1m(1+w)m−jΔj(Xt),∀i∈[m].R_i(T_2)= _t=1^T_2 _i(X_t)≤ _t=1^T_2 _j=1^m(1+w)^m-j _j(X_t), ∀ i∈[m]. Proof. Fix an arbitrary arm X∈X . For simplicity, write Δi=Δi(X) _i= _i(X). Since X∗X_* is lexicographically optimal, no arm can strictly improve the first objective over X∗X_*. Hence, Δ1=μ1(⟨X∗,Θ1∗⟩)−μ1(⟨X,Θ1∗⟩)≥0. _1= _1\! ( _*, _1^* )- _1\! ( , _1^* )≥ 0. Moreover, Assumption 5 implies that, for every i≥2i≥ 2, −Δi=μi(⟨X,Θi∗⟩)−μi(⟨X∗,Θi∗⟩)≤wmaxj∈[i−1]Δj.- _i= _i\! ( , _i^* )- _i\! ( _*, _i^* )≤ w _j∈[i-1] _j. For ℓ∈[m] ∈[m], define Pℓ=∑j=1ℓqℓ−jΔj,Mℓ=maxj∈[ℓ]Δj.P_ = _j=1 q -j _j, M_ = _j∈[ ] _j. We prove by induction that Pℓ≥Mℓ,∀ℓ∈[m].P_ ≥ M_ , ∀ ∈[m]. When ℓ=1 =1, we have P1=Δ1=M1≥0.P_1= _1=M_1≥ 0. Suppose Pℓ−1≥Mℓ−1P_ -1≥ M_ -1 holds for some ℓ≥2 ≥ 2. Then Pℓ=qPℓ−1+Δℓ.P_ =qP_ -1+ _ . By the induction hypothesis and the trade-off condition, Pℓ≥qMℓ−1−wMℓ−1=(q−w)Mℓ−1=Mℓ−1,P_ ≥ qM_ -1-wM_ -1=(q-w)M_ -1=M_ -1, where we used q=1+wq=1+w. If Δℓ≤Mℓ−1 _ ≤ M_ -1, then Mℓ=Mℓ−1M_ =M_ -1, and hence Pℓ≥MℓP_ ≥ M_ . If Δℓ>Mℓ−1 _ >M_ -1, then Mℓ=ΔℓM_ = _ . Since Mℓ−1≥Δ1≥0M_ -1≥ _1≥ 0 and Pℓ−1≥Mℓ−1P_ -1≥ M_ -1, we have Pℓ=qPℓ−1+Δℓ≥Δℓ=Mℓ.P_ =qP_ -1+ _ ≥ _ =M_ . Thus, Pℓ≥MℓP_ ≥ M_ for all ℓ∈[m] ∈[m]. Taking ℓ=m =m, we obtain ∑j=1mqm−jΔj=Pm≥Mm=maxj∈[m]Δj. _j=1^mq^m-j _j=P_m≥ M_m= _j∈[m] _j. Therefore, for every i∈[m]i∈[m], Δi≤maxj∈[m]Δj≤∑j=1mqm−jΔj. _i≤ _j∈[m] _j≤ _j=1^mq^m-j _j. Substituting back q=1+wq=1+w gives Δi(X)≤∑j=1m(1+w)m−jΔj(X). _i(X)≤ _j=1^m(1+w)^m-j _j(X). Finally, applying this pointwise inequality to each played arm XtX_t and summing over t=1,…,T2t=1,…,T_2 yields Ri(T2)=∑t=1T2Δi(Xt)≤∑t=1T2∑j=1m(1+w)m−jΔj(Xt).R_i(T_2)= _t=1^T_2 _i(X_t)≤ _t=1^T_2 _j=1^m(1+w)^m-j _j(X_t). This completes the proof. □ By Lemma 5, Ri(T2)≤∑t=1T2∑i=1m(1+w)m−i(μi(⟨X∗,Θi∗⟩)−μi(⟨Xt,Θi∗⟩)). R_i(T_2)≤ _t=1^T_2 _i=1^m(1+w)^m-i ( _i\! ( X_*, _i^* )- _i\! ( _t, _i^* ) ). (16) Consider the high-probability event in Lemma 4, on which, for every t∈[T2]t∈[T_2], j∈[m]j∈[m], and X∈X , |y^t,j(X)−μj(⟨X,Θj∗⟩)|≤βt‖fj(X)‖Vt,j−1=ct,j(X). | y_t,j(X)- _j\! ( , _j^* ) |≤ _t\|f_j(X)\|_V_t,j^-1=c_t,j(X). It follows that ∑j=1m(1+w)m−jμj(⟨X,Θj∗⟩)≤UCBt(X,w) _j=1^m(1+w)^m-j _j\! ( , _j^* ) _t(X,w) for every X∈X . Moreover, UCBt(X,w)−∑j=1m(1+w)m−jμj(⟨X,Θj∗⟩) _t(X,w)- _j=1^m(1+w)^m-j _j\! ( , _j^* ) =∑j=1m(1+w)m−j[y^t,j(X)+ct,j(X)−μj(⟨X,Θj∗⟩)] = _j=1^m(1+w)^m-j [ y_t,j(X)+c_t,j(X)- _j\! ( , _j^* ) ] ≤2∑j=1m(1+w)m−jct,j(X). ≤ 2 _j=1^m(1+w)^m-jc_t,j(X). (17) Using (B) and the arm-selection rule Xt∈argmaxX∈UCBt(X,w),X_t∈ *argmax_X UCB_t(X,w), we obtain Ri(T2) R_i(T_2) ≤∑t=1T2[UCBt(X∗,w)−∑j=1m(1+w)m−jμj(⟨Xt,Θj∗⟩)] ≤ _t=1^T_2 [UCB_t(X_*,w)- _j=1^m(1+w)^m-j _j\! ( _t, _j^* ) ] ≤∑t=1T2[UCBt(Xt,w)−∑j=1m(1+w)m−jμj(⟨Xt,Θj∗⟩)] ≤ _t=1^T_2 [UCB_t(X_t,w)- _j=1^m(1+w)^m-j _j\! ( _t, _j^* ) ] ≤2∑t=1T2∑j=1m(1+w)m−jβt‖fj(Xt)‖Vt,j−1. ≤ 2 _t=1^T_2 _j=1^m(1+w)^m-j _t\|f_j(X_t)\|_V_t,j^-1. Since βt≤βT _t≤ _T, interchanging the two sums and applying the Cauchy–Schwarz inequality yield Ri(T2) R_i(T_2) ≤2βT∑j=1m(1+w)m−j∑t=1T2‖fj(Xt)‖Vt,j−1 ≤ 2 _T _j=1^m(1+w)^m-j _t=1^T_2\|f_j(X_t)\|_V_t,j^-1 ≤2βTT2∑j=1m(1+w)m−j(∑t=1T2‖fj(Xt)‖Vt,j−12)1/2. ≤ 2 _T T_2 _j=1^m(1+w)^m-j ( _t=1^T_2\|f_j(X_t)\|_V_t,j^-1^2 )^1/2. (18) For each objective, the standard elliptical-potential argument [Abbasi-yadkori et al., 2011, Lemma 11], followed by the anisotropic log-determinant bound of Lemma C.5 in Kang et al. [2022], gives ∑t=1T2‖fi(Xt)‖Vt,i−12≤4cμ(klog(1+Tk)+cμT2λ⟂). _t=1^T_2\|f_i(X_t)\|_V_t,i^-1^2≤ 4c_μ (k (1+ Tk )+ c_μT2 _ ). Thus, we have Ri(T2)≤∑i=1m(1+w)m−i2βTT24cμ(klog(1+Tk)+cμT2λ⟂) R_i(T_2)≤ _i=1^m(1+w)^m-i2 _T T_2 4c_μ (k (1+ Tk )+ c_μT2 _ ) Taking the first T1T_1 rounds and μi(⋅)≤U _i(·)≤ U into the total regret, we have Ri(T) R_i(T) ≤2UT1+∑i=1m(1+w)m−i4βTT2kcμlog(1+Tk)+T2λ⟂ ≤ 2UT_1+ _i=1^m(1+w)^m-i4 _T T_2 kc_μ (1+ Tk )+ T2 _ Step 4: Parameter choice and completion of the proof. We now substitute the choices of T1T_1, λ⟂ _ , and S⟂S_ into the regret bound. Define Wsca:=∑j=1m(1+w)m−j,A:=M(d1+d2)rDrr2log(m(d1+d2)δ).W sca:= _j=1^m(1+w)^m-j, A:= M(d_1+d_2)rD_r^2 \! ( m(d_1+d_2)δ ). By the choice of the exploration length T1≍AT_1 AT and S⟂=(d1+d2)MrT1Drr2log(m(d1+d2)δ)=AT1,S_ = (d_1+d_2)MrT_1D_r^2 \! ( m(d_1+d_2)δ )= AT_1, we have S⟂≍AT.S_ AT. Recall that λ⟂=cμTklog(1+cμT/(kλ0)). _ = c_μTk \! (1+c_μT/(k _0) ). Therefore, cμT2λ⟂=k2log(1+cμTkλ0), c_μT2 _ = k2 \! (1+ c_μTk _0 ), and hence the confidence radius satisfies βT _T ≤Lμ(Rklog(1+Tk)+cμT2λ⟂+2log(mδ)+λ0S+λ⟂S⟂) ≤ L_μ (R k \! (1+ Tk )+ c_μT2 _ +2 \! ( mδ )+ _0S+ _ S_ ) =O~(Lμ(Rk+λ0S+λ⟂S⟂)). = O (L_μ (R k+ _0S+ _ S_ ) ). Furthermore, λ⟂S⟂=cμTklog(1+cμT/(kλ0))⋅AT=O~(cμAk). _ S_ = c_μTk \! (1+c_μT/(k _0) )· AT= O ( c_μAk ). Thus, βT=O~(Lμ(Rk+λ0S+cμAk)). _T= O (L_μ (R k+ _0S+ c_μAk ) ). On the other hand, the elliptical-potential term in the regret bound can be simplified as kcμlog(1+Tk)+T2λ⟂ kc_μ \! (1+ Tk )+ T2 _ =kcμlog(1+Tk)+k2cμlog(1+cμTkλ0) = kc_μ \! (1+ Tk )+ k2c_μ \! (1+ c_μTk _0 ) =O~(kcμ). = O ( kc_μ ). Using T2≤T_2≤ T, we obtain Ri(T) R_i(T) ≤2UT1+4WscaβTT2kcμlog(1+Tk)+T2λ⟂ ≤ 2UT_1+4W sca _T T_2 kc_μ \! (1+ Tk )+ T2 _ =O~(UAT+WscaLμ(Rkcμ+Sλ0kcμ+A)T). = O (U AT+W scaL_μ ( Rk c_μ+S _0kc_μ+ A ) T ). Substituting the definition of A gives Ri(T)=O~([UM(d1+d2)rDrr+WscaLμ(Rkcμ+Sλ0kcμ+M(d1+d2)rDrr)]T).R_i(T)= O ( [U M(d_1+d_2)rD_r+W scaL_μ ( Rk c_μ+S _0kc_μ+ M(d_1+d_2)rD_r ) ] T ). When U,Lμ,R,cμ,λ0U,L_μ,R,c_μ, _0, and S are treated as constants, and since Wsca≥1W sca≥ 1, this simplifies to Ri(T)=O~(Wsca(k+M(d1+d2)rDrr)T).R_i(T)= O (W sca (k+ M(d_1+d_2)rD_r ) T ). Finally, since k=(d1+d2)r−r2≍(d1+d2)rk=(d_1+d_2)r-r^2 (d_1+d_2)r, under the standard scaling condition M(d1+d2)rDrr≲(d1+d2)r, M(d_1+d_2)rD_r (d_1+d_2)r, we obtain Ri(T)=O~(Wsca(d1+d2)rT).R_i(T)= O (W sca(d_1+d_2)r T ). The proof of Theorem 1 is finished. □ Appendix C Proof of Theorem 2 Proof roadmap. The online proof separates estimation from lexicographic decision making. First, we establish a uniform confidence bound for the online Newton-type estimators. Second, we prove that the filtering rule never eliminates the lexicographically optimal arm and that the arm selected in the current round is controlled by the previous round’s common uncertainty. Third, because the most uncertain objective may change across rounds, we partition the elliptical norms by objective, combine the resulting m potential budgets, and substitute the same parameter choices as in Theorem 1. Step 1: Online estimation and reward confidence. Lemma 6 (One-step estimation recursion) Fix an objective i∈[m]i∈[m] and define at=fi(Xt)⊤(θ^t,i−θi∗)a_t=f_i(X_t) ( θ_t,i- _i^*). Under Assumptions 2–4, ‖θ^t+1,i−θi∗‖Vt+1,i2 \| θ_t+1,i- _i^*\|_V_t+1,i^2 ≤‖θ^t,i−θi∗‖Vt,i2−cμ2at2+4(U+R)2‖fi(Xt)‖Vt+1,i−12+2ηt,iat. ≤\| θ_t,i- _i^*\|_V_t,i^2- c_μ2a_t^2+4(U+R)^2\|f_i(X_t)\|_V_t+1,i^-1^2+2 _t,ia_t. Proof. Fix an objective i∈[m]i∈[m]. For simplicity, we write xt=fi(Xt)x_t=f_i(X_t), θ^t=θ^t,i θ_t= θ_t,i, θ∗=θi∗θ^*= _i^*, Vt=Vt,iV_t=V_t,i, and ηt=ηt,i _t= _t,i. Define the instantaneous loss ℓt,i(θ)=−yt,ixt⊤θ+∫0xt⊤θμi(z)z. _t,i(θ)=-y_t,ix_t θ+ _0^x_t θ _i(z)\,dz. Then ∇ℓt,i(θ)=(μi(xt⊤θ)−yt,i)xt,∇ _t,i(θ)= ( _i(x_t θ)-y_t,i )x_t, which is consistent with Eq. (9). Since μ˙i(z)≥cμ μ_i(z)≥ c_μ, the function ℓt,i(⋅) _t,i(·) is strongly convex along the direction xtx_t. Thus, for any θ1,θ2 _1, _2, ℓt,i(θ1)−ℓt,i(θ2)≤∇ℓt,i(θ1)⊤(θ1−θ2)−cμ2(xt⊤θ1−xt⊤θ2)2. _t,i( _1)- _t,i( _2)≤∇ _t,i( _1) ( _1- _2)- c_μ2 (x_t _1-x_t _2 )^2. Taking θ1=θ^t _1= θ_t and θ2=θ∗ _2=θ^* gives ℓt,i(θ^t)−ℓt,i(θ∗)≤∇ℓt,i(θ^t)⊤(θ^t−θ∗)−cμ2(xt⊤θ^t−xt⊤θ∗)2. _t,i( θ_t)- _t,i(θ^*)≤∇ _t,i( θ_t) ( θ_t-θ^*)- c_μ2 (x_t θ_t-x_t θ^* )^2. Let ft,i(θ)=E[ℓt,i(θ)]f_t,i(θ)=E[ _t,i(θ)]. Since E[yt,i]=μi(xt⊤θ∗)E[y_t,i]= _i(x_t θ^*), the parameter θ∗θ^* minimizes ft,i(θ)f_t,i(θ), and hence ft,i(θ^t)−ft,i(θ∗)≥0.f_t,i( θ_t)-f_t,i(θ^*)≥ 0. Taking conditional expectation in the previous strong-convexity inequality and using the above fact yields 0≤∇ft,i(θ^t)⊤(θ^t−θ∗)−cμ2(xt⊤θ^t−xt⊤θ∗)2.0≤∇ f_t,i( θ_t) ( θ_t-θ^*)- c_μ2 (x_t θ_t-x_t θ^* )^2. By adding and subtracting ∇ℓt,i(θ^t)∇ _t,i( θ_t), we obtain 0≤(∇ft,i(θ^t)−∇ℓt,i(θ^t))⊤(θ^t−θ∗)+∇ℓt,i(θ^t)⊤(θ^t−θ∗)−cμ2(xt⊤θ^t−xt⊤θ∗)2. 0≤ (∇ f_t,i( θ_t)-∇ _t,i( θ_t) ) ( θ_t-θ^*)+∇ _t,i( θ_t) ( θ_t-θ^*)- c_μ2 (x_t θ_t-x_t θ^* )^2. Moreover, ∇ft,i(θ^t)=(μi(xt⊤θ^t)−μi(xt⊤θ∗))xt,∇ f_t,i( θ_t)= ( _i(x_t θ_t)- _i(x_t θ^*) )x_t, and therefore ∇ft,i(θ^t)−∇ℓt,i(θ^t)=ηtxt.∇ f_t,i( θ_t)-∇ _t,i( θ_t)= _tx_t. Hence, 0≤ηt(xt⊤θ^t−xt⊤θ∗)+∇ℓt,i(θ^t)⊤(θ^t−θ∗)−cμ2(xt⊤θ^t−xt⊤θ∗)2. 0≤ _t (x_t θ_t-x_t θ^* )+∇ _t,i( θ_t) ( θ_t-θ^*)- c_μ2 (x_t θ_t-x_t θ^* )^2. Next, the proximal update in Eq. (10) implies the standard online Newton inequality: for any feasible θ, ∇ℓt,i(θ^t)⊤(θ^t−θ)−12‖∇ℓt,i(θ^t)‖Vt+1−12≤12(‖θ^t−θ‖Vt+12−‖θ^t+1−θ‖Vt+12).∇ _t,i( θ_t) ( θ_t-θ)- 12\|∇ _t,i( θ_t)\|_V_t+1^-1^2≤ 12 (\| θ_t-θ\|_V_t+1^2-\| θ_t+1-θ\|_V_t+1^2 ). Taking θ=θ∗θ=θ^* gives 0≤12(‖θ^t−θ∗‖Vt+12−‖θ^t+1−θ∗‖Vt+12)−cμ2(xt⊤θ^t−xt⊤θ∗)2+ηt(xt⊤θ^t−xt⊤θ∗)+12‖∇ℓt,i(θ^t)‖Vt+1−12. 0≤ 12 (\| θ_t-θ^*\|_V_t+1^2-\| θ_t+1-θ^*\|_V_t+1^2 )- c_μ2 (x_t θ_t-x_t θ^* )^2+ _t (x_t θ_t-x_t θ^* )+ 12\|∇ _t,i( θ_t)\|_V_t+1^-1^2. Since Vt+1=Vt+cμ2xtxt⊤,V_t+1=V_t+ c_μ2x_tx_t , we have ‖θ^t−θ∗‖Vt+12=‖θ^t−θ∗‖Vt2+cμ2(xt⊤θ^t−xt⊤θ∗)2.\| θ_t-θ^*\|_V_t+1^2=\| θ_t-θ^*\|_V_t^2+ c_μ2 (x_t θ_t-x_t θ^* )^2. Substituting this identity into the previous inequality yields 0≤12(‖θ^t−θ∗‖Vt2−‖θ^t+1−θ∗‖Vt+12)−cμ4(xt⊤θ^t−xt⊤θ∗)2+ηt(xt⊤θ^t−xt⊤θ∗)+12‖∇ℓt,i(θ^t)‖Vt+1−12. 0≤ 12 (\| θ_t-θ^*\|_V_t^2-\| θ_t+1-θ^*\|_V_t+1^2 )- c_μ4 (x_t θ_t-x_t θ^* )^2+ _t (x_t θ_t-x_t θ^* )+ 12\|∇ _t,i( θ_t)\|_V_t+1^-1^2. By Assumption 4, |ηt|≤R| _t|≤ R and |μi(⋅)|≤U| _i(·)|≤ U. Hence |yt,i|≤U+R|y_t,i|≤ U+R and |μi(xt⊤θ^t)−yt,i|≤2(U+R).| _i(x_t θ_t)-y_t,i|≤ 2(U+R). Using a slightly loose bound, we have ‖∇ℓt,i(θ^t)‖Vt+1−12≤4(U+R)2‖xt‖Vt+1−12.\|∇ _t,i( θ_t)\|_V_t+1^-1^2≤ 4(U+R)^2\|x_t\|_V_t+1^-1^2. Therefore, 0≤12(‖θ^t−θ∗‖Vt2−‖θ^t+1−θ∗‖Vt+12)−cμ4(xt⊤θ^t−xt⊤θ∗)2+ηt(xt⊤θ^t−xt⊤θ∗)+2(U+R)2‖xt‖Vt+1−12. 0≤ 12 (\| θ_t-θ^*\|_V_t^2-\| θ_t+1-θ^*\|_V_t+1^2 )- c_μ4 (x_t θ_t-x_t θ^* )^2+ _t (x_t θ_t-x_t θ^* )+2(U+R)^2\|x_t\|_V_t+1^-1^2. Multiplying by two and rearranging proves the stated recursion. □ Lemma 7 (Uniform control of the noise cross term) Fix an objective i∈[m]i∈[m] and let at=fi(Xt)⊤(θ^t,i−θi∗)a_t=f_i(X_t) ( θ_t,i- _i^*). Under Assumptions 2–4, with probability at least 1−δ/m1-δ/m, simultaneously for all t≥1t≥ 1, 2∑τ=1tητ,iaτ≤cμ2+cμ2∑τ=1taτ2+16R2cμlog(m1+4S2tδ).2 _τ=1^t _τ,ia_τ≤ c_μ2+ c_μ2 _τ=1^ta_τ^2+ 16R^2c_μ ( m 1+4S^2tδ ). Proof. The sequence ηt,iatt≥1\ _t,ia_t\_t≥ 1 is a martingale difference sequence and |ηt,i|≤R| _t,i|≤ R. The self-normalized martingale inequality [Abbasi-Yadkori et al., 2012] therefore gives, simultaneously for all t≥1t≥ 1, ∑τ=1tητ,iaτ≤R2(1+∑τ=1taτ2)log(m1+∑τ=1taτ2δ). _τ=1^t _τ,ia_τ≤ R 2 (1+ _τ=1^ta_τ^2 ) ( m 1+ _τ=1^ta_τ^2δ ). Since ‖fi(Xτ)‖2≤1\|f_i(X_τ)\|_2≤ 1 and both ‖θ^τ,i‖2\| θ_τ,i\|_2 and ‖θi∗‖2\| _i^*\|_2 are at most S, we have |aτ|≤2S|a_τ|≤ 2S. Thus the logarithm is at most log(m1+4S2tδ). ( m 1+4S^2tδ ). Applying Young’s inequality to the resulting square-root term gives the claimed bound. □ Lemma 8 Suppose Assumptions 2–4 hold. With probability at least 1−δ1-δ, for all i∈[m]i∈[m] and all t≥1t≥ 1, ‖θ^t+1,i−θi∗‖Vt+1,i2≤‖θi∗‖Λ2+16(U+R)2cμlogdet(Vt+1,i)det(Λ)+cμ2+16R2cμlog(m1+4S2tδ). \| θ_t+1,i- _i^*\|_V_t+1,i^2≤\| _i^*\|_ ^2+ 16(U+R)^2c_μ (V_t+1,i) ( )+ c_μ2+ 16R^2c_μ ( m 1+4S^2tδ ). Proof. Fix i∈[m]i∈[m], suppress the objective index, and let at=xt⊤(θ^t−θ∗)a_t=x_t ( θ_t-θ^*). Summing Lemma 6 over τ=1,…,tτ=1,…,t, and using θ^1=0 θ_1=0 and V1=ΛV_1= , gives ‖θ^t+1−θ∗‖Vt+12≤‖θ∗‖Λ2−cμ2∑τ=1taτ2+4(U+R)2∑τ=1t‖xτ‖Vτ+1−12+2∑τ=1tητaτ. \| θ_t+1-θ^*\|_V_t+1^2≤\|θ^*\|_ ^2- c_μ2 _τ=1^ta_τ^2+4(U+R)^2 _τ=1^t\|x_τ\|_V_τ+1^-1^2+2 _τ=1^t _τa_τ. The standard elliptical-potential argument [Hazan et al., 2007] yields ∑τ=1t‖xτ‖Vτ+1−12≤4cμlogdet(Vt+1)det(Λ). _τ=1^t\|x_τ\|_V_τ+1^-1^2≤ 4c_μ (V_t+1) ( ). On the event in Lemma 7, its quadratic term exactly cancels the negative strong-convexity term above. Substitution therefore proves the claimed bound for objective i. A union bound over i∈[m]i∈[m] completes the proof. □ By Lemma C.5 of Kang et al. [2022], together with λ0≥cμ/2 _0≥ c_μ/2 and log(1+x)≤x (1+x)≤ x, for every objective i∈[m]i∈[m], logdet(Vt+1)det(Λ)≤klog(1+tk)+cμt2λ⟂. det(V_t+1)det( )≤ k (1+ tk )+ c_μt2 _ . Substituting this bound into Lemma 8, we obtain that for all i∈[m]i∈[m], ∥θ^t+1,i−θi∗∥Vt+1,i2≤λ0S2+λ⟂S⟂2+16(U+R)2cμ⋅(klog(1+tk)+cμt2λ⟂)+cμ2+16R2cμlog(m1+4S2tδ). θ_t+1,i-θ^*_i _V_t+1,i^2≤ _0S^2+ _ S_ ^2+ 16(U+R)^2c_μ· (k (1+ tk )+ c_μt2 _ )+ c_μ2+ 16R^2c_μ ( m 1+4S^2tδ ). Based on this, we provide the following lemma. Lemma 9 Suppose Assumptions 2–4 hold. Then, with probability at least 1−δ1-δ, for all t≥1t≥ 1, all objectives i∈[m]i∈[m], and all arms X∈X , we have |μi(fi(X)⊤θi∗)−μi(fi(X)⊤θ^t,i)|≤βt‖fi(X)‖Vt,i−1, | _i\! (f_i(X) _i^* )- _i\! (f_i(X) θ_t,i ) |≤ _t\|f_i(X)\|_V_t,i^-1, where βt+1=Lμ(4(U+R)cμklog(1+tk)+cμt2λ⟂+log(m1+4S2tδ)+cμ2+λ0S+λ⟂S⟂). _t+1=L_μ ( 4(U+R) c_μ k (1+ tk )+ c_μt2 _ + ( m 1+4S^2tδ )+ c_μ2+ _0S+ _ S_ ). Proof. Fix any round t≥1t≥ 1, objective i∈[m]i∈[m], and arm X∈X . Since μi(⋅) _i(·) is LμL_μ-Lipschitz continuous, we have |μi(fi(X)⊤θi∗)−μi(fi(X)⊤θ^t,i)|≤Lμ|fi(X)⊤(θi∗−θ^t,i)|. | _i\! (f_i(X) _i^* )- _i\! (f_i(X) θ_t,i ) |≤ L_μ |f_i(X) ( _i^*- θ_t,i) |. By the Cauchy–Schwarz inequality under the norm induced by Vt,iV_t,i, we further obtain |fi(X)⊤(θi∗−θ^t,i)|≤‖fi(X)‖Vt,i−1‖θi∗−θ^t,i‖Vt,i. |f_i(X) ( _i^*- θ_t,i) |≤\|f_i(X)\|_V_t,i^-1\| _i^*- θ_t,i\|_V_t,i. Combining the above inequality gives |μi(fi(X)⊤θi∗)−μi(fi(X)⊤θ^t,i)|≤βt‖fi(X)‖Vt,i−1. | _i\! (f_i(X) _i^* )- _i\! (f_i(X) θ_t,i ) |≤ _t\|f_i(X)\|_V_t,i^-1. Since the confidence event holds uniformly over all t≥1t≥ 1 and i∈[m]i∈[m], the desired result follows. □ Step 2: Lexicographic filtering and bounded gaps. We next analyze the candidate-set recursion. The first lemma controls every arm that survives filtering within one round; the second transfers this control to the arm selected in the following round. Lemma 10 Suppose Assumption 5 holds. Let Wilex=1+w+⋯+wi−1.W_i lex=1+w+·s+w^i-1. With probability at least 1−δ1-δ, if X∗∈t0X_* _t^0, then, for every i∈[m]i∈[m], the following two statements hold: X∗∈ti,X_* _t^i, and, for every X∈tiX _t^i, μi(⟨X∗,Θi∗⟩)−μi(⟨X,Θi∗⟩)≤4Wilexct,it(Xt). _i( X_*, _i^* )- _i( , _i^* )≤ 4W_i lexc_t,i_t(X_t). Proof. For simplicity, define Δi(X)=μi(⟨X∗,Θi∗⟩)−μi(⟨X,Θi∗⟩). _i(X)= _i( X_*, _i^* )- _i( , _i^* ). Since (Xt,it)(X_t,i_t) maximizes the confidence width over t×[m]X_t×[m], for every X∈tX _t and every i∈[m]i∈[m], ct,i(X)≤ct,it(Xt).c_t,i(X)≤ c_t,i_t(X_t). Let Wi:=2+4w+⋯+4wi−1.W_i:=2+4w+·s+4w^i-1. Then the filtering rule in Algorithm 3 can be written as ti=X∈ti−1:y^t,i(Xt,i)−y^t,i(X)≤Wict,it(Xt).X_t^i= \X _t^i-1: y_t,i(X_t,i)- y_t,i(X)≤ W_ic_t,i_t(X_t) \. Note that Wi+2=4(1+w+⋯+wi−1)=4WilexW_i+2=4(1+w+·s+w^i-1)=4W_i lex. We prove the result by induction over the objective index i. For i=1i=1, since X∗X_* is lexicographically optimal, it maximizes the first objective. Hence, for any X∈tX _t, μ1(⟨X∗,Θ1∗⟩)≥μ1(⟨X,Θ1∗⟩). _1( X_*, _1^* )≥ _1( , _1^* ). In particular, μ1(⟨X∗,Θ1∗⟩)≥μ1(⟨Xt,1,Θ1∗⟩). _1( X_*, _1^* )≥ _1( _t,1, _1^* ). Using the confidence event, we obtain y^t,1(Xt,1)−y^t,1(X∗) y_t,1(X_t,1)- y_t,1(X_*) ≤μ1(⟨Xt,1,Θ1∗⟩)−μ1(⟨X∗,Θ1∗⟩)+ct,1(Xt,1)+ct,1(X∗) ≤ _1( _t,1, _1^* )- _1( X_*, _1^* )+c_t,1(X_t,1)+c_t,1(X_*) ≤2ct,it(Xt). ≤ 2c_t,i_t(X_t). Since W1=2W_1=2, this implies X∗∈t1X_* _t^1. Moreover, for any X∈t1X _t^1, Δ1(X) _1(X) =μ1(⟨X∗,Θ1∗⟩)−μ1(⟨X,Θ1∗⟩) = _1( X_*, _1^* )- _1( , _1^* ) ≤y^t,1(X∗)−y^t,1(X)+2ct,it(Xt) ≤ y_t,1(X_*)- y_t,1(X)+2c_t,i_t(X_t) ≤y^t,1(Xt,1)−y^t,1(X)+2ct,it(Xt) ≤ y_t,1(X_t,1)- y_t,1(X)+2c_t,i_t(X_t) ≤W1ct,it(Xt)+2ct,it(Xt) ≤ W_1c_t,i_t(X_t)+2c_t,i_t(X_t) =4ct,it(Xt)=4W1lexct,it(Xt). =4c_t,i_t(X_t)=4W_1 lexc_t,i_t(X_t). Thus the claim holds for i=1i=1. Now suppose the claim holds for all objectives j<ij<i. Since the candidate sets are nested, ti−1⊆tj,∀j<i.X_t^i-1 _t^j, ∀ j<i. Thus, for every X∈ti−1X _t^i-1 and every j<ij<i, Δj(X)≤4Wjlexct,it(Xt)≤4Wi−1lexct,it(Xt). _j(X)≤ 4W_j lexc_t,i_t(X_t)≤ 4W_i-1 lexc_t,i_t(X_t). We first show that X∗∈tiX_* _t^i. Since Xt,i∈ti−1X_t,i _t^i-1, Assumption 5 gives μi(⟨Xt,i,Θi∗⟩)−μi(⟨X∗,Θi∗⟩) _i( _t,i, _i^* )- _i( X_*, _i^* ) ≤wmaxj∈[i−1]μj(⟨X∗,Θj∗⟩)−μj(⟨Xt,i,Θj∗⟩) ≤ w _j∈[i-1] \ _j( X_*, _j^* )- _j( _t,i, _j^* ) \ =wmaxj∈[i−1]Δj(Xt,i)≤4wWi−1lexct,it(Xt). =w _j∈[i-1] _j(X_t,i)≤ 4wW_i-1 lexc_t,i_t(X_t). Therefore, by the confidence event, y^t,i(Xt,i)−y^t,i(X∗) y_t,i(X_t,i)- y_t,i(X_*) ≤μi(⟨Xt,i,Θi∗⟩)−μi(⟨X∗,Θi∗⟩)+ct,i(Xt,i)+ct,i(X∗) ≤ _i( _t,i, _i^* )- _i( X_*, _i^* )+c_t,i(X_t,i)+c_t,i(X_*) ≤4wWi−1lexct,it(Xt)+2ct,it(Xt) ≤ 4wW_i-1 lexc_t,i_t(X_t)+2c_t,i_t(X_t) =Wict,it(Xt). =W_ic_t,i_t(X_t). Hence X∗∈tiX_* _t^i. Next, for any X∈tiX _t^i, using the confidence event again gives Δi(X) _i(X) =μi(⟨X∗,Θi∗⟩)−μi(⟨X,Θi∗⟩) = _i( X_*, _i^* )- _i( , _i^* ) ≤y^t,i(X∗)−y^t,i(X)+2ct,it(Xt) ≤ y_t,i(X_*)- y_t,i(X)+2c_t,i_t(X_t) ≤y^t,i(Xt,i)−y^t,i(X)+2ct,it(Xt) ≤ y_t,i(X_t,i)- y_t,i(X)+2c_t,i_t(X_t) ≤Wict,it(Xt)+2ct,it(Xt) ≤ W_ic_t,i_t(X_t)+2c_t,i_t(X_t) =4Wilexct,it(Xt). =4W_i lexc_t,i_t(X_t). This completes the induction and the proof. □ Lemma 11 Suppose Assumption 5 holds. Let Wilex=1+w+⋯+wi−1.W_i lex=1+w+·s+w^i-1. With probability at least 1−δ1-δ, for every decision round t≥1t≥ 1, the lexicographically optimal arm satisfies X∗∈t.X_* _t. Moreover, for every t≥2t≥ 2 and every objective i∈[m]i∈[m], the arm XtX_t selected at round t satisfies μi(⟨X∗,Θi∗⟩)−μi(⟨Xt,Θi∗⟩)≤4Wilexct−1,it−1(Xt−1). _i\! ( _*, _i^* )- _i\! ( _t, _i^* )≤ 4W_i lexc_t-1,i_t-1(X_t-1). Proof. We first prove by induction on t that X∗∈tX_* _t. By initialization, 1=X_1=X, and hence X∗∈1X_* _1. Suppose that X∗∈tX_* _t for some t≥1t≥ 1. Since t0=tX_t^0=X_t, Lemma 10 implies that X∗∈tmX_* _t^m. By the candidate-set update t+1=tmX_t+1=X_t^m, we obtain X∗∈t+1X_* _t+1. Thus, X∗X_* belongs to tX_t for every t≥1t≥ 1. Next, for every t≥2t≥ 2, Algorithm 3 selects XtX_t from tX_t. Since t=t−1mX_t=X_t-1^m, we have Xt∈t−1mX_t _t-1^m. Applying Lemma 10 at round t−1t-1 gives, for every i∈[m]i∈[m], μi(⟨X∗,Θi∗⟩)−μi(⟨Xt,Θi∗⟩)≤4Wilexct−1,it−1(Xt−1). _i\! ( _*, _i^* )- _i\! ( _t, _i^* )≤ 4W_i lexc_t-1,i_t-1(X_t-1). This completes the proof. □ Step 3: Regret accumulation and objective-wise potentials. We now combine the regret incurred during the initial subspace exploration phase with that accumulated during the subsequent online decision phase. Since the reward of each objective is bounded in absolute value by U, the first T1T_1 rounds contribute at most 2UT12UT_1 to the regret. The first round of the online decision phase contributes at most 2U2U, while the remaining T2−1T_2-1 rounds, where T2=T−T1T_2=T-T_1, are controlled by Lemma 11. Therefore, Ri(T) R_i(T) =∑t=1T(μi(⟨X∗,Θi∗⟩)−μi(⟨Xt,Θi∗⟩)) = _t=1^T ( _i\! ( _*, _i^* )- _i\! ( _t, _i^* ) ) ≤2UT1+2U+∑t=2T24Wilexct−1,it−1(Xt−1) ≤ 2UT_1+2U+ _t=2^T_24W_i lexc_t-1,i_t-1(X_t-1) =2UT1+2U+∑s=1T2−14Wilexcs,is(Xs) =2UT_1+2U+ _s=1^T_2-14W_i lexc_s,i_s(X_s) ≤2UT1+2U+4WilexβTT2−1∑s=1T2−1‖fis(Xs)‖Vs,is−12, ≤ 2UT_1+2U+4W_i lex _T T_2-1 _s=1^T_2-1\|f_i_s(X_s)\|_V_s,i_s^-1^2, (19) where the last inequality follows from the monotonicity of βtt≥1\ _t\_t≥ 1 and the Cauchy–Schwarz inequality. Next, for each fixed objective, the standard elliptical-potential argument [Abbasi-yadkori et al., 2011, Lemma 11] gives ∑t=1T2‖fi(Xt)‖Vt,i−12≤4cμlogdet(VT2+1,i)det(Λ). _t=1^T_2\|f_i(X_t)\|_V_t,i^-1^2≤ 4c_μ (V_T_2+1,i) ( ). Applying Lemma C.5 of Kang et al. [2022], using λ0≥cμ/2 _0≥ c_μ/2 and log(1+x)≤x (1+x)≤ x, therefore yields ∑t=1T2‖fi(Xt)‖Vt,i−12≤4cμ(klog(1+Tk)+cμT2λ⟂). _t=1^T_2\|f_i(X_t)\|_V_t,i^-1^2≤ 4c_μ (k (1+ Tk )+ c_μT2 _ ). (20) Because the selected objective isi_s may vary across rounds, we partition the elliptical norms according to the selected objective. Applying (20) separately to each objective gives ∑s=1T2−1‖fis(Xs)‖Vs,is−12 _s=1^T_2-1\|f_i_s(X_s)\|_V_s,i_s^-1^2 =∑j=1m∑s∈[T2−1]is=j‖fj(Xs)‖Vs,j−12 = _j=1^m _ subarraycs∈[T_2-1]\\ i_s=j subarray\|f_j(X_s)\|_V_s,j^-1^2 (21) ≤∑j=1m∑s=1T2−1‖fj(Xs)‖Vs,j−12 ≤ _j=1^m _s=1^T_2-1\|f_j(X_s)\|_V_s,j^-1^2 ≤4mcμ(klog(1+Tk)+cμT2λ⟂). ≤ 4mc_μ (k (1+ Tk )+ c_μT2 _ ). Substituting (21) into (19) yields Ri(T) R_i(T) ≤2UT1+2U+8WilexβTm(T2−1)(kcμlog(1+Tk)+T2λ⟂) ≤ 2UT_1+2U+8W_i lex _T m(T_2-1) ( kc_μ (1+ Tk )+ T2 _ ) Step 4: Parameter choice and completion of the proof. We now substitute the choices of T1T_1, λ⟂ _ , and S⟂S_ into the regret bound for Lexi-LowGLM. Let A:=M(d1+d2)rDrr2log(m(d1+d2)δ).A:= M(d_1+d_2)rD_r^2 ( m(d_1+d_2)δ ). Then the prescribed exploration length and the tail-coordinate bound satisfy T1≍M(d1+d2)rTlog((d1+d2)m/δ)Drr=AT,S⟂=(d1+d2)MrT1Drr2log(m(d1+d2)δ)≍AT.T_1 M(d_1+d_2)rT ((d_1+d_2)m/δ)D_r= AT, S_ = (d_1+d_2)MrT_1D_r^2 ( m(d_1+d_2)δ ) AT. Recall that λ⟂=cμTklog(1+cμT/(kλ0)). _ = c_μTk \! (1+c_μT/(k _0) ). Hence, cμT2λ⟂=k2log(1+cμTkλ0) and T2λ⟂=k2cμlog(1+cμTkλ0). c_μT2 _ = k2 \! (1+ c_μTk _0 ) and T2 _ = k2c_μ \! (1+ c_μTk _0 ). Therefore, kcμlog(1+Tk)+T2λ⟂=O~(kcμ). kc_μ (1+ Tk )+ T2 _ = O ( kc_μ ). Next, by the definition of βT+1 _T+1, βT+1=Lμ(4(U+R)cμklog(1+Tk)+cμT2λ⟂+log(m1+4S2Tδ)+cμ2+λ0S+λ⟂S⟂). _T+1=L_μ ( 4(U+R) c_μ k (1+ Tk )+ c_μT2 _ + ( m 1+4S^2Tδ )+ c_μ2+ _0S+ _ S_ ). Using the above expression of λ⟂ _ , we obtain klog(1+Tk)+cμT2λ⟂+log(m1+4S2Tδ)=O~(k). k (1+ Tk )+ c_μT2 _ + ( m 1+4S^2Tδ )= O( k). Furthermore, λ⟂S⟂=cμTklog(1+cμT/(kλ0))⋅AT=O~(cμAk). _ S_ = c_μTk (1+c_μT/(k _0))· AT= O ( c_μAk ). Thus, βT+1=O~(Lμ((U+R)kcμ+cμ+λ0S+cμAk)). _T+1= O (L_μ ( (U+R) k c_μ+ c_μ+ _0S+ c_μAk ) ). Since βt _t is nondecreasing in t, we use βT≤βT+1 _T≤ _T+1. Combining the above estimates and using T2−1≤T2≤T T_2-1≤ T_2≤ T, we get Ri(T) R_i(T) ≤2UT1+2U+8WilexβTmT2kcμlog(1+Tk)+T2λ⟂ ≤ 2UT_1+2U+8W_i lex _T mT_2 kc_μ (1+ Tk )+ T2 _ =O~(UAT+WilexmLμ((U+R)kcμ+k+Sλ0kcμ+A)T). = O (U AT+W_i lex mL_μ ( (U+R)kc_μ+ k+S _0kc_μ+ A ) T ). Substituting the definition of A, we obtain Ri(T)=O~([ R_i(T)= O ( [ UM(d1+d2)rDrr+WilexmLμ((U+R)kcμ+k+Sλ0kcμ+M(d1+d2)rDrr)]T). U M(d_1+d_2)rD_r+W_i lex mL_μ ( (U+R)kc_μ+ k+S _0kc_μ+ M(d_1+d_2)rD_r ) ] T ). When U,R,Lμ,cμ,λ0U,R,L_μ,c_μ, _0, and S are treated as constants, and since Wilex≥1W_i lex≥ 1, this simplifies to Ri(T)=O~(Wilexm(k+M(d1+d2)rDrr)T).R_i(T)= O (W_i lex m (k+ M(d_1+d_2)rD_r ) T ). Finally, since k=(d1+d2)r−r2≍(d1+d2)rk=(d_1+d_2)r-r^2 (d_1+d_2)r and M(d1+d2)rDrr≲(d1+d2)r, M(d_1+d_2)rD_r (d_1+d_2)r, we obtain Ri(T)=O~(Wilexm(d1+d2)rT).R_i(T)= O (W_i lex m\,(d_1+d_2)r T ). The proof of Theorem 2 is finished. □