Achieving Sub-linear Regret in Infinite Horizon Average Reward Constrained MDP with Linear Function Approximation
Authors: Arnob Ghosh
Xingyu Zhou
Ness Shroff
Venue: ICLR 2023 poster (2023)
Keywords: Reinforcement Learning Theory
Infinite horizon Average Reward
Theory of Constrained Reinforcement Learning
Linear MDP
Model-free RL
Soft-max

Abstract: We study the infinite horizon average reward constrained Markov Decision Process (CMDP). In contrast to existing works on model-based, finite state space, we consider the model-free linear CMDP setup.  We first propose a computationally inefficient algorithm and show that $\tilde{\mathcal{O}}(\sqrt{d^3T})$ regret and constraint violation can be achieved, in which $T$ is the number of interactions, and $d$ is the dimension of the feature mapping. We also propose an efficient variant based on the primal-dual adaptation of the LSVI-UCB algorithm and show that $\tilde{\mathcal{O}}((dT)^{3/4})$ regret and constraint violation can be achieved. 
This improves the known regret bound of $\tilde{\mathcal{O}}(T^{5/6})$ for the finite state-space model-free constrained RL which was obtained under a stronger assumption compared to ours.  We also develop an efficient policy-based algorithm via novel adaptation of the MDP-EXP2 algorithm to our primal-dual set up with $\tilde{\mathcal{O}}(\sqrt{T})$ regret and even zero constraint violation bound under a stronger set of assumptions.

Published as a conference paper at ICLR 2023
ACHIEVING SUB-LINEAR REGRET IN INFINITE HORI- ZON AVERAGE REWARD CONSTRAINED MDP WITH LINEAR FUNCTION APPROXIMATION
Arnob Ghosh
Xingyu Zhou
Electrical and Computer Engineering The Ohio State University ghosh. 2440osu.
Electrical and Computer Engineering
Wayne State University
xingyu. zhou@wayne.edu edu
Ness Shroff
Electrical and Computer Engineering The Ohio State University shroff. 110osu. edu
ABSTRACT
We study the infinite horizon average reward constrained Markov Decision Process (CMDP). In contrast to existing works on model-based, finite state space, we consider the model-free linear CMDP setup. We first propose a computationally inefficient algorithm and show that (VddT)) regret and constraint violation be achieved, in which I is the number of interactions, and d is the dimension of the feature mapping. We also propose an efficient variant based on the primal- dual adaptation of the LSVI-UCB algorithm and show that ((ddT)//4) regret and constraint violation can be achieved. This improves the known regret bound of (r75/) for the finite state-space model-free constrained RL which was obtained under stronger assumption compared to ours. We also develop an efficient policy-based algorithm via novel adaptation of the MDP-EXP2 algorithm to the primal-dum set up with ((VT) regret and even zero constraint violation bound under a stronger set assumptions.
INTRODUCTION
In many standard applications of Reinforcement learning (RL) (c.g., autonomous vehicles), the agent needs to satisfy certain constraints (e.g., safety constraint, fairness). These problems can be formulated as constrained Markov Decision process (CMDP) such that the agent needs to ensure that average utility (cost, resp.) exceeds certain threshold (is below threshold, resp.).
While CMDP in the finite state-space has been studied, those studies can not be extended to the large state space. RL with value function approximation has demonstrated empirical success for large-scat RL application using the deep neural networks. However, theoretical understandings of constrained RL with value function approximation is quite limited. Recently, Ghosh et al. (2022) has made some progress towards the understanding of the constrained RL for linear MDP under episodic setting. In particular, Ghosh al. (2022) developed a primal-dual adaptation of the LSVI-UCB and showed Ö(vPTT) regret and violation where d the dimension of the feature space and the number of interactions. Importantly, the above bounds are independent of the cardinality of state-space.
However, infinite-horizon model fits well compared the finite horizon setting for many real- world applications (e.g., stock-market investment, routing decisions). Compared to the discounted-rewwe reward model, maximizing the long-term average reward under the long-term average utility also has its advantage in the sense that the transient behavior of the learner does not really matter for the latter case (Wei et al., 2020). Recently, model- based RL algorithm for infinite-horizon average reward CMDP has been proposed (Chen al., 2022). However, it considers tabular setup. Further, the model-based approach requires large memory to store the model parameters. is also hard (computationally) to extend model-based approaches for infinite state-space such linear MDP (Wei et al., 2020).

---

Published as a conference paper at ICLR 2023
Model-free RL algorithm is more popular because of the ease of implementation, and being computa- tional, and storage efficient particularly for the large state space. However, model-free learning for the infinite horizon average reward setup is even more challenging. For example, it is still unknown whether it is possible to achieve computationally efficient model-free algorithm with ((VT) regret even under the unconstrained tabular setup (Wei et al., 2020) for a weakly communicating MDP. To the best of our knowledge, Wei al. (2022) is the only paper to study model-free algorithms for CMDPs in the infinite horizon average reward setup. In particular, they consider 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 RL applications where the number of states could even be infinite. To summarize, little known for the performance guarantee of model-free algorithms in CMDPs beyond tabular settings in the affinit-hhoizon average reward setting, even in the case of linear CMDP. 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 for the infinite horizon average reward setting?
Contribution. To answer the above question, we consider CMDP with linear function approximation, where the transition dynamics, the utility function, and the reward function can be represented as linear function of some known feature mapping. Our main contributions are as follows.
We propose an algorithm (Algorithm 1) which achieves Ó( (BT) regret and constraint violation bounds with a high probability when the optimal policy belongs to a smooth function class (Definition 1). This is the first result that shows that ((VT) regrei and violation are achievable for linear CMDP in the aafinite-horizon regime using model-free RI. Achieving uniform concentration bound for individual value function turns out to be challenging and we need to rely on the smoothness of the policy, unlike the unconstrained case. The algorithm relies on optimizer that returns the parameters corresponding to the state-action bias function by solving a contained optimization problem.
We also propose an efficient variant and show that (((T))3/+) regret and violation bound can be achieved. This is the first result that provides sub-linear regret and violation guarantee under only Assumption 1 for linear CMDP using a computationally efficient algorithm. The idea is to consider finite-horizon episodic setup by dividing the entire time-horizon T into multiple episodes T/ H where each episode consists of H steps. We then invoke the primal-dual adaptation of the LSVI-UCB algorithm proposed in Ghosh et al. (2022) to learn the good policy for the finite-horizon setting by carefully crafting the constraint for the episodic case. Finally, we bound the gap between the infniit-hhoizon average and the finite-horizon result to obtain the final result.
We also propose an algorithm which can be implemented efficiently and achieves Õ(VT) regret and ((VT) constraint violation under a stronger set of assumptions (similar to the ones made in Wei et al. (2021a) for the unconstrained setup). We, further, show that one can achieve zero constraint violation for large enough (still, finite) T' while maintaining the same order on regret.
We attain our bounds without estimating the unknown transition model or requiring a simulator, and they depend on the state-space only through the dimension of the feature mapping. To the best of our knowledge, these sub-linear bounds are the first results for model-free (or, model-based online RL algorithms for infinite-horizon average reward CMDPs with function approximations. Wei et al. (2022) proposes a model-free algorithm in the tabular setting which achieves ((T5/6) regret. Since linear MDP contains tabular setting our result improves the existing results. Further, we show that under the same set of Assumptions of Wei et al. (2022).
achieve zero constraint violation by maintaining the same order on regret
We relegate Related Work to Appendix A.
2 PRELIMINARIES
We consider an infinite horizon constrained MDP, denoted by (S,A, Pr,,) g) where S is the state space, A is the action space, IP is transition probability measures, and g are reward and utility functions respectively. We assume that S is a measurable space with possibly infinite number of elements, and A is finite action set. PP- a) is the transition probability kernel which denotes the probability to reach a state when action a is taken at state x. We also denote IP as p to simplify the notation. p satisfies fxx p(dze (x, a) (following integral notation from Hernández-Leend (2012))
2

---

Published as a conference paper at ICLR 2023
S x A [0, 1]. and g S A [0,1] and are assumed to be deterministic. We can readily extend to settings when r and 9 are random.
The process starts with the state T1. Then at each step t [T', the agent observes state I; E S, picks an action ag E A. receives a reward r(ze, qz), and a utility g(z,, at). The MDP evolves to 2++1 that is drawn from (- at). In this paper, we consider the challenging scenario where the agent only observes the bandit information r a₂) and ( a²) at the visited state-action pair (Iz, Qz). The policy-space of agent is ((A[S); (-I-) (+(2)) E A(A), Vx E S, and E T). Here A(A) is the probability simplex over the action space. For any Te E S. (T (Ft) denotes the probability that the action O₂ A is taken at step when the state is zg. We also denote the space of stationary policy as
A (A)S) where the policy T (zz) is independent of time t.
Let (F and J (z) denote the expected value of the average reward and average utility respectively starting from state when the agent selects action using the stationary policy (*(S))
(x)
lim T0000
T E
Σ
(2),,,)) x
for o = r,g, where I' is taken with respect to the policy π and the transition probability kernel P.
From Puterman (2014), there exists state-action bias function q satisfying the Bellman's equation for - %. (z, a) + J (x) = (x, a) + "pg--p(( [xg(x)) where vg (z) = >. π (a (z(z)) (I, a) =
(m(-Iz), 4. (x. A- of and et are analogue to the Q-function and value function respectively for finite-horizon and discounted infinite horizon scenario.
The Problem: We are interested in solving the following problem
maximize, (I) subject to JØ (z) 2 b
Let n² be optimal stationary solution of the above problem. Note that both J. and J depend
on the initial state т. Also note that our approach can be extended to multiple constraints, and the constraints of the form J5 (x)= < 6.
Unlike the episodic set-up where the sub-linear regret is possible, it is known that even in the unconstrained set-up, the necessary condition for sub-linear regret is that the optimal policy has long-term average reward and utility that are independent of the initial state (Bartlett and Tewari, 2012). Hence, assume the following:
Assumption 1. There exists J,, J and a stationary n² such that they are solution of (2) and the followings hold for all o = r,g, x E S, and a E A
Jo (x, = c(x,a) + Ex (1'),, Σ x (2)x))
(3)
We denote J as the optimal gain. We also denote the span of og as sp(())) ( sup, - og (s) for o r.g. For a finite state and action space (a.k.a. tabular case), the weakly communicating MDP is the broadest class to study the regret minimization in the literature, and is known to satisfy Assumption 1. Assumption
adaptation of the Bellman's optimality equation for unconstrained version (Wei et al., 2021a) in the CMDP. Note that unlike the unconstrained case, here the optimal policy might not be greedy with respect to yr as the greedy policy might not be feasible.
Bellman's 's equation with state-independent average reward and average utility: A stationary policy x satisfies the Bellman's 's equation with indeeenneenndent average reward and average utility there exists measurable functions vg + IR oo S x A + E such that the following holds for all x S, o = r, g. and a E A
J go (z olx, a) + E og)
Σ (2,
(4)
Wei et al. (2022) assumes that any stationary policy (not only the optimal policy) satisfies the Bellman's 's equation with iate-independent average reward and average utility. In Section 3 consider the setup where Assumption is satisfied which is weaker compared to Wei et al. (2022). In Section 4 we consider set of assumptions which entails that every stationary policy satisfies (4).
3

---

Published as a conference paper at ICLR 2023
The agent is unaware of the underlying environment, and seeks to learn the optimal policy. Hence, the agent can take action according to a non-stationar policy Te at a state Zt.
Learning Metric:
We are interested in minimizing the following metrics
T Regret (T) - az)),
Violation(T) = (Tb Eg(er,
(5)
The regret denotes the difference between the total reward obtained by best stationary policy and the reward obtained by the learner. The violation denotes how far the total utility achieved by the learner compared the Tb. Similar metrics are employed in model-based infinite horizon average reward (Chen et al., 2022) and in the finite horizon setup (Ding et al., 2021).
Linear Function Approximation. To handle a possible large number of states, we consider the following linear MDPs.
Assumption 2. The CMDP a linear MDP with feature map & S x A + TRd if there exists d over S such that for any (z,a,2' x') E A
unknown signed measures μ {u' ..... ......,,) J
P(r'Iz, a) = (Ø(x, a), u(x)))
and there exists vector 8, Bg E Rd such that for any (x, a) E
r(z, a) (0(2, 0,) g(z,a) a) (Ø(x, a),
Assumption 2 adapts the definition of linear MDP in Jin et al. (2020) to the constrained case. By the above definition, the transition model, the reward, and the utility functions are linear in terms of feature map Φ. We remark that despite being linear, IP ((-|22 a) can still have infinite degrees of freedom since yu()) is unknown. Note that tabular MDP is part of linear MDP (Jin et al., 2020). Similar Constrained Linear MDP model is also considered in Ghosh et al. (2022) (for episodic setup).
Note that Ding al. (2021); Zhou et (2021) studied another related concept known as linear kernel MDP in episodic setup. In the linear kernel MDP, the transition probability is given by P(x Izx a) = (1'(r', x, a), 0). In general, linear MDP and lincar kernel MDPs are two different classes of MDP (Zhou et al., 2021).
Under linear CMDP, we can represent the % function as a linear the feature space. Lemma 1 (Wei al. (2021a)). Under Assumptions 1 and 2, there exists fixed w E IR such that (x, a) ((x.a) a)TTs) w for r,g and all (z, a) S A with || poollVd sp(u:)).
3
OPTIMISM-BASED ALGORITMS
3.1 FIXED-POINT OPTIMIZATION WITH OPTIMISM
We present our first algorithm (Algorithm 1) which achieves Ó(sp(c;) TT) O(sp(vg) V d) constraint violation. Note that for the unconstrained tabular version, Q (T) the lower bound for regret (Auer et al., 2008). Hence, our obtained bound is optimal in terms of regret (nearly). Further, we show that we can attain zero violation while maintaining the same order in regret with an additional assumption (Remark 1). In the following we describe our Algorithm and point out the key modifications we have made over the unconstrained version.
regret and
From Lemma and (3), we have
p( a)" w = ox -J) J5 f
0 (5(d))p(dr' (x,
Hence, the natural idea is to build an estimator Wo,t for w from the data. However, we do not know J p. r, and g. Further, we also need to find π in order to obtain vg (cf.(3)). In the following, we describe how we address those challenges. First, in order handle unknown p. and o, we use the sample points till time t to estimate Wo,s. In particular, if for a moment, if we assume J and are known then we can fit Wo, such that Φ(z, a)Two, w.,t s oxx,, a,) - J + co Then solving regularized least square problem with regularization term Al|Wo,,l1 gives a natural estimate of w.,t
To,t (AA) Σ (0(x,. (-)(o(rr, - J (o.((
4

---

Published as a conference paper at ICLR 2023
ar where A, +I+ ay) a,) is the empirical co-variance matrix.
Now, we replace (2++()))) with the expression (o,x(T++1) = (T(- (o, +)4 which gives rise a fixed-point equation as (o.r(;.) = ( Wo.t- In order to incorporate uncertainty, we introduce slack variable bo, with bounded quadratic form ||bo,,IlA, S 8% (5. a parameter for r. g). It will ensure that wo is contained within Wo,t + bo,e with high-prout proshprbbbbility. Now, we discuss how we handle the unknown J and x.
We introduce Jo.t and Ti variables and design an optimization problem Pi which maximizes Jr. with the constraint Jg, 2 We also restrict x to class of soft-max policy II (Definition 1) and search for over 11.
Definition 1. We define the policy class as II as the collection of soft- policies II {-((---) x exp(o(.,)) (), E RR, L}.
We replace J in (7) with Jo,t- Further, we add the slack variable bo.t to Wo.t in (7) to obtain (8) in Algorithm This has similarity with the "optimism under uncertainty" as the optimal (wz. bg. J x for o = r.g are feasible for the optimization problem with high probability (Lemma 2) if T E II. Hence, it naturally entails that Jr,, 2 JĀ- Wei al. (2021a) also proposed an optimization problem with fixed-point equation (Algorithm 1) to obtain W.t in the unconstrained setup. In the following, we point out the main differences with the Algorithm I proposed Wei et al. (2021a) and describe the necessity of the introduction of policy space II.
First, we have an additional constraint where Jg. 2 b since we consider CMDP. Second and more importantly, in the unconstrained case (Wei et al., 2021 the policy was greedy with respect to fr- Since the greedy policy may not be feasible, we need to search over policy in the CMDP. However, we restrict the policy to function class I1. The main reason for introduction to II is that the uniform concentration bound (a key step for proving both regret and violation for model-free approach) for value function class vo not be achieved unless the policy has smooth properties such Lipschitz continuous. In particular, we need to show that log covering number for the class of u. scales at most (l)g For the unconstrained case, we only need to obtain e-covering number for o, and with greedy policy, e-covering number for the class of g-function was enough. However, we need to obtain e-covering number for both v, and Eg. hence, such a trick would not hold. In order to obtain e-covering number for Uo. we use the smoothness of soft-max to show that log e-covering number for the class of value function scales at most (log(T)) (Lemma 7). In Appendix F.6 our analysis can be extended to the class of policies which satisfy Lemma 8
Also note that we update the parameters when the determinant of A, doubles compared to As.-1 where 8t-1 is the time step with the most recent update before the time t. This can happen only at most (d log T)) times. Similar to Wei et al. (2021a), our algorithm also does not allow any efficient implementation due the complicated nature of the optimization problem. However, that with high probability, the optimal solution and parameters are feasible of P1 by the careful choice of the parameter So. and using the fact that || sd.
show
Lemma 2. With probability - 26, Algorithm ensures that Jr, 2 if EL
Using Lemma 2 we obtain the regret and violation bound for Algorithm in the following
Theorem 1. With probability 1 56, the regret and violation bounds are
Regret(T) (osp(t)) if the optimal policy n" E II.
Violation(T) s log(T//)
This is the first result which shows that Ö(VT) regret and violation is achievable for infinite horizon average reward linear CMDP under Assumption using model-free approach. Recently, Chen et al. (2022) obtained (VVT) regret and violation for model-based tabular setup for weakly communicating MDP. The proposed algorithm (Algorithm 4) in Chen et al. (2022) is also computationally inefficient. Chen et al. (2022) also requires the knowledge of sp(u)) for r-
For the unconstrained MDP, the lower bound of regret is ((vT) (proved for tabular setup, (Auer al., 2008)). Hence, the regret order optimal with respect T. We also show that it is possible to zero violation for large T under an additional set of Assumption (Remark 1).
5

---

Published as a conference paper at ICLR 2023
Algorithm 1 Model Free Fixed-point Algorithm for Long-term Average Reward and Constraint
1: Initialization: 3. 2d + sp(r.)) +pl for g.
2: for t= 1..... T
. do
3: if or det (At) 2 2As then
4: Set 8, =t.
5: Obtain Wo,t for r, 9 as the solution of the following optimization problem Pi:
max Wraw 0g 5e
Jra
Wo,t = (Ax) -1 " (r) Jo,t + vo,((Er+1)) + bz,e), - r,g (8)
Jn 2 b, (0,(2, = 6(x, Vo, = (Tt, to,); ne E
|Bo,,ll,, Bo: | (2 sp(v:))
6:
Take action ar ~ ())) and observe 2 Update Ac+1 = A₁ 6( ())(),))))) a.)"
7:
3.2
ALGORITHM BASED ON EPISODIC PRIMAL-DUA DUAL ALGORITHM
We now present another optimism ppased algorithm which can be implemented efficiently albeit with a sub-optimal regret and violation guarantee under the Slater's condition (Assumption 3)-
Assumption We assume the following, there exists n, ", qT, J.. and J such that (4) is satisfied; and J 2 b + y with > O.
The above assumption states that there exists stationary policy with strict feasibility. Striet feasibility assumption is common both in the infinite horizon average reward (Wei et al., 2022; Chen et al., 2022) and finite horizon episodic CMDP set up (Efroni al., 2020; Ding al., 2021). We only need to know rather than the strictly feasible policy.
In algorithm the inefficiency arises since we do not know how efficiently solve fixed- -oint-ponttt equation and find the policy to solve the optimization problem. We show that we eliminate the above inefficiencies by considering a finite-horizon problem. In particular, we divide the entire horizon T into T/ H episodes with H rounds and employ a finite-horizon primal dual optimistic LSVI-based algorithm proposed in Ghosh et al. (2022). However, since the original problem is still infinite horizon we need to bound the gap because of the finite-horizon truncation which we describe in the following.
3.2.1 OUR APPROACH
We replace the time index with the combination of the episode index i and the step index h. t= (k 1)H h. The k-thh episode starts at time (k- 1)H + The agent chooses the policy oh for the step h E [H] at episode & E [K]. Note that for finite-horizon setting, the policy needs not to be stationary even though the optimal policy for the infinite horizon problem stationary. As we mentioned, the idea is here to obtain policy with good performance guarantee in the episodic setup
and then bound gap between the infinite horizon and episodic setup.
We now introduce the notations specific to the episodic setting.
H Σ h=h
V (x) = Ex
o(, az = (z, = En
Σ imh
(z ai) = x, an = a
Note that since J 2 b, the natural choice of the constraint in the episodic CMDP would be VT 2 Hb. However, in order to compare the best policy in the episodic setup with the optimal policy in the infinite horizon setup we need to ensure that the optimal stationary policy for the infinite horizon problem is feasible in the episodic setup. If we have V 2 Hb sp(E;) that the optimal stationary policy x is also feasible for the episodic setup using the following lemma:
conclude
Lemma 3. If (s) = J for o = r,g, and any state s, stationary policy n, then
V.
(H h + 1)J5 spp(²))

---

Published as a conference paper at ICLR 2023
Further, in order to apply the primal-dual algorithm also need show that there exists a strictly feasible policy for the episodic setup. Again using Lemma 3 and from Assumption 3, we conclude that there exists strictly feasible policy for the episodic setup if V 2 Hb + sp(e Thus, 7).
consider the following constraint V Hb- where mmx maxxsp(()))spp()
Lagrangian: We consider the composite value function as V/= VT
(x)
V (x) + 2M
The following proved in Ding et al. (2021).
V (x1) - Vx1)
H
Lemma 4 (Boundedness of Y*). The optimal dual-variable Y*
S
H9
where R* is the optimal solution of the episodic CMDP.
Definition 2. We set { = 2/7y- & is used to truncate the dual variable.
3.2.2 ALGORITHM
We now describe our proposed Algorithm 2 (Appendix D). First, note that the finite-horizon state- action value function for linear MDP can be represented as the following linear form
Qº (2, a) ((r,))" wā = (n( + / (o. (x, a)
(10)
Hence, the natural estimates for the parameters w w h are obtained by solving the following regularized least square problem
A-1
Wohh <- arg min WERd T=1 R
ΣΣ
1o(a ( + V* "0.+1(007=1) - w MTTT,, o/)) + 1/1w112
(11)
(I, .) (w 6(x, + B10((z "))|a= where B1) ")][,;, is the bonus term. Since we are considering a horienh hence, we can recursively set Vo,h+1 starting from Vo = 0. Thus, we do not need solve the fixed-point equation unlike in Algorithm 1. Another difference with Algorithm is that we introduce a pointwise bonus term for optimism. Finally, we use a primal-dual adaptation unlike in Algorithm
The policy is based on the soft-max. In particular, at step h, Th, (a/xr is computed based on the soft-max policy on the composite Q-function vector 1Q*,, (I, a) + Y& 2. (z, a)}aAA where Ys is the lagrangian multiplier. The computation of policy also efficient unlike Algorithm not need to search over the policy space. Note that the greedy policy with respect to the composite Q-function vector fails to show that log e-covering number for the individual value function class is at most lTg(T) (Ghosh et al., 2022). Note that Ghosh et al. (2022) maintains different covariance matrices at each step h, A But we maintain a single A k for all h since the transition probability and reward are the same across the steps. The last part (Step 15) of Algorithm 2 includes dual-update step. The dual variable increases if the estimated utility value function does not satisfy the constraint.
we do
3.2.3 MAIN RESULTS
Theorem 2. Under Assumptions 2, and 3, with probability 1 58, the regret and constraint violations are
2(1 2)1+ ((1+)))31))))
Regret(T) < (ptt)
Violation(T)
where: log(log([4))522TT0))
Unlike in Theorem here, the optimal policy does not need to belong II. Wei et al. (2022) proved that the regret bound is (TT5/6) for the model-free RL algorithm in the tabular regime under much stronger Assumption compared to ours. Since linear CMDP contains a tabular setup, our approach improves the upper bound for the tabular case as well. We show that it is possible to achieve zero violation while maintaining the same order on regret under an additional Assumption (Remark I).
Note that the regret is also ((dT)3/44 for the unconstrained linear MDP (Wei et al., 2021a) for the efficient implementation variant of the algorithm.
7

---

Published as a conference paper at ICLR 2023
Analysis: The overall regret can be decomposed in
T/H Regret(T) (HJ, -HJ (+)))); (x1)) Σ
T/H
TуH Σ (v.
KH
Σ (1-1)
r( az))
1=
The third term on the right-hand side can be bounded using the azuma-HHoffdiae inequality. Hence, focus the first two terms of the right- side. The second part is exactly the same the regret for the episodic scenario. However, there is subile difference. We need to show that optimal policy for the original infinite horizon is also feasible (see Appendix G.1) which we show using the fact that we have relaxed the constraint by K. We show that the above is upper bounded by Ó( D(vdTH')) H²). Note that compared to Ghosh et al. (2022), we have vH improvement as our case the transition probability is independent of the time h unlike in Ghosh et al. (2022).
One may wonder why not set the length H too small. However, since our original problem is about average-reward over infinite horizon, need to argue that the best smite-horizon policy also performs well under the infinite-horizon criteria. The first term characterizes the gap. We show that the sub-optimality gap to the best finite horizon policy is bounded by Tsp(u?)) H using Lemma 3. Hence, if we set too small H, the gap would increase. By setting H T /d we balance the upper bounds on the first two terms of the right-hand side. As increases, H also increases.
Constraint Violation: The violation term also be decomposed as follows
T/H
kH Σ
Violation(T) (
+ (x -
g(., az)) + (T/H)R
k=1
((K-1))++
We obtain the upper bound of the first term as ((V@HHT)) The second term can be bounded by Azuma-Hoeffiee inequality. The third term denotes the error incurred due to the introduction of k. We obtain the final constraint violation bound by replacing H with T1/1 /1/1//3/1.
4 POLICY-BASED ALGORITHM
Even though Algorithm 2 is computationally efficient, still one needs to compute Vk Vh, for every encountered state and needs to evaluate (Ag)-1, We now show that it possible to achieve ((VT) regret and constraint violation under a different and relaxed set of assumptions using computationally less intensive algorithm. We propose a policy-base algorithm towards this end. First, we state the assumptions and then we describe the algorithm and the results.
Assumption 4. There exists constant tmix 2 such that for any policy and any distribution 1,,1/ E Ax over the state-space ||PTM - pP*vallrVS e -1/mmin [|p - 12 where v(x' E. ((al (x),(x:), TV is the total variation distance.
Ergodic MDP satisfies the above assumption Hao et al. (2021). With the above assumption, we can conclude the following, as shown the unconstrained setup (Wei et al., 2021a)).
Lemma 5. Under Assumption 4, any stationary policy æ satisfies (4).
Hence, under Assumption 4, the gain is constant, and any stationary policy indeed satisfies (4). Assumption 5. Let Amin (-) be minimum eigen value of a matrix. There exists a such that for any π,, Amin (E, (all))á(z, a)o(I, ())))((>())))))))))))))))))
The assumption intuitively guarantees that every policy is explorative in the feature space. similar assumptions are also made (Wei et al., 2021a: a; Abbasi- Yadkori et al., 2019) in the unconstrained case. Similar to Wei et al. (2021a) we can relax this assumption to the setting where the above holds for one known policy instead all policies.
Lagrangian: J YJ is the Lagrangian for the stationary policy where Y is the dual variable.
Under Assumption 3, optimal dual-variable Y J (a1) - (x11) < < 8/2.
7
8

---

