Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process
Authors: Jiashuo Jiang
Yinyu Ye
Venue: NeurIPS 2024 poster (2024)
Keywords: constrained MDP
reinforcement learning
online linear programming
Primary area: learning_theory

Abstract: We consider the reinforcement learning problem for the constrained Markov decision process (CMDP), which plays a central role in satisfying safety or resource constraints in sequential learning and decision-making. In this problem, we are given finite resources and a MDP with unknown transition probabilities. At each stage, we take an action, collecting a reward and consuming some resources, all assumed to be unknown and need to be learned over time. In this work, we take the first step towards deriving optimal problem-dependent guarantees for the CMDP problems. We derive a logarithmic regret bound, which translates into a $O(\frac{1}{\Delta\cdot\epsilon}\cdot\log^2(1/\epsilon))$ sample complexity bound, with $\Delta$ being a problem-dependent parameter, yet independent of $\epsilon$. Our sample complexity bound improves upon the state-of-art $O(1/\epsilon^2)$ sample complexity for CMDP problems established in the previous literature, in terms of the dependency on $\epsilon$. To achieve this advance, we develop a new framework for analyzing CMDP problems. To be specific, our algorithm operates in the primal space and we resolve the primal LP for the CMDP problem at each period in an online manner, with \textit{adaptive} remaining resource capacities. The key elements of our algorithm are: i) a characterization of the instance hardness via LP basis, ii) an eliminating procedure that identifies one optimal basis of the primal LP, and; iii) a resolving procedure that is adaptive to the remaining resources and sticks to the characterized optimal basis.

Achieving Õ(1/E) Sample Complexity for Constrained Markov Decision Process
Jiashuo Jiang
Department of Industrial Engineering & Decision Analytics Hong Kong University of Science and Technology Hong Kong, China pajiangoust. hk
Yinyu Ye
Department of Management Science & Engineering Institue of Computational Mathematics and Engineering Stanford University
California, US yyye@stanford. edu
Abstract
We consider the reinforcement learning problem for the constrained Markov deci- sion process (CMDP), which plays central role in satisfying safety resource constraints in sequential learning and docision-making In this problem, we are given finite resources and a MDP with unknown transition probabilities. At each stage, we take an action, collecting reward and consuming some resources, all assumed to be unknown and need to be learned over time. In this work, we take the first step towards deriving optimal problem-dependent guarantees for the CMDP problems. We derive logarithmic regret bound, which translates into 0 log (1/=)) sample complexity bound, with A being parameter, yet independent of Our sample complexity bound improves upon the state-of-art O(1/e²) sample complexity for CMDP problems established in the previous literature, terms of the dependency on e. To achieve this advance, develop
framework for analyzing CMDP problems. To be specific, algorithm operates in the primal space and we resolve the primal LP for the CMDP problem at each period in online manner, with adaptive remaining resource capacities. The key elements instance hardness via LP basis, ii) eliminating procedure that identifies optimal basis of the primal LP, and; iii) a resolving procedure that adaptive to the remaining resources and sticks the characterized optimal basis.
our algorithm are: i) a characterization
the
1 Introduction
Reinforcement learning (RL) is pivotal in the realm of dynamic decision decision-making under uncertainty, where the objective is to maximize total reward through ongoing interaction with and learning from an enigmatic environment. Markov Decision Processes (MDPs) are a prevalent framework for encapsulating environmental dynamics. MDPs have been instrumental in various domains, such as video gaming [52], robotics [41], recommender systems [57], inventory control [11], and beyond. Yet, they fall short in accommodating additional constraints that may influence the formulation of the optimal policy and the decision-maked e's engagement with the uncertain environment. Often, in MDP applications, there are stringent constraints on utilities or costs, emanating from like safe
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

