Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learning
Authors: Ruida Zhou
Tao Liu
Dileep Kalathil
Panganamala Kumar
Chao Tian
Venue: NeurIPS 2022 Accept (2022)
Keywords: Multi-Objective Markov Decision Process
Constrained Markov Decision Process
Policy Optimization

Abstract: We study policy optimization for Markov decision processes (MDPs) with multiple reward value functions, which are to be jointly optimized according to given criteria such as proportional fairness (smooth concave scalarization), hard constraints (constrained MDP), and max-min trade-off. We propose an Anchor-changing Regularized Natural Policy Gradient (ARNPG) framework, which can systematically incorporate ideas from well-performing first-order methods into the design of policy optimization algorithms for multi-objective MDP problems. Theoretically, the designed algorithms based on the ARNPG framework achieve $\tilde{O}(1/T)$ global convergence with exact gradients. Empirically, the ARNPG-guided algorithms also demonstrate superior performance compared to some existing policy gradient-based approaches in both exact gradients and sample-based scenarios. 

Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learning
Ruida Zhou" Texas A&M University ruida@tamu. edu
Tao Liu" Texas A&M University
Dileep Kalathil Texas A&M University dileep www.kaaalllaaa...oooommmm edu
tliu@tamu.edu
P. R. Kumar Texas A&M University
Chao Tian
Texas A&M University chao. t tian@tamu. edu
prkStamu, edu
edu
Abstract
We study policy optimization for Markov decision processes (MDPs) with multiple reward value functions, which are be jointly optimized according to given crite- ria such as proportional fairness (smooth concave scalarization), hard constraints (constrained MDP), and max-min trade-off. We propose Anchor-changing Regularized Natural Policy Gradient (ARNPG) framework, which can systemati- cally incorporate ideas from well-performing first-order methods into the design of policy optimization algorithms for multi-objective MDP problems. Theoretically, the designed algorithms based on the ARNPG framework achieve Ö(1/T) global convergence with exact gradients. Empirically, the ARNPG-guided algorithms also demonstrate superior performance compared to some existing policy gradient-bass approaches both exact gradients and sample-base cample-based scenarios.
Introduction
In many sequential decision- scenarios, agents usually face multiple objectives simultaneously. This motivates the study of reinforcement learning (RL) with multiple reward values VT (p). Given the achievable region V = {Vis (p) consisting of value vectors achieved by policies in policy class II, the agent employs certain criteria to reflect the system requirement. For example,
1. Proportional faimess 13 Given aiam > 0, find E V that DITh d/ < 0, Ve' E..
2. Hard constraints 4 Given b2:m. maximize 01, subject to 02 2 bi Vi 2,..., m.
3. Max-min trade-off M Given Cl.m. 0, maximize,gy min:e[m] (vs/c)).
We study policy gradient-based approaches that optimize over parameterized policies II {To
E () through policy gradient. In general, the optimization problems above may not convex in terms of f not even for single-objective MDPs with direct parameterization by 0,,- TT(als) ss) [2]. Due to the non-convexity, O(1/T) global convergence of policy gradient- -baed methods was only established very recently for single-objective MDPs with exact gradients 2 (20). These breakthrough results have motivated the study of policy optimization for multi-objective MDPs, e.g., smooth concave scalarization 1 constrained MDPs (CMDPs) 3T.
However, under the exact gradients scenario, the previous approaches for multi-objective MDPs. either suffer from slow provable O11//T) global convergence [I]. or require extra assumptions
"The first two authors contributed equally.
2The notations are formally defined in Section
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The compactness of è is assumed in [37,, but this assumption forbids a very common parameterization, where é = I R| The NPG-based methods have been analyzed in under an ergodicity assumption, but such an assumption is not required for NPG in single- objective MDPs
+v
33 18
softmax
3
|
[2] and therefore appears artificial.
The above criteria for multi-objective MDPs could be viewed as convex optimization problems w.r.t. a value vector u E V. for which there are a wide array of well- pell-perfonnnn first-order methods for convex optimization problems in general. It is desirable to take full advantage of such efficient first-order methods in a unified and flexible manner when designing policy gradient-based algorithms for multi-objective MDPs
Main contributions
1. We propose an anchor- anchor-changing regularized natural policy gradient (ARNPG) framework in Section that can exploit and integrate first-order methods for the design of policy gradient-based algorithms for multi-objectivy MDPs.
2. We demonstrate the strength of the ARNPG framework by designing algorithms for three general criteria: smooth concave scalarization (Section constrained MDPs (Section and max-mii trade-off (Section 4.3).
3. Under softmax parameterization with exact gradients, the proposed algorithms inherit the advantages of the integrated first-order methods, and are guaranteed to have Õ(1/T) global convergence without further assumptions on the underlying MDP.
4. In addition to the theoretical advantages, we provide the results of extensive experimentation in Section 5 and Appendices A and which demonstrate that the ARNPG-guided algorithms provide superior performance in exact gradient and sample-based tabular scenarios, as well as actor-critic deep RL scenarios, compared to several existing policy gradient-based approaches.
1.1 Related works
10 14] due their simplicity as well as the potential to generalize to large scale problems. Despite their non-convex nature, PG-based methods have been shown to converge globally for single-objective MDPs [ 20)
Policy gradient (PG)-based methods have drawn much attention recently [1
Their convergence may be further accelerated with appropriate regularization [IO M7. e.g., entropy
regularization, but the algorithms only converge to the optimum of the regularized problem instead of the desired (unregularized) problem.
This paper considers single-policy multi-objective MDPs, including CMDPs where constraints are specified on some objectives. Global convergence of PG-based approaches in the multi-objective MDPs has been previously studied. For smooth concave scalarization, Bai et al. [5] showed an O(1/Et) sample complexity (to achieve e-optimal in expectation) of the policy-gradient method under sample-based scenarios. However, with exact gradients, we are unaware of works with fast Ö(1/T) convergence. For CMDPs, Ding et al. achieving O(L/VT) global convergence for both the optimality gap and the constraint violation. Xu et al. 31 have proposed a primal approach that reduces constraint violations with a higher priority than optimizing objective, and enjoys the same (LIV/T) global convergence. In work conducted concurrently with ours, [35] and [8] have proposed algorithms that achieve Ö(1/T) convergence but with extra ergodicity assumptions.
have studied a primal-dual NPG algorithm
general setting of optimizing a concave function of the state-action visitation distribution has been considered in [37. Though the problem is more general, its gradient estimation is more complicated than the canonical policy gradient estimate. Zhang et al. achieves O(1/T) global convergence for smooth scalarization with exact gradients, under several assumptions such as convexity and compactness of the parameter set θ. Directly viewing the state- action visitation as the decision variables and imposing equality constraints for their feasibility, smooth concave scalarization has been studied in (36] and later generalized to the constrained setting in 6 These two works focus on sample-based scenarios, but due to their primal-dual approach with equality constraints, the convergence rate only O(1/ /VT even with exact gradients. Moreover, the state-action visitation parameterization is difficult to generalize to larger scale deep RL scenarios.
3i showed that the gradient ascent
A more thorough discussion on related works is given in Appendix

---

2 Preliminaries
System model A Markov decision process (MDP) is represented by tuple (S, A, P. n, r, where is the state space, A the action space, P: : S x A - (SS) the transition kernel, P E (S)) the initial state distribution, 7 (0, 1) the discount factor, and
x A [0, 1] the reward function. Given any policy : S + ((A) and any reward function r : 8 x A + [0, 1]. we define the state
value function V S 10, r and the state-action value function Q :S x A [0, 1-y1 as
VT7 B=
a.) so m| (s. : E a)) 8g 8, dg a. m)
where expectation E is taken over the random trajectory of the Markov chain induced by the policy и and the transition kernel P. With a slight abuse of notation, we denote V.= (p) := [V= (s)] Define the discounted state-action visitation distribution (state-action visitation for short) of policy with initial state distribution by dz (8, == (1 -e) 15 7'P((s = 44 also, m)}. then follows that V,7 (p) (d r) by viewing di and as (S|lAA-dimeesiooall vectors indexed by as E S x A. When it clear from the context, we denote the state visitation distribution by d=(s) : Esoup [[1 7) Er= (s: s|so]]. which is the marginal distribution of the state-action visitation (s, a), i... (5)s) EneA (s,
We study an MDP with m objectives represented by P.p,,, where r2 : x [0, 1] is the i-th reward function for each i [m]. For simplicity, denote (.) (- and
Tim (+) = (V) (-)) We consider parameterized policies in II = [To 0 θ), where
c R is the parameter space. For example, the softmax policy is (a(a))) Σ. exp(",,. with
exp(O..
+ = || and neural softmax policy is (a(as) Σn exp(NN. where NN is some neural network parameterized 9. Define V := (Vism (p) Q as the achievable region of value vectors. The agent wishes to optimize the policy in 11 for given specific multi-objective criterion on value vectors in V.
(e((NN((x.a))
Mirror ascent As one of the most well- iterative optimization methods, mirror descent (actually ascent in the context of our formulation as maximization problem) 7 is a general class that encompasses many first-order methods in convex optimization. Given variable in compact convex set C RR and an ascent direction g E R.", the variational representation of the mirror ascent update is
x' E arg max v) (y
(1)
where (xlll)) == h(x) h(v) - (Vh(y), y) is some Bregman divergence generated by differentiable convex function h X - TR. When analyzing the convergence of first-order methods, certain fundamental inequalities are usually established to facilitate the proof. One such inequality is
x²) - Ba (arll=== 2 (g. a BA (vlla) + (ull"))))
Vy E X,
(2)
which is critical step in many previous works, e.g., 22 27 16
is desirable construct a similar fundamental inequality for multi-objective MDPs that can facilitate the analysis of convergence. As we will show in the next section, such an inequality can indeed be established in a new framework, which we refer to the Anchor-Changing Regularized Natural Policy Gradient (ARNPG).
Notations Denote KL-divereence between two n-dimensional probability vectors x. y by D(xlly) Σns Ij (,), which is a widely-used Bregman divergence. For any policies ग, x and state visitation distribution d, define Da(=]((r') = E.es (T(s)) which chooses actions uniformly at random.
uniform policy is one
3 Anchor-changing regularized natural policy gradient
Let us consider hypothetical mirror ascent update decision value vector Uk E V according to (I] Given ascent direction Gjg along which to improve uk. the updated value vector is
v' E arg max (G,, v) - aB (vllv))) vEV
(3)
3

---

Suppose the value vector ey is achieved by policy Tee i... 2k = Vinn (p). Denote the reward function in the ascent direction as Fn (s a) (G&, Timm a)). It follows that (Gx, U&)
V Th (p).
Note that B, (vllvx) in serves the role of a soft constraint on by keeping e within vicinity of (azo (Ta))
will induce a similar soft constraint that prefers the vicinity of the "anchor" policy Td.- Therefore we consider replacing the variational update in 3 by
0k- Replacing ( ) by
I-y
D dx (TOll
8' arg max BEG
where
Via (p) Vi7 (p)
(4)
ARNPG Motivated by the intuition above, we propose the Anchor- Crahhor-haangng Regularized Natural Policy Gradient (ARNPG) framework. At (macro) step k, the ARNPG framework determines the reward function in the ascent direction T&z and the anchor policy Te., which can exploit well- performed first-order methods in convex optimization literature utilizing the features of the specific criteria in use. With ř5 and T we wish to solve for 4 to improve the value vector. However the optimal solution 8' of (4 is generally not determinable explicitly. ARNPG therefore approaches the optimal solution via a subroutine that executes natural policy gradient (NPG) algorithm w.r.t.
the KL-regularized value function Vi (p). We refer to this subroutine, given in Algorithm as
Innerl (oop(r n Ot, 71, 4.). It iteratively updates the parameter ( for la (micro) steps according to the NPG update rule as in 5 where (,)) is the Moore-Penrose inverse of the Fisher information matrix (0) == E (s,a)=d,
Vo log (als) (Vo log mo(a)s))
Algorithm I: InnerLoop(ik, Te,, 07,7 1x)
Initialize (10) = 0z
for f 0, O.I....th do
L
((++1)) b + 0 + (o Vo ka (p)
(5)
Return ((a))
The choice of the number of iterations in InnerLoop (i.e., t₂) involves a trade-off between the variational update precision and the overall efficiency. On the one hand, a larger fy leads a more accurate approximation of the optimal solution 0' to Q but it may cause the algorithm to spend unnecessary computational resources on the regularized objective ViTa (p), instead of on the true optimization problem. On the other hand, a smaller tu saves inner loop iterations but the update follows less closely the underlying mirror-ascent update improving the value vector. In our experiments, we choose Eg within 10 to strike balance and empirically observe tx > 1 has better performance.
We note that when l the gradient VoV. (p) gradient at 0 0s. The update in (5) reduces an NPG update the unregularized value function Vi (p). For oingle-objective MDPs, it reduces to the canonical NPG method.
VoVi Thx Fs (p), since Da.o (To)| has zero
3.1 Theoretical guarantee of ARNPG
We now present the main theoretical tool for the analysis of the ARNPG framework. Recall the discussion of the fundamental inequality after 2 Proposition D establishes such fundamental inequality with controllable approximation error under the softmax policy parameterization, i.c., exp(#..a)
To(als) ب.ب exp((....) In the rest of the paper, omit 0 in ao when it is clear from the context, but it should be noted that all updates of policies are performed on the parameters.
Proposition 1. Under the softmax parameterization, given EN > 0, for any Tx. to 2 log(
Gll 70
+ I, a 0 and 1-2, the update Th+1 + InnerLoop( ( Fx, n, (x)
satisfies
D 42 (TT+2l//TA)
Daz (IT (T)) Daz (T Tk41)
Mk+1 (p) a
2 V (p)
Ebs VT. (6)
1 1-7
1-2

---

The inequality G is critical to the convergence proof. Its right hand side allows telescoping, which by summing over k can iteratively cancel the terms Daz (Tr TT).. Since f2 ((log(L/cx)) it suffices use very few iterations in InnerLoop for maintaining precision.
Remark. It has been shown that for the rearropi-eeull MDP, i.e., KL-regularized with the uniform policy the anchor policy, NPG converges linearly (i.e., geometrically fast) the regularized optimal policy [TO]. It is natural to anticipate that for the KL-regularized MDP (p) with anchor gy.- NPG
would similarly converge linearly (i.e., V 2 V e for t2 (log to a corresponding optimal policy, denoted o contrast, the right hand side of inequality c has a positive drift
Dag (#1) for any policy n, which is considerably stronger.
1-7
Proof sketch of Proposition y We can show that InnerLoop approximately solves the variational update in 4 with linear convergence as anticipated. However to establish (6) the difficulty lies in the introduction of positive drift, since ViTe (p) is not concave w.r.t. and Daze (TT|| may not be Bregman divergence. We tackle this difficulty by showing that optimizing Ty in InnerLoop implicitly performs mirror ascent update for state action visitation d5
As demonstrated in the next section, Proposition I derived from the ARNPG framework is of the same rate as the underlying first-order methods with only extra logarithmic factors.
ensures that the convergence rate of the algorithms
4 Theoretical applications
In this section, we apply the ARNPG framework to several important multi-objective MDP scenarios and obtain new policy optimization algorithms by integrating first-order methods in convex opti- mization. All the theoretical results presented in this section are under the softmax parameterization with exact gradients. However, the obtained algorithms can be implemented in more general settings such as neural softmax and sample- scenarios, as in the next section. We theoretically establish (1/TT) convergence of these algorithms by leveraging the fundamental inequality in Proposition
4.1 Smooth concave scalarization function
We start by considering the following optimization problem max F(V 15m (p)),
0
where F is a concave function, and 8-smooth w.r.t.
I Iloo norm, i.e., [[VF(v) - VF('')ll S
31lv-t'llo. Since the set of achievable values C for some factor L 0.
0,
it can be verified that [|VF())] S
The proportional fair criterion discussed in Section can be approximated by F(v) Σ a, log( + wz), where > 0 is some constant introduced to circumvent the pathological case U3 for some i E [m]. Under this criterion, 3 = Em az/5² and L = - a//8.
When is viewed the decision variable, at macro step A with value vector ViTT (p), the ascent direction in typical gradient ascent step is the gradient Ö₁ VV.. (p)). This naturally determines the reward in the ascent direction as (s, a) = (G&, (G., (s, a))- Adapting the ARNPG framework to this specific context, we present the algorithm for solving the program 7 in Algorithm We refer to "implicit mirror descent" because the algorithm implicitly employs mirror descent.
Algorithm 2: ARNPG Implicit Mirror Descent (ARNPG-IMD)
Input To, Q, 7) lo.K -
for k 0, I,..,,
do Update Tk+1 + -InnerL Fk, o,, (,74)) (4)
Return the policy in { with the largest FVV (p))
Let "" be the optimal policy for 7 Based on Proposition we present the following theorem which guarantees the convergence of ARNPG-IMD with appropriately selected parameters To, a, 17, tg.
5

---

Theorem 1. For any K 2 1, take uniform policy No. 2
8 (1-7)a.
1_2 and ty.
5LK T log( HTo + 17. The optimality gap of ARNPG-IMD (Algorithm
satisfies
F(VE.
max F(V KE[L-K]
1am (p)) SF(VEm(()) - K ==1
1
Σ
K
F(V (p)) - (K 1am
2a log((A))
(8)
There are a total of K macro steps, and the total number of iterations is T = -x== tj @( @( K_ T- (og(K)). The following corollary provides the convergence rate in terms of T.
Corollary 1. Under the same conditions as in Theorem the ARNPG-IMD algorithm satisfies (logg()
F(VE. (p)) Xx E F(VT. =0 (117))1
Remark. the absence of knowledge of K, we can select time-varying numbers of Innerl.oop iterations, such as fg = (klo()))), and ARNPG-IMD will still have the same (11/T) convergence.
4.2 Constrained Markov decision process
Another way of trading off the objectives is to optimize one while setting hard constraints on the others. This can be formulated as the following constrained MDP (CMDP) problem:
max VL (p), V (p) > b; vi [2 m],,
(9)
where b2.m E (0, 1- 1 Let x To- be the optimal policy of the CMDP problem in 9
Define the Lagrangian of the CMDP problem L( A) ViTe (p) E >, where A; is the Lagrange multiplier (dual variable) corresponding to the constraint VTTe 2 6; for each i [2 m]. The Lagrange dual function max, f( is convex function of dual variables 2 O. Denote by X the optimal dual variables that minimize the Lagrange dual function. We assume X is finite, which is guaranteed by Slater's condition, i.e., there is some xy and & >> 0 with (p) - b; 2 & for any E [2 m]. Note (x", X*) is saddle point of the Lagrangian L(T, A). This motivates the primal-dual approach, which iteratively performs gradient ascent for me and gradient descent for A. This is suitable for the CMDP setting, since for any fixed X, the Lagrangian [(T, A) corresponds to an MDP for which policy gradient can be employed.
b,).
The canonical primal-dual gradient descent method for constrained convex optimization can only guarantee O(1/vT) convergence, and consequently the primal-dual policy gradient- based approach for CMDPs [1] has the same convergence. Recently, Yu al. (55] have proposed primal-
dual-based method with ((1 (1/T) convergence under the Euclidean setting, i.e., B, (x = ||x- y
Adopting ideas from 35 we next propose the ARNPG with Extra Primal-Duse (ARNPG-EPD)
algorithm (Algorithm 3) To the best of our knowledge, this new primal-dual update appears in the
CMDP-related literature for the first time.
Note that b, - V.T is the amount of constraint violation. There are two key ideas we adopt from B5
The first is the design of the reward in the ascent direction
i a) := (s. a) + 2A,, + 1/ - V.Th (p))))
where an extra constraint violation term is added to the dual variables. The second idea is that the update of dual variables should not fall below the negative constraint violation (the first term in (0). and it can alleviate the overshooting of dual variables. The extra constraint violation terms in N and the dual update work jointly to ensure the ((1/T) convergence.
Theorem 2. For any K > and n/' (0, take uniform policy no. a 5L*K and choose to = - log( 2n logí (AT)) + 17 with La -1+ 1-y 1'(m-11 + Emn A The average optimality gap and the average constraint violation of ARNPG-EPD (Algorithm satisfy
2 m (I-733-
"
3a log((A)) TTTH (p)
(p)
(11)
K
(1-7)K
km
121x*112
la log((Al) + 3 (1 (1 )
ViTH (p)
<
Vi E ml.
(12)
K
K
n
1=1

---

Algorithm 3: ARNPG with Extra Primal Dual (ARNPG-EPD)
Input To, 1/, a, 7), to:K-
Initialize Ao,; max 1/ (V, (p) - b)),0), Vi E [2: m]
for k I..... K do
Update Tk+1 wonnnerrooopp:: Ak, a, 77 77.k))
Update A max (V," 1 (p) b;), Ax,t 1/ (b, - (p))), Vi e [2: m] (10)
Return: a policy randomly chosen from { 1==1
K
Note that the number of micro steps lx chosen according to the dual variables X the previous theorem. Denote by T' := ΣK-1 tg the total number of iterations.
Corollary 2. Under the same conditions as in Theorem 2 the ARNPG-EPD algorithm satisfies
VI (p) * E VT 0 mn log(T) and b, Σ (.*
(1-7)7)
0 - (og(T)
(1-7)
The theorem and corollary establish convergence of the average optimality gap and the average constraint violation, in the same manner as many previous works M However, a guarantee on the last iterate is more preferable. This drawback is inherited from the primal-dual algorithm for convex optimization, where the primal-dual algorithm with sublinear convergence can only be guaranteed on the average solution, as of our knowledge. Last iterate convergence is still an on-going open research topic.
19 on CMDPs.
4.3 Max-min trade-off criteria
Finally, we consider the max-min trade-off criterion defined
max min ((V (p), A),
(13)
where A is subset of the m-dimensional probability simplex ([mm). We assume o(- A) is concave and ((v,-) is convex. We also assume 4 is 8-smooth w.r.t. the norm (( A) = |vllc + ||||
The max-min criterion mentioned in Section D can be represented by (v;, A) Σ 0//e/e; and A = [[m]). & satisfies the concave-convex assumption and is f3-smooth w.r.t. the norm with (())
Denote F(v) == minxes (ee A), which is concave but not necessarily smooth. Thus we cannot apply the ARNPG-IMD algorithm (Algorithm) due to the non-smoothness of F, and the subgradient- based method can only guarantee O(1/VT) convergence.
We next integrate the optimistic mirror descent ascent (OMDA) method Arr for solving minimax optimization in the ARNPG framework. Denote the gradients G V & (p), A&) and Gj V, 1:m (p), )+). can be verified that ||Gā|| < L for some L due to the smoothness of db OMDA performs gradient ascent along the direction Gy w.r.t. the value vector, and therefore we construct the reward in the ascent direction as Fx((s a) (Ōy, (.g. (s. ()) OMDA performs mirror descent along direction G% w.r.t. the dual vector X. A key ingredient of OMDA is that it updates twice in each macro step. ARNPG-OMD adopts this idea and update (T, A) from the same anchor points (TT, AR), first with ascent direction (Fx. - G E 2m2 and then a further step with direction (fR+1, -G G2 1) E 1m2m
We present ARNPG-OMDA in Algorithm and establish the following performance guarantees:
Theorem 3. For any K 2 1, take uniform policy no T/ I 63
60
77
1-1 and
SLK # - log( 63 Log( ) + 17. The ARNPG-OMDA algorithm (Algorithm
satisfies
1
K
3a log( (AA)
log(m)
F(VE - F
(p) 1sm
thu
(14)
K
(1
7)
r/ K
R=
7

---

Algorithm 4: ARNPG with Optimistic Mirror Descent Ascent (ARNPG-OMDA)
Input To, Ao 17', a, 77, f0:K-1, Initialize Mo = Mo and Au: λg as uniform distribution on [m]] for k- 0.I...... K 1 do
Update Tk+1 InnerLoop(TT. a, 77 tu), Aut1 arg minxmm ( D(A])An) Update Te+1 In-eerrLooop(T: 1 at 77, Lx), Akt1 < arg arg minneed (1G) k+1: + D(Njaul)
Return: a policy randomly chosen from TT 1K
k==
Similar the discussion after Corollary 2 Theorem provides a performance guarantee the
average value vector F( T Σ _k=1 1.mm (p)), which is inherited from the OMDA methods. Denote the
total number of iterations by T = Σk=o k== 21
K-11g
Corollary 3. Under the same conditions as in Theorem ARNPG-OMDA satisfies F (VIm (p))
K Ex Vi:m (p)) ( (1-7)²1)
F
5 Empirical evaluation and application
In this section, we present the experimental results on CMDP. We compare the performance of the proposed ARNPG-EPD algorithm (Algorithm B with two benchmarks: NPG-PD (I]] and CRPO Experimental details on CMDP are postponed to Appendix A and further experiments on smooth concave scalarization and max-min trade-off presented in Appendix B We provide code at https://gihub..omm/iuu 1997/RRPGG-MRR..
BI.
5.1 Tabular CMDP with exact gradients
Recall that under softmax policy with exact gradients, Corollary 2 (Theorem 2 guarantees ((1TT) convergence of both performance measures: average optimality gap and average constraint violation. We compare the proposed ARNPG-EPD with the benchmarks NPG-PD and CRPO under both performance measures on randomly generated CMDP with single constraint, which are illustrated The horizontal axis is the total number of iterations, i.c., including the micro steps in
in Figure ! InnerLoop of ARNPG-EPD.
Ogiinalty Gap
0.6
0.0
ARNFG PD ORPO
Vidillon
02
04
ARMPG-EPD
NPG CRPO
Ostmallyy Sap
SPD
ARMPG
0.4
t0
0.
4.2
-04
0
50
100
150
200
200
500
0
50
100 of Ierations
150
200
250
300
10
16f
10
12²
16
10'
10¹
herations
berations
lications
(a)
Figure 1: The average optimality gap and the average constraint violation versus the total number of iterations, for ARNPG-EPD, NPG-PD, and CRPO on a randomly generated CMDP.
Figures I aa and bbb show that both the average optimality gap and the average constraint violation of the ARNPG-ER EPD algorithm converge faster than those of NPG-PD. Since the CRPO focuses on the violated constraint, the policy becomes fcasible quickly, though at the cost of an initially slower convergence for the optimality gap. As illustrated in Figures ((c) and dd), the slopes of both the optimality gap and the constraint violation of the ARNPG-EPD algorithm in the log-log plots approximately between -0.9 and -1, indicating converge rate of ((/TT).
5.2 based tabular CMDP
We next consider the same tabular CMDP described in Section 5.1 without exact policy gradients. Instead, policy gradients are estimated by samples from generative model that can generate
8

---

Rewer Villues
Coretraint Vilelion
Rewerr Villues
Constreint Voletion
ARAPG-EPD NPG-0 CRPO
0.4
e.
02
3.1
ARNPG-BR NFC.FD
ARRNPG-RPD
8.0
NPG-PD
CRPO
200
150
200 250
150
liarations
llerations
(a)
(b)
(c)
(d)
Figure 2: The reward values and the constraint violation with respect the total number of iterations, for sample-bat ARNPG-EPD, NPG-PD, and CRPO on a randomly generated CMDP.
independent trajectories starting from any state and action pair. The assumption of such a generative model is common
3T.
The performances CRPO, NPG-PD, and ARNPG-EPD in the sample-based scenario are shown in Figure 2 Figures _ a) and bb) display the averaged performance, while Figures ( and d) display the pertormance of the current iterate (a.k.a. last-iterate optimization literature). shows that in this sample- based scenario, ARNPG-EPD achieves higher reward values with faster convergence, while all three algorithms satisfy the constraint after a few iterations.
5.3 Acrobot-v1
To demonstrate the efficacy of ARNPG-EPD on complex tasks, we have conducted experiments on the Acrobot-vl environment from OpenAl Gym [9] We follow the same experiment setup in BT where there a reward value to maximize, and two cost values to be constrained below some thresholds. The superior performance of ARNPG-EPD is shown in Figure
240
200
ARNPG-SPO
200
ARNPG-EPD
Reward Values
200
1.0
NPG PD CRPO
150
PD
160 120
Cost Values
1.00
Values
1:20
CRPO
80
80
ARNPI-EPDD NPG-PO
40
0-
180 250 400 0
250
of lierations
of lterations
of lterations
(a)
(b)
(c)
Figure 3: Last-iterate performance for sample-based ARNPG-EPD, NPG-PD, CRPO averaged over 10 random seeds. The black dashed lines in (b) and (c) represent given thresholds.
Figure 3 () shows that ARNPG-EPD achieves a higher reward value compared NPG-PD and CRPO, while Figures ()) and ((c) demonstrate that the cost values of all three algorithms are below the thresholds after few initial iterations. We believe the superiority is due the new primal-dual
design inspired by (34] (discussed in Section 4.2) and the flexibility of choosing & in the InnerLoop in the framework. More experiments with different t are presented Appendix A
6 Conclusion and future works
We propose an ARNPG framework to systematically integrate well well-performing first-order methods into the design of policy gradient-basee algorithms for multi-objective MDPs. The designed algo- rithms achieve global O(1/T" convergence rate under the softmax parameterization with exact gradients, and empirically have satisfactory performance beyond tabular and exact gradient settings. We believe that ARNPG has potential applications in other scenarios, since the general and flexible framework allows integration with more advanced first-order methods, currently and in the future.
A natural future direction is to extend the theoretical results to more general settings such as function approximation and sample-based scenarios. Viewing ARNPG as a heuristic, the anchor-changing ideas can also be applied policy optimization for multi-agent RL and meta RL.

---

7 Acknowledgement
R. Kumar's work based upon work partially supported by the US Army Contracting Command under W911NF-22-1-0151. US Office of Naval Research under N00014-21-1-2385, 4/21-22 DARES: Army Research Office W91 N-F-21-20064, US National Science Foundation under NMMI-2038625. The views expressed herein and conclusions contained in this document are those of the authors and should not be interpreted as representing the views or official policies, either expressed or implied, of the U.S. Army Contracting Command, ONR, ARO, NSF, or the United States Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
Dileep Kalathil gratefully acknowledges funding from the U.S. National Science Foundation (NSF) grants NSF-CRII-CPS: 1850206 and NSF-CAREER-EPE --455-204
We thank Dongsheng Ding and Tengyu Xu for generously sharing their code in
31
baselines.
References
[1] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approxi- mation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pages 64-66. PMLR, 2020.
[2] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
[3] Mridul Agarwal and Vaneet Aggarwal. Reinforcement learning for joint optimization of multiple rewards. arXiv preprint 1rXiv:1909.02990 190999999900 2019.
[4] Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
[5] Qinbo Bai, Mridul Agarwal, and Vaneet Aggarwal. Joint optimization of multi-objective reinforcement learning with policy gradient based algorithm. arXiv preprint arXiv:2105.1412. 2021.
[6] Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. arXiv preprint arXiv:2109.06332 2021.
[7] Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
[8] Dimitri Bertsekas and Robert Gallager. Data networks. Athena Scientific, 2021.
[9] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
[10] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 2021.
[11] Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo R Jovanovic. Natural policy gradient primal-dur method for constrained markov decision processes. In Advances in Neural Information Processing Systems, 2020.
[12] Arushi Jain, Sharan Vaswani, Reza Babanezhad, Csaba Szepesvari, and Doina Precup. Towards painless policy optimization for constrained mdps. arXiv preprint arXiv:2204.05176, 2022.
[13] Frank P Kelly, Aman K Maulloo, and David Kim Hong Tan. Rate control for communica- tion networks: shadow prices, proportional fairness and stability. Journal of the Operational Research society, (0(3))237-252 1998.
[14] Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and Siva Theja Mag- uluri. On the linear convergence of natural policy gradient algorithm. arXiv preprint 1rXiv:2105.01422 2021.
10

---

[15] Panagiotis Kyriakis, Jyotirmoy Deshmukh, and Paul Bogdan. Pareto policy adaptation. In International Conference on Learning Representations, 2022.
[16] Guanghui Lan. First-order and Stochastic Optimization Methods for Machine Learning. Springer Nature, 2020.
[17] Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. arXiv preprint arXiv:2102.00133, 2021.
[18] Tianjiao Li, Ziwei Guan, Shaofeng Zou, Tengyu Xu, Yingbin Liang, and Guanghui Lan. Faster algorithm and sharper analysis for constrained markov decision process. arXiv preprint arXiv:21 10. 10351, 2021.
[19] Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. Advances in Neural Information Processing Systems, 34, 2021.
[20] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global con- vergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pages 6820-6829, PMLR, 2020.
[21] Arkadi Nemirovski. Prox-method with rate of convergence o (1/t) for variational inequali- ties with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15())229--21, 2004.
[22] Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013.
[23] Diederik M Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley. A survey of multi- objective sequential decision-making. Journal of Artificial Intelligence Research, 48:67-113, 2013.
[24] Sandhya Saisubramanian, Ece Kamar, and Shlomo Zilherstein. A multi-objectivve approach mitigate negative side effects. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pages 354-361, 2021.
[25] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, pages 5026-5033. IEEE, 2012.
[26] Kristof Van Moffaert, Madalina M Drugan, and Ann Nowé. Scalarized multi-objective rein- forcement learning: Novel design techniques. In 2013 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL), pages 191-199. IEEE, 2013.
[27] Chen- Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng I Luo. Linear last-iterate con- vergence in constrained saddle-point optimization. In International Conference Learning Representations, 2020.
[28] Xiaohan Wei, Hao Yu, and Michael Neely. Online primal-dual mirror descent under stochastic constraints. Proceedings of the ACM on Measurement and Analysis Computing Systems, 4(2):1-36, 2020.
[29] Kyle Hollins Wray, Shlomo Zilberstein, and Abdel-Illah Mouaddib. Multi-objective mdps with conditional lexicographic reward preferences. In Twenty- AAAI conference on artificial intelligence, 2015.
[30] Jingfeng Wu, Vladimir Braverman, and Lin F Yang. Accommodating picky customers: Regret bound and exploration complexity for multi-objective reinforcement learning. arXiv preprint arXiv:2011 1. 13034, 2020.
[31] Tengyu Xu, Yingbin Liang, and Guanghui Lan. CRPO: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pages 1 11480-1149 1491. PMLR, 2021.

---

[32] Runzhe Yang. Xingyuan Sun, and Karthik Narasimhan. A generalized algorithm for multi- objective reinforcement learning and policy adaptation. Advances in Neural Information Processing Systems, 32, 2019.
[33] Donghao Ying, Yuhao Ding, and Javad Lavaei. A dual approach constrained markov decision processes with entropy regularization. arXiv preprint arXiv:2110.0883 2021.
[34] Hao Yu and Michael J Neely. A primal-dual parallel method with O(1/e) convergence for constrained composite convex programs. arXiv preprint 1tXiv:1708.00322 2017.
[35] Hao Yu and Michael Neely, A simple parallel algorithm with an O(1i)) convergence rate for general convex programs. SIAM Journal Optimization, 27(2):759-783, 2017.
[36] Junyu Zhang, Amrit Singh Bedi, Mengdi Wang, and Alec Koppel. Beyond cumulative returns via reinforcement learning over state-action occupancy measures. In 2021 American Control Conference (ACC), pages 894-901, IEEE, 2021.
[37] Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. Advances Neural Information Processing Systems, 33:4572-45555 2020.
[38] Yiming Zhang, Quan Vuong, and Keith Ross. First order constrained optimization in policy space. Advances in Neural Information Processing Systems, 11115338-1334 2020.
[39] Dongruo Zhou, Jiahao Chen, and Quanquan Gu. Provable multi-objective reinforcement learning with generative models. arXiv preprint arXiv:2011.10134, 2020.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A] You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section
Did you include the license to the code and datasets? [No] The code and the data are proprictary.
Did you include the license the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the last paragraphs of Section
4 and
4K
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to
them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] After the definition of the problems 9
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix C and t
3. If you experiments...
12

---

(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as URL)? [Yes] See https://gitub..co//iiu
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix and
(c) Did you report error bars (c.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We only report the mean in Figure S for clarity. In
Appendix A we will report error bars.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
See https://ithub..cm//iii 1997/ARNPG-MORI.
(d) Did you discuss whether and how consent obtained from people whose data you're
using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "xUd7Frf8Xhk", "reviewer": "Reviewer_yFP8", "summary": "This paper proposed an Anchor-changing Regularized Natural Policy Gradient (ARNPG) framework, which can systematically incorporate ideas from well-performing first-order methods into the design of policy optimization algorithms for multi-objective MDP problems. Theoretically, the designed algorithms based on the ARNPG framework achieve $O(\\frac{1}{T})$ global convergence with exact gradients.  A few experiments demonstrate the effectiveness of the algorithm.", "questions": " There are no obvious problems. I am only concerned about whether it can be applied to more complex tasks, such as robotics control or video game, etc.", "limitations": "The limitations of the algorithm are rarely discussed in this paper. As far as I'm concerned, the algorithm presented in this paper is only proved to be effective in a very simple human-designed environment, and there are no relevant experiments for more practical standard tasks, such as video games.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n1. Adequate theoretical proof.\n2. Well-established experimental evidence (though simple).\n3. The motivation is clear.\n\n## Weaknesses\n1. Except for the tabular-based experiment, the effectiveness of ARNPG is verified in only one task (i.e., Acrobot-v1). We still need more practical examples to verify the value of the algorithm in more scenarios. I am concerned that one example alone is not enough to demonstrate the effectiveness of the algorithm.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VXm-zWGvHmo", "reviewer": "Reviewer_Mwr3", "summary": "This paper studies three instances of the multi-objective RL problem, namely smooth concave scalarization, CMDPs, and max-min trade-off. The authors proposed a new class of algorithms for these problems which updates a regularized objective which constrains the KL between the update policy and some anchor policy and uses natural gradients for policy update. The resulting algorithm achieves $\\tilde{O}(1/T)$ global convergence with exact gradients.", "questions": "- Mathematically it seems that using natural gradients is key to achieving $\\tilde{O}(1/T)$ global convergence but I wonder if you could give a little more intuition on the update rule in Equation (5), specifically if we change the gradient term to be w.r.t. the unregularized objective $V$ instead of the regularized $\\tilde{V}$, this would be first-order equivalent to optimizing the KL-regularized objective in Equation (4) (first-order equivalence of TRPO and NPG) so I'm curious what is the intuition with taking the gradient of the regularized objective here?\n- Following up on the previous question, what would happen if we were to remove the Fisher information term altogether and do the InnerLoop as a standard policy gradient update w.r.t. the regularized objective.\n- Another question I have is related to the sample efficiency of the algorithm from a practical perspective, since both the expected KL and Fisher information matrix are w.r.t. $\\pi_{\\theta}$ and not the anchor policy $\\pi_{\\theta_k}$, this means that if we were to use a sample-based version of your proposed algorithm, we would need to collect new samples from $\\pi_{\\theta}$ every time we perform a policy update in the InnerLoop, wouldn't this be extremely sample inefficient even for relatively small $t_k$?\n- (Minor) On line 147, is the tilde on top of the $V$ on the RHS of the equality a typo?\n- (Minor) \"Lagrange\" is mis-spelt as \"Langrange\" in several places.", "limitations": "Yes, the authors discussed future extensions to the function approximation case", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think this is a solid paper which extends the recent series of work on the global convergence of policy gradient methods to several important classes of multi-objective problems. One disclaimer I wish to make is that even though I am familiar with some of the related work, this paper is a little outside my own research area, but despite this I found the paper to be quite clearly written and fairly easy for me to follow. I did not go through all the details of the proofs but the overall structure and logic is quite clear. Multi-objective RL and constrained RL are gaining increasing interest within the community both from a theoretical and practical perspective, I think this paper makes an important contribution to our understanding of the problem and I therefore recommend this paper for acceptance.  Some additional comments and questions below in the section below.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MNMJTijl-2", "reviewer": "Reviewer_w1Sp", "summary": "In this paper, the authors studied policy optimization in multi-objective Markov decision processes. Three specific optimization scenarios are considered: smooth concave scalarization, objective constraints, and max-min tradeoffs. The main technical contribution is an anchor-changing regularized natural policy gradient (ARNPG) framework. Theoretical analyses for the three scenarios are provided under the ARNPG framework. Some empirical experiments corroborate theoretical results.", "questions": "1. Line 122: equation (3), I believe it should be $v$ instead of $v_k$ in the inner product?\n\n2. Line 639: It would improve the readability of the proof to include some more details on how equation (20) comes about, rather than simply pointing to a reference.\n\n3. I am not entirely clear on what the “exact gradients” mean in Section 5.1. Can the authors provide some clarifications?\n", "limitations": "The authors had an adequate discussion on the limitation of the current work. \n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: This work is quite original. The authors make this connection between mirror ascent and multi-objective policy optimization. Proposition 1, which establishes an analogous inequality to classical first-order methods, is technically novel. \n\nThe theoretical applications of Proposition 1 (Section 4) are natural and instructive. The three optimization scenarios encompass a wide range of decision-making in multi-objective MDPs. In summary, this paper clearly passes the bar for originality. \n\nQuality: I have only checked the proof of Proposition 1 (Section D in the Appendix) as it is the foundation for the subsequent analyses. The proof is technically sound and contains several interesting techniques. \n\nBeing a mainly theoretical paper, the empirical evaluation part (Section 5) provides some corroborations to the theoretical results but it is weak in terms of baselines. In Section B.1.1 Sommth concave scalarization, there are no baseline methods. Granted the specific scalarization formula (equation 16) limits baseline choices. I wonder if it is possible to apply the more common linear scalarization, which is also smooth concave, and compare with works such as the one by Yang et al. NeurIPS 2019.\n\nClarity: The paper is overall clear. I have some minor questions in the next section.\n\nSignificance: Theoretical analyses of policy optimization in multi-objective MDPs are highly relevant to the NeurIPS community. The novel proof techniques in this paper are likely to be significant for the future development of this topic.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1rWsSnH_hM3", "reviewer": "Reviewer_kSw7", "summary": "The authors propose Anchor-changing Regularized Natural Policy Gradient (ARNPG), a novel framework for designing policy-gradient based methods for multi-objective MDPs which builds on first-order methods for convex optimization problems. In contrast to prior work, it allows $\\mathcal O(1/T)$ convergence without artificial or impractical assumptions. The authors theoretically analyze their approach and provide empirical evaluations in exact-gradient as well as sampling-based CMDP as well as on Acrobot.", "questions": "---------", "limitations": "-----------", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality:** The authors develop a novel framework for the design of policy-gradient methods in multi-objective MDPs and demonstrate its application in several scenarios (proportional fairness, constrained MDP, max-min trade-off). Building on first-order convex optimization methods, they claim that their method achieves $\\mathcal O(1/T)$ global convergence w.r.t. optimality gap and constraint violation, which related work does not achieve without further assumptions. They clearly work out their contributions in their Introduction and Related Work section. \n\n**Quality:** The problem setting as well as the proposed ARNPG approach and its theoretical foundations are presented clearly and in a technically sound manner. The authors thoroughly analyze ARNPG in various different scenarios and make sure to clearly state relevant assumptions for their proofs. Further, they provide experimental evidence for the effectiveness of their approach. However, I am not familiar enough with the topic to judge the soundness of the proofs and experiments themselves.\n\n**Clarity:** The paper is written very clearly. The authors structure their work well and do a good job in guiding the reader through their paper. I cannot judge the presentation and clarity of the derivations and proofs. \n\n**Significance:** I believe that powerful policy-gradient methods for multi-objective MDPs and, in particular, a thorough and sound theoretical and experimental analysis as presented in the paper is important and therefore I am convinced the submission is interesting for the community. However, I am not familiar enough with the state of the art to fully judge the significance of this work.\n\nIn summary, I think this work is an interesting contribution and presented in a clear and well-written manner. Therefore, I recommend acceptance. However, this recommendation is with low confidence, as I am not very familiar with the topic. Therefore, I might adjust my rating after the discussion period.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept