Generating Adjacency-Constrained Subgoals in Hierarchical Reinforcement Learning

Hierarchical reinforcement learning (HRL) has shown great potentials in scaling up reinforcement learning (RL) methods to tackle large, temporally extended problems with long-term credit assignment and sparse rewards [39, 31, 2]. As one of the prevailing HRL paradigms, goal-conditioned HRL framework [5, 37, 20, 42, 26, 22], which comprises a high-level policy that breaks the original task into a series of subgoals and a low-level policy that aims to reach those subgoals, has recently achieved significant success. However, the effectiveness of goal-conditioned HRL relies on the acquisition of effective and semantically meaningful subgoals, which still remains a key challenge.

As the subgoals can be interpreted as high-level actions, it is feasible to directly train the high-level policy to generate subgoals using external rewards as supervision, which has been widely adopted in previous research [26, 25, 22, 20, 42]. Although these methods require little task-specific design, they often suffer from training inefficiency. This is because the action space of the high-level, i.e., the goal space, is often as large as the state space. The high-level exploration in such a large action space results in inefficient learning. As a consequence, the low-level training also suffers as the agent tries to reach every possible subgoal produced by the high-level policy.

One effective way for handling large action spaces is action space reduction or action elimination. However, it is difficult to perform action space reduction in general scenarios without additional information, since a restricted action set may not be expressive enough to form the optimal policy. There has been limited literature [43, 41, 19] studying action space reduction in RL, and to our knowledge, there is no prior work studying action space reduction in HRL, since the information loss in the goal space can lead to severe performance degradation [25].

In this paper, we present an optimality-preserving high-level action space reduction method for goal-conditioned HRL. Concretely, we show that the high-level action space can be restricted from the whole goal space to a $k$-step adjacent region centered at the current state. Our main intuition is depicted in Figure 3: distant subgoals can be substituted by closer subgoals, as long as they drive the low-level to move towards the same “direction”. Therefore, given the current state $s$ and the subgoal generation frequency $k$, the high-level only needs to explore in a subset of subgoals covering states that the low-level can possibly reach within $k$ steps. By reducing the action space of the high-level, the learning efficiency of both the high-level and the low-level can be improved: for the high-level, a considerably smaller action space relieves the burden of exploration and value function approximation; for the low-level, adjacent subgoals provide a stronger learning signal as the agent can be intrinsically rewarded with a higher frequency for reaching these subgoals. Formally, we introduce a $k$-step adjacency constraint for high-level action space reduction, and theoretically prove that the proposed constraint preserves the optimal hierarchical policy in deterministic MDPs. Also, to practically implement the constraint, we propose to train an adjacency network so that the $k$-step adjacency between all states and subgoals can be succinctly derived.

We benchmark our method on various tasks, including discrete control and planning tasks on grid worlds and challenging continuous control tasks based on the MuJoCo simulator [40], which have been widely used in HRL literature [26, 22, 25, 11]. Experimental results exhibit the superiority of our method on both sample efficiency and asymptotic performance compared with the state-of-the-art HRL approach HIRO [26], demonstrating the effectiveness of the proposed adjacency constraint.

We consider a finite-horizon, goal-conditioned Markov Decision Process (MDP) defined as a tuple $\langle\mathcal{S},\mathcal{G},\mathcal{A},\mathcal{P},\mathcal{R},\gamma\rangle$, where $\mathcal{S}$ is a state set, $\mathcal{G}$ is a goal set, $\mathcal{A}$ is an action set, $\mathcal{P}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}$ is a state transition function, $\mathcal{R}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ is a reward function, and $\gamma\in[0,1)$ is a discount factor. Following prior work [20, 42, 26], we consider a framework comprising two hierarchies: a high-level controller with policy $\pi^{h}_{\theta_{h}}(g|s)$ and a low-level controller with policy $\pi^{l}_{\theta_{l}}(a|s,g)$ parameterized by two function approximators, e.g., neural networks with parameters $\theta_{h}$ and $\theta_{l}$ respectively, as shown in Figure 3. The high-level controller aims to maximize the external reward and generates a high-level action, i.e., a subgoal $g_{t}\sim\pi^{h}_{\theta_{h}}(g|s_{t})\in\mathcal{G}$ every $k$ time steps when $t\equiv 0\,(\mathrm{mod}\ k)$, where $k>1$ is a pre-determined hyper-parameter. It modulates the behavior of the low-level policy by intrinsically rewarding the low-level for reaching these subgoals. The low-level aims to maximize the intrinsic reward provided by the high-level, and performs a primary action $a_{t}\sim\pi^{l}_{\theta_{l}}(a|s_{t},g_{t})\in\mathcal{A}$ at every time step. Following prior methods [26, 1], we consider a goal space $\mathcal{G}$ which is a sub-space of $\mathcal{S}$ with a known mapping function $\varphi:\mathcal{S}\rightarrow\mathcal{G}$. When $t\not\equiv 0\,(\mathrm{mod}\ k)$, a pre-defined goal transition process $g_{t}=h(g_{t-1},s_{t-1},s_{t})$ is utilized. We adopt directional subgoals that represent the differences between desired states and current states [42, 26], where the goal transition function is set to $h(g_{t-1},s_{t-1},s_{t})=g_{t-1}+s_{t-1}-s_{t}$. The reward function of the high-level policy is defined as:

which is the accumulation of the external reward in the time interval $[kt,kt+k-1]$.

While the high-level controller is motivated by the environmental reward, the low-level controller has no direct access to this external reward. Instead, the low-level is supervised by the intrinsic reward that describes subgoal-reaching performance, defined as $r_{t}^{l}=-D\left(g_{t},\varphi(s_{t+1})\right)$, where $D$ is a binary or continuous distance function. In practice, we employ Euclidean distance as $D$.

The goal-conditioned HRL framework above enables us to train high-level and low-level policies concurrently in an end-to-end fashion. However, it often suffers from training inefficiency due to the unconstrained subgoal generation process, as we have mentioned in Section 1. In the following section, we will introduce the $k$-step adjacency constraint to mitigate this issue.

In this section, we provide our theoretical results and show that the optimality can be preserved when learning a high-level policy with $k$-step adjacency constraint. We begin by introducing a distance measure that can decide whether a state is “close” to another state. In this regard, common distance functions such as the Euclidean distance are not suitable, as they often cannot reveal the real structure of the MDP. Therefore, we introduce shortest transition distance, which equals to the minimum number of steps required to reach a target state from a start state, as shown in Figure 3. In stochastic MDPs, the number of steps required is not a fixed number, but a distribution conditioned on a specific policy. In this case, we resort to the notion of first hit time from stochastic processes, and define the shortest transition distance by minimizing the expected first hit time over all possible policies.

The shortest transition distance is determined by a policy that connects states $s_{1}$ and $s_{2}$ in the most efficient way, which has also been studied by several prior work [10, 8]. This policy is optimal in the sense that it requires the minimum number of steps to reach state $s_{2}$ from state $s_{1}$. Compared with the dynamical distance [15], our definition here does not rely on a specific non-optimal policy. Also, we do not assume that the environment is reversible, i.e., $d_{\mathrm{st}}(s_{1},s_{2})=d_{\mathrm{st}}(s_{2},s_{1})$ does not hold for all pairs of states. Therefore, the shortest transition distance is a quasi-metric as it does not satisfy the symmetry condition. However, this limitation does not affect the following analysis as we only need to consider the transition from the start state to the goal state without the reversed transition.

Given the definition of the shortest transition distance, we now formulate the property of an optimal (deterministic) goal-conditioned policy $\pi^{*}:\mathcal{S}\times\mathcal{G}\rightarrow\mathcal{A}$ [36]. We have:

where $\varphi^{-1}:\mathcal{G}\rightarrow\mathcal{S}$ is the known inverse mapping of $\varphi$. We then consider the goal-conditioned HRL framework with high-level action frequency $k$. Different from a flat goal-conditioned policy, in this setting the low-level policy is required to reach the subgoals with $k$ limited steps. As a result, only a subset of the original states can be reliably reached even with an optimal goal-conditioned policy. We introduce the notion of $k$-step adjacent region to describe the set of subgoals mapped from this reachable subset of states.

Harnessing the property of $\pi^{*}$, we can show that in deterministic MDPs, given an optimal low-level policy $\pi^{l*}=\pi^{*}$, subgoals that fall in the $k$-step adjacent region of the current state can represent all optimal subgoals in the whole goal space in terms of the induced $k$-step low-level action sequence. We summarize this finding in the following theorem.

Theorem 1 suggests that the $k$-step low-level action sequence generated by an optimal low-level policy conditioned on a distant subgoal can be induced using a subgoal that is closer. Naturally, we can generalize this result to a two-level goal-conditioned HRL framework, where the low-level is actuated not by a single subgoal, but by a subgoal sequence produced by the high-level policy.

Theorem 1 and 2 show that we can constrain the high-level action space to state-wise $k$-step adjacent regions without the loss of optimality. We formulate the high-level objective incorporating this $k$-step adjacency constraint as:

where $r_{kt}^{h}$ is the high-level reward defined by Equation (1) and $g_{kt}\sim\pi^{h}_{\theta_{h}}(g|s_{kt})$.

In practice, Equation (7) is hard to optimize due to the strict constraint. Therefore, we employ relaxation methods and derive the following un-constrained optimizing objective:

where $H(x,k)=\max(x/k-1,0)$ is a hinge loss function and $\eta$ is a balancing coefficient.

One limitation of our theoretical results is that the theorems are derived in the context of deterministic MDPs. However, these theorems are instructive for practical algorithm design in general cases, and the deterministic assumption has also been exploited by some prior works that investigate distance metrics in MDPs [15, 3]. Also, we note that many real-world applications can be approximated as environments with deterministic dynamics where the stochasticity is mainly induced by noise. Hence, we may infer that the adjacency constraint could preserve a near-optimal policy when the magnitude of noise is small. Empirically, we show that our method is robust to certain types of stochasticity (see Section 5 for details), and we leave rigorous theoretical analysis for future work.

