Semi-infinitely Constrained Markov Decision Processes
Authors: Liangyu Zhang
Yang Peng
Wenhao Yang
Zhihua Zhang
Venue: NeurIPS 2022 Accept (2022)

Abstract: We propose a generalization of constrained Markov decision processes (CMDPs) that we call the \emph{semi-infinitely constrained Markov decision process} (SICMDP).
Particularly, in a SICMDP model, we impose a continuum of constraints instead of a finite number of constraints as in the case of ordinary CMDPs.
We also devise a reinforcement learning algorithm for SICMDPs that we call SI-CRL.
We first transform the reinforcement learning problem into a linear semi-infinitely programming (LSIP) problem and then use the dual exchange method in the LSIP literature to solve it.
To the best of our knowledge, we are the first to apply tools from semi-infinitely programming (SIP) to solve reinforcement learning problems.
We present theoretical analysis for SI-CRL, identifying its sample complexity and iteration complexity.
We also conduct extensive numerical examples to illustrate the SICMDP model and validate the SI-CRL algorithm.

Semi-Infinitely Constrained Markov Decision Processes
Liangyu Zhang Academy of Advanced Interdisciplinary Studies Peking University zhangliangyuêpku. edu. cn
Yang Peng School of Mathematical Sciences
Peking University pengyang@pku, edu. cn
Wenhao Yang Academy of Advanced Interdisciplinary Studies Peking University yangreenhaosms@pku. edu. cn
Zhihua Zhang
School Mathematical Sciences Peking University zhzhang@math. pku, edu, cn
Abstract
We propose generalization of constrained Markov decision processes (CMDPs) that we call the semi-infinitely constrained Markov decision process (SICMDP). Particularly, consider continuum of constraints instead of finite number of constraints as in the case of ordinary CMDPs. We also devise a reinforcement learning algorithm for SICMDPs that call SI-CRL. We first transform the reinforcement learning problem into linear semi-infinitely programming (LSIP) problem and then use the dual exchange method in the LSIP literature to solve it. To the best of our knowledge, we are the first to apply tools from semi-infiniteh, programming (SIP) to solve constrained reinforcement learning problems. We present theoretical analysis for SI-CRL, identifying its sample complexity and iteration complexity. We also conduct extensive numerical examples illustrate the SICMDP model and validate the SI-CRL algorithm.
Introduction
Reinforcement learning has achieved great success areas such as Game-playing 34 39], robotics 24 recommender systems [44), etc. However, due to safety concerns or physical limitations, in some real-world reinforcement learning problems, we must consider additional constraints that may influence the optimal policy and the learning process [15]. A standard framework handle such cases is the constrained Markov Decision Process (CMDP) (5). Within the CMDP framework, the agent has maximize the expected cumulative reward while obeying finite number of constraints, which are usually in the form of expected cumulative cost criteria.
However, we are sometimes concerned with the problem with a continuum of constraints. For example, the constraints we meet might be time-evolving or subject to uncertain parameters, which cannot be formulated as ordinary CMDP (see Examples and and 3.2). In this paper we would study generalized CMDP to address the above problem. Because the constraints are not only nnfibrte-number but also lie in continuous set, the generalization not trivial. Fortunately,
find that we can borrow the idea behind linear semi-infinite programming (LSIP) [33] [16 to deal with the semi-infinite constraints. Accordingly, propose semi-infinitely constrained Markov decision processes (SICMDPs) as a novel complement to the ordinary CMDP framework.
We also present so-called SI-CRL reinforcement learning algorithm to solve SICMDPs. The main challenge is that we need to deal with continuum of constraints, thus reinforcement learning algorithms for ordinary CMDPs do not work anymore. We tackle this difficulty by first transforming
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the reinforcement learning problem to an equivalent LSIP problem, which can then be solved using As far as we know, we are the first to introduce tools from semi-infinitely programming (SIP) into the reinforcement learning community for solving constrained reinforcement learning problems.
the dual exchange methods the LSIP literature 233 B2
Furthermore, we give theoretical analysis for SI-CRL. We decompose the error of SI-CRL into two parts: the statistical error from approximating the true SICMDP with an offline dataset and the optimization error due to the fact that the solution of the LSIP problem obtained by the dual exchange method is inexact. On the statistical side, we show that the sample complexity of SI-CRL is Ô
IAA if the offline dataset is generated by a generative model, and Ô SI
Umin (II-)) if
the dataset is generated by a probability measure V as considered in [T]. Here means that all logarithm terms are discarded. On the optimization side, show that the iteration complexity of d'
SI-CRL is of 4
We perform a set of numerical experiments illustrate the SICMDP model and validate the SI-CRL algorithm. We consider two numerical examples: toy SICMDP and discharge of sewage. In the example of toy SICMDP, we show the efficiency of the SI-CRL algorithm and validate the established theoretical bounds. In the example of discharge of sewage, we further show the advantage of the SICMDP framework over the CMDP baseline obtained by naive discretization in modeling realistic decision-making problems.
2
Related Work
The constrained Markov decision processes (CMDPs) have been extensively applied in areas like robotics [31] communication and networks, [27 35] and finance []] For a detailed treatment of CMDPs one may refer [5). A number of reinforcement learning algorithms for CMDPs are proposed, which include Lagrangian methods (4) actor-critic methods (2] 37), policy gradient theoretical aspects of CMDPs. Wu al. [1I. Amani et al. [6] studied the online regret bound of the bandit case. Wachi and Sui [40], Zheng and Ratlif [45) considered the case where the reward and cost are random but the transition dynamics are known. And Efroni et al. [14, Amani et al. [7]. HasanzadeZonuzy et al. [21] considered the case where the transition dynamics are unknown and need be estimated. Our SI-CRL algorithm uses similar strategy as in 14) in the sense that they all use the optimistic method to transform the reinforcement learning problem into a linear nemi-infinitely) programming problem, which resolves the feasibility issue and makes the theoretical analysis easier as well. However, our work and [14] are very different at the technical level: 1) Our theoretical guarantees are the form of sample complexity bounds, while the results in (Efroni et. al 2020) are in the form of online regret bounds; the proof techniques are quite different. 2) Efroni et al. 14 considered the episodic MDPs, while we consider the infinite-horizon case.
methods (42] etc. There are also works focusing
The origination of semi-infinitely programming (SIP) can date back 33 From then on, SIP has been widely used in quantum physics [10], signal processing 29 30 finance [3], environment
science, and engineering 22 One important class of SIP problems called linear semi-infinitely programming (LSIP). Goberna and López [17] provided a thorough survey about LSIP theory. Various numerical methods are proposed to solve LSIP problems, including discretization methods (9 (3). exchange methods 23 43), and local reduction methods (20 12). Unlike IP, most LSIP problems cannot be solved exactly and all-purpose LSIP solvers do not exist. In SI-CRL,, we choose to use the dual exchange method in ( to solve the LSIP problem therein for its conceptual simplicity as well as concrete theoretical guarantees.
3 The SICMDP Model
A semi-ing semi-infiniti infinitely constrained MDP (SICMDP) is defined by tuple M = Here S, A, P. r, 14, 7 are defined in similar manner as common infinite-horizon discounted MDPs. Specifically,, S and A are the finite sets of states and actions, respectively. P is the transition dynamics and ((s (, a) represents the probability of transitioning to state s' when playing action a at state 8. And r: S A + [0, 1] is the reward function, j is the fixed initial distribution, and is the discount

---

factor. Y is the set of constrains, which we define as compact set in RR, and diam < oc denotes its diameter. In addition, c: Y S A + [0, is used to denote continuum of cost functions and the value for constraints (bounds that must be satisfied) is determined by function u: Y -> IR. Note that when is finite, we get an ordinary constrained MDP, which indeed a special case of SICMDP.
The general SICMDP problem is to find stationary policy æ: S A(A), where A is the set of probability measure supported on A, to maximize the value function while complying with a continuum constraints. other words, we consider the following optimization problem:
max (p) s.t. C. (p) S ug Vy E Y,
(M)
( where VT(p) := E(E r'r(s,, a0) μe) and C7 (M) == 2' as) ~ p).
Let us concrete examples of SICMDPs. Example 3.1 (Spatial-temporal Constraints). Consider an ordinary CMDP problem with a single constraint:
max (+( s.t. (²())= S u.
(I)
In some cases the constraint would be spatial-temporal, i.e., the cost function c(s, a) and the value
for constraints u are no longer constant function and would change with time T E [0 or location d E D c RS, Then we should use the SICMDP model with Y [0, T] or Y D rather than the ordinary CMDP framework to model such problems:
maxx
V (J)
s.t. (u) S ur, VT [0, TJ.
(2)
Load Balancing: Suppose RL agent needs to balance the load between multiple cell sites using some policy æ. The objective is to minimize the cost (=(u) and the constraint is that at every place in the region D the cumulative communication capacity CJ (u) is above some threshold ua.
Example 3.2 (Constraints with Uncertainty). Again we consider a problem like Problem IT. In many application scenarios the cost function c(s, a) is handcrafted and the construction of c(s. a) not guaranteed to be correct. Hence it may be helpful to include an additional parameter e e E representing our uncertainty in the construction of the cost function c(s, a) as well as the value of constraints u. Even if the constraint is not handcrafted and has clear physical meaning, may still subject to uncertain parameters c E that cannot be observed in advance. Therefore, we should use the SICMDP model with Y E rather than the ordinary CMDP framework to model such problems:
max
(p) s.t. C (p) S Me, Ve E E.
Suppose an underwater drone needs to maximize V accomplish some tasks. When the unknown environment feature (salimity, temperature, ocean current, etc.) is e E, for acteenaction pair (s, a) the energy consumption (s a), and the constraint that total energy consumption C (()) cannot be larger than its battery capacity ue.
Underwater Drone:
Remark 3.3. An alternative approach solving problems such as Examples 3.1 and 3.2 is naively discretize the constraint set Y, and then the discretized problem can be fit into the conventional CMDP framework. The problem of this naive method is that the prior knowledge, i.e., the constraint function is continuous w.r.t. would be lost, which makes the method extremely inefficient. In Section 6.2 we demonstrate this issue via a numerical example.
When an SICMDP M is known to we may do the planning by solving linear semi-infinite programming (LSIP) problem. Denote the occupancy measure on S introduced by policy π as 4n E ASS x A). Then we have
(s(
(s. = (1 >)
Σ
PP s,a, s.a, a), <(als) Eo'es (1,,aa)
Problem M can be reformulated as the following LSIP problem:
max q
1
s.t.
Cy 5 uw Vy Y,
(4)
Eg(s',
a(s'. (1,))(1(0)))) PPss'' (ssss//a,)) 4)) = (1-7)u(s), E
2.0
9 920 0.
3

---

Therefore, when M is already known the optimal policy n can be found by solving Problem (4) And we always assume such policy π exists.
Assumption 3.4. Problem (M) feasible with an optimal solution n,, or equivalently, Problem feasible with an optimal solution q"
4 The SI-CRL Algorithm
In this section we present an offline reinforcement learning algorithm called SI-CRL for SICMDPs. In a high-level point of view, our algorithm is a semi-infinite version of the algorithms proposed in 21 In the first stage, SI-CRL takes an offline dataset {(si, ag s = 1, 2.... . as input and generate an empirical estimate P of the true transition dynamic P. Then the algorithm constructs a confidence set (the optimistic set) according to P that would cover the true SICMDP with high probability. Then for each policy we would only view its return as the largest possible return in SICMDPs in the confidence set. This method is also called the optimistic approach. In the second stage, the optimistic policy मे is found using a LSIP algorithm. can be shown that the resulting policy स is guaranteed to be nearly optimal, and the theoretical analysis can be found in Section
Now we give a more detailed description of SI-CRL. First, the empirical estimate P is calculated as: m(s.a,s') (()'(s, max(1.n(s.aa))' where n(s, a,
Σ 1( 8, a, a, s') and n(s, a) E,, s'). The reason why we do not directly plug P into Problem 44) and solve the resulting LSIP problem is due to the fact that there is no guarantee that the LSIP problem w.r.t. P is feasible. To address this issue, we construct an optimistic set Ms such that with high probability the true SICMDP M lies in Ms. In particular, Ms is defined via the empirical Bernstein's 's bound and the Hoeffding's 's bound (26]:
n.C.U.u M3 U.S.A.Y,PPP............ (P - P(s'ls, a)l s do(s, s'), Vs, E ES, E A}.
where
{1
2
log 4log(4/0) n(s,a, 8') V
log(2/0)
= =mimm]
n(s,, a, 8*)
2n(s, a,))
The next step is to solve the optimistic planning problem:
VR. (M)) s.t. C...M (n) S ug EY,
max M M
(5)
where the superscript M' denotes that the expectation is taken w.r.t. SICMDP M'.
Theorem 4.1. Suppose 3. With probability at least 1 2|S| Alō, we have that M Ms. and
Problem (5) is feasible.
The proof is given in the appendix. Note that the optimization variables include both M' and m and LSIP reformulations like Problem (4p would no longer be possible. Instead, shall intro- duce the state-action-state occupancy measure 2(8, a, s'). In particular, assuming (8, (8) ".,(0,,))") P(s Is, (s, a), we have P(s'|s, a) Eges (5, and Tals)) = Edes =p Problem (5) can be reformulated as the following extended LSIP problem:
Evess,'ea (
max Σ 2(s a)),a))))
6,0,e
Σ
2(s,0, Vy
6.a."'
da(s,, Σ 2(s,a, aE 2(,,0,5)) 2 (P(5lss,)) (s as(s,,,s')
2(8,0,8) & +((.)))).))))()...))))))))))
(6)
Vs, aEA,
#ES
Σ z(a.b,z) (1 - >))(()) +y
RESAEA
ZEBAEA
2 2z 0.

