Year: 2019

Abstract:
Reinforcement learning (RL) has become an increasingly active area of research in recent years. Although there are many algorithms that allow an agent to solve tasks efficiently, they often ignore the possibility that prior experience related to the task at hand might be available. For many practical applications, it might be unfeasible for an agent to learn how to solve a task from scratch, given that it is generally a computationally expensive process; however, prior experience could be leveraged to make these problems tractable in practice. In this paper, we propose a framework for exploiting existing experience by learning reusable options. We show that after an agent learns policies for solving a small number of problems, we are able to use the trajectories generated from those policies to learn reusable options that allow an agent to quickly learn how to solve novel and related problems.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) techniques have experienced much of their success in simulated environments, such as video games (Mnih et al., 2015) or board games (Silver et al., 2016; Tesauro, 1995). One of the main reasons why RL has worked so well in these applications is that we are able simulate millions of interactions with the environment in a relatively short period of time. In many real world applications, however, where the agent interacts with the physical world, it might not be easy to generate such a large number of interactions. The time and cost associated with training such systems could render RL an unfeasible approach for training in large scale.
As a concrete example, consider training a large number of humanoid robots (agents) to move quickly, as in the Robocup competition (Farchy et al., 2013). Although the agents have similar dynamics, subtle variations mean that a single policy shared across all agents would not be an effective solution. Furthermore, learning a policy from scratch for each agent is too data-inefficient to be practical. As shown by Farchy et al. (2013), this type of problem can be addressed by leveraging the experience obtained from solving a related task (e.g., walking) to quickly learn a policy for each individual agent that is tailored to a new task (e.g., running). These situations also occurs in industry, such as robots tasked with sorting items in fulfillment centers. A simple approach, like using PD controllers, would fail to adapt to the forces generated from picking up objects with different weight distributions, causing the arm to drop the objects. RL is able to mitigate this problem by learning a policy for each arm that is able to make corrections quickly, which is tailored to the robot’s dynamics. However, training a new policy for each agent would be far too costly to be a practical solution. In these scenarios, it is possible to use a small number of policies learned a subset of the agents, and then leverage the experience obtained from learning those policies to allow the remaining agents to quickly learn their corresponding policies. This approach can turn problems that are prohibitively expensive to solve into relatively simple problems.
To make use of prior experience and improve learning on new related problems in RL, several lines of work, which are complementary to each other, have been proposed and are actively being studied. Transfer learning (Taylor & Stone, 2009) refers to the problem of adapting information acquired while solving one task to another. One might consider learning a mapping function that allows for a policy learned in one task to be used in a different task (Ammar et al., 2015) or simply learn a mapping of the value function learned in one task to another (Taylor et al., 2007). These techniques can be quite effective, but are also limited in that they consider mapping information from one source task to another target task. Another approach to reusing prior knowledge is through meta learning
or learning to learn (Schmidhuber, 1995; Schmidhuber et al., 1998). In the context of RL, the goal under this framework for an agent to be exposed to a number of tasks where it can learn some general behavior that generalizes to new tasks (Finn et al., 2017).
One last technique to leverage prior experience, and the one this paper focuses on, is through temporally extended actions or temporal abstractions (McGovern & Sutton, 1998; Sutton et al., 1999). While in the standard RL framework the agent has access to a set of primitive actions (i.e., actions that last for one time step), temporally extended actions allow an agent to execute actions that last for several time-steps. They introduce a bias in the behavior of the agent which, if appropriate for the problem at hand, results in dramatic improvements in how quickly the agent learns to solve a new task. A popular representation for temporally extended actions is the options framework (Sutton & Precup, 1998; Sutton et al., 1999) (formally introduced in the next section), which is the focus of this work. It has been shown that options learned in a specific task or set of tasks, can be reused to improve learning on new tasks (Machado et al., 2017; Bacon et al., 2017); however, this often requires knowledge from the user about which options or how many options are appropriate for the type of problems the agent will face.
In this paper, we propose learning reusable options for a set of related tasks with minimal information provided by the user. Throughout this paper, we refer as (near)-optimal policies to those policies that were learned to solve a particular task, but are not strictly speaking optimal. We consider the scenario where the agent must solve a large numbers of tasks and show that after learning a (near)-optimal policy for a small number of problems, we can learn an appropriate number of options that facilitates learning in a remaining set of tasks. To do so, we propose learning a set of options that minimize the expected number of decisions needed to represent trajectories generated from the (near)-optimal policies learned by the agent, while also maximizing the probability of generating those trajectories. Unlike techniques that learn options to rach bottleneck states (McGovern & Barto, 2001) or states deemed of high value (Machado et al., 2017), our method seeks to learn options that are able to generate trajectories known to perform well. This does not necessarily lead to learn options that reach states one might consider “interesting”.

heading: 2 BACKGROUND AND NOTATION
text: A Markov decision process (MDP) is a tuple,M = (S,A, P,R, γ, d0), where S is the set of possible states of the environment, A is the set of possible actions that the agent can take, P (s, a, s′) is the probability that the environment will transition to state s′ ∈ S if the agent executes action a ∈ A in state s ∈ S , R(s, a, s′) is the expected reward received after taking action a in state s and transitioning to state s′, d0 is the initial state distribution, and γ ∈ [0, 1] is a discount factor for rewards received in the future. We use t to index the time-step and write St,At, andRt to denote the state, action, and reward at time t. A policy, π : S × A → [0, 1], provides a conditional distribution over actions given each possible state: π(s, a) = Pr(At = a|St = s). We denote a trajectory of length t as ht = (s0, a0, r0, . . . , st−1, at−1, rt−1, st), that is, ht is defined as a sequence of states, actions and rewards observed after following some policy for t time-steps. This work focuses on learning options that can be used for a set of related tasks. We consider the setting where an agent must solve a set of related tasks, where each task is an MDP, M = (S,A, PM , RM , γ, dM0 ); that is, each task is an MDP with its own transition function, reward function and initial state distribution, with shared state and action sets.
An option, o = (Io, µo, βo), is a tuple in which Io ⊆ S is the set of states in which option o can be executed (the initiation set), µo is a policy that governs the behavior of the agent while executing o, and βo : S → [0, 1] is a termination function that determines the probability that o terminates in a given state. We assume that Io = S for all options o; that is, the options are available at every state. The options framework does not dictate how an agent should choose between available options or how options should be discovered. A common approach to selecting between options is to a learn a policy over options, which is defined by the probability of choosing an option in a particular state. Two recent popular approaches to option discovery are eigenoptions (Machado et al., 2017) and the option-critic architecture (Bacon et al., 2017).
The eigenoptions (Machado et al., 2017) of an MDP are the optimal policies for a set of implicitly defined reward functions called eigenpurposes. Eigenpurposes are defined in terms of proto-value functions (Mahadevan, 2005), which are in turn derived from the eigenvectors of a modified adjacency matrix over states for the MDP. The intuition is that no matter the true reward function, the
eigenoptions allow an agent to quickly traverse the transition graph, resulting in better exploration of the state space and faster learning. However, there are two major downsides: 1) the adjacency matrix is often not known a priori, and may be difficult to construct for large MDPs, and 2) for each eigenpurpose, constructing the corresponding eigenoption requires solving a new MDP. The option-critic architecture (Bacon et al., 2017) is a more direct approach to learn options and a policy over options simultaneously using policy gradient methods. One issue that often arises within this framework is that the termination functions of the learned options tend to collapse to “always terminate”. In a later publication, the authors built on this work to consider the case where there is a cost associated with switching options (Harb et al., 2018). This method resulted in the agent learning to use a single option while it was appropriate and terminate when an option switch was needed, allowing it to discover improved policies for a particular task. The authors argue that minimizing the use of the policy over options may be desirable, as the cost of choosing an option may be greater than the cost of choosing a primitive action when using an option. Recent work by Harutyunyan et al. (2019) approaches the aforementioned termination problem by explicitly optimizing the termination function of options to focus on small regions of the state space. However, in contrast to the work presented in these paper, these methods do not explicitly take into consideration that the agent might face many related tasks in the future.
We build on the idea that minimizing the number of decisions made by an agent leads to the discovery of general reusable options, and propose an offline method where they are learned by solving a small number of tasks. The options are then leveraged to quickly solve new problems the agent will face in the future. We use the trajectories generated while learning (near)-optimal policies, and learn an appropriate set of options by directly minimizing the expected number of decisions the agent makes while simultaneously maximizing the probability of generating the observed trajectories.

heading: 3 LEARNING REUSABLE OPTIONS FROM EXPERIENCE
text: In this section, we introduce the objective for learning a set of reusable options for a set of related tasks. Our algorithm introduces one option at a time until introducing a new option does not improve the objective further. This procedure results in a natural way of learning an adequate number of options without having to predefine it; a new option is included if it is able to improve the probability of generating optimal behavior while minimizing the number of decisions made by the agent. Our method assumes that the agent has learn a policy for a small number of tasks, and sample trajectories are obtained from these (near)-optimal policies. Notice that the propose algorithm is only concerned with being able to recreate the demonstrated trajectories, so if these were sample from a poorly performing policy the options learned are unlikely to provide any benefits.

heading: 3.1 PROBLEM FORMULATION
text: In the options framework, at each time-step, t, the agent chooses an action, At, based on the current option, Ot. Let Tt be a Bernoulli random variable, where Tt = 1 if the previous option, Ot−1, terminated at time t, and Tt = 0 otherwise. If Tt = 1, Ot is chosen using the policy over options, π. If Tt = 0, then the previous option continues, that is, Ot = Ot−1. To ensure we can represent any trajectory, we consider primitive actions to be options which always select one specific action and then terminate; that is, for an option, o, corresponding to a primitive, a, for all s ∈ S, the termination function would be given by βo(s) = 1, and the policy by µ(s, a′) = 1 if a′ = a and 0 otherwise.
Let O = OA ∪ OO denote a set of options, {o1, . . . , on}, where OA refers to the set of options corresponding to primitive actions and OO to the set corresponding to temporal abstractions. Furthermore, letH be a random variable denoting a trajectory of length |H| generated by a near-optimal policy, and let Ht be a random variable denoting the sub-trajectory of H up to the state encountered at time-step t. We seek to find a set, O∗ = {o∗1, . . . , o∗n}, that maximizes the following objective:
J(π,O) = E [ |H|∑ t=1 Pr(Tt = 0, Ht|π,O) + λ1g(H,OO) ] , (1)
where g(h,OO) is a regularizer that encourages a diverse set of options, and λ1 is a scalar hyperparameter. If we are also free to learn the parameters of π, then O∗ ∈ arg max
O max π
J(π,O).
One choice for g is the average KL divergence on a given trajectory over the set of m options
being learned: g(h,OO) = 2m(m−1) ∑ o,o′∈OO ∑|h|−1 t=0 DKL ( µo(st)||µo′(st)). 1 Intuitively, we seek to find options that are capable of generating near-optimal trajectories with a small number of terminations. Notice that minimizing the number of terminations is the same as minimizing the number of decisions made by the policy over options, as each termination requires the policy to choose a new option. Given a set of options, a policy over options, and a near-optimal sample trajectory, we can calculate the joint probability for a trajectory exactly, and estimate equation 1 by averaging over a set of near-optimal trajectories.

heading: 3.2 OPTIMIZATION OBJECTIVE FOR LEARNING OPTIONS
text: Given that the agent must solve a set of tasks, we can use the experienced gathered on a subset of tasks to obtain trajectories demonstrating optimal behavior. Given a set,H, of trajectories generated from an initial subset of tasks, we can now estimate the expectation in equation 1 to learn options that can be leveraged in the remaining problems. Because the probability of generating any trajectory approaches 0 as the length of the trajectory increases, we make modify the original objective for better numerical stability, and arrive to the objective Ĵ that we optimize in practice.
Ĵ(π,O,H) = 1H ∑ h∈H ( λ2 Pr(H = h|π,O)︸ ︷︷ ︸
probability of generating h
− ∑|h|
t=1 E [Tt = 1|Ht = ht, π,O] |h|︸ ︷︷ ︸
expected number of terminations
+ λ1g(h,OO) )︸ ︷︷ ︸
encourage diverse options
.
(2)
A more detailed discussion on how we arrived to this objective is provided in Appendix A. We can express equation 2 entirely in terms of the policy over options π, options O = {o1, . . . , on} and the transition function, P (which we estimate from samples). The following theorems show how to calculate the first two terms in equation 2, allowing us to maximize the proposed objective. Theorem 1. Given a set of options, O, and a policy, π, over options, the expected number of terminations for a trajectory h is given by:
|h|∑ t=1 E [ Tt = 1 ∣∣∣∣Ht = ht, π,O] = |h|∑ t=1 ∑ o∈O βo(st) µo(st−1, at−1) Pr(Ot−1 = o|Ht−1 = ht−1, π,O)∑ o′∈O µo(st−1, at−1) Pr(Ot−1 = o ′|Ht−1 = ht−1, π,O) ,
(3)
Pr(Ot = o|Ht = ht, π,O) = [( π(st, o)βo(st) ) + ( P (st−1, at−1, st)αt−1(o)(1− βo(st−1)) )] ,
and Pr(O0 = o|H0 = h0, π,O) = π(s0, o).
Proof. See Appendix B.
Theorem 2. Given a set of options O and a policy π over options, the probability of generating a trajectory h of length |h| is given by:
Pr(H|h| = h|h||π,O) =d0(s0) [∑ o∈O π(s0, o)µo(s0, a0)f(h|h|, o, 1) ] |h|−1∏ k=0 P (sk, ak, sk+1),
where f is a recursive function defined as:
f(ht, o, i) =  1, if i = t[( βo(si) ∑ o′∈O π(si+1, o ′)µo′(si+1, ai+1)f(ht, o ′, i+ 1) ) + ( (1− βo(si))µo(si+1, ai+1)f(ht, o, i+ 1) )] otherwise
Proof. See Appendix C.
1This term is only defined when we consider more than one option. Otherwise, we set this term to 0.
Algorithm 1 Option Learning Framework - Pseudocode
1: Collect set of trajectoriesH 2: Initialize option set O with primitive options 3: done = false 4: Ĵprev = −∞ 5: while done == false do 6: Initialize new option o′ = (µ′φ, β ′ ψ), ini-
tializing parameters for φ and ψ. 7: O′ = O ∪ o′ 8: Initialize parameters θ of policy πθ 9: for k=1,. . . ,N do
10: Ĵk = Ĵ(πθ,O′,H) 11: θ = θ + α∂Ĵk∂θ 12: φ = φ+ α∂Ĵk∂φ 13: ψ = ψ + α∂Ĵk∂ψ 14: if ĴN − Ĵprev < ∆ then 15: done = true 16: else 17: O = O′ 18: Ĵprev = ĴN 19: Return new option set O
Given a parametric representation of the option policies and termination functions for each o ∈ O and for the policy π over options, we use Theorems 1 and 2 to differentiate the objective in equation 2 with respect to their parameters and optimize with any numerical optimization technique.

heading: 3.3 LEARNING OPTIONS INCREMENTALLY
text: One common issue in option discovery is identifying how many options are needed for a given problem. Oftentimes this number is predefined by the user based on intuition. In such a scenario, one could learn options by simply randomly initializing the parameters of a number of options and optimizing the proposed objective in equation 2. Instead, we propose not only learning options, but also the number of options needed, by the procedure shown in Algorithm 1. This algorithm introduces one option at a time and optimizes the objective Ĵ with respect to the policy over options πθ, with parameters θ, and the newly introduced option, o′ = (µ′φ, β ′ ψ), with parameters φ and ψ, for N epochs. Optimizing both o′ and πθ allows us to estimate how much we can improve Ĵ given that we keep any previously introduced option fixed. After the new option is trained, we measure how much Ĵ has improved; if it fails to improve above some threshold, ∆, the procedure terminates. This results in a natural way of obtaining an appropriate number of options, as options stop being added once a new option no longer improves the ability to represent the demonstrated behavior.

heading: 4 EXPERIMENTAL RESULTS
text: This section describes experiments used to evaluate the proposed technique approach. We show results in the “four rooms” domain to allow us to visualize and understand the options produced by our method, and to show empirically that these options produce a clear improvement in learning. We use this domain to show that options generated by our method are able to generalize to tasks where the option-critic architecture (Bacon et al., 2017) and eigenoptions (Machado et al., 2017) would fail to do so. We then extend our experiments to evaluate our technique in a few selected problems from the Atari 2600 emulator provided by OpenAI Gym (Brockman et al., 2016). These experiments demonstrate that by using the trajectories obtained from solving a small subset of tasks, our approach is able to discover options that significantly improve the learning ability of the agent in the tasks it has yet to solve. For the four room experiment, we assume the transition function was known in advance. In all ATARI experiments, we estimated the transition functions by fitting the parameters of a linear Gaussian model to all the transitions experienced during training.

heading: 4.1 EXPERIMENTS ON FOUR ROOMS ENVIRONMENT
text: We tested our approach in the four rooms domain: a gridworld of size 40 × 40, in which the agent is placed in a start state and needs to reach a goal state. At each time-step, the agent executes one of four available actions: moving left, right, up or down, and receives a reward of −1. Upon reaching the goal state, the agent receives a reward of +10. We generated 30 different task variations by changing the goal and start locations, and collected six sample trajectories from optimal policies learned in six tasks. We evaluated our method on the remaining 24 tasks.
Figure 1a shows the change in the average expected number of terminations and average probability of generating the observed trajectories while learning options, as new options are introduced and adapted to the sampled trajectories. Options were learned over the six sampled optimal trajectories and every 50 epochs a new option was introduced. For every new option, the change in probability of
generating the observed trajectories as well as the change in expected number of decisions reaches a plateau after 30 or 40 training epochs. When a new option is introduced, there is a large jump in the loss because a new policy, π, is initialized arbitrarily to account for the new option set being evaluated. However, after training the new candidate option, the overall loss improves beyond what it was possible before introducing the new option.
In Figure 1b, we compare the performance of Q-learning on 24 novel test tasks using options discovered by our method (with and without regularization using KL divergence), eigenoptions, and option critic. We allowed each competing method to learn options from the same six training tasks and, to ensure a fair comparison, we used the original code provided by the authors. As baselines, we also compare against primitive actions and randomly initialized options. It might seem surprising that both eigenoptions and the option-critic failed to reach an optimal policy when they were shown to work well in this type of problem; for that we offer the following explanation. Our implementation of four rooms is defined in a much larger state space than the ones where these methods were originally tested, making each individual room much larger. Since the options identified by these methods tend to lead the agent from room to room, it is possible that, once in the correct room, the agent executes an option leading to a different room before it had the opportunity to find the goal. When testing our approach in the smaller version of the four room problem, we found no clear difference in performance of the competing methods. In this experiment, we set the threshold ∆ for introducing a new option to 10% of Ĵ at the previous iteration and the hyperparameter λ2 = 100.0. When adding KL regularization, we set λ1 = 0.001.
Figure 2 shows a visualization of the policy learned by the agent for a specific task. The policy leads the agent to navigate from a specific location in the bottom-left room to a location in the top-right room in a small “four-room” domain of size 10×15. 2 The new task to solve is shown in the top-left figure, while the solution found is shown in the top-right figure. The remaining rows of images depict the learned option policies, termination functions, and how they were used in the new task. The first row shows the learned option policies after training, the center row depict the termination functions and the bottom row shows a heat-map depicting where each option is likely to be called. The figure shows that while the options are defined over the entire state space, they are only useful in specific regions—that is, they are specialized. These options, when used in combination in specific regions, allow the agent to learn how to solve new problems more efficiently.

heading: 4.2 EXPERIMENTS USING ATARI 2600 GAMES
text: We evaluated the quality of the options learned by our framework in two different Atari 2600 games: Breakout and Amidar. We trained the policy over options using A3C (Mnih et al., 2016) with grayscale pixel input. Options were represented by a two layer convolutional neural network, and
2We show a smaller domain than used in the experiments for ease of visualization
were given the previous two frames as input. In both experiments the task variations consisted in changing the number of frames skipped after taking an action (randomly selected between 2 and 10), the reward function by scaling the reward with a real number between 0.1 and 10.0, and initial state distribution by letting the agent execute between 0 and 20 actions before start it starts learning. The full implementation details for these experiments are given in Appendix E. Figures 3a and 3b show the performance of the agent as a function of training time in Breakout and Amidar, respectively. The plots show that given good choices of hyperparameters, the learned options led to a clear improvement in performance during training. For both domains, we found that λ2 = 5, 000 led to a reasonable trade-off between the first two term in Ĵ , and report results with three different regularization values: λ1 = 0.0,, λ1 = 0.01 and λ1 = 0.1.
Note that our results do not necessarily show that the options result in a better final policy, but they improve exploration early in training and enable the agent to learn more effectively. Figure 4a depicts the behavior for one of the learned options on Breakout. The option efficiently catches the ball after it bounces off the left wall, and then terminates with high probability before the ball has to be caught again. Bear in mind that the option remains active for many time-steps, significantly reducing the number of decisions made by the policy over options. However, it does not maintain control for so long that the agent is unable to respond to changing circumstances. Note that the option is only useful in specific case; for example, it was not helpful in returning a ball bounced off the right wall. That is to say, the option specialized in a specific sub-task within the larger problem:
a highly desirable property for generally useful options. Figure 4b shows the selection of two of the options learned for Amidar when starting a new game. At the beginning of the game, option 1 is selected, which takes the agent to a specific intersection before terminating. The agent then selects option 2, which chooses a direction at the intersection, follows the resulting path, and terminates at the next intersection. Note that the agent does not need to repeatedly select primitive actions in order to simply follow a previously chosen path. Having access to these types of options enables an agent to easily replicate known good behaviors, allowing for faster and more meaningful exploration of the state space.
(a) Visualization of a learned option executed until termination on Breakout. The option learned to catch the ball bouncing off the left wall and terminates with high probability before the ball bounces a wall again (ball size increased for visualization).
(b) Visualization of two learned options on Amidar. The agent is shown in yellow and enemies in pink. Option 1 learned to move up, at the beginning of the game, and turn left until reaching an intersection. Option 2 learned to turn in that intersection and move up until reaching the next one.

heading: 5 CONCLUSION AND FUTURE WORK
text: In this work we presented an optimization objective for learning options offline from demonstrations of near-optimal behavior on a set of tasks. Optimizing the objective results in a set of options that allows an agent to reproduce the behavior while minimizing the number of decisions made by the policy over options, which are able to improve the learning ability of the agent on new tasks. We provided results showing how options adapt to the trajectories provided and showed, through several experiments, that the identified options are capable of significantly improving the learning ability of an agent. The resulting options encode meaningful abstractions that help the agent interact with and learn from its environment more efficiently.

heading: A APPENDIX
text: The following list defines the notation used in all derivations:
1. At: random variable denoting action taken at step t. 2. St: random variable denoting state at step t. 3. Ht: random variable denoting history up to step t. Ht = (S0, A0, S1, A1, . . . , St). 4. Tt: random variable denoting the event that the option used at step t− 1 terminates at state St.
5. π: policy over options. 6. P : transition function. P (s, a, s′) denotes the probability of transitioning to state s′ by
taking action a in state s 7. Ot: random variable denoting the option selected for execution at state St. 8. o: option defined as o = (µo, βo), where µo is the option policy for option and βo is the
termination function. 9. Assume primitives are options that perform only 1 action and last for 1 time-step.
10. O: set of available options.
We can compute the probability of an option terminating at state st and generating a trajectory ht as:
Pr(Tt = 1, Ht = ht|π,O) = Pr(Tt = 1|Ht = ht, π,O) Pr(Ht = ht|π,O) (4)
To compute the proposed objective J we need to find an expression for Pr(Tt = 1|Ht = ht, π,O) and Pr(Ht = ht|π,O) in terms of known quantities.
A.1 APPENDIX A - DERIVATION OF Ĵ Recall J(π,O, H) = E [∑|h| t=1 Pr(Tt = 0, Ht|π,O) ] , ignoring the regularization term. Assuming access to a set H of sample trajectories, we start by estimating J from sample averages and derive the objective Ĵ as follows:
J(π,O,H) ≈ 1 |H| ∑ h∈H |h|∑ t=1 Pr(Tt = 0, Ht = ht|π,O)
= 1 |H| ∑ h∈H |h|∑ t=1 ( 1− Pr(Tt = 1|Ht = ht, π,O) ) Pr(Ht = ht|π,O)
= 1 |H| ∑ h∈H |h|∑ t=1 ( 1−E [ Tt|Ht = ht, π,O ]) Pr(Ht = ht|π,O)
It can easily be seen that to maximize the above expression E [ Tt|Ht = ht, π,O ] should be minimized while Pr(H = h|π,O) should be maximized. Given that for long trajectories the expected number of terminations increases while the probability of generating the trajectories goes to 0, we normalize the number of terminations by the lenght of the trajectory, |h|, and adjust a hyperparameter, λ2, to prevent one term from dominating the other during optimization. Based on this observation we propose optimizing the following objective:
Ĵ(π,O,H) = 1 H ∑ h|h|∈H λ2 Pr(H = h|π,O)− ∑|h| t=1 E [Tt|Ht = ht, π,O] |h| .
This objective allow us to control a trade-off, through λ2, of how much we care about the options reproducing the demonstrated trajectories vs. how much we want the agent to minimize the number of decisions.
A.2 APPENDIX B - PROOF OF THEOREM 1
Theorem 1 Given a set of options O and a policy π over options, the expected number of terminations for a trajectory h of length |h| is given by:
|h|∑ t=1 E [Tt = 1|Ht = ht, π,O] = |h|∑ t=1 (∑ o∈O βo(st) µo(st−1, at−1) Pr(Ot−1 = o|Ht−1 = ht−1, π,O)∑ o′∈O µo′(st−1, at−1) Pr(Ot−1 = o ′|Ht−1 = ht−1, π,O) ) ,
where, Pr(Ot−1 = o|Ht−1 = ht−1, π,O) = [( π(st−1, o)βo(st−1) )( P (st−2, at−2, st−1)µo(st−2, at−2)
×Pr(Ot−2 = o|Ht−2 = ht−2, π,O)(1− βo(st−1)) )] ,
and Pr(O0 = o|H0 = h0, π,O) = π(s0, o).
Proof. Notice that ∑|h| t=1 E [Tt = 1|Ht = ht, π,O] = ∑|h| t=1 Pr(Tt = 1|Ht = ht, π,O) 1, so if we find an expression for Pr(Tt = 1|Ht = ht, π,O), we can calculate the expectation exactly. We define Pr(T0 = 1|H1 = h1, π,O) = 1 for ease of derivation even though there is no option to terminate at T0.
Pr(Tt = 1|Ht = ht, π,O) = ∑ o∈O Pr(Tt = 1|Ot−1 = o,Ht = ht, π,O) Pr(Ot−1 = o|Ht = ht, π,O)
= ∑ o∈O βo(st) Pr(Ot−1 = o|Ht = ht, π,O)
= ∑ o∈O βo(st) Pr(Ot−1 = o|Ht−1 = ht−1, At−1 = at−1, St = st, π,O)
= ∑ o∈O βo(st) Pr(St = st|Ht−1 = ht−1, At−1 = at−1, Ot−1 = o, π,O) Pr(St = st|Ht−1 = ht−1, At−1 = at−1, π,O)
× Pr(Ot−1 = o|Ht−1 = ht−1, At−1 = at−1, π,O) = ∑ o∈O βo(st) Pr(St = st|Ht−1 = ht−1, At−1 = at−1, π,O) Pr(St = st|Ht−1 = ht−1, At−1 = at−1, π,O)
× Pr(Ot−1 = o|Ht−1 = ht−1, At−1 = at−1, π,O) = ∑ o∈O βo(st) Pr(Ot−1 = o|Ht−1 = ht−1, At−1 = at−1, π,O)
= ∑ o∈O βo(st) Pr(At−1 = at−1|Ht−1 = ht−1, Ot−1 = o, π,O) Pr(Ot−1 = o|Ht−1 = ht−1, π,O) Pr(At−1 = at−1|Ht−1 = ht−1, π,O)
= ∑ o∈O βo(st) µo(st−1, at−1) Pr(Ot−1 = o|Ht−1 = ht−1, π,O) Pr(At−1 = at−1|Ht−1 = ht−1, π,O)
= ∑ o∈O βo(st) µo(st−1, at−1) Pr(Ot−1 = o|Ht−1 = ht−1, π,O)∑ o′∈O Pr(At−1 = at−1, Ot−1 = o ′|Ht−1 = ht−1, π,O)
= ∑ o∈O βo(st)µo(st−1, at−1) Pr(Ot−1 = o|Ht−1 = ht−1, π,O)
× ( ∑ o′∈O Pr(At−1 = at−1|Ot−1 = o′, Ht−1 = ht−1, π,O)
× Pr(Ot−1 = o′|Ht−1 = ht−1, π,O) )−1
= ∑ o∈O βo(st) µo(st−1, at−1) Pr(Ot−1 = o|Ht−1 = ht−1, π,O)∑ o′∈O µo′(st−1, at−1) Pr(Ot−1 = o ′|Ht−1 = ht−1, π,O)
We are left with finding an expression in terms of known probabilities for Pr(Ot−1 = o|Ht−1 = ht−1, π,O).
Pr(Ot−1 = o|Ht−1 = ht−1, π,O) = [
Pr(Ot−1 = o, Tt−1 = 1|Ht−1 = ht−1, π,O) + Pr(Ot−1 = o, Tt−1 = 0|Ht−1 = ht−1, π,O) ] = [( Pr(Ot−1 = o|Ht−1 = ht−1, Tt−1 = 1, π,O)
× Pr(Tt−1 = 1|Ht−1 = ht−1, π,O) )
+ ( Pr(Ot−1 = o|Ht−1 = ht−1, Tt−1 = 0, π,O)
× (1− Pr(Tt−1 = 1|Ht−1 = ht−1, π,O)) )]
= [( π(st−1, o) Pr(Tt−1 = 1|Ht−1 = ht−1, π,O) ) + ( Pr(Ot−1 = o|Ht−1 = ht−1, Tt−1 = 0, π,O)
× (1− Pr(Tt−1 = 1|Ht−1 = ht−1, π,O)) )]
= [( π(st−1, o)βo(st−1) ) +
× ( Pr(Ot−1 = o|Ht−1 = ht−1, Tt−1 = 0, π,O)(1− βo(st−1)) )]
Given that by convention, Pr(T0 = 1|H0 = h0, π,O) = 1.0, we are now left with figuring out how to calculate Pr(Ot−1 = o|Ht−1 = ht−1, Tt−1 = 0, π,O)
Pr(Ot−1 = o|Ht−1 = ht−1, Tt−1 = 0, π,O) = Pr(Ot−2 = o,At−2 = at−2, St−1 = st−1|Ht−1 = ht−1, π,O) = Pr(At−2 = at−2, St−1 = st−1|Ot−2 = o,Ht−1 = ht−1, π,O) × Pr(Ot−2 = o|Ht−1 = ht−1, π,O)
= Pr(St−1 = st−1|At−2 = at−2, Ot−2 = o,Ht−1 = ht−1, π,O) × Pr(At−2 = at−2|Ot−2 = o,Ht−1 = ht−1, π,O) × Pr(Ot−2 = o|Ht−1 = ht−1, π,O)
=P (st−2, at−2, st−1)µo(st−2, at−2) Pr(Ot−2 = o|Ht−1 = ht−1, π,O) =P (st−2, at−2, st−1)µo(st−2, at−2) Pr(Ot−2 = o|Ht−2 = ht−2, π,O)
where Pr(O0 = o|H0 = h0, π,O) = π(s0, o)
Using the recursive function Pr(Ot−1 = o′|Ht−1 = ht−1, π,O), the expected number of terminations for a given trajectory is given by:
|h|∑ t=1 E [Tt = 1|Ht = ht, π,O] = |h|∑ t=1 (∑ o∈O βo(st) µo(st−1, at−1) Pr(Ot−1 = o|Ht−1 = ht−1, π,O)∑ o′∈O µo′(st−1, at−1) Pr(Ot−1 = o ′|Ht−1 = ht−1, π,O) ) ,
A.3 APPENDIX C - PROOF OF THEOREM 2
Theorem 2
Given a set of options O and a policy π over options, the probability of generating a trajectory h of length |h| is given by:
Pr(H|h| = h|h||π,O) = d0(s0) [∑ o∈O π(s0, o)µo(s0, a0)f(h|h|, o, 1) ]∏|h|−1 k=0 P (sk, ak, sk+1),
where f is a recursive function defined as:
f(ht, o, i) =  1, if i = t[ βo(si) ∑ o′∈O π(si+1, o ′)µo′(si+1, ai+1)f(ht, o ′, i+ 1) +(1− βo(si))µo(si+1, ai+1)f(ht, o, i+ 1) ] , otherwise
Proof. We define Hi,t to be the history from time i to time t, that is, Hi,t = (Si, Ai, Si+1, Ai+1, . . . , St), where i < t. If i = t, the history would contain a single state.
Pr(Ht = ht|π,O) = Pr(S0 = s0|π,O) Pr(H1,t = h1,t, A0 = a0|S0 = s0, π,O) =d0(s0) Pr(H1,t = h1,t, A0 = a0|S0 = s0, π,O)
=d0(s0) ∑ o∈O Pr(H1,t = h1,t, A0 = a0, Oo = o|S0 = s0, π,O)
=d0(s0) ∑ o∈O Pr(O0 = o|S0 = s0, π,O) Pr(H1,t = h1,t, A0 = a0|S0 = s0, O0 = o, π,O)
=d0(s0) ∑ o∈O π(s0, o) Pr(H1,t = h1,t, A0 = a0|S0 = s0, O0 = o, π,O)
=d0(s0) ∑ o∈O π(s0, o) Pr(A0 = ao|S0 = s0, O0 = o, π,O)
× Pr(H1,t = h1,t|S0 = s0, O0 = o,A0 = a0, π,O) =d0(s0) ∑ o∈O π(s0, o)µo(s0, ao) Pr(H1,t = h1,t|S0 = s0, O0 = o,A0 = a0, π,O).
We now need to find an expression to calculate Pr(H1,t = h1,t|S0 = s0, O0 = o,A0 = a0, π,O). Consider the probability of seeing history hi,t given the previous state, s, the previous option, o, and the previous action, a:
Pr(Hi,t = hi,t|Si−1 = s,Oi−1 = o,Ai−1 = a) = Pr(Si = si|Si−1 = s,Oi−1 = o,Ai−1 = a) Pr(Hi+1,t = hi+1,t, Ai = ai|Si−1 = s,Oi−1 = o,Ai−1 = a, Si = si) =P (s, a, si) Pr(Hi+1,t = hi+1,t, Ai = ai|Si−1 = s,Oi−1 = o,Ai−1 = a, Si = si) =P (s, a, si) Pr(Hi+1,t = hi+1,t, Ai = ai|Oi−1 = o,Ai−1 = a, Si = si) =P (s, a, si) [ Pr(Ti = 1|Oi−1 = o,Ai−1 = a, Si = si)
× Pr(Hi+1,t = hi+1,t, Ai = ai|Oi−1 = o,Ai−1 = a, Si = si, Ti = 1) + Pr(Ti = 0|Oi−1 = o,Ai−1 = a, Si = si) × Pr(Hi+1,t = hi+1,t, Ai = ai|Oi−1 = o,Ai−1 = a, Si = si, Ti = 0)
] =P (s, a, si) [ βo(si)
× Pr(Hi+1,t = hi+1,t, Ai = ai|Oi−1 = o,Ai−1 = a, Si = si, Ti = 1) + (1− βo(si)) × Pr(Hi+1,t = hi+1,t, Ai = ai|Oi−1 = o,Ai−1 = a, Si = si, Ti = 0) ] .
Even though the equation above might seem complicated, there are only two cases we need to consider: either the current option terminates and a new one must be selected (the first term), or the current option does not terminate (the second term). Let’s consider each of them separately.
Case 1 - option terminates: If we terminate, we sum over new options:
Pr(Hi+1,t = hi+1,t, Ai = ai|Oi−1 = o,Ai−1 = a, Si = si, Ti = 1) = ∑ o′∈O Pr(Oi = o ′|Oi−1 = o,Ai−1 = a, Si = si, Ti = 1)
× Pr(Hi+1,t = hi+1,t, Ai = ai|Oi−1 = o,Ai−1 = a, Si = si, Ti = 1, Oi = o′) = ∑ o′∈O π(si, o ′) Pr(Hi+1,t = hi+1,t, Ai = ai|Oi−1 = o,Ai−1 = a, Si = si, Ti = 1, Oi = o′)
= ∑ o′∈O π(si, o ′) Pr(Hi+1,t = hi+1,t, Ai = ai|Si = si, Oi = o′)
= ∑ o′∈O π(si, o ′) Pr(Ai = ai|Si = si, Oi = o′) Pr(Hi+1,t = hi+1,t|Si = si, Oi = o′, Ai = ai)
= ∑ o′∈O π(si, o ′)µo′(si, ai) Pr(Hi+1,t = hi+1,t|Si = si, Oi = o′, Ai = ai).
Note that the expanded probability has the same form as Pr(Hi,t = hi,t|Si−1 = s,Oi−1 = o,Ai−1 = a).
Case 2 - option does not terminate: This tells us that Oi = o, so we may drop the dependency on the i− 1 terms:
Pr(Hi+1,t = hi+1,t, Ai = ai|Si−1 = s,Oi−1 = o,Ai−1 = a, Si = si, Ti = 0) = Pr(Hi+1,t = hi+1,t, Ai = ai|Si = si, Oi = o) = Pr(Ai = ai|Si = si, Oi = 0) Pr(Hi+1,t = hi+1,t|Si = si, Oi = o,Ai = ai) =µo(si, ai) Pr(Hi+1,t = hi+1,t|Si = si, Oi = o,Ai = ai).
Plugging these two cases back into our earlier equation yields:
Pr(Hi,t = hi,t|Si−1 = s,Oi−1 = o,Ai−1 = a) =P (s, a, si) [ βo(si) ∑ o′∈O π(si, o ′)µo′(si, ai) Pr(Hi+1,t = hi+1,t|Si = si, Oi = o′, Ai = ai)
+ (1− βo(si))µo(si, ai) Pr(Hi+1,t = hi+1,t|Si = si, Oi = o,Ai = ai) ] .
Note that each term contains an expression of the same form, Pr(Hi,t = hi,t|Si−1 = s,Oi−1 = o,Ai−1 = a). We can therefore compute the probability recursively. Our recursion will terminate when we consider i = t, asHt,t contains a single state, and we adopt the convention of its probability to be 1. Notice that for every recursive step, both inner terms will produce a P (s, a, si) term. Consider the result when we factor every recursive P (s, a, si) term to the front of the equation. We define the following recursive function:
f(ht, o, i) =  1, if i = t[ βo(si) ∑ o′∈O π(si+1, o ′)µo′(si+1, ai+1)f(ht, o ′, i+ 1) +(1− βo(si))µo(si+1, ai+1)f(ht, o, i+ 1) ] , otherwise
.
Notice that this is the recursive probability described above, but with the P (s, a, s′) terms factored out. We now see that:
Pr(Hi,t = hi,t|Si−1 = si−1, Oi−1 = o,Ai−1 = ai−1) = f(ht, o, i) t−1∏ k=i−1 P (sk, ak, sk+1).
Plugging this all the back into our original equation for Pr(Ht = ht|π,O) gives us the desired result:
Pr(H|h| = h|h||π,O) = d0(s0) [∑ o∈O π(s0, o)µo(s0, ao)f(h|h|, o, 1) ] t−1∏ k=0 P (sk, ak, sk+1).
A.4 APPENDIX D - EMPIRICAL VALIDATION OF DERIVED EQUATIONS
To double check the derivation of the proposed objective and make sure the implementation was correct, we conducted a simple empirical test to compared the calculated expected number of decisions in a trajectory and the probability of generating each trajectory for a set of 10 trajectories on 10 MDPs. The MDPs are simple chains of 7 states with different transition functions. We randomly initialized four options and a policy over options, and estimated the probability of generating each trajectory and the expected number of terminations, for each sampled trajectory, by Montecarlo sampling 10, 000 trials. Table 1 presents results for the 10 trajectories verifying empirically that the equations were correctly derived and implemented. The table compares the empirical and true probability of generating a given trajectory, P̂r(H|·) and Pr(H|·), respectively, and the empirical and true sum of expected number of decisions an agent has to make to generate those trajectories,∑|H| t=1 Ê [Tt|·] and ∑|H| t=1 E [Tt|·], respectively.
Note that the cases with largest discrepancy between the estimated and calculated number of terminations occur when the probability of generating a trajectory is low. This happens because, since the trajectory is unlikely to be generated, the Monte Carlo sampling is not able to produce enough samples of the trajectory.
A.5 APPENDIX E - IMPLEMENTATION DETAILS FOR ATARI EXPERIMENTS
For these experiments we first learned a good performing policy with A3C for each game and sampled 12 trajectories for training. Each trajectory lasted until a life was lost, not for the entire duration of the episode. Each option was represented as a two-layer neural network, with 32 neurons in each layer, and two output layers: a softmax output layer over the four possible actions representing µ, and a separate sigmoid layer representing β. We implemented our objective using PyTorch which simplifies gradient calculations. The options were represented by a two-layer neural network, where the input was represented by gray scale images of the last two frames. We ran 32 training agents in parallel on CPUs, the learning rate was set to 0.0001 and the discount factor γ was set to 0.99.
Because the options can only learn from the states observed in the trajectories, it is possible that when using them, they will be executed in previously unseen states. When this happens, the termination function may decide to never terminate, as it has not seen that region of the state space before. To address this issue, we add a value of 0.05 to the predicted probability of termination per time-step that the option has been running since executed. Therefore, in our experiments an option cannot run for more than 20 time-steps in total.

Review summaries:
This paper proposes a new option discovery method for multi-task RL to reuse the option learned in previous tasks for better generalization. The authors utilize demonstrations collected beforehand and train an option learning framework offline by minimizing the expected number of terminations while encouraging diverse options by adding a regularization term. During the offline training, they add one option at a time and move onto the next option when the current loss fails to improve over the previous loss, which enables automatically learning the number of options without manually specifying it. Experiments are conducted on the four rooms environment and Atari 2600 games and demonstrate that the proposed method leads to faster learning on new tasks.

The authors propose to learn reusable options to make use of prior information and claim to do so with minimal information from the user (such as # of options needed to solve the task, which options etc). The claim is that the agent is first able to learn a near-optimal policy for a small # of problems and then is able to solve a large # of tasks by such a learned policy.  The authors build on the idea that minimizing the number of decisions made by the agent results in discovering reusable options. The options are learned offline by learning to solve a small number of tasks. Their algorithm introduces one option at a time until introducing a new option doesn’t improve the objective further. The ideas are interesting, However, the paper as it stands is lacking in thorough evaluation.