Hashing over Predicted Future Frames for Informed Exploration of Deep Reinforcement Learning

1 Introduction

Reinforcement learning (RL) involves an agent progressively interacting with an initially unknown environment, in order to learn an optimal policy with the objective of maximizing the cumulative rewards collected from the environment [Sutton and Barto, 1998]. Throughout the learning process, the RL agent alternates between two primal behaviors: exploration - to try out novel states that could potentially lead to high future rewards; and exploitation - to perform greedily according to the learned knowledge. In the past, exploitation of learned knowledge has been well studied, while how to efficiently explore through the state space is still remained as a critical challenge, especially for deep RL domains.

In deep RL domains, a state can be represented by lowlevel sensory inputs, such as image pixels [Mnih et al., 2015], which is often high-dimensional or/and continuous. Thus, the state space for deep RL is huge and often intractable for searching. When performing exploration through such a huge state space, most existing single-task (e.g., [Wang et al., 2016; Schaul et al., 2016; Bellemare et al., 2016]) and multi-task (e.g., [Parisotto et al., 2016; Rusu et al., 2016; Yin and Pan, 2017]) deep RL approaches adopt a simple exploration heuristic, ϵ-greedy strategy, where the RL agent takes a random action with a probability of ϵ, e.g., via uniform sampling for discrete-action domains [Sutton and Barto, 1998; Mnih et al., 2015] or corrupting action with i.i.d. Gaussian noise for continuous-action domains [Lillicrap et al., 2016]. In such a way, the agent explores the state space undirectedly [Thrun, 1992], i.e., without incorporating any meaningful knowledge about the environment. Such exploration heuristic turns out to work well in simple problem domains but fails to handle more challenging domains, such as those with extremely sparse rewards that result in exponentially increasing state space.

Unlike the undirected exploratory behavior for agents using ϵ-greedy strategy, when human beings are intending to explore an unfamiliar task domain, one often actively applies domain knowledge for the task, accounts for the state space that has been less frequently visited, and intentionally tries out actions that lead to novel states. In this work, we aim to mimic such exploratory behaviors to improve upon the ϵ-greedy strategy with random action selection, and come up with a more efficient informed exploration framework for deep RL agents. On the one hand, we develop agent's knowledge on the environment and make it able to predict the future trajectories. On the other hand, we integrate the developed knowledge with hashing techniques over the high-dimensional state space in order to make the agent be able to realistically evaluate the novelty for the predicted future trajectories.

Specifically, in our proposed informed exploration framework, first, we train an action-conditional prediction model to predict future frames given a state-action pair. Second, to perform hashing over the high-dimensional state space seen by the agent, we train a deep convolutional autoencoder to generate high-level features for the state and apply localitysensitive hashing (LSH) [Charikar, 2002] on the high-level state features to generate binary codes to represent each state. However, the learned hashing function is counting over the actually seen states, while we need to query the counts for the predicted future frames to compute their novelty. Hence, we introduce an additional training phase for the autoencoder to match the hash codes for the predicted frames with that of their corresponding ground-truth frames (i.e., the actually seen frames). In this way, we are able to utilize the environment knowledge and hashing techniques over the high-dimensional states to generate a reliable novelty evaluation metric for the future direction pointed by each action given a state.

2 RelatedWork

Recently, works on enhancing the exploration behavior of deep RL agents have demonstrated great potential in improving the performance of various challenging RL task domains. In [Mnih et al., 2016], asynchronous training techniques are adopted and multiple agents are created to perform gradientbased learning to update the model parameters separately in the Atari 2600 domain. In [Osband et al., 2016], an ensemble of Q-functions is trained to reduce the bias for the values being approximated and increases the exploration depth in the Atari 2600 domain. In [Houthooft et al., 2016], an exploration strategy based on maximizing the information gain of the agent's belief about the environment dynamics is adopted for tasks with continuous states and actions. In [Achiam and Sastry, 2017], the KL-divergence between the probability obtained from a learned dynamics model before and after updated by the experience is used to measure the surprise over the experience. In [Bellemare et al., 2016; Tang et al., 2017; Martin et al., 2017], the novelty of a state is measured based on count-based mechanisms, and reward shaping is performed by adding a reward bonus term inferred from the value of counts. For all aforementioned approaches, the exploration strategy is incorporated either in the function approximation or during the optimization process, and the agent still needs to randomly choose action to explore without relying on any knowledge about the model. In this work, we aim to conduct informed exploration by utilizing the model-based knowledge to derive a deterministic choice of action for the agent to explore.

Exploration with Deep Prediction Models Recent works aiming to incentivize exploration via deep prediction models have shown promising results for deep RL domains. In [Stadie et al., 2015], an autoencoder model is trained jointly with the policy model, and the reconstruction error from the autoencoder is used to determine the rareness of a state. In [Pathak et al., 2017], the prediction loss for the transited state at the feature level is used to infer the novelty of a state. In [Ostrovski et al., 2017], a pixelCNN is trained jointly with the policy model as a density model for the state. The prediction gain of a state is measured as the difference of the state density given by the pixelCNN after and before observing that state. In the above approaches, the novelty of a state is measured by the loss or estimation output of another model, which is not exact statistics. In our work, we use the counts derived from hashing over the state space to reliably infer the novelty of a state. In [Oh et al., 2015], which is a work mostly related to ours, an action-conditional prediction model is trained to predict the future frame given a state-action pair. Then they compute the Gaussian kernel distance between each predicted future frame and a set of history frames, and inform the agent to take the action that leads to the frames which are most dissimilar compared to a window of recently seen frames. In our work, we use the same frame prediction architecture as in [Oh et al., 2015], but our work additionally performs hashing over the predicted future frames to reliably infer the novelty of a possible action direction for the agent to explore.

Hashing for Deep RL Domain Running RL algorithms on the discretized features yields faster learning and promising performance. It is shown that the latent features learned by autoencoder trained in an unsupervised manner is of great promise to efficiently discretize the high-dimensional state space [Blundell et al., 2017]. In [Tang et al., 2017], the state space for Atari 2600 domain is first discretized using the latent features derived from an autoencoder model. Then hashing is performed to encourage exploration by computing a reward bonus term in a form like MBIE-EB [Strehl and Littman, 2008]. Our work also introduces hashing over the state space based on latent features trained from deep autoencoder model, but the exploration mechanism is significantly different from [Tang et al., 2017]. First, in our work, we count over the actually seen image frames, but query the hash for the predicted frames. Second, in their approach, the reward bonus inferred from hashing is directly added to the function approximation target, which silently influences the previous states backwards through Bellman equation. But in our work, the count is used for informed exploration, which does not have direct influence on the approximated Q-values.

3 Methodology

3.1 Notations

In this paper, we consider a discounted finite-horizon Markov Decision Process (MDP) with discrete actions. Formally, it is defined by a tuple (S, A, P, R, γ), where S is a set of states which could be high-dimensional or continuous, A is a set of actions, P is a state transition probability distribution with P(s′ |s, a) specifying the probability for transiting to state s′ after issuing action a at state s, R is a reward function mapping each state-action pair to a reward in R, and γ ∈ [0, 1] is a discount factor. The goal of the RL agent is to learn a policy π that maximizes the expected cumulative future rewards given the policy: Eπ[∑Tt=0 γ tR(st, at)]. In the context of deep RL, at each step t, an RL agent receives a state observation St ∈ Rr×m×n , where r is the number of consequent frames to represent a state, and m×n is the dimension for each frame. The agent selects an action at ∈ A among all the l possible choices, and receives a reward rt ∈ R.

3.2 Informed Exploration Framework

We propose an informed exploration framework to mimic the exploratory behavior of human beings under an unfamiliar task domain. The overall exploration decision making process is illustrated in Figure 1.

Generally, the RL agent no longer randomly selects an action to explore without incorporating any domain knowledge. Instead, we aim to let the agent intentionally select the action that leads to the least frequent future states and thus explore the state space in an informed and deterministic manner. To this end, we build the capability of the RL agent on performing the following two tasks: 1) predicting over future transitions, and 2) evaluating the visiting frequency for those predicted future frames.

Learning Transition Model with Prediction Network

The architecture for action-conditional prediction is shown in Figure 2 (up). To be specific, we train a deep prediction model f : (St, at) → St+1 to make the agent able to predict over the future transitions given a state-action pair. The state input St is a set of r recent image frames, and the action input at is represented by at ∈ Rl , which is a one-hot vector, where l is the number of actions for the task domain. To predict a new state, the model predicts one single frame at a time, denoted as ˆ s ∈ Rm×n . The new state St+1 is formed by concatenating the predicted new frame with the most recent r-1 frames. We adopt the action-conditional transformation as proposed in [Oh et al., 2015] to form a joint feature for the state input and the action input. Specifically, the state input is first passed through three stacked convolutional layers to form a feature vector hst ∈ Rh . Then the state feature hst and the one-hot action feature at perform a linear transformation by multiplying with their corresponding transformation matrix Ws t ∈ Rk×h and Wa t ∈ Rk×l . After the linear transformation, both features are shaped with the same dimensionality. Then the features for the state and action after the linear transformation performs a multiplicative interaction to form a joint feature as follows,

Afterwards, the joint feature ht is passed through stacked deconvolutional layers and a sigmoid layer to form the final prediction output. To predict over multiple future steps, the prediction model progressively composes the new state using its prediction result to predict the next-step transition. Note that our prediction on frame-to-frame level is more precise than those on feature level because the prediction target of frame-to-frame is exact image from game environment while feature prediction target is encoded feature extracted from a trained neural network.

Hashing over the State Space with Autoencoder and LSH

To evaluate the novelty of a state, we adopt a hashing model to count over the state space. We first train an autoencoder model on frames, g : s ∈ Rm×n → ˆ s ∈ Rm×n , in an unsupervised manner (to classify the pixels), with the reconstruction loss defined as follows [Kingma and Welling, 2014],

where ˆ stij is the reconstructed pixel at the i-th row and the j-th column. The architecture for the autoencoder model is shown in Figure 2 (down). To be specific, each convolutional layer is followed by a Rectifier Linear Unit (ReLU) layer and a max pooling layer with a kernel size 2 × 2. To discretize the state space, we hash over the last frame st of each state. We adopt the output of the last ReLU layer from the encoder as the high-level state features, and denote by φ(·) the corresponding feature map that generates the high-level feature vector zt ∈Rd of a state, i.e., φ(st) = zt. To further discretize the state feature, locality-sensitive hashing (LSH) [Charikar, 2002] is adopted upon zt. To this end, a projection matrix A ∈ Rp×d is randomly initialized with i.i.d. entries drawn from a standard Gaussian N(0, 1). Then by projecting feature z through A, the sign of the outputs form a binary code, c ∈ Rp . With the introduced discretization scheme, we are able to count over the state space for the problem domain. During the RL process, a hash table H is created. The count for a state St, denoted by ψt, can be stored, queried and updated from the hash table. Overall, the process for counting over a state St is expressed in the following way:

Matching the Prediction with Reality

To derive the novelty for the predicted frames while updating the hash table by counting over the seen frames, we need to match the predictions with realities, i.e., make the hash codes for the predicted frames to be the same as their corresponding ground-truth seen frames in training. To this end, we introduce an additional training phase for the autoencoder model g(·). To make the hash codes to be the same, the derived feature vectors of the predicted frames and the ground-truth seen fames through φ(·) need to be close to each other. We introduce an additional loss function of a pair of ground-truth seen frame and predicted frame (st, ˆ st) as follows,

Finally, by combing (1) and (3), we define the following overall loss function,

where θ is the parameter for the autoencoder. Note that even though the prediction model could generate almost identical frames, training the autoencoder with only the reconstruction loss may lead to distinct state codes in all the task domains (details will be shown in Section 4.2). Therefore, the effort for matching the codes is necessary.

However, matching the state code while guaranteeing a satisfying reconstruction behavior is extremely challenging. Fine tuning an autoencoder fully trained with Lrec by involving the additional code matching loss Lmat would fast disrupt the reconstruction behavior before the code loss could decrease to the expected level. Training the autoencoder from scratch with both Lrec and Lmat is also difficult, as Lmat is initially very low and Lrec is very high. The network can hardly find a direction to consistently decrease Lrec with such an imbalance. Therefore, in this work, we propose to train the autoencoder for two phases, where the first phase uses Lrec to train on seen frames until convergence, and the second phase uses the composed loss function L as in (4) to address the requirement for matching the prediction with reality.

Computing Novelty for States

Once the prediction model f (·) and the autoencoder model g(·) are both trained, the agent could perform informed exploration as illustrated in Figure 1. At each step, the agent performs exploration with a probability less than ϵ and performs greedy action selection otherwise. When performing exploration, the agent strategically selects the most novel action direction to explore. Given the state St, the agent first performs roll-out with length H for the future trajectories predicted by the prediction model, for all the possible actions aj ∈ A. Formally, the novelty score for an action aj given state St, denoted by ρ(aj|St), is computed as,

where ψt+i is the count for the future state St+i derived from (2) by hashing over the predicted frame ˆ st+i, H is a predefined roll-out length, and β is a real-valued discount rate. After evaluating the novelty for all the possible actions, the agent selects the one with the highest novelty score to explore. Overall, the policy for the RL agent with the proposed informed exploration strategy is defined as:

where p is a random value sampled from Uniform (0,1), and Q(St, a) is the output of the Q-value function.

4 Experiments

In the empirical evaluation, we use the Arcade Learning Environment (ALE) [Bellemare et al., 2013], which consists of Atari 2600 video games as the testing domain. We choose 5 representative games that require significant exploration to learn the policy: Breakout, Freeway, Frostbite, Ms-Pacman and Q-bert. Four of the five games, Freeway, Frostbite, MsPacman and Q-bert are classified as hard exploration games, based on the taxonomy of exploration proposed in [Bellemare et al., 2016], where Freeway has sparse reward and the others have dense reward. Breakout, though not classified as hard exploration game, demonstrates significant exploration bottleneck with standard exploration attempt, as the state space is changing rapidly as agent learn, and the performance with standard exploration falls far behind advanced exploration technique. Hence it is also included as a test domain.

For all the tasks, we use the state representation that concatenates 4 consequent image frames of size 84 × 84.

4.1 Evaluation on PredictionModel

The architecture of the prediction model is identical to the one shown in Figure 2 (up). To train the prediction model, we create a training dataset which consists of 500,000 transition records generated by a fully trained DQN agent performing under standard ϵ-greedy, where ϵ is set equal to 0.3 (same as [Oh et al., 2015]). During training, we adopt Adam [Kingma and Ba, 2014] with a learning rate of 10-3 and a mini-batch size of 100. Moreover, we discount the gradient scale by multiplying the gradient value by 10-2 .

We show the pixel prediction loss in mean square error (MSE) for multi-step future prediction in Table 1. For all the task domains, the prediction losses are within a small scale. For multi-step prediction, as expected, the prediction loss increases with the increase of the prediction length. We demonstrate that the trained prediction models are able to generate realistic future frames which are visualized to be very close to the ground-truth frames in Figure 3.

4.2 Evaluation on Hashing with Autoencoder and LSH

