Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
Authors: Bo Xue
Dake Bu
Ji Cheng
Yuanyu Wan
Qingfu Zhang
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement learning
multi-objective
linear model
Primary area: theory->reinforcement_learning_and_planning
TL;DR: We provide a theoretical analysis of regret bounds for multi-objective reinforcement learning.

Abstract: Reinforcement Learning (RL) with linear transition kernels and reward functions has recently attracted growing attention due to its computational efficiency and theoretical advancements. However, prior theoretical research in RL has primarily focused on single-objective problems, resulting in limited theoretical development for multi-objective reinforcement learning (MORL). To bridge this gap, we examine MORL under lexicographic reward structures, where rewards comprise $m$ hierarchically ordered objectives. In this framework, the agent the agent maximizes objectives sequentially, prioritizing the highest-priority objective before considering subsequent ones. We introduce the first MORL algorithm with provable regret guarantees. For any objective $i \in \\{1, 2, \ldots, m\\}$, our algorithm achieves a regret bound of $\widetilde{O}(\Lambda^i(\lambda) \cdot \sqrt{d^2H^4 K})$, where $\Lambda^i(\lambda) = 1 + \lambda + \cdots + \lambda^{i-1}$, $\lambda$ quantifies the trade-off between conflicting objectives, $d$ is the feature dimension, $H$ is the episode length, and $K$ is the number of episodes. Furthermore, our algorithm can be applied in the misspecified setting, where the regret bound for the $i$-th objective becomes $\widetilde{O}(\Lambda^i(\lambda)\cdot(\sqrt{d^2H^4K}+\epsilon dH^2K))$, with $\epsilon$ denoting the degree of misspecification.

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
Bo Xue Dake Bu'
Ji Cheng'
Yuanyu Wan 2 Qingfu Zhang'
Abstract
nance (Liu al., 2022), healthcare (Yu et al., 2021), and autonomous systems (Merkle et al., 2024). Therefore, es- tablishing solid theoretical foundation for RL is crucial. Over the years, significant advancements have been made in understanding RI. with linear transition kernels and reward functions, a subfield often referred to as linear RL or linear Markov Decision Process (MDP) (Zhang et al., 2024a; Zhou & Gu, 2022: Zhang al., 2024b; Vial et al., 2022; He et al., 2021; Cassel et al., 2024; Xiong et al., 2023; Jin et al., 2020; Li & Sun, 2024; Li et al., 2024a). Nevertheless, these stud- ies have primarily concentrated on single-objective prob- lems, where a single reward function is optimized during the agent's 's interactions with the environment.
Reinforcement Learning (RL) with linear tran- sition kernels and reward functions has recently attracted growing attention due to its computa- tional efficiency and theoretical advancements. However, prior theoretical research in RL has primarily focused on singlc-objective problems, resulting in limited theoretical development for multi-objective reinforcement learning (MORL). To bridge this gap, we examine MORL under lexicographic reward structures, where rewards comprise m hierarchically ordered objectives. In this framework, the agent maximizes objectives sequentially, prioritizing the highest-priority ob- jective before considering subsequent ones. We introduce the first MORL algorithm with prov- able regret guarantees. For any objective i (1, .m), our algorithm achieves a regret bound of (A) vd² where (A()) 1 + +.... X À quantifies the trade-off between conflicting objectives, d is the feature dimension, H is the episode length, and K is the number of episodes. Furthermore, our algorithm can be applied in the misspecified setting, where the regret bound for the i-th objective becomes (AA( (Vd' H + e)]l² with denot- ing the degree of misspecification.
In contrast, many real-world decision makiing problems re- quire the simultancous optimization of multiple, often con- flicting objectives. For example, in autonomous driving, systems must simultaneously optimize safety and efficiency (Zhang et al., 2023), while energy management systems face trade-offs between cost and sustainability (Qiao et al., 2023). Traditional single-objective RL methods are are insufficient for handling the complexities arising from multiple objec- tives, motivating the development of Multi-objective Re- inforcement Learning (MORL) (Gábor et al., 1998; Roi- jers et al., 2013; Abdolmaleki et al., 2020; Xu et al., 2020; Momma et al., 2022; Skalse et al., 2022; Cai et al., 2023).
+
Recent work in MORL extends conventional RL frame- works to accommodate multiple objectives through two pri- mary approaches: (1) reward aggregation, which combine multiple objectives into single objective using weighted sums other scalarization techniques (Roijers et al., 2013). However, this method is highly sensitive to the choice of weights and requires precise knowledge of the relative im- portance of the objectives, which may not always be avail- able or straightforward. (2) Pareto front construction, which assumes all objectives hold equal importance and employs Pareto dominance to identify Pareto-optimal decisions (Xu et al., 2020). Although this method does not require knowl- edge of objective importance, it may lack practical appli- cability in cases where the objectives are not of equal im- portance. For example, a hotel recommendation system must prioritize price, location, and service according to user preferences (Yager et al., 2011).
1. Introduction
Reinforcement Learning (RL) is a powerful paradigm wherein an agent learns solve tasks through iterative trial and error with unknown environment, dynamically ad- justing its actions based received reward signals (Sutton & Barto, 2018). This framework has proven effective in tackling complex decision decision-making challenges across var- ious domains, including robotics (Kober et al., 2013), fi-
'Department of Computer Science, City University of Hong Kong, Hong Kong, China "Shoool of Software Technology. Zhe- jiang University, Ningbo, China. Correspondence to: Qingfu Zhang waa.gfu.hhan@ecitu...o
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
To overcome these limitations, growing line of MORL

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
research has introduced lexicographic reward structures that enforce hierarchical optimization of objectives (Gábor et al., 1998; Wray & Zilberstein, 2015; Skalse et al., 2022; Ter- can & Prabhu, 2024). This approach optimizes objectives hierarchically, ensuring that the most critical objectives are prioritized while still enabling effective optimization of sec- ondary objectives. Such a hierarchical structure offers a more flexible and practical solution for Decision-making in complex scenarios where the relative importance of objec- tives is partially known.
Table I. Comparisons of the regret bounds for linear RI..
Algorithm
Objectives
Regret
Jin al. (2020)
Single
Ō(V
Zanette et al. (2020)
Single
Ö(Vo-HAK + Ho
He et al. (2023)
Single
Ö(V@H + d²Ht))
This work
Multiple
Ö(A(A)) V(HHAK)
of Ō(A( (V@H'*+ maintaining ro- bustness to model inaccuracies.
Although algorithmic advances has been made in MORL concerning scalarization methods (Roijers et al., 2013), Pareto front construction (Xu et al., 2020) and lexicographic rewards (Skalse et al., 2022), most of them heavily focused on empirical evaluations, with limited attention given to theoretical guarantees. This lack of analysis has hindered the development of principled algorithms with provable performance bounds. To bridge this gap, we leverage es- tablished theoretical foundations in single-objective linear reinforcement learning (He et al., 2023; Jin et al., 2020) and extend them to the finite-horizon MORL, framework, specifically focusing on environments with linear transition kernels and reward functions. We term this framework Multi-Objectio Linear Reinforcement Learning (MOLRL). Our work provides a comprehensive theoretical analysis of regret bounds, thereby contributing to the development of more robust and scalable solutions in this field.
As shown in Table 1, our algorithm achieves a regret bound comparable to single-objective RL algorithms in terms of the leading-order term K, while simultane- ously optimizing multiple objectives.
2. Related Work
In this section, we briefly review the development of linear RL and multi-objective RL.
2.1. Linear Reinforcement Learning
The existing literature on linear reinforcement learning can be broadly categorized into two main research directions. The first direction focuses on establishing minimax-type re- gret bounds for proposed algorithms. Yang & Wang (2019) assumed linearity in both the reward function and transition probabilities and analyzed the complexity of finding an e- optimal policy. Later, Jin et al. (2020) focused on regret minimization, proposing a linear RL algorithm that achieves regret bound of O(v H K). Their algorithm can also be applied misspecified linear RL, attaining regret bound of DVV + edH K). In an improved approach, Vial et al. (2022) introduced a parameter-free algorithm for the misspecified linear RL problem, which does not require knowledge of the misspecification level e. Zanette et al. (2020) applied the Thompson sampling approach to linear RL, achieving regret bound of O(Vd*H*K) He al. (2023) developed computationally efficient algorithm with regret bound of O( + d² HD) for linear RL.
To the best of our knowledge, this the first work to address MOLRL with lexicographic rewards. A key challenge in this setting that the Bellman optimality equation (Sutton & Barto, 2018) does not hold, which invalidates greedy action-selection strategies, such as LSVI-UCB (Jin et al., 2020) and LSVI-UCB++ (He et al., 2023). We tackle this challenge and make the following contributions:
We propose an MOLRL algorithm that decomposes the seiin--election process into multiple stages, enabling a more refined balance between conflicting objectives. This approach prioritizes higher-level objectives while effectively managing lower-level ones.
For the proposed algorithm, we derive a regret bound of ((A(A)) vd²H for any objective E (1,2,... m), where m is the number of objectives and (A) = + X depicts the trade-off between conflicting objectives, d is the feature vector dimension, H denotes the episode length, and K is the total number of episodes.
The second research direction emphasizes deriving gap- dependent regret bounds for linear RL. He et al. (2021) established a regret bound of Odd HD / A (o)( for the algorithm of Jin et al. (2020), where A is the minimal sub- optimality gap. More recently. Zhang et al. (2024a) pro- posed an improved algorithm that achieves regret bound of (d H3 /A), which is independent of the episode num- ber K. Additionally, other studies have explored linear RL. in various settings. Zhou et al. (2021) achieved a nearly opti- mal minimax regret bound for RL with linear mixture MDPs, where the transition probability is a linear combination of several base models. Li et al. (2024b) analyzed dynamic
Our algorithm can be applied in the misspecified MOLRL setting, where the transition kernel and reward function of the true environment are approximated by linear functions with a misspecification level of e 2 O. In this setting, our algorithm achieves a regret bound
2

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
regret bounds for adversarial linear mixture MDPs, where optimal policies change over time. Dai et al. (2024) stud- ied multi-agent linear RL, in which multiple agents share a common state space but have independent action spaces. However, these studies mainly address single-objective set- tings and do not extend to multi-objectivee problems.
symbols associated with different objectives and the symbol ()) signifies that the variable is an estimate, e.g., Q'(::) is the estimated action-value function for the i-th objective. The Euclidean norm of a vector & E R is denoted by || The norm induced by a positive-definite matrix U E RRdd is defined by | T-
MORL. MORL a framework which an agent interacts with an environment to learn an optimal policy. Formally, Multi-Objectivy Markov Decision Process (MOMDP), defined by the tuple (S, A, H, P, r)), where S is the state space, A is the action space, H E Z_ is the length of each episode. P = { { and r {rr ) are the transition probability functions and reward functions for each h E H. Specifically, IP, IP (a'[xx a) represents the probability of transitioning from state x E S to state x' 8 after taking action at step h, rh : S A + [0, 1Jth. is deterministic function that maps state-action pair (z, a) in to reward vector
2.2. Multi-objective Reinforcement Learning
Early approaches to MORL employed scalarization meth- ods, which aggregate the reward vector into a single scalar through a weighted sum (Roijers et al., 2013; Van Moffaert et al.. 2013; Agarwal et al., 2022). Although these meth- ods are simple and intuitive, they require careful tuning of the weights (Abels et al., 2019; Yang et al., 2019). More recent MORL research has explored alternative strategies to address these challenges. For instance, Abdolmaleki et al. (2020) proposed encoding preferences via constraints on each objective, enabling the specification of desired prefer- ences in a ccale-invariant manner. Xu et al. (2020) incor- porated the multi-objective policy gradient method into evolutionary framework to identify set of Pareto-optimal policies, where no objective can be improved without de- grading another. Momma et al. (2022) introduced a general framework capable of incorporating multiple forms of pref- erences to identify Pareto-optimal policies.
MORL is modeled
step h E [H]] The reward function
r4 a) = [2) r a). ...,,,.,, rh (z, a)),
where (2, a) is the reward corresponding to the objective E [m]] and m is the number of objectives.
A policy of an agent is a function x S x [H] - A, where (zz h) specifies the action that the agent takes at state x E S and step h E [H]. For each objective i E [m]] and state-action pair (z, a) E S x A, the action-value function Qz,n (Ir, a) (also known as the Q-function) and the value function Vi,n(2) of policy π are defined as
In the context of MORL with lexicographic rewards, Gábor et al. (1998) first formalized this problem and introduced preedy-based algorithm to solve it. Wray et al. (2015) introduced the slack-based Lexicographic RI., which allows for deviations from the optimal policy rather than adhering to absolute thresholds. More recently, Skalse et al. (2022) presented a family of algorithms based on action-value and policy gradient methods for solving lexicographic MORL. In the simplified setting of lexicographic bandits (i.e., RL with horizon H = 1). related work has been conducted multi-armed bandits (Hüyük& & Tekin, 2021), contextual bandits (Turgay et al., 2018), Lipschitz bandits (Xue et al., 2024), and linear bandits (Xue et al., 2025).
2 a) = (1,
#
E
Σ
In = x, as
Liv
H
V V (x) = E
Σ
(Dw,, and I = x
Let (P,V] = B (.) (V (x') denote the ex- pected value of function V under the transition dynamics PR. The Bellman equation for objective E [m]] is
(-1a,,)
While many existing MORL studies focus primarily on em- pirical evaluations, several also offer valuable theoretical insights, such as convergence analyses and structural re- sults (e.g., (Gábor et al., 1998)). However, formal regret guarantees, particularly in the setting of linear MDPs, re- main underexplored. To address this gap, we present comprehensive theoretical analysis of regret bounds within the MORL framework, thereby paving the way for more robust and scalable solutions in this domain.
(2, ri + IPA (i (x)(x)= = f. (z, (2)
(1)
This formulation provides a recursive relationship between the Q-function and the value function, which is fundamental to the analysis and optimization of policies in RL.
The Learning Process. The learning process in MORL comprises K episodes. At the start of each episode k = 1, 1, K, the agent selects a policy Tr based on data collected from the previous 1 episodes. The agent then interacts with the environment following Hi over H time
3. Preliminaries
Notation. For any positive integer N E E4. we define [N] A (1, Nj. The superscript E [m] distinguishes
3

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
steps. At each step h = -,,2...., H, the agent observes the environment state F and selects action dk.A Th (2 h). Subsequently, the environment transitions to new state TR,h+11 ~ PA. (-) (g.h) and provides the agent with a reward vector Pk. After completing all H steps, the agent collects the data { ag.h, J and uses it to refine its policy, thereby improving future pacision-making
Here, Vi(=) = (w((x), rhand where w(x) HR--h+ is shared weighting vector across all objectives, and rieh [rA( (), -), ( (:.))...., (....)).
Here, À bounds the improvement in the value of the i-th objective for each unit decrease in the preceding 1 ob- jectives. In multi-objectinn optimization, objectives often conflict, thus it is common to introduce parameters to quan- tify trade-offs, such as the global trade-off (Miettinen, 1999), the marginal rate of substitution (Miettinen, 1999), and the allowable trade-off (Wiecek, 2007).
How to evaluate policies in a multi-objective context re- mains open issue. Since conflicting objectives cannot be maximized simultaneously, multi-objective work defines notion of dominance to compare reward vectors and assess policies, such as Pareto dominance (Xu et al., 2020) and lexicographic dominance (Skalse et al., 2022). In this pa- per, we adopt the lexicographic order, where objectives are prioritized. The formal definition is as follows.
In this paper, we focus on the linear MOMDP, a natural ex- tension of linear MDP (Jin et al., 2020), defined as follows:
Definition 3. M H..r is linear MOMDP with a feature map Φ= S x A -> TR., if for any h E [H], there exist unknown measures (.(())
::S
Definition 1 (Lexicographic Order). Consider two vec- tors u- = [u',...; w=)) v = [u'...., ,v"] E R". u lexi- cographically dominates v if and only if there exists some i" E [m] such that u² = v² for i E li- - 1] and wt > v²".
+ Rd and unknown vectors 0% E R.", such that for any (sr, a) E x A.
(a a) = (6(2, a), pm (a) (1), (2, a) (0(2,, (((z,a),00 0,),,
Lexicographic order compares vectors element-wise, start- ing from the first and proceeding sequentially to the last. For example, 35,3,4 4] lexicographically dominates [5, 2] and [4, 8, 1]. Based on this ordering, we define the lexico- graphically optimal policy (Skalse et al., 2022).
where lI0(z, a)ll I 1 for all (z, E S x A, and max( 11111) S for all h E [H] and i E [m]]
In environments with large state and action spaces, linear structure significantly reduces computational complexity, and well-established mathematical techniques and tools for the liner model facilitate rigorous analysis. Regarding the relationship between general and linear MDP, any MDP with finite state space S and action space A can be represented as a linear MDP by encoding each state-action pair (xc a) as a one-hot feature vector in Rdd where d = |S] x |AA.. The transition kernel (- 2 a) and reward function r (2, a) can be expressed inner products between the feature vector of (zz a) and learnable parameters.
Definition 2 (I elxxioggraphically Optimal Policy). A pol- icy R. is lexicographically optimal if and only if. for any a E S, its vector of values [V=.., (x), Vmm, (x)] is not lexicographically dominated by that of any other policy.
A lexicographically optimal policy ensures that the most important objective is maximized, while still allowing some optimization of the lower-priority objectives.
Following single-objective RL (Jin et al., 2020), we evaluate the performance of the agent by regret, which quantifies the difference between the accumulated rewards of the agent's ss policy and those of lexicographically optimal policy, i.e.,
4. Algorithm
K
In this section, we present the Lexicographic Linear Rein- forcement Learning (LLRL) algorithm, which effectively combines the computational efficiency of linear MOMDPs with the hierarchical prioritization inherent in lexicographic rewards, ensuring that higher-priority objectives are maxi- mized before considering lower- ones.
R$ R²(K) = Σ V (# - V (IR,1), i [m].
To establish a regret bound for MORL. we quantify the trade-offs among confficting objectives as follows.
Assumption 1. Let Qf, a) = (x, a) + [PA Viataa a) for any E [m]] and (z, a, h) E S x x [H. Let (z, h) denote the action chosen by a lexicographically optimal policy at (x, h). We assume (x, h) is the lexicographic optimal action for Qj (z. a) and the trade-off among objec- tives is governed by X 2 O, such that for all lt E [H] and i E [m).
Initialization. LLRL learns the optimal policy over K episodes, with each episode comprises H interaction steps with the environment. Initially, the covariance matrix Uj, is initialized as the identity matrix 1 E dxd for all h [H]]. Similarly, the p-functions (.-) are initialized to zero for all objectives i E [m]] and time steps h E [H]. Both the covariance matrix and Q-functions are updated iteratively across episodes based on the rewards received at each step. At the terminal step H + the functions for all objectives are set to zero, as no further rewards can be obtained.
Q1 a)- - (2, h1)
{ (1) n. (x, - (1(
S A max
]E
4

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
Algorithm I Lexicographic Linear Reinforcement Learning
Algorithm 2 Lxxicographi Action Elimination
Input: ó,d, m, K, H, X, { ]EEK]]
Input: {Ộ) (ax - kemm) .k. A.. C
1: Initialize Un = T, (x+))
(()) = 0,
1: Initialize Al = As
vh E { Q1 + (s.))
2: for i 1.2,..., m do
2: for k- ===1 ..2...., K do
3: 0 argmaxxE
Q (T),,,
3: Receive the initial state IR.1
4: A = fa E A (T k/) - (
4: for h = 2, ..... H do
(2 + 4A + ... + 11111) Bx C}
5: Initialize = 1, = A
5: end for
6: repeat
6: Returr AT
7: if [1 a) llu. $ 1/VKK KyKKVa Va E A, then
8:
Run Algorithm 2 to refine actions: AK =
LAE([ (z )eemm)) 3r. As, 1/VK)
(LAE) algorithm (Algorithm 2) to refine the candidate action set, producing a smaller subset of promising actions Ax. An action Λg is then randomly selected from Ak. LAE uses the estimated Q-functions Q% (TA.A. -) and the uncertainty bound 1/ /K to sequentially eliminate suboptimal actions from Ag by the priority of objectives. Further details on the LAE are provided in the following content.
9:
Randomly take an action a E AK
10:
else if [| ulu, > - 3ak, E As then
11:
Take the action 4/sh else
12:
13:
Run Algorithm to refine actions: Ao+1 = LAB( (AB((Q% (Q2 ( Nejm)) Sx.
2)
14:
Update =s+1
(ii) If [| 4s,A) Il,, > 2- for some action OK,A E As. this action is directly selected due to its high uncertainty, which requires further exploration.
15:
end if
16:
until an action d is taken
17:
Observe rewards T and next state T1,h+1 end for
(iii) If all actions A, satisfy (1 (t)_,,,;aalus a)llu, 2 it implies that the uncertainty in the estimated Q-functions for all a E A, is bounded by 2 In this case, LAE is invoked again to refine the candidate set, using the uncertainty bound 2- as the exploration threshold. The stage index 8 is then incremented to 8 + for a more refined elimination process.
18:
19:
for h = H. H - 1,.... 1 do
20:
Un = Eim
an ara)) T +1
21:
Pr.m = r+ + (2T,
VT E [k]
and E [m]
22:
unj, = h - ( 07,)) h. Vi E [m]
23:
Update the estimated Q-function: (x, =
This iterative process continues until an action is selected. Once action 0k.h is chosen, LLRL observes the corre- sponding reward PA,A [rk T.A ................................ ,... and transi- tions to the next state 24,4+11. The episode concludes after all H steps are completed. The intuition behind this policy design is further discussed in Section 6.
(z)) 6(2, a)), V(2,a) E S x A and i e [m]
24:
end for
25:
end for
Decision-making, each episode, LLRL begins by receiv- ing an initial state I and then enters into H interaction steps. At each step h = 2, H. LLRL selects an action by balancing exploration (i.e., acquiring information about rarely observed actions) and exploitation (i.e., choosing the most promising action). ). To manage trade-offs among differ- ent objectives, the decision making process is divided into multiple stages. Actions are refined based on uncertainty checks and lexicographic prioritization.
Lexicographic Action Elimination. LAE plays a crucial role in balaneing trade-off's among conflicting objectives. It iteratively refines the action set by prioritizing objectives sequentially, from the first to the last. Initially, LAE defines the action set as A = A,, which contains all candidate actions of the current stage. For each objective é E [m]] LAE selects the action aj,n E A that maximizes the estimated Q-value Q), (Ja,,n a), i.e.
af. argmax Q (ER,..))) GEAt-1
Before the decision-making process begins, LLRL initial- izes the stage index s = 1 and the candidate action set A, = A. Then, LLRL iteratively refines the candidate ac- tions until a final action is chosen. For the given state Tk,h of current step, L.RL considers three scenarios:
This action, at serves as the reference point to eliminate suboptimal actions. Precisely, LAE removes actions whose estimated Q-values deviate significantly from aj. i.c.
(i) IF [| a) I| S J for all a E A.. this indicates that all actions in Ag have been sufficiently explored. In this case, L.RL invokes the Lexicographic Action Flimination
A = fa E 1 (IK,A alex)) Q2 (1 (.n,n.a)) a) $ (2 41 + + +4x--1 Br -C..
5

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
where C' is dynamically adjusted threshold balance exploration and exploitation. Specifically, C = 1//KK in case (i), and C' = =2 2- in case (iii) of the s-th stage.
Finally, the estimated Q-function ( for objective i e [m]] is updated using the newly obtained parameter rij,, i.e.,
(x, = (1if. o(z, a)). ((z,)) E S x A.
(5)
After processing all m objectives, the final set A consists of actions deemed promising across all objectives and can be returned to LLRL for a more refined decision-making process in the next stage + 1.
The steps outlined in Eqs. (2), (3), (4), and (5) constitute the core of the backward pass in the LLRL algorithm. By iter- atively updating the Q-functions of each objective, LLRL reduces uncertainty in parameter estimation and progres- sively improves the agent's 's policies over time.
Policy Update. In each episode k after completing its inter- actions with the environment, the agent gathers the dataset (TIL,,, 4K,A, Fk,A ) and initiates backward update pro- cedure. Owing to the linear structure of the linear MDP, the inherent Q-function 2r,a(, for any objective i E [m]] and policy x exhibits linearity with respect to the feature vector ((2, a). This property is formally expressed in the following proposition, which generalizes Proposition 2.3 of Jin et al. (2020) to multi-objective context.
5. Theoretical Guarantees
In this section, we provide the regret bounds for LLRL to rig- orously analyze its performance. We establish two theorems that offer theoretical guarantees for different models. Specif- ically, Theorem I characterizes the performance of LLRL in the linear MOMDP setting, while Theorem 2 examines its behavior in the e-approximate linear MOMDP. These results not only validate the reliability of LLRL across different scenarios but also provide insights into its limitations.
Proposition 1. In a linear MOMDP, for any objective E [mi] and any policy n, there exist weights f such that for any (x, a, E ESx x A [H], we have (n,(( = (0(2,, (), w
Theorem 1. Let (A(A) - 1 + X + ... + X for i E [m]. For a linear MOMDP. if LLRL is run with Bx =
Based on Proposition 1, LLRL estimates Qir, a (ar, a) follow- ing the procedure of least-squares estimation. According to the Bellman equation (Eq. (I)). the Q-function at the h-th step a² / is influenced by the future value function V -. Therefore, the estimation process starts from the final step h H and proceeds backward the first step h
3H V d'log (2mpe)) then with probability at least 1 - 28, the regret for any objective i [m] satisfies
R²(K) Sō (0((()))))))) (N(A).VRH-K
Remark Theorem states that for linear MOMDPs with lexicographic rewards, LLRL achieves a regret bound of Ô (Ai()) V(=HIK) for any objective i E [m]. This matches the near-optimal dependence on fcature dimension d and time horizon K observed in single-objective RL (He et al., 2023). The multiplicative factor A' (A) quantifies the trade-off in lexicographic optimization: for the primary objective, A (A) = 1 leads to improved bound compared to single-objective baselines (Jin et al., 2020) in terms of d while lower-priority objectives incur increasing regret as A (2) grows with their position i in the priority hierarchy.
During the backward pass, for each step h = H...., 1,
LLRL first updates the covariance matrix Un using the fea- ture vectors observed at the h-th step of previous episodes:
* UA = Σ (IT,, (o +I. I.
7=1
Subsequently, to perform least-squares estimation for ob- jective i E [m]. LLRL combines the immediate reward ri,n and the future Q-value Qh+11 (IR,, 11,4+1) to form surrogate reward, given by:
f = rk, + Qh+ (1
(3)
Theorem I relies on the linear structure of the MDP. How- ever, real-world applications often involve nonlinear MDPs, leading to potential misspecification when assuming linear- ity. To address this, we first introduce an approximate linear model and then establish the regret bounds of LLRL under such misspecified conditions.
This bootstrapping procedure integrates immediate rewards with long-term Q-values, aligning with the principle of Bell- man equation (1).
LLRL then estimates the parameter wi A. for objective i E [m] using least-squares estimation, formulated as:
Definition 4. M(S. H,P, r)) is an c-approximate linear MOMDP with a feature map & : S x A Ed if for any h E [H) there exist unknown measures pm(-)) S - Rd and unknown vectors Oz E IRd, such that for any (z, a) e
wi = argmin weRd
((b(TT, ar,n): w)) P p),N))
||
(4)
S x A.
[P a) - (6(I, a). (n)-))11 S
Σ
Fr H( (r.).
(6)
h
(r)(2, a) - (ola,, a), 0
6

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
where (,, a)ll < 1 for all (z, a) E 8 x A, and max max(llen (1)))) [0011] S for all h E [H] and i E [m]-
and highlight our techniques to resolve them.
Theorem 2. Let (A) = - ... + x for E [m]] For an e-approximate linear MOMDP, LLRL is run with
6.1. Challenges
Optimal Action Preservation Dilemma. The first chal- lenge in the lexicographic setting is how keep the optimal action during action elimination procedures. Lexicographic RL requires sequential elimination across objectives, but uncertainty in transition dynamics Py, (-Jar, a) brings optimal action preservation risks during confidence interval-based climination. Precisely, when addressing the i-th objective, the agent constructs the confidence intervals of Q-values and eliminates actions whose Q-value intervals do not overlap with that of the most promising action. In the lexicographic setting, however, the confidence interval of the lexicograph- ically optimal action may not overlap with that of the most promising action, leading to the loss of the optimal action. An example is provided to illustrate this issue.
3x = 3Hl dog 22mHH) + 2H kd and the threshold C in LAE is modified by C + 2H,, then with probability at
least 1 - 8, the regret for any objective i E [ml] satisfies
S ) (NO(N) (AN0))(Vi--It))) (Vi-II*K+ + <edff*))
Remark 2. Theorem 2 states that for c-approximate linear MOMDPs with lexicographic rewards, LLRL achieves a re- gret bound of Ō (A)()) (VæHHA + =eff2k) for any objective i E [mm]. This matches the dependence on e, H, and K observed in single-objective RL (Jin et al., 2020), while improving the dependence on d. The linear model serves as an approximation of the true environment. Com- pared to Theorem 1, the additional regret term ()) stems from approximation error, which decreases as model accuracy improves.
Example 1. Suppose there are three Q-value vectors: [5, 5, 5), [1, 5] and [4, 10, for actions a1, 02 and ag, re- spectively. a1 is the lexicographically optimal action. When eliminating actions based on the first objective, 02 is elim- inated because 1 is far from 5. but is kept as 4 is close to 5. After this step, only actions {a1,03} are contained in the candidate action. Next, the agent proceeds to eliminate actions based on the second objective. Since 10 much big- ger than 5, thus the optimal action ai is eliminated, which is disappointing because ag is awful for the third objective.
Complexity Analysis. We provide detailed complexity analysis of Algorithm 1 and discuss its computational limi- tations. In Step 7, the complexity is ((d))A) while Step 8 requires O (mdl_A) computations due to the LAE procedure. Step 22 incurs a computational cost of Ommkd + mdd"), pri- marily driven by the matrix inversion of Un (O())) and the computation of m linear regressions (i.e., Omkd md))). Summing over all H layers of the MDP, the overall com- plexity becomes ((Hmd) A|| + H | Hmkdd++ + Hmdd).
This demonstrates that standard elimination techniques may discard the lexicographically optimal action, necessitating novel preservation mechanisms.
When aggregated over K rounds, the total computational complexity is O(K H AI + d) + 2 + K m Notably, the O(3)) term results in significantly higher com- plexity compared to standard bandit algorithms (Xue et al., 2025). Nevertheless, our approach remains competitive with existing methods for single-objective MDP (Jin al., 2020; Zanette et al., 2020; He et al., 2023).
Failure of Bellman Optimality. Another challenge is to develop decision-making approach that progressively con- verges to the optimal policy. In single-objective RL, the Bellman optimality equation serves as foundation for al- gorithm design and theoretical analysis. It characterizes the optimal value function through an intuitive decision-making process and a recursive relationship. i.c.,
Further Improvements. As summarized in Table I, our al- gorithm's 's regret bound remains slightly higher than the near- optimal WVV2H'K + d² (²) bound for singlc-objective linear MDPs in terms of Н (He et al., 2023). This gap does not stem from a fundamental limitation but our cur- rent policy update mechanism, which employs simpler approach compared to advanced methods. By incorporat- ing the LSVI-UCB+ update framework (He et al., 2023), we anticipate refining L.RII. to achieve an improved regret bound of Ö (A) (VæHHa + d' HH)) We plan to investigate this promising direction in future research.
(x) = max ( a), aEA
(x,,n(2,a) = (x a) + [IA MI)
where we omit the superscript for single-objective notation. This framework enables straightforward policies like:
ag,h = argmax (ZK,h)))))
(8)
aeA
as employed in LSVI-UCB (Jin et al., 2020) and LSVI- UCB++ (He et al., 2023).
In the lexicographic setting, this structure breaks down for secondary objectives, as shown in the following example. Example 2. Let [Q (z, a1), Q2 (z, a1)] = [2.3] and (tt. M (x, 02), Q2 n (z. 0z) = [1, 4) for actions a1 02 e
6. Challenges and Key Techniques
In this section, we analyze the main challenges in designing algorithms for linear MOMDPs with lexicographic rewards
7

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
A and x E S. Since (2, 3) lexicographically dominates [1, 4). the lexicographically optimal action n. (x, a1. Ac- cording to the Bellman equation (1), we obtain V22 (x)
Now, we highlight how to avoid losing the lexicographically optimal action. Lemma reveals that all objectives share common confidence term fx [1, a) l distinctive feature of MOMDPs. To ensure the overlap between con- fidence intervals of lexicographically optimal actions and the most promising action of current round, we scale the confidence term. As detailed in Algorithm 2, the confidence
Oz. (2, h)) = 3. However, for the second objective, the maximum Q-value is maXae (2) Q ( = 4, which does not equal to V2 (x)).
This example establishes the following proposition. Proposition 2. There exists an MOMDP with lexicographic rewards problem, where for some (a, a) E 8 x A and E [m]]
term C' is scaled by the following factor:
2 2 4A + + +4X
which is specially designed to guarantee the confidence intervals of the lexicographic optimal action and the most promising action of current round overlap. Therefore, the lexicographically optimal action is preserved, formalized in the following lemma:
(z) # max Q*,,,
aEA
for the lexicographically optimal poliy ...
This divergence from Bellman optimality complicates both algorithm design and theoretical analysis, precluding the direct methods like Eq. (8).
Lemma 3. For Algorithm 2, (z, h) E Ag, then with probability at least 1 - 6, for any objective i E [m] and action a E A'g, we have
6.2. Key Techniques
(, E A', and
In this part, we highlight the key techniques used to address the aforementioned challenges.
(t,
BB C.
For clarity, we denote Uk... u and Qi,, i, as the param- eters and the estimated Q-function at episode k, with m representing the policy k-th episode. The estimated value function K.A is defined as Vi (x) = Qi (I, (2, h)). k. h) E S x A x [K] x [H], we define the surrogate Q-function for objective i E [m] as
Finally, we highlight the basic idea of dealing with the failure of Bellman optimality in MORL. Since the Bellman optimality equation does not hold, direct maximization of Q- values fails to recover lexicographically optimal actions due to conflicting objectives and environment uncertainty. As an alternative, LLRL initiates a multi-stage action refinement process, which progressively eliminates suboptimal actions using geometrically decreasing confidence thresholds 2 This mechanism operates in three regimes: 1) Aggressive pruning under low uncertainty. 2) Exploration prioritiza- tion for high-uncertainty actions [, a) Ul > 2-*, and 3) manfidence-constraine elimination via the LAE sub- routine for intermediate uncertainty As+1 = LAE(., Crucially, lexicographic optimality is preserved through overlapping confidence intervals, ensuring the retention of lexicographically optimal actions despite Bellman equation violations. By replacing Q-maximization with threshold- adaptive elimination paradigm, LLRL decouples action selection from Bellman optimality assumptions while con- trolling cumulative suboptimality via geometrically tighten- ing thresholds. The resultant value function gap, formalized in Lemma 4, quantifies how uncertainty reduction across stages drives convergence to near-optimal policies.
For any (x,
[ SzeS
(1,(( a) = (1,( r
Vi 1 (n'') a))'''
Since rí (x, a) and (1 xx a) depend on the unknown pa- rameters 0% and su (a'), respectively, we first provide con- fidence intervals for the surrogate Q-functions.
Lemma 1. Let 3x 3H V ddlo
2mmk H
5
With probability
at least 1 - for all (z, a, k, h) E Ax [K] x [H] and i E [m)) we have
[(0s,, a), wi. (x, < Ballola (ao,,)))lla a)ll
Building on this, we analyze the discrepancy between esti- mated and inherent value functions under policy Te:
Lemma 2. Let oi ( (T n (IH, and Ch.n SE - Elog, 1 R. With probability at least - 8, for any (k, h) E [K] x [H] and i E [mi) we have
Lemma 4. With probability at least 1 8, for all (z, h) E S Ax [K] x [H] and i E [m]. we have
(xH,)) Vi (zk.h) 11
H
23x 2 (wwww) +
Σ
V V (x V4 (IK S
Σ (0A h'=h
W=
M=h+1
where sy.w (IK.)) denotes the stage at which LLRL selects the action for state Ik.h
where Sk,N (Z denotes the stage at which LLRL selects the action for state 2g.30-
8

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
As the learning process advances, the uncertainty in value estimation diminishes geometrically, evidenced by the ponential decay of the term 2 2- This ensures the estimated value functions Vg, converge toward their optimal counterparts V=, .h- By combining Lemma 2 and bound the per-episode instantaneous re-
Abdolmaleki, A., Huang, S., Hasenclever, L., Neunert, M., Song, F., Zambelli, M., Martins, M., Heess, N., Hadsell, R., and Riedmiller, M. A distributional view multi- objective policy optimization. In Proceedings of the 37th International Conference on Machine Learning, pp. 11-
Lemma 4, gret (vE,,) - V (3E,1) at each episode k E [K], leading to the regret bound ((A(A)) KK) in Theo- rem 1. Please refer to appendix for more details.
22, 2020.
Abels, A., Roijers, D., Lenaerts, T., Nowé, A., and Steck- elmacher, D. Dynamic weights in multi-objectivee deep reinforcement learning. In Proceedings of the 36th In- ternational Conference on Machine Learning, pp. 11-20, 2019.
7. Conclusion and Future Work
This work establishes the first theoretical regret guaran- tee for MORL. We propose the LLRL algorithm, which addresses the failure of Bellman optimality through multi- stage iefiidenneeguuded elimination strategy. By decompos- ing action selection into refined phases with geometrically decaying thresholds 2 LLRL attains a regret bound of (A) dd k) for all objectives i [m], matching single-objective baselines (Jin et al., 2020; He et al., 2023) in leading K -edependence. Meanwhile, (A) = 1 indi- cates LLRL recover the near-optimal regret bounds of He et al. (2023) for the first objective in terms of both d and K. Furthermore, LLRL naturally extends to misspecified settings through minor algorithmic modifications, maintain- ing (A) & + K)] regret- - crucial robustness property for practical applications.
A Agarwal, M., Aggarwal, V., and Lan, T. Multi-objective re- inforcement learning with non-linear scalarization. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pp. 9-17, 2022. Cai, X.-Q.. Zhang, P., Zhao, L.,, Jiang, B., Sugiyama, M., and Llorens, A. J. Distributional pareto-optimal multi- objective reinforcement learning. In Advances in Neural Information Processing Systems 36, pp. 15593-15613, 2023.
Cassel, A., Luo, H., Rosenberg, A., and Sotnikov, D. Near- optimal regret in linear mdps with aggregate bandit feed- back. In Proceedings of the 4 st International Conference on Machine Learming, pp. 5757-5791, 2024.
While our analysis relies on Assumption 1 to manage inter- objective trade-offs, a fundamental open question is whether comparable regret bounds can be derived without this as- sumption. Additional directions include improving the re- gret bound of our algorithm by employing the policy update mechanism of He et al. (2023).
Chu, W., Li. L., Reyzin, L., and Schapire, R. Contextual bandits with linear payoff functions. In Proceedings the 14th International Conference on Artificial Intelligence and Statistics, pp. 208-214, 2011.
Dai, Y., Cui, Q. and Du, S. S. Refined sample complex- ity for markov games with independent linear function approximation. In Proceedings of 37th Conference on Learning Theory, pp. 1260-1261, 2024.
Acknowledgements
The work described in this paper was supported by the Research Grants Council of the Hong Kong Special Admin- istrative Region, China [GRF Project No. CityU 11215622).
Gábor, Z., Kalmár, Z., and Szepesvári, C. Multi-criteria reinforcement learning. In Proceedings of the 15th Inter- national Conference on Machine Learning, pp. 197-205, 1998.
Impact Statement
He, J., Zhou, D., and Gu, Q. Logarithmic regret for rein- forcement learning with linear function approximation. In Proceedings of the 38th International Conference on Machine Learning, pp. 4171 41880, 2021.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
He, J., Zhao H., Zhou, D., and Gu, Q. Nearly minimax op- timal reinforcement learning for linear Markov decision processes. In Proceedings of the 40th International Con- ference on Machine Learning, pp. 12790-12822, 2023.
References
Abbasi-yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24, pp. 2312- 2320, 2011.
Hüyük, A. and Tekin, C. Multi-objective multi-armed bandit with lexicographically ordered and satisficing objectives. Machine Learning, 110(6):122) (0000:1233-1200 1266, 2021.

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
Jin, C.,, Yang, Z., Wang, Z., and Jordan, M. I. Provably effi cient reinforcement learning with linear function approxi- mation. In Proceedings of 33rd Conference on Learning Theory, pp. 2137-2143 2020.
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An
Introduction. The MIT Press, second edition, 2018.
Tercan, A. and Prabhu, V. S. Thresholded lexicographic ordered multiobjective reinforcement learning. In The 27th European Conference on Artificial Intelligence, pp. 2024.
Kober, J., Bagnell, J. A., and Peters, J. Reinforcement learning in robotics: A survey. International Journal of Robotics Research, 32(11):1238 -2744 2013.
Turgay, E., Oner, D., and Tekin, C. Multi-objective con- textual bandit problem with similarity information. In Proceedings of the 2 International Conference on Arti- ficial Intelligence and Statistics, pp. 1673-1681, 2018.
Li, L.F., Zhang, Y.JJ., Zhao, P., and Zhou, Z.-H. Provably efficient reinforcement learning with multinomial logit function approximation. In Advances in Neural Informa- tion Processing Systems 37, pp. 58539-58573, 2024a.
Van Moffaert, K., Drugan, M. M., and Nowé, A. Scalar- ized multi-objective reinforcement learning: Novel de- sign techniques. In 2013 IEEE Symposium on Adaptive Dynamic Programminng and Reinforcement Learning, Pp. 191-199, 2013.
Li, L.-F., Zhao, P., and Zhou, Z.-H. Near-optimal dynamic regret for adversarial linear mixture mdps. Advances in Neural Information Processing Systems 37, pp. 55858- 55883, 2024b.
Vial, D., Parulekar, A., Shakkottai, S., and Srikant, R. Im- proved algorithms for misspecified linear markov deci- sion processes. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, pp. 4723-4744 2022.
Li, X. and Sun, Q Variance-aware decision making with linear function approximation under heavy-tailed rewards. Transactions on Machine Learning Research, pp. 2835- 8856, 2024.
Liu, X.-Y., Yang, H., Gao, J., and Wang. C. D. Finrl: deep reinforcement learning framework automate trading in quantitative finance. In Proceedings of the 2nd ACM International Conference on Al in Finance, pp. 1 1-9, 2022.
Wiecek, M. M. Advances in cone-based preference model- ing for decision making with multiple criteria. Decision Making in Manufacturing and Services, 1(2):153-173, 2007.
Merkle, F., Blossey, G., Haeussler, S., and Schneckenreither, M. Reinforcement learning in autonomous multi- vehicle systems: A structured review. In Proceedings of the 13th International Conference on Software and Computer Applications, pp. 310-317, 2024.
Wray, K., Zilberstein, S., and Mouaddib, A.-I. Multi- objective mdps with conditional lexicographic reward preferences. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, pp. 3418-3422 2015.
Wray. K. H. and Zilberstein, S. Multi-objective pomdps with lexicographic reward preferences. In Proceedings of the 24th International Joint Conference on Artificial Intelligence, pp. 1719-1725, 2015.
Miettinen, K. Nonlinear Multiobjective Optimization. Kluwer Academic Publishers, Boston, USA, 1999.
Momma, M., Dong, C.,, and Liu, J. A multi-objective / multi- task learning framework induced by pareto stationarity. In Proceedings of the 39th International Conference on Machine Learning, pp. 15895-15907, 2022.
Xiong, W., Zhong, H., Shi, C., Shen, C., Wang, L., and Zhang, T. Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent MDP and markov game. In The 11th International Con- ference on Learning Representations, 2023.
Qiao, Y., Hu, F., Xiong, W., Guo, Z., Zhou, X., and Li, Y. Multi mujti-obbjectiv optimization of integrated energy sys- tem considering installation configuration. Energy, 263: 125785, 2023.
Xu, J., Tian, Y., Ma, P., Rus, D., Sueda, S., and Matusik, W. Prediction Prediction-guided multi multi-objective reinforeement learn- ing for continuous robot control. In Proceedings of the 37th International Conference on Machine Learning, pp. 10607-10616, 2020.
Roijers, D. M., Vamplew, P., Whiteson, S., and Dazeley, R. A survey of multi-objective sequential decision-making. Journal of Artificial Intelligence Research, 48(1):67-113, 2013.
Xue, B., Cheng, J., Liu, F., Wang, Y., and Zhang, Q. Multi- objective lipschitz bandits under lexicographic ordering. pp. 16238-16246, 2024.
Skalse, J., Hammond, L., Griffin, C., and Abate, A. Lex- icographic multi-objective reinforcement learning. In Proceedings of the 31st International Joint Conference on Artificial Intelligence, pp. 1430-3436, 2022.
Xue, B., Lin, X., Zhang, X., and Zhang, Q. Multiple trade- offs: An improved approach for lexicographic linear ban- dits. pp. 21850-22 1100-28855 21858, 2025.
10

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
Yager, R. R., Gumrah, G., and Reformat, M. Z. Using web personal evaluation tool pet for lexicographic multi- criteria service selection. Knowledge-Basee Systems, 24 (7):929-949) 2011.
Yang, L. and Wang, M. Sample-optimal parametric q- learning using linearly additive features. In Proceedings of the 36th International Conference Machine Learn- ing., pp. 6995-7004, 2019.
Yang, R. Sun, X., and Narasimhan, K. generalized algorithm for multi-objective reinforcement learning and policy adaptation. In Advances in Neural Information Processing Systems 32, pp. 14636 14647, 2019.
Yu, C., Liu, J., Nemati, S., and Yin, G. Reinforcement learn- ing in healthcare: survey, ACM Computing Surveys, 55 (1), 2021.
Zanette, A., Brandfonbrener, D., Brunskill, E., Pirotta, M., and Lazarie, A. Frequentist regret bounds for randomized least-squares value iteration. In Proceedings of the 23rd International Conference Artificial Intelligence and Statistics, pp. 1954-1964, 2020.
Zhang. H., Lin, Y., Han, S., and Lv, K. Lexicographic actor- critic deep reinforcement learning for urban autonomous driving. JEEE Transactions Vehicular Technology, 72 (4):4308-4319) 2023.
Zhang, W., Fan, Z., He, J., and Gu, Q. Achieving constant regret in linear markov decision processes. In Advances in Neural Information Processing Systems 37, pp. 130694- 130738, 2024a.
Zhang, Z., Lee, J. D., Chen, Y., and Du S. Horizon-free regret for linear markov decision processes. In The 12th International Conference Learning Representations, 2024b.
Zhou, D. and Gu, Q. Computationally efficient horizon- free reinforcement learning for linear mixture mdps. In Advances in Neural Information Processing Systems 35, pp. 36337-36349, 2022.
Zhou, D., Gu, Q. and Szepesvari, C. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. Proceedings of 34th Conference on Learning Theory, pp. 3532-4576, 2021.

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
A. Proof of Theorem 1
Notation. denote UR... w. and Qi,,, as the parameters and the estimated Q-function at episode k, with wy representing
the policy k-th episode. The estimated value function Vi, n. is defined V A (x) Q (z, ( h)). For notational
simplicity, let Φk, (( (k.a). For any (2, E S x A [K] [ the surrogate Q-function for objective i [m]] is defined as
( = (z) + / Vi (1')) a)dz''
(9)
J
Equipped with Lemma and Lemma 4, we decompose the regret for objective i [m]] as
K
(K)
Σ
V
(
(10)
K
Σ
Vi (Dx,1)
Vi
(1 + Σ (
V (
Lemma 2 establishes that
H
H
1 - Vi (xxx,) S
Σ
2 2 (.,, + Σ
(11)
h=1
h=2
while Lemma 4 implies
( - 1 (Fx,1) S
Σ 10A((A) - 2- (x0,,))
(12)
Substituting (11) and (12) into (10), we obtain with probability at least 1 - 8, for any E [m]]
K
H
K
H
RK(K)
S
12A -Bk 22,
Sk
k=
k=1
k=1b=2
(13)
(A) :K -2 +
Sk.b
h= 8=1
km
h=
*+1 2-+1+ Ilok,,lll,, 2- The bound S < llgg(K)) (K) arises from the termination threshold1 /VK where tha.. {K [
in Step 7 of ALgorithm 1, as 2 log(K) < 1/VK.
By Lemma 13,
Σ ll /d/bn..l log(Ion,s)). TEPA.
Since [| > 2- for E sh this implies
2 --//nh, S 5 vhhn log((h)...))
Thus,
s 12 < Σ 60A .x v ddwn. log(/unnd) Σ (AA -8x
s
(14)
(00A((1) 3x log( VKKK
where the last inequality follows from the inequality and E Whall K.
12

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
For the term Ek=1 2x= Sk, in Eq. (13), observe that Çk.6 & Eloo (a,, (g,A) forms martingale difference
sequence with 1sk,ul I 2H for all (k, h). By the Azuma- nauma-noffdding inequality, with probability at least - 5, for any i [m]]].
K ΣΣ k=1A=2
Sh S / /KKH log(m/6).
(15)
Combining Eq. (14) and Eq. (15) in Eq. (13), we conclude with probability at least 20, for all i E [m]]
(K) - (A) Bx log(K)v dHIK (K)KKK + v 2K H3 log(m/8).
Substituting 3K -3H / (loo((2mKH/OO) this yields
R²(K) S (N())) ((HHK
completing the proof of Theorem
B. Proof of Proposition 1
For any objective i [m] and timestep h E [H]. the Bellman equation (1) implies:
(,, a) (z, a) + [P V + (z,, a)
= -z, a) + Bu (1x,)) [[))+)
(16)
= (r, a) + $f Jzes
Va Va (x (e")) a)dx'.
By the definition of a linear MOMDP, the reward and transition functions satisfy:
a (ø(2, a), O)), Pn(2'(x,
Substituting these expressions into Eq. (16) yields:
(x, (0(x,,), 0) [ Va Va,tt((a') (0(2,a) pa ( (z'))
(((xz, 0f [ Vi (nn) (x')dd"))
Jes
Letting w 0% + Swes Vi ahh (x (x))) finishes the proof of Proposition
C. Proof of Lemma 1
Following similar proof of Proposition we derive
(, a) (1( a) + a) (d(x, a), wk.n):
(17)
where wh,n =0 SSES Visti (x' dun Therefore, the equation Lemma 1 can be rewritten as
(0(x, a), wf (z (0(x, a), wf wh.))
(18)
Recalling the expression for wf, from Eq. (4), we obtain
w - U-1
Drnh Pran w
r=l
13

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
Eq. (3) indicates that f4 T.A
r
k (I,,, (,4+1) for all E [k]. Substituting this yields
Σ 6r.h (rha Qki (Ir,it1, ((nni)))rrti)))) UR.ARöiN
kk wkhh
k
Σ Drn (rha + Vihhzl(rratt) Unawinn
U
a ar,)) Substituting this into the above equation From Eq. (17), we observe that r (or whin gives
1kk,1
Σ TT (1r, wk [Px (PA (r,)) + V (x+1((TTN+1)) Uk uii. U
(19)
= U kib
Wke +
Onn (P - [I V -
where the final equality follows from Uk,b = Er= o( a, a0,)) ar,)) + I. Substituting Eq. (19) into Eq. (18), we decompose the bound into two terms: (ô(x, a), w - wkit)l (o(o,a), U whh ) +
6z (a,,a) a), k.h T=1
Ednn ΦT
(V (VeR+I(ETT, - V. V. (
(20)
A2
To bound A1 and A2, we introduce two lemmas:
Lemma 5. Let W., denote the corresponding weights satisfying Qi (2. a) = (0(x, a), whnd for all (x,a,h) E eSxA [H] and i [m]. Then, [| I 211 2d.
Lemma 6. With probability at least 8, for any h1, E [K] x [H] and i E [m]]
Σ Orch (V (F [Px V K. P (r.6))
d log
22mkH
8
Us.n
Applying Lemma 5, we bound A1 as
A = (0(z, a), U w < 16(2,, all [| Ilv.,, S a)l(z, || s 2HVd [1,(zz, a)l (21)
For A2, Lemma 6 and the Cauchy-Schward inequality imply
A₂ v |1 a) allurn
EΦnn Rin (V (VeN41(07T [PA V. (
Un.
(22)
< Hy dog 2mkHl
1|0(1, all
Taking Eq. (21) and Eq. (22) into Eq. (20), we obtain
(2mkH) )) (10(0, a)llur.s
Kô(x, a), a). w (x,
2H 2H + H
d 8
which concludes the proof of Lemma since By =3H
3H / dlog (2mkH)
14

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
D. Proof of Lemma 2
To bound the term V2 ( Vi Fksh (Z in Lemma 2, we begin by decomposing as follows:
(1 (FA.N) = (FR,N) - ( Th ( h)) + Qi. (FKK,, TA ( h)) V a (FRR,))
(23)
Analysis of B3: By Lemma 1, with probability at least for any (z, h) E [K] x [H] and i [m]] we have (6(z, (2, h)), w))n)) - (n (1 b)) - Bxllo(2, (z M)
Since (z) Oh (2, hi) (0(2, Th (2, h2, 20 it follows that
(x) (I, (z (TEE s Bxllo(z, mT(2, (1)
(24)
Let sx,a (x) denotes the stage at which Algorithm I selects the action for state J S. From Step 10 of Algorithm 1, we have 2 -m,a(()) $ 110(2, (z, $2 2=*,,a(x)+1 Substituting this into Eq. (24) yields
(x) (1,, s 2 =
Thus, term B3 satisfies
B3 (., (a S 28x - (L,A))
(25)
Analysis of B₁: Using the definition of (+,(( in Eq. (9) and the Bellman equation, we observe:
(x, = ri (x. [ Vhatu (n')Pa((a (1
Jaes
V H. (x) Q2 h)), Qu, r)(z,a)+ f V Vi (x')) a))dz''''
JaYes
This implies B4 can be expressed as
- Vi (Ix - Z (Vhntzlo')- V (2')) -V Pn (2
B4 =
(2 h()dd. (26)
Combining results:
Substituting (25) and (26) into (23) gives
Vi (ZK,)) - V (Tr, S 23x ( +
(V (Vkntil2²) Vi V (20
( (11) Tu ( 1
EES
Recalling the notation o/,n = (FT.N) V Vic (xTe,)) and Gh -kk -E(0k bork from Lemma 2, we obtain
(Z2, V2l (IK,,)) S 223 2 (ummmn)))) Sh + Sha
H1
H
Σ
28 2 S (a)w)) + Σ S
M=h
W=R++
where the second inequality follows by simple inductive argument. The proof of Lemma 2 is finished.
E. Proof of Lemma 3
We prove this lemma by mathematical induction on the objective index E [m]] to prove this lemma. First, we note that in Algorithm 2, the confidence terms of all actions are bounded by C. By Lemma 1, for any (x, a) S x A, and objective i [m], we have
(2, Qi, a)l s BE C.
(27)
15

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
Base i 1: The candidate action set A² A, and the refined set Ag is constructed
A - {a Ag (Zr, (k,,) - Q ( a) s 2, C}.
(28)
Since (I, h) E As and 0 E A = A.. Eq. (27) implies
(1, (x, h)) + Bk C Q (z,, T (x, 2 (x, ok 2 (z, ok.n) 8k C,
where the inequality 1,,, (1. n. (x, h)) Qh (z. m follows from Assumption 1 and the optimality of a (z. h).
Substituting these bounds into Eq. (28), we conclude n. (x, h) E A!
For any a E AA,, applying the confidence interval Eq. (27) and the refined operation in Eq. (28) gives
(k, a) 2 Qh,, (2, a) - 3k C Q% k2, 3,3 C.
Since / = argmax Q (I. a) and (x. (2,1) h) E Ao we further derive
(x,( 2 (= , 38s C 2 Q T (x, 33x C 2 (HE,, -83 C.
Thus, Q/ (TR,n) T. (x) Q (z, a) s 43p- C. Inductive step: Assume for any
that:
(z, h) E A and
(29)
O (z. T. (z) - Ph (2, a) S (A) Bx. C,
then we prove the following statements hold for the objective ::
T= h) E AS, and
Chin (T, h)) - (r, a) S (2) Bp C.
By, Assumption 1, the trade-off among different objectives are bounded by X, which implies that (Q) (2, (xx (2, JE(i-1]
Qu,n an ( n. (x, s A max
Substituting Eq. (29) into the right-hand side yields
Q (z. a (I, T (x, S A- --AA--1 4A) Bk C.
(30)
Applying the confidence intervals from Eq. (27) to bound Q (x, w) and Qh (x, T. (ar, h)), we rewrite Eq. (30) as
Qh ok, Qu, T. h2) 23: C+ 41 (A) Bx C.
(31)
Given Ai(A) 1 + A ... + x 1-1 for i E [m] and Step 4 of Algorithm 2, which constructs,
A = {a E A 12 (Tx, (h (T S (2 + 4 ... + + Bx -C
Eq. (31) ensures nx (z, h) E As.
Since a argmax Q (Fr,, a) and (, h) As-1, the construction of implies
( T. (x, h)) Q% (x a) s (TK, kk ()) (2 5 +1x-1)- BBx C. (32)
By the confidence interval in Eq. (27), we have
(K(,,,, a) S 8x C. Ch (1, A)) & Q (T; + Be C, (,(o,,,)))
Substituting this into Eq. (32) yields
(ELA, h)) - (I(K,,)))) 44(1 + +
This completes the proof of Lemma
16

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
F. Proof of Lemma 4
Recall definition of Q (+.)) in Eq. (9) and Bellman equation:
(x, (x, / Vi (x'))) ())),,
J'ES
V n.h (z) Q ( (1z, (I, b)), (z,0) a)( [
V V (2 (ax)) a), Jo
From these, we can write nh (z) as
(V (Va.uti(a")) Vinni(t')) Pu(x' a (x.x))))rr ( S Jes
(x) Tu (x) +
Lemma 3 establishes the bound
Th, TE S (AA( 3x 2-
where nH (Z h) E As,,)) and (z,,) is constructed by setting = 2 ( in the LAE procedure. Substituting this into the expression for Vi (x), we obtain
V (ITK,N) (EA H)) 8A²(A) Br. 2-8ha(zrnn)
$ Swes
(V (VEneti(e")) V (()))((()) (ol,) (a (ont h))dd'
(33)
Lemma provides the confidence interval
(TR,, Th (K h)) (FE,, Ta (TK, h)) 3x (K ma( um) < (EEN, TH (= h)) + 23, 2 (mnka)))
V. (F2,N + 2 2-
Substituting this inequality into (33) yields
(#v..) & VE (IK,N) + 2Bx 2- + 8A((A) BB 2 malcnn)
max / (Ve.,oti(a)) - Ven+s(1')) (2'lson a)da'. aEA
XEES
Applying induction over h, we have
"
Vi n. (ZR,))
V (mKN)) S
Σ
10A((A) 3r 2-
h'=h
This completes the proof of Lemma 4.
G. Proof of Theorem 2
Notation. Let Uk,,, w and Qi denote the parameters and the estimated Q-function for episode k, with TH representing
the policy k-th episode. The estimated value function Vi is defined as V (x) Q (z. (xr h)). For notational simplicity, we define de ((T n, (.. For any (I, a, k h) E ESxAxx [K] x [). the surrogate Q-function for objective i [m]] is given by
(Lal,,)==r((e. + J (2a+)(2))a a)dz'.
(34)
We now present the following proposition and lemmas, which extend key tools used in the proof of Theorem 1. Specifically, Proposition 3 extends Proposition 3, while Lemmas 7, 8, and 10 extend Lemmas 2, 3, and respectively.
17

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
Proposition 3. In an e-approximate linear MOMDP, for any objective [m]] and any k [K], there exist weights (hElA)) such that for any (2t, a, h) E 8 A x [ we have
12, a) (0(z, a), w S 2He.
Proof. From the definition of Q (2,, a) in Eq. (34), for all E [m]] and E [M]
Qi, a) r,, a) + (P = (x, a) + B (e
(35)
= (x, + V V (x)) a)dz'.
X'ES
By the definition of e-approximate linear MOMDP, (2, a) (ő(#, a), 0,01 e, - (d(o, un se.
Taking these bounds into Eq. (35), derive:
(xn( a) - (0(z, a), 0/) +e+ / Vinnz(e") (o(x, a), (n(e))) + He
S (ő(1, a). 0f f Z'ES
Vhn4z(z4) (zn))))))) + 2He.
A symmetric argument provides the lower bound:
[ (e))) - -HE S (E,
(ó(z, 0f
Thus, setting w = 0% + JeES vi Vh (x')d(u((z)) completes the proof of Proposition 3.
3H Lemma 7. Let Bxx- -3H v dlog (2mkH)) +2H Had With probability least for all (x, a, k. E SxAx [K] H and i E [m]. we have
(0(x, a), w
(z, a) S (all((x,))lll,, + 2Hc
Proof. By Proposition 3, we derive the initial bound:
16b(, a), w ( a)l S (((r, a), wn unkn)) + 2Hc
(36)
From the definition of w h. in Eq. (4), we express the difference:
W whe Uni Σ Drn P.. whi
Using the surrogate reward relation in Eq. (3), where Pr., = -rtm + Vi 1 ar,+1) for all T E [k], we expand:
Σ Hr.h (rhn Qh (1r,ht1 Un.
kkk when
U
Σ Hr.h (Fen + (RnTI((aaHH)) Unsttkn
- k,h
Let Pa (-lar, = (0(x, a), m.)())). Recalling the proof of Proposition 3 that wh = 0% + Jwes Vh (x' ( (dd)dnn we restructure the above equation to
h wk.h wh. = -U wh. + U Σ Sr.h (1i. - (6r,,, 0%) + [(PA ta (r
(37)
+ U-1
Eonn Hrir (VGA4)(E7,,41)) [P PRAk
rm/
18

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
Taking the Eq. (37) into Eq. (36), we have
(0(2, a), w - w
((( o), U wkhn + ((2, U URbh E 0Tu (V (VintI(eTAn)))- - [IP V k 1 ar.h)
A1
(38)
A2
k o(), U E prh (re, (0r, 0%) + (IP - Pn) k (I arth))
Ag
Term A1 and A2 are bounded by the same methodology as Lemma 1. For Ag, noting that Irt, (dr,,, 0%21 S and
|P - Pxlla e, we can bound A3 as
As $ 2He
ल(z, a) T PrA
(39)
22H
pl a) To T Uk
rhh U 0r,
s 2Hevkd | allue,.
Integrating Eqs. (21), Eq. (22), and Eq. (39) into Eq. (38) produces:
22kkll
(é(z, wk.n) (z, <
3H d
+ 2222He kd 1)(x,, + 2Hc,
8
which concludes the proof of Lemma
The proofs of the following three lemmas follow analogous arguments their counterparts in Lemmas 2, and 4, requiring only the replacement of Bxl10(z, a)l, with 8& (1,(1, l)l,u,, + 2He. We therefore omit their full proofs for brevity.
Lemma 8. Let ok,n V E. (x), V V (2),)) and Sk.n 62 Bloh (k og With probability at least 1 8, for any (ks, h) [K] x [ and i (m], we have
H
(KL - V (I
<
Σ 28k 2 ( + =/
Σ
Sk + 2H - h 1)e,
W=++1
where Sk. (F denotes the stage at which LLRL selects the action for state Kk,h!
Lemma 9. For Algorithm if n. (x, As then with probability at least for any objective E [m]] and action E A have
<_ h) E A and
(I, h)) Qi a) S 441(2) Bk (C+ (C+22 +2Hc.
Lemma 10. With probability at least 1 - 8, for all (z, a, k E S ES Ax [K] x [H] and i E [m], we have
Vi I (T Vi (x S Σ 10A((A) - Bxx (= 20) (H- - h 1)He
M=h
where St. (xx,N) denotes the stage at which L.RL selects the action for state TK,K'
19

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
Proof of Theorem 2: Using Lemma 8 and Lemma 10, decompose the regret for each objective i [mm]]
K Σ
R$ (K)
V
(Ix,1)
Vite1 (ITk,1)
N.,
K
K
Vi
n..1 V
(3x,1)
(FK,) +
Vi (xx,1)
The (FR,1)
Following an analogous procedure to Theorem 1, we derive:
(K) < (0) Bx log KHHHR + 22KH3 log(m/8) + 22 He...
Substituting 3K = 3H /dlog (2mKH/6) + 2222HHHKK Kd yields:
R((K) S 5 (N(2)) ((HH-+aaH(Ke)))
This completes the proof of Theorem
H. Proof of Lemma 5
By the Bellman equation in Eq. (1), for any (z,,,k,,) E Ax [K] [H] and i E [m], we have
(k (() [Px V k,
Applying reasoning analogous to Proposition 1, we derive
k 0% + [ (i)+il=)eer (d')dun((x)
Ja'eS
Given the bounded reward rf, (1r, a) E [0, 1). the value function satisfies Vi Ve (x') S H for any state x'. Therefore,
||0m|| s vd, and |/f (E SHVd.
which finishes the proof.
I. Proof of Lemma 6
According to Lemma 11, for any fixed [m] and [H], with probability least 1 8, the following incquality holds for all & 2 1:
dde((U&)
Σ
Φr ((TN41( - [IP 1k,,-Il(r,,
$ 2H log
Uk.
Lemma 12 simplifies this bound via the inequality det, yielding:
Φr Vid (1,,14)) - [Px -o (r.h
2H log
v (1 + k/djdd
$ dH² log
1
8
Uk.h
Applying a union bound over E [m]] and h E [H] completes the proof.
20

---

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards
J. Auxiliary Lemmas
Lemma 1I. (Abbasi-yadkori al., 2011, Theorem 1) Let {+ be a real-valued stochastic process adapted to filtration (Fils where Ft-1 be zero-mean and o-subGaussian, i.e..
12 Bic[F-11]= = 0, and AA R. ( 6220-/2
Let {d:].-n S Rd be stochastic process where d, E Ft-1- Assume Un is d d positive definite matrix, and let U, Uo + -==1 0.0.. Then for any 8 >> O, with probability at least 6, for all t 0:
Σ
CCC
I 20 2o2
Lemma 12. (Abbasi-yadkori et al., 2011, Lemma 10) Let Φ1, 02.......a de E IRd satisfy lloele & L for any I 8 S t.
Define U. = + Ei=1 2 for some À > 0. Then:
det(U,) S (A (++ /d)".
Lemma 13. (Chu et al,, 2011, Lemma 3) Let Φ1 .2...., Φ2 E Rd and U, = I E. 6.07 Then:
l S 55 logb.
21


Reviews:
[{"review_id": "nh5xzLsAto", "reviewer": "Reviewer_a9vt", "summary": "This paper provides an algorithm for the multi-agent reinforcement learning (MORL) setting and regret bounds. Notably the regret bounds given match the single-objective setting up to the leading order term.\n\n## update after rebuttal\n\nI found the work to be making a substantial contribution.  I am glad to see the authors considering the removal of contribution 4 and to tone down the primacy claims.  I think the paper makes a significant contribution without over-claiming or exaggerating.  I think this paper would make a nice contribution to the conference.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the constructive feedback and have carefully considered the raised concerns. Our point-by-point responses follow below.\n\n---\n\n*Q1. **Claims And Evidence:** Contributions 1-3 are well supported and insightful. However, the finite-horizon assumption shouldn't be glossed over $\\cdots$.*\n\nWe appreciate the reviewer’s positive feedback on Contributions 1-3 and their helpful suggestion. We agree that introducing the finite-horizon assumption earlier in the paper will better clarify our work’s scope. In the revised version, we will highlight this in the Introduction.\n\n---\n\n*Q2. **Claims And Evidence:** Contribution 4 seems disingenuous $\\cdots$ Isn't that just a restricted class of MDPs like the authors' restriction?*\n\n We agree that calling our work the \"first theoretical regret bound for MORL\" was inaccurate, especially since prior work on lexicographic bandits  (e.g., Huyuk et al., 2019), which is a special case of MDPs with $H=1$.  We will remove Contribution 4 and instead integrate the discussion of the $\\sqrt{K}$ regret term into our other contributions. Meanwhile, we will add comparisons to bandit-based MORL frameworks (Huyuk et al., 2019) in the related work section.\n\n---\n\n*Q3. **Methods And Evaluation Criteria:** Why is Xu (2020) a row in the table $\\cdots$ Even Skalse (2022) seems odd as it makes no linear MDP assumptions.*\n\nTo the best of our knowledge, no prior work specifically tackles multi-objective linear MDPs, so we refer to general multi-objective MDP (MOMDP) frameworks. Xu et al. (2020) focuses on finding Pareto-optimal frontiers in MOMDPs under Pareto ordering. Skalse et al. (2022) studies lexicographic ordering in MOMDPs without assuming linearity. We will update the table by removing Xu et al. (2020) and Skalse et al. (2022), retaining only works directly relevant to **linear MDPs** to avoid confusion. \n\n---\n\n*Q4. **Relation To Broader Scientific Literature:**  Lexicographic ordering in RL goes back at least to Gabor et al. (1998), which (to be fair) is discussed eventually on page 3, but long after the introduction seems to disregard this history.*\n\nWe thank the reviewer for their helpful comment on the history of lexicographic ordering in RL. We will restructure the introduction to foreground the seminal work of Gabor et al. (1998) as the conceptual origin of lexicographic RL so as to strengthen the paper’s scholarly context.\n\n---\n\n*Q5. **Other Strengths And Weaknesses:** Some additional discussion of where assumption 1 comes from would be nice.*\n\nAssumption 1 addresses the Optimal Action Preservation Dilemma (**Section 6**). In Example 1, there are three Q-value vectors: $[5,5,5], [1,5,5]$ and $[4,10,1]$ for actions $a_1, a_2$ and $a_3$, where $\\lambda=\\frac{10-5}{5-1}=5$. $a_1$ is lexicographically optimal. When eliminating actions based on the first objective, $a_2$ is eliminated since $1$ is far from $5$, but $a_3$ is kept as $4$ is close to $5$, leaving $\\\\{a_1,a_3\\\\}$. Next, elimination considers the second objective. Although $10$ (from $a_3$) is much bigger than $5$ (from $a_1$), the confidence term $\\beta_k\\cdot C$ is scaled by $2+4\\lambda$ (Step 4 of Algorithm 2), ensuring $a_1$ stays in $A_s^2$.\n\n---\n\n*Q6. **Other Strengths And Weaknesses:** Might it actually allow the objective to satisfy the Continuity axiom of von Neumann and Morganstern?*\n\nThe continuity axiom says that for three options where $A \\succ B \\succ C$ , some mix of $A$ and $C$ should be equally good as $B$. This means no outcome is infinitely better or worse than another. But in lexicographic optimization, higher-priority goals (like safety) are infinitely more important than lower ones (like cost). Thus, the continuity axiom may not apply, since no trade-off can make such different-priority goals equivalent.  \n\n---\n\n*Q7. **Other Strengths And Weaknesses:** I think the introduction of linear RL in Section 2 should include some discussion of what \"linearity in both the reward function and transition probabilities\" means, and a definition of “misspecified”.*\n\nWe will revise Section 2 to clarify the concepts of \"linearity in both the reward function and transition probabilities\" and discuss \"misspecified.\" Specifically, we will explain that in linear RL the reward function is $r_h(x,a) = \\phi(x,a)^\\top \\theta_h$, where $\\phi(s,a)$ is a known feature vector and $\\theta_h$ is unknown. The transition probabilities follow $\\mathbb{P}_h(x'|x,a)=\\phi(x,a)^\\top \\mu_h(x')$, where $\\mu_h(x')$ is an unknown measure. Additionally, we will clarify that \"misspecified\" refers to settings where the true environment deviates from the assumed linear class (e.g., due to approximation errors in rewards or transitions).\n\n---\n\n*Q8. **Other Comments Or Suggestions.***\n\nWe sincerely appreciate the reviewer’s detailed feedback, which has significantly contributed to improving the quality of our paper. All suggested revisions have been carefully considered and will be incorporated into the final version of the paper.", "claims_and_evidence": "The paper explores how techniques in the finite horizon linear MDP setting can be applied to the space of the lexicographically ordered objectives. The paper claims four contributions: A MORL algorithm, a regret bound for the algorithm, a regret bound for the algorithm in the misspecified MORL setting, and a claim of being the first MORL algorithm with a regret bound. \n\nContributions 1-3 are well supported and insightful.   However, the finite-horizon assumption shouldn't be glossed over as just part of the formalization of the policy 3 pages in, but should be stated much earlier in regards to contextualizing the contributions.\n\nContribution 4 seems disingenuous. Since the authors’ work is limited to linear MDPs, I don't know what it means to be the \"first theoretical regret bound for MORL\". In a pedantic sense, it's not true: consider MDPs with a single state and action, all algorithms have zero regret, so there’s a theoretical bound. What about lexicographic ordering in bandits (e.g., Huyuk et al., 2019; Xu & Klabjan, 2023; Xue et al., 2024; all just from a cursory Google search)? Isn't that just a restricted class of MDPs like the authors' restriction? I would strongly recommend dropping this bullet point, and just roll the observation of the sqrt(K) term into one of the other stated contributions (which is the main defensible statement in the contribution).", "methods_and_evaluation_criteria": "Yes.  However this is marred by what seems like overclaiming and exaggeration of the results.\n\nFor example, \"All of the aforementioned MORL studies primarily rely on empirical evaluations, with limited attention given to theoretical guarantees. This absence of formal analysis has impeded the development of principled algorithms with provable performance bounds.\" This feels needlessly pejorative. It is true that these past works did not report a regret bound on linear MDPs, but many did some form of formal analysis. Not providing regret bounds does not mean they are not theoretically grounded. For example, Gabor et al. (1998) provided convergence results. How is that not a theoretical guarantee?  The second statement is nonsensical and more pejorative; essentially it’s saying that the lack of algorithms with provable performance bounds has impeded the development of algorithms with provable performance bounds.\n\nTable 1 I find to also be disingenuous. Why is Xu (2020) a row in the table when it introduced an algorithm for finding the Pareto-optimal frontier, which is an entirely different problem? Even Skalse (2022) seems odd as it makes no linear MDP assumptions. These rows seem to be needlessly propping up the authors' work by critiquing others that had different goals.\n\nThe paper makes a valuable contribution without this need to oversell their own results and minimize the results of others.  What seems a more accurate description of what's going on is that the authors are using recent techniques for the only-recently explored space of linear MDPs and establishing how they extend into the space of the lexicographic ordering objective.  This is interesting research and deserving to be disseminated without any need to exaggerate the contribution.", "theoretical_claims": "I mostly followed the definition of the algorithm and the approach all seems plausible, but I did not verify any of the proofs (all in the supplementary material).", "experimental_designs_or_analyses": "NA.", "relation_to_broader_scientific_literature": "This is one of the weaknesses of the paper. \n\nAccording to the introduction, MORL started in 2013, but no interesting advance happened until this decade. \n\nYet the cited 2013 paper is, in fact, a survey with over a hundred citations of work in this area going back decades. Lexicographic ordering in RL goes back at least to Gabor et al. (1998), which (to be fair) is discussed eventually on page 3, but long after the introduction seems to disregard this history.  \n\nI would say this is doing a poor job of placing the contributions in the broader scientific literature.", "essential_references_not_discussed": "I don't think there's an essential reference missing, but I hope the authors consider being more careful in discussing the historical line of work.", "other_strengths_and_weaknesses": "I really like section 6. I find it helpful to understand what's going on. However, I feel like Section 6 is out of order. Shouldn't this come before Section 4, as it motivates the underlying techniques employed in the algorithm? Or at least 6.1 should come first?\n\nSome additional discussion of where  assumption 1 comes from would be nice. This assumption seems super restrictive! Might it actually allow the objective to satisfy the Continuity axiom of von Neumann and Morganstern? This would then admit a single scalar reward signal that would allow maximizing its expectation reducing the entire problem to traditional RL. For finite states and actions, there always exists such a lambda, and so this assumption just creates a constant to use in the bound. However, what if the action space allows for continuous probabilities such as admitting stochastic policies, this seems to rule out certain discontinuities that would naturally arise with lexicographic orderings and are what makes them challenging to begin with (e.g., see Gabor et al., 1998; Bowling et al., 2023).\n\nI think the introduction of linear RL in Section 2 should include some discussion of what \"linearity in both the reward function and transition probabilities\" means, and a definition of “misspecified”. The current related work section has no real value. It's merely a list of recent papers and the resulting regret bound. The form of the problem addressed (e.g., exactly what is linear and how) would seem way more important than the regret bound form itself. After all, your main deviation is in the form of the problem to explore a lexicographic objective.", "other_comments_or_suggestions": "* Line 189: \"while still maintaining the feasibility of optimizing\": the word choice of \"feasibility\" seems odd here. Maybe a better wording would be \"while still allowing some optimization of\".\n* Line 301: \"is a \\epsilon-approximate\" shouldn't it be \"is an \\epsilon-approximate\"?\n* Line 371: \"Next, the agent proceeds to eliminate arms based on the second objective.\" First time the word \"arms\" is used in the paper. I understand, but this is adding confusion.\n* Line 373: \"which is disappointing because a_3 is awful for the third objective.\" Isn't it disappointing because a_3 is not the optimal action (since 4 < 5)?\n* The term \"the lexicographically optimal policy...\" is used in several places.  The policy is likely not unique, so maybe this should say \"A lexicographically optimal policy...\"\n* Why is lexicographic ordering defined as \"dominates\"? Dominance I would expect to be reserved for a partial order, not the total order of lexicographic ordering.\n* I believe there are typos in the definitions of the action value functions. Throughout the paper, x is used to denote state however in the value function definitions, reward is written as a function of s.\n* There is also a typo in Assumption 1 that is critical to fix. I believe the superscript of the reward terms should be a j. As stated, the inequality does not make sense.\n* Brackets around the transition-kernel value-function product before/in Equation (1) is confusing given the meaning of brackets as a set.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gx2nTc37ue", "reviewer": "Reviewer_8VYt", "summary": "This paper studies linear Markov Decision Processes (where the transition function and reward function can be expressed using a known linear kernel and two unknown vectors). The paper introduces a novel algorithm for finding policies according to a lexicographic objective with bounded regret. While prior work has studied multi-objective optimisation in linear MDPs and lexicographic objectives in finite MDPs, no prior work has considered lexicographic objectives in linear lexicographic MDPs (which generalise finite MDPs). The paper also proves a PAC regret bound (in terms of each objective separately) for their algorithm, which may be the first regret bound for lexicographic MDPs. This bound assumes unknown (& linear) transition dynamics and reward. The paper also bounds regret when an MDP can be approximately expressed as a linear MDP.\n\n## Update after rebuttal\nI'm grateful to the authors for including additional information about, e.g., time/space complexity. I think this information significantly improves the paper. Given the complexity of the algorithms presented and the absence of real implementation, I don't feel I can increase my score to a 5, although I still believe the paper should be accepted.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thorough and constructive feedback. We have carefully considered each weaknees and present our responses below, which will be incorporated into the revised paper.\n\n---\n\n*W1. To aid with comparison to existing work investigating lexicographic objectives (not-necessarily-linear) MDPs (such as Skalse et al. 2022), a more explicit discussion of the relationship between MDPs and linear MDPs would be beneficial.*\n\nThank you for highlighting this important connection. We have clarified the relationship between general and linear MDPs as follows: \n\n1. Any finite MDP with state space $\\mathcal{S}$ and action space  $\\mathcal{A}$ can always be represented as a linear MDP by encoding each state-action pair $(x, a)$ as a one-hot feature vector in $\\mathbb{R}^d$, where $d=|\\mathcal{S}| \\times |\\mathcal{A}|$. The transition kernel $\\mathbb{P}(x'\\mid x, a)$ and reward function $r(x, a)$ can be expressed as inner products between the feature vector of $(x, a)$ and learnable parameters.\n2. While linear MDPs impose structure that enables tractable theoretical analysis (e.g., regret bounds in Jin et al. 2020), general MDPs with lexicographic objectives (as in Skalse et al. 2022) may not always adhere to this linearity. Our results for linear MDPs directly apply to finite MDPs, but lexicographic objectives in non-linear MDPs may require different algorithms.\n\n---\n\n*W2. The space and time complexity of Algorithm 1 is not discussed $\\cdots$ An explicit readers to understand any (potential) limitations to application.*\n\n\nWe thank the reviewer for the constructive feedback. Below, we provide a detailed complexity analysis of Algorithm 1 and discuss its limitations:\n\n1. Step 7: Computational complexity is $O(d^2|\\mathcal{A}|)$, while memory complexity is $O(|\\mathcal{S}||\\mathcal{A}|)$ for storing state-action pairs.\n\n2. Step 8: LAE requires $O(md|\\mathcal{A}|)$ computations and $O(|\\mathcal{S}||\\mathcal{A}|)$ memory.\n\n3. Step 20: Both computational and memory complexity are $O(d^2)$, as $U_h$ can be updated incrementally.\n\n4. Step 21: Computational complexity is $O(mk)$ for updating $m \\cdot k$ values.  Memory complexity is $O(mk+md)$ to store $\\\\{\\hat{r}\\_{\\tau,h}^i, (x\\_{\\tau,h+1}, a\\_{\\tau,h+1})\\\\}\\_{\\tau\\in[k]}^{i\\in[m]}$ and $\\\\{\\hat{w}\\_h^i\\\\}\\_{i\\in[m]}$.\n\n5. Step 22: Computational complexity is $O(mkd+md^2)$, dominated by inverting $U_h$ ($O(d^2)$) and computing $m$ linear regressions ($O(mkd+md^2)$). Memory complexity is $O(md)$ for storing weight vectors $\\\\{\\hat{w}\\_h^i\\\\}\\_{i\\in[m]}$.\n\n6. Step 23: No additional resources are required, as Q-values can be updated directly from retained $\\{\\hat{w}_h^i\\}_{i\\in[m]}$.\n\nSumming across all $H$ MDP layers:\n\n- The computational complexity of is $O(Hmd|\\mathcal{A}|+Hd^2|\\mathcal{A}|+Hmkd+Hmd^2)$ .\n- The memory is $O(Hd^2+Hmk+Hmd+|\\mathcal{S}||\\mathcal{A}|)$. \n\nSumming over $K$ rounds:\n\n- The **total computational complexity** is $O(KHd|\\mathcal{A}|(m+d)+K^2Hmd+KHmd^2)$ .\n- The memory of our algorithm is $O(Hd^2+HmK+Hmd+|\\mathcal{S}||\\mathcal{A}|)$.\n\nThe $O(K^2)$ computational complexity and $O(K)$ memory are much more expensive than standard bandit algorithms, which typically achieve $O(K)$ computation and $O(1)$ memory. However, our approach remains competitive with existing methods in single-objective MDPs (Jin et al. 2020; Zanette et al. 2020; He et al. 2023). In the revised paper, we will explicitly discuss the computational and memory complexities of our method to clarify its practical applicability.\n\n---\n\n*W3. Compounding on the above, the paper does not implement the proposed algorithm and empirically demonstrate how well it performs in comparison to prior literature (which do conduct empirical analysis).*\n\nThank you for raising this issue. The absence of empirical validation in our work aligns with the foundational single-objective linear MDP studies (Jin et al. 2020; Zanette et al. 2020; He et al. 2023), which similarly omit experiments due to challenges in constructing valid linear MDP benchmarks (e.g., enforcing low-rank dynamics and linear payoff structures). We plan to address this limitation in two phases: i) Synthetic experiments will be added to illustrate key theoretical properties. ii) Comprehensive empirical comparisons against heuristic baselines and ablations will be conducted in follow-up work. We appreciate your feedback and welcome suggestions for specific experimental protocols or baseline implementations.\n\n---\n\n*W4. **Other Comments Or Suggestions:** In the statement of theorems 1 and 2, it is not immediately clear whether the events that each of the m objective regrets satisfy the bound (with probability 1-2\\delta) are co-occurring.*\n\nMany thanks for your detailed reviews. The events that each of the $m$ objective regret satisfy the bound are co-occuring. We have polished the paper to avoid typos and improve the clarity in the revised version.", "claims_and_evidence": "All claims in the submission are made as formal statements and are supported by proofs in the appendix (see below).", "methods_and_evaluation_criteria": "The only method, Algorithm 1, is justified in terms only of the regret bound. The regret bound is an appropriate criterion if the work is viewed as foundational and is meant to lead to future algorithms that could be applied. \nThe paper does not state a specific application (a few potential applications of RL in general are mentioned); however, evaluation of the algorithm’s suitability for even toy applications is not given.  For example, there is no analysis of the space or time complexity of the algorithm nor empirical application to a toy lexicographic linear MDP (see weaknesses below).", "theoretical_claims": "I reviewed the major results presented in the appendix, and, to the best of my understanding, there are no problems with the correctness of the proofs.", "experimental_designs_or_analyses": "There are no empirical experiments in this paper.", "relation_to_broader_scientific_literature": "The results are well-connected to regret-bounded algorithms in single-objective RL. As far as I know, this is the first result bounding the regret of an algorithm for lexicographic RL. \n\nA number of other papers propose lexicographic RL algorithms without regret bounds. Therefore, a full understanding of the key contributions of this paper may require an empirical comparison.", "essential_references_not_discussed": "Although there are a number of other papers exploring lexicographic multi-objective RL (e.g., https://arxiv.org/abs/2408.13493), I don’t know of any other results that attempt to prove regret bounds.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is mostly presented with excellent clarity despite the technicality of its content. \n2. The regret bound is, to the best of my knowledge, novel and requires no additional assumptions when compared with prior work (see weakness 1).\n\nWeaknesses:\n1. To aid with comparison to existing work investigating lexicographic objectives (not-necessarily-linear) MDPs (such as Skalse et al. 2022), a more explicit discussion of the relationship between MDPs and linear MDPs would be beneficial. For example, it could be clearly stated that finite MDPs can always be represented as linear MDPs with d=|S|\\times|A|, as is shown in Example 2.1 of Jin et al. 2020.\n2. The space and time complexity of Algorithm 1 is not discussed. I am uncertain, but it is possible that the complexity of this algorithm would make it intractable for real applications. For example, computing lines 20-23 of Algorithm 1 appears to require storing H * K state-action pairs in memory and then computing a least-squares estimate over K values. Although this could be competitive with similar algorithms with regret bounds (in the single-objective case), it may not be scalable to real environments. An explicit readers to understand any (potential) limitations to application.\n3. Compounding on the above, the paper does not implement the proposed algorithm and empirically demonstrate how well it performs in comparison to prior literature (which do conduct empirical analysis).", "other_comments_or_suggestions": "I found very few typos in the paper. Example 1 says “arm” (which is not used elsewhere) instead of “action”, but in some contexts, these words are synonymous, so this did not impede clarity.\n\nIn the statement of theorems 1 and 2, it is not immediately clear whether the events that each of the m objective regrets satisfy the bound (with probability 1-2\\delta) are co-occurring.", "questions_for_authors": "No further questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rOrtdQ5SjM", "reviewer": "Reviewer_6izD", "summary": "This paper studies multi-objective RL (MORL) with lexicographic rewards in linear MDPs, where rewards comprise hierarchically ordered objectives. A key challenge in MORL is the failure of Bellman optimality. They propose the LLRL algorithm and establish the first regret bound for MORL under a certain assumption (Assumption 1).", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your constructive reviews. We have carefully considered your concerns and our responses are provided as follows.\n\n---\n\n*Q1. What is the definition of $a_2$ lexicographically dominates $a_1$ in Assumption 1? Does it mean the reward vector $[r_h^1(x, a_2),\\cdots,r_h^m(x, a_2)]$ lexicographically dominates vector $[r_h^1(x, a_1),\\cdots,r_h^m(x, a_1)]$?*\n\nYes, the definition aligns with your interpretation: $a_2$ lexicographically dominates $a_1$ if and only if the reward vector $[r_h^1(x, a_2),\\cdots,r_h^m(x, a_2)]$ lexicographically dominates vector $[r_h^1(x, a_1),\\cdots,r_h^m(x, a_1)]$.\n\n---\n\n*Q2. Following Q1, I have one question regarding the proof of Lemma 3 in Appendix E. Specifically, why would Assumption 1 result in the argument in lines 797-800?*\n\nWe appreciate this critical observation. Upon re-examination, we recognize that Assumption 1 alone does not suffice to support the argument in lines 797-800. This oversight has led us to propose a revised assumption, detailed below.\n\n**Key Revision Rationale:** Initially, we presumed that if individual rewards satisfied Assumption 1 (lexicographic dominance on immediate rewards), their weighted aggregation $\\bar{Q}\\_{k,h}^i$ would inherently preserve this property. However, this reasoning neglected the temporal dynamics of MDPs: actions at step $h$ influence not only immediate rewards but also future state distributions (via $\\mathbb{P}\\_h$). The original assumption only bounded trade-offs in immediate rewards ($r\\_h^i$), failing to account for long-term value interactions in $\\bar{Q}\\_{k,h}^i$.\n\n**Revised Assumption:** Let $\\tilde{Q}^i\\_h(x,a)=r\\_{h}^i(x,a)+\\[\\mathbb{P}\\_h \\tilde{V}^i\\_{h+1}\\](x,a)$ for any $i\\in[m]$ and $(x,a,h)\\in S\\times A\\times [H]$. Let $\\pi_*(x,h)$ denote the action chosen by the lexicographically optimal policy at $(x,h)$.  We assume the trade-off among objectives is governed by $\\lambda\\geq0$, such that for all $h\\in[H]$ and $i\\in[m]$,\n$$\n\\tilde{Q}^i\\_{h}(x,a)-\\tilde{Q}^i\\_{h}(x,\\pi_*(x,h))\\leq \\lambda \\cdot \\max\\_{j\\in[i-1]}\\left\\\\{\\tilde{Q}^i\\_{h}(x,\\pi\\_*(x,h))-\\tilde{Q}^i\\_{h}(x,a)\\right\\\\}.\n$$\nHere, $\\tilde{V}^i_h(x)=\\langle w(x), \\mathbf{r}^i_{h:H}\\rangle$, where $w(x)\\in\\mathbb{R}^{H-h+1}$ is a shared weighting vector across all objectives, and $\\mathbf{r}^i_{h:H}=[r^i_{h}(\\cdot,\\cdot),r^i_{h+1}(\\cdot,\\cdot),\\cdots, r^i_{H}(\\cdot,\\cdot)]$.\n\n**Lines 797-800:** Under the revised assumption, we can demonstrate that Lines 797-800 hold because the action-value function $\\bar{Q}^i_h(x,a)$ decomposes as $r_{h}^i(x,a) + \\[\\mathbb{P}\\_h \\hat{V}^i_{k,h+1}\\](x,a)$, where $\\hat{V}^i_{k,h+1}$ represents a weighted sum of rewards from step $h+1$ to $H$. Crucially, the weighting parameter $w(x) = \\phi(x, \\pi_k(x,h))^\\top U_h^{-1}F_h$ is shared across all objectives, ensuring consistency in multi-objective optimization. Here, $F_h \\in \\mathbb{R}^{d\\times k}$ denotes the feature matrix comprising historical state-action pairs, defined as $F_h = [\\phi(x_{1,h},a_{1,h}), \\ldots, \\phi(x_{k,h},a_{k,h})]$.  \n\n**Comparison with Assumption 1:** \n\n- *Advantage.* Assumption 1 requires that for any action $a_1,a_2\\in A$, if $a_2$ lexicographically dominates $a_1$, then their rewards satisfies the trade-off value $\\lambda$. The revised assumption fixed the one action as $\\pi_*(x,h)$, relaxing the trade-off among actions. \n- *Limitation.* The revised assumption introduces a shared weight $w(x)$ across objectives, ensuring **consistent reward processing** via $\\tilde{V}^i_{h+1}(x)$. While this is natural in tabular MDPs (where $w(x)$ represents visit-count normalization), it imposes stricter conditions in linear MDPs due to the non-fixed nature of $w(x)$. \n\n---\n\nWe thank the reviewer for prompting this clarification, which strengthens our theoretical framework. We are happy to answer more questions.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "My major concern is on Assumption 1. I am unable to find the definition of \"$a_2$ lexicographically dominates $a_1$\" in the main text (please point it out if there is any). Please refer to for follow-up questions.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "**Strength:** This paper establishes the first theoretical regret bound for MORL.\n\n**Weakness:** See Questions.", "other_comments_or_suggestions": "Typo: The inequality under Assumption 1: $\\text{LHS} \\le \\lambda \\cdot \\max_{j \\in [i - 1]} \\\\{ r_h^j(x, a_2) - r_h^j (x, a_1) \\\\}$", "questions_for_authors": "1. What is the definition of \"$a_2$ lexicographically dominates $a_1$\" in Assumption 1? Does it mean the reward vector $[r_h^1(x,a_2), \\cdots, r_h^m(x,a_2)]$ lexicographically dominates vector $[r_h^1(x,a_1), \\cdots, r_h^m(x,a_1)]$?\n2. Following Q1, I have one question regarding the proof of Lemma 3 in Appendix E. Specifically, why would Assumption 1 result in the argument in lines 797-800?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KIMIRkOg50", "reviewer": "Reviewer_xDG7", "summary": "This work focuses on development of an algorithmic framework with theoretical performance guarantees in Multi-objective RL where the underlying Multi-Objective Markov Decision Process (MO-MDP) is assumed to be linear. The algorithmic strategy optimizes for lexicographic rewards which are essentially hierarchically ordered. To this end, Lexicographic Linear RL (LLRL), is proposed in the finite-horizon episodic learning setup. The method refines agent's policy over time by backward pass updates on the model parameters, careful management of exploration-exploitation trade-off, and handling lexicographic rewards through multi-stage action refinement via a dedicated action elimination routine. The paper also surfaces key challenges with MORL and connects them to its key algorithmic innovation pieces.Finally, a mathematical analysis of LLRL's performance measured in regret against optimal rewards is also presented.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your constructive feedback. We have carefully considered your concerns (including Weaknesses and Questions raised), and our responses are provided below.\n\n---\n\n*W1. The lack of experimental results is a significant limitation.*\n\nThank you for raising this issue. The absence of empirical validation in our work aligns with the foundational single-objective linear MDP studies (Jin et al. 2020; Zanette et al. 2020; He et al. 2023), which similarly omit experiments due to challenges in constructing valid linear MDP benchmarks (e.g., enforcing low-rank dynamics and linear payoff structures). We plan to address this limitation in two phases: **i)** Synthetic experiments will be added to illustrate key theoretical properties. **ii)** Comprehensive empirical comparisons against heuristic baselines and ablations will be conducted in follow-up work.\n\n---\n\n*W2. The assumption that the transition kernel and reward function are linear may limit the applicability of the algorithm in practice.*\n\nWe acknowledge that the linear assumptions may not hold universally in all practical scenarios, particularly in environments with highly complex dynamics or non-linear relationships. However, linearity allows us to leverage well-established mathematical tools from linear algebra and convex optimization, which are essential for deriving rigorous regret bounds. Similar assumptions are common in foundational RL theory (e.g., Jin et al. (2020), Zanette et al. (2020), and He et al. (2023)) to balance generality and analyzability. \n\nMoreover, in finite state-action spaces, any nonlinear system can be represented as a linear MDP by encoding each state-action pair $(x, a)$ as a one-hot feature vector in $\\mathbb{R}^d$, where $d=|\\mathcal{S}| \\times |\\mathcal{A}|$. The transition kernel $\\mathbb{P}(x' \\mid x, a)$ and reward function $r(x, a)$ can be expressed as inner products between the feature vector of $(x, a)$ and learnable parameters.\n\nIn the future, we will try to adopt techniques of generalized linear bandits or Lipschitz bandits to extend the model into generalized linear or Lipschitz.\n\n---\n\n*Q1. How scalable will be LLRL? In other words, what are the computational complexities of the LLRL algorithm and the LAE procedure?*\n\nThe computational cost of LLRL mainly lies on LAE and policy update (Steps 19-24). Below, we provide a detailed complexity analysis of Algorithm 1:\n\n1. Step 7: The complexity is $O(d^2|\\mathcal{A}|)$.\n\n2. Step 8: LAE requires $O(md|\\mathcal{A}|)$ computations.\n\n3. Step 20: The complexity is $O(d^2)$, as $U_h$ can be updated incrementally.\n\n4. Step 21: The complexity is $O(mk)$ for updating $m \\cdot k$ values.\n\n5. Step 22: The complexity is $O(mkd+md^2)$, dominated by inverting $U_h$ ($O(d^2)$) and computing $m$ linear regressions ($O(mkd+md^2)$).\n\n6. Step 23: No additional resources are required, as Q-values can be updated directly from retained $\\{\\hat{w}_h^i\\}_{i\\in[m]}$.\n\n- Summing across all $H$ MDP layers, the complexity of $k$-th round is $O(Hmd|\\mathcal{A}|+Hd^2|\\mathcal{A}|+Hmkd+Hmd^2)$.\n- Summing over $K$ rounds, the **overall computational complexity of LLRL** is $O(KHd|\\mathcal{A}|(m+d)+KHmd(K+d))$. \n\nWe will incorporate this complexity analysis in the revised paper to clarify scalability.\n\n---\n\n*Q2. Can we have a mathematical sketch of how the performance would look like in the absense of Assumption 1? Also, is there any other way based on practical considerations that we can measure these objective trade-offs?*\n\nIn the context of lexicographic bandit problems, Huyuk and Tekin [1] establish regret bounds without relying on assumptions analogous to Assumption 1 in our work. Extending their analysis to linear MDPs, we hypothesize that a similar regret bound of order $O((d^2H^4K)^{\\frac{2}{3}})$ may hold, though a formal proof remains an open question for future investigation.\n\nRegarding practical trade-off quantification, domain-specific expertise often provides empirically grounded ratios for prioritizing objectives. For example, environmental policy frameworks frequently employ comparative metrics where 1 tonne of SO2 emissions is considered $\\leq10$ times as harmful as 1 tonne of CO emissions (Podinovski [2], 1999), which directly corresponds to $\\lambda=10$.\n\n*[1] Huyuk, A. and Tekin, C. Multi-objective multi-armed bandit with lexicographically ordered and satisficing objectives. Machine Learning, 110(6):1233–1266, 2021.*\n\n*[2] Podinovski, V. V. A dss for multiple criteria decision analysis with imprecisely specified trade-offs. European Journal of Operational Research, 113(2):261–270, 1999.*\n\n---\n\n**Other Comments Or Suggestions:** *Notations and Alternative Assumptions.*\n\nThank you for your positive feedback and constructive suggestions. In the revised paper, we will carefully revise all notation and compile it into a summary table for clarity. Meanwhile, we will try to establish comparable regret bounds without Assumption 1 in the future work.", "claims_and_evidence": "The authors' central claim is around developing an efficient strategy for MOLRL with lexicographic rewards settings. To this end, LLRL is presented, and the evidence of LLRL's performance is captured in theoretical regret analysis (Theorem 1, 2). To the best of my knowledge, an empirical performance evaluation is missing for LLRL.", "methods_and_evaluation_criteria": "The method LLRL is proposed towards solving an MOMDP in lexicographic rewards setting, and it is being benchmarked by worst case regret bound against a optimal policy. To the best of my understanding, both the method and the evaluation criteria is relevant to the underlying problem setup.", "theoretical_claims": "The key theoretical contributions are stated in Theorem 1,2 providing LLRL's regret bounds. These results are then proven using intermediate supporting results through Appendix A-J. In my understanding, the results are derived systematically using well-known statistical concentration inequalities, and linear algebra results.", "experimental_designs_or_analyses": "A thorough experimental analysis of LLRL is missing.", "relation_to_broader_scientific_literature": "In my understanding, the paper discusses relevant prior works on linear RL as well as MORL, identifies a concrete gap for MOMDP with lexicographic reward structure. The proposed LLRL method addresses the aforementioned problem statement, and is supported by Theorem 1,2 where the regret bounds are derived for a finite horizon setup. However, an empirical validation of LLRL is missing.", "essential_references_not_discussed": "I think the paper provides a good overview of the relevant literature.", "other_strengths_and_weaknesses": "Strengths:\n1. The LLRL algorithm is well-described with the key techniques and challenges being clearly highlighted.\n2. The proofs are rigorous and detailed.\n3. The results in the misspecified setting are interesting and valuable.\n\n\nWeakeness:\n1. The lack of experimental results is a significant limitation.\n\n2. The assumption that the transition kernel and reward function are linear may limit the applicability of the algorithm in practice.", "other_comments_or_suggestions": "1. While the paper is well-written overall, some of the notation can be dense and difficult to follow. Consider simplifying the notation where possible and providing more intuitive explanations of the key concepts. A diagramatic workflow could be helpful in this regard.\n\n2. Investigate alternative assumptions for managing inter-objective trade-offs and explore whether comparable regret bounds can be derived without Assumption 1.", "questions_for_authors": "1. How scalable will be LLRL ? In other words, what are the computational complexities of the LLRL algorithm and the LAE procedure?\n\n2. Can we have a mathematical sketch of how the performance would look like in the absense of Assumption 1 ? Also, is there any other way based on practical considerations that we can measure these objective trade-offs ?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a novel algorithm for multi-objective reinforcement learning (MORL) under lexicographically ordered objectives in the linear MDP setting. The proposed method, Lexicographic Linear Reinforcement Learning (LLRL), provides regret guarantees that match the single-objective case up to leading-order terms and extend to the misspecified setting. The work offers a rigorous analysis of a challenging objective structure where Bellman optimality does not naturally hold and introduces a principled action elimination mechanism to handle the lexicographic constraints.

The paper's main strengths include its theoretical contributions, well-structured algorithmic design, and clear motivation for exploring lexicographic preferences within the linear MDP framework. The reviewers praised the novelty of formal regret bounds in this space and the careful use of linear assumptions to enable tractable analysis. However, several concerns were raised. One reviewer criticized the initial claim of being the first MORL regret bound as overstated, particularly in light of prior work in lexicographic bandits. Another reviewer highlighted the strength of Assumption 1, questioning whether it might reduce the problem to scalarized RL. In addition, the absence of experimental results and the lack of discussion around computational complexity were noted as limitations. Some confusion also stemmed from the paper’s notation and incomplete treatment of earlier MORL literature.

The authors responded constructively to all these points. They agreed to remove and rephrase the overstatement of contribution, clarified their position concerning prior bandit literature, and significantly improved the theoretical basis by revising Assumption 1. This revised assumption, introduced in response to a key concern about Lemma 3, was positively acknowledged by the reviewer who raised it. A subsequent technical exchange regarding scalarization-based strategies led to a meaningful theoretical comparison, in which the authors convincingly demonstrated the advantages of their approach in terms of regret bounds for high-priority objectives. Further, the authors provided a complete computational complexity analysis and outlined a clear plan for future empirical validation, consistent with precedent in theoretical RL papers.

Overall, the submission makes a timely and rigorous contribution to MORL. In addition, the authors’ technically deep responses helped resolve key concerns.
Decision: Accept (poster)