Sample-Efficient Constrained Reinforcement Learning with General Parameterization
Authors: Washim Uddin Mondal
Vaneet Aggarwal
Venue: NeurIPS 2024 poster (2024)
Keywords: Constrained MDP
Sample Complexity
Constraint Violation
Global Optimality.
Primary area: reinforcement_learning
TL;DR: New state-of-the-art sample complexity for CMDPs.

Abstract: We consider a constrained Markov Decision Problem (CMDP) where the goal of an agent is to maximize the expected discounted sum of rewards over an infinite horizon while ensuring that the expected discounted sum of costs exceeds a certain threshold. Building on the idea of momentum-based acceleration, we develop the Primal-Dual Accelerated Natural Policy Gradient (PD-ANPG) algorithm that ensures an $\epsilon$ global optimality gap and $\epsilon$ constraint violation with $\tilde{\mathcal{O}}((1-\gamma)^{-7}\epsilon^{-2})$ sample complexity for general parameterized policies where $\gamma$ denotes the discount factor. This improves the state-of-the-art sample complexity in general parameterized CMDPs by a factor of $\mathcal{O}((1-\gamma)^{-1}\epsilon^{-2})$ and achieves the theoretical lower bound in $\epsilon^{-1}$.

Sample-Efficient Constrained Reinforcement Learning with General Parameterization
Washim Uddin Mondal Department of Electrical Engineering Indian Institute of Technology Kanpur
Vaneet Aggarwal School of IE and ECE Purdue University West Lafayette, IN, USA 47906 vaneet&purdue.cm edu
Kanpur, UP, India 208016 wmondal@1 meellliiikkkee ac
Abstract
We consider a constrained Markov Decision Problem (CMDP) where the goal of agent is to maximize the expected discounted sum of rewards over an infinite horizon while ensuring that the expected discounted sum of costs exceeds a certain threshold. Building on the idea of momentum-basse bbssed acceleration, the Primal-Dual Accelerated Natural Policy Gradient (PD-ANPG) algorithm that ensures an global optimality gap and constraint violation with (((1-)) sample complexity for general parameterized policies where denotes the discount factor. This improves the state-of-the-ard sample complexity in general parameter- ized CMDPs by factor of O(11 - -1---- and achieves the theoretical lower bound in e
develop
1 Introduction
Reinforcement learning (RL) is a framework where an agent repeatedly interacts with an unknown Markovian environment find policy that maximizes the expected discounted sum of its observed rewards. Such problems, often modeled via Markov Decision Processes (MDPs), find applications in many areas, including transportation [T], communication networks (2). robotics B etc. In many applications, however, the agents must also obey certain constraints. For example, in a food delivery network, the orders must be delivered within a stipulated time window: the marketing decisions of firm must satisfy its budget constraints, etc. Such constraints are incorporated into RI. by introducing a cost function. In constrained MDPs (CMDPs), the agents not only maximize the expected sum of discounted rewards but also ensure that the expected sum of discounted costs does not cross predefined boundary.
Finding an optimal policy for a CMDP is a challenging problem, especially when the environment, i.e., the transition function, is unknown. The efficiency of solution CMDP measured by its sample complexity, which essentially states how many state-transition samples it takes to yield policy that close to the optimal one while also ensuring that the expected sum discounted costs does not violate the imposed boundary by more than amount. Many articles in the literature solve the CMDP with an unknown environment. Most of these works, however, focus on the tabular case where the number of states is finite. These solutions cannot be applied to many real-life scenarios where the state space is either large infinite. To tackle this issue, the concept of policy parameterization must be invoked. Unfortunately, as exhibited in Table [] only a few works are available on CMDPs with parameterized policies. While, for softmax parameterization, the state-of-the-art (SOTA) sample complexity is (O the same for the general parameterization Õ(e-1) which is far from the lower bound l -2). .. It should be noted that the number of parameters needed in softmax parameterization (SA) where S, A are the sizes of the state and action spaces of the underlying CMDP. On the other hand, general parameterization uses d < S.A number of parameters, which makes it appropriate
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Algorithm
Sample Complexity
Parameterization
PMD-PD 9
Softmax
PD-NAC 10
0
Softmax
NPG-PD
0((1-)) --2)
Softmax
CRPO 6
0((1-))-e
Softmax
NPG-PD [5]
0(1--))*8
General
CRPO 66]
0(11-))186
General
C-NPG-PDD
0(117))886
General
PD-ANPG (This Work) (((1-)));-
General
Lower Bound
Q((1 (((1-))-86
Table 1: Summary of sample complexity results on CMDP with parameterized policies. The parameter y indicates the discount factor. The dependence of the sample complexities of PMD-PD and PD-NAC on is not depicted in [9] [0]
for dealing with large or infinite states. Given the importance of general parameterization for large state space CMDPs, the following question naturally arises: "Is possible solve CMDPs with general parameterization and achieve a sample complexity better than the SOTA Ō(e=)) bound?"
In this article, we provide an affirmative answer to the above question. We propose a Primal- based Accelerated Natural Policy Gradient (PD-ANPG) algorithm to solve y-discounted CMDPs with general parameterization. We theoretically prove that PD-ANPG achieves e optimality gap and e constraint violation with Ō((1 - -) -2)- sample complexity (Theorem 1) that improves the SOTA ((( 7) - sample complexity result of [4]. closes the gap between the theoretical upper and lower bounds of sample complexity in general parameterized CMDPs (in terms of e E- which was an open problem for quite some time (see the results of S] in Table
1.1 Challenges and Key Insights
Our algorithm builds upon the idea of primal dual-based NPG 7 4. However, unlike the previous works, we use accelerated stochastic gradient descent (ASGD) in the inner loop to compute the estimate of the NPG. The improvement in the sample complexity results from key observations. Firstly, we establish a global-to-local convergence lemma (Lemma (3), which dictates how the global convergence of the Lagrange function is related to the first and second-order estimation error of the NPG. Here, via careful analysis, we show that the first-order term can be written as the expected bias of the NPG estimator (i.c., the difference between the true NPG and the expectation of its estimate). Secondly, we show (Lemma 5 and its subsequent discussion) that the bias of the NPG estimate can be interpreted as the convergence error of an ASGD program with stochastc (i.e., deterministic) gradients. These, combined with the ASGD convergence result provided by [8], lead to convergence result of the Lagrange function (Corollary [
Finally, Theorem segregates the objective and constraint violation rates from Lagrange convergence. Corollary [ shows that Lagrange convergence error is bounded by an independent function of C (the dual learning rate). One might, hence, be tempted to make ( arbitrarily small. However, our analysis shows that although small ( leads better objective convergence, it worsens the constraint violation rate. We demonstrate how to optimally choose Ç to reach the middle ground which eventually leads us to ( -2) sample complexity.
1.2 Related Works
Unconstrained RL: Many algorithms solve MDPs with exact gradients
12 13 4 5 16 More-
over, many works use generative models to show either first-order [17 18
19
20
21 or global
convergence 22 23 24 25 26 27
'We would like to point that the sample complexity of C-NPG-PDA reported in is Ō((1 7) -----6--1 However. the result is erroneous. The authors have subsequently corrected their result, and the sample complexity has been modified Ō((1 - in the arXiv version (updated May 2024).

---

Constrained RL; The tabular setting is well investigated. and many model-based [28] 29 30 31 and
model-free 6 30 32 331 algorithms are available the literature. In comparison, there are relatively fewer works parameterized policies. Policy mirror descent-primal dual (PMD-PD) algorithm was proposed by 9 that achieves ((e-3) sample complexity for softmax policies. For the same parameterization, [0] achieved (c)=) sample complexity via their proposed Online Primal- Natural Actor-Critic Algorithm. The primal-dual Natural Policy Gradient algorithm suggested by [5] yields O and O O)) sample complexities for softmax and general parametrization respectively. [6] also proposed a primal policy-based algorithm that works for both the softmax and general function approximation cases. The state of the art for the general parameterization is given by 44) where the O) sample complexity is obtained. This work improves upon this direction to obtain Occ-2) sample complexity. The comparisons summarized in Table
2 Formulation
Let us consider a constrained Markov Decision Process (CMDP) characterized by the tuple M = (S,,,rrc, 7.7,)) p) where S, denote the state space and the action space respectively, S A [0, 1] defines the reward function, S x A - [-1,1] 1] is the cost function, P S x A + ((S) indicates the state transition kernel (where A(S) is the collection of all probability distributions over S), y is the discount factor, and E (SS) is the initial state distribution. Note that the state space S, our setting, can potentially be a compact set of infinite size. However, for simplicity, we assume to be countable. The action space, A. is assumed to be of finite size. The range of the cost function chosen to be [-1, 1]. rather than [0, 1]. ensure that the constraint in our central optimization problem (defined later in (2) is non-trivial. A policy, S - A(A) is defined as a distribution over the action space for given state of the environment. For a given policy, æ, and a state-action pair (s, a), we define the Q-value associated with {r,c} as follows.
8
O7 a 2 E
Σ
r' a.) su = S. 8.00
where E,, is the expectation computed over all r-induced trajectories {( a=) where 8+11 P(st, at) and a (st), Vt E {0, 1..... Similarly, the V-value associated with policy т, state s. and g E {r,c) c) is defined below.
(s) - E
Σ
r'g(s) =s Σ
- (s.)s)
Below we define the advantage value for policy π, a state-action pair (s, a). and g E (r.
(s, a) a Q7 a) (s)
Define a function 9.p- Vg E (r,c} as follows.
J A E.-pl (5)(
Σ (a))))))))))((
where d E A(S) is the state occupancy measure given by,
(x) = (1 - 7) Σ 'Pr( 8/50 ~ n), Vs E
Similarly, the state-action occupancy measure is defined as, (s, a) d;)
V(s,a) E S
(1)
Our goal is to maximize the function J over all policies ग while ensuring that J does not lie below a predefined threshold. Without loss of generality, we can formally express this problem as,
max Jr subject to: J 2 0
(2)
the state space, S, is large or infinite (which is the case in many application scenarios), the policies no longer be represented in the tabular format; rather, they are indexed by parameter, 0 e. In
3

---

this paper, we assume e = R.. Such indexing can be done via, for example, neural networks (NNs). Let (0) & J.p. This allows us to redefine the constrained optimization problem as follows.
max (0) subject to: Je.p(0) 00
We assume the existence of at least one interior point solution of the above optimization. This also known as Slater condition which can be formally expressed as follows.
Assumption 1.
There exists such that (e,p(0) 2 Calater for some Calater E (0, 1
Algorithm
The dual problem associated with the constraint optimization (3) can be written follows.
min max (0,)( where (0, A) - (0) + XJ (0) X BEG
(4)
The function, (t.) :) is called the Lagrange function while À is said to be the Lagrange multiplier. The above problem can be solved by iteratively applying the following update rule Vk E (0, .. K 1}. starting with (Ou, Au) where Og E è is arbitrary and λu= = 0.
0k+1 02 + (0x)) VeJr ( (On, Xx)
(5)
AR+1 = Px A - (Ox)
(6)
where 1 learning rates, PA denotes the projection function onto the set, A A [0, Amax) and is the Moore-Penrose pseudoinverse operator. The choice of Amax will be specified later. Note that the update rule of / is similar to that of the standard policy gradient method except here the learning rate, is modulated by the inverse of the Fisher matrix, (0) which is defined below.
F (0) E (( [V log (a|s) @ V log The [a)ass)]
(7)
where & indicates the outer product. Using variation of the classical policy gradient theorem [3] one can obtain the gradient of the Lagrange function as follows.
1 1p A), where Hp A) & E ((s,))0550 AF. (s, V) log (alas))
VOJL.
and ATA (s. a) A (s, a) AA (s.
In most application scenarios, the learner unaware of the state transition function, P, and thereby, of the advantage function, A, and the occupancy measure, v/0 This makes the exact computation of (0) and H Hp A) impossible task. Fortunately, there is way obtain approximate value of the natural policy gradient w A (,(0)) 1, (0,)) A) that does not require the knowledge of P. Invoking B), one can prove that w is solution of quadratic optimization. Formally, we have,
wa. E arg min min (w, 0, A),
1 2 (s.a)~07
[
1 [
']
where Lyz0 (w, 0,
A A (s, w W
log log To(als)
The above reformulation opens up the possibility to compute wß. via a gradient descent-type iterative procedure. Observe that the gradient of L, (-,0, can be calculated as follows.
VuLygo (w, 0. A) F2)
(0,
(10)
Algorithm describes a procedure to obtain unbiased estimates of this gradient. This is inspired by Algorithm 3 of [12] Additionally, observe from (6) that the update of the Lagrange variable, À requires the computation of (0) which is also difficult to accomplish without having an explicit knowledge about P. Algorithm also provides unbiased estimation of the above quantity.
Algorithm firrtt samples horizon length, T, from the geometric distribution with success probability (I 7) and executes the CMDP for T instances following the policy, ze. starting from state so p.

---

Algorithm Unbiased Sampling
Input: Parameters (0, w, A, 7), Initial Distribution p
2: T ~ Gco(1 - 7) Su ~ p. au ~ (su)
3: for (0,... ,T-11 1) do
4: Execute új observe 8--1 ~ P(sj, az) and sample aj+1 ~ mo(s++1)
5: (0) Σj= c(s,, az), ($, t (sr, ar)
6: ~~ Geo(1 7). (sp, ao) ())
Q-function Estimation
7: for jE (0. ... 1) do
8: Execute aj. observe 8J-1 P(sj, az), and sample az+1 (8(+11))
9: for ge fr,c} do
10:
(5, à) + A(s.0a))
11: T~ Gco(1 - 7), 80 + 8, au ~ ne (so)
> V-function Estimation
12: for mnje (0.... T
do
13:
Execute 0j. observe 8--1 ~ P(aj, az), and sample 0s+1 ~ (8(++1)
14:
for g (r, do
vi - Σr 2j=0
[(8]. ag)
16:
Aga à) Q (8, () (8)
17:
Estimation of Relevant functions
A (3, à) + A. (3, a) - AA (5,a)
(11)
(0(0) + Volog To (a 8 Vo log (a(
(12)
H,) < - (3. V (a)3)
(13)
18:
Gradient Estimate
1
Vah (w, - (()W 1- H,(0, 2)
(14)
Output: (0), V Vu 0,)
The total cost observed in the resulting trajectory is assigned as the estimate (0). The state-action pair (Sr, ar)) can be assumed to be an arbitrary sample (8, â) chosen from the occupancy measure 1/50 The algorithm then generates a no rg-induced trajectory of length T ~ Gco(1 - 7), taking (8, â) as the starting point. The total reward and cost observed in this trajectory are assigned as Q (3, â) and Q (8, â) respectively. Next, another ro-induced trajectory of length T ~ Geo(1 - 7) is generated assuming the state, as the initiation point. The total reward and cost this trajectory are assigned as V. (8) and ViTo (3) respectively. For g E {r,c), c), an estimate of the advantage value is computed as Age [8, à) = TTTa (8, a) n (8). Finally, the estimates of F, (0) and H0 A) are obtained via (12) and (13) respectively which produces estimation of the desired gradient in (1).. The following
Lemma demonstrates that the estimates produced by Algorithm [ are unbiased.
Lemma 1. Let (8), L. (w, 0, X) be the estimates produced by Algorithm for predefined set of parameters (w, O, A). The following equations hold.
E [0)0 = (0) and E T. (ws 0, A) w. 0, = (u.
In the absence of knowledge about the transition model, P, one can utilize the estimates generated by Algorithm [ as good proxies for their true values. In particular, one can obtain an approximate value of the natural policy gradient Wā, by iteratively minimizing the function Lyyo (- 8, X) using the
gradient estimate VuLL,,5 (w, 8, A). On the other hand, using the estimate (e), an approximate update equation of the Lagrange parameter can be formed. Algorithm P Juees these two ideas obtain policy that is close to the optimal one.
5

---

Algorithm 2 Primal-Dual Accelerated Natural Policy Gradient (PD-ANPG)
Input: Parameters (lo, Ao), Distribution p. Run-time Parameters K, H. Learning Parameters
7) a, 8,5.
2: for k {0,- ,00,..,444 - 1] do
Outer Loop
3: Xo. Vo 40
4: for (..
do
Inner Loop
5:
> Accelerated Stochastic Gradient Descent
Y4 t axn + (1 a)v
(15)
G VuL, (w, 24) Ak) (Algorithm
6:
X/+11 Yh 86
(16)
2h - Byn + - B)vB
(17)
Vh+1 EG
(18)
7:
Tail Averaging:
2
Wk
Σ Xh.
(19)
H
4 <
8: Obtain (0k) via Algorithm
1
9: Parameter Updates:
Bc+1 <- 0k + nywk
(20)
AR+1 PA(Aa (Jo,p (0x))
(21)
10: Output: {8x 1= K-1
Algorithm| haa a nested loop structure. The outer loop runs K number of times. given instance, k. of the outer loop, the policy parameter 0g and the Lagrange parameter, Å are updated via 20 and (2I). The estimate, Je,p(0p) is computed via Algorithm On the other hand, wk. the approximate value the natural policy gradient W is obtained by iteratively minimizing L L, (-. 0k. Ax) in
H number of inner loop steps via the Accelerated Stochastic Gradient Descent (ASGD) procedure as stated in [] ASGD comprises the iterative updates (15) (18) with tunable learning parameters (a, B. E. 8) followed by a tail-ave averaging step [9). The gradient estimate utilized in (16) and (18) is obtained via Algorithm[] T It is worth mentioning that existing NPG algorithms such as that given in 7 typically apply the SGD, rather than the ASGD procedure, to obtain Wk. The difference
between these subroutines is that while SGD uses only the current gradient estimate to update ASGD considers the contribution of all previous gradient estimates (momentum) using its convoluted iteration and tail-averaging steps.
Analysis
Our goal in this section is to characterize the rate of convergence the objective function and the constraint violation if policy parameters are generated via Algorithm 2 assumptions needed for the analysis.
We start by stating a few
The log-tikelihood function is G-Lipschitz and B-smooth where B,G 0. Formally, the following relations hold v0, 01, E θ, and V(s, a) S A
Assumption 2.
Vo log To (a(s))) S G, and V log ne, (als) V log ne, (a|s)] s B| - 02
Remark 1. Assumption 2 is commonly applied in proving convergence guarantees of policy gradient- type algorithms [35 7 This assumption obeyed by many widely used policy classes such as the class of neural networks with bounded weights.

---

Assumption Assumption/iimmllies the boundedness of the gradient of the Lagrange function. This can be formally expressed as follows.
Lemma 2. If Assumption 2 holds, then the following inequality is true vo and VA E
IV (01 S G(1 + Amax)
(1 7)-
Proof. Statement (a) can be proven using along with Assumption 2 and the facts that |AΣ, (8, a)l
bounded by (1 + A1 - 77) and X S Amax AA A.
The result established by Lemma will be pivotal in our further analysis.
Assumption 3. The compatible function approximation error defined in ( satisfies the inequality Lyg- (W 0, >) S Cbias/2, 48 E θ and Aλ E A where x² is solution to the original constrained optimization problem 2 and w is defined in ( The term Ebias is non-negative constant. The factor 2 is used for notational convenience.
Remark 2. The term ébias quantifies the expressivity of the parameterized policy class. For example, if the parameterization complete i.e., includes all possible policies (such as in direct or sofimax purameterization) then ébias 0 (72). A similar result can be proven for linear MDPs [36]. For incomplete policy classes, we have Ebiss > However, if the class is sufficiently rich (such as neural networks with a large number of parameters), Cbiss be assumed be negligibly small (37].
Assumption 4. There exists positive constant uF such that F2(0) la is positive semidefinite Le., (0) ž prra. vO E ④ where La is a d x identity matrix and F.(.) is defined in 7
The property of the policy classes laid out in Assumption 4i called Fisher Non- DeneDeeenerayy (FND) which essentially ensures that 40 E O, the Fisher matrix (0) is away from the zero matrix by certain amount. Observe that the Hessian of the function, (-)x - L, (-,0, A) is (0). Therefore, Assumption also indicates that 4e,x is pu--ttonnlly convex. This assumption is commonly applied in analyzing policy-gradient algorithms [4] 38 7. Assumption 4 also ensures that the matrix F, (0) invertible, which, turn, implies the uniqueness of the maximizer W arg min (w))
39
describes concrete set of policies that obeys Assumption
2
4.1
Local-to-Global Convergence Lemma
Recall that our goal is to establish the global convergence rates. Lemma 3 (stated below) is the first step in that direction. Specifically, it demonstrates how the average optimality gap of the Lagrange function can be bounded by the first and second-order error of the gradient estimates.
Lemma 3. If the parameters 10x, >u K-1 are updated via 200 and and assumptions 2 hold, then the following inequality holds for any K.
1
K
E
- (OK, Ato)
Ebins
+
G
K-1
E||
E
Lw Ok, AR]
wflll
K
K
k=0
k=
(22)
K
Bn
1 nK
E
11
E
Eendgt [KL( (-1s) To, (+Is))
2K
where wi. A Ne Wh, constrained optimization Finally, wi is the approximation of Wi given by (99 and K L(---l) is the KL-divergence.
Ao the natural policy gradient defined (9. and n²" the solution to the
Note the presence of the term, Cbias in (2 It shows that due to the incompleteness of the param- eterized policy class, the average optimality error cannot made arbitrarily small. worth mentioning that many existing CMDP analyses (such as (4) follow path similar to that of Lemma
3 However, while the first order term in those works turns out to be Eljw - will. we improved it to will- Such seemingly insignificant improvement has important ramifications for
El 0xx, As]
7

---

our analysis as explained later in the paper. The second order term in
22
can be expanded as,
2
E
Wk 11
-
E ws
wfll
K
K
K
k=
k=0
(0)
2
K-
K
E|
Bi|wx - wfll
VoJL, As)1
(23)
K
1 K
(6)
2
K
2G (1 + Xmax)) 12 71)
Bl|wa will +
K
k=0
where (a) utilises W - (0())) (o....)) Aτ) and Assumption The second inequality applies
Lemma together with the fact that D E Our next subsection provides bound on Eljux - w 1| and the first order term El [(wx: As] will Il-
4.2 Local Convergence of the Natural Policy Gradient
To deliver the promised bounds, we first provide some characterization of the gradient estimate.
Lemma 4. Let VuLuzo (w, 0, X) be the estimate produced by Algorithmm
Under assumptions and
the following semidefinite inequality holds for any and
V Lup (wg 0, 20 T. ( 0, 2)] 3 oF
where woxx (0) are given by and respectively and 0² is defined below.
1
2G
32 (1 Amax)
(24)
7)a
2 PF
The term o² defined in Lemma 4 can be described as the scaled variance of the gradient estimate, V (w, A). Note that if the estimates were non-stochastic (i.e., deterministic), we would have x² = O since Vu (wž,)- 0, A) = 0. The last equation can be proved using the definition of w given in (9) the gradient expression provided in (TO), and observing that the Fisher matrix, (0) is invertible due to Assumption 4 The above information crucial in bounding the first-order error, as stated in the following lemma.
Lemma 5. If afssumptiios and hold, then the following relations are satisfied Vk E {0. (O.
5V with learning rates +3/32a B
oe E
3v5G2 and
1 provided that the inner
9G2.
loop length of Algorithm
obeys H O log oF
(Vage) for some universal constant, C.
ur
E Blw will < 22 o²d
+ O Cexp
(-
20G H1
uF
(1 Amax)² )2 [r 7)4
(25)
1r H
+ Amax
E Wk Oc, An]
will < VC exp
H)
(26)
40G²
Vur(1 7)2
where C denotes a universal constant, wi is given by and o² defined in (24).
The first bound (25) is consequence of Lemma and the ASGD convergence result provided in g (Corollary 2). To gain intuition about the second result (26). note that by taking the conditional ex-
pectation El- O2, Au] on both sides of the ASGD iterations (15) 18). and applying the unbiasedness
of the gradient estimate (Lemma D we obtain the following vh E {0. ... 1}.
Ya = axi, + (1 V)v
R = yn - dv vo
Jop (w, O2 Att
(27)
2/ Byn + (1- 3)
Va+1 = Zn &V
Top (w, 0x. da) w=gn up
8

---

where i, El4A 8g Ax), (v.x,y, z}. Moreover, taking conditional expectation on both sides of we arrive at the following.
the tail averaging process
2
Wk
WR
ON, ARl
Xh
(28)
H
Note that the steps
(8) resemble the iterative updates a deterministic ASGD. This allows us
to obtain E
Wy
wi by substituting o² in 25 and applying the Sauchy-Schwand incquality.
4.3 Global Convergence of the Lagrange
Combining Lemma 3 23 and using the expected gradient errors provided by Lemma 5 we bound the average Lagrange optimality gap as function of tunable parameters and K as stated in the
following corollary.
Corollary 1. Consider the same setup and the choice of parameters described in Lemma 3 following inequality holds if assumptions 2
The
Aare met.
K-1
GVC(L Amax) Vur(1 - 7)
K
E (I,,p(T",, Ax) (1.,p(Ok (E)
S V VEbias
exp
40G²
PF
H
R=0
22o
(- MF H)
[ Amax)² )21
C(1 +
G² + Amax) )2
Bn
Hr
texp
"20G2
pr 7)
11/(1 - 7)
n Bndy
E
(=15)
(29)
Corollary bounds the optimality error of the Lagrange function as O(/ibis cxp (-C + 7
I where Co is some problem specific constant. Interestingly, the dual learning parameter, < does not appear in this bound. However, the next section shows that plays pivotal role in deciding the objective and constraint violation rates.
4.4 Decoupling the Objective and the Constraint Violation Rates
The goal of the following theorem is choose optimal values of the tunable parameters and decouple the objective and constraint violation rates from the Lagrange convergence result given in (29)
Theorem 1. Consider the same setup and the choice of parameters given in Lemma 3 5
Assume
= (1- + Amax)-²/VKK /V/ <= >max - ->//v v K, and Amax 2/((1 Cslater)) For
sufficiently small the following inequalities hold
K
- Smn(Oaa) < / Vehias +
E
K
k=0
(30)
E
Σ k=
-J (0p 5 5 (11-7)calater Ebbis
K
Therefore, the It to be clarified that O(11 - -1) samples -
whenever assumptions 7 are met, = = and K 00(00)))))))
sample complexity to ensure is the (1 -1)--11-1 factor in the sample complexity calculation appears due to the fact that it requires
average to obtain grudient estimate via Algorithm
Theorem I dictates that, with appropriate choice of the parameters, the rate convergence of the objective and that of constraint violation can be bounded as O /Cbias + c) with - -(--)
samples. This beats the SOTA Ó(e-1) sample complexity of 4 and achieves the theoretical lower bound. Our derived sample complexity also dependent on Gstater- However, this not explicitly mentioned in Theorem Interested readers can find such details in the appendix.

---

Remark 3. Note the importance of the nested expectation in the first-order term El E| OR. Au] will in 3 Lemma|5|ouur bounds this term as (eexp(-C,H) where Co is a problem dependent constant. Other terms in the Lagrange optimality bound (Lemma 3) can be expressed as O + , Moreover, following the proof of Theorem 1 one sees that decoupling the objective optimality error and constraint violation bounds incurs additional O + (R lerms. Choosing 1), S as prescribed in Theorem 7 makes both the objective and constraint violation errors Olyicias + cxp(-Cc,H)
). This allows us to take H = (1) and K = O(E leading to ( sample complexity. Had the first-order term been E Eilwy,- willl it would have resulted in (v/Ebiss + H -00.5 + K (.-)))
objective and constraint violation errors which would have lead to O sample complexity.
Conclusions and Limitations
This paper considers the problem of learning a CMDP where the goal is to maximize the objective value function while guaranteeing that the cost value exceeds predefined threshold. We propose an acceleration-bant baase primal-dual natural policy gradient algorithm that ensures e optimality gap and c constraint violation with (c-2) sample complexity. This improves upon the previous state- of-the-art sample complexity of ((e-)) and achieves the theoretical lower bound. Future works include applying the idea of acceleration-based NPG to improve sample complexities other related domains of constrained reinforcement learning, e.g., non-linear CMDP, average reward CMDP, etc.
References
[1] Al-Abbasi, A. O., A. Ghosh, V. Aggarwal. Deeppool: Distributed model-free algorithm for ride- sharing using deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 20(12)44114-47
2019.
[2] Geng, N., T. Lan, et al. A multi-agent reinforcement learning perspective on distributed traffic engincering. In 2020 IEEE 28th International Conference on Network Protocols (ICNP), pages 1-11. IEEE, 2020.
[3] Gonzalez, G., M. Balakuntala, M. Agarwal, et al. Asap: A semi- precise system for telesurgery during communication delays. IEEE Transactions on Medical Robotics and Bionics, 5(1):66-78, 2023.
[4] Bai, Q., A. S. Bedi, V. Aggarwal. Achieving zero constraint violation for constrained reinforce- ment learning via conservative natural policy gradient primal-dual algorithm. In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, pages 6737-6744. 2023.
[5] Ding, D., K. Zhang, T. Basar, M. Jovanovic. Natural policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Information Processing Systems, 33:8378-833 8390, 2020.
[6] Xu, T. Y. Liang, G. Lan. Crpo: A new approach for safe reinforcement learning with con- vergence guarantee. In International Conference on Machine Learning, pages 14980-11491. 2021.
[7] Liu, Y., K. Zhang. T. Basar, W. Yin. An improved analysis of (variance -earience-reuuced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33:7624-7633 7636, 2020.
[8] Jain, P., S. M. Kakade, R. Kidambi, P. Netrapalli, A. Sidford. Accelerating stochastic gradient descent for least squares regression. In Conference On Learning Theory, pages 644- 2018.
[9] Liu, T., R. Zhou, D. Kalathil, P. Kumar, C. Tian. Policy optimization for constrained mdps with provable fast global convergence. arXiv preprint arXiv:21 2021.
[10] Zeng, S., T. T. Doan, J. Romberg. Finite time complexity of online primal-dual natural actor- critic algorithm for constrained markov decision processes. In 2022 IEEE 61 Conference on Decision and Control (CDC), pages 4028-4033. IEEE, 2022.
[1I] Vaswani, S., Yang. C. Szepesvári. Near-optimal sample complexity bounds for constrained mdps. Advances in Neural Information Processing Systems, 35:3110- 10-3122, 2022.
10

---

[12] Agarwal, A., S. M. Kakade, J. D. Lee, G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):44314450 2021.
[13] Bhandari, J., D. Russo. On the linear convergence of policy gradient methods for finite mdps. In International Conference on Artificial Intelligence and Statistics, pages 2386-2394, 2021.
[14] Cen, S., C. Cheng, Y. Chen, Y. Wei, Y. Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, (((4):2563-2578 2022.
[15] Lan, G. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, 198(1))109--1166 2023.
[16] Zhan, W., S. Cen, B. Huang, Chen, J. Lee, Y. Chi. Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence. SIAM Journal on 2023.
Optimization,
[17] Xu, P., F. Gao. Q. Gu. An improved convergence analysis of stochastic variance-reduced policy gradient. In Uncertainty in Artificial Intelligence, pages 541-551. 2020.
[18) Gargiani, M., A. Zanelli, A. Martinelli, T. Summers, J. Lygeros. Page-pg: A simple and loopless variance-reduced policy gradient method with probabilistic gradient estimation. In International Conference on Machine Learning, pages 7223-7240. 2022.
[19] Huang, F., S. Gao, Pei, H. Huang. Momentum-based policy gradient methods. In International 2020.
conference on machine learning, pages
[20] Salehkaleybar, S., M. Khorasani, N. Kiyavash, N. He, P. Thiran. Momentum- policy gradient with second-order information. Transactions on Machine Learning Research, 2024.
[21] Shen, Z., A. Ribeiro, H. Hassani, H. Qian, C. Mi. Hessian aided policy gradient. In International conference machine learning, pages 5729-5733 2019.
[22] Chen, Z., S. Khodadadian, S. T. Maguluri. Finite-sample analysis of off-policy natural actor- critic with linear function approximation. IEEE Control Systems Letters,
2022.
[23] Chen, Z., S. T. Maguluri. Sample complexity of policy-basee methods under off-policy sampling and linear function approximation. In International Conference on Artificial Intelligence and Statistics, pages 11 1195-112111 1214. 2022.
[24] Khodadadian, S., T. T. Doan, J. Romberg, S. T. Maguluri. Finite sample analysis of two-time- scale natural actor-critic algorithm. IEEE Transactions on Automatic Control, 2022.
[25] Fatkhullin, I., A. Barakat, A. Kireeva, N. He. Stochastic policy gradient methods: Improved sample complexity for ssser-non--egeneeree policies. In International Conference on Machine Learning, pages 9827-9869. 2023.
[26] Masiha, S., S. Salehkaleybar, N. He, N. Kiyavash, P. Thiran. Stochastic second-order methods improve best-known sample complexity of SGD for gradient-dominated functions. Advances in Neural Information Processing Systems, 35:10862-
2022.
[27] Mondal, W. U., V. Aggarwal. Improved sample complexity analysis of natural policy gradient algorithm with general parameterization for infinite horizon discounted reward Markov decision processes. In International Conference on Artificial Intelligence and Statistics, pages 3097-3105. 2024.
[28] Efroni, Y. S. Mannor, M. Pirotta. Exploration-exploittiio in constrained mdps. arXiv preprint drXiv:2003.0218% 2020.
[29] Liu, T., R. Zhou, D. Kalathil, P. Kumar, C. Tian. Learning policies with zero bounded constraint violation for constrained mdps. Advances in Neural Information Processing Systems, 34:17183-17193, 2021.
[30] Ding, D., X. Wei, Z. Yang, Z. Wang, M. Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligence and Statistics, pages 3304-3312, 2021.
[31] He, J., D. Zhou, Q. Gu. Nearly minimax optimal reinforcement learning for discounted mdps. Advances in Neural Information Processing Systems, 34:22288-211 -22300, 2021.
11

---

[32] Wei, H., X. Liu, L. Ying. Tripleqq: A model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation. International Conference on Artificial Intelligence and Statistics, pages 2274-3307. 2022.
[33] Bai, Q. A. S. Bedi, M. Agarwal, A. Koppel, V. Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, pages 3682-3689. 2022.
[34] Sutton, R. S., D. McAllester, S. Singh, Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
[35] Zhang. J., Ni, C. Szepesvari, M. Wang. the convergence and sample efficiency of variance-reduced policy gradient method. Advances in Neural Information Processing Systems, 34:2228-22 22400, 2021.
[36] Jin, C.. Z. Yang. Z. Wang, M. Jordan. Provably efficient reinforcement learning with linear functiin approximation. In J. Abernethy, S. Agarwal, eds., Proceedings of Thirty Third Conference on Learning Theory, vol. 125 of Proceedings of Machine Learning Research, pages 2137-2143. PMLR, 2020.
[37] Wang, L.,, Q. Cai, Z. Yang, Z. Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations. 2019.
[38] Zhang, K., A. Koppel, H. Zhu, T. Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 3866)3358--361, 2020.
[39] Mondal, W. U., V. Aggarwal,, S. Ukkusuri. Mean-field control based approximation of multi- agent reinforcement learning in presence of a non-decomposable shared global state. Transac- lions on Machine Learning Research, 2023.
[40] Ding, D., K. Zhang, J. Duan, T. Başar, M. R. Jovanović. Convergence and sample com- plexity of natural policy gradient primal-dual methods for constrained mdps. arXiv preprint arXiv:2206.02:5 2022.
12

---

A Helper Lemma
Lemma 6. With slight abuse of notation, define [L, 2) _ Sr. + AJo.pr holds for any two policies 1 22 and X E A.
The following relation
( A) (T,, A)
E (e,a))u7))
(s.
(31)
1 1-
Proof. This can be proved using Lemma of
12 and the definition of the Lagrange function.
B Proof of Lemma
Proof. Fix arbitrary 0 and x. Note that the following equation holds due to the definition of (0.,
E (0) = (1 (0)==
B -1
(88s ag)
80 P.
j=
= (1 - E
c(S a3)
80 ~ p. TT 2
(32)
t=j
E
y c(s c(s),,a)) a,)
80 ~ p, n
(0)
To prove the unbiasedness of the gradient, first prove that the distribution of the sample pair (s, à)
produced by Algorithm is indeed v0 Observe the following.
Pr($ = =, = mo) = (1 - 7) Σ
PPrrs = 8, = also ~ p. no) = (s,
(33)
Next, show that for given pair (s, as, the estimate
(s, a), (
[r,c) is unbiased.
2g (s.a))00ss = (1-
g 9/ az)
8o 8,00 T,
1=0
(1 - E
Σ
g
7 8, 0u
0,
(34)
t=j
E
79 ai) 8,00 a,
29 (s,
In similar fashion, one can establish that El E me
vo) Vg E fr, c). Combining this
with (3) leads to: E[ATA (s, a)]0, X, s, a]
A (5, a). We arrive at.
E
E ((, re
[o log no (a @ V lo = Fo(0),
(35)
E (0,
( Te
E A ()
0, 8, à
V Volog 0,1
(36)
= =(( re
A (3, Vo log To (a|s)
= (0,
Finally, we arrive at the following by utilizing the definitions
10) and 14
E Woowoogo (w. A) 0,
E [[,00] w E 10,00)
(37)
= F](Ww 1- H, A) = (w, (W
This concludes the proof.
13

---

C Proof of Lemma 3
Proof. Invoking the definition of KL divergence, we arrive at the following series of inequalities.
E B
[KL( (-1ss(( (-1s) [L( (-|s) (+1s))]
#B2+1 (a|s)
log
TTe (a|s)
B
B(s Vo log no, (als) (0k+1 0x)]
2 10x+1 1
Bnp
(s,)) Vo log no, (a|s) wk]
1|wx12
2
Brj²
(),)) (Vo log no. (als) w + n T (.,0)~ (o log Te, (a|s) (wx - whil
2 |
= n Nt) Jr. O0 Aa)] + r (s,") Vo log ma, (als) wil
B1j²
"/Vino(a' Ax) - Jr.p (0s, Ax)] + n (a.a)
Vo log no (a|s) (wi - wit]l 1| 11
(0) n Ax) - (0k, Ax)1 + 17 (s.a)
Vo to, To, (als) w AL,2 (s,
By²²
+ +, (aa) Vo To
To, (als) (wi - wijl
|
2
2
n Ax) - ( (6x, Ax) - V/ E ((ao)nog
Va Volog To, (als) w
A (3.0)
1-
+ 1/ (s,a)a) Volog Toe (als) (wi wfll
||
(4)
2 n|JL,pTT' (x)) JL, Ak)] ///iias
Bnj 2
+ (..))
Vo log na, (a|s) (wx - wf))
(38)
where the step (a) holds by Assumption and step (b) holds by Lemma 6 Step (c) uses the convexity
of the function (xx = x²² Finally, step (d) comes from the Assumption Rearranging the terms and taking expectations on both sides, we have.
E (T As) JL, Ax)] S -E (s,a)=oz E
V log Toz (als) E
WE Ok Au] - w[]]
By
1 Em
+
E
[w
1|2
[E [[ (-1s) (+|=))] E [LL(T (-Is) [H)] + Vébias
"1
[ Ok. Aa] - ww)il + Bn 1|
Cbias
GE
E WN
+
E B
E
(+1s)) - E [KL(TT (-1s) (+1))]]
"
(39)
where (a) follows from Assumption Summing from i: = to K - 1, using the non-negativity of KL divergence and dividing the resulting expression by K. we obtain,
1
K-1
E
[L, Ax) - ( -he)
/ Cbius +
G
K-1
Σ
(E
E
w Ok, Aa]
wflll
K
K
R=
0
km
(40)
Bn 2K
K
+
E
Ellwa 1|
Bandyy [KL( (-1s) (-1s))]
ni
This concludes the proof.
14

---

D Proof of Lemma 4
Proof.
Fix a E O and À E A. Observe the following equation.
VuLy (ub,s: 0, VuLyzo (W),), 0. 2.]
E
2 V log @ V log Tol
E (s,a)ov
E
Ve log ne (a(a)) wā,x 1 A (8,a)
(s,a)
To prove the lemma, it is sufficient to demonstrate that E (a S o², of inequalities stated below.
v(s,a) V(s, Notice the chain
V log (alas) Wa,
I - L.
Tu (s, a)
2 2 Ve (o w6.1
+ (1- E
AE (s,
(0)
4(1 A)2
Ana (s, a) }
$ V log To (o(als)
max gE(r.c)
E
(1 7)2
(
$ 10 VoJl. A)12 + 8(1+ X)2
Qg (s, [s,
Vo }"}
max
E
+ E
(1 7)2
(r:c)
3 21' + 2)
32(1 + x)a
1
2G
+
32
(1 Amax)²
( 7) (1 7)
(1 7)
(41)
Inequality (a) follows from the Gauchy-Schward inequality and the fact that (a+ < 2(a² + 122) for any two numbers a, b. The argument also applied in inequality (b). Additionally. it Assumption 2 and the definition of wā,x Finally, (c) is a consequence of Assumption 4 Lemma 2 and the following two bounds.
2 E 0770 (s, a)] S (1 71 and E
(s) 8
S (1 (1-7) V(s () A (r.c) (42)
To establish the first bound, note that (2 (s, a) is assigned a value of at most (j+1) with probability (1 - ->> Vg E (r.c). Therefore,
E Q as)
(1-
(1+ 2 (1 71 (1 7)
(43)
The second bound in 42 can be proven similarly. This concludes the lemma.
E Proof of Lemma 5
We establish Lemma applying Corollary [8] Note the following statements.
S1 The following quantities exist and are finite 40 e e.
(0) A E, (a.0)
Ve [e(ls) & V log To (a[s)).
(44)
G)) A E (
ze log my (a|s) & Vo lo (als) & Vo log (a(s)) Vo log (als)) (45)
S2: There exists 2² such that the following is obeyed A0 E where w minimizes Ly (. (-, (, A).
E
Vi (wă, 0, A) & I ( 0. & FFFF,(0)
(46)
15

---

S3 There exists μF, G > 0 such that the following statements hold 44 E O
(a) (0) Msla,
(47)
(b) E (s
[ log mo (a (als) log mo(als) & Vo log x GP))((),
(48)
G²
(c) B (s.a))07
Vo log xo ()))) (o)+ Vo mo & Vo log (
& F2(0)
(49)
PF
Statement S1 follows from Assumption 2 whereas S2 a consequence of Lemma 4 Statement
(3()) is identical to Assumption 4 S3(6) results from Assumption 2 and finally, S3(e) follows
from Assumption 2 and 4 can, therefore, apply Corollary of [8] with K
G up and
deduce the following convergence result whenever > CV KR log( (Vdy/v/ii RR) and the learning rates
set
3v5v/K
B 9VER* 3VouEVER and 3G
143/5KR
C
o²d
E [[([w))] 1e(WW) - exp 20VKR
[2x(0) (wxt) + 11
H
(50)
where La (w) A no (w, On. As), Vi E _2d
The term, C' is universal constant. Note that 4 (w(f) 2 and (e( bounded above as follows.
2 (a) (1 Amax) )²
4.(0)
E
A moe (s.
(51)
2 (s,a)~up
2(1 - 7)
where (a) is a result of the fact that [AL. (s, a)) I (1 + Amax) - 7), v(s, E x A. 40 E O, and AY A. Combining (50). (5I), and the fact that (.) is pe- convex, we establish,
E Bllwx w v
2
E [w()) [e(wR]] 22 o²d
Cexp (-
MP
H
(1 + Amax )2 |F
PF
Hp
20G
7)
(52)
This proves the first statement. We get the following for noiseless
(o 0) gradient updates.
E (E 0n] w1 < Ceep
(-
20C
HF
(1 + Amax) )
(53)
|F 7)
The second statement can be established from (53 by applying Jensen's inequality on the function f=) 2
F Proof of Theorem 1
Applying the inequalities H 2 1, (HF/20 I 1 and substituting the values of o² and (as stated in Lemma and Theorem respectively) we can rewrite (2) as follows.
K-
E ( ,,)) (L,p(0k Ax)
K
k=
0
(54)
(1 Amax)
cxp (-
Pr H + f1
(1 >max)
1 CCias + fo
(1 7)2
400=
(1 7)2
VK
The terms So and fi are defined below.
GVC
fo A
VIF
(55)
44d
4
C
G pp
f 2
B
16
+
+
Eandy (K((=((-ss) To, (-1s))
PF
PF
Using the definition of Jr,pp (. ,), one can write,
JL, Ax)) JL Ax) - (r,((0a)) + >ooFET (e,)(0k))
(56)
(0)
2
- (0x) + (x(=-o,.(00)) -
16

---

where (a) follows from the fact that AA 2 0 we obtain the following.
and J 2 0 due to feasibility. Combining 54 and 56
K
K 1
Jr (0a)
+
(x
K
K
k=0
(57)
$ /bils + So (1 Amaxx)
exp (- 400 H) + 11 (1 + Amax) 1
(1 7)2
71-
K
F1
Convergence Rate of the Objective Function
Note that 57
can be alternatively written as,
(0 S Vebias + fo
(1 + Xmax)
exp (-
PF
11)
K k=0
- (1-7)2
400G
(58)
+ fi (1 + Amax) (1 7)2
K
+
Σ
(x
VK
K
k=
To obtain the convergence rate the objective functiin, we need to bound the last term in the above expression. Observe the following chain of inequalities.
0 ((R) (Ak+1)2-(AAp) (2xe²)
(59)
(8)
K
K K-1
K-1
(Ax (Jcc((1))) - -Mx))) = -2
Σ
(0k) + c2²
Σ ja
(0)
k=0
k=0
k=0
where (a) uses Ào 0 and (b) follows from the contraction property of the projection operator, PA Using the above inequality, one can write,
K
C
K 1
Av. (0k)
Σ
p2
(0k)
(60)
K
2K
K=
k=0
Using the unbiasedness of (0k) (Lemmal 1p. we deduce the following.
A (0x)
As (0)p
E
AuJa,
(61)
where (a) is a consequence of the fact that (Ox) and d are conditionally independent given Oz.
Note that, _e_,p(pp (0x) is assigned value of at most (j + 1)a with probability (1 (1-7)?', E {0, 1..... Therefore, the RHS of (60) can be bounded follows.
E j2 (0x)
<
(1
7) + +1
1+7
2
(62)
(1 (1-7)²
[I 7)²
0
Combining
58
60
61
and
62
we finally obtain.
E
J (0k)
K
k=0
(1 + )max)
MF 40G2
(1 + Amax)
S
Vebias
+ ʃo
exp
fi
(1 - 72
(1 - 7)2 VK
(1 - 7)2
(63)
(1 + \mmxx
|F
(1 + Amax)
Amax
Cbbias + fo
(1 - 7)2
exp
40G2
H
+ f1
(1 - 7)2
VK
(1 7) VK
5 Ebias + fo (1-7) 7)2
(1 + Amax)
exp
PF
11
(fi + 1)
11 )mnax
4062
- 7)3 vK K
where (a) uses the substitution
Amax
17

---

F.2 Rate of Constraint Violation
The following inequality is satisfied for any lo E {0,1,... -K-K1 13.
AR+1 Amax| 12 (PA (Je, Amax 1
(64)
A (Ok)) )max 2== Axx Amax / (0x) )max) + (2
where (a) is due to the contractive property of PA. Performing an average over k E {0, K - 1}. and applying expectations both sides, get,
K
(Ax - Amax) (o,
(a)
Amax 12
1AK 2çK
Amax
C
K-1
E
j2 (epp(0a)
2K
k=0
(65)
x max
5
(c)
3 3Amax
K
7)2
2(1
7)
VK
where (a) utilises Ào = 0. (b) applies (62) and (c) is derived using C - Amax (1 - /////////// Note that
one can write the following using Lemma 1 and the observation that Je.p (4x) and d are conditionally independent given fg.
(Ax Amax) (0n) = [Av Amax ) (0.)(0=](0x]] = (Ar - Amax)Ja (66)
Combining (65) and (66), we get,
1
K-
3 3Amax
2(1 + Amax)
E
(Ax
Amax (0x)
5
2(1 - 7) KK S
(67)
K
(1 /K
0=0
Finally, combining
(58)
and 67
we arrive at,
E
J
(0k)
Amax K
E
(0x)
K
k=0
(68)
(1 )mnax)
(- (_p H) (fr 2)
He
(1 Amax)
S Vebias + fo
exp
(1 7)2
(1 (1-7) 7)2 VK
Since the functions (Ox)) 9 (r,c), k (0...., K 1} linear in occupancy measure, there exists policy स such that the following holds Vy E (r,c).
(g.p(
-g.p
K
This allows to rewrite (68) as,
J E[J Amax E [ Jē.p]
Vebins +
(1 Amax)
(1 71-
exp
-00G2
HF
H
(69)
(1 + >max) 1
+ (f1 +2) 2)
(1 71- VK
Applying Lemma and verifying (via Lemma 8 that Amax 2 2X where X is the non-negative minimizer of the dual function corresponding to the unparameterized constrained optimization (2). we can write the constraint violation rate as follows.
1
K
E -
(c,))
2/hbias Amax
+ 2fo
Xmax (1 7)2 exp (-
(1 )max)
-0000 H
HF
K
k=
(70)
+ 2(f + 2) (1 + dmax)
X (1 7)2 VK
18

---

F.3 Final Result
Substituting Amax 2/[(1 Golater) 2 2 in 63 we get the rate of convergence of the objective
as follows.
E
J - Jr (8a)
K
k=0
(71)
S Vebis +
3 exp
(-
40G² H) +
MF
3(11 1)
(1 71-
(1 - 1-7)3
V
Similarly, we obtain the constraint violation rate as,
Σ E (0,)
(72)
350
PF
3(f1 +2 1
S Csstter v Cbias +
cxp
H
+
(1
7)
4002
(1 - 7)2 VK
Let, H and K are chosen as follows for an arbitrary e
H 40G²
6foc e-
6fo
})
log
max
(1 - 7)3 (1 71-
-Oloo((c
μF
(73)
36( + Calater
- 36 36 +22
K = max
2 (1 7)-
= (7) (E-2)
(1 71
For the above choice of H and K, we have,
1
E
Jr. - (1k) Vehins + 6,
K
k=0
(74)
K-1
Σ
(Os)
5 - 7s)Cstae v Ebbis +
K
k=0
Note that the expected number steps required in Algorithm (((100(11))))))))))))
- () Therefore, the sample complexity required to ensure (74) is ((11(1))))))) HK)= (1)1)))))_)) Finally, note that Lemma requires H G log (vac*) This can be ensured if is sufficiently small. pr
pe
G
Strong Duality and Related Lemmas
Define the dual function associated with the unparameterized constrained optimization 2 as follows.
BD,- max {J + XJ
(75)
The following lemma formally describes the strong duality result.
Lemma 7. (40) [Lemma 3] Xf arg min and x is solution of 2 then the following holds whenever Assumption iis true.
J J r.p
(76)
is be mentioned that strong duality, in general, does not hold for the parameterized optimization 33. The following lemma established a bound on X which becomes the foundation for choosing the value of Amax in Algorithm 2
Lemma 8. Lemma 3] Let X* be the optimal dual variable defined in Lemma 7 The following inequalities hold where Calater is defined in Assumption 7
S X <
(1 7
19

---

The following lemma is the main tool in decoupling the objective and constraint violation rates.
Lemma 9. Let Slater's condition (Assumption) 7 hold. IfC 2 2 where X is defined in Lemmal and it is policy such that J JT.p + C..pl..l S for some Ç > 0 then
2 c.p S C
(77)
Proof. Define the function v--) as follows.
((r) max J Jē,p 2T), TE Rd
(78)
Let J2pp Therefore, one can write the following chain of inequalities.
(a) Jr S u(T) = max (Jr Jep 2 m} max { + + -T) 2r}
max { x JT, J
c.pl cp 27 TX
(79)
(e) JT. TX (d)
r.P TX
where (a) follows from the definition of u(T), (b) uses X N 0. (c) follows from the definition of the
dual function, and (d) is a result of the strong duality (Lemmal 7 Utilizing (79), we get,
(C - (C-)))(-T) Jr Jr, C(-r)
(80)
This leads -T -/
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction clearly state the paper's contribution and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Some limitations of the paper have been discussed in the conclusion sec- tion. Moreover, some assumptions are also accompanied by elaborate discussion on their limitations.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-specifiaatinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
21

---

Answer: [Yes]
Justification: We have clearly stated the required assumptions and an accompanying com- plete proof in the appendix for each theory result.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: Our paper is primarily of theoretical nature and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
22

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
Our paper is primarily of theoretical nature and does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /tte://uuuddeeooooSuuubmmiibia ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our paper is primarily of theoretical nature and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our paper is primarily of theoretical nature and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
23

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our paper is primarily of theoretical nature and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:: atttps:/nneurps..com http::/ppwppppppcaccccccccccaaaa
Answer: [Yes]
Justification: Our research conforms, in every respect, to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is primarily of theoretical nature and has no immediate societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No high risk data or model have been used.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: No existing asset has been used in the paper.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
25

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No new asset is introduced in the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No experiments with human subjects were conducted.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We conducted no experiments with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "p9mBrZjmjf", "reviewer": "Reviewer_jftD", "summary": "The paper studies the sample complexity of the constrained Markov Decision Process (CMDP), and derives an algorithm that attains the $O(\\epsilon^{-3})$ that improves the SOTA sample complexity bound for CMDP by a factor of $O(\\epsilon^{-1})$.", "questions": "As mentioned, the major weakness of the paper is that you have overlooked the sample complexity bound's dependency in $\\gamma$ and it seems you have a worse constraint violation result. Can you update Table 1 with sample complexity bounds having dependency in $\\gamma$ and with constraint violations? More importantly, can you justify why your result has seemingly worse dependency in $\\gamma$ and constraint violations?", "limitations": "The major limitation of the paper is the lack of proper comparison of the sample complexity bounds with prior works.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "CMDP with general parameterization is a very challenging problem, and thus there have not been many papers making progress in this challenging setting compared to the tabular CMDP setting. The authors modify the classic primal-dual natural policy gradient (NPG) framework by leveraging an accelerated stochastic gradient descent (ASGD) method to improve the SOTA sample complexity bound by a factor of $O(\\epsilon^{-1})$.", "weaknesses": "Even though the authors claim they have improved the SOTA sample complexity bound for CMDP with general parameterization, I still think it is hard to say the authors have \"beat\" the previous results. $\\epsilon$ is not the only factor that matters for the sample complexity bound for discounted infinite-horizon MDPs, since $\\gamma$ is also another significant factor. Unfortunately, it seems that the authors' bound has a dependency of $O(1/(1-\\gamma)^{-8})$, so that makes the sample complexity bound read $O(1/(1-\\gamma)^8\\epsilon^3)$. Compared to a prior work [1] which has a sample complexity bound of $O(1/(1-\\gamma)^6\\epsilon^4)$, it is clear the two bounds are not necessarily comparable due to one bound is superior in terms of the order of $\\epsilon$ and the other superior in terms of the order of $\\gamma$. \n\nAlso, [1]'s algorithm has zero constraint violation while the authors' algorithm permits $O(\\epsilon)$ constraint violation, which is a worse result.\n\nHence, unless the authors can clarify their result has improvement in $\\epsilon$ and $\\gamma$ and constraint violations (or at least provide stronger justifications that their algorithm requires a smaller number of samples to achieve near-optimality), it is hard to evaluate the value of the authors' result.\n\n[1] Bai, Qinbo, Amrit Singh Bedi, and Vaneet Aggarwal. \"Achieving zero constraint violation for constrained reinforcement learning via conservative natural policy gradient primal-dual algorithm.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 6. 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Fairer Comparison of Sample Complexities:** We would like to point out that the sample complexity of $\\tilde{\\mathcal{O}}((1-\\gamma)^{-6}\\epsilon^{-4})$ reported by [1] in their AAAI version is erroneous. The authors have subsequently corrected their result and the sample complexity has been modified to $\\tilde{\\mathcal{O}}((1-\\gamma)^{-8}\\epsilon^{-4})$ in the arXiv version  (updated May 2024). Please see Table 1 in [2] to verify our claim. Therefore, in comparison to the state-of-the-art (SOTA), we improve the sample complexity in terms of the optimality gap $\\epsilon$ without sacrificing the powers of $(1-\\gamma)$. We also note from Table 1 in [2] that other existing results on general parameterized CMDPs are worse than our result both in terms of $\\epsilon$ and $(1-\\gamma)$. Following the reviewer's suggestion, we will revise the comparison table in our manuscript to exhibit the dependence of the sample complexity on both $\\epsilon$ and $(1-\\gamma)$. The updated table is provided below for a quick reference.\n\n|   Algorithm  |   Sample Complexity  | Parameterization  |\n| :------------: | :-----------------------: | :-------------------: |\n| PMD-PD [6] |  $\\mathcal{O}(\\epsilon^{-3})$ | Softmax |\n| PD-NAC [7] | $\\mathcal{O}(\\epsilon^{-6})$  | softmax |\n| NPG-PD [5] | $\\mathcal{O}((1-\\gamma)^{-5}\\epsilon^{-2})$ | Softmax |\n| CRPO [4] | $\\mathcal{O}((1-\\gamma)^{-7}\\epsilon^{-4})$ | Softmax |\n| NPD-PG [5] | $\\mathcal{O}((1-\\gamma)^{-8}\\epsilon^{-6})$ | General |\n| CRPO [4] | $\\mathcal{O}((1-\\gamma)^{-13}\\epsilon^{-6})$ | General |\n| C-NPG-PDA [2] | $\\tilde{\\mathcal{O}}((1-\\gamma)^{-8}\\epsilon^{-4})$ | General|\n| **PD-ANPG (This Work)** | $\\tilde{\\mathcal{O}}((1-\\gamma)^{-8}\\epsilon^{-3})$ | General |\n| Lower Bound [8] | $\\Omega((1-\\gamma)^{-5}\\epsilon^{-2})$ | $-$ |\n\nThe dependence of the sample complexities of PMD-PD and PD-NAC on $\\gamma$ is not depicted in the papers.\n\n**Zero Constraint Violation:** Transforming an $\\epsilon$ constraint violation (CV) result to a zero CV result is a relatively straightforward exercise that is routinely employed in the literature. The main idea is to choose a slightly modified cost function $c'=c-(1-\\gamma)\\delta$ and demonstrate an $\\epsilon$ CV result for $c'$. This can be done by following the same procedure stated in our paper that is used for producing a similar result for $c$. Observe that $J^{\\pi}_{c'}=J^{\\pi}_c-\\delta$ for any policy $\\pi$. Therefore, choosing an appropriate value of $\\delta$, one can prove that the obtained $\\epsilon$ CV result for $c'$ implies a zero CV result for $c$. Application of this \"conservative constraint\" technique is abundant in the CMDP literature, e.g., see [1], [3]. In the revised manuscript, we will provide an outline explaining how to derive the zero CV result.\n\n**References:**\n\n[1] Bai, Qinbo, Amrit Singh Bedi, and Vaneet Aggarwal. \"Achieving zero constraint violation for constrained reinforcement learning via conservative natural policy gradient primal-dual algorithm.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 6. 2023.\n\n[2] https://arxiv.org/pdf/2206.05850\n\n[3] Ding, D., Wei, C.Y., Zhang, K. and Ribeiro, A., 2024. Last-iterate convergent policy gradient primal-dual methods for constrained MDPs. Advances in Neural Information Processing Systems, 36.\n\n[4] Xu, T., Liang, Y. and Lan, G., 2021, July. CRPO: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning (pp. 11480-11491). PMLR.\n\n[5] Ding, D., Zhang, K., Basar, T. and Jovanovic, M., 2020. Natural policy gradient primal-dual method for constrained Markov decision processes. Advances in Neural Information Processing Systems, 33, pp.8378-8390.\n\n[6] Liu, T., Zhou, R., Kalathil, D., Kumar, P.R. and Tian, C., 2021. Policy optimization for constrained MDPs with provable fast global convergence. arXiv preprint arXiv:2111.00552.\n\n[7] Zeng, S., Doan, T.T. and Romberg, J., 2022, December. Finite-time complexity of online primal-dual natural actor-critic algorithm for constrained Markov decision processes. In 2022 IEEE 61st Conference on Decision and Control (CDC) (pp. 4028-4033). IEEE.\n\n[8] Vaswani, S., Yang, L. and Szepesvári, C., 2022. Near-optimal sample complexity bounds for constrained MDPs. Advances in Neural Information Processing Systems, 35, pp.3110-3122.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uBpz1f4GPJ", "reviewer": "Reviewer_c2f7", "summary": "This paper studied the sample complexity of learning a discounted-reward MDP with a discounted cost constraint under a general policy parameterization. \nIt proposes a policy-gradient-type of algorithm that combines natural policy gradient and an accelerating stochastic gradient descent algorithm proposed in [6]. \n\nThen the paper proves that with $O(1/\\epsilon^3)$ samples, the policy learned by this algorithm violates the constraint by at most $\\epsilon$, and is optimal up to $\\epsilon_{bias} + \\epsilon$ error, where $\\epsilon_{bias}$ is a constant coming from policy parameterization. \n\nThe sample complexity of this policy improves upon the prior SOTA, which was $O(1/\\epsilon^4)$.", "questions": "1 I believe the definition of L in (9) has a typo: the square should be inside the expectation, rather than outside the expectation, so that its gradient with respect to w is given by (10). \nDoes this typo affect the proof? \n\n2 The logic from (75) to (76) is not very clear. How did you get rid of the first term on LHS of (76), and where does $\\lambda^*$ comes from?", "limitations": "There is no negative social impact. A discussion of limitation is included in the submission.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written. The main contribution, the algorithm, the key idea of the proof and the proof structure are clearly presented. \n\nThe improvement of sample complexity from $O(1/\\epsilon^4)$ to $O(1/\\epsilon^3)$ is non-trivial, following from a clever observation given in lemma 3. \n\nThe analysis looks solid, though I do have questions about a few minor details, see the questions 1 and 2 below.", "weaknesses": "1\nThe “sample efficient” in the title seems to overclaim the contribution of the paper, since there is still an order gap between the sample complexity of the algorithm in this paper, $O(\\epsilon^{-3})$, and the lower bound, $O(\\epsilon^{-2})$. \n\n2\nIt is not entirely accurate to say that the algorithm achieves “$\\epsilon$ global optimality gap” and “$\\epsilon$ constraint violation”, as the actual bounds in Theorem 1 contain constant terms involving $\\epsilon_{bias}$. \nAlthough $\\epsilon_{bias}$ is common in the analysis of RL algorithms with general parameterizations, it is crucial to discuss whether they are tight and optimal, how they compare to the prior work, and whether they are truly negligible when the policy is parameterized by a neural net of a reasonable scale. \nAt the very least, the sense in which your policy is epsilon-optimal should be clarified in a prominent part of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Weakness 1:** The term \"sample-efficient\" simply acknowledges the fact that the sample complexity of our algorithm is better than that of all existing algorithms in the general parameterized CMDP setup. Note that we refrain from using the term \"sample optimal\" since there is still a gap between our bound $\\mathcal{O}(\\epsilon^{-3})$ and the theoretical lower bound of $\\Omega(\\epsilon^{-2})$.\n\n**Response to Weakness 2:** Thank you for mentioning the inappropriate use of the phrases \"$\\epsilon$ optimality gap\" and \"$\\epsilon$ constraint violation\". In the revised paper, we will change these phrases to emphasize the presence of the $\\epsilon_{\\mathrm{bias}}$ term. Moreover, we will also discuss the precise meaning of optimality in the introduction of our paper.\n\n**Response to Question 1:** We apologize for the confusion. The notation $\\mathbf{E}[\\cdot]^2$ in (9) was intended to denote $\\mathbf{E}[(\\cdot)^2]$. We will add additional parentheses in the revised manuscript to make the notation unambiguous. \n\n**Response to Question 2:** The equations $(75)-(76)$ use the fact that the average of the occupancy measures is still an occupancy measure. Therefore, the average of the occupancy measures corresponding to the policies $\\\\{\\pi_{\\theta_k}\\\\}\\_{k=1}^K$ would be an occupancy measure corresponding to some policy, say $\\bar{\\pi}$. Since the value function $J_g^{\\pi}$ can be written as a linear function of the occupancy measure corresponding to the policy $\\pi$, the transition from $(75)$ to $(76)$ is immediate. Moreover, the optimal dual variable $\\lambda^*$ comes into the picture due to the use of Lemma 10. We shall expand these arguments in the revised manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9bf6jInpSQ", "reviewer": "Reviewer_rE2r", "summary": "The paper considers the constrained MDP setting. Given a target error of $\\epsilon > 0$, the paper provides a primal-dual algorithm on that will return an epsilon optimal policy making at most epsilon constraint violations.  The claim is that the algorithm solves such problem with O($\\epsilon^{-3}$) sample complexity.", "questions": "Your result stated in Lemma 6 is based on a previous result provided by [6]. In [6], the result relies on an oracle that, when given an input, provides a noisy unbiased gradient of a function. However, your algorithm uses a sampling procedure to obtain a gradient estimate, which appears to rely on access to a generative model (Kakade (2003) On the sample complexity of reinforcement learning). Are you considering the setting of having access to a generative model, or are you assuming access to an oracle as in [6], for which your Lemma 6 is based? If you are considering the setting of having access to a generative model, the paper should address the statistical challenges associated with sampling, and the sample complexity should include the number of queries to a simulator, incorporating $T$ into the sample complexity. Therefore, the result from [6] in Lemma 6 does not immediately apply. If you are considering the setting of having access to an oracle, it is not clear why Algorithm 1 is necessary.", "limitations": "By stating the Slater's constant in the sample complexity, the sample complexity is in the order of epsilon to the minus 6 instead of minus 3 so to be independent of the Slater's constant.  See comments in the Weaknesses section.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The idea of incorporating momentum acceleration to a primal-dual algorithm seems interesting.", "weaknesses": "The Slater's constant $c_{slater}$ is missing from the big O-notations in your $H$ and $K$ terms.  The slater's constant is an unique quantity in CMDP and should be clearly stated in your sample complexity.  In the relaxed-feasibility problem, where the algorithm returns a policy that is allowed to have some small constraint violation (such as epsilon constraint violation), the Slater's constant can be smaller than the target error epsilon.  In this case, the Slater's constant can be set to be the $\\epsilon$.  Your paper is in this relaxed-feasibility setting.  \n\nBy writing the Slater's constant $c_{slater}$ explicitly in the big O-notations, we see that $H = \\mathcal{O}((1-\\gamma)^{-3} \\epsilon^{-1} c_{slater}^{-1})$ and $K = \\mathcal{O}((1-\\gamma)^{-4} \\epsilon^{-2} c_{slater}^{-2})$. If the Slater's constant = epsilon, then we see that $H \\propto \\epsilon^{-2}$ and $K \\propto \\epsilon^{-4}$ making the total sample complexity to be proportional to $\\epsilon^{-6}$. Then, the result is independent of the Slater's constant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**On Slater's Constant:** We would like to clarify that, for a given problem instance, Slater's constant is fixed and outside of the control of the learner. On the other hand, the target optimality error $\\epsilon$ can be chosen by the learner to be arbitrarily small. Therefore, it would be inappropriate to assign $c_{\\mathrm{slater}}=\\mathcal{O}(\\epsilon)$. Note that, in all previous works on CMDPs, $c_{\\mathrm{slater}}$ is treated as a constant, rather than a function of $\\epsilon$, e.g., see [1], [2].\n\n**On Query Complexity of the Simulator:** Our algorithm does not assume access to a gradient oracle. Rather, we assume access to a generative model that yields a sample of the next state $s'$ given the current state-action pair $(s, a)$ following $s'\\sim P(s, a)$. We use this generator to obtain an unbiased sample of the gradient via Algorithm 1. It is easy to check that the expected number of queries to the generator to generate one gradient sample is $T=\\mathcal{O}((1-\\gamma)^{-1})$. We do account for this factor in computing the overall sample complexity of our algorithm. In particular, note that the lengths of inner and outer loops in Algorithm 2 are $H = \\mathcal{O}((1-\\gamma)^{-3}\\epsilon^{-1})$ and $K=\\mathcal{O}((1-\\gamma)^{-4}\\epsilon^{-2})$ respectively, which leads to an overall sample complexity of $\\mathcal{O}(THK) = \\mathcal{O}((1-\\gamma)^{-8}\\epsilon^{-3})$. We shall elaborate on the impact of $T$ on the sample complexity in the revised manuscript.\n\n**References:**\n\n[1] Bai, Qinbo, Amrit Singh Bedi, and Vaneet Aggarwal. \"Achieving zero constraint violation for constrained reinforcement learning via conservative natural policy gradient primal-dual algorithm.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 6. 2023.\n\n[2] Ding, D., Zhang, K., Basar, T. and Jovanovic, M., 2020. Natural policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Information Processing Systems, 33, pp.8378-8390.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "byy5qnru9H", "reviewer": "Reviewer_NWcj", "summary": "The paper studies constrained Markov decision processes. Using momentum acceleration, the paper develops a primal-dual natural policy gradient-based algorithm and shows that it achieves an \\epsilon global optimality with O(\\epsilon^-3) samples. The policy class considered in the paper is the generic Fisher non-degenerate policies.", "questions": "* I hope the author could discuss the concern I raised in the weakness section.\n* Since the paper actually studies Fisher non-degenerate policies, I think a more common (and precise) way is to directly use the name \"Fisher non-degenerate policies\". Using the name \"general parameterization\" is a little bit misleading.", "limitations": "The author has discussed the limitation of the paper briefly in the conclusion section.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The paper is the first in the literature that derives the O(\\epsilon^-3) sample complexity for constrained MDP under more general policy parameterizations than the softmax.\n* The presentation of theoretical results are clear and easy to follow. I appreciate that the author presents a complete flow of proof in the main body of the paper.", "weaknesses": "I mainly have the following concern, and if it can be addressed, then I am willing to adjust my rating. In literature [25], a sample complexity of O(\\epsilon^-2) is derived for unconstrained MDP. To me, it seems it is not impossible to translate this result to the constrained setting by adding a primal-dual component, and if this can be done, I think the sample complexity should be O(\\epsilon^-3) or so. I wonder could the author discuss the feasibility of this generalization (and perhaps the underlying challenges if it is not generalizable).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**On the Generalizability of [25]:** The approach explored in [25] does not generalize to CMDPs. To understand the reasoning, note that one of the preliminary steps in [25] is showing a descent-like inequality. For example, Lemma 6 in [25] reads as follows. \n\\begin{align}\n    \\delta\\_{t+1} \\leq (1-\\kappa \\gamma_t)\\delta_t +R_t, ~~R_t=\\mathcal{O}\\left(\\gamma_t\\mathbf{E}\\left[\\Vert e_t\\Vert\\right]+ \\gamma_t^2 + \\sqrt{\\epsilon\\_{\\mathrm{bias}}}\\gamma_t\\right)  \n\\end{align}\nwhere $\\delta_t = J^*- J(\\theta_t)$ is the optimality gap, $e_t$ is the difference between the gradient estimate and its actual value, $\\gamma_t$ is a time-dependent learning rate, and $\\kappa<1$ is some problem-dependent constant. Next, using recursion, and an appropriate choice of $\\gamma_t$, the following result is derived (Lemma 12 in [25]).\n\\begin{align}\n    \\delta_T \\leq \\mathcal{O}\\left(\\frac{\\delta_0}{(T+1)^2}\\right)+ \\dfrac{\\sum_{t=0}^{T-1}R_t(t+2)^2}{(T+1)^2}\n\\end{align}\n\nThe authors of [25] could prove the convergence of $\\delta_T$ up to a factor of $\\sqrt{\\epsilon_{\\mathrm{bias}}}$ precisely because each term in $R_t$ is accompanied by $\\gamma_t$ which is chosen to decrease sufficiently fast with $t$. Following Lemma 6 of [25], we can prove the following bound for a primal-dual algorithm.\n\\begin{align}\n    \\bar{\\delta}^{L}\\_t \\leq (1-k\\gamma_t)\\delta_t^L + R_t^L\n\\end{align}\nwhere $\\gamma_t$ is the time-dependent primal rate, $\\delta_t^L = J_r^* - J_{\\mathrm{L}}(\\theta_t, \\lambda_t)$ is the Lagrange optimality gap, $R_t^L$ has a dependence on $\\gamma_t$ that is similar to that of $R_t$, and $\\bar{\\delta}\\_t^L = J_r^* - J_{\\mathrm{L}}(\\theta_{t+1}, \\lambda_t)$. To obtain a recursion on $\\delta_t^L$, one can use the following.\n\\begin{align}\n    \\delta_{t+1}^L - \\bar{\\delta}\\_t^L = J_{\\mathrm{L}}(\\theta_{t+1}, \\lambda_t) - J_{\\mathrm{L}}(\\theta_{t+1}, \\lambda_{t+1}) = (\\lambda_t - \\lambda\\_{t+1})J_c(\\theta\\_{t+1}) = \\mathcal{O}(\\zeta_t)\n\\end{align}\nwhere $\\zeta_t$ is the time-dependent dual learning rate. Combining the above two results, we have the following recursion.\n\\begin{align}\n    \\delta_{t+1}^{L} \\leq (1-k\\gamma_t)\\delta_t^{L} + R_t^L + \\mathcal{O}(\\zeta_t)\n\\end{align}\n\nNote that, unlike $R_t^L$, $\\zeta_t$ has no dependence on $\\gamma_t$. Thus, to establish convergence via recursion, one must choose $\\zeta_t$ to decrease faster than $\\mathcal{O}(t^{-1})$. On the other hand, the process of decomposing the optimality gap and constraint violation rates from the Lagrange convergence introduces a term of the form $\\mathcal{O}(1/(t\\zeta_t))$ (see the proof of Theorem 1 in our paper) which requires $\\zeta_t$ to decrease slower than $\\mathcal{O}(t^{-1})$ to obtain meaningful results. Therefore, any choice of $\\zeta_t$ will either disrupt the convergence of the Lagrange function or blow up the constraint violation rates. This negates the possibility of generalizing the approach of [25] to CMDPs via primal-dual algorithms.\n\n**On Fisher Degenerate Policies:** Thank you for this comment. We will modify the terminology in the revised paper accordingly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces a novel algorithm called Primal-Dual Accelerated Natural Policy Gradient (PD-ANPG) for Constrained Markov Decision Processes (CMDPs). The algorithm achieves state-of-the-art results in terms of sample complexity, proving that it can reach an $\epsilon$ global optimality gap and $\epsilon$ constraint violation with $O(\epsilon^{-3})$ samples.


Four reviewers reviewed the paper, unanimously agreeing to accept it. They acknowledged the algorithm's innovation and effectiveness, particularly highlighting its improvements in sample complexity. However, some concerns were raised, including the sample complexity's dependency and the need for more detailed comparisons with previous work.


Overall, the paper presents a promising algorithm that makes progress in sample complexity for CMDPs. However, the authors need to further clarify some details and provide more comprehensive comparisons with existing works.
Decision: Accept (poster)