Concave Utility Reinforcement Learning with Zero-Constraint Violations
Authors: Mridul Agarwal
Qinbo Bai
Vaneet Aggarwal
Venue: Accepted by TMLR ()

Abstract: We consider the problem of tabular infinite horizon concave utility reinforcement learning (CURL) with convex constraints.
For this, we propose a model-based learning algorithm that also achieves zero constraint violations. Assuming that the concave objective and the convex constraints have a solution interior to the set of feasible occupation measures, we solve a tighter optimization problem to ensure that the constraints are never violated despite the imprecise model knowledge and model stochasticity. We use Bellman error-based analysis for tabular infinite-horizon setups which allows analyzing stochastic policies. 
Combining the Bellman error-based analysis and tighter optimization equation, for $T$ interactions with the environment, we obtain a high-probability regret guarantee for objective which grows as $\Tilde{O}(1/\sqrt{T})$, excluding other factors. The proposed method can be applied for optimistic algorithms to obtain high-probability regret bounds and also be used for posterior sampling algorithms to obtain a loose Bayesian regret bounds but with significant improvement in computational complexity.


Published in Transactions on Machine Learning Research (MM/YYY)
Concave Utility Constraint Violations
Reinforcement
Learning
with
Zero-
Mridul Agarwal
agana1808purdue.com edu
Purdue University
Qinbo Bai Purdue Universily
bail 1od113@@urrdeeccmm
Vaneet Aggarwal
naneet
Purdue Universily
Reviewed on OpenReview: https: // openreview. net/ farmm? id- WXVkkkPXRk
Abstract
We consider the problem tabular infinite horizon concave utility reinforcement learning (CURL) with convex constraints. For this, we propose model-based learning algorithm that also achieves zero constraint violations. Assuming that the concave objective and the convex constraints have a solution interior to the set of feasible occupation measures, we solve a tighter optimization problem to ensure that the constraints imprecise model knowledge and model stochasticity. We use Bellman error-based analysis for tabular infinite-horizon setups which allows analyzing stochastic policies. Combining the Bellman error-based analysis and tighter optimization equation, for T interactions with the environment, we obtaín high-probability regret guarantee for objective which grows as O(I/VT), excluding other factors. The proposed method can be applied for optimistic algorithms obtain high-probability regret bounds and also be used for posterior sampling algorithms to obtain a loose Bayesian regret bounds but with significant improvement in computational complexity.
never violated despite the
1 Introduction
In many applications where learning agent reinforcement learning to find optimal policies, the agent optimizes concave function of the expected rewards or the agent must satisfy certain constraints while maximizing an objective (Altman & Schwartz 1991 Roijers et al. 2013 For example, in network scheduling, controller can maximize lairness of the users using concave function of the average reward of each of the users (Chen et al. 2021]. Consider scheduler which allocates resource to users. Fach user obtains some reward based on their current state. The goal of the scheduler to maximize fairness among the users. However, there are certain preferred users for which some service level agreements (SLA) must be made. For this setup, the scheduler aims to find a policy which maximizes the fairness while ensuring the SLA constraints of the preferred users are met. Note that, here, the objective is a non-linear concave utility in the presence of raints on service level agreement. Setups with constraints also exist in autonomous vehicles where the goal is to reach the destination quickly while ensuring the safety of the surroundings (Le et al. 2019 Tessler et al. 2018). Further, an agent may aim to efficiently explore the environment by maximizing the entropy, which is a concave function of the distribution induced over the state and action space (Hazan et al. 2019
Owing to the variety of the use cases, recently, there has been significant effort to make RL algorithms for sctups with constraints, algorithms (Brantley et al. 2020, Yu et al.] (021) to primal-dual based model-free algorithms (Ding et al., 2021). Recently, ly, there has been a thrust. towards developing algorithms which can also achieve vero-constraint. violations in the learning phase well (Wei et al. 2022a Liu et al. 2021
concave utiltics, both. For episodic sctup, works range from model based
Bai et al.] 2022b). However, for

---

Published in Transactions on Machine Learning Research (MM/YYYY)
the episodic setup, the majority of the current works consider the weaker regret definition specified by Efroni let al. (2020) and only achieve zero expected constraint violations. Further, these algorithms require the Indge of a safe policy following which the agent does not violate constraints, or the knowledge of the Slater's gap 8 which determines how far a safe policy is from the constraint boundary.
The dcfinition which considers the average over time makes sense for an infinite horizon sctup as the long-tent term average is naturally defined (Puterman 2014). For a tabular infinite-horizen proposed an optimistic epoch-based algorithm. Much recently, Chen et. al. (2022) proposed an Optimistic Online Mirror Descent based algorithm. In this work, we consider the problem of maximizing concave utility of the expected rewards while also cnsuring that a set of convex constraints of the expected rewards are also satisfied. Moreover, we aim to develop algorithms that can also ensure that the constraints are not violated during the training phase as well. We work with tabular MDP with infinite horizon. For such setup, our algorithm updates policies it learns the system model. Further, our approach also bounds the accumulated observed constraint violations as compared to the expected constraint violations.
setup, [Singh et al. (2020)
For infinite horizon sctups for non-constrained sctup, the regret analysis has been widely studied (Fruit et al. 2018: Jaksch el al. 2010). However, we note that the dealing with constraints and non-linear setup requires additional attention because of the stochastic policies. Further, unlike episodic setup, the distribution at the epoch is not constant and hence the policy switching cost has to be accounted explicitly. Prior works in infinite horizon also faced this issue and provide some tools to overcome this limitation. [Singh al. (2020) builds confidence intervals for transition probability for every next state given the current state-action pair and obtains regret bound of ((T2/3). Chen et al. (2022) obtains regret bound of O(TM with S A) constraint violations for ergodic MDPs with T'M mixing time following an analysis which works with confidence intervals on both transition probability vectors and value functions.
To overcome the limitations mentioned in previous analysis and to obtain tighter result, propose an optimism based UC-CURL algorithm which proceeds in epochs e. At each epoch, we solve for an policy which considers constraints tighter by & than the true bounds for the optimistic MDP in the confidlence intervals for the transition probabilities. Further, as the knowledge of the model improves with increased interactions with the environment, we reduce this tightness. This c--sequence is critical to our algorithm as, if the sequence decays too fast, the constraints violations cannot be bounded by zero. If this sequence decays too slow, the objective regret may not decay fast enough. Further, using the sesuunnee,, we do not require the knowledge of the total time T for which the algorithm runs.
We bound our regret by bounding the gap between the optimal policy in the feasible region and the optimal policy for the optimization problem with e, tight constraints. We bound this gap with multiplicative factor of O(1/5), where ó is Slater's parameter. Based on our analysis using the Slater's parameter 6, we consider a case where a lower bound Ti on the time horizon T is known. This knowledge of Ti allows us to relax our assumption on 5.
Further, for the regret analysis of the proposed UC-CURL algorithm, we use Bellman error for infinite horizon setup to bound the difference between the performance of optimistic policy on the optimistic MDP and the true MDP. Compared to analysis of Jaksch et al.] (2010), this allows us to work with stochast policies. We bound our regret as Ö VA/T STMS A/T(1 1 p)) and constraint violations as O, where S and A are the number of states and actions respectively, L is the Lipschitz constant of the objective and constraint functions, d is the number of costs the agent is trying to optimize, and Thr is the mixing time of the MDP. The Bellman error based analysis along with Slater's slackness assumption also allows to develop posterior sampling based hods for constrained RL (see Appendix G by showing feasibility of the optimization problem for the sampled MDPs.
To summarize our contributions, we improve prior results on infinite horizon concave utility reinforcement learning setup on multiple fronts. First, we consider convex function for objectives and constraints. Second, even with a non-linear function setup, we reduce the regret order to STTSS/A/T and bound the constraint violations with O. Third, our algorithm does not require the knowledge of the time horizon T, safe policy, or Slater's gap 8. Finally, we provide analysis for postcrior sampling algorithm which improves both empirical performance and computational complexity.
2

---

Published in Transactions on Machine Learning Research (MM/YYY)
2 Related Works
Constrained RL: Altman 1999) builds the formulation for constrained MDPs to study constrained
reinforcement learning and provides algorithms for obtaining policios with known transition models. [Zengg & (0200) considered an episodic CMDP (Constrained Markov Decision Processos) and use an optimism based a algorithm to bound the constraint violation as Ó(1/Tu.25) with high probability. Kalagarla al.
Ratliff
also considered the episodic setup to obtain PAC-style bound for an optimism based algorithm. Ding 2021] considered the setup of H-episode length episodic CMDPs with d-dimensional linear function /T) by mixing the optimal policy with an exploration policy. Efroni et al. (020)) proposes a linear-progrant programming and primal-dual policy optimization algorithm to bound the regret as O(S H²/T)) Wei et al. (022a)) Liu et al. (2021) considered the problem of ensuring zero constraint violations using a model-Iree algorithm for tabular MDPs with linear rewards and constraints. However, for infinite horizon setups, the analysis from finite horizon algorithms does not directly hold. This is because finite horizon setups can update the policy after every episode. But this policy switch modifies the induced Markov chains which takes time to converge to a stationary distribution.
[2021
et al.
approximation to bound the constraint violations as
Xu et al. (2021) considered an infinite horizon discounted setup with constraints and obtain global convergence using policy gradient algorithms. Bai et al. (2022b) proposed a conservative stochastic model-free primal-dual algorithm for infinite horizon discounted setup. Ding et al. (2020): Bai al. (2023) also considered an infinite horizon discounted setup with parametrization. They used natural policy gradient to update the primal variable and sub-gradient descent to update the dual variable, In addition to the above results on discounted MDPs, the long-term rewards have also been considered. [Singh ct al. (2020) considered the setup of infinite-horizon ergodic CMDPs with long-term average constraints with optimism based algorithm. Gattami el al. (2021) analyzed the asymplotic performance for Lagrangian based algorithms for infinite-horizn long-term average constraints, however they only show convergence guarantees without. explicit convergence rates. Chen et al. 2022) provided an optimistic online mirror descent algorithm for ergodic MDPs which obtain regret bound of O(TM SvSA), and Wei al. (002bb) provided model free SARSA algorithm which obtains a regret bound of O(V SAT5/6) for constrained MDPs. Agarwal et al.
(222bb proposed a posterior sampling basod algorithm for infinite horizon sctup with a regret of S(TM)VAT) and constraint violation of SVTM)
Algorithm(s)
Setup
Regret
Constraint Violation O(H522$ /A/K)
Non-Linear
ConRL Brantley et al.
2020
FH
OLLH5/2S A/K)
Yes
MOMA Yu et al. 2021
FH
OLH SA/K)
0(H /SA/K)
Yes
TripleQ Wei et al. 2022a
FH
OOHHASAK-
No
OptPess LP
Liu et al.
2021)
FH
O( A/3A
0 O(H'S
No
OpttPss-Priman Dual (Liu et al.
2021
FH
O( 5 AS3A/K)
No
UCRI-CMDP Singh et al.
2020)
TH
O(VSAT-133)
OLVSA/TV/)
No
Chen et al.
Chen et al.
2022)
IH (STMS)SAATT
O T
No
Wei et al.
(Wei et al. 2022b)
TH V/VSAT-V/6
No
Agarwal et al. [Agarwal et al. 2022b
IH
O(TMSVA/T) (/LTT)
O /A/T)
No
UC-CURL (This work)
IH
Yes
Table 1: Overview of work for constrained reinforcement learning setups. For finite horizon (FH) setups, // is the episode length and K is the number of episodes for which the algorithm runs. For infinite horizon (IH) setups, T' denotes the mixing time of the MDP, and T is the time for which algorithm runs. L is the Lipschitz constant. We note that all the IH setups assume ergodic MDPs, where the FH sctups do not require the ergodic assumption as the system resets to the final state after every episode.
Concave Utility RL: Another major research area related to this work is concave utility RL Hazan et al, 2019). Along this direction, Cheung (2019) considered a concave function of expected per-step vector reward and developed an algorithm using Frank-Wolfe gradient of the concave function for tabular infinite horizon MDPs. Agarwal & Aggarwal 20222 Agarwal et al. (2022a) also considered the same setup using a posterior sampling based algorithu. Recently, Brantley el al. (2020) combined concave utility reinforcement. learning
and constrained reinforcement learning for an episodic setup. Yu et. al. (0211 also considered the case of
3

---

Published in Transactions on Machine Learning Research (MM/YYY)
episodic setup with concave utility RL. However, both BBratleey et al. 2020 and Yu et al. 2021 consider the weaker regret definition by Efroni et al. 2020), and Cheung (201)) 9:: Yu et al. (2021) do not larget the convergence the policy. Further, these works do not target rero-constraint violations. Recently, policy gradient based algorithms have also been studied for discounted infinite horizon setup (Bai et al. 2022ap.
Another parallel line of work in RL which deals with concave utilities variational policy gradient (Zhang et al. 2021 2020). However, they consider discounted MDPs whereas we consider undiscounted setup for our work.
Compared to prior works, we consider the constraincd reinforcement learning with convex constraints and concave objective function. Using infinite-horizon setup, we consider the tightest possible regret definition. Further, we achieve zero constraint violalions with objective regrel light in T using optimization problem with decaying tightness. A comparative survey of key prior works and our work is also presented in Table
3 Problem Formulation
We consider ergodic tabular infinite-horizon constrained Markov Decision Process M ca. P. o). S is finite set of S states, and A is a finite set of A actions. P: S x A + A(S) denotes the transition probability distribution such that on taking action a E A in state s S, the system moves to state s' E S with probability a() denotes the average reward obtained and average costs incurred in state action pair (8.a) E E x A, and Φ is the distribution over the initial state.
S x A - [0, 1] and S x A + [0, 1]. 1,.... ,d
The agent interacts with M in time-steps E 1, ... for total of T' time-steps. We note that T is possibly unknown and 81 ~ Φ. At each time I, the agent observes stale 8t and plays action az- The agent selects an action on observing the state s using a policy π S A(A), where ((A) is the probability simplex on the action space. On following a policy π, the long-term average reward of the agent is denoted as:
lim ET.P x
Σ r(s,, at)/T
(1)
where P|-] denotes the expectation over the state and action trajectory generated from following π on transitions P. The long-len average reward can also be represented as:
X = E, ())ss))
= lim lim (111-)) VSES
7-1
where (s) is the discounted cumulative reward on following policy म, and of E A(S x A) is the steady- state occupancy measure generated from following policy и on MDP with transitions PPuterman 2014 Similarly, we also define the long-term average costs as follows:
of = lim Ex.P E (i(s, lim (1 (1- VV)V VsES --220
7-1
= E (s)
The agent interacts with the CMDP M for T time-steps in an ouline manner and aims to maximize a function
ʃ : [o, 1] I of the average per-step reward. Further, the agent attempts to ensure that a function of average per-step costs g (0, 1]d R at most O. In the hindsight, the agents wants play policy x² which which satisfies:
max f (1F) s.t. g ( ,f() 0o
(3)
Let Pt - P. denote the t-step transition probability following policy æ in MDP M starting from some state 8 where (+]+)) = E. ((1s)))( Let T denote the time taken by the Markov chain induced by the policy to hit state s' starting from state Further, let Tas == max, E be the mixing time of the MDP M. We now introduce our assumptions the MDP M.
4

---

Published in Transactions on Machine Learning Research (MM/YYY)
Assumption 3.1. For MDP M, we have | P+ll Cp' with Ps being the long-term steady state distribution induced by policy n, and C > 0 and < are problem specific constants. Additionally, the mixing time of the MDP M if finite or TM < xo. In other words, the MDP, M, ergodic.
Assumption 3.2. The rewards r(s, a), the costs (((,,))V i, and the functions f and g are known to the agent.
Assumption 3.3. The scalarization function f is jointly concave and the constraints g are jointly convex. Hence for any arbitrary distributions D and 22, the following holds.
f (BanD, [x]) 2 Eg [f (a)] (Ex~D, (x]) & Ex-D, lg (x)]; x E IR"
(4)
(5)
Assumption 3.4. The function I and g are assumed to be a L- Lipschitz function, or
(a)) (v)) M yii ZHER lg (x) - g (y) s L|| 1 yll, x,y
(6)
(7)
Remark 3.5. We consider a standard setup of concave and the Lipschitz function as considered by Cheung (2019) Brantley et al. (2020g; ; Yu et al.] (2021). Note that the analysis in this paper directly works for +R, where the function takes as input K average per-step rewards for K objectives.
Remark 3.6. For non-Lipshitz continuous functions such as entropy, we can obtain maximum entropy exploration if choose function f == - Ex ds log(As + 7) with (x(s, a) 1 [sy,a.) for a particular state action
pair Sk, ag and choosing K S x A to cover all state-action pairs and regularizer 1) (Hazan et al. 2019).
Assumption 3.7. There exists policy and one constant 8 8> LdSTM Maloo/AAooooo (AlogT)/T++CSS (CS log (T p)) such that
(.) g (1), (1),,,,,,,,,))) ( -88
This assumption is again a standard assumption in the constrained RL literature Efroni et al. 2020 Ding
et al. 2021 2020 Wei et al.) 2022a). 8 is referred as Slater's ' constant. Ding et al. 2021)) assumees that the Slater's constant is known. Wei et al. (2022a) assumes that the number of iterations of the algorithu is at least ((SAH/6)) for episode length H. On the contrary, we simply assume the existence of 8 and lower bound on the value of 8 which gets relaxed as the agent acquires more time to interact with the environment.
Any online algorithm starting with no prior knowledge will need to obtain estimates of transition probabilities P and obtain reward and costs ck, V k E {1,... ,d), for cach state action pair. Initially, when algorithm does not have good estimate of the model, it accumulates a regret as well as violates constraints as it does not know the imal policy. We define reward regret. R(T) as the difference between the average cumulative reward obtained vs the expected rewards from running the optimal policy x² for T steps,
(Er, r(se, at)/T)
R(T) (
Additionally, we define constraint regret C(T) as the gap betweon the constraint function and incurred and constraint bounds,
C(T) c(T)=(1) am=
at)/T. (()(\\/aaaa))))))
( .T. calse, ca(se, a)))r)) where(x)+ max(0,
In the following section, we present model-based algorithm to obtain this policy n", and reward regret and the constraint regret accumulated by the algorithm.
4 Algorithm
We now present our algorithu UC-CURL and the key ideas used in designing the algorithm. Note that if the agent is aware of the true transition P. it solve the following optimization problem for the optimal
5

---

Published in Transactions on Machine Learning Research (MM/YYYY
feasible policy.
max S( J(E,
r(s,a)p(s,a))
(9)
p(s.a)
s,
with the following set of constraints,
sa p(, -0 p(s,a) 20
(10)
pl' .(s = -E P(dl\s,a)p(s..a
(11)
9( <. ((),))p(s,a);.. Σ ca(s,a)p(s,a)) 0
(12)
for all s' E S, E and V a E A. Equation 11 denotes the constraint on the transition structure for
the underlying Markov Process. Equation 10 ensures that the solution is a valid probability distribution.
Finally, Equation [12 are the constraints for the constrained MDP sctup which the policy must satisfy. Using the solution for p, we can obtain the optimal policy as:
p(s,a) T" (als) EsEA A s
(13)
However, the agent does not have the knowledge of P solve this optimization problem, and thus starts lcarning the transitions with an arbitrary policy. We first note that if the agent does not have complete knowledge of the transition P the true MDP M, it should be conservative in its policy to allow room to violate constraints. Based on this idea, we formulate the e-light optimization problem by modifying the constraint in Equation 12 as.
g( Σ s,a (s) E., ca(s, ((),,) S -e
(14)
Let Pe be the solution of the e-tight optimization problem, then the optimal conservative policy becomes:
(als) Pc(s,a) V s.a EDEAPh(s,
(15)
We now ready to design algorithm UC-CURL which is based the optimism principle (Jaksch) et al. 2010). The UC-CURL algorithm is presented in Algorithm [ The algorithm proceeds in epochs e. The algorithm maintains three key variables (2(8,a), a), Ne(s, a), and P(s,a,s') for all 8, Me a) stores the number of times state-action pair (s, a) are visited in epoch e. Ne(s, a) stores the number of times (s, are visited till the start of epoch e. P(s,, a') stores the number of times the system transitions to state s' after laking action in state 8. Another key parameter of the algorithm is K Le)/te where 4, is the start time the epoch and K is a configurable constant. Using these variables, the agent solves for the optimal e conneerrvttive policy for the optimistic MDP by replacing the constraints in Equation (I1 by:
Encr p(s',a) S E p=(s((s,a)p(s.a)
(16)
Pa(5'ls,)) > 0. E, ac(5'1s,a)=1
(17)
a(s,a,))
log(At)
[PP((1s.a) Iv) |1 V 1 (v.
(18)
for all s' E S, E S, and Ya E A and x V max(#, y). Equation 18 ensures that the agent searches for optimistic policy the confidence intervals of the transition probability estimates.
Combining the right hand side of 16 with 10 gives
Σ 80
P.(3()).))p(s..) = =1 =E, ,)

---

Published in Transactions on Machine Learning Research (MM/YYN)
Algorithm UC-CURL
Parameters: K
Input: 5, A, r, d, q [d] [d]
1: Let t= 1, e 6= 1, = /V Int
2: for (s,a) E S A do
3: Ve(s,a)= = 0, (s, = 0, P(s',a,s) 0v o' E
4: end for
5: Solve for policy Te using Eq. 19
for E (1, do
Observe St, and play at Te(
Observe s,+1, r(s,, ar) and (i(s), Vie
Ve(si, ar) = (s) a+)+1 +1
10:
P( ae (1, (t+1) = P( dz: 8441) +1
11:
if ae(s,a) ma Ne(s,a)} for any 8, then
12:
for (5, E 8 Ao do
13:
Ne.1(s,a) = (s, + av
14:
e == 1= u,(s, =
15:
end for
16: 6. k Int
t
17: Solve for policy ne using Eq.
19
18: end if
19:
end for
Thus, joint with (16), we see that equality in 166 will be satisfied at the boundary as Σg p(s', a) for some s' can never exceed the boundary to compensate for another and hence, for all s E. P(s', ,'', a) will lie on the boundary. In other words, the above constraints give P(s', = -E.o Pc(5 p(s, a). Further, we note that the region for the constraints is convex. This is because the set {z, v, ay 2 2} is convex when x. F.y, 2 We note that even though the optimization problem may look non-convex due to constraints having product of two variables, We expand more on this in Appendix B We note that (Rosenberg & Mansour 2019 provide another approach to obtain convex optimization problem for optimistic MDP.
Equations (0) (14,, and [16]-[18 form convex optimization problem.
Let Pe be the solution for ee-tight optimization equation for the optimistic MDP. Then, obtain the optimal conservative policy for epoch as:
(a(s))) (s) EbEAPe (s s,a
(19)
The agent plays the optimistic conservative policy ne for epoch Note that the conservative parameter e, decays with time. As the agent interacts with the environment, the system model improves and the agent does not need to be as conservative as before. This allows us to bound both constraint violations and the objective regret. Further, if during the initial iterations of the algorithms conservative solution is not feasible, we ignore the constraints completely. We will show that the conservation behavior is required when f = O(T) to compensate for the violations in the initial period of the algorithm E.2
For the UC-CURL algorithm described in Algorithm we choose (cc) = { KK / (log te)te)) However, if the agent has access to a lower bound T, (Assumption 3.7 on the time horizon T, the algorithm can change the
6, = K (ln(t, TL, V Ti) < 8 in each epoch e as follows. Note that if Ti = O, e. becomes as specified Algorithm T and if T T, ée becomes constant for all epochs e.
7

---

Published in Transactions on Machine Learning Research (MM/YYN)
5 Regret Analysis
After describing UC-CURL algorithm, we now perform the regret and constraint violation analysis. We note that the standard analysis for infinite horizon tabular MDPs of UCRL2 (Jaksch et al. 2010) cannot be directly applied as the policy Te is possibly stochastic for every epoch. Another peculiar aspect of the analysis of the infinite horizon MDPs is that the regret grows linearly with the number of epochs (or policy switches). This is because a new policy induces a new Markov chain and this chain take time to converge to the stalionary distribution. The analysis still bounds the regret by Ö(TMS A/T) as the number of epochs are bounded by Al T)
Before diving into the details, we first define few important variables which are key to our analysis. The first variable is the standard Q-value function. We define Q7 as the long term expected reward on taking action a in state s and then following policy л for the MDP with transition P. Mathematically, we have
((s,a)-((s00) + +vves P(s')s, (s'); (.) = Eewa (s,""s,,)) (s.
We also define Bellman error Ba.P (s, a) for the infinite horizon MDPs as the difference between the cumulative expected rewards obtained for deviating from the system model with transition p for one step by taking action in state and then following policy We have:
(r, = -iim (s, - - Eves P(d)s,,,v) 7-1
(20)
After defining the key variables, we can now jump into bounding the objective regret R(T). Intuitively, the algorithm incurs regret on three accounts. First source is following the conservative policy which require to limit the constraint violations. Second source of regret is solving for the policy which is optimal for the optimistic MDP. Third source of regret the stochastic behavior of the system. We also note that the constraints are violated because of the imperfect MDP knowledge and the stochastic behavior. However, the conservative behavior actually allows us to violate the constraints within some limits which we will discuss in the later part of this section.
We start by stating our first lemma which bounds the regret due to solving for a conservative policy. We define 6 tighttht optimization problem as optimization problem for the true MDP with transitions P with Eg. We bound the gap between the value of function f at the long-term expected reward of the policy for Ce-tight optimization problem and the truc optimization problem (Equation (1-(12) in the following lemma.
Lemma 5.1. Let X be the long-lerm average reward following the optimal feasible policy n² for the true MDP M and let X be the long-term average rewards following the optimal policy Te for the tight optimization problem for the true MDP M, then for Ee S 8, we have,
(f 2Le//6
(21)
Proof Sketch. We construct a policy for which the steady state distribution is the weighted average of two steady state distributions. First distribution is for the optimal policy for the truc optimization problem. Second distribution is for the policy which satisfies Assumption 3.7 We show that this constructed policy satisfies the ti-hitht constraints. Further, using Lipschitz continuity, we convert the difference between function values into the difference between the long-term average rewards to obtain the required result. The detailed proof is provided in Appendix C
Lemma 5.1 and our construction of c. sequence allows us to limit the growth of regret because of conservative policy by O AAAT).
To bound the regret from the second source, we use Bellman error based analysis. In our next lemma, we show that the difference between the performance of a policy two different MDPs is bounded by long-term averaged Bellman error. Formally, we have:
The difference of long-term average rewards for running the optèmistic policy the optimistic MDP, M and the average long-term average rewards for ranning the optimistic policy ne on the
Lemma 5.2.
8

---

Published in Transactions on Machine Learning Research (MM/YYY)
true MDP, No. is the long-term average Bellman error
L xx
-o--_ = =E,, p B (8,a)
(22)
Proof Sketch. We start by writing Q7 in terms of the Bellman error. Subtracting Vi from V and using the fact that X = =imm, VT.P and Nox lim VT,le, we obtain the required result. A complete proof is provided in Appendix D.3
After relating the gap between the long-term average rewards of policy on the two MDPs, we aim to bound the sum of Bellman error over an epoch. For this, we first bound the Bellman error for a particular state action pair (s,a) in the following lemma. We have,
Lemma 5.3. With probability at least 1 - 1/t6, the Bellman error (s a) for state-action pair (8, a) in epoch E is upper bounded as
14S1og(2AT)
(s) - V (v |//l000
(23)
where (e(s. a) is the number of visitations to (s till epoch e and h is the bias of the MDP with transition probability Pe.
Proof Sketch. We start by noting that the Bellman error essentially bounds the impact of the difference in value obtained because of the difference in transition probability to the immediate next state. We bound the difference in transition probability between the optimistic MDP and the true MDP using the result from [Weissman et al. 2003 This approach gives the required result. A complete proof provided in Appendix
D.3
We use Lemma 5.2 and Lemma 5.3 bound the regret because of the imperfect knowledge of the system model. We bound the expected Bellman error in epoch starting from state st, and action a2 by constructing a Martingale sequence with filtration Ft = {$1, a1.-.. St-1, a-11 and using Azuma's incquality (Bercu et al. 2015). Using the Azuma's inequality, we can also bound the deviations because of the stochasticity of the Markov Decision Process. The result is stated in the following lemma with proof in Appendix D
Lemma 5.4. With probability at least - 7-1 the regret incurred from imperfect model knowledge and process stochastics is bounded by
(TTMSVA(log AT)/T + S Alog T)/(1-111))) p))
(24)
The regret analysis framework also prepares us to bound the constraint violations as well. We again start by quantifying the reasons for const.raint violations. The agent violates the constraint because 1. it is playing with the imperfect knowledge of the MDP and 2. the stochasticity of the MDP which results in the deviation from the average costs. We note that the conservative policy He for every epoch does not violate the constraints, but instead allows the agent to manage the constraint violations because of the imperfect model knowledge and the system dynamics.
We note that the Lipschitz continuity of the constraint function allows us convert the function of d averaged costs to the sum of d averaged costs. Further, we note that we can treat the cost similar to rewards (Brantley et al. 2020). This property allows us to bound the cost incurred incurred in a way similar to how we bound the gap from the optimal reward by LdTx A(log AT)/T. We now want that the slackness provided by the conservative policy should allow LdTx A(log AT)/T constraint violations. This is ensured by our chosen eg sequence. We formally state that result in the following lemma proven in parts in Appendix D and Appendix E
Lemma 5.5. The cumulative sum of the ee sequence is upper and lower bounded as
Σ e=1 (lo41 - le)ee = θ /Vogl
(25)
9

---

Published in Transactions on Machine Learning Research (MM/YYYY)
After giving the details bounds the possible sources of regret and constraint violations, we can formally state the result in the form of following theorem.
Thcorem 5.6. For all T and K = G(LdT CSA(11 is bounded as
(1-//1100)) the regret R(T) of UC-CURL algorithm
B(T)= (f
log AT CT log
A
(26)
[)T
and the constrannis are bounded as C(T) =0)==0,- with probobility at least 7-/4.
5.1 Posterior Sampling Algorithm
We can also modify the analysis to obtain Bayesian regret for a posterior sampling version of the UC-CURL algorithm using Temma 1 of (Osband et al.) 2013). In the posterior sampling algorithm, instead of finding the optimistic MDP, we sample the transition probability Pa using an updated posterior. This sampling allows to reduce the complexity of the optimization problem by eliminating Eq. (17 and Eq. (18). The complete algorithm is described in Appendix G We note that optimization problem for the UC-CURL algorithm is feasible because the true MDP lies in the confidence interval. However, for the sampled MDP obtaining the feasibility requires a stronger Slater's condition.
5.2 Further Modifications
The proposed algorithm, and the analysis can be easily extended to M convex constraints 91.-.. .MM by applying union bounds. Further, our analysis uses Proposition 1 of (Jaksch et al. 2010 to bound the epochs by O(SA loga T). However, we can improve the empirical performance of the UC-CURL algorithm by modifying the epoch trigger condition (Line 11 of Algorithm []. Triggering new episode whenever ve(s, a) becomes max(1, (s, a) + 1] for any state-action pair results in a linearly increasing episode length with total epochs bounded by O(SA+ VSAT). This modification results in better empirical performance (See Appendix G for simulations) at the cost of a higher theoretical regret bound and computation complexity for obtaining a new policy every epoch.
6 Simulation Results
To validate the performance of the UC-CURL algorithm and the PS-CURL algorithm, we run the simulation on the flow and service control in single-serve queue, which was introduced in (Altman & Schwartz, 1991|
Along with validating the performance of the proposed algorithms, we also compare the algorithms against the algorithms proposed in (Singh al. 2020) and in (Chen al. 2022 for model-based constrained reinforcement learning for infinite horizon MDPs. Compared to these algorithms, note that our algorithm is also designed to handle concave objectives of expected rewards with convex constraints on costs with 0 constraint violations.
In the queue environment, a discrete-time single-server queue with a buffer of finite size L is considered. The number of customers waiting in the queue is considered as the state in this problem and thus = 1. Two kinds of the actions, service and flow, are considered in the problem and control the number of customers together. The action space for service is finite subset A in [amin- @maz), where O < amin S amaar < 1. Given a specific service action a, the service a customer is successfully finished with the probability is successful, the length of the queue will reduce by 1. Similarly, the space for flow is also a finite subsection B in [Iminn bmaa]. In rast. to the service action, flow action will increase the queue by 1 with probability the specific flow action 6 is given. Also, we assume that there no customer arriving when the queue is full. The overall action space is the Cartesian product of the and B. According to the service and flow probability, the transition probability can be computed and is given in the Table 2
the service
Define the reward function as r(s, a, b) and the constraints for service and flow as ct, a, b) and c² a, b), respectively. Define the stationary policy for service and flow as na and He. respectively. Then, the problem
10

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Table 2: Transition probability of the queue system
Current State
P(x++1 2t 1)
P41+11 24)
P(x+41 = 24 1)
15 0t <
a(1
ab + (1 a)
(1 a)b
Ft- L
a
1-6
I; 0
b(1 a)
b(1
4.30
0.25
0.00
4.00
3.75
-0.50
3.25
-0.75
Chen al
Chen (B)
PS: CURL Inner epocns
-1.00
PS-CURL liner eoochs
FS CURL doubling epochs
PS-CURL doubling apechs
CURL spochs
CURL
epochs
coubling epochs
(20)
Singh [28]
2.50
-1.50
400000
102 stops
(a) Reward growth w.r.t. time
(b) Regret w.r.t. time
1.0
0.-
constrant Value
0.6
Incar opacss
CURL, doubling epochs
UC- JC-C lnner epocts
0.01
0.4
UC CURL doubling spochs
Singh
[B]
P5 CURL Inear spocts
-0.5
PS-CURL doutling epochs
02-
UC CURL Inear spochs
doub
0.0
-1.0
100000
200000
300000
400000 500000
100000
200000
300000
400000
500000
(c) Service constraints w.r.t. time
(d) Flow constraints w.r.t. time
Figure Performance of the proposed UC-CURL and PS-CURL algorithms on a flow and service control problem for single queue with doubling epoch lengths and linearly increasing epoch lengths. The algorithms are compared against Chen al. (0022) and Singh et al. (2000)
can be defined as
lim To
r(s,, n (8)),
To
T
s.l.
lim
dl (st, na (81,, Tb(2))) 20
(27)
T+x
T
lim T-00
Σ
(s,, na (sx), 2
According to the discussion in (Altman & Schwartz 1991 we define the reward function as r(s, a, b) 8, which is decreasing function only dependent the state. It is reasonable to give higher reward when the
11

---

Published in Transactions on Machine Learning Research (MM/YYY)
number of customers waiting in the queue is small. For the constraint function, we define (ss,,, = 10a + 6 and c² = -8(1 - +2,+2,, value is given if the probability for the service and flow are low and high, respectively.
2, which are dependent only on service and flow action, respectively. Higher constraint.
In the simulation, the length of the buffer is set L 5. The service action space is set as [0.2, 0.4, 0.6, 0.8) and the flow action space is set as [0.4, 0.5, 0.6, 0.7]. We use the length of horizon T = 5 x 10 and run 50 independent simulations of all algorithms. The experiments were run on 36 core Intel-i9 CPU @3.00 GHz with 64 GB of RAM. The result. is shown in the Figure [] The average values of the cumulative reward and the constraint functions are shown in the solid lines. Further, we plot the standard deviation around the mcan value in the shadow to show the random error. In order to compare this result to the optimal, we assume that the full information of the transition dynamics is known and then use Linear Programming to solve the problem. The optimal cumulative reward for the constrained optimization ion is calculated to be 4.48 with both flow constraint and service constraint values to be O. The optimal cumulative reward for the unconstrained optimization is 4.8 with service constraint being- -2 and flow constraint being -0.88.
We now discuss the performance of all the algorithms starting with our algorithms UC-CURL and PS-CURL. In Figure [ we observe that the proposed UC-CURL algorithm in Algorithm [ does not perform well initially. We observe that this is because the confidence interval radius V log(AL)/N [s)]Ns a) for any (s, are not tight enough in the initial period. After the algorithms collects sufficient samples to construct tight confidence intervals around the transition probabilities, the algorithm starts converging towards the optimal policy. We also note that the linear epoch modification of the algorithm works better than the doubling epoch algorithm presented in Algorithm [ This is because the linear epoch variant updates the policy quickly whereas the doubling epoch algorithm works with the same policy for too long and thus looses the advantages of collected samples. For our implementation, we choose the value of parameter K in Algorithm 1 as K = 1, using which we observe that the constraint values start converging towards zero.
We now analyse the performance of the PS-CURL algorithm. For our implementation of the PS-CURL algorithm, we sample the transition probabilities using Dirichlet distributtin. Note that the true transition probabilities were not sampled from a Dirichlet distribution and hence this experiment also shows the robustness against misspecified priors. We observe that the algorithm quickly brings the reward close to the optimal rewards. The performance of the PS-CURL algorithm is significantly better than the UC-CURL algorithm. We suspect this is because the UC-CURL algorithm wastes a largo-numbe number of steps to find optimistic policy with a large confidence interval. This observation aligus with the TDSE algorithm (Ouyang ct al., 2017), where they show that the Thompson sampling algorithm with ((VSAT) epochs performs empirically better than the optimism based UCRL2 algorithm (Jaksch et al.] 2010) with O(VSA T) epochs. (Osband et al. 2013) also made similar observation where their PSRL algorithm worked better than the UCRL2 algorithm. Again, we set the value of parameter K as 1 and with K = 1, the algorithm does not violate constraints, We also observe that the standard deviation of the rewards and constraints are higher for the PS-CURL algorithm as compared to the UC-CURL algorithm as the PS-CURL algorithm has an additional stochastic component which ariscs from sampling the transition probabilities.
A After analysing the algorithms presented in this paper, we now analyse the performance of the algorithm by Chen et al. (2022). They provide an optimistic online mirror descent algorithm which also works with conservative parameter to tightly bound constraint violations. Their algorithm also obtains a O(VT) regret reward/constraint cconstriint setup with a single constraint, and empirically the algorithm is difficult to tune as it requires additional knowledge of TM, P, 8, and T to fine tune parameters used in their algorithm. We set the value of the learning rate 0 for online mirror descent as 5 x 10-² with an episode length of 5 x 10 Further, we scale the rewards and costs to ensure that they lic between 0 and 1. We analyze the behavior of the optimistic online mirror descent algorithm in Figure Ib We observe that the algorithm has three phases. The first. phase is the first episodes where the algorit him uses a uniform policy which is the initial flat area till first 5000 steps. In the second phase, the algorithm updates the policy for the first time and starts converging to the optimal policy with a convergence rate which matches to that of the PS-CURL algorithm. However, after few policy updates, we observe that the algorithm has oscillatory behavior which is because the dual variable updates require online constraint violations.
bound. However, their algorithm is designed for a linear reward/
Finally, we analyze the the algorithm by Singh et al. 2020 They also provide an algorithm which proceeds in epochs and solves an optimization problem at every epoch. The algorithm considers fixed epoch length T1/3, Further, the algorithun considers a confidence interval on each estimate of P(8'|8, a) for all 8, s
12

---

Published in Transactions on Machine Learning Research (MM/YYYY)
triplet. The algorithm does not perform well even though it updates the policy most frequently because of creating confidence intervals on individual transition probabilities P(s 18, a) instead of the probability vector a))
From the experimental observations, we note that the proposed UC-CURL algorithm is suitable in cases where the paramcter tuning is not possible and the system requires tighter bounds on deviation of the performance of the algorithm. The PS-CURL algorithm can be used in cases where the variance in algorithm's 's performance can be tolerated computation aional complexity is constraint. Further, for both the algorithms, it is beneficial to use the linear increasing epoch lengths. Additionally, the algorithm by Chen et al. (2022) is suitable for cases where solving an optimization equation is not fcasible, for example an embodded system, as the algorithm updates policy using exponential function which can be easily computed. However, this algorithm is only applicable in applications with linear swward/constradd and single constraint.
7 Conclusion
We considered the problem of Markov Decision Process with concave objective and convex constraints. For this problem, we proposed UC-CURL algorithm which works on the principle of optimism. To bound the constraint violations, we solve for conservative policy using an optimistic model for an c-tight optimization problem. Using an analysis based on Bellman error for infinite- algorithum achieves 0 constraint violations with a regret bound of S + (CSAlog') () p)). Further, reduce the computation complexity of finding optimistic MDP, we also propose posterior sampling algorithm which finds the optimal policy for a sampled MDP. We provide a Bayesian regret bound of OS A/T SS A (oogT)((((L)) - p)) for the posterior sampling algorithm by considering a stronger Slater's condition to solve for constrained optimization for sampled MDPs well. As part of potential future works, we consider dynamically configuring K to be an interesting and important direction to reduce the requirement of problem parameters.
MDPs, we show the UC-CURL
References
Mridul Agarwal and Vaneet Aggarwal. Reinforcement learning for joint optimization of multiple rewards.
Accepted Journal of Machine Learning Research, 2022.
Mridul Agarwal, Vancet Aggarwal, and Tian Lan. Multi-objective reinforcement learning with non-lincar scalarization. In Proceedings of the 21st International Conference on Autonomous Agents and Multiogent Systems, pp. 17, 2022a.
Mridul Agarwal, Qinbo Bai, and Vancet Aggarwal. Regret guarantees for model-basee reinforcement learning with long-term average constraints. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022b.
E. Altman and A. Schwartz. Adaptive control of constrained markov chains. IEEE Transactions on Automatic Control, 36(4):454 462, 1991. doi: 10.1109/9.75100
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Qinbo Bai, Mridul Agarwal, and Vaneet Aggarwal. Joint optimization of concave scalarized multi-objective reinforcement learning with policy gradient based algorithm. Journal of Artificial Intelligence Research, 74: 1565 1597, 2022a.
Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving zero constraint. violation for constrained reinforcement learning via primal-dual approach. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 36, pp. 3682 3689, 2022b.
Qinbo Bai, Amrit Singh Bodi, and Vancot Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via conservative natural policy gradient primal-dual algorithm. In Proceedings of the AAAI Conference on Artificial Intelligence, 2023.
Bernard Bercu, Bernard Delyon, and Emmanuel Rio. Concentration inequalilies for sums and martingales. Springer, 2015.
13

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Kianté Brantley, Miro Dudik, Thodoris Lykouris, Sobhan Miryoosefi, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun. Constrained episodic reinforcement learning in concave-convex and knapsack set singsngs. Advances Neural Information Processing Systems, 33:16315-16326, 2020.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and TrendslB in Machine Learning, ((3-4):231-38) 357, 2015.
Jingdi Chen, Yimeng Wang, and Tian Lan. Bringing fairness to actor-critic reinforcement learning for network utility optimization. In IEEE INFOCOM 2021-IEEE Conference on Computer Communications, pp. 1-. IEEE, 2021.
Liyu Chen, Rahul Jain, and Haipeng Luo. Learning infinite-horizon averago-reward Markov decision process with constraints. In Kamalika Chaudhuri, Stefanic Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 3246-3270. PMLR, 17-23 23 Jul 2022.
Wang Chi Cheung. Regret minimization for reinforcement learning with vectorial feedback and complex objectives. Advances in Newral Information Processing Systems, 32:726-7355 -36,, 2019.
Wei Cui, Kaiming Shen, and Wei Yu. Spatial deep learning for wireless scheduling. ieee journal on selected areas in communications, 37(6):1248 1261, 2019.
Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo Jovanovic. Natural policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Information Processing Systems, 33, 2020.
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligence and Stalistics, pp. 3304 3312. PMLR, 2021.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration--explitttiin in constrained mdps. arXic preprinl ar XrXi::2003.02. 02189, 2020.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-span-constrrined exploration-exploiiatioon in reinforcement learning. In International Conference on Machine Learning, pp. 1578-1586 1586. PMLR, 2018
Ather Gattami, Qinbo Bai, and Vaneet Aggarwal. Reinforcement learning for constrained markov decision processes. In International Conference on, Artificial Intelligence and Statistics, pp. 2656-22666 -6664 PMLR, 2021.
Seyed Kamyar Seyed Ghasemipour, Richard Zemel, and Shixiang Gu. A divergence minimization perspective imitation learning methods. In Conference Robot Learning, pp. 1259-1277. PMLR, 2020.
Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Socst. Provably efficient maximum entropy exploration. In International Conference on Machine Learning, pp. 2681 2691. PMLR, 2019.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Arr):1563 1600, 2010.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pp. 1724-1732. PMLR, 2017.
Krishna C Kalagarla, Rahul Jain, and Picrluigi Nuzzo. A sample-cfficient algorithm for episodic finito-horizon mdp with constraints. 35(9):8030-800) 8037, 2021.
Raymond Kwan, Cyril Leung, and Jie Zhang. Proportional fair multiuser scheduling in Itc. IEEE Signal Processing Lellers, 16(6):461-46) 2009.
Tian Lan, David Kao, Mung Chiang, and Ashutosh Sabharwal. An axiomatic theory of fairness network resource allocation. TEFE, 2010.
14

---

Published in Transactions on Machine Learning Research (MM/YYYY)
J Langford and S Kakade. Approximately optimal approximate reinforcement learning. In Proceedings of ICML, 2002.
Hoang Le, Cameron Voloshin, and Yisong Yuc. Batch policy learning under constraints. In International Conference on Machine Learning, pp. 3703-3712. PMLR, 2019.
Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. Advances in Newral Information Processing Systems, 34:17183-17193 2021.
lan Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. In Advonces in Neural Information Processing Systems, pp. 3003 3011, 2013.
Yi Ouyang, Mukul Gagrani, Ashutosh Nayyar, and Rahul Jain. Learning unknown markov decision processes: A thompson sampling approach. Advances in neural information processing systems, 30, 2017.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley &
Sons, 2014.
Diederik M Roijers, Peter Vamplew, Shimon Whitcson, and Richard Dazeley. A survey of multi-objoctive soquential decision-making. Journal of Artificial Intelligence Research, 48:67-113, 2013.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial markov decision processes.
In International Conference on Machine Learning, pp. 5478-5486. PMLR, 2019.
Rahul Singh, Abhishek Gupla, and Ness B ShrofT. Learning in markov decision processes under constraints.
arXiv preprint 12435, 2020.
Chen Tessler, Daniel Mankowitz, and Shie Mannor. Reward constrained policy optimization. In International Conference on Learning Regresentations, 2018.
Honghao Wei, Xin Liu, and Lei Ying. Triple-q: A model-free algorithm for constrained reinforcement lcarning with sublinear regret and zero constraint violation. In International Conference on Artificial Intelligence and Slatistics, pp. 3274 3307. PMLR, 2022a.
Honghao Wei, Xin Liu, and Lei Ying. A provably-effecien model-free algorithm for infinito-horizon average- reward constrained markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022b.
Tsachy Weissman, Erik Ordentlich, Gadiel Scroussi, Sergio Verdu, and Marcelo J Weinberger. Inoqualities for the 11 deviation of the empirical distribution. Hewlett-Packard Labs, Tech. Rep, 2003.
Adam Wierman. Fairness and scheduling in single server queues. Surveys in Operations Research and Management Science, 16(1):39 48, 2011.
Tengyu Xu, Yingbin Liang, and Guanghui Lan. Crpo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pp. 11480 11491. PMLR, 2021.
Tiancheng Yu, Yi Tian, Jingzhao Zhang, and Suvrit Sra. Provably efficient algorithms for multi-objectivee competilive rl. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th Intervational Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 12167-12170 PMLR, 18 24 Jul 2021.
Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. Advances in Newral Information Processing Systems, 33:4572-455 44822 2020.
Junyu Zhang, Chengzhuo Ni, Zheng Yu, Csaba Szepesvari, and Mengdi Wang. On the convergence and sample elficiency of varience-reduced policy gradient method. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Newral Information Processing Systems, 2021. URL https: //perrevie mett/oorumidd-Be VXFOyyy
Liyuan Zheng and Lillian Railiff. Constrained upper confidence reinforcement learning. In Learning for Dynamics and Control, pp. 020-629 PMI.R, 2020.
15

---

Published in Transactions on Machine Learning Research (MM/YV (M//YYYY)
A Assumptions and their justification
We first introduce our initial assumptions on the MDP M. We assume the MDP M is ergodic. Ergodicity is a commonly used assumption in coustrained RL literature (Singh et al. 2020 Chen et al. 2022 Further, ergodicity required to obtain stationary Markovian policies which test environment. Let P denote the t-step transition probability on following policy т in MDP M starting from some state s. Also, let Ty denotes the time taken by the Markov chain induced by the policy π to hit state s' starting from state Building on these variables, P and T 8-28/ we make our first assumption as follows:
be tranlerred from training setup to
Assumption A.1. The MDP M is ergodic, or
|| - Pal S Cp'
(28)
where P7 is the long-term steady state distribution induced by policy 9, and C > and p < are problem specific constants. Also, we have
Tar == max E < <0
(29)
where TM is the finite mixing time of the MDP M.
We note that in most the problems, rewards are engineered according to the problem. However, the system dynamics are stochastic and lypically not known. Based this, we make the following assumption on rewards.
Assumption A.2. The rewards r(8, a), the costs a(s,a); i and the functions f and are known to the agent.
Our next assumption is on the functions f and g. Many practically implemented fairness objectives are concave (Kwan al., 2009), or the agent want to explore all possible state action pairs by maximizing the entropy of the long-ten term state-action distribution (Hazan et al. 2019). or the agent may want to minimize divergence with respect to a certain expert policy Ghhsseipporr et al. 2020). Formally, we have
Assumption A.3. The scalarization function f jointly concave and the constraints g are jointly convex. Hence for any arbitrary distributions D1 and D2, the following holds.
f (BEnD, [x]) 2 Ee-D, [f (x)]
(30)
9 (Ex~Dz [x]) < Ex [g (x)]; IRd
(31)
We impose an additional assumption on the functions f and g. We assume that the functions are continuous and Lipschitz continuity in particular. Lipschitz continuity is a common assumption for optimization literature
[Bubeck et al. [2015] Jin et al. 2017 Zhang al. 2020). Additionally, in practice this assumption is validated, often by adding some regularization. We have,
Assumption A.4. The function f and g are assumed to be a L- Lipschitz function,
|s (x) - (v) < L/c - yl: x, ER
(32)
(x) g (x) s L | - yll E
(33)
We consider a standard setup of concave and the Lipschitz function as considered by (Cheung 2019 Brantley et al. 2020 Yu al. 2021). Note that the analysis in this paper directly works for f R E, where the Tunction takes as input multiple average per-step rewards. We can obtain maximum entropy exploration if choose function f = E. d log(A + 7) with rk(s, a) = [s) for a particular state action pair 8k. Og and choosing K S to cover all state-action pairs and a regularizer n).
Next, we assume the following Slater's condition to hold.
Assumption A.5. There exists policy π, and one constant 8 LdST / A/T such that
g (c)( ..))),))),)))) < -8
(34)
16

---

Published in Transactions on Machine Learning Research (MM/YYY)
Further, if there is (possibly unknown) lower bound on time-horizon, Ti 2 exp (1), then we only require 8 > LdSTas v Aloo T.)/T-- This assumption is again standard assumption in the constrained RL literature EEroni ct al. 2020; Ding et al. 2021; 2020; Wei et al. 2022a). 5 is referred as Slater's constant. (Ding iet al. 2021 assumes that the Slater's 's constant ò is known. (Wei et al., 2022a) assumes that the number iterations of the algorithm is least, ((SAH//) for episode length H. On the contrary, we simply assume the existence of 5 and a lower bound on the value of which can be relaxed as the agent acquires more time
to interact with the environment.
B Efficiently solving the Conservative Optimistic Optimization problem
We now provide the details on efficiently solving the optimistic optimization problem described with constraints in Equation ( (18. Similar to the method proposed in (Rosenberg & Mansour 2019), we define a new variable p(s, a, ) which denotes the probability of being is state 8, taking action a, and then moving to state s'. Now, the transition probability to next state s' given current state and action a is given as:
p(s,a,8')
P(s'(s,a) a)
(35)
Ee,
Further, the occupancy mcasure of state-action pair 8, is given as
p(s, a) = Σ p(s,a,s)
(36)
Based on these two observations, at the beginning of epoch e, we define the optimization problem follows:
(I
(Eplesa.st) rr(s.a)
max pls.a.0))
(37)
8.0
subject to following constraints
Σ p(s,,,,')) 1,p(s,a,s') 20 5,a,8'
(38)
Σ Cpss,a,s Σ p(sss,a,h s)
(39)
s' Σ ([plssasss) ale.a))
Σ ((_ [plsaas)) cale.a)) sce c
9
(40)
P(s,a,s')
p(s,a,s')
E E 1o
5 a(s
(41)
P(s,a,5')
Σ p(s,a,s) -psss) a(s,a,8))
(42)
TVNo(s,
145 (2At)
Ea(s,a,''s
Σ Ep(),a,s)
(43)
IV Nv
for all s E S,a E A, and s' E S. Also, a(s, a,s') is auxiliary variable introduced to reduce the complexity of l norm constraints and the present the optimization problem in a disciplined convex program which can be coded easily CVXPY. The Equations probability estimates.
42 43 jointly describe the confidence interval on the
17

---

Published in Transactions on Machine Learning Research (MM/YVV (YYY)
C Proof of Lemma 5.1
Proof. Note that p denotes the stationary distribution of the optimal solution which satisfies
g Σ (s.0))(()))))
[et-s,a)caa) sc
(44)
5,8
Further, from Assumption
3.7
we have a feasible policy и for which
g Σ ((,,)))(ss,)) Is SC
(45)
We now construct a stationary distribution p obtain the corresponding mye as:
(s, = (1- Cc) ())
8 pf. (s,
& (s)
'e
(46)
m'é = p (s, a)/
En((s) s/b
(47)
For this new policy and convex constraint g, we observe that
9
Σ
Exf(s,a)cass.a)
(48)
8.0
8.0
9
Σ
(1-
Ce
Ee pr p +
(s,0)o2(8,0),.... E C((1- [
8
p
ce 1 (c)))c(aa))))
(49)
8
$ (11- (c)
8,
5,
Ee + 0
g
Σ (
(50)
Ec C+
to (C 00
$
(51)
8
= C - 8 8 --
(52)
where Equation 50
follows from the convexity of the constraints. Equation
51 follows from Equation
and Equation 45
Note that the policy Th corresponding to stationary distribution constructed in Equation ti-tight constraints. Further, we find n. the optimal solution for the e.-tight optimization problem. Hence, have
46 satisfies the
f Σ (s.0)ra)))))))
-f Σ E (s,
Σ (2, - Σ (s,0)r(3,0)
S
f
(53)
8.0
3,0
<
L
(p (s, - (s, r(s,a)
(54)
8,0
<
L Σ
(s, (1 [ p (5, - (s)(sa)) - cals.a)
6e
(55)
18

---

Published in Transactions on Machine Learning Research (MM/YYYY)
$ L
c
Σ (pf - (((s))))
(56)
< L 8
Σ p (8, a)
+ 5
(57)
Ee
S 2
(58)
where, Equation 54 follows from the Lipschitz assumption on the joint objective f. Equation 58 follows from the fact that a( I 1 for all (8,a) E S x A.
D Objective Regret Bound
In this section, we begin with breaking down the regret in multiple components and then analysis the components individually.
D.1 Regret breakdown
We first break down our regret into multiple parts which will help us bound the regret.
T (se,
R(T)= = f(2)) - f
at)
(59)
T
1=1
E
1 E
ETJ(O)) -1 - ((:
T
= -(( T
(>
Σ a()
(60)
T c=1
1=1
1
Σ To (1(2)) -
+ T Σ Ta)( -1
1
Σ
r
re(80,0))) at)
(61)
T
T
Σ Te (f(12)-((33) - --(5))
E
+ Σ
E
Tef(
-
(1(7
1
Σ
re(se, ai)
(62)
E
1
E
(
T
Σ
Te (f(X.)- - -(0 +1
Teh
-
Σ
re(s,, as)
(63)
T
T
T
1=1
1 E
E
1 T
Σ
Te ((12)-10R)) - + T
1
TeXPa
P.
Σ
(1 az)
(64)
T
T
T
1=1
E
l+t1-1
Σ
Te (f(22) - -(())) +
-P X rr(s),a))
(65)
T
Te
fet1-1
1 T
Σ
Te
- -((f)))))t) +
Σ
(>ee - xL.)
t=
E 1++1-1
(Xe - ael)
(66)
(T) + (T) Rz(T)
(67)
where Equation 62
comes from the fact that the policy ne is for the optimistic CMDP and provides a higher value of the function f. Equation 03 comes from the concavity of the function f, and Equation 04 comes from the Lipschitz continuity of the function f. The three terms in Equation 66 are now defined as:
I Σ Te R1 (T)
(68)
T
19

---

Published in Transactions on Machine Learning Research (MM/YYYY)
R1 (T) denotes the regret incurred from not playing the optimal policy n" for the true optimization problem in Equation (9) but the optimal policy Te for the e--light optimization problem in epoch e.
B
letl-1
(T) = T t=
X -2..)
(69)
R2(T) denotes the gap between expected rewards from playing the optimal policy aa for e-tight optimization problem on the optimistic MDP instead of the true MDP. For this term, we further consider another modification. We have P. being the optimistic MDP with optimistic policy Te as the solutions for the optimization equation solved at the beginning of every epoch. Now consider MDP Pe in the confidence
set, which maximizes the long term expected reward for policy Te or ARE 2 Xo for all Pe in the confidence interval at epoch e. Hence, we have
E
l441-1
R2
Pe x
(70)
T
F=1
t=
144-1
L
x
(71)
We relabel Pr as Pa in the remaining analysis to reduce notation clutter.
E let1 11
R3(T) T
(72)
RT(T) denotes the gap between obtained rewards from playing the optimal policy na for e-tight optimization problem the true MDP and the expected per-step reward of playing the optimal policy Te for ti-tight optimization problem the true MDP.
20

---

Published in Transactions on Machine Learning Research
D.2 Bounding R1(T) (T)
Bounding (T) uses Lemma 5.1
We have the following set equations:
E
1--1-
(T(T) = T
(120)-((12
(73)
em
2
(74)
2L
log
K
(75)
T6
t
2KL
T
log
(76)
T8
t
2KL
log T
(77)
2KLlog
Σ
(78)
T8
2KLlog T
(1+
(79)
T8
1=1
2KLlogT T
(2VT)
(80)
T5
where Equation
77
follows from the fact that logt S log T for t S T.
D.3 Bounding (T")
We relate the difference between long-term average rewards for running the optimistic policy me the optimistic MDP X and the long-term average rewards for running the optimistic policy we on the true MDP (XF.) with the Bellman error. Formally, we have the following lemma:
Lemma D.1. The difference of long-term average rewords for running the optimástic policy te on the optimistic MDP, Xee, and the average long-term average rewards for raraing the optimistic policy te on the true MDP, XP is the long-ten term average Bellman error as
X ne
Σ P BT..P 3,4
(81)
Re
Proof. Note that for all s S, we have:
Pe (s)
Eawn,
Pe
(82)
Eara,
+ P(
(83)
s'ES
where Equation 83 follows from the definition of the Bellman error for state action pair a).
21

---

Published in Transactions on Machine Learning Research (MM/YYYY
Similarly, for the true MDP, have,
V P (8) Eewx [0,
(84)
Bowse r(s,a) a) +
Σ
P(s'|s, (V)
(85)
e'ES
Subtracting Equation 85 from Equalion 83
we gel:
Pe Pe (s) V. (s) = Ea
BT (s, +y Σ P(s'|s,a) (i - ViciPe) (5')
(86)
s'ES
Bante
B (s,
+7 Σ Pr. (VRePe= Vil.fe) (8')
(87)
s'ES
Using the vector format for the value functions, we have,
no V.a.Pr Voai (1 - 7 Px B
T
(88)
Now, converting the value function to average per-step reward we have,
X AP:1s
A 1s = lim 7) (VrcrPe V.
(89)
Te
7-1
lim 7) (1 -pPa)) -1 Bo.
(90)
7-1
Σ
Pr. Ba (s. 1s
(91)
where the last equation follows from the definition of occupancy measures by Puterman 2014
Remark D.2. Note that the Bollman error not be confusod by Advantage function and policy improvement lemma (Langford & Kakade 2002). The policy improvement lemuna relates the performance of two policies on same MDP whereas we bounded the performance of one policy on two different MDPs in Lemma D.1
We now want bound the Bellman errors to bound the gap between the average per-step reward X and XP From the definition of Bellman error and the confidence intervals on the estimated transition probabilitics, we obtain the following lemma:
Lemma D.3. With probability at least 1 - 1/t6, the Bellman error Be (s, a) for state-action pair in epoch e is upper bounded as
14S log(AAT)
Po < min 2,
[l0(-)llo
(92)
1 (s.
22

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Proof. Starting with the definition of Bellman error in Equation 20
we get
((5lls,a)izeel) ))
(st.f((ssa)) lim 7-1
( (1(s.0)+ + Σ
(93)
S'ES
(((s,))+ + Σ
Pa(5'1s, (((6))s.))/1
lim 7-1
s'ES
r(s,a) +7
P(s'ls, P(s'|s,a)V, (((1)110)773(((11)
(94)
d'ES
lim
(Pe(5)(s,a) ( ( (5))
(95)
7+1
S'ES
lim
Σ (Pa(5l(s,a) - P()l(s,a)
(o (( + (i - Ps)
(96)
7-1
#EES
lim
Σ
(Pa(8'(s,a) - P()lls,a)) P (o
7-1
#'ES
Σ
av)
a)
Σ P(s (8)
(97)
s'ES
s'ES
lim ?
Σ (((ssss)) (V V
(98)
7-1
3EES
Σ
(Pc('ls,a) - a(s))s,a) lim y (v)) - Pa
(99)
Σ (Pa(s'ls,a) P(s'la ((')ls,a)) h(d') WES
(100)
(Po(-1s,a) P(+ls, a)) 1, |m())lo
(101)
14S log(2Al)
V Ne(s.a) [l
(102)
14S (2g()AT)
[0))m
(103)
V (s)
where Equation 95 comes from the assumption that the rewards are known to the agent. Equation
99
follows from the fact that the difference between value function two states is bounded. Equation [100]
comes from the definition of bias term (Puterman 2014). Equation (101) follows from Hölder's ' inequality. In
Equation 102 [[ is the bias span of the MDP with transition probabilities P. for policy Te. Also, the
L1 norm of probability vector is bounded using Lemma F.I for start time te of epoch e.
Additionally, note that the & norm in Equation 101 is bounded by 2. Thus the Bellman crror is loose upper bounded by 2l for all state-action pairs.
Note that we have converted the difference of average rewards into the average Bellman error. Also, we have bounded the Bellman error of a state-action pair. We now want to bound the average Bellman error of an epoch using the realizations of Bellman error at state-action pairs visited in an epoch. For this, we present the following lemma.
23

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Lemma D.4.
With probability at least 1 1/T0, the cumulative expected Bellman ervor is bounded
le+1-1
Σ (te+1 te Bs.P ( (s. $ Σ Σ
B ae) + 47ys WDls/7I' (T
(104)
tl
St, at) be the filtration generated by the rumning the algorithm for t time-steps. Note that conditioned on filtration Ft.-1 the two expectations E=,a==..P(! and P(-IF_..P are not equal as the former is the expected value of the long-term state distribution and the latter the long-tern term state distribution condition on initial state -t, We now Assumption 3.1 to obtain the following set of inequalities.
Proof. Let F, {11, d., ,
E (x.a)==T, p eB (s, a)] ((,,a)= P (s) + E Bsseadee p B (st, (e)
(105)
- B (8), F.-1l
(Eisa))me..P B Po (8, (8,a8) a))
B Beec.Pe (s:: uz) (e)
(106)
S B BTT. Po (8t, 010 Fro-1]
221h(-))l Σ (o(als)dx Te (clss))
(107)
8.0
$ Pl (S) Ft)
+ 21[x())]l
J.d Σ (aass) d=. (s)
pt-
(108)
8,a
(Br (.)
Berr
+ 21l Σ T(a|s)]ld+.
pt-tetlllmy lrl
(109)
Pl Be (8t
+ +2ll(())l Σ
T(aas)Cpp'
(110)
B(s. P( (st, 0: Ft. 2c
(111)
where Equation 107 comes from Assumption 3.1 for running policy me starting from state st,-1 for t + 111 follows from bounding the total-variation distance for all states
steps and from Lemma 5.3 Equation
and from the fact that Σn N [a(s))=1
Using this, and the fact that Ex,.P P [B (s) Fr.1 BF..Po az) forms a Martingale difference (r (x1, Fr)1 B (s,, at)l S 41]b(-))loo, we
sequence conditioned on filtration F.-1 with [Bmg,P can use Azuma-Hoeffding incquality to bound the summation
(te11 L (s,))
b---11
Σ
(te+1 - Ex,,P Br at) at)
Σ
2CS|
(112)
24

---

Published in Transactions on Machine Learning Research (MM/YYY)
E
hc))l
BreiP (s,,
(113)
1-p
f+-1-1
2C (())((())))) h 10c
BreiPe + 4l10(())looo)) 7T' log 2T
(114)
p
where Eq. 114 comes from the Azuma- Hoefddinss inequality with probability at least T
D.4 Bounding the term |
Note that we have Xe= X for all P in the confidence set. Ne
Lemma D.5. For a MDP with rewards r(s, a) and transition probabilities Pe. using policy Tey the difference of bias of any two states 8, and of is bounded as h(s) h(s') S TM V 8, 8 E.S.
Proof. Note that Xh: 2 Xxx for p' in the confidence set. Now, consider the following Bellman equation
h(s) = (s, - 2h + (Prn.c = =h(ss)
where Tro (8) E. Te (e(a)s)r(s,a) and (5. En =(als) P. Pc('lss,)
Consider two states s E S. Also, let T min{! 2 1: = 8', = of be a random variable. With Pa (-1s) = -E Te ((((as))P a), we also define another operator,
Th(s) = (min r(s, P + (Pax.(1ss)) # + h(s')1(s=s'),
Note that Th(s) < Th(s) = h(ss) for all since Pa maximizes the reward over all the transition probabilities in the confidence set of Eq. (21) including the true transition probability P. Further, for any two vectors u, v E RS with u(s) 2 vss)vs, we have Tu 2 Tv. Hence, we have (<)(()) S h(s)) for all s. Hence, we have
h(s) > (5) = E[ (1
-mnn minn((,,a)) h(snar)]
8,0
Taking limit as n + xc, we have h(s)) 2 h((²) Tar, thus completing the proof.
We ready to bound (T) using Lemma D.1
Lemma D.3 and Lemma D.4 We have the following
set of equations:
R2(T) =
L
E
let1-1
Pe Te
- xe.)
(115)
T
==1
t=t.
L
E
fet1-1
TT. (o,))(
(116)
T
9.6
L
E
1+41-1
2CTMSE
<
7
Σ
Σ
BToiPe 0r) + 4T Www.TTTTTlo (Tlog((
1 1-p
(117)
25

---

Published in Transactions on Machine Learning Research (MM/YYN)
F. Pe41-
log(7
+ 47 7T (2g + 2CT
TM
(118)
1V (x
-
6=1
t=
14S (2g))
2CTMSE
$
Σ
Σ
Ve (s, a)Tr
+ 47 M 7T log() 1 1-p
(119)
(v
E
ve(s,a)
2CTM
Σ
TM / 14SA
+ 4T 77
(120)
T
1 1-p P
6,0
2CTMSE
Σ
TM (22 14 (3)
47 7I 7o (2g
+
(121)
1 1-p
8,0
$ T
Tus(v2 + 1)/1))///////// (4SAllg(2AT))
Σ
a)
8,0
3,0
2CTMSE
+ 4I'M 7T 7T (2T)
(122)
1 1-p
2C
M Tus(V2 1444Alog(AA))) SAT SAT + 4TM (og(T) + 1 - p
(123)
where Equation
116 follows from Lemma D.1 Equation 117 follows from Lemma D.4 and Equation 118
follows from Lemma D.4 Equation
121 follows from (Jaksch et al. 2010) and Equation 122 follows from
Cauchy-Schwarz inequality.
D.5 Bounding RT(T)
Bounding RT(T) follows mostly similar to Lemma D.4 At each epoch, the agent visits states according to the occupancy measure ph. and obtains the rewards. We bound the deviation of the observed visitations to the expected visitations to each state action pair in each epoch.
Lemma D.6. With probability at least 1 - 1/76, the difference between the observed rewards and the expected rewards is bounded as:
E 1-41-1
Σ t=
E., (r(s,a))
Σ
Σ t=
r(st, an) s 22V7T
(124)
Proof. We note that E,,,,P (r(s, F)-F r(st, ae) is Martingale difference sequence bounded by because the rewards are bounded by 1. Hence, following the proof of Lemma D.4 we get the required result. ]
D.6 Bounding the number of episodes E
The number of episodes E of the UC-CURL algorithm are bounded by 1 2SA + SAlog(T/SA) from
We now bound the number of episodes for the modification of the algorithm as described in Section 5.2 We considered to trigger a new episode whenever ue (e(s, a) becomes max (1, (e-1(s,a) a) + 1} where V--1 is the number of visitations to 8, a which triggered a new epoch. In the following lemma, we show that the number of episodes are bounded by 22SAT) with this epoch trigger schedule.
Proposition 18 of (Jaksch et al.) 2010
Lemma D.7. If the UC-CURL algorithm triggers a new epoch whenever ve(8, a) 2 max(1, (8, + +1} for any state-action pair s, s,a, the total number of epochs are bounded by O(1 + /2SAT), where D. (s, vels, (ua(s,)) = Ve-1(8, (s,a) + 1} + all 8,a.
a) (ve a) & Vo_1(8,)) and vn = (r(8,a) = for
26

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Proof. Let ((s be the number visitations to state-action pair and (s, be the total number of epochs triggered when the trigger condition met for state action pair 8, a. Hence, we have
E
N(s,o) = Σ ve(s,a)
(125)
E
va(s,a)
(126)
((s,a) +1) (²(s,a)
(127)
where considcring only epoch triggers for 8, gives Equation 126 that (e(8,a) a) (s a) = (s-1(s, which gives Ne+1 e(e + 1)/2.
Equation
127
obtained from the fact
(s a) +
Now, we have the following,
== Σ a(s,a)
(128)
8,0
k²
(129)
SA
(s,
(130)
2SA
6,0
2
2
SA
1
Σ K(s,a)
(131)
SA
where Equation 131 is obtained from the convexity of x². Hence, we have,
2T
Σ K(s,a) S SA
2SST
(132)
SA
Further, the first epoch is triggered when the algorithm starts. Hence we have = 1 Σ,, K(s,a) = 1 V2SAT.
E
Bounding Constraint Violations
bound the constraint violations C(T), we break into multiple components. We can then bound these components individually.
27

---

Published in Transactions on Machine Learning Research
E.1
Constraint breakdown
We first break down our constraint violations into multiple parts which will help us bound the constraint violations.
T
T
C(T)
9
T
(1,)
..
T
Σ
aaloraa))
(133)
9
T
C1 (st, at),
T
1
ar)
+ T
Σ
Tog ( (1), (d)
1
Σ
Teg
Po (1), .... <d)(d))
(134)
T
t=1
E Σ
9
T
Σ
ci (81, at), ".
T
1
Σ calse:
T
Teg
( (1),
T
1
Σ
Tele
c=1
+
(135)
Σ
T
(st, az), ...
1
Σ
T
ca(se, oi)) -9
E
T
Pe
(1),
1
Σ
To
Tos
(d)
E
Tole
T
T
T
STT
-T
T
1=1
1=1
e=1
c=1
(136)
d
E 1++1-1
E
((88) - (l)(1)) - T Σ
Tele
(137)
6=1
8 f-11-1
E
(1()))))) - -F. + c (1) - C2 (i) || - Σ Toee
(138)
T
c=1
+
ト
Σ
E
Σ
(c(()) - -
Σ
E
f-11-1
Σ
(c. (i)
1
E
Tree
1=
t=
+
(139)
< (C,(T) - -2(7) (TT))
(140)
where Equation 185 comes from the fact the policy ne is solution of conservative optimization equation. Equation (186) comes from the convexity of the constraint 9(-). Equation (187) follows from the Lipschitz assumption. The three terms in Equation 667 are now defined as:
E Tase
1
CiT)
(141)
T
(T) denotes the gap left by playing the policy for ce-tight optimization problem on the optimistic MDP.
d
F le41 -1
C2(T)
-f
(142)
T
e=l
[=f,
CT) denotes the difference between long-term average costs incurred by playing the policy on the true MDP with transitions and the optimistic MDP with transitions P. This term bounded similar to the bound of (T)
28

---

Published in Transactions on Machine Learning Research (MM/YYY)
fe-1-1
L Ca(T) = T :=1
-
(143)
CT) denotes the difference between long-term average costs incurred by playing the policy Re on the truc MDP with transitions P and the realized costs. This term is bounded similar the bound of RT(
E.2
Bounding Ci(T)
Note that Ci (T) allows us to violate constraints by not having the knowledge of the true MDP and allowing deviations incurred costs from the expected costs. We now want to lower bound C1 to allow us sufficient. slackness. With this idea, we have the following set of equations.
E
1e41-1
1
(IT)
Ce
(144)
T
1
log le
K
(145)
T
te
1=te
1=+1-1
(og(T/4)
K
(146)
T
e=
t=ta
E
641-1
log(TT4)
K
Σ
Σ
(147)
T
T
6=
t=t.
(og(T/4)
K _
(T - t
(148)
T
T
K 1
(og(T/4)
2/
T
(149)
1
/logT
K
(150)
4
T
where E' some epoch for which T/4 < ty' T/2.
E.3
Bounding CT))), and C3(T)
We note that costs incurred in C2(T), and Cs(T) follows the same bound as R2(T) and Rs(T) respectively. Thus, replacing r with c, we obtain constraint violations because of imperfect system knowledge and systom stochastics (SLdTMSAA/S
Summing the three terms gives the required bound and choosing K = ((LdTMSSA) gives the required bound constraint violations.
F Concentration bound results
We want to bound the deviation of the estimates of the estimated transition probabilities of the Markov Decision Processes M. For that we use & deviation bounds from /Weissman et al. 2003 Consider, the following event,
14S log P(1s,
V(s,a) E ESXA] (ax((,nn(s,))
E,
(151)
29

---

Published in Transactions on Machine Learning Research (MM/YYY)
where Ei= 1 (sg ms) Then, we have the following result: Lemma F.1. The probability that the event & fails to occur upper bounded by 2015
Proof. From the result of (Weissman et al. 2003 the & distance of a probability distribution over S events with n samples is bounded as:
nc²
(- nc²
P (IIP(1)s,a) P(1s, 20) s exp
$ 222)cxp)
exp
(152)
2
2
This, for V n(s.a]
log (28205AAA)))
14S mls,a]
log(2AI)
log(2AT) gives,
V
V n(e.0)
P [P((l,,)) P(-1,,))111
14S
log(2Al)
S (2 exp
(- n(s,a) a)
2 log(2 (00
(153)
n(s,a)
2 n(s,a)
2
(154)
2520S
1
(155)
20ASt?
We sum over the all the possible values of n(s,a) till time-step to bound the probability that the event E, does not occur as:
1
S
(156)
20S
205.At6
m(s.n)
Finally, summing over all the s, a, we get,
P (IP((15,0) a(11),))l1 2
14S n(s, a)
log(2At) Vs,a
(157)
V
2016
The second lemma is the Azuma-HHofflding inequality, which we use to bound Martingale difference sequences. Lemma F.2 Aizma-HHeffdingg Inequality). Let X1, Xn be Martingale difference sequence such that XxJ S e for all E (1,2,... ,n), then,
n
2
P
X.| 2,
$ 2exp
(158)
2nc
G Posterior Sampling Algorithm
Note that in the UC-CURL algorithm, the agent solves for an optimistic policy. This convex optimization problem may be computationally intensive with O(S² A) additional variables and O(SA) additional constraints. We now present the posterior sampling version of the UC-CURL algorithm which reduces this computational complexity by sampling the transition probabilities from the updated posterior. The posterior sampling algorithm based on Lemin of (Osband et al. 2013), which we state formally here.
Lemma G.I. [Posterior Sampling] IJ h is the distribution of M then, for any of (Fr.) meeusurble function g,
E B[g(M) =
(159)
where Me is the MDP sampled at the beginning of the epoch at time-step le-
30

---

Published in Transactions on Machine Learning Research (MM/YYN)
Algorithm PS-CURL
Parameters: K
Input: 5, A, r, d, ai [d]
1: Let t= 1, e= - K Int
2: Ve(s,a) = 0, N, = 0 s.
Solve for policy We using Eq. 164
for E (1, do Obscrve St, and play at (-(s))
Observe st+1, r(s; 01) and c(t ar) Vi [d]
7: Ve(st, 01) = (st az) +1
8:
if (e(8,a) max Ne(s,a)) for any 8, then
9:
for (s,a) E A do
10:
(8,1 a) (2, v (8)
11:
e e 1, a) =0
12:
end for
13:
E. K
Int t
14: P ~ h(117)))
15: Solve for policy ne using Eq. 164
16: end if
17:
end for
We now present our posterior sampling based PS-CURL algorithm described in Algorithm Similar to the UC-CURL algorithm, the PS-CURL algorithm proceeds in epochs. At each epoch e, the agent samples Pe ~ F(,), it can solve the following optimization problem for the optimal feasible policy.
max S( (E r(8,a))e(ss.))
(160)
p(x.a)
with the following set of constraints,
Eo,po(s,0)= 1, po(s,a)20 20
(161)
Enca Pol' E sia Pc(s()s,a)po(ss.)
(162)
a( ( ((ss,a)p(ss.))... E.s (c.s.a)).(s.a)) s -c
(163)
for all 8' S, V and A. Using the solution for Pa for tight optimization equation for the optimistic MDP, we obtain the optimal conservative policy for epoch
pe(s. Ao
(a(ss)
V s.a
(164)
For the UC-CURL algorithm, the true MDP lies in the confidence interval with high probability, and hence the solution of the optimization problem was guaranteed. However, the same is not true for the MDP with sampled transition probabilities. We want the existence of policy such that Equation (163) holds. We obtain the condition for existence of such a policy in the following lemma. To obtain the lemma, we first. state tighter Slater assumption as:
LdST (AlogT)/1 (CSA log (T( - p)) and I > Ld (2STTr /OSl///4AA loA AT/T1/3 + CSTMM((1 CSTM/(A-p)rv3)) such that
Assumption
G.2. There exists policy n, and constants delta
g (cP.
....,.PP.K P.K2) 5-5-1
(165)
31

---

Published in Transactions on Machine Learning Research (MM/YYY)
Lemma G.3. If there erists policy n, such that
(d)) -
(166)
and there cvists episodes and + with start timesteps te and bet1 respectively satisfying let1 te 2 71/3,
then for (P)o..)) P(-ls, S s/
148 148 lng(2At) the policy satisfies,
Ncls.a)
g ( (1), (d)) (()) -8.
(167)
Proof. We start with the Lipschitz assumption (Assumption 3.4 to obtain,
1 f (1), (1).... -fa (d) 99 (5 (4))))))))))))) S Ldmax (sf= (1)
(168)
9 & (1). c
, (d)) < Ld max (C)(()) - _ (1)
(169)
where Equation 169 is obtained by choosing the sign of modulo in the previous equation. We now bound the term <p== [ using Bellman error. We have,
+ (
Σ P (s) = E (s,aa
(170)
where BTT.PPoss.. inequality as follows:
(s. a) is the Bellman error for cost. We bound the expectation using Aeuma-Hoffdlin's
E B (s, = E (st. Ft) + Cp
(171)
1-11-1
E (s) + Cph
(172)
60+1 Lo le
le41-1
< 1
Σ
(E Br
(s,, a))FF (1- (1-o)
(173)
l0+1
te
1
log 148 log AT) Σ (s)
|10ll0 I4S
VN +4(h(-)1lo 7(te41 te log(te++ te)
te+1 - te
CS([
(174)
(1 (ttttt+1 - te)
|1/llooo I4S log AT Σ (v(ss)))+4[[())))) 4l log(te11 - te)
10+1 La
CSI)i(())oo
(175)
(1 (t(et)tteetet1 -t)
< 1
[1ollooss 14A log AT
Σ
(e + +111(())loo / T(tet1 - to) loggoog - te)
10+1 - la
8.a
(176)
(1
(tet1 - te)
32

---

Published in Transactions on Machine Learning Research (MM/YYYY)
1
e+l le / 14g AT (te+11 - te) T(t41 to) log(te-1 - te)
CS)1i(-)llo
(177)
(1-p)(te+1 - te)
| (te+1 -te) te) + (.) () o
14Alog AT
7 7log(lo41 (0)
CS
+ p)(te+1 - tc)
(178)
(fe+1 - tc)
where Equation 172 is obtained by sumiinng both sides from = le to L = le+1- Equation 173 is obtained by summing over the geometric series with ratio p. Equation (74) comes from Lemma D.4 Equation 175
comes from the fact that Ne(s, a) 2 Ve(s, a) for all a, and then replacing the lower bound of (s, Equation 176) follows from the Cauchy Schwarz inequality. Equation (177) follows from the fact that the epoch length le+1 - Le is same as the number of visitations to all state action pairs in an epoch.
Combining Equation 178 with Equation 169 and bounding the [lx(-)l term with TMr we obtain the required result as follows:
9 (c, (d) Ld max (2) -1)- + (G)) (f
(179)
Ld
SM
14Alog AT
+ M
7log(tet1 - te)
(te+1 -te)
(tet1 - -te)
CTMS
(1 1-P)(le+1 ()(ee11-1o) 1e)
+ (1), , (2(d))
(180)
La(
T 14A AT
7log(tet1 - te) (te+1 - -e)
+ +ATMM
(te+1 -te)
CTMS -1-
(181)
(1 [1-))(ee+1 - 10)
8,
(182)
where Equation
182 is follows from the definition of I' in Assumption G.2 and tet1 - te 2 71/3.
observe that for tighter Slater condition the true MDP, can only guarantee weaker Slater guarantee. However, we make that assumption to obtain the feasibility of the optimization problem Equation (160).
From Lemma G.3
The Bayesian regret of the PS-CURL algorithm is defined as follows:
B(R(T)) = (2 - (Ein, r(s,, an)
(()))a))))))))))
Similarly, we define Bayesian constraint violations, C(T)), as the expected gap between the constraint function and incurred and constraint. bounds,
T - at)T, ..., Σn ci (((n))))))) ]
T
E(C(T)) = EE
+
where (x)+ = max(0, x).
Now, we can use Lemma G.1 to obtain E[(({)))F=. = B(((E)) and [[(((E))(())..)) = (C EL((CE) (o) i, and follow the analysis similar to the analysis of Theorem 5.6 to obtain the required regret bounds.
33

---

Published in Transactions on Machine Learning Research (MM/YYY)
G.1 Bound on constraints
We now bound the constraint violations and prove that using conservative policy. We can reduce the constraint violations to O. We have:
ca(ss, (z) ))
C(T)
g
(86, 0e);
T
Σ
(183)
t=1
+
T
T
T
C1 (1 (t))),)
Σ
calss, at)
T c=1
1
Teg
Ste
PPell
; :i
Pe.K2)
Tel
P..1 ....
Po.K2
(184)
T
+
T
T
E
c1(5,, oz),
Σ
calsi, az)
1
Teg
Pull Sile
Khe +C1
(185)
T
T
t=1
e=1
T
T
E
9
T
(1 01),
T
Σ
ca( at)
-
TaCse
Pesl
Σ
Tolke
+ C1
(186)
fet1-
L
Σ
(st, - -Pack)) |
+
(187)
f-1-1 Σ
(() CPN + p.P
Prink) +
(188)
E 44111
K2
E
1-41-1
ΣΣΣ
(c1. (...)
+
Σ
+ Ci
(189)
t=ke
< +2(1))
(190)
where Equation
186 follows from the convexity of the function g, and Equation 187 follows from the Lipschtiz continuity.
We bound C2( +(T)+C((l CT) similar to the analysis of R(T) by
ò (
A 1 STMS2A S
(191)
T (1-p)T
We focus our attention on bounding (T). For this, note that in Assumption 3.4 we assumed that the cost function y is Lipschitz continuous and the gradients are bounded at all points. This implies for a bounded input domain the cost. function is bounded. We assume that the upper bound of the cost is goc- We now
34

---

Published in Transactions on Machine Learning Research (MM/YYY)
obtain the bound on (T) as:
(
1
Σ
Te
9
STe 11 Stc staaka))
(192)
T e=1
1
Σ
Te 9 (ffeill.... , (h..kk) 1 1(Te 2 11/3}
T
E
(1 Te (g
STe y (o..,,,t..k))) liTe < <T1/3]
(193)
T c=1
E
1
To [g]
(
Pe.l
:- (to.ki) 1{To 2 T2/33 +
1
T2/$
9:0
(194)
T
T
6=
1
[Te 2 2T//3 1 g30
(195)
T
T
Tele (1-1(T<<T/3))
< <1133) + 1/ go0
(196)
E
E 7L
Σ Take + T
Teral (Te < <T</3> + T FTT/3/ g00
(197)
T
e=1
K
E
Tlog T
+
T2/3 R + T
ET2/3 go0
(198)
T
4
T
K
(TTlog T + +
1
1
ETT/3 yo0
(199)
47
T
where Equation 194 follows from the bound on g(x) S 9oo. Equation 195
follows from following the
conservative policy.
Thus, choosing appropriate K, can bound constraint violations by 0.
H Further Discussions
H.1 Regarding Ergodicity in Assumption 3.1
Regarding the assumption on ergodicity in Assumption 3.1 we make two observations:
For MDPs with constraints, we note that for optimal policy to be stationary, the MDP has to be ergodic. For finite diameter MDPs, the optimal policy can be non-stationary. Consider an MDP with three states, left, middle, right, and two actions left, right. The left action keeps the state unchanged from left, or takes the agent left from middle and to middle from right. Similarly, the right action takes the agent to middle from left and to right from middle, or keep the agent to right. Since there exists different recurrent classes for different policies (For a policy which takes only left action, the recurrent class contains only left state. For policy which takes only right action, the recurrent class contains only right state), the MDP is non-ergodic. Further, the agent obtains reward of +1 and cost of 0 taking left action in left state and reward of 0 and cost of +1 on taking right action in the right state. A stationary policy provides an average reward of (1/6, 1/6) as the agent stays in all three states with equal probability and takes either actions with equal probability in each state. Whereas, if the agent follows a non-stationary optimal policy, the agent optimizes both rewards and cost with average reward of 11/2,1/2). Hence, the agent must stay in state left as much as the state right by only making minimal transitions via the middle state. Thus, the optimal policy is non-stationary for non-ergodic MDPs. This example is provided in detail by Cheung 2019)).
The second observation is for finite diameter MDPs, where Chen et al. 2022) provided an algorithm which requires the knowledge of the time horizon T and the span of the costs sp.. We note that the two variables might not be known to the agent in advance. Further, the knowledge of the time horizon required to divide
35

---

Published in Transactions on Machine Learning Research (MM/YYYY)
the time horizons to epochs of duration 0(T1/3) to obtain regret bound of O(T This particular epoch length is required to bound the bias-span of the MDP considered in the epoch. Finally, we note that the finite mixing time is also assumed in other works in constrained TH MDP (Singh et al., 2020
We note that even if we use other exploration strategies, will require the Bellman error analysis to analyze the stochastic policics. In this work, we perform an exploration and exploitation strategy by dividing the time horizon into epochs and then updating the policy in each epoch using the MDP model built using exploration done in previous epochs. The analysis of the regret will still need the impact of stochastic policies and thus the analysis approaching the paper will still be needed for any exploration strategy.
We also note that since the MDP is ergodic, exploration can be done with any policy and the agent does not need an optimistic MDP lo explore. However, the agent wants to minimize the regret for the online algorithm, and hence it plays the optimal policy based on the MDP crrimated/learneen till time t. To do so the agent finds the optimistic policy or the policy which provides the highest possible reward in the confidence interval. Note that if agent agent could have played any policy and obtained same regret bound, policy worse than the true MDP can also cxist in the confidence interval and that would not give the same performance. In the following, we provide simplified problem setup and algorithm to demonstrate that some policy may achieve large regret bound even with ergodic assumption.
Consider a simplified problem setup where f(x_) = X with no constraints. Note that this is the classical RL setup. Also consider an algorithm where the agent uses the estimated MDP without considering the confidence intervals. After every epoch, the agent solves for the optimal policy using the following optimization equation.
max Σ p(s,a)
s.a r(8,a))(8,a)
(200)
with the following set of constraints,
((),))))= =1, p(s,a)20 20
(201)
P(eap(s,a)= = E, 8,a P
(202)
where Po(-Is, a) is the estimate for transition probability to next state given state action pair (s,a) after epoch e. Let Te be the solution for optimization problem in Equation 200 202 for epoch e.
Now the regret R(T), till time horizon T, defined as
T r(si,
R(T) TX n.
Σ
as)
(203)
1=1
1441-1 -
4++1-1
Σ
r(s az)
(204)
1=
1=t
441-1
l++1-1
let1-1
Σ
Σ
P
P
Σ
Σ
r(s,, az)
(205)
6
1=
t=
41-11
4+1-1
le+1
4-111
ΣΣ
L
ΣΣ
Σ
X
+
Σ
X
Σ
Σ
r(s):
(206)
Fc
me
tst.
(T) + (T)
(207)
36

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Ry(T) is analysed in similarly to the regret analysis of the proposed UC-CURL algorithm. For R2(T), we oblain the following analysis:
4--1-1
(T( =
(X - -1)
(208)
1=
Be+1-1
- + (2 - -2a))
(209)
1=
Now, the second term, xe: - X.. in Equation (209) can be again analyzed using the Bellman error based analysis. We primarily interested in the first term. Now, nole that since the agent does not play the optimistic policy, Rí (T) cannot be upper bounded by the optimal policy of the optimistic MDP in the coufidence interval. For this, the average reward X satisfies X 2 Xp. For a posterior sampling algorithm,
][ This two properties for the optimistic or posterior sampling algorithm contributes to the key parts in the analysis and design of the RL algorithms.
the optimal policy for the sampled MDP satisfies ][
However, no such relationship can be established for Xe., and - and hence the first term of Equation (209 is not trivially upper bounded by 0. Further, for the optimal policy Te for the estimated MDP P. can return reward lower than the optimal policy x² the true MDP P or X < Ng- resulting in trivial O(T) regret. bound.
H.2 Regarding Optimality
We note the work of (Singh et al. 2020) provided lower bound of ADAT, where D is the diameter of the MDP; A, S are the number of actions and states respectively and T is the time horizon for which the algorithm runs. Based on the lower bound, the regret results presented this work are optimal in A and T. However, to obtain tighter dependence remain an open problem. Further, note that reducing the dependence of Tar to the diameter D while also keeping the regret order in as Ö(VT) is an open problem.
S using tighter concentration inequalities for stochastic policies
Experiments with Fairness Utility and Constraints
We also evaluate the proposed algorithm on non-linear setup. We consider scheduler allocating resources to two clients, client1, clientz. At each time step, the scheduler allocates resource to either of the clients. Hence, {client1, clientz) } are 2 actions available to the scheduler. The client, on resource allocation, consumes the resouree and obtains reward. The reward depends on the state of the client. Each client can be in 4 possible states. Hence, there are 16 total possible system states. At every step client stays in the same state with probability 0.625 and transitions to a different state with probability 0.125 of landing in any of the remaining states.
The agent aims to maximize the proportional fairness among the two clients (Lan et al. 2010 The proportional fairness is used to quantitatively evaluate fairness in various networks scheduling systems such as wireless scheduling (Cui al. 2019) and queuing (Wierman, 2011). We calculate proportional fairness as:
Σ log El(s.)))(s.a)) i (1.2)
(210)
s,a
where denotes the client index, ry(s, a) the reward received by the client when the system is in state s and takes action a, and p(s,a) is the steady-state state-action distribution. The rewards are r3 with respect to client state is presented in Table B
Further, the first client is high priority client and requires a minimum service level agreement (SLA) guarantee. Every time client, denied the resource, the scheduler incurs a penalty of -1. Let C denote the
37

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Table 3: Transition probability of the queue system
Client
Client State
Client State
Client State 3
Client State 4
client1 0.75
0.375
0.5
0.375
clientz 0.25
0.5
0.75
1.0
SLA guarantee for client1. Then the cost constrraint can be written as:
Σ ((=deet C
(211)
where C' is set to 0.3.
We evaluate the PS-CURL and UC-CURL algorithms on the scheduling system with = 1. We evaluate both PS-CURL and UC-CURL algorithms for linear epochs and doubling epochs. We run 10 independent iterations of the algorithm for T = 500000 time steps. The mean values of the simulation results for the constrained setup are presented in Figure 2 The scheduler take about 100, 000 steps to converge at the optimal fairness value (Figure 2a) for PS-CURL algorithm where the optimistic setup does not converges till 500, 000 steps. This is inline with the results of Section G
where the posterior sampling algorithm converges the fastest. Further, note that optimistic algorithm is vonsevvative with respect to constraints but it does not. optimises for the fairness satisfy the constraints.
We also present the system behavior in absence of constraints in Figure Figure 2d For the unconstrained setup, we only evaluate the lincar epoch sctup of the PS-CURL algorithm which converges to the optimal fairness value at around t = 50, 000 which is faster than the constrained sctup. We also observe that the optimal fairness among the clients is higher when the scheduler is not required to guarantee any service level agreements.
Again, from the experimental evaluations, observe that the proposed PS-CURL and UC-CURI algorithms can be used for systems with non-linear utilities and/or /or non-linear constraints.
38

---

Published in Transactions on Machine Learning Research (MM/YYY)
-1000
-02
1100
-1.10
Domstrant
-14
-1.20
-05-
UC-CURL finear spocts
-1.25
CURL Inner epocts
UC CURL,
doubling epocts
UC-C doubling epochs
PS PS-CURL. lnner epoens
PS-CLRC lneet spochs
PS-CURI, doubling spochs:
-0.7
Constraint
100000
200000
300000
400000
500000
100000
200000
300000
400000
500000
lime-kwc
timi-slap
(a) System fairness w.r.l. time
(b) SLA penalty w.r.l. time
-0.30
00.40
-0950
-0.45
-0.55
-0.600
PS CURL, Inear spechs
PS CURLL Inear
Comstrint Value
100000
200000
400000 time steat
300000
500000
0
100000
200000
300000
400000
500000
time stop
(c) System fairness w.r.f. time for unconstrained setup
(d) SLA penalty time for unconstrained setup
Figure 2: Performance of the proposed UC-CURL and PS-CURL algorithms the scheduling example
39


Reviews:
[{"review_id": "kfzKg7dw6p", "reviewer": "Reviewer_7s2j", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: the paper's technique is solid, and the setting is general.\n\nWeakness: some of the assumptions might require further discussion; the writing needs to be improved; the algorithms and analyses seem standard, and their novelty might need to be discussed more.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies tabular infinite horizon concave utility RL with concave with convex constraints. A model-based RL approach was proposed, with zero constraint violation guarantees. Regret analyses have been developed for both optimistic methods and Thompson sampling methods.\n\n1. How strong and necessary the assumptions of knowing the reward and cost functions (Assumption 3.2) are? This seems to be not exactly the RL setting.\n\n2. Why Assumption 3.1 is necessary? Is it assumed to hold for ANY pi (and with finite mixing time)? If so, why we even need to explore, using optimistic methods, to get a good regret analysis? I might be a bit confused about this assumption, compared to the literature on average-reward MDP.\n\n3. Can we elaborate more about Assumption 3.7? what is C, and what is the intuition of  being larger than the constants?\n\n4. Does Eq (14) have a typo?\n\n5. Can the authors give more examples about the usefulness and expressiveness of the mode of general utility with general constraints? It seems that even in the simulations, the comparison was with the recent average-reward MDP setting (not the general utility one). It would be better to make use of the developed methods in other general examples.\n\n6. How optimal is the upper bound? There is an S dependence (instead of sqrt S), is this optimal? Since this is a new and more general setting, it would be better to elaborate more about this point, or ideally give some lower bound.\n\n7. The writing of the paper needs a bit more work. Typos: 1). Second paragraph on page 2, in the beginning \"in past...\" does not read well. 2). First line on page 2, \"bound\" -> \"bounds\". 3). When referring to references, sometimes the present, but sometimes the past tenses are used. it's better to make it consistent. 4). Some equations are not ended with period, or sometime it should be, but ended with a comma. 5). Two lines after eq. (3), \"let ... denotes\" -> \"let ... denote\".\n\nIn sum, the paper deals with a more general RL setting, with some interesting theoretical developments. However, the paper might still need to be improved in order to clear the bar of acceptance.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. It would be good if the authors could elaborate and justify more about the assumptions that I have mentioned above.\n2. A thorough and careful grammar and writing check is necessary.\n3. Discussion about the technical novelty is necessary.\n4. Discussion on the optimality of the upper bound would be ideal.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WDvIunFYjF", "reviewer": "Reviewer_yAcd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- There has been a large amount of work over the last few years on constrained RL. This work considers a novel constrained RL setting—infinite horizon with nonlinear objective and constraints—and obtains a guarantee which, at least in the horizon dependence, appears to be optimal.\n- As far as I can tell the results are technically correct.\n- Simulation results demonstrate that a posterior sampling version of the algorithm achieves state-of-the-art performance. \n\nWeaknesses:\n- The result feels somewhat incremental. My understanding is that the primary novelty is considering nonlinear constraints in the infinite-horizon setting. Infinite-horizon constrained RL with linear constraints and finite horizon with nonlinear constraints have both been studied before, so the only real novelty is combining these.\n- In addition, the techniques and algorithm feel largely standard.\n- The ergodicity assumption seems rather strong, and is likely not necessary ((Chen et al., 2022) remove this assumption in the linear case, with somewhat weaker guarantees).\n- No discussion of optimality is given. It seems the $T$ dependence is optimal, but it’s not clear the dependence on the remaining parameters is optimal (I would guess it is not—for example you would expect a $\\sqrt{S}$ instead of the obtained $S$ dependence). \n- The exposition could be cleaned up somewhat (see comments below). ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies reinforcement learning with constraints, and is the first to consider this setting with nonlinear constraints and objectives in the infinite horizon setting. At each step, the learner receives a reward signal and $d$ constraint signals. The goal is to then maximize a (concave) function of the average reward, while ensuring that the average constraint signals satisfy a convex constraint. They propose an optimism-style algorithm and show that it provably achieves $O(1/\\sqrt{T})$ average regret and the final constraint signal averages satisfy the desired constraint with high probability.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "- It is not clearly stated what the goal is. From reading equation (3), it is unclear whether the agent simply wants to find a policy with maximal reward satisfying the constraints (a PAC problem), or solve it in an online manner. This becomes clear by section 5, but clearly stating the objective in section 3 would help clarify things. \n- In general the standard RL setup considers linear rewards (and linear constraints, in the constrained setting). Several examples are given to justify the study of nonlinear functions of the rewards and constraints but, given that it is somewhat non-standard and that this is the primary novelty of the work, more justification and discussion would be helpful. \n- As mentioned above, (Chen et al., 2022) also consider the weakly communicating case (I.e. removing the ergodicity assumption). Obtaining a result in this setting would be ideal, but at least some discussion of this setting should be given. \n- The setting of $K$ given in Theorem 5.6 depends depends on $T_M, C$, and $\\rho$, which the learner in general may not know. It would be helpful to state how the regret and constraint violations scale if these parameters are not known and $K$ is therefore chosen differently. \n- There were numerous minor typos and incorrect word uses throughout the paper. For example, in the last paragraph on page 1, the sentence beginning “Much recently” should begin “More recently”. There were many other similar instances (too many for me to list here), or places where “the” or other minor words were dropped. The main idea was still conveyed in every case I found, but the number of typos was very distracting. As such, I think it’s important that these are fixed for the final version.\n\nIn addition, there were several missing or unclear definitions throughout that should be fixed. In particular:\n- The definition of the MDP should contain an initial state distribution.\n- It is never spelled out what the acronym “CMDP” means.\n- $\\pi*$ is never defined.\n- The definition of the mixing time should have a max over $s$ and $s’$ as well I believe.\n- It is stated in words what $V_\\gamma^{\\pi,P}(s)$ is but this should be defined mathematically.\n- $V_\\gamma^{\\pi,P}(s;i)$ is never defined.\n- $P_{\\pi,s}^t$ is defined in words but it would be helpful to also define mathematically.\n- In the definition of $C(T)$, I believe the subscript on the final $c$ term should be $c_d$ not $c_1$.\n- In the experiments section, the PS-CURL algorithm is referenced but it is never stated in the text what algorithm this is (I assume it is the algorithm described in section 5.1 but this should be clarified).\nWhile several of these terms might be obvious and standard, I believe it is important that they are clearly spelled out.\n", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "0MdO4XcjJy", "reviewer": "Reviewer_xsiA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(1) The authors formulate a class of constrained reinforcement learning problems using the general value functions, instead of standard cumulative additive forms of reward functions. It is meaningful to study this class of RL problems since many practical RL objectives do not have the standard forms, e.g., regularized RL problems.\n\n(2) The authors employ the conservative constrained optimization and the upper confidence bound of transitions to propose a UCRL type algorithm for the constrained RL problem with general value function. The authors provide a sublinear regret analysis that has some new features, e.g., the conservative offset can be used to limit the growth of the regret and constraint violation, and the performance gap of the optimistic policy under the optimistic and true models can be bounded by the Bellman errors. \n\n(3) The authors provide an experiment to show how the proposed method can handle the constraints, which is useful. \n\n\nWeaknesses:\n\n(1) It is less discussed about the motivation of using general value functions in constrained reinforcement learning problems. It would be helpful to readers if the authors could discuss one or two typical examples in details, e.g., fairness.\n\n(2) For the related work, it might be not fair to compare different algorithms from finite or infinite horizon setups. Although we can relate them conceptually, algorithms designed for these two setups seem to be different, especially how to design/assume online exploration. Instead of comparing all algorithms, it is useful to focus a class of algorithms in infinite horizon setup and make a comparison in more technical details.\n\n(3) The ergodicity assumption (Assumption 3.1) is restrictive for the applicability of the proposed algorithm. It is more useful if the authors can weak this assumption or remove it, since the upper confidence bounds already encourage some level of exploration. \n\n(4) In the regret bound, the probability depends on the length of horizon $T$. It might be confusing to call it high probability bound, since the probability can't be arbitrarily large in a way that is independent of the algorithm. It would be useful to remove the dependence on $T$ in the high probability. \n\n(5) It is not very clear to me how posterior sampling works for your algorithms. It is useful to state the algorithm and regret in the paper since this is also an interesting part of the paper. ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the constrained reinforcement learning problem with general value functions in the infinite-horizon tabular setting. The authors employ the conservative approach from constrained optimization to propose a model-based RL algorithm for learning a constrained optimal policy. The authors prove that the proposed method has sublinear regret and zero constraint violation with high probability, under some assumptions on the underlying problem. The authors also show that the proposed method can be used for posterior sampling while enjoying a Bayesian regret. The authors also demonstrate the effectiveness of the proposed method by comparing it with other two methods in some experiments.   ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I provide some revision suggestions when weaknesses are discussed above. \n\nSome other questions are given as follows.\n\n(1) It is useful to provide a formal proof of the convexity of constraint Eq. (16), since it is not obvious.\n\n(2) How do you choose the confidence bound in Eq. (18)? Is it optimal?\n\n(3) In Algorithm 1, do you need to fix $T$? This is assumed by the theorem.\n\n(4) Typos like 'Equation equation 11' and missing reference '(?)Lemma 1]osband2013more'\n\n(5) In experiments, it seems the constrained value converges to some small positive constant. This might contradict the zero violation performance in theory. Can you comment the reason for this?\n\n(6) It is helpful if the authors can test the proposed method in other practical applications, e.g., fairness?\n\n(7) Grammatical errors need to be cleared. ", "broader_impact_concerns": "As mentioned, the paper studies a class of constrained RL problems that have the potential to address fairness issues. It is important to discuss this potential in depth: pros and cons of your model or method in real-world scenarios. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers are generally positive about the work, which gives solid contributions in an interesting setting. Even though the algorithm and analysis are built on previous work, the results are useful additions to the literature. The author responses clarified several questions raised in the reviews, and made further improvements such as adding a discussion of the ergodicity assumption and proofreading. The work is now ready for acceptance.

A few minor suggestions:

* When a citation is used as a noun, use \citet instead of \citep. So "the discussion in (Altman & Schwartz, 1991)" would become "the discussion in Altman & Schwartz (1991)".

* Make the language in assumption A.1 precise. "The MDP M is ergodic, or ..." Should "or" be "and" instead?

* There is no need to start a new page for a new section in the appendix.
Decision: Accept (poster)