A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDP
Authors: Fan Chen
Junyu Zhang
Zaiwen Wen
Venue: NeurIPS 2022 Accept (2022)
Keywords: reinforcement learning theory
offline reinforcement learning
statistical optimality
safe reinforcement learning
primal-dual

Abstract: As an important framework for safe Reinforcement Learning, the Constrained Markov Decision Process (CMDP) has been extensively studied in the recent literature. However, despite the rich results under various on-policy learning settings, there still lacks some essential understanding of the offline CMDP problems, in terms of both the algorithm design and the information theoretic sample complexity lower bound. In this paper, we focus on solving the CMDP problems where only offline data are available. By adopting the concept of the single-policy concentrability coefficient $C^*$, we establish an $\Omega\left(\frac{\min\left\{|\mathcal{S}||\mathcal{A}|,|\mathcal{S}|+I\right\} C^*}{(1-\gamma)^3\epsilon^2}\right)$ sample complexity lower bound for the offline CMDP problem, where $I$ stands for the number of constraints. By introducing a simple but novel deviation control mechanism, we propose a near-optimal primal-dual learning algorithm called DPDL. This algorithm provably guarantees zero constraint violation and its sample complexity matches the above lower bound except for an $\tilde{\mathcal{O}}((1-\gamma)^{-1})$ factor. Comprehensive discussion on how to deal with the unknown constant $C^*$ and the potential asynchronous structure on the offline dataset are also included. 

A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDP
Fan Chen
Junyu Zhang"
School of Mathematics Peking University chernêpku edu.
Department of Industrial Systems Engineering and Management National University of Singapore
junyuzênus.edus edu.sg
Zaiwen Wen
Beijing International Center for Mathematical Research, Center For Machine Learning Research Peking University wenzwêpku. edu...dduccom en
Abstract
As an important framework for safe Reinforcement Learning, the Constrained Markov Decision Process (CMDP) has been extensively studied in the recent liter- ature. However, despite the rich results under various on-policy learning settings, there still lacks some essential understanding of the offline CMDP problems, terms of both the algorithm design and the information theoretic sample complex- ity lower bound. this paper, we focus on solving the CMDP problems where only offline data are available. By adopting the concept of the single-policy con-
centrability coefficient C*,, we establish an ((A)((()_A)))))))))))) sample com- (1-7)922
plexity lower bound for the offline CMDP problem, where / stands for the number of constraints. By introducing a simple but novel deviation control mechanism, we propose near-optimal primal-dual learning algorithm called DPDL. This al- gorithm provably guarantees zero constraint violation and its sample complexity matches the above lower bound except for an Õ((1 - -)) factor. Comprehen- sive discussion on how deal with the unknown constant C* and the potential asynchronous structure on the offline dataset are also included.
Introduction
Reinforcement Learning (RL) is important tool for modeling the real world tasks that involve sequential decision making. Such RL problems are often mathematically described as Markov Decision Process (MDP) that maximizes cumulative sum of rewards. The safe reinforcement learning, on the other hand, not only cares the reward maximization, but also attempts to ensure a reasonable system performance with respect certain safety constraints. Such safety constrained RL problems are often formulated as the Constrained Markov Decision Process (CMDP) M = AS, P. u, Y, Po), where S is finite state space, A is finite action space, 7 (0. is the discount factor, (s' [ss a) stands for the transition probability from s to s' under the action a for v(s, a, 8') E Sx A S, and r S x A [-1, 1] is the reward function, (u, S A [-1, 1)) a set utility functions, Po is the initial state distribution over S. The goal of CMDP is to find
"Corresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

an optimal policy ग to maximize the cumulative reward while satisfying group of constraints:
+00
max J(T) = E
r (5t,
80 ~ po,
+00
S.L. (1) = R
Σ
us (8c: 0t)
2 0, for i [7] (1,2, 13.
etc.]. However, in real world applications such as training physical robots, where safety is an important measure of performance, the real time on-policy interaction with the environment may suffer from the potential damages to the robots. Besides, in many non-simulating environments, the on-policy data collection may also time-consuming. Therefore, it is crucial to design an off-policy algorithm to solve the CDMP problems, where plenty of historical data are already accumulated while real time interac- tions are limited. To our best knowledge, offline CMDP algorithms are rare [2 27 29). and the sample complexity guarantees are limited. In particular, strong uniform concentrability assump- tion is required in 11), and the model-based method [ mainly considers the case an empirical model is known. Thus it is still not clear how to efficiently solve offline CMDPs with model-free approaches, and there lacks essential understanding of the information theoretic lower bound on the sample complexity of the offline CMDP
For the CMDP problem, there has been plenty of on-policy algorithms, see 7 8 20
In this paper, we propose a neeviation-controlle Primal-Dual Learning (DPDL. method to solve problem ( We adopt the primal-dual strategy developed in 16 gorithmic framework while several non-trivial contributions have been made beyond the existing results. Unlike the aforementioned literatures that exclusively rely on the accessibility of gener- ative model, DPDL utilizes the offline data, where the distribution shift difficulties of the offline data is tackled by novel and effective adaptive deviation control mechanism. If the considered CMDP instance has a finite (but potentially unknown) concentrability coefficient, DPDL provably finds policy with Opt)-mptimal reward and zero constraint violation. An information theoretical lower bound on the sample complexity of offline CMDP is also derived in this paper, which indi- cates that our deviation control mechanism achieves minimax optimal complexity dependence on T, S, |A], C
26 35 etc.] as the main al-
Main Contribution. We summarize the contributions in details as follows.
We propose the DPDL algorithm solve the CMDP problem ( Suppose the CMDP in- stance satisfies the Slater's condition and certain prior knowledge on the concentrability coeffi- cient C* is given. DPDL provably finds an c-optimal policy with zero constraint violation using 8 offline samples.
(1-7)+22
We establish information theoretic sample complexity lower bound of min (A)AAA) +/JC" (1-7)-²²
for the offline CMDPs, indicating that DPDL is near optimal up to an Õ(( - 2) factor. The necessity of the Slater's condition for achieving
constraint violation is also established. The sharp dependence on the number of constraints is mainly captured by our careful construction of
the correlated actions.
In order to handle the practical situation where C* is unknown, an adaptive version of DPDL is
designed with the same sample complexity DPDL.
Our analysis of DPDI. also extends to the asynchronous case, where the offline dataset consists of sample trajectory generated by certain behavior policy. In this situation, the sample complexity
of DPDL. is shown to be Ô Canve miinmmn(Ss]) (1-7)²22
Our handling of the correlated gradient estimators with large variance can also be beneficial to other algorithms under the asynchronous setting.
Related Work. Recently, considerable efforts have been devoted to the online learning of CMDP. Under the episodic and tabular setting, several works 20 have achieved the ((V regret and cumulative constraint violation, with different dependence on the episode length H omitted. Under proper assumptions, zero or bounded cumulative constraint violation can be achieved [ [7 In terms of the number of constraints I, MOMA proposed in [34] achieves
an Ô (v min Al/T) convergence both average reward gap and constraint violation.

---

Nevertheless, all the above results adopt the model-based approaches. Except for [4 they either consider the cases where I completely ignore the influence of I in the sample complexity. Therefore, both deriving an efficient model-free method and obtaining the optimal dependence on remain open.
Another approach closely related to our paper is the primal-dual method in RL, see 1111 26 35
etc.J. Given the access a generative model, the model-free primal-dual method developed
achieves an (1- 422 sample complexity to find an e-optimal safe policy. The deviation control
mechanism we develop enables the primal-dual approach to extend beyond the generative model.
Finally, we mention few related works in the offline RL and safe RL. Previous offline RL algo- rithms with sample efficiency guarantees typically assume the uniform concentrubility [12 [8] etc.] or lower bounded minimum visitation Mmin 332 33
etc.]. Recently, under the less restrictive sumption of the single-polig concentrability coefficient C a minimax optimal sample complexity
lower bound of S2( -1-- (1->))²²)
for discounted offline MDPs is derived in [1]. A similar 22(
# [
lower bound also derived for the episodic setting in Under both settings, offline algorithms with Ó ?² sample complexity (with different (1 (1-7)- or H factors omitted) have been dis- covered with either model-based [I5] 21 28 31] or model free approaches [22 30]. In terms of the
offline CMDP problem, the only existing results are [22 27 29 where (29 only provides asymp- totic convergence, [12] relies on much stronger uniform concentrability assumption, and [27] is model based method that potentially suffers an (((C*)²) )2) dependence. Compared to these works, our method is model-free and has an optimal O(C") dependence on the concentrability coefficient.
2
Problem setup
2.1 LP formulation of CMDP problem
For any policy π, the (unnormalized) state-action occupancy measure defined as
to0
v (5
~ x), for V(s,a) ESXA. =al = rt (st s,a =
(2)
Given any occupancy measure v², the policy a that generates v² can be recovered as
v= (s, T(als) Ess (s,
V(s,a) E A.A.
(3)
According to 12 it is well known that the set of all state-action occupancy measures form a poly- is an |5)-dimensional
hedron { R 20 [S
EmEA(I yPPa)' (PPa)r==P)) = } where V. == column vector, is the [S|x| [S) identity matrix, and P. == (P(s'(s,a) sr.s is an |S] x [S] transition matrix, also (26). Therefore, combined with the fact that (mT) (v. and (T) (M7 un),
the CMDP problem (I) can be reformulated as an LP problem with |S] +/ constraints:
max VERISIXIAI
(u,r) S.L.
(I-7Pall
Po. (v, ux) 2 0, Vi E [7].
(4)
BEA
Due to the fundamental theorem of LP, see e.g. solution with most [S] positive entries, which indicates the following proposition.
5 problem (4) has an optimal basic feasible
Proposition 2.1. For the CMDP problem ( with I constraints, there is an optimal policy x" such that |supp(>"")) minin ||| where supp(.) denotes the support of a vector.
This result captures the potential sparse structure of the optimal policy when T is not as large as |S, and is the key to deriving tight complexity dependence on the number of constraints T.
Off-policy learning from demoustration
In this work, we consider the offline CMDP problems where the agent cannot interact with the environment. Instead, the optimization is conducted using fixed offline dataset. To standardize the discussion, we make the following assumption on the offline dataset, see e.g. (21)
3

---

Assumption 2.2 (Independent batch dataset). The batch dataset 'D consists of independent tuples (s, a, ,T, u). such that (s, a) ps, EE [r] = r a), u s, al u,(s, a), and s' P(-)s,a), where is called the reference distribution.
To characterize the distribution shift of an arbitrary occupancy measure 1ath from the reference distri- bution J4, we introduce the following notion of the deviation: D = maxs,0 (1 (1=2))=(s.0) where the p[s,a]
(1 --fator normalizes v" to be distribution. In offline RI., it is natural to assume that the devia- tion D of the optimal policy is finite. That is, the reference distribution μ fully covers supp(r"). Otherwise, no optimality can be guaranteed. Combining the sparse nature of the optimal solution of
I we introduce the following finite concentrability assumption for our problem.
Assumption 2.3. For Val 2 1, denote the vi-deviated policy class as I[(p): == {T: E D(b)) where
|SILA|, D(O):= = V R 20
(1 (1-7)u(s,a) (s)sa)
SV Σ (1-)))(s,)) s SNub 8,0 ((s.a)
max 8,a
(5)
We assume there exists a finite 1b such that some optimal policy x" is contained in 11(b)). Let C' be the minimum of such vb. We call this constant C the (single-policy) concentrabilityy coefficient.
The above assumption includes a sparsity induced constraint as a result of Proposition 2.1 its coun- terpart in the definition of single-policy concentrability of offline MDP (2] is the deterministic optimal policy. The explicit dependence on N in ((b) facilitates the derivation of the information theoretic lower bound as well near-optimal algorithm.
second remark is that if we know any upper bound vi of the coefficient C*, then will be sufficient to only consider the policies in II( When C* is unknown, v control the risk of distribution shift. Consequently, in this paper, we propose to solve the LP formulation 4 with a tighter feasible region introduced by (1)). This will allow to properly control the variance of the off off-policy sampling when some of p(s, a) is extremely small or even zero. We call this strategy deviation control.
2.3 Conservatism toward constraints
We say policy π is safe if it satisfies all constraints T and we say a is e-safe if JT) -c, for Vi E [4]. Most of the existing online CMDP algorithms guarantee (1/VVT) average safeness. To ensure the true safeness (zero constraint violation) in this work, assume the Slater's s condition to hold throughout this paper. In fact, in Section 5 we will show that the Slater's condition is the necessary condition for any offline CMDP algorithm obtain zero constraint violation.
30 Assumption 2.4. There exists > and policy π such that J. (T)) 2 1-y- Vi E [7].
prior knowledge of such a constant yp is assumed throughout our discussion, and we also assume the Slater's s condition holds for IT' = IT(C*). Given Assumption 2.4 we leverage the idea of conser- vative constraints proposed in 4 Namely, instead of (T) 2 O, we consider the conservative con- straints J," (T)) 2 when solving the CMDP problem, where K >> 0 is properly chosen parameter that controls the level of conservatism in the constraints. In order to keep the form of the constraints in problem M we adopt shifted utility function uf defined by uf(ss, (s, a) == u'(s, a) (1 - 7)x for v(s. a) S x A, Vi E [4]. Therefore, J('(T) 2 K is then equivalent to J. (x) 2 0. It can be shown that a properly selected к will facilitate a high probability of preserving zero constraint violation, while only introducing an extra O x) sub-optimality gap in the reward.
3 The Deviation-controlled Primal Dual Learning (DPDL) algorithm
To solve CMDP with offline samples, we transform its IPP formulation 4 to saddle point form
max min C(V, v) = (r,v) Vv (P-)PP)) + (A, Un))
(6)
DED X20,V
where D(1) is defined by 5).
V VRRSS X R are Lagrangian multipliers, and the matrix U, is defined as Ux == ........ .,7] R [ with u² being the shifted utility defined in Section 2.3

---

Given the reference distribution the objective function can be rewritten as an expectation:
v(s,a)
( -VV))) (V(s)- +
-(V,A.D)= = E
[s0o)] +
sompo
(s.a)ru s(MP(()s.))
a(s,a)
If the reference distribution is known, we can directly sample stochastic gradient of L. However, when the reference distribution μ unknown in practice, then the importance sampling weight
p(s,a) is also unknown. To tackle this issue, let já be a proper estimation of the reference distribution p(s,a)
(,, we introduce the weights w(s a) u(s,a)
[[s,a]. and the diagonal matrix W diag (w(s a)). Then
=(s.e) v(s.a) for Vs, a to enable apply change of variables W-1 v, in other words, set [[3,0] μ(s,a)
sampling. From now on, we will focus on the following reweighted problem
min max L (V, X, = L(V, X, Wx), VEV.VEV sEa
where the feasible regions are defined as r(s, a) 8,a a(s.a)
R
20
8 STAA
max
1-7 8,a
Σ x(s,a)
a(sa)
1 1-y
No Σ
a(ssa)
1 - 7
4
8,0
(8)
v:= VERIS 11 S 1-
(1
and
A = A A R
|| -
8
The sets X. V and A are chosen be large enough so that they contain the optimal solution of the problem (6). see detailed discussion in Appendix P Given a sample Ç (No, 8, 0, 8 T; u) ~ Po x D, and point Z (V, X, I), we construct the unbiased gradient estimators for C (-) as
(v: = I., + x(ssa)
A(s,a) (yI..- - I.).
(x:C) = x(s, a) u"
(9)
ju(s, a)
(z:C) + (V)) (ss,
V(s') + (u" A)
Ig.a:
where II, is the dimeennnlll unit vector with the s-th element being one, Isao is the |8| |||- dimensional unit vector with the (s, a)-th element being one, and u the shifted utility vector. Based on these estimators, we propose stochastic mirror descent ascent approach to solve problem 7 as stated in Algorithm [
x(1 -)11 E R' is
The algorithm starts from a feasible solution Z which, for example, can be casily chosen as V 0 NV = Φा x² = || ب S In each iteration, an offline sample Ç is used to construct the unbiased gradient estimators gv. 9 and g" A stochastic mirror descent ascent step (TT) is then used to update the solution Z", where Projy(.) denotes the Euclidean projection to the set V, and KL(Y| ==
E, Y, log 3 Y Y? denotes the generalized KL divergence. Simple closed form solutions
are available to the pt+1 and X++1 updates. By taking the advantage of the special structure of g and the fact that x E X' is feasible, the x²+1 subproblem can be reduced to the root finding of 1-dimensional monotone function, which can be solved efficiently, see details in Appendix [
Finally, it is worth noting that x is the approximate optimal solution to the reweighted problem. And WT will be the approximate solution the original problem (6) before the change of variable.
Therefore, ideally, we should have output the policy (als)) Σ. w(s.a' w(s.aa))((.. "=( which is inacces- sible in practice without knowing the reference distribution μ. In order to overcome such dilemma, we show that by properly constructing the estimated distribution f. the output by Algorithm | will be close enough to the ideal output T...
The sample complexity of DPDL
4.1 Main results of DPDL
For the DPDL algorithm, the convergence and performance guarantee of the output policy are summarized as the following theorem.
5

---

Algorithm 1: Deviaaion--oontrllled Primal-Dual Learning algorithm (DPDL)
input Tolerance >> 0, confidential level >> conservatism level stepsize 7 0,
constants Oiy, OxaO0t Ne. S > 0, and initial feasible solution Z = [VI: A ;= x-).
Obtain Ne samples from D, let N (s, a) be the times that the pair (s, a) appears. Compute
pls, a) = max (No (N(s..).)) .). ((s,a)
(10)
No
for / -o..
Sample Ç. (sl: St, ats S Ti, u,) from Po x D;
Compute stochastic gradients gV (Z'; (²), 9. 5x (Z+; and g22 (Z';
Compute the stochastic mirror descent ascent update
p Projy -y*--1om gvv,
4+1 arg min AEA
-0::A-10-0 as KL (1
(11)
(g x - x²) +
ar KL(x || x4))
arg min xEA
1/t
Compute the average iterate x + Ei= E
ΣI V2 E 1
F(s.o) Compute F(als) Σ., a(s.a') for all (s,a);
output: Policy and the approximate solution
Theorem 4.1. Suppose that Algorithm i runs with ne = vT n = 5ic, as = 1-y V Ing 1 av =
1
1
10
Nr log wo and vb 2 C Then for any fixed E (0, 10(1111)) and T 2
PP
[ST
Oz
Co (1-))))
log (ISIIAAM and is universal constant, the output policy of DPDL satisfies the following with probability at least
where
S (c), and 2, When sb = O(C*), DPDL needs at most δ policy.
J(T²) ((z)
NC (ল-ा)
samples to find a safe O (optinal
Remark 4.2. When the prior knowledge of C is not available, and the selected parameter v < C but the Slater's 's condition for 11(b) still holds, the output policy स of DPDL satisfies that
((T) 2
max Te
((T) - (c) and
(.
2 Capprox: Vi [4].
where G denotes the set of safe policies, and eapprox (1)) [(x') max ((T) in some sense measures the "sub-optimaliry" of the policy class II(b). In case fixed sub-optimality gap given, such difficulty of unknown C also appears in the guarantees provided in previous works
[
21
22
28 30 37/.
simple approach to resolve the difficulty of an unknown C* is discussed later in Section 6
4.2
The analysis of DPDL
We break down the analysis of Theorem 4.1 into the following steps. First of all, we provide proper choice of N₂ and 5 so that ğ is close enough to μ. See proof in Appendix B
Proposition 4.3. Denote e I and let
p(1-))²e. and No 2 2N
p'1-")' log
512N4
6 LA|
Then with probability at least 1 - 6/3, the estimated reference distribution defined by TO satisfies the following properties simultaneously: (1). ple.a)
M(..) < 2, and pass a) 2 s. for all s, a; (2). For any
11(bb). w X; (3), For any E X. [ =||1 s011 7)E..

---

All the rest of our analyses are all conditioning on the success of Proposition 4.3 It is worth noting that in Proposition 4.3 (3) clarifies the validity of constructing the output policy я with æ instead of Wa; (2) explains why the feasible region X' is defined as (); and (1), combined with the carefully specified feasible domains, provides the proper upper bounds on the magnitude and variance of the unbiased gradient estimators in ( A very detailed discussion is provided in Appendix [ In particular, for the (-) estimator, an explicit (AV) dependence has been established for both the magnitude and variance, which plays crucial role in deriving the optimal ( |S| + /)) dependence on [S], |A| and I. Let us define the following gap to measure the performance of the output I w.r.t. problem 7
min Gap 2 = max min Lw (V..,)) VEV,λEA #E VEV,AEA
(v,
(12)
Based on the properly bounded gradient estimators, a high probability bound for Gap(Z) is estab- lished in the following theorem. Its proof detailed in Appendix D
Theorem 4.4. Suppose the constants Tt- QV,, a)2 ag and K. are chosen the same as Theorem 4.1
the output I satisfies Then there is a universal constant such that, as long as T 2 -1-1)1-)
Not
Gap(#) < & with probability least 1 6/3.
Given Theorem 4.4 we finalize the proof of Theorem by properly transforming the bound on Gap(z) to the expected reward gap and the constraint violation on the original CMDP problem ( which is discussed in details in Appendix
4.3 Extension to asynchronous setting
In some situations, an independent dataset that satisfies Assumption 2.2 may not be available. In- stead, the dataset may have the following asynchronous structure.
Assumption 4.5. The asynchronous dataset D Dasyne is a single sample trajectory generated by some behavior policy Ty- Namely, what we observe is a sequence {st, Qt, Fi, uz)121 generated under Tu- We assume the Markov Chain {st, (1) is irreducible, aperiodic and uniformly ergodic, with the stationary distribution μ and the mixing time lmix +00.
The asynchronous data structure introduced here is frequently considered in RI,, for example, the asynchronous Q-learning [14]. However, to best knowledge, this type of offline data has yet been considered under the assumption of a finite single-policy concentrability. In this situation, we set St (s): St, at, Tt, uz) in the DPDL method (Algorithm lb. where of po and (St, ae, St+1, Ft. u,) is the tuple in the t-th time step of the asynchronous dataset. The sample com- plexity of the DPDL Algorithm under Assumption 4.5 established follows.
Theorem 4.6. Under Assumption any fixed (0, 1op- vb 2 C*, and T 2 co 60 1122
4.5 we follow the choice of constants in Theorem 4.1. Then given Nops"
the output policy of DPDL satisfies
the following with probability at least 1 5
J(x)) ( S
and
(T)) 0,Vi [4].
Here = log (T) (I)AIIA) and do is a universal constant. Therefore, when eb = O(C)), DPDL samples to find a safe e e-optimal policy.
needs at most ò
2 NC
The main framework for proving Theorem 4.6 is similar to that in Section thus we present the proof in the Appendix H However, compared the synchronous setting, key difficulty here is that the gradient estimators Ov (Z':G) (x Ge). and 9z (Z': (4) are no longer unbiased, because the samples {S:) are obtained from a sample path. This brings further difficulties in the analysis because the variance of the estimators can be amplified by the correlation between samples.
The basic idea to deal with this difficulty is leverage the mixing property of the uniformly ergodic Markov chain. Take the (-) estimator for example, the bias can be well controlled as long as T' is selected larger than the mixing time bmix of the sample path, which can be illustrated by the following decomposition
G. GZ' (.) V (Z")
(Z' Gr Iz (1) + V. (2 vafu
onder (TT))
gr - (Z (13)
+ Jn (2 (e) E Iz = (t) z
E
zero mean
order ((exp(-T/tmix)
7

---

When t = S2 (tmix), one can bound the bias of (Z() by O (fmix)) with suitably chosen T.
5 Lower Bound of Sample Complexity for Learning CMDP
In this section we will discuss whether the DPDL Algorithm is the near-optimal and whether the Slater's condition (Assumption 2.4) is necessary in achieving zero constraint violation. We answer these questions affirmatively by establishing the following theorems.
Theorem 5.1. Suppose S > 4. A 2 3. I 8, C 2 2, 7 E 1) 221, For any learning algorithm 2, there exists a CMDP M - (S, A, P, (ui)se)) 7: PO) and reference distribution p.. such that the following hold true.
(1) S 4S 1, |A| S A, and the concentrability coefficient C* for M and p. satisfies C* SC
(2) Let &t be the policy output by given N offline samples from μ. and let nt" be the optimal policy, then at least one of the following two inequalities hold true:
min {SA,S+IJC (1-7)8N
(M min
f and Em.ufviolation (t) 2 1,
1-
where violation = E'= (+) and J is the utility w.r.. the constraints J. 2 0, Vi E [4].
For DPDL, the constraint violation is guaranteed to be zero with high probability, then only the first inequality is valid for our method, which indicates an 52(
NC
sample complexity lower bound.
(1-3)=2)
Therefore, the complexity of DPDL is nearly optimal up to an ( factor. Besides the lower bound, we also establish the necessity of the Slater's condition in ensuring zero violation.
C, y be the same as Theorem 5.7 For any algorithm 2. there exists a CMDP Theorem 5.2. Let S, A,C,
M = (S,A,P, (1:) [ 7. Po) with I = 1, |8] < S, TAl S A and reference distribution p. with C* S C, such that EM, a (violation(f)) 2 min ( [1-
where î is the output policy of SC
21 given N samples from μ..
Theorem 5.2 is obtained by utilizing the same idea Theorem Thus we only discuss the derivation of Theorem 5.1 while moving all the details to Appendix
For offline CMDPs, the fixed data distribution μ fully dominates the frequency of exploring the state-action pairs. Therefore, intuitively, the hard CMDP instances will be the ones with a large support supp(v"") that widely spreads across the less frequently visited station-action pairs of μ. Based on this intuition, we design basic block of CMDP presented in Fig.[] which is essentially constrained bandit with 2K + arms. The instance M will be replicas of the basic blocks, plus an extra "null" state 8-1 to control C". In this discussion, we only consider the case where 1 = KS, the more general construction that cover full range of I is presented the appendix.
s
s
10
3
0-0
r=1
4-p
1-4
#11+8 $)
1-p
L-g
L-p P
1-9
1-n
s
1- 9
s
(a) (s} a:)
(b) (s] b.)
(c) (s{ e)
Figure 1: Transition dynamics of the jth replica under different actions, E [K].
State, action and transition. At the states s s/g s6. there is no action to be taken. At each state si. there are 2K + actions 41 by, ... ,ak, bx, e. The transition dynamics of the jth replica under different actions are illustrated in Fig. where the directed ares and the numbers associated with
8

---

them are the transitions and the corresponding probabilities, where 2-y and 2 - 1 are some constants, while s and 8,.j E [-1,1), j parameters be designed.
Constraints and Reward. By carefully selecting the u, u,'s, one can construct a set of 2 constraints that indicate ग. [[a:|s]) (bbbs({) 4 Vi,j. For the reward, we set r(s() = r(s)) ) = 0, view a, bj. and
r(sg) 1, and r(s()) -1, regardless of the actions. At any replica as bandit arms with (cumulative) reward caoly cz and respectively, for some c > 0. When 2
p,==1= one would rather pick e. But when f, 1, due to the constraint T(a:)s{) - I ((b, s v TK T prckick a, and b, with equal probability I will be optimal. In fact, this IK upper bound forces the support of the optimal policy to widely spread across the (i,j)'s where 0, = 1, and the task of learning is essentially determining whether 022- 1 for each (i,
Optimal policy. Based on the above discussion, it is not hard see that the unique optimal policy is T-' (a: = ग -0 (brls()= [= and 7~00 (els)) = 2K 10= =1.
4K
Finally, with the above T and a proper initial distribution Po. the occupancy measure can be explicitly computed and reference distribution μ with concentrability coefficient C S C' can be designed. Moreover, for any policy â. we consider f.. (K(((()))))))))) 1, then
T violation(f; (f;; >² (())(()))))))))()))))) Ol]
[(+; 0) = [J(m -====),) J(:; 0]]
64KS(1 7)
Namely, if ((+) is not close enough to the underlying parameter 6, the policy म will incur a con- siderable reward gap or constraint violation. By setting w min {v [SK-3]C 1
I6(1-7)N 2 to be small enough number, any two CMDP instances with different parameters will be non-distinguishable, given N samples from μ. According to [9] and (24), there exists subset θ c 1JsK such that [0] 2 exp(SK/8), and ||0 0'11, 2 SK for any pair of different 0,0' E.. In other words, there will be at least exp(S /8) CMDP instances with different enough parameters while being non-distinguishable under N samples. Then the rest of the arguments will follow by applying the generalized Fano's inequality 3 A detailed proof is provided in Appendix
2
6 Adaptive deviation-control framework of DPDL
We should notice that in both Theorems 4. and 4.6 it has been explicitly emphasized that prior belief v 2 C is required. Otherwise, both the reward and the constraints will suffer extra loss of eapprox ()). this section, we propose an adaptive deviation-control framework (Algorithm to handle the practical situation where no such prior knowledge is available.
Algorithm 2: The Adaptive-DPDA framework
input : Sub- Sub-optimalitty c, confidence level 8. Initialize 1), default jK = -00, for K = 1,
2 for K 1. do
Call DPDL with k obtain an approximate solution ((K) and the policy π ((K); VERIFY (z, = TRUE then
L Compute ((x(K) as an O(e)-accurate estimator of [[ set J [[](K]))
if -00 < JKK < JK + O(c) then Terminate;
Set 1/K+1 2bp:
output: Policy (K)
At a high-level, Algorithm 2 consists of the following steps.
Verification For the output z of the DPDL, we develop a verification method VERIFY 6) that, with probability at least - 5, returns TRUE only when following two statements hold: (1). The vector // = Wr satisfies II - >Pa) - po = (ee), which essentially checks whether is approximately a valid occupancy measure; (2). The policy स induced by E is safe. At step K, if any one of the two statements does not hold, we immediately know 4/ < C* due to the analysis of Theorem 4.1 Consequently, to double the coefficient vKK+1 2 in the next iteration.

---

Certifying performance improvement When VERIFY (z; e, 8) returns TRUE, then it holds that jo(()) = (=(((()++((e)) where (1( denotes the optimal value of problem 7 with x = O. That is, can estimate (15) with (K) if VERIFY 6) TRUE. As long VERIFY returns TRUE for two consecutive runs, and the performance improvement is small, i.c., Jo(wx) (o(xx-1) = O(e), then Lemma 6.1 guarantees that the safe policy x(*) is O --potimall.
Lemma 6.1. The function jo(-) is strictly increasing in the range di E [1, C*), and jo(b) (
for 2 C For any io of S C holds that
- -6(("")-o(())) jo(b)) - ( / -
Detailed descriptions of VERIFY and AdaD are presented in Appendix G and so does the proof of the following theorem.
Theorem 6.2. Fixed E (0, Torl-))1. E (0,1). Then with probability at least 5, Adaptive-
DPDL stops at step K such that UK S 4C and outputs the safe policy x(() with sub-optimality - VK
gap J(T) - (k)) S 0
) Moreover, there exists a (problem dependent) constant eo(M)
such that, i S co(M), then it must hold that thx E {C*, ,2C*) and n (()) is e-optimal.
Intuitively, the Adaptive-DPDL will quickly terminate within Ollog C*) calls of DPDL, resulting NO
in total samples complexity of Ô
(1-7)+2]
Acknowledgement
Zhang is supported by Ministry of Education, Singapore, grant R-266-000-158-133 Z. Wen is supported in part by the NSFC grant 11831002. F. Chen is supported in part by the elite undergrad- uate training program of School of Mathematical Sciences in Peking University.
References
[1] Mridul Agarwal, Qinbo Bai, and Vaneet Aggarwal. Concave utility reinforcement learning with zero-constraint violations. arXiv preprint (tt::20090053999 2021.
[2] Eitan Altman. Constrained Markov decision processes. PhD thesis, INRIA, 1995.
[3] Bin Yu Assouad. Fano, and le cam. Festschrift for Lucien Le Cam, pages 423-435, 1996.
[4] Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achiev- ing zero constraint violation for constrained reinforcement learning via primal-dual approach. arXiv preprint arXhv:2109.06332, 2021.
[5] Dimitris Bertsimas and John Tsitsiklis. Introduction to linear optimization, volume 6. Athena Scientific Belmont, MA, 1997.
[6] Gong Chen and Mare Teboulle. Convergence analysis of proximal-like minimization algo- rithm using Bregman functions. SIAM Journal on Optimization, 3(3):538-555 543, 1993.
[7] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Prov- ably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligence and Statisties, pages 3304-3312. PMLR, 2021.
(8] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitatio in constrained mdps. arXiv preprint arXiv:2003.02/88, 2020.
2020.
[9] Edgar N Gilbert. A comparison of signalling alphabets. The Bell system technical journal, 31 3):504-522, 1952.
[10] Bai Jiang, Qiang Sun, and Jianqing Fan. Bernstein's inequality for general markov chains. arXiv preprint 10111 2018.
10

---

[11] Angeliki Kamoutsi, Goran Banjac, and John Lygeros. Efficient performance bounds for primal-dual reinforcement learning from demonstrations, International Conference on Ma- chine Learning, pages 5257-5268. PMLR, 2021.
[12] Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In International Conference on Machine Learning, pages 3702-3712. PMLR, 2019.
[13] David Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[14] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asyn- chronous Q-learning: Sharper analysis and variance reductionn Advances in neural information processing systems, 33:7031-7043, 2020.
[15] Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-based offline reinforcement learning. arXiv preprint urXiv:2204.052755 2022.
[16] Yongfeng Li, Mingming Zhao, Weijie Chen, and Zaiwen Wen. stochastic composite aug- mented Lagrangian method for reinforcement learning. arXiv preprint arXiv:2105.09716, 2021.
[17] Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. Advances in Neural Informa- tion Processing Systems, 34, 2021.
[18] Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008
[19] Daniel Paulin. Concentration inequalities for markov chains by marton couplings and spectral methods. Electronic Journal of Probability, 20:1 1-32, 2015.
[20] Shuang Qiu, Xiaohan Wei, Zhuoran Yang. Jieping Ye, and Zhaoran Wang. Upper confidence primal-dual reinforcement learning for emdp with adversarial loss. Advances in Neural Infor- mation Processing Systems, 33:15277-15287, 2020.
[21] Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging of- fline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34, 2021.
[22] Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic Q-learning for offline reinforcement learning: Towards optimal sample complexity. arXiv preprint arXiv:2202. 13890, 2022.
[23] Joel Tropp. Freedman's inequality for matrix martingales. Electronic Communications in Probability, 16:262-270, 2011.
[24] Rom Rubenovich Varshamov. Estimate of the number of signals in error correcting codes. Docklady Akad. Nauk, SSSR, 117:739-741, 1957.
[25] Mengdi Wang. Primal-dual ı learning: Sample complexity and sublinear run time for ergodic markov decision problems. arXiv preprint 17 2017.
[26] Mengdi Wang. Randomized linear programming solves the markov decision problem in nearly linear (sometimes sublinear) time. Mathematics of Operations Reseurch, 45(2):11-566,, 2020.
[27] Runzhe Wu, Yufeng Zhang, Zhuoran Yang, and Zhaoran Wang. Offline constrained multi- objective reinforcement learning via pessimistic dual value iteration. Advances in Neural In- formation Processing Systems, 34, 2021.
[28] Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing safple-efficient offline and online reinforcement learning, Advances in neural information processing systems, 34, 2021.
[29] Haoran Xu, Xianyuan Zhan, and Xiangyu Zhu. Constraints penalized Q-learning for safe offline reinforcement learning. arXiv preprint a7X0v:210..00000, 2021.
11

---

[30] Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. The efficacy of pessimism in asynchronous Q-learning. arXiv preprint arXiv:2203.07568, 2022.
[31] Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems, 34, 2021.
[32] Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. arXiv preprint arXiv:2007.03760, 2020.
[33] Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction. Advances neural information processing systems, 34, 2021.
[34] 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.
[35] Junyu Zhang, Amrit Singh Bedi, Mengdi Wang, and Alec Koppel. Cautious reinforcement learning via distributional risk in the dual domain. IEEE Journal on Selected Areas in Infor- mation Theory, 2(2):611-626, 2021.
12


Reviews:
[{"review_id": "fbYQjkLJrp1", "reviewer": "Reviewer_Gvdm", "summary": "This manuscript investigates offline Constrained Markov Decision Process (CMDP), where on top of optimizing the cumulative reward r one must maintain (in a hard way) a cumulative constraint u to be non-negative. The offline setting uses only the offline data without a generative model. This manuscript proposes Deviation-controlled Primal-Dual Learning (DPDL), an algorithm that uses the saddle point formulation of MDP and a mirror descent-like update. When the concentrability coefficient of a CMDP is finite, assuming the Slater's condition, the algorithm guarantees the convergence and a proved sample complexity. An information-theoretic lower bound validates the optimality of this sample complexity up to a 1/(1-gamma) factor.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper improves previous works on CMDP by removing the generative model. Without a generative model, it is necessary to have the Slater's condition to satisfy the constraint. With the Slater's condition, the authors show a close-to-matching pair of upper and lower bounds of sample complexity (need concentrability assumption). The argument seems natural and the improvement is clear.\n\nI would question the relevance of the manuscript as the assumptions needed to conclude the sample complexity are heavy. Despite one of them is necessary (Slater), it is not clear if this particular setting is worth investigating.\n\nI also suggest the authors to highlight the technical contributions, if any.", "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": "djNyoYt-S2H", "reviewer": "Reviewer_73m4", "summary": "This paper studies the offline CMDP through the linear programming (LP) formulation and the primal-dual based method. An upper bound is proved under the notion of the concentrability coefficient in offline RL literature. A lower bound is established to demonstrate the near-optimality of the proposed upper bound. Finally, an adaptive algorithm is proposed to address the situation when the optimal concentrability coefficient is unknown.", "questions": "(1) Could the authors discuss the potential of relaxing the assumption of a finite concentrability coefficient?\n\n(2) Could authors discuss the technical challenges and contributions of this paper compared with some key references like [14, 30] and [23]?\n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(1) The paper is well-written and the presentation is very clear.\n\n(2) Offline/off-policy CMDP is an important problem and there are not as many offline/off-policy CMDP in the literature as for online CMDP.\n\n(3) The theoretical results are solid. Both the upper bound and lower bound are provided, and the dependencies on the key parameters are very clear. In addition, an adaptive algorithm is proposed to address the situation when the optimal concentrability coefficient is unknown, without the optimality sacrifice.\n\nWeaknesses:\n\n(1) The assumption of having an offline dataset with a finite concentrability coefficient seems to be too strong in practice. Most of time, we would only have an offline dataset that does not well covers all state-action pairs.\n\n(2) The LP-based approach is very restrictive and not scalable. This further restricts the application of this work to the practical implementations. \n\n(3) There are some other published works in offline CMDP that the author may need to compare. For example:\n\nWu, Runzhe, et al. \"Offline Constrained Multi-Objective Reinforcement Learning via Pessimistic Dual Value Iteration.\" Advances in Neural Information Processing Systems 34 (2021): 25439-25451.\n\nXu, Haoran, Xianyuan Zhan, and Xiangyu Zhu. \"Constraints penalized q-learning for safe offline reinforcement learning.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 8. 2022.\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": {}}, {"review_id": "bDJ2zuJgfj3", "reviewer": "Reviewer_EXgi", "summary": "This paper proposes a model-free off-policy reinforcement learning algorithm DPDL that aims to solve the constrained MDP (CMDP) problems given an offline static dataset, and also provides an information theoretic lower bound on the sample complexity in the offline CMDP setting. DPDL adopts the primal-dual approach and addresses the distribution shift challenge in the offline setting via an adaptive deviation control mechanism. \n", "questions": "A large part of the analysis in this current version replies on an assumption that we know a reference distribution, while we actually don't have an access to such a distribution. Although the paper proposed to use an estimated distribution instead, this current does not provide a principled way to construct such a distribution estimation. \n\n", "limitations": "As mentioned in the strengths and weaknesses section, some of the concerns include a lack of experiments that can demonstrate the practice effectiveness of the proposed DPDL algorithm as well as principled ways to derive a practical algorithms based on the theoretical analysis. ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "An innovative aspect of this work is that it considers a combination of the offline reinforcement learning (RL) and safe RL formulated as a constrained MDP. Currently, there are limited existing work on this specific combination, while recent exploration on offline RL and safe RL separately are extensive. The paper could be further improved if the authors would elaborate on the factors that motivate the authors to combine the two settings from both theoretic and practical perspectives. \n\nIn addition, while this paper analyzed the algorithm theoretically, it remains unclear whether it would be effective in solving real-world problems due to a number of issues. Towards this end, experiment results should be conducted to address this issue.  \n\n\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": {}}, {"review_id": "W6d4iwZfGAk", "reviewer": "Reviewer_YGXW", "summary": "The paper studies the offline reinforcement learning in the framework of constrained Markov decision processes. The authors propose an offline primal-dual algorithm, prove near-optimal sample complexity under different assumptions on datasets, and propose an adaptive algorithm without prior knowledge on concentrability coefficient. ", "questions": "- Notation $I$ is abused in Section 2.1.\n\n- line 103: what is the sparse nature of optimal policy? LP only works for occupancy measures, not policy. \n\n- Can you explain how to determine $C^*$ in Assumption 2.3?\n\n- Does saddle points always exist for (6) or (7)? How does constraints (8) work for (7)?  This constraint set looks a strong restriction.\n\n- How to compute $\\mu(s,a)/\\hat \\mu(s,a)$ for degenerate $\\hat \\mu(s,a)$ when finite concentrability is absent? An issue occurs in (9) also.\n\n- How to compute $KL(\\lambda \\Vert \\lambda^t)$ on $\\Lambda$?\n\n", "limitations": "No, for example how to mitigate potential bias in offline data is not discussed. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Originality\n\n- The proposed offline primal-dual algorithm is new in offline constrained reinforcement learning. \n\n- The sample complexity matches a lower bound except for the dependence on the discount factor. \n\n## Quality & Clarity\n\n- Main results of the paper has been delivered well, except for a few concepts.\n\n- All claims are supported by proofs, although I didn't check correctness. \n\n## Significance\n\n- The proposed offline primal-dual algorithm takes either independent batch dataset or single trajectory sequence, which are two important settings in offline reinforcement learning.\n\n- The optimality of sample complexity is studied by establishing lower bound. \n\n- An adaptive implementation of proposed algorithm is useful for practice due to the absence of prior knowledge on concentrability coefficient.", "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": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept