Benchmarking Batch Deep Reinforcement Learning Algorithms — part 1/3
Cleaned-text code points [0, 15959). Bibliography omitted here; source.md includes it.
# Benchmarking Batch Deep Reinforcement Learning Algorithms
###### Abstract
Widely-used deep reinforcement learning algorithms have been shown to fail in the batch setting–learning from a fixed data set without interaction with the environment. Following this result, there have been several papers showing reasonable performances under a variety of environments and batch settings. In this paper, we benchmark the performance of recent off-policy and batch reinforcement learning algorithms under unified settings on the Atari domain, with data generated by a single partially-trained behavioral policy. We find that under these conditions, many of these algorithms underperform DQN trained online with the same amount of data, as well as the partially-trained behavioral policy. To introduce a strong baseline, we adapt the Batch-Constrained Q-learning algorithm to a discrete-action setting, and show it outperforms all existing algorithms at this task.
## 1 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.
Our contributions are as follows: • 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.
## 2 Preliminaries
Reinforcement Learning. Reinforcement learning studies sequential decision making processes, generally formulated by a Markov decision process (MDP) ( 𝒮 , 𝒜 , p , r , γ ) (\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 ∈ 𝒜 a\in\mathcal{A} in state s ∈ 𝒮 s\in\mathcal{S} , and receives a new state s ′ ∈ 𝒮 s^{\prime}\in\mathcal{S} and reward r ( s , a , s ′ ) r(s,a,s^{\prime}) , in accordance to the transition dynamics p ( s ′ , r | s , a ) 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 = ∑ i = t + 1 ∞ γ i r ( s i , a i , s i + 1 ) R_{t}=\sum_{i={t+1}}^{\infty}\gamma^{i}r(s_{i},a_{i},s_{i+1}) , where the discount factor γ ∈ [ 0 , 1 ) \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 s to a distribution over actions.
For a given policy π \pi , we define the value function as the expected return of an agent following the policy Q π ( s , a ) = 𝔼 π [ R t | s , a ] Q^{\pi}(s,a)=\mathbb{E}_{\pi}[R_{t}|s,a] . Given Q π Q^{\pi} , a new policy π ′ \pi^{\prime} of equal or better performance can be derived by greedy maximization π ′ = argmax a Q π ( s , a ) \pi^{\prime}=\argmax_{a}Q^{\pi}(s,a) ( Sutton and Barto, 1998 ) . The optimal policy π ∗ = argmax Q ∗ ( s , a ) \pi^{*}=\argmax Q^{*}(s,a) , can be obtained by greedy selection over the optimal value function Q ∗ ( s , a ) = max π Q π ( s , a ) Q^{*}(s,a)=\max_{\pi}Q^{\pi}(s,a) . For γ ∈ [ 0 , 1 ) \gamma\in[0,1) the value function and optimal value function are the unique fixed points of the Bellman operator 𝒯 π \mathcal{T}^{\pi} and optimality operator 𝒯 ∗ \mathcal{T}^{*} , respectively ( Bellman, 1957 ; Bertsekas and Tsitsiklis, 1996 ) : 𝒯 π Q ( s , a ) \displaystyle\mathcal{T}^{\pi}Q(s,a) = 𝔼 s ′ , r , a ′ ∼ π [ r + γ Q ( s ′ , a ′ ) ] \displaystyle=\mathbb{E}_{s^{\prime},r,a^{\prime}\sim\pi}[r+\gamma Q(s^{\prime},a^{\prime})] (1) 𝒯 ∗ Q ( s , a ) \displaystyle\mathcal{T}^{*}Q(s,a) = 𝔼 s ′ , r [ r + γ max a ′ Q ( s ′ , a ′ ) ] . \displaystyle=\mathbb{E}_{s^{\prime},r}[r+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime})]. (2)
Deep Reinforcement Learning. In deep reinforcement learning, the value function is approximated by a neural network Q θ Q_{\theta} . In the Deep Q-Network algorithm (DQN) ( Mnih et al., 2015 ) , this value function Q θ Q_{\theta} is updated in a manner that approximates the optimality operator, through Q-learning ( Watkins, 1989 ) : ℒ ( θ ) = l κ ( r + γ max a ′ Q θ ′ ( s ′ , a ′ ) − Q θ ( s , a ) ) , \mathcal{L}(\theta)=l_{\kappa}\left(r+\gamma\max_{a^{\prime}}Q_{\theta^{\prime}}(s^{\prime},a^{\prime})-Q_{\theta}(s,a)\right), (3) where l κ l_{\kappa} defines the Huber loss ( Huber et al., 1964 ) : l κ ( δ ) = { 0.5 δ 2 if δ ≤ κ κ ( | δ | − 0.5 κ ) otherwise. , l_{\kappa}(\delta)=\begin{cases}0.5\delta^{2}&\text{if }\delta\leq\kappa\\ \kappa(|\delta|-0.5\kappa)&\text{otherwise.}\end{cases}, (4) but is generally interchangeable with other losses such as mean-squared error. A target network Q θ ′ 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 ′ ) (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 π b \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 ′ a^{\prime} (Eqn. 3 ), such that ( s ′ , a ′ ) (s^{\prime},a^{\prime}) is distant from data contained in the batch, the estimate Q θ ′ ( s ′ , a ′ ) 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 ′ a^{\prime} , which occurs naturally as long as the behavioral policy is similar to the target policy.
## 3 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 K τ \tau -quantiles of the return distribution, { τ } K = { i + 0.5 K } i = 0 K − 1 \{\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 K -dimensional vector representing these quantiles. A pairwise loss between each quantile is computed, similarly to DQN: ℒ ( θ ) = 1 K 2 ∑ τ ∑ τ ′ l τ ( r + γ max a ′ Q θ ′ τ ′ ( s ′ , a ′ ) − Q θ τ ( s , a ) ) , \mathcal{L}(\theta)=\frac{1}{K^{2}}\sum_{\tau}\sum_{\tau^{\prime}}l_{\tau}\left(r+\gamma\max_{a^{\prime}}Q^{\tau^{\prime}}_{\theta^{\prime}}(s^{\prime},a^{\prime})-Q^{\tau}_{\theta}(s,a)\right), (5) where l τ l_{\tau} is a weighted variant of the Huber loss, denoted the quantile Huber loss: l τ ( δ ) = | τ − 𝟙 δ < 0 | l κ ( δ ) . l_{\tau}(\delta)=|\tau-\mathbbm{1}_{\delta<0}|l_{\kappa}(\delta). (6) 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: π ( s ) = argmax a 1 K ∑ τ Q θ τ ( s , a ) . \pi(s)=\argmax_{a}\frac{1}{K}\sum_{\tau}Q^{\tau}_{\theta}(s,a). (7)
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 K -dimensional vector. During each update, this vector is combined with a convex combination of K K weights α k \alpha_{k} sampled from a ( K − 1 ) (K-1) -simplex: ℒ ( θ ) = l κ ( r + γ max ∑ k a ′ α k Q θ ′ k ( s ′ , a ′ ) − ∑ k α k Q θ k ( s , a ) ) . \mathcal{L}(\theta)=l_{\kappa}\left(r+\gamma\max_{a^{\prime}}\sum_{k}\alpha_{k}Q^{k}_{\theta^{\prime}}(s^{\prime},a^{\prime})-\sum_{k}\alpha_{k}Q^{k}_{\theta}(s,a)\right). (8) The policy is defined by the argmax over the mean of the output vector π = argmax a 1 K ∑ Q θ k ( s , a ) \pi=\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 π b \pi_{b} , and are therefore unlikely to be contained in the batch. At its core, BCQ uses a state-conditioned generative model G ω : 𝒮 → 𝒜 G_{\omega}:\mathcal{S}\rightarrow\mathcal{A} to model the distribution of data in the batch, G ω ≈ π b G_{\omega}\approx\pi_{b} akin to a behavioral cloning model. As it is easier to sample from π b ( a | s ) \pi_{b}(a|s) than model π b ( a | s ) \pi_{b}(a|s) exactly in a continuous action space, the policy is defined by sampling N N actions a i a_{i} from G ω ( s ) 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 ξ ϕ ( s , a ) \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 Q^{k}_{\theta} with k = { 1 , 2 } k=\{1,2\} : ℒ ( θ ) \displaystyle\mathcal{L}(\theta) = ∑ k ( r + γ max a ^ ( λ min k ′ Q θ ′ k ′ ( s ′ , a ^ ) + ( 1 − λ ) max k ′ Q θ ′ k ′ ( s ′ , a ^ ) ) − Q θ k ( s , a ) ) 2 , \displaystyle=\sum_{k}\left(r+\gamma\max_{\hat{a}}\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}, (9) where a ^ = a i + ξ ϕ ( s ′ , a i ) , a i ∼ G ω ( s ′ ) . \displaystyle\text{where }\hat{a}=a_{i}+\xi_{\phi}(s^{\prime},a_{i}),\qquad a_{i}\sim G_{\omega}(s^{\prime}). During evaluation, the policy is defined similarly, by sampling N N actions from the generative model, perturbing them and selecting the argmax: π ( s ) = argmax a ^ = a i + ξ ϕ ( s ′ , a i ) Q θ 0 ( s , a ^ ) , a i ∼ G ω ( s ) . \pi(s)=\argmax_{\hat{a}=a_{i}+\xi_{\phi}(s^{\prime},a_{i})}Q^{0}_{\theta}(s,\hat{a}),\qquad a_{i}\sim G_{\omega}(s). (10)