How to Find the Exact Pareto Front for Multi-Objective MDPs?

## Abstract

Abstract Multi-objective Markov Decision Processes (MDPs) are receiving increasing attention, as real-world decision-making problems often involve conflicting objectives that cannot be addressed by a single-objective MDP.
The Pareto front identifies the set of policies that cannot be dominated, providing a foundation for finding Pareto optimal solutions that can efficiently adapt to various preferences.
However, finding the Pareto front is a highly challenging problem. Most existing methods either (i) rely on traversing the continuous preference space , which is impractical and results in approximations that are difficult to evaluate against the true Pareto front, or (ii) focus solely on deterministic Pareto optimal policies, from which there are no known techniques to characterize the full Pareto front. Moreover, finding the structure of the Pareto front itself remains unclear even in the context of dynamic programming, where the MDP is fully known in advance.
In this work, we address the challenge of efficiently discovering the Pareto front.
By investigating the geometric structure of the Pareto front in MO-MDP, we uncover a key property: the Pareto front is on the boundary of a convex polytope whose vertices all correspond to deterministic policies, and neighboring vertices of the Pareto front differ by only one state-action pair of the deterministic policy, almost surely.
This insight transforms the global comparison across all policies into a localized search among deterministic policies that differ by only one state-action pair, drastically reducing the complexity of searching for the exact Pareto front.
We develop an efficient algorithm that identifies the vertices of the Pareto front by solving a single-objective MDP only once and then traversing the edges of the Pareto front, making it more efficient than existing methods. Furthermore, the entire Pareto front can be found in V 𝑉 V italic_V iterations, where V 𝑉 V italic_V represents the number of vertices on the Pareto front.
Our empirical studies demonstrate the effectiveness of our theoretical strategy in discovering the Pareto front efficiently.

## 1 Introduction

In recent years, there has been growing interest in multi-objective Markov Decision Processes (MO-MDPs), where the reward involves multiple implicitly conflicting objectives [, ].
Traditional methods developed for single-objective MDPs are not directly applicable to MO-MDPs, as they fail to address the trade-offs between conflicting objectives.
Consequently, attention has shifted toward developing approaches for finding Pareto optimal policies, policies whose returns cannot be dominated by any other policies, in MO-MDPs and, more broadly, in multi-objective Reinforcement Learning (RL) [, , , ].

Finding Pareto optimal policies based on specific preferences is often sensitive to the scales of the objectives and struggles to adapt to changing preferences  [, ].
Accurately capturing true preferences across multiple objectives is challenging, as the balance between objectives can be distorted by differences in scale [, ].
When one reward objective has a much larger scale than others, even assigning a small weight to it cannot prevent it from dominating the scalarized reward, leading to an undesired Pareto optimal policy.
In such cases, multiple adjustments to the preferences may be necessary to achieve the desired balance across objectives.
Additionally, preferences may shift over time, requiring quick adaption to new preferences [, , ].
In such cases, solving for a Pareto optimal policy from scratch using a scalarization-based approach does not meet the need for fast adaptability.

On the other hand, the Pareto front which consists of all Pareto optimal policies directly represents the trade-offs between multiple objectives, thus avoiding sensitivity to differences in objective scales.
Once the Pareto front is obtained, the Pareto optimal policies corresponding to various preference vectors can be selected from the Pareto front without recalculating from scratch.

The Pareto front approximation methods can be broadly divided into two categories.
The first straightforward approach derives the Pareto front by solving single-objective problems obtained from scalarizing the multi-objective MDP for each preference and combining the resulting Pareto optimal policies [].
Although state-of-the-art methods in the field of MO-RL leverage the similarity between Q-functions or policy representations of Pareto optimal policies for nearby preferences to avoid solving the optimal policy from scratch for each preference, thus reducing complexity [, , ], these methods still require traversing the continuous preference space to approximate the Pareto front.
Another Pareto front finding method iteratively finds the preference that improves the current Pareto front the most to avoid blind traversing the preference space [, ].
However, this method only identifies deterministic policies on the Pareto front, which does not capture the entire Pareto front.
In 2D (2-objectives) cases, constructing the whole Pareto front from deterministic Pareto optimal policies simply connects adjacent deterministic points by a straight line. However, in general cases, it is not that simple.
For example, in a 3D (3-objectives) case shown in Fig. 1, deriving the entire Pareto front (as in Fig. 1(a)) from the vertices corresponding to deterministic Pareto optimal policies (as in Fig. 1(b)) alone still requires significant effort.
Therefore, even in scenarios where the MDP is fully known, deriving the entire Pareto front through dynamic programming remains complex.
This raises a fundamental question:

How can we efficiently obtain the full exact Pareto front in MO-MDPs?

In this work, we address the problem of efficiently finding the Pareto front in MO-MDPs.
We explore the geometric properties of the Pareto front in MO-MDP and reveal a surprising property of deterministic policies on the Pareto front: the Pareto front lies on the boundary of the convex polytope, and the neighboring deterministic policies, corresponding to neighboring vertices of the Pareto front, differ by one state-action pair almost surely.
Building on this key insight, we propose an efficient algorithm for finding the Pareto front.

Specifically, our contributions are as follows:

- 1.
Geometric Properties of the Pareto Front: We reveal several key geometric properties of the Pareto front, which form the foundation of our efficient Pareto front searching algorithm. First, we demonstrate that the Pareto front lies on the boundary of a convex polytope, with its vertices corresponding to deterministic policies. Notably, any neighboring policies on this boundary differ by only one state-action pair, almost surely(^1^11For almost all ${\mathbf{P}}$ and ${\bm{r}}$ in the space of valid transition kernels and rewards (with Lebesgue measure $1$), the neighboring deterministic policies on the convex polytope differs by at most one state-action pair.).
Furthermore, we prove that every deterministic policy on the Pareto front is connected to at least one deterministic Pareto optimal policy. Additionally, we show that all Pareto-optimal faces incident to a deterministic policy can be efficiently extracted from the convex hull formed by that policy and its neighbors.
- 2.
Efficient Pareto Front Searching Algorithm: We propose an efficient Pareto front searching algorithm that can discover the exact Pareto front, while also identifying all deterministic Pareto-optimal policies as a byproduct. The proposed algorithm only requires solving the single-objective optimal policy once for initialization, and the total iteration number is the same as the number of vertices on the Pareto front.

Figure: (a) Pareto front
Refer to caption: extracted/5941282/figs/paper_figs/intro_figs/Pareto_front_S_5_A_5_seed_1_r_3.png

## 2 Related work

In the literature on both multi-objective optimization and reinforcement learning, two categories of problems are commonly considered.
The first assumes that the (sequential) decision maker has preset or deduced preferences over multiple objectives in advance, and the goal is to find a Pareto optimal solution that performs well under these given preferences [, , , ]. The methods addressing this problem in multi-objective MDPs are specifically referred to as single-policy methods [, , , , ].
The second category focuses on finding a set of (approximate) Pareto optimal solutions that are diverse enough to represent the full range of the Pareto front [, , ]. This allows the (sequential) decision maker to choose the most preferable solution afterward. Due to its flexibility in adapting to changing preferences, this approach has received significant attention.
This section gives an overview of the methods to get the Pareto optimal front estimation in multi-objective MDP and MO-RL.

As early as in [], the dynamic programming-based method was proposed to find the optimal Pareto front for MO-MDP, though the size of the candidate non-stationary policy set grows exponentially with the time horizon. To efficiently find the vertices on the Pareto front, [] introduced the Optimistic Linear Support (OLS) method, which solves a single-objective problem along the direction that improves the current set of candidate policies the most. However, OLS can only find vertices on the Pareto front and does not provide a method for constructing the entire Pareto front from these vertices, which remains non-trivial.

Authors of [] proposed Pareto Q-learning, which learns a set of Pareto optimal policies in the MO-RL setting.
Building on this, subsequent work has investigated training a universal Pareto optimal policy set, where the policy network takes preference embedding as input and outputs the corresponding Pareto optimal policy [, , , ].
These Q-learning variants rely on the maximization of Q-function estimations over the action space, making them suitable only for discrete action spaces. Recent works have extended Q-learning with policy networks to handle continuous action spaces [, ].
While these Q-learning methods update the Q-function for each preference vector by leveraging the Q-functions of similar visited preference vectors thus avoiding the need to retrain from scratch, they still essentially require updating the Q-function for each visited preference vector. Consequently, they still need to explore the preference space to achieve a near-accurate Pareto front. This process becomes computationally inefficient and impractical as the reward dimension increases.

There are also policy-based MORL algorithms designed to find Pareto optimal policies [, , , ].
A concept similar to our approach, which directly searches over the Pareto front, is the Pareto-following algorithm proposed by [].
This algorithm employs a modified policy-gradient method that adjusts the gradient direction to follow the Pareto front.
While it can reduce the complexity of finding the Pareto front by avoiding the need to converge to the optimal policy from scratch, it still requires multiple policy-gradient steps to identify even a nearby Pareto optimal policy.
Furthermore, it cannot guarantee comprehensive coverage of the estimated policies, nor can it ensure discovering the true Pareto front.

In addition to value-based and policy-based methods that extend from single-objective RL, there are also heuristic approaches for combining policies that have shown promising performance in specific settings.
For instance, Rewarded Soup [, ] proposes learning optimal policies for individual preference criteria and then linearly interpolating these policies to combine their capabilities.
While [] demonstrated that rewarded soup is optimal when individual rewards are quadratic with respect to policy parameters, this quadratic reward condition is highly restrictive and does not apply to general MDP settings.

## 3 Pareto front searching on MO-MDP

We first provide an overview of the proposed efficient Pareto front searching algorithm, followed by an introduction to the basic concepts behind MO-MDP. Finally, we present the details of the proposed algorithm.

### 3.1 Algorithm Overview

This section provides an overview of our proposed algorithm for efficiently identifying the entire Pareto front. By using a single-objective solver *only once* to get an initial Pareto optimal point and then searching along the surface of the Pareto front, our method ensures complete coverage of the Pareto front.

The algorithm maintains a queue $Q$ containing Pareto optimal policies whose neighboring policies have yet to be explored.
The queue is initialized with a deterministic policy $\pi_{0}$, derived by solving a single-objective MDP, which is formulated from the original multi-objective MDP using an arbitrary positive preference vector,
ensuring that $\pi_{0}$ lies on the Pareto front.
The obtained policy $\pi_{0}$ serves as the starting point for systematically traversing the entire Pareto front.

In each loop, we pop out one element $\pi$ in the queue $Q$. The following steps are applied to explore the Pareto front in the neighborhood of $\pi$. We also use Fig. 2 to give an illustration of those steps in each loop.

- (a)
(Neighbor Search) First, we identify and evaluate all deterministic policies that differ from $\pi$ by only one state-action pair. From these, we discard any policies whose returns are dominated by returns of others(^2^22We say that ${\bm{u}}$ is dominated by ${\bm{v}}$ if ${\bm{u}}$ is less than or equal to ${\bm{v}}$ in all objectives. A more formal definition of dominance is provided in Section 3.2.).
As shown in Fig. 2(a), the gray planes and edges represent previously discovered parts of the Pareto front, the black point corresponds to the returns of $\pi$ (the deterministic Pareto-optimal policy being explored), and the red points represent the policies that are not dominated among those differing from $\pi$ by only one state-action pair.
- (b)
(Incident Faces Calculation) Next, we compute the incident faces of the return of $\pi$ on the convex hull formed by the returns of $\pi$ and the policies identified in the first step, i.e., the non-dominated policies among deterministic policies differing from $\pi$ by only one state-action pair.
As depicted in Fig. 2(b), the incident faces of $\pi$ on the constructed convex hull are illustrated with purple planes, and the black lines represent the edges of these incident faces.
- (c)
(Pareto Face Extraction).
In this final step, we select the faces from the incident faces identified in the second step.
We add a face from the incident faces to the Pareto front if a non-negative combination of the normal vectors of all intersecting facets on the face yields a strictly positive vector.
Once a face is selected, all neighboring vertices on this face are added to the set of deterministic Pareto optimal policies.
These vertices are also added to the queue $Q$ to explore their neighboring faces in the next iterations.
As illustrated in Fig. 2(c), the selected faces are added to the set of Pareto front (marked in blue), and all neighboring vertices on the incident faces are shown as orange dots.

By applying the above steps to all policies in the queue $Q$ until the queue is empty ensures that the neighboring policies of all possible deterministic policies on the Pareto front have been visited.
Since all vertices and their incident faces are traversed by the proposed algorithm, it guarantees full exploration of all faces of the Pareto front.

As the algorithm is guaranteed to consistently search along the Pareto front, which will be shown in Section 4, the total number of iterations is the same as the number of deterministic Pareto optimal policies.

Figure: (a) Step 1: Selecting non-dominated distance-1 policies
Refer to caption: extracted/5941282/figs/paper_figs/steps/step1.png

### 3.2 Preliminaries on MO-MDP

We consider a discounted MO-MDP $(\mathcal{S},\mathcal{A},{\mathbf{P}},{\bm{r}},\gamma)$, where $\mathcal{S}$ and $\mathcal{A}$ are the sets of states and actions, with cardinalities $S$ and $A$, respectively.
The transition kernel ${\mathbf{P}}$ defines the probability ${\mathbf{P}}(s^{\prime}|s,a)$ of transitioning from $s$ to $s^{\prime}$ given action $a$.
The reward tensor ${\bm{r}}\in\mathbb{R}^{S\times A\times D}$ specifies the
$D$-dimensional reward ${\bm{r}}(s,a)$ obtained by taking action $a$ in state $s$. $\gamma<1$ is the discount factor.

Define $\Pi$ as the set of stationary policies, where for any $\pi\in\Pi$, $\pi(a|s)$ represents the probability of selecting $a$ at state $s$.
We consider an ergodic MDP, meaning that any state is reachable from any other state by following a valid policy. The assumption of MDP ergodicity is commonly used in RL literature [, ].

The value function with policy $\pi$ is denoted as ${\mathbf{V}}^{\pi}(s)\in\mathbb{R}^{d}$, which is written as

$$ ${\mathbf{V}}^{\pi}(s)=\mathbb{E}\left[\sum_{t}\gamma^{t}{\bm{r}}(s_{t},a_{t})| s_{0}=s,a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim{\mathbf{P}}(\cdot|s_{t},a_{t}) \right].$ $$

Given an initial state distribution $\mu>0$, which assumes that the probability of starting from any state $s$ is non-zero, we define the long-term return of policy $\pi$ as $J^{\pi}(\mu)=\mathbb{E}_{s\sim\mu(\cdot)}\left[{\mathbf{V}}^{\pi}(s)\right]$.
Let ${\mathbb{J}}(\mu)$ denote the set of expected long-term returns for all stationary policies under the initial state distribution $\mu$, i.e., ${\mathbb{J}}(\mu)=\{J^{\pi}(\mu)|\pi\in\Pi\}$. For simplicity of notation, we will omit $\mu$ in the following sections.

${\mathbb{J}}$ is convex as proven in []. We further emphasize that ${\mathbb{J}}$ is not only convex but also a convex polytope, with each vertex corresponding to a deterministic policy, as established in Lemma 1(^3^33Proof of this lemma is in Appendix D.).

###### Lemma 1 .

${\mathbb{J}}$ is a closed convex polytope, and its vertices are achieved by deterministic policies.

As we investigate the boundary of ${\mathbb{J}}$, which is a convex polytope, we introduce relevant definitions concerning convex polytopes. Let ${\mathbb{C}}\subseteq\mathbb{R}^{d}$ be a convex polytope. A face of ${\mathbb{C}}$ is any set of the form ${\mathbb{F}}={\mathbb{C}}\cap\{{\bm{x}}\in\mathbb{R}^{d}:{\bm{w}}^{\top}{\bm{x
}}=c\}$, where ${\bm{w}}^{\top}{\bm{y}}\leq c$ for any ${\bm{y}}\in{\mathbb{C}}$. The faces of dimension 0 0, $1$, and $\text{dim}({\mathbb{C}})-1$ are called vertices, edges, and facets, respectively.

To address the trade-offs between conflicting objectives, we introduce the well-known notions of dominance and Pareto optimality. For any two vectors ${\bm{u}}$ and ${\bm{v}}$, ${\bm{u}}$ strictly dominates ${\bm{v}}$, denoted as ${\bm{u}}\succ{\bm{v}}$, if each component of ${\bm{u}}$ is at least as large as the corresponding component of ${\bm{v}}$, and at least one component is strictly larger.
A vector ${\bm{u}}$ is Pareto optimal in a set ${\mathbb{S}}$ if any other vector ${\bm{v}}\in{\mathbb{S}}$ does not strictly dominate ${\bm{u}}$. The Pareto front of a set ${\mathbb{S}}$, denoted as $\mathbb{P}({\mathbb{S}})$, is the set of Pareto optimal vectors in ${\mathbb{S}}$.

In the context of MO-MDP, we say that policy $\pi_{1}$ dominates policy $\pi_{2}$, denoted as $\pi_{1}\succ\pi_{2}$ if $J^{\pi_{1}}\succ J^{\pi_{2}}$. A policy $\pi$ is Pareto optimal if $J^{\pi}$ is Pareto optimal in ${\mathbb{J}}$. We similarly define the Pareto front of $\Pi$ as $\mathbb{P}(\Pi)=\{\pi\in\Pi\mid J^{\pi}\in\mathbb{P}({\mathbb{J}})\}$(^4^44We consider the Pareto optimality definition based on the long-term return concerning an initial distribution. A detailed comparison with other definitions of Pareto optimality can be found in Appendix A.).

###### Lemma 1 .

### 3.3 Pareto front searching

This section presents the pseudocode and details of the proposed Pareto front searching algorithm.
Before diving into details, we introduce some necessary notations as preparation for presenting our algorithms(^5^55Notation table is provided in Table 1 of Appendix B.).
We denote the set of deterministic policies that differ from $\pi$ by exactly one state-action pair as $\Pi_{1}(\pi)$, and the set of non-dominated policies among $\Pi_{1}(\pi)$ as $\Pi_{1,\text{ND}}(\pi)$. Let $\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\})$ represent the convex hull constructed from the long-term returns of $\Pi_{1,\text{ND}}(\pi)$ and $\pi$. The set of incident faces of $J^{\pi}$ on the convex hull $\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\})$ is denoted by ${\mathbb{F}}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$.

Figure: Algorithm 1 Pareto Front Searching Algorithm

The pseudocode for the Pareto front searching algorithm is presented in Algorithm 1. While the primary objective of Algorithm 1 is to identify the entire Pareto front, a byproduct of the algorithm is the identification of all vertices on the Pareto front that correspond to all deterministic Pareto optimal policies. Therefore, the output of Algorithm 1 includes both the Pareto front, denoted as $\mathbb{P}(\Pi)$, and the set of deterministic Pareto optimal policies, denoted as ${\mathbb{V}}(\Pi)$.

We begin by finding a Pareto optimal policy through scalarization and adding it to the queue $Q$ as part of the initialization, as detailed in 6 and 7 of Algorithm 1.

Neighbour Search As detailed in 11 and 12 of Algorithm 1, for any deterministic Pareto optimal policy $\pi$ popped from $Q$, we first evaluate all policies in $\Pi_{1}(\pi)\setminus{\mathbb{Z}}$, which differ from $\pi$ by only one state-action pair and have not yet been visited (with the visited policies stored in ${\mathbb{Z}}$). Once the long-term returns of $\Pi_{1}(\pi)$ are known, we select the set of non-dominated policies, $\Pi_{1,\text{ND}}(\pi)$, the set of policies in $\Pi_{1}(\pi)$ that cannot be dominated by any other policies in $\Pi_{1}(\pi)$. Specifically, the PPrune algorithm from [] efficiently identifies the set of non-dominated elements from a given set.

Although the number of policies differing by one state-action pair is proportional to the state and action space, i.e., $|\Pi_{1}(\pi)|=S\times(A-1)$, the number of non-dominated policies $\Pi_{1,\text{ND}}(\pi)$ is usually small. This helps reduce the complexity of calculating the convex hull and extracting Pareto front faces in the subsequent steps.

Incident Facets Calculation In 13 and 14, we aim to compute ${\mathbb{F}}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$, the set of $(D-1)$-dimensional facets of $\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\})$ that intersect at $J^{\pi}$.
A straightforward approach is to calculate the convex hull of the set of vertices $J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}$ (as shown in 13) and select all facets that intersect at $J^{\pi}$. However, since we are only interested in the facets of $\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\})$ that involve $J^{\pi}$, computing the entire convex hull is unnecessary. Specifically, facets that do not involve $J^{\pi}$ do not need to be considered.
An efficient solution is to adapt the Quickhull algorithm [], a well-established method for computing the convex hull of a set of points, to our algorithm. This adaptation focuses on updating only the facets related to $J^{\pi}$, thereby avoiding unnecessary calculations of irrelevant facets.

Pareto Face Extraction We apply Algorithm 2 to extract all faces where the Pareto front intersects at $J^{\pi}$ from ${\mathbb{F}}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$.

Figure: Figure 3: Convex polytope (blue planes) and its Pareto front (red edge and plane)
Refer to caption: extracted/5941282/figs/paper_figs/neighbour_facet_doesnot_exist.png

Consider a $k$-dimensional face of a $D$-dimensional polytope. Let the normal vectors to the $D-1$-dimensional facets that intersect at this face be denoted as $\{{\bm{w}}_{i}\}_{i=1}^{n}$. Specifically, when $k=D-1$, then the facet that intersects on the face is itself, and $n=1$. The face is Pareto optimal if $\sum_{i=1}^{n}\alpha_{i}^{*}[\mathbf{w}_{i}]_{j}>0$ for any $j=1,\cdots,D$, where $\boldsymbol{\alpha}^{*}$ is the solution to the following linear programming problem:

$$ $\displaystyle\text{maximize}_{\boldsymbol{\alpha}}$ $\displaystyle\min_{j\in\{1,\cdots,D\}}\sum_{i=1}^{n}\alpha_{i}[\mathbf{w}_{i}] _{j},$ (1) subject to $\displaystyle\alpha_{i}\geq 0,\quad\forall i\in\{1,2,\dots,n\}.$ $$

Here, $\mathbf{w}_{i}=[[\mathbf{w}_{i}]_{1},\cdots,[\mathbf{w}_{i}]_{D}]^{\top}$ represents the normal vectors, and $[\mathbf{w}_{i}]_{j}$ refers the $j$-th component of the $i$-th normal vector. The objective function aims the maximize the smallest component of the weighted sum across all dimensions $j=1,\cdots,D$, ensuring the face is Pareto optimal.
A detailed lemma showing the Pareto front criterion and its proof is presented in Appendix G.

It is possible that a high-dimensional face is not on the Pareto front, while some lower-dimensional components of that face still belong to the Pareto front. Figure 3 illustrates this scenario. The cyan and red planes form a 3D polytope, where the red line and red planes represent the Pareto front of the polytope. Notably, the Pareto front includes not only 2D planes but also 1D edges, such as the line segment AB.
This observation implies that even if a high-dimensional face (e.g., the plane containing AB) is not Pareto optimal, it is necessary to examine its lower-dimensional faces (e.g., edge AB) to determine if they are Pareto optimal.

In Algorithm 2, We traverse from $(D-1)$-dimensional faces down to $1$-dimensional faces (edges) to verify if each face is Pareto optimal. Faces that have not yet been verified are pushed into the queue $Q_{\text{face}}$. If the face $H$ popped from $Q_{\text{face}}$ is verified to be Pareto optimal via Eq. 1, it is added to the Pareto face set, and its vertices are added to the set of Pareto optimal vertices. Otherwise, we proceed to examine the subfaces of $F$ that are one dimension lower.

Note that if a Pareto optimal face has vertices corresponding to deterministic policies $\{\pi_{i}\}_{i=1}^{k}$, then the policies constructing the face are convex combinations of $\{\pi_{i}\}_{i=1}^{k}$, expressed as $\{\pi|\pi(a|s)=\sum_{i=1}^{k}\alpha_{i}\pi_{i}(a|s),\forall s,a,\alpha_{i}\geq
0
,\sum_{i=1}^{k}\alpha_{i}=1\}$. The lemma demonstrating this result, along with its detailed proof, can be found in Lemma 23 of Appendix G.

Figure: Algorithm 2 Pareto Optimal Face Selection

## 4 Why can the Pareto-front searching algorithm work?

In this section, we present the theoretical foundations behind Algorithm 1. This section is divided into three parts, and we give an overview of each part as follows.

- 1.
Distance-one Property on Boundary of ${\mathbb{J}}(\mu)$: We prove that neighboring deterministic policies on the boundary of ${\mathbb{J}}$ differ by only one state-action pair. This ensures that we can efficiently find all neighboring policies of $\pi$ on both the boundary of ${\mathbb{J}}$ and the Pareto front by searching within the $\Pi_{1}(\pi)$.
- 2.
Sufficiency of Traversing Over Edges: We show that for any vertex on the Pareto front, at least one edge on the Pareto front connects it to another Pareto-optimal vertex. This property guarantees that we can traverse the entire Pareto front by exploring neighboring deterministic policies.
- 3.
Locality Property of the Pareto front: We establish that the faces of the Pareto front intersecting at a vertex can be found by computing the convex hull of the vertex and returns of non-dominated deterministic policies that differ by one state-action pair. This ensures efficient discovery of Pareto front faces through local convex hull computation, reducing the computational overhead.

### 4.1 Distance-one Property on Boundary of 𝕁 𝕁 {\mathbb{J}} blackboard_J

We present a theorem stating that the endpoints of any edge on the boundary of ${\mathbb{J}}$ correspond to deterministic policies that differ by only one state-action pair, almost surely. Specifically, for a finite MDP $(\mathcal{S},\mathcal{A},{\mathbf{P}},{\bm{r}},\gamma)$, where ${\mathbf{P}}$ is the transition probability kernel and ${\bm{r}}\geq 0$ is the reward function, the set of ${\mathbf{P}}$ and ${\bm{r}}$ for which deterministic policies on the edge of the Pareto front differ by more than one state-action pair has Lebesgue measure zero. The proof of this theorem is provided in Appendix D,

###### Theorem 1 .

For any edge on the boundary of ${\mathbb{J}}$ connecting two deterministic policies, these policies differ by only one state-action pair, almost surely.

Since the Pareto front lies on the boundary of ${\mathbb{J}}$, this theorem guarantees that for any policy $\pi$ on the Pareto front, the neighboring policies on the Pareto front can be found by searching among $\Pi_{1}(\pi)$, a set of policies that differ from $\pi$ by only one state-action pair. This significantly reduces the search space, making it more efficient to traverse the Pareto front.

###### Theorem 1 .

#### Proof Sketch

The proof follows two key steps:
(1) First, we show that any face on the boundary of ${\mathbb{J}}$ is formed by the long-term returns of policies that are the convex combinations of the deterministic policies corresponding to the vertices of the face. Specifically, any point on an edge between two deterministic policies is the long-term return of a convex combination of these policies.
(2) Next, we establish that if two deterministic policies differ by only one state-action pair, the long-term returns of their convex combinations form a straight line. In contrast, if two deterministic policies differ by more than one state-action pair, the long-term returns of their convex combinations do not form a straight line between them for almost all MDPs.

By combining these two observations, we conclude that the endpoints of any edge on the boundary of ${\mathbb{J}}$ correspond to deterministic policies differing by exactly one state-action pair almost surely. Since the Pareto front lies on the boundary of ${\mathbb{J}}$, it follows that neighboring policies on the Pareto front differ by only one state-action pair. This completes the proof.

### 4.2 Sufficiency of Traversing Over Edges

From the previous section, we have the properties of the neighboring policies on the Pareto front. Hence, a natural approach would be to traverse all vertices of the Pareto front by moving along the edges connecting them. However, this approach relies on the assumption that the vertices on the Pareto front are connected. If the vertices are not connected, we risk being stuck at a single vertex on the Pareto front without a way to reach other unconnected vertices. To address this, we present Lemma 2 showing that the Pareto front of ${\mathbb{J}}$ is connected (proof is provided in Appendix E).

###### Lemma 2 .

(Existence of Neighboring Edges on the Pareto Front of ${\mathbb{J}}$)
Suppose ${\mathbb{J}}$ contains multiple Pareto optimal vertices. Let $J^{\pi_{1}}$ be a Pareto optimal vertex on ${\mathbb{J}}$. Let $J_{N}(\pi_{1},{\mathbb{J}})=\{J^{\pi}\mid\pi\in\Pi_{N}(\pi_{1},{\mathbb{J}})\}$ represent all neighboring vertices of $J^{\pi_{1}}$ on ${\mathbb{J}}$. Then, there exists at least one neighboring vertex $J\in J_{N}(\pi_{1},{\mathbb{J}})$ such that the edge connecting $J$ and $J^{\pi_{1}}$ lies on the Pareto front.

###### Lemma 2 .

#### Proof Sketch

We prove Lemma 2 by contradiction. Assume there exists a vertex on the convex polytope ${\mathbb{J}}$ that is not connected by an edge lying on the Pareto front. In this case, we show that this vertex would dominate all other points on the polytope, implying that it is the only Pareto optimal point, which leads to a contradiction. Therefore, if the Pareto front contains more than one deterministic Pareto optimal policy, the vertex must be connected to at least one edge on the Pareto front. This completes the proof.

Lemma 2 only shows that a Pareto optimal vertex is connected to an edge (1-dimensional) on the Pareto front. However, it does not guarantee that one of the neighboring facets of a Pareto optimal vertex must also lie on the Pareto front.
A facet of ${\mathbb{J}}$ lies on the Pareto front only if its normal vector is strictly positive (which will be shown later in Lemma 3), meaning that all points on the facet are not dominated by any other points in ${\mathbb{J}}$. However, the normal vectors of all facets intersecting at a Pareto optimal vertex are not necessarily strictly positive.
This observation is consistent with Fig. 3, where point A is a Pareto optimal vertex, but it only lies on a Pareto optimal edge AB, and all its incident faces are not Pareto optimal.
This also justifies that constructing the Pareto front in a 2D case (with two reward objectives) is relatively simple, as we only need to connect the neighbor vertices. However, in higher dimensions, the Pareto front becomes more complex, and it is impossible to build the Pareto front purely from vertices.

### 4.3 Locality Property of the Pareto front

Previous theoretical results show that it is possible to traverse the Pareto front through edges constructed by deterministic policies that differ by only one state-action pair. However, each policy has $S\times(A-1)$ neighboring policies, and the challenge lies in efficiently selecting the Pareto optimal policies among them and constructing the Pareto front based on these neighbors.

This section provides the theoretical foundations for retrieving the boundary of ${\mathbb{J}}$ from the convex hull constructed by a vertex and the neighboring policies that differ by only one state-action pair. Furthermore, we show that the Pareto front can be retrieved by (1) constructing the convex hull using the vertex and locally non-dominated policies, and (2) applying Lemma 3 to extract all Pareto optimal faces from the convex hull.

Let deterministic policy $\pi$ correspond to a vertex on ${\mathbb{J}}$.
We denote the set of neighbors on the boundary of ${\mathbb{J}}$ to $J^{\pi}$ as $\mathrm{N}(J^{\pi},{\mathbb{J}})$, and the set of deterministic policies whose long-term returns make up $\mathrm{N}(J^{\pi},{\mathbb{J}})$ as $\mathrm{N}_{\pi}(J^{\pi},{\mathbb{J}})$.
Let ${\mathbb{F}}(J^{\pi},{\mathbb{J}})$ and ${\mathbb{F}}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\})$ be the set of incident faces of $J^{\pi}$ on ${\mathbb{J}}$ and $\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}$, respectively.

###### Theorem 2 .

The neighboring vertices and faces of $J^{\pi}$ on the convex hull $\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\})$ are the same as those on ${\mathbb{J}}$. Formally, $\mathrm{N}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))=\mathrm{N}(J^{
\pi},{\mathbb{J}})$, $\mathrm{N}_{\pi}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))=\mathrm{N}
_{\pi}(J^{\pi},{\mathbb{J}})$, and ${\mathbb{F}}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{\{J^{\pi}\}))={\mathbb{F}}
(J^{\pi},{\mathbb{J}})$.

This theorem guarantees that we can find all neighboring vertices and faces on the boundary of ${\mathbb{J}}$ from the local convex hull $\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\})$. By iterating through the process of constructing the convex hull of all distance-one policies and retaining the neighboring faces, we can eventually traverse the entire boundary of ${\mathbb{J}}$.

We also establish key properties of the Pareto front on a convex polytope.

###### Lemma 3 .

Given a convex polytope ${\mathbb{C}}$, let $F$ be face of ${\mathbb{C}}$ defined as the intersection of $n$ facets, i.e., $F=\cap_{i=1}^{n}F_{i}$, where $n\geq 1$ and each facet is of the form $F_{i}={\mathbb{C}}\cap\{{\bm{x}}\in\mathbb{R}^{d}:{\bm{w}}_{i}^{\top}{\bm{x}}=
c_{i}\}$. Then the face $F$ lies on the Pareto front of ${\mathbb{C}}$ if there exists a linear combination of the normal vectors, weighted by $\boldsymbol{\alpha}_{i}\geq 0$ for any $i\in\{1,\cdots,n\}$, such that $\sum_{i}\boldsymbol{\alpha}_{i}[{\bm{w}}_{i}]_{j}>0$ where $[{\bm{w}}_{i}]_{j}$ is the $j$-th component of ${\bm{w}}_{i}$.

Based on Lemma 3, we can also extract the Pareto optimal faces from the local convex hull. Let ${\mathbb{F}}(J^{\pi},\mathbb{P}({\mathbb{J}}))$ be the set of incident faces of $J^{\pi}$ on the Pareto front $\mathbb{P}({\mathbb{J}})$.

###### Proposition 1 .

Let ${\mathbb{F}}_{P}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$ denote the incident faces of $J^{\pi}$ on the convex hull $\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\})$ that satisfy the conditions of Lemma 3. Then,

$$ ${\mathbb{F}}(J^{\pi},\mathbb{P}({\mathbb{J}}))={\mathbb{F}}_{P}(J^{\pi}, \mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\})).$ $$

This proposition demonstrates that the faces of the Pareto front that intersect with a vertex are equivalent to the Pareto optimal faces of the local convex hull constructed by the vertex and its neighboring vertices.
Therefore, we conclude that all faces of the Pareto front that intersect with a vertex can be identified by computing the convex hull of neighboring non-dominated policies and then applying the Pareto front criterion in Lemma 3, which corresponds to Eq. 1, to extract the Pareto optimal faces from the local convex hull.

###### Theorem 2 .

###### Lemma 3 .

###### Proposition 1 .

## 5 Algorithm Evaluation

In this section, we empirically evaluate the performance of our algorithm in discovering the full Pareto front, including the vertices that correspond to deterministic Pareto optimal policies in MO-MDPs. To the best of our knowledge, this is the first method capable of precisely identifying the complete Pareto front without traversing the preference vector space. We start with giving an example where the shape of the Pareto front necessitates identifying the entire front, rather than focusing solely on deterministic policies. Then we compare our algorithm with existing methods in terms of efficiency in finding both the full Pareto front and the set of deterministic Pareto optimal policies.

We demonstrate a Pareto front structure that is not immediately evident from the vertices alone even in a simple setting. We consider a basic MDP setting, where we only have $4$ states and $3$ actions, and the reward dimension is $3$.
As illustrated in Fig. 6, the Pareto front is more complex than simply being the convex hull of its vertices.
For instance, A is a point on the Pareto front, but none of its incident facets are on the Pareto front. To find an edge connecting A to another policy on the Pareto front, we must further examine which edge that connects point A and other points corresponding to deterministic Pareto optimal policies is also on the Pareto front by Lemma 3. This edge is difficult to derive using only the knowledge of deterministic policies on the Pareto front.

### 5.1 Ability and Efficiency in Finding the Pareto Front

As the Pareto front searching algorithm is the first to recover the entire precise Pareto front, we provide a benchmark algorithm for comparison to demonstrate both the ability and efficiency of our method in identifying all faces of the true Pareto front.
The benchmark algorithm retrieves the Pareto front in two steps: (1) computing the convex hull of all non-dominated deterministic policies and (2) applying Algorithm 2 to identify the Pareto front.

Since the number of deterministic policies increases exponentially with the number of states, and the complexity of calculating the convex hull is proportional to the number of input points [], the benchmark algorithm’s complexity grows exponentially with the number of actions. Therefore, we compare the performance of our algorithm against the benchmark in small MDP settings.
Specifically, we consider state spaces of size $5$ and $8$, action spaces ranging from $5$ to $7$, and a reward dimension of $3$.
Our algorithm successfully identifies all faces of the true Pareto front in all cases.
As shown in Fig. 6, the runtime of the benchmark algorithm increases exponentially with the number of actions, making it impractical even in moderately sized action spaces. In contrast, our algorithm maintains a controllable runtime by efficiently traversing edges on the Pareto front to identify the Pareto faces.

### 5.2 Efficiency in Finding the Pareto Front Vertices

We compare the efficiency of finding all vertices on the Pareto front (i.e., deterministic Pareto optimal policies) with OLS [].
Let $N$ denote the number of vertices on the Pareto front.

OLS iteratively calculates a new preference vector and solves the single-objective MDP using this updated preference vector. The complexity of calculating the new preference vector involves comparisons with all previously effective preference vectors to discard obsolete ones, resulting in a complexity of $\mathcal{O}(N^{2}D+NC_{\text{we}})$. Additionally, solving the single-objective planning problem in each iteration incurs a complexity of $\mathcal{O}(N(C_{\text{so}}+C_{\text{pe}}))$, where $C_{\text{we}}$, $C_{\text{so}}$, and $C_{\text{pe}}$ represent the complexity of computing the new preference vectors, solving the single-objective MDP, and policy evaluation, respectively. Since planning is significantly more computationally expensive than evaluation, and OLS requires planning in each iteration, this leads to a high overall complexity.

In contrast, our algorithm requires only a one-time single-objective planning step during the initialization phase to obtain the initial deterministic Pareto-optimal policy. As our algorithm directly searches the Pareto front, the total number of iterations corresponds to the number of vertices on the Pareto front, avoiding the quadratic complexity introduced by the preference vector updates in OLS. The overall complexity of our algorithm is $\mathcal{O}(C_{\text{so}}+N(S(A-1)C_{\text{pe}}+C_{\text{ND}}+C_{\text{cvx}}))$, where $C_{\text{ND}}$ refers to the complexity of finding $\Pi_{1,\text{ND}}$, the set of non-dominated policies from $\Pi_{1}$, and $C_{\text{cvx}}$ is the complexity of computing the convex hull faces formed by $N_{\text{ND}}+1$ points that intersect at the current policy. Since the number of policies in $\Pi_{1,\text{ND}}$ is limited, the complexities $C_{\text{ND}}$ and $C_{\text{cvx}}$ are similarly constrained.

We compare the running time of our algorithm against OLS in terms of efficiency for finding all vertices on the Pareto front. Specifically, we consider scenarios where the state space size is $5$ and $8$, and the reward dimension is $4$. As shown in Fig. 6, while both OLS and the proposed algorithm efficiently find all vertices when the action and state space are small, the running time for OLS increases significantly with even slight expansions in the state and action space. In contrast, our proposed algorithm maintains a more manageable running time.

Figure: Figure 4: Pareto front of a simple MDP with $S=4$, $A=3$, and $D=3$.
Refer to caption: extracted/5941282/figs/paper_figs/special_cases/Pareto_front_S_4_A_3_seed_1_r_3.png

## 6 Conclusion and Future Directions

In this paper, we investigated the geometric properties of the set of long-term returns of all policies and the Pareto front in MO-MDPs. We proved a key property of the Pareto front in MO-MDPs that any neighboring deterministic policies on the Pareto front differ in exactly one state-action pair almost surely. This result eliminates the need for blind searches in the policy or feature space. Instead, we can traverse the Pareto front by iteratively searching for policies that differ from the current policy in only one state-action pair, significantly reducing the computational complexity.
Then, we demonstrated that the Pareto front is continuous in MO-MDP, enabling traversing the Pareto front by moving along edges.
Moreover, we showed that the faces intersecting at a vertex on the Pareto front can be recovered by the faces of the convex hull constructed by the vertex and all non-dominated deterministic policies that have only one state-action difference.
Building on these theoretical insights, we proposed an efficient Pareto front searching algorithm, which was validated through experiments. The algorithm effectively explores the Pareto front by leveraging the structure of the deterministic policies.

For future work, we plan to explore the robustness of the proposed algorithm in scenarios where the MDP is not known in advance. In such cases, policy evaluation errors may cause deviations between the estimated Pareto front and the true Pareto front. Additionally, integrating modern reinforcement learning algorithms could lead to more efficient approaches for handling large-scale problems.

## Appendix A Discussion on Pareto optimality

We define the Pareto optimal policy set based on an initial state distribution $\mu$. Unlike single-objective reinforcement learning (RL), where the optimal policy maximizes the long-term return for all states under any initial state distribution, Pareto optimality with respect to a specific initial state distribution $\mu$ does not ensure Pareto optimality across all states []. [] introduces the concept of aggregate Pareto efficiency, where a policy $\pi$ is considered aggregate Pareto optimal if there exists no policy $\pi^{\prime}$ such that ${\mathbf{V}}^{\pi^{\prime}}\succ{\mathbf{V}}^{\pi}$. The Pareto front $\mathbb{P}(\Pi)$ defined in Section 3.2 only forms a subset of the aggregate Pareto optimal set, as some policies may perform better than any other policies in a single objective for specific states, even though they are dominated when states are weighted by $\mu$.

We focus on the definition of Pareto optimality over a given state distribution for two key reasons:

- 1.
Relevance to Practical Applications: In real-world applications, the starting state often follows a specific distribution. For example, in RLHF applications in Large Language Models (LLM), input texts typically follow a certain distribution. Thus, it is unnecessary to optimize for Pareto efficiency over every individual state and objective, as this would not align with the natural distribution of inputs in such settings.
- 2.
Convergence to Aggregate Pareto Optimality: As the discount factor $\gamma\rightarrow 1$, $\mathbb{P}(\Pi)$ approaches the aggregate Pareto optimal set []. Therefore, in settings with a high discount factor, focusing on $\mathbb{P}(\Pi)$ provides a close approximation to the aggregate Pareto optimal set.

## Appendix B Notations

Let ${\mathbf{I}}_{M}$ denote the identity matrix of size $M$, ${\bm{1}}_{M}$ denote the $M$-dimensional vector where all elements are $1$, and ${\bm{0}}_{M\times N}$ denote a zero matrix with dimensions $M\times N$.
Let ${\mathbf{A}}^{\top}$ denote the transpose of the matrix ${\mathbf{A}}$.
Let ${\mathbf{A}}>(\geq){\mathbf{B}}$ denote that each element of ${\mathbf{A}}$ is strictly greater than (or greater than or equal to) the corresponding element of ${\mathbf{B}}$.
Given an MDP $(\mathcal{S},\mathcal{A},{\mathbf{P}},{\bm{r}},\gamma)$, for any policy $\pi$, define the state transition probability matrix ${\mathbf{P}}^{\pi}$ and the expected reward vector ${\bm{r}}^{\pi}$ as:

$$ ${\mathbf{P}}^{\pi}(s,s^{\prime})\coloneqq\sum_{a\in\mathcal{A}}{\mathbf{P}}(s^ {\prime}|s,a)\pi(a|s),\quad{\bm{r}}^{\pi}(s)\coloneqq\sum_{a\in\mathcal{A}}{ \bm{r}}(s,a)\pi(a|s).$ $$

We provide the notation table as follows.

**Table 1: Notation table**
| Notation | Description |
| --- | --- |
| $\Pi$ | Set of stationary policies |
| $\Pi_{D}$ | Set of deterministic stationary policies |
| $J^{\pi}(\mu)$ | Long-term return of policy $\pi$ given initial state distribution $\mu$ |
| $J^{U}(\mu)$ | Set of long-term returns of all stationary policies in $U$ with initial distribution $\mu$ |
| ${\mathbb{J}}(\mu)$ | Set of long-term returns of all stationary policies with initial distribution $\mu$ |
| $\mathbb{P}({\mathbb{S}})$ | Pareto front of the set ${\mathbb{S}}$ |
| ${\mathbb{V}}({\mathbb{C}})$ | Set of vertices of the polytope ${\mathbb{C}}$ |
| ${\mathbb{B}}({\mathbb{C}})$ | Boundary of the polytope ${\mathbb{C}}$ |
| $\mathbb{P}(\Pi)$ | Set of Pareto optimal policies $\{\pi\in\Pi\mid J^{\pi}\in\mathbb{P}({\mathbb{J}}(\mu))\}$ |
| $\mathrm{Conv}({\mathbb{S}})$ | Convex hull of the set ${\mathbb{S}}$ |
| $\mathrm{N}({\bm{x}},{\mathbb{C}})$ | Set of neighboring vertices of vertex ${\bm{x}}$ on ${\mathbb{C}}$ |
| ${\mathbb{F}}({\bm{x}},{\mathbb{C}})$ | Set of incident faces of vertex ${\bm{x}}$ on ${\mathbb{C}}$ |
| $\Pi_{1}(\pi)$ | Set of deterministic policies differing from $\pi$ by exactly one state-action pair |
| $\Pi_{1,\text{ND}}(\pi)$ | Set of non-dominated policies among $\Pi_{1}(\pi)$ |
| $\Pi_{N}(\pi,{\mathcal{M}})$ | Set of deterministic policies that differ from $\pi$ at all states in ${\mathcal{M}}$ and matching $\pi$ at all other states |

## Appendix C Supporting Lemmas and Theorems

In this section, for the sake of completeness in the paper, we present some well-known lemmas and theorems, along with a few easily proven lemmas, which will be used in the subsequent proofs.

We begin by presenting some well-known theorems and lemmas in the field of linear algebra.

###### Theorem 3 .

(Rank-nullity theorem)
Let ${\mathbf{A}}$ be an $m\times n$ matrix. Then, the following relationship holds: $\mathrm{rank}({\mathbf{A}})+\dim(\mathrm{null}({\mathbf{A}}))=n$, where $\mathrm{rank}({\mathbf{A}})$ is the dimension of the column space of ${\mathbf{A}}$, and $\mathrm{null}({\mathbf{A}})$ is the null space of ${\mathbf{A}}$.

###### Lemma 4 .

Let ${\mathbf{A}}$ be an $m\times n$ matrix and ${\bm{b}}\neq{\bm{0}}$ be an $m$-dimensional vector.
If ${\mathbf{A}}{\bm{x}}={\bm{b}}$ has at least one solution, then the dimension of the solution space of ${\mathbf{A}}{\bm{x}}={\bm{b}}$ is equal to $\dim(\mathrm{null}({\mathbf{A}}))$, where $\mathrm{null}({\mathbf{A}})$ is the null space of ${\mathbf{A}}$.

###### Lemma 5 .

Let ${\mathbf{A}}$ be an $m\times n$ matrix with full column rank. If ${\mathbf{A}}{\mathbf{B}}=k{\mathbf{A}}{\mathbf{C}}$, then ${\mathbf{B}}=k{\mathbf{C}}$.

###### Proof.

From ${\mathbf{A}}{\mathbf{B}}=k{\mathbf{A}}{\mathbf{C}}$, we can subtract $k{\mathbf{A}}{\mathbf{C}}$ from both sides to get ${\mathbf{A}}({\mathbf{B}}-k{\mathbf{C}})={\bm{0}}_{m}$.
Since ${\mathbf{A}}$ has full column rank, it follows from Theorem 3 that the dimension of its null space must be zero, and the only solution is ${\mathbf{A}}{\bm{x}}={\bm{0}}_{m}$ is ${\bm{x}}={\bm{0}}_{n}$.
Therefore, the only solution to ${\mathbf{A}}({\mathbf{B}}-k{\mathbf{C}})={\bm{0}}_{m}$ is ${\mathbf{B}}-k{\mathbf{C}}={\bm{0}}_{n}$.
Hence, ${\mathbf{B}}=k{\mathbf{C}}$.
∎

###### Lemma 6 .

[]
Let ${\mathbf{A}}\in\mathbb{R}^{n\times n}$ be a square matrix. The maximum absolute value of the eigenvalues of ${\mathbf{A}}$, denoted as $\rho({\mathbf{A}})$, satisfies the following inequality:

