Near-Optimal Sample Complexity for Online Constrained MDPs
Authors: Chang Liu
Yunfan Li
Lin Yang
Venue: NeurIPS 2025 poster ()
Keywords: Reinforcement learning
constrained MDPs
online learning
sample complexity
learning theory
Primary area: theory

Abstract: Safety is a fundamental challenge in reinforcement learning (RL), particularly in real-world applications such as autonomous driving, robotics, and healthcare. To address this, Constrained Markov Decision Processes (CMDPs) are commonly used to enforce safety constraints while optimizing performance. However, existing methods often suffer from significant safety violations or require a high sample complexity to generate near-optimal policies. We address two settings: relaxed feasibility, where small violations are allowed, and strict feasibility, where no violation is allowed. We propose a model-based primal-dual algorithm that balances regret and bounded constraint violations, drawing on techniques from online RL and constrained optimization. For relaxed feasibility, we prove that our algorithm returns an $\varepsilon$-optimal policy with $\varepsilon$-bounded violation with arbitrarily high probability, requiring $\tilde{O}\left(\frac{SAH^3}{\varepsilon^2}\right)$ learning episodes, matching the lower bound for unconstrained MDPs. For strict feasibility, we prove that our algorithm returns an $\varepsilon$-optimal policy with zero violation with arbitrarily high probability, requiring $\tilde{O}\left(\frac{SAH^5}{\varepsilon^2\zeta^2}\right)$ learning episodes, where $\zeta$ is the problem-dependent Slater constant characterizing the size of the feasible region. This result matches the lower bound for learning CMDPs with access to a generative model. Episodic tabular CMDPs serve as a crucial benchmark for safe RL, providing a structured environment for theoretical analysis and algorithmic validation. Our results demonstrate that learning CMDPs in an online setting is as easy as learning with a generative model and is no more challenging than learning unconstrained MDPs when small violations are allowed.

Near-Optimal Sample Complexity for Online Constrained MDPs
Chang Liu
Yunfan Li
University of California, Los Angeles changliul1@ucla.edi
University of California, Los Angeles yunfanli@ucle edu
Lin Yang
University of California, Los Angeles linyangdee ucla.edu
Abstract
Safety is a fundamental challenge in reinforcement learning (RL), particularly real-world applications such autonomous driving, robotics, and healthcare. To address this, Constrained Markov Decision Processes (CMDPs) are commonly used to enforce safety constraints while optimizing performance. However, isting methods often suffer from significant safety violations or require a high sample complexity generate near-optimal policies. We address two settings: laxed feasibility, where small violations are allowed, and strict feasibility, where no violation is allowed. We propose model-based primal-dual algorithm that balances regret and bounded constraint violations, drawing on techniques from online RL and constrained optimization. For relaxed feasibility, prove that our algorithm returns an e-optimal policy with s-bounded violation with arbitrar-
ily high probability, requiring Ô SAH" learning episodes, matching the lower bound for unconstrained MDPs. For strict feasibility, we prove that algorithm returns an e-optimal policy with zero violation with arbitrarily high probability, requiring Ō SAA E-C2
learning episodes, where Ç the problem-dependeen Slater
constant characterizing the size of the feasible region. This result matches the lower bound for learning CMDPs with access to generative model. Our results demonstrate that learning CMDPs in online setting easy learning with generative model and is no more challenging than learning unconstrained MDPs when small violations are allowed.
Introduction
Safety is fundamental concern in reinforcement learning (RL), especially in real-world applica- tions such as autonomous driving [II], healthcare [D], and industrial automation [3]. Constrained Markov Decision Processes (CMDPs) [ are widely used to ensure safety by incorporating safe constraints and safe policies into the decision-making process. These frameworks allow for opti- mizing performance while limiting risky actions in safety-critical environments, such preventing collisions in autonomous vehicles or ensuring correct treatment healthcare. However, during course of training, many RL methods can suffer from significant safety violations 15. &il. particularly when exploring new states or actions. This is highly problematic in real-world systems where even temporary unsafe actions can result in accidents, equipment damage, hazardous conditions. For instance, in autonomous driving [Ø]] safety violations during training might lead to collisions or dan- gerous maneuvers, while in robotics [8], such violations could cause physical harm equipment
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

or workers. As a result, it is crucial to design methods that guarantee bounded safety constraint violations, ensuring that any violations during training remain within acceptable limits, thereby pre- venting catastrophic outcomes while maintaining safety throughout the learning process.
Tabular episodic MDPs, of the most fundamental settings in RL, have been extensively stud- ied, with various methods proposed to solve them [EL TIO have been shown to achieve minimax optimal regret OVSSAH* K) and [C provided a method to achieve the minimax optimal sample complexity Ō
III
12
[5]. Many algorithms
Extending to CMDPs, prior works [6. II.. IA I& 19 20, 24L 22, 23, DZI have proposed methods in various settings that either achieve sublinear regret or return near-optimal algorithms. However, lower bounds and algorithms with provable minimax optimal upper bounds still remain unexplored in most of these works. Two pri- mary feasibility settings in CMDPs are relaxed feasibility and strict feasibility []8, 200, 211 23 In the relaxed feasibility setting, algorithms may return approximately optimal policies that allow small constraint violations. In contrast, in the strict feasibility setting, the learned policies must be near-optimal while ensuring zero constraint violations. The formal formulations for both settings are defined in section E [TS] proposed a model-based algorithm that achieves minimax sample com- plexity in both regimes, but relied on the assumption of a generative model that grants the learner random access to any state-action queries. However, in many real-world scenarios such as robotics and autonomous driving, the learning agent has to collect data online through sequential interactions with the environment. How or whether minimax optimal sample complexity be achieved in the online setting, which generalizes the random access setting and is inherently more challenging [2S], remains unknown. This raises the following question:
SAH
Can we design safe online reinforcement learning (RI.) algorithms for both relaxed and strict fea- sibility settings that achieve near-optimal sample efficiency in large-scale state spaces and long horizons while guaranteeing approximate reward optimality with arbitrarily high probability?
In this paper, we affirmatively answer this question by proposing a model-based primal-dual algo- rithm. Our contributions are summarized follows:
We propose a model-based primal-dual algorithm with doubling batch updates. In each episode, a policy is derived by mixing policies from multiple iterations of primal-dual up- dates in a constrained model represented in its Lagrangian form. This policy is then used to gather data to update the empirical transition model. The doubling batch update tech- nique ensures a lazy update of the empirical transition model, allowing us to derive tighter theoretical bounds.
For the relaxed feasibility setting, we prove that our algorithm returns an e-optimal policy with at most e constraint violation after SAAH* of online learning episodes, where g²
S and A is the number of states and actions, H is the horizon. This sample complexity (SAN") g²
[αа]], showing that learning CMDPs the relaxed feasibility setting is as easy as learning unconstrained MDPs.
matches the lower bound for unconstrained MDPs: Ω
For the strict feasibility setting, we prove that our algorithm returns an c-optimal zero- violation policy after Ō SAH of online learning episodes, where Ç is the problem- E²C²
dependent Slater constant characterizing the size of the feasible region. This sample com- plexity matches the lower bound for infinite-horizon discounted CMDPs with access generative model: f
[18], showing that learning CMDPs with online access is as easy as learning CMDPs with random access.
SA
(1-9)--<)
Notation. We introduce set of notation to be used throughout. For any two vectors x, E R with the same dimension d, we use xy to abbreviate the inner product af y, e.g. Peoa, Vi h+1, For any integer S > 0, any probability vector p E A(s] and another vector u [vil we denote by (p,,)) v) := <p, - ((p, v))² the associated variance, where
E. Pa.a.
x² = [0]] isiss represents element-wise square of v.

---

