Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits

# Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits
Source: [https://arxiv.org/html/2608.04324](https://arxiv.org/html/2608.04324)
22footnotetext:Corresponding AuthorBo 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 proposeLexi\-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\-LowGLMupdates each objective\-specific estimator via an online Newton step, reducing the estimator\-update complexity overTTrounds fromO​\(T2\)O\(T^\{2\}\)toO​\(T\)O\(T\)\. We establish a regret bound ofO~​\(Wilex​m​\(d1\+d2\)​r​T\)\\widetilde\{O\}\\left\(W\_\{i\}^\{\\rm lex\}\\sqrt\{m\}\\,\(d\_\{1\}\+d\_\{2\}\)r\\sqrt\{T\}\\right\)for each objectivei∈\[m\]i\\in\[m\], whererris an upper bound on the ranks of the objective\-specific parameter matrices andWilexW\_\{i\}^\{\\rm lex\}characterizes the lexicographic trade\-off effect\. This bound depends on the effective low\-rank dimension\(d1\+d2\)​r\(d\_\{1\}\+d\_\{2\}\)rrather than the ambient dimensiond1​d2d\_\{1\}d\_\{2\}\. Numerical experiments further validate the effectiveness and computational efficiency of the proposed method\.

## 1Introduction

Contextual bandits provide a fundamental framework for sequential decision\-making under uncertainty\(Robbins,[1952](https://arxiv.org/html/2608.04324#bib.bib14); Lai and Robbins,[1985](https://arxiv.org/html/2608.04324#bib.bib31); Auer,[2002](https://arxiv.org/html/2608.04324#bib.bib10)\), with widespread applications in personalized recommendation\(Liet al\.,[2010](https://arxiv.org/html/2608.04324#bib.bib17)\), online advertising\(Schwartzet al\.,[2017](https://arxiv.org/html/2608.04324#bib.bib125)\), and resource allocation\(Khansaet al\.,[2021](https://arxiv.org/html/2608.04324#bib.bib126)\)\. 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\(Junet al\.,[2019](https://arxiv.org/html/2608.04324#bib.bib265); Kanget al\.,[2022](https://arxiv.org/html/2608.04324#bib.bib268)\)\. Although matrix\-valued actions can be vectorized and handled using standard bandit algorithms\(Daniet al\.,[2008](https://arxiv.org/html/2608.04324#bib.bib40); Filippiet al\.,[2010](https://arxiv.org/html/2608.04324#bib.bib56)\), 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\(Junet al\.,[2019](https://arxiv.org/html/2608.04324#bib.bib265)\)\. Specifically, the expected reward of an armX∈ℝd1×d2\\mathrm\{X\}\\in\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}is modeled asμ​\(⟨X,Θ∗⟩\)\\mu\(\\langle\\mathrm\{X\},\\Theta^\{\*\}\\rangle\), whereμ​\(⋅\)\\mu\(\\cdot\)is an inverse link function andΘ∗\\Theta^\{\*\}is an unknown rankrrmatrix\. By exploiting the row and column subspaces ofΘ∗\\Theta^\{\*\}, 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 dimensiond1​d2d\_\{1\}d\_\{2\}\(Janget al\.,[2021](https://arxiv.org/html/2608.04324#bib.bib266); Luet al\.,[2021](https://arxiv.org/html/2608.04324#bib.bib267)\)\. However, existing generalized low\-rank matrix bandit algorithms are mainly developed for scalar rewards\(Kanget al\.,[2024](https://arxiv.org/html/2608.04324#bib.bib271); Wanget al\.,[2025](https://arxiv.org/html/2608.04324#bib.bib269)\), 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\(Jeeet al\.,[2007](https://arxiv.org/html/2608.04324#bib.bib102)\)\. 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\(Weberet al\.,[2002](https://arxiv.org/html/2608.04324#bib.bib103)\)\. These examples motivate the use of lexicographic preferences\(Ehrgott,[2005](https://arxiv.org/html/2608.04324#bib.bib70)\), 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](https://arxiv.org/html/2608.04324#bib.bib111); Hüyük and Tekin,[2021](https://arxiv.org/html/2608.04324#bib.bib71); Xueet al\.,[2025b](https://arxiv.org/html/2608.04324#bib.bib6)\), 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 dimensiond1​d2d\_\{1\}d\_\{2\}, thereby losing the advantages of low\-rank modeling\. Conversely, existing generalized low\-rank matrix bandit algorithms primarily focus on scalar rewards\(Kanget al\.,[2022](https://arxiv.org/html/2608.04324#bib.bib268)\)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\(Kanget al\.,[2022](https://arxiv.org/html/2608.04324#bib.bib268)\)\. Although this approach facilitates theoretical analysis, it repeatedly processes past data and incurs a cumulative estimator\-update complexity ofO​\(T2\)O\(T^\{2\}\)overTTrounds, 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 proposeLexi\-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\-LowGLMreduces the cumulative estimator\-update complexity overTTrounds fromO​\(T2\)O\(T^\{2\}\)toO​\(T\)O\(T\)\.
- •Regret guarantee\.We establish an objective\-wise regret bound forLexi\-LowGLM\. Specifically, for each objectivei∈\[m\]i\\in\[m\], the regret scales asO~​\(Wilex​m​\(d1\+d2\)​r​T\)\\widetilde\{O\}\(W\_\{i\}^\{\\rm lex\}\\sqrt\{m\}\\,\(d\_\{1\}\+d\_\{2\}\)r\\sqrt\{T\}\), whereWilex=1\+w\+⋯\+wi−1W\_\{i\}^\{\\rm lex\}=1\+w\+\\cdots\+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\(Kanget al\.,[2022](https://arxiv.org/html/2608.04324#bib.bib268)\), while simultaneously controlling the regret of all objectives\. Whenw=0w=0, we haveWilex=1W\_\{i\}^\{\\rm lex\}=1for alli∈\[m\]i\\in\[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\.

## 2Related Work

In this section, we review related work on matrix bandits and multi\-objective bandits\.

#### Matrix Bandits\.

Matrix bandits extend contextual linear bandits\(Abbasi\-yadkoriet al\.,[2011](https://arxiv.org/html/2608.04324#bib.bib26); Chuet al\.,[2011](https://arxiv.org/html/2608.04324#bib.bib19)\)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\.Junet al\.\([2019](https://arxiv.org/html/2608.04324#bib.bib265)\)introduced bilinear bandits and proposed an explore\-subspace\-then\-refine strategy\. Subsequent works improved this line by leveraging the geometry of the action space\(Janget al\.,[2021](https://arxiv.org/html/2608.04324#bib.bib266)\), studying pure exploration with shared representations\(Mukherjeeet al\.,[2023](https://arxiv.org/html/2608.04324#bib.bib273)\), and developing robust algorithms under heavy\-tailed rewards\(Kanget al\.,[2024](https://arxiv.org/html/2608.04324#bib.bib271)\)\.

More recent works consider generalized low\-rank matrix bandits, where the expected reward follows a generalized linear model\.Luet al\.\([2021](https://arxiv.org/html/2608.04324#bib.bib267)\)studied this problem beyond the bilinear setting, but their covering\-based algorithm can be computationally expensive\.Kanget al\.\([2022](https://arxiv.org/html/2608.04324#bib.bib268)\)improved computational tractability through Stein\-type subspace estimation and low\-rank generalized linear bandit learning\. Other extensions further exploit arm\-set geometry\(Janget al\.,[2024](https://arxiv.org/html/2608.04324#bib.bib272)\), graph information\(Wanget al\.,[2025](https://arxiv.org/html/2608.04324#bib.bib269)\), or low\-rank structures in related feedback models\(Leeet al\.,[2026](https://arxiv.org/html/2608.04324#bib.bib270)\)\. 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](https://arxiv.org/html/2608.04324#bib.bib68)\)\.Busa\-Feketeet al\.\([2017](https://arxiv.org/html/2608.04324#bib.bib276)\)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](https://arxiv.org/html/2608.04324#bib.bib275)\)\. 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\(Turgayet al\.,[2018](https://arxiv.org/html/2608.04324#bib.bib72); Luet al\.,[2019](https://arxiv.org/html/2608.04324#bib.bib47); Caiet al\.,[2023](https://arxiv.org/html/2608.04324#bib.bib162)\), and recent work further developed Pareto regret analysis for both stochastic and adversarial multi\-objective MABs\(Xu and Klabjan,[2023](https://arxiv.org/html/2608.04324#bib.bib114); Parket al\.,[2025](https://arxiv.org/html/2608.04324#bib.bib274)\)\. Related pure\-exploration studies aim to identify the Pareto front with sample\-complexity guarantees\(Aueret al\.,[2016](https://arxiv.org/html/2608.04324#bib.bib69); Creponet al\.,[2024](https://arxiv.org/html/2608.04324#bib.bib223)\)\. Moreover, recent studies on multi\-objective reinforcement learning with bandit feedback\(Qiuet al\.,[2024](https://arxiv.org/html/2608.04324#bib.bib3)\)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](https://arxiv.org/html/2608.04324#bib.bib71)\), contextual bandits\(Tekin and Turgay,[2018](https://arxiv.org/html/2608.04324#bib.bib111)\), and stochastic linear bandits\(Xueet al\.,[2025b](https://arxiv.org/html/2608.04324#bib.bib6)\)\. Related lexicographic preference models have also been explored in reinforcement learning \(RL\), including lexicographic multi\-objective RL\(Skalseet al\.,[2022](https://arxiv.org/html/2608.04324#bib.bib117); Alperen Tercan,[2024](https://arxiv.org/html/2608.04324#bib.bib277)\)and lexicographic linear MDPs\(Xueet al\.,[2025a](https://arxiv.org/html/2608.04324#bib.bib7)\)\. However, these methods do not consider low\-rank matrix structures\.

## 3Preliminaries

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,\\ldots,n\\\}for any positive integernn\. Given a vectorx∈ℝdx\\in\\mathbb\{R\}^\{d\},‖x‖2\\\|x\\\|\_\{2\}denotes its Euclidean norm, and for a positive definite matrixV∈ℝd×d\\mathrm\{V\}\\in\\mathbb\{R\}^\{d\\times d\}, its weighted norm is‖x‖V=x⊤​V​x\\\|x\\\|\_\{\\mathrm\{V\}\}=\\sqrt\{x^\{\\top\}\\mathrm\{V\}x\}\. For a matrixA∈ℝd1×d2\\mathrm\{A\}\\in\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\},‖A‖F\\\|\\mathrm\{A\}\\\|\_\{F\},‖A‖op\\\|\\mathrm\{A\}\\\|\_\{\\mathrm\{op\}\}, and‖A‖nuc\\\|\\mathrm\{A\}\\\|\_\{\\mathrm\{nuc\}\}denote its Frobenius norm, operator norm, and nuclear norm, respectively\. The inner product between two matricesA,B∈ℝd1×d2\\mathrm\{A\},\\mathrm\{B\}\\in\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}is defined as⟨A,B⟩=trace⁡\(A⊤​B\)\\langle\\mathrm\{A\},\\mathrm\{B\}\\rangle=\\operatorname\{trace\}\(\\mathrm\{A\}^\{\\top\}\\mathrm\{B\}\)\.vec⁡\(A\)\\operatorname\{vec\}\(\\mathrm\{A\}\)denotes the vectorization ofA\\mathrm\{A\}obtained by stacking its columns, andO~​\(⋅\)\\widetilde\{O\}\(\\cdot\)hides logarithmic factors\.

#### Learning Model\.

Lexicographic generalized low\-rank matrix bandits consider aTT\-round sequential decision\-making problem\. At each roundt∈\[T\]t\\in\[T\], the learner first observes the arm set𝒳⊆ℝd1×d2\\mathcal\{X\}\\subseteq\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}, selects an armXt∈𝒳\\mathrm\{X\}\_\{t\}\\in\\mathcal\{X\}, and then receives a stochastic reward vectoryt=\(yt,1,…,yt,m\)∈ℝmy\_\{t\}=\(y\_\{t,1\},\\ldots,y\_\{t,m\}\)\\in\\mathbb\{R\}^\{m\}, wheremmis the number of objectives\. For each objectivei∈\[m\]i\\in\[m\], the expected reward is modeled by an objective\-specific generalized low\-rank matrix model:

E​\[yt,i∣Xt\]=μi​\(⟨Xt,Θi∗⟩\),\\mathrm\{E\}\[y\_\{t,i\}\\mid\\mathrm\{X\}\_\{t\}\]=\\mu\_\{i\}\\\!\\left\(\\left\\langle\\mathrm\{X\}\_\{t\},\\Theta\_\{i\}^\{\*\}\\right\\rangle\\right\),whereμi​\(⋅\)\\mu\_\{i\}\(\\cdot\)is an inverse link function, andΘi∗∈ℝd1×d2\\Theta\_\{i\}^\{\*\}\\in\\mathbb\{R\}^\{d\_\{1\}\\times 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\}=\\mu\_\{i\}\\\!\\left\(\\left\\langle\\mathrm\{X\}\_\{t\},\\Theta\_\{i\}^\{\*\}\\right\\rangle\\right\)\+\\eta\_\{t,i\},i\\in\[m\],whereηt,i\\eta\_\{t,i\}is zero\-mean noise\.

#### Lexicographic Preference and Regret\.

For any two armsX,X′∈𝒳\\mathrm\{X\},\\mathrm\{X\}^\{\\prime\}\\in\\mathcal\{X\}, we say thatX\\mathrm\{X\}*lexicographically dominates*X′\\mathrm\{X\}^\{\\prime\}if there exists an objective indexi∈\[m\]i\\in\[m\]such that

μj​\(⟨X,Θj∗⟩\)\\displaystyle\\mu\_\{j\}\\\!\\left\(\\left\\langle\\mathrm\{X\},\\Theta\_\{j\}^\{\*\}\\right\\rangle\\right\)=μj​\(⟨X′,Θj∗⟩\),∀j∈\[i−1\],\\displaystyle=\\mu\_\{j\}\\\!\\left\(\\left\\langle\\mathrm\{X\}^\{\\prime\},\\Theta\_\{j\}^\{\*\}\\right\\rangle\\right\),\\forall j\\in\[i\-1\],μi​\(⟨X,Θi∗⟩\)\\displaystyle\\mu\_\{i\}\\\!\\left\(\\left\\langle\\mathrm\{X\},\\Theta\_\{i\}^\{\*\}\\right\\rangle\\right\)\>μi​\(⟨X′,Θi∗⟩\)\.\\displaystyle\>\\mu\_\{i\}\\\!\\left\(\\left\\langle\\mathrm\{X\}^\{\\prime\},\\Theta\_\{i\}^\{\*\}\\right\\rangle\\right\)\.An armX∗∈𝒳\\mathrm\{X\}\_\{\*\}\\in\\mathcal\{X\}is*lexicographically optimal*if it is not lexicographically dominated by any other arm in𝒳\\mathcal\{X\}\.

We evaluate the performance of the learner using the objective\-wise cumulative regret with respect to the lexicographically optimal armX∗\\mathrm\{X\}\_\{\*\}\. Specifically, for each objectivei∈\[m\]i\\in\[m\], the cumulative regret is defined as

Ri​\(T\)=∑t=1T\[μi​\(⟨X∗,Θi∗⟩\)−μi​\(⟨Xt,Θi∗⟩\)\]\.R\_\{i\}\(T\)=\\sum\_\{t=1\}^\{T\}\\left\[\\mu\_\{i\}\\\!\\left\(\\left\\langle\\mathrm\{X\}\_\{\*\},\\Theta\_\{i\}^\{\*\}\\right\\rangle\\right\)\-\\mu\_\{i\}\\\!\\left\(\\left\\langle\\mathrm\{X\}\_\{t\},\\Theta\_\{i\}^\{\*\}\\right\\rangle\\right\)\\right\]\.This quantity measures the cumulative loss on objectiveiiincurred by selectingXt\\mathrm\{X\}\_\{t\}instead of the lexicographically optimal armX∗\\mathrm\{X\}\_\{\*\}\. The goal is to design an algorithm that achieves sublinear growth ofRi​\(T\)R\_\{i\}\(T\)for every objectivei∈\[m\]i\\in\[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\(Kanget al\.,[2024](https://arxiv.org/html/2608.04324#bib.bib271); Wanget al\.,[2025](https://arxiv.org/html/2608.04324#bib.bib269)\)and lexicographic bandit learning\(Xueet al\.,[2025b](https://arxiv.org/html/2608.04324#bib.bib6)\)\.

###### Assumption 1\(Low\-rank structure\)

For each objectivei∈\[m\]i\\in\[m\], the unknown parameter matrixΘi∗\\Theta\_\{i\}^\{\*\}is of rank at mostrr, i\.e\.,rank⁡\(Θi∗\)≤r\\operatorname\{rank\}\(\\Theta\_\{i\}^\{\*\}\)\\leq r, wherer≪min⁡\{d1,d2\}r\\ll\\min\\\{d\_\{1\},d\_\{2\}\\\}\.

###### Assumption 2\(Bounded parameters and arms\)

There exists a constantS\>0S\>0such that‖Θi∗‖F≤S\\\|\\Theta\_\{i\}^\{\*\}\\\|\_\{F\}\\leq Sfor alli∈\[m\]i\\in\[m\]\. The arm set is normalized so that‖X‖F≤1\\\|\\mathrm\{X\}\\\|\_\{F\}\\leq 1for allX∈𝒳\\mathrm\{X\}\\in\\mathcal\{X\}\.

###### Assumption 3\(Regular link functions\)

For each objectivei∈\[m\]i\\in\[m\], the inverse link functionμi​\(⋅\)\\mu\_\{i\}\(\\cdot\)is continuously differentiable\. There exist constants0<cμ≤Lμ0<c\_\{\\mu\}\\leq L\_\{\\mu\}such that, over the relevant domain,cμ≤μi′​\(z\)≤Lμ,∀i∈\[m\]c\_\{\\mu\}\\leq\\mu^\{\\prime\}\_\{i\}\(z\)\\leq L\_\{\\mu\},\\forall i\\in\[m\]\.

###### Assumption 4\(Bounded rewards and noise\)

There exist constantsU,R\>0U,R\>0such that\|μi​\(z\)\|≤U\|\\mu\_\{i\}\(z\)\|\\leq Uover the relevant domain and\|yt,i−μi​\(⟨Xt,Θi∗⟩\)\|≤R,∀t∈\[T\],i∈\[m\]\\left\|y\_\{t,i\}\-\\mu\_\{i\}\\\!\\left\(\\left\\langle\\mathrm\{X\}\_\{t\},\\Theta\_\{i\}^\{\*\}\\right\\rangle\\right\)\\right\|\\leq R,\\forall t\\in\[T\],\\ i\\in\[m\]\.

###### Assumption 5\(Lexicographic trade\-off\)

There existsw≥0w\\geq 0such that, for everyi∈\{2,…,m\}i\\in\\\{2,\\ldots,m\\\}and anyX∈𝒳\\mathrm\{X\}\\in\\mathcal\{X\},

μi​\(⟨X,Θi∗⟩\)−μi​\(⟨X∗,Θi∗⟩\)\\displaystyle\\qquad\\mu\_\{i\}\\left\(\\left\\langle\\mathrm\{X\},\\Theta\_\{i\}^\{\*\}\\right\\rangle\\right\)\-\\mu\_\{i\}\\left\(\\left\\langle\\mathrm\{X\}\_\{\*\},\\Theta\_\{i\}^\{\*\}\\right\\rangle\\right\)≤w⋅maxj∈\[i−1\]⁡\{μj​\(⟨X∗,Θj∗⟩\)−μj​\(⟨X,Θj∗⟩\)\}\.\\displaystyle\\leq w\\cdot\\max\_\{j\\in\[i\-1\]\}\\left\\\{\\mu\_\{j\}\\left\(\\left\\langle\\mathrm\{X\}\_\{\*\},\\Theta\_\{j\}^\{\*\}\\right\\rangle\\right\)\-\\mu\_\{j\}\\left\(\\left\\langle\\mathrm\{X\},\\Theta\_\{j\}^\{\*\}\\right\\rangle\\right\)\\right\\\}\.

#### 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\(Kanget al\.,[2022](https://arxiv.org/html/2608.04324#bib.bib268)\)\.

Letp:ℝ→ℝp:\\mathbb\{R\}\\to\\mathbb\{R\}denote a univariate probability density function\. Its corresponding score function is defined by

Sp​\(x\)=−∇xlog⁡p​\(x\)=−∇xp​\(x\)p​\(x\),x∈ℝ\.S^\{p\}\(x\)=\-\\nabla\_\{x\}\\log p\(x\)=\-\\frac\{\\nabla\_\{x\}p\(x\)\}\{p\(x\)\},\\quad x\\in\\mathbb\{R\}\.For a random matrixA∈ℝd1×d2\\mathrm\{A\}\\in\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}with entrywise density𝐩=\(pi​j\):ℝd1×d2→ℝd1×d2\\mathbf\{p\}=\(p\_\{ij\}\):\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}\\to\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}, its score function is

S𝐩​\(A\)=\(Spi​j​\(Ai​j\)\)i,j∈ℝd1×d2\.S^\{\\mathbf\{p\}\}\(\\mathrm\{A\}\)=\\big\(S^\{p\_\{ij\}\}\(\\mathrm\{A\}\_\{ij\}\)\\big\)\_\{i,j\}\\in\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}\.When the underlying exploration distribution is clear from the context, we simply writeS​\(A\)S\(\\mathrm\{A\}\)\.

###### Assumption 6\(Exploration distribution\)

There exists a sampling distribution𝒟\\mathcal\{D\}over𝒳\\mathcal\{X\}such that, forX∼𝒟\\mathrm\{X\}\\sim\\mathcal\{D\}with associated entrywise density𝐩\\mathbf\{p\},E​\[\(S𝐩​\(X\)\)i​j2\]≤M,∀\(i,j\)∈\[d1\]×\[d2\]\.\\mathrm\{E\}\\\!\\left\[\\big\(S^\{\\mathbf\{p\}\}\(\\mathrm\{X\}\)\\big\)\_\{ij\}^\{2\}\\right\]\\leq M,\\forall\(i,j\)\\in\[d\_\{1\}\]\\times\[d\_\{2\}\]\.Moreover, either the rows or the columns ofX\\mathrm\{X\}are pairwise independent\.

We also introduce the Hermitian dilation operator\. For any matrixA∈ℝd1×d2\\mathrm\{A\}\\in\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}, define

ℋ​\(A\)=\(0AA⊤0\)∈ℝ\(d1\+d2\)×\(d1\+d2\)\.\\mathcal\{H\}\(\\mathrm\{A\}\)=\\begin\{pmatrix\}0&\\mathrm\{A\}\\\\ \\mathrm\{A\}^\{\\top\}&0\\end\{pmatrix\}\\in\\mathbb\{R\}^\{\(d\_\{1\}\+d\_\{2\}\)\\times\(d\_\{1\}\+d\_\{2\}\)\}\.Moreover, for any real\-valued functiong:ℝ→ℝg:\\mathbb\{R\}\\to\\mathbb\{R\}and any symmetric matrixA=UDU⊤\\mathrm\{A\}=\\mathrm\{U\}\\mathrm\{D\}\\mathrm\{U\}^\{\\top\}, define

g​\(A\)=U​diag⁡\(g​\(D11\),…,g​\(Dd​d\)\)​U⊤\.g\(\\mathrm\{A\}\)=\\mathrm\{U\}\\operatorname\{diag\}\\big\(g\(\\mathrm\{D\}\_\{11\}\),\\ldots,g\(\\mathrm\{D\}\_\{dd\}\)\\big\)\\mathrm\{U\}^\{\\top\}\.
To obtain a robust matrix estimator under the finite\-moment condition in Assumption[6](https://arxiv.org/html/2608.04324#Thmassume6), we use the truncation function

ψ​\(x\)=\{log⁡\(1\+x\+x2/2\),x≥0,−log⁡\(1−x\+x2/2\),x<0\.\\psi\(x\)=\\begin\{cases\}\\log\(1\+x\+x^\{2\}/2\),&x\\geq 0,\\\\ \-\\log\(1\-x\+x^\{2\}/2\),&x<0\.\\end\{cases\}Givenν\>0\\nu\>0, define the matrix\-valued truncation operator

ψ~ν​\(A\)=1ν​\[ψ​\(ν​ℋ​\(A\)\)\]1:d1,\(d1\+1\):\(d1\+d2\)\.\\widetilde\{\\psi\}\_\{\\nu\}\(\\mathrm\{A\}\)=\\frac\{1\}\{\\nu\}\\left\[\\psi\\big\(\\nu\\mathcal\{H\}\(\\mathrm\{A\}\)\\big\)\\right\]\_\{1:d\_\{1\},\\,\(d\_\{1\}\+1\):\(d\_\{1\}\+d\_\{2\}\)\}\.\(1\)Specifically,ψ~ν​\(⋅\)\\widetilde\{\\psi\}\_\{\\nu\}\(\\cdot\)first appliesψ​\(⋅\)\\psi\(\\cdot\)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\.

## 4Algorithms

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\(Kanget al\.,[2022](https://arxiv.org/html/2608.04324#bib.bib268)\), 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\.1Objective\-Specific Subspace Estimation

We begin by estimating the objective\-specific low\-rank row and column subspaces\. To this end, during the firstT1T\_\{1\}rounds, the learner samples arms independently from the exploration distribution𝒟\\mathcal\{D\}over𝒳\\mathcal\{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 objectivei∈\[m\]i\\in\[m\], define the empirical loss

LT1,i​\(Θ\)=⟨Θ,Θ⟩−2T1​∑t=1T1⟨ψ~ν​\(yt,i⋅S​\(Xt\)\),Θ⟩,L\_\{T\_\{1\},i\}\(\\Theta\)=\\langle\\Theta,\\Theta\\rangle\-\\frac\{2\}\{T\_\{1\}\}\\sum\_\{t=1\}^\{T\_\{1\}\}\\left\\langle\\tilde\{\\psi\}\_\{\\nu\}\\\!\\big\(y\_\{t,i\}\\cdot S\(\\mathrm\{X\}\_\{t\}\)\\big\),\\Theta\\right\\rangle,\(2\)whereS​\(Xt\)S\(\\mathrm\{X\}\_\{t\}\)is the score function associated with the exploration distribution𝒟\\mathcal\{D\}, andψ~ν​\(⋅\)\\widetilde\{\\psi\}\_\{\\nu\}\(\\cdot\)is the matrix\-valued truncation operator defined in Eq\. \([1](https://arxiv.org/html/2608.04324#S3.E1)\)\.

The objective\-specific estimator is then obtained by solving the nuclear\-norm regularized optimization problem

Θ^i=arg⁡minΘ∈ℝd1×d2⁡\{LT1,i​\(Θ\)\+λT1​‖Θ‖nuc\},\\widehat\{\\Theta\}\_\{i\}=\\arg\\min\_\{\\Theta\\in\\mathbb\{R\}^\{d\_\{1\}\\times d\_\{2\}\}\}\\left\\\{L\_\{T\_\{1\},i\}\(\\Theta\)\+\\lambda\_\{T\_\{1\}\}\\\|\\Theta\\\|\_\{\\mathrm\{nuc\}\}\\right\\\},\(3\)where the nuclear norm promotes low\-rank structure\. We set

ν=2​log⁡\(2​m​\(d1\+d2\)/δ\)\(4​R2\+U2\)​M​T1​\(d1\+d2\)\\nu=\\sqrt\{\\frac\{2\\log\(2m\(d\_\{1\}\+d\_\{2\}\)/\\delta\)\}\{\(4R^\{2\}\+U^\{2\}\)MT\_\{1\}\(d\_\{1\}\+d\_\{2\}\)\}\}and

λT1=4​2​\(4​R2\+U2\)​M​\(d1\+d2\)​log⁡\(2​m​\(d1\+d2\)/δ\)T1\.\\lambda\_\{T\_\{1\}\}=4\\sqrt\{\\frac\{2\(4R^\{2\}\+U^\{2\}\)M\(d\_\{1\}\+d\_\{2\}\)\\log\(2m\(d\_\{1\}\+d\_\{2\}\)/\\delta\)\}\{T\_\{1\}\}\}\.After computingΘ^i\\widehat\{\\Theta\}\_\{i\}, we take its singular value decomposition

Θ^i=\[U^i,U^i,⟂\]​D^i​\[V^i,V^i,⟂\]⊤,\\widehat\{\\Theta\}\_\{i\}=\[\\widehat\{\\mathrm\{U\}\}\_\{i\},\\widehat\{\\mathrm\{U\}\}\_\{i,\\perp\}\]\\widehat\{\\mathrm\{D\}\}\_\{i\}\[\\widehat\{\\mathrm\{V\}\}\_\{i\},\\widehat\{\\mathrm\{V\}\}\_\{i,\\perp\}\]^\{\\top\},whereU^i\\widehat\{\\mathrm\{U\}\}\_\{i\}andV^i\\widehat\{\\mathrm\{V\}\}\_\{i\}contain the leadingrrleft and right singular vectors, respectively\. These matrices provide estimates of the objective\-specific row and column subspaces for constructing the transformed feature representations\.

Algorithm 1Objective\-Specific Subspace Estimation0:

𝒳,T1,r,𝒟,δ\\mathcal\{X\},T\_\{1\},r,\\mathcal\{D\},\\delta
1:for

t=1,2,…,T1t=1,2,\\ldots,T\_\{1\}do

2:Sample

Xt∼𝒟\\mathrm\{X\}\_\{t\}\\sim\\mathcal\{D\}and observe

yt=\(yt,1,…,yt,m\)y\_\{t\}=\(y\_\{t,1\},\\ldots,y\_\{t,m\}\)
3:endfor

4:for

i=1,2,…,mi=1,2,\\ldots,mdo

5:Define the loss function

LT1,i​\(Θ\)L\_\{T\_\{1\},i\}\(\\Theta\)as in Eq\. \([2](https://arxiv.org/html/2608.04324#S4.E2)\)

6:Compute

Θ^i\\widehat\{\\Theta\}\_\{i\}by solving Eq\. \([3](https://arxiv.org/html/2608.04324#S4.E3)\)

7:Compute the SVD

Θ^i=\[U^i,U^i,⟂\]​D^i​\[V^i,V^i,⟂\]⊤\\widehat\{\\Theta\}\_\{i\}=\[\\widehat\{\\mathrm\{U\}\}\_\{i\},\\widehat\{\\mathrm\{U\}\}\_\{i,\\perp\}\]\\,\\widehat\{\\mathrm\{D\}\}\_\{i\}\\,\[\\widehat\{\\mathrm\{V\}\}\_\{i\},\\widehat\{\\mathrm\{V\}\}\_\{i,\\perp\}\]^\{\\top\}
8:Define the transformed feature map

fi​\(⋅\)f\_\{i\}\(\\cdot\)as in Eq\. \([4](https://arxiv.org/html/2608.04324#S4.E4)\)

9:endfor

10:return

\{fi​\(⋅\)\}i=1m\\\{f\_\{i\}\(\\cdot\)\\\}\_\{i=1\}^\{m\}

#### Transformed Feature Representation\.

For each objectivei∈\[m\]i\\in\[m\], define the rotation operator

ℛi​\(A\):=\[U^i,U^i,⟂\]⊤​A​\[V^i,V^i,⟂\]\.\\mathcal\{R\}\_\{i\}\(\\mathrm\{A\}\):=\[\\widehat\{\\mathrm\{U\}\}\_\{i\},\\widehat\{\\mathrm\{U\}\}\_\{i,\\perp\}\]^\{\\top\}\\mathrm\{A\}\[\\widehat\{\\mathrm\{V\}\}\_\{i\},\\widehat\{\\mathrm\{V\}\}\_\{i,\\perp\}\]\.The rotated matrix is then partitioned according to the estimated rank\-rrrow 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\)\],\\Pi\_\{r\}\(\\mathrm\{A\}\):=\\begin\{bmatrix\}\\operatorname\{vec\}\(\\mathrm\{A\}\_\{1:r,\\,1:r\}\)\\\\ \\operatorname\{vec\}\(\\mathrm\{A\}\_\{r\+1:d\_\{1\},\\,1:r\}\)\\\\ \\operatorname\{vec\}\(\\mathrm\{A\}\_\{1:r,\\,r\+1:d\_\{2\}\}\)\\\\ \\operatorname\{vec\}\(\\mathrm\{A\}\_\{r\+1:d\_\{1\},\\,r\+1:d\_\{2\}\}\)\\end\{bmatrix\},which vectorizes the four resulting blocks\. The transformed feature map for objectiveiiis therefore given by

fi​\(X\):=Πr​\(ℛi​\(X\)\)\.f\_\{i\}\(\\mathrm\{X\}\):=\\Pi\_\{r\}\\\!\\big\(\\mathcal\{R\}\_\{i\}\(\\mathrm\{X\}\)\\big\)\.\(4\)The firstk=\(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\.2Scalarized Batch Method:Scalar\-LowGLM

Algorithm[2](https://arxiv.org/html/2608.04324#alg2)presents a natural baseline that extends the single\-objective low\-rank matrix bandit algorithm\(Kanget al\.,[2022](https://arxiv.org/html/2608.04324#bib.bib268)\)to the multi\-objective setting\.

After estimating the objective\-specific low\-rank subspaces using Algorithm[1](https://arxiv.org/html/2608.04324#alg1), Algorithm[2](https://arxiv.org/html/2608.04324#alg2)performs bandit learning in the transformed feature spaces\{fi​\(X\):X∈𝒳\}i=1m\\\{f\_\{i\}\(\\mathrm\{X\}\):\\mathrm\{X\}\\in\\mathcal\{X\}\\\}\_\{i=1\}^\{m\}\. Let

p=d1​d2,k=\(d1\+d2\)​r−r2\.p=d\_\{1\}d\_\{2\},\\quad k=\(d\_\{1\}\+d\_\{2\}\)r\-r^\{2\}\.The firstkkcoordinates offi​\(X\)f\_\{i\}\(\\mathrm\{X\}\)correspond to the estimated low\-rank subspace, while the remainingp−kp\-kcoordinates represent its orthogonal complement\. To exploit this structure, we use the anisotropic regularization matrix

Λ=diag⁡\(λ0​Ik,λ⟂​Ip−k\),\\Lambda=\\operatorname\{diag\}\(\\lambda\_\{0\}\\mathrm\{I\}\_\{k\},\\lambda\_\{\\perp\}\\mathrm\{I\}\_\{p\-k\}\),whereλ⟂≫λ0\\lambda\_\{\\perp\}\\gg\\lambda\_\{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 objectivei∈\[m\]i\\in\[m\], we maintain a design matrixVt,i\\mathrm\{V\}\_\{t,i\}and a parameter estimatorθ^t,i\\hat\{\\theta\}\_\{t,i\}in the transformed feature space\. They are initialized asV1,i=Λ\\mathrm\{V\}\_\{1,i\}=\\Lambdaandθ^1,i=0\\hat\{\\theta\}\_\{1,i\}=0, with confidence radiusβ1=Lμ⋅\(λ0​S\+λ⟂​S⟂\)\\beta\_\{1\}=L\_\{\\mu\}\\cdot\(\\sqrt\{\\lambda\_\{0\}\}S\+\\sqrt\{\\lambda\_\{\\perp\}\}S\_\{\\perp\}\)\.

At roundtt, the predicted reward and confidence width of armX∈𝒳\\mathrm\{X\}\\in\\mathcal\{X\}under objectivei∈\[m\]i\\in\[m\]are given by

y^t,i​\(X\)=μi​\(fi​\(X\)⊤​θ^t,i\),ct,i​\(X\)=βt​‖fi​\(X\)‖Vt,i−1\.\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\)=\\mu\_\{i\}\\\!\\big\(f\_\{i\}\(\\mathrm\{X\}\)^\{\\top\}\\hat\{\\theta\}\_\{t,i\}\\big\),\\ c\_\{t,i\}\(\\mathrm\{X\}\)=\\beta\_\{t\}\\\|f\_\{i\}\(\\mathrm\{X\}\)\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}\.\(5\)Here,ct,i​\(X\)c\_\{t,i\}\(\\mathrm\{X\}\)quantifies the uncertainty associated with the estimated reward\.Scalar\-LowGLMthen 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\)\)\.\\mathrm\{UCB\}\_\{t\}\(\\mathrm\{X\},w\)=\\sum\_\{i=1\}^\{m\}\(1\+w\)^\{m\-i\}\\left\(\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\)\+c\_\{t,i\}\(\\mathrm\{X\}\)\\right\)\.\(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\)\\mathrm\{X\}\_\{t\}=\\operatorname\*\{argmax\}\_\{\\mathrm\{X\}\\in\\mathcal\{X\}\}\\mathrm\{UCB\}\_\{t\}\(\\mathrm\{X\},w\)\.

Algorithm 2Scalar\-LowGLM0:

T,T1,δ,r,w,λ0,λ⟂,S⟂T,T\_\{1\},\\delta,r,w,\\lambda\_\{0\},\\lambda\_\{\\perp\},S\_\{\\perp\}
1:Run Algorithm[1](https://arxiv.org/html/2608.04324#alg1)for

T1T\_\{1\}rounds and obtain

\{fi​\(⋅\)\}i=1m\\\{f\_\{i\}\(\\cdot\)\\\}\_\{i=1\}^\{m\}
2:Set

p=d1​d2p=d\_\{1\}d\_\{2\}and

k=\(d1\+d2\)​r−r2k=\(d\_\{1\}\+d\_\{2\}\)r\-r^\{2\}
3:Set

Λ=diag​\(λ0​Ik,λ⟂​Ip−k\)\\Lambda=\\mathrm\{diag\}\(\\lambda\_\{0\}\\mathrm\{I\}\_\{k\},\\lambda\_\{\\perp\}\\mathrm\{I\}\_\{p\-k\}\)
4:Initialize

V1,i=Λ\\mathrm\{V\}\_\{1,i\}=\\Lambdaand

θ^1,i=0\\hat\{\\theta\}\_\{1,i\}=0for all

i∈\[m\]i\\in\[m\], and set the confidence radius

β1=Lμ⋅\(λ0​S\+λ⟂​S⟂\)\\beta\_\{1\}=L\_\{\\mu\}\\cdot\(\\sqrt\{\\lambda\_\{0\}\}S\+\\sqrt\{\\lambda\_\{\\perp\}\}S\_\{\\perp\}\)
5:for

t=1,…,T−T1t=1,\\ldots,T\-T\_\{1\}do

6:Compute

y^t,i​\(X\)\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\)and

ct,i​\(X\)c\_\{t,i\}\(\\mathrm\{X\}\)for all

X∈𝒳\\mathrm\{X\}\\in\\mathcal\{X\}by Eq\. \([5](https://arxiv.org/html/2608.04324#S4.E5)\)

7:Compute

UCBt​\(X,w\)\\text\{UCB\}\_\{t\}\(\\mathrm\{X\},w\)for all

X∈𝒳\\mathrm\{X\}\\in\\mathcal\{X\}by Eq\. \([6](https://arxiv.org/html/2608.04324#S4.E6)\)

8:Play

Xt=argmaxX∈𝒳UCBt​\(X,w\)\\mathrm\{X\}\_\{t\}=\\operatorname\*\{argmax\}\_\{\\mathrm\{X\}\\in\\mathcal\{X\}\}\\text\{UCB\}\_\{t\}\(\\mathrm\{X\},w\)
9:Observe reward vector

yt=\(yt,1,yt,2,…,yt,m\)y\_\{t\}=\(y\_\{t,1\},y\_\{t,2\},\\ldots,y\_\{t,m\}\)
10:for

i=1,…,mi=1,\\ldots,mdo

11:Compute the estimator

θ^t\+1,i\\hat\{\\theta\}\_\{t\+1,i\}by Eq\. \([7](https://arxiv.org/html/2608.04324#S4.E7)\)

12:Update

Vt\+1,i=Vt,i\+cμ2​fi​\(Xt\)​fi​\(Xt\)⊤\\mathrm\{V\}\_\{t\+1,i\}=\\mathrm\{V\}\_\{t,i\}\+\\frac\{c\_\{\\mu\}\}\{2\}f\_\{i\}\(\\mathrm\{X\}\_\{t\}\)f\_\{i\}\(\\mathrm\{X\}\_\{t\}\)^\{\\top\}
13:endfor

14:Compute

βt\+1\\beta\_\{t\+1\}by Eq\. \([8](https://arxiv.org/html/2608.04324#S4.E8)\)

15:endfor

After observing the reward vectoryt=\(yt,1,…,yt,m\)y\_\{t\}=\(y\_\{t,1\},\\ldots,y\_\{t,m\}\), the estimator for each objectivei∈\[m\]i\\in\[m\]is updated by solving the following regularized empirical risk minimization problem over all observations collected up to roundtt:

θ^t\+1,i=argmin‖θ‖2≤S​∑τ=1tℓτ,i​\(θ\)\+12​‖θ‖Λ2,\\displaystyle\\hat\{\\theta\}\_\{t\+1,i\}=\\operatorname\*\{argmin\}\_\{\\\|\\theta\\\|\_\{2\}\\leq S\}\\sum\_\{\\tau=1\}^\{t\}\\ell\_\{\\tau,i\}\(\\theta\)\+\\frac\{1\}\{2\}\\\|\\theta\\\|\_\{\\Lambda\}^\{2\},\(7\)whereℓτ,i​\(θ\)=bi​\(fi​\(Xτ\)⊤​θ\)−yτ,i⋅fi​\(Xτ\)⊤​θ\\ell\_\{\\tau,i\}\(\\theta\)=b\_\{i\}\\\!\\left\(f\_\{i\}\(\\mathrm\{X\}\_\{\\tau\}\)^\{\\top\}\\theta\\right\)\-y\_\{\\tau,i\}\\cdot f\_\{i\}\(\\mathrm\{X\}\_\{\\tau\}\)^\{\\top\}\\thetaandbi​\(⋅\)b\_\{i\}\(\\cdot\)is the cumulant function associated with the link functionμi​\(⋅\)\\mu\_\{i\}\(\\cdot\), i\.e\.,bi′​\(x\)=μi​\(x\)b\_\{i\}^\{\\prime\}\(x\)=\\mu\_\{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μ​R​Lt,k\+2​log⁡\(m/δ\)\+β1,\\displaystyle\\beta\_\{t\+1\}=L\_\{\\mu\}R\\sqrt\{L\_\{t,k\}\+2\\log\\left\(m/\\delta\\right\)\}\+\\beta\_\{1\},\(8\)whereLt,k=k​log⁡\(1\+tk\)\+cμ​t2​λ⟂L\_\{t,k\}=k\\log\\left\(1\+\\frac\{t\}\{k\}\\right\)\+\\frac\{c\_\{\\mu\}t\}\{2\\lambda\_\{\\perp\}\}\.

We now present the regret guarantee ofScalar\-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](https://arxiv.org/html/2608.04324#Thmassume1)–[6](https://arxiv.org/html/2608.04324#Thmassume6)hold\. For each objectivei∈\[m\]i\\in\[m\], letDr​r,iD\_\{rr,i\}denote therr\-th largest singular value of the objective\-specific parameter matrixΘi∗\\Theta\_\{i\}^\{\*\}, and defineDr​r=mini∈\[m\]⁡Dr​r,iD\_\{rr\}=\\min\_\{i\\in\[m\]\}D\_\{rr,i\}\. Run Algorithm[2](https://arxiv.org/html/2608.04324#alg2)with

T1≍M​\(d1\+d2\)​r​T​log⁡\(\(d1\+d2\)​m/δ\)Dr​r,T\_\{1\}\\asymp\\frac\{\\sqrt\{M\(d\_\{1\}\+d\_\{2\}\)rT\\log\(\(d\_\{1\}\+d\_\{2\}\)m/\\delta\)\}\}\{D\_\{rr\}\},and set

λ0=max⁡\{1,cμ/2\},λ⟂=cμ​Tk​log⁡\(1\+cμ​T/\(k​λ0\)\),\\lambda\_\{0\}=\\max\\\{1,c\_\{\\mu\}/2\\\},\\quad\\lambda\_\{\\perp\}=\\frac\{c\_\{\\mu\}T\}\{k\\log\\\!\\left\(1\+c\_\{\\mu\}T/\(k\\lambda\_\{0\}\)\\right\)\},wherek=\(d1\+d2\)​r−r2k=\(d\_\{1\}\+d\_\{2\}\)r\-r^\{2\}\. Furthermore, set

S⟂=M​\(d1\+d2\)​r​log⁡\(m​\(d1\+d2\)/δ\)Dr​r2​T\.S\_\{\\perp\}=\\sqrt\{\\frac\{M\(d\_\{1\}\+d\_\{2\}\)r\\log\(m\(d\_\{1\}\+d\_\{2\}\)/\\delta\)\}\{D\_\{rr\}^\{2\}T\}\}\.Then, with probability at least1−2​δ1\-2\\delta, for every objectivei∈\[m\]i\\in\[m\], the cumulative regret satisfies

Ri​\(T\)=O~​\(Wsca⋅\(d1\+d2\)​r​T\),R\_\{i\}\(T\)=\\widetilde\{O\}\\\!\\left\(W^\{\\rm sca\}\\cdot\(d\_\{1\}\+d\_\{2\}\)r\\sqrt\{T\}\\right\),whereWsca=∑i=1m\(1\+w\)i−1W^\{\\rm sca\}=\\sum\_\{i=1\}^\{m\}\(1\+w\)^\{i\-1\}\.

###### Remark 1

Whenm=1m=1, Theorem[1](https://arxiv.org/html/2608.04324#Thmthm1)indicatesScalar\-LowGLMachieves a regret bound ofO~​\(\(d1\+d2\)​r​T\)\\widetilde\{O\}\(\(d\_\{1\}\+d\_\{2\}\)r\\sqrt\{T\}\), matching the rate in single\-objective settings\(Kanget al\.,[2022](https://arxiv.org/html/2608.04324#bib.bib268)\)\. Compared with vectorizing matrix arms and applying lexicographic linear bandit methods\(Xueet al\.,[2025b](https://arxiv.org/html/2608.04324#bib.bib6)\), our bound replaces the ambient dimensiond1​d2d\_\{1\}d\_\{2\}with the intrinsic low\-rank dimension\(d1\+d2\)​r\(d\_\{1\}\+d\_\{2\}\)r\. The factorWscaW^\{\\rm sca\}captures the cost of fixed scalarization: whenw=0w=0, we haveWsca=mW^\{\\rm sca\}=mand hence only linear growth in the number of objectives; whenw\>0w\>0,Wsca=\(1\+w\)m−1wW^\{\\rm sca\}=\\frac\{\(1\+w\)^\{m\}\-1\}\{w\}, which grows geometrically with the number of objectives\.

### 4\.3Lexicographic Online Method:Lexi\-LowGLM

Algorithm 3Lexi\-LowGLM0:

T,T1,δ,r,w,λ0,λ⟂,S⟂T,T\_\{1\},\\delta,r,w,\\lambda\_\{0\},\\lambda\_\{\\perp\},S\_\{\\perp\}
1:Run Algorithm[1](https://arxiv.org/html/2608.04324#alg1)for

T1T\_\{1\}rounds and obtain

\{fi​\(⋅\)\}i=1m\\\{f\_\{i\}\(\\cdot\)\\\}\_\{i=1\}^\{m\}
2:Set

p=d1​d2p=d\_\{1\}d\_\{2\}and

k=\(d1\+d2\)​r−r2k=\(d\_\{1\}\+d\_\{2\}\)r\-r^\{2\}
3:Set

Λ=diag​\(λ0​Ik,λ⟂​Ip−k\)\\Lambda=\\mathrm\{diag\}\(\\lambda\_\{0\}\\mathrm\{I\}\_\{k\},\\lambda\_\{\\perp\}\\mathrm\{I\}\_\{p\-k\}\)
4:Initialize

V1,i=Λ\\mathrm\{V\}\_\{1,i\}=\\Lambdaand

θ^1,i=0\\hat\{\\theta\}\_\{1,i\}=0for all

i∈\[m\]i\\in\[m\], and set the confidence radius

β1=Lμ⋅\(λ0​S\+λ⟂​S⟂\)\\beta\_\{1\}=L\_\{\\mu\}\\cdot\(\\sqrt\{\\lambda\_\{0\}\}S\+\\sqrt\{\\lambda\_\{\\perp\}\}S\_\{\\perp\}\)
5:Initialize the candidate arm set

𝒳1=𝒳\\mathcal\{X\}\_\{1\}=\\mathcal\{X\}
6:for

t=1,…,T−T1t=1,\\ldots,T\-T\_\{1\}do

7:Compute

y^t,i​\(X\)\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\)and

ct,i​\(X\)c\_\{t,i\}\(\\mathrm\{X\}\)for all

X∈𝒳t\\mathrm\{X\}\\in\\mathcal\{X\}\_\{t\}by Eq\. \([5](https://arxiv.org/html/2608.04324#S4.E5)\)

8:Select

\(Xt,it\)=arg⁡maxX∈𝒳t,i∈\[m\]⁡ct,i​\(X\)\(\\mathrm\{X\}\_\{t\},i\_\{t\}\)=\\arg\\max\_\{\\mathrm\{X\}\\in\\mathcal\{X\}\_\{t\},i\\in\[m\]\}c\_\{t,i\}\(\\mathrm\{X\}\)
9:Set

𝒳t0=𝒳t\\mathcal\{X\}\_\{t\}^\{0\}=\\mathcal\{X\}\_\{t\}
10:for

i=1,2,…,mi=1,2,\\ldots,mdo

11:

Xt,i=arg⁡maxX∈𝒳ti−1⁡y^t,i​\(X\)\\mathrm\{X\}\_\{t,i\}=\\arg\\max\_\{\\mathrm\{X\}\\in\\mathcal\{X\}\_\{t\}^\{i\-1\}\}\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\)
12:

𝒳ti=\{X∈𝒳ti−1:y^t,i​\(Xt,i\)−y^t,i​\(X\)≤Wi⋅ct,it​\(Xt\)\}\\mathcal\{X\}\_\{t\}^\{i\}=\\\{\\mathrm\{X\}\\in\\mathcal\{X\}\_\{t\}^\{i\-1\}:\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\_\{t,i\}\)\-\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\)\\leq W\_\{i\}\\cdot c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)\\\}with

Wi=2\+4​w\+⋯\+4​wi−1W\_\{i\}=2\+4w\+\\cdots\+4w^\{i\-1\}
13:endfor

14:Play

Xt\\mathrm\{X\}\_\{t\}and observe

yt=\(yt,1,yt,2,…,yt,m\)y\_\{t\}=\(y\_\{t,1\},y\_\{t,2\},\\ldots,y\_\{t,m\}\)
15:for

i=1,2,…,mi=1,2,\\ldots,mdo

16:Compute the gradient

∇ℓt,i​\(θ^t,i\)\\nabla\\ell\_\{t,i\}\(\\hat\{\\theta\}\_\{t,i\}\)by Eq\. \([9](https://arxiv.org/html/2608.04324#S4.E9)\)

17:Update the estimator

θ^t\+1,i\\hat\{\\theta\}\_\{t\+1,i\}by Eq\. \([10](https://arxiv.org/html/2608.04324#S4.E10)\)

18:endfor

19:Compute the confidence radius

βt\+1\\beta\_\{t\+1\}by Eq\. \([11](https://arxiv.org/html/2608.04324#S4.E11)\)

20:Set

𝒳t\+1=𝒳tm\\mathcal\{X\}\_\{t\+1\}=\\mathcal\{X\}\_\{t\}^\{m\}
21:endfor

Algorithm[3](https://arxiv.org/html/2608.04324#alg3)is our proposed online method\. It shares the same subspace\-estimation and low\-rank feature initialization steps asScalar\-LowGLM: first run Algorithm[1](https://arxiv.org/html/2608.04324#alg1)to construct the transformed feature maps\{fi​\(⋅\)\}i=1m\\\{f\_\{i\}\(\\cdot\)\\\}\_\{i=1\}^\{m\}, and then initialize the anisotropic regularization matrixΛ\\Lambda, the covariance matrices\{V1,i\}i=1m\\\{\\mathrm\{V\}\_\{1,i\}\\\}\_\{i=1\}^\{m\}, the estimators\{θ^1,i\}i=1m\\\{\\hat\{\\theta\}\_\{1,i\}\\\}\_\{i=1\}^\{m\}, and the confidence radius\. Beyond this shared initialization,Lexi\-LowGLMmaintains an active candidate set𝒳t\\mathcal\{X\}\_\{t\}, initialized as𝒳1=𝒳\\mathcal\{X\}\_\{1\}=\\mathcal\{X\}, and progressively refines it throughout the learning process\.

UnlikeScalar\-LowGLM, which scalarizes the vector\-valued reward into a single score,Lexi\-LowGLMexplicitly preserves the lexicographic preference by sequentially eliminating statistically suboptimal arms objective by objective\. At each round,Lexi\-LowGLMcomputes the predicted reward and confidence width for every candidate arm under each objective using Eq\. \([5](https://arxiv.org/html/2608.04324#S4.E5)\), and selects the most uncertain arm\-objective pair in the current candidate set:

\(Xt,it\)∈argmaxX∈𝒳t,i∈\[m\]ct,i​\(X\)\.\(\\mathrm\{X\}\_\{t\},i\_\{t\}\)\\in\\operatorname\*\{argmax\}\_\{\\mathrm\{X\}\\in\\mathcal\{X\}\_\{t\},\\,i\\in\[m\]\}c\_\{t,i\}\(\\mathrm\{X\}\)\.The confidence widthct,it​\(Xt\)c\_\{t,i\_\{t\}\}\(\\mathrm\{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=𝒳t\\mathcal\{X\}\_\{t\}^\{0\}=\\mathcal\{X\}\_\{t\}, for each objectivei=1,2,…,mi=1,2,\\ldots,m,Lexi\-LowGLMfirst selects the empirically best arm in the current candidate set:

Xt,i=argmaxX∈𝒳ti−1y^t,i​\(X\)\.\\mathrm\{X\}\_\{t,i\}=\\operatorname\*\{argmax\}\_\{\\mathrm\{X\}\\in\\mathcal\{X\}\_\{t\}^\{i\-1\}\}\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\)\.It then removes arms whose estimated rewards are significantly inferior to that ofXt,i\\mathrm\{X\}\_\{t,i\}under theii\-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\)\},\\mathcal\{X\}\_\{t\}^\{i\}=\\left\\\{\\mathrm\{X\}\\in\\mathcal\{X\}\_\{t\}^\{i\-1\}:\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\_\{t,i\}\)\-\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\)\\leq W\_\{i\}\\cdot c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)\\right\\\},whereWi=2\+4​w\+⋯\+4​wi−1W\_\{i\}=2\+4w\+\\cdots\+4w^\{i\-1\}\.

The tolerance factorWiW\_\{i\}accounts for the cumulative trade\-off induced by the lexicographic structure\. Since the candidate set is refined sequentially from objective11to objectivemm, higher\-priority objectives are enforced before lower\-priority ones\. Consequently, the final candidate set𝒳tm\\mathcal\{X\}\_\{t\}^\{m\}contains the arms that remain promising across all objectives\. After all objectives have been processed,Lexi\-LowGLMplays armXt\\mathrm\{X\}\_\{t\}and observes the reward vectoryt=\(yt,1,yt,2,…,yt,m\)y\_\{t\}=\(y\_\{t,1\},y\_\{t,2\},\\ldots,y\_\{t,m\}\)\.

UnlikeScalar\-LowGLM, which recomputes the estimator from all historical observations,Lexi\-LowGLMupdates each objective\-specific estimator via an online Newton\-type proximal step\. For each objectivei∈\[m\]i\\in\[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\),\\nabla\\ell\_\{t,i\}\(\\hat\{\\theta\}\_\{t,i\}\)=\(\\mu\_\{i\}\(f\_\{i\}\(\\mathrm\{X\}\_\{t\}\)^\{\\top\}\\hat\{\\theta\}\_\{t,i\}\)\-y\_\{t,i\}\)\\cdot f\_\{i\}\(\\mathrm\{X\}\_\{t\}\),\(9\)and updates the covariance matrix by

Vt\+1,i=Vt,i\+cμ2​fi​\(Xt\)​fi​\(Xt\)⊤\.\\mathrm\{V\}\_\{t\+1,i\}=\\mathrm\{V\}\_\{t,i\}\+\\frac\{c\_\{\\mu\}\}\{2\}f\_\{i\}\(\\mathrm\{X\}\_\{t\}\)f\_\{i\}\(\\mathrm\{X\}\_\{t\}\)^\{\\top\}\.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\)⟩\.\\displaystyle\\hat\{\\theta\}\_\{t\+1,i\}=\\operatorname\*\{argmin\}\_\{\\lVert\\theta\\rVert\_\{2\}\\leq S\}\\frac\{\\lVert\\theta\-\\hat\{\\theta\}\_\{t,i\}\\rVert^\{2\}\_\{\\mathrm\{V\}\_\{t\+1,i\}\}\}\{2\}\+\\langle\\theta,\\nabla\\ell\_\{t,i\}\(\\hat\{\\theta\}\_\{t,i\}\)\\rangle\.\(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,\\displaystyle\\beta\_\{t\+1\}=L\_\{\\mu\}\\left\(4\(U\+R\)\\sqrt\{\\frac\{L\_\{t,k\}\+L\_\{t,\\delta\}\}\{c\_\{\\mu\}\}\}\+\\sqrt\{\\frac\{c\_\{\\mu\}\}\{2\}\}\\right\)\+\\beta\_\{1\},\(11\)whereLt,δ=log⁡\(m​1\+4​S2​tδ\)L\_\{t,\\delta\}=\\log\\left\(\\frac\{m\\sqrt\{1\+4S^\{2\}t\}\}\{\\delta\}\\right\)\.

Finally, the candidate set for the next round is updated as𝒳t\+1=𝒳tm\\mathcal\{X\}\_\{t\+1\}=\\mathcal\{X\}\_\{t\}^\{m\}\. In this way, Algorithm[3](https://arxiv.org/html/2608.04324#alg3)gradually eliminates statistically suboptimal arms while updating the objective\-specific estimators in the estimated reduced feature spaces\.

We next establish the regret guarantee ofLexi\-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](https://arxiv.org/html/2608.04324#Thmassume1)–[6](https://arxiv.org/html/2608.04324#Thmassume6)hold, and run Algorithm[3](https://arxiv.org/html/2608.04324#alg3)with the same parameters as specified in Theorem[1](https://arxiv.org/html/2608.04324#Thmthm1)\. Then, with probability at least1−2​δ1\-2\\delta, for every objectivei∈\[m\]i\\in\[m\], the cumulative regret satisfies

Ri​\(T\)=O~​\(Wilex​m⋅\(d1\+d2\)​r​T\),\\displaystyle R\_\{i\}\(T\)=\\widetilde\{O\}\\left\(W\_\{i\}^\{\\rm lex\}\\sqrt\{m\}\\cdot\(d\_\{1\}\+d\_\{2\}\)r\\sqrt\{T\}\\right\),whereWilex=1\+w\+⋯\+wi−1W\_\{i\}^\{\\rm lex\}=1\+w\+\\cdots\+w^\{i\-1\}\.

###### Remark 2

Theorem[2](https://arxiv.org/html/2608.04324#Thmthm2)shows thatLexi\-LowGLMmatches the horizon and effective\-dimension dependence achieved in the single\-objective setting\(Kanget al\.,[2022](https://arxiv.org/html/2608.04324#bib.bib268)\), while jointly learning all objectives\. Compared with the scalarized baseline in Theorem[1](https://arxiv.org/html/2608.04324#Thmthm1), the improvement lies in the objective\-dependent factor\. In particular, the regret for the highest\-priority objective is independent of the trade\-off parameterww\. Whenw=0w=0, we haveWilex=1W\_\{i\}^\{\\rm lex\}=1for alli∈\[m\]i\\in\[m\], whereasWsca=mW^\{\\rm sca\}=m\. Thus, lexicographic filtering improves the dependence on the number of objectives frommmtom\\sqrt\{m\}\. Whenw\>0w\>0,WilexW\_\{i\}^\{\\rm lex\}remains more refined thanWscaW^\{\\rm sca\}sinceWilexW\_\{i\}^\{\\rm lex\}grows with the prefix lengthiirather than the total number of objectivesmm, and uses powers ofwwinstead of powers of1\+w1\+w\. This highlights the benefit of explicitly exploiting the sequential structure of lexicographic preferences\. In addition,Lexi\-LowGLMuses 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\.

## 5Experiments

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\.

![Refer to caption](https://arxiv.org/html/2608.04324v1/x1.png)Figure 1:Regret comparison of our algorithms versusG\-ESTTandMTLOfor rank11\.#### Baselines\.

We compareScalar\-LowGLMandLexi\-LowGLMwith two representative baselines:G\-ESTT\(Kanget al\.,[2022](https://arxiv.org/html/2608.04324#bib.bib268)\)andMTLO\(Xueet al\.,[2025b](https://arxiv.org/html/2608.04324#bib.bib6)\)\.G\-ESTTis 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\.MTLOis a lexicographic linear bandit algorithm applied to the vectorized matrix featuresvec⁡\(X\)∈ℝd1​d2\\operatorname\{vec\}\(X\)\\in\\mathbb\{R\}^\{d\_\{1\}d\_\{2\}\}\. It captures lexicographic preferences but operates in the ambient dimensiond1​d2d\_\{1\}d\_\{2\}without exploiting the underlying low\-rank structure\.

We set the horizon toT=10,000T=10\{,\}000, the exploration length toT1=3,000T\_\{1\}=3\{,\}000, and consider ranksr∈\{1,2\}r\\in\\\{1,2\\\}\. Each experiment is repeated over1010independent 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](https://arxiv.org/html/2608.04324#S5.F1)compares the objective\-wise cumulative regret of all algorithms\.G\-ESTTeffectively controls the regret on Objective 1, but its regret grows nearly linearly on Objectives 2 and 3\. This behavior is expected becauseG\-ESTTis designed for single\-objective learning, without explicitly accounting for the lower\-priority objectives\.MTLOachieves the smallest regret on Objective 1 during the early rounds because it operates directly on the fixed finite arm set and avoids theT1T\_\{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:MTLOis 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 thanG\-ESTTandMTLO\. The relatively larger Objective 1 regret ofLexi\-LowGLMis partly attributable to the initial subspace\-exploration phase\.Scalar\-LowGLMstabilizes shortly after this exploration phase and attains the smallest empirical regret on the two lower\-priority objectives\. Although the theoretical bound ofLexi\-LowGLMhas a more favorable objective\-dependent factorWilexW\_\{i\}^\{\\mathrm\{lex\}\}, this does not imply that its finite\-horizon regret must be uniformly smaller than that ofScalar\-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 atT=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\.Table[1](https://arxiv.org/html/2608.04324#S5.T1)reports the mean wall\-clock time required to complete a rank\-one trial over10,00010\{,\}000rounds\.Lexi\-LowGLMfinishes in only4\.0704\.070seconds, making it approximately21×21\\timesfaster thanG\-ESTTand55×55\\timesfaster thanScalar\-LowGLM\. This gap reflects their different estimator\-update mechanisms:G\-ESTTrepeatedly refits a batch estimator for the highest\-priority objective, whileScalar\-LowGLMperforms batch refitting for all three objectives\. By contrast,Lexi\-LowGLMupdates each estimator online using only the current observation, thereby avoiding repeated processing of the full history\.MTLOandLexi\-LowGLMhave similar running times because both rely on online updates\. However,MTLOis designed for linear rewards and does not accommodate the generalized linear setting, resulting in linear regret on Objectives 2 and 3\. Overall,Lexi\-LowGLMachieves the lowest mean runtime while substantially outperformingMTLOon the lower\-priority objectives\.

## 6Conclusion 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\-LowGLMandLexi\-LowGLM\.Scalar\-LowGLMserves as a natural scalarized batch baseline, whileLexi\-LowGLMcombines objective\-specific subspace estimation, lexicographic filtering, and online Newton\-type updates\. Theoretically, we established objective\-wise regret bounds of orderO~​\(Wilex​m​\(d1\+d2\)​r​T\)\\widetilde\{O\}\(W\_\{i\}^\{\\rm lex\}\\sqrt\{m\}\(d\_\{1\}\+d\_\{2\}\)r\\sqrt\{T\}\), showing that the regret depends on the intrinsic low\-rank dimensionrr\. Moreover, compared with repeated batch re\-estimation\(Kanget al\.,[2022](https://arxiv.org/html/2608.04324#bib.bib268)\),Lexi\-LowGLMreduces the cumulative estimator\-update complexity fromO​\(T2\)O\(T^\{2\}\)toO​\(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

- Improved algorithms for linear stochastic bandits\.InAdvances in Neural Information Processing Systems 24,pp\. 2312–2320\.Cited by:[Appendix B](https://arxiv.org/html/2608.04324#A2.SS0.SSS0.Px6.p3.4),[Appendix B](https://arxiv.org/html/2608.04324#A2.SS0.SSS0.Px8.p8.3),[Appendix C](https://arxiv.org/html/2608.04324#A3.SS0.SSS0.Px10.p2.4),[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px1.p1.1)\.
- Y\. Abbasi\-Yadkori, D\. Pal, and C\. Szepesvari \(2012\)Online\-to\-confidence\-set conversions and application to sparse stochastic bandits\.InProceedings of the 15th International Conference on Artificial Intelligence and Statistics,pp\. 1–9\.Cited by:[Appendix C](https://arxiv.org/html/2608.04324#A3.SS0.SSS0.Px4.p1.3)\.
- V\. S\. P\. Alperen Tercan \(2024\)Thresholded lexicographic ordered multiobjective reinforcement learning\.InProceedings of the 27th European Conference on Artificial Intelligence,pp\. 3006–3014\.Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p2.1)\.
- P\. Auer, C\. Chiang, R\. Ortner, and M\. Drugan \(2016\)Pareto front identification from stochastic bandit feedback\.InProceedings of the 19th International Conference on Artificial Intelligence and Statistics,pp\. 939–947\.Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p1.1)\.
- P\. Auer \(2002\)Using confidence bounds for exploitation\-exploration trade\-offs\.Journal of Machine Learning Research3\(11\),pp\. 397–422\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p1.1)\.
- R\. Busa\-Fekete, B\. Szörényi, P\. Weng, and S\. Mannor \(2017\)Multi\-objective bandits: optimizing the generalized Gini index\.InProceedings of the 34th International Conference on Machine Learning,pp\. 625–634\.Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p1.1)\.
- X\. Cai, P\. Zhang, L\. Zhao, B\. Jiang, M\. Sugiyama, and A\. J\. Llorens \(2023\)Distributional pareto\-optimal multi\-objective reinforcement learning\.InAdvances in Neural Information Processing Systems 36,Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p1.1)\.
- W\. Chu, L\. Li, L\. Reyzin, and R\. Schapire \(2011\)Contextual bandits with linear payoff functions\.InProceedings of the 14th International Conference on Artificial Intelligence and Statistics,pp\. 208–214\.Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px1.p1.1)\.
- É\. Crepon, A\. Garivier, and W\. M Koolen \(2024\)Sequential learning of the Pareto front for multi\-objective bandits\.InProceedings of The 27th International Conference on Artificial Intelligence and Statistics,pp\. 3583–3591\.Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p1.1)\.
- V\. Dani, T\. P\. Hayes, and S\. M\. Kakade \(2008\)Stochastic linear optimization under bandit feedback\.InProceedings of the 21st Annual Conference on Learning,pp\. 355–366\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p1.1)\.
- M\. M\. Drugan and A\. Nowe \(2013\)Designing multi\-objective multi\-armed bandits algorithms: a study\.InThe 2013 International Joint Conference on Neural Networks,pp\. 1–8\.Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p1.1)\.
- M\. Ehrgott \(2005\)Multicriteria optimization\.Springer\-Verlag,Berlin, Heidelberg\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p3.1)\.
- S\. Filippi, O\. Cappe, A\. Garivier, and C\. Szepesvári \(2010\)Parametric bandits: the generalized linear case\.InAdvances in Neural Information Processing Systems 23,pp\. 586–594\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p1.1)\.
- E\. Hazan, A\. Agarwal, and S\. Kale \(2007\)Logarithmic regret algorithms for online convex optimization\.Machine Learning69\(2\-3\),pp\. 169–192\.Cited by:[Appendix C](https://arxiv.org/html/2608.04324#A3.SS0.SSS0.Px5.p1.9)\.
- A\. Hüyük and C\. Tekin \(2021\)Multi\-objective multi\-armed bandit with lexicographically ordered and satisficing objectives\.Machine Learning110\(6\),pp\. 1233–1266\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p4.1),[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p2.1)\.
- K\. Jang, K\. Jun, S\. Yun, and W\. Kang \(2021\)Improved regret bounds of bilinear bandits using action space analysis\.InProceedings of the 38th International Conference on Machine Learning,pp\. 4744–4754\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p2.8),[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px1.p1.1)\.
- K\. Jang, C\. Zhang, and K\. Jun \(2024\)Efficient low\-rank matrix estimation, experimental design, and arm\-set\-dependent low\-rank bandits\.InProceedings of the 41st International Conference on Machine Learning,pp\. 21329–21372\.Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px1.p2.1)\.
- K\. Jee, D\. L\. McShan, and B\. A\. Fraass \(2007\)Lexicographic ordering: intuitive multicriteria optimization for imrt\.Physics in Medicine & Biology52,pp\. 1845–1861\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p3.1)\.
- K\. Jun, R\. Willett, S\. Wright, and R\. Nowak \(2019\)Bilinear bandits with low\-rank structure\.InProceedings of the 36th International Conference on Machine Learning,pp\. 3163–3172\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p1.1),[§1](https://arxiv.org/html/2608.04324#S1.p2.8),[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px1.p1.1)\.
- Y\. Kang, C\. Hsieh, and T\. C\. M\. Lee \(2022\)Efficient frameworks for generalized low\-rank matrix bandit problems\.InAdvances in Neural Information Processing Systems 35,pp\. 19971–19983\.Cited by:[Appendix B](https://arxiv.org/html/2608.04324#A2.SS0.SSS0.Px2.p1.3),[Appendix B](https://arxiv.org/html/2608.04324#A2.SS0.SSS0.Px6.p3.6),[Appendix B](https://arxiv.org/html/2608.04324#A2.SS0.SSS0.Px8.p8.3),[Appendix C](https://arxiv.org/html/2608.04324#A3.SS0.SSS0.Px10.p2.2),[Appendix C](https://arxiv.org/html/2608.04324#A3.SS0.SSS0.Px5.p2.3),[3rd item](https://arxiv.org/html/2608.04324#S1.I1.i3.p1.6),[§1](https://arxiv.org/html/2608.04324#S1.p1.1),[§1](https://arxiv.org/html/2608.04324#S1.p4.1),[§1](https://arxiv.org/html/2608.04324#S1.p5.2),[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px1.p2.1),[§3](https://arxiv.org/html/2608.04324#S3.SS0.SSS0.Px4.p1.1),[§4\.2](https://arxiv.org/html/2608.04324#S4.SS2.p1.1),[§4](https://arxiv.org/html/2608.04324#S4.p1.1),[§5](https://arxiv.org/html/2608.04324#S5.SS0.SSS0.Px1.p1.2),[§6](https://arxiv.org/html/2608.04324#S6.p1.4),[Remark 1](https://arxiv.org/html/2608.04324#Thmrem1.p1.9),[Remark 2](https://arxiv.org/html/2608.04324#Thmrem2.p1.15)\.
- Y\. Kang, C\. Hsieh, and T\. C\. M\. Lee \(2024\)Low\-rank matrix bandits with heavy\-tailed rewards\.InProceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence,pp\. 1863–1889\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p2.8),[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px1.p1.1),[§3](https://arxiv.org/html/2608.04324#S3.SS0.SSS0.Px3.p3.1)\.
- A\. A\. Khansa, R\. Visoz, Y\. Hayel, and S\. Lasaulce \(2021\)Resource allocation for multi\-source multi\-relay wireless networks\.InUbiquitous Networking,pp\. 62–75\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p1.1)\.
- T\. L\. Lai and H\. Robbins \(1985\)Asymptotically efficient adaptive allocation rules\.Advances in Applied Mathematics6\(1\),pp\. 4–22\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p1.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](https://arxiv.org/abs/2412.19436)Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px1.p2.1)\.
- L\. Li, W\. Chu, J\. Langford, and R\. E\. Schapire \(2010\)A contextual\-bandit approach to personalized news article recommendation\.InProceedings of the 19th International Conference on World Wide Web,pp\. 661–670\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p1.1)\.
- S\. Lu, G\. Wang, Y\. Hu, and L\. Zhang \(2019\)Optimal algorithms for lipschitz bandits with heavy\-tailed rewards\.InProceedings of the 36th International Conference on Machine Learning,pp\. 4154–4163\.Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p1.1)\.
- Y\. Lu, A\. Meisami, and A\. Tewari \(2021\)Low\-rank generalized linear bandit problems\.InProceedings of The 24th International Conference on Artificial Intelligence and Statistics,pp\. 460–468\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p2.8),[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px1.p2.1)\.
- S\. Mukherjee, Q\. Xie, J\. Hanna, and R\. Nowak \(2023\)Multi\-task representation learning for pure exploration in bilinear bandits\.InAdvances in Neural Information Processing Systems 36,pp\. 47816–47827\.Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px1.p1.1)\.
- S\. Park, H\. Ann, and M\. Oh \(2025\)Thompson sampling for multi\-objective linear contextual bandit\.InAdvances in Neural Information Processing Systems 38,pp\. 84523–84555\.Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p1.1)\.
- 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](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p1.1)\.
- H\. Robbins \(1952\)Some aspects of the sequential design of experiments\.Bulletin of the American Mathematical Society58\(5\),pp\. 527–535\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p1.1)\.
- E\. Schwartz, E\. Bradlow, and P\. Fader \(2017\)Customer acquisition via display advertising using multi\-armed bandit experiments\.InMarketing Science,pp\. 500–522\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p1.1)\.
- J\. Skalse, L\. Hammond, C\. Griffin, and A\. Abate \(2022\)Lexicographic multi\-objective reinforcement learning\.InProceedings of the 31st International Joint Conference on Artificial Intelligence,pp\. 3430–3436\.Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p2.1)\.
- C\. Tekin and E\. Turgay \(2018\)Multi\-objective contextual multi\-armed bandit with a dominant objective\.IEEE Transactions on Signal Processing66\(14\),pp\. 3799–3813\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p4.1),[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p2.1)\.
- E\. Turgay, D\. Oner, and C\. Tekin \(2018\)Multi\-objective contextual bandit problem with similarity information\.InProceedings of the 21st International Conference on Artificial Intelligence and Statistics,pp\. 1673–1681\.Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p1.1)\.
- 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](https://arxiv.org/abs/2507.17528)Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p2.8),[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px1.p2.1),[§3](https://arxiv.org/html/2608.04324#S3.SS0.SSS0.Px3.p3.1)\.
- E\. Weber, A\. E\. Rizzoli, R\. Soncini\-Sessa, and A\. Castelletti \(2002\)Lexicographic optimisation for water resources planning: the case of lake verbano, italy\.InIntegrated Assessment and Decision Support \- Proceedings of the 1st Biennial Meeting of the International Environmental Modelling and Software Society,pp\. 235–240\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p3.1)\.
- M\. Xu and D\. Klabjan \(2023\)Pareto regret analyses in multi\-objective multi\-armed bandit\.InProceedings of the 40th International Conference on International Conference on Machine Learning,pp\. 38499–38517\.Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p1.1)\.
- B\. Xue, D\. Bu, J\. Cheng, Y\. Wan, and Q\. Zhang \(2025a\)Multi\-objective linear reinforcement learning with lexicographic rewards\.InProceedings of the 42nd International Conference on Machine Learning,Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p2.1)\.
- B\. Xue, X\. Lin, X\. Zhang, and Q\. Zhang \(2025b\)Multiple trade\-offs: an improved approach for lexicographic linear bandits\.InProceedings of the 39th AAAI Conference on Artificial Intelligence,pp\. 21850–21858\.Cited by:[§1](https://arxiv.org/html/2608.04324#S1.p4.1),[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p2.1),[§3](https://arxiv.org/html/2608.04324#S3.SS0.SSS0.Px3.p3.1),[§5](https://arxiv.org/html/2608.04324#S5.SS0.SSS0.Px1.p1.2),[Remark 1](https://arxiv.org/html/2608.04324#Thmrem1.p1.9)\.
- Q\. \(\. Zhang \(2024\)Optimal scalarizations for sublinear hypervolume regret\.InAdvances in Neural Information Processing Systems 37,pp\. 39963–39999\.Cited by:[§2](https://arxiv.org/html/2608.04324#S2.SS0.SSS0.Px2.p1.1)\.

## Appendix AExperimental Setup and Rank\-Two Results

### A\.1Detailed Experimental Setup

We setd1=d2=10d\_\{1\}=d\_\{2\}=10, considerm=3m=3objectives, and examine matrix ranksr∈\{1,2\}r\\in\\\{1,2\\\}\. Each problem instance containsK=10K=10fixed matrix arms\. For eachk∈\[K\]k\\in\[K\], define the objective\-specific latent scores

g1​\(k\)\\displaystyle g\_\{1\}\(k\)=1−min⁡\{\|k−1\|,\|k−4\|,\|k−8\|\},\\displaystyle=1\-\\min\\\{\|k\-1\|,\|k\-4\|,\|k\-8\|\\\},g2​\(k\)\\displaystyle g\_\{2\}\(k\)=1−min⁡\{\|k−3\|,\|k−7\|\},\\displaystyle=1\-\\min\\\{\|k\-3\|,\|k\-7\|\\\},g3​\(k\)\\displaystyle g\_\{3\}\(k\)=1−\|k−8\|\.\\displaystyle=1\-\|k\-8\|\.Thus, arms11,44, and88maximize the first objective\. Among these arms,44and88remain optimal under the second objective, while the third objective uniquely identifies arm88\. Hence, arm88is the unique lexicographically optimal arm\.

Let\{ej\}j=110\\\{e\_\{j\}\\\}\_\{j=1\}^\{10\}denote the canonical basis ofℝ10\\mathbb\{R\}^\{10\}\. For each objectivei∈\[m\]i\\in\[m\], define the unknown parameter matrix as

Θi⋆=1r​∑ℓ=1rei\+3​\(ℓ−1\)​eℓ⊤\.\\Theta\_\{i\}^\{\\star\}=\\frac\{1\}\{\\sqrt\{r\}\}\\sum\_\{\\ell=1\}^\{r\}e\_\{i\+3\(\\ell\-1\)\}e\_\{\\ell\}^\{\\top\}\.By construction,rank⁡\(Θi⋆\)=r​and​‖Θi⋆‖F=1\.\\operatorname\{rank\}\(\\Theta\_\{i\}^\{\\star\}\)=r\\text\{ and \}\\\|\\Theta\_\{i\}^\{\\star\}\\\|\_\{\\mathrm\{F\}\}=1\.Thekk\-th fixed arm is defined as

Xk=1κr​r​∑ℓ=1r∑i=1mgi​\(k\)​ei\+3​\(ℓ−1\)​eℓ⊤,\\mathrm\{X\}\_\{k\}=\\frac\{1\}\{\\kappa\_\{r\}r\}\\sum\_\{\\ell=1\}^\{r\}\\sum\_\{i=1\}^\{m\}g\_\{i\}\(k\)e\_\{i\+3\(\\ell\-1\)\}e\_\{\\ell\}^\{\\top\},where

κr=maxk∈\[K\]⁡1r​∑i=1mgi​\(k\)2\.\\kappa\_\{r\}=\\max\_\{k\\in\[K\]\}\\sqrt\{\\frac\{1\}\{r\}\\sum\_\{i=1\}^\{m\}g\_\{i\}\(k\)^\{2\}\}\.This normalization ensures that‖Xk‖F≤1\\\|\\mathrm\{X\}\_\{k\}\\\|\_\{\\mathrm\{F\}\}\\leq 1for everyk∈\[K\]k\\in\[K\]\. Moreover,

⟨Xk,Θi⋆⟩=1κr​r​gi​\(k\),\\langle\\mathrm\{X\}\_\{k\},\\Theta\_\{i\}^\{\\star\}\\rangle=\\frac\{1\}\{\\kappa\_\{r\}\\sqrt\{r\}\}g\_\{i\}\(k\),so the resulting matrix construction preserves the rankings and ties specified by the latent scores\.

After selecting armXt\\mathrm\{X\}\_\{t\}, the learner observes

yt,i=μ​\(⟨Xt,Θi⋆⟩\)\+ηt,i,μ​\(z\)=11\+exp⁡\(−z\),y\_\{t,i\}=\\mu\\\!\\left\(\\langle\\mathrm\{X\}\_\{t\},\\Theta\_\{i\}^\{\\star\}\\rangle\\right\)\+\\eta\_\{t,i\},\\qquad\\mu\(z\)=\\frac\{1\}\{1\+\\exp\(\-z\)\},where the noise variablesηt,i∼Uniform⁡\[−0\.1,0\.1\]\\eta\_\{t,i\}\\sim\\operatorname\{Uniform\}\[\-0\.1,0\.1\]are independent across rounds and objectives\.

During the firstT1T\_\{1\}rounds, the low\-rank methods sample arms from a continuous exploration distribution\. Leta=1/d1​d2\.a=1/\\sqrt\{d\_\{1\}d\_\{2\}\}\.For each entry, we independently drawZu​v∼Beta⁡\(3,3\)Z\_\{uv\}\\sim\\operatorname\{Beta\}\(3,3\)and set\(Xt\)u​v=−a​Zu​v\.\(\\mathrm\{X\}\_\{t\}\)\_\{uv\}=\-aZ\_\{uv\}\.This construction guarantees‖Xt‖F≤1\\\|\\mathrm\{X\}\_\{t\}\\\|\_\{\\mathrm\{F\}\}\\leq 1\. The corresponding entrywise score function is

S​\(Xt\)u​v=−2​\(a\+2​\(Xt\)u​v\)\(Xt\)u​v​\(a\+\(Xt\)u​v\)\.S\(\\mathrm\{X\}\_\{t\}\)\_\{uv\}=\-\\frac\{2\\bigl\(a\+2\(\\mathrm\{X\}\_\{t\}\)\_\{uv\}\\bigr\)\}\{\(\\mathrm\{X\}\_\{t\}\)\_\{uv\}\\bigl\(a\+\(\\mathrm\{X\}\_\{t\}\)\_\{uv\}\\bigr\)\}\.The exploration radius is chosen such thatX8\\mathrm\{X\}\_\{8\}remains the comparator among the fixed arms\. After the exploration phase, the low\-rank methods select from the ten fixed arms, whereasMTLOoperates on the fixed candidate set from the beginning\.

We set the horizon toT=10000T=10000and the exploration length toT1=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 to11,0\.10\.1,0\.0040\.004,33, and10−510^\{\-5\}, respectively\. Each experiment is repeated over1010independent 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 one1000010000\-round trial, including exploration, arm selection, reward generation, and estimator updates\.

### A\.2Additional Rank\-Two Results

![Refer to caption](https://arxiv.org/html/2608.04324v1/x2.png)Figure 2:Regret comparison of our algorithms versusG\-ESTTandMTLOfor rank22\.Figure[2](https://arxiv.org/html/2608.04324#A1.F2)shows that the qualitative ordering observed for rank one largely persists when the rank increases to two\.Scalar\-LowGLMreaches 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 ofG\-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 byScalar\-LowGLMon the highest\-priority objective\. The batch refitting of all three objective models then enablesScalar\-LowGLMto identify arm88and correct temporary estimation errors using the complete observation history\.

In contrast,G\-ESTTaccumulates almost linear regret on Objectives 2 and 3\. Under Objective 1, arms11,44, and88are 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\.MTLOalso 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 ambientd1​d2d\_\{1\}d\_\{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\-LowGLMsubstantially reduces the lower\-priority regret relative toG\-ESTTandMTLO\. 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 within1000010000rounds\. 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\}=19to3636\. The resulting larger subspace and parameter uncertainty keeps multiple candidate arms active for longer\. HenceLexi\-LowGLMcontinues to explore among arms that are nearly indistinguishable under the higher\-priority objectives instead of selecting arm88exclusively\.

## Appendix BProof of Theorem[1](https://arxiv.org/html/2608.04324#Thmthm1)

#### 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 ofT1T\_\{1\},λ⟂\\lambda\_\{\\perp\}, andS⟂S\_\{\\perp\}\.

#### Step 1: Subspace estimation and tail\-coordinate control\.

###### Lemma 1

Suppose that Assumptions[2](https://arxiv.org/html/2608.04324#Thmassume2)–[4](https://arxiv.org/html/2608.04324#Thmassume4)and[6](https://arxiv.org/html/2608.04324#Thmassume6)hold\. LetX1,…,XT1\\mathrm\{X\}\_\{1\},\\ldots,\\mathrm\{X\}\_\{T\_\{1\}\}be sampled independently from𝒟\\mathcal\{D\}over𝒳\\mathcal\{X\}\. For each objectivei∈\[m\]i\\in\[m\], letΘ^i\\widehat\{\\Theta\}\_\{i\}be the solution to the nuclear\-norm regularized problem \([3](https://arxiv.org/html/2608.04324#S4.E3)\)\. Setν=2​log⁡\(2​m​\(d1\+d2\)/δ\)\(4​R2\+U2\)​M​T1​\(d1\+d2\)\\nu=\\sqrt\{\\frac\{2\\log\(2m\(d\_\{1\}\+d\_\{2\}\)/\\delta\)\}\{\(4R^\{2\}\+U^\{2\}\)MT\_\{1\}\(d\_\{1\}\+d\_\{2\}\)\}\}andλT1=4​2​\(4​R2\+U2\)​M​\(d1\+d2\)​log⁡\(2​m​\(d1\+d2\)/δ\)T1\\lambda\_\{T\_\{1\}\}=4\\sqrt\{\\frac\{2\(4R^\{2\}\+U^\{2\}\)M\(d\_\{1\}\+d\_\{2\}\)\\log\(2m\(d\_\{1\}\+d\_\{2\}\)/\\delta\)\}\{T\_\{1\}\}\}\. Then, with probability at least1−δ1\-\\delta, the following bound holds for alli∈\[m\]i\\in\[m\]:

‖Θ^i−μi∗​Θi∗‖F2≤C1​M​\(d1\+d2\)​r​log⁡\(2​m​\(d1\+d2\)/δ\)T1\\\|\\widehat\{\\Theta\}\_\{i\}\-\\mu^\{\*\}\_\{i\}\\Theta^\{\*\}\_\{i\}\\\|^\{2\}\_\{F\}\\leq\\frac\{C\_\{1\}M\(d\_\{1\}\+d\_\{2\}\)r\\log\(2m\(d\_\{1\}\+d\_\{2\}\)/\\delta\)\}\{T\_\{1\}\}forC1=36​\(4​R2\+U2\)C\_\{1\}=36\(4R^\{2\}\+U^\{2\}\)andμi∗=E​\[μi′​\(⟨X,Θi∗⟩\)\]≥cμ\>0\\mu^\{\*\}\_\{i\}=\\mathrm\{E\}\[\\mu^\{\\prime\}\_\{i\}\(\\langle X,\\Theta\_\{i\}^\{\*\}\\rangle\)\]\\geq c\_\{\\mu\}\>0\.

Proof\.Under Assumptions[2](https://arxiv.org/html/2608.04324#Thmassume2)–[4](https://arxiv.org/html/2608.04324#Thmassume4)and[6](https://arxiv.org/html/2608.04324#Thmassume6), the observations associated with objectiveiiconstitute a low\-rank generalized linear model satisfying the conditions ofKanget al\.\[[2022](https://arxiv.org/html/2608.04324#bib.bib268), Theorem 4\.1\]\. Applying this theorem to objectiveiiwith confidence levelδ′=δ/m\\delta^\{\\prime\}=\\delta/mgives

Pr​\(ℰi\)≥1−δ′,\\mathrm\{Pr\}\(\\mathcal\{E\}\_\{i\}\)\\geq 1\-\\delta^\{\\prime\},where

ℰi:=\{‖Θ^i−μi∗​Θi∗‖F2≤C1​M​\(d1\+d2\)​r​log⁡\(2​\(d1\+d2\)/δ′\)T1\},\\mathcal\{E\}\_\{i\}:=\\left\\\{\\left\\\|\\widehat\{\\Theta\}\_\{i\}\-\\mu\_\{i\}^\{\*\}\\Theta\_\{i\}^\{\*\}\\right\\\|\_\{F\}^\{2\}\\leq\\frac\{C\_\{1\}M\(d\_\{1\}\+d\_\{2\}\)r\\log\\\!\\left\(2\(d\_\{1\}\+d\_\{2\}\)/\\delta^\{\\prime\}\\right\)\}\{T\_\{1\}\}\\right\\\},withC1=36​\(4​R2\+U2\)C\_\{1\}=36\(4R^\{2\}\+U^\{2\}\)andμi∗=EX∼𝒟​\[μi′​\(⟨X,Θi∗⟩\)\]\\mu\_\{i\}^\{\*\}=\\mathrm\{E\}\_\{\\mathrm\{X\}\\sim\\mathcal\{D\}\}\\left\[\\mu^\{\\prime\}\_\{i\}\\bigl\(\\langle\\mathrm\{X\},\\Theta\_\{i\}^\{\*\}\\rangle\\bigr\)\\right\]\.

Sinceδ′=δ/m\\delta^\{\\prime\}=\\delta/m, we have

log⁡\(2​\(d1\+d2\)δ′\)=log⁡\(2​m​\(d1\+d2\)δ\)\.\\log\\left\(\\frac\{2\(d\_\{1\}\+d\_\{2\}\)\}\{\\delta^\{\\prime\}\}\\right\)=\\log\\left\(\\frac\{2m\(d\_\{1\}\+d\_\{2\}\)\}\{\\delta\}\\right\)\.Consequently, the regularization parameters become

v=2​log⁡\(2​m​\(d1\+d2\)/δ\)\(4​R2\+U2\)​M​T1​\(d1\+d2\)v=\\sqrt\{\\frac\{2\\log\\\!\\left\(2m\(d\_\{1\}\+d\_\{2\}\)/\\delta\\right\)\}\{\(4R^\{2\}\+U^\{2\}\)MT\_\{1\}\(d\_\{1\}\+d\_\{2\}\)\}\}and

λT1=4​2​\(4​R2\+U2\)​M​\(d1\+d2\)​log⁡\(2​m​\(d1\+d2\)/δ\)T1\.\\lambda\_\{T\_\{1\}\}=4\\sqrt\{\\frac\{2\(4R^\{2\}\+U^\{2\}\)M\(d\_\{1\}\+d\_\{2\}\)\\log\\\!\\left\(2m\(d\_\{1\}\+d\_\{2\}\)/\\delta\\right\)\}\{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−δ\.\\displaystyle\\mathrm\{Pr\}\\left\(\\bigcap\_\{i=1\}^\{m\}\\mathcal\{E\}\_\{i\}\\right\)=1\-\\mathrm\{Pr\}\\left\(\\bigcup\_\{i=1\}^\{m\}\\mathcal\{E\}\_\{i\}^\{c\}\\right\)\\geq 1\-\\sum\_\{i=1\}^\{m\}\\mathrm\{Pr\}\(\\mathcal\{E\}\_\{i\}^\{c\}\)\\geq 1\-\\sum\_\{i=1\}^\{m\}\\frac\{\\delta\}\{m\}=1\-\\delta\.Thus, with probability at least1−δ1\-\\delta, the claimed estimation bound holds simultaneously for alli∈\[m\]i\\in\[m\]\.

Furthermore, under the assumed uniform lower boundμi′​\(z\)≥cμ\\mu^\{\\prime\}\_\{i\}\(z\)\\geq c\_\{\\mu\}over the relevant parameter domain,

μi∗=E​\[μi′​\(⟨X,Θi∗⟩\)\]≥cμ\>0\\mu\_\{i\}^\{\*\}=\\mathrm\{E\}\\left\[\\mu^\{\\prime\}\_\{i\}\\bigl\(\\langle X,\\Theta\_\{i\}^\{\*\}\\rangle\\bigr\)\\right\]\\geq c\_\{\\mu\}\>0for everyi∈\[m\]i\\in\[m\]\. This completes the proof\.□\\hfill\\square

After acquiring the estimatedΘ^i\\widehat\{\\Theta\}\_\{i\}in Algorithm[1](https://arxiv.org/html/2608.04324#alg1), we can obtain the corresponding SVD as

Θ^i=\[U^i,U^i,⟂\]​D^i​\[V^i,V^i,⟂\]⊤,\\widehat\{\\Theta\}\_\{i\}=\[\\widehat\{\\mathrm\{U\}\}\_\{i\},\\widehat\{\\mathrm\{U\}\}\_\{i,\\perp\}\]\\widehat\{\\mathrm\{D\}\}\_\{i\}\[\\widehat\{\\mathrm\{V\}\}\_\{i\},\\widehat\{\\mathrm\{V\}\}\_\{i,\\perp\}\]^\{\\top\},where

U^i∈ℝd1×r,U^i,⟂∈ℝd1×\(d1−r\),V^i∈ℝd2×r,V^i,⟂∈ℝd2×\(d2−r\)\.\\widehat\{\\mathrm\{U\}\}\_\{i\}\\in\\mathbb\{R\}^\{d\_\{1\}\\times r\},\\quad\\widehat\{\\mathrm\{U\}\}\_\{i,\\perp\}\\in\\mathbb\{R\}^\{d\_\{1\}\\times\(d\_\{1\}\-r\)\},\\quad\\widehat\{\\mathrm\{V\}\}\_\{i\}\\in\\mathbb\{R\}^\{d\_\{2\}\\times r\},\\quad\\widehat\{\\mathrm\{V\}\}\_\{i,\\perp\}\\in\\mathbb\{R\}^\{d\_\{2\}\\times\(d\_\{2\}\-r\)\}\.And we assume the SVD of the matrixΘi∗\\Theta^\{\*\}\_\{i\}can be represented as

Θi∗=Ui​Di​Vi⊤,\\Theta^\{\*\}\_\{i\}=\\mathrm\{U\}\_\{i\}\\mathrm\{D\}\_\{i\}\\mathrm\{V\}\_\{i\}^\{\\top\},whereUi∈ℝd1×r\\mathrm\{U\}\_\{i\}\\in\\mathbb\{R\}^\{d\_\{1\}\\times r\}andVi∈ℝd2×r\\mathrm\{V\}\_\{i\}\\in\\mathbb\{R\}^\{d\_\{2\}\\times r\}\. To transform the original generalized matrix bandits into generalized linear bandit problems, we penalize those covariates that are complementary toU^i\\widehat\{\\mathrm\{U\}\}\_\{i\}andV^i\\widehat\{\\mathrm\{V\}\}\_\{i\}\. Specifically, we could orthogonally rotate the inherent parameterΘi∗\\Theta\_\{i\}^\{\*\}as

Θi′=\[U^i,U^i,⟂\]⊤​Θi∗​\[V^i,V^i,⟂\]\.\\Theta^\{\\prime\}\_\{i\}=\[\\widehat\{\\mathrm\{U\}\}\_\{i\},\\widehat\{\\mathrm\{U\}\}\_\{i,\\perp\}\]^\{\\top\}\\Theta\_\{i\}^\{\*\}\[\\widehat\{\\mathrm\{V\}\}\_\{i\},\\widehat\{\\mathrm\{V\}\}\_\{i,\\perp\}\]\.
Define the total dimension and the effective dimension as

p=d1​d2,k=d1​d2−\(d1−r\)​\(d2−r\)\.p=d\_\{1\}d\_\{2\},\\quad k=d\_\{1\}d\_\{2\}\-\(d\_\{1\}\-r\)\(d\_\{2\}\-r\)\.For each objectivei∈\[m\]i\\in\[m\], letDr​r,iD\_\{rr,i\}denote therr\-th largest singular value of the objective\-specific parameter matrixΘi∗\\Theta\_\{i\}^\{\*\}, and defineDr​r=mini∈\[m\]⁡Dr​r,iD\_\{rr\}=\\min\_\{i\\in\[m\]\}D\_\{rr,i\}\. Then, for the true parameterθi∗\\theta^\{\*\}\_\{i\}after transformation, we denote the lastp−kp\-kentries asθi,k\+1:p∗\\theta^\{\*\}\_\{i,k\+1:p\}, such that

θi,k\+1:p∗=vec⁡\(\(Θi′\)r\+1:d1,r\+1:d2\)\.\\theta^\{\*\}\_\{i,k\+1:p\}=\\operatorname\{vec\}\\left\(\(\\Theta^\{\\prime\}\_\{i\}\)\_\{r\+1:d\_\{1\},\\;r\+1:d\_\{2\}\}\\right\)\.
###### Lemma 2\(Subspace perturbation to tail control\)

LetA=U​D​V⊤A=UDV^\{\\top\}have rankrrand smallest nonzero singular valueσr​\(A\)\>0\\sigma\_\{r\}\(A\)\>0\. LetA^\\widehat\{A\}be any matrix, and letU^\\widehat\{U\}andV^\\widehat\{V\}contain its leadingrrleft and right singular vectors\. Then

‖U^⟂⊤​U‖F,‖V^⟂⊤​V‖F≤2​‖A^−A‖Fσr​\(A\)\\\|\\widehat\{U\}\_\{\\perp\}^\{\\top\}U\\\|\_\{F\},\\,\\\|\\widehat\{V\}\_\{\\perp\}^\{\\top\}V\\\|\_\{F\}\\leq\\frac\{2\\\|\\widehat\{A\}\-A\\\|\_\{F\}\}\{\\sigma\_\{r\}\(A\)\}and

‖U^⟂⊤​U​D​V⊤​V^⟂‖F≤4​‖D‖op​‖A^−A‖F2σr​\(A\)2\.\\\|\\widehat\{U\}\_\{\\perp\}^\{\\top\}UDV^\{\\top\}\\widehat\{V\}\_\{\\perp\}\\\|\_\{F\}\\leq\\frac\{4\\\|D\\\|\_\{\\mathrm\{op\}\}\\\|\\widehat\{A\}\-A\\\|\_\{F\}^\{2\}\}\{\\sigma\_\{r\}\(A\)^\{2\}\}\.

#### Proof\.

LetA^r\\widehat\{A\}\_\{r\}be the best rank\-rrapproximation ofA^\\widehat\{A\}\. BecauseAAhas rankrr, the Eckart–Young theorem gives‖A^−A^r‖F≤‖A^−A‖F\\\|\\widehat\{A\}\-\\widehat\{A\}\_\{r\}\\\|\_\{F\}\\leq\\\|\\widehat\{A\}\-A\\\|\_\{F\}\. Therefore,

‖U^⟂⊤​A‖F≤‖A^−A‖F\+‖A^−A^r‖F≤2​‖A^−A‖F\.\\\|\\widehat\{U\}\_\{\\perp\}^\{\\top\}A\\\|\_\{F\}\\leq\\\|\\widehat\{A\}\-A\\\|\_\{F\}\+\\\|\\widehat\{A\}\-\\widehat\{A\}\_\{r\}\\\|\_\{F\}\\leq 2\\\|\\widehat\{A\}\-A\\\|\_\{F\}\.On the other hand,‖U^⟂⊤​A‖F≥σr​\(A\)​‖U^⟂⊤​U‖F\\\|\\widehat\{U\}\_\{\\perp\}^\{\\top\}A\\\|\_\{F\}\\geq\\sigma\_\{r\}\(A\)\\\|\\widehat\{U\}\_\{\\perp\}^\{\\top\}U\\\|\_\{F\}\. This proves the left\-subspace bound; applying the same argument toA⊤A^\{\\top\}proves the right\-subspace bound\. Finally,

‖U^⟂⊤​U​D​V⊤​V^⟂‖F≤‖U^⟂⊤​U‖F​‖D‖op​‖V⊤​V^⟂‖F,\\\|\\widehat\{U\}\_\{\\perp\}^\{\\top\}UDV^\{\\top\}\\widehat\{V\}\_\{\\perp\}\\\|\_\{F\}\\leq\\\|\\widehat\{U\}\_\{\\perp\}^\{\\top\}U\\\|\_\{F\}\\\|D\\\|\_\{\\mathrm\{op\}\}\\\|V^\{\\top\}\\widehat\{V\}\_\{\\perp\}\\\|\_\{F\},and substituting the two subspace bounds proves the result\.□\\hfill\\square

###### Lemma 3

Suppose that the conditions of Lemma[1](https://arxiv.org/html/2608.04324#Thmlem1)hold\. Then, with probability at least1−δ1\-\\delta, simultaneously for alli∈\[m\]i\\in\[m\],

∥θi,k\+1:p∗∥2≲M​\(d1\+d2\)​rT1​Dr​r2log\(m​\(d1\+d2\)δ\)=:S⟂\.\\left\\\|\\theta\_\{i,k\+1:p\}^\{\*\}\\right\\\|\_\{2\}\\lesssim\\frac\{M\(d\_\{1\}\+d\_\{2\}\)r\}\{T\_\{1\}D\_\{rr\}^\{2\}\}\\log\\left\(\\frac\{m\(d\_\{1\}\+d\_\{2\}\)\}\{\\delta\}\\right\)=:S\_\{\\perp\}\.

#### Proof\.

SetAi=μi∗​Θi∗A\_\{i\}=\\mu\_\{i\}^\{\*\}\\Theta\_\{i\}^\{\*\}andEi=Θ^i−AiE\_\{i\}=\\widehat\{\\Theta\}\_\{i\}\-A\_\{i\}\. Sinceμi∗\>0\\mu\_\{i\}^\{\*\}\>0,AiA\_\{i\}andΘi∗\\Theta\_\{i\}^\{\*\}have the same singular subspaces, andσr​\(Ai\)=μi∗​Di,r​r\\sigma\_\{r\}\(A\_\{i\}\)=\\mu\_\{i\}^\{\*\}D\_\{i,rr\}\. Moreover, the lastp−kp\-kcoordinates ofθi∗\\theta\_\{i\}^\{\*\}are the vectorization ofU^i,⟂⊤​Θi∗​V^i,⟂\\widehat\{\\mathrm\{U\}\}\_\{i,\\perp\}^\{\\top\}\\Theta\_\{i\}^\{\*\}\\widehat\{\\mathrm\{V\}\}\_\{i,\\perp\}\. Lemma[2](https://arxiv.org/html/2608.04324#Thmlem2)therefore gives

‖θi,k\+1:p∗‖2≤4​‖Di‖op​‖Ei‖F2\(μi∗\)2​Di,r​r2\.\\\|\\theta\_\{i,k\+1:p\}^\{\*\}\\\|\_\{2\}\\leq\\frac\{4\\\|\\mathrm\{D\}\_\{i\}\\\|\_\{\\mathrm\{op\}\}\\\|E\_\{i\}\\\|\_\{F\}^\{2\}\}\{\(\\mu\_\{i\}^\{\*\}\)^\{2\}D\_\{i,rr\}^\{2\}\}\.By Lemma[1](https://arxiv.org/html/2608.04324#Thmlem1), the event

‖Ei‖F2≤C1​M​\(d1\+d2\)​r​log⁡\(2​m​\(d1\+d2\)/δ\)T1\\\|E\_\{i\}\\\|\_\{F\}^\{2\}\\leq\\frac\{C\_\{1\}M\(d\_\{1\}\+d\_\{2\}\)r\\log\(2m\(d\_\{1\}\+d\_\{2\}\)/\\delta\)\}\{T\_\{1\}\}holds simultaneously for all objectives\. Usingμi∗≥cμ\\mu\_\{i\}^\{\*\}\\geq c\_\{\\mu\},Di,r​r≥Dr​rD\_\{i,rr\}\\geq D\_\{rr\}, and‖Di‖op≤Dmax\\\|\\mathrm\{D\}\_\{i\}\\\|\_\{\\mathrm\{op\}\}\\leq D\_\{\\max\}, and suppressing constants depending onC1C\_\{1\},cμc\_\{\\mu\}, andDmaxD\_\{\\max\}, proves the claim\.□\\hfill\\square

#### 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](https://arxiv.org/html/2608.04324#Thmassume2)–[4](https://arxiv.org/html/2608.04324#Thmassume4)hold\. Then, with probability at least1−δ1\-\\delta, for allt≥1t\\geq 1, all objectivesi∈\[m\]i\\in\[m\], and all armsX∈𝒳\\mathrm\{X\}\\in\\mathcal\{X\}, we have

\|μi​\(fi​\(X\)⊤​θi∗\)−μi​\(fi​\(X\)⊤​θ^t,i\)\|≤βt​‖fi​\(X\)‖Vt,i−1,\\left\|\\mu\_\{i\}\\\!\\left\(f\_\{i\}\(\\mathrm\{X\}\)^\{\\top\}\\theta\_\{i\}^\{\*\}\\right\)\-\\mu\_\{i\}\\\!\\left\(f\_\{i\}\(\\mathrm\{X\}\)^\{\\top\}\\hat\{\\theta\}\_\{t,i\}\\right\)\\right\|\\leq\\beta\_\{t\}\\\|f\_\{i\}\(\\mathrm\{X\}\)\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\},where

βt\+1=Lμ​\(R​k​log⁡\(1\+tk\)\+cμ​t2​λ⟂\+2​log⁡\(mδ\)\+\(λ0​S\+λ⟂​S⟂\)\)\.\\beta\_\{t\+1\}=L\_\{\\mu\}\\left\(R\\sqrt\{k\\log\\left\(1\+\\frac\{t\}\{k\}\\right\)\+\\frac\{c\_\{\\mu\}t\}\{2\\lambda\_\{\\perp\}\}\+2\\log\\left\(\\frac\{m\}\{\\delta\}\\right\)\}\+\\left\(\\sqrt\{\\lambda\_\{0\}\}S\+\\sqrt\{\\lambda\_\{\\perp\}\}S\_\{\\perp\}\\right\)\\right\)\.

#### Proof\.

Fix an objectivei∈\[m\]i\\in\[m\]and write

xτ,i=fi​\(Xτ\),x=fi​\(X\)\.x\_\{\\tau,i\}=f\_\{i\}\(\\mathrm\{X\}\_\{\\tau\}\),\\qquad x=f\_\{i\}\(\\mathrm\{X\}\)\.For notational simplicity, we omit the subscriptiiwhen there is no ambiguity\. At the beginning of roundtt, the estimatorθ^t,i\\hat\{\\theta\}\_\{t,i\}is computed from the observations collected in the previoust−1t\-1rounds\. Define

gt,i​\(θ\)=∑τ=1t−1μi​\(xτ,i⊤​θ\)​xτ,i\+Λ​θ\.g\_\{t,i\}\(\\theta\)=\\sum\_\{\\tau=1\}^\{t\-1\}\\mu\_\{i\}\(x\_\{\\tau,i\}^\{\\top\}\\theta\)x\_\{\\tau,i\}\+\\Lambda\\theta\.Sinceθ^t,i\\hat\{\\theta\}\_\{t,i\}minimizes the regularized negative log\-likelihood, the first\-order optimality condition gives

gt,i​\(θ^t,i\)=∑τ=1t−1yτ,i​xτ,i\.g\_\{t,i\}\(\\hat\{\\theta\}\_\{t,i\}\)=\\sum\_\{\\tau=1\}^\{t\-1\}y\_\{\\tau,i\}x\_\{\\tau,i\}\.Moreover,

gt,i​\(θi∗\)−gt,i​\(θ^t,i\)=−∑τ=1t−1ητ,i​xτ,i\+Λ​θi∗,g\_\{t,i\}\(\\theta\_\{i\}^\{\*\}\)\-g\_\{t,i\}\(\\hat\{\\theta\}\_\{t,i\}\)=\-\\sum\_\{\\tau=1\}^\{t\-1\}\\eta\_\{\\tau,i\}x\_\{\\tau,i\}\+\\Lambda\\theta\_\{i\}^\{\*\},where

ητ,i=yτ,i−μi​\(xτ,i⊤​θi∗\)\.\\eta\_\{\\tau,i\}=y\_\{\\tau,i\}\-\\mu\_\{i\}\(x\_\{\\tau,i\}^\{\\top\}\\theta\_\{i\}^\{\*\}\)\.
Next, by the fundamental theorem of calculus,

gt,i​\(θi∗\)−gt,i​\(θ^t,i\)=Gt,i​\(θi∗−θ^t,i\),g\_\{t,i\}\(\\theta\_\{i\}^\{\*\}\)\-g\_\{t,i\}\(\\hat\{\\theta\}\_\{t,i\}\)=G\_\{t,i\}\(\\theta\_\{i\}^\{\*\}\-\\hat\{\\theta\}\_\{t,i\}\),where

Gt,i=∫01∇gt,i​\(s​θi∗\+\(1−s\)​θ^t,i\)​𝑑s\.G\_\{t,i\}=\\int\_\{0\}^\{1\}\\nabla g\_\{t,i\}\\\!\\left\(s\\theta\_\{i\}^\{\*\}\+\(1\-s\)\\hat\{\\theta\}\_\{t,i\}\\right\)ds\.Sinceμ˙i​\(⋅\)≥cμ\\dot\{\\mu\}\_\{i\}\(\\cdot\)\\geq c\_\{\\mu\}, we have

Gt,i⪰cμ​∑τ=1t−1xτ,i​xτ,i⊤\+Λ⪰Vt,i=cμ2​∑τ=1t−1xτ,i​xτ,i⊤\+Λ\.G\_\{t,i\}\\succeq c\_\{\\mu\}\\sum\_\{\\tau=1\}^\{t\-1\}x\_\{\\tau,i\}x\_\{\\tau,i\}^\{\\top\}\+\\Lambda\\succeq\\mathrm\{V\}\_\{t,i\}=\\frac\{c\_\{\\mu\}\}\{2\}\\sum\_\{\\tau=1\}^\{t\-1\}x\_\{\\tau,i\}x\_\{\\tau,i\}^\{\\top\}\+\\Lambda\.Using the Lipschitzness ofμi​\(⋅\)\\mu\_\{i\}\(\\cdot\), we obtain

\|μi​\(x⊤​θi∗\)−μi​\(x⊤​θ^t,i\)\|\\displaystyle\\left\|\\mu\_\{i\}\(x^\{\\top\}\\theta\_\{i\}^\{\*\}\)\-\\mu\_\{i\}\(x^\{\\top\}\\hat\{\\theta\}\_\{t,i\}\)\\right\|≤Lμ​\|x⊤​\(θi∗−θ^t,i\)\|\\displaystyle\\leq L\_\{\\mu\}\\left\|x^\{\\top\}\(\\theta\_\{i\}^\{\*\}\-\\hat\{\\theta\}\_\{t,i\}\)\\right\|=Lμ​\|x⊤​Gt,i−1​\(gt,i​\(θi∗\)−gt,i​\(θ^t,i\)\)\|\\displaystyle=L\_\{\\mu\}\\left\|x^\{\\top\}G\_\{t,i\}^\{\-1\}\\big\(g\_\{t,i\}\(\\theta\_\{i\}^\{\*\}\)\-g\_\{t,i\}\(\\hat\{\\theta\}\_\{t,i\}\)\\big\)\\right\|≤Lμ​‖x‖Vt,i−1​‖gt,i​\(θi∗\)−gt,i​\(θ^t,i\)‖Vt,i−1\.\\displaystyle\\leq L\_\{\\mu\}\\\|x\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}\\left\\\|g\_\{t,i\}\(\\theta\_\{i\}^\{\*\}\)\-g\_\{t,i\}\(\\hat\{\\theta\}\_\{t,i\}\)\\right\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}\.Substituting the expression ofgt,i​\(θi∗\)−gt,i​\(θ^t,i\)g\_\{t,i\}\(\\theta\_\{i\}^\{\*\}\)\-g\_\{t,i\}\(\\hat\{\\theta\}\_\{t,i\}\)gives

\|μi​\(x⊤​θi∗\)−μi​\(x⊤​θ^t,i\)\|≤Lμ​‖x‖Vt,i−1​\(‖∑τ=1t−1ητ,i​xτ,i‖Vt,i−1\+‖Λ​θi∗‖Vt,i−1\)\.\\displaystyle\\left\|\\mu\_\{i\}\(x^\{\\top\}\\theta\_\{i\}^\{\*\}\)\-\\mu\_\{i\}\(x^\{\\top\}\\hat\{\\theta\}\_\{t,i\}\)\\right\|\\leq L\_\{\\mu\}\\\|x\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}\\left\(\\left\\\|\\sum\_\{\\tau=1\}^\{t\-1\}\\eta\_\{\\tau,i\}x\_\{\\tau,i\}\\right\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}\+\\\|\\Lambda\\theta\_\{i\}^\{\*\}\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}\\right\)\.\(12\)
We now bound the two terms inside the parentheses\. Since the noise is bounded byRR, it is conditionallyRR\-sub\-Gaussian\. By the self\-normalized martingale inequality\[Abbasi\-yadkoriet al\.,[2011](https://arxiv.org/html/2608.04324#bib.bib26)\], with probability at least1−δ/m1\-\\delta/m, simultaneously for allt≥1t\\geq 1,

‖∑τ=1t−1ητ,i​xτ,i‖Vt,i−1≤R​log⁡det\(Vt,i\)det\(Λ\)\+2​log⁡\(m/δ\)\.\\left\\\|\\sum\_\{\\tau=1\}^\{t\-1\}\\eta\_\{\\tau,i\}x\_\{\\tau,i\}\\right\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}\\leq R\\sqrt\{\\log\\frac\{\\det\(\\mathrm\{V\}\_\{t,i\}\)\}\{\\det\(\\Lambda\)\}\+2\\log\(m/\\delta\)\}\.\(13\)To bound the log\-determinant term, Lemma C\.5 ofKanget al\.\[[2022](https://arxiv.org/html/2608.04324#bib.bib268)\],λ0≥cμ/2\\lambda\_\{0\}\\geq c\_\{\\mu\}/2, andlog⁡\(1\+x\)≤x\\log\(1\+x\)\\leq xgive

log⁡det\(Vt,i\)det\(Λ\)≤k​log⁡\(1\+tk\)\+cμ​t2​λ⟂\.\\log\\frac\{\\det\(\\mathrm\{V\}\_\{t,i\}\)\}\{\\det\(\\Lambda\)\}\\leq k\\log\\left\(1\+\\frac\{t\}\{k\}\\right\)\+\\frac\{c\_\{\\mu\}t\}\{2\\lambda\_\{\\perp\}\}\.Substituting this bound into \([13](https://arxiv.org/html/2608.04324#A2.E13)\) gives

‖∑τ=1t−1ητ,i​xτ,i‖Vt,i−1≤R​k​log⁡\(1\+tk\)\+cμ​t2​λ⟂\+2​log⁡\(mδ\)\.\\left\\\|\\sum\_\{\\tau=1\}^\{t\-1\}\\eta\_\{\\tau,i\}x\_\{\\tau,i\}\\right\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}\\leq R\\sqrt\{k\\log\\left\(1\+\\frac\{t\}\{k\}\\right\)\+\\frac\{c\_\{\\mu\}t\}\{2\\lambda\_\{\\perp\}\}\+2\\log\\left\(\\frac\{m\}\{\\delta\}\\right\)\}\.\(14\)
For the regularization bias term, sinceVt,i⪰Λ,\\mathrm\{V\}\_\{t,i\}\\succeq\\Lambda,we have‖Λ​θi∗‖Vt,i−1≤‖θi∗‖Λ\.\\\|\\Lambda\\theta\_\{i\}^\{\*\}\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}\\leq\\\|\\theta\_\{i\}^\{\*\}\\\|\_\{\\Lambda\}\.By the construction of the transformed feature space,

‖\(θi∗\)1:k‖2≤S,‖\(θi∗\)k\+1:p‖2≤S⟂\.\\\|\(\\theta\_\{i\}^\{\*\}\)\_\{1:k\}\\\|\_\{2\}\\leq S,\\qquad\\\|\(\\theta\_\{i\}^\{\*\}\)\_\{k\+1:p\}\\\|\_\{2\}\\leq S\_\{\\perp\}\.Thus,

‖Λ​θi∗‖Vt,i−1≤‖θi∗‖Λ≤λ0​S\+λ⟂​S⟂\.\\\|\\Lambda\\theta\_\{i\}^\{\*\}\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}\\leq\\\|\\theta\_\{i\}^\{\*\}\\\|\_\{\\Lambda\}\\leq\\sqrt\{\\lambda\_\{0\}\}S\+\\sqrt\{\\lambda\_\{\\perp\}\}S\_\{\\perp\}\.\(15\)
Taking the Eq\. \([14](https://arxiv.org/html/2608.04324#A2.E14)\) and Eq\. \([15](https://arxiv.org/html/2608.04324#A2.E15)\) into Eq\. \([12](https://arxiv.org/html/2608.04324#A2.E12)\), with probability at least1−δ/m1\-\\delta/m, for the fixed objectiveiiand allt≥1t\\geq 1, allX∈𝒳\\mathrm\{X\}\\in\\mathcal\{X\},

\|μi​\(fi​\(X\)⊤​θi∗\)−μi​\(fi​\(X\)⊤​θ^t,i\)\|≤Lμ​\(R​k​log⁡\(1\+tk\)\+cμ​t2​λ⟂\+2​log⁡\(mδ\)\+\(λ0​S\+λ⟂​S⟂\)\)​‖fi​\(X\)‖Vt,i−1\.\\displaystyle\\left\|\\mu\_\{i\}\(f\_\{i\}\(\\mathrm\{X\}\)^\{\\top\}\\theta\_\{i\}^\{\*\}\)\-\\mu\_\{i\}\(f\_\{i\}\(\\mathrm\{X\}\)^\{\\top\}\\hat\{\\theta\}\_\{t,i\}\)\\right\|\\leq L\_\{\\mu\}\\Bigg\(R\\sqrt\{k\\log\\left\(1\+\\frac\{t\}\{k\}\\right\)\+\\frac\{c\_\{\\mu\}t\}\{2\\lambda\_\{\\perp\}\}\+2\\log\\left\(\\frac\{m\}\{\\delta\}\\right\)\}\+\\left\(\\sqrt\{\\lambda\_\{0\}\}S\+\\sqrt\{\\lambda\_\{\\perp\}\}S\_\{\\perp\}\\right\)\\Bigg\)\\\|f\_\{i\}\(\\mathrm\{X\}\)\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}\.Taking a union bound over all objectivesi∈\[m\]i\\in\[m\]completes the proof\.□\\hfill\\square

#### 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 factorWscaW^\{\\rm sca\}enters the analysis\.

###### Lemma 5

Suppose Assumption[5](https://arxiv.org/html/2608.04324#Thmassume5)holds\. For any armX∈𝒳\\mathrm\{X\}\\in\\mathcal\{X\}and objectivei∈\[m\]i\\in\[m\], define the objective\-wise gapΔi​\(X\)=μi​\(⟨X∗,Θi∗⟩\)−μi​\(⟨X,Θi∗⟩\)\.\\Delta\_\{i\}\(\\mathrm\{X\}\)=\\mu\_\{i\}\\\!\\left\(\\langle\\mathrm\{X\}\_\{\*\},\\Theta\_\{i\}^\{\*\}\\rangle\\right\)\-\\mu\_\{i\}\\\!\\left\(\\langle\\mathrm\{X\},\\Theta\_\{i\}^\{\*\}\\rangle\\right\)\.Letq=1\+wq=1\+w\. Then, for every objectivei∈\[m\]i\\in\[m\]and every armX∈𝒳\\mathrm\{X\}\\in\\mathcal\{X\},

Δi​\(X\)≤∑j=1mqm−j​Δj​\(X\)=∑j=1m\(1\+w\)m−j​Δj​\(X\)\.\\Delta\_\{i\}\(\\mathrm\{X\}\)\\leq\\sum\_\{j=1\}^\{m\}q^\{m\-j\}\\Delta\_\{j\}\(\\mathrm\{X\}\)=\\sum\_\{j=1\}^\{m\}\(1\+w\)^\{m\-j\}\\Delta\_\{j\}\(\\mathrm\{X\}\)\.Consequently, for any sequence of arms\{Xt\}t=1T2\\\{\\mathrm\{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\}\)=\\sum\_\{t=1\}^\{T\_\{2\}\}\\Delta\_\{i\}\(\\mathrm\{X\}\_\{t\}\)\\leq\\sum\_\{t=1\}^\{T\_\{2\}\}\\sum\_\{j=1\}^\{m\}\(1\+w\)^\{m\-j\}\\Delta\_\{j\}\(\\mathrm\{X\}\_\{t\}\),\\qquad\\forall i\\in\[m\]\.

#### Proof\.

Fix an arbitrary armX∈𝒳\\mathrm\{X\}\\in\\mathcal\{X\}\. For simplicity, writeΔi=Δi​\(X\)\\Delta\_\{i\}=\\Delta\_\{i\}\(\\mathrm\{X\}\)\. SinceX∗\\mathrm\{X\}\_\{\*\}is lexicographically optimal, no arm can strictly improve the first objective overX∗\\mathrm\{X\}\_\{\*\}\. Hence,

Δ1=μ1​\(⟨X∗,Θ1∗⟩\)−μ1​\(⟨X,Θ1∗⟩\)≥0\.\\Delta\_\{1\}=\\mu\_\{1\}\\\!\\left\(\\langle\\mathrm\{X\}\_\{\*\},\\Theta\_\{1\}^\{\*\}\\rangle\\right\)\-\\mu\_\{1\}\\\!\\left\(\\langle\\mathrm\{X\},\\Theta\_\{1\}^\{\*\}\\rangle\\right\)\\geq 0\.Moreover, Assumption[5](https://arxiv.org/html/2608.04324#Thmassume5)implies that, for everyi≥2i\\geq 2,

−Δi=μi​\(⟨X,Θi∗⟩\)−μi​\(⟨X∗,Θi∗⟩\)≤w​maxj∈\[i−1\]⁡Δj\.\-\\Delta\_\{i\}=\\mu\_\{i\}\\\!\\left\(\\langle\\mathrm\{X\},\\Theta\_\{i\}^\{\*\}\\rangle\\right\)\-\\mu\_\{i\}\\\!\\left\(\\langle\\mathrm\{X\}\_\{\*\},\\Theta\_\{i\}^\{\*\}\\rangle\\right\)\\leq w\\max\_\{j\\in\[i\-1\]\}\\Delta\_\{j\}\.
Forℓ∈\[m\]\\ell\\in\[m\], define

Pℓ=∑j=1ℓqℓ−j​Δj,Mℓ=maxj∈\[ℓ\]⁡Δj\.P\_\{\\ell\}=\\sum\_\{j=1\}^\{\\ell\}q^\{\\ell\-j\}\\Delta\_\{j\},\\qquad M\_\{\\ell\}=\\max\_\{j\\in\[\\ell\]\}\\Delta\_\{j\}\.We prove by induction that

Pℓ≥Mℓ,∀ℓ∈\[m\]\.P\_\{\\ell\}\\geq M\_\{\\ell\},\\qquad\\forall\\ell\\in\[m\]\.Whenℓ=1\\ell=1, we have

P1=Δ1=M1≥0\.P\_\{1\}=\\Delta\_\{1\}=M\_\{1\}\\geq 0\.SupposePℓ−1≥Mℓ−1P\_\{\\ell\-1\}\\geq M\_\{\\ell\-1\}holds for someℓ≥2\\ell\\geq 2\. Then

Pℓ=q​Pℓ−1\+Δℓ\.P\_\{\\ell\}=qP\_\{\\ell\-1\}\+\\Delta\_\{\\ell\}\.By the induction hypothesis and the trade\-off condition,

Pℓ≥q​Mℓ−1−w​Mℓ−1=\(q−w\)​Mℓ−1=Mℓ−1,P\_\{\\ell\}\\geq qM\_\{\\ell\-1\}\-wM\_\{\\ell\-1\}=\(q\-w\)M\_\{\\ell\-1\}=M\_\{\\ell\-1\},where we usedq=1\+wq=1\+w\. IfΔℓ≤Mℓ−1\\Delta\_\{\\ell\}\\leq M\_\{\\ell\-1\}, thenMℓ=Mℓ−1M\_\{\\ell\}=M\_\{\\ell\-1\}, and hencePℓ≥MℓP\_\{\\ell\}\\geq M\_\{\\ell\}\. IfΔℓ\>Mℓ−1\\Delta\_\{\\ell\}\>M\_\{\\ell\-1\}, thenMℓ=ΔℓM\_\{\\ell\}=\\Delta\_\{\\ell\}\. SinceMℓ−1≥Δ1≥0M\_\{\\ell\-1\}\\geq\\Delta\_\{1\}\\geq 0andPℓ−1≥Mℓ−1P\_\{\\ell\-1\}\\geq M\_\{\\ell\-1\}, we have

Pℓ=q​Pℓ−1\+Δℓ≥Δℓ=Mℓ\.P\_\{\\ell\}=qP\_\{\\ell\-1\}\+\\Delta\_\{\\ell\}\\geq\\Delta\_\{\\ell\}=M\_\{\\ell\}\.Thus,Pℓ≥MℓP\_\{\\ell\}\\geq M\_\{\\ell\}for allℓ∈\[m\]\\ell\\in\[m\]\.

Takingℓ=m\\ell=m, we obtain

∑j=1mqm−j​Δj=Pm≥Mm=maxj∈\[m\]⁡Δj\.\\sum\_\{j=1\}^\{m\}q^\{m\-j\}\\Delta\_\{j\}=P\_\{m\}\\geq M\_\{m\}=\\max\_\{j\\in\[m\]\}\\Delta\_\{j\}\.Therefore, for everyi∈\[m\]i\\in\[m\],

Δi≤maxj∈\[m\]⁡Δj≤∑j=1mqm−j​Δj\.\\Delta\_\{i\}\\leq\\max\_\{j\\in\[m\]\}\\Delta\_\{j\}\\leq\\sum\_\{j=1\}^\{m\}q^\{m\-j\}\\Delta\_\{j\}\.Substituting backq=1\+wq=1\+wgives

Δi​\(X\)≤∑j=1m\(1\+w\)m−j​Δj​\(X\)\.\\Delta\_\{i\}\(\\mathrm\{X\}\)\\leq\\sum\_\{j=1\}^\{m\}\(1\+w\)^\{m\-j\}\\Delta\_\{j\}\(\\mathrm\{X\}\)\.
Finally, applying this pointwise inequality to each played armXt\\mathrm\{X\}\_\{t\}and summing overt=1,…,T2t=1,\\ldots,T\_\{2\}yields

Ri​\(T2\)=∑t=1T2Δi​\(Xt\)≤∑t=1T2∑j=1m\(1\+w\)m−j​Δj​\(Xt\)\.R\_\{i\}\(T\_\{2\}\)=\\sum\_\{t=1\}^\{T\_\{2\}\}\\Delta\_\{i\}\(\\mathrm\{X\}\_\{t\}\)\\leq\\sum\_\{t=1\}^\{T\_\{2\}\}\\sum\_\{j=1\}^\{m\}\(1\+w\)^\{m\-j\}\\Delta\_\{j\}\(\\mathrm\{X\}\_\{t\}\)\.This completes the proof\.□\\hfill\\square

By Lemma[5](https://arxiv.org/html/2608.04324#Thmlem5),

Ri​\(T2\)≤∑t=1T2∑i=1m\(1\+w\)m−i​\(μi​\(⟨X∗,Θi∗⟩\)−μi​\(⟨Xt,Θi∗⟩\)\)\.\\displaystyle R\_\{i\}\(T\_\{2\}\)\\leq\\sum\_\{t=1\}^\{T\_\{2\}\}\\sum\_\{i=1\}^\{m\}\(1\+w\)^\{m\-i\}\\left\(\\mu\_\{i\}\\\!\\left\(\\left\\langle X\_\{\*\},\\Theta\_\{i\}^\{\*\}\\right\\rangle\\right\)\-\\mu\_\{i\}\\\!\\left\(\\left\\langle\\mathrm\{X\}\_\{t\},\\Theta\_\{i\}^\{\*\}\\right\\rangle\\right\)\\right\)\.\(16\)
Consider the high\-probability event in Lemma[4](https://arxiv.org/html/2608.04324#Thmlem4), on which, for everyt∈\[T2\]t\\in\[T\_\{2\}\],j∈\[m\]j\\in\[m\], andX∈𝒳\\mathrm\{X\}\\in\\mathcal\{X\},

\|y^t,j​\(X\)−μj​\(⟨X,Θj∗⟩\)\|≤βt​‖fj​\(X\)‖Vt,j−1=ct,j​\(X\)\.\\left\|\\hat\{y\}\_\{t,j\}\(\\mathrm\{X\}\)\-\\mu\_\{j\}\\\!\\left\(\\left\\langle\\mathrm\{X\},\\Theta\_\{j\}^\{\*\}\\right\\rangle\\right\)\\right\|\\leq\\beta\_\{t\}\\\|f\_\{j\}\(\\mathrm\{X\}\)\\\|\_\{\\mathrm\{V\}\_\{t,j\}^\{\-1\}\}=c\_\{t,j\}\(\\mathrm\{X\}\)\.It follows that

∑j=1m\(1\+w\)m−j​μj​\(⟨X,Θj∗⟩\)≤UCBt​\(X,w\)\\sum\_\{j=1\}^\{m\}\(1\+w\)^\{m\-j\}\\mu\_\{j\}\\\!\\left\(\\left\\langle\\mathrm\{X\},\\Theta\_\{j\}^\{\*\}\\right\\rangle\\right\)\\leq\\mathrm\{UCB\}\_\{t\}\(\\mathrm\{X\},w\)for everyX∈𝒳\\mathrm\{X\}\\in\\mathcal\{X\}\. Moreover,

UCBt​\(X,w\)−∑j=1m\(1\+w\)m−j​μj​\(⟨X,Θj∗⟩\)\\displaystyle\\mathrm\{UCB\}\_\{t\}\(\\mathrm\{X\},w\)\-\\sum\_\{j=1\}^\{m\}\(1\+w\)^\{m\-j\}\\mu\_\{j\}\\\!\\left\(\\left\\langle\\mathrm\{X\},\\Theta\_\{j\}^\{\*\}\\right\\rangle\\right\)=∑j=1m\(1\+w\)m−j​\[y^t,j​\(X\)\+ct,j​\(X\)−μj​\(⟨X,Θj∗⟩\)\]\\displaystyle=\\sum\_\{j=1\}^\{m\}\(1\+w\)^\{m\-j\}\\left\[\\hat\{y\}\_\{t,j\}\(\\mathrm\{X\}\)\+c\_\{t,j\}\(\\mathrm\{X\}\)\-\\mu\_\{j\}\\\!\\left\(\\left\\langle\\mathrm\{X\},\\Theta\_\{j\}^\{\*\}\\right\\rangle\\right\)\\right\]≤2​∑j=1m\(1\+w\)m−j​ct,j​\(X\)\.\\displaystyle\\leq 2\\sum\_\{j=1\}^\{m\}\(1\+w\)^\{m\-j\}c\_\{t,j\}\(\\mathrm\{X\}\)\.\(17\)
Using \([B](https://arxiv.org/html/2608.04324#A2.Ex84)\) and the arm\-selection rule

Xt∈argmaxX∈𝒳UCBt​\(X,w\),\\mathrm\{X\}\_\{t\}\\in\\operatorname\*\{argmax\}\_\{\\mathrm\{X\}\\in\\mathcal\{X\}\}\\mathrm\{UCB\}\_\{t\}\(\\mathrm\{X\},w\),we obtain

Ri​\(T2\)\\displaystyle R\_\{i\}\(T\_\{2\}\)≤∑t=1T2\[UCBt​\(X∗,w\)−∑j=1m\(1\+w\)m−j​μj​\(⟨Xt,Θj∗⟩\)\]\\displaystyle\\leq\\sum\_\{t=1\}^\{T\_\{2\}\}\\left\[\\mathrm\{UCB\}\_\{t\}\(\\mathrm\{X\}\_\{\*\},w\)\-\\sum\_\{j=1\}^\{m\}\(1\+w\)^\{m\-j\}\\mu\_\{j\}\\\!\\left\(\\left\\langle\\mathrm\{X\}\_\{t\},\\Theta\_\{j\}^\{\*\}\\right\\rangle\\right\)\\right\]≤∑t=1T2\[UCBt​\(Xt,w\)−∑j=1m\(1\+w\)m−j​μj​\(⟨Xt,Θj∗⟩\)\]\\displaystyle\\leq\\sum\_\{t=1\}^\{T\_\{2\}\}\\left\[\\mathrm\{UCB\}\_\{t\}\(\\mathrm\{X\}\_\{t\},w\)\-\\sum\_\{j=1\}^\{m\}\(1\+w\)^\{m\-j\}\\mu\_\{j\}\\\!\\left\(\\left\\langle\\mathrm\{X\}\_\{t\},\\Theta\_\{j\}^\{\*\}\\right\\rangle\\right\)\\right\]≤2​∑t=1T2∑j=1m\(1\+w\)m−j​βt​‖fj​\(Xt\)‖Vt,j−1\.\\displaystyle\\leq 2\\sum\_\{t=1\}^\{T\_\{2\}\}\\sum\_\{j=1\}^\{m\}\(1\+w\)^\{m\-j\}\\beta\_\{t\}\\\|f\_\{j\}\(\\mathrm\{X\}\_\{t\}\)\\\|\_\{\\mathrm\{V\}\_\{t,j\}^\{\-1\}\}\.Sinceβt≤βT\\beta\_\{t\}\\leq\\beta\_\{T\}, interchanging the two sums and applying the Cauchy–Schwarz inequality yield

Ri​\(T2\)\\displaystyle R\_\{i\}\(T\_\{2\}\)≤2​βT​∑j=1m\(1\+w\)m−j​∑t=1T2‖fj​\(Xt\)‖Vt,j−1\\displaystyle\\leq 2\\beta\_\{T\}\\sum\_\{j=1\}^\{m\}\(1\+w\)^\{m\-j\}\\sum\_\{t=1\}^\{T\_\{2\}\}\\\|f\_\{j\}\(\\mathrm\{X\}\_\{t\}\)\\\|\_\{\\mathrm\{V\}\_\{t,j\}^\{\-1\}\}≤2​βT​T2​∑j=1m\(1\+w\)m−j​\(∑t=1T2‖fj​\(Xt\)‖Vt,j−12\)1/2\.\\displaystyle\\leq 2\\beta\_\{T\}\\sqrt\{T\_\{2\}\}\\sum\_\{j=1\}^\{m\}\(1\+w\)^\{m\-j\}\\left\(\\sum\_\{t=1\}^\{T\_\{2\}\}\\\|f\_\{j\}\(\\mathrm\{X\}\_\{t\}\)\\\|\_\{\\mathrm\{V\}\_\{t,j\}^\{\-1\}\}^\{2\}\\right\)^\{1/2\}\.\(18\)
For each objective, the standard elliptical\-potential argument\[Abbasi\-yadkoriet al\.,[2011](https://arxiv.org/html/2608.04324#bib.bib26), Lemma 11\], followed by the anisotropic log\-determinant bound of Lemma C\.5 inKanget al\.\[[2022](https://arxiv.org/html/2608.04324#bib.bib268)\], gives

∑t=1T2‖fi​\(Xt\)‖Vt,i−12≤4cμ​\(k​log⁡\(1\+Tk\)\+cμ​T2​λ⟂\)\.\\sum\_\{t=1\}^\{T\_\{2\}\}\\\|f\_\{i\}\(\\mathrm\{X\}\_\{t\}\)\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}^\{2\}\\leq\\frac\{4\}\{c\_\{\\mu\}\}\\left\(k\\log\\left\(1\+\\frac\{T\}\{k\}\\right\)\+\\frac\{c\_\{\\mu\}T\}\{2\\lambda\_\{\\perp\}\}\\right\)\.Thus, we have

Ri​\(T2\)≤∑i=1m\(1\+w\)m−i​2​βT​T2​4cμ​\(k​log⁡\(1\+Tk\)\+cμ​T2​λ⟂\)\\displaystyle R\_\{i\}\(T\_\{2\}\)\\leq\\sum\_\{i=1\}^\{m\}\(1\+w\)^\{m\-i\}2\\beta\_\{T\}\\sqrt\{T\_\{2\}\}\\sqrt\{\\frac\{4\}\{c\_\{\\mu\}\}\\left\(k\\log\\left\(1\+\\frac\{T\}\{k\}\\right\)\+\\frac\{c\_\{\\mu\}T\}\{2\\lambda\_\{\\perp\}\}\\right\)\}Taking the firstT1T\_\{1\}rounds andμi​\(⋅\)≤U\\mu\_\{i\}\(\\cdot\)\\leq Uinto the total regret, we have

Ri​\(T\)\\displaystyle R\_\{i\}\(T\)≤2​U​T1\+∑i=1m\(1\+w\)m−i​4​βT​T2​kcμ​log⁡\(1\+Tk\)\+T2​λ⟂\\displaystyle\\leq 2UT\_\{1\}\+\\sum\_\{i=1\}^\{m\}\(1\+w\)^\{m\-i\}4\\beta\_\{T\}\\sqrt\{T\_\{2\}\}\\sqrt\{\\frac\{k\}\{c\_\{\\mu\}\}\\log\\left\(1\+\\frac\{T\}\{k\}\\right\)\+\\frac\{T\}\{2\\lambda\_\{\\perp\}\}\}

#### Step 4: Parameter choice and completion of the proof\.

We now substitute the choices ofT1T\_\{1\},λ⟂\\lambda\_\{\\perp\}, andS⟂S\_\{\\perp\}into the regret bound\. Define

Wsca:=∑j=1m\(1\+w\)m−j,A:=M​\(d1\+d2\)​rDr​r2​log⁡\(m​\(d1\+d2\)δ\)\.W^\{\\rm sca\}:=\\sum\_\{j=1\}^\{m\}\(1\+w\)^\{m\-j\},\\qquad A:=\\frac\{M\(d\_\{1\}\+d\_\{2\}\)r\}\{D\_\{rr\}^\{2\}\}\\log\\\!\\left\(\\frac\{m\(d\_\{1\}\+d\_\{2\}\)\}\{\\delta\}\\right\)\.By the choice of the exploration lengthT1≍A​TT\_\{1\}\\asymp\\sqrt\{AT\}and

S⟂=\(d1\+d2\)​M​rT1​Dr​r2​log⁡\(m​\(d1\+d2\)δ\)=AT1,S\_\{\\perp\}=\\frac\{\(d\_\{1\}\+d\_\{2\}\)Mr\}\{T\_\{1\}D\_\{rr\}^\{2\}\}\\log\\\!\\left\(\\frac\{m\(d\_\{1\}\+d\_\{2\}\)\}\{\\delta\}\\right\)=\\frac\{A\}\{T\_\{1\}\},we have

S⟂≍AT\.S\_\{\\perp\}\\asymp\\sqrt\{\\frac\{A\}\{T\}\}\.
Recall that

λ⟂=cμ​Tk​log⁡\(1\+cμ​T/\(k​λ0\)\)\.\\lambda\_\{\\perp\}=\\frac\{c\_\{\\mu\}T\}\{k\\log\\\!\\left\(1\+c\_\{\\mu\}T/\(k\\lambda\_\{0\}\)\\right\)\}\.Therefore,

cμ​T2​λ⟂=k2​log⁡\(1\+cμ​Tk​λ0\),\\frac\{c\_\{\\mu\}T\}\{2\\lambda\_\{\\perp\}\}=\\frac\{k\}\{2\}\\log\\\!\\left\(1\+\\frac\{c\_\{\\mu\}T\}\{k\\lambda\_\{0\}\}\\right\),and hence the confidence radius satisfies

βT\\displaystyle\\beta\_\{T\}≤Lμ​\(R​k​log⁡\(1\+Tk\)\+cμ​T2​λ⟂\+2​log⁡\(mδ\)\+λ0​S\+λ⟂​S⟂\)\\displaystyle\\leq L\_\{\\mu\}\\left\(R\\sqrt\{k\\log\\\!\\left\(1\+\\frac\{T\}\{k\}\\right\)\+\\frac\{c\_\{\\mu\}T\}\{2\\lambda\_\{\\perp\}\}\+2\\log\\\!\\left\(\\frac\{m\}\{\\delta\}\\right\)\}\+\\sqrt\{\\lambda\_\{0\}\}S\+\\sqrt\{\\lambda\_\{\\perp\}\}S\_\{\\perp\}\\right\)=O~​\(Lμ​\(R​k\+λ0​S\+λ⟂​S⟂\)\)\.\\displaystyle=\\widetilde\{O\}\\left\(L\_\{\\mu\}\\left\(R\\sqrt\{k\}\+\\sqrt\{\\lambda\_\{0\}\}S\+\\sqrt\{\\lambda\_\{\\perp\}\}S\_\{\\perp\}\\right\)\\right\)\.Furthermore,

λ⟂​S⟂=cμ​Tk​log⁡\(1\+cμ​T/\(k​λ0\)\)⋅AT=O~​\(cμ​Ak\)\.\\sqrt\{\\lambda\_\{\\perp\}\}S\_\{\\perp\}=\\sqrt\{\\frac\{c\_\{\\mu\}T\}\{k\\log\\\!\\left\(1\+c\_\{\\mu\}T/\(k\\lambda\_\{0\}\)\\right\)\}\}\\cdot\\sqrt\{\\frac\{A\}\{T\}\}=\\widetilde\{O\}\\left\(\\sqrt\{\\frac\{c\_\{\\mu\}A\}\{k\}\}\\right\)\.Thus,

βT=O~​\(Lμ​\(R​k\+λ0​S\+cμ​Ak\)\)\.\\beta\_\{T\}=\\widetilde\{O\}\\left\(L\_\{\\mu\}\\left\(R\\sqrt\{k\}\+\\sqrt\{\\lambda\_\{0\}\}S\+\\sqrt\{\\frac\{c\_\{\\mu\}A\}\{k\}\}\\right\)\\right\)\.
On the other hand, the elliptical\-potential term in the regret bound can be simplified as

kcμ​log⁡\(1\+Tk\)\+T2​λ⟂\\displaystyle\\sqrt\{\\frac\{k\}\{c\_\{\\mu\}\}\\log\\\!\\left\(1\+\\frac\{T\}\{k\}\\right\)\+\\frac\{T\}\{2\\lambda\_\{\\perp\}\}\}=kcμ​log⁡\(1\+Tk\)\+k2​cμ​log⁡\(1\+cμ​Tk​λ0\)\\displaystyle=\\sqrt\{\\frac\{k\}\{c\_\{\\mu\}\}\\log\\\!\\left\(1\+\\frac\{T\}\{k\}\\right\)\+\\frac\{k\}\{2c\_\{\\mu\}\}\\log\\\!\\left\(1\+\\frac\{c\_\{\\mu\}T\}\{k\\lambda\_\{0\}\}\\right\)\}=O~​\(kcμ\)\.\\displaystyle=\\widetilde\{O\}\\left\(\\sqrt\{\\frac\{k\}\{c\_\{\\mu\}\}\}\\right\)\.UsingT2≤TT\_\{2\}\\leq T, we obtain

Ri​\(T\)\\displaystyle R\_\{i\}\(T\)≤2​U​T1\+4​Wsca​βT​T2​kcμ​log⁡\(1\+Tk\)\+T2​λ⟂\\displaystyle\\leq 2UT\_\{1\}\+4W^\{\\rm sca\}\\beta\_\{T\}\\sqrt\{T\_\{2\}\}\\sqrt\{\\frac\{k\}\{c\_\{\\mu\}\}\\log\\\!\\left\(1\+\\frac\{T\}\{k\}\\right\)\+\\frac\{T\}\{2\\lambda\_\{\\perp\}\}\}=O~​\(U​A​T\+Wsca​Lμ​\(R​kcμ\+S​λ0​kcμ\+A\)​T\)\.\\displaystyle=\\widetilde\{O\}\\left\(U\\sqrt\{AT\}\+W^\{\\rm sca\}L\_\{\\mu\}\\left\(\\frac\{Rk\}\{\\sqrt\{c\_\{\\mu\}\}\}\+S\\sqrt\{\\frac\{\\lambda\_\{0\}k\}\{c\_\{\\mu\}\}\}\+\\sqrt\{A\}\\right\)\\sqrt\{T\}\\right\)\.Substituting the definition ofAAgives

Ri​\(T\)=O~​\(\[U​M​\(d1\+d2\)​rDr​r\+Wsca​Lμ​\(R​kcμ\+S​λ0​kcμ\+M​\(d1\+d2\)​rDr​r\)\]​T\)\.R\_\{i\}\(T\)=\\widetilde\{O\}\\left\(\\left\[U\\frac\{\\sqrt\{M\(d\_\{1\}\+d\_\{2\}\)r\}\}\{D\_\{rr\}\}\+W^\{\\rm sca\}L\_\{\\mu\}\\left\(\\frac\{Rk\}\{\\sqrt\{c\_\{\\mu\}\}\}\+S\\sqrt\{\\frac\{\\lambda\_\{0\}k\}\{c\_\{\\mu\}\}\}\+\\frac\{\\sqrt\{M\(d\_\{1\}\+d\_\{2\}\)r\}\}\{D\_\{rr\}\}\\right\)\\right\]\\sqrt\{T\}\\right\)\.WhenU,Lμ,R,cμ,λ0U,L\_\{\\mu\},R,c\_\{\\mu\},\\lambda\_\{0\}, andSSare treated as constants, and sinceWsca≥1W^\{\\rm sca\}\\geq 1, this simplifies to

Ri​\(T\)=O~​\(Wsca​\(k\+M​\(d1\+d2\)​rDr​r\)​T\)\.R\_\{i\}\(T\)=\\widetilde\{O\}\\left\(W^\{\\rm sca\}\\left\(k\+\\frac\{\\sqrt\{M\(d\_\{1\}\+d\_\{2\}\)r\}\}\{D\_\{rr\}\}\\right\)\\sqrt\{T\}\\right\)\.Finally, sincek=\(d1\+d2\)​r−r2≍\(d1\+d2\)​rk=\(d\_\{1\}\+d\_\{2\}\)r\-r^\{2\}\\asymp\(d\_\{1\}\+d\_\{2\}\)r, under the standard scaling condition

M​\(d1\+d2\)​rDr​r≲\(d1\+d2\)​r,\\frac\{\\sqrt\{M\(d\_\{1\}\+d\_\{2\}\)r\}\}\{D\_\{rr\}\}\\lesssim\(d\_\{1\}\+d\_\{2\}\)r,we obtain

Ri​\(T\)=O~​\(Wsca​\(d1\+d2\)​r​T\)\.R\_\{i\}\(T\)=\\widetilde\{O\}\\left\(W^\{\\rm sca\}\(d\_\{1\}\+d\_\{2\}\)r\\sqrt\{T\}\\right\)\.The proof of Theorem[1](https://arxiv.org/html/2608.04324#Thmthm1)is finished\.□\\hfill\\square

## Appendix CProof of Theorem[2](https://arxiv.org/html/2608.04324#Thmthm2)

#### 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 resultingmmpotential budgets, and substitute the same parameter choices as in Theorem[1](https://arxiv.org/html/2608.04324#Thmthm1)\.

#### Step 1: Online estimation and reward confidence\.

###### Lemma 6\(One\-step estimation recursion\)

Fix an objectivei∈\[m\]i\\in\[m\]and defineat=fi​\(Xt\)⊤​\(θ^t,i−θi∗\)a\_\{t\}=f\_\{i\}\(\\mathrm\{X\}\_\{t\}\)^\{\\top\}\(\\hat\{\\theta\}\_\{t,i\}\-\\theta\_\{i\}^\{\*\}\)\. Under Assumptions[2](https://arxiv.org/html/2608.04324#Thmassume2)–[4](https://arxiv.org/html/2608.04324#Thmassume4),

‖θ^t\+1,i−θi∗‖Vt\+1,i2\\displaystyle\\\|\\hat\{\\theta\}\_\{t\+1,i\}\-\\theta\_\{i\}^\{\*\}\\\|\_\{\\mathrm\{V\}\_\{t\+1,i\}\}^\{2\}≤‖θ^t,i−θi∗‖Vt,i2−cμ2​at2\+4​\(U\+R\)2​‖fi​\(Xt\)‖Vt\+1,i−12\+2​ηt,i​at\.\\displaystyle\\leq\\\|\\hat\{\\theta\}\_\{t,i\}\-\\theta\_\{i\}^\{\*\}\\\|\_\{\\mathrm\{V\}\_\{t,i\}\}^\{2\}\-\\frac\{c\_\{\\mu\}\}\{2\}a\_\{t\}^\{2\}\+4\(U\+R\)^\{2\}\\\|f\_\{i\}\(\\mathrm\{X\}\_\{t\}\)\\\|\_\{\\mathrm\{V\}\_\{t\+1,i\}^\{\-1\}\}^\{2\}\+2\\eta\_\{t,i\}a\_\{t\}\.

#### Proof\.

Fix an objectivei∈\[m\]i\\in\[m\]\. For simplicity, we writext=fi​\(Xt\)x\_\{t\}=f\_\{i\}\(\\mathrm\{X\}\_\{t\}\),θ^t=θ^t,i\\hat\{\\theta\}\_\{t\}=\\hat\{\\theta\}\_\{t,i\},θ∗=θi∗\\theta^\{\*\}=\\theta\_\{i\}^\{\*\},Vt=Vt,i\\mathrm\{V\}\_\{t\}=\\mathrm\{V\}\_\{t,i\}, andηt=ηt,i\\eta\_\{t\}=\\eta\_\{t,i\}\. Define the instantaneous loss

ℓt,i​\(θ\)=−yt,i​xt⊤​θ\+∫0xt⊤​θμi​\(z\)​𝑑z\.\\ell\_\{t,i\}\(\\theta\)=\-y\_\{t,i\}x\_\{t\}^\{\\top\}\\theta\+\\int\_\{0\}^\{x\_\{t\}^\{\\top\}\\theta\}\\mu\_\{i\}\(z\)\\,dz\.Then

∇ℓt,i​\(θ\)=\(μi​\(xt⊤​θ\)−yt,i\)​xt,\\nabla\\ell\_\{t,i\}\(\\theta\)=\\big\(\\mu\_\{i\}\(x\_\{t\}^\{\\top\}\\theta\)\-y\_\{t,i\}\\big\)x\_\{t\},which is consistent with Eq\. \([9](https://arxiv.org/html/2608.04324#S4.E9)\)\. Sinceμ˙i​\(z\)≥cμ\\dot\{\\mu\}\_\{i\}\(z\)\\geq c\_\{\\mu\}, the functionℓt,i​\(⋅\)\\ell\_\{t,i\}\(\\cdot\)is strongly convex along the directionxtx\_\{t\}\. Thus, for anyθ1,θ2\\theta\_\{1\},\\theta\_\{2\},

ℓt,i​\(θ1\)−ℓt,i​\(θ2\)≤∇ℓt,i​\(θ1\)⊤​\(θ1−θ2\)−cμ2​\(xt⊤​θ1−xt⊤​θ2\)2\.\\ell\_\{t,i\}\(\\theta\_\{1\}\)\-\\ell\_\{t,i\}\(\\theta\_\{2\}\)\\leq\\nabla\\ell\_\{t,i\}\(\\theta\_\{1\}\)^\{\\top\}\(\\theta\_\{1\}\-\\theta\_\{2\}\)\-\\frac\{c\_\{\\mu\}\}\{2\}\\big\(x\_\{t\}^\{\\top\}\\theta\_\{1\}\-x\_\{t\}^\{\\top\}\\theta\_\{2\}\\big\)^\{2\}\.Takingθ1=θ^t\\theta\_\{1\}=\\hat\{\\theta\}\_\{t\}andθ2=θ∗\\theta\_\{2\}=\\theta^\{\*\}gives

ℓt,i​\(θ^t\)−ℓt,i​\(θ∗\)≤∇ℓt,i​\(θ^t\)⊤​\(θ^t−θ∗\)−cμ2​\(xt⊤​θ^t−xt⊤​θ∗\)2\.\\ell\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)\-\\ell\_\{t,i\}\(\\theta^\{\*\}\)\\leq\\nabla\\ell\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)^\{\\top\}\(\\hat\{\\theta\}\_\{t\}\-\\theta^\{\*\}\)\-\\frac\{c\_\{\\mu\}\}\{2\}\\big\(x\_\{t\}^\{\\top\}\\hat\{\\theta\}\_\{t\}\-x\_\{t\}^\{\\top\}\\theta^\{\*\}\\big\)^\{2\}\.
Letft,i​\(θ\)=E​\[ℓt,i​\(θ\)\]f\_\{t,i\}\(\\theta\)=\\mathrm\{E\}\[\\ell\_\{t,i\}\(\\theta\)\]\. SinceE​\[yt,i\]=μi​\(xt⊤​θ∗\)\\mathrm\{E\}\[y\_\{t,i\}\]=\\mu\_\{i\}\(x\_\{t\}^\{\\top\}\\theta^\{\*\}\), the parameterθ∗\\theta^\{\*\}minimizesft,i​\(θ\)f\_\{t,i\}\(\\theta\), and hence

ft,i​\(θ^t\)−ft,i​\(θ∗\)≥0\.f\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)\-f\_\{t,i\}\(\\theta^\{\*\}\)\\geq 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\\leq\\nabla f\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)^\{\\top\}\(\\hat\{\\theta\}\_\{t\}\-\\theta^\{\*\}\)\-\\frac\{c\_\{\\mu\}\}\{2\}\\big\(x\_\{t\}^\{\\top\}\\hat\{\\theta\}\_\{t\}\-x\_\{t\}^\{\\top\}\\theta^\{\*\}\\big\)^\{2\}\.By adding and subtracting∇ℓt,i​\(θ^t\)\\nabla\\ell\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\), we obtain

0≤\(∇ft,i​\(θ^t\)−∇ℓt,i​\(θ^t\)\)⊤​\(θ^t−θ∗\)\+∇ℓt,i​\(θ^t\)⊤​\(θ^t−θ∗\)−cμ2​\(xt⊤​θ^t−xt⊤​θ∗\)2\.\\displaystyle 0\\leq\\big\(\\nabla f\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)\-\\nabla\\ell\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)\\big\)^\{\\top\}\(\\hat\{\\theta\}\_\{t\}\-\\theta^\{\*\}\)\+\\nabla\\ell\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)^\{\\top\}\(\\hat\{\\theta\}\_\{t\}\-\\theta^\{\*\}\)\-\\frac\{c\_\{\\mu\}\}\{2\}\\big\(x\_\{t\}^\{\\top\}\\hat\{\\theta\}\_\{t\}\-x\_\{t\}^\{\\top\}\\theta^\{\*\}\\big\)^\{2\}\.Moreover,

∇ft,i​\(θ^t\)=\(μi​\(xt⊤​θ^t\)−μi​\(xt⊤​θ∗\)\)​xt,\\nabla f\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)=\\big\(\\mu\_\{i\}\(x\_\{t\}^\{\\top\}\\hat\{\\theta\}\_\{t\}\)\-\\mu\_\{i\}\(x\_\{t\}^\{\\top\}\\theta^\{\*\}\)\\big\)x\_\{t\},and therefore

∇ft,i​\(θ^t\)−∇ℓt,i​\(θ^t\)=ηt​xt\.\\nabla f\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)\-\\nabla\\ell\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)=\\eta\_\{t\}x\_\{t\}\.Hence,

0≤ηt​\(xt⊤​θ^t−xt⊤​θ∗\)\+∇ℓt,i​\(θ^t\)⊤​\(θ^t−θ∗\)−cμ2​\(xt⊤​θ^t−xt⊤​θ∗\)2\.\\displaystyle 0\\leq\\eta\_\{t\}\\big\(x\_\{t\}^\{\\top\}\\hat\{\\theta\}\_\{t\}\-x\_\{t\}^\{\\top\}\\theta^\{\*\}\\big\)\+\\nabla\\ell\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)^\{\\top\}\(\\hat\{\\theta\}\_\{t\}\-\\theta^\{\*\}\)\-\\frac\{c\_\{\\mu\}\}\{2\}\\big\(x\_\{t\}^\{\\top\}\\hat\{\\theta\}\_\{t\}\-x\_\{t\}^\{\\top\}\\theta^\{\*\}\\big\)^\{2\}\.
Next, the proximal update in Eq\. \([10](https://arxiv.org/html/2608.04324#S4.E10)\) implies the standard online Newton inequality: for any feasibleθ\\theta,

∇ℓt,i​\(θ^t\)⊤​\(θ^t−θ\)−12​‖∇ℓt,i​\(θ^t\)‖Vt\+1−12≤12​\(‖θ^t−θ‖Vt\+12−‖θ^t\+1−θ‖Vt\+12\)\.\\nabla\\ell\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)^\{\\top\}\(\\hat\{\\theta\}\_\{t\}\-\\theta\)\-\\frac\{1\}\{2\}\\\|\\nabla\\ell\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)\\\|\_\{\\mathrm\{V\}\_\{t\+1\}^\{\-1\}\}^\{2\}\\leq\\frac\{1\}\{2\}\\left\(\\\|\\hat\{\\theta\}\_\{t\}\-\\theta\\\|\_\{\\mathrm\{V\}\_\{t\+1\}\}^\{2\}\-\\\|\\hat\{\\theta\}\_\{t\+1\}\-\\theta\\\|\_\{\\mathrm\{V\}\_\{t\+1\}\}^\{2\}\\right\)\.Takingθ=θ∗\\theta=\\theta^\{\*\}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\.\\displaystyle 0\\leq\\frac\{1\}\{2\}\\left\(\\\|\\hat\{\\theta\}\_\{t\}\-\\theta^\{\*\}\\\|\_\{\\mathrm\{V\}\_\{t\+1\}\}^\{2\}\-\\\|\\hat\{\\theta\}\_\{t\+1\}\-\\theta^\{\*\}\\\|\_\{\\mathrm\{V\}\_\{t\+1\}\}^\{2\}\\right\)\-\\frac\{c\_\{\\mu\}\}\{2\}\\big\(x\_\{t\}^\{\\top\}\\hat\{\\theta\}\_\{t\}\-x\_\{t\}^\{\\top\}\\theta^\{\*\}\\big\)^\{2\}\+\\eta\_\{t\}\\big\(x\_\{t\}^\{\\top\}\\hat\{\\theta\}\_\{t\}\-x\_\{t\}^\{\\top\}\\theta^\{\*\}\\big\)\+\\frac\{1\}\{2\}\\\|\\nabla\\ell\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)\\\|\_\{\\mathrm\{V\}\_\{t\+1\}^\{\-1\}\}^\{2\}\.SinceVt\+1=Vt\+cμ2​xt​xt⊤,\\mathrm\{V\}\_\{t\+1\}=\\mathrm\{V\}\_\{t\}\+\\frac\{c\_\{\\mu\}\}\{2\}x\_\{t\}x\_\{t\}^\{\\top\},we have

‖θ^t−θ∗‖Vt\+12=‖θ^t−θ∗‖Vt2\+cμ2​\(xt⊤​θ^t−xt⊤​θ∗\)2\.\\\|\\hat\{\\theta\}\_\{t\}\-\\theta^\{\*\}\\\|\_\{\\mathrm\{V\}\_\{t\+1\}\}^\{2\}=\\\|\\hat\{\\theta\}\_\{t\}\-\\theta^\{\*\}\\\|\_\{\\mathrm\{V\}\_\{t\}\}^\{2\}\+\\frac\{c\_\{\\mu\}\}\{2\}\\big\(x\_\{t\}^\{\\top\}\\hat\{\\theta\}\_\{t\}\-x\_\{t\}^\{\\top\}\\theta^\{\*\}\\big\)^\{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\.\\displaystyle 0\\leq\\frac\{1\}\{2\}\\left\(\\\|\\hat\{\\theta\}\_\{t\}\-\\theta^\{\*\}\\\|\_\{\\mathrm\{V\}\_\{t\}\}^\{2\}\-\\\|\\hat\{\\theta\}\_\{t\+1\}\-\\theta^\{\*\}\\\|\_\{\\mathrm\{V\}\_\{t\+1\}\}^\{2\}\\right\)\-\\frac\{c\_\{\\mu\}\}\{4\}\\big\(x\_\{t\}^\{\\top\}\\hat\{\\theta\}\_\{t\}\-x\_\{t\}^\{\\top\}\\theta^\{\*\}\\big\)^\{2\}\+\\eta\_\{t\}\\big\(x\_\{t\}^\{\\top\}\\hat\{\\theta\}\_\{t\}\-x\_\{t\}^\{\\top\}\\theta^\{\*\}\\big\)\+\\frac\{1\}\{2\}\\\|\\nabla\\ell\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)\\\|\_\{\\mathrm\{V\}\_\{t\+1\}^\{\-1\}\}^\{2\}\.By Assumption[4](https://arxiv.org/html/2608.04324#Thmassume4),\|ηt\|≤R\|\\eta\_\{t\}\|\\leq Rand\|μi​\(⋅\)\|≤U\|\\mu\_\{i\}\(\\cdot\)\|\\leq U\. Hence\|yt,i\|≤U\+R\|y\_\{t,i\}\|\\leq U\+Rand\|μi​\(xt⊤​θ^t\)−yt,i\|≤2​\(U\+R\)\.\|\\mu\_\{i\}\(x\_\{t\}^\{\\top\}\\hat\{\\theta\}\_\{t\}\)\-y\_\{t,i\}\|\\leq 2\(U\+R\)\.Using a slightly loose bound, we have

‖∇ℓt,i​\(θ^t\)‖Vt\+1−12≤4​\(U\+R\)2​‖xt‖Vt\+1−12\.\\\|\\nabla\\ell\_\{t,i\}\(\\hat\{\\theta\}\_\{t\}\)\\\|\_\{\\mathrm\{V\}\_\{t\+1\}^\{\-1\}\}^\{2\}\\leq 4\(U\+R\)^\{2\}\\\|x\_\{t\}\\\|\_\{\\mathrm\{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\.\\displaystyle 0\\leq\\frac\{1\}\{2\}\\left\(\\\|\\hat\{\\theta\}\_\{t\}\-\\theta^\{\*\}\\\|\_\{\\mathrm\{V\}\_\{t\}\}^\{2\}\-\\\|\\hat\{\\theta\}\_\{t\+1\}\-\\theta^\{\*\}\\\|\_\{\\mathrm\{V\}\_\{t\+1\}\}^\{2\}\\right\)\-\\frac\{c\_\{\\mu\}\}\{4\}\\big\(x\_\{t\}^\{\\top\}\\hat\{\\theta\}\_\{t\}\-x\_\{t\}^\{\\top\}\\theta^\{\*\}\\big\)^\{2\}\+\\eta\_\{t\}\\big\(x\_\{t\}^\{\\top\}\\hat\{\\theta\}\_\{t\}\-x\_\{t\}^\{\\top\}\\theta^\{\*\}\\big\)\+2\(U\+R\)^\{2\}\\\|x\_\{t\}\\\|\_\{\\mathrm\{V\}\_\{t\+1\}^\{\-1\}\}^\{2\}\.Multiplying by two and rearranging proves the stated recursion\.□\\hfill\\square

###### Lemma 7\(Uniform control of the noise cross term\)

Fix an objectivei∈\[m\]i\\in\[m\]and letat=fi​\(Xt\)⊤​\(θ^t,i−θi∗\)a\_\{t\}=f\_\{i\}\(\\mathrm\{X\}\_\{t\}\)^\{\\top\}\(\\hat\{\\theta\}\_\{t,i\}\-\\theta\_\{i\}^\{\*\}\)\. Under Assumptions[2](https://arxiv.org/html/2608.04324#Thmassume2)–[4](https://arxiv.org/html/2608.04324#Thmassume4), with probability at least1−δ/m1\-\\delta/m, simultaneously for allt≥1t\\geq 1,

2​∑τ=1tητ,i​aτ≤cμ2\+cμ2​∑τ=1taτ2\+16​R2cμ​log⁡\(m​1\+4​S2​tδ\)\.2\\sum\_\{\\tau=1\}^\{t\}\\eta\_\{\\tau,i\}a\_\{\\tau\}\\leq\\frac\{c\_\{\\mu\}\}\{2\}\+\\frac\{c\_\{\\mu\}\}\{2\}\\sum\_\{\\tau=1\}^\{t\}a\_\{\\tau\}^\{2\}\+\\frac\{16R^\{2\}\}\{c\_\{\\mu\}\}\\log\\left\(\\frac\{m\\sqrt\{1\+4S^\{2\}t\}\}\{\\delta\}\\right\)\.

#### Proof\.

The sequence\{ηt,i​at\}t≥1\\\{\\eta\_\{t,i\}a\_\{t\}\\\}\_\{t\\geq 1\}is a martingale difference sequence and\|ηt,i\|≤R\|\\eta\_\{t,i\}\|\\leq R\. The self\-normalized martingale inequality\[Abbasi\-Yadkoriet al\.,[2012](https://arxiv.org/html/2608.04324#bib.bib27)\]therefore gives, simultaneously for allt≥1t\\geq 1,

∑τ=1tητ,i​aτ≤R​2​\(1\+∑τ=1taτ2\)​log⁡\(m​1\+∑τ=1taτ2δ\)\.\\sum\_\{\\tau=1\}^\{t\}\\eta\_\{\\tau,i\}a\_\{\\tau\}\\leq R\\sqrt\{2\\left\(1\+\\sum\_\{\\tau=1\}^\{t\}a\_\{\\tau\}^\{2\}\\right\)\\log\\left\(\\frac\{m\\sqrt\{1\+\\sum\_\{\\tau=1\}^\{t\}a\_\{\\tau\}^\{2\}\}\}\{\\delta\}\\right\)\}\.Since‖fi​\(Xτ\)‖2≤1\\\|f\_\{i\}\(\\mathrm\{X\}\_\{\\tau\}\)\\\|\_\{2\}\\leq 1and both‖θ^τ,i‖2\\\|\\hat\{\\theta\}\_\{\\tau,i\}\\\|\_\{2\}and‖θi∗‖2\\\|\\theta\_\{i\}^\{\*\}\\\|\_\{2\}are at mostSS, we have\|aτ\|≤2​S\|a\_\{\\tau\}\|\\leq 2S\. Thus the logarithm is at most

log⁡\(m​1\+4​S2​tδ\)\.\\log\\left\(\\frac\{m\\sqrt\{1\+4S^\{2\}t\}\}\{\\delta\}\\right\)\.Applying Young’s inequality to the resulting square\-root term gives the claimed bound\.□\\hfill\\square

###### Lemma 8

Suppose Assumptions[2](https://arxiv.org/html/2608.04324#Thmassume2)–[4](https://arxiv.org/html/2608.04324#Thmassume4)hold\. With probability at least1−δ1\-\\delta, for alli∈\[m\]i\\in\[m\]and allt≥1t\\geq 1,

‖θ^t\+1,i−θi∗‖Vt\+1,i2≤‖θi∗‖Λ2\+16​\(U\+R\)2cμ​log⁡det\(Vt\+1,i\)det\(Λ\)\+cμ2\+16​R2cμ​log⁡\(m​1\+4​S2​tδ\)\.\\displaystyle\\\|\\hat\{\\theta\}\_\{t\+1,i\}\-\\theta\_\{i\}^\{\*\}\\\|\_\{\\mathrm\{V\}\_\{t\+1,i\}\}^\{2\}\\leq\\\|\\theta\_\{i\}^\{\*\}\\\|\_\{\\Lambda\}^\{2\}\+\\frac\{16\(U\+R\)^\{2\}\}\{c\_\{\\mu\}\}\\log\\frac\{\\det\(\\mathrm\{V\}\_\{t\+1,i\}\)\}\{\\det\(\\Lambda\)\}\+\\frac\{c\_\{\\mu\}\}\{2\}\+\\frac\{16R^\{2\}\}\{c\_\{\\mu\}\}\\log\\left\(\\frac\{m\\sqrt\{1\+4S^\{2\}t\}\}\{\\delta\}\\right\)\.

#### Proof\.

Fixi∈\[m\]i\\in\[m\], suppress the objective index, and letat=xt⊤​\(θ^t−θ∗\)a\_\{t\}=x\_\{t\}^\{\\top\}\(\\hat\{\\theta\}\_\{t\}\-\\theta^\{\*\}\)\. Summing Lemma[6](https://arxiv.org/html/2608.04324#Thmlem6)overτ=1,…,t\\tau=1,\\ldots,t, and usingθ^1=0\\hat\{\\theta\}\_\{1\}=0andV1=Λ\\mathrm\{V\}\_\{1\}=\\Lambda, gives

‖θ^t\+1−θ∗‖Vt\+12≤‖θ∗‖Λ2−cμ2​∑τ=1taτ2\+4​\(U\+R\)2​∑τ=1t‖xτ‖Vτ\+1−12\+2​∑τ=1tητ​aτ\.\\displaystyle\\\|\\hat\{\\theta\}\_\{t\+1\}\-\\theta^\{\*\}\\\|\_\{\\mathrm\{V\}\_\{t\+1\}\}^\{2\}\\leq\\\|\\theta^\{\*\}\\\|\_\{\\Lambda\}^\{2\}\-\\frac\{c\_\{\\mu\}\}\{2\}\\sum\_\{\\tau=1\}^\{t\}a\_\{\\tau\}^\{2\}\+4\(U\+R\)^\{2\}\\sum\_\{\\tau=1\}^\{t\}\\\|x\_\{\\tau\}\\\|\_\{\\mathrm\{V\}\_\{\\tau\+1\}^\{\-1\}\}^\{2\}\+2\\sum\_\{\\tau=1\}^\{t\}\\eta\_\{\\tau\}a\_\{\\tau\}\.The standard elliptical\-potential argument\[Hazanet al\.,[2007](https://arxiv.org/html/2608.04324#bib.bib61)\]yields

∑τ=1t‖xτ‖Vτ\+1−12≤4cμ​log⁡det\(Vt\+1\)det\(Λ\)\.\\sum\_\{\\tau=1\}^\{t\}\\\|x\_\{\\tau\}\\\|\_\{\\mathrm\{V\}\_\{\\tau\+1\}^\{\-1\}\}^\{2\}\\leq\\frac\{4\}\{c\_\{\\mu\}\}\\log\\frac\{\\det\(\\mathrm\{V\}\_\{t\+1\}\)\}\{\\det\(\\Lambda\)\}\.On the event in Lemma[7](https://arxiv.org/html/2608.04324#Thmlem7), its quadratic term exactly cancels the negative strong\-convexity term above\. Substitution therefore proves the claimed bound for objectiveii\. A union bound overi∈\[m\]i\\in\[m\]completes the proof\.□\\hfill\\square

By Lemma C\.5 ofKanget al\.\[[2022](https://arxiv.org/html/2608.04324#bib.bib268)\], together withλ0≥cμ/2\\lambda\_\{0\}\\geq c\_\{\\mu\}/2andlog⁡\(1\+x\)≤x\\log\(1\+x\)\\leq x, for every objectivei∈\[m\]i\\in\[m\],

log⁡det​\(Vt\+1\)det​\(Λ\)≤k​log⁡\(1\+tk\)\+cμ​t2​λ⟂\.\\displaystyle\\log\\frac\{\\text\{det\}\(\\mathrm\{V\}\_\{t\+1\}\)\}\{\\text\{det\}\(\\Lambda\)\}\\leq k\\log\\left\(1\+\\frac\{t\}\{k\}\\right\)\+\\frac\{c\_\{\\mu\}t\}\{2\\lambda\_\{\\perp\}\}\.Substituting this bound into Lemma[8](https://arxiv.org/html/2608.04324#Thmlem8), we obtain that for alli∈\[m\]i\\in\[m\],

∥θ^t\+1,i−θi∗∥Vt\+1,i2≤λ0​S2\+λ⟂​S⟂2\+16​\(U\+R\)2cμ⋅\(k​log⁡\(1\+tk\)\+cμ​t2​λ⟂\)\+cμ2\+16​R2cμ​log⁡\(m​1\+4​S2​tδ\)\.\\displaystyle\\lVert\\hat\{\\theta\}\_\{t\+1,i\}\-\\theta^\{\*\}\_\{i\}\\rVert\_\{\\mathrm\{V\}\_\{t\+1,i\}\}^\{2\}\\leq\\lambda\_\{0\}S^\{2\}\+\\lambda\_\{\\perp\}S\_\{\\perp\}^\{2\}\+\\frac\{16\(U\+R\)^\{2\}\}\{c\_\{\\mu\}\}\\cdot\\left\(k\\log\\left\(1\+\\frac\{t\}\{k\}\\right\)\+\\frac\{c\_\{\\mu\}t\}\{2\\lambda\_\{\\perp\}\}\\right\)\+\\frac\{c\_\{\\mu\}\}\{2\}\+\\frac\{16R^\{2\}\}\{c\_\{\\mu\}\}\\log\\left\(\\frac\{m\\sqrt\{1\+4S^\{2\}t\}\}\{\\delta\}\\right\)\.Based on this, we provide the following lemma\.

###### Lemma 9

Suppose Assumptions[2](https://arxiv.org/html/2608.04324#Thmassume2)–[4](https://arxiv.org/html/2608.04324#Thmassume4)hold\. Then, with probability at least1−δ1\-\\delta, for allt≥1t\\geq 1, all objectivesi∈\[m\]i\\in\[m\], and all armsX∈𝒳\\mathrm\{X\}\\in\\mathcal\{X\}, we have

\|μi​\(fi​\(X\)⊤​θi∗\)−μi​\(fi​\(X\)⊤​θ^t,i\)\|≤βt​‖fi​\(X\)‖Vt,i−1,\\left\|\\mu\_\{i\}\\\!\\left\(f\_\{i\}\(\\mathrm\{X\}\)^\{\\top\}\\theta\_\{i\}^\{\*\}\\right\)\-\\mu\_\{i\}\\\!\\left\(f\_\{i\}\(\\mathrm\{X\}\)^\{\\top\}\\hat\{\\theta\}\_\{t,i\}\\right\)\\right\|\\leq\\beta\_\{t\}\\\|f\_\{i\}\(\\mathrm\{X\}\)\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\},where

βt\+1=Lμ​\(4​\(U\+R\)cμ​k​log⁡\(1\+tk\)\+cμ​t2​λ⟂\+log⁡\(m​1\+4​S2​tδ\)\+cμ2\+λ0​S\+λ⟂​S⟂\)\.\\displaystyle\\beta\_\{t\+1\}=L\_\{\\mu\}\\Bigg\(\\frac\{4\(U\+R\)\}\{\\sqrt\{c\_\{\\mu\}\}\}\\sqrt\{k\\log\\left\(1\+\\frac\{t\}\{k\}\\right\)\+\\frac\{c\_\{\\mu\}t\}\{2\\lambda\_\{\\perp\}\}\+\\log\\left\(\\frac\{m\\sqrt\{1\+4S^\{2\}t\}\}\{\\delta\}\\right\)\}\+\\sqrt\{\\frac\{c\_\{\\mu\}\}\{2\}\}\+\\sqrt\{\\lambda\_\{0\}\}S\+\\sqrt\{\\lambda\_\{\\perp\}\}S\_\{\\perp\}\\Bigg\)\.

#### Proof\.

Fix any roundt≥1t\\geq 1, objectivei∈\[m\]i\\in\[m\], and armX∈𝒳\\mathrm\{X\}\\in\\mathcal\{X\}\. Sinceμi​\(⋅\)\\mu\_\{i\}\(\\cdot\)isLμL\_\{\\mu\}\-Lipschitz continuous, we have

\|μi​\(fi​\(X\)⊤​θi∗\)−μi​\(fi​\(X\)⊤​θ^t,i\)\|≤Lμ​\|fi​\(X\)⊤​\(θi∗−θ^t,i\)\|\.\\displaystyle\\left\|\\mu\_\{i\}\\\!\\left\(f\_\{i\}\(\\mathrm\{X\}\)^\{\\top\}\\theta\_\{i\}^\{\*\}\\right\)\-\\mu\_\{i\}\\\!\\left\(f\_\{i\}\(\\mathrm\{X\}\)^\{\\top\}\\hat\{\\theta\}\_\{t,i\}\\right\)\\right\|\\leq L\_\{\\mu\}\\left\|f\_\{i\}\(\\mathrm\{X\}\)^\{\\top\}\(\\theta\_\{i\}^\{\*\}\-\\hat\{\\theta\}\_\{t,i\}\)\\right\|\.By the Cauchy–Schwarz inequality under the norm induced byVt,i\\mathrm\{V\}\_\{t,i\}, we further obtain

\|fi​\(X\)⊤​\(θi∗−θ^t,i\)\|≤‖fi​\(X\)‖Vt,i−1​‖θi∗−θ^t,i‖Vt,i\.\\left\|f\_\{i\}\(\\mathrm\{X\}\)^\{\\top\}\(\\theta\_\{i\}^\{\*\}\-\\hat\{\\theta\}\_\{t,i\}\)\\right\|\\leq\\\|f\_\{i\}\(\\mathrm\{X\}\)\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}\\\|\\theta\_\{i\}^\{\*\}\-\\hat\{\\theta\}\_\{t,i\}\\\|\_\{\\mathrm\{V\}\_\{t,i\}\}\.Combining the above inequality gives

\|μi​\(fi​\(X\)⊤​θi∗\)−μi​\(fi​\(X\)⊤​θ^t,i\)\|≤βt​‖fi​\(X\)‖Vt,i−1\.\\left\|\\mu\_\{i\}\\\!\\left\(f\_\{i\}\(\\mathrm\{X\}\)^\{\\top\}\\theta\_\{i\}^\{\*\}\\right\)\-\\mu\_\{i\}\\\!\\left\(f\_\{i\}\(\\mathrm\{X\}\)^\{\\top\}\\hat\{\\theta\}\_\{t,i\}\\right\)\\right\|\\leq\\beta\_\{t\}\\\|f\_\{i\}\(\\mathrm\{X\}\)\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}\.Since the confidence event holds uniformly over allt≥1t\\geq 1andi∈\[m\]i\\in\[m\], the desired result follows\.□\\hfill\\square

#### 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](https://arxiv.org/html/2608.04324#Thmassume5)holds\. LetWilex=1\+w\+⋯\+wi−1\.W\_\{i\}^\{\\rm lex\}=1\+w\+\\cdots\+w^\{i\-1\}\.With probability at least1−δ1\-\\delta, ifX∗∈𝒳t0X\_\{\*\}\\in\\mathcal\{X\}\_\{t\}^\{0\}, then, for everyi∈\[m\]i\\in\[m\], the following two statements hold:

X∗∈𝒳ti,X\_\{\*\}\\in\\mathcal\{X\}\_\{t\}^\{i\},and, for everyX∈𝒳ti\\mathrm\{X\}\\in\\mathcal\{X\}\_\{t\}^\{i\},

μi​\(⟨X∗,Θi∗⟩\)−μi​\(⟨X,Θi∗⟩\)≤4​Wilex​ct,it​\(Xt\)\.\\mu\_\{i\}\(\\langle X\_\{\*\},\\Theta\_\{i\}^\{\*\}\\rangle\)\-\\mu\_\{i\}\(\\langle\\mathrm\{X\},\\Theta\_\{i\}^\{\*\}\\rangle\)\\leq 4W\_\{i\}^\{\\rm lex\}c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)\.

#### Proof\.

For simplicity, defineΔi​\(X\)=μi​\(⟨X∗,Θi∗⟩\)−μi​\(⟨X,Θi∗⟩\)\.\\Delta\_\{i\}\(\\mathrm\{X\}\)=\\mu\_\{i\}\(\\langle X\_\{\*\},\\Theta\_\{i\}^\{\*\}\\rangle\)\-\\mu\_\{i\}\(\\langle\\mathrm\{X\},\\Theta\_\{i\}^\{\*\}\\rangle\)\.Since\(Xt,it\)\(\\mathrm\{X\}\_\{t\},i\_\{t\}\)maximizes the confidence width over𝒳t×\[m\]\\mathcal\{X\}\_\{t\}\\times\[m\], for everyX∈𝒳t\\mathrm\{X\}\\in\\mathcal\{X\}\_\{t\}and everyi∈\[m\]i\\in\[m\],

ct,i​\(X\)≤ct,it​\(Xt\)\.c\_\{t,i\}\(\\mathrm\{X\}\)\\leq c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)\.LetWi:=2\+4​w\+⋯\+4​wi−1\.W\_\{i\}:=2\+4w\+\\cdots\+4w^\{i\-1\}\.Then the filtering rule in Algorithm[3](https://arxiv.org/html/2608.04324#alg3)can be written as

𝒳ti=\{X∈𝒳ti−1:y^t,i​\(Xt,i\)−y^t,i​\(X\)≤Wi​ct,it​\(Xt\)\}\.\\mathcal\{X\}\_\{t\}^\{i\}=\\left\\\{\\mathrm\{X\}\\in\\mathcal\{X\}\_\{t\}^\{i\-1\}:\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\_\{t,i\}\)\-\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\)\\leq W\_\{i\}c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)\\right\\\}\.Note thatWi\+2=4​\(1\+w\+⋯\+wi−1\)=4​WilexW\_\{i\}\+2=4\(1\+w\+\\cdots\+w^\{i\-1\}\)=4W\_\{i\}^\{\\rm lex\}\. We prove the result by induction over the objective indexii\.

Fori=1i=1, sinceX∗X\_\{\*\}is lexicographically optimal, it maximizes the first objective\. Hence, for anyX∈𝒳t\\mathrm\{X\}\\in\\mathcal\{X\}\_\{t\},

μ1​\(⟨X∗,Θ1∗⟩\)≥μ1​\(⟨X,Θ1∗⟩\)\.\\mu\_\{1\}\(\\langle X\_\{\*\},\\Theta\_\{1\}^\{\*\}\\rangle\)\\geq\\mu\_\{1\}\(\\langle\\mathrm\{X\},\\Theta\_\{1\}^\{\*\}\\rangle\)\.In particular,

μ1​\(⟨X∗,Θ1∗⟩\)≥μ1​\(⟨Xt,1,Θ1∗⟩\)\.\\mu\_\{1\}\(\\langle X\_\{\*\},\\Theta\_\{1\}^\{\*\}\\rangle\)\\geq\\mu\_\{1\}\(\\langle\\mathrm\{X\}\_\{t,1\},\\Theta\_\{1\}^\{\*\}\\rangle\)\.Using the confidence event, we obtain

y^t,1​\(Xt,1\)−y^t,1​\(X∗\)\\displaystyle\\hat\{y\}\_\{t,1\}\(\\mathrm\{X\}\_\{t,1\}\)\-\\hat\{y\}\_\{t,1\}\(X\_\{\*\}\)≤μ1​\(⟨Xt,1,Θ1∗⟩\)−μ1​\(⟨X∗,Θ1∗⟩\)\+ct,1​\(Xt,1\)\+ct,1​\(X∗\)\\displaystyle\\leq\\mu\_\{1\}\(\\langle\\mathrm\{X\}\_\{t,1\},\\Theta\_\{1\}^\{\*\}\\rangle\)\-\\mu\_\{1\}\(\\langle X\_\{\*\},\\Theta\_\{1\}^\{\*\}\\rangle\)\+c\_\{t,1\}\(\\mathrm\{X\}\_\{t,1\}\)\+c\_\{t,1\}\(X\_\{\*\}\)≤2​ct,it​\(Xt\)\.\\displaystyle\\leq 2c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)\.SinceW1=2W\_\{1\}=2, this impliesX∗∈𝒳t1X\_\{\*\}\\in\\mathcal\{X\}\_\{t\}^\{1\}\.

Moreover, for anyX∈𝒳t1\\mathrm\{X\}\\in\\mathcal\{X\}\_\{t\}^\{1\},

Δ1​\(X\)\\displaystyle\\Delta\_\{1\}\(\\mathrm\{X\}\)=μ1​\(⟨X∗,Θ1∗⟩\)−μ1​\(⟨X,Θ1∗⟩\)\\displaystyle=\\mu\_\{1\}\(\\langle X\_\{\*\},\\Theta\_\{1\}^\{\*\}\\rangle\)\-\\mu\_\{1\}\(\\langle\\mathrm\{X\},\\Theta\_\{1\}^\{\*\}\\rangle\)≤y^t,1​\(X∗\)−y^t,1​\(X\)\+2​ct,it​\(Xt\)\\displaystyle\\leq\\hat\{y\}\_\{t,1\}\(X\_\{\*\}\)\-\\hat\{y\}\_\{t,1\}\(\\mathrm\{X\}\)\+2c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)≤y^t,1​\(Xt,1\)−y^t,1​\(X\)\+2​ct,it​\(Xt\)\\displaystyle\\leq\\hat\{y\}\_\{t,1\}\(\\mathrm\{X\}\_\{t,1\}\)\-\\hat\{y\}\_\{t,1\}\(\\mathrm\{X\}\)\+2c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)≤W1​ct,it​\(Xt\)\+2​ct,it​\(Xt\)\\displaystyle\\leq W\_\{1\}c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)\+2c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)=4​ct,it​\(Xt\)=4​W1lex​ct,it​\(Xt\)\.\\displaystyle=4c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)=4W\_\{1\}^\{\\rm lex\}c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)\.Thus the claim holds fori=1i=1\.

Now suppose the claim holds for all objectivesj<ij<i\. Since the candidate sets are nested,

𝒳ti−1⊆𝒳tj,∀j<i\.\\mathcal\{X\}\_\{t\}^\{i\-1\}\\subseteq\\mathcal\{X\}\_\{t\}^\{j\},\\qquad\\forall j<i\.Thus, for everyX∈𝒳ti−1\\mathrm\{X\}\\in\\mathcal\{X\}\_\{t\}^\{i\-1\}and everyj<ij<i,

Δj​\(X\)≤4​Wjlex​ct,it​\(Xt\)≤4​Wi−1lex​ct,it​\(Xt\)\.\\Delta\_\{j\}\(\\mathrm\{X\}\)\\leq 4W\_\{j\}^\{\\rm lex\}c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)\\leq 4W\_\{i\-1\}^\{\\rm lex\}c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)\.
We first show thatX∗∈𝒳tiX\_\{\*\}\\in\\mathcal\{X\}\_\{t\}^\{i\}\. SinceXt,i∈𝒳ti−1\\mathrm\{X\}\_\{t,i\}\\in\\mathcal\{X\}\_\{t\}^\{i\-1\}, Assumption[5](https://arxiv.org/html/2608.04324#Thmassume5)gives

μi​\(⟨Xt,i,Θi∗⟩\)−μi​\(⟨X∗,Θi∗⟩\)\\displaystyle\\mu\_\{i\}\(\\langle\\mathrm\{X\}\_\{t,i\},\\Theta\_\{i\}^\{\*\}\\rangle\)\-\\mu\_\{i\}\(\\langle X\_\{\*\},\\Theta\_\{i\}^\{\*\}\\rangle\)≤w​maxj∈\[i−1\]⁡\{μj​\(⟨X∗,Θj∗⟩\)−μj​\(⟨Xt,i,Θj∗⟩\)\}\\displaystyle\\leq w\\max\_\{j\\in\[i\-1\]\}\\left\\\{\\mu\_\{j\}\(\\langle X\_\{\*\},\\Theta\_\{j\}^\{\*\}\\rangle\)\-\\mu\_\{j\}\(\\langle\\mathrm\{X\}\_\{t,i\},\\Theta\_\{j\}^\{\*\}\\rangle\)\\right\\\}=w​maxj∈\[i−1\]⁡Δj​\(Xt,i\)≤4​w​Wi−1lex​ct,it​\(Xt\)\.\\displaystyle=w\\max\_\{j\\in\[i\-1\]\}\\Delta\_\{j\}\(\\mathrm\{X\}\_\{t,i\}\)\\leq 4wW\_\{i\-1\}^\{\\rm lex\}c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)\.Therefore, by the confidence event,

y^t,i​\(Xt,i\)−y^t,i​\(X∗\)\\displaystyle\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\_\{t,i\}\)\-\\hat\{y\}\_\{t,i\}\(X\_\{\*\}\)≤μi​\(⟨Xt,i,Θi∗⟩\)−μi​\(⟨X∗,Θi∗⟩\)\+ct,i​\(Xt,i\)\+ct,i​\(X∗\)\\displaystyle\\leq\\mu\_\{i\}\(\\langle\\mathrm\{X\}\_\{t,i\},\\Theta\_\{i\}^\{\*\}\\rangle\)\-\\mu\_\{i\}\(\\langle X\_\{\*\},\\Theta\_\{i\}^\{\*\}\\rangle\)\+c\_\{t,i\}\(\\mathrm\{X\}\_\{t,i\}\)\+c\_\{t,i\}\(X\_\{\*\}\)≤4​w​Wi−1lex​ct,it​\(Xt\)\+2​ct,it​\(Xt\)\\displaystyle\\leq 4wW\_\{i\-1\}^\{\\rm lex\}c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)\+2c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)=Wi​ct,it​\(Xt\)\.\\displaystyle=W\_\{i\}c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)\.HenceX∗∈𝒳tiX\_\{\*\}\\in\\mathcal\{X\}\_\{t\}^\{i\}\.

Next, for anyX∈𝒳ti\\mathrm\{X\}\\in\\mathcal\{X\}\_\{t\}^\{i\}, using the confidence event again gives

Δi​\(X\)\\displaystyle\\Delta\_\{i\}\(\\mathrm\{X\}\)=μi​\(⟨X∗,Θi∗⟩\)−μi​\(⟨X,Θi∗⟩\)\\displaystyle=\\mu\_\{i\}\(\\langle X\_\{\*\},\\Theta\_\{i\}^\{\*\}\\rangle\)\-\\mu\_\{i\}\(\\langle\\mathrm\{X\},\\Theta\_\{i\}^\{\*\}\\rangle\)≤y^t,i​\(X∗\)−y^t,i​\(X\)\+2​ct,it​\(Xt\)\\displaystyle\\leq\\hat\{y\}\_\{t,i\}\(X\_\{\*\}\)\-\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\)\+2c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)≤y^t,i​\(Xt,i\)−y^t,i​\(X\)\+2​ct,it​\(Xt\)\\displaystyle\\leq\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\_\{t,i\}\)\-\\hat\{y\}\_\{t,i\}\(\\mathrm\{X\}\)\+2c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)≤Wi​ct,it​\(Xt\)\+2​ct,it​\(Xt\)\\displaystyle\\leq W\_\{i\}c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)\+2c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)=4​Wilex​ct,it​\(Xt\)\.\\displaystyle=4W\_\{i\}^\{\\rm lex\}c\_\{t,i\_\{t\}\}\(\\mathrm\{X\}\_\{t\}\)\.This completes the induction and the proof\.□\\hfill\\square

###### Lemma 11

Suppose Assumption[5](https://arxiv.org/html/2608.04324#Thmassume5)holds\. LetWilex=1\+w\+⋯\+wi−1\.W\_\{i\}^\{\\rm lex\}=1\+w\+\\cdots\+w^\{i\-1\}\.With probability at least1−δ1\-\\delta, for every decision roundt≥1t\\geq 1, the lexicographically optimal arm satisfies

X∗∈𝒳t\.\\mathrm\{X\}\_\{\*\}\\in\\mathcal\{X\}\_\{t\}\.Moreover, for everyt≥2t\\geq 2and every objectivei∈\[m\]i\\in\[m\], the armXt\\mathrm\{X\}\_\{t\}selected at roundttsatisfies

μi​\(⟨X∗,Θi∗⟩\)−μi​\(⟨Xt,Θi∗⟩\)≤4​Wilex​ct−1,it−1​\(Xt−1\)\.\\mu\_\{i\}\\\!\\left\(\\langle\\mathrm\{X\}\_\{\*\},\\Theta\_\{i\}^\{\*\}\\rangle\\right\)\-\\mu\_\{i\}\\\!\\left\(\\langle\\mathrm\{X\}\_\{t\},\\Theta\_\{i\}^\{\*\}\\rangle\\right\)\\leq 4W\_\{i\}^\{\\rm lex\}c\_\{t\-1,i\_\{t\-1\}\}\(\\mathrm\{X\}\_\{t\-1\}\)\.

#### Proof\.

We first prove by induction onttthatX∗∈𝒳t\\mathrm\{X\}\_\{\*\}\\in\\mathcal\{X\}\_\{t\}\. By initialization,𝒳1=𝒳\\mathcal\{X\}\_\{1\}=\\mathcal\{X\}, and henceX∗∈𝒳1\\mathrm\{X\}\_\{\*\}\\in\\mathcal\{X\}\_\{1\}\. Suppose thatX∗∈𝒳t\\mathrm\{X\}\_\{\*\}\\in\\mathcal\{X\}\_\{t\}for somet≥1t\\geq 1\. Since𝒳t0=𝒳t\\mathcal\{X\}\_\{t\}^\{0\}=\\mathcal\{X\}\_\{t\}, Lemma[10](https://arxiv.org/html/2608.04324#Thmlem10)implies thatX∗∈𝒳tm\\mathrm\{X\}\_\{\*\}\\in\\mathcal\{X\}\_\{t\}^\{m\}\. By the candidate\-set update𝒳t\+1=𝒳tm\\mathcal\{X\}\_\{t\+1\}=\\mathcal\{X\}\_\{t\}^\{m\}, we obtainX∗∈𝒳t\+1\\mathrm\{X\}\_\{\*\}\\in\\mathcal\{X\}\_\{t\+1\}\. Thus,X∗\\mathrm\{X\}\_\{\*\}belongs to𝒳t\\mathcal\{X\}\_\{t\}for everyt≥1t\\geq 1\.

Next, for everyt≥2t\\geq 2, Algorithm[3](https://arxiv.org/html/2608.04324#alg3)selectsXt\\mathrm\{X\}\_\{t\}from𝒳t\\mathcal\{X\}\_\{t\}\. Since𝒳t=𝒳t−1m\\mathcal\{X\}\_\{t\}=\\mathcal\{X\}\_\{t\-1\}^\{m\}, we haveXt∈𝒳t−1m\\mathrm\{X\}\_\{t\}\\in\\mathcal\{X\}\_\{t\-1\}^\{m\}\. Applying Lemma[10](https://arxiv.org/html/2608.04324#Thmlem10)at roundt−1t\-1gives, for everyi∈\[m\]i\\in\[m\],

μi​\(⟨X∗,Θi∗⟩\)−μi​\(⟨Xt,Θi∗⟩\)≤4​Wilex​ct−1,it−1​\(Xt−1\)\.\\mu\_\{i\}\\\!\\left\(\\langle\\mathrm\{X\}\_\{\*\},\\Theta\_\{i\}^\{\*\}\\rangle\\right\)\-\\mu\_\{i\}\\\!\\left\(\\langle\\mathrm\{X\}\_\{t\},\\Theta\_\{i\}^\{\*\}\\rangle\\right\)\\leq 4W\_\{i\}^\{\\rm lex\}c\_\{t\-1,i\_\{t\-1\}\}\(\\mathrm\{X\}\_\{t\-1\}\)\.This completes the proof\.□\\hfill\\square

#### 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 byUU, the firstT1T\_\{1\}rounds contribute at most2​U​T12UT\_\{1\}to the regret\. The first round of the online decision phase contributes at most2​U2U, while the remainingT2−1T\_\{2\}\-1rounds, whereT2=T−T1T\_\{2\}=T\-T\_\{1\}, are controlled by Lemma[11](https://arxiv.org/html/2608.04324#Thmlem11)\. Therefore,

Ri​\(T\)\\displaystyle R\_\{i\}\(T\)=∑t=1T\(μi​\(⟨X∗,Θi∗⟩\)−μi​\(⟨Xt,Θi∗⟩\)\)\\displaystyle=\\sum\_\{t=1\}^\{T\}\\left\(\\mu\_\{i\}\\\!\\left\(\\left\\langle\\mathrm\{X\}\_\{\*\},\\Theta\_\{i\}^\{\*\}\\right\\rangle\\right\)\-\\mu\_\{i\}\\\!\\left\(\\left\\langle\\mathrm\{X\}\_\{t\},\\Theta\_\{i\}^\{\*\}\\right\\rangle\\right\)\\right\)≤2​U​T1\+2​U\+∑t=2T24​Wilex​ct−1,it−1​\(Xt−1\)\\displaystyle\\leq 2UT\_\{1\}\+2U\+\\sum\_\{t=2\}^\{T\_\{2\}\}4W\_\{i\}^\{\\rm lex\}c\_\{t\-1,i\_\{t\-1\}\}\(\\mathrm\{X\}\_\{t\-1\}\)=2​U​T1\+2​U\+∑s=1T2−14​Wilex​cs,is​\(Xs\)\\displaystyle=2UT\_\{1\}\+2U\+\\sum\_\{s=1\}^\{T\_\{2\}\-1\}4W\_\{i\}^\{\\rm lex\}c\_\{s,i\_\{s\}\}\(\\mathrm\{X\}\_\{s\}\)≤2​U​T1\+2​U\+4​Wilex​βT​T2−1​∑s=1T2−1‖fis​\(Xs\)‖Vs,is−12,\\displaystyle\\leq 2UT\_\{1\}\+2U\+4W\_\{i\}^\{\\rm lex\}\\beta\_\{T\}\\sqrt\{T\_\{2\}\-1\}\\sqrt\{\\sum\_\{s=1\}^\{T\_\{2\}\-1\}\\\|f\_\{i\_\{s\}\}\(\\mathrm\{X\}\_\{s\}\)\\\|\_\{\\mathrm\{V\}\_\{s,i\_\{s\}\}^\{\-1\}\}^\{2\}\},\(19\)where the last inequality follows from the monotonicity of\{βt\}t≥1\\\{\\beta\_\{t\}\\\}\_\{t\\geq 1\}and the Cauchy–Schwarz inequality\.

Next, for each fixed objective, the standard elliptical\-potential argument\[Abbasi\-yadkoriet al\.,[2011](https://arxiv.org/html/2608.04324#bib.bib26), Lemma 11\]gives

∑t=1T2‖fi​\(Xt\)‖Vt,i−12≤4cμ​log⁡det\(VT2\+1,i\)det\(Λ\)\.\\sum\_\{t=1\}^\{T\_\{2\}\}\\\|f\_\{i\}\(\\mathrm\{X\}\_\{t\}\)\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}^\{2\}\\leq\\frac\{4\}\{c\_\{\\mu\}\}\\log\\frac\{\\det\(\\mathrm\{V\}\_\{T\_\{2\}\+1,i\}\)\}\{\\det\(\\Lambda\)\}\.Applying Lemma C\.5 ofKanget al\.\[[2022](https://arxiv.org/html/2608.04324#bib.bib268)\], usingλ0≥cμ/2\\lambda\_\{0\}\\geq c\_\{\\mu\}/2andlog⁡\(1\+x\)≤x\\log\(1\+x\)\\leq x, therefore yields

∑t=1T2‖fi​\(Xt\)‖Vt,i−12≤4cμ​\(k​log⁡\(1\+Tk\)\+cμ​T2​λ⟂\)\.\\sum\_\{t=1\}^\{T\_\{2\}\}\\\|f\_\{i\}\(\\mathrm\{X\}\_\{t\}\)\\\|\_\{\\mathrm\{V\}\_\{t,i\}^\{\-1\}\}^\{2\}\\leq\\frac\{4\}\{c\_\{\\mu\}\}\\left\(k\\log\\left\(1\+\\frac\{T\}\{k\}\\right\)\+\\frac\{c\_\{\\mu\}T\}\{2\\lambda\_\{\\perp\}\}\\right\)\.\(20\)Because the selected objectiveisi\_\{s\}may vary across rounds, we partition the elliptical norms according to the selected objective\. Applying \([20](https://arxiv.org/html/2608.04324#A3.E20)\) separately to each objective gives

∑s=1T2−1‖fis​\(Xs\)‖Vs,is−12\\displaystyle\\sum\_\{s=1\}^\{T\_\{2\}\-1\}\\\|f\_\{i\_\{s\}\}\(\\mathrm\{X\}\_\{s\}\)\\\|\_\{\\mathrm\{V\}\_\{s,i\_\{s\}\}^\{\-1\}\}^\{2\}=∑j=1m∑s∈\[T2−1\]is=j‖fj​\(Xs\)‖Vs,j−12\\displaystyle=\\sum\_\{j=1\}^\{m\}\\sum\_\{\\begin\{subarray\}\{c\}s\\in\[T\_\{2\}\-1\]\\\\ i\_\{s\}=j\\end\{subarray\}\}\\\|f\_\{j\}\(\\mathrm\{X\}\_\{s\}\)\\\|\_\{\\mathrm\{V\}\_\{s,j\}^\{\-1\}\}^\{2\}\(21\)≤∑j=1m∑s=1T2−1‖fj​\(Xs\)‖Vs,j−12\\displaystyle\\leq\\sum\_\{j=1\}^\{m\}\\sum\_\{s=1\}^\{T\_\{2\}\-1\}\\\|f\_\{j\}\(\\mathrm\{X\}\_\{s\}\)\\\|\_\{\\mathrm\{V\}\_\{s,j\}^\{\-1\}\}^\{2\}≤4​mcμ​\(k​log⁡\(1\+Tk\)\+cμ​T2​λ⟂\)\.\\displaystyle\\leq\\frac\{4m\}\{c\_\{\\mu\}\}\\left\(k\\log\\left\(1\+\\frac\{T\}\{k\}\\right\)\+\\frac\{c\_\{\\mu\}T\}\{2\\lambda\_\{\\perp\}\}\\right\)\.Substituting \([21](https://arxiv.org/html/2608.04324#A3.E21)\) into \([19](https://arxiv.org/html/2608.04324#A3.E19)\) yields

Ri​\(T\)\\displaystyle R\_\{i\}\(T\)≤2​U​T1\+2​U\+8​Wilex​βT​m​\(T2−1\)​\(kcμ​log⁡\(1\+Tk\)\+T2​λ⟂\)\\displaystyle\\leq 2UT\_\{1\}\+2U\+8W\_\{i\}^\{\\rm lex\}\\beta\_\{T\}\\sqrt\{m\(T\_\{2\}\-1\)\}\\sqrt\{\\left\(\\frac\{k\}\{c\_\{\\mu\}\}\\log\\left\(1\+\\frac\{T\}\{k\}\\right\)\+\\frac\{T\}\{2\\lambda\_\{\\perp\}\}\\right\)\}

#### Step 4: Parameter choice and completion of the proof\.

We now substitute the choices ofT1T\_\{1\},λ⟂\\lambda\_\{\\perp\}, andS⟂S\_\{\\perp\}into the regret bound forLexi\-LowGLM\. Let

A:=M​\(d1\+d2\)​rDr​r2​log⁡\(m​\(d1\+d2\)δ\)\.A:=\\frac\{M\(d\_\{1\}\+d\_\{2\}\)r\}\{D\_\{rr\}^\{2\}\}\\log\\left\(\\frac\{m\(d\_\{1\}\+d\_\{2\}\)\}\{\\delta\}\\right\)\.Then the prescribed exploration length and the tail\-coordinate bound satisfy

T1≍M​\(d1\+d2\)​r​T​log⁡\(\(d1\+d2\)​m/δ\)Dr​r=A​T,S⟂=\(d1\+d2\)​M​rT1​Dr​r2​log⁡\(m​\(d1\+d2\)δ\)≍AT\.T\_\{1\}\\asymp\\frac\{\\sqrt\{M\(d\_\{1\}\+d\_\{2\}\)rT\\log\(\(d\_\{1\}\+d\_\{2\}\)m/\\delta\)\}\}\{D\_\{rr\}\}=\\sqrt\{AT\},\\quad S\_\{\\perp\}=\\frac\{\(d\_\{1\}\+d\_\{2\}\)Mr\}\{T\_\{1\}D\_\{rr\}^\{2\}\}\\log\\left\(\\frac\{m\(d\_\{1\}\+d\_\{2\}\)\}\{\\delta\}\\right\)\\asymp\\sqrt\{\\frac\{A\}\{T\}\}\.
Recall that

λ⟂=cμ​Tk​log⁡\(1\+cμ​T/\(k​λ0\)\)\.\\lambda\_\{\\perp\}=\\frac\{c\_\{\\mu\}T\}\{k\\log\\\!\\left\(1\+c\_\{\\mu\}T/\(k\\lambda\_\{0\}\)\\right\)\}\.Hence,

cμ​T2​λ⟂=k2​log⁡\(1\+cμ​Tk​λ0\)​and​T2​λ⟂=k2​cμ​log⁡\(1\+cμ​Tk​λ0\)\.\\frac\{c\_\{\\mu\}T\}\{2\\lambda\_\{\\perp\}\}=\\frac\{k\}\{2\}\\log\\\!\\left\(1\+\\frac\{c\_\{\\mu\}T\}\{k\\lambda\_\{0\}\}\\right\)\\text\{ and \}\\frac\{T\}\{2\\lambda\_\{\\perp\}\}=\\frac\{k\}\{2c\_\{\\mu\}\}\\log\\\!\\left\(1\+\\frac\{c\_\{\\mu\}T\}\{k\\lambda\_\{0\}\}\\right\)\.Therefore,

kcμ​log⁡\(1\+Tk\)\+T2​λ⟂=O~​\(kcμ\)\.\\sqrt\{\\frac\{k\}\{c\_\{\\mu\}\}\\log\\left\(1\+\\frac\{T\}\{k\}\\right\)\+\\frac\{T\}\{2\\lambda\_\{\\perp\}\}\}=\\widetilde\{O\}\\left\(\\sqrt\{\\frac\{k\}\{c\_\{\\mu\}\}\}\\right\)\.
Next, by the definition ofβT\+1\\beta\_\{T\+1\},

βT\+1=Lμ​\(4​\(U\+R\)cμ​k​log⁡\(1\+Tk\)\+cμ​T2​λ⟂\+log⁡\(m​1\+4​S2​Tδ\)\+cμ2\+λ0​S\+λ⟂​S⟂\)\.\\displaystyle\\beta\_\{T\+1\}=L\_\{\\mu\}\\Bigg\(\\frac\{4\(U\+R\)\}\{\\sqrt\{c\_\{\\mu\}\}\}\\sqrt\{k\\log\\left\(1\+\\frac\{T\}\{k\}\\right\)\+\\frac\{c\_\{\\mu\}T\}\{2\\lambda\_\{\\perp\}\}\+\\log\\left\(\\frac\{m\\sqrt\{1\+4S^\{2\}T\}\}\{\\delta\}\\right\)\}\+\\sqrt\{\\frac\{c\_\{\\mu\}\}\{2\}\}\+\\sqrt\{\\lambda\_\{0\}\}S\+\\sqrt\{\\lambda\_\{\\perp\}\}S\_\{\\perp\}\\Bigg\)\.Using the above expression ofλ⟂\\lambda\_\{\\perp\}, we obtain

k​log⁡\(1\+Tk\)\+cμ​T2​λ⟂\+log⁡\(m​1\+4​S2​Tδ\)=O~​\(k\)\.\\sqrt\{k\\log\\left\(1\+\\frac\{T\}\{k\}\\right\)\+\\frac\{c\_\{\\mu\}T\}\{2\\lambda\_\{\\perp\}\}\+\\log\\left\(\\frac\{m\\sqrt\{1\+4S^\{2\}T\}\}\{\\delta\}\\right\)\}=\\widetilde\{O\}\(\\sqrt\{k\}\)\.Furthermore,

λ⟂​S⟂=cμ​Tk​log⁡\(1\+cμ​T/\(k​λ0\)\)⋅AT=O~​\(cμ​Ak\)\.\\sqrt\{\\lambda\_\{\\perp\}\}S\_\{\\perp\}=\\sqrt\{\\frac\{c\_\{\\mu\}T\}\{k\\log\(1\+c\_\{\\mu\}T/\(k\\lambda\_\{0\}\)\)\}\}\\cdot\\sqrt\{\\frac\{A\}\{T\}\}=\\widetilde\{O\}\\left\(\\sqrt\{\\frac\{c\_\{\\mu\}A\}\{k\}\}\\right\)\.Thus,

βT\+1=O~​\(Lμ​\(\(U\+R\)​kcμ\+cμ\+λ0​S\+cμ​Ak\)\)\.\\beta\_\{T\+1\}=\\widetilde\{O\}\\left\(L\_\{\\mu\}\\left\(\\frac\{\(U\+R\)\\sqrt\{k\}\}\{\\sqrt\{c\_\{\\mu\}\}\}\+\\sqrt\{c\_\{\\mu\}\}\+\\sqrt\{\\lambda\_\{0\}\}S\+\\sqrt\{\\frac\{c\_\{\\mu\}A\}\{k\}\}\\right\)\\right\)\.
Sinceβt\\beta\_\{t\}is nondecreasing intt, we useβT≤βT\+1\\beta\_\{T\}\\leq\\beta\_\{T\+1\}\. Combining the above estimates and usingT2−1≤T2≤T\\sqrt\{T\_\{2\}\-1\}\\leq\\sqrt\{T\_\{2\}\}\\leq\\sqrt\{T\}, we get

Ri​\(T\)\\displaystyle R\_\{i\}\(T\)≤2​U​T1\+2​U\+8​Wilex​βT​m​T2​kcμ​log⁡\(1\+Tk\)\+T2​λ⟂\\displaystyle\\leq 2UT\_\{1\}\+2U\+8W\_\{i\}^\{\\rm lex\}\\beta\_\{T\}\\sqrt\{mT\_\{2\}\}\\sqrt\{\\frac\{k\}\{c\_\{\\mu\}\}\\log\\left\(1\+\\frac\{T\}\{k\}\\right\)\+\\frac\{T\}\{2\\lambda\_\{\\perp\}\}\}=O~​\(U​A​T\+Wilex​m​Lμ​\(\(U\+R\)​kcμ\+k\+S​λ0​kcμ\+A\)​T\)\.\\displaystyle=\\widetilde\{O\}\\left\(U\\sqrt\{AT\}\+W\_\{i\}^\{\\rm lex\}\\sqrt\{m\}L\_\{\\mu\}\\left\(\\frac\{\(U\+R\)k\}\{c\_\{\\mu\}\}\+\\sqrt\{k\}\+S\\sqrt\{\\frac\{\\lambda\_\{0\}k\}\{c\_\{\\mu\}\}\}\+\\sqrt\{A\}\\right\)\\sqrt\{T\}\\right\)\.Substituting the definition ofAA, we obtain

Ri\(T\)=O~\(\[\\displaystyle R\_\{i\}\(T\)=\\widetilde\{O\}\\Bigg\(\\Bigg\[UM​\(d1\+d2\)​rDr​r\+WilexmLμ\(\(U\+R\)​kcμ\+k\+Sλ0​kcμ\+M​\(d1\+d2\)​rDr​r\)\]T\)\.\\displaystyle U\\frac\{\\sqrt\{M\(d\_\{1\}\+d\_\{2\}\)r\}\}\{D\_\{rr\}\}\+W\_\{i\}^\{\\rm lex\}\\sqrt\{m\}L\_\{\\mu\}\\left\(\\frac\{\(U\+R\)k\}\{c\_\{\\mu\}\}\+\\sqrt\{k\}\+S\\sqrt\{\\frac\{\\lambda\_\{0\}k\}\{c\_\{\\mu\}\}\}\+\\frac\{\\sqrt\{M\(d\_\{1\}\+d\_\{2\}\)r\}\}\{D\_\{rr\}\}\\right\)\\Bigg\]\\sqrt\{T\}\\Bigg\)\.WhenU,R,Lμ,cμ,λ0U,R,L\_\{\\mu\},c\_\{\\mu\},\\lambda\_\{0\}, andSSare treated as constants, and sinceWilex≥1W\_\{i\}^\{\\rm lex\}\\geq 1, this simplifies to

Ri​\(T\)=O~​\(Wilex​m​\(k\+M​\(d1\+d2\)​rDr​r\)​T\)\.R\_\{i\}\(T\)=\\widetilde\{O\}\\left\(W\_\{i\}^\{\\rm lex\}\\sqrt\{m\}\\left\(k\+\\frac\{\\sqrt\{M\(d\_\{1\}\+d\_\{2\}\)r\}\}\{D\_\{rr\}\}\\right\)\\sqrt\{T\}\\right\)\.Finally, sincek=\(d1\+d2\)​r−r2≍\(d1\+d2\)​rk=\(d\_\{1\}\+d\_\{2\}\)r\-r^\{2\}\\asymp\(d\_\{1\}\+d\_\{2\}\)randM​\(d1\+d2\)​rDr​r≲\(d1\+d2\)​r,\\frac\{\\sqrt\{M\(d\_\{1\}\+d\_\{2\}\)r\}\}\{D\_\{rr\}\}\\lesssim\(d\_\{1\}\+d\_\{2\}\)r,we obtain

Ri​\(T\)=O~​\(Wilex​m​\(d1\+d2\)​r​T\)\.R\_\{i\}\(T\)=\\widetilde\{O\}\\left\(W\_\{i\}^\{\\rm lex\}\\sqrt\{m\}\\,\(d\_\{1\}\+d\_\{2\}\)r\\sqrt\{T\}\\right\)\.The proof of Theorem[2](https://arxiv.org/html/2608.04324#Thmthm2)is finished\.□\\hfill\\square