Hierarchical Reinforcement Learningwith Unlimited Recursive Subroutine Calls
2019-09-17 ICANN 20191

Humans can set suitable subgoals
recursively to achieve certain tasks
Initial state"the ladder is set up"

Set up a ladder

Initial state

Take an object
on a high shelf"in the store room"

Go to the store room

Initial state

Goal state:"holding the object"

Subgoal state:"the ladder is set up"

Carry the ladder

Sub-subgoal state:"in the store room"
The depth of this recursion is apparently unlimited.

2

Hierarchical reinforcement learning
architecture RGoal• In RGoal, an agent's subgoal settings are similar tosubroutine calls in programming languages.
• Each subroutine can execute primitive actions orrecursively call other subroutines.
• The timing for calling another subroutine is learned
by using a standard reinforcement learning method.
• Unlimited recursive subroutine calls acceleratelearning because they increase the opportunity forthe reuse of subroutines in multitask settings.
3

Previous work: MAXQ [Dietterich 2000]• Multi-layered hierarchical reinforcement
learning architecture with a fixed number oflayers.
• Accelerates learning speed• Subtask sharing, Temporal abstraction, State abstraction

RGoal simplifies MAXQ archicecture and extends its feature.

4

RGoal architecture
Agent

Reward Augmented state𝑠𝑠̃ = (𝑠𝑠, 𝑔𝑔)
function𝑟𝑟(𝑠𝑠̃ , 𝑎𝑎�)

Reward 𝑟𝑟

Action value function
𝑄𝑄𝐺𝐺 𝑠𝑠̃ , 𝑎𝑎�= 𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎� + 𝑉𝑉𝐺𝐺 (𝑔𝑔)Augmentedaction 𝑎𝑎�

State 𝑠𝑠Sensor

Subgoal 𝑔𝑔

Environment

Stack

Subroutine call 𝐶𝐶𝑚𝑚Action 𝑎𝑎

Actuator

The agent has a subgoal and a stack as its internal states.

5Augmented state-action space
𝒮𝒮 = 0,0 , 0,1 , …
𝒜𝒜 = 𝑈𝑈𝑈𝑈, 𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷, 𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅, 𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿, …

Left

𝑠𝑠Down𝒮𝒮̃ = 𝒮𝒮 × ℳ
𝒜𝒜̃ = 𝒜𝒜 ∪ 𝒞𝒞ℳℳ = {𝑚𝑚1 , 𝑚𝑚2 , … } ⊆ 𝒮𝒮
𝒞𝒞ℳ = 𝐶𝐶𝑚𝑚1 , 𝐶𝐶𝑚𝑚2 , …

Left

Down

[Levy and Shimkin 2011]

Up
Right

augment

RGoal solves the Markov Decision Process(MDP) in the augmented state-action space.

Up

𝑠𝑠𝐶𝐶𝑚𝑚2
𝐶𝐶𝑚𝑚3

Right

The augmented state is a pair of state andgoal 𝑠𝑠̃ = (𝑠𝑠, 𝑔𝑔) .
The augmented action 𝑎𝑎� is a primitiveaction 𝑎𝑎 or a subroutine call 𝐶𝐶𝑚𝑚 .

𝑔𝑔 = 𝑚𝑚1𝑔𝑔 = 𝑚𝑚2𝑔𝑔 = 𝑚𝑚3

Unlike previous hierarchical RLs, caller andcallee relation between subroutines is notpredefined, but is learned within theframework of RL.
(Subroutine call is just a state transition inthe augmented state-action space.)
6

Value function decomposition[Singh 1992][Dietterich 2000]• Action value function 𝑄𝑄 is decomposed into two parts:
before subgoal

after subgoal

𝑄𝑄𝐺𝐺𝜋𝜋 (𝑠𝑠, 𝑔𝑔), 𝑎𝑎 = 𝑄𝑄𝜋𝜋 𝑠𝑠, 𝑔𝑔, 𝑎𝑎 + 𝑉𝑉𝐺𝐺𝜋𝜋 𝑔𝑔

where 𝑉𝑉𝐺𝐺𝜋𝜋 𝑔𝑔 = Σ𝑎𝑎 𝜋𝜋 𝑔𝑔, 𝐺𝐺 , 𝑎𝑎 𝑄𝑄𝜋𝜋 𝑔𝑔, 𝐺𝐺, 𝑎𝑎
G : original global goalg : current subgoal•

𝑄𝑄(𝑠𝑠, 𝑔𝑔, 𝑎𝑎) can be shared between tasks because it does notdepend on the original goal G.
– Accelerates learning speed

7Update rule of Q(s,g,a) is derived
from the standard Sarsa algorithm
𝑄𝑄 𝑠𝑠̃ , 𝑎𝑎� ← 𝑄𝑄 𝑠𝑠̃ , 𝑎𝑎� + 𝛼𝛼(𝑟𝑟 + 𝑄𝑄 𝑠𝑠̃ ′, 𝑎𝑎�′ − 𝑄𝑄 𝑠𝑠̃ , 𝑎𝑎� )When subgoal is g and stack contents are g1,g2,...gn,
the agent moves though the path: s -> g -> g1 -> g2 -> ... -> gn .
If a subroutine g' is called, the changed path is: s -> g' -> g -> g1 -> g2 -> ... -> gn .
Therefore, the equation bellow holds:

𝑄𝑄𝑔𝑔𝑛𝑛 𝑠𝑠̃ ′, 𝑎𝑎�′ − 𝑄𝑄𝑔𝑔𝑛𝑛 𝑠𝑠̃ , 𝑎𝑎�= 𝑄𝑄 𝑠𝑠 ′ , 𝑔𝑔′ , 𝑎𝑎�′ + 𝑉𝑉𝑔𝑔 𝑔𝑔′ + 𝑉𝑉𝑔𝑔1 𝑔𝑔 + 𝑉𝑉𝑔𝑔2 𝑔𝑔1 + ⋯ + 𝑉𝑉𝑔𝑔𝑛𝑛 𝑔𝑔𝑛𝑛−1− 𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎� + 𝑉𝑉𝑔𝑔1 𝑔𝑔 + 𝑉𝑉𝑔𝑔2 𝑔𝑔1 + ⋯ + 𝑉𝑉𝑔𝑔𝑛𝑛 𝑔𝑔𝑛𝑛−1= 𝑄𝑄 𝑠𝑠 ′ , 𝑔𝑔′ , 𝑎𝑎�′ − 𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎� + 𝑉𝑉𝑔𝑔 𝑔𝑔′
This equation also holds when 𝑎𝑎� is not a subroutine call,but is a primitive action. Therefore:

𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎 ← 𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎 + 𝛼𝛼(𝑟𝑟 + 𝑄𝑄 𝑠𝑠′, 𝑔𝑔′, 𝑎𝑎′ − 𝑄𝑄 𝑠𝑠, 𝑔𝑔, 𝑎𝑎 + 𝑉𝑉𝑔𝑔 𝑔𝑔′ )Efficiently executed.

8Maze task■■■■■■■■■■■■■■■■■■■■■■■■■■・・ｍ・・・・・・・・・・・・・・■・・・・ｍ■■・・・・・■・・ｍ・・・・・・・ｍ■・・・・・■■・・・・・■■■■■・・・・■■■■・・・・・■■・・・・ｍ・・・・■・・・・・■・・・・・・・■■・・・・・■・・・■ｍ・・・ｍ■・・・・・・・■■・・・・・■・・・■■■・・・・・ｍ・・・・・■■・・・・・■・ｍ・・・■・・・・・■・・・・ｍ■■・・・ｍ■■・・・・・■・・・・・■・・・・・■■・・・・・■・・・・・■ｍ■・・・■・・・・・■■・・・・・■・・・■・■・■・・・・・・・・・■■・・・・・・・・・・ｍ■・・・・・・・■・・・■■■■■■・・・・・・・■■■■・・・・■ｍ・・■■・・ｍ■・・・・・・・・・・■・・・・■■■■■■・・・■・・ｍ・・・ｍ・・・■ｍ・・・・・・・■■・・・・・・・・・・■・・・■■■・・・・・・■■・・・・・・・・・・■・・・・・・・・・・・・■■・・・■・・・ｍ・・■・・・・・・・ｍ・・・・■■■■■■■■■■■■■■■■■■■■■■■■■■

m : landmark

Twenty landmarks are placed on
the map.
Landmarks may become subgoals.
For each episode, the start S andgoal G are randomly selectedfrom the landmark set.
We focus on convergence speed
to suboptimal solutions, rather
than exact solutions.
9Experiment 1. Relationship between the upper limit Sof the stack depth and RGoal performance
0.08

episodes/steps

0.07

No subroutine calls(Sarsa)0.06

S=00.05

S=1
S=20.04

S=30.03

Hierarchical RL
without recursive calls

S=4
S=1000.02
0.01
01

357

911 13 15 17 19 21 23 25 27 29 31 33 35 37 39

x 100,000 steps
A greater upper limit results in faster convergencebecause it increases the opportunity for the reuse of subroutines.

10

"Thought-mode" combines learned simple tasks tosolve unknown complicated tasks• Suppose that the optimal routes
between all neighboring pairs of
m1
landmarks have been already learned.
• An approximate solution for the optimalroute between distant landmarks can beobtained by connecting neighboringm1
landmarks.
• Such solutions can be found without
taking any actions within theenvironment. [Singh 1992]– Found by simulations within theagent's brain• A kind of Model-based RL• A kind of Deductive reasoning

m4

m2

m3

m3
m2

11

Before evaluation of Thought-mode,
the agent learns simple tasks■■■■■■■■■■■■■■■■■■■■■■■■■■・・ｍ・・・・・・・・・・・・・・■・・・・ｍ■■・・・・・■・・ｍ・・・・・・・ｍ■・・・・・■■・・・・・■■■■■・・・・■■■■・・・・・■■・・・・ｍ・・・・■・・・・・■・・・・・・・■■・・・・・■・・・■ｍ・・・ｍ■・・・・・・・■■・・・・・■・・・■■■・・・・・ｍ・・・・・■■・・・・・■・ｍ・・・■・・・・・■・・・・ｍ■■・・・ｍ■■・・・・・■・・・・・■・・・・・■■・・・・・■・・・・・■ｍ■・・・■・・・・・■■・・・・・■・・・■・■・■・・・・・・・・・■■・・・・・・・・・・ｍ■・・・・・・・■・・・■■■■■■・・・・・・・■■■■・・・・■ｍ・・■■・・ｍ■・・・・・・・・・・■・・・・■■■■■■・・・■・・ｍ・・・ｍ・・・■ｍ・・・・・・・■■・・・・・・・・・・■・・・■■■・・・・・・■■・・・・・・・・・・■・・・・・・・・・・・・■■・・・■・・・ｍ・・■・・・・・・・ｍ・・・・■■■■■■■■■■■■■■■■■■■■■■■■■■In the pre-training phase, onlypairs of the start and goal
within Euclidean distances ofeight are selected.
In the evaluation phase,
arbitrary pairs are selected.

m : landmark

12Experiment 2. Relationship between the length P of
the pre-training phase and RGoal performance
0.14

episodes/steps

0.12

0.1

0.08

P=0
P=10000.06

P=2000

0.04

0.02

01

3

57

9

11 13 15 17 19 21 23 25 27 29 31 33 35 37 39

x 100,000 steps
A greater value of P results in faster convergence
If an agent learns simple tasks first, learning difficult tasks becomes
faster because the learned simple tasks can be reused as subroutines.

13Experiment 3. Relationship between thought-mode
length T and RGoal performance
0.08

0.06
0.05

T=0
T=1

0.04

T=10

0.03

T=100

0.02
0.01

T is the number ofsimulations executed
prior to the actual
execution of each
episode.
Here, we only plot thechange in score after
the pre-training phase.

02001
2005
2009
2013
2017
2021
2025
2029
2033
2037
2041
2045
2049
2053
2057
2061
2065
2069
2073
2077
2081
2085
2089
2093
2097

episodes/steps

0.07

x 1,000 steps
If thought-mode length is sufficiently long, approximate solutions
are obtained in almost zero-shot time.

14

Pseudo code of RGoal
This algorithm only uses simple
data structures and a simple
single loop.
Because of its simplicity, weconsider RGoal to be a
promising first step toward a
computational model of theplanning mechanism of thehuman brain.

15

Conclusion• We proposed a novel hierarchical RL architecture that allows
unlimited recursive subroutine calls.
• We integrated several important ideas proposed before into asingle simple architecture.
– Augmented action-value space[Levy and Shimkin 2011],– Value function decomposition[Singh 1992][Dietterich 2000]– Model-based RL [Sutton 1990]• A novel mechanism called Thought-mode combines learned
simple tasks to solve unknown complicated tasks rapidly,
sometimes in zero-shot time.
• Because the theoretical framework and the architecture ofRGoal is simple, it is easy to extend.
16