---

However, compared to LP problems, LSIP problems are typically harder to solve and there are no all-purpose LSIP solvers. Here, we choose the simple yet effective dual exchange methods 23 to solve Problem 6
The SI-CRI. algorithm can be summarized in Algorithm
Algorithm 1 SI-CRL
state space S, action space A, dataset {(s,, ai, si]li 1, 1, m.., m), reward function r, continuum of cost function c, value for constraints discount factor for each (s, s²) tuple do
Input:
Set (() := Σ 1(
max 1. ((==s,=aa))
end for
Initialize Yo {
for 1 T do
Use LP solver to solve a finite version of Problem 6 by only considering constraints in Yo
and store the solution as 24
Find yi = argmaxyey Ex ziss, a, (s)c) uy
if Es..s' 2(8, a, "a,,a,s")cc, C') (8, Uy, S 0 then
Set 2T 24
BREAK
end if Add y: to Yo
end for
for each (s, a) pair do
Set (als) Dve (5,
end for RETURN *
Theoretical Analysis
We give PAC-type bounds for SI-CRL under two different settings. The error of SI-CRL is decom- posed into two parts: the statistical error from approximating Problem (M) with Problem (5) and the optimization error from the fact that the solution of (5) obtained by dual exchange method is inexact. On the statistical side, our goal is to determine that how many samples are required to make SI-CRL an (c. opttima when Problem (5) can be solved exactly, i.e., we want find the sample
complexity of SI-CRL. We show that the sample complexity of SI-CRL Ō
LAP if the dataset ((1-9)3))
we use is generated by a generative model, and Ô
[811A]
if the dataset we use is generated
Pinin e (1 (1-333
by probability measure v defined on the space S x A and P(-|s, a) as considered in 11 Here Ô means that all logarithm terms are discarded, and Miin = mine(s.a)200 (ss J. can be noted that the order of our sample complexity bound increases by factor of ||S|||| compared to that of ordinary discounted MDP [8] On the optimization side, we show that if the inner maximization problem w.r.t. y can be solved exactly, the dual exchange method would produce an e-optimal solutions when
the number of iterations T
O [diam(Y) | Ald/e where L is the Lipschitz constant
defined in Assumption 5.3 We will present our theoretical analysis in more details in the following part of this section.
5.1 Notation and Preliminaries
Given a stationary policy we define the value function (*(s)) = B (s), so = s). V (V (s1), V (T T RIS Thus we have V (μ) TT VT. Similarly, we define the
expected cost CJ (s) E 2 a:)lsp s), C (C (3) (si).... Cj s))) e gls), thus
'The (e, -pptimmlllyy would be defined Definition
"The c-optimal solutions is defined in Definition 5.2
5

---

(3) μ C.. And x² denotes the optimal policy, Suppose म, M are the solution of Problem (S, A.Y, r. c, u, 1, For given stationary policy æ, we use (s), V=, V (1), (s), C. (J). (=(s,a) a). to represent the value function, expected cost, occupancy measure of SICMDP M, respectively. We say an offline dataset {(8s, (s K(]li 1,2...., m) to be generated by generative model if we sample according to P(-|s,a) for each (s,a)-pair m//S||Ai times and record the results in the dataset. We say an offline dataset to be generated by probability measure and P(-|s,0) a) if (s) Lid. and s/ ~ a())
and M = (S,A,Y
An (e, ooptimal policy is defined as follows.
Definition 5.1. An RL algorithm is called (c, -optimall for e, > 0 if with probability at least it can return policy such that
v (m) (A) e; (3(() - uy S Vy E.
An e-optimal solution of Problem
5 is defined
Definition 5.2. A stationary policy स is called an e-optimal solution of Problem (5) for >> 0 if
(v² V (w) se 10g (u) uy e VyY
hold simultaneously.
Unless otherwise specified, we assume that V(s, a) E S x A, (s, a) is L-Lipschitz in y w.r.t. l1-112- We also assume that My is L-Lipschitz in w.r.t 11-112- The assumptions can be formally stated as:
Assumption 5.3. (s, a) and My are Lipschitz in w.r.t |1-11, i... EL > 0 s.t. Vy, y E Y, (8,
S A. (s, a) cy (s. a)l S Lly s v'll2.11 Juy uvl S L 1 y/ 22.
The Lipschitz assumption is usually necessary when dealing with a semi-infinitely constrained problem 36 23 And this assumption indeed quite mild because Y is compact set.
5.2 Sample Complexity of SI-CRL
We consider the case where the offline dataset we use is generated by generative model. First consider a restricted setting as in [26] where for each (s, a) -ppar in the true SICMDP there are at most two possible next-states and provide the sample complexity bound. Then will drop Assumption 5.4 Juiiing the same strategy as (26) and derive the sample complexity bound of the general case.
The proof can be found in the appendix.
Assumption 5.4. The true unknown SICMDP M satisfies P(s'|s, a) 0 for all but two s' E S denoted as sat and sa E S.
Theorem 5.5. Suppose Assumption model with m/ S|||| > max have that
5.4 holds, and the dataset we use is generated by a generative
36 log 4/8
4log 4/8
}. Then with probability A
(1
11-7))+
(1-7)5
log 4/6 4/6
log 4/5 n(1 - 7)3 Vy E EY
V V=)()) (w)-Va (*( S 24
(f(() uy 12
n(1 - 7/33
Theorem 5.6. Suppose Assumption 5.4 holds, the dataset we use is generated by generative
model and Problem can be solved exactly. Then when m = [SS]A]] c²ll-)) (e, -)potimal
(5914/10((91))1111))) SI-CRL
Theorem 5.7. Suppose the dataset is generated by a generative model and Problem 5 can be solved exactly. Then when m = (A) (log (S)) log S15) (AP/)) a modification of SI-CRL is (c. -optimal.
c
Remark 5.8. Our proof strategy is similar to (26. However, to get Õ(1 (1)-))33) bound 26 tedious recursion argument. We greatly simplify the proof and achieve improvements in log terms
(by a factor of (log( ( )) using sharper bounds on local variances of MDPs developed in 3
(og(<(11,))

---

Remark 5.9. Although Assumption 5.4 seems quite restrictive, we argue that it is necessary to establish sharp sample complexity bound, shown in [26.. Specifically, without this assumption the "quasi-Bernstein bound" (Lemma B.4) will not hold, thus we may not be able to get the Õ((1 - bound.
Remark 5.10. It can be noted that our sample complexity bound does not rely on the constraint set Y. This is because we consider the setting where r and Cy are known deterministic functions and the only source of randomness comes from estimating the unknown transition dynamic using an offline dataset.
Now generalize results to the case where the offline dataset is generated by probability measure. The proof can be found in the appendix.
Theorem 5.11. Suppose the dataset we use is generated by probability measure v and Problem can be solved exactly. Then when m =0 [S] Al(log (81)* log (81S)1111 (1/1/1))))))) modification of SI-CRL
Pmine 7))
(c, -optimall...
Remark 5.12. Here "a modification of SI-CRL" stands for the following procedure: first we transform the original SICMDP to new SICMDP satisfying Assumption [.4] then we run SI-CRL to solve the new SICMDP. One may refer the proof in Appendix BB more details.
5.3 Iteration Complexity of SI-CRL
We give the iteration complexity of SI-CRL, i.e., how many iterations are required to output an e-optimal solution of Problem (5) when the inner-loop problem can be solved exactly. Our results is
corollary of Theorem in [2
Theorem 5.13. If the inner-loop maxinization problem in SI-CRL can be exactly solved, then SI-CRL will output an e-optimal solution of Problem 5 if the number of iterations T of
Numerical Experiments
We design two numerical examples: toy SICMDP and discharge of sewage. By a set of numerical experiments, we illustrate the SICMDP model and validate the efficacy of the SI-CRL algorithm as well as the correctness of our theoretical results. We highlight that in the example of discharge of sewage find that the SICMDP framework greatly outperforms the CMDP baseline obtained by discretizing the original problem in modeling realistic reinforcement learning problems. We solved using full-featured university version of Gurobi [9). Details of our implementation can be found in the appendix. All the experiments are workstation with 8 CPUs and no GPU.
implement methods with Python and LP problems
6.1 Toy SICMDP
We consider most simple SICMDP with |S| = |A| and Y = 1]. Its MDP part is specified in Figure where p E (0.5, 1) and < 1 is small positive number. For each y E (0. 1), design Lipschitz Cy and u. such that the optimal policy takes ag with probability 0.9 and 0.5 on S and s!. respectively. For details of the construction of Toy SICMDP, one may refer the appendix. To make our numerical results more reliable, we repeat all experiments in this subsection for 30 times and report the average results. First, would like check the efficacy of the SI-CRL algorithm. We set T' sufficiently large such that the algorithm is guaranteed to converge. Then we gradually increase m, the size of the dataset, and see whether SI-CRL can recover the pre-defined optimal policy. The results are shown in Figure 3, It can be noticed that as m gets larger, the error term converges to zero, showing that our SI-CRL algorithm may effectively solve reinforcement learning problems for SICMDPs. Second, we would like to validate the theoretical results in Section 5 Specifically, we investigate the sample complexity of SI-CRL for fixed (c, 8) (See Definition 5.1) when y and Pmin vary. T is set to be sufficiently large as in the previous experiment. We present the results in Figure 3 The logarithm sample complexity vs. the transformed parameter of interest approximately linear with slope 1, which indicates our sample complexity bounds are correct and tight.
7

---

(aor P. 1)
(ag, 1 p.1)
(ag. 1)
O
1
S
S
(q,1- p..1p.1 p.1) (a,,p,
(0,, 1,0)
Figure I: MDP part of Toy SICMDP: The triple means (action, probability, reward). The agent should al always take action dg in both states it sets aside the constraints.
Figure 2: (Discharge of Sewage) The satellite image is from NASA and is only for illustrative purposes. The icons represent the locations of the sewage outfalls.
32
2.5
24
30
22
logam
1.5
20
28
1.0
18
0.5
14
24.
0.0
12
15 logom
18
21
6
10 12
5 7 -log
8
10
3loga(1 y)
Figure 3: (Toy SICMDP) Left: The policy returned by SI-CRL converges to the optimal solution as the dataset gets larger. The error term is defined as max V (μ) (H)) supyey C$ (n) Uy the dataset is generated by generative models. Middle: Sample complexity of SI-CRL with varying y; the dataset is generated by generative models. Right: Sample complexity of SI-CRL with varying
Uinn the dataset is generated by a probability measure. Here we set 0.01, ò lines are obtained by linear regression.
0.005
Straight
[SP[A
6.2 Discharge of Sewage
To demonstrate the power of the SICMDP model and the SI-CRL algorithm, we consider a more realistic and complex problem adapted from [18]. Assume there [S] sewage outfalls in region [0, 1]d, with d or 3, and at each time point only single outfall is active. The active outfall would cause pollution in nearby areas, and the impact would decrease with Euclidean distance. We need to figure out strategy to switch between neighboring outfalls to avoid over-pollution each location of the region while minimizing the switching cost. Clearly, this problem can be formulated SICMDP model with Y [0. 1]d and corresponding Gy and By. For details of the construction of the Discharge of Sewage, one may refer to the appendix. In the following numerical experiments, assume that offline dataset generated by generative model is available.
First, we numerically validate our theoretical bounds on sample complexity and iteration complexity. In particular, we investigate the relationship between the sample complexity and iteration complexity of SI-CRL and the size of state space |.S]. Like the case Toy SICMDP, we find the numerical results fit well with theoretical analysis. We show the results in Figures experiment for 30 times and report the averaged results.
As before, we run each
Second, we compare our method with a naive CMDP baseline 3.3 showing the advantage of SICMDP modeling problems like Example 3.1 3.2 In the baseline method, we only consider the constraints standard CMDP problem with Thuseline constraints. The CMDP problem then solved by algorithm proposed in [1]] We visualize the quality of solutions of our proposed method and baseline method Figure 5 can be found that when T Traseline: the policy obtained by our proposed methods of far better quality than the policy obtained by the baseline methods.
on a grid of Y containing Thssetine points, which allows us to model Discharge of Sewage

---

30
5.0
28
4.0
10g
log,T
26
3.5
24
2.5
2.0
22
1.0
100 1.5 2.0 2.5 3.0 3.5 1og2|5]
4.0
1og.|5|
log2|5|
Figure 4: (Discharge of Sewage) Left: Sample complexity of SI-CRL (e 0.015, 8 0.005 T
|
sufficiently large) with different [S]. Middle and right: Iteration complexity of SI-CRL (c 0.015, 5 0.005
> m sufficiently large) with different [S] when d = 2 (middle) and d 3 (right), respectively. Straight lines obtained by linear regression.
5
4
X
3
2
1
X
X
0
Figure 5: (Discharge of Sewage) Visualization of violation of constraints using SI-CRL (left) and
baseline (right). The heat refers to the number log((C, (μ) - uy)4 + x 10-6) log(5 x 10-
Larger number means more serious violation of constraints. The red cross icons represent the T = T baseline check points selected by the algorithms.
SI-CAL
-3-
Baseline
SI-CRL
0.8
Baseline
(Errr))r))
Time (s)
0.6
-7
-8-
0.2
50
150 T
200
0.0
1e-2
3e-3
1e-3 3e-4 1e-4
Error
Figure 6: (Discharge of Sewage) Error term our proposed method and the baseline method when 7' and Thseline vary. (Ō 0.005 ciently large)
Figure Time consumption of our method and the CMDP baseline to get a solution of given accuracy. (5 |i|i|i| sufficiently large)
| m suffi-
0.005
An anti-intuitive phenomenon is that although in our method we need to deal with multiple LP problems while the baseline we only solve one single L.P problem, our method still more time-efficient than the CMDP baseline. Figure indicates that our method takes less time to get solution of given accuracy, which evaluated by the error term sup,ey C (14) uy. The reason that in SI-CRL we solve LP problems with dual simplex method, thus re-optimization after adding

---

new constraint is much faster than re-solving the LP problem from scratch [25]. And our method needs far fewer active constraints attain the same accuracy as the baseline methods, see Figure
7 Conclusion
We have studied novel generalization of CMDP that we have called SICMDP. In particular, we have considered a continuum of constraints rather than a finite number of constraints. We have devised reinforcement learning algorithm SI-CRI. to solve SICMDP problems. Furthermore, we have presented theoretical analysis for SI-CRL,, establishing the sample complexity bounds as well as the iteration complexity bounds. We have also performed the extensive numerical experiments to show the efficacy of our proposed method and its advantage over traditional CMDPs. However, the SI-CRL algorithm can only handle the tabular case, with nice offline dataset avaliable. We would study the SICMDP beyond the tabular case and develop efficient algorithms in future works.
Acknowledgments and Disclosure of Funding
This work has been supported by the National Key Research and Development Project of China (No. 2020AAA0104000, Also, the authors would like to thank Mr. Hao Jin for helpful discussions.
References
[1] Naoki Abe, Prem Melville, Cezar Pendus, Chandan Reddy, David Jensen, Vince P Thomas, James Bennett, Gary F Anderson, Brent R Cooley, Melissa Kowalczyk, et al. Optimizing debt collections using constrained reinforcement learning. In Proceedings of the 16th ACM SIGKDD international conference Knowledge discovery and data mining, pages 75-84, 2010.
[2] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International Conference on Machine Learning, pages 22-31. PMLR, 2017.
[3] Alekh Agarwal, Sham Kakade, and Lin F. Yang. Model-based reinforcement learning with a generative model is minimax optimal, In Proceedings Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 67-83. PMLR, 09-12 Jul 2020. http:tttppocceeetttiiie
mlr wwwppppesssaaieeeee / agarwal20b. html
[4] Eitan Altman. Constrained markov decision processes with total cost criteria: Lagrangian approach and dual linear program. Mathematical methods of operations research, 48(3): 387-417, 1998.
[5] Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
[6] Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. arXiv preprint arXiv: 058/4, 2019.
[7] Sanae Amani, Christos Thrampoulidis, and Lin F Yang. Safe reinforcement learning with linear function approximation. arXiv preprint arXiv: 106.0020600699 2021.
[8] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with generative model. Machine learning. 91 (3):325-349, 2013.
[9] Bruno Betrò, An accelerated central cutting plane algorithm for linear semi-infinite program- ming. 101(3):479 495, dec 2004. ISSN 0025-5610. doi: 10.10077/111107-003-44492 URL
[10] Thiago Mureebe Carrijo, Wesley Bueno Cardoso, and Ardiley Torres Avelar. Linear semi- infinite programming approach for entanglement quantification. Physical Review A, 104(2), Aug 2021. ISSN 2469-9924 doi: 10. 10.1103/physreva.144.22222 URt/ttp://dxx doi org/
10. 10.1103/PhyeRevA. 104.00440 022413
[11] Jinglin Chen and Nan Jiang. Information-theorett considerations in batch reinforcement learning. In International Conference Machine Learning, pages 1042-1051, PMLR, 2019,
10

---

[12] Ian D Coope and G Alistair Watson. A projected lagrangian algorithm for semi-infinitt programming. Mathematical Programming, 32(3):337-356, 1985.
[13] Sebastian Daum and Ralf Werner. A novel feasible discretization method for linear semi-infinite programming applied to basket option pricing. Optimization, 60(10-11):139--13 2011.
[14] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitationn in constrained mdps, 2020.
[15] Javier Garcia and Fernando Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-1480, 2015.
[16] M. A Goberna. Linear semi-infinite optimmiiiiiniiiiiiiiiiiiiiioioi. Mathematical Methods in Practice 2, 1998. URL httttts///c nii http::///...ii......./pa//a///// acc..pphaaaad/0001111116666/////
[17] M.A. Goberna and M.A. López. Linear semi-infinite programming theory: An updated survey.
European Journal of Operational Research, 143(():390-403, 2002. ISSN 0377-2217. doi: https://o..oogggooooooo///111112 ccieeee//attceee///////172212220
URL https: wwwww//wwwww////////////////. www.scciecedirect... com/
[18] WL Gorr, S-À Gustafson, and Kenneth O Kortanek. Optimal control strategies for air quality standards and regulatory policy. Environment and Planning A, 4(2):183-192, 1972.
[19] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2021. URL https: /ww gurobi com
[20] S. A. Gustafson.
On the computational solution of class of generalized moment problems. SIAM Journal on Numerical Analysis, 7(3):343-357, 1970. ISSN 00361429, URL http:
/www www.jjstrrroooo otsttrr.rr//ttable/299555
[21] Aria HasanzadeZonuzy, Dileep Kalathil, and Srinivas Shakkottai. Model-based reinforcement learning for infinite-horizon discounted constrained markov decision processes. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 2519- 2525, 8 2021. doi: 20.224963/jccai.222///44 2021/347
URL https: /tttps://doi.org// org/ 10. 24963/ /a0/s3//jje/ 1///66//jjaa
[22] Rainer Hettich and Kenneth Kortanck. Semi-infinite programming: theory, methods, and applications. SIAM review, 35(3):380 329, 1993.
[23] H. Hu. one-phase algorithm for semi-infinite linear programming. Math. Program., 46(1): 85-103, January 1990. ISSN 00225-5610. doi: 10.1007/BBF015857300 URL https://doi org/10. 100.000////1887753303
[24] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: survey. The International Journal of Robotics Research,
2013.
[25] Achim Koberstein. The dual simplex method, techniques for a fast and stable implementation. 2005.
[26]
Tor Lattimore and Marcus Hutter. Near-optimal pac bounds for discounted mdps. The- oretical Computer Science, 558:125-143, 2014. ISSN 0304-3975. doi: https://doi.org
URL httpsstps::/// //www. sciencedirect. com www.//ciien//articcii.... p:1/$03044975540007775 Algorithmic Learning Theory.
[27] Nicholas Mastronarde and Mihaela der Schaar. Fast reinforcement learning for energy- efficient wireless communication. IEEE Transactions on Signal Processing, 59(12):622-6266, 2011.
[28] Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:000773744 2009.
[29] Pierre Moulin, Mihai Anitescu, Kenneth O Kortanek, and Florian A Potra. The role of linear semi-infinite programming signal-adapted qmf bank design. IEEE Transactions on Signal Processing, 4509):2160-2174, 1997.
11

---

[30] Sven Nordebo, Zhuquan Zang, and Ingvar Claesson. A semi-infinite quadratic programming algorithm with applications to array pattern synthesis. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 48(3):225-23) 2001.
[31] Masahiro Ono, Marco Pavone, Yoshiaki Kuwata, and J Balaram. Chance-constrained dynamic programming with application to risk-aware robotic space exploration. Autonomous Robots, 39 (4):555-571, 2015.
[32] Rembert Reemtsen and Stephan Görner. Numerical methods for semi-infinite programming: survey. In Semi-infinite programmingg pages 195-275. Springer, 1998.
[33] Eugene Remez. Sur la détermination des polynômes d' d'aaproximation de degré donnée. Comm. Soc. Math. Kharkov, 10(196):41-63, 1934.
[34] David Silver, Thomas Hubert, Julian Schritwiieerr, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1 140-11 144, 2018.
[35] Rahul Singh and PR Kumar. Throughput optimal decentralized scheduling of multihop networks with end-to-end deadline constraints: Unreliable links. IEEE Transactions on Automatic Control, 64(1):127-142, 2018.
[36] Georg Still. Discretization in semi-infinite programming: the rate of convergence. Mathematical programming, 91(1):53-6) 69, 2001.
[37] Chen Tessler, Daniel Mankowitz, and Shie Mannor. Reward constrained policy optimization. arXiv preprint 1805.
[38] Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematies. Cambridge University Press, 2018. doi: 10.1017/9781 108231596.
[39] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun- young Chung, David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et Grandmaster level in stareraft using multi-agent reinforcement learning. Nature, 575(7782):350-3355 3544 2019.
[40] Akifumi Wachi and Yanan Sui. Safe reinforcement learning in constrained markov decision processes. In International Conference on Machine Learning, pages 9797-9806. PMLR, 2020.
[41] Huasen WU, R. Srikant, Xin Liu, and Chong Jiang. Algorithms with logarithmic or sublinear regret for constrained contextual bandits. NIPS 15, page 433 441, Cambridge, MA, USA, 2015. MIT Press.
[42] Tengyu Xu, Yingbin Liang, and Guanghui Lan. Crpo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pages 14480-1149) PMLR, 2021.
[43] Liping Zhang, Soon-Yo Yi Wu, and Marco A. López. A new exchange method for convex semi- infinite programming. SIAM on Optimization, 20(6):2959 2916)))29922977.... oct 2010. ISSN 1052-6234, doi: 10.1137/090667133 https://: org/ 10. 1137/09777773
[44] Xiangyu Zhao, Long Xia, Liang Zhang, Zhuoye Ding, Dawei Yin, and Jiliang Tang. Deep reinforcement learning for page-wise recommendations, RecSys '18, page 95-103, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450359016. 10.1 011144/324032332240000
doi:
http:/ttt////ooo 110 10 3240377 URL WRL http:p////do..rrrr0.0001/////200
[45] Liyuan Zheng and Lillian Ratliff Constrained upper confidence reinforcement learning. In Learning for Dynamics and Control, pages 629, PMLR, 2020.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] See Assump- tions 3.4
5.4
(b) Did you include complete proofs of all theoretical results? found in Appendix
[Yes] All proofs can be
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either the supplemental material or as a URL)? [Yes] Please see supplementary material.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section aad Appendix D
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] All the experiments are workstation with CPUs and no GPU.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "WGMj_BDLyUG", "reviewer": "Reviewer_KTCv", "summary": "This paper proposes a generalization for the Constrained MDPs, coined as semi-infinitely constrained MDPs. This framework extends the general CMDP making it able to handle a continuum of constraints. They transform the semi-infinite CMDP into a linear semi-infinite programming problem and then apply tools from semi-infinite programming literature to solve it. They present solid theoretical derivation and supports the claims with thorough empirical analysis.", "questions": "The paper is carefully written answering most questions, thanks to the authors.\n\nLine 128 refers to \"the optimistic approach\". But this was never introduced in the paper before, right? Please note what it is in the paper before referring.\n\nAlgorithm 1 incrementally adds new constraints from the set of constraints. Is this set of constraints discrete, not continuous? If yes, then is the claim of incorporating continuum of constraints correct? Also how it differs from the brute-force approach of discretizing a continuous set of constraints and the using the general CMDP framework? On the other hand, if the set of constraints is continuous, is it possible to clarify the process a bit on how the incremental constraint incorporation works in algorithm 1?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well organized and well written proposing a novel and important direction of incorporating a continuum of constraints into the CMDP framework. The theories and the algorithm are presented clearly with convincing empirical results.\n\nExamples 3.1 and 3.2 presented in the paper are sound and makes the motivation of the proposed SICMDP framework pretty clear.\n\nThe SI-CRL algorithm presented in section 4 is simple, well organized and easy to follow.\n\nThe theoretical analysis presented in section 5 is rigorous. The authors provide both the computational complexity and sample complexity for the proposed algorithm.\n\nSection 6 provides a detailed experimental analysis of SI-CRL algorithm on one toy  and one more realistic problem domain. The results clearly show that SI-CRL outperforms the baseline method both in terms of reducing constraint violations and minimizing the errors.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "OTeaUcbw5x", "reviewer": "Reviewer_iCiQ", "summary": "The paper \"Semi-Infinitely Constrained Markov Decision Processes\" proposes a generalization of CMDPs from finite constraints to a continuum of constraints. The authors devise a generative model based reinforcement learning algorithm for Semi-Infinitely Constrained Markov Decision Processes\", and characterized the sample complexity. Numerical experiments are provided to validate the performance of algorithm.", "questions": "Remark 5.10: The sample complexity bounds do not seem to depend on $Y$. Will this result translate to classical CMDP case?\n\nBecause, existing bounds in the classical CMDP seem to suggest the sample complexity increases with the number of constraints. \n\n\nThe details on the experiments are missing. How is the LISP being solved? ", "limitations": "Yes, this algorithm works for only tabular case, and only when a offline data set is provided apriori.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is reasonably well written, presentation easy to follow. The use cases in Section $3$ illustrate the applicability of this approach.\n\nThe theoretical results (sample complexity bounds) are strong. But the novelty in the analysis seems to be limited, since multiple works have addressed similar problems (classical CMDPs) in the past, and this approach is very similar to the earlier works. [HasanzadeZonuzy, 2021]. \n\nThe algorithm is a generative model based, it only works with a data provided apriori.\n\nNumerical experiments indicate the advantage of the algorithm w.r.t the baseline, but this section is weak.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6iLA8cLaJ-R", "reviewer": "Reviewer_V6h8", "summary": "This paper generalizes the traditional constrained Markov decision process (CMDP) to a CMDP that has infinitely many constraints, which is called semi-infinitely CMDP (SICMDP). The main challenge of solving the optimal policy for such a SICMDP is to deal with a continuum of constraints, and existing constrained reinforcement learning (CRL) methods do not work anymore. In this paper, the authors propose the first RL algorithm for the tabular SICMDP based on linear semi-infinitely programming (LSIP). Specifically, they first construct a set of dynamics under the offline setting or the generative model setting, and formulate an optimistic planning problem. Then, they augment the state-action occupancy measure to the state-action-state occupancy measure, by which they transform the optimistic planning problem into LSIP. Finally, such LSIP is solved via an existing method. Furthermore, the authors prove the sample complexity and iteration complexity of their algorithm under some assumptions. In the experiments, they show the effectiveness of their method and the tightness of their theoretical bounds.", "questions": "1. In this paper, the reward and cost functions are known a priori. Do the method and theory still work when the reward and cost functions are unknown and learned from samples as the dynamic?\n\n2. The method in this paper only works for tabular SICMDPs with small state and action spaces. RL algorithms for SICMDPs beyond the tabular case would be significant.\n\n3. What is the technical difference between this work and [21], except that this work is a LSIP?\n\n4. The authors should clarify their contributions more clearly.\n\n5. It would be interesting to design algorithms for the episodic setting in addition to the generative model setting and offline setting, since the last two setting omit exploration and are somewhat easier.\n", "limitations": "1. The PAC bound in this paper is flawed, and should consider both the statistical and optimization errors.\n\n2. The technical difference between this work and [21] should be explained. And the authors should clarify their contributions more clearly.\n\n3. The extensions of this paper to the episodic setting or large MDPs would be appreciated.\n", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. This paper generalizes CMDP to SICMDP, which is a novel model that has many applications. \n2. This paper introduces tools from LSIP to RL and proposes the first RL algorithm for solving the optimal policy of SICMDP.\n3. This paper provides the sample complexity and iteration complexity of their algorithm. \n\nWeaknesses\n1. About solution: \n- Although this paper is the first one to focus on SICMDP, the proposed solution has limited novelty. Specifically, this paper constructs a confidence interval for the dynamic and formulates an optimistic planning problem, which is widely used in model-based papers, e.g., [14] and [21]. \n- This paper transforms the optimistic planning problem into LSIP form. Such transform is similar to [21]. At last, the LSIP is solved by an existing solver. \n\n2. About theory: \n- The PAC bound in this paper is flawed. The authors prove the sample complexity of their algorithm under the assumption that Problem (5) can be solved exactly, which is unreasonable. The authors should prove that, in order to get a $\\epsilon$-optimal policy with probability $1-\\delta$, how many samples and number of iterations are needed. \n- In Theorem 5.7 and 5.11, the authors say “a modification of SI-CRL is …”. But they do not describe what the modification is.\n\n3. About experiments:\n- In Discharge of Sewage domain, the authors compare the CMDP baseline obtained by discretizing the original problem. However, they only discretize the infinite set Y into 9 points, which may be unfavorable for such a CMDP baseline. They should add experiments about discretizing Y into more points.\n- In Figure 5, the authors show the results of constraint violation. But they should also show the performance of the objective, i.e., the cumulative rewards, as in regular CRL papers.\n\n4. About related work:\n- The authors should explain the difference between this work and [21].\n- The literature review on CRL works is far from thorough. The authors should add more related works about CRL.\n\n5. About Writing:\n- In the penultimate paragraph of Introduction, some notations (e.g., d, diam(Y)) are used \tbefore introducing them, which is confusing for readers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept