Multi-objective Linear Reinforcement Learning with Lexicographic Rewards

We sincerely appreciate your constructive feedback. We have carefully considered your concerns (including Weaknesses and Questions raised), and our responses are provided below.

W1. The lack of experimental results is a significant limitation.

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

W2. The assumption that the transition kernel and reward function are linear may limit the applicability of the algorithm in practice.

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

Moreover, 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.

In the future, we will try to adopt techniques of generalized linear bandits or Lipschitz bandits to extend the model into generalized linear or Lipschitz.

Q1. How scalable will be LLRL? In other words, what are the computational complexities of the LLRL algorithm and the LAE procedure?

The computational cost of LLRL mainly lies on LAE and policy update (Steps 19-24). Below, we provide a detailed complexity analysis of Algorithm 1:

1. Step 7: The complexity is $O(d^2|\mathcal{A}|)$.

2. Step 8: LAE requires $O(md|\mathcal{A}|)$ computations.

3. Step 20: The complexity is $O(d^2)$, as $U_h$ can be updated incrementally.

4. Step 21: The complexity is $O(mk)$ for updating $m \cdot k$ values.

5. 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)$).

6. Step 23: No additional resources are required, as Q-values can be updated directly from retained $\{\hat{w}_h^i\}_{i\in[m]}$.

• Summing across all $H$ MDP layers, the complexity of $k$-th round is $O(Hmd|\mathcal{A}|+Hd^2|\mathcal{A}|+Hmkd+Hmd^2)$.
• Summing over $K$ rounds, the overall computational complexity of LLRL is $O(KHd|\mathcal{A}|(m+d)+KHmd(K+d))$.

We will incorporate this complexity analysis in the revised paper to clarify scalability.

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?

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

Regarding 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$.

[1] Huyuk, A. and Tekin, C. Multi-objective multi-armed bandit with lexicographically ordered and satisficing objectives. Machine Learning, 110(6):1233–1266, 2021.

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

Other Comments Or Suggestions: Notations and Alternative Assumptions.

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

Many thanks for your constructive reviews. We have carefully considered your concerns and our responses are provided as follows.

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)]$?

Yes, 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)]$.

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?

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

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

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]$,

Here, $\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)]$.

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})]$.

Comparison with Assumption 1:

• 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.
• 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)$.

We thank the reviewer for prompting this clarification, which strengthens our theoretical framework. We are happy to answer more questions.

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.

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.

Thank you for highlighting this important connection. We have clarified the relationship between general and linear MDPs as follows:

1. 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.
2. 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.

W2. The space and time complexity of Algorithm 1 is not discussed $\cdots$ An explicit readers to understand any (potential) limitations to application.

We thank the reviewer for the constructive feedback. Below, we provide a detailed complexity analysis of Algorithm 1 and discuss its limitations:

1. Step 7: Computational complexity is $O(d^2|\mathcal{A}|)$, while memory complexity is $O(|\mathcal{S}||\mathcal{A}|)$ for storing state-action pairs.

2. Step 8: LAE requires $O(md|\mathcal{A}|)$ computations and $O(|\mathcal{S}||\mathcal{A}|)$ memory.

3. Step 20: Both computational and memory complexity are $O(d^2)$, as $U_h$ can be updated incrementally.

4. 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]}$.

5. 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]}$.

6. Step 23: No additional resources are required, as Q-values can be updated directly from retained $\{\hat{w}_h^i\}_{i\in[m]}$.

Summing across all $H$ MDP layers:

• The computational complexity of is $O(Hmd|\mathcal{A}|+Hd^2|\mathcal{A}|+Hmkd+Hmd^2)$ .
• The memory is $O(Hd^2+Hmk+Hmd+|\mathcal{S}||\mathcal{A}|)$.

Summing over $K$ rounds:

• The total computational complexity is $O(KHd|\mathcal{A}|(m+d)+K^2Hmd+KHmd^2)$ .
• The memory of our algorithm is $O(Hd^2+HmK+Hmd+|\mathcal{S}||\mathcal{A}|)$.

The $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.

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

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

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.

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

We sincerely appreciate the constructive feedback and have carefully considered the raised concerns. Our point-by-point responses follow below.

Q1. Claims And Evidence: Contributions 1-3 are well supported and insightful. However, the finite-horizon assumption shouldn't be glossed over $\cdots$.

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

Q2. Claims And Evidence: Contribution 4 seems disingenuous $\cdots$ Isn't that just a restricted class of MDPs like the authors' restriction?

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.

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.

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

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.

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

Q5. Other Strengths And Weaknesses: Some additional discussion of where assumption 1 comes from would be nice.

Assumption 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$.

Q6. Other Strengths And Weaknesses: Might it actually allow the objective to satisfy the Continuity axiom of von Neumann and Morganstern?

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

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

We 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).

Q8. Other Comments Or Suggestions.

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