Title: DS-VIC: UNSUPERVISED DISCOVERY OF DECISION STATES FOR TRANSFER IN RL

Abstract: We learn to identify 'decision states', namely the parsimonious set of states where decisions meaningfully affect the future states an agent can reach in an environment. We utilize the VIC framework (Gregor et al., 2016) , which maximizes an agent's 'empowerment', i.e. the ability to reliably reach a diverse set of states -and formulate a sandwich bound on the empowerment objective that allows identification of decision states. Unlike previous work (Goyal et al., 2019) , our decision states are discovered without extrinsic rewards -simply by interacting with the world. Our results show that our decision states are: 1) often interpretable, and 2) lead to better exploration on downstream goal-driven tasks in partially observable environments.

1. INTRODUCTION:

Not all states in a decision making process are created equal. Consider the middle illustration in Figure 1 , where a robot has four 'options', each representing a goal shape it can potentially reach. Given its spawn location, it can initially proceed straight regardless of the option it chooses until the intersection, at which point it needs to utilise 1 bit of (Shannon) information from the option variable to inform the choice of whether to turn left or right. However, right after it takes the left turn (say), it again does not need the goal information when choosing actions and can follow 'default' or 'option-independent' behaviour. Thus, there is a natural difference in the minimum amount of necessary goal information or 'relevant information' (Polani et al., 2006) needed at different states.

Identifying these 'decision states', i.e. states in the environment where a high amount of relevant goal information is needed, leads to better understanding of the environment structure, which has the potential to enable better transfer to novel environments and tasks. This has previously been shown by Goyal et al. (2019) in partially-observable, goal-driven (i.e. with extrinsic rewards) 2D navigation settings, where using decision states to guide exploration enables faster learning.

Goal-independent Decision States. Our key intuition is that decision states exist in an environment independent of extrinsic goals. For example, one can imagine the (middle) red tile at the intersection in Figure 1 being a useful decision state -even across all possible navigation goals the agent could have. Ofcourse, not all intersections are decision states. For e.g., if the left room was full of lava, where the robot would die, thinking of the middle red tile as a decision state would have limited utility, since the relevant goal information (across all reachable goals) in this case would be 0 bits.

Identifying 'unsupervised' (or task-agnostic) decision states is advantageous in scenarios where: 1) rewards are sparse or absent (Pathak et al., 2017) , 2) for an agent to learn meaningful behaviour, proxy goals and rewards need to be hand engineered (making it hard to scale), and 3) the notion of a goal might not even be obvious, e.g. in continuous control tasks (Lillicrap et al., 2015) .

Our DS-VIC method identifies decision states without extrinsic rewards, solely by interacting with partially-observable environments. These decision states are a function of the environment as well as the states an agent can reliably reach. We demonstrate that our decision states generalise to novel environments and tasks, leading to comparable (or better) exploration and performance on downstream tasks compared to Goyal et al. (2019) that identifies goal-driven decision states.

Decision States in Empowered Agents. We build on the VIC framework (Gregor et al., 2016) (Figure 1 ), where the core idea is to maximize the empowerment of an agent. In simple terms, an empowered agent is able to reliably reach a diverse set of states in the environment, while avoiding states that are difficult to reach reliably. We use VIC's formulation to learn options Ω that maximize (a lower bound J V IC on) the mutual information I(S f , Ω) where S f is the final state in a trajectory. We use latent options since we operate in a setting without external goals. To see why this maximizes Figure 1 : Left: The VIC framework (Gregor et al., 2016) in a navigation context: an agent learns high-level macro-actions (or options) to reach different states in an environment reliably without any extrinsic reward. Right: DS-VIC identifies decision states (in red) associated with options where the agent is empowered to make informed decisions. The rest of the states in a trajectory (dotted lines in blue regions) then show default, option-independent behavior. Identification of decision states leads to improved transfer to novel environments. empowerment, notice that I(S f , Ω) = H(S f ) -H(S f |Ω), where H(.) denotes entropy. Thus, empowerment maximizes the diversity in final states S f while learning options highly predictive of S f (Salge et al., 2013) . Using VIC, we identify decision states by attempting to hit the relevant information required at a particular state by minimizing the mutual information I(Ω, A t |S t ) (for every state S t , action A t ). This is similar in spirit to Goyal et al. (2019) ; Polani et al. (2006) , with the key difference that we use latent options Ω instead of external goals. Interestingly, we prove that t I(Ω, A t |S t ) is an upper bound on empowerment, which we minimize, in addition to maximizing the VIC lower bound J V IC . This shines a connection to VIC-while they optimize a lower bound, our work optimizes a sandwich bound on the empowerment1 . To summarize our contributions,

• We propose DS-VIC, a novel framework to identify decision states in a task-agnostic manner.

These decision states align with our intuitive assessments in various partially-observed scenarios. • We provide an understanding of our proposed objective, proving that our framework optimizes a sandwich bound on the empowerment I(Ω, S f ). • We show that our mechanism to identify decision states is transferable and leads to improved sample-efficiency on goal-driven tasks in novel 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, A, P, r), where the (discrete or continuous) state-space S is a set of underlying but unobserved states s ∈ S and A denotes a discrete action space. P : S × S × A denotes an unknown transition function, representing p (s t+1 |s t , a t ) : s t , s t+1 ∈ S, A t ∈ A. Both VIC and DS-VIC train an option (Ω) conditioned policy π(a t |ω, s t ), where ω ∈ {1, • • • , |Ω|}. Following standard practice (Cover & 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):

The option Ω in VIC is a global latent variable underlying a trajectory τ = {S 0 , A 0 , • • • , S f } (Figure 2 ). To encourage the agent to reach a diverse set of states reliably, VIC proposes maximizing the mutual information (Cover & Thomas, 1991) between Ω and final state S f given s 0 , i.e. I(S f , Ω | S 0 = s 0 ). Informally, this maximizes the empowerment for an agent, i.e. its internal options Ω have a high degree of correspondence to the states of the world S f that it can reach. VIC formulates a variational lower bound on this mutual information. Specifically, let p(ω | s 0 ) = p(ω) be a prior on options (we keep the prior fixed as per Eysenbach et al. (2018) ), p J (s f | ω, s 0 ) is defined as the (unknown) terminal state distribution achieved when executing the policy π(a t | ω, s t ), and q ν (ω | s f , s 0 ) denote a (parameterized) variational approximation to the true posterior on options ⌦ < l a t e x i t s h a 1 _ b a s e 6 4 = " F t a c 6 Y T H 9 z

