Dynamic Shielding for
Reinforcement Learning inBlack-Box Environments
Masaki Waga1, Ezequiel Castellano2, Sasinee Pruekprasert3,
Stefan Klikovits2, Toru Takisaka4, Ichiro Hasuo2
Kyoto University1, National Institute of Informatics2,
National Instutite of Advanced Industrial Science and Technology3,
University of Electric Science and Technology of China4

Originally Presented at ATVA 2022 26th Oct. 2022
1

M. Waga (Kyoto U.)

prevent unsafe exploration

Dynamic Shielding for
Reinforcement Learning inBlack-Box Environments
only for white-box env.
→ also for black-box env.

Masaki Waga1, Ezequiel Castellano2, Sasinee Pruekprasert3,
Stefan Klikovits2, Toru Takisaka4, Ichiro Hasuo2
Kyoto University1, National Institute of Informatics2,
National Instutite of Advanced Industrial Science and Technology3,
University of Electric Science and Technology of China4

Originally Presented at ATVA 2022 26th Oct. 2022
1

M. Waga (Kyoto U.)

Reinforcement Learning (RL)
Actions

Observation/RewardLearns a controller
maximizing the rewardwith trials-and-errors

2

M. Waga (Kyoto U.)

Applications of RL

https://carla.org/2020/04/22/release-0.9.9/
https://www.bbc.com/news/technology-35785875
https://chatbotslife.com/deep-learning-in- nance-learning-to-trade-with-q-rl-and-dqns-6c6c 4a1429

M. Waga (Kyoto U.)
fffi

3

Applications of RL

https://carla.org/2020/04/22/release-0.9.9/
https://www.bbc.com/news/technology-35785875
https://chatbotslife.com/deep-learning-in- nance-learning-to-trade-with-q-rl-and-dqns-6c6c 4a1429

M. Waga (Kyoto U.)
fffi

3

Applications of RL

https://carla.org/2020/04/22/release-0.9.9/
https://www.bbc.com/news/technology-35785875
https://chatbotslife.com/deep-learning-in- nance-learning-to-trade-with-q-rl-and-dqns-6c6c 4a1429M. Waga (Kyoto U.)
fffi3

RL with Physical Env.

yamsnoitcaelbarisednUWHkaerb)yll(eventuaActions

Observation/Reward
https://www.roscomponents.com/1326-thickbox_default/turtlebot-3.jpg
https://web.archive.org/web/20190417171518if_/http://emanual.robotis.com/assets/images/platform/turtlebot3/challenges/autorace_dankook_1.jpg

4

M. Waga (Kyoto U.)

Q. Can we prevent
undesired actions during
training?
A. Yes if we have someprior knowledge of env.
5

M. Waga (Kyoto U.)

Safe RL with Shielding[Alshiekh+, AAAI’18]

Safe Actions

Safe Action

Observation/RewardAction/Observation

6

M. Waga (Kyoto U.)

Safe RL with Shielding[Alshiekh+, AAAI’18]

Safe Actions

Safe Action

Observation/Reward
System Model

𝒫

Spec.
No Crash

Strategy

σ : Loc →Action/Observation
(Act)

6

M. Waga (Kyoto U.)

Safe RL with Shielding[Alshiekh+, AAAI’18]

Safe Actions

Safe Action

Observation/Reward
System Model𝒫Spec.
No Crash

Strategy

σ : Loc →Action/Observation(Act)

6Requires!
!
ledommetsys
M. Waga (Kyoto U.)

Q. Can we reduce
undesired actions
during training
without prior systemmodel?
7M. Waga (Kyoto U.)

Dynamic Shielding
Safe Actions[Contribution]

Safe Action
acc.

acc.

System ModelSpec.
No Crash

Strategy

σ : Loc →𝒫

gninrae
Latamotu
Aev
iss
Pa

(Act)

Observation/RewardAction/Observation

8M. Waga (Kyoto U.)

Contributions•Introduce the dynamic shielding scheme• Idea: passive automata learning + shielding•Modi ed RPNI algorithm for passive autom. learning• to maintain necessary exploration•

Experiment results show that dynamic shielding
reduces # of undesired actions during training

fi9

M. Waga (Kyoto U.)

Outline•

Preliminaries•

Static shielding•

RPNI algorithm for passive automata learning•

Dynamic shielding + modi cation of RPNI algorithm• Idea 1: passive automata learning + shielding• Idea 2: additional requirements to deem twosequences are the same•

Experimentsfi

10

M. Waga (Kyoto U.)

[Alshiekh+, 2018]

Action +Observation(a,o)•+Shield is stateful, i.e., Shield: (Act × Obs)

→We use a shield with nite state space→ Mealy machine with input: Act × Obs, output:
11fi•

Safe Actions{a1, a2, …, an}

(Act)
(Act)

𝒫𝒫(Preemptive) Shield

M. Waga (Kyoto U.)

Shield Synthesis
1. Given: system model ℳ and speci cation φ• ℳ: Mealy machine with 2 players• φ: safety LTL formula

2. Construct a safety gameby combining ℳ and φ

𝒢𝒢

3. Solve to obtain the set of winning actions→ Use it as the safe actions

M. Waga (Kyoto U.)
fi12

Safe RL with Shielding[Alshiekh+, AAAI’18]

Safe Actions

Safe Action

Observation/RewardAction/Observation

13

M. Waga (Kyoto U.)

Safe RL with Shielding[Alshiekh+, AAAI’18]

Safe Actions

Safe Action

Observation/Reward
Statically synthesizedwith prior systemknowledge

Action/Observation

13

M. Waga (Kyoto U.)

Outline•

Preliminaries•

Static shielding•

RPNI algorithm for passive automata learning•

Dynamic shielding + modi cation of RPNI algorithm• Idea 1: passive automata learning + shielding• Idea 2: additional requirements to deem twosequences are the same•

Experiments

fi14

M. Waga (Kyoto U.)

Passive Automata Learning &RPNI-style Algorithm for Mealy machines[Oncina & Garcia,1992]+Given: Set T ⊆ Act × Obs of words with labels(training data)
Learn: Mealy machine ℳ compatible with Ti.e. ∀(w, o) ∈ T . ℳ(w) = o
Idea:
1. Construct a pre x tree T̃ from T

2. Merge nodes of T̃ unless it makes
nondeterministic branchingfi15

M. Waga (Kyoto U.)

RPNI-style algorithm forMealy machines
1. Construct a pre x tree T̃ from TInitial pre x tree representing the training data

n3b/ln6b/r

n8a/r

n1a/r
n0b/l

n4b/r

n7a/ln9b/ln10b/l
n2a/ln5fifi

16

M. Waga (Kyoto U.)

RPNI-style algorithm for
Mealy machines
1. Construct a pre x tree T̃ from T

Initial pre x tree representing the training data

n3b/l

n6b/r

n8a/r

n1a/r
n0b/l

n4b/r

n7a/l

n9b/l

n10b/ln2a/ln5fifi16

M. Waga (Kyoto U.)

RPNI-style algorithm for
Mealy machines2. Merge nodes of T̃ unless it makes
nondeterministic branching…

Compatible?
n3n0n6b/r

n8a/r

Compatible?
a/rb/l

n1b/l

n4b/r

n7a/l

n9b/l

n10b/ln2a/ln5Compatible?

17

M. Waga (Kyoto U.)

RPNI-style algorithm for
Mealy machines

2. Merge nodes of T̃ unless it makes
nondeterministic branching

n3n0n6b/r

n8a/r

Compatible?
a/rb/l

n1b/l

n4b/r

n7a/l

n9b/l

n10b/ln2a/l

n517

M. Waga (Kyoto U.)

RPNI-style algorithm for
Mealy machines

2. Merge nodes of T̃ unless it makes
nondeterministic branching
n3Compatible
a/r
n0b/l

n6b/r

n8a/r
b/l

n1n4b/r

n7a/l

n9b/l

n10b/la/l

n2n0 and n1 are merged

n5a/r
a/l
n0b/l

n2n5b/rn718a/l

n9b/l

n10

M. Waga (Kyoto U.)

RPNI-style algorithm for
Mealy machines

2. Merge nodes of T̃ unless it makes
nondeterministic branchinga/ra/ln0b/ln2n5b/rn7a/lb/ln10n0 and n9 are merged

Compatible

a/l
a/rb/ln0n9n5n2b/r
a/l

19n7

M. Waga (Kyoto U.)

RPNI-style algorithm forMealy machines

2. Merge nodes of T̃ unless it makes
nondeterministic branchinga/l
a/rb/ln0

Final result withno compatible nodes

n5n2b/ra/lCompatible
n7n2 and n7 are mergeda/r

n0b/rb/l

n2a/l
20

M. Waga (Kyoto U.)

Observation of the RPNI
Learns a small Mealy machine by merging nodes••Generalization in machine learning

No data → can be anything•Result can be largely di erent from the ground truth
if the training data is small21ff•

M. Waga (Kyoto U.)

Outline•

Preliminaries•

Static shielding•

RPNI algorithm for passive automata learning•

Dynamic shielding + modi cation of RPNI algorithm• Idea 1: passive automata learning + shielding• Idea 2: additional requirements to deem twosequences are the same•

Experiments

fi22

M. Waga (Kyoto U.)

Idea of Dynamic Shielding
Explicitly learn the outcome of the actions→ exploit it to avoid undesired behavior•

In the beginning, we know nothing→ We cannot guarantee anything•

At a certain point, we know some of the unsafe actions→ Use this information to prevent same mistake•

By generalization, we also prevent similar mistakes

23

M. Waga (Kyoto U.)

Dynamic Shielding
Safe Actions[Contribution]

Safe Action
acc.

acc.

System ModelSpec.
No Crash

Strategy

σ : Loc →𝒫gninrae
Latamotu
Aev
iss
Pa

(Act)

Observation/Reward
Action/Observation

24

M. Waga (Kyoto U.)

Dynamic Shielding
Safe Actions[Contribution]

Safe Actionacc.

acc.

System ModelSpec.
No CrashStrategy

σ : Loc →𝒫gninrae
LatamotuAev
issPa(Act)

Observation/RewardAction
Previous Observations as training data
/Observation
a1, a2, …, an → o1
a’1, a’2, …, a’n’ → o2
a’’1, a’’2, …, a’’n’’ → o3
⋮24

M. Waga (Kyoto U.)

Dif culties in Dynamic Shielding•

Exploration is prevented if deemed to be unsafe•

At an early state, the training data is limited•

Learned model is unreliable

Learning algorithm should not merge nodes if thecon dence of the similarity is low••

Otherwise, necessary exploration may be preventedfifi25

M. Waga (Kyoto U.)

RPNI algorithm with additional
merging requirements[Contribution]

Idea: merge nodes only if we are con dent enoughEvidence of the con dence:common children with enough depth•Example: minimum depth = 2Compatible

n0

n6b/r

n8a/r

n1

a/r

b/l

n3b/l

b/r

n4

n7a/l

n9b/l

n10b/ln2a/ln5Common children: “a/r, b/l, b/r” of depth 3→ con dent enoughM. Waga (Kyoto U.)
fi

fi

fi

26

RPNI algorithm with additional
merging requirements[Contribution]

Idea: merge nodes only if we are con dent enoughEvidence of the con dence:•common children with enough depth

Example: minimum depth = 2
a/r
n5a/l
b/l

n0n2b/r
n7a/l

n9b/l

n10

Compatible but no common children with depth ≥ 2→ we do not merge them!
M. Waga (Kyoto U.)
fifi27

Heuristics to adaptively decideminimum depth[Contribution]••

Merging should be less greedy in the beginningbecause:•the training data is small•

we want varletry exploration

Adaptively decide the minimum depth based on theepisode length
N•

Concretely:epmax − ∑i=0 | epi | /NN
∑i=0 | epi | /N

, with epmax: maximum episode length
N

∑
i=028

| epi | /N: average episode length
M. Waga (Kyoto U.)

Outline•

Preliminaries•

Static shielding•

RPNI algorithm for passive automata learning•

Dynamic shielding + modi cation of RPNI algorithm• Idea 1: passive automata learning + shielding• Idea 2: additional requirements to deem twosequences are the same•

Experiments

fi29

M. Waga (Kyoto U.)

Setting of Experiments•

Implemented dynamic shielding with Python3 and Java•

Used 7 benchmarks mostly from the literature•••

discrete, continuous ([−1,1]4), and image observation

Baselines:•

RL with no safety mechanism (Plain)•

RL with safe padding (SafePadding)• A shielding-style method for black-box setting• No generalization by state merging• Di erent construction

AMD EPYC 7702P, NVIDIA GeForce RTX 2080Ti, 125GiB RAM

ff

30

M. Waga (Kyoto U.)

RQ 1. Safety by Dynamic Shielding
Mean # of training episodes with undesired behaviors
Plain

SafePadding

Dynamic Shielding(Ours)

WaterTank

1883.67

1892.4177.13

GridWorld

6996.47322.235623.43

Cli Walk

1493.21528.67478.20Taxi

8723.132057.33

37.77

SelfDrivingCar

6403.076454.65662.4

SideWalk

373.6

427.93273.37

CarRacing180.13141.17

41.73

ff

31

M. Waga (Kyoto U.)

RQ 1. Safety by Dynamic Shielding
Mean # of training episodes with undesired behaviors
PlainSafePadding

Dynamic Shielding(Ours)

WaterTank

1883.67

1892.4177.13

GridWorld

6996.47322.235623.43

Cli Walk

1493.21528.67478.20Taxi

8723.132057.33

37.77

SelfDrivingCar

6403.076454.65662.4

SideWalk

373.6

427.93273.37

CarRacing180.13141.17

41.73

ff

31

M. Waga (Kyoto U.)

RQ 1. Safety by Dynamic Shielding
Mean # of training episodes with undesired behaviors
Plain

SafePadding

Dynamic Shielding(Ours)

WaterTank

1883.67

1892.4177.13

GridWorld

6996.47322.235623.43

Cli Walk

1493.2≈ 0.4% of Plain
1528.67478.20Taxi

8723.132057.33

37.77

SelfDrivingCar

6403.076454.65662.4

SideWalk

373.6

427.93≈ 23% of Plain

273.37

CarRacing180.13141.17

41.73

ff

31

M. Waga (Kyoto U.)

RQ 2. Controller’s Performance
Mean reward of the resulting controller in the testing phase
Plain

SafePadding

Dynamic Shielding(Ours)

WaterTank

918.89919.81921.81

GridWorld

0.37

0.46

0.07

Cli Walk-69.13-66.00-65.93

Taxi-147.61-139.62-92.93

SelfDrivingCar

28.83

28.86

29.81

SideWalk

0.93

0.90

0.67

CarRacing375.53509.25622.07ff

32

M. Waga (Kyoto U.)

RQ 2. Controller’s Performance
Mean reward of the resulting controller in the testing phase
Plain

SafePadding

Dynamic Shielding(Ours)

WaterTank

918.89919.81921.81

GridWorld

0.37

0.46

0.07

Cli Walk-69.13-66.00-65.93

Taxi-147.61-139.62-92.93

SelfDrivingCar

28.83

28.86

29.81

SideWalk

0.93

0.90

0.67

CarRacing375.53509.25622.07ff≈ 166% of Plain
32M. Waga (Kyoto U.)

RQ 2. Controller’s Performance
Mean reward of the resulting controller in the testing phase
PlainSafePadding

Dynamic Shielding(Ours)

WaterTank

918.89919.81921.81

GridWorld

0.37

0.46

0.07

Cli Walk-69.13-66.00Signi cantly
worse-65.93

Taxi-147.61-139.62-92.93

SelfDrivingCar

28.83

28.86

29.81

SideWalk

0.93

0.90

0.67

CarRacing375.53509.25622.07

fiff≈ 166% of Plain
32

M. Waga (Kyoto U.)

RQ 3. Overhead of DynamicShielding
Mean exec. time [min] of the whole RL process
Plain

SafePadding

Dynamic Shielding(Ours)

WaterTank

31.01

32.45

101.35

GridWorld

2.95

24.79

75.81

Cli Walk

5.926.09

13.98

Taxi

5.601

5.83

10.2

SelfDrivingCar

14.43

81.99

168.12SideWalk

12.71

28.91

106.6

CarRacing

127.5

278.24208.87ff

33

M. Waga (Kyoto U.)

RQ 3. Overhead of Dynamic
Shielding
Mean exec. time [min] of the whole RL process
Plain

SafePadding

Dynamic Shielding(Ours)

WaterTank

31.01

32.45

101.35

GridWorld

2.95

24.79

75.81

Cli Walk

5.92

6.09

13.98

Taxi

5.601

5.83

10.2

SelfDrivingCar

14.43

81.99

168.12SideWalk

12.71

28.91

106.6

CarRacing

127.5

278.24208.87ff

33

M. Waga (Kyoto U.)

RQ 3. Overhead of Dynamic
ShieldingSigni cantly slower(≈ + 1-2 hours)

Mean exec. time [min] of the whole RL process
Plain

SafePadding

Dynamic Shielding(Ours)

WaterTank

31.01

32.45

101.35

GridWorld

2.95

24.79

75.81

Cli Walk

5.92

6.09

13.98

Taxi

5.601

5.83

10.2

SelfDrivingCar

14.43

81.99

168.12SideWalk

12.71

28.91

106.6

CarRacing

127.5

278.24208.87fi

ff

33

M. Waga (Kyoto U.)

RQ 3. Overhead of Dynamic
ShieldingSigni cantly slower(≈ + 1-2 hours)

Mean exec. time [min] of the whole RL processPlain

SafePadding

Dynamic Shielding(Ours)

WaterTank

31.01

32.45

101.35

GridWorld

2.95≈ +70 min. of Plain
24.79

75.81

Cli Walk

5.92

6.09

13.98

Taxi

5.601

5.83

10.2

SelfDrivingCar

14.43

81.99

168.12SideWalk

12.71≈ +81 min. of Plain
28.91

106.6

CarRacing

127.5

278.24208.87≈ +94 min. of Plain

fiff

33

M. Waga (Kyoto U.)

Conclusions & Future works
Improve the safety of exploration in RL with black-box env.
••

Undesired behaviors were signi cantly prevented••

Idea: passive automata learning + shieldingNote: ≫ 0 but (hopefully) still useful for some usage

Current limitation: Leaned system model is deterministic→ Future work: Extension for stochastic models

34fi

•

M. Waga (Kyoto U.)

Appendix

35

M. Waga (Kyoto U.)

Detail of our Implementation•

Implemented in Python3 and Java•

Used libraries (only major ones):•

Stable Baselines 3 or Keras-RL (in Python3): for RL•

LearnLib (in Java): for the RPNI algorithm
Our modi cation of the RPNI algorithm is also in Java••Available at: https://doi.org/10.5281/zenodo.690667336fi•

Bridging between Python3 and Java: py4j

M. Waga (Kyoto U.)

List of the Benchmarks

37

M. Waga (Kyoto U.)

Other Experiment Results(Safety)38

M. Waga (Kyoto U.)

Other Experiment Results(Performance)

39

M. Waga (Kyoto U.)

Example: Limited Exploration
due to Wrong Merging
Simple Grid World (A: agent; G: goal; X: Wall, should not hit)
XXXGXXXXXXX
XX X XXAXXXXXXX

Training Data→ ↑ ← (crash)← ↑ ← (crash)→ ↑ → (crash)← ↑ → (crash)→ ↑ ↑ ↑ (crash) ← ↑ ↑ ↑ (crash)→ ↑ ↑ → (crash)← ↑ ↑ ← (crash)
Outcome of “→ ↑” and “← ↑” seems
the same from the training data“→ ↑ ↑ ←” is deemed to be unsafe

40

M. Waga (Kyoto U.)

Benchmark: Sidewalk
Success

Unsafe41

M. Waga (Kyoto U.)

Benchmark: Sidewalk
Success

Unsafe41

M. Waga (Kyoto U.)

Benchmark: CarRacing
Success

Unsafe42

M. Waga (Kyoto U.)

Benchmark: CarRacing
Success

Unsafe42

M. Waga (Kyoto U.)