Density Constrained Reinforcement Learning
Authors: Zengyi Qin
Yuxiao Chen
Chuchu Fan
Venue:  (2021)
Keywords: Constrained Reinforcement Learning
Density
Safe AI

Abstract: Constrained reinforcement learning (CRL) plays an important role in solving safety-critical and resource-limited tasks. However, existing methods typically rely on tuning reward or cost parameters to encode the constraints, which can be tedious and tend to not generalize well. Instead of building sophisticated cost functions for constraints, we present a pioneering study of imposing constraints directly on the state density function of the system. Density functions have clear physical meanings and can express a variety of constraints in a straightforward fashion. We prove the duality between the density function and Q function in CRL and use it to develop an effective primal-dual algorithm to solve density constrained reinforcement learning problems. We provide theoretical guarantees of the optimality of our approach and use a comprehensive set of case studies including standard benchmarks to show that our method outperforms other leading CRL methods in terms of achieving higher reward while respecting the constraints.

Under review as a conference paper at ICLR 2021
DENSITY CONSTRAINED REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Constrained reinforcement learning (CRL) plays an important role in solving safety-critical and resource-limited tasks. However, existing methods typically rely on tuning reward or cost parameters to encode the constraints, which can be tedious and tend to not generalize well. Instead of building sophisticated cost functions for constraints, we present pioneering study of imposing constraints directly on the state density function of the system. Density functions have clear physical meanings and can express a variety of constraints in a straightforward fashion. We prove the duality between the density function and Q function in CRL and use it to develop an effective primal-dual algorithm to solve density con- strained reinforcement learning problems. We provide theoretical guarantees of the optimality of our approach and use a comprehensive set of case studies includ- ing standard benchmarks to show that our method outperforms other leading CRI. methods in terms of achieving higher reward while respecting the constraints.
INTRODUCTION
Constrained reinforcement learning (CRL) Achiam et al. 2017 Altman 1999 Dalal et al. 2018 Paternain et al. 2019; Tessler et al. 2019) has received increasing interests as a way of address- ing the safety challenges in reinforcement learning (RL). CRL techniques aim to find the optimal policy that maximizes the cumulative reward signal while respecting the specified constraints. Ex- isting CRL approaches typically involve constructing suitable cost functions and value functions to take into account the constraints. Then crucial step is to choose appropriate parameters such as thresholds for the cost and value functions encode the constraints. However, one significant gap between the use of such methods and solving practical RI problems is the correct construction of the cost and value functions, which typically not solved systematically but relies on engineering intuitions (Paternain et al., 2019). Simple cost functions may not exhibit satisfactory performance, while sophisticated cost functions may not have clear physical meanings. When cost functions lack clear physical interpretations, it is difficult to formally guarantee the satisfaction of the performance specifications, even if the constraints on the cost functions are fulfilled. Moreover, different envi- ronments generally need different cost functions, which makes the tedious tuning process extremely time-consuming.
In this work, we fill the gap by imposing constraints on the state density functions systematic way to encode constraints RI. Density is a measurement of state concentration in the state space, and is directly related the state distribution. It has been well-studied in physics (Yang) 1991] and control (Brocketi 2012. Chen & Ames| 2019; Rantzer 2001). A variety of real-world constraints are naturally expressed density constraints in the state space. Pure safety constraints can be trivially encoded as the entire density of the states being contained in the safe region. In more general examples, the vehicle densities certain areas are supposed to be less than the critical density (Gerwinski & Krug, 1999) to avoid congestion. When spraying pesticide using drones, different parts of farmland requires different levels of pesticide density. Indeed, in the experiments will see how these problems are solved with guarantees using density constrained RL (DCRL).
intuitive and
Our approach is based on the new theoretical results of the duality relationship between the density function and value function in optimal control (Chen & Ames) 2019). One can prove generic dual- ity between density functions and value functions for both continuous dynamics and discrete-state Markov decision processes (MDP), under various setups such using Bolza form terminal con- straints, infinite horizon discounted rewards, or finite horizon cumulative rewards. In Chen & Ames (019) the duality is proved for value functions in optimal control, assuming that the full dynamics

---

