CUP: A CONSERVATIVE UPDATE POLICY ALGORITHM
Year: 2021

Abstract:
Safe reinforcement learning (RL) is still very challenging since it requires the agent to consider both return maximization and safe exploration. In this paper, we propose CUP, a Conservative Update Policy algorithm with a theoretical safety guarantee. The derivation of CUP is based on surrogate functions with respect to our new proposed bounds. Although using bounds as surrogate functions to design safe RL algorithms have appeared in some existing works, we develop it at least three aspects: (i) We provide a rigorous theoretical analysis to extend the bounds with respect to generalized advantage estimator (GAE). GAE significantly reduces variance while maintains a tolerable level of bias, which is an efficient step for us to design CUP; (ii) The proposed bounds are more compact than existing works, i.e., using the proposed bounds as surrogate functions are better local approximations to the objective and constraints. (iii) The bound of worst-case safe constraint violation of CUP is more compact than the existing safe RL algorithms, which explains why CUP is so good in practice. Finally, extensive experiments show the effectiveness of CUP where the agent satisfies safe constraints.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) (Sutton & Barto, 1998) has achieved significant successes in many fields (Mnih et al., 2015; Silver et al., 2017; OpenAI, 2019; Afsar et al., 2021), robotics (Deisenroth et al., 2013), playing Go (Silver et al., 2016; 2017), Starcraft (Vinyals et al., 2019), Dota (OpenAI, 2019), and recommendation system (Afsar et al., 2021). However, most RL algorithms improve the performance under the assumption that an agent is free to explore any behaviors. In real-world applications, only considering return maximization is not enough, and we also need to consider safe behaviors. For example, a robot agent should avoid playing actions that irrevocably harm its hardware, and a recommender system should avoid presenting offending items to users. Thus, it is crucial to consider safe exploration for RL, which is usually formulated as constrained Markov decision processes (CMDP) (Altman, 1999).
It is challenging to solve CMDP since traditional approaches (e.g., Q-learning (Watkins, 1989) & policy gradient (Williams, 1992)) usually violate the safe exploration constraints, which is undesirable for safe RL. Recently, Achiam et al. (2017); Yang et al. (2020); Bharadhwaj et al. (2021) suggest to use some surrogate functions to replace the objective and constraints. However, their implementations involve some convex approximations to the non-convex objective and safe constraints, which leads to many error sources and troubles. Concretely, Achiam et al. (2017); Yang et al. (2020); Bharadhwaj et al. (2021) approximate the non-convex objective (or constraints) with first-order or second Taylor expansion, but their implementations still lack a theory to show the error difference between the original objective (or constraints) and its convex approximations. Besides, their approaches involve the inverse of a high-dimension Fisher information matrix, which causes their algorithms to require a costly computation for each update when solving high-dimensional RL problems.
Our Main Work. To address above problems, we propose the conservative update policy (CUP) algorithm with a theoretical safety guarantee. We derive the CUP bases on some new proposed surrogate functions with respect to objective and constraints and provide a practical implementation of CUP that does not depend on any convex approximation to adapt high-dimensional safe RL.
Concretely, in Section 3, Theorem 1 shows generalized difference bounds between two arbitrary policies for the objective and constraints. Those bounds provide principled approximations to the
objective and constraints, which are theoretical foundations for us to use those bounds as surrogate functions to replace objective and constraints to design algorithms.
Although using difference bound to replace objective or constraints has appeared in some existing works (e.g., (Kakade & Langford, 2002; Schulman et al., 2015; Achiam et al., 2017)), Theorem 1 improves their bounds at least two aspects: (i) Firstly, our rigorous theoretical analysis extends the bound with respect to generalized advantage estimator (GAE) (Schulman et al., 2016). GAE significantly reduces variance while maintains a tolerable level of bias, which is one of the critical steps for us to design efficient algorithms in the later section. Although Zhang et al. (2020); Kang et al. (2021) have applied GAE to solve safe RL problems, their approaches are empirical and lack a theoretical analysis with respect to GAE. Thus, our result provides a theory to illustrate the effectiveness of the work (Zhang et al., 2020; Kang et al., 2021). (ii) Our new bounds refine classic difference bounds. For example, our bounds are more compact than Achiam et al. (2017), i,e., using our new bounds as surrogate functions are better local approximations to the objective and constraints. Besides, the surrogate functions with respect to our new bounds are more accessible to be estimated from the samples than the approaches appears in (Kakade & Langford, 2002; Schulman et al., 2015)), for more discussions, please see Remark 1.
In Section 4, we provide the necessary details of the proposed CUP. The CUP contains two steps: it performs a policy improvement at first, then it projects the policy back onto the safe region to reconcile the constraint violation. Theorem 2 shows a lower bound on policy improvement and an upper bound on constraint violation for CUP at each update. Notably, the result in Theorem 2 shows the bound of CUP is more compact than state-of-the-art safe RL algorithms: CPO (Achiam et al., 2017, Proposition 1-2), PCPO (Yang et al., 2020, Theorem 1) and FOCOPS (Zhang et al., 2020), which provides a partial explanation for why CUP is so good in practice. For more discussions, please refer to Remark 2. Finally, we provide a practical implementation of sample-based CUP. Such an implementation allows us to use deep neural networks to train a model. Mainly, CUP does not depend on any convex approximation for objective and constraints, and it optimizes the objective according to the first-order optimizer. Extensive high-dimensional experiments on continuous control tasks show the effectiveness of CUP where the agent satisfies safe constraints.

heading: 2 PRELIMINARIES
text: Reinforcement learning (RL) (Sutton & Barto, 1998) is often formulated as a Markov decision process (MDP) (Puterman, 2014) that is a tupleM = (S,A,P, r, ρ0, γ). Here S is state space, A is action space. P(s′ |s, a) is probability of state transition from s to s′ after playing a. r(·) : S ×S ×A → R, and r(s′|s, a) denotes the reward that the agent observes when state transition from s to s′ after it plays a. ρ0(·) : S → [0, 1] is the initial state distribution and γ ∈ (0, 1). A stationary parameterized policy πθ is a probability distribution defined on S ×A, πθ(a|s) denotes the probability of playing a in state s. We use Πθ to denote the set of all stationary policies, where Πθ = {πθ : θ ∈ Rp}, and θ is a parameter needed to be learned. Let Pπθ ∈ R|S|×|S| be a state transition probability matrix, and their components are: Pπθ [s, s ′] = ∑ a∈A πθ(a|s)P(s′|s, a) =: Pπθ (s ′ |s), which denotes one-step state transformation probability from s to s′ by executing πθ. Let τ = {st, at, rt+1}t≥0 ∼ πθ be a trajectory generated by πθ, where s0 ∼ ρ0(·), at ∼ πθ(·|st), st+1 ∼ P(·|st, at), and rt+1 = r(st+1|st, at). We use Pπθ (st = s
′ |s) to denote the probability of visiting the state s ′ after t time steps from the state s by executing πθ . Due to the Markov property in MDP, Pπθ (st = s ′ |s) is (s, s′)-th component of the matrix Ptπθ , i.e., Pπθ (st = s ′ |s) = Ptπθ [s, s ′ ].
Finally, let ds0πθ (s) = (1 − γ) ∑∞ t=0 γ
tPπθ (st = s|s0) be the stationary state distribution of the Markov chain (starting at s0) induced by policy πθ. We define dρ0πθ (s) = Es0∼ρ0(·)[d s0 πθ
(s)] as the discounted state visitation distribution on initial distribution ρ0(·). The state value function of πθ is defined as Vπθ (s) = Eπθ [ ∑∞ t=0 γ
trt+1|s0 = s], where Eπθ [·|·] denotes a conditional expectation on actions which are selected by πθ. Its state-action value function is Qπθ (s, a) = Eπθ [ ∑∞ t=0 γ
trt+1|s0 = s, a0 = a], and advantage function is Aπθ (s, a) = Qπθ (s, a)− Vπθ (s). The goal of reinforcement learning is to maximize J(πθ):
J(πθ) = Es∼dρ0πθ (·)[Vπθ (s)]. (1)

heading: 2.1 POLICY GRADIENT AND GENERALIZED ADVANTAGE ESTIMATOR (GAE)
text: Policy gradient (Williams, 1992; Sutton et al., 2000) is widely used to solve policy optimization, which maximizes the expected total reward by repeatedly estimating the gradient g = ∇J(πθ). Schulman et al. (2016) summarize several different related expressions for the policy gradient:
g = ∇J(πθ) = E [ ∞∑ t=0 Ψt∇ log πθ(at|st) ] , (2)
where Ψt can be total discounted reward of the trajectory, value function, advantage function or temporal difference (TD) error. As stated by Schulman et al. (2016), the choice Ψt = A(st, at) yields almost the lowest possible variance, which is consistent with the theoretical analysis (Greensmith et al., 2004; Wu et al., 2018). Furthermore, Schulman et al. (2016) propose generalized advantage estimator (GAE) ÂGAE(γ,λ)t (st, at) to replace Ψt: for any λ ∈ [0, 1],
Â GAE(γ,λ) t (st, at) = ∞∑ `=0 (γλ)`δVt+`, (3)
where δVt = rt+1 + γV (st+1)− V (st) is TD error, and V (·) is an estimator of value function. GAE is an efficient technique for data efficiency and reliable performance of reinforcement learning.

heading: 2.2 SAFE REINFORCEMENT LEARNING
text: Safe RL (Ray et al., 2019) is often formulated as a constrained MDP (CMDP)M∪C (Altman, 1999), which is a standard MDPM augmented with an additional constraint set C. The set C = {(ci, bi)}mi=1, where ci are cost functions: ci : S ×A → R, and limits are bi, i = 1, ·,m. The cost-return is defined as: Jci(πθ) = Eπθ [ ∑∞ t=0 γ
tci(st, at)], then we define the feasible policy set ΠC as: ΠC = ∩mi=1 {πθ ∈ Πθ and Jci(πθ)≤bi} .
The goal of CMDP is to search the optimal policy π? such that π? = arg max
πθ∈ΠC J(πθ). (4)
Furthermore, we define value functions, action-value functions, and advantage functions for the auxiliary costs in analogy to Vπθ , Qπθ , and Aπθ , with ci replacing r respectively, we denote them as V ciπθ , Q ci πθ , and Aciπθ . For example, V ci πθ (s) = Eπθ [ ∑∞ t=0 γ
tci(st, at)|s0 = s]. Without loss of generality, we will restrict our discussion to the case of one constraint with a cost function c and upper bound b. Finally, we extend the GAE w.r.t. auxiliary cost function c:
Â GAE(γ,λ) C,t (st, at) = ∞∑ `=0 (γλ)`δCt+`, (5)
where δCt = rt+1 + γC(st+1)− C(st) is TD error, and C(·) is an estimator of cost function c.

heading: 3 GENERALIZED POLICY PERFORMANCE DIFFERENCE BOUNDS
text: In this section, we show some generalized policy optimization performance bounds for J(πθ) and Jc(πθ). The proposed bounds provide some new certain surrogate functions w.r.t. the objective and cost function, which are theoretical foundations for us to design efficient algorithms to improve policy performance and satisfy constraints. Additionally, those bounds refine or extend some existing works (e.g., (Kakade & Langford, 2002; Schulman et al., 2015; Achiam et al., 2017)) to GAE case that significantly reduces variance while maintains a tolerable level of bias, which is one of the key steps for us to propose efficient algorithms in the later section.
Before we present our new bounds, let us revisit a classic result about policy performance difference from (Kakade & Langford, 2002), i.e., the next Eq.(6),
J(πθ)− J(πθ′ ) = (1− γ) −1Es∼dρ0πθ (·)Ea∼πθ(·|s)[Aπθ′ (s, a)]. (6)
Eq.(6) shows a difference between two arbitrary policies πθ and πθ′ with different parameters θ and θ ′ . However, as stated by Zanger et al. (2021), Eq.(6) is very intractable for sampling-based policy optimization since it requires the data comes from a fixed policy πθ. In this section, our new bound will refine the result (6). For more discussions about the difference between our new bound and Eq.(6), please refer to Remark 1.

heading: 3.1 SOME ADDITIONAL NOTATIONS
text: We use a bold lowercase letter to denote a vector, e.g., a = (a1, a2, · · · , an), and its i-th element a[i] =: ai. Let ϕ(·) : S → R be a function defined on S, δϕt = r(st+1|st, at) + γϕ(st+1)− ϕ(st) is TD error w.r.t. ϕ(·). For two arbitrary policies πθ and πθ′ , we denote δ ϕ πθ,t
(s) as the expectation of TD error, and define ∆ϕt (πθ, πθ′ , s) as the difference between δ ϕ πθ,t (s) and δϕπ θ ′ ,t(s): ∀s ∈ S,
δϕπθ,t(s) = Est∼Pπθ (·|s) at∼πθ(·|st)
st+1∼P(·|st,at)
[δϕt ] ,∆ ϕ t (πθ, πθ′ , s) = E
st∼Pπ θ ′ (·|s)
at∼πθ′ (·|st) st+1∼P(·|st,at)
[( πθ(at|st) πθ′ (at|st) − 1 ) δϕt ] .
Furthermore, we introduce two vectors δϕπθ,t,∆ ϕ t (πθ, πθ′ ) ∈ R|S|, and their components are:
δϕπθ,t[s] = δ ϕ πθ,t (s), ∆ϕt (πθ, πθ′ )[s] = ∆ ϕ t (πθ, πθ′ , s). (7) Let matrix P(λ)πθ = (1 − γλ) ∑∞ t=0(γλ)
tPt+1πθ , where λ ∈ [0, 1]. It is similar to the normalized discounted distribution dρ0πθ (s), we extend it to λ-version and denote it as d λ πθ (s):
dλπθ (s) = Es0∼ρ0(·)
[ (1− γ̃)
∞∑ t=0 γ̃tP(λ)πθ (st = s|s0)
] ,
where γ̃ = γ(1−λ)1−γλ , the probability P (λ) πθ (st = s|s0) is the (s0, s)-th component of the matrix product(
P (λ) πθ )t . Finally, we introduce a vector dλπθ ∈ R |S|, and its components are: dλπθ [s] = d λ πθ (s).

