Benchmarking Batch Deep Reinforcement Learning Algorithms — part 2/3
Cleaned-text code points [15959, 31411). Bibliography omitted here; source.md includes it.
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 ω 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 K Q-networks, and constraining the maximum mean discrepancy (MMD) ( Gretton et al., 2012 ) between G ω G_{\omega} and π ϕ \pi_{\phi} through dual gradient descent: ℒ ( ϕ ) = − ( 1 K ∑ k Q θ k ( s , a ^ ) − τ var k Q θ k ( s , a ^ ) ) s.t. MMD ( G ω ( s ) , π ϕ ( s ) ) ≤ ϵ , \mathcal{L}(\phi)=-\left(\frac{1}{K}\sum_{k}Q^{k}_{\theta}(s,\hat{a})-\tau\text{var}_{k}Q^{k}_{\theta}(s,\hat{a})\right)\text{ s.t. MMD}\left(G_{\omega}(s),\pi_{\phi}(s)\right)\leq\epsilon, (11) where a ^ ∼ π ϕ ( s ) \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 a ^ \hat{a} can be sampled from the single actor network π ϕ \pi_{\phi} rather than sampling from a generative model and perturbing: ℒ ( θ ) = ∑ k ( r + γ max a ^ ∼ π ϕ ( s ′ ) ( λ min k ′ Q θ ′ k ′ ( s ′ , a ^ ) + ( 1 − λ ) max k ′ Q θ ′ k ′ ( s ′ , a ^ ) ) − Q θ k ( s , a ) ) 2 . \mathcal{L}(\theta)=\sum_{k}\left(r+\gamma\max_{\hat{a}\sim\pi_{\phi}(s^{\prime})}\left(\lambda\min_{k^{\prime}}Q^{k^{\prime}}_{\theta^{\prime}}(s^{\prime},\hat{a})+(1-\lambda)\max_{k^{\prime}}Q^{k^{\prime}}_{\theta^{\prime}}(s^{\prime},\hat{a})\right)-Q^{k}_{\theta}(s,a)\right)^{2}. (12) The policy used during evaluation is defined similarly to BCQ, but again samples actions directly from the actor: π ( s ) = argmax a ^ 1 K ∑ k Q θ k ( s , a ^ ) , a ^ ∼ π ϕ ( s ) . \pi(s)=\argmax_{\hat{a}}\frac{1}{K}\sum_{k}Q^{k}_{\theta}(s,\hat{a}),\qquad\hat{a}\sim\pi_{\phi}(s). (13)
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 p into learning, which is weighted by the hyper-parameter c c . In this method, the prior is set to a learned estimate of the behavioral policy p = π b p=\pi_{b} , again via a generative model G ω G_{\omega} , in similar fashion to BCQ, noting that in a discrete-action setting the probabilities G ω ( a | s ) ≈ π b ( a | s ) 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 K dropout masks ( Srivastava et al., 2014 ; Gal and Ghahramani, 2016 ) and taking the minimum: ℒ ( θ ) = l κ ( log G ω ( a | s ) + r c + γ min k ( log ∑ a ′ exp Q θ ′ k ( s ′ , a ′ ) ) − Q θ ( s , a ) ) . \mathcal{L}(\theta)=l_{\kappa}\left(\log G_{\omega}(a|s)+\frac{r}{c}+\gamma\min_{k}\left(\log\sum_{a^{\prime}}\exp{Q^{k}_{\theta^{\prime}}(s^{\prime},a^{\prime})}\right)-Q_{\theta}(s,a)\right). (14) In Ψ \Psi -learning, the policy π ( a | s ) = exp Q θ ( s , a ) ∑ a ^ ∈ 𝒜 exp Q θ ( s , a ^ ) \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 π = argmax a Q θ ( s , a ) \pi=\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, π b \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 ) D(s,a) . The authors define state-action pairs ( s , a ) ∈ 𝔅 (s,a)\in\mathfrak{B} as the data points which are unlikely under the data distribution D ( s , a ) ≤ ϵ D(s,a)\leq\epsilon . For a given state s s , the actions a a , such that ( s , a ) ∈ 𝔅 (s,a)\in\mathfrak{B} , the policy is set to match the baseline policy π ( a | s ) = π b ( a | s ) \pi(a|s)=\pi_{b}(a|s) . Otherwise, the highest valued action a ∉ 𝔅 a\notin\mathfrak{B} is set to the remaining probability, defining the policy as follows: π ( a | s ) = { π b ( a | s ) if ( s , a ) ∈ 𝔅 ∑ a ∉ 𝔅 π b ( a | s ) if ( s , a ) ∉ 𝔅 and a = argmax a | ( s , a ) ∉ 𝔅 Q θ ( s , a ) 0 otherwise. . \pi(a|s)=\begin{cases}\pi_{b}(a|s)&\text{if }(s,a)\in\mathfrak{B}\\ \sum_{a\notin\mathfrak{B}}\pi_{b}(a|s)&\text{if }(s,a)\notin\mathfrak{B}\text{ and }a=\argmax_{a|(s,a)\notin\mathfrak{B}}Q_{\theta}(s,a)\\ 0&\text{otherwise.}\end{cases}. (15) The Q-network is updated following the standard DQN update, swapping the max operator with π \pi : ℒ ( θ ) = l κ ( r + γ Q θ ′ ( s ′ , a ′ ) − Q θ ( s , a ) ) , a ′ ∼ π ( s ′ ) . \mathcal{L}(\theta)=l_{\kappa}\left(r+\gamma Q_{\theta^{\prime}}(s^{\prime},a^{\prime})-Q_{\theta}(s,a)\right),\qquad a^{\prime}\sim\pi(s^{\prime}). (16) 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 ) D(s,a) can be computed almost exactly. However, in principle D ( s , a ) 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 ) .
## 4 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 ω G_{\omega} is learned and the highest valued action is selected after sampling actions from G ω 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 ω ( a | s ) ≈ π b ( a | s ) G_{\omega}(a|s)\approx\pi_{b}(a|s) , and instead utilize some threshold to eliminate actions: π ( s ) = argmax a | G ω ( a | s ) / max a ^ G ω ( a ^ | s ) > τ Q θ ( s , a ) . \pi(s)=\argmax_{a|G_{\omega}(a|s)/\max\hat{a}~G_{\omega}(\hat{a}|s)>\tau}Q_{\theta}(s,a). (17) 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: ℒ ( θ ) = l κ ( r + γ max a ′ | G ω ( a ′ | s ′ ) / max a ^ G ω ( a ^ | s ′ ) > τ Q θ ′ ( s ′ , a ′ ) − Q θ ( s , a ) ) . \mathcal{L}(\theta)=l_{\kappa}\left(r+\gamma\max_{a^{\prime}|G_{\omega}(a^{\prime}|s^{\prime})/\max\hat{a}~G_{\omega}(\hat{a}|s^{\prime})>\tau}Q_{\theta^{\prime}}(s^{\prime},a^{\prime})-Q_{\theta}(s,a)\right). (18) With this threshold τ \tau , we maintain the original property of BCQ where setting τ = 0 \tau=0 returns Q-learning and τ = 1 \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 θ Q_{\theta} , and evaluating with the target Q-network Q θ ′ Q_{\theta^{\prime}} : ℒ ( θ ) = l κ ( r + γ Q θ ′ ( s ′ , a ′ ) − Q θ ( s , a ) ) , a ′ = argmax a ′ | G ω ( a ′ | s ′ ) / max a ^ G ω ( a ^ | s ′ ) > τ Q θ ( s ′ , a ′ ) . \mathcal{L}(\theta)=l_{\kappa}\left(r+\gamma Q_{\theta^{\prime}}(s^{\prime},a^{\prime})-Q_{\theta}(s,a)\right),\qquad a^{\prime}=\argmax_{a^{\prime}|G_{\omega}(a^{\prime}|s^{\prime})/\max\hat{a}~G_{\omega}(\hat{a}|s^{\prime})>\tau}Q_{\theta}(s^{\prime},a^{\prime}). (19)
The generative model G ω 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 .
## 5 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 ϵ = 0.2 \epsilon=0.2 for the whole episode with p = 0.8 p=0.8 and ϵ = 0.001 \epsilon=0.001 with p = 0.2 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 10 million data points, where the offline agents are trained with 4 × 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.
## 6 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.
## Appendix A Experimental Details
### A.1 Atari Preprocessing.
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.