Robustly Learning Composable Options in Deep Reinforcement Learning

1 Introduction

Temporal abstraction is a promising approach to scaling reinforcement learning (RL) algorithms [Botvinick et al., 2009] because it is capable of addressing some of the biggest challenges in RL: structured exploration [Jinnai et al., 2019], transfer [Konidaris and Barto, 2007] and long-term credit assignment [Dietterich, 2000]. Hierarchical methods are particularly attractive for long-horizon, sparse reward tasks, where flat (non-hierarchical) RL algorithms often struggle.

Hierarchical approaches succeed by allowing the agent to sequentially execute high-level actions. This intuition has led to several skill-discovery algorithms that explicitly satisfy the composability objective: executing one skill takes the agent to a state where it can execute another. Such algorithms are widespread in the literature; from controltheory [Lyapunov, 1992; Burridge et al., 1999; Tedrake, 2009], to robotics [Lozano-Perez et al., 1984; Kaelbling and Lozano-P´erez, 2017], to the online [Randløv et al., 2000; Konidaris and Barto, 2009; Shoeleh and Asadpour, 2017;

∗Equal contribution

Video, code and appendix can be found at https://sites.google. com/brown.edu/robustly-composing-options

Bagaria and Konidaris, 2020] and batch RL [Singh et al., 2020] settings.

Even when skills are not explicitly constructed to be sequentially executable, they must eventually be sequenced to solve goal-directed tasks [Sharma et al., 2020; Frans et al., 2018]. Additionally, skills that can be reliably sequenced can support abstract, high-level planning [Konidaris et al., 2018].

The core difficulty that arises when discovering composable skills is that of non-stationary subgoals. Skill-discovery algorithms that explicitly optimize for composability must learn the regions (called initiation sets [Sutton et al., 1999]) from which each skill can be successfully executed. To construct sequentially executable skills, the initiation set of one skill becomes the subgoal of a new skill [Konidaris and Barto, 2009]. These initiation sets are constantly changing as the agent learns, causing the target (and therefore reward function) of successive skills to also change over time, destabilizing composability and complicating learning.

We propose three methods to combat this problem. First, we propose to stabilize learned initiation sets using a dualclassifier approach. An optimistic classifier determines when the agent can execute the skill, which encourages exploration. Meanwhile, a pessimistic classifier is used as a subgoal target, which is likely to grow but unlikely to shrink, leading to stable chains. Next, to create skill policies that are robust to non-stationary subgoals, we propose to use goal-conditioned policies [Schaul et al., 2015] for each skill. Such policies are robust to subgoal changes because they can always be retargeted towards a state in the new subgoal region. Finally, while the majority of skill-discovery work has been modelfree, we show that using model-based RL to learn skill policies leads to a substantially more robust skills.

To evaluate our proposed changes, we consider four sparsereward continuous control problems in MuJoCo [Todorov et al., 2012]. Compared to a flat model-free solution [Fujimoto et al., 2018; Andrychowicz et al., 2017], our agent achieves at least two orders of magnitude better sample efficiency. While a flat model-based solution [Nagabandi et al., 2018] is unable to solve any of the problems considered in this paper, our model-based hierarchy solves them with relative ease. Finally, our agent achieves at least a 5× improvement in sample-efficiency over a state-of-the-art skill-discovery algorithm [Bagaria and Konidaris, 2020].

2 Background and RelatedWork

We consider decision making problems modelled as episodic, goal-oriented MDPs M = (S,A,R, T , γ, G) [Sutton and Barto, 2018], where G refers to a set of goals that the agent could be asked to reach, whereupon execution terminates with a non-negative reward. Like most goal-conditioned RL algorithms [Schaul et al., 2015; Andrychowicz et al., 2017], we assume access to a reward function R : S × G → R.

Model-Free RL. Model-free methods often use Q-learning [Watkins and Dayan, 1992] to learn Qπ (st, at), estimating the expected sum of discounted future rewards conditioned on taking action at from st, thereafter following policy π. The policy π(st) = argmaxa∈AQ(st, a) chooses an action that greedily maximizes the Q-function at a given state. The Q-function is often represented by a neural network φ [Mnih et al., 2015] and the policy by another neural network ψ [Lillicrap et al., 2015]. Many algorithms exist for learning φ and ψ from interactions with M [Duan et al., 2016].

Hindsight Experience Replay (HER). When the class of policies we wish to learn in M is restricted to goal-reaching policies [Kaelbling, 1993], HER can improve sample efficiency as follows. Given a trajectory τ1 = (s1, a1,R(s2, g), s2), ..., (sn, an,R(sn+1, g), sn+1) executed while trying to reach goal g, HER [Andrychowicz et al., 2017] replays τ1 assuming that the agent was trying to reach goal sn+1, by augmenting its set of experiences with another trajectory τ2 = (s1, a1, R(s2, sn+1), s2), ..., (sn, an, R(sn+1, sn+1), sn+1). Replaying trajectory τ2 trains the agent to reach state sn+1, even when the reward function R is sparse.

Model-Based RL. While Q-learning directly learns the value function for control, model-based methods first learn an approximate model of the system dynamics. This model fξ : S × A → S is often represented using another neural network ξ [Nagabandi et al., 2018]. Model-based methods can then select actions by solving:

such that st+1 = fξ(st, a). In Model Predictive Control (MPC) [Garcia et al., 1989], the agent approximately solves this optimization problem at every time-step, executing only the first action from the resulting action sequence. By replanning at every time-step, MPC is robust to the prediction errors that compound over time with a learned model [Asadi et al., 2019].

2.1 Hierarchical Reinforcement Learning

The standard RL formulation considers an agent selecting primitive actions at every time-step. In hierarchical RL [Barto and Mahadevan, 2003], the agent instead selects temporally extended actions or skills. These skills are commonly modeled as options [Sutton et al., 1999], where each option o is described using three elements: the initiation region, Io : S → {0, 1}, describing the set of states from which the option can be executed; the termination region, βo : S → {0, 1}, describing the subgoal region in which option execution must terminate; and the policy, πo : S → A, which drives the agent from Io to βo. Several methods have been proposed to autonomously discover useful options (see Abel [2020], chapter 2.3, for a survey).

Skill Chaining. For two options oi and oj to be reliably sequentially executable, it must be the case that βoi ⊆ Ioj . The skill-chaining algorithm [Konidaris and Barto, 2009] explicitly satisfies this property by learning options such that βoi = Ioj . In skill-chaining, each discovered option o learns its initiation region Io,θ using a binary classifier θ that describes the region from which the πo reaches βo with high probability. Simultaneously, πo is learned using a model-free RL algorithm to reach its subgoal region βo. The algorithm is recursive: it first learns an option that initiates near the goal and reliably takes the agent to the goal; then it learns another option whose termination region is the initiation region of the first option; then it repeats the procedure targeting the new option. Options are chained together in this fashion until the agent discovers an option whose initiation region contains the start state. Deep skill chaining (DSC) [Bagaria and Konidaris, 2020] extended skill-chaining with deep RL, outperforming existing state-of-the-art skill-discovery algorithms [Levy et al., 2019; Bacon et al., 2017].

Since DSC explicitly constructs composable options, we build on top of it to show that our proposed augmentations can substantially improve the reliability of the resulting options. However, since any skill-discovery algorithm must eventually compose learned skills to solve goal-directed tasks, our insights could, at least in principle, improve the robustness of their solutions.

2.2 RelatedWork

Robustness in HRL. Several variants of the Option-Critic architecture [Bacon et al., 2017] have showcased robustness to changes in transition dynamics or the reward function [Mankowitz et al., 2018; Khetarpal and Precup, 2019; Tiwari and Thomas, 2019; Jain et al., 2021]. By contrast, we seek to improve the reliability of hierarchical methods in stationary, sparse-reward MDPs.

Composing Options. Some recent work has studied the problem of composing skills as linear [Barreto et al., 2019] or non-linear [Qureshi et al., 2020] combinations of options available to the agent. These methods require pre-trained options, while we discover them from scratch.

Model-Based Skill Discovery. Empowerment-driven skilldiscovery methods [Gregor et al., 2016; Eysenbach et al., 2019] have recently been augmented with model-based RL via the DADS algorithm [Sharma et al., 2020]. This led to a family of related methods that optimize for exploration [Campos Cam´u˜nez et al., 2020], lifelong learning [Lu et al., 2021], and skill acquisition in image-based observation spaces [Baumli et al., 2020]. These methods represent substantial progress in unsupervised skill-discovery, but our setting differs from theirs in a few ways. First, unlike these methods, we do not require a special pre-training phase for skill-discovery. Second, while DADS is designed for the multi-task setting, we focus on creating more robust solutions to single-goal MDPs. Finally, skills learned by DADS have global support, whereas we consider composability for skills that specialize in different regions.

3 Robustly Learning Composable Options

The core difficulty in learning composable options is that, during learning, all three components (Io, βo, πo) of every option are simultaneously in flux. This difficulty is compounded by the relationship between the initiation region of one option and the subgoal region of another-changes to one option's initiation region changes another's subgoal, in turn changing its own policy and initiation region. These changes cascade to downstream options, propagating instability and causing chains of composable options to become unreliable or even break. This situation-which can happen whenever composable options are being learned simultaneously-is illustrated in Figure 2.

To ameliorate this difficulty, which we call nonstationary subgoals, we propose to robustify the learning process of all three option components. First, we propose a two-classifier representation of the initiation region that provides a stable subgoal target while encouraging exploration. Second, we use hindsight-experience replay to learn a generalized policy that enables us to target subgoal states that maximize the probability of being able to execute the successor option. Finally, to manage the difficulty of learning so many functions in parallel, we leverage the higher stability of model-based RL methods to learn more robust option policies.

3.1 Dual Initiation Classifiers to Avoid Shrinkage

Previous approaches learned a single binary classifier to represent Io for each option o in the skill chain. If the option execution succeeds (i.e, the agent reaches βo), it adds a new positive example for further refining Io. Since the positive example is from a region already inside the classifier, a successful execution leaves the classifier's decision boundary largely unchanged. Alternatively, if the option execution fails to reach βo, the agent gets a negative example for the next training iteration of Io. Since this negative example comes from a region inside the classifier, it often shrinks the initiation region over time, with no opportunity to expand.

To avoid this issue, we propose a dual-classifier parameterization of Io-representing it using both optimistic and pessimistic classifiers. The pessimistic classifier represents the states from which we are highly confident that option execution will succeed, and so is a stable region for other options to target. However, if the agent could only ever choose to execute the option from inside this classifier, exploration would be hindered because the option would be prevented from expanding to new regions. To encourage exploration outside the pessimistic region, we also use an optimistic classifier to represent states where the agent can choose to execute the option. Eventually, the two classifiers should converge to approximate the "true" initiation region of the option.

Many techniques could be used to learn these two classifiers; we learn the optimistic classifier using a two-class SVM [Cortes and Vapnik, 1995] and the pessimistic classifier using a one-class SVM [Tax and Duin, 1999]. For more details, please refer to Appendix A3.

3.2 Robust Subgoals via Goal State Selection

We next turn to termination regions. The "chainability" of options oi and oj implies that the subgoal region βoi is a subset of the initiation region Ioj . As Ioj is refined over time, the subgoal region βoi also changes, and consequently, so does the option's terminating reward. Since learning is highly sensitive to even small changes in the reward function [Packer et al., 2018], this creates instability in learning πoi . DSC [Bagaria and Konidaris, 2020] mitigates this issue by freezing Ioj after a fixed number of learning iterations, which can lead to the agent being stuck with poor estimates of Ioj that hinder reliable skill composition.

Nevertheless, an option's subgoal region will unavoidably change continually as its target option refines its initiation classifier. To be robust to changes in βo, we propose to make each option policy more flexible: rather than a fixed policy πo, each option learns a goal-conditioned policy πo(s|g) using hindsight experience replay (HER). By conditioning the option policy πo on goals sampled from βo, and postponing selecting g until option execution time, the agent learns a policy robust to non-stationarity in βo.

The goal-conditioned option policy strategy necessitates a strategy for sampling subgoal states from βo. We propose optimizing two objectives for choosing subgoal states: (a) robustness and (b) hierarchical optimality.

Selecting Subgoal States for Robustness

Each option policy is rewarded for reaching its termination region; from its own perspective, all states in its termination region are equally rewarding. However, for a subsequent option o, some start states are better than others. How can we pick a subgoal for one option so that we increase the probability that a successive option execution will succeed?

One way is to evaluate the probability of every positive example of o succeeding (by querying the probabilistic classifier representing Io), but that becomes computationally very expensive as the agent gathers experience. Instead, we use the simple heuristic that, over time, the agent will learn to execute the option from reliable start states, and simply sample from the set of positive examples used to train Io.

Selecting Subgoal States for Hierarchical Optimality

The method above results in feasible trajectories that are, at best, recursively optimal [Barto and Mahadevan, 2003]. We would prefer to pick subgoals for each option in the skillchain so that the overall solution trajectory is approximately hierarchically optimal [Barto and Mahadevan, 2003].

To select such subgoals, we first store the states ˆ βo in which each option o triggered βo. Then, we use dynamic programming (DP) to distribute the value of reaching the MDP's goal g to all the ˆ βos along the skill chain. This results in a value table ˜Q : S × S → R that can be used to pick a subgoal sg for the current option ot from state st: sg = argmaxs∈ˆ βot ˜Q(st, s). The quality of the resulting sub-goals depends on how well ˆ βo approximates βo. If it is a perfect approximation, this DP algorithm yields the hierarchically optimal solution; otherwise, it yields a near-optimal solution. For more details, please refer to Appendix A1.

3.3 Learning Robust Option Policies

Finally, we consider the third component of an option: its policy. Given the number of components simultaneously being learned in hierarchical algorithms, policy learning must be highly stable for the agent to succeed. Although modelfree methods are commonplace for learning option policies, model-based methods are often more stable and sampleefficient [Deisenroth and Rasmussen, 2011].

We therefore propose learning option policies using modelbased RL. We follow Nagabandi et al. [2018] to learn a dynamics model fξ. However, Equation 1 is insufficient for good action-selection in sparse reward problems. So, we solve the following infinite-horizon optimization problem and then execute the first action [Lowrey et al., 2019]:

We follow the same procedure as the model-free variant of our algorithm to learn the terminal value function Vφ.

4 Experiments

Our experiments aim to answer the following questions: 1) do the proposed improvements increase the probability with which a sequence of options can be successfully composed? 2) Does the subgoal selection algorithm approximate hierarchically optimal trajectories? 3) How does the proposed algorithm compare to flat RL and other skill-discovery algorithms?

To answer these questions, we use a test-bed comprising four continuous-control maze-navigation tasks (shown in Figure 3) involving an "ant" robot simulated using MuJoCo [Todorov et al., 2012; Duan et al., 2016; Fu et al., 2020].

Sparse vs Dense Rewards. Dense reward functions, although commonplace in RL, are often problematic because they demand cumbersome engineering [Yu et al., 2020], can lead to sub-optimal solutions [Ng et al., 1999] or reduce the problem so much that simple search might outperform RL [Mania et al., 2018]. Since hierarchies are a promising way to address the challenges of sparse rewards, we evaluate all algorithms in the sparse reward setting.

4.1 Implementation Details

We use TD3 [Fujimoto et al., 2018] and HER to learn goalconditioned value functions in all our experiments. Transitions seen by all options were used to train a single dynamics model fξ, critic Vφ, and actor πζ. Vφ and πζ were used for selecting actions in the model-free case. Only Vφ from TD3 was used in the model-based case, where we approximately solved Equation 2 for action-selection. For more details, see Appendix A4.

4.2 Evaluating Robustness

We first evaluate whether the proposed changes increase the composability of discovered options, by measuring the robustness of skill-chains constructed in Ant U-Maze.

We measure the robustness of a sequence of options as the probability that executing each option would take the agent to a state from which it could successfully execute the next option (until it finally reaches the goal). We call this the chaining probability:

where p(si ∼ βoi-1 ∈ Ioi ) represents the open-loop probability that the agent will be able to execute oi after executing option oi-1. We approximate each probability term by the empirical "success rate" of the option:

where #successes(oi-1) is the number of times option πoi-1 was able to reach βoi-1 .

We ablate our proposals by comparing the robustness of the following versions of our algorithm:

1. Baseline DSC: The deep skill chaining algorithm from Bagaria and Konidaris [2020] that we aim to improve.
2. Dual Classifiers: We add the dual classifier approach from Section 3.1 to the baseline DSC.
3. MF-Robust-DSC: We add goal-conditioned policies to (2); this is the model-free version of the algorithm from Section 3.2.
4. MB-Robust-DSC: We add model-based policies to (3); this is the version of the algorithm from Section 3.3.

Results. Figure 5 shows that each of our proposals successively increases the robustness of the discovered skill-chain. The shape of the curves warrants discussion: as the agent discovers new options, its chain probability, at first, decreases. This is for two reasons: (a) more terms between 0 and 1 are included in the product of Equation 3 and (b) when initialized, option policies are not strong enough to reach their subgoals. Over time, two factors are responsible for the increasing trend: (a) the agent has discovered as many options as it needs to solve the problem, at which point no more terms are added to the product and (b) each option's policy improves. Finally, the small absolute values on the vertical axis is due to the metric being an open-loop probability-we report the closed-loop success rate of the algorithm later in Section 4.4.

4.3 Evaluating Hierarchical Optimality

To compare the two subgoal selection strategies outlined in section 3.2, we ran the model-based variant of our algorithm on the Ant-Reacher domain. The goal state corresponds to the center of mass (CoM) of the ant being at (0, 0); the starting position of the ant is sampled uniformly from (-10, 10). The learned initiation classifiers tended to lie in approximately concentric circles around the goal state (visualized in Figure 1 of the Appendix). After both algorithm variants were trained for 1000 episodes, they were evaluated on how many steps it would take them to reach the goal when starting in the four corners of the domain {(±9, ±9)}.

Results. Robust subgoal selection often yielded subgoal states on the "other side" of the goal-if the robot was on the bottom-left of the domain, it could pick a subgoal closer to the top-right. This led to the sub-optimal trajectories shown in Figure 4a, where the ant would often over-shoot the goal. By contrast, the dynamic programming procedure picked subgoal states that were always between the agent's current state and the overall goal-leading to much more sensible, and approximately hierarchically optimal, solution trajectories (Figure 4b). Figure 4c shows that the agent using our DP algorithm for picking subgoals collected higher average rewards, further suggesting smoother overall trajectories to the goal.

4.4 Learning Curves

Our final experiment compares the following algorithms on ant U-maze, large-maze and four-rooms:

1. Flat model-free baseline: we used TD3+HER [Fujimoto et al., 2018; Andrychowicz et al., 2017] as a flat modelfree baseline, since it is a state-of-the-art method for continuous control (we used the same algorithm to learn our model-free option policies).
2. Flat finite-horizon model-based baseline: we used the model-based algorithm fromNagabandi et al. [2018] as our flat model-based baseline (we used the same algorithm to learn our model-based option policies).
3. Flat infinite-horizon model-based baseline: given that our problems are sparse-reward, we augment the modelbased baseline with TD3, which is used to learn a value function that informs action-selection (Equation 2).
4. Deep skill chaining (DSC): DSC is our HRL baseline, because we extend DSC and it outperformed other skilldiscovery methods [Bagaria and Konidaris, 2020].
5. Model-Free DSC++ (ours): the model-free variant of our algorithm described in Section 3.2.
6. Model-based DSC++ (ours): the model-based variant of our algorithm described in Section 3.3.

We report the "average success rate" metric from Andrychowicz et al. [2017]. Every 10 episodes, we ran the algorithm from a fixed start position (0, 0), checking if it could reach the goal within 1000 steps. Due to its simplicity, we use the robust subgoal selection algorithm from Section 3.3 for rolling out our goal-conditioned option policies.

Results. Figure 6 shows the average success rate of competing methods averaged over 5 random seeds. Both versions of the flat model-based baseline were unable to achieve a > 0% success rate; so we leave them out of the learning curves in Figure 6. Ant U-Maze was the only sparse-reward problem that TD3 and the baseline DSC were able to achieve a > 0% (but TD3 had to be trained for far more episodes). The proposed algorithm (shown with blue and orange curves) were easily able to outperform all baselines including DSC.

5 Conclusion

The success of skill discovery in goal-directed tasks depends on learning options that can be sequentially composed. However, robust composition is challenging because of nonstationary subgoal regions. We proposed methods that address all three components of option learning-initiation regions, termination conditions, and option policies-to learn reliably composable options. We experimentally showed that our augmentations measurably improve the robustness of discovered skills and eventually allow us to solve more challenging, long-horizon problems.

Acknowledgements

We thank Kshitij Sachan, Cam Allen, Sam Lobel, and other members of the Brown BigAI group for their suggestions. This research was supported by NSF grants 1955361, 1717569 and the DARPA Lifelong Learning Machines program under grant FA8750-18-2-0117. This research was conducted using computational resources and services at the Center for Computation and Visualization, Brown University.