Reward Prediction Error as an Exploration Objective in Deep RL

1 Introduction

In recent years deep reinforcement learning (RL) algorithms have demonstrated impressive performance on tasks such as playing video games and controlling robots [Mnih et al., 2015; Kalashnikov et al., 2018]. However, successful training for such cases typically requires both a well-shaped reward function, where the RL agent can sample improved trajectories through simple dithering exploration such as ϵ-greedy sampling, and the ability to collect many (hundreds of thousands to millions) of trials. Satisfying these preconditions often requires large amounts of domain-specific engineering. In particular, reward function design can be unintuitive, may require many iterations of design, and in some domains such as robotics can be physically impractical to implement.

∗Contact Author

The field of exploration methods in RL seeks to address the difficulties of reward design by allowing RL agents to learn from unshaped reward functions. Unshaped functions (for example, a reward of 1 when an object is moved to a target, and 0 otherwise) are usually much easier to design and implement than dense well-shaped reward functions. However, it is hard for standard RL algorithms to discover good policies on unshaped reward functions, and they may learn very slowly, if at all.

While substantial work has been conducted on designing general exploration strategies for high-dimensional Markov Decision Processes (MDPs) with sparse reward functions, few studies have distinguished between different types of tasks requiring exploration, particularly in terms of which signals in each MDP are useful for discovering new sources of reward. In this work, we consider three types of exploration challenges in particular: solving mazes, learning goal conditioning relationships, and escaping local reward maxima.

Many classical exploration tasks can be described well as mazes. For example, discovering the single rewarding state in a sparse reward environment, or navigating a precise series of obstacles in order to play a game. Qualitatively, the agent must search for the exit to the maze (reward), receives little or no reward before finding it, and has no learned priors. In the limit any RL task can be seen as a maze (such as by treating a single optimal trajectory as the "exit"), but such a treatment is often intractable for large MDPs.

Related but distinct are goal conditioned tasks. Here, the reward function is conditioned on a non-static goal specified by the environment and discovered through interaction. For example, a robot that must move an object to a set of coordinates, which differ for each episode. The agent must learn how the observation and reward are conditioned on the goal, which is made significantly harder when the underlying reward function is sparse and unshaped. Unlike a maze, correlations between observation and goal/reward provide additional information an agent can use to solve the problem.

Lastly, in a poorly-shaped reward function there may exist local maxima in the space of trajectories, where an agent cannot discover an improved policy through local exploration and must deliberately sample suboptimal trajectories to escape local maxima. Here, the contours of the reward function can provide information on what directions of exploration might be informative, even if exploring them does not immediately maximize reward.

This distinction is important because both goal conditioning and local maxima introduce additional information about the task that mazes do not contain - In a maze-like environment, discovering new states is explicitly linked with discovering new reward signals. Goal conditioning can provide hints as to what states are and are not rewarding (and when) through correlations in the observation. Similarly, local reward maxima are embedded within a dense reward function which provides correlations between each observation and the reward that results, and discovering this relationship may lead to improved reward. Each of these problems can be intractable using naive exploration (depending on the severity of the problem), but each in turn provides some signal that can be used to solve it. For example, goal-conditioning relationships can also be learned by goal-driven RL methods such as Hindsight Experience Replay [Andrychowicz et al., 2017], which by assuming the presence of a goal can learn much faster and more sample-efficiently on that class of problems.

In this paper, we propose the use of reward prediction error, specifically the Temporal-Difference Error (TD-Error) of a value function, to direct exploration in MDPs that contain Goal Conditioning and Local Maxima Escape problems but do not have a strong correlation between reward discovery and state novelty. To facilitate the use of this objective in a deep reinforcement learning setting for high-dimensional MDPs, we introduce QXplore, a new deep RL exploration formulation that seeks novelty in the predicted reward landscape instead of novelty in the state space. QXplore exploits the inherent reward-space signal from TD-error in valuebased RL, and directly promotes visiting states where the current understanding of reward dynamics is poor. In the following sections, we describe QXplore for continuous MDPs and demonstrate its utility for efficient learning on a variety of complex benchmark environments showcasing different exploration cases.

2 RelatedWork

Of the exploration methods proposed for deep RL settings, the majority provide some state-novelty objective that incentivizes an agent to explore novel states or transition dynamics. A simple approach consists of explicitly counting how many times each state has been visited, and acting to visit rarely explored states. This approach can be useful for small MDPs, but often performs poorly in highdimensional or continuous state spaces. However, several recent works [Tang et al., 2017; Bellemare et al., 2016; Fu et al., 2017] using count-like statistics have shown success on benchmark tasks with complex state spaces.

Another approach to environment novelty learns a model of the environment's transition dynamics and considers novelty as the error of the model in predicting future states or transitions. This exploration method relies on the assumption that any new state that can be predicted in advance is equivalent to some previously seen state in its effect on reward. Predictions of the transition dynamics can be directly computed [Pathak et al., 2017; Stadie et al., 2015], or related to an information gain objective on the state space, as described in VIME [Houthooft et al., 2016] and EMI [Kim et al., 2019].

Several exploration methods have recently been proposed that capitalize on the function approximation properties of neural network to recognize novel states. Random network distillation (RND) trains a function to predict the output of a randomly-initialized neural network from an input state, and uses the approximation error as a reward bonus for a separately-trained RL agent [Burda et al., 2019]. Similarly, DORA [Fox et al., 2018] trains a network to predict zero on observed states and deviations from zero are used to indicate unexplored states.

These methods have been shown to perform well on maze-solving exploration tasks such as the Atari game Montezuma's Revenge, where maximizing reward (game score) requires visiting each room of the game, which also maximizes the diversity of states and observations experienced. However, evaluating these methods on tasks where novelty does not correlate highly with reward, such as on other Atari games, shows little improvement over ϵ-greedy [Taiga et al., 2020].

Reward prediction error has been previously used for exploration in a few cases. Previous works described using reward misprediction and model prediction error for exploration [Schmidhuber, 1991; Thrun and M¨oller, 1992]. However, these works were primarily concerned with modelbuilding and system-identification in small MDPs, and used single-step reward prediction error rather than TD-error. Later, TD-error was used as a negative signal to constrain exploration to focus on states that are well understood by the value function for safe exploration [Gehring and Precup, 2013]. Related to maximizing TD-error is maximizing the variance or KL-divergence of a posterior distribution over MDPs or Q-functions, which can be used as a measure of uncertainty about rewards [Fox et al., 2018; Osband et al., 2018]. Posterior uncertainty over Q-functions can be used for information gain in the reward or Q-function space, but posterior uncertainty methods have thus-far largely been used for local exploration as an alternative to dithering methods such as ϵ-greedy sampling, though [Osband et al., 2018] do apply posterior uncertainty to Montezuma's Revenge and other exploration tasks in the Atari game benchmark.

3 Preliminaries

We consider RL in the terminology of [Sutton and Barto, 1998], in which an agent seeks to maximize reward in a Markov Decision Process (MDP). An MDP consists of states s ∈ S, actions a ∈ A, a state transition function S : S × A × S → [0, 1] giving the probability of moving to state st+1 after taking action at from state st for discrete timesteps t ∈ 0, ..., T. Rewards are sampled from reward function r : S × A → R. An RL agent has a policy π(st, at) = p(at|st) that gives the probability of taking action at when in state st. The agent aims to learn a policy to maximize the expectation of the time-decayed sum of reward Rπ(s0) = ∑Tt=0 γ t r(st, at) where at ∼ π(st, at).

A value function Vθ(st) with parameters θ is a function which computes Vθ(st) ≈ Rπ(st) for some policy π. Temporal difference (TD) error δt measures the bootstrapped error between the value function at the current timestep and the next timestep as

A Q-function is a value function of the form Q(st, at), which computes Q(st, at) = r(st, at) +γ · maxa′Q(st+1, a′ ), the expected future reward assuming the optimal action is taken at each future timestep. An approximation to this optimal Q-function Qθ with some parameters θ may be trained using a mean squared TD-error objective LQθ = ||Qθ(st, at) - (r(st, at) + γ · maxa′Q′θ′ (st+1, a′ ))||2 given some target Qfunction Q′θ′ , commonly a time-delayed version of Qθ [Mnih et al., 2015]. Extracting a policy π given Qθ amounts to com-

puting argmaxaQθ(st, a).

4 QXplore: TD-Error as Reward Signal

4.1 TD-error Objective

We first discuss why and how TD-error can be used as an exploration signal in deep RL settings on the classes of MDPs discussed above. Many Deep RL methods maintain a value function, typically a Q function, which in off-policy settings is bootstrapped to approximate the true Q function of the optimal policy. During the course of training, this Q function will naturally contain inaccuracies such that there is nontrivial Bellman error for certain s, a, s′ , r tuples. Intuitively, these errors indicate that the current estimate of the Q function does not correctly model the reward dynamics of the MDP per Bellman optimality. Therefore, an exploration method that prioritizes seeking out regions of the environment where the Q-function is inaccurate could aid an off-policy method in discovering novel sources of reward and propagating those improvements through the Q function.

Given a Q function with parameters θ and δt we define our exploration signal for a given state-action-next-state tuple as:

for some extrinsic reward function rE and target Q-function Q′θ . Notably, we use the absolute value of the TD rather than signed TD, as this is necessary to harness network extrapolation error in sparse reward environments.

Intuitively, a policy maximizing the expected sum of rx for a fixed Q function will sample trajectories where Qθ does not have an accurate estimate of the future rewards it will experience. This is useful for exploration because rx will be large not only for state-action pairs producing unexpected reward, but for all state-action pairs leading to such states, providing a denser exploration reward function and allowing for longer-range exploration.

4.2 Qx: Learning a Q-Function toMaximize TD-error

Now that we have defined a TD-error exploration formulation, we must ask, how should we maximize it? If we treat

Algorithm 1 QXplore for Continuous Actions

Input: MDP S, Q-function Qθ with target Q′θ′ , Qx function Qx,φ with target Q′x,φ′ , replay buffers ZQ and ZQx , batch size B and sampling ratios RQ and RQx , CEM policies πQ and πQx , time decay parameter γ, soft target update rate τ , and environments EQ, EQx

while not converged do

Sample environments

Sample minibatches for Qθ and Qx,φ

(sQ, aQ, rQ, s′Q) ← B ∗ RQ samples from ZQ and B ∗ (1 - RQ) samples from ZQx

(sQx , aQx , rQx , s′Qx ) ← B∗RQx samples from ZQx and B ∗ (1 - RQx ) samples from ZQ

Train

rx,θ ← |Qθ(sQx , aQx )-

LQx ← ||Qx,φ(sQx , aQx )-

(rx,θ + γQ′x,φ′ (s′Qx , πQx (s′Qx )))||2

Update θ ∝ LQ

Update φ ∝ LQx

θ′ ← (1 - τ )θ′ + τ θ

φ′ ← (1 - τ )φ′ + τφ

end while

end while

this signal as a reward function, rx can be used to generate a new MDP where the reward function is replaced by rx, and thus generally can be solved via any RL algorithm. For practical purposes, we choose to train a second Q-function to maximize rx, as allows the entire algorithm to be trained off-policy and for the two Q-functions to share replay data. Additionally, this allows us to use the original Q function Qθ as an exploitation policy at inference time, avoiding the need to trade off between exploration and exploitation because the Q function estimates are not directly affected by rx values.

In our formulation, which we call QXplore, we define a Q-function, Qx,φ(s, a) with parameters φ, whose reward objective is rx. We train Qx,φ using the standard bootstrapped loss function

The two Q-functions, Qθ and Qx, are trained in parallel, sharing replay data so that Qθ can learn to exploit sources of reward discovered by Qx and so that Qx can better predict the TD-errors of Qθ. Since the two share data, πQx acts as an adversarial teacher for Qθ, sampling trajectories that produce high TD-error under Qθ and thus provide novel information about the reward landscape. A similar adversarial sampling scheme was used to train an inverse dynamics model by [Hong et al., 2019], and [Colas et al., 2018] use separate goal-driven exploration and reward maximization phases for efficient learning. However, to our knowledge adversarial sampling policies have not previously been used for exploration. To avoid off-policy stability issues due to the different reward objectives, we sample a fixed ratio of experiences collected by each policy for each training batch. Our full method is described for the continuous-action domain in Algorithm 1 and a schematic of the method is shown in Figure 1.