Under review as a conference paper at ICLR 2021
of the world model is known. In this paper, we take nontrivial step establish the duality between the density function and the Q function (Theorem I]. We also reveal that under density constraints, the density function and Q function is also dual to each other (Theorem 2), which enables to force constraints on state density functions in CRL. We propose a model-free primal-dual algorithm (Algorithm I to solve the DCRL problem, which is applicable in both discrete and continuous state and action spaces, and can be flexibly combined with off-the-shelf RL methods to update the policy. We prove the optimality of the policies returned by our algorithm if converges (Proposition [ We also discuss the approaches to computing the key quantities required by Algorithm [|
Our main contributions are: 1) We are the first to introduce the DCRL problem with constraints on state density. which is associated with a clear physical interpretation. 2) We are the first to prove and use the duality between density functions and Q functions over continuous state space to solve DCRL. 3) Our model-free primal-dual algorithm solves DCRL and can guarantee the optimality of the reward and satisfaction of density constraints simultaneously. 4) We use an extensive set of experiments to show the effectiveness and generalization capabilities of our algorithm over leading approaches such as CPO, RCPO, and PCPO, even when dealing with conflicting requirements
Related work. Safe reinforcement learning (Garcia & Fernández, 2013) primarily focuses on two
approaches: modifying the optimality criteria by combining a risk factor (Heger 1994. Nilim &
El Ghaoui 2005| [Hwward & Matheson 1972 Borkar 2002 Basu et al.] 2008; Sato et al. 1001
Dotan Di Castro & Mannor 2012 Kadota et al. 2006; Lötjens et al. 2019) and incorporating extra
knowledge to the exploration process (Moldovan & [abeee][2012] | Abbeel et al. 2010 Tang al.
2010 Geramifard et al.] 2013]] Clouse & Utgofi 1992] Thomaz et al. 2006;; Chow et al. 2018).
Our method falls into the first category by imposing constraints and is closely related constrained
Markov decision processes (Aluman 1999) (CMDPs) and CRL (Achiam el al. [017 Lillicrap et al.
2016
CMDPs and CRL have been extensively studied in robotics (Gu et al. [017]] Pham et al.
2018
game theory (Altman & Shwartz 2000). and communication and networks (Hou & Zhao
2017
Bovopoulos& & Lazar 1992). Most previous works consider the constraints on value functions,
cost functions and reward functions (Altman, 1999. Paternain et al. 2019: Altman & Shwartz, 2000)
Dalal et al. 2018 Achiaa et al., 2017; Ding et al. 2020). Instead, we directly impose constraints
on the state density function. Our approach builds on Chen et al. (2019) and Chen & Ames (011)),
which assume known model dynamics. Instead, in this paper we consider the model-free setting
and proved the duality of density functions to Q functions. In /eibel & Wysotzki| (2005) density was studied as the probability of entering error states and thus has fundamentally different physical interpretations from us. In Dai et al. (2017) the duality was used boost the actor-critic algorithm. The duality is also used in the policy evaluation community (Nachum et al. 2019) |Nachum & Dai 2020 Tang et al.) 2019). The offline policy evaluation method proposed by Nachum et al.. (2019) can also be used to estimate the state density in our paper, but their focus is policy evaluation rather than constrained RL. Therefore, we claim that this paper is the first work to consider density constraints and use the duality property to solve CRL.
2 PRELIMINARIES
Markoy Decision Processes (MDP). An MDP M tuple A,,,,PR,R,)) 7). where (1) S is the (possibly infinite) set of states; (2) A is the (possibly infinite) set of actions; (3) P S x A x S + [0. 1] is the transition probability with P(s, a, s') the probability of transitioning from state s to s' when action E A is taken; (4) R: S x A S + IR is the reward associated with the transition P under the action a E A; (5) 7 E [0, 1] is a discount factor.
A policy æ maps states to probability distribution over actions where T(als) denotes the prob- ability of choosing action a at state s. Let a function & S + I specifies the initial state distribution. The objective of MDP optimization is to find the optimal policy that maxi- mizes the overall discounted reward Jp = S (s))ss, where (T(ss) is called the value function and satisfies (s) = (s) + + Is P(s, a, s'' da, and rT(s) = SA (a]s) Ig P(s, a, (..'')((s, a, s')ds'd da is the one-step reward from state following policy и. For every state s with occurring as an initial state with probability Φ(s). it incurs a expected cumula- tive discounted reward of V* (s). Therefore the overall reward is Is V(s)V=(s)dss Although the equations are written in integral forms corresponding to continuous state-action space, the discrete counterparts can be derived similarly. Two major methods for solving MDPs are value iteration and
2

---

Under review as a conference paper at ICLR 2021
policy iteration, both based on the Bellman operator. Take value iteration example, the Bellman optimality condition indicates ((s) = max [ P(s, s, a, (R)s, a, s') + (V)(ss)dss However, the formulation of value functions in MDP typically cannot handle constraints the state distribu- tion, which motivates the density functions.
Density Functions. Stationary state density functions p. 5 - >> are measurements of the state concentration in the state space (Chen & Ames 2019 Rantzer 2001 We will show later that generic duality relationship exists between density functions and value functions (or functions), which allows us to directly impose density constraints in RL problems. For infinite horizon MDPs, a given policy x and an initial state distribution Φ, the stationary density of state expressed
1 (5) Σ
= S/7 Φ).
which is the discounted sum of the probability of visiting s. The key motivation behind the stationary density distribution is because most of the density constraints are time invariant and are instead defined over the state space. Stationary distribution gives a projection of all possible reachable states to the state space and is invariant over time. Therefore, satisfy the density constraints, the system always satisfies the density constraints at any time. It is straightforward show that all theories and algorithms in this paper actually does not depend on the fact that the density distribution is stationary.
long the stationary density
We prove in the appendix that the density has an equivalent expression
pT(s) - 6(s) + J π T(als')P(s' a, () (ddds'
where ø is the initial state distribution. & coincides with the normalized (positive) supply function in Chen et al.) (2019), which is defined as the rate of state entering the state space as an initial condition. We omit the details on constructing stationary distribution, which are provided in Chen al. (2019).
Definition 1 (DCRL). Given MDP M (S, A, 7) and an initial state distribution é, the density constrained reinforcement learning problem finds the optimal policy nt" that maximizes the expectation of the cumulative of a reward signal I's ob s) V (s)ds, subject to constraints on the stationary state density function represented as Pmiin S p (s) S Pmax (8) for Vs S.
3 DENSITY CONSTRAINED REINFORCEMENT LEARNING
In this section, we first show the duality between Q functions and density functions, and then intro- duce a primal-dual algorithm for solving DCRL, problems.
3.1 DUALITY BETWEEN DENSITY FUNCTIONS AND Q FUNCTIONS
The duality relationship between density functions and value functions in optimal control is recently studied, for both dynamical systems and finite-state MDPs in Chen & Ames (2019). In this paper, we take step further to show the duality property between the density function and Q function, for both continuous and discrete state MDPs. Our work is the first to prove and use the duality between density functions and functions has not been explored and utilized by published RL literature. We use the standard infinite horizon discounted rewards cumulative rewards and infinite horizon average rewards can be proved in a similar way.
continuous state space solve density constrained RL, which
an illustrative example. The duality in other setups such as finite horizon
To show the duality with respect to Q function, action taken at each state. Let p. S x A + R>0 be a stationary state-action density function, which represents the amount of state instances taking action state s. Po related to Ps via marginalization: ps(s) = SA (s(s, a da. Under a policy x, we also have p.. (s. a) PT (als).
extend the stationary density P% consider the
"p is necessarily probability density function. That is, Ig p(s) is enforeed.
3

---

Under review as a conference paper at ICLR 2021
Let Letr(s, P(,,a, s')ds. Consider the density function optimization:
/
Jd = max
po ()) a)ddad
P.
(3)
s.t. 1 (s. x(als) ((s))
(66)) +>
P(s', ,'',a,, (s ds')
and the Q function optimization:
Jp max Q. / ((s) J
(s) ("(ssa)r(aabs)dade
(4)
s.t. Q= a) = r(s, + P(s.a, T(d'ss'00 (s', a''dd''''' ds'
Theorem 1. The optimization objectives Ja and J, are dual to each other and there is duality gap. If both are feasible, then Ja Jp and they share the same optimal policy π
The proof of Theorem Dis included in the appendix. Theorem T states that optimizing the density function (dual) equals to optimizing Q functions (primal) since they will result in the same optimal policy π² Since the dual optimization is directly related to density, constraints on the dual problem. Consider the density constrained optimization:
naturally enforce density
[sJ, 0r (0, ( a)dddds
J3 = maxx
P:
s.t. 1% (8, a) (als) ((s)) (0()) + p(s',a',s)) a)) ('',''' a''dd' ds')
(5)
Pmin (8) S (s)
(s)= S Pmmaz())
The marginalization p. (s) = SA 0% (s, da. Denote the Lagrange multipliers for Po 2 Pmin and D < Pmaza as a_ :S R20 and 04 Rzo. The primal problem is formulated as:
d(s) / ((((s,))(aal)dddd
JØ = max Q. 5
(6)
s.t. (= a) = r(s, + o (s) - o+()) (2 to P(s,a, / =(a'ls')Q*t d''d,''''''d ds'
The difference between 6 and is that the reward r(s, a) is adjusted by -s)
Theorem 2. The density constrained optimization objectives Jā and J are dual to each other. If both are feasible and the KKT conditions are satisfied, then they share the same optimal policy π².
The proof of Theorem 2 provided in the appendix. Theorem 2 reveals that when the KKT condi-
tions are satisfied, the optimal solution to the adjusted unconstrained primal problem (6) is exactly the optimal solution the dual problem (5) with density constraints. Such an optimal solution not only satisfies the state density constraints. but also maximizes the the total reward J Thus it is the optimal solution the DCRL problem.
Remark 1. The duality relationship between density and value function wide exists, for example, Linear Programming. Technically, any nonnegative dual variable satisfying the conservation law (Liouville PDE in the continuous case, see Chen & Ames (2019)) is valid dual. However, among all valid dual variables, the state density associated with a clear physical interpretation as the concentration of states, and are able to directly apply constraints the density in RL.
Remark 2. Theorem and can be used in Constrained MDP (CMDP). In CMDP, the con- straint Ja Ss H(s) I a is indeed a special case of the density constraint. Jo Is (ss)ds is the immediate cost and V, is the value of cost. Thus the CMDP constraint J. S a equals to special case of constraint density Ps-
IS Vc = fs (s)rr((s))d
a + Pe(s)re(s)ds < a, where re
4

---

Under review as a conference paper at ICLR 2021
Update nt based on o, and a.
Primal domain
Dual domain
Update o, and a_ based on x
04 and d.
Figure I: Illustration of the primal-dual optimization in DCRL. In the primal domain, we solve the adjusted primal problem in 6 to obtain the policy Then in the dual domain, the is used evaluate the state density. Based whether not the density constraints and KKT conditions
satisfied, the Lagrange multipliers 0+ and a- are updated as 04 <- max(0: 0. a(p (mas)) and o < max a- + a(pmin - p )). In the next loop, since the reward r(s. a) + a- as) a (+) is updated, the primal optimization solves for the new π
under the updated reward. The loop stops when the KKT conditions are satisfied.
3.2 PRIMAL-DUAL ALGORITHM FOR DCRL
The DCRL problem looks for optimal policy of MDP subject to constraints the density fune- tion. In this section, we continue considering the case where the stationary density in the infinite horizon discounted reward case must satisfy some upper and lower bounds: Pree (8) 2 pa(s) 2 (s), Vs E S. However, the primal-dual algorithm discussed in this section can be easily ex- tended to handle other reward function setup and other types of constraints on the density function.
By utilizing the duality between density function and Q function (Theorem 2 in the density con- strained optimization 6) the DCRL problem can be solved by alternating between the primal and dual problems, as is illustrated in Figure [] In the primal domain, we solve the adjusted primal prob- lem (reward adjusted by Lagrange multipliers)
(6) using off-the-shelf unconstrained RL methods such as TRPO (Schulman et al. 2015 and DDPG [Lillicrap et al. 2016). Note that the density con- straints are enforced dual domain and the primal domain is still an unconstrained problem, which make use of existing RL methods to solve the primal problem. In the dual domain, the policy is used to evaluate the state density function, which is described details in Section 3.3
means
If the KKT conditions 0+ (p" |mmx) 0, a_ (Pmin p%) = and Pmain I PT S Pmaz are not satisfied, the Lagrange multipliers are updated and enter the next primal-dual loop. The key insight is that the density constraints can be enforced in the dual problem, and we can solve the dual problem by solving the equivalent primal problem using existing algorithms. Alternating between the primal and dual optimization can gradually adjust the Lagrange multipliers until the KKT con- ditions are satisfied. A general template of the primal-dual optimization with density constraint is provided in Algorithm
Algorithm 1 General template for the primal -ual optimization with density constraints
1: Input MDP M, initial condition distribution Φ, constraints on the state density Pmox and Puain
2: Initialize π randomly, a + 0, a_ + O
3: Generate experience D ((,,,rr, s a, ~ (s) then r and s' are observed]
4: Repeat
5:
(s,a,r,s)) +
-,, (s,
0+ (s), for each (s,a,r,s) D,r
6: Update policy π using Dr
7: Generate experience D2 C ((8, a, r, 8') 80 ~ 0, a (s)) then r and are observed)
8: Compute stationary density & using Dx
9:
0+ f max(0, 0 a(pp pmaz))
10:
max(0, + alpmin p%))
11: Until 0. (p Pmax) = 0, a_ (pmin - P.) = and Pmin S p S Pina
12:
Return n, P
In Lines 5 6 of Algorithm I the Lagrange multipliers a and a_ are used to adjust rewards, which lead to an update of the policy æ. In Lines 8 the policy used evaluate the stationary density, then the Lagrange multipliers are updated following dual ascent (Lines D 10). The iteration stops when all the KKT conditions are satisfied. Although Algorithm I is derived for the infinite horizon reward case, it also applies to the finite horizon case.
Proposition 1. If Algorithm I converges to a feasible solution that satisfies the KKT condition, is the optimal solution the DCRL problem. (Proof provided in the appendix.)
5

---

Under review as a conference paper at ICLR 2021
3.3 COMPUTATIONAL APPROACHES
Algorithm requires computing the policy n, stationary density P3 Lagrange multipliers 0+ and d-. For オ, there are well-developed representations such as neural networks and tabular methods. Updating using experience D is also straightforward using standard approaches such as policy gradients or Q-Learning. By contrast, the computation of P 0+ and a_ is need to be addressed. The following computational approaches apply to both finite and infinite horizon.
Density functions. In the discrete state case, P: is represented by a vector where each element corresponds to a state. To compute P from experience D, (line of Algorithm [ let Dz contain N episodes where episode i ends at time Ti Let 8 represent the state reached at time j in the tth episode. Initialize p <0, For all E {1.-.., ,N3 and j E [0.1, .Ti., do the update P (s + PT (s V The resulting vector p. approximates the stationary state density, In the continuous state space, P. cannot be represented as a vector since there are infinitely many states. We utilize the kernel density estimation method Chen
(2017); Chen & Ames (219)) that computes E- Kr 2t) where K₁, is the kernel function satisfying Vs S, (s) 2 and Is (s) 1. There are multiple choices of the kernel Kn. e.g. Gaussian, Spheric, and Epanechnikov kernels Chen (2017), and probabilistic guarantee of accuracy can be derived, c.f. Wasserman (2019).
P. (s) at state using the samples in Dx with p
N
Lagrange multipliers. If the state space is discrete, both c7 and a_ are vectors whose length equals to the number of states. In each loop of Algorithm [ after the stationary density is computed, 0+ If the state space is
and a_ are updated following Line 9 and Line 10 respectively in Algorithm [ continuous, we construct Lagrange multiplier functions a+ and a_ from samples in the state space leveraging linear interpolation. Let ø every loop of Algorithm|| I] denote the Lagrange function computed by the previous loop as of and o We compute the updated Lagrange multipliers at states as:
[s1, $2.-.. represent the samples in the state space. In
0+ |max(0, o² (s1) + (s) Pmoz max(0, of (s2) a(p) Pmma ... Ø_ = mmax(0, o2 (s1) + a (pmin (s1) - (si)), max(0, o² ($2) + (pmina())) - pT, (82)),
Then the new a+ and a_ are obtained by linearly interpolating 0. and の_ respectively.
EXPERIMENT
We consider the MuJoCo (ooorrvv et al. 2012) benchmark and the autonomous electrical vehicle routing benchmark adopted from Blahoudek al. (2020) in our experiment. We also report addi- tional experimental results on 3 other benchmarks in the appendix, including safe electrical motor control, an agricultural spraying drone, and a express delivery service transportation system, which all can show the power of our DCRL method over other approaches when dealing with complex density constraints. The evaluation criteria includes the reward and constraint values. The meth- ods should keep the constraint values below the required thresholds and achieve as much reward as possible. The definition of reward and constraint vary from task to task and will be explained when each task is introduced. Our implementation will be made available upon acceptance of the paper.
Baseline Approaches. Three CRL baselines are compared. PCPO (Yang et al. 2020) first per- forms an unconstrained policy update then project the action to the constrained set. CPO (Achiam et al. 2017) maximizes the reward in a small neighbourhood that enforces the constraints. RCPO (Tessler et al.) 2019) incorporates the cost terms and Lagrange multipliers with the reward function to encourage the satisfaction of the constraints. We used the original implementation of CPO and PCPO with KL--projetioo that leads to the best performance. For RCPO, since the official implementation is not available, we re-implemented RCPO and made sure it matches the original performance, RCPO restricts the expectation of the constraint values to be smaller than a threshold instead of enforcing the constraints (mar(s) and (min(s) for every state All the three baseline approaches and our DCRL have the same number of neural network parameters. Note that the base- line approaches enforee the constraints by restricting return values while our DCRL restricts the state densities. The constraint thresholds of DCRL and the baseline methods can be inter-converted by the duality of density functions and value functions (Chen & Ames 2019).

---

Under review as a conference paper at ICLR 2021
Point-Gather
Point-Circle
Ant-Circle
80
15
60
Reward
Reward
Reward
10
90
DCRL
PCPO
CPO
20
RCPO
400
200
400
600
200
400
600
Number of policy updates
Number of policy updates
Number of policy updates
Point-Gather
Point Circle
Ant-Circle
10
PCPO
DCRL
Constraimt valuees
15
Constraint values
30
8
CPO
20
Constraint
6-
Threshold
4
2
200
400
600
Number of policy updates
Number of policy updates
Number of policy updates
Figure 2: Performance on the constrained reinforcement learning tasks the MuloCo Todorov al. 2012 benchmark. results are averaged over independent trials. The methods are expected to achieve high reward while keeping the constraint values close to the threshold.
3.0
Vehicle density constraint
2.0
Energy constraint
1.5
Reward
2.0
1.5
1.0
DCRL
1.0
PCPO
0.5
0.0
Threshold
0.0
200
400
600
200
400
200
400
600
Number of policy updates
Number of policy updates
Number policy updates
Figure 3: Performance on the autonomous electrical vehicle routing benchmark. All results are averaged over 10 independent trials. The methods expected to keep close to the energy threshold (middle) and below the vehicle density threshold (right), while maximizing the reward (left).
4.1 MuJoCo BENCHMARK
Domain Description. Experiments are conducted on three tasks adopted from CPO (Achiam et al., 2017) the MuJoCo benchmark, including Gather task, a point agent moves on a plane and tries to gather as many apples as possible while keeping the probability of gather bombs below the threshold. In the Point-Circle task, point agent tries to follow circular path that maximizes the reward, while constraining the probability of exiting an given area. The Ant-Circle task is similar the Point-Circle task except that the agent an instead of point, detailed configurations of the benchmarks can be found in Achiam et al. (011))
Point-Circle and Ant-Circle In the Point-
Experimental Results. Figure demonstrates the performance of the four methods. In general, DCRL is able to achieve higher reward than other methods while satisfying the constraint thresh- olds. In the Point-Gather and Point-Cirele environments, all the four approaches exhibit stable performance with relatively small variances. In the Ant-Circle environment, the variances of reward and constraint values are significantly greater than that in Point environments, which is mainly due to the complexity of ant dynamics. In Ant- Ant-Circle, after 600 iterations of policy updates, the straint values the four approaches converge to the neighbourhood of the threshold. The reward of DCRL falls behind PCPO in the first 400 iterations of updates but outperforms PCPO thereafter.

---

Under review as a conference paper at ICLR 2021
4.2 AUTONOMOUS ELECTRICAL VEHICLE ROUTING BENCHMARK
Domain Description. Our second case study is about controlling autonomous electric vehicles (EV) in the middle of Manhattan, New York. It is adopted from Blahoudek et al.] (2020) and is shown in Figure 4.2 When EVs drive their destinations, they can avoid running out of power by recharging at the fast charging stations along the roads. At the same time, the vehicles should not stay at the charging stations for too long in order save resources and avoid congestion. An road intersection is called a node. In each episode, an autonomous EV starts from a random node and drives the goals. At each node, the EV chooses a direction and reaches the next node along that direction at the next step. The consumed electric energy is assumed to be proportional to traveling distance. The EV fully charged at the beginning of each episode, and can choose to recharge at the fast charging stations. There are 1024 nodes and 137 charging stations in total. Denote the full energy capacity of the vehicle as of and the remaining energy as ey. When arriving at charging station, the EV chooses charging time T E [0, 1J, then its energy increases to min(c), Cr tcr). The action space includes the EV direction and the charging time The state space S C R is consisted of the current 2D location and the remaining energy Cr-
Two types of constraints are considered: (1) the min- imum remaining energy should keep close to a re- quired threshold and (2) the vehicle density at charg-
ing stations should be less than a given threshold. Apparently, if the EV chooses larger т, then the constraint (I) is more likely to be satisfied, while (2) is more likely to be violated, since a larger will increase the vehicle density at the charging station. These contradictory constraints pose greater chal- lenge to the RI. algorithms. Both constraints can be naturally expressed as density constraints. For con- straint (1), we can limit the density of low-energy states. For constraint (2), it straightforward to limit the EV density (a function of E[rr) at charg- ing stations. The threshold of density constraints are transformed to the threshold of value functions to be used by the baseline methods. The conversion is based on the duality of density functions and value functions (Chen & Ames 2019).
Experimental Results. Figure B demonstrates the performance of the four approaches. Since this task has two contradicting constraints, it is challenging to satisfy both and at the same time maximize the reward. Although the baseline methods can approxi- mately satisfy both constraints, their reward values are lower than the proposed DCRL method, Our Proposition reveals that DCRL can achieve the op- timal reward when enforcing the constraints, which is an important reason why DCRL shows higher reward than other methods in this task.
Figure 4: Autonomous electric vehicle routing in Manhattan: Control the electric vehicles to drive on the grey lines roads and reach red nodes as goals. Vehicles can be charged at the gold nodes as fast charging stations. The roads and fast charg- ing stations are from the real- weal-world data (Bla-) houdek et al.) 2020). More experimental results are provided in the appendix B.4.
CONCLUSION AND FUTURE WORKS
We introduced the DCRL problem to solve the RL problem while respecting the constraints on the state densities. State densities have clear physical meanings and can express a variety of constraints of the environment and the system. We proposed model-free primal-dual algorithm to solve DCRL, which avoids the challenging problem of designing cost functions to encode constraints. Note that algorithm does not guarantee the density constraints satisfied in the learning process. In the future, we aim to improve the algorithm to enforce the density constraints during training as well. We also plan to identify the assumptions prove the convergence of our algorithm.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Pieter Abbeel, Adam Coates, and Andrew Y Ng. Autonomous helicopter aerobatics through ap- prenticeship learning. The International Journal of Robotics Research, 29(13):1608-1639, 2010.
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International Conference Machine Learning (ICML). pp. 22-31, 2017.
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Eitan Altman and Adam Shwartz. Constrained markov games: Nash equilibria. In Advances in Dynamic Games and Applications, pp. 213-221. Springer, 2000.
Arnab Basu, Tirthankar Bhattacharyya, and Vivek Borkar. A learning algorithm for risk-sensitive Mathematics of operations research, (38444888-89))) 2008
František Blahoudek, Tomášs Brázdil, Petr Novotný, Melkior Ornik, Pranay Thangeda, and Ufuk
Topcu. Qualitative controller synthesis for consumption markov decision processes. International Conference on Computer-aided Verification, 2020.
Vivek S Borkar. Q-Jearning for risk-sensitive control. Mathematics of operations research, 27(2):
294-311, 2002.
Andreas D Bovopoulos and Aurel A Lazar. The effect of delayed feedback information network performance. Annals of Operations Research, 36(1):101-12) 1992.
Roger Brockett. Notes on the control of the liouville equation. In Control of partial differential equations, pp. 101-129. Springer, 2012.
Yen-Chi Chen. A tutorial on keree density estimation and recent advances. Biostatistics Epi- demiology, 1()):161-18,,2111 2017.
Yuxiao Chen and Aaron D. Ames. Duality between density function and value function with applications in constrained optimal control and markov decision process. arXiv preprint arXiv:1902.09583, 2019.
Yuxiao Chen, Andrew Singletary, and Aaron Ames. Density functions for guaranteed safety robotic systems. American Control Conference, 10 2019.
Yinlam Chow, Ofir Nachum, Edgar Duemez-Guzman, and Mohammad Ghavamzadeh. Iyapunov- based approach safe reinforcement learning. In Advances in neural information processing systems, pp. 8092-8101, 2018.
Jeffery A Clouse and Paul E Utgoff. A teaching method for reinforcement learning. In Machine Learning Proceedings 1992, pp. 92-101. Elsevier, 1992.
Dai, Albert Shaw, Niao He, Lihong Li, and Song. Boosting the actor with dual critic. arXiv preprint arXiv:1712.10282) 2017.
Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerik, Todd Hester, Cosmin Paduraru, and Yuval Tassa. Safe exploration in continuous action spaces. arXiv preprint arXiv: 2018.
Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo Jovanovic. Natural policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Information Processing Systems, 33, 2020.
Aviv Tamar Dotan Di Castro and Shie Mannor. Policy gradients with variance related risk criteria. In Proceedings of the 29th International Conference on Machine Learning, Edinburgh, Scotland, UK, 2012.
Javier Garcia and Fernando Feráández. A comprehensive survey safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-1480, 2015.
Peter Geibel and Fritz Wysotzki. Risk-sensitive reinforcement learning applied to control under constraints. Journal of Artificial Intelligence Research, 24:81-108, 2005.

---

Under review as a conference paper at ICLR 2021
Alborz Geramifard, Joshua Redding, and Jonathan P How. Intelligent cooperative control architec- ture: a framework for performance improvement using safe learning. Journal of Intelligent & Robotic Systems, 72(1):83-103 2013.
M Gerwinski and J Krug. Analytic approach the critical density in cellular automata for traffic flow. Physical Review E, 60(1):188, 1999.
Shixiang Gu, Ethan Holly. Timothy Lillicrap, and Sergey Levine. Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates. In 2017 IEEE international confer- ence on robotics and automation (ICRA), pp. 3389-3396. IEEE, 2017.
Matthias Heger. Consideration of risk in reinforcement learning. In Machine Learning Proceedings 1994, pp. 105-111. Elsevier, 1994.
Chen Hou and Qianchuan Zhao. Optimization of web service-based control system for balance between network traffic and delay. IEEE Transactions on Automation Science and Engineering, 15(3):1152-1162 2017.
Ronald A Howard and James E Matheson. Risk-sensitive markov decision processes. Management science, 18(7):356-36, 1972.
Yoshinobu Kadota, Masami Kurano, and Masami Yasuda. Discounted markov decision processes with utility constraints. Computers & Mathematics with Applications, 51(2):279-288 2006.
Timothy Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning, 2016.
Bjöm Lötjens, Michael Everett, and Jonathan P How. Safe reinforcement learning with model uncertainty estimates. In 2019 International Conference on Robotics and Automation (ICRA), pp- 8662-8668. IEEE, 2019.
Teodor Mihai Moldovan and Pieter Abbeel. Safe exploration in markov decision processes. arXiv preprint 1205.4:2005.88/11 2012.
Ofir Nachum and Bo Dai. Reinforcement learning via fenchel-roccafelllar duality. arXiv preprint arXiv:2001.01866 2020.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems, pp. 2318-2328, 2019.
Arnab Nilim and Laurent El Ghaoui. Robust control of markov decision processes with uncertain transition matrices. Operutions Research, 53(5):780-798, 2005.
Santiago Paternain, Luiz Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained rein- forcement learning has zero duality gap. In Advances in Neural Information Processing Systems (NeurIPS), pp. 7553-7563, 2019.
Tu-Hoa Pham, Giovanni De Magistris, and Ryuki Tachibana. Optlayer-practical constrained opti- mization for deep reinforeement learning in the real world. In 2018 IEEE International Confer- ence on Robotics and Automation (ICRA), pp. 6236 6236-6243. IEEE, 2018.
Anders Rantzer. A dual to Iyapunov's stability theorem. Systems and Control Letters, 42(3):161- 168, 2001.
Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking Safe Exploration in Deep Reinforce- ment Learning. 2019.
Makoto Sato, Hajime Kimura, and Shibenobu Kobayashi. Td algorithm for the variance of return and mean-variance reinforcement learning. Transactions of the Japanese Society for Artificial Intelligence, 16(3):353-32,, 2001.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference machine learning, pp. 1889-1897, 2015.
10

---

Under review as a conference paper at ICLR 2021
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Jie Tang, Arjun Singh, Nimbus Goehausen, and Pieter Abbeel. Parameterized maneuver learning for autonomous helicopter flight. In 2010 IEEE International Conference on Robotics and Au- tomation, pp. 1442-1148. IEEE, 2010.
Ziyang Tang, Yihao Feng, Lihong Li, Dengyong Zhou, and Qiang Liu. Doubly robust bias reduction in infinite horizon off-policy estimation. arXiv preprint arXiv:1910.07186, 2019.
Chen Tessler, Daniel J Mankowitz, and Shie Mannor. Reward constrained policy optimization. In International Conference Learning Reprexentations (ICLR), 2019.
Andrea Lockerd Thomaz, Cynthia Breazeal, et al. Reinforcement learning with human teachers: Ev- idence of feedback and guidance with implications for learning performance. In Aaai, volume 6, pp. 1000-1005. Boston, MA, 2006.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEF/RSJ International Conference Intelligent Robots and Systems, pp. 5026-50333 IEEE, 2012.
Arne Traue, Gerrit Book, Wilhelm Kirchgässner, and Oliver Wallscheid. Towards reinforcement learning environment toolbox for intelligent electric motor control, 2019.
Larry Wasserman. Lecture notes in statistical methods for machine learning, 2019. URL http:: // /www atat cmu.
pdf Online material,
ast visited on 2019/08/25.
Tsung- Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter J. Ramadge. Projection-bass -based constrained policy optimization. In International Conference on Learning Representations, 2020.
Weitao Yang. Direct calculation of electron density density- theory. Physical review letters, 66(11):1438, 1991.
A PROOFS STATEMENTS AND THEOREMS
In this section, the proofs omitted in our main paper are provided. We will prove the equivalent ex- pression of the state density function, the duality between density function optimization and Q func- tion optimization in the unconstrained case (Theorem [ and constrained case (Theorem 2) as well the optimality of the proposed primal-dual algorithm for DCRL (Proposition

---

Under review as a conference paper at ICLR 2021
A.1 EQUIVALENT EXPRESSION OF THE STATE DENSITY FUNCTION
In Section 3.1 we point out that the state density function P3 has two equivalent expressions. We start from Equation equation
I
and derive another expression:
(3)
Σ t=0
PPs S/ s" ~
Pss 8/ 00 Φ) + Σ 7dth P(s' s|T, 5 ~
1=1
20
=(s) Σ
1t1p 44 = x))
(ss) + Σ
7 P 3/T,,0
t=
(6) +7 a(als))P((s 8) Σ
P = -'T ~ o)dads'
1=0
(6)) + / {(als))Pa(s's))))
A.2 PROOF OF THEOREM
The Lagrangian of is
L [ (s, (s,
J/ ((s.a) (s.0) - ((lls)(((s) +7 1 Par(s', (d' ddddddd) dads (7)
where p:: 8 x A - R the Lagrange multiplier. The key step is by noting that
J / (a s))p (6', a da'd dadss
((dd)) s')p" (s, a)da' ds' dads (8)
Then by rearranging terms, the Lagrangian becomes
L = ((s) / pls, ()
r((,,) (u(s,o)-r(ssa) / (3)() (u(s.o)
Pa(s,5') / <(a'\s')((s d')dd' ds') dads (9)
By the KKT condition and taking Q = μ. the optimality condition satisfies equation 4 exactly, and when optimality condition is attained, Jī J
A.3 PROOF OF THEOREM 2
The solution to the primal problem is the optimal policy for the modified MDP with reward r r 0+. which means π is the optimal solution to:
max / (s)) / Q (s))))a( Q,7 (= a) r(), + (s) - (4(s) +7 / Po(e.s') T(o')s')Q"'') (d''dd (11)
(10)
12

---

Under review as a conference paper at ICLR 2021
Source
Reference state trajectories
4
Action
Convertor
Agent
Sensors
Men
Rotor
(8) Direct current series motor
(b) A farmland Saskatchewan, Canada
Figure 5: Illustration of the electrical motor control and drone application environments. (a) Electrical motor control: Control the motor to follow the reference trajectories and avoid motor overheating, (b) Agricultural pesticide spraying: Control the drones spray pesticide over farmland which is divided into five parts and each requires different densities of pesticide.
According to Theorem also the optimal solution to:
P.m max / p. (s))))((s))))+
-+(())dddds
(12)
s.t. (s) x(lss) (0(s) + J Par (s d'' ds'
(13)
Therefore, for any feasible policy x' the following inequality holds:
J (1 +o a a+ (s)) 2
J ph (s, (r)())))) (s) (+())ddads -o_(s))o4(())ddds (14)
By complementary slackness, if a (8) 0, then (s) Pm)n(s). The same applies a+ and Pmaz. Since p. (s) 2 Pmni (s) and p (s) S Pmaz (s), we have:
I (s. a (s)) S [ 0% (s, a (a)
(15)
Then we use equation
15 to eliminate the a- (8) - o (8) in 14 and derive:
J p. (s), a)dads 2 1 Pe (s, (5,a)r(s, a)dads
(16)
which means x is the optimal solution maximizing Jj among all the solutions satisfying the density constraints. As result, is the optimal solution to the DCRL problem.
A.4 PROOF OF PROPOSITION
Note that when Algorithm D converges and the KKT conditions are satisfied, the policy that Algo- rithm I founds is the optimal solution to the primal problem (6) because the algorithm explicitly solves in Line Thus, by Theorem 2] the policy the optimal solution to the DCRL problem.
B SUPPLEMENTARY EXPERIMENTS
In this section, provide compare with RCPO (Tessler et al. 2019) and the unconstrained DDPG (Lillicrap et al.] 2016)) which serves the upper bound of the reward that can be achieved if the constraints are ignored.
studies that not covered in the main paper. We mainly
13

---

Under review as a conference paper at ICLR 2021
Teraperature dersity (DCRL)
Temperature density (RCPO)
1.0
lemperature density (DOPG)
0.8
Max allowed density
0.8
Max allowed density
0.8
Max allowed density
0.4
0.4
0.4
0.0
0.0
0.0
0.0
0.1
0.2
0.3
0.4
0.0
0.1
0.2
0.3
0.4
0.0
0.1
0.2
0.3
0.4
Motor temperature
Motor te temperature
Mator temperature
Kgguir velcity
Reference
Trajectory (DCRL)
Tajectory (RCPO)
Trjjectry (DDPG)
0.5
0.5
0.
0.0
0.00
0.25
6.75
1.00
0.00
0.25
0.50
0.75
3.00
0.00
0.25
0,50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Figure 6: Density curves of motor's 's temperature when following wwwtooth-wave trajectories using different methods. The temperature is relative to and also normalized using the environment temperature.
Phote
Phase
0
Action
00.
Action
0.7
Phone
0.0
0.0
0.0
0.3
0.3
Reference
'emper sture
Reference
"emperature
Reference
temperatur
0.5
0.5
0.5
(a) DCRL
(b) RCPO
DDPG
Figure 7: Visualization of the behavior of three methods in the safe electrical motor control task.
B.1 SAFE ELECTRICAL MOTOR CONTROT.
The safe electrical motor control environment is from Traue et al. (2019) and is illstrated in Fig- (a). The objective is to control the motor so that its states follow a reference trajectory and the same time to prevent the motor from overheating. The state space S c I6 and consists of six variables: angular velocity, torque, current, voltage, temperature and the reference angular velocity. The action space A C IR. is the electrical duty cycle that controls the motor power. The agent out- puts duty cycle at each time step to drive the angular velocity close to the reference. When the reference angular velocity increases, the required duty cycle will need to increase. As a result, the motor's power and angular velocity will increase and cause the motor temperature to grow.
The algorithms are trained and tested using sawtooth-wave reference trajectories. Results for other types trajectories are presented in the supplementary material. Figure shows that our approach successfully controls the temperature density below the given threshold. Unconstrained DDPG does not consider the temperature and only minimizes the difference between reference and measured angular velocity. Therefore, the motor controlled using unconstrained DDPG has significant vio- lation of the required temperature density when the motor temperature high. RCPO manages to avoid the high temperature but fails suppress the density completely below the threshold. As comparison, our method manages to successfully control the temperature density completely below the required threshold.
To gain some insight on the different performance of the three methods, we visualize the trajectories and actions (duty cycles) taken different temperatures and reference angular velocities in Figure In Figure 7 (a). The trajectory using DCRL can be divided into three phases. In Phase 1, as the reference angular velocity grows, the duty cycle also increases, so the motor temperature goes up. When the temperature is too high, the algorithm enters Phase where it reduces the duty cycle to control the temperature, even though the reference angular velocity remains high. As the temperature goes down, the algorithm enters Phase and increases the duty cycle again to drive the motor angular velocity closer to the reference. Figure (b), when the temperature high, the RCPO algorithm will stop increasing the duty cycle but will not decrease it Algorithm does. So the temperature remains high and thus the density constraints are violated. In Figure (c), the unconstrained DDPG algorithm continues to increase the duty cycle in spite of the high temperature.
14

---

Under review as a conference paper at ICLR 2021
Temperature density (DCRL)
1.0
Temperature density (RCPO)
lemperature dersity (UDPS)
0.8
Max allowed dersity
0.8
Max allowed density
0.8
Max alloved density
0.8
0.4
0.4
0.4
0.2
0.2
0.0
0.0
0.0
0.0
0.1
0.2
0.3
0.4
0.0
0.1
0.7
0.3
0.4
0.0
0.1
0
0.3
0.4
Mator temperature
Motor temperature
Motor temperature
Anguarr velocty
1.0
Reference
Trajectory (DCRL)
Tejectory (RCPO)
Trijectory (DDPG)
0.5
0.0
0.0
0.0
0.00
0.75
0.75
Figure 8: Density curves of the motor's temperature when following asymmetric sine- trajectories using different methods, which are trained with sawtooth-wave trajectories. None of methods have seen the asymmetric sine-wave trajectories during training. The temperature is relative to and also normalized using the environment temperature. DDPG almost perfectly follows the angular velacity trajectory but violates the density constraints on nigh-temperature states. RCPO slightly violates the density constraints. DCRL is able to follow most part of the trajectories and completely satisfy the constraints.
Temperature density (DCRL)
Temperature donsity (RCPO)
Temperature density (DDPS)
Snsperctur dengty
0.0
Max allowed density
0.8
Max allowed dansity
0.8
Max allowed density
0.4
0.4
0.4
0.0
0.0
0.0
0.0
0.1
0.7
0.3
0.2
0.0
0.1
0.2
0.3
0.4
0.0
0.1
02
0.3
0.4
Motor temperature
Mator temperature
Motor temperature
Areular velocty
1.0
Reference
1.0
Prajctory (MEBI)
Trajcctor (RCPO)
Trojectry (DDPG)
0.00
0.25
0.50
0.75
1.00
0.01
0.25
1.00
0.0
0.0
Time
Tirm
Figure 9: Density curves of the motor's temperature using different methods trained and tested with staircase- wave trajectories. The temperature is relative to and also normalized using environment temperature. The unconstrained DDPG violates the temperature constraints while perfectly following the trajectory. RCPO hetter than the unconstrained DDPG in terms of restricting the temperature, but its angular velocity trajectory is not stable DDPG. DCRL. can successfully control the temperature meet the constraints.
To examine the generalization capability of our method, here we train on the sawtooth- wave trajec- tories but test asymmetry sine trajectories that not seen by Algorithm Sraritthmmeeoooo before (Figure (3) To make the experiments more diverse, we also train and test the methods using staircase-wave trajectories (Figure 9). Note that all the configurations of DCRL. method are the three experiments (Figure reference trajectory.
in the and we did not tune any of the hyper-paramene parameters for each type of
In order to demonstrate the difficulty of tuning cost functions to satisfy the constraints with the RCPO method, we present the results of RCPO with different hyper-parameter configurations of the cost function (Figure 10). Throughout the experiment, RCPO uses the cost function max(0, (s m where s is the temperature variable under state s. The cost function is positive when exceeds y). 1 = 0.20 for RCPO, / 0.23 for RCPO-V2, " 0.17 for RCPO-V3 and 7 = 0.16 for RCPO-V4, V4. For fair comparisons, other parameters of these three variants of RCPO remain unchanged. It is clear that SCPO-V4+ is only slightly different from RCPO-V3.
As is shown in Figure S even the testing reference trajectories are unseen, our approach still manages to control the temperature density below the threshold. The sawtooth-wave trajectories are piece-wise linear, which are for training. By contrast, the asymmetric sine-wave trajectories are nonlinear curves, which are for testing. Figure shows the generalization capability from linear to nonlinear reference trajectories without any re-training. Figure 9 while the angular veloc- ity trajectory of RCPO shows unstable high-frequency oscillation, DCRL can stabilize the angular
15

---

Under review as a conference paper at ICLR 2021
Tamperature density (RCPO-V2)
1.0
Temperature density (RCPD-V3) Max allowed dansity
Temperature density (RCPO-V4;
0.03
Max allowed dansity
0.8
0.8
Max allowve dansity
0.6
0.4
0.4
0.4
0.2
0.0
0.0
0.0
0.0
0.1
0.2
0.3
0.4
0.0
0
022
0.3
0.4
0.0
0.1
0.2
0.3
0:4
Motor temperature
Motor temperature
Motor temperature
Anguler valokk
1.0
1.0
10
Reference
Trajctory (RCPO
Trajectory (RCPO V3I
Trajectory (RCPO V4)
05
0.5
0.5
0.5
0.00
0.25
0,50
0.75
1.00
0.00
0.25
0.50
0.75
1:00
0.30
0.25
0.50
0.75
1,00
0.00
0:25
0,50
0.75
1.00
Figure 10: Density curves of the motor's 's temperature when following staircase- wave trajectorics using the RCPO method with different configurations of the cost function. It is still possible to achieve satisfactory performance (RCPO-V3) through extensive cost function tuning. However, though RCPO-V4 is only slightly different from RCPO-V3 in terms of hyper-parameters This observation suggests that could be difficult to design and tune the cost functions to satisfy the density constraints.
completely fails to follow the reference trajectory.
velocity and keep the temperature density completely below the threshold. Unconstrained DDPG does not take into account the temperature density constraints and thus causes the motor to overheat. All these scenarios show that our method can constantly outperforms RCPO and the unconstrained DDPG in terms of guarantceing satisfaction of constraints and generalization capability.
Different configurations in the cost (negative reward) function of RCPO will yield different results, and we show that could be difficult to tune the cost functions to satisfy the density constraints. In Figure [0] though it is still possible for RCPO to satisfy the density constraints by tuning the hyper- parameters of the cost function (as (3), a small perturbation would have an unexpected negative effect. The hyper-parameter of RCPO-V4 is only slightly different from that of RCPO-V3, but RCPO-V4 V4 completely fails to follow the reference trajectory. A larger 7) will incur a heavier punishment for high temperature states, but tuning 7) could be difficult. Moreover, when the refer- ence trajectory changes, the feasible 1j also changes, making the tuning process time-consuming. In comparison, we did not tune any parameter of the DCRL method for each reference trajectory, which indicates the robustness and generalization capability of DCRL when applied to new scenarios.
B.2 AGRICULTURAL SPRAYING DRONE
We consider the problem of using drones to spray pesticides over a farmland simulation. Consider the area in Figure 5 (b). The drone starts from the top-left corner, flies over the farmland spraying pesticides, and stops at the bottom-right corner. At each timestep. the agent outputs an acceleration parallel to the ground and then the drone moves horizontally at fixed height. The drone has a stant spraying speed, which means when the drone moves faster, there would be less pesticides on the land that the drone passes over. At each moment, the pesticides sprayed by the drone uniformly cover an area centered at the drone with diameter equals to 0.02 times the side length of the farm- land. Two constraints are (1) the pesticide density of each part of the land is within the predefined minimum and maximum pesticide density requirements, and (2) the density (distribution) of drone velocity below a predefined threshold, which is to prevent dangerous high-speed movement.
As is shown in Figure 11 for each method we evaluate the area that satisfies pesticide density con- straints, the time consumption and the velocity density. While RCPO and our method demonstrate similar performance in terms of controlling the pesticide density and velocity density, our method requires fewer time steps to finish the task. The unconstrained DDPG algorithm takes less time, but cannot satisfy the requirement on pesticide density or velocity density. More experiments on the agricultural spraying problem are presented in the supplementary material.
We also examine the methods with different pesticide density requirements to assess their capability of generalizing to new scenarios. For the farnland shown in Figure 5 (b), from area 0 to 4, the minimum and maximum pesticide density are (1, 0, O, 1, 1) and (2, 0. 0. 2, 2) respectively. In this supplementary material, we evaluate with two new configurations. In Figure [2] the minimum and maximum density are set (0. 1, 1, and (0, 0,2) 2) from area 0 to 4. In Figure 13 the
16

---

Under review as a conference paper at ICLR 2021
1.0
50
0.1
(aldity dendily (DCAL)
0.6
40
0.0
concumption
20
0.3
Settsf
0.4
20
8.0
0.2
10
8.3
derrdyy (D3P))
0.0
0.0
DCAL
RCPO Method
DDPG
DCAL
ACPO Method
DDRG
0.0
0.2
0.4
0.6
0.5
1.0
Velocity
Percentage of the entire area that satisfies the pesticide density requirement. Middle: Time consumption in steps. Whiskers in the left and middle plots denote confidence intervals. Right: visualization the velocity densities using different methods.
Figure 11: Results of the agricultural spraying problem. Left:
minimum and maximum density are set to 10,0,1,1,0) and (0, 0, 2, 2) from from area 4.
Other configurations remain the same.
Time consumotion (stepi))
5g
0.1
Wiicity deadit
0.8
20
0.0
0.1
Sattredd
0.4
20
Veleiity
0.0
0.1
Vellcity :5000)
0.0
0.0
DCRL
RCPO
DDPG
DCRL
RCPO
DORG 0.0
0.2
0.4
0,0
0.3
1.0
Method
Methoc
Velocity
Figure 12: Results of the agricultural spraying problem with minimum pesticide density (0, 1, 1, 0, 0) and maximum density (0, 0, 2) from area Left: Percentage of the entire area that satisfies the pesti- cide density requirement. Middle: Time consumption in steps. Whiskers in and middle plots denote confidence intervals. Right: visualization of the velocity densities using different methods.
1.0
50
0.1
slowed
densty
0.6
consumpton
0.1
weddy (RCP))
20
6.n
0.2
DCRL
ACPO Method
DDPG
DCRL
DDPG
0.2
0.6
0.8
100
Method
lociityy
Figure 13: Results the agricultural spraying problem with minimum pesticide density (0, 0, 1, 1) and maximum density (0, 2, 0) from area 0 to 4. Left: Percentage of the entire area that satisfies the pesti- cide density requirement. Middle: Time consumption in steps. Whiskers in the left and middle plots denote confidence intervals. Right: visualization of the velocity densities using different methods.
In Figure 12 and 13 DCRL and RCPO demonstrates similar performance controlling pesticide densities to be within the minimum and maximum thresholds, while DCRL demands less time to finish the task. DDPG only minimizes the time consumption and thus requires the least time among the three methods, but cannot guarantee the pesticide density satisfied. In terms of the velocity control, both DCRL and RCPO can avoid the high-speed movement. These observations suggest that when both DCRL and RCPO finds feasible policies satisfying density constraints, the policy found by DCRL can achieve lower cost or higher reward defined by the original unconstrained problem, which is the time consumption of executing the task this case study.
B.3 EXPRESS DELIVERY SERVICE TRANSPORTATION
An express delivery service company has several service points and a ship center in a city. An ex- ample configuration is illustrated in Figure 14 (a). The company vans to transport the packages from each service point to the ship center. The vans start from some service points following an initial distribution, travel through some service points and finally reach the ship center. The cost is
17

---

Under review as a conference paper at ICLR 2021
(a) Network of service points (gold) and ship center (red)
Density obtained using O-Leaming without constraints
example of the express delivery service company's transportation network with one ship center service points. Left: The vans start from service points (initial states) bounded by squares with equal probability, then visit other service points following a transition probability (policy), and finally reach the ship center (goal). Right: The standard Q-Learning method finds a policy that drives the vans directly to the goal without visiting any other service points, which minimizes the cost (traveling distance). The sizes of gold nodes represent state density.
Figure 14:
Table 1: Results of the express delivery service task. The maximum allowed running time solve for feasible policy is 600s. The cost the expectation of traveling distance from initial states to the goal.
Density space
Method
Pmin
0.1
Penin
Panin
0.5
Solved
Time (s)
Cost
Solved
Time (s)
Cost
Solved
Time (s)
Cost
P. E R210
CERS
True
163.69
3,85
True
183.81
5.36
True
466.32
5.12
DCRL
True
1.35
2.91
True
2.05
2.66
True
4.31
4.28
Ps E 2200
CERS
True
227.15
5,80
True
527.26
6.00
False True
Timeout
DCRL
True
3.41
5.58
True
3.99
6.16
5.28
Ps 100
CERS
True
161.62
10.26
False True
Timeout
False True
Timeout 153.86
DCRL
True
3.53
10.23
116.24
12.13
14.06
18

---

Under review as a conference paper at ICLR 2021
formulated as the traveling distance. The frequency that each service point is visited by vans should exceed a given threshold in order to transport the packages in the service points to the ship center. Such frequency constraints can be naturally viewed density constraints. A policy is represented as the transition probability of the vans from one point to surrounding points. The optimal policy should satisfy the density constraints and minimize the transportation distance.
Instead of comparing to methods that exert constraints on cost or value functions in the three case studies in Section 4 this case study is proposed further understand Algorithm I [ndd its key steps. In Algorithm T Line [ our approach adds Lagrange multipliers to the original reward in order to compute a policy that satisfies density constraints. The update of Lagrange multipliers follows the dual ascent in Algorithm Line 9 and [0] which is key to satisfying the KKT conditions. In this experiment, we try to update the Lagrange multipliers using an alternative approach and see how the performance changes. We replace the dual ascent with the cross-entropy method, where a set of Lagrange multipliers Σ 02 02, "..] are drawn from an initial distribution a (o) and utilized to adjust the reward respectively, after which set of policies [T1, 22 T3, ...] I are obtained following the same procedure
Algorithm [ Line S and 6 A small subset Σ whose т has the least violation of the density constraints chosen to compute new distribution Z(r), which is utilized to sample a new Σ. The loop continues until we find a whose т completely satisfies the density constraints. We call this cross-entropy reward shaping (CERS). We experiment with 10D, 20D and 100D state spaces (corresponding to 10, 20 and 100 service points in the road network), whose density constraints lie in 1R 12200 and IR 100 respectively. The density constraint vector Pmin S + IR is set to identical values for each state (service point). For example, Prxin = 0.1 indicates the minimum allowed density at each state is 0.1. In Algorithm Line 6 use Q- Learning to update the policy for both DCRL and CERS since the state and action space are discrete.
From Table there are two important observations. First, our computational time of finding the policy is sigmificantly less than that of CERS. When P. E R and Pmin 0.1, our approach is least 100 times faster than CERS on the same machine. When Ps E 100 and Pmin 0.5, CERS cannot solve the problem (no policy found can completely satisfy the constraints) in the maximum allowed time (600s), while our approach can solve the problem in 153.86s. Second, the cost reached by our method is generally lower than that of CERS, which means our method can find better solutions in most cases.
Autonomous electric vehicle routing in Manhattan, New York City. The objective is to control the electric vehieles to drive the grey lines roads and reach red nodes goals. The left and right figures represent two scenarios where the goal sets are different. Vehicles can be charged the gold nodes as fast charging stations. All vehicles should maintain energy levels while avoiding congesting the charge stations.
Figure 15:
B.4 AUTONOMOUS ELECTRIC VEHICLE ROUTING
In the autonomous electric vehicle routing task, we evaluate the methods in two new settings in addition to the one presented in our main paper. As shown in Figure [5] the goal sets (red nodes) different from Figure 4.2 The number of nodes and fast charging stations remain the same.
In Figure 16 three approaches exhibit similar performance in maintaining energy levels and avoiding running into low-energy states. Nevertheless, only DCRL succeeds in preventing the congestion in the fast charging stations by suppressing the vehicle density at each fast charging stations below the density constraints. RCPO is better than the unconstrained DDPG in terms of reducing the vehicle
19

---

Under review as a conference paper at ICLR 2021
0.0
0.0
0.6
Energy density (DCRL)
Energy density (ACP))
Energy density (DDPG)
0.5
Max allowed densty
0.5
Max allowed density
0.5
Max allowed density
Energy Senatty
0.4
04
0.2
0.1
0.3
0.1
0.0
0.0
0.0
Rermiined energy
Rerniined vy
Remained
Max allowed density
Max allowed donsity
Max allowed density
Vehicee density (DCRL)
Vehicle density (RCPO)
vehicle density (DDRG)
0.10
0.30
0.10
Whide
0.05
0.05
0.05
0.00
0.00
0.00
Tast
Fast charging stabons
Fest charging stations
Figure 16: Density curves of the autonomous EV routing in Manhattan, with target locations shown on the left of Figure [S] The first row are the energy density and the second row are the vehicle density at each charging station using different algorithms (left to right: DCRL. RCPO, DDPG). Since there are too many charging stations, those with density lower than half of the threshold for all the three methods omitted. Only 15 charging stations are kept in the second row. The error whiskers represent two times of the standard deviations.
0.5
0.6
0.6
Energy density (DCRL)
Energy denaity (RCPO)
Energy density (DDPG)
0.5
Max allowad densty
0.5
Max allowad density
0.5
Max allowed dencity
Energy develty
0.4
0.4
0.2
0.1
0.1
0.1
0.0
0.0
0.0
Remeined energy
Remeined energy
Remeined
0.15
0.15
0.15
Nax allowed density
Max allowed density
Max sllowed density
vehicee density (DCRL)
Vehicle density (RCP0)
Vehicee density (DDPG)
0.10
0.30
0.10
0.05
0.05
0.05
0.00
0.00
0.00
FAst charging stations
Fast charging stations
Fast tharging stations
Figure 17: Density curves of the autonomous EV routing in Manhattan, with target locations shown on the right of Figure [5] The first row are the energy density and the second row are the vehicle density at cach charging station using different algorithms (left right: DCRL, RCPO, DDPG). The error whiskers represent two times of the standard deviations. Note that DDPG violates the density constraints on low-energy states.
density, but still cannot keep the density completely below the thresholds. In Figure 17 DCRL and RCPO demonstrates similar performance in avoiding low-energy states, but DDPG violates the density constraints on low-energy states. This is mostly because DDPG chooses relatively short charging time in this scenario, which consistent with the fact that DDPG only slightly violates the constraints on vehicle density at fast charging stations. As for the time consumption to finish the task, DCRL, RCPO and DDPG take 64.32, 60.89 and 58.40 steps on average to reach the goals shown in the left of Figure 15 and 56.31, 59.47 and 54.19 steps on average to reach the goals shown in the right of Figure 15 DDPG minimizes the traveling distance and thus requires the least amount of traveling time, while DCRL shows the best performance in satisfying the vehicle density constraints at fast charging stations.
B.5 SAFE GYM
In this section, we experiment with the Safe Gym (Ray et al. (211) and compare with CPO (Achiam et al. 2017) and PPO (Schulman et al. 2017) with Lagrangian (PPO-L). Both the CPO and PPO- L are implemented by Ray et al. (2019) We consider three environments in Safe Gym, including PointGoal. PointButton and PointPush. In PointGoal, the point agent aims navigate to a goal while avoiding hazards. In PointButton, the point agent aims to press the goal button and avoid hazards. The agent will be penalized if it presses the wrong button. In PointPush, the agent is expected to
20

---

Under review as a conference paper at ICLR 2021
push box to the goal position and avoid hazards. A detailed description of the environments be found in Section 4 of Ray et al. (2019).
PointGeal1-v0
PointButton1-v0
PointPush1-v0
35
DCRL
DCRL
30
CPO
CPO PPO-L
CPO PPO-L
Average retum
25
PPO-L
Average retum
Averaie retum
10
20
20
8
10
0
200 400
600
600
1000
0
200
400
600
800
1000
200
400
600
800
1000
Number of policy updates
Number of policy upcates
Number of policy updates PointPush1-v0
PointGoall vo
PointButton1
DCAL
DCAL
DCRL
Constraint valuee
CPO
Conutrainss value
CPO
Constraint value
CPO
PPO-L
MPO-L
PPO-L
40
40
40
30
20
20
200 400
600
800
1000
200
400
600
800
1000
200
400
600
800 1000
Number of policy updates
Number of policy updates
Number policy updates
Results Safe Gym (Ray man et al. 2017) with Lagrangian (PPO-L.) The solid lines are the mean values of 10 independent runs. The first row shows the average return and the second row shows the constraint values. The constraint values expected to be below the dashed lines that represent the thresholds.
Figure 18:
2019)
comparing CPO (Achiam
2017 and PPO (Schul-
Results are presented in Figure 18 In the PointGoal environment, all the three methods can satisfy the constraints, while DCRL can achieve a higher average return comparing other methods. In the PointButton environment, CPO fails to satisfy the constraint. In the PointPush environment, it is hard for all the methods to satisfy the constraints because the pushing task is more difficult than the goal reaching task and button task. Overall, DCRL shows the highest reward and the least violation of the constraints among the three methods.
C DISCUSSION ON KERNEL DENSITY ESTIMATION
Eximmiionn with Spareee hare samed
Linar batnel
Esimu.io an Linner kanmal
0.150
0.125
0.129
0.100
0.100
0.050
0.025
0.025
0.000
0.000
-.00
-0.3
0.0
0.3
1.0
30
15
20
-1.0 -0.3
0.0
3.5
1.0
10
20
(8)
Figure 19: Empirical analysis on kernel density estimation with different kernels and bandwidths. We used the Epanechnikov kernel (visualized in (a)) and the linear kernel (visualized in (c)). We estimate the state density w.r.t. the horizontal distance to origin in the CointeCircle environment that used Section The densities are estimated with 1000 samples.
In Section 3
presented effective way to obtain the density function using kernel density estimation when the states are continuous. In this section, we present both theoretical analysis of kerne density estimation and experimental result with different kernels and bandwidth and evaluate their influence on density estimation. There exist many results about the accuracy of kernel density estimation, quote the following lemma from WWaserran 2019
21

---

Under review as a conference paper at ICLR 2021
Lemma 1. Let [..,h), h1] be the bandwidth of the kernel with dimension d. Let ps be the kernel density estimation of Ps. then for a Pa E for any fixed O.
Clogn nha + +4ch S
sup FER
- Φ+V
for some constants e and where depends on 6.
2(3,)) 9: D g()) - D'g(()) S || vll,
y = 1, Vx,y
where D D²g(x)=
8a I. and [s| D27 ...
Ei=1 8i.
This adapted from Theorem 9 in (Wasserman 2019), more detail and other bias analysis results therein. Lemmall @ essentially says that if pa is smooth enough and one takes enough samples, the bias of the kernel density estimator can be bounded uniformly in the state space.
We used the Epanechnikov kernel and linear kernel with various bandwidths to estimate the state density w.r.t. the horizontal distance origin the Point-Circle environment that is used in Sec- tion Results are shown in Figure [9] Although the kernels and bandwidths are different (see
Figure 19 (a) and (c)), the estimated densities (see Figure 19 (b) and (d)) are all close to the true
densities (grey curves).
Once the upper bound cp of the density estimation error computed from Lemma we can incor- porate Ep into Algorithm [ and derive Algorithm 2 which is robust under the possibly inaccurate density estimation.
Line 10 we bloat the density thresholds Pman and Pmin to Pmar tp and Pmin + Ep. which guarantee that the density constraints will still be satisfied even when there inaccuracics in density function estimation.
Algorithm Optimization with density constraints under inaccurate density estimation
1: Input MDP M, initial condition distribution é, constraints on the state density Pmaw and Pmins the upper bound cp of the density estimation error
2:
Initialize т randomly, a+ + 0, 0. + 0
3: Generate experience D (s, 80 a, (s) then r and s' are observed}
4: Repeat
5: (s, 8') (s,a, r a 0+ (s), for each (s,a,r,8) in D,
6:
Update policy π using D
7: Generate experience D2 {(s, a, r, s') s a, (s) then and s' observed]
8: Compute stationary density P5 using D
9: T+ + max 11.0+++00 a(pp Pmaz + (p) max(0, + alpmin P + Ep))
10:
11: Until 04 .....p (p= -Mman + tp) = 0, a_ (pmin - 13 + ep) and Pmin S 12 S Pmar
12:
Return n, P.
22


Reviews:
[{"review_id": "nrODnEsW24_", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper proposes to solve constrained RL through the lens of setting constraints on state density, rather than setting constraints on value functions. The main contributions are (1) a proof of the duality between the density function and Q-value function in constrained RL, and (2) a primal-dual algorithm, called DCRL, for solving the constrained density problem.\n\nRecommendation:\nThis paper tackles an important problem, and presents a theoretically-grounded novel perspective on constrained RL. I'm leaning toward accept, but have several suggestions regarding the empirical evaluation, that are detailed below.\n\nPros:\n* The paper is clearly written and well-motivated.\n* It seems easier to express constraints in terms of the state density function rather than Q-values.\n* The empirical evaluation contains a comparison to several state-of-the-art approaches for constrained RL.\n* DCRL shows modest improvements in the experiments, compared to the baselines.\n\nCons:\n* I would like to see a comparison against the simple yet effective baseline of PPO combined with Lagrangian relaxation, with respect to constraints on Q-values.\n* I would like to see results on more challenging constrained RL tasks, where the state density function is harder to estimate, for instance the Safety Gym task suite [1]. These tasks are particularly interesting because CPO (surprisingly) performs worse on them than the simpler PPO-Lagrangian approach. I'm curious whether DCRL would struggle as well.\n\nComments/questions regarding notation:\n* Using $P_a(s, s')$ and $R_a(s, s')$ in the definition of an MDP (Section 2) is odd; I recommend using the typical notation of $P(s, a, s')$ and $R(s, a, s')$.\n* In the definition of MDPs, $V^\\pi(s)$ is incorrectly referred to as _reward_ / _total reward_, but it should instead be referred to as the _return_ or _expected cumulative discounted reward_.\n* It's not clear that the $[0, \\infty]$ for the density function $\\rho$ corresponds to $t$ (in the first sentence of the Density Functions section).\n* Why are there two $s$'s in $\\rho_s^\\pi(s)$ (e.g., in Equations 1 and 2). Should the subscript be a $\\gamma$ instead?\n* What does it mean to \"linearly interpolate\" $\\sigma_+$ and $\\sigma_-$ (at the end of Section 3.3)?\n\n[1] Ray et al. Benchmarking Safe Exploration in Deep Reinforcement Learning. 2019.", "extra_scores": {}, "extra_text": {}}, {"review_id": "bgmwfYovPyW", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studied density constrained reinforcement learning (DCRL), which compared with standard RL has constraints on the stationary state distribution. It proposes a primal-dual optimization method and proves its optimality. \n\n\nThe theoretical analysis in this paper assumes $\nP_a(s^\\prime, s)$ is perfectly known whenever needed.  In fact, in this case formulations (3), (4), (5), (6) are simple deterministic convex (linear) optimization (regardless if density constraints are introduced or not).  The duality $J_d$ and $J_p$ duality follows directly from duality for convex programs.   The developed algorithm, Algorithm 1, is also simple application of (primal)-dual subgradient method for convex programs. If the D_s update and  \\rho_s^\\pi update are done exactly, i.e., assuming perfect knowledge of  P_a(s^\\prime, s), then the theorems in this paper is just simple consequence of well-established convex optimization results. (I looked into the proof in the appendix. It seems the analysis indeed assumes perfect $P_a(s^\\prime, s)$ in the analysis.)\n\nOverall, I think the technical contribution and novelty of this are marginal.", "extra_scores": {}, "extra_text": {}}, {"review_id": "PfAqa48tfX", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The submission introduces the dual formulation of a Constrained MDP optimization. While their algorithm does not guarantee that the constraints are satisfied during learning, the experiments show that they are reasonably respected, and yield high returns.\n\nDespite the typos and approximations I could identify, I found the exposition of the submission very clear, the arguments are convincing, and the experiments are compelling. For all these reasons, I recommend to accept it. I rate my confidence low because I have some doubts about the novelty of Theorems 1 and 2.\n\nMy main regret is the lack of discussion of the results, both on the theoretical and empirical side. Indeed:\n- Theorems 1 and 2: isn't it immediate since J_d=J_p? Is it really novel?\n- Proposition 1: I'm surprised the failure modes of Proposition 1 are not more discussed. How can it not converge? Can't we guarantee monotonic improvement? Likewise, how can it converge to an unfeasible solution? Can't we enforce the feasibility during the iteration? Does it only happen when no feasible solution is ever encountered?\n- Experiments: what explains the apparent superiority of the primal-dual formulation as opposed to the other algorithms? What are their failure modes? Too conservative? Not safe enough? Does it depend on the setting of some hyperparameters? Isn't it simply because the constraint is defined on the density level and that Algorithm 1 is the only one designed to solve this?\n\nTypos and minor comments:\n- P_a and R_a are SxS->_\n- I feel that straightening the d, like with \\dd from physics package would make the integrals more readable.\n- why is the density function defined as [0,\\infty)xS->R_>0, isn't [0,\\infty)=R_>0? What is it used for? Shouldn't it be simply S->R_>0?\n- I would advise to rename \\rho_s to \\rho, because s is used as a variable everywhere, for instance in Eq. 2 \\rho_s(s') looks like it depends on s.\n- equation 3 \\tho_s^\\pi should be just \\rho.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2XLWwTZA6e5", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors explored the duality between density function and value function in the setting of density constrained RL. Based on this, the author proposed a new safe constrained policy optimization algorithm by jointing optimizing policy and lagrangian multipliers of the density constraints, with an extra effort to estimate the stationary state density of current policy $\\pi$ using kernel density estimation. The empirical results demonstrate that the proposed algorithm  is effective in several mujoco benchmark and  autonomous electric vehicle controlling.  I believe exploring the duality between density function and value function in the  setting in density constrained reinforcement learning is new, and may be helpful in safe reinforcement learning. \n\nFollowings are my detailed questions and comments:\n\n- I have a major concern about estimating the marginal (or stationary) state function of the policy $\\pi$. The author use kernel density estimation to estimate $\\rho(s)$, which I think deserve more discussion in this paper, and at least some empirical experiments should be conducted to verify its accuracy. Moreover, since the estimation requires to use kernels, it would be good to see the empirical results of choices of kernels and bandwidth of the kernel. \n\n- All the derivation and the stop criterion is based on infinite number of samples, which will not guarantee that the constrain is satisfied using finite mc samples to estimate (since you don't have the transition, you can only use samples to estimate). Will there be any guarantee that the exact estimation of density and constrain is upper bounded by some empirical estimation, such that we can use mc sampling to estimate the density or constraints?\n\n- The duality between the density function and value function is well-known in the community, and has drawn great attention recently in the policy evaluation community [1, 2, 3, 4], which I think the authors should have some discussion on this in the related work,  and to see if the techniques can be used to estimate the density functions.\n\nOverall I think the paper proposed a new perspective for density constrained rl, which I think is interesting and is publishable if my above concerns are well addressed. \n\n--------------------\nI will update my scores if my questions are addressed:)\n\n[1] Nachum, Ofir, et al. \"Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections.\" Advances in Neural Information Processing Systems. 2019.\n\n[2] Tang, Ziyang, et al. \"Doubly robust bias reduction in infinite horizon off-policy estimation.\", ICLR 2020.\n\n[3] Uehara, Masatoshi, Jiawei Huang, and Nan Jiang. \"Minimax weight and q-function learning for off-policy evaluation.\" arXiv preprint arXiv:1910.12809 (2019).\n\n[4] Nachum, Ofir, and Bo Dai. \"Reinforcement learning via fenchel-rockafellar duality.\" arXiv preprint arXiv:2001.01866 (2020).\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers raised several theoretical and empirical questions about the paper. During the rebuttals, the authors seem to  successfully address the experimental issues, in particular those raised by Reviewers 1 and 2. However, the theoretical concerns have mainly remained unanswered. Reviewer 2 has a major concern about the convergence of Algorithm 1, both Reviewers 3 and 4 (in particular Reviewer 3) have several questions about the theoretical analysis and see the technical contribution of the work relatively low. These are not minor issues and require a major revision to be properly addressed. So, I suggest that the authors take the reviewers comments into account, revise their work and properly address the issues raised by the reviewers, and prepare their work for an upcoming conference. 
Decision: Reject