Unveiling Options with Neural Network Decomposition
Authors: Mahdi Alikhasi
Levi Lelis
Venue: ICLR 2024 poster (2024)
Keywords: reinforcement learning
options
programmatic options
Primary area: reinforcement learning
TL;DR: This paper describes a method that decomposes policies encoded as neural networks with piecewise linear action functions into sub-policies that can be turned into effective temporal abstractions.

Abstract: In reinforcement learning, agents often learn policies for specific tasks without the ability to generalize this knowledge to related tasks. This paper introduces an algorithm that attempts to address this limitation by decomposing neural networks encoding policies for Markov Decision Processes into reusable sub-policies, which are used to synthesize temporally extended actions, or options. We consider neural networks with piecewise linear activation functions, so that they can be mapped to an equivalent tree that is similar to oblique decision trees. Since each node in such a tree serves as a function of the input of the tree, each sub-tree is a sub-policy of the main policy. We turn each of these sub-policies into options by wrapping it with while-loops of varied number of iterations. Given the large number of options, we propose a selection mechanism based on minimizing the Levin loss for a uniform policy on these options. Empirical results in two grid-world domains where exploration can be difficult confirm that our method can identify useful options, thereby accelerating the learning process on similar but different tasks.

Published as a conference paper at ICLR 2024
UNVEILING OPTIONS WITH NEURAL DECOMPOSITION
Mahdi Alikhasi and Levi H. S. Lelis
Amii, Department of Computing Science University of Alberta
{alikhasi, levi 1elis
ABSTRACT
In reinforcement learning, agents often learn policies for specific tasks without the ability to generalize this knowledge to related tasks. This paper introduces an algo- rithm that attempts address this limitation by decomposing neural networks en- coding policies for Markov Decision Processes into reusable sub-policies, which are used synthesize temporally extended actions, or options. We consider neural networks with piecewise linear activation functions, so that they can be mapped to an equivalent tree that is similar to oblique decision trees. Since each node in such a tree serves as a function of the input of the tree, each sub-tree is sub-policy of the main policy. We turn each of these sub-policies into options by wrapping it with while-loops of varied number of iterations. Given the large number of op- tions, we propose selection mechanism based on minimizing the Levin loss for uniform policy these options. Empirical results in two grid-world domains where exploration can be difficult confirm that our method can identify useful options, thereby accelerating the learning process on similar but different tasks.
INTRODUCTION
A key feature of intelligent agents that learn by interacting with the environment is their ability to transfer what is learned in one task to another (André & Markovitch 2005| Taylor & Stone 2009). In this paper, we investigate extracting from neural networks "helpful" temporally extended actions, or options (Sutton et 1999). as means of transferring knowledge across tasks. Given a neural network encoding policy for a task, where a policy is a function that returns an action for a given state of the task, we decompose the network into sub-networks that are used to create options.
We assume that neural networks encoding policies use two-part piecewise- activation func- tions, such as ReLU (Nair & Hinton] 2010). which is standard in reinforcement learning (Mnih) et al. 2013). As shown in previous work (Lee & Jaakkola 2020
Orfanos & Lelis 2023), such
networks can be mapped into oblique decision trees (Breiman et al. 1986). which is a type of tree where each node encodes linear function of the input. In this paper, wise linear functions to a structure similar to an oblique decision tree, which we call a neural tree. Like oblique decision tree, each internal node in the neural tree is function of the input of the network. Unlike an oblique tree, the leaf nodes of neural trees represent the entire output layer of the network. Thus, each node in the neural tree, including leaf nodes, represents a sub-policy of the neural policy. We hypothesize that some of these sub-policies can generalize across tasks and we turn them into options by wrapping them in while-loops that perform different numbers of iterations.
map networks with piece-
Since the number of sub- nollpooicies grows exponentially with the number of neurons in the network, we introduce a procedure select subset of options that minimizes the Levin loss (Orseau al.) 2018) set of tasks that the agent has already mastered. We compute the Levin loss for the uni- form policy over the options because such policy approximates the policy encoded in randomly initialized neural network representing an agent in the carly stages of learning. If the tasks used to generate and select options are similar to the next task, minimizing the Levin loss can increase the chances that the agent visits promising states early in learning, thus guiding the agent's exploration.
Our method of learning options has benefits compared to previous approaches. First, it enables the extraction of options from neural policies, even when learning options was not the original intention. This implics the possibility of learning options from "legacy agents", provided that their networks piecewise-linear functions. Second, our method automatically learns from data when start

---