Published as a conference paper at ICLR 2023
4.1 ALGORITHM
We consider a primal-dual adaptation of MDP-EXP2 in Algorithm 3 (Appendix E). The algorithm proceeds in epochs where each epoch consists of B = (dlmiiz /)) steps. Within each epoch, we collect B/ B/2N trajectories where N = (fmiaa) The update of policy T for k-th epoch is equivalent the online mirror descent (OMD), i.e.,
(-I-) arg max(TT, (T, 9, (., 1 19
- (., ( D(=
1
(12)
where (x. (w--1) a). We consider a composite q- q-function which is the sum of the dr and Og (scaled by the dual- varialvariable). We estimate w from sample average reward Rg,m and sample average utility Gk.m by utilizing Lemma 5 and the fact that g5 is linear in feature space.
Since we consider primal-dual adaptation of MDP-EXP2 Wei et al. (2021a), we maintain two different types of sample averages for the utility. Gk.m is used to estimate g3e + J, on the other hand, jR is used to estimate J The dual update is based on the value of jR. Naturally the analysis also differs significantly (see Appendix H.1).
4.2 MAIN RESULTS
Theorem 3. Under Assumptions 2, 4,5, and 3, Algorithm 2 ensures that with probability 1 46,
Regret (T) s (1 + ()0(/// G C..T. T), Violation(T) S E) 0(1//
13 P)
(13)
E
Wei et al. (2021a) shows that (VVT) regret is achieved in the expectation under Assumptions 4, and in the unconstrained setup. We show that even with a high probability, such a regret can be achieved along with (V)T) of violation. Assumption can be relaxed to the scenarios where q.t is linear (even though the underlying MDP is not linear) similar to unconstrained setup (Assumption 4 in Wei et al. (2021a)). Hence, Ö(VT) regret and violation can be achieved for any linear q" even if the underlying MDP is not linear. In the model-based tabular CMDP, Chen et al. (2022) shows that the regret also scales with ((VT) in the ergodic MDP. Also note that the regret scales with fmir and g there as well (order of tmiz is worst there). Note that the dependence
is implicit as 1/a (2d)..
We need to know Emiz. and a in Algorithm 3. Similar to the unconstrained setup Wei et al. (2021a), we can modify our algorithm to incorporate unknown tmiz and with slightly worsened regret.
Remark 1. We can reduce the violation to 0 with sacrificing the regret a little bit (the order the same) under the Assumptions in Section 4 (Appendix H.5). The idea is the following, we consider a tighter optimization problem where we add
the right-hand side of the constraint (2). We
then bound the difference of the optimal gains in the tighter problem and the original problem function of e. The bound on regret and violation can allained following our analysis for the lighter optimization problem since it is CMDP with b + in place of b. Hence, by carefully choosing e, can show that it is strictly feasible, and achieves zero violation for large enough T (Lemma 36).
For the assumption in Section 3.2 and Section 3.1, need additional assumption (any stationary policy satisfies Bellman's 's equation (cf.(4)) to obtain zero constraint violation (Appendix H.5). The idea is similar to the one described in earlier paragraph. The additional assumption would help us to bound the difference between the tighter and the original problem.
5 EXPERIMENTAL RESULTS
We conduct numerical experiments validate our theory on an environment similar to Chen et al. (2022). We implement Algorithm 3 and observe that regret and violation indeed grow sub-linearly even without the knowledge of tmiz, and a. Please see Appendix I for details.
6 CONCLUSION AND FUTURE WORK
In this work, we provide model-free RL algorithms under two different sets of Assumptions. To the best of our knowledge, ours is the first work on the average reward-constrained linear MDP. Our results improve the regret and violation bound even for the finite horizon tabular model-free constrained RL setup. Whether optimal regret under Assumption 1 constitutes a future research question. Whether we can extend the analysis to the non-linear function approximation is also an open question.
develop computationally efficient algorithm that achieves

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work has been partly supported by NSF grants NSF AI Institute (AI-EDGE) 2112471, CNS- 2106933, 2007231, CNS-1955535, and CNS-1901057, and in part by Army Research Office under Grant W91 1011-11-1-1-222
Xingyu Zhou is supported in part by NSF CNS-2153220.
REFERENCES
Arob Ghosh, Xingyu Zhou, and Ness Shroff. Provably efficient model-free constrained rl with linear function approximation. arXiv preprint arXiv:2206. 1 1889, 2022.
Chen-Yu Wei, Mchdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free reinforcement learning in infinite-horizon average-reward markov decision processes. In International conference on machine learning, pages 10170-10180. PMLR, 2020.
Liyu Chen, Rahul Jain, and Haipeng Luo. Learning infinite-horizon average-reward markov decision processes with constraints. arXiv preprint arXiv:2202.00115, 2022.
Honghao Wei, Xin Liu, and Lei Ying. A provably-efficient model-free algorithm for infinite- horizon average-reward constrained markov decision processes. In AAAI Conference Artificial Intelligence, 2022.
Chen- Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, and Rahul Jain. Learning infinite-horizon average-reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statisties, pages 3007-3015. PMLR, 2021a.
Onésimo Srrnández-Lermer Adaptive Markov control processes, volume 79. Springer Science & Business Media, 2012.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John
Wiley & Sons, 2014.
Peter L Bartlett and Ambuj Tewari. Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps. arXiv preprint
2012.
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. International Conference on Artificial Intelligence and Statistics, pages 3304-3312. PMLR, 2021.
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.
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. International Conference on Machine Leurning, pages 12793- 12802. PMLR, 2021.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitation in constrained mdps. arXiv preprint arXhv:2003.02/89, 2020.
Botao Hao, Nevena Lazic, Yasin Abbasi- Yadkori, Pooria Joulani, and Csaba Szepesvari. Adaptive approximate policy iteration. In International Conference Artificial Intelligence and Statistics, pages 523-531. PMLR, 2021.
Yasin Abbasi- Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. International Conference Machine Learning, pages 3692-3702. PML.R, 2019.
10

---

Published as a conference paper at ICLR 2023
Tengyu Xu, Yingbin Liang, and Guanghui Lan. Cipo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pages 11480- 1100-11490 1491. PMLR, 2021.
Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo R Jovanovie. Natural policy gradient primal-dual method for constrained markov decision processes. In NeurIPS, 2020.
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
2021.
Sven Koenig and Reid G Simmons. Complexity analysis of real-time reinforcement learning. In AAAI, pages 99-107, 1993.
Mohammad Gheshlaghi Azar, Rémi Munos, and Bert Kappen. On the sample complexity of reinforcement learning with a generative model. arXiv preprint arXiv:1206. 6461, 2012.
Honghao Wei, Xin Liu, and Lei Ying. provably-efficient model-free algorithm for constrained markov decision processes. arXiv preprint arXiv:2106001577, 2021b.
Kianté Brantley, Miroslav Dudik, Thodoris Lykouris, Sobhan Miryoosefi, Max Simehowitz, Aleksan- drs Slivkins, and Wen Sun. Constrained episodic reinforcement learning in concave-convex and knapsack settings. arXiv preprint wwXiv:2006.05051, 2020.
Krishna C Kalagarla, Rahul Jain, and Pierluigi Nuzzo. A sample-efficient algorithm for episodic finite-horizon mdp with constraints. arXiv preprint arXiv:2009. 1 1348, 2020.
Tao Liu, Ruida Zhou, Dileep Kalathil, PR Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. arXiv preprint AXiv:2206.00684, 2021.
Liyuan Zheng and Lillian Ratliff. Constrained upper confidence reinforcement learning. Learning for Dynamics and Control, pages 629. PMLR, 2020.
Rahul Singh, Abhishek Gupta, and Ness B Shroff. Learning in markov decision processes under constraints. arXiv preprint arXiv:2002.12435, 2020.
Ling Pan, Qingpeng Cai, Qi Meng, Wei Chen, Longbo Huang, and Tie-Yan Liu. Reinforcement learning with dynamic boltzmann softmax updates. arXiv preprint vrXiv:/903.0533 2019.
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-22 2320,, 2011.
Roman Vershynin. Introduction to the non-asymptotic analysis arXiv:1011.3027, 2010.
of random matrices. arXiv preprint
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- tion. In International Conference on Machine Learning, pages 1283-1294. PMLR, 2020.
Eitan Altman. Constrained Markov decision processes: stochastic modeling. Routledge, 1999.

---

Published as a conference paper at ICLR 2023
Organization of Appendix We provide related work in Appendix A. In Appendix B, we provide some motivating examples. We summarize our results in Appendix under various sets of Assumptions. We describe Algorithm 2 in Appendix D. We formally describe Algorithm 3 in Appendix E. We prove the results of Section 3.1 in Appendix F. We prove the results of Section 3.2 in Appendix G. We prove the results of Section 4 in Appendix H. We show how Algorithm 3 can achieve violation while maintaining the same order on the regret bound (with respect to I') in Appendix H.5. In Appendix H.5 also show how Algorithms I and 2 achieve zero violation while maintaining the same order on regret (with respect to T) with an additional assumption. We show numerical experiments in Appendix
constraint
12

---

Published as a conference paper at ICLR 2023
A RELATED WORK
Model-free RL algorithms have been proposed (Xu et al., 2021; Ding et al., 2020; Bai et al., 2021) to solve CMDP in the discounted infinite horizon setting. All of these works consider an easier setting compared to standard RL in that they assume access to simulator (Koenig and Simmons, 1993) (a.k.a. a generative model (Azar et al., 2012)), which a strong oracle that allows the agent to query arbitrary actennctionn pairs and return the reward and the next state, hence greatly alleviating the intrinsic difficulty of exploration in RL. Wei et al. (2021b) proposed a 'triple-QU Q' algorithm that does not require a 'simulator'. However, it only considered the tabular setting and the episodic set-up.
To develop online sample-efficient algorithms for CMDPs, prior works have largely resorted to the finite horizon setup (Efroni et al., 2020; Brantley al., 2020; Kalagarla et al., 2020; Liu et al., 2021). Model-based RL in the episodic linear kernel CMDP is considered in Ding et al. (2021). Model-based infinite horizon average reward CMDP for tabular setup is also considered in Zheng and Ratliff (2020); Singh et al. (2020).
B MOTIVATING EXAMPLES
First, we provide examples of constrained MDP.
Consider an intelligent agent taking an action to optimize the power consumption for household. It would seek to minimize the overall cost while trying maintain a minimum level of satisfaction (e.g.. maintaining a certain temp., maintaining the charge of the electric vehicles). Here the reward can be cast as the negative of the cost for power consumption, while utility can be modeled as the satisfaction the user gets.
As another example, consider a sensor network where sensor nodes sample and send information to server (fusion center) for processing. However, these sensor nodes also need to satisfy the energy constraint as they have limited battery capacity. Such a decision process can be modeled as CMDP where (i) the reward depends the nature of the information and whether the information is successfully received or not and (ii) the cost corresponds to the cost for sampling and transmitting information.
We now provide some examples of CMDP that might run for long-time where the average reward CMDP would be the ideal candidate for modeling.
Consider the sensor network example provided earlier. Here, the sensor node continually takes decisions, and thus, an infinite horizon average reward CMDP is natural choice.
As another example, consider that a server is scheduling jobs to different machines. The scheduler seeks to minimize the job completion time. The server wants to maintain a uniform queue length (i.e, the number of jobs waiting to be processed) across the machines which can only process jobs sequentially. The server is continually taking decisions, thus, it is maximizing the average reward while maintaining an average queue length below a certain threshold. This can be cast as the average reward CMDP. Another example is controller in autonomous system that takes a decision in order to maximize the average reward (objective) while trying to maintain system stability. We can model the system as average reward CMDP where there is utility of if the system remains in the safe region at every step. The goal of the controller is to maximize the average reward while the system will be in one of the safe states for at least e fraction of times for the desired choice of > 0. This can be cast as average reward CMDP where the controller seeks to maximize the average reward while the average utility is at least
Finally, we argue why choose the function approximation setup. In many examples, provided above, the state space is continuous or at least very large. For example, the state of the battery for a sensor is continuous. Similarly, the length of the queue generally used to approximate the Q-function or policy in such a large state space. We consider linear function approximation in our setup as first step handle the large state space.
be very large. Function approximation is
13

---

Published as a conference paper at ICLR 2023
C
SUMMARY OF OUR RESULTS IN A TABLE
We summarize our results in Table 1.
Table 1: Regret and Constraint Violations on Linear MDP for our proposed algorithms
ALGORITHM
REGRET
VIOLATIONS
ASSUMPTIONS
ALGORRITM 1
Ö(VæT) OldaTyiit O(VT)
olvd (ldTys/1) Ó(VT)*
ASSUMPTION ASSUMPTIONS 1, AND 3
ALGORITHM 2
3LGORITHM
ASSUMPTIONS 3,4, AND
WE CAN REDUCE THE VIOLATION TO FOR LARGE ENOUGH T (AP- PENDIX H.5) WHILE MAINTAINING THE SAME ORDER OF REGRET WITH RESPECT TO T'
WE CAN REDUCE THE VIOLATION TO FOR ALGORITHMS AND 2 IF WE ASSUME
STATIONARY SATISFIES (4) (APPENDIX H.5).
D ALGORITHM 2
Here, we state Algorithm 2.
Algorithm 2 Model Free Primal-Dual Algorithm for Long-term Average Reward and Constraint
T
log((A))VKH
1: Initialization: Y1 = O, Wo,h 0, H
K T/H,
d3/4
2(1 + H)
E/VKH2, B dH v log(2 (2 log Al
2: for episodes = 1,..., K do
3: Receive the initial state af
4: A + k- --> Σn (x az) (o)T) aF) + AI
5: for step h H,
do
6:
wH,n (A*) f W= 6 o ()((( Vk 7 (x
H
7:
with t (At)- k-
+ "((, +
8:
Ch +- minf min
H)
Q (g,l)))) -- min(( (w n. o(, -N
9:
exp(a((R a) + (+)
10:
(al.(a).)) Ea @ (..0) YuQ (x (:,))
11:
VAL (-) = --)== En (a (,a), a). ()) = =. (al))aa)))))
12:
for step h = I..... H do
Compute Q 1h (af a). Qh (ot a). 7 (a)=)) for all a.
14:
Take action af The T (- and observe aht-1
15:
Yk+1 max/min (Yn + rb (x+)), E).0}
E ALGORITHM 3
Here, we describe Algorithm 3.
F PROOF OF THE RESULT OF SECTION 3.1
Without loss of generality, we assume that the first element o(.,)) is Hence Φ(, (( e = 1 where eq is d-dimensional vector where the first element is and the rest are
Notations:
0. Also recall that ||wš|| vd(2 sp(u?)) from Lemma 1. As shown in Wei et al. (2021a)
14

---

Published as a conference paper at ICLR 2023
Algorithm 3 Model Free Primal-Dual Algorithm for Long-term Average Reward in Linear MDP
1: Initialization: Y1 = 0, Stmiz log(()) Wo.1 0, B 32.N (log(d))))) a min(1/(1- T (244N + E))). n= E/
2: for epochs 1, ..... T/B do
3: Define the policy T& (alxx) such that (a(az) exp aa Wh, + Yyww,s)) and
initialize count Jg. Execute TT. in the entire epoch.
4:
5:
for (k: 1) 1, ,,............ kB do
6:
Execute ( [ observes, (r az), (x at), and Ø++1-
7:
it (k B)B +
then
8:
Sum the constraint JR = Js + g(z,,
9:
for step m 1..... B/2N do
10:
Define
m = (k: - 1)B 2N (m +1
as the start of the m-th trajectory.
11: Compute
Tk
R
Σ
r(zs, oz)
Tk
Them + N-1
Gk.
Σ
g(1,,
L=
12:
Compute
B/2N
M Σ
Σ
T(a Tre )ob(Ire ara. (T ATy.
Amii (Mx) 2 Ba (24(2 then
14:
Wr.k
M₁
Σ m=1 6 Or R
BB/2N
15:
Wgik = M₁
EB/2 ((ITE, aTH Gk.m
B/2N
16:
else
17:
Wr.k, Wg.k = O.
18:
J& = JB N)
19:
YE+1 max + n Je).E).0}
have sup_lu5(z)(5 {sp(e)) without loss of generality. Without loss of generality, we assume ((((,,))l22 /2 for all (z, a) E S A, (| Vd, 10, Vd for r.g.
F.I PROOF-SKETCH OF THEOREM
Note from (3) that for r,g
Σ(J ax))))))) = Eloo 10 (14)
We then show that Lemma 6. With probability 6,
T
T
Σ Emnootr a.) - (1t, ())= < " - Ja,,)) )
+ Σ
Fe (Va.o - v)
[=1
0(3o V log(T))
(15)
15

---

Published as a conference paper at ICLR 2023
where is the last time the optimization problem is solved before time t. Ussoorbsio War Tac) are the solutions which also specify aa,,o and Ee,,o-
The key step in proving the above lemma is that need to show
b(or; Oz) (1s,s(((aa)) - Exg ue
(16)
upper bounded by Olog I' with high probability. To this end, value-aware uniform concentration required to handle the dependence between va and samples { fk=1 which renders the standard self-normalized inequality infeasible in the model-free setting. The general idea here is to fix function class Vo in advance and then show that each possible value function in our algorithm ea is within this class which has polynomial log e-covering number.
The idea is to show that the function class Qa has log covering number which is at most Old loglo1(1 sp() (Lemma 7). Now, using the smoothness property of soft-max, policy class also has log e-covering number which is at most d log(1 + 16L/e). Combining the above compute the e-covering number for the class V. and show that (16) upper bounded by log(T)) with high probability. The detailed proof is in Lemma 7.
also show that the
Now, we divide the proof of Theorem two parts. First, we bound the regret and subsequently, we bound the violation.
Proof of Regret: From Lemma with probability 1 28, w wy Jg J T feasible solution for the optimization problem. Since we are maximizing Jr, thus, Jo.. 2 J with probability 1 25. Further, from Lemma 6 with probability 1 5,
Σ Conr( - of (It, ar) s D(; Jerr)
E
(x
+ +0Brv dT (oToo(T)
Hence, from union bound, with probability 35.
E (1t, - of (2), S
E (1) -/ + +1 (17)
By rearranging
T
[B p' p( mn a.) (x))) (Ic, az))
( (l (... Qu + log
T Σ (Eal (oir Ue, (x))) Σ +0 log T)
We define Fi, as the o-algebra generated by [(I, a, ) U 21+1- Then, Eiv,, (I.)) Is,,0 az) Fr-1] = O. Thus, (x2) ( 04) Martingale difference. Since | ||s vd(2 sp(et)) (from the optimization problem in Algorithm 1), hence, (2r) - ( ae) is upper bounded by T with probability 1 8. Thus, from union bound, with probability 1 45, have
T
E Ap (0, - q.t (Iz, az))
E a m (a) (2a. (x)r( 0 (
(18)
16

---

Published as a conference paper at ICLR 2023
Notice that every time the algorithm updates (i.e., 8t + st-1) it holds that det(A,) det((As:)
2
2det(A,,,)) ). Since det(Ar+1)/det(a & (1+T/A) thus, can not happen more than d logg T) O(d times. Thus, with probability - 46,
T
E Apt po (oa (xe, az))
[ (on
(s ((3.VaTToo((T//) 3,d T) (19)
The first term in the right-hand side of (19) can be bounded by ((sp(r;)) loggo///))) with probability 1 - 8 by Azuma-Hoeffding inequality. Hence, with probability 1 56,
T Ee Be (e of ax))
(B di (T/0) Bog T),
Azuma-Hoeffdinn where the last step holds via Azuma- Hoeffdiig inequality.
Hence, the result follows from the definition of 3,, and (14).
Proof of Constraint Violation: From Lemma 6 with probability 8.
En az) 9g (rt, 04)
T s 0(3 log Σ (J' Jmng)
T
E (e =g'('))
Similar to (19) we obtain with probability 1 1-30 36
[E (2ar=))())) 2 (Ie, an)
00, v dI log (og(To0) B
(Jg Jaca)
(20)
Hence, rearranging (20) and from (14), we obtain
T - Jena) 500 di logT + Bydlog
Σ (J - o()),
Σ JJ.. g(z,, a()) < OB3, / log((T)))) + Byd
(21)
Note that not conclude that J 2 J unlike the reward term. Nevertheless, since Ja. is feasible, thus, from the optimization problem P, Algorithm 1, we have Ja..9 2 b. Hence, from (21) with probability 1 36,
T a())
T (Jang g(ø,, a.)) S0 (TT + 8ydlog(T/8))
Σ (b - g(() a:)) S
Σ 1=1
1=1
Hence, the result follows.
17

---

Published as a conference paper at ICLR 2023
F.2
PROOF OF LEMMA 2
For T.
w (At)
Σ (.),; (+) A
4-
=
Σ
0( ar
+ aa, + AA,'W5 w
= (Ad Σ
p ar (r) Jo + (0((++1)) + Ad
w + Cooe
(22)
where
6-1
E1,o = (Aa)
Σ
p a,
- (xr++))
(23)
Let us denote 7,, Ex .a,) 2i (x") 2. (x++1) which is Martingale difference, then from the self-concentration result with probability
25 (Theorem 4),
G. S sp(o5) log
(24)
8
Now, det(A,) S (A+ t). det(An) 2 1d. Thus,
G. sp(())) v dlog((1 + T)/5)
(25)
On the other hand, note that X(A,)- w6,t S Bo/2, hence, by selecting bo.t X(A,) " + Eot (which is upper bounded by 3o) and J 2 b we have the result.
F.3 PROOF OF LEMMA 6
Proof. For notational simplicity, we denote s = 8.
From the definition of Wg,0
Ws.0 w = -.-
o(x a.)(((r))( - Jao + (2,((I+11)) b
A-1 Σ p(x,, ar (o(o,, J + E 1e A
A, Σ
cb a+ ( -Jao +
ug (2(1))
+ 6,,0 + tb, AA.'w3
where 6,0 is defined in (23).
Wao0 w A-1
Σ (r) ar)
ar) (Jãel - Jaoel + / (Vaolx') (o,o2)))(((=')dda)
+ 60 0u AA-'wo
J Ja + ( (Vaolo") - ((((())dp((') + 6,,0 du
- -AA- Jooel + (Uaola') - (3 1A=
(26)
Therefore,
18

---

Published as a conference paper at ICLR 2023
(0 (1) 2o (2, a.) ((z,, az) (w - w()
I (Jo - J2 + Bul-pp-lla (u (2,, - v3(x')] + p(x,, ar) (cs,0 + 0u, + AA Up,0) (27)
where
u,o = -J - Js,001 / (vs.o(t)) -c((2')dd((()) - W
(28)
We now bound the third term in the right hand side which will prove the lemma. From Lemma 21 with probability 8
||e,,ollA,=
ereor ||,21 sp(u))) d/2 d/2log((s A)/A) + log(No,o
+ 84482/22
(29)
We now compute Ne,o which is the e-covering number for the value function class va,0-
Lemma 7. The e-covering number for the class Vo = foolus(() = (m(+)2), go a is upper bounded by
2(2 + sp(::)))
+ dlog 1+
167.
log No, I dloog 1+
(30)
where è'
1+ (2 sp sp(:)) π E II and go(+))) w o(.,)), where l1wolls (2 + sp(r:)) Vd
Proof. Proof is in Appendix F.4.
Hence, from (29) and putting T we obtain
|| 0(3))
(31)
with probability at least - 8. Now,
|AA U,,olla,- A|uuaoll villus,o 1l 0(1+ ()(()))))) - 0(8)) lbb,,olA. Bo.
(32)
Further,
Hence,
(x,,, (Eap + bao + A I || a,)l, -/,,, + t,, + AA, A uslolla,
2||0(10, ar) u.) Iles,o + bs.o + AA, "llolla,
Thus,
Σ (gn,(1r; (0(2), < Σ - + Σ
E (o) (x'))
1=1
t=1
+ 0 >
$ Σ
(JO Jacoo) + Σ
Ex Ber - (x()))
1=1
T
+0
Bo BO
Σ
11bt ac) 1
T
< Σ
(J Jo +
Σ
E
B (oon) - (x()))
1=1
+ O(B / /T <T T)
(33)
19

---

Published as a conference paper at ICLR 2023
where the second inequality follows from Cauchy-Schwarz inequality. The last inequal- ity follows from the fact that v / V S (2bg((de(AA and
lo)(det(Ar+t)) & d d'lo(A+ + 7)
F.4 PROOF OF LEMMA 7
Proof.
||o (2 sp(et))vd By Lemma 22, the covering number for Ws is
2(2 sp(u:))
(1+
Since (s.o::-) = ((.,))Tw, and | v2, e-covering number for ws,o is also the e-covering number for the class of state-action bias functions ys,o is
++ 2(2 sp(ug)) ( 2d
(34)
with respect to co-norm.
For the policy-pane pallee-paramttereeeee class, note that || L. Hence, the e-covering number for the parameter class is (1 + 2L/e)/ from Lemma 22. We also use the following result where we show that the
1-norm of the difference between two policies is close if the parameters close from the property of soft-max.
Lemma 8. n II where a is parameterized by Ç and it is parameterized by č, then for any EX
Σ m[aa)) #<a|)))s 8|1C č1I
(35)
iflls Ł115 1/2.
Proof. See Appendix F.5.
The value function class vsoo is parameterized by (S, w.oo). Consider Č such that || [55-c11- <|l e/8, then from Lemma 8 for every state
> ( - -((al))s
(36)
Further, consider w..o such that ||,,, w.ools then 10, (2, a)15 where Ze is parameterized by w. Now, Ua.0 (it, Z,,0), and Us,0 = (T.
Then, for any
(x,0(x) (2) (ग, (1.0) ) (TT, qa,0)
(T - 7, qo,o) {5, (ā=.0 (,,o))
(2 sp(u:)) )) 2d +
(37)
Thus, consider é'
1+ (2 + sp sp(r))) then,
log No. 5 dlog 1+ 2(2 2 sp(p;)) 22d
+ dlog (1+16)) 167
(38)
e'
20

---

Published as a conference paper at ICLR 2023
F.5
PROOF OF LEMMA 8
Proof. Dividing (a) by 7t (a)rr) yields
aT (a(a) < eloln,a),5)
e(d(n,)).))
a elolz,a))
x
Ea e(o((,a))s)
e(d(r,a)).))
=(
(elolaa') ())
x a'
En e(((2,0).5)
Σ =elo(aa)
x((a (
(39)
Since | and exponential is strictly increasing function, thus,
Taax) 7(a|z)
ells- šll Σ [aa'lz)) v 2 < 1++ 4|ls -īll
(40)
where the first inequality stems from the fact that Ex T(al(x)) = 1. The second inequality stems from the fact that e I +++ + 2x if (0, 0.5). Hence,
x <a]x) #(al=) ( Eil
(41)
We can apply the similar argument with the roles ( and & reversed to conclude
#(a|z) <<al²) = 4T(0/=)]ls čil
(42)
Hence,
Σ [aaa=) -((]=))((a[>) s 4||s Σ max(m(al2)) +()x))
4||s xll> Σ
(अ(a|z) + #((x))
8||s čil
(43)
F.6 CLASS OF POLICIES
Note that we only use Lemma 8 to show Lemma for the class bias value function. Thus, our analysis can be extended any policy parameterized by such that
Definition 3. For any x, En. (m( - F<a|))|< R|ІÇ - čII holds for some ||5- - La where R
constant and Lı 0.
Obviously, soft-max policy is such policy which satisfies the condition of the Definition 3.
G PROOF OF THE RESULTS OF SECTION 3.2
Organization: In Appendix G.I, we provide the proof sketch and subsequently we prove various parts in Appendix E.2 to Appendix E.9. We formally prove Theorem in Appendix G.10.
Notations for this Section: Throughout this section, we denote Q 2 who w A as the Q-
value and the parameter values estimated at the episode k. Vith (-) (TT, (+l-), 2j, (.)))) (+a))-)) the soft-max policy based on the composite Q-function at the k-th episode as Q YuQu g.h. To simplify the presentation, we denote of: = 0(z%f a.).
Without loss of generality, we assume ||œ(z, 2) for all (z,a) e S x A. 1|A(S) Vd. |00|||5 Vdl for r,g-
21

---

Published as a conference paper at ICLR 2023
G.1 PROOF SKETCH OF THEOREM 2
We reiterate the decomposition of regret.
T/H
(T)
Σ [H - V + Σ (K v.
k=1
R=
T/H
kH
Σ (v+)
Σ r(z,,
(44)
1)--1)
The first term is bounded via Lemma 3 by (T)H)sp((;) which we prove in Appendix G.3. The third-term is bounded using Lzuma-Hoeffding inequality, and its upper bound is given by O(vTH)) with probability 1 - 8. We bound the second term in Appendices G.4-G.8. In the following, we describe rough idea to bound the second term.
Note that order to bound the second term we follow Ghosh et al. (2022) which bounds the regret over episodic setup. However, there are subtle differences. Ghosh et al. (2022) bounds the regret with respect to the optimal solution for the episodic case, i.e., Ghosh et al. (2022) bounds the following
K
(2 V (af))
where मt is the optimal solution for the episodic case (cf.(46)). Instead, we are interested bounding E(vi (xf) - V7 (af))
Note that the optimal solution for episodic case, #", can be different from n", the optimal solution for the infinite horizon average reward CMDP. Since we relax the constraint by subtracting k. from Hb. it would guarantee that is also feasible over the episodic case for any initial state x by Lemma 3. Hence,
V (x+) V= (af) 2
Thus,
Eori -VT S (ai
(45)
Now, we invoke the analysis of Ghosh et al. (2022) to bound the right-hane side of (45).
Since we relax the constraint there will be an additional term k in the violation at each episode. By summing over all the episodes the term will grow as (T/H)R. Since H O(T1/4) we can bound that additional term by (TT/44).
Now, we bound the right-hand side of (45). We first state the episodic CMDP on which the Algorithm is learning for completeness.
maximize , V. (z+1) subject to V3,n (xf) 2 Hb- K
(46)
Similar to Ghosh al. (2022), we first establish the following decomposition, which upper bounds the sum of regret and violation (Lemma 9).
Lemma 9. For any Y E [), we have
K
nH²K
(V. (++)
(24)) K- (x+)) - 22 +
2n
2
Vi (af) Yo YoV (=+))
(v- Yav. 9.1 (att) +
K
K Σ
(v (vti(at) -V (x
Vk (at) - V (a+
(47)
T5
22

---

Published as a conference paper at ICLR 2023
Proof. See Appendix G.4.
This will serve as the basis when applying optimization tools to bound the violation as well. Note that by making Y O, we can bound the regret.
Note that 7i 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 Yx. 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 r7, we are only left to bound Ti and T2, respectively.
In order to bound Ti and T2, we use the following result Lemma 10. There exists a constant C2 such that for any fixed E (0, 1), if we let & be the event that
k-1
H
Σ
Σ
J.
PVV PV (1 (hr)]
S SC2HH
(48)
(AR)-1
for all j E (r.g), x log[2(C1 + log([A))dTT/ for some constant C2, then Pr(E)
28.
Proof. Please see the proof of Lemma 8 in Ghosh et al. (2022).
The above lemma entails that for all (k, h) E [K] x [H] with high probability
Σ
Σ pl and (oLN+1(()442) - PV (17 a
h
(AR)-1
is upper bounded by lower order term (c.g., OddloogT) Similar to Algorithm I the general idea here is to fix a function class Vo,h advance and then show that each possible value function in our algorithm V is within this class which has log-covering number which scales with log
Similar to Ghosh et al. (2022) we introduce soft-max policy and define the following corresponding function classes to show that the value function class has log e-covering number which scales with log We first define the following class for Q-function for o = r.g. Qo = (Qo1Qo(.))
min((w., (6., -)) + ( -I J, H}. Then, we define the following value function x (al-)Qo( (- a): Qo E Co. E I1,), where II, is given by the following class II. [T]) SOFT-MAX: ((Qr(,)) +Yo (((((:)))) )); Va E A, Qr
class Vo V. = (VolV(())
Qr,Q, y. Y [), As described in Ghosh et al. (2022) greedy algorithm with respect to the composite Q-function fails to show that the log e-covering number for individual Vo scales most (llg((T)
as the greedy policy is not Lipschitz.
Using the above we show the following
Lemma 11. There exists an absolute constant 3 = C,dHH VL, t= log(log([A1)<2d1]] /8), and for any fixed policy n, on the event defined Lemma 10, we have
(δ(x, a), wh,n) n.) - (2,n a) PlV - VoL (o,, a) + A (x,
(49)
for some ( a) that satisfies ( a)ls (
Proof. See Appendix G.5.
The above lemma bounds the difference between the value function maintained in Algorithm 2 (without the bonus term) and the value function for any policy for both the reward and utility value functions. We bound this using the expected difference the next step plus error term. The result shows that this error term can be upper bounded by the bonus term with a high- highbbbobability.
Using the above, can easily show the following- Lemma 12. With prob. 28, (for the event in E)
(x, + ViQU (x, a) S 0% (2, + VeQ + P(V V/+
(50)
23

---

Published as a conference paper at ICLR 2023
Proof. See Appendix G.6.
Using the above, and the property of the soft-max (Lemma 19), obtain
Lemma 13. With probability 1 -2, Ti S H log([AA)
Proof. See Appendix G.7.
Further, from Lemma 12, obtain the following
Lemma 14. On the event defined in & in Lemma 10, we have
Vol (x1) Vo.1 (x1)
(D h, a + D Do,n,2
at "0(0 at)
(51)
A=1
h=1
where
De,,, ((00, 2oth (2hhs xx,((112))) - (Q0,( (2))
D o.h,2 PA (Vor, 0,h41 V ( at) IV VTh Voth (
(52)
Proof. See Appendix G.8.
Using the above result, Azuma-Hoeflding inequality, and plugging the value of obtain the following Lemma 15. With probability 1 46, T2 $ (1+1)0[(8TTH))
Proof. See Appendix G.9.
Combining all the pieces: In (47), we replace Y with 0, and vj = = Lem),Lemmas 13 and 15 bound the second term in (44) with probability 1 -5. Thus, the final result follows from the union bound ( (pppendix G.10).
E/VKH2 Then, by combining
Constraint Violation: The violation can be decomposed the following
K
K (V
kH Σ
Hb - K V (x4))
(x) +
Σ K
(53)
((--1)H++
where K = T/H. Note that the third term equivalent to (T/H)s. The second term can be bounded
by Azuma Hoeffding inequality Õ(VTHi) with probability 1 1- We now describe how to bound the first term.
Note from Lemma 9
1 y2
1112KK
(V (++) (x4)) + Y(H Vo < 21
2
(. (oV)) (v1 Ya (222((a))) +
K
K -V r Σ
Vk (2+) (at)
(54)
1=1
Ta
24

---

Published as a conference paper at ICLR 2023
8 Y S ç, Lemma 13 and 15 we obtain with probability 1- 48
Now, using 1)
VKH2
K
(g S ( ((V
(55)
Now, from the result of convex optimization (Corollary 1) we obtain that with probability 1 - 36,
2(1 + O (VVoTT Σ - - K (2+))
&
Thus, obtain bound for the second term. individual term in (53).
The final result is obtained from the bounds of each
G.2 PRELIMINARY RESULTS
Lemma 16. Under Assumption 2, for any fixed policy m, w be the corresponding weights such that Q₁,a (0(2, a), for {r,9). then we have for all h E [H].
||05 2HVd
(56)
Proof. From the linearity of the action-value function, we have
QJa(x, a) jn(x, a) PV, (2x a) = (Ó(1,, a), (5,m) + / Vj Vj () a), = (6(x, a), w.,N)
(57)
where W.AA- = 0j.h + Ss i Now, |10,A Vd. and IlSs Vi (2)) (x')ls Hvd. Thus, the result follows.
Lemma 17. For any (ks, h), the weight wht satisfies
|1ug,alls 2H 2H /kH/A
(58)
Proof. For any vector v E Rd we have
--1 "
|oT wi " (A))
Σ
( (h))) + Σ The 1m
a))l
(59)
here Th. (-|2)) is the Soft-max policy.
Note that Of,41 +1 (Ir, a) S H for any (x,, a). Hence, from (59) we have
1 25. 1.2H
h
T (AR) (AR)--U
Σ
Σ th (A 154
2H|| VdkH VA
(60)
We use Observation 1 to bound the second term. Note that |/w ||= max,: |m|| =||=1| 00 ". Hence, the result follows.
25

---

Published as a conference paper at ICLR 2023
G.3 PROOF OF LEMMA 3
Proof. We prove the result for o = r. The proof for is similar.
For any x, and h E [M],
V (x) (H h - 1)J, = E Σ r a/h) 1F 24 2]
H
Σ M=h
or (1/2 d/h) - Pe (2 d/)l x!
E
Σ (b (IN)) - (x =
k'=h
v (x) Ele (IH+1))
Hence, V. (x) - (H + h 1) 1} sp(r;)) since |0,|5 5sp(u)).
G.4 PROOF OF LEMMA 9
We first state and prove the following result which is similar to the one proved in Ding al. (2021).
Lemma 18. For Y [0.
K
y2
nH²k
Σ
(Y--Y) (H) - x (x,, S
(61)
21
k=1
Proof.
|Y++1 =|== |Projo (Yx + 17(b - (x((2)1)) (roj)o.e(()))
S (Y: + 11(b (x1))) - Y)²
< (Y, -Y)² + H2² + 2Yx - Y)) - (2,(1()))
(62)
Summing over k we obtain
K
S |K41 Yp= IY +22 Σ
Hb k -Y)+
k=1
K Σ (Y-Y))) - Vk 9.1 (x4))
Y1 - Y12
n
+
(63)
2n
2
1=1
Since Yi = 0, we have the result.
Now, we prove Lemma 9.
Proof. Note that
K
K -Y- V& (x + Y x) 1---VV V2VA (x+)
HHb - K- V-))((+)))))))
h=1
+ L((+ (V² - (2fi
1 y2
!7 11'2 K Σ (Hb -V))+ (xf)
21
2
K
< y y2
! H
Σ (rav (x Ya ( + Y
g.1 (at) - VV
2m
2
k=1
where the first inequality follows from Lemma 18, and the second inequality follows from the fact
that Vi (x+) > Hb Hence, the result simply follows from the above inequality.
26

---

Published as a conference paper at ICLR 2023
G.5 PROOF OF LEMMA 1
Proof. We only prove for o - r, the proof for o = is similar.
Note that OT, (I, a) (0(z, a), w (z, + PV (a,
We can write W = (A*)- A W
Now, A AI -ー= Ex N 6 of )o( af (See the algorithm 1, line 3). Hence,
W (AI) + ( 0h )o( (,) a )u,,
Finally, from the definition of WaA, @ h, 0 7 ".,,, ru (2% al) IVV,,,+1 (1% af) (from Lemma 4).
Hence, W = -A +
En p( o/ (rn(of) + PV PV
Hence, we have
k-1
wrth W7,h (A#)-1
Σ
Ir ah) + Vrl V w
=- (w:,h) + (1*
thr (Vih (1T -
-Aat
Σ Σ M
the
(1%h oh.)
PV PV al.)]
(64)
Now, bound each term in the right hand side of expression in (64). We call those terms qı Q2. and respectively.
First, note that
(),
(A²)
S VVllwA (NV)))
(65)
Second, from Lemma 10, for the event in E, we have
K (). CdH CLH where x log(2(C] + 1) log( (og((l)))))))))) AI) Third,
(66)
(6(2, a), qu) = (0(x, (A*)
The (P - V af-)l)
A-
(0(z, (At)
ΣΣ
Σ
/ (Vihh (
T=1 h
= (,(2, / (V - Vr
(2 - (olz, (),=,))) (1/ Vith+r
(67)
The last term (67) can be bounded as the following
(V (o(2, /
V (= 2 2H 2H /A (A)
(68)
since II (V V2 ((a)))()))()))) 2H as (S] Vd. The first term in (67) is equal to
P(Vk h.+1 V (Z
(69)
27

---

Published as a conference paper at ICLR 2023
Note that (0(æ; a), w Q (z, = (0(2, a), wS,h w (0(2,a), + 92 qs). Since 1, we have from (65), (66,,68), and (69)
(((r,, a), w C a) P( - V (rn+))( a)ls C3dH VXV (A0
(70)
for some constant C3 which independent of C₁. Finally, note that
Cavī Vlog(2(Ci log( log((A))(dTT/))
= C3v log(C1 +
Cive
(71)
where , = l2g(2 (o((log((A))/dT/p)) The last inequality follows from the fact that [log 2, o0) as
| 2, and C3 is independent of C1. Hence, can always pick C3 /log 2 log(C1 1) <
Ci /log which satisfies (71) for all values of E [log 2, oc).
G.6 PROOF OF LEMMA 12
Proof. From Lemma 11, we have w.p. 1 28,
(x) + V2Qg < (0(2, a), wH,h) + (o( a), k (ggh)) + (1 Yx) (A4)
+ + + VeVy - V/A+1 - -VV
PPVE = (0, + (2, +) -
G.7 PROOF OF LEMMA 13
First, state and prove supporting result which bounds the value functions corresponding the greedy policy and the soft-max policy at a given step. We show that this gap can be controlled by the parameter a.
log|
Lemma 19. -
- (x) <
where
Definition 4. V/((-) max, (0t Y2Q (t,a).
A (-) is the value function corresponds to the greedy-policy with respect to the composite Q-function.
Proof. Note that
(x(()) Σ (nela + Y&Q (2,a)
(72)
where
exp(alQk (2, V.Qu (z,
(x, a)))
[n,((a
(73)
Σ. exp(alQ (x, V&QU g.l (Ir a)))
Denote a, arg (Q. a) + Y& 1 (I,
28

---

Published as a conference paper at ICLR 2023
Now, recall from Definition 4 that V/ [ (2, (x) Then,
V (z) (x) (2, (z,
The (al=)) + 10, (z,
log(E. exp(a(Q (2,0) + Y2Q (z. a))))
(a + V. (2,
(og((AA)
(74)
αt
where the last inequality follows from Proposition in Pan et al. (2019).
are now ready to show Lemma 13.
Proof. We prove the lemma by Induction.
First, we prove for the step H.
Note that Q H+1 0 U²H+1
Under the event in & as described Lemma 10 and from Lemma 11, we have for j = r, 9.
Kő(x, a), (2, QZ a)|s ( (N0))000
Hence, for any a.,
(2, & min((o(e, w., By (1)))10 H}
= (x,n)(
(75)
Hence, from the definition of V/A
(x) = max(Q + Ya Y2Q (x, 2 Σ x4 Y2Q (x,
V. (x)
(76)
for any policy Thus, it also holds for n² Hence, from Lemma 19, have
log(lAA)
V Ya (x)
V (x:)
a
Now, suppose that it true till the step h + and consider the step h.
Since, it is true till step h 1, thus, for any policy n
(H - h) log((AA))
P (z,
(77)
a
From (50) in Lemma 12 and the above result, we have for any (z,
(z, + A s (x, + Y&Q (z, a) + (H - h)) log( (AA)
(78)
Hence,
V... (x) < (x((x) + (H - h) (og((A))
(79)
29

---

Published as a conference paper at ICLR 2023
Now, again from Lemma 19, we have (x) (x)) - log(lA[) Thus,
a
V/ (x) v (H h 1) log((AA)
(x) (*)
(80)
Now, since it is true for any policy it will be true for n² From the definition of VT we have
Y& (x))))))) - H - + (4++1) log((AA)
V (x) + Y (( (x) (
(81)
Hence, the result follows by summing over K and considering 1.
G.8 PROOF OF LEMMA 14
Proof. By Lemma 11, for any x. h, a,
+ 3 o(2 -o. (T,,((,,)) 0(2, ((2,,
< - -ooiii--oohhllll 22
(82)
Thus,
(v, - 2oth (z, S
PP(V - VaL (oht))(2, a) + 23 a) (M))))0)))00
(1, Qo a)) 20
(83)
Since V2 E. (a| (a)2) (x, (2, and vah(2) En (1 (x, where Th,k (al.) = SOFT- + Y&Q Va.
Thus, from (83),
val (1+t) - (=t)())))) = Σ maa
Σ (a
2a (2t, a)]
+ 2/ / (At) ( at) + PVV 2 V ( att - (0% (1h, 0% (ah at))
(84)
Thus, from (84), have
(x (x S D D&,n.2 + 1o,t+1
VTa ( o (A*)
(85)
Hence, by iterating recursively, we have
H
H
vha (z1) V.- S E + D 2. + Σ 23 ø( ( a%)
(86)
h=1
h=1
The result follows.
G.9 PROOF OF LEMMA 15
Proof. Note from Lemma 14, have with probability 1 - 25,
K ΣΣ
v (x1)
( 1, + D
Don
Σ> 2,3 (1 a
k=1
k=1h=1
(87)
30

---

Published as a conference paper at ICLR 2023
We, now, bound the individual terms. First, we show that the first term corresponds to Martingale difference.
For any hk E [K] x [H], we define Fh,1 o-algebra generated by the state-action sequences, reward, and constraint values, {(r], ()) U {(a.. af))
Similarly, we define the Fh,2 as the o-algebra generated by (()):))))s U {(4,, (irt,a)))e Nem U (= # is null state for any k E [K].
filtration is a sequence of o-algebras (AAm))
in terms of time index
t(k, m) = 2(k 1)H + 2(h - 1) + m
(88)
which holds that h.m C ml for any t S t'.
Note from the definitions in (52) that D E Fhi and D E Fh.- Thus, for any (k. h)
[K] x [
1. = 0, ElD A,2 Fr =0
0, 1 1,2
(89)
Notice that ((k: 0, 2) - 1(k - 1, H, 2) = 2(H - 1)k. Clearly, Fh.2 = =F for any h: 2 2. Let Fb.2
be empty. We define Martingale sequence
k-1 #
h-1
M km
D + Djx2))
Σ
(D + D2 + Σ J.h.
Σ
Do.i.l
(90)
(())))/KKK(((((])]_____ where t(k, h, m) = 2(k 1)H + 2(h - 1) + m is the time index. Clearly, this martingale adopted the filtration (Fh (Fhmmb) (k.h,,) [K] x []] and particularly
ΣΣ D),n2) = M 2HH
(91)
k=1A=1
Thus, M H. is Martingale difference satisfying I. 4H since |D 1.I, 2H
From the Azuma- Honna-Hoef inequality, we have
s2
Pr(M > 8) S eexp(
(92)
16TH2
With probability 1 - 25 at least for any o= o=
ΣΣ MK M S H
(93)
h
Now, we bound the second term. Note that the minimum eigen value of A is at least A 1 for all (k, h) E [K] x [H) By Lemma 20,
det(Ak-1) det (oo)
(AA) s S 2log
(94)
Moreover, note that ||A MAK++11
( +IIIS X T, hence,
K
T T
( ( 1/ < 2d
2d
(95)
A
1=
Now, by Cauchy-Schwarde inequality, have
K
K
(A*) S VKH
(At)
k=
k=1k=1
/2dTi
(96)
31

---

Published as a conference paper at ICLR 2023
Note that 3 Vt. Thus, we have with probability 1 -6,
K
K
V (xf(
V (xf) + Y
(v
(af)
Val (zf))
9.1
S + + -
(97)
Hence, the result follows.
G.10 PROOF OF THEOREM 2
Note from Lemma 9, Lemma 13, and Lemma 15, we have w.p. 1 - 48,
K
(V. (x1) V.l (11)
Hb Vggi (xf))
k=1
k=1
5 y2 7 I12K
HK logl A
O(Y 1) H2
(98)
2nj
Replacing with 0 in (98), we have
(V (z1) - (
S 2 H² +
7
HK logl +O(VHHTT1
2
5 and a
loglAly KH
By noting that
we have
VKH²
2(1 + E + H)
EVKH²
Σ
(xt)
+
= =((VPTH?)
(99)
where the last equality follows from the fact that KH T
Now, observe the third term in (47). Note from Azuma-Hoeffdiin Hoeffding inequality (since 1 (x (t=(k- (1aee)))4((1(( (r( ax))] = 0 with respect to the Filtration Fx-1). Hence, with probability 1 -
T/H
kH Σ
(xf)
(r(*n, ax)) S H HTT/Hoog(2//
1y#+1
S <((TH))
(100)
Now, using Lemma 3, (45), (99), and (100), in (44) we obtain with probability 1 58,
Regret (T) s (T/H))p(r;) ((V@THH) + +(VTH) Since H T1/1 //3/4, we obtain with probability 55,
(101)
Regret(T) < 3//4//// 3//4/3/4 sp((;)) + (((dT))34) (1 + (1+sp(o2))0((arr>>
(102)
E and
logl A v KH
Now, we bound Violation. By noting that 17
have from (98),
VKH²*
2(1 + H!)
K (V. (m) -XT (x)
Y
K ( (a+1)
k=
+
+
(103)
32

---

Published as a conference paper at ICLR 2023
From the convex optimization result (Corollary 1), we obtain
K
2(1 +1
- k -
(104)
&
Also note from Aruma-Hoeffding inequality, w.p. 1
T/H Σ
KH
(V
Σ
a(),,a))) S H / /T/ H (2/
(105)
t= 11++1
Hence, combining (104) and (105), we obtain w.p. 1 56
K
T/H
kH
g(z). am)) s 5 (0(
+)) VdTH2)
2 Hb - K (x +
(Hb
(a+)
Σ
1=1
k=1
t- [k -- 1)
+ E)
Violation(T) (T) S (T/H) Ō
V(TTH2
+1++ x)O (1 + 5) 8/1)
(106)
where the last equality follows from the fact that H = 11/4
G.11 DIFFERENCES IN A NNLYSSIS FOR ALGORITHMS 1 AND 2
Note that we also need to show that log e-covering number for function class is also log(T) in Algorithm 1. However, since Algorithm and Algorithm 2 are different, the analysis is also different. In particular, in Algorithm we consider a primal-dual type algorithm, hence, the policy is based on the combined state-action value function. Thus, we need to show that the log e-covering number for individual value function scales at most with log(T)) even though the policy is based on the composite Q-function. On the other hand, in Algorithm 1, we directly search for the policy which solves constrained optimization problem. In Algorithm 2 the policy is itself a function of Qo and dual variable Y,. Thus, we obtain the result only using the property of the function class of Q, and the boundedness of Y₁- On the other hand separate policy function class is defined for Algorithm and obtain the result by exploiting of the smoothness property of the function class. Thus, our analysis would work for any policy class with smoothness property (Appendix F.6) unlike Algorithm 2. We need that the optimal policy should also belong to 11 in Algorithm In contrast, in Algorithm 2 we consider an unconstrained version of the episodic CMDP setup. Carefully crafted Soft-max policy enables us to bound the gap with the optimal policy in the episodic setup. Hence, we do not need to search over feasible policy space unlike in Algorithm 1.
G.12 SUPPORTING RESULTS
The following result is shown Abbasi- Yadkori et al. (2011) and in Lemma D.2 in Jin et al. (2020).
Lemma 20. Let {Ør Fiz be a sequence in Rd satisfying sup:zall@uls 1. For any t 2 0, we define Ag Ao + 1 En Sh (ot)). Then if the smallest eigen value of Ag be at least 1, we have [de((Ak)
[de(AAk) (Ao)
log
S <Σ (ot)" on < 2og
(107)
dde((Ao)
Theorem 4. |Concentration of Self-Normalized Process Abbasi-Yadkorii et al. (2011)) Let { be a vell-valued stochastic process with corresponding filtration {Filo= Let e be a zero mean and a sub-Gaussian, i.e., [[E, = 0, and
VCER. [le S S 000
(108)
Let (2)) be -value Stochastic process where de Ft Assume No Raxd is a positive- define matrix, let, = kH, A. Ao + En= En H (d..) Then for any 8 > with probability at least 1 8, we have
1-11200m00 log det((A,) 1/2 det det(AA) - 1/2
Doea 1 20
(109)
6
33

---

Published as a conference paper at ICLR 2023
The next result characterizes the covering number of Euclidean ball (Lemma 5.2 in Vershynin (2010)).
Lemma 21. Let {2a] be stochastic process on state space with prnvesspodinngfltraattt {Fi). {or} be IR--values stochastic process where Φt E Fi-1 and @ 1, A, = TX + +E= 2.0. and V be arbitrary set of functions defined on X with N. be its c-covering number with respect
disr(V, V*) = sup,, (z() - ('(x)) for some fixed e > O. Then for any > with probability 1
for any V E V so that sup,, [ H. we have
I (+}
N + 8/22
Σ
S <H
log
+ log
(110)
2
A,
Observation 1. Let A - EN (0%) + AI, where X 0, and 0% R., then
ΣΣ (0))) (A7) sd
Further, Ex=l En tr((0),) 1 = 1r((Ar) 11:))~-E E/= En oy (1h,) )) Given the eigen value de- composition, Σ En 07 (1 Udiag(A (A1. U². Thus, A Udiag(Ai +A,,... Aa+ A)Ue.
Proof. We have Ex=1 (o)
Et=l En tr((o)))) -A+)-1%))) - -o)).
Hence, (r((Az) (A oh (%. \1/(Ar + d) S d.
Lemma 22. [Covering Number of Euclidean Ball] For any O, the e-covering number of the Euclidean ball in IR with radius R is upper bounded by (1 + 2R/e)*.
We have used the following result from the optimization which is proved in Lemma in Ding et al. (2021).
Lemma 23. Let Y be the optimal dual variable of the episodic CMDP (46), and C 2 2Y", then, if Vil (x+)) < &z
VAT (2f) - (+ + C(b
(111)
then
20g -b- V. S
(112)
C
Corollary 1. Let Y be the optimal dual variable, and C 2 2Y if
Σ v (a+)
V (2+)
V. (a+)) < 8
(113)
then
28 C
vh (xf)) <
(114)
Proof. Let V, (af) - (xf)
C(bb V (xf), then from Lemma 23,
28
(1 S V
(xf))
(115)
By summing over k obtain
28 25
Σ (b- Vb < Σ <
(116)
C C
where the last inequality follows from the fact that Σx 8x v 8.
n
34

---

Published as a conference paper at ICLR 2023
H PROOF OF RESULTS IN SECTION 4
We, first, provide a proof sketch of Theorem 3 in (Appendix H.1). Subsequently, we provide detailed proof. We show that how we achieve zero constraint violation via tweaking the algorithm in Appendix H.5.
Organization:
Notations for this Section: As shown in Appendix A of Wei et al. (2021a); assume that (1 a)llaa)llsss 1. Without loss of generality, we assume that we represent 6(x a) ej = 1 for some vector é1 for every (z, a). [|(())]2z vd, |10l1es va for j r. Also, for every policy x, qº (x, a) can be written as ((x, a)) a)""" w=. || I| 6t vd (by Lemma 34). We denote of (zz a) as (uf)) ó(x, a).
H.1
PROOF SKETCH OF THEOREM 3
Regret can be decomposed as the following
KB
Regret (T)
Σ -
Σ
Σ 1=(k-1)8+1
(J+- (F=,)(3;))))
(117)
In the following, we bound each of the two terms at the right hand side. Unlike the unconstrained setup Wei et al. (2021a), here the decision depends on both of and gg thus, the analysis will also be
different. In particular, in order to bound the first term, we bound T/B B[J; J + BY - J Specifically, since J 2 b. we obtain for any Y E [)
T/B
Σ
BJJ - J.h - J S
km1
T/B
B
J
YzJ
J + (Y-:+++-----)) Yn) Jg + Y Y2) - jMy
km
Ts
Note that since the above expression is true for any Y E [0, E). we can recover the bound on regret by setting Y O.
For Tı, we employ the value-difference lemma. This step may seem similar to the one considered for the unconstrained version (Wei et al., 2021a) which bounds Ex(; - -J²)). However, there are two important differences. We have an additional constraint term scaled by the dual variable Y₃ which also changes over time. Second, Wei et al. (202la). We utilize the one-step decent result of OMD OMDfrom Lemma 3.3 in Cai et al. (2020), Azuma- Azuma-Hoeffliin Hoeffding inequality, and the boundedness of [[w'll using Assumption bound the term. The final result is shown in Lemma 24.
provide high probubility bound instead expectation bound in
Lemma 24. With probability 1 8.
B T < (KO(a(1+ + +2) + log(1A)
(118)
Proof. See Appendix H.I.I.
Note that in the unconstrained setup the term To does not arise. For Tz. we rely on the fact Ex(j Jst are close since the way collected samples jk is close to an unbiased estimator for J (Lemma 33). Using the fact that - Yæl &, we bound Ta the following
Lemma 25. With probability 1 8,
To < + (2VTo))g()
(119)
Proof. See Appendix H.1.2.
35

---

Published as a conference paper at ICLR 2023
In order to bound 7s. utilize the result from the dual-domain analysis (Corollary 3). We show that the upper bound of T3 & EVTB.
Hence, we have with probability 1-22 -2.
T/B
Σ
BJJ - - (b
BKO + N)2 (log((AA) + O
(120)
In order to bound the second term in (117), we need to show that policy between two epochs change slowly. Here, we use the value the hyper-parametee a, and the upper bound of the dual variable to bound the term Lemma 26. With probability 1 162
RB
Σ
(J= r(a, s Ó((( + V Tes
(121)
1)8+1
Proof. See Appendix H.2
Hence, combining the above, setting Y 0 and replacing (120) in (117) obtain with probability
1 45
B Regret (T) KŌ(o(1 E)2 log(lA) Ō(1 + Te
(122)
Now, replacing the value of a, and B, we obtain
Regret(T) S Õ((1 + f)/o///////// /
Tt
(123)
Constraint Violation: Similar to the regret step, we decompose the violation in the following form
B
Σ
g(Er, at))
t= = 1)841
The second term can be upper bounded the similar way as the second term in (117) with probability 1 28. For the first term, we observe
B J < Σ - - )
(124)
Now, from (120), we have with probability 28
Σ B J7 BY J s ((11 + ()/o ()/o+)//ooooll/////
(125)
Finally, by replacing B and applying Corollary 4, we obtain with probability 26
B(b - Jz²) - 2(1 E) Ö Tr Σ
(126)
&
Hence, the result follows.
H.1.1 PROOF OF LEMMA 24
We, first, state Lemmas 27,28,29 which will be useful for proving Lemma 24. Lemma 27. Using the value difference lemma (Lemma 15) in Wei et al. (2020), we have
J + YnJz J YNJ g - (a)o))) (a(x))))
(x, ( Yugg (x, d)) (x)
(127)
where u²² (x)) is the stationary distribution corresponding to the stationary policy n².
36

---

Published as a conference paper at ICLR 2023
Also note that Eo (T ( (a|2) (T( + + since J is constant.
From Lemma in Wei et al. (202la)
Lemma 28. Let [k.] denote the expectation conditioned on (Frr. arhmn and all the history before ma then
1
E Ra [Tkmm] (47 (ETK. amn..)) N
7
1
G [k,m]]
(gg (Irr, arr. + NJ )|ا
(128)
T
Thus, Rt.m and Gk.m are close to the unbiased estimator of g.* N J and 47 +N* respectively. Also from Lemma in Wei al. (2021a) Lemma 29. For r,
1
E& [ (w + NJ
(129)
T
where E& is the expectation conditioned on all history before epoch k.
Now, we are ready prove Lemma 24.
Proof From Lemma 27, We express Ti in (117) as
B TT (a|xr - (2 + Yeg (r, NJ, + +
&
B
(alx) - (m + Y (x, YzNJT*) Ex + (n a)l)
T (alx) (((al)) + (2
(1 (x, + (x,((,)))))
To
(alx) (a(l)))(() (xo)(z,))
(130)
Bounding T:: The bound of Ta is similar to the unconstrained case Wei et al. (2021a). The only difference is that since have extra term corresponding to Yugğ. there is an additional scaling factor of (1 E). The details are in the following-
Note that d.th (xx a) (w y o(x, a), J = Jm plx, and (x, = (Tx))'(( a).
From Lemma 29, we obtain that
E& [ (Tt a) (wg* + NJ ) || (w + NJ )
< T2
Hence,
(T (a|x) - T (oooooo0000(((oooooooaooaa + -E.
(z, s a) +
|| (.1z) -
NJ YYNJT*) Ex Yeg
1 +
7
Hence,
T4 < 1+
(131)
T
37

---

Published as a conference paper at ICLR 2023
Bounding Ts: Since providing high probability bound instead unlike the expected regret bound in Wei et al. (2021a), we need to bound 75 whereas such a term did not arise in Wei et al. (2021a).
Ta is Martingale difference with respect to the Filtration Fk-1 which contains all the histories till epoch k. (x, + Yeg, (a, a>|s (1 + N)N/o (From Lemma 31). Hence, from Azuma-Hoefiding inequality, we obtain w.p. 6,
Σ
(T" (a/x) =x(al))) (z. a) + Yag (z. a)] - (g. + (x,
s ( 20
(132)
Thus, multiplying the above with B, we obtain
To S + ()
(133)
with probability 1- 8.
Bounding To: In the unconstrained case Wei et al. (2021a) bounds EIΣ, (rr [x(al=))a""< a)] (Lemma 19 Wei et al. (2021a)). To may seem similar to the above expres- sion, however, there subtle differences. First, do not have expectation since need to consider high-probability bound. Second, we have additional Yogg term where Yg is changing over k. Thus, we need to different techniques compared to Wei et al. (2021a). In particular, rely on the analysis of OMD and one-step decent result from Lemma 3,3 in Cai et al. (2020) to bound Te. In particular, use the result from Lemma 3.3 in Cai al. (2020), obtain
T - T R-1 + YE- 19-19 k-1 S =alla=11 + Yugg k 11 + - (D(T"(TKk)) (k- - ((TT'(TT)
Now, by the construction of w and w we have |1 (Lemma 31). Finally, by telescope summing over & and using the fact that D(-) is non-negative, we have the result. The details can be found in Lemma 30. Specifically, we use the result from Lemma 30 to bound Tg-
(1 0)=12))22
B log(l-4))
To TO(a(1+))
(134)
since KB = T.
Hence, we have with probability 1 8,
TT" [a(a)) (a()))))))))))) Yeug (enga(1,,0)
2(1 (7((a(1+))2N2)
B log( Al) + 0
N v /BB log(2/))) (135)
a
Since min(
(1+ Time 24(1 E)N ). N Stmix log(T), 32N 222Nlog( (dT) 00 then,
B
(TT (a|x) n4 (=(a)=)) (x, Yva TM (I, (((1 /)/ Tt?
Σ/
B B ((()))))m((()))()))) (z + Yog (z, a)) (x) < 5(1 5)/o Tt3 mims)
where the last inequality follows from the dominated convergence theorem and fx dv= (z) = 1. Hence, we have with probability 1 1-6 8,
Ti < Õ + ()/o T
38

---

Published as a conference paper at ICLR 2023
H.1.2
PROOF OF LEMMA 25
Proof. We can decompose T2 as
Σ - (E) - B(Y - Yx) Ea()))
(136)
2 From Lemma 33, [E (Ja) J 77.
Also note that (Y - Yc) E& (Ja)) is Martingale
sequence where j s 1. Further, Y -x E. Thus, we have with probability 1 1 6.
K
B(Y - Ya) - F& (x())) < BE B Σ
(137)
Since K B/B, hence, with probability 1- 8
& To S 76 & TB log (2/0)
TB
From Corollary 3 and 1)
we have
VTBB
Ta S EVTB
(138)
where recall that T3 is the third term in (117).
H.2
PROOF OF LEMMA 26
Proof. Note that
&B
Σ
Σ
(J - r(()) b (=(k-1)B-1
Σ
(o - BE (v, (2++1)))
(
Σ
Σ
(1 - 2. + Σ
Σ
(1.7 with (I++1))
11B+1
1)8+1
Σ
Σ
of (Z+41)
EE 1 P( (w.7 (I++1))
k tm 11+
Σ
Σ
(g Th (Ir, (t) - -. (Ix)) + Σ (0 (xt) 0f To (o+)) + 0, (xt) T. (xx
Σ
Σ
1f -
(I++1))
K 1=(#-
111++1
Note that T (xt)ss (tmirr), and 1uT (I Ottmir), thus, we have
kB
Σ
Σ
(J - (((,
Bk+1
Σ
Σ
(0* - + (0 with (xf)) O(bmix)
1)B+1
Σ
Σ
o Th (T+11
EE, IM (+(a,a)) (1z (v++1))
(139)
(k-1))++
The first term is Martingale sequence. Hence, with prob. 1 - 6, we have
E
(q (2), ot (xx)) I 6tmis 22T 1og(2/8)
(140)
(=(K-1)B+1
39

---

Published as a conference paper at ICLR 2023
For the second term, since [Tx(a|z) - = (000)) (by Lemma 32),
then, by Lemma 7 in Wei et al. (2020), we have
2 (z)
ur - (x) = (a((1 ()
(141)
The third term is again Martingale sequence. Hence, we have with probability 1 1 6,
E
(E(+1) E B P( (21+1)) (2((1)) I mtm 22T log(2/6)
(=
Hence, we have with probability -2,,
BB
Σ
L - a:),
+ + + 12 v 27 log(6/0))
(142)
(
Now, using the value of a, we obtain with probability -25,
kB
Σ
(J+
r(z,, al) & T
Tt
(143)
t= (1-1)
H.3 CONSTRAINT VIOLATION BOUND
From (120), and the value of N,, and B, we have with probability 25
B J:h) + YB(b Jz²) - (((1 + ()/o Ttmeis)
(144)
Now, from Corollary 4
Σ B(b B(b-J5+ Ö 2(1 + 5) 0(
Eo V Te
(145)
On the other hand similar to Lemma 26, we can also show that Corollary 2. With prob. 1 28,
Σ
(J - -(E,
S Ö6 TI
(146)
B)41
Hence, we obtain with probability 1 - -66
Violation(T)) - 36 3(((++5)
(
(147)
Eo
H.4 SUPPORTING RESULTS
Similar to Lemma 18, can show the following Corollary 3. For any Y E [0.g]
Y2 Л
[ Yb) - 5kb
(148)
2n
2
Lemma 30.
Tk, dr
+.g < >
<) log((AA)
(149)
40

---

Published as a conference paper at ICLR 2023
Proof. Now, from the composition of the algorithm (12), obtain
1 a (
K = arg max(T, or k-1 + 10-10 k-1)
(150)
From Lemma 3.3 in Cai al. (2020),
(T" 1 R-1 + Yk- 19 R-
1 =
+ + Ykgg aalar-1
11x0 (D(T (D(T"|Tx-1) - D(
(151)
Now, from Lemma 31, ||,,-11 Yug 1 1l O((1 0(11+))22300
Now, by summing from l: = to K + 1. and shifting k: to k2 we obtain from (151),
K
Th, of + +Yd - (0((((+()()/////// + (D( - D( (x+1))
(152)
By Pinsker's inequality
D(T - +
(153)
On the other hand, since mi is uniformly random, thus,
D(* TT) S log([A4)
(154)
Hence, from (152),
K
- Tk, TR, + Yu4g) s (T((a(1()))N3/11 log((AA)
Σ
a
Lemma 31. For any x, and
10(x, (w + Yx-1w [(1 ()
(155)
Proof.
oxx, a)"(()))))) (wf=1 + Yk-Iwn S 1|0(,, a)ll,,, + Yn-
(156)
Note that from the construction of the parameter,
24N B
|ml 1
VaN
(157)
Bo 2N
Hence, we have
a) (w { <0((1+))N/
(158)
Lemma 32. For any a, x
aN (x(aax)) (a(=)]s Te-1(a)=)0 (1 +))
(159)
Proof.
Th (a)x)) (xxxe(o))x exp(ax((x, (( + Yt 1n wo
Th (a/2)) - T
Σ, -h- (b/z) (b exp(ax(xx ()
(w/- + Yv 1 -1))
[x-1(alx) exp(xó(z, a) (w + Yn- YR-1
expl- -sp min (bo,, b) (w k-1 + Yk-1w/ (a)x
E. TK (b/zz)
20 (z, 6)² (w k-1 + Yo Yo- - 1)
41

---

Published as a conference paper at ICLR 2023
Note that max: (w + 12 - 1 as long S 0/ E)N). Combining with the fact that exp(2x) I 1 + 8x for E [0, 1].
exp(max 2aolxx b)* (u, -- + 1x-1 1 S 8a (2x 6)" (u, 11 + 1u- 111
b
O(a (1 + NN
Hence, the result follows.
Lemma 33. For any k;
[B
J S T
(160)
Proof. Let I (1) denote the probability that the learner reaches the state 2 time within epoch & when the epoch starts with the state zf. Hence,
|PT x -llv== ||P 82, (x)
(161)
where dz, (x) when a = Iı, and 0 otherwise.
[+
1 1
g
B
Σ
(1), - J alteelaalllaa (x)
B - N
N=N+1
x
Σ
2 2|
-/ 2f)
10
B N
2e [mi
B
N
M=++1
2
(162)
7T
where the second last inequality follows from Assumption 4. The last inequality follows from the definition of N.
Similar to Corollary 1, show the following Corollary 4. For C 2Y*,
(J - J=+) C(b C(b-
8 5
(163)
k=1
then
25 C
Cbb
<
(164)
Finally, state some results which are proved in Wei al. (2021a) (Lemma 6 and 14, respectively).
Lemma 34. For any stationary policy æ. and (x))< 4tmiz and l (z, a) 6t for any (x, a).
Lemma 35.
9² (x. a) (w" + e= (T(
(165)
42

---

Published as a conference paper at ICLR 2023
H.5 ZERO CONSTRAINT VIOLATION
We show that by considering a e-tighter optimization problem, and by carefully choosing one can obtain zero constraint violation while maintaining the same order on the regret.
First, we introduce some notations. Consider the e-tighter optimization problem
maximize J, subject to J 2 b b
(166)
where in the constraint 6 replaces b. I S 7/2, then Slater's condition is satisfied as म would still be strictly feasible for the e-tighter CMDP (Assumption 3). The optimal dual variable is bounded
by Y I 2/n for this tighter optimization problem. Since need & 2 2Y*, make 4/y- We denote the optimal policy of the e-tighter optimization problem .=. We denote J the optimal constant gain of the tighter optimization problem (166).
Now, ready state the result for the set of Assumptions in Section 4.
Lemma 36. In Algorithm 3 replace b with b + and with 4/7, then under Assumptions 3,2, 4, and 5, with probability 46
Te
Regret(T) S. 0((1+
T )
7
Violation(T) S Ō 2(1
6 2(1+ + 5)
TT - -T'.
(167)
of
2(1 2(1 + E)
T+3
log(d))2/5 min
where e min(Co(
), 7/2 for some absolute constant C..
of
T
2(1+5 Note that when Ö 2 {) Thmin
S 4/22, then violation becomes Hence, for some constant
of T
mix log(dT))/6 < 7/2. Also note that by 2(1+5)
VTH
Cs. we obtain violation 0 when Co(
of
T
plugging in the value of e, the upper bound on regret is still Ö(VT). Hence, even when for large enough T (still finite), the violation is 0, while the regret bound is still Ö(VT).
Proof: First, we prove the upper bound on regret. The regret can be decomposed as the following
T -J
T
(T)
Σ (J. r(x,, at))
(168)
The first term can be bounded with the help of the following lemma (the proof for finite state is in Wei al. (2022) and for episodic setup in Wei et (2021b), we provide the proof the end of this section)-
Lemma 37. If each stationary policy induces stationary state-action distribution v v=(xx a), every stationary policy satisfies (4), and =5* is the optimal solution of (166), then
J -
(169)
Under uniform mixture assumption (Assumption 4, the conditions of the Lemma can be verified.
Since the tighter optimization problem also CMDP, we note that the second term the right hand side of (168) is essentially the regret of the tighter CMDP.
Hence, from Theorem and Lemma 37 we obtain the expression of the regret bound Lemma 36.
Constraint Violation: Again applying Theorem 3 to the tighter optimization problem (166), we obtain
b + (0ce-()),))))))))) & 00
2(1 + 5) / Tva m
of
43

---

Published as a conference paper at ICLR 2023
Thus,
g( s 5Ō 50(211) 2 of Te Te
Thus, the result follows.
Now, we show that zero violation can be attained under the of Assumptions in Theorem 2 and one additional assumption:
Assumption Every stationary policy x satisfies (4), and induces a state-action stationary distribu- fion v² (z, a).
For uniform mixture assumption (Assumption 4), one can show that Assumption 6 holds. Note that Wei al. (2022) which studies the infinite horizon average reward CMDP for the finite state space setup assumes the above assumption inherently in their work. We are now ready to state and prove the main result.
Lemma 38. Replace b with + in Algorithu 2, k max(sp(vf sp(e;" }}, and & = =4ny, then, under Assumptions 3,2, 1, and
Regret (T) - 5(1 + (d(T))))7)3//) +
Violation (T) - (( (d))))) Te
(170)
.2/23 for absolute constant Ct. and ((1 + (dTT)
where min
T
log(2log((A)))) (0)
Note that when Õ(11 (dT))344)
S 7/2, the violation becomes 0. Hence, there exists some
T
constant C7 such that when C7 ((1 + +))T)) S 7/2,, then the violation becomes O. Hence, for large enough T' (Still finite), the violation indeed becomes On the other hand, by plugging in the value of e, we note that the regret bound still ((dr))//4 (in fact is Õ((1 + x sp(x;)
T
Proof. First, prove the upper bound regret. The regret can be decomposed the following
T
Regret (K) =
(J
+
Σ (J -r(ae
(171)
t=1
The first term is bounded from Lemma 37 since assume that every stationary policy satisfies (4). Hence,
J
(172)
Since the tighter optimization problem is also CMDP, note that the second term in the right hand side of (171) is essentially the regret of the tighter CMDP.
Hence, from Theorem and Lemma 37 obtain the expression of the regret bound in Lemma 38.
Constraint Violation: Again applying Theorem to the tighter optimization problem (166), we obtain
Σ b + g((,,))))))))))))))))))))))))))) +(1
Thus.
T
bb g(2r, ar)) < (0(1++))xTT)))))
44

---

Published as a conference paper at ICLR 2023
We also obtain that zero violation for Theorem in similar way while maintaining order of regret by picking O(I/VT) in the tighter CMDP.
Here, we show the proof of Lemma 37.
Proof. Let 1² (x, a) be the stationary state-action occupation distribution corresponding to the sta- tionary policy æ. According to Assumption, for every policy induces a stationary distribution. Hence, J Iz. r(z, a)dv/" (o (z, a), and J = S2 g(z, a)dd/" (z, a).
Consider the sate-action distribution // (.. -) (1 - -/" +<///0( There exists policy which induces the acte-action distribution If Altman (1999). Now,
[ g(x, ala, (z, c/7) / g(2, a( (x,0) + t / a(z,a)dv"
22
2 21 -1-e//10 e/>/////////// e//(bb + +2) b
(173)
Thus, such state-action occupation measure feasible for the tighter optimization problem (166).
Further,
I n.o.
r(c,a)dv (x, = -1-11/1) (11)) / r(a,a)ddr" (x, /
r(z,a)dv=(r, (r,
2 (1 </>)JØ
(174)
Since the state-action measure v/ (x, a) feasible, then J 2 S2 a)d) (x, Hence, from (174), we have
J J 2 -c/7
Hence, the result follows.
I EXPERIMENTS
We evaluate Algorithm on a similar model described in Chen et (2022); Singh al. (2020)- wireless node is continuously transmitting packets. The node consists of queue where the maximum capacity
time the node needs to choose a transmission power a {0.1,0.9) action. Higher transmission power results in higher probability of successful transmission. The number of packets arriving at the node at time t given by Y,. We assume Y, E {0, 1,2,3), and the corresponding probabilities attempted transmission has success probability of 0.9. The dynamics of the queue is the following Q.+1 min (9, max Q: + Y, D.. 0}} where D, is with probability a,P,, and 0 otherwise. The goal is to maintain short queue length with small transmission power. At time L, the node gets reward dg, Reward decreases d, increases. On the other hand, it gets utility if the state of the queue is low. Specially, the utility is (QQ)) = - 0.1QQ, We seek to ensure that the average utility kept at least 0.7. i.e., the goal to keep average queue length less than or equal to Compared to Chen et al. (2022), we use different utility function. First, we ensure that the utility is bounded between 0 and Further, Chen et al. (2022) considers the constraint as a cost function where we consider it as utility function. Hence, need to provide higher utility for lower state and vice versa unlike Chen et al. (2022). Further, our algorithm is model-free unlike in Chen et al. (2022).
(0.65, 0.2, 0.1, 0.05). The channel reliability is 0.9, i.e., each
Note that the setup can be represented in tabular form. Since linear MDP contains tabular form, the feature space representation becomes simple, in particular, Φ(x, a) = es.a where e,,a for the state-action pair (s, a), and 0 otherwise. The dimension of the feature space is |S||AA
We run Algorithm 3 for x 10a time steps. The parameter we used are the followings: = 200, N = 10, a = 1/VT, = 10/VT/B. Note that we do not know tmiz or σ, yet, we achieve sub-linear regret and violation which approaches zero. We have used Bo/(24N) obtain by tuning. Hence, our algorithm can work well even if we do not know the MDP dependent parameters.
0.05 which
45

---

Published as a conference paper at ICLR 2023
Average Regret
Average Violation
0.04
3
1
3
4
x10
x10
Figure I: The plot for average regret (Regret divided by of steps) and average constraint violation (T)) as function of (x-axis) for 0.01. The x-axis is in the order of 10 Each plot is average of 5 trials.
Average Regret
0.22
Avg. Violation
0.3
0.1
0.05
1
2
3
4
0
2
3
4
x10
x10
Figure 2: The plot for average regret (Regret(T)/T) and average constraint violation (Violation(T)/T)) as function of T (x-axis) for = 0.1. The x-axis is in the order of 10 Each plot an average of trials.
In Fig. we plot the average regret and average violation tightness for constrained introduced in Remark 1). As predicted by our theory, our algorithm achieves sub-linear regret and sub-linear violation as both the average regret and average violation decrease to O as 7 increases. Initially, the regret decreases fast since we start with an infeasible policy (violation increases. Fig. 3). Subsequently, the regret increases as our algorithm seeks reduce the violation by making the dual variable high (the policy would be sub-optimal). The average violation decreases rapidly (Fig. 2). Eventually, the regret again decreases when T x 10 as our algorithm finds the dual variable which balances the regret and violation. In this regime, the average violation slowly approaches as T grows.
function of for 0.01 (the
In Fig. 2 plot the average regret and average violation function of T for 0.1. Again is apparent that the regret and violation grow sub-linearly as the average regret and average violation decrease to O. Since is high, from Fig. we observe that the violation indeed eventually becomes 0. From Fig. 3, we observe that the violation starts decreasing after T ~ 0.5 x 10a as opposed to Re 10 for smaller value of e. The variation of regret similar to Fig. the regret first decreases rapidly and then increases till T = 0.5 x 105. The regret eventually decreases steadily as T increases further. Note that the regret starts to decrease much earlier T 0.5 x 10*) in this scenario compared to the scenario where is smaller. Intuitively, since is higher, the dual variable increases higher rate which helps in finding the feasible solution faster rate. The regret then starts decreasing
find the dual variable which balances between the regret and violation.
would like to point out the difference with Chen et al. (2022). The violation Chen et al. (2022) oscillates, and never approaches 0. On the other hand, in our evaluation, we observe that the violation eventually approaches 0. This is due to the fact that we have learning rate (which is O(1/ ) in the dual-update step whereas Chen et al. (2022) the learning rate is 1, hence, in Chen et al. (2022) the dual variable oscillates more compared to approach. Further, Chen al. (2022) only guarantees constant violation, whereas we can achieve zero violation.
46

---

Published as a conference paper at ICLR 2023
x10*
6000
Violation tion
4000
2000
Violatio
0.5
-1
x10
-1.5
1
2
x10
Figure 3: The plot for violation function of I'' (x-axis). The left-hand figure is for 0.01 and the right-hand figure is for 0.1.
47


Reviews:
[{"review_id": "rEAZkynppUI", "reviewer": "Reviewer_3YVd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This work proposes two approach, optimism-based algorithm and policy-based algorithm for infinite-horizon average reward constrained linear MDP under different assumptions and achieve better convergence upper bounds. ", "summary_of_the_review": "I recommend to accept this paper since the author has presented a complete result, including new algorithm designs, theoretical analysis, and empirical studies. And these results are new.  ", "strength_and_weaknesses": "Strength.\n\nThis paper is sufficiently complete. It proposes new algorithms, builds a theoretically-improved convergence analysis on both regret and violation bounds, and empirically verifies the result on stochastic environments. And this work is purely model-free; it doesn't require any estimation of transition kernel.\n\nWeaknesses.\n\nI didn't find any major weaknesses.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gpJCYLB8OD", "reviewer": "Reviewer_ob3W", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studied the Constrained MDP (CMDP) problem, under the infinite-horizon average-reward setup of linear MDP. The model-free algorithm proposed in this paper has better regret bound in terms of total steps $T$ compared with the previous algorithm for tabular CMDP, under weaker assumptions. Under the same assumption as the tabular CMDP algorithm, the authors show the algorithm can achieve smaller regret with no violation of the constraint. The second result in this paper is a policy-based algorithm that works under less realistic assumptions: uniform ergodicity and explorative policies. This algorithm takes a different approach and can achieve regret and violation of order $\\sqrt{T}$.", "summary_of_the_review": "This is a technically clear and rigorous paper. The novelty and significance are slightly decreased due to the existence of two previous works.", "strength_and_weaknesses": "Strength:\n1. The performance guarantee is significantly better than previous works. Compared with previous works for tabular CMDP, this paper works under weaker assumptions and has better upper bounds for regret and violation.\n2. Linear function approximation is a highly noted topic in RL theory community. The constrained MDP problem is a meaningful extension and can be interesting to many.\n3. The paper is clearly written and easy to follow.\n\nWeakness:\n\n1. Compared with Ghosh et al. (2022) and Wei et al. (2021a), the technical contribution is not significant. The regret analysis relies on first reducing the infinite-horizon average reward regret to the regret of finite horizons, the same as Wei et al. (2021a). Then, results for episodic CMDP are invoked from Ghosh et al. (2022) to bound the finite-horizon regret. This makes the novelty of Theorem 2 not significant enough. While the difference from Ghosh et al. (2022) is discussed it just remains superficial: the paper claims a $\\sqrt{H}$ improvement, which is no surprise because it studies the homogeneous setting.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KW_Q9Onkgkr", "reviewer": "Reviewer_65aT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies the model-free linear constrained Markov Decision Process with infinite horizon average rewards. The goal is to learn a policy for selecting actions that minimize the regret (the difference between the maximum achievable average reward and the policy's total average reward) while keeping the total constraint violations as low as possible.\n\nThe authors propose four different algorithms (the last two are policy-based algorithms) and show their sub-linear regret and constraint violation upper bounds. ", "summary_of_the_review": "This paper has some overlap with my current work. My recent work was focused on closely related topics and I am knowledgeable about most of the topics covered by the paper.", "strength_and_weaknesses": "**Strengths of paper:**\n1. Authors first propose an algorithm with $O(\\sqrt{d^3T})$ regret and constraint violation upper bounds, which has the tightest regret upper bound, but the algorithm is computationally inefficient. So they propose a computationally efficient algorithm that uses the primal-duel adaption of the LSVI-UCB algorithm but has $O((dT)^{3/4})$ regret constraint violation upper bounds. \n\n2. Under strong assumptions (Assumption 4 and Assumption 5), authors propose policy-based algorithms that are computationally efficient and have $O(\\sqrt{T})$ regret constraint violation upper bounds (or even constant constraint violation bound). \n\n3. No simulator (a common assumption) is needed to show the proposed algorithms' bounds.\n\n**Weakness of paper:**\n1. The assumptions for policy-based algorithms are too strong, which can limit their practical use. \n\n2. To show any algorithm to be \"provably sample-efficient,\" we need to have a lower bound. I didn't find any discussion or comparison with the lower bound in the main paper.\n\n3. It is unclear when the primal-dual algorithm and fixed episode length (to deal with infinite horizon) are used; then, the learned policy is also optimal. If the learned policy is sub-optimal, it can lead to linear regret and constraint violations.\n\n4. Empirical evaluations are weak. Even regret shown in Figure 1 (left) looks linear. \n\n\n\n**Question and other comments.** \n\nPlease address the above weaknesses. I have a few more questions:\n1. Would you give a few motivating examples (with what reward and utility functions) for your problem setting?\n2. What is $\\pi_1$ in Algorithm 1?\n\n\nA minor comment:\n1. Page 3, second last paragraph, second line:$j \\rightarrow \\diamond$.\n\n\nI am open to changing my score based on the authors' responses.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "IevM--xOX43", "reviewer": "Reviewer_2G2e", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper studies the infinite horizon average reward constrained Markov Decision Process (CMDP) for the model-free linear CMDP setup. The paper proposes 3 different algorithms under different assumptions or computation efficiency. The first algorithm is based on fixed-point optimization with optimism, which is to solve a very complicated optimism under uncertainty problem for every time step, which as the author/s pointed out, is very inefficient, but enjoys the \\tilt{O}(\\sqrt{T}) bound guarantee for both the regret and constraint violation. The second algorithm is computationally efficient but has worse bound of \\tilt{O}(T)^{3/4}, which is an extension of the previous work LSVI-UCB algorithm from the finite-horizon setting to the infinite one with additional analysis on the horizon truncation impact on the regret and constraint violation. The third algorithm, a primal-dual adaptation of previous work's algorithm MDP-EXP2, has stronger assumptions than the first two algorithms, which is both efficient and having \\tilt{O}(\\sqrt{T}) bound guarantee for both the regret and constraint violation.", "summary_of_the_review": "As I commented above, I think the paper tries to solve a meaningful problem in the RL area. But all the proposed efficient algorithms are heavily dependent on previous works and the theoretical results are incremental as well. ", "strength_and_weaknesses": "Strength:\n  1. The problem setup considered in this paper is infinite horizon average reward CMDP with linear function approximation, which is meaningful and interesting.\n  2. The theoretical results in both regret and constraint violation have improvements over existing works in the above mentioned specific problem domain. For example, the efficient algorithm 2 has better bounds of \\tilt{O}(T)^{3/4 compared with known one.\n  3. The paper is well-written and easy to read.\n\nWeakness:\n  1. The algorithm 2 and 3 are direct extensions of the existing algorithms in the literature with incremental efforts on having improved results in both regret and constraint violation bounds.\n  2. For the algorithm 2, the main difference is to show how to bound the gap between the best finite horizon policy and the infinite horizon case, which is obtained by Lemma 3 and its proof in the paper. The additional effort looks very incremental.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster