Convergence Rate of Primal-Dual Approach to Constrained Reinforcement Learning with Softmax Policy
Authors: Long Yang
Li Shen
Pengfei Li
Yaodong Yang
Zhouchen Lin
Gang Pan
Venue: Submitted to ICLR 2023 (2023)
Keywords: Constrained Reinforcement Learning
Constrained Markov Decision Process

Abstract: In this paper, we consider primal-dual approach to solve constrained reinforcement learning (RL) problems, where we formulate constrained reinforcement learning  under constrained Markov decision process (CMDP). We propose the primal-dual policy gradient (PD-PG) algorithm with softmax policy. Although the constrained RL involves a non-concave maximization problem over the policy parameter space, we show that for both exact policy gradient and model-free learning, the proposed PD-PG needs iteration complexity of $\mathcal{O}\left(\epsilon^{-2}\right)$ to achieve its optimal policy for both constraint and reward performance. Such an iteration complexity outperforms or matches most constrained RL algorithms. For the learning with exact policy gradient, the main challenge is to show the positivity of deterministic optimal policy (at the optimal action) is independent on both state space and iteration times.
For the model-free learning, since we consider the discounted infinite-horizon setting, and the simulator can not rollout with an infinite-horizon sequence; thus one of the main challenges lies in how to design unbiased value function estimators with finite-horizon trajectories. We consider the unbiased estimators with finite-horizon trajectories that involve geometric distribution horizons, which is the key technique for us to obtain the theoretical results for model-free learning.

