Reconnaissance for reinforcement learning with safety constraints
Authors: Shin-ichi Maeda
Hayato Watahiki
Yi Ouyang
Shintarou Okada
Masanori Koyama
Venue:  (2021)
Keywords: Reinforcement Learning
Safety constraints
Constrained Markov Decision Process

Abstract: Practical reinforcement learning problems are often formulated as constrained Markov decision process (CMDP) problems, in which the agent has to maximize the expected return while satisfying a set of prescribed safety constraints. In this study, we consider a situation in which the agent has access to the generative model which provides us with a next state sample for any given state-action pair, and propose a model to solve a CMDP problem by decomposing the CMDP into a pair of MDPs; \textit{reconnaissance} MDP (R-MDP) and \textit{planning} MDP (P-MDP). In R-MDP, we train threat function, the Q-function analogue of danger that can determine whether a given state-action pair is safe or not. In P-MDP, we train a reward-seeking policy while using a fixed threat function to determine the safeness of each action. With the help of generative model, we can efficiently train the threat function by preferentially sampling rare dangerous events. Once the threat function for a baseline policy is computed, we can solve other CMDP problems with different reward and different danger-constraint without the need to re-train the model. We also present an efficient approximation method for the threat function that can greatly reduce the difficulty of solving R-MDP. We will demonstrate the efficacy of our method over classical approaches in benchmark dataset and complex collision-free navigation tasks.

Under review as a conference paper at ICLR 2021
RECONNAISSANCE FOR REINFORCEMENT LEARNING WITH SAFETY CONSTRAINTS
Anonymous authors Paper under double-blind review
ABSTRACT
Practical reinforcement learning problems are often formulated as constrained Markov decision process (CMDP) problems, in which the agent has to maximize the expected return while satisfying a set of prescribed safety constraints. In this study, we consider a situation model which provides us with a next state sample for any given state-action pair, and propose model to solve CMDP problem by decomposing the CMDP into a pair of MDPs; recomnaissance MDP (R-MDP) and planning MDP (P-MDP). In R-MDP, we train threat function, the Q-function analogue of danger that can determine whether given state-action pair is safe not. In P-MDP, we train a reward-seeking policy while using a fixed threat function to determine the safeness of each action. With the help of generative model, we can efficiently train the threat function by preferentially sampling rare dangerous events. Once the threat function for baseline policy computed, we can solve other CMDP problems with different reward and different danger-constraint without the need to re-train the model. We also present an efficient approximation method for the threat function that can greatly reduce the difficulty of solving R-MDP, We will demonstrate the efficacy of our method over classical approaches in benchmark dataset and complex collision-free free navigation tasks.
which the agent has access to the generative
INTRODUCTION
With recent advances reinforcement learning (RL), becoming possible to learn complex
reward-maximizing policy in an increasingly more complex environment (Mnih et al. 2015 Silver
ctt al. 2016: Andrychowicz et al.) 2018 James et al., 2018 Kalashnikov et al., 2018) 8). However,
difficult in general to assess whether the policies found by a given RL algorithm is physically safe when applied to real world situations. This has long been one of the greatest challenges in the application of reinforcement learning mission-critical systems. In popular setup, assumes Markovian system together with predefined measure of danger, and formulates the problem as a type of constrained Markov decision process (CMDP) problem. That is, based on the classical RL notations in which ग represents a policy of the agent, we aim to solve
max E" [Rhh)] s.t. [Dh)( S.
(I)
where h is a trajectory of state-action pairs, R((h) is the total return that can be obtained by h. and
D(h) the measure of how dangerous the trajectory is. To solve this problem. one must monitor
the value of E" [(h) throughout the training. Methods like (Altman 1999 Geibel & Wysotzki
2005 Geibel 2006: Achiam al.) 2017a| Chow et al. 2018 2019) uses sampling to approximate
E ((h) or its Lyapunov function at every update. However, the sample-based evaluation of the
E (D)) particularly difficult when the system involves "rare" catastrophic accidents, because an
immense number of samples will be required to collect information about the cause of such accident.
This problem can be partially resolved if we can use a generative model to predict the outcome of any given sequence of actions and initial state. Model Predictive Control (MPC) (Maciejowski 2002 Falcone et al. 2007 Wang & Boyd| 2010 Di Cairano et al., 2013 Weiskircher et al.) 2017) uses the philosophy of receding horizon and predicts the future outcome of actions in order to determine what action the agent should take in the next step. If the houure- to consider is sufficiently short and the dynamics is deterministic, the prediction can often be approximated well by linear dynamics,

---

Under review as a conference paper at ICLR 2021
Original Circuit
New Circuit
(a) RP (proposed)
(b)
MPC
(c) DQN with A=O
(d) RP (proposed) (e)
MPC
DON with A=O
X crash
Figure 1: The trajectories produced by the the policy trained by our proposed method ((a) and (d)),
4-step MPC ((b), (c)), and the policy trained with penalized DQN ((c) and (f)). The trajectories on circular circuit were produced by the policies trained on the original circuit. represents the initial position of the agent. The red marks represents the places at which the agent crashed into the wall.
which can be evaluated instantly. However, because MPC must finish its assessment of the future before taking every action, its performance is limited by the speed of the predictions. When we apply MPC to environments with multiple agents and stochastic dynamics, the computational load of prediction especially heavy and can be difficult to finish the prediction in time. MPC requires this computation for each time-step even if the current state is similar to the ones experienced in the past. Meanwhile, if the prediction is done for only a short horizon, MPC may suggest a move to state leading to catastrophe.
an effort to reduce the difficulty in evaluating safeness policies, we propose novel generative model-based approach that looks for solution of a CMDP problem by decomposing the CMDP into a pair MDPs: a reconnaissance MDP (R-MDP) and planning MDP (P-MDP), The purpose of R-MDP is to (1) recon the state space using the generative model and (2) train a baseline policy for the threat function, which is a Q-function analogue of D.
In R-MDP, we use generative model to selectively sample trajectories containing dangerous events, and learn the threat function for the baseline policy in the way of supervised learning. Once obtain a good approximation of the threat function for the baseline policy, we can determine whether a given action is safe at each state or not by just evaluating the threat function. This process does not involve prediction, which that we can increase the set of safe actions by improving the safeness of the baseline policy. In P-MDP, train the reward-secking policy while using the threat function make sure that unsafe actions are not chosen. We may say that P-MDP is a version of original MDP in which the agents are only allowed to select an action from the set of safe policies defined by the threat function. P-MDP can be solved with standard RL methods like DQN (Mnih al. 2015). With our framework, the user freed from the need of monitoring ET [D] throughout the whole training process.
be computationally demanding. We will theoretically show
We will also show that our approach enjoys the following useful properties: 1) If we can find safe bascline policy from the R-MDP problem, the lcarning of P-MDP will always be safe. 2) So long that we define the danger with the same D) function, we re-use the threat function constructed for one CMDP problem to solve another CMDP problem with a different reward function and different constraint threshold. 3) When dealing with a problem with multiple sources of danger, we use basic rule of probability to upper-boune the threat functions by a sum of sub-threat functions, with each summand corresponding to different source of danger each. The property (2) allows us train an agent that can safely navigate circuit irrespective of the course-layou[T we represented the circuit's wall as a of point obstacles, and computed the threat functions for the collision with each obstacle point. The property (3) allows us to find a good reward-seeking policy for sophisticated task like safely navigating through crowd of randomly moving obstacles. Although our method does not guarantee to find the optimal solution of the CMDP problem, there has been any study date that has succeeded in solving a CMDP in dynamical environments as high-dimensional as the ones discussed in this study.
In this experiment,
2 PROBLEM FORMULATION AND THEORETICAL RESULTS
We assume that the system in consideration is discrete-time constrained Markov Decision Process (CMDP) with finite horizon, defined by tuple (S, A, d, P, Po). where is the set of states, A is the set of actions, P(s (efls,,d a) is the density of the state transition probability from to s' when the
2

---

Under review as a conference paper at ICLR 2021
action is a, r(s, a) is the reward obtained by action at state s, d(ss, a) is the non-negative danger of taking action a at state s, and Po is the distribution of the initial state. We use ((ass) to denote the policy IT' 's probability of taking an action at a state Finally, let use 1n to represent the indicator function of an event B. Now we formally present the optimization problem (T.
arg max EAT END (r((se, S.t.Exx EnD 3ld(ss, mi)) S.
where e 2 0 specifies the safety level, 7, B E [0, 1) are the discount factors, and Ex denotes the expectation with respect to P and Po. We use plain E' to denote the expectation with respect to Po-
2.1 PROPERTIES OF THREAT FUNCTIONS AND SECURE POLICIES
In our formulation, we use the following threat function and danger function as danger-analogue of the action-value function and state-value function, respectively.
T-
(s,, = Eny
Σ N=
gh d(sk; ax) 8t, as
- E as)
(3)
We say that a policy 1) is safe if (00) < c. Indeed, the set of safe policies is the set of feasible policies for the CMDP [T. Before we proceed further, we describe several key definitions and theorems that stem from the definition of the threat function. For now, let us consider a time- dependent safety threshold 2, defined at each time and let r any policy. Let us also use æ to denote (Zg...., -T-1). Then the set of (1) x) -sccure actions is the set of actions that are deemed safe by 1) for the safety threshold in the sense of the following definition;
Definition (17, ssecure actions and ) secure states). Let AT {0 (s, s xt
{a;
A (s) =
n A (s, ST. {s S S: ( + f0}.
(4)
BE (O,"..T-II
This (17, xz--scuree set of actions (s) represents the agent's freedom in seeking the reward under the safety protocol created by the policy 17. The set of secure actions for an arbitrary could be empty for some states. (17, -secure states is defined as set of states for which there is non-empty (17, x)- secure actions. If we use supp(p) denote the support of a distribution p, we can use this definition to define set of policies that is at least as safe n. First, let us define the set of distributions,
F*())= - p(:: /. ((a))))(((
(s a)da S (s,
Then the following set of policies are at least as safe as v). Definition (General (17, ax) -secure policies).
IT: {T:; for E ST:", supp(r(-ls)) S (s), otherwise, <--ss) E (s))
(5)
Now, we are ready to develop our theory for determining when given policy is safe. The following theorem enables us to bound 277 (s:) without evaluating the expectation with respect to π.
Theorem 1. For given policy 7) and sequence of safety thresholds =(ro..... TT-1), let be policy in I1% Let us use drv (p. g) to denote the total variation distance between two distributions p and 9. Then for all t E {0, (O....,T T
T-1
(s)) (8) +2
gk
[zk se).
(6)
where 2 = 11..5nnddyy (.)ss))) (t), (s)) is a distance measure the two polices.
The proof of this result practically same logic the one used for Theorem in (Achiam et al., 201 7a) Please see the Appendix for the detail. In practical application, is more convenient to set Tt for all t. If we also bound 2, from above by we obtain the following useful result.
Total variation distance defined ( q(a)) -/2 Σ. lr(a) q(a)]-
3

---

Under review as a conference paper at ICLR 2021
1-8 Corollary 2. If El S let (x² (Fe....,, with x² = =2(c El (so))) policy x is safe if _ (i.e., E S c).
1-ge. Then
The above corollary provides us a safety guarantee for when rj itself is safe. But in fact, if we look inside a smaller subset of u we can guarantee the safety even when itself may not be safe. Definition 3 (177, x) -secure policies). Let greedy-n(aas) = 1 =a=arg ming/ (s,a),
11 = (T; for s E S supp(T((Is)) S A (s), otherwise, r(-ss) greedy-n(-ls)}- (7)
The (n, -s-cure policies 11 indeed a subset of _ because greedy-1) is just the one-step policy improvement from It turns out that we can construct a pool of absolutely safe policies explicitly from T," a) and e alone even when 1) itself is not necessarily safe.
Corollary 3. If E(98)))))))) (so)] I c, by setting x (=2gg.. ... x2,gg with x2 " ((s)))) 1-p2, any policy π E II is safe, i.c. El (so)) Sc..
}
1-9
This result can be derived using a result similar to 6 (See Appendix for the detail). In the next section, we will use I construct a pool of safe policies from which seek a good and safe reward-seeking policy. Now, several remarks are in order. First, if we set / = 1, then x² - 0 as T DO. This is in agreement with the law of large numbers: that is, any accident with positive probability is bound to happen at some point. Also, note that we have A (s) S A (s) whenever g." (s,a) (,, a) for any f. Thus, by finding the risk- maskmminiiizing. 7), we can maximize the pool of safe policies. Whenever we can, we shall therefore look not just for a safe 17, but also for the threat minimizing policy. Finally and most importantly, note that the threshold expression in Corollary 3 is free π. We can use this result to tackle the CMDP problem by solving two separate MDP problems. More particularly, in seeking solution the CMDP problem we can (i) first look for 1) satisfying FI Fi ((sp)cddy""ss))))))))))) (so)) S c, and then (ii) look for safe reward maximizing policy in IT". We will further articulate this procedure in the next section. Hereafter unless otherwise noted, we will use II to denote II 11 and use S (s) to denote 5m.00.., A (s).
3 RECONNAISSANCE-MDD (R-MDP) AND PLANNING-MDP (P-MDP)
In the previous section, we have shown that we can create a pool of safe policies using a bascline safe policy. Also, by training policy to minimize the threat, we can find safe policy that corresponds to a larger pool of secure policies, and we look within this pool to search for a possibly better reward seeking policy. This motivates us to solve two types of MDP problem: the one with the aim of minimizing the threat, and the one with the goal maximizing the reward.
The purpose of the Reconnaissance MDP (R-MDP) is thus to recomoiieer the system prior to the reward maximization process and to look for the threat minimization safe policy 17" that solves
arg min Ey ETD 8t sdd(sr,a)) at)
(8)
Indeed, solution 17" of argmin is not unique, up to freedom the actions on the states unreachable by any optimal policy 77". . For our ensuing discussions, we will chose 17 to be a version whose policy on each unreachable state s* is computed by (8) with initial state being s". If the problem is of infinite horizon, 17" computed from any initial state will be same because of the Markov property.
As process, R-MDP same as the original MDP except that we have a danger function in place of reward function, and that the goal of the agent in the system is to minimize the danger. The following true in general about R-MDP.
Corollary 4. If the set of feasible policies of the original CMDP nonempty, the optimal R-MDP policy 17" is safe. Thus, every policy in II" is safe.
After we solve the R-MDP, the Planning MDP (P-MDP) searches within II" for a good reward- seeking policy n². The P-MDP is similar the original MDP except that the agent is only allowed to
4

---

Under review as a conference paper at ICLR 2021
take actions from A when E S and that it follows greedy-n" at non-secure states & S
T-
arg max E
Σ rr((s, 0x)
=Ell"'
In implementation, we do not explicitly construct II" Instead, we evaluate T." (s, for every considered state-action pair in P-MDP and make sure that all suggested reward-seeking actions are in A"", Note that, if policy r) is safe, every policy in II" is guaranteed be safe. More particularly, in such case, any policy in the entire learning process of the P-MDP is safe. We would refer to the whole procedure of solving R-MDP and P-MDP as Recomnaissance and Planning (RP) algorithm. The following table summarizes the algorithm. Naturally, whether this algorthm works in application
Algorithm 1 RP algorithm
1: Obtain the baseline policy 17" by either solving R-MDP selecting heuristic policy
2: Estimate T."" (+.+)
3: Solve the P-MDP (9) while referring the evaluation of J.."" at every considered state-action pair
so that all actions will be chosen from A (Eq.
depends on how well we can evaluate the threat in R-MDP. However, in many applications, the set of dangerous events to be avoided can be extremely rare. These rare events make the empirical approximation E,y [-] difficult. We resolve this problem by evaluating J," (s, a) with the generative model. With the generative model, we can freely explore the system from any arbitrary initial state, and evaluate (s, a) for any (s, a) and 7). To facilitate the learning of N."' (s, a), we use the generative model to preferentially sample the states with relatively high estimated T." (s, a) more frequently. We will next introduce a technique approximate the threat function.
3.1 THREAT DECOMPOSITION AND APPROXIMATE RP ALGORITHM
We will present a useful bound on the threat function that can be used when the danger is be described
terms of multiple risky events. Suppose that there are N risky events {E1.... Evy } to consider, and that the goal is optimize the reward while avoiding any risky event. More formally, let us represent the indicator function of En by d" ds((s)) ..(()) ar) where s/") is the state of the system relevant to En and g(o) is the state of the system not relevant to any risky events. Let us also assume that the transition (n) (n)
probabilities decompose into p(s (t, at) = p(5 (0) aa) II ((s,"11ss
a.). at).
is
the indicator function of U En. can formalize this result as follows:
Theorem 5. Let be policy that takes action based solely on 5,"), and let T be the threat function
defined for the indicator function of U En. Then T," a4) I EN "."."(s"" (0) (n)
St a.))
This result is especially useful in navigation-like tasks. For example, when E,, is the collision event with nthh obstable, 8, will be the state of rath obstacle, and s. will be the aggregate state of the system that are not related to any obstacles(state of the agent, etc). In such case, each g can be estimated using the simulator containing just the nuth obstable object and the agent. Algorithm i the algorithm that uses Theorem For other variants of Theorem S
please see the Appendix. Theorem 5 suggests
Algorithm 2 Approximate RP algorithm
1: Pick a heuristic policy rf(o) which depends on (o) only.
2: Estimate the threat functions 9.00") ((.-) for all sub R-MDPs.
3: Solve the P-MDP (9) while referring to the evaluation of Σn (p)
at every considered
state-action pair so that all chosen actions will satisfy Σn gryloin tohn
I It-
that that threat function can be treated like risk potential. Wolf & Burdick 2008 Rasekhipour et al. (2016b); Ji et al. (2016). Risk-potential based methods also work by evaluating the risk of collision with each obstacle for each location in the environment, and by superimposing the results. However, most of these works define the risk potential rather heuristically.
5

---

Under review as a conference paper at ICLR 2021
FFFFFFF
FFFFEFFF
LEFT
DOWN
RIGHT
UP
FFFHFFFF
FFFFFHFF
FFFHFFFF
FEIFFFUF
PHEPНPиF
FFPHFFFC
0.00
0.25
0.50
0.75
1.00
125
155
175
(a) Map
(b) Threat function
10
1.0
Average danger
P-MDP with r
Average reward
P-MDP with d
P-MDP with f
0.6
Lagrange multiplier method
P-MOP with A
Upper bound
P-MOP with d
02
P-MDP with o
0.
RP
10
10
10
10
threat threshold x
Average danger
(c) Danger
(d) Reward vs Danger
Figure 2: (a) Map FrozenLake8x8-v00 Here the symbols 'S', 'G', 'H' and 'F' denote the position of start, goal, hole be avoided, and frozen surface, respectively. (b) Heat map of the threat function of optimal R-MDP baseline policy. The warmer color represents the higher value of the threshold function at the corresponding position and action. The threshold tends to be higher around the hole. (c) Average danger suffered by PMDP policies vs safety threshold æ. (d) Scatter plot of average rewards and average dangers obtained with different safety thresholds.
EXPERIMENT
We conducted a series of experiments to (i) analyze the nature of the threat function, (ii) the effect of the choice of the baseline policy 7) on the performance of P-MDP, and (iii) the sheer efficacy of the RP algorithm implemented with the threat decomposition approximation. We will also show that can re-use the threat function computed for one CMDP to solve another CMDP problem with similar safety constraint. We will demonstrate the power of our method on high-dimensional problems.
4.1 FROZEN LAKE ENVIRONMENT
We considered example of the frozen lake environment FrozenLake8x8 in OpenAl Gym where the agent navigates in the by 8 grid world in Fig. 2 (a). The goal of the agent is to start from 'S' and navigate its way through the slippy environment reach the goal 'G' while avoiding the holes 'H'. Each time on a frozen surface 'F", the agent can choose to move in one of the four directions, but
the surface is slippery so the agent's actual movement may be different from the intended direction. We first construct the R-MDP as described in Sec 3 The R-MDP is tabular MDP which can be solved by value iteration. The threat function of the optimal R-MDP policy is shown Fig. 2 (b). The threat values are indeed higher when the agent is closer to the holes. From the threat function we can see that, there is safe path from 'S' 'G' following the right most column. But the tricky part is at positions (6, 8) and (7, 8). On these positions, the only action that can avoid the danger is 'RIGHT', which not the best reward-seeking action ('DOWN').
The P-MDP is again tabular MDP, and we can solve it by value iteration. In Fig. (c) and (d), we compare the performance P-MDP based on the optimal R-MDP policy 17" against those of the P-MDPs based the sub-optimal R-MDP policies. Based on completely random policy for 7 we defined '7' = greedy-17 and r7 = greedy-n' In other words, both 7) 772 are the outcomes of applying policy iterations the random policy. We also plot the reward and danger trade-off using the Lagrange multiplier method. We can see that, even though 77 is completely random, the P-MDP constructed from , generates safe policies when the threat threshold is small. When the baseline

---

Under review as a conference paper at ICLR 2021
(a)
(b)
(c)
(d)
45
-15
-10
Figure 3: (a) Illustration of Jam task. The light blue circles are obstacles and the yellow circle the agent. Three shaded corners are safe-zones. The arrow attached to each object shows its direction of movement. (b) Heat map of the trained threat function whose value at point (x;, y) represent the threat when the obstacle (light blue) is placed at (r, y) with the same velocity. (c) and (d) are the heat maps of the sum of the threat functions of all moving obstacles. The heat value at (I, y) is the threat posed to the agent at (a, 2) when it is moving in the direction indicated at the left bottom corner.
policy becomes better, the reward tends to become higher and the danger becomes smaller. At the same time, the difference becomes small after the second iteration. We see that, two policy iteration is enough to obtain near-optimal policy for this problem. The upper bound from Theorem is shown as a dashed curve in Fig. (c) which is in accordance with our theory.
4.2 DICHEDIMENSIONAL ENVIRONMENTS
For high-dimensional environments, we consider three tasks on 2-D fields. See Fig. I and Fig. for visualizations. For Point Gather, the agent's goal is to collect many apples possible while avoiding bombs. For Circuit, the agent's goal is to complete one lap around the circuit without crashing into wall. The agent can control its movement by regulating its acceleration and steering. LiDAR sensors are used to compute the distance to obstacles. For Jam, the LiDAR-equipee goal is to navigate its way out of a room from the exit located at the top right corner as quickly as possible without bumping into 8 randomly moving objects. The observation of each environment consists of 29, 364, 392 real values respectively and an agent needs to deal with stochasticity in Jam. For further details, please see Appendix F Before explaining the experimental results, we would like to note that the total reward changes depending on how much we severely penalizes the agent for each crash. As a reference, we show the results when imposing heavier penalty on the crash in Appendix H.
agent's 's
As discussed carlier, finding the optimal policy of the R-MDP is challenging in high- nigh-dimensional environments. However, since the constraint in these environments is to avoid collision with any obstacles,
the approximation method introduced in See 3.1 that uses set of sub-R-MDPs containing one obstacle and one agent each. Thus, to guarantee the safety in P-MDP, we only learned a threat function of a heuristic baseline policy ry (0) in a Sub-R-MDP with one obstacle. For Circuit and Jam, treated wall as set of immobile obstacles that we construct the threat function of any shape. After about 10 minutes of data collection with the generative model, this threat function the supplemental material
could be learned in less than half an hour without using GPUs. Please for more detailed conditions and videos of the agent trained by each method. Fig. 3 (d) are the heat maps for the upper bound of the threat function computed in the way of Theorem The color of each heat map at pixel Z represents Σ,, "0" (s(z), a). where s(z) represents the state at which the agent's 's current location is and its velocity and direction is given by the picture located the left corner of the heat map. We see that our threat function is playing a role similar to the artificial potential field (Ge & Cuil 2000 Cetin et al. 2011 Lam et al., 2010). Because our threat function is computed using all aspects of the agent's 's state (acceleration, velocity, location), we can provide more comprehensive measure of risk compared to other risk metries such as TTC (Time To Collision) (Lee)
1976) used in smart automobiles that considers only ID movement.
Fig. plots the average reward and the crash rate against the training iteration for various methods: (i) classical MPC (exhaustive search), (ii) DQN with Lagrange penalty, and (iii) Constrained Policy Optimization (CPO) (Achiam et al. 20)7a). DQN and CPO are model-free algorithms, while RP and MPC are generative model-based algorithms. (ii) is essentially the same the Lagrangian based methods like (Geibel & Wysotzki 20055; Geibel 2006). The results of DQN can be considered as a reference of the difficulty of solving CMDP with model-free RI. methods. To compute the threat in
7

---

Under review as a conference paper at ICLR 2021
(a)
Point Gather
Point Gather
average reward
0.8
crash rale
DoudleDON (A-1)
DousleDON (A-1
DousleDoN Me500
50
AFprox (=00.5
48- CPO
20
(1step)
Constraint
08
million steps
million steps
(b)
Circuit
Circuit
average reward
1390
crass rate
DoublDON (A=0)
mm
DoubkDON (A=20)
DoubkenON (A=200)
CPO
MPG (Solaps)
-200
MPG (3000ps)
Constrant
million steps
million steps
(c)
Jam
Jam
average reward
crash rate rate
0.0
DouDieDON
DoubleeON (A-5 5500)
JEOFOX
MFC (3tepp)) MPC (2tepps) Comstraint
880
million steps
million steps
Figure 4: Comparison of multiple CMDP methods in terms of rewards (left panels) and crash rate (right panels) diffferent environments (a) Point Gather, (b) Circuit and (c) Jam.
MPC, we took the same strategy of threat decomposition as our method G.4 in order to make the prediction efficient.
The average values and the 90% confidence intervals in the plot were computed over 10 seeds. The curve plotted for approx. RP corresponds to the result obtained by DON-based P-MDP solution. The plot does not include the R-MDP phase. As we can see, our method achieves the highest reward almost all phases of the training for both Circuit and Jam, while maintaining the lowest crash rate. Our method is safer than the 3-step MPC for both Jam and Circuit as well, method with significantly higher runtime computational cost. For point- gather, RP with z 0.1 performs worse in terms of reward than the penarlized DQN and CPO. Although 0. is a value that is slightly larger than the minimum safety threshold that guarantees the safety, our RP with very conservatively in term of safety. This suggest that the pool of actions allowed for = 0.1 is probably still too small. Fortunately, however, we can fine-tune the threshold to increase the pool of allowed actions for P-MDP without re-learning the threat function. Our RP with 0.5 performs competitively while satisfying the prescribed constraint. That we can fine-tune the threshold without retraining is significant advantage of our method over Lagrange-tyee -yppe methods. Also, by the token of Corollary 3 that our policy is experimentally safe suggests that greedy-1) is also safe for the choice of the baseline policy 10
performs
4.3 RECYCLING OF THE THREAT FUNCTION FOR A CMDP IN DIFFERENT ENVIRONMENT
As we mentioned introduction, we can reuse the threat function for different CMDP tasks with different goals if their safety constraints defined similarly. In order to verify this powerful feature of our algorithm, we conducted two sets of experiments in which we apply a policy learned on one environment to the tasks another environment. For the first set of experiments, trained safe
8

---

Under review as a conference paper at ICLR 2021
Environment
approx. RP
MPC (4steps)
DQN (A=0)
DQN (A=200)
Training env.
1439 (0)
1055 (0.35)
1432 (0.05)
933 (0.4)
Narrowed env.
377 (0)
959 (0.55)
-151 (1.0)
-145 (0.99)
Circle Computation Time (s)
130 (0)
351 (0)
-189 (1.0)
-171 (1.0)
0.5
18.2
0.4
0.4
Table Performance of trained policies on known and unknown Circuit environments. The values in the table are the obtained rewards, and inside the parenthesis are the probabilities of crashing. Time stands for the computation time consumed in making 100 action steps. Note that our method never crashes in this experiment. In this experiment, every crash is penalized by 200pts. See Appendix for the result with heavier crash penalty.
Environment
approx. RP
MPC (3steps)
DQN (A=5)
DQN (A=500)
N =3
78.2 (0)
77.5 (0.05)
77.2 (0.04)
4.4 (0.17)
(training env.)
69.1 (0)
65.3 (0.2)
47.1 (0.38)
-1.0
N 15
33.0 (0.02)
36.6 (0.45)
16.5 (0.66)
-16.8 (0.51)
Computation Time (S)
1.2
285
0.4
0.4
Table 2: Performance of trained policies on and known and unknown Jam environments. Values in In this experiment, every crash is penalized by
the table are reported in the same way in Table [ 50 pts. Note that we achieve the lowest crashing rate while achieving high score. Our RP stands out more if the crash is penalized more heavily (See Appendix)
policy for the Circuit task, and evaluated its performance on the environments that are different from the original circuit used in the training, (1) narrowed circuit with original shape, and (2) differently trained safe policy for
shaped circuit with same width. For the second set of experiments, the Jam task, and tested its performance on other Jam tasks with different numbers of randomly moving obstacles. Figs. [a show the results. For the modified Jam, we have results for MPC with more than 3-step prediction since the exhaustive search cannot be completed within reasonable fime-e The 4-step MPC requires 18.2secs per each 100 steps for Circuit, and the 3-step MPC requires 285secs per each 100 steps for the original Jam. We find that, even in varying environments, the policy obtained by our method can guarantee safety with high probability while seeking high reward. On the other hand, DQN in new environment is failing both in terms of reward and safety.
5 CONCLUSION
In this study we proposed a method that isolates the safety seeking procedure from reward-secking procedure in solving CMDP. Although method does not guarantec to find the optimal reward- seeking safe policy, it can perform significantly better than classical methods both in terms of safety and reward in high-dimensional dynamic environments like Jam. Our method is designed so that more training in R-MDP will always help increase the search space in P-MDP. Our treatment of only allows us solve similar problems without the need of re-learning,
the threat function also helps us obtain more comprehensive measure of danger at each state than conventional methods. Overall, we find that utilizing threat functions a promising approach safe RL and further research on framework may lead to new CMDP methods applicable to complex, real-world environments.
REFERENCES
Joshua Achiam, David Held, Aviv Tamar, and Picter Abbeel. Constrained policy optimization. arXiv preprint arXiv: 10528, 2017a.
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization, 2017b. ht.
com/ jach aachiam/// impo
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999. ISBN 0849303826.

---

Under review as a conference paper at ICLR 2021
dexterousMarcin Andrychowicz, Bowen Baker, Maciek Chociej, Rafal Jozefowicz, Bob McGrew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, and Alex Ray. Learning in-hand 2018.
manipulation. arXiv preprint
Christel Baier, Boudewijn Haverkort, Holger Hermanns, and J-P Katoen. Model-checking algorithms for continuous-tii time markov chains. IEEE Transactions software engineering. 29(6):524-541, 2003. ISSN 0098-5589.
Maxime Bouton, Jesper Karlsson, Alireza Nakhaci, Kikuo Fujimura, Mykel Kochenderfer, and Jana Tumova. Reinforcement learning with probabilistic guarantees for autonomous driving. arXiv preprint 1eXXv:/904.071/0 2019.
Omer Cetin. Sefer Kurnaz, Okyay Kaynak, and Hakan Temeltas. Potential based navigation task for autonomous flight control of unmanned aerial vehicles. International Journal of Automation and Control, 1(1): 2011. ISSN 1740-7516.
Yinlam Chow, Ofir Nachum, Edgar Duenez-Guzman, and Mohammad Ghavamzadeh. A lyapunov- based approach to safe reinforcement learning. In Neural Information Processing Systems 2018, 2018.
Yinlam Chow, Ofir Nachum, Aleksandra Faust, Mohammad Ghavamzadeh, and Edgar Duenez- Guzman. Lyapunov-based safe policy optimization for continuous control. arXiv preprint 1901 10031, 2019.
Stefano Di Cairano, Danicle Bernardini, Alberto Bemporad, and Ilya V Kolmanovsky. Stochastic mpe with learning for predictved vehicle control and its application to hev energy management. IEEE Transactions Control Systems Technology, 22(3):1018-10 1031, 2013. ISSN 1063-6536.
Jerry Ding, Eugene Li, Haomiao Huang, and Claire J Tomlin. Reachability- based synthesis of feedback policies for motion planning under bounded disturbances. In 201 IEEE International Conference on Robotics and Automation, pp. 2160-2165 IEEE. ISBN 1612843859.
Michael Everett, Yu Fan Chen, and Jonathan P. How. Motion planning among dynamic, decision- making agents with deep reinforcement learning. Intelligent Robots and Systems (IROS), 2018 IEEE/RSJ International Conference on, 2018.
Paolo Falcone, Francesco Borrelli, Jahan Asgari, Eric Tseng, and Davor Hrovat, model predictive control approach for combined braking and steering in autonomous vehicles. In Mediterranean Conference on Control & Automation, pp. 1-6. IEEE, 2007. ISBN 1424412811.
Shuzhi Sam Ge and Yan Juan Cui. New potential functions for mobile robot path planning. IEEE Transactions on robotics and automation, 16(5):615-66 6200, 2000. ISSN 1042-296X.
Peter Geibel. Reinforcement learning for mdps with constraints. In European Conference on Machine Learning, pp. 646-653. Springer, 2006.
Peter Geibel and Fritz Wysotzki. Risk-sensitive reinforcement learning applied to control under constraints. Journal of Artificial Intelligence Research, 24:81-108, 2005.
Stephen James, Paul Wohlhart, Mrinal Kalakrishnan, Dmitry Kalashnikov, Alex Irpan, Julian Ibarz, Sergey Levine, Raia Hadsell, and Konstantinos Bousmalis. Sim-to-real via sim-to-sim: Data-efficient robotic grasping via randomized-to- to-ad-ooo---ccclll adaptation networks. arXiv preprint arXiv:1812.00725,, 2018
Jie Ji, Amir Khajepour, Wael William Melek, and Yanjun Huang. Path planning and tracking for vehicle collision avoidance based on model predictive control with multiconstraints. IEEE Transactions Vehicular Technology, 66(2):952 964, 2016. ISSN 0018-9545.
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, and Vincent Vanhoucke. Qt-opt: Scalable deep reinforcement learning for vision- vision-based robotic manipulation. arXiv preprint 110.111806.10293, 2018.
10

---

Under review as a conference paper at ICLR 2021
Chi-Pang Lam, Chen-Tun Chou, Kuo-Hung Chiang, and Li-Chen Fu. Human-centeree robot navigation- towards harmoniously human robot coexisting environment, IEEE Transactions on Robotics, 27(1):99-112 112, 2010. ISSN 1552-3098.
David Lee. A theory of visual control of braking based on information about conllso-collision. Perception, 5(4):437-459, 1976. doi: 10. 1068///0433...
Wei Liu and Marcelo Jr. Incremental sampling-based algorithm for risk-aware planning under motion uncertainty. In JEEE International Conference on Robotics and Automation, pp. 2051-2058, 2014.
Jan Marian Maciejowski. Predictive control: with constraints. Pearson education, 2002. ISBN 0201398230.
Megumi Miyashita, Shirou Maruyama, Yasuhiro Fujita, Mitsuru Kusumoto, Tobias Pfeiffer, Eiichi Matsumoto, Ryosuke Okuta, and Daisuke Okanohara. Toward onboard control system for mobile robots via deep reinforcement learning. In Proceedings of workshop on machine learning systems (LearningSys) in the twenty-ninth annual conference neural information processing systems (NIPS), 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, and Georg Ostrovski. Human-level control through deep reinforcement learning. Nature, 518(7540):522 533, 2015. ISSN 0028-0836.
Santiago Paternain, Luiz Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained reinforcement learning has zero duality gap. In Advances in Neural Information Processing Systems, pp- 7553-7563, 2019.
Yadollah Rasckhipour, Amir Khajepour, Shih-Ken Chen, and Bakhtiar Litkouhi. A potential field- based model predictive path-planning controller for autonomous road vehicles. IEEE Transactions Intelligent Transportation Systems, 18(5):1255-12) 2016a. ISSN 1524-9050.
Yadollah Rasekhipour, Amir Khajepour, Shih- Ken Chen, and Bakhtiar Litkouhi. A potential field- based model predictive path-planning controller for autonomous road vehicles. IEEE Transactions on Intelligent Transportation Systems, 18(5): 2016b. ISSN 1524-9050.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, and Mare Lanctot. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016. ISSN 0028-0836.
Sean Summers, Maryam Kamgarpour, John Lygeros, and Claire Tomlin. A stochastic reach-avoid problem with random obstacles. In Proceedings of the 14th international conference on Hybrid computation and control, pp. 251-260.
systems:
Ryo Takei, Haomiao Huang, Jerry Ding, and Claire J Tomlin. Time-optimal multi-stage motion planning with guaranteed collision avoidance via open-loop game formulation. In 2012 IEEE International Conference on Robotics and Automation, pp. 323-329. IEEE. ISBN 146731 14056
Seiya Tokui, Kenta Oono, Shohei Hido, and Justin Clayton. Chainer. gext-generation open source framework for deep learning. In Proceedings of workshop on machine learning systems (LearningSys) in the twenfy-ninth annual conference on neural information processing systems (NIPS), volume 5, pp. 1-6, 2015.
Biji Uchibe and Kenji Doya. Constrained reinforcement learning from intrinsic and extrinsic rewards. In Development and Learning, 2007. ICDI 2007. IEEE 6th International Conference on, pp. 163-168. IEEE, 2007. ISBN 1424411157.
Erwin Walraven and Matthijs TJ Spaan. Column generation algorithms for constrained pomdps. Journal of artificial intelligence research, 62:489-533, 2018. ISSN 1076-9757.
Yang Wang and Stephen Boyd. Fast model predictive control using online optimization. 1EEE Transactions control systems technology, 18(2):267-278, 2010. ISSN 1063-6536.
11

---

Under review as a conference paper at ICLR 2021
Thomas Weiskircher, Qian Wang, and Beshah Ayalew. Predictive guidance and control framework for (semi-) autonomous vehicles in public traffic. IEEE Transactions on control systems technology. 25(6):2034 2046, 2017. ISSN 1063-6536.
Min Wen, Rüdiger Ehlers, and Ufuk Topeu. Coryect-yy-sythheiis reinforcement learning with temporal logic constraints. In Intelligent Robots and Systems (IROS), 2015 IEEE/RSJ International Conference on, pp. 4983-4990, IEEE, 2015. ISBN 1479999946.
Michael Wolf and Joel W Burdick. Artificial potential functions for highway driving with collision avoidance. In 2008 IEEE International Conference on Robotics and Automation, pp. IEEE, 2008. ISBN 1424416469.
Eiichi Yoshida, Claudia Esteves, Igor Belousov, Jean-Paul Laumond, Takeshi Sakaguchi, and Kazuhito Yokoi. Planning 3-d collision-free dynamic robotic motion through iterative reshaping. IEEE Transactions on Robotics, 24(5): 10111866-119999 1198, 2008. ISSN 1552-3098.
APPENDIX
A PROOF OF THEOREM
Proof. Let's first prove the theorem by induction. At T. Eq. (6) holds because both sides
zero. Suppose Eq. (6) holds at & + 1. Then at time t, the danger value function of π at t satisfies
27 (8)) Ex [d(se, ar) + ( 8c]
T-1
Ex d(st, a.) + 3 2 T4t1 (8++1) +
Σ
Bh-t on
En Ex (=(Ea(0++1)))
k=1+1
=E, T." 1t, az) st
+
Σ
gk-t xx Ex [2k(s]]
(10)
k=t+1
The above inequality follows from the induction hypothesis at + 1, and the last equality is from the definition of J."" and the property of conditional expectation.
Since æ E IT when 8, S we know that F J." (st, ox) 8t
S Fry (,, (st, a:) st). Noting
the fact above and (st) = (," a.) st). for the first term in Eq. 10 we have
F [TT 88 (s{))
Slaesmm (T((rls)) n((rls))) (,,,, ax)
Sluesne
(T(acls)) n(a.ss:)) a da::
max
9.' (5((,, a)
(11)
Here the first inequality holds because the term is negative when 8; & ST.= The second inequality is true by taking the absolute value with fact that (St, a,) 0. The thirdinequality follows from the property of the total variation distance. The last inequality is true because of the construction of I7.
Now get
T-1
(x))) (8) + 2240 +
Σ
gh 'x
Ex [x
k=
T-1
= (8)(()) + Σ
3
23 Ex
Iza [sc]
(12)
1=
12

---

Under review as a conference paper at ICLR 2021
which completes the induction step and the proof of Theorem N.Notice that the logic used here is essentially same as the one used in the proof of Theorem of (Achiam et al. 2017a). However, our result is slightly different in that consider finite time-horizon and utilize our assumption that Ti" a) S 2z for (17, x)-secure states.
B PROOF OF COROLLARY 3
Proof. First, we will derive a result similar to Theorem
Theorem 2. For given policy and a sequence of safety thresholds æ = ..0....,TT-1) let be policy in IT Then for all E (O....,? 1}.
(st) S gtoaady " (st)
3
En
1= st],
T-1
S min (st + 2
Σ
3 xy
3h
12 stl
(13)
k=t
where =/ is distance measure Lo.sn= drv (+), greedy-n((lss)).
between
and
greedy-n given by 2
=
Let's prove the theorem by induction. At T, Eq. (13) holds because both sides Suppose Eq. (13) holds at + 1. Then at time t, the danger value function of x at t satisfies
2f (8t) = [d(st, at) + 12 st
T-1
F d(st, at) + 3
2 (s++1) +2
Σ
gh gh-t 1 Be Er (=l2l1ee11)
k=1+1
T-1
-Ea g. (st, gs
st +2
Σ
Iy [2]]s]]
(14)
The above inequality follows from the induction hypothesis at + 1, and the last equality is from the definition of grreedy and the property of conditional expectation.
Since क E II when 8 & S we know that .( (-1s;t) = greedy-7(-Iss). Noting the fact above and (a = Egreedy-ng | (. az) se). for the first term in Eq. (4)) we have
Eg ge (S1, as)
=1 =1
(T (x))
-greedy-y(aa) (x)) F. predy ( (8r, as dae
(T(a(()))
greedy-n((e(ss))) J.
(Se, ar daa
S1 27 (-(+ss)) gredd--)r)
max g.and g.anddy (s,, dempplat: ac))
<1. 2TV greedy-nen-neee
F." (st, max (Em))((((1s)))
<22f xt
(15)
Here the first inequality is true by taking the absolute value with fact that I greedly- ((,, ax) 2 0. The second inequality follows from the property of the total variation distance. The third inequality holds because greedy-7 7 is the policy after one step of policy improvement from 17, hence gereedyn a) S
T." (8,,a). The last inequality is true because of the construction of I[
13

---

Under review as a conference paper at ICLR 2021
Now get
T-1
27 (8t) - 2ereedy-- (se) + 22,32 +2
gh xx For [=1]
k=t-1
T-1
22roody- (st) +
3 E [c]
A=t
min T." (5t, a) 2
g
Sx Fix
[=] 88]
(16)
which completes the induction step and the proof of Theorem 2
Now using Theorem Corollary follows using the same arguments as Corollary
C PROOF THEOREM 5
By the assumption about the transition probability, (s
Ed , as))ss
(o) &k ax) (x)) " ,ae). Using this property, the claim of Theorem 5 immediately
follows by applying the union bound d(st,a)) az) S > dl (s
D ANOTHER INTERPRETATION FOR P-MDP
Since restrict attention to policies in II", the P-MDP can be viewed as an MDP defined of the smaller state space S", Namely, we constructed the tuple (5", A", ry, Pp. Po). whose components defined follows. The function r (-ls) is the restriction of the reward PR is a transition probability function derived from the original state transition probability P such
(*(s) for all S",
that, for all 81, 82 S Pj (82 $1, a) P(s 81, a) P((81, a) (8") $2) where (81, a) (8") 82 is the set of all trajectories from to 82 that (1) take detour to (S at least once after taking the action a at s, (2) take the action a" a"(s" arg minae A (s' a) for all s' (S*)S, and (3) lead to $2 without visiting any other states in S"
E VALUE ITERATION AND Q-LEARNING FOR P-MDP
When the transition probabilities are available, we can solve the P-MDP using value iteration. The value iteration for P-MDP can be described by the following algorithm.
Algorithm 3 Value Iteration for P-MDP
1: Input: threat function T"(s, a), transition probabilities P(s'ls,
2: Initialize (s) +-
3: while before convergence do
4: for each s, do
5: Q(s, a) Σ.' P(s (()))s, +(((s))
6: end for
7: for each E 5t do
8: V(s) +- ma()) (s)
9:
end for
10: for each $ 5th do
11: greddy-n t arg min, (,( a)
12:
13: V(s) - Q(x, areadyy)))
14: end for
15:
end while
14

---

Under review as a conference paper at ICLR 2021
When the transition probabilities not available, we can solve the P-MDP using Q-learning or its Deep RL versions.
Algorithm 4 Q-learning for P-MDP
1: Input: threat function g"(s,, a), learning rate a and a behavior policy π
2: Initialize (s.
3: while before convergence do
4: sample a transition s, a, by
5: if s' E S" then
6:
Quaga(s, < r(s, a) + max Q(s',a')
7:
else
8:
agreedyn t arg ming ("', .')
9:
Quager (s, + r(8, + 7Q(s', agneddy))
10:
end if
11:
(s..0) + (1 (0l-a)Q(ss (s),aa))))))))))))))))) a) + a Qusrga a))
12:
end while
F ENVIRONMENTS
CIRCUIT
In this task, the agent's goal is to complete one lap around the circuit without crashing into the wall. Each state in the system was set to be the tuple of (1) location, (2) velocity, (3) the direction of the movement, and (4) the raw LiDAR input for each one degree. Thus, the state observation has 364 real values. The set of actions allowed for the agent was {0.15 to left, 0.05rad to left, stay course, 0.05 rad to right, 0. 0.15 rad to right] } x { 0.02 unit acceleration, no acceleration, 0.02 unit deceleration (15 options). At all time, the speed of the agent was truncated at {-0.04, 0.13. We reward the agent for the distance of travel along the course in the right direction, which accumulates to 1250pts for one lap. We also give negative rewards for the stopping and collision at the time step. We penalize the agent 1t for stopping. and penalized the agent by 200pts for colliding. We set the length of the episode to 200 steps, which is the approximate number of steps required to make one lap. In the computation of each summand in the threat decomposition, we augmented the generated dataset by flipping the state with respect to x aris(left-right). The constraint for CMDP was set to le-3.
JAM
In this task, the agent's goal is to navigate its way out of room from the exit located at the top left corner without bumping into randomly moving objects. We set three circular safety zones centered at each corner except for the top left corner, i.e., exit. Any moving obstacle entered into the safety zone disappear. Without the safcty zone, the task seems to be too difficult, i.c., there is a situation that the agent cannot avoid the collision even if the agent tries his best. We set the safety zone to ease the problem hoping the probability that the agent can solve the task when employing the optimal policy becomes reasonably high. The field was x 3 square and the radius of the safety zone located at three corners were set to 0.5. The radius of the agent and moving obstacles were set to 0. We reward the agent for its distance from the exit, and controlled its value so that the accumulated reward at the goal will be around 85. The agent is given 10 points when it reaches the goal, penalized -0.05 points for stopping the advance, and given 50pts penalty for each collision. Similar the setting as in Circuit, the agent is allowed to change direction and acceleration of the movement simultancously at each time point. The observation of agent has the information of relative location, relative velocity, and relative direction of 8 nearest cars in addition to the observation of Circuit. It is composed of totally 396 real values. The set of actions allowed for the agent {0.30 rad to left, 0.10 rad to left, stay course, 10 rad to right, 0.30 rad to right } x { 0.02 unit acceleration, no acceleration, 0.02 unit deceleration }. At all time, the speed of the agent is truncated at { (-0.1, 0.1}. Each obstacle in the environment is allowed to take random action from 5 to left, 0.05rad to left, stay course, 0.05 rad to right, 0.15 rad to right/ x { 0.02 unit acceleration, no acceleration, 0.02 unit deceleration }. The speed of the environment truncated (0, 0.06). We set the length of each episode 100
15

---

Under review as a conference paper at ICLR 2021
steps. In the computation of each summand in the threat decomposition. augmented the generated dataset by flipping the state with respect to x aris(left-right). The constraint for CMDP was set to 0.01.
POINT GATHER
In this task, the goal is to collect as many green apples possible while avoiding red bombs. There are apples and 8 bombs in the field. We used the exact same task setting as the one used in the original paper, and the agent is rewarded 10pts when the agent collected apple. The point mass agent receives 29-dimensional state and can take two-dimensional continuous actions, For the implementation of DQN, discretize each action variable into 9 values. The state variable takes real values, which include position, velocity, direction, distance to the bomb, and etc. The action variables determine the direction and the velocity of the agent. As is done in the experiment in (Achiam et al.) 2017a), we set the length of each episode to 15 steps. At every step, our selected baseline policy randomly chooses a direction from 14.33, 14.33]degree range with uniform distribution, and move forward with probability 0.9 and move backward with probability 0.1. After deciding the direction of the move, the baseline policy prompts the agent to move at at the speed chosen uniformly from [0, 1 1|unit range. For the approximation of threat function, we sampled 1e6 trajectories by simualtors, and we did not bother to the compute average value for each fixed initial state. The constraint for CMDP was set to 0.1.
G MODEL ARCHITECTURE AND OPTIMIZATION DETAILS
G.1 RP-ALGORITHM
We implement our method on Chainer (Tokui al. 2013). The code is available in supplementary
material.
LEARNING OF THREAT FUNCTION IN R-MDP
For the Circuit and Jam tasks, the agent must avoid collisions with both moving obstacles and the wall. For these environments, it computationally difficult to obtain the best 77. Thus, we follow the approximate RP algorithm by training threat function for baseline policy 17(0), We used tha (1) decides the direction of the movement by staying course with probability 0.6, turning right with probability 0.2 and turning left with probability 0.2, and (2) decides its speed by accelerating with probability 0.2 and decelerating with probability 0.2. We chose not to train specifically for this experiment, because 1) to be used in the decomposition must not depend on the state of all but one obstacle, and we could not expect to improve its safety much by training it. The threat function for the collision with the immobile point is used to avoid collision with the wall, which can considered as set of immobile points. We thus trained two threat functions in total: one corresponding to the collision with an immobile point, and one corresponding to the collision with randomly moving obstacle. Threat function for 17(0) can be trained by using generative models starting at various initial points to collect samples and by conducting supervised learning.
For the threat function for the collision with immobile object, we used neural network with three fully connected layers (100-50-15). For the threat function for the collision with moving obstacles, we used network with four fully connected layers 35005500-500-55 For the training dataset, we sampled 100,000 initial state and simulated 10,000 paths of length from each initial state. We train the network with Adam. The parameter settings for the training of the threat function of immobile point and of mobile obstacle
(a le 2. le 2, batchsize 512, number of epochs 20), and (a = le - 3, c = 1e 2, batchsize = 512, number of epochs 25), respectively. We used relu as the activation function for the approximation of all threat functions.
For the Point Gather task, we again use the approximate RP algorithm. The threat function is estimated by three-layer (100-100-81) fully connected neural network.
16

---

Under review as a conference paper at ICLR 2021
SOLVING P-MDP
For the Planning MDP, we use DQN. The network used for the Q-function in P-MDP looks like (),,s), where is the result of applying lider outputs ID conv network, 8 is the combination of location, velocity and angle, and ① is a three-layered fully connected network (50-20-15) with tanh activation functions.
The convolutional layer has 3 output channels with kernel size = and stride 1, followed by max pooling with kernel size 8. In Point Gather, we use fully connected neural network with three layers (50-50-81), 30) We trained the network with Adam (a le - 3, C le 2). We linearly decayed æ for e-greedy from 1 to 0.05 over 3M iterations. We used one GPU, with which it took no longer than about 24 hours to complete 3M iterations.
G.2 DQN WITH LAGRANGE COEFFICIENT
As for the network, we used the same DQN architecture as the one we used in P-MDP. We used tanh for the activation function. For Lagrange coefficient, we test with three Lagrange coefficients for each task, {0, 20, 200} for Circuit, {5, 50, 500} for Jam, {1, 10, 50} for Point Gather, respectively. For the Jam task, the initial Lagrange coefficients are all set and gradually incremented the final values (1, 10, 50} as done in (Miyashita et al. 2018). This heuristic pushes the agent to learn the goal-oriented policy first, and then learn the collision avoidance.
G.3 CONSTRAINED POLICY OPTIMIZATION
As for CPO, we use the same implementation publicized on Github (Achiam et al., 2017b), i.e., the policy a Gaussian policy implemented by three layer MI.P with hidden units and 32 for all tasks. We used tanh for the activation function.
G.4 MODEL PREDICTIVE CONTROL
We tested MPC with receding horizon E {3, 5] for Circuit, E {2,3} for Jam and E {1, 2} for Point Gather. At every step, selected the action with the highest reward among those that were deemed safe by the prediction. To select the next safe action, we used tree-search on the sequence of actions, and prematurely pruned branches that were sure violate the safety condition. Also, for the JAM experiment, we used the same strategy as our approximate-RE More particularly, we allowed MPC to make predictions in a of environments consisting of one pair of obstacle and ego-object each, and evaluated the safety by summing the danger values computed from all environments. This was done in order reduce the computation time of prediction (which already is large), because the number of combinatorial cases explodes as we increase the number of obstacle objects.
H PERFORMANCE EVALUATIONS WITH LARGER COLLISION PENALTY ON CIRCUIT AND JAM
Here show the score computed with a larger collision penalty on Circuit and Jam tasks to stress the fact that the performance will vary arbitrarily depending on how much we put emphasis on the constraints. below, the collision penalty increased to be 1500pts and 500pts instead of the ones used in Table where the collision penalties are 200pts and 50pts, respectively.
Environment
approx. RP
MPC (4steps)
DQN (A=0)
DQN (A=200)
Training env.
1439 (0)
600 (0.35)
1367 (0.05)
413 (0.4)
Narrowed
377 (0)
244 (0.55)
-1451 (1.0)
-1432 (0.99)
Circle
130 (0) 351 (0)
-1489 (1.0)
-1471 (1.0)
Computation Time (s)
0.5
18.2
0.4
0.4
Table 3: Performance of trained policies on unknown Circuit environments. The values in the table are the obtained rewards, and inside the parenthesis are the probabilities of crashing. Time stands for the computation time consumed in making 100 action steps. Note that our method never crashes in this experiment. this experiment, every crash penalized by 1500pts.
17

---