2 i U V q D Y V K w b Q P E E r o = " > A A A B 7 X i c b V D L S g N B E J y N r x h f U Y 9 e B o P g K e y q o M e g F 2 9 G M A 9 I l j A 7 6 U 3 G z G O Z m R X C k n / w 4 k E R r / 6 P N / / G S b I H T S x o K K q 6 6 e 6 K E s 6 M 9 f 1 v r 7 C y u r a + U d w s b W 3 v 7 O 6 V 9 w + a R q W a Q o M q r n Q 7 I g Y 4 k 9 C w z H J o J x q I i D i 0 o t H N 1 G 8 9 g T Z M y Q c 7 T i A U Z C B Z z C i x T m p 2 7 w Q M S K 9 c 8 a v + D H i Z B D m p o B z 1 X v m r 2 1 c 0 F S A t 5 c S Y T u A n N s y I t o x y m J S 6 q Y G E 0 B E Z Q M d R S Q S Y M J t d O 8 E n T u n j W G l X 0 u K Z + n s i I 8 K Y s Y h c p y B 2 a B a 9 q f i f 1 0 l t f B V m T C a p B U n n i + K U Y 6 v w 9 H X c Z x q o 5 W N H C N X M 3 Y r p k G h C r Q u o 5 E I I F l 9 e J s 2 z a n B e 9 e 8 v K r X r P I 4 i O k L H 6 B Q F 6 B L V 0 C 2 q o w a i 6 B E 9 o 1 f 0 5 i n v x X v 3 P u a t B S + f O U R / 4 H 3 + A F / b j v 0 = < / l a t e x i t > p(!|s 0 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " N 5 A F 0 W U O M 3 X w y M e / G G W b Z r m i L B I = " > A A A B 9 X i c b V D L S g N B E O z 1 G e M r 6 t H L Y B D i J e y q o M e g F 4 8 R z A O S N c x O Z p M h 8 1 h m Z p U Q 8 x 9 e P C j i 1 X / x 5 t 8 4 S f a g i Q U N R V U 3 3 V 1 R w p m x v v / t L S 2 v r K 6 t 5 z b y m 1 v b O 7 u F v f 2 6 U a k m t E Y U V 7 o Z Y U M 5 k 7 R m m e W 0 m W i K R c R p I x p c T / z G A 9 W G K X l n h w k N B e 5 J F j O C r Z P u k 1 J b C d r D T 8 h 0 / J N O o e i X / S n Q I g k y U o Q M 1 U 7 h q 9 1 V J B V U W s K x M a 3 A T 2 w 4 w t o y w u k 4 3 0 4 N T T A Z 4 B 5 t O S q x o C Y c T a 8 e o 2 O n d F G s t C t p 0 V T 9 P T H C w p i h i F y n w L Z v 5 r 2 J + J / X S m 1 8 G Y 6 Y T F J L J Z k t i l O O r E K T C F C X a U o s H z q C i W b u V k T 6 W G N i X V B 5 F 0 I w / / I i q Z + W g 7 O y f 3 t e r F x l c e T g E I 6 g B A F c Q A V u o A o 1 I K D h G V 7 h z X v 0 X r x 3 7 2 P W u u R l M w f w B 9 7 n D 2 v r k c w = < / l a t e x i t > ⇡(a t |!, s t ) < l a t e x i t s h a 1 _ b a s e 6 4 = " I g f I n 2 c t L N Q 5 A x i A S T V g 9 d C d H g U = " > A A A B / n i c b V B N S 8 N A E N 3 U r 1 q / o u L J y 2 I R K k h J V N B j 0 Y v H C v Y D m h A 2 2 2 2 7 d D c J u x O h x I J / x Y s H R b z 6 O 7 z 5 b 9 y 2 O W j r g 4 H H e z P M z A s T w T U 4 z r d V W F p e W V 0 r r p c 2 N r e 2 d + z d v a a O U 0 V Z g 8 Y i V u 2 Q a C Z 4 x B r A Q b B 2 o h i R o W C t c H g z 8 V s P T G k e R / c w S p g v S T / i P U 4 J G C m w D 7 y E V 0 g A j 9 i L J e u T U 6 w D O A n s s l N 1 p s C L x M 1 J G e W o B / a X 1 4 1 p K l k E V B C t O 6 6 T g J 8 R B Z w K N i 5 5 q W Y J o U P S Z x 1 D I y K Z 9 r P p + W N 8 b J Q u 7 s X K V A R 4 q v 6 e y I j U e i R D 0 y k J D P S 8 N x H / 8 z o p 9 K 7 8 j E d J C i y i s 0 W 9 V G C I 8 S Q L 3 O W K U R A j Q w h V 3 N y K 6 Y A o Q s E k V j I h u P M v L 5 L m W d U 9 r z p 3 F + X a d R 5 H E R 2 i I 1 R B L r p E N X S L 6 q i B K M r Q M 3 p F b 9 a T 9 W K 9 W x + z 1 o K V z + y j P 7 A + f w D p 2 J T M < / l a t e x i t > ⇡(a t |!, s t ) < l a t e x i t s h a 1 _ b a s e 6 4 = " I g f I n 2 c t L N Q 5 A x i A S T V g 9 d C d H g U = " > A A A B / n i c b V B N S 8 N A E N 3 U r 1 q / o u L J y 2 I R K k h J V N B j 0 Y v H C v Y D m h A 2 2 2 2 7 d D c J u x O h x I J / x Y s H R b z 6 O 7 z 5 b 9 y 2 O W j r g 4 H H e z P M z A s T w T U 4 z r d V W F p e W V 0 r r p c 2 N r e 2 d + z d v a a O U 0 V Z g 8 Y i V u 2 Q a C Z 4 x B r A Q b B 2 o h i R o W C t c H g z 8 V s P T G k e R / c w S p g v S T / i P U 4 J G C m w D 7 y E V 0 g A j 9 i L J e u T U 6 w D O A n s s l N 1 p s C L x M 1 J G e W o B / a X 1 4 1 p K l k E V B C t O 6 6 T g J 8 R B Z w K N i 5 5 q W Y J o U P S Z x 1 D I y K Z 9 r P p + W N 8 b J Q u 7 s X K V A R 4 q v 6 e y I j U e i R D 0 y k J D P S 8 N x H / 8 z o p 9 K 7 8 j E d J C i y i s 0 W 9 V G C I 8 S Q L 3 O W K U R A j Q w h V 3 N y K 6 Y A o Q s E k V j I h u P M v L 5 L m W d U 9 r z p 3 F + X a d R 5 H E R 2 i I 1 R B L r p E N X S L 6 q i B K M r Q M 3 p F b 9 a T 9 W K 9 W x + z 1 o K V z + y j P 7 A + f w D p 2 J T M < / l a t e x i t > = Z dz t p(z t |s t , !)p(a t |s t , z t ) < l a t e x i t s h a 1 _ b a s e 6 4 = " c R F c j 7 Q A 2 v p n 2 6 U 2 W / d 6 L H t s 6 G M = " > A A A C I X i c b V D L S g N B E J z 1 b X x F P X o Z D E I C E n Z V M B d B 9 O I x g l E h u y y z s 5 1 k c P b B T K 8 Y 1 / y K F 3 / F i w d F c h N / x k k M o o k F A z V V 3 X R 3 B a k U G m 3 7 w 5 q a n p m d m 1 9 Y L C w t r 6 y u F d c 3 L n W S K Q 4 N n s h E X Q d M g x Q x N F C g h O t U A Y s C C V f B z e n A v 7 o F p U U S X 2 A 3 B S 9 i 7 V i 0 B G d o J L 9 Y O 6 K u i J G G 9 N 5 H F + E O c 9 p L y + b z Q L W P u 9 R N I m i z C k 3 L 7 E c z b s U v l u y q P Q S d J M 6 I l M g I d b / Y d 8 O E Z x H E y C X T u u n Y K X o 5 U y i 4 h F 7 B z T S k j N + w N j Q N j V k E 2 s u H F / b o j l F C 2 k q U e W b b o f q 7 I 2 e R 1 t 0 o M J U R w 4 4 e 9 w b i f 1 4 z w 1 b N y 0 W c Z g g x / x 7 U y i T F h A 7 i o q F Q w F F 2 D W F c C b M r 5 R 2 m G E c T a s G E 4 I y f P E k u 9 6 r O f t U + P y g d n 4 z i W C B b Z J u U i U M O y T E 5 I 3 X S I J w 8 k m f y S t 6 s J + v F e r f 6 3 6 V T 1 q h n k / y B 9 f k F I C i i P A = = < / l a t e x i t > VIC: DS-VIC: Policy Parameterization + VIC T < l a t e x i t s h a 1 _ b a s e 6 4 = " i v t Z / S W W m D p + I a H l d V v z V M q Y H r U = " > A A A B 6 H i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K o k K e i x 6 8 d h C v 6 A N Z b O d t G s 3 m 7 C 7 E U r o L / D i Q R G v / i R v / h u 3 b Q 7 a + m D g 8 d 4 M M / O C R H B t X P f b W V v f 2 N z a L u w U d / f 2 D w 5 L R 8 c t H a e K Y Z P F I l a d g G o U X G L T c C O w k y i k U S C w H Y z v Z 3 7 7 C Z X m s W y Y S Y J + R I e S h 5 x R Y 6 V 6 o 1 8 q u x V 3 D r J K v J y U I U e t X / r q D W K W R i g N E 1 T r r u c m x s + o M p w J n B Z 7 q c a E s j E d Y t d S S S P U f j Y / d E r O r T I g Y a x s S U P m 6 u + J j E Z a T 6 L A d k b U j P S y N x P / 8 7 q p C W / 9 j M s k N S j Z Y l G Y C m J i M v u a D L h C Z s T E E s o U t 7 c S N q K K M m O z K d o Q v O W X V 0 n r s u J d V d z 6 d b l 6 l 8 d R g F M 4

g w v w 4 A a q 8 A A 1 a A I D h G d 4 h T f n 0 X l x 3 p 2 P R e u a k 8 + c w B 8 4 n z + w U 4 z a < / l a t e x i t > T = 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " S S 8 4

L O M K D R s 3 9 I p R P w C v r z X E / o 4 = " > A A A B 6 n i c b V D L S g N B E O y N r x h f U Y 9 e B o P g K e x G Q S 9 C 0 I v H i H l B s o T Z S W 8 y Z H Z 2 m Z k V Q s g n e P G g i F e / y J t / 4 y T Z g y Y W N B R V 3 X R 3 B Y n g 2 r j u t 5 N b W 9 / Y 3 M p v F 3 Z 2 9 / Y P i o d H T R 2 n i m G D x S J W 7 Y B q F F x i w 3 A j s J 0 o p F E g s B W M 7 m Z + 6 w m V 5 r G s m 3 G C f k Q H k o e c U W O l x / p N p V c s u W V 3 D r J K v I y U I E O t V / z q 9 m O W R i g N E 1 T r j u c m x p 9 Q Z T g T O C 1 0 U 4 0 J Z S M 6 w I 6 l k k a o / c n 8 1 C k 5 s 0 q f h L G y J Q 2 Z q 7 8 n J j T S e h w F t j O i Z q i X v Z n 4 n 9 d J T X j t T 7 h M U o O S L R a F q S A m J r O / S Z 8 r Z E a M L a F M c X s r Y U O q K D M 2 n Y I N w V t + e Z U 0 K 2 X v o u w + X J a q t 1 k c e T i B U z g H D 6 6 g C v d Q g w Y w G M A z v M K b I 5 w X 5 9 3 5 W L T m n G z m G P 7 A + f w B o 0 2 N X Q = = < / l a t e x i t > S 0 < l a t e x i t s h a 1 _ b a s e 6 4 = " t L m X U 1 r v x e i c V Y A W a m i R F M x m f g c = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 l U 0 G P B i 9 4 q t R / Q h r L Z T t q l m 0 3 Y 3 Q g l 9 C d 4 8 a C I V 3 + R N / + N 2 z Y H b X 0 w 8 H h v h p l 5 Q S K 4 N q 7 7 7 R T W 1 j c 2 t 4 r b p Z 3 d v f 2 D 8 u F R S 8 e p Y t h k s Y h V J 6 A a B Z f Y N N w I 7 C Q K a R Q I b A f j 2 5 n f f k K l e S w f z S R B P 6 J D y U P O q L F S o 9 F 3 + + W K W 3 X n I K v E y 0 k F c t T 7 5 a / e I G Z p h N I w Q b X u e m 5 i / I w q w 5 n A a a m X a k w o G 9 M h d i 2 V N E L t Z / N T p + T M K g M S x s q W N G S u / p 7 I a K T 1 J A p s Z 0 T N S C 9 7 M / E / r 5 u a 8 M b P u E x S g 5 I t F o W p I C Y m s 7 / J g C t k R k w s o U x x e y t h I 6 o o M z a d k g 3 B W 3 5 5 l b Q u q t 5 l 1 X 2 4 q t T u 8 z i K c A K n c A 4 e X E M N 7 q A O T W A w h G d 4 h T d H O C / O u / O x a C 0 4 + c w x / I H z + Q P U h I 2 D < / l a t e x i t > S 1

< l a t e x i t s h a 1 _ b a s e 6 4 = " M K J d a w Q 3 F c v Z a y j g 5 u Z q l s g 0

U s A = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 l U 0 G P B i 9 4 q t R / Q h r L Z T t q l m 0 3 Y 3 Q g l 9 C d 4 8 a C I V 3 + R N / + N 2 z Y H b X 0 w 8 H h v h p l 5 Q S K 4 N q 7 7 7 R T W 1 j c 2 t 4 r b p Z 3 d v f 2 D 8 u F R S 8 e p Y t h k s Y h V J 6 A a B Z f Y N N w I 7 C Q K a R Q I b A f j 2 5 n f f k K l e S w f z S R B P 6 J D y U P O q L F S o 9 H 3 + u W K W 3 X n I K v E y 0 k F c t T 7 5 a / e I G Z p h N I w Q b X u e m 5 i / I w q w 5 n A a a m X a k w o G 9 M h d i 2 V N E L t Z / N T p + T M K g M S x s q W N G S u / p 7 I a K T 1 J A p s Z 0 T N S C 9 7 M / E / r 5 u a 8 M b P u E x S g 5 I t F o W p I C Y m s 7 / J g C t k R k w s o U x x e y t h I 6 o o M z a d k g 3 B W 3 5 5 l b Q u q t 5 l 1 X 2 4 q t T u 8 z i K c A K n c A 4 e X E M N 7 q A O T W A w h G d 4 h T d H O C / O u / O x a C 0 4 + c w x / I H z + Q P W C I 2 E < / l a t e x i t > S 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " 9 W 1 H i A R W Z W V D X d t f a d 3 L Y c U u M t c = " > A A A B 6 n i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K k k V 9 F j w o r d K 7 Q e 0 o W y 2 k 3 b p Z h N 2 N 0 I J / Q l e P C j i 1 V / k z X / j t s 1 B W x 8 M P N 6 b Y W Z e k A i u j e t + O 2 v r G 5 t b 2 4 W d 4

u 7 e / s F h 6 e i 4 p e N U M W y y W M S q E 1 C N g k t s G m 4 E d h K F N A o E t o P x 7 c x v P 6 H S P J a P Z p K g H 9 G h 5 C F n 1 F i p 0 e h X + 6 W y W 3 H n I K v E y 0 k Z c t T 7 p a / e I G Z p h N I w Q b X u e m 5 i / I w q w 5 n A a b G X a k w o G 9 M h d i 2 V N E L t Z / N T p + T c K g M S x s q W N G S u / p 7 I a K T 1 J A p s Z 0 T N S C 9 7 M / E / r 5 u a 8 M b P u E x S g 5 I t F o W p I C Y m s 7 / J g C t k R k w s o U x x e y t h I 6 o o M z a d o g 3 B W 3 5 5 l b S q F e + y 4 j 5 c l W v 3 e R w F O I U z u A A P r q E G d 1 C H J j A Y w j O 8 w p s j n B f n 3 f l Y t K 4 5 + c w J / I H z + Q P X j I 2 F < / l a t e x i t > A 0

< l a t e x i t s h a 1 _ b a s e 6 4 = " n w z b V s u A 1

V N 0 W H 7 5 W + c Q 2 W n 2 0 L X O 0 = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 l U 0 G P F i 9 4 q 2 g 9 o Q 9 l s N + 3 S z S b s T o Q S + h O 8 e F D E q 7 / I m / / G b Z u D t j 4 Y e L w 3 w 8 y 8 I J H C o O t + O 4 W V 1 b X 1 j e J m a W t 7 Z 3 e v v H / Q N H G q G W + w W M a 6 H V D D p V C 8 g Q I l b y e a 0 y i Q v B W M b q Z + 6 4 l r I 2 L 1 i O O E + x E d K B E K R t F K D 9 c 9 t 1 e u u F V 3 B r J M v J x U I E e 9 V / 7 q 9 m O W R l w h k 9 S Y j u c m 6 G d U o 2 C S T 0 r d 1 P C E s h E d 8 I 6 l i k b c + N n s 1 A k 5 s U q f h L G 2 p Z D M 1 N 8 T G Y 2 M G U e B 7 Y w o D s 2 i N x X / 8 z o p h l d + J l S S I l d s v i h M J c G Y T P 8 m f a E 5 Q z m 2 h D I t 7 K 2 E D a m m D G 0 6 J R u C t / j y M m m e V b 3 z q n t / U a n d 5 X E U 4 Q i O 4 R Q 8 u I Q a 3 E I d G

< l a t e x i t s h a 1 _ b a s e 6 4 = " T R B F a g D 8 l H s P w w G v O D D o o z k k j X I = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 l U 0 G P F i 9 4 q 2 g 9 o Q 9 l s J + 3 S z S b s b o Q S + h O 8 e F D E q 7 / I m / / G b Z u D t j 4 Y e L w 3 w 8 y 8 I B F c G 9 f 9 d g o r q 2 v r G 8 X N 0 t b 2 z u 5 e e f + g q e N U M W y w W M S q H given S f and S 0 . Then:

V C N g k t s G G 4 E t h O F N A o E t o L R z d R v P a H S P J a P Z p y g H 9 G B 5 C F n 1 F j p 4 b r n 9 c o V t + r O Q J a J l 5 M K 5 K j 3 y l / d f s z S C K V h g m r d 8 d z E + B l V h j O B k 1 I 3 1 Z h Q N q I D 7 F g q a Y T a z 2 a n T s i J V f o k j J U t a c h M / T 2 R 0 U j r c R T Y z o i a o V 7 0 p u J / X i c 1 4 Z W f c Z m k B i W b L w p T Q U x M p n + T P l f I j B h b Q p n i 9 l b C h l R R Z m w 6 J R u C t / j y M m m e V b 3 z q n t / U a n d 5 X E U 4 Q i O 4 R Q 8 u I Q a 3 E I d G

2 i U V q D Y V K w b Q P E E r o = " > A A A B 7 X i c b V D L S g N B E J y N r x h f U Y 9 e B o P g K e y q o M e g F 2 9 G M A 9 I l j A 7 6 U 3 G z G O Z m R X C k n / w 4 k E R r / 6 P N / / G S b I H T S x o K K q 6 6 e 6 K E s 6 M 9 f 1 v r 7 C y u r a + U d w s b W 3 v 7 O 6 V 9 w + a R q W a Q o M q r n Q 7 I g Y 4 k 9 C w z H J o J x q I i D i 0 o t H N 1 G 8 9 g T Z M y Q c 7 T i A U Z C B Z z C i x T m p 2 7 w Q M S K 9 c 8 a v + D H i Z B D m p o B z 1 X v m r 2 1 c 0 F S A t 5 c S Y T u A n N s y I t o x y m J S 6 q Y G E 0 B E Z Q M d R S Q S Y M J t d O 8 E n T u n j W G l X 0 u K Z + n s i I 8 K Y s Y h c p y B 2 a B a 9 q f i f 1 0 l t f B V m T C a p B U n n i + K U Y 6 v w 9 H X c Z x q o 5 W N H C N X M 3 Y r p k G h C r Q u o 5 E I I F l 9 e J s 2 z a n B e 9 e 8 v K r X r P I 4 i O k L H 6 B Q F 6 B L V 0 C 2 q o w a i 6 B E 9 o 1 f 0 5 i n v x X v 3 P u a t B S + f O U R / 4 H 3 + A F / b j v 0 = < / l a t e x i t > S t < l a t e x i t s h a 1 _ b a s e 6 4 = " Y y V p m o A d p m b A s y a / 4 + A w f S i 0 Q y g = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 l U 0 G P B i 9 4 q t R / Q h r L Z b t q l m 0 3 Y n Q g l 9 C d 4 8 a C I V 3 + R N / + N 2 z Y H b X 0 w 8 H h v h p l 5 Q S K F Q d f 9 d g p r 6 x u b W 8 X t 0 s 7 u 3 v 5 B + f C o Z e J U M 9 5 k s Y x 1 J 6 C G S 6 F 4 E w V K 3 k k 0 p 1 E g e T s Y 3 8 7 8 9 h P X R s T q E S c J 9 y M 6 V C I U j K K V G o 0 + 9 s s V t + r O Q V a J l 5 M K 5 K j 3 y 1 + 9 Q c z S i C t k k h r T 9 d w E / Y x q F E z y a a m X G p 5 Q N q Z D 3 r V U 0 Y g b P 5 u f O i V n V h m Q M N a 2 F J K 5 + n s i o 5 E x k y i w n R H F k V n 2 Z u J / X j f F 8 M b P h E p S 5 I o t F o W p J B i T 2 d 9 k I D R n K C e W U K a F v Z W w E d W U o U 2 n Z E P w l l 9 e J a 2 L q n d Z d R + u K r X 7 P I 4 i n M A p n I M H 1 1 C D O 6 h D E x g M 4 R l e 4 c 2 R z o v z 7 n w s W g t O P n M M f + B 8 / g A 7 o 4 3 H < / l a t e x i t > Z t < l a t e x i t s h a 1 _ b a s e 6 4 = " Q n A B F S g R X 4 U n T h 0 b U Y N 6 n G C E u v k = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 l U 0 G P B i 9 4 q 2 g 9 s Q 9 l s N + 3 S z S b s T o Q S + h O 8 e F D E q 7 / I m / / G b Z u D t j 4 Y e L w 3 w 8 y 8 I J H C o O t + O 4 W V 1 b X 1 j e J m a W t 7 Z 3 e v v H / Q N H G q G W + w W M a 6 H V D D p V C 8 g Q I l b y e a 0 y i Q v B W M r q d + 6 4 l r I 2 L 1 g O O E + x E d K B E K R t F K 9 4 8 9 7 J U r b t W d g S w T L y c V y F H v l b + 6 / Z i l E V f I J D W m 4 7 k J + h n V K J j k k 1 I 3 N T y h b E Q H v G O p o h E 3 f j Y 7 d U J O r N I n Y a x t K S Q z 9 f d E R i N j x l F g O y O K Q 7 P o T c X / v E 6 K 4 Z W f C Z W k y B W b L w p T S T A m 0 7 9 J X 2 j O U I 4 t o U w L e y t h Q 6 o p Q 5 t O y Y b g L b 6 8 T J p n V e + 8 6 t 5 d V G q 3 e R x F O I J j O A U P L q E G N 1 C H B j A Y w D O 8 w p s j n R f n 3 f m Y t x a c f O Y Q / s D 5 / A F G T Y 3 O < / l a t e x i t > A t < l a t e x i t s h a 1 _ b a s e 6 4 = " x 2 L 5 P 8 l 8 z H 2 v L x n o c p u n 9 d c p r q k = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 l U 0 G P F i 9 4 q 2 g 9 o Q 9 l s N + 3 S z S b s T o Q S + h O 8 e F D E q 7 / I m / / G b Z u D t j 4 Y e L w 3 w 8 y 8 I J H C o O t + O 4 W V 1 b X 1 j e J m a W t 7 Z 3 e v v H / Q N H G q G W + w W M a 6 H V D D p V C 8 g Q I l b y e a 0 y i Q v B W M b q Z + 6 4 l r I 2 L 1 i O O E + x E d K B E K R t F K D 9 c 9 7 J U r b t W d g S w T L y c V y F H v l b + 6 / Z i l E V f I J D W m 4 7 k J + h n V K J j k k 1 I 3 N T y h b E Q H v G O p o h E 3 f j Y 7 d U J O r N I n Y a x t K S Q z 9 f d E R i N j x l F g O y O K Q 7 P o T c X / v E 6 K 4 Z W f C Z W k y B W b L w p T S T A m 0 7 9 J X 2 j O U I 4 t o U w L e y t h Q 6 o p Q 5 t O y Y b g L b 6 8 T J p n V e + 8 6 t 5 f V G p 3 e R x F O I J j O A U P L q E G t 1 C H B j A Y w D O 8 w p s j n R f n 3 f m Y t x a c f O Y Q / s D 5 / A E g N 4 2 1 < / l a t e x i t > q(!|S f = s 2 , s 0 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " V 1 / b S q d w v Q K 3 A 4 / Q R b a I X g C g 2 1 U = " > A A A C A X i c b V D L S g M x F M 3 U V 6 2 v U T e C m 2 A R K k i Z q Y J u h K I b l x X t A 9 p h y K S Z N j T J j E l G K G P d + C t u X C j i 1 r 9 w 5 9 + Y t r P Q 6 o F 7 O Z x z L 8 k 9 Q c y o 0 o 7 z Z e X m 5 h c W l / L L h Z X V t f U N e 3 O r o a J E Y l L H E Y t k K 0 C K M C p I X V P N S C u W B P G A k W Y w u B j 7 z T s i F Y 3 E j R 7 G x O O o J 2 h I M d J G 8 u 2 d 2 1 I n 4 q S H 7 q / 9 E J 5 B 5 V c O T X M O f L v o l J 0 J 4 F / i Z q Q I M t R 8 + 7 P T j X D C i d C Y I a X a r h N r L 0 V S U 8 z I q N B J F I k R H q A e a R s q E C f K S y c X j O C + U b o w j K Q p o e F E / b m R I q 7 U k A d m k i P d V 7 P e W P z P a y c 6 P P V S K u J E E 4 G n D 4 U J g z q C 4 z h g l 0 q C N R s a g r C k 5 q 8 Q 9 5 F E W J v Q C i Y E d / b k v 6 R R K b t H Z e f q u F g 9 z + L I g 1 2 w B 0 r A B S e g C i 5 B D d Q B B g / g C b y A V + v R e

EQUATION

2.3. DECISON STATE VIC (DS-VIC):

We identify decision states by employing an information regularizer that finds states with minimum relevant option information. Formally, this means that at every timestep t in the trajectory, we minimize the mutual information I(Ω, A t |S t , S 0 = s) and the resulting states where this mutual information remains high despite the minimization are identified as decision states. Intuitively, this means that on average (across different options), a decision state is a state with higher relevant option information than other states (e.g. the red regions in Figure 1 ) Overall, our objective is to maximize:

EQUATION

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 information at each step.

Interestingly, Equation 2 has a clear, principled interpretation in terms of the empowerment I(Ω, S f |S 0 ) from the VIC model. We state the following lemma (full proof in Appendix):

Lemma 2.1 Let A t be the action random variable at timestep t and state S t following an optionconditioned policy π(a t |s t , ω). Then, I(Ω, A t |S t , S 0 ) i.e. the conditional mutual information between the option Ω and action A t when summed over all timesteps in the trajectory, upper bounds the conditional mutual information I(Ω, S f |S 0 ) between Ω and the final state S f -namely the empowerment as defined by Gregor et al. (2016) :

EQUATION

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

max J V IC s.t. U DS ≤ R (4)

where R > 0 is a constant. Thus, we can essentially target values of R we have in mind by maximizing the lower bound and minimizing the upper bound, by (in practice) sweeping different values of β in eq. ( 2). This is a result potentially of interest beyond the specific context of decision states (Achiam et al., 2018; Gregor et al., 2016) . Specifically, while the VIC objective only allows us to maximize the empowerment I(Ω, S f ) = H(S f ) -H(S f |Ω), imposing an upper bound can help control how 'abstract' the latent option representation is relative to the states S f , by finding solutions that have say a higher entropy H(S f |Ω) on states given options. This might lead to more abstract options that achieve better generalisation depending on downstream tasks. Note that most approaches currently limit the abstraction by constraining the number of discrete options, which (usually) imposes a (tighter) upper bound on H(Ω), since H ≥ 0 in the discrete case. However, this does not hold for the continuous case, where the bound might be more useful. Investigating this is beyond the scope of this current paper, however, as our central aim is to identify decision states, and not to scale the VIC framework to continuous options.

2.4. ALGORITHMIC DETAILS:

Upper Bounds for I(Ω, A t | S t , S 0 ). Inspired by InfoBot (Goyal et al., 2019) , we bottleneck the information in a statistic Z t of the state S t and option Ω used to parameterize the policy π(A t | Ω, S t ) (fig. 2 right ). This is justified by the the data-processing inequality (DPI) (Cover & Thomas, 1991) for the markov chain Ω, S t ↔ Z t ↔ A t , which implies I(Ω, A t | S t , S 0 ) ≤ I(Ω, Z t | S t , S 0 ). We can then obtain the following upper bound on I(Ω, Z t | S t , S 0 ) (see appendix for derivation):

EQUATION

where q(z t ) is a fixed variational approximation (set to N (0, I) as in InfoBot), and p φ (z t | ω, s t ) 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, A t | S t , S 0 ), while we bottleneck the option-information.

We can compute a Monte Carlo estimate of Equation 5 by first sampling an option ω at s 0 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, 2010) ) as a bonus to encourage sufficient exploration. Overall, the DS-VIC objective is:

max θ,φ,ν J(θ, φ, ν) = E Ω∼p(ω),τ ∼p J (•|Ω,S0),Zt∼p φ (zt|St,Ω) log q ν (Ω | S f , S 0 ) p(Ω) - f -1 t=0 β log p φ (Z t | S t , Ω) q(Z t ) + α log π θ (A t | S t , Z t ) (6)

where θ, φ and ν are the parameters of the policy, latent variable decoder and the option inference network respectively. Note that we abuse the notation slightly in Equation 6 by writing τ ∼ p J (• | ω, s 0 ) to denote a trajectory sampled by following π(• | ω, s 0 ). This is a sequential process where

Z t ∼ p φ (z t | s t , ω), A t ∼ π θ (a t | s t , z t ) and S t+1 ∼ p(s t+1 | s t , a t ) (state transition function).

The first term in the objective ensures reliable control in terms of visitation over a diverse set of final states in the environment while learning options; the second term ensures minimality in using the options sampled to make decisions (taking actions) and the third provides an incentive for exploration.

See algorithm 1 in appendix for more details on the entire training pipeline.

Handling Partial Observability. We are generally interested in identifying decision states in partially observable environments (similar to InfoBot Goyal et al. ( 2019)). To formalise how we handle this, let o t be the (partial) observation made by the agent at time t. We set the state s t = g(o 0 , • • • , o t ) in all the equations above, where g is a recurrent neural network (RNN) (Hochreiter & Schmidhuber, 1997) encoding partial observations. We found it important to parameterize the policy (Figure 2 With the sum over all timesteps for I(Ω, S t ), the bound in theorem 2.1 no longer holds true, which also means that there is no principled reason (unlike our model) to scale the second term with β -which we find to be crucial for identifying decision states (similar to findings in InfoBot). Experimentally, we show that the decision states with DIAYN are no longer as interpretable, since options in this case are more low level and correspond to trajectories instead of goals.

The most closely related work to ours is InfoBot, which maximizes t R(t) -βI(A t , G|S t ) for a goal (G) conditioned policy π(a t |S t , G). The key difference is that InfoBot requires extrinsic rewards, while our work is strictly more general and scales even in the absence of extrinsic rewards.

Further, in context of both these works, our work provides a principled connection between actionoption information reqularization I(A t , Ω|S t ) and empowerment of an agent. The tools from Theorem 2.1 might be useful for analysing these previous objectives which both employ this technique. 

3. EXPERIMENTS:

EQUATION

The count-based reward2 decays with square root of c(S t ) to encourage the model to explore novel states, and the mutual information between goal G and bottleneck variable Z t identifies decision states, and is multiplied with the exploration bonus to encourage visitation of decision states. We use an almost identical setup, replacing their decision-state term from supervised pretraining with DS-VIC intrinsic reward pretraining:

d Y g = " > A A A B / n i c b V D L S g N B E J y N r x h f q + L J y 2 A Q v B h 2 j a A X I e j F Y w T z g G w I s 5 N O M m T 2 w U y v G J a A v + L F g y J e / Q 5 v / o 2 T Z A + a W N B Q V H X T 3 e X H U m h 0 n G 8 r t 7 S 8 s r q W X y 9 s b G 5 t 7 9 i 7 e 3 U d J Y p D j U c y U k 2 f a Z A i h B o K l N C M F b D A l 9 D w h z c T v / E A S o s o v M d R D O 2 A 9 U P R E 5 y h k T r 2 g e c D M n p F P Y R H R E x d O C 2 P O 3 b R K T l T 0 E X i Z q R I M l Q 7 9 p f X j X g S Q I h c M q 1 b r h N j O 2 U K B Z c w L n i J h p j x I e t D y 9 C Q B a D b 6 f T 8 M T 0 2 S p f 2 I m U q R D p V f 0 + k L N B

L t Z R U L X c p V 5 y f M j D 8 H q O 3 x i J k = " > A A A B + 3 i c b V D L S g N B E J y N r x h f M R 6 9 D A b B U 9 h V Q S 9 C 0 I v H C O Y B y R J m J 7 3 J k N n Z Z a Z X E p b 8 i h c P i n j 1 R 7 z 5 N 0 4 e B 0 0 s a C i q u u n u C h I p D L r u t 5 N b W 9 / Y 3 M p v F 3 Z 2 9 / Y P i o e l h o l T z a H O Y x n r V s A M S K G g j g I l t B I N L A o k N I P h 3 d R v P o E 2 I l a P O E 7 A j 1 h f i V B w h l b q F k u d A J D R G 9 p B G C F i 5 k 2 6 x b J b c W e g q 8 R b k D J Z o N Y t f n V 6 M U 8 j U M g l M 6 b t u Q n 6 G d M o u I R J o Z M a S B g f s j 6 0 L V U s A u N n s 9 s n 9 N Q q P R r G 2 p Z C O l N / T 2 Q s M m Y c B b Y z Y j g w y 9 5 U / M 9 r p x h e + 5 l Q S Y q g + H x R m E q K M Z 0 G Q X t C A 0 c 5 t o R x L e y t l A + Y Z h x t X A

Q d Q D C z U 1 l l F L T j K 6 e a u e 7 7 H i M = " > A A A B 9 X i c b V D J S g N B E K 2 J W 4 x b 1 K O X x i B 4 C j M q 6 D E u B 7 1 I B L N I M o a e T i d p 0 r P Q X a O G I f / h x Y M i X v 0 X b / 6 N n W Q O m v i g 4 P F e F V X 1 v E g K j b b 9 b W X m 5 h c W l 7 L L u Z X V t f W N / O Z W V Y e x Y r z C Q h m q u k c 1 l y L g F R Q o e T 1 S n P q e 5 D W v f z 7 y a w 9 c a R E G t z i I u O v T b i A 6 g l E 0 0 n 0 T + R M i J h d X p 3 f X w 1 a + Y B f t M c g s c V J S g B T l V v 6 r 2 Q 5 Z 7 P M A m a R a N x w 7 Q j e h C g W T f J h r x p p H l P V p l z c M D a j P t Z u M r x 6 S P a O 0 S S d U p g I k Y / X 3 R E J 9 r Q e + Z z p 9 i j 0 9 7 Y 3 E / 7 x G j J 0 T N x F B F C M P 2 G R R J 5 Y E Q z K K g L S F 4 g z l w B D K l D C 3 E t a j i j I 0 Q e V M C M 7 0 y 7 O k e l B 0 D o v 2 z V G h d J b G k Y U d 2 I V 9 c O A Y S n A J Z a g A A w X P 8 A p v 1 q P 1 Y r 1 b H 5 P W j J X O b M M f W J 8 / f c G S f g = = <

K R E A q e C j Q v d W L G I B E Z s I m A f G Z c t L p W N q J U e o d S V w B q v e S I m v V O J u t M n M F T z k T z + v E L w U h E M b C A z h b Y E h x J M k c I L R k E k m h A q u b V y G R h I L O q B D s O d f X i T N k p W r F u z r V W h Z H H u j A R G N j p H V X S N q i B K E r Q M p F b a T W K G x + z p y R z R T R H x i f P R K k M = < /

EQUATION

I(•) is computed with eq. ( 5) with a parameterized p(z t | ω, s t ) encoder frozen during transfer. See Algorithm 1 in appendix for more details.

Environments. We pre-train and test on gridworlds 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 across multiple runs. We also conduct experiments on Mountain-Car (Brockman et al., 2016) , a continuous state-space environment with discrete actions. In all pre-training environments, options are executed for a fixed number of steps before terminating.

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 will release our code upon publication.

4. RESULTS:

Baselines. We evaluate the following on quality of exploration and transfer to downstream goal-driven tasks with sparse rewards: 1) InfoBot (our implementation) -which does goal-driven extraction of decision states, 2) DIAYN -whose focus is unsupervised skill acquisition (and not decision states)3 , but has an I(A t , Ω|S t ) 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(Ω, Z t |S t , S 0 ) with 1 in Equation 8), 4) a randomly initialized encoder p(z t | ω, s t ) to check if learning in DS-VIC or InfoBot models improves over random initialization, 5) how different values of β affect performance, and 6) a heuristic baseline that looks for local features like corners and doorways and uses every such occurrence as a decision state. This validates the extent to which relevant goal information is useful in identifying decision states, vs. local, feature-based heuristics.

4.1. QUALITATIVE RESULTS:

Grid Worlds: Figure 3 shows results on 4-Room and maze. We notice that when β = 1, DS-VIC collapses to identifying every state as a decision state and gets poor empowerment: 0.51 (row 1, column 3 in Figure 3 ), indicating that the regularization strength is too high and hinders empowerment maximization. At lower values of β = 1e-3, we get more discernible decision states. Across both environments, we notice that some corners and intersections are identified as decision states. In general, for DS-VIC on maze with β = 1e-3 (when it gets an empowerment of 2.61), we notice that if an intersection is a decision state, and there is a corner next to it, it is often not a decision state. That is, not every state which looks like an corner needs to be a decision state, if for example the part of the state space in question is only spanned by one option. Finally, for maze we see that for a similar value of empowerment4 , DS-VIC leads to a sparser decision state distribution than DIAYN. This makes sense, since intuitively, one expects to have to make more decisions when following a particular trajectory (as in DIAYN), as opposed to a terminal state (as in DS-VIC). , point-radius proportional to I(Ω, Z t |s t , s 0 ), we find that decision states occur at points in the state-space where trajectories associated with different options intersect. Intuitively, these are the states where the agent can switch from one option (mode of behavior) to another and therefore, needs to make a decision. Interestingly, there is a dominance of decision states along the velocity = 0 line, which indicates that the model identifies decision states to be points where the cart has velocity = 0 at some position (specific to the option). Finally, decision states often occur, for say, the orange option (Ω 1 ) in the right half of the position-velocity plane and never in the bottom-left quadrant, where it is the only option covering that part of the state-space, and thus default behavior can be practiced. 1 : Success rate (mean ± standard error) of the goal-conditioned policy when trained with different exploration bonuses in addition to the extrinsic reward Re(t). We report results at ∼5 × 105 timesteps for MultiRoomN3S4, MultiRoomN5S4 and at ∼8.2 × 106 timesteps for MultiRoomN6S25. We also report the performance of InfoBot for completeness. Note that for rooms of size 4 (MultiRoomN3S4, MultiRoomN5S4), incentivizing to visit corners and doorways (Heuristic Decision States) is equivalent to count-based exploration.

4.2. QUANTITATIVE RESULTS:

Transfer to Goal-Driven Tasks. Next, we evaluate Equation 8, i.e. whether incentivizing the agent to visit decision states in addition to extrinsic reward can aid in transfer to goal-driven tasks in different environments (see Sec. 3.1). We restrict ourselves to the point-navigation task (Goyal et al., 2019) transfer in the MultiRoomNXSY set of partially-observable environments. In this task, the agent is always spawned in 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 correct cell. Goyal et al. (2019) test the efficacy of different exploration objectives 5 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 DS-VIC to identify decision states (Equation 2) on MultiRoomN2S6 and transfer to a goal-driven task on Overall Trends. Table . 1 reports success rate -the % of times the agent reaches the goal on validation. First, our implementation of InfoBot is competitive with Goyal et al. (2019) 6 . For the MultiRoomN2S6 to N5S4 transfer (middle column), methods which identify decision states outperform count-based exploration. Interestingly, in this setup, a randomly initialized encoder is competitive with both InfoBot and DS-VIC, and serves as an important baseline. In MultiRoomN2S10 to N6S25 transfer, which has a large state space, we find that DS-VIC (at β = 10 -2 ) achieves the best performance, followed by count-based exploration and InfoBot (that are both within standard-error of each other). This shows that decision states identified by DS-VIC effectively guide exploration in sparse-reward settings. More importantly, our model beats a strong heuristic baseline which treats every corner and doorway as a decision state (more details on this are in the appendix). Finally, the randomly initialized encoder as well as DIAYN 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, followed by 10 -5 and 10 -3 . In general, performance is robust, i.e. across β, we seem to reach ≈ 90% success for most values. More results on N6S25. To better understand Equation 8 compared to other exploration incentives, in addition to success rate and sample-efficiency (Figure 6 ), we also consider another metric where we count the number of unique rooms reached (other than the starting room 0) as training progresses (Figure 6 (c)). Across metrics, DS-VIC performs the best on the challenging N6S25 transfer. Furthermore, the unique room metric reveals that DIAYN gets stuck after exploring the first room.

5. RELATED WORK:

Intrinsic Control and Intrinsic Motivation. Learning how to explore without extrinsic rewards is a foundational problem in Reinforcement Learning (Machado et al., 2017; Pathak et al., 2017; Gregor et al., 2016; Strehl & Littman, 2008; 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 (Stadie et al., 2015; 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 at every state along the trajectory, and Achiam et al. (2018) learn options for entire trajectories by encoding the sequence of states at regular intervals. Since decision states are more related to 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 (Galashov et al., 2018; 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. 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.

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 & Barto, 2001) or use a diffusion model built using an MDP's transition matrix (Machado et al., 2017; Şimşek & Barto, 2004; Theocharous & Mahadevan, 2002) . The key distinction between bottleneck states and decision states 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) . Concretely, while a corner in a room need not be a bottleneck state, since visiting a corner does not 'open up' new states (the way a doorway would), it is still a useful state for a goal-driven agent with partial observation to visit (since it is a distinct landmark in the state space where meaningful decisions can be made).

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 & Schwab, 2017; Still et al., 2004) , sparse coding (Chalk et al., 2016) , classification using deep learning (Alemi et al., 2016; Achille & Soatto, 2016) , cognitive science and language (Zaslavsky et al., 2018) and reinforcement learning (Goyal et al., 2019; Galashov et al., 2018; Strouse et al., 2018) . We apply an information regularizer to an RL agent that must learn without extrinsic rewards to identify decision states.

6. CONCLUSION:

We devise a principled approach to identify decision states in an environment without any extrinsic reward supervision using a sandwich bound on the empowerment of Gregor et al. (2016) . Our approach yields decision states that align with human intuition across environments, and aid directed exploration on external-reward tasks and subsequently lead to better success rate and sample complexity in novel environments (competitive to supervised decision states of Goyal et al. (2019) ). All our code and environments will be made publicly available.

Repeating the same set of steps recursively gives us:

I(Ω, S f |S 0 ) ≤ I(Ω, (S f -1 , A f -1 )|S 0 )

DPI (Cover & Thomas, 1991) 

(12a) = I(Ω, S f -1 |S 0 ) + I(Ω, A f -1 |S f -1 , S 0 ) Chain rule of MI (12b) = I(Ω, S f -2 |S 0 ) + I(Ω, A f -2 |S f -2 , S 0 ) + I(Ω, A f -1 |S f -1 , S 0 ) Same as 12a-12b (12c) • • • (12d) = I(Ω, S 0 |S 0 ) + f t=1 I(Ω, A t |S t , S 0 ) (12e) (12f)

Note that the graphical model presented in Fig. 2 implies that Ω ⊥ ⊥ S 0 and hence,

EQUATION

A.3 UPPER BOUND ON I(A t , Ω|S t , S 0 )

We explain the steps to derive Eqn. (4) in the main paper, as an upper bound on I(A t , Ω|S t , S 0 ). By the data processing inequality (Cover & Thomas, 1991) 

The key difference here is that our objective here uses the options Ω internal to the agent as opposed to Goyal et al. (2019) , who use external goal specifications g provided to the agent. Similar to VIC, p J here denotes the (unkown) state distribution at time t from which we can draw samples when we execute a policy.

We then assume a variational approximation q(z t )7 for p(z t |S t ), and using the fact that D KL [p(z t |s t )||q(z t )] ≥ 0, we get a the following lower bound:

EQUATION

A.4 DECISION STATE DISCOVERY -ON POLICY WITH OPTIONS.

We use Eqn. 16 to discover and visualize the decision states learned in an environment, augmented with random sampling of the start state S 0 . Thus, we compute our decision states in an on-policy manner. Mathematically, we can write this as:

EQUATION

where S 0 is a random spawn location uniformly chosen from the set of states in the environment and Ω is a random option chosen at each of the spawn locations. Thus, for each state S t in the environment, we look at the aggregate of all the trajectories that pass through it and compute the values of log p(zt|ω,st) q(zt)

to identify / visualize decision states. In addition to being principled, this methodology also precisely captures our intuition that it is possible to identify decision states which are common to, or frequented across multiple options. Our results section 4 show that the identified decision states match our assessments of decision states corresponding to some structural regularities in the environment.

A.5 IDENTIFICATION OF DECISION STATES DURING TRANSFER:

As mentioned in the main paper, we would like to compute I(Ω, Z t |S t , S 0 ) to identify decision states and given a (potentially) novel environment and a novel goal-conditioned task, to provide it an exploration bonus. Given a state s , that we would like to compute I(Ω, Z t |S t = s , S 0 ), we can write: ω,s0 dz t p(ω)p(s 0 )p J (S t = s |s 0 , ω)p(z t |s t , ω) log p(z t |ω, S t = s ) q(z t )

However, this cannot be computed in this form in a transfer task, since a goal driven agent is not following on-policy actions for an option Ω that would allow us to draw samples from p J (•|S 0 , Ω) above (in order to do a monte-carlo estimate of the integral above). Thus instead, we propose to compute the mutual information as follows:

ω,s0

EQUATION

Now, given a state S t = s , this requires us to draw samples from p(s 0 , ω|S t = s ), which in general is intractable (since this requires us to know p J (s t |Ω), which is not available in closed form). In order to compute the above equation, we make the assumption that p(s 0 , ω|S t = s ) = p(s 0 )p(ω).

Breaking it down, this makes two assumptions: firstly, p(ω|S t = s , s 0 ) = p(ω|s 0 ). This means that all options have equal probability of passing through a state s at time t, which is not true in general.

The second assumption is the same as VIC, namely that p(ω|s 0 ) = p(ω). Instead of making this assumption, one could also fit a parameterized variational approximation to p(ω|S t = s , s 0 ) and train it in conjunction with VIC. However, we found our simple scheme to work well in practice, and thus avoid fitting an additional variational approximation.

A.6 DECISION STATES FROM LOCAL OBSERVATIONS:

In the main paper, our results assumed that one had access to a good SLAM routine that did mapping and localization from partial observations {u 0 , • • • , u t }. In general, as we discuss in the main paper, this is not a bad assumption since our model is always trained on a single environment, and thus it is reasonable for us to expect it to have a sense of the (x, y) coordinates in its internal representation / weights as training progresses. In this section, we detail some of the pathologies that we observed when kicking off training, if we took a naive approach to SLAM, estimating a function f ({u 0 , • • • , u t }) to directly regress to Ω from partial observations (Algorithm 1). We note that since our particular choice of environment is a discrete gridworld, several partial observations (especially for small agent view sizes like the 3x3 window) look the same to the agent and the agent has a tendency to converge to the most trivial optima for learning options -one which learns to end at an easily obtainable partial observation given an option. For instance, while training DS-VIC, one particular policy simply learned 4 options corresponding to the four cardinal directions the agent can face, and each can be achieved by left or right turns, without actually requiring any movement by the agent. Since the agent has a compass which tells it the direction it is facing, it can ignore the partial observation and just use the direction vector to predict which of the 4 options was sampled.

A.7 BASELINES:

We use an exploration bonus coefficient of κ = 0.1 for the count-based exploration bonus baseline. The heuristic baseline identifies all occurrences of the following types of states in the MultiRoom environments -(1) corners of the room, (2) doorways, and gives them a slightly higher coefficient of exploration bonus than the κ used for the count-based bonus. We ran a sweep for the values of this higher coefficient and found that 0.105 (i.e. a +5% increase) gave best results.

A.8 IMPLEMENTATION DETAILS:

Network Architecture: We use a 3 layered convolutional neural network with kernels of size 3x3, 2x2 and 2x2 in the 3 layers respectively to process the agent's egocentric observation. We use ReLU as the non-linear activation function after each convolutional layer. The output of the CNN is then concatenated with the agent's direction vector (compass) and the option (or goal encoding). The concatenated features are then passed through a linear layer with hidden size 64 to produce the final features used by option encoder p φ (z t |s t , ω) head and the policy head π θ (a t |s t , z t ). We use the (x, y) coordinates of the final state (embedded through a linear layer of hidden size 64) to regress to the option via q ν (ω|s 0 , s f ). Furthermore, our parameterized policy is a reactive one and the encoder p φ (z t |s t , ω) is recurrent over the sequence of states encountered in the episode. The bottleneck random variable Z t is sampled from the parameterized gaussian p φ (z t |s t , ω) and is made a differentiable stochastic node using the re-parmaterization trick for gaussian random variables.

Training Details: We use Advantage Actor-Critic (A2C) (open-sourced implementation by Kostrikov ( 2018)) for all our experiments. We use RMSprop as the optimizer for all our experiments. For the partially-observable grid world settings, the agent receives an egocentric view of it's surroundings as input, encoded as an occupancy grid where the channel dimension specifies whether the agent or an obstacle is present at an (x, y) location. We set the coefficient α in Eqn. 6 to be 10 -3 for all our experiments based on sweeps conducted across multiple values. In practice, we found it to be difficult to optimize our unsupervised objective in absence of an entropy bonus -the parameterized policy collapses to a deterministic one and no options are learned in addition to inefficient exploration of the state-space. Moreover, we found that it was hard to obtain reasonable results by optimizing for both the terms in the objective from scratch and therefore, we optimize the intrinsic objective itself for ∼ 8k episodes (i.e., we set β = 0) after which we turn on the regularization term and let β grow linearly for another ∼ 8k episodes to get feasible outcomes at convergence. We experiment with a vocabulary of 2, 4 and 32 options (imitating undercomplete and overcomplete settings) for all the environments. For all the exploration incentives presented in Table 1 , we first picked a value of κ in Eqn. 7 (decides how to weigh the bonus with respect to the reward) from {10, 1, 0.1, 0.01, 0.001, 0.0001} based on the best sample-complexity on goal-driven transfer.

InfoBot Implementation: Since code to reproduce InfoBot (Goyal et al., 2019) was not publiclt available, we implemented InfoBot ourselves while making sure that we are consistent with the architectural and hyper-parameter choices adopted by InfoBot (as per the A2C implementation by (Chevalier-Boisvert et al., 2018) ). (i) We replace the convolution layers with fully connected layers to process the observations, and (ii) we use the layer sizes as mentioned by (Goyal et al., 2019) in the appendix. The checkpoint used to report the final performance for N3S4 and N5S4 were picked by doing validation on the transfer task based on the success metric. However, this procedure was infeasible for the bigger N6S25 environment and we chose the last checkpoint from the training for this environment.

Convergence Criterion. In practice, we observe that it is hard to learn a large number of discrete options using the unsupervised objective. From the entire option vocabulary, the agent only learns a few number of options discriminatively (as identified by the option termination state), with the rest collapsing into the same set of final states. To pick a suitable checkpoint for the transfer experiments, we pick the ones which have learned the maximum number of options reliably -as measured by the likelihood of the correct option from the final state log q ν (ω|s 0 , s f ).

Option Curriculum It is standard to have a fixed-sized discrete option space Ω with a uniform pior (Gregor et al., 2016) . However, learning a meaningful option space with larger option vocabulary size |Ω| = K has been reported to be difficult Achiam et al. (2018) . We adopt a curriculum based approach proposed in Achiam et al. (2018) where the option vocabulary size is gradually increased as the option decoder q ν (ω|s f ) becomes more confident in mapping back the final state back to the corresponding option sampled at the beginning of the episode. More concretely, whenever q ν (ω|s 0 , s f ) > 0.75 (threshold chosen via hyperparameter tuning), the option vocabulary size increases according to

K ← min int 1.5 × K + 1 , K max

For our experiments, we start from K = 2 and terminate the curriculum when K = K max = 32.

We run each of our experiments on a single GTX Titan-X GPU, and use no more than 1 GB of GPU memory per experimental setting.

A.9 ADDITIONAL RESULTS

In Fig. 7 and Fig. 8 , we show further results on the MultiRoomN3S4 and MultiRoomN5S4 environments to compare DS-VIC with other exploration incentives in terms of sample-complexity and the quality of the exploration incentive. As seen in the figures, DS-VIC is either competitive with or better than the presented baselines. As highlighted before, MultiRoomN3S4 and MultiRoomN5S4 Table 2 : Success rate (mean ± standard error) of the goal-conditioned policy when trained with different exploration bonuses in addition to the extrinsic reward Re(t). We report results at ∼5 × 10 5 timesteps for MultiRoomN3S4, MultiRoomN5S4 and at ∼8.2 × 10 6 timesteps for MultiRoomN6S25. We also report results from InfoBot (Goyal et al., 2019) for completeness. Note that for rooms of size 4 (MultiRoomN3S4, MultiRoomN5S4), incentivizing to visit corners and doorways (Heuristic Decision States) is equivalent to count-based exploration.

are relatively simpler environments where simpler baselines like count based exploration incentives also perform quite well due to the small size of rooms.

In Table . 2, we report broader comparisons with other exploration baselines InfoBot (Goyal et al., 2019) compare with. 

:

This has potential implications beyond the context of this paper, for example, in training VIC models which target a particular amount of "compression" in the option (Ω) representation, similar representational choices for supervised(Tishby et al., 1999) and unsupervised learning(Alemi et al.,

2016).

Visitation counts have several limitations including the requirement of a discrete state space and a state table for maintaining visit counts in POMDPs. However, our exploration bonus need not be restricted by these assumptions. One could alternatively use a technique similar toBurda et al. (2018) where the incentive is to learn to distill a trained encoder network, alleviating the need for visitation counts altogether.

Note that to keep things consistent with our method and InfoBot, we use I(Zt, Ω|St) to impose the mutual information regularization in DIAYN, whereasEysenbach et al. (2018) use a different construction.

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.

While our focus is on identifying and probing how good the decision states from intrinsic training are, more broader comparisons to exploration baselines are in InfoBot(Goyal et al., 2019) (reproduced in the appendix).

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

For our experiments, we fix q(zt) to be a unit gaussian, however it could also be learned.

Figures and Tables:

s B g A M / w C m + O d F 6 c d + d j 3 l p w 8 p l D + A P n 8 w e 5 G I 1 x < / l a t e x i t >

s B g A M / w C m + O c F 6 c d + d j 3 l p w 8 p l D + A P n 8 w e 6 n I 1 y < / l a t e x i t > ⌦ < l a t e x i t s h a 1 _ b a s e 6 4 = " F t a c 6 Y T H 9 z

Figure 2: Illustration of VIC for 2 timesteps. L: Given a start state S0, VIC samples option ω and follows policy π(at | Ω = ω, st) and infers Ω from the terminating state (S2), optimizing a lower bound on I(S2, Ω | S0). R: DS-VIC considers a particular parameterization of π and imposes a bottleneck on I(At, Ω|St).

TRANSFER TO GOAL-DRIVEN TASKS Do the unsupervised decision states meaningfully transfer to novel tasks? To address this, we replicate the InfoBot experimental setup, replacing decision state identification (pre-training) with DS-VIC. Exploration-based Transfer. Goyal et al. (2019) pretrain their model to identify decision states, and then study if decision states improve exploration when training a new policy π γ (a|s, g) from scratch. Given an environment with reward R e (t), goal G, κ > 0, and state visitation count c(S t ), their reward is:

t e x i t s h a 1 _ b a s e 6 4 = " j 4 5 k Q u 7 g K 5 w k o 9 O 0 7 C p 1 b r k 5

6 F P i m M 2 A 4 0 P P e R P z P a y X Y u 2 y n I o w T h J D P F v U S S T G i k y x o V y j g K E e G M K 6 E u Z X y A V O M o 0 m s Y E J w 5 1 9 e J P W z k l s u O X f n x c p 1 F k e e H J I j c k J c c k E q 5 J Z U S Y 1 w k p J n 8 k r e r C f r x X q 3 P m a t O S u b 2 S d / Y H 3 + A B d a l O s = < / l a t e x i t > = 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " C /

U b g r f 8 8 i p p n F e 8 i 4 r 7 c F m u 3 i 7 i y J N j c k L O i E e u S J X c k x q p E 0 5 G 5 J m 8 k j d n 4 r w 4 7 8 7 H v D X n L G a O y B 8 4 n z 9 o + Z Q I < / l a t e x i t > Maze = 1e-3 < l a t e x i t s h a 1 _ b a s e 6 4 = " j 4 5 k Q u 7 g K 5 w k o 9 O 0 7 C p 1 b r k 5 d Y g = " > A A A B / n i c b V D L S g N B E J y N r x h f q + L J y 2 A Q v B h 2 j a A X I e j F Y w T z g G w I s 5 N O M m T 2 w U y v G J a A v + L F g y J e / Q 5 v / o 2 T Z A + a W N B Q V H X T 3 e X H U m h 0 n G 8 r t 7 S 8 s r q W X y 9 s b G 5 t 7 9 i 7 e 3 U d J Y p D j U c y U k 2 f a Z A i h B o K l N C M F b D A l 9 D w h z c T v / E A S o s o v M d R D O 2 A 9 U P R E 5 y h k T r 2 g e c D M n pF P Y R H R E x d O C 2 P O 3 b R K T l T 0 E X i Z q R I M l Q 7 9 p f X j X g S Q I h c M q 1 b r h N j O 2 U K B Z c w L n i Jh p j x I e t D y 9 C Q B a D b 6 f T 8 M T 0 2 S p f 2 I m U q R D p V f 0 + k L N B 6 F P i m M 2 A 4 0 P P e R P z P a y X Y u 2 y n I o w T h J D P F v U S S T G i k y x o V y j g K E e G M K 6 E u Z X y A V O M o 0 m s Y E J w 5 1 9 e J P W z k l s u O X f n x c p 1 F k e e H J I j c k J c c k E q 5 J Z U S Y 1 w k p J n 8 k r e r C f r x X q 3 P m a t O S u b 2 S d / Y H 3 + A B d a l O s = < / l a t e x i t > = 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " C / L t Z R U L X c p V 5 y f M j D 8 H q O 3 x i J k = " > A A A B + 3 i c b V D L S g N B E J y N r x h f M R 6 9 D A b B U 9 h V Q S 9 C 0 I v H C O Y B y R J m J 7 3 J k N n Z Z a Z X E p b 8 i h c P i n j 1 R 7 z 5 N 0 4 e B 0 0 s a C i q u u n u C h I p D L r u t 5 N b W 9 / Y 3 M p v F 3 Z 2 9 / Y P i o e l h o l T z a H O Y x n r V s A M S K G g j g I l t B I N L A o k N I P h 3 d R v P o E 2 I l a P O E 7 A j 1 h f i V B w h l b q F k u d A J D R G 9 p B G C F i 5 k 2 6 x b J b c W e g q 8 R b k D J Z o N Y t f n V 6 M U 8 j U M g l M 6 b t u Q n 6 G d M o u I R J o Z M a S B g f s j 6 0 L V U s A u N n s 9 s n 9 N Q q P R r G 2 p Z C O l N / T 2 Q s M m Y c B b Y z Y j g w y 9 5 U / M 9 r p x h e + 5 l Q S Y q g + H x R m E q K M Z 0 G Q X t C A 0 c 5 t o R x L e y t l A + Y Z h x t X A U b g r f 8 8 i p p n F e 8 i 4 r 7 c F m u 3 i 7 i y J N j c k L O i E e u S J X c k x q p E 0 5 G 5 J m 8 k j d n 4 r w 4 7 8 7 H v D X n L G a O y B 8 4 n z 9 o + Z Q I < / l a t e x i t > DIAYN < l a t e x i t s h a 1 _ b a s e 6 4 = " z 3

/ l a t e x i t > DIAYN < l a t e x i t s h a 1 _ b a s e 6 4 = " z 3 Q d Q D C z U 1 l l F L T j K 6 e a u e 7 7 H i M = " > A A A B 9 X i c b V D J S g N B E K 2 J W 4 x b 1 K O X x i B 4 C j M q 6 D E u B 7 1 I B L N I M o a e T i d p 0 r P Q X a O G I f / h x Y M i X v 0 X b / 6 N n W Q O m v i g 4 P F e F V X 1 v E g K j b b 9 b W X m 5 h c W l 7 L L u Z X V t f W N / O Z W V Y e x Y r z C Q h m q u k c 1 l y L g F R Q o e T 1 S n P q e 5 D W v f z 7 y a w 9 c a R E G t z i I u O v T b i A 6 g l E 0 0 n 0 T + R M i J h d X p 3 f X w 1 a + Y B f t M c g s c V J S g B T l V v 6 r 2 Q 5 Z 7 P M A m a R a N x w 7 Q j e h C g W T f J h r x p p H l P V p l z c M D a j P t Z u M r x 6 S P a O 0 S S d U p g I k Y / X 3 R E J 9 r Q e + Z z p 9 i j 0 9 7 Y 3 E / 7 x G j J 0T N x F B F C M P 2 G R R J 5 Y E Q z K K g L S F 4 g z l w B D K l D C 3 E t a j i j I 0 Q e V M C M 7 0 y 7 O k e l B 0 D o v 2 z V G h d J b G k Y U d 2 I V 9 c O A Y S n A J Z a g A A w X P 8 A p v 1 q P 1 Y r 1 b H 5 P W j J X O b M M f W J 8 / f c G S f g = = </ l a t e x i t > t e x i t s h a 1 _ b a s e 6 4 = " p u r q k A + T I F q H 0 V k 2 8 m f z m P t k 6 4 E = " > A A A B 9 H i c b V D J S g N B E O 2 J W 4 x b 1 K O X x i B 4 G m Z c U G 9 B L x 4 j m A W S I f R 0 a p I m P Y v d N c E w 5 D u 8 e F D E q x / j z b + x k 8 x B o w 8 K H u 9 V U V X P T 6 T Q 6 D h f V m F p e W V 1 r b h e 2 t j c 2 t 4 p 7 + 4 1 d J w q D n U e y 1 i 1 f K Z B i g j q K F B C K 1 H A Q l 9 C 0 x / e T P 3 m C J Q W c X S P 4 w S 8 k P U j E Q j O 0 E h e B + E R E T P X P r + a d M s V x 3 Z m o H + J m 5 M K y V H r l j 8 7 v Z i n I U T I J d O 6 7 T o J e h l T K L i E S a m T a k g Y H 7 I + t A 2 N W A j a y 2 Z H T + i R U X o 0 i J W p C O l M / T m R s V D r c e i b z p D h Q C 9 6 U / E / r 5 1 i c O l l I k p S h I j P F w W p p B j T a Q K 0 J x R w l G N D G F f C 3 E r 5 g C n G 0 e R U M i G 4 i y / / J Y 0 T 2 z 2 1 n b u z S v U 6 j 6 N I D s g h O S Y u u S B V c k t q p E 4 4 e S B P 5 I W 8 W i P r 2 X q z 3 u e t B S u f 2 S e / Y H 1 8 A 1 R I k c w = < / l a t e x i t > 0.51 < l a t e x i t s h a 1 _ b a s e 6 4 = " q x f 8 G T 1 3 + J d Y 3 v 7 z e J j p P A G J o N w= " > A A A B 9 H i c b V D J S g N B E O 2 J W 4 x b 1 K O X x i B 4 G m Z c 0 G P Q i 8 c I Z o F k C D 2 d m q R J z 2 J 3 T T A M + Q 4 v H h T x 6 s d 4 8 2 / s J H P Q x A c F j / e q q K r n J 1 J o d J x v q 7 C y u r a + U d w s b W 3 v 7 O 6 V 9 w 8 a O k 4 V h z q P Z a x a P t M g R Q R 1 F C i h l S h g o S + h 6 Q 9 v p 3 5 z B E q L O H r A c Q J e y P q R C A R n a C S v g / C E i J l j X 7 q T b r n i 2 M 4 M d J m 4 O a m Q H L V u + a v T i 3 k a Q o R c M q 3 b r p O g l z G F g k u Y l D q p h o T x I e t D 2 9 C I h a C 9 b H b 0 h J 4 Y p U e D W J m K k M 7 U 3 x M Z C 7 U e h 7 7 p D B k O 9 K I 3 F f / z 2 i k G 1 1 4 m o i R F i P h 8 U Z B K i j G d J k B 7 Q g F H O T a E cS X M r Z Q P m G I c T U 4 l E 4 K 7 + P I y a Z z Z 7 r n t 3 F 9 U q j d 5 H E V y R I 7 J K X H J F a m S O 1 I j d c L J I 3 k m r + T N G l k v 1 r v 1 M W 8 t W P n M I f k D 6 / M H R p i R w w = = < / l a t e x i t > 2.05 < l a t e x i t s h a 1 _ b a s e 6 4 = " H Q K F f 0 i R 6 D 9 Z M O w X 0 b c l p S / Y g l U = " > A A A B 9 H i c b V B N S 8 N A E N 3 4 W e t X 1 a O X Y B E 8 h a Q q e i x 6 8 V j B f k A b y m Y 7 a Z d u N n F 3 U i y h v 8 O L B 0 W 8 + m O 8 + W / c t j l o 6 4 O B x 3 s z z M w L E s E 1 u u 6 3 t b K 6 t r 6 x W d g q b u / s 7 u 2 X D g 4 b O k 4 V g z q L R a x a A d U g u I Q 6 c h T Q S h T Q K B D Q D I a 3 U 7 8 5 A q V 5 L B 9 w n I A f 0 b 7 k I W c U j e R 3 E J 4 Q M a s 4 7 u W k W y q 7 j j u D v U y 8 n J R J j l q 3 9 N X p x S y N Q C I T V O u 2 5 y b o Z 1 Q h Z w I m x U 6 q I a F s S P v Q N l T S C L S f z Y 6 e 2 K d G 6 d l h r E x J t G f q 7 4 m M R l q P o 8 B 0 R h Q H e t G b i v 9 5 7 R T D a z / j M k k R J J s v C l N h Y 2 x P E 7 B 7 X A F D M T a E M s X N r T Y b U E U Z m p y K J g R v 8 e V l 0 q g 4 3 r n j 3 l + U q z d 5 H A V y T E 7 I G f H I F a m S O 1 I j d c L I I 3 k m r + T N G l k v 1 r v 1 M W 9 d s f K Z I / I H 1 u c P S B 6 R x A = = < / l a t e x i t > t e x i t s h a 1 _ b a s e 6 4 = " z v i r x r S f + k V h g n 0 3 g 9 r d p Q R 3 B 5 8 = " > A A A B 9 H i c b V B N S 8 N A E N 3 4 W e t X 1 a O X Y B E 8 h a S K e i x 6 8 V j B f k A b y m Y 7 a Z d u N n F 3 U i y h v 8 O L B 0 W 8 + m O 8 + W / c t j l o 6 4 O B x 3 s z z M w L E s E 1 u u 6 3 t b K 6 t r 6 x W d g q b u / s 7 u 2 X D g 4 b O k 4 V g z q L R a x a A d U g u I Q 6 c h T Q S h T Q K B D Q D I a 3 U 7 8 5 A q V 5 L B 9 w n I A f 0 b 7 k I W c U j e R 3 E J 4 Q M a s 4 l 9 6 k W y q 7 j j u D v U y 8 n J R J j l q 3 9 N X p x S y N Q C I T V O u 2 5 y b o Z 1 Q h Z w I m x U 6 q I a F s S P v Q N l T S C L S f z Y 6 e 2 K d G 6 d l h r E x J t G f q 7 4 m M R l q P o 8 B 0 R h Q H e t G b i v 9 5 7 R T D a z / j M k k R J J s v C l N h Y 2 x P E 7 B 7 X A F D M T a E M s X N r T Y b U E U Z m p y K J g R v 8 e V l 0 q g 4 3 r n j 3 l + U q z d 5 H A V y T E 7 I G f H I F a m S O 1 I j d c L I I 3 k m r + T N G l k v 1 r v 1 M W 9 d s f K Z I / I H 1 u c P S y 6 R x g = = < / l a t e x i t > 1.19 < l a t e x i t s h a 1 _ b a s e 6 4 = " c t K V V F 6 n Z m i q g N T / 9 s T a v Q L E X G s = " > A A A B 9 H i c b V D L S g N B E J y N r x h f U Y 9 e B o P g a d l V Q b 0 F v X i M Y B 6 Q L G F 2 0 p s M m X 0 4 0 x s M S 7 7 D i w d F v P o x 3 v w b J 8 k e N L G g o a j q p r v L T 6 T Q 6 D j f V m F l d W 1 9 o 7 h Z 2 t r e 2 d 0 r 7 x 8 0 d J w q D n U e y 1 i 1f K Z B i g j q K F B C K 1 H A Q l 9 C 0 x / e T v 3 m C J Q W c f S A 4 w S 8 k P U j E Q j O 0 E h e B + E J E T P X d q 8 n 3 X L F s Z 0 Z 6 D J x c 1 I h O W r d 8 l e n F / M 0 h A i 5 Z F q 3 X S d B L 2 M K B Z c w K X V S D Q n j Q 9 a H t q E R C 0 F7 2 e z o C T 0 x S o 8 G s T I V I Z 2 p v y c y F m o 9 D n 3 T G T I c 6 E V v K v 7 n t V M M r r x M R E m K E P H 5 o i C V F G M 6 T Y D 2 h A K O c m w I 4 0 q Y W y k f M M U 4 m p x K J g R 3 8 e V l 0 j i z 3 X P b u b + o V G / y O I r k i B y T U + K S S 1 I l d 6 R G 6 o S T R / J M X s m b N b J e r H f r Y 9 5 a s P K Z Q / I H 1 u c P T j C R y A = = < / l a t e x i t > 2.22 < l a t e x i t s h a 1 _ b a s e 6 4 = " b / R a w k X k c 2 c x C m i + l k B q g / Y J l 1 0 = " > A A A B 9 H i c b V D L S g N B E J y N r x h f U Y 9 e B o P g a d m N g h 6 D X j x G M A 9 I l j A 7 6 U 2 G z D 6 c 6 Q 2 G J d / h x Y M i X v 0 Y b / 6 N k 2 Q P m l j Q U F R 1 0 9 3 l J 1 J o d J x v q 7 C 2 v r G 5 V d w u 7 e z u 7 R + U D 4 + a O k 4 V h w a P Z a z a P t M g R Q Q N F C i h n S h g o S + h 5 Y 9 u Z 3 5 r D E q L O H r A S Q J e y A a R C A R n a C S v i / C E i F n V r l a n v X L F s Z 0 5 6 C p x c 1 I h O e q 9 8 l e 3 H / M 0 h A i 5 Z F p 3 X C d B L 2 M K B Z c w L X V T D Q n j I z a A j q E R C 0 F 7 2 f z o K T 0 z S p 8 G s T I V I Z 2 r v y c y F m o 9 C X 3 T G T I c 6 m V v J v 7 n d V I M r r 1 M R E m K E P H F o i C V F G M 6 S 4 D 2 h Q K O c m I I 4 0 q Y W y k f M s U 4 m p x K J g R 3 + e V V 0 q z a 7 o X t 3 F 9 W a j d 5 H E V y Q k 7 J O X H J F a m R O 1 I n D c L J I 3 k m r + T N G l s v 1 r v 1 s W g t W P n M M f k D 6 / M H R p u R w w = = < / l a t e x i t > I(⌦, At|St) < l a t e x i t s h a _ b a s e = " u J t t Q m X G e m z d e J H l B Z y g f = " > A A A B / H i c b V D L S g N B E J y N r x h f q z l G Q x C B A m K u g x s W c j G g e k C z L G S S D J l M N M r L G v F S e F P H q h j z b w k e D E g o a i q p v u L i S X I F l f R u p e W V b X e m F j c t x z d a o w l p Q a C h C f a I Y o I H r A E c B G t H k h H f E z l j a m f u u B S c X D B S i D k + G Q S z y k B L b l m s V b u v h s Q I x p Q u P + M F I c s W R V r C r x I I y U U I a a e y G N f R Y A F U S p j m F

Figure 3: Decision state heatmaps plotting I(Ω, Zt|St, S0) at visited states on simple environments -4-Room (top) and maze (bottom). First column depicts environment layout, second and third show results for DS-VIC for β = 1e -3 and β = 1 respectively, and the fourth column shows DIAYN. Please refer to Appendix A.4 for details about how I(Ω, Zt|St, S0) is computed. * denotes lower bound (Eq. 1) on empowerment.

Figure 4: We visualize identified decision states for 3 options by DS-VIC on the Mountain Car environment. (a) shows the environment layout, (b) the trajectories corresponding to the 3 options in position-velocity space -if trajectories corresponding to two different options reach the same position and velocity, then they are said to intersect, (c) the final-state distributions in the position-velocity space, and (d) the identified decision states. In (b), (c), (d), x-axis (position) shows the x-coordinate of the car, while y-axis shows the velocity of the car.Mountain Car Environment: We also use DS-VIC to identify decision states in the Mountain Car(Brockman et al., 2016) environment -a continuous state-space (position and velocity of the car) environment with three discrete actions {+1(right), 0, -1(left)}, which correspond to the direction of the force being applied to the car (see Fig.4(a)). Fig.4(b)shows the trajectories and Fig.4(c)shows the final state(s) corresponding to 3 specific options (out of 8) overlaid on a position-velocity plane. Upon observing decision states in the same position-velocity plane (see Fig.4(d), point-radius proportional to I(Ω, Z t |s t , s 0 ), we find that decision states occur at points in the state-space where trajectories associated with different options intersect. Intuitively, these are the states where the agent can switch from one option (mode of behavior) to another and therefore, needs to make a decision. Interestingly, there is a dominance of decision states along the velocity = 0 line, which indicates that the model identifies decision states to be points where the cart has velocity = 0 at some position (specific to the option). Finally, decision states often occur, for say, the orange option (Ω 1 ) in the right half of the position-velocity plane and never in the bottom-left quadrant, where it is the only option covering that part of the state-space, and thus default behavior can be practiced.

Figure 5: Effect of β during DS-VIC pre-training on success with exploration bonus for the goalconditioned policy. Shaded areas represent standard error of the mean over 10 random seeds.

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 larger rooms (25x25) making efficient exploration critical to find doors quickly. For DS-VIC and DIAYN, we train for 6 million episodes in the decision state identification phase (pre-training) and pick the checkpoints with highest empowerment values across training.

Transfer results on MultiRoomN6S25 after unsupervised pre-training to identify decision states on MultiRoomN2S6. Shaded regions represent standard errors of the mean over 10 random seeds.

Farthest Room Reached (running best) Figure 7: (a) Success Rate, (b) Avg. Task Returns, (c) farthest room reached so far, versus time-steps on MultiRoomN3S4. Unsupervised pre-training to identify decision states was done on MultiRoomN2S6. Shaded areas represent standard error of the mean over 3 random seeds.

Room Reached (running best) Figure 8: (a) Success Rate, (b) Avg. Task Returns, (c) farthest room reached so far, versus time-steps on MultiRoomN5S4. Unsupervised pre-training to identify decision states was done on MultiRoomN2S6. Shaded areas represent standard error of the mean over 3 random seeds.

This is because the sequence of observations {o 1 , • • • , o t } might be informative of the option Ω being followed i.e. conditioning p(a t | •) on S t in addition to z could 'leak' information about the underlying option to the actions, making it the bottleneck penalty on z potentially ineffective. Finally, when maximizing the likelihood of option Ω given the final state S f in learning q(ω | s f ) in VIC (the option inference network), we use the global (x, y) coordinates of the final and initial state of the agent. Note that the agent's policy continues to be based only on observations o t , and it is only at the end of the trajectory that we use the global coordinates to compute intrinsic reward. Please refer to Sec. A.6 for a discussion of the issues when training the model with partial observations in the option inference network.

Table content: <table><tr><td>Related Objectives. Eysenbach et al. (2018) (DIAYN) attempts to learn skills (similar to options)</td></tr><tr><td>which can control the states visited by agents while ensuring that states, not actions, are used</td></tr><tr><td>to distinguish skills. Thus, for an option Ω and every state S t in a trajectory, they maximize</td></tr></table>

I(A t , Ω|S t , S 0 ) ≤ I(Z t , Ω|S t , S 0 ) for the graphical model in Fig 2.So we will next derive an upper bound on I(Z t , Ω|S t , S 0 ). write I(Ω, Z t |S t , S 0 = s), given a start state S 0 = s as:

Table content: <table><tr><td>We E Ω∼p(ω),St∼p J (st|Ω,S0=s),Zt∼p(zt|St,Ω) log</td><td>p(Z t |Ω, S t ) p(Z t |S t )</td></tr></table>

Encoder p φ (Z t |S t , Ω) pretrained on)

Table content: <table><tr><td>Method</td><td colspan="3">MultiRoomN3S4 MultiRoomN5S4 MultiRoomN6S25</td></tr><tr><td colspan="4">(MultiRoomN2S6 MultiRoomN2S6 MultiRoomN2S10</td></tr><tr><td>Goal-conditioned A2C</td><td>0%</td><td>0%</td><td>0%</td></tr><tr><td>TRPO + VIME</td><td>54%</td><td>0%</td><td>N/A</td></tr><tr><td>Curiosity-based Exploration</td><td>95%</td><td>54%</td><td>N/A</td></tr><tr><td>Count-based Exploration Goyal et al. (2019)</td><td>95%</td><td>0%</td><td>N/A</td></tr><tr><td>InfoBot Goyal et al. (2019)</td><td>90%</td><td>85%</td><td>N/A</td></tr><tr><td>InfoBot (Our Implementation)</td><td>99.6%±0.2%</td><td>98.9%±0.8%</td><td>86.8%±2.3%</td></tr><tr><td>Count-based Exploration (Our Implementation)</td><td>99.8%±0.2%</td><td>71.4%±28.1%</td><td>88.4%±2.3%</td></tr><tr><td>DIAYN-based Exploration Bonus (β = 1)</td><td>99.7%±0.2%</td><td>99.7%±0.2%</td><td>0.1%±0.1%</td></tr><tr><td>Randomly Initialized Encoder</td><td>100%±0%</td><td>98.8%±0.7%</td><td>67.9%±7.7%</td></tr><tr><td>Heuristic Decision States</td><td>N/A</td><td>N/A</td><td>81.3%±3.0%</td></tr><tr><td>DS-VIC (β = 10 -3 )</td><td>99.9%±0.1%</td><td>99.1%±0.3%</td><td>90.9%±0.6%</td></tr><tr><td>DS-VIC (β = 10 -2 )</td><td>100%±0%</td><td>71.1%±28.1%</td><td>92.6%±0.6%</td></tr></table>

Peer review (iclr2020):
This paper proposes a mechanism for identifying decision states, even on previously unseen tasks. Decision states are states from which the option taken has high mutual information with the final state of that option, but low mutual information with the action at a time-step, given the current state. An intrinsic reward based on an upper bound of the relevant mutual information speeds up learning in similar environments that the agent has not encountered. A key contribution of this work is extending the notion of goal-driven decision states to goal-independent decision states. The authors also introduce an interesting upper bound on the mutual information between options and final states. The authors provide an empirical evaluation that supports their central claims. I recommend this paper be accepted because it contributes an interesting theoretical result, a definition of decision state that does not depend on extrinsic rewards, and an algorithm to find such decision states. Further suggestions to improve clarity that did not influence the decision: * The acronym VIC is used frequently throughout the introduction, but is not explained until section 2. Please introduce variational intrinsic control in the introduction. * The partial observability claim is not substantiated by the experiments. From the general response to reviewers, *Therefore, we make the assumption that the complete state is available, in order to study unsupervised decision states.* It is not a problem to assume that the complete state is available, but claiming to generalize to partial observability is not entirely correct, even if your method handles the same semi-partially observable case as previous work like VIC or DIAYN. * Please explicitly describe the motivation for using a bottleneck variable. * In MDPs with fixed episode length, the probability of termination is only non-zero on the last time step. Therefore, information about the time step must be included in a Markov state. The options in this paper terminate based on a time horizon, but there is no mention of whether the intra-option time step is included in the state or bottleneck variables.