Year: 2020

Abstract:
In this paper, we study the problem of autonomously discovering temporally abstracted actions, or options, for exploration in reinforcement learning. For learning diverse options suitable for exploration, we introduce the infomax termination objective defined as the mutual information between options and their corresponding state transitions. We derive a scalable optimization scheme for maximizing this objective via the termination condition of options, yielding the InfoMax Option Critic (IMOC) algorithm. Through illustrative experiments, we empirically show that IMOC learns diverse options and utilizes them for exploration. Moreover, we show that IMOC scales well to continuous control tasks.

heading: 1 INTRODUCTION
text: Abstracting a course of action as a higher-level action, or an option (Sutton et al., 1999), is a key ability for reinforcement learning (RL) agents in several aspects, including exploration. In RL problems, an agent learns to approximate an optimal policy only from experience, given no prior knowledge. This leads to the necessity of exploration: an agent needs to explore the poorly known states for collecting environmental information, sometimes sacrificing immediate rewards. For statistical efficiency, it is important to explore the state space in a deep and directed manner, rather than taking uniformly random actions (Osband et al., 2019). Options can represent such directed behaviors by capturing long state jumps from their starting regions to terminating regions. It has been shown that well-defined options can facilitate exploration by exploiting an environmental structure (Barto et al., 2013) or, more generally, by reducing decision steps (Fruit and Lazaric, 2017).
A key requirement for such explorative options is diversity. If all options have the same terminating region, they will never encourage exploration. Instead, options should lead to a variety of regions for encouraging exploration. However, automatically discovering diverse options in a scalable, online manner is challenging due to two difficulties: generalization and data limitation. Generalization with function approximation (Sutton, 1995) is important for scaling up RL methods to large or continuous domains. However, many existing option discovery methods for exploration are graph-based (e.g., Machado et al. (2017)) and incompatible with function approximation, except for that by Jinnai et al. (2020). Discovering options online in parallel with polices requires us to work with limited data sampled from the environment and train the model for evaluating the diversity in a data-efficient manner.
To address these difficulties, we introduce the infomax termination objective defined as the mutual information (MI) between options and their corresponding state transitions. This formulation reflects a simple inductive bias: for encouraging exploration, options should terminate in a variety of regions per starting regions. Thanks to the information-theoretical formulation, this objective is compatible with function approximation and scales up to continuous domains. A key technical contribution of this paper is the optimization scheme for maximizing this objective. Specifically, we employ a simple classification model over options as a critic for termination conditions, which makes our method data-efficient and tractable in many domains.
The paper is organized as follows. After introducing background and notations, we present the infomax termination objective and derive a practical optimization scheme using the termination gradient theorem (Harutyunyan et al., 2019). We then implement the infomax objective on the option-critic architecture (OC) (Bacon et al., 2017) with algorithmic modifications, yielding the InfoMax Option Critic (IMOC) algorithm. Empirically, we show that (i) IMOC improves exploration in structured environments, (ii) IMOC improves exporation in lifelong learning, (iii) IMOC is scalable
to MuJoCo continuous control tasks, and (iv) the options learned by IMOC are diverse and meaningful. We then relate our method to other option-learning methods and the empowerment concept (Klyubin et al., 2005), and finally give concluding remarks.

heading: 2 BACKGROUND AND NOTATION
text: We assume the standard RL setting in the Markov decision process (MDP), following Sutton and Barto (2018). An MDPM consists of a tuple (X ,A, p, r, γ), where X is the set of states, A is the set of actions, p : X ×A×X → [0, 1] is the state transition function, r : X ×A → [rmin, rmax] is the reward function, and 0 ≤ γ ≤ 1 is the discount factor. A policy is a probability distribution over actions conditioned on a state x, π : X ×A → [0, 1]. For simplicity, we consider the episodic setting where each episode ends when a terminal state xT is reached. In this setting, the goal of an RL agent is to approximate a policy that maximizes the expected discounted cumulative reward per episode:
JRL(π) = Eπ,x0 [ T−1∑ t=0 γtRt ] , (1)
where Rt = r(xt, at) is the reward received at time t, and x0 is the initial state of the episode. Relatedly, we define the action-value function Qπ(xt, at) def = Ext,at,π [∑T−1 t′=t γ t′−tRt′ ] and the
state-value function V π(xt) def = Ext,π ∑ a π(a|xt)Qπ(xt, a).
Assuming that π is differentiable by the policy parameters θπ , a simple way to maximize the objective (1) is the policy gradient method (Williams, 1992) that estimates the gradient by:
∇θπJRL(π) = Eπ,xt [ ∇θπ log π(at|xt)Â(xt, at) ] , (2)
where Â(xt, at) is the estimation of the advantage function Aπ(xt, at) def = Qπ(xt, at)− V π(xt). A common choice of Â(xt, at) is N -step TD error ∑N i=0 γ iRt+i + γ N V̂ (xt+N )− V̂ (xt), where N is a fixed rollout length (Mnih et al., 2016).

heading: 2.1 OPTIONS FRAMEWORK
text: Options (Sutton et al., 1999) provide a framework for representating temporally abstracted actions in RL. An option o ∈ O consists of a tuple (Io, βo, πo), where Io ⊆ X is the initiation set, βo : X → [0, 1] is a termination function with βo(x) denoting the probability that option o terminates in state x, and πo is intra-option policy. Following related studies (Bacon et al., 2017; Harutyunyan et al., 2019), we assume that Io = X and learn only βo and πo. Letting xs denote an option-starting state and xf denote an option-terminating state, we can write the option transition function as:
P o(xf |xs) = βo(xf )Ixf=xs + (1− βo(xs)) ∑ x pπ o (x|xs)P o(xf |x), (3)
where I is the indicator function and pπo is the policy-induced transition function pπo(x′|x) def=∑ a∈A π
o(a|x)p(x′|x, a). We assume that all options eventually terminate so that P o is a valid probability distribution over xf , following Harutyunyan et al. (2019).
To present option-learning methods, we define two option-value functions: QO and UO, where QO is the option-value function denoting the value of selecting an option o at a state xt defined by QO(xt, o) def = Eπ,β,µ [∑T−1 t′=t γ t′−tRt ] . Analogously to Qπ and V π, we let VO denote the
marginalized option-value function VO(x) def = ∑ o µ(o|x)QO(x, o), where µ(o|xs) : X ×O → [0, 1] is the policy over options. Function UO(x, o) def = (1− βo(x))QO(x, o) + βo(x)VO(x) is called the option-value function upon arrival (Sutton et al., 1999) and denotes the value of reaching a state xt with o and not having selected the new option.

heading: 2.2 OPTION CRITIC ARCHITECTURE
text: OC (Bacon et al., 2017) provides an end-to-end algorithm for learning πo and βo in parallel. To optimize πo, OC uses the intra-option policy gradient method that is the option-conditional version
of the gradient estimator (2), ∇θπoJRL(πo) = E [ ∇θπo log πo(at|xt)Âo(xt, at) ] , where Âo is an estimation of the option-conditional advantage Aπ o .
For optimizing βo, OC directly maximizes QO using the estimated gradient: ∇θβoQO(x, o) = γE [ −∇θβoβ o(x) ( QO(x, o)− VO(x) )] . (4)
Intuitively, this decreases the termination probability βo(x) when holding an o is advantageous, i.e., QO(x) − VO(x) is positive, and vice versa. Our method basically follows OC but has a different objective for learning βo.

heading: 2.3 TERMINATION CRITIC
text: Recently proposed termination critic (TC) (Harutyunyan et al., 2019) optimizes βo by maximizing the information-theoretic objective called predictability:
JTC(P o) = −H(Xf |o), (5)
where H denotes entropy and Xf is the random variable denoting the option-terminating states. Maximizing −H(Xf |o) makes the terminating region of an option smaller and more predictable. In other words, we can compress terminating regions by optimizing the objective (5). To derivate this objective by the beta parameters θβo , Harutyunyan et al. (2019) introduced the termination gradient theorem: Theorem 1. Let βo be parameterized with a sigmoid function and `βo denote the logit of βo. We have
∇θβP o(xf |xs) = ∑ x P o(x|xs)∇θβ `βo(x)(Ixf=x − P o(xf |x)), (6)
Leveraging the theorem 1, TC performs gradient ascent using the estimated gradient:
∇θβoJ TC(P o) = −Exs,x,xf [ ∇θβ `βo(x)βo(x) (( logP oµ(x)− logP oµ(xf ) ) + ( 1−
P o(xf |xs)P oµ(x) P oµ(xf )P o(x|xs)
))] .
where P oµ(x) is the marginalized distribution of option-terminating states.
Contrary to the termination objective of OC (4), this objective does not depend on state values, making learned options robust against the reward structure of the environment. Our method is inspired by TC and optimizes a similar information-theoretic objective, not for predictability but for diversity. Also, our infomax objective requires an estimation of p̂(o|xs, xf ) instead of the option transition model P o(xf |xs), which makes our method tractable in more environments.

heading: 3 INFOMAX OPTION CRITIC
text: We now present the key idea behind the InfoMax Option Critic (IMOC) algorithm. We first formulate the infomax termination objective based on the MI maximization, then derive a practical gradient estimation for maximizing this objective on βo, utilizing the termination gradient theorem 1.
To evaluate the diversity of options, we use the MI between options and option-terminating states conditioned by option-starting states:
J IMOC = I(Xf ;O|Xs) = H(Xf |Xs)−H(Xf |Xs, O), (7)
where I denotes conditional MI I(A;B|Z) = H(A|Z) −H(A|B,Z), Xs is the random variable denoting an option-starting state, and O is the random variable denoting an option. We call this objective the infomax termination objective. Let us interpret Xf |Xs as the random variable denoting a state transition induced by an option. Then maximizing the MI (7) (i) diversifies a state transition Xf |Xs and (ii) makes an option-conditional state transition Xf |Xs, o more deterministic. Note that the marginalized MI I(Xf ;O) also makes sense in that it prevents the terminating region of each option from being too broad, as predictability (5) does. However, in this study, we focus on the conditional objective since it is easier to optimize.
To illustrate the limitation of infomax options, we conducted an analysis in a toy four-state deterministic chain environment, which has four states and two deterministic actions (go left and go right) per each state. Since deriving the exact solution is computationally difficult, we searched options that maximize H(Xf |Xs) from deterministic options that has deterministic option-policies and termination functions (thus has the minimum H(Xf |Xs, O)). Among multiple solutions, Figure 1 shows two interesting instances of deterministic infomax options when |O| = 2. The left options enable diverse behaviors per state, although they fail to capture long-term behaviors generally favorable in the literature (e.g., Mann et al. (2015)). On the other hand, the right options enable relatively long, two step state transitions, but they are the same and the rightmost state and the next one. Furthermore, an agent can be caught in a small loop that consists of the leftmost state and the next one. This example shows that (i) we can obtain short and diverse options with only a few options, (ii) to obtain long and diverse options, we need sufficiently many options, and (iii) an agent can be caught in a small loop with only a few options, failing to visit diverse states. As we show in Appendix A, this ’small loop’ problem cannot happen with four options. Thus, the number of options is important when we are to maximize the MI (7) and a limitation of this method. However, in experiments, we show that we can practically learn diverse options with relatively small number of options.
For maximizing the MI by gradient ascent, we now derive the gradient of the infomax termination objective (7). First, we estimate the gradient of the objective using the option transition model P o and marginalized option-transition model P (xf |xs) = ∑ o µ(o|xs)P o(xf |xs).
Proposition 1. Let βo be parameterized with a sigmoid function. Given a trajectory τ = xs, . . . , x, . . . , xf sampled by πo and βo, we can obtain unbiased estimations of∇θβH(Xf |Xs) and ∇θβH(Xf |Xs, O) by
∇θβH(Xf |Xs) = Exs,x,xf ,o [ −∇θβ `βo(x)βo(x) ( logP (x|xs)− logP (xf |xs) )] (8)
∇θβH(Xf |Xs, O) = Exs,x,xf ,o [ −∇θβ `βo(x)βo(x) ( logP o(x|xs)− logP o(xf |xs) )] (9)
where `βo(x) denotes the logit of βo(x).
Note that the additional term βo is necessary because x is not actually a terminating state. The proof follows section 4 in Harutyunyan et al. (2019) and is given in Appendix B.1.
The estimated gradient of the infomax termination objective (7) can now be written as:
∇θβI(Xf ;O|Xs) = ∇θβH(Xf |Xs)−∇θβH(Xf |Xs, O) = Exs,x,xf ,o [ −∇θβ `βo(x)βo(x) (logP (x|xs)− logP (xf |xs)− (logP o(x|xs)− logP o(xf |xs))) ] ,
(10)
which means that we can optimize this objective by estimating P o and P . However, estimating the probability over the state space can be difficult, especially when the state space is large, as common in the deep RL setting. Hence, we reformulate the gradient using Bayes’ rule in a similar way as Gregor et al. (2017). The resulting term consists of the reverse option transition p(o|xs, xf ) that denotes the probability of having an o given a state transition xs, xf .
Proposition 2. We now have
∇θβI(Xf ;O|Xs) =∇θβH(Xf |Xs)−∇θβH(Xf |Xs, O) =Exs,x,xf ,o [ ∇θβ `βo(x)βo(x) ( log p(o|xs, x)− log p(o|xs, xf ) )] (11)
The proof is given in Appendix B.2. In the following sections, we estimate the gradient (11) by learning a classification model over options p̂(o|xs, xf ) from sampled option transitions.

heading: 4 ALGORITHM
text: In this section, we introduce modifications for adjusting the OC (Bacon et al., 2017) to our infomax termination objective. Specifically, we implement IMOC on top of Advantage-Option Critic (AOC), a synchronous variant of A2OC (Harb et al., 2018), yielding the Advantage-Actor InfoMax Option Critic (A2IMOC) algorithm. To stably estimates p̂(o|xs, xf ) for updating θβ , we sample recent option state transitions o, xs, xf from We follow AOC for optimizing option-policies except the following modifications and give a full description of A2IMOC in Appendix C.1. In continuous control experiments, we also used Proximal Policy InfoMax Option Critic (PPIMOC) that is an implementation of IMOC based on PPO (Schulman et al., 2017). We give details of PPIMOC in Appendix C.2.
Upgoing Option-Advantage Estimation Previous studies (e.g., Harb et al. (2018)) estimated the advantage Âot(xt) ignoring the future rewards after the current option ot terminates. Since longer rollout length often helps speed up learning (Sutton and Barto, 2018), it is preferable to extend this estimation to use all available future rewards. However, future rewards after option termination heavily depends on the selected option, often leading to underestimation of Âo. Thus, to effectively use future rewards, we introduce an upgoing option-advantage estimation (UOAE). Let t+ k denote the time step where the current option ot terminates in a sampled trajectory. Then, UOAE estimates the advantage by:
ÂoUOAE = −QO(xt, ot) +  ∑k i=0 γ iRt+i +max  N∑ j=k γjRt+j , γ kVO(xt+k)  ︸ ︷︷ ︸ upgoing estimation (k < N)
∑N i=0 γ iRt+i + γ NUO(xt+N , ot) (otherwise)
.
(12)
Similar to upgoing policy update (Vinyals et al., 2019), the idea is to be optimistic about the future rewards after option termination by taking the maximum with VO.
Policy Regularization Based on Mutual Information To perform MI maximization not only on termination functions but also on option-policies, we introduce a policy regularization based on the maximization of the conditional MI, I(A;O|Xs), where A is the random variable denoting an action. This MI can be interpreted as a local approximation of the infomax objective (7), assuming that each action leads to different terminating regions. Although optimizing the infomax termination objective diversifies option-policies implicitly, we found that this regularization helps learn diverse option-policies reliably. Letting πµ denote the marginalized policy πµ(a|x) def = ∑ o µ(o|x)πo(a|x), we write I(A;O|Xs) as:
I(A;O|Xs) = H(A|Xs)−H(A|O,Xs) = Exs [H(πµ(xs))]− Exs,o [H(πo(xs))] .
We use this regularization with the entropy bonus (maximization of H(πo)) common in policy gradient methods (Williams and Peng, 1991; Mnih et al., 2016) and write the overall regularization term as
cHµH(πµ(x)) + cHH(π o(x)), (13)
where cHµ and cH are weights of each regularization term. Note that we add this regularization term on not only option-starting states but all sampled states. This introduces some bias, which we did
not find to be harmful when cHµ is reasonably small. To approximate H(πµ), we employ µ̂ that is the empirical estimation of µ. Using µ̂, H(πµ) is computed by πµ(a|x) ≈ ∑ o µ̂(o|x)πo(a|x) for descrete action spaces and approximated by Monte Carlo method for continuous action spaces. We show the details in Appendix C.1.

heading: 5 EXPERIMENTS
text: We conducted a series of experiments to show two use cases of IMOC: exploration in structured environments and exploration for lifelong learning (Brunskill and Li, 2014). In this section, we used four options for all option-learning methods and compared the number of options in Appendix D.7.

heading: 5.1 SINGLE TASK LEARNING IN STRUCTURED ENVIRONMENTS
text: We consider two ’Four Rooms’ domains, where diverse options are beneficial for utilizing environmental structures.
Gridworld Four Rooms with Suboptimal Goals First, we tested IMOC in a variant of the classical Four Rooms Gridworld (Sutton et al., 1999) with suboptimal goals. An agent is initially placed at the upper left room and receives a positive reward only at goal states: two closer goals with +1 reward and the farthest goal with +2 reward, as shown in Figure 2a. The episode ends when an agent reaches one of the goals. The optimal policy is aiming the farthest goal in the lower right room without converging to suboptimal goals. Thus, an agent is required to learn multimodal behaviors leading to multiple goals, which options can help. In this environment, we compared A2IMOC with A2C (Mnih et al., 2016; Wu et al., 2017), AOC, and our tuned version of AOC (our AOC) with all enhancements presented in section 4 to highlight the effectiveness of the termination objective among all of our improvements.1 We show the progress of average cumulative rewards over ten trials in Figure 2b. A2IMOC performed the best and found the optimal goal in most trials. AOC and our AOC also occasionally found the optimal goal, while A2C overfitted to either of the suboptimal goals through all trials.
Figure 3 illustrates learned option-polices and termination functions of each compared method.2 Terminating regions learned with A2IMOC is diverse. For example, option 0 mainly terminates in the right rooms while option 3 terminates in the left rooms. We see that termination regions learned by A2IMOC are diverse and clearly separated per each option. Although all option policies converged to the same near optimal one, we show that A2IMOC diversifies option-policies at the beginning of learning in Appendix D.4. On the other hand, terminating regions learned with AOC overlap each other, and notably, option 3 has no terminating region. We assume this is because the loss function (4) decreases the terminating probability when the advantage is positive. We can see the same tendency in our AOC, although we cannot see the vanishment of the terminating regions.
1Note that we did not include ACTC (Harutyunyan et al., 2019) for comparison since we failed to reliably reproduce the reported results with our implementation of ACTC.
2Note that we choose the best model from multiple trials for visualization throughout the paper.
(a) MuJoCo Point Four Rooms. The agent is an orange ball and there are three goals: green goals are suboptimal (+0.5) and the red one in optimal (+1.0).
0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 Total Environment Steps 1e6
0.0
0.2
0.4
0.6
0.8
1.0
Cu m
ul at
iv e
Re wa
rd s
Method PPIMOC PPOC OurPPOC PPO
(b) Performance progression.
analysis, we observed the same tendency in learned options as the Gridworld experiment, where the details are given in Appendix D.5.

heading: 5.2 SINGLE TASK LEARNING IN CLASSICAL CONTINUOUS CONTROL
text: Additionally, we test PPIMOC on two classical, hard-exploration control problems: Mountain Car (Barto et al., 1983) and Cartpole swingup (Moore, 1990). In Mountain Car, PPIMOC and our PPOC successfully learns to reache the goal, while PPO and PPOC converged to run around the start posisition. In Cartpole swing up, PPIMOC and our PPOC performed better than PPO and PPOC, but still failed to learn stable behaviors.

heading: 5.3 EXPLORATION FOR LIFELONG LEARNING
text: As another interesting application of IMOC, we consider the lifelong learning setting. Specifically, we tested IMOC in ’Point Billiard’ environment. In this environment, an agent receives a positive reward only when the blue objective ball reaches the goal, pushed by the agent (orange ball). Figure 6a shows all four configurations of Point Billiard that we used. There are four goals: green goals with +0.5 reward and a red one with +1.0 reward. The positions of four goals move clockwise after 1M environmental steps and agents need to adapt to the new positions of goals. We compared PPIMOC with PPO, PPOC, and our PPOC in this environment. Figure 6b shows the progress of average cumulative rewards over five trials. Both PPIMOC and our PPOC performed the best and adapted to all reward transitions. On the other hand, PPO and PPOC struggle to adapt to the second transition, where the optimal goal moves behind the agent. The ablation study given in Appendix D.6 shows that UOAE (12) works effectively in this task. However, without UOAE, PPIMOC still outperformed PPO. Thus, we argue that having diverse terminating regions itself is beneficial for adapting to new reward functions in environments with subgoals.

heading: 6 RELATED WORK
text: Options for Exploration Options (Sutton et al., 1999) in RL are widely studied for many applications, including speeding up planning (Mann and Mannor, 2014) and transferring skills (Konidaris and Barto, 2007; Castro and Precup, 2010). However, as discussed by Barto et al. (2013), their benefits for exploration are less well recognized. Many existing methods focused on discovering subgoals that effectively decompose the problem then use such subgoals for encouraging exploration. Subgoals are discovered based on various properties, including graphical features of state transitions (Simsek and Barto, 2008; Machado et al., 2017; Jinnai et al., 2019) and causality (Jonsson and Barto, 2006; Vigorito and Barto, 2010). In contrast, our method directly optimizes termination functions instead of discovering subgoals, capturing environmental structures implicitly. From a theoretical perspective, Fruit and Lazaric (2017) analyzed that good options can improve the exploration combined with state-action visitation bonuses. Using infomax options with visitation bonuses would be an interesting future direction.
End-to-end learning of Options While many studies attempted to learn options and option-policies separately, Bacon et al. (2017) proposed OC to train option-policies and termination functions in parallel. OC has been extended with various types of inductive biases, including deliberation cost (Harb et al., 2018), interest (Khetarpal et al., 2020), and safety (Jain et al., 2018). Our study is directly inspired by an information-theoretic approach presented by Harutyunyan et al. (2019), as we noted in section 2.
Mutual Information and Skill Learning MI often appears in the literature of intrinsically motivated (Singh et al., 2004) reinforcement learning, as a driver of goal-directed behaviors. A well-known example is the empowerment (Klyubin et al., 2005; Salge et al., 2013), which is obtained by maximizing the MI between sequential k actions and the resulting state I(at, ..., at+k;xt+k|xt). Some works (Mohamed and Rezende, 2015; Zhao et al., 2020) implemented lower bound maximization of empowerment as intrinsic rewards for RL agents, encouraging goal-directed behaviors in the absence of extrinsic rewards We can interpret our objective I(Xf ;O|Xs) as empowerment between limited action sequences and states corresponding to options. Gregor et al. (2017) employed this interpretation and introduced a method for maximizing the variational lower bound of this MI via option-policies, using the same model as our p̂, while we aim to maximize the MI via termination functions. MI is also used for intrinsically motivated discovery of skills, assuming that diversity is important to acquire useful skills. Eysenbach et al. (2019) proposed to maximize MI between skills and states I(O;X), extended to the conditional one I(O;X ′|X) by Sharma et al. (2020). Although our study shares the same motivation for using MI as these methods, i.e. diversifying sub-policies, the process of MI maximization is significantly different: our method optimizes termination functions, while their methods optimize conditional policies by using MI as intrinsic rewards.

heading: 7 CONCLUSION
text: We presented a novel end-to-end option learning algorithm InfoMax Option Critic (IMOC) that uses the infomax termination objective to diversify options. Empirically, we showed that IMOC improves exploration in structured environments and for lifelong learning, even in continuous control tasks. We also quantitatively showed the diversity of learned options. An interesting future direction would be combining our method for learning termination conditions with other methods for learning option-policies, e.g., by using MI as intrinsic rewards. A limitation of the infomax objective presented in this study is that it requires on-policy data for training. Hence, another interesting line of future work is extending IMOC to use for off-policy option discovery.

heading: A MORE ANALYSIS ON DETERMINISTIC CHAIN EXAMPLE
text: Figure 7 shows infomax options with three options and four options in the four state deterministic chain example. Among multiple solutions, we selected options with an absorbing state per option (i.e., βo(x) = 1.0 for only one x), which are partially the same as the right options in Figure 1. With four options, Pr(xf |xs) = 0.25 for all xf and xs, thus H(Xf |Xs) is the maximum. This example shows that we need sufficiently many options for maximizing the MI, otherwise an agent can be caught in a small loop as we described in Section 3.

heading: B OMITTED PROOFS

heading: B.1 PROOF OF PROPOSITION 1
text: First, we repeat the assumption 2 in Harutyunyan et al. (2019).
Assumption 1. The distribution dµ(·|o) over the starting states of an option o under policy µ is independent of its termination condition βo.
Note that this assumption does not strictly hold since -Greedy option selection depends on βo via QO. However, since this dependency is not so strong, we found that βo reliably converged in our experiments.
Lemma 1. Assume that the distribution dµ(·|o) over the starting state of an option o under policy µ is independent with βo. Then the following equations hold.
∇θβH(Xf |Xs) = − ∑ xs,o dµ(xs, o) ∑ x P o(x|xs)∇θβ `βo(x) [ logP (x|xs) + 1− ∑ xf P o(xf |x) ( logP (xf |xs) + 1 )] (14)
∇θβH(Xf |Xs, O) = − ∑ xs,o dµ(xs, o) ∑ x P o(x|xs)∇θβ `βo(x) [ logP o(x|xs) + 1− ∑ xf P o(xf |x) ( logP o(xf |xs) + 1 )] ,
(15)
Sampling xs, x, xf , o from dµ and P o, ∇θβH(Xf |Xs) = Exs,x,xf ,o [ −∇θβ `βo(x)βo(x) ( logP (x|xs)− logP (xf |xs) )] (16)
∇θβH(Xf |Xs, O) = Exs,x,xf ,o [ −∇θβ `βo(x)βo(x) ( logP o(x|xs)− logP o(xf |xs) )] . (17)

heading: Proof of Lemma 1
text: Proof. First, we prove Equation (14). Let dµ(xs) denote the probability distribution over xs under the policy µ, or the marginal distribution of dµ(xs|o), and dµ(xs, o) denote the joint distribution of xs and o. Then, we have:
∇θβH(Xf |Xs) = −∇θβ ∑ xs dµ(xs) ∑ xf P (xf |xs) logP (xf |xs)
= − ∑ xs dµ(xs) ∑ xf ( ∇θβP (xf |xs) logP (xf |xs) + P (xf |xs) ∇θβP (xf |xs) P (xf |xs) ) = −
∑ xs dµ(xs) ∑ xf ∇θβP (xf |xs) ( logP (xf |xs) + 1 ) = −
∑ xs dµ(xs) ∑ xf ∑ o
µ(o|xs) ∇θβP o(xf |xs)︸ ︷︷ ︸ Apply theorem (6)
( logP (xf |xs) + 1 )
= − ∑ xs dµ(xs) ∑ xf ∑ o µ(o|xs) ∑ x P o(x|xs)∇θβ `βo(x)(Ixf=x − P o(xf |x)) ( logP (xf |xs) + 1 ) = −
∑ xs dµ(xs) ∑ o µ(o|xs) ∑ x P o(x|xs)∇θβ `βo(x) ∑ xf (Ixf=x − P o(xf |x)) ( logP (xf |xs) + 1 ) = −
∑ xs,o
dµ(xs, o)︸ ︷︷ ︸ sample
∑ x
P o(x|xs)︸ ︷︷ ︸ sample
∇θβ `βo(x)× [ logP (x|xs) + 1− ∑ xf
P o(xf |x)︸ ︷︷ ︸ sample
( logP (xf |xs) + 1 )] .
Sampling xs, x, xf , o, we get (16).
Then we prove Equation (15). ∇θβH(Xf |Xs, O) = −∇θβ ∑ xs,o dµ(xs, o) ∑ xf P o(xf |xs) logP o(xf |xs)
= − ∑ xs,o dµ(xs, o) ∑ xf ( ∇θβP o(xf |xs) logP o(xf |xs) + P o(xf |xs) ∇θβP o(xf |xs) P o(xf |xs) ) = −
∑ xs,o dµ(xs, o) ∑ xf
∇θβP o(xf |xs)︸ ︷︷ ︸ Apply theorem (6)
( logP o(xf |xs) + 1 )
= − ∑ xs,o dµ(xs, o) ∑ xf ∑ x P o(x|xs)∇θβ `βo(x)(Ixf=x − P o(xf |x)) ( logP o(xf |xs) + 1 ) = −
∑ xs,o dµ(xs, o) ∑ x P o(x|xs)∇θβ `βo(x) ∑ xf (Ixf=x − P o(xf |x)) ( logP o(xf |xs) + 1 ) = −
∑ xs,o
dµ(xs, o)︸ ︷︷ ︸ sample
∑ x
P o(x|xs)︸ ︷︷ ︸ sample
∇θβ `βo(x)× [ logP o(x|xs) + 1− ∑ xf
P o(xf |x)︸ ︷︷ ︸ sample
( logP o(xf |xs) + 1 )]
Sampling xs, x, xf , o, we get (17).

heading: B.2 PROOF OF PROPOSITION 2
text: Proof. First, we have that:
logP o(xf |xs)− logP (xf |xs) = log P o(xf |xs) P (xf |xs)
= log Pr(xf |xs, o) P (xf |xs)
= log Pr(xs, xf , o) Pr(xs)
Pr(xs, xf ) Pr(xs, o)
= log Pr(xs, xf , o)
Pr(xs, xf ) Pr(o|xs)
= log Pr(o|xs, xf ) Pr(xs, xf ) Pr(xs, xf ) Pr(o|xs)
= log p(o|xs, xf ) µ(o|xs)
Using this equation, we can rewrite the equation (10) as:
∇θβI(Xf ;O|Xs) = ∇θβH(Xf |Xs)−∇θβH(Xf |Xs, O) = Exs,x,xf ,o [ −∇θβ `βo(x)βo(x) ( logP (x|xs)− logP (xf |xs)− logP o(x|xs) + logP o(xf |xs) )] = Exs,x,xf ,o [ ∇θβ `βo(x) (( logP o(x|xs)− logP (x|xs) ) − ( logP o(xf |xs)− logP (xf |xs)
))] = Exs,x,xf ,o [ ∇θβ `βo(x) ( log
p(o|xs, x) µ(o|xs) − log p(o|xs, xf ) µ(o|xs) )] = Exs,x,xf ,o [ ∇θβ `βo(x) ( log p(o|xs, x)− log p(o|xs, xf ) )]
C IMPLEMENTATION DETAILS

heading: C.1 THE WHOLE ALGORITHM OF A2IMOC
text: Algorithm 1 shows a full description of A2IMOC. It follows the architecture of A2C (Mnih et al., 2016; Wu et al., 2017) and has multiple synchronous actors and a single learner. At each optimization step, we update πo, QO, and βo from online trajectories collected by actors. We update p̂(o|xs, xf ) for estimating the gradient (11) and µ̂(o|xs) for entropy regularization (13). To learn p̂ and µ̂ stably, we maintain a replay buffer BO that stores option-transitions, implemented by a LIFO queue. Note that using older o, xs, xf sampled from the buffer can introduce some bias in the learned p̂ and µ̂, since they depend on the current πo and βo. However, we found that this is not harmful when the capacity of the replay buffer is reasonably small.
We also add maximization of the entropy of βo to the loss function for preventing the termination probability saturating on zero or one. Then the full objective of βo is written as:
log p̂(o|xs, x)− log p̂(o|xs, xf ) + cHβH(βo(x)),
where cHβ is a weight of entropy bonus.
C.2 IMPLEMENTATION OF PPIMOC
For continuous control tasks, we introduce PPIMOC on top of PPO, with the following modifications to A2IMOC.
Algorithm 1 Advantage-Actor InfoMax Option Critic (A2IMOC) 1: Given: Initial option-value QO, option-policy πo, and termination function βo. 2: Let BO be a replay buffer for storing option-transitions. 3: for k = 1, ... do 4: for i = 1, 2, ..., N do . Collect experiences from environment 5: Sample termination variable bi from βoi(xi) 6: if bi = 1 then 7: Store option transition xs, xf , oi to BO 8: end if 9: Choose next option oi+1 by -Greedy 10: Receive reward Ri and state xi+1, taking ai ∼ πoi+1(xi) 11: end for 12: for all xi in the trajectory do . Train option-policy, option-values, and termination function 13: Update πo(ai|xi) with PG via the UOAE advantage (12) and policy regularization (13) 14: Update QO(xi, o) via the optimistic TD error (12) 15: if oi has already terminated then 16: Update βo(xi) via (11) and the maximization of cHβH(β
o(xi)) 17: end if 18: end for 19: Train p̂ and µ̂ by option-transitions sampled from BO 20: end for
Upgoing Option-Advantage Estimation for GAE To use an upgoing option-advantage estimation (12) with Generalized Advantage Estimator (GAE) (Schulman et al., 2015b) common with PPO, we introduce an upgoing general option advantage estimation (UGOAE). Letting δ denote the TD error corresponding to the marginalized option-state-values, δt = Rt + γVO(xt+1)− VO(xt), we write the GAE for marginalized policy πµ as Âoµ = ∑N i=0(γλ)
iδt+i, where λ is a coefficient. Supposing that ot terminates at the t+ k step and letting δo denote the TD error corresponding to an option-state value δot = Rt + γQO(xt+1, o)−QO(xt, o), we formulate UGOAE by:
ÂoUGOAE =  ∑k i=0(γλ) iδot+i +max( N∑ i=k+1 (γλ)iδt+i, 0)︸ ︷︷ ︸ upgoing estimation
(k < N)
∑N−1 i=0 (γλ) iδot+i + (γλ) N (Rt+N + γUO(xt+N+1)−QO(xt+N , o)) (otherwise).
(18)
The idea is the same as UOAE (12) and is optimistic about the advantage after option termination.
Clipped βo Loss In our preliminary experiments, we found that performing multiple steps of optimization on the gradient (11) led to destructively large updates and resulted in the saturation of βo to zero or one. Hence, to perform PPO-style multiple updates on βo, we introduce a clipped loss for βo:
∇θβclip(`βo(x)− `βoold(x),− β , β)β o old(x) ( log p(o|xs, x)− log p(o|xs, xf ) ) , (19)
where β is a small coefficient, βoold is a β o before the update, and clip(x,− , ) = max(− ,min( , x)). Clipping makes the gradient zero when βo is sufficiently different than βoold and inhibits too large updates.

heading: D EXPERIMENTAL DETAILS

heading: D.1 NETWORK ARCHITECTURE
text: Figure 8 illustrates the neural network architecture used in our experiments. In Gridworld experiments, we used the same state encoder for all networks and we found that it is effective for diversifying πo as an auxiliary loss (Jaderberg et al., 2017). However, in MuJoCo experiments, we found that sharing
the state encoder can hurt the policy update because the magnitude of βo loss is larger even if clipped loss (19) is used. As a remedy for this, we used two encoders in MuJoCo experiments: one is for πo and QO, and the other is for βo, p̂, and µ̂.
In Gridworld experiments, we represented a state as an image and encoded it by a convolutional layer with 16 filters of size 4× 4 with stride 1, followed by a convolutional layer with 16 filters of size 2× 2 with stride 1, followed by a fully connected layer with 128 units. In MuJoCo experiments, we encode the state by two fully connected layers with 64 units. πo is parameterized as a Gaussian distribution with separated networks for standard derivations per option, similar to Schulman et al. (2015a). We used ReLU as an activator for all hidden layers and initialized networks by the orthogonal (Saxe et al., 2014) initialization in all experiments. Unless otherwise noted, we used the default parameters in PyTorch (Paszke et al., 2019) 1.5.0.

heading: D.2 HYPERPARAMETERS
text: When evaluating agents, we used -Greedy for selecting options with opt and did not use deterministic evaluation (i.e., an agent samples actions from πo) in all experiments. We show the algorithm-specific hyperparameters of A2IMOC in Table 1. In Gridworld experiments, we used = 0.1 for AOC. Our AOC implementation is based on the released code3 and uses truncated N -step advantage. Other parameters of AOC and A2C are the same as A2IMOC. We also show the hyperparameters of PPIMOC in Table 2. For PPOC, we used cµent = 0.001 for the weight of the entropy H(µ(x)). Our PPOC implementation is based on the released code4 and uses N -step (not truncated) GAE for computing advantage. PPOC and PPO shares all other parameters with PPIMOC.
3https://github.com/jeanharb/a2oc_delib 4https://github.com/mklissa/PPOC

heading: D.3 ENVIRONMENTAL DETAILS
text: In the Gridworld experiment, an agent can select four actions: go up, go down, go left and go right. With the probability 0.1, the agent takes a uniformly random action. If the agent reaches one of goals, it receives +1.0 or +2.0 reward. Otherwise, an action penalty −0.002 is given. The maximum episode length is 100.
MuJoCo Point environments are implemented based on “PointMaze” in rllab (Duan et al., 2016) with some modifications, mainly around collision detection. The maximum episode length is 1000. In Four Rooms task, an agent receives +0.5 or +1.0 reward when it reaches a goal. Otherwise, an action penalty −0.0001 is given. This reward structure is the same in Billiard Task: an agent receives a goal reward when the object ball reaches a goal, otherwise it receives penalty.

heading: D.4 EARLY OPTION-POLICIES LEARNED IN GRIDWORLD FOUR ROOMS
text: Figure 9 shows early option-polices and termination probabilities in Gridworld Four Rooms experiment. We can see that A2IMOC learned the most diverse option-policies.

heading: D.5 QUALITATIVE ANALYSIS OF POINT FOUR ROOMS EXPERIMENT
text: Figure 10 shows the visualizations of learned option-polices and termination functions in MuJoCo Point Four Rooms, averaged over 100 uniformly sampled states per each position. Arrows show the expected moving directions, computed from rotations and option-policies. Terminating regions and option-policies learned with PPIMOC are diverse. For example, option 1 tends to go down while option 2 tends to go right. In the sampled trajectory of PPIMOC, we can see that it mainly used option 1 but occasionally switched to option 0 and option 2 for reaching the goal, and switched to option 3 around the goal. Contrary, for reaching the goal PPOC only used option 3 that does not terminate in any region. Options learned by Our PPOC is almost the same: termination probability is high around the upper left corner and option-policies direct downward.

heading: D.6 ABLATION STUDIES
text: We conducted ablation studies with three variants of A2IMOC/PPIMOC:
• cHµ = 0: Do not use the policy regularization based on MI (13). • N -step Advantange: Use N -step advantage or N -step GAE instead of UOAE (12)
UGOAE (18). • Truncated N -step Advantange: Compute advantage ignoring future rewards instead of using
UOAE or UGOAE.
Figure 11 shows all results in three tasks. We can see that UOAE is effective in all tasks, since both N -step advantage and truncated N -step advantage performed worse than UOAE. The policy regularization based on MI (13) is effective only in the Point Billiard lifelong learning task.

heading: D.7 NUMBER OF OPTIONS
text: Figure 12 shows the performance of IMOC with varying the number of options. Two options perfomed worse in all experiments and we need four or more options to make use of IMOC. However, when we increase the number of options to six and eight, we don’t see any peroformance improvement from four options, despite of our analysis that we need sufficiently many options to cover the state space Appendix A. This would be an interesting problem for future works.

Review summaries:
The authors propose a modification of the option-critic algorithm for hierarchical reinforcement learning. The proposed algorithm modifies how the termination conditions of the options are improved by experience. Specifically, the algorithm aims to maximize the mutual information between the options and their termination states. The authors develop an optimization scheme for achieving this objective and provide empirical results in a number of domains