$$ $\rho({\mathbf{A}})\leq\|{\mathbf{A}}\|_{\infty},$ $$

where $\|{\mathbf{A}}\|_{\infty}=\max_{1\leq i\leq n}\sum_{j=1}^{n}|A_{ij}|.$ is the infinity norm of the matrix ${\mathbf{A}}$.

Then we present some lemmas related to the multi-objective optimization.

###### Lemma 7 .

[]
Let ${\mathbb{S}}$ denote the set of achievable objective values and let ${\mathbb{P}}({\mathbb{S}})$ denote the set of Pareto optimal values in ${\mathbb{C}}$. Then ${\mathbb{P}}({\mathbb{S}})\subseteq{\mathbb{B}}({\mathbb{S}})$, i.e., every Pareto optimal value lies in the boundary of the set of achievable objective values.

###### Lemma 8 .

Let ${\bm{x}}$ be a point in a set ${\mathbb{S}}$. If there exists a vector ${\bm{w}}>0$ such that ${\bm{w}}^{\top}({\bm{x}}-{\bm{y}})\geq 0$ for all ${\bm{y}}\in{\mathbb{S}}$, then ${\bm{x}}$ lies on the Pareto front of ${\mathbb{S}}$.

###### Proof.

Assume, for the sake of contradiction, that ${\bm{x}}$ is not on the Pareto front of ${\mathbb{S}}$. This means there exists a point ${\bm{y}}\in{\mathbb{S}}$ that strictly dominates ${\bm{x}}$, i.e., ${\bm{y}}\succ{\bm{x}}$.
This implies that ${\bm{y}}$ is at least as large as the corresponding objective of ${\bm{x}}$ and ${\bm{y}}$ is strictly better than ${\bm{x}}$ in at least one objective.
Therefore, given ${\bm{w}}>0$, we have ${\bm{w}}^{\top}({\bm{x}}-{\bm{y}})<0$.
However, this contradicts the assumption that ${\bm{w}}^{\top}({\bm{x}}-{\bm{y}})\geq 0$ for all ${\bm{y}}\in{\mathbb{S}}$. Thus, no point in ${\mathbb{S}}$ strictly dominates ${\bm{x}}$, which implies that ${\bm{x}}$ is on the Pareto front.
∎

Next, we restate some definitions in the main body of the paper and present several lemmas related to polytopes.

###### Definition 1 .

[]
Let ${\mathbb{C}}\subseteq\mathbb{R}^{d}$ be a convex polytope. A linear inequality
${\bm{w}}^{\top}x\leq c_{0}$ is valid for ${\mathbb{C}}$ if it is satisfied for all points $x\in{\mathbb{C}}$. A face of ${\mathbb{C}}$
is any set of the form ${\mathbb{F}}={\mathbb{C}}\cap\{x\in\mathbb{R}^{d}:{\bm{w}}^{\top}x=c_{0}\}$
where ${\bm{w}}^{\top}{\bm{x}}\leq c_{0}$ is a valid inequality for ${\mathbb{C}}$. The dimension of a face is the dimension of its affine hull, i.e., $\dim(F):=\dim(\text{aff}(F)).$
The faces of dimension smaller than $\dim({\mathbb{C}})$ are called proper faces.
The faces of 0 0, $1$, $\dim({\mathbb{C}})-2$, $\dim({\mathbb{C}})-1$ are called vertices, edges, ridges, and facets, respectively.

###### Lemma 9 .

[]
Every nonempty proper face of a convex polytope ${\mathbb{C}}$ is an intersection of facets of ${\mathbb{C}}$.

Finally, we give some lemmas related to MDP.

###### Lemma 10 .

[]
The occupancy measure of any policy $\pi$ and initial distribution $\mu$ is defined as $d_{\mu}^{\pi}(s)\coloneqq(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}P(s_{t}=s|s_{0
}\sim\mu(\cdot))$. Similarly, define $\bar{d}_{\mu}^{\pi}(s,a)\coloneqq(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}P(s_{t
}=s,a_{t}=a|s_{0}\sim\mu(\cdot))=d_{\mu}^{\pi}(s)\pi(a|s)$.
Define for any set of policies $U$, $L^{U}(\mu)\coloneqq\cup_{\pi\in U}\bar{d}_{\mu}^{\pi}$ and define $L(\mu)\coloneqq\cup_{\pi\in\Pi}\bar{d}_{\mu}^{\pi}$.
Then, $L(\mu)$ is closed convex polytope and $L(\mu)=\mathrm{Conv}(L{\Pi_{D}}(\mu))$.

###### Lemma 11 .

[]
Given MDP $(\mathcal{S},\mathcal{A},{\mathbf{P}},{\bm{r}},\gamma)$, there exists at least one policy that is always better than or equal to all other policies in all states, denoted as optimal policy. The optimal policy $\pi^{*}$ satisfies $\pi^{*}(s)=\arg\max_{a\in\mathcal{A}}Q^{*}(s,a)$, where $Q^{*}(s,a)$ is the solution to the Bellman optimality equation $Q^{*}(s,a)=\mathbb{E}\left[{\bm{r}}(s,a)+\gamma\max_{a^{\prime}}Q^{*}(s^{
\prime},a^{\prime})\mid s,a\right]$.

###### Lemma 12 .

If there exists $\mu$ where $\mu(s)>0$ for any $s\in\mathcal{S}$ such that a deterministic policy $\pi^{*}$ maximizes for $J^{\pi^{*}}(\mu)=\mu^{\top}{\mathbf{V}}^{\pi^{*}}$, then $\pi^{*}$ is the optimal policy, i.e., ${\mathbf{V}}^{\pi^{*}}(s)=\max_{\pi}{\mathbf{V}}^{\pi}(s)$ for any $s$.

###### Proof.

We prove this by contradiction. If $\pi^{*}$ is not the optimal policy, and there exists optimal policy $u\neq\pi^{*}$ such that $V^{\pi^{*}}(s)\leq V^{u}(s)$ for any $s\in\mathcal{S}$, and on at least one state $V^{\pi^{*}}(s)<V^{u}(s)$. Then $J^{u}(\mu)>J^{\pi^{*}}(\mu)$ since $\mu(s)>0$ for any $s$. This contradicts the condition that $\pi^{*}$ maximizes for $J^{\pi}(\mu)$.
So $\pi^{*}$ is also an optimal policy.
∎

###### Lemma 13 .

Given a single-objective MDP $(\mathcal{S},\mathcal{A},{\mathbf{P}},r,\gamma)$. If $\Pi^{*}$ is the set of the optimal deterministic policies, then the set of all optimal policies (including stochastic and deterministic policies) is the convex hull constructed by $\Pi^{*}$.

###### Proof.

We first show that all policies in the convex hull constructed by the set of optimal deterministic policies $\Pi^{*}$ are optimal policies.
By Lemma 11, the optimal policies share the same state-action value function, that is, $Q^{\pi_{i}}(s,a)=Q^{\pi_{j}}(s,a)=Q^{*}(s,a)$ for any $\pi_{i},\pi_{j}\in\Pi^{*}$. Since $\pi_{i}\in\Pi^{*}$ are deterministic policies, with a little abuse notation of $\pi$, we have $\pi_{i}(s)=\arg_{a\in\mathcal{A}}\max Q^{*}(s,a)$ for any $i$. Let $\boldsymbol{\alpha}$ be a $(|\Pi|-1)$-dimension standard simplex.
Let $\pi$ be the convex combination of $\Pi^{*}$, that is, $\pi(a|s)=\sum_{i}\boldsymbol{\alpha}_{i}\pi_{i}(a|s)$ for any $s$.
As each possible choice of $\pi$ at state $s$ maximizes $Q^{*}(s,a)$, i.e., $\pi_{i}(\arg_{a\in\mathcal{A}}\max Q^{*}(s,a)|s)=1$, $\pi$ at state $s$ maximizes $Q^{*}(s,a)$ and $\pi$ is an optimal policy. Hence any convex combination $\pi$ optimal deterministic policies are also optimal.

Then we want to show for any policies not on the convex hull the set of optimal deterministic policies $\Pi$, it cannot be the optimal policy.
We prove this by contradiction. Suppose an optimal policy $\pi$ is not on the convex hull by all deterministic policies. In that case, it is written as $\pi=\sum_{i,\pi_{i}\in\Pi^{*}}\alpha_{i}\pi_{i}+\sum_{j,\pi_{j}\in\bar{\Pi}}
\beta_{j}\pi_{j}$, where $\sum_{i}\alpha_{i}+\sum_{i}\beta_{j}=1$, $\alpha_{i}\geq 0$, $\beta_{j}\geq 0$, and $\bar{\Pi}$ is a set of non-optimal deterministic policies. Suppose on state $s$ such that $V^{\pi_{j}}(s)\leq V^{*}(s)$, then $\pi(s)\neq\arg\max^{\pi}Q^{*}(s,a)$, which indicates $\pi$ is no longer an optimal policy. This contradicts the assumption that $\pi$ is an optimal policy.
∎

###### Lemma 14 .

Given an MDP $(\mathcal{S},\mathcal{A},{\bm{P}},{\bm{r}},\gamma)$ and a deterministic policy $\pi:\mathcal{S}\rightarrow\mathcal{A}$, let $\pi\in\Pi_{N}(\pi_{1},{\mathcal{M}})$. The transition matrix ${\mathbf{P}}^{\pi}$ and reward vector ${\bm{r}}^{\pi}$ can be decomposed into block matrices as follows:

$$ ${\mathbf{P}}^{\pi}=\begin{bmatrix}{\mathbf{A}}&{\mathbf{B}}\\ {\mathbf{C}}^{\pi}&{\mathbf{D}}^{\pi}\end{bmatrix},\quad{\bm{r}}^{\pi}=\begin{ bmatrix}\bm{X}\\ \bm{Y}^{\pi}\end{bmatrix}.$ $$

Following the definitions of $\Gamma$ and ${\mathbf{V}}$ in Eq. 8 we have

$$ $\Gamma^{\pi}=\begin{bmatrix}\gamma({\mathbf{I}}_{S-M}-\gamma{\mathbf{A}})^{-1} {\mathbf{B}}\\ {\mathbf{I}}_{M}\end{bmatrix},\quad\tilde{{\mathbf{V}}}^{\pi}=\begin{bmatrix}( {\mathbf{I}}_{S-M}-\gamma{\mathbf{A}})^{-1}\bm{X}\\ {\bm{0}}_{M}\end{bmatrix}.$ $$

###### Proof.

Since the transition probabilities and rewards starting from $\mathcal{S}\setminus{\mathcal{M}}$ are the same for any $\pi\in\Pi_{N}(\pi_{1},{\mathcal{M}})$, we conclude that ${\mathbf{A}}$, ${\mathbf{B}}$, and $\bm{X}$ (the relevant blocks of ${\mathbf{P}}^{\pi}$ and ${\bm{r}}^{\pi}$) are independent of $\pi$. However, ${\mathbf{C}}^{\pi}$, ${\mathbf{D}}^{\pi}$, and $\bm{Y}^{\pi}$ vary with $\pi$, as indicated by the subscripts.

###### Theorem 3 .

###### Lemma 4 .

###### Lemma 5 .

###### Proof.

###### Lemma 6 .

###### Lemma 7 .

###### Lemma 8 .

###### Proof.

###### Definition 1 .

###### Lemma 9 .

###### Lemma 10 .

###### Lemma 11 .

###### Lemma 12 .

###### Proof.

###### Lemma 13 .

###### Proof.

###### Lemma 14 .

###### Proof.

#### Analysis of Γ Γ \Gamma roman_Γ

We decompose $\Gamma^{\pi}$ into block matrix form, i.e., $\Gamma^{\pi}=\left[\left(\Gamma^{\pi}_{1}\right)^{\top},\left(\Gamma^{\pi}_{2}
\right)^{\top}\right]^{\top}$, where $\Gamma^{\pi}_{1}\in\mathbb{R}^{(S-M)\times M}$ and $\Gamma^{\pi}_{2}\in\mathbb{R}^{M\times M}$.

The definition of ${\mathbf{H}}(\bar{s}_{i},{\mathcal{M}},\bar{s}_{j})$ that for any $\bar{s}_{i},\bar{s}_{j}\in{\mathcal{M}}$ with $i\neq j$ shows that ${\mathbf{H}}(\bar{s}_{i},\bar{s}_{i})=0$ with probability $1$ and ${\mathbf{H}}(\bar{s}_{i},\bar{s}_{j})=\infty$ with probability $1$.
Thus,

$$ $[\Gamma^{\pi}_{2}]_{i,j}=\mathbb{E}\left[\gamma^{{\mathbf{H}}(\bar{s}_{i},\bar {s}_{j})}\right]=0\quad\text{for }i\neq j,\quad\text{and}\quad[\Gamma_{2}]_{i, i}=\mathbb{E}\left[\gamma^{{\mathbf{H}}(\bar{s}_{i},\bar{s}_{i})}\right]=1.$ $$

For $\Gamma^{\pi}_{1}$, starting from $s_{i}\in\mathcal{S}\setminus{\mathcal{M}}$, the probability of reaching $\bar{s}_{j}\in{\mathcal{M}}$ in one step is ${\mathbf{B}}_{i,j}$. The probability of reaching $\bar{s}_{j}$ in two steps is ${\mathbf{A}}_{i,:}{\bm{1}}_{S-M}$. Repeating this reasoning for subsequent steps, we obtain:

$$ $\displaystyle\left[\Gamma^{\pi}_{1}\right]_{i,j}=$ $\displaystyle P(S^{\pi}(s_{i},{\mathcal{M}})=\bar{s}_{j})\mathbb{E}\left[ \mathbb{E}\left[\gamma^{{\mathbf{H}}(s_{i},\bar{s}_{j})}\right]\middle|S^{\pi} (s_{i},{\mathcal{M}})=\bar{s}_{j}\right]$ $\displaystyle=$ $\displaystyle\gamma{\mathbf{B}}_{i,j}+\gamma^{2}{\mathbf{A}}_{i,:}{\mathbf{B}} _{:,j}+\gamma^{3}{\mathbf{A}}_{i,:}{\mathbf{A}}{\mathbf{B}}_{:,j}+\cdots$ $$

Since $\|\gamma\mathbf{A}\|_{\infty}<1$, it follows from Lemma 6 that the eigenvalues of $\gamma\mathbf{A}$ are smaller than 1. Therefore, $\mathbf{I}_{S-M}-\gamma\mathbf{A}$ does not have any zero eigenvalues, implying that it is invertible.
Summing over all steps, we have:

$$ $\Gamma^{\pi}_{1}=\gamma\sum_{n=0}^{\infty}(\gamma{\mathbf{A}})^{n}{\mathbf{B}} =\gamma({\mathbf{I}}_{S-M}-\gamma{\mathbf{A}})^{-1}{\mathbf{B}}.$ $$

Thus, we conclude:

$$ $\Gamma^{\pi}=\begin{bmatrix}\Gamma^{\pi}_{1}\\ \Gamma^{\pi}_{2}\end{bmatrix}=\begin{bmatrix}\gamma({\mathbf{I}}_{S-M}-\gamma{ \mathbf{A}})^{-1}{\mathbf{B}}\\ {\mathbf{I}}_{M}\end{bmatrix}.$ $$

#### Analysis of 𝐕 𝐕 {\mathbf{V}} bold_V

Similarly, we decompose ${\mathbf{V}}$ into block matrix form: $\tilde{{\mathbf{V}}}^{\pi}=\left[\left(\tilde{{\mathbf{V}}}_{1}^{\pi}\right)^{
\top},\left(\tilde{{\mathbf{V}}}_{2}^{\pi}\right)^{\top}\right]^{\top}$, where $\tilde{{\mathbf{V}}}^{\pi}_{1}\in\mathbb{R}^{(S-M)\times D}$ and $\tilde{{\mathbf{V}}}^{\pi}_{2}\in\mathbb{R}^{M\times D}$.

For $\tilde{{\mathbf{V}}}^{\pi}_{2}$, starting from any $\bar{s}\in{\mathcal{M}}$, we reach ${\mathcal{M}}$ with probability 1 in zero steps, so the total reward is 0. Thus, $\tilde{{\mathbf{V}}}^{\pi}_{2}={\bm{0}}_{M\times M}$.

Starting from state $s_{i}\in\mathcal{S}\setminus{\mathcal{M}}$, it has immediate reward $[{\mathbf{X}}]_{(i,\cdot)}$. For the next state, it has probability $[{\mathbf{A}}]_{i,j}$ to move to state $s_{j}\in S\setminus{\mathcal{M}}$, and it has probability $\sum_{j}[{\mathbf{B}}]_{i,j}$ to move to $\bar{s}_{j}\in{\mathcal{M}}$ which terminates the process with future return 0. Therefore, we can write the Bellman equation-like form:

$$ $\displaystyle\tilde{{\mathbf{V}}}^{\pi}_{1}=$ $\displaystyle\bm{X}+\gamma{\mathbf{A}}\tilde{{\mathbf{V}}}^{\pi}_{1}+\gamma{ \mathbf{B}}{\bm{0}}_{(S-M)\times D}$ $\displaystyle=$ $\displaystyle\bm{X}+\gamma{\mathbf{A}}\tilde{{\mathbf{V}}}^{\pi}_{1}.$ $$

Solving this equation gives:

$$ $\tilde{{\mathbf{V}}}^{\pi}_{1}=({\mathbf{I}}_{S-M}-\gamma{\mathbf{A}})^{-1}\bm {X}.$ $$

Hence, we conclude:

$$ $\tilde{{\mathbf{V}}}^{\pi}=\begin{bmatrix}\tilde{{\mathbf{V}}}^{\pi}_{1}\\ \tilde{{\mathbf{V}}}^{\pi}_{2}\end{bmatrix}=\begin{bmatrix}({\mathbf{I}}_{S-M} -\gamma{\mathbf{A}})^{-1}\bm{X}\\ {\bm{0}}_{M}\end{bmatrix}.$ $$

∎

###### Lemma 15 .

(Properties of ${\mathbf{F}}^{\pi}$ and ${\mathbf{E}}^{\pi}$)
The functions ${\mathbf{F}}^{\pi}$ and ${\mathbf{E}}^{\pi}$, defined in Eq. 11, can be expressed as follows:

$$ $\displaystyle{\mathbf{F}}^{\pi}$ $\displaystyle\coloneqq\gamma{\mathbf{P}}^{\pi}({\mathcal{M}})\Gamma,$ $\displaystyle{\mathbf{E}}^{\pi}$ $\displaystyle\coloneqq\mathbf{r}^{\pi}({\mathcal{M}})+\gamma{\mathbf{P}}^{\pi} ({\mathcal{M}})\tilde{{\mathbf{V}}},$ $$

where $\Gamma$ and $\tilde{{\mathbf{V}}}$ are predefined matrices given in Lemma 14, ${\mathcal{M}}$ is a subset of states, and ${\mathbf{P}}^{\pi}({\mathcal{M}})$ is the transition probability matrix under policy $\pi$ restricted to the subset ${\mathcal{M}}$.

We can derive the following properties:

- 1.
Gradients of ${\mathbf{F}}^{\pi}$ and ${\mathbf{E}}^{\pi}$ with respect to $\pi$. For any $\bar{s}\in{\mathcal{M}}$ and $a\in\mathcal{A}$, the partial derivatives of ${\mathbf{F}}^{\pi}$ and ${\mathbf{E}}^{\pi}$ with respect to the policy $\pi$ are given by:
$\frac{\partial{\mathbf{F}}^{\pi}}{\partial\pi(\bar{s},a)}=\gamma{\mathbf{P}}(
\delta(\bar{s}),a,\cdot)\Gamma,\quad\frac{\partial{\mathbf{E}}^{\pi}}{\partial
\pi(\bar{s},a)}=\mathbf{r}(\delta(\bar{s}),a,\cdot)+\gamma{\mathbf{P}}(\delta(
\bar{s}),a,\cdot)\tilde{{\mathbf{V}}},$
where $\delta(\bar{s})$ is a unit vector indicating the state $\bar{s}$, $Z={\mathbf{P}}(\delta(\bar{s}),a,\cdot)\in\mathbb{R}^{M\times S}$, with $Z(\bar{s},\cdot)={\mathbf{P}}(\bar{s},a,\cdot)$, and $Z(\bar{s}^{\prime},\cdot)=0$ for any $\bar{s}^{\prime}\neq\bar{s}$.
- 2.
Simplification when $\pi$ is a deterministic policy. If $\pi$ is a deterministic policy, then ${\mathbf{F}}^{\pi}$ and ${\mathbf{E}}^{\pi}$ can be simplified as follows:
$\displaystyle{\mathbf{F}}^{\pi}$
$\displaystyle=\sum_{\bar{s}\in{\mathcal{M}}}\gamma{\mathbf{P}}(\delta(\bar{s})
,\pi(\bar{s}),\cdot)\Gamma,$
$\displaystyle{\mathbf{E}}^{\pi}$
$\displaystyle=\sum_{\bar{s}\in{\mathcal{M}}}\left(\mathbf{r}(\delta(\bar{s}),
\pi(\bar{s}),\cdot)+\gamma{\mathbf{P}}(\delta(\bar{s}),\pi(\bar{s}),\cdot)
\tilde{{\mathbf{V}}}\right).$
- 3.
Given $\pi=\alpha\pi_{1}+(1-\alpha)\pi_{2}$, where $0\leq\alpha\leq 1$ to ensure $\pi$ is a valid policy, we have
$\displaystyle{\mathbf{F}}^{\pi}=$
$\displaystyle\alpha{\mathbf{F}}^{\pi_{1}}+(1-\alpha){\mathbf{F}}^{\pi_{2}},$
$\displaystyle{\mathbf{E}}^{\pi}=$
$\displaystyle\alpha{\mathbf{E}}^{\pi_{1}}+(1-\alpha){\mathbf{E}}^{\pi_{2}}.$

###### Proof.

(1) Recall that the state transition matrix and reward function under policy $\pi$ are defined as follows:

$$ ${\mathbf{P}}^{\pi}(s,s^{\prime})\coloneqq\sum_{a\in\mathcal{A}}{\mathbf{P}}(s, a,s^{\prime})\pi(s,a),\quad\mathbf{r}^{\pi}(s)=\sum_{a\in\mathcal{A}}\mathbf{r }(s,a)\pi(s,a),$ $$

where ${\mathbf{P}}(s,a,s^{\prime})$ is the probability of transitioning from state $s$ to state $s^{\prime}$ given action $a$, and $\mathbf{r}(s,a)$ is the reward for taking action $a$ in state $s$.

For any $\bar{s}\in{\mathcal{M}}$ and $a\in\mathcal{A}$, we compute the derivatives of ${\mathbf{P}}^{\pi}(s,s^{\prime})$ and $\mathbf{r}^{\pi}(s)$ with respect to the policy $\pi(\bar{s},a)$:

$$ $\frac{\partial{\mathbf{P}}^{\pi}(s,s^{\prime})}{\partial\pi(\bar{s},a)}={ \mathbf{P}}(s,a,s^{\prime})\delta(s=\bar{s}),\quad\frac{\partial\mathbf{r}^{ \pi}(s)}{\partial\pi(\bar{s},a)}=\mathbf{r}(s,a)\delta(s=\bar{s}),$ $$

where $\delta(s=\bar{s})$ is the Kronecker delta function, which is 1 if $s=\bar{s}$ and 0 otherwise.

Next, substituting these expressions into the derivatives of ${\mathbf{F}}^{\pi}$ and ${\mathbf{E}}^{\pi}$ with respect to $\pi(\bar{s},a)$, we obtain:

$$ $\displaystyle\frac{\partial{\mathbf{F}}^{\pi}}{\partial\pi(\bar{s},a)}$ $\displaystyle=\frac{\gamma\partial{\mathbf{P}}^{\pi}(s,s^{\prime})}{\partial \pi(\bar{s},a)}\Gamma=\gamma{\mathbf{P}}(\delta(\bar{s}),a,\cdot)\Gamma,$ $\displaystyle\frac{\partial{\mathbf{E}}^{\pi}}{\partial\pi(\bar{s},a)}$ $\displaystyle=\frac{\partial\mathbf{r}^{\pi}(s)}{\partial\pi(\bar{s},a)}+\frac {\partial\gamma{\mathbf{P}}^{\pi}(s,s^{\prime})}{\partial\pi(\bar{s},a)}\tilde {V}$ $\displaystyle=\mathbf{r}(\delta(\bar{s}),a)+\gamma{\mathbf{P}}(\delta(\bar{s}) ,a,\cdot)\tilde{V}.$ $$

(2) When $\pi$ is a deterministic policy, we recall that $\pi$ maps each state $s\in\mathcal{S}$ to a specific action $\pi(s)\in\mathcal{A}$. In this case, with a slight abuse of notation $\pi$, the transition matrix and reward function are simplified as follows:

$$ $\displaystyle{\mathbf{P}}^{\pi}(s,s^{\prime})$ $\displaystyle=\sum_{a\in\mathcal{A}}{\mathbf{P}}(s,a,s^{\prime})\pi(s,a)={ \mathbf{P}}(s,\pi(s),s^{\prime}),$ $\displaystyle\mathbf{r}^{\pi}(s)$ $\displaystyle=\sum_{a\in\mathcal{A}}\mathbf{r}(s,a)\pi(s,a)=\mathbf{r}(s,\pi(s )),$ $$

where the policy $\pi$ deterministically selects action $\pi(s)$ in each state $s$.

Substituting these expressions into the definitions of ${\mathbf{F}}^{\pi}$ and ${\mathbf{E}}^{\pi}$, we obtain the desired results:

$$ $\displaystyle{\mathbf{F}}^{\pi}$ $\displaystyle=\sum_{\bar{s}\in{\mathcal{M}}}\gamma{\mathbf{P}}(\delta(\bar{s}) ,\pi(\bar{s}),\cdot)\Gamma,$ $\displaystyle{\mathbf{E}}^{\pi}$ $\displaystyle=\sum_{\bar{s}\in{\mathcal{M}}}\left(\mathbf{r}(\delta(\bar{s}), \pi(\bar{s}))+\gamma{\mathbf{P}}(\delta(\bar{s}),\pi(\bar{s}),\cdot)\tilde{V} \right).$ $$

(3) Since the transition probability matrix and reward function under a mixed policy $\alpha\pi_{1}+(1-\alpha)\pi_{2}$ can be expressed as linear combinations of the respective components under policies $\pi_{1}$ and $\pi_{2}$, we have:

$$ ${\mathbf{P}}^{\alpha\pi_{1}+(1-\alpha)\pi_{2}}({\mathcal{M}})=\alpha{\mathbf{P }}^{\pi_{1}}({\mathcal{M}})+(1-\alpha){\mathbf{P}}^{\pi_{2}}({\mathcal{M}}),$ $$

and

$$ $\mathbf{r}^{\alpha\pi_{1}+(1-\alpha)\pi_{2}}({\mathcal{M}})=\alpha\mathbf{r}^{ \pi_{1}}({\mathcal{M}})+(1-\alpha)\mathbf{r}^{\pi_{2}}({\mathcal{M}}).$ $$

By applying these expressions in conjunction with the definitions of ${\mathbf{F}}^{\pi}$ and ${\mathbf{E}}^{\pi}$, the desired result follows.
∎

###### Lemma 15 .

###### Proof.

## Appendix D distance-1 property

Given initial state distribution $\mu>0$, recall the definition of ${\mathbb{J}}(\mu)=\{\pi\in\Pi|J^{\pi}(\mu)\}$ is all the achievable long-term returns for any policies belonging to $\Pi$ which can be non-stationary and stochastic policies, and the Pareto front of ${\mathbb{J}}(\mu)$ is denoted as $\mathbb{P}({\mathbb{J}}(\mu))$. Lemma 1 shows that the ${\mathbb{J}}(\mu)$ construct a convex polytope. The boundary and vertices of the convex polytope ${\mathbb{J}}(\mu)$ are denoted as ${\mathbb{B}}({\mathbb{J}}(\mu))$ and ${\mathbb{V}}({\mathbb{J}}(\mu))$, respectively. Lemma 1 also implies the vertices of ${\mathbb{J}}(\mu)$ are deterministic policies, that is, ${\mathbb{V}}({\mathbb{J}}(\mu))\subseteq\Pi_{D}$.

###### Lemma 16 .

(Restatement of Lemma 1)
${\mathbb{J}}(\mu)$ is closed convex polytope, and the vertices of ${\mathbb{J}}(\mu)$ can be achieved by deterministic policies.

###### Proof.

We observe that ${\mathbb{J}}(\mu)$ can be obtained by applying a linear transformation to $L(\mu)$, that is, ${\mathbb{J}}(\mu)=\{\left(\bar{d}_{\mu}^{\pi}\right)^{\top}{\bm{r}}|\bar{d}_{
\mu}^{\pi}\in L(\mu)\}$.

Then we prove the following lemma, which shows that linear transformations preserve the convex polytope structure and a subset of its vertices.

###### Lemma 17 .

Suppose ${\mathbb{C}}$ is a convex polytope in $n$-dimension space whose vertices set is ${\mathbb{V}}$, and ${\mathbf{A}}\in\mathbb{R}^{m\times n}$. Let $\bar{{\mathbb{C}}}=\{{\mathbf{A}}{\bm{x}}|{\bm{x}}\in{\mathbb{C}}\}$, then $\bar{{\mathbb{C}}}$ is also a convex polytope with vertices $\bar{{\mathbb{V}}}$, and $\bar{{\mathbb{V}}}\subseteq\{{\mathbf{A}}{\bm{v}}|{\bm{v}}\in{\mathbb{V}}\}$.

###### Proof.

Since ${\mathbb{C}}$ is a convex polytope, it is the convex hull of its finite vertex set ${\mathbb{V}}=\{{\bm{v}}_{1},{\bm{v}}_{2},\dots,{\bm{v}}_{k}\}$. That is, ${\mathbb{C}}=\mathrm{Conv}({\mathbb{V}})=\left\{\sum_{i=1}^{k}\boldsymbol{
\alpha}_{i}{\bm{v}}_{i}\ \middle|\ \boldsymbol{\alpha}_{i}\geq 0,\sum_{i=1}^{k
}\boldsymbol{\alpha}_{i}=1\right\}.$
Applying the linear map $\mathbf{A}$ to ${\mathbb{C}}$, we get:

$$ $\displaystyle\bar{{\mathbb{C}}}=$ $\displaystyle\mathbf{A}{\mathbb{C}}=\left\{\mathbf{A}\left(\sum_{i=1}^{k} \boldsymbol{\alpha}_{i}{\bm{v}}_{i}\right)\ \middle|\ \boldsymbol{\alpha}_{i} \geq 0,\sum_{i=1}^{k}\boldsymbol{\alpha}_{i}=1\right\}$ $\displaystyle=$ $\displaystyle\left\{\sum_{i=1}^{k}\boldsymbol{\alpha}_{i}(\mathbf{A}{\bm{v}}_{ i})\ \middle|\ \boldsymbol{\alpha}_{i}\geq 0,\sum_{i=1}^{k}\boldsymbol{\alpha} _{i}=1\right\}.$ $$

This shows that $\bar{{\mathbb{C}}}$ is the convex hull of the finite set $\{\mathbf{A}{\bm{v}}_{1},\mathbf{A}{\bm{v}}_{2},\dots,\mathbf{A}{\bm{v}}_{k}\}$, which implies that $\bar{{\mathbb{C}}}$ is a convex polytope, and the set of vertices $\bar{{\mathbb{V}}}$ is a subset of $\{{\mathbf{A}}{\bm{v}}|{\bm{v}}\in{\mathbb{V}}\}=\{\mathbf{A}{\bm{v}}_{1},
\mathbf{A}{\bm{v}}_{2},\dots,\mathbf{A}{\bm{v}}_{k}\}$.
∎

The conclusion can be obtained by combining Lemma 10 and Lemma 17.
∎

By the definition of the Pareto front, the Pareto front is the set of non-dominated policies on ${\mathbb{J}}(\mu)$. By Lemma 7, the Pareto front is on the boundary of the convex polytope.

We define two policies, $\pi_{1}$ and $\pi_{2}$, as neighboring policies if an edge on the boundary of the convex polytope ${\mathbb{B}}({\mathbb{J}}(\mu))$ connects the long-term returns of $\pi_{1}$ and $\pi_{2}$.

###### Lemma 18 .

For any edge on ${\mathbb{B}}({\mathbb{J}}(\mu))$ with endpoints denoted as $J^{\pi_{1}}(\mu)$ and $J^{\pi_{2}}(\mu)$, any point on this edge can only be achieved by the long-term return of a convex combination of policies $\pi_{1}$ and $\pi_{2}$. Specifically, for any $\alpha\in[0,1]$, there exists a $\beta\in[0,1]$ such that

$$ $\alpha J^{\pi_{1}}(\mu)+(1-\alpha)J^{\pi_{1}}(\mu)=J^{\beta\pi_{1}+(1-\beta) \pi_{2}}(\mu).$ $$

###### Proof.

Let $\pi_{1}$ and $\pi_{2}$ are neighboring points on ${\mathbb{B}}({\mathbb{J}}(\mu))$, and $E(\pi_{1},\pi_{2})$ is an edge connecting two vertices. Since $E(\pi_{1},\pi_{2})$ is a face of ${\mathbb{J}}(\mu)$, by Definition 1, there exists weight vector ${\bm{w}}$ and scalar $c_{0}$ such that $E(\pi_{1},\pi_{2})={\mathbb{C}}\cap\{{\bm{x}}\in\mathbb{R}^{d}:{\bm{w}}^{\top}
{\bm{x}}=c_{0}\}$ and ${\bm{w}}^{\top}{\bm{x}}\leq c_{0}$ for any ${\bm{x}}\in{\mathbb{J}}(\mu)$. Therefore, we have

$$ $\{\pi_{1},\pi_{2}\}=\arg\max_{\pi\in{\mathbb{V}}({\mathbb{J}}(\mu))}{\bm{w}}^{ \top}J^{\pi}(\mu).$ $$

Moreover, since any points within the convex polytope can be written as the convex combination of extreme points, and the solutions of extreme points to $\arg\max_{\pi\in\Pi_{D}}{\bm{w}}^{\top}J^{\pi}(\mu)$ only contains $\pi_{1}$ and $\pi_{2}$, therefore

$$ $\{\alpha J^{\pi_{1}}(\mu)+(1-\alpha)J^{\pi_{1}}(\mu)|\alpha\in[0,1]\}=\arg\max _{\pi\in\Pi}{\bm{w}}^{\top}J^{\pi}(\mu).$ (2) $$

We construct a single-objective MDP $(\mathcal{S},\mathcal{A},{\bm{P}},{\bm{r}}^{\top}{\bm{w}},\gamma)$, where we use the preference vector ${\bm{w}}$ to transform $M$-objective reward tensor ${\bm{r}}\in\mathbb{R}^{S\times A\times D}$ to single-objective reward $\in\mathbb{R}^{S\times A}$. By Lemma 12, $\pi_{1}$ and $\pi_{2}$ are optimal deterministic policies on $(\mathcal{S},\mathcal{A},{\bm{P}},{\bm{r}}^{\top}{\bm{w}},\gamma)$. By Lemma 13, the optimal policies on $(\mathcal{S},\mathcal{A},{\bm{P}},{\bm{r}}^{\top}{\bm{w}},\gamma)$ lies in the convex hull constructed by $\pi_{1}$ and $\pi_{2}$, i.e.,

$$ $\{J^{\beta\pi_{1}+(1-\beta)\pi_{2}}(\mu)|\beta\in[0,1]\}=\arg\max_{\pi\in\Pi}{ \bm{w}}^{\top}J^{\pi}(\mu).$ (3) $$

Combining Eq. 2 and Eq. 3, we obtain

$$ $\{\alpha J^{\pi_{1}}(\mu)+(1-\alpha)J^{\pi_{1}}(\mu)\mid\alpha\in[0,1]\}=\{J^{ \beta\pi_{1}+(1-\beta)\pi_{2}}(\mu)\mid\beta\in[0,1]\}.$ $$

This result indicates that, for an initial distribution $\mu$, the edge between neighboring policies in ${\mathbb{J}}(\mu)$ can only be achieved through the long-term return of the convex combination of these neighboring policies. This concludes our proof.
∎

###### Definition 2 .

We define the distance between two deterministic policies, $\pi_{1}$ and $\pi_{2}$, as the number of states where the policies differ. This distance is denoted by $d(\pi_{1},\pi_{2})$.

###### Lemma 19 .

Given a finite MDP $(\mathcal{S},\mathcal{A},{\mathbf{P}},{\bm{r}},\gamma)$, where ${\mathbf{P}}$ is the transition probability kernel and ${\bm{r}}\geq 0$ is the reward function. Let $\pi_{1}$ and $\pi_{2}$ be two deterministic policies.

- 1.
$d(\pi_{1},\pi_{2})=1$: If $\pi_{1}$ and $\pi_{2}$ differ by exactly one state-action pair, $\{J_{\alpha\pi_{1}+(1-\alpha)\pi_{2}}(\mu)|\alpha\in[0,1]\}$ forms a straight line segment between $J^{\pi_{1}}(\mu)$ and $J^{\pi_{1}}(\mu)$.
- 2.
$d(\pi_{1},\pi_{2})>1$: If $\pi_{1}$ and $\pi_{2}$ differ by more than one state-action pair, for almost all ${\mathbf{P}}$ and ${\bm{r}}$ in the space of valid transition kernels and rewards (with Lebesgue measure $1$), $\{J_{\alpha\pi_{1}+(1-\alpha)\pi_{2}}(\mu)|\alpha\in[0,1]\}$ does not form the straight line segment between $J^{\pi_{1}}(\mu)$ and $J^{\pi_{1}}(\mu)$.

###### Proof.

Let ${\mathcal{M}}$ be the set of states that $\pi_{1}$ and $\pi_{2}$ differ on. By definition of distance between two deterministic policies, $M\coloneqq|{\mathbb{M}}|=d(\pi_{1},\pi_{2})$.

Starting from state $s$ under policy $\pi$, we define hitting time of the set ${\mathcal{M}}\subseteq\mathcal{S}$, denoted as ${\mathbf{H}}^{\pi}(s,{\mathcal{M}})$, as the first time step at which the process reaches any state in ${\mathcal{M}}$. It is defined as:

$$ ${\mathbf{H}}^{\pi}(s,{\mathcal{M}})\coloneqq\inf\left\{t\geq 0\mid s_{0}=s,s_{ t}\in{\mathcal{M}}\right\},$ $$

where $s_{t}$ denotes the state of the process at time $t$.
For any $\bar{s}\in{\mathcal{M}}$, we define the random variable ${\mathbf{H}}^{\pi}(\bar{s},{\mathcal{M}})=0$ as it takes 0 0 steps from $\bar{s}^{\prime}$ to ${\mathcal{M}}.$
Moreover, we define the total return of $d$-th objective before hitting ${\mathcal{M}}$ from state $s$ under policy $\pi$ as the sum of discounted rewards until the process reaches any state in ${\mathcal{M}}$. It is given by:

$$ $\tilde{R}^{\pi}_{d}(s,{\mathcal{M}})\coloneqq\sum_{t=0}^{{\mathbf{H}}^{\pi}(s, {\mathcal{M}})-1}\gamma^{t}{\bm{r}}_{d}(s_{t},a_{t}),$ $$

where $r(s_{t},a_{t})$ is the reward at time step $t$.

Similarly, Starting from state $s$ under policy $\pi$, we denote the hitting time of a specific state $\bar{s}\in{\mathcal{M}}$, conditioned on avoiding all other states in ${\mathcal{M}}$ before reaching $\bar{s}$ as ${\mathbf{H}}^{\pi}(s,{\mathcal{M}},\bar{s})$ with slight abuse of notation. It is defined as:

$$ ${\mathbf{H}}^{\pi}(s,{\mathcal{M}},\bar{s})\coloneqq\inf\left\{t\geq 0\mid s_{ 0}=s,s_{t}=\bar{s},\,s_{k}\notin{\mathcal{M}},\forall k<t\right\}.$ (4) $$

For any $\bar{s}^{\prime},\bar{s}\in{\mathcal{M}}$ with $\bar{s}^{\prime}\neq\bar{s}$, the random variable ${\mathbf{H}}^{\pi}(\bar{s}^{\prime},{\mathcal{M}},\bar{s})$ are defined as:

- •
${\mathbf{H}}^{\pi}(\bar{s},{\mathcal{M}},\bar{s})=0$ with probability 1, as it takes 0 steps to reach $\bar{s}$ from $\bar{s}$,
- •
${\mathbf{H}}^{\pi}(\bar{s}^{\prime},{\mathcal{M}},\bar{s})=\infty$ with probability 1, as it is impossible to reach $\bar{s}$ first from $\bar{s}^{\prime}$ (since we are already at $\bar{s}^{\prime}\in{\mathcal{M}}$).

The total return before hitting $\bar{s}\in{\mathcal{M}}$, conditioned on avoiding all other states in ${\mathcal{M}}$ before reaching $\bar{s}$, denoted as $\tilde{R}^{\pi}_{d}(s,{\mathcal{M}},\bar{s})$:

$$ $\tilde{R}^{\pi}_{d}(s,{\mathcal{M}},\bar{s})\coloneqq\sum_{t=0}^{{\mathbf{H}}^ {\pi}(s,{\mathcal{M}},\bar{s})-1}\gamma^{t}{\bm{r}}_{d}(s_{t},a_{t}).$ (5) $$

The arrival state is defined as the first state in ${\mathcal{M}}$ reached by the process, starting from $s$ under policy $\pi$. Denote the arrival state as:

$$ $S^{\pi}(s,{\mathcal{M}})\coloneqq s_{{\mathbf{H}}^{\pi}(s,{\mathcal{M}})},$ (6) $$

where $s_{{\mathbf{H}}^{\pi}(s,{\mathcal{M}})}$ is the state of the process at the hitting time ${\mathbf{H}}^{\pi}(s,{\mathcal{M}})$. Since $S^{\pi}(s,{\mathcal{M}})$ is the first state in ${\mathcal{M}}$ that is reached, the hitting time of $S^{\pi}(s,{\mathcal{M}})$ is indeed the same as the hitting time of ${\mathcal{M}}$. Similarly, the total return before hitting ${\mathcal{M}}$ is the same as the return before hitting $S^{\pi}(s,{\mathcal{M}})$ conditioned on avoiding hitting other states in ${\mathcal{M}}$, that is:

$$ $\displaystyle{\mathbf{H}}^{\pi}(s,{\mathcal{M}})=$ $\displaystyle{\mathbf{H}}^{\pi}(s,{\mathcal{M}},S^{\pi}(s,{\mathcal{M}})),$ (7) $\displaystyle\tilde{R}^{\pi}_{d}(s,{\mathcal{M}})=$ $\displaystyle\sum_{t=0}^{{\mathbf{H}}^{\pi}(s,{\mathcal{M}})-1}\gamma^{t}{\bm{ r}}_{d}(s_{t},a_{t})=\sum_{t=0}^{{\mathbf{H}}^{\pi}(s,{\mathcal{M}},S^{\pi}(s, {\mathcal{M}}))-1}\gamma^{t}{\bm{r}}_{d}(s_{t},a_{t})=\tilde{R}^{\pi}_{d}(s,{ \mathcal{M}},S^{\pi}(s,{\mathcal{M}})).$ $$

Denote the expectation of the total return and discount before hitting $\bar{s}$ conditioned on avoiding all other states in ${\mathcal{M}}$ before reaching $\bar{s}$ as $\tilde{{\mathbf{V}}}^{\pi}_{d}\in\mathbb{R}^{S\times 1}$, $\tilde{{\mathbf{V}}}^{\pi}\in\mathbb{R}^{S\times D}$, and $\tilde{\Gamma}\in\mathbb{R}^{S\times M}$, respectively. For $s\in\mathcal{S}$, $s^{\prime}\in{\mathcal{M}}$, $d\in\{1,\cdots,D\}$,

$$ $\displaystyle\tilde{{\mathbf{V}}}^{\pi}_{d}(s,{\mathcal{M}})\coloneqq$ $\displaystyle\mathbb{E}\left[\tilde{{\mathbf{R}}}^{\pi}_{d}(s,{\mathcal{M}}) \right],$ (8) $\displaystyle\tilde{{\mathbf{V}}}^{\pi}=$ $\displaystyle[\tilde{{\mathbf{V}}}^{\pi}_{1},\dots,\tilde{{\mathbf{V}}}^{\pi}_ {D}],$ $\displaystyle\Gamma^{\pi}(s,{\mathcal{M}},\bar{s})=$ $\displaystyle P(S^{\pi}(s,{\mathcal{M}})=\bar{s})\mathbb{E}\left[\gamma^{{ \mathbf{H}}(s,{\mathcal{M}},\bar{s})}\right].$ $$

By the ergodicity assumption of MDP, starting from any state, the probability of arriving ${\mathcal{M}}$ is $1$.
Recall ${\mathbf{V}}^{\pi}\in\mathbb{R}^{S\times D}$ is the value function with initial state distribution $\mu$, where $\mu$ is ignored for the notation simplicity. Moreover, we use ${\mathbf{V}}^{\pi}_{d}(s)$ and ${\mathbf{V}}^{\pi}_{d}({\mathcal{M}})$ to denote the $d$-th objective value function at state $s$ and at state set ${\mathcal{M}}$, respectively. By the definition of value function, ${\mathbf{V}}^{\pi}_{d}(s)$ can be written as

$$ $\displaystyle{\mathbf{V}}^{\pi}_{d}(s)=$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}{\bm{r}}_{d}(s_{t},a _{t})\middle|s_{0}=s\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}\left[\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}{\bm {r}}_{d,t}\middle|S^{\pi}(s,{\mathcal{M}})\right]\middle|s_{0}=s\right].$ $$

We next want to calculate the conditional expectation of long-term return given $S^{\pi}(s,{\mathcal{M}})=\bar{s}$.

$$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}{\bm{r}}_{d,t} \middle|S^{\pi}(s,{\mathcal{M}})=\bar{s}\right]=$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{{\mathbf{H}}(s,{\mathcal{M}},\bar{s}) -1}\gamma^{t}{\bm{r}}_{d,t}+\gamma^{{\mathbf{H}}(s,{\mathcal{M}},\bar{s})}{ \mathbf{V}}^{\pi}_{d}(\bar{s})\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{{\mathbf{H}}(s,{\mathcal{M}},\bar{s}) -1}\gamma^{t}{\bm{r}}_{d,t}\right]+\mathbb{E}\left[\gamma^{{\mathbf{H}}(s,{ \mathcal{M}},\bar{s})}\right]{\mathbf{V}}^{\pi}_{d}(\bar{s})$ (By linearity of expectations and ${\mathbf{V}}^{\pi}_{d}(\bar{s})$ is a constant) $\displaystyle=$ $\displaystyle\mathbb{E}\left[\tilde{R}^{\pi}_{d}(s,{\mathcal{M}},\bar{s}) \right]+\mathbb{E}\left[\gamma^{{\mathbf{H}}(s,{\mathcal{M}},\bar{s})}\right]{ \mathbf{V}}^{\pi}_{d}(\bar{s})\quad\text{(by definition of $\tilde{R}^{\pi}_{d }(s,{\mathcal{M}},\bar{s})$ in \lx@cref{creftype~refnum}{eq:R_s_bars})}$ $$

Plugging the above equation into ${\mathbf{V}}^{\pi}_{d}(s)$, we have

$$ $\displaystyle{\mathbf{V}}^{\pi}_{d}(s)=$ $\displaystyle\sum_{\bar{s}\in{\mathcal{M}}}P(S^{\pi}(s,{\mathcal{M}})=\bar{s}) \mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}{\bm{r}}_{d,t}\middle|S^{\pi}(s,{ \mathcal{M}})=\bar{s}\right]$ $\displaystyle=$ $\displaystyle\sum_{\bar{s}\in{\mathcal{M}}}P(S^{\pi}(s,{\mathcal{M}})=\bar{s}) \mathbb{E}\left[\tilde{R}^{\pi}_{d}(s,{\mathcal{M}},\bar{s})\right]+\sum_{\bar {s}\in{\mathcal{M}}}P(S^{\pi}(s,{\mathcal{M}})=\bar{s})\mathbb{E}\left[\gamma^ {{\mathbf{H}}(s,{\mathcal{M}},\bar{s})}\right]{\mathbf{V}}^{\pi}_{d}(\bar{s})$ $\displaystyle\overset{\leavevmode\hbox to9.93pt{\vbox to9.93pt{\pgfpicture \makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont \pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope } \pgfsys@endscope\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@endscope\pgfsys@beginscope\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2. 63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.76 44pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63 133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.764 4pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt} \pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}{=}$ $\displaystyle\mathbb{E}\left[\tilde{R}^{\pi}_{d}(s,{\mathcal{M}})\right]+\sum_ {\bar{s}\in{\mathcal{M}}}P(S^{\pi}(s,{\mathcal{M}})=\bar{s})\mathbb{E}\left[ \gamma^{{\mathbf{H}}(s,{\mathcal{M}},\bar{s})}\right]{\mathbf{V}}^{\pi}_{d}( \bar{s})$ $\displaystyle=$ $\displaystyle\tilde{{\mathbf{V}}}^{\pi}_{d}(s,{\mathcal{M}})+\sum_{\bar{s}\in{ \mathcal{M}}}\Gamma^{\pi}(s,{\mathcal{M}},\bar{s}){\mathbf{V}}^{\pi}_{d}(\bar{ s})\quad\text{(by \lx@cref{creftype~refnum}{def:tV_Gamma}),}$ $$

where 1 is because

$$ $\displaystyle\sum_{\bar{s}\in{\mathcal{M}}}P(S^{\pi}(s,{\mathcal{M}})=\bar{s}) \mathbb{E}\left[\tilde{R}^{\pi}_{d}(s,{\mathcal{M}},\bar{s})\right]=$ $\displaystyle\mathbb{E}\left[\mathbb{E}\left[\sum_{t=0}^{{\mathbf{H}}(s,{ \mathcal{M}},S^{\pi}(s,{\mathcal{M}}))-1}\gamma^{t}{\bm{r}}_{d}(s_{t},a_{t}) \right]\middle|S^{\pi}(s,{\mathcal{M}})\middle|s_{0}=s\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}\left[\mathbb{E}\left[\sum_{t=0}^{{\mathbf{H}}(s,{ \mathcal{M}})-1}\gamma^{t}{\bm{r}}_{d}(s_{t},a_{t})\right]\middle|S^{\pi}(s,{ \mathcal{M}})\middle|s_{0}=s\right]\quad\text{(by \lx@cref{creftype~refnum}{eq :eq_hitting_M_S})}$ $\displaystyle=$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{{\mathbf{H}}(s,{\mathcal{M}})-1} \gamma^{t}{\bm{r}}_{d}(s_{t},a_{t})\middle|s_{0}=s\right]$ $\displaystyle=$ $\displaystyle\tilde{R}^{\pi}_{d}(s,{\mathcal{M}}).$ $$

Lemma 14 gives the value of $\Gamma^{\pi}$ and $\tilde{{\mathbf{V}}}^{\pi}$ as following

$$ $\Gamma^{\pi}=\begin{bmatrix}\gamma({\mathbf{I}}_{S-M}-\gamma{\mathbf{A}})^{-1} {\mathbf{B}}\\ {\mathbf{I}}_{M}\end{bmatrix},\quad\tilde{{\mathbf{V}}}^{\pi}=\begin{bmatrix}( {\mathbf{I}}_{S-M}-\gamma{\mathbf{A}})^{-1}\bm{X}\\ {\bm{0}}_{M}\end{bmatrix}.$ $$

Note that $\Gamma^{\pi}$ and $\tilde{{\mathbf{V}}}^{\pi}$ are the same for any policy in $\Pi_{N}(s_{1},{\mathcal{M}})$. Since we only consider policies within $\Pi_{N}(s_{1},{\mathcal{M}})$, for simplicity of notation, we omit the superscripts $\pi$ in $\Gamma^{\pi}$ and $\tilde{{\mathbf{V}}}^{\pi}$ in the following sections, as they remain constant for any policies within $\Pi_{N}(s_{1},{\mathcal{M}})$.

Rearranging ${\mathbf{V}}^{\pi}$, we have

$$ ${\mathbf{V}}^{\pi}=\tilde{{\mathbf{V}}}+\Gamma{\mathbf{V}}^{\pi}({\mathcal{M}}).$ (9) $$

By the Bellman equation and Eq. 9, we can rewrite the ${\mathbf{V}}^{\pi}({\mathcal{M}})$ as

$$ $\displaystyle{\mathbf{V}}^{\pi}({\mathcal{M}})=$ $\displaystyle{\bm{r}}^{\pi}({\mathcal{M}})+\gamma{\mathbf{P}}^{\pi}({\mathcal{ M}}){\mathbf{V}}^{\pi}\quad\text{(by Bellman equation)}$ $\displaystyle=$ $\displaystyle{\bm{r}}^{\pi}({\mathcal{M}})+\gamma{\mathbf{P}}^{\pi}({\mathcal{ M}})\left(\tilde{{\mathbf{V}}}+\Gamma{\mathbf{V}}^{\pi}({\mathcal{M}})\right) \quad\text{(by \lx@cref{creftype~refnum}{eq:V_pi0})}$ $\displaystyle=$ $\displaystyle\left({\bm{r}}^{\pi}({\mathcal{M}})+\gamma{\mathbf{P}}^{\pi}({ \mathcal{M}})\tilde{{\mathbf{V}}}\right)+\gamma{\mathbf{P}}^{\pi}({\mathcal{M} })\Gamma{\mathbf{V}}^{\pi}({\mathcal{M}}).$ $$

Since $[\mathbf{A},\mathbf{B}]$ is a stochastic matrix, we have $(\mathbf{I}_{S-M}-\gamma\mathbf{A})^{-1}\mathbf{B}\mathbf{1}_{M}<(\mathbf{I}_{
S-M}-\mathbf{A})^{-1}\mathbf{B}\mathbf{1}_{M}=\mathbf{1}_{S-M}$, where the inequality means $(\mathbf{I}_{S-M}-\gamma\mathbf{A})^{-1}\mathbf{B}\mathbf{1}_{M}$ is smaller than $(\mathbf{I}_{S-M}-\mathbf{A})^{-1}\mathbf{B}\mathbf{1}_{M}$ component-wisely.
Moreover, since each element of ${\mathbf{A}}$ and ${\mathbf{B}}$ are larger than zero, we also have $(\mathbf{I}_{S-M}-\gamma\mathbf{A})^{-1}\mathbf{B}\mathbf{1}_{M}>{\bm{0}}_{S-M}$.
As each element of $\mathbf{C}^{\pi}$ and $\mathbf{D}^{\pi}$ are not smaller than zero, it follows that ${\bm{0}}_{M}\leq\left(\mathbf{C}^{\pi}(\mathbf{I}_{S-M}-\gamma\mathbf{A})^{-1}
\mathbf{B}+\mathbf{D}^{\pi}\right)\mathbf{1}_{M}<\left(\mathbf{C}^{\pi}+
\mathbf{D}^{\pi}\right)\mathbf{1}_{M}=\mathbf{1}_{M}$. Hence, $\|\mathbf{C}^{\pi}(\mathbf{I}_{S-M}-\gamma\mathbf{A})^{-1}\mathbf{B}+\mathbf{D
}^{\pi}\|_{\infty}<1$. By Lemma 6, $\mathbf{P}^{\pi}({\mathcal{M}})\Gamma=\gamma\mathbf{C}^{\pi}(\mathbf{I}_{S-M}-
\gamma\mathbf{A})^{-1}\mathbf{B}+\mathbf{D}^{\pi}$ has eigenvalues all smaller than 1.
Hence the eigenvalue of $\left({\mathbf{I}}_{M}-\gamma{\mathbf{P}}^{\pi}({\mathcal{M}})\Gamma\right)$ are larger than zero, implying it is invertible.
Rearranging the above equation, we have

$$ ${\mathbf{V}}^{\pi}({\mathcal{M}})=\left({\mathbf{I}}_{M}-\gamma{\mathbf{P}}^{ \pi}({\mathcal{M}})\Gamma\right)^{-1}\left({\bm{r}}^{\pi}({\mathcal{M}})+ \gamma{\mathbf{P}}^{\pi}({\mathcal{M}})\tilde{{\mathbf{V}}}\right).$ (10) $$

Define

$$ $\displaystyle{\mathbf{F}}^{\pi}\coloneqq$ $\displaystyle\gamma{\mathbf{P}}^{\pi}({\mathcal{M}})\Gamma,$ (11) $\displaystyle{\mathbf{E}}^{\pi}\coloneqq$ $\displaystyle{\bm{r}}^{\pi}({\mathcal{M}})+\gamma{\mathbf{P}}^{\pi}({\mathcal{ M}})\tilde{{\mathbf{V}}}.$ $$

Plugging Eq. 10 into Eq. 9, we obtain

$$ $\displaystyle{\mathbf{V}}^{\pi}=$ $\displaystyle\tilde{{\mathbf{V}}}+\Gamma\cdot\left({\mathbf{I}}_{M}-\gamma{ \mathbf{P}}^{\pi}({\mathcal{M}})\Gamma\right)^{-1}\left({\bm{r}}^{\pi}({ \mathcal{M}})+\gamma{\mathbf{P}}^{\pi}({\mathcal{M}})\tilde{{\mathbf{V}}}\right)$ (12) $\displaystyle=$ $\displaystyle\tilde{{\mathbf{V}}}+\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F }}^{\pi}\right)^{-1}{\mathbf{E}}^{\pi}.\quad\text{(by definition of ${\mathbf{ F}}^{\pi}$ and ${\mathbf{E}}^{\pi}$)}$ $$

We move to investigate the derivative of ${\mathbf{V}}^{\pi}$ with respect to $\pi(\bar{s},a)$.

$$ $\displaystyle\frac{\partial{\mathbf{V}}^{\pi}}{\partial\pi(\bar{s},a)}=$ $\displaystyle\Gamma\cdot\frac{\partial\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi }\right)^{-1}}{\partial\pi(\bar{s},a)}{\mathbf{E}}^{\pi}+\Gamma\cdot\left({ \mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right)^{-1}\frac{\partial{\mathbf{E}}^{\pi} }{\partial\pi(\bar{s},a)}$ $\displaystyle=$ $\displaystyle\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right)^{-1} \frac{\partial{\mathbf{F}}^{\pi}}{\partial\pi(\bar{s},a)}\left({\mathbf{I}}_{M }-{\mathbf{F}}^{\pi}\right)^{-1}{\mathbf{E}}^{\pi}+\Gamma\cdot\left({\mathbf{I }}_{M}-{\mathbf{F}}^{\pi}\right)^{-1}\frac{\partial{\mathbf{E}}^{\pi}}{ \partial\pi(\bar{s},a)}$ (by $\frac{\partial{\mathbf{Y}}^{-1}}{\partial x}=-{\mathbf{Y}}^{-1}\frac{\partial{ \mathbf{Y}}}{\partial x}{\mathbf{Y}}^{-1}$ [ 40 ] ) $\displaystyle=$ $\displaystyle\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right)^{-1}{ \mathbf{P}}(\delta(\bar{s}),a,\cdot)\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf {F}}^{\pi}\right)^{-1}{\mathbf{E}}^{\pi}$ $\displaystyle\quad+\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right) ^{-1}\left(\mathbf{r}(\delta(\bar{s}),a,\cdot)+{\mathbf{P}}(\delta(\bar{s}),a, \cdot)\tilde{{\mathbf{V}}}\right).\quad\text{(by \lx@cref{creftype~refnum}{lem :Fpi_Epi})}$ $$

Then we can calculate the directional derivative on the direction of $\pi_{2}-\pi_{1}$, where $\pi_{2}$ and $\pi_{1}$ are deterministic policies. Moreover, $\pi_{1}(\bar{s})\neq\pi_{2}(\bar{s})$ for any state $\bar{s}$ belonging to ${\mathcal{M}}$, and $\pi_{1}(\bar{s})=\pi_{2}(\bar{s})$ for any state other than ${\mathcal{M}}$. The calculation of the directional derivative, denoted as $\left\langle\frac{\partial{\mathbf{V}}^{\pi}}{\partial\pi},\pi_{2}-\pi_{1}\right\rangle$, is as follows:

$$ $\displaystyle\left\langle\frac{\partial{\mathbf{V}}^{\pi}}{\partial\pi},\pi_{2 }-\pi_{1}\right\rangle=$ $\displaystyle\sum_{\bar{s}\in{\mathcal{M}},a\in\mathcal{A}}\frac{\partial{ \mathbf{V}}^{\pi}}{\partial\pi(\bar{s},a)}\left(\pi_{2}(\bar{s},a)-\pi_{1}( \bar{s},a)\right)$ $\displaystyle=$ $\displaystyle\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right)^{-1} \sum_{\bar{s}\in{\mathcal{M}}}\left({\mathbf{P}}(\delta(\bar{s}),\pi_{2}(\bar{ s}),\cdot)-{\mathbf{P}}(\delta(\bar{s}),\pi_{1}(\bar{s}),\cdot)\right)\Gamma \cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right)^{-1}{\mathbf{E}}^{\pi}$ $\displaystyle+\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right)^{-1} \sum_{\bar{s}\in{\mathcal{M}}}\left(\left(\mathbf{r}(\delta(\bar{s}),\pi_{2}( \bar{s}),\cdot)+{\mathbf{P}}(\delta(\bar{s}),\pi_{2}(\bar{s}),\cdot)\tilde{{ \mathbf{V}}}\right)\right.$ $\displaystyle\quad\quad\left.-\left(\mathbf{r}(\delta(\bar{s}),\pi_{1}(\bar{s} ),\cdot)+{\mathbf{P}}(\delta(\bar{s}),\pi_{1}\bar{s}),\cdot)\tilde{{\mathbf{V} }}\right)\right)$ (by (1) of Lemma 15 ) $\displaystyle=$ $\displaystyle\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right)^{-1} \left({\mathbf{F}}^{\pi_{2}}-{\mathbf{F}}^{\pi_{1}}\right)\left({\mathbf{I}}_{ M}-{\mathbf{F}}^{\pi}\right)^{-1}{\mathbf{E}}^{\pi}+\Gamma\cdot\left({\mathbf{ I}}_{M}-{\mathbf{F}}^{\pi}\right)^{-1}\left({\mathbf{E}}^{\pi_{2}}-{\mathbf{E} }^{\pi_{1}}\right)$ $\displaystyle\text{(by (2) of \lx@cref{creftype~refnum}{lem:Fpi_Epi})}.$ $$

Consequently, the directional derivative along the direction of $\pi_{2}-\pi_{1}$ at a convex combination of $\pi_{1}$ and $\pi_{2}$, namely $\alpha\pi_{1}+(1-\alpha)\pi_{2}$ with $0\leq\alpha\leq 1$, can be expressed as follows:

$$ $\displaystyle\left\langle\frac{\partial{\mathbf{V}}^{\pi}}{\partial\pi}\big{|} \pi=\alpha\pi_{1}+(1-\alpha)\pi_{2},\pi_{2}-\pi_{1}\right\rangle$ (13) $\displaystyle\quad=\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right) ^{-1}\left({\mathbf{F}}^{\pi_{2}}-{\mathbf{F}}^{\pi_{1}}\right)\left({\mathbf{ I}}_{M}-{\mathbf{F}}^{\pi}\right)^{-1}{\mathbf{E}}^{\pi}+\Gamma\cdot\left({ \mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right)^{-1}\left({\mathbf{E}}^{\pi_{2}}-{ \mathbf{E}}^{\pi_{1}}\right)$ $\displaystyle\quad=\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right) ^{-1}\left({\mathbf{F}}^{\pi_{2}}-{\mathbf{F}}^{\pi_{1}}\right)\left({\mathbf{ I}}_{M}-{\mathbf{F}}^{\pi}\right)^{-1}\left(\alpha{\mathbf{E}}^{\pi_{1}}+(1- \alpha){\mathbf{E}}^{\pi_{2}}\right)$ $\displaystyle\quad\quad+\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi} \right)^{-1}\left({\mathbf{E}}^{\pi_{2}}-{\mathbf{E}}^{\pi_{1}}\right)$ (by ${\mathbf{E}}^{\pi}=\alpha{\mathbf{E}}^{\pi_{1}}+(1-\alpha){\mathbf{E}}^{\pi_{2}}$ from (3) of Lemma 15 ) $\displaystyle\quad=\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right) ^{-1}\left((1-\alpha)\left({\mathbf{F}}^{\pi_{2}}-{\mathbf{F}}^{\pi_{1}}\right )+\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right)\right)\left({\mathbf{I}}_{M }-{\mathbf{F}}^{\pi}\right)^{-1}{\mathbf{E}}^{\pi_{2}}$ $\displaystyle\quad\quad+\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi} \right)^{-1}\left(\alpha\left({\mathbf{F}}^{\pi_{2}}-{\mathbf{F}}^{\pi_{1}} \right)-\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right)\right)\left({\mathbf{ I}}_{M}-{\mathbf{F}}^{\pi}\right)^{-1}{\mathbf{E}}^{\pi_{1}}$ $\displaystyle\quad=\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right) ^{-1}\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)\left({\mathbf{I}}_{M }-{\mathbf{F}}^{\pi}\right)^{-1}{\mathbf{E}}^{\pi_{2}}$ $\displaystyle\quad\quad-\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi} \right)^{-1}\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{2}}\right)\left({\mathbf {I}}_{M}-{\mathbf{F}}^{\pi}\right)^{-1}{\mathbf{E}}^{\pi_{1}}$ $\displaystyle\quad\quad\text{(by ${\mathbf{F}}^{\pi}=\alpha{\mathbf{F}}^{\pi_{ 1}}+(1-\alpha){\mathbf{F}}^{\pi_{2}}$ from (3) of \lx@cref{creftype~refnum}{le m:Fpi_Epi})}.$ $$

Furthermore, the directional derivative along the direction $\pi_{2}-\pi_{1}$ at the point $\pi_{1}$ can be written as:

$$ $\displaystyle\left\langle\frac{\partial{\mathbf{V}}^{\pi}}{\partial\pi}\big{|} \pi=\pi_{1},\pi_{2}-\pi_{1}\right\rangle=$ $\displaystyle\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)^{ -1}\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)\left({\mathbf{I}}_{M}- {\mathbf{F}}^{\pi_{1}}\right)^{-1}{\mathbf{E}}^{\pi_{2}}$ (14) $\displaystyle-\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)^ {-1}\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{2}}\right)\left({\mathbf{I}}_{M} -{\mathbf{F}}^{\pi_{1}}\right)^{-1}{\mathbf{E}}^{\pi_{1}}$ $\displaystyle=$ $\displaystyle\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)^{ -1}{\mathbf{E}}^{\pi_{2}}-\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_ {1}}\right)^{-1}\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{2}}\right)\left({ \mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)^{-1}{\mathbf{E}}^{\pi_{1}}$ $\displaystyle=$ $\displaystyle\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)^{ -1}\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{2}}\right)\left(\left({\mathbf{I} }_{M}-{\mathbf{F}}^{\pi_{2}}\right)^{-1}{\mathbf{E}}^{\pi_{2}}-\left({\mathbf{ I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)^{-1}{\mathbf{E}}^{\pi_{1}}\right).$ $$

The statement that ${\mathbf{V}}^{\alpha\pi_{1}+(1-\alpha)\pi_{2}}$ lies on the straight line between ${\mathbf{V}}^{\pi_{1}}$ and ${\mathbf{V}}^{\pi_{2}}$ is equivalent to that the directional derivative of ${\mathbf{V}}^{\pi}$ along the direction $\pi_{2}-\pi_{1}$ at the point $\alpha\pi_{1}+(1-\alpha)\pi_{2}$ aligns with the direction of ${\mathbf{V}}^{\pi_{2}}-{\mathbf{V}}^{\pi_{1}}$.
That is, for any $0\leq\alpha\leq 1$, there exists $k\in\mathbb{R}$ which is related to $\alpha$ such that the following equation holds

$$ $\left\langle\frac{\partial{\mathbf{V}}^{\pi}}{\partial\pi}\big{|}_{\pi=\alpha \pi_{1}+(1-\alpha)\pi_{2}},\pi_{2}-\pi_{1}\right\rangle=k\left({\mathbf{V}}^{ \pi_{2}}-{\mathbf{V}}^{\pi_{1}}\right).$ (15) $$

Plugging Eq. 12 and Eq. 13 into Eq. 15, LHS and RHS can be written as

$$ $\displaystyle\text{LHS}=$ $\displaystyle\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right)^{-1} \left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)\left({\mathbf{I}}_{M}-{ \mathbf{F}}^{\pi}\right)^{-1}{\mathbf{E}}^{\pi_{2}}$ $\displaystyle-\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right)^{-1} \left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{2}}\right)\left({\mathbf{I}}_{M}-{ \mathbf{F}}^{\pi}\right)^{-1}{\mathbf{E}}^{\pi_{1}},$ $\displaystyle\text{RHS}=$ $\displaystyle k\left({\mathbf{V}}^{\pi_{2}}-{\mathbf{V}}^{\pi_{1}}\right)$ $\displaystyle=$ $\displaystyle k\left(\left(\tilde{{\mathbf{V}}}+\Gamma\cdot\left({\mathbf{I}}_ {M}-{\mathbf{F}}^{\pi_{2}}\right)^{-1}{\mathbf{E}}^{\pi_{2}}\right)-\left( \tilde{{\mathbf{V}}}+\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}} \right)^{-1}{\mathbf{E}}^{\pi_{1}}\right)\right)$ $\displaystyle=$ $\displaystyle k\Gamma\cdot\left(\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{2}} \right)^{-1}{\mathbf{E}}^{\pi_{2}}-\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1 }}\right)^{-1}{\mathbf{E}}^{\pi_{1}}\right).$ $$

Note that when $M=1$, ${\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}$ is a scalar and ${\mathbf{E}}^{\pi}\in\mathbb{R}^{d}$. In this case, for any $0\leq\alpha\leq 1$, there exists $k$ such that $\text{LHS}=\text{RHS}$. To show this, define scalars $b\coloneqq\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi}\right)$, $b_{1}\coloneqq\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)$, $b_{2}\coloneqq\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{2}}\right)$. Then we can express $\text{LHS}=b_{1}b_{2}/b^{2}\Gamma\left({\mathbf{E}}^{\pi_{2}}/b_{2}-{\mathbf{E
}}^{\pi_{1}}/b_{1}\right)$ and $\text{RHS}=\Gamma\left({\mathbf{E}}^{\pi_{2}}/b_{2}-{\mathbf{E}}^{\pi_{1}}/b_{
1}\right)$. Clearly letting $k=b_{1}b_{2}/b^{2}$ makes Eq. 15 hold. As a result, ${\mathbf{V}}^{\alpha\pi_{1}+(1-\alpha)\pi_{2}}$ lies on the straight line between ${\mathbf{V}}^{\pi_{1}}$ and ${\mathbf{V}}^{\pi_{2}}$ when $d(\pi_{1},\pi_{2})=1$.

A necessary condition for the statement ${\mathbf{V}}^{\alpha\pi_{1}+(1-\alpha)\pi_{2}}$ lies on the straight line between ${\mathbf{V}}^{\pi_{1}}$ and ${\mathbf{V}}^{\pi_{2}}$ is that the directional derivative of ${\mathbf{V}}^{\pi}$ along the direction $\pi_{2}-\pi_{1}$ at the point $\pi_{1}$ aligns with the direction of ${\mathbf{V}}^{\pi_{2}}-{\mathbf{V}}^{\pi_{1}}$, i.e., Eq. 15 when $\pi=\pi_{1}$. Formally, there exists a scalar $k$ such that

$$ $\left\langle\frac{\partial{\mathbf{V}}^{\pi}}{\partial\pi}\big{|}_{\pi=\pi_{1} },\pi_{2}-\pi_{1}\right\rangle=k\left({\mathbf{V}}^{\pi_{2}}-{\mathbf{V}}^{\pi _{1}}\right).$ (16) $$

Define $\Lambda\coloneqq\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{2}}\right)^{-1}{
\mathbf{E}}^{\pi_{2}}-\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)^{-1
}{\mathbf{E}}^{\pi_{1}}$. Plugging Eq. 14 into LHS, we have