Under review as a conference paper at ICLR 2023
CONVERGENCE RATE OF PRIMAL-DUAL APPROACH TO CONSTRAINED REINFORCEMENT LEARNING WITH SOFTMAX POLICY
Anonymous authors Paper under double-blind review
ABSTRACT
this paper, we consider primal-dual approach to solve constrained reinforcement learning (RL) problems, where we formulate constrained reinforcement learning under constrained Markov decision process (CMDP). We propose the primal-dual policy gradient (PD-PG) algorithm with softmax policy. Although the constrained RL involves a non-concave maximization problem over the policy parameter space, we show that for both exact policy gradient and model-free learning, the proposed PD-PG needs iteration complexity of O (E- to achieve its optimal policy for both constraint and reward performance. Such an iteration complexity outperforms or matches most constrained RL algorithms. For the learning with exact policy gradient, the main challenge is to show the positivity of deterministic optimal policy (at the optimal action) is independent on both state space and iteration times. For the model-free learning, since we consider the discounted infinitehhorizn setting, and the simulator can not rollout with infinit-hhorizo sequence; thus one of the main challenges lies in how to design unbiased value function estimators with finite-horizee trajectories. We consider the unbiased estimators with mnitehhorizon trajectories that involve geometric distribution horizons, which is the key technique for us obtain the theoretical results for model-free learning.
INTRODUCTION
Reinforcement learning (RL) has achieved significant success in many fields (e.g., (Silver et al. 2017; Vinyals et al. 2019 OpenAl 2019)). However, most RL algorithms improve the performance under the assumption that agent free to explore any behaviors (that may be detrimental). For example, a robot agent should avoid playing actions that irrevocably harm its hardware (Deisenroth et al.) 2013).Thus, is important consider safe exploration that is known as constrained RL (or safe RL., which is usually formulated as constrained Markov decision processes (CMDP) (Altman 1999).
The primal-dual approach (Altman 1999 Bertsekas 2014) is fundamental way solve CMDP problems. Recently, the primal-dual method has also been extended to policy gradient (e.g., Tessler
al.
2019 Petsagkourakis et al., 2020; Xu al. 202T). However, most previous work only focus
on natural policy gradient (NPG) (akadee (2002) to solve constrained RL (e.g., (Ding et al. 2020 Xu
al. 2021 Zeng et al., (02T)), little known about the vanilla policy gradient (Sutton al. 2000)
with primal-dum approach to constrained RI., which involves the following foundational theoretical
issues: (i) how to employ the primal-dual vanilla policy gradient method constrained RI with exact information and model-free learning? (ii) how fast does primal-dual vanilla policy gradient converge to the optimal policy? (iii) what is the sample complexity of the primal-dual policy gradient? These questions are the focus of this paper, and we mainly consider softmax policy for the discounted infinite-horizon CMDP with finite action space and state space.
1.1 MAIN CONTRIBUTIONS
Constrained RL with Exact Policy Gradient. In Section propose primal-dual policy gradient (PD-PG) algorithm, which improves reward performance via gradient ascent on the primal policy parameter space and plays safe explorations via projecting gradient descent the dual space.

---

Under review as a conference paper at ICLR 2023
Theorem 2 shows that PD-PG with exact policy gradient needs the iteration complexity of de mx
|g LAI
c. 7)
to obtain the -pptimallt where is the infimum of the probability of the optimal action from softmax policy, e, is a positive scalar independent on the time-step and independent on the state space S. One of the main challenges obtain the complexity (1) is to show that e, is bounded away from O, see Proposition 2 From i
we know the proposed PD-PG is with the iteration which is comparable to extensive constrained RL algorithms.
complexity of
Model-Free Constrained RL. In Section 4 we propose a sample-based PD-PG that only uses empirical data to learn a safe policy. The sample-hased PD-PG needs a complexity of
(1 doe
2 |S| (S)|
+ m
log AA]
o
(2)
Po
(1 (1-1-)) 2)
to obtain the oottiompimal,it, where m is the number of constraints. The iteration complexity 2 outperforms or matches extensive existing ofte-of-thee-n constrained RL algorithms. see Table [. Since this work considers discounted infimitehhorizon CMDP, and the simulator can not rollout with an -efiitt-hooizon sequence; thus the main challenge lies in designing unbiased value function estimators with mnite-horizon trajectories. In Section 4.2 according to co|Paternain] (2018) Chapter 6), we introduce unbiased estimators with finite-horizon trajectories that involve geometric distribution horizons, which plays a critical role for us to obtain the iteration complexity of sample-based PD-PG. Finally, in Section 4.6 we also illustrate an iteration complexity trade-off between PD-PG and NPD-
PG (Ding et al.
2020 y where we analyze it from the trade-off between the distribution mismatch
coefficient den
(contained the proposed PD-PG) and the Moore-Penrose pseudo inverse Fisher
information matrix Fi( (contained in NPD-PG DDigg et al. 2020
1.2 RELATED WORK
Constrained RL with Exact Policy Gradient. The proposed PD-PG (Algorithm) I is Lagrangian-
based CMDP algorithm (Borkar 2005 Bhatnagar & Lakshmanan 2012 Liang et al. 2018 Tessler
al. 2019 Yu al. [219 Chow et al. 2017; Koppel al. [019 Miryoosefi et al. 2019 Paternain
et al. 2019a by. However, those work only focus on the asymptotic convergence results. Primal-dual
method is extended with policy gradient (e.g..(Borkar
2005 [Bhatnagar & Lakshmanan] 2012 Tessler
et al. 2019 Petsagkourakis et al. 2020 Wachi et al.
2021) p), but those work focus natural policy
gradient (NPG) with Fisher information (Kakade) 2002) or regularized policy iteration to solve
constrained RL problems (c.g.. (Bharadhwaj et al. 2021)). is still known litter about vanilla policy gradient [Williams) 1992, Sutton et al.] 2000) with primal-dual approach (i.e., the proposed PD-PG) to constrained RL. This work studies the finite- sample performance of the vanilla PD-PG. From Table 1 we know expect UCBVI-> (He et al. 2021) outperforms PD-PG by a factor PD-PG is comparable to extensive existing state-ol-the-ae art CMDP algorithms.
Model-Free Constrained RL. Model-free constrained RL algorithms. including CPO AAhiam et al.
2017), IPO (Liu et al./ 2020). Lyapunov-Based Safe RL (Chow et al. (2018). SAILR (Wagener et al.
2021
SPRL (Sohn al. 202T). SNO-MDP (Wachi & Suij (200)) A-CRL (Calvo-Fullana al.
2021
and DCRL (Qin et al.
2021 all lack convergence rate analysis.
Recently, Ding et al. (2020) propose the natural policy gradient primal-dual (NPD-PG) method for solving discounted adfnite-horizon CMDP. Even though the underlying maximization involves non- concave objective function and nonconvex constraint setting under the softmax policy parametriza- Diog et al.) (2020) show NPD-PG converges at sublinear rates regarding both the optimality gap and the constraint violation, which shares a similar iteration complexity as the proposed PD-PG. Later, Zeng et al. (2021 1) extend the critical idea of NPD-PG, propose an online version of NPD-PG, and show their algorithm needs the sample complexity of O(c Xu et al. (2021) propose a primal-type algorithmic framework to solve SRL problems, and Xu et al. (2021) show needs O sample complexity to obtain ((c) -c)tomatiaality 7. Finally, from Table we know PD-PG achieves the best
sample complexity among the policy-based safe RL algorithms.
2

---

Under review as a conference paper at ICLR 2023
Exaci Information
Algorihaas
lievztin Complexny
Model-Fize Lowning
Algodihim
licraion Complesity
Value-Baser
OrePimslDeakk Dran-DDD
Lironi D020
[SP
Value Based
(ramley al. 2020
CroRt
Remark 3.5)
Valae-Baced
Erroni et a.. 2020
Opt MDP
[SP
Value-Rased
(Rai ct 2011
CSP3A
[8PLL
S S
Value-Bovd
Kalagara
Theorem
2 [S]
Value-Rascd
Wei al.
[1 (1
Value Based
Liu 2021
Value Based
Miryosseli & Jin 2021 Thenrem 7)
Rewand Free CRL
o
[SjA
Valuc-Based
Ding
2021 Theorem
[1 11-
ISPLA
Policy-Based
CRFQ Ktetal
Thomem
Value Based
de ml
2011 Theuren 4.3)
0
i1-opte
Policy Dased
7emp al. 3021
Ot- Inc XPD
Thoosom
5
Policy Based
Ding et dl. 2020 Theoeem 1)
0
Policy Based
Ding et al. 20120 Theorem 4)
MDD.F
12 (2-r)6e2
[8]
Poli
Algorithm
Policy-Rased
PD-PG (Thhs Work, Algorithm
Table I: Typical exact gradient and model-free tfae-of-the-and algorithms for constrained RL.
PRELIMINARIES
Constrained Reinforcement Learning. Constrained RL is often formulated a constrained Markov decision process (CMDP), which is the standard Markov decision process (MDP) M augmented with an additional constraint C. A MDP a tuple .M (,,A, P. r, Po: 7). Here S is state space, A is action space. P(s [s, a) is probability of state transition from 8 to after playing a. r(s'|s, a) denotes the reward that the agent observes when state transition from & to 8 after it plays a, and it is bounded as |r(-] < 1. po(.) S - [0, 1] is the initial state distribution and 7 E (0, 1). The policy ग (als) denotes the probability of playing a in state s, and Ils denotes the set of all stationary policies. (s (s) denotes one-step state transformation probability from to by executing т. Let T = {st, at, r++1 ~ be trajectory generated by æ, where 80 ~ -ool)) ar (T((s)), 8141 ~ IP((|ss; ot), and r r($c41|8t, 0t). Let d (s)
7) E.e P = s/sp) be the state distribution of the Markov chain (starting at so) induced by policy n,, and (s)
Eegr<po))) [d (s)]. Let (s) E, 1> 1oc
s| be the state value function. The state- ag a). and advantage function is Ag (s, a) = Qx a) - (s). Finally, we define the objective function ( =
action value function is (s, a) E, 1E === 7"T (so
CMDP extends MDP with an additional constraint set C = {c,, b,)) where G, S R is cost function, each b; is cost limit, and [c;(-) < 1. We define value functions V/e. action-value functions Q and advantage functions Aç: for costs in analogy to Va, QT. and A,, with e; replacing respectively, i 2....... .m]. e.g., Via
E 1E= ('t, as)ss s]. Furthermore, define the expected cost Ci(T) = Ex-po(-) [VS [V]((s)] (s)]. The feasible policy set IIc is defined as follows, 1lc = n { E 1ls and (T)) S b.). The goal of safe RL is to search a policy т satisfies
max J(T), such that c(TT = b.
#eIl,
where the vector c(T) = (CI(#), (2()), ... Om (T)) and b = (b1, (b, b2. ... bm) If the con- strained policy optimization problem (3 exists solution, we denote it as:
n arg max (TT). rElle
According to Bai
2021 Kalagarla et al.
2021 Theorem 1) involves constant C' bounded by [8] [8
UCBVI-- matches the lower bound
(1 9,,2 for MDP (Lattimore & Hutter 2012 Azar et al. 2013
Theorem of Ding al. 2020) shows convergence rate independent S and A. Notice that in Theorem
4 of Ding al. 2020
[ AT samples necessary for the two outer loops.
Bai et al.
2022) claim CSPDA needs O(
(1-1) xi but the inner loop of their Algorithm 1 needs an
[ÁI
additional generative model that needs (T-
I A (is(A))) samples (Agarwal et al.
2020a Chapter 2).
'We show this iteration complexity according to a recent work (Bai et al.
2021).
Since Wei et al. 2021)
study the finite-horizon CMDP, we believe their Triple-Q plays at least O
18
A
'The worst-case of constraint violation shown MMryooseeii Jin 2021
reaches O
if the [1-7)+22
[8 |8
number of constraint function is large than (S].
"Notcee that the inner loop with Ki, (
(-- ) iteration is needed Xu el al.
2021
Theorem 3). Lemma 8-9).
We show the iteration complexity after some simple algehra according
Zeng ct
2021
3

---

Under review as a conference paper at ICLR 2023
Strong Duality. Let À R", and À 0, the Lagrange multiplier function [(T,, X) is defined as: [ A) (z) A (b- c(x)).
(5)
Its associated dual function is defined as: (D = max [(T,, 2), its optimal dual parameter is: arg min (A), i.e., LD(>.) min max L(T,, A). 0 wells
Assumption (Slater Condition), There exists a vector & x 0, and a policy i E IIg such that c(
The Slater condition Slater 1950) is mild in practice (otherwise, we can simply increase the constraint vector b by a tiny amount), and Slater condition standard assumption for CMDP appears in the
previous work (Chow et al. 2018 Paternain et al. 2019a b Le et al. 2019, Ding et al. 2020 Ying
al. 2.2T Slater's condition and convexity of policy class Ilg ensure that strong duality holds. We
formulate the problem ( as the following strong duality version.
Theorem (Strong Duality (Altman 1999)). Let the stationary policy space IIs be a convex set. shares the same optimal solution the following
Under Assumption [ the CMDP problem 3
min-max and max-min problems
Jm,.)
min max L(T, A) max min L(TT, A). X wells
xell, A
Policy Gradient with Softmax Policy, In this paper, we mainly consider softmax policy:
exp(Os.a
(a(a)) EReA exp
v (8, E
where 0 E [AI and each 0[s, a) = 02,a. Finally, we define two additional notations:
a (s) = (At) (s, a), A (s, a), ... A (s, a)) Ano A) = Ano (s, a) A T (8, a).
Proposition Let no be softmax policy (9. the gradient of ((TO) and Ci(TTO) with respect to 0 is:
aJ(me) d (s)mo(als)A.,, (s,a).
0C₁(Te)
d (s))o(((s))A4 (s, (10)
00,aa
00..a 1-
Then the gradients of C(TT. A) with respect to 0 A are:
AL(To.
aC(To. A) b c((T))
dog (1)
(11)
00...
Ox
PRIMAL-DUAL POLICY GRADIENT METHOD
According to strong duality shown in Theorem 1 to solve the constrained RL problem (3), we only need to solve the equivalent unconstrained problem 8 We define primal-dual approach as follows,
AE1I
(A: - v)V>T(TT. 71) 0.+1 < 0, + Vo At),
(12)
where the elements of VoL(Te, Ae) and V V(TT, Ax) are shown in Proposition [ {-) denotes the positive part operator, i.c., if æ S 0. {x}+ = 0, else {x}+ x, and 17 > 0 is step-size. The complete primal-dual approach has been shown in Algorithm [ where we introduce a notation G(0,A) E ( |AA that is the matrix version of aL(mo.)) i.e., each G(0, A) a] is defined as:
86
((0,A)[s 1
d (s) (s, A)
Before we show the convergence rate of Algorithm I we assume that the initial state distribution Po(-) used in the gradient updates is bounded away from zero.
Assumption (Sufficient Exploration). The initial state distribution pa(.) satisfies
Pmin
min {po(s)} 0. sES
(13)
4

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Primal-Dual Policy Gradient (PD-PG)
Initialization: step-size 17, 0g = 0, X 0. policy gradient G(B,)); for / 0, 1. 1.... T do
G(O,, A,) a| I-y deg (s) (als) Aro (s);;
A++1 f {}. 7(b c(TT,)))++
0,41 f 0g + G(,, An);
end for
Assumption 2 has been adapted by Agarwal et al. (020b);; Mei et al. (2020); Ying et al. 2021)
which requires the initial distribution (- lies in the interior of the probability simplex A (S)
(pslp > 0, Exes Ps = 1}. The condition 13) ensures "sufficient exploration", which means that for any policy т E Ilg, the distribution d keeps positive over the state space S. Additionally, Assumption is necessary for global optimality of policy gradient methods. Concretely, |Mei et al. (2020) have shown that there exists an MDP with the condition min,es Po(s) = O, and there exists a parameter 0, such that this 0, is stationary policy of J(To). but no, is not optimal policy.
To short the expression, we define some additional notations. Recall 5 == (61, E2, ... [m) T
defined in Assumption I i..., Ea 0, i = 1,2, m, let minigigm { e: 1+ (1-7)).22
2m
d
d (a) Finaaly, let po(a)
The distribution mismatch coefficient is defined as:
== max.cs
(e(als) == no, (a|s), and T.. == no,-
(14)
From stating this and the remaining results, we fix deterministic optimal policy n. (-Is), denote it as a. (s), i.e., v. (a, (s)ls) 1; a a. T. (als) O.
Proposition 2. Under Assumption 2 updating गe according to Algorithm 7 we obtain
C = .68,121
inf (x)((())))))) > O.
(15)
We provide the proof in Appendix D.1 (see Lemma 15). According to 15 C, is a positive scalar independent the time-step & and independent on the state space S. Theorem 2. Under Assumption
2
To is the softmax policy defined in
9 Let time-step T satisfy
1
D
T2 max
(16)
(1- ((1 (1-7) 7)2 + 2m/12)²
S log [ D1
where D1 and D2 are positive scalars will be special later. The sequence {Ax, 0 is generated
by Algorithm| Let Let
-
log C(1
deo Po
1o5) (1-7)"ee,
where C a positive
scalar will be special later. Then for all {1,2,
m), Te == To. satisfies
log IA V [1,(1 27
min (J(T.) J(T() <
nr
(17)
KT
Pu
4g
deg
|S log IA|
min (C.(Te)) - bi) 3 t<T
(18)
oc
Po
c+(1 TT
Remark 1. Lemma (see Appendix B.3 has shown the boundedness of X as follows: || 2
Furthermore, according to the discussions in Remark 3 3 Appendix D.2), the inequality
(1-7)
3>
(1-7)e always holds. Thus 3 > |> which implies the bounds 17) and 18) are well-defined.
Remark 2. Theorem
2 Qimplies Algorithm 7 needs the iteration complexity of
deo m
|S| LAI
(19)
Po
c1 7)
obtain optimmalll, The iteration complexity of (19 is functionn with respect the toleration e, which matches the best known policy gradient methods from (Ding et al.) 2020) for CMDP, where both NPD-PG (Ding et al. 2020 and the proposed PD-PG share complexity of (
5

---

Under review as a conference paper at ICLR 2023
4 PRIMAL-DUAL METHOD TO SOLVE MODEL-FREE CONSTRAINED RL
The main difficulty to implementing a model-free algorithm lies in designing an efficient policy gradient estimator for the discounted infinite-horizon MDP, which is intractable for sampling-base policy optimization since requires a trajectory with an infinite horizon, which is impossible for practical simulation. In Section 4.2 4.3 we present an unbiased value function and policy gradient estimators with finite horizon trajectory. which the benchmark for us to propose sample- based algorithms. The proposed algorithm and convergence analysis lie in Section 4.4 4.5
4.1 DILEMMA IN MONTE-CARLA ROLLOUT
Recall Proposition I the following two conditions:
to obtain unbiased estimators of (J() and (C,(xe), it is necessary to satisfy 00,,
20,,a
. (C1): draw the state-action pair (s, a) according to: (s. ~ (d (-), To(-ss)):
(C2): obtain the unbiassed estimator of the advantage functions Aro (8, a) and A (s, a).
(st s|so)] for model- free RL, since the transformation probability Pro (st = s|su) unknown. Additionally, Monte-Carle campling-based approach to obtain an unbiased rollout is a theoretically possible but intractable estimator of A (s, a), which requires us to run infinite-horizon trajectories to estimate the value start from (so, ao) (s,a).
However, we can not obtain exact d (s) Ess~poo))(( - -i)
functions. For example, let ((5t, oz, r(s),(()))))))) ac)) li20
80
((s, a) = Σ )'r(st,
(20)
t=
is an unbiased estimators of QTo (s, a). Despite the unbiasedness of @ a), Monte-Cario rollout (20) requires infinite number of horizons, which is impossible in practice.
4.2
UNBIASED VALUE FUNCTION ESTIMATOR WITH FINITE HORIZON TRAJECTORY
Both of the conditions (C1) and (C2) can be implemented via geometric random variable horizon during the simulated process (Paternaim 2018 Chapter 6). Now, we present the insights behind this process, which requires us to master geometric distribution Geo(-), see Appendix E.
Recall the Monte-Carlo rollout (2)). if y O, then infinite series Q(s, a) (0) prioritizes the present reward information. In that sense, when y is very small, we do not need to require the agent to evolve to collect the future reward for long time. On the contrary, y = 1, we need to require the agent to look far away into the future reward information. The geometric distribution provides us a way to formulate this idea (Paternain] 2018). Concretely, let Geo(1 - 7), and rollout finite horizon trajectory as D, {s, a,, ((5t, Ft)Ft= ~ т,, where the initial state-action (sp, ao) (s. a). Then, we define an estimator of Qx (s, a) according the sum of reward along the trajectory D,:
Qr( = Σ r(se, az).
(21)
1=
This (s, a) unbiasedly estimates (s, a) for each (s, a). Such a programming 21 can be extended cost function if we use c2 (-) to replace r(-) respectively, and can be extended to Vj (s) and Vi (s) if DD starts from s.
Due to the limitation of space, we have provided the details of implementation to estimate Qu and V in Algorithm 4 (denoted as EstQ(T, g. s, a)) and Algorithm 5 (denoted as BstV(T.0 g, s, a)), see Appendix E.2 where we denote it as EstQ( g. a). where g r(-) or g c(-). The next Proposition 3 show that Algarithm and Algorithm Jotputt unbiased estimators for value functions.
We have provided the proof in Appendix H.3
Proposition (Unbiasedness of Algorithm
Let (s, Esto( Q: (s,a)
EstQ((T, G, 8, a), then the following holds: E E (s, a)] = a). Q7
Proposition 4 (Unbiasedness of Algorithm 5 Let Vx(()) = EstV(T, (C(() =
EstV(T, Gi 8), then the following holds: E (x) = V*(s), E (s,a))= (s)

---

Under review as a conference paper at ICLR 2023
Algorithm 2 PG( 9, s, a): Estimate Policy Gradient
Input: Policy no: Reward function or Cost function g(: :); State-action pair (s,a);
2: First Rollout: Q(s, a) = ( 9, 8, a), let 7 ~ Geo(1 - 7) denote the terminal time;
3: Second Rollout:
(1-) = EstQ no, 9, Sr; (r), let
Geo -) denote the terminal
time; collect the trajectory {(5,, aj. g(8). aj) J= where the initial (50. ap) (r);
θ log No (0)((18))
Output: G(s,a) 1-9 ((T. ar)
4:
06,,0
4.3 UNBIASED POLICY GRADIENT ESTIMATOR
Now, we introduce an unbiased policy gradient estimator, which involves two rollouts.
First Rollout: we play rollout with respect ιe according Algorithm
T.yy (s, a) E T, s,
(22)
we use T Geo - 7) to denote the finite terminal time of the horizon of the rollout (2)
Second Rollout: we play rollout for the last state-action pair (s+, a.) according to Algorithm
@no (8y, a,) = Est Q 87, a.).
(23)
Let r' Geo(1 7) be the terminal time of the rollout (3 and we denote it as D' (s a j=b:r" where the initial state-action pair (s au) (sy, a,).
Output: let G.ng (s,a) a) be estimator defined as follows,
Gro - 2To ( a,)
1
2 log To (ar ( (8T)
(24)
00 s.a
Since return objective (TO) and cost function (TT) share similar structure, all the estimators
(22 224 can be extended to C((TT) if we use to replace r respectively. We have provided such policy gradient estimator with finite horizon trajectory in Algorithm 2 and denote it PG(T,, 9, 8, a).
Theorem 3. Let To be the softmax policy (9) and Goo as = PG(TO, r, s, a), G (s, a) =
PG( G2 8, a), Then G.o a) and Go (8, a) satisfy
E B|Gro (s, a)] = @
E(G2, S (1 (1-7)) 73)3
4
00.,
(T)(TT)
4
E E|Ga (s, a)] 00..
B[(G&, (s. a)) S (1 733
Theorem has guaranteed the unbiasedness and boundedness of the estimator PG(R, g, 5, a), which is the benchmark for us to show theoretical results. We provide its proof in Appendix E.4
4.4 MODEL-FREE ALGORITIIM DERIVATION
We have shown model-free PD-PG Algorithm 3 To show a stochastic primal-dual implementation, the iteration 12 implies that we need to estimate ac( and @C(xo.A) ax
80
Estimator for (C(=..)) We obtain the estimators of the cost value function: 0X EstV(TT, Cr2 s). Furthermore, let Či(TT) E.es Po(s) Pols) (s), and
Des (s)
c(Tо) - (z(TT), .... TTo))
(25)
then according to Proposition b - é(ma) is an unbiased estimator of #[(To.N) policy parameter 0, the following holds
i.e., for any given
dA
ØL(TO. A)
E b - -(Te)
ax
7

---

Under review as a conference paper at ICLR 2023
Algorithm 3 Primal-Dual Approach to Model-Frree Safe RL
1: Initialization: step-size 7/. 0o O, and Lagrange multiplier Ao O;
2: for / 0, 0, 2.
do
3: # Estimate @c(Te, Ad)) Obtain cost value estimator Č(TTO) according to 25 Let ax
4:
Vx, C(TO, Ar) = -b-è(Toe)
5: # Estimate
aC(To, As)) 80,
Let G Ar) al -GT, ()
Nigre, (s, a): calculate
Vo T(To, 2x) = G(TTO,:)))
6: #Primal-Dual Update for Parameters.
A+t1 = {>, - 17 C.To A1) = 0, toVo Ad);
7: end for
Estimator for @C(ng.A) According to Algorithm
we obtain the policy gradient estimators with
80
respect 86,,
@J(ma) and @Ci(ne)
as follows,
39,,
Gro (8, F, Go (8. = PG
(26)
Let g (s, a) = (G (s, a), Gr (s, a). ... Gcm (s, a)) collect all the policy gradient estimators of cost value function. Let the matrix G A) R| and each element G( A) a] is:
G A) = G.o (s, a) x g (s,
(27)
Then according to Theorem (Tg. A) an unbiased estimator of @C(ss.A)
00
Stochastic Primal-Dual Iteration. We rewrite the iteration 12 the following stochastic version,
A - { 1/(b é(TTo_ 02 + +)((me
(28)
where we calculate é(To,-1) and G 11- according to estimator (5) and estimator (7
4.5 CONVERGENCE RATE
For each time I, notice the estimator ê(TT) the inner loop (see Line of Algorithm involves m trajectories, and estimator G Ax) (see Line 5 of Algorithm involves (2|5]|AA + trajectories. We use D, to collect all those [2]S||A| + 2m) trajectories,
D; {T, (15))
(29)
According to rollout rule in Algorithm trajectories among D, are independent with each other.
4 Algorithm 5 and Algorithm 2 those (2[8]|A) + 2m)
Theorem 4. Under Assumption
? Tg the softmax policy
9 The time-step T shares a fixed low
bound similar to 16). The initial Xo 0, 0, 0, the parameter sequence {>x, T.TTT is generated according to Algorithm
Let n, B satisfy rj
[S] log LAI 3 V no (1-7)
d 1 log LAI
O' (1-2)
where C' is a positive scalar will be special later. Then for all E {1,2, (1,2,...,m) m. me = ne, satisfies
deo
S log (A] C.
E
min (J(m.) [(me))
KTT
Pu
7
dPo
|S| log [A]
E
min (Ci(Te)
bi]
<
KT
Po
A aow
+)
where the notation B[| is short for Ep.:Dr= randomness the trajectories (-D))--)
[:] that denotes the expectation with respect to the
8

---

Under review as a conference paper at ICLR 2023
The details of the proof is in Appendix F2 and the unbiased policy gradient estimator and the independent samples among De play a critical role for us to obtain the Theorem 4 According to (29). we need [2|S]||A] + 2m) trajectories to rollout the policy gradient estimator, Theorem implies
Algorithm needs a total iteration complexity of
deo
2
|S|
[|||A| + m
log LA|
(30)
Po
c1 +)
to obtain (cc) optimallty The iteration complexity shown in (30) matches the best known algorithm NPD-PG et al. (2020). NPD-PG (Ding et al. (2000) and the proposed PD-PG share a complexity
of O which is better than CRPO (Xu et al. 2021) that with ((e and on-line NPD-PG
(Zeng et al. 2021) that is with (c=9))
4.6
COMMENT ON (DIG ET AL.. 2020): A TRADE-OFF BETWEEN PD-PG AND NPD-PG
The initial 6g = 0 implies the distribution of initial policy is uniform, which implies To [s) |A|-1 Then is upper bounded follows, C. inf,es, (s)(ss))))) S [A|-1, which implies the iteration complexity of the proposed PD-PG (30) is lower bounded as follows,
(1
de Po
|5/3|,412 7)-
(31)
to obtain O(e)-optimality, where we omit the constant m (that is the number of constraints), and (-) to hide polylogarithmic factors in the input parameters. According to (Ding al. 2020 Theorem 4), the complexity of NPD-PG is upper bounded by
ō ( |SP| (1-
(32)
Although the proposed PD-PG shares the same state-action independent iteration complexity of O with NPD-PG, the state-action dependent iteration complexity (31) and (32) implies PD-PG is difficult than NPD-PG (Ding al. 2020) due to the following two aspects. Firstly, the lower bound 31 w.r. PD-PG and the upper bound (32) w.r.t NPD-PG implies NPD-PG plays never worse
than PD-PG. Additionally, the bound w.r. PD-PG 31 involves the distribution mismatch coefficient deo
which heavily depends on the initial distribution po(-). Concretely, if po(-) is near 0 at
Pu
some state, then distribution mismatch coefficient can be very large, which is indeed detrimental for PD-PG to search safe policy. In this sense, it also demonstrates the necessity of Assumption [
However, although the upper bound (32 w.r. NPD-PG does not contain the distribution mismatch coefficient, the NPD-PG (Ding et al. 2020 requires additional computation w.r.t the Moore-Penrose pseudo inverse (f)) where F(A) is the Fisher information matrix:
F(0) = E 2o (r)
[ log To (a)ss) (V log =
Thus, there exists a hidden off between PD-PG and NPD-PG. Finally, we should emphasize that trade-off is hidden due to the notation (-)) covers some information w.r.t MDP or policy space.
5 CONCLUSION
This work proposes PD-PG algorithm to solve constrained reinforcement learning problem, which a Lagrangian- based algorithm with policy gradient. Although the maximization objective is non- concave and the minimization is non-convex over the parameter space, we show that for both exact policy gradient and model-free learning, PD-PG converges to the optimal solution at sublinear rate for both reward objective and safety constraint. Since consider discounted infinite-horizon CMDP, we consider unbiased estimators with inite-horizon trajectories, which plays a critical role for us to obtain the iteration complexity of sample-base based PD-PG. Additionally, investigate that PD-PG needs a complexity of Ó (c=?) to obtain O(e)- ((())oopimallty. which is comparable to sfate-of the-art algorithms available in the literature in constrained RI.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International Conference on Machine Learning, pp. 22-31. PMLR, 2017.
Alekh Agarwal, Nan Jiang, Sham M.Kakade, and Sun Wen, Reinforcement learning: Theory and algorithms. Princeton university press, 2020a.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods markov decision processes. Conferecnce on Learning Theory (COLT), 2020b.
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.
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax pac bounds on the sample complexity reinforcement learning with generative model. Machine learning, 91(3): 325-349, 2013.
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.063: 2021.
Dimitri P Bertsekas. Constrained optimization and Lagrange multiplier methods. Academic press, 2014.
Homanga Bharadhwaj, Aviral Kumar, Nicholas Rhinehart, Sergey Levine, Florian Shkurti, and Animesh Garg. Conservative safety critics for exploration. In International Conference on Learning Representations (ICLR), 2021.
Shalabh Bhatnagar and K Lakshmanan. An online actor-crite criticc algorithm with function approximation for constrained markov decision processes. Journal of Optimization Theory and Applications, 153 (3):6887708) 2012.
Vivek S Borkar. An actor-critic algorithm for constrained markov decision processes. Systems & control letters, 5403):20--213, 2005.
Kianté Brantley, Miroslav Dudik, Thodoris Lykouris, Sobhan Miryoosefi, Max Simchowitz, Alcksan- drs Slivkins, and Wen Sun. Constrained episodic reinforcement learning in concave-convex and knapsack settings. Advances in Newral Information Processing Systems (NeurIPS), 2020.
Miguel Calvo-Fullans, Santiago Paternain, Luiz FO Chamon, and Alejandro Ribeiro. State augmented constrained reinforcement learning: Overcoming the limitations learning with rewards. In International Conference Machine Learning, 2021.
Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18(1):6070-6120 2017.
Yinlam Chow, Ofir Nachum, Edgar Mhenez-Guzmant and Mohammad Ghavamzadeh. A Ayapunov- based approach to safe reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Marc Peter Deisenroth, Gerhard Neumann, and Jan Peters. A survey policy search for robotics. Foundations and Trends@ in Machine Learning, 2013.
Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo R Jovanovie. Natural policy gradient primal-dual method for constrained markov decision processes. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
10

---

Under review as a conference paper at ICLR 2023
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligence and Statistics. pp. 3304-3312. PMLR, 2021.
Rick Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-explootaainn in constrained mdps. arXiv preprint arXiv:2003.02/88 2020.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for discounted mdps. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of International Conference on Machine Learning (ICML), volume 2, pp. 267-274, 2002.
Sham M Kakade. A natural policy gradient. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1531-1538, 2002.
Krishna C. Kalagarla, Rahul Jain, and Pierluigi Nuzzo. A sample-efficient algorithm for episodic finite-horizon mdp with constraints. Proceedings of the AAAI Conference on Artificial Intelligence, 35(9):8030-800) May 2021.
Alec Koppel, Kaiqing Zhang, Hao Zhu, and Tamer Başar. Projected stochastic primal-dual method for constrained online learning with kernels. IEFE Transactions on Signal Processing, 67(10):
2019.
Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. arXiv preprint arXiv:2102.001335 2021.
Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. In Proceedings of the 23rd International Conference Algorithmic Learning Theory, ALT' 12, pp. 320-334, 2012.
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Interna-
tional Conference on Machine Learning (ICML), pp. 3703-3712, 2019.
Qingkai Liang, Fanyu Que, and Eytan Modiano. Accelerated primal-dual policy optimization for safe reinforcement learning. arXiv preprint arXiv: (80.0068000 2018.
Tao Liu, Ruida Zhou, Dileep Kalathil, P. R. Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Yongshuai Liu, Jiaxin Ding, and Xin Liu. Ipo: Interior-point policy optimization under constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 4940-4944 2020.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pp- 6820-6829, PMLR, 2020.
Sobhan Miryoosefi and Chi Jin. A simple reward-free approach to constrained reinforcement learning. arXiv preprini urXiv:2107.052166 2021.
Sobhan Miryoosefi, Kianté Brantley, Hal Daumé III, Miroslav Dudík, and Robert Schapire. Re- inforcement learning with convex constraints. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
OpenAl. Openai five defeats dota 2 world champions, 2019. httpps::/ppeaaa.ccmm/bbbb//////a Lpeeral-iivve-eeefattddd--------
ons/
Santiago Paternain. Stochastic control foundations of autonomous behavior. PhD thesis, University of Pennsylvania, 2018
Santiago Paternain, Miguel Calvo-Fullana, Luiz FO Chamon, and Alejandro Ribeiro. Safe policies for reinforcement learning via primal-dual methods. arXiv preprint 1.000000,, 2019a.
11

---

Under review as a conference paper at ICLR 2023
Santiago Paternain, Luiz FO Chamon, Miguel Calvo Calvo-Fullana, and Alejandro Ribeiro. Constrained reinforcement learning has zero duality gap. In Advances in Neural Information Processing Systems (NeurIPS), 2019b.
Panagiotis Petsagkourakis, Ilya Orson Sandoval, Eric Bradford, Dongda Zhang, and Ehecatl Antonio del Rio-Chanona. Constrained reinforcement learning for dynamic optimization under uncertainty, Pape-nnaprs, 53(2): 1264-11270, 2020.
Zengyi Qin, Yuxiao Chen, and Chuchu Fan. Density constrained reinforcement learning. In International Conference Machine Learning, pp. 8682-8692. PMLR, 2021.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge, Nature, 550(7676)3354, 2017.
Morton Slater. Lagrange multipliers revisited: contribution to non-linear programming. 1950.
Sungryull Sohn, Sungtae Lee, Jongwook Choi, Harm van Seijen, Mehdi Fatemi, and Honglak Lec. Shortest-path constrained reinforcement learning for sparse reward tasks. In International Conference on Machine Learning, 2021.
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1057-1063, 2000.
Chen Tessler, Daniel J Mankowitz, and Shie Mannor. Reward constrained policy optimization. International Conference on Learning Representation (ICLR), 2019.
Oriol Vinyals, Igor Babuschkin, Junyoung Chung, Michael Mathieu, Max Jaderberg, Wojeiech M Czarnecki, Andrew Dudzik, Aja Huang, Petko Georgiev, Richard Powell, et al. Alphastar: Mastering the real-time strategy game starcraft ii. DeepMind blog, 2, 2019.
Akifumi Wachi and Yanan Sui. Safe reinforcement learning in constrained markov decision processes. In International Conference on Machine Learning, pp. 9797-9800 PMLR, 2020.
Akifumi Wachi, Wei Yunyue, and Sui Yanan. Safe policy optimization with local generalized linear function approximations. In Advances in Neural Information Processing Systems (NeurlPS), 2021.
Nolan Wagener, Byron Boots, and Ching-An Cheng. Safe reinforcement learning using advantage- based intervention. In International Conference on Machine Learning, 2021.
Honghao Wei, Xin Liu, and Lei Ying. A provably-efficient model-free algorithm for constrained markov decision processes. urXiv preprint 2rX1iv22006.0157,, 2021.
Ronald J Williams.
Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229255 1992.
Tengyu Xu, Yingbin Liang, and Guanghui Lan. Crpo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pp. 11480-1 1149. PMLR, 2021.
Tsung- Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter Ramadge. Projection based constrained policy optimization. In International Conference on Learning Representations (ICLR), 2020.
Donghao Ying, Yuhao Ding, and Javad Lavaci. A dual approach to constrained markov decision processes with entropy regularization. arXiv preprint arXiv:2110.0880 10.0823,, 2021.
Ming Yu, Zhuoran Yang, Mladen Kolar, and Zhaoran Wang. Convergent policy optimization for safe reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS). 2019.
Sihan Zeng, Thinh T Doan, and Justin Romberg. Finite-time complexity of online primal-dual natural actor-critic algorithm for constrained markov decision processes. arXiv preprint arXiv:21 11383, 2021.
12

---

Under review as a conference paper at ICLR 2023
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58(6): 3586-3612, 2020.
13

---

Under review as a conference paper at ICLR 2023
A
NOTATIONS
For any positive integer m, [m] == f1,2. .1. We use bold capital letter to denote matrix, e.g.,
.m}. A (as,)) TR and (i. element denoted as A ji = at.js where E [m]:j [n].
bold lowercase letter denotes vector, e.g., (41, On) E IR" and a ==
A.1
VECTOR AND MATRIX
1m
1m R" and each element of vector 1m is 1, i.c., 1m (1, 1,
1).
0m
Om E Rm, and each element of vector 0m is 1. i.e. 0m (0,0, 0)
It denotes component- -wise order, i.e., afj] b E m]].
b
It denotes component -wise order, i.c., aßj] < b E mm..
A.2 MARKOV DECISION PROCESS
S The set of states.
(S)
The interior of the probability simplex over the state space S
A* = Ps Ps
0. Σ Ps =
#ES
A
The set of actions.
P(8 (8,a)
The probability of state transition from 8 to 8 under playing the action a.
r(-)
The reward function r(-) S x S A - R. and it is bounded by |r()] < 1.
p + [0, 1] is the initial state distribution.
Po
7
The discount factor, and (0, 1).
A.3
STATE DISTRIBUTION
(x (so)
The probability of single step state transformation probability from s to s' by executing
(st
The probability of visiting the state 8, after t time steps from the initial state 8p by executing тe. The state transition probability matrix, and its (s, >-th component is
P.
P [s
Σ [(als))Pssssss a) = (s
d (s), due (s)
a The discounted stationary state distribution of the Markov chain (starting at so) induced by m.
(g)(( (s)
(P = s|su), dhe Exo- 200-po())dd, (s)].
doo
1=0
The distribution mismatch coefficient, i.e..
Po oo
deo
dea (s) (o(s) max eES
Po
doc
Due to the Assumption
the term
is well-defined.
(o(s)
14

---

Under review as a conference paper at ICLR 2023
A.4
STATE, STATE- ACTION AND COST VALUE FUNCTION
(s)
State value function (*( E Et 2 180 5].
(s,a)
State-action value function (s. a) = E, 1,1E; 00 7 0, a].
(8
Advantage function (8, = (8, a) (+).).
[(T
The objective function.
The constraint set C = {(c,, b,)) where b, are limited values, and cost function cj C S A RR and is bounded by |ci(-) I
b
The vector stores all the limited values: b = (b,, b2. :.. )
(8)
State cost value function (8) = En 15 70c 0z =
2 (s,
sate-action cost function (=) E, 1 ? ar]ssp s, ag a).
AG (8,a)
Advantage function A (8, a) + (8,a) (s)
CT(T)
The expected cost value function (.( ( (-) [V (8)).
c(T)
The vector stores all the expected cost values:
c(π) (E(T) (T))
Iee
The feasible policy set IIe is defined as follows,
m
1c 0 { IIs and C+(x) < b.).
A.5 PARAMETER
A
Lagrange multiplier parameter, À IR... Optimal dual parameter X, = arg min max +A() (b--c())))
X
A.6
CONSTANT
Pmin
Sufficient exploration condition Pmin minges (p)
The dimension of the vector b, i.e the number of the constrained conditions
E
component-wise negitive vector defined in Assumption (E1, { < 0, and each & < 0, i= 1, m.
E
positive constant == minisis [-
2m
A positive constant @ = 1+ (1-7)222
D1, D2
Two positive constants that defined in Eq. 173
15

---

Under review as a conference paper at ICLR 2023
B PRELIMINARIES AND AUXILIARY LEMMA
B.1 STATE DISTRIBUTION
We use Px ||S|X|S| denote the state transition matrix by executing n, and their components are:
[ s'1 Σ
x(als)P(s'|s,a) = Pn 8, E S,
aEA
which denotes one-step state transformation probability from to s'.
We use P- (s, = s s|50) to denote the probability visiting s after time steps from the initial state so by executing и. Particularly, notice if t 8t # so. then PP (s+ s|so) 0, i.e.
Pa (3+ = s|50) = 0, = 0 and s + so.
(33)
Then for any initial state 80 ~ p(-), the following holds,
P=(s: s|su)
Σ
PT s|sc-1 )T =s(s)))
(34)
ES
In this paper, we also use p(() to denote Pr (8t = s s'1s), i.e..
p!u) ss (s) P= 1s0 = s).
Recall d denotes the normalized discounted distribution of the future state encountered starting at so by executing x,
d (8) (1 7)
IP= (x: = s/80)-
(35)
t=
Furthermore, since 80 ~ po(.), we define
d Eso po() [s)
pd( (s)
J
as the discounted state visitation distribution over the initial distribution po(-)
B.2 PERFORMANCE DIFFRRENCE LEMMA
Lemma (Performance Difference (Kakade Langford 2002)).
For any policies a and n', 8g ~ ))(.), and for each i 1,2, ................................ ,, the following performance (or cost) difference holds
J(x) J(a')
1- Eg ()
[A_ (s,((s)))) (s,a)).
(36)
- I- E B amm 4 (s, a)
(37)
B.3 BASIC FACTS
In this section, we present basic facts will be use later, those results adaptive to Ding et al.) 2020), and we extend them to the versions of vectors.
Recall (A( max L(m, A), for give scalar E R, define notation
[(c) = (A= (o(A)ss))
We notice the following inequality alway holds
max min L(T,, A) < min max L(w, A) = min (p()), Ellls X
(38)
X
X
c < max+en,, minAzo L(TT, A) paper.
J(T,), then I(c) = 0. We assume c 2 J(R.) throughout this
16

---

Under review as a conference paper at ICLR 2023
Lemma 2. Recall the optimal dual variable X, min (D(A), let (T.)), the following holds
X (c).
(39)
Proof. If we choose == J(T.), , and let À E F(c), then by the definition of [c), we achieve
()(
max [(T,, A) S ( mElla
max min [(T,, A). #llls A
(40)
x = 0). combining the result
Let's maximize the left-hand of Eq. 40 overset the space the vector À satisfies
38 then
max min [(x, A) = min max L(T, A), Tllls o
(41)
λzo xElla
which implies Ā = >., further it implies
A (J(TT))
(42)
With the result Lemma 2 we denote the set of all optimal dual variables as D,, i.e.,
(X r-:{(A
r. r.:=
arg min CD(A)} (J(TT)) 2
arg
Lemma 3. Consider the policy satisfies Assumption 7
let X E I(c), then the following holds
C-J( -
Furthermore, the optimal dual variable X is bounded as follows,
|x - (JT.)) ((x)) (1 7)
2
Proof. Let X I(c), and recall Assumption and (A( maxxells L(T, A), then
(D(A) (#) + T (b- c(a)) ( X ATe
which implies
c (()) 2 -
(43)
Furthermore, according to Lemma
if J [TT,, then for each A, E T (J(r.)), E3 implies
J(π.) J(+) ス X (-
(44)
Recall Assumption we know & - i... & == (51, Ez. ... Sm) T x 0, which implies each & < i == 1,2, m. Let
1 = min {-E:}-
15$5
then is a positive scalar, and - > 11m- Let X, = (Xi, Xo. ... A ) since X > 0, then each X 2 0. Furthermore,
||>|llo = max{X; Xg, Xr Nr according to Eq. 44 we achieve
J(T.) - J(T) 2 A 1m Σ
x 2 1/ Ax
(45)
which implies
| W 1 (J(T.)- $ (1 (1-7)L"
(46)
17

---

Under review as a conference paper at ICLR 2023
Lemma 4. Let 4 > |2,1l and for any policy it such that
+ - bb+
(47)
then
5
(m())) bb < 40 10
(48)
Proof. Let
v(w) = max [J and b c(TT) w) =llls
according to Paternain et al.
2019b): Ding et al. 22220) v(w) is concave. We notice J(T.) = v(O).
Recall A, arg minx=o (A), then according to Theorem we achieve
C( max [(T,, A.) LD(..) - (TT) = v()), Vi E lls. mells
(49)
Then, for each æ such that
a E E TTs :.:bb.. b c(x))= ビ w)
the following holds
(0) A
L(T, X.) \ J(T) N (b. c(T)) - X w 2 J(T),
(50)
where the last Eq. 50) holds: since b c(T) ž w. then A (b c(T)) X. 2 0.
Let's maximize the right-hand of Eq. 50 with respect to over the space { E IT b -((T) 2 w). then achieve
v(0) X w 2 v(w).
(51)
Furthermore, if we choose then
3 = (c(+) b)+,
(52)
(( < ((T.) = v0) S v(5))
(53)
where the last inequality holds since
{ b c( > {T b c(T) 2 a).
Finally, considering the results from [5] to (33 we have
( - J(T.)
v(w) ((Tx) -v)
- w.
(54)
Consider the condition (7).
47
8 JTT.) - J(x) + (1 -b}+
X, ④ + p1 (c(ā) b)+
(p1m - A.) (c(ā) b}+ (pp - |>, 1 - bb++
(55)
where the last inequality holds: since 80 > || blo then the following equation always holds
1lm - X z (s 11+
Eq. (55)
implies
5
(c( b)+ p-112,1a
(56)
18

---

Under review as a conference paper at ICLR 2023
C POLICY GRADIENT W.R.T. OBJECTIVE AND COST VALUE FUNCTION
Although some similar results with respect to Proposition I have appeared in Agarwal et al. 2020b :
Mei al. 2020); Lan
202Tp. also need to provide the details since we will use some key details
DTo (s'ss)) which plays a critical role to
later. Before we show Proposition
we need to calculate
20..a
proof Proposition
Lemma 5. Let be the softmax policy defined in then
@mo(a'ls)
a
exp(0,,a')
00 8.0
00.,a
Eãee expl0,'a)
exp(0, |/aEA exp(t, -
exp(ox 00,,a
00,0
(
al)
exp(Os.a H HEãC exp(0s,a)) (cxp(0s,a)) (CREA (x.)))
if and a
expl0 (exp(
if = and a # a;
(EEE exp(o,,a))
0,
if + a # a;
(a(as) (#o()))))
ifs and a a;
To(a (s)ss(ass)
if and a # a;
(57)
0.
if + 8 or a #
Proposition 1 Under the softmax policy parameterization 9 the gradient of the objective J (Te) and cost (T)) with respect to 0 is
(me)
1
den (s)mo(als)) (s, (s,
00,,a
1
(Ta()T))
1
d (s) (8.
00
1
Furthermore, let
a (s. a) = (A (s, a), A (s, a), A (s)
Ano (8, A) = ATo (8, a) A a (8)
then the gradients of C(TO, A) with respect to 0. are:
AL(TO, A)
aC(To. A)
doo (s (s)T (s)
c(TO).
(58)
00,n 1
aJ(TO)
Proof. Since J(TT) = Eggdag (-) |Va (8)], to derive the gradient
we only need to show
00,a
@V (50)
According to the relationship between VTo (s) and Q a):
30.n
VA (50) = Σ
To(a (s0) (s..)))
a' EE
19

---

Under review as a conference paper at ICLR 2023
then we have
0V (s0)
@ag(a (s0) 00..0
Quo (50, a') To(a aQ (
Σ
(59)
00 8,0
00
d'EA
Due to the equation
Σ
p(sils, a)r(s')ss +7
Σ
P(s ((
s'ES
e'ES
we achieve the gradient of QT with respect to 0 as follows,
0Q (80, a')
P(s |s: a') Vo (8)
Σ
(60)
00 P.a
00,.
e'ES
Taking 66 to Eq. 59 we have
@V (00)
@rola (s0)
P(s (so, [V==0s)) (s')
a'o
Σ
Qro Qro (80, yoo((alss)
(so)
Σ
00,00
00,,a
00,,a
a' EA
e'ES
Orola (so) 20,,a
OV (8')
Qro (80,
('s..a)) +7
Σ
Σ
Ta (o)P(s(1s,,d)
00,aa
d'EA
s'ES
(aEEA
=Pag (0)=51
@mola' 180) Qro (80. +7 Σ
OV (8)
(s1 5 (50)
(61)
20,a
00.,
a'Ed
S'ES
which implies for each E N+ the following equation holds:
@Va
@mo(a'ls')
0V (s")
Q:o (s',a') +
Σ
( = (ss
(62)
00,.0
20..o
00,,a
E'EAA
s'ES
Considering Eq.(62)
with the case / 1, we write Eq. (6 follows,
δro(a (su)
Σ
Qxo (su. a')
00..a
00,a
d'EA
(no (no +y Σ
aV (8
+ Σ
Pro (81 = s
Σ EA
Pro (32 s =
00,,
00 n.a
o' ES
s"ES
(63)
According to (4.
34
the following equation holds
P x (s)
=s (1s)))PP
-r (s2 s" s1 s11s| s') =P (52 s s')s)):
ees
VV (so) as follows,
and taking it to Eq.
63 we achieve the gradient
00,a
@V (s0)
ra 1s0)
Pro (81 = =8/100) Σ OTo(d'ls)
Σ
Q:o (80, a')+7 + Σ
(
00
00,,a
a'Ed
a'ES
a'EA
TV. (s")
+
ΣΣ J'ESS'SS
(s1 = 130) P (32 = = 5
00.m
@mola' (80)
@mo(a
Quo (50, a') +y Σ Σ
Pro (si ss100)
Qno (s
20,,
80..
d'Ed
d'EASESS
OV.o (s")
+ 2
P (82 = "10))
(80) 08.0
(64)
8" cs
20

---

Under review as a conference paper at ICLR 2023
5o (so)
Furthermore, according to (64, we analyze
as follows,
08 8,a
TV
@mo(a
(80)
PP (51 =8 =1180) @mo(a'ls))
(s0
+y
Σ
Σ
(s
00,,0
00,,a
00z,a
E'EA
a' ESS
Oko(a'ls"
= )) [v (s")
+ 72
(52 = =s
Qno (s aa)) +7 Σ
PRO (53 = m 182
00s.
00.,
E"
a'EA
s"
@To(a'lsi
OTo(a'ss)
(su. a')+
Σ
(Pooo = =5(00)= + + P no
(s2 s [1ss)
2no as
00.a
00,.a
d'EA
d'EAS'ES
3
PrO (53 = (s0)
(s)
00..a
@ro(a'ls)
Σ
P no (st = =s(ss))
Qno
(65)
00..a
d'EAs'e ES 1=U
1
Σ
d (s')
Orola'ls')
Σ
d (s)
Onola (s)
Quo (s, a')
00.a
1
08,aa
a' L'EASEES
a'EA
a'
(66)
1
do (s) (s)so(a)ss)
(s, - Σ To(a'ls)Qno (s,
(67)
1 ?
d'EA
1 deo TT) 8) (Qro(s, (s)
1
1 - 150 (a) (r
(68)
where Eq.16 holds since if * 8, then
Ime (a Is') 0;
20,,a
Eq. holds due to (5)
(57
Finally, since J(TT) E
so (-) [V (su)], then
( E. Bso~po())
1
1
d (s) (s)
dea (s)mo((ls)AAn) (8, a).
00..a
1 --
1-
Similarly,
(To)
den (s) (s, a).
00.a.
This concludes the proof of Proposition
1
Let
a (s. (A% as, A% (s,
A (s)
then
Oc(TTo)
aC2(TT) ()C)(T))
aCm(
00 00.a
20,a
00,m.
00 20,0a
doo (T)TT( (a (a|s) (A (8, a), A (8,a)."
A (s)
deg (a) as)
With the result in Proposition I it is easy to calculate the gradient of L( A) (5) with respect to 0. X, formally, we present it in the following Proposition 5
21

---

Under review as a conference paper at ICLR 2023
Proposition 5. Consider the Lagrange multiplier C( X) (5). its gradient with respect
0, A is:
0
1
[( A)
1-7 d (s) (s, A ala (s,
(69)
09 8.0
((To = bb bc(ee)).
(70)
0x
We consider the following update rule with respect to x and 0:
8
LT 1 ..de-1))
A x- A
"1 ax
(71)
0 ((To-1,,111
0, 0 " 00
(72)
where each (s, compponet update rule of 02 defined as follows,
(, a] ((t) f- 0(t-1) + 17 500,.
(73)
0((-1) 1 de-
(5)
A (8, (als) af (8,
(74)
where 00 02 [s, a].
To short the expression, we use the following notations:
{ (002)
exp
T = To. (als)
and म. ==
(75)
((()
Eaed exp 0,.
22

---

Under review as a conference paper at ICLR 2023
D PROOF OF THEOREM 2
In this section, we provide the necessary proof details of Theorem 2 is very technical to achieve the result of Theorem _ provide some basic lemmas in Section D.I, and the proof of Theorem is shown Section D.2
we outline some necessary intermediate results in Section D.I where
D.I AUXILIARY LEMMAS
Lemma 6. The sequence {)x, f1 generated by 72 7 and the softmax policy ni To, is defined as 75), then update rule with respect to equals 10
1 x1-1 (8) (4)))
7 deo
exp
Te (a(s)) (e-1(a(s)
(76)
Z(-1(s)
where A ((t-))(s,a) = 1 - (8, and
Z 71-(8)== Σ (al1 exp { 1 d (s)
" de
A A
- a (8. (s,
GEA
Proof. According to the update rules (74
calculate policy (als) 775 follows,
exp 000
<e(als) Te. (als)
ΣREA exp
0 s.a
exp (l(aa))
+ 1 1-
17
deo (a)s)) Ar, (0,
- -T (0,
74
xi
EBed exp exp
((--1) 1)
de (8) (s) A (s, (5) af-
1 1-7
exp
(0(t-1)) exp
deo
(a)s)
A (8,
(8,
EiEA
exp {
(0(l-11 exp
doo (s) (ā|s)
A A (), AT (s, a))
Exedess exp {
(0(t--))
exp
1] Ne_
des
(a)s:
Ax. (8, -A a _ (8, (s,a) )
=T[-1(a(s)
Eaes
exp
glt-1))
siu
exp
1-7
1]
den (5) A (s, AT af (s,
(77)
exp
11
d00 me_
( Ar. ( AT af (s,
(a|s)
( (t-1) exp
ΣieA
Eaed exp
s.a
(((--1)
exp
11-7
17
d (8) A (s, XI a (s,
9.
exp
71
doo
A [
(s,a)) (0,
1
(a(s)
EaeA
(āls) exp
n
doo
(s) (s)T(((ā(s)) Am. (s, \T as ne_ (s,
(78)
where Eq. (7 holds since we use the following definition
exp { (
T(-1sa Enes exp
{ (1(--1))
sā
23

---

Under review as a conference paper at ICLR 2023
To short the expression, introduce two notations:
{
Σ
(c]s)
1-7 dm (s)) (ā]s) (Ami (s, Xi (s, (s.
" dd
aeA
(79)
A 111-1) = ( - a (8,
(80)
we rewrite 78 as follows
7 d
(1)3)
exp
1 x
(a(as)) (a)s)
(81)
11-1(s)
This concludes the proof of Lemma
Before we further discussions, we need to define some a notations: (s) and a distance D[-I1]
between function p(-) and function g(-) over the action space A,
(ali(a)s) {a(s)))
(a+1(als)
Dip(-)ll(()]= Σ p(a) log p(a) (a
Hs(s)
log
q(a)
REA
acA
Note that if p(-). q()) divergence between the two distributions g()):
) is reduced to probability distributions, then D(-II-) reduced to Beilbackk-eibblee
DD Dip(-)lla() = B log p(x)
(
= -LLp()))a(())))
q(x)
Lemma 7. The sequence {)e, 0.112a is generated by 77 74 and the softmax policy no, defined as 75), the ie and x; satisfy the following equation
c(T) (Ci(T), C2( ... _m)(T)
( a) (A (s, a), (s, a). (s,a))
Furthermore, applying Lemma again, we rewrite 85 as follows
1 deo (8)
(a|s)
Te+a(a|s)
- J
log (als))
1
doa
(als)
.EAA
deo (s) (a|s)
log Ze(s) X (c(TT)) - c((t)))
(82)
(T))T((())) (a(s)
BES
aEA
where n. is the optimal policy of primal problem 4 i.e., arg max (TT).
Proof. According to Lemma follows,
we calculate the performance difference between J(T.) and J(T.) as
1
J(x.) ((TT)) 1-
E ExndR ().a). [An, (s,
d (s)ss (s, (s. a).
(83)
Recall (8) and (8.
81
write it follows,
log
TTt1 (a)
Zi(s))
" 1-7 d d (s)ae((ass) (A,,(s, X, ATa (s,
(a(ss
Then, rewrite the term A,, (s, as follows,
An, a)
1-
log (1l1 Tt(a|s)
Zi(8)) 2J a (s,
(84)
d (s) (als)
1
24

---

Under review as a conference paper at ICLR 2023
Taking the results
84
into
83
rewrite the performance difference between (T..) and (TTe) as
follows,
1
(s)
(a(s))
Tt-1(als) Tr (a|s)
(T.) - (mTe)
mq
log
Z((6)
7
doa
Te (a(s)
SES
Σ
(a) a (8,a)
#ES RESaEA
doo (s)
T. (als)
Trls(a
log
dou
Te (a)s)
TT((a|s)
d (5) (als)
+
log (s)s
ΣΣ BES
d ( (s, (85)
d (s)
1-7
SES REA
Recall the vectors c(T), a (s, a) defined in previous sections, where
c(π) = (T) ... (m() ( a) (s, (7 A (s, (s.a))
Furthermore, let us apply Lemma again, we obtain
c(π.) c(TT))
ΣΣ
d (s)a(( (s,
RERREA
which implics.
den (s)
(als)
log (als
J(T.) J(T.)
17
deu
(a(s)
Te. (a
dea (s)).
log (s() + (c(TT) c(TT)).
d (s)T{((())
sES aE.4
This concludes the proof of the result 822
Similarly, obtain the performance difference between ((T+11) and J(re).
Lemma 8. The performance difference belween (TT+1) and (TT) satisfies the following equation
[( - J( Xo (c((T+1)) c(TT))
(86)
d0u (8)
den (s) (3)Te+1(als)
(s(s) + ΣΣ
log (s)).
d (s)
de (s)T((((s)
SES
sES
Proof. According to Lemma as follows.
1 we calculate the performance difference between J( and J(x,)
J(T(1)) - -((e)
E, Eg-ido ()amm)e11111)) [A, (s,
(87)
-
dee (s)
(88)
wES DEA
Recall (8) and Eq. we have
A (s, a) 1-7 n
log (1l1) (((s) xJ a (s)
(89)
d (a)s)
Tt(a|s)
25

---

Under review as a conference paper at ICLR 2023
Taking
89
88
have
deo
(++1(als)
loog Te+i(als)
+ Te+1(als) <<(a(s)
(( - J(r,)
logg 2x(6))
7)
d
Te (T(aas)
{((ass)
d (s)T++((als)) A a (s,a)
? sES
do
d (als) d (a)s)
H4 (8) +
log (s) + X (c(Te+1)) - c(())).
SES
sES asA
This concludes the proof the result (86)
Lemma 9, The sequence {)e, Orti2a generated by 77 7 and the softmax policy क. is defined as (5). then the performance difference between J (Te+1) and ((T)) satisfies
74
ddo (s) (s)
((T+1) J (TT) X -c(Tet1)-
Fell
log Zi(s), (90)
d (()s)
sEA
and log (s) 2
Proof. Recall
(als)
log (als)
Hy(s) Σ
n, (a(s))
(((a(s)
aEA
since iy (a|s) < 1, then
(s) Σ Ta/s( (als) (e(a(s)
log
(a(ss)
aEA
(als) (als)
Te+1(a/s5 log
KL (1s) o.
(91)
aEAA
According to 86.86),
86 and due positivity of the terms (s) and de (8), we have
deg Kezz (5)m)+
((T(11) - J(m)) (c(TT(4)) - c(TT))
d (s) log (s).
r SES
Now, we need to show log Z.(s) O. In fact, the following holds
log (s) log
Σ
(ālss)
exp
d (s) (s, 2, aT (s.
REAA
(a(ss) log
exp
"
no (s) (s,
إo aL, a))
(92)
REAA
Te (2 (Ax, - aT
1
aEA
2 min (a({) aEA
Σ
d (s)Te (Am, (), Ao a (s, ā))
aEA
min (T<(a|s))
dd (s)
Σ
TT(@))s)Am (3, Σ
Te(T)s) a (5.
aed
1-
aed
aEA
(93)
26

---

Under review as a conference paper at ICLR 2023
where
92 92) holds due to the Jensen's 's inequality, and the last equation 93 holds since:
Σ Te(a =
REA
Σ acA
T ( A (5, = 0. i= 1,2,,. ,
m,
(94)
T
Σ aEA
( (s,
Σ ne (a] (s))), aEA
Σ T=(
Σ
Te(āls)AGT (5,
aEA
aEA
the notation O E IR mx1 denotes a vector with the elements are all zero.
Lemma 10. The term Eves log Zi(s) bounded as follows,
Σ #ES
log (x) S (1 - Prnin (J(Te+1)- J(me) X (c(m+41)) c(m.))
1)
Proof. Since dga (8) < 1, Te (a(ss) < always holds, recall 90. in Lemma 9
we achieve the
following inequality:
J(m++1) J(Te) X, (c(m)41) - c(Te)) 2
Rets (8) log Zz(s).
(95)
#ES aEA
According to Eq.
143 , we rewrite Eq. (95) as follows
J ( (TTe) - X (c(TT+1) - c(TT))
1
po(s) log (s)
(96)
1]
1 (o(s) log (s)
Σ
(als) 1-
Σ Po(s) log Zs(s)-
(97)
7
1
AEA
SES
Then, under Assumption
2 for each E Pmin S po(s). result (97
implies
17
(J(T(+1)- J(T() 27 (c(m(41) c(T.)) 2 Σ
log (s).
(98)
(1 - P)
SES
Lemma 11. Let To and no be softmax policy, then the following holds
(V (s)
0 0)
4
ViAi (8) Vna (s)
(1-
110 -
00
(1 7)3
Proof: See MMi et al. 2020
Lemma 7).
(V)
Let (1 31
and 0'
= + 3 80
then we obtain
1
av n (s)
Va (s) V*, (s)
(99)
23
00
Let of (8, a) E n is defined as follows,
(s, 12 (s, a). Q2 (), Q.m a)), vg(() (V (8, V V
V. (s))
27

---

Under review as a conference paper at ICLR 2023
Qxo (s. a. = (s) - x (s) (s, = Vxo(s) (s) - A -v (s).
Furthermore, we define
(1) = max (Qr(8, xelle
relle,ata [Qx(s,))}
max
(100)
= (5, a2 melle.az.
max (Qx(s, 0.
(101)
Similarly, we define
(+) min (Qt ()) a)}
min
(s,
(102)
rellc
Q2 (s, (s)) rEllc.oza.(5)
min
{Q (s. a)} O.
(103)
We define (s) as follows
A. = + (s) (42
(s)
(104)
Recall the notation 02aa = 0(s,, a). for all (s, E S A, and we define
0 0L A)
aL(TO. A)
(s)s)
Ya {
(105)
00 s (s))
00 00(s,0|
1
Quo
(s) - a. (s.
O2(s)
0
(106)
Q: a.)) 2 -
A i 1,2,
m
VaO, (s) 2 2xo, (s, a. (s))
03(s)
for > 0 is large enough
(107)
Va
(s) 2 Q ne
(s, (5,0 (s))
A
==1
no:
{ 0: (s(a(s))ss)
> d(s)
|
(c(s) =
c(s)+1 c(s) +1 =
(108)
(1 7),,))
Lemma 12. Let ()()) Oz(s), then
1 (+)(
Proof. 0,+1 E (2)ss) Since 0, Og(s), obtain the following equation
(s, A) 2 a,, A) 1 -,)) -
where is short for No, and (s, a, = maxzelle Q= Furthermore, we obtain
A) - Qn.
=7 Σ
P(s''ss.
(V (s' A) -Va A1)_
s'eS
(109)
According to Lemma
Eq. we know
Quai (8, (s), A) (s)(
(110)
which implies 0,11 O2(s).
Oct1 Os(s)
28

---

Under review as a conference paper at ICLR 2023
For any + (s), we know
On (,, A) (m,
(I11)
m (s, A) Q.(8,a A) + (s),, (s,0,,
(112)
2 (s)s) + (., A) - Q.. + (-. - (s,
(113)
2
2 (. Q. (8) A)
max aFa.(s)
Q- Q+( Qz.
(114)
100
102
101
A.(8) + (s) +y Σ
Ps (Vre4s (s', - (s)(
(115)
2
sES
1
2 (s).
(116)
Similarly, we obtain
1 A.)(s), (5, (s),) Queen (s,a,
(117)
which implies Oc+1 E Os(s))
Oct1 E (8)
According to Proposition
T
dC(TO. A)
1
d (n) (8, as, A),
00,
1 7
(T. Ac)
OC(TO, Xz)
if 0, E (s),
we obtain: for a +
00, (8, a. (s)
00,(s, a)
Te (s)
3) Are (s) A) (a)
(s, a, A),
where is short for me.
Case (i): (s)(()))s) 2 (als))
T. (s)(s)))) 2 Te (als), according to softmax parameterization we obtain
i as)) 2: [s
(118)
Recall the update rule of Algorithm D we know
aC(mo. X,)
105
188
aC(To, X,)
0441s [s, a. (s)) a, +
0.[s, al
0c+1(s,a),
a..
00 [s,a]
which implies
(xp(
exp(fi[s,a]}
(a.1 EeEA exp(Or|s,c))
EnEs exp(Or[s.a]) (ati()
(119)
Recall
we obtain
(s, 2 Ar, (8,
(120)
Eq. 11.1199F44 Fq 120
implies
aC(Te..:> 2 00 00,+1|,,a.33)
aL(Te..::
a
which implies o+11 (s)..
Case (ii): (r)((s)))s) < (als).
According to
(s)as)))ss) An, (.),))))))) (alas) (s,
29

---

Under review as a conference paper at ICLR 2023
obtain
(=(((())ss) (s,, (s), - V8, X)) 2 (alss) (Q=, (s, (8, (8,
(121)
= = (Q (8, (8) 2) - (8, + (8, A) - (s) 2)),
(122)
i.c.
1 (=(a()))ls) (Q (s, Vv A))
(123)
ne(a|s)
= (1 - exp [0. ax (s)] - 02(2, (Q, (s) A) (8,
(124)
<Qm (8, ax) (s), 2) - Qm (8, a, 2).
(125)
Recall the update rule of Algorithm 1 we know
aL( Ae) 20,0[s, a. (s)]
0441 a] = 0,(s, a| aC( d1)
0c+1ls, as)) 0r a. (9)]
(126)
00,[5,a]
aL(TO. At)
aC( A1)
Since 0, E i.,, 00, a. (s)]
2 00,[8,a] al
Eq.. 126 implies
0441l8, Oc+1 [8, a] 2 0, (s)] (s a].
(127)
Since we consider Ti (a)(()))))) < (alss) then
(<)((()))s)
1 cxc - 0. a]]=- 11
{c(s)) > 0,
which implies
(1-csp(0-1ls..a a. 0et1ls, (S). (s, (s) A) Q (s,
Rearranging it, obtain
T (a.)))))) (8, (..a,(s)))) 2 Te+ ( ( (8, X),
which is
0C A
aL(TO, 111 Aet1)
80 a.))))())) [s]]
00 [s,a]
which implies 0.+1 (s))
Lemma 13. Let 0,
Og(s), then (a))(s))))s) ()))
Proof. Recall aL(TO, Ae)
aL(To, >
we obtain
00,(s,a, (s) 00, [s.0] a]
exp Ozls, as()) + aC(TO. Ae)
exp 18,
30, (8, 0, (x)
(a,(a,)))ss)
(128)
EaEA exp (0,11s
0L no, At)
EaEd exp
(((s,a)
00 [s.a] a)
aL(TA, Ax)
exp 0.(8)0((8)
00, (s a, (8)
(129)
0L (T.,, As) 00, [s, a. (s)]
EaEA exp (1(s,a) +
exp(Or(s a, (s)))
(a(a
(130)
Eaes exp exp
(8,aa))
Lemma 14.
n (s(ss)
30

---

Under review as a conference paper at ICLR 2023
Proof. Let E Oc(s) n (2()) n (s)),, consider the two following cases:
Case (s))ss 2 maxaza. (s) ne (c)s).
AL(TO. At)
d (s To (s) (s,
(131)
00,(5. [s, a. [s)]
106 107
aL(To. A1)
dog (T) ( A (s, A)
(132)
30 18, a)
where the last equation holds since the same analysis from
we have
Qn, as)) X) Qz, (s,
2 A.).
Case (ii): (s)()) 2 cax (a)ss) which is impossible, since if this case hold, obtain
2c(s) 1.
(e(a)())|s) - (a(a)))
c(s) +1
Lemma 15. Under Assumption updating according to Algorithm we obtain
C. inf {T)(O(())ss) 0.
Proof. According to (Agarwal et al. 2021 Lemma E.2-Lemmal2), we know (s(a(s)))s) + 1,
which implies there exists T1()) 2 I, such that
c(s)
To (n (ax())))) c(s) +
Furthermore, since Quo (s, a. (s)) Q. (s)). oc. then there exists T2(s) 1, s.t
1 -
Quegen (s, (s)) 2 (s.
A.)).
Finally, since QTo, (s) V=(s), and V=o, (8) Vs(.). as t - co, then there exists Ts(8) 2 1, such that Vt 2 Ts(s),
250, (s)) Vio,, (s) (s).
Define To(s) = max (s), (2), Ta T3 then we obtain
CTo(K) E o (e) Oro(s) E (s 0z)
According Lemma 12 14 i.e., i (s)))
then 0-1 E ((()))))(())))(()))
and the policy ne, (a
is increasing in the space 9 (s) n (2g)s) we have
inf no. (s)ls) = min 1g/STo(>>
no. (s)
200
To(s) only depends on initialization and c(s), which only depends on the CMDP and state Finally, we have
inf e58,121
(T)(s( min min no. (a)(s) > SE IstSTo(e)
Lemma 16.
For any fixed T > 0, let O, 0, As 0. The sequence (Ar, O2 Froo is generated by
dnd po
71 72
/
74). and the softmax policy गe = ne, is defined as 75) Let (1-7)e-
C1
Then
(1->)²
((x.)
T-1
Σ ((Te) - T
Σ
T-1 c((T,) S
x log IA
2x
+ +m2x
T
Puin (1 7
1=0
(133)
31

---

Under review as a conference paper at ICLR 2023
Proof. According to Lemma 7
we obtain
d (s)
(als) (e(a
log TL-1(a|5)
J(H,)- (TTe)
17 #ES
dea (s)
AeEA
xr(a|s)
deg (als) log Zi(s) + 2, (c(x=)) -((r)),
(134)
d ({)s)
SES aEA
and summing 134 as ranges from 0 to T 1, we have
1 T-1
don (s) d (s)
n. (als)
(ali
J(TT)
Σ
((T))
Σ
log
T
1/T
Tr (a|s)
Te (a|s)
1=0 SES
aaEA
T
d (s) IT (a|s)
log (s(s)
+
Σ t=0
No (c(πT. - c((T))
1 (T) (a
1= 8ES AEA
d (s)
T. (als)
log 1a|s) (T(aas))
771 7T
Po(s)
(a dao (S) (u(s)
t=
DEAA
T-1
+ 111 T)
1
log (s) T
Σ
x7 -c(x.))c((T)
- c(TT))
(135)
t=
sES DEA
t=
doa
T-
T. (a|s)
log (als(als)
(136)
1111 7)T
Po
(a)s)
(a|s))
t=0 8ES aEA
+ 11(1 -)T
1
ΣΣΣ
(als) (a(ss)
log (1()) + T Σ
(c(TT)) -((=))
(137)
PO
I=0 8E8 SEA
1=0
1
dec
T-1
(als)) log (a(s)
(138)
1/11 - T)+T
Po
(<(ass))
(=0 sES A
T-1
+ 111
ITc
log (8) + T
Σ 1=
xJ (c(xx)) c((T))
(139)
T
PO
(=0 SE
1
deo
T-1
- KIL [T.. (18))][=++
(140)
1/11 - TT
Po
(=0 SES
+ 11 - 7)cTT
1
log Zx(s) + -
Σ (c(x)))) c(T.))
Po
t=0 SES
0=
1
deo
Σ KL |.. (11s)] - KL [T. (-15)]l
(T.
7/11 7),,T
Po
00
SES
de0 IT.
T-1
+ 17(1 -c,
log (s) +
Σ
xT (c(TT)) c((Te))
Po
T
t=0 SES
1=0
1 deo
1 T-1
KL [TT (1s)
Σ
x (c(xx.) - c((T))
(141)
7711 - 7),.T
Pu
T
00 -ES
1=
ddPu
T-1
+
ΣΣ
log (s),
(142)
- 7)
Pu
t= SES
32

---

Under review as a conference paper at ICLR 2023
where Eq (35) holds since: for any Markov stationary policy n,,
don (s) E Beo-
E (p
(1-7) Σ Pr s/50)
2 (o [[1 (11-))Paa (s s|su]]
p)poss);
(143)
dee
Eq.1137 holds since we use
to denote the distribution mismatch coefficient, i.c.,
Po
d
de (s)
max #ES
Pu
Po(ss
den (s)
Due to the Assumption 2 the term
is well-defined;
po(s)
Eq. 138) holds since is deterministic optimal policy, and we denote it as (+(a(())(s) otherwise, i.e.,if a # a,(s), (als)) inf infees.e21 (s))ss) >
Recall Proposition we know c,
(als) AEA [a(a
Te+ 1 log
(s)(s) (s){ss){s)
Te+ (a, (s){s)
log my. (ax((s)))s)
(144)
nt (als)
n. (8)())
log Te+ (a, (8)(8)
(145)
Cx
(a. (s)(s)
1
Σ
n (a|s) log
(146)
Cx aEA
(e(a)))
Similarly, 139
139
hold since
T. (als)
T. (a.(sssss)
aEA (a(s))
())
Eq 139
holds since:
Σ n. (als) log (als) (e(a))
IKL [T, (. (-1s)] KL [ (-1x)]] mT (-16)];
aEA
Eq. 141
holds since omit the term KLL [T. (-1s) (-1s)]-
Taking Eq.
98 into Eq. 142), we achieve
1 T-1
deo
((T.) T
((Te) <
KL [T. (115)) + +
Σ
-
11(1 c).
Po
1=0
SES
1=0
deg
T
(J(T(+1) ((Te) x7
Pmin (1 - c)c,77 27
Po
1
dPo T
KL JTa (-|s) To (-1s)] + T
T-1
Σ
(c(TT.) - -c(Te)
(111 7).TT
Po
seS
1=0
dod
T-1
J(TT) J Σ (c(m)) c(Te-1)))
Pmnin
- c),,
Po
(147)
33

---

Under review as a conference paper at ICLR 2023
Now, we need to bound the term 1 to (Ding et al. 2020
T - X (c(TT) c(Te+1)) in Eq. 147) our proof is adaptive
T
Ao (c(TTe - c((s+11)))
x -c(To)
T
T-1
Σ
c(Te)()))1)) - N c((e))
Σ (i - A1t1 c(me+1))
+
T
T 1=0
T-1
1
(M))(F)
Xo ofau))) + T
Σ
(441 c(Te+1))
(148)
T
1
1 T-1
T | |
T
Σ
A
||((T++)]]2.
(149)
t=
where Eq. 148
holds since the initial value Xo 0, and Eq 149 due to inequaliit..
Recall update rule
71
with respect to A:
A L An) =(>- ny c(T+)))+
A++1
vax
which implies
|A41 dell2 S ///lb c(2 S 17 (11bl22 ||((+))l2))
(150)
Now, we need to bound
[c((T;)l22
Σ (((T))
Eso [V (so))
E so So>po(()) (l
Σ
* Acs(s, az)
(151)
where last equation holds since the cost function c:()) is bounded by Recall = (b1, be. bm)) let
bmax max/bi, b2. .bm.: }.
then, according to 150,, we achieve
1
A dell2 I m/ c(TTe)l2 mmm Umax +
I-7)
(152)
Furthermore,
|
12
Σ - Ao
S <nym
|maxx
+
T.
(153)
1 1-
Taking Eq. 151 Eq. 152
and Eq. 153 to Eq. 149
we have
1
1 &
Σ
x7 (c(m) - c(T++1)) < 2mm
(Dmax
1 1-7)
(154)
T
1=0
34

---

Under review as a conference paper at ICLR 2023
Finally, recall the result (147)
and taking [144
it, we obtain the following equation,
1 T-1 ((x,) T
d
( S
KL [-)+))]0]
+
T (c(T))) - c(T,))
17(1
7),,T
Pa
1=0
SES
dea
T (J(TT) J(
Σ
M (c(7++1) c(T+))
Pmin (1
r)c+²
Po
T
d
KIL (-15)][== +
1
Σ
T-1
2, (c(xx)) - c(TI))
17(1 7)c,T
Pu
T
#ES
1=
+
d
(J(m)) - J(To))
1
1
Σ
x (c( e(meta))
Pmin (1
y)c,2
Pu
T
T
t=
1
dgo
|S] log |A|
+
T-1
Σ
(c(TT) c(T+))
(155)
17(1
c),TT
Pu
T
+
dl
2
2mm
1 1- |imax +
1
(156)
Pmin
c).
Pu
T 1 1
where Eq. 155 holds since: according to the initial value Ao 0, then the initial policy xo is reduced uniform distribution, and the probability of each action a is no(als) A
(a|s)
KIL (1)(()))000)())]
Σ aEA
n. (+18) log
Σ Th (-18) log (I.A I (als)) S log AA)
To (a
which implies
Σ
KLL (-s)) s log [A]:
Eq. (56) holds since: for any policy m, the objective ((z satisfies
J(x) 5(t) 1-7*
I-
and the result (144]
shows the boundedness of
T
x (c(m))) - c(TT+1)) < 21mm
(Imax +
T 2=0
T-
Finally, let
doc
C
m
bmax +
(157)
Po
(1 7)2
1 1-7)
then we rewrite Eq.(156 as follows
( 1 Σ ((T))
Σ
-
<
I| |A|
2x
1
2
T
1
Pmin (1 - 7)
T
(158)
This concludes the proof
133
D.2 DETAILS FOR PROOF OF THEOREM 2
Theorem 2
Under Assumption i
ne the sofimax policy defined in P.. The time-step T satisfies
F
F.
T > max
(1-7)2'
((1 7 + 2m 122
35

---

Under review as a conference paper at ICLR 2023
where F = [8] log Pi, Di
D1 and D2 are positive scalars will special later. The initial X =
tg- = 0, the parameter sequence (A,,0t)=s 1 is generated according to Algorithm
Let v), B satisfy
dou
S log IAI C(1 -)7
de
4 log [A (1 3
3
Po
Po
where C' is a positive scalar will be special later. Then for all i E [1, .m.. me no, satisfies
d
18 log |A| c.(1 - 7)"
min -J()))
S4
(159)
KT
Po
4g
|S log |A|
min (C.(T.) - bi - KT
Pa
(160)
8
|
c. - (c(1-))+
In this section, show the details for the proof of Theorem The proof contains two key steps: bounding the optimality gap and bounding the constraint violation. Finally, we summary the hyper- parameter setting for to obtain the results presented in Theorem
Bounding the Optimality Gap.
Recall the dual update 7T
we have
AA 1
A| 12
2
{ { -1 2
L(TT, Ac)
5-
11
ax
-
(II(A, 77 (b -c(m))) -11
(IA, (A:-n(1) (b c(T))))l -
172 lb - c(TT))l( + 2n727 (c((T)) - -b))
n'm (Bunax +
_1
+ +n (c(mT) - -c(Ta))
(161)
1 1-
T-1
=nim m Umax +
1
T 2m
Σ 1=U
(>7 (c(m)) c(T))))
(162)
1
where Eq. 161
holds since: c(T++) 1 b, then A[((TT))) b) 0, and
X (c(m.) - b) X, (c(m) c(T.) + c(T,)) b) < X (c(mT) c(π.));
(163)
Eq. 152
implies
b -0T, S vm (mmxx + 1 )
(164)
Combining the results (63) and 164p. we obtain Eq. 161
Since |
||
0, Eq. 162 implies the following boundedness w.r.t. X, (c(m.)) c(m.):
1
m
|max 1 1-7)
2
Σ (AT
(c(m.))-
(165)
T=
36

---

Under review as a conference paper at ICLR 2023
Recall Lemma 16
we have
J(T+))
1
T-1
Σ
J(m+)
T
1
X|S|
[A]
+
2x
+ 2xnCC +
1 Σ
(c(T+) c(TT))
T
7
Pmin (1 1 7)2
T 1
1=0
165
1
[X|S| |A|
2x
+
+ +x + 2 mm
|nnux
T
Pmin (1 -))
1-7)
1
(x(S) |Al
2x
2
T
+
Pmin (1 y)2
+n 2xC2
2 m
|bmax +
1 - (166)
which implies
1 min (J(=)) [(m)) s T teT
x log |A|
2x
+1 )
2
2xC1 2
|Dmux 1-71
Pmin (1 - 7)2
(167)
Furthermore, let
x log [A|
dog
S log [A]
= T 2xC1 + m (Imax +
(168)
(1 7)C T
Po
where the positive scalar C' is defined as follows,
1 )
1
C = C+ 2xC1 + 2m Utmax +
< +00.
(169)
Then we achieve the optimal gap as follows
x|S| log IA|
1 12xC + 100 2 Umax +
1->) }
2)
2x
min reT
(J(TT)) - (TT)] S
T
Pmin (1 - 2T
(170)
S|S| A
2x
(Mi + 1)2x01 + Pmin (1 2T
(171)
T
where the constant M, is special as follows: 2xC,
2 m (bmmx + T-1) i.e.
dog
bmax + I-n
Mi (1 y)c
Po
1
Recall and C defined in Eq. 157).
d
7)c.
Po
C1
(1 - 7)
6max
1 1-7)
taking them into Eq. 171
we rewrite 171 as follows
min (J(m.) (mm)) < KT
1
deo
S log |A|
(M, + 1)2m
(bmax
(1
7
Po
T
(c.)²
1 1-7
00
+ 2
1
ite
C. Punin
(1 - 3)
Po
1
dPo
S log D
D2
dPo
(172)
(1
7
P0
T
Puiu (1 - 3T
Pa
37

---

Under review as a conference paper at ICLR 2023
where D1 and D2 two positive constants defined as follows
D1 = (M1 + 1)2m
bmax + T-m) < to0, D2 = < t00.
(173)
(c+)²
Finally, let
D2
2
(174)
(1 - 7) log AAl Alppinn D1
which implies
2
do n
S log (
min (J(TT) - [ 5
(175)
K<T
(1
- 7)2
Po
T
Bounding the Constraint Violation.
We consider the parameter | 2a j0, 3), where the positive scalar 3 will be special later. According to the update rule 71 w.r.t. parameter X, we obtain the following the equation,
{}: 7(b c(T+)))++ x
d 1//b c(m)) - 5 |
A X (m x) (b- c(TT)) +1² |lb c(Te))l2
T)T(b
A 2 2m(x. T)_ (b- c(x:)) + +m2m (bmax +
1-
which is equal to
A4+1 Ā A/
2 < -2m(4 - (b-bbcc(T) + +m²m bmax +
(176)
1
Summing Eq. 1766 from to T
1, we achieve the following equation
5 x 2
< 2 x1(²
T-1
1 2
5 A-
2n
a 2) (b - c(Te)) TT?
|bmax +
1 1-7)
which implies
() c(T))) S
Ao
x|2
+
17 m
bmax +
(177)
T 1=0
2n/T"
2
1
Due to c(T.) 3 b, and A 2 0, then the following equation holds,
T-1
T T-1
T-1
(c(T.) -((,) - - (c(T)) - b b c(T.)) 2
Σ
x (b c(m)).
1=0
(178)
Recall Lemma 16
J(m,) 1
-
Σ J(T.)
T-1
T
T-1
Σ
XJ (c(TT.) c(T,)) S
x log IA
Pmin (1 - 7)
2x
+ 2nn
1=0
t
whhere obtain the term T
174 by solving the inequality:
doo
S log D
D2
dPa
2
Po
T
Pain
(1
2T
Po
38

---

Under review as a conference paper at ICLR 2023
and taking 178) into above equation, achieve
T-1
T-1 Σ
(x|S [A|
Pmin (1 - 7)2 )
2x
J(T,) T 1=0
Σ
((m)
7T (b c(TTT) S
+
+ 21x
T
77
1=0
(179)
We rewrite Eq. 179
follows,
1
J(H.) T 1=0
J(m))
Σ
x, 2T (b
c(Ti))
T t=0
1 T-1
T-1
1 T-1
=J(m+) T
Σ
J(mt)
T Σ
(A:
- ()
T Σ X (b-c(m))
1
x|5| log |A|
2x
ST T
+ 21
(180)
Pinin (1 - 7)3
Let A = (21,,2,.... .., 5m) T. taking the result 177 into Eq. 180), we have
T-1
T-1
T-1
[(T.)= T 0=
Σ
((TT) -
Σ Σ
(b. - c(TT)) c((()( = ((T.)
-
Σ 1=
(TTE) +
Σ
(c(TT) - b)
r=
(181)
=J( T
Σ
J(Te) +
Σ X
(C((Te) -bi)
(182)
T
1=0
1=0
( 105 A
2x
1
+
21
+
|1:0 - A11 + m |mmxx +
17
Puin (1 - 7)
2n/T
1- 7
(183)
For any policy n, the objective function J(T) is linear function in an occupancy measure induced by such policy и. Since the set of occupancy measures is convex and compact, the average of occupancy measures another occupancy measure that yields policy, which implies there exists a policy Te such that
Σ t=0
J(me) = (
(.((T.) - -b)) C.(Fe) bi.
(184)
Furthermore, let
B Sx [A]
if ( (C,(m.) - (.) 2 0,
(1 7]-
(185)
0.
if (C,()) - -b) < <0
39

---

Under review as a conference paper at ICLR 2023
1
x|S| log [A]
recall 7/ defined in 168), i.e., 11
then rewrite Eq. (82) as
T
2.
1 2xC1 1m (Dmax + 1-7/
follows.
1 (T.) T
Σ
(TT)
Σ A
Σ
(Ci(T)) - -bi)
T
1=
1=1
184
[F+)) - J(tt)) +
X (C+(#+) - b.))
m
185
J(x.) ((tt)) +
(Ct(ft) b,b+
(186)
= (T.)) ) - ( + 31 m (c(tt) - b}+
the vector version of Eq.
186
83
x|8| log A
2x
1
x|(² + "
1
2
+ 21 +
Ao
Imaxx +
"
Pinn (1 - 7)2
2n/T
1 1-7
(187)
T
x|S| log
A
Punin (1 7)2
2x
+ 21
+
m 2n/T
12
+
2
m
bmax +
1
1
(188)
X|S| log |A|
1 2m (brmax 2xC1 +
2) ?/ )
2x
+
g²
(189)
T
Pmin (1
-
2n/T
2m
x|5| X|S|log log |Al
2x01 + 1mm 5mmm (bmnxx 1-7)
)
2)
2x
1
(1 72222
Pmin (1
2)
(190)
170 122
1 + (1 - 2/
2m
d
log A
D2
doc
{1-
Po
T
Pmin (1 - --) 3T
Pa 1000
(191)
where Eq. 188) holds since: by the definition of X in Eq. 185 and initial do 0. we have
|
S ms²2
Eq. 190) holds since we replace the term
32 as follows: recall B v S|S|log AA| 2n
m
2
(1
7)
defined in (85 we have
2xC1 + 1m Umax + T-m
82
32
2xyT
Tx|S| log LAl
2m
S log LA| T
2
2xC1 + -m
(Imax +
(1 22
1- 1
Finally, let
1 + (1 42
2m
d
S log A
D2
deo
8: (1 21-
Po
T
Puin (1 3T
Po
then the results (99) can be represented simply as follows.
J(T.) J 31 (c(#t) b)+ S 8;
(192)
40

---

Under review as a conference paper at ICLR 2023
recall
Lemma
that reveals the boundedness of X., the definition of 3
vx log A
7) implies | oo: then applying Lemma we have
[c( - b)+ < B |
(193)
Since (c b}+ Ex= (At - bib+ and each (Tx( b.l 2 0, then we have
{c((t) - -b}+ 1 3- 12 1m.
(194)
Eq. 194 implies for each i E (1,2, , m.) (C,(#t) - -bil+ 5
i.e.
B 8-11A.1 ||,
184
1 T-1
(C,(TT) [(C(())))) -bi b)) }
8
( - +,,+
[
[T2)
5 B |
(195)
t=
which implies the Best-Case Constraint Violation as follows: for each i E {1,2, ..). we have
min (T+(TT) - -b,b RTT
(196)
1
+ 2m
S log IA|D;
D2
d IT
10
(1-
(1-
Poo
T
Punin (1 37
Po
Furthermore, let
D ((1 7)2 2m/ 2 2 Pini D 1 log |A]
T
(197)
then we obtain
2
(1 1+ (1 7)2
2m
d
|S| log DA
min (Ci(Te) - bb s KT
=3 || 1000
(1 T
Pu
2m
1 + (1 - 7/)
deg
Sl LAIDi
(198)
| Dc
Po
7)
Summarizing the Conclusion under Special Hyper-Parametes Setting.
Finally, recall the condition for the term T in 174 197). we conclude if the time-step satisfies
1 (1 ?)- ((1 - 7)2 + 2m/
D
max
| log A min D1
the step-size 7) defined in (168) satisfies
deo
[S] log [A] (1 - CC T
Pu
and the constant term 3 satisfies
185
2
S log A
(199)
(1 7)
1
des
2 (1 (1-7)u
|S] log |A|
(200)
(1 cc.
Po
dPo
D|S log |
(201)
Po
(1 33,22
where we obtain the term T
197 by solving the inequality:
2m
d
S log (|
D2
ded
(1 (1= +
T
Panna (1 33
Pu
41

---

Under review as a conference paper at ICLR 2023
where we define the constant D follows
D1
Then, according to (755) and (98).. the following holds
ddd
S log A
min (J(T+) - [m]) < 2
KT
Po
7)
2m
d me
[S] log L
min (T((TT) - b,t 5 KTT
+ (1 7)
3 | |m
7)-7
Po
where each E (1,2, ,m). m This concludes the proof of Theorem 2
d
Remark 3. Recall 14.3143) : d (s) 2 (1 - (s)) which implies
2 (1 -17. Thus,
1 10g AA|
2
2 (1 - 7)
B 2 V c
>
(1 11-71 7)6
Lemma shows that
2
|7e S
(1 (1-7)²²
Thus B > |AA loc.
42

---

Under review as a conference paper at ICLR 2023
E PROOF OF THEOREM 3
E.1 GEOMETRIC DISTRIBUTION
Before we show the details of the proof, we introduce some basic notations about geometric distri- bution Geo(7), which is defined the following discrete probability distributions: the probability distribution of the number of failures before the first success, supported on the set {0, 1, h.
i.e.,
P(T =) (1 7)7 7E (0, t 0, 0,,,,,,3,...
(202)
To understand G7 202 clearly, we list the distribution column the distribution Geo(y) in the following Table 2
Table 2: Distribution column of the distribution Geo(?).
7
7)7
(1-7))
7 ?
7)
E.2 ROLLOUT WITH FINITE HORIZONS
Algorithm 4 Est 9, a): Estimate Q Value Function
Input: Policy æ.; Reward function Cost function 9(:-); State-action pair (s, a);
2: Initialization: ((s, a) = (so. ao) = (s, a);
3: Draw an integer from a geometric distribution with parameter (1 7): P(r = t) -1-7)1
4: for = 1, ................................
1 do
5: Collect reward (or cost) g ax) and add to estimate: @(s, a) + @(s, a) + g at);
6: Simulate the next state and action follows: Sc4-1 P(: St. artl al ((110+1);;
7: end for
8: Collect last reward (or cost) g(s,, a.), add to estimate: Q(s,, a) - ((, + g(s.
9: Output: (s..a).
Algorithm EstV(m, g, 8): Estimate V Value Function
1: Input: Policy и to be evaluated; Reward function or Cost function g(,, ); State 8;
2: Initialization: (()s 0, so s, dg x--[50);
3: Draw an integer from a geometric distribution with parameter (1 7): P(F = =1] = (1-7)77
4: for = 0, 1, F 1 do
5: Collect reward (or cost) g a.) and add estimate: ((s) (s) g at):
6: Simulate the next state and next action as follows: 88+-1 P(: at); a++1 ~ T (1118141);
7: end for
8: Collect last reward (or cost) (33,, a4), add to estimate: ((s) + V(s) + az)+
9: Output: (s)).
E.3 PROOF OF PROPOSITION
We need the following Lemma to show Proposition B
Lemma (Dominated Convergence Theorem). Let {Xn, Jo20 be a random variable sequence, and Furthermore, if [x,] I Y for all and E|Y] I co, then
X, X almost surely,
E[X.] + [[ as n + oc.
Proof. See Durrrt 2019 Theorem 1.6.7).
43

---

Under review as a conference paper at ICLR 2023
Proposition 3 The output Algorithm (also Algorithm 4 is unbiased estimator Qn a) or (s, 0), Le., let
- Est @ (s. a) 2,
(203)
then the following holds
= (IQ%(s, (s.
(204)
Proof. This proof is adaptive to Paternain (2018) : Zhang et al. (2020). Without losing generality, we
only need to show the case of ((: = r(s ) i.e., E (s, a) = Q= a).
According to the iteration from Algorithm
obtain the estimator of (8, a) as follows,
(=, = Σ ((00000)) (00 - (s,a), T ~~ Geo(1 - 7).
(205)
We consider the expectation of (205
((Q+(s, E
(st -
= 5,000
(206)
1 (1t 7(0 5,00
(207)
=
(208)
t=
where 20. holds since: we have substituted oo for the via the indicator function I(-) such that the summand for > is vanished;
Eq. (Q8) holds since we use the dominated convergence theorem (see Lemma let
X, = Σ ((
1=
then we obtain
|,| = Σ
[itsT)r(ssa))
< Σ utt = Yn.
(209)
1=0
t=
and recall Geo(1 7), then we obtain
P( Σ - (1-
(210)
n
E V
[1
P(1 ST)
210
(211)
1=0
according to the results 2099 and 211b. and applying Lemma
we obtain
IE
Σ
1 az) n, 8, s0 s, 0g
Σ e
(
ie., we have checked exchange condition for the sum and the expectation in the previous expression from Eq.207 to Eq. (20))
44

---

Under review as a conference paper at ICLR 2023
Furthermore, we consider the result (208 follows,
[[)+(s, =
Σ
= = B 7 1-))
t=
1tt Itt TT r) as)
T, 80 = =, 40
(212)
00
B 1-
[[t r (8 a0
TT, =
(213)
t=
7 (
T, 0,
(214)
0
= as,
(215)
where 212 holds due to the double expectation formula: E[X] Ey Ex [X]],, which implies that we find the expected value of X by conditioning it on another random variable Y;
Eq. 213
holds since: the horizon
drawn independently of the MDP sequence {st, ar r(s,, at)::
Eq 214
holds since:r ~ Geo(1 - 7), then we obtain
(r-~Go(11-)) [(( 5 (P(
(1 =
T=1
This concludes the result (s, = (s,
If we replace all the term r(*,, 0x) to (st,,, a.) from Eq. 200 1..5--B..00 (15). (s,
we obtain E[Q (s, a)]
E.4 PROOF OF THEOREM
Since return objective J (me) and cost function (T())) share similar structure, all the Eq. 24 can be extended (TT) if we use c to replace respectively. this section, we only show the case of the reward function J(TT) in Theorem Before we show the details, we present some insights of those unbiased esitimators.
Rollout Algorithm
We rollout policy evaluation with respect mo according Algorithm
To (s, a) = EstQQ(Te s, a),
(216)
we use r ~ Geo(1 - to denote the terminal time of the horizon of the rollout (216).
Furthermore, let G.g (s, a) be an estimator defined as follows,
2no (s,, a,) θ log To (a (s7)
G (s,
(217)
00
where we obtain Qng (8r, ar) according to Algorithm 4
(s7 a,) = EsttQ(Tg)) r, a,).
(218)
Let r' Geo(1 >) be the terminal time of the horizon of the rollout (118) and we denote the rollout trajectory follows,
D' (s)), j=0"
where initial state-action pair (s a6) = (Sr, ar).
Then, rewrite the value Q.o (Sr, (+)
218 follows.
@Ta a7) = Σ r(3 2g); (so. = (s,,a7); 7' ~ -GeoO1 -7).
(219)
5=0
45

---

Under review as a conference paper at ICLR 2023
Algorithm 6 EEttPG(T, a): Estimate Policy Gradient
Input:
policy To with given parameter 0, (8, a) E A:
2: Policy Evaluation Rollout for (s, a--Pair: Q (s, a) = ( r, a). and r ~ Geo(1 -7)
denotes the terminal time of the horizon of such a policy evaluation rollout;
3: Policy Evaluation Rollout for (8+, a-) J-P-- QTo (8,:07) 07) EstQ((TT:)) 8,, ar), and
Geo(1 7) denotes the terminal time of the horizon of such policy evaluation rollout;
4: Collect the trajectory D'
(s)) aj ((1), "=o=" where initial state-action pair (so, ao) =
(St; ar);
5: Output: (s, a) defined as follows,
(3, = 1- 2no (NT, a+) θ log To (1
0
r (1) 00,,a
log no (87))))))
00.a
1=0
(221)
Taking 219) 217
we obtain the expression of Gr (s, a) (217) as follows,
Gro (s)
r(3) a
log (a (s.), where (so. (sr, r'~ Geo(1 - -7).
a0..a
1=0
(220)
Remark 4. Since Algorithm plays two rollouts that cause randomness of the estimator Gro (s, a)
220 with respect to T and T, which implies Gao (s, a) 220) is random variable with respect to and T.
Unbiased Analysis
We consider the expectation of GN (s, a) (17) as follows, for any given 6,
r a 2 log To (e (s7)
Gro -,,r'
(222)
00,.a
220
Ey
(())
2 log To ca(a)(87) 00
(0) = (St, a+)
1
(223)
where E,, is short for the expectation the randomness from the variables Geo(1 7),T' ~ Geo(1 - 7), similarly, [.[-] denotes the expectation over the randomness from the trajectory 7 Geo(1 7).
As similar analysis from 207 to 215
we consider the term E, (223) as follows,
Σ r(ss (a)
Olog ma(a))s>)
($0: (6) (St, ar)
E
223
Goo((10))))
00.aa
1li < }r( (r(s))))))))))
(60. (or,
a Olog (a(
00,a
Olog TO (or 187)
= Qno ar)
(224)
00 s.a
46

---

Under review as a conference paper at ICLR 2023
According to Eq. 223) and Eq. 224 obtain
2 log To (8+)
G (8)
? E
TTo (8);
(225)
00..a
00
a log TO vo(arlsi)
Ry
Σ
T(== T]Q (8r, ax)
(226)
00,..
1=0
where s H is short for the expectation over the randomness from the variables Geo(1 - 7), Sy ~ P(. (-1s0), and a, ~ (-1st)
Recall the result (7). we obtain
To(als) - (TT(aas))
st = and 0 = a
Omo (re(())):))
-Te(ool))To((ss)
if St and #
(227)
00,
if st + s or at #
(a(al)))) (TT((a)s:)))
if 8t and at
if 8 = and at +
(228)
if st F at a,
which implies
1 - (e(((s))s))
if st and 0
i log ao (sc)
-aa(ass)
if st = s and *
(229)
00,n. 2,0
if st or a # a.
According to the result (229). it is similar to 209 condition of dominated convergence theorem (see Lemma 17), thus we rewrite Eq. 226 as follows,
21 it easy to check that Eq. (26) satisfies the
Blgg To (cclsa)
(8,
Br
1lt = =] (st, at)
(230)
30,,a
1
log (a(()))))
Byn yy) [T(I= = [ Beco, O (8t, az)
(231)
7
20
km0
(8e, at) log To(a)))))
7
ME
(232)
00..
Σ (o'aalss) 1T a') Glog To(a'ls)
Σ
Pro (st = s
00,
1=
N'ES
a' 2'EAA
(233)
P (st (oo (s') (m (s',a') Glog vola'ss))
33
(234)
00..a
JeSa'EA 1=
where 233 holds since
E (I [I{{ -}] = Pt 7)
where Eq. 234) holds since we use the dominated convergence theorem (see Lemma 17
We should notice that the last Eq. 234 share the same expression in the previous in 65) and
following the same analysis from Eq. 156-566 68
obtain the unbiasedness of G (8,a).
47

---

Under review as a conference paper at ICLR 2023
Boundedness Analysis
Recall the expectation of Gzo (s, a) (277) as follows, for any given 0,
d Ooo no (ar157))
E ( (s,o)))
=B p,0"
(s ag)
(235)
00, 00,00
==0
(1 71- 7)2 Ey'
Σ r(s),
(236)
(+) 2
E Gee(
<
(237)
(1 7)2
7)3
i log To (gelse)
where Eq. (266) holds since: (2.9 implics the boundedness of
$ 2;
00.aa
Eq. 237 237
holds since: recall 7' Geo 7) can be expressed as follows,
Table 3: Distribution column of the distribution Geo - 7)
0
2 72(1 - 7)
3
t 7/1 77)
1 - y
(1 717
7:5
7)
7 (1 - 7)
which implies the distribution of (r')² can be presented as follows,
Table 4: Distribution column of the distribution (7')².
2
9
16
f2
1- 7 (1 7)7
(1 7)
( 7)
16 7)
7 (1 117)
thus
[(7)-]
Ey's GGo(l
E Geu(11))
[5]
(238)
I-7
48

---

Under review as a conference paper at ICLR 2023
F PROOF OF THEOREM 4
In this section, we provide the necessary proof details of Theorem It is very technical to achieve the result of Theorem 4 we outline some necessary intermediate results in Section where we provide some basic lemmas, and the proof of Theorem Tis is shown in Section
F.2
Theorem Under Assumption I Te the softmax policy defined in O The time-step T shares
fixed low bound similar (6). The initial X O, 0p O, the parameter sequence (x 1 generated according to Algorithm
3
Let 17, B satisfy
d
log |A| C² - 7)T
d
4|S| log |AT
3
(1- 12,
Pu
Po
8c
where C' is a positive scalar will be special later. Then for all E {1, . ,mn, Te =- ne, satisfies
d
18 log [A] c.(11 - -))
E
min
(J(xz)
- J(Te)
K<
Po
4
4
SS] log [A]] c. 7)
E
min [C((TT) -b++ KT
pa
80
B
|
10
where the notation E|| short for ED.:Dr- randomness over the trajectories [DD))_ TT-1
[ that denotes the expectation with respect to the
F.1 AUXILIARY LEMMA
Recall Algorithm 3. at current time t, we obtain cost value estimator Č(TO,) according to (55
ē(Te.) = (T). Cm (mO.))
(239)
where each (TO,)) is rollout estimator according to:
(.(....) Esmpol)) (re
Toe (s) Σ
po(s) =E (s),
(240)
#ES
V (s) = Est C2,
(241)
According to Proposition 4. after some simple algebra, we obtain the unbiasedness of C(TT.):
E [( = c(TO.).
(242)
Now, we provide the boundedness of ((Te,) follows,
239
(To, 2112
(243)
which implies we need to bound each (C,(T)))) where E (1,2,.m
Recall the definition of Õ (TT,) in (240). we expand as follows.
(T.)))
E
Ex-po(-)
Dies xo, (s) Epo(s) (s).
(244)
According to the iteration from Algorithm
we rewrite De. no, (s) as follows.
Vra: (s) r(s,, at), so s, ~~ Geo(1 7))
(245)
.o.
1=0
49

---

Under review as a conference paper at ICLR 2023
Now, we bound the expectation of (Te,)) as follows,
E (C((e))))
Σ Po(s))
Σ
r((esar)
(o0(11))
lEES
1=0
< EE Goo -g
r(se, ai)
(246)
seES t=0
238
|8]
E BTo 1-7)
(247)
1 1-7
Collect the results 242
243 and
247
achieve the next Lemma
18
Lemma 18. Let ne, be the softmax policy defined in (9). For each parameter Os let (Te,)). c(TT.)
be the estimator of cost value function defined in (240) and (239):
(T(TT.)) - Eempol-)
Ves ne
(s)
Σ
(o((s)
no, (8),
(248)
#ES
?(Te.) = (TT.)) (2(TT)), Cm(
(249)
no, where Ves (s) is defined in 24. Then è(TO,) is an unbiased and bounded of cost value function,,
i.e,
E [é((T))]] ]] = c(TT.))
(250)
E (Ci(Te.))
- S
(251)
m S1
E [|()(TT,)) )1
(252)
Recall Algorithm 3 we obtain the unbiased estimator as follows,
V C(TO, )1) = b C(TT,)) ):
(253)
V C(TO. x:) E c(TT,)) aL(TO,,
E
(254)
According to the estimators (26) and (26). we obtain the policy gradient estimators i.e., for each (s, a) S x A.
T, P, a), G (s, PG Ci a), 1,2, ,..... (r,
Furthermore, let the vector Sin, (8,a) a) E 1mmh collect all the policy gradient estimators of cost value function, i.e..
g ()) (ā (s, O.m, (s, (s,a))
Let G(TO, Ar) E [A) each (s, a)- eleemet is defined as follows,
G( >c) a) G (8, A, g (s,
(255)
then we obtain the policy gradient estimator of aL(Fo, Ad). d0.
G XD) aC(To. A,)
Co ACCIT,,AA0 A₂) = G : Ae), E
(256)
00,
Collect the results 254 and 256), we achieve the next Lemma
Lemma 19. ne, be the softmax policy defined (9. For each parameter Or, les C, (TT..)) ((To.)
be the estimator of cost value function defined in (44 and (239). Then, the following holds Recall Algorithm 3 we obtain the unbiased estimator as follows,
Ebb c(TT..)] iL(TO, A1)
(257)
ax.
50

---

Under review as a conference paper at ICLR 2023
Let the policy gradient G(Te 21) be defined in 255 then
aL(To. X²)
E ((Te,) Ao)
(258)
00:
F.2 PROOF OF THEOREM
In this section, show the details for the proof of Theorem 4 The proof contains two key steps: bounding the optimality gap and bounding the constraint violation. Finally, we summary the hyper- parameter setting for to obtain the results presented in Theorem 4
We rewrite the iteration
12 as the following stochastic version.
A++1 {): 1) +)++)))+>
(259)
0,+1 = 0, + ry G (To. Aτ),
(260)
where we calculate e and G Ae) according to 253 and (256). To short the expression, as before, we introduce the following notations:
( exp
(als)) no, (als)
((0) and n. no.-
EEEA exp
For each time t, we notice the estimator é(TT,) in the inner loop (see Line 3) involves m trajectories, and estimator (TTo, X²) (see Line 5) involves (A|S||A| + m) trajectories. We use Dr to collect all those (2|5||AA + 2m) trajectories,
D. = (T, (Ti i=1
(2
According rollout rule in Algorithm 4 Algorithm and Algorithm those (2|S]|A) + 2m) trajectories among D, are independent with each other.
Bounding the Optimality Gap.
Lemma 20. The average term
T Et- No (c(TT) - c(TT)) )) bounded as follows,
Σ (c(mT) - e(T.)) -
m S)
DD.
(261)
max
1
1=0
where BD.:Dr-l
denotes the expectation with respect to the randomness over the trajectories [
(D.)
Proof. According to the dual update 255
we have
IMMM MM IMMMM
Ar
(1A 11 1
259
(IIA) 7(b c(T)))) -12
(l 1/ <(TT)))1 -11
1/ E(TT))13 + 2 (6(AT)) - b))
(72 3(m))) + 2 (é(TTe) b))
172 blb 1 2n (é(=T) c(T.)) + 2n1.T(((m)) - c(Tx.)), (262)
51

---

Under review as a conference paper at ICLR 2023
where Eq. 222) holds since express (é(TT)) b) as follows,
(é(m)) b) (((())) -((m))) + (c(TT.) (obm,)-bb-)))
-b) b)+ +(((m)) (c(T)))
(263)
and the fact A = and c(TT)) 3 b, then X (C((T.) - b) S 0 implies
x (é(m)) b) v X (é(T))) - c(T+)) + X (c(m)) c(Tx)).
(264)
For each given 0-- the estimator c( ) independent of X; and X independent of (é(m)) c(m.)). Thus according to (242). for each time t. the next equation holds
IE X (é(m)) c(T))) = =0,
(265)
where E ,
Furthermore, we consider the expectation of ET-1 A (c(A)) - c(Te)) over the trajectory (De) TT-1 as follows,
D
NX -
T-2
-Enaar 2(4)
Σ
A (é(TT)) - -c(TT)) + EDr-1 A - c c(TT--)))
(266)
1=0
263
(((())))((())) c(ai))
=EDoar-2(9)
Σ (e(T))
(267)
where Eq. (66) holds since the term Et= \T (c(TT)) c(Tx)) is independent of the trajectories Dr-1. which implies
N (c(m)) - c(Tre))
Dr.
-Epoar-z(s)
Σ
ED, ( c(TT- 1)]]
Let us expand recurrently according to the mathematical induction, achieve
Dr.:Dr-1
Σ (e(m)) c(m))) 0.
(268)
Recall the result (26 which implies
n b é(T)) 2nd, (é(m)) c(T()) + 2nA (c(T)) - e(Tx))) 2 0.
(269)
Recall the result (268 and we consider to take expectation of (269) over the trajectory {D.)T=) then achieve the next equation
TT
E Ep DT-1
Σ
2 lb E(T))11 2nA, (é(m)) c(TT)) + 2nd, 2n(T(c((m)) c(T.))) 0.
(270)
52

---

Under review as a conference paper at ICLR 2023
rewriting 270
obtain the following equation,
1
Dr
X (c(TT) -((,))))()))
T
T-1
S.D::Dr
17
Σ
[b - o(T)))1
(271)
2T
<EDo::r
11
[||b12 + ([O(TT)) (2)
2T
t=0
$ 5570mma
Do:
Σ 11((T))
(272)
27
t=
m|
m|s|
5 max
21177
2
62
max
+
1-71
(273)
where last Eq. 273
holds since
Er
|[(())11
= Dooor 2(4)
|((TT)1 tB,,_, (10(m
(274)
252
m|S
E Doior
(275)
1-7
S||| T,
(276)
7
where (74) holds since the term ET= ([Ō(T:) 12 is independent of DT-1i
Eq. (76) holds since we expand recurrently according (275) by the mathematical induction; Taking
the result (276) into (272). we achieve the result (273).
Lemma 21. The optimal gap is bounded as follows.
dPa x,
log |A|D
Dr.
reT min (1(T.) ( J
5 (1 7)
Po
T
where the positive scalar D' will be special later.
Proof. Due the unbiasedness of Q.o a), D (s) according Algorithm 4 and Algorithm 5
we achieve a similar result as 133 in Lemma 16 but we need to consider the over the trajectory (o.
Concretely, we replace the terms with respect to expectation by the corresponding estimators, then we have
DD
J(T.) T
Σ
(
T Σ (c(..)) c(..)
t=
1
log [A]
2x
+ 211
(277)
T
Pmin (1 - 7)
Furthermore, taking Eq. (73)
(we have also presented it in Lemma
20 in to Eq (77), obtain
Ep.:Pr-: ((T.)
1
1
Σ
T-1
(
x log IA]
+
2x
n
4xCr
82 b
m|S]
T
n/T'
Pmin (1
2T
1-
(278)
53

---

Under review as a conference paper at ICLR 2023
The above result (278)
implies
Dro:Dr-1 min (J.)) - {(x))) K<
<
x||| log |A|
2x Pmin (1 - -) 2
+
!
(AxCi + bmax + m|[|
r/L
1 1- 7
(279)
It similar to the analysis of result (167). if the next condition (280) holds, then above
obtains the optimal gap (that is shown in Eq. (833) for the difference over (J(++) [(T+))
x S log [A]
?
4xC1 + 62 + 1-7) max
m|S
(280)
1/
2
which implies
x log |A|
d
|S] log AA| 1 (1 -) T'
S (2xC1 + 1 + mC2 2(1-))"
(281)
may
T
Po
where the positive scalar C' is defined as follows,
1
m|S|
c = 12x +
2 max
1-7)
+oc.
(282)
Taking the step-size 281 into 279).. we obtain the optimal gap follows,
Dr.
min
(J(Tx) I(TE)) KT
(283)
X log |A|
1 62 2xC1 +
+ m|s1
2x
(284)
T
2 max
Pmin (1 - 22
deo
SS] log IAI
2x
20, (Mi +1)+ + Pmiia (1 - 72)
(285)
(1 7),
Po
107
S|5 log |A|
m
6max +
(1
+1)
(1 7)c,
Po
T
(1- 7)2
1 --
dgo
+
(286)
(1
y),
Po
Panin (1 - -2
deo
[S] log |A
D22
doe
Dj + Pmin (1 - --)
(287)
y).
Po
T
Po
10
1
m|||
where Eq. (25)
holds since we choose the constant M/ satisfies 2x
62
i.e.,
2
max
dPo
1
b2 maxx
|
M
7)c,
3
Umaxx
5 (288)
Po
7
4m
4(1 7
the constants DJ and D2 in (287) are defined as follows,
DJ = (1 7)
2m
Drux + 1 1--) (Mi+1) + < +00, D2 = C.
2 < +00.
(289)
Finally, it is similar to the same analysis of (75). we conclude that if
(D')²
T 2 (1 - --) log Alp D2
(290)
which implies
ED
rer min (J(TT) J(TT)]] 5
2
xx
S |AA
(291)
7)
Po
T
54

---

Under review as a conference paper at ICLR 2023
Bounding the Constraint Violation.
Lemma 22. For any given [|Al2 E [0, where the positive scalar 3 will be special later, the term
1 E (A+ 2) (b c(T+)) is bounded as follows,
T
T-1
m|s]
DD
T a (Ax- TT - c(Ti))
+ max +
(292)
2x/7
2
1
1=0
Proof. We consider the parameter ||ll| [0, 3]. where the positive scalar B will be special later. According to the update rule (259), we have
A1t1 2 = (2, 7b e(m)))+ X x|2
12
1 A 7b c(a))) x
2 A Ā
(n )) S TTb-b---- e((T)) 17² ||b -
2
2
m|S]
< A X
2n A) (b- - e(TT)) )) + n7² 6a
(293)
where the last Eq. 2933 holds the next result (294) holds, which is contained the previous Eq.
273
m|S]
| - m(m)))) |lb|| + [[0(m=) 112 z 1 + 1-
(294)
We rewrite Eq. 293 as follows,
| x
A x1 2n X) (b (( + +7²
62 1a +
m|S|
(295)
1 1-7)
Summing Eq. (25) from = to T 1, we achieve the following equation
x 213 x Ao 5
6 + m|||
Ar
2m Σ
() (b Trp²
1=0
which implies
T
Auu - x x|(
m|S
(2. - (b-
S
+
+
T t=0
2n/T
2
1
|>|
n
2
b
+
ml|5
(296)
2nT
2
2
2(1 7)
According to 242
taking expectation on Eq. (26)). we obtain
Dr.:
T
E0.
Tb c(T.))
2T/
17
max
+
m|S]
(297)
1=0
where we use the fact E[c,] c(T) 242 and A is independent of é(TT) for given 0.-1-
Lemma 23. The constraint violation is bounded as follows,
2m
dPo
{S] log A
Epg:Dr-
min (C.(TT)
bib+
<
3 - | Alo 1 (1
KT
22
Po
- (1-7)4T
2m
2 + (1 2122
doo
|S] log LA|Di
8 |
Po
(1- 7T
55

---

Under review as a conference paper at ICLR 2023
Taking (99 into 277
we obtain
T-1
T-1
T-1
DD
[T+.)
1
Σ
(m+)
1 T
Σ
XT (b- c(T.))
T Σ x (b- c(Ti))
T
1 T
X|8| log |A|
1
X
2
2x
+1 2x( + maxx
b
+
2(1 ((1-7)
m m||1
(298)
27y
2
Pmin
(1
- 7)
Due to c(T,) = b, and x =
0, then we have
1 T-1
T
T-1
Dr.:Dr-1
[(T.)
(
+
XX (b. c(T.))
Σ 1=0
xT (b. c(TT))
T
T 1=0
T
t=0
1 T-1
1 T-1
DEDO:D--
J(T.))
Σ
J
(m)
Σ
x
(b c(Ti))
(299)
T
T
1=0
It is similar to the previous proof from 186 to Eq. 191. we need to show the boundedness of the expectation Ep [(x.) ( + + Xe (f,) - b.) defined in (301), which is a fundamental result for us to show the boundedness of the constraint violation.
Recall c(T) = (C1 (2(m) Cm.( and À (2 7m combining the
result 29% and (299). and taking consideration to the step-size defined in (8 we have
1 T-1
Dr.:
[(T.) T
( +
x
(c(
-b)
T 2=
t=0
1 T-1
Dr-
J(T.) T
Σ ((TE) Σ
1
Σ
(C.(Te) -bi)
(300)
T
t=0
1=
-TD
J(m+) J(a)) +
Ne (C.(tt) - bb:)
(301)
DED.:Dr
(TT.) J ( 31 (c((t)) - bb+
(302)
298
x|5| log |A|
|
2x
Max
m S|
+ 2m
+ Pmin (1 - 7)2
+ 2xC1+ +
T
2
2(1 7)
(303)
307
x log |A|
+ m z2 +
2x
+1
2xC1 +
12
max
+
m|S]
(304)
T
"
2n
Pani (1 - 7)2
2
2(1 7)
x|5| log A
1
m||1
2x
22xC1 +
-2
32
(305)
2(1 - 7)
2n/T
Punin( (1
7)2
307
287
1
2m
(S] log LAIDi
d
+ (1 7/
(1 7)2
Pa
Punin
7)3T
Pa
00
(306)
where (31 as follows
holds due to the same reason as
(844 : Eq. 302 holds since we set the parameter A
2
β V log A||
if To (C,(m.)) - bb,)= 2 0,
(1 7)2"
(307)
0,
if ET- - -b)) <0
Furthermore, let
1
2m
dec d
|S| log (A|Di
D2
dec
8 :=
(11 (11-))
+
(1 4/
Po
T
Pmin (1 - 37
Po
56

---

Under review as a conference paper at ICLR 2023
then the results (306) implies,
E Dr: [T(T)) - ((ae) + (c()t(())) - -b]-] s
(308)
Finally, it is similar to the proof (196), we have
Dr
min (Ci(Te)
bit+
(309)
KT
1
(1-1)
1
2m
d
S log LAIDi
D2
d
1
(1 4/2
Po
T
Pmin
- 3)3
Do
Furthermore, let
(D2)²
T
(310)
((1 7)2 2m/ 2)/ Pinia 11 log |A|
then we obtain
2
2m
deo M1
S log |A D (1-7)a7
EDo:Dr-1
min (C((TT) bib+
S
1
KT
3 - 1|2,1100
(1 7222
Po
2m
2 + (1 11-71 2212
deo
S log LAIDi
(311)
3 || |0x0
(1->)
Summarizing the Conclusion under Special Hyper- Param--a Setting.
Finally, recall the condition for the term T' in (200.
310p. we conclude if the time-step satisfies
1
(D²)²
T max
(1- ((1-7)² 2 + 2m 2m/22)2
[ log [ D
the step-size 7) defined in (28T) satisfies
do
1og [A| (1 7) T
Pu
and the constant term 3 satisfies
2 (1 7)
S log A
(312)
157
1
deo
|S] log |A|
(313)
(1 7)c+
Po
(1 - 7)4
deo
D' S log [A]
(314)
(1 3,,
Po
where we define the constant D' follows
D' D'
c.
Then, according (75) and 198
the following holds
SS] log LA 7T
Ep,:Dr-1
min (T.).) (m+)]
2
m.
KT
Po
2
2m
dou
S |AID
EDg:Dy-1
min (CT(Te) bib+
1
KT
3 ooo
(1 (1- 21-2
Po
(1-7)²T
where each i E (1,2,...,n) ,m). This concludes the proof of Theorem
57


Reviews:
[{"review_id": "YdvQqNXlEY7", "reviewer": "Reviewer_zsRP", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies primal-dual approach to solve constrained reinforcement learning (RL) problems under the framework of constrained MDPs. It studies the global convergence of policy gradient primal-dual method under softmax parameterization, for both model-based and model-free settings. The paper is in general well-written, and easy to follow, with some solid theoretical results.", "summary_of_the_review": "The paper studied a fundamental setting for safe RL: solving constrained MDP using primal-dual policy gradient methods, under tabular softmax parameterization. The writing is clear and easy to follow. However, there is some technical issue with the current paper.", "strength_and_weaknesses": "Strength: The paper is in general well-written, and the literature review is thorough.\n\n\nWeakness: Some of the theoretical arguments are not accurate/correct.\n\n1. The motivation of studying policy gradient primal-dual method might need more justification: given the existing results on natural PG primal-dual method (with potentially better rates, since the $c_*$ in the result in this paper might be very small), why should we still focus the vanilla PG-PD algorithm, with tabular softmax parameterization (except out of theoretical interest)?\n2. Some of the claims regarding technical contributions might need improvement: for example, it was claimed with quite some space in the abstract and intro that, designing unbiased value function estimators with finite-horizon trajectories for the infinite-horizon case is one of the contributions. However, it is known that such a technique has been widely used in the literature, e.g., Zhang et al., 2020, Agarwal et el., 2020, Ding et al., 2020, etc.\n3. Some of the comparisons with the literature might need to be improved. For example, the results in Table 1 might not be completely comparable: some of them are for finite-horizon settings, and more importantly, some of them are the online exploration setting, while some of them are the generative model setting; some allow constraint violation and some do not; are the sample/iteration complexity in the table referring to suboptimality guarantee or constraint violation guarantee? I am not sure if it is accurate to compare them this way.\n4. As it is a theory-oriented paper, it would be helpful to summarize the \"novelty of the Techniques\" (and the intuition) upfront, in introduction, so that people can better compare and understand the results.\n5. Some parts of the writing might need more care. \nTypos:\n1) what is the definition of $\\Pi_S$ in (3)? if it means \"stationary policy\" (which misses \"Markov\"), why it is \"assumed\" to be convex in Theorem 1? Is it a subset of it?\n2) would it be more accurate to write $\\in\\argmax$ instead of $=\\argmax$ in (4)? Similarly for the definition of $L_D(\\lambda)$: does the maximizer have to be unique? So is the optimal dual variable $\\lambda_*$.\n3) Sentence before (12): the problem (8) should also be \"constrained\", not \"unconstrained\".\n4) Right after Algorithm 1: \"adapted\" -> \"adopted\"? \n6. I think there is a fundamental issue with the technical part of the paper: it is known that the optimal policy of CMDP might not be deterministic. See http://readingsml.blogspot.com/2020/03/constrained-mdps-and-reward-hypothesis.html for example. However, the analysis in the paper strongly depends on the “optimal policy” being deterministic: see argument around (14) and page 33. \n\nGiven 6, I might not be able to recommend acceptance of the paper given its current form.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "IIdz8uI2_7", "reviewer": "Reviewer_YnNr", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors have considered the problem of constrained RL which is formulated via constrained Markov decisions process. The problem is then solved via first formulating the Lagrangian, and writing down the primal dual method. The authors have used the vanilla policy gradient in the primal domain to solve the problem. Theoretical results are derived. The paper is nicely written. ", "summary_of_the_review": "The most of the mathematical tools/analysis used in the paper already exists. The major concern is regarding the contribution/novelty which is not significant enough. ", "strength_and_weaknesses": "*Strengths*\n\n- The paper is well written and easy to follow.\n- The theoretical results are derived in detail.  \n\n\n*Weakness*\n\n- The contribution is incremental and limited. \n- As mentioned by the authors, the problem is already studied with the natural policy gradient. So what are the additional challenges to consider vanilla policy gradient? Wouldn't that follow directly? \n- The results in this work follows directly from NPG-PG and Paternain's work, what are the specific challenges being addressed in this work. The challenge of designing an unbiased gradient estimator via utilizing geometric distribution rollouts is already addressed in Paternain 2018. \n- The authors have discussed the strong duality and slater's condition with policy pi. Does these holds for the softmax policy parameterization as well? If not, then how to utilize the similar concepts? \n- Sec 4.2 in the paper is not novel. \n- There is no empirical evidence of comparison between PG-PD and NPG-PD. This is also a major downside of the results. \n- Given the analysis in Ding et al, it is required to mention the additional mathematical challenges  exist to do the analysis in this paper. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "769jqk9M3l", "reviewer": "Reviewer_5KTD", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers primal-dual approach to solve constrained reinforcement learning (RL) problems, where we formulate constrained reinforcement learning under constrained Markov decision process (CMDP).", "summary_of_the_review": "This paper considers primal-dual approach to solve constrained reinforcement learning (RL) problems, where we formulate constrained reinforcement learning under constrained Markov decision process (CMDP). The paper needs significant modifications to be at the level of ICLR paper as mentioned in weaknesses. ", "strength_and_weaknesses": "+: The analysis seems correct. \n\n-: The related work is misrepresented. The generative model should give additive samples, and not multiplicative. \n\n-: The approach is standard, and novelty seems limited. \n\n-: The constraint violations in the literature have been improved to zero violations, which should be incorporated. \n\n-: Based on the table presented, the results do not seem the state of the art. \n\n-: The paper is giving iteration complexity, and not sample complexity.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2ppf7XJ25q", "reviewer": "Reviewer_akKw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the iteration complexity of primal-dual gradient descent-ascent algorithm in safe RL problem. In the soft-max tabular policy setting, the author is able to provide the best iteration complexity rate for this type of algorithm.", "summary_of_the_review": "Overall this paper provide some solid results for a fundamental problem However, as I mentioned in previous sections, the comparison with SOTA is somehow misleading and not fair thus I hope the author can clarify that part so that we can justify the contribution of this paper. ", "strength_and_weaknesses": "Strength:\n(1) This paper is clearly written and easy-to-follow\n(2) The technical proof is solid and comparison with SOTA is complete\n\nWeakness:\n(1) The comparison with SOTA is not fair (I will include in the next section for detail). Thus, it is difficult to justify the contribution of this paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject