Near-Optimal Sample Complexity Bounds for Constrained MDPs
Authors: Sharan Vaswani
Lin Yang
Csaba Szepesvari
Venue: NeurIPS 2022 Accept (2022)
Keywords: Constrained Markov Decision Processes
Sample complexity
Generative model
Model-based RL
Primal-dual algorithm

Abstract: In contrast to the advances in characterizing the sample complexity for solving Markov decision processes (MDPs), the optimal statistical complexity for solving constrained MDPs (CMDPs) remains unknown. We resolve this question by providing minimax upper and lower bounds on the sample complexity for learning near-optimal policies in a discounted CMDP with access to a generative model (simulator). In particular, we design a model-based algorithm that addresses two settings: (i) relaxed feasibility,  where small constraint violations are allowed, and (ii) strict feasibility, where the output policy is required to satisfy the constraint. For (i), we prove that our algorithm returns an $\epsilon$-optimal policy with probability $1 - \delta$, by making  $\tilde{O}\left(\frac{S A \log(1/\delta)}{(1 - \gamma)^3 \epsilon^2}\right)$ queries to the generative model, thus matching the sample-complexity for unconstrained MDPs. For (ii), we show that the algorithm's sample complexity is upper-bounded by $\tilde{O} \left(\frac{S A \, \log(1/\delta)}{(1 - \gamma)^5 \, \epsilon^2 \zeta^2} \right)$ where $\zeta$ is the problem-dependent Slater constant that characterizes the size of the feasible region. Finally, we prove a matching lower-bound for the strict feasibility setting, thus obtaining the first near minimax optimal bounds for discounted CMDPs. Our results show that learning CMDPs is as easy as MDPs when small constraint violations are allowed, but inherently more difficult when we demand zero constraint violation. 

Near-Optimal Sample Complexity Bounds for Constrained MDPs
Sharan Vaswani* Simon Fraser University vaswani shar and gmail. com
Lin F. Yang"
University of California, Los Angeles linyang@ee ucla. edu
Csaba Szepesvári
Amii, University of Alberta, DeepMind s azepesva@ualberta.co
Abstract
In contrast to the advances in characterizing the sample complexity for solving Markov decision processes (MDPs), the optimal statistical complexity for solving constrained MDPs (CMDPs) remains unknown. We resolve this question by providing minimax upper and lower bounds on the sample complexity for learning near-optimal policies in a discounted CMDP with access to generative model (simulator). In particular, settings: (i) relaxed feasibility, where small constraint violations are allowed, and (ii) strict feasibility, where the output policy is required to satisfy the constraint. For (i), we prove that our algorithm returns an 8-optimal policy with probability 1 6, by making Ô
design model-based algorithm that addresses two
SA log(1/)) queries to the generative model, thus matching the (1 (1-
sample-complexity for unconstrained MDPs. For (ii), we show that the algorithm's log(1/6) where ( is the problem- sample complexity is upper-bounded by Ô [1-7)"e-(²
dependent Slater constant that characterizes the size of the feasible region. Finally, we prove matching lower-bound for the strict feasibility setting, thus obtaining the first near minimax optimal bounds for discounted CMDPs. Our results show that learning CMDPs is as easy as MDPs when small constraint violations are allowed, but inherently more difficult when demand zero constraint violation.
Introduction
Common reinforcement learning (RL) algorithms focus on optimizing an unconstrained objective, and have found applications in games such Atari [23] Go [28], robot manipulation tasks [29, or clinical trials [26). However, many applications require the planning agent to satisfy constraints - for example, in wireless sensor networks [10] where there is a constraint on average power consumption. More generally, in the constrained Markov decision processes (CMDP) framework, the goal is to find policy that maximizes the value associated with a reward function subject to the policy achieving a return (for a second reward function) that exceeds an apriori determined threshold [3]. There has been substantial work addressing the planning problem to find a near-optimal policy in a known CMDP [8, 7, 30, 24, 1, 35). However, since the CMDP is unknown in most practical applications, we consider the problem of finding near-optimal policy in this more challenging setting.
There have been multiple recent approaches to obtain a near-optimal policy in CMDPs in the regret-minimization or PAC-RL settings [13, 38, 9, 19, 31, 22, 36, 12, 15, 16, 11]. These works
Equual contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

tackle the exploration, estimation and planning problems simultaneously. On the other hand, recent works [16, 33, 6] consider an easier, but even more fundamental problem of obtaining a near-optimal policy with access to a simulator or generative model [20, 18, 2J. In particular, these works assume that the transition probabilities in the underlying CMDP are unknown, but the planner has access to sampling oracle (the generative model) that returns sample of the next state when given any state-action pair as input. This is the problem setting we consider and aim to øbtain matching upper and lower bounds the sample complexity of planning in CMDPs with access to a generative model.
Given a target error ε > 0, the approximate CMDP objective is to return a policy that achieves a cumulative reward within an & additive error of the optimal policy in the CMDP. Previous work can be classified into two categories based on how it tackles the constraint for the easier problem that we term relaxed feasibility. the policy returned by an algorithm is allowed to violate the constraint by at most E. On the other hand, for the more difficult strict feasibility problem, the returned policy is required to strictly satisfy the constraint and achieve zero constraint violation. Except for the recent works of Wei et al. [33] and Bai et al. [6], most provably efficient approaches including those in the cegrettmiimizztioon and PAC-RL settings consider the relaxed feasibility setting. For this problem, the best model-based al algorithm requires Ô
samples to return an E-optimal policy in an infinite-horizon --discounted CMDP with S states and A actions [16], while the best model-free approach requires Ô known upper bounds for a model-free algorithm in the strict feasibility setting are achieved by Bai
S (1-7)*E²
SA [I-
samples for achieving the objective [12]. On the other hand, the best
et al. [6]. In particular, their algorithm requires Ô (1-7)) samples [6. Theorem 2] to output an optimal policy. However, their analysis considers normalized reward and constraint value functions [6, Eq. 1] that lie in the [0, 1] range (compared to the standard [0, 1/1 - 7 range). This difference the scale of the values prevents a direct comparison of their results to our sample complexity bounds. Subsequently, we show that when appropriately normalized, our sample complexity bounds are better by a (2/1->) factor in both the relaxed feasibility (Section 4) and strict feasibility settings (Section 5).
Importantly, there are no lower bounds characterizing the difficulty of either the relaxed striet feasibility problems (except in degenerate cases where the constraint is always satisfied and the CMDP problem reduces to an unconstrained MDP). To get an indication of what the optimal bounds might be, it is instructive to compare these results to the unconstrained MDP setting. For unconstrained MDPs with access to a generative model, both model-basee [2, 21] and model-free approaches [27]
can return an e-optimal policy within near-optimal é
SA [1=>)&E> sumple-complexity [4]. Hence,
compared to the sample-complexity for unconstrained MDPs, the best-known upper-bounds for CMDPs are worse for both the relaxed and strict feasibility settings. However, it is unclear whether solving CMDPs is inherently more difficult than unconstrained MDPs. We resolve these questions for both the relaxed and striet feasibility settings, and make the following contributions.
Generic model-based algorithm: In Section 3, we provide a generic model- primal-dual algorithm (Algorithm 1) that can be used to achieve both the relaxed and strict feasibility objectives (with appropriate parameter settings). The proposed algorithm requires solving a sequence of unconstrained empirical MDPs using any black-box MDP planner.
Upper-bound on sample complexity under relaxed feasibility: In Section 4, we prove that with specific set of parameters, Algorithm 1 uses no more than ò ( SA
(1-7)²=²² samples achieve the
relaxed feasibility objective. This improves upon the bounds of HasanzadeZonuzy et al. [16] and matches the lower-bound in the easier unconstrained MDP setting, implying that our bounds are near-optimal. Our result indicates that under relaxed feasibility solving CMDPs is as easy as solving unconstrained MDPs. To the best of our knowledge, these are the first such bounds.
Upper-bound on cample-complexity under strict feasibility: In Section 5, we prove that with a specific set of parameters, Algorithm 1 uses no more than ò (1--))<2>>) to achieve the strict feasibility objective. Here Ç E (0, 1/1->] is the problem-dependent Slater constant that characterizes the size of the feasible region and influences the difficulty of the problem. Unlike Bai et al. [6], our bounds do not depend on additional (potentially large) problem-dependent quantities.
SA
Lower-bound on sample-complexity under strict feasibility: In Section 7, we prove a matching
problem-dependdett Ω
SA
lower bound on the sample-complexity in the strict feasibility

---

setting. Our results thus demonstrate that the proposed model-based algorithm is near minimax optimal. Furthermore, our bounds indicate that under strict feasibility (i) solving CMDPs is inherently more difficult than solving unconstrained MDPs, and (ii) the problem hardness (in terms of the sample-complexity) increases as Ç (and hence the size of the feasible region) decreases. To the best of our knowledge, these are first results characterizing the difficulty of solving CMDPs with access to a generative model and demonstrate a separation between the relaxed and strict feasibility settings.
Overview of techniques: For proving the upper bounds, we use a specific primal-dual algorithm that reduces the CMDP planning problem to solving multiple unconstrained MDPs. Specifically, by using a strong-duality argument, we show that we can obtain an optimal CMDP policy by averaging the optimal policies of a specific sequence of MDPs. For each MDP in this sequence, we use the model- based techniques from Agarwal et al. [2]. Li et al. [21] to prove concentration results for data-dependent policies. This allows us to prove concentration for the optimal data-dependent policy in the CMDP, and subsequently bound the sample complexity for both the relaxed and strict feasibility problems. For the lower bound, we modify the MDP hard instances [5, 34] to handle a constraint reward. This makes the resulting gadgets significantly more complex than those required for MDPs, but we show that similar likelihood arguments can be used to prove the lower-bound.
2 Problem Formulation
We consider an hnfinite-horizon discounted constrained Markov decision process (CMDP) [3] denoted by M, and defined by the tuple (S, P, r, b, p,7) where S is the set of states, A is the action set, P. : S x A ++ As is the transition probability function, & E As is the initial distribution of states and E [0, 1) is the discount factor. The primary reward to be maximized is denoted by
r : S:S x A + [0.1], 1], whereas the constraint reward is denoted by c : S x A - 1J². If A denotes the simplex over the action space, the expected discounted return or reward value function of a stationary, stochastic policy² π : S + A is defined as V. (p) = E ao....... E 7'r(e. a))
where 8D ~ p, az ~ ((((s)), and St+1 ~ P((|st, az). For each state-action pair (s, and policy T. the reward action-value function is defined O S x A - R. and satisfies the relation: (s) = (=(s),, Q7 (x, +)), where (s)(s) is the reward value function when the starting state is equal 8. Analogously, the construint value function and constraint action-value function of policy is denoted by Va (p) and Q respectively. The CMDP objective is to return a policy that maximizes
V, (p). while ensuring that Vi2 (p) 2 b. Formally,
max V. (p) s.t. (p) b.
The optimal stochastic policy for the above CMDP is denoted by x² and the corresponding reward value function is denoted by (p). We also define ( max, V. (p) b as the quantity referred to as the Slater constant [12, 6]. The Slater constant is a measure of the size of the feasible region and determines the difficulty of solving Eq. (1).
For simplicity of exposition, we assume that the rewards r and constraint rewards e are known, but the transition matrix P is unknown and needs to be estimated. We note that assuming the knowledge of the rewards does not affect the leading terms of the sample complexity since learning these is an easier problem compared to the transition matrix [5, 27]. We assume access to generative model or simulator that allows the agent to obtain samples from the P(-|s, a) distribution for any (s, a). Assuming access to such a generative model, our aim is to characterize the sample complexity required to return a near- optimal policy ă in M. Given a target error ε > O, we can characterize the performance of policy Æt in two ways:
Relaxed feasibility: We require â to achieve an approximately optimal reward value, while allowing it to have a small constraint violation in M Formally, we require á s.t.
(²)( 2 (p) e, s, and Vaa (p) 2 b b-s.
(2)
"These ranges for r and are chosen for simplicity. Our results can be easily extended to handle other ranges. 'The performance
an optimal policy in a CMDP can always achieved by a stationary, stochastic policy [3]. On the other hand, for an MDP, suffices to only consider stationary, deterministic policies [25]. In general, the desired gap in the reward value can be different from the level of constraint violation.
3

---

Algorithm 1: Model-based algorithm for CMDPs with generative model
Input: S (state space), A (action space), r (rewards), (constraint rewards), C (Slater constant), N (number of samples), b' (constraint RHS), w (perturbation magnitude), U (projection upper bound), S (epsilon-net resolution). ' (number of iterations), Ao = 0 (initialization).
2 For each state-action (s, a) pair, collect N samples from P(-]ss a) and form P. Perturb the rewards to form vector Tp(s, a) == r(s,a) + E(s, a) where E(s, a) w]]
4 Form the empirical CMDP M = AS P. Tpp c, b', P: 7).
Form the epsilon-net A {0, E 2e U}. do Update the policy by solving an unconstrained MDP: मe = arg max V
6 for t < 0 to
7
Ape
Update the dual-variables: A4+1 RA [PMM.U]
|^e- - 7) (V. 1/
end
10
Output: Mixture policy कr = T Li= #r.
Strict feasibility We require á to achieve approximately optimal reward value, while simultane- ously demanding zero constraint violation in M. Formally, we require A s.t.
(p) 2 (p) -, and V (p) 2 6
(3)
Next, we describe a general model-based algorithm to handle both these cases, and subsequently instantiate the algorithm for the relaxed feasibility (Section 4) and strict feasibility (Section 5) settings.
3 Methodology
We will use model-based approach [2, 21, 16] for achieving the objectives in Eq. (2) and Eq. (3). In particular, for each (8, a) pair, we collect N independent samples from P(.|s, a) and form an empirical transition matrix P such that ((s||s,, a) = N where N (s'lss, a) is the number of samples that have transitions from (s. to s'. These estimated transition probabilities are used to form an empirical CMDP. Due to a technical requirement, (which we will clarify in the Section 6), we require adding small random perturbation to the rewards in the empirical CMDP3. In particular, for each E S and a E A. we define the perturbed rewards (s, a) == r(s, a) + E(s, a) where E(s, a) ~ 2/(0, w] are i.i.d. uniform random variables. Finally, compared to Eq. (1), we will require solving the empirical CMDP with a constraint right-hand side equal to b'. Note that setting 5' < b corresponds to loosening the constraint, while 6' > b corresponds to tightening the constraint. This completes the specification of the empirical CMDP M that is defined by the tuple AS P. rpp c, b', p, p, For M, the corresponding reward value function (and constraint value function) for policy ι is denoted as V r9 (p) (and v.Th (p) respectively). In order to fully instantiate M, we require setting the values of w (the magnitude of the perturbation) and (the constraint right-hand side). This depends on the specific setting (relaxed vs strict feasibility) and we do this in Sections 4 and respectively. We compute the optimal policy for the empirical CMDP M follows:
#* E arg max V (p) s.t. (2) 2
(p)
(4)
In contrast to Agarwal et al. [2]. Li et al. [21] that consider model-based approaches for unconstrained MDPs and can solve the resulting empirical MDP using any black-box approach, we will require solving Eq. (4) using specific primal-dual approach that we outline next. Using this algorithm enables us to prove optimal sample complexity bounds under both relaxed and strict feasibility.
First, observe that Eq. (4) can be written as an equivalent saddle-point problem ( (Tr,() + (V - ]]] where À E IR corresponds to the Lagrange multiplier for the constraint. The solution to this saddle-poin point problem is (#*, where ** is the optimal empirical policy and X is the optimal Lagrange multiplier. We solve the above saddle-point problem
max, minx20
Siiiiaar to MDPs [21], we instead perturb the Q function while planning in the empirical CMDP.

---

iteratively, by alternatively updating the policy (primal variable) and the Lagrange multiplier (dual variable). I is the total number of iterations the primal-dual algorithm, we define ūn and ) to be the primal and dual iterates for & E [7] == , T). The primal update at iteration is given as:
# arg max
[1) + (o) = arg max V.J +iy+A
(5)
Hence, iteration L of the algorithm requires solving an unconstrained MDP with reward equal to pp + λpc. This can be done using any black-box MDP solver such as policy iteration. The algorithm updates the Lagrange multipliers using a gradient descent step and requires projecting and rounding the resulting dual variables. In particular, the dual variables are first projected onto the [0, U'] interval, on |^* After the projection, the resulting iterates are
where U is chosen to be an upper-boume rounded to the closest element in the set A = {0, E., 2......; U}, one-dimensional epsilon-net (with resolution E over the dual variables. In Section 6, we will see that constructing such an eet will
enable us to prove concentration results for all À E A. The dual update at iteration is given as:
A4+1 RA |ro.0] A - (V.t (p) - [D)]
where P(o,ur(AA = arg min pEjo,r AA - pl projects onto the [0, interval and RA arg min PEA [A - p| rounds À to the closest element A. Since is an epsilon-net, for all X E [0, U.. TA - [A]l S 6, Finally, 7) in Eq. (6) corresponds to the step-size for the gradient descent update. The above primal-dual updates are similar to the dual-descent al algorithm proposed in Paternain et al. [24]. The pscudo-code sunmarizing the entire model-based algorithm is given in Algorithm 1. We note that although Algorithm requires the knowledge of Ç, this is not essential and we can instead use an estimate of Ç. In Appendix F, we show that we can estimate ( to within a factor of using ISILA (I-T><
additional queries. Next, we show that the primal-dual updates in Algorithm 1 can
be used to solve the empirical CMDP M. Specifically, we prove the following theorem (proof in Appendix A) that bounds the average optimality gap (in the reward value function) and constraint violation for the mixture policy returned by Algorithm 1.
Theorem 1 (Guarantees for the primal-dual algorithm). For target error Sipe >> 0 Oand the primal- 1 + (U-x-y² . U11-7) and
dual updates in Eq. (5)-Eq. (6) with U > |1 T
40/2
cx (1-7)²
E
Sup (1 (11 (U-X")
GU
the mixture policy म. == T
1 IT-1 be satisfies,
te , (p) 2 x* ry (p) - Eppt ; 2 (p) 2 b' Eop..
Hence, with T' = 0(%eap) and e = (E²2p) the algorithm outputs a policy är that achieves reward Eupt close to that of the optimal empirical policy #*, while violating the constraint by at most eog Hence, with sufficient number of iterations T and by choosing a sufficiently small resolution E, for the epsilon-net, we can use the above primal-dual algorithm to approximately solve the problem in Eq. (4). In order to completely instantiate the primal-dus algorithm, we require setting U > | We will subsequently do this for the the relaxed and strict feasibility settings in Sections 4 and respectively. We note that in contrast to Paternain et al. [24, Theorem 3] that bounds the Lagrangian, Theorem provides explicit bounds on both the reward suboptimality and constraint violation.
We conclude this section by making some observations about the primal-dual algorithm while the subsequent bounds for both settings heavily depend on using the "best-response" primal update in Eq. (5), the algorithm does not require using the specific form of the dual updates in Eq. (6). Indeed, when used in conjunction with the projection and rounding operations in Eq. (6), we can use any method to update the dual variables (not necessarily gradient descent) provided that it results in an O (T + a,T") (for < 1) bound on the dual regret (see the proof of Theorem I for the definition).
Next, we specify the values of N, U', w. e,, T, U in Algorithm to achieve the objective in Eq. (2).
4 Upper-hound under Relaxed Feasibility
In order to achieve the objective in Eq. (2) for a target error E > 0, we require setting N log(1/6)
Ô (1-7)- 2- ). = 8
35 and w = 8
5012)) This completely specifies the empirical CMDP M
5

---

and the problem in Eq. (4). In order to specify the primal-dual algorithm, we set U = O (1-(())))
= O (s 7) and T = O (1)") With these choices, we prove the following theorem in Appendix B and provide a proof sketch below.
Theorem 2. For a fixed E (0, 1/1-) and ā E (0. 1). Algorithm 1 with N = Ö log(1/5)
(1-7)-82
samples, b' = b- 35 w.w ماللك U - 0 (V/ - O (= (1))) and T = O (1)(1-))=5*)
7)9)
x
w
returns policy Ft that satisfies the objective in Eq. (2) with probability at least 1 - 48.
Proof Sketch: We prove the result for a general primal-dual error Cage < E and =
5apt and
2
subsequently specify Eug and hence b'. In Lemma 11 (proved Appendix B), we show that if the constraint value functions are sufficiently concentrated (the empirical value function is close to the ground truth value function) for both the optimal policy xt M and the mixture policy गт returned by Algorithm i.e. if
V - (p')
8 - Eapt S
(P)( V. (0) S
8 - Eapt
2
then (i) policy गт violates the constraint in M by at most E, i... Ve** (p) 2 b b- E, and (ii) its suboptimality in M (compared TT) can be decomposed as:
V (p) u (p) S 1-7 + Eage + V (p) V.r (p) + 1et Vे (p))
2w
(8)
In order to instantiate the primal-dual algorithm, we require a concentration result for policy oद that maximizes the the constraint value function, i.e. if nr == arg max V (p), then we require
V. (p) V2- (0) v E + Eapt- In Case 1 of Lemma 9 (proved in Appendix A), we show that if this
2(1+w) concentration result holds, then we can upper-bound the optimal dual variable |X* by (o++ With these results in hand, we can instantiate all the algorithm parameters except N (the number of samples required for each state-action pair). In particular, we set Expt = å and hence b' b and
32 <(1-2) <1 1. Setting U 5e (1-7) ensures that the U > | condition required by Theorem 1 holds. To guarantee that the primal-dual algorithm outputs an _ approximaae policy, we Theorem 1
to set T O ( (1-1))-0)) iterations and E O (=2(1 - >) ) Eq. (8) can then be simplified as,
V. (p) - ,.T
V. (p) V. (p) + V .. (p) - Vे (p)
Putting everything together. in order to guarantee an e-reward suboptimality for मr, we require that:
V.ti (p) - (p)
-
5c
v
(p) (TT(() (p)
-
Ve (p) - V/- (p) s 35
4
8
8
V (p) V.. (p)
2 (p) , r (p)
(9)
4
4'
We control such concentration terms for both the constraint and reward value functions in Section 6, and bound the terms in Eq. (9). In particular, we prove that for a fixed E (0, 1/1->), using
N > Ô log(1/8) samples enssures that the statements in Eq. (9) hold with probability 1 - 48. [1->)²>²
This guarantees that V (p) v.r (p) S E and V (p) 2 b b-
Hence, the total sample-complexity of achieving the objective in Eq. (2) is Ô SAlog(11/) (I-y)
This
result improves over the Ô ( (og(1/)) result in HasanzadeZonuzzy et al. [16]. Furthermore, our
[I (1-7)*²
result matches the bower-bound in the easier unconstrained setting [4], implying that our bounds are
optr-ol We conclude that under relaxed feasibility and with access to generative model, solv- ing constrained MDPs is as easy solving MDPs. Algorithmically, we do not require constructing an optimistic CMDP like HasanzadeZonuzy et al. [16]. Instead, we solve the empirical CMDP in Eq. (4) using specific primal-dual updates Eqs. (5) and (6). Note that if the rewards and constraint rewards (corresponding to K constraints) are unknown and need to be estimated, a union bound guarantees that the sample complexity will only increase by multiplicative log( K + 1) factor [16].

---

In this setting, when using the normalized value functions, Bai et al. [6, Corollary 1] prove an bound on the sample complexity. When translated to the standard [0, 1/2->] range,
S4
(1-7))
this implies an O better dependence on 1/1-y and does not depend on Ç. Importantly, unlike [6], our result implies that in the relaxed feasibility setting, solving CMDPs is as hard as solving MDPs. In the next section, instantiate Algorithm in the strict feasibility setting.
SA (1->)" bound [6, Footnote 6]. In comparison, our result in Theorem has a
5 Upper-bound under Strict Feasibility
Unlike Section 4, since the strict feasibility setting does not allow any constraint violations, necessitates using stricter constraint in the empirical CMDP to account for the estimation error in the transition probabilities. Algorithmically, we require setting > b. Specifically, in order to
achieve the objective in Eq. (3) for target error > we require setting N =0= Ô log(1/5)
(
(1--))<>?
y' = b+ <(I=7)< and w <(l=>), This completely specifies the empirical CMDP N7 and the problem 4[l+w)
in Eq. (4). To specify the primal-dual algorithm, we set U <(1->) & = O (sa - -) and
T O (+/t->))<++"). With these choices, we prove the following theorem in Appendix C, and provide a proof sketch below.
Theorem 3. For fixed e (0, 1/1-) and 5 (0, 1), Algorithm 1, with N Ô (og(1//)) sam- (1-7)"==A²
ples, b' = b+ =(1->لs w =(1-2), U = 4(l+w) <(->) = O (=2 - 5)) and T = 0 (1/1 (1/11>)"5'' =*))
20
returns policy मा that satisfies the objective in Eq. (3), with probability at least 1 46.
Proof Sketch: We prove the result for general V/ + for > 0 and primal-dual error Eags < A and subsequently specify A (and hence 1/) and Eup-- In I Lemma 12 (proved in Appendix C), we prove that if the constraint value functions are sufficiently concentrated (the empirical value function is close to the ground truth value function) for both the optimal policy x' in M and the mixture policy क returned by Algorithm i.e. if
V (p) at (T)(p) SA - Eipt
V (p) - V. (p) SA
(10)
then (i) policy är satisfies the constraint in M i.e. (aT(p) 2 b, and (ii) its suboptimality in M (compared to T²" can be decomposed as:
2w
V (p) V. (p) S
+ Enj + 24A V. (p) V (p) (+ (p) V (0) (11)
-
In order upper-bound |^1 require a concentration result for policy म. arg max V (p)
that maximizes the the constraint value function. In particular, we require A
(0, and
V.l (p) (p) v (2 s A. A. In Case 2 of Lemma 9 (proved in Appendix A), show that if this concentration result holds, then we can upper-bound the optimal dual variable |A*| by 2(1+w) Using the above bounds to simplify Eq. (11),
V. (p) V.TT(a) S
2w 1-7 + Cap +
4A(1 + W) <(1 7)
| (p) V (0) + V= (p) V (p)
With these results in hand, we can instantiate all the algorithm parameters except N (the number of samples required for each state-action pair). In particular, set A = (1 (1-7)
40 S, Eage
=1-715 < E. and ب e(1-1)
8 10 < 1. We set U .リー for the primal-dual algorithm, ensuring
200
that the U |^*| condition required by Theorem holds. In order to guarantee that the primal-dual algorithm outputs =(1->) ( -approximat policy,
Theorem 1 to set T O (1 (1--))
200
Again, we do not need know and can be replaced by the estimator constructed in Section F.
7

---

iterations and El == With these values, we can further simplify Eq. (11),
3x V (p) V.z (p) 5
V. (p)
+ V. (p) V (p)
Putting everything together, in order to guarantee an e-reward suboptimality for Tr, we require the following concentration results to hold for A s(1-2
40
44 5
19A V (p) V.r (0) (0) SA: (p) V. S 5
Ve- (p) V.-h (0)
V. (p) - V. (0)
S 5i ()) - (0) (0) 5
E
(12)
We control such concentration terms for both the constraint and reward value functions in Section and bound the terms in Eq. (12). In particular, we prove that for fixed & E (0, 1/1->), using
N 2 Ô guarantees that V.r" (p) V (p) I and V.*T (p) 2 b.
1og(1/8) (1-
ensures that the statements in Eq. (12) hold with probability 1 - 46. This
Hence, the total sample-complexig of achieving the objective in Eq. (3) is Ô SA log(1/h) (1-7)" (= Similar
to Section 4, in the strict fcasibility setting, with the normalized value functions, Bai et al. [6] prove an O
S4 !1
bound on the sample complexity. When translated the standard [0, 1/1 //1 range,
this implies an $2
SA
bound (see Appendix for a detailed explanation). In comparison,
(1-7)"=2(C
our result in Theorem 3 has better dependence on (2/1-7).
In Section 7, we prove a matching lower bound showing that Algorithm minimax optimal the strict feasibility setting. In the next section, we give more details for the bounding the concentration terms in Theorem 2 and Theorem 3.
Bounding the concentration terms
We have seen that proving Theorem 2 and Theorem 3 require bounding the concentration terms in Eq. (9) and Eq. (12) respectively. In this section, we detail the techniques to achieve these bounds.
Our approach requires reasoning about a general unconstrained MDP Ma = (S. P, 7; a) with the same state-action space, transition probabilities and discount factor as the CMDP in Eq. (1) but with rewards equal to a, coming from [0, amax]. Analogously, we define the empirical MDP Ma = AS 7, a)) where the empirical transition matrix P is the same as that of the empirical CMDP in Eq. (4). Similarly, we define MDP (and its empirical counterpart) M3- (S, A, P, 3) (and Mg) where the rewards 33 are from [0, fmax]. Note that the rewards a and /3 are independent of the sampling of the transition matrix. The corresponding value functions for policy in M, and M. (and Ma and Mş) are denoted as V and V (and V and V/z) respectively, with the optimal value functions denoted as VØ and V.- (and Vğ and V/2) respectively. The action-value function in Ma for policy π and state-action pair (s, a) is denoted as (s, a) and analogously for M.. For the subsequent technical results, we require that M, satisfy the following gap condition [21]:
Definition 4 (I-Gap Condition). MDP Ma satisfies the t-gap condition if Vs, Vi(())
maxa'sa4t tn (s) Q7 (s,aa) 2 where A" == arg max V and # (s) arg max, (% is the optimal action in state s.
Intuitively, the gap condition states that there is unique optimal action at each state and there is a gap between the performance of best action and the second best action. With this gap condition, use techniques in Li et al. [21] to prove the following lemma in Appendix D.
Lemma 5. Define # == arg max, & VaL If is the event that the t-gap condition in Definition holds for Ma and for 8 (0, 1) and C(δ) 72 log
1160 8 log(s/->)) ) the number of samples
[1 71-7)=16
per state-aud actte-action pair is N > 1-7
4C()) then with probability at least Pr[E] 6 6/10.
C(ल)
V
<
N. (1 7)3 1|
8

---

Hence, for policy a we can obtain a concentration result in another MDP Mg with an independent reward function 33 and the same empirical transition matrix P.
We wish to use the above lemma for the unconstrained MDP formed at every iteration of the primal update in Eq. (5). In particular, for given A,, we will use Lemma 5 with a Tp + X.C and 8 Yp
Doing so will immediately give us bound on V. -V 1oo and hence V. (p) - V: 7 (p) In
order to use Lemma 5, we require the unconstrained MDP My to satisfy the gap condition in Definition 4 for any À E A. This is achieved by the perturbation of the rewards in Line 3 of Algorithm 1. Specifically, using Li et al. [21, Lemma 6] with a union-boume over A, we prove (in Lemma 16 in Appendix D) that with probability 1 - 6/10, Mry+ satisfies the gap condition in Definition with
w 8 (1->) 30 A||S]] A|2 for every E A. This allows us to use Lemma with Tp + c for all & E [T'. and / = Ty and 8 = c. In the following theorem, we obtain concentration result for each āe and hence for the mixture policy ūт.
Theorem 6. For 8 E 1), I 1 and C(6) log [6(1+U+w) SA +) where 1. (1-7)2.8
v5(1-)) 11
10(8), then for कe output by Algorithm I, with probability at least 1 - 5/5, if 2 T-7
C(8) V (p) - VT5 Tu (p) S 2 N 71- |1 (p) - (=*( VV N (1.(1 (1-
C(6)
Eqs. (9) and (12) also require proving concentration bounds for fixed (that do not depend on the data) policies n² and T²- This can be done by directly using Li et al. [21, Lemma 1]. Specifically, we prove the following the lemma in Appendix D.
Lemma 7. For d E 10, w I and C")) = 72 log
[|8] log(e//1)))
if N N
(C) T-y
and
B(O, N): = V N1- then with probability at least 1 - 33,
C((8)
V.. (p) ".2 (0) 2BB N); |v=" (0) - V. (0) s B)² Vo- (p) Vee S B))
Using Theorem 6 and Lemma 7, we can bound each term in Eq. (9) and Eq. (12), completing the proof of Theorem 2 and Theorem 3 respectively. In the next section, we prove a lower-bound on the sample-complexity in the strict feasibility setting.
7 Lower-bound under strict feasibility
For target error of e, our lower bound construction demonstrates that it is important to estimate the constraint value function to a smaller error equal to e' := <(1 - -7)ç. Intuitively, this is because a small (e') estimation error in the constraint value can incorrectly render the optimal policy infeasible and result in large e'/(1-)<< suboptimality in the reward value. In Appendix 1. we detail this intuition a simplified bandit setting and present the formal CMDP lower-bound below.
We define an algorithm to be (c, 8)-sunnd if it outputs a policy á such that with probability 8, V.* (p) V (p) < and V (p) 2 b.ce. the algorithm achieves the strict fcasibility objective in Eq. (3). We prove a lower bound on the number of samples required by any (s, 6)-sound algorithm on the
CMDP instance in Fig. 1. For this instance, with specific setting of the rewards and probabilities
Po < p < we prove that any (e, -)-uunnd algorithm requires at least ? [In(SS) samples to distinguish between Mo and Mia- In partieular, we prove the following theorem Appendix E.2.
(1
Theorem 8. There exists constants To (1 1/ log([ 1). 0 so S ويرل min 11, पーं
6o (0, 1), such that, for any 7 (70. 1), e =0, (0, 60). any (5.8)-sound algorithm requires Ω 9Alm(1/48) samples from the generative model in the worst case. (-<-[1-)>
The above lower bound matches the upper bound in Theorem 3 and proves that Algorithm is near minimax optimal in the strict feasibility setting. It also demonstrates that solving CMDPs under strict

---

SD
20
$1
Pia
a1
04
5
WEA
FET
00
01
Gg
05
01
%
Pasi
S1S)
Figure 1: The instance consists of CMDPs with S = 2 (for some integer > 0) states and A actions. We consider SA + CMDPs MM and Mi,a E (1....S), a E (1,...,A) A}) that share the same structure shown in the figure. For each CMDP, On is the fixed starting state and there is deterministic path of length m + from 0g to each the Except for states 5; the transitions in all other states are deterministic. For i o 0, for action E in state 5;, the probability of staying in 5, is Pi.a. while that of transitioning to state z; is Pi,a- There is only one action dg in 5p and the probability of staying in is Po, while that of transitioning to state 2g is Po.a. The CMDPs Mg and M, only differ the values of pi,a- The rewards r and constraint rewards are the same in all CMDPs and are denoted in green and red respectively.
states - 8, (for E {0. .,......,) S)).
feasibility inherently more difficult than solving unconstrained MDPs or CMDPs in the relaxed feasibility setting. Finally, we can conclude that the problem becomes more difficult (requires more samples) as the Slater constant decreases and the feasible region shrinks.
Discussion
We proposed model-based primal-dual algorithm for planning in CMDPs. Via upper and lower bounds, we proved that our algorithm is near minimax optimal for both the relaxed and strict feasibility settings. Our results demonstrate that solving CMDPs is easy MDPs when small constraint violations are allowed, but inherently more difficult when we demand zero constraint violation. Algorithmically, we required a specific primal-dual approach that involved solving a sequence of MDPs. In contrast, model-based approaches for MDPs (2, 21] allow the use of any black-box planner.
possible to obtain an PI-
S²A
sample complexity for black-box CMDP planner in
relaxed feasibility setting. However, the O(S A) dependence the bound implies that we need to accurately estimate all entries in the transition probability matrix, and is therefore loose in the special case of unconstrained MDPs [2, 21]. In the future, we aim to extend our near-optimal sample complexity results to black-box CMDP solvers.
Acknowledgements
We would like to thank Reza Babanezhad and Arushi Jain for helpful feedback on the paper. Csaba Szepesvári gratefully acknowledges the funding from Natural Sciences and Engineering Research Council (NSERC) of Canada, "Design.R Al-assisted CPS Design" (DARPA) project and the Canada CIFAR AI Chairs Program for Amii. Lin Yang is supported in part by DARPA grant HR001 12190130 and NSF Award 222187 1871. This work was partly done while Lin Yang was visiting Deepmind.
10

---

References
[1] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International Conference Machine Learning, pages 22 31. PMLR, 2017.
[2] Alckh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Conference Learning Theory, pages 67-83. PMLR, 2020.
[3] Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
[4] Mohammad Gheshlaghi Azar, Rémi Munos, and Bert Kappen. On the sample complexity of reinforcement learning with a generative model. arXiv preprini arXiv: arXiv: /tt.://066.6666 2012.
[5] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with generative model. Machine learning. 91 (3):325-344 -495, 2013.
[6] Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. arXiv preprint 279.:2200..06332, 2021.
[7] Vivek Borkar and Rahul Jain. Risk-constrained markov decision processes. IEEE Transactions on Automatic Control, 59(9):257-2279, 2014.
[8] Vivek S Borkar. An actor-critic algorithm for constrained markov decision processes. Systems control letters, 54(3):207-213, 2005.
[9] Kianté Brantley, Miroslav Dudik, Thodoris Lykouris, Sobhan Miryoosefi, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun. Constrained episodic reinforcement learning in concave- convex and knapsack settings. arXiv preprint arXiv:2006.05005/ 2020.
[10] Chiara Buratti, Andrea Conti, Davide Dardari, and Roberto Verdone. An overview on wireless sensor networks technology and evolution. Sensors, 9()):88696688)) 2009.
[11] Yi Chen, Jing Dong, and Zhaoran Wang. primal-dual approach to constrained markov decision processes. arXiv preprint arXiv: 100.0 2021.
[12] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligence and Statistics, pages 3304-3318 PMLR, 2021.
[13] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. mdps. arXiv preprint arXiv:2003.02189, 2020.
in constrained
[14] Fei Feng, Wotao Yin, and Lin F. Yang. Does knowledge transfer always help to learn better policy? CoRR, abs/1912.02988. 2019. URL /tttt://arrxe www.vv.oo orgg abbs//////// 992. 6..
[15] Ather Gattami, Qinbo Bai, and Vaneet Aggarwal. Reinforcement learning for constrained markov decision processes. In International Conference on Artificial Intelligence and Statistics, pages 2656-2664. PM 2021.
[16] Aria HasanzadeZonuzz, Dileep M. Kalathil, and Srinivas Shakkottai. Model-based reinforce- ment learning for horizon discounted constrained markov decision processes. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelli- gence, IJCA/ 2021, Virtual Event / Montreal, Canada, 19-27 August 1, pages 2519-2525 ijcai.org, 2021.
[17] Arushi Jain, Sharan Vaswani, Reza Babanezhad, Csaba Szepesvari, and Doina Precup. Towards painless policy optimization for constrained mdps. arXiv preprint arXiv:2204.05176, 2022.
[18] Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.

---

[19] Krishna Chaitanya Kalagarla, Rahul Jain, and Pierluigi Nuzzo. A sample-efticien algorithm for episodic smite-horizon MDP with constraints. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI, pages 8030-8037. AAAI Press, 2021.
[20] Michael Kearns and Satinder Singh. Linite-sample convergence rates for q-learning and indirect algorithms. Advances neural information processing systems, pages 996-1002, 1002, 1999.
[21] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances in neural information processing systems, 33: 12861-12872 2020.
[22] Sobhan Miryoosefi and Chi Jin. A simple reward-free approach constrained reinforcement learning. In International Conference on Machine Learning, pages 15666-15698. PMIR, 2022.
[23] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, nature, 518(7540):529-533, 2015.
[24] Santiago Paternain, Luiz FO Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Con- strained reinforcement learning has zero duality gap. arXiv preprint arXiv: 13393, 2019.
[25] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[26] Andrew Schaefer, Matthew D Bailey, Steven M Shechter, and Mark S Roberts. Modeling medical treatment using markov decision processes. In Operations research and health care, pages 593-612. Springer, 2005.
[27] Aaron Sidford, Mengdi Wang. Xian Wu, Lin F Yang. and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with generative model. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 5192-5202, 2018.
(28) David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mas- tering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
[29] Jie Tan, Tingnan Zhang, Erwin Coumans, Atil Iscen, Yunfei Bai. Danijar Hafner, Steven Bohez, and Vincent Vanhoucke. Sim-to-real: Learning agile locomotion for quadruped robots. arXiv preprint arXiv: /804. 10332, 2018
[30] Chen Tessler, Daniel Mankowitz, and Shie Mannor. Reward constrained policy optimization. arXiv preprint
2018.
[31] Akifumi Wachi and Yanan Sui. Safe reinforcement learning in constrained markov decision processes. In International Conference on Machine Learning, pages 9797-9806. PMLR, 2020.
[32] Mengdi Wang. Randomized linear programming solves the markov decision problem in nearly linear (sometimes sublinear) time. Mathematics of Operations Research, 45(2):517-546, 2020.
[33] Honghao Wei, Xin Liu, and Lei Ying. A provably-efficient model-free algorithm for constrained markov decision processes. arXiv preprint arXiv:2106.01557 2021.
[34] Chenjun Xiao, Ilbin Lee, Bo Dai, Dale Schuurmans, and Csaba Szepesvari. On the sam- ple complexity of batch reinforcement learning with policy-induced data. arXiv preprint 2rXiv:2/06.09973 2021.
[35] Tengyu Xu, Yingbin Liang, and Guanghui Lan. Crpo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pages 11480-11491. PMLR, 2021.
[36] Tiancheng Yu, Yi Tian, Jingzhao Zhang, and Suvrit Sra. Provably efficient algorithms for multi- objective competitive rl. In International Conference on Machine Learning, pages 12167-12176. PMLR, 2021.
12

---

[37] Andy Zeng, Shuran Song, Johnny Lee, Alberto Rodriguez, and Thomas Funkhouser. Tossingbot: Learning to throw arbitrary objects with residual physics. IEEE Transactions on Robotics, 36 (4):1307-1319, 2020.
[38] Liyuan Zheng and Lillian Ratliff. Constrained upper confidence reinforcement learning. In Learning for Dynamics and Control, pages 620-629. PMLR, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [N/A]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "oCcyJ8-rU59", "reviewer": "Reviewer_KfEz", "summary": "The paper considers Constrained MDPs and finds the sample complexity bounds. The paper results seem weaker than that in [6]. The paper mentions that [6] has a Lipshitz constant L. However, this constant is when the objective function and constraint function are convex, while is 1 for the setup of this paper. As such, [6] does not have the parameter L and thus the authors misrepresent the prior work. Given that the results in this work are not better than the state of the art, the reviewer does not believe that the paper can be accepted in its current form. ", "questions": "Please see above", "limitations": "Please see above", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper results seem weaker than that in [6]. The paper mentions that [6] has a Lipshitz constant L. However, this constant is when the objective function and constraint function are convex, while is 1 for the setup of this paper. As such, [6] does not have the parameter L and thus the authors misrepresent the prior work. Given that the results in this work are not better than the state of the art, the reviewer does not believe that the paper can be accepted in its current form. \n\nBased on the discussions with the authors, I am increasing the score. Some evaluations would be good in the paper. Also, more discussions on novelty would help. Use of zero constraint part achievability beyond that for relaxed setup is standard. The key contributions are: (i) lower bound on strict feasibility, (ii) achievability for relaxed setup. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "itnYIrFL3Hw", "reviewer": "Reviewer_3jqt", "summary": "The paper studies the sample complexity for learning constrained MDPs with a generative model. The authors provide minimax optimal upper and lower bounds for two settings: relaxed feasibility, where one seeks the best policy matching the constraints up to a slack of epsilon, and strict feasibility, where instead one focuses on strictly matching the constraints. Interestingly, the authors show that the first setting is as easy as solving unconstrained MDPs (ie the same worst-case sample complexity is attainable and optimal), while the second setting is strictly harder.", "questions": "Overall I think the paper provides a significant contribution to our understanding of learning constrained MDPs (though in a limited setting with a generative model). I thus vote for acceptance. Here are a few comments/questions.\n\n1. One thing I find slightly weird is the definition of relaxed feasibility, where the same value \\epsilon is used for both the objective  function and the constraint. Since r and c are different quantities with different meanings (and possibly on different scales), I was wondering whether it wouldn't be more reasonable to have two distinct parameters, say \\epsilon_r and \\epsilon_c, which can be used to properly tune the desired degree of sub-optimality and constraint violations.\n\n2. Related to the previous point, if we imagine to have an algorithm and analysis for this case with two different values of \\epsilon, it might be even possible to have a unified treatment for the relaxed and strict feasibility settings (right now the algorithm must be instantiated with different parameters -- eg b' -- for the two settings). In particular, the latter would be just a special case obtained by setting \\epsilon_c = 0. A unified analysis might also be possible. Would there be any fundamental complication in handling two different values of epsilon for r and c?\n\n3. Here a single constraint c is considered. What if we have multiple constraints to satisfy? How would the sample complexity scale with the number of constraints? Polynomially? Logarithmically? \n\n4. While I find the primal-dual approach interesting, it was not completely clear to me why we cannot simply solve the empirical MDP with, say, linear programming (or any black-box approach). Could the authors elaborate on that?\n\n5. Footnote 1 mentions that the [0,1] bounded rewards assumption is only for simplicity and one can handle other ranges. Is it also easy to handle unbounded rewards (eg sub-Gaussian)?\n\n6. The algorithm is not really adaptive as it requires a fixed number of samples N (to collect from each s,a) as input. Would it be possible to have a variant of the algorithm with an adaptive sampling and stopping rule?\n\n7. I guess Theorem 8 should read as \"for any sound algorithm and any values of the parameters (eg S, A, etc), there exists an MDP with S states, A actions, etc such that the algorithm must pay at least the stated sample complexity\". While I see how the instance in Figure 1 can be made arbitrarily large in terms of number of actions A, it is not clear there how to do the same with the number of states S.", "limitations": "Limitations have been properly discussed. I would stress more in the paper that considering the tabular (finite S,A) setting with a generative model limits the practical impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper studies a relevant problem (that of constrained MDPs)\n- The results are significant as they close the gap between upper and lower bounds for this setting\n- The algorithm and its analysis are, to my knowledge, novel\n- The fact that CMDPs are as easy as standard MDPs in the relaxed feasibility regime is also an interesting and relevant result\n- The paper is very well written. The proof sketches are very clear\n\nWeaknesses:\n- The paper assumes access to a generative model.\n- The algorithm and its analysis need to handle the two settings (relaxed and strict feasibility) differently (see below).\n- No numerical result is presented.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fn6ndUbiyz", "reviewer": "Reviewer_KeTv", "summary": "This paper studies sample complexity bounds for constraint MDPs with generative model under relaxed feasibility setting (where the algorithm needs to find a policy that achieves \\epsilon-optimal reward and \\epsilon constraint violation) and strict feasibility setting (where the algorithm needs to find a policy that achieves \\epsilon-optimal reward and 0 constraint violation). For the relaxed feasibility setting, this paper achieves $O(SA(1-\\gamma)^{-3}\\epsilon^{-2})$ sample complexity, which is minimax optimal and matches the lower bound for unconstraint case. For strict feasibility setting, this paper achieves $O(SA(1-\\gamma)^{-5}\\epsilon^{-2}\\zeta^{-2})$ sample complexity and proves a corresponding lower bound.\n", "questions": "- The dependency on Slater constant ($\\zeta=\\max_\\pi V^\\pi_c(\\rho)-b$) is interesting. Since the Slater constant doesn’t depend on the reward function, for any MDP one can always add a redundant state with r=0 and c=1 (and an action from the initial state that deterministically leads to this redundant state) so that the Slater constant becomes bigger. Consequently, the MDP becomes easier. If I understand correctly, with this redundant state the algorithm can somewhat “amortize” its reward and constraint: if the algorithm visits this redundant state with positive probability, its constraint will be increased but reward will be decreased. While the strict feasibility setting appears to be important in practice (e.g., we don’t want to break a robot arm), the behavior of the algorithm is somewhat undesired (it may output a mixture of an unsafe policy and extra-safe policy). Is there a way to address this mismatch?\n\n- Do the bounds in [1] or [2] translated to the relaxed or strict feasibility setting? How does the bounds compare with each other?\n", "limitations": "The authors adequately addressed the limitations and potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality. Although similar primal-dual methods are also considered in previous works, this paper provides novel analysis and therefore proves stronger results. The lower bound for the strict feasibility case is interesting and novel.\n\nThe following two related works are missing. In particular, Section 6 of [1] proves $O(\\sqrt{SAT})$ regret for constrained MDPs without generative models, and [2] proves sample complexity bounds.\n \n[1] Yu, Tiancheng, et al. Provably efficient algorithms for multi-objective competitive rl\n\n[2] Miryoosefi, Sobhan, and Chi Jin. A simple reward-free approach to constrained reinforcement learning.\n\n\nQuality. This paper is technically sound. I didn’t read through the appendix but the proofs that I read are morally correct.\n\nClarity. The exposition of the results could be improved:\n-\tThe proof of Theorem 8 looks like a zero-knowledge proof and is hard to follow. The choice of constants are not explicitly stated, and some of the core ideas are hidden in the proof details. The intuition of why strict feasibility setting is harder than relaxed feasibility setting is unclear to me, as well as the idea of the hard instances.\n-\tWhile this paper proves a separation between relaxed and strict feasibility cases, the proof sketch for Theorem 2 & 3 looks very similar except the choice of parameters (e.g., b’, \\epsilon_1). However, the choice of parameters is not justified in the first 9 pages. In particular, it’s unclear why the parameters have to be different without reading the full proof.\n\nSignificance. This paper proves minimax optimal sample complexity for constrained MDPs with generative model, and improves upon previous results. This paper partially answers the question that whether constrained MDPs are harder than unconstrained MDPs --- somewhat surprisingly, constrained MDPs with generatively model are not harder with relaxed feasibility.\nFor the strict feasibility case, the error decomposition (lemma 12) is novel and could be a useful tool to analyze constrained MDPs in different settings. The matching lower bound in this case demonstrates that the strict feasibility setting is strictly harder than the relaxed feasibility setting, which is an interesting result by itself.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "I-j3XjC-5_9", "reviewer": "Reviewer_VP1s", "summary": "This work provides finite-sample analysis for constrained MDPs in a generative model/simulator setting. For the first relaxed feasibility setting, the proposed method improves the prior art sample complexity by $S$ and matches the unconstrained minimax lower bound. For a strict feasibility setting, this work provides the first lower bound and also proposed a method that can match the minimax lower bound.\nEspecially, this work shows that with strict feasibility requirements, CMDPs have intrinsic more challenges than unconstrained MDPs.", "questions": "1. Do the result need the value accuracy gap $\\varepsilon$ to be the same as the small constraint violation in Line 122? From my understanding after reading the proof sketch, they can be different. But the equation (2) may lead to some confusion as they are related and must be the same. If they can be different, using different variable notation may be better.", "limitations": "The author already mentioned the possible extension of this work in the discussion.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Advantages:\n1. For the strict feasibility of CMDP settings, this work is the first one that provides a tight lower bound and also proposes a method with a minimax sample complexity bound, characterizing the difficulty of solving CMDPs theoretically.\n2. Furthermore, in the relaxed feasibility setting, it also improves the prior arts and achieves the minimax lower bound (unconstrained MDPs') sample complexity.\n\nDisadvantages:\n1. The presentation of the work can be polished more by showing more intuition and key technical tools and moving the proofing details to the appendix.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept