How to Find the Exact Pareto Front for Multi-Objective MDPs?
Authors: Yining Li
Peizhong Ju
Ness Shroff
Venue: ICLR 2025 Spotlight (2025)
Keywords: Multi-objective optimization
Markov decision Process
Primary area: reinforcement learning

Abstract: Multi-Objective Markov Decision Processes (MO-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, involving both deterministic and stochastic Pareto optimal policies.
By investigating the geometric structure of the Pareto front in MO-MDPs, 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$ iterations, where $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.

Published as a conference paper at ICLR 2025
HOW TO FIND THE EXACT PARETO FRONT FOR MULTI- OBJECTIVE MDPs?
Yining Li Peizhong Ju' ,& Ness Shroff
'Department of Electrical and Computer Engineering, The Ohio State University 'Department of Computer Science, University of Kentucky
*Department of Computer Science and Engineering. The Ohio State University 1i.1231 ww..22122oss...oo peizhong. juêuky. budu, shroff. 11 11@osu.edi
ABSTRACT
Multi-Ohjective Markov Decision Processes (MO-MDPs) are receiving increasing attention, as real-world
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 foundation for finding Pareto optimal solutions that can efficiently adapt 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, involving both deterministic and stochastic Pareto optimal policies. By investigating the geometric structure of the Pareto front in MO-MDPs, we uncover key property: the Pareto front is on the boundary of convex polytope whose vertices all correspond to deterministic policies, and neighboring vertices of the Pareto front differ by only one sate-action pair of the deterministic policy, almost surely. This insight transforms the global comparison across all policies into a localized search, drastically reducing the complexity of searching for the exact Pareto front. We develop efficient algorithm that identifies the vertices of the Pareto front by solving single-objective MDP only once and then traversing the edges of the Pareto front, making it more efficient than existing methods. 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 (Xu et al., 2020b; Rame et al., 2024). 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) (Abdolmaleki et al., 2020; Yang et al., 2019b; Lu et al., 2022; Zhou et al., 2024).
Finding Pareto optimal policies based on specific preferences is often sensitive to the scales of the objectives and struggles to adapt changing preferences (Zhou et al., 2024; Qiu et al., 2024). Accurately capturing true preferences across multiple objectives is challenging, as the balance between objectives can be distorted by differences scale (Ab- dolmaleki al., 2020; Kim al., 2024). When one reward objective has 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 achieve the desired balance across objectives. Additionally, preferences may shift over time, requiring quick adaption to new preferences (Mossalam et al., 2016; Yang et al., 2019 9019;; Jang et al., 2023). In such cases, solving for Pareto optimal policy from scratch using a scalarization- 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.

---

Published as a conference paper at ICLR 2025
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 (Qiu et al., 2024). Although state-of-the 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 (Parisi et al., 2014; Yang et al., 2019a; Lu et al., 2022), these methods still require sampling the continuous preference space to approximate the Pareto front. In cases where the Pareto front contains oow-dimesiiona faces, sampling preference vectors on those faces makes it nearly impossible for approximation methods to identify such edge cases and accurately reconstruct the exact 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 (Roijers, 201 6; Mossalam et al., 2016). 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. la) from the vertices corresponding to deterministic Pareto optimal policies (as in Fig. 1b) 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 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'. Furthermore, we prove that deterministic Pareto optimal policies are connected and all Pareto-optimal faces incident to 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-ohjective optimal policy once for initialization. and the total iteration number is the same as the number of vertices on the Pareto front.
Objartve Rola
Chijstiie Relam
Obgaahe Retinn
Objeatie I Rotum
Objective 2 Retutn
Objective 2 Return
(a) Pareto front
(b) Vertices on Pareto front
Figure 1: Finding Pareto front and Pareto front vertices in MO-MDP
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
For almost all P and 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.
2

---

Published as a conference paper at ICLR 2025
multiple objectives in advance, and the goal is to find a Pareto optimal solution that performs well under these given preferences (Fernando et al., 2023; Chen et al., 2024; Mahapatra & Rajan, 2020; Xiao et al., 2024). The methods addressing this problem in multi-objeccive MDPs are specifically referred to as single-policy methods (Siddique et al., 2020; Peschl et al., 2021; Hwang et al., 2023; Zhou et al., 2024; Qiu et al., 2024). The second category focuses on finding set of (approximate) Pareto optimal solutions that are diverse enough to represent the full range of the Pareto front (Liu et al., 2021; Zhang et al.. 2023; Ye et al., 2024). 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. However, finding the Pareto optimal front in the multi-objective optimization field does not take advantage of the specific structure of MO-MDPs, where multiple objectives share the same state and action spaces, as well as identical transition dynamics. Exploiting this structure in MO-MDPs could potentially lead to significant reductions in computational complexity. This section overviews the methods to get the Pareto optimal front estimation in MO-MDPs and MO-RL.
As early as White (1982), the dynamic programming- based method was proposed to find the optimal Pareto front for MO-MDPs, 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, Mossalam et al. (2016) 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.
Van Moffaert & Nowé (2014) proposed Pareto Q-learning, which learns a set of Pareto optimal policies in the MO-RL setting. Building this, subsequent work has investigated training universal Pareto optimal policy set. where the policy network takes preference embedding as input and outputs the corresponding Pareto optimal policy (Yang et al., 2019a; Abels et al., 2019; Zhou et al., 2020; Lu et al., 2022). 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 (Xu et al., 2020a; Basaklar al., 2022). 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 retrain from scratch, they still 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 as the reward dimension increases.
There are also policy-based MORL algorithms designed to find Pareto optimal policies (Chen et al., 2021; Cai et al., 2023: Zhou et al., 2024; Parisi et al., 2014). concept similar to our approach, which directly searches over the Pareto front, is the Pareto followifoloowing algorithm proposed by Parisi et al. (2014). 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 requires multiple policy-gradient steps to identify even a nearby Pareto optimal policy. Furthermore, 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 (Rame et al., 2024; Jang et al., 2023) proposes learning optimal policies for individual preference criteria and linearly interpolating these policies to combine their capabilities. While Rame et al. (2024) 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 general MDPs.
3 PARETO FRONT SEARCHING ON MO-MDP
We begin with introducing to the basic concepts underlying MO-MDPs. Next, we provide an overview of the proposed efficient Pareto front searching algorithm to offer intuition into its workings. Finally, we present a detailed explanation of the algorithm. A proof sketch of the proposed algorithm will be provided in Section 4.
3.1 PRELIMINARIES ON MO-MDP
We consider a discounted finite MO-MDP (S, AS where and A are the sets of states and actions, with cardinalities S and A, respectively. The transition kernel P defines the probability P(s'ls, a) of transitioning from s
to s' given action a. The reward tensor r E SXADD specifies the D-dimensional reward r(s, a) obtained by taking action in state s. 7 < 1 is the discount factor.
Assumption 1. (Sufficient Coverage of the Initial State Distribution) We assume that the initial state distribution p > O. meaning that the probability of starting from any state is larger than zero.
3

---

Published as a conference paper at ICLR 2025
The sufficient coverage of the initial state distribution assumption is commonly used in RL (Agarwal et al., 2020). Define IT as the set of stationary policies, where for any x II, (a]s)) represents the probability of selecting at state 8. The value function with policy is denoted as V*(s)= E R2, which is written as
V (s) = En'r(s(n ae)]s = s, at T-|ss),, 81+1 P(Isst.
We define the long- tere-termmn return of policy as (M) = Es-p() [V]( Let J(u) denote the set of expected long-term returns for all stationary policies under the initial state distribution μt, i.e., I(p) = {J (n)] E IT). For simplicity of notation, we will omit y in the following sections.
is convex as proven in Lu et al. (2022). We further emphasize that J is not only convex but also a convex polytope, with each vertex corresponding to a deterministic policy, as established in Lemma 12.
Lemma 1. In discounted finite MO-MDP, under Assumption 1, J is closed convex polytope, and its vertices are achieved by deterministic policies.
As we investigate the boundary of J, which is a convex polytope, we introduce relevant definitions concerning convex polytopes. Let C S Rdd be a convex polytope. A face of C is any set of the form F C n fx R w x c). where w S for any C. The faces of dimension 0, 1, and dim(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 u and v. u strictly dominates v. denoted as u > v. if each component of u is at least as large as the corresponding component of v, and at least one component is strictly larger. A vector u is Pareto optimal in a set if any other vector v S does not strictly dominate u. The Pureto front of set S, denoted as PP))), is the set of Pareto optimal vectors in S.
In the context of MO-MDP, we say that policy Ti dominates policy T2. denoted as T1 > T2 if J A policy π is Pareto optimal if J is Pareto optimal in J. We similarly define the Pareto front of II as (IIII) { III J e P(J)..
3.2 ALGORITHM OVERVIEW
This section provides an overview of our proposed algorithm for efficiently identifying the entire Pareto front. By using single-objective solver only once 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 be explored. The queue is initialized with a deterministic policy To, derived by solving a single-objective MDP, which is formulated from the original multi-objective MDP using an arbitrary positive preference vector, ensuring that Tg lies on the Pareto front. The obtained policy Tu serves as the starting point for systematically traversing the entire Pareto front.
In each loop. we pop out one element π in the queue Q. The following steps are applied to explore the Pareto front in the neighborhood of и. We also use Fig. 2 to give an illustration of those steps in each loop.
(a) (Neighhor Search) First, we identify and evaluate all deterministic policies that differ from ı by only one state-action pair. From these, we discard any policies whose returns are dominated by returns of others?.
As shown in Fig. 2a, the gray planes and edges represent previously discovered parts of the Pareto front, the black point corresponds to the returns of æ (the deterministic Pareto-optimal policy being explored). and the red points represent the policies that are not dominated among those differing from by only one state-action pair.
(b) (Incident Faces Calculation) Next, we compute the incident faces of the return of on the convex hull formed by the returns of and the policies identified in the first step, i.e., the non-dominated policies among deterministic policies differing from π by only one state-action pair.
As depicted in Fig. 2b, the incident faces of π 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 a non-negative combination of the
Proof this lemma is Appendix D.
We say that u is dominated by v if t is less than or equal to v in all objectives. A more formal definition of dominance is provided in Section 3.1.
4

---

Published as a conference paper at ICLR 2025
Obpaaivee
80
222 Objeoivve Retum
7.5
1.0
65
to
Rs Rn to Fo Objective Return
65
Objeztive 2 Retur
4o Objective Retum
Objective 2 Retur
60 Objective Roum
Objecdive Ruturn
25 60 85
25
12 Et 15
15
by
a5
(a) Step 1: Selecting non-dominated 1 policies
(b) Step 2: Generate convex hull of cur- rent policy and non-dominated policies
(c) Step 3: Extract incident Pareto opti- mal faces
Figure 2: Illustrations of the steps for finding Pareto-optimal front at each iteration. S = 5, A = 5, and D = 3.
normal vectors of all intersecting facets on the face yields a strictly positive vector. Once 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. 2c, the selected faces are added to the set of Pareto front (marked in blue), and all neighboring vertices on the ineident faces are shown as orange dots.
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.
The intuition behind the proposed algorithm is that any deterministic Pareto optimal policy can identify all neighboring policies on the Pareto front by considering deterministic policies that differ by only one state-action pair. This ensures that all Pareto optimal policies are discovered during the search process. Additionally, the Pareto optimality justification excludes any policies that are not Pareto optimal, guaranteeing that the search trajectory remains on the Pareto front. The detailed theoretical results will be shown in Section 4. As the algorithm is guaranteed to consistently search along the Pareto front, the total number of iterations is the same as the number of deterministic Pareto optimal policies.
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". We denote the set of deterministic policies that differ from by exactly one state-action pair as I1, (z), and the set of non-dominated policies among (T) as (DD)). Let Conv(JIll.o U (J"}) represent the convex hull constructed from the long-term returns of II (T)) and и. The set of incident faces of J on the convex hull Conv(JTh,, U {J"}) is denoted by F(J", Conv(J (T U {J)))).
The pscudocode for the Pareto front searching algorithm is presented in Algorithm 1. While the primary objective of Algorithm 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 P(II), and the set of deterministic Pareto optimal policies, denoted as V(II).
We begin by finding Pareto optimal policy through scalarization and adding it to the queue Q part of the initialization, as detailed in Lines 4 and 5 of Algorithm 1.
Neighbour Search As detailed in Lines 9 and 10 of Algorithm 1, for any deterministic Pareto optimal policy æ popped from Q, we first evaluate all policies in II (1T) \ Z, which differ from æ by only one state-action pair and have not yet been visited (with the visited policies stored in Σ). Once the long-term returns of II, (T)) are known, we select the set of non-dominated policies, (I).ND(T), (T), the set of policies in I1, (T) that cannot be dominated by any other policies in II, (T). Specifically, the PPrune algorithm from Roijers (2016) efficiently identifies the of non-dominated elements from given set, whose details are shown in Algorithm 3 in Appendix I.
Notation table is provided in Table 1 of Appendix B.
5

---

Published as a conference paper at ICLR 2025
Algorithm Pareto Front Searching Algorithm
Input: MDP settings: (S, (rr, r.
Output: the set of Pareto optimal faces P(TT) and the set of deterministic Pareto optimal policies V(IT)
1: Initialize PIII) 6-3 2, V(II) < Ø.
2: Initialize queue Q 4 Ø.
Queue of Pareto optimal policies to explore // Set of visited deterministic policies 4: Initialization: Sample a weight vector w > 0, solve the optimal deterministic policy To for (S, w r,7).
3: Initialize set Z < Ø.
5: Q. ppus((T))) V(TT).add(T)).
6: while Q is not empty do
π + Q-pop()-
8: Select (T).
I/Select all deterministic policies that differ from by one state-action pair //Evaluate policies not yet visited
Evaluate II, (T)) and update ž by (II (x)).
10:
(T) Select non-dominated policies (T) from (T).
11:
Calculate the convex hull Conv( ( U (J"1) formed by {J (I U {
12:
Extract (JJ, Conv(J U {J))).
1/ehe set of incident facets of J on Conv(J ( aD (JT)))
13:
Extract Pareto optimal faces F and vertices V from F(J5, Conv U {J*})) using Algorithm 2.
14:
Q-push(V) \ V(II)..
15:
((I)).ad((FF) add)).
16:
end while
Although the number of policies differing by one state-action pair is proportional to the state and action space, i.e., [T)] = S x (A - 1), the number of non-dominated policies ID 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 Lines 11 and 12, we aim to compute F(J", Conv No U {J*])), the set of (D -D-1)- dimensional facets of Conv(JUI,No {J*}) that intersect at J". straightforward approach is calculate the convex hull of the set of vertices Jul U { (as shown in Line 11) and select all facets that intersect at J However, since we are only interested in the facets of Couv(J U ((J)) }} that involve Js, computing the entire convex hull is unnecessary. Specifically, facets that do not involve J do not need to be considered. An efficient solution is to adapt the Quickhull algorithm (Barber et al., 1996), a well-established method for computing the convex hull of a set of points, to algorithm. This adaptation focuses on updating only the facets related to J thereby avoiding unnecessary calculations of irrelevant facets.
Pareto Face Extraction We apply Algorithm 2 extract all faces where the Pareto front intersects J from [(J", Conv Conv(JJI..S U (J))))
Consider a k-dimensional face of D-dimensional polytope. Let the normal
vectors to the - 1 1-dimensional facets that intersect at this face be denoted as {wn; 1 Specifically, when k D 1, then the facet that intersects the face is itself, and n = 1. The face is Pareto optimal if for any j = 1,... D,
2.00
1.75
1eam g 190
Σ of (wil 0,
1.25
B
1.00
0.75
Obj. Return
where a" is the solution to the following linear programming problem:
maximizea
min jE(1. D)
oe [We]
Obj. Return
(2)
subject to a, 0. Vi (1.
Convex polytope and its Pareto front (red edge and plane)
Figure 3:
Here, w; [[w:]] [w]]p] represents the normal vectors, and [wal, refers to the j-th component of the i-th normal vector. The objective function aims to maximize the smallest component of the weighted sum across all dimensions j = 1, D, ensuring that the face is Pareto optimal. A detailed lemma showing the Pareto front criterion and its proof is presented in Appendix G.
It possible that a high-dimensional face is not on the Pareto front, while some lower-dimension face still belong to the Pareto front. Figure 3 illustrates this scenario. The cyan and red planes form 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 ID edges, such as the line segment AB. This observation implies that even if dighedimmnsional
components of that
6

---

Published as a conference paper at ICLR 2025
face (e.g., the plane containing AB) is not Pareto optimal, it is necessary to examine its dower-dimensional faces (e.g., edge AB) to determine if they are Pareto optimal.
In Algorithm 2, We traverse from (D --dimensional faces down to 1- 1-dimensional faces (edges) to verify if each face is Pareto optimal. Faces that have not yet been verified are pushed into the queue Quwe- If the face H popped from
Qunee is verified to be Pareto optimal via Eq. (I), 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 F that are one dimension lower.
Note that if Pareto optimal face has vertices corresponding to deterministic policies Jm:jen then the policies constructing the face convex combinations of { expressed {a|s( Σ (aT)( Vs, a, a; Z 0. E 1]. The lemma demonstrating this result, along with its detailed proof, can be found in Lemma 24 of Appendix G.
Algorithm Pareto Optimal Face Selection
Input: Incident faces [JJ", ( Conv(J U {J*]))
Initialize the set of Pareto optimal faces t 2, the set of Pareto optimal vertices V +- Ø, the queue of faces for checking Pareto optimality Quace Ø.
2:
For all G E R(J", Conv (C [JIL U (J)))), Quace- Bace-) and w(G) <- normal vector of G.
(G) represents the set of normal vectors of facets that intersect G
3: while Qiace is not empty do H t Qiwee-pp().
5:
if there exist vertices of H not in FF then
11 H $ F
if (H) has a feasible solution to Eq. (1) then F.add( H) and V V.add add(veriices of H).
7:
else if dim H) > then
9:
Let S be the set of (dim(H)- 1) dimeensiona faces of H that intersect J
10:
for each H E S do
11:
Qince- Shce- H) and w (H).aadduu) (ud((w(H))
12:
end for
13:
end if
14:
end if
15:
end while
16:
Return F and V.
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.
Distance-one Property on Boundary of J(n): We prove that neighboring deterministic policies on the boundary of J differ by only one state-action pair. This ensures that we can efficiently find all neighboring policies of on both the boundary of J and the Pareto front by searching within the [[ (T)).
2. Sufficiency of Traversing Over Edges: We show that for any vertex on the Pareto front, at least one edge the Pareto front connects to another Pareto-optimal vertex. This property guarantees that we can traverse the entire Pareto front by exploring neighboring deterministic policies.
Locality Property of the Pareto front: We establish that the faces of the Pareto front intersecting at a deterministic policy can be found by computing the convex hull of the returns of this deterministic policy and 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 J
We present theorem stating that the endpoints of any edge on the boundary of J correspond to deterministic policies that differ by only one actton pair, almost surely. Specifically, for a finite MDP (S, P. where P is the transition probability kernel and r > 0 is the reward function, the set of P and 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.
7

---

Published as a conference paper at ICLR 2025
Theorem 1.
In discounted finite MO-MDP (S.A.P.r.7)) and under Assumption 1. any edge on the boundary of J connecting two deterministic policies corresponds to policies that differ by only one state-action pair, almost surely.
Since the Pareto front lies on the boundary of J, this theorem guarantees that for any policy on the Pareto front, the neighboring policies on the Pareto front can be found by searching among IT (x), a set of policies that differ from a by only one state-action pair. This significantly reduces the search space, making it more efficient to traverse the Pareto front.
Proof Sketch The proof follows two key steps: (1) First, we show that any face on the boundary of 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 combination of these policies. (2) Next, we establish that if two deterministic policies differ by only one acteon pair, the long-term returns of their convex combinations form 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.
edge between two deterministic policies is the long-ten return of convex
By combining these two observations, we conclude that the endpoints of any edge on the boundary of J correspond to deterministic policies differing by exactly one state-action pair almost surely. Since the Pareto front lies on the boundary of 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, 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 J is connected (proof is provided in Appendix E).
Lemma 2. (Existence of Neighboring Edges on the Pareto Front of J) Suppose I contains multiple Pareto optimal vertices. Let J be Pareto optimal vertex J. Let JJ( {J ι E [m), represent all neighboring vertices of J on I. Then, there exists at least one neighhoring vertex J E JN J) such that the edge connecting J and J lies on the Pareto front.
Proof Sketch We prove Lemma 2 by contradiction. Assume there exists a vertex on the convex polytope 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 contradiction. Therefore, if the Pareto front contains more than one deterministic Pareto optimal policy, the vertex must be connected 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 (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 lies on the Pareto front if and 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 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 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 connect the neighbor vertices. However, in higher dimensions, the Pareto front becomes more complex, and is impossible to build the Pareto front purely from vertices.
4.3 LOCALITY PROPERTY OF THE PARETO FRONT
Previous theoretical results show that it possible traverse the Pareto front through edges constructed by deterministic policies that differ by only one state-action pair. However, each policy has S x (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 J from the convex hull constructed by 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.
8

---

Published as a conference paper at ICLR 2025
Let deterministic policy correspond to a vertex on J. We denote the set of neighbors on the boundary of J to J as N(J",J) and the set of deterministic policies whose long-term returns make up N(J*, ,J) as Nz((",.), Let IF [F(J..) and (J"", Conv U {J*)) be the set of incident faces of J on I and Conv U (J")). respectively.
Theorem 2. The neighboring vertices and faces of J on the convex hull Conv(JT, i U (J*H) are the same as those on J. Formally. N Conv U (J"))) = N(J",J)
(J"",Cnv(J U (J*H)) = N,(J",]] J), and
R(J", Conv(Jul U ((J*)) ))) = F(J",J)
The proof is provided in Theorem 6 and Proposition 3 of Appendix F. This theorem guarantees that we can find all neighboring vertices and faces on the boundary of from the local convex hull Conv(J (J*)). 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
We also establish key properties of the Pareto front on a convex polytope (proof is provided in Appendix G).
Lemma 3. Given a convex polytope C, let F be face of C defined as the intersection of n. facets, i.., F = Fi.
where n. 2 1 and each facet is of the form F; Cn {ar E R w. x = =. Then the face F lies on the Pareto front of C if and only if there exists a linear combination of the normal vectors, weighted by o; 2 0.for any i E {1,-.-, ,T)), such that Σ, 04; [x/w >> 0 where [w:li is the j-th component of w.,
Based on Lemma 3, we can also extract the Pareto optimal faces from the local convex hull. Let F(J", ((J),((T) be the set of incident faces of J the Pareto front [J]]. The proof is shown in Proposition 6 of Appendix F. Proposition 1. Let (J",,, Conv(J U {J*))) denote the incident faces of J on the convex hull Conv(J U {J*]) that satisfy the conditions of Lemma 3. Then,
[F R (PJ)) Fr()", Conv(J (J)))).
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 vertex can be identified by computing the convex hull of neighboring non-immin 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.
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 Pareto front structure that is not immediately evident from the vertices alone even in simple setting. We consider a basic MDP setting, where we only have 4 states and 3 actions, and the reward dimension is 3. The transition kernel is uniformly distributed between 0 and and normalized to sum to 1, while the reward functions are uniformly distributed between O and 1. The discount factor is 0.9. As illustrated in Fig. 4, 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 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 to identify the Pareto front. Details are shown in Algorithm 4.
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 (Barber et al., 1996), the benchmark algorithm's
9

---

Published as a conference paper at ICLR 2025
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. 5, 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 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 (Roijers, 2016). For each iteration, OLS solves the single-objective MDP for given preference vector and calculates new preference vectors by constructing convex hull of all candidate preference vectors. In contrast, our algorithm requires only a single single-objective planning step during the initialization phase to obtain the initial deterministic Pareto-optimal policy. Rather than constructing global convex hull encompassing all potential Pareto- optimal policies, our algorithm builds the convex hull locally based on the vertex and its neighboring policies. As a result, our algorithm achieves significantly lower computational complexity compared to OLS. A detailed complexity comparison is provided in Appendix H.
We compare the running time of our algorithm against OLS in terms of efficiency for finding all vertices 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 more manageable running time.
S-t, prguoal
12n1a3 E SAMpa90
8.5
Running time (9)
bonduak
Rurning Lime (6)
$-3,0L3
S-R prrpesod
S-E benchrork
7.5
6.3
Objective Retur
5.5 60 65 10 Objective 2 Retur
of Cactions
of Fcctions
Figure 4: Pareto front of a simple
Figure 5: Comparison between the
Figure 6: Comparison between the proposed deterministic Pareto optimal policies searching algorithm and the OLS algorithm when D 4.
MDP with S A 3, and D 3. proposed Pareto front searching algo- rithm and the benchmark algorithm when D) = 3.
6 CONCLUSION
This paper investigated the geometric properties of the Pareto front in MO-MDPs. We proved that any neighboring deterministic policies on the Pareto front differ in exactly one state-action pair almost surely. We also demonstrated that the Pareto front is continuous in MO-MDPs, enabling traversing the Pareto front by moving along edges. 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.
ACKNOWLEDGMENT
This work has been supported in part by the U.S. National Science Foundation under the grants: NSF AI Institute (AI- EDGE) 21 12411, CNS-2312883 and was sponsored by the Army Research Laboratory under Cooperative Agreement Number W91 23-2-2255. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed implied, of the Army Research I Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Abbas Abdolmaleki, Sandy Huang. Leonard Hasenelever, Michael Neunert, Francis Song, Martina Zambelli, Murilo Martins, Nicolas Heess, Raia Hadsell, and Martin Riedmiller. A distributional view multi-objective policy optimization. In International conference on machine learning, pp- 11-22. PMLR, 2020.
Axel Abels, Diederik Roijers. Tom Lenaerts, Ann Nowé, and Denis Steckelmacher. Dynamic weights in multi-objective deep reinforcement learning. In International conference on machine learning, pp. 11-20. PMLR, 2019.
Alekh Agarwal, Sham M Kakade, Jason Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pp. 64-66. PMLR, 2020.
Eitan Altman. Constrained Markov decision processes. Routledge, 2021.
C Bradford Barber, David P Dobkin, and Hannu Huhdanpaa. The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software (TOMS), 22(4))469-483, 1996.
Toygun Basaklar, Suat Gumussoy, and Umit Y Ogras. Pd-morl: Preference-driven multi-objective reinforcement learning algorithm. arXiv preprint arXiv:2208.079/1 2022.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Qingpeng Cai, Zhenghai Xue, Chi Zhang, Wanqi Xue, Shuchang Liu, Ruohan Zhan, Xueliang Wang. Tianyou Zuo, Wentao Xie, Dong Zheng, al. Two-stage constrained actor-critic for short video recommendation. In Proceedings of the ACM Web Conference 2023, pp. 865-875, 2023.
Lisha Chen, Heshan Fernando, Yiming Ying, and Tianyi Chen. Three-way trade-off in multi-objective learning: Optimization, generalization and conffict-avoidance. Advances in Neural Information Processing Systems, 36, 2024.
Xu Chen, Yali Du, Long Xia, and Jun Wang. Reinforcement recommendation with user multi-aspect preference. In Proceedings of the Web Conference 2021, pp. 425 435, 2021.
Heshan Fernando, Han Shen, Miao Liu, Subhajit Chaudhury, Keerthiram Murugesan, and Tianyi Chen. Mitigating gradient bias in multi-objective learning: A provably convergent approach. In International Conference on Learning Representations, 2023.
Branko Grünbaum. Convex Polytopes, volume 221. Springer Science & Business Media, 2013.
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Minyoung Hwang, Luca Weihs, Chanwoo Park, Kimin Lee, Aniruddha Kembhavi, and Kiana Ehsani. Promptable behaviors: Personalizing multi-objective rewards from human preferences. arXiv preprint arXiv:2312.09337. 2023.
Joel Jang. Seungone Kim, Bill Yuchen Lin, Yizhong Wang, Jack Hessel, Luke Zettlemoyer, Hannanch Hajishirzi, Yejin Choi, and Prithviraj Ammanabrolu, Personalized soups: Personalized large language model alignment via post-hoc parameter merging. arXiv preprint arXiv:2310. /564, 2023.
Dohycong Kim, Mineui Hong, Jeongho Park, and Songhwai Oh. Scale-invariant gradient aggregation for constrained objti-obeective reinforcement learning. arXiv preprint arXiv:2403.002 2024.
Xingchao Liu, Xin Tong, and Qiang Liu. Profiling pareto front with multi-objectivv stein variational gradient descent. Advances in Neural Information Processing Systems, 34:14721-14733, 2021.
Haoye Lu, Daniel Herman, and Yaoliang Yu. Multi-objective reinforcement learning: Convexity, stationarity and pareto optimality, In The Eleventh International Conference on Learning Representations, 2022.
Debabrata Mahapatra and Vaibhav Rajan. Multi-task learning with user preferences: Gradient descent with controlled ascent in pareto optimization. In International Conference Machine Learning, pp. 6597-6607. PMLR, 2020.
Hossam Mossalam, Yannis M Assael, Diederik M Roijers, and Shimon Whiteson. Multi-objective deep reinforcement learning. arXiv preprint arXiv:1610.02707. 2016.
Simone Parisi, Matteo Pirotta, Nicola Smacchia, Luca Bascetta, and Marcello Restelli. Policy gradient approaches for multi-objective sequential decision making. In 2014 International Join! Conference on Neural Networks (IJCNN) pp. 2323-2330. IEEE, 2014.

---

Published as a conference paper at ICLR 2025
Markus Peschl, Arkady Zgonnikov, Frans A Olichock, and Luciano C Siebert. Moral: Aligning ai with human norms through multi-objeccive reinforced active learning. arXiv preprint 000:2201.000111 2021.
Kaare Brandt Petersen, Michael Syskind Pedersen, et al. The matrix cookbook, volume 7. Technical University of Denmark, 2008.
Shuang Qiu, Dake Zhang. Rui Yang, Boxiang Lyu, and Tong Zhang. Traversing pareto optimal policies: Provably efficient multi-objective reinforcement learning. arXiv preprint vrXiv:2407.17466 2024.
Alexandre Rame, Guillaume Couairon, Corentin Dancette, rean-Baptist Gaya, Mustafa Shukor, Laure Soulier, and Matthieu Cord. Rewarded soups: towards pareto-optimal alignment by interpolating weights fine-tuned on diverse rewards. Advances in Neural Information Processing Systems, 36, 2024.
Diederik M Roijers. Multi-objective decision-theoretie planning. Al Matters, 2(4):11-12, 2016.
Umer Siddique, Paul Weng, and Matthieu Zimmer. Learning fair policies in multi-objectivee (deep) reinforcement learning with average and discounted rewards. In International Conference on Machine Learning, pp. 8905-8915. PMLR, 2020.
Richard Sutton and Andrew G Barto. Reinforcement learning: introduction. MIT press, 2018.
Kristof Van Moffaert and Ann Nowé. Multi-objective reinforcement learning using sets pareto dominating policies. The Journal of Machine Learning Research, 15(():3483-3512, 2014.
DJ677750 White. Multi-objective iafinite-horizon discounted markov decision processes. Journal of mathematical analysis and applications, 89(2)6639-647, 1982.
Peiyao Xiao, Hao Ban, and Kaiyi Ji. Direction-oriented multi-objective learning: Simple and provable stochastic algorithms. Advances in Neural Information Processing Systems, 36, 2024.
Jie Xu, Yunsheng Tian, Pingchuan Ma, Daniela Rus, Shinjiro Sueda, and Wojciech Matusik. Prediction-guidee multi-objective reinforcement learning for continuous robot control. In International conference machine learning, pp. 10607-10616. PMLR, 2020a.
Tengyu Xu, Zhe Wang, and Yingbin Liang. aon-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms. arXiv preprint 20Xv:2000503355, 2020b.
Runzhe Yang. Xingyuan Sun, and Karthik Narasimhan. generalized algorithm for multi-objeetio reinforcement learning and policy adaptation. Advances in neural information processing systems, 32, 2019a.
Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. Advances neural information processing systems, 32, 2019b.
Rongguang Ye, Longcan Chen, Jinyuan Zhang, and Hisao Ishibuchi. Evolutionary preference sampling for pareto set learning. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 630-633 (30, 2024.
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.
Dongruo Zhou, Jiahao Chen, and Quanquan Gu. Provable multi-objective reinforcement learning with generative models. arXiv preprint arXiv:2011.10134 2020.
Tianchen Zhou, FNU Hairi, Haibo Yang. Jia Liu, Tian Tong, Fan Yang, Michinari Momma, and Yan Gao. Finite- time convergence and sample complexity of actor-critic multi-objectivv reinforcement learning. arXiv preprint arXiv:2405.0308. 2024.
Günter M Ziegler. Lectures on polytopes, volume 152. Springer Science & Business Media, 2012.
12

---

Published as a conference paper at ICLR 2025
A DISCUSSION ON PARETO OPTIMALITY
We define the Pareto optimal policy set based on an initial state distribution μ. Unlike dingle-bbecctive reinforcement learning, 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 μ does not ensure Pareto optimality across all states (Lu et al., 2022). Lu et al. (2022) introduces the concept of aggregate Pareto efficiency, where policy is considered aggregate Pareto optimal if there exists no policy n' such that V V", The Pareto front P(TI) defined in Section 3.1 only forms a subset of the aggregate Pareto optimal set.
We focus on the definition of Pareto optimality
given state distribution for two key reasons:
1. Relevance to Practical Applications: In real-world applications, the starting state often follows specific distribution. For example, RLHF applications in Large Language Models (LLM), input texts typically follow 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 + 1, P(T)) approaches the aggregate Pareto optimal set (Lu al., 2022). Therefore, in settings with a high discount factor, focusing on PIII) provides a close approximation to the aggregate Pareto optimal set.
B NOTATIONS
Let Ias denote the identity matrix of size M, 1M denote the M --dimensional vector where all elements are 1, and xmx denote zero matrix with dimensions M x N. Let A denote the transpose of the matrix A. Let A > (2)B denote that each element of A strictly greater than (greater than or equal to) the corresponding element of B. Given MDP (S, A, P, r, for any policy æ, define the state transition probability matrix p and the expected reward vector 7r as:
Pd (8, = Σ
P(s'(s,a)T(aal) (s) = Σ r(s, a)((as)
aEA
aEA
We provide the notation table as follows.
Table I: Notation table
Notation
Description
11
Set of stationary policies
Set of deterministic stationary policies
(T)
Long-tern Morg-term return of policy æ given initial state distribution μ
(1s
Set of long-term returns of stationary policies with initial distribution f
J(p)
Set of long-term returns of all stationary policies with initial distribution
P(S)
Pareto front of the set $
V(C)
Set of vertices of the polytope C
B(C)
Boundary of the polytope C
P(II)
Set of Pareto optimal policies { E 11 J E F(J()))
Cony (S)
Convex hull the set
N(x, C))
Set of neighboring vertices of vertex on C
F(xz, (C)
Set of incident faces of vertex æ on C
II,
Set of deterministic policies differing from by exactly one state-action pair Set of non-dominated policies among (m)
[N, M)
Set of deterministic policies that differ from и at all states in M and matching π at all other states
13

---

Published as a conference paper at ICLR 2025
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 A be an m x n matrix. Then, the following relationship holds: rank( A) + dim(mull( A)) = n, where rank(A A) is the dimension of the column space of A, and null(A) is the null space of A. Lemma 4. Let A be an X n. matrix and b + O be an m-dimensional vector. If Ax = b has at least one solution, then the dimension of the solution space of Ax = b is equal to dim (mull(A)), where mull(A) is the null space of A. Lemma 5. Let A be an m x matrix with full column rank. If AB = kAC, then B = I.C.
Proof. From AB = AAC, we can subtract AAC from both sides to get A(B - kC) = On- Since 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 Aar On is & O,- Therefore, the only solution to A(B - kC) = Om is B - &C = O,. Hence, B B= BC
]
Lemma 6. (Horn & Johnson, 2012) Let A E R be a square matrix. The maximum absolute value of the eigenvalues of A, denoted as p(A), satisfies the following inequality:
p(A) S ||A||
where ||A maxigisn Ei= |Agl is the infinity norm of the matrix A.
Then we present some lemmas related to the multi-objective optimization.
Lemma 7. (Boyd & Vandenberghe, 2004) Let S denote the set of achievable objective values and let (P() denote the set of Pareto optimal values in C. Then (S()) S (BS),, i.e., every Pareto optimal value lies in the boundary of the set of achievable objective values.
Lemma 8. Let x be a point in a set S. x lies on the Pareto front of S if and only if there exists a vector w > 0 such that
w. T (x= y) 2 for all y S.
Proof. ( (=) ) Assume, for the sake of contradiction, that is not on the Pareto front of S. This means there exists point y E S that strictly dominates æ, i.e., y > x. This implies that y is at least as large as the corresponding objective of and y is strictly better than x: in at least one objective. Therefore, given w O, we have w (x: y) < O. However, this contradicts the assumption that wo" T (x: y) 2 0 for all y E S. Thus, no point in S strictly dominates x, which implies that æ is on the Pareto front.
(=) If x is Pareto optimal, then for any E S, x is at least as large as the corresponding objective of and æ is strictly better than y in least one objective. Given w > O, w (x y) O.
Next, we restate some definitions in the main body of the paper and present several lemmas related to polytopes. Definition 1. (Ziegler, 2012) Let C C Rdd be a convex polytope. A lineur inequality wo T S Go is valid for C if is satisfied for all points x E C. A face of C is any set of the form F = Cn {ar E TR w x co) where w x S Co is a valid inequality for C. The dimension of a face is the dimension of its affine hull, i.e., dim == dim(aff(FF) The faces of dimension smaller than dim(C) are called proper faces. The faces of 0, 1, dim(C) - 2. dim(C) 1 are called vertices, edges, ridges, and facets, respectively.
Lemma 9. (Grünbaum, 2013) Every nonempty proper face of convex polytope C is an intersection of facets of C. Lemma 10. Given a d-dimensional convex polytope, if the optimization objectives are the individual coordinate values, then the Pareto front of the convex polytope is continuous set.
Finally, we give some lemmas related to MDP.
Lemma 11. (Almman, 2021) The occupancy measure of any policy x and initial distribution y defined as (=)s) (1- Ei P(s s|so p(-)). Similarly, define (s, == (1 - 7) Er= n²t P(st = s, a, = also ~ ((-))
(s)))((()s). Define for any set policies U, L (n) = UrEu {d] and define L(μ) = Un, Then, L(y) is closed convex polytope and L(p)= = (L
Lemma 12. (Sutton
Barto, 2018) Given MDP (S,A,P,r,M)
y). there exists at least one policy that is al-
ways better than or equal to all other policies in all states, denoted as optimul policy. The optimal policy
x² satisfies x² (8) = arg A (8. where Q" (s, a) is the solution to the Bellman optimality equation Q* a) = ()) + max. Q" (s', d') 8, s,
14

---

Published as a conference paper at ICLR 2025
Lemma 13. If there exists μ where plss > 0 for any 3 E S such that deterministic policy x² maximizes for J" (j)) p vVV V then x² is the optimal policy, ie., V (8) max, V (s) for any 8.
Proof. We prove this by contradiction. If x is not the optimal policy, and there exists optimal policy u & 'T" such that V"a (s) S (s) for any S, and on least one state V" (s) < V*(s). Then Ju > J (1) since ju(s) for any This contradicts the condition that xt maximizes for J (1)). So TT" is also optimal policy.
Lemma 14. Given a single-objective MDP (S,A,P,,,T) If 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 II".
Proof. We first show that all policies in the convex hull constructed by the set of optimal deterministic policies II are optimal policies. By Lemma 12, the optimal policies share the same state-action value function, that is, Q"*(s, a) QT (8, a) (* a) for any Ti, j E II.. Since ग. E II* are deterministic policies, with a little abuse notation of ग, we have (s) = argae max Q (s. a) for any i. Let a be a (III) - 1)-dmennsion standard simplex. Let be the convex combination of II,, that is, Tals)) maximizes Q" (s, a), i.e., Tı margae. max (8, a){s) = 1, т at state maximizes Q* a) and x is an optimal policy. Hence any convex combination π optimal deterministic policies are also optimal.
E. (a]s(a)s) for any As each possible choice of π at state
Then we want to show for any policies not on the convex hull the set of optimal deterministic policies IT, it cannot be the optimal policy. We prove this by contradiction. Suppose an optimal policy и is not the convex hull by all deterministic policies. In that case, it is written as = Ei 0g7T; + Ejjs,e eñ ЛyTz where >; 04 + >, 8g
0g 2 Bj 2 O, and II a of non-optimal deterministic policies. Suppose on state such that V* (s) S (s),,, then I (s() o arg max" Q" (s, a), which indicates π is no longer an optimal policy. This contradicts the assumption that æ an optimal policy.
(r,,,)))) 7) and deterministic policy S + A, let M)) The transition matrix Pd and reward vector r" can be decomposed into block matrices as follows:
Lemma 15. Given MDP (S,A,P,r,
A
B
X
p
C
D
T
Y
Following the definitions T and V in Eq. (9) we have
7Is M --)
(Is- -A-)= X
V =
IM
0M
Proof. Since the transition probabilities and rewards starting from S M are the same for any ι E ( M), we conclude that A, B, and X (the relevant blocks of p and r*) are independent of m. However, C D and Y vary with n. as indicated by the subscripts.
Analysis of r We decompose 1 into block matrix form, i.e., 1 ((T) (TT) where IT e ((8-M)XM and 13 E MRM
The definition of H M, 3y) that for any 8,, 8, E M with * shows that ((s,, s;) = 0 with probability and H(5,, 53) do with probability 1. Thus,
m7 E [ H(B = for i + j. and Teli, = E ((8,..)) = 1.
For IT, starting from s S') M, the probability of reaching 8, M in one step is Baj. The probability of reaching 8y in two steps is A, 1s Repeating this reasoning for subsequent steps, we obtain:
I j =P(S
3, 3,) E
H
(s.
ByB + A. B + A
it follows from Lemma 6 that the eigenvalues of A are smaller than 1. Therefore, Is- M A does not have any zero eigenvalues, implying that is invertible. Summing over all steps, we have:
Since Al <
IT = Σ (TA)"B B- - (Is-M - 7A)-
==0
15

---

Published as conference paper at ICLR 2025
Thus, we conclude:
(1s- - -A) B
I
IM
(Vi) ((3 T
Analysis of V Similarly, decompose V into block matrix form: V
where Vi E
(g(S-M)xL and V5 E RMXD.
For Vz. starting from any & E M. we reach M with probability in zero steps, so the total reward 0. Thus, V = =0MMM-
Starting from state S M, it has immediate reward (i.). For the next state, it has probability [A],, to move to state 8j S \ M, and it has probability E, B)j to move to 3j E M which terminates the process with future return 0. Therefore, we can write the Bellman equation-like form:
VT = + AVT + 17
-X +AV..
Solving this equation gives:
VI = (Is-M - -AA)
Hence, conclude:
VI
(Is-M -AA-1X
V
V
OM
Lemma 16. (Properties of F and Ea) The functions F and E", defined in Eq. (12), can be expressed as follows:
F" (MII, ET r"= + (M
where I and V are predefined matrices given in Lemma 15, M is subset of states, and (*MM) is the transition probability matrix under policy a restricted to the subset M.
We derive the following properties:
1. Gradients of F" and E with respect to т. For any 8 E M and a E A, the partial derivatives of F" and E with respect to the policy are given by:
OF
OE
7P(((), a,
r(6()),))))))))))))()))) a, 7,(((3),,
@m(3,a) a)
(T, a)
where 8(8) a unit vector indicating the state s, Z P(5()) a. MR5x with 7(5,) P(5, a, and 7 -) 0 for any 8' + s.
2. Simplification when n is deterministic policy. If π. is deterministic policy, then F and E can be simplified as follows:
FT Σ (3),
SEM
ET Σ
((6(3), (()) + P-P())),
SEM
Given aTı (1 a)Tz, where a < 1 to ensure π is valid policy, have
F =0F + (1 1 F
ET = Ti +1 =
Proof. (1) Recall that the state transition matrix and reward function under policy are defined as follows:
p. (s) = Σ ((s,a,,')7(s,.) (=(ss Σ [((s,a)((ssa)
16

---

Published as conference paper at ICLR 2025
where P(s, s') is the probability of transitioning from state to state s' given action a, and r(ss, a) is the reward for taking action a in state 8.
For any 8 E .M and a E A. we compute the derivatives of Pd (s, s') and r (s) with respect to the policy n (T, a):
(s"
0r (s)
=5), (3, a)
r(s, a)o(s =),,
(3,
where 6(s 8) is the Kronecker delta function, which is if = and 0 otherwise.
Next, substituting these expressions into the derivatives of F and E" with respect (T, a), obtain:
OF 7OP (s. 8') P( 0π(3,0)
(3( a)
OF
(s)
(x,
(m(3,0)
+ = + a(
(2) When is a deterministic policy, recall that maps each state S to specific action (ss) e A. In this case, with a slight abuse of notation и, the transition matrix and reward function are simplified as follows:
P (" 8') = Σ a, 8')(ss)) = P(s (s),
aEA
r (s) = Σ
aEA
where the policy π deterministically selects action (s) in each state 8.
Substituting these expressions into the definitions of F and E", we obtain the desired results:
F Σ
(8))))
SEM
ET Σ
SEM
(3) Since the transition probability matrix and reward function under mixed policy az + (1 a) can be expressed as linear combinations of the respective components under policies mi and Iτ, we have:
pa = (M) - o o (M))
and
+ = ar (M) + (1 a3 (M).
By applying these expressions in conjunction with the definitions of F and E", the desired result follows.
D DISTANCE-1 PROPERTY
Let Ian be the set of all policies, including both stationary and non-stationary policies, and let Jan (J" (m) e Ham denote the set of achievable long-term returns for all policies in Hall- Recall that J(n) (J*((p)a (p)]T II} represents the set of achievable long-term returns for all policies in the set of stationary policies 11. By Theorem 3.1 of Altman (2021), is sufficient represent the J(μ) using only stationary policies, i.c., (an(p) J(x). Therefore, we focus on the set of stationary policies to construct the Pareto front in our paper.
The Pareto front of I(μ) denoted P(J(H)). Lemma 1 shows that the I(n) construct a convex polytope. The boundary and vertices of the convex polytope I(μ) are denoted as B(J(u)) and V(J(p)), respectively. Lemma also implies the vertices of I(Js) are deterministic policies, that is, (I(()) S П..
Lemma 17. (Restatement of Lemma 1) J(p)) a closed convex polytope, and the vertices of D(H) can be achieved by deterministic policies.
17

---

Published as a conference paper at ICLR 2025
Proof. We observe that J(H) can be obtained by applying linear transformation to L(a), that is, 1(p) ((d7) r/dz E L(n)).
Then we prove the following lemma, which shows that linear transformations preserve the convex polytope structure and a subset of its vertices.
Lemma 18. Suppose C is convex polytope in n-dimension space whose vertices set is V, and A E Rxx, Let C (Axl E [], then C is also a convex polytope with vertices V, and V S {Av/o E V}.
Proof. Since C is convex polytope, it is the convex hull of its finite vertex set V {ui u....., ;k). That is,
C Conv(V) EE a a, 2 0. Ei a = 1 Applying the linear map A to C, we get:
C AC A
a
a:
Σ a:
=1
k
k
(Avs)
a; 2
0,
a
This shows that C the convex hull of the finite set (AV1, Au2, Auk). which implics that C is a convex polytope, and the set of vertices V is subset of {Avle V) (Av1, Au2, ........ Avk).
The conclusion can be obtained by combining Lemma II and Lemma 18.
By the definition of the Pareto front, the Pareto front is the set of non-dominated policies on J(u). By Lemma 7, the Pareto front is on the boundary of the convex polytope.
We define two policies, TT and T2, as neighburing policies an edge on the boundary of the convex polytope ((I())) connects the long-ten returns of T and T2.
Lemma 19. Under Assumption for any edge on (JJ())) with endpoints denoted as J (u) and (n), any point on this edge can only be achieved by the long-term return of a convex combination of policies Ti and mz. Specifically, for any a E [0, 1). there exists a 3 E [0. 1] such that
a. (p) + a) (p) = JBx, + (H).
Proof. Let Ti and m2 are neighboring points on (J(())), and E(T1, T2) is an edge connecting two vertices. Since E(m,, T2) is a face of I(2), by Definition 1, there exists weight vector and scalar co such that E(T1, R2) Cn (æ e
Rd w x = co} and un x S cu for any x E I(u). Therefore, we have
{ m2) = arg
max w (H). (EV((())
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 w JJ (H) only contains Ti and T2, therefore
{ajT (n) + (1 a))² (w)la E [0, 1]} = arg max w T (T)) #ell
(3)
We construct a single-objective MDP (S, A. P.r w,,), 7), where we use the preference vector w to transform M- objective reward tensor r E Sx AxD to oingle-objective reward e S Under Assumption 1, πі and T2 are optimal deterministic policies on A, r T w, 7) by Lemma 13. By Lemma 14, the optimal policies on AS,A, r w, 7) lies in the convex hull constructed by ni and T2, i.e.,
{J +1 (M]B3 E [0, 1]} = arg max w T J*
(4)
well
Combining Eq. (3) and Eq. (4), we obtain
(aJ=) (p) + (1 - a) (p) | a E [0, 1] = ( (n) E [0, 1]}
This result indicates that, for an initial distribution μs, the edge between neighboring policies in I(u) can only be achieved through the long-term return of the convex combination of these neighboring policies. This concludes our proof.
18

---

Published as a conference paper at ICLR 2025
We define the distance between two deterministic policies, γı and T2. as the number of states where the policies differ. This distance is denoted by di m2).
Definition 2.
Lemma 20. Given a discounted finite MDP (S, A. n, where P is the transition probability kernel and r 2 is the reward function. Let ih and σ2 be two deterministic policies. Under Assumption 1, we have
1. d(T1,17) m2) = 1: If Iı and T2 differ by exactly one state-action pair, (Jm (u)la E [0, 1]} forms a straight line segment between J (1) and J (u).
2. d( m2) 1: If 1 and 22 differ by more than one state-action pair, for almost all P and r in the space of valid transition kernels and rewards (with Lebesgue measure 1), (Jam+(1-aax; (4) E [0, 1]} does not form the straight line segment between J (p) and J (H)).
Proof. Let .M be the set of states that Ti and T2 differ on. By definition of distance between two deterministic policies, = M = d(T1::T2)
Recall that 11, MM denotes the set of deterministic policies that differ from only at states within M, while matching π at all other states. In other words, all policies in set M. For states that cannot reach M within a finite number of steps, the value function is identical across all such policies. Conversely, for states that can reach M in finite steps, the value function depends on the policy within M. With some slight abuse of notation, in the remainder of this proof, we focus only the of states that can reach M within finite number of steps, denoted as S.
take the same actions for states outside the
Starting from state under policy æ, define hitting time of the set . C S, denoted as H (s, as the first time step at which the process reaches any state in M. It is defined as:
H (s. M) = inf {t 2 so = s, M}
where 8, denotes the state of the process at time t. For any E M, we define the random variable H (5,,,M) = 0 as takes steps from to M. Moreover, we define the total return d-th objective before hitting M from state s under policy as the sum of discounted rewards until the process reaches any state in M. It is given by:
(=,
M) =
Σ t=0
Fra(s)aa))
where r(s ax) is the reward time step f.
Similarly, Starting from state under policy we denote the hitting time of a specific state 3 E M, conditioned on avoiding all other states in M before reaching as H M, with slight abuse of notation. is defined as:
H (s, inf (t 2 Sg s, St 3, sk M, < t).
For any 8',8 8 E M with 8' * s, the random variable H (8', .,, 8) are defined as:
(*, 8) with probability 1, as it takes 0 steps to reach ø from 8,
H M,3) with probability 1, as it is impossible to reach 5 first from 3' (since we are already at M).
The total return before hitting 3 E M, conditioned on avoiding all other states in M before reaching 8, denoted as ir5 M8):
H (s.M88))
(s,
Σ
r'ra(st, az).
(6)
The arrival state is defined as the first state in M reached by the process, starting from under policy Denote the arrival state as:
S St = (HT(s.M))
where (s. is the state of the process the hitting time H" M). Since S (s. is the first state in M that is reached, the hitting time of S M) is indeed the same the hitting time of M. Similarly, the total return before
19

---

Published as conference paper at ICLR 2025
hitting M is the same as the return before hitting 5 (s, conditioned on avoiding hitting other states in M, that is:
(s, =H" (,, (s,
(1
(s....
(8)
M), E a)))
(r) = (s, (s.
Denote the expectation of the total return and discount before hitting conditioned on avoiding all other states in M before reaching 5 as Vī- IV (sp, M), (ss), 1x11,, V RSXD and I' RRSM respectively. For E S,8' 8' M, d E (1. D}. we define
(s, =B [ (s. MM)
V = Vbl.
(9)
(s, P(( = =]E [lls.....))
Recall V E RxD the value function with initial state distribution μs, where is ignored for the notation simplicity. Moreover, (s) and (M(M) denote the d-th objective value function at state and state set M, respectively. By the definition of value function, V can be written
20
(s( =E
ralss 50 =
E
ra,
5
(s, M)
Sy 8
We next want to calculate the conditional expectation of long-term return given S (s, = 3.
0
E
Td,
STh
(s,
=
=E
Σ
raa + H(s.
H(s.M.8)-1
E
Σ
rr,, +E H(s.
v
(By linearity of expectations and V (8) is constant)
E (s, s)]
E H(s) VJ
(by definition of it (s, MM 3) in Eq. (6)
Plugging the above equation into (s(s), we have
Vi(s) Σ
(s T)TE
Σ ras Sth (s,
SEM
Σ P(S (s 5) i (, + Σ (s, 3)B ( ((MM..)) V3(()
SEM
BEM
E R7 M) Σ P(ST((, 5)B H(s.M.3) VT(3)
-V, Σ (s Eq. (9))
20

---

Published as conference paper at ICLR 2025
where ! is because
H(s.M.s
Σ (s, =8)
(1 Ms
=E
?rnals,, ar)
8 (s,
80 -
H H(a.M)-
E
10
7'ra(s),r))
8th (s,
50 =
(by Eq. (8)
t=
H(s.M)-1
E
ra(s,, 0t)
RJ
M).
Lemma 15 gives the value of r and v following
T" (Is M 7A) B
[Is- ----1X
V"
IM
0M
Note that Ix and v are the same for any policy in II ( M). Since only consider policies within (N(, for simplicity of notation, omit the superscripts in n and V in the following sections, as they remain constant for any policies within II (1)
Rearranging V have
V = V
(10)
By the Bellman equation and Eq. (10), we can rewrite the (*(M) as
V (M) =r (M) + (M)V (by Bellman equation) -r"(M)+ + 7P' (v (V (by Eq. (10)
=(F*(M) PMM + (M)
Since [A, B) is stochastic matrix, we have (Is-M - - - BB M < (Is-M A) 1s-as, where the inequality means (Is- M - - B11 is smaller than (Is-M A) BB component-wisely, Moreover, since each element of A and B are larger than zero, we also have (Is-M- -1-M--AA -A) - > Os-M. As each element of C and D are smaller than zero, it follows that aa S (C (IS(IsM - - D IM < (C" +D) 1M = 1as. Hence, || (Is-M 7 'B + D loc <
By Lemma 6, Pd (M)) - (Is-M - - D has eigenvalues all smaller than 1. Hence the eigenvalue of (IM -P= (M)l') are larger than zero, implying it is invertible. Rearranging the above equation, we have
-PP((M)
V=(M) = (IM -M)) (FMM (PTM))+(PP))
(11)
Define
FT PMMJI
(12)
ET (M)+ +
Plugging Eq. (11) into Eq. (10), we obtain
v = V +r (IM -PP +
(13)
V + (IM Fn) E (by definition and E*)
21

---

Published as conference paper at ICLR 2025
We move to investigate the derivative of V with respect to (3,
OV =r. ① (( FT) FT)
O
E" + (IM
F")
(x,
0T((3 a)
(3,
OF
OE
=I' (IM F=)-1
(IM F") E +T (IM F")
(5,5,
0Y ---11 0Y Y (Petersen al., 2008))
(by Oz
dr
=I (IM F -1 P(0(3), -I' (IM F²) E
+ (IM- F (r(6(3), a. P(8(3). (by Lemma 16)
Then we can calculate the directional derivative on the direction of n2 æ1, where T2 and лı are deterministic policies. Moreover, Ti (3) (5) for any state belonging to M, and т (B) T2(3) for any state other than M. The calculation of the directional derivative, denoted as (0v
Ür T2 TT) is as follows:
8V
UV
42
Σ
0T(3,a) a)
(T2(5, a) - (3,
REM.aEAA
=r. (IM F
(2)6(3), (()))))))))((())))))()))))))) (IM - -F)) E"
SEM
+ r. (IM - F*)-
Σ
(1(6(3)) (2(3) P(0(3),
3EM
-(r(8(3), (8), + P(((5),
(by (1) of Lemma 16)
=I- (IM - F7) -F F (IM - F")
E +T. (IM FF)) (ET E=
(by (2) of Lemma 16).
Consequently, the directional derivative along the direction of π2 Ti at convex combination of πΙ and n2, namely + (1 22 with
am1
S be expressed as follows:
vV"
aTT1 (1 a) T) 222
= - (IM F > (F - F (INs FT) FT) E + + (IN - F*) -1 (E E
r. (Iar FT) -1 (F - F (IM
FT)
[aE* + (1 - (1-x)E") E²)
+ T .I F -1 (E E
(by Ex = =F
+
+1 (1-a)
E from (3) of Lemma 16)
(14)
= (Iy FT)
((1-0) (F (F*2- F + (IM - -F*)) (IM - FT) ET
+ I' -I'(IM - FT) F-)
(a (F - F - (IM FT)) (IM - F") E
r- (IN FT)- (In FT) (Inr FT) m
T (IM - F=) (IM - FT2) (IM FT) E
(by F oF + F from (3) of Lemma 16).
Furthermore, the directional derivative along the direction Ti at the point Ti can be written as:
V
π = T1.
T2
n1
(IM F (IN
F (Ias - F F E
P. (IN FT1) (IN FT2 (IM - F E
(15)
= (IM F = r (Inr - F
(I - FT)) (IM F -1 E
= (IM F -1 (IN FT²) ( 1 T (IN F=1) ET
22

---

Published as a conference paper at ICLR 2025
The statement that (1=)+(1-0)rz lies on the straight line between * and V is equivalent to that the directional derivative of V along the direction #2 # the point amı (1 a) aligns with the direction of V V
That is, for any 0 I a I 1, there exists l E R which is related to such that the following equation holds
Ov θπ T= +11 (1-a0)m² "2 = k (V V*
(16)
Plugging Eq. (13) and Eq. (14) into Eq. (16), LHS and RHS can be written as
LHS =I (IM FT) (IM F (IM FT) E
- (IM - FF) (IM - F (IM - FT) ET RHS =k (V V
-k (v + r (IN F
E
-V+r- (Ias FT E
=k- ((Iv F T (IM F
E
Note that when M 1, IM F is a scalar and E E Rd In this case, for any 0 < a S 1, there exists such that LHS RHS. To show this, define scalars b (IM F. bi (IM F b2 == (Iar FT12, Then express LHS = b / (E*= /b2 E. /by) and RHS = (E*2/b/ -E /bi). Clearly letting k: = byb2/l makes Eq. (16) hold. As a result, (1m)+(--)) lies on the straight line between V and v when d(T1, T2) = 1.
A necessary condition for the statement + lies on the straight line between V and * is that the directional derivative of V along the direction #2 л1 at the point Ti aligns with the direction of V V i.e., Eq. (16) when π = T1. Formally, there exists sealar it such that
12
k((' V*1).
(17)
I=
Define A = (IM- - FT2)"
E - (IM
F
E Plugging Eq. (15) into LHS, we have
LHS =r (Ins - F -1 [I FT2) (T - F ETT (IM - -
=r (INs FTi)-
(IN FT2) A,
RHS can be rewritten as
RHS - A.
By Lemma 15, r rank. By Lemma 5, Eq. (17) is equivalent to the following equation:
IMM S and I has rank M S. Therefore, has full column
(IIN FFI) (Im-F"*) - - -kIM) A O.
(18)
Note that A E R DD and rank(A) S min(M, D).
(1) When rank(A) M, has full row rank. This also implies M S D. By Theorem 3, the only solution to XA = 0 is X = 0. Therefore, Eq. (18) is equal to
(IM FT1)-! (I FT2) KIM = 0.
Substituting the definition F as F pp (M)) in the above equation and rearrange the equation, we have
pdd PM (IM - k (Ins - P (M))))
Moreover, to make pm a valid probability distribution vector, p should satisfy 101 1M. Therefore, (M) should satisfy p (M) [T 1s] = [Tar - (Ias - -p (M)T) (()r)/>> /7, lar]
When M -M=,, S, [r. 1s] E Sx(++) has rank S. When M < S, Since [T] has S rows and rank at least M. Hence, T. 1s] has 5 rows and rank least . in both cases. Fix k. By the rank-nullity theorem Theorem and Lemma 4, for E M, if the solution of (3) exists, the dimension of the solution p is at most S - M. On the other hand, if no solution pa (8) exists, the dimension of the solution space is O. Therefore, the dimension of solution space of a (M) most M x (S M).
23

---

Published as a conference paper at ICLR 2025
By varying & E R. the dimension of solution space of (M) is M x (S x
M) +1
Since valid probability transition matrix P (M) requires that the row sums equal one, the ambient space PT (M) lies in has dimension M x (S - 1). Since the solution space of (MM that satisfies Eq. (18) has dimension at most M (S M) + 1 with rank(A) > O, while the ambient space where P** (M) resides has dimension M (S - 1). When M > 1. the dimension of the solution space is significantly lower than that of the full space. Therefore, the set of points where pm (M) satisfies Eq. (18) forms subset of Lebesgue measure 0 in the x (S 1)-dimensional space.
(2) When 0 < rank(A) < M, the dimension of the solution set to XA- is M x (M - rank(A)) by Theorem 3.
Let H be a possible solution to XA- = O. Then we have
(INs F (Ias F
KIM H.
Rewrite the above equation, we have
PM 1 (IM k (IM 7PT (M)I (H + kIa)))..
?
Define G = [G|G = 1 (INr - k (Iw - -Pm (M)T (H + al)))) HA = 0, k E RR. Since the dimension of the solution set to XA = 0 is M x (M- ra))(A)) and Iy is not a solution to XA = 0, we have dim (G) =
M x (M rank (A)) + 1.
Fix G in G. Similar to the analysis of (1), the dimension of solution space of P*2(M) is at most M x (S - M))
Combining with the dimension of G. the dimension of solution space of p (MM) that satisfies Eq. (18) is most M x (5- M)) + M x (M- rank(A)) + 1 = M x (S - AA))(A)) + 1. Since the solution space of PT (M) that satisfies Eq. (18) has dimension at most M x (S rank(A)) + 1 with rank(A) 0, while the ambient space where (MM resides has dimension M x (S- - 1). When M > 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 pT (M) satisfies Eq. (18) forms subset of Lebesgue measure O in the M x (S - 1)-dimensional space.
(3) When rank(A) (A) 0, we have
(IN-
FT2y E
(LM F E O.
Plugging ET r (M) + 7 PM (M)V into the above equation and rearrange it, we have
TT (M) -I - FT2) (IM 1 F (1T)
(M) + -PP - (PPT(MM)
When P and rTT (M) are given, rTa (M) has only one solution. Hence, the solution space of TT (M) that satisfies Eq. (18) has dimension 0, while the ambient space where (MM) resides has dimension M x 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 n2 (M) satisfies Eq. (18) forms subset of Lebesgue measure 0 in the M D-dimensional space.
Theorem 4. Given a finite MDP (S, (S,A,P.r r,Pr. 7) where P the transition probability kernel and r 2 0 the reward function. The endpoints for any edges on B (H)()) are deterministic policies and only differ in one state-action pair almost surely.
Proof.
Suppose ni and 22 two neighbouring vertices in I(n).. By Lemma mi and ne that vertices of J(μ)) are deterministic policies.
Lemma 19 shows that the edge connecting Ti and T2 can only be formed by the long-term term return of policies that are convex combination of ア and 72, that is,
(aJ= (w) + (1 a) (n) a E [0, 1}} = [J m2 (n) | 1 E [0, 1]}-
However, if d( m > 1, Lemma 20 shows that it is almost surely that
(aJ (p) + (1 - a)) (p) a E [0,1]} * {J (J0m (n) E [0, 1]}.
This leads to a contradiction. Therefore, we must have d(T11 T2) = 1. This concludes the proof.
Theorem 5. Let C be a convex polytope, and let V be the set of vertices of C. Let denote the Pareto front of C, with V(P) and F(P) representing the set of vertices and faces on the Pareto front, respectively. Let Vp C (TP) and PpC C ((P) be subsets of the vertices and faces of the Pareto front, such that every face in FF P is composed of vertices in V P. Given set of vertices T C V such that Vp T. then Ep C ((Conv(T)).
24

---

Published as a conference paper at ICLR 2025
Proof. Pick face F from Ep. By Lemma 7, F is also on the boundary of C. Since the vertices of F belong to Vp, we can express F as:
F IP n {ar R
JuTz = c}.
where and wi TTa x S c for all æ E Moreover, since F is on the Pareto front, we have w > 0.
Given that Pp S T, F is a slice of the convex polytope Conv(T). F is a valid face of Conv (T) only if w x S c for all x E Conv(T).
We proceed by contradiction. Suppose there exists z E Conv (T) such that w > c. Since T C V and C = CVnv(V), it follows that CTnv(T) S C. This would imply that w (x - y) > 0 for some y E F and æ E C. As w > 0, by Lemma 8, this would imply that dominates y, which contradicts the assumption that is Pareto optimal point of C. Therefore, no such æ can exist, and F is a valid face of (Tny(T).
Thus, conclude that Fp S F(Conv(T)).
7
and Fp F(P), we have the following proposition. Proposition 2. Let C be convex polytope, and let V be the set of vertices of C. Let P denote the Pareto front of C, with ((P) and ((P) representing the set of vertices and faces on the Pareto front, respectively. Given a set of vertices T S V such that (F) C., then (IP)) C ((CCovvTT).
Consider a special case of Theorem 5 when Vp = V(P) and
E SUFFICIENCY OF TRAVERSING OVER EDGES
Lemma 21. (Existence of Neighborhood Edges on Pareto front of I(n)) Suppose J(u) contains multiple Pareto optimal
vertices. Let π be Pareto optimal policy, and let NJJ (H)),)), M(p) represent all neighboring points of (p))) on the boundary of I(].. Then, there exists J N(JJ [()) such that the edge connecting J and J (H) lies on the Pareto front.
Proof. By Lemma 1, J(x) is convex polytope. Given J (() J and J (μ) are neighboring vertices on I(H), and the edge between J and J (μO) is a 1-dimensional face of J(p). By the definition of Definition 1, there exists vector w. such that w. J (p) w. J, and for any J(2) that not on the edge between J and J (μ²), we have J.J. >> w/en x.
We first prove that there exists J E N(J=(H), such that w. > 0. We prove this by contradiction. Assume that for every J E N(JJ (p), there does not exist w. 0.
By the definition of the Pareto front, if J (4) is not strictly dominated by J, meaning that (4) is greater than or equal to // in some dimensions and strictly smaller in others, then there must exist positive vector wy 0. Hence, if for every J E N(J I()). w. > O does not exist, it implies that either J"(()) is strictly dominated by J or J is strictly dominated by J" (n.) Since J (n) is on the Pareto front, point in J(n) can strictly dominate (T))). Therefore, it must be the case that is strictly dominated by J (n)) for all J E N(J(()) I(4)). This implies that for all J E NJJ (p), and any > we have (J- (1)) < O.
We then show that J (1) dominates every point within J(n). For any point æ E J(H), we can express æ as a linear combination of J (n) and the neighboring points in N(J [p) with non-negative weight vector a::
= (T) +
Σ
an(J (²))).
Consider any such point æ and any vector u > O. We have:
w TT(x J (1))
w
(M)
Σ
ailJ, -((J--J(()) (T(
(M)
Σ ai(Ji- JEl (=)
w
Σ a:w (J: - J (11)
(M)
0.
25

---

Published as a conference paper at ICLR 2025
where the last inequality is because w wJ);- (J:- J (n)) < 0 for any J: E (()))1)) from previous analysis and a > component-wiselyy
This implies that J (1) dominates every point within I(n). However, this contradicts the condition that the multi- objective MDP has more than one deterministic Pareto optimal policy. Hence, our assumption wrong and there exists such that w. > O.
J E (n),
We next show that J, as well as the edge between and J (p)), is on the Pareto front. Since there exists a
w > O such that w [J .) 2 0 for any E J(j),, it follows Lemma 8 that J is also Pareto optimal. Moreover, the convex combination of J and J (u), written as aJ + (1 (1-00 a -1-a)
(u) with 0 v a I 1, is also a solution to the linear scalarization problem with weight vector w., > 0. Hence, the convex combination of J and J (p), i.e., the edge connecting J and J (u), is not strictly dominated by any point in J(u) and thus lies on Pareto front.
F LOCALITY PROPERTY OF BOUNDARY OF J(k) AND PARETO FRONT
This section provides the proofs for locality properties of the boundary of I(n) and the Pareto front. We will ignore the initial state distribution 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 II as I(4). By Lemma 1, is a convex polytope and vertices are the long-return of deterministic policies. Given polytope C and vertex on the polytope æ, we denote the set of neighbors on the polytope to x as N(x, C). Suppose deterministic policy π whose long term return J is a vertex on J. denote the set of deterministic policy whose long-term returns composes N(J", JJ) as N= J). Let Conv(J h U (JJ".. We denote the set of deterministic policies whose long-term returns compose N(J", Conv U {J*) })) pair.
{J*}) be the convex hull constructed by
as N=J,", Conv(JJl ((J"]) Let II, (T)) be the set of deterministic policies that differ from by only one state-action
Theorem 6. Let the long-term return of deterministic policy x, i.e,, Js, be a vertex on J. Then, N(J", Conv(JJh U (J+))) N N(J", (J) and (J", CCnv U (J" = N=(J ,J).
= N(J J) from (= Conv(J") U (J*)) = (JT, so will focus on proving (JJ, Conv( (J U {1
Proof. is enough to get N(J", Conv (JTT: U (J
= (J*.J))
We will prove (J", Conv U (J+N) = N₂ (JF, J) in two steps: first prove (J"," S N (J", Conv(J U {J*))), and then prove (JT, Conv (1 U (J* S (JT.J.).
(1) (1)N& S (NJ, (J",, U (J)))). We prove this by contradiction. Suppose there exists a deterministic policy such that Nz",", JJ) and u & N₂ (JJ Conv(J") U {J)
Suppose u E (T). Since u E (J",J), J lies above all the facets formed by J and the long-term return of other policies, including the policies in IT (T)). Since u E II then J would also belong to N(J Conv( U (J)))) by the definition of the convex hull, contradicting the assumption that Ju & N(J", Conv(J U (J))). Hence, u & II, (T).
Thus, u E (J(, JJ and u & II, (T) simutaneously, which contradicts Theorem that N₂ NJT, S II (T) almost surely. This causes contradiction, and therefore, N=(J*, C N₂(J", Conv U (J")).
(2) NJ Conv(J U (J))) C N+(J". J). We again proceed by contradiction. Suppose there exists a policy
such that e E NJJ, (Jnv(J ((J and & (T.).. We denote the straight line between J and J
E(JU, J²). Since v E Nz(T, Conv(Jul (J))))), ((J"JJ") is an edge of Conv (J (()"))), implying E(J J") cannot lie below all facets whose vertices are JR and long-term returns of policies belonging to NT(T, Conv (Juh U {J)
Given the condition that v & N₂ (T, J). follows that E(J", not on the boundary of J. that is. E(J", JT) lies below all facets of J. including the facets whose vertices correspond to π and policies belonging to Nx J). By (= JJ) S NJ(",, Conv(J U ()) from (1), we have that E(J", JT) also lies below all facets whose vertices are J and the long-term returns of policies belonging to (= Conv(J U {J*))). This contradicts the
fact that E(J JT) cannot lie below all facets whose vertices are J and long-term returns of policies belonging to (T Conv(Jill U {J)
The assumption that there exists a policy a such that e E N=(J", Conv(JIl, U (JJ))) and v & N=(x, leads a contradiction. Hence, (MT, Co, U (J) C (T,
26

---

Published as a conference paper at ICLR 2025
Combining steps (I) and (2), we have (T,, Conv( = (T, and N(T, This concludes the proof.
- N( ((.J.) J).
Lemma 22. Let P be a convex polytope, and let x be a vertex Pf Denote by the set of all vertices of IP that are neighbors Let C be the convex hull constructed by V V i.e., Conv(V U {x}), where V U ( are the vertices ofC. Then, the set of faces P that intersect at x, denoted as F(x,, P), is the same as the set of faces of C that intersect at x, denoted as (xx C), i..., ((ar, = (xxe C).
Proof. We will prove the two inclusions: F(x, P) S Fx C) and F(z, C) F().)).
(1) F(, C (Fx,C) C).
Suppose I' a face in (x,,P) Then, there exists a vector w and a scalar e such that w To C, and the face can c}. where the vertices of F are a subset of V. Since C is the convex hull
be written as F = IP fz E Rd : w constructed by V (z), F is slice contained in C.
For F to be valid face of C, it must satisfy w S for all E C. We prove this by contradiction: suppose there exists y E C such that T y > c. Therefore, y lies above points in TP in the direction of un. Since C is subset of TP (because C is the convex hull of subset of the vertices of IP), this would imply that y lies above all points in C in the direction w, which contradicts the assumption that y E C.
Therefore, F is also a valid face of C, implying F(x, P) S C),
(2) (a, C) C F(x,P),
The argument is analogous to part (1). Suppose F is face of C that intersects at æ. Then F can be written F en (y E TRd w = c). where ur TTa x = c, and w y S for any y E C. With the same analysis as in (1), F is slice contained in C. Since any point E IP can be expressed as a linear combination of æ and its neighboring vertices U, E V, we have:
w w x I 05 - 2)) S
where a; > O, and w x and w 0; S c. Therefore, F is also a face of P.
Combining (1) and (2), conclude that F(x, F(x, C).
Proposition 3. Let the long-term return of deterministic policy n, i.e. J", be a vertex Fet (( be the set of faces of the convex hull constructed by Jul, U {JJ} that intersect at J". Similarly, let [FJ JJ) be the set of faces of that intersect at J Then, B(J", Conv U (J) = F[J",J)
Proof. By Theorem 6, we know that N(J*, Conv(J () N(J JJ). According to Lemma 22, two sets of vertices have the same set of neighbor vertices, then the sets of faces formed by those vertices are identical. Hence, conclude that F(J", Conv U (J"))) = =F(J".])
Proposition 4. Let n be a policy the Pareto front of J. Let (I)((T)) C (T) be the set of policies belonging to [1(T)) that are not dominated by any other policies in Ih (T), and let N(J" (onv(JJl1.00 U (J"J)) be the set of neighbors of JR the convex hull constructed by J U (J"). Similarly, let N(J", ,(()) be the set of neighbors of J on the Pareto front of J. Then we have
N(J", P(J)) S N(J", Conv(JJ U (J)
Proof. By Lemma 7, the Pareto front lies on the boundary of J. Therefore, the neighbors of π the Pareto front, N(J", ((]),, are the intersection of the set of vertices on J neighboring J and the Pareto front. Formally, we have N(JJ PJJ) ,(J=.J) (JJ..
Define ND(II,) as the set of all policies (including stochastic and deterministic policies) that are not dominated by any other policies in IT. Since the Pareto front consists of the long-term return of policies that are not dominated by any other policies in II, it follows that PJJ) C (ND()),) Thus, we have P(J) C N(J=,J)
JND(L.),
By Theorem we know that N(J", Conv (J (J*J)) N(J".J). Therefore, combining with N(J",P(J)) C N(J", JJ JND(I.), we can conclude:
N(J P(J)) C N(J", Conv(J I1 U (JJ)))) (.D ND(n))
27

---

Published as a conference paper at ICLR 2025
Next, consider any point J E N(J", ((""))")("")(()))))))) J" E l n (ND()) This means that u is in 11, (T) and is not dominated by any policy in 11, (T). thus u (T). And since J is also a vertex of the convex hull constructed by : U {J"), it does not lie below all facets formed by the long-term return of any other policies belonging to [I and я. Since II [DD) - [T), follows that J" does not lie below all facets formed by the long-term return of any other policies in 11 T) and π. Therefore,
By N(J", Conv ((-)) S Jm, we have
J" E N(J", Conv U {J")). Thus, we have:
[(T, Conv U (J" n (ND(L)) C NNJ", Conv (J U (()))).
Combining this with the previous result, conclude:
N(J", P(J)) S N(J", Conv u (()))))
Then we also have (J",P(DI E (J,, Conv(JUI..D U (J*])). Proposition 5.
Let v be policy on the Pareto front of J. Let II (D S (T)) (T) that are not dominated by any other policies in l1,(T), and let F Conv(Jul. U ((J))) be the set of faces of the convex hull constructed by _ U {JJ} } that intersect at J Similarly, let F[J", P(J)) be the set of faces on the Pareto front of J that intersect at J Then, we have:
be the set of policies belonging to
[JJ", P(T)) C R(J", Conv aJ U (J))).
Remark 1. Note that in this case, the faces of the convex hull Conv ( U {x+) that intersect at x may not necessarity lie on J. However, the characteristies of the Pureto front from Theorem 5 to show that faces of the convex hull Conv([ U {2z)) that intersect at x lie on the Pareto front of I.
can use the condition (JJ) & N(T, CInv(I from Proposition 4 and
Proof. Since NJT Conv ND U (()))) E D.D, then N(J*, Conv(J"l U (J* J. J. By Proposition 4, we have N(J", (J)) S N(J" Conv(J U ()). By Theorem 5, the set of faces Pareto front constructed by J and vertices belonging to N(J", ,(J)) is a subset of the set of faces of the convex hull constructed by J U {J*), i.e., F(J", PJJ) C [J]", Conv Conv(Jun..o (Jul.,o (J)))) This concludes our proof.
Proposition 6. (Restatement of Proposition 1) Let Ep(J", Conv U (JTH)) denote the set of faces of F(J", (Jnv(J U (J) that satisfying Lemma 3. Then, we have
B(J", P(J)) = [PJ", CJnv ({J*)))
Proof. We prove this by two inclusions: F(J", P(J)) [PP(J" Conv(J U {JT and Ep(J", Conv U (JTH)) C F(JJ, P(J)).
(1) (EJ(,,,PUU) F(J", ,(()) S CFJ", [())), ND U (J"))), we have F FFF Conv(Jul ( (()))))
C [J Conv(J U (JF))) Let F E P(J). Since Proposition 5 proves that
Since F is face on the Pareto front of J and Conv Conv(J (J U (JJT) 1) is a subset of J. F is also the Pareto front of Conv(J" U (J*)). Therefore, F satisfies Lemma 3 in Conv(J (J. Thus, we have [[J", P(J)) S (JJ Conv(J ( U ((()))
U (JJ)) and F E FP(J", Co U
(2) Fr(J= Conv(J ND U (J) C F(J" P(J)). Let F Fr",", Conv(J U (J)))), By Lemma 8, there exists a weight vector w > 0 such that w (x - y) 2 0 for any x E F and y E (Cony(JULLN U {J* Since N AD CConv(J (IIL.S U {J) the inequality also holds for any I E F and y E JJILNN For any 2 E J z either belongs to juh,,n or is dominated by y E ND In both cases, w (x - 2) 2 0 implyyng x is not dominated by any = E JuI: Thus, F is a Pareto optimal face of Conv(Ju (J.))). Suppose that F written the intersection of
facets, i.c., F = ni= Fi, where F; Conv(J U (JT)) Rd: w x c.}, we can express F as:
F Conv(J U (JT x BERS, Laww? I Ea.c
where for any a 2 0. As F = Conv(J U (J (a E Rd, w x = c), there exists a non-negative a such that = E, a,w; 0. That is, there exists non-negative linear combination of these facets Conv(J U (J"]) that intersects on J such that the linear combination is strictly positive.
As F(ConveJ U (J*])) = F(J by Proposition 3, there exists non-negative linear combination of facets of [FJ"", .J) that intersects on J such that the combination is strictly positive. By Lemma 3 again, F E FFJJ,,(D)
Combining (1) and (2) concludes the proof.
28

---

Published as a conference paper at ICLR 2025
G FIND PARETO FRONT ON CCS
By Lemma 9, each nonempty face F of a convex polytope can written as the intersection of facets {Fi)i. i.c., F = (.(..))
Lemma 23. (Restatement of Lemma 3) Given a convex polytope C, a face F of C lies on the Pareto front if and only if the following conditions hold:
When F is a facet Cf i.e. dim(F) dim (C) - 1, there exists 0 such that F C {2 E R TTx co}.
When 0 S FF) < dim(L) - and F is the intersection facets of C, i.e., F NyFF,, where each facet written as F; Cn {a _2d w x c.), there exists a linear combination of the normal vectors with weight vector a 2 0, such that E, W; > 0.
Proof. When If C Rd w co is a facet of C. by the definition of valid linear inequality, the inequality
w TT y S co holds for all points y E C. Since w 0, for any æ on and any y E C, we have w Lemma 8, this is equivalent that point in C dominates æ and F lies on the Pareto front.
(y - x)) S 0. By
When F is a lower-dimensions face of C, written as the intersection of n facets, i.e. F = Fi where F, = Cn E Rd wp x c;). we can express as:
F C x ZERE; Σ a x =x===aah ase
where a 2 0. Since E, w, > 0, for any x on and any E C, there exists a vector w > 0 such that w (y (y- ) S 0. Therefore, by Lemma 8, this equivalent no point in C strictly dominates and FF lies on the Pareto front.
Lemma 24. Let be a face J. and let 1 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 I1., i.e..
F = lr T(als)
E a. a Eaa= Retll
Proof. By Lemma I, is convex polytope, and its vertices correspond to deterministic policies. Since Fis face of the convex polytope J. by the definition face, there exist w and e such that F' fx R w x = nJJ, and for any E J. w y S. Therefore, I
arg max w J" where Th denotes the of all deterministic policies. By Lemma 14, the convex hull of μp.. i... {i [(aas) Emen, (als) 2 0, 0,E, [R=11, con- structs policies (including stochastic and deterministic) that maximize JR. Thus, the long- term returns of { [[(ass)) = Exelr (a)s()))) 2 0, O, = =] construct F. Formally, F {J= i(aas) Em.eup a,t((als). 2 0. O.E. 1]. This concludes the proof.
H COMPLEXITY COMPARISON BETWEEN OLS AND ALGORITHM
Let S, A, and D represent the state space size, the action space size, and the reward dimension, respectively. Let N denote the number of vertices on the Pareto front.
For each iteration, OLS solves the single-objective MDP with a preference vector, removes obsolete preference vectors with the new points, and computes new preference vectors. Solving the single-objective planning problem incurs a complexity of (C Cpe), where C.a and Cpe represent the computational complexity of single-objective MDP solver and policy evaluation, respectively. The complexity of comparing with the previous candidate Pareto optimal policies and removing obsolete ones ((N D), and the complexity calculating a new preference vector is denoted as Owe- The computational complexity of OLS is O(N2 + NCwe NC + NCpe).
Al Algorithm requires only a one-time single-objective planning step during the initialization phase to obtain the initial deterministic Pareto-optimal policy. The overall computational complexity of our algorithm is OCoso + NNAC
29

---

Published as conference paper at ICLR 2025
NCND + NCeex), where CND and Cevx represent the computational complexity to select the non-dominated policies and computing faces of the convex hull, respectively.
Specifically, we dive deeper into the computational complexity of each module.
Cso- The computational complexity of singlc-objective planning is Cso = +
Ope. The computational complexity the policy evaluation is Cpe - -
OND- CND refers to the complexity of finding IND. the set of non-dominated policies from lh, Let
NND ND The non-dominated policies searching complexity is OND OSS
Cevx- Cevx is the complexity of computing the convex hull faces formed by NND + points that intersect at the current policy. If the number of vertices of the output convex hull is Nevx- By [1], the complexity of the calculation of convex hull is ONNd log Nevx) when //L/////(D/211))
3 and O N..DNN.o//eew where fL
As Algorithm 1 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. Moreover, note that calculating new weight in OLS requires calculating the vertices of the convex hull constructed by N + D hyperplanes of dimension D 1, making it significantly more expensive than the local convex hull construction of neighboring policies in our proposed algorithm. Hence, Cwe much larger than Cevx.
In conclusion, our algorithm induces total computational complexity of O(S A* A A+ A D Cevx), A+ 4 while OLS has computation complexity ASS NN is more efficient than OLS in all cases.
Given Cevx < Cwes our algorithm
SUPPORTING ALGORIHTS
For completeness, we provide the PPrune algorithm (Roijers, 2016), which identifies the non-dominated vector value functions V from given set of vector value functions V. Note that, with slight abuse of notation, here refers to the set of vector value functions rather than the set of vertices used in the main text.
Algorithm PPrune(V) (Roijers, 2016)
Input: A set of value vectors V
1: V
+ Ø
while V * Ø do
3: V + the first element of V
for all V V do
5: if V > V then
V V' 7: end if
end for
9: Remove V and all vectors dominated by V from V
10: Add V to V
11:
end while
12:
return V
The benchmark algorithm retrieves the Pareto front in two steps: (1) evaluate all deterministic policies and compute the convex hull of all non-dominated deterministic policies and (2) apply Algorithm 2 to identify the Pareto front. The details of the benchmark algorithm are shown in Algorithm 4.
EXPERIMENT RESULTS
We adopt the deep-sea- teep-sea-treasure treasureeur setting from Yang al. (2019a) and construct a scenario where the agent navigates grid world, making trade-offs between different objectives. At each step, the agent can move up, down, left, or right, and the reward for each grid generated randomly. We compare the performance of the OLS algorithm and the proposed Pareto front scarching algorithm under different grid sizes (varying numbers of rows and columns). The experiments
30

---

Published as conference paper at ICLR 2025
Algorithm Benchmark Algorithm
Input:
MDP settings: (S, r.r,
Output: the set of Pareto optimal faces P(TT) and the set of deterministic Pareto optimal policies V(IT)
1: Generate all deterministic policies IIp. Select non-dominated policies 1Ip. ND from 1ID.
Caleulate the convex hull formed by {JH и E [DDDD)
Extract Pareto optimal faces P(TI) and vertices V(II) from the convex hull with Algorithm 2.
were conducted on smaller grid sizes to ensure that the running time of OLS remained manageable, As shown in the Fig. 7, the proposed algorithm consistently outperforms OLS in terms of efficiency across all tested settings.
We evaluate the trend the number of vertices in terms and A with the state space size ranging from 10 to 50 and the action space sizes ranging from 10 to 20. The reward dimension is 3. As shown in Fig, 8, the result shows that the number of vertices grows approximately as N SS A. where & is constant number. Combined with the computational complexity analysis O A 5 1 NS A NS Coxx), this demonstrates the scalability of our algorithm.
30000
row=4, proposed
1000
$ 19
==10
25000
row 4, OLS
30
==
Running time (s)
20000
ro 3, proposed
3200
=
row 3, OLS
2500
15000
3006
10000
0
5000
5
1266
500
0
3.0
3.5
4.0
4.5
5.0
0.0
03
1.
20
25
# of cols
S3A
Figure 7: Pareto front of simple MDP with S = 4, and
Figure 8: Comparison between the proposed Pareto
A
front searching algorithm and the benchmark algo- rithm when D = 3.
31


Reviews:
[{"review_id": "oR0OoAaDEm", "reviewer": "Reviewer_5te3", "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.", "questions": "Could the authors elaborate on potential modifications to improve the algorithm's scalability with larger action and state spaces?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 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.\n2. 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.", "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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "G6EVzVEFCw", "reviewer": "Reviewer_n21h", "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.", "questions": "see weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper is well written.\n\n- The idea is interesting and novel, and the results are significant.", "weaknesses": "- The complexity analysis lacks clarity, particularly when compared to other algorithms. A more explicit comparison would significantly improve the discussion.\n\n- The numerical evaluation is restricted to small instances, which are insufficient to demonstrate the scalability of the proposed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N37L4erMLA", "reviewer": "Reviewer_JJrB", "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.", "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?\n\nRegarding 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?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I think the paper is written very clearly. In particular the proof sketches are structured in a helpful manner.\nThe paper makes good use of examples to explain technical points of the algorithm (ex. paragraph around 407).\n\nThe 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.", "weaknesses": "In other settings the assumption of ergodicity is a significant one. I think this should be highlighted a bit more.\n\nThis 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.)\n\nI think the wording of the definition of ergodicity should be clarified. The provided definition sounds similar to the definition of a communicating MDP.\n\nThe 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)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Zjx5Xu1ECv", "reviewer": "Reviewer_QTi5", "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. \nThe 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.\nThe empirical studies demonstrate the proposed algorithm maintains a much better run time than Optimistic Linear Support (OLS).", "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?\n\nCan the algorithm be adapted for use in continuous action spaces?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 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.\nThe paper has good quality, and is supported by theoretical proofs and empirical evidence.\nThe 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.\nThe 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.", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Dy3FPX9IvY", "reviewer": "Reviewer_WFhh", "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.", "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? \n\n- What are assumptions about MDPs made in analysis (e.g. finite state/action spaces, ergodicity, etc.)? Can the authors state them in theorems? \n\n- 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? \n\n- Can the authors provide some use examples of the entire Pareto front?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 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. \n\n- 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. \n \n- 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.\n\n- The authors evaluate the performance of the proposed method in an experiment, showing better runtime compared to benchmark.", "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. \n\n- 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. \n\n- 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.  \n\n- The scalability of Algorithm 1 is not analyzed regarding the size of MDP and dimension of reward. \n\n- Regarding the properties of the vector value function, it would be helpful if the authors could provide some examples or intuitions behind them. \n\n- The current analysis seems to be limited to finite MDPs. It would be useful to extending it to MDPs with continuous spaces.\n\n- The example in experiments is artificial. It would be useful if the authors could provide some practical use cases.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eY5cU3Vpyf", "reviewer": "Reviewer_hhfj", "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.", "questions": "Please address the concerns and questions raised in the weaknesses section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 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.\n* 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.\n* The writing is clear and well-structured with good visual presentations.", "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.\n* 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?\n* 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. \n\n[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.\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LnasYK4NCB", "reviewer": "Reviewer_4Q5J", "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.", "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?\n\n2. 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.) \n\n3. 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.\nAlso, I cannot locate the proof of Lemma 3.\n\n4. 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.\n\n5. It would be better to add relevant existing algorithms in the appendix (e.g. Roijers, PPrune algorithm) for the completeness.\n\n6. It would be better to note the corresponding proof locations below all theorems (e.g. Theorem 2, Proposition 1).\n\n7. 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).\n\nI am giving the score of 6 for the current draft, but I am eager to talk with the authors and reconsider the score.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "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. \nThe idea of identifying the vertices as deterministic policies through a linear transformation for Multi-Objective MDPs is impressive.\nI 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.", "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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)