heading: 3.2 MAIN RESULTS
text: Theorem 1 (Generalized Policy Performance Difference). For any function ϕ(·) : S → R, for two arbitrary policies πθ and πθ′ , for any p, q ∈ [1,∞) such that 1p + 1 q = 1, we define two error terms:
ϕ,(λ) p,q,t (πθ, πθ′ ) =: ‖d λ πθ − dλπ θ ′ ‖p‖δ ϕ πθ,t ‖q, (8)
Lϕ,±p,q (πθ, πθ′ ) =: 1
1− γ̃ ∞∑ t=0 γtλtEs∼dλπ θ ′ (·) [ ∆ϕt (πθ, πθ′ , s)± ϕ,(λ) p,q,t (πθ, πθ′ ) ] . (9)
Then, the following bound w.r.t. policy performance difference J(πθ)− J(πθ′ ) holds: Lϕ,−p,q, (πθ, πθ′ ) ≤ J(πθ)− J(πθ′ ) ≤ L ϕ,+ p,q, (πθ, πθ′ ). (10)
We provide its proof in Appendix E. The bound (10) is tight, i.e., if πθ = πθ′ , all the three terms in Eq.(10) are zero identically. From Eq.(9), we know the performance difference bound Lϕ,±p,q (πθ, πθ′ ) (10) can be interpreted by two distinct difference parts: (i) the first difference part, i.e., the expectation ∆ϕt (πθ, πθ′ , s), which is determined by the difference between TD errors of πθ and πθ′ ; (ii) the second difference part, i.e., the discounted distribution difference ϕ,(λ)p,q,t (πθ, πθ′ ), which is determined by the gap between the normalized discounted distribution of πθ and πθ′ . Thus, the difference of both TD errors and discounted distribution determine the policy difference J(πθ)− J(πθ′ ). The different choices of p and q lead Eq.(10) to be different bounds. If p = 1, q = ∞, we denote ϕπθ,t =: ‖δ ϕ πθ,t ‖q = maxst∈S Eat∼πθ(·|st),st+1∼P(·|st,at)[|δ ϕ t |], then, according to Lemma 2 (see Appendix E.3), when p = 1, q =∞, then error ϕ,(λ)p,q,t (πθ, πθ′ ) is reduced to:
ϕ,(λ) p,q,t (πθ, πθ′ ) ∣∣ p=1,q=∞ ≤ 1 1− γ̃ · γ(1− λ) ϕπθ,t |1− 2γλ|S||A|| Es∼dλπ θ ′ (·) [2DTV(πθ′ , πθ)[s]] ,
where DTV(πθ′ , πθ)[s] is the total variational divergence between action distributions at state s, i.e., 2DTV(πθ′ , πθ)[s] = ∑ a∈A |πθ′ (a|s)− πθ(a|s)| .
Finally, let ϕ = Vπ θ ′ , the left side of (10) in Theorem 1 implies a lower bound of performance difference, which illustrates the worse case of approximation error, we present it in Proposition 1.
Proposition 1 (Worse case approximation error). For any two policies πθ and πθ′ , let Vπθ (πθ′ ) =: supt∈N+{ ϕ πθ,t : ϕ = Vπ θ ′ }, then the following bound holds
J(πθ)− J(πθ′ ) (11)
≥ 1 1− γ̃ Es∼dλπ θ ′ (·),a∼πθ(·|s)
[ AGAE(γ,λ)π
θ ′ (s, a)− 2γ(1− λ) Vπθ (πθ′ ) (1− γλ) |1− 2γλ|S||A|| DTV(πθ′ , πθ)[s]
] .
If λ→ 0, then the distribution dλπ θ ′ (·) is reduced to dρ0π θ ′ (·) and the bound (11) is reduced to
J(πθ)− J(πθ′ ) ≥ 1
1− γ Es∼dρ0π θ ′ (·),a∼πθ(·|s)
[ Aπ
θ ′ (s, a)− 2γ Vπθ (πθ′ )DTV(πθ′ , πθ)[s]
] . (12)
Let us review (Achiam et al., 2017, Corollary 1), which shows
J(πθ)− J(πθ′ ) ≥ 1
1− γ Es∼dρ0π θ ′ (·),a∼πθ(·|s)
[ Aπ
θ ′ (s, a)− 2
γ Vπθ (πθ′ )
1− γ DTV(πθ′ , πθ)[s]
] . (13)
Comparing (12) to (13), our new bound (12) is slightly tighter than the bound shown by (Achiam et al., 2017). Concretely, our result improves the bound (13) by a factor 11−γ . Since the refined bound (11) contains GAE technique that significantly reduces variance while maintains a tolerable level of bias (Schulman et al., 2016), which implies using the bound (11) as a surrogate function could improve performance potentially. Remark 1 (Comparison with (Kakade & Langford, 2002)). The result (11) develops the classic performance difference (6) at least three aspects. Firstly, the bound (11) extends from the advantage Aπ
θ ′ (6) to GAE function A GAE(γ,λ) π θ ′ . Secondly, the following term in Eq.(11):
(1− γ̃)−1Es∼dλπ θ ′ (·),a∼πθ(·|s)
[ AGAE(γ,λ)π
θ ′ (s, a)
] (14)
is an approximation for the difference J(πθ)− J(πθ′ ), while Eq.(6) shows an identity for difference J(πθ) − J(πθ′ ). Comparison to Eq.(6), the proposed Eq.(14) uses the state distribution dλπ
θ ′ (·)
instead of dρ0πθ (·), which is known the first oder expansion with respect to the policy πθ around the neighborhood around πθ′ (Kakade & Langford, 2002; Achiam et al., 2017). Finally, although Eq.(6) provides an identity for J(πθ)− J(πθ′ ), it never shows an error bound of the first oder expansion for the performance difference J(πθ)− J(πθ′ ), and the proposed bound (11) makes up for such a weakness. Such a bound (11) can be viewed as the worse-case approximation error, which provides a fresh surrogate function for us to design algorithms in the later section.
Let ϕ = V cπ θ ′ , Theorem 1 implies an upper bound of cost function as presented in the next Proposition 2, we will use it to make guarantee for safe policy optimization. Proposition 2. For any two policies πθ and πθ′ , let Cπθ (πθ′ ) =: supt∈N+{ ϕ πθ,t : ϕ = V cπ θ ′ }, then
Jc(πθ)− Jc(πθ′ ) (15)
≤ 1 1− γ̃ Es∼dλπ θ ′ (·),a∼πθ(·|s)
[ A
GAE(γ,λ) π θ ′ ,C (s, a) + 2γ(1− λ) Cπθ (πθ′ ) (1− γλ) |1− 2γλ|S||A|| DTV(πθ′ , πθ)[s]
] ,
where we calculate AGAE(γ,λ)π θ ′ ,C (s, a) according to the data sampled from πθ′ and (5).
All above bound results (11) and (15) can be extended for a total variational divergence to KLdivergence between policies, which are desirable for policy optimization. We obtain
Es∼dλπ θ ′ (·) [DTV(πθ′ , πθ)[s]] ≤Es∼dλπ θ ′ (·)
[√ 1
2 KL(πθ′ , πθ)[s]
] ≤ √ 1
2 Es∼dλπ θ ′ (·) [KL(πθ′ , πθ)[s]],
(16) where KL(·, ·) is KL-divergence, and KL(πθ′ , πθ)[s] = KL(πθ′ (·|s), πθ(·|s)); the first inequality follows Pinsker’s inequality (Csiszár & Körner, 2011) and the second inequality follows Jensen’s inequality. According to (16), we obtain the next Proposition 3. Proposition 3. All the bounds in (11) and (15) hold if we make the following substitution:
Es∼dλπ θ ′ (·)
[DTV(πθ′ , πθ)[s]]← √ 1
2 Es∼dλπ θ ′ (·) [KL(πθ′ , πθ)[s]].

heading: 4 METHODOLOGY: A CONSERVATIVE UPDATE POLICY (CUP)
text: According to the bounds in Proposition 1-3, we develop new surrogate functions to replace the objective and constraints. Inspired by two recent works (Yang et al., 2020; Zhang et al., 2020), we propose the CUP (conservative update policy) algorithm that is a two-step approach contains performance improvement and projection. Theorem 2 proves the proposed CUP guarantees the policy improvement and safe constraints.
Step 1: Performance Improvement. According to Proposition 1 and Proposition 3, for an appropriate coefficient αk, we update policy as follows,
πθ k+1
2 = arg max πθ∈Πθ { Es∼dλπθk (·),a∼πθ(·|s) [ AGAE(γ,λ)πθk (s, a) ] − αk √ Es∼dλπθk (·) [KL(πθk , πθ)[s]] } .
(17) This step is a typical minimization-maximization (MM) algorithm (Hunter & Lange, 2004), it includes return maximization and minimization the distance between old policy and new policy.
Step 2: Projection. According to Proposition 2 and Proposition 3, for an appropriate coefficient βk, we project the policy πθ
k+1 2 onto the safe constraint set. Concretely, we use a measure D(·, ·) (e.g., KL divergence or `2-norm) to minimize distance between πθ
k+1 2 and πθ , and require the new policy satisfies the safe constraint:
πθk+1 = arg min πθ∈Πθ
D ( πθ, πθ
k+1 2
) , (18)
s.t. Jc(πθk) + 1
1− γ̃ Es∼dλπθk (·),a∼πθ(·|s)
[ A
GAE(γ,λ) πθk ,C
(s, a) ] + βk √ Es∼dλπθk (·) [KL(πθk , πθ)[s]] ≤ b.
Until now, the particular choice of surrogate function is heuristically motivated, we show the policy and safe constraint guarantee of the proposed CUP in Theorem 2, and its proof shown in Appendix F.
Theorem 2. Let δk = Es∼dλπθk (·) [ KL ( πθk , πθk+1 2 ) [s] ] , if πθk and πθk+1 are related to (17)-(18), then the lower bound on policy improvement, and upper bound on constraint violation are
J(πθk+1)− J(πθk) ≥ − γ(1− λ)αk
√ 2δk V πθ (πθ′ )
(1− γ) |1− 2γλ|S||A|| , Jc(πθk+1) ≤ b+
γ(1− λ)βk √ 2δk C πθ (πθ′ )
(1− γ) |1− 2γλ|S||A|| .
Remark 2. Let λ→ 0, according to Theorem 2, the performance and cost constraint of CUP satisfies
J(πθk+1)− J(πθk) ≥ − γαk √ 2δk V πθ (πθ′ )
(1− γ) , Jc(πθk+1) ≤ b+
γβk √ 2δk C πθ (πθ′ )
(1− γ) . (19)
The bounds of CUP in (19) achieves at O(αkγ1−γ ) or O( βkγ 1−γ ), which is more compact than the bounds of CPO (Achiam et al., 2017, Proposition 1-2), PCPO (Yang et al., 2020, Theorem 1) and FOCOPS (Zhang et al., 2020) where their bounds achieve at O ( γ
(1−γ)2
) .
Practical Implementation Now, we present our sample-based implementation for CUP (17)-(18). Our main idea is to estimate the objective and constraints in (17)-(18) with samples collected by current policy πθk , then solving its optimization problem via first-order optimizer. Due to the limitation of space, we present pseudo-code of CUP in Algorithm 1 (see Appendix B).
For each {(st, at, rt+1, ct+1)}Tt=1 ∼ πθk , firstly, we update performance improvement step as:
θk+ 12 = arg maxθ
{ 1
T N∑ t=1 πθ(at|st) πθk(at|st) Ât − αk √ D̂KL(πθk , πθ) } , (20)
where Ât is a estimator of A GAE(γ,λ) πθk (s, a), D̂KL(πθk , πθ) = 1 T ∑N t=1 KL(πθk(·|st), πθ(·|st)).
Then we update projection step by replacing the distance function D by KL-divergence, and we use a soft constraint instead of the hard constraint (18),
θk+1 = arg min θ
{ 1
T T∑ t=1 KL ( πθ k+1 2 (at|st), πθ(at|st) ) + βkLc } , (21)
where Lc = ĴC + 11−γ̃ · 1 T ∑T t=1 πθ(at|st) πθk (at|st) ÂCt + αk √ 1 T ∑T t=1 KL(πold(at|st), πθ(at|st)) − b, ĴCand ÂCt are estimators for cost-return and cost-advantage correspondingly.

heading: 5 RELATED WORK
text: This section reviews some typical ways to solve safe reinforcement learning: local policy search, Lagrangian approach, and constrained policy optimization (CPO). We provide more comparisons and discussion in Appendix A and Table 3.
Local Policy Search and Lagrangian Approach. A direct way to solve CMDP (4) is to apply local policy search (Peters & Schaal, 2008; Pirotta et al., 2013) over the policy space ΠC , i.e.,
πθk+1 = arg max πθ∈Πθ
J(πθ), s.t. Jc(πθ) ≤ b, and D(πθ, πθk) < δ, (22)
where δ is a positive scalar, D(·, ·) is some distance measure. For practice, the local policy search (22) is challenging to implement because it requires evaluation of the constraint function c to determine whether a proposed point π is feasible (Zhang et al., 2020). Besides, when updating policy according to samples, local policy search (22) requires off-policy evaluation (Achiam et al., 2017), which is very challenging for high-dimension control problem (Duan et al., 2016; Yang et al., 2018; 2021a). Thus, local policy search (22) looks simple, but it is impractical for high-dimension policy optimization.
The standard way to solve CMDP (4) is Lagrangian approach (Chow et al., 2017; Xu et al., 2021) that is also known as primal-dual policy optimization:
(π?, λ?) = arg min λ≥0 max πθ∈Πθ
{J(πθ)− λ(Jc(πθ)− b)} . (23)
Although extensive canonical algorithms are proposed to solve problem (23), e.g., (Liang et al., 2018; Tessler et al., 2019; Paternain et al., 2019; Le et al., 2019; Russel et al., 2020; Xu et al., 2020; Satija et al., 2020; Chen et al., 2021), the policy updated by Lagrangian approach may be infeasible w.r.t. CMDP (4). This is hazardous in reinforcement learning when one needs to execute the intermediate policy (which may be unsafe) during training (Chow et al., 2018).
Constrained Policy Optimization (CPO). Recently, CPO (Achiam et al., 2017) suggests to replace the cost constraint with a surrogate cost function which evaluates the constraint Jc(πθ) according to the samples collected from the current policy πθk :
πθk+1 = arg max πθ∈Πθ Es∼dρ0πθk (·),a∼πθ(·|s) [ Aπθk (s, a) ] (24)
s.t. Jc(πθk) + 1
1− γ Es∼dρ0πθk (·),a∼πθ(·|s) [ Acπθk (s, a) ] ≤ b, (25)
D̄KL(πθ, πθk) = Es∼dρ0πθk (·) [KL(πθ, πθk)[s]] ≤ δ. (26)
Existing recent works (e.g., (Achiam et al., 2017; Vuong et al., 2019; Yang et al., 2020; Han et al., 2020; Bisi et al., 2020; Bharadhwaj et al., 2021)) try to find some convex approximations to replace the term Aπθk (s, a) and D̄KL(πθ, πθk) Eq.(24)-(26). Such first-order and second-order approximations turn a non-convex problem (24)-(26) to be a convex problem, it seems to make a simple solution, but this approach results in many error sources and troubles in practice. Firstly, it still lacks a theory analysis to show the difference between the non-convex problem (24)-(26) and its convex approximation. Policy optimization is a typical non-convex problem (Yang et al., 2021b); its convex approximation may introduce some error for its original issue. Secondly, CPO updates parameters according to conjugate gradient (Süli & Mayers, 2003), and its solution involves the inverse Fisher information matrix, which requires expensive computation for each update. Later, Yang et al. (2020) propose projected-based constrained policy optimization (PCPO) that also uses second-order approximation, which also results in an expensive computation.
Instead of using a convex approximation for the objective function, the proposed CUP algorithm improves CPO and PCPO at least two aspects. Firstly, the CUP directly optimizes the surrogate objective function via the first-order method, and it does not depend on any convex approximation. Thus, the CUP effectively avoids the expensive computation for the inverse Fisher information matrix. Secondly, CUP extends the surrogate objective function to GAE. Although Zhang et al. (2020) has used the GAE technique in experiments, to the best of our knowledge, it still lacks a rigorous theoretical analysis involved GAE before we propose CUP.

heading: 6 EXPERIMENTS
text: In this section, we show the effectiveness of CUP on three different sets of experiments (including seven tasks): (i) robots with speed limit (Zhang et al., 2020); (ii) circle task (Achiam et al., 2017); (iii) robot options and desiderata (Ray et al., 2019).
For task (i), we train different robotic agents to move along a straight line or a two-dimensional plane, but the robot’s speed is constrained for safety purposes. For task (ii), the agent is rewarded for running in a wide circle but is constrained to stay within a safe region smaller than the radius of the target circle. Task (iii) is safety Gym ships with three pre-made robots that we use in the benchmark environments from (Ray et al., 2019). All of those details are provided in Appendix G.1.
Baseline algorithms. We compare CUP to CPO (Achiam et al., 2017), PCPO (Yang et al., 2020), FOCOPS (Zhang et al., 2020) in the task (i) and task (ii). To make a more comprehensive comparison, we compare CUP with the unconstrained algorithms TRPO (Schulman et al., 2015) and PPO (Schulman et al., 2017), and compare CUP with two additional safe RL algorithms TRPO-Lagrangian and PPO-Lagrangian, that combine the Lagrangian approach with TRPO and PPO.
Robots with Speed Limit and circle task. Table 1 shows that both CUP and FOCOPS consistently enforce approximate constraint satisfaction while CUP has a higher performance than FOCOPS. CUP outperforms CPO and PCPO significantly for both reward and cost. Those observations suggest the projection step of CUP helps the agent to learn the safe constraints. We notice PCPO also has a projection step, CUP performs better than PCPO due to CUP learning the objective and constraints
under a non-convex function while PCPO uses its convex approximation, which is one motivation for us to propose CUP.
Safety Gym Ships with Three Pre-made Robots. We compare the algorithms on three environments SGPoint, SGCar, and SGDoggo, which are all six Point/Car/Doggo robot environments with constraints in Safety Gym. Thus, it is necessary to introduce the rule for comparing the aggregate performance of algorithms across many environments by (Ray et al., 2019), where it assigns each environment E a set of characteristic metrics, J̄Er , J̄Ec , ρ̄Ec and compute normalized return J̄r, normalized constraint violation M̄c, and normalized cost rate ρ̄c:
J̄r = J(πθ)
J̄Er , M̄c = max{0, Jc(πθ)− d} max{10−6, J̄Ec − d} , ρ̄c = ρ̄c ρ̄Ec .
Figure 1 shows the results from benchmarking unconstrained and constrained RL algorithms on all Point level 1 and 2 environments, and the approximately constraint-satisfying training run (CostRate curves). All the cost are shown in [25, 30] In Table 2, we show the normalized metrics from the conclusion of training averaged over various slates of environments and three random seeds per environment. All experiments were run with three random seeds. Results show that cost and rewards trade off happens in SGPoint and SGCar, while CUP achieves the best performance in those two environments. In the SGDoggo environment, CUP achieves the best performance and constraint satisfaction over all the baseline algorithms.

heading: 7 CONCLUSION
text: In this paper, we propose the CUP algorithm with a theoretical safety guarantee. We derive the CUP bases on some new proposed surrogate functions w.r.t. objective and constraints and the practical implementation of CUP does not depend on any convex approximation. Extensive experiments on continuous control tasks show the effectiveness of CUP where the agent satisfies safe constraints.

heading: A ADDITIONAL DISCUSSION ABOUT RELATED WORK
text: This section reviews three typical safe reinforcement learning algorithms: CPO (Achiam et al., 2017), PCPO (Yang et al., 2020) and FOCOPS (Zhang et al., 2020). Those algorithms also use new surrogate functions to replace the objective and constraints, which resembles the proposed CUP algorithm. The goal is to present the contribution of our work.
A.1 CPO (ACHIAM ET AL., 2017)
For a given policy πθk , CPO updates new policy πθk+1 as follows:
πθk+1 = arg max πθ∈Πθ Es∼dρ0πθk (·),a∼πθ(·|s) [ Aπθk (s, a) ] (27)
s.t. Jc(πθk) + 1
1− γ Es∼dρ0πθk (·),a∼πθ(·|s) [ Acπθk (s, a) ] ≤ b, (28)
D̄KL(πθ, πθk) = Es∼dρ0πθk (·) [KL(πθ, πθk)[s]] ≤ δ. (29)
It is impractical to solve the problem (24) directly due to the computational cost. (Achiam et al., 2017) suggest to find some convex approximations to replace the term Aπθk (s, a) and D̄KL(πθ, πθk) Eq.(24)-(26).
Concretely, according to (6), Achiam et al. (2017) suggest to use first-order Taylor expansion of J(πθ) to replace the objective (24) as follows,
1
1− γ Es∼dρ0πθk (·),a∼πθk (·|s) [ πθ(a|s) πθk(a|s) Aπθk (s, a) ] = J(πθ)− J(πθk) ≈ (θ − θk)>∇θJ(πθ).
Similarly, Achiam et al. (2017) use the following approximations to turn the constrained policy optimization (24)-(26) to be a convex problem,
1
1− γ Es∼dρ0πθk (·),a∼πθk (·|s) [ πθ(a|s) πθk(a|s) Acπθk (s, a) ] ≈ (θ − θk)>∇θJc(πθ), (30)
D̄KL(πθ, πθk) ≈ (θ − θk)>H(θ − θk), (31)
where H is Hessian matrix of D̄KL(πθ, πθk), i.e.,
H[i, j] =: ∂2
∂θi∂θj Es∼dρ0πθk (·) [KL(πθ, πθk)[s]] ,
Eq.(31) is the second-oder approximation of (26).
Let λ?, ν? is the dual solution of the following problem
λ?, ν? = arg max λ≥0,ν≥0 { −1 2λ ( g>H−1g − 2νr + sv2 ) + νc− λδ 2 } ;
where g = ∇θEs∼dρ0πθk (·),a∼πθ(·|s) [ Aπθk (s, a) ] , a = ∇θEs∼dρ0πθk (·),a∼πθ(·|s) [ Acπθk (s, a) ] , r = g>Ha, s = a>H−1a, and c = Jc(πθk)− b. Finally, CPO updates parameters according to conjugate gradient as follows: if approximation to CPO is feasible:
θk+1 = θk + 1
λ? H−1(g − ν?a),
else,
θk+1 = θk − √
2δ
a>H−1a H−1a.
A.2 PCPO (YANG ET AL., 2020)
Projection-Based Constrained Policy Optimization (PCPO) is an iterative method for optimizing policies in a two-step process: the first step performs a local reward improvement update, while the second step reconciles any constraint violation by projecting the policy back onto the constraint set.
Reward Improvement:
πθ k+1
2 = arg max πθ∈Πθ Es∼dρ0πθk (·),a∼πθ(·|s) [ Aπθk (s, a) ] ,
s.t.D̄KL(πθ, πθk) = Es∼dρ0πθk (·) [KL(πθ, πθk)[s]] ≤ δ;
Projection:
πθk+1 = arg min πθ∈Πθ
D ( πθ, πθ
k+1 2
) ,
s.t. Jc(πθk) + 1
1− γ Es∼dρ0πθk (·),a∼πθ(·|s) [ Acπθk (s, a) ] ≤ b.
Then, Yang et al. (2020) follows CPO (Achiam et al., 2017) uses convex approximation to original problem, and calculate the update rule as follows,
θk+1 = θk −
√ 2δ
g>H−1g H−1g −max 0, √
2δ
g>H−1g a>H−1g + c
a>L−1a L−1a, where L = I if D is `2-norm, and L = H if D is KL-divergence.

heading: A.3 FOCOPS (ZHANG ET AL., 2020)
text: Zhang et al. (2020) propose the First Order Constrained Optimization in Policy Space (FOCOPS) that is a two-step approach. We present it as follows.
Step1: Finding the optimal update policy. Firstly, for a given policy πθk, we find an optimal update policy π? by solving the optimization problem (27)-(29) in the non-parameterized policy space.
π? = arg max π∈Π Es∼dρ0πθk (·),a∼π(·|s) [ Aπθk (s, a) ] (32)
s.t. Jc(πθk) + 1
1− γ Es∼dρ0πθk (·),a∼π(·|s) [ Acπθk (s, a) ] ≤ b, (33)
D̄KL(πθ, πθk) = Es∼dρ0πθk (·) [KL(π, πθk)[s]] ≤ δ. (34)
If πθk is feasible, then the optimal policy for (32)-(34) takes the following form:
π?(a|s) = πθk(a|s) Zλ,ν(s) exp
( 1
λ
( Aπθk (s, a)− νA c πθk (s, a) )) , (35)
where Zλ,ν(s) is the partition function which ensures (35) is a valid probability distribution, λ and ν are solutions to the optimization problem:
min λ,ν≥0 λν + νb̃+ λEs∼dρ0πθk (·),a∼π?(·|s) [Zλ,ν(s)] ,
the term b̃ = (1− γ)(b− Jc(πθk)). Step 2: Projection Then, we project the policy found in the previous step back into the parameterized policy space Πθ by solving for the closest policy πθ ∈ Πθ to π? in order to obtain πθk+1 :
θk+1 = arg min θ Es∼dρ0πθk (·) [KL(πθ, π?)[s]].

heading: A.4 COMPARISON TO CUP
text: Comparing to CPO and PCPO, the implementation of CUP does not depend on any convex approximations. CPO learns its objective with the deep neural network via the first-order method (see Appendix B).
Concretely, CPO and PCPO approximate the non-convex objective (or constraints) with first-order or second Taylor expansion, but their implementations still lack a theory to show the error difference between the original objective (or constraints) and its convex approximations. Additionally, their approaches involve the inverse of a high-dimension Fisher information matrix, which causes their algorithms to require a costly computation for each update when solving high-dimensional RL problems. While the proposed CUP does not depend on any convex approximations, it learns the policy via first-order optimization approaches. Thus, CUP does not involve the inverse of a high-dimension Fisher information matrix, which implies CUP requires less memory than CPO and PCPO.
Although FOCOPS is also a non-convex implementation, it heavily depends on the current bestsatisfied policy. It is known that the current best policy may not be the optimal policy, and FOCOPS requires to project this policy back into the parametric policy space, which implies FOCOPS reduce the chances for an agent to explore the environment since it may lose in a locally optimal solution. While the proposed CUP does not depend on the current optimal policy, in fact, CUP requires the agent to learn the policy according to (17), the numerical solution is not the current optimal policy, which helps CUP to explore the environment.
Ta bl
e 3:
C om
pa ri
so n
of so
m e
sa fe
re in
fo rc
em en
ta lg
or ith
m s.
A lg
or ith
m O
pt im
iz at
io n
pr ob
le m
Im pl
em en
ta tio
n R
em ar
k
C PO
(A ch
ia m
et al
., 20
17 )
π θ k +
1 =
a rg
m a x π θ ∈
Π θ E s ∼ d ρ 0 π θ k
(· ), a ∼ π θ
(· |s
)
[ A π θ k
(s ,a )] , s. t. J c (π θ k ) + E s ∼ d ρ 0 π θ k (· ), a ∼ π θ (· |s ) [ Ac π θ k (s ,a )] ≤ b, D̄ K L (π θ ,π θ k ) = E s ∼ d ρ 0 π θ k (· ) [K L (π θ ,π θ k )[ s] ] ≤ δ.
θ k +
1 =
a rg
m a x θ g >
(θ −
θ k ),
s. t. c
+ b >
(θ −
θ k ) ≤
0 ,
1 2 (θ −
θ k )>
H (θ −
θ k ) ≤ δ.
C on
ve x
Im pl
em en
ta tio
n
PC PO
(Y an
g et
al .,
20 20
)
R ew
ar d
Im pr
ov em
en t
π θ k +
1 2
= a rg
m a x π θ ∈
Π θ E s ∼ d ρ 0 π θ k
(· ), a ∼ π θ
(· |s
)
[ A π θ k
(s ,a )] , s. t. D̄ K L (π θ ,π θ k ) = E s ∼ d ρ 0 π θ k (· ) [K L (π θ ,π θ k )[ s] ] ≤ δ; Pr oj ec tio n π θ k + 1 = a rg m in π θ ∈ Π θ D ( π θ ,π θ k + 1 2 ) , s. t. J c (π θ k ) + 1 1 − γ E s ∼ d ρ 0 π θ k (· ), a ∼ π θ (· |s ) [ Ac π θ k (s ,a )] ≤ b.
R ew
ar d
Im pr
ov em
en t
θ k +
1 2 =
a rg
m a x θ g >
(θ −
θ k ),
s. t.
1 2 (θ −
θ k )>
H (θ −
θ k ) ≤ δ;
Pr oj
ec tio
n
π θ k +
1 =
a rg
m in
θ 1 2
(θ −
θ k )>
L (θ −
θ k ),
s. t. c
+ b >
(θ −
θ k ) ≤
0 .
C on
ve x
Im pl
em en
ta tio
n
FO C
O PS
(Z ha
ng et
al .,
20 20
)
O pt
im al
up da
te po
lic y
π ?
= a rg
m a x π ∈
Π E s ∼ d ρ 0 π θ k
(· ), a ∼ π
(· |s
)
[ A π θ k
(s ,a )] , s. t. J c (π θ k ) + E s ∼ d ρ 0 π θ k (· ), a ∼ π (· |s ) [ Ac π θ k (s ,a )] ≤ b, D̄ K L (π θ ,π θ k ) = E s ∼ d ρ 0 π θ k (· ) [K L (π ,π θ k )[ s] ] ≤ δ; Pr oj ec tio n π θ k + 1 = a rg m in π θ ∈ Π θ E s ∼ d ρ 0 π θ k (· ) [K L (π θ ,π ? )[ s] ].
O pt
im al
up da
te po
lic y
π ? (a |s
) =
π θ k
(a |s
)
Z λ ,ν
(s )
ex p ( 1 λ(
A π θ k
(s ,a
) − ν A c π θ k
(s ,a ))) ; Pr oj ec tio n
θ k +
1 =
a rg
m in
θ E s ∼ d ρ 0 π θ k
(· ) [K
L (π
θ ,π ? )[ s]
].
N on
-C on
ve x
Im pl
em en - ta tio n
C U P (O ur W
or k)
Po lic
y Im
pr ov
em en
t
π θ k +
1 2
= a rg
m a x
π θ ∈
Π θ
{ E s∼ d λ π θ k
(· ), a ∼ π θ
(· |s
)
[ AGA E (γ ,λ ) π θ k
(s ,a )] − α k √ E s ∼ d λ π θ k (· ) [K L (π θ k ,π θ )[ s] ]} , Pr oj ec tio n
π θ k +
1 =
a rg
m in
π θ ∈
Π θ
D ( π θ,
π θ k +
1 2 ) , s. t.J c (π θ k ) + 1 1 − γ̃ E s ∼ d λ π θ k (· ), a ∼ π θ (· |s ) [ AGA E (γ ,λ ) π θ k ,C
(s ,a )] + β k √ E s ∼ d λ π θ k (· ) [K L (π θ k ,π θ )[ s] ] ≤ b.
Po lic
y Im
pr ov
em en
t
θ k +
1 2 =
a rg
m a x θ
{ 1 T T ∑ t=1
π θ (a t |s t ) π θ k (a t |s t ) Â t
− α
√ √ √ √1 T T ∑ t=1K
L (π
θ k (· |s t ), π θ (· |s t )) } ; Pr oj ec tio n
θ k +
1 =
a rg
m in θ
1 T
T ∑ t=1{ K
L ( π θ k
+ 1 2
(· |s t ), π θ (· |s t ))
+ ν k
1 − γ λ 1 − γ
π θ (a t |s t ) π θ k (a t |s t ) Â C t
} .
N on
-C on
ve x
Im pl
em en - ta tio n

heading: B CONSERVATIVE POLICY UPDATE (CPU) ALGORITHM
text: Algorithm 1 Conservative Policy Update (CPU) Initialize: policy network parameters θ0; value network parameter ω0; cost value function parameter ν0, step-size ν0; Hyper-parameters: trajectory horizon T ; discount rate γ; episode number M,N , mini-batch size B, positive constant α, η; for k = 0, 1, 2, . . . do
Collect batch data ofM episodes of horizon T in∪Mi=1∪Tt=0{(si,t, ai,t, ri,t+1, ci,t+1)} according to current policy πθk ; Estimate c-return by discount averaging on each episode: ĴCi = ∑T t=0 γ
tci,t+1; Compute TD errors ∪Mi=1 ∪Tt=0 {δi,t}, cost TD errors ∪Mi=1 ∪Tt=0 {δCi,t}:
δi,t = ri,t + γVωk(si,t)− Vωk(si,t−1), δCi,t = ci,t + γV Cνk(si,t)− V C νk (si,t−1);
Compute GAE: ∪Mi=1 ∪Tt=0 {Âi,t, ÂCi,t}: Âi,t = ∑T j=t(γλ) j−tδi,j , Â C i,t = ∑T j=t(γλ)
j−tδCi,j ; Compute target function for value function and cost value function as follows,
V targeti,t = Âi,t + Vωk(si,t), V target,C i,t = Â C i,t + V C νk (si,t);
Store data: Dk = ∪Mi=1 ∪Tt=0 { (ai,t, si,t, Âi,t, Â C i,t, V target i,t , V target,C i,t ) } ; πold ← πθk ; Policy Improvement for i = 0, 1, 2, . . . ,M do
θk+ 12 = arg maxθ  1T T∑ t=1 πθ(ai,t|si,t) πold(ai,t|si,t) Âi,t − α √√√√ 1 T T∑ t=1 KL(πold(·|si,t), πθ(·|si,t))  ; end for πold ← πθ
k+1 2
; Projection
νk+1 = (νk + η(Ĵ C i − b))+; for i = 0, 1, 2, . . . ,M do
θk+1 = arg min θ
1
T T∑ t=1 { KL(πθold(·|si,t), πθ(·|si,t)) + νk 1− γλ 1− γ πθ(ai,t|si,t) πθk(ai,t|si,t) ÂCi,t } ;
end for for each mini-batch {(aj , sj , Âj , ÂCj , V target j , V target,C j )} of size B from Dk do
ωk+1 = arg min ω B∑ j=1 ( Vω(sj)− V targetj )2 ,νk+1 = arg min ν B∑ j=1 ( V cν (sj)− V target,C j )2 ;
end for end for

heading: B.1 PRACTICAL IMPLEMENTATION OF CUP
text: In this section, we present the practical implementation of CUP.
Step 1: Policy Improvement
For the first step,
πθ k+1
2 = arg max πθ∈Πθ { Es∼dλπθk (·),a∼πθ(·|s) [ AGAE(γ,λ)πθk (s, a) ] − αk √ Es∼dλπθk (·) [KL(πθk , πθ)[s]] } ,
according to
Es∼dλπθk (·),a∼πθ(·|s) [ AGAE(γ,λ)πθk (s, a) ] = Es∼dλπθk (·),a∼πθk (·|s) [ πθ(a|s) πθk(a|s) AGAE(γ,λ)πθk (s, a) ] , (36)
for each data sampled from ∪Mi=1 ∪Tt=0 {(si,t, ai,t, ri,t+1, ci,t+1)} according to current policy πθk , we learn the parameter θk+ 12 as follows,
θk+ 12 = arg maxθ  1T T∑ t=1 πθ(ai,t|si,t) πθk(ai,t|si,t) Âi,t − α √√√√ 1 T T∑ t=1 KL(πθk(·|si,t), πθ(·|si,t))  , which can be solved via the first order optimizer.
Step 2: Projection
Now, consider the second step:
πθk+1 = arg min πθ∈Πθ
D ( πθ, πθ
k+1 2
) ,
s.t. Jc(πθk) + 1
1− γ̃ Es∼dλπθk (·),a∼πθ(·|s)
[ A
GAE(γ,λ) πθk ,C
(s, a) ] + βk √ Es∼dλπθk (·) [KL(πθk , πθ)[s]] ≤ b.
We turn the projection step as the following unconstrained problem:
min θ,ν≥0
{ D ( πθ, πθ
k+1 2
) + ν ( Jc(πθk)+ 1
1− γ̃ Es∼dλπθk (·),a∼πθ(·|s)
[ A
GAE(γ,λ) πθk ,C
(s, a) ]
+βk √ Es∼dλπθk (·) [KL(πθk , πθ)[s]]− b
)} . (37)
In our implementation, we use KL-divergence as the distance measure D(·, ·), then D ( πθ, πθ
k+1 2 ) = Es∼dλπθk (·) [ KL ( πθ k+1 2 , πθ ) [s] ] . (38)
To simplify the problem, we ignore the term βk √ Es∼dλπθk (·) [KL(πθk , πθ)[s]] due to the following two aspects: (i) firstly, βk is adapted to the term γ(1−λ) √ 2δk C πθk+1 (πθk )
(1−γλ)|1−2γλ|S||A|| , and for the highdimensional state space or continuous action space, then βk is very small; (ii) secondly, if D is a KL-divergence measure, then the direction of the policy optimization D ( πθ, πθ
k+1 2
) (38) is pro-
portional to βk √ Es∼dλπθk (·) [KL(πθk , πθ)[s]], thus, in practice, we can only optimize the distance
D ( πθ, πθ
k+1 2
) . Above discussions implies that instead of (37), we can consider the problem
min θ,ν≥0
L(θ, ν),
where L(θ, ν) = D ( πθ, πθ
k+1 2
) + ν ( Jc(πθk) + 1
1− γ̃ Es∼dλπθk (·),a∼πθ(·|s)
[ A
GAE(γ,λ) πθk ,C
(s, a) ] − b ) .
Then, according to gradient decent method, we have
θ ← θ − ηL(θ, ν) ∂θ , ν ← ν − ηL(θ, ν) ∂ν . (39)
Particularly,
L(θ, ν) ∂ν = Jc(πθk) + 1 1− γ̃ Es∼dλπθk (·),a∼πθ(·|s)
[ A
GAE(γ,λ) πθk ,C
(s, a) ] − b, (40)
where the term Es∼dλπθk (·),a∼πθ(·|s) [ A GAE(γ,λ) πθk ,C (s, a) ] can be estimated following the idea as (36). But recall (17) is a MM-iteration, i.e., we require to minimize Es∼dλπθk (·) KL (πθ, πθk) [s], which
implies πθ is close to πθk . Thus it is reasonable Es∼dλπθk (·),a∼πθ(·|s) [ A GAE(γ,λ) πθk ,C (s, a) ] ≈ 0, thus, in practice, we update ν following a simple way
ν ← (ν − η(Jc(πθk)− b))+,
where (·)+ denote the positive part, i.e., if x ≤ 0, (x)+ = 0, else (x)+ = x. Finally, according to (39), for each data sampled from ∪Mi=1∪Tt=0{(si,t, ai,t, ri,t+1, ci,t+1)} according to current policy πθk , we learn the parameter θk+1 as follows,
θk+1 = arg min θ
1
T T∑ t=1 { KL ( πθ k+1 2 (·|si,t), πθ(·|si,t) ) + νk 1− γλ 1− γ πθ(ai,t|si,t) πθk(ai,t|si,t) ÂCi,t } ,
which can be solved via the first-order optimizer.

heading: C NOTATIONS

heading: C.1 MATRIX INDEX
text: In this paper, we use a bold capital letter to denote matrix, e.g., A = (ai,j) ∈ Rm×n, and its (i, j)-th element denoted as
A[i, j] =: ai,j ,
where 1 ≤ i ≤ m, 1 ≤ j ≤ n. Similarly, a bold lowercase letter denotes a vector, e.g., a = (a1, a2, · · · , an) ∈ Rn, and its i-th element denoted as
a[i] =: ai,
where 1 ≤ i ≤ n.

heading: C.2 KEY NOTATIONS OF REINFORCEMENT LEARNING
text: For convenience of reference, we list key notations that have be used in this paper.
C.2.1 VALUE FUNCTION AND DYNAMIC SYSTEM OF MDP.
rπθ , Rπθ (s), : rπθ ∈ R|S| is the expected vector reward according to πθ , i.e., their components are: rπθ [s] = ∑ a∈A ∑ s′∈S πθ(a|s)r(s′|s, a) =: Rπθ (s), s ∈ S. vπθ , Vπθ (s), : vπθ ∈ R|S| is the vector that stores all the state value functions, and its components are: vπθ [s] = Vπθ (s), s ∈ S.
ρ(·),ρ : ρ(s): the initial state distribution of state s; ρ ∈ R|S|, and ρ[s] = ρ(s). Pπθ : Single-step state transition matrix by executing πθ.
Pπθ (s ′ |s) : Single-step state transition probability from s to s′ by executing πθ, and it
is the (s, s ′ )-th component of the matrix Pπθ , i.e., Pπθ [s, s ′ ] = Pπθ (s ′ |s). Pπθ (st = s
′ |s) : The probability of visiting the state s′ after t time steps from the state s by executing πθ, and it is the (s, s ′ )-th component of the matrix Pπθ , i.e.,
Ptπθ [s, s ′ ] = Pπθ (st = s ′ |s). ds0πθ (s), d ρ0 πθ
(s) : The normalized discounted distribution of the future state s encountered starting at s0 by executing πθ: ds0πθ (s) =: (1− γ) ∑∞ t=0 γ
tPπθ (st = s|s0). Since s0 ∼ ρ(·), we define dρ0πθ (s) =: Es0∼ρ(·)[d s0 πθ
(s)]. dρ0πθ : It stores all the normalized discounted state distributions d ρ0 πθ
(s), ∈ S, i.e., dρ0πθ ∈ R |S|, and its components are: dρ0πθ [s] = d ρ0 πθ (s).
C.2.2 EXTEND THEM TO λ-VERSION.
P (λ) πθ : P (λ) πθ = (1− γλ) ∑∞ t=0(γλ) tPt+1πθ .
P(λ)πθ (s ′ |s) : P(λ)πθ (s ′ |s) =: P(λ)πθ [s, s ′ ] = (1− γλ) ∑∞ t=0(γλ) tPπθ (st+1 = s ′ |s).
r (λ) πθ , R (λ) πθ (s) : r (λ) πθ = ∑∞ t=0(γλPπθ ) trπθ ; R (λ) πθ (s) =: r (λ) πθ [s].
γ̃ : γ̃ = γ(1− λ) 1− γλ .
ds0,λπθ (s) : d s0,λ πθ (s) = (1− γ̃) ∑∞ t=0 γ̃
tP(λ)πθ (st = s|s0). dλπθ (s), d λ πθ : dλπθ (s) = Es0∼ρ0(·) [ ds0,λπθ (s) ] , dλπθ [s] = d λ πθ (s).
C.2.3 TD ERROR W.R.T. ANY FUNCTION ϕ(·).
δϕt : δ ϕ t = r(st+1|st, at) + γϕ(st+1)− ϕ(st).
δϕπθ,t(s) : δ ϕ πθ,t (s) = Est∼Pπθ (·|s),at∼πθ(·|st),st+1∼P(·|st,at) [δ ϕ t ].
δϕπθ,t : δ ϕ πθ,t [s] = δϕπθ,t(s).
∆ϕt (πθ, πθ′ , s) : Est∼Pπ θ ′ (·|s),at∼πθ′ (·|st),st+1∼P(·|st,at) [( πθ(at|st) πθ′ (at|st) − 1 ) δϕt ] .
∆ϕt (πθ, πθ′ ) : ∆ ϕ t (πθ, πθ′ )[s] = ∆ ϕ t (πθ, πθ′ , s).

heading: D PRELIMINARIES
text: In this section, we introduce some new notations about state distribution, policy optimization and λ-returns.

heading: D.1 STATE DISTRIBUTION
text: We use Pπθ ∈ R|S|×|S| to denote the state transition matrix by executing πθ, and their components are:
Pπθ [s, s ′] = ∑ a∈A πθ(a|s)P(s′|s, a) =: Pπθ (s ′ |s), s, s ′ ∈ S,
which denotes one-step state transformation probability from s to s ′ .
We use Pπθ (st = s|s0) to denote the probability of visiting s after t time steps from the initial state s0 by executing πθ. Particularly, we notice if t = 0, st 6= s0, then Pπθ (st = s|s0) = 0, i.e.,
Pπθ (st = s|s0) = 0, t = 0 and s 6= s0. (41) Then for any initial state s0 ∼ ρ(·), the following holds,
Pπθ (st = s|s0) = ∑ s′∈S Pπθ (st = s|st−1 = s ′ )Pπθ (st−1 = s ′ |s0). (42)
Recall ds0πθ (s) denotes the normalized discounted distribution of the future state s encountered starting at s0 by executing πθ,
ds0πθ (s) = (1− γ) ∞∑ t=0 γtPπθ (st = s|s0).
Furthermore, since s0 ∼ ρ0(·), we define
dρ0πθ (s) = Es0∼ρ0(·)[d s0 πθ (s)] = ∫ s0∈S ρ0(s0)d s0 πθ (s)ds0
as the discounted state visitation distribution over the initial distribution ρ0(·). We use dρ0πθ ∈ R |S| to store all the normalized discounted state distributions, and its components are:
dρ0πθ [s] = d ρ0 πθ (s), s ∈ S.
We use ρ0 ∈ R|S| to denote initial state distribution vector, and their components are: ρ0[s] = ρ0(s), s ∈ S.
Then, we rewrite dρ0πθ as the following matrix version,
dρ0πθ = (1− γ) ∞∑ t=0 (γPπθ ) tρ0 = (1− γ)(I− γPπθ )−1ρ0. (43)

heading: D.2 OBJECTIVE OF MDP
text: Recall τ = {st, at, rt+1}t≥0 ∼ πθ, according to τ , we define the expected return J(πθ|s0) as follows,
J(πθ|s0) =Eτ∼πθ [R(τ)] = 1
1− γ Es∼ds0πθ (·),a∼πθ(·|s),s′∼P(·|s,a)
[ r(s ′ |s, a) ] , (44)
where R(τ) = ∑ t≥0 γ
trt+1, and the notation J(πθ|s0) is “conditional” on s0 is to emphasize the trajectory τ starting from s0.
Since s0 ∼ ρ0(·), we define the objective of MDP as follows,
J(πθ) = 1
1− γ Es∼dρ0πθ (·),a∼πθ(·|s),s′∼P(·|s,a)
[ r(s ′ |s, a) ] . (45)
The goal of reinforcement learning is to solve the following optimization problem:
θ? = arg max θ∈Rp J(πθ). (46)

heading: D.3 BELLMAN OPERATORN
text: Let Bπθ be the Bellman operator:
Bπθ : R|S| → R|S|, v 7→ rπθ + γPπθv, (47)
where rπθ ∈ R|S| is the expected reward according to πθ, i.e., their components are:
rπθ [s] = ∑ a∈A ∑ s′∈S πθ(a|s)r(s′|s, a) =: Rπθ (s), s ∈ S.
Let vπθ ∈ R|S| be a vector that stores all the state value functions, and its components are:
vπθ [s] = Vπθ (s), s ∈ S.
Then, according to Bellman operator (47), we rewrite Bellman equation (Bellman, 1957) as the following matrix version:
Bπθvπθ = vπθ . (48)
Furthermore, we define λ-Bellman operator Bλπθ as follows,
Bλπθ = (1− λ) ∞∑ t=0 λt(Bπθ )t+1,
which implies
Bλπθ : R |S| → R|S|, v 7→ r(λ)πθ + γ̃P (λ) πθ v, (49)
where
P(λ)πθ = (1− γλ) ∞∑ t=0 (γλ)tPt+1πθ , r (λ) πθ = ∞∑ t=0 (γλPπθ ) trπθ , γ̃ = γ(1− λ) 1− γλ . (50)
Let
P(λ)πθ (s ′ |s) = P(λ)πθ [s, s ′ ] =: (1− γλ) ∞∑ t=0 (γλ)t ( Pt+1πθ [s, s ′ ] ) , (51)
where Pt+1πθ [s, s ′ ] is the (s, s ′ )-th component of matrix Pt+1πθ , which is the probability of visiting s ′ after t+ 1 time steps from the state s by executing πθ, i.e.,
Pt+1πθ [s, s ′ ] = Pπθ (st+1 = s ′ |s). (52)
Thus, we rewrite P(λ)πθ (s ′ |s) (51) as follows
P(λ)πθ (s ′ |s) = (1− γλ) ∞∑ t=0 (γλ)tPπθ (st+1 = s ′ |s), s ∈ S. (53)
D.4 λ-RETURN
Furthermore, recall the following visitation sequence τ = {st, at, rt+1}t≥0 induced by πθ, it is similar to the probability Pπθ (st = s ′ |s0), we introduce P(λ)πθ (st = s ′ |s0) as the probability of transition from state s to state s ′ after t time steps under the dynamic transformation matrix P(λ)πθ . Then, the following equity holds
P(λ)πθ (st = s|s0) = ∑ s′∈S P(λ)πθ (st = s|st−1 = s ′ )P(λ)πθ (st−1 = s ′ |s0). (54)
Similarly, let
R(λ)πθ (s) =: r (λ) πθ [s] = ∞∑ t=0 (γλPπθ ) trπθ [s] = ∞∑ t=0 (γλ)t ∑ s′∈S Pπθ (st = s ′ |s)Rπθ (s ′ )  =
∞∑ t=0 ∑ s′∈S (γλ)tPπθ (st = s ′ |s)Rπθ (s ′ ). (55)
It is similar to normalized discounted distribution dρ0πθ (s), we introduce λ-return version of discounted state distribution dλπθ (s) as follows: ∀s ∈ S,
ds0,λπθ (s) = (1− γ̃) ∞∑ t=0 γ̃tP(λ)πθ (st = s|s0), (56)
dλπθ (s) = Es0∼ρ0(·) [ ds0,λπθ (s) ] , (57) dλπθ [s] = d λ πθ (s), (58)
where P(λ)πθ (st = s|s0) is the (s0, s)-th component of the matrix ( P (λ) πθ )t , i.e.,
P(λ)πθ (st = s|s0) =: ( P(λ)πθ )t [s0, s].
Similarly, P(λ)πθ (st = s ′ |s) is the (s, s′)-th component of the matrix ( P (λ) πθ )t , i.e.,
P(λ)πθ (st = s ′ |s) =: ( P(λ)πθ )t [s, s ′ ].
Finally, we rewrite dρ0,λπθ as the following matrix version,
dλπθ = (1− γ̃) ∞∑ t=0 ( γP(λ)πθ )t ρ0 = (1− γ̃) ( I− γ̃P(λ)πθ )−1 ρ0. (59)
Remark 3 (λ-Return Version of Bellman Equation). According to Bellman equation (48), vπθ is fixed point of λ-operator Bλπθ , i.e.,
vπθ = r (λ) πθ + γ̃P(λ)πθ vπθ . (60)
Recall τ = {st, at, rt+1}t≥0 ∼ πθ, according to (60), the value function of initial state s0 is
Vπθ (s0) = vπθ [s0] = r (λ) πθ [s0] + γ̃P (λ) πθ vπθ [s0] = R(λ)πθ (s0) + γ̃ ∑ s′∈S P(λ)πθ (s1 = s ′ |s0)Vπθ (s ′ ). (61)
We unroll the expression of (61) repeatedly, then we have
Vπθ (s0)
=R(λ)πθ (s0) + γ̃ ∑ s′∈S P(λ)πθ (s1 = s ′ |s0) R(λ)πθ (s′) + γ̃ ∑ s′′∈S P(λ)πθ (s2 = s ′′ |s1 = s ′ )Vπθ (s ′′ )  ︸ ︷︷ ︸
=Vπθ (s ′ ) =R(λ)πθ (s0) + γ̃ ∑ s′∈S P(λ)πθ (s1 = s ′ |s0)R(λ)πθ (s ′ )
+ γ̃2 ∑ s′′∈S ∑ s′∈S P(λ)πθ (s1 = s ′ |s0)P(λ)πθ (s2 = s ′′ |s1 = s ′ )  ︸ ︷︷ ︸
(54) = :P(λ)πθ (s2=s ′′ |s0)
Vπθ (s ′′ )
=R(λ)πθ (s0) + γ̃ ∑ s∈S P(λ)πθ (s1 = s|s0)R (λ) πθ (s) + γ̃2 ∑ s∈S P(λ)πθ (s2 = s|s0)Vπθ (s)
=R(λ)πθ (s0) + γ̃ ∑ s∈S P(λ)πθ (s1 = s|s0)R (λ) πθ (s)
+ γ̃2 ∑ s∈S P(λ)πθ (s2 = s|s0) R(λ)πθ (s) + γ̃ ∑ s′∈S P(λ)πθ (s3 = s ′ |s2 = s)Vπθ (s ′ )  =R(λ)πθ (s0) + γ̃
∑ s∈S P(λ)πθ (s1 = s|s0)R (λ) πθ (s) + γ̃2 ∑ s∈S P(λ)πθ (s2 = s|s0)R (λ) πθ (s)
+ γ̃3 ∑ s′∈S (∑ s∈S P(λ)πθ (s2 = s|s0)P (λ) πθ (s3 = s ′ |s2 = s) ) ︸ ︷︷ ︸
=P(λ)πθ (s3=s ′ |s0)
Vπθ (s ′ )
=R(λ)(s0) + γ̃ ∑ s∈S P(λ)πθ (s1 = s|s0)R (λ) πθ (s) + γ̃2 ∑ s∈S P(λ)πθ (s2 = s|s0)R (λ) πθ (s)
+ γ̃3 ∑ s∈S P(λ)πθ (s3 = s|s0)Vπθ (s)
= · · ·
= ∑ s∈S ∞∑ t=0 γ̃tP(λ)πθ (st = s|s0)R (λ) πθ (s) (56) = 1 1− γ̃ ∑ s∈S ds0,λπθ (s)R (λ) πθ (s). (62)
According to (44) and (62), we have
J(πθ) = ∑ s0∈S ρ0(s0)Vπθ (s0) (62) = 1 1− γ̃ ∑ s0∈S ρ0(s0) ∑ s∈S ds0,λπθ (s)R (λ) πθ (s)
= 1 1− γ̃ ∑ s∈S (∑ s0∈S ρ0(s0)d s0,λ πθ (s) ) ︸ ︷︷ ︸
=dλπθ (s)
R(λ)πθ (s)
= 1 1− γ̃ ∑ s∈S dλπθ (s)R (λ) πθ (s) = 1 1− γ̃ Es∼dλπθ (·) [ R(λ)πθ (s) ] . (63)
Finally, we summarize above results in the following Lemma 1.
Lemma 1. The objective J(πθ) (45) can be rewritten as the following version:
J(πθ) = 1 1− γ̃ ∑ s∈S dλπθ (s)R (λ) πθ (s) = 1 1− γ̃ Es∼dλπθ (·) [ R(λ)πθ (s) ] .

heading: E PROOF OF THEOREM 1
text: We need the following Proposition 4 to prove Theorem 1, which illustrates an identity for the objective function of policy optimization. Proposition 4. For any function ϕ(·) : S → R, for any policy πθ, for any trajectory satisfies τ = {st, at, rt+1}t≥0 ∼ πθ, let
δϕt = r(st+1|st, at) + γϕ(st+1)− ϕ(st), δϕπθ,t(s) = Est∼Pπθ (·|s),at∼πθ(·|st),st+1∼P(·|st,at) [δ ϕ t ] ,
then, the objective J(πθ) (63) can be rewritten as the following version:
J(πθ) =Es0∼ρ0(·)[ϕ(s0)] + 1 1− γ̃ ∑ s∈S dλπθ (s) ( ∞∑ t=0 γtλtδϕπθ,t(s) ) (64)
=Es0∼ρ0(·)[ϕ(s0)] + 1
1− γ̃ Es∼dλπθ (·) [ ∞∑ t=0 γtλtδϕπθ,t(s) ] .
We present the proof of of Proposition 4 at the end of this section, see Section E.2.
We introduce a vector δϕπθ,t ∈ R |S| and its components are: for any s ∈ S
δϕπθ,t[s] = δ ϕ πθ,t (s). (65)
Then, we rewrite the objective as the following vector version
J(πθ) = Es0∼ρ0(·)[ϕ(s0)] + 1
1− γ̃ ∞∑ t=0 γtλt〈dλπθ , δ ϕ πθ,t 〉, (66)
where 〈·, ·〉 denotes inner production between two vectors.

heading: E.1 PROOF OF THEOREM 1
text: Theorem 1 (Generalized Policy Performance Difference) For any function ϕ(·) : S → R, for two arbitrary policy πθ and πθ′ , for any p, q ∈ [1,∞) such that 1p + 1 q = 1, The following bound holds:
1
1− γ̃ ∞∑ t=0 γtλtMϕ,−p,q,t(πθ, πθ′ ) ≤ J(πθ)− J(πθ′ ) ≤ 1 1− γ̃ ∞∑ t=0 γtλtMϕ,+p,q,t(πθ, πθ′ ), (67)
where the terms Mϕ,−p,q,t and M ϕ,+ p,q,t are defined in (83)-(84).
Proof. (of Theorem 1)
We consider two arbitrary policies πθ and πθ′ with different parameters θ and θ ′ , let
D ϕ,(λ) t (πθ, πθ′ ) =: 〈d λ πθ , δϕπθ,t〉 − 〈d λ π θ ′ , δ ϕ π θ ′ ,t〉. (68)
According to (66), we obtain performance difference as follows,
J(πθ)− J(πθ′ ) = 1
1− γ̃ ∞∑ t=0 γtλt ( 〈dλπθ , δ ϕ πθ,t 〉 − 〈dλπ θ ′ , δ ϕ π θ ′ ,t〉 )
= 1
1− γ̃ ∞∑ t=0 γtλtD ϕ,(λ) t (πθ, πθ′ ), (69)
which requires us to consider the boundedness of the difference Dϕ,(λ)t (πθ, πθ′ ) (68) .
Step 1: Bound the term Dϕ,(λ)t (πθ, πθ′ ) (68).
We rewrite the first term of (68) as follows,
〈dλπθ , δ ϕ πθ,t 〉 = 〈dλπ
θ ′ , δ
ϕ πθ,t 〉+ 〈dλπθ − d λ π θ ′ , δ ϕ πθ,t 〉, (70)
which is bounded by applying Hölder’s inequality to the term 〈dλπθ − d λ π θ ′ , δ ϕ πθ,t 〉, we rewrite (70) as follows,
〈dλπ θ ′ , δ ϕ πθ,t 〉 − ‖dλπθ − d λ π θ ′ ‖p‖δ ϕ πθ,t ‖q
≤〈dλπθ , δ ϕ πθ,t 〉 ≤ 〈dλπ
θ ′ , δ
ϕ πθ,t 〉+ ‖dλπθ − d λ π θ ′ ‖p‖δ ϕ πθ,t ‖q, (71)
where p, q ∈ [1,∞) and 1p + 1 q = 1. Let
ϕ,(λ) p,q,t (πθ, πθ′ ) =: ‖d λ πθ − dλπ θ ′ ‖p‖δ ϕ πθ,t ‖q,
then we rewrite Eq.(71) as follows,
〈dλπ θ ′ , δ ϕ πθ,t 〉 − ϕ,(λ)p,q,t (πθ, πθ′ ) ≤ 〈d λ πθ , δϕπθ,t〉 ≤ 〈d λ π θ ′ , δ ϕ πθ,t 〉+ ϕ,(λ)p,q,t (πθ, πθ′ ). (72)
Let
Mϕt (πθ, πθ′ ) =: 〈d λ π θ ′ , δ ϕ πθ,t 〉︸ ︷︷ ︸
Term-I
−〈dλπ θ ′ , δ ϕ π θ ′ ,t〉︸ ︷︷ ︸
Term-II
, (73)
combining the (68) and (72), we achieve the boundedness of Dϕt (πθ, πθ′ ) as follows
Mϕt (πθ, πθ′ )− ϕ,(λ) p,q,t (πθ, πθ′ ) ≤ D ϕ t (πθ, πθ′ ) ≤M ϕ t (πθ, πθ′ ) + ϕ,(λ) p,q,t (πθ, πθ′ ). (74)
Step 2: Analyze the term Mϕt (πθ, πθ′ ) (73).
To analyze (74) further, we need to consider the first term appears in Mϕt (πθ, πθ′ ) (73):
Term-I (73) =〈dλπ θ ′ , δ ϕ πθ,t 〉 = ∑ s∈S dλπ θ ′ (s)δ ϕ πθ,t (s) = Es∼dλπ θ ′ (·) [ δϕπθ,t(s) ] (75)
(65) = Es∼dλπ
θ ′ (·)
[ Est∼Pπθ (·|s)[δ ϕ πθ (st)] ] . (76)
We notice the following relationship
δϕπθ,t(s) = Est∼Pπθ (·|s) at∼πθ(·|st)
st+1∼P(·|st,at)
[δϕt ] = E st∼Pπ
θ ′ (·|s)
at∼πθ′ (·|st) st+1∼P(·|st,at)
[ πθ(at|st) πθ′ (at|st) δϕt ] , (77)
which holds since we use importance sampling: for any distribution p(·) and q(·), for any random variable function f(·), Ex∼p(x)[f(x)] = Ex∼q(x) [ p(x)
q(x) f(x)
] .
According to (75), (77), we rewrite the term 〈dλπ θ ′ , δ ϕ πθ,t 〉 in Eq.(73) as follows,
Term-I (73) = 〈dλπ θ ′ , δ ϕ πθ,t 〉 = ∑ s∈S dλπ θ ′ (s)  Est∼Pπθ′ (·|s) at∼πθ′ (·|st) st+1∼P(·|st,at) [ πθ(at|st) πθ′ (at|st) δϕt ]  . (78)
Now, we consider the second term appears in Mϕt (πθ, πθ′ ) (73):
Term-II (73) = 〈dλπ θ ′ , δ ϕ π θ ′ ,t〉
= ∑ s∈S dλπ θ ′ (s)δ ϕ π θ ′ ,t(s) = ∑ s∈S dλπ θ ′ (s)  Est∼Pπθ′ (·|s) at∼πθ′ (·|st) st+1∼P(·|st,at) [δϕt ]  . (79)
Finally, take the results (78) and (79) to (73), we obtain the difference between 〈dλπ θ ′ , δ ϕ πθ,t 〉 and 〈dλπ θ ′ , δ ϕ π θ ′ ,t〉, i.e., we achieve a identity for M ϕ t (πθ, πθ′ ) (73) as follows,
Mϕt (πθ, πθ′ ) (73) = 〈dλπ
θ ′ , δ
ϕ πθ,t 〉 − 〈dλπ
θ ′ , δ ϕ π θ ′ ,t〉
(78,(79) = ∑ s∈S dλπ θ ′ (s)  Est∼Pπθ′ (·|s) at∼πθ′ (·|st) st+1∼P(·|st,at) [( πθ(at|st) πθ′ (at|st) − 1 ) δϕt ]  . (80)
To simplify expression, we introduce a notation as follows,
∆ϕt (πθ, πθ′ , s) =: E st∼Pπ
θ ′ (·|s)
at∼πθ′ (·|st) st+1∼P(·|st,at)
[( πθ(at|st) πθ′ (at|st) − 1 ) δϕt ] , (81)
and we use a vector ∆ϕt (πθ, πθ′ ) ∈ R|S| to store all the values {∆ ϕ t (πθ, πθ′ , s)}s∈S :
∆ϕt (πθ, πθ′ )[s] = ∆ ϕ t (πθ, πθ′ , s).
Then we rewrite 〈dλπ θ ′ , δ ϕ πθ,t 〉 − 〈dλπ θ ′ , δ ϕ π θ ′ ,t〉 (80) as follows,
Mϕt (πθ, πθ′ ) =〈d λ π θ ′ , δ ϕ πθ,t 〉 − 〈dλπ θ ′ , δ ϕ π θ ′ ,t〉 (80) = ∑ s∈S dλπ θ ′ (s)∆ ϕ t (πθ, πθ′ , s) = 〈d λ π θ ′ ,∆ ϕ t (πθ, πθ′ )〉.
Step 3: Bound on J(πθ)− J(πθ′ ). Recall (74), taking above result in it, we obtain
〈dλπ θ ′ ,∆ ϕ t (πθ, πθ′ )〉 − ϕ,(λ) p,q,t (πθ, πθ′ ) ≤ D ϕ t (πθ, πθ′ ) ≤ 〈d λ π θ ′ ,∆ ϕ t (πθ, πθ′ )〉+ ϕ,(λ) p,q,t (πθ, πθ′ ).
(82)
Finally, let
Mϕ,−p,q,t(πθ, πθ′ ) = 〈d λ π θ ′ ,∆ ϕ t (πθ, πθ′ )〉 − ϕ,(λ) p,q,t (πθ, πθ′ ) (83)
= ∑ s∈S dλπ θ ′ (s)  Est∼Pπθ′ (·|s) at∼πθ′ (·|st) st+1∼P(·|st,at) [( πθ(at|st) πθ′ (at|st) − 1 ) δϕt ] − ‖dλπθ − dλπθ′ ‖p‖δϕπθ,t‖q
=Es∼dλπ θ ′ (·)  Est∼Pπθ′ (·|s) at∼πθ′ (·|st) st+1∼P(·|st,at) [( πθ(at|st) πθ′ (at|st) − 1 ) δϕt ] − ‖dλπθ − dλπθ′ ‖p‖δϕπθ,t‖q.
and
Mϕ,+p,q,t(πθ, πθ′ ) = 〈d λ π θ ′ ,∆ ϕ t (πθ, πθ′ )〉+ ϕ,(λ) p,q,t (πθ, πθ′ ) (84)
= ∑ s∈S dλπ θ ′ (s)  Est∼Pπθ′ (·|s) at∼πθ′ (·|st) st+1∼P(·|st,at) [( πθ(at|st) πθ′ (at|st) − 1 ) δϕt ] + ‖dλπθ − dλπθ′ ‖p‖δϕπθ,t‖q
=Es∼dλπ θ ′ (·)  Est∼Pπθ′ (·|s) at∼πθ′ (·|st) st+1∼P(·|st,at) [( πθ(at|st) πθ′ (at|st) − 1 ) δϕt ] + ‖dλπθ − dλπθ′ ‖p‖δϕπθ,t‖q.
According to (69) and (82), we achieve the boundedness of performance difference between two arbitrary policies πθ and πθ′ :
1
1− γ̃ ∞∑ t=0
γtλtMϕ,−p,q,t(πθ, πθ′ )︸ ︷︷ ︸ =:Lϕ,−p,q, ≤ J(πθ)− J(πθ′ ) ≤ 1 1− γ̃
∞∑ t=0
γtλtMϕ,+p,q,t(πθ, πθ′ )︸ ︷︷ ︸ =:Lϕ,+p,q, . (85)

heading: E.2 PROOF OF PROPOSITION 4
text: Proof. (of Proposition 4).
Step 1: Rewrite the objective J(πθ) in Eq.(63).
We rewrite the discounted distribution dλπθ (59) as follows,
ρ0 − 1
1− γ̃ dλπθ +
γ̃
1− γ̃ P(λ)πθ d λ πθ = 0. (86)
Let ϕ(·) be a real number function defined on the state space S, i.e., ϕ : S → R. Then we define a vector function φ(·) ∈ R|S| to collect all the values {ϕ(s)}s∈S , and its components are
φ[s] = ϕ(s), s ∈ S.
Now, we take the inner product between the vector φ and (86), we have
0 = 〈ρ0 − 1
1− γ̃ dλπθ +
γ̃
1− γ̃ P(λ)πθ d λ πθ ,φ〉
= 〈ρ0,φ〉 − 1
1− γ̃ 〈dλπθ ,φ〉+
γ̃
1− γ̃ 〈P(λ)πθ d λ πθ ,φ〉. (87)
We express the first term 〈ρ0,φ〉 of (87) as follows, 〈ρ0,φ〉 = ∑ s∈S ρ0(s)ϕ(s) = Es∼ρ0(·)[ϕ(s)]. (88)
We express the second term 〈dλπθ ,φ〉 of (87) as follows,
− 1 1− γ̃ 〈dλπθ ,φ〉 = − 1 1− γ̃ ∑ s∈S dλπθ (s)ϕ(s) = − 1 1− γ̃ Es∼dλπθ (·)[ϕ(s)]. (89)
We express the third term 〈γ̃P(λ)πθ dλπθ ,φ〉 of (87) as follows,
γ̃
1− γ̃ 〈P(λ)πθ d
λ πθ ,φ〉 = γ̃ 1− γ̃ ∑ s′∈S ( P(λ)πθ d λ πθ ) [s ′ ]ϕ(s ′ )
= γ̃ 1− γ̃ ∑ s′∈S (∑ s∈S P(λ)πθ (s ′ |s)dλπθ (s) ) ϕ(s ′ ). (90)
According to Lemma 1, put the results (63) and (87) together, we have
J(πθ)
(63),(87) =
1 1− γ̃ ∑ s∈S dλπθ (s)R (λ) πθ (s) + 〈 ρ0 − 1 1− γ̃ dλπθ + γ̃ 1− γ̃ P(λ)πθ d λ πθ ,φ 〉
=Es0∼ρ0(·)[ϕ(s0)] + 1 1− γ̃ ∑ s∈S dλπθ (s) R(λ)πθ (s) + γ̃ ∑ s′∈S P(λ)πθ (s ′ |s)ϕ(s ′ )− ϕ(s)  , (91)
where the last equation holds since we unfold (87) according to (88)-(90). Step 2: Rewrite the term ( R
(λ) πθ (s) + γ̃ ∑ s′∈S P (λ) πθ (s ′ |s)ϕ(s′)− ϕ(s) ) in Eq.(91).
Then, we unfold the second term of (91) as follows,
R(λ)πθ (s) + γ̃ ∑ s′∈S P(λ)πθ (s ′ |s)ϕ(s ′ )− ϕ(s) (92)
(53),(55) = ∞∑ t=0 (γλPπθ ) trπθ [s] + γ̃(1− γλ) ∑ s′∈S ∞∑ t=0 (γλ)t ( Pt+1πθ [s, s ′ ] ) ϕ(s ′ )− ϕ(s)
(50) = ∞∑ t=0 (γλPπθ ) trπθ [s] + γ(1− λ) ∑ s′∈S ∞∑ t=0 (γλ)tPπθ (st+1 = s ′ |s)ϕ(s ′ )− ϕ(s). (93)
Recall the terms P(λ)πθ , r (λ) πθ [s] defined in (50)-(55),
R(λ)πθ (s) + γ(1− λ) ∑ s′∈S P(λ)πθ (s ′ |s)ϕ(s ′ )− ϕ(s) (94)
We consider the first term R(λ)πθ (s) of (92) as follows,
R(λ)πθ (s) (50)−(55) = r(λ)πθ [s] = ∞∑ t=0 (γλ)tPtπθrπθ [s] = ∞∑ t=0 ∑ st∈S (γλ)tPπθ (st|s)Rπθ (st). (95)
We consider the second term γ̃ ∑ s∈S P (λ) πθ (s ′ |s)ϕ(s)− ϕ(s) of (92) as follows,
γ̃ ∑ s′∈S P(λ)πθ (s ′ |s)ϕ(s ′ )− ϕ(s)
(53) = γ̃(1− γλ) ∑ s′∈S ∞∑ t=0 (γλ)tPπθ (st+1 = s ′ |s)ϕ(s ′ )− ϕ(s) (96)
(50) = γ(1− λ) ∑ s′∈S ∞∑ t=0 (γλ)tPπθ (st+1 = s ′ |s)ϕ(s ′ )− ϕ(s) (97)
=γ ∑ s′∈S ∞∑ t=0 (γλ)tPπθ (st+1 = s ′ |s)ϕ(s ′ )− ∑ s′∈S ( ∞∑ t=0 (γλ)t+1Pπθ (st+1 = s ′ |s)ϕ(s ′ ) ) ︸ ︷︷ ︸
= ∑∞ t=1(γλ) tPπθ (st=s ′ |s)ϕ(s′ )
−ϕ(s)
=γ ∑ s′∈S ∞∑ t=0 (γλ)tPπθ (st+1 = s ′ |s)ϕ(s ′ )− ∑ s′∈S ∞∑ t=1 (γλ)tPπθ (st = s ′ |s)ϕ(s ′ ) + ϕ(s)  ︸ ︷︷ ︸
= ∑ s ′∈S ∑∞ t=0(γλ) tPπθ (st=s ′ |s)ϕ(s′ )
(98)
=γ ∑ s′∈S ∞∑ t=0 (γλ)tPπθ (st+1 = s ′ |s)ϕ(s ′ )− ∑ st∈S ∞∑ t=0 (γλ)tPπθ (st|s)ϕ(s), (99)
where the equation from Eq.(98) to Eq.(99) holds since: according to (41), we use the following identity
∑ s′∈S Pπθ (s0 = s ′ |s)ϕ(s ′ ) = ϕ(s).
Furthermore, take the result (95) and (99) to (94), we have R(λ)πθ (s) + γ̃ ∑ s′∈S P(λ)πθ (s ′ |s)ϕ(s ′ )− ϕ(s)
= ∞∑ t=0 (γλ)t ( ∑ st∈S Pπθ (st|s)Rπθ (st) + γ ∑ s′∈S
Pπθ (st+1 = s ′ |s)ϕ(s ′ )︸ ︷︷ ︸
(42) = ∑ st∈S Pπθ (st+1=s ′ |st)Pπθ (st|s)ϕ(s ′ )
− ∑ st∈S Pπθ (st|s)ϕ(st)
) (100)
= ∞∑ t=0 (γλ)t ∑ st∈S Pπθ (st|s)Rπθ (st) + γ ∑ st∈S Pπθ (st|s) ∑ st+1∈S Pπθ (st+1|st)ϕ(st+1)
− ∑ st∈S Pπθ (st|s)ϕ(st)
) (101)
= ∞∑ t=0 (γλ)t ∑ st∈S Pπθ (st|s)  ∑ at∈A πθ(at|st) ∑
st+1∈S P(st+1|st, at)r(st+1|st, at)︸ ︷︷ ︸
=Rπθ (st)
+ γ ∑ at∈A πθ(at|st) ∑
st+1∈S P(st+1|st, at)︸ ︷︷ ︸
=Pπθ (st+1|st)
ϕ(st+1)− ϕ(st)  =
∞∑ t=0 (γλ)t ∑ st∈S Pπθ (st|s) ∑ at∈A πθ(at|st) ∑ st+1∈S P(st+1|st, at) (r(st+1|st, at) + γϕ(st+1)− ϕ(st))
(102)
= ∞∑ t=0 (γλ)tEst∼Pπθ (·|s),at∼πθ(·|st),st+1∼P(·|st,at) [r(st+1|st, at) + γϕ(st+1)− ϕ(st)] , (103)
the equation from Eq.(99) to Eq.(100) holds since:
Pπθ (st+1|s) (42) = ∑ st∈S Pπθ (st+1|st)Pπθ (st|s);
the equation from Eq.(100) to Eq.(101) holds since we use the Markov property of the definition of MDP: for each time t ∈ N,
Pπθ (st+1 = s ′ |st = s) = Pπθ (s ′ |s);
the equation (102) the following identity:∑ at∈A πθ(at|st) = 1, ∑ st+1∈S P(st+1|st, at) = 1,
then ϕ(st) = ∑ at∈A πθ(at|st) ∑ st+1∈S P(st+1|st, a)ϕ(st).
Step 3: Put all the result together.
Finally, let
δϕt = r(st+1|st, at) + γϕ(st+1)− ϕ(st), δϕπθ,t(s) = Est∼Pπθ (·|s),at∼πθ(·|st),st+1∼P(·|st,at) [δ ϕ t ] ,
combining the results (91) and (103), we have
J(πθ) =Es0∼ρ0(·)[ϕ(s0)] + 1 1− γ̃ ∑ s∈S dλπθ (s) ( ∞∑ t=0 γtλtδϕπθ,t(s) ) (104)
=Es0∼ρ0(·)[ϕ(s0)] + 1
1− γ̃ Es∼dλπθ (·) [ ∞∑ t=0 γtλtδϕπθ,t(s) ] .
This concludes the proof of Proposition 4.

heading: E.3 LEMMA 2
text: Lemma 2. Let ‖Ππ θ ′ −Ππθ‖1,1 denote as the L1,1-norm for the difference between two policy space {πθ(a|s)}(s,a)∈S×A, {πθ′ (a|s)}(s,a)∈S×A, i.e.,
‖Ππ θ ′ −Ππθ‖1,1 =: ∑ s∈S ∑ a∈A |πθ′ (a|s)− πθ(a|s)| . (105)
The divergence between discounted future state visitation distributions, ‖dλπ θ ′ − dλπθ‖1, is bounded as follows,
‖dλπ θ ′ − d λ πθ ‖1 ≤
(1− γλ)2 (1− γ) (
1− γλ‖Ππ θ ′ −Ππθ‖1,1 )Es∼dλπθ (·)[2DTV(πθ′ , πθ)[s]] and
‖dλπ θ ′ − d λ πθ ‖1 ≤
(1− γλ)2 (1− γ) (
1− γλ‖Ππ θ ′ −Ππθ‖1,1
)Es∼dλπ θ ′ (·) [ 2DTV(πθ′ , πθ)[s] ] ,
where 2DTV(πθ′ , πθ)[s] =: ∑ a∈A |πθ′ (a|s)− πθ(a|s)| .
Furthermore, we achieve the boundedness of ‖dλπ θ ′ − dλπθ‖1 as follows,
‖dλπ θ ′ − d λ πθ ‖1 ≤
1 1− γ̃ · 1− γλ |1− 2γλ|S||A|| Es∼dλπθ (·) [ 2DTV(πθ′ , πθ)[s] ] ,
‖dλπ θ ′ − d λ πθ ‖1 ≤
1 1− γ̃ · 1− γλ |1− 2γλ|S||A|| Es∼dλπ θ ′ (·)
[ 2DTV(πθ′ , πθ)[s] ] .
Proof. Recall Eq.(59), let Gπθ = ( I− γ̃P(λ)πθ )−1 , Gπ θ ′ = ( I− γ̃P(λ)π θ ′ )−1 , D = P(λ)π θ ′ −P (λ) πθ . (106)
Then, the following holds
G−1πθ −G −1 π θ ′ = ( I− γ̃P(λ)πθ ) − ( I− γ̃P(λ)π θ ′ ) = γ̃D. (107)
Furthermore, by left-multiplying by Gπθ and right-multiplying by Gπθ′ , we achieve
Gπ θ ′ −Gπθ = γ̃Gπθ′DGπθ . (108)
Grouping all the results from (106)-(108), recall (59),
dλπθ = (1− γ̃) ∞∑ t=0 ( γP(λ)πθ )t ρ0 = (1− γ̃) ( I− γ̃P(λ)πθ )−1 ρ0 = (1− γ̃)Gπθρ0, (109)
then we have
dλπ θ ′ − d λ πθ
=(1− γ̃) ( Gπ
θ ′ −Gπθ
) ρ0
(108) = (1− γ̃)γ̃Gπ
θ ′DGπθρ0
(109) = γ̃Gπ
θ ′Dd λ πθ . (110)
Applying (110), we have
‖dλπ θ ′ − d λ πθ ‖1
(110)
≤ γ̃‖Gπ θ ′ ‖1‖Ddλπθ‖1. (111)
Firstly, we bound the term ‖Gπ θ ′ ‖1 as follows,
‖Gπ θ ′ ‖1 = ∥∥∥∥(I− γ̃P(λ)πθ′ )−1 ∥∥∥∥
1 ≤ ∞∑ t=0 γ̃t ∥∥∥P(λ)π θ ′ ∥∥∥ 1 = 1 1− γ̃ = 1− γλ 1− γ . (112)
Now, we analyze the second term as follows,
‖Ddλπθ‖1
= ∑ s′∈S ∣∣∣∣∣∑ s∈S D(s ′ |s)dλπθ (s) ∣∣∣∣∣ (53) = ∑ s′∈S ∣∣∣∣∣∑ s∈S ( P(λ)π θ ′ (s ′ |s)− P(λ)πθ (s ′ |s) )∣∣∣∣∣ dλπθ (s)
(53) = ∑ s′∈S ∣∣∣∣∣(1− γλ) ∞∑ t=0 (γλ)t ∑ s∈S ( Pπ θ ′ (st+1 = s ′ |s)− Pπθ (st+1 = s ′ |s) )∣∣∣∣∣ dλπθ (s)
≤ ∑ s∈S (1− γλ) ∞∑ t=0 (γλ)t ∑ s′∈S ∣∣∣Pπ θ ′ (st+1 = s ′ |s)− Pπθ (st+1 = s ′ |s) ∣∣∣  dλπθ (s) (113)
.
Before we provide a further analyze (113), we need to bound |Pπ θ ′ (st+1 = s ′ |s)−Pπθ (st+1 = s ′ |s)|. Let s0 = s, then
Pπθ (st+1 = s ′ |s) 42= ∑ s1∈S Pπθ (st+1 = s ′ |s1)Pπθ (s1|s0)
= ∑ s1∈S ∑ s2∈S Pπθ (st+1 = s ′ |s2)Pπθ (s2|s1)Pπθ (s1|s0)
= · · · = ∑ s1∈S ∑ s2∈S · · · ∑ st∈S ( t+1∏ i=1 Pπθ (si|si−1) )
= ∑ s1∈S ∑ s2∈S · · · ∑ st∈S ( t+1∏ i=1 (∑ ai∈A P(si|si−1, ai)πθ(ai|si−1) )) . (114)
Similarly, we have
Pπ θ ′ (st+1 = s
′ |s) = ∑ s1∈S ∑ s2∈S · · · ∑ st∈S ( t+1∏ i=1 (∑ ai∈A P(si|si−1, ai)πθ′ (ai|si−1) )) . (115)
Then, according to the results (114)-(115), let s0 = s, the following holds∑ s′∈S |Pπ θ ′ (st+1 = s ′ |s)− Pπθ (st+1 = s ′ |s)|
= ∑ s′∈S ∣∣∣∣∣∑ s1∈S ∑ s2∈S · · · ∑ st∈S ( t+1∏ i=1 (∑ ai∈A P(si|si−1, ai) (πθ′ (ai|si−1)− πθ(ai|si−1)) ))∣∣∣∣∣ ≤ ∑ s1∈S ∑ s2∈S · · · ∑ st∈S ( t+1∏ i=1 ∑ ai∈A |πθ′ (ai|si−1)− πθ(ai|si−1)| )
= ∑ s1∈S ∑ s2∈S · · · ∑ st∈S ( t+1∏ i=2 ∑ ai∈A |πθ′ (ai|si−1)− πθ(ai|si−1)| ) · (∑ a1∈A |πθ′ (a1|s0)− πθ(a1|s0)| )
= t+1∏ i=2  ∑ si−1∈S ∑ ai∈A |πθ′ (ai|si−1)− πθ(ai|si−1)|  ·(∑ a1∈A |πθ′ (a1|s0)− πθ(a1|s0)| )
=  ∑ s∈S ∑ a∈A |πθ′ (a|s)− πθ(a|s)|︸ ︷︷ ︸
=: ∥∥∥Ππ
θ ′ −Ππθ ∥∥∥ 1,1
 t · (∑ a∈A |πθ′ (a|s)− πθ(a|s)| ) . (116)
Taking the result (116) to (113), we have
‖Ddλπθ‖1 ≤(1− γλ) ∞∑ t=0 (γλ)t ∥∥∥Ππ θ ′ −Ππθ ∥∥∥t 1,1 ∑ s∈S ∑ a∈A |πθ′ (a|s)− πθ(a|s)|︸ ︷︷ ︸ =:2DTV(πθ′ ,πθ)[s] dλπθ (s)
=(1− γλ) ∞∑ t=0 (γλ)t‖Ππ θ ′ −Ππθ‖t1,1Es∼dλπθ (·) [ 2DTV(πθ′ , πθ)[s] ] =
1− γλ 1− γλ‖Ππ
θ ′ −Ππθ‖1,1
Es∼dλπθ (·) [ 2DTV(πθ′ , πθ)[s] ] . (117)
Finally, according to (111), (112) and (117), we have
‖dλπ θ ′ − d λ πθ ‖1 ≤
γ̃ 1− γ̃ · γ(1− λ)
1− γλ‖Ππ θ ′ −Ππθ‖1,1
Es∼dλπθ (·) [ 2DTV(πθ′ , πθ)[s] ] . (118)
Recall (105), we have
‖Ππ θ ′ −Ππθ‖1,1 = ∑ s∈S ∑ a∈A |πθ′ (a|s)− πθ(a|s)| ≤ 2|S||A|. (119)
Then, we achieve the boundedness of ‖Ππ θ ′ −Ππθ‖1,1 as follows,
‖dλπ θ ′ − d λ πθ ‖1 ≤
γ̃ 1− γ̃ · 1− γλ |1− 2γλ|S||A|| Es∼dλπθ (·) [ 2DTV(πθ′ , πθ)[s] ] . (120)

heading: F PROOF OF THEOREM 2
text: Theorem 2 Let δk = Es∼dλπθk (·) [ KL ( πθk , πθk+1 2 ) [s] ] , if πθk and πθk+1 are related to (17)-(18), then the lower bound on policy improvement, and upper bound on constraint violation are
J(πθk+1)− J(πθk) ≥ − γ(1− λ)αk
√ 2δk V πθ (πθ′ )
(1− γ) |1− 2γλ|S||A|| , Jc(πθk+1) ≤ b+
γ(1− λ)βk √ 2δk C πθ (πθ′ )
(1− γ) |1− 2γλ|S||A|| .
Proof. (of Theorem 2)
According to Bregman divergence, if policy πθk is feasible, policy πθk+1 is generated according to (18), then the following
KL ( πθk , πθk+1
2
) ≥ KL ( πθk , πθk+1 ) + KL ( πθk+1 , πθk+1
2 ) implies
δk = Es∼dλπθk (·) [ KL ( πθk , πθk+1 2 ) [s] ] ≥ Es∼dλπθk (·) [ KL ( πθk+1 , πθk ) [s] ] .
According to the asymptotically symmetry of KL divergence if we update the policy within a local region, then, we have
δk ≥ Es∼dλπθk (·) [ KL ( πθ k+1 2 , πθk ) [s] ] ≥ Es∼dλπθk (·) [ KL ( πθk+1 , πθk ) [s] ] .
Furthermore, according to Proposition 1 and Proposition 3, we have
J(πθk+1)− J(πθk)
≥ 1 1− γ̃ Es∼dλπθk (·),a∼πθk+1 (·|s) [ AGAE(γ,λ)πθk (s, a)− 2γ(1− λ) Vπθk+1 (πθk) (1− γλ) |1− 2γλ|S||A|| DTV(πθk , πθk+1)[s] ]
≥ 1 1− γ̃ Es∼dλπθk (·),a∼πθk+1 (·|s)
[ −
2γ(1− λ)αk Vπθk+1 (πθk) (1− γλ) |1− 2γλ|S||A||
√ 1
2 Es∼dλπθk (·)
[ KL(πθk , πθk+1)[s]
]]
≥ 1 1− γ̃ Es∼dλπθk (·),a∼πθk+1 (·|s)
[ − γ(1− λ)αk √ 2δk V πθk+1 (πθk)
(1− γλ) |1− 2γλ|S||A||
] .
Similarly, according to Proposition 1 and Proposition 2, and since policy πθk+1 satisfies
Jc(πθk) + 1
1− γ̃ Es∼dλπθk (·),a∼πθk+1 (·|s)
[ A
GAE(γ,λ) πθk ,C
(s, a) ] + βk √ Es∼dλπθk (·) [ KL(πθk , πθk+1)[s] ] ≤ b,
(121)
and
Jc(πθk+1)− Jc(πθk) (122)
≤ 1 1− γ̃ Es∼dλπθk (·),a∼πθk+1 (·|s)
[ A
GAE(γ,λ) πθk ,C (s, a) + 2γ(1− λ)βk Cπθk+1 (πθk) (1− γλ) |1− 2γλ|S||A|| DTV(πθk , πθk+1)[s]
] .
Combining (121)- (123), we have
Jc(πθk+1)− Jc(πθk) (123)
≤b+ 1 1− γ̃ Es∼dλπθk (·),a∼πθk+1 (·|s) [ 2γ(1− λ)βk Cπθk+1 (πθk) (1− γλ) |1− 2γλ|S||A|| √ 1 2 Es∼dλπθk (·) [ KL(πθk , πθk+1)[s] ]]
≤b+ 1 1− γ̃ Es∼dλπθk (·),a∼πθk+1 (·|s)
[ γ(1− λ)βk √ 2δk
C πθk+1 (πθk)
(1− γλ) |1− 2γλ|S||A||
] . (124)

heading: G EXPERIMENTS
text: The Python code for our implementation of CUP is provided along with this submission in the supplementary material.

heading: G.1 ENVIRONMENT

heading: G.1.1 ENVIRONMENT 1: ROBOTS WITH SPEED LIMIT.
text: We consider two tasks from MuJoCo (Brockman et al., 2016): Walker2d-v3 and Hopper-v3, where the setting of cost follows (Zhang et al., 2020). For agents move on a two-dimensional plane, the cost is calculated as follows,
C(s, a) = √ v2x + v 2 y;
for agents move along a straight line, the cost is calculated as
C(s, a) = |vx|, where vx, vy are the velocities of the agent in the x and y directions respectively.

heading: G.1.2 ENVIRONMENT 2: CIRCLE.
text: The Circle Environment follows (Achiam et al., 2017), and we use open-source implementation of the circle environments from https://github.com/ymzhang01/mujoco-circle. According to Zhang et al. (2020), those experiments were implemented in OpenAI Gym (Brockman et al., 2016) while the circle tasks in Achiam et al. (2017) were implemented in rllab (Duan et al., 2016). We also excluded the Point agent from the original experiments since it is not a valid agent in OpenAI Gym. The first two dimensions in the state space are the (x, y) coordinates of the center mass of the agent, hence the state space for both agents has two extra dimensions compared to the standard Ant-v0 and Humanoid-v0 environments from OpenAI Gym.
Now, we present some necessary details of this environment taken from (Zhang et al., 2020).
In the circle tasks, the goal is for an agent to move along the circumference of a circle while remaining within a safety region smaller than the radius of the circle. The exact geometry of the task is shown in Figure 2. The reward and cost functions are defined as:
R(s) = −yvx + xvy 1 + | √ x2 + y2 − r| , C(s) = I(|x| > xlim),
where x, y are the positions of the agent on the plane, vx, vy are the velocities of the agent along the x and y directions, r is the radius of the circle, and xlim specifies the range of the safety region. The radius is set to r = 10 for both Ant and Humanoid while xlim is set to 3 and 2.5 for Ant and Humanoid respectively. Note that these settings are identical to those of the circle task in Achiam et al. (2017); Zhang et al. (2020).

heading: G.1.3 ENVIRONMENT 3: SAFETY GYM SHIPS WITH THREE PRE-MADE ROBOTS.
text: In Safety Gym environments, the agent perceives the world through a robot’s sensors and interacts with the world through its actuators. In our paper, we consider three environment: Point, Car, Dog from (Ray et al., 2019). In this section, the presentation of those environments are taken from (Ray et al., 2019), for more details, please refer to (Ray et al., 2019, Page 8–10).
Point: (Figure 3 (a)). A simple robot constrained to the 2D-plane, with one actuator for turning and another for moving forward/backwards. This factored control scheme makes the robot particularly easy to control for navigation. Point has a small square in front that makes it both easier to visually determine the robot’s direction, and helps the point push a box element that appears in one of our tasks.
Car: (Figure 3 (c)). Car is a slightly more complex robot that has two independently-driven parallel wheels and a free rolling rear wheel. Car is not fixed to the 2D-plane, but mostly resides in it. For this robot, both turning and moving forward/backward require coordinating both of the actuators. It is similar in design to simple robots used in education.
Doggo: (Figure 3 (e)). Doggo is a quadrupedal robot with bilateral symmetry. Each of the four legs has two controls at the hip, for azimuth and elevation relative to the torso, and one in the knee, controlling angle. It is designed such that a uniform random policy should keep the robot from falling over and generate some travel.
All actions for all robots are continuous, and linearly scaled to [−1,+1], which is common for 3D robot-based RL environments and (anecdotally) improves learning with neural nets. Modulo scaling, the action parameterization is based on a mix of hand-tuning and MuJoCo actuator defaults, and we caution that it is not clear if these choices are optimal. Some safe exploration techniques are action-layer interventions, like projecting to the closest predicted safe action (Dalal et al., 2018), and these methods can be sensitive to action parameterization. As a result, action parameterization may merit more careful consideration than is usually given. Future work on action space design might be to find action parameterizations that respect physical measures we care about—for example, an action space where a fixed distance corresponds to a fixed amount of energy.
The Safety Gym environment-builder currently supports three main tasks: Goal, Button, and Push (depicted in Fig. 2). Tasks in Safety Gym are mutually exclusive, and an individual environment can only make use of a single task. Reward functions are configurable, allowing rewards to be either sparse (rewards only obtained on task completion) or dense (rewards have helpful, hand-crafted shaping terms). Task details follow:
Goal: (Figure 3 (b)). Move the robot to a series of goal positions. When a goal is achieved, the goal location is randomly reset to someplace new, while keeping the rest of the layout the same. The sparse reward component is attained on achieving a goal position (robot enters the goal circle). The dense reward component gives a bonus for moving towards the goal.
Button: (Figure 3 (d)). Press a series of goal buttons. Several immobile “buttons” are scattered throughout the environment, and the agent should navigate to and press (contact) the currently-
highlighted button, which is the goal button. After the agent presses the correct button, the environment will select and highlight a new goal button, keeping everything else fixed. The sparse reward component is attained on pressing the current goal button. The dense reward component gives a bonus for moving towards the current goal button.
Push: (Figure 3 (f)). Move a box to a series of goal positions. Like the goal task, a new goal location is drawn each time a goal is achieved. The sparse reward component is attained when the yellow box enters the goal circle. The dense reward component consists of two parts: one for getting the agent closer to the box, and another for getting the box closer to the goal.

heading: Constraint Options and Desiderata
text: The constraint elements themselves are:
Hazards: (Figure 4 (a)). Dangerous areas to avoid. These are circles on the ground that are non-physical, and the agent is penalized for entering them.
Vases: (Figure 4 (b)). Objects to avoid. These are small blocks that represent fragile objects. The agent is penalized for touching or moving them.
Pillars: (Figure 4 (c)). Immobile obstacles. These are rigid barriers in the environment, which the agent should not touch.
Buttons: (Figure 4 (d)). Incorrect goals. When using the “buttons” goal, pressing an incorrect button is penalized.
Gremlins: (Figure 4 (e)). Moving objects. These are simple moving objects that the agent must avoid contacting. Since they are moving quickly, the agent must stay out of the way of their path of travel.
Although all constraint elements represent things for the agent to avoid, they pose different challenges for the agent by virtue of having different dynamics. To illustrate the contrast: hazards provide no physical obstacle, vases are moveable obstacles, pillars are immovable obstacles, buttons can sometimes be perceived as goals, and gremlins are actively-moving obstacles. Like reward functions in Safety Gym, cost functions are configurable in various ways; see the code for details. By default, cost functions are simple indicators for whether an unsafe interaction has occured (ct = 1 if the agent has done the unsafe thing, otherwise ct = 0).
Finally, SGPoint, SGCar, and SGDoggo, which are all six Point/Car/Doggo robot environments with constraints in Safety Gym, and Ray et al. (2019) have provided an implementation for those environments.

heading: G.2 DETAILS OF EXPERIMENTS
text: In all of those experiments, we use a two-layer feedforward neural network with a tanh activation for both policy and value networks. Experiment-specific parameters are as follows:
Parameter Walker2d Hopper HumanoidCircle AntCircle No. of hidden layers 2 2 2 2 No. of hidden nodes 64 64 64 64
Batch size 2048 2048 50000 50000 Minibatch size 64 64 1000 1000 Rollout length 1000 1000 1000 1000 GAE parameter (cost) 0.95 0.95 0.995 0.995 GAE parameter (reward) 0.95 0.95 0.995 0.995
discounter for cost 0.99 0.99 0.995 0.995 discounter for reward 0.99 0.99 0.995 0.995
learning rate for policy 3× 10−4 3× 10−4 3× 10−4 3× 10−4 learning rate for value and reward function 3× 10−4 3× 10−4 3× 10−4 3× 10−4

Review summaries:
The paper studies the problem of learning under constrained Markov decision processes. It proposes to solve this problem by an RL algorithm based on generalized advantage estimator (GAE), which they call  Conservative Update Policy (CUP). Although existing works have already proposed GAE-based algorithms, the current paper is the first to provide theoretical foundations for this type of algorithm. Specifically, it proves bounds on performance difference for GAE-based algorithms and one-step improvement for CUP. Numerical experiments have been conducted to showcase the performance of the proposed algorithm.

This paper considers reinforcement learning, a common model which has seen success recently in many areas (e.g. games, robotics, autonomous vehicles).  Prototypical reinforcement learning algorithms explore the action space in order to maximize their rewards as much as possible, potentially ignoring impacts of the chosen actions or safety constraints.  Typical to many real-world scenarios, though, are constraints on the selected actions allowing the algorithm designer or practitioner to enforce certain constraints on the selected actions in the environment (e.g. ensure that the autonomous vehicle stays within the dictated lines on the road, etc).  This is typically done by introducing a cost-function and adding an additional constraint that the resulting policies have long-run discounted cost upper bounded by a given constant.  While many RL algorithms have been designed in this setting, they mostly focus on either taking lagrangian relaxations of the given policy constraints, or constructing convex approximations to the non-convex objectives to optimize (which also in turns adds to additional complexity in constructing higher order moments of the objective for optimization).  In contrast, the authors in this paper take a different view, via the following: 1. Construct tight upper and lower bounds on the difference in value functions for arbitrary policies with respect to arbitrary functions $\phi$, a given additional discount parameter $\lambda$ 2. Instantiate the upper bound with $\phi$ taken as the value function to get a lower bound on the difference in value between any two policies 3. Instantiate the lower bound with $\phi$ taken as the cost-value function to get an upper bound on the cost-difference between any two policies  Once these bounds are established, the algorithmic approach is simple.  In the first step they perform a performance improvement step to improve the performance of the policy by maximizing the lower bound on the difference in value between the two policies.  The second step is a projection step, where after lagrangianizing the constraint set they minimize the lower bound on the difference in costs between the two policies.  The authors show a guarantee on per-step improvements on the rewards and cost for this proposed approach assuming exact maximization / minimization of these objectives.  To be more specific, the authors consider the typical RL model with an MDP characterized via $(S, A, P, r, \gamma)$.  They consider the goal of maximizing the expected long term rewards $r$.  However, there is an additional cost function $c$ and they add an additional constraint that the long-run discounted cost is upper bounded by a given constant $b$.  The hope is that the learned policy picks actions which satisfy the long-run average cost constraint while simultaneously maximizing the expected rewards.  The authors first start-off by proposing a novel bound, generalizing the policy performance difference $J(\pi_\theta) - J(\pi_{\theta'})$ between any two policies.  In particular the difference is upper and lower bounded by two terms.  The first term can be interpreted as the expectation between the TD errors of $\pi_\theta$ and $\pi_{\theta'}$ where TD errors are computed for an arbitrary function $\phi$.  The second part is the discounted distribution difference between the two different policies.  These bounds are then instantiated with different functions $\phi$ and parameters in order to get lower and upper bounds on the performance difference between the policies with respect to the costs and rewards of the problem.  Once these lower and upper bounds on the performance difference are established, the algorithm falls naturally by maximizing the reward lower bound and minimizing the cost upper bound.  This is then theoretically justified by providing a per-step improvement with respect to the two different objectives.    To complement the algorithmic framework, the authors present a set of synthetic experiments to compare the efficiency and constraint violation of the resulting policies of their method and others in the literature.  In particular, they test the policies on three different environments and compare to several other existing algorithms in the literature (more on this later).  They show that their algorithm and approach dominates others in terms of performance while simultaneously ensuring the cost constraints.