Anytime-Competitive Reinforcement Learning with Policy Prior
Authors: Jianyi Yang
Pengfei Li
Tongxin Li
Adam Wierman
Shaolei Ren
Venue: NeurIPS 2023 poster (2023)
Keywords: Markov Decision Process
Constrained Reinforcement Learning
Anytime Competitive Constraints

Abstract: This paper studies the problem of Anytime-Competitive Markov Decision Process (A-CMDP). Existing works on Constrained Markov Decision Processes (CMDPs) aim to optimize the expected reward while constraining the expected cost over random dynamics, but the cost in a specific episode can still be unsatisfactorily high. In contrast, the goal of A-CMDP is to optimize the expected reward while guaranteeing a bounded cost in each round of any episode against a policy prior. We propose a new algorithm, called Anytime-Competitive Reinforcement Learning (ACRL), which provably guarantees the anytime cost constraints. The regret analysis shows the policy asymptotically matches the optimal reward achievable under the anytime competitive constraints. Experiments on the application of carbon-intelligent computing verify the reward performance and cost constraint guarantee of ACRL.

Anytime-Competitive Reinforcement Learning with Policy Prior
Jianyi Yang UC Riverside Riverside, CA, USA jyang239cucr.edd edu
Pengfei Li UC Riverside Riverside, CA, USA pli081@ucr edu
Tongxin Li
CUHK Shenzhen Shenzhen, Guangdong, China litongxin@cuhlk edu. cn
Adam Wierman Caltech Pasadena, CA, USA adamw&calteche edu
Shaolei Ren
UC Riverside Riverside, CA, USA shaolei@ucr.. edu
Abstract
This paper studies the problem Anytime- Competitive Markov Decision Process (A-CMDP). Existing works on Constrained Markov Decision Processes (CMDPs) aim to optimize the expected reward while constraining the expected cost over random dynamics, but the cost in specific episode can still be unsatisfactorily high. In contrast, the goal of A-CMDP is to optimize the expected reward while guaranteeing bounded cost in each round of any episode against policy prior. We propose a new algorithm, called Prytime-Competitie Reinforcement Learning (ACRL), which provably guarantees the anytime cost constraints. The regret analysis shows the policy asymptotically matches the optimal reward achievable under the anytime competitive constraints. Experiments the application of carbon- intelligent computing verify the reward performance and cost constraint guarantee of ACRL.
Introduction
In mission-critical online decision-making problems such as cloud workload scheduling 2y 20 cooling control in datacenters [3 16. 46], battery management for Electrical Vehicle (EV) charging [57 [6]] and voltage control in smart grids 5 73 there is always need to improve the reward performances while meeting the requirements for some important cost metrics. In these mission- critical systems, there always exist some policy priors that meet the critical cost requirements, but they may not perform well in terms of the rewards. In the application of cooling control, for example, some rule- based heuristics (19 46 have been programmed into the real systems for long time and have verified performance in maintaining a safe temperature range, but they may not achieve a high energy efficiency. In this paper, design Reinforcement Learning (RL) algorithm with the goal of optimizing the reward performance under the guarantee of cost constraints against policy prior for any round in any episode.
Constrained RL algorithms have been designed to solve various Constrained MDPs (CMDPs) with reward objective and cost constraints. Among them, some designed to guarantee the expected cost constraints [6] [2], some can guarantee the cost constraints with a high probability (w.h.p.)
[R], and others guarantee bounded violation of the cost constraints 26 29 21 22 [1. In addition, conservative RL algorithms [27] 68 31 [5
consider constraints that require the performance of
learning agent is worse than known baseline policy in expectation or with high probability. 27 points out that is impossible to guarantee the constraints for any round with probability
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Unknown dynamic
Expected constraints or constriants w.h.p. With violation
Any-episode constraints
Anytime--ompelltive
Methods
violation
constraints
saminng-uggmentation Constrained RL
NIA
N/A
XR ST X
x
22 1
Conservative RL
N/A
68S
AN
4B1
35
X
x
ACRL (this work)
Table I: Comparison between ACRL and most related works.
one while such guarantees are desirable. In real mission-critical applications, the cost constraints are often required to be satisfied at each round in any episode even in the worst case, but such anytime constraints are not guaranteed by the existing constrained/conservatvee RL policies. Recently, Searning-augmente online control algorithms B37 38 69
17 331 have been developed to exploit machine learning predictions with the worst-case control performance guarantee. Nonetheless, the Baaning-auggment control algorithms require the full knowledge of the dynamic models, which limits their applications in many systems with unknown random dynamic models. summary of most relevant works is given in T
[5]
To fill in this technical blank, we model the mission-critical decision-making problem as new Markov Decision Process (MDP) which is called the mnytime-Competitiv MDP (A-CMDP). In A-CMDP, the environment feeds back reward and cost corresponding to the selected action at each round. The next state is updated based on a random dynamic model which is a function of the current action and state and not known the agent. The distribution of the dynamic model is also unknown to the agent and needs to be learned. Importantly, at each round h in any episode, the policy of A-CMDP must guarantee that the cumulative cost Jn. is upper bounded by scaled cumulative cost the policy prior π! plus a relaxation, i.e. Jn S (1 + A)JY + hb with X, b > O, which is called an anytime competitive constraint or anytime competitiveness. The term "competitive" or "commptitiveness" is used to signify the performance comparison with a policy prior. Under the anytime cost competitiveness for all rounds, the RL agent explores the policy to optimize the expected reward.
The anytime competitiveness guarantee is more strict than the constraints in typical constrained or conservative MDPs, which presents new challenges for the RL algorithm design. First of all, the anytime competitive constraints are required to be satisfied for any episode, even for the early episodes when the collected sequence samples are not enough. Also, to guarantee the constraints for each round, we need to design a safe action set for each round to ensure that feasible actions exist to meet the constraints in subsequent rounds. Last but not least, without knowing the full transition model, the agent has access to the action sets defined by the anytime competitive constraints. Thus, in comparison to the control settings with known transition models 38 competitiveness for MDPs is more challenging.
ensuring the anytime
Contributions. this paper, we design algorithms to solve the novel problem of A-CMDP. The contributions are summarized as follows. First, we propose an -ortpee-Competttivee Decision-makinn (ACD) algorithm to provably guarantee the anytime competitive constraints for each episode. The key design in ACD is projection to safe action set in each round. The safe action set is updated at each round according to a designed rule to gain as much flexibility as possible to optimize the reward. Then, we develop a new model-based RL algorithm (ACRL) to learn the optimal ML model used in ACD. The proposed model-based RL can effectively improve the reward performance based on the new dynamic defined by ACD. Last but not least, give rigorous analysis on the reward regret of ACRL compared with the performs well as the optimal ACD policy and there exists a fundamental trade-off between the optimization of the average reward and the satisfaction of the anytime competitive constraints.
policy. The analysis shows that the learned policy
2 Related Work
Constrained RL. Compared with the existing literature on constrained RL 68 17 67 I0, 13 21
29 26 22 51, our study has important differences. Concretely, the existing constrained RL works consider average constraint with or without constraint violation. In addition, existing conservative RL works (68] consider an average constraint compared with policy prior. However, the constraints can be violated especially at early exploration episodes. In sharp contrast, our anytime competitive

---

constraint ensures a strict constraint for any round in each episode, which has not been studied in the existing literature as shown in Table In fact, with the same policy prior, our anytime competitive policy can also meet the average constraint without violation in conservative/constraiee RI. 68 25
[56] considers MDPs that satisfy safety constraint with probability one and proposes an approach with a high empirical performance. However, there is no theoretical guarantee for constraint satisfaction. Comparably, our method satisfies the constraint with theoretical guarantee, which is essential to deploy AI for mission-criticss applications.
1 focus on constraining that the system state or action at each time h cannot fall into certain pre- deeermemeededd restricted regions (often with a high probability), which is orthogonal to our anytime competitiveness requirement that constrains the cumulative cost at each round of an episode. Our study is related to RL with safety constraints IT 39 , but is highlighted by the strict constraint guarantee for each round in each episode. In a study on safe RL [1O), the number of safety violation events is constrained almost surely by budget given in advance, but the safety violation value can still be unbounded. By contrast, our work strictly guarantees the anytime competitive constraints by designing the safety action sets. In recent study B the safety requirement is formulated as the single-round cost constraints. Differently, we consider cumulative cost constraints which have direct motivation from mission-critiaal applications.
Our study is also relevant to safe RL. Some studies on safe RL
[0
aaamiing-augmentte online preision-makingg average performance but suffer from unbounded worst-case performance. To meet the requirements for the worst-case performance of learning- basedd policies. tetrminggauggmenn
mhariing-based policies can usually achieve good
algorithms are devel- To guarantee the performance for algorithm can perform an online switch between MI. policy and prior [5I], combine the MI. policy and prior with an adaptive parameter 38], or project the ML actions into safe action sets relying on the prior actions (35) Compared with Searning-augment algorithms, we consider more general online settings without knowing the exact dynamic model. Also, our problem can guarantee the cost performance for each round in any episode compared with a policy prior, which has not been studied by existing
oped for online control/optimizztion problems [R 51
177
35 34]
each problem instance, learning-augmentt
algorithms.
3 Problem Formulation
3.1 Anytime-Competice MDP
In this section, we introduce the setting of a novel MDP problem called Markov Decision Process (A-CMDP), denoted as M, 9, H, , c, n. x1). In A-CMDP, each episode has H rounds. The state at each round is denoted as Iy E X, h E [H] At each round of an episode, the agent selects an action a₁ from an action set A. The environment generates a reward ry (Vn, ax) and a cost Oy (Ih, an) with The E R and C₁ C. We model the dynamics as Th+1 = fa,,,, as) where fn F is a random transition function drawn from an unknown distribution s(fx) with the density g E G. The agent has no access to the random function fn. but can observe the state Iy at each round h. Note that we model the dynamics in function style for ease of presentation, and this dynamic model can be translated into the transition probability in standard MDP models 59 3 as P( xn. an) = Σ,, 1(fn (Zh, an) (fx)) A policy π is a function
which gives the action on for each round h e [H]. Let V (x) = E - ru( a:)) | I = x denote the expected value of the total reward from round h by policy æ. One objective of A- CMDP is to maximize the expected total reward starting from the first round which is denoted as Ez, [VT (I;) = E Σdh Th (2 (x))
Besides optimizing the expected total reward as in existing MDPs, A-CMDP also guarantees the anytime competitive cost constraints compared with a policy prior T!. The policy prior can be a policy that has verified cost performance in real systems guaranteed cost performance. for which concrete examples will be given in the next section. Denote y = (fh, ch2 rh), and y1:H = {yn H E = F x R C is sampled sequence of the models in an A-CMDP. Let J (y1.)) = E'= (i a.) be the cost up to round h E [H] with states x,, í E [M] and actions a, i E [6] of a policy Also, let JE' (yI-)) Σi cx a.) be the cost of the prior with states n.. i E [+] and actions a!,+ i E [h] of the prior tt. The anytime competitive constraints are defined as below.
heuristic policy with strong empirically-
3

