Multi-Objective Reinforcement Learning: Convexity, Stationarity and Pareto Optimality
Authors: Haoye Lu
Daniel Herman
Yaoliang Yu
Venue: ICLR 2023 poster (2023)

Abstract: In recent years, single-objective reinforcement learning (SORL) algorithms have received a significant amount of attention and seen some strong results. However, it is generally recognized that many practical problems have intrinsic multi-objective properties that cannot be easily handled by SORL algorithms. Although there have been many multi-objective reinforcement learning (MORL) algorithms proposed, there has been little recent exploration of the fundamental properties of the spaces we are learning in. In this paper, we perform a rigorous analysis of policy induced value functions and use the insights to distinguish three views of Pareto optimality. The results imply the convexity of the induced value function's range for stationary policies and suggest that any point of its Pareto front can be achieved by training a policy using linear scalarization (LS). We show the problem that leads to the suboptimal performance of LS can be solved by adding strongly concave terms to the immediate rewards, which motivates us to propose a new vector reward-based Q-learning algorithm, CAPQL. Combined with an actor-critic formulation, our algorithm achieves state-of-the-art performance on multiple MuJoCo tasks in the preference agnostic setting. Furthermore, we empirically show that, in contrast to other LS-based algorithms, our approach is significantly more stable, achieving similar results across various random seeds. 

Published as a conference paper at ICLR 2023
MULTI-OBIECTIVE REINFORCEMENT LEARNING: CONVEXITY, STATIONARITY AND PARETO OPTIMALITY
Haoye Lu, Daniel Herman & Yaoliang Yu School of Computer Science, University of Waterloo
Vector Institute
(haoye. lu,, d2herman, rman, yacliang yu) yu)@uwaterloo.ce
ABSTRACT
In recent years, single-objective reinforcement learning (SORL) algorithms have received a significant amount of attention and seen some strong results. However, it is generally recognized that many practical problems have intrinsic multi-objective properties that cannot be easily handled by SORI. algorithms. Although there have been many multi-objective reinforcement learning (MORL) algorithms proposed, there has been little recent exploration of the fundamental properties of the spaces we are learning in. In this paper, we perform rigorous analysis of policy induced value functions and use the insights to distinguish three views of Pareto optimality. The results imply the convexity of the induced value function's 's range for stationary policies and suggest that any point of its Pareto front be achieved by training a policy using linear scalarization (LSS). We show the problem that leads to the suboptimal performance LS can be solved by adding strongly concave terms the immediate rewards, which motivates us to propose a new vector reward-based Q-learning algorithm, CAPQL. Combined with an actor-critic formulation, our algorithm achieves state-of-the-ar performance on multiple MuJoCo tasks in the preference agnostic setting. Furthermore, we empirically show that, in contrast to other LS-based algorithms, our approach is significantly more stable, achieving similar results across various random seeds.
INTRODUCTION
The past decade has seen the rapid development of reinforcement learning (RL) algorithms. Recent breakthroughs in RL have made it possible to develop policies that exceed human-level performance: Atari (Mnih al., 2015), Dota 2 (OpenAI al., 2019), etc. Despite their great success, the vast majority of RL algorithms are single-objective based. Although many practical problems can be reduced to a SORL task, there an increasing recognition that many real-world tasks require us to consider their multi-objective nature (Coello, 2000; Pickett & Barto, 2002; Moffaert & Nowé, 2014; Roijers al., 2013; Abels et al., 2019; Abdolmaleki et al., 2020; Abdelaziz al., 2021). There many works that discuss how to find optimal policies in multi-objective RL (MORL) problem (Gâbor et al., 1998; Pickett & Barto, 2002; Moffaert Nowé, 2014; Roijers et al., 2013; Yang al., 2019; Parisi et al., 2016; Mahapatra & Rajan, 2020) or more general dynamic programming setting (Sobel, 1975; Corley, 1985), but the relationship among various definitions of Pareto optimal policies is hardly discussed. Moreover, there is rigorous analysis of the range of induced value functions, which has been thought hard to characterize and of irregular shapes (Vamplew et al., 2008; Roijers al., 2013; Reymond & Nowe, 2019). (Note, similar work has been done for mixed policies, but fundamentally differs from the more common stationary policy that is sought in modern RL.) We hope to give researchers well aligned intuitions about MORL problems that can save effort and accelerate the rate of research in the field; it is to this end that we introduce this paper.'
Within this paper, we perform a theoretical analysis of MORL problems with an infinite horizon (rigorous proofs are given in Appx B). After quick review of the MORL setting and three widely- adopted definitions of Pareto efficiency (PF), we begin our analysis by characterizing the effects
Extra literature reviews are given in Appx A.

---

