Safe Exploration and Optimization ofConstrained MDPs using Gaussian Processes
Akifumi Wachi (Univ. Tokyo), Yanan Sui (Caltech)
Yisong Yue (Caltech), Masahiro Ono (NASA/JPL)
February 5, 2018
AAAI Conference on Artificial Intelligence1

Background
There is increasing need for automated explorationof the unknown environment• Unknown where is dangerous/safe• Unknown where is scientifically worthwhile to visit

Hsu, Hsiang-Wen; Postberg, Frank; et al. (March11, 2015).

2

Problem Statement
We would like an agent to:• Obtain scientifically valuable data
• Guarantee safety© NASAProblem formulation: state vector: terminal time step

: reward function: safety threshold: safety function: discount rate

We assume that reward and safety are a priori unknown.
© NASA/JPL3

Our Contributions
Reinforcement learning[Sutton and Barto, 1998;
Bertsekas and Tsitsikils, 1995]

Risk-Sensitive Decision Making[Schwarm and Nikolaou, 1999;
Blackmore et al., 2010]

Add risk-sensitivity(Safety constraint)

Assume that safety
is a priori unknown
Our research4

Exploration & Exploitation
If you were a treasure hunter, what would you do?
• Collect treasure which has been already identified?
• Seek more valuable treasure?
• Try to search safe region？

Such a problem is called exploration/exploitation problem
5

Three-way trade-off
Check where is safe/dangerous

Explorationof safety© NASAExploitationof reward

Explorationof reward

Collect alreadyrecognized reward

Seek higher reward6How should we deal with safety?
It is difficult to guarantee safety because ...

It is too late to realize the hazard after hitting it!
Just single mistake may result in failure.
We must predict hazards before actually visitingunsafe states.
7

How should we deal with safety?
Parameters in natural environments have some regularity

We assume that similar states have similar values ofsafety function.
Evaluate safety function using Gaussian Processes (GPs)8Gaussian Processes
Safety constraint:

ThresholdAn agent can guarantee safety with high probability.
(For more detail, see our paper.)9

Exploration/Exploitation Problem
Explorationof safety

M. Turchetta et al. (2016)
focuses on exploration ofsafety.

Key point
How can we balance
the three objectives?

Exploitationof reward

Explorationof reward

A great deal of previous workin the field of reinforcement learning
has worked on this problem

11Classification of State Space• Classify the state space into three regions using GP→ safe space, uncertain space, risky space
Pessimistic (Blue: safe, Red: uncertain or risky)

True(Blue: safe, Red: risky)

Time

10%

40%

60%

Optimistic (Blue: safe or uncertain, Red: risky)

12

Introduction of Delta-J
Difference of cumulative reward for Optimistic and Pessimistic
cases means the need for exploration of safety
Optimistic Pessimistic
Optimistic

Pessimistic

Difference is big → “exploration of safety” is necessary
13
Difference is small → it is OK to focus on reward

Overall Policy
exploration/exploitation

explorationof rewardof safetyvalue function for
Optimistic casevalue function for
Pessimistic caseAn agent should choose a state with the maximum valueof the dividing point of optimistic and pessimistic cases.
14

Algorithm flow
Reasoning of reward and safety function
via Gaussian Process Regression
Classification in terms of safety

Solve optimistic MDP

Solve pessimistic MDP

Obtain Δ𝐽

Execution of optimal action
15

Simulation result
Proposed method Safety/reward known: safe region: Uncertain or unsafe region

M. Turchetta et al.

Safety known

16

Mars Surface Exploration Example
Conducted a simulation using Mars terrain data basedon real Mars surface exploration scenario.
• Safety function: slope angle• Threshold: 25deg• Reward function: binary (one within in ROI)
Result• Succeeded in arriving at ROI
while guaranteeing safety.
• Proved that our proposed
method can be applied topractical applications

PathRegion ofinterest (ROI)
18

Conclusion
1. Formulate a problem in which a MDP is safelyexplored and optimized with a priori unknown
reward and safety
2. Propose an algorithm to balance exploration of reward,
exploitation of reward, and exploration of safety
3. Demonstrate the effectiveness of our proposed
method by the three types of simulation including
one using real Martian data

19