Title: GUMBELCLIP: OFF-POLICY ACTOR-CRITIC USING EXPERIENCE REPLAY

Abstract: This paper presents GumbelClip, a set of modifications to the actor-critic algorithm, for off-policy reinforcement learning. GumbelClip uses the concepts of truncated importance sampling along with additive noise to produce a loss function enabling the use of off-policy samples. The modified algorithm achieves an increase in convergence speed and sample efficiency compared to on-policy algorithms and is competitive with existing off-policy policy gradient methods while being significantly simpler to implement. The effectiveness of GumbelClip is demonstrated against existing on-policy and off-policy actor-critic algorithms on a subset of the Atari domain.

1. INTRODUCTION:

Recent advances in reinforcement learning (RL) have enabled the extension of long-standing methods to complex and large-scale tasks such as Atari (Mnih et al., 2015) , Go (Silver et al., 2016) , and DOTA (OpenAI, 2018) . The key driver has been the use of deep neural networks, a non-linear function approximator, with the combination usually referred to as Deep Reinforcement Learning (DRL) (LeCun et al., 2015; Mnih et al., 2015) . However, deep learning-based methods are usually data-hungry, requiring millions of samples before the network converges to a stable solution. As such, DRL methods are usually trained in a simulated environment where an arbitrary amount of data can be generated.

RL algorithms can be classified as either learning in an off-policy or on-policy setting. In the onpolicy setting, an agent learns directly from experience generated by its current policy. In contrast, the off-policy setting enables the agent to learn from experience generated by its current policy or/and other separate policies. An algorithm that learns in the off-policy setting has much greater sample efficiency as old experience from the current policy can be reused; it also enables off-policy algorithms to learn an optimal policy while executing an exploration-focused policy (Sutton et al., 1998) .

The most famous off-policy method is Q-Learning (Watkins & Dayan, 1992) which learns an actionvalue function, Q(s, a), that maps the value to a state s and action a pair. Deep Q-Learning (DQN), the marriage of Q-Learning with deep neural networks, was popularised by Mnih et al. (2015) and used various modifications, such as experience replay, for stable convergence. Within DQN, experience replay (Lin, 1992) is often motivated as a technique for reducing sample correlation.

Unfortunately, all action-value methods, including Q-Learning, have two significant disadvantages. First, they learn deterministic policies, which cannot handle problems that require stochastic policies. Second, finding the greedy action with respect to the Q function is costly for large action spaces. To overcome these limitations, one could use policy gradient algorithms (Sutton et al., 2000) , such as actor-critic methods, which learn in an on-policy setting at the cost of sample efficiency.

The ideal solution would be to combine the sample efficiency of off-policy algorithms with the desirable attributes of on-policy algorithms. Work along this line has been done by using importance sampling (Degris et al., 2012) or by combining several techniques together, as in ACER (Wang et al., 2016) . However, the resulting methods are quite complex and require many modifications to existing algorithms.

This paper, proposes a set of adjustments to A2C (Mnih et al., 2016) , a parallel on-policy actor-critic algorithm, enabling off-policy learning from stored trajectories. Therefore, our contributions are as follows:

• GumbelClip, a fully off-policy actor-critic algorithm, the result of a small set of simple adjustments, in under 10 lines of code (LOC)1 , to the A2C algorithm. • GumbelClip has increased sample efficiency and overall performance over on-policy actorcritic algorithms, such as A2C. • GumbelClip performs similarily to other off-policy actor-critic algorithms, such as ACER, while being significantly simpler to implement.

The paper is organized as follows: Section 2 covers background information, Section 3 describes the GumbelClip algorithm, Section 4 details the experiments along with results, discussion, and ablations of our methodology. Section 5 discusses possible future work, and finally Section 6 provides concluding remarks. At each time step t, the agent observes the environment state s t ∈ S, chooses an action a t ∈ A from its policy π(a t |s t ), and receives a reward r t from the environment. The goal of the agent is to maximize the discounted future return G t = ∞ k=0 γ k r t+k+1 . The discount factor γ ∈ [0, 1) trades off the importance of immediate and future rewards. Following from this, the value function of a policy π, in a discounted problem, is defined as the expected return V π (s t ) = E a∼π [G t |S t = s] and its action-value counterpart as

2. BACKGROUND AND NOTATION:

Q π (s t , a t ) = E a∼π [G t |S t = s, A t = a].

2.2. POLICY GRADIENT METHODS:

To optimize the parameters θ of the stochastic policy π the policy gradient theorem (Sutton et al., 2000) is used, which provides an expression for the gradient of the discounted reward objectives with respect to parameter θ. Therefore, the parameters θ of the differentiable stochastic policy π θ (a t |s t ) are updated as:

∇ θ J(θ) = E π [Ψ π (s t , a t )∇ θ log π θ (a t |s t )]

(1) where Ψ π (s t , a t ), as shown by Schulman et al. (2015b) , can be replaced with quantities such as: the total reward of the trajectory, the TD residual, or the state-action value function Q π (s t , a t ). The choice of Ψ π affects the variance of the estimated gradient. This work uses the advantage function A π (s t , a t ) = Q π (s t , a t ) -V π (s t ), which provides a relative measure of value for each action. The advantage function helps to reduce the variance of the gradient estimator while keeping the bias unchanged.

2.3. GUMBEL-SOFTMAX DISTRIBUTION:

The Gumbel-Softmax distribution (GSD) (Jang et al., 2016) is a continuous distribution used to approximate samples from a categorical distribution. The GSD uses standard Gumbel noise to sample directly from the softmax distribution. On its own, the Gumbel distribution is typically used to model the maximum of a set of independent samples. Given categorical class probabilities π 1 , π 2 , ..., π k the Gumbel-Softmax distribution is defined as: where g 1 ...g k are i.i.d. samples drawn from Gumbel(0, 1) and τ is a temperature hyperparameter.

EQUATION

The temperature hyperparameter τ , interpolates between a one-hot-encoded categorical distribution and a continuous categorical distribution. In this work, τ = 1. Additional choices of τ and their effects are shown in Figure 1 .

2.4. IMPORTANCE SAMPLING:

In practice, the policy gradient is estimated from a trajectory of samples generated by the on-policy stationary distribution π(a|s). This limits the efficiency of typical policy gradient methods, such as actor-critic, compared to methods like Deep Q-Learning which can learn off-policy. A common approach to using off-policy samples is a technique known as importance sampling (Degris et al., 2012; Meuleau et al., 2000; Jie & Abbeel, 2010; Levine & Koltun, 2013) .

Given a trajectory of samples generated by some behaviour policy B(a|s), the policy gradient from Equation 1 is modified to be:

∇ θ J(θ) = E B ρ t Ψ π (s t , a t )∇ θ log π θ (a t |s t ) (3)

where ρ is the known as the importance weight and is defined as a ratio between the current policy π(a|s) and the behaviour policy B(a|s):

EQUATION

Unfortunately, the importance weighted gradient in Equation 3 suffers from high variance. To reduce variance, Wawrzyński (2009) proposed truncating each importance weight to the interval [0, c] where c is some constant.

3. GUMBELCLIP:

GumbelClip builds off the on-policy actor-critic algorithm A2C. To enable off-policy learning Gum-belClip uses clipped importance sampling, policy forcing through Gumbel noise, and large batches sampled from a replay memory. Psuedo-code for GumbelClip is provided in Algorithm 1. We begin by defining a few quantities.

In importance weighting, two policy classes exist: the current policy π(a|s; θ) and the behaviour policy B(a|s). Because replay memory is being used, the behaviour policy is simply the distribution over actions with an old parameter setting θ * :

B(a t |s t ) = π(a t |s t ; θ * ) (5)

GumbelClip introduces a third policy, the forced policy F(a|s) using the Gumbel-Softmax distribution, which results from adding noise (i) sampled from a standard Gumbel distribution to the normalized logits of the current policy:

F(a (i) t |s t ) = exp (log π(a (i) t |s t ; θ) + (i) ) j=0 exp (log π(a (j) t |s t ; θ) + (j) ) (6)

As the name implies, adding Gumbel noise has the effect of "forcing" the sampled policy distribution to be more categorical such that one action contains most of the probability mass. As Equation 6 is identical to the Gumbel-Softmax distribution, with temperature τ = 1, we can refer to Figure 1b ) to understand the characteristics of the resulting sampled distribution. 

(•|s0), • • • , s k , a k , r k , B(•|s k )} from the replay memory D. for i ∈ {0, • • • , k} do Compute π(•|si; θ) and F(•|si). ρi = clamp F (a i |s i ) B(a i |s i ) , 0, c end for R ← 0 for terminal s k V (s k ; θv) otherwise Reset gradients: dθ ← 0 and dθv ← 0. for i ∈ {k -1, • • • , 0} do R ← 0 for terminal si ri + γR otherwise

Accumulate gradients dθ ← dθ + ρi∇θ log F(ai|si) R -V (si; θv) Accumulate gradients dθv ← dθv + ∇ θv (R -V (si; θv)) 2 end for Perform update of θ using dθ and θv using dθv. until Max iteration or time reached.

Similarly to previous work, this study uses importance sampling ρ to weight the updates of the loss function. However, instead of using the current policy, π(•|s t ), in the numerator, it is replaced with the forced policy F(a t |s t ):

ρ (i) t = F(a (i) t |s t ) B(a (i) t |s t ) (7)

The range of ρ t is clipped to [0, c] and this clipped importance weight is referred to as ρt . Clipping the upper bound prevents the product of many importance weights from exploding and reduces the variance (Wawrzyński, 2009) . Putting this all together the update equation for GumbelClip is as follows:

EQUATION

The gradient is estimated by uniformly sampling b trajectories of length k from a replay memory with size N . In addition, the network parameters are updated using the forced policy F(a|s). The advantage function

A(s t , a t ) = R (k) t -V (s t ) is used, where R (k) t

is the bootstrapped k-step return for time t.

As the forced policy in the numerator tends towards a categorical distribution, it became evident that the importance weights had the habit of clumping near the boundaries of the interval and often near ~1. Following from Figure 2 , we can see the distribution of the ratio between GumbelClip and a typical application of truncated importance sampling to A2C as might be suggested by Wawrzyński (2009) . Figure 2 (a) shows this behaviour if one were to implement truncated importance sampling The effect of clipping and Gumbel noise has an interesting effect on the way the policy is updated.

From Figure 2 (b), we see that three modes exist, which roughly correspond to the cases of agreement and disagreement. The case of agreement corresponds to ratios and the mode near 1 while disagreements correspond to ratios and modes at 0 and c. More exactly, when the forced policy disagrees with the behaviour policy, say F(•|s) ≈ 1 and B(•|s) ≈ 0, the update the policy receives is at most clipped by the upper bound of our interval: c. On the other hand, when the situation is reversed, but still in disagreement, with F(•|s) ≈ 0 and B(•|s) ≈ 1, the policy has an importance weight of ~0.

4. EXPERIMENTS:

Our experiments focus on the Atari domain (Bellemare et al., 2013) as there exists a large amount of variety between environments and the states are represented as raw high-dimensional pixels. The gym software package by Brockman et al. (2016) was used to conduct all the experiments. All experiments used the same algorithm, network architecture, and hyper-parameters to learn to play Atari games using only raw pixel observations. This study used the same input pre-processing and network architecture as Mnih et al. (2016) . The network architecture consists of three convolutional layers as follows: 32 8 × 8 filters with stride 4, 64 4 × 4 filters with stride 2, and 32 3 × 3 filters with stride 1. The final convolutional layer feeds into a fully-connected layer with 512 units. All layers are followed by rectified non-linearity. Finally, the network outputs a softmax policy over actions and a state-value.

The experimental set-up used 16 threads running on a GPU equipped machine. All experiments trained for 40 million frames. A replay memory of size N = 250000 was kept, an update was performed every k = 5 steps in the environment, and a clamping coefficient of c = 4 was used. The optimization procedure used RMSProp (Hinton et al., 2012) with a learning rate of 5e -4, entropy regularization of 0.01, and a discount factor of γ = 0.99. We sample 64 trajectories of length 5 for each update. Learning begins after we have collected 10, 000 samples in the replay memory. We tuned the hyperparameters and developed GumbelClip on the FishingDerby environment only; the other environments can be considered "out of sample". All experiments used the same hyperparameter settings and network architecture. We use the best 3 of 4 seeds and report the mean value with 1 standard deviation as shaded areas on all graphs. As GumbelClip uses larger batchsizes we see an improvement in total run time per seed of 6-7 hours over A2C which takes 9-10 hours per seed.

Due to limited computational resources, we were only able to evaluate GumbelClip on a subset of the environments and with a smaller replay memory size. Therefore, in this study, an effort was made to select environments that best showcase the performance of off-policy (ACER) and on-policy (A2C)

Figure 3 : Training performance across 8 Atari games. We see the performance of GumbelClip (shown in blue) against ACER (shown in green), an off-policy actor-critic algorithm, and the onpolicy algorithm A2C (shown in red). The graphs show the average performance over 3 seeds with 1 standard deviation shown as the shaded region. GumbelClip matches or exceeds the performance of the on-policy algorithm on all environments shown; while in all cases achieving improved convergence speed. It also shows a respectable performance when compared to the ACER algorithm on many of the environments.

actor-critic methods. We note that the performance can be expected to improve with a larger replay memory, as seen with DQN and other methods using replay memory. Additionally, we focused the examination of our ablations on the Alien environment to reduce computational requirements.

GumbelClip is based on a modified version of the open-source A2C implementation by Kostrikov (2018) . The present work was compared with an off-policy actor-critic algorithm, ACER (Wang et al., 2016) , and an on-policy actor-critic algorithm, A2C, the synchronous version of A3C (Mnih et al., 2016) . Both baseline models, A2C and ACER, used the baselines package provided by Ope-nAI (Dhariwal et al., 2017) . ACER used a replay ratio of 4, trust region updates (Schulman et al., 2015a) , a discount factor of γ = 0.99, entropy regularization of 0.01, updated every 20 steps, and a 50000 capacity replay memory per thread.

4.1. EXPERIMENTAL RESULTS:

To test the proposed methodology, the performance of GumbelClip on a subset of Atari environments was examined. In particular, the following environments were investigated: Alien, BeamRider, Boxing, FishingDerby, MsPacman, Qbert, Seaquest, and SpaceInvaders. We report the average reward every 1000 episodes over 40 million frames. As mentioned previously, environments were chosen where either the on-policy algorithms perform well or where there is a clear difference in performance between an off-policy and on-policy method.

From Figure 3 , we see the performance of GumbelClip, shown in blue, in comparison to the onpolicy ACER algorithm, shown in green, and the off-policy A2C algorithm. We see that the use of replay memory and learning with off-policy samples significantly improves the sample efficiency of GumbelClip over A2C. Across the board, we see that GumbelClip converges significantly faster than A2C while also exceeding A2C's performance.

We achieve similar sample efficiency between the off-policy actor-critics, GumbelClip and ACER, across each environment. The additive noise and aggressive clamping seem to have both positive and negative effects. We see that GumbelClip sees a faster initial increase in performance across almost all environments, even outperforming ACER in some cases. However, clamping has been noted by Wang et al. (2016) to have the possibility of introducing bias. We hypothesize this might be the cause of poor performance on the Qbert environment, which while better than A2C, is much lower when compared to ACER. The benefit of GumbelClip comes from its simplicity, requiring a small number of easy changes to the A2C algorithm, while still providing better performance than other on-policy actor-critic algorithms.

4.2. WILL OTHER DISTRIBUTIONS WORK FOR NOISE GENERATION?:

Figure 4 : Variations in distributions used to sample additive noise. We compare the impact of noise drawn from the standard Gumbel distribution to the standard Normal distribution and Uniform distribution between [0, 1].

Here we examine the distribution used to draw the additive noise (i) for use in the forced policy F(a|s). We compare the performance of noise sampled from the standard Gumbel distribution to that of the standard Normal distribution and the Uniform distribution [0, 1].

The experiments only adjust the sampling distribution with no other parameter changes. We investigate the performance on the Alien Atari game over 40 million frames. From the results in Figure 4 , we see that the Gumbel and Normal distributions have the same initial rate of improvement but diverge roughly midway through training. The Normal distribution appears to degrade in performance before becoming stable at ~1500. The uniform distribution, sampled between [0, 1], has the same convergence characteristic as the other two distributions but instead of diverging away, similar to the Normal distribution, it continues upward before converging at ~2000. From Figure 4 , we see that the Gumbel distribution is the most performant. 

4.3. STABILITY:

It is natural to inquire on the stability of this method, as we rely on additive noise which could cause instability after an optimal policy has been reached. To this end, we evaluate the stability of GumbelClip by increasing the number of training iterations such that 150 million frames are seen. The Boxing and FishingDerby environments are used for this evaluation. The environments were chosen as the policy had achieved the highest score during training, a known ceiling, and any instability would cause a divergence to a sub-optimal policy. From the rather uninteresting graphs, shown in Figure 5 , we see that GumbelClip can converge to and maintain a stable policy even with continued parameter updates. To overcome the noise added by the Gumbel distribution requires the network to output a near one-hot-encoded categorical distribution.

4.4. ABLATIONS:

In our final set of experiments, we performed ablations over the various components of GumbelClip to tease apart the cause of improvements in performance. The results of the ablation are shown in Figure 6 (a) with the complete GumbelClip algorithm in blue and each stripped version of Gumbel-Clip as a red curve. We start with a base version, which is the application of truncated importance sampling and replay memory to the off-policy algorithm A2C; this base version is shown in the leftmost panel in Figure 6 (a). From Table 6 (b) we see that the base version has a performance -39.39%

5. FUTURE WORK:

As GumbelClip relies heavily on the Gumbel distribution to sample noise from, it is best suited to environments with discrete actions. Therefore, an interesting avenue for future work would be to find a suitable distribution to sample noise from that works with continuous actions.

Additionally, further investigation into possible annealing schedules for a temperature hyperparameter, in Equation 6, or around the clamping constant c could yield interesting results.

6. CONCLUSION:

In this paper we have presented GumbelClip, a set of adjustments to the on-policy A2C algorithm, enabling full off-policy learning from stored trajectories in a replay memory. Our approach relies on aggressive clipping of the importance weight, large batchsize, and additive noise sampled from the Gumbel distribution. We have empirically validated the use of each component in GumbelClip through ablations and shown the stability of the algorithm.

Furthermore, we have shown that GumbelClip achieves superior performance and higher sample efficiency than A2C. GumbelClip nears the performance and sample efficiency of ACER on many of the tested environments. Our methodology requires minimal changes to the A2C algorithm, which in contrast to ACER, makes the implementation of GumbelClip straightforward.

:

Assuming code for replay memory is available.

Figures and Tables:

Figure 1: Gumbel-Softmax distribution: The temperature parameter τ controls the interpolation between discrete one-hot-encoded categorical distributions and continuous categorical densities. As τ → 0 samples from the Gumbel-Softmax distribution are identical to those from a categorical distribution. If τ → ∞ then the samples tend towards a uniform distribution. At τ = 1 the samples wash out the smaller values and accentuate high density areas. Figure used with permission of Jang et al. (2016).

Figure 2: Histograms of ratios. The x-axis is the magnitude of ρ and the y-axis is the number of updates since start of training. a) Using truncated ρ with the current policy in the numerator and b) the ratios seen during training from GumbelClip, which corresponds to use of the forced policy in the numerator.

Figure 5: Stability of GumbelClip with extended training time. GumbelClip is trained for 150M frames, ~4x longer, on the Boxing and FishingDerby environments. We see that GumbelClip experiences little to no oscillations in performance even with continued weight updates.

Algorithm 1 Pseudo-code for GumbelClip Initialize parameters θ and θv. Initialize replay memory D with capacity N . repeat for i ∈ {0, • • • , k} do Perform ai according to π(•|si; θ). Receive reward ri and new state si+1. Store (si, ai, ri, π(•|st)) in D. end for Sample b trajectories {s0, a0, r0, B

Table content: <table/>

Peer review (iclr2020):
Overall I don*t really understand *why* the Gumbel-softmax *forced* policy is used over the standard policy. There is no discussion on the motivation at all. Using the *wrong* policy in importance sampling will increase the bias of the updates, and possibly the variance. Furthermore, the point of using the Gumbel-softmax in other situations is to avoid the use of reinforce, however in this paper policy gradient (basically reinforce) is used anyway. On top of this there are no theoretical results showing that this approach is principled in any way. The experimental results are not enough justification. Fig. 1 is very confusing, it took me a long time to understand what the *sample* row was trying to show me. This is made extra confusing by eq 2 which is introduced using *the Gumbel-Softmax distribution is defined as*, which, despite the claim, is not the definition of a distribution but actually the definition of a *sample* from the distribution. Several of the claims in the introduction are plain wrong, e.g., *Unfortunately, all action-value methods, including Q-Learning, have two significant disadvantages. First, they learn deterministic policies, which cannot handle problems that require stochastic policies. Second, finding the greedy action with respect to the Q function is costly for large action spaces.* The claim that it holds for *all* action-value methods is wrong. Moreover the claim that finding the greedy action is costly is just bizarre, since that amounts to simply taking a max over a set of numbers, whereas any policy method requires sampling from a set of probabilities of the same size - much harder to do! Paper is over the 8 page limit, but without really needing to be. I think some content could be removed. Three very relevant papers that I am surprised are missing are the following: PGQ: https://arxiv.org/abs/1611.01626 This uses the duality between value methods and policy methods to derive an off-policy algorithm. I really think a comparison to this approach is needed, especially because it is also much simpler than ACER to implement, and it doesn*t require access to the old policy. RETRACE: https://arxiv.org/abs/1606.02647 Another importance weighted approach, must be mentioned (ACER is based on this). V-trace (in IMPALA): https://arxiv.org/abs/1802.01561 Follow-up work to RETRACE, also very relevant.