IR-VIC: Unsupervised Discovery of Sub-goals for Transfer in RL

1 Introduction

A common approach in reinforcement learning (RL) is to decompose an original decision making problem into a set of simpler decision making problems - each terminating into an identified sub-goal. Beyond such a decomposition or abstraction being evident in humans (e.g. adding salt is a sub-goal in the process of cooking a dish) [Hayes-Roth and Hayes-Roth, 1979], sub-goal identification is also useful from a practical perspective of constructing policies that transfer to novel tasks (e.g. adding salt is a useful sub-goal across a large number of dishes one might want to cook, corresponding to different 'end' goals).

However, identifying sub-goals that can accelerate learning while also being re-usable across tasks or environments is a challenge in itself. Constructing such sub-goals often requires knowledge of the task structure (supervision) and may fail in cases where 1) dense rewards are absent [Pathak et al., 2017], 2) rewards require extensive hand engineering and domain knowledge (hard to scale), and 3) where the notion of reward may not be obvious [Lillicrap et al., 2015]. In this work, we demonstrate a method for identifying sub-goals in an "unsupervised" manner - without any external rewards or goals. We show that our sub-goals generalise to novel partially observed environments and goal-driven tasks, leading to comparable (or better) performance (via. better exploration) on downstream tasks compared to prior work on goal-driven sub-goals [Goyal et al., 2019].

We study sub-goals in the framework of quantifying the minimum information necessary for taking actions by an agent. [van Dijk and Polani, 2011] have shown that in the presence of an external goal, the minimum goal information required by an agent for taking an action is a useful measure of sub-goal states. [Goyal et al., 2019] demonstrate that for action A, state S and a goal G, such sub-goals can be efficiently learnt by imposing a bottleneck on the information I(A,G|S). We show that replacing the goal with an intrinsic objective admits a strategy for discovery of sub-goals in a completely unsupervised manner.

Our choice of intrinsic objective is the Variational Intrinsic Control (VIC) formulation [Gregor et al., 2016] to learn options Ω that maximize the mutual information I(Sf ,Ω), referred to as empowerment, where Sf is the final state in a trajectory [Salge et al., 2013]. To see why this maximizes empowerment, notice that I(Sf ,Ω) = H(Sf) - H(Sf |Ω), where H(.) denotes entropy. Thus, empowerment maximizes the diversity in final states Sf while learning options highly predictive of Sf . We demonstrate that by limiting the information the agent uses about the selected option Ω while maximizing empowerment, a sparse set of states emerge where the necessary option information I(Ω,A|S) is high - we interpret these states as our unsupervised sub-goals. We call our approach Information Regularized VIC (IR-VIC). Although IR-VIC is similar in spirit to [Goyal et al., 2019; Polani et al., 2006], it is important to note that we use latent options Ω instead of external goals - removing any dependence on the task-structure. To summarize our contributions,

• We propose Information Regularized VIC (IR-VIC), a novel framework to identify sub-goals in a task-agnostic manner, by regularizing relevant option information.
• Theoretically, we show that the proposed objective is a sandwich bound on the empowerment I(Ω, Sf ) - this is the only useful upper bound we are aware of.
• We show that our sub-goals are transferable and lead to improved sample-efficiency on goal-driven tasks in novel, partially-observable environments. On a challenging grid-world navigation task, our method outperforms (a re-implementation of) [Goyal et al., 2019].

2 Methods

2.1 Notation

We consider a Partially Observable Markov Decision Process (POMDP), defined by the tuple (S,X,A,P, r), s ∈ S is the state, x ∈ X is the partial observation of the state and a ∈ A is an action from a discrete action space. P : S × S × A denotes an unknown transition function, representing p (st+1|st, at) : st, st+1 ∈ S,At ∈ A. Both VIC and IR-VIC initially train an option (Ω) conditioned policy π(at|ω, xt), where ω ∈ {1, · · · , |Ω|}. During transfer, all approaches (including baselines) train a goal-conditioned policy π(at|xt, gt) where gt is the goal information at time t. Following standard practice [Cover and Thomas, 1991], we denote random variables in uppercase (Ω), and items from the sample space of random variables in lowercase (ω).

2.2 Variational Intrinsic Control (VIC)

VIC maximizes the mutual information between options Ω and the final (option termination) state Sf given s0, i.e. I(Sf ,Ω | S0 = s0), which encourages the agent to learn options that reliably reach a diverse set of states. This objective is estimated by sampling an option from a prior at the start of a trajectory, following it until termination, and inferring the sampled option given the final and initial states. Informally, VIC maximizes the empowerment for an agent, i.e. its internal options Ω have a high degree of correspondence to the states of the world Sf that it can reach. VIC formulates a variational lower bound on this mutual information. Specifically, let p(ω | s0) = p(ω) be a prior on options (we keep the prior fixed as per [Eysenbach et al., 2018]), pJ (sf | ω, s0) is defined as the (unknown) terminal state distribution achieved when executing the policy π(at | ω, st), and qν(ω | sf , s0) denote a (parameterized) variational approximation to the true posterior on options given Sf and S0. Then:

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

Z

c

P

q

2

u

w

F

z

C

f

H

/

T

B

8

9

>

A

n

D

L

S

g

M

I

Y

V

r

R

Q

k

U

p

K

o

3

X

d

y

N

+

E

G

0

v

W

7

O

j

J

m

5

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

M

2

G

R

N

Z

S

Y

O

J

D

p

8

r

W

B

V

o

w

>

A

9

X

c

L

F

I

U

z

P

m

C

g

q

j

d

f

0

K

v

/

u

7

T

+

Q

3

E

k

H

n

y

5

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

j

g

3

+

q

E

/

I

5

X

C

f

T

o

A

Y

Z

w

>

B

n

c

D

L

S

N

F

P

W

9

m

8

u

p

J

K

Q

V

7

z

U

y

M

G

d

0

O

H

2

r

k

R

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

C

J

m

n

O

9

T

U

R

y

2

f

/

X

u

d

H

>

A

B

c

Z

D

L

S

N

F

I

P

q

3

W

K

r

o

M

p

0

Q

g

j

G

E

w

5

8

z

+

V

k

7

Y

v

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

M

N

r

j

V

O

D

c

K

Y

G

5

2

U

f

I

v

w

>

A

B

n

Z

L

S

g

F

P

u

k

C

7

R

q

d

X

o

9

J

m

y

Q

H

8

p

+

z

/

3

W

E

0

T

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

X

p

P

m

D

c

9

A

S

5

Q

v

M

/

V

R

E

0

g

>

B

7

Z

L

F

I

Y

z

r

k

G

J

U

K

d

u

j

q

N

2

O

W

+

T

H

n

y

3

w

C

f

o

8

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

G

u

D

B

P

c

T

q

9

g

w

X

S

n

r

I

J

H

f

/

>

A

Z

L

N

F

3

W

C

U

K

d

m

R

o

M

p

2

0

Q

y

j

E

5

8

z

+

V

k

7

Y

v

O

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

F

0

w

W

8

Q

A

5

/

D

L

B

k

K

S

Z

g

>

C

X

c

M

I

Y

z

9

V

U

3

p

m

2

o

d

O

y

r

N

G

E

R

u

P

7

n

j

H

+

J

T

f

q

v

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

y

d

W

V

c

U

H

p

Y

D

E

R

k

G

m

L

>

A

B

n

Z

S

g

M

F

I

P

u

r

2

w

C

K

7

j

q

X

o

9

O

J

N

Q

f

5

8

+

z

/

3

v

0

T

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

P

Q

N

S

Z

o

K

n

U

J

B

L

D

G

d

M

>

A

c

F

I

q

3

W

9

C

j

0

m

p

2

y

T

R

u

g

H

f

E

w

5

8

X

/

z

+

V

r

k

7

Y

v

O

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

X

p

P

m

D

c

9

A

S

5

Q

v

M

/

V

R

E

0

g

>

B

7

Z

L

F

I

Y

z

r

k

G

J

U

K

d

u

j

q

N

2

O

W

+

T

H

n

y

3

w

C

f

o

8

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

Q

r

G

N

Y

g

E

M

F

f

U

X

u

2

Z

>

A

B

H

c

D

J

S

I

P

o

9

5

R

w

V

j

k

p

y

0

7

3

O

/

n

8

d

+

v

C

L

K

z

q

m

W

T

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

Z

z

T

C

7

u

K

p

Y

w

J

m

G

R

L

U

9

>

A

B

n

c

D

S

g

M

F

I

P

r

k

2

j

q

d

V

X

o

O

W

y

Q

H

f

5

8

+

/

3

N

v

E

0

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

Q

D

7

w

5

R

U

S

N

z

Y

I

W

m

g

>

A

B

n

c

Z

L

M

F

P

u

r

k

2

C

K

j

q

d

V

X

o

9

O

J

y

H

f

8

p

+

/

3

G

v

E

0

T

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

p

9

v

5

U

m

A

Z

E

q

F

c

3

X

+

M

2

y

Q

>

B

n

D

L

S

g

I

Y

z

V

r

R

k

H

T

N

j

G

C

K

O

W

/

7

P

J

w

d

8

f

0

o

u

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

N

E

2

n

S

u

C

p

m

R

P

G

B

r

H

X

c

>

A

3

V

D

L

g

J

z

F

o

Z

y

j

M

I

0

w

9

W

5

O

8

/

v

Q

q

7

Y

k

d

+

U

K

T

f

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

r

Y

z

Z

2

8

f

d

k

E

m

v

W

O

V

S

A

Q

g

/

>

B

3

c

D

L

M

F

I

9

R

w

y

0

C

U

K

T

X

j

n

H

N

+

u

P

5

7

G

q

p

J

o

2.3 Information Regularized VIC (IR-VIC)

We identify sub-goals as states where the necessary option information required for deciding actions is high. Formally, this means that at every timestep t in the trajectory, we minimize the mutual information I(Ω,At|St, S0 = s) , resulting in a sparse set of states where this mutual information remains high despite the minimization. Intuitively, this means that on average (across different options), these states have higher relevant option information that other states (e.g. the regions with darker shades of red in Figure 1). Overall, our objective is to maximize:

where β > 0 is a trade-off parameter. Thus, this is saying that one wants options Ω which allow the agent to have a high empowerment, while utilizing the least relevant option information at each step.

Interestingly, Equation 2 has a clear, principled interpretation in terms of the empowerment I(Ω, Sf |S0) from the VIC model. We state the following lemma (which follows from recursively applying the chain rule of mutual information and the data-processing inequality [Cover and Thomas, 1991]):

Lemma 2.1. Let At be the action random variable at timestep t and state St following an option-conditioned policy π(at|st, ω). Then, I(Ω,At|St, S0) i.e. the conditional mutual information between the option Ω and action At when summed over all timesteps in the trajectory, upper bounds the conditional mutual information I(Ω, Sf |S0) between Ω and the final state Sf - namely the empowerment as defined by [Gregor et al., 2016]:

Implications. With this lens, one can view the optimization problem in Equation 2 as a Lagrangian relaxation of the following constrained optimization problem:

where R > 0 is a constant. While upper bounding the empowerment does not directly imply one will find useful subgoals (meaning it is the structure of the decomposition eq. (3) that is more relevant than the fact that it is an upper bound), this bound might be of interest more generally for representation learning [Achiam et al., 2018; Gregor et al., 2016].

Targeting specific values for the upper bound R can potentially allow us to control how 'abstract' or invariant the latent option representation is relative to the states Sf , leading to solutions that say, neglect unnecessary information in the state representation to allow better generalization. Note that most approaches currently limit the abstraction by constraining the number of discrete options, which (usually) imposes an upper bound on I(Ω, Sf) = H(Ω) - H(Ω|Sf), since H(Ω) ≥ H(Ω|Sf) and H ≥ 0 in the discrete case. However, this does not hold for the continuous case, where this result might be more useful. Investigating this is beyond the scope of this current paper, however, as our central aim is to identify useful sub-goals, and not to scale the VIC framework to continuous options.

2.4 Algorithmic Details

Upper Bounds for I(Ω,At | St, S0)

Inspired by InfoBot [Goyal et al., 2019], we bottleneck the information in a statistic Zt of the state St and option Ω used to parameterize the policy π(At | Ω, St) (fig. 2 right). This is justified by the the data-processing inequality [Cover and Thomas, 1991] for the markov chain Ω, St ↔ Zt ↔ At, which implies I(Ω, At | St, S0) ≤ I(Ω, Zt | St, S0). We can then obtain the following upper bound on I(Ω,Zt | St, S0): 1

where q(zt) is a fixed variational approximation (set to N(0, I) as in InfoBot), and pφ(zt | ω, st) is a parameterized encoder. As explained in section 1, the key difference between eq. (5) and InfoBot is that they construct upper bounds on I(G,At | St, S0) using information about the goal G, while we bottleneck the option-information. One could use the DIAYN objective [Eysenbach et al., 2018] (see more below under related objectives) which also has a I(At,Ω|St) term, and directly bottleneck the action-option mutual information instead of eq. (5), but we found that directly imposing this bottleneck often hurt convergence in practice.

We can compute a Monte Carlo estimate of Equation 5 by first sampling an option ω at s0 and then keeping track of all states visited in trajectory τ . In addition to the VIC term and our bottleneck regularizer, we also include the entropy of the policy over the actions (maximum-entropy RL [Ziebart et al., 2008]) as a bonus to encourage sufficient exploration. We fix the coefficient for maximum-entropy, α = 10-3 which consistently works well for our approach as well as baselines.

1 Similar to VIC, pJ here denotes the (unknown) state distribution at time t from which we can draw samples when we execute a policy. We then assume a variational approximation q(zt) (fixed to be a unit gaussian) for p(zt|St). Using the fact that DKL(p(zt|st)||q(zt)) ≥ 0 we get the derived upper bound.

Overall, the IR-VIC objective is:

where θ, φ and ν are the parameters of the policy, latent variable decoder and the option inference network respectively. The first term in the objective promotes high empowerment while learning options; the second term ensures minimality in using the options sampled to take actions and the third provides an incentive for exploration.

Related Objectives

DIAYN [Eysenbach et al., 2018] attempts to learn skills (similar to options) which can control the states visited by agents while ensuring that all visited states, as opposed to termination states, are used to distinguish skills. Thus, for an option Ω and every state St in a trajectory, they maximize ∑t I(Ω, St) - I(At,Ω|St) + H(At|St), as opposed to I(Ω, Sf) - β ∑t I(At,Ω|St) + H(At|St) in our objective. With the sum over all timesteps for I(Ω, St), the bound in lemma 2.1 no longer holds true, which also means that there is no principled reason (unlike our model) to scale the second term with β. The most closely related work to ours is InfoBot [Goyal et al., 2019], which maximizes ∑t R(t) - βI(Zt,G|St) for a goal (G) conditioned policy π(at|St, G). They define states where I(Zt, G|St) is high despite the bottleneck as "decision states". The key difference is that InfoBot requires extrinsic rewards in order to identify goal-conditioned decision states, while our work is strictly more general and scales in the absence of extrinsic rewards.

Further, in context of both these works, our work provides a principled connection between action-option information reqularization I(At, Ω|St) and empowerment of an agent. The tools from Lemma 2.1 might be useful for analysing these previous objectives which both employ this technique.

2.5 Transfer to Goal-Driven Tasks

In order to transfer sub-goals to novel environments, [Goyal et al., 2019] pretrain their model to identify their goalconditioned decision states, and then study if identifying similar states in new environments can improve exploration when training a new policy πγ(a|s, g) from scratch. Given an environment with reward Re(t), goal G, κ > 0, and state visitation count c(St), their reward is:

The count-based reward decays with square root of c(St) to encourage the model to explore novel states, and the mutual information between goal G and bottleneck variable Zt is a smooth measure of whether a state is a sub-goal, and is multiplied with the exploration bonus to encourage visitation of state where this measure is high.

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

Y

c

p

K

d

A

m

I

W

z

f

U

y

L

X

Q

>

B

/

n

Z

S

8

N

F

9

V

r

q

u

3

w

0

P

T

O

H

C

j

g

D

5

7

k

2

M

o

R

+

v

E

G

J

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

Y

c

p

K

d

A

m

I

W

z

f

U

y

L

X

Q

>

B

/

n

Z

S

8

N

F

9

V

r

q

u

3

w

0

P

T

O

H

C

j

g

D

5

7

k

2

M

o

R

+

v

E

G

J

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

R

0

r

9

2

g

G

7

L

p

y

+

D

X

U

3

d

P

>

A

B

/

n

c

Z

S

8

N

F

I

m

V

W

E

u

q

J

K

j

Q

T

f

M

H

w

Y

5

o

O

C

z

k

v

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

3

c

8

B

D

7

Q

A

/

F

d

P

H

p

+

u

o

>

n

Z

L

S

N

I

U

9

R

f

V

X

r

k

q

K

W

E

O

T

G

C

m

J

y

M

0

Y

j

z

5

g

2

v

w

e ⇡ 2.61

e ⇡ 1.19

e ⇡ 2.22

Figure 3: Heatmaps of necessary option information I(Ω,Zt|St, S0) (normalized to [0,1]) at visited states on environments - 4-Room (top) and maze (bottom). First column depicts environment layout, second and third show results for IR-VIC, β = 1e-3 and β = 1 respectively, and the fourth column shows DIAYN. e-values show computed lower bounds (with Eq. 1) on empowerment in nats.

We use an almost identical setup, replacing their decisionstate term from supervised pretraining with necessary option information from IR-VIC pretraining:

I(·) is computed with eq. (5) with a frozen parameterized encoder p(zt | ω, st) during transfer. Thus, we incentivize visitation of states where necessary option information is high.

Algorithm. In summary, IR-VIC consists of two major phases - (1) Unsupervised Discovery and (2) Transfer. In phase (1), we optimize Eqn. 6 based on unrolled trajectories conditioned on the initially sampled option to update the parameterized encoder pφ(zt|ω, xt), option-conditioned policy πθ(at|ω, xt) and the option inference network qν(ω|s0, sf). In phase (2), we freeze the pretrained encoder pφ(zt|ω, xt) and use it as an added exploration incentive to learn the goal conditioned policy πγ(at|xt, g) (see Eqn. 8).

2.6 IR-VIC for Transfer

Options with partial observability. The methods we have described so far have assumed the true state s ∈ S to be known - the VIC framework with explicit options has only been shown to work in fully obervable MDPs [Gregor et al., 2016; Eysenbach et al., 2018]. However, since we are primarily interested improved exploration in downstream partiallyobservable tasks, we adapt the VIC framework to only use partially-observable information for the parts that we use during transfer. We design our policy (including the encoder p(Zt | Ω, St) used for computing the reward bonus I(Ω,Zt | St, S0) during transfer) to take as input partial observations x ∈ X while allowing the option inference networks (of IR-VIC and DIAYN) to take as input the global (x, y) coordinates of the agent (assuming access to the true state s ∈ S. Note that this privileged information is made available for a single environment in order to discover subgoals transerable to multiple novel environments (whereas

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

o

+

Z

v

A

p

2

E

z

0

I

H

U

7

j

S

W

n

>

B

/

c

L

8

N

F

P

m

R

V

u

C

q

J

G

X

Q

k

T

Y

f

9

d

y

O

K

D

3

M

w

5

g

r

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

y

J

0

R

X

A

o

Y

T

3

I

U

Q

K

v

S

9

E

N

>

B

/

n

c

Z

L

8

F

P

m

V

W

u

q

j

G

f

M

H

D

w

r

g

5

O

C

7

2

z

k

p

+

d

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

w

Y

H

9

v

U

G

C

Q

f

0

+

/

P

K

J

L

>

A

B

3

c

Z

S

8

N

F

I

n

V

X

r

m

E

u

q

o

y

2

k

O

T

W

j

7

z

5

d

g

D

M

p

R

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

w

Y

H

9

v

U

G

C

Q

f

0

+

/

P

K

J

L

>

A

B

3

c

Z

S

8

N

F

I

n

V

X

r

m

E

u

q

o

y

2

k

O

T

W

j

7

z

5

d

g

D

M

p

R

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

w

r

q

c

0

Y

R

J

D

C

X

8

j

f

A

k

>

B

/

n

Z

L

S

N

F

I

U

P

m

V

W

E

u

K

o

G

Q

T

y

M

H

g

3

5

O

7

2

z

p

v

+

d

9

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

K

P

/

R

D

c

f

C

S

I

g

2

9

o

3

J

H

Q

>

A

B

n

Z

L

8

N

F

U

V

X

r

k

p

T

j

v

0

w

y

E

q

+

d

G

O

M

m

u

5

W

z

7

Y

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

P

G

E

d

u

m

/

5

Y

9

H

J

q

D

v

o

M

B

c

>

A

X

Z

L

S

8

N

F

I

U

n

V

j

+

r

z

W

R

3

g

2

0

w

Q

p

K

C

y

T

k

O

f

7

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

P

G

E

d

u

m

/

5

Y

9

H

J

q

D

v

o

M

B

c

>

A

X

Z

L

S

8

N

F

I

U

n

V

j

+

r

z

W

R

3

g

2

0

w

Q

p

K

C

y

T

k

O

f

7

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

w

q

j

P

9

0

o

5

A

D

3

M

>

B

/

H

c

Z

L

S

F

I

X

v

+

7

d

E

W

G

V

C

r

u

Q

T

J

y

R

z

8

g

O

k

U

m

p

Y

n

N

K

f

2

supervised methods such as InfoBot [Goyal et al., 2019] require global (x, y) coordinates as goal information across all training environments).

Preventing option information leak. We parameterize p(at|zt, st) (fig. 2, right) using just the current state st, whereas the encoder p(zt|Ω, (s1, · · · , st)) uses all previous states since a sequence of state observations (s1, · · · , st) could potentially be very informative of the Ω being followed, which if provided directly to p(at|·) can lead to a leakage of the option information to the actions, rendering the bottleneck on option information imposed via zt useless. Hence, in our implementation we remove recurrence over partial observations for p(at|zt, st) while keeping it in p(zt | Ω, st).

3 Experiments

Environments. We pre-train and test on grid-worlds from the MiniGrid [Chevalier-Boisvert et al., 2018] environments. We first consider a set of simple environments - 4-Room and Maze (see Fig. 3) followed by the MultiRoomNXSY also used by [Goyal et al., 2019]. The MultiRoomNXSY environments consist of X rooms of size Y, connected in random orientations. We refer to the ordering of rooms, doors and goal as a 'layout' in the MultiRoomNXSY environment - pre-training of options (for IR-VIC and DIAYN) is performed on a single fixed layout while transfer is performed on several different layouts (a layout is randomly selected from a set every time the environment is reset). In all pre-training environments, we fix the option trajectory length H (the number of steps an option takes before termination) to 30 steps.

We use Advantage Actor-Critic (A2C) for all experiments. Since code for InfoBot [Goyal et al., 2019] was not public, we report numbers based on a re-implementation of InfoBot, ensuring consistency with their architectural and hyperparameter choices. We refer the readers to our code 2 for further details.

Baselines. We evaluate the following on quality of exploration and transfer to downstream goal-driven tasks with sparse rewards: 1) InfoBot (our implementation) - which identifies goal-driven decision states by regularizing goal information, 2) DIAYN - whose focus is unsupervised skill acquisition, but has an I(At, Ω|St) term which can be used for the bonus in Equation 8, 3) count-based exploration which uses visitation counts as exploration incentive (this corresponds to replacing I(Ω, Zt|St, S0) with 1 in Equation 8), 4) a randomly initialized encoder p(zt | ω, xt) which is a noisy version of the count-based baseline where the scale of the reward is adjusted to match the count-based baseline 5) how different values of β affect performance and how we choose a β value using a validation set, and 6) a heuristic baseline that uses domain knowledge to identify landmarks such as corners and doorways and provide a higher count-based exploration bonus to these states. This validates the extent to which necessary option information is useful in identifying a sparse set of states that are useful for transfer vs. heuristically determined landmarks.

2 https://github.com/nirbhayjm/irvic

Method	MR-N3S4	MR-N5S4	MR-N6S25
pφ(Zt|St,Ω) pretrained on	MR-N2S6	MR-N2S6	MR-N2S10
InfoBot [Goyal et al., 2019]	90%	85%	N/A
InfoBot (Our Implementation)	99.9%±0.1%	79.1%±11.6%	9.9%±1.2%
Count-based Baseline	99.7%±0.1%	99.7%±0.1%	86.8%±2.2%
DIAYN	99.7%±0.1%	95.4%±4.1%	0.1%±0.1%
Random Network	99.9%±0.1%	98.8%±0.7%	79.5%±5.2%
Heuristic Baseline	N/A	N/A	85.9%±3.0%
Ours (β = 10-2 )

99.3%±0.3% 99.4%±0.2% 92.9%±1.2%

Table 1: Success rate (mean ± standard error) of the goalconditioned policy when trained with different exploration bonuses in addition to the extrinsic reward Re(t). We report results at 5×105 timesteps for MultiRoom (MR-NXSY) N3S4, N5S4 and at 107 timesteps for N6S25. We also report the performance of InfoBot for completeness. Note that for rooms of size 4 (N3S4, N5S4), incentivizing to visit corners and doorways (Heuristic Sub-goals) is equivalent to count-based exploration.

3.1 Qualitative Results

Figure 3 shows heatmaps of necessary option information I(Ω, At|St, S0) on 4-Room and maze grid world environments where the initial state is sampled uniformly at random. Stronger regularization (β = 1) leads to poorer empowerment maximization and in some cases not learning any options (and I(Ω,At|St, S0) collapses to 0 at all states). At lower values of β = 1e-3, we get more discernible states with distinctly high necessary option information. Finally, for maze we see that for a similar value of empowerment 3 , IR-VIC leads to a more peaky distribution of states with high necessary option information than DIAYN.

3.2 Quantitative Results

Transfer to Goal-driven Tasks

Next, we evaluate Equation 8, i.e. whether providing visitation incentive proportional to necessary option information at a state in addition to sparse extrinsic reward can aid in transfer to goal-driven tasks in different environments. We restrict ourselves to the point-navigation task [Goyal et al., 2019] transfer in the MultiRoomNXSY set of partiallyobservable environments. In this task, the agent learns a policy π(at|gt, st) where gt is the vector pointing to the goal from agent's current location at every time step t. The initial state is always the first room, and has to go to a randomly sampled goal location in the last room and is rewarded only when it reaches the goal. [Goyal et al., 2019] test the efficacy of different exploration objectives 4 and show that this is a hard setting where efficient exploration is necessary. They show that InfoBot outperforms several state-of-the art exploration methods in this environment.

Concretely, we 1) train IR-VIC to identify sub-goals (Equation 2) on MultiRoomN2S6 and transfer to a goaldriven task on MultiRoomN3S4 and MultiRoomN5S4 (similar to [Goyal et al., 2019]), and 2) train on MultiRoomN2S10 and transfer to MultiRoomN6S25, which is a more challenging transfer task i.e. it has a larger upper limit on room size making efficient exploration critical to find doors quickly. For IR-VIC and DIAYN (the two methods that learn options), we pre-train on a single layout of the corresponding MultiRoom environment for 106 episodes and pick the checkpoints with highest empowerment values across training. For InfoBot (no option learning required), we pre-train as per [Goyal et al., 2019] on multiple layouts of the MultiRoom environment. Transfer performance of all methods is reported on a fixed test set of multiple MultiRoom environment layouts and hyperparameters across all methods, e.g. β for IR-VIC and InfoBot are selected using a validation set of MultiRoom environment layouts.

3 Since DIAYN maximizes the mutual information with every state in a trajectory, we report the empowerment for the state with maximum mutual information with the option.

4 While our focus is on identifying and probing how good subgoals from intrinsic training are, more broader comparisons to exploration baselines are in InfoBot [Goyal et al., 2019].

Overall Trends

Table 1 reports success rate - the % of times the agent reaches the goal and Figure 4 reports the average return when learning to navigate on test environments. The MultiRoomN6S25 environment provides a sparse decaying reward upon reaching the goal - implying that when comparing methods, higher success rate (Table 1) indicates that the goal is reached more often, and higher return values (Figure 4) indicate that the goal is reached with fewer time steps.

First, our implementation of InfoBot is competitive with [Goyal et al., 2019] 5 . Next, for the MultiRoomN2S6 to N5S4 transfer (middle column), baselines as well as subgoal identification methods perform well with some models having overlapping confidence intervals despite low success means. In MultiRoomN2S10 to N6S25 transfer, where the latter has a large state space, we find that IR-VIC (at β = 10-2 ) achieves the best sample complexity (in terms of average return) and final success, followed closely by InfoBot. Moreover, we find that the heuristic baseline which identifies a sparse set of landmarks (to mimic sub-goals) does not perform well - indicating that it is not easy to handspecify sub-goals that are useful for the given transfer task. Finally, the randomly initialized encoder as well as DIAYN

5 We found it important to run all models (inlcuding InfoBot) an order of magnitude more steps compared to [Goyal et al., 2019], but our models also appear to converge to higher success values.

generalize much worse in this transfer task.

β sensitivity. We sweep over β in log-scale from {10-1 , . . . , 10-6 }, as shown in Figure 5 (except β = 10-1 which does not converge to > 0 empowerment) and also report β = 0 which recovers a no information regularization baseline. We find that 10-2 works best - with performance tailing off at lesser values. This is intuitive, since for a really large value of β, one does not learn any options (as the empowerment is too low), while for a really small value of β, one might not be able to target necessary option information, getting large "sufficient" (but not necessary) option information for the underlying option-conditioned policy.

We pick the best model for transfer based on performance on the validation environments, and study generalization to novel test environments. Choosing the value of β in this setting is thus akin to model selection. Such design choices are inherent in general in unsupervised representation learning (e.g. with K-means and β-VAE [Higgins et al., 2017]).

4 RelatedWork

Intrinsic control and intrinsic motivation. Learning how to explore without extrinsic rewards is a foundational problem in Reinforcement Learning [Pathak et al., 2017; Gregor et al., 2016; Schmidhuber, 1990]. Typical curiosity-driven approaches attempt to visit states that maximize the surprise of an agent [Pathak et al., 2017] or improvement in predictions from a dynamics model [Lopes et al., 2012]. While curiosity-driven approaches seek out and explore novel states, they typically do not measure how reliably the agent can reach them. In contrast, approaches for intrinsic control [Eysenbach et al., 2018; Achiam et al., 2018; Gregor et al., 2016] explore novel states while ensuring those states are reliably reachable. [Gregor et al., 2016] maximize the number of final states that can be reliably reached by the policy, while [Eysenbach et al., 2018] distinguish an option (which they refer to as a 'skill') at every state along the trajectory, and [Achiam et al., 2018] learn options for entire trajectories by encoding a sub-sequence of states, sampled at regular intervals. Since we wish to learn to identify useful sub-goals which one can reach reliably acting in an environment rather than just visiting novel states (without an estimate of reachability), we formulate our regularizer in the intrinsic control framework, specifically building on the work of [Gregor et al., 2016].

Default behavior and decision states. Recent work in policy compression has focused on learning a default policy when training on a family of tasks, to be able to re-use behavior across tasks. In [Teh et al., 2017], default behavior is learnt using a set of task-specific policies which then regularizes each policy, while [Goyal et al., 2019] learn a default policy using an information bottleneck on task information and a latent variable the policy conditions on, identifying sub-goals which they term as "decision states". We devise a similar information regularization objective that learns default behavior shared by all intrinsic options without external rewards so as to reduce learning pressure on option-conditioned policies. Different from these previous approaches, our approach does not need any explicit reward specification when learning options (ofcourse, since we care about transfer we still need to do model selection based on validation environments).

Bottleneck states in MDPs. There is rich literature on identification of bottleneck states in MDPs. The core idea is to either identify all the states that are common to multiple goals in an environment [McGovern and Barto, 2001] or use a diffusion model built using an MDP's transition matrix [Machado et al., 2017]. The key distinction between bottleneck states and necessary-information based sub-goals is that the latter are more closely tied to the information available to the agent and what it can act upon, whereas bottleneck states are more tied to the connectivity structure of an MDP and intrinsic to the environment, representing states which when visited allow access to a novel set of states [Goyal et al., 2019]. However, bottleneck states do not easily apply to partially observed environments and when the transition dynamics of the MDP are not known.

Information bottleneck in machine learning. Since the foundational work of [Tishby et al., 1999; Chechik et al., 2005], there has been a lot of interest in making use of ideas from information bottleneck (IB) for various tasks such as clustering [Strouse and Schwab, 2017; Still et al., 2004], sparse coding [Chalk et al., 2016], classification using deep learning [Alemi et al., 2016], cognitive science and language [Zaslavsky et al., 2018] and reinforcement learning [Goyal et al., 2019; Strouse et al., 2018]. We apply an information regularizer to an RL agent that results in a set of sparse states where necessary option information is high, which correspond to our sub-goals.

5 Conclusion

We devise a principled approach to identify sub-goals in an environment without any extrinsic reward supervision using a sandwich bound on the empowerment of [Gregor et al., 2016]. Our approach yields sub-goals that aid efficient exploration on external-reward tasks and subsequently lead to better success rate and sample complexity in novel environments (competitive with supervised sub-goals). Our code and environments will be made publicly available.