Safe Reinforcement Learningin Constrained Markov Decision Processes
Akifumi Wachi

Yanan Sui

IBM Research AI

Tsinghua University

1Overview
Details are in page 11 – 18.

2

Background
There is increasing need for automatedexploration of the unknown environment© NASA• Unknown where is safe/unsafe• Unknown where is scientifically worthwhile to visit© NASAAn agent needs to maximize the cumulative
reward while guaranteeing safety.

3

Problem Statement
We consider a safety-constrained Markov Decision Processes (MDPs).

: finite state space: finite action space: deterministic transition: reward function: safety function: discount factor

Problem Formulation

4

Problem Statement• Both reward function 𝑟 and safety function 𝑔
are unknown a priori.
• It is intractable to solve this problem without
further assumptions.

• We adapt two assumptions from Sui et al. (2015) and Turchetta et al. (2016).
• Assumption 1. Agent starts in a set of safe states, which is known to be safe.
•Assumption 2. Reward and safety functions exhibit regularity.
Ø We model them using Gaussian Processes.

Sui et al., A. Safe exploration for optimization with Gaussian processes. In ICML, 2015.

© NASA/JPL
Turchetta et al., A. Safe exploration in finite Markov decision processes with Gaussian processes. In NeurIPS, 2016.

5

Exploration and Exploitation
Explorationof Safety

Turchetta et al. (2016) focusedon exploration of safety.
Key point
How can we balance
the three objectives?

Explorationof Reward

Exploitationof Reward

A great deal of previous work
on RL has focused on this problem
6

Our Main Contribution
Wachi et al. "Safe Exploration and Optimization ofConstrained MDPs using Gaussian Processes." AAAI 2018.
• Safety: probabilistic guarantee• Optimality: no guarantee

This paper: Safe Near-optimal MDP (SNO-MDP)
Wachi and Sui, “Safe Reinforcement Learningin Constrained Markov Decision Processes.” ICML 2020.
• Safety: probabilistic guarantee• Optimality: probabilistic guarantee© NASA/JPL

7

Step-wise Approach
Wachi et al. (2018) tried to solve thethree-way trade-off simultaneously.

This work takes a step-wise approach.
1. Exploration of safety.
2. Optimization of the cumulative reward
in the certified safe region.

Explorationof Safety

Explorationof Reward

Exploitationof Reward

Intuitions. Suppose an agent can sufficiently expand the safe region.
Then, the agent only has to optimize the cumulative reward in the certified safe region.
© NASA/JPL8

Early Stopping of Exploration of Safety• Pure step-wise approach (brown line) has an issue.
• Spend much time for the exploration of safety.
• We additionally proposed early stopping of exploration of safety (ES2).
• ES2 maintains the theoretical guarantees on near-optimality.
• P-ES2 empirically performs better than ES2.

Exploration of Safety© NASA/JPL9

Experiments• Developed a new simulation environment, called GP-Safety-Gym,
which is based on Open AI SafetyGym (Ray et al., 2019).
• Achieved better empirical performance than other baselines.
• SafeMDP (Turchetta et al., 2016)• SafeExpOpt-MDP (Wachi et al., 2018)

Reward (high: yellow , low: blue )Safety: height© NASA/JPL

10

Details

11

Overview of SNO-MDP
Step 1: Exploration of Safety (Turchetta et al., 2016)
loop
Step 1-1: Update of GPs based on the observations
Step 1-2: Conventional terminal condition

This terminal condition isrelated to the “completeness”of the safe region.

Step 2: Exploration and Exploitation of Reward© NASA/JPL12

Overview of SNO-MDP with ES2
Step 1: Exploration of Safety
loop
Step 1-1: Update of GPs based on the observations
Step 1-2: Conventional terminal condition
Step 1-3: ES2 algorithm

If ES2 algorithm identifies that “exploration of safety”
can be stopped, then break the loop.
Step 2: Exploration and Exploitation of Reward© NASA/JPL13

Step 1: Exploration of Safety
To expand the safe region, we use the same scheme
as in Turchetta et al. (2016).
1) Probabilistic Safety Guarantee
Original safety constraint:

If a stateー safety function
ー threshold・ observation

satisfies the following condition,

safety is guaranteed with high probability.

Lower bound of 𝑔 inferred by GP.
© NASA/JPL14Step 1: Exploration of Safety
2) Expansion of Safe Region• The efficiency of expanding the safe region is measured
by the width of the safety function’s confidence interval.

• Sample the next state with the maximum
ー safety function
ー threshold・ observation

within the safe space.
3) Conventional Terminal Condition of Exploration of Safety• The previous work (Sui et al., 2015; Turchetta et al., 2016) terminated the exploration
if the following equation holds for all states in safe space.

© NASA/JPL15

Step 2: Optimization of Reward• All the agent has to do is optimize the cumulative reward in the certified safe region.
• Leverage algorithms for optimizing unconstrained MDPs.
• A simple approach is to follow the optimism in the face of uncertainty principle.

Probabilistic upper confidencebound of reward

Next state must be inpessimistically identified safe space© NASA/JPL16

ES2 algorithm• Consider a new MDP, where reward function is defined as in the figure below.
• Reward is set to be the lower bound in the currently identified safe region.
• Otherwise, set to be the upper bound.
• This reward settings encourage the agent to explore outsides the currently identified safe region.
• Suppose the set of next states thatthe agent will visit based on the
optimal policy is a subset of thecurrently identified safe region

Identifiedunsaferegion

Uncertainregion
Identified saferegion
Reward: lower bound•we can stop exploring the safetyfunction.

Reward:upper bound17

Conclusion• We have proposed SNO-MDP, a stepwise approach for exploring and optimizing asafety-constrained MDP.
• Theoretically, we proved a bound of the sample complexity to achievenear-optimal policy while guaranteeing safety, with high probability.
• We also proposed the ES2 algorithm for improving the efficiency in obtaining rewards.
• We developed GP-SAFETY-GYM to test the effectiveness of SNO-MDP.
• Our proposed algorithm, SNO-MDP overperforms other baselines.

© NASA/JPL18

Thank you!

19