autonomous driving [22], robotics [56], revenue management [33] and financial management [62]. These constraints might also symbolize limitations on resources within resource allocation applica- tions. Constrained MDPs (CMDPs), as introduced in [4], enhance MDPs to factor in constraints affecting long-term policy results. In CMDPs, the decision-make aims to optimize cumulative rewards while adhering to these constraints. Our paper focuses on CMDPs, and we aim to develop efficient algorithmic solutions.
The significance of RL in CMDP contexts has garnered substantial attention in recent years. A variety of methods for tackling CMDPs have been developed, including the primal-dual technique [21, 49, 12, 69, 18, 45, 25, 26]. which leverages the Lagrangian dual of CMDPs and implements an online learning strategy for the iterative update of dual variables. Other methods encompass constrained optimization [1, 61], the Lyаpunov technique [14], among others. Previous research has established minimax bounds for CMDPs, representing the optimal regret that can be achieved for the most challenging problem within a specific class of problems. Nonetheless, these minimax regret bounds and worst-case scenarios can be overly conservative, leading to disconnect between theoretical guarantees and practical performance for specific problem instances. A more tailored approach is warranted-one that ensures great performance on every single problem instance and furnishes problem-dependen guarantees. Our research takes the first step towards deriving optimal problem-dependent guarantees for CMDP problems.
1.1 Preliminaries
We consider CMDP problem with finite set of states S = (1,2....,18)) and finite set of actions A [1.2..... [l). We denote by 7 10. a discount factor. We also denote by P: x A - D(S) the probability transition kernel of the CMDP, where D(S) denotes a probability measure over the state space S. Then, P(s'|s, a) denotes the probability of transiting from state to
state s' when the action a is executed. The initial distribution over the states of the CMDP is denoted by in-
There is stochaastic reward function r S - Dío, 1] and K stochastic cost functions Ck : S A + DIO, for each & E [K]. We also denote by f(s, a) = B|r(s, a)] for each (s, a) and č(s, = B[ca (s, a)] for each (s, a). For any Markovian policy т, where the action of x depends only on the current state and the action of ı allowed to be randomized, we denote by V,(TT, f1 the infinite horizon discounted reward of the policy æ, with the formulation of VT given below:
V₁ VI(TT, = E Σ rt
r(se, ae) P1
where (st, at) is generated according to the policy ir and the transition kernel P with the initial state distribution nr. For each & E [K]. the infinite horizon discounted cost of the policy is denoted by (T,TT, and the following constraint needs to be satisfied by the policy n,
VW m1) = E Σ 7'
cu (St, at) mn S aus, Vk E [K].
(2)
To solve the CMDP problem, we aim to find an optimal Markovian policy, denoted by x², that maximizes the reward in (1) while satisfying the cost constraint (2) for each & E [K], with og
0, being a pre-specified value for each k E [K]. Importantly, we assume that the reward
function r. the cost functions {= and the transition kernel P, are all unknown to the decision maker. Our goal is to obtain a policy π that approximates the optimal policy πT with as few samples as possible. We now describe the sampling procedure and present the performance measure of our policy. We assume the existence of a stylized generative model M, as studied in [39, 38, 44]. The model M satisfies the following condition.
Assumption 1.1 For each state and action pair a), we can query the model M to obtain an observation of rs,, a), es (8(8,)) for each [K), and the new state s' E S, where the transition from to s' follows the probability kernel P(s'|8,,0 (8,0) independently.
Note that reinforcement learning for CMDP problems, querying the generative model M can be costly. Therefore, it is desirable to query the model M as less as possible, while guaranteeing the

---

near optimality of the approximate policy. To this end, we use sample complexity as the measure of the performance of our policy. For any E, we aim to find an e-aceurate policy π such that
VT(TT, mn) V (n) Se e and (I(T,, ork S e, vk [K],
with as few samples as possible.
1.2 Our Main Results and Contributions
The main result of our research is the introduction of novel algorithm that promises 0 (1/e)) sample complexity bound, where is a positive constant that characterizes the gap between the optimal policy and the sub-optimal ones. Note that the state-of-the-art sample complexity bound under the worst-case scenarios is ((1/=²), which has been established in a series of work [68, 37, 21]. Though the (L1/E) better iteration complexity has been achieved in [45, 50, 74, 26), it comes with a sample complexity bound no better than (1)==)) Our algorithm enjoys a sample complexity bound that has better dependency in terms of To achieve this improved result, develop several new elements listed below.
we develop new characterizations of the problem instance hardness for CMDP problems. Note that a key component for achieving instance-dependent bounds is to characterize the "hardness" of the underlying problem instance. That is, we need to identify a positive gap to separate the optimal policy from the sub-optimal policies for a particular problem instance. The importance of identifying such gap has been demonstrated in instance-optimal learning for multi-arm-bande problems (e.g. [42]) and reinforcement learning problems (c.g. [6]). among others. For CMDP, identifying such gap is non-trivial because the optimal policies for CMDP are randomized policies [4]. Then, the policies can be represented by distributions over the action set and the sub-optimal policies can be arbitrarily close to the optimal policy long as the corresponding sub-optimal distributions converge to the optimal one. To tackle this problem, we show that the feasible region for the policies can be represented as a polytope and we only need to focus on the corner points of this polytope to find an optimal policy. Therefore, the hardness can simply be characterized as the distance between the optimal corner point and the sub-optimal corner point, as illustrated in detail in Section 2. This is the first characterization of problem instance hardness for CMDP problems.
Contribution 1:
Contribution 2: we devise new algorithmic framework to analyze CMDP problems, inspired by the online packing/linear programming (LP) literature [3, 40, 47, 46]. Specifically, we utilize a linear programming reformulation of the CMDP problem, where policies are delineated via occupancy measures [4]. The optimal policy emerges from the LP's solution; however, the indeterminate parameters mean the LP cannot be solved directly but must be approached online
obtain more samples from the generative model. Each generative model query leads to solving an empirical LP with accrued samples, and our final policy is derived from averaging these solutions-an approach akin to the methodology in online LP. A critical feature of our algorithm is the adaptiveness of the LP constraints' right-hand side the input samples, technique demonstrated achieve logarithmic regret in online LP literature, which we now apply to CMDP problems.
Contribution 3: extend our contributions to the online LP literature. Note that after adopting the LP reformulation, the corner points of the feasible region for policies can be represented by the basis of the LP. Separating the optimal policy from the others is equivalent to identifying one optimal basis of the LP. We utilize an approach that lexicographically restricts one variable to zero and tests whether the LP value has changed. We show that this approach systematically pinpoints a particular optimal LP basis with a high probability. Then, we develop a resolving procedure that capitalizes on the structure of the identified optimal basis, which involves only the non-zero basic variables and the active constraints. This is a new approach of deriving problem-dependent bound for online I.P.
Other related literature. Troblem-dependee RL literature, where a series of work [72, 59, 54, 23, 17, 66, 65, 71, 20] establishes the lNg(N) regret bound or the O(k 11) sample complexity, with x being a problem-dependen constant. Our approach can also be directly applied to the RL problems. Moreover, our approach can handle long-term constraints and can deal with oblti-objective (safe) RL problems.
guarantees have been considered extensively in the
our work presents a new algorithm for safe RL problems. We adopt an occupancy measure represen- tation of the optimal and obtain an IP to work with, which is similar to the previous work. However, our algorithm resolves an IP and operates in the primal space, which is fundamentally different from the previous work that adopts a primal-dual update (e.g. [60]. [19]. [73], [8], [53]). There is also
3

---

work developing primal-bace based algorithms, for example ([51], [13], [15], [16], [70]). Our algorithm completely different from the previous work and we obtain new results. The result that we are able to obtain an instance-dependent ((1/c) sample complexity the first time in the literature, which improves upon the O(1/c") worst-case sample complexity established in the previous work. Though the constrained optimization approach and the Lyapunov approach have also been developed for CMDP problems, they do not enjoy a theoretical guarantee. In comparison to the literature, we develop a new primal-based algorithm and achieve the first instance-dependent sample complexity for CMDP problems.
Our new primal-bused algorithm motivated from the literature of online linear programming [3, 40, 47] and bandits with knapsack problems (c.g. [46], [48]). In these problems, the optimal policy can be written an LP and we need to develop an online policy solve this LP sequentially, Note that a prevalent strategy is to resolve the LP adaptive to the remaining resources, which has been developed in long line of research on various applications, for example [31], [32], [5], [36],
[64], [35] and [10]. We make the innovation of resolving the LP while sticking to the identified optimal basis, which distinguishes our algorithm from the previous ones in online LP. Note that the online LP techniques has also been extended to handle non-stationarity, for example in [9], [34]. It an interesting future topic to explore whether our algorithm can be extended to non-stationary environment.
2 LP Reformulation
The infinite horizon discounted setting described in Section 1.1 admits a linear programming refor- mulation. To be specific, due to the existence of the constraints, the optimal policy of a CMDP can be randomized policies (e.g. [4]), where it is optimal to take a stochastic action given the current state. Therefore, it is convenient to represent policy through the occupation measure, which gives us the desired linear programming reformulations of the CMDP problems.
For the infinite horizon discounted problem, the occupancy measure is defined as ga (s. a) for any state 8, action a, and policy т. Note that gr (s, a) represents the total expected discounted time spent on the state-action pair (s, a). under policy multiplied by 1 7. Then, following [4], the optimal policy (and the optimal occupancy measure) can be obtained from the following linear programming.
Ilaf
max
Σ
Σ
a(s.a) a(s,a)
(4a)
SES aEA
s.t. Σ
Σ
Ck(s, a) q(s, a) I an
Ak E [K] (4b)
#ES aEA
ΣV Σ
((s.a)) (6..0' y P(s|s', = = (1- (1(s)
Aa E (4c)
*'ES <ES (ss, a) 2
A8E E (4d)
where da.s' 11 s' and μn (s) denotes the probability for the first state be realized s E S following the initial distribution pr, Note that for an optimal solution {q" (s, Jxs to (4), the corresponding optimal policy nr" will be
(s, Eweat(s,
if Σ a')
P(r = a)
a'EA
(5)
1/IAI.
if " = 0,
a'EA
where n² (s) denotes the probability for the policy n" to take the action E A given the state E S. In fact, when En'e 10 a') 0, we can take an arbitrary action. what follows, we rely on the linear programming formulation (4) to derive our results.

---

optimal point
The soparation BMp 4
Figure 1: A graph illustration of the hardness characterization via LP basis, where the shaded area denotes the feasible region for the policies.
2.1 Characterization of Instance Hardness
We now rewrite the LP (4) into the following standard formulation to proceed with our illustration.
V max
+ q
s.t.
Cq S
Bq μ
2 0.
Note that one crucial step for achieving -ebbemmed bounds is characterize the hardness of the underlying problem instance and define gap that separates the optimal policies from the others. For multi-arm- bandit problem, the characterization of the hardness can be the gap between the optimal arm and the best sub-optima arm (e.g. [42]). For reinforcement learning problem, characterization of the hardness can also be the gap between the optimal policy and the best sub-optimal policy (e.g. [6]). As long as this separation gap is positive constant, denoted by A, separating the optimal policy from the others with a probability at least e would require samples at most A log( (/ee,, which finally implies the instance-optimal sample complexity bound.
For CMDP problem, characterizing the hardness of the problem instance can be hard. Based on LP (6), we know that feasible policy corresponds to a feasible solution and the sub-optimal solution can be arbitrarily close the optimal solution since the feasible set "continuous". Therefore, there is no direct way to identify a positive gap between the optimal policies and the sub-optimal ones. However, from standard LP theory, we know that one corner point of the feasible region must be one optimal solution. Therefore, we can simply focus on the corner points when solving LP (6) and we define the gap as the distance between the optimal corner point and the sub-optimal corner point, as illustrated in Figure 1. As we will show later, the I.P reformulation (6) and such characterization of hardness via corner points will inspire our entire approach.
Since the problem hardness is characterized via corner points, it is essential to provide further characterization of the corner points. Note that in LP theory, the corner point is called basic solution and can be represented by LP basis, which involves the set of basic variables that are allowed to be non-zero, and the set of active constraints that are binding under the corresponding basic solution. Our next lemma follows from standard LP theory, where the proof is provided in the appendix for completeness.
Lemma 2.1 Denote by b the number of rows in the matrix B. Then, there exists a subset J C [K] with K' = -- and an optimal solution q" LP (6) such that there are b + K' variables in are non-zero. Moreover, we denote by I" the index set of the non-zero element q" Then, the optimal solution q² can be uniquely determined the solution the linear system
C(T I' II' =.
(7a)
B(:,I") μ.
(7b)
qI=c O.
(7c)
with T being the complementary set of the index set I
Remark. Note that the minimax lower bound ((1/c²) has been established in previous work [7, 63]. However, this does not contradict with our Ô(1/e) sample complexity after we introduce the instance
5

---

hardness measure A. To be specific, for a problem instance I, we can denote by S(I,e) c) the number of samples needed to construct an e-optimal policy. Then the worst-case lower bound implies that max, e(T, ( (1)))). However, if we do not consider the worst-case guarantee, i.e., if we do not maximize over the problem instance T, then we can characterize an instance-dependent constant (T) (independent of c) such that S(T, <) A(7)/e polylog(1/c) (c)).. When the problem instance is favorable such that the constant (1) smaller than 1/E, our bound strictly improves upon the worst-case bound.
Overview of our approach: the first part, we aim to identify the optimal basis and J. In this way, we identify the optimal corner point to look at. The detailed procedure is described in Section 3. In the second part, we learn the optimal solution given the optimal basis we have identified. which finally gives us near-optimal policy with the desired sample complexity bound. The detailed procedure is described Section 4.
Construct Estimates and Identify Optimal Basis
We describe how to construct estimates for LP (6). To this end, for round No. denote by FNa the filtration of all the information collected up to round No. Then, we denote by CNo (resp. BNx)) ) an estimate of the matrix C' (resp. B), constructed using the information in the set FNo- We also denote by FNo and estimate of f constructed from the information in the set FNo- To be specific, we define
ENo (s. Cn, a) EN cf and PNo (5'18,))) No
ENO (8.0)))
(8, a)
No
No
(8)
where (s, a) denotes the n-th observation of the reward, and (s a) denotes the n-th observation of the k-th cost, and ss a) denotes the n-th observation of the state transition for the state-action pair (s, a), for E [No]. Then, similar to [21], we can use the following L.P obtain an estimate of V (6).
VNO = max (FNa)
s.t.
CNo S a + ANo
Bi S μ + ANo
BN q 2 μ ANO
920, 0,
with AN, being a parameter that we specify later. To bound the estimation gap between VN, and V, is useful to bound the optimal dual solution to (6). To this end, we adopt the approach in [29, 55) that utilizes Slater's condition, which is imposed as an assumption below.
Assumption 3.1 There exists policy गे such that all the resource constraints are satisfied strictly. In other words, there exists occupancy measure q such that Bq = I and Cq < a. In fact, for each state s S, there exists null action that consumes no resource.
The Slater point q can be set as the policy that takes the null action given each state. The estimation error will be related to the gap between the Slater point g and the optimal point q" We then define the lower gap as
Gap, E) 2 V VNo
(10)
and the upper gap as
Gap,(No. 2 VN.
(11)
with both inequalities (10) and (11) hold with probability at least E.
3.1 Bound the Estimation Gap
We denote by Rad(No.
Following the standard Hoeffding's 's inequality, we know that N, (s, a) - (s, a)). and [Pv, (s') s, a) - P(s'|s, a)) are all upper bounded We can simply set
12/(2/E)
2Nr
FN, (s, - f(s, a)), 1 by Rad(No, e) with probability at least
Gap, (No. s) (N)(No.e)
(12)

---

and
Gapz(NNo. 2Rad(No, minketk](an] We have the following result, where the proof is relegated to appendix.
(I (1+ [5]
Rad (No, 8) minke[K] [k]
|8| [)
1-7)
(13)
Lemma 3.2 As long ANo Rad(NNo,)) E), the following inequality
V S VN, + Gap,(No, V + Gap, (No, e) + Gapy(No,e).
(14)
holds with probability least (K| || [S] E, where Gap, (No, E) defined in (12) and Gapz(No, is defined in (13).
3.2 Characterize One Optimal Basis
We now describe how to identify optimal basis of the LP (6) as required in Lemma 2.1, by sequentially discarding the sub-optimal actions and the redundant constraints. The formal algorithm to identify such non-zero elements and the constraints is given in Algorithm 1.
Algorithm Algorithm for identifying one optimal basis
1: Input: the historical sample set FNg that contains No samples for each (s,a) E A.
2: Compute the value of VN, as in (9).
3: Initialize I to be the whole index set that contains every column index of matrix B in (6) and
-= [K].
4: for i 1 do
5: Let =
6: Compute the value of Vr, as in (15).
7: If IV VNOl (Naa E) + 2Gap>(No,e). then set I T.
8:
end for
9:
for k == do
10: Let
Compute the value of Dualy N,N, as in (18).
If [V.. Du & 2Gap, eNo,e) (Gap2(NN,8)) then set set =
13: end for
14:
Output: the set of indexes I and J.
We now explain the intuition why Algorithm works. Denote by q" an optimal solution to LP (6). We describe how to identify the non-zero elements q" and how identify the constraints such that the values of the non-zero elements of q" can be uniquely determined by the corresponding linear equation. For each i-th element of q", we compare the value V (6) against V with an additional constraint that = 0. If the two values are different, we identify a non-zero element. To this end, for an index set I, we define an LP, well as its estimate, as follows.
Vi = max
i 9
VI,No max (FN,) 9
s.t.
Cq < a
s.t.
ON.9 S + ANo
Bq μ
BN. q 1l S ANo
(15)
4
dr-
2 0.
2 0.
know that Ie contains non-zero basic variable. The steps 4-8 in Algorithm reflect this point. Starting from Z denoting the whole index set, we sequentially delete one element (denoting (s,a) in the infinite horizon discounted problem) from the set Z. Once we detected that V Vzy(1 >> O, we know that is non-zero basic variable and add back into the I. In this way, we can classify all the basic variables into the set Z. However, since we do not know the exact value of V and Vz, we use the estimates and compare the value of VN, and VI,No- For this comparison to be valid, the estimation error has to be smaller than the intrinsic gap between V and Vz. We define a constant
where Ie denotes the complementary set of I. Note that Vf - Vz
min(V VT V- Vx 00
(16)
7

---

and we need No to be large enough such that the estimation gap is smaller than A1/2.
To find the corresponding active constraints, we consider the dual program of Vz, where I is determined steps 4-8 Algorithm 1, and similarly, we test which dual variable can be set to 0 without influencing the dual objective value. For dual variable index subset J [K], we consider the dual program as follows.
Du min a a'y+ 1 (C(:: y + (B(:I))) Az
(17a)
(17b)
y5 =0 y 2 0, -0,
(17c)
(17d)
where === =K]NJ The estimate of D,al J,T, can be obtained from the estimate of its dual, which given below.
=
Dual J.I,No = VJ,I,No = max (FNo)*
(18a)
s.t. (N, S. a ANo
(18b)
|BN 9
ma & ANo
(18c)
91 =0
(18d)
q 2 0,
(18e)
Similarly, we compare the value of Dualz, where Dualz Dual with J = [K], and Dual I- However, we can only compare the value of their estimates Dualz,N, and Dual J.I.No To this end, we define a constant
2 min ( Dualz Dualy, JC(K)
Dualy 0}.
(19)
For the comparison be valid, we need No to be large enough such that the estimation error smaller than 22/2. In this way, we identify the linearly independent binding constraints corresponding to q". described in steps 9-13 of Algorithm I.
4 Our Final Algorithm
We now describe our formal algorithm. From the output Algorithm 1, we characterize one optimal solution. If the sample size is used in Algorithm denote by I, and Jn the output of Algorithm I. To be specific, we have 47g = and the non-zero elements 9 can be given as the solution to
InJ,,
4i, = TT,T..
(20)
Bl:,In)
(1 7)
However, in practice, both the matrices C(J,, In) and B(:, In) are unknown. We aim to use the samples to learn the matrices C(T,, Iw,) and B(;,I,) such that the Fz can also be determined. The steps 3-8 in Algorithm is to use Algorithm
Our formal algorithm given in Algorithm a subroutine to identify the set I and J that satisfy the conditions in Theorem 2.1. We can show that as long as n 2 Ng. where NY is threshold that depends on the problem parameters, Algorithm correctly obtains the set I and J satisfying the conditions in Theorem 2.1. Therefore, we exponentially increase the value of as input to Algorithm to reach N²-
A crucial element in Algorithm 2 (step 10) is that we adaptively update the value of a J._. and (²((s) in (22) and (23). We then the updated a",, and y²'(' to obtain the value of 9h in (21). Such an algorithmic design follows the resolving idea from online LP achieve problem-dependent bound. In step 11, we further project q to the set {q 2 0 //q/l < 2} to obtain qu+h, This prevents q" from behaving ill when is not large and the estimates of C(J., I,,) and B.,, are not accurate enough. We can show that when n is large enough, q automatically belongs to the set {q 0: ||q]] 2).
5 Theoretical Analysis
In this section, we conduct our theoretical analysis. The analysis can be divided into two parts. In the first part, show that Algorithm can successfully help us identify optimal basis to work

---

Algorithm 2 The Adaptive-resolving Algorithm
Input: the number samples N for each (s,a) ESx A. 2: Initialize F1 = 0. a N a and μ N N.
3: for 1,... .N do
4: if 2 for an integer m then
5: Obtain the output In and Jn from Algorithm with the imput F.
6: else
7:
set I, I and In = Jn-1-
8:
end if
9:
Construct estimates C" (Jnn, and (;, using the sample set Fu.
10:
Construct solution q" such that 07c 0 and Fz. is the solution to
Jn
O"h In, (I,Inn)
N
+
F =
(21)
N
11:
Project q"h to the set {q: ||q/| s 2} to obtain q".
12:
For each (s, a) In S x A. query the model M to obtain sample of the reward r"(s, a) and the costs cf )) for each & E In C [K], as well as the state transition s" (s,,a)..
13:
Update Fu+1 FnUff" (s, (s(,,) a), s"(s,, a), V(s,o) E x A, E [K]}.
14:
Denote by (s, = (c) and do the update:
a+1 Jn
a² (s
Σ
(22)
15:
Do the update:
1 (5) = (²
Σ (s) (60 71 ( (1==(a)))) Vs' E S.
(23)
(s,a)eZ
where 1 (s'=s" (s(a) is an indicator function of whether the state transition (s a) equals s end for 17: We define qa such that o.x = and
ofx
= - E
Li
We then define policy #
q (s
if
Σ (s, > 0
(s,
P(# (s) a)
a'E.A
(24)
1/1A1.
Σ
qN a') 0.
a'EA
Output: policy N
with. In the second part, we show how to learn the optimal distribution over the optimal basis we have identified.
We now present the theorem showing that Algorithm indeed helps us identify one optimal basis with high probability. In practice, the value of s will be to 1/N in the following theorem.
Theorem 5.1 For any e > 0, as long as No satisfies the condition
2Gap, (No, e) + 2Gap2 S min(A1, A2)
(25)
the outputs IN and INK of Algorithm satisfy the conditions described in Lemma 2.1 with probability at least 1 - (K| |S() Moreover, the sets I, and Jn will be common for any n. 2 No satisfying (25), which we denote by I" and J
An important problem parameter related to I' and J can be described as follows. Define
CCT*
A"
(26)
B(:II*)

---

We then denote by ( the eigenvalues of the matrix A We define or as
min (10)((4)))) -os.. (A*)))
(27)
From the non-singularity of the matrix A", we know that o > 0. We then have the following bound.
Theorem 5.2 With a sample complexity bound of
o . o(1 7) min 7)1
(1S) K) S| LA
log" (1/E)
where A min [1 A2), <= aa)e) (s, (s,a)} and q' denotes the optimal soluton to LP (6) corresponding to the optimal basis Ie and J we obtain a policy n from Algorithm 2 (defined in (24)) such that
Vi(T" 11) V* .1) SE and V*(a*N .1) aa E, Vk [K].
Our Algorithm 2 can be directly applied to solving MDP problems without resource constraints and our bounds in Theorem E.2 and Theorem 5.2 still hold. Note that in the MDP problems, the parameter can be lower bounded by - % which follows from the fact that the matrix A can simply be represented by the probability transition matrix. Then, we have the following sample complexity bound for our Algorithm 2.
Proposition 5.3 For the MDP problems without resource constraints, ie., K = 0. with sample complexity bound of
o
|S |A|
log (1/s)
(28)
we obtain policy म from Algorithm (defined (24)) such that
(T m1) V= p1) Se and V=(#N p1) aa S E, Wk [K].
In terms the dependency of our sample complexity bound on other problem parameters such as [8], [A], and - 7, we compare to the series of work [58, 67, 68, 2, 27], that subsequently achieves
where the dependency over [8), |A], and 7 is sample complexity bound of O [SI-LAI (1-
optimal [24, 43]. Our sample complexity bound in (28) has worse dependency in terms of [S] and 1 y- This is because we construct an empirical LP to estimate the value of LPP (6) and resolve the linear equation as in (21), where the size of the LP (which is (S)) and the eigenvalues of the matrix A (which bounded by 1-)) will play a part. However, our bound (28) enjoys a better dependency
in terms of E.
6 Conclusions
In this paper, develop the first instance-dependent ((1/c) sample complexity for constrained MDP problems. We characterize the instance hardness via corner points of the LP formulation and we develop resolving algorithm learn the optimal solution while sticking the identified optimal basis. The work presented by this paper advances the field of Machine Learning and the algorithmic ideas developed in this paper have broader impact to inspire new algorithms. Our results developed for the tabular settings, which pose some limitations to the real-world applications of our methods. We leave the extensions to more involved settings for future work.
Acknoledgement
Jiashuo Jiang generously supported by the early career scheme 26210223 and the general research fund 16204024 from Research Grants Council, Hong Kong.
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] Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with generative model is minimax optimal. In Conference on Learning Theory, pages 67-83. PMLR, 2020.
[3] Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A dynamic near-optimal algorithm for online linear programming. Operations Research, 62(4))876-890, 2014.
[4] Eitan Altman. Constrained Markov decision processes. vo17. CRCPress, 1999.
[5] Alessandro Arlotto and Itai Gurvich. Uniformly bounded regret in the multisecretary problem. Stochastic Systems, 93):231-260, 2019.
[6] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
[7] Mohammad Gheshlaghi Azar, Rémi Munos, Mohammad Ghavanzadeh, and Hilbert Kappen. Reinforcement learning with a near optimal rate of convergence. 2011.
[8] Qinbo Bai, Amrit Singh Bedi, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via conservative natural policy gradient primal- algorithm. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 6737-6744, 2023.
[9] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Dual mirror descent for online allocation problems. In International Conference on Machine Learning, pages 613-628. PMLR, 2020.
[10] Pornpawee Bumpensanti and He Wang. A re-solving heuristic with uniformly bounded loss for network revenue management. Management Science, 66(7):299333009 2020.
[11] Boxiao Chen, Jiashuo Jiang, Jiawei Zhang, and Zhengyuan Zhou. Learning to order for inventory systems with lost sales and uncertain supplies. Management Science, 2024.
[12] Yi Chen, Jing Dong, and Zhaoran Wang. A primal-dual approach to constrained markov decision processes. arXiv preprint arXiv:2101. 10099 2021.
[13] Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. Journal of Machine Learning Research, 18(167):1-51, 2018.
[14] Yinlam Chow, Ofir Nachum, Edgar Quenez-Guzman, and Mohammad Ghavamzadeh. A lyapunov-based approach to safe reinforcement learning. Advances in neural information processing systems, 31, 2018.
[15] Yinlam Chow, Ofir Nachum, Aleksandra Faust, Edgar Duenez-Guzman and Mohammad Ghavamzadeh. Lyapunov- basuud safe policy optimization for continuous control. arXiv preprint arXiv: 1911 2019.
[16] Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerik, Todd Hester, Cosmin Paduraru, and Yuval Tassa. Safe exploration continuous action spaces. arXiv preprint arX1v:1801.08777, 2018.
[17] Christoph Dann, Teodor Vanislavov Marinov, Mehryar Mohri, and Julian Zimmert. Beyond value-function gaps: Improved instance deeenddet regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34: 1-12, 2021.
[18] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. International Conference on Artificial Intelligence and Statistics, pages 3304 3312. PMLR, 2021.
[19] Dongsheng Ding, Kaiqing Zhang, Jiali Duan, Tamer Başar, and Mihailo R Jovanovié. Conver- gence and sample complexity of natural policy gradient primal-dusl methods for constrained mdps. arXiv preprint arXivv2206.02344. 2022.

---

[20] Yaqi Duan and Martin J Wainwright. Taming" data-hungry" reinforcement learning? stability in continuous state-action spaces, arXiv preprint arXiv:2401.05233, 2024.
[21] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitatoon in constrained mdps arXiv preprini arXiv:2003.02189, 2020.
[22] Jaime F Fisac, Anayo K Akametalu, Melanie N Zeilinger, Shahab Kaynama, Jeremy Gillula, and Claire J Tomlin. A general safety framework for learning- control in uncertain robotic systems. IEEE Transactions Automatic Control, 64(7):273722752, 2018.
[23] Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. instance-dependee complexity of contextual bandits and reinforcement learning: A disagreement based perspective. arXiv preprint arXiv:2010.03104, 2020.
[24] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91:325-349 2013.
[25] Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Achieving sub-linear regret in infinite horizon av- erage reward constrained mdp with linear function approximation. In The Eleventh International Conference on Learning Representations, 2022.
[26] Egor Gladin, Maksim nikov, and Martin Takac. Algorithm for constrained markov decision process with linear convergence. In International Conference on Artificial Intelligence and Statistics, pages 11506- 11533. PMLR, 2023.
Karina Zainullina, Varvara Rudenko, Alexander Gas-
[27] Jiafan He, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for discounted mdps. Advances Neural Information Processing Systems, 34:22288-222 -23000, 2021.
[28] Nicholas J Higham. Accuracy and stability of numerical algorithms. SIAM, 2002.
[29]
Jean-Baptiste Hiriart-Urruty and Claude Lemanéchal. Convex analysis and minimization algo- rithms Fundamentals, volume 305. Springer science & business media, 1996.
[30] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
[31] Stefanus Jasin and Sunil Kumar. A re-solving hcuristic with bounded revenue loss for network revenue management with customer choice. Mathematics of Operations Research, 37(2):3 13- 345, 2012.
[32] Stefanus Jasin and Sunil Kumar. Analysis of deterministic Ip-based booking limit and bid price controls for revenue management. Operations Research, 61(6):1312-1320 2013.
[33] Jiashuo Jiang. Constant approximation for network revenue management with markovian- correlated customer arrivals. arXiv preprini arXiv:2305.00 055899 2023.
[34] Jiashuo Jiang, Xiaocheng Li, and Jiawei Zhang. Online stochastic optimization with wasserstein based non-stationarity, arXiv preprint arX1v.2012.06961, 2020.
[35] Jiashuo Jiang, Will Ma. and Jiawei Zhang. Degeneracy is ok: Logarithmic regret for network revenue management with indiscrete distributions. arXiv preprint arXiv:2210.07996 2022.
[36] Jiashuo Jiang and Jiawei Zhang. Online resource allocation with stochastic resource consump- tion. arXiv preprint arXiv:2012.07933 2020.
[37] Yujia Jin and Aaron Sidford. Efficiently solving mdps with stochastic mirror descent. In International Conference on Machine Learning, pages 4890-4900. PMLR, 2020.
[38] Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.
[39] Michael Kearns, Yishay Mansour, and Andrew Y Ng. A sparse sampling algorithm for near- optimal planning in large markov decision processes. Machine learning, 49:193-208, 2002.
12

---

[40] Thomas Kesselheim, Andreas Tönnis, Klaus Radke, and Berthold Vöcking. Primal beats dual on online packing lps the random-orde model. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 303-312, 2014.
[41] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey, The International Journal of Robotics Research, 32(11):1238 1274, 2013.
[42] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in applied mathematics, 6(1):4-22, 1985.
[43] Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. In Algorithmic Learn- ing Theory: 23rd International Conference, ALT 2012, Lyon, France, October 29-31, 2012. Proceedings 23, pages 320-334. Springer, 2012.
[44] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with generative model. Operations Research, 72(1):203-221, 2024.
[45] Tianjiao Li, Ziwei Guan, Shaofeng Zou, Tengyu Xu, Yingbin Liang, and Guanghui Lan. Faster algorithm and sharper analysis for constrained markov decision process. arXiv preprint arXiv:21 10351, 2021.
[46] Xiaocheng Li. Chunlin Sun, and Yinyu Ye. The symmetry between arms and knapsacks: A primal-dual approach for bandits with knapsacks. In International Conference Machine Learning, pages 6483-6492. PMLR, 2021.
[47] Xiaocheng Li and Yinyu Ye. Online linear programming: Dual convergence, new algorithms, and regret bounds. Operations Research, 70(5):2948-298) 2022.
[48] Shang Liu, Jiashuo Jiang, and Xiaocheng Li. Non- von-stationary bandits with knapsacks. Advances in Neural Information Processing Systems, 35: 35:16522-16532, 2022.
[49] 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 Information Processing Systems, 34:17183-1771 17193, 2021.
[50] Tao Liu, Ruida Zhou, Dileep Kalathil, PR Kumar, and Chao Tian. Policy optimization for constrained mdps with provable fast global convergence. arXiv preprint arXiv:2111.00552, 2021.
[51] Yongshuai Liu, Jiaxin Ding, and Xin Liu. Ipo: Interior-point policy optimization under constraints. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 4940 4947, 2020.
[52] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 13X1v:13 2013.
[53] Ted Moskovitz, Brendan O' D'Donoguue, Vivek Veeriah, Sebastian Flennerhag, Satinder Singh, and Tom Zahavy. Reload: Reinforcement learning with optimistic ascent-descent for last-iterate convergence in constrained mdps. In International Conference on Machine Learning, pages 25303-25336. PMLR, 2023.
[54] Wenlong Mou, Zheng Wen, and Xi Chen. On the sample complexity of reinforcement learning with policy space generalization. arXiv preprint 2rXiv:2008.07355. 2020.
[55] Angelia Nedić and Asuman Ozdaglar. Subgradient methods for saddle-poimt problems. Journal of optimization theory and applications, 142:205-228, 228, 2009.
[56] Masahiro Ono, Marco Pavone, Yoshiaki Kuwata, and J Balaram. Chance-constrained dynamic programming with application to risk-aware robotic space exploration. Autonomous Robots. 39:555-571, 2015.
[57] Guy Shani, David Heckerman, Ronen Brafman, and Craig Boutilier. An mdp-hased recom- mender system. Journal of Machine Learning Research, 6(9), 2005.
13

---

[58] Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. Advances in Neural Information Processing Systems, 31, 2018.
[59] Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32, 2019.
[60] Adam Stooke, Joshua Achiam, and Pieter Abbeel. Responsive safety in reinforcement learning by pid lagrangian methods. In International Conference Machine Learning, pages 9133-9143, PMLR, 2020.
[61] Zhongchang Sun, Sihong He, Fei Miao, and Shaofeng Zou. Constrained reinforcement learning under model mismatch. arXiv preprint arXiv:2405.01321 2024.
[62] Aviv Tamar, Dotan Di Castro, and Shie Mannor. Policy gradients with variance related risk criteria. In Proceedings of the twenty-ninth international conference on machine learning, pages 387-396, 2012.
[63] Sharan Vaswani, Lin Yang, and Csaba Szepesvári. Near-optimal sample complexity bounds for constrained mdps. Advances in Neural Information Processing Systems, 35:31 35:3110-3122, 2022.
[64] Alberto Vera and Siddhartha Banerjee. The bayesian prophet: A low-regret framework for online decision making. Management Science, 67(3):1368-1391 2021.
[65] Andrew J Wagenmaker and Dylan J Foster. Instance-optimality in interactive decision making: Toward asymptttttoiicc theory. In The Thirty Sixth Annual Conference on Learning Theory, pages 1322- 1472. PMLR, 2023.
[66] Andrew J Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond no regret: Instance- dependent pac reinforcement learning. In Conference on Learning Theory, pages 358-418. PMLR, 2022.
[67] Martin J Wainwright. arXiv:/9066 04697, 2019.
Variance-reduced q-learning is minimax optimal. arXiv preprint
[68] Mengdi Wang. Randomized linear programming solves the markov decision problem in nearly linear (sometimes sublinear) time. Mathematics of Operations Research, 45(2):117-546, 2020.
[69] Honghao Wei, Xin Liu, and Lei Ying. A provably-efficient -ree algorithm for constrained markov decision processes. arXiv preprint arXiv:2106.01577, 2021.
[70] 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 1 11180-11491, PMLR, 2021.
[71] Yunbei Xu and Assaf Zeevi. Towards optimal problem dependent generalization error bounds in statistical learning theory. Mathematics of Operations Research, 2024.
[72] Andrea Zanette and Emma Brunskill. Tighter prohlem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
[73] Sihan Zeng, Thinh T Doan, and Justin Romberg. Finite-time complexity of online primal-dum natural actor-critic algorithm for constrained markov decision processes. In 2022 IEEE 61 Conference on Decision and Control (CDC), pages 4028-4033 IRFF, 2022.
[74] Ruida Zhou, Tao Liu, Dileep Kalathil, PR Kumar, and Chao Tian. Anchor-changing regular- ized natural policy gradient for multi-objective reinforcement learning. Advances in Neural Information Processing Systems, 35:14444-1359 13596, 2022.
14

---

A Numerical Experiments
We implement our Algorithm 2 to study the numerical performance. We consider CMDP problem with the state space |S| = 10 and the action space | 10. We set the discount factor y = 0.7. We then randomly generate the probability transition kernel P. To be specific, for each state E S, action E A. and the future state s' E S, we uniformly generate a randomly variable Ps.a,s'
Then, the transition probability is defined as P(s'ss,a) = -. Po...." For each state-action pair (s, a) E S x A. the expected reward f(s, a) is uniformly generated from the interval [1. 2] (with the reward for the first action set to be 0). The actual reward r(s, a) i(s, a) 77. where 17 is uniformly distributed among [-0.5, 0.5). There are K
Psiaie
constraints and for each constraint & E [K] and each state-action pair (s, a) S A, define the expected cost éx (s. to be uniformly generated from [1. The actual cost C& (s, a) = č₁ (s, a) + ry', where v/ is uniformly distributed among 00.55 0.5].
For each total iterations N, We apply Algorithm 2 and obtain the output q'........ We compare qN with the optimal occupancy measure. Since our algorithm is a randomized algorithm, we study the performance of our algorithm in expectation. To be specific, given the problem instance and a fixed N, we implement our algorithm repeatedly for M = 500 rounds. Denote by 9 the output of our Algorithm 2 at round m, for m E [M]. We define the error term as Err(N) -m== l q" |l1 ///l1111111 We study how the error term Err(N) scales with N. The results displayed in Figure 2. As we can see, the eπrоr term Err(N) decreases quickly with respect to N. Moreover, since our Algorithm 2 requires only solving a set of linear equations each iteration, the computation cost of our Algorithm 2 is also moderate.
M
0.18
0.18
0.14
0.12
0.08
0.08
Size N
Figure 2: The computational performance of Algorithm 2. The x-label denotes the size of N, while the y-label denotes the error term Err(N) N))
B Proof of Lemma 2.1
Let q" be a basic optimal solution to LP (6). We also denote by the index set of q" such that f > O. We then denote by J' [K] the set of active constraints q". Then, the following linear equations must be satisfied by q"
C(J'II) o.g. and B(: = μ.
(29)
From the property of the basic optimal solution, we must have [J'l + b>b1 [Z]
If b = [Z]. then we know that we already find the desired index set I and J = J'
Otherwise, if [ - > Z]. then we know that the LP (6) is degenerate. However, now the linear system (29) is over-determined, i.e., there must be [J' [Z] number of equations can implied by the others. It only remains to show that those redundant equations are all in the set J'. This step can be done can showing that the matrix Bc: Σ) has a full row rank. We prove this by showing contradiction.
15

---

For the infinite horizon discounted problem, suppose that (:,, does not have full row rank, there must exists B E IR si such that
B B(, =
(30)
On the other hand, denote by x² the optimal policy corresponding to q". We then define matrix I R|= such that the s-th column of I a vector that takes 0 for all the (s', a) I-th element # s, and take value of x (a|s) for all such that (s,a) E I. We know that
BI: - PD
with E [S being the identify matrix and px being the transition probability matrix under the policy n², with the element the s-th row and s'-th column denoting the probability of transiting from state state s' under the policy π². It well known that the matrix / - p is non-singular (see for example the Gersgorin's 's Theorem in [30]). Therefore, for any vector B E gl
we know that
g ((,, 3 (T pm #
which contradicts with (60). Our proof is thus completed.
C Proof of Lemma 3.2
We now condition the event that [i,, (s, a.) -f(s,)),, (fss)) [C,.N, - a)), and PN, (s'ls, a)
P(s'|s, a) for each E [K], (s,a) E S x A and s' E S are all bounded by Rad (N..)) E). From the union bound, we know that this event happens with probability at least 1 - (KSS |A|| [S|]|A|)
Note that for LP (4), by summing up the constraint (4c) all s E S, we obtain that any feasible solution for LP (4) would satisfy
|
1.
(31)
We first upper bound the gap V VNo- Denote by q" one optimal solution V. Then, from the feasibility of q", we know that
ONO = Cq + (Cno C) < a + Rad((No, E) S a + ANo
(32)
where the first inequality follows from | || = (31) and all elements of CNo - are upper bounded by Rad(No, e). Also, we know that
BN Bq* + (BN, B)q²
+ Rad(No. a) S - 7) ANo
(33)
where the first inequality follows from ||q" 1 (31) and all elements of BN. - B are upper bounded by 7 Rad(No, E). Similarly, we have that
BNO 9" Bq + (B B)q² 2 (1 7) p p- y Rad(NN: e) (1 7) 1 A
(34)
Therefore, as long as
ANo 2 RRa((No, e),
(35)
we know that q² is a feasible solution to VNO- We have that
rh, TT q" Rad(No.
(36)
by noting || (31) and all elements of FNN are upper bounded by Rad(No, s). Therefore,
we can obtain the bound
V Rad( S F... q" s UNo-
(37)
We then lower bound the gap V VNo- We first define
VN (Nv..) max (FNo XN.) TT
Cx,q ANo
BN, # +NNo
(38)
BN, 2 4 ANo
q q20 0,
16

---

for any constant Nya Clearly, any optimal solution q' to VN, will be a feasible solution to VN, (Nv,). Moreover, by summing up the constraints BN, S μ + ANo for all S, we know that
S
l1 1+ 1-7
ANo
(39)
Then, it holds that
|S|
VN. S (FNo x + NNo 11q 11 I VN, (NNo) + XNo 1 1-7 AN. AN.YN.
(40)
We then compare the value between VNo (N/vo) and V. The dual of UNo (Nwo) is given below.
Dual'y, (Xx,) = min
a y + p (z1 22) + ANo (113)11 + || 11ll2 (|22|11)
s.t.
CN y + B No (2) x2) 2 FNo XN,
(41)
y 2 0, 2 0, 22 0.
Denote by y and xt one optimal solution to the dual of LP (6), given below.
Dual min a dy 4
C CyーBB=>6
(42)
y 220, 0, -00.
We now show that y" and is also a feasible solution to Dual'N, with Xx. minge fau
1 11 51 (1) Ro.((N.e)) E). We have the following claim regarding the upper bound on || ll and
| |==
Claim C.1 There exists an optimal solution y² and z" to the Dual (42) such that
1y ||| S 1
1
1
minke[k] [ax] and ||='||00 S T- minke[K](ax]
Then, we define ÿ²" yy z = max (0, }²} and 2 = max(0, = - We have
CN. ". + BNo (zī 252 2 C T y +B= x' RRadNNo e) (1ly* Il ||=*111)
1
|S|
C y" B -Rad(No:e) minke(k)(
1
|S| 1 Rad s).
(1+1
2 f min {aw)
Thus, know that 8² and zi, 2 is also feasible solution Dual (N/vo). ) and we have Dual's, (Nr)) & Dual + AN. (Ilv")l + 11> & Dual + Rad(NNo 5) minke(K] {ac]
1 1 |S|
1-1) (43)
Combing (43) with (40) and also noting that UN, (Nvo) = Dual',, (NNo)), we have
VN, < V (Ro((No, {))x) (1+1
[S] 1-x) +
Rad Mad2(NNr) (No, E)
|S|]
|
minne[K] fax}
1
which completes our proof.
Proof of Claim C.1. We first bound yly" We utilize the approach in [29, 55]. We define a Lagrangian function, with only y the Lagrangian dual variable.
L q) = a y + TT - y TCq
(44)
where the feasible set for is {q 2 0: Bq= = 14} and the feasible set for y is (y 2 0}. Following Lemma 3 in [55], it is without loss of generality restrict the feasible set of y to the set { 2 0 || S p}. where the constant p is defined as
+ rT TT
(45)
minke[K] {as ((k)))))
17

---

where q is the occupancy measure that satisfies Slater's 's condition as stated in Theorem 3.1. Note that we have
P 1
minkElK] {
Therefore, obtain the following bound y":
1l p.
(46)
We now proceed to bound =". Denote by q" the optimal solution corresponding to the optimal dual solution (y*,=*), with y" bounded as in (46). We also denote by x² the optimal policy corresponding to q². Then, from the complementary slackness condition, as long as q" (s,s a) > 0 for a (s, a), we must have
(s, T y² + (s, a)) 2² = f(s,
(47)
We now multiply both sides of (47) by q" (s, Evees o' (s, and sum up over a, for each state Then we get
( + B x" = pm
(48)
Here, C E T Kx|s and the element at k-th row and s-th column is EnEA Cx(8, q (s.a)
En'ca & (m,a") B = I Ps s where px" (s, = EgEa (als)) P(s'ls, denotes the tran- sition probability matrix under the policy x². Also, pm RISl with fmr (8) ExEx a() q" (a.a) En'eA 9" (8,a"") Then, we have
z" = -Ba""-- -C*)
(49)
From [37], we know that
1
11(Ba) 1
11
(50)
1 7-7
Also, from the bound on y" in (46), we know that
10
"T 3
Sp.
(51)
Therefore, we have that
100
p
(52)
1 I- 7
which completes our proof.
D Proof of Theorem 5.1
We now condition on the event that |i (s, - a)), 1ū,,No (s, a) (x a)). and (8' (8'1s, a) P(s'|s, ((s'(ssa) for each & E [K]. (s, a) S x A and s E S are all bounded by Rad We know that this event happens with probability at least (KS)) - A|} ...
Following the procedure in Algorithm 1, we identify an index set I, where we set = 0 for each i I Note that we cannot further delete one more from the set Otherwise, when deleting this particular i in Z by setting I' = I {i), we will have V/z, V and as result of Lemma 3.2, we have
UN, Vi No.l S VV-
(No, 22Ga E) = 2Gap, (No, E) + 22Gap, E) (53)
Therefore, it feasible (objective value does not change) delete one more i from the index set I, our algorithm will already do so.
We denote by q" the optimal solution LP (6), corresponding to the optimal basis I identified by Algorithm 1. We know that z > 0 and zr. = O, which implies that
V Vz max
(fz)
s.t.
Clt, $ a
(54)
B(I μ q 2 0,
18

---

Note that in the formulation of (54), we simply discard the columns of the constraint matrix in the index set I. Thus, one optimal solution to (54) will just be qz. The dual of (54)
Dualy = min a y +
s.t. (C(::. (B(
((Z)
(55)
y 2 2
From the complementary slackness condition, know that for the optimal dual variable corre- sponding to az. all the constraints in (55) must hold with equality. Therefore, we have the following result.
Claim D.1 It holds that
V
VI Dualz min a n²
s.t. ()) TT y (B(,Z))² ==
(56)
2 0, 02 -X0
The proof of the claim is relegated the end of this proof. We now show that Algorithm identify the linearly independent binding constraints for q² such that the conditions in Lemma 1 are satisfied.
Denote by C(T,I) sub-matrix of C' such that the rows in the index set J C [K] and the columns in the index set I of the matrix C' remain. Now if the matrix
A [C(J B(,
(57)
is singular, there must be
one row C(J,I) can be expressed the linear combination of the other rows in (we know that the matrix B( has full row rank from Lemma 2.1);
(ii). or one column A can be expressed as the linear combination of other columns.
We consider the situation (i). Denote this row as k and know that restricting Vı will not change the objective value of Dualz, which implies that k' will be added to the index set J. This is because yıu cannot be basic variable, otherwise, the optimal basis of the Dual (56) will be linearly dependent. Therefore, we obtain a contradiction and we know that the matrix A must have full row rank. Thus, situation (i) will not happen.
We then consider the situation (ii). Note that we have
V Dual J.I = min aby + 4T
s.t. (C(J I)) y yy+ (B(, T 2 Pz
(58)
y 0, 2 -0,
Comparing the formulation (58) to the formulation (55), we only remain the rows of the matrix C(:, I) in the index set J, where is feasible (objective value does not change) to set yy- = 0. The dual of (58) is
V = VJ max
(Fz) C(J, ITq S aJ B(; =
(59)
q 0.
If situation (ii) happens and one column of A can be expressed the lincar combination of the other columns in A, then we denote the index of this column by and we know that we can simply restrict qr = 0 without changing the objective value of (59). This is because gr cannot be a basic variable otherwise the corresponding optimal basis will be linearly dependent. However, the index i' E I. This means that cannot further delete / from the index set I by restricting 4u- 0 without changing the objective value of LP (4). The above argument leads to a contradiction. Therefore, we know that situation (ii) cannot happen.
Given the arguments above, we know that the matrix is a non-singular matrix and thus the conditions in Lemma 2.1 are satisfied with the variable index set I and the constraint index set J.
19

---

It only remains to show that we can tell whether the objective value of V or Dualz has changed by restricting one variable to be O. Following the same steps as Lemma 3.2, we can show that for index sets I' and J', it holds that
Gap1 V VIIII,
(60)
and the upper gap as
Gapz(No.E) 2 V V with the formulation of Gap, (No. e) and Gap2 (No. <) given in (12) and (13). Therefore, as long as 2Gap, (Nu. 2Gap, E) 2 1i. A2h: where 01 is defined in (16) and 62 is defined in (19), and whether Dual is different from y Our proof is thus completed.
(61)
(62)
tell whether / is different from Vinn
Proof of Claim D.1. We first show that
V
Vi
max
(fz) q
s.t.
C(; S a
(63)
B(; 2 0.
Denote by q" the optimal solution V corresponding to the optimal basis I. It clear see that q is a feasible solution to Vz with the same objective value. Then, we have
V Vz.
(64)
On the other hand, we denote by á one optimal solution to Vr, and we construct
qr q and qr- =.
is clear to see that q is feasible solution to with the same objective value, which implies that
Vz S V.
(65)
Therefore, (63) is proved from combining (64) and (65). The dual Vz is given by
Dualz min a y T
s.t. (C 2)) T y + (B(;,)) 2 F(Z)
(66)
y 2 0, x -o.
We denote by y", x² the optimal dual variable to V corresponding to q". It is easy to see that y", = also feasible to Dualy and
Dualz = V+ = = =
where the first equality follows from the strong duality between Vz and Dualz, the second equality follows from (63), and the third equality follows from the strong duality between and its dual. Therefore, we know that y and x* is also optimal solution to Dualz. Moreover, note that from the complementary slackness condition, since of > O, we must have
(C(:,))) 3" + (B(t,)) = FZZ)
(67)
We know that y", x² is feasible solution to
Dual'y min a +1 (1-)) 4 s.t. (C(: (B(: ===
(68)
y y 0, 2 -00,
which implies that
Dual < Dualz.
On the other hand, any feasible solution to Dual', must be feasible solution to Dualy, and we have
Dual, 2 Dualz.
Therefore, must have Dual'y Dualy and our proof is completed.
20

---

E Proof of Theorem 5.2
We first prove the following lemma.
Lemma E.1 For the optimal basis identified in Algorithm and the corresponding optimal solution q, we denote by I and J the output sets as long as No satisfies the condition (25). also denote by (y", ,C' the corresponding optimal dual solution. Then, it holds that
N. VV(TT", - Σ B S
Vj.Blaj)
Σ 2/ El SES
(69)
JEJ
Therefore, suffices to analyze how the "remaining resources" (a'z., n²)) behave. We now define
(n)(n) 0% E J and (n))
11 N Vs S, vn E [N].
(70)
The key is to show that the stochastic process (n) and ita possess some concentration properties such that they will stay within a small neighborhood of their initial value of, and μ for sufficiently long time. We denote by J the time that one of ăy (n) for each & E J and Pa for each s E S escape this neighborhood. Then, both Regret, (T, and Regret, (T, .) for each & [K] can be upper bounded by E[N - T]. From the update rule (22) and (23), we know that
(n + 1) (n) E( c"(s, a) (" a) (x(
AKE J
(71)
-
and
P. + = Eis.aee-- (" (ōsts (0= (7.(m)
(72)
N
Ideally, both (n n + 1) and ",(n + 1) will have the same expectation as â& (n) and (n) such that they become a martingale. However, this is not true since we have estimation error over C(J* " II' and B(:, I,), and
only use their estimates compute q". Nevertheless, we show that â (n) for each l E J and jás for each 8 E S behave as a sub-martingale. Then, from the concentration property of the sub-martingale,
upper bound E E[ for each k J and El[n")] for each E S.
The term [ ]| for each is E [K] can be upper bounded well. The results are presented in the following lemma.
Lemma E.2 Denote by N the output policy of Algorithm 2 and denote by N the number of rounds.
Then, it holds that
N
(IS) + K)3
(og(N)
N V .1)
Σ ==1
r "EE
00 3
a. min(o² 7)2 A}
N
where the parameters (aak) A min( A3) with A given in (16) and 22 given in (19), given in (27). Also. for any k E [K], we have
N
(|S) + K) a. min (02, (1 - 7)2 A}
log(N)
N ag
Σ
c
0
(73)
N
E.1
Proof of Lemma E.1
Note that the distribution of q" independent of the distribution of n We know that
N TE)Ta) = Σ (fz- TE [o
Σ
1=1
Denote by q and y" z" the optimal primal-dual variable corresponding to the optimal basis I and J". From the complementary slackness condition and noting that q > O, we know that
(C(J",I')) T (B(,I"))) r.-
(74)
21

---

Also, we can define a matrix C* and (s, a) E I" column is o (s, a). We can also define a matrix 8" (, such that the element of Bd (:. T") at the s' E row and (s, a) E I column is òx' 7 (s.a)" It is easy to see that =
such that the element of C* (J", at the k E J row
II I') C(J*, IT' and (:. [[_rr]==B0 ();
Then, holds that
N E
N Σ
((((J"I')) y3 (B(, )²) T B[qž.]
E
=
n=1
n=1
(IC" (0% 2
(75)
E
(O") +(=)) (B=
Note that we have
Σ (T",III aly a
(76)
and
N
Σ (= )g- = x²= -M²
(77)
9=1
Plugging (76) and (77) back into (75), we get that
N
(fr-)) E 197-1 = (VG-) Ta'z. + (2") 11 - (WG-)) T [a.-] (E")TE [
TE
n=1
Note that
Va(T" 11) = (2z.) ( + (z*) nra
that holds from the strong duality of Infi (4). Then, we have that
N
N V= .1)) - Σ ( E[q") S (1g T aa + (2") B [
(78)
Our proof is thus completed.
E.2
Proof of Lemma E.2
We now condition on the event that [F, a) - -((ss (s,,(s))) (s, a)}. and (s (s a) P(s'|s (s a) for each & E [K]. (s,a) E S A and s' S are all bounded by Rad(n, s). for any [ We know that this event happens with probability at least 1 N (K|S)IAA - |8|]|||) e.
From now on, we set = = N² to guarantee that the event happens with probability at least 1 {| N
We consider the stochastic process (n) and (n) defined in (70). For fixed v > 0 which we specify later, we define a set
04 E [ox U, or + w). uk E J.). X = (a' E RRTT"
(79)
and
y {m' E [R : 14 E [mz - u. vs
(80)
It is easy to see that initially, @(1) E X' and ūi(1) y. We show that ((n) and (i()) behave well as long as they stay the region and y for sufficiently long time. To this end, we define a stopping time
T min (ā(n) X or ((()) V). =E[N]
(81)
Note that in Algorithm 2, to stop q" from behaving ill when n is small, we project it to set that guarantees | S We now show the following claim that when large enough but smaller than the stopping time т, there is no need to do projection.
22

---

Claim E.3 There exist two constants No and vo. When max Not S n T, and v S vo. it holds that 11 II 2, where qi. denotes the solution to the linear equations (21). Specifically, No is given in (25) and N6 is given as follows
K))
NO = 16
log(1/))
(82)
o²
Also, Vo is given as follows
v0 = 16 a. (1-
(83)
([S) + K)2²
We set satisfy the condition S with un satisfies the condition in Claim E.3, We bound E[N -r] the following claim.
Claim E.4 Let the stopping time be defined in (81). It holds that
E[N- -r] S mNx,No, N¹ + 2(K + (S)) exp(-u2/88
where No is given in (25) and No is given in (82), as long as
8
(IS) + K)) 32a (1 7)22"
N 2 No No} and N
(84)
Also, for any N' such that max (No, No N' < N, it holds that
(K + [S])
v2
exp (-12 -N-NNNNN )
(N N'
P(r S N') 5
(85)
4
8
From the definition of the stopping time in (81), we know that for each &: E J", it holds
of [(N - + 1). (ox - v), (N - r + (ax + v)]
Thus, we have that
aa S |a
Σ
(s, (s,
(86)
(8.a)EI'
and thus
Ela < 4 r] S max/NN, No +
+ (K+18)) exp(->²/1)
(87)
Following the same procedure, we can show that for each s E S, it holds that
[lir < 4BIN 7] S 4 max(No, No) + 8(K + (S]) exp(- -v²/8)-
(88)
We finally consider the other constraints is E T"c Note that following the definition of a " and μ²" we have that
A'
Elgg-11 =aa-- E Ja :pp E (((11 []-
(89)
Also, from the bindingness of q² regarding the optimal basis I and J we have
N A" qi- = ='"
(90)
Therefore, it holds that
Σ
E
[ N Zr- - (A*)-1, [R 2 FE [1
(91)
and
N Σ
E lg
2No
(92)
Finally, for any le E Th we have
(Tx) T Σ E [9")
N ((x) q ( (AA)) [B
[o..]]
:E [1 [1]
+ +NN
(93)
= - -(x) q" - ( (Ar)-1 [B [ N1 +NO
23

---

From the feasibility of q", we know that
Na N.. (éx) q².
Therefore, for any E J=o, it holds that
N. 04k
(6x) (47)-1. BlI + 2No
| K
m4x No + 8(K + (S]) exp(-12/8)) + 2No.
(94)
Moreover, the definition of a in (27) implies that following upper bound on the norm of the dual variable y* and z=.
S + K
1 11a + |=" (1(AA))-1
- 11
(95)
Therefore, we know that the regret over the reward and the regret over the constraint violation can all be bounded by using (87), (88), and (94). We present the bounds as follows.
N. VT
Σ
T
q")
K -||] a
(4x .
No + 8(K + (S)) exp(-12/8)). (96)
Meanwhile, the constraint violations are bounded by (87), (88), and (94). Our proof is thus completed.
Proof of Claim E.3. J.. Then, it holds that
Denote by q" the optimal solution corresponding to the optimal basis I and
(T)
Ta.-
(97)
We compare H with zz. when large enough. Note that when 2 No. q" is the solution to the following linear equations
(²(J"IT") B²(,I")
N
+
77.
(98)
11t
N
+
When n I T, we know that
a
Sv
(99)
N
n
+
and
11"
S..
(100)
N
Moreover, we know that the absolute value of each element -"( ((T+II) and (²(,I") (*) (²) upper bounded by Rad(n, We now bound the distance between the solutions to the linear equations (97) and (98). The perturbation of the matrix is denoted as
-C(+,I")- (T" [21]
AA'
B(:I")-BBC B(:TT")
Clearly, it holds that
AA < Rad(n,e) (K + (S]).
(101)
Therefore, as long as
|A 11 S Rad(n, s) (K + +(SI) < 211(A))
S 20'
(102)
24

---

following standard perturbation analysis of linear equations [28], we have that
77.-
-7-
11a
x((A))
|
| + (IS + -V)
99
--((A))-
IAAhh
||A 112
[JS+K] KK]
$ R(Ar)
(103)
||A* I|
|AAA" 112
(18) K))
$ 2 x(A")
||
1-7
where x<A") ||^ |1(A7)~*1| denotes the conditional number of A" The last inequality
follows from || 44 || 2 -1-7 Further, note that l/ ||1 1. Therefore, in order to satisfy the
condition - || S 2, we only need the right hand side of (103) to be upper bounded by Clearly,
as long satisfies the condition (102) and the following condition
|| |A
(n, E) .K + +1S1)
2 2- *-A(
2
S 2
(104)
||A|12
we only need to select v such that
(18) + K) 1 -
2 2- x(A)
(105)
Combining (102) and (104), we know that needs to satisfy the following conditions: 2 No and
No = 16 (IS) (IS) K)²
log(1/e).
(106)
o²
Also, v is selected to satisfy the following condition
a. 2-(1- (1-7)
1/ S PD = 16
(107)
([S) + K)²
Our proof is thus completed.
Proof of Claim E.4. Now we fix a A E J We specify a No = max No) For any No N' S N, it holds that
N
- (NoN)) Σ - an())).
nm No
We define (n) ãr ān ān (n). Then, have
N
-1 (n)
āx(N') (NooN) = Σ (Ex(n) - (m)) +
Σ
n=No
n=No
where F, denotes the filtration of information up step n. Note that due to the update (71), have
(n) = (x(n) E E(.a)er- (s a) qt (s,
N-n-1
Then, it holds that
2
(n) [[E
(108)
N W-n+1
where the inequality follows from the fact that the value of (n) is deterministic given the filtration < 2 for any n. Note that
Fn and ll ||
(Ex (n) Fnlmm)/
forms martingale difference sequence. Following Hoeffding's ' inequality, for any N < N' and any
b > 0, it holds that
6²
Σ No
(n) - E((()))) 2
5 2exp
2 DA No 1/(N
1)2
63. (N N2 NN*11)
< 2 2xxp
2
25

---

Therefore, we have that
N
P
Σ (Ex(n) - (.Ex,1
2 for some No S N" s NN
n= N= No
(109)
N
b. b.N(N NN
-1)
(N. b2. N' + 1)
82
eexp
2 S b exp
2
N"=No
holds for any b > O.
We now bound the probability that N' for one particular N' such that No N' S N. Suppose that N' I т, then, from Claim E.3, for each n S N', we know that ll S 2 and therefore
q" q" as the solution (21). We have
àg(n)=
Σ (s, (s. (s.a)EI-
holds that
Σ (=(),)) [F(Ck,((s, (x, 2R,
(A) S N n
(110)
N n +1
(s.a)eI+
Then, we know that
N-11
12g(2/E)
N'
1og(2/E)
N -1
[[(a()))FF)11 S
N
Vn. (N - n1)
2
n. (N - m)
No
n= Ng
Ng
log (2/e)
VN'
N'
Σ
N
N -
No
No
-
/2 /2log(2/e)
$ V log(2/e)
log(N)
logglo(())]) (N) S
N
(111)
for N large enough such that
8
(IS) + K)1
N
2
2
(112)
22
320 71
Combining (111) and (109) with b = v/2, and apply a union bound over all k E J and s E S, we know that
(K (K+ + (8)) v2
2² LN
P(r N')
exp
(113)
Therefore, we know that
E 7| Σ P(TSNN) No
Σ
P(rs $ No +2(K (S]) exp(-22/8)
N
which completes our proof.
E.3 Final Proof of Theorem 5.2
Note that in the proof of Lemma E.2, we have shown the following bounds.
B[a I| < 4ELN 7] s 4 max N6) + 8(K + +[[) exp(-12/8).
(114)
holds for the each & E J", For each S, it holds that
Biи (s) < 4 7] < max No + 8(K + [S]) exp(->2/8))
(115)
The caveat of directly transferring the bound of (114) and (115) into the sample complexity bounds of the policy # is that, the vector q does not directly characterize occupancy measure. This point
26

---

can be seen by noting that there is a gap between Bq and μ., though bounded by O(log(N)/NN) by setting & = 1/N2, However, we can show that the gap between qx and q" is upper bounded by Ollog(N)/N), which implies a bound over the gap between the policy я and the optimal policy n¹ that corresponds to the occupancy measure q'. This bound over the gap between the policy distributions can be then transferred into the bound over the gap between the state-value functions under the policy म and π². The regret bounds can be obtained then.
We first bound the gap between q and q² Note that as long as n 2 No. we have In = I following Theorem 5.1. Then, by noting IN I", we know that
Trec Cr
(116)
Also, note that following the definition of a² and μ², we have that
A
Σ E (
layy - E [a ip! EE [[
(117)
Also, from the bindingness of q" regarding the optimal basis I and J we have
N A t [a).:
(118)
Then, from (117) and (118), we know that
N
(AA))-
E Toyy. E
111
4r
1l.0
4r-
E
97.
N
N
1=
E
g-
1
(119)
σ
N.N
1
(4max Noo No + 8(K + [8]) exp(-1²/00
N
From Markov's inequality, for each E I" and any 0, we know that
P ((q.""
9:1l > g) s g. N (4max No. No + 8(K + +S)) exp((v²/8))
(120)
We denote by
min (s) (a.0)EI
(121)
The policy N is essentially random by noting that q is random variable, where the randomness comes from the randomness of the filtration Fx- For each E and E A, we denote by स (aa (s) the (ex-ante) probability that the random policy takes the action given the state s. Then, for any < g S E/2, we note that
q (s, EweA aN EneA (s,a")
('(s,a)
2g
1q," 4.l S for each i = (s, a) E I implies that
E (s,
g
(122)
for each (s, I For any 0 < g E/2, note that
[S] + (4max(No, NY) + 8(K + (8]) exp(-12/88
P (lg," -,"1= g for each i (s,a) I'' 1
(123)
where the inequality follows from the bound (120) and the union bound over i E I". Therefore, for any <g 5 E/2 and any (s, a), we know that
2g P | (als) - " (als)) <
|S| + K g.o.N.
(4 m4x No) + +(K + +(S)) exp(-u2
(124)
27

---

From the above inequality, for any (s, a), we have that
π R (als)
x (als)]
2
2
fer P ( (als) <a((ss)] 2g dg
E/2
<
1 (als) =a -
+
N
&
g
2
2([S] K),
- (4 No3 8(K + [S]) (xp(-12/81)) /
/2/2 dg
Ng
g x 9
2
2([S] + K)
+
(4 (No, N3) + 8(K + (8) exp(-1²) (log( N) log(E/
Ng
..
(125)
We finally transfer the bound (125) into the sample complexity bounds of policy #* We use the state-value functions V, s), defined for any initial state and any policy follows
Vi(T, 8) = E
Σ 7 r(s)
(126)
where (st, at) is generated according to the policy æ and the transition kernel P with the initial state Note that the value of (T, 8) for any S can be obtained from solving Bellman's equation under policy π
Vi 8) (-1o) [f(s,a) + ((-aa)))))) VV (T, (T, s')]]
(127)
We define a matrix _ E R|S|X|S| such that the s-th row s' s'tth column element
1dd (s 6,,5'
Σ
xals)) a))
(128)
REA
Then, the matrix 8" represents the state transition probability matrix under the policy т. Denote by
V+(T) = (V.(T, s))vEEs
and
((T) = Σ (als) . f(8, a))ssss.
acA
We have that the state values VT(T)) is the solution to the linear equation
B (+T) f(TT)
(129)
To bound the regret, we bound the solution to the linear equation (129) with being म N and n separately. The perturbation of the right hand of the equation (129) is
AF -( -(*²).
Clearly, we have that
2([S) + K) Ng
2
||A|| loc <
(4max(No, No) + 8(K + (S]) exp(-v? /8)//88)))))))) (log(N)))))) log(E/2))
-
(130)
The perturbation of the matrix is denoted
AB Ba" B3¹
Clearly, it holds that
27
27([S+ K)
|A <
- (4max/ No) 8(K + (S)) exp(-v3 -8)) (log(N) + (2)))
NE
(131)
We plug the formulation of No in (25) and N/6 in (82) into the bound (130) and (131). We obtain
(SS
K)3
log 2g2((N) (N)
| S C a.
(132)
min 7)2. .A.
N
28

---

where C1 is a constant, a minke [x] {ak), and A = minf4]. A3) with A given in (16) and 2
given in (19). We also obtain
7 [SS|+
+ K)a
log"(N)
aA SC o².g. min (1 - }}
(133)
N
Therefore, as long as
(|S) + K)3
log
C a² g min (1 (1- }}
N S 11/1(B")) = 1/06,
(134)
following standard perturbation analysis of linear equations [28]. we have that
VV* - Vl S SC2 (C2xx(("')
( 8c +
|
(135)
VVt 1oo
100 |F(T))]
where x(B**) || Iloe - 11((Br)--ll denotes the conditional number of D=,, and C22 is constant. Note that we have the regret
Regret, ( ,N) n (V+ V=(T)) S (1- (1->)11V((*)) (x(x=)
(
||
(136)
S C22(1- (1(1--) x(BB') (IV)
+
B 1000
[ |l
It is clear to see that
[|V $ 1-7
(137)
and
[((T))]lo
(138)
1 1-7
Following [37], we have the following bound.
1
[I
-
100 5
(139)
1 1-7
Also, from the definition, we have that
| 11 = 7
(140)
Plugging the bound (132), (133), (137), and (138), into the inequality (136), we have that
((S + K)3
log2 (N)
Regret, (# (NN,N) & C3 a² E a(1 7) min (1 (1- (1-))3-A)
(141)
N
where C3 a constant. same way, for any h E [K]. we obtain that
( + K)3
log (Ng
Regret, ,N) < Cs a². a(1 7) min (1 7))
(142)
N
To show the sample complexity bound, we denote by constant such that
(1S) + K)S
(N) N
C3 a² a2 (1) min (1 7)2 AA
Therefore, we have
(1S) + K)3
log (1/e)
N N a2. ( 7) min 002 (1-7)2.A)
Note that in each of the N rounds, obtain sample for each (s, a) S x AA Therefore, the bound on N above should be multiplied by (S) [A| to obtain the final sample complexity bound. Our proof is thus completed.
29

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The contributions and scope is accurately reflected.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations discussed in the conclusion.
30

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The assumptions and proofs are provided full.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Experimental details given in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
31

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: This a theoretical paper and all the data is simulated with details given in the appendix.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /ttpsscccppbbpcc////eeccppcpppcp hwwbbliccguiieee guwdee/ /CodeSubmis ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
32

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
All the experimental details are given in the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The experiment has been repeated enough times to guarantee that the expected regret has been appropriately approximated.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split. initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative еттог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The simulated experiments are easy to implement and no significant computing resource is required.
Guidelines:
The answer NA means that the paper does not include experiments.
33

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httpss://neet //tppri//////p../eeeee cctppublic//thiccouueeeee
Answer: [Yes]
Justification: It conforms.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Presented in the conclusion.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Not applied here.
34

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Not applied here.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the wwwrssitthhhdee package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Not applied here.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
35

---

Answer:
[NA]
Justification:
Not applied here.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: None is included.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
36


Reviews:
[{"review_id": "HIMA3ENY4s", "reviewer": "Reviewer_55Qh", "summary": "This paper studies reinforcement learning problem under Constrained Markov Decision Processes (CMDPs). It formulates the problem using linear programming and designs a novel algorithm to solve it. Using the newly designed algorithm, the authors prove a sample complexity of $\\tilde{O}(1/\\epsilon)$, albeit at the expense of having some additional factors.", "questions": "Could you theoretically provide some cases to illustrate when those additional dependencies do not make the bound worse? Besides, it will better if the cases provided are not edge cases.", "limitations": "There are no potential negative societal impact concerns for this theoretical work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The sample complexity analyzed in this paper breaks the barrier of $O(1/\\epsilon^2)$ which is known as the lower bound for the problem that the paper studies.\n\n- The algorithm proposed in this paper is novel. Under the linear programming framework, It designs an algorithm which only focuses on the LP basis (corner points of the feasible region). The algorithm run in $O(1/\\epsilon)$ iterations and in each iteration, the order of the samples collected is independent of $\\epsilon$. Unlike some traditional methods that operate in the dual space or use primal-dual techniques, this algorithm operates directly in the primal space.", "weaknesses": "- It has many additional dependencies such as an additional $|\\mathcal{S}|^3$, $\\sigma$, and etc., compared to other complexity bounds.\n\n- Since the algorithm focuses on the corner points, it defines the separation gap $\\delta_1$ between the optimal corner point and the sub-optimal corner points. They are defined to ensure the estimation errors are bounded to distinguish the optimal policy from sub-optimal policies. However, since the algorithm outputs stochastic policies, it is possible that the sub-optimal policies are very close to the optimal policy. Similarly, $\\delta_2$ is the minimum gap in the dual values when some constraints are excluded. If the constraints do not change the value of the dual problem much, $\\delta_2$ will also be small. Therefore, an additional $\\delta = \\min \\{\\delta_1^2, \\delta_2^2 \\}$ term might not be worth substituting for $\\epsilon$.\n\n- In addition, from the definitions of $\\xi$ and $\\sigma$, it is very likely they will be small terms. For example, for rarely visited states in $q^*$ and small eigenvalues for $A^*$.\n\n- Due to the above concerns, it would be better to conduct experiments showing that the samples needed under such a framework are indeed fewer than those needed for other algorithms achieving $O(1/\\epsilon^2)$. However, there are no numerical experiments done in this work. Thus, it is hard to tell whether the newly proposed algorithm is more efficient or not in reality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for your positive review and insightful comments! Please find below our response to the weakness and your question. We hope that our response would clarify your concerns regarding our work.\n\n$\\textbf{Response to weakness 1}$: Thank you for the comment! You are right that our bound has additional dependencies on the model parameters, however, this seems to be common for instance-dependent learning and has shown up in other works. It is easy to understand that when we obtain a better dependency on $\\epsilon$, we would suffer from a worse dependency on other parameters. However, it is important to note that the additional dependency on the model parameters is fixed and is independent of $\\epsilon$. Therefore, when we are seeking a highly accurate near-optimal policy and set $\\epsilon$ to be small, our bound will be a better one. Please further refer to our response to your question for a more detailed explanation. \n\n$\\textbf{Response to weakness 2}$: Thanks and you are right that for some instances, the parameter $\\delta$ can be small, making it difficult to separate the optimal policy from the sub-optimal ones and leading to a large bound. However, please note that no matter how small $\\delta$ can be, the parameter $\\delta$ is independent of $\\epsilon$. Therefore, even if $\\delta$ is very small, as long as we are seeking a solution with high accuracy, i.e., the error term $\\epsilon$ is also very small, it could still be desirable to use $\\delta$ to substitute $\\epsilon$.\n\n$\\textbf{Response to weakness 3}$: Thanks for the comments! You are right that for some bad instances, the dependencies on other problem parameters can be large. However, these parameters are always independent of $\\epsilon$. Therefore, when we want to find a near-optimal policy with a small $\\epsilon$, the $\\tilde{O}(1/\\epsilon)$ bound is desirable even if the dependencies on other parameters are large. Please refer to our response to your question below for more detailed explanations.\n\n$\\textbf{Response to weakness 4}$: You are right that it is better to conduct some numerical experiments to support our results. Due to the time limit, we conduct basic experiments. Please refer to the ``global response'' for more details on our numerical experiments.\n\n$\\textbf{Response to the question}$: Thank you so much for the question which allows us to provide further clarifications! Please note that though our bound has some additional dependencies on the problem parameters, they are independent of the accuracy level $\\epsilon$. To be specific, for a problem instance $I$, denote by $C_1(I)$ the constant term in our bound. Then, our sample complexity bound is $C_1(I)\\cdot\\log^2(1/\\epsilon)/\\epsilon$ on the instance $I$. The worst-case sample complexity bound established in the previous literature is $C_2/\\epsilon^2$. Please note that $\\epsilon$ is the accuracy level that we can decide. Therefore, for any problem instance $I$, as long as we set $\\epsilon$ small enough such that $\\epsilon\\leq O(C_2/C_1(I))$, our instance-dependent bound $C_1(I)\\cdot\\log^2(1/\\epsilon)/\\epsilon$ will be better than the worst-case bound $C_2/\\epsilon^2$. That being said, for any problem instance, even if the problem instance is not that favorable such that the constant term in our bound is large, our bound can always be better than the worst-case $O(1/\\epsilon^2)$ as long as we set $\\epsilon$ small enough, i.e., we are seeking for a policy with low error.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "z7quwYBj14", "reviewer": "Reviewer_w3CH", "summary": "The strength of this paper is that it provides strong sample complexity results for the constrained MDP, enhancing the existing analysis in the literature by developing a new algorithm. However, despite presenting a promising method, it lacks thorough comparisons with existing methods in the literature.", "questions": "1) Please define the notation [K] in page 2\n2) I wonder if the constraint (2) is commontly used in the literature. \nPlease add some discussions on the constraint (2) and if they are used in other papers.\n3) The term \"problem instance hardness\" is frequently used in the introdcution part, but it is not familier with the most readers in my opinion. Therefore, it is necessary to clearly define what is the problem instance hardness.\n4) Although the authros develop some promising algorithms, it seems that comparison with other approaches is still weak. Therefore, it would be better if some thorough discussions with existing works is added.", "limitations": "The authors properly addressed the limitations of the paper in the document.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The strength of this paper is that it provides strong sample complexity results for the constrained MDP, enhancing the existing analysis in the literature by developing a new algorithm.", "weaknesses": "Although the paper presents a promising method, it does not present more through comparisons with existing methods in the literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for your insightful comments! Please find below our response to each of the weakness points and the questions you posted. We hope that our response would clarify your concerns about the paper.\n\n$\\textbf{Response to weakness}$: Thank you for the comment! We will for sure provide a better literature review and comparison with previous methods. Briefly speaking, our work presents a new algorithm. We adopt an occupancy measure representation of the optimal and obtain an LP to work with, which is similar to the previous work. However, our algorithm resolves an LP and operates in the primal space, which is fundamentally different from the previous work that adopts a primal-dual update (e.g. Stooke et al., 2020, Ding et al., 2022, Zeng et al., 2022, Bai et al., 2023, Moskovitz et al., 2023, ). There is also work developing primal-based algorithms, for example (Liu et al., 2019; Chow et al., 2018; 2019; Dalal et al., 2018, Xu et al. 2021). Our algorithm is completely different from the previous work and we obtain new results. The result is that we are able to obtain an instance-dependent $\\tilde{O}(1/\\epsilon)$ sample complexity the first time in the literature, which improves upon the $O(1/\\epsilon^2)$ worst-case sample complexity established in the previous work. Though the constrained optimization approach and the Lyapunov approach have also been developed for CMDP problems, they do not enjoy a theoretical guarantee. In comparison to the literature, we develop a new primal-based algorithm and achieve the first instance-dependent sample complexity for CMDP problems.\n\nWe will add a more comprehensive literature review. We would be appreciative if you could point out the papers that we haven't discussed and we will add discussions of those.\n\n$\\textbf{Response to question 1}$: Thanks. The definition is $[K]=\\{1,\\dots, K\\}$. \n\n$\\textbf{Response to question 2}$: Thanks for the comment! Indeed, there are other formulations of the constraints in CMDP, for example,\n\\begin{equation}\nV_k(\\pi, \\mu_1)=\\mathbb{E}\\left[ \\sum_{t=0}^{\\infty}\\gamma^t\\cdot c_k(s_t, a_t)\\mid \\mu_1 \\right] \\geq \\lambda_k, ~~\\forall k\\in[K].\n\\end{equation}\nin a series of work that studies safe reinforcement learning. However, the above formulation can be transferred from our formulation in constraint $(2)$. One can set $\\alpha_k=\\frac{1}{1-\\gamma}-\\lambda_k$ for each $k\\in[K]$, and it is easy to see that the two inequalities are equivalent to each other,\n\\begin{equation}\n\\mathbb{E}\\left[ \\sum_{t=0}^{\\infty}\\gamma^t\\cdot c_k(s_t, a_t)\\mid \\mu_1 \\right] \\geq \\lambda_k \\Leftrightarrow \\mathbb{E}\\left[ \\sum_{t=0}^{\\infty}\\gamma^t\\cdot (1-c_k(s_t, a_t))\\mid \\mu_1 \\right] \\leq \\alpha_k.\n\\end{equation}\nTherefore, we can equivalently use the formulation in constraint $(2)$ with the cost function defined as $1-c_k$ for each $k\\in[K]$.\n\n$\\textbf{Response to question 3}$: Thank you! Please note that when deriving instance-dependent learning, it is important to define a measure to describe how difficult it is to separate the optimal policies from the sub-optimal ones. The importance of defining such a measure has been illustrated in other problems, such as multi-arm-bandit problems (e.g. Lai and Robbins (1985)) and reinforcement learning problems  (e.g. Auer et al. (2008)). There are also other works studying how to characterize such a measure for instance-dependent learning on general sequential decision-making problems, for example Wagenmaker and Foster (2023). This measure is usually defined as the gap (a positive constant) between the value of the optimal policies and the value of the best sub-optimal policies. However, since the optimal policies for CMDP problems are randomized policies, the sub-optimal policies can be arbitrarily close to the optimal ones. In our paper, we show that if we restrict the policies to the ones represented by the corner points, then such a gap can be characterized as the difference between the optimal corner points and the sub-optimal corner points. Suppose this gap is $\\Delta$, then it requires $\\tilde{O}(1/\\Delta)$ number of samples to identify the optimal corner point. In summary, ``problem instance hardness'' is a measure of the number of samples needed to separate the optimal policies from the sub-optimal ones. Our corner point characterization motivates our entire approach.\n\n$\\textbf{Response to question 4}$: Thank you! We will provide a better comparison with existing methods. Please refer to our response to the weakness part.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "H7GOo6O9qe", "reviewer": "Reviewer_sc31", "summary": "This paper addresses the reinforcement learning problem for CMDPs.  The authors derived a problem-dependent sample complexity bound that is $\\tilde O(1/\\epsilon)$, improving upon the state-of-the-art.  They introduce a novel way to characterize the hardness of CMDP instances using the LP basis, enabling problem-dependent guarantees. The proposed algorithm involves an elimination procedure to identify an optimal basis and a resolving procedure that adapts to remaining resources, ensuring the policy remains near-optimal with fewer samples.", "questions": "N/A", "limitations": "Suggestions:\n1) A typo in 1.1 Preliminaries line 53: \"stochaastic reward\" -> stochastic reward\n2) Define N in line 120\n3) In RL, the notation $q_\\pi$ is usually reserved for action-value function according to policy $\\pi$.  Thus, it may be a bit disorientating for people from the RL community to see $q_\\pi$ as a notation for occupancy measure. Perhaps use a different notation?  I've seen paper using $\\nu$ or $d$ for defining occupancy measures. \n4) On line 244, I believe \"...satisfy the condition in Theorem 2.1\" should be \"...Lemma 2.1\".", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well written, and the intuition/ideas behind the algorithm and theoretical proofs are clearly explained, making the paper a pleasant read.  I've learned something interesting and new.", "weaknesses": "While this point may seem minor since the problem setting assumes a tabular formulation with finite and fully observable state and action spaces, it is important to note that the methodology becomes challenging to apply when dealing with large or infinite state spaces where function approximation is required.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for your positive review and insightful comments! Please find below our response to your comments and questions!\n\n$\\textbf{Response to weakness}$: Thank you so much for the comment! Indeed, the method developed in this paper is mainly for the tabular setting. However, the method can also be extended to handle the setting with possibly large state/action space. To be specific, we can utilize a linear function approximation and similarly write a LP with the coefficients in the linear approximation as the decision variables of the LP. We are currently working on this extension. Combining our method with more general function approximations will be a future topic for us to explore. \n\n$\\textbf{Response to limitation 1}$: Thank you for pointing it out! We will correct it.\n\n$\\textbf{Response to limitation 2}$: Thank you! $N$ refers to the number of episodes.\n\n$\\textbf{Response to limitation 3}$: Thank you for the suggestion! Indeed, $\\nu$ or $d$ is a better notation for the occupancy measure.\n\n$\\textbf{Response to limitation 4}$: You are right! Thanks for the correction!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9bZZpNpnnt", "reviewer": "Reviewer_hDFd", "summary": "The paper proposes a new algorithm that solves the CMDP problem in $O(1/\\epsilon)$ sample complexity, which improves the best-known $O(1/\\epsilon^2)$ sample complexity in the literature. To achieve this, this paper made three contributions: (1) New characterizations of the problem instance hardness for CMDP problems. (2) A new algorithm based on LP literature instead of the traditional RL literature. (3) Extended results adopted to online LP literature.", "questions": "I am mainly concerned about the $O(1/\\epsilon)$ complexity. Can the author clarify the difference between this work and classical RL literature?", "limitations": "This is a theoretical work so there is no any negative impact.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The proposed method is new. Though it is mainly inpired by existing LP literature, to my understanding similar approaches have not been applied in RL or ML research. The LP formulation also leads to a new perspective in understanding the CMDP problem.", "weaknesses": "1. The presentation of this work is relatively poor. The author listed three contributions but I feel hard to understand how these contributions have contributed to this work. For example, in the Contribution 1, the author should tell (a) what is the problem instance hardness for CMDP problem, (b) what is the motivation of proposing new characterizations of the problem instance hardness for CMDP problems, (c) why the new characterization is helpful in developing the new algorithm or achieving better complexity.  \n2. There is no sufficient discussions on Lemma 2.1. How is it connected to the whole section Characterization of Instance Hardness?\n3. The reward, cost, and transitions are all estimated during training. I cannot agree that this algorithm work with unknown transition probabilities since it requires to estimate that.\n4. I doubt if the theoretical analysis is correct since it has been known that the sample complexity lower bound is $O(1/\\epsilon^2)$. See [R1] and [R2].\n\n[R1] Azar, Mohammad Gheshlaghi, et al. \"Reinforcement learning with a near optimal rate of convergence.\" (2011).\n[R2] Vaswani, Sharan, Lin Yang, and Csaba Szepesvári. \"Near-optimal sample complexity bounds for constrained MDPs.\" Advances in Neural Information Processing Systems 35 (2022): 3110-3122.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your insightful comments, which allow us to provide further clarifications. Please find below our response to the weakness and the questions. We hope that our response would clarify your concerns about the paper and we are happy to provide further clarifications if needed.\n\n$\\textbf{Response to weakness 1}$: Thank you so much for the comment! Please allow us to further clarify. Please note that when deriving instance-dependent learning, it is important to define a measure to describe how difficult it is to separate the optimal policies from the sub-optimal ones. The importance of defining such a measure has been illustrated in other problems, such as multi-arm-bandit problems (e.g. Lai and Robbins (1985)) and reinforcement learning problems (e.g. Auer et al. (2008)). There are also other works studying how to characterize such a measure for instance-dependent learning on general sequential decision making problems, for example Wagenmaker and Foster (2023). This measure is usually defined as the gap (a positive constant) between the value of the optimal policies and the value of the best sub-optimal policies. However, since the optimal policies for CMDP problems are randomized policies, the sub-optimal policies can be arbitrarily close to the optimal ones. In our paper, we show that if we restrict the policies to the ones represented by the corner points, then such a gap can be characterized as the difference between the optimal corner points and the sub-optimal corner points. Suppose this gap is $\\Delta$, then it requires $\\tilde{O}(1/\\Delta)$ number of samples to identify the optimal corner point. \n\nIn summary, (a). ``problem instance hardness'' is a measure of the number of samples needed to separate the optimal policies from the sub-optimal ones; (b). The optimal policies for CMDP are randomized policies and thus previous measures do not apply. We need to develop a new measure that can separate the optimal randomized policies from the sub-optimal randomized policies for the CMDP problems (by restricting to the policies represented by the corner points of the LP); (c). Our new algorithm is developed based on corner point characterization. To be specific, our algorithm 1 is developed to identify one optimal corner point (one optimal basis of the LP), and our algorithm 2 resolves the LP sticking to the identified corner point to learn the optimal randomization. As we can see, identifying the optimal corner point (basis) and resolving the LP sticking to this corner point (basis) are the key elements of our algorithm, which is motivated by the instance hardness characterization via corner point. \n\n$\\textbf{Response to weakness 2}$: Thank you! Lemma 2.1 is to show that for any LP, there exists an optimal basis or corner point and the LP basis or corner point can be characterized via non-zero variables and binding constraints. As discussed in our response to your previous point, this corner point representation motivates our entire approach.\n\n$\\textbf{Response to weakness 3}$: Thanks for the comment. Our work assumes that the transition probabilities are unknown and need to be estimated from the data. Our algorithm is more in the sense of model-based, and this is why we need to construct estimates of the transition probabilities, as well as rewards and costs, during the execution of our algorithm.\n\n$\\textbf{Response to weakness 4}$: Thank you for mentioning the two important papers! It is indeed true that if we are seeking for a $\\textbf{worst-case}$ sample complexity bound, then $O(1/\\epsilon^2)$ is the best we can hope for, just as illustrated in the two papers you mentioned. However, we would like to emphasize that we are deriving instance-dependent sample complexity in our paper. This is the key reason why we can break the $O(1/\\epsilon^2)$ lower bound and obtain an improved $\\tilde{O}(1/\\epsilon)$ sample complexity. To be specific, for a problem instance $I$, we can denote by $S(I, \\epsilon)$ the number of samples needed to construct an $\\epsilon$-optimal policy. Then the worst-case lower bound implies that $\\max_{I}S(I,\\epsilon)=\\Theta(1/\\epsilon^2)$. However, if we do not consider the worst-case guarantee, i.e., if we do not maximize over the problem instance $I$, then we can characterize an instance-dependent constant $\\Delta(I)$ (independent of $\\epsilon$) such that $S(I,\\epsilon)=\\Delta(I)/\\epsilon\\cdot \\text{polylog}(1/\\epsilon)$. The main contributions of our paper are to (i). find a cornet-point characterization of the instance-dependent constant $\\Delta(I)$, and ii). derive a policy that achieves the instance-dependent $\\tilde{O}(1/\\epsilon)$ sample complexity bound. Please note that our bound does not contradict with the worst-case lower bound $O(1/\\epsilon^2)$. It is simply that we are seeking for an instance-dependent bound and when the problem instance is favorable such that the constant $\\Delta(I)$ is smaller than $1/\\epsilon$, our bound strictly improves upon the worst-case bound. \n\n$\\textbf{Response to the question}$: Thank you for this question! The main difference between our work and the classical RL for CMDP literature is that we are deriving an instance-dependent sample complexity bound, while the previous literature focuses on the worst-case sample complexity bound. Indeed, the instance-dependent guarantee has been considered in the previous RL literature (but without constraints). See for example [1] and [2] for the logarithmic regret which transfers into $\\tilde{O}(1/\\epsilon)$ sample complexity bound. However, these works do not consider the existence of the constraints.\n\n[1]. Velegkas, Grigoris, Zhuoran Yang, and Amin Karbasi. \"Reinforcement learning with logarithmic regret and policy switches.\" Advances in Neural Information Processing Systems 35 (2022).\n\n[2]. He, Jiafan, Dongruo Zhou, and Quanquan Gu. \"Logarithmic regret for reinforcement learning with linear function approximation.\" International Conference on Machine Learning. PMLR, 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6bNRJPz0gk", "reviewer": "Reviewer_rqcB", "summary": "The paper studies the linear program formulation of constrained MDPs. The paper first characterizes the instance hardness of the underlying LP. Then, by proposing an algorithm that operates in the primal space and resolves the primal LP in an online manner, the paper derives an overall sample complexity of O(1/\\epsilon) up to logarithm terms.", "questions": "* Can the author provide a more comprehensive literature review and problem introduction? And I think it is also important to consider the dependency of the sample complexity on the problem-related parameters (i.e., |S| and |A|) in the comparison.\n* It would be better to briefly discuss the proof idea/implications of theoretical results around the theories. Currently, the ending of the paper seems too abrupt?\n* If it is possible, can the author provides some preliminary numerical experiments (not mandatory)?", "limitations": "I did not find the place where the paper explicitly discuss the limitation (yet, the author claims \"Yes\" in the checklist question 2). BTW, it seems the author also forgot to provide justifications for other questions in the checklist as well.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "* The paper provides a strong bound on the constrained MDP using LP-based approaches. The obtained sample complexity is the first in the literature that achieves \\tilde O(1/\\epsilon).\n* The derivation and presentation of theoretical results are clear and easy to follow. The proposed theoretical framework has the potential to be applied to more general online LP problems.", "weaknesses": "* The introduction and related work parts of the paper are not comprehensive enough (especially the related work). In the beginning of Section 1.2, the paper compares itself with [25, 29, 44, 14]. Yet, all of these works focus on policy-based methods, and I think it is not directly comparable with the proposed method in this paper. For example, the dependency of the sample complexity in this work is |S|^4, and this is usually lower for policy-based methods. Moreover, I think the paper might miss several related literature also studies occupancy-measure based approaches, for example,  \"Achieving Zero Constraint Violation for Concave Utility Constrained Reinforcement Learning via Primal-Dual Approach\" by Bai et al. \n* The paper does not provide numerical simulations. If there is some simulation, I think it helps the reader to have a better sense of how the convergence rate of the algorithm depends on the problem size.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for your insight review! Please find below our response to the weakness and your questions!\n\n$\\textbf{Response to weakness 1}$: Thank you for mentioning the important references to us! We will refine our literature review part to incorporate a better comparison with existing works and approaches, including the important work you pointed out. Briefly speaking, our work presents a new algorithm. We adopt an occupancy measure representation of the optimal and obtain an LP to work with, which is similar to the previous work. However, our algorithm resolves an LP and operates in the primal space, which is fundamentally different from the previous work that adopts a primal-dual update (e.g. Stooke et al., 2020, Ding et al., 2022, Zeng et al., 2022, Bai et al., 2023, Moskovitz et al., 2023, ). There is also work developing primal-based algorithms, for example (Liu et al., 2019; Chow et al., 2018; 2019; Dalal et al., 2018, Xu et al. 2021). Our algorithm is completely different from the previous work and we obtain new results. The result is that we are able to obtain an instance-dependent $\\tilde{O}(1/\\epsilon)$ sample complexity the first time in the literature, which improves upon the $O(1/\\epsilon^2)$ worst-case sample complexity established in the previous work. Though the constrained optimization approach and the Lyapunov approach have also been developed for CMDP problems, they do not enjoy a theoretical guarantee. In comparison to the literature, we develop a new primal-based algorithm and achieve the first instance-dependent sample complexity for CMDP problems.\n\nWe will add a more comprehensive literature review. We would be appreciative if you could point out the papers that we haven't discussed and we will add discussions of those.\n\n$\\textbf{Response to weakness 2}$: Thank you for the comment! We have conducted basic numerical experiments to illustrate the empirical performance of our algorithms. Please refer to the ``global response'' for more details.\n\n$\\textbf{Response to question 1}$: Yeah, sure! Please find in our response to the first weakness part the refined literature review on the comparison with existing works. Also, we provide the following discussion on the dependency on other problem parameters.\n\n``We discuss the dependency of our sample complexity bound on problem parameters other than $\\epsilon$. We restrict to the MDP context without resource constraints. Denote by $\\mathcal{S}$ the state set and $\\mathcal{A}$ the action set. We show a sample complexity bound of $O\\left( \\frac{|\\mathcal{S}|^4\\cdot|\\mathcal{A}|}{(1-\\gamma)^4\\cdot\\Delta}\\cdot\\frac{\\log^2(1/\\epsilon)}{\\epsilon}\\right)$, where $\\Delta$ is the constant that represents the hardness of the underlying problem instance.\nCompared to the optimal worst-case sample complexity $O\\left( \\frac{|\\mathcal{S}|\\cdot|\\mathcal{A}|}{(1-\\gamma)^3\\cdot\\epsilon^2} \\right)$ that is achieved in a series of work (e.g.  Sidford et al. 2018, Wainwright 2019, Wang 2020, Agarwal et al. 2020, He et al. 2021), our bound has a worse dependency over $|\\mathcal{S}|$ and $1-\\gamma$. This is due to our algorithm being LP-based and the dimension of the LP ($|\\mathcal{S}|$ and $1-\\gamma$) will influence our final bounds. However, our bound enjoys a better dependency in terms of $\\epsilon$. For the general CMDP problem, our bound will depend additionally on the conditional number of the constraint matrix in the LP formulation, which is a byproduct of the resolving LP heuristics (e.g. Vera and Banerjee 2021, Li et al. 2021). However, our $\\tilde{O}(1/\\epsilon)$ sample complexity bound depends polynomially on other parameters including $|\\mathcal{S}|$, $|\\mathcal{A}|$, $1-\\gamma$, and the number of constraints.''\n\nPlease note that even though our bound has some additional dependencies on other parameters, our bound can still improve upon the worst-case bound for any problem instance as long as $\\epsilon$ is set to be small. To be specific, for an instance $I$, denote by $C_1(I)/\\epsilon$ our bound (logarithmic term neglected) and denote by $C_2/\\epsilon^2$ the worst-case bound. Then, as long as we set $\\epsilon\\leq C_2/C_1(I)$, our bound will be smaller. Therefore, our bound is favorable when the instance is good such that $C_1(I)$ is small, or when we are seeking for a highly accurate near-optimal solution such that $\\epsilon$ is small.\n\n$\\textbf{Response to question 2}$: Thanks for the comment. Due to the space limit, the discussions on the proof idea have not been added. We will for sure have the discussion. Please find below for a preliminary one.\n\n``Our algorithm is motivated by the resolving LP heuristics in online LP/resource allocation literature (e.g. Vera and Banerjee (2021), Li and Ye (2021)). We can naturally interpret the right-hand-side constraints of the LP as the resource capacities and at each round $n$, the variables $\\alpha^n$ and $\\mu^n$ can be interpreted as the remaining capacities. Then, a key step in the proof is to establish that the average remaining capacities, $\\alpha^n/(N-n+1)$ and $\\mu^n/(N-n+1)$ behave as (sub-)martingales. As a result, we can apply concentration properties to show that the remaining capacities will diminish when we arrive at the end of the horizon, i.e., the resources have been utilized well. Moreover, since we have already identified the optimal basis in Algorithm 1 and we resolve the LP sticking to the optimal basis, we can show that when the resources are well utilized, the total reward we collect is very close to the optimal reward. In this way, we obtain a bound over the total reward collected by our policy and that of the optimal policy, which then transfers into the sample complexity bound.''\n\n$\\textbf{Response to question 3}$: Thanks for the question! We are happy to add the numerical results. We have conducted basic experiments. Please refer to the ``global response'' for more details.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We implement our algorithm to study the numerical performance. We consider a CMDP problem with the state space $|\mathcal{S}|=10$ and the action space $|\mathcal{A}|=10$. We set the discount factor $\gamma=0.7$. We then randomly generate the probability transition kernel $P$. To be specific, for each state $s\in\mathcal{S}$, action $a\in\mathcal{A}$, and the future state $s'\in\mathcal{S}$, we uniformly generate a randomly variable $p_{s,a,s'}$. Then, the transition probability is defined as $P(s'|s,a)=\frac{p_{s,a,s'}}{\sum_{s''\in\mathcal{S}}p_{s,a,s''}}$. For each state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$, the expected reward $\hat{r}(s,a)$ is uniformly generated from the interval $[1,2]$ (with the reward for the first action set to be $0$). The actual reward $r(s,a)=\hat{r}(s,a)+\eta$,  where $\eta$ is uniformly distributed among $[-0.5, 0.5]$. There are $K=5$ constraints and for each constraint $k\in[K]$ and each state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$, we define the expected cost $\hat{c}_k(s,a)$ to be uniformly generated from $[1,2]$. The actual cost $c_k(s,a)=\hat{c}_k(s,a)+\eta'$, where $\eta'$ is uniformly distributed among $[-0.5, 0.5]$.

For each total iterations $N$, We apply our algorithm and obtain the output $q^1, \dots, q^N$. We compare $\bar{q}^N$ with the optimal occupancy measure and we define the error term as $\text{Err}(N)=\|\bar{q}^N-q^*\|_{1}/\|q^*\|_1$. We study how the error term $\text{Err}(N)$ scales with $N$. The results are displayed in the attached PDF. As we can see, the error term drops to $0.02$ within $N=5000$ iterations and it keeps improving as we have more and more iterations. The computation time of our algorithm is also fast in that in each iteration, we only need to solve a set of linear equations. These evidences demonstrate the numerical efficiency of our algorithm and we will conduct more involved experiments in the future work.

Meta-review: This paper derives optimal problem-dependent guarantees for CMDPs. In particular, the paper proposes a primal only algorithm and prove that the resulting algorithm has an instance-dependent $O(1/\epsilon)$ sample complexity bound. 

The reviewers agree that the paper is well-written, and its contributions merit acceptance. After carefully reading the paper and the corresponding discussion, I tend to agree. Please incorporate the reviewers' feedback. In particular, addressing the following concerns will help strengthen the paper:
- Include the experiment done as part of the author response. An empirical comparison with an existing approach (e.g. primal-dual policy gradient) will be helpful. 
- Explain whether the proposed algorithm (without any modification) retains the $O(1/\epsilon^2)$ problem-independent sample-complexity
- Better situate the resulting algorithm and compare to the existing literature (response to Rev. w3CH)
- Add the discussion about the minimax lower-bound (response to Rev. hDFd)
- Compare to the previous bounds in terms of the dependence in $S$, $A$ (and not just $\epsilon$)
- Add a proof sketch. Including some more details about the online LP literature and better connecting it to the CMDP problem will enhance the paper's readability for the audience working on constrained RL. 
- Clearly explain the dependence on the constants in Theorem 5.2. What is tight and what can be relaxed? Conjecturing a lower bound and having a discussion section will be helpful.
Decision: Accept (poster)