Published as a conference paper at ICLR 2023
of policy alterations on the induced value function. We find that single-state policy alterations insufficient to optimize the induced value function in a MORL setting, but show how it can be done by multi-state state update. We also prove that improving in all states is generally not possible. From here, we show that the range of value functions is convex, which suggests that linear scalarization (LS) is not the bottleneck in finding PE policies. We discuss the deficiencies of existing LS-based algorithms as suggested by our theory and fix them by augmenting the reward function using strongly convex term. These insights motivate us to propose new MORL algorithm (CAPQL) which achieves state-of titte-of-th-arr performance on multiple MoJoCo environments in the preference agnostic setting. An ablation study is performed to understand how augmentation affects the algorithm's 's performance.
MULTI-OBIECTIVE RL PROBLEM
To begin, we will do a quick review of MORL problems and the notation we will be using, as well as introduce definitions of Pareto optimality. Like SORL problems, consider an agent interacting with an environment. At each step. the agent performs an action based on the current state and the environment returns reward and the next state. Our setting assumes vector reward in IR and is reduced to a SORL problem if d = 1. We model the interaction as a Markov Decision Process (MDP) (S,A, R, 7) As usual, S and A the sets of states and actions, and 7 (0, 1) the discount factor. Our discussion considers finite A and S. When the agent takes action a E A in state s E S, the environment gives reward R(a, s) Idd and moves to the next state following the transition probability P(a.s) s) E l In this paper, we consider an -hriiite MORL problem and assume bounded rewards. Let R(s)= = [[(a, s)Ia E AA Rdx[AAl and P(s) = [P(a, s) A] R [[ Il the set of all stationary policies, where π E Il maps a state to a distribution over actions, Following the work of Roijers et al. (2013), given π E II, the induced value function (*()s) E Rd returns the expected sum of discounted reward over the interaction trajectory with the initial state s,
(T()) == E
E 7" R(aa, st) with st P( St-1), ac-1 ~ (st-1) 30 = s.
(1)
Let p: + [0, 1] be the probability distribution over initial states. The expected value function is: vT = R En
1= R(ar, s with 8t ~ P(at-1,8t-1) a:-1 ((8-1)) and 80 Jr. (2) That is, V Begna V (so). Let V [V*(s)]s S] E Raxisi, V(s) = (s) II). V (V e I1) and V= (V= I1]. The Bellman equation (Bellman, 2003) can be written as:
V=(+)= (R(s) ( +VV))(s) T(s) f
In RL, we are interested in finding π that maximizes (T()). When d = 1, the regular order defined on R is adopted, and the optimal policy gives the greatest (T).). For d > 1, we con- sider the Pareto order (PO): for real-valued tensors u, of the same shape, u v if every entry of u is not less than its counterpart in à For a set of tensors of the same shape, v E C is Pareto efficient (PE) if for all elements.) In this paper, we are interested in three types of PE policies that are not carefully distin- guished in the existing literature (Roijers et al., 2013; Song al., 2020; Abdolmaleki et al., 2020).
C, either Z
d (A set may have multiple PE
Definition (Pareto efficient policies) For E S and initial state distribution p. π E II is single-state PE (SPE) V (s) is PE (s), and it is distributed initial state PE (DPE) VS is PE in V μ. Likewise, π E II is aggregate PE (APE) V is PE
SPE DPE APE
approact
Figure 1: The relationship among three types of PE in Defn 1.
in V. Let 115, 11, and I1* denote the sets of policies that are SPE, DPE and APE, respectively.
In Sec 4.2, assuming the Markov chain is ergodic, we show that SPE and DPE are equivalent and have the relationship with APE demonstrated in Fig. 1. Since we prove that for all E S. II; coincide, may not specify to which state we are referring to when discussing SPE.
2 The entries of V (s) are induced value functions in SORL and is known exist. Thus, (s) also exists. If every entry in is strictly greater than its counterpart in v. we write u > v. In general, not all tensors are comparable. For example, given ()) and ()), u o and 1 v. We write oe < (u o v) A (u 1 v). For single-entry tensors, PO reduced the regular order defined on IR.
2

---

Published as a conference paper at ICLR 2023
Optimizing MORL using linear scalarization (LS). It is common convert MORL problems to SORL problems by LS (White, 1993). To do so, take a nonzero vector w E R and take the dot product of the reward vector via w R[a,,s) s). In fact, for any can left multiply Eq (3) by w to see that w T V is the induced value function of the associated SORL problem. We refer the associated SORL problem with weight as SORI(().
In this paper, rely on the intimate relationship between MORL and the associated SORL problems to characterize the properties of PE policies (of both types). Our characterization shows that LS does not necessarily inhibit agents from finding desired PE policies, and sheds light the challenges that modern MORL algorithms face when searching for PE policies.
3 FINE-GRAINED CONTROL OF INDUCED VALUE FUNCTIONS
In this section, we study the dynamics of the induced value functions resultant from policy alterations in MORL problems. Our discussion starts by characterizing the effects of single-state policy adjustments. We will show that, unlike SORL, it is not always possible to optimize the value function by optimizing single-state actions. This suggests that the popular Bellman operator, optimizing policies single-state basis, does not sufficiently improve a policy's 's performance in the MORL setting.
State 5p
State $;
All aotid vol v*Ue)
Adi malo) yagg) Vila
Objective 1
10 Objective
100 Objective
Figure 2: The induced value functions of selected
policies in Ex 1. Here, To: An è = 0.5; #: Ao = 0.7, \ = 0.5. The pink line segments are the value function range for E 4 To), and the light blue patch is the value function range V.
The difficulties faced by single-state based op- timization techniques reveal the intrinsic differ- ence between the SORL and MORL optimiza- tions, which motivates us to investigate how to adjust multiple states' actions to jointly improve the induced function values.
State St
State
10
AL sddd M661
vMoul
Vhoui
To make our theoretical results intuitive, we will use the following example throughout this paper.
Example 1 Consider a two-objective problem with S {ss,, $1} and A {ag, 01 ). For
0
Oleectiee D
Olpective
each state 8, the chance of staying in 8 is 50% for both actions. Let R(an, so)
5]
The induced value functions of selected policies in a two-state MORI. problem with the configuration given in Ex 1. Here, To. do \ = 0.5; n. A 0.7, X = 0.5; my: Ao 0.5. A1 = 0.7. Starting from To. the pink area cor- responds to the value functions of iT obtained by adjusting (5))) (i.e., An), the green area is the one by adjusting (s1) (i.e., Aι) and the grey area is the one by adjusting both. The red vector indicates the shifting direction when increasing Ao and \ at the same rate.
Figure 3:
R(ai, 80) [5, 1
R(ag, 81) = [10,
R(a,, = [5, 2] T and 7 0.5. The induced
value function of π satisfies:
Va (*T(s) = [
m + +
0.5 0.5
(so);
0.5 0.5
(T((s)= = [
10 +
[.5 0.5
(s1))
2
[.55 0.5
Since |A] 2, \ = Pritaking ag in s;),
(0. 13 is sufficient to specify a policy because Pr(taking a1 in s;)
X
3.1 ADJUSTING THE POLICY IN A SINGLE STATE
In this section, we discuss the properties of the induced value funetions when the policy is modified in single state. In particular, given 8p E S and To E II, we temporarily restrict our attention to the policies equal to No in all states except so; this is the set:
((80, To) == {πt II (s) To(s) for so}
(4)
Fig plots the value function's 's range with To in Ex 1: A = x₁ = 0.5. The plot shows, when (Tp)) changed (i.e. $500 Ro)), its induced value function moves along line segment in both states
3

---

Published as a conference paper at ICLR 2023
with the same moving direction but at different rates. For instance, in Fig 2, mark the value function of क by green dots, where के : A = 0.7, λ = 0.5. In comparison to To (blue dots), V moves faster in so than in $1, which is intuitive because the adjustment is made in Sp and should change its value function by the greatest magnitude. Our observations here indeed hold in general:
Proposition 1 For To. T1 E ((00, To), let Ta = (1 a + 0 Then
(v) aV== E ( (116:000]]
(5)
da
da
where the random variable X (s; is the number of steps to reach so starting from s; its distribution is identical for Tu. TT, and a. Moreover,
Vo + so) Vm
(6)
ordb where B(a;; (1-a)oo+adh and Ø, 7, 1] is scalar depending on n, and the RL problem settings but independent from o.*
In Prop 1, Eq (5) says when Ta (50) moves from To to T (so), the value functions in all states move along the same direction =v (so) while the moving rate is scaled by EE [[>xX(<:e0)) for state 8 E S. We note that (so: su) = and (s; so) 2 1 for all & 80- Therefore, the induced value function always changes the most drastically in So, which is what observed in Fig 2.
8a
Eq (6) shows that, if we modify the policy in so by letting To (80) ) be convex combination of (s)) and mi (5o) E ((00 m.), then V^a (8o) is a convex combination of (so) and V (8o). Consider the example presented in Fig 2: every policy x' Ø(50, (T)) can be seen convex combination between To and some policy mı E (s0. mo) with V (50) on the boundary (where Tı depends T').
Moreover, every point between 7 (sp) and 4 (so) corresponds to policy in (SSo, To).
Single-state optimization is not sufficient to improve policies in MORL. It is known that, in SORL problems, a single-state action optimization is sufficient to increase the value function in all states (Sutton & Barto, 2018, p78). Unfortunately, this does not generally hold in MORL problems.
To give a counterexample, consider the setting in Ex 1. Given ma Åo = A = 0.5, we plot the induced values of obtained by modifying exactly one state's policy in Fig 3. Here, the pink line segment is the set of value functions obtained by modifying To(so). Similarly, the green line segment is obtained by changing (s1).. As we can observe, when updating a single state's policy, one objective must be traded off to optimize the other one. This can be clarified by considering the policy optimization of Su: taking actions ag and an gives the rewards [1, 5) and [5, 1] respectively. so the immediate expected reward for this state is [-4xp + 4Nu + 1]. Thus, no single-state policy adjustment will improve both objectives.
3.2 ADJUSTING THE POLICY IN MULTIPLE STATES
The insufficiency of optimizing single-state actions motivates us to combine policy adjustments in mul- tiple states to jointly improve the value functions. In Fig 3, the vectors in red give the induced value func- tion's moving directions when we in- crease do and A₃ at the same rate. We observe that both objectives are improved in 81, but not in 8p. This suggests that we can adjust multiple states' policies simultancously to jointly improve its value function in state. This leads to the natural question: Are there rates of change for Xn and A₁ that improves the induced values at both states? The answer is negative. The first graph of Fig 4 plots the feasible changes of X and A that We give the closed-form expression of di in Cor in the appendix.
v-0.5
Y- 0.9
Viau Dec Vn
Des (la
Dec 19i5ol
Dec VMN
Dec (936
5
6.2
-1.2
0.2
-2.
0.2
0.8
Figure 4: Left: 7 = 0.5. The feasible changes on mo Ex that increase (decrease) the value function in two states (under the PO). Middle: 7 = 0.7. Right: 7 = 0.9.
4

---

Published as a conference paper at ICLR 2023
improve V (su) and VT (s1). When y 0.5, the feasible areas (blue and yellow) to improve both objectives in both states are disjoint and hence cannot be improved simultancously.
The mutual exclusiveness of the two areas is caused by the attenuation effect of the discount factor. Consider the induced value function obtained by increasing λ from 0.5 to 0.7 for To (the steel-blue dots in Fig. 3). This adjustment makes the induced function increase in Obj. at the cost of Obj. 0 for both states. Since we are making the adjustment from the perspective of so. the value function change is greatest in sy and is dampened by the discount factor y when viewed from $1. Similar observations can be made by increasing Å1 from 0.5 to 0.7. This attenuation of the reward propagation makes it impossible for the induced values to move in the same direction in all states, which prevents them from being optimized simultaneously. The last two plots of Fig. 4 show that when 7 increases, the feasible areas to improve induced values in both states overlap, which corroborate our claims. We generalize our observations by proving:
Proposition 2 Assume To E 11 is not optimal in the associated scalar problem for all w # O. Let 50 S. Then any neighbourhood of wo contains T1, 22 1l such that for any E2 we have
vaa (sn) - V (80) = Eiu u and V V
= E2 for some E1, E2,52 > O.
(7)
Moreover, the MDP is ergodic, as 7 - 1, V
v (s) - for all E
Prop 2 says that, under some weak conditions, we can move the induced value of To in state (or the expected induced value) along any direction. Setting u = 1, we improve the induced values. When the MDP is ergodic, T - 1, the values in all states move along u and will be optimized at the same time.
Visu)
Figure 5: VT is not optimal for any but cannot move along u.
We note that Prop is non-trivial because a policy's 's suboptimality over all associated scalar problems does not automatically imply the induced value function can move in any direction. For example, in Fig 5, V (sy) is not optimal in any associated SORL problem but cannot move along W. Prop 2 says (so) cannot have shape like this.
Remark
The first plot of Fig 4 shows Tu cannot be further improved in both states at the same time. This implies To is in fact APE. However, Fig 2 shows V (se) is in the middle of the induced value function range. Thus, there exists a policy π that has an induced value in So greater than V (so). and hence no is not SPE in 80- This observation tells us SPE and APE are different in general.
Remark
CONVEXITY AND PARETO EFFICIENT POLICIES
The analysis of the induced value function's 's behaviour in Sec 3 provides us with powerful tools to characterize their properties. In this section, we use these tools to show the convexity of the induced function's range and the relationships among the three types of PE.
4.1 CONVEXITY OF THE INDUCED FUNCTION RANGES
For more than a decade, it has been considered true that the induced value functions' ranges are irregularly shaped (for stationary policies) (Vamplew et al., 2008; Roijers et al., 2013; Hayes et al., 2022). In fact, this is the key reason behind the belief that LS is not powerful enough to find all PE policies. Prop 3 shows that this belief is not true, and the ranges of the functions actually convex.
Proposition 3 For s E S, Vs) is convex. Also, Vp is comvex
The convexity of (s) can be shown by repetitively applying Prop 2 to construct path between V (sp) and V= (s) with To, 2 E II. Roughly speaking, for any point v over the path, starting from V (s), we can repetitively use Prop
construct sequence of policies with the induced value approaches v. Thus, the path is included in V(x), and by definition, V(s) is convex. We can apply the similar idea to show V is convex.
Remark 3 Prop 3 can also be proved as a corollary of the convexity of the occupancy measure, initially derived in constrained Markov decision theory (Kallenberg, 1983; Puterman, 1994; Altman, 1999). We discuss their relationship and provide second proof of Prop 3 in Appx C.
5

---

Published as a conference paper at ICLR 2023
LS is not bottleneck in finding PE policies. The convexity of the induced value functions' ranges suggest that we can potentially find all SPE (DPE) policies through LS. In particular, we have:
State 5o
Objectivve
Proposition 4 For E S, 112 if πt is optimal in SORI(W) w) with some w > 0. Also, if E 11, (s) is optimal in SORI(W) with nonzero =
As result, a SPE (DPE) policy achieves optimality in some associ- ated SORL problem. This also suggests that we can potentially find all SPE (DPE) policies by choosing different weights in LSS.
5.0
7.5
10.0
12.5
Objective
Figure 6: Value functions of for various (Ao, in Ex The stars are deter- ministic SPE policies and the squares are stochastic ones; sub-optimal ones are marked by golden dots. The choice of weights for finding differ- ent SPE policies are plotted in the top-right corner, where the patch colours correspond to the found SPE policies'.
Problems of the existing LS-based algorithms. We suggest that there are two significant reasons why many algorithms cannot find a rich set of PE policies: determinism and numerical instability.
The majority of RL algorithms favour determinism. While it is well- known that an optimal deterministic policy always exists for SORL problems (Puterman, 1994, Ch 6), almost all PE value functions for MORL problem require stochastic policies. In Fig. 6, plot the value functions of state 8y for different policies in Ex We see that most PE policies are stochastic (squares) while the deterministic ones can only cover the vertexes (stars). This observation shows that unless almost all PE policies. Additionally, it is numerically impossible to obtain some SPE policies in practice although they can be found in theory. In fact, almost all nonzero weights w correspond to the SPE policies on the vertexes. For instance, in Fig. 6, we show the choice of weights for finding specific SPE policy in the up-right corner. While there is a wide range of weight selections for finding the SPE policies on the vertexes, only those on the boundary of the weeenncyaa/cyaan-pee purple patches can used to find the stochastic policies upper/right boundary the polytope. Specifically, only weight vectors normal to the Pareto front can be used to find stochastic policies. In practice, we do not know how to find such weights; even if we do, they cannot be picked as a tiny perturbation over them gives a weight corresponding to vertex. Besides, these weights are shared by set of stochastic SPE policies (on the same facet of the polytope). Thus, the algorithm would produce a random policy in the set with undesired value function even if the right weight is picked.
current algorithms can favour stochastic policies, we have implicitly excluded
Adding a strongly concave term fixes the problems. Let f: A + R be a strongly concave function for action-taking distributions. We then replace the regular reward R(ae, 8t) with R(a, 8x) = R(a,, 8t) + of( (s:)) 1, where Rd is a vector of ones and >> controls the strength of the
augmentation effect. Then the induced value function of policy æ for initial state s E S under this augmented setting becomes:
V. (s):=E
aaf(((())) 19]
st at 1 1
so=s. (8)
Let Var(s) (s)l 11), W {w 7
10.0
OJri < ||w]|| r2) for some r1, > and V/ the set of PE elements in (s)
Va
7.5
5.0
Fig shows how the reward augmentation changes the value function's 's range. We observe that the aug- mentation makes the shape of the PE element set V Vay()) strictly convex. Thus, for every w W+ there is unique V (s) E (s) that has the max- imum projection on w. Let Js denote this unique correspondence relationship from W to V. (s):
10
5
30 30
10
Figure 7: The effects on the induced value functions at sy for selected policies in Ex I by adding strongly concave terms to the im- mediate rewards with different alpha. Here, f returns the entropy of action taking distri- bution. Vay (5o) is marked in blue and the dots of the same colour among the four plots correspond to the same policy.
go (w()) argmax
w

---

Published as a conference paper at ICLR 2023
From Fig 7, we also observe that, the strict convexity of (a)(s) makes 9s (uniformly) continuous. As rotate clockwise, (w) slides from the left end of the blue curve the right for last three plots; in contrast, for the first one, it will jump from top left vertex to the middle one followed by the bottom right one, The continuity ga makes numerically possible pick good w with (ww) close to the desired PE element in V of (s). We summarize our observations in Prop 5.
Proposition 5 Function 9s given in (9) is well-defined, surjective and uniformly continuous.
Finally, the strongly concave term naturally injects the preference on the stochastic policies. Therefore, all the problems of the existing L.--base methods mentioned in Sec 4.1 has been fixed.
Remark 4 Function gs corresponds the extended target value function considered by Abels et al. (2019) and Yang et al. (2019). In their work, they implemented an extended Q-network, Q(s, a, w) and minimize [1gs(w) (w) E., ((,, a, w) w)llla for all S.a E AA and we will see that, as they adopted regular rewards without augmentation, the target value function 9s sensitive to the input w, making the training process unstable and lowering the algorithms' performance (Appx D describes the causes of this training instability). We will instead propose concave-augmente Pareto Q-learning algorithm (CAPQL). Our empirical study shows that the algorithm's performance improves with significantly more stable training trajectories.
Φ C W/+ In Sec
Remark 5 Fig 7 suggests that smaller a preserves more information about the original problem but makes (-)-) ) less robust to perturbations and lowers the stability of the algorithm approximating 9a- Likewise, a larger improves the stability but would harm the algorithm's expected performance.
4.2 RELATIONSHIPS AMONG THREE TYPES OF PE
Before we introduce our new LS-based MORL algorithm, we will complete our theoretical discussion about PE. In particular, we prove that the three types of PE have the relationship summarized in Fig. Throughout this section, we assume that the MDP is ergodic.
SPE state-independent and equivalent DPE. According Prop 4, if ग E II; for S. then it must be the optimal policy for some associated scalar problem with some nonzero w > 0. When w > O, we apply Prop 4 to conclude that E II for all s' and π E I If w contains zero entries, the problem can be approximated by assigning an arbitrarily small positive weight to the zero entries. Then, the problem is reduced to case with w 0. Since π is optimal in the associated problem of all states, none of its value functions can be improved independently or in aggregation. Hence, æ E II as well. We summarize the derived results in:
Proposition 6 If π E I, for some state s E S, then for all E S, π E IT Thus, the sets of single-state PE policies coincide for all initial states and is subsel of IT".
Using a similar derivation by linking the PE policies to the optimal solutions of the corresponding associated scalar problem also proves:
Proposition 7 A policy is SPE if and only if is DPE. That is, for 11; 11;-
SPE implies APE but not vice versa in general. For a selected state S. policy is SPE as long as its induced value function V (s) is PE in V(s). The function values for other states are not relevant. In contrast, APE involves the induced function value in all states. A policy is APE if have to trade off' the value functions of some states for improving those of the others.
For ergodic SORL problems, the induced value function policy я reaches the maximum in one state if and only if it reaches the maximum in all states (Prop 2.1.2 in (Bertsekas. 2022)). This implics that SPE and APE are equivalent in a SORL problem. However, the equivalence does not generally hold for MORL problems. In Rmk 2, we presented a where To E IT but no & IT* Besides, Prop shows that ग E II for some & E S, then π E II". As a result, IIo C II but do not necessarily coincide.
'We provide more rigorous proof in the appendix by constructing lexicographic order Rd
7

---

$. As Published as a conference paper at ICLR 2023
As we have noted in Sec 3.2, this proper subset relationship is due to the attenuation of the reward propagation caused by the discount factor. The attenuation makes the moving direction of the value function differ among various states and causes the feasible sets of improvement adjustments to be disjoint (see Fig 4). When 7 + 1, the moving directions of all states converge (Prop 2). Therefore, the feasible sets of improvement adjustments for different states will also converge and eventually overlaps for sufficiently large 7 (see the last two plots of Fig 4), Therefore, improvements can be made in all states until they reach the boundaries of the value functions' ranges. In other words:
Proposition 8 For all E S. as + 1, the SPE policy set IT;; approaches the APE one II"
5 CONCAVE-AUGMENTER PARETO Q-LEARNING
Motivated by the discussions in Sec 4.1, in this section, we develop new Q-learning algorithm with the reward augmented by a strongly concave term. We call our new algorithm concave-augmentee Pareto Q-learning (CAPQL).
5.1 MORL PROBLEM WITH AGNOSTIC WEIGHT PREFERENCE
Our CAPQL algorithm is designed for solving MORL problems where the preference weights for the objectives are (potentially) different between episodes and are not known in advance. The setting was initially considered by Abels et al. (2019) to propose a multi-objective Q-network (MOQ). In particular, the problem considers a set of weights & C W+. For each episode, a preference weight w E given, and the algorithm is expected maximize the sum of the rewards projected onto w. Thus, the algorithm has to handle all possible weights in Φ.
5.2 IMPLEMENTATION OF CAPQL
Following Abels el al.'s work, we consider an extended Q-network, Q(s,a, a, w), and train it to approximate the Q-values of a optimal policy of SORL(W) for all w E 4. Unlike MOQ that uses the reward R(a,, st) from the environment directly, CAPQL replaces it with R(a,, st) = R(a,,8)) + ozf ( (s:; I) where a 0. (
Notice that scaling w does change the selection of the induced value function Vay(s) that has the greatest projection it. Without loss of generality, we assume |/w]]2 1. Furthermore, set f to be the entropy operator H(g) = I q(a) log q(a) da (discussions on the selection of f are given in Appx E). We train our algorithm by optimizing it over SORL(W), for all w क For fixed w, the learning task of SORL(W) can be written as
(-: w) = argmax E Σ En00"
(w (Ra st) + a (s:; w))
(10)
x'( -(W)
which is obtained by projecting the value function defined in (8) onto w followed by taking the maxi- mum over the policies conditioned on it. Interestingly, this is the MORL extension of the learning task considered in SAC (Haarnoja et al., 2018). Hence, we implement the algorithm with the Q-network and policy network conditioned on w. In each training step, we first sample a weight w' and follow the SAC method to train the policy and the Q-network conditioned on it. (The implementation details, pseudocode are given in Appx F and convergence property is discussed in Appx G.)
As discussed in Prop 5 and Rmk 4, the optimal policy æ of SORI has the value function ys (w). Thus, the training is to make |E=r(s: [Q(s, a, w)] match gw()) for all s E S and Prop 5 shows, adding the entropy term makes the target (w) uniformly continuous with respect to w, which is easier to fit and less numerically unstable (in Appx H. we empirically show this phenomenon by training the algorithm over Ex and visualizing its g, (w)). Hence, we should expect CAPQL to both converge faster and be more numerically stable during training.
5.3 EXPERIEMENTS
We test our algorithm over a multi-objective version of the MuJoCo environment. The reward vector was created by simply exposing the individual components that went into the regular scalar reward:
8

---

Published as a conference paper at ICLR 2023
1.200
0:33
1.007
CAPEL
600
3000
1300
702
000
2200
200
2.6
milin stap
mil stape
(a) Hopper
(b) Walker2D
(c) HalfCheetah
(d) Humanoid
Figure 8: Training curves of the MORL algorithms in MuloCo environments with vector rewards.
adding them up recovers the default scalar reward. (See Appx I-Table for details.) We restrict & to only contain weights within 22.5 degrees of the unit vector to ensure that > 0. Finally, will also perform an ablation study to understand how the algorithm's 's performance changes with different strength of reward augmentation.
We compare method to two popular LS-based algorithms: MOQ (Abels et al., 2019) and EnvQ (Yang et al., 2019). MOQ can be seen as a special case of CAPQL as a - and EnvQ is its enhanced version. It has been shown that EnvQ enjoys higher sampling efficiency and has consistently better performance than MOQ on multiple MORL benchmarks. Since MOQ and EnvQ were proposed under the finite action setting, adapt them to MuJoCo's continuous action space, we follow Tang & Agrawal (2020)'s work and discretize each action dimension into five discrete values (e.g., Hopper has three action dimensions; then there are 5 125 actions). Additionally, we implement a continuous action version of EnvQ combined with an actor-critic formulation (referred as QEnv-ctn) for comparison. (The model and training configurations are summerized in Appx I).
Fig plots the methods' trajectories on four MuloCo bench- marks. We train each method five times with various random seeds and report the mean and standard deviation. In every step, we test them over ten randomly sampled weights. We observe that CAPQL has a consistently better performance over all benchmarks and enjoys faster convergence speed. Additionally, compared QEnv-ctn, CAPQI. has far more stable training trajectory over different random seeds.
Avg. Run with rdm. weight
1250
e-
0.02
1000
0.2
0.8
750
500
250
0.0
0.2
D.4
0.6
0.8
1.0
The relationship between the augmentation strength and CAPQL's performance. In Rmk 5, we discussed how the augmentation would affect the CAPQL's performance as its strength varies. In Fig 9, we plot the training curves of CAPQL for Hopper with different a, which corroborates our claim. particular, as a increases, the target value function g. (w) defined in Prop 5 becomes less sensitive to w. Thus, it can be learned more easily; meanwhile, we observe faster convergence and stabler training trajectories over various random initial seeds. However, a becomes too large (the case with 0.8), 9a (w) will significantly deviate from the original one (i.e., when a = 0). Then, the algorithm's 's performance after convergence starts to drop.
million steps
Figure 9: Training curves of CAPQL with different for Hopper.
DISCUSSION
This paper performed a rigorous analysis of the dynamics of the induced value functions resultant from policy alterations in MORL problems. We analyzed the behaviours of the functions when a single state's 's policy is altered and showed that this is insufficient to optimize the induced value functions in a MORL setting. We then discussed how to update a policy in multiple states to improve the value function of a specific state. We also showed that when -> 1, the induced values of all states will be improved as well. These insights into the induced value function's 's properties helped us show the convexity of their range and prove that LS is sufficient to find all SPE (DPE) policies. The equivalence of SPE and DPE was shown, which are also equivalent to APE when 7 + 1. Next, showed why existing based algorithms fail and proposed the CAPQL algorithm to address these issues; our empirical evaluation indicates CAPQL's superior performance and corroborates our theoretical analysis.

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY
Theoretical Work All theoretical results have formal proofs provided in the Appx B.
Empirical Work We provide a detailed pscudocode description of our CAPQL implementation (Alg in Appx F. The parameters used train and implement all algorithms we analyzed are listed in Tables 1-3 in Appx I. Additionally, we have provided details on the environment configuration and our derived reward functions in Table 4. The source code of our CAPQL implementation is available online: https//gthuu..com/oyyylllCCCCC
ACKNOWLEDGEMENT
We thank the reviewers and area chair for constructive comments. We gratefully acknowledge funding support from NSERC and the Canada CIFAR AI Chairs program. Resources used in preparing this research were provided, part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute.
REFERENCES
Fouad Ben Abdelaziz, Davide La Torre, and Houda Alaya. Dynamic programming and optimal control for vector-valued functions: A state-of-the-art review, RAIRO-Operations Research, 55: S351-S364, 2021. URL https: / wwg/ooggg/.....o 1tt...0000/////100000000
Abbas Abdolmaleki, Sandy H. Huang, Leonard Hasenclever, Michael Neunert, H. Francis Song, Martina Zambelli, Murilo F. Martins, Nicolas Heess, Raia Hadsell, and Martin Riedmiller. A distributional view multi-objective policy optimization. In Proceedings of the 37th International Conference on Machine Learning, 2020. URL http::/proceediile abdolmaleken www.aaawwolaaeeeeeeeeeeeeeeaaeae
www. www.ppressvville
pdf.
Axel Abels, Diederik M. Roijers, Tom Lenaerts, Ann Nowé, and Denis Steckelmacher. Dynamic weights in multi-objective deep reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, 2019. URL http://proceedinge mlr. www..press//eee / abelsl / abelsll 9a. pdf.
Mridul Agarwal, Vaneet Aggarwal, and Tian Lan. Multi-objective reinforcement learning with non-linear scalarization. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pp. 9-17, 2022.
Eitan Altman. Constrained Markov Decision Processes: Stochastic Modeling. Routledge, edition, 1999.
Leon Barrett and Srini Narayanan. Learning all optimal policies with multiple criteria. In Proceedings of the 25th international conference on Machine learning, pp. 41-47, 2008. URL http:// icm12008 es hehsinkii fi /ttppaprs///eeeeeeeeaeeeeaaeasse / 225. pdf.
R. E. Bellman. Dynamic Programminn. Dover Publications, 2003. URL hwtps::/tppseeeeee hywpd//yoaaoo.-ogaaaiinnng
Dimitri P. Bertsekas. Abstract Dynamic Programming. Athena Scientific. 3rd edition, 2022. URL
https: //bbbwb.... mi t. edu dimitrita ttttbr//// www Abst watprraatta_________e_e_
C.S. Chow and J.N. Tsitsiklis. An optimal one-way multigrid algorithm for discrete-time stochastic control. IEEE Transactions on Automatic Control, 36(8):898-914, 1991. URL https::/dceeec
1331184.
C. A. C. Coello. Handling preferences in evolutionary multiobjective optimization: a survey. In Proceedings of the 2000 Congress on Evolutionary Computation, volume 1, pp. 30-37, 2000. URL https: //ooi. www/10.........ooooooooo........ 1109/CECCCC. 2000 870272.
H. Corley. Some multiple objective dynamic programs. IEEE Transactions on Automatic Control, 30 (21):1221 1985. https: //oii org/10.g///0/ httg/10.119/////.. 1ww.111011A...... 1985. 1103871.
10

---

Published as a conference paper at ICLR 2023
Kenneth R Davidson and Allan P Donsig. Real analysis and applications: theory in practice. Springer Science & Business Media, 2009.
Achiya Dax. An elementary proof of Farkas' lemma. SIAM Review, 39(3):003-507, 1997. URL
http:/ //www www.jijtoooooo... org/ http//saabeeee130/0//
Bugene A. Feinberg and Adam Shwartz. Constrained Markov decision models with weighted
discounted rewards. Mathematics of Operations Research, 20(2):302-320, 1995. URL https:
atdoi.oor/// 1287 /tto/oooo.2/// 2.02..
Zoltán Gábor, Zsolt Kalmár, and Csaba Szepesvári. Multi-criteria reinforcement learning. In Proceedings of the International Conference Machine Learning. 1998. URL https://
sites. uww.ertaabbaaaa... www.aaaasssssaeeeee wwtp://aappps/aaeeeeeeee pesperssmmutaae ps..pf..
Matthieu Geist, Julien Pérolat, Mathieu Laurière, Romuald Elie, Sarah Perrin, Olivier Bachem, Rémi Munos, and Olivier Pietquin. Concave utility reinforcement learning: the mean-field game viewpoint. arXiv preprint vrXiv:2106.03795 2021.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In Jennifer Dy and Andreas Krause (eds.), International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1861-1870. PMLR, 10-15 Jul 2018. URL https://
proceedings mll.. www.ppresssvveee htress//B0/haaro///
haaaaaaaoooooaa jalab.llbb....b html.
Conor Hayes, Roxana Răduleseu, Eugenio Bargiacchi, Johan Källström, Matthew Macfarlane, Mathicu Reymond, Timothy Verstracten, Luisa M Zintgraf, Richard Dazeley, Fredrik Heintz, Enda Howley, Athirai Irissappane, Patrick Mannion, Ann Nowé, Gabriel Ramos, Marcello Restelli, Peter Vamplew, and Diederik M Roijers. A practical guide to multi-objective reinforcement learning and planning. Autonomous Agents and Multi-Agent Systems, 36(26):1-59, 2022. URL https: //t::///oo/// /oi. /10g 1007 s 0458- 0075558----22- 1222-9553 09552-92
Onésimo Hernández-Lerma and Rosario Romera. The scalarization approach to multiobjective Markov control problems: Why does it work? Applied Mathematics and Optimization, 50: 279-293, 2004. URL httttts///oo.oogg//gg 10. 1000/ -00-2244-000000000 0804
L. M. Kallenberg. Linear programming and finite Markovian control problems. Mathematisch Centrum, 1983.
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Frez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In International Conference Learning Representations, 2016.
Debabrata Mahapatra and Vaibhav Rajan. Multi-task learning with preferences: Gradient descent with controlled ascent in Pareto optimization. In International Conference on Machine Learning, pp. 6597-6607, 2020. URL http::ttp/peee htttt::/pprcceeiiggs mlr.. wwt.s/eeesssieeeeeeeeeeeese..sse mahapattaa20. html.
Shie Mannor and Nahum Shimkin. A geometric approach to multi-criterion reinforcement learning. Journal of Machine Learning Research, 5:325-360, 2004. URI, papers/ httpss/volmmmeee papers//olummmm/mmmma000... www.anooaa/maanorrrrraaaaaaaaaae
jmm org/
pdf.
Kaisa Miettinen. Nonlinear multiobjectiiee optiniiiaionniiiiniiiiiaiai Kluwer Academic Publishers, 1998. URL
https: : /ooi.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin Riedmiller. Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529-555 533, 2015. URL https:ttt// h/tpss::///////// /tt.oooooooooooooooooooooooooo.o org/ 01.0110.1 0.8///8/// na naturel 42366.
Kristof Van Moffaert and Ann Nowé. Multi-objective reinforcement learning using sets of Pareto dominating policies. Journal of Machine Learning Research, 15(107)336633366 2014, URL http:// jm1 r. .org/papers v //t/:///o///oo/aae//teee html.
11

---

Published as a conference paper at ICLR 2023
OpenAI, Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, Rafal Józefowicz, Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique Pondé de Oliveira Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, llya Sutskever, Jie Tang, Filip Wolski, and Susan Zhang. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv: 111.v..912.06688.0 2019. URL https: /awxivivvvv/./////////.a.//a/ava org /abs////////a /b1// 06680.
Simone Parisi, Mattco Pirotta, and Marcello Restelli. Multi-objective reinforcement learning through continuous Pareto manifold approximation. Journal of Artificial Intelligence Research, 57(1): 187-227 2016. URL httph:ttt////t //tii htt.ppp://ool.og/1...1111111 1ttp////...113//aaa..... 4961.
Mare Pickett and Andrew G. Barto. Policyblocks: An algorithm for creating useful macro-actions in reinforcement learning. In International Conference on Machine Learning, pp. 506-513, 2002. pdf.
URL hwtph:tp://// http::/// http:///aapppccecceeeeemmm www.:ppwwwpppppp.oeeeeeeee wwwpprssp.ccettttMMi.....
discrete Martin L. Puterman. Markov decision processes: decisiie discree d stochastic dynamic programming. John 000078847733888
Wiley & Sons, 1994. URL https::/ddoi.org/11...0000
Mathieu Reymond and Ann Nowe. Pareto-DQN: Approximating the Pareto front in complex multi- objective decision problems. Proceedings of the Adaptive and Learning Agents Workshop 2019 (ALA-19) at AAMAS, 2019, URL https:ttp....m ht//aall00000 www. ac.be/b.e/e............ wwc..beepappee http///pppss////0 paper_36.rm 3d
Diederik M. Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley. A survey of multi- objective sequential mecision-making. Journal of Artificial Intelligence Research, 48(1):67-113,, 2013. URL https:ttp//.m /oii org / ja air. a.i...99 3387..
Matthew J. Sobel. Ordinal dynamic programming, Management Science, 21(9):967-975, 1975. URL
http::/wwet
H. Francis Song, Abbas Abdolmaleki, Jost Tobias Springenberg, Aidan Clark, Hubert Soyer, Jack W. Rae, Seb Noury, Arun Ahuja, Siqi Liu, Dhruva Tirumala, Nicolas Heess, Dan Belov, Martin Ried- miller, and Matthew M. Botvinick. V-MPO: On-policy maximum a posteriori policy optimization for discrete and continuous control. International Conference on Learming Representations, 2020. URL wwtph:ttp/.cmmm...t.m wpwp//vieeeeeeeeeeeeeeeeee net 10
R.S. Sutton and A.G. Barto. Reinforcement Learning, second edition: An Introduction. Adaptive Computation and Machine Learning series. MIT Press, 2018. ISBN 9780262039246. URL http:// /t////ncommpp atteideas net http:/boookhheeeheooeeee 2nd. html.
Yunhao Tang and Shipra Agrawal. Discretizing continuous action space for on-policy optimiza- tion. AAAI Conference on Artificial Intelligence, 34(04),5981-5988, Apr. 2020. doi: 10. aaai. aaai.v34i04. v34i04.6059, https: aaai org/ index wtpppdpppppppppppppppppppppppppp TAA.///aaiillcooo 6059.
Peter Vamplew, John Yearwood, Richard Dazeley, and Adam Berry. On the limitations of scalarisation for multi-objective reinforcement learning of Pareto fronts. In Wayne Wobcke and Mengjic Zhang (eds.), A/ 2008: Advances in Artificial Intelligence, pp. 372-378, 2008 URL https:
//doi. org 10. 1007 - 5-000-00-50 5155540037777 ----8-83788388 37.
Peter Vamplew, Richard Dazeley, Ewan Barker, and Andrei Kelarev. Constructing stochastic mixture policies for episodic multiobjective reinforcement learning tasks. In Ann Nicholson and Xiaodong Li (eds.), Al 2009; Advances in Artificial Intelligence, pp. 349, 2009. URL https: /doi. org/ 1007 9988/9783333 3- 642-64222111
Kristof Van Moffaert, Madalina M. Drugan, and Ann Nowé. Scalarized multi-objective reinforcemet learning: Novel design techniques. In 2013 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL), pp. 191-199, 2013. doi: 10. 10.1099ADDPLL2213366...000
D. J. White. Markov Decision Processes. Wiley, 1993. URL https: http://wwwwwwww..oooo/o
en-us/Marhh Maw./////aooooeeee..oo si Pwwoontttsssssssoo 9at.a/ess-s--9997119179199999999 07804719362777
12

---

Published as a conference paper at ICLR 2023
Runzhe Yang, Xingyuan Sun, and Karthik Narasimhan. A generalized algorithm for multi-ojjective reinforcement learning and policy adaptation. In 33rd Conference on Neural Information Process- ing Systems, 2019. URL
neurips. cc/ pappr//019/Ei1e 6f 46 65a2 7622 2oloee220222ooooffoaaaaaa--aaaa
Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. Advances in Neural Information Processing Systems, 33:4572-4588 2020.
13

---

Published as a conference paper at ICLR 2023
A RELATED WORK
In recent years, there have been relatively few developments in the abstract analysis of the spaces involved in MORL problems. Much the previous work done on analyzing the set of induced value functions has been done on a general state-space while allowing various kinds of deterministic or mixed policies (Feinberg& & Shwartz, 1995; Vamplew et al., 2008; 2009; Roijers et al., 2013; Barrett & Narayanan, 2008; Moffaert & Nowé, 2014). In particular, Feinberg & Shwartz (1995) found that the expected discounted sum of rewards (*(s) (s) with a fixed initial state is a convex set when и is allowed to be non-stationary. Moreover, they prove that Pareto optimality (at any given state) is equivalent to a linear scalarization (LS) problem under specific weight vector. Similar convexity and Pareto results were found by Vamplew et al. (2008; 2009), but instead of allowing a general non-stationary policy, they restricted their policies to the set of mixed deterministic policies. The key difference between our work and theirs is that we restrict our analysis to stochastic stationary policies. Hernández- & Romera (2004) also performed an analysis in similar setting to us but focused on the feasibility of finding Pareto optimal solutions for specific weights.
Mannor& & Shimkin (2004) have also done similar work and required that there exists a common accessible state from every other state; ergodicity is a sufficient condition for their setting. How- ever, their expected sum of rewards un-discounted, which is not reflective of common modern formulations. They also focused significantly on directional policy optimization and proposed several algorithms that require mixed deterministic policies to function. Apart from the theoretical works, Abels et al. (2019) generalized the Q-function by conditioning it on the importance of the objectives. In their problem setting, the objective preference changes between different episodes and is not known in advance. Therefore, the learning task requires the algorithm to perform well over all potential weight selections. Yang et al. (2019) extended Abels et al.'s work. In particular, they developed a new Bellman optimality operator using envelope updates and proposed new algorithm for MORL called envelope Q-learning (QEnv). They showed that their algorithm consistently performs better over multiple MORL benchmarks and is more sample efficiency. Finally, Abdolmaleki et al. (2020) have developed an algorithm that allows users to choose objective preferences in a scale-invariant way by restricting the relative influence of each objective when improving the policy.
It should be noted that significant efforts have been made to find alternatives to LS due to perceived and real drawbacks. For example, Van Moffaert et al. (2013) demonstrate that Chebyshev metric can dominate LS in the discrete policy setting since it can be used to find Pareto efficient policies that are in the interior of the convex hull. While one of its primary benefits over LS no longer holds in the stochastic policy setting, it may be interesting to see if an extension of this methodology to our setting could still be beneficial. Alternatively, recent papers in the domain of concave utility reinforcement learning (CURL) have achieved some intriguing results (Geist et al., 2021: Zhang et al., 2020; Agarwal et al., 2022). In the recent work of Agarwal et al. (2022), they seek to find a single policy that maximizes concave utility function applied to V (s). While their setting, methods, focuses and insights are largely different from ours, they analyzed their framework's ' sample efficiency and developed an actor-critic method that reduces the variation the policy gradients by directly shifting them with state-dependent term.
B PROOFS
Given so E S and Tu E II, we temporarily restrict our attention to the policies equal to mo in all states except Sp; this is the set:
( TO) =- = E II: (()) = =s()s) for s 8 so
(11)
Proposition 9 Let (s) and X(s; denote the random variables that, starting from S the sum of the discounted rewards and the number of steps before the first time reaching su." (The distributions of V(s; so) and X(s; sp) do not depend on a(s) and thus are identical for all
E (1 mo).) Write
V(5e) = [ Vs': so) for s' E S) E dddss)
I(50) = [E
TBBxtss ((s))0) for s' E S] x (12)
'When So. V(so: so) x(00 = =0.
14

---

Published as a conference paper at ICLR 2023
For (S0, To), we have
v = V(8n) + (*0)) = V(so) + Q (50))
(13)
(7((8))
where (7(8)) = P (s0)) Q(sa) = (R(s)) + (V(s)) Moreover ((8))=(()) E [0, 1].
Proof:
Let s' be the next state starting from For E (s0.
(*())) = E R(a, su) - -V(s': su) + 7 x(d' (s0)
(14)
= (8(s)) + Σ [B[( so)] + [ ([ (m0) (T()))
Σ P(so, 8 s') 80),
(15)
where x (a, sn) is the probability of taking action a in state so when adopting policy æ and P(so, a, 8') is the transition probability of moving to state s' when taking in
That is,
V (0) R ((5o)=((5)) + + + yV (()))((())))))
(16)
where (7(s)) = ((s)))(ss))) and is easy to see (ss) E [0, 1]. Rearranging it yields
7(50) Q(so)
π TT(0)
(=(()) (R(s0) + (((())))()))) (177)(80)7(4))))
(17)
1-79 (sn)
Note that, for all E S, we have
(*(s) E ((s + x x(d1100) VF( =E (ss so) + [ V v=))))
(18)
Replacing (su) with the expression in (17) yields (13).
Corollary (Full version of Proposition 1 in the main text) For no, गI (s0, vo), let Ta
(1-a) + aT, with E [0, 1). Then
nT (1 3(0; V B(a; V*)
(19)
where
ax91
B(a; [1 - a0 + aœ
(20)
with 6; = 1 (35 y, 1] and 3 (a;; so) > 0. Besides,
v V (V=i - (su)
(21)
and
v
(a;50) -(V=I- - = 8 (o: so) ((so)
V
(22)
da
vV I(su),
(23)
da
where
π. (sp)
To (s0)
D(s)) = Q(s0)
(24)
1- (1 - )0
(Note: Eq (23) is identical to (5) in Prop 1.)
15

---

Published as a conference paper at ICLR 2023
Proof: Notice that
(1 su) + 3(a; Vm
= (1 - a)
V +
V
a0000 amh
00
aP1
(1- 00000
(3()
V(so) + Q(50)
a100 + a01
do
apd
Ti (80)
[(so)
[by (17)
(1 - auuu aΦι
$1
(1 a:) am + am [((0))
V(so) + Q(s))
=
(1 a) + ado
V(sg) + Qs)))
1 ((05) r(sp)
To
=
V
[by (17))
which is (19).
0, By Prop 9, (s)))))(())) [0,1) for i =0,1. Hence, 6; = - ($)))))) [1 7, 1] and du
('(a; [0oa 90- a1) [1-7, 1]. Besides, by (19). we have @V B' (o) (V V==))=)) da
Plugging and no into (13) followed by taking the difference yields V V (s5)) with (ss)) defined in (24). In this way, (22) proved.
Let so) be the entry for s in [(so). Namely, [(s; so) = [[xx(s=0))] Then
v V*1 (so) - V (so) ((so) so) = (Eso) = =(s0).
(25)
Hence,
V v ((ss) (VT) Vao (so)
(26)
which is (21). Likewise, (22) can be written as OV*= (su) da
(a(;s)) (ss)) so) = ('(a;; ((50) = ('; so) D(so).
(27)
Therefore, for 8 E S. OV (s) ('(a; D(so) T(s; OV (s;;80)
(28)
da
da
which is (23).
Proposition 10 (Proposition 2 in the main text) Assume To II is not optimal in the associated scalar problem for all w * 0. Let E S. We have the conic hull
(T)(s) - vT (50) TE U ((5,TO) = Rd
1 = cone
(29)
*ES
Q2 cone
V
U
((s, To)
=R.
(30)
SES
Therefore, for all u E RRd, can construct a function
(a.,...... ..01....,000 aMM) (1
Σ
04
To
0277
(31)
with a; 2 E, aj $ 1 and F. E such that
M @v*(0)
11
ry for some r, 2 0.
(32)
daz
==1
16

---

Published as a conference paper at ICLR 2023
(Note that (00) 7,.,,
0) ky. Besides, assuming the MDP is ergodic, if - 1,
M (
(s)
r. uu for all E S.
(33)
daj
/=1
Similarly, we can construct o (a1, aM) such that
M
(V
day rs for some 2 O.
(34)
Proof: Assume the cone (V* V (50) E USES $ss, mo)) # Rd. Then by Farkas'
lemma (Dax, 1997), must contained in some closed half-space H4 {x E R I x 0}. Now we show that ni V (so) cannot be further improved, which means π is optimal in the associated scalar RL problem with weight nı and thus contradiction. To improve n 1 (so), there must be
some s' E S that is reachable from so and n' E D(s', mo) such that n (V" (s') (s)( > By (21), this implics,
nf (V*((s) (8o) (so)) n (V* (8') V r(so; 5 > 0,
(35)
where 1'(so; s') 0 is the entry corresponding to so in l'(s') Hence, V (so) V (s) $ H1, which is a contradiction. Therefore, we have shown that Q = 12d
Similarly, if Q. * R Farkas' lemma shows it must be contained in some closed half-space H2 {x E Rdd n, x s 0}. Since To is assumed to be not optimal in all associated SORL problems with w * 0, it is not optimal for the SORL one with weight n2. Therefore, there exists some 8 S that is reachable when following the initial distribution and n' D(s', To) such that nz (V (s') (s)) O. Then (21) implies
n2 (V* (s) (s)) ny (V (8') - (s)) ((s;8') >0
(36)
for all s E S. As a result,
VT Viu
n Σ m(s) VTh (VT (8) - (s) 0.
(37)
sES
Hence, V WT & H2, which is contradiction. Therefore, Q2 = Rd.
Since 21 = IRd, there exist 8; E S, ग.
UsEs(56 mo) and di 2 0, for = 1,..., M, such that
M
d((" - (so)))
(38)
Define function ı taking the expression (31). By Corollary we have
(V=(()
0V(1- (o
la,=0 (a(ays8)) (V*s V av= (s)
T(s))-
(39)
0aj 0ag
Oa:
This implies,
@V* (8o)
(aa;ss) (V* (so))
(40)
da,
(V=(0 ((s0;8z).
(41)
day
Combining (38) and (40) yields
M d
@v=(0)
(42)
((a
Oa:
WWe note that the policy optimization performed in s' instead of so (as did in Cor 1).
17

---

Published as a conference paper at ICLR 2023
Setting ri ((ayssas) yields (32). Moreover, the MDP is ergodic, as y + 1, we have all entries of [(sy) approach to one for all j .,2....,M.. M. Then, combining (41) and (42) yield
df
M
dy
M
d'
(v (s)
M ())
u (aaiss)
da;
8(a;s)))
aa
ri
aa
(43)
for all 8 S. Likewise, since Q2 = Rd, there exist r 2 0 for i = I,..., M such that
u1
4 (V v
(44)
Notice that
OV
05, u(s))
Σ En(s) (v)
daz
da,
daj
Σ (()))((a;ss))) (V*((s) -V
[by (22))
B'(ay 8,) (V V)
Plugging it into (44) yields,
M
u
8()
aa.
(45)
Setting r; = [a.e) yields (34).
Proposition 11 (Proposition in the main text) For E S, V(s) is convex. Besides, V is convex.
Proof: We first consider the set of policies ii that are not optimal in the associated scalar problem for all w # 0. Then for mı, E Iī and E [0, 1], we show
(1 - 1-ajV= (8) + aV**(s) = V (s) for some n' E f.
(46)
Note that, since (s) and (s) not optimal in the associated SORL problem for all * 0. for any vector v on the line segment from (*i()) to V (s),,, v cannot be optimal in any associated problem either. (Otherwise, at least one of V (s) and (**(s) is optimal.) Therefore, starting from (s), we can keep constructing function म defined in Prop 10 with u = V (s) 5 (s) to move along the line segment." In this way, we can find a policy that has V*(ss) corresponding each point on the line segment, which implies (V*(s) (s) II] is convex. Therefore, V(s) (V*
I]] = cl(V(((sss (s) E ff)) is convex.
Similarly. for T1, E II, V and T are not optimal in the associated SORL problem for all w # Therefore, for any vector v that convex combination of V and V v not optimal in any associated SORL problem either. According to Prop 10, for every convex combination v, there is a policy ı that has V v. Hence, (V.Tm E II} is convex, which implies its closure V, is also convex.
Proposition 12 (Proposition in the main text) For & E S, π E II if there exists w > such that is optimal in the associated scalar problem. Also, if II π is optimal in an associated scalar problem with some nonzero w > 0. A similar statement holds for 1I; replaced with II.
A rigorous treatment is construct line (path) integral with the directional derivative nI.
18

---

Published as a conference paper at ICLR 2023
Proof: Consider the optimization problem
maximize w subject to ve V(s).
(47)
If is optimal for some associated scalar problem with weight w > then V*(s) the optimal solution of problem (47) (Bertsekas, 2022, Prop 2.1.2). Since V(s) is convex (Prop 1), according to (Miettinen, 1998, Thm 3. 3.1.2), V (s) is Pareto optimal V(s). That is, π IT!"
Conversely, if IT, then (*((s) is Pareto optimal in V(s). Since V(s) is convex, by (Miettinen, 1998, Thm 3.1,4), there exists w > and w o such that V*(s) is a solution problem (47). Then is optimal in the associated SORL problem with the nonzero w 2 0.
Repeating the derivations by replacing II; with II proves the similar statement for 11
Proposition 13 (Proposition 5 in the main text) Function 9s given in (9) is well-defined, surjective and uniformly continuous.
We prove Prop 13 by first proving the functional relationship from E W+ to Vay(s) E Va)(s)
and thus is well defined. In particular, we show
Lemma For any w E W+, there exists unique (s) E (a)(s) such that π is optimal in SWRL(W). (i.e., (a) is the only element in (s)(s) having the greatest projection w.)
Proof: We prove the lemma by contradiction. Assume that there exist two distinct Vaj (s) and V.. (8) in Vs)(s) such that mi and 22 are optimal in SORL(W). Then we have
{V (s), Var S argmax w V, vEVa,(s)
(48)
and
w 2 (5) (V)
(49)
In SORL problem, is well-known that policy ग is optimal for initial state if and only if is optimal for all states that are reachable from (Sutton & Barto, 2018). Since Vaj (s) # (s). we have Ti (s') * T2(5') for some s' that is reachable from under policies का and π2. Moreover, we have w 1 af (5') = w VTr We then consider a new policy n' that equals का for all S except s'. For s',, Ts'')) = (s)) + (2())). Due to the strongly concavity of the immediate augmented reward, the projected immediate reward T' on w strictly greater than the ones of Ti and πτ. As single-state action optimization is sufficient to increase the value function in all states (Sutton & Barto, 2018, p78), we also have w V w wTV VaJ (s) =w VTj which contradicts (48).
Since for each E W+ there exists unique corresponding (i)(s) E V (.) The relationship (+) by definition is function. We then show that
Lemma 9s W+ Viy(s) surjective.
Proof: Consider variant of the MORL problem that has the same setting as the original one except that we now treat the action-taki ttkiing distributions of state as actions. We keep referring the actions under the original definition actions and the ones under the new definition as the d-actions.
Then for each state-action pair s). the immediate reward is R(s) + af(ā). This setting is the same the one we considered in the proof of the convexity of the induced value function's 's range. Therefore, let V (s)(s) denote the range of the induced value function for the original MORL problem's variant; by Prop 3, we have V.r(s) 3) is convex. (In this variant of the MORL problem, the action space A is actually infinite. Thus, to apply Prop 3, we need to first approximate the action space through sufficiently fine discretization (Chow & Tsitsiklis, 1991).) Let V Vay(s) denotes the set
19

---

Published as a conference paper at ICLR 2023
of PE elements in Vag. Then applying the same method for the proof of Prop 12, we can show that for all v E V. (s)(s), there exists E W such that v has the maximum projection on w. Besides, applying the same method used in the proof of Lem I, we can show that for any w E W there exists unique v E (s) such that has the maximum projection on w. Therefore, there is functional relationship Is : W + Va that maps w to v. Moreover, Is is surjective. Finally, we show that Is = 9: by showing that v must be in Vāy(s)
Given E (s) that has the maximum projection over some w E W+. Then consider its associated SORL with weight Since the corresponding policy of taking d-actions are optimal, it must achieve the maximal cumulative discounted reward in all s' that are reachable from s. Then suppose in some s' the policy of taking actions is not deterministic (i.e., the agent follows some distribution p(a) to take d-actions). Then by replacing the distribution with the one only taking d-action a' Ja ūp(ä), the projected cumulative discounted reward starting at s' increases (due to the strongly convavity and the Jensen's inequality). Therefore, to find an optimal policy of the associated SORL, we only need to consider the deterministic d-action policy. Namely, it is sufficient to choose one distribution to take actions instead of adopting a bilevel design such that first follow a distribution to pick an action-taking distribution g followed by using q to take actions. Equivalently. we have shown that E V Vay(s) which completes the proof.
Finally, we show that gs uniformly continuous.
Lemma 9, is uniformly continuous.
Proof: We first show that w is continuous over W+, By Lem I, we know gw(w) can be written as
Is (w) = argmax w TTv v. vEV.,($)
(50)
For a sequence Wi w", let VA (w&s) and v² Is (w"). Then for any subsequence
C N, VA has an accumulation point v' (because Va (S) is closed and bounded and due to the Bolzano-Weierstrass theorem (Davidson & Donsig, 2009)). Since w Vk 2 w v for all v E (a)(s), k E I. We also have w* v' > w for all v E (s) Therefore, v' = =v= and g, is continuous by definition (Davidson & Donsig, 2009).
Finally, since W+ is compact, gs is uniformly continuous (Davidson & Donsig, 2009).
Combining Lemma 1-3 completes the proof of Prop 13.
Corollary 2 (Proposition 6 in the main text) If т E II, for some state E S, then for all s' E S, II. Thus, the sets of SPE policies coincide for all initial states and a subset II".
Proof: According to Prop 12, if π E II, for some s' E S, then V*((')
('''in is optimal in an associated SORL with some none-zero w > 0. Thus, (T(s) is the optimal solution of problem (47) for all s E S (by (Bertsekas, 2022, Prop 2.1.2) and the ergodic assumption).
If w 0, then by Prop 12, V (T(s) E V(s) for all s E S. That is, π E II; for all s.
If w contains zero entries, as π (s') ) E II;,, V*((") is Pareto optimal in V(s'). Intuitively, V (55') can be seen as a maximizer of problem (47) with weight w' = lim,-to w + cl. Then since w + cl > 0 as it approaches to w, the problem is reduced to the first case, and thus, π E II; for all 8.
more rigorous proof can be done by introducing a lexicographic order over Rdd Specifically, we need to construct lexicographic order such that V*((') is the global maximum V(s') C. Rd Let We w, Sg = / (s') and ma = maxves, wiJ v. Define S = {v E So w. v mn). Since Sg is convex, so is 5 as it is an intersection of So and a hyperplane. It is easy to check V (s') E S₁ and is
Pareto optimal in S,. Applying (Miettinen, 1998, Thm 3.1.4), there exists nonzero wi > 0 such that
Wi Wo = 0 and (ss') is a solution of
maximize w.T. subject to E Sj.
(51)
20

---

Published as a conference paper at ICLR 2023
We can continue this process to get mą maxves, W v. Sk+1 fvv S v m followed by applying (Miettinen, 1998, Thm 3.1.4) to get Wk+1, where W w = for all j < k + 1. Besides, Wk+11 has at least one nonzero entry, which is zero for the counterpart in w for all j k+
The process will continue until we get list of non-zero weights wo. Wi...., Wn Ł 0 such that for any dimension = 1, ...... d, there is exactly one w, having positive entry dimension i. Then we can construct a lexicographic order St. over Rdd by ordering tuple (w] v, w v,..., W,, where <1, u if w
w for l < and w
w
Since VT(s') (s") is Pareto optimal in all Sk. is the global maximum of V(s') under 3r, Since for any dimension in R there is exactly one w.. = 0. 1...., having a positive entry. For u, v E R if # u, either u > V or u < V. Thus, V(s') in fact the unique global maximum of (s'').
Gabor et al. (Gábor al., 1998) extends the SORL setting MORL by ordering IR using lexicographic order. They generalized the Bellman optimality operator by choosing the action that gives the greatest (vectored) value function under the lexicographic order. They showed that under this setting, the value function converges to the unique optimal point (under the lexicographic order) and the generalized Bellman optimality operator monotonie. Thus, the value function reaches the optimality for all states simultaneously under the ergodic assumption.
As a result, since (s*'') is optimal in V(s",, V*(s) is also optimal in V(s) for all E S (under order ).) Thus, V is Pareto optimal in V(s). (Otherwise, if there is some V(s) such that > (s), we can show that u >r. V*(8) as well.)
Proposition 14 (Proposition 7 in the main text) For all s S, 11; II
Proof: If E Hy' for some s' E S, then by Prop 12, x is optimal in an associated SORL problem with some nonzero w > O. Therefore, w T (*()) reaches the maximum for all s E S; thus, so is W V E.Es M. w (s)...
If w > 0, by Prop 12, VI is Pareto optimal in V Otherwise, contains entries. Intuitively, approximate with w' lim w + c1 like what do in the proof of Cor 2. More rigorously, we can use the same trick to construct a lexicographic order 3z over Rd, where V*('') is the only global maximum of V(8'.. Then, by Gabor et al. (Gábor et al., 1998)'s work, V (s) is the only global maximum of (ss) for all s, which implies VT is the only global maximum in Va under order 3t. Therefore, VIT is Pareto optimal Vy.
Reversely, given II; we have VI is Pareto optimal in u- Then Prop 12 shows is optimal in an associated SORL problem with a nonzero w > 0. If w > 0, then by Prop 12, π e II; for all E S. Otherwise, we construct lexicographic order zn through the method used in Cor 2's proof. Then we can show that V/5 is the the global maximum in Vμ. and (s)) is the global maximum in (s) for all s (under order 1.). Thus, (s) is Pareto optimal in V(s) and x E [I) for all s.
Proposition 15 (Proposition 8 in the main text) For any s E S, as ? + 1, the SPE set II; ap- proaches to the APE one II..
Proof: It is sufficient to show y - 1, every policy II must be in II; In particular, assume
there is и E II* but π & II; Then there exists v V(s) such that v a v*(s) and v > V*((). By Prop 11, Vss) is convex. Thus, the line segment with the ends v and V=((s) is contained in V(s). By Prop 10, we can optimize the policy to move from (s) to v over the line segment; at the same
time, 7 + 1, (s') will move in the same direction for all s' E S (see (33)). Hence, the value
function are improved in all states, which implies x cannot be APE.
21

---

Published as a conference paper at ICLR 2023
C THE RELATIONSHIP BETWEEN THE CONVEXITY OF THE OCCUPATION MEASURE AND THE INDUCED FUNCTION'S S RANGE
The convexity of the induced function's ' range can also be seen as a corollary of the occupation measure's s convexity, which was initially proved by Kallenberg (1983). In this section, we give second proof of Prop 3 based on the occupation measure's convexity.
For any initial distribution μ.. the occupation measure of a policy x is defined (Altman, 1999, p27)
z TT. p3 = (1 (1
7' S(T,
(52)
10
where P(a,, St3 (4) denotes the probability of taking action a in state 8; at step f when adopting policy π with initial distribution μs. It is easy see that we can write
V = 1-
1
ΣE
ITT, 8) R(a,s) 8).
(53)
EES DEA
Let (( xgIAx(S) such that [X(T,, M)]as z(π, μu; a. s). Additionally, let X(μ) {X p E III. Then Kallenberg (1983) proved that (Altman, 1999, Thm 3.2)
Lemma 4 (Convexity of occupation measure) X(u) is convex.
In other words, for X1, X2 E X(n), we also have iX1 + (1 8)X2 E X(1) for all 5 E [0, 1].
Then, we use this result to prove the convexity of the induced function's range.
Proof: [The second proof of Prop 3] Given V V E Vus by (53), we have
V
Σ
x a( u (,,)s) R(a,s),
(54)
sES aEA
TTa
x(22, R(a,s).
(55)
SES
Then for any E [0, 1]. we have
(1 11-8) TV 1
1
Σ
(1- 2(T1, + ((02, R(a,s). (56)
SES aE
Due to the convexity of X(1), we know that there exists some X such that
x(T', pi s) (1 8) x(M,, + 12
(57)
for all 8 E S and a A. That is,
- 8) + 8V
ΣΣ I(T', R(a, s) V E V.e.
(58)
sES
as well. Therefore, Vp is convex. Let be the one-hot distribution that puts all mass on state s. We have V(s) Vn,, which is also convex.
D WHY A DISCONTINUOUS 9s MAKES THE TRAINING PROCESS UNSTABLE
Training using LS is unstable because of the sensitivity of g, to preference vectors w that are near normal to a surface edge of V(s): slight changes in means the optimal policy will be on different vertex of the polytope. This behaviour will be exacerbated by estimating V(s) since slight changes in the value functions will also change the surface geometry. More specifically, g, (w) is discontinuous when we do not add our concave regularization term (a = 0). so is highly sensitive errors in estimate of V o (s).
22

---

Published as a conference paper at ICLR 2023
E THE SELECTION OF THE STRONGLY CONCAVE TERMS IN CAPQL
In this section, we discuss our selection of the strongly concave term used in CAPQL.
According to the theoretical results presented Sec 4.1, f can be any strongly concave term for the definition of V given in (8), and Prop 5 shows that the corresponding 9, defined in (9) is surjective and uniformly continuous. In this way, all the problems of the existing I-S-baed methods discussed in Sec 4.1 are solved.
10
α 0.2
0.5
a ==1
5
0
10
10
10
10
Figure 10: The effects on the induced value functions at so for selected policies in Ex 1 by adding strongly concave terms to the immediate rewards with different alpha. Here, f A |AI + R is defined as fp) = - - A p. V (so) is marked in blue and the dots of the same colour among the four plots correspond to the same policy.
In Fig 10, we visualize the changes of V (so) by choosing a different f(p) = - Σ p. We can observe that the transformation of V (sy(s)) here is very similar to the one presented in Fig 7 where f(p) = H(()).
While the theoretical results presented in Sec 4.1 holds as long as f is strongly concave, some special choice of f can significantly simplify the implementation of CAPQL and improve the computational efficiency. Specifically, CAPQL consists of two major parts: 1) optimizing the generalized Q- nework using the Bellman operation and 2) optimizing the policy networks To conditioned w by minimizing the KL divergence from the predicted action-taking distribution TT(S,, w) and the target one induced by the Q-values:
argmax (())
Cols, a. T(a, s)) (T((s)
(59)
aEA
where π (a, 8) denotes the probability taking action a in state s.²
Regarding the first part, the optimization of Q(s,, a,, w) needs the estimated value function condi- tioned on w at the next state S1+1. That is,
((5+11 w) = Eawno Q0(se+1, a, w) + as (T (f w)).
(60)
which requires f f w)) can be computed efficiently. If the number actions is huge or infinite, we need to estimate V(s++1, w) through sampling. Note that, when f = H. we have
V ((441, w) (B
Q0 Q0 a, w) Eawzolansiw))
log (T(0141, w)).
(61)
=Bawsylse mw)
Q0 w) log T (9441,W)
(62)
Qu( w) log (5(4141, w)
(63)
with a ~ T (S w). (We adopt this approximation in our CAPQL implementation as the MoJuCo environment has continuous action space.) However, similar estimation cannot be made given (()) 4 p² because the expression not an expectation over the action-taking distribution.
For the second part, practical implementation requires that the (s) defined in (59) can be evaluated efficiently. When f H. the x has the expression:
(a. 8) exp (w T Qo a, w)/a)
(64)
Z
See Appx for the implementation details of n. and Qo-
23

---

Published as a conference paper at ICLR 2023
where Z = -=fas aas exp (w Qo(s.a, a, w)/a)da. In Appx F. will show that Z is not required to be evaluated explicitly. As a result, x² can computed effortlessly.
H enables the efficient computation//ssimation in training the Q network and the policy network, we use the entropy function to augment the immediate rewards in our CAPQL implementation.
Since setting =
F IMPLEMENTATION DETAILS OF CAPQL
In this section, we provide extra implementation details of the CAPQL algorithm and gives its psuedocode.
Our algorithm largely follows the spirit of the implementation of the soft actor critic (SAC) (Haarnoja al., 2018). The major difference is that in CAPQL, the Q-network and the policy network conditioned on the preference weight w. As a result, the Q-network takes input (s, a, w) instead of (s, a). and the policy network has input (s, w) instead of s.
Let Qo denote the Q-network with parameter 0 for training. Qj target network with parameter 0 and Ty the policy network with parameter vh. Additionally, let Dæ be a weight sampling distribution with support Φb. As mentioned in the main text, without the loss of generality, we assume that for all w E Φ we have ||w]] = 1; in practice, the assumption can be simply satisfied by normalize w after sampling it. Then we give the CAPQL's implementation in Alg 1.
The CAPQL implementation Input: weight sampling distribution Do Initialize parameter vectors I1. oz 01. 0g. v 0, < 0; for i E {1, 2} for each iteration do
Algorithm 1:
for each environment step do D
sample (St. w)
8t+1 P(ay, 8t) D {(st, de. R(ai, st), 81+1, w)}
end
for each training step do x- sample N transitions from D
+ 02 Aa Vo, EsE (s),, (L aj: w) Qu: aj w)l for {1,2]
where ( Aj. w) = R(aj. 8,)+
min.e(112) Qú,
w) - a log ToogTlaan (1 95+1, w)
and a++1 To (s/+1, w)
1 + 3e X, V Es DKL (Tp w) exp(w" mingg(1.2) Qu, (n,())::
2(s,.w)
with Z(sj. w) Sa exp (w min Qo, (sj,a, w)/a) da
exp
70, 7) for i (1,2)
end
end
Note that when computing the gradient of q/, the partition function Z(sj, w) does not depend on ei and will be dropped in the actual implementation. Besides, we use an exponentially moving average with smoothing constant to update the target network, which stabilizes the learning trajectory. This technique has been commonly adopted in the prior work (Mnih al., 2015; Lillicrap al., 2016; Haarnoja et al., 2018).
Implementation of the Q-network. Inspired by the design of SAC, our Q-network consists of two fully connected networks (FCNs). The two networks have the same architecture but different parameters. Each of them has two hidden layers and takes input of the dimension equal to the sum
24

---

Published as a conference paper at ICLR 2023
of the ones of observation states and reward. The output dimension equals the reward's. When performing inference, the Q-network returns element-wise minimum over the two FCNs' outputs.
Implementation of the policy network. The policy network is implemented using the reparame- terization trick. In particular, it can be written
= f0(G w):
(65)
where 6z is sample of a spherical Gaussian distribution. In our implementation, we first use the trick generate Gaussian sample with mean jug (8t, w) and standard deviation ( w) (Me and o are respectively implemented by two-layer FCN), followed by using tanh function to ensure a, is 1]d as required by the Mujoco environment.
G THE CONVERGENCE PROPERTIES OF CAPQL
In this section, we discuss the convergence property of the CAPQL algorithm. As mentioned in Sec 5.2, the learning task of SORL(W (w) specified in (10) the one used SAC (Haarnoja al., 2018); therefore, after picking w, use the SAC method train the policy and the Q-network.
Let W [w'[w' ww E + and ||w'l 111 = 1). It has been shown that by repeatedly applying the SAC optimization step, the policy converges to the optimal (Haarnoja et al., 2018, Thm 1). As a result, for CAPQL, given fixed weight w W. we have the conditioned policy π ((; w) converge to the optimal policy ww such that w T (s, w TQ" (8, a) for all TI and (s, a) E S x A.
As the CAPQL algorithm converges conditioned on every w E W, it also converges as whole.
H ADDITIONAL EMPIRICAL STUDY OF CAPQL
MOQ (a= 0)
0.1
a 0.3
0.5
10
1.0
Wo or (1- W1)
0.5
5
0.0
5 10
5
10
10
5
10
Figure 11: Visualization of the estimated gea (w) Ex by MOQ (Abels al., 2019) and CAPQL with a = 0.1, 0.3, 0.5. The MOQ can be seen as a special case of CAPQL when + 0.
In this section, we provide extra empirical evidence to corroborate our theoretical results discussed in Prop 5 and Rmk 4 and show that CAPQL is capable of finding all the PE policies
We perform the experiments on the environment specified in Ex 1 which has simple configuration so that we can plot the range its induced value function.
In Fig 11. we visualize the estimated 9eo (w) of the CAPQL with 0.1, 0.3. 0.5. We also provide one for MOQ (Abels et al., 2019) which can be seen as a limiting case of CAPQL when a + 0. The visualization was made by picking w { {[oo wa]" E IR2 wg + w/ 1, wh E [0, 1]}.
Fig 11 (left plot) shows that the MOQ algorithm cannot precisely estimate 9.p as it is not continuous when a 0. In particular, the target 9s, has the range only consisting of the upper two vertices and the the right (also Fig 6). However, the estimated Is, randomly fluctuates the vertices and mistakenly has continuous transition between the upper two. The fluctuations suggest that the estimated 9*u is numerically unstable and could harm the performance of the induced policy. Additionally, the continuous transition indicates that the target 9s, is inaccurately estimated.
The right three plots show that the aforementioned problems can be alleviated by the CALQL algorithm. We observe that even relatively small alpha (a 0.1) can largely alleviate the numerical
25

---

Published as a conference paper at ICLR 2023
stability problem the most of fluctuations near the vertices disappeared and the estimation of geo improves. We also observe that as a increases to 0.5, a nearly perfect estimation of 9so is obtained. The observations tell us by adding the entropy term to the immediate reward can indeed make it casier to learn Iso and improves the numerical stability, which supports our claims in Prop 5 and Rmk 4.
Moreover, we can observe that the learned Isa is surjective function from W+ to the entire Pareto front, which implies that the corresponding policies learned by CAPQL are the induced value functions which cover the entire Pareto front of V (Su) as well.
I HYPERPARAMETERS
Tables 1-3 list the hypermeters of the models considered in Sec 5.3. Table lists the specifications of the four Mujoco environments.
Table I: Hyperparameters of CAPQL and QEnv-ctn
Parameter
Value
Optimizer
Adam
learning rate
3 x 10
discount factor (x)
0.99
hidden dim (for all networks)
256
replay buffer size
10"
minibatch size
256
nonlinearity
ReLU
target smoothing coefficient (r)
0.005
Table Augmentation strength of CAPQL
Environment
Hopper
0.2
Walker2D
0.05
HalfCheetah
0.1
Humanoid
0.005
Package Versioning Python 3.10.4 was used as the primary programming language. We accessed MuJoCo210 through gym-0.21.0's wrapper classes. Training was done using pytorch- 1.112 and NVIDIA's CUDA 11.6.
26

---

Published as a conference paper at ICLR 2023
Table 3: Hyperparameters of QEnv and MOQ
Parameter
Value
Additional Info
SGD was only used on Humanoid because Adam was requiring too much RAM for the system
Optimizer
Adam SGD
learning rate
1 10
discount factor (7)
0.99
hidden dim
A linear function of dim(() + d
The NN architecture used in the original QEnv work.
(for all networks)
replay buffer size
4000
Effective batch size after taking the Cartesian product with the preference vectors
minibatch size
16 x 16
nonlinearity
ReLU
The Humanoid's action-space has dimension of 17, making it infeasible to use a more fine-grained discretization of its action space.
# discretized values for each action dim.
5 (2 for humanoid)
Table Specifications of Environments
Environment
Action dim.
Obs. state dim.
Rwd. dim.
Rwd entries
forward reward
Hopper
3
11
negative ctrl cost
healthy reward
forward reward
Walker2D
6
17
3
negative etrl cost
healthy reward
forward reward
HalfCheetah
6
17
2
negative etrl cost
forward reward
negative etrl cost
Humanoid
17
376
healthy reward
negative contact cost
27


Reviews:
[{"review_id": "pOTyUAqZWP", "reviewer": "Reviewer_ahKt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies some theoretical questions about multi-objective reinforcement learning. The focus is on policy-induced value functions. Section 3 develops several tools to characterize changes to value functions when one changes policies. Section 4 uses those tools to show the value function space is convex and provides insights into why linear scalarization methods fail to find Pareto-efficient policies. The authors present a concave-augmented Pareto Q-learning algorithm (CAPQL) and demonstrate its effectiveness on several multi-objective variants of the MuJoCo environments.", "summary_of_the_review": "This a well-written paper with a good theoretical contribution. The empirical evaluation section could be strengthened to make the whole package stronger.", "strength_and_weaknesses": "Strength: overall the theoretical contribution is quite interesting and insightful. As the authors pointed out, recent multi-objective RL research has not presented a coherent view on this topic. This paper is a timely investigation of some fundamental properties in this space.\n\nWeakness: \nThe empirical evaluation section, in comparison, is weak. As the new algorithm proposes adding a strongly concave term to the reward function, it would be better to explain the choice of selecting the entropy operator in the implementation. Can one use any other operator in its place?\n\nWhile the results on the 4 presented environments look promising, I noticed the sample size is relatively small (10k steps). Are there longer runs so we can see result comparison at convergence?\n\nThe authors should also discuss a relevant paper on introducing an improved scalarization method beyond linear scalarization. \n\nKristof Van Moffaert; Madalina M. Drugan; Ann Nowé: Scalarized multi-objective reinforcement learning: Novel design techniques\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Y55zRZN8l1p", "reviewer": "Reviewer_gKVf", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper conducts a rigorous analysis on the fundamental properties of the policy induced value functions in multi-objective reinforcement learning (MORL). Based on the analysis, the authors further distinguish and consolidate three existing definitions of Pareto optimal policies and identify issues of training policies via linear scalarization (LS). The authors fix this issue by adding strongly concave terms to the immediate rewards and verify the effectiveness of the approach via experiments on simulated control tasks. ", "summary_of_the_review": "Due to the strong theoretical contributions, I recommend acceptance. ", "strength_and_weaknesses": "I am not an expert in MORL. But after reading this paper, I envision that the contributions of this paper will have a large impact on the MORL community. They can accelerate the research in this field. Furthermore, as many practical RL problems can be better formulated using multiple objectives, the contributions are very important to the RL community in general. \n\nThe authors offer several novel theoretical results, including\n\n- The induced value function’s range for stationary policies is concave. This has been thought hard to characterize and of irregular shapes. \n- There are at least three existing definitions of Pareto optimal policies. The authors rigorously distinguish and consolidate them. \n\nI really like the new theoretical results. However, I have some questions regarding the Problems of the existing LS-based algorithms paragraph and the proposed algorithm. \n\n- The solutions to linear programs are almost always on the vertices. If this does not make solving them less numerically stable, why would LS-based algorithms be less numerically stable? \n- The motivation of identifying all SPE policies is not very clear to me. When is this required in practice? \n- Maybe derived from a different perspective, based on Eq (9), the proposed algorithm CAPQL is almost the same as entropy-regulated RL algorithms. Is this correct? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JfFRy2HhrwG", "reviewer": "Reviewer_Z4Pt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the fundamental properties of the learning spaces in multi-objective reinforcement learning (MORL). The authors give a theoretical analysis of policy induced value functions and discuss three metrics of Pareto optimality. Their results imply the convexity of the induced value function, and show that training a policy based on linear scalarization (LS) can achieve any point of the Pareto front. The authors propose a new vector reward-based Q-learning algorithm, called CAPQL, which adds a strongly concave term to the immediate reward and solves the problems of existing LS-based algorithms.", "summary_of_the_review": "I think that the theoretical analysis for the problems of existing LS-based algorithms and the relationship among three types of Pareto optimality for multi-objective reinforcement learning (MORL) is novel and interesting. But the proposed algorithm CAPQL lacks a sufficient discussion on the used concave term and a more in-depth theoretical analysis, e.g., a convergence or sample complexity guarantee. The experiments can be further enhanced by adding a comparison to existing LS-based algorithms and a discussion on how the empirical phenomena support the theoretical fundings in Section 4. Overall, I give borderline acceptance.", "strength_and_weaknesses": "Strengths:\n1.\tThis paper is very well-written and easy to follow. The authors use an example (Example 1) throughout the paper to illustrate their insights, which facilitate well readers’ understanding.\n2.\tThe investigation on the relationship between three types of Pareto optimality is novel and interesting, which is supported by theoretical analysis.\n\nWeaknesses:\n1.\tAccording to the results in Section 4, i.e., adding a strongly concave term can fix the problems of existing LS-based algorithms, it seems that the proposed algorithm CAPQL can add an arbitrary strongly concave term to the immediate reward. Why does CAPQL use the entropy operator $\\mathcal{H}(q)$? Can this entropy operator be changed to other strongly concave terms? It would be better if the authors can include more discussion on the strongly concave terms used for CAPQL.\n2.\tThe theoretical analysis for algorithm CAPQL is not sufficient. In the current version of this paper, the theoretical guarantee for CAPQL fully replies on the analysis for the limitations of existing LS-based algorithms and three types of Pareto optimality. It would be better if the authors can provide a more thorough theoretical analysis for CAPQL, e.g., a convergence or sample complexity guarantee.\n3.\tCan the authors provide the experimental results for the comparison to existing LS-based algorithms? The results in Section 4 will be more convincing if the authors can show some experimental phenomena that support the theoretical results.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6KZsneTt44", "reviewer": "Reviewer_HSHv", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper discusses the impact of multiple objectives. Pareto optimality guarantees are discussed, and actor-critic formulation is provided. ", "summary_of_the_review": "The paper provides some results on Pareto optimality of MORL with concave regularization of the policy. Sample complexity results would have been nice for the paper. ", "strength_and_weaknesses": "The paper analyses the dynamics of the induced value functions resultant from policy alterations in MORL problems. The analysis seems good. \n\nThe proposed algorithm mainly adds a concave function of the policy, which can help with determinism and numerical instability. The algorithms could have some sample complexity type results which will be helpful, with comparisons to the existing works. This is especially since many algorithms like policy gradient, actor critic, etc. have sample complexity guarantees. Even though this paper is different from CURL frameworks, it is not clear why we cannot use the model like there to model the multi-objective problem - and what benefits this formulation gives or what problems this could solve which the other cannot.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster