Provably Efficient Model-Free Constrained RL with Linear Function Approximation
Authors: Arnob Ghosh
Xingyu Zhou
Ness Shroff
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement Learning Theory
Theory of Constrained Reinforcement Learning
Linear MDP
Model-free RL
Soft-max

Abstract: We study the constrained reinforcement learning problem, in which an agent aims to maximize the expected cumulative reward subject to a constraint on the expected total value of a utility function.  In contrast to existing model-based approaches or model-free methods accompanied with a `simulator’, we aim to develop the first \emph{model-free}, \emph{simulator-free} algorithm that achieves a sublinear regret and a sublinear constraint violation even in \emph{large-scale} systems. To this end, we consider the episodic constrained Markov decision processes with linear function approximation, where the transition dynamics and the reward function can be represented as a linear function of some known feature mapping. We show that $\tilde{\mathcal{O}}(\sqrt{d^3H^3T})$ regret and  $\tilde{\mathcal{O}}(\sqrt{d^3H^3T})$ constraint violation bounds can be achieved, where $d$ is the dimension of the feature mapping, $H$ is the length of the episode, and $T$ is the total number of steps. Our bounds are attained without explicitly estimating the unknown transition model or requiring a simulator, and they depend on the state space only through the dimension of the feature mapping. Hence our bounds hold even when the number of states goes to infinity. Our main results are achieved via novel adaptations of the standard LSVI-UCB algorithms. In particular, we first introduce primal-dual optimization into the LSVI-UCB algorithm to balance between regret and constraint violation. More importantly, we replace the standard greedy selection with respect to the state-action function with a soft-max policy. 
This turns out to be key in establishing uniform concentration (a critical step for provably efficient model-free exploration) for the constrained case via its approximation-smoothness trade-off. Finally, we also show that one can achieve an even zero constraint violation for large enough $T$ by trading the regret a little bit but still maintaining the same order with respect to $T$.

Provably Efficient Model-Free Constrained RL with Linear Function Approximation
Arnob Ghosh
Xingyu Zhou
Electrical and Computer Engineering
Electrical and Computer Engineering
The Ohio State University
Wayne State University
Columbus, OH, USA ghosh. 244@osu. edu
Detroit, MI, USA
xingyu who.gyy.zouuuaayne..o edu
Ness Shroff
Electrical and Computer Engineering
The Ohio State University
Columbus, OH, USA shroff. 110osu. edu
Abstract
We study the constrained reinforcement learning problem, in which an agent aims to maximize the expected cumulative reward subject to a constraint on the expected total value of utility function. In contrast to existing model-based approaches or model-free methods accompanied with a 'simulator', we aim to develop the first model-free, simulator-free algorithm that achieves a sublinear regret and a sublinear constraint violation even in large-scale systems. To this end, we consider the episodic constrained Markov decision processes with linear function approximation, where the transition dynamics and the reward function can be represented
linear function of some known feature mapping. We show that (VV H3T) regret and Ó (33 constraint violation bounds can be achieved, where d is the dimension of the feature mapping, H is the length of the episode, and T is the total number of steps. Our bounds are attained without explicitly estimating the unknown transition model or requiring simulator, and they depend on the state space only through the dimension of the feature mapping. Hence our bounds hold even when the number of states goes to infinity. Our main results achieved via novel adaptations of the standard LSVI-UCB algorithms. In particular, we first introduce primal-dual optimization into the LSVI-UCB algorithm to balance between regret and constraint violation. More importantly, we replace the standard greedy selection with respect the state-action function in LSVI-UCB with soft-max policy. This turns out to be key in establishing uniform concentration for the constrained case via its approximation-ssoonnie show that one can achieve an even zero constraint violation for large enough 7 by trading the regret little bit but still maintaining the same order with respect to T'.
trade-off. Finally, also
Introduction
In many practical applications of online reinforcement learning (RL) (e.g.. financial regulations, safety), there exist additional constraints on the learned policy in the sense that it also needs to ensure that the expected total utility (cost, resp.) exceeds given threshold (is below a threshold, resp.). Constrained RI. problem is formulated as constrained Markov Decision Process (CMDP), in which trade-off in online RL becomes more challenging due the
the celebrated exploration-exploiaatiii additional need to find balance between reward regret and constraint violations.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

trade-off To develop online sample-efficien algorithms for CMDPs, prior works have largely resorted to model-based approaches, where the control policy is constructed based on a learned model IT-7. However, due to the explicit estimation and storage of the unknown transition model, bosel- approaches often lead to large time and space complexities. These issues are exacerbated in the large state space. Hence, there are several recent works starting to investigate model-free algorithms for CMDPs, which directly update the value function or the policy without first estimating the model [8] [0]. However, all of these works consider an easier setting compared to standard RL in that they assume access to a simulator [T] (a.k.a. a generative model [2),, which is a strong oracle that allows the agent to query arbitrary state-action pairs and return the reward and the next state, hence greatly alleviating the intrinsic difficulty of exploration in RL. To the best of our knowledge, [3] were the first to study model-free and simulator-fre free algorithms for CMDPs. The above mentioned work on model-free algorithm considers the finite-state tabular setting and the regret scales polynomially with the number of states. Thus, the result would not be useful for large-scale RI. applications where the number of states could even be infinite. To address this curse of dimensionality, modern RL has adopted function approximation techniques to approximate the (action-) function of policy, which greatly expands the potential reach of RL, especially via deep neural networks. However, little is known for the performance guarantee of model-free algorithms in CMDPs beyond tabular settings, even in the case of linear function approximation. Motivated by this, we are interested in the following question:
Can we achieve provably sample-efficien and model-free exploration for CMDPs beyond tabular settings (without a simulator)?
Contribution. To answer the above question, we consider the episodic CMDPs with linear function approximation, where the transition dynamics and the reward function can be represented as a linear function of some known feature mapping. Our main contributions are as follows.
We show that with a proper parameter choice, our proposed algorithm achieves Ö(V de HTT) regret and O (3)) constraint violation bounds with high probability, where d is the dimension of the feature mapping, H is the length of the episode, and is the total number of steps. We also show that it is in fact possible to achieve zero constraint violation by trading the regret little bit while maintaining the same order with respect to T.
Our bounds are attained without explicitly estimating the unknown transition model or requiring simulator, and they depend on the state space only through the dimension of the feature mapping. To the best of knowledge, these sub-linear bounds are the first results for model-free. simulator- free online RL algorithms for CMDPs with function approximations. We even improve the bound (Ō(T0.8)) proposed in the model-free finite state tabular setting by [33 (Table
We combine the primal-dual algorithm with the classic model-free, simulator-Fi free LSVI-UCB algorithm [4] to balance between regret and constraint violations. This naturally leads to the construction of new composite Q-function for the reward and the Q-function for the utility weighted by the dual variable. Due to this new type of Q-function in CMDPs, a key challenge arises when establishing the value-aware uniform concentration, which lies the heart of the performance analysis of model-free exploration. More specifically, the standard greedy selection with respect to this composite Q-function fails in finding non-trivial covering number for the function class of individual value functions (i.e., V -function) for the reward and the utility respectively. To address this fundamental issue, we instead adopt soft-max policy by utilizing its nice property of aaproximatioon-smoonn via its parameter, i.e., temperature coefficient.
function (i.e., Q-function), which is the sum of the
1.1 Related Work
Model-based RL algorithms have been proposed for the CMDP 5 Apart from 77. the rest considered tabular set-up. In the tabular model-based set-up, the best known regret and constraint violations achieved are Ó( ((ViSPIAAT | where S] and [A| are the dimensions of the state and action spaces respectively. Hence, such results can not cope up with the large state space. 77] considered linear kernel MDP whereas we consider linear MDP. These two are not the same in general. We describe the differences with the algorithm proposed in 7 in Section 4.
Model-free RL. algorithms have also been proposed S 10 to solve CMDP. However, of the above require generator model, which simulates from any state and action. [13 proposed 'triple-Q'

---

Table 1: Regret and Constraint Violations Episodic MDP for algorithms which do not simulators. (LFA: Linear Function Approximation, MOD-FREE: Model-Free)
ALGORITHM
LFA?
MOD-FREE?
REGRET
VIOLATIONS
OPDOP
YES
x
O(VEHHT)
O(VPH'T) O(V SPAATT
OPT- PRIMALDUAL CMDP 'II
No
X
O(v
H SF
OPTDUAL-CMDP 'I
No
X
Oly ((VTSTTTTT) 0(1)
OPTPRESS-PRIMALDDE
6
NO
X
Ó(y H* (SSSSSTTTTT))
TRIPLE-Q [B
No
V
O(H*2T0 VSS(AA) O(V&HHT)
OUR APPROACH
YES
O(V
WE CAN REDUCE THE VIOLATION
FOR LARGE ENOUGH T (FINITE) WHILE MAINTAINING THE SAME
ORDER REGRET WITH RESPECT T (APPENDIX(H))
WE REPLACE & ( IN OUR PAPER) BY O(H) SIMILAR TO OUR PAPER AND A BY (S].
algorithm which does not require a 'simulator'. However, it only considered tabular setting. The regret bound shown in [13 is O which is far from the optimal for the model-based Ö(VT). Please Table to proposed a RL algorithm for the scenario where a constraint needs to be satisfied at each step of an episode. We consider constraint where the cumulative utility over the length of the episodes must exceed a threshold. Hence, the set of constraints is fundamentally different. The authors in [15] also assumed that safe-action is known for each state which we do not assume in setting.
contribution compared the state-of-the-ane approaches. [T5]
2 Problem Formulation
We consider an episodic constrained MDP, denoted by A is the action space, H is the fixed length of each episode, P = (P is collection of transition probability measures, a collection of utility functions. We assume that S is a measurable space with possibly infinite number of elements, A is finite action set. P, (-Ia,, a) is the transition probability kernel which denotes the probability to reach state when action is taken at state æ. Fh : S x A - [0, 1]. and Ih S A [0, 1] and are assumed to be deterministic. However, we readily extend to settings when T4 and Ih are random.
where the state space,
(ra /== is collection of reward functions, and 9 = {gr k
Each episode k [K] starts with the fixed state z1. It can be readily generalized to the setting where #1 drawn from a distribution. Then at each step / E [H] in episode k, the agent observes state 2f, E S. picks an action af E A, receives reward rh (z af). and a utility gn (# af)). The MDP evolves to of 1 that is drawn from IP, , (-12f,, (f) The episode terminates
1. step Without loss of generality. we assume that MH+1 9H+1 = O. In this paper, we consider the challenging scenario where the agent only observes the bandit information r' (a at) and gn (x), (x) the visited state-action pair (a a.). .. The policy-space of an agent is A(A|S, H): (--))-)) TA (-Ix) E (AA), VI E S, and h E [H] ). Here A(4) is the probability simplex over the action space.
For any o E S & E [K]. and E [H]. n (a ( denotes the probability that the action of e A is taken at episode A: when the state is x
Let V (xr) denote the expected value of the total reward function starting from step h and state
when the agent selects action using the policy क {m
(x) = Er Σ ra a:)lan = x
where E taken with respect to the policy π and the transition probability kernel P. Let Q (xx a) denote the expected value the total reward starting from step and the state-action pair (x, a) and follows the policy
(T, EE,
Σ
rl(2 az) x, as
(2)
h=h
3

---

9. (2), and the action-value function for the Similarly, we define the value function for the utility V
urility Q (x..). We denote VAA (x), and 27,1 (2, a) for j = g. Definition 1. For brevity, we denote PA J (z, a) Ez (-1za)) J (x") (or g.
Using this notation, the Bellman's 's equation associated with the policy π becomes (j, a) = + P. PN
(3)
Note that V. EaeA (a(a)z)QT. (1, (I)
(ma())2), 05, A) where (T,
The objective of the learning agent is to find an optimal solution of the following problem
maximize TEA(A(S,H) V (z1),
subject to ( 2 b.
(4)
Note that even though we have only once constraint, it can be readily generalized to the scenario with multiple constraints. In order to avoid trivial solutions, we consider E (0, H]. We denote the
optimal policy as x which solves the above optimization problem. Since n² is obtained by having complete information, it is also denoted as the best policy in the hindsight.
Without any constraint information a priori, an agent can not know the policies that satisfy the constraint. Instead, we allow the policy to violate the constraint and minimize the regret while minimizing the total constraint violations over the K episodes. Such an approach is also considered in the existing literature [179 9. We now define the performance metric which we seek to minimize.
Performance Metric.
Let the policy employed by the agent at episode k- be T [Ti,k.... Th.::-.. TH,] The performance metric we are considering is the following
Regret(K))
V (21)
K (b V (x1))
Violation ()
(5)
where [=]+ max(z, 0}. The regret is defined as the difference between the total reward value by following the optimal policy x²' and the total reward value obtained by following agent's policy тą at episode & over K episodes. The constraint violation is defined as the difference between the threshold value Kb and the total utility function attained by following the policies over all the episodes K.
Linear Function Approximation. To handle a possible large number of states, we consider the following linear MDPs.
Assumption 1. The CMDP is a linear MDP with feature map o 8 S A + Rd, for any h, there exists d unknown signed measures Pa = -p S Ax
,.,,,,,, 1 over S such that for any (x, 0, x')
Pa(x'1 a) = (Ó(x, u),
(6)
and there exists vectors 0, 0gh E Rd such that for any (z, E 5xxA.
rh (2( a) (d(ar, a), 0r,n)) gh (2x, a) (0(x,, 0g.))
Assumption adapts the definition of linear MDP [4] 16 to the constrained case. By the above linear in terms of feature map (- fx. a) can still have infinite degrees of freedom since
definition, the transition model, the reward, and the utility functions
6. We remark that despite being linear, (.
(.a(-) is unknown. Note that tabular MDP is part of linear MDP [14.
Note that 17 studied another related concept known as linear kernel MDP. In the linear kernel MDP, the transition probability is given by P (2'11, [z, a) = (1b(x', xx, a), 0z). In general, linear MDP and linear kernel MDPs are two different classes of MDP [7].
Similar to Proposition 1 in (14, we can show that for a linear MDP and for any policy т there exists (ws, H such that QT,, (z, a) (wJ.., Φ(2,0) a)) for any (a, h) E S x Ax H). We, thus, focus on linear action-value function.
Dual problem and Slater's Condition. We first introduce few notations which we will use throughout this paper.

---

Definition 2. Vi (.) = V Vi, + YV (.g)) ()) and Q (z, - Q7 (x, + YQ (z,a), where is the dual variable.
Thus, V. (-) and 0% (..)) are respectively the composite value function and Q-functions re- spectively. We can cast the problem (4) saddle point problem max, miny L(x,, Y) where [(T,, Y) v + (21) b) V.T. Yb, where π is the primal policy and Y is the dual variable. However. the lagrangian is non-concave in [88] even though it is convex in Y. Nevertheless, the strong duality holds [9].. Hence, there exists optimal dual variable y*, such that max, [(T, Y*) will correspond to the optimal reward value function.
5.1
We assume the following slater's condition in this paper.
Assumption 2 (Slater's Condition). There exists Y O, and ((A|D, H), such that V (x1)) Z
b + 7
V (x11
V (x)1
Lemma (Boundedness of Y*). The optimal dual-variable Y
The slater's condition mild in practice and commonly adopted in previous works 7 20 the properties of the slater's 's condition to bound the performance of our proposed algorithm.
We use
Definition 3. We set -2//7
Our Approach
Algorithm Model Free Primal-Dual Algorithm for Linear Function Approximation
log(IAA)K
Initialization: Y1 0, Wish
0. g 2H///a 2(1 +H) 7 E/VKHH,
Gidff/logg 4 log AldT//dTpp) 2: for episodes 1,.... K do
3: Receive the initial state xt
4: for step h H, H
1, ..... do
A f 1-1 (( 07 (1 a5) AI
5:
6:
(1 (r) + Vk 7. (1)4
7:
wh + (AA) 0(0% 02) 07) (
8:
C.((,)) + (wn Φ(, ((())
(()-)))))
9:
2u + minf(u)) -(-
(hl,(al-) = exp(a(Q# (.a) (
10:
Ea exppa((Q (3,a) V ()a))
11:
VE (-) = E. (0t r.
12:
Vk (.)()) (.) En (al))a))) (saa)
13:
for step h I..... H do
14:
Compute C a). Q+ g.h (x a). n (aa for a.
15:
Take action af. Th. (-1x and observe a
16:
Y max/mmnnff + n (z1)). (3.0)
We now describe our proposed algorithm in Algorithm I This algorithm is based on the primal-dual adaptation of the LSVI-UCB [14). For given dual variable, the primal policy is updated, and then the dual value is updated based on the estimated utility value function. At each episode, the algorithm consists of three parts. The first part (Steps 4-12) consists of updating the parameters w w and Aς which are used to update the Q and V at episode k. A is the Gram-matrix for the j.h. regularized least square problem (see Eqn. (8), later). Note that the Steps 8-12 are not evaluated for each state, rather, they are evaluated only for the encountered states till episode k - 1. Hence, we do not need to iterate over potentially infinite number of states. For the first episode, since l: - and 1, we have w 0, Vj and A AI. We note that ((, for r.g.
5

---

The value functions are updated (Steps 11-12) based on Q function and the policy. The policy is based (Step 10) on a soft-max policy unlike the greedy one in the unconstrained case [4]. Soft-max policy SOFT-MAX, (X) {SoFT-MAX, (X)) for any vector X E R (g is a |Alddimensional vector with parameter where the i-th component
explax;)
SOFT-MAX, (X) E exp(aX,,)
At step h, (a.a(a//x) is computed based on the soft-max policy on the composite Q-function vector (2r (z) Y. (2, a) Jue where Y₁ is the lagrangian multiplier. When a = co, this becomes equal to the greedy policy. The second part (Steps 13-15) is the execution of the soft-max policy based on the composite Q-value for the encountered state ox.
Q function and Value function Estimation. We need to estimate the value-function and Q-function with respect to the policy .T. However, there are challenges. We do not know PA, in Bellman's equation 33 rather PAV, 3Ah+1 should be replaced by the empirical samples. Further, in the large state space, we can not iterate over all (ar, a). Rather, we parameterize (s-)) by a linear form (uf, )) o(+ The intuition is to obtain wfth from the Bellman's 's equation using the regularized least-square regression. We obtain wh,n for j g, according the following equation
k-1
j.A - arg min WER
Ebi o + VAA++ (1h+1) w² a()%),7))3 + A//w|/
(8)
Then, an additional bonus term ((
is added as in 14. 3 is constant which we will characterize in the next section. Such an additional term is used for upper confidence bound in LSVI-UCB [14). The same additional term is used for both Q and 0 Note the difference with the LSVI-UCB, here, we need to estimate the value function corresponding to the soft-max policy na where in LSVI-UCB, greedy policy corresponding to the Q Q-function is used.
Policy. We update a soft-max policy which selects actions according to the estimated 'composite' Q-function at the k-th episode. The reason behind using the soft-max policy instead of a greedy policy will be apparent in the next section when we state the main results and the proof ideas. Note from the strong duality, for optimal dual variable Y*, optimal primal policy π- maximizes the composite value function y*","" , (Definition 2). Thus, the optimal policy should be a greedy one based on this optimal dual value Y*. However, the greedy policy is not Lipschitz, hence, it does not provide uniform concentration bound for each individual value function, an essential step in the regret bound (Section 4.2). Hence, compared the unconstrained scenario, we need more exploration in the policy space w where the apparent reason is that we do not know the optimal dual variable beforehand. Since we use the soft-max policy, there is a gap compared to the optimal value even when the lagrangian multiplier Y& becomes equal to Y However, if a in the soft-max max policy also scales with K, then we can bound the gap from the optimal value function (Section 4.2
Dual Update. To infer the constraint violation, we estimate 9. for 9.1- We update the lagrangian multiplier Yg by moving towards minimizing the lagrangian L(T, Y) over Y 2 0 in line 16, where n > is step-size and E is the upper bound on the dual variable such that optimal dual variable Y is contained within [0, E). The dual update is similar to the step described in Α.
The dual update works as a trade-off between the reward maximization and the constraint violation reduction. If b - V._ 2 O, that means with a high probability, the constraint will be violated for the policy тg. Hence, the dual value is increased in order to focus on minimizing the constraint violation. Otherwise, the agent tries to maximize the reward value function.
Space and Time Complexities. We remark that Algorithm 1 only needs to store Ye. wit w g.h. Th (#f, a gh (2f af),, AA, and {ø(#), a) for all (h, E [H] x [K], hence, takes (dd H + d.TT) space. When we compute (A using Sherman-Morrison formula, the com- putation of V/ 1 is dominated by computing Q 2 and the policy Ty. Hence, it takes (ld AT") time. Note that since our approach is model and we do not need to evaluate integrals as in M in order estimate P, VV
Note that both 7) and a use the knowledge of K. In case, K is unknown, one can use the "doubling trick" (21 which will only scale the regret and constraint violation by constant factor.

---

4 Analysis
We now state the main result. We prove that Algorithm 1 achieves regret and constraint violation which are sublinear in T KH where T is the total number of steps.
4.1 Main Results
Theorem 1. pixp > O. set 1, = Li in Algorithm for some absolute constant Cj. With probability (1 p).
Swheritthhwwhheeeeeeeeeee Where = log(log([A))AdT]]
Regret(K) K) S CVd3 + +VVHT
C²2 + 23T
Violation -
for some absolute constants C, and C".
We remark the difference with the existing results. Since ç 2H/y (by Definition our result indicates that our approach obtains O(v H regret and the same order of constraint violation where O absorbs logarithmic factor on T. The regret and constraint violation sub-linear in T, and similar dependence is observed in [ 77. Also note that compared to the unconstrained case [14], there is an additional log([AA)) factor the value of which arises because we use soft-max policy instead of the greedy policy which adds to the covering number. The regret and constraint violation do not depend on the dimension of the state space, rather, it depends on the dimension of the feature space. To the best of our knowledge this is the first result which shows both Ö regret and constraint violation in the model-free set up (tabular or linear) without requiring a simulator.
Comparison with [7]: Compared to 7 which also considers linear function approximation (however, considers linear kernel MDP rather linear MDP) we improve the result in (7) by a factor of H. Second, compared 77. which is a model-based policy-based algorithm, ours is model-free value-based algorithm. Due to this, the above uniform concentration challenge does not exist in [7]. Moreover, our model-free algorithm also enjoys an easy implementation and improved computation efficiency since it does not estimate the next step expected value function as in 7 which requires an integration oracle compute d-dimensional integration at every step. 7 also needs to store the previous policies and estimated value functions, hence, it needs ((T) additional space complexity. We have an additional vd factor in front of the regret and constraint violation. Similar difference in regret is also observed between the model-based linear kernel unconstrained MDP [22] and model-free linear unconstrained MDP [4] even in the unconstrained case.
Similar to the discussion in Section 3.1 on 2 our result directly translates to a sample complexity guarantee (or, PAC guarantee). For example, we can learn policy such that V (æ1) V, (21) s and - V (x1) < after O(d number of samples. Here, the policy æ is obtained after running Algorithm for Ö (idd11/// /e2 number of episodes, and then selecting policy mi with probability 1/K K for any k E [K].
Recently, 24 proposed an algorithm with provable sample complexity guarantee for linear CMDP. However, the regret and violation guarantees are different from the sample complexity guarantees as the former ones any time guarantee. The proposed algorithms different since the goal is different. In particular, the uniform concentration bound challenge does not appear there. Note that using the explore-then. weee--teee--omeeee then-commit algorithm (23,, one can achieve ( regret for large T (from ((1/e) sample complexity bound achieved in (24)) which is worse than ours. Additionally, we achieve zero violation (Remark while maintaining the same order of regret with respect T.
4.2 Outline of the Proof
In this section, we provide an outline of our proof, which is mainly divided into three steps. We first establish a decomposition of the sum of reward regret and constraint violation. Then, we will bound two key terms that are related to optimism and prediction error, respectively. Finally, using standard optimization tools, we can achieve the main results. We highlight that the key challenges lie in the second step where balance between the optimistic term and prediction emro term is handled via the introduced soft-max policy.
7

---

will see Step 1: Bounding the sum of Regret and violation scaled by dual variable Similar to M. we first establish the following decomposition. which upper bounds the sum of regret and violation. This will serve as the basis when applying optimization tools in Step 3.
Lemma (Decomposition). For any E [0, c),
we have
K
1 y² + 7 K
(V (a1) (x1)
VA (21)) + Y (b (21() I 27
K+
k=1
(2)) (z1) Yvvgi ( (2)) + Vv (21) +
T1
K
((((()) (xT +
(o - Vo.1
- (11))
1=
72
Note that Ti is similar to the term related to optimism in the unconstrained case with the difference being that we now have two value functions weighted by the dual variable Yt. Similarly, T2 is similar to prediction error term with the additional weight by Y. Since the first term in the above inequality can be easily bounded with a proper choice of v7, we are only left to bound Ti and T2, respectively.
Step 2: Bounding Ti and To To bound To and T1, we need to bound the difference between the individual estimated value function V.A. and the individual value function Vj,h corresponding to given policy æ episode k. As in the unconstrained case, the key step is to control the fluctuations in least-squares value iteration. In particular, we need to show that for all (k: h) E [K] x [H] with high probability
Σ blzh a/) (Vint1(0h+1) PA sh+ (1% 0R)
(A))-1
is upper bounded by lower order term (e.g., Old/log K). To this end, value-aware uniform con- centration is required to handle the dependence between j,h+t1 and samples { )==1 which renders the standard self-normalized inequality infeasible in the model-free setting. The general idea here is to fix a function class Vj.1 in advance and then show that each possible value function in our algorithm V. is within this class which has polynomial log-covening number. In the following, fix an h E [H] and drop the subscript h for notation simplicity.
Uniform Concentration Bound for class of value function: We first note that this uniform concentration bound is the main motivation for us to choose soft-max policy that the standard greedy policy would fail in this case. That is, in order to guarantee that for each possible VAA there is an e-close function in Vj. it would basically lead to very large covering number. To address this, we introduce soft-max policy and define the following cor- responding function classes. We first define the following class for Q-function for
r,g- 2, ().) = min (wy o0, )) + (3/0(.))) (0..))..)AA)))) (A,)) (An)) H). Then, we define the follow- ing value function class Vj. Vi = (V)V)(
En ((( Q5 E 2 E [T, where IT is given by the following class IT (a| SOFT-MAX (Q.. +Y (): Va A, Q,
2r, Q2 E 2,, Y E [), where SOFT-MAX is defined in
Why soft-max? At this moment, is critical. Suppose we follow the standard greedy selection, which corresponds to a = co in above. The key issue in this approach is that needs large c-covering for V, so that each possible V can be well-approximated (i.c., e-close) by function in Vy. This is in sharp contrast to the unconstrained case where VA has a polynomial log-covering number. To see this difference. in the unconstrained case, we only have V, that is greedy with respect to Q By the fact that max, is a contraction map, an e-covering of the Qt implies an e-covering of V and meanwhile the covering number of Q, is reasonably small (Lemma 14) by standard arguments. This no longer holds in the constrained case due to the use of a composite Q-function. In particular, note that if the policy is greedy w.r.t. the composite Quuuctioo,, then an e-covering of Qf fails to be an
explain why the introduction of soft-max in our algorithm
8

---

e-covering of V in general since the greedy policy is not smooth in that a slight change of the composite Q-function could lead a substantial change of the output action. This leads a large distance for individual value functions due to the different action choices, even though the Q-function is close (Please see Appendix [ for an example). Hence, one can not approximate individual value function within c-bound using greedy policy based on composite Q-function. This fact motivates us to turn to SOFT-MAXa. which is Lipschitz continuous with a Lipschitz constant at most 2o. Thus, our main idea as follows. Given Q Qº and Yú. we can first find fixed Q, E 2
@ E 2g and Y E [ such that Q |10e +Y20) - (②, + 2 S with reasonably small covering number. Then, thanks to
I - Qr S Se1. Q Qq no S S2,, y* 81
I 63 and
the smoothness of soft-max function, we have [|T #||, S the closeness of individual Q-function yields the closeness of individual V- function (Lemma [3).
2cxe (Lemma 15) Combining this with
Hence, it ensures that the class V, in our set-up has log-covering number of (dglog()).
Choosing hy perramerreeeter a to achieve bound: A larger value of a means that we need a smaller hence larger covering number. Then, one may wonder if we can choose an arbitrarily small value for a. However, the term Ti will be enlarged if we choose too small a. Note that in the unconstrained case, Ti is upper bounded by zero due to optimism under greedy policy. Now, since we are using soft-max, we need bound the approximation error between the soft-max and greedy one. As expected, in this case, a larger a leads to a smaller approximation error.
From the discussions above, we can see that the approximation-smootheee trade-off of the soft-max function is well captured by our TI and Tz, respectively. Therefore, we need to carefully choose the value of to balance these two. In particular, with log([AA) we have the following bounds on Ti and T2, respectively.
log((AA)) H log((AA), Hence, for a 2(1 + E HY
Lemma 3. With probability p/2, we have Ti S K
a
we have TI S 21 (1 + H) with probability 1 - 1pp/2.
Lemma 4. With probability at least 1 p/2,, T2 S O((Y + 1)THTT?)) where L log[log( (gg[log[AA))AdT]] (IA)))dTT/p))
Remark The additional log) factor in arises as trade-off for selecting soft-max policy as is evident in Lemma 3 When we compensate by making a scaled with log) A| in Lemma it increases the covering-number by [o] as well in the term.
Step 3: Final Result by combining all the pieces: By replacing Y = 0, 17 = E/ (/(V and combining Lemma 23 4 we obtain the regret bound. We also obtain the constraint violation using the idea from IT.
Remark 2. We can reduce the violation to zero while maintaining the same order on regret with respect to T (Appendix [T]] We consider tighter optimization problem where we add Ç in the constraint of (4). In Appendix we bound the difference between the optimal value function for the tighter and the original problem as a function of C. Since the tighter problem is also CMDP, we attain the regret and violation bound as in Theorem ! with b b+ Ç in place of b. Hence, by choosing S, we can show that it is possible to achieve Ö( D(VT) regret and zero violation for large enough K (Theorem 3 in Appendix H albeit with an extra H factor in front of regret bound.
5 Experiments
We evaluate Algorithm on a simulated model for job scheduling to validate our theoretical results. We consider that the number of jobs belongs to the discrete state {0, 1,...,9) 9} where 0 means that there is no job. Total time horizon (H) is divided in 10 steps. After I/ steps, a new episode begins. At the start of the each episode, the state of the job is assumed to be 9, i.e., the job stack is full. The agent needs to decide whether to send job (a = 1) or not (a = 0) to machine. We assume that
= 1, the agent sends 2 jobs to a machine and incurs cost as the machine spends some resources to process the job. We assume that the rewards are step dependent. In particular, we assume that at time steps from 3 to 6, the reward is 1 - 0.9a, In other time steps, the reward is 1 0.2 This mimics the setup where at certain time, might be more costly to process a job (for example, electricity cost might be higher, or the machine needs to abandon an important job).

---

x10*
Constr, Violation
2000
Regret
1500
1000
2
1000
50,000
100,000
150,000 200,00
1000
50,000
100,000
150,000
Figure I: The plot for cumulative regret and constraint violation as a function of K. Each plot is an average of 10 trials.
We assume that even if the scheduler schedules a job, the machine might not be able to complete the 2 jobs. In particular,
w.p. 0.8 max a, 0} w.p. 0.1
max (3h 2a, 0}
Th+1
The
otherwise
Thus, o O, the state Th+1 The The agent gets an utility of g on xh+1) = (I 12-11/22. We want that utility to be greater than or equal to 4 at the end of every episode. This will ensure that most job can remain at the end of each episode.
We run Algorithm| 1 for x 10" episodes (K). The parameters we used are the followings: a K/(1 + 2H /- + H).
2H/(vVKH3) We set 7 1. We have also set = 0.1 in order to ensure that the violation goes towards 0 as K increases. Note that the setup tabular form. Since linear MDP contains tabular form, the feature space representation becomes simple, in particular, o(s, a) es.o where e is 1 for the state-action pair (s, a). and 0 otherwise. The dimension of the feature space is S||AA]. The cumulative regret and constraint violations are shown in Figure 1 As predicted by theory, the regret scales only as vK. On the other hand, the cumulative violation oscillates. However, the violation approaches 0 as increases. The oscillation of violation is due the fact that dual variable also oscillates in order to illicit conservative response when the cumulative violation increases, and illicit aggressive response when the violation decreases.
be represented in
Conclusion and Future Work
We propose model-free RL-based algorithm for linear MDP. We have achieved Õ(Va3 H3T) regret and Ö( H3)) constraint violation. To the best of our knowledge, this is the first result which shows ((VT) regret and (VTT) constraint violation without requiring a generator for the model-free case. We have extended the LSVI-UCB algorithm in the primal-dual type framework. We have underlined the technical challenges in doing so and explained how the greedy policy fails to achieve uniform concentration bound for individual value function. Subsequently, show that soft-max type algorithm achieves that.
Compared to 7 our regret is off by Vd factor which due to the fact that we need to use uniform concentration bound. The similar gap is also observed for the unconstrained set-up as well. Whether we can tighten this dependence on remains an important future research direction. Whether we can tighten the dependence on H also constitutes future research direction. Extending the work to the setup where the feature-space needs to be learnt also important. Recent works 27 on feature-space learning for unconstrained MDPs may provide some insights in this direction. Consideration of non-linear MDP also constitutes a future research direction.
Acknowledgment
XZ is partially supported by the NSF grant CNS-2153220. This work has been supported in part by NSF grants: 12471 (also partly funded by DHS), CNS-2106933, and 1N5-1901057 and a grant from the Army Research Office: W911NF-21-1-0224
10

---

References
[1] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-explootaton in constrained mdps. arXiv preprint arXiv:2003.02119, 2020.
[2] Rahul Singh, Abhishek Gupta, and Ness B Shroff. Learning in markov decision processes under constraints. arXiv preprint arXi::2002.12435, 2020.
[3] Kianté Brantley, Miroslav Dudik, Thodoris Lykouris, Sobhan Miryoosefi, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun. Constrained episodic reinforcement learning in concave- convex and knapsack settings. arXiv preprint arXiv:2006.0505), 2020.
[4] Liyuan Zheng and Lillian Ratiff. Constrained upper confidence reinforcement learning. In Learning for Dynamics and Control, pages 620-629. PMLR, 2020.
[5] Krishna C Kalagarla, Rahul Jain, and Pierluigi Nuzzo. sample-efficient algorithm for episodic finite-horizon mdp with constraints. arXiv preprint arXiv:2009. /10000009.11/4,, 2020.
[6] Tao Liu, Ruida Zhou, Dileep Kalathil, PR Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. arXiv preprint arXiv:2106. 026644 2021.
[7] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang. Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization, In International Conference on Artificial Intelligence and Statistics, pages 3304-3312. PMLR, 2021.
[8] Tengyu Xu, Yingbin Liang, and Guanghui Lan. Crpo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pages 11480-1 1491. PMLR, 2021.
[9] Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo R Jovanovic. Natural policy gradient drimal-dual method for constrained markov decision processes. In NeurlPS, 2020.
[10] Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. arXiv preprint arXiv:2109.06332, 2021.
[11] Sven Koenig and Reid Simmons. Complexity analysis of real-time reinforcement learning. In AAAI, pages 99-107, 1993.
[12] Mohammad Gheshlaghi Azar, Rémi Munos, and Bert Kappen. On the sample complexity of reinforcement learning with a generative model. arXiv preprint urXiv:1206 6461, 2012.
[13] Honghao Wei, Xin Liu, and Lei Ying. A provably-efficient model-free algorithm for constrained markov decision processes. arXiv preprint arXiv:2106.01577, 2021.
[14] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143. PMLR, 2020.
[15] Sanae Amani, Christos Thrampoulidis, and Lin F Yang. Safe reinforcement learning with linear function approximation. arXiv preprint arXiv:2 106.000.0000 006396639.9....... 2021.
[16] Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
[17] Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning. pages 1 12802. PMLR, 2021.
[18] Alckh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1--6, 2021.
[19] Santiago Paternain, Miguel Calvo-Fullana, Luiz FO Chamon, and Alejandro Ribeiro. Safe policies for reinforcement learning via primal-dual methods, arXiv preprint arXiv: Xiv:19111009001 2019.
11

---

[20] Shuang Qiu, Xiaohan Wei, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. Upper confidence primal-dual optimization: Stochastically constrained markov decision processes with adversarial losses and unknown transitions. arXiv preprini arXiv:2003.00660, 2020.
[21] Lilian Besson and Emilie Kaufmann. What doubling tricks can and can't do for multi-armed bandits. arXiv preprint vrXiv:103330697, 2018.
[22] Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang. and Lin Yang. Model-based rein- forcement learning with value-targeted regression. In International Conference Machine Learning, pages 463-474, PMLR, 2020.
[23] Chi Jin, Zeyuan Allen-Zhu Sebastien Bubeck, and Michael Jordan. Is q-learning provably efficient? arXiv preprint arXiv:1807.03700 2018.
[24] Sobhan Miryoosefi and Chi Jin. A simple reward-free approach to constrained reinforcement learning. In International Conference on Machine Learning, pages 15666-15698. PMLR, 2022.
[25] Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.07035, 2021.
[26] Xuezhou Zhang, Yuda Song, Masatoshi Uehara, Mengdi Wang, Alekh Agarwal, and Wen Sun. Efficient reinforcement learning in block mdps: A model-free representation learning approach. In International Conference on Machine Learning, pages 26517-26547. PMLR, 2022.
[27] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095 200007 2020.
[28] Ling Pan, Qingpeng Cai, Qi Meng, Wei Chen, Longbo Huang, and Tie-Yan Liu, Reinforcement learning with dynamic boltzmann softmax updates. arXiv preprint arXiv: 0e0.. 0093009926 2019.
[29] Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni, and Manolis Zampetakis. Optimal aproximatioonssmottnnss tradeoffs for soft-max functions. arXiv preprint arXiv:2010./ 1450, 2020.
[30] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312-2320 2011.
[31] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv: 1011.307 2010.
[32] Sharan Vaswani, Lin F Yang, and Csaba Szepesvári. Near-optimal sample complexity bounds for constrained mdps. arXiv preprint (xxiv:222060667777 2022.
[33] Bruce Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applica- tions. Advances in Applied probability, 14(3):502-525, 1982.
[34] Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultancous-move markov games using function approximation and correlated equilibrium. arXiv preprint arXiv:2002.07066, 2020.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We have clearly compared our results with the existing work. In the Conclusion and Future Work, we identified some important directions where our approach can be extended.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We clearly state the Assumptions and 2 in Section 2
(b) Did you include complete proofs of all theoretical results? [Yes] We have added the proofs Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [Yes] Our main goal to obtain Theoretical Results. Nevertheless, have performed experiment simulated setup to verify our theoretical results.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We have characterized the parameters.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "rUz3NQXtIXF", "reviewer": "Reviewer_4Xoe", "summary": "The paper considers the episodic, model-free, simulator-free, constrained Markov Decision Process (CMDP) framework with a linear function approximator. \nThe main contribution is the primal-dual algorithm that is based on the LSVI-UCB algorithm. The paper also provides the regret and constraint violations' bounds that do not depend on the state space cardinality. Instead, the bounds depend on on the dimension of feature mapping $d$. In addition, the presented algorithm can achieve a zero constraints' violation given a sufficiently large number of episodes $K$ as proven in theorem 3.\nThe paper also compares the presented algorithm with other algorithms that consider the model-free CMDP case, and mentions the shortcomings of them (e.g. their need for a simulator, being model-based).", "questions": "**Question 1:** With linear function approximators, finding a good performing set of features significantly affects the approximations' accuracy. Can the author(s) discuss how a set of features $\\phi(s,a)$ can be chosen for a linear approximator?\n\nI am willing to increase my score if the author(s) address the weaknesses I mentioned as well as the question I have here.", "limitations": "**Limitations:** work only considers a linear function approximator. It would be nice to expand this approach to a quadratic function approximator or a kernel-basis functions. The author(s) also mention the possibility of finding tighter bounds given *d* and *H*, and I am pleased that they addressed this bound gap.\n\n\n**Societal impact:** Not applicable to this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\nThe primal-dual extension to the LSVI-UCB algorithm is non-trivial and is a good contribution to the CMDP literature. The author(s) also clearly presented how their algorithm differentiates from other model-free or tabular algorithms as shown in table 1. The constraints' violations was also shown to go to zero asymptotically w.r.t. the number of episodes. \n\nIn addition, theorem 3 (and its proof in the appendix) is a nice addition to the finite-time regret\\constraint violation analysis. I read the proofs provided in the appendix, and to the best of my knowledge they appear to be correct in their analysis. \n\n\n**Weaknesses:**\nThe paper's biggest weakness is its lack of experimental evaluation of the proposed algorithm to support the theoretical bounds. Some of the cited work (Triple-Q algorithm) do present results for the tabular and function approximation cases. \n\nIn addition, the Triple-Q algorithm (cited as [13] inn the paper) was also extended to the neural networks' function approximation case. This raises the point if the proposed primal-dual algorithm should be extended to other function approximators (possibly radial-basis function and not neural networks). The claim on lines 86 and 87 is hence inaccurate since other work can already handle continuous state spaces. \n\nMinor comments I have:\n\nLine 45 *value function or a policy*: value function of a policy.\n\nLine 87 *regret bound shown in the above paper*: it's better if the author(s) cites the paper again to avoid confusion. \n\nThe Gram matrix $\\Lambda_h^k$ is first mentioned on line 196 but it's referenced earlier in Algorithm 1 and its description. The symbol definition should be introduced earlier in the paper.\n\nLine 354: *Whether we can the tighten the*: Whether we can tighten the.\n\nLine 514 *we, now, recursively*: we now, recursively. \n\n\n--------------------------------------\n### After rebuttal:\n\nI read the responses by the author(s) and also the revised manuscript. I am pleased to see that the author(s) implemented an experiment in less than a week. I also find their response regarding picking a good feature set $\\phi(s,a)$ sufficient.\n\nI increased my score from 6 to 7.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SV8MmycGTF_", "reviewer": "Reviewer_K6Mq", "summary": "The paper deals with providing an algorithmic scheme which is provable efficient for Model-free RL in a setting where there are additional constraints on the learned policy in the sense that it also needs to ensure that the expected utility is above a given threshold. The paper also claims that their algorithm does not require an explicit simulator or oracle to run trajectories for a given policy for some number of rounds (as is usually the case with many existing RL methods). They further provide, regret guarantees for their algorithm and compare it with the existing approaches to show their usefulness and superiority.", "questions": "1) Each episode starts with a state drawn from a fixed distribution -- Seems to require a reset at the start of every episode? This seems to contradict the claim that their scheme is simulator-free. Am I missing something?\n2) Since I am not very well versed with this topic, can the authors provide some insight on Assumption 2? ", "limitations": "The authors have clearly stated the limitations of their work and the areas of future directions.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ Paper is technically solid.\n+ The theoretical results appear to be sound and useful\n+ The problem attacked is well-motivated\n\nThe main weakness of the paper according to me is readability.\n- It might help to organize the outline of the proof in a more structured way by giving (sub-)headings for each the various parts, for easy parsing.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OIKMBKWhaJz", "reviewer": "Reviewer_F93d", "summary": "The paper studies episodic constrained MDP problems. The authors propose a model-free value-based RL algorithm with linear function approximation and establish sublinear regret and violation. ", "questions": "- What is $\\xi$ in your analysis? Any dependence on $H$?\n\n- It is useful to discuss some work in linear setting: A Simple Reward-free Approach to Constrained Reinforcement Learning\n\n- The proof outline is helpful, but it is useful to highlight the new key techniques. If I set $Y=0$, would this become the standard LSVI-UCB and analysis carries over? \n", "limitations": "Yes. ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Originality\n\n- The proposed primal-dual algorithm is new and it works for constrained MDPs with linear function approximation, which is an important constrained RL setting. \n\n- The proof has some novel ingredients, e.g., uniform concentration of value functions.\n\n## Quality & Clarity\n\n- The paper is well written and all claims are justified via proofs. The authors also discussed improvements and limitations in the end of the paper. \n\n## Significance\n\n- The proposed primal-dual algorithm is based LSVI-UCB while taking account for constraints in the linear function approximation setting. This is a new advance in learning constrained MDPs with large state spaces.\n\n- The analysis generalizes the uniform concentration bound in LSVI-UCB to the constrained case using an intermediate softmax policy update.\n\n- This regret and violation bounds are near-optimal. They improve the dependence on $H$ compared with the existing methods, while $d$-dependence is slightly worse.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "IulKbjGOqWE", "reviewer": "Reviewer_EWtE", "summary": "This paper studied the episodic CMDPs with linear function approximation and proposed the LSVI-UCB based algorithm which can achieve $O(\\sqrt{T})$ regret and $O(\\sqrt{T})$ constraint violation bounds.  The author also showed that zero constraint violation is achievable for a large $T.$", "questions": "1. This paper indicates that their algorithm is model-free in the sense that the algorithm does not need to estimate the transition kernels. My concerns come from the comparison between this paper and [7]. Although Linear MDP and linear kernel MDP have different assumptions on the model, your algorithms both need to solve a LSTD problem at each episode. [7] needs to estimate the transition kernel in the tabular setting because of the assumption from the linear kernel assumption. I am wondering if your algorithm needs to estimate the transition kernels in the tabular setting?\n2. The LSTD-based algorithms are well studied in both bandit and RL settings. Can the authors clarify what the novel technical contributions of this paper are?", "limitations": "I don't think this paper has any potential negative societal impact.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. The paper is well-written and well-organized.\n2. The paper proposes a model-free, simulator-free reinforcement learning algorithm for CMDPs with linear function approximation that can achieve $\\sqrt{T}$ regret and zero constraint violation.\n3. The paper proves that zero constraint violation is possible when $T$ is sufficiently large.\n\n**Weaknesses**\n1. The memory complexity is high, since the algorithm needs to store all the historical states and actions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept