--- title: "IR-VIC: Unsupervised Discovery of Sub-goals for Transfer in RL" authors: - "Nirbhay Modhe" - "Prithvijit Chattopadhyay" - "Mohit Sharma" - "Abhishek Das" - "Devi Parikh" - "Dhruv Batra" - "Ramakrishna Vedantam" doi: "10.24963/ijcai.2020/280" url: "https://ijcai.org/proceedings/2020/280" pdf: "https://ijcai.org/proceedings/2020/0280.pdf" venue: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence" year: 2020 pages: "2022-2028" track: "Main track" keywords: - "Machine Learning: Reinforcement Learning" - "Machine Learning: Deep Reinforcement Learning" - "Machine Learning: Unsupervised Learning" --- # IR-VIC: Unsupervised Discovery of Sub-goals for Transfer in RL Nirbhay Modhe, Prithvijit Chattopadhyay, Mohit Sharma, Abhishek Das, Devi Parikh, Dhruv Batra, Ramakrishna Vedantam *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence*, pages 2022-2028. DOI: [10.24963/ijcai.2020/280](https://doi.org/10.24963/ijcai.2020/280) ## Abstract We propose a novel framework to identify sub-goals useful for exploration in sequential decision making tasks under partial observability. We utilize the variational intrinsic control framework (Gregor et.al., 2016) which maximizes empowerment -- the ability to reliably reach a diverse set of states and show how to identify sub-goals as states with high necessary option information through an information theoretic regularizer. Despite being discovered without explicit goal supervision, our sub-goals provide better exploration and sample complexity on challenging grid-world navigation tasks compared to supervised counterparts in prior work. ## Full text ## 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]. 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: IR-VIC identifies sub-goals as states where necessary option information is high (darker shades of red) for an empowered agent. Identification of unsupervised sub-goals leads to improved transfer to novel environments. ![Image](https://ijcai.org/proceedings/2020/fulltext/280/image_000000_7534331d81f769aed932b381170e1d344241102de402ed995ffb2e55735bd0be.png) ![Image](https://ijcai.org/proceedings/2020/fulltext/280/image_000001_96aa0af1c65688274ef52faf0a625c263ca8eea6865f93e05e8169e1f6ac3d30.png) 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 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: IR-VIC considers a particular parameterization of π and imposes a bottleneck on I(At, Ω|St). ![Image](https://ijcai.org/proceedings/2020/fulltext/280/image_000002_7de88091064a4574f93656c744158b23b6cbd6ae1281dc0a31a0a7d1e6cf8e1a.png) ## 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 ![Image](https://ijcai.org/proceedings/2020/fulltext/280/image_000003_f2d7003e93fc2cf4558dbcf6ad50e6028dedf0075c0c674af9dbbd497d8e8317.png) 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](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]. Figure 4: Transfer results on a test set of MultiRoomN6S25 environment layouts after unsupervised pre-training on MultiRoomN2S10. Shaded regions represent standard error of the mean of average return over 10 random seeds. ![Image](https://ijcai.org/proceedings/2020/fulltext/280/image_000004_93b16c3400d6b6b14307c705a75af8c9a336378a09ad434640164df55a556e2d.png) ## 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. Figure 5: Evaluation of average return on a held-out validation set of MultiRoomN6S25 environment layouts. For each value of β, pretraning is performed over 3 random seeds with the best seed being picked to measure transfer performance over 3 subsequent random seeds. Shaded regions represent standard error of the mean over the 3 random seeds used for transfer. ![Image](https://ijcai.org/proceedings/2020/fulltext/280/image_000005_ffb1468c4ba532ef80918d3169b300b88835f3846fafcfdfdc340f164fe51117.png) 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. ## References 1. [Achiam et al., 2018] Joshua Achiam, Harrison Edwards, Dario Amodei, and Pieter Abbeel. Variational option discovery algorithms. arXiv preprint arXiv:1807.10299, 2018. 2. [Alemi et al., 2016] Alexander A Alemi, Ian Fischer, Joshua V Dillon, and Kevin Murphy. Deep variational information bottleneck. In ICLR, 2016. 3. [Chalk et al., 2016] Matthew Chalk, Olivier Marre, and Gasper Tkacik. Relevant sparse codes with variational in- formation bottleneck. 2016. 4. [Chechik et al., 2005] Gal Chechik, Amir Globerson, Naf- tali Tishby, and Yair Weiss. Information bottleneck for gaussian variables. J. of Machine Learning Research, 6(Jan):165-188, 2005. 5. [Chevalier-Boisvert et al., 2018] Maxime Chevalier- Boisvert, Lucas Willems, and Suman Pal. Min- imalistic gridworld environment for openai gym. https://github.com/maximecb/gym-minigrid, 2018. 6. [Cover and Thomas, 1991] Thomas M Cover and Joy A Thomas. Elements of information theory. Wiley Series in Telecommunications, 1991. 7. [Eysenbach et al., 2018] Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. CoRR, abs/1802.06070, 2018. 8. [Goyal et al., 2019] Anirudh Goyal, Riashat Islam, Daniel Strouse, Zafarali Ahmed, Matthew Botvinick, Hugo Larochelle, Yoshua Bengio, and Sergey Levine. InfoBot: Transfer and exploration via the information bottleneck. arXiv [stat.ML], January 2019. 9. [Gregor et al., 2016] Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv preprint arXiv:1611.07507, 2016. 10. [Hayes-Roth and Hayes-Roth, 1979] Barbara Hayes-Roth and Frederick Hayes-Roth. A cognitive model of planning. Cognitive science, 3(4):275-310, 1979. 11. [Higgins et al., 2017] Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-VAE: Learning basic visual concepts with a constrained varia- tional framework. In ICLR, 2017. 12. [Lillicrap et al., 2015] Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous con- trol with deep reinforcement learning. arXiv preprint arXiv:1509.02971, 2015. 13. [Lopes et al., 2012] Manuel Lopes, Tobias Lang, Marc Tou- ssaint, and Pierre-Yves Oudeyer. Exploration in model- based reinforcement learning by empirically estimating learning progress. In NIPS, 2012. 14. [Machado et al., 2017] Marios Machado, Marc Bellemare, and Michael Bowling. A laplacian framework for option discovery in reinforcement learning. In ICML, 2017. 15. [McGovern and Barto, 2001] Amy McGovern and An- drew G. Barto. Automatic discovery of subgoals in reinforcement learning using diverse density. In ICML, 2001. 16. [Pathak et al., 2017] Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 16-17, 2017. 17. [Polani et al., 2006] Daniel Polani, Chrystopher L Nehaniv, Thomas Martinetz, and Jan T Kim. Relevant information in optimized persistence vs. progeny strategies. In In: Ar- tificial Life X: Proc. of the Tenth International Conference on the Simulation and Synthesis of Living Systems. Mit Press, 2006. 18. [Salge et al., 2013] Christoph Salge, Cornelius Glackin, and Daniel Polani. Empowerment -an introduction. October 2013. 19. [Schmidhuber, 1990] Jürgen Schmidhuber. A possibility for implementing curiosity and boredom in model-building neural controllers. In Proc. of the First International Con- ference on Simulation of Adaptive Behavior on From An- imals to Animats, pages 222-227, Cambridge, MA, USA, 1990. MIT Press. 20. [Still et al., 2004] Susanne Still, William Bialek, and Léon Bottou. Geometric clustering using the information bot- tleneck method. In S Thrun, L K Saul, and B Schölkopf, editors, NIPS. 2004. 21. [Strouse and Schwab, 2017] D J Strouse and David J Schwab. The information bottleneck and geometric clus- tering. December 2017. 22. [Strouse et al., 2018] D J Strouse, Max Kleiman-Weiner, Josh Tenenbaum, Matt Botvinick, and David Schwab. Learning to share and hide intentions using information regularization. August 2018. 23. [Teh et al., 2017] Yee Teh, Victor Bapst, Wojciech M Czar- necki, John Quan, James Kirkpatrick, Raia Hadsell, Nico- las Heess, and Razvan Pascanu. Distral: Robust multitask reinforcement learning. In NIPS, 2017. 24. [Tishby et al., 1999] Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method. In The 37th annual Allerton Conf. on Communication, Con- trol, and Computing, pages 368-377, 1999. 25. [van Dijk and Polani, 2011] Sander G van Dijk and Daniel Polani. Grounding subgoals in information transitions. In IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, pages 105-111, 2011. 26. [Zaslavsky et al., 2018] Noga Zaslavsky, Charles Kemp, Terry Regier, and Naftali Tishby. Efficient compression in color naming and its evolution. Proc. Natl. Acad. Sci. 27. U. S. A., 115(31):7937-7942, July 2018. 28. [Ziebart et al., 2008] Brian D Ziebart, Andrew L Maas, J Andrew Bagnell, and Anind K Dey. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pages 1433-1438. Chicago, IL, USA, 2008.