Under review as a conference paper at ICLR 2021
Environment
approx. RP
MPC (3steps)
DQN (A=5)
DQN (A=500)
78.2 (0)
55 (0.05)
59.2 (0.04)
-72.1 (0.17)
N 88 (training env.)
69.1 (0)
-24.7 (0.2)
-123.9 (0.38)
-109 (0.24)
N 15
24.0 (0.02)
-165.9 (0.45)
-280.5 (0.66)
-246.3 (0.51)
Computation Time (8)
1.2
285
0.4
Table 4: Performance of trained policies on and unknown Jam environments. Values in the table are reported in the same way as in T In this experiment, every crash is penalized by 500 pts. Note that we achieve the lowest crashing rate while achieving high score.
I ADDITIONAL RELATED WORK
As mentioned in the introduction, one classic strategy for safe maximization of the reward is MPC, which uses simulator/generator
directly predict the outcome of candidate actions. There are
many applications and variations of this approach (Maciejowski 2002) Yoshida et al. [0088] Wang &
Boyd 2010; Di Cairano et al. 2013 Liu & Jr 2014] Weiskircher et al.] [017]] Rasekhipour et al.
2016b). One straight forward approach for constrained Markov Decision process is to formulate the objective with Lagrange multiplier. This approach has been used widely in practice, including (Geibel & Wysotzki 2005 Geibel 2006 [Uchibe & Doya 2007 Everett et al. 2018 Walraven &
Spaan 2018 Paternain et al. (2019) and CPO(Achiam et al. 2017a). CPO a method that gradually improves the safe policy by making local search for better safe policy in the neighborhood of the current safe policy. By nature, at each update, CPO has to determine whether a suggested member in the neighborhood of current safe policy satisfies the safety constraint. In implementation, this is again done by the evaluation of Lagrange coefficients. Accurate selection of safe policies in the neighborhood is especially difficult when the danger be avoided is "rare" and "catastrophic", because we would need massive number of samples to verify whether a given policy is safe or not. This is problem common to all approaches using the Lagrange multipliers, because the optimization of Lagrange coefficient requires accurate evaluation of the expected danger. Moreover, because each update is incremental, we have to repeat this process multiple times (usually, several dozens of times for Point Circle, and several thousands of times for Ant Gather and Humanoid Circle). Lyapunov based approach (Chow et al., 2018 2019) are also similar in nature. At each step of the algorithm. Lyapunov based approach uses margiy function c-a state-dependent measure of how bold the agent can be while remaining safe- to construct a set of safe policies the neighborhood of the baseline policy. For the accurate computation of the margin, one must use the transition probability to solve a linear programming problem in the space whose dimension equals the number of states the system. This computation requires [[] (I 2)) computation time. Especially when dealing with system with rare dangerous events, the set of policies found this way may still contain unsafe policies. Reachability analysis is a theory that provides safety guarantee. However, they built their theory on more restrictive setting than the one we consider here (Takei et al.) Ding et al. Summers al. Rasekhipour al. 2016a). Model-checking another approach guarantee the safety. Once the constraints are represented in the form of temporal logic constraints or computation-tre logic (Baier al., 2003 Wen et al. 2015 Bouton et al. 2019). we can ensure the safety by using model checking systems. However, it is sometimes difficult to express the constraints in such structured form. Also, even when we can represent the constraints in the structured form, the computational cost can be heavy. When the state-action space is large, the computation time required for the model-checking system can become prohibitively heavy.
18


Reviews:
[{"review_id": "iepV_udRuYn", "reviewer": "AnonReviewer2", "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": "This paper proposes an approach to learning safe reinforcement learning policies using a simulator. The main idea is to consider essentially two distinct reward functions on the same MDP, one quantifying the risk/safety level of the states, and the other quantifying the usual reward. A policy is first trained to optimize safety, and then a policy is trained to optimize reward, subject to remaining in the safe region, i.e., subject to a constraint given by the Q function for the safety MDP. If the policy enters an unsafe state, it is required to follow the policy for the safety MDP; the paper includes some theoretical results demonstrating that this is an adequate way to ensure the expected safety remains above a given threshold.\n\nActually, the paper also proposes to decompose the safety reward into scores w.r.t. various events such as colliding with the various objects in the environment, and uses a linear combination of these component scores to obtain an aggregate safety score. This approach provides estimates of the safety scores in novel environments, for example where the configuration of the environment is changed, or with a different number of obstacles. Experiments suggest that the resulting approach is much computationally lighter than model-predictive control, and obtains the safest execution across the various methods considered. The reward obtained remains competitive overall.\n\nThe one downside here is the assumption of a simulator, which is pretty strong. It is true that pure sampling alone is never going to be able to provide a strong safety guarantee, and some kind of assumption is going to be necessary to obtain a strong guarantee, so I don't fault the use of some assumption. At the same time, the existence of the simulator does not make the problem trivial, as the optimization remains challenging, and the relative efficiency of the proposed approach is an argument in its favor. The approach is pretty effective overall and has some nice generalization properties. I recommend acceptance.\n\nOne question I have is whether the decomposition of the environment's threats into different factors could be used with other methods: if the dimension of the state space is sufficiently small, then maybe for example the synthesis (model checking/reachability) methods could be feasibly applied.", "extra_scores": {}, "extra_text": {}}, {"review_id": "iHDiffAL3FY", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "Summary: The paper studies problems that can be modelled as constrained markov decision processes (CMDPs). It proposes to solve the CMDP by decomposing it into a pair of MDPs; i) a reconnaissance MDP (R-MDP) that is trained with the help of a generative model, and ii) a planning MDP (P-MDP) that is trained given a threat function (i.e., previously trained for the R-MDP). The decomposition approach is tested over some classical benchmarks.\n\nStrengths:\n\ni) The motivation, organization and the overall writing of the paper are clear.\n\nWeakness:\n\ni) The paper seems to be missing out related works [1,2,3,4,…] that can solve C-(PO)MDPs, which could have been used as baselines (i.e., instead of DQN). Therefore it is not clear if the following claim is true or not: “Although our method does not guarantee to find the optimal solution of the CMDP problem, there has not been any study to date that has succeeded in solving a CMDP in dynamical environments as high-dimensional as the ones discussed in this study.”. Overall, I would say this is the weakest part of the paper.\n\nii) It is not clear if the selected experimental benchmarks are challenging. Looking at Table 1 and 2, it seems either i) the selected domains do not benefit from long-term planning, and/or ii) the proposed method learns short-sighted policies. That is in Table 2 for N=15, the proposed method performs similar to MPC over 3 steps.\n\niii) The experimental results require better presentation. For example, since one of the main arguments is that the proposed methodology can solve high-dimensional problems, it would be great to note the dimensionality of the benchmarks in the beginning of section 4. Moreover, none of the figures are readable and are left mostly unexplained.\n\nReferences:\n\n[1] Reinforcement Learning for MDPs with Constraints, Geibel, ECML 2016.\n\n[2] Monte-Carlo Tree Search for Constrained MDPs, Chen et al., IJCAI 2018.\n\n[3] Column Generation Algorithms for Constrained POMDPs, Walraven and Spaan, JAIR 2018.\n\n[4] Hindsight Optimization for Hybrid State and Action MDPs, Raghavan et al. AAAI 2017.", "extra_scores": {}, "extra_text": {}}, {"review_id": "WLlDpCjhDTA", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "This paper attempts to propose a practical method for solving constrained MDP via decomposing the original problem into two MDPs. In the first phase, it uses a generative model to solve the MDP with the original constraint being the cost. The policy is then used to define secure actions to help solving the second MDP that maximizes the reward. While the method does not guarantee to find the optimal safe policy, the authors claim (and show in few experiments) that it can perform better than classical methods.\n\nWhile the approach seems simply and intuitive, it is not clear whether the contributions are significant for the community. The decomposition seems straightforward and the algorithmic innovation does not seem to be significant. All the difficulties of solving the thread function is being resolved by assuming the access to a generative model. In particular, the authors further consider the case where solving the R-MDP is simpler: the danger is described by known risky events and hence sampling rare events with the generative model is easier. As a result, the experiments primarily focus on navigation tasks. More thorough experiments would be appreciated. In addition, beyond MPC, is it possible to add other baselines that use a learning based approach with access to generative model? If possible, I think this will help to further clarify the benefit of the overall idea of decomposition.   ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates safe reinforcement learning with distinct reward function and safety function. The authors present theoretical analysis and simulation results. The representation of safety is a critical step. The authors define the safety function values based on various events and use linear combination of them to construct safety score. Theoretical guarantees on safety and efficiency are presented. Simulation results also show safety and efficiency of the method. 

This was a tricky case as the paper is borderline. Based on reviewers comments, we decided that the paper is not ready for publication in its current form and would benefit from another round revisions. 

Decision: Reject