Although we have formulated the adjacency constraint in Section 3, the exact calculation of the shortest transition distance $d_{\mathrm{st}}(s_{1},s_{2})$ between two arbitrary states $s_{1},s_{2}\in\mathcal{S}$ remains complex and non-differentiable. In this section, we introduce a simple method to collect and aggregate the adjacency information from the environment interactions. We then train an adjacency network using the aggregated adjacency information to approximate the shortest transition distance $d_{\mathrm{st}}(s_{1},s_{2})$ in a parameterized form, which enables a practical optimization of Equation (8).

We have presented our method of Hierarchical Reinforcement learning with $k$-step Adjacency Constraint (HRAC). Our experiments are designed to answer the following questions: (1) Can HRAC promote the generation of adjacent subgoals? (2) Can HRAC improve the sample efficiency and overall performance of goal-conditioned HRL? (3) Can HRAC outperform other strategies that may also improve the learning efficiency of hierarchical agents, e.g., hindsight experience replay [1]?

Effectively learning policies with multiple hierarchies has been a long-standing problem in RL. Goal-conditioned HRL [5, 37, 20, 42, 26, 22] aims to resolve this problem with a framework that separates high-level planning and low-level control using subgoals. Recent advances in goal-conditioned HRL mainly focus on improving the learning efficiency of this framework. Nachum et al. [26, 25] proposed an off-policy correction technique to stabilize training, and addressed the problem of goal space representation learning using a mutual-information-based objective. However, the subgoal generation process in their approaches is unconstrained and supervised only by the external reward, and thus these methods may still suffer from training inefficiency. Levy et al. [22] used hindsight techniques [1] to train multi-level policies in parallel and also penalized the high-level for generating subgoals that the low-level failed to reach. However, their method has no theoretical guarantee, and they directly obtain the reachability measure from the environment, using the environmental information that is not available in many scenarios. There are also prior works focusing on unsupervised acquisition of subgoals based on potentially pivotal states [23, 18, 21, 34, 32, 17]. However, these subgoals are not guaranteed to be well-aligned with the downstream tasks and thus are often sub-optimal.

Several prior works have constructed an environmental graph for high-level planning used search nearby graph nodes as reachable subgoals for the low-level [34, 8, 17, 44]. However, these approaches hard-coded the high-level planning process based on domain-specific knowledge, e.g., treat the planning process as solving a shortest-path problem in the graph instead of a learning problem, and thus are limited in scalability. Nasiriany et al. [29] used goal-conditioned value functions to measure the feasibility of subgoals, but a pre-trained goal-conditioned policy is required. A more general topic of goal generation in RL has also been studied in the literature [12, 28, 33]. However, these methods only have a flat architecture and therefore cannot successfully solve tasks that require complex high-level planning.

Meanwhile, our method relates to previous research that studied transition distance or reachability [30, 34, 35, 10, 15]. Most of these works learn the transition distance based on RL [30, 10, 15], which tend to have a high learning cost. Savinov et al. [34, 35] proposed a supervised learning approach for reachability learning. However, the metric they learned depends on a certain policy used for interaction and thus could be sub-optimal compared to our learning method. There are also other metrics that can reflect state similarities in MDPs, such as successor represention [4, 21] that depends on both the environmental dynamics and a specific policy, and bisimulation metrics [9, 3] that depend on both the dynamics and the rewards. Compared to these metrics, the shortest transition distance depends only on the dynamics and therefore may be seamlessly applied to multi-task settings.

We present a novel $k$-step adjacency constraint for goal-conditioned HRL framework to mitigate the issue of training inefficiency, with the theoretical guarantee of preserving the optimal policy in deterministic MDPs. We show that the proposed adjacency constraint can be practically implemented with an adjacency network. Experiments on several testbeds with discrete and continuous state and action spaces demonstrate the effectiveness and robustness of our method.

As one of the most promising directions for scaling up RL, goal-conditioned HRL provides an appealing paradigm for handling large-scale problems. However, some key issues involving how to devise effective and interpretable hierarchies remain to be solved, such as how to empower the high-level policy to learn and explore in a more semantically meaningful action space [27], and how to enable the subgoals to be shared and reused in multi-task settings. Other future work includes extending our method to tasks with high-dimensional state spaces, e.g., by encompassing modern representation learning schemes [16, 25, 38], and leveraging the adjacency network to improve the learning efficiency in more general scenarios.

This work may promote the research in the field of HRL and RL, and has potential real-world applications such as robotics. The main uncertainty of the proposed method might be the fact that the RL training process itself is somewhat brittle, and may break in counterintuitive ways when the reward function is misspecified. Also, since the training data of RL heavily depends on the training environments, designing unbiased simulators or real-world training environments is important for eliminating the biases in the data collected by the agents.

This work was supported in part by the National Natural Science Foundation of China under Grant 61671266, Grant 61836004, Grant 61836014 and in part by the Tsinghua-Guoqiang research program under Grant 2019GQG0006. The authors would also like to thank the anonymous reviewers for their careful reading and their many insightful comments.