---

Definition 3.1 (Anytime competitive constraints). If a policy æ satisfies (A, 6) anytime competitive- ness, the cost of π never exceeds the cost of the policy prior n¹ relaxed by parameters À 2 0 and 2 0, i.e. for any round h in any model sequence yI.H E 3 holds that J (yI.)) S (1+A)JE' (vI:))
Now, we can formally express the objective of A-CMDP with II being the policy space as
max Ezy [V] (z1)), s.t. (vI:)) S (1 + X)JÆ (vI.H) ) + hb, 4h E [H], VyL.H E V. wlll
Let x 6 be the collection of policies that satisfy the anytime competitive constraints in D. We design anytime-competitive RL algorithm that explores the policy space X7 in K episodes to optimize the expected reward Egg [V (z])]. Note that different from constrained/conservtivee MDPs I1 67,, the anytime competitive constraints in ① must be satisfied for any round in
(26 29 61 688
any sampled episode y1-H E 3 given relaxed parameters X, b 2 0. To evaluate the performance of the learned policy nh 11,,b, k E [K] and the impact of the anytime competitive constraints, we consider the regret performance metric defined as
K Σ Ex (21) - VT (01) with x² lII,6
Regret (K)
where n² = arg max Eay (VT(((r) is an optimal policy without considering the anytime com- becomes larger, the constraints get less strict and the algorithm
petitive constraints. When has more flexibility to minimize the regret in ( Thus, the regret analysis will show the trade-off between optimizing the expected reward and satisfying the anytime cost competitiveness.
In this paper, we make additional assumptions on the cost functions, transition functions, and the prior policy which are important for the anytime-competitive algorithm design and analysis.
Assumption 3.2. All the cost functions in the space C have a minimum value c 2 0, i.e. V(z, a), wh E [H] Ch. (z, a) 2 2 and are Le- Lipschiit continuous with respect to action an and the state zh- All the transition functions in the space F are Ly-Liscchitz continuous with respect to action a₁ and the state Vr. The parameters e, L.. and Ly are known to the agent.
The Lipschitz continuity of cost and transition functions can also be found in other works on model- based MDP 45 5 28 The Lispchitz assumptions actually apply many continuous mission-critical systems like cooling systems [T). power systems [54] 15 and carbon- aware datacenters 49] In these systems, the agents have no access to concrete cost and transition functions, but they can evaluate the Lipschitz constants of cost and dynamic functions based on the prior knowledge of the systems. The minimum cost value can be as low as zero, but the knowledge of positive minimum cost c can be utilized to improve the reward performance which will be discussed in Section 5.1
Definition 3.3 (Telescoping policy). A policy v satisfies the telescoping property if the policy is applied from round h₁ to h2 with initialized states The and s'h,, it holds for the corresponding states The and Th at round h2 that
|0hh shhn S p(h2 - In ) - -5/,, Il.
where p(h) is called a perturbation function with h and p(0) = 1. Assumption 3.4. The prior policy n² satisfies the telescoping property with some perturbation function p. Furthermore, nt is Lipschitz continuous.
The telescoping property in Definition 5.3 indicates that with an initial state perturbation at fixed round, the maximum divergence of the states afterwards is bounded. Thus, the perturbation function p measures the sensitivity of the state perturbation with respect to policy prior. The telescoping property is satisfied for many policy priors 600 43 It is also assumed for perturbation analysis in model predictive control
Note that in A-CMDP, the constraints are required to be satisfied for any round in any sequence, which is much more stringent than constraint satisfaction in expectation or with a high probability. In fact, the any-time constraints cannot be theoretically guaranteed without further knowledge on the system & [6 This paper firstly shows that Assumption
3.2 and Assumption 3.4 which are reasonable for 40 are enough to guarantee the anytime competitive constraints, thus advancing the deployment of RL in iission-critica applications.
many mission-critical applications [6

---

3.2 Motivating Examples
The anytime competitiveness has direct motivations from many mission-critical control systems. We present two examples in this section and defer other examples to the appendix.
Safe cooling control in data centers. In mission-critical infrastructures like data centers, the agent needs to make decisions on cooling equipment management to maintain a temperature range and achieve a high energy efficiency. Over many years, rule-based policies have been used in cooling systems and have verified cooling performance in maintaining a suitable temperature for computing [4.. Recently, RL algorithms are developed for cooling control in data centers to optimize the energy efficiency 633 16. A6l. The safety concerns of RL policies, however, hinder their deployment in real systems. In data centers, an unreliable cooling policy can overheat devices and denial critical
services, causing huge loss [99 46. The safety risk is especially high at the early exploration stage of RL in the real environment. Therefore, it crucial to guarantee the constraints on cooling performance at anytime in any episode for safety. With the reliable rule-based policies as control priors, A- A-CMDP can accurately model the critical parts of the cooling control problem, opening a path towards learning reliable cooling policies for data centers.
Workload scheduling in carbon-intelln bittlliittllligent computing. The world is witnessing a growing demand for computing power due to new computing applications. The large carbon footprint of computing has become a problem that cannot be ignored [40]
Studies find that the amount of carbon emission per kilowatt-houu on electricity grid varies with time and locations due to the various types Exploiting the time-varying property of carbon efficiency, recent studies are developing workload scheduling policies (e.g. delay some temporally flexible workloads) to optimize the total carbon efficiency [49]. However, an unreliable workload scheduling policy in data centers can cause a large computing latency, resulting in an unsatisfactory Quality of Service (QoS). Thus, to achieve a high carbon efficiency while guaranteeing low computing latency, we need to solve an A-CMDP which leverages RL to improve the carbon efficiency while guaranteeing the QoS constraints compared with a policy prior targeting at computing latency [20, 30 12
64
52
of electricity generation B3 32 g
This also resembles the practice of carbon- tettlnn-ntelligentt computing adopted by Google
49
4 Methods
In this section, first propose algorithm to guarantee the anytime competitive constraints for any episode, and then give an RL algorithm to achieve a high expected reward under the guarantee of the anytime competitive constraints.
4.1 Guarantee the Anytime Constraints
It is challenging to guarantee the anytime competitive constraints in ① for an RL policy in any episode due to the following. First of all, in MDPs, the agent can only observe the real states {æx 1 corresponding to the truly-selected actions {an h==1 The agent does not select the actions af. of the prior, so the states of the prior x) are virtual states that are not observed. Thus, the agent cannot evaluate the prior cost J which is in the anytime competitive constraint at each round h. Also, the action at each round h has an impact on the costs in the future rounds i, > h based on the random transition models f., 2 h. Thus, besides satisfying the constraints in the current round, we need to have good planning for the future rounds to avoid any possible constraint violations even without the exact knowledge of transition and/or cost models. Additionally, the RL policy may be arbitrarily bad in the environment and can give high costs (especially when very limited training data is available), making constraint satisfaction even harder.
h=1
Despite the challenges, we design safe action sets {A,,, h E [H]} to guarantee the anytime competitive constraints: if action 0n is strictly selected from A,, for each round h, the anytime competitive constraints for all rounds are guaranteed. As discussed above, the anytime competitive constraints cannot be evaluated any time since the policy prior's 's state and cost information not available. Thus, we propose to convert the original anytime competitive constraints into constraints that only depend on the known parameters and the action differences between the real policy and the policy prior. We give the design of the safe action sets based on the next proposition. For the ease of presentation, we denote 6; = es (I2, a4) as the real cost and ei = <=(x], n (xx)) as the cost of the policy prior round i.
5

---

Proposition 4.1. Suppose that Assumption 3.2 and 3.4 are satisfied. At round h with costs {cr {c:] h-1 observed, the anytime competitive constraints J S (1 + A)JE + h'b for rounds h' h,. .. , are satisfied if for all subsequent rounds h' = h, ..... H,
W
Taallay - x (x,))l - GRN, Vh' = h.... H,
(4)
where T = Eten U3.. (j
E [H Vn 2 1), with 9is = Le = i) + Le(1 + 1
1 1-j)1(j < 1), (vj [H 2 j), relying on known parameters, and GA is called the allowed
deviation which is expressed as
h-1
GAN = Σ ((++) - -a- 1 -aadd)) + (h' - h + 1)(Ae + b).
(5)
i=1
where of max 15.4-Ei T! (I,))l. E [H] is the action difference at round j.
Ej=1 -,,4, (Vi E [AT), the lower bound of of ch, and d3 = ||aj
At each round h E [H], Proposition 4.1 provides sufficient condition for satisfying all the anytime competitive constraints from round to round given in ① The meanings of the parameters in Proposition 4.1 are explained as follows. The weight Qj.i measures the impact of action deviation at round j on the cost difference |c; - c/| at round Z j. and the weight ja indicates the total impact of the action deviation at round j on the sum of the cost differences from rounds n to round H. Based on the definition of qj.i, we get é! as a lower bound of the prior cost c/. With these bounds, we can calculate the maximum allowed total action deviation compared with the prior actions x xzz)) from round j = to h' as GA,K"
By applying Proposition 1.1 at initialization, we can guarantee the anytime competitive H we ensure that for all rounds h' [H] En Pyailay l|ay - x (z,)) GI, = hi(Ae + b). This sufficient condition is long-term constraint relying on the relaxation parameters and b. Although we can guarantee the anytime competitive constraints by the sufficient condition obtained at initialization, we apply Proposition 4. at all the subsequent rounds with the cost feedback information to get larger action sets and more flexibility to optimize the average reward. In this way, we can update the allowed deviation according to the next corollary.
conştraints for all rounds h
Corollary 4.2. Al round 1, we initialize the allowed deviation as D de + b. At round h, h 1. the allowed deviation is updated as
Dn = max (Da-1 + de + b- Th-1,--14h-- RE-1 + de + b}
(6)
where RA-1 Ei= (1 + Ajεt c; - -rnnd)) with notations defined in Proposition 4.1 The
(X, aanttime competitive constraints in Desinition 3.7 are satisfied it holds at each round h that h ar 7 (zx)]l S Dr.
Corollary 4 gives a direct way to calculate the allowed action deviation at each round. In the update rule 6 of the allowed deviation, the first term of the maximum operation is based on the deviation calculation at round
1 while the second term is obtained by applying Proposition 4. for round
We can find that the conditions to satisfy the anytime competitive constraints can be controlled by parameters À and b. With larger À and b, the anytime competitive constraints are relaxed and the conditions in Corollary 4.2 get less stringent. Also, the conditions in Corollary 42 rely on the minimum cost value and other system parameters including Lipschitz constants L.s Lyy L,t and telescoping parameters p through Ti. Since Th. increases with the Lipschitz and telescoping parameters, even if the estimated Lipschitz constants and the telescoping parameters are higher than the actual values or the estimated minimum cost is lower than the actual value, the obtained condition by Corollary 4.2 is sufficient to guarantee the anytime competitive constraints, although it is more stringent than the condition calculated by the actual parameters.
By Corollary
4.
we can define the safe action set at each round h as
An (Da) {a I I n (xw)l Dr)

---

24 The Algorithm Deyyiime-Compttitee Decision-making (ACD)
Initialization: Initialize allowed deviation: D1 Ac b.
for ..... H do
Obtain the output of the ML policy स as d4.- Select the action a, by projecting an into the safe action set (D,;)) in
Update the allowed deviation Dh+1 by (6
end for
With the safe action set design in 7 we propose a projection- algorithm called ACD in Algorithm|I [ We first initialize an allowed deviation as D1 = de + b. When the output āj of the ML model obtained at each round h, it is projected into safe action set An (2)) depending on the allowed deviation Da. i.e. 4y PAs, (D,) (āx) arg min |a 0 The projection can be
efficiently solved by many existing methods on constrained policy learning [67
11 4
allowed deviation is then updated based on Corollary 4.2. Intuitively, if the actions are closer to the
prior actions before h, i.e. the action deviations fd; M=1 get smaller, then R becomes larger and D₁ becomes larger, leaving more flexibility to deviate from a,, i subsequent rounds.
4.2 Anytine-Compelitive RL
The anytime competitive constraints have been satisfied by Algorithm I but it remains to design an RL algorithm to optimize the average reward under the anytime competitive cost constraints, which is given in this section.
The anyrime-competitive decision-making algorithm in Algorithm [ defines a new MDP, with an additional set of allowed deviations D to the A-MDP defined in Section [.1 denoted as M(X, D, A,F.9. H,,, c, म, T!). In the new MDP, we define an augmented state 8a which in- clude the original state Th, the allowed deviation Dn E DD and history information {c:)= and Hd The transition of Z4 is defined by fr. in Section 3.1 and needs to be learned while the tran- sition of Dj, is defined in (6) and is known to the agent. The ML policy रे gives an output ă and the selected action is the projected action aj (D.(D..) (ān). Then the environment generates reward T (3th, (An(D.)(ān)) and cost (Ih, (D.( (āz) )). Thus, the value function corresponding to the ML. policy मे can be expressed V. (st) E Σm ri( (AN(D)(()))) with ãn being the output of the ML policy For notation convenience, sometimes write the actions of n² and æ as n (s) and T (s) even though they only reply on the original state x in s.
To solve the MDP, propose model-based RL algorithm called ACRL in Algorithm 2 Different from the existing model-based RL algorithms [48 770,, ACRL utilizes the dynamic model of A- CMDP and ACD (Algorithm [ optimize the average reward. Given transition distribution, g episode k perform value iteration update Q
functions for h 1,.... H.
2 (Sh, an) = Th (xn, an) + Eg
(Sh+1) | 8h, an) V (sx) = max (sh,
aEA
(8)
Fg
1 1 (sn+1) 8h, an
Σ
Vih (5441)9))))
JEF
where on = PAn, (āx). Qu+1, 0, VH+LL(()) = O. The transition model g is estimated
as
A-1 H
g² arg min
ΣΣ
Eg
Vi (5442)
s/s on (
(9)
gEG
Based on the transition estimation,
calculate the confidence set of the transition model
A A-1
GN = g g
ΣΣ E,
( 8h, an - -Egr VittaSs444 sn, (aaaa)) anl)² s BB (10)
where Bx is confidence parameter.

---

Algorithm 2 Anytime-Competiin Reinforcement Learning (ACRL)
1: Initialization: Transition model set 9 {
2: for each episode k 1,... K do
3: Observe the initial state sy.
4: Select g = arg max By [v]()
5: Perform value iteration with g in Eqn. 1 and update Q functions Qf ... Qn-
6: for each round h 1,... .. do
7: Run ACD (Algorithm [ by ML policy 7t (sp) = arg max.e (sh, a)
8: Observe state +1 and store values V (0/++))
9: end for
Update transition model g using O and calculate confidence set G6+1.
11:
end for
With a learned ML policy म each episode k. the policy used for action selection is the ACD policy x.. Given the optimal MI. policy #* arg max V/ (s1) with IT being the MI policy space, the optimal ACD policy is denoted as .². For state 8h round h, x² and x² select actions
x² (sn) (A. x (sa)
(F"
(11)
In the definition of A- A-CMDP, the dimension of the augmented state sh increases with the length of the horizon H, which cloud cause scalability issue for implementation. The scalability issues also exit in other RL works with history-dependent states [58] [4]. practice, tractable methods can be
designed through feature aggregation (58) or PODMP 66
5
Performance Analysis
this section, we analyze the reward regret ACRL to show the impacts of anytime cost constraints on the average reward.
5.1 Regret due to Constraint Guarantee
Intuitively, due the anytime competitive constraints Eqn. 1 there always exists an unavoidable reward gap between an ACD policy and the pprimal-unconstrannee policy x². In this section, to quantify this unavoidable gap, we bound the regret of the optimal ACD policy x,, highlighting the impact of anytime competitive cost constraints on the average reward performance.
Theorem 5.1. Assume that the optimal-unconstrer which is LQ & L-Lisschitz continuous with respect to the action a for all x. The regret between the optimal A CCD policy To that satisfies (A, b) anytime competitiveness and the optimal pptimal-unconstrrinned policy π² bounded as
policy n² has value function Q (x, a)
[ Σ LQR 7-
H
}.
Ex VT (x1) - V/"" (x1) I ByL
T (he (Me ( AGR)
(12)
where 1l sup (x) - (x))l is the maximum action discrepancy between the policy prior n and optimal-unconstneee unconstrained policy π"; I'.. is defined in Proposition 4.1 AGr. [R is the gain of the allowed deviation by applying Proposition
round h.
The regret bound stated in Theorem 5.1 is intrinsic and inevitable, due to the committed as- surance of satisfying the anytime competitive constraints. Such a bound cannot be improved via policy learning, i.e, converge to 0 when the number of episodes K + co. This is be- cause satisfy the (X, baaytimee competitiveness, the feasible policy set II defined un- der ①I is subset of the original policy set II, and the derived regret is an upper bound of max Ex, [V] (x1)) maxxellx,, Ez, (v1' Moreover, the regret bound relies on the ac- tion discrepancy 77. This is because if the optimal-unconstrainn
policy n" is more different from the prior I its actions are altered to a larger extent to guarantee the constraints, resulting a larger degradation of the reward performance. More importantly, the regret bound indicates the trade-off

---

between the reward optimization and anytime competitive constraint satisfaction governed by the parameters and b. When À or b becomes larger, we can get smaller regret because the anytime competitive constraints in (1) are relaxed to have more flexibility to optimize the average reward. In the extreme cases when À constraints, so we can get zero regret.
large enough, all the policies in IT can satisfy the anytime competitive
Moreover, the regret bound shows that the update of allowed deviation by applying Proposition based on the cost feedback at each round will benefit the reward optimization. By the definition of - in Corollary 4.2 if the real actions deviate more from the prior actions before h, the gain AG, for 2 h can be smaller, so the actions must be closer to the prior actions in the subsequent rounds, potentially causing larger regret. Thus, is important have a good planing of the action differences [d:) to get larger allowed action deviations for reward optimization. Exploiting the representation power machine learning, ACRL can learn a good planning of the action differences, and the ACD policy x² corresponding to the optimal ML policy #* can achieve the optimal planing of the action differences.
Last but not least, Theorem shows the effects of the systems parameters in Assumption 3.2 and Assumption 3.4 the regret through aa defined Proposition 4. and the minimum cost Observing that I h.h increases with the systems parameters including the Lipschitz parameters Le, L and telescoping parameters p. a higher estimation of the Lipschitz parameters and telescoping parameters can cause a higher regret. Also, lower estimation of the minimum cost value can cause higher regret. Therefore, although knowing the upper bound of the Lipschitz parameters and telescoping parameters and the lower bound of the minimum cost value is enough to guarantee the anytime competitive cost constraints by Proposition 4.1 a lower reward regret can be obtained with more accurate estimation of these system parameters.
5.2 Regret of ACRL
To quantify the regret defined in Eqn. ② it remains bound the reward gap between the ACD policy T and the optimal ACD policy π². In this section, we show that T by ACRL approaches the optimal one TT episode K + oo by bounding the pseudo regret
K Σ (vv' VT (r)(
PReg(K)= = EEI;
(13)
Theorem 5.2. Assume that the value function is bounded by V. Denote a set of function as
{ql 3g (, E S x V. g(s = Esng [u(s') s, al}.
(14)
If 3x = 2 log and (N, olo)) being the covering number of Q. with probability at least 1 8, the pseudo regret of Algorithm is bounded as
2N CVH with a = H log( C being a constant,
(Reg(K)= S doHV + 4 +
(15)
where de- dimg Q R the Eluder dimension of defined in (50)
Theorem 5.2 bounds the pseudo regret for each episode k. The confidence parameter 3g to balance the exploration and exploitation chosen to get the pseudo regret bound as shown Theorem 5.2 A higher 5& is chosen to encourage the exploration if the covering number of the function space Q. the episode length, or the maximum value becomes larger. Also, the pseudo regret relies on the size of the function space Q through do and 3x. With smaller À or b, less actions satisfy Corollary 4.2 given a state, and so smaller state-action space S is obtained, which results smaller size of the function space Q and thus smaller regret.
To get more insights, we also present the overall regret bound when the transition model g can be represented by linear kernel as in ( 7701, i.e. g(f) = (o(f), 0) with dimension of 0 as dg, the reward regret Eqn is bounded as
1 (Ac+b+ AGN)) | =0lV | HolpHHV (16)
Regret (K) (K)SAA KE
LQn 11
Th

---

80
ANN
2
Violation Ratte
0.0
Regret
60
Repret
0.4
0.2
BL--2
BLa-5
30
Epicode
(a) Regret episade
(b) Regret w.r.t. X
(c) Violation rate w.r.t. À
Figure I: Regret and cost violation rate of different algorithms. Shadows in Figure 2 show the
range of the regret.
where Ln
h. 7) I'n. and AG₁, are all defined in Theorem 5.1 The overall regret bound is obtained because under the assumption of linear transition kernel, we have 3x
H)² log( ( (Q, ax ||
50 Thus the pscudo regret is PReg K) = ( H log((/))) which is sublinear in terms of K. With the sublinear pseudo regret PReg(K). the ACD policy x performs as asymptotically well as the optimal ACD policy x when K oc. Combining with the regret of the optimal ACD policy in Theorem 5.1 we can bound the overall regret of ACRL. Since in the definition of regret, ACD policy compared with the optimal-uncon snconstreend policy x², the regret bound also includes unavoidable linear term due to the commitment to satisfy the anytime competitive constraints. The linear term indicates the trade-off between the reward optimization and the anytime competitive constraint satisfaction.
[ls))) H))
l)))) R and the Eluder dimension de (do)
Empirical Results
We experiment with the application of resource management for carbon-aware computing : to empirically show the benefits of ACRL. The aim of the problem is to jointly optimize carbon efficiency (QoS), In this problem, there
and revenue while guaranteeing the constraints on the quality-of- exists a policy prior n which directly optimizes QoS based on estimated models. our experiment, we apply ACRL to optimize the expected reward and guarantee that the real QoS cost is no worse than that of the policy prior. The concrete settings can be found in Appendix A
Figure (a) gives the regret changing the first 500 episodes. Figure lb shows the regret with different and b, demonstrating the trade-off between reward optimization and the satisfaction of anytime competitive constraints. Figure ][e]shows shows the probability of the violation of the anytime competitive constraints by RI. and constrained RL. ACRL and MI. models with ACD have violation of anytime competitive constraints. More analysis about the results are provided in Appendix A due to space limitations.
Concluding Remarks
This paper considers a novel MDP setting called A-CMDP where the goal is to optimize the average reward while guaranteeing the anytime competitive constraints which require the cost learned policy never exceed that of policy prior It for any round h in any episode. To guarantee the anytime competitive constraints, we design ACD, which projects the output an ML policy into safe action set at each round. Then, we formulate the decision process of ACD new MDP and propose a model-based RL algorithm ACRL to optimize the average reward under the anytime competitive constraints. Our performance analysis shows the tradeoff between the reward optimization and the satisfaction of the anytime competitive constraints.
Future directions. Our results are based on the assumptions on the Lipschitz continuity of the cost, dynamic functions, and the policy prior, as well the telescoping properties of the policy prior, which are also supposed or verified in other literature (5, 28 60. 40 In addition, to guarantee the anytime competitive constraints, the agent is assumed to have access to the Lipschitz constants, the minimum cost value, and the perturbation function. However, since the anytime competitive constraints are much stricter than the expected constraints or the constraints with a high probability, there is no way to guarantee them without any knowledge of the key properties of mission-critical system. Our work presents the first policy design to solve A-CMDP, but would be interesting to design seytiiee-compettie policies with milder assumptions in the future.
10

---

Acknowledgement
We would like thank the anonymous reviewers for their helpful comments. Jianyi Yang. Pengfei Li and Shaolei Ren were supported in part by the U.S. NSF under the grant CNS-1910208, Tongxin Li was partially supported by the NSFC grant No. 72301234, the Guangdong Key Lab of Mathematical Foundations for Artificial Intelligence, and the start-up funding UDF01002773 of Adam Wierman was supported in part by the U.S. NSF under grants CNS-21468 14, CPS-2136197, CNS-2106403, NGSDI-2105648.
References
[1] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International conference on machine learning, pages 22-31. PMLR, 2017.
[2] Sanae Amani, Christos Thrampoulidis, and Lin Yang. Safe reinforcement learning with linear function approximation. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 243-253. PMLR, 18 24 Jul 2021.
[3] Sanae Amani, Christos Thrampoulidis, and Lin Yang. Safe reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 243-253 PMLR, 2021.
[4] Brandon Amos and J Zico Kolter. Optnet:
Differentiable optimization as a layer in neural networks. In International Conference on Machine Learning, pages 136-145. PMLR, 2017.
[5] Kavosh Asadi, Dipendra Misra, and Michael Littman. Lipschitz continuity in model-based reinforcement learning. In International Conference on Machine Learning, pages 264-273. PMLR, 2018.
[6] Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based rein- forcement learning with value-targeted regression. In International Conference on Machine Learning, pages 463-474. PMLR, 2020.
[7] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alee Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1877-1901. Curran Associates, Inc., 2020.
[8] Lukas Brunke, Melissa Greeff, Adam W Hall, Zhaocong Yuan, Siqi Zhou, Jacopo Panerati, and Angela P Schoellig. Safe learning in robotics: From learning-based control to safe reinforcement learning. Annual Review of Control, Robotics, and Autonomous Systems, 5:4 1-444, 2022.
[9] Duncan Callaway, Meredith Fowlie, and Gavin McCormick.
Location, location, location: The variable value of renewable energy and demand-side efficiency resources. Journal of the Association of Environmental and Resource Economists, 5(1):39-75, 2018.
[10] Agustin Castellano, Hancheng Min, Juan Bazerque, and Enrique Mallada. Reinforcement learning with almost constraints. In Learning for Dynamics and Control, 2022.
[11] Bingqing Chen, Priya L Donti, Kyri Baker, J Zico Kolter, and Mario Bergés. Enforcing policy feasibility constraints through differentiable projection for energy optimization. In Proceedings of the Twelfth ACM International Conference Future Energy Systems, pages 199-210, 2021.
[12] Shuang Chen, Christina Delimitrou, and José Martínez. Parties: Qos-aware resource parti- International
tioning for multiple interactive services. In Proceedings of the Conference on Architectural Support for Progrumming Languages and Operating Systems, pages 107-120, 2019.
11

---

[13] Weiqin Chen, Dharmashankar Subramanian, and Santiago Paternain. Policy gradients for probabilistic constrained reinforcement learning, 2022.
[14] Xiaoyu Chen, Xiangming Zhu, Yufeng Zheng, Pushi Zhang, Li Zhao, Wenxue Cheng, Peng Cheng, Yongqiang Xiong, Tao Qin, Jianyu Chen, et al. An adaptive deep rl method for non-stationary environments with piecewise stable context. Advances in Neural Information Processing Systems, 35:35449- 2022.
[15] Xin Chen, Guannan Qu, Yujie Tang, Steven Low, and Na Li. Reinforcement learning for decision- decision-making and control in power systems: Tutorial, review, and vision. arXiv, 2021.
[16] Yuri Chervonyi, Praneet Dutta, Piotr Trochim, Octavian Voicu, Cosmin Paduraru, Crystal Qian, Emre Karagozler, Jared Quincy Davis, Richard Chippendale, Gautam Bajaj. et al. Semi-analytical industrial cooling system model for reinforcement learning. arXiv preprins arXiv:2207.13131, 2022.
[17] Nicolas Christianson, Junxuan Shen, and Adam Wierman. Optimal robustness-consistenn tradeoff's for
metrical task systems. In Al STATS, 2023.
[18] Eli Cortez, Anand Bonde, Alexandre Muzio, Mark Russinovich, Marcus Fontoura, and Ricardo Bianchini. Resource central: Understanding and predicting workloads for improved resource management in large cloud platforms. In Proceedings of the 26th Symposium on Operating Systems Principles, pages 153-167, 2017.
[19] Google DeepMind. ing and industrial control. safety- firs-firtt-ar ai- for- autonomous- dattnaouuu-da-----ee centre- cooling and- industrial contror 2018.
Safety-first ai for autonomous data
centre cool-
https: http:s///www.eepiiidd..oo ceteppinndccommbllgg....
[20] Christina Delimitrou and Christos Kozyrakis. Paragon: Qos-aware scheduling for heterogeneous datacenters. ACM SIGPLAN Notices, 48(4):77-88, 2013.
[21] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligence and Statistics, pages 3304-3312. PMLR, 2021.
[22] 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:8378 8390, 2020.
[23] Jesse Dodge, Taylor Prewitt, Remi Tachet des Combes, Erika Odmark, Roy Schwartz, Emma Strubell, Alexandra Sasha Luccioni, Noah A Smith, Nicole DeCario, and Will Buchanan. Measuring the carbon intensity of ai in cloud instances. In 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 1877-1894, 2022.
[24] Priya L Donti, David Rolnick, and Zico Kolter. Dc3: A learning method for optimization with hard constraints. arXiv preprint arXiv:2104.12225, 2021.
[25] Yihan Du, Siwei Wang, and Longbo Huang. A one-size-fitss filt--lllllll solution conservative bandit problems. In AAAI, 2021.
[26] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitation in constrained mdps. arXiv preprini arXiv:2003.02/88) 2020.
[27] Evrard Garcelon, Mohammad Ghavamzadeh, Alessandro Lazaric, and Matteo Pirotta. Conserva- tive exploration in reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 143 1431-. PMLR, 2020.
[28] Carles Gelada, Saurabh Kumar, Jacob Buckman, Ofir Nachum, and Marc G Bellemare. Deep- mdp: Learning continuous latent space models for representation learning. In International Conference on Machine Learning, pages 2170-2179. PMLR, 2019.
[29] Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Provably efficient model-free constrained rl with linear function approximation. arXiv preprint arXiv:2206.1 11889, 2022.
12

---

[30] fñigo Goiri, Kien Le, Md E Haque, Ryan Beauchea, Thu D Nguyen, Jordi Guitart, Jordi Torres, and Ricardo Bianchini. Greenslot: scheduling energy consumption in green datacenters. In Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-11, 2011.
[31] Sumeet Katariya, Branislav Kveton, Zheng Wen, and Vamsi K Potluru. Conservative exploration using interleaving. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 954-963. PMLR, 2019.
[32] Imran Khan. Temporal carbon intensity analysis: renewable versus fossil fuel dominated electricity systems. Energy Sources, Part A: Recovery, Utilization, and Environmental Effects, 41(3):309-333 02100999-2,,22 2019.
[33] Mo Li, Timothy M Smith, Yi Yang, and Elizabeth J Wilson. Marginal emission factors considering renewables: A case study of the us midcontinent independent system operator (miso) system. Environmental science & technology, 5191) 1215-11122111122 2017.
[34] Pengfei Li, Jianyi Yang, and Shaolei Ren. Expert-calibrated learning for online optimization with switching costs. Proc. ACM Meas. Anal. Comput. Syst., 6(2), Jun 2022.
[35] Pengfei Li, Jianyi Yang, and Shaolei Ren. Robustified learning for online optimization with memory costs. INDOCOM, 2023.
[36] Tongxin Li, Yue Chen, Bo Sun, Adam Wierman, and Steven H Low. Information aggregation for constrained online control. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5-2),1335, 2021.
[37] Tongxin Li, Ruixiao Yang. Guannan Qu, Yiheng Lin, Adam Wierman, and Steven H Low. Certifying black-box policies with stability for nonlinear control. IEEE Open Journal of Control Systems, 2:49-62 2023.
[38] Tongxin Li, Ruixiao Yang. Guannan Qu, Guanya Shi, Chenkai Yu, Adam Wierman, and Steven Low. Robustness and consistency in linear quadratic control with untrusted predictions. Proc. ACM Meas. Anal. Comput. Syst., 6(1), feb 2022.
[39] Yingying Li, Subhro Das, Jeff Shamma, and Na Li. Safe adaptive learning-based control for constrained linear quadratic regulators with regret guarantees. arXiv preprint arXiv:2111.00411 2021.
[40] Yingying Li, James A Preiss, Na Li, Yiheng Lin, Adam Wierman, and Jeff Shamma. Online switching control with stability and regret guarantees. arXiv preprint arXiv:22301.08444 2023.
[41] Enming Liang, Minghua Chen, and Steven H. Low. Low complexity homeomorphie projection to ensure neural-network solution feasibility for optimization over (non-)convex set. In ICML, 2023.
[42] Yiheng Lin, Yang Hu, Guannan Qu, Tongxin Li, and Adam Wierman. Bounded-regret mpe via perturbation analysis: Prediction error, constraints, and nonlinearity, arXiv preprint arXiv:2210. 12312, 2022.
[43] Yiheng Lin, Yang Hu, Guanya Shi, Haoyuan Sun, Guannan Qu, and Adam Wierman. Perturbation- regret analysis of predictive control in linear time varying systems. Advances in Neural Information Processing Systems, 44:5174-5185 2021.
[44] Alexandra Sasha Luccioni, Sylvain Viguier, and Anne-Laure Ligozat. Estimating the carbon footprint of bloom, a 166b parameter language model. arXiv preprint arXiv:2211.02000, 2022.
[45] Fan-Ming Luo, Tian Xu, Hang Lai, Xiong-Hui Chen, Weinan Zhang, and Yang Yu. A survey on model-based reinforcement learning. arXiv preprint arXiv:2206.09322. 2022.
[46] Jerry Luo, Cosmin Paduraru, Octavian Voicu, Yuri Chervonyi, Scott Munns, Jerry Li, Crystal Qian, Praneet Dutta, Jared Quincy Davis, Ningjia Wu, et al. Controlling commercial cooling systems using reinforcement learning. arXiv preprint arXiv:2211.07355 2022.
13

---

[47] California Independent System Operator. Calfornia renewable datasets. com/Paggss/default aspx 2023.
https: / /www caiso
[48] Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
[49] Ana Radovanović, Ross Koningstein, Ian Schneider, Bokan Chen, Alexandre Duarte, Binz Roy, Diyue Xiao, Maya Haridasan, Patrick Hung, Nick Care, et al. Carbon-aware computing for datacenters. IEEE Transactions on Power Systems, 3802):170--1280, 2022.
[50] Daniel Russo and Benjamin Van Roy. Learning optimize via posterior sampling. Mathematies of Operations Research, 39(4): 12:)):222211233 2014.
[51] Daan Rutten, Nico Christianson, Debankur Mukherjee, and Adam Wierman. Online optimiza- tion with untrusted predictions. arXiv preprint arXiv:2202.035T 2022.
[52] Roy Schwartz, Jesse Dodge, Noah A Smith, and Oren Etzioni. Green ai. Communications of the ACM, 63(12):54 63, 2020.
[53] Mohammad Shahrad, Cristian Klein, Liang Zheng, Mung Chiang. Erik Elmroth, and David Wentzlaff. Incentivizing self-capping to increase cloud utilization. In Proceedings of the 2017 Symposium on Cloud Computing, pages 52-65, 2017.
[54] Yuanyuan Shi, Guannan Qu, Steven Low, Anima Anandkumar, and Adam Wierman. Stability constrained reinforcement learning for real-time voltage control. In 2022 American Control Conference (ACC), pages 2715-2721. IEEE, 2022.
[55] Youngbin Song, Minjun Park. Minhwan Sco, and Sang Woo Kim. Improved soc estimation of lithium-ion batteries with novel soc-ocv curve estimation method using equivalent circuit model. In 20/9 4th International Conference on Smart and Sustainable Technologies (SpliTech), pages 1-6. IEEE, 2019.
[56] Aivar Sootla, Alexander Cowen-Rivers, Taher Jafferjee, Ziyan Wang, David H Mguni, Jun Wang, and Haitham Ammar. Sauté rl: Almost surely safe reinforcement learning using state augmentation. In International Conference on Machine Learning, pages 20423-20443, PMLR, 2022.
[57] Bo Sun, Ali Zeynali, Tongxin Li, Mohammad Hajiesmaili, Adam Wierman, and Danny HK Tsang. Competitive algorithms for the online multiple knapsack problem with application to electric vehicle charging. ACM Measurement and Analysis of Computing Systems (POMACS), 4(3), 2021.
[58] Guy Tennenholtz, Nadav Merlis, Lior Shani, Martin Mladenov, and Craig Boutilier. Reinforce- ment learning with history-dependent dynamic contexts. ICML, 2023.
[59] Garrett Thomas. Markov decision processes. 2007.
[60] Hiroyasu Tsukamoto, Soon-Jo Chung, and Jean-Jaques E Slotine. Contraction theory for nonlinear stability analysis and learning-based control: A tutorial overview. Annual Reviews in Control, 52:135-169, 2021.
[61] Sharan Vaswani, Lin Yang, and Csaba Szepesvári. Near-optimal sample complexity bounds for constrained mdps. Advances in Neural Information Processing Systems, 15:3110-3122, 2022.
[62] Honghao Wei, Xin Liu, and Lei Ying. Triple-q: A model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation. In International Conference Artificial Intelligence and Statistics, pages 3274-3307. PMLR, 2022.
[63] William Wong, Praneet Dutta, Octavian Voicu, Yuri Chervonyi, Cosmin Paduraru, and Jerry Luo. Optimizing industrial hvac systems with hierarchical reinforcement learning. arXiv preprint DrXiv:2209081122 2022.
14

---

[64] Carole-Jean Wu, Ramya Raghavendra, Udit Gupta, Bilge Acun, Newsha Ardalani, Kiwan Maeng, Gloria Chang, Fiona Aga, Jinshi Huang, Charles Bai, et al. Sustainable ai: Environmen- tal implications, challenges and opportunities. Proceedings of Machine Learning and Systems, 4:795-813. 2022.
[65] Yifan Wu, Roshan Shariff, Tor Lattimore, and Csaba Szepesvári. Conservative bandits. In International Conference Machine Learning, pages 1254-1262 PMLR, 2016.
[66] Yi Xiong, Ningyuan Chen, Xuefeng Gao, and Xiang Zhou. Sublinear regret for learning pomdps. Production and Operations Management, (19)33491-3304 2022.
[67] Tsung- Yen Yang. Justinian Rosca, Karthik Narasimhan, and Peter J. Ramadge. Projection-base constrained policy optimization. In International Conference on Learning Representations, 2020.
[68] Yunchang Yang. Tianhao Wu, Han Zhong, Evrard Garcelon, Matteo Pirotta, Alessandro Lazaric, Liwei Wang, and Simon Shaolei Du A reduction based framework for conservative bandits and reinforcement learning. In International Conference Learning Representations, 2022.
[69] Runyu Zhang, Yingying Li, and Na Li. On the regret analysis of online lqr control with predictions. In 2021 American Control Conference (ACC), pages 697-703 IEEE, 2021.
[70] Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning, pages 1799-11200.. PMLR, 2021.
[71] Xingyu Zhou, Ness Shroff, and Adam Wierman. Asymptotically optimal load balancing in large-scall scale heterogeneous systems with multiple dispatchers. ACM SIGMETRICS Performance Evaluation Review, 48(3):57-58, 2021.
[72] Xingyu Zhou, Jian Tan, and Ness Shroff. Flexible load balancing with multi-dimennional state-space collapse: Throughput and heavy-traffic delay optimality. ACM SIGMETRICS Performance Evaluation Review, 46(3):10-1) 11, 2019.
[73] Xinyang Zhou, Masoud Farivar, Zhiyuan Liu, Lijun Chen, and Steven H Low. Reverse and forward engineering of local voltage control in distribution networks. IEEE Transactions on Automatic Control, 66(3):1116-11 2020.
15


Reviews:
[{"review_id": "usAXILbKmD", "reviewer": "Reviewer_SitE", "summary": "This paper proposed a novel problem called Anytime-constrained Markov Decision Process. Unlike CMDP, at each step, a constraint should be satisfied. A projection-based algorithm is proposed to solve the Anytime-constrained MDP. The authors gave a perturbation-based regret analysis for the algorithm.", "questions": "1. From intuitions of the constrained optimization theory, the projection-based algorithm might not be guaranteed to be optimal with non-convex objectives/constraints. Would you mind giving me some intuitions about why the projection-based algorithm will result in an asymptotically optimal ACD policy? \n\n", "limitations": "The authors addressed the limitations well.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper has great novelty. The anytime constrained MDP is a new problem formulation and has good value for real-world safety-critical problems. The perturbation-based analysis is solid to me.", "weaknesses": "Although the problem formulation is novel, the analysis might be weak. The assumptions of known Lipschitz constant, a prior policy, might be too strict. Thus, the regret analysis might have limited guidance for the real-world problem. I have seen that the authors already mentioned it in the limitations.\n\nThe writing needs to be improved. Some words in the important part of the paper are confusing. For example, \n\n1. in Definition 3.3, the initialized and corresponding look quite confusing to me. Initial distribution usually refers to the states at step, or round, 0. The correspondence is also not clear. You might need to add more explanation to lines 153-159.\n\n2. in line 328, the linear kernel assumption is mentioned inline, which is critical to the major contribution of this paper. The assumptions should be highlighted and discussed more.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the comments of the reviewer and address them as below.\n\n`Are the assumptions too strict?`\\\nAs discussed in limitations, the any-time constraint is significantly stricter than the expected constraints or the constraints with high probability, so it cannot be guaranteed without further assumptions. The assumptions to guarantee the any-time constraint include the known cost lower bound, the Lipschitz cost and transition functions with known Lipschitz constants, and the existence of a policy prior with telescoping property.\n\nThe cost lower bound can be as small as zero, so this assumption is not strict. The Lipschitz cost functions are assumed in other MDPs [9]. The Lipschitz transition functions are common in sequential decision-making problems [3,4,10]. In mission-critical applications such as voltage control [6] and cooling control[7,8], the Lipschitz constants can be estimated based on prior knowledge. Additionally, the telescoping property holds for many policy priors, e.g. stable policies [5]. It is also proved for model predictive control [4], and it is assumed for other perturbation analysis [3].\n\n`Explanation of Definition 3.3 (Telescoping policy).`\\\nTelescoping policy means when a policy is applied, if the state $x_{h_1}$ at round $h_1$ is perturbed to state $x_{h_1}'$, then the state $x_{h_2}$ at round $h_2$ is perturbed to $x_{h_2}'$, and the perturbation error $\\|x_{h_2}-x_{h_2}'\\|$ is bounded by $p(h_2-h_1)\\|x_{h_1}-x_{h_1}'\\|$. \n\n`The linear kernel assumption.`\\\nThe pseudo regret bound in Theorem 5.2 is a general bound that does not rely on the linear kernel assumption, but the linear kernel assumption is needed to get a regret bound with sub-linear property.  The regret bound in (16) relies on the linear kernel assumption. The linear kernel assumption is widely considered in regret analysis of RL [1,2].  We will highlight this assumption required for (16) and discuss more about the limitations. \n\n`Why does the projection-based algorithm result in an asymptotically optimal ACD policy?`\\\nACRL learns the ML model $\\tilde{\\pi}$ in Algorithm 1 to optimize expected reward for the new MDP environment defined by Algorithm 1. The optimal ACD policy $\\pi^{\\circ}$ is ACD with the optimal ML model $\\tilde{\\pi}^*$. However, please note that the optimal ACD policy does not necessarily gives the optimal expected reward for the (non-convex) constrained optimization in (1). This is because the safe action set (7) used in ACD is sufficient to guarantee the constraint in (1), but is not a necessary condition. That being said, the reward gap between the optimal ACD policy and the optimal policy of A-CMDP is upper bounded by the reward gap in Theorem 5.1 where the optimal ACD policy is compared with a stronger oracle - the optimal unconstrained policy. The reward gap shows that with larger $\\lambda$ and $b$ (more relaxed constraint), the reward of the optimal ACD policy get closer to that of the optimal unconstrained policy.\n\n\n**References**\\\n[1] Ayoub, Alex, et al. \"Model-based reinforcement learning with value-targeted regression.\" ICML, 2020.\\\n[2] Zhou, Dongruo, Jiafan He, and Quanquan Gu. \"Provably efficient reinforcement learning for discounted mdps with feature mapping.\" ICML, 2021.\\\n[3] Lin, Yiheng, et al. \"Bounded-Regret MPC via Perturbation Analysis: Prediction Error, Constraints, and Nonlinearity.\" NeurIPS 2022.\\\n[4] Lin, Yiheng, et al. \"Perturbation-based regret analysis of predictive control in linear time varying systems.\" NeurIPS 2021.\\\n[5] Tsukamoto, Hiroyasu, Soon-Jo Chung, and Jean-Jaques E. Slotine. \"Contraction theory for nonlinear stability analysis and learning-based control: A tutorial overview.\" Annual Reviews in Control 52 (2021): 135-169.\\\n[6] Shi, Yuanyuan, et al. \"Stability constrained reinforcement learning for real-time voltage control.\" ACC 2022.\\\n[7] Google Deepmind, Safety-first ai for autonomous data centre cooling and industrial control.\\\n[8] Luo, Jerry, et al. \"Controlling commercial cooling systems using reinforcement learning.\" arXiv preprint arXiv:2211.07357 (2022).\\\n[9] Luo, Fan-Ming, et al. \"A survey on model-based reinforcement learning.\" arXiv preprint arXiv:2206.09328 (2022). \\\n[10] Gradu, Paula, John Hallman, and Elad Hazan. \"Non-stochastic control with bandit feedback.\" NeurIPS 2020.\n\n"}, {"review_id": "NyZIDcXBAx", "reviewer": "Reviewer_skPV", "summary": "The paper studies a novel problem of Anytime-Constrained Markov Decision Process (A-CMDP), where the goal is to optimize the expected reward while guaranteeing that the cumulative cost in each round of any episode does not exceed a relaxed version of the cost of a policy prior. The paper proposes a projection-based algorithm, called Anytime-Constrained Decision-making (ACD), which ensures the anytime cost constraints by projecting the output of a machine learning policy into safe action sets at each round. The paper also develops an efficient model-based reinforcement learning algorithm, called Anytime-Constrained Reinforcement Learning (ACRL), which learns the optimal ML policy for ACD via value iteration and model estimation. The paper provides theoretical analysis on the regret performance of ACRL, showing the trade-off between reward optimization and anytime constraint satisfaction, as well as the effectiveness of policy learning.", "questions": "\n- How does ACRL scale with large state-action spaces or long horizons? What would be the challenges there and how would the scale affect the convergence?\n- What are the computational challenges or bottlenecks in implementing ACRL?\n- How sensitive is ACRL to errors or uncertainties in estimating the Lipschitz constants, minimum cost value, or perturbation function?\n- In some applications there might be several constraints. How can ACRL be extended to handle multiple costs or multiple constraints?", "limitations": "The authors have adequately listed most limitations in their work, such as assuming Lipschitz continuity, telescoping property, and known parameters. Those are reasonable to some extent since as stated by the authors, there is no way to guarantee any time safety constraints without any knowledge of the properties of the dynamics. However, they could also discuss some possible extensions or future directions based on their limitations, such as relaxing some assumptions, incorporating online estimation, exploring more applications, or improving scalability.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\n- The paper addresses an important and novel problem of A-CMDP, which has direct motivations from many mission-critical applications that require strict cost constraints for safety and reliability.\n- The paper introduces a novel algorithm, ACD, which can guarantee the anytime constraints given any ML policy by projecting it into safe action sets. The paper also develops a model-based RL algorithm, ACRL, which can learn an optimal ML policy to be used in ACD. \n- The paper provides rigorous theoretical analysis on the regret performance of ACRL and shows how it depends on the relaxation parameters and the discrepancy between the policy prior and the optimal-unconstrained policy.\n- The paper presents empirical results on an application of resource management for carbon-aware computing, although all of this part is in appendix.", "weaknesses": "\n- The paper makes some strong assumptions on the Lipschitz continuity of the cost and transition functions, and the telescoping property of the policy prior, which may limit its applicability to more general environments. Specifically, the telescoping property of the policy prior is a strong assumption for both the policy and the dynamics. It would be interesting to explore how to relax these assumptions or how to estimate them online without compromising safety.\n- The paper also relies on the assumption that the safe policy prior can be queried on any state, even if the state is not explored on the policy prior trajectory. This assumption may not be feasible in real applications.\n- The paper does not provide much intuition or discussion on how the relaxation parameters or other parameters would affect the exploration-exploitation trade-off and the robustness of ACRL.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the comments of the reviewer and address them as below.\n\n`The reason that the safe policy prior can be queried on any state`\\\nThe safe policy prior is a mapping from a state to an action. In the ACD policy, policy prior is queried on true states to get a virtual action (which does not interact with the real world) to construct the safe action set. The queries bring some computation load but they are doable in the real world.\n\n`How do the relaxation parameters or other parameters affect the exploration-exploitation trade-off and the robustness of ACRL?`\\\nThe relaxation parameters $\\lambda$ and $b$ affects the trade-off between the reward maximization and the any-time constraint satisfaction as shown in Theorem 5.1. When $\\lambda$\u0000 or $b$ becomes larger,  the any-time constraints in (1) are relaxed to have more flexibility to optimize the average reward, so the regret comparing with the optimal unconstrained policy becomes smaller.\n\nThe relaxation parameters $\\lambda$ and $b$ also have effect on the exploration complexity. With smaller $\\lambda$ or $b$, the safe action set in (7) becomes smaller, which results in a smaller action-state space $\\mathcal{A}\\times \\mathcal{S}$ for the new MDP defined at the beginning of Section 4.2. By Theorem 5.2, the regret becomes smaller since the covering number and the Eluder dimension of set $\\mathcal{Q}$ is reduced with smaller action-state space.\n\nAnother important parameter that affect the exploration-exploitation trade-off is the confidence parameter $\\beta_k$ in (10). When $\\beta_k$ becomes larger, ACRL explores more, and vice versa. The regret is bounded in Theorem 5.2 with a proper choice of $\\beta_k$.\n\nWe will add these intuition and discussions in the future version.\n\n`How does ACRL scale with large state-action spaces or long horizons?`\\\nThe dependence of ACRL regret on the length of horizons $H$ is explicitly shown in (16).  Increasing the size of the state-action space can cause a larger covering number and Eluder dimension of the value function set $\\mathcal{Q}$, resulting in a larger regret. The challenges from large state-action space and long horizon also exist in many RL works ([1,2,3]). In this paper, we focus on the constraint guarantee and its impact on the regret, and leave the scalability issue on regret for future works.\n\n`What are the computational challenges or bottlenecks in implementing ACRL?`\\\nThe computational challenges of ACRL mainly comes from the scaling of state-action space and horizon length. For implementation, the scalability issue can be mitigated by feature aggregation [4].\n\nAlso, ACRL needs to query the policy prior and solve a projection into the safe action ball (7) at each round, which brings additional computational complexity. Some convex optimizers [5] can be queried to solve the projections\n\n`How sensitive is ACRL to errors or uncertainties in estimating the Lipschitz constants, minimum cost value, or perturbation function?`\\\nThe any-time constraints can be violated if the Lipschitz constants and perturbation parameters are lower estimated or the minimum cost value is higher estimated.  Thus, knowing the upper bounds of the Lipschitz constants and telescoping parameters and the lower bound of the minimum cost value is conservative enough to guarantee the constraints by our algorithm. However, our analysis shows that the reward regret bound is sensitive to the errors of the parameters. As is shown in Theorem 5.1, using larger Lipschitz constants or perturbation function or using smaller minimum cost value in ACD can cause larger reward gap between the optimal ACD policy and the optimal unconstrained policy, resulting in a larger bound of the regret in Eqn. (2). This is because smaller safe action sets are obtained under this case, causing less flexibility to optimize the reward.\n\n`How can ACRL be extended to handle multiple costs or multiple constraints?`\\\nIf we can find a policy prior that can achieve satisfactory performance for all the cost metrics, we can define the non-empty safe action set as the intersection of multiple safe action sets in (7) corresponding to different cost metrics. In this way, ACD can always give feasible actions. The extension is challenging if multiple policy priors are used for different cost metrics and they are not consistent in action selection. It would be interesting to explore the methods to handle this case. \n\n**References**\\\n[1] Ayoub, Alex, et al. \"Model-based reinforcement learning with value-targeted regression.\" ICML, 2020.\\\n[2] Zhou, Dongruo, Jiafan He, and Quanquan Gu. \"Provably efficient reinforcement learning for discounted mdps with feature mapping.\" ICML, 2021.\\\n[3] Yang, Zhuoran, et al. \"On function approximation in reinforcement learning: Optimism in the face of large state spaces.\" NeurIPS 2020.\\\n[4] Tennenholtz, Guy, et al. \"Reinforcement Learning with History-Dependent Dynamic Contexts.\" ICML 2023. \\\n[5] Agrawal, Akshay, et al. \"Differentiable convex optimization layers.\" NeurIPS 2019.\n"}, {"review_id": "PsNeOkTPGX", "reviewer": "Reviewer_MVJu", "summary": "Existing work on Constrained Markov Decision Processes (CMDPs) typically formulate a problem where the expected cumulative reward \nis maximized under a constraint where the expected cost over random dynamics is less than some threshold. Such existing work has a drawback that the safety constraint is violated in a specific episode. Hence, the authors study a problem named Anytime-CMDP (A-CMDP). The objective of the authors is to optimize the reward value function while guaranteeing the satisfaction of the safety constraint in each round of any episode. Under several assumptions (e.g., telescoping policy prior, Lipschitz continuity), the authors propose a new algorithm, called Anytime-Constrained Reinforcement Learning (ACRL) and provided theoretical results on constraint satisfaction and regret. The authors conduct experiments on the application of carbon-intelligent computing.", "questions": "[Q1] Is there any reason why standard safe RL benchmark problems (e.g., Safety Gym) were not used?\n\n[Q2] What is the minimal set of assumptions that are needed for guaranteeing safety?", "limitations": "Limitations have been adequately addressed.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Important problem settings. The drawbacks of the typical CMDPs have been discussed in recent years, so I think this paper will attract much attention within safe RL research community.\n\n- Good theoretical results. Though there are many assumptions, the obtained theoretical results are indeed good. Given the difficulty of the problem (and the theoretical results the authors try to provide), the number and strength of the assumptions are somewhat reasonable.", "weaknesses": "- There are several important missing citations and comparisons. Especially, Ref-1 is very relevant to this paper, which try to guarantee the satisfaction of the safety constraint with probability of 1. This paper is exactly the same motivation to Ref-1 though the approaches are quite different. Though I understand there are pros and cons as follows, it is extremely important to discuss the differences between Ref-1 and this paper. \n\n    ```\n    [Ref-1]\n        + High performance in complicated environments (e.g., Safety-Gym)\n        + High affinity with deep RL\n        + Assumptions are weak\n        - No theoretical guarantee\n    [This paper]\n        + Theoretical guarantee\n        - High affinity with deep RL\n        - Assumptions are strong\n    ```\n\n- Also, anytime constraints have been also studied in several literature. For example, [Ref-2] and [Ref-3] formulate their safety constraint as an instantaneous one $c(s_t, a_t) \\le d$ and propose algorithms to guarantee its satisfaction with high probability (though it is not probably of 1). It seems quite miss-leading that Table 1 show that ACRL is the first and only work to deal with any-time constraint.\n\n- Regarding experiments, the benchmark problem used in this paper is not popular and it would be better to evaluate their method in standard ones (e.g., Safety-Gym). Especially, if I understand correctly, the SOTA algorithm in the problem settings the authors address is Saute-RL in [Ref-1] and the I consider that there should be some comparison between ACRL and Saute-RL.\n\n- There are so many strong assumptions, which makes us to follow this paper. I guess it is partly because the authors try to derive regret bound as well as guarantee safety. I wonder what is the minimal set of assumptions for guaranteeing safety. It may be better to focus on guaranteeing safety with a small number of assumptions, which make this paper easy to follow and the contribution clearer.\n\n- References\n\n    - [Ref-1] Sootla, Aivar, et al. \"Sauté RL: Almost surely safe reinforcement learning using state augmentation.\" International Conference on Machine Learning. PMLR, 2022.\n\n    - [Ref-2] Wachi, Akifumi, and Yanan Sui. \"Safe reinforcement learning in constrained Markov decision processes.\" International Conference on Machine Learning. PMLR, 2020.\n\n    - [Ref-3] Amani, Sanae, Christos Thrampoulidis, and Lin Yang. \"Safe reinforcement learning with linear function approximation.\" International Conference on Machine Learning. PMLR, 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your comments and are happy to address them as below.\n\n`The differences between Ref-1 and this paper.` \\\nRef-1 solves the MDP with almost surely safety constraint by introducing Sauté MDP where constraints are incorporated into the reshaped objective. The approach is verified to have a high empirical performance, but there is no theoretical guarantee for constraint satisfaction, as is summarized by the reviewer. Comparably, we derive the sufficient conditions of the constraint satisfaction in Proposition 4.1 and Corollary 4.2, and propose a projection-based policy with theoretical guarantee for the any-time constraint satisfaction. The regret analysis shows the impact of the strict constraint satisfaction on reward optimization. We will discuss the differences in the future versions.\n\nWe'd like to highlight that the theoretical guarantee for the any-time constraints is essential for safety-critical applications with examples in Section 3.2.  In the application of cooling control in datacenters [6], for example, even one violation of the safety constraint can cause unaffordable loss.  The lack of theoretical constraint guarantee hinders the deployment of deep policies in real safety-critical systems. Thus we argue that although with some reasonable assumptions (explained in the next answer), the proposed RL algorithm with theoretically guaranteed any-time constraints is really needed.\n\n`Reasons for the assumptions.`\\\nThe minimal set of assumptions to guarantee safety are listed in Assumption 3.2 and 3.4 which include the known cost lower bound, the Lipschitz cost and transition functions with known Lipschitz constants, and the existence of a policy prior satisfying telescoping property.  The cost lower bound can be as small as zero. The non-negative cost is also assumed in [Ref-1].  The Lipschitz cost functions are assumed in other MDPs [8]. The Lipschitz transition functions are common in sequential decision-making problems [3,4,9].  In mission-critical applications such as voltage control [1] and cooling control[2], the Lipschitz constants can be estimated based on prior knowledge. Additionally, the telescoping property holds for many policy priors, e.g. stable policies [5].  It is also proved for model predictive control [4], and it is assumed for perturbation analysis in [3]. \n\nTo the best of our knowledge, our work presents the first RL algorithm to guarantee the any-time constraint under these assumptions which are reasonable for many mission-critical applications. However, for the future work, it is definitely interesting to study RL that guarantee the constraints under relaxed assumptions to be applied to general scenarios.\n\n`Why not evaluate on standard benchmarks?`\\\nThe settings and assumptions of ACMDP are motivated from the sequential decision-making problems in mission-critical applications such as datacenters [7], cooling systems [2,6], power systems[1], In these systems, there exist some safe policy priors that have been programmed in the real systems for a long time and/or have verified cost performance. Also, the key system (environment) properties (in Assumption 3.2 and 3.4) are known to the agent. The considered application of carbon-aware computing in datacenters is one of such applications, so we evaluate our method ACRL in this application. \n\nThe standard benchmarks generally do not meet these assumptions. The method in SOTA algorithms like Ref-1 applies to the environments with safety budget constraints where the agent has less knowledge about the environment. Since the considered constraints are different, it is not fair to compare our paper with these algorithms.\n\n`The any-time constraint in Table 1.` \\\nThe \"any-time constraint\" specifically refers to the any-time cost constraint against a policy prior in Eqn. (1) which is studied by us for the first time. We will change the phrase in Table 1 into any-time constraint against a policy prior to avoid misunderstanding. \n\n\n**References**\\\n[1] Shi, Yuanyuan, et al. \"Stability constrained reinforcement learning for real-time voltage control.\" ACC 2022.\\\n[2] Luo, Jerry, et al. \"Controlling commercial cooling systems using reinforcement learning.\" arXiv preprint arXiv:2211.07357 (2022).\\\n[3] Lin, Yiheng, et al. \"Bounded-Regret MPC via Perturbation Analysis: Prediction Error, Constraints, and Nonlinearity.\" NeurIPS 2022.\\\n[4] Lin, Yiheng, et al. \"Perturbation-based regret analysis of predictive control in linear time varying systems.\" NeurIPS 2021.\\\n[5] Tsukamoto, Hiroyasu, Soon-Jo Chung, and Jean-Jaques E. Slotine. \"Contraction theory for nonlinear stability analysis and learning-based control: A tutorial overview.\" Annual Reviews in Control 52 (2021): 135-169.\\\n[6] Google Deepmind, Safety-first ai for autonomous data centre cooling and industrial control. \\\n[7] Radovanović, Ana, et al. \"Carbon-aware computing for datacenters.\" IEEE Transactions on Power Systems 38.2 (2022): 1270-1280.\\\n[8] Luo, Fan-Ming, et al. \"A survey on model-based reinforcement learning.\" arXiv preprint arXiv:2206.09328 (2022).\\\n[9] Gradu, Paula, John Hallman, and Elad Hazan. \"Non-stochastic control with bandit feedback.\" NeurIPS 2020.\n\n\n"}, {"review_id": "LePRFe3zmi", "reviewer": "Reviewer_LDWt", "summary": "This paper addresses the problem of anytime constrained RL. Contrary to traditional constrained RL where the constraints are expressed as expected costs, this work looks at a stronger criteria that the cost should be bounded for any episode. The cost is defined relative to the performance of an existing safe policy deployed in the environment of interest.\n\nAn algorithm (ACD) is derived which consists in deriving a safe action set by computing the maximum allowed deviation from the prior policy. The computation relies on the knowledge of Lipschitz constants characterizing the transition model, the cost variation, and the policy prior. This algorithm allows to take safe actions but does not address optimizing the return. \n\nACD is extended to ACRL which adds the learning and optimization parts to maximize the return while taking safe actions. ACRL is a model based algorithm. An analysis of the regret of the algorithm is provided to analyze the regret from the anytime constraint and from the learning part.\n", "questions": "- I am not sure I understand why the notion of model (y) is needed in the definition the A-CMDP, as opposed to the notion of trajectories more common in the RL literature?\n\n- Why is the value definition an expectation over the first state $x_1$? Shouldn’t it be an expectation over trajectories like in regular MDPs?\n\n- How does one find the necessary Lipschitz constants in a problem where the dynamics is unknown? Is it important to have accurate values?\n\n- In proposition 4.1, how can the cost of the policy prior be known if it is not executed? \n", "limitations": "The authors are explicitly mentioning the limitations at the end of the paper. However, I find the discussion somewhat contradicting. One of the main related works rely on knowledge of the dynamics and this work relies on knowledge of the Lipschitz constants and some information about the policy prior. Is it really much simpler to get this information compared to an approximate dynamics model?", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The introduced framework of A-CMDP is very sound and fits many practical applications. The main assumption of the work that there exist a policy prior is a strong one but I believe it applies to a lot of problems and is quite relevant. The associated definition of regret makes sense, although the formalism of the A-CMDP is sometimes unclear.\n\nThe article is fairly well written. All propositions and assumptions are followed by an intuitive explanation and they all seem sound. \n\nThe discussion of the related work and their relation to what is being presented is clear and seems to cover most of the relevant topics.\n\nThe structure of deriving first ACD and ACRL is useful to follow the work and the algorithms make sense given the proposed assumptions.\n", "weaknesses": "The authors did not include the experiments in the main body of the paper. The experiments show that the algorithm is better in terms of worst case cost, but does not provide the best regret per episode (expected since stronger constraints). The algorithm is evaluated on only one problem, it would have been useful to test it on at least one other problem to show its value, maybe some classical benchmark from the safe RL literature. An ablation study of showing the performance of the model-based approach without the constraints would have been useful as well. Adding the experiments to the main body seems necessary to me.\n\nAlthough the intuitive explanation of the A-CMDP is clear, there are some unclarities in the mathematical definition of the A-CMDP (see questions).\n\nThe main assumptions of the article require the cost functions, transition functions, and prior policy to have some sort of Lipschitz continuity property with known constants. At the same time, a main advantage of the proposed algorithm is that it does not require to know much of the dynamics, it seems a bit contradictory. The author provide some arguments with support from related work but I am still curious whether a precise knowledge of this constant is important or not.\n\nIn ACRL, the state augmentation part increasing significantly the size of state by adding a dependency on the history. This approach raises scalability issues which are not discussed in the paper. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your comments and are happy to address them as below.\n\n`Experiments.`\\\nThank you for your suggestions, we will move some important experiment results to the main body of the paper.\n\nSince the motivation is from mission-critical applications, we will add another experiment on real-time voltage control [1] where the Lyapunov-based policy is used as the policy prior.\n\n`Notion y in the definition the A-CMDP?`\\\nA sampled sequence of models can be seen as a part of a sampled trajectory. We will change expression as $\\sum_{i=1}^hc_i(x_i,a_i)\\leq (1+\\lambda) \\sum_{i=1}^hc_i(x_i^{\\dagger},a_i^{\\dagger})+hb$ to avoid any misunderstanding and be more consistent with the RL literature.\n\n`Value definition in the objective (1)`\\\nThe value function $V(x_h)=\\mathbb{E}[\\sum_{i=h}^Hc_i(x_i,a_i)\\mid x_h]$ is an expectation of reward over the trajectories conditioned on a state $x_h$. We add an expectation $E_{x_1}$ over the initial state $x_1$ on $V(x_1)$ in (1) to represent the expected reward over the whole trajectory.\n\n`Is the knowledge about Lipschitz continuity and telescoping property important? How to get the knowledge of Lipschitz constants and telescoping parameters? Is it easier than approximating a dynamic model?`\\\nWe consider any-time constraints which are required to be satisfied for any round in any episode.  Different from standard constrained MDPs where constrained are satisfied in expectation or with high probability, the any-time constraints cannot be guaranteed without further knowledge on the environment. In this work, we find that the any-time constraints can be theoretically guaranteed with the knowledge of Lipschitz constants and telescoping parameters because they indicate how sensitive the system is given a small perturbation of states or actions.  Given this intuition, knowing the upper bounds of the Lipschitz constants and telescoping parameters is enough to guarantee the constraints by our algorithm. In spite of this,  Theorem 5.1 shows that using larger Lipschitz constants or perturbation function in ACD can cause larger reward gap between the optimal ACD policy and the optimal unconstrained policy, resulting in a larger bound of the reward regret. This is because smaller safe action sets are obtained under this case, causing less flexibility to optimize the reward. \n\nKnowing the Lipschitz constants and telescoping parameters are far from approximating a dynamic model. There exists a set of transition functions that satisfy the Lipschitz assumption and the telescoping property given fixed Lipschitz constants and telescoping parameters. Thus, assuming the knowledge does not contradict with the role of RL in learning dynamic models.\n\nFor mission-critical applications [1,5,6], it is much easier to get the needed information based on some prior knowledge. The Lipschitz constants of cost and transition functions can be estimated based on the model information. For telescoping parameters, we can first estimate the Lipschitz constant of the policy prior as $L_{\\pi^{\\dagger}}$ given that we have full access to the policy prior. Then the telescoping function can be simply calculated as $p(h_2-h_1)=(L_f(1+L_{\\pi^{\\dagger}}))^{h_2-h_1}$ where $L_f$ is the Lipschitz constant of the transition function. For some specific priors and dynamics (e.g. priors in nonlinear stability analysis [7]), tighter telescoping functions can be calculated.\n\n`In proposition 4.1, how can the cost of the policy prior be known if it is not executed?`\\\nIn proposition 4.1, the cost of the policy prior $c^{\\dagger}$ is never needed. Instead, we derive a lower bound of the cost of the policy prior, i.e.  $\\hat{c}^{\\dagger}$ based on the known parameters to evaluate inequality (4).\\\n\n\n`The scalability issue in ACRL`\\\nThe augmented state in Line 254-258 includes the history costs and action differences which are needed to calculate the safe action set for each round. The dimension of the augmented state increases with the length of the horizon $H$, resulting a scalability issue. The salability issue also exits in other RL works [2,3].  in this paper, we focus on the constraint guarantee and its impact on the regret, but in practice, tractable methods can be designed through feature aggregation [2] or PODMP [4].\n\n\n\n**References**\\\n[1] Shi, Y., Qu, G., Low, S., Anandkumar, A. and Wierman, A., 2022, June. Stability constrained reinforcement learning for real-time voltage control. In 2022 American Control Conference (ACC) (pp. 2715-2721). IEEE.\\\n[2] Tennenholtz, Guy, et al. \"Reinforcement Learning with History-Dependent Dynamic Contexts.\" ICML 2023.\\\n[3] Chen, Xiaoyu, et al. \"An adaptive deep rl method for non-stationary environments with piecewise stable context.\" NeurIPS 2022.\\\n[4] Xiong, Yi, et al. \"Sublinear regret for learning pomdps.\" Production and Operations Management 31.9 (2022): 3491-3504.\\\n[5] Luo, Jerry, et al. \"Controlling commercial cooling systems using reinforcement learning.\" arXiv preprint arXiv:2211.07357 (2022).\\\n[6] Radovanović, Ana, et al. \"Carbon-aware computing for datacenters.\" IEEE Transactions on Power Systems 38.2 (2022): 1270-1280.\\\n[7] Tsukamoto, Hiroyasu, Soon-Jo Chung, and Jean-Jaques E. Slotine. \"Contraction theory for nonlinear stability analysis and learning-based control: A tutorial overview.\" Annual Reviews in Control 52 (2021): 135-169."}]

Author rebuttal:

Meta-review: The paper introduces a stronger notion of constrained MDPs, where the cost constraint is imposed not in expectation but for any realization of the randomness. While the paper is borderline, overall the setting is well motivated and the theoretical/algorithmic contribution is interesting. For this reason I propose acceptance.

Nonetheless, I would like to encourage the authors to revise the paper by addressing the reviewers concerns and by integrating the rebuttal. In particular, I suggest to revise the following aspets:
- The assumptions seem overall reasonable. Nonetheless they seem quite strong and the lack of discussion on where they are used, and, if not a full lower bound, it would be useful to have a stronger conjecture on whether they are needed or how they could be relaxed.
- Expand the discussion on related work, in particular following the suggestions of Rev. MVJu.
- I would also encourage the authors to consider changing the title of the paper. "Anytime" is somehow overloaded wrt to the way it is used in bandit/online learning literature.
Decision: Accept (poster)