The architecture for the autoencoder model is identical to that shown in Figure 2 (down). The autoencoder is trained on a dataset collected in an identical manner as that for the prediction model. It is trained under two phases. In the first phase, it is trained with only reconstruction loss. We use Adam as optimization algorithm, 10-3 as learning rate, a mini-batch size of 100 and discount the gradient by multiplying 10-2 . In the second phase, we train the autoencoder based on the loss in (4). Specifically, we use Adam as optimization algorithm, 10-4 as learning rate, a mini-batch size of 100, and λ value of 0.01. We discount the gradient by multiplying the gradient value by 5 × 10-3 .

Overall, it is extremely challenging to match the state codes for the predicted frames and their corresponding seen frames while maintaining a satisfying reconstruction performance.

We demonstrate this in Figure 5 (a) by showing the code loss, which is measured in terms of the number of mismatch in binary codes between a pair of predicted frame and its corresponding ground-truth frame. The presented result is derived by averaging over 10,000 pairs of codes. First, the result shows that without the second phase, it is impossible to perform hashing with autoencoder trained only by the reconstruction loss, since the average code losses are above 1 in all the domains and with distinct hash codes, the count values returned from querying the hash table are meaningless. Second, the result shows that after the training of the second phase, the code loss is significantly reduced.

We also show the reconstruction errors measured in terms of MSE after the training of the two phases for each domain in Figure 5 (b). By incorporating the code matching loss, the reconstruction behavior for the autoencoder receives slightly negative effect. A comparison of frame reconstruction effect after the training of the two phases are shown in Figure 3. It is shown that after training to match the state codes, the reconstructed frames are slightly blurred, but still able to reflect the essential features in each problem domain.

Moreover, we use Breakout as an illustrative example to demonstrate the hashing can generate meaningful hash codes for predicted future frames (see Figure 4). For a given groundtruth frame, we show the predicted frames with length 5 for taking each action. It can be found that different actions lead to different trajectories of board positions. For the hash codes, as three of the actions, no-op, fire and left, lead to little change in frames, most of the future frames are hashed into the same code. The action right leads to the most significant changes in board position, so the codes for future frames are much more distinct than the rest. Meanwhile, Figure 4 also shows that the multi-step prediction model generates realistic future frames.

4.3 Evaluation on Informed Exploration

We integrate the proposed informed exploration framework into DQN algorithm [Mnih et al., 2015] and compare with the following baselines: (1) DQN that performs ϵ-greedy with uniform random action selection, denoted by DQN-Random; (2) A3C [Mnih et al., 2016], (3)A3C with density model on Atari features [Bellemare et al., 2016], (4) exploration with pixelCNN-based density model [Ostrovski et al., 2017], (5) the state-of-the-art informed exploration approach proposed in [Oh et al., 2015], denoted by DQN-Informed. Our proposed approach is denoted by DQN-Informed-Hash. We use q = 3

as the length for hashing over future frames. We report the result in Table 2.

Among all the test domains, DQN-Informed-Hash outperforms DQN-Informed, and there are significant performance gains observed in each domain. Note that in Breakout, the agent fails to progress with DQN-Informed and always scores almost 0. It may due to that the kernel-based pixel distance evaluation metric used in DQN-Informed encourages the agent to explore states that is dissimilar from the recent history, which is insufficient to let the agent explore. Note that DQNInformed-Hash demonstrates the superior performance with a deterministic exploration mechanism. It indicates that counting over the predicted future frames could provide a meaningful direction for exploration.

5 Conclusion

In this paper, we propose an informed exploration framework for deep RL domains with discrete action space. By incorporating a deep action-conditional prediction model over future transitions and a hashing mechanism based on a deep autoencoder model and LSH, we enable the agent to predict over the future trajectories and intuitively evaluate the novelty for each future action direction based on the hashing result. Empirical results on Atari 2600 domain show that the proposed informed exploration framework could significantly improve the exploration efficiency in several challenging deep RL domains.

Acknowledgments

This work is funded by NTU Singapore Nanyang Assistant Professorship (NAP) grant M4081532.020, MOE AcRF Tier-1 grant 2016-T1-001-159, and Microsoft Research Asia.