HILONet: Hierarchical Imitation Learning from Non-Aligned Observations

There are two general groups of ILfO: model-based algorithms, and model-free algorithms[6]. Model-based approaches to ILfO are characterized by the fact that they learn some dynamics model during the imitation process. As for model-based part, [7] have proposed an algorithm, behavioural cloning from observation(BCO), that is learned an inverse dynamics model using an exploratory policy, and then uses that model to infer the actions from the demonstrations and to use behaviour clone[8] to learn. There is also another ILfO approach that learns and uses forward dynamics like imitating latent policies from observation (ILPO) [9].

In this work, we mostly discuss model-free algorithms. Adversarial approaches to ILfO are inspired by the generative adversarial imitation learning (GAIL)[10] algorithm, but takes ${(o_{t},o_{t+1})}$ instead of ${(o_{t},a_{t})}$ in GAIL. This is called GAILfO[11]. There are other adversarial approaches like [12], [13].

Another type of model-free algorithm is reward engineering. It means that, based on the expert demonstrations, a manually-designed reward function is used to find imitation policies via RL. Reward engineering methods use Euler distance of the same time step’s policy observation and expert observation to design rewards, like in TCN and [14]. Another approach of this type is [15] in which the algorithm uses a formulation similar to shuffle-and-learn [16] to train a classifier that learns the order of frames in the demonstration.

There are several RL approaches to learning hierarchical policies[17]; [18]; [19]. However, these have many strict limits and are not off-policy training methods. Recently popular works like HIRO[20], Option-Critic[21] and FeUdal Networks[22]have achieve quite good performance. Especially, HAC[23] using hindsight[24] to overcome non-stationarity in HRL and makes off-policy method have a better performance. In this work, we also use hindsight in a different way to overcome non-stationarity in the form of imitation learning. As for using HRL in imitation learning, there are few works, too. Like [5] using HRL to choose which observation of the expert trajectory should be jumped. However, it still follows a single trajectory step-by-step essentially.

In the hierarchical framework, we consider agent with a natural two-level hierarchy. The high level corresponds to choosing sub-goals, and the low level corresponds to achieve those sub-goals. This structure is typical in past works[25].

In standard Markov Decision Process (MDP), one agent sequentially chooses an action $a_{t}$ according to a policy $\pi(a|o)$ based on the observation $o_{t}$ at time t. After taking the action $a_{t}$, observation $o_{t}$ transforms to the next observation $o_{t+1}$ according to the transition probability which satisfies Markov property and is entirely determined by the observation-action pair one time step before, i.e. $o_{t+1}\sim p(o_{t+1}|o_{t},a_{t})$. Then the agent receives a scalar reward signal $r(o_{t},a_{t})$ from the environment. Deep Reinforcement Learning is one kind of deep learning algorithms that finds a policy $\pi$ which can extract features with deep neural network and maximizes the expected discounted cumulative reward in one episode, i.e. $R(o_{t})=E\left[\sum_{t}\gamma^{t}r(o_{t},a_{t})\right]$, where $\gamma$ is a discount factor.

As we use the off-policy learning algorithm, we also use Hindsight Experience Replay(HER)[24]. HER is a data augmentation technique that can accelerate learning in sparse reward tasks. HER first creates copies of the observation, action, reward, next observation, goal transitions that are created in traditional off-policy RL. In the copied transitions, the original goal element is replaced with a observation that was achieved during the episode, which guarantees that at least one of the HER transitions will contain the sparse reward. This method can help us to overcome non-stationarity in HRL.

Policy gradient methods maximize the expected cumulative reward by estimating the performance gradient with respect to the policy parameter vector $\theta$: $\nabla_{\theta}J(\pi_{\theta})$, and updating the policy parameter vector with gradient ascent.

As the original version of policy gradient algorithm, REINFORCE [26] tends to be of high variance due to the gradient estimation with Monte Carlo method:

where $R_{t}$ represents the cumulative reward from time t to the end of one episode. Actor-critic methods use the value function $V(o_{t})$, action-value function $Q(o_{t},a_{t})$ or advantage function $A(o_{t},a_{t})=Q(o_{t},a_{t})-V(o_{t})$ to substitute for the cumulative reward $R_{t}$, so as to reduce the variance of gradient estimation and improve the performance of policy gradient methods. Policy gradient methods maximize the expected cumulative reward by estimating the performance gradient with respect to the policy parameter vector $\theta$: $\nabla_{\theta}J(\pi_{\theta})$, and updating the policy parameter vector with gradient ascent.

For deterministic policy such as DPG [27] and DDPG [28], according to the deterministic policy gradient theorem [27], the gradient of the objective $J(\theta)$ can be estimated as:

In order to show the algorithm more clearly, we list all the main notations used in our method below. We first define $D=\{\tau_{1},\tau_{2},...,\tau_{N}\}$ means all $N$ trajectories we used in training process. $\tau_{i}=\{d_{1}^{i},d_{2}^{i},...,d_{T_{i}}^{i}\}$ is one trajectory of demonstrations. $d_{j}^{i}$ means the observation of time step $j$ in the number $i$ trajectory of demonstrations. $T_{i}$ means the length of trajectory $i$. Then, we define $I(d_{j}^{i})$ to represent the index of $d_{j}^{i}$ in its own trajectory.

In our approach, the whole policy is consisted of two part, high level policy $\pi_{high}(o_{g}|o_{t};\theta_{h})$ and low level policy $\pi_{low}(a|o_{t},o_{g};\theta_{l})$, where $o_{g}$ is sub-goal chosen from expert trajectory observations for low level policy, $o_{t}$ is current observation. We use DDPG algorithm to train both high level policy and low level policy.

The high level policy is charged for choosing a feasible demonstrated observation depending on current observation so low level policy is capable of achieving that sub-goal in certain steps, i.e. five steps in our experiment. To represent the $o_{g}$ among $D$, we select a 2-dim action space for high level policy. The high level policy’s action consists of two rates between 0 and 1, the first dimension of action stands for which trajectory in $D$ is chosen, and second action dimension is the index of observation chosen in the trajectory. In this way, the sub-goal can be formed as:

where the $N$ is the number of all demonstrated trajectories and $T_{i}$ means the length of trajectory $i$.

The low level policy is focused on interacting with the environment and find a way to achieve the sub-goal provided by the high level policy in certain steps. It takes $\{o_{g},o_{t}\}$ as input and output $a_{t}$ as inter-action that interacts with the environment. The low level policy can be viewed as

In this way, the low level policy and the high level policy together form the overall strategy. By flexibly selecting the observation in the demonstration as the sub-goal, the target task can be completed step-by-step. The structure of our overall policy is shown in Fig. 1. The training process is shown in Algorithm. 1.

The rewards for both high level and low level policy are designed based on observation information as there is no action label available. For low level policy, the insight is simple, that we want the reward to encourage the agent to achieve sub-goals. We can use the Euler distance of goal observation and current observation to do so directly. However, this reward can not reflect whether the sub-goal is achieved. For example, the reward increases similarly when agent approaching the sub-goal from a far distance or when agent is close to the target but missing the target slightly. To encourage agent achieving sub-goal, we add a sparse reward $r$ that is given only when the agent achieves the current sub-goal. We define if $|o_{g}-o_{t}|<\epsilon$ then we consider agent has achieved the sub-goal. The overall reward of low level policy can be viewed as:

As for the high level policy, we consider it should guide the low level policy to accomplish the specific tasks. In this way, the high level policy must do two tasks, finding a feasible sub-goal that agent can achieve and the sub-goal should gradually solve the specific tasks. The reward for the high level policy is designed based on these two proposals. First, we naturally use a sparse reward that given only when low level policy achieved the sub-goal. Then we add another reward related with which phase agent is right now. This reward can be evaluated by $I(o_{g})=I(d_{j}^{i})$. Because it represents the index of the reached expert state in the entire expert sequence. If the value of $I(o_{g})$ is getting larger, means the agent is getting closer to the final goal. And since $I(o_{g})$ is normalized between 0 and 1, it can be used among all trajectories even if they have the different number of steps to the end. If we output sub-goal every $\Delta t$, we can use

as the reward to guide agent. Furthermore, we define $I(o_{g})=0$ if $o_{t}$ is not in expert trajectory, which can punish agent when it deviates from the expert trajectory. The overall reward of high level policy can be viewed as:

where $\alpha$ is the multipliers to control the optimization ratio of these two parts of the reward. And here we propose,

Theorems 1: By changing $\alpha$, we can control the behavior pattern of the learned policy, the higher $\alpha$ is, the learned policy would focus on following the trajectories as closely as possible. And the lower $\alpha$ is, the learned policy would focus on exploring more novel paths to the goal position.

$Proof$ Firstly, we can have the optimal value at a state is given by the state-value function

where

we consider two optimum policies that can solve the tasks $\pi_{1}$ and $\pi_{2}$. Both policies are well-trained, which means the low level policies is the same, only high level policies are different. $\pi_{1}$ choose a path to reach the goal observation exactly as the expert does, while $\pi_{2}$ choose a total different path but reach the same goal position. The state-value function of these two policy are:

We substitute our reward $r_{high}$ into Eq. 10 to obtain

We use Eq. 11 minus Eq. 12, we have

Then we have

As

We have

In this way, we prove that $\Delta V^{*}\left(o_{t}\right)$ is monotonically increasing with $\alpha$, when $\alpha$ is high, the return distinguish between $\pi_{1}$ and $\pi_{2}$ are large, which pushes the agent to follow the expert as close as possible. However, when the $\alpha$ is low, there is not much difference in the return of $\pi_{1}$ and $\pi_{2}$, which makes the agent tend to explore more novel path, as the novel path can increase the chance of obtaining rewards.

In summary, our hierarchical framework method has three advantages. First of all, comparing to another reward engineering imitation learning from observation methods, our method can plan dynamically thus it can solve the non-time-aligned problem. Furthermore, the reward structure of our method can adopt in all kinds of environments, no matter the tasks are described by a single goal observation or a sequence of key observations. Additionally, our method can use information from multiple trajectories simultaneously, while most reward engineering methods can only imitate one trajectory if it imitates an expert step-by-step.

Secondly, our method is based on reward engineering, so comparing with adversarial methods, our method has access to observation information directly, which can offer more dense reward and will not miss any important information in demonstrated trajectories.

The third advantage is that using a hierarchical framework policy can naturally divide a complex task into two more straightforward tasks, which will accelerate learning in sequential decision-making tasks.

In this section, we will introduce three methods that overcome the non-stationarity in the hierarchical framework so that we can increase sample efficiency.

We choose MountainCar, LunarLander, Swimmer in Gym[30] and Reacher, 3Dball in ml-agents[31]. All environments are shown in Fig. 2. These five environments are all non-time-aligned and represent different characteristics, including two kinds of tasks can be effectively described by a single goal observation or a sequence of key observations rather than a single goal. Specially, the MountainCar and LunarLander can be viewed as a single goal environment, while the Swimmer and 3Dball can be viewed as a sequence of goal environment. And Reacher is more complex that it can be viewed as a mixing environment. More details about environments will discuss below. Experiments in these environments can show the universality of our method.

MountainCar: The goal is to have the car reach the target point. The target is on top of a hill on the right-hand side of the car. If the car reaches it or goes beyond, the episode terminates. This means the number of steps of each episode is changing, which is a typical non-time-aligned environment. On the left-hand side, there is another hill. Climbing this hill can be used to gain potential energy and accelerate towards the target. On top of this second hill, the car cannot go further than a position equal to -1, as if there was a wall. Hitting this limit does not generate a penalty.

LunarLander: The goal is to land on a specific position without crashing. The landing pad is always at coordinates (0,0). If lander moves away from the landing pad, it loses reward back. The episode finishes if the lander crashes or comes to reset, receiving additional -100 or +100 points. Landing outside the landing pad is possible. Fuel is infinite, so an agent can learn to fly and then land on its first attempt. These feature make sure that the agent can choose different path to the goal position, which is also a typical non-time-aligned environment.

Reacher: The agent must move their hand to a constantly moving goal location, and keep it there. The agent is a double-jointed arm which can move to target locations. The target location is a constantly moving location in 3D space, which makes the agent must follow its trajectory. This environment is different from the other environments. The moving target points bring an enormous challenge, as the first phrase of reaching the goal position can be viewed as a single-goal task and the second phrase of keeping moving within the goal area can be viewed as a sequenced-goal task.

3Dball: The agent must balance the ball on it’s head for as long as possible. This goal makes the environment different from the single-goal ones, as it not a reaching given goal point task which the goal point is usually the last frame of demonstration. This task needs to follow a special action pattern to keep a requested status, which is not directly related to the last frame of demonstration.

Swimmer: This task involves a 3-link swimming robot in a viscous fluid, where the goal is to make it swim forward as fast as possible, by actuating the two joints. Like 3Dball, this task requires the agent to arrive at the orderly goal frames in order to achieve high speed.

In this part, we evaluate the effect our Hierarchical Imitation Learning From Observation(HILONet) in these five environments. For comparison, we evaluate several state-of-the-art imitation learning algorithms, including adversarial methods like GAIL, which using a specific class of cost functions. This allows for the use of generative adversarial networks in order to do apprenticeship learning. And GAILfO[11], which is similar to GAIL but only using observations. Meanwhile, we evaluate a baseline reward engineering method, which imitates the expert observation step-by-step. This method learns to reach the observation of the same time step of the demonstrated trajectory at each time step. We call it time-sequential reward engineering(TSRE). Notable, our method, GAILfO and reward engineering baseline are using only expert observations, but GAIL have access to the demonstrator’s actions.

We implement HILONet using DDPG algorithm. In the implementation of DDPG, the policies are all parameterized by a two-layer full connected network with 64 units per layer and “relu” active function and are initialized randomly. The high level policy acts every five steps. The $\alpha$ is 0.5 in single-goal task and 10 in the sequenced-goal task. We use precisely the same parameters for all compared algorithms. As for demonstrations, we use 20 trajectories in MountainCar, 30 trajectories in LunarLander, Swimmer, 3Dball and Reacher. However, TSRE can only use one of these trajectories as it can only follow one expert step-by-step. All demonstrations are collected by pre-trained expert policies which are trained with extinct reward. All tests are evaluated over three seeds and using 20 or 30 experts’ trajectories in all environments. For all experiments, we utilize the environmental return as the performance of each method, which is the y-axis in all plots.

In this setting, we test how different ways of overcoming non-stationarity affect the agent’s performance. Firstly, we test our method training without hindsight transition replacement in both high level policy and low level policy. Then, we find out how the time delay method affects the training process. At last, we test our method with a bigger replay buffer size, e.g. twice as big as the original one.

These results in Fig. 10, Fig. 11 and Fig. 12 shows that all these three ways that we proposed to overcome non-stationarity in the hierarchical framework works. Especially, methods without hindsight transition replacement or time delay training can hardly even get out of ground level. As for using a bigger replay buffer size, the influence is not as huge as others. However, we can still observe a significant decay. The reason for this is that hindsight transition replacement or time delay training changes the distribution of the sample, so it has a greater impact on the learned policy. In contrast, changing the size of replay buffer only changes the learning hyperparameters, and the impact will not be so large.