Published as a conference paper at ICLR 2024
and when to terminate option, and it also decides the number of options required to accelerate learning. The disadvantages are that it assumes a sequence of tasks in which the options generalize, and it involves combinatorial search problem to select options that minimize the Levin loss.
We empirically evaluated on two grid-world problems, where exploration can be difficult, the hy- pothesis that neural decomposition can unveil helpful options. We used small neural networks to allow for the evaluation of all sub-policies; this choice prevented us from possibly conflating lack baseline that generates options
of helpful options with our inability to find them. Compared from the non-decomposed policy of trained networks, options learned with our decomposition were more effective in speeding up learning. Our options were also more effective than transfer learning baselines and three methods that learn options for specific task. This paper offers novel approach to learning options, where options are not intentionally learned, but extracted from existing policies.
The implementation used in our experiments is available online
2 RELATED WORK
Options Temporally extended actions have a long history in reinforcement learning. Many pre- vious works rely on human knowledge provide the options (Sutton al., 1999) or components to enable them to be learned, such as the duration of the options (Frans et al. 2017 Tessler et al.) ).17). the number of options to be learned (Bacon et al., 2017 Igl et al., 2020). or human supervi- sion (Andreas et al. (2017). Our decomposition- based method learns all options components from data generated by the agent interacting with the environment. Other approaches use specific neu- ral architectures for learning options (Achiam et al., 2018), while we show that options can "occur naturally" in neural policies, even when it was not intended to learn them. Options have also been used to improve exploration in reinforcement learning (Machado et al.) 2018: Jinnai et al. 20200] Machado et al. 2023). We minimize the Levin loss for the uniform policy with the goal of guiding exploration in the early stages of learning. However, instead of covering the space, equip the agent with the ability to sample sequences of actions that led to promising states in previous tasks.
Transfer Learning Transfer learning approaches are represented by different categories such as regularization-based such as Elastic Weight Consolidation (Kirkpatrick et al. (017), which pre- vent the agent from becoming too specialized in a given task. Others focused on adapting the neural architecture to allow for knowledge transfer across tasks, while retaining the agent's ability of learning new skills. Progressive Neural Networks (Rusu et al. (016)), Dynamically Expandable representative
Networks (Yoon et al. 2017), and Progress and Compress (Schwarz et al. 2018) methods of this approach. Previous work also stored past experiences as a way to allow the agent to learn new skills while retaining old ones (Rolnick et al., 2019). Previous work has also transferred the weights of one model to the next (Narvekar et al. 2020). One can transfer the weights of a policy (Clegg et al. | (017)), of value network, or both (Shao et al. 2018). SupSup (Wortsman al.) 2020) and Modulating Masks (Ben-Iwhiwhu et al. 2022) also transfer knowledge by learning masks for different tasks. The use of masks is particularly related to our approach because they also allow the agent to use sub-networks of a network, but to learn policies instead of options.
Compositional Methods Compositional method attempts to decompose the problem so that one can train sub-policies for the decomposed sub-problems (Kirsch et al. 2018 Goyal al. 2019 Mendez. et al. 2022). These methods assume that the problem can be decomposed and often rely on domain-specific knowledge to perform such a decomposition. 7PLL learns sub-policies in earlier tasks, and these sub-policies are made available as actions to the agent (Qiu & Zhu 202T). We also learn policies in earlier tasks as means of learning options, but we consider all sub-policies of a policy to learn options, instead of considering only the final policy as an option, as in r-RRL.
We use representative baselines of these categories in our experiments, including Option- Option-Critic (Ba- con et al. 2017), e7-greedy (Dabney et al., (022), and DCEO (Klissarov & Machado 2023). We also use Progressive Neural Networks, and a variant of our method that does not use decomposition and therefore resembles the skill learning process used in 7 PPLL and H-DRLN (Tessler et al. 2017).
resea
2

---

Published as a conference paper at ICLR 2024
3 PROBLEM DEFINITION
We consider Markov decision processes (MDPs) (S,A,,,T:7), where S represents the set of states and A is the set of actions. The function p(5++ 1 18t, a+) encodes the transition model, since it gives the probability of reaching state $(+1 given that the agent is in 8 and takes action d, at time step t. When moving from & to 8t+1- the agent observes the reward value of R&+1, which is returned by the function r; ? in [O, 1] is the discount factor. A policy ι is function that receives state and an action a and returns the probability in which a is taken in 8. The objective is to learn policy æ that maximizes the expected sum of discounted rewards for क starting sy: Ex, Ek= 7* Rk+++1 [se].
Let P = {pI, P2. ... maximize the expected sum of discounted rewards. After learning policies for P, we evaluate the agent while learning policies for a set of tasks P with P' n = 0. This is a simplified version of scenarios where agents learn continually; we focus on transferring knowledge from P to P' through options (Konidaris & Barto 2007).
JanJ } be a set of MDPs, which we refer to as tasks, for which the agent learns
LEARNING OPTIONS WITH NEURAL NETWORK DECOMPOSITION
We use the knowledge that the agent generates while learning policies π for tasks in P to learn temporally extended actions that use "parts" of that can be "helpful". We hypothesize that these temporally extended actions can speed up the learning process of policies for P We consider the options framework define temporally extended actions (Sutton al. 1999). An option is a tuple (tw, Tw. T.). where In is the initiation set of states in which the option can be selected; Tw the policy that the agent follows once the option starts; T. is function that receives a state st and returns the probability in which the option terminates in 8t. We consider the call-and-return execution of options: once initiated, the agent follows Th until terminates.
Here is an overview of our algorithm for learning options.
1. Learn a set of neural policies ( Té:: me, h. one for each task in P.
2. Decompose each neural network encoding no; into of sub-policies U2 (Section 4.1
3. Select subset from U, to form set of options (Section 4.2p.
4. Use A U U as the set actions that the agent has available to learn a policy for tasks in Pl
We can use any algorithm that leams a parameterized policy wa, such as policy gradient (Williams)
1992) and actor-critic algorithms (Konda & Tsitsiklis 1999) in Step above. In Step we can use any algorithm to solve MDPs, because we augment the agent's action space with the options learned in Steps 3 Kulkarni et al. 2016). The process of decomposing the policies into sub-policies
described Section 4. (Step 2 and the process of defining and selecting a set of options
described in Section 4.2 (Step Since we use the set of options Ω as part of the agent action space
defines The and T. for all w Ω and I,, is set to be all states Due to its process of decomposing trained neural networks, we call DEC-OPTIONS both the algorithm and the options it learns.
for the tasks in P',
4.1 DECOMPOSING NEURAL POLICIES INTO
We consider fully connected neural networks with m layers (l, (.), where the first layer is given by the input values X and the m-th layer the output of the network. For example, m for the network shown in Figure [ Each layer has ny neurons (1...., n2)) where ni = [X] The parameters between layers i and i + of the network are indicated by W E Ra and B E g The k-th row vector of W and Bi, denoted Wi and B represent the weights and the bias term of the k-th neuron of the (i + 1)-th layer. In Figure | π 2 and n2 = 2. Let A' E R be the values the i-th layer produces, where A = X and A is the output of the model. A forward pass in the model computes the values of A' g o'Z"), where 9(-) is activation function and Z' = Wi-1 - + B In Figure [ the neurons in the hidden layer use ReLU as the activation function, and the output neuron uses a Sigmoid function.
3

---

Published as a conference paper at ICLR 2024
Neural Network
Neural Tree
F1
4
2 + ag +1
S
2ir +1
22
xg
+
0
[
0-22n
22 + 2)
af 2r x2)
4r
2 +
A neural network with two inputs, two ReI.U neurons in the hidden layer, and one Sigmoid neuron in the output neuron is shown on the left. All bias terms of the model are 1; for simplicity, we omit bias values. The neural tree representing the same function encoded in the network is shown on the right. The root of the tree represents the neuron Ai, the nodes in the second layer represent the neuron A2. and the leaf nodes represent the output neuron Ai, where a (.) is the Sigmoid function. The colors of the neurons match the colors of the nodes in the tree that represent them.
Figure I:
Let (N, E) be binary tree, which we call neural tree. Here, N represents the nodes in the tree and F the connections between them. Given a network with two-part piecewise linear activation functions (e.g., ReLU), we can construct equivalent neural tree, where each internal node of the tree represents a neuron in the layers [2, m - 1J of the network (all neurons, but those in the output layer). The neurons in the output layer are represented in each leaf node of the tree. Like oblique decision trees, each internal node of neural trees defines a function P-X + S of the input X. Unlike oblique decision trees, each leaf node represents the computation of the output layer of the network. In the case of a neural policy for an MDP with |A| = 2 actions, so that the number of output neurons mmm = 1, each leaf node returns the Sigmoid value of P. X + v. If the number of actions is |A| > 2, so that nmm = |A|, then each leaf node returns the probability distribution given by the Softmax values of p X + V, where P' E R X and V E R In continuous action spaces, each leaf returns the parameterized distribution from which an action can be sampled. Once the parameters of the internal and leaf nodes are defined, inference is made starting at the root of the tree, and if P X + u S O, then we follow the left child; otherwise, we follow the right child. This process is repeated until a leaf node is reached, where the leaf computation is performed.
If neuron the two linear functions composing g. For example, neuron employing a ReLU function, expressed as 9(=)= max(0, 2). The neuron's output is either 0 or z. When the input of ReLU network is fixed, each neuron is either inactive (yielding 0) or active (yielding 2). This leads to the concept of an activation pattern, an ordered set composed of binary values representing each node in the network. It signals whether a node is active or inactive for an input X (Montúfar et al. 2014 Zhang et al., 2018 Lee & Jaakkola 2020). Every path in a neural tree corresponds to an activation pattern, excluding those in the output layer. For example, if P. X + S is true for the root of the tree, then the left sub-tree of the root represents the scenario in which the first neuron of the network is inactive. In contrast, the right sub-tree represents the scenario in which the first neuron is active. Choosing a path in the neural tree means that every neuron represents a linear function. Consequently, combining multiple linear functions results in another linear function. This allows us to define the function of the output layer in each tree as a linear function of the input X.
a two-part piecewise linear function 9(-), its output value is determined by of
Example 1 Consider the example in Figure where the neural network represents a neural policy with two actions, given by the Sigmoid value of the oulput neuron. Figure | also shows the neural tree that represents the neural network. The tree accounts for all activation patterns in the neural network. For example, if both neurons in the hidden layer are inactive, then A =A = O and the output of the network is (0--1100-1 1+++ = (1); this activation pattern is represented by the left branch of the tree. the first neuron (from top to bottom) in the hidden layer is active and the second is inactive, the neural network produces the output a (-1-(2x1 + +12+1)++1++++
= a--2r1 -22); this activation pattern is given by following the right and then left branch from the root.
Since all nodes in the neural tree represent a function of the input, each sub-tree of the neural tree represents sub-policy of the policy the network encodes. A neural network with d neurons and a single hidden layer decomposes into 2d+1 sub-policies, one for each node in the tree. Note, however, that the order in which neurons are represented along the paths of the neural tree could
4

---

Published as a conference paper at ICLR 2024
result in different sub-policies. In our running example, the sub sub-programs we obtain if Ai is the root of the tree are different from the programs we obtain if A3 is the root. The total number of different sub-pon pobliciisees for network with single hidden layer with d neurons is Σ (:) .2'. In our example, this sum results in 1 1+ 1+4+4-- = 9. To give intuition, the value of for = 0 represents the sub-policy that is identical to the original policy. The value of 4 for i = 1 is the number of sub-policies given by trees rooted at the children of the root of the tree: the root of the tree can represent different neurons and each of them has 2 children, for total of 4. Finally, the sub- sub-policies given by the leaf nodes are identical independently of order of the earlier nodes, and they are exactly 4. In this paper, consider small neural networks with one hidden layer, we can evaluate all sub-policies of neural policy. This is to test our hypothesis that these sub-policies can result in "helpful" options.
4.2 SYNTHESIZING AND SELECTING OPTIONS
Let {To, To...... To. J be the set of policies that the agent learns for each task in P. Let Ug be the set of sub-policies obtained through the neural tree of To, as described in the previous section, and U {U1, U2 U.). Let {(50, oo), (81, a1), (ST, aT) be a sequence of state-action pairs observed under and distribution of initial states μ for task p. where so is sampled from Ii and, for given state 8t in the sequence, the next state St+1 is sampled from p(-]st, dt), where a arg max, π (st, a). The use of the arg max operator over reduces the noise in the selection process of the OPE-OOSSIOS because the options also act greedily according to the sub-policies extracted from π. If is episodic, ST+1 is a terminal state; T 1 defines maximum horizon for the sequence otherwise. Ti is a set of such sequences for To, and pa 's μ. Finally, T = (Ti, T2, ... ",,,",,TT) ).
The sub-policies U do not offer temporal abstractions as they are executed only once. We turn these sub-policies into options by wrapping each π in U with a while-loop of z iterations. Once the resulting option w is initiated, it will run for steps before terminating. We denote wa the z-value of w. In each iteration of the while loop, the agent will execute in the environment the action arg max, (s, a). where x is the sub-policy and s the agent's current state. The arg max operator ensures that the policy is deterministic within the loop. Let Tmax be the length of the longest sequence in T, then we consider options with z = 1. Trux for each sub-policy in U. Let Ω = (S2, S2, .......................... S. } be the set of all while-loop options obtained from U. Each Ω2 has T [U]] options for Pt. one for each 2. Our task is to select a subset of "helpful" options from S2
We measure whether set of options is helpful in terms of the Levin loss (Orseau et al. 2018) of the set. The Levin loss measures the expected number of environmental steps (calls to the function p) an agent needs to perform with a given policy to reach target state. The Levin loss assumes that p is deterministic and the initial state is fixed; the only source of variability comes from the policy. The Levin loss for a sequence Ti and policy π is L(T., R)) = II [(saa) The factor 1/ I/((S..) as) is the expected number of sequences that the agent must sample with π to observe T, We assume that the length of the sequence the agent must sample to observe Ti is known to be [T/| and therefore is fixed, so the agent performs exactly [T|] steps in every sequence sampled.
[T.]
Let T., be the uniform policy for an MDP, that is, a policy that assigns equal probability to all actions available in a given state. Furthermore, let = be the uniform policy when we augment the MDP actions with set of options Ω. There available actions. First, the Levin loss can increase because the probability of choosing each action decreases, including the actions in the target sequence. Second, the Levin loss can decrease because the number of decisions the agent needs to make can also decrease, potentially reducing the number of multiplications performed in the denominator of the loss. Our task is then to select a subset of options from the set Ω generated with decomposed policies such that we minimize the Levin loss.
two effects once we add set of options to the set of
arg min R'Cor T.ETV
Σ C(T,, R
We divide the set of tasks P into disjoint training and validation sets to increase the chances of selecting options that generalize. For example, an option that encodes тe, with loop that iterates for 2 steps, where 2 is equal to the length of the sequences in T,, is unlikely to generalize to other tasks, as it is highly specific P:. In Equation Py is the set of options extracted from the policies learned for the tasks in the training set and Tv are the sequences obtained by rolling out the policies learned for the tasks in the validation set. We consider uniform policies in our formulation because they
5

---

Published as a conference paper at ICLR 2024
approximate neural policies in the first steps of training, since the network's weights are randomly initialized. By minimizing the Levin loss, we reduce the expected number of sequences that the agent samples to observe high reward values. Solving the subset selection problem in Equation is NP-hard (Garey & Johnson 1979), so we use greedy approximation to solve the problem.
4.2.1 GREEDY APPROXIMATION TO SELECT OPTIONS
The greedy algorithm for approximating a solutions to Equation initializes Sz' as an empty set and, in every iteration, adds S2' the option that represents the largest decrease in Levin loss. The process stops when adding another option does not decrease the loss, so it returns the subset S
Due to the call-and-return model, we need to use a dynamic programming procedure efficiently compute the values of C while selecting Ω!, This is because it is not clear which action/option the agent would use each state of sequence so that the probability II (s.a))) (5,, a) is maximized. For example, an option returns the correct action for w, states in the sequence starting in $1. While w' does not return di in 81, it returns the correct action in the sequence for w/ states from 82. If wi < w/ and using w 81 prevented us from using w' in 82 because w would still be executing in 82, then using (1 in A for $1 and then starting w' in 82 could maximize [[())))TT (8, a).
Algorithm COMPUTE-LOSS
Require: Sequence S = {s0, {10,$1,"* $1, .. sTT+1 of states of a trajectory T, probability Pa,t, options Ω Ensure: C(T, xT))
1: M[i + j for j 1, T + 1 initialize table assuming only primitive actions
2: for j = 0 to T + do
3: for w in Q do
4:
if w is applicable in 8, then
5:
Mij + w2] < min(MB + ws], M[1] + 1) # w is used in 8j for w. steps
6:
if > 0 then
7:
[b] + min (Mjj - 1] + 1, MD))
8: return [T] (Pw,n) -
Algorithm D shows the computation of L. The procedure receives a sequence of states from trajectory T: the sequence includes T's terminal state 8T+1. It also receives the probability Pu,0 = 1 M+++ of choosing any of the available actions under the uniform policy when the action space is augmented with the options in Ω. Finally, it also receives the set of options Q and returns C(T, TT.).
To compute the Levin loss, one needs to decide whether each transition 8; to 8:4 in T is covered by an action in A or an option in f2 [ verifies all possibilities for each of these pairs such that the Levin loss is minimized. It uses a table MM with one entry for each state in S, which stores the smallest number of decisions the agent must make to reach each state in the sequence. Initially, the procedure assumes that the agent reaches all states with primitive actions (line I M[j j for all j. Then, it updates the entries of M (lines 5 and 7 by verifying which options w can be applied each state. At the end of the computation (line 8
[j] stores the smallest number of decisions that the agent must make to reach 8,, for all j. including T + 1. The minimum loss for Pu,0 and Ω based on the smallest number of decisions needed to reach the end of the sequence, ST+1 (line 8
Algorithm ! computes the Levin loss for a set of options Ω in 0( T) time steps; its memory complexity is O(T). We present in Appendix Alan an example of the computation of Algorithm |
5 EXPERIMENTS
We conducted experiments to evaluate the hypothesis that neural networks encoding policies for MDPs may contain useful underlying options that can be extracted through neural decomposition.
In our experiments, we consider a set of tasks P, all of which share a common state representation and output structure, but may differ in terms of reward functions and dynamics. The primary ob- jective is to evaluate an agent that uses an action space augmented with DEC-OPTIONS synthesized from P on new set of tasks P'. We use Proximal Policy Optimization (PPO) (Schulman et al.

---

Published as a conference paper at ICLR 2024
(a) Simple Crossing
(b) Four Rooms
(c) ComboGrid 1
(d) ComboGrid 2
Figure 2: Representative images of the problem domains used our experiments.
2017] in the set of tasks P. implemented using the Stable- framework (Raffin et al. 202 The policy network was configured as a small need-forwrrd neural network with ReLU neurons. We use small neural networks be able to evaluate all sub- sub-policies in the greedy selection step of REC-OPTIONS. This way, we are able to evaluate our hypothesis without the added complexity of searching in the space of sub-policies. We use larger networks for the value function, the value network is not used in DEC-OPTIONS. The task of learning policies for the set P does not have to be solved with actor-critic algorithms. This is because the DEC- OPT-OOS action space of the agents and any learning algorithm can be used. Thus, we evaluate both the Deep Q-Network (DQN) (Mnih al., al.] 2013) algorithm alongside PPO. Additional details, including agent architectures, hyperparameter settings, and used libraries are provided in the Appendix.
used augment the
Baselines the DEC-OPTIONS are helpful, then the sample-efficient than DQN and PPO operating in the original action space (Vanilla-RL). To demon- strate the importance of the decomposition and selection steps of DEC-OPTIONS, we also consider baseline where the action space of the agents is augmented with the neural policies learned from the tasks P (Neural-Augmented), We also consider a variant of DEC-OPTIONS where we only perform the generation and selection steps, without performing decomposition, i.e., consider the non-decomposed policies for P while generating options (Dec-Options- Seeo--ptton-Woolee This compari- son serves as evidence that neural decomposition facilitates transfer learning compared using the complete policy. We also consider baseline where both the value and policy models are trained in a task and initialized with the weights of the previously learned model when learning to solve new task (Transfer-PPOO. Since masking methods also access sub-policies of network, we consider Modulating-Mast as a baseline. We use PNN, Progressive Neural Networks, as a representative baseline of methods that adapt the neural architecture. To demonstrate the impact of knowledge transfer, we consider Option- Critic, ez-greedy, and DCEO as representative algorithms for learn- ing options directly in tasks P', without using knowledge of the policies learned for tasks in P.
agent should be more
5.1 PROBLEM DOMAINS
We use two domains where exploration can be difficult and it is easy to generate similar but different tasks: MiniGrid Schevalier-Boiveer et al., 2023) and ComboGrid, which we introduce in this paper.
MiniGrid The first domain is based on Minigrid environments, In MiniGrid, the agent is restricted partial observation of its surroundings, determined by a view size parameter. We select set of simple tasks set P and a set of more challenging tasks as set P In P, we use three instances of the Simple Crossing Environment with 9 grids and one wall, shown in Figure [2 For the test set P', we use three configurations of the Four Rooms Environment, as illustrated in Figure 2b) In Four Rooms, the agent navigates 19 x 19 grid divided into four rooms. In the first task, the agent and the goal point in the same room. In the second task, they are located in neighboring rooms, and in the third task, which is shown in Figure 2b they are located in two non non- non-neighboring rooms.
ComboGrid In this environment, the agent has full observational capabilities. The agent's move- ments are determined by a combination of actions (combo). Four unique combinations, each corre- sponding move neighboring cell, dictate the agent's navigation. If the agent successfully executes the correct series of actions corresponding to a valid combo, it moves to the corresponding neighboring cell. Failing to execute the correct combo results in the agent remaining in its current position and the history of previous combo actions being reset. The state contains not only the grid, but also the agent's current sequence of actions. A reward of -1 is assigned in the environment,

---

Published as a conference paper at ICLR 2024
(PPO)
Rooms (PPO)
(PPO)
1.00
0.75
Retum
Opc-Onllons
Dec-OptonswWhdd Whole
0.25
Noura Stura//ugmontes
Modultting Mask
12
0.6
1. 0.0
0.9
Transter
Time steps (x10f)
Time steps (x10*)
Time steps (x10*)
ez-grwdd
Four Rooms 1 (DQN)
Four Rooms (DQN)
Four Rooms (DON)
0.75
Return
0.25
Doc Options
OotamnCriic
0.00
0.25
0.50 steps (x10%)
0.750.00
0.25
0.50
8.750.30
0.25
0.50
Vanils-RL
steps (x10%)
steps (x10*)
Figure 3: Performance of different methods on MiniGrid Domain.
with a reward granted once the terminal point reached. We evaluate DEC-OPTION and baselines four versions of ComboGrid, each differing in grid size: x3) (4 4), (5x5), (6 6). For the set P. we use four instances each grid size; Figure (eguure2cshows shows one of the tasks P for size 6 X 6. Tasks in P differ in their initial and goal positions, which can cause interference for algo- rithms that do not decompose policies while transferring knowledge. Figure [d] the instance in Pl for grid size 6 x 6. The agent receives reward of 10 for collecting each green marker.
5.2 EMPIRICAL RESULTS
3x3 ComboGrid (PPO)
4x4 ComboGrid (PPO)
5x5 ComboGrid (PPO)
6x6 ComboGrid (PPO)
Retur
Dec Options
Dec Ophiee--hhhtee
Nbural Aggmette
Mod Med.deiinggMss
PNN
0'4
0.2
0.60.0
0.4
0'8
120.0
Transtor
Time steps (x10*)
Time sleps 6x10*)
Time steps (x10*)
Time steps (x10
magreedy
3x3 ComboGrid (DON)
4x4 CombaGrid (DON)
5x5 ComboGrid (DQN)
6x6 Com ComboGrid (DON)
30
Return
20
10
Option
2,40
Time steps (x10F)
Time steps 6x10%)
Time steps (x105)
Time steps (x10F)
DCE0
Figure& 4: Performance of different methods ComboGrid Domain.
8

---

Published as a conference paper at ICLR 2024
Figure shows the learning curves of agents equipped with DEC-OPTIONS and of the baselines. The first row shows the results for agents using PPO, while the second row shows the results for agents using DQN. Each plot shows the average return the agent receives over 24 independent runs of each system; the plots also show the 95% confidence interval of the runs. Since the domain is not discounted, the maximum reward is 1.0. Each instance of Four Room: 1, 2, and 3, represents a domain in which the agents using transfer learning attempt to learn after learning policy for tasks in P. Similarly to Figure 3 Figure shows the results for the ComboGrid domain. Here, the maximum return the agent can obtain is 40, 10 for each marker the agent collects.
In Minigrid, Vanilla-RL fails to learn a good policy with the number of samples used in our experi- ments. The dynamics of the environment, where the agent needs to turn and then move, contributes to this difficulty. Transfer-PPO and PNN also faced difficulties due to interference caused by dif- ferences between tasks (Kessler et al. 2022). In contrast, NEC-OPTIONS, Dec-Options-Were Whole, Auggene,,,,,,,,,, and Modulating- Mask performed well in Four Rooms Regarding the DQN agents, Option-Critic, Critic, DCEO, and DEC-O REC-OPTIONS outperformed Vanilla-RL. As the complexity of the task increases, most of the baselines do not converge to an optimal policy. In particular, only the agent learned optimal policies in Four Rooms 3.
In the smallest ComboGrid, most of the baselines yield similar performance. Similarly to Minigrid, we increase the size of the grid, start to notice differences among the methods. For grids of Options-ttoootttoo converge quicker to an optimal policy than the
size 4 x 4, DEC-OPTIONS and other methods. For grid of size 6 x 6, DEC- OPC-OPSIONS converges quicker than all other methods. For the DQN experiments, we also observe similar results to those observed in MiniGrid, where the gap between DEC-OPTIONS and other methods increases as the grid size increases.
Although we compare DEC-OPTIONS with other option-learning algorithms, we note that DEC- OPTIONS solves fundamentally different problem than the other methods evaluated. For example, DCEO focuses on exploration while learning options for a target task. In contrast, we learn options on set of tasks and evaluate whether these options are helpful in downstream problems. Future research might investigate the use of some of these baselines in the context of transfer learning.
Examples DEC-OPTIONS learned long options for MiniGrid. The sequence below shows the tions from state to goal (left to right) of the DEC-OPTIONS agent the Four Room 3 environment. Here, O, 1, and mean 'turn right', 'turn left', and 'move forward', respectively. The curly brack- ets show what is covered by one of the options learned. The options reduce the number of agent decisions from 39 only 10 in this example.
0, 0, 2,
0, 2.2 2,2,0,2.,,2,,,,,,,22222222 2, 2,2,, 0,
Option
Option
Option 1
We show a sub-sequence of an episode of the DFC-OPTIONS agent in the 4 x ComboGrid. Option 2 learns sequences of actions that move the agent to another cell on the grid (c.g.. "Down" and "Right"). Option I is shorter than Option 2 and it applies in many situations. For example, calling Option 1 twice can move the agent up, or even finish left move then move up.
Right
Up
Down
Down
Down
Up
0,2,2,
0,0
2, 2,
0,2,2, 0, 2,
0,2
2,0 0,
Option 2
Option 2
Option
Option
Option 2
Option 2
Option 2
Option
Option
Option
Option 1
CONCLUSIONS
In this paper, we showed that options can "occur naturally" in neural network encoding policies and that we can extract such options through neural decomposition. We called the resulting options DEC-OPTIONS. Our decomposition approach assumes set of related tasks where the goal is to transfer knowledge from one set of tasks to another. Since the number of options we can extract from neural networks grows exponentially with the number of neurons in the network, we use a greedy procedure to select subset of them that minimizes the Levin loss. By minimizing the Levin loss, we increase the chances that the agent will apply sequences of actions that led to high-reward states in previous tasks. We evaluated our decomposition and selection approach hard-exploration grid- problems. The results showed that DEC- OPTIONS accelerated the learning process in a set of tasks that are similar to those used train the models from which the options were extracted.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This research was supported by Canada's NSERC and the CIFAR AI Chairs program, and was enabled in part by support provided by the Digital Research Alliance of Canada. We thank the reviewers for the discussions and their suggestions, Marlos Machado for helpful comments on an early draft of this work, and Martin Klissarov for answering questions we had regarding DCEO.
REFERENCES
Joshua Achiam, Harrison Edwards, Dario Amodei, and Pieter Abbeel. Variational option discovery algorithms. arXiv preprint arXiv: 1807. 2018.
David André and Shaul Markovitch. Learning representations for the transfer of learning. In Pro- ceedings of the International Joint Conference on Artificial Intelligence, volume 5, pp. 415-420, 2005.
Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. In International conference on machine learning, pp. 166-175. PMLR, 2017.
Pierre-Lue Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Proceedings of the AAAI conference artificial intelligence, volume 31, 2017.
Escoghene Ben-Iwhiwhu, Saptarshi Nath, Praveen K Pilly, Soheil Kolouri, and Andrea Soltoggio. Lifelong reinforcement learning with modulating masks. arXiv preprint arXi::2212.11110 2022.
Lco Breiman, Jerome Friedman, Richard A Olshen, and Charles J Stone. Classification and regression trees. CRC press, 1986.
Maxime Chevalicr-Boisved Bolun Dai, Mark Towers, Rodrigo de Lazcano, Lucas Willems, Salem Lahlou, Suman Pal, Pablo Samuel Castro, and Jordan Terry. Minigrid & miniworld: Modular & customizable reinforcement learning environments for goal-oriented tasks. CoRR, 1as//3306.18811, 2023.
Alexander Clegg, Wenhao Yu, Zackory Erickson, Jie Tan, Karen Liu, and Greg Turk. Learning to navigate cloth using haptics. In 2017 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2799-2805. IEEE, 2017.
Will Dabney, Georg Ostrovski, and Andre Barreto. Temporally-extendee e-greedy exploration. In International Conference on Learning Representations, 2021.
Kevin Frans, Jonathan Ho, Xi Chen, Pieter Abbeel, and John Schulman. Meta learning shared hierarchies. arXiv preprint arXiv:1710.09760 2017.
Michael Garey and David S. Johnson. Computers and Intractability: Guide to the Theory of WPP-Competenees. W. H. Freeman, 1979.
Anirudh Goyal, Shagun Sodhani, Jonathan Binas, Xue Bin Peng. Sergey Levine, and Yoshua Ben- gio. Reinforcement learning with competitive ensembles of coomation-coostrinnee primitives. arXiv preprint arXiv: 1906. 10667, 2019.
Maximilian Igl, Andrew Gambardella, Jinke He, Nantas Nardelli, N Siddharth, Wendelin Böhmer, and Shimon Whiteson. Multitask soft option learning. In Conference on Uncertainty in Artificial Intelligence, pp. 969-978. PMLR, 2020.
Yuu Jinnai, Jee W. Park, Marlos C. Machado, and George Konidaris. Exploration in reinforcement learning with deep covering options. In International Conference Learning Representattioss 2020.
Samuel Kessler, Jack Parker-Holdes Philip Ball, Stefan Zohren, and Stephen Roberts. Same state, different task: Continual reinforcement learning without interference, In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 7143-7151, 2022.
10

---

Published as a conference paper at ICLR 2024
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiaoo Ramalho, Agnieszka Grabska Barkkskaaaiikk,, et al. Overcom- ing catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114(13):3521-3222 2017.
Louis Kirsch, Julius Kunze, and David Barber. Modular networks: Learning to decompose neural computation. Advances in neural information processing systems, 31, 2018.
Martin Klissarov and Marlos C. Machado. Deep laplacian-based options for temporally-extender exploration. In Proceedings of the International Conference on Machine Learning. JMLR.org, 2023.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. In Solla, T. Leen, and Müller (eds.), Advances in Neural Information Processing Systems, volume 12, pp. 1014- MIT Press, 1999.
George Konidaris and Andrew Barto. Building portable options: Skill transfer in reinforcement learning. In International Joint Conference Artificial Intelligence, pp. 895-900, 2007.
Tejas D Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum. Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29, 2016.
Steven M Valle, Michael S Branicky, and Stephen R Lindemann. On the relationship between classical grid search and probabilistic roadmaps. The International Journal of Robotics Rexearch, 23(7-8):673-692, 2004.
Guang-He Lee and Tommi S. Jaakkola. Oblique decision trees from derivatives of relu networks. In International Conference on Learning Representations, 2020.
Marlos C. Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. In International Conference on Learning Representations, 2018.
Marlos C. Machado, André Barreto, Doina Precup, and Michael Bowling. Temporal abstraction in reinforcement learning with the successor representation. Journal of Machine Learning Research, 24:1-69, 2023.
Jorge A Mendez, Harm van Seijen, and Eric Eaton. Modular lifelong reinforcement learning via neural composition. arXiv preprint arXiv:2207.00429, 2022.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 131iv:1312.5602. 2013.
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of lin- ear regions of deep neural networks. In Proceedings of the International Conference on Neural Information Processing Systems. pp. 3924-2933 Cambridge, MA, USA, 2014. MIT Press.
Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the International Conference on International Conference on Machine Learning, pp. 807 814, 2010.
Sanmit Narvekar, Bei Peng. Matteo Leonetti, Jivko Sinapov, Matthew Taylor, and Peter Stone. Curriculum learning for reinforcement learning domains: A framework and survey. The Journal of Machine Learning Research, 21(1):7382-431, 2020.
Spyros Orfanos and Levi H. S. Lelis. Synthesizing programmatic policies with actor-critic algo- rithms and relu networks, 2023.
Laurent Orseau, Levi H. S. Lelis, Tor Lattimore, and Théophane Weber. Single-agent policy tree search with guarantees. In Proceedings of the International Conference on Neural Information Processing Systems, pp. 3205-3215, 2018.

---

Published as a conference paper at ICLR 2024
Wenjie Qiu and He Zhu. Programmatic reinforcement learning without oracles. In International Conference on Learning Representations, 2021.
Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dor- mann. Stable-baselines3: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22(268):1-8, 2021.
David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy Lillicrap, and Gregory Wayne. Experience replay for continual learning. Advances in Neural Information Processing Systems, 32, 2019.
Andrei A Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. arXiv preprint 1rXiv:1606.04677 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford. and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint urXiv:1707.06347 2017.
Jonathan Schwarz, Wojciech Czarnecki, Jelena Luketina, Agnieszka Gaabska-Barwinska. Yee Whye Teh, Razvan Pascanu, and Raia Hadsell. Progress & compress: A scalable framework for contin- ual learning. In International conference on machine learning, pp. 4528 4537. PMLR, 2018.
Kun Shao, Yuanheng Zhu, and Dongbin Zhao. Starcraft micromanagement with reinforcement learning and curriculum transfer learning. IEEE Transactions Emerging Topics in Computa- fional Intelligence, 3(1):73-84, 2018.
Richard Sutton, Doina Precup, and Satinder Singh. Between MDPs and semi-MDPs: A frame- work for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181- 211. 1999.
Matthew E Taylor and Peter Stone. Transfer learning for reinforcement learning domains: A survey. Journal of Machine Learning Research, 10:1633-1685, 2009.
Chen Tessler, Shahar Givony, Tom Zahavy, Daniel Mankowitz, and Shie Mannor. A deep hierarchi- cal approach to lifelong learning in minecraft. In Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
Ronald J Williams.
Simple statistical frollwin-folloiing algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-25 256, 1992.
Mitchell Wortsman, Vivek Ramanujan, Rosanne Liu, Aniruddha Kembhavi, Mohammad Rastegari, Jason Yosinski, and Ali Farhadi. Supermasks in superposition. Advances in Neural Information Processing Systems, 13:15173-15184, 2020.
Jaehong Yoon, Eunho Yang. Jeongtae Lee, and Sung Ju Hwang. Lifelong learning with dynamically expandable networks. arXiv preprint arXiv: /7xiv:/708.01547, 2017.
Liwen Zhang, Gregory Naitzat, and Lek- Heng Lim. Tropical geometry of deep neural networks, In Jennifer Dy and Andreas Krause (eds.), Proceedings of the International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5824-5832, PMLR, 2018.
12

---

Published as a conference paper at ICLR 2024
A EXAMPLE OF THE ALGORITHM FOR COMPUTING THE LEVIN LOSS
Let S = {80, $1, 82, 84, 35 be a sequence of states and Ω = {wi, w2) be a set of options. W/ can start in Sy and terminates $2; w2 can start $1 and it terminates in $4. Next, we show how the table M in Algorithm [ changes after every iteration of the for-loop in line
Iterations
M
initialization
0, I, 2, 4,
0, I, I, 3, 4,5
0, 1. 1, 2,5
0, 1,3,,,
1,
1,
0, 1,
The value of [5) at the end of the last iteration indicates that the state a; can reached with three actions: primitive action from 80 to 81, we from to 84, and another primitive action from 81 to $3. If pu,ft = 0.25, then the optimal Levin loss value returned line of Algorithm T for T
and Q is 0.25
384.
B EXPERIMENTS DETAILS
B. OPTIONS SELECTION PROCESS
our methodology, we employ an approach to select options based on set of sequences denoted T (Ti, T2, J. as described in Section 4.2 This selection process is driven by greedy algorithm, facilitating the identification that when decomposing the policy ne, the resulting sub-policies will have low Levin loss sequence T. To mitigate this bias, we compute the Levin loss for sub-policies derived from the neural decomposition of no; on the set T (Ti).
options that can be "helpful". However,
the case
B.2 PLOTS
Figures shown in Section were generated using standardized methodology. To ensure robustness, we applicd a systematic procedure to all our baselines. We began the process by performing a hyperparameter search, outlined in B.3 select the best hyperparameters for each baseline. Subsequently, we perform 30 independent runs (seeds) for each baseline. We discarded the 20% of the independent runs with the poorest performance. We computed the mean and 95% confidence intervals over the remaining 24 seeds.
B.3 ARCHITECTURE AND PARAMETER SEARCH
For algorithms utilizing the Proximal Policy Optimization (PPO) framework, including Vanilla- RL PPO, Neural-Augmenteed Transfer-PPO, PNN, ez-greedy, Dec-Options-Whole and Dec- Options baselines, we used the stable-baselines library (Ratiin et al. 202T). A comprehensive parameter search was conducted. encompassing the clipping parameter, entropy coefficient, and learning rate. These parameters are reported for each domain in their respective sections. In the case of PNN, we leveraged the library provided htthtttss///giie http//ttttt.tt../////////t com/ arcos inniinnooii while still relying on the PPO algorithm from stable-baselines for training. For the ez-greedy algo- rithm, we integrated the cemporally-extendee e-greedy algorithm with the PPO algorithm from the stable-baselines. We set the to be equal to 0.01 and the to be equal to 2, ez-greedy's 's original work. For Option-Critic implementations, we used the implementation in https: /ggttub.. com/ 1wei twt.ttaaaapp//mmmmmm... rate and the number of options in a hyperparameter sweep process. For the DCEO baseline, we used the implementation from the original paper (https: / thub. cwm.moommmmmmoooom mkk ssaa/ dceo/).
and the best parameters found for the learning
13

---

Published as a conference paper at ICLR 2024
(a) Simple Crossing
Seed
(b) Simple Crossing Seed
(c) Simple Crossing Seed
Figure 5: MiniGrid Simple Cross Tasks
The parameter search is then applied the learning rate, the number of options, and the probability of executing an option. As for the Modulating-Mann -ask method, we used the code provided by the original authors (https://githul) com/ dipbe/ halppp/emss-aae mask-mssss In scenarios where the Deep
Q-Network (DQN) was employed, such as Vanilla-RI. DQN and Dec-Options DQN baselines, we adhered to the stable-baselines. Similarly PPO, performed parameter search, this time tar- geting Tau and the learning rate, while keeping other parameters fixed, All the parameter searches mentioned were performed using the grid search method (La et al.) 2004).
For tasks within the MiniGrid domain, we employed feedforward network. The policy network structure consisted of single hidden layer comprising nodes, while the value network used three hidden layers with 256 neurons each. As tasks transitioned to P', expanded the policy network to encompass three hidden layers with 50 neurons in each layer. In the Transfer-PPo method, also used policy network with three hidden layers with 50 neurons in each across all tasks in both P and PP. Regarding the Modulating-Mask approach, we retained the structure of the neural network in its original implementation. This structure featured shared feature network with three hidden layers, each with 200 neurons, followed by one hidden layer with 200 neurons for the policy network and another hidden layer also with 200 neurons for the value network. For DQN- based methods, including Vanilla-RL DQN and Dec-Options DQN. as well as Option-Critic and DCEO, the neural network had three hidden layers, each with 200 neurons.
In the ComboGrid domain, the architectural and parameter search aspects mirrored those of the MiniGrid domain for DEC-OPTIONS The policy network structure featured one hidden layer with 6 nodes for tasks in P. and we increased it to 16 nodes for tasks in P Transfer-PPO maintained uniform policy network structure one hidden layer with nodes across all tasks P and P', The value network is network with 3 hidden layers with 200 neurons each for tasks in P and Pl As for the Modulating-Mo methods and Option-Critic, adopted two-layer configuration with 32 neurons in the first layer and 64 neurons in the second hidden layer.
method, the structure the neural network as before. For DON-based
C DOMAINS
C.I MINIGRID
As described in Section 5 we leveraged the MiniGrid implementation provided by Chevalier Boisvert et al. (2023). For our experiments, we opted for the Simple Crossing tasks, which formed the training set denoted as P. Notably, we selected three different variants of 'MiniGrid- SinpleCrossingS9N1-V00 as illustrated in Figure 5 For the test set P', we chose three versions of the Four Rooms domain, as depicted in Figure 6 In these environments, actions for interacting with object are not needed and were not available the agent. The agent had access to three prim- itive actions: 'Action Left' (represented by 0) for left turns, 'Action Right' (represented by 1) for right turns, and 'Action Forward' (represented by 2) for forward movement. At each step, the agent views a small field front of itself. making the environment partially observable. Also, its view obstructed by walls where applicable. Regarding the representation of the state, employed
14

---

Published as a conference paper at ICLR 2024
(a) Four Rooms
(b) Four Rooms 2
(c) Four Rooms
Figure 6: MiniGrid Four Rooms Tasks
modified version of the original MiniGrid observation. At each time step, the agent's view is constrained to 5x5 grid in front of itself. This observation was then transformed into a one-hot encoding format. The one-hot encoding encapsulated various elements, including the goal, walls, and empty floor spaces, Additionally, we incorporated the agent's directional orientation into the ob- servation, consistent with the conventions of the original MiniGrid. This directional indicator served compass for the agent, aiding it in determining its current facing direction. This representation aimed to streamline observations without altering the fundamental dynamics of the original library. To maintain consistency across our experiments, we maximum episode length of 1000 for tasks in set P and 361 for tasks in set P In terms of rewards, we assigned a value of -1 for each step in tasks within set P, except termination points. Tasks in set P' were designed with rewards of 0 for all states, except upon reaching the terminal state, where reward of was granted.
Parameter Search for all methods used in our experiments. We have outlined the search spaces for each method below.
In pursuit of reasonable hyperparameters, performed parameter search
For methods using the PPO algorithm, explored the following hyperparameter ranges:
Learning Rate: 0.005, 0.001, 0.0005, 0.0001, 0.00005
Clipping Parameter: 0.1, 0.15, 0.2, 0.25, 0.3
Entropy Coefficient: 0.0, 0.05, 0.1, 0.15, 0.2
For methods relying on the Deep Q-Network (DQN) paradigm, parameter search encompassed the following hyperparameter lists:
Learning Rate: 0.01, 0.005, 0.001, 0.0005, 0.0001
Tau: 1., 0.7, 0.4, 0.1
In the of the Option-Criie Critic method, explored the following hyperparameter combinations:
Learning Rate: 0.01, 0.005, 0.001, 0.0005, 0.0001, 0.00005
Number of Options 2, 3, 4, 5,
For the DCEO baseline, we explored the following hyperparameter combinations:
Learning Rate: 0.01, 0.005, 0.001, 0.0005, 0.0001, 0.00005
Number of Options: 3, 10
Option Probability: 0.2, 0.7, 0.9
The hyperparameter values used our experiments with MiniGrid problems are given Tables
and 6
15

---

Published as a conference paper at ICLR 2024
Clipping Parameter
Entropy Coefficient
Learning Rate
Vanilla-RL
0.15
0.05
0.0005
Neural-Augmented
0.2
0.2
0.0005
Transfer-PPO
0.15
0.15
0.0001
PNN
0.1
0.0
0.0001
Modulating-Mann
0.15
0.1
0.001
ez-greedy
0.15
0.05
0.0005
Dec-Options-Wine Whole
0.3
0.15
0.0005
Dec-Options
0.25
0.0005
Table 1: Four Rooms 1 PPO
Tau/Number of Options
Learning Rate
Vanilla-RL
0.7
0,0001
Option-critic
0.0001
Dec-Options
0.7
0.0005
DCEO
5 (Probability: 0.9)
0.0005
Table 2: Four Rooms DQN
Clipping Parameter
Entropy Coefficient
Learning Rate
Vanilla-RL
0.1
0.2
0.0005
Neural-Augmente
0.15
0.0
0.0005
Transfer-PPO
0.05
5e-05
PNN
0.25
0.0
0.005
Modulating-Mann
0.2
0.0
0.01
ez-greedy
0.1
0.0
0.0001
Dec-Options-Wii Whole
0.25
0.05
0.0005
Dec-Options
0.2
0.1
0.001
Table 3: Four Rooms 2 PPO
Tau/Number of Options
Learning Rate
Vanilla-RL
1.0
0.0005
Option-critic
0.0001
Dec-Options
1.0
0.001
DCEO
10 (Probability: 0.9)
0.001
Table 4: Four Rooms 2 DQN
C.2 COMBOGRID
In the ComboGrid environment, the agent's movement is dictated by sequence of actions, which we refer to as "combos". These action sequences are described in the list below, for Down, Up. Right, and Left.
Moving Down: 0, 2,
Moving Up: 0, 0, 1, 1
Moving Right: 1, 2, 1, 0
Moving Left: 1, 0, 2,
16

---

Published as a conference paper at ICLR 2024
Clipping Parameter
Entropy Coefficient
Learning Rate
Vanilla-RL
0.2
0.0
5e-05
Neural-Augmented
0.1
0.0
0.001
Transfer-PPO
0.1
0.05
0.0001
PNN
0.15
0.0
0.001
Modulating-Mass
0.1
0,0
0.005
ez-greedy
0.25
0.05
0.0005
Dec-Options-Whet Whole
0.15
0.05
0,001
Dec-Options
0.2
0.001
Table 5: Four Rooms 3 PPO
Tau/Number of Options
Learning Rate
Vanilla-RL
0.7
0.001
Option-critic
0.0001
Dec-Options DCEO
0.1
0.0005
10 (Probability: 0.9)
0.0001
Table 6: Four Rooms 3 DQN
In experiments, conducted tests under four settings of the ComboGrid environment, each varying in size. The tasks P. of sizes x 5 and 6 x 6, are shown in Figure Across all tasks in the set P. established uniform reward structure, with value of assigned for every step taken in the environment, except when reaching the terminal state, where the reward was set to 0. The tasks in set P' for different grid sizes are also presented in Figure 8 These tasks adhered reward structure, with reward value of assigned for all states except those corresponding to goal points, where the reward was set 10. There were four distinct goal points on the grid, which added to the maximum cumulative reward attainable in a single episode of 40. The action space and the fully observable state space remained fixed for tasks, regardless of the size of the grid, encompassing tasks in both sets, P and pl.
different
Agents are presented with primitive actions represented by integers 0, and 2, resulting the cre- ation of combinations ("combos")) according to the specifications described above. For example, to move down, the agent needs to perform the sequence 0, 2, 2, 1. At each time step, the agent is pro- vided with complete view of the grid in the form of one-hot representation. This representation encapsulated the position the agent as well as the positions of the goals within the grid. Conse- quently, the dimension of the observation space was proportional to the size of the grid, resulting in a representation of size W x 2, where W is the size of the grid. Additionally, the agent received the sequence of past combo actions, also in one-hot encoding format, part of its input. We enforce maximum episode length of 2 80 steps for tasks in set P and W x 16 steps for tasks within set P'.
Parameter Search Similarly to MiniGrid, we performed a parameter search for all methods used our experiments. We have outlined the search spaces for each method below.
For methods utilizing the PPO algorithm, we explored the following hyperparameter values.
Learning Rate: 0.05, 0.01, 0.005, 0.001
Clipping Parameter 0.05, 0.1, 0.15, 0.2, 0.25, 0.3
Entropy Coefficient: 0.0, 0.05, 0.1, 0.15, 0.2
For methods relying on the Deep Q-Network (DQN) paradigm, our parameter search encompassed
the following hyperparameter values.
Learning Rate: 0.05, 0.01, 0.005, 0.001, 0.0005, 0.0001
Tau: 1., 0.7, 0.4, 0.1
17

---

Published as a conference paper at ICLR 2024
I
I
(a) Grid 5x5 Task
(b) Grid 5x5 Task
(c) Grid 5x5 Task
(d) Grid 5x5 Task 4
(e) Grid
(l) Grid 6x6 Task
(g) Grid 6x6 Task
(h) Grid 6x6 Task
Figure 7: ComboGrid tasks. In this depiction, the agent is highlighted in red, while the goals denoted in green, and the walls are represented in grey.
(a) ComboGrid 3x3
(b) ComboGrid 4x4
(c) ComhoGrid 5x5
(d) ComboGrid 6x6
Figure 8: ComboGrid p' tasks
In the case the Option-Critic method, we explored the following hyperparameter values.
Learning Rate: 0.01, 0.005, 0.001, 0.0005, 0.0001, 0.00005
Number of Options 2, 3, 4, 5,
For the DCEO baseline, we explored the following hyperparameter values.
Learning Rate: 0.01, 0.005, 0.001, 0.0005, 0.0001
Number of Options: 3, 5, 10
Option Probability: 0.2, 0.7, 0.9
As for the Modulating-Matt method, we explored the following hyperparameters values.
Learning Rate: 0.005, 0.001, 0.0005, 0.0001, 0.00005
Clipping Parameter 0.1, 0.15, 0.2, 0.25
Entropy Coefficient: 0.0, 0.05, 0.1, 0.15, 0.2
The hyperparameter values used our experiments with ComboGrid problems are given in Tables
12
and 14
18

---

Published as a conference paper at ICLR 2024
Clipping Parameter
Entropy Coefficient
Learning Rate
Vanilla-RL
0.15
0.1
0.01
Neural-Augmented
0.25
0.05
0.01
Transfer-PPO
0.3
0.05
0.001
PNN
0.2
0.1
0.01
Modulating-Mann
0.1
0.1
0,0005
ez-greedy
0.15
0.05
0.005
Pee-Options-Whet Whole
0.15
0.05
0,005
Dec-Options
0.2
0.05
0.005
Table 7: ComboGrid 3x3 PPO
Tau/Number of Options
Learning Rate
Vanilla-RL Option-critic
1.
0.001
0.001
Dec-Options DCEO
1.
0.001
10 (Probability: 0.2)
0.0005
Table 8: ComboGrid 3x3 DQN
Clipping Parameter
Entropy Coefficient
Learning Rate
Vanilla-RL
0.1
0.0
0.005
Neural-Augmented
0.3
0.0
0.005
Transfer-PPO
0.05
0.2
0,001
PNN
0.2
0.1
0.005
Modulating-Mask
0.25
0.15
0.0001
ez-greedy
0.2
0.05
0,005
Dec-Options-When Whole
0.25
0.05
0.01
Dec-Options
0.25
0.0
0.005
Table 9: ComboGrid 4x4 PPO
Tau/Number of Options
Learning Rate
Vanilla-RL Option-critic
0.7
0,0005
0.0005
Dec-Options
1.
0,0005
DCEO
(Probability: 0.2)
0.0005
Table 10: ComboGrid 4x4 DQN
D QUALITATIVE ANALYSIS OF RESULTS
D.1 MINIGRID
In study, we used heatmaps to visually represent the distribution of cells visited within the MiniGrid environment during training. These heatmaps provide information on the states that the agent frequents at different training steps. By comparing the heatmaps of the with those of Vanilla-BB RL in Figure 9 we can see different exploration patterns, which can be related the performance of the methods shown in Figure 3
method
19

---

Published as a conference paper at ICLR 2024
Clipping Parameter
Entropy Coefficient
Learning Rate
Vanilla-RL
0.25
0.1
0.005
Neural-Augmented
0.15
0.0
0.005
Transfer-PPO
0.1
0.2
0.001
PNN
0.25
0.05
0.005
Modulating-Mann
0,2
0,05
0,001
ez-greedy
0.2
0.15
0.005
Pec-Options-Wher Whole
0.2
0.05
0,005
Dec-Options
0.2
0.05
0.005
Table 11: ComboGrid 5x5 PPO
Tau/Number of Options
Learning Rate
Vanilla-RL. Option-critic
0.7
0.001
4
0.0001
Dec-Options
0.001
DCEO
5 (Probability: 0.7)
0.001
Table 12: ComboGrid -
Clipping Parameter
Entropy Coefficient
Learning Rate
Vanilla-RL
0.1
0.05
0.005
Neural-Augmented
0.2
0.05
0.005
Transfer-PPO
0.3
0.05
0.001
PNN
0,05
0,0
0,005
Modulating-Man
0.15
0.0
0.005
ez-greedy
0.2
0.05
0.005
Dec-Options- Whole
-holle
0.2
0.0
0.001
Dec-Options
0.15
0.05
0.005
Table 13: ComboGrid 6x6 PPO
Tau/Number of Options
Learning Rate
Vanilla-RL
0.7
0.001
Option-critic
0.005
Dec-Options
0.7
0.001
DCEO
3 (Probability: 0.9)
0.0001
Table 14: ComboGrid 6x6 DQN
D.2 COMBOGRID
To illustrate the DEC- OPTIONS learned in the ComboGrid problems, we sampled the trajectories of the policy trained to use the options. The following sequences are partial trajectories of the agents that highlight the use of the learned options. We present trajectories on ComboGrid problems of sizes 3 x 3, x 5, and 6 x 6 (trajectories for the grids of size x are already presented in the main text). We present only partial trajectories for grids of sizes 5 x and 6 to improve readability.
In grids of size 3 3, the learned options almost exactly match the dynamics of the problem. The exception is Option 4, which only partially executes the sequence actions that allow the agent to move left. For grids of size 5 5 and 6 6, DEC-OPTION learns longer options. For example, for x 5, Option can almost complete the sequence of actions to go up twice, while for 6 6, Option 2 can perform the sequence of actions go left twice.
20

---

Published as a conference paper at ICLR 2024
Figure 9: This figure shows the heatmap of cells visited in the Four Rooms 1 environment for both the DEC-OPTIONS and Vanilla-RL methods. The first shows the heatmap of the DEC- OPTIONS's method, while the second row shows the Vanilla-RL method. The first, second, and third columns show the heatmap after 1, 3200, and 12800 steps, respectively.
ComboGrid 3x3 (full trajectory):
Down
Up
Up
Right
Down
Left
Left
2.
O.
2.
1,
0. 2, 2 1. 0, 2,
Option
Option
Option
Option
Option
Option
Option
ComboGrid 5x5:
Up
Up
Right
Right
Down
Down
0, 0, 1, 1. 0, 0. 1. 2, 1.
1.2.1.
0,0
2.2
2,2
Option
Option
Option
Option
Option
Option
Option 4 Option
ComboGrid 6x6:
Left
Len
Up
Up
Up
Right
1, 0, 2,
2,
1, 2, 2,
0.0
1,
0,0
2,
1.0
Option
Option
Option!
Option 3 Option
Option
Option
Option
E BASELINE SELECTING RANDOM OPTIONS
We also considered a baseline where we ignore steps and 2 of DEC-OPTIONS and randomly select an option that performs a fixed set of actions length M. We then add of such options to the agent's is action set. Note that this approach requires domain knowledge, the values of M and K are not known a priori. By contrast, DEC-OPTIONS discovers them automatically.
We ran experiments the Combo domain where chose M to be 6, which is the average number of options OEC-OOPSONS chooses and to be 4, which is the number of directions the agent can move. We present the results in Figure I0 DEC- DEC-OPTIONS performs better than this baseline. Even when we manually set the values of M and K. there are many options to choose from, and it is unlikely that helpful options would be selected this way.
21

---

Published as a conference paper at ICLR 2024
3x3 ComboGrid (PPO)
4x4 ComboGrid (PPO)
5x5 CombeGrid (PPO)
6x6 ComboGrid (PPO)
Retur
Dpp---paaaaa Vanilla RL Random
0.4
Time steps (x10*)
Time steps (x10P)
Time steps (x10²)
Time steps (x10*)
Figure 10: Comparison of DEC-OPTIONS with Vanilla-RL, and the Random baseline.
22


Reviews:
[{"review_id": "yjtdcu6kLH", "reviewer": "Reviewer_j32D", "summary": "The paper proposes to decompose piece-wise linear neural networks into options. To do so the authors build on the idea of decomposing a neural network into a neural tree, a quantity closely related to oblique decision trees. As each node of the tree is a sub-policy, the authors propose to use a Levin loss to prune the important sub-policies from which options will be derived. The authors evaluate their approach on a series on grid worlds.", "questions": "What would be required to scale the method to larger neural networks?\n\nWhy investigate the ComboGrid environment? What is interesting about this task?\n\n\"we consider small neural networks with one hidden layer, so we can evaluate all sub-policies of a neural policy.\" This should be highlighted more.\n\n\n======================================================================\n\n[1] Deep Laplacian-based Options for Temporally-Extended Exploration. Klissarov and Machado. 2023", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "* The authors propose a novel way to learn options, directly from neural networks that are learning, or that have been retrained\n* The overall presentation is rigorous as well as the empirical evaluation (10 seeds with 95% CI)\n* The method seems to perform better compared to proposed baselines\n\nOne of the strong points of the method is the originality in the way the options are discovered. Although the empirical evaluation is limited, the method clearly has a lot of potential as stated by the authors, for example by learning options from \"legacy agents\". I think the community would do well in integrating such unusual ways of learning options/skills. Moreover, the empirical evaluation is rigorous and clearly shows statistical advantages.", "weaknesses": "* The presentation is heavy and sometimes confusing. Efforts in addressing this are done but it is not close to being enough\n* The HRL baseline of Option-Critic is outdated and does not reflect progress in the field\n* The qualitative experiments are very limited\n\nThe whole of section 4.1 and 4.2 would require a deep rewriting. Many references to oblique trees are made, yet most of the readers will have no idea what that is. A better visualization than Figure 1 would be needed, and it should be on the same page as the description in 4.1.  I would suggest starting with a simple case of 2 actions and leave the generalizations too much later. The notation of Z is confusing, it adds many sub- and super-scripts that are not well presented. Are the Z functions really necessary to understand the method? The whole section of 4.2 suffers from similar problems. I would strongly suggest the authors to consider the point of view of someone who knows nothing about the specifics of their method and to write these sections from that point of view. It will be most helpful to the paper.\n\nOne of the HRL baseline is Option-Critic which is an outdated algorithm that has been beaten many times. [1] recently set strong performance across a wide range of environments. To adequately understand the merits of the method such a baseline should be included.\n\nThe qualitative experiments are very limited. Much more on this aspect is needed as interpretabiltiy is one of the hallmarks of HRL. I would suggest heatmaps that show option activation or trajectories that highlight when options are activated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WXMkJ3gCN7", "reviewer": "Reviewer_i5GW", "summary": "This paper studies the problem of extracting useful skills/options from existing neural network policies. The proposed method involves collecting a set of neural networks (that use piecewise linear activation functions) trained to perform a variety of tasks and then constructing tree structures (neural trees) representing the activation patterns of these networks. Every subtree of a neural tree can be interpreted as a separate policy giving rise to a collection of sub-policies which are used to construct options. Since this collection of options can be large and contain very specialized policies that may not be useful in general, the authors propose a greedy method for selecting a set of useful options. Experiments in grid world environments show that the extracted options are effective in learning to perform new unseen tasks.", "questions": "1. It appears that Levin loss corresponding to the uniform policy is equivalent to the minimum number of actions (or steps) required to explain a trajectory. Since the general Levin loss is described, are there other natural candidates (which would simply weight different actions/steps differently) besides the uniform policy to use for option selection?\n1. Algorithm 1 uses $O(|\\mathcal{T}|^2)$ space. It looks like the algorithm can be modified to use $O(|\\mathcal{T}|)$ space (the loss after position j is independent of d). Is there a specific reason for using the version in the paper? \n1. It looks like Dec-Options-Whole is doing reasonably well in most cases. Could this suggest a heuristic to reduce the computational complexity by not considering all subtrees of the neural tree? From my understanding, Dec-Options-Whole is only considering a single subtree per tree which is the whole tree, so maybe there is a middle ground between the two extremes?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Inferring skills/options that can be used to perform new tasks is an important problem and the proposed approach provides an intuitive way of extracting options from pretrained neural network policies. This method leverages the compositional structure of neural networks to identify sub-policies that might be useful for performing new tasks. Based on my understanding, any such sub-policy matches the original policy on inputs triggering a specific set of activations in the network which represents a specific region of the state space where this option is used in the original policy. Therefore, this appears to be a principled way of extracting options from pretrained policies.\n- The idea of directly extracting options from NN policies instead of constructing them during training appears to be novel and interesting. As far as I know, this is the first paper to propose this idea and this might lead to further research on such approaches.\n- Experimental results look very promising with the proposed approach outperforming existing baselines for constructing options as well as transfer learning approaches.\n- The paper is well-written and examples are provided to illustrate key concepts.", "weaknesses": "- The main weakness appears to be scalability of the approach w.r.t. the size of the neural network. The total number of options considered is exponential in the size of the network. The option selection method involves enumerating all candidate options which doesn’t help address the computational challenges of such an approach.\n- Experiments are limited to grid world environments. Experiments in more complex environments with continuous state and action spaces would strengthen the paper significantly. Although the current experiments demonstrate the value in the proposed method for constructing options, it would be good to confirm its applicability in a wider range of scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CnvnW7hQM5", "reviewer": "Reviewer_voTZ", "summary": "The paper proposes to distill policies from a learned neural network and use these as options. They provide an algorithm that translates the neural network into a tree, decomposes it into sub-policies and selects their subset. In experiments, they verify the usefulness of the approach in several variants of grid-based domains.", "questions": "Please, present a definite argument (e.g., an experiment or a disproval why I am wrong) that the steps (1) and (2) are needed and the set of extracted sub-policies is useful, compared to a set of random sub-policies. I may reconsider the rating based on the arguments presented.\n\nI assume that in the beginning of the section 4.2, the authors meant `where a_t = argmax_a \\pi(s_t , a)`, instead of `where a_t = argmax_a p(s_t , a)`. However, if that is true, why not to sample the actions as `a_t ~ \\pi(s)`? If this is to make a unique sequence per each policy, clearly indicate it for the reader and add a reason.\n\n---\nSuggestions:\n- The graph in Figure 1-right confused me for a while, as I was trying to read it from left-to-right, instead of top-to-down. Indicate this fact for the reader. Also, consider (I don't stress this point) showing the complete graph with the path highlighted.\n\nTypos:\n- p. 7: Since learning a policy [IN] the new set ...\n- p. 7: baseline Dec-Options-Whole[.]", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and is original in the way the options are created -- i.e., extracting them from an already trained neural network. However, the suggested approach is limited only to simple NNs.", "weaknesses": "First substantial weakness is that the number of sub-policies raises exponentially with the size of the NN, limiting this approach to very small networks and thus the significance of the proposed algorithm. \n\nSecond, given the large number of the subpolicies, it is not clear whether the subset selection (step 3) is better than selecting from a set of random policies. That is, if steps (1) and (2) are ommited and step (3) would select from a random set. In the second example at the end of Experiments, the subpolicies consist of 4 actions, which can be easily randomly generated. This would drastically reduce the complexity of the algorithm, but still would be limited to simle domains. This ablation is crucially missing from the evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)