Confident Natural Policy Gradient for Local Planning in  $q_\pi$-realizable Constrained MDPs
Authors: Tian Tian
Lin Yang
Csaba Szepesvari
Venue: NeurIPS 2024 poster (2024)
Keywords: reinforcement learning
constrained MDP
sample complexity
q-pi realizability
local planning
Primary area: reinforcement_learning

Abstract: The constrained Markov decision process (CMDP) framework emerges as an important reinforcement learning approach for imposing safety or other critical objectives while maximizing cumulative reward. However, the current understanding of how to learn efficiently in a CMDP environment with a potentially infinite number of states remains under investigation, particularly when function approximation is applied to the value functions. In this paper, we address the learning problem given linear function approximation with $q_{\pi}$-realizability, where the value functions of all policies are linearly representable with a known feature map, a setting known to be more general and challenging than other linear settings. Utilizing a local-access model, we propose a novel primal-dual algorithm that, after $\tilde{O}(\text{poly}(d) \epsilon^{-3})$ iterations, outputs with high probability a policy that strictly satisfies the constraints while nearly optimizing the value with respect to a reward function. Here, $d$ is the feature dimension and $\epsilon > 0$ is a given  error. The algorithm relies on a carefully crafted off-policy evaluation procedure to evaluate the policy using historical data, which informs policy updates through policy gradients and conserves samples. To our knowledge, this is the first result achieving polynomial sample complexity for CMDP in the $q_{\pi}$-realizable setting.

Confident Natural Policy Gradient for Local Planning in 9n reareizlea Constrained MDPs
Tian Tian
Lin F. Yang
University of Alberta, Edmonton trianOualberta.ca
University of California, Los Angeles linyangdee. ucla.
Csaba Szepesvári
University of Alberta, Google DeepMind, Edmonton
szepesva@uallberta.co
Abstract
The constrained Markov decision process (CMDP) framework emerges as an impor- reinforcement learning approach for imposing safety or other critical objectives while maximizing cumulative reward. However, the current understanding of how learn efficiently in a CMDP environment with a potentially infinite number of states remains under investigation, particularly when function approximation is applied to the value functions. In this paper, we address the learning problem given linear function approximation with er vn-reelizabilityy where the value functions of policies are linearly representable with a known feature map, a setting known to be more general and challenging than other linear settings. Utilizing a local- access model, we propose novel primal-dual algorithm that, after (ppolydd)e-)) queries, outputs with high probability a policy that strictly satisfies the constraints while nearly optimizing the value with respect reward function. Here, d is the feature dimension and 6 > is a given error. The algorithm relies on a carefully crafted off off-co evaluation procedure to evaluate the policy using historical data, which informs policy updates through policy gradients and conserves samples. To our knowledge, this is the first result achieving polynomial sample complexity for CMDP in the geereiizzblle setting.
Introduction
In the classical reinforcement learning (RL) framework, optimizing single objective above all else can be challenging for safety-critical applications like autonomous driving, robotics, and Large Language Models (LLMss). For example, it may be difficult for an LLM agent to optimize single reward that fulfills the objective of generating helpful responses while ensuring that the messages are harmless (Dai et al., 2024). autonomous driving, designing single reward often requires reliance on complex parameters and hard-coded knowledge, making the agent less efficient and adaptive (Kamran et al., 2022). Optimizing single objective in motion planning involves combining heterogeneous quantities like path length and risks, which depend on conversion factors that are not necessarily straightforward determine (Feyzabadi and Carpin, 2014).
The constrained Markov decision process (CMDP) framework (Altman, 2021) emerges as an im- portant RL approach for imposing safety other critical objectives while maximizing cumulative
"Correspondigg author. Here Ó(-) hides log factors.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

reward (Wachi and Sui, 2020; Dai et al., 2024; Kamran et al., 2022; Wen et al., 2020: Girard and Reza Emami. 2015; Feyzabadi and Carpin, 2014).
In addition to the single reward function optimized under a standard Markov decision process (MDP), CMDP considers multiple reward functions, with one designated the primary reward function. The goal of CMDP is to find a policy that maximizes the primary reward function while satisfying constraints defined by the other reward functions. Although the results of this paper can be applied to multiple constraint functions, for simplicity of presentation, we consider the CMDP problem with only one constraint function.
Our current understanding of how to learn efficiently in a CMDP environment with a potentially infinite number of states remains limited, particularly when function approximation is applied to the value functions. Most works studying the sample efficiency of a learner have focused on the tabular or simple linear CMDP setting (see related works for more details). However, there has been little work in the more general settings such as the (r (r-reaaizabilityy which assumes the value function of all policies can be approximated by linear combination of a feature map with unknown parameters. Unlike Linear MDPs (Yang and Wang, 2019; Jin et al., 2020), where the transition model is assumed to be linearly representable by a feature map, g--realizability only imposes the assumption on the existence of a feature map to represent value functions of policies.
Nevertheless, the generality of -r-rraaizabilityy comes with a price, as it becomes considerably more challenging to design effective learning algorithms,, even for the unconstrained settings. For the general online setting, et al., 2023), which, however, is computationally inefficient. To tackle this issue, a line of research (Kearns et al., 2002; Yin et al., 2022; Hao et al., 2022; Weisz et al., 2022) applies the local-access model, where the RL algorithm can restart the environment from any visited states- a setting that also practically motivated, especially when a simulator is provided. The local-access model is more general than the generative model (Kakade, 2003; Sidford et al., 2018; Yang and Wang, 2019; Lattimore al., 2020; Vaswani al., 2022), which allows visitation to arbitrary states in an MDP. The local-access model provides the ability to unlock both the sample and computational efficiency of learning with 9r rraaraiizabilyty for the unconstrained MDP settings. However, it remains unclear whether we can harness the power of local-access for CMDP learning.
are only aware of one sample-efficient MDP learning algorithm (Weisz
In this paper, we present a systematic study of CMDP for large state spaces, given ge-realizable function approximation in the local-access model. We summarize our contributions as follows:
We design novel, computationally efficient primal-dual algorithms to learn CMDP near- optimal policies with the local-access model and g= rearliiizeele function classes. The algo- rithms can return policies with small constraint violations or even no constraint violations and can handle model misspecification.
We provide theoretical guarantees for the algorithms, showing that they can compute an c-optimal policy with high probability, making no more than (d)))(d))=3) queries to the local-access model. The returned policies can strictly satisfy the constraint.
Under the misspecification setting with misspecification error w, we show that our algo- rithms achieve an Ö(w) + sub-optimality with high probability, maintaining the same sample efficiency of (pply(dd)
2 Related works
Most provably efficient algorithms developed for CMDP are in the tabular and linear MDP settings. In the tabular setting, most notably are the works by (Efroni et al., 2020; Liu et al., 2021; Zheng and Ratliff, 2020; Vaswani et al., 2022; Kalagarla et al., 2021; Yu et al., 2021; Gattami et al., 2021: HasanzadeZoonuzy et al., 2021; Chen et al., 2021; Kitamura et al., 2024). Work by Vaswani et al.
(2022) have showed their algorithm uses no more than ò
SA (-ン)
samples to achieve relaxed
feasibility and Ô discount factor and Ç (0, +-:] is the Slater's 's constant, which characterizes the size of the feasible region and hence the hardness of the CMDP. In their work, they have also provided lower bound of
SA (1-7) samples to achieve strict feasibility. Here, the Y [0, 1) is the

---

Q
(1-7)-<++) on the sample complexity under strict feasibility, However, all the aforementioned results all scale polynomially with the cardinality of the state space.
84
For problems with large possibly infinite state spaces, works by (Jain al., 2022; Ding al., 2021; Miryoosefi and Jin, 2022; Ghosh et al., 2024; Liu et al., 2022) have used linear function approximations to address the curse of dimensionality. All these works, except Jain et al. (2022); Liu et al. (2022), make the linear MDP assumption, where the transition function is linearly representable.
Under the generative model, for the infinite horizon discounted case, the online algorithm proposed in Jain et al. (2022) achieves regret of Ō D(Vd/v/ /K) with Ó D(vd/ VK) constraint violation, where K' is the number of iterations. Work by Liu et al. (2022) is able to achieve a faster O(In(K) K) convergence rate for both the reward suboptimality and constraint violation. For the online access setting under linear MDP assumption, Ding et al. (2021); Ghosh et al. (2024) achieve a regret of (poly (d) (oy(H))T) with (poly (d) poly (T) violations, where T is the number of episodes and H is the horizon term.
Miryoosefi and Jin (2022) presented an algorithm that achieves a sample complexity of Ô L where d the dimension of the feature space and H is the horizon term in the finite horizon CMDP setting. In the more general setting under g.- rr-realizability, the best-known upper bounds are in the unconstrained MDP setting.
In the unconstrained MDP setting with access to local-access model, early work by Kearns et al. (2002) have developed rearch style algorithms under this model, albeit in the tabular setting. Under v" -realizability, Weisz et al. (2021) presented a planner that returns an e-optimal policy using ((dH//c) AI) queries to the simulator. More works by (Yin et al., 2022; Hao et al., 2022; Weisz et al., 2022) have considered the local-access model with dr- g--realizability assumption. Recent work by Weisz et al. (2022) have shown their algorithm can return a near-optimal policy that achieves a
sample complexity of Ô (1-7))+²²
3 Problem formulation
Constrained MDP
We consider an infinite-horizon discounted CMDP (S, P,r, C, 7, 6,,,,)) consisting a possibly count- ably infinite state space with a finite set of actions A, a reward function r S A + [o. 1], a constraint function c S x A + [o, 1], discount factor E [0. 1), constraint threshold b 2 0. and a fixed initial state sg. Let Mi (X) denote the space of probability distributions supported on the set X. Then, the transition probability P: S x A + Mi (S).
Define a of stationary randomized policies Trand and policy π Trand maps states prob- ability distributions over the actions (i.c.. π S + (A)).. Given a π E ILannd the policy interacts with the CMDP starting from any state E S through discrete steps indexed by t E No. where No = {0, 2..,,..., J. This interaction generates a trajectory of {S,, Ag JeN, where At) The reward action-value function is defined as (s, = E 1E r'r(S, A.)[So s. A. =]. Similarly, the constraint action-valt value function is defined as of (x,a) = E iI " 7,,,, Ar) 8, An = a). The reward state-value function (s) (m()s,), of (s. )), where (, denotes the inner product over actions. Likewise, the con-
...
So s, A, ~ 7-1S,), and S
straint state-value function of (s) = (IT()s), of
The objective of the CMDP is to find a policy that maximizes the state-value function if starting from a given state sp, while ensuring that the constraint of (Su) 2 is satisfied:
max Ui (50) xElland
s.t. (so) 2 b.
We assume the existence of a feasible solution to eq. (1) and let TT" denote a solution to eq. (1). A quantity unique to CMDP is the Slater's constant, which is denoted as ( = max, of (su) - b. Slater's constant characterizes the size of the feasibility region, and hence the hardness of the problem.
Because the state space can be large possibly infinite, we use linear function approximation to approximate the values of stationary randomized policies. Let Φ S x A -> Rdd be a feature map. We assume that both of and of satisfy the following condition:
3

---

Assumption (gareaalia))ility) There exists B > and misspecification error w 2 0 such that for every πt mad there exists weight vector Wn R. || S B, and ensures 1 (s. a) (Wx, (88 a))l I w for all (s, a) E A.
mixture policy is defined as a policy randomly selected from finite set of policies ( ... * and executed for all subsequent steps. For example, a mixture policy क K is constructed by sampling a policy Tk with probability R and following it. The value function of such mixture policy for state 2k= Ux (s), where UT, (s) is the value function of the individual
E S is given by U (s) policy Ty- Note that * is a non-stationary policy, and the set of non-stationary policies includes the set of stationary randomized policies aadd
We assume access to a local access model, where the agent can query the simulator only for states that have been encountered during previous simulations. Our goal is to design algorithm that outputs near-optimal mixture policy K, whose performance can be characterized in one two ways.
For given target error > O, the relaxed feasibility requires the returned policy मx whose sub- optimality gap ve (su) 2 (so) is bounded by e, while allowing for small constraint violation. Formally, we require H such that
(5o) - o (80) I s.t
(80) 2 b-cc
On the other hand, ftaibi-feaiibility requires the returned policy मं whose sub-optimality gap -ig- (8o) " (so) is bounded by while not allowing any constraint violation. Formally, we require T such that
v-- ux (50) Se s.t ox (50) 2 b.
Notations
For any real number a E RR we let [a] to denote the smallest integer i such that S a. For vector I E Rd, let |||||] = Σ, |ry]. ||æ|||
E x and || = max; |za|.- For positive definite matrix A E Rdxd, the || = x Ar. We let proj (^) = arg minpe [g]] [ - pl. and trunc(ar,a (v) = min max (v, a2). For any two positive numbers a, b, we write a = O(b) if
there exists an absolute constant e such that cb. We use the Ô to hide any polylogarithmic terms.
4 ConfidentNNG-CMDDP a local-access algorithm for CMDP
In this section, we introduce primal-dual algorithm, which we call Confident-PGGCMMD (sce algorithm l).
4.1 A primal-dual approach
We approach solving the CMDP problem by framing as an equivalent saddle-point problem:
max min L( A); A20
where L IInand X R4 + IR is the Lagrange function. For a policy x Ia and a Lagrange multiplier À R4, we have
L( x) u)(()))))))))) (so) b). -)).
Let (Tr", X²) be solution to this saddle-point problem. By an equivalence to LP formulation and strong duality (Altman, 2021), is the policy that achieves the optimal value in the CMDP as defined in eq. (1). An optimal Lagrange multiplier X* E arg min [(xx", A). Therefore, solving eq. (1) is equivalent to finding a saddle-point of the Lagrange function.
A typical primal dual algorithm that finds the saddle-point will proceed in an iterative fashion alternating between a policy update using policy gradient and a dual variable update using mirror descent. The policy gradient is computed with respect to the primal value & 9-, + A and the mirror descent is computed with respect to the constraint value vi (so) = (-s0)) df (so. )))-

---

Algorithm Confident-NG--CMIP
1: Input: 8o (initial state), (target accuracy), E (0, 1] (failure probability); y (discount factor)
2: Initialize:
3: Define K, ",, 72, m according to Theorem for relaxed-feasibiiity and Theorem for strict-
feasibility,
4: Set L e [|]][[[m)) ml + +-]]--
5: For each iteration l E {0,..... [K]] me Unif(A), R((-) 0, VE()) 0, and A O.
6: For each phase E (0....,I.+
< O, Dj 0
7: For a E A: if (so, a) & ActionCov(Co), then append (so, a) to Co and set 1 to Dol(so, a)] see ActionCov defined in eq. (4)
8: while True do
main loop
9: Let be the smallest integer s.t. De[2'] =1 for some z' E C.
Let be the first state- actten pair in Ce s.t. Dz[2]=1]
If
1, then return ĀK
ke e ([m]+
iteration corresponding to phase
13:
(result, discovered) +- Gather-data(Tke Co, ax
14:
if discovered True then
15:
Append result to Co and set 1 to Do(result]
resull is state-action pair
16:
Goto line
17:
De[z] +- result.
18:
if Ae E EC s.t. De(24 =1 then
19:
ket1 t kg ([ml 1) if + (Im) + S [K] otherwise [K]
20:
for k ke,..., ke+1 do Qh Q + LSE(C,, De, Th; Tk. Tke)
off-policy iterations reusing Ce Dr
21:
22:
For S Cov(Ce) \ Cou((Ce1), and for a E A (R(s,a) t- trunc (o (s)sa)) + d trunc (g(s,a) (T()) trunc (o., (T)())) (s(s,)))
23:
25:
> update policy
26:
For 8, E x A:
(als)
if s Cov(Ce+1) otherwise
27:
(x.(m (als)) +- (als))) En'e Tu(a'ls) (xp(m
28:
update dual variable
Dh-1
if so E Cov(Ce+1) otherwise.
29:
AR+1 pprojjou1 (>x (5(
-b)
30:
For Ce s.t. Ce+si append to C4+1 and set 1 to D4+1[a]
5

---

Given that we do not have access to an oracle for exact policy evaluations, we must collect data to estimate the primal and constraint values. If we have the least-squares estimates of l and Fax denoted by Qj and Q respectively, then we can compute the least-squares estimate 0% = QR 2 to be the estimate of the primal value A Additionally, we can compute Vg((s)
(+s)) Q% (=0-)) -)) to be the least-squares estimate of the constraint value " (#o)- Then, for any A, our algorithm makes a policy update of the following form:
given (s, a)
* (als) x TT& (a(a)s) exp(m (x a)):
(2)
followed by dual variable update of the following form:
Ak+1 t AK= 1/2 (8)) - b).
where the 7n and 1/2 are the step-sizes.
4.2 Core set and least square estimates
To construct the least-squares estimates, let us assume for now that are given set of state-action pairs, which we call the core set C. By organizing the feature vector of each state-action pair in C row-wise into matrix & E [R|C xd we can write the covariance matrix as V(C, a) = Φ te + aT. For each (s, a) C. suppose the local access simulator to obtain an averaged Monte Carlo return denoted by 7(s, a). Then we gather all the state-action pairs into a vector ạ & RI For any state-action pair (8, a) E S x A. the least-square estimate of action-value fr is defined to be
have run Monte Carlo rollouts using the rollout policy with
Q(s = (ø(s, a), - g)
(3)
Since the algorithm can only rely on estimates for policy improvement and constraint evaluation, is imperative that these estimates closely approximate their true action values. In the local access setting, an algorithm may not be able to visit all state-action pairs, so we cannot guarantee that the estimates will closely approximate the true action values for all state-action pairs. However, we can ensure the accuracy of the estimates for a subset states.
Given C. let us define set of state-action pairs whose features satisfies the condition [lo(s, a)llv(c,a) S then we call this set the action-cover of C:
ActionCov(C) = {(s,[{sss)ee a) E S x A: [lo(s, (odssa))llvccal a)llv(c,))- S 1}.
(4)
Following from the action-cover, we have the cover of C. For state to be in the cover of C, all its actions a E A, the pair (s, a) is in the action-cover of C. In other words,
Cov(C)= {s E S: Va E A, (s, E ActionCov(C)).
For any COv(C), we can ensure the least square estimate Q(s, a) defined by eq. (3) closely approximates its true action value gx (x, a) for all a E A. However, such a core set C is not available before the algorithm is run. Therefore, in the local-access setting while planning. To achieve this, we build our algorithm on CAPI-OPI-Plan (Weisz et al., 2022), using similar methodology for core set building and data gathering.
need algorithm that will build core set incrementally
4.3 Core set building and data gathering control the accuracy of the least-square estimates
Confident-NPG-CMM does not collect data in every iteration but collects data in interval of O (In(1 + Po) poly(e -)), where po 2 0 is an user defined constant. During each data collection phase, the algorithm performs on-policy evaluation. Between these phases, it conducts (Im] + 1) off-policy evaluations, reusing data from the most recent on on-policy iteration.
By setting Pu to positive value, we impose upper bound of 1+ Pu on the per- pejetrajectory importance sampling ratio used in off-policy evaluations, and m is adjusted accordingly to maintain this bound. The total number of data collection phases is L = [K] mm] J + 1)J. where K is the total number of iterations. When Po set to zero, we have T. = K, resulting in a purely on-policy version of the algorithm.

---

ConfidentNPG-CMMD maintains a set of core sets {C,) one for each data collection phases. Each core set C, is a list of state-action pairs. Due the off off-policy evaluations, Confident-NPG- CMDP also maintains a set of data sets (Di) Initially, all core sets are empty, all policies are initialized to the uniform policy, and all data sets are empty.
The algorithm begins by adding the feature vectors corresponding to (so, a) for all actions a E A that are not in the action-cover of Co. These feature vectors are considered informative. For every (s, a) E Co. the algorithm adds an entry to Do and sets its value to the placeholder 1, indicating that there is no roll-out data yet. Then, in line 9 of algorithm 1, the algorithm finds the smallest integer I {o..... L} such that the corresponding D, has an entry without roll-out data (i.e., it contains the placeholder L). When such a phase is found, a running phase begins, denoted by & in algorithm 1. We note that when & = L + 1, the algorithm returns and no roll-outs are stored.
Since only one running phase l can be active time, and & can only take value E {0, {0.....: I.), the algorithm updates the policies of the corresponding iterations in line 27, updates the dual variables of these iterations in line 29, and extends the core set for the next phase in line 30.
Suppose during a running phase with E = I, while performing the roll-out in Gather-data subroutine (algorithm 3 in Appendix A), if any state-action pair (s, a) E S x AA is not in the action-cover of C,, the current running phase stops and the newly discovered state-action pair is added to Cu in line 15. by line 30.
The same state-action pair is then propagated to C1 and
Once a state-action pair added to a core set by line 7, line 15, and line 30, it remains in that core set for the duration of the algorithm. This means that any Cy. / E {0...... I. + }) can grow in size and be extended multiple times during the execution of the algorithm. When any new state-action pair is added to core set, the least-square estimate should be recomputed with the newly added information. This implies that the policy needs to be updated and data re-collected. However, we can avoid restarting the entire data collection procedure by updating only the policy for states that are newly added to the extended core set. We elaborate on this approach further in the next paragraph.
When the algorithm enters the running phase & = I. and the Gather-dat data subroutine returns, the LSE subroutine (algorithm 4) computes the least least-squares estimate Qi Qi using the most recently extended
core set C2 for each corresponding iteration k = kt. kt+1 - 1. Subsequently, Q% of line 23 of algorithm 1 is updated with the newly updated least- least-square estimates Qi, Qi- However, the policy Tk+1 will only be updated for states that are newly covered by C2 (i.e., s E Cov(Ce) \ Cov(Ce+1)). For any states that are already covered by Ce (i.e., s E Cov(C(+1)), the policy remains unchanged from its previous update using the Q' that time. By updating the policy in this manner, the accuracy guarantee of Q% (s, a) with respect to o L. A2 (s, a) is ensured not just for Tg, but for an extended set of policies defined follows:
Definition For any policy л from the set of randomized policies Hyand and any subset X C (S, the extended set of policies is defined as:
- = (='== ( (-11))= = =x'r ('(ss) all s E X).
By maintaining a set of core sets, gathering data via the Gather-data subroutine (algorithm 3 in Appendix A), making policy updates by line 27, and dual variable updates by line 29, we have:
Lemma 1 Whenever LSE subroutine in line 21 of Confuden--NGG-CMDP is executed during rumning phase É = for E (O...., LL). the least-square estimate Q7 (,, a) satisfies the following condition for all iterations k- = kig,... kee1 associated with this phase and for all 8 E Cov(Ci) and a E A,
-, (s) for all T'C II Covi(C):
(5)
where e' = (1+U) (w+ vaB + (w + v 2) with d= ò(d) and U is an upper bound on the optimal Lagrange multiplier. Similarly, for initial state so, we have
[50)s) v (so) S w VaB (w +ejāāā for all T'K E Cov(CC))
(6)
The accuracy guarantee of eq. (5) and eq. (6) are maintained throughout the execution of the algorithm.
By lemma 4.5 of Weisz et al. (2022) (restated in lemma 6 in Appendix A), for any past version C,ast
7

---

past associated with C,e, we have II Cov(CC) S II Cov(c of C and the corresponding policy "e This means that if eq. (5) and eq. (6) hold true for any policy in T Cov(c"") they will also hold true for any future updated policy Tk-
4.4 Differences between Confident-NPG-CMDD and CAPI-QPI-Plan
CAPI-QPI-Plan is designed for unconstrained MDPs and returns deterministic policy, which may be feasible in the constrained setting. contrast, Confident-NPG-CMMI returns soft mixture policy R,, ensuring that マx (a|s) > 0 for all (s, a) E S x A.
In constrained MDPs, controlling the dual variable via mirror descent adds an e factor to the sample complexity. Directly applying CAPI-QPI-Plan would increase the complexity to O(c=4) due the need to manage both the dual variable and estimation error. To address this, Confident-NPGG -aMpeett-GGGGDDPPP employs the natural policy gradient for policy improvement and leverages the softmax policy structure to perform off-pofl off-policy estimation, thereby reducing the complexity to Ō(
By employing a per-trajectory importance sampling ratio, we weigh the Monte Carlo returns generated from data collected in earlier on-policy phases, resulting in unbiased estimates of action values with respect to the target policy. However, this ratio can become large there a substantial difference between the on-policy and target policies. To mitigate this, the algorithm collects data at intervals of m, effectively determining when to gather new data as the policy significantly diverges from an earlier recent data-gat gatta-gatering iteration. By setting Po 0, importance sampling ratio, thus controlling the interval m for resampling on on-policy data to produce well-controleed estimators.
bound the per- per-trajectory
Key algorithmic differences between Confident-PPG-CMDPP and CAPI-QPI-Plan:
1. Policy Improvement Step: Confident-NPG-CMDD utilizes a softmax over the estimated action-values, whereas CAPI-OPI-Plan employs greedy approach.
2. Dual Variable Computation: Confident-PGG-CMP requires computation of the dual variable inherent in primal-dual algorithms.
3. Data Sampling Strategy: Unlike CAPI-QPI-Plan, Confident-NPee -PP.nMMDP does not sample data at every iteration but collects data at specific intervals to control the importance sampling ratio.
In the next two sections, we will demonstrate how these changes ensure a feasible mixture policy for the CMDP and address the additional analytical challenges.
Confident-NPG-CMDD satisfies relaxed-feasibility
With the accuracy guarantee of the least-square estimates, we prove that at the termination of Confiden--PG-CCMDDP the returned mixture policy ã satisfies because of the execution of line 30 in algorithm 1, at termination, one can show using induction that Co = C, = CL+1- Therefore, Cov(Cn) = Cov(C,) = Cov(C,). Thus, is sufficient to only consider Co at the termination of the algorithm. By line 7 of algorithm 1, we have ensured 8o Cov(C,).
feasibiiiiy We note that
By employing the primal-duil approach discussed in section 4, we reduce the CMDP problem to an unconstrained problem with a single reward function of the form r> = r + Ac. Therefore, we can apply lemma 12 from the Confident-NPG algorithm in the single-reward setting (see Appendix A) to our Confident-NPG-CMME
algorithm, replacing æ with n. Consequently, the value difference between x² and 7x can be bounded, which leads to:
Lemma Let ō E (0, 1] be the failure probability, > 0 be the target accuracy, and be the initial state. Assuming for all Cov(Co) and all E A. (2,(s))) d (s,a)) a)l S é' and
[ 2 (su)l S w VaB + (w + e)v/ doror all 7h E II Cov((C)) then, with probability 1 - 8.

---

ConfidentNPG--MDDP returns a mixture policy F.K that satisfies the following,
(50) - (80) - 1-7 + (v21n(A) + +1)(++U)
5c'
(1-7)2vR
U (5o) S $b -b-1xxx V (50)l+ 1 (1 (1- xx) + (v2 +
5c
PU
where e' = (1 U)w + (VaB + (w + +e) a)) with d = (d), and U an upper bound on the
optimal Lagrange multiplier.
By setting the parameters to appropriate values, it follows from lemma 2 that we obtain the following result:
Theorem that
With probability 1 ö, the mixture policy क returned by confident-NPG-CMDD ensures
(90) - 2xxx (5o) 1
2/ (5o) 2 b (Ōlv (0(va(1->)) [c)
if we choose n = (1 a -0(e((1-))))) K = - -1 90- -
Th Ô ((1 -1) 1/2), 1/2 = K- H H ((1-))-1)
0 (1 ?).
and = [K[[m]] + 1)1 00 total number of data collection phases.
Furthermore, the algorithm utilizes at most Ō( 35- - -)- queries in the local-access setting.
Remark 1: In the presence of misspecification error w > 0, the reward suboptimality and constraint
violation is (ww) + e with the same sample complexity.
Remark 2:
Suppose the Slater's constant is much smaller than the suboptimality bound of Then, the sample complexity is Ō (1- d²),
(ww) + c, and it is reasonable to set which is independent of Ç.
Remark 3: Our algorithm requires the Slater's constant Ç. which can be estimated by running
CAPI-QPI-Plan only on the constraint function c, treating it as an unconstrained optimization problem. This yields an approximation of max, (so). allowing us to estimate Ç. Performing this estimation before executing Confident-NPG-CMM adds only an additive term to the overall sample complexity.
Confident-NPG-CMDD satisfies strict-feasibility
To address the strict feasibility problem, where no constraint violations are permitted (i.e., og 2 b). the algorithm must solve more conservative CMDP. We define a surrogate CMDP with the tuple (S,A P, r, c, 7, D/ sg). where = + A for some 2 0. Note that > b, imposing stricter constraints than the original problem. The optimal policy of this surrogate CMDP ensures compliance with the original constraint and defined as follows:
A E arg max (50) s.t. (s()) 2 V'
Notice that A a more conservative policy than n², where x" is the optimal policy the original and applying
CMDP objective eq. (1). By solving this surrogate CMDP using the result of theorem 1, we obtain 7 k that would satisfy
- (50) of (so) S 7 s.t. of (so) 2 6
where E = ((w) e. Expanding out b', we have of (so) (+0))+---2 - If we can set A such that A ē 2 0, then of (sp) 2 b, which satisfies feasiiifeasi We show this formally in the next theorem, where ^ Oce(1 - -)) and is incorporated into the algorithmic parameters for ease of presentation.

---

Theorem 2 With probability 1 - 6, target < > 0. the mixture policy Tx returned
by confidentNPG- ensures that V (80) u (5o) I e and vi (50) 2 b, if
assuming the misspecification emvor w & <c2 - 7) + vāj-1, and if we choose = ( (1-1)111)))) -))- n = 0 - 7) -))
a = -(
H =
and L [K/[[m] + 1)] ((((-) (1-))) ((1-7)-)) m 0 (1-)(((1-7))
total data collection phases.
Furthermore, the algorithm utilizes most 0(-- ((--7)--0 1 queries in the local-access setting.
Remark 1: We note that by solving this conservative CMDP incurs higher sample complexity, necessitating a separate treatment for this setting. Additionally, in the presence of a misspecifica- tion error w' O, the strict-feasibility setting requires additional assumptions on w, whereas the relaxid-feasibility setting does not. The sample complexity of the felaxii-faasiiility setting can be independent of Slater's constant, whereas for strict feasibility, the returned policy must strictly adhere to constraints, and we cannot simply set Slater's constant to e and disregard its impact.
7 A discussion on memory cost and some implementation details
The overall memory requirement is I))
(I + 1)dd. The term dL + 1) comes from maintaining L + copies of the core sets, and each core set contains more than d state-action pairs. For each state-action pair in Cj for I E { L}, the algorithm stores trajectories consisting of tuples (s, a, c).
In phase L + 1, the algorithm terminates, so no roll-outs are stored. The second term d accounts for the elements stored in CL+1. which has no more than elements.
Finally, the last term is the memory required to store the least-square weights of the estimator during core set extensions. Each core set Cj can undergo up to d extensions. Recall that one state-action pair added Co at time, and subsequently propagated to C1, C2 and so on, ensuring that each core set contains no more than d elements. During every extension of Ct, the newly added state-action pairs are marked, and up to m + least-square weights are stored to account for the corresponding iterations associated with C, Since each weight vector has dimension d, and there are + 1 core sets maintained this manner, the total memory required to store all least-square weights is bounded by (T. + (m + 1)dd.
We store the least-squares weights because the algorithm must return mixture policy, which requires access to all policies .o...., -K- Instead of storing each Ty for k = o...., K across the entire state-action space, the algorithm tracks the state-action pairs newly added to each core set during extensions and saves their corresponding squares weights for each extension. With this stored information and the initialization of Tu. subroutine can reconstruct the policies (-((ss) for any and iteration & as needed. Please refer to Appendix E for a brief discussion on how to mark the state-action pairs, store the least-square weights, and use this information to reconstruct the policies as required.
8 Conclusion
We have presented a primal-dual algorithm for planning in CMDP with large state spaces, given qu- realizable function approximation. The algorithm, with high probability, returns a policy that achieves both the relaxed and strict feasibility CMDP objectives, using no more than Ô(c-3 0(c=332poly((" (1 7)=1)) queries to the local-access simulator.
Our algorithm does not query the simulator and collect data every iteration. Instead, the algorithm queries the simulator only at fixed intervals. Between these data collection intervals, our algorithm improves the policy using off-policy optimization. This approach makes it possible achieve the desired sample complexity in both feasibility settings.
10

---

Acknowledgments and Disclosure of Funding
Tian Tian would like to thank Roshan Shariff and Kenny Young for their insightful comments and helpful feedback during the preparation of this manuscript. Csaba Szepesvári also gratefully acknowledges funding from the Canada CIFAR Al Chairs Program, Amii, and NSERC. Lin Yang is supported in part by NSF #2221871 and Amazon Faculty Award.
References
Altman, E. (2021). Constrained Markov decision processes. Routledge.
Chen, Y., Dong, J., and Wang. Z. (2021). primal-dual approach to constrained markov decision processes. arXiv preprint arXiv:2101.1089:
Dai, J., Pan, X., Sun, R., Ji, J., Xu, X., Liu, M., Wang, Y., and Yang, Y. (2024). Safe RLHE:
Safe reinforcement learning from human feedback. In The Twelfth International Conference Learning Representations.
Ding, D., Wei, X., Yang, Z., Wang. Z., and Jovanovic, M. (2021). Provably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligence and Statistics, pages 3304-3312. PMLR.
Efroni, Y. Mannor, S., and Pirotta, M. (2020). apploration-explotaaaiie in constrained mdps. CoRR. abs/2003.02189)
Feyzabadi, S. and Carpin, S. (2014). Risk-aware path planning using hirerachical constrained markov decision processes. In 2014 IEEE International Conference Aulomation Science and Engiinering (CASE), pages 297-303.
Gattami, A., Bai, Q., and Aggarwal, (2021). Reinforcement learning for constrained markov decision processes. In International Conference Artificial Intelligence and Statistics, pages 2656-2664. PMLR.
Ghosh, A., Zhou, X., and Shroff, N. (2024). Towards achieving sub-linear regret and hard constraint violation in model-free rl. In International Conference on Artificial Intelligence and Statistics, pages 1054-1062. PMLR.
Girard, J. and Reza Emami, M. (2015). Concurrent markov decision processes for robot team learning. Engineering Applications of Artificial Intelligence, 39:223-234
Hao, B., Lazic, N., Yin, D., Abbasi- Yadkori, Y., and Szepesvari, C. (2022). Confident least square value iteration with local access to simulator. In International Conference Artificial Intelligence and Statistics, pages 2420-2435. PMLR.
HasanzadeZoomuz, A., Kalathil, D.,, and Shakkottai, S. (2021). Model-based reinforcement learning for infinite-horizon discounted constrained markov decision processes. IJCAI 2021.
Jain, A., Vaswani, S., Babanezhad, R., Szepesvari, C., and Precup, D. (2022). Towards painless policy optimization for constrained mdps. In Uncertainty in Artificial Intelligence, pages 895-905. PMLR.
Jin, C., Yang, Z., Wang. Z., and Jordan, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pages 2137-2143. PMLR.
Kakade, S. M. (2003). On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom).
Kalagarla, K. C., Jain, R., and Nuzzo, P. (2021). A sample-efficient algorithm for episodic finite- horizon mdp with constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8030-8037.
11

---

Kamran, D., Simão, T. D., Yang, Q. Ponnambalam, C. T., Fischer, J., Spaan, M. T., and Lauer, M. (2022). A modern perspective on safe automated driving for different traffic dynamies using constrained reinforcement learning. In 2022 IEEF 25th International Conference Intelligent Transportation Systems (ITSC), pages 4017-4023. IEEE.
Kearns, M., Mansour, Y., and Ng. A. Y. (2002). A sparse sampling algorithm for near-optimal planning in large markov decision processes. Machine learning, 49:193-208.
Kitamura, T., Kozuno, T., Kato, M., Ichihara, Y., Nishimori, S., Sannai, A., Sonoda, S., Kumagai, W., and Matsuo, Y. (2024). policy gradient primal-dual algorithm for constrained mdps with uniform pac guarantees. arXiv preprint urXiv:2401.17780
Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
Lattimore, T., Szepesvari, C., and Weisz, G. (2020). Learning with good feature representations in bandits and in with a generative model. In International conference on machine learning, pages 5662-5670. PMLR.
Liu, T., Zhou, R., Kalathil, D., Kumar, P. R., and Tian, C. (2021). Learning policies with zero or bounded constraint violation for constrained mdps. CoRR, 0oss/2066026844
Liu, T., Zhou, R., Kalathil, D., Kumar, P. R., and Tian, C. (2022). Policy optimization for constrained mdps with provable fast global convergence.
Miryoosefi, S. and Jin, C. (2022). A simple reward-free approach to constrained reinforcement learning. International Conference on Machine Learning, pages 15666-15698. PML..
Sidford, A., Wang, M., Wu, X., Yang. L., and Ye, Y. (2018). Near-optimal time and sample complexities for solving markov decision processes with a generative model. Advances in Neural Information Processing Systems, 31.
Vaswani, S., Yang, L.., and Szepesvári, C. (2022). Near-optimal sample complexity bounds for constrained mdps. Advances in Neural Information Processing Systems, 1-3110031121
Wachi, A. and Sui, Y. (2020). Safe reinforcement learning in constrained markov decision processes. In International Conference on Machine Learning, pages 9797-9806. PMLR.
Weisz, G., Amortila, P., Janzer, B., Abbasi- Yadkori, Y., Jiang, N., and Szepesvári, C. (2021). On query-efficient planning in mdps under linear realizability of the optimal state-value function. In Conference on Learning Theory, pages 4355-4385. PMLR.
Weisz, G., György, A., and Szepesvári, C. (2022). Confident approximate policy iteration for efficient local planning in q pi realizable mdps. arXiv preprint arXiv, 2210.
Weisz, G., György, A., and Szepesvári, C. (2023). Online rl in linearly rrealizzll mdps is as easy as in linear mdps you learn what to ignore.
Wen, L., Duan, J., Li, E., Xu, S., and Peng. H. (2020). Safe reinforcement learning for autonomous vehicles through parallel constrained policy optimization. In 2020 IEFE 23rd International Conference on Intelligent Transportation Systems (ITSC), pages 1-7.
Yang, L. and Wang. M. (2019). Sample-optimal parametric q-learning using linearly additive features. In International conference muchine learning, pages 6995-7004. PMLR.
Yin, D., Hao, B., Abbasi- Yadkori, Y., Lazić, N., and Szepesvári, C. (2022). Efficient local planning with linear function approximation. In International Conference on Algorithmic Learning Theory, pages 1165-1192. PMLR.
Yu, T., Tian, Y., Zhang, J., and Sra, S. (2021). Provably efficient algorithms for multi-objective competitive rl. In International Conference on Machine Learning, pages 12167-12176. PMLR.
Zheng, L. and Ratliff, L. (2020). Constrained upper confidence reinforcement learning. Bayen, A. M., Jadbabaie, A., Pappas, G., Parrilo, P. A., Recht, B., Tomlin, C.,, and Zeilinger, M., editors, Proceedings of the 2nd Conference on Learning for Dynamics and Control, volume 120 of Proceedings of Machine Learning Research, pages 620-629, PMLR
12

---

A Confident-NPG in a single reward setting
The pseudo code of Confident-NPG with a single reward setting is the same as Confident-NPG-CMMe CMDD in algorithm I, except that line 24 and line 29 will not appear in Confident-NPG. Additionally, the LSE subroutine returns just Q", and the policy update will be with respect to Q". For the complete pseudo code Confident-NPG in the single reward setting, please see algorithm In the following analysis, for convenience, omit the superseript
Algorithm 2 Confident-NPG
Input: 8o (initial state), (target accuracy), E (0, (failure probability), c 2 0, K
2 (l(()))
(1-
71 = (1 (1-11)
2 (4)) K m In 2n 372
1n(1+pp))
L LLKJ/([m] + 1]]-
[K] } m Uniform(A), (% a) 0, for all 8, E x A, and A < O. For each phase E (O...., L + 13 C + () D1 + (
Initialize: for each iteration k E {O....,
for do
2:
if (s0, a) & ActionCov(Co) then Append (so, a) to Co: Dol(so,a)) +-
3:
4:
while True
main loop
5:
Get the smallest integer i s.t. De[2'l =1 for some 2' C2
6:
Get the first state- action pair 2 in Ce s.t. De[2]
7:
i = L + then return π
8:
ke +
fx 1-ex ([m]+ +1
b iteration corresponding to phase
9:
(result, discovered) +- Gather-data(Tke Ce, a, 2) if discovered True then result is a state-action pair Append result to Co: Do[result] +1 break
10:
11:
12:
13:
14:
result is of H-horizon trajectories The starting De[2] +- result.
15:
16:
if Az' E C s.t. DrR2 [2]]= =1 then
ke+1 Ke + 1) k2 (Lm] + 1) S [K] otherwise [K]
18:
update policy for every for k ke..... k4+1 do
ket1 1] using Ce, De
19:
Q (SE(C,, De, Th, Tk.)
> update variables and improve policy for all 8 E Cov(Ce) \ Cov (Ce(),)), and for all A do (x, < Trunc o. (x)
22:
23:
24:
for all 8, E S x A do
(alss
if s E Cov(Ce+1) otherwise
25:
T (als) -
TT((ass)
exp(n (s.e))
Evee se (a'ls) exp(n (g(e,)))
for = E Ce s.t. E Cr+1 do Append to C4+1i D=+1 +1
27:
A.1
The Gather-data subroutine
Given a core set C, a behaviour policy 14 a starting state-action pair (8,a) E A along with some algorithmic parameters, the Gather-data subroutine (algorithm 3) will either 1) return newly
13

---

Algorithm 3 Gather-data
Input: policy n, core set C, regression parameter
(111))² 26B"(1-0)' H
In(4/(e(1~>])
1-y
(1+00) adL
2c-(1-1) starting state and action (s, a)
Initialize: Trajectories + ()
1: if's Cov(C) then
2: for A do
3:
if (s) ActionCov(C) then return ((s, a), True)
4:
for [n] do
5:
T, + ()
6:
So 4-8, 8, A
7:
append So
Ag to g0
8:
for = 0,..., H do
9:
St 5h41 1141 Chi simulator(S}, AA)
if +1 $ Cov(C) then for a E A do if (S ()) ActionCov(C) then return ((S+ a). True)
11:
13:
> no new informative features discovered 4 x(-1S)+11 append R1 C Ch41 Si S1 to T.
14:
16:
append - to Trajectories return (Trajectories, False)
discovered state-action pair, or 2) return set of n trajectories. Each trajectory is generated by running
the behaviour policy μ with the simulator for H consecutive steps. For 1.... n, let r denote the ith trajectory starting from s, to {S] = s, Ai = a, R2 Cj ... SH A Rig C S } Then the i-th discounted cumulative rewards G(r > 7² R For target policy æ, then the empirical mean of the discounted sum rewards as follows,
1 E pl plr..a) G(Ts.a) ((s
(8)
where P(T) = - x (8))
p(4), is the per-trajectory importance sampling ratio.
For some given 3 and ā, we establish the following relationship between the target policy i and the behavior policy
s.t. sup (fpl a) S In(1 Po)
(als) exp(((s
2H
where () A R and po 2 0 is given constant. By establishing relationship stated in eq. (9), the importance sampling ratio pl p(T can be bounded by + Po this is proven in the following lemma:
Lemma
Suppose the trajectory r = (Sa, Ao: Rí, SI, A1. ,S An-1, Rτ) sampled from behaviour policy μt, and is related to the target policy n via eq. (9). The per-trajectory importance sampling ratio
p(T) -1 #1 ((An)A)
<1+ Po-
(A)
14

---

Proof: Let tu = sups,a (f(s, a)), where f is defined in eq. (9). For any (s,a) E {(S), An)
exp(f(s.a)) a))
exp(lo)
<(a|s) = p(als) En exp((ss, S {u(aas) S |اals) exp(2la).
((als) expls) exp(-1o)
We see that T(als) p(ale)
I exp(2la), and it follows that II ((A) lo < [n([+eo), then exp H exp 2H im(1+po) 2H
p( SSh) I cx)((2g By assumption,
Po-
Define the probability distribution Pr.s.a over trajectory {Sh, An, RA+1 R121 as follows: the initial state So set deterministically s, and the initial action Ag is set deterministically a. For each subsequent time step h 2 O, the next state SA+1 is sampled according to the transition probability P(-[Sh, An,, and the next action Ah+1 sampled from the policy x 5-115h+1). follows that Ex,,,. denotes the expectation with respect to distribution Ps.e,a.
Now, show that for all (s, C, (Ā(s, a) (s. a)l S c, where Additionally, the accuracy guarantee of (g(ss a) In (s, a) I c continues to holds for the extended set of policies defined in definition 1. Formally, state the main result of this section.
is a given target error.
Lemma 4 For any 8,0 E S x A, C S, the Gather-data subroutine will either return with ((s',a'), True) for some s' &X, will return with [s, a)}, False), where D[(s, a)] is a set of n independent trajectories generated by behavior policy starting from (8, a). When Gather-data for returns False for (s, a), we assume 1) the behavior policy j and target policy x for all the states and
actions encountered in the trajectories stored in D[ a)) satisfy eq. (9) and 2) q(s, a) is unbiased estimate of Ex' ... D H-- 7hh +*R++1] for all n' Xx Then, the importance-wert weighted return @(s, a) k=0
constructed from D [8, a) according to eq. (8) will, with probability 8',
lã(s, a) - yar (8, a)l Se for all n' E El
Proof: The proof follows similar reasoning to Lemma 4.2 Weisz et al. (2022).
Recall D[(s, a)] stores number of trajectories indexed by i, where each trajectory Tia
(SH 8, Ai a, Si μ. The per-trajectory importance sampling ratio p(T),a)
= - ((A))))) and the discounted cumulative return is 2h= //R By the triangle inequality, (()))))))
(S)
H-1
(0( - (s( =
Σ
R 9- (s(ssa)) a))
h=
((A)))))
p(
i=1
h=0
H-1
P(T Σ h R8
E
Σ
7"th
RA+il + En
Σ rh Ra+1 qu (s) (10)
n1
The goal to bound each of the two terms in eq. (10) by & so that the sum of the two is 5.
By assumption, the policies and μ satisfies eq. (9) for all state-action pairs (S, Af, ex- tracted from the i-trajectory < Second, q(s, a) is assumed be unbiased estimate of Em,a,
E 7th RR+1]. Note that for all i I,...,n, n, the importance weighted cumulative 7 / are independent random variables, and the value of each such random This is because 1) Σm''' 7" R S ب since the rewards take values in the range of [0, 1]. and 2) p(T(.a) $ 1 + pa by lemma We apply Hoeffding's inequality.
return p(Tá.a) Σ
11-1-
variable
0, 1+
I-7
H-1
H Rh+1
> c 2) < 2exp
2n ($)
PP
p(
Ri+t - E
3.a
4
1400
i=1
h=
h=
T-
15

---

Then, we have with probability 8//2. where 8' 2 exp
2nee
the first term in eq. (10)
I Ei= p(T
En=o H-1
7 R A
R Bx,,,0 Em=0 H-1 / I 4. For the second term in eq. (10),
H
n 1-7
B a, Σ
?th T RR++ 2x (8, = En, Σ
7 Ra+1 S
11
By the choice of H In(4/(1-2]k) we have - S 1. Putting everything together, we get (ā(s,a) a) - 4, (s, a)] 5. To get the final result, we need to upper bound [4a (s,a) - qs (s, a)l by i. so that (ā(5, Ox (s, a)l s (7(s, a) Zr (s) + (s, gx (s, a)l S.
1-7
Recall that and n' differs in distributions s, AD = a, Si....). .) let be the smallest positive integer such that ST & X, then the distribution of the trajectory (So An a, SI,..... Sr) are the same under Pr,s,a and Pri,s,a because (-1ss) = n' (+1s) for all E X.. Then,
states that not in X. For trajectory (Sa
T-1 1
(x(88,) a) - 2 (8, = E7,,,
Σ 10=
rt Ru + uz vx(r)
ET'', ,8,a
Σ 1=
7t Ru + 7 (e((
= Br,n [T (ST)) - Er'' [T"0-- (+ (ST)]
E Pa. (S == s', Ar-1 = d') P P(Srls', d'))"''=(80
8'EX,a'
Σ Pri = 8 AT-1 a') P(Sr a' u.)
s'E
Σ
Pa Pr,,,(SS-11 - AT-1 a') P(S d'nn" (u=(ST) (Tr)
8'EXaa'
Σ
P Pr.sa(ST-1 -
1
Em,,, h-21
1-
1
' P Px (T=t) =t)
Pr.,,a (T t)
Pr Pr.e.a (T H
1-7
H
< 1 - PA, (1 ST H) + 1-7
Recall Pr. (1 TT < - Evex,'Es - - d')P(Srls', and
recall Sp = 8, Ag = a, then by the law of total probability, we have
(S, 8', A, = aa)
Σ
IT P = S141sS = si A; = a;) (II, (A4 ag|S;= =s))
81 01m
<(A; = ag|S; = si)
Σ
P = 8141/S = si A = a
u(A; = as|S; = si)
4(A, aiSs s;)
81
01
< (1)
Σ
= $ =5, = = = = = s.)
(11)
= (1 + s' A d').
To get eq. (11), lemma 3 and that <t H -
16

---

Altogether, we have
In (s, a)
qr (s, a)l
--1
Σ
(1+ Pua s', d') c')P(Srls',d)
t= d'EX,a'EA
7
1-7
1 + Po Pa ( ST H) +
Now, bound (I T < H). For each (s,a) E X, in the ith rollouts, let (( be indicator function, where it takes the value 1 when the event that Sy & X occurs during $ T < H. Then E,,,,a (I. a)] Pu,s,a( (1 T < H). By another Hoeffding's inequality,
1 Σ 11
<(1 (11-2)] 4(1 + po)
2n(e(1 7)/ po))2
a(s,a))
S 2exp
(1)
2nE
exxp
8'.
2
L+ I-7
Then, with probability 1 1 8//22,
(en,aa(((ss)) 1 Σ Lis, a)l - c(1 - 7)
(12)
4(1 + pn)
When Gather-date subroutine returns, all indicators [;ss, a) = 0 for all (8,a) E X and i [n], then
we have
aa (1 11) S <1 ?1
(13)
4(1 + Pb)
Putting everything together, we have the result.
A.2 The LSE subroutine
Algorithm LLSE
Input: C, Ti
1: for s,a C do
2: for every Ti E D[(s a)] for every i E [n] do
3: extract (S). Ab: Ri Cj. Si Ai ... S S A from T
4:
compute (s, + Σ Sd as) + Enz CC
compute (3)) + I H 18(
5:
h=1 (TAN))))
6:
+ (s.aa)
('(s + 1 E. ((s
7: w -
:ī w - (0. + +al) कह
8: a) + (w", o(s, a)). (s, + (w o(s, a)) for all s, a
return Of
Given set C, set of trajectories, behaviour policy μ4, target policy ग, the LSE subroutine (algorithm 4) returns a least-square estimate Q of qx-
If the core set C is empty, we define Q(.+) to be zero. Then, for target accuracy > 0 and a uniform misspecification error w defined assumption 1, we have a bound on the accuracy q with respect to 4x as given by the next lemma.
17

---

Lemma's 5 [Lemma 4.3 of Weisz et al. (2022)] Let x be a randomized policy. Let C = {(s a; [EMM be a set of state-action pairs of set size N E N. Assume for all i E [N], (ā(s;, a;) - qu (8,, a:)l Se Then, for all s, a 8 A, 14(s, a) - gz (s, a)l I w lIo(s, (vaB+ (w (w+ +c)
Proof: If assumption holds, then there exists a wa R., ||w I B such that for any (s,a) S A, lØ(s, " W Ox (s, I w, where is the misspecification error. Let wa a(C,a)-'Eee o ai)o(ss a.) wx. For any (s,a) E S A, recall Q(s,a) ((s.a)"ul w, where w V(C, a) EiENN (ss,, ai){(s;;);) It follows that
[Q(s, 0) - ($( I l0(s, a) (w wxxl ) + lø(s, a) (w> - wx)l + lō(s, a) wx 4x (x.
Twx
(14)
To bound the second term in eq. (14), we have
(0(8a) a) [ wx ) - l - -
s (1(vv_a)llvcc..)-111 aV -Va(Cca)"walvcc.... wullv(c,,)
= allo(s, (l)c,,)))l((c,a)--
wr 11 (V(C,a))
I calléss,a)llvcc.m |
|x |x ||
(15)
< <allo(s, volio(e,))llvccca--1
VaBllo(s, a)llv(e..)-1.
Let a be the smallest eigenvalue of V(C, a), then by eigendecomposition, V(C, QAQT: > Q(al)QT aQQ 2 al since QQ is orthonormal. This implies that a) L which
leads to eq. (15).
Finally, we bound the first term in eq. (14). For every i e [N], let & 6(s,, a "y a( a.). Then,
4n (s,, (s, - o(s; ai) Twxl I& = (ā(s;, a.) ols;, a:) wnl S ((s);
SEtw. w.
follows that for all s, s, A, (ø(s,a) (w - x+)l = (V(CC
Σ cE[N]
a(s;,a)) (g(s;, - a Tw+) o(s. a))
a) -1 Σ ais
ME(M]
< KV(C, (.s,,
KE[N]
(w+e)
Σ
(sh,
iE[M]
< <w++eVVC
(()) by Holder's inequality k
$ (w++)VCC
0(s (s,,)TV(CCa)==
o(sn, a(s,)))(( (((s,) iE[N]
Σ
$ <w++oVC
((C,
o(si, (5) + +al (((,0))) (E[N]
Σ
= (w + (ls
Mu++evNNle (1oos a)
Putting everything together complete the proof.
18

---

A.3 The accuracy of least-square estimates
Given a core set C and a target policy и, for any Cov(C), a A, the feature vector Φ(s, a) satisfies ||o(s, ()clv(c,,))> I 1. Then, by lemma 5, have (Q. a) qu (s, a) = (lw + for any E Cov(C). In this section, we verify whether this accuracy is maintained throughout the execution of our algorithm.
We note that policy improvements can only occur during running phase f = L. When all (s, a) pairs in C. have their placeholder value replaced by trajectories, algorithm 2 executes line 17 line 27. During each iteration from by to ké+1 1, the LSE subroutine is executed. The accuracy of Øs is used bound the estimation error in lemma Therefore, we will first verify that the accuracy guarantee of (s, s. a) used in lemma 4 is indeed satisfied by the main algorithm and maintained throughout its execution.
Once a state-action pair is added to a core set, remains in that core set for the duration of the algorithm. This means that any core set C₁ for 1 E {0. ..... L 1} grow in size over time. When a core set C₁ is extended during running phase & = | 1, the least-square estimate will need be updated based the newly extended in running phase = I, which contains newly discovered features. However, the policy is update only for states that are newly covered by the extended core set C using the newly improved estimates. Meanwhile, the policy for other states that have already been updated by prior softmax update remain unchanged. Note that after line 27 of algorithm 2 is run, the next phase's core set C++1 will be set to G. which means that any state that was once newly covered by Cj is no longer considered newly covered. Consequently, the policy for those states will remain unchanged throughout the rest of the algorithm's 'ss execution. By updating the policies accordingly, we arrive at the following lemma, which will be crucial in proving the accuracy guarantee of the leaat-squares estimators.
Lemma 6 For any E L), let Crea be any past version of Ci and let past for k = ",,-.. ki+1 - 1 be the corresponding policies associated with Crae If at any later point dur- ing the execution of the algorithm, Ty is updated again, then it holds that
The E mm,, S IT_eer (Cov(o)"))
Additionally, for any states that have been covered by Cjas, it will continue to be covered by C₁ throughout the execution of the algorithm. In other words, 8 E Cov(Crrrt) C Cov(C,).
Proof: The proof follows similar logic to Lemma 4.5 of Weisz et al. (2022). Recall for matrices A, B, A 2 means that
B is positive semidefinite.
Because Ct C.nat there may be more rows added &c, than &epe. Recall V(G,, a)) DJ &c, +al, and likewise for V V(Croo)) except Pe, is replaced by Cheat Note that both (CC a), VCCpatt .a) dimension d d. Let C/ contain set of state-action pairs that in C. \ A.TT.. Then, ((G V(Cpaat .q) E(s.))c; a ())(,))(s,) a)T. Since any rank-1 1 matrices is positive semidefinite and their sum also positive semidefinite, follows that VCC,, a) 2 V(C.est..)
Since ((C,,a) a) and V(Crast a)) are symmetric positive definite matrices, then it follows that a(G,a)-1 s VC (V( aa-1, From this, we see that for any x Rd, | ||=lll .o)- Then, it follows that ActionCov(CTT"1) S ActionCov(Ci). and likewise Cov(c S Cov(C.). Therefore, for an E Cov(Cru))) the same state & E Cov(C,), and the second result follows. Finally, by the definition of the extended policy definition II Cov(CC) II _ )
Lemma For any E {O..... L} and any (s, a) E Cr. the importance-weighted qu (s. a) computed in the LSE subroutine during the running phase = is an unbiased estimator of the expected discounted reward:
H-1 Σ
Eng,s,a s.a
th Rh+1
for The E Cor,)Co((C.)>
for iterations ks ... k1t1 associated with this phase.
19

---

Proof: For the algorithm to execute the LSE subroutine, every (s, a) E C must have its placeholder value 1 in Dil(s, a)] replaced with trajectories. Trajectories are stored in Dj only when the Gather-data subroutine returns "discovered is False" during the running phase ensures that every state within these trajectories has passed the uncertainty test, thereby ensuring that all such states are in the cover of C₁ and will remain in the cover of C for the duration of the algorithm, as established stored in Di, they remain unchanged throughout the algorithm's 's execution. We aim to show that To s, a) computed using Di[(s, a)]. is an unbiased estimate the stated quantity for all it- erations associated with the phase. This will be established through the following inductive arguments.
= 1. This
lemma 6. Additionally, once trajectories for a (s, a) E C are
Base case: for (s,a) E Ct. the trajectories are generated and stored in Di((s, a)] for the first time during the running phase { I.
We let T denote the i-th trajectory (S) A R SH-1 A/ R2y) generated by The interacting with the simulator, and there are n such trajectories stored in Dil(s, a)]. Then, for all k ..... kit1 1, the return
TA (A)1S)) Kh (4%)
(s, = 72
G(T
where G(Ti,a) => 2h=0 7 R R1+11
The behavior policy Th, is updated in a previous loop through the algorithm when / = / For iterations, starting with k = K2 + l,..., k1+1 1, the policy Tr is updated in iteration k - 1. Thus, the most recent policy wa and the behaviour policy Th, are available for the computation of the
importance sampling ratio: pe(Tá,a) - Tu (A),S)) We show that the importance weighted mx. (5) return pk (F,,a) an unbiased estimate of 3T G((T,a))
H
BREy 8,0
pa (
7hh
R
h==
8(8, (ls,a)P(S. ( So 8 Ao (..
H-1
= =Bmapisa
7 Ri
P(Si ((S,a)((Sila
8, a) (A1 Th, (A SH
h=
H-1
=Eng,s,a
Σ 7 Rh
where ö(s, a) is the dirac-delta function. Note, for the on-policy iteration k: = ky, the importance sampling ratio px(Ti,a) = 1, and the result is trivially satisfied.
Finally, since all the states in the trajectories are in Cov(C,, it follows that any policy मं Cov((C) produces the same (x(T),a). The return Pk ) is an unbiased estimate of E for all T/K Cov(CC). This is true for all 1..... n. Consequently, (s,s, a) is an unbiased estimate of F H R for all for all T/K E II Cov(C.))
The requirement that the importance weighted ōR be unbiased for all policies Th E 11,, Cov(()) is important. This ensures that if π. is to be updated in a future loop through the algorithm again, the estimates remain unbiased and unchanged.
Previously generated trajectories: for any (s, a) E C,, the trajectories have already been generated and stored in Di[(s, a)] during previous loop of the algorithm when & f=1,
past for k Let D) [(s, a)] denote a past snapshot of the data stored for a (s, a) E C. Let x ki.... k441 denote the policies associated with Cgust after line 27 has been run. Finally, let i.past denote the i-th trajectory stored in [(s a)).
Assume the importance weighted return ( i.past (r i.past is an unbiased estimate of Ts.a
Eaa. [G (.psstt for all से E II _e [Covcepa) for = ki.... k+ 11 When the algorithm executes a loop with & = 1 again, by lemma 6, the most recent policy E IT x,, Cov(Ci) C IT (Co((cp") i.past i.pust is also unbiased estimate of Eng, ,, [G(T(p=))) for all Th. E 11x Cov((C). then pa (T (Tia))
20

---

Once Djatt ((s, a)] is populated with trajectories, Di a)] remain unchanged throughout the execution of the algorithm. Therefore, G(Té,a) Ga Since all the states in the trajectories are in Cov (C(aat) S Cov(Ci) by lemma 6, any policy # E _ CCv((c"") produces the same Ps (Té,e) Thus, we have pk ( = Ph (T Appstt )T G (ppsst It follows that pk (T (T ((T is an unbiased estimate of B.g....a (T),a)) for all Tik E 11 Cov(Ci)) This is true for all I,..., Consequently, (s,s, a) is an unbiased estimate of Brg.a,a 21=0
"
H- R for all T CoveCC)(
Lemma 8 Whenever the LSE-subroutine of Confidemt-NPG is executed during a running phase = forl E (O...., LJ. the behaviour policy The (-16) and larget policy Tx Tx(-(s) for k -ig...., kg+1 satisfy eq. (9) for any E Cov(Ce).
Proof: Recall that the behavior policy Th, is updated during previous loop of the algorithm when L - 1. By the time the LSE subroutine is executed, Thy will be the policy that generated the data. Therefore, for the on-policy iteration where k kr. eq. (9) is trivially satisfied.
For subsequent iterations, starting with = kg 1,....,.e. .kt1 - 1, for any 8 E Cov(Cr), the policy T& (-|s)) will have either performed a softmax update for the first time or remain unchanged from a previous softmax update based on an earlier least-square estimate. Either way, for any Cov(Cr), the target policy TTę and behaviour policy The relate to each other in the form of T& (+1s) oc Txe (-1s) exp(m Eis, a)). Since Q2(s,a) E ا
[0,
for any t = kgy...,k k 1,
then it follows that
k-
M m((Im + 1) 1)
Σ a) S ml(k - ke) 1-7
S 7
t=k
By choosing 1/1 (1 7)
2 [An((AI)
H
In(4/e(1 m po()+ - and K
2 2ln(4) [1 (1-
K
1-y
have (1 ([Im|+1)-)) 91m I-y
ln()pp))
Then it follows that eq. (9) is satisfied.
1-4
2H
Lemma 9 For any 1 E {O..... L and any (s, a) E Ct. the importance-weightee qu (s. a) computed in the LSE subroutine during the running phase = satisfies the following with probability 1 8',
17x a) - qr( (s, a)) Sc c for T/K E Cov(C))(
(16)
for all iterations k- = ka,..... k41 - 1 associated with this phase.
Proof: We apply lemma to each (s, a) E Ct. To ensure the applicability of the lemma, we verify its two conditions: 1) the policies satisfy eq. (9) and 2) the estimate are unbiased.
We note that when the LSE-Subroutine is executed during running phase with é = I, the Gather-data subroutine has already completed, and the algorithm trajectories for each state-action pair (s.a) E C, are stored in [ss a)). For any trajectory to be stored in Dj, this means that every state within the trajectories has passed the uncertainty test, ensuring that all such states are in the cover of G. By lemma 6, these states will continue be covered by Ct throughout the exccution of the algorithm. The implication of this is that all the states in a trajectory of Di a)] satisfy eq. (9) by lemma 8.
Second, by lemma 7, the importance weighted return (s, a) is unbiased estimate of any Emi.,., D nh Ro+1 for all A E Cor,,Cor(C,) Altogether, by lemma 4, we can ensure eq. (16) holds.
Consider past loop through the algorithm with e = I, let chast be the core set and n past for k == .i...., k141 - be the policies associated with Cpest after line 27 has been run. If eq. (16) holds for all सt E II CCo then the accuracy of qR will continue to hold for any future update of T because Thk E Cov(()) C [C by lemma 6.
Lemma 10 (Weisz et al. (2022)) At any time during the execution of the main algorithm, for all I E L), the size of each C, is bounded:
|c|| < 4d (1+ 4 =d ) =d
21

---

where the a is the smallest eigenvalue of V VC, (C, a) and N is the radius of the Euclidean ball containing all the feature vectors.
Lemma 11 Whenever LSE subroutine of Confident-NPG is executed during a rumning phase & = ffor 1 E 10....,Be. L}, the least-square estimate Qu(8, a) satisfies the following condition for all iterations k ke, ket1 associated with this phase and for all E Cov(Cz) and a E A,
12x(s, a) 9 (s. sé' for all T Covl)C))((C))
(17)
where e' = w voB + (w +cVā
Proof: We prove the result by induction similar to Lemma F.I of Weisz et al. (2022). We let
CT , Qi to denote the value of variable Ci, Tk. Qs at the time when line 17 to line 27 were most recently executed with = ( a previous loop through the algorithm. If such time does not exist, we let their values be the initialization values. Only after the execution of line line 27 will CT change and as well as Cl+1, and this the only time that C++1 can be changed. Therefore, at the start of new loop,
that C++1 = CT- This also holds at the initialization of the algorithm, we conclude that at the start of each loop, Cov(C(+1)
Cov(CT).
At initialization, Qx 0 for any & E (0,..... K and C () for all I E (o.....,L) L}. By applying lemma 5 (Lemma 4.3 of Weisz et al. (2022)), for any (8,a) E A.
[Qu(s,)) a) gmg (s.a) a) S ww voB sé.
which satisfies eq. (17).
Next, let us consider the start of a loop after L = is set and assume that the inductive hypothesis holds for the previous time line 17 to line 27 were executed with the same value of f = l. For any 8 E Cov(C-1)) policy Thy (-Is) would have already been set in a previous loop with value - and remains unchanged in the current loop. By lemma 9, the condition of lemma 5 holds, then by lemma 5, we have for any E Cov(C_1).
(0, 1or (1, sw vaB+ (w + +)vV for Twद E TI
"i Cov .)?
where [| ) )lv(c, 1 S because 8 E Cov(CT-n and 1CT=1 S d by lemma 10. Recall by definition, Qu, QT, Th: The C1 CT and Cov(C) = Cov(CT,)) follows that for any E Cov(Ci), ( (s t (s, S é' for TRद E Cov(CC)
For any s that is already covered by C, (i.c., s E Cov(CT)) )) and for any off-policy iteration & k + 1,... ke41 - 1, (s. Q (s. Additionally, the policy Te (-(s) would already have been set in a previous running loop with the same value of i and remains unchanged in the current loop. For E Cov((T). ), by lemma 9, the condition of lemma 5 holds, and then by lemma 5,
14 (s.-) ax (s.
VoB + (w +eVV for The II Cov(CT))
. < 1 because E Cov(CT) and |CT| S Vd lemma 10. By lemma 6, where ((((s,))lvic; (0)+
Cov(CC)) C 11 Cov(CTT) By definition, Qu(s,)) Q (3,-) for Cov(C(+1) Cov((C), [Qu(s,)) 40. (s, I e' for any T (ov,,
Finally, for any that is newly covered by Ct (i.e., & Cov(C++1)), and for all h: .a...., k Qu(s, -) = (s. -). By lemma 9, the condition of lemma holds, and then by lemma 5, we have 1Qu(s, -) 9-ç (s, )1 S w + VaB+ (w + v for ne E 11 Cov,CC)
where [|o(s, )ll(c... < and |CJ| < by lemma 10.
Lemma For any 8' E (0, 1}, a target accuracy e > O, misspecification error w 2 O, and initial state 80, with probability at least 1 - 8', the value difference between any n E IInand and the mixture policy it k returned by Confident-NPG has the following bound:
K-1
(=0) UF ( S
4e'
1
Σ
(sa)
((u((s))), ((
T-(-11'1))
1 1-7 K(1 - 7)
k=0
22

---

Proof: For any LE {0,..... ...................... L} and for all iterations l = ki:.... ks+1 1 associated with 1, define
(-(ss))
if Cov(Ci)
क (-|s)
a (-1ss)
otherwise.
Then, for any E Cov(Ci),
Un (s) - UTa (s) = (s( - 1/ (8) + u/ (8) Una (s)
1 E. Eo'nd (a) (a (s', T(11s') (-1=1))
by performance difference lemma
(grg (0, ) m - (ym (s, :), +x((11)))
11
where (s) is the discounted state occupancy measure induced by following starting from s. To bound term II, we note that for any 8 E Cov(C),, we have oh. (-18) = nu = and both
Thi Th (+1s) E Cov(c.) By lemma 11, we have for any E Cov(Ci), a A. (8, gog (s) S é' for any T E Cov(C.) Then, for any s Cov(C)).
1 (s,a) 9mz (s, a)l I 19 (8,a) - Qx(s, a)l + (Qx(s, am ( a)) s 2e'.
follows that for any & E (Cv(Ci),
(9tt (s, T (-|s) - (9me (s, Tx(ss)
= (T 97t (s, ax. (s, .)) S (Tx (-11)) (s), Ozg (8, 4T (8, )
< gxt (8, - 2o (s, ) )l || (
< 2é.
To bound term 1, we note that for any & CC)( के (-16) = =-1ss) and क, E (ov).C then
E Ey' [1ng (6', ()((ss)) - के (+1=))
7
1
γ E By
(0=; x. (-18") - के (11s1))
1
+-
Ey'ndy s (C.
(i.n (5' (-1s') =
1
Ey Adz a (Cov((C)
( (s', (-1s") - - के (1s5))
1 γ
1
E Bydd (Coo(())
(a (6/,.) (2.))),, -
क (-1s'))
+
Eg da s (CC))CC)
(Qx :), (-(16)) - (
γ
1
E dg ECov(Ce)
||u,, (6',-) (((6)))))==())(())))) - _ (16311
by Holder's inequality
1 7
Eg (C))
2
by lemma 11 and || (-1s") n (.1s)) Il $2
1 y
Eylnay s (CCoo
(Q) (-168/ - n
7
2c'
1 By Bo (ECov(C.) ()) ne(-1s'))
+
1-2
23

---

In summary, for any 1, for any h = ki...., .......,.-... h- associated with 1, and for any Cov(Ci),
4c' +
1
(s) Uxa (s) -
Eg Bedddars (Qu(s' -
Because of line 27 of algorithm 2, one can use induction to show that by the time Confident-NPG terminates, all the C₁ for {o..... L + 1} will be equal. Therefore, the cover of C, for all I E [0..... L+ 1} are also equal. Thus, it is sufficient to only consider Co at the end of the algorithm. Because of line of algorithm 80 Cov(Co). Putting everything together, the value difference can be bounded as follows,
R1-1-1
(U>(80) Usa (80)
Σ
Σ
(U=(50) Uara (80))
K
K
k41-1 1
4e'
K
k=k
k141
E Egrnd (CCoCC)) ((0 =x(-15/1))
K(1 - 7)
k=ki
4e'
1
K-1
(Qu(s' (,,6,,,),=((ss))) - mx(1s/))]
$
+
(s)
(so) (so)
1-7
K(1 7)
k=0
B Confident-NPG-CMDP
We include the proofs of lemmas that appear in prior works and supporting lemmas that are helpful proving the lemmas in the main section. The lemmas that appear in the main section will have the same numbering here.
B.1 The accuracy of least-square estimates
Once a state-action pair is added to core set, remains in that core set for the duration of the algorithm. This means that any C, for E L L extended during a running phase & = the least-square estimates will need be updated based on the newly extended C, which contains newly discovered features. However, the policy is update only for states that are newly covered by the extended core set Ct using the newly improved estimates. Note that after line 30 of algorithm is run, the next phase's core set C1+1 will be set to C₁, which means that any state that was once newly covered by C₁ is no longer considered newly covered. Consequently, the policy for those states will remain unchanged throughout the rest of the algorithm's execution.
1} can grow in size. When a core set C is
We introduce hypothetical Q and Q reflect the value of Q used in the update of Th+ for k kt..... k - 1 associated with running phase e é At initialization, (7 a) = 0, (s, a) = for all == 0, K, E S and a E A. The values are specified in the following cases when line 27
is run:
(x,,)
if s Cov(C(+1)
()) -
as)
s E Cov(Ci) \\ Cov(C(+1)
initial value 0
if s & Cov(Ci),
(5(s.a) (s
if Cov(C(+1)
()( -
s E Cov(Ci) \ Cov(CI41)
initial value 0 if & Cov(Ci),
where (i(s, a). ( a) are the least-square estimates using the most recently extended C₁ that time. The dual variable A is defined line 29. Therefore, the @ a) used in the update policy at line 27 can be written as Q (s, a) = truncio. ا (x a) + Da trunc Q2(
24

---

Lemma 1 Whenever LSE subroutine in line 21 of ConfidentNPGG-NNe is executed during rumning phase & = for I E (O....,.I L.. the least-square estimate (s, a) satisfies the following condition for all iterations K ke...., ke+1 associated with this phase and for all s E Cov(Ci) and a E A.
[R(s,a) Pe (8, for all mly. ET CoviCC)))
where é' (1+U)( + VaB + (w (e)+ d) with d = (dd) and U is an upper bound on the optimal Lagrange multiplier. Similarly, for initial state 80, we have
(V((s)) -5 (5o)] S w VaB + (w (wv for all Thp E Cov(Ce)
Proof: By using the primal- approach, we have reduced the CMDP problem to an unconstrained problem with a single reward of the form ry = + Ac.
Because of line 7 have executed before entering the loop and line 30 have been executed in the previous phase E f= 1--1 1, the initial state 8o CCv((C). If so is in Cov(Ce) for the first time (i.e. s0 E Cov(Cc) Cov(Ce+1) ), then the dual variable Ås makes a mirror descent update in line 29 using (so) that time. After line 30 is executed, the core set for the next phase Ce+1 C.. This means that any states, including so. that are covered by C₁ are then covered by Ce+1. By lemma 6, the initial state Su will continue to be covered by C4+1 for the remainder of the algorithm's execution. This implies that the dual variable A referenced in this lemma remains fixed at the value set when so covered by Cg for the first time and does not change thereafter for the duration of the algorithm's execution.
Then the proof of this lemma follows similar logic lemma 11 in the single reward setting. The result of lemma 11 uses lemma 5. For lemma 5 to hold, lemma 9 is used to verify the conditions sufficient for lemma 5 hold. For lemma to hold, one of the requirement that the behaviour policy The and the target policy must satisfy eq. (9). In the following paragraphs, we show that eq. (9) indeed hold with appropriate changes the parameters of interest. Then it follows that lemma holds and consequently lemma 5 holds. Once all the sufficient conditions hold, by following similar logic as in lemma I, we have the proof.
Since the policies are updated with respect to Q2 instead of Q of the single-reward setting, need to make adjustment to n7. H, m, K to ensure Tx, and Tu indeed satisfy eq. (9). First, note the value Q for k = 0, ... K are the range of 0 and 1+U The upper bound value is the result of the primary reward function taking values in the range of [0, 1] and the dual variable taking values in the range of [o, UJ. The value U is defined in lemma 13 for gelaxed-feasibilite and in lemma 15 for strici-feasibility, and it is an upper bound on the optimal dual variable (i.e., X & U). By similar argument to lemma 8,
we make the following changes to 1/, H, m. K. We set the step size 171
1+0 V
(l)(
K the total
number of iterations K- (ml/mm(()))))) (1-7)a2²
and H In((s0V /(++))/ Po) Then,
1-7
follows that m (1+U))n(in Im(Lpp)
2HE(1-7)²
Next, from lemma 7, we have each (8, a) and (s, is an unbiased estimate of E H-1 7h Rn+1] and E (Ei-) CC respectively for all mh E [ Let
2n 2n())²
8' = 2exp
mg) By lemma 9, with probability 8', we have for any (s, a) E EC,
(s,5 a) d/4 SSe, (s. - -
Se Se
for all o II
Then the conditions of lemma 5 hold, and by similar argument to lemma Il using lemma 5, we have for each (s, a) E Cov(Ci).
(K[s, a) of (s, a)) S w JaB + (w v (Ki(s, of (s) Sw+ VaB (w++)
25

---

for all & CovC))) Then it follows that for given Ap=
(s) L (s, = ((Q((s tūg (s) 7e( (s,
for all o CoviCe))(CC)
Finally, since 80 E Cov(Cr) and (x0) = (1)0) Qi )),, therefore (v] - u (s0)
(<Tg()))0) (5( o (50, )> S w + vaB + (w + <) V for all T E Cov((C))
C Reasiiiyyy
Lemma 13 [Lemma 4.1 of Jain et al. (2022)] Let X be the optimal dual variable that satisfies miRA20 max, (p) + ((e b). If we choose
U 2
<(1 7)
then X² S U.
Proof: Let (p) arg max of (p), and recall that <= of (p) b 0. then
b (p)
maxmin (p) + (p)((p) b)-
X20
By Altman (2021),
(p) min max (p) ((e b) X20 "
max xf + (v) b)
2 o/ (p) + (11=;(1) b)
2 v/ (p) +NG.
After rearranging terms, we have
5 x (p) uxat (p)
1 2 [(1 7)
By choosing U = {(1-g). we have X* < U.
Definition 2
K-1
(
Σ
Egend, (so) (TT((11s)) - ma((ss), x=
k=0
K-1
RC(A, K) Σ (Ax - ()(V -))
Lemma Let 8 E (0, 1] be the failure probability, e > be the target accuracy, and so be the initial state. Assuming for all s E Cov(Co) and all a E A. ()(s,a) - -,,,,, a)l s é' and
(VE( - (2 (so)) S w /oB + (w + e)v d for all n.. E TTx then, with probability Confident-NPG-CMDP returns a mixture policy H that satisfies the following,
(80) - 2x (80) 5 1-7 + (V2In((A]) + 10(++))
5c
(1-7)
5E'
(v2lm([AA) + 1)(++0)
b - uf (90) < [b vr (so))+ 5 (1- (1- -x) xx)
(1 (1-2) (U-
where e' = (1 (w (VaB + (wo + e) d)) with d Ō(d).
26

---

Proof: For the following result, we consider a E {o...... }} with its corresponding I E { At the time of termination. all C₁ are equal.
To obtain a bound on the suboptimality and the constraint violation, we apply lemma 12 with π = n of CMDP, 0% = 0% + 2 instead of Qs. and lemma instead of lemma 11 of the single reward setting. Then, we have
u x" Ak
(80) - o (5
(18)
k=0
$
46'
+
1
K- 1
((Z(('))) + [(((())))) Bx (50) (ECov()))
Ta (-1s'))
1 Y
K(1 7)
k=
4e'
(K)
1 1-9 +
K(1 -7)
By Proposition 28.6 of Lattimore and Szepesvári (2020), the primal regret RR(T", K) I 22K In(AA]] with mn = 1=0 2l)(LA)) Expanding eq. (18) in terms of v", of, we have I-y
14
K
K 1
T (50) - (s0) -
Σ
du (5) - -f (50))
K
K
k=0
k=
4e'
1 U
2In((AA)
+ (1 11-7)) 7)2
(19)
1 y
K
Furthermore, by lemma 1, we have (2%(s, a) - gz. (s, S w vaB + (w + e)vVd d for any E Cov(Cr). Recall (/0(s)) (=x)) Qi (8. }), then it follows that Ae (80) Vi((s) S (As( (so) - Vi((s))) < U(w + VaB + (w v)vo) se.
1 K-1
1
Ae (80) -s0()))) s
Σ
de (k (80) - b)
K
K
k=0
h=0
K-1
Σ
da Me (80) V=(())) + do >x (8) -b) b)
K
k=
(O, K)
S c +
K
Sé' + (1 11>)
The update to the dual variable is mirror descent algorithm. By Proposition 28.6 of Lattimore and Szepesvári (2020), the dual regret (d, K) E UVK with 1/2
0((1 (7(12)) Altogether,
I-7
/K
K-1
Σ -
(su)
1r (so) < 4
+ (1 21- V
1 U
(In((A))
+ U
K
1 -- 7
K
(1 (1-7)vR K
k=0
5c'
(V21n((AA) + 1)(1 + U)
< Y-7 +
(1 (1-7)²VK
27

---

For bounding the constraint violations, we first incorporate (A, K) into eq. (19) and rearrange terms obtain:
K
U- (so) v. (50)
Σ
(b u (so))
K
K-1
(Ak - (>=-\)(0 (80) b) + 1 1-7 + (1+U)) 22
4t'
<
K
(1-1)8V
K=
1 K-1
K-1
Σ
(At: -N)c (5)) (50)) +
1
Σ(E (Ax 2)(V(((0) bb)
K k=0
K
km0
4c'
+ (1+ U) (-+U)22nmm (1)((AA)
+ 1 1-7 7
(1-7)VKK
Rd (2,
+ 1-7 + (1+U)/2m((A)
4c'
é' +
K
(1-7)3VK
< 56'
+ (1 (1+0) In( Al) +1)
(1 (1-7)2VK
There are two constraint cases. Case one no violation: b- uxx xx (50) S Then, it also holds
that b- A xx (so) S for any A 0, which is what we want show. Case two is violation:
b ux (so) > O, for which case, À= U. Using notation [x] max xr 0}, we have
K-1
1
U
Σ
o (50)
oT (su) +
Σ b 0 (su)
K
K
5c
(1 UU{ 2 11 (AA
+ +1)
1 1-7
(1 V)
By Lemma B.2 of Jain et al. (2022), we have
5c
(v2In([AA)+ + +1(1++0) +U) (U-vV(-XXVV
[ of (so)l+ S (1 (1- - x²) +
Theorem
With probability - 8, the mixure policy á returned by confuden-NPG-CCMP ensures
that
"r (so) U/xx (80) 5(1 + (1 + Vd)
c,
(20)
1-7
5(1 (1(+U)(1 + VT)
" (80) 2 b
w +
(21)
(1 (1-7)
30 (1
&dd [dd(I++1) a (1=
K 6'(22 Al) + (1-
we choose
In
11-11-7)
11 (1-78*
1-7 2lm([Al)
(11-)) H (a(3oV/((+u))// VK
m (1+0) (1+U) Im(1+po)) and
m
1+0 2 <(
1/2
2+H(1-9)²
U
Furthermore, the algorithm utilizes most Ö(d(1 + U) 7)-8) queries in the local-access setting.
Proof: From lemma 2, we have
5e'
+ (22In((AA) + 1)(1+0))
"r (s0) - of (50) 5
(22)
(1 - 7)
(1 7)2K
5c
+ ( (V2In((A)) ()(1+00))) U)
b - vf (90) 5
(23)
(1 () -x+)
(1 (1-7) (U (U-)))(U->>vVV
28

---

Let C' 1 for a E (0, |- By lemma 13, we chose U = 2C' and X S C. It follows that {(1-))
U-X S C = 5(1 - 7) S 1, and thus the right hand side of eq. (23) is upper bounded by the right hand side of eq. (22). Recall e' (1 + (w + (VaB + (w + e) d Then, the goal is to set the parameters H, n, K, and a appropriately so that the A, B and C of the following expression, when added together, is less than
5(1 + U) + Vdw (1+U)Ve +
5(1 + U)
+ (V2In([A)) + 1)) +U) (1 - 1-2)
(24)
1-7
1-7
First, we set appropriately so that the failure probability is well controlled. The failure probability depends on the number times Gather-date subroutine (algorithm 3) is executed. Gather-data is run for phase O,..., L. Each phase has at most d elements, and recall d defined in lemma 10. Therefore, Gather-data would return success at most d times. Altogether, Gather-data can return success at most di[. + 1) times, each with probability of at least 1 = - 5/ 5/(d(L 1)). By union bound, Gather-data returns success in all occasions with probability - 6.
In( (ul(so//
and 30 p In ( we have for "1-1--)"
By setting
any 1 E (0, (0.-.., L). k h411 1, the 1% Lz. (8,
(1-7)e and [
6(14UVd
C. (s, a)l S (1-T)e
5(1+0)/d hold for all & E II, Cov(CC) with probability at least - 6. Then, this is used in the accuracy guarantee of the least-square estimate (lemma 1) and finally in the suboptimality bound of lemma
(1-2)² 31+01 Finally, by setting
Then, we can of eq. (24) to be equal to and solve for a
K 62 (2 we have of eq. (24) be less than & Altogether, we have the reward (1-2)*2"
suboptimality satisfying eq. (20) and constraint satisfying eq. (21).
For the query complexity, we note that our algorithm does not query the simulator in every iteration, but at fixed intervals, which we call phases. Each phase is m iterations in length. There are total of = [K[[m] + 1)] < K/m = ((1 + () - =11) phases. In each phases, Gather-data subroutine (algorithm 3) can be run. Each time Gather-data returns success with trajectories, the subroutine would have made at most nH queries. Gather-data is run for each of the elements in G, I E {O......) L). By the time the algorithm terminates, all Ci's 's are the same. Since there at most (dd) elements in each Ci the algorithm will make total of nH 1)|Col number of queries to the simulator. Since we have H Ō((1 ")), = Ō((1 U) (11 (11-))-9) and (( U -)),, the sample complexity is
- -
D Strict-feasibility
Lemma 14 Let TT be defined as in eq. (7) and x² be an optimal policy of CMDP. Then, for a A > 0,
0ff (50) - vr=g (so) A'A,
where X" is an optimal dual variable that satisfies minAzo max, (80) ((v V/).
Proof:
0/ (5v) max min oi (5o) ((vE(s)) - b').
A
29

---

By Altman (2021),
04 (50)
min e + (()) b¹)
X20
max (50) (x0)
- -b)
2 U/ (00) + + (v. (v)) - (b+
2 (5o) (b 4) because o (50) 2 b
- (so) A
After rearranging the terms, we get the result.
Lemma 15 Let X be the optimal dual variable that satisfies minx2o max; V (VV())) If we choose
5(1 7)
then X & requiring that A (0, ().
Proof: Let Tī (8o) = arg max (sp). and recall that Ç = V2 (50) 0, then
0 (5o) = max min (so) + {(v - 5')
# A20
By Altman (2021),
2 (80)
min max of (50) + X(r - V9 A20
max of (80) + (VV(V((())) - -b)
o (50) + x ( (50) (b+ + 4))
2 (s)) + 1- - A).
If we require A (0, )), then we have
0 (50) 2 vー= (so) + +5 5
= = (50) + X7
(25)
2
After rearranging terms in eq. (25), we have
2 20072 (80) - v/ (80))
2 {(1 7)
By choosing U = {(1ーン)' X" U.
Theorem With probability 1 8, a target > 0, the mixture policy it K returned by confident-
NPG-CMDP ensures that v=- (so) u (s0) I and v (50) 2 b, if assuming the misspeci-
A(1-)) and if we choose A xl--b T0 K
A²(1->)²
ficiation error 70(1+))(+V5)
14 (22n(((A)++1)((( n 3" ( H
41
(1- U ((--)
21
m
(n(U) 2AH(1-1)
Furthermore, the algorithm utilizes at most access setting.
queries in the local-
Proof: Let X be the optimal dual variable that satisfies the Lagrangian primal-dual of the surrogate CMDP defined by eq. (7) (i.e., X arg min max, vi (su) + ((f((s)) - B/)).
ef (so) 2/= (so) o (so) v (o0)
+
w (sn) w (50)
surrogate saboptinality
ComlidentNPG-CMMe suhoptimality
< A
30

---

where ē ((++U)(++Va) 5(1+U)vBB 50+U)/Vd ( By lemma 14, 1-7
1-7
1-y
(1~>)2 /
- (50) 2 (so) S A.
We can further upper bound X by U <(- using lemma 15 and
requiring E (0 f). Together with theorem 1, we have Contiden--PG-CMDD return F s.t.
4A +ē and
of (50) xxxx (50) - 5(1 5(1- 7)
(26)
8' V (8o) SE.
Now, we need to set A such that 1 A E (0.5) and 2) A - 2 0 are satisfied. If we choose
A <(1=))s then the first condition is satisfied. This is because E 0, and thus A s $ < $.
Next, we check if our choice of A كادللا satisfies A 2 For the condition A 8
to be true, we make an assumption on the misspecificcttion error 70(++U)++V and pick
A(17)
n, Ot, K, m,, 12, H, m to be the values outlined in this theorem. Consequently, we have I.A Then, we have ensured the condition A - 2 is satisfied.
We note that because Ç 1.)) we have ē I - (so) - ux (so) S and b' Vax (so) I feasilbility is achieved.
following from eq. (26), we have Then it follows that + + S Vix (so). Strict-
S
16
A
For the query complexity, we note that our algorithm does not query the simulator in every iteration, but at fixed intervals, which we call phases. Each phase is m iterations in length. There are total of
= K/(Lm) | + 1)] < K/m = Ô ((1 (11+ U) - -) (-)-))--111 -A-1) phases. each phase, Gather-date subroutine (algorithm 3) can be run. Each time Gather-data subroutine returns with trajectories, the subroutine would have made at most nH queries. Gather-data is run for each of the element in C., I E (0,.... I.). By the time the algorithm terminates, all Ci's are the same. Since there most (dd elements in each C,, the algorithm will make total of nH (L + 1)/Col number of queries to the simulator. Since we have Ó(1 - >) -0- )) n Ó(( + U)2d(1 (0 -3). L L -=Ō 1( (0((1-)--A-11 and A <((1->) the sample complexity is ((d 8
- c 35
E A discussion on memory cost and some implementation details
By recording the states added to each core set during extensions and their corresponding least-squares reconstruct the policy as needed. This section explains how to track this information and how it facilitates policy reconstruction.
weights,
In phase I, the policies n& for iterations k = Ri + 1..... k441 1 depend on the core set Cj- Since Ct can be extended multiple times, these policies may change accordingly. However, we do not want to change the action distribution for states have already passed the uncertainty test in previous extensions (i.e. 8 E Cov(Cr+1)). For such states, action distributions are based on the least-square estimation of the core set at that time they passed the uncertainty test for the first time (i.c.. s e Cov(C)) \ Cov(C++1)). Therefore, it is essential to track newly added states in each extension and store their corresponding least-square weights to recompute their action distributions.
To achieve this, Co is extended only via line and line 15 of algorithm 1, while other core sets C₁, where 1 E {1..... L + }} are extended solely via line 30 during the running phase f = 1 1. We mark newly added elements in line 7, line 15, and line 30. After executing line 21, we store the least-square weights associated with these newly added state-action pairs
By keeping track of the state-action pairs that are newly added in each extension and saving the corresponding least-square weights, we can construct the policy T associated with C, Let C = 0. and Cj denote all state-action pairs added to C, in extension for 1 up to most d. Let w represent the least-square weight computed using C₁ C? ucl UC? u... UC for the k-th iteration. When C, is extended for the (i 1)-th time, let C be the set of newly added state-action pairs,
31

---

++ is then computed using making the latest C, u....c. The least-squares weight W
G. When line of algorithm is executed, T remains unchanged for the of the algorithm''s execution for any states already in Cov(C) UC, U. ... U CJ), equivalent to Cov(CI+1) 1) in line 27, because line 30 would have been executed in the i-th extension, making C++1 = = U. U... U. For states in Cov(C) UCJ U... ).t+. \ Cov(CP UC! U... .C() (equivalent to Cov(Cr) (C+(()+
in line 27), T makes softmax update using w i+1 remains as Ti.
For all other states not in Cov(Ci), the policy
A subroutine can start with No. use the stored data to compute and return ( for any s and k. By tracking newly added elements and the corresponding least-square weights, the algorithm can reconstruct policies no. kK- This approach enables the algorithm to return the value of a mixture policy termination.
32

---

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: Reviewers may find results from section 4 leading to the main results stated in section and section 6.
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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails 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 address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged 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.
the paper. The authors should use their best
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]
33

---

The assumptions are listed in every lemma and theorems. In the supplementary section, all supporting lemmas will be proven or cited. All the lemmas are presented in sequence leading up to the two main theorems.
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 referenced in the statement of any theorems.
The proof' can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper does not include experiment
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way 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 large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
34

---

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 experiment
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
Beglliicguides//oeeSuabaaa ssiillllicssos for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
wttps.cc/ppblccc//eccccccpcppppp gewic//guuee...eee CoodeSummii agionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiment
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 provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiment
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.)
35

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiment
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics attps://neurs httpp//ccccpppcccccccccooeeeeeee
Answer: [Yes]
Justification: have read the ethics guidelines.
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 circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: By understanding the sample complexity CMDP, a framework used by many of the safe reinforcement learning research, we can design more efficient algorithms. This potentially has broader positive impact for real world applications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
36

---

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

---

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


Reviews:
[{"review_id": "C6ZEKpr9H1", "reviewer": "Reviewer_ynfZ", "summary": "**Problem setup**\n\nThe authors consider the task of global planning in large Constrained \nDiscounted MDPs. They assume local access to a simulator which can be queried at previously \nencountered state-action pairs to obtain a next state sample and immediate \nreward, and that the $Q$-value of any policy is linearly realizable by a given feature map. Under this more general assumption on the MDP, they aim to develop an efficient method which learns a policy that maximizes return with minimal constraint violations.\n\n**Approach**\n\nIn the above context, the authors propose a primal-dual approach to solve a constrained \nreturn optimization problem. Under the weaker assumption of $Q^{\\pi}$-realizability and local access to a simulator, their method combines existing techniques on $Q$-value estimation in large MDPs and off-policy evaluation to nicely approximate the gradients of the primal-dual objective while conserving samples. Precisely, they apply the $Q$-values estimation sub-routine of CAPI-QPI-PLAN in [1] to construct least squares estimates which are guaranteed to closely approximate the true value at a subset of important (namely \\emph{core}) state-action pairs. Furthermore, contrary to the fully on-policy evaluation routine of CAPI-QPI-PLAN, their method Confident-NPG-CMDP reuses the core set and trajectory data for value estimation and policy improvement across a number of steps in each learning phase.\n\n**Result**\n\nThe authors derive performance guarantees for their method in terms of the value error and constraint violation of the output mixture policy. Precisely, they prove that w.h.p their method learns a near-optimal policy with minimal constraint violation with at most $\\mathcal{O}(poly(d)\\varepsilon^{-3})$ queries to the simulator and iterations. \n\n\n\n[1] Weisz, G., György, A., Kozuno, T., & Szepesvári, C. (2022). Confident Approximate Policy Iteration for Efficient Local Planning in $ q^\\pi $-realizable MDPs. Advances in Neural Information Processing Systems, 35, 25547-25559.\n\n\n**Update**: I also updated my score for contribution.", "questions": "1. The nature of the output policy in Line 268 is a bit ambiguous and I spent a considerable amount of time trying to understand the meaning of the notation $\\frac{1}{K}\\sum_{k=0}^{K-1}\\pi_{k}$ means.\n\n    On one hand, the authors refer to the said notation as a mixture policy, which to my knowledge means that at deployment, the agent flips a coin at the beginning of each episode to decide which of the $K$ policies to use. In this case, it is unclear how you define $v_{\\overline{\\pi}\\_{K}}$, and more importantly, such policies are not suitable for constrained MDPs, especially with safety constraints as they are only required to perform well on average.\n\n    On the other hand, the notation seems to mean that $\\overline{\\pi}\\_{K}$ is an element-wise average for all state-action pairs. In this case, the policy is stochastic and $v_{\\overline{\\pi}\\_{K}}$ well defined.\n\n2. The complexity guarantees has worse dependence on the effective horizon $(1-\\gamma)$ e.g. $(1-\\gamma)^{-11}$ in Theorem 1 and $(1-\\gamma)^{-14}$  in Theorem 2. Is this a consequence of the method or an artefact of the analysis? Can this be improved?\n\n3. In Remark 3, the authors mention that the Slater's constant, which is required by their algorithm, can be approximated by another algorithm. Is this approximation trivial? How will the approximation error influence the current results?\n\n4. In appendix A, the authors provide Confident-NPG, a version of \nConfident-NPG-CMDP for the single-reward (or unconstrained MDP) case. \nFurthermore, their performance guarantees for the latter algorithm appear to be \nbased on first relating the former to CAPI-QPI-PLAN. Therefore, to \nbetter understand the contributions of this paper in the constrained case, the following questions are based on Confident-NPG. Can the authors kindly clarify the following:\n\n    - Why is $c > 0$ interesting to study?\n\n    - What is a suitable choice of $c$ and how does tuning this parameter show up in the performance guarantees?\n\n    - Can the authors comment on the memory requirement of Confident-NPG?", "limitations": "This is a purely theory paper so there are no direct \nsocietal impacts. However, I would recommend that the authors highlight the  \ndependence on the effective horizon in their discussion. More \nimportantly, I recommend that the authors elaborate on the memory and \ncomputational complexity as these contribute to the efficiency of their method.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper addresses the task of planning in large Constrained Discounted MDPs under the weakest possible assumptions in the RL literature. This is achieved with a unique combination of existing techniques. Their value estimation scheme makes use of techniques from CAPI-QPI-PLAN to create a core set in addition to off-policy evaluation via importance sampling for value estimation at core state-action pairs. The authors also adequately cite related works.\n\n2. The submission is well written and, to the best of my knowledge, technically sound.\n\n3. In terms of the target accuracy and feature dimension, the results are significant especially in restrictive the setting of approximate policy completeness and local access to the simulator that they consider.", "weaknesses": "1. The relevance and impact on the theoretical analysis of the off-policy evaluation scheme is not fully accessible. It would help if the authors could clarify (with pointers in the main text), how this routine helps conserve samples in theory. Precisely, does the sample complexity get worse if the authors simply apply CAPI-QPI-PLAN?\n\n2. In Line 268, it should be $\\frac{1}{K}$ not $\\frac{1}{k}$ in the definition of $\\overline{\\pi}_{K}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "You are correct that the mixture policy randomly selects an index $I \\in {0, \\ldots, K-1}$ with probability $1/K$ at deployment and then follows the policy $\\pi_I$ for all subsequent steps. The value function of the mixture policy, $v_{\\bar \\pi_K}(s)$, is defined as the expected return when the mixture policy is initiated in state $s$: $v_{\\bar \\pi_K}(s) = \\sum_{i=0}^{K-1} \\text{Prob}(I = i) v_{\\pi_i}(s) = \\frac{1}{K} \\sum_{i=0}^{K-1} v_{\\pi_i}(s)$.  This averaging of the value functions is used in our analysis to demonstrate that the returned mixture policy achieves the two feasibility objectives stated in sections 5 and 6.\n\nIt's important to note that the mixture policy is a history-dependent policy. The notation $\\frac{1}{K}\\sum_{k=0}^{K-1} \\pi_k$ is defined with respect to trajectories. Specifically, this means that the probability of a trajectory is the weighted average of the probabilities of that trajectory under each of the component policies. We will also clarify this in the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DedcPJlxxF", "reviewer": "Reviewer_EJjQ", "summary": "This paper studied constrained Markov decision processes (CMDP) and proposed a confident policy gradient algorithm for $q_\\pi$ realizable MDPs. Here, a $q_\\pi$ realizable MDP assumes that the Q function can be approximated by a linear function w.r.t. some feature of state-action pairs. By using primal-dual methods, the proposed algorithm can find an $\\epsilon$-optimal policy satisfying the constraint or with small constraint violation. The proposed approach can also be applied to the misspecification case.", "questions": "Please see the weaknesses part.", "limitations": "No further limitations need to be addressed.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper is technically sound.\n2. The studied problem is important and well-motivated.", "weaknesses": "1. The major weakness is the presentation of contribution. According to the paper's presentation, it feels like the proposed method is a straightforward extension of Weisz et al., 2022 applying to the Lagrangian objective function. It would be better to highlight the difficulties of handling CMDP or this Lagrangian function.\n\n2. The presentation of the two learning goals is also confusing. In my understanding, the proposed algorithm can already achieve the stringent constraint, i.e. zero violation, and the relaxed feasibility is satisfied naturally. It seems redundant to spend a whole section to describe the result of relaxed feasibility. Some papers split the two results (Liu et al., 2021) because they need different assumptions. Perhaps the authors can explain or organize the presentation more clear.\n\n3. Another presentation issue: There is no introduction or justification of the terminology *natural policy gradient* in this paper. \n\n[1]. Weisz et al., Confident Approximate Policy Iteration for Efficient Local Planning in $q_\\pi$-realizable MDPs, 2022.\n\n[2]. Liu et al., Learning policies with zero or bounded constraint violation for constrained mdps, 2021", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please note that our algorithm is NOT a straightforward extension of CAPI-QPI-Plan. Moreover, our paper distinguishes between the relaxed-feasibility and strict-feasibility problem settings. Treating each setting uniquely is a key strength of our work. In the relaxed-feasibility problem, the returned policy $\\bar \\pi_K$ is allowed to have some constraint violations, specifically where $v_{\\bar \\pi_K}^c(s_0) \\geq b - \\epsilon$. This contrasts with the strict-feasibility setting, where no constraint violations are permitted, meaning $v_{\\bar \\pi_K}^c(s_0) \\geq b$. To address the strict-feasibility problem, the algorithm must solve a more conservative CMDP, as discussed in Section 6 of our paper. However, solving this more conservative CMDP incurs a higher sample complexity cost, necessitating that the relaxed-feasibility setting be treated separately. Additionally, in the presence of a misspecification error $\\omega > 0$, the strict-feasibility setting requires additional assumptions on $\\omega$, whereas the relaxed-feasibility setting does not. The sample complexity of the relaxed-feasibility setting can be independent of Slater's constant, whereas for strict feasibility, the returned policy must strictly adhere to constraints, and we cannot simply set Slater's constant $\\zeta$ to $\\epsilon$ and disregard its impact.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VhBJIDdhOm", "reviewer": "Reviewer_KqmD", "summary": "This is the first work which addresses and achieves polynomial sample complexity for the learning problem of CMDPs in the more general setting of linear function approximation with $q_{\\pi}$ realizability.  The authors propose a primal-dual algorithm and utilize a local access model (can be viewed to in between online learning and a generative model ). The algorithm reliably produces a policy that strictly adheres to the constraints while closely optimizing the reward function's value.", "questions": "- Since the paper claims that $q_{\\pi}$ realizability is more general than the linear MDP setting, does it mean that linear MDP setting implies $q_{\\pi}$ realizability ? Is this result known or trivial ? Could this point be included in the paper?\n\n- The paper seems an extension of earlier work i.e., (Weisz et al., 2022). Can the authors elaborate on what were the main technical challenges overcome on extending this work to the CMDP setting ?", "limitations": "There are no potential negative societal impact of their work", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is mostly well written with good summarization of the main ideas and theorem statements.\n- It is the first work achieving polynomial sample complexity for CMDPs in the more general $q_{\\pi}$ realizability setting.", "weaknesses": "- Lack of experimental results.\n-  The paper seems an extension of earlier work i.e., (Weisz et al., 2022). \n- Despite general good writing, the main algorithm description in section 4.2-4.3 is very dense and difficult to parse.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Yes, you are correct that linear MDP implies $q_\\pi$ realizability.  However, $q_\\pi$ realizability DOES NOT imply linear MDP, and one can show this via a counterexample.  To name a few references that discuss this, please refer to Proposition 4 of Andrea Zanette et al., Learning near optimal policies with low inherent Bellman error, 2020a. (https://arxiv.org/pdf/2003.00153) and Hao, B et al., Confident least square value iteration with local access to a simulator (2022) (https://proceedings.mlr.press/v151/hao22a/hao22a.pdf).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to begin by thanking all the reviewers for their time and dedication in evaluating our work. We start our rebuttal by emphasizing that our algorithm is not a straightforward extension of the work by Weisz et al. (2022).


First, we want to point out that the algorithm CAPI-QPI-Plan by Weisz et al. (2022) is designed for the unconstrained MDP setting, where it returns a deterministic policy. However, in the constrained MDP setting, an optimal deterministic policy for the unconstrained MDP may not be feasible. Thus, CAPI-QPI-Plan is not applicable to the constrained MDP setting.  In contrast, our algorithm, Confident-NPG-CMDP, returns a soft mixture policy $\bar \pi_{K}$, ensuring that $\bar \pi_K(a | s) > 0$ for all $(s, a) \in \mathcal{S} \times \mathcal{A}$. The soft policy returned by Confident-NPG-CMDP can solve the relaxed-feasibility problem in section 5 and the strict-feasibility problem in section 6.


The main algorithmic differences between Confident-NPG-CMDP and CAPI-QPI-Plan are as follows:
1) Data Sampling: Confident-NPG-CMDP does not sample data in every iteration, unlike CAPI-QPI-Plan.
2) Dual Variable Computation: Confident-NPG-CMDP requires computing the dual variable present in a primal-dual algorithm.
3) Policy Improvement Step: Confident-NPG-CMDP utilizes a softmax over the estimated action-values, whereas CAPI-QPI-Plan is greedy with respect to the estimated action-values.


These are critical changes to ensure a feasible mixture policy for the CMDP. Moreover, it also makes the analysis considerably more challenging.


We will now explain the motivation behind the changes to the policy improvement step and why we do not sample data in every iteration.  In the constrained MDP setting using a primal-dual approach, it is also crucial to control the dual variable. The dual variable is obtained using a mirror descent algorithm, introducing an additional $\epsilon^{-2}$ factor to the sample complexity. Simply applying CAPI-QPI-Plan and returning a mixture policy at the end would yield an overall sample complexity $\propto \epsilon^{-4}$, with the additional $\epsilon^{-2}$ factor arising from controlling the dual variable in addition to having to control for the estimation error. This complexity led us to adopt the natural policy gradient approach.


By using the natural policy gradient as a policy improvement step instead of CAPI-QPI-Plan's greedy policy improvement step, Confident-NPG-CMDP reduces the sample complexity from $\tilde O(\epsilon^{-4})$ to $\tilde O(\epsilon^{-3})$. This reduction is achieved by leveraging the softmax policy structure within the natural policy gradient, enabling effective use of off-policy estimation to conserve data. By employing a per-trajectory importance sampling ratio, we can weigh the Monte Carlo returns generated from data collected in an earlier on-policy phase, resulting in unbiased estimates of action values with respect to the target policy. However, this ratio can become large if there is a substantial difference between the on-policy and target policy. To address this, the algorithm collects data at intervals of $m$, effectively determining when to collect new data as the policy significantly diverges from the earlier on-policy data. By setting $c > 0$, we can bound the per-trajectory importance sampling ratio, thus controlling the interval $m = O(\ln(1+c) \text{poly}(\epsilon^{-1} (1-\gamma)^{-1}))$ for resampling on-policy data to produce well-controlled estimators.

Meta-review: The paper proposes a new algorithm to solve constrained MDPs in the online infinite horizon setting under the q^pi-realizable and local access assumptions. There is general consensus among the reviewers of the interest of the results. Nonetheless, there was a concern about the technical novelty, since the algorithmic structure and the theoretical analysis heavily rely on existing results, in particular from the CMDP literature and on recent works such as CAPI-QPI-Plan. The authors have addressed these concerns in the rebuttal and explained how a direct application of CAPI-QPI-Plan would result in worse complexity and which ingredients of Confident-NPG-CMDP are key to achieve the desired results. Based on this, I believe the paper is significant and novel enough for the theoretical community working on CMDP as it pushes forward the limits of how we can solve this challenging problem. Hence, I recommend acceptance.

I strongly encourage the authors to improve the current manuscript as follows:
* Include a thorough discussion on the algorithmic and theoretical differences between CAPI-QPI-Plan and Confident-NPG-CMDP. This would greatly help in understanding the novel contributions of the paper.
* Highlight the limitations of the current work, notably the dependency on the horizon.
* Add a more comprehensive comparison and discussion with results in the linear MDP case and explain how moving to less restrictive assumptions makes the problem more challenging.
* Include the clarifications provided during the rebuttal.
Decision: Accept (poster)