2 Related Work
Constrained Markov Decision Process (CMDP) The Constrained Markov Decision Process (CMDP) [8]] key model for addressing safety concerns in reinforcement learning (RL), Many existing works on CMDPs employ a primal-dual approach to achieve sublinear regret while main- taining bounded constraint violations [T8. 26, 27, 28. 29. 50J. Another widely-used method is adapt- ing policy gradient algorithms [G1] B2. B%, DEY. Furthermore, [K]] introduces a more stringent metric for hard constraint violation, where only positive constraint violations are accumulated. Their ap- proach achieves sublinear regret, constraint violations and hard constraint violation. Recently, [55] extended this idea to linear setting, obtaining similar results. In practical applications, ensuring strict adherence to safety constraints without violations often requires system-specific assumptions. For instance, [LG] assumes regularity in the safety functions, while [GY]] presumes knowledge of a safe action for each state. Additionally, [T66, [7] assume the existence of a known safe policy and its true constraint value, achieving improved regret bounds and constraint violations compared to [ö]. Building on the assumption of a known safe policy and its true constraint value, work proposes a primal-dual low-switching algorithm, leveraging advanced techniques from standard MDPs. This approach not only improves the regret bound but also maintains constant constraint violation. [TS]] solved the infinite-horizon discounted tabular CMDPs in the random access setting. Our work ex- tends their results to tabular CMDPs in the online setting, which serve as a crucial benchmark for safe RL that provides a structured environment for theoretical analysis and algorithmic validation. Further extension to function approximation or multiple constraints is out of the scope of this paper and an interesting topic for future research.
Episodic unconstrained MDPs [S first provided an upper bound of O(V
[59
established lower bounds of Q(V K) for regret and S2(SAH for sample complexity. [о] introduced a posterior sampling approach for RL, achieving minimax-optimal regret bounds of O(VSAHK) under certain conditions. [ further achieved a minimax optimal regret for model- based algorithm, and |[ developed similar results for a model-free Q-learning method. Many methods have achieved near-optimal upper bounds [122
Recently, [[SS] achieved minimax optimal regret, sample complexity, and burn-in cost, yet such methods are rarely explored in CMDPs. To our knowledge, this work the first to incorporate state-of-the-ee techniques for unconstrained MDPs into CMDPs, achieving minimax optimal performance in online constrained RL.
3 Problem Setup
We consider a finite-horizon non-stationary constrained Markov Decision Process (MDP) defined by the tuple M the horizon length. The unknown transition probability at each time step is denoted by Pa where P. (s.) represents the probability of transitioning to state s' from state after taking action a at time step h. The reward function receives for taking action in state s at time step h. Similarly, the cost function C₁ : x A [0. 1] represents safety violations incurred for the same action. We assume that both the reward and cost functions are known to the agent, though the same results can be easily extended to the case where neither function is known. Finally, b E (0, H) is predefined safety constraint that limits the cumulative cost over the episode.
H,,,H, b). where S is the state space, A is the action space, and H is
S x A + [0. 1] quantifies the immediate reward the agent
The agent interacts with the enviromment over K episodes, each consisting of H steps. At the start of each episode k, the agent selects a randomized policy R [ where time step h the policy TH S - A prescribes a distribution over actions conditioned on the current state. The policy is executed with the goal of maximizing the cumulative reward while ensuring that the cumulative cost remains within the safety limit. The cumulative value state s and time step h. with respect to any function y : S x A I. under policy is defined as: VA, (s) Ep,,, "E g(S, As) Sn s
representing the expected cumulative sum of g(S, At) from time step h to the end of the episode, given that the process starts in state time h. The objective of CMDP is to solve the following constrained optimization problem:
max VT, ($1) s.t. (1. S b. x
(1)
3

---

where (81) is the expected cumulative reward value, and V (s)) is the expected cumulative cost value, constrained by the safety threshold The optimal policy x solving eq. ( defined as
π arg max (s1) s.t. V(Ic(s1) I
The corresponding expected reward and cost value are denoted by (s1) and (i.) For
CMDP instance, define the Slater constant Ç == max, b VT, (s1). The Slater constant measures the size of the feasible region. We also define the policy that with the minimal cost value: Te E arg max, b (+1).
We now define the regret and constraint violation over K episodes:
K
Regret(K) K) = Σ
(Vi, 1m
VT," (st) and CV(K) =
Σ
( (84) -
-b)
(2)
We will provide upper bounds on both regret and constraint violation of our algorithm, but more importantly, convert such bounds to our final sample complexity bounds. For small suboptimality error E, we define the two settings as follows:
The agent's ' objective is to return a policy that with high probability achieves an approximately optimal reward value, while violates the constraint by small margin. Formally the agent returns a policy such that with high probability,
Relaxed feasibility:
(s,) 2 (s) - E, and (11 bb+
Striet feasibility: The agent's objective is to return a policy that with high probability achieves an approximately optimal reward value, and simultaneously achieves zero constraint violation. For- mally the agent returns policy π such that with high probability.
(s1) (si) -, and (T) <.
In the next section, present technical methodology to tackle both settings in online CMDPs.
4 Methodology
Before introducing our method, we examine the state-of-the-an algorithms tabular online CMDPs, and discuss why their methods fail to achieve near-optimal sample complexity.
One of the biggest challenges in analyzing model-based algorithms in unconstrained MDPs and CMDPs is to decouple the correlation between the empirical model P and the estimate values V=* Indeed, both [[6]] and [17]]] get the extra regret terms due to loose decoupling steps. In particular, [ achieve a regret of Ö(V5² AH (arKK/(( K/(b- c²)), where c is the value of known safe policy. In both their regret analysis, the authors bound the term Vi,"" (s1) VT," (81) by
H
(r.) - Vi,
Σ
P Por.agi(6)) - Po..ag.(66)) (itti.(s)) Σ
h=1
H
Ex
Σ P ( -
(o H
,P
Am
where the equality follows from value difference lemma and the inequality follows from Hölder's s inequality and V < H. Then they invoke Bernstein's 's inequality on the concentration bound of P. This technique is also known to be used in unconstrained MDPs [2] and gives regret of Ö O(VS*AH*K) which is suboptimal compared to the lower bound N (2 (SH*A) ). Following [[2], subsequent works [R, [S] introduced different techniques to achieve opar-altimal regret, but neither method extends directly to CMDPs.
In the regret analysis of [SI, the authors bound /i (s/) Ver (sh) by writing in a recursive form. One of the key steps bound the following term as:
(Paar - Pa.a.) ( (DitLLF
Vātt.r) S Σ P Pa.a, (s') Paaai(ss) (Vii - vxti,

---

where the inequality follows from the optimism of VES and optimality of k. (o) 2 (s) > hhr (s), wh E | E [K] E S. This argument fails in CMDPs, because the optimal policy n² in CMDPs is not necessarily optimal for all h E [M]]
The high-level idea of "profile" that keeps track of visitation counts for all (s, a)) tuples. V is independent of Pa. A union bound over all possible profiles then gives the desired regret bound. To avoid the number of such profiles being exponential in K, the authors adopt the double batch updates explained later. Although decoupling arises naturally in unconstrained MDPs through backward updates, it is not the case in constrained MDPs. If the policy л is determined by enforcing the constraint Vr. s b. then π and thus 1 will be inherently correlated to all Pr's.
[ to decouple the correlation between P and V is that, when fixing
To tackle these challenges, we use eq. (I). Adopting the doubling batch updates, we update our empirical transition matrix only when the visitation count of any state-action pair doubles. To be specific, we denote N₂ (s, a) as the total visitation count of state-action pair (s, a) in time step ht N₁, (s, a, s') as the count of transitions from (s, a) to s' since the last update, and (x, = >.' (s, a, s') the visitation count of (s, a) since the last update. We update an empirical transition matrix P whenever (n a) for any (s, a) doubles, such that (8') (s.a.,') Note that we will only use the data collected after the (N.(s.))
approach to address the CMDP problem defined in
last update to calculate P. With P. we are able to formulate an empirical CMDP.
We adopt a UCB-style bonus for both reward and cost. For any reward function g and policy x, we define the bonus for (s, a, h, k) tuple as
- V(P..,. DI 1.) log(1/8)) (s)
H log(1/6")
+ C2 N,, a)
(5)
where et and C2 are constant to be specified later and 8' = K/(200SAHPK²) is related to the confidence level 8. For reward, we add this Bernstein-style bonus bs. a) to rn (s, a) for each (s,a) to encourage exploration. We denote the optimistically biased reward estimate (s, a) = (s, a) + (s, a). For safety cost, we subtract a Bernstein-style bonus bn.c(s, a) from a). We denote the optimistically biased cost estimate by c. i.c., CA (s, a) ca,s, a) - bb, a). By using the optimistically biased cost estimate we will underestimate the cumulative cost. To com- pensate for this and strive to satisfy the safety constraint in the strict feasibility setting, pessimistic constraint constant D' for each episode by subtracting gap A from b, that is, b' = b- A. Whereas for the relaxed feasibility setting, since small violations are allowed, we define optimistic constraint constant b' := b + r. This non-negative optimistic shift is also required to derive (-free results for the relaxed feasibility setting. We will specify the value of A and 7 later.
7, ie..
define
We now introduce an empirical CMDP for each episode defined by Me 1I, and the corresponding optimization problem ph:
max (11) s.t. (s) S8.
(6)
As discussed before, directly solving eq. ( results in complex correlation of P and V leading to suboptimal results. Therefore, we employ primal-dual approach, which transforms the constrained optimization problem into a saddle-poin problem. Let X 2 0 be the dual variable associated with the cost constraint. The equivalent saddle-poin problem to eq. (8i is:
min max (iT((s1) - > (P) X
and we denote ( as the optimal solutions to the saddle point problem eq. (и))
We solve the saddle-point problem eq. ( iteratively, and for each iteration f. E [T], we alternatively update iterates of the primal variable मे. and the dual variable 7t_ The primal update is
k = arg max T. (s1) - X (v. (Vig(s)) - 6)) = arg max D= 1.7- 144 (81),
(8)
5

---

where the last equality follows from lemma 15 By augmenting rewards with the Lagrhnge-weighted costs, the policy Rf can be solved with backward updates, allowing us to decouple V from Ph- However, the value estimates 77 now depend on the dual variable x that takes continuous values. To retain tractable union bounds in the analysis, we must restrict À to a discrete set. Specifically, we update the dual variable by performing single gradient descent step with step size 17. We then discretize the values by rounding the gradient descent result to the nearest element in e-net {0, E 2,,, J. The resulting dual update is
N RA [ +
-s)
(9)
where (A( arg min 1p A| is rounding function.
Algorithm 1: Model-based algorithm for online CMDP
Input: S, A, H. K, r, Ç, D', C1 460/9, 544/9. 17 HVT T, U,,
Initialization :for all [K], X/ 0, for all (s, s', h), set Nn,s,,, 0,)) +- 0, (s, a. 8') < (s, 0; for all x, set Vi (s)) t 0, (s) H.
for k = 1, ... K do
for 1,... do
a/ = arg max, Va (s (s
X/41 RA 13p
n pat (ot))]
ck Th = 11=1 "
for h = 1.... H do
Observe sh, take action at ~ म (-1s/t) receive r, of, observe & 8/41
(s) t sh ah. s
(x) t (s, + (s, ass.a,s) s') + (n(s,,,s') +1
if N (1,2,4, ..... 2 K then
a)(ss + -; (,
(L),((3) TRIGGERED + TRUE
a,, t 0
if TRIGGERED then TRIGGERED + FALSE 1
Vz S for h = H. - 1,.... do
for (8,a) E x A and any x do
(s, = minfra(s,a)) + k... h.r
(s. + P..a, V7 1 1
(x) = E.EA (a)ls)
(s) = maxfcn (s, kki. (s, + P. Po.a, v Viti 0}
(r = EaEA (als)) (8,a)
return क R Σk=1 x
Finally, we state our algorithm in algorithm MI For each episode, we first execute iterations of primal and dual updates. The agent executes the mixture policy & and receives the reward, cost, and the next state. We update the empirical model using the doubling technique as described before. In the end, the algorithm outputs the mixture policy that mixes all intermediate policies.
Main Results and Analysis
We first present the regret and constraint violation bounds of our algorithm and proofs, while we leave intermediate lemmas and proofs used to support the main results in the appendix.

---

5.1 Regret and constraint violation results
Theorem (Regret bound of algorithm M1 for relaxed feasibility), Let b' b T in algorithm for some > 0. With probability at least 1 ō, the regret of algorithm B is
Regret(K) Ō (VSAH +2 +
H²K
TVT
Proof. Recall the definition of regret: Regret(K) = - (Vi, VI. (ot)) Note that x² is
the optimal solution to the original CMDP optimization problem eq. (I), while for each episode * is an approximation solution to the empirical CMDP optimization problem eq. (8). To cope with the gap between the two policies, we introduce a proxy policy T.* defined as the optimal solution to the following optimization problem
π
E arg max VI, (s1), s.t.
Vi,c(t)) S =b
(10)
x
We decompose the regret as
K
K
Regret(K) (K) = Σ
-V, (of))
V (s - D1. (ot)
k=
K
Σ k=
Va (st) - (1
Virk (s - VI, (st))
+
R=
and give the regret bound by bounding each term above. The first term the error incurred by replacing the original constraint constant b by relaxed empirical constraint constant t' = 6 + 5 for each episode k. Note that by definition of x², we have (s1) S b < b' Thus by definition of T.**
in eq. (IIL), have V (s1) 2 Vi,, Hence, bound the first term by 0: Σ VE (o4)) O.
k== (Vi,, (st)
By definition of the proxy policy T in eq. (II)) and noting that T is predetermined constant, we see that T. a fixed policy that independent of the online learning process. Thus we can apply
lemma IIG and bound the second term by 0: Σ k=1 (Vr,"" (o+) V (sf) O.
The third term is the optimization error, and it is incurred because x is an approximation solution generated by iterative primal-dual updates. We bound this term by using the primal update rules in lemma Z and also by lemmas I and 12 we have
K
V (s Vi. (st) S HKVT+ UHK VT 2K +
H'K TVT
Σ 1=1
Finally, the last term in the regret decomposition is the model prediction error, consisting of the errors caused by inaccurate empirical models and additional bonus terms. Worth mentioning, this term is essentially similar to the entire regret in [TS]] as the algorithms share the similar exploration bonus and update rules for transition models. We state in lemma E the bound with probability 8,
Vi. V
VI. (6)) = Ö(VSAHKK)
(11)
Putting everything together, we conclude our desired regret bound.
Theorem 2 (Regret bound of algorithm II for strict feasibility). Let b' = b A in algorithm for some A > 0. With probability at least - 5, the regret of algorithm M is
A Regret( K) Ō(VSAHSA + HK 2$1 AK
H²K
(c- A)
7

---

Proof. The proof to theorem D follows the similar idea as the proof to theorem MI Again, we intro- duce a proxy policy x².* defined as the optimal solution the following optimization problem
arg max Vi,, (s,)
s.t. (i,c(s) 5 = b.
(12)
We decompose the regret as
K
K
Regret(K)
Σ
(s))
- Vi.rr (sf) +
Σ
V (s V (0f)
V
1=1
k=
K
K
Vi (5)) PIF (o4)
VT (sf) - VI (df));
A=1
k=1
and give the regret bound by bounding each term above. The first term the error incurred by replacing the original constraint constant b by more restrictive empirical constraint constant d' b A for each episode k: We bound the first term in lemma II:
K
Σ
(Vi,
VTr (5 - HK.
(13)
For the second term, we use the similar argument in the proof to theorem MI By definition of the proxy policy π A. in eq. (I2)), and noting that A is a predetermined constant, we see that n is a fixed policy that is independent of the online learning process. Thus we apply lemma [T and
bound the second term by O: Σ (VE," (s/) 1 (s S.O. O.
The last two terms can be bounded with the argument as in the proof to theorem II Putting everything together, we conclude the regret bound in the strict feasibility setting.
Theorem 3 (Constraint violation bound of algorithm for relaxed feasibility). Let V' = b t in algorithu for some > O. With probability at least 1 - 6, the constraint violation of algorithm M
CV(K) = ÖVVSAHK + 28, H HWTT++UHVV
K Kr).
U- U-H
Proof. Recall the definition of constraint violation and we decompose as follows:
CV(K)
Σ VIO (+ )b)
K
Σ (v) -prt) (3)) Σ (ot) -8) 6) + u 6)
For the first term, by definition of optimistically biased estimates of rewards and cost, note that the analysis of bounding Σx Vi, (sf) VI. (af) and Ee Dat (st) VI,* (sf) are analogous, and mostly identical. Hence, by lemma we have
Σ (VT (T)()) S ŌÖ(SAHHK)
(14)
with probability at least SAHK8'.
The second term is the optimization error in the primal-dual process. We calculate & as an approx- imate solution to the empirical optimization problem defined in eq. @.. Thus, it is not necessarily satisfied that D (st) < b'. We hence return to the analysis of the primal-dual framework, and adapt techniques used in [26, [8]. By lemmas M [4L have
2 HTT +UHIVT K, U U-H/T
Vir (x B) 5 Σ (
(0)) (x)) V
For the third term, we recall the definition of V/, and we have Σk=1 (V everything together, we have the desired upper bound on constraint violation.
b) Kr. Finally, putting
L
8

---

Theorem 4 (Constraint violation bound of algorithm W1 for strict feasibility). Let b' b - A for
some A 0. With probability at least 1 8. the constraint violation of algorithm is
CV(K)= OVVSAK 2 + +UH/T K KA).
U- - C-HH(S--))
Proof. We decompose the violation similarly as in the proof to theorem [ and note that the first two terms can be bounded using the same argument. Then, recall V/ = b A, and we immediately have the upper bound on constraint violation for strict feasibility.
5.2 Sample complexity bounds
We present the sample complexity bounds of algorithm II We derive these bounds by converting them from the regret and constraint violation upper bounds presented above.
Theorem (Sample complexity of algorithm 0 for relaxed feasibilityy. For a fixed (0, H| and 6 (0, with K = =Ö (SAAT T O
H
U O (#) E1 O
63 and 3.
algorithm I returns a policy गे that satisfies eq. (G) with probability 6.
Proof. Note that = K Ek=1 Th is mixture policy, and we have
K
(1)) - v(,,()) = Regret(K) ())
(1) - V (1)
K
K
k=1
and
Vi- Vi- (81) -b) 5 CV(K) K
(i,o(11) -
K
k=1
By setting K Ō Ō SAH" z²
T = 00 11
U = - ( 0 and 1. with proper
coefficients we have Vi, (s1) - (s) S E, and (11) b S E.
Theorem D shows the sample complexity of algorithm M is Ō SAH in the relaxed feasibility
setting. For unconstrained MDPs with online access, provided lower bound of Ω (AA for s-optimal policy identification. We thus conclude that learning online CMDPs in the relaxed feasibility setting as easy as learning unconstrained MDPs.
Theorem 6 (Sample complexity of algorithm DI for strict feasibility). For a fixed E E (0, H c]
and 8 (0,1), with K- = Ö SSA T o #
U U= H²
((H-T)) E1 0
2 and
ECC
2H algorithm returns a policy से that satisfies eq.
(+) with probability 1 8.
Proof. The proof is mostly the same as the proof to theorem B
(ii((1)) - (s.. (vit((s) - Vi. (81) Regret K)
K
and
K
(TT -6) < -CV(K)
V (i(((1)) -
K
K
k=1
By setting K Ō SAH' 522
T T
0 11
U 0 H²² 81 0 0 (2(2) (22²))
and A Cc
([H-
27
with proper coefficients, we have (i,)
(8, (81) S S, and V (x1) - b 50 0.

---

Theorem E shows the sample complexity of algorithm is Ō
SAH 6²C²
in the strict feasibility setting.
With access to a generative model, [[S] provided a lower bound Ω
(1->) for infinite-
horizon discounted CMDPs, which translates to Ω (AAH" for episodic CMDPs. Note that this c²<²
lower bound can be readily applied to learning with online access: Suppose there exists online algorithm s/ achieving better sample complexity than the lower bound for the random access setting. Since trajectories generated in the online setting can be simulated with a generative model, we can easily construct a sampling scheme with the generative model using a as a subroutine. This contradicts the lower bound. We thus conclude that in the strict feasibility setting, learning CMDPs with online access is as easy as learning CMDPs with random access.
Acknowledgement
Chang Liu, Yunfan Li, and Lin Yang are supported in part by NSF Grant 2221871 and an Amazon Faculty Award.
References
[1] Jun Wang, Li Zhang, Yanjun Huang, and Jian Zhao. Safety of autonomous vehicles. Journal of advanced transportation, 2020(1): 2020.
[2] Charles Vincent, Susan Burnett, and Jane Carthey, Safety measurement and monitoring in healthcare: framework to guide clinical teams and healthcare organisations in maintaining safety. BMJ quality & safety, 23(8):670-677, 2014.
[3] José Machado, Eurico Seabra, José C Campos, Filomena Soares, and Celina P Leão. Safe controllers design for industrial automation systems. Computers & Industrial Engineering, 60 (4):635-63,, 2011.
[4] Eitan Altman. Constrained Markov Decision Processes. CRC Press, 1999.
[5] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovie. Prov- ably efficient safe exploration via primal-dual policy optimization. In International conference on artificial intelligence and statistics, pages 3304-3312, PMLR, 2021.
[6] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exxloittton in constrained mdps, 2020. URL httpt://aa//iii..cot org 20t.//bbb/02220..2 02189
[7] Alessandro Calò, Paolo Arcaini, Shaukat Ali, Florian Hauer, and Fuyuki Ishikawa. Generating avoidable collision scenarios for testing autonomous driving systems. In 2020 IEEE 13th International Conference on Software Testing, Validation and Verification (ICST), pages 375- 386. IEEE, 2020.
[8] Barbara CN Müller, Xin Gao, Sari RR Nijssen, and Tom GE Damen. robot: How human appearance and mind attribution relate to the perceived danger of robots. International Journal of Social Robotics, 13:691-701 2021.
[9] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International conference machine learning, pages 263-272. PMLR, 2017.
[10] Chi Jin, Zeyuan AlennZZhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning prov- ably efficient? In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL httph: httpss://proceeeingss.. inw..eeeeeddddngnnnnrrirrpp.p neurips............. cc/paper ficaaper_fleeee files/paper/ pdf..
[11] Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. In Proceedings of the 32nd International Conference Algorithmic Learning Theory. PMLR, 2021.
10

---

[12] Zihan Zhang, Xiangyang Ji, and Simon Du Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In Proceedings of Thirty Fourth Conference on Learning Theory. PMLR, 2021.
[13] Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. UCB Mo- mentum Q-learning: Correcting the bias without forgetting. In International Conference on Machine Learning, Vienna / Virtual, Austria, 2021.
[14) Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. In Proceedings of the 35th Inter- national Conference on Neural Information Processing Systems, NIPS '21, Red Hook, NY, USA, 2021.
[15] Zihan Zhang, Yuxin Chen, Jason D Lee, and Simon S Du. Settling the sample complexity of online reinforcement learning. In Proceedings of Thirty Seventh Conference on Learning Theory, Proceedings of Machine Learning Research. PMLR, 2024.
[16] Tao Liu, Ruida Zhou, Dileep Kalathil, P. R. Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS '21, 2021.
[17] Archana Bura, Aria Hasanzade Zonuzy, Dileep Kalathil, Srinivas Shakkottai, and Jean- Francois Chamberland. Dope: doubly optimistic and pessimistic exploration for safe reinforce- ment learning. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS 22, 2022.
[18] Sharan Vaswani, Lin Yang, and Csaba Szepesvári. Near-optimal sample complexity bounds for constrained MDPs. In Advances in Neural Information Processing Systems, 2022.
[19] Tiancheng Yu, Yi Tian, Jingzhao Zhang, and Suvrit Sra. Provably efficient algorithms for multi- objective competitive rl. In Proceedings of the 38th International Conference Machine Learning. PMLR, 2021.
[20] Fan Chen, Junyu Zhang, and Zaiwen Wen. A near-optimal primal-dual method for off-policy learning in cmdp. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, 2022.
[21] Aria HasanzadeZonnzzy Archana Bura, Dileep M. Kalathil, and Srinivas Shakkottai. Learning with safety constraints: Sample complexity of reinforcement learning for constrained mdps. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021. AAAI Press, 2021.
[22] Washim Uddin Mondal and Vaneet Aggarwal. Sample-efficient constrained reinforcement learning with general parameterization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[23] Jiashuo Jiang and Yinyu Ye. Achieving ( sample complexity for con- strained markov decision process. In The Thirty-eighte Annual Conference on Neural Informa- tion Processing Systems, 2024.
[24] Arnob Ghosh. Sample complexity for obtaining sub- sub-optimality and violation bound for distri- butionally robust constrained MDP. In First Reinforcement Learning Safety Workshop, 2024.
[25] Dong Yin. Botao Hao, Yasin -adkkr,, Nevena Lazić, and Csaba Szepesvári. Effi- cient local planning with linear function approximation. In Proceedings of The 33rd Inter- national Conference on Algorithmic Learning Theory, Proceedings of Machine Learning Re- search, pages 1165 1192. PMLR, 2022.
[26] Arushi Jain, Sharan Vaswani, Reza Babanezhad Harikandeh, Csaba Szepesvári, and Doina Precup. Towards painless policy optimization for constrained MDPs. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022.
[27] Santiago Paternain, Luiz F. O. Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Con- strained reinforcement learning has zero duality gap. In Proceedings of the 33rd International Conference Neural Information Processing Systems, 2019.

---

[28] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo R. Jovanović. Provably efficient safe exploration via primal-dual policy optimization. In International Con- ference on Artificial Intelligence and Statistics, 2020.
[29] Xiaohan Wei, Hao Yu, and Michael J. Neely. Online primal-dual mirror descent under stochas- tie constraints. In Abstracts of the 2020 SICMETRICSPPrformanee Joint International Con- ference on Measurement and Modeling of Computer Systems, 2020.
[30] Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo Jovanovie. Natural policy gra- dient primal-dual method for constrained markov decision processes. In Advances in Neural Information Processing Systems, 2020.
[31] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In Proceedings of the 34th International Conference on Machine Learning Volume 70, 2017.
[32] Chen Tessler, Daniel J. Mankowitz, and Shie Mannor. Reward constrained policy optimization. In International Conference on Learning Representations, 2019.
[33] Adam Stooke, Joshua Achiam, and Pieter Abbeel. Responsive safety in reinforcement learning by pid lagrangian methods. In Proceedings of the 37th International Conference Machine Learning, 2020.
[34] Tian Tian, Lin F Yang, and Csaba Szepesvári. Confident natural policy gradient for local planning in rerllizze constrained mdps. arXiv preprint 240.22200.88829 2024.
[35] Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Towards achieving sub-linear regret and hard constraint violation in model-free RL. In Proceedings of The 27th International Conference on Artificial Intelligence and Statisties, 2024.
[36] Akifumi Wachi and Yanan Sui. Safe reinforcement learning in constrained markov decision processes. In Proceedings of the 37th International Conference Machine Learning, 2020.
[37] Sanae Amani, Christos Thrampoulidis, and Lin Yang. Safe reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 243-253. PMLR, 2021.
[38] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
[39] Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed horizon reinforce- ment learning. Advances Neural Information Processing Systems, 28. 2015.
[40] Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for re- inforcement learning? In International conference machine learning, pages 2701-2710. PMLR, 2017.
[41] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
[42] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1600, 2010.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The contributions and scope of this paper are included in both the abstract
and the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of this work are discussed in the related work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The au- thors should reflect 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 on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play 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]
13

---

For all main results of this paper, the proof sketch is provided in the main paper, and the complete proof and auxiliary lemmas are included in the appendix, numbered and referenced.
Justification:
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 theo- rems.
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 a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer 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 a dataset and/or model, the authors should describe the steps taken make their results reproducible 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 the contribution it may be necessary to either make it 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, other means that are appropriate the research performed.
specific model and empirical evaluation,
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
14

---

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

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of eπrоrs 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 of range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it 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 http:////waaappscccccccccc/cccac
Answer: [Yes]
Justification: The research conducted in this paper conform in every respect with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is 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: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
16

---

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

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, 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 deseribe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) 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 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.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy ottpas///eaarrrsscccc//oorrreere for what should or should be described.
19

---

A Regret Analysis
Lemma 1. Let A be defined as in eq. (22, then
(s) Vi, (st) = 5
A HK.
Proof. Recall the definition
22c = arg max (+1);
and < <= 1 (+1). For each episode k. we define a fixed policy = = (1 (1- + - and its value function satisfies
A Vite (s1) (1 5 Vioo(s))
A (s1( s (1 (1-2)2++ v0 A (6 () - A.
5
Then.
K -V,,r" (sf)
(o) - 1,r
K
(ot) -ViA (st)
K
(ot)((h) - (1- + 2 V (d9)
(st, (++))
HK,
where the first inequality is due to the definition of A i.e., for any policy n, s.t. V.T, (81) SV
b A, VT. (s1) 2 (s1,, and the second inequality follows from (s, S H.
Lemma 2. Let n² be the mixture policy in algorithm i T and n be defined as in eqs. (III and (l2), then
K
Vi (sf) - -i S 28, HVT +
UH VT
A=1
and
K
Vir b. ( - Dif((s)) < 22i,HVT+ + UH
VT
Proof. For any primal-dual iteration 1 E [T].
VIF (sf) - X.. 1.g (s/) S (it - X3 x (of).
Taking average over T iterations.
1 T
1 Σ T (st) XiVITe (st)
<
Σ
(i
34 (ot))
T
Note that the mixture policy - is the average policies of #f, we have
1 T
T 1
DIF (++)
+
V (s S
VI
Σ
(15)
20

---

Further, we notice that
Pre S 1,0
SV.
(16)
Thus, for any episode k,
V (sf) - D (af)
T
1 T
Vi.2" (sf)
X
X (ot)
(of)
T 1=1
T
1.
t=1
T
+
Xx
(VT
T
[=1
T
X (Vi.e
(st)
(
T
<
Σ
2/ (s+))
2M, UH
VT
where the first inequality follows from eq. (L5) the second inequality follows from eq. (I.), and the last inequality follows from lemma 44 by letting x = 0 The proof for n. is analogous and is thus omitted.
Lemma 3.
K
V ViF
(5f)
(6t) = Ō(VSAH3K)
Proof.
By definition, we write
(sh) = Σ (als (a
aEA
Qi att) + Σ St
@ at)
AEA
< rs att + (8 at)) + Pok Vist 1+1,F + of
shing in
S (s at) + (sh at) + (pt.
ot - Ps, Paaan 1 + (Pot - 11 [ottn (ottnn)) P
Dart
V 7 (8h+1) $h.
where
di = Σ x (als)) - (h
AaEA
is zero-mean random variable conditional on t Then by summing over H time steps and tele- scoping, we have
(5t) S
Σ h=1
(s k att + (/ att + sfa
(PL
Pann))
(P aa A - Ilokert 1) Vitta
+
Pam
21

---

The term we want to bound is now decomposed as
H
K
H
H
Vir (+t) - VT. (of)
Ph of
Psaa))
Σ A=1b=1
1=
h=14=1
K
H
K
H
Σ
rn( att - Vi (0f)
Lo
1+1.7
kml
Amm
We apply lemmas 91 5 and 7 to M. and contude that with probability 1
((V SAHS& log SAHH
V (5 V (o4) =0
5
Lemma 4. With probability at least 3SAHKö,
(sh a S Ō(VSAIKK)
Proof. By definition of bonus
(5h at)). we have
K H
k,x" hnr
(sh,
460
Pk shoof, hi 1.1.7) NW (sh a%)
D
log 5'
544
H log f N (sh a%)
9
9
k=14=1
k.
k,h
Applying the Cauchy-Schwand inequality and lemma IA we obtain
K
k.n Whr
(sh
460
log + (sh a
Σ k.
Dk
Drck 1,
9
N
V
k=
544H log
9
N (s at))
460
25AH (log, K) 1og 11
1)
(pk
shaagh P
9
81)
(
k.h
1088
SAH² (loge K) K)log 1
+
gr.
Then by lemma 10 we have the desired result.
Lemma S.
K
H
Pk a - Pe Pean) S Ö(VSAH2K)
Proof. First we notice that nh is mixture policy of म = = En 2t, then we have
K
H
K
Pt oha
P.an))
p
Pa.att Σ
h+1F
11
h=1
T
K
H
Pk oo
Ps.a, h41.7
) DEz
D Note that given a total profile I E C and a dual variable sequence À E A, A+1, determined by
pllia (Ik (fhaw) (s, Ci f (s,a)
(1t (Itm.r)
elal .rw
22

---

and || 141,7ll00 S H. Thus we can invoke lemma a also by lemma III. we have
Pk F Pao, S Ō(VSAIIK).
Lemma 6. Let us first specify the types of vectors {Xh,s.). For each total profile I & C, consider any set (R ISSSH obeying: for each S H,
I given by a deterministic
of a dual variable X A, and
plltaw)) (1" (1h...)
(1 (f (s. s,0," ,Th. (s,a), Opl
| S for each vector X E Xn.I
Xn is a set of no more than K + non-negative vectors in TR., and contains the all-zero vector 0.
Suppose that 2 SAH K, and construct a set {Hr,I) IghS for each I E C. satisfying the
above properties. Then with probability at least - 8',
Σ
(D
Pa,,, Xht1sa)
E
max { s.a.
- Pa,a, N1+1,,
s,a,
5,0,hE5xAx(H]
s,a.hESxAx(1E)
8
Σ V (Psass (6SAH log2 K) + 21-2 (6SAH log K)
4H
2 8.0.h
holds simultaneously for all I E C, all dual variable sequences, all 2 < 1 < log, K + 1, and all sequences
obeying Xb,s E K,+1I, V(s, a, h) E A x H
Proof. This proof is adapted from the proof to lemma 6 in [1.5]. Let us begin by considering any fixed total profile I E C. any fixed integer obeying 2 < S log, K 1, and any given feasible sequence (Xn,s,a) ( (e.o..))SSxxx(I1) Recall that (i) p(1) is computed based on the I-th batch of data s.a.h comprising 21-2 independent samples; and (ii) each Xa-1.s.a is given by a deterministic function of I and the empirical models for steps h' E [h + 1, H). Consequently, lemma I8 tells us that: with probability at least 1 - 8', one has
Σ
(D0) (p)
a,a.h Ps.a, Xn+1,s,)
8
3 3log, (SAHK)
4H 2--2 log
3 3 (SAHK)
Σ V (Pa X1+1, log
21-2
8'
8.a.
where we view the left-hand side martingale sequence from H back to h 1. Moreover, given that each Xa.s has at most K + different choices (since we assume |Kr,z| < K + ), there are no more than (K + SAH < (2K)SAH possible choices of the feasible sequence (Xn.saa (s....) In addition, has been shown Lemma 5 of [[SS] that there are no more than A4S log, K possibilities of the total profile I. Taking the union bound over all these choices and replacing 8' with 8'/ (4AAHH))2AA) log, K (2K) log, K K|A/K)) we can demonstrate that with probability at least 8',
Σ 8.0.h
p(O S -Ps Xn+1,0,)
4H Σ V ((Psaah- (6SAH log? K) + 21-2 (6SAH log3 K)
(
21-2
8.a.k
23

---

holds simultaneously for all I E C, all dual variable sequences, all v 1 5 log, K + 1, and all feasible sequences (Xn,,s,) (s., ( Finally, recalling our assumption 0 1h+1, we see that for every total profile I and its associated feasible sequence {Kh,s,a}
Σ max ( Pe.a,h: Xntie,,) E
Σ
p(D) s,a
Pe,,, Xb-L Xn+1aa E X V(s,a,))
5,a,A
holds true. Consequently, the uniform upper bound on the right-hand side continues to be valid upper bound on Es,a, max { (550 s,a.h Pa.ah X1+1800) 0). This concludes the proof.
Lemma 7, With probability at least 48' log((KH)
"
ΣΣ
t S Ō(VH3K).
k=1
Proof. Note that 0% n
a) Q7: af) is zero-mean random vari-
able conditional The and is upper bounded by constant H. By lemma IT] have
K
H
K
222
Var(o)) log 8 + 3/H log 8'
A=1
+ 3H log 1 8 2K H3 log 8
1
2
with probability at least 46' log( (H)-
Lemma 8. With probability least SAH1"288
K H
ΣΣ
(P (Paaat
- 1, V S Ō((H²K).
Proof. We note that conditional on state-action pair (s ) the vectors P "aaaat h and 1 1 are both independent of the value function estimate V k+1,F- Also, the vector 1 1 has the mean of P af Hence, (Pat 1,k F is a zero-mean random variable bounded by H from above, and we thus apply lemma II and have
K P. 1
V WHIFF S 2
Σ
ΣΣvR v
(P..aaa
1 + 3H log Vit1..)) log
1 8
with probability at least SAH2K28 By lemma IIC obtain our lemma.
Lemma 9. With probability at least
48' log(KH).
Σ
Σ
(n att VT," (st( S {Ō(VHK).
Proof. Note that conditional R Eg = EH (5t att variable upper bounded by constant H. By lemma IN, we have
Vi," (sf) is zero-mean random
Σ E A=
2
Varl Ex log 8' + 3H +H 1
1
< 2
2K H2 log + 3H log 8'
with probability at least - 48' log (H), where the last incquality holds because E&l < H.

---

Lemma 10. With probability at least 1 6SAHK8,
(P Po Vitl.))
k=1b=1
ΣV (e
SŌ(H' + VHOK SAH)).
Proof. This proof is modified from the proof to lemma 11 in [15], and we show here the parts where the proofs differ. First we write by direct calculation
K
H
K
H
(P
ah Vatt
(P ( (+
Dart ( ahiahi (411.)
1=
1=1
Am1
Pk
P oh (V
pk
1st (V
k=1
K
2
2
k=1k=1
K
K
H
Ph sh n: (P
pk
Loter' (P
#= h=1
R= h=
( (Poh VhtLF))
(Vi
and since the value function estimates are bounded by H,
K H
-p
pk
1 Iottr (Pxt2.+2))
2H
(P (Potiotii
Dirk
1+ o}
K
H
Ph
(Drt ah
(V
+
pk
Ister (Pxt1.5t))
A= 1 hml
Amm
K
(xn((s))
( att + (Tt att - (Pot at Pa 0).
+H
max
k=1k=1
By definition of update rule of @ functions, we have
H
Pk
Pk ok A: (1
(Drt
pk
1 in (D (+
h=1
K
H
K H
K H
+ 2H
(s a + +H
k hir
(s% a
+ 2H
Σ
max 0},
k= 1=1
k=1 1=1
where </ = V ( at)
EnEA tt (als QT
(
a is zero-mean
random variable conditional on x bounded by H. By the results of lemma 10 and in [15], we finally bound
v (pt (P Vati.7)
SŌHHK -
1=1
25

---

Similarly we can show that with probability at least 1 - -3SHAKK,
K
Hf
1
Pettatthh Vo+1,7)
P of (Vh++1)* )2)
ΣΣ
(Pot Vhe )
k=1b=1
k=1 1=
k=1/=1
K
H
K
H
K H
P ahatthhh - -o (Vitta)
(V (sh))²
(Pttoat V Vitta)
+
k=
k=1 h=2
1=1
and we invoke the similar argument above,
K
H
K
H
Pag aa h - 1 ott (Vi+1) )²) + 2H
max V/h (sh) - -Poot Vitti .03
1=1
h=1
k= h=1
K
H
Pst Saa 1 Loter (Vi+t)²)
+ 2H
max V/2 (sh) (Pot Vitt).
1= hm1
k= A=1
Σ max {
(ph sf
Pay Pak.ag,as Vitt),0)
+ 2H
A= /=1
K
H
K + 2/1
K H
P. Pajiatth - 1. A (Vi+zz))
(s at) + 211
Σ
hor
(0% aft
1= hm
1m 1 h=1
1m 1 1m
H
+ 2H
max 0) + 2H
Σ max {
Pat (ott
k=14=1
By the results of lemma 10 and 11 in [15]], we finally bound
K
H
v
(Potiatiio vot1,) < <Ō VH SAH
k=1b=
B Primal-dual Optimization Analysis
Lemma 11. For the relaxed feasibiliiy setting, let b' = b for some T O, we have
H X S T
For the strict feasibility setting, let V = b- A, for some A E (O, we have
N H
A
Proof. Writing the empirical CMDP eq. (6) in its Lagrangian form,
i (sf) = max min (+(()) > (vr. (st)
" X20
Using the linear programming formulation of CMDPs in terms of the state-occupancy measures we know that both the objective and the constraint are linear functions of μr, and strong duality holds w.r.t. μ. Since and have a one-to-one mapping, we can switch the min and the max, implying,
1.F
(sf)
min max
(T)(())) > (Vr,((st) b'
X
Since t is the optimal dual variable for the empirical CMDP in eq. (6) and recall x. arg max, - (s)), we have
VI, (sf) = max (it((s))) - * (V) b²)
(s - -x-- (Viz (s -b')
= ((ft + R (w b) + (b Vila (sf)) + (VTE( PT
26

---

Note that के is fixed policy and by lemma IG we have Vi
Vic (sf) 2 0. Recall that
Ç ==b VI, ($1), and we have
z (st) + x
+)-
For the relaxed feasibility setting, we let V/ = b + T for some 7 > 0. Then we have
V 1. (o+) - Vi
H
T T
Note that the shift T > is introduced to get rid of ( in the results of the relaxed feasibility setting,
For the strict feasibility setting, let D' = A for some A (0,5), we have
V (x+) (s+)
H
A 5
A
Lemma 12. Let U >> Rhit and for any ग. s.f.
V (54) (5)) + U
V (Fic((t)- -b) s B,
we have
(s)) - b/ 1 U A
B
Proof. Define v(T) = max, (77)((f) (rg(()) < V- - 7 and note that by definition, v(0) =
Vak (sf), and that v is a decreasing function for its argument. Then, for any policy π s.t. Vr,( S
1.F
D' - 7, we have
Vir(oh) - It (Vr.((()))))) - b¹) S max Vi X (st) -b)
-i (sf) X (sf) b')
Vi, (sf) v(0) (by strong duality)
This further implies
M(0) - - 2 Vi 7tit (1ig (5t) - b¹) Xtit
-Vi I (Viz (st) - (b' -7)
Since this holds for any policy л s.t. Dir, (st) - b' 7 we have
v(0) - Xt-0 2 max (s)) (i) 26
and thus
24ir s <v(0) vv7))
Now we choose
7 = 15 1.g (0)) -))))) 1++
U x = 84:7 + URl
v(0) (17) UFA
VEF (sf) - ( - -v(7)
-DAT" (of) - +=( - 1/+ + VT.((1)- (7(
< B + (1) ((7)
27

---

Now let us bound (1)):
m(7) max Vi,F(s) (sf( < + (V - b)++
max m (5)) ( s Vig(())) (tightening the constraint)
2 v (s
Finally,
U - -B = (s) - 6') -
Ak.
Lemma 13.
T (b
Vi 1,F
- (5) + A (s)
b') S - Σ ( -
t=1
Proof. For any episode is and any time step in the primal-dual iterations, the primal update ensures that for any policy r,
(+) (of) b²) 2 PEA(()) (1 6')
Let π be pk.* and rearrange:
V (5 (6f) S (
1. (sf) - Did (ot)).
Note that * is the solution to the empirical CMDP in eq. (6) thus VT (st) s V. and we have
V (st) 1 (st S 2
i. (st)).
Take average over I' iterations,
1 T
1 T
Patee 1,F
(of) - D&t (6))
7
Σ
X
8
(ee (ot)
-
T
1=1
To use lemma 14, we rewrite as
T +
E x Vic
( (sf) - b)
S T Σ o - ^)
D ( (of)
Note that 4 (s/) is constant throughout T primal-dual iterations, and n² is mixture policy, then
V (of) V + A (ir (sf) -B¹) - Σ (2 2) (b' 1)
Dia (st))
V HVT updates in eqs. (g) and (H), we have
Lemma 14. Recall we set =
For any episode k, any X E [0, UJ, and primal and dual
1
X
(1- s 28T
UH VT
T
Proof. In this proof, for the simplicity of notations, we will only focus on primal-dual iterations in an arbitrary episode & E [K], and thus we will drop all dependency on & when the context is clear. The dual update is given by
Res1 = RR n VT (s1)))
28

---

Particularly, we denote
N/41 = P - n(6' -1b6-1,77 -V(((s))]-
First, we shall look at 12x - A/:
But1 21 IRA | X/ (RA(X/+111 N/t1 + X/+1 A
- A (2/ - -++1+++ 17++1 -
51 + 18/+1 - 2/.
Take square on both sides,
Pet1 X/2 S e + 28, P241 - X/+ 18241 2/2
5 + 23 + 18/41 -22
< < + 2 + 1i -n(b' 17 (ig((1)) - 212
= o + 22/0 + 1o - 2/2 - 2n(6' - ())(() - +/ - ()
< o + 2 + Ae - 212 - 20 - -
Now we have
of+ 22+2 + T
[Nc -22-112-0 - 17et1 - 212
- - - (s1) S
2m
217
By taking average over T iterations and telescoping, we have
o7 + U + H22
|^1 A12
- -IT+11 - 2/2
T Σ 2)(6 - (s1)) <
2m
2n/T'
c7 + 221 U + ?22 H
1A1 212
21
2n/T
c7 + 2 U + n H²
U
21
2n/T
20
nH² + 2n/T
U
1
UH
= 26, Hv +
TT
C
Useful Lemmas
Lemma 15 (Primal update). We re-state the primal update in eq. (8):
arg max (11) 2/ (Vig(()) -6) aar max Vx
155 (81).
Proof.
Note the estimate value functions Viz, of any reward-like function g g:Sx A R is given
by:
H
(T) = EF
Σ
g(S, A.) = =8
29

---

Then we have
bे. arg max (1)( - X/ ( ((1)(())= -
H
arg max F
Σ F(S,. =1
Xx Epp
Σ
c(Sr A.) $1 + X/ b'.
arg max Ep
A)), = 51
arg max 1--MP (51),
T
where the second- to-last equality follows from the linearity of expectation and reward- like functions, and the last equality follows from the definition of estimate value functions.
Lemma 16 (Optimism). With probability at least 28', for any fixed policy n, reward function and 8 E S, h E [M]. we have
Vigg(s) (5) 2 Vig(() (s).
Proof. First, we define the following function
20
V(p. v) log 5' 400 H log 8
v = (p, v) + max
3
n
for any vector p E A any non-negative vector E R$ obeying integer n. We claim that
||l| S H, and any positive
(p, v, n) is non-decreasing in each entry of v.
(17)
To justify this claim, consider any 1 1 8 S S, and let us freeze p, and all but the 8-th entries of e. It then suffices to observe that (i) is continuous function, and (ii) except for most two possible
choices of v(s) that obey calculate
20 3
V(p.v)log #
400 H log one can use the properties of p and v to
(p, v. n) 0r(s)
20
V(p v) log
400 H log
p(s)(o(s) - (p. u))/ log 1 VnV(p,)) v)
p(s) 3
3
n
n
= =p(s) +1 -1
{ NV v) log
1
20
1
20 H log 8
p(s)(((s) (p,v))
log 8
8
3
nV v) log 11
2 min {p(s) + pps)) (u(s) - (p) -(s))
H
2 p() min { H + v(8) ((b)
up u)
20, 0.
H
thus establishing the claim. We now proceed to the proof of lemma [T.. Consider any kh s, a). and we divide into two cases.
Case 1: (s, S 2. In this case, the following trivial bounds arise directly from the value function initiation:
(s. a) 0 ON.g(saa) (T) H 2 (h
(i) H 2 V (s) 2 0 Vi (ig(()) (s).
Case 2: (), > 2. Suppose now that Q Qu+11 2 1h+1. 2 Q which also implies that
Vitig 2 hiigg 2 Vitig If (h)(s,a) = H. then (s,g( 2 Qi. (s, a) holds trivially, and
30

---

hence it suffices to look at the case with Qh (s, <
H. According to the update rule, it holds that
(s.)(
+ (Paans as) Vhit1) tai
V Pt.
s,a,
V (s,a)
1+1.5
log 0
log 5 No (s,
02
(18)
48H 1sHlog 87
+ (Pt sea 1i
(g,
( (s,
(8) + 48H log
+ (P Vit N (s.a))
(s,
for any (s, a), where the last inequality results from the claim (eq. (IT) and the hypothesis Vē+13" V 1+1.. Moreover, applying Lemma 19, have
Vir V Pi s, V141.g)
log 14H log 1 (s.
( (Pea. Poyarrs (kttoo)>>
(s)
<
po s,ah - Ps,a,h Vittool>>
2V
V saa, V1+1,
log 87
7H log 37 (N,
< 28'.
(s) -1
This implies that with probability least 1 - 28';
f (Pha, 1i+... (/(ss = (Pesoon vi-- + + - Peoa, Vitt.s)
V
Pk
s,0,h ( log 37 400 H log 0 No
20
+ max
3
(s,
2 (P V Vh+i.g)
Substitution into eq. (ES) gives: with probability at least 1 - 28',
(T,(6,a) 2 go (s, a) (Pa.a,t, Vi+1,g) = (h,
The proof for Q 2 2% is analogous and we leave out here.
Lemma 17. Recall the definition of ( at) in algorithm 71 It holds that:
K
H
max[NN at,, 13 < 2SAH 1og, K.
k=1A=1
Proof. In view of the doubling batch update rule, easily seen that: for any given (s, a, h),
K
ma at), 13 11 {(s, a) (sh ati}} S 2 logz K,
since each (s, a, h) is associated with at most log, K epochs. Summing over (s, as,a,)) h) completes the proof.
Lemma 18 (Freedmans inequality). Let (Mn)n2 be a martingale such that Mo O and MM, M,-1| S e (Vn 2 1) hold for some quantity e. >> O. Define
Var
[(M+ M Ma-1)
for every 0, where Fy is the o-algebra generated by (M1,.... MA). Then for any integer 2
and any e, 8 > O, one has
MMI 2 2 Var, log 2 log 1 + 2clog 2 (
Ine"
+ +1)0 6.
TP
31


Reviews:
[{"review_id": "VNnbThYW9v", "reviewer": "Reviewer_f6iM", "summary": "In this work, the authors tackle safety in RL through the framework of constrained MDPs (CMDPs). A CMDP is essentially a Markov decision process equipped with a cost function. Safety is encoded through a bound on the maximum cost the agent must incur while maximizing its return. Precisely, the authors develop a theoretical framework for tabular episodic MDPs, equipped with sample complexity for regret bounds and constraints violations. They consider two settings: strict feasibility, where the safety bound needs to be strictly satisfied, and relaxed feasibility, where the user fixes an acceptable error term violating the safety bound. Notably, the authors provide an online algorithm. This is in contrast to previous work that relied on access to a generative model (an assumption hardly feasible in practice). To achieve the guarantees, the technique is based on a primal-dual formulation. Interestingly, the provided sample complexity in the relaxed feasibility setting matches the lower bound for unconstrained MDPs, while in the strict setting, it matches the lower bound for constrained MDPs with access to a generative model.", "questions": "- Could you explain why ‘fixing a profile that keeps track of visitation counts for all $(s, a, h)$ tuples makes $\\hat{V}$ independent of $\\hat{P}$’ (line 168)?\n- Could you also explain how the double-batch update allows to avoid the number of profiles to be exponential in $K$?\n- Could you please motivate a bit more the introduction of the USB/Bernstein-style bonus $b^{k, \\pi}_{h, g}$ that is added to the reward function and subtracted from the cost estimate? Intuitively, how does this encourage exploration? And how does this allow us to underestimate the cumulative cost?\n- Could you comment and explain the equality of Equation 8? \n- In Algorithm 1, how do you obtain/compute exactly $\\hat{\\pi}_{t}^{k}$? We assume here to retrieve the policy maximizing Equation 8 (through a careful discretization of $\\lambda$). In practice, I guess one should use an LP formulation or policy iteration, right?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "# Strengths\n- The theoretical results seem rather significant: in the relaxed setting, learning in a CMDP is as easy as learning in a classic MDP. On the other hand, in the strict setting, learning in the online setting is as easy as with generative access.\n- The results presented cover two crucial axes: regret bound and constraint violation, for the two settings discussed above.\n- The authors did a good job in presenting the related work, clearly exposing the problem setup and discussing why previous methods failed to achieve near-optimal sample complexity (beginning of Section 4).\n\n# Weaknesses\n- The main concerns I have about this paper are the lack of clarity and problems of presentation. In particular, this makes the paper very difficult to follow, especially for a non-expert reader in RL sample complexity/regret analysis.\n- The paper is very dense (in particular, starting from Section 4) and extremely notation-heavy. Of course, this is a theoretical paper, and that’s the kind of work where formalities are necessary. However, finding the right balance between clarity and formality is key; in the main text, clarity is perhaps even more important as formalities, and notations make the paper very difficult to follow. Beyond the high number of symbols to digest, some of them are even reused for different purposes. For instance, $b$ is used both for the safety bound and for the UCB-style bonus. Taken out of context, it is very confusing. Another example is in Equation 8, where the authors write in a single line that the primal update is equal to subtracting the dual variable multiplied by the optimistically biased cost estimated. First, this is entirely written in the equation through subscript of the value function. This is very difficult to parse. Furthermore, this is written via several layers of subscripts, which makes it even more difficult to read. Why not detail this equality in the main text? Second, the authors do not explain why this equality holds. It should be made clearer. \n- Starting at page 5 (in the methodology section), the paper starts to become very difficult to follow due to the high number of notations, subscripts, superscripts, and the lack of motivation when introducing new concepts and algorithmic choices. Those are later on justified in the proofs, but to me, some of them should be motivated beforehand. To be clear, the design choice of the algorithms is rightfully _described_, but rarely motivated. As an example, the authors describe a double batch update scheme to learn an empirical transition matrix and briefly mention that this is to make $\\hat{V}$ independent from $\\hat{P}$. How? This is not justified. Another example is the reason why a mixture of policies is taken in Algorithm 1. This is not motivated before diving into the proofs.\n- If I am not mistaken, the algorithm assumes knowledge of the reward and cost functions (they are given as input of Algorithm 1). Unless I am mistaken, this is not clearly stated in the main text. I think this also deserves a (at least brief) discussion, even if it is considered ‘standard’ in theoretical RL — in practice, that’s not. \n- The paper ends abruptly with a Theorem and its proof. I would really have liked to have a final formal discussion about the results presented in Section 5 and their implications on the ongoing research.", "was_revised": true, "final_justification": "As originally stated in my review, I believe that the theoretical results presented in this paper are significant.\nNote that I disagree with reviewer JXZe on the fact that the episodic and tabular MDPs are too restrictive.\nIndeed, providing theoretical sample complexity guarantees in those settings is the cornerstone of further theory that can be developed in more advanced and complicated settings. Furthermore, the majority of sample complexity results are developed in tabular settings.\nSince the authors answered thoroughly to my questions, I raised my score, under the condition that (1) they implement the remarks and their answers in the final version of the paper, and (2) they polish the clarity and presentation of their results.", "rebuttal": "We thank the reviewer for the constructive feedback, insightful comments, and positive assessment of our work.\n\nWe respond to the reviewer's concerns below:\n\n- *Clarity and presentation:* \n\nWe appreciate the reviewer's feedback on clarity. We are confident that the clarity concerns can be fully addressed in the camera-ready version through streamlined exposition, more in-line intuition, and improved presentation, so the technical content remains rigorous and more accessible.\n\n- *Notation reuse:* \n\nWe thank the reviewer for pointing this out. We will introduce distinct notations for the constraint constant and the UCB-style bonus to eliminate ambiguity. \n\n- *Regarding equation 8:* \n\nWe agree that the equality should be spelled out in the main text. A full derivation will be added. Please refer to our responses to the reviewer's Question 4 below for detailed explanations.\n\n- *Motivation for the doubling batch update and mixture policy:* \n\nPlease refer to our responses to Questions 1 and 2 for the motivation behind the doubling batch update. Regarding the mixture policy, since the policies obtained from each primal update are deterministic, and CMDPs often require stochastic policies to satisfy constraints exactly, we adopt mixture policies to introduce the necessary randomization.\n\n- *If I am not mistaken, the algorithm assumes knowledge of the reward and cost functions (they are given as input of Algorithm 1). Unless I am mistaken, this is not clearly stated in the main text. I think this also deserves a (at least brief) discussion, even if it is considered ‘standard’ in theoretical RL — in practice, that’s not.*\n\nWe state the assumption of known reward and cost functions in Section 3 (line 118-120). Learning reward and cost functions in CMDPs does not affect the leading terms of the final sample complexity [1], and we introduce this assumption to keep the exposition concise and focus on the core contributions without loss of generality.\n\n- *The paper ends abruptly with a Theorem and its proof. I would really have liked to have a final formal discussion about the results presented in Section 5 and their implications on the ongoing research.*\n\nWe agree that the paper would benefit from a more conclusive discussion, and we will include a brief summary of our results and implications for future research.\n\n---\n\nWe respond to the reviewer's questions below:\n1. *Why fixing a profile makes $\\hat{V}$ independent of $\\hat{P}$:* \n\nRecall that a profile is a “snapshot” of the online learning process that records the visitation counts $N_h(s,a)$ for all $(s,a,h)$ tuples (c.f. line 168). In unconstrained MDPs, we compute: $\\hat{V}\\_h(s) = \\max\\_a \\hat{Q}\\_h(s,a) = \\max\\_a\\\\{r\\_h(s,a) + b\\_h(s,a) + \\hat{P}\\_{s,a,h}\\hat{V}\\_{h+1}\\\\}$. When fixing a profile, the value estimate $\\hat{V}\\_{h+1}$ can be deterministically computed from $\\\\{\\hat{P}\\_{h'}\\\\}\\_{h'=h+1}^H$ and thus independent of $\\hat{P}\\_h$.\n\n2. *How does the double-batch update avoid the number of profiles to be exponential in $K$:* \n\nThe number of profiles equals the number of strictly increasing paths of visitation‑count updates, which is exponential in the number of updates. Adopting the doubling batch update reduces the number of updates from $K$ to $\\log\\_2 K$, thereby avoids profile numbers being exponential in $K$ (see Lemma 4.2 of [2] for a formal proof).\n\n3. *How does the UCB-style bonus encourage exploration while underestimate cost:* \n\nThe UCB-style bonus shrinks with more visitation counts, assigning higher value to less-visited $(s,a,h)$ tuples, and thus encouraging exploration. By subtracting UCB-style bonus from estimated cost values, we offset potential overestimation of $\\hat{P}$ by statistical error, effectively leading to an underestimation of cumulative costs.\n\n4. *Comment and explain the equality of Equation 8:* \n\nWe provide the detailed explanation to equation 8 here, which will be added to the appendix in the camera-ready version:\n    Note that $\\\\hat{V}\\_{1,g}^\\\\pi(s) = \\\\mathbb{E}\\_{\\hat{P},\\pi}\\left[\\sum\\_{t=1}^H g(S\\_t, A\\_t)|S\\_1 = s\\right]$ for any reward-like function $g$ mapping $(s,a,h)$ tuples to scalars, then we have\n       $\\\\hat{\\\\pi}\\_t^k = \\\\arg\\\\max\\_\\\\pi \\\\mathbb{E}\\_{\\\\hat{P},\\\\pi}\\left[\\sum\\_{t=1}^H \\tilde{r}(S\\_t, A\\_t)|S\\_1 = s\\_1\\right] - \\\\hat{\\\\lambda}\\_t^k\\cdot\\\\mathbb{E}\\_{\\hat{P},\\pi}\\left[\\sum\\_{t=1}^H \\\\underline{c}(S\\_t, A\\_t)|S\\_1 = s\\_1\\right] + \\hat{\\lambda}\\_t^k\\cdot b'$ $= \\\\arg\\\\max\\_\\\\pi \\\\mathbb{E}\\_{\\\\hat{P},\\pi}\\left[\\sum\\_{t=1}^H (\\tilde{r} - \\hat{\\lambda}\\_t^k \\underline{c})(S_t, A_t)|S_1 = s_1\\right] = \\\\arg\\\\max\\_\\\\pi \\hat{V}\\_{1,\\tilde{r} - \\hat{\\lambda}\\_t^k\\underline{c}}^\\\\pi(s_1)$.\n\n5. *How do you obtain exactly $\\hat{\\pi}\\_t^k$:* \n\nIn the primal update $\\hat{\\lambda}\\_t^k$ is fixed, and we obtain $\\hat{\\pi}\\_t^k$ from the unconstrained MDP with Lagrange-augmented rewards (c.f. equation 8). The policy can be exactly solved by backward inductions as in standard unconstrained MDPs [2].\n\n---\n\nReference\n\n[1] Sharan Vaswani, Lin Yang, and Csaba Szepesvári. Near-optimal sample complexity bounds for constrained MDPs. In Advances in Neural Information Processing Systems, 2022.\n\n[2] Zihan Zhang, Yuxin Chen, Jason D Lee, and Simon S Du. Settling the sample complexity of online reinforcement learning. In Proceedings of Thirty Seventh Conference on Learning Theory, Proceedings of Machine Learning Research. PMLR, 2024."}, {"review_id": "o3z70lNaNm", "reviewer": "Reviewer_R9pq", "summary": "The authors improve upon known results from constrained reinforcement learning. Specifically, by improving the traditional bonus-driven approach with a primal-dual intuition, the authors improve the sample complexity for learning policies in the no-violation as well as the small-violation regimes.", "questions": "Can your results be stated in another way that avoids dependency on the stater coefficient? Also, do the authors have any thoughts on the optimality of their results? Specifically, for the $\\epsilon$-violating regime, would it be possible to achieve the same sample condition while achieving even smaller than $\\epsilon$ violation?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The paper's main strength is the construction of an algorithm with improved sample complexity guarantees. In addition to the theoretical advancements, using primal-dual intuitions within the bonus-driven approach is a very nice idea. The main weakness of this paper is the presentation; the paper is very mathematically driven and terse. It could benefit from some improvements in writing for clarity. It could also be argued that the improvements in the sample complexity are not drastic, but I believe they are very meaningful nonetheless.", "was_revised": true, "final_justification": "I would agree with many of the other reviewers that the results in this work are very good, but the paper could use some significant revisions to improve clarity. Given the author's responses on matching lower bounds, I think these technical results are even better than I originally thought and certainly outweigh any writing issues, but would still recommend the authors make some edits for the camera-ready version.", "rebuttal": "We thank the reviewer for the constructive feedback, insightful comments, and positive assessment of our work.\n\nWe will improve the exposition and expand the high-level intuition of our methods to enhance overall clarity. Although the improvement of $\\sqrt{SH}$ in the sample complexity compared to the best existing bounds is sublinear in form, it closes a long-standing theoretical gap between the existing upper bounds for online CMDPs and the information-theoretic lower bound. Moreover, its benefits scale with the size of the state space and the episode length, yielding especially significant improvements in large‑state‑space regimes.\n\nWe respond to the reviewer's questions below:\n\n- *Can your results be stated in another way that avoids dependency on the stater coefficient?*\n\nFor the relaxed feasibility setting, the sample complexity does not depend on the Slater constant $\\zeta$. For the strict feasibility setting, the sample complexity must depend on the Slater constant $\\zeta$. It is required both by our upper bound analysis and the lower bound proved in [1]. Intuitively, in the strict feasibility setting, an estimation error of $\\varepsilon$ in the cost domain can lead to a $\\frac{H}{\\zeta}\\varepsilon$-suboptimality in the reward domain. Therefore, ensuring an $\\varepsilon$-suboptimality in reward requires controlling estimation error of cost to within $\\varepsilon' = \\frac{\\zeta}{H}\\varepsilon$. Achieving that precision in MDPs costs $\\Omega(\\frac{SAH^3}{\\varepsilon'^2}) = \\Omega(\\frac{SAH^5}{\\varepsilon^2\\zeta^2})$ samples, forcing the $\\zeta$-dependence.\n\n- *Do the authors have any thoughts on the optimality of their results? Specifically, for the $\\varepsilon$-violating regime, would it be possible to achieve the same sample condition while achieving even smaller than $\\varepsilon$ violation?*\n\nOur upper bounds for sample complexity in both regimes match the corresponding lower bounds (up to logarithmic factors), so our results are minimax optimal (up to logarithmic factors). In the relaxed feasibility setting, the sample complexity depends on the smaller of the reward suboptimality and the cost violation tolerances.\n\n---\n\nReference\n\n[1] Sharan Vaswani, Lin Yang, and Csaba Szepesvári. Near-optimal sample complexity bounds for constrained MDPs. In Advances in Neural Information Processing Systems, 2022."}, {"review_id": "7GXppu7imw", "reviewer": "Reviewer_A1jm", "summary": "The paper considers the online learning problem for episodic constrained MDPS.\nFor the proposed online learning algorithm, which does not require access to a generative model(as in [3]), they provide regret bounds, constraint violation bounds, and sample complexities for relaxed and strict constrained MDP scenarios.  The algorithm and proofs leverage many existing ideas from constrained MDPs and unconstrained MDPs to improve the regret bounds compared to other existing algorithms.", "questions": "**Technical Questions**\n\n- The algorithm uses optimistic rewards and cost functions along with the empirical model, even though the reward and cost functions are known. In unconstrained RL (UCRL2 variants ) as well as in constrained RL [1], optimistic estimates are used for the unknown quantities ($P$ in the case). Can the author provide their intuition on why they do not use optimistic estimates of P instead of the MLE estimate, as well as use optimistic reward and cost when they are assumed to be known?  When optimism is required and when empirical estimate suffices? This is similar to [3] but more surprising as they assume access to a generative model.\n\n\n- As mentioned earlier, even though the algorithm is shown to have improved pre-constants in regret, it does not give a complete picture of the comparison of various model-based constrained RL algorithms.  A common theme in many unconstrained, tabular RL papers is to provide empirical comparison with existing algorithms in terms of regret and computational complexity; this has been missing in most Tabular constrained MDP papers, including this one. Can authors potentially address this missing aspect in this line of papers, which can provide new insights into these algorithms?\n\n- Why is $\\pi^{\\tau,*}$ a deterministic policy (Line 233)?\n- As suggested in Lines 55-56 (\"large-scale state spaces\"), what aspect of the algorithm makes it more suitable for large state spaces compared to the previous algorithms? \n\n \n**Writing / Presentation Questions (and Suggestions)**\n- As found in many theoretical RL papers these days (e.g., see Table 1 in [1] and [2]), can the author provide a table comparing regret bounds, constraint violation, and sample complexity of various algorithms in the related work/ introduction section? Only mentioning that the existing algorithm provides sublinear regrets (lines 40-41) does not give a full picture when the primary contribution of the paper is improving pre-constants in regret bounds.\n- Would it be better to use some other symbol instead of $T$ for the number of primal-dual updates? Since $T$ is usually used for time ($HK$) in regret bounds, it can be potentially confusing.  \n- The title is perhaps too similar to [3]. I recommend that the authors consider some modifications that highlight the contribution of this paper, particularly compared to [3].\n\n- While most of the paper is well-written and easy to follow, can the authors explain the \"profile\" mentioned in lines 167-168?\n- Missing values in Line 552 after \"With probability at least\"\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n**Reference**\n\n[1]  Tao Liu, Ruida Zhou, Dileep Kalathil, P. R. Kumar, and Chao Tian. Learning policies with zero\nor bounded constraint violation for constrained MDPs. In Proceedings of the 35th International\n Conference on Neural Information Processing Systems, NIPS ’21, 2021.\n\n[2] Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity\n barrier to regret-optimal model-free reinforcement learning. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21, Red Hook, NY,\n USA, 2021.\n\n[3] Sharan Vaswani, Lin Yang, and Csaba Szepesvári. Near-optimal sample complexity bounds\nfor constrained MDPs. In Advances in Neural Information Processing Systems, 2022", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths** \n\n- The paper addresses many theoritical aspects of the constrained MDP learning problems by providing regret bounds, constraint violation bounds and sample complexity in both relaxed and strict feasibility cases. \n- The paper removes the requirement of access to generative model assumed in [3]. \n- The presentation and writing in this paper is good and easy to follow, particularly the inclusion of Section 4 provides lot of insights into the existing work and the algorithm.\n\n\n**Weaknesses**\n- The paper mentions that constrained MDP is an important setup for RL problems with safety concerns. The paper's contribution is purely algorithmic and theoritical. It lacks any experimental / simulation studies, comparison with existing algorithms. As seen in unconstrained RL algorithms, particularly UCRL variants, algorithm with similar regret bounds have been shown to have different empirical performance, so improved regret bounds alone are not sufficient to make a strong case for a new algorithm. \n\n- Please see the questions section for potential weaknesses and questions. \n\n**References**\n\n[1]  Tao Liu, Ruida Zhou, Dileep Kalathil, P. R. Kumar, and Chao Tian. Learning policies with zero\nor bounded constraint violation for constrained mdps. In Proceedings of the 35th International\n Conference on Neural Information Processing Systems, NIPS ’21, 2021.\n\n[2] Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity\n barrier to regret-optimal model-free reinforcement learning. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21, Red Hook, NY,\n USA, 2021.\n\n[3] Sharan Vaswani, Lin Yang, and Csaba Szepesvári. Near-optimal sample complexity bounds\nfor constrained MDPs. In Advances in Neural Information Processing Systems, 2022", "was_revised": true, "final_justification": "The paper has received a positive response from all reviewers. Most reviewers highlight that there is room for improvement in presentation and clarity of the paper. The authors addressed my questions and concerns adequately. I retain the current positive rating of the paper, hoping all the changes discussed during the rebuttal are included in the camera-ready version.", "rebuttal": "We thank the reviewer for the constructive feedback, insightful comments, and positive assessment of our work.\n\nWe agree that empirical evaluation of CMDP algorithms is valuable. Our primary contribution of this paper is theoretical and to close the gap between upper and lower bounds for online tabular CMDPs using novel analysis techniques. While comprehensive empirical study is beyond the scope of this paper, we plan to conduct numerical experiments in future work. \n\nWe respond to the reviewer's questions below:\n- *Can the author provide their intuition on why they do not use optimistic estimates of $P$ instead of the MLE estimate, as well as use optimistic reward and cost when they are assumed to be known? When optimism is required and when empirical estimate suffices?*\n    \nWe thank the reviewer for this excellent question. In our method, the UCB bonus $b_h(s,a)$ is indeed used to encode optimism for the transition model $P$. As shown in the optimism analysis (c.f. lemma 15), the bonus term is designed to cover the statistical error between $\\hat{P}$ and $P$, guaranteeing an optimistic value estimates for any fixed policies (c.f. line 571). Because the UCB bonus $b_h(s,a)$ is analogous to reward and cost functions, mapping $(s,a,h)$ tuples to scalars, we add the bonus directly to rewards (or subtract from costs) and denote the estimated reward (or cost) values by $\\hat{V}_{h,\\tilde{r}}(s)$ (or $\\hat{V}\\_{h,\\underline{c}}(s)$) to streamline the presentation.\n\n- *Why is $\\\\pi^{\\\\tau,\\*}$ a deterministic policy (line 233)?*\n    \nWe thank the reviewer for catching this. The policy $\\pi^{\\\\tau,\\*}$ is in fact fixed, but not necessarily deterministic. We will correct the wording in line 233 to reflect that it may be randomized. Meanwhile, the policy $\\pi^{\\tau,*}$ remains independent of the online learning process, and this typo does not affect the soundness of our theoretical results.\n\n- *As suggested in Lines 55-56 (\"large-scale state spaces\"), what aspect of the algorithm makes it more suitable for large state spaces compared to the previous algorithms?*\n    \nOur algorithm reduces the sample complexity by $\\sqrt{SH}$ compared to the best existing results [1], and in scenarios with large state space $S$ and episode length $H$, the advantage of our algorithms will be significant.\n\n- *Can the author provide a table comparing regret bounds, constraint violation, and sample complexity of various algorithms in the related work/ introduction section?*\n    \nWe agree that a table will help readers. In the camera-ready version, we will add a table that compares the regret, constraint violation, and sample complexity of existing online CMDP algorithms to ours. \n\n- *Would it be better to use some other symbol instead of $T$ for the number of primal-dual updates? Since $T$ is usually used for time ($HK$) in regret bounds, it can be potentially confusing.*\n\nWe appreciate the reviewer for the kind advice. We will refine the notations in the camera-ready version to eliminate ambiguity.\n\n- *The title is perhaps too similar to [2]. I recommend that the authors consider some modifications that highlight the contribution of this paper, particularly compared to [2].*\n    \nWe thank the reviewer for the constructive comment. We will revise the title to highlight the contributions of our work.\n\n- *While most of the paper is well-written and easy to follow, can the authors explain the \"profile\" mentioned in lines 167-168?*\n    \nA profile is a “snapshot” of the online learning process that records the visitation counts $N_h(s,a)$ for all $(s,a,h)$ tuples (c.f. line 168).\n\n- *Missing values in Line 552 after ``With probability at least'':*\n\nWe thank the reviewer for catching this typo. We will add the probability $1-2\\delta'$ to line 552.\n\n---\n\nReference\n\n[1] Archana Bura, Aria Hasanzade Zonuzy, Dileep Kalathil, Srinivas Shakkottai, and Jean-Francois Chamberland. Dope: doubly optimistic and pessimistic exploration for safe reinforcement learning. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, 2022.\n\n[2] Sharan Vaswani, Lin Yang, and Csaba Szepesvári. Near-optimal sample complexity bounds for constrained MDPs. In Advances in Neural Information Processing Systems, 2022."}, {"review_id": "PuDmkPHORF", "reviewer": "Reviewer_JXZe", "summary": "The paper studies tabular CMDPs. They proposed a primal-dual algorithm that obtains a near-optimal policy with sample complexity that matches the lower bound. This holds for both the setting considered in the paper, relaxed and strict feasibility.\nThe paper is generally well-written and easy to follow. I had several questions while reading—some were answered later, but it would still be helpful to clarify them in the final version for the benefit of other readers.", "questions": "What does giving access to generative model means? Does it imply that system can obtain transitions values for any state, looks impractical?\n\nline 71-71: It was counterintuitive why sample complexity depends inversely on the size of the feasible region.\n\nline 162: explain intutively \\tilde{r}. Is it some optimistic acquisition function?\n\nIn section 3: problem setup can you write the finite state space and finite action spaces? It is mentioned in line 36 but no where in problem setup section.\n\nMethodology section starts nicely with explaining why the existing methods have loose bounds. Since the section is long with a sequence of paragraphs, i recommend naming paragraphs as \"\\textbf{name.} content of paragraph.....\"\n\nline 174-181: Can you also clarify why the doubling batch updates solves the problem\n\nIt would be good to mention t, k, and h early on and what they represent. In line 202 why does a finite number of solve iterations T is Guaranteed to converge to optimal solution?\n\nline 233, why \\pi^{\\tu, \\star} is a deterministic policy?\n\nin the proof of theorem 1, why does s_1 depends on k? is it a typo? If it does depend on k, then \\pi^{\\tau, \\star} should also depend on k.\n\nline 237-238: Is this term (3rd regret term) non-zero due to finite number of gradient steps T? If it T is long enough (converges) then it will be zero as well? I think so, but it is not evident with the upper bounds of this term. Is your regret optimal with T?\n\nWhat does _{+} represents is CV(K)? If it is ciel function, shouldn't it be inside \\sum_k ? \n\nTheorem 4: why there is constraint violations in the case of strict feasibility? (c.f. line 14 saying zero violation)\n\ntheorem 3: does \\delta' h in line line 264 is same as line 184? Since theorem statement is with 1-\\delta, may be just write 1-SHAK\\delta' > 1-\\delta.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\nThe theoretical results are solid. They provide upper bounds for their algorithm, which match the lower bounds existing in the literature.\n\nWeakness: There were no major flaws/weaknesses in the paper. \n- The assumption of a finite state-action space is somewhat limiting in practice. The model essentially reduces to a linear setting. (This is only my opinion about the considered settings in the literature; however, there are multiple works with similar setting,s and this paper adds value)\n- The paper would benefit from an implementation of the algorithm and releasing the code.\n- It would be helpful to clearly state all assumptions using an Assumption environment and refer to them explicitly in the theorems. (But not sure if there are any assumptions apart from written in the problem setup) For example, do you require full support over the state space from the initial state distribution?\n- See the questions below for improving paper clarity", "was_revised": true, "final_justification": "I would keep the score as borderline accept. The paper makes a theoretical contribution by providing upper bounds that match existing lower bounds. However, the considered setting of tabular, episodic MDP is very limiting, and the absence of a simulation or numerical study leads me to keep it borderline.", "rebuttal": "We thank the reviewer for the constructive feedback, insightful comments, and positive assessment of our work.\n\nWe address the reviewer's concerns below:\n- *The assumption of a finite state-action space is somewhat limiting in practice. The model essentially reduces to a linear setting. (This is only my opinion about the considered settings in the literature; however, there are multiple works with similar setting,s and this paper adds value)*\n\nTabular CMDPs provide the fundamental setting for more complex settings such as function approximations, and it is of significance to obtain minimax optimal results for online tabular CMDPs. We agree that generalizing our techniques and results is important and view it as an exciting direction for future work.\n\n- *The paper would benefit from an implementation of the algorithm and releasing the code.*\n\nWe agree that empirical evaluation of CMDP algorithms is valuable. Our primary contribution of this paper is theoretical and to close the gap between upper and lower bounds for online tabular CMDPs using novel analysis techniques. While comprehensive empirical study is beyond the scope of this paper, we plan to conduct numerical experiments in future work. \n\n- *It would be helpful to clearly state all assumptions using an Assumption environment and refer to them explicitly in the theorems. (But not sure if there are any assumptions apart from written in the problem setup) For example, do you require full support over the state space from the initial state distribution?*\n\nWe thank the reviewer for the constructive suggestion. We will highlight the known reward and cost functions assumption in the final version. We do not require full support over the state space from the initial state distribution.\n\n---\n\nWe respond to the reviewer's questions below:\n- *What does giving access to generative model means? Does it imply that system can obtain transitions values for any state, looks impractical?*\n    \nA generative model, also called random access, gives the learner oracle access to a simulator that, for any queried $(s,a,h)$ tuple, returns an i.i.d. sample of the next state, reward, and cost drawn from the true distributions. A generative model is indeed rarely available in practice. Therefore, extending minimax optimal results from the random access setting to the online learning setting is significant in the CMDP literature.\n\n- *line 71-71: It was counterintuitive why sample complexity depends inversely on the size of the feasible region.*\n\nIntuitively, the Slater constant $\\zeta$ measures the slack in the constraint. For a small $\\zeta$, a small estimation error can make an otherwise feasible policy appear infeasible. To guarantee the same reward suboptimality, the learner must estimate reward and cost values with higher precision, demanding a higher sample complexity.\n    \n- *line 162: explain intuitively $\\tilde{r}$. Is it some optimistic acquisition function?*\n\nThe optimistic reward $\\tilde{r} = r + b_r$ and optimistic cost $\\underline{c} = c - b_c$ is introduced purely for notational clarity: the UCB bonus $b_h(s,a)$, which compensates for transition uncertainty, is absorbed into the reward. Writing value estimates (e.g., $\\hat{V}\\_{h,\\tilde{r}}(s)$ and $\\hat{V}\\_{h, \\tilde{r} - \\lambda\\underline{c}}(s)$) with $\\tilde{r}$ and $\\underline{c}$ makes it explicit how bonus terms enter each estimate, keeping the exposition concise.\n    \n- *In section 3: problem setup can you write the finite state space and finite action spaces? It is mentioned in line 36 but no where in problem setup section.*\n\nWe appreciate the suggestion. In the camera-ready version, section 3 will explicitly state that both the state and action spaces are finite when we introduce the CMDP formalities.\n\n- *Methodology section starts nicely with explaining why the existing methods have loose bounds. Since the section is long with a sequence of paragraphs, i recommend naming paragraphs as \"\\textbf{name.} content of paragraph.....\"*\n\nWe thank the reviewer for this constructive suggestion. We will add paragraph headings to better guide the readers in the final version.\n\n- *line 174-181: Can you also clarify why the doubling batch updates solves the problem*\n\nAs mentioned in lines 167-170, although fixing a profile decouples the dependence between $\\hat{P}\\_h$ and $\\hat{V}\\_{h+1}$, it is the doubling batch updates that reduces the number of profiles, so a union bound over all profiles yields tight results.\n    \n- *It would be good to mention $t$, $k$, and $h$ early on and what they represent. In line 202 why does a finite number of solve iterations $T$ is Guaranteed to converge to optimal solution?*\n\nWe thank the reviewer for the helpful suggestion. We will revise the presentation in the final version to clarify that we do not require solving equation 7 exactly. Accordingly, we will update the wording from \"solve the saddle-point problem eq. 7 iteratively\" to \"tackle the saddle-point problem eq.7 iteratively\".\n\n- *line 233, why $\\pi^{\\tau, \\*}$ is a deterministic policy?*\n\nWe thank the reviewer for catching this. The policy $\\pi^{\\tau,\\*}$ is in fact fixed, but not necessarily deterministic. We will revise the wording to \"fixed\" in line 233 to reflect that it may be randomized. Meanwhile, the policy $\\pi^{\\tau,\\*}$ remains independent of the online learning process, and this typo does not affect the soundness of our theoretical results.\n\n- *in the proof of theorem 1, why does $s_1$ depends on $k$? is it a typo? If it does depend on $k$, then $\\pi^{\\tau, \\*}$ should also depend on $k$.*\n\nWe thank the reviewer for catching this typo. It should be $s_1$ throughout the paper. We will revise the notations in the final version.\n    \n- *line 237-238: Is this term (3rd regret term) non-zero due to finite number of gradient steps $T$? If it $T$ is long enough (converges) then it will be zero as well? I think so, but it is not evident with the upper bounds of this term. Is your regret optimal with $T$?*\n\nThe third term is non-zero due to two factors (c.f. lemma 14, second-to-last line of the last equation): (1) We discretize $\\lambda$ by an $\\varepsilon_1$-net. This introduces a non-zero optimization error of $\\frac{2\\varepsilon_1 U}{\\eta}$, which depends on $\\varepsilon_1$ and does not vanish as $T$ goes to infinity. (2) The $T$-iteration primal-dual optimization introduces an error of $\\frac{\\eta H^2}{2} + \\frac{U^2}{2\\eta T} = \\frac{UH}{\\sqrt{T}}$ (by selecting $\\eta = \\frac{U}{H\\sqrt{T}}$), which indeed goes to zero as $T$ goes to infinity. Therefore, our results are optimal in $T$, as increasing $T$ will not reduce the leading terms.\n    \n- *What does \\_{+} represents is CV(K)? If it is ceil function, shouldn't it be inside sum\\_k?*\n\nWe will add the notation of $(x)_+ = \\max\\\\{x, 0\\\\}$ to improve clarity. The cumulative constraint violation defined in equation 2 is used to compute the constraint violation of the output mixture policy in theorem 5 and 6. It is also worth mentioning that this definition of constraint violation is widely adopted in many CMDP works [1,2,3,4].\n    \n- *Theorem 4: why there is constraint violations in the case of strict feasibility? (c.f. line 14 saying zero violation)*\n\nAs mentioned in the definition of the strict feasibility regime (c.f. line 144-146), our algorithm returns a zero-violation policy. Moreover, with parameters defined in theorem 6, we can bound $CV(K) \\le 0$.\n\n- *theorem 3: does $\\delta'$ in line line 264 is same as line 184? Since theorem statement is with $1-\\delta$, may be just write $1-SHAK\\delta' \\rightarrow 1-\\delta$.*\n\nWe thank the reviewer for the constructive comment. We will revise the probability guarantees in the final version to ensure consistency and clarity in the use of $\\delta'$ and $\\delta$.\n\n---\n\nReference\n\n[1] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo R. Jovanović. Provably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligence and Statistics, 2020.\n\n[2] Arushi Jain, Sharan Vaswani, Reza Babanezhad Harikandeh, Csaba Szepesvári, and Doina Precup. Towards painless policy optimization for constrained MDPs. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022.\n\n[3] Tao Liu, Ruida Zhou, Dileep Kalathil, P. R. Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21, 2021.\n\n[4] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitation in constrained mdps, 2020."}]

Author rebuttal:

Meta-review: The paper considers the problem of learning under constrained MDP where constraints can be seen as enforcing safety for instance. The paper is theoretically strong and reviewers agree with this. Reviewers do mention that the paper might be dense to read and it would be good for the authors to fix before final version. That said I believe the paper is clearly above the bar for publication at Neurips.
Decision: Accept (poster)