4.3 State Novelty fromNeural Network Function Approximation Error

A key question in using TD-error for exploration is what happens when the reward landscape is flat? Theoretically, in the case that ∀(s, a), r(s, a) = C for some constant C ∈ R, an optimal Q-function which generalizes perfectly to unseen states will, in the infinite time horizon case, simply output ∀(s, a), Q⋆ (s, a) = ∑∞t=0 Cγ t . This results in a TD-error of 0 everywhere and thus no exploration signal. However, using neural network function approximation, we find that perfect generalization to unseen states-action pairs does not occur, and in fact observe in Figure 2 that the distance of a new datum from the training data manifold correlates with the magnitude of the network output's deviation from ∑∞t=1 Cγ t and thus with TD-error. As a result, in the case where the reward landscape is flat TD-error exploration converges to a form of state novelty exploration. This property of neural network function approximation has been used by several previous exploration methods to good effect, including RND [Burda et al., 2019] and DORA [Fox et al., 2018]. In particular, the exploration signal used by RND (extrapolation error from fitting the output of a random network) should be analogous to rx (extrapolation error from fitting a constant value), meaning we should expect to perform comparably to RND when no extrinsic reward exists.

5 Experiments

We describe here the results of experiments to demonstrate the effectiveness of QXplore on continuous control and Atari benchmark tasks. We also compare to results on SparseHalfCheetah from several previous publications.

Finally, we discuss several ablations to QXplore to demonstrate that all components of the method improve performance.

We compare QXplore primarily with a related state of the art state novelty-based method, RND [Burda et al., 2019], and with ϵ-greedy sampling as a simple baseline. Each method is implemented in a shared code base on top of TD3/dueling double deep Q-networks for the continuous/discrete action case [Fujimoto et al., 2018; Wang et al., 2016]. For experiments in continuous control environments, we implement and use a nonparametric cross-entropy method policy, previously described as more robust to hyperparameter variance, with the same architecture and hyperparameters as prior work [Simmons-Edler et al., 2019; Kalashnikov et al., 2018]. We experimented with a variant using DDPG-style parametric policies [Lillicrap et al., 2015] for both Qθ and Qx , but found preventing Qθ's policy from converging to poor local maxima difficult, consistent with previously reported stability issues in that class of algorithms [Simmons-Edler et al., 2019; Islam et al., 2017]. For all experiments, we set the data sampling ratios of Qθ and Qx, RQ and RQx respectively, at 0.75, the best ratio among a sweep of ratios 0.0, 0.25, 0.5, and 0.75 on SparseHalfCheetah. For continuous control tasks, we used a learning rate of 0.0001 for both Q-functions, the best among all paired combinations of 0.01, 0.001, and 0.0001, and fully-connected networks of two hidden layers of 256 neurons to represent each Q-function, with no shared parameters. For Atari benchmark tasks, we used the dueling double deep Q-networks architecture and hyperparameters described by Wang et al..

5.1 Experimental Setup

We benchmark on five continuous control tasks using the MuJoCo physics simulator that each require exploration due to sparse or unshaped rewards. First, the SparseHalfCheetah task originally proposed by VIME [Houthooft et al., 2016]. This task requires an agent to move 5 units (several hundred timesteps of actions) forward to receive reward, receiving 0 reward otherwise, and is maze-like in this regard. Next, we benchmark on three goal-directed OpenAI gym tasks, FetchPush, FetchSlide and FetchPickAndPlace, originally proposed in HER [Andrychowicz et al., 2017]. Lastly, we test a variant of SparseHalfCheetah that we refer to as LocalMaxEscape where a local reward maximum has been introduced - the agent receives 0 reward for every timestep it is between -1 and 1 units from the origin, -1 reward if it moves outside that range, but 100 reward per timestep if it moves 5 units forward, similar to SparseHalfCheetah. We chose these tasks as they are challenging exploration problems highlighting the different cases we are interested in that are relatively simple to control, but still involve large continuous state spaces and continuous actions. Guided by a recent study suggesting that exploration in the Atari game benchmark suite doesn't improve performance on most tasks [Taiga et al., 2020], we evaluated on a pair of "hard" exploration games, Venture and Gravitar, as well as an easy game, Pong, to show that QXplore can also function in this very different domain. We ran five random seeds for each experiment and plot the mean and plus/minus 1 standard deviation bounds for each set of runs, applying a Gaussian filter to each mean/stdev for readability.

5.2 Exploration Benchmark Performance

We show the performance of each method on each task in Figure 3. QXplore performs comparable to RND on the SparseHalfCheetah task, in line with our expectation, but performs much better comparatively on the Fetch tasks - only on FetchPush, the easiest task, did RND find non-random reward. We believe this is because TDerror drives exploration behavior that helps the agent to uncover the goal-conditioning relationship, whereas state novelty is goal-agnostic and does not aid in discovery of the relationship. QXplore also strongly outperformed RND on LocalMaxEscape, as negative rewards far from the origin increase TD error and drive rapid discovery of the global optimum.

To validate our performance and sample efficiency, we compare QXplore to previously published SparseHalfCheetah performance numbers in Table 1. Because to our knowledge no previous work has evaluated offpolicy Q-learning based methods on SparseHalfCheetah, we compare to previous methods built on top of TRPO [Schulman et al., 2015]. Due to the difference in baseline algorithms, we compare the number of episodes of interaction required to reach a given level of reward, though QXplore was not intended to be performant with respect to this metric. While some decrease in sample efficiency is expected due to differing baseline methods (TRPO [Schulman et al., 2015] versus TD3 [Fujimoto et al., 2018]), compared to the results reported by Kim et al. for EMI [Kim et al., 2019] and EX2 [Fu et al., 2017], and by Houthooft et al. for VIME [Houthooft et al., 2016] on the SparseHalfCheetah task, QXplore reaches almost every reward milestone faster, and achieves a peak reward (300) not achieved by any previous method. This shows that off-policy Q-learning combined with TD-error exploration can result in sample efficient as well as flexible exploration.

We also implemented a continuous-control adaptation of DORA [Fox et al., 2018] and tested it on SparseHalfCheetah. DORA performed poorly, possibly because it was not intended for use with continuous action spaces, and thus we did not test it on other tasks.

As a comparison to a published off-policy Q-learning exploration method, we compared to GEP-PG [Colas et al., 2018], which used separate exploration and exploitation phases similar to QXplore. We downloaded the author's implementation (built on top of DDPG) and tested it on SparseHalfCheetah using the parameters for the HalfCheetah-v2 task it was originally tested on. GEP-PG reached a validation reward of 120.2 after 4000 episodes, broadly comparable to our QXplore and RND implementations.

Finally, while the main focus of our evaluation is on continuous control tasks, we also evaluated QXplore on several games in the Atari Arcade Learning Environment [Bellemare et al., 2013] to verify that QXplore extends to tasks with image observations and discrete action spaces. We implemented QXplore and RND on top of dueling double DQN [Wang et al., 2016], using hyperparameters and network architectures from the Dopamine implementation of DQN [Castro et al., 2018]. We show the results in Figure 3 after 25 million training steps. Based on the findings of [Taiga et al., 2020], we did not expect to improve significantly compared to the baseline in this domain. Indeed, we find that QXplore performs comparably to the baseline and RND implementations on Pong and Gravitar, while outperforming them modestly on Venture, where QXplore converges faster, perhaps due to Qx focusing on reward-adjacent states more than ϵ-greedy or RND.

5.3 Ablations

There are two major features of QXplore that distinguish it from prior work in exploration: the use of a pair of policies that share replay data, and the use of unsigned TD-error to drive exploration. We performed several ablations that assess the contribution of each of these features to our method and confirm their value for exploration. We show the results in Figure 4. We find that the use of separate exploration and exploitation policies along with unsigned TD-error is necessary to obtain good performance, and that ablations of these components either fail to train or substantially reduce performance. We discuss each case in detail below.

Single-Policy QXplore. First, we tested a single-policy version of QXplore by replacing Qθ(s, a) with a value function Vθ(s). We use a value function rather than Q-function in this case to avoid large estimation errors stemming from fully off-policy training. We observe in Figure 4 that while the policy is able to find reward quickly and converge faster, the need to satisfy both objectives results in a lower converged reward than the original QXplore method.

1-Step Reward Prediction. Second, we ran an ablation where we replace Qθ(s, a) with a function that simply predicts the current r(st, at). Using reward error instead of a value function in Qx can still produce the same state novelty fallback behavior in the absence of reward; however, it provides only limited reward-based exploration utility. We evaluate this variant and observe in Figure 4 that it fails to sample reward. Reward prediction error is not sufficient to allow strong exploration behavior without some form of lookahead.

QXplore with State Novelty Exploration. To assess the importance of TD-error specifically in our algorithm, we replaced the TD-error maximization objective of Qx with the random network prediction error maximization objective of RND, while still performing rollouts of both policies. The results are shown in Figure 4. We observe that while the modified Qx samples reward, it is too infrequent to guide Q to learn the task. Qualitatively, the modified Qx function does not display the directional preference in exploration that normal Qx does once reward is discovered, instead sampling both directions equally.

QXplore with Signed TD-Error Objective. While we used unsigned TD-error to train Qx, we also tested QXplore using signed TD-error. We used the negative signed TD-error -δt from equation 1 so that better-than-expected rewards result in positive rx values. The results of this experiment are shown in Figure 4. While this ablation is able to converge and solve the task, the unsigned TD-error performs much better on SparseHalfCheetah, likely due to the extrapolation error described in Figure 2 being both positive and negative.

5.4 Qualitative Behavioral Analysis

Qualitatively, on SparseHalfCheetah we observe interesting behavior fromQx late in training. After initially converging to obtain high reward, Qx appears to get "bored" and will focus on the reward threshold, stopping short or jumping back and forth across it, which results in reduced reward but higher TD-error. This behavior is distinctive of TD-error seeking over state novelty seeking, as such states are not novel compared to moving past the threshold but do result in higher TDerror. Such behavior from Qx motivates Q to sample the state space around the reward boundary and thus learn to solve the task. Example sequences of such behaviors are shown in Figure 5.

6 Discussion and Conclusions

Here, we have proposed the use of reward prediction error as an objective for exploration in deep reinforcement learning. We defined a deep RL algorithm, QXplore, using TDerror that is sufficient to discover solutions to multiple types of challenging exploration tasks across multiple domains. We found that QXplore performs well across all exploration task types tested compared to our state novelty baseline, although type-specific algorithms can likely perform better on some types, such as goal-directed exploration.

While QXplore is a general-purpose exploration algorithm that can be applied successfully to many tasks, several limitations remain for TD-error exploration. In the worst-case, TDerror likely performs no better than state novelty for certain "pure" exploration tasks, such as exploring a linear chain of states, though with an optimistic prior on the Q-values of unseen states it may perform comparably to state novelty. There also exist adversarial tasks where the unsigned TD-error leads to less efficient exploration compared to other possible policies, such as a task with many states that yield large negative rewards uncorrelated with positive rewards. Combining TD-error exploration with reward exploitation may help in such cases to bias the search. However, balancing the rate at which the TD-error signal disappears for a given state with the reward function's magnitude is critical to get rapid convergence, and more research into such approaches is needed. Lastly, TD-error maximization may result in "risky" exploration (in contrast to the "safe" TD-minimizing exploration of Gehring and Precup) and thus may not be well suited for tasks where failures or negative returns have real-world consequences without additional constraints on the agent's actions, or the use of signed TD-error to avoid trajectories yielding worse-than-expected returns.

We hope that our results can spur more investigation into TD-error-based exploration methods to address some of the outstanding challenges described above, as well as encourage further work on diverse exploration signals in RL and on more general exploration objectives suitable for use on heterogeneous RL tasks.