$$ $\displaystyle\text{LHS}=$ $\displaystyle\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)^{ -1}\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{2}}\right)\left(\left({\mathbf{I} }_{M}-{\mathbf{F}}^{\pi_{2}}\right)^{-1}{\mathbf{E}}^{\pi_{2}}-\left({\mathbf{ I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)^{-1}{\mathbf{E}}^{\pi_{1}}\right)$ $\displaystyle=$ $\displaystyle\Gamma\cdot\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)^{ -1}\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{2}}\right)\Lambda,$ $$

RHS can be rewritten as

$$ $\displaystyle\text{RHS}=$ $\displaystyle k\Gamma\cdot\Lambda.$ $$

By Lemma 14, $\Gamma=\left[\left(\gamma({\mathbf{I}}_{S-M}-\gamma{\mathbf{A}})^{-1}{\mathbf{
B}}\right)^{\top},{\mathbf{I}}_{M}\right]^{\top}\in\mathbb{R}^{S\times M}$ and $\Gamma$ has rank $M\leq S$. Therefore, $\Gamma$ has full column rank.
By LABEL:{lem:full_col_rank_ABACsame_BCsame}, Eq. 16 is equivalent to the following equation:

$$ $\left(\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)^{-1}\left({\mathbf{ I}}_{M}-{\mathbf{F}}^{\pi_{2}}\right)-k{\mathbf{I}}_{M}\right)\Lambda={\bm{0}}.$ (17) $$

Note that $\Lambda\in\mathbb{R}^{M\times D}$, and $\mathrm{rank}(\Lambda)\leq\min(M,D)$.

(1) When $\mathrm{rank}(\Lambda)\leq M$, $\Lambda$ has full row rank. This case also implies $M\leq D$. By Theorem 3, the only solution to ${\mathbf{X}}\Lambda={\bm{0}}$ is ${\mathbf{X}}={\bm{0}}$. Therefore, Eq. 17 is equal to

$$ $\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)^{-1}\left({\mathbf{I}}_{M }-{\mathbf{F}}^{\pi_{2}}\right)-k{\mathbf{I}}_{M}={\bm{0}}.$ $$

Substituting the definition of ${\mathbf{F}}^{\pi}$ as ${\mathbf{F}}^{\pi}=\gamma{\mathbf{P}}^{\pi}({\mathcal{M}})\Gamma$ in the above equation and rearrange the equation, we have

$$ ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})\Gamma=\frac{1}{\gamma}\left({\mathbf{I}} _{M}-k\left({\mathbf{I}}_{M}-\gamma{\mathbf{P}}^{\pi_{1}}({\mathcal{M}})\Gamma \right)\right).$ $$

Moreover, to make ${\mathbf{P}}^{\pi_{2}}$ a valid probability distribution vector, ${\mathbf{P}}^{\pi_{2}}$ should satisfy ${\mathbf{P}}^{\pi_{2}}{\bm{1}}_{S}={\bm{1}}_{M}$. Therefore, ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})$ should satisfy ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})\left[\Gamma,{\bm{1}}_{S}\right]=[{
\mathbf{I}}_{M}-k\left({\mathbf{I}}_{M}-\gamma{\mathbf{P}}^{\pi_{1}}({\mathcal
{M}})\Gamma\right)/\gamma,{\bm{1}}_{M}]$.

When $M=S$, $\left[\Gamma,{\bm{1}}_{S}\right]\in\mathbb{R}^{S\times(S+1)}$ has rank $S$, and When $M<S$, Since $\left[\Gamma,{\bm{1}}_{S}\right]$ has $S$ rows and rank at least $M$. Hence, $\left[\Gamma,{\bm{1}}_{S}\right]$ has $S$ rows and rank at least $M$ in both cases. Fix $k$. By the rank-nullity theorem Theorem 3 and Lemma 4, for $\bar{s}\in{\mathcal{M}}$, if the solution of ${\mathbf{P}}^{\pi_{2}}(\bar{s})$ exists, the dimension of the solution ${\mathbf{P}}^{\pi_{2}}(\bar{s})$ is at most $S-M$. On the other hand, if no solution to ${\mathbf{P}}^{\pi_{2}}(\bar{s})$ exists, the dimension of the solution space is 0 0. Therefore, the dimension of solution space of ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})$ is at most $M\times(S-M)$.

By varying $k\in\mathbb{R}$, the dimension of solution space of ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})$ is $M\times(S-M)+1$.

Since valid probability transition matrix ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})$ requires that the row sums equal one, the ambient space ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})$ lies in has dimension $M\times(S-1)$.
Since the solution space of ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})$ that satisfies Eq. 17 has dimension at most $M\times(S-M)+1$ with $\mathrm{rank}(\Lambda)>0$, while the ambient space where ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})$ resides has dimension $M\times(S-1)$, the dimension of the solution space is significantly lower than that of the full space. Therefore, the set of points where ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})$ satisfies Eq. 17 forms a subset of Lebesgue measure 0 in the $M\times(S-1)$-dimensional space.

(2) When $0<\mathrm{rank}(\Lambda)<M$, the dimension of the solution set to ${\mathbf{X}}\Lambda={\bm{0}}$ is $M\times(M-\mathrm{rank}(\Lambda))$ by Theorem 3.
Let ${\mathbf{H}}$ be a possible solution to ${\mathbf{X}}\Lambda={\bm{0}}$. Then we have

$$ $\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)^{-1}\left({\mathbf{I}}_{M }-{\mathbf{F}}^{\pi_{2}}\right)-k{\mathbf{I}}_{M}={\mathbf{H}}.$ $$

Rewrite the above equation, we have

$$ ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})\Gamma=\frac{1}{\gamma}\left({\mathbf{I}} _{M}-k\left({\mathbf{I}}_{M}-\gamma{\mathbf{P}}^{\pi_{1}}({\mathcal{M}})\Gamma \cdot\left({\mathbf{H}}+k{\mathbf{I}}_{M}\right)\right)\right).$ $$

Define ${\mathbb{G}}=\{{\mathbf{G}}|{\mathbf{G}}=\frac{1}{\gamma}\left({\mathbf{I}}_{M
}-k\left({\mathbf{I}}_{M}-\gamma{\mathbf{P}}^{\pi_{1}}({\mathcal{M}})\Gamma
\left({\mathbf{H}}+k{\mathbf{I}}_{M}\right)\right)\right),{\mathbf{H}}\Lambda=
{\bm{0}},k\in\mathbb{R}\}$.
Since the dimension of the solution set to ${\mathbf{X}}\Lambda={\bm{0}}$ is $M\times(M-\mathrm{rank}(\Lambda))$ and ${\mathbf{I}}_{M}$ is not a solution to ${\mathbf{X}}\Lambda={\bm{0}}$, we have $\dim({\mathbb{G}})=M\times(M-\mathrm{rank}(\Lambda))+1$.

Fix $G$ in ${\mathbb{G}}$. Similar to the analysis of (1), the dimension of solution space of ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})$ is at most $M\times(S-M)$.

Combining with the dimension of ${\mathbb{G}}$, the dimension of solution space of ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})$ that satisfies Eq. 17 is at most $M\times(S-M)+M\times(M-\mathrm{rank}(\Lambda))+1=M\times(S-\mathrm{rank}(
\Lambda))+1$.
Since the solution space of ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})$ that satisfies Eq. 17 has dimension at most $M\times(S-\mathrm{rank}(\Lambda))+1$ with $\mathrm{rank}(\Lambda)>0$, while the ambient space where ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})$ resides has dimension $M\times(S-1)$, the dimension of the solution space is significantly lower than that of the full space. Therefore, according to results from measure theory, the set of points where ${\mathbf{P}}^{\pi_{2}}({\mathcal{M}})$ satisfies Eq. 17 forms a subset of Lebesgue measure 0 in the $M\times(S-1)$-dimensional space.

(3) When $\mathrm{rank}(\Lambda)=0$, we have

$$ $\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{2}}\right)^{-1}{\mathbf{E}}^{\pi_{2} }-\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)^{-1}{\mathbf{E}}^{\pi_{ 1}}={\bm{0}}.$ $$

Plugging ${\mathbf{E}}^{\pi}=\mathbf{r}^{\pi}({\mathcal{M}})+\gamma{\mathbf{P}}^{\pi}({
\mathcal{M}})\tilde{{\mathbf{V}}}$ into the above equation and rearrange it, we have

$$ $\mathbf{r}^{\pi_{2}}({\mathcal{M}})=\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{ 2}}\right)\left({\mathbf{I}}_{M}-{\mathbf{F}}^{\pi_{1}}\right)^{-1}\left( \mathbf{r}^{\pi_{1}}({\mathcal{M}})+\gamma{\mathbf{P}}^{\pi_{1}}({\mathcal{M}} )\tilde{{\mathbf{V}}}\right)-\gamma{\mathbf{P}}^{\pi_{2}}({\mathcal{M}})\tilde {{\mathbf{V}}}.$ $$

When ${\mathbf{P}}$ and ${\bm{r}}^{\pi_{1}}({\mathcal{M}})$ are given, $\mathbf{r}^{\pi_{2}}({\mathcal{M}})$ has only one solution.
Hence, the solution space of ${\bm{r}}^{\pi_{2}}({\mathcal{M}})$ that satisfies Eq. 17 has dimension 0, while the ambient space where ${\bm{r}}^{\pi_{2}}({\mathcal{M}})$ resides has dimension $M\times D$. The dimension of the solution space is significantly lower than that of the full space. Therefore, according to results from measure theory, the set of points where ${\bm{r}}^{\pi_{2}}({\mathcal{M}})$ satisfies Eq. 17 forms a subset of Lebesgue measure 0 in the $M\times D$-dimensional space.

∎

###### Theorem 4 .

Given a finite MDP $(\mathcal{S},\mathcal{A},{\mathbf{P}},{\bm{r}},\gamma)$, where ${\mathbf{P}}$ is the transition probability kernel and ${\bm{r}}\geq 0$ is the reward function.
The ending notes for any edges on ${\mathbb{B}}({\mathbb{J}}(\mu))$ are deterministic policies and only differ in one state-action pair almost surely.

###### Proof.

Suppose $\pi_{1}$ and $\pi_{2}$ are two neighbouring vertices in ${\mathbb{J}}(\mu)$.
By Lemma 1, $\pi_{1}$ and $\pi_{2}$ that are vertices of ${\mathbb{J}}(\mu)$ are deterministic policies.

Lemma 18 shows that the edge connecting $\pi_{1}$ and $\pi_{2}$ can only be formed by the long-term return of policies that are convex combination of $\pi_{1}$ and $\pi_{2}$, that is,

$$ $\{\alpha J^{\pi_{1}}(\mu)+(1-\alpha)J^{\pi_{1}}(\mu)\mid\alpha\in[0,1]\}=\{J^{ \beta\pi_{1}+(1-\beta)\pi_{2}}(\mu)\mid\beta\in[0,1]\}.$ $$

However, if $d(\pi_{1},\pi_{2})>1$, Lemma 19 shows that it is almost surely that

$$ $\{\alpha J^{\pi_{1}}(\mu)+(1-\alpha)J^{\pi_{1}}(\mu)\mid\alpha\in[0,1]\}\neq\{ J^{\beta\pi_{1}+(1-\beta)\pi_{2}}(\mu)\mid\beta\in[0,1]\}.$ $$

This leads to a contradiction. Therefore, we must have $d(\pi_{1},\pi_{2})=1$. This concludes the proof.
∎

###### Theorem 5 .

Let ${\mathbb{C}}$ be a convex polytope, and let ${\mathbb{V}}$ be the set of vertices of ${\mathbb{C}}$. Let ${\mathbb{P}}$ denote the Pareto front of ${\mathbb{C}}$, with ${\mathbb{V}}({\mathbb{P}})$ and ${\mathbb{F}}({\mathbb{P}})$ representing the set of vertices and faces on the Pareto front, respectively. Let ${\mathbb{V}}_{P}\subseteq{\mathbb{V}}({\mathbb{P}})$ and ${\mathbb{F}}_{P}\subseteq{\mathbb{F}}({\mathbb{P}})$ be subsets of the vertices and faces of the Pareto front, such that every face in ${\mathbb{F}}_{P}$ is composed of vertices in ${\mathbb{V}}_{P}$. Given a set of vertices ${\mathbb{T}}\subseteq{\mathbb{V}}$ such that ${\mathbb{V}}_{P}\subseteq{\mathbb{T}}$, then ${\mathbb{F}}_{P}\subseteq{\mathbb{F}}(\mathrm{Conv}({\mathbb{T}}))$.

###### Proof.

Pick a face $F$ from ${\mathbb{F}}_{P}$. By Lemma 7, $F$ is also on the boundary of ${\mathbb{C}}$. Since the vertices of $F$ belong to ${\mathbb{V}}_{P}$, we can express $F$ as:

$$ $F={\mathbb{P}}\cap\{{\bm{x}}\in\mathbb{R}^{d}:{\bm{w}}^{\top}{\bm{x}}=c\},$ $$

where and ${\bm{w}}^{\top}{\bm{x}}\leq c$ for all ${\bm{x}}\in{\mathbb{C}}$. Moreover, since $F$ is on the Pareto front, we have ${\bm{w}}>0$.

Given that ${\mathbb{V}}_{P}\subseteq{\mathbb{T}}$, $F$ is a slice of the convex polytope $\mathrm{Conv}({\mathbb{T}})$. $F$ is a valid face of $\mathrm{Conv}({\mathbb{T}})$ only if ${\bm{w}}^{\top}{\bm{x}}\leq c$ for all ${\bm{x}}\in\mathrm{Conv}({\mathbb{T}})$.

We proceed by contradiction. Suppose there exists ${\bm{x}}\in\mathrm{Conv}({\mathbb{T}})$ such that ${\bm{w}}^{\top}{\bm{x}}>c$. Since ${\mathbb{T}}\subseteq{\mathbb{V}}$ and ${\mathbb{C}}=\mathrm{Conv}({\mathbb{V}})$, it follows that $\mathrm{Conv}({\mathbb{T}})\subseteq{\mathbb{C}}$. This would imply that ${\bm{w}}^{\top}({\bm{x}}-{\bm{y}})>0$ for some ${\bm{y}}\in F$ and ${\bm{x}}\in{\mathbb{C}}$. As ${\bm{w}}>0$, by Lemma 8, this would imply that ${\bm{x}}$ dominates ${\bm{y}}$, which contradicts the assumption that ${\bm{y}}$ is a Pareto optimal point of ${\mathbb{C}}$. Therefore, no such ${\bm{x}}$ can exist, and $F$ is a valid face of $\mathrm{Conv}({\mathbb{T}})$.

Thus, we conclude that ${\mathbb{F}}_{P}\subseteq{\mathbb{F}}(\mathrm{Conv}({\mathbb{T}}))$.
∎

Consider a special case of Theorem 5 when ${\mathbb{V}}_{P}={\mathbb{V}}({\mathbb{P}})$ and ${\mathbb{F}}_{P}={\mathbb{F}}({\mathbb{P}})$, we have the following proposition.

###### Proposition 2 .

Let ${\mathbb{C}}$ be a convex polytope, and let ${\mathbb{V}}$ be the set of vertices of ${\mathbb{C}}$. Let ${\mathbb{P}}$ denote the Pareto front of ${\mathbb{C}}$, with ${\mathbb{V}}({\mathbb{P}})$ and ${\mathbb{F}}({\mathbb{P}})$ representing the set of vertices and faces on the Pareto front, respectively. Given a set of vertices ${\mathbb{T}}\subseteq{\mathbb{V}}$ such that ${\mathbb{V}}({\mathbb{P}})\subseteq{\mathbb{T}}$, then ${\mathbb{F}}({\mathbb{P}})\subseteq{\mathbb{F}}(\mathrm{Conv}({\mathbb{T}}))$.

###### Lemma 16 .

###### Proof.

###### Lemma 17 .

###### Proof.

###### Lemma 18 .

###### Proof.

###### Definition 2 .

###### Lemma 19 .

###### Proof.

###### Theorem 4 .

###### Proof.

###### Theorem 5 .

###### Proof.

###### Proposition 2 .

## Appendix E Sufficiency of Traversing over Edges

###### Lemma 20 .

(Existence of Neighborhood Edges on Pareto front of ${\mathbb{J}}(\mu)$)
Suppose ${\mathbb{J}}(\mu)$ contains multiple Pareto optimal vertices. Let $\pi$ be a Pareto optimal policy, and let $\mathrm{N}(J^{\pi}(\mu),{\mathbb{J}}(\mu))$ represent all neighboring points of $J^{\pi}(\mu)$ on the boundary of ${\mathbb{J}}(\mu)$. Then, there exists $J\in\mathrm{N}(J^{\pi}(\mu),{\mathbb{J}}(\mu))$ such that the edge connecting $J$ and $J^{\pi}(\mu)$ lies on the Pareto front.

###### Proof.

By Lemma 1, ${\mathbb{J}}(\mu)$ is a convex polytope. Given $J\in\mathrm{N}(J^{\pi}(\mu),{\mathbb{J}}(\mu))$, $J$ and $J^{\pi_{1}}(\mu)$ are neighboring vertices on ${\mathbb{J}}(\mu)$, and the edge between $J$ and $J^{\pi_{1}}(\mu)$ is a $1$-dimensional face of ${\mathbb{J}}(\mu)$. By the definition of Definition 1, there exists a vector ${\bm{w}}_{J}$ such that ${\bm{w}}_{J}^{\top}J^{\pi_{1}}(\mu)={\bm{w}}_{J}^{\top}J$, and for any ${\bm{x}}\in{\mathbb{J}}(\mu)$ that not on the edge between $J$ and $J^{\pi_{1}}(\mu)$, we have ${\bm{w}}_{J}^{\top}J>{\bm{w}}_{J}^{\top}{\bm{x}}$.

###### Lemma 20 .

###### Proof.

#### We first prove that there exists J ∈ N ⁢ ( J π ⁢ ( μ ) , 𝕁 ⁢ ( μ ) ) 𝐽 N superscript 𝐽 𝜋 𝜇 𝕁 𝜇 J\in\mathrm{N}(J^{\pi}(\mu),{\mathbb{J}}(\mu)) italic_J ∈ roman_N ( italic_J start_POSTSUPERSCRIPT italic_π end_POSTSUPERSCRIPT ( italic_μ ) , blackboard_J ( italic_μ ) ) such that 𝒘 J > 𝟎 subscript 𝒘 𝐽 0 {\bm{w}}_{J}>{\bm{0}} bold_italic_w start_POSTSUBSCRIPT italic_J end_POSTSUBSCRIPT > bold_0 .

We prove this by contradiction. Assume that for every $J\in\mathrm{N}(J^{\pi}(\mu),{\mathbb{J}}(\mu))$, there does not exist ${\bm{w}}_{J}>{\bm{0}}$.

By the definition of the Pareto front, if $J^{\pi}(\mu)$ is not strictly dominated by $J$, meaning that $J^{\pi}(\mu)$ is greater than or equal to $J$ in some dimensions and strictly smaller in others, then there must exist a positive vector ${\bm{w}}_{J}>{\bm{0}}$. Hence, if for every $J\in\mathrm{N}(J^{\pi}(\mu),{\mathbb{J}}(\mu))$, ${\bm{w}}_{J}>{\bm{0}}$ does not exist, it implies that either $J^{\pi}(\mu)$ is strictly dominated by $J$ or $J$ is strictly dominated by $J^{\pi}(\mu)$.
Since $J^{\pi}(\mu)$ is on the Pareto front, no point in ${\mathbb{J}}(\mu)$ can strictly dominate $J^{\pi}(\mu)$. Therefore, it must be the case that $J$ is strictly dominated by $J^{\pi}(\mu)$ for all $J\in\mathrm{N}(J^{\pi}(\mu),{\mathbb{J}}(\mu))$. This implies that for all $J\in\mathrm{N}(J^{\pi}(\mu),{\mathbb{J}}(\mu))$ and any ${\bm{w}}>{\bm{0}}$, we have ${\bm{w}}^{\top}(J-J^{\pi_{1}}(\mu))<0$.

We then show that $J^{\pi}(\mu)$ dominates every point within ${\mathbb{J}}(\mu)$.
For any point ${\bm{x}}\in{\mathbb{J}}(\mu)$, we can express ${\bm{x}}$ as a linear combination of $J^{\pi}(\mu)$ and the neighboring points in $\mathrm{N}(J^{\pi}(\mu),{\mathbb{J}}(\mu))$ with non-negative weight vector $\boldsymbol{\alpha}$:

$$ ${\bm{x}}=J^{\pi}(\mu)+\sum_{J_{i}\in\mathrm{N}(J^{\pi}(\mu),{\mathbb{J}}(\mu)) }\boldsymbol{\alpha}_{i}(J_{i}-J^{\pi}(\mu)).$ $$

Consider any such point ${\bm{x}}$ and any vector ${\bm{w}}>{\bm{0}}$. We have:

$$ $\displaystyle{\bm{w}}^{\top}({\bm{x}}-J^{\pi}(\mu))$ $\displaystyle={\bm{w}}^{\top}\left(J^{\pi}(\mu)+\sum_{J_{i}\in\mathrm{N}(J^{ \pi}(\mu),{\mathbb{J}}(\mu))}\boldsymbol{\alpha}_{i}(J_{i}-J^{\pi}(\mu))-J^{ \pi}(\mu)\right)$ $\displaystyle={\bm{w}}^{\top}\left(\sum_{J_{i}\in\mathrm{N}(J^{\pi}(\mu),{ \mathbb{J}}(\mu))}\boldsymbol{\alpha}_{i}(J_{i}-J^{\pi_{1}}(\mu))\right)$ $\displaystyle=\sum_{J_{i}\in\mathrm{N}(J^{\pi}(\mu),{\mathbb{J}}(\mu))} \boldsymbol{\alpha}_{i}{\bm{w}}^{\top}(J_{i}-J^{\pi_{1}}(\mu))$ $\displaystyle<0.$ $$

where the last inequality is because ${\bm{w}}^{\top}(J_{i}-J^{\pi_{1}}(\mu))<0$ for any $J_{i}\in\mathrm{N}(J^{\pi}(\mu),{\mathbb{J}}(\mu))$ from previous analysis and $\boldsymbol{\alpha}>{\bm{0}}$ component-wisely.

This implies that $J^{\pi}(\mu)$ dominates every point within ${\mathbb{J}}(\mu)$. However, this contradicts the condition that the multi-objective MDP has more than one deterministic Pareto optimal policy.
Hence, our assumption is wrong and there exists $J\in\mathrm{N}(J^{\pi}(\mu),{\mathbb{J}}(\mu))$ such that ${\bm{w}}_{J}>{\bm{0}}$.

#### We next show that J 𝐽 J italic_J , as well as the edge between J 𝐽 J italic_J and J π 1 ⁢ ( μ ) superscript 𝐽 subscript 𝜋 1 𝜇 J^{\pi_{1}}(\mu) italic_J start_POSTSUPERSCRIPT italic_π start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT end_POSTSUPERSCRIPT ( italic_μ ) , is on the Pareto front.

Since there exists a $\mathbf{w}_{J}>0$ such that $\mathbf{w}_{J}^{\top}(J-{\bm{x}})\geq{\bm{0}}$ for any ${\bm{x}}\in{\mathbb{J}}(\mu)$, it follows Lemma 8 that $J$ is also Pareto optimal. Moreover, the convex combination of $J$ and $J^{\pi_{1}}(\mu)$, written as $\alpha J+(1-\alpha)J^{\pi_{1}}(\mu)$ with $0\leq\alpha\leq 1$, is also a solution to the linear scalarization problem with weight vector ${\bm{w}}_{J}>0$. Hence, the convex combination of $J$ and $J^{\pi_{1}}(\mu)$, i.e., the edge connecting $J$ and $J^{\pi_{1}}(\mu)$, is not strictly dominated by any point in ${\mathbb{J}}(\mu)$ and thus lies on Pareto front.
∎

## Appendix F Locality Property of boundary of 𝕁 ⁢ ( μ ) 𝕁 𝜇 {\mathbb{J}}(\mu) blackboard_J ( italic_μ ) and Pareto front

This section provides the proofs for locality properties of the boundary of ${\mathbb{J}}(\mu)$ and the Pareto front.
We will ignore the initial state distribution $\mu$ in this section for simplicity of notations.

Before presenting the proofs, we first recall some key notations.
We denote the set of long-term returns by policies in $\Pi$ as ${\mathbb{J}}(\mu)$.
By Lemma 1, ${\mathbb{J}}$ is a convex polytope and vertices are the long-return of deterministic policies.
Given a polytope ${\mathbb{C}}$ and a vertex on the polytope ${\bm{x}}$, we denote the set of neighbors on the polytope to ${\bm{x}}$ as $\mathrm{N}({\bm{x}},{\mathbb{C}})$.
Suppose deterministic policy $\pi$ whose long term return $J^{\pi}$ is a vertex on ${\mathbb{J}}$, denote the set of deterministic policy whose long-term returns composes $\mathrm{N}(J^{\pi},{\mathbb{J}})$ as $\mathrm{N}_{\pi}(J^{\pi},{\mathbb{J}})$.
Let $\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\})$ be the convex hull constructed by $J^{\Pi_{1}}\cup\{J^{\pi}\}$. We denote the set of deterministic policies whose long-term returns compose $\mathrm{N}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))$ as $\mathrm{N}_{\pi}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))$.
Let $\Pi_{1}(\pi)$ be the set of deterministic policies that differ from $\pi$ by only one state-action pair.

###### Theorem 6 .

Let the long-term return of deterministic policy $\pi$, i.e., $J^{\pi}$, be a vertex on ${\mathbb{J}}$. Then, $\mathrm{N}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))=\mathrm{N}(J^{
\pi},{\mathbb{J}})$ and $\mathrm{N}_{\pi}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))=\mathrm{N}
_{\pi}(J^{\pi},{\mathbb{J}})$.

###### Proof.

It is enough to get $\mathrm{N}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))=\mathrm{N}(J^{
\pi},{\mathbb{J}})$ from $\mathrm{N}_{\pi}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))=\mathrm{N}
_{\pi}(J^{\pi},{\mathbb{J}})$, so we will focus on proving $\mathrm{N}_{\pi}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))=\mathrm{N}
_{\pi}(J^{\pi},{\mathbb{J}})$.

We will prove $\mathrm{N}_{\pi}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))=\mathrm{N}
_{\pi}(J^{\pi},{\mathbb{J}})$ in two steps: first prove $\mathrm{N}_{\pi}(J^{\pi},{\mathbb{J}})\subseteq\mathrm{N}_{\pi}(J^{\pi},
\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))$, and then prove $\mathrm{N}_{\pi}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))\subseteq
\mathrm{N}_{\pi}(J^{\pi},{\mathbb{J}})$.

###### Theorem 6 .

###### Proof.

#### (1) N π ⁢ ( J π , 𝕁 ) ⊆ N π ⁢ ( J π , Conv ⁢ ( J Π 1 ∪ { J π } ) ) subscript N 𝜋 superscript 𝐽 𝜋 𝕁 subscript N 𝜋 superscript 𝐽 𝜋 Conv superscript 𝐽 subscript Π 1 superscript 𝐽 𝜋 \mathrm{N}_{\pi}(J^{\pi},{\mathbb{J}})\subseteq\mathrm{N}_{\pi}(J^{\pi},%
\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\})) roman_N start_POSTSUBSCRIPT italic_π end_POSTSUBSCRIPT ( italic_J start_POSTSUPERSCRIPT italic_π end_POSTSUPERSCRIPT , blackboard_J ) ⊆ roman_N start_POSTSUBSCRIPT italic_π end_POSTSUBSCRIPT ( italic_J start_POSTSUPERSCRIPT italic_π end_POSTSUPERSCRIPT , roman_Conv ( italic_J start_POSTSUPERSCRIPT roman_Π start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT end_POSTSUPERSCRIPT ∪ { italic_J start_POSTSUPERSCRIPT italic_π end_POSTSUPERSCRIPT } ) ) .

We prove this by contradiction.
Suppose there exists a deterministic policy $u$ such that $u\in\mathrm{N}_{\pi}(J^{\pi},{\mathbb{J}})$ and $u\notin\mathrm{N}_{\pi}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))$.

Suppose $u\in\Pi_{1}(\pi)$. Since $u\in\mathrm{N}_{\pi}(J^{\pi},{\mathbb{J}})$, $J^{u}$ lies above all the facets formed by $J^{\pi}$ and the long-term return of other policies, including the policies in $\Pi_{1}(\pi)$. Since $u\in\Pi_{1}(\pi)$, then $J^{u}$ would also belong to $\mathrm{N}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))$ by the definition of the convex hull, contradicting the assumption that $J^{u}\notin\mathrm{N}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))$. Hence, $u\notin\Pi_{1}(\pi)$.

Thus, $u\in\mathrm{N}_{\pi}(J^{\pi},{\mathbb{J}})$ and $u\notin\Pi_{1}(\pi)$ simutaneously, which contradicts Theorem 4 that $\mathrm{N}_{\pi}(J^{\pi},{\mathbb{J}})\subseteq\Pi_{1}(\pi)$ almost surely. This causes a contradiction, and therefore, $\mathrm{N}_{\pi}(J^{\pi},{\mathbb{J}})\subseteq\mathrm{N}_{\pi}(J^{\pi},
\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))$.

#### (2) N π ⁢ ( J π , Conv ⁢ ( J Π 1 ∪ { J π } ) ) ⊆ N π ⁢ ( J π , 𝕁 ) subscript N 𝜋 superscript 𝐽 𝜋 Conv superscript 𝐽 subscript Π 1 superscript 𝐽 𝜋 subscript N 𝜋 superscript 𝐽 𝜋 𝕁 \mathrm{N}_{\pi}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))\subseteq%
\mathrm{N}_{\pi}(J^{\pi},{\mathbb{J}}) roman_N start_POSTSUBSCRIPT italic_π end_POSTSUBSCRIPT ( italic_J start_POSTSUPERSCRIPT italic_π end_POSTSUPERSCRIPT , roman_Conv ( italic_J start_POSTSUPERSCRIPT roman_Π start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT end_POSTSUPERSCRIPT ∪ { italic_J start_POSTSUPERSCRIPT italic_π end_POSTSUPERSCRIPT } ) ) ⊆ roman_N start_POSTSUBSCRIPT italic_π end_POSTSUBSCRIPT ( italic_J start_POSTSUPERSCRIPT italic_π end_POSTSUPERSCRIPT , blackboard_J ) .

We again proceed by contradiction. Suppose there exists a policy $v$ such that $v\in\mathrm{N}_{\pi}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))$ and $v\notin\mathrm{N}_{\pi}(\pi,{\mathbb{J}})$.
We denote the straight line between $J^{v}$ and $J^{\pi}$ as $E(J^{v},J^{\pi})$.
Since $v\in\mathrm{N}_{\pi}(\pi,\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))$, $E(J^{v},J^{\pi})$ is an edge of $\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))$, implying $E(J^{\tilde{\pi}},J^{\pi})$ cannot lie below all facets whose vertices are $J^{\pi}$ and long-term returns of policies belonging to $\mathrm{N}_{\pi}(\pi,\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))$.

Given the condition that $v\notin\mathrm{N}_{\pi}(\pi,{\mathbb{J}})$, it follows that $E(J^{v},J^{\pi})$ is not on the boundary of ${\mathbb{J}}$, that is, $E(J^{v},J^{\pi})$ lies below all facets of ${\mathbb{J}}$, including the facets whose vertices correspond to $\pi$ and policies belonging to $\mathrm{N}_{\pi}(\pi,{\mathbb{J}})$.
By $\mathrm{N}_{\pi}(J^{\pi},{\mathbb{J}})\subseteq\mathrm{N}_{\pi}(J^{\pi},
\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))$ from (1), we have that $E(J^{v},J^{\pi})$ also lies below all facets whose vertices are $J^{\pi}$ and the long-term returns of policies belonging to $\mathrm{N}_{\pi}(\pi,\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))$.
This contradicts the fact that $E(J^{\tilde{\pi}},J^{\pi})$ cannot lie below all facets whose vertices are $J^{\pi}$ and long-term returns of policies belonging to $\mathrm{N}_{\pi}(\pi,\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))$.

The assumption that there exists a policy $v$ such that $v\in\mathrm{N}_{\pi}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))$ and $v\notin\mathrm{N}_{\pi}(\pi,{\mathbb{J}})$ leads a contradiction. Hence, $\mathrm{N}_{\pi}(\pi,\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))\subseteq
\mathrm{N}_{\pi}(\pi,{\mathbb{J}})$.

Combining steps (1) and (2), we have $\mathrm{N}_{\pi}(\pi,\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))=\mathrm{N}_{
\pi}(\pi,{\mathbb{J}})$ and $\mathrm{N}(\pi,\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))=\mathrm{N}(\pi,{
\mathbb{J}})$. This concludes the proof.
∎

###### Lemma 21 .

Let ${\mathbb{P}}$ be a convex polytope, and let ${\bm{x}}$ be a vertex of ${\mathbb{P}}$. Denote by ${\mathbb{V}}$ the set of all vertices of ${\mathbb{P}}$ that are neighbors to ${\bm{x}}$. Let ${\mathbb{C}}$ be the convex hull constructed by ${\mathbb{V}}\cup\{{\bm{x}}\}$, i.e., $\mathrm{Conv}({\mathbb{V}}\cup\{{\bm{x}}\})$, where ${\mathbb{V}}\cup\{{\bm{x}}\}$ are the vertices of ${\mathbb{C}}$. Then, the set of faces of ${\mathbb{P}}$ that intersect at ${\bm{x}}$, denoted as ${\mathbb{F}}({\bm{x}},{\mathbb{P}})$, is the same as the set of faces of ${\mathbb{C}}$ that intersect at ${\bm{x}}$, denoted as ${\mathbb{F}}({\bm{x}},{\mathbb{C}})$, i.e., ${\mathbb{F}}({\bm{x}},{\mathbb{P}})={\mathbb{F}}({\bm{x}},{\mathbb{C}})$.

###### Proof.

We will prove the two set inclusions: ${\mathbb{F}}({\bm{x}},{\mathbb{P}})\subseteq{\mathbb{F}}({\bm{x}},{\mathbb{C}})$ and ${\mathbb{F}}({\bm{x}},{\mathbb{C}})\subseteq{\mathbb{F}}({\bm{x}},{\mathbb{P}})$.

(1) ${\mathbb{F}}({\bm{x}},{\mathbb{P}})\subseteq{\mathbb{F}}({\bm{x}},{\mathbb{C}})$.

Suppose $F$ is a face in ${\mathbb{F}}({\bm{x}},{\mathbb{P}})$. Then, there exists a vector ${\bm{w}}$ and a scalar $c$ such that ${\bm{w}}^{\top}{\bm{x}}=c$, and the face can be written as $F={\mathbb{P}}\cap\{{\bm{z}}\in\mathbb{R}^{d}:{\bm{w}}^{\top}{\bm{z}}=c\}$, where the vertices of $F$ are a subset of ${\mathbb{V}}$. Since ${\mathbb{C}}$ is the convex hull constructed by ${\mathbb{V}}\cup\{{\bm{x}}\}$, $F$ is a slice contained in ${\mathbb{C}}$.

For $F$ to be a valid face of ${\mathbb{C}}$, it must satisfy ${\bm{w}}^{\top}{\bm{z}}\leq c$ for all ${\bm{z}}\in{\mathbb{C}}$. We prove this by contradiction: suppose there exists ${\bm{y}}\in{\mathbb{C}}$ such that ${\bm{w}}^{\top}{\bm{y}}>c$. Therefore, ${\bm{y}}$ lies above all points in ${\mathbb{P}}$ in the direction of ${\bm{w}}$. Since ${\mathbb{C}}$ is a subset of ${\mathbb{P}}$ (because ${\mathbb{C}}$ is the convex hull of a subset of the vertices of ${\mathbb{P}}$), this would imply that ${\bm{y}}$ lies above all points in ${\mathbb{C}}$ in the direction of ${\bm{w}}$, which contradicts the assumption that ${\bm{y}}\in{\mathbb{C}}$.

Therefore, $F$ is also a valid face of ${\mathbb{C}}$, implying ${\mathbb{F}}({\bm{x}},{\mathbb{P}})\subseteq{\mathbb{F}}({\bm{x}},{\mathbb{C}})$.

(2) ${\mathbb{F}}({\bm{x}},{\mathbb{C}})\subseteq{\mathbb{F}}({\bm{x}},{\mathbb{P}})$.

The argument is analogous to part (1). Suppose $F$ is a face of ${\mathbb{C}}$ that intersects at ${\bm{x}}$. Then $F$ can be written as $F={\mathbb{C}}\cap\{{\bm{y}}\in\mathbb{R}^{d}:{\bm{w}}^{\top}{\bm{y}}=c\}$, where ${\bm{w}}^{\top}{\bm{x}}=c$, and ${\bm{w}}^{\top}{\bm{y}}\leq c$ for any ${\bm{y}}\in{\mathbb{C}}$. With the same analysis as in (1), $F$ is a slice contained in ${\mathbb{C}}$. Since any point ${\bm{z}}\in{\mathbb{P}}$ can be expressed as a linear combination of ${\bm{x}}$ and its neighboring vertices ${\bm{v}}_{i}\in{\mathbb{V}}$, we have:

$$ ${\bm{w}}^{\top}{\bm{z}}={\bm{w}}^{\top}\left({\bm{x}}+\sum_{i}\alpha_{i}({\bm{ v}}_{i}-{\bm{x}})\right)\leq c,$ $$

where $\alpha_{i}>0$, and ${\bm{w}}^{\top}{\bm{x}}=c$ and ${\bm{w}}^{\top}{\bm{v}}_{i}\leq c$. Therefore, $F$ is also a face of ${\mathbb{P}}$.

Combining (1) and (2), we conclude that ${\mathbb{F}}({\bm{x}},{\mathbb{P}})={\mathbb{F}}({\bm{x}},{\mathbb{C}})$.
∎

###### Proposition 3 .

Let the long-term return of deterministic policy $\pi$, i.e., $J^{\pi}$, be a vertex on ${\mathbb{J}}$. Let ${\mathbb{F}}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\})$ be the set of faces of the convex hull constructed by $J^{\Pi_{1}}\cup\{J^{\pi}\}$ that intersect at $J^{\pi}$. Similarly, let ${\mathbb{F}}(J^{\pi},{\mathbb{J}})$ be the set of faces of ${\mathbb{J}}$ that intersect at $J^{\pi}$. Then, ${\mathbb{F}}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))={\mathbb{F}}(J
^{\pi},{\mathbb{J}})$.

###### Proof.

By Theorem 6, we know that $\mathrm{N}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))=\mathrm{N}(J^{
\pi},{\mathbb{J}})$. According to Lemma 21, if two sets of vertices have the same set of neighbor vertices, then the sets of faces formed by those vertices are identical. Hence, we conclude that ${\mathbb{F}}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))={\mathbb{F}}(J
^{\pi},{\mathbb{J}})$.
∎

###### Proposition 4 .

Let $\pi$ be a policy on the Pareto front of ${\mathbb{J}}$. Let $\Pi_{1,\text{ND}}(\pi)\subseteq\Pi_{1}(\pi)$ be the set of policies belonging to $\Pi_{1}(\pi)$ that are not dominated by any other policies in $\Pi_{1}(\pi)$, and let $\mathrm{N}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$ be the set of neighbors of $J^{\pi}$ in the convex hull constructed by $J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}$. Similarly, let $\mathrm{N}(J^{\pi},\mathbb{P}({\mathbb{J}}))$ be the set of neighbors of $J^{\pi}$ on the Pareto front of ${\mathbb{J}}$. Then we have

$$ $\mathrm{N}(J^{\pi},\mathbb{P}({\mathbb{J}}))\subseteq\mathrm{N}(J^{\pi}, \mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\})).$ $$

###### Proof.

By Lemma 7, the Pareto front lies on the boundary of ${\mathbb{J}}$. Therefore, the neighbors of $\pi$ on the Pareto front, $\mathrm{N}(J^{\pi},\mathbb{P}({\mathbb{J}}))$, are the intersection of the set of vertices on ${\mathbb{J}}$ neighboring $J^{\pi}$ and the Pareto front. Formally, we have $\mathrm{N}(J^{\pi},\mathbb{P}({\mathbb{J}}))=\mathrm{N}(J^{\pi},{\mathbb{J}})
\cap\mathbb{P}({\mathbb{J}})$.

Define $\text{ND}(\Pi_{1})$ as the set of all policies (including stochastic and deterministic policies) that are not dominated by any other policies in $\Pi_{1}$.
Since the Pareto front consists of the long-term return of policies that are not dominated by any other policies in $\Pi$, it follows that $\mathbb{P}({\mathbb{J}})\subseteq J^{\text{ND}(\Pi_{1})}$. Thus, we have $\mathrm{N}(J^{\pi},\mathbb{P}({\mathbb{J}}))\subseteq\mathrm{N}(J^{\pi},{
\mathbb{J}})\cap J^{\text{ND}(\Pi_{1})}$.

By Theorem 6, we know that $\mathrm{N}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))=\mathrm{N}(J^{
\pi},{\mathbb{J}})$. Therefore, combining with $\mathrm{N}(J^{\pi},\mathbb{P}({\mathbb{J}}))\subseteq\mathrm{N}(J^{\pi},{
\mathbb{J}})\cap J^{\text{ND}(\Pi_{1})}$, we can conclude:

$$ $\mathrm{N}(J^{\pi},\mathbb{P}({\mathbb{J}}))\subseteq\mathrm{N}(J^{\pi}, \mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))\cap J^{\text{ND}(\Pi_{1})}.$ $$

Next, consider any point $J^{u}\in\mathrm{N}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))\cap J^{
\text{ND}(\Pi_{1})}$. By $\mathrm{N}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))\subseteq J^{\Pi_
{1}}$, we have $J^{u}\in J^{\Pi_{1}}\cap J^{\text{ND}(\Pi_{1})}$. This means that $u$ is in $\Pi_{1}(\pi)$ and is not dominated by any policy in $\Pi_{1}(\pi)$, thus $u\in\Pi_{1,\text{ND}}(\pi)$. And since $J^{u}$ is also a vertex of the convex hull constructed by $J^{\Pi_{1}}\cup\{J^{\pi}\}$, it does not lie below all facets formed by the long-term return of any other policies belonging to $\Pi_{1}(\pi)$ and $\pi$. Since $\Pi_{1,\text{ND}}(\pi)\subseteq\Pi_{1}(\pi)$, it follows that $J^{u}$ does not lie below all facets formed by the long-term return of any other policies in $\Pi_{1,\text{ND}}(\pi)$ and $\pi$. Therefore, $J^{u}\in\mathrm{N}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$.
Thus, we have:

$$ $\mathrm{N}(\pi,\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))\cap J^{\text{ND}(\Pi _{1})}\subseteq\mathrm{N}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{ \pi}\})).$ $$

Combining this with the previous result, we conclude:

$$ $\mathrm{N}(J^{\pi},\mathbb{P}({\mathbb{J}}))\subseteq\mathrm{N}(J^{\pi}, \mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\})).$ $$

Then we also have $\mathrm{N}_{\pi}(J^{\pi},\mathbb{P}({\mathbb{J}}))\subseteq\mathrm{N}_{\pi}(J^
{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$.
∎

###### Proposition 5 .

Let $\pi$ be a policy on the Pareto front of ${\mathbb{J}}$. Let $\Pi_{1,\text{ND}}(\pi)\subseteq\Pi_{1}(\pi)$ be the set of policies belonging to $\Pi_{1}(\pi)$ that are not dominated by any other policies in $\Pi_{1}(\pi)$, and let ${\mathbb{F}}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$ be the set of faces of the convex hull constructed by $J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}$ that intersect at $J^{\pi}$. Similarly, let ${\mathbb{F}}(J^{\pi},P({\mathbb{J}}))$ be the set of faces on the Pareto front of ${\mathbb{J}}$ that intersect at $J^{\pi}$. Then, we have:

$$ ${\mathbb{F}}(J^{\pi},P({\mathbb{J}}))\subseteq{\mathbb{F}}(J^{\pi},\mathrm{ Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\})).$ $$

###### Remark 1 .

Note that in this case, the faces of the convex hull $\mathrm{Conv}(\Pi_{1,\text{ND}}\cup\{{\bm{x}}\})$ that intersect at ${\bm{x}}$ may not necessarily lie on ${\mathbb{J}}$. However, we can use the condition $\mathrm{N}(\pi,\mathbb{P}({\mathbb{J}}))\subseteq\mathrm{N}(\pi,\mathrm{Conv}(
\Pi_{1,\text{ND}}))$ from Proposition 4 and the characteristics of the Pareto front from Theorem 5 to show that faces of the convex hull $\mathrm{Conv}(\Pi_{1,\text{ND}}\cup\{{\bm{x}}\})$ that intersect at ${\bm{x}}$ lie on the Pareto front of ${\mathbb{J}}$.

###### Proof.

Since $\mathrm{N}_{\pi}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))
\in\Pi_{D}$, then $\mathrm{N}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))
\subseteq{\mathbb{J}}$.
By Proposition 4, we have $\mathrm{N}(J^{\pi},\mathbb{P}({\mathbb{J}}))\subseteq\mathrm{N}(J^{\pi},
\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$.
By Theorem 5, the set of faces in Pareto front constructed by $J^{\pi}$ and vertices belonging to $\mathrm{N}(J^{\pi},\mathbb{P}({\mathbb{J}}))$ is a subset of the set of faces of the convex hull constructed by $J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}$, i.e., ${\mathbb{F}}(J^{\pi},P({\mathbb{J}}))\subseteq{\mathbb{F}}(J^{\pi},\mathrm{
Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$. This concludes our proof.

∎

###### Proposition 6 .

Let ${\mathbb{F}}_{P}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$ denote the set of faces of ${\mathbb{F}}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$ that satisfying Lemma 3. Then, we have

$$ ${\mathbb{F}}(J^{\pi},P({\mathbb{J}}))={\mathbb{F}}_{P}(J^{\pi},\mathrm{Conv}(J ^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$ $$

###### Proof.

We prove this by two inclusions: ${\mathbb{F}}(J^{\pi},P({\mathbb{J}}))\subseteq{\mathbb{F}}_{P}(J^{\pi},\mathrm
{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$ and ${\mathbb{F}}_{P}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))
\subseteq{\mathbb{F}}(J^{\pi},P({\mathbb{J}}))$.

(1) ${\mathbb{F}}(J^{\pi},P({\mathbb{J}}))\subseteq{\mathbb{F}}_{P}(J^{\pi},\mathrm
{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$.
Let $F\in{\mathbb{F}}(J^{\pi},P({\mathbb{J}}))$.
Since Proposition 5 proves that ${\mathbb{F}}(J^{\pi},P({\mathbb{J}}))\subseteq{\mathbb{F}}(J^{\pi},\mathrm{
Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$, we have $F\in{\mathbb{F}}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$.

Since $F$ is a face on the Pareto front of ${\mathbb{J}}$ and $\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\})$ is a subset of ${\mathbb{J}}$, $F$ is also the Pareto front of $\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\})$.
Therefore, $F$ satisfies Lemma 3 in $\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\})$ and $F\in{\mathbb{F}}_{P}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}
\}))$.
Thus, we have ${\mathbb{F}}(J^{\pi},P({\mathbb{J}}))\subseteq{\mathbb{F}}_{P}(J^{\pi},\mathrm
{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))$.

(2) ${\mathbb{F}}_{P}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\}))
\subseteq{\mathbb{F}}(J^{\pi},P({\mathbb{J}}))$. Let $F\in{\mathbb{F}}_{P}(J^{\pi},\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}
\}))$. By Lemma 8, there exists a weight vector ${\bm{w}}>0$ such that ${\bm{w}}^{\top}({\bm{x}}-{\bm{y}})\geq 0$ for any ${\bm{x}}\in F$ and ${\bm{y}}\in\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\})$. Since $J^{\Pi_{1,\text{ND}}}\subseteq\mathrm{Conv}(J^{\Pi_{1,\text{ND}}}\cup\{J^{\pi}\})$, the inequality also holds for any ${\bm{x}}\in F$ and ${\bm{y}}\in J^{\Pi_{1,\text{ND}}}$.
For any ${\bm{z}}\in J^{\Pi_{1}}$, ${\bm{z}}$ either belongs to $J^{\Pi_{1,\text{ND}}}$ or is dominated by ${\bm{y}}\in J^{\Pi_{1,\text{ND}}}$. In both cases, ${\bm{w}}^{\top}({\bm{x}}-{\bm{z}})\geq 0$ implying ${\bm{x}}$ is not dominated by any ${\bm{z}}\in J^{\Pi_{1}}$.
Thus, $F$ is a Pareto optimal face of $\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\})$.
Suppose that $F$ written as the intersection of $n\geq 1$ facets, i.e., $F=\cap_{i=1}^{n}F_{i}$, where $F_{i}=\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\})\cap\{{\bm{x}}\in\mathbb{R}^{d}
:{\bm{w}}_{i}^{\top}{\bm{x}}=c_{i}\}$, we can express $F$ as:

$$ $F=\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\})\cap\left\{{\bm{x}}\in\mathbb{R}^{d }:\sum_{i}\boldsymbol{\alpha}_{i}{\bm{w}}_{i}^{\top}{\bm{x}}=\sum_{i} \boldsymbol{\alpha}_{i}c_{i}\right\},$ $$

where for any $\boldsymbol{\alpha}\geq 0$. As $F=\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\})\cap\{{\bm{x}}\in\mathbb{R}^{d}:{
\bm{w}}^{\top}{\bm{x}}=c\}$, there exists a non-negative $\boldsymbol{\alpha}$ such that ${\bm{w}}=\sum_{i}\boldsymbol{\alpha}_{i}{\bm{w}}_{i}>{\bm{0}}$. That is, there exists a non-negative linear combination of these facets $\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\})$ that intersects on $J^{\pi}$ such that the linear combination is strictly positive.

As ${\mathbb{F}}(\mathrm{Conv}(J^{\Pi_{1}}\cup\{J^{\pi}\}))={\mathbb{F}}(J^{\pi},{
\mathbb{J}})$ by Proposition 3, there exists a non-negative linear combination of facets of ${\mathbb{F}}(J^{\pi},{\mathbb{J}})$ that intersects on $J^{\pi}$ such that the combination is strictly positive.
By Lemma 3 again, $F\in{\mathbb{F}}(J^{\pi},P({\mathbb{J}}))$.

Combining (1) and (2) concludes the proof.
∎

###### Lemma 21 .

###### Proof.

###### Proposition 3 .

###### Proof.

###### Proposition 4 .

###### Proof.

###### Proposition 5 .

###### Remark 1 .

###### Proof.

###### Proposition 6 .

###### Proof.

## Appendix G Find Pareto front on CCS

By Lemma 9, each nonempty face ${\mathbb{F}}$ of a convex polytope can be written as the intersection of facets $\{{\mathbb{F}}_{i}\}_{i}$, i.e., ${\mathbb{F}}=\cap_{i}({\mathbb{F}}_{i})$.

###### Lemma 22 .

Given a convex polytope ${\mathbb{C}}$, a face ${\mathbb{F}}$ of ${\mathbb{C}}$ lies on the Pareto front if the following conditions hold:

- •
If ${\mathbb{F}}$ is a facet of ${\mathbb{C}}$, i.e., $\text{dim}({\mathbb{F}})=\text{dim}({\mathbb{C}})-1$, and can be written as ${\mathbb{F}}={\mathbb{C}}\cap\{{\bm{x}}\in\mathbb{R}^{d}:{\bm{w}}^{\top}{\bm{x
}}=c_{0}\}$, then ${\mathbb{F}}$ lies on the Pareto front if ${\bm{w}}>{\bm{0}}$.
- •
If $0\leq\text{dim}({\mathbb{F}})<\text{dim}({\mathbb{C}})-1$, and ${\mathbb{F}}$ is the intersection of facets of ${\mathbb{C}}$, i.e., ${\mathbb{F}}=\cap_{i}{\mathbb{F}}_{i}$, where each facet is written as ${\mathbb{F}}_{i}={\mathbb{C}}\cap\{{\bm{x}}\in\mathbb{R}^{d}:{\bm{w}}_{i}^{
\top}{\bm{x}}=c_{i}\}$, then ${\mathbb{F}}$ lies on the Pareto front if there exists a linear combination of the normal vectors with weight vector $\boldsymbol{\alpha}\geq 0$, such that $\sum_{i}\boldsymbol{\alpha}_{i}{\bm{w}}_{i}>0$.

###### Proof.

When ${\mathbb{F}}={\mathbb{C}}\cap\{{\bm{x}}\in\mathbb{R}^{d}:{\bm{w}}^{\top}{\bm{x
}}=c_{0}\}$ is a facet of ${\mathbb{C}}$, by the definition of a valid linear inequality, the inequality ${\bm{w}}^{\top}{\bm{x}}\leq c_{0}$ holds for all points ${\bm{x}}\in{\mathbb{C}}$. Since ${\bm{w}}>0$, for any ${\bm{x}}$ on ${\mathbb{F}}$ and any ${\bm{y}}\in{\mathbb{C}}$, we have ${\bm{w}}^{\top}({\bm{y}}-{\bm{x}})\leq 0$. By Lemma 8, this implies that no point in ${\mathbb{C}}$ dominates ${\bm{x}}$, so ${\mathbb{F}}$ lies on the Pareto front.

When ${\mathbb{F}}$ is a lower-dimensional face of ${\mathbb{C}}$, written as the intersection of $n$ facets, i.e., ${\mathbb{F}}=\cap_{i=1}^{n}{\mathbb{F}}_{i}$, where ${\mathbb{F}}_{i}={\mathbb{C}}\cap\{{\bm{x}}\in\mathbb{R}^{d}:{\bm{w}}_{i}^{
\top}{\bm{x}}=c_{i}\}$, we can express ${\mathbb{F}}$ as:

$$ ${\mathbb{F}}={\mathbb{C}}\cap\left\{{\bm{x}}\in\mathbb{R}^{d}:\sum_{i} \boldsymbol{\alpha}_{i}{\bm{w}}_{i}^{\top}{\bm{x}}=\sum_{i}\boldsymbol{\alpha} _{i}c_{i}\right\},$ $$

where $\boldsymbol{\alpha}\geq 0$. Since $\sum_{i}\boldsymbol{\alpha}_{i}{\bm{w}}_{i}>0$, for any ${\bm{x}}$ on ${\mathbb{F}}$ and any ${\bm{y}}\in{\mathbb{C}}$, there exists a vector ${\bm{w}}>0$ such that ${\bm{w}}^{\top}({\bm{y}}-{\bm{x}})\leq 0$. Therefore, by Lemma 8, no point in ${\mathbb{C}}$ strictly dominates ${\bm{x}}$, and ${\mathbb{F}}$ lies on the Pareto front.
∎

###### Remark 2 .

(3D case) When $d=3$, if the convex combination of the normal vectors of all facets adjacent to an edge points towards the interior of ${\mathbb{C}}$, then the edge lies on the Pareto front.

###### Lemma 23 .

Let $F$ be a face of ${\mathbb{J}}$, and let $\Pi_{F}$ be the set of deterministic policies corresponding to the vertices of $F$. Then $F$ can be constructed by the long-term returns of the convex combinations of $\Pi_{F}$, i.e.,

$$ $F=\left\{J^{\pi}\middle|\pi(a|s)=\sum_{\pi_{i}\in\Pi_{F}}\boldsymbol{\alpha}_{ i}\pi_{i}(a|s),\boldsymbol{\alpha}\geq 0,\sum_{i}\boldsymbol{\alpha}_{i}=1 \right\}.$ $$

###### Proof.

By Lemma 1, ${\mathbb{J}}$ is a convex polytope, and its vertices correspond to deterministic policies. Since $F$ is a face of the convex polytope ${\mathbb{J}}$, by the definition of a face, there exist ${\bm{w}}$ and $c$ such that $F=\left\{{\bm{x}}\in\mathbb{R}^{D}\mid{\bm{w}}^{\top}{\bm{x}}=c\right\}\cap{
\mathbb{J}}$,
and for any ${\bm{y}}\in{\mathbb{J}}$, ${\bm{w}}^{\top}{\bm{y}}\leq c$.

Therefore, $\Pi_{F}=\arg\max_{\pi\in\Pi_{D}}{\bm{w}}^{\top}J^{\pi}$, where $\Pi_{D}$ denotes the set of all deterministic policies. By Lemma 13, the convex hull of $\Pi_{D}$, i.e.,
$\left\{\pi\mid\pi(a|s)=\sum_{\pi_{i}\in\Pi_{F}}\boldsymbol{\alpha}_{i}\pi_{i}(
a|s),\boldsymbol{\alpha}\geq 0,\sum_{i}\boldsymbol{\alpha}_{i}=1\right\}$,
constructs all policies (including stochastic and deterministic) that maximize ${\bm{w}}^{\top}J^{\pi}$. Thus, the long-term returns of $\left\{\pi\mid\pi(a|s)=\sum_{\pi_{i}\in\Pi_{F}}\boldsymbol{\alpha}_{i}\pi_{i}(
a|s),\boldsymbol{\alpha}\geq 0,\sum_{i}\boldsymbol{\alpha}_{i}=1\right\}$ construct $F$.
Formally, we have

$$ $F=\left\{J^{\pi}\mid\pi(a|s)=\sum_{\pi_{i}\in\Pi_{F}}\boldsymbol{\alpha}_{i} \pi_{i}(a|s),\boldsymbol{\alpha}\geq 0,\sum_{i}\boldsymbol{\alpha}_{i}=1\right\}.$ $$

This concludes the proof.
∎

###### Lemma 22 .

###### Proof.

###### Remark 2 .

###### Lemma 23 .

###### Proof.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: Could the authors elaborate on potential modifications to improve the algorithm's scalability with larger action and state spaces?
soundness: 3
strengths: 1. The paper takes an original approach to MO-MDPs, revealing geometric properties of the Pareto front that support an efficient search algorithm, standing apart from previous methods that rely on scalarizing preferences or using approximations.
2. The algorithm provides a strong computational edge, needing only one single-objective solution to start, then systematically traversing edges between Pareto-optimal policies—ideal for applications requiring efficient navigation of complex Pareto fronts.
summary: This paper presents an efficient method to identify the exact Pareto front in multi-objective Markov Decision Processes (MO-MDPs). The authors use the geometric insight that the Pareto front forms on a polytope boundary, allowing for a simplified, localized search by adjusting one state-action pair at a time. This approach keeps computations efficient and complete.
weaknesses: 1. The complexity analysis could benefit from a more detailed comparison with existing algorithms, especially in larger, higher-dimensional state-action spaces. Testing on bigger benchmarks would clarify the algorithm's scalability and relevance for complex MO-MDPs.
2. The experiments use small, artificial setups. Adding tests in larger, more realistic MO-MDP scenarios would better show the algorithm’s practical applicability and effectiveness.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: see weaknesses.
soundness: 3
strengths: - This paper is well written.

- The idea is interesting and novel, and the results are significant.
summary: This paper studies the multi-objective MDPs and explores the properties of their Pareto front. By using the insight that the Pareto front is on the boundary of a convex polytope where each vertex is a deterministic policy, a fast algorithm is designed to compute the Pareto front efficiently.
weaknesses: - The complexity analysis lacks clarity, particularly when compared to other algorithms. A more explicit comparison would significantly improve the discussion.

- The numerical evaluation is restricted to small instances, which are insufficient to demonstrate the scalability of the proposed algorithm.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: Could you give an overview of the difficulties in generalizing your results beyond the ergodicity assumption and describe how it is used in the proofs?

Regarding the benchmark algorithm in Section 5.1, are there situations where the benchmark algorithm has comparable performance to the main algorithm, and what would they look like?
soundness: 3
strengths: I think the paper is written very clearly. In particular the proof sketches are structured in a helpful manner.
The paper makes good use of examples to explain technical points of the algorithm (ex. paragraph around 407).

The paper also seems to make a original and significant contribution to the study of multi-objective MDPs, not just outperforming prior work but also developing a fundamentally different algorithmic approach and presenting useful theoretical/structural results.
summary: The authors provide an algorithm for finding the entire Pareto-optimal front for multi-objective MDPs. Their algorithm is based upon several structural/theoretical observations about the geometry of the Pareto front, relating neighboring vertices of the Pareto front to policies which differ in a single state-action pair. This leads to their local-search-based algorithm, which outperforms baselines and prior approaches.
weaknesses: In other settings the assumption of ergodicity is a significant one. I think this should be highlighted a bit more.

This is subjective but I think the organization of section 3 would be improved if the problem setup (Section 3.2) was provided before the algorithm overview (Section 3.1). (I still think the algorithm overview is very helpful.)

I think the wording of the definition of ergodicity should be clarified. The provided definition sounds similar to the definition of a communicating MDP.

The plots in Figures 5 and 6 are hard to understand due to overlapping curves. I think changing the y-axis scale might be a better solution than the current approach. Also I think the caption of Figure 6 is incorrect? (Should be OLS not benchmark)

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: The evaluation of the algorithm demonstrates its efficiency with state space sizes of 5 and 8, action spaces ranging from 5 to 7, and a reward dimension of 3. If the state and action space cardinalities were significantly larger, would this algorithm remain more efficient compared to others? Specifically, could sampling the preference space be more efficient in certain cases?

Can the algorithm be adapted for use in continuous action spaces?
soundness: 3
strengths: The paper introduces an original contribution to the field by uncovering key geometric properties of the Pareto front in multi-objective Markov Decision Processes.
The paper has good quality, and is supported by theoretical proofs and empirical evidence.
The paper provides a clear explanation of the geometric properties of the Pareto front and a clear demonstration of the proposed algorithm. The paper should ideally explain the empirical setup in more detail.
The paper makes a significant contribution to solving multi-objective MDP problems by offering insights into the geometry of the Pareto front and developing an efficient algorithm for finding the exact Pareto front.
summary: The paper investigates the geometric structure of the Pareto front in multi-objective MDPs and reveals key properties, including that the vertices on the Pareto front correspond to deterministic policies and that neighboring vertices differ by only one state-action pair, almost surely. 
The paper also presents an efficient algorithm that leverages these geometric properties to find the Pareto front, which could reduces the computational complexity compared to existing methods.
The empirical studies demonstrate the proposed algorithm maintains a much better run time than Optimistic Linear Support (OLS).
weaknesses: In the evaluation of the algorithm, more details could be provided about the experiment setting to give context to the results. For instance, specifying the states, actions, transition kernel, reward function, and the number of time steps considered. Also, including a few more benchmark algorithms would help demonstrate the efficiency of the proposed algorithm more effectively.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 2
questions: - The authors have focused on identifying deterministic policies in the Pareto front. What are specific reasons not considering the whole policy space including stochastic policies? 

- What are assumptions about MDPs made in analysis (e.g. finite state/action spaces, ergodicity, etc.)? Can the authors state them in theorems? 

- How sensitive of Algorithm 1 to the accuracy (e.g., errors or approximations in these subroutines) of calling subroutines like line 11, 12, and 13? 

- Can the authors provide some use examples of the entire Pareto front?
soundness: 3
strengths: - The key idea is clearly presented. Compared with the state of the art for multi-objective Markov decision processes, the authors highlight that the proposed method can find the entire Pareto front. 

- The authors derive a few interesting geometric properties of the vector value function: (1) distance one property; (2) sufficiency of traversing over edges; (3) locality property of the Pareto front. I believe this is the main theoretical contribution to the literature. The authors also show how these properties are used to find the entire Pareto front, which is new to me. 
 
- Based on the geometric properties of the Pareto front, the authors develop an efficient Pareto search algorithm. This algorithm initiates with a neighbor search of a deterministic policy, computes incident faces for a convex hull, and then extracts the Pareto front.

- The authors evaluate the performance of the proposed method in an experiment, showing better runtime compared to benchmark.
summary: The paper studies how to find the Pareto front of multi-objective Markov decision processes efficiently.  The authors first show that the Pareto front lies on the boundary of a convex polytope, with vertices representing deterministic policies, and neighboring vertices of the Pareto front differ by only a state-action pair in the deterministic policy. Based on this observation, the authors propose a Pareto front searching algorithm with three key steps: (1) neighbor search; (2) incident faces identification; (3) Pareto face extraction. A major advantage of this method is that the localized search among deterministic policies that differ only one state-action pair significantly reduces the computational burden. The authors also provide some empirical results to show the effectiveness of this proposed method.
weaknesses: - A key contribution is to find the full exact Pareto front for multi-objective MDPs. Although it is of theoretical interest, it is less discussed the practical use of the entire Pareto front, such as multi-objective learning. It would be helpful if the authors could provide some examples that warrant the entire Pareto front. 

- The authors first introduce the algorithm and then the key properties. Without reading Section 4, it is difficult to understand why Algorithm 1 works. It would be helpful to reverse the order of Section 3 and Section 4. 

- The convergence study of Algorithm 1 is not provided. It seems that it is not justified that Algorithm 1 can find the entire Pareto front. Also, the stop criterion and computational complexity are not analyzed.  

- The scalability of Algorithm 1 is not analyzed regarding the size of MDP and dimension of reward. 

- Regarding the properties of the vector value function, it would be helpful if the authors could provide some examples or intuitions behind them. 

- The current analysis seems to be limited to finite MDPs. It would be useful to extending it to MDPs with continuous spaces.

- The example in experiments is artificial. It would be useful if the authors could provide some practical use cases.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Please address the concerns and questions raised in the weaknesses section.
soundness: 3
strengths: * The paper makes a novel theoretical contribution by providing an exact solution method for finding optimal Pareto front in MO-MDPs. The proofs are rigorous, offering valuable insights into the geometric properties of the Pareto front, which could impact other optimization methods for MO-MDPs.
* The method reduces computational complexity compared to OLS, marking a notable advantage in computational efficiency for exact MO-MDP solutions. The iterative nature of the algorithm also suggests it could be more robust and reliable than blind search-based methods.
* The writing is clear and well-structured with good visual presentations.
summary: The paper proposes an exact method for finding Pareto fronts (in turn Pareto optimal policies) for Multi-Objective Markov Decision Processes (MO-MDPs). Leveraging the geometric properties of the Pareto front, the authors demonstrate that it lies on the boundaries of a convex polytope, with neighboring Pareto front vertices differing by at most one state-action pair. The paper provides proofs showing that every deterministic policy on the Pareto front is connected to at least one deterministic Pareto optimal policy, which can be extracted via the convex hull of a Pareto optimal policy and its neighbors. Building on these findings, the paper introduces a search algorithm for Pareto fronts that requires solving each single objective of the MO-MDP once for initialization, with total iterations bounded by the number of Pareto fronts. The proposed algorithm is evaluated on small MDPs with 5 to 8 states, 5 to 7 actions, and 3 objectives. The benchmark used for comparison is the Optimistic Linear Support (OLS) method, which can find Pareto vertices but not the entire Pareto front. Results indicate that the proposed method can find exact Pareto fronts and is more computationally efficient than the OLS method.
weaknesses: * The practical relevance of finding exact solutions versus approximation is not thoroughly addressed. Since approximate solutions are computationally easier to obtain, the paper could benefit from providing scenarios and discussion where exact solutions are preferred.  Comparisons and discussions against approximation methods, such as those in [1,2], are missing, which could help contextualize the result.
* The experimental evaluation is relatively weak, relying on very small, toy MO-MDPs with only a single benchmark for comparison.  Is there any practical relevance or application of exact solutions to such problems on such small problem sizes?
* The scalability of the algorithm is not adequately discussed. From the results, it seems like running times are negligible for small MDPs, it's unclear how the method performs on larger problems, and when scalability could become an issue. 

[1] Xingchao Liu, Xin Tong, and Qiang Liu. Profiling Pareto front with multi-objective Stein variational gradient descent. Advances in Neural Information Processing Systems, 34:14721–14733, 2021.

[2] Xiaoyuan Zhang, Xi Lin, Bo Xue, Yifan Chen, and Qingfu Zhang. Hypervolume maximization: A geometric view of Pareto set learning. Advances in Neural Information Processing Systems, 36:38902–38929, 2023.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 4
questions: 1. Line 905 says that $\Pi$ can contain non-stationary policies, while Line 684 defines $\Pi$ as a set of stationary policies. I am confused about whether the authors only consider stationary policies or not. Can you explain any intentional differences if they exist?

2. What is $L \Pi_D(\mu)$ in Line 749? Is it $\Pi_D (\mu)$? Or does it mean that the vertices are the occupancy measures of a set of policies $\Pi_D (\mu)$? (If it is a separate concept, the authors should define what $L\Pi$ is.) 

3. To recover “full” exact Pareto front, I believe that the “if” statement in Lemma 3 should be modified to “if and only if” (necessary and sufficient). If you intended to do so, can you modify that? (It seems that Line 409 talks about “only if” part, but it is not accurately stated in the lemma.) If not, please explain why the sufficient conditions are enough to prove the following theorems or propositions.
Also, I cannot locate the proof of Lemma 3.

4. I think the point of Lines 10-11 in Algorithm 2 is to include all normal vectors associated with lower-dimensional faces to apply (1). If that’s the case, shouldn’t Line 4 of Algorithm 2 specify that .pop() be done from high-dimensional faces to lower-dimensional faces (or specify that .push() is done in the order of dimension)? If the order matters, please modify the algorithm accordingly and if it doesn't, please explain why this is the case.

5. It would be better to add relevant existing algorithms in the appendix (e.g. Roijers, PPrune algorithm) for the completeness.

6. It would be better to note the corresponding proof locations below all theorems (e.g. Theorem 2, Proposition 1).

7. In the abstract, it would be better to use MO-MDPs inside the first parenthesis instead of MDPs to understand the 12th line of the abstract (I personally didn't get it at first glance).

I am giving the score of 6 for the current draft, but I am eager to talk with the authors and reconsider the score.
soundness: 4
strengths: I really like the presentation of this paper. Sections 4.1, 4.2, and 4.3 sequentially validate the algorithm in a very clear way. The figures help understand the characterization of the vertices and faces, and the algorithm description is very clear. 
The idea of identifying the vertices as deterministic policies through a linear transformation for Multi-Objective MDPs is impressive.
I believe that the concept of traversing the vertices (deterministic policies) is clearly distinguished from the previous works which typically uses approximation while searching continuous spaces.
summary: This paper is concerned with characterizing optimal Pareto front and a corresponding algorithm to efficiently build the optimal Pareto front for Multi-Objective MDPs. In contrast with the existing works using preference vector and traversing continuous space, this paper characterizes Pareto front using deterministic policies, and elucidating the relationship between neighboring vertices. The authors present the relevant algorithms to extract Pareto optimal faces. The numerical experiments and detailed proofs were provided.
weaknesses: I doubt if the author’s algorithm is really more efficient than the OLS in all cases. Generally, dealing with discrete sets such as the author's approach takes longer than handling continuous sets. I understand that the experiment demonstrates the efficiency of the algorithm, but this was done when S and A are small enough. For example, in Line 496, the author had clarified the complexity of the algorithm which is $O(NS(A-1))$, but if the state/action spaces are large, $S(A-1)$ may be larger than $N$ and it may have a higher complexity than $O(N^2)$. Can you present why the above situation may not be the case? If impossible, I suggest the authors discuss trade-offs between N, S, and A, and preferable scenarios where the algorithm would work well (e.g. propose certain situations where $N$ >> $S(A-1)$ and why).

Meta-review: This paper studies methods for identifying the exact Pareto front in Multi-Objective Markov Decision Processes (MO-MDPs), leveraging novel geometric insights that the Pareto front lies on the boundary of a convex polytope and can be efficiently explored through localized searches among deterministic policies. It presents a new algorithm that is theoretically grounded and computationally efficient, outperforming prior methods like Optimistic Linear Support (OLS) in empirical studies. The reviewers found the paper to be well-written, theoretically novel, and a significant contribution to MO-MDP research, although they suggested clarifying complexity analysis, scalability, and adding practical evaluations. During the rebuttal phase, the reviewers were satisfied with the authors’ detailed responses and updates, leading to a consensus on acceptance.

Decision: Accept (Spotlight)