Benchmarking Batch Deep Reinforcement Learning Algorithms

Introduction

Batch reinforcement learning is the study of algorithms that can learn from a single batch of data, without directly interacting with the environment (Lange et al., 2012). Learning with finite data sets is invaluable for a variety of real-world applications, where data collection may be difficult, time-consuming or costly (Guez et al., 2008; Pietquin et al., 2011; Gauci et al., 2018). In principle, standard off-policy deep reinforcement learning algorithms such as DQN and DDPG (Mnih et al., 2015; Lillicrap et al., 2015) are applicable in the batch reinforcement learning setting, due to basis on more fundamental batch reinforcement learning algorithms such as Fitted Q-iteration (Ernst et al., 2005; Riedmiller, 2005). However, these traditional algorithms only come with convergence guarantees for non-parametric function approximation (Gordon, 1995; Ormoneit and Sen, 2002), have no guarantees on the quality of the learned policy, and scale poorly to high dimensional tasks.

Recent results demonstrated widely-used off-policy deep reinforcement learning algorithms fail in the batch setting due to a phenomenon known as extrapolation error, which is induced from evaluating state-action pairs which are not contained in the provided batch of data (Fujimoto et al., 2019). This erroneous extrapolation is propagated through temporal difference update of most off-policy algorithms (Sutton, 1988), causing extreme overestimation and poor performance (Thrun and Schwartz, 1993). Fujimoto et al. (2019) proposed the batch-constrained reinforcement learning framework, where the agent should favor a state-action visitation similar to some subset of the provided batch, and provided a practical continuous control deep reinforcement learning algorithm, BCQ, which eliminates unseen actions through a sampling procedure over a generative model of the data set. Contrary to these results, Agarwal et al. (2019) showed that using the entire history of a deep reinforcement learning agent as a batch (50 million time steps), standard deep reinforcement learning algorithms could reach a comparable performance to an online algorithm. In particular, they highlighted that distributional reinforcement learning algorithms (Bellemare et al., 2017; Dabney et al., 2017) performed particularly well with this large and diverse data set.

Given batch reinforcement learning encompasses a large number of settings, existing algorithms have been tested over a wide range of environments, and under a variety of data distributions, making comparisons difficult and contradictory results possible. In this paper, we benchmark the performance of several algorithms on the Arcade Learning Environment (Bellemare et al., 2013), with a large data set of 10 million data points generated by a partially-trained policy. We find that with a single behavioral policy, not only do widely-used off-policy deep reinforcement learning algorithms perform poorly, even existing batch algorithms are inadequate solutions, failing to outperform the behavioral policy.

We introduce a variant of the BCQ algorithm (Fujimoto et al., 2019) which operates on a discrete action space. Our version of BCQ is simple to implement, while maintaining the core ideas of the original continuous control algorithm. Furthermore, our results demonstrate BCQ greatly outperforms all prior deep batch reinforcement learning algorithms, including KL-Control (Jaques et al., 2019), which was shown to outperform another naïve variant of BCQ for discrete actions. BCQ demonstrates learning akin to a strong robust imitation learning algorithm, matching, or exceeding, the performance of the noiseless behavioral policy, a DQN agent trained online with the same amount of data. While simply matching the noiseless behavioral policy is often unsatisfactory, we hope that BCQ will serve as a strong baseline in this setting.

We benchmark the performance of several batch deep reinforcement learning algorithms under a single unified setting. This continues the line of work from Agarwal et al. (2019) by examining the performance of widely-used off-policy algorithms in the Atari domain. However under ordinary data conditions, we find that standard off-policy reinforcement learning algorithms perform poorly.

We validate the batch reinforcement learning experiments from Fujimoto et al. (2019) on the more challenging, discrete-action Atari environments, and demonstrate the phenomenon of extrapolation error still occurs in this domain.

We introduce a discrete-action version of BCQ which achieves a state of the art performance in our batch reinforcement learning setting, and will serve as a strong baseline for future methods.

Preliminaries

Reinforcement Learning. Reinforcement learning studies sequential decision making processes, generally formulated by a Markov decision process (MDP) $(\mathcal{S},\mathcal{A},p,r,\gamma)$, where $\mathcal{S}$ and $\mathcal{A}$ denote the corresponding state and action spaces respectively. At a given discrete time step, a reinforcement learning agent takes action $a\in\mathcal{A}$ in state $s\in\mathcal{S}$, and receives a new state $s^{\prime}\in\mathcal{S}$ and reward $r(s,a,s^{\prime})$, in accordance to the transition dynamics $p(s^{\prime},r|s,a)$. The aim of the agent is to maximize the sum of discounted rewards, also known as the return $R_{t}=\sum_{i={t+1}}^{\infty}\gamma^{i}r(s_{i},a_{i},s_{i+1})$, where the discount factor $\gamma\in[0,1)$, determines the effective horizon by weighting future rewards. The decisions of an agent are made by its policy $\pi:\mathcal{S}\rightarrow\mathcal{A}$, which maps a given state $s$ to a distribution over actions.

Deep Reinforcement Learning. In deep reinforcement learning, the value function is approximated by a neural network $Q_{\theta}$. In the Deep Q-Network algorithm (DQN) (Mnih et al., 2015), this value function $Q_{\theta}$ is updated in a manner that approximates the optimality operator, through Q-learning (Watkins, 1989):

where $l_{\kappa}$ defines the Huber loss (Huber et al., 1964):

but is generally interchangeable with other losses such as mean-squared error. A target network $Q_{\theta^{\prime}}$ with frozen parameters is used to maintain a fixed target over multiple updates, where $\theta^{\prime}$ is updated to $\theta$ after a set number of learning steps. The loss (Eqn. 3) is minimized over mini-batches of transitions $(s,a,r,s^{\prime})$ sampled from some data set, or replay buffer $\mathcal{B}$ (Lin, 1992). For an on-policy algorithm, $\mathcal{B}$ is generated by the current policy, however, for an off-policy algorithm $\mathcal{B}$ may be generated by any collection of policies.

Batch Deep Reinforcement Learning. In batch reinforcement learning, we additionally assume the data set is fixed, and no further interactions with the environment will occur. This is in contrast to many off-policy deep reinforcement learning algorithms which assume further interactions with the current policy, but train with a history of experiences generated by previous iterations of the policy. In some instances, access to the behavioral policy is assumed (Precup et al., 2001; Thomas and Brunskill, 2016; Petrik et al., 2016; Laroche et al., 2019), but in our experiments, the behavioral policy is treated as unknown. For notational simplicity, we sometimes refer to a collection of behavioral policies as a single behavioral policy $\pi_{b}$.

Batch deep reinforcement learning algorithms have been shown to be susceptible to extrapolation error (Fujimoto et al., 2019), induced by generalization from the neural network function approximator. When selecting actions $a^{\prime}$ (Eqn. 3), such that $(s^{\prime},a^{\prime})$ is distant from data contained in the batch, the estimate $Q_{\theta^{\prime}}(s^{\prime},a^{\prime})$ may be arbitrarily poor, introducing extrapolation error. In systems where further environment interactions are possible this error can be mitigated by simply attempting the action $a^{\prime}$, which occurs naturally as long as the behavioral policy is similar to the target policy.

Batch Deep Reinforcement Learning Algorithms

In this section, we survey recent batch deep reinforcement learning algorithms, including off-policy algorithms which have been to shown to work in a batch setting (Agarwal et al., 2019).

QR-DQN. Quantile Regression DQN (QR-DQN) (Dabney et al., 2017) is a distributional reinforcement learning method (Morimura et al., 2010; Bellemare et al., 2017) which aims to estimate the set of $K$ $\tau$-quantiles of the return distribution, $\{\tau\}^{K}=\{\frac{i+0.5}{K}\}^{K-1}_{i=0}$. Instead of outputting a single value for each action, QR-DQN outputs a $K$-dimensional vector representing these quantiles. A pairwise loss between each quantile is computed, similarly to DQN:

where $l_{\tau}$ is a weighted variant of the Huber loss, denoted the quantile Huber loss:

An estimate of the value can be recovered through the mean over the quantiles, and the policy $\pi$ is defined by greedy selection over this value:

REM. Random Ensemble Mixture (REM) (Agarwal et al., 2019) is an off-policy Q-learning method which aims to capture the success of distributional reinforcement learning algorithms with a simpler algorithm. Similar to QR-DQN, the output of the Q-network is a $K$-dimensional vector. During each update, this vector is combined with a convex combination of $K$ weights $\alpha_{k}$ sampled from a $(K-1)$-simplex:

The policy is defined by the argmax over the mean of the output vector $\pi=\operatorname*{argmax}_{a}\frac{1}{K}\sum Q^{k}_{\theta}(s,a)$.

BCQ. Batch-Constrained deep Q-learning (BCQ) (Fujimoto et al., 2019) is a batch reinforcement learning method for continuous control. BCQ aims to perform Q-learning while constraining the action space to eliminate actions which are unlikely to be selected by the behavioral policy $\pi_{b}$, and are therefore unlikely to be contained in the batch. At its core, BCQ uses a state-conditioned generative model $G_{\omega}:\mathcal{S}\rightarrow\mathcal{A}$ to model the distribution of data in the batch, $G_{\omega}\approx\pi_{b}$ akin to a behavioral cloning model. As it is easier to sample from $\pi_{b}(a|s)$ than model $\pi_{b}(a|s)$ exactly in a continuous action space, the policy is defined by sampling $N$ actions $a_{i}$ from $G_{\omega}(s)$ and selecting the highest valued action according to a Q-network. Since BCQ was designed for continuous actions, the method also includes a perturbation model $\xi_{\phi}(s,a)$, which is a residual added to the sampled actions in the range $[-\Phi,\Phi]$, and trained with the deterministic policy gradient (Silver et al., 2014). Finally the authors include a weighted version of Clipped Double Q-learning (Fujimoto et al., 2018) to penalize high variance estimates and reduce overestimation bias, using $Q^{k}_{\theta}$ with $k=\{1,2\}$:

During evaluation, the policy is defined similarly, by sampling $N$ actions from the generative model, perturbing them and selecting the argmax:

BEAR-QL. Bootstrapping Error Accumulation Reduction Q-Learning (BEAR-QL) (Kumar et al., 2019) is an actor-critic algorithm which builds on the core idea of BCQ, but instead of using a perturbation model, samples actions from a learned actor. As in BCQ, BEAR-QL trains a generative model of the data distribution in the batch. Using the generative model $G_{\omega}$, the actor $\pi_{\phi}$ is trained using the deterministic policy gradient (Silver et al., 2014), while minimizing the variance over an ensemble of $K$ Q-networks, and constraining the maximum mean discrepancy (MMD) (Gretton et al., 2012) between $G_{\omega}$ and $\pi_{\phi}$ through dual gradient descent:

where $\hat{a}\sim\pi_{\phi}(s)$ and the MMD is computed over some choice of kernel. The update rule for the ensemble of Q-networks matches BCQ, except the actions $\hat{a}$ can be sampled from the single actor network $\pi_{\phi}$ rather than sampling from a generative model and perturbing:

The policy used during evaluation is defined similarly to BCQ, but again samples actions directly from the actor:

KL-Control. KL-Control with $\Psi$-learning and Monte-Carlo target value estimation is a combination of methods introduced by Jaques et al. (2019) for batch reinforcement learning of a dialog task with discrete actions. KL-control uses a KL-regularized objective to incorporate a prior $p$ into learning, which is weighted by the hyper-parameter $c$. In this method, the prior is set to a learned estimate of the behavioral policy $p=\pi_{b}$, again via a generative model $G_{\omega}$, in similar fashion to BCQ, noting that in a discrete-action setting the probabilities $G_{\omega}(a|s)\approx\pi_{b}(a|s)$ can be computed exactly through behavioral cloning. Rather than a hard maximum in the target, $\Psi$-learning uses the log over the sum of the exponential of the action-values (Jaques et al., 2017). Finally, Jaques et al. (2019) estimate a lower-bound over the target value by Monte-Carlo estimation, from sampling $K$ dropout masks (Srivastava et al., 2014; Gal and Ghahramani, 2016) and taking the minimum:

In $\Psi$-learning, the policy $\pi(a|s)=\frac{\exp{Q_{\theta}(s,a)}}{\sum_{\hat{a}\in\mathcal{A}}\exp Q_{\theta}(s,\hat{a})}$, as a form of Boltzmann exploration, however in a setting where diversity is not beneficial, we found $\pi=\operatorname*{argmax}_{a}Q_{\theta}(s,a)$ to achieve higher performance.

SPIBB-DQN. Safe Policy Improvement with Baseline Bootstrapping DQN (SPIBB-DQN) (Laroche et al., 2019) is a safe batch reinforcement learning algorithm for discrete actions which resembles Q-learning, but modifies the policy to match the behavioral policy, or a known baseline, $\pi_{b}$ when there is insufficient access to data. Additionally, the authors assume access to some estimate of the state-action distribution of the batch $D(s,a)$. The authors define state-action pairs $(s,a)\in\mathfrak{B}$ as the data points which are unlikely under the data distribution $D(s,a)\leq\epsilon$. For a given state $s$, the actions $a$, such that $(s,a)\in\mathfrak{B}$, the policy is set to match the baseline policy $\pi(a|s)=\pi_{b}(a|s)$. Otherwise, the highest valued action $a\notin\mathfrak{B}$ is set to the remaining probability, defining the policy as follows:

The Q-network is updated following the standard DQN update, swapping the max operator with $\pi$:

Although appealing due to its theoretical guarantees in the tabular setting, the authors unfortunately do not include a complete implementation of their deep algorithm in their paper, instead analyzing the algorithm under settings where $D(s,a)$ can be computed almost exactly. However, in principle $D(s,a)$ can be computed with a number of pseudo-count methods (Bellemare et al., 2016; Tang et al., 2017; Burda et al., 2018).

Discrete Batch-Constrained Deep Q-learning

In this section, we introduce a discrete variant of the Batch Constrained deep Q-Learning (BCQ) algorithm (Fujimoto et al., 2019). Much of the complexity of the original algorithm is introduced to deal with the continuous action space, and the core principles of the algorithm can be maintained in a much simpler manner in the discrete setting.

In the original BCQ, a state-conditioned model of the data set $G_{\omega}$ is learned and the highest valued action is selected after sampling actions from $G_{\omega}$ and perturbing the sampled actions within a set range. However, in a discrete-action setting, we can compute the probabilities of every action $G_{\omega}(a|s)\approx\pi_{b}(a|s)$, and instead utilize some threshold to eliminate actions:

To adaptively adjust this threshold, we scale it by the maximum probability from the generative model over all actions, to only allow actions whose relative probability is above some threshold. This results in an algorithm comparable to DQN (Mnih et al., 2015) where the policy is defined by a constrained argmax. The Q-network is trained by swapping the max operation with actions selected by the policy:

With this threshold $\tau$, we maintain the original property of BCQ where setting $\tau=0$ returns Q-learning and $\tau=1$ returns an imitator of the actions contained in the batch.

Given the original BCQ used Clipped Double Q-learning (Fujimoto et al., 2018) to reduce overestimation bias in the continuous-action setting, we instead apply Double DQN (Van Hasselt et al., 2016), selecting the max valued action with the current Q-network $Q_{\theta}$, and evaluating with the target Q-network $Q_{\theta^{\prime}}$:

The generative model $G_{\omega}$, effectively a behavioral cloning network, is trained in a standard supervised learning fashion, with a cross-entropy loss. We summarize our discrete BCQ in algorithm 1.

Experiments

We validate our methods on the Arcade Learning Environment platform (Bellemare et al., 2013) of Atari 2600 games through OpenAI gym (Brockman et al., 2016). We use standard preprocessing to image frames and environment rewards (Mnih et al., 2015; Castro et al., 2018), and match the recommendations of Machado et al. (2018) for fair and reproducible results. Exact experimental and algorithmic details are explained in the supplementary. In general, consistent hyper-parameters are kept across all algorithms, and minimal hyper-parameter optimization was performed.

Algorithms. We use each of the algorithms listed in Section 3, other than BEAR-QL and SPIBB-DQN, and use our discrete version of BCQ rather than the original, which was defined for continuous control. We omit BEAR-QL due to the reliance on a continuous action space, similarity to BCQ and number of hyper-parameter choices. Although SPIBB-DQN can be extended to settings where the behavioral policy is estimated (Simão et al., 2019), we omit it due to the lack of implementation for a deep setting without access to pseudo-counts of the dataset, which again would require a large number of design and hyper-parameter choices.

Experimental Setting. We use a partially-trained DQN agent (Mnih et al., 2015) as our behavioral policy. This DQN agent was trained online for 10 million time steps (40 million frames), following a standard training procedure. The behavioral policy is used to gather a new set of 10 million transitions which is used to train each off-policy agent. To ensure exploration, the behavioral policy uses $\epsilon=0.2$ for the whole episode with $p=0.8$ and $\epsilon=0.001$ with $p=0.2$. This mix of $\epsilon$ is used to ensure the data set includes data reaching the max performance of the agent as well as exploratory behavior. Unlike the experiments by Agarwal et al. (2019), the batch data is generated by this single behavioral policy, rather than a series of changing policies. This setup is used to closely match batch settings used by real-world systems, which generally rely on a single behavioral for a fixed period of time (Gauci et al., 2018). For each environment, the agents are trained on this data set for 10 million time steps, and evaluated on 10 episodes every 50k time steps. We graph both the final performance of the online DQN, as well as the performance of the behavioral policy, the online DQN with exploration noise. Results are displayed in Figure 1. Additionally, in Figure 2 we graph the value estimates of each algorithm to examine if the divergence from extrapolation error (Fujimoto et al., 2019) is present in the Atari domain.

Discussion. Under our experimental conditions, both the online DQN and offline agents have been trained with $10$ million data points, where the offline agents are trained with $4\times$ more iterations. Regardless, it is clear from Figure 1 that standard off-policy algorithms (DQN, QR-DQN, REM) perform poorly in this single behavioral policy setting. Out of the three QR-DQN is a clear winner, but generally underperforms the noisy behavioral policy. While Agarwal et al. (2019) showed these algorithms performed well with large replay buffers and high diversity, by training agents using the entire replay buffer from training a DQN agent (50 million transitions), it is clear there is a reliance on their specific setting for these algorithms to perform well. We do remark that our results confirm their observation that distributional reinforcement learning algorithms (QR-DQN) outperforms their standard counterpart (DQN), suggesting that learning a distribution aids in exploitation.

In comparison to the off-policy algorithms, the batch reinforcement learning algorithms perform reasonably well. BCQ, in particular, outperforms every other method in all tested games. However, these results also shown the current downsides of these methods. Although BCQ has the strongest performance, on most games it only matches the performance of the online DQN, which is the underlying noise-free behavioral policy. These results suggest BCQ achieves something closer to robust imitation, rather than true batch reinforcement learning when there is limited exploratory data. KL-Control often demonstrates a strong initial performance before failing. Examining Figure 2, the drop in performance corresponds to a negative divergence in the value estimate. In the games where the value estimate does not diverge (Enduro and Seaquest), KL-Control performs well. It is possible that with additional hyper-parameter tuning, stability could be maintained, however, this suggests that KL-Control is not robust to hyper-parameters or varied tasks.

These results additionally confirm the experiments from Fujimoto et al. (2019), which showed that standard off-policy deep reinforcement learning algorithms fail in the batch setting, due to high extrapolation error from selecting out-of-distribution actions during value updates. Furthermore, it is clear that the algorithms with the strongest performance also have stable value estimates, suggesting that the mitigation of extrapolation error is important for batch deep reinforcement learning.

Conclusion

In this paper, we perform empirical analysis on current off-policy and batch reinforcement learning algorithms in a simple single behavioral policy task on several Atari environments (Bellemare et al., 2013). Our experiments show that current algorithms fail to achieve a satisfactory performance in this setting, by under-performing online DQN and the behavioral policy. Our results suggest that algorithms which do not consider extrapolation error or the distribution of data will perform poorly in the batch setting with low data diversity, due to unstable value estimates. Lastly, we introduce a discrete version of Batch-Constrained deep Q-learning (BCQ) (Fujimoto et al., 2019), which outperforms all previous algorithms in this setting, while being straightforward to implement. We hope BCQ will serve as a strong baseline for future methods in this area.

References

Appendix A Experimental Details

The Atari 2600 environment is preprocessed in the same manner as previous work [Mnih et al., 2015, Machado et al., 2018, Castro et al., 2018] and we use consistent preprocessing across all tasks and algorithms.

We denote the output of the Atari environment as frames. These frames are grayscaled and resized to $84$ by $84$ pixels. Furthermore, the agent only receives a state and selects an action every $4$th frame. The selected action is repeated for the next $4$ frames. The state is defined by the maximum between the previous two frames. Furthermore, the input to the networks is a concatenation of the previous $4$ states. This means each network receives a tensor with dimensions $(4,84,84)$, which considers a history of $16$ frames ($4$ frames over $4$ states). For the first $3$ time steps, the input to the networks includes states which are set to all s. If the environment terminates before $4$ frames have passed, the state is defined by the maximum of the final two frames before termination.

In accordance to Machado et al. , sticky actions are used, such that the action $a_{t}$ is set to the previous action $a_{t-1}$ with probability $p=0.25$. No-operations are not applied at the beginning of episodes, and random frame skips are not used.

The reward function is defined by the in-game reward, but clipped to a range of $$. The environment terminates when the game terminates (rather than on a lost life), or after$27$k time steps, corresponding to$108$k frames or$30$ minutes of real time.

A.2 Architecture and Hyper-parameters.

Unless stated otherwise, all networks use the same architecture and hyper-parameters.

Image inputs are passed through a 3-layered convolutional neural network taking an input size of $(4,84,84)$. The first layer has a kernel depth of $32$, kernel size of $8\times 8$ and stride $4$. The second layer has a kernel depth of $32$, kernel size of $4\times 4$ and stride $2$. The third layer has a kernel depth of $64$, kernel size of $2\times 2$ and stride $1$. This output is flattened into a vector of $3136$ and passed to a full-connected network with one hidden layer of $512$. The output of the Q-network is a Q-value for each action. ReLU activation functions are used after layer besides the final fully-connected layer.

For methods which require a generative model, the convolutional neural network is shared between both the Q-network and the generative model. The generative model is a secondary fully-connected network with the same architecture. The final layer uses a softmax activation after the output of the network, to recover probabilities for each action.

Hyper-parameters are held consistent across each algorithm and listed in Table 1. Hyper-parameters were chosen to match the implementation of Rainbow [Hessel et al., 2017] in the Dopamine framework [Castro et al., 2018].

Algorithm-specific hyper-parameters are listed in Table 2. Additionally, we regularize the generative model $G_{\omega}$ used in BCQ and KL-Control by a penalty on the final pre-activation output $x$ by $0.01x^{2}$. For KL-Control, dropout is applied before both of the fully-connected layers.

Additionally, we list the hyper-parameters of the online DQN, which served as the behavioral policy, in Table 3. Training frequency corresponds to how often a training update was performed. Warmup time steps defines the initial period where actions are randomly selected and stored in the replay buffer, before any training occurs. We use $\epsilon$-greedy for exploration, where $\epsilon$ is decayed over time.