{'fraction_non_alphanumeric': 0.04295504704379138, 'fraction_numerical': 0.013938901149959345, 'mean_word_length': 4.405072827724761, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 5, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Adaptive Experience Selection for Policy Gradient

Policy gradient reinforcement learning (RL) algorithms have achieved impressive performance in challenging learning tasks such as continuous control, but suffer from high sample complexity. Experience replay is a commonly used approach to improve sample efficiency, but gradient estimators using past trajectories typically have high variance. Existing sampling strategies for experience replay like uniform sampling or prioritised experience replay do not explicitly try to control the variance of the gradient estimates. In this paper, we propose an online learning algorithm, adaptive experience selection (AES), to adaptively learn an experience sampling distribution that explicitly minimises this variance. Using a regret minimisation approach, AES iteratively updates the experience sampling distribution to match the performance of a competitor distribution assumed to have optimal variance. Sample non-stationarity is addressed by proposing a dynamic (i.e. time changing) competitor distribution for which a closed-form solution is proposed. We demonstrate that AES is a low-regret algorithm with reasonable sample complexity. Empirically, AES has been implemented for deep deterministic policy gradient and soft actor critic algorithms, and tested on 8 continuous control tasks from the OpenAI Gym library. Ours results show that AES leads to significantly improved performance compared to currently available experience sampling strategies for policy gradient.


I. INTRODUCTION
Reinforcement learning (RL) is a computational approach for solving sequential decision-making problems under uncertainty [1]. In these problems, typically an agent interacts over time with the environment and learns to take actions according to an optimal policy that maximises the cumulative future expected rewards. Recent advances in RL have adopted deep neural networks as high-capacity function approximators resulting in deep reinforcement learning (DRL) [2]. DRL has yielded impressive results in a number of tasks, including learning to play Atari games [3], controlling robots from raw images [4], and mastering the game of Go [5].
Policy gradient algorithms [6]- [11] seek the optimal policy by operating directly on the gradient of accumulated rewards taken with respect to the policy parameters. These methods have reached excellent performance in problems with large and/or continuous action spaces [12]. In its simplest formulation, the policy gradient is estimated from trajectories 1 generated by the current policy (i.e. on-policy) [6], [10], [11], [13]. On-policy gradient estimators are unbiased, but contemporary algorithms suffer from low sample efficiency. This is because a new set of trajectories need to be generated for each policy update, i.e. at every step.
To improve sample efficiency, experience replay (ER) [14] is commonly used. This approach works by storing trajectories generated by past policies and reusing them to estimate the policy gradient. ER leads to off-policy algorithms, i.e. the gradient of the current policy is estimated using trajectories generated by different policies [7], [15]- [17]. In these algorithms, the divergence between current and past policies leads to bias in gradient estimators, which is often corrected by employing an importance sampling ratio in the off-policy gradient estimator. However, this ratio is unbounded and can yield high (or even infinite) variance [18]- [21]. Such high variance compromises the algorithm's convergence, resulting in increased sample complexity and hindering effective learning.
To reduce the variance in off-policy gradient estimators, several approaches have focused on seeking estimators with better bias-variance trade-offs [7], [16], [22]- [26]. Most of these variance reduction algorithms uniformly sample trajectories from the replay butter to compute the gradients. Improved experience replay sampling methods have also been studied. A representative methodology is prioritised experience replay [27] which identifies the most important trajectories and sample them more frequently to improve learning efficiency whereas the the importance of a trajectory is determined by the temporal-difference error of transitions. Other experience replay sampling strategies have also been proposed such as distributed prioritized experience replay [28], and methods that depend on the propagation of sample priority [29], curiosity [30], the divergence between trajectories and current policy [31], and a method to learn a separate policy for experience sampling [32]. Although the available experience sampling methods can often achieve better performance compared to uniform sampling, none of them explicitly address the high variance issue.
In this paper, we learn a sampling distribution for selecting samples from the ER buffer to compute the gradient at each step. Unlike existing approaches, our aim is to adaptively choose this sampling distribution so that it explicitly minimises the variance of the gradient estimates. This is achieved through an online regret minimisation approach [33], which we call Adaptive Experience Selection (AES), whereby the sampling distribution is updated in a sequential manner during the learning phase. We assume that there exists an unknown competitor distribution that has optimal variance. AES attempts to update the current sampling distribution in order to match the competitor's variance. To address the non-stationarity of samples in the experience replay buffer, which is due to the process of sample insertion and over-writing, we consider the case of a dynamic (i.e. time-varying) competitor distribution. We demonstrate that AES leads to a closed-form solution of the sampling distribution, and has low regret and reasonable sampling complexity. Empirically, we have implemented AES with two representative DRL algorithms, deep deterministic policy gradient (DDPG) [9] and soft actor critic (SAC) [34], and have examined the performance on 8 continuous control tasks in OpenAI Gym library. We show that AES achieves significantly improved performance compared to existing experience sampling strategies.

II. BACKGROUND A. Markov Decision Processes
We consider sequential decision making problems whereby an agent interacts with an environment, and the decision process is modelled as discrete-time Markov Decision Process (MDP). A MDP is defined by a tuple M = {S, A, P, r, γ, ρ 0 }, where S is the state space; A is the action space; P : S × A × S → R is the transition probability distribution, r : S × A → R is the reward function, γ ∈ (0, 1) is the discounting factor and ρ 0 : S → R the initial state distribution. At a timestep t, the agent observes the current state s t ∈ S and takes an action according to a policy a t ∼ π θ (a t |s t ) with θ denoting policy parameters. Then, the environment moves to the next state s t+1 ∼ P (s t+1 |s t , a t ), and the agent receives a reward r (s t , a t ). With s 0 ∼ ρ 0 , and after following a fixed policy π θ for H steps, a trajectory τ = (s 0 , a 0 , s 1 , a 1 , ..., t=0 γ t r(s t , a t ) be the return for τ . RL aims to maximise the expected return, denoted by J: where p(τ |π θ ) is the trajectory distribution under policy π θ , and is defined as: B. Policy gradient and experience replay On-policy methods. Policy gradient methods update θ along the direction of ∇ θ J (θ) to maximise J (θ). It can be shown that ∇ θ J (θ) can be expressed as [6]: The analytical expression of Eq. 3 is difficult to obtain, since environmental knowledge like transition probabilities and reward functions are difficult to obtain. Alternatively, Monte Carlo methods are widely used to estimate the expectation in Eq. 3 from trajectories only. The corresponding Monte Carlo estimator for Eq. 3 is: where τ k is the k th trajectory in Monte Carlo sampling.∇J(θ) is an unbiased estimator of ∇J(θ), when τ k is generated by π θ . This can be shown by taking expectation with respect to τ k ∼ p(τ k |π θ ) over the right hand side of Eq. 4. On policy RL algorithms [10], [11], [13] run the current policy to obtain τ k . After θ is updated, a new τ i is obtained under the new policy. This procedure requires to generate a large amount of new trajectories for each policy update, thus resulting in low sample efficiency.
Off-policy methods. To increase sample efficiency, offpolicy RL algorithms [7], [15]- [17] update the current policy using existing trajectories generated by previous, hence different, policies. Considering a target policy π θ to maximise J (θ) and a behaviour policy denoted by µ to generates trajectories for Monte Carlo gradient estimate, Eq. 3 can be rewritten as: where ω (τ |π θ , µ) = p (τ |π θ )/p (τ |µ) is the importance weight ratio, and g (τ |π θ ) = ∇ log p(τ |π θ )R(τ ). Note that Eq. 5 samples τ from µ rather than π θ . This requires to introduce ω for the equivalence between Eq. 5 and Eq. 3. However, introducing ω results high variance. To see this, it suffices to note that, using Eq. 2, Eq. 6 is a product of many unbounded importance weight ratios. Therefore, if several µ (a t |s t ) have very low probabilities, the corresponding ratio π θ (a t |s t ) /µ (a t |s t ) can become very large; the product of these ratio can explode resulting in very high ω, and hence high variance. Alternative formulations for ω and g have been proposed to reduce the variance whilst keeping the bias low. For example, clipping [7], [23] or scaling [22] the ratios π θ (a t |s t ) /µ (a t |s t ) to prevent ω becoming too large; subtracting a baseline from g [7], [24], [35]; the baseline is designed to reduce the variance while adding little or no bias; taking the expectation in Eq. 5 with respect to individual state-action pairs rather than trajectories to alleviate the issue of exploding importance ratios by considering a marginal return function with limiting state distribution [7], [16].
Experience replay. Most off-policy RL algorithms use an experience replay buffer to store the trajectories generated by the current policy at each update. The policy gradient can be estimated using Eq. 5 from a batch of trajectories randomly sampled from the experience replay. Let B be the experience replay, and π θt be the policy parameters at timestep t. At a specific timestep t, the experience replay B may contain past trajectories π θ0 , π θ1 , ... π θt . Assuming a uniform sampling distribution over B, an unbiased Monte Carlo gradient estimator for Eq. 6 is: where Ψ is the set of sampled indexes for the trajectories in B, and l (k) is a function specifying the policy update step corresponding to the k th sample in B.

A. Problem Formulation
In this paper, we focus on off-policy policy gradient algorithms using experience replay. We seek a sampling distribution for the trajectories in the ER buffer such that the gradient estimator features the smallest possible variance whilst adding no bias. In this subsection, we present the proposed formulation.
Let U {1, |B|} be a discrete uniform distribution as commonly adopted for experience sampling. We rewrite Eq. 7 to incorporate the procedure of sampling experience replay into the policy gradient formulation: where the outer expectation is taken with respect to the sampled index in B, and the inner expectation is with respect to the selected trajectory. With Eq. 8, using |Ψ|-sample Monte Carlo estimator for the outer expectation and single-sample Monte Carlo estimator for the inner expectation, leads to the estimator in Eq. 7. This procedure can be expressed as firstly selecting Ψ then averaging the gradient over the selected trajectories. Instead of using uniform sampling, we aim to learn a sampling distribution that minimises the variance in the gradient estimate. Specifically, let p = [p(1), p(2), ..., p(|B|)] be a vector, where p(i) represents the sampling probability for the i th trajectory in B, and |B| i=1 p(i) = 1. Let M (1, p) be a multinomial distribution parameterised by p with single trial. The policy gradient formulation with M as experience sampling distribution can be obtained by rewriting Eq. 8: where τ ∼ p(τ |π θ l(k) ), and the ratio λ k = 1/p (k) |B| is the importance weight ratio. By using |Ψ|-sample Monte Carlo estimator for the outer expectation and single-sample Monte Carlo estimator for the inner expectation, we obtain a unbiased gradient estimator: We want to learn p so as to minimise the variance in each element of∇J(θ). Accordingly, we introduce the objective function: where Cov (·) is the covariance matrix, Diag (·) is an operator that extracts the diagonal elements in a square matrix and stacks them into a vector, and · is the Euclidean norm. The corresponding optimisation problem is: arg min p∈∆ f (p) (12) where ∆ is the probability simplex. The objective function in Eq. 11 can be expanded and simplified. Expanding f (p) using the definition of covariance leads to: For brevity, we write ω τ i |π θ , π θ l(i) as ω θ i and g (τ i |π θ ) as g θ i . The formulation for E∇J (θ) is: Thus, the second term in Eq. 13 does not depend on p, and can be ignored. On the other hand, let Assuming the Monte Carlo samples from B are i.i.d., the formulation for the first term in Eq. 13 can be obtained: According to Eq. 14, the constant B does not depend on p. By substituting Eq. 15 into Eq. 13 and ignoring the constants |Ψ|, |B| and B, our objective function is simplified to: In the rest of this section, we present the proposed algorithm, Adaptive Experience Selection (AES) used to minimise Eq. 16 in the context of off-policy RL. We start from the simplified setting where B is static, i.e. pre-filled, and the trajectories in B do not change. Then, we will consider the more general case where where sample insertions and overwriting are allowed during learning, as in general off-policy RL algorithms.

B. Experience selection with static experience replay
In off-policy RL, the policy parameters are updated repeatedly using trajectories sampled from B. In this setting, the optimisation in Eq. 12 requires an online learning formulation whereby p is updated at each policy update step using the observed data from all the previous steps. Specifically, let p t be the sampling distribution at a policy update step t. At a specific step T , we observe {θ t } T −1 t=1 and B; we firstly obtain p T by solving the following optimisation problem: Then, trajectories are sampled from B using p T as sampling distribution; a gradient estimate is made using Eq. 9; the gradient estimate is used to update θ T −1 to θ T with gradient descent. The above procedure is repeated for each policy update step.
Optimisation algorithms assuming full data observation and i.i.d sampling like stochastic gradient descend are less applicable in this context for two main reasons. First, θ t is revealed sequentially for different t, hence we have incremental observations. Second, the θ t 's are not i.i.d. as the policy parameters in subsequent steps depend on those in earlier steps. Here we resort to a regret minimisation approach to solve the above online learning problem. We define the regret at policy update step T , denoted by f R (T ), as: where the first term in brackets is our objective function at step T , and the second term is a competitor assumed to have optimal p. Ideally, we aim to update p to match the competitor's performance, formally lim T →∞ 1 T f R (T ) = 0. This is also referred to as non-regret.
Follow-the-regularised-leader (FTRL) is an effective approach to solve the regret minimisation problem in Eq. 18, and can be formulated as [36]: where the first term is our objective function; the second term is a regularisation term to avoid zero probability for any index; ν is a scalar balancing the two terms.
. It can be shown that Eq. 19 has a closed-form solution [36]: The update in Eq. 20 leads to a regret bounded by O( √ T ). To derive this, we need to make some assumptions on ∇J (θ) and environmental rewards. In the rest of the paper we consider the general policy gradient formulation in Eq. 5. However, the assumptions and derivations below are also applicable to other policy gradient formulations with different forms of ω and g as discussed in Section II-B. We make three assumptions: Assumption 1 (Lower-bounded policy function): There exists a real constant 0 < β ≤ 1, such that: Assumption 2 (Lipschitz differential policy function): There exists a real constant 0 ≤ L < ∞, such that:

Assumption 3 (Bounded rewards):
There exists a real constant 0 ≤ ζ < ∞, such that: Based on the above assumptions, a bound on d t is defined by the following lemma. Lemma 1. Given Assumptions 1, 2 and 3, we have the following bound: Proof. See Appendix A-A. Given Lemma 1, the regret is bounded by the following corollary. Corollary 1. Given Assumptions 1, 2 and 3, we have the following regret bound: Proof. The proof is straightforward by applying the above Lemma 1 with the Theorem 3 in [36].

C. Experience selection with partial gradient
Eq. 20 requires to compute the gradient for all the samples in B in all the policy update steps. Practically, this procedure is very computationally expensive, as |B| is usually in the order of millions. In this subsection, we aim to alleviate the computational load by using a subset of B to estimate p T . This scheme fits well into an off-policy RL setting where, at each step, some trajectories are sampled from B to estimate the policy gradient; the same trajectories can then be used to estimate p T . Let Ψ t be the index set of sampled trajectories in B at policy update step This leads to the following solution One problem of Eq. 22 is thatd t (i) is unbounded for i ∈ Ψ t . This leads to unbounded regret according to Lemma 1 and Corollary 1, as d t (i) /p t (i) is unbounded. A typical solution is to mix Eq. 22 with the probability mass function of a uniform distribution: where κ ∈ [0, 1] is a coefficient to balance between the closedform solution (the first term) and the uniform distribution (the second term). Sincep T (i) ≥ κ/|B|, we obtain a bound for d t (i) according to Lemma 1 Another effect of the uniform distribution in Eq. 23 is to improve exploration, as introducing uniform distribution encourages to sample each trajectory equally. In term of regret bound, we focus on expected regret as Eq. 23 is based on an estimator of d t (i). The following corollary demonstrates that Eq. 23 achieves a bound of O |B| for expected regret.
Under Assumptions 1, 2 and 3, and assuming T ≥ |B|, Eq. 23 leads to the following bound: Proof. Note that the optimal p does not depend onp t . Thus, the proof can be done by applying the Theorem 7 in [36] with Eq. 24.

D. Naive adaptive experience selection
The methods described in Section III-B and Section III-C assumes the experience replay is static, i.e. the experience replay is pre-filled and does not change over time. In off-policy RL, however, the experience replay is dynamically updated with new trajectories being inserted and old trajectories overwritten at every step. A naive application of the solution in Eq. 23 would reinitialise the sampling distribution each time new experiences are added into the buffer. Alg. 1 is the corresponding algorithm encapsulating this approach. Line 3 -11 generate trajectories using the current policy and store the trajectories into B. Line 12 resets ω(i) which equals to T −1 t=1d t (i) in Eq. 23. Line 14 updates the sampling distribution (analogous to Eq. 23). Line 15 samples from experience replay with the current sampling distribution and update policy parameters. Line 16 updates ω(i) in an incrementally.
A significant problem of Alg. 1 is that it is sample inefficient with regards to variance reduction. That is, it requires a significantly large number of samples to achieves low regret, as seen with the following results. Assumption 4 (Limited off-policy iterations). With Alg. 1, we have m < |B|/|Ψ|. Assumption 4 results m|Ψ| < |B|, i.e. we do not go through all the trajectories in |B| in a single epoch. This is reasonable in the RL context as doing so harms exploration and is very likely to get stuck into local optimum. Perform a t according to π θ (.|s t ) 8: Get reward r t and next state s t+1 9: Add experience (s t , a t , π θ (a t |s t ), r t , s t+1 ) into B 10: Sample index set Ψ t from B using p t as sampling distribution; use the corresponding trajectories in B to update the policy parameters from θ to θ t using off-policy policy gradient algorithms like DDPG or SAC 16: Use the computed gradients in the step 15 to computẽ Update current policy θ ← θ t

18:
end for 19: end for implying that T < C 2 |B| |Ψ| , for any constant C > 0, Alg. 1 achieves the following bound: Corollary 3 demonstrates that for Alg. 1 to achieve regret bound less than , it requires number of samples nb > H |B|C 2 3 . Moreover, the condition T < C 2 |B| |Ψ| restricts the number of iterations allowed for the bound to hold. Primarily to achieve certain regret bound the number of iterations needs to be high. For higher T , we need to increase C meaning that m = T C 2 goes down resulting in less RL updates and lower RL convergence rate.

E. Non-regret adaptive experience selection
In this subsection, we extend the methods described in Section III-B and Section III-C to general experience replay, i.e. when new experiences can be added on-the-fly and old experiences can be overwritten. This extension leads to a lowregret experience selection algorithm. In this more general setting, the optimal sampling distribution changes continuously as new experiences are being added into the buffer. Accordingly, we consider a regret minimisation model with a dynamic competitor formulated as The second term allows the competitor to choose different optimal sampling distribution for each policy update steps. To derive a solution, we make the following assumption. Assumption 5 (Lipschitz continuous gradient). There exists a real constant 0 < K < ∞, such that: This is a mild smoothness assumption that holds for most models, particularly neural networks. Assumption 6 (PL inequality). There exists a real constant ξ > 0, such that: where θ * = arg min θ J (θ). This PL inequality assumption [37] is a bit stronger than the smoothness assumption. Examples of functions satisfying PL condition include neural networks with one-hidden layers, ResNets with linear activation and objective functions in matrix factorisation [38].
It follows that we can bound the dynamic regret in Eq. (25) given that the change in f t (p) is small for consecutive steps. This smooth change can be guaranteed if only a very small portion of B is changed between two consecutive steps, which is common for off-policy RL algorithms. We propose Adaptive Experience Selection (AES) algorithm that exploits this smooth changing properties by regularly forgetting the influence of f t (p) for old t. AES updates p using FTRL and reset p every M steps. This is formally formulated as where T 0 = max(1, T /M M ) is the starting index of the M -step interval that T falls in, with · the floor function.
Eq. 26 has a closed-form solution similarly to Eq. 20: Equation 27 is computationally expensive, since this formulation requires to calculate the gradient for all the trajectories in B. Similarly to Section III-C, we alleviate the computational load by making an unbiased estimate of d t using the sampled trajectories in each policy update step. This leads to the following update similarly to Eq. 23: The expected regret with Eq. 28 is bounded by the following Theorem. Theorem 1. Under assumption 1, 2, 3, 5, 6. Given a condition on the learning rate according to the smoothness degree of g θ i : α t < 1 K and a condition on the severity of overwriting M 2 < |B|. Eq. 28 leads to the following bound: According to Theorem 1, setting M = T C leads to sub-linear regret bound with respect to T : However, the condition M 2 < |B| implies T < C |B| which restricts the number of iterations allowed for the bound to hold. Hence, there is a trade-off between the bound that can be achieved and the number of iteration T allowed to achieve that bound. Note that primarily to achieve certain regret bound the number of iterations needs to be high. Thus, to relax the restriction on T , we set M = √ T C so that T < C 2 |B|. Hence, we have: This bound is softer that the one in Eq. (29). However, the restriction on the number of iteration is more relaxed T < C 2 |B|. Note that to achieve this bound, we need high T . For higher T , we need to increase C meaning that M = √ T C goes down, hence more resetting is required.
Similar study is applied to Alg. 1 in Corollary 3 which shows that to achieve regret bound less than , Alg. 1 requires number of samples nb > H |B|C 2 3 while AES requires nb > H C 2 C 2/3 4/3 . As stated above, for higher T , we need to increase C meaning that m = T C 2 goes down faster for Alg. 1 compared to M of AES. Unlike AES, lower m for Alg. 1 means less RL update and lower RL convergence rate. Finally, we should point out that the regret bound of AES is, unlike Alg. 1, with respect to Dynamic competitor.
Based on the above studies, we propose sample efficient adaptive experience selection algorithm for off-policy policy gradient methods. The proposed algorithm is presented in Alg. 2. Line 5 calculates the sampling distribution. Line 6 samples from experience replay with the current sampling distribution and update policy parameters. Line 7 incrementally update w(i) for the sampling distribution estimation in the next iteration. Line 8-10 reset the sampling distribution every M iterations. Line 12-17 generate experiences with the current policy and add them into the experience replay. Note that line 15 use 1−p t to sample the experience to be written by the new one. This is because we consider the experience with smaller sampling probability less valuable.
Sample index set Ψ t from B using p t as sampling distribution; use the corresponding samples in B to update the policy parameters from θ to θ t using policy gradient algorithms like DDPG or SAC 7: Use the computed gradients in the step 6 to computẽ d t (i) and update w(i) ← w(i) +d t (i) for i ∈ Ψ t 8: if t%M == 0 then Perform a k according to π θt (.|s k ) 14: Get reward r k and next state s k+1

15:
Add experience (s k , a k , π θt (a k |s k ), r k , s k+1 ) into B; overwritten the experience sampled with distribution 1 − p t if B is full 16: k ← k + 1 17: end while 18: end for

IV. RELATED WORK
Variance reduction in policy gradient RL. Control variate [39] is typically used to reduce variance by subtracting a baseline from gradient estimate whilst adding no or little bias. Various forms of baselines has been exploited in RL, e.g. those based on exponential moving averages of rewards [13], [40], a closed-form formulation minimising the variance for each element in gradient [41], an approximation of value function [7], [10], [11], [42], a function based on past gradients [43], and a first order Taylor expansion of value function using off-policy data [44]. Other representative methods include trust region regularisation that limits the policy change in each policy update [7], [10], clipping or scaling the importance sampling ratio for importance sampling-based methods [7], [22], [23], formulating policy gradient using limiting state distribution [7], [16], and combining on-policy and off-policy methods [44], [44], [45]. All these methods focus on seeking a low-variance estimation of the gradient, using either uniform sampling or temporal difference error-based sampling for trajectories. None of these works has investigated the problem of learning an adaptive sampling distribution to reduce variance.
Experience selection in RL. A substantial body of work has also been devoted to design better sampling distributions for the ER buffer. [27] propose prioritised experience replay that uses a non-uniform sampling distribution prioritising the experiences with higher temporal-difference error. [29] propagate the priorities of samples through sequence of transitions. [28] propose a distribution version of prioritised experience replay using multiple workers to generate and select experiences. [30] propose a curiosity-based strategy that prioritises samples with rarely-seen states. [31] consider the "off-policyness" of trajectories and ignore the trajectories that deviate too much from the current policy. [32] learn a policy through RL to sample from experience replay. The influence of the size of experience replay [8], [46], [47] and overwritten strategy of existing experiences [8] have also been studied. All the above methods do not explicitly optimise the sampling distribution to reduce the gradient's variance.

A. Experiment setting
Environments. We perform experiments on 8 Mujoco [48] environments using the OpenAI Gym library [49]: InvertedPendulum, InvertedDoublePendulum, Reacher, Hopper, HalfCheeta, Walker2d, Ant, Humanoid. The environments are selected to include tasks with varying complexity. Examples for these environments are presented with some comparisons on our team YouTube channel 2 Parameter Tuning. All experiments are evaluated using 5 different seeds: {2, 20, 200, 2000, 20000}. For AES's hyperparameters tuning, we set the seed to 2, then use the hyperparameters with the best results on the remaining 4 seeds. Details about the hyper-parameters setting and implementations of AES and the policy gradient RL methods (i.e., SAC and DDPG) can be found in App. B.
Evaluation. We report plots (Fig. V-B and Fig. V-B) of the mean and standard deviation of the episodic return over all 5 different seeds. For each seed, the episodic return is computed on testing trials over the learning steps. This allows us to study the learning progress with respect to the number of samples acquired over time. AES' goal is to improve the sample efficiency by explicitly reducing the variance in gradient estimators. Lower variance should also entail improvement in the learning stability, robustness and final performance. We analyse these performance metrics from the reported plots. Performance measurements reflecting these four aspects are extracted from the plots and reported in App. D-B. A simple study of the variance over learning steps is reported in App. D-A.
Comparison methods. We have implemented the proposed AES methodology for two widely used off-policy RL algorithms: deep deterministic policy gradient (DDPG) [9] (see App. C-B) and soft actor-critic (SAC) [34] (See App. C-A), referred to as AES-DDPG and AES-SAC, respectively. We compare these algorithms with two competing methods: DDPG and SAC with uniform experience sampling as baseline and DDPG and SAC with prioritised experience replay [27] (here called pri-DDPG and pri-SAC, respectively) as representative methods for experience selection.  Fig. V-B report the mean episodic return. From Fig. V-B, we can see that pri-DDPG performs generally better than DDPG, and AES-DDPG achieves improved performance compared to pri-DDPG. Specifically, for relatively simpler environments (Inverted Pendulum, Inverted Double Pendulum, Reacher, Hopper), AES-DDPG performs slightly better than pri-DDPG. For HalfCheetah and Walker2d, which are more complex tasks, AES-DDPG achieves a larger improvement compared to pri-DDPG. For Ant and Humanoid, which are the most complex ones, DDPG is unable to learn a good policy. As a result, the performance of AES-DDPG is unstable. AES-2 https://www.youtube.com/channel/UCkDyucGZSYrSbBefntPZVHg DDPG performs similarly to pri-DDPG on Ant, and slightly better than pri-DDPG on Humanoid. The improvement achieved by AES is not limited to sample efficiency, but involves also learning stability, robustness and final performance. AES-DDPG achieves the highest final episodic return on all the environments with slight fluctuations across the learning steps and little variation over the different seeds.

Fig. V-B and
Similar trends can be observed with SAC as shown in Fig. V-B. It can be seen that SAC-AES performs clearly better than SAC and pri-SAC on more complex environments (Hopper, HalfCheetah, Walker2d, Ant), while SAC-AES performs comparablly to SAC on simpler environments (Inverted Pendulum, Inverted Double Pendulum, Reacher). A possible reason here is that SAC alone is sufficient to achieve near-optimal performance on these environments due to their simplicity, and there is litte room for improvement. On the other hand, we observe that pri-SAC based on temporal difference error does not perform better than SAC with general uniform sampling. A potential problem could be that Prio depends on the objective function being optimised as SAC, unlike DDPG, modifies the policy gradient objective function by adding an additional term of the policy entropy. On the contrary, AES considers the objective function as a whole regardless of its components. Note that, SAC-AES outperforms SAC on the complex environment Humanoid, but its performance is comparable to pri-SAC. An explanation for this result can be related to [8], who empirically demonstrated that the performance of heuristic experience selection method such as Prio depends on the characteristics of the control problem at hand. In addition to this assessment, we have also observed that the performance of heuristic experience selection methods also depends on the objective function defined by the underlhying RL algorithm. These results clearly demonstrate the ability of AES to adapt to different environments using different RL algorithms.

VI. CONCLUSION AND DISCUSSION
In this paper, we have proposed an adaptive variance reduction methodology for policy gradient learning through experience replay, which has been framed as an online optimisation problem. AES is generic and does not modify the gradient estimate making it possible to integrate different existing methods to reduce the variance further. We demonstrate this claim by employing AES in two existing RL algorithms i.e., SAC and DDPG, that can be considered as gradient based VR policy gradient methods. We have empirically shown that AES improves the learning performance of SAC and DDPG compared to standard and prioritised experience replay. We also also provided theoretical analysis and justification for guaranteeing variance reduction within our framework.
In future work, different approaches for handling the nonstationarity caused by RL experiences overwriting could be further explored. An alternative approach would use online unsupervised clustering algorithm to estimate the experience replay distribution directly in the experience space rather than imposing sampling distribution over their index. Overwriting would then update the density estimation (clustering) model of the experiences. This will prevents abrupt change in the sampling distribution and standard online learning can then be applied to find the best sampling distribution reducing the variance the most. On the application aspect, AES could be explored with multi-agent RL where the variance is known to be high and alleviating it is essential.

APPENDIX A PROOFS
A. Proof of Lemma 1 For simplicity, we write θ t as θ. Note that the output of ω θ i and R are scalars. Therefore, we have the following equation: According to Eq. 2 and Assumption 1, we have Eq. 2 and Assumption 2 lead to Using Assumption 3 we can obtain By substituting Inequalities (31), (32) and (33) to Eq. 30, we obtain Thus, the proof of Lemma 1.

B. Proof of Corollary 3
Using Corollary 2, we have It follows that Setting m = E/C 2 leads to sub-linear regret bound with respect to E: Under assumption 4 and with m = E/C 2 , we have T < C 2 |B| |Ψ| . The regret bound can be written as follows: Thus, Corollary 3 is proven.

C. Proof of Theorem 1
Recall that for AES we reset p every M policy update steps. Thus, we divide the policy update steps into sequential sets each with M steps, and use T m to denote the m th set where m ∈ [1, 2, ..., T /M + 1]. It follows up that: Using Lemma 2, we can bound the second term of Eq. (39): Following Theorem 7 in [36], we can bound first part of Eq. (39) as follows: where |T m | = M ∀m. Using the same steps used in lemma 2 to move from Eq. (55) to Eq. (57), we can bound Eq. (41) as follows: Using the steps used in lemma 2 to move from Eq. (57) to Eq. (63), we can bound Eq. (41) as follows: For these steps, Assumption 3 and 5 need to hold. Using Jensen's inequality and with a bit of algebra, we can obtain the following: Under assumption 6 and given that the number of overwritten samples before resetting is less than the buffer size M 2 < |B| (this condition is already needed for lemma 2), we use the steps of lemma 2 used to move from Eq. (63) to Eq. (64): Thus, 1 Using Eq. (46) with Eq. (40), we have: Thus, we prove theorem 2.

D. Proof of Lemma 2:
Under assumption 1, 2, 3, 5 and 6, lemma 2 bounds regret between static and dynamic optimum within epoch: Taking p * = arg min p∈∆ t∈Tm , Eq. (48) can be expressed as: To find p * , we solve the following optimisation problems: By formulating the Lagrangian, setting its derivative to zero and using complementary slackness, we can show that: Similarly, to find p * t , we solve the optimisation problem: where α t = α ≤ ξ/K 2 . Assume 0 ≤ (1 − ξα) < 1, hence α < 1/ξ which implies a condition on the learning rate according to the smoothness degree of the objective function α < 1/K. Given that number of overwritten samples before resetting is much less than the buffer size M 2 < |B|: Thus, lemm 2 is proven APPENDIX B IMPLEMENTATIONS All implementations are in python 3.6.8 using pytorch 0.4.0.

A. DDPG
DDPG's agent uses actor-critic architecture. For the actor, we use three layers neural network with fully connected input layer mapping the states to a fully connected 400 hidden layer followed by a fully connected 300 output layer where its output size is equal to the action dimension. All input and hidden layers were followed by a rectifier nonlinearity while the output layer is a tanh layer to bound the actions. For the critic, we use neural network with three fully connected layers. All layers excluding the last one are followed by a rectifier nonlinearity. The first layer maps states to 400 hidden layer. Actions are concatenated with the output of the first layer and fed to the second layer with 300 output size. The third layer maps the 300 ouput of the second layer to output of size 1. Adam optimiser is used with its learning rates set to 10 −4 and 10 −3 for the actor and critic respectively. Mini-batch size is set to 64. The rest hyper-parameter of DDPG are set the same as its original paper [9].

B. SAC
SAC adopts the soft Q-learning (SQL) implementation of [51] with two Q-functions. Both, the Q-value functions and policy / sampling network are neural networks comprised of 256 hidden layer and ReLU nonlinearity. Adam optimiser is used with its learning rates set to 10 −4 , batch size is set to 256. The rest hyper-parameter of SAC are set the same as in the orginal code 3 .

C. AES
AES implementations resemble the steps presented in Alg. 2 with few practical variations. The AES hard resetting presented in Alg. 2 (line 9) is replaced with soft resetting version where forgetting factor is used. For some experiments, we anneal this forgetting factor from initial to final values. For parameters tuning of AES, samples of different hyper-parameter settings are tested and the best ones are used. Table I

APPENDIX C ALGORITHMS A. SAC application
We apply AES presented in Alg. 2 to SAC algorithm for continuous action proposed by [34]. We call the resulting algorithm AES-SAC presented in Alg. 3.

B. DDPG application
We apply AES presented in Alg. 2 to DDPG algorithm for continuous action proposed by [9]. We call the resulting algorithm AES-DDPG presented in Alg. 4.

16:
end for 17: until Max iteration T reached

B. Numerical measurements
When applying AES, we are interested in the improvement in sample efficiency, that is, can we achieve higher score using same amount of samples. We are also interested in the learning stability and final performance because reducing variance should affect these measurements. To report the effect of AES on this three aspect, we define Learning speed as the average speed with respect to steps within the steps needed to reach the maximum score during the last 60% of total learning steps; Learning speed= (max score)/(number of steps). Since our method reduce the updating variance by selecting samples with less noisy gradient, faster improvement can be achieved. That is because local optimum can be reached without much of distraction, allowing better optimum using less samples. That reflect higher score with less steps. Thus, we also report the (max score) Algorithm 4 Adaptive Experience selection for DDPG: AES-DDPG 1: input: number of iteration T , sampling batch |Ψ|, restarting period M , experience size |B|, exploration meta-learning parameter κ, maximum trajectory length H 2: initialise: initialise policy parameters θ, critic parameters θ v , target policy parameters θ , target critic parameters θ v , probability of sampling weights w(i) = 0 E i=1 and gradient accumulators dθ ← 0, dθ v ← 0. Update sampling distribution p(j) = (1 − κ) Select action a i = µ θ (s i ) + N according to the current policy and exploration noise 9: Execute action a i and receive reward r i and the next state s i+1 10: Store transition (s i , a i , r i , s i+1 ) in the experience buffer by overwriting experience indexed by j ∼ 1−p |B|−1

16:
end for 17: until Max iteration T reached during the last 60% of total learning episodes. Note that the score denotes the per-episode total testing return and is computed using moving average windows.
A common drawback of DRL algorithms is that even when a good performance has been achieved, it can drop significantly as the distribution of acquired data changes. That happens when a reached local optimum is lost to a worse one. Hence, the algorithm de-learns and could diverge. By using our variance reduction methods, distracting samples are avoided. Thus, the algorithm is expected to leave a optimum only to reach a better one. To measure this Learning stability, we compute the proportion of the mean scores achieved at the end of learning to the max score achieved. This expresses how much of the max score has been carried till the end of the learning. We also report the final performance which is the testing score after learning is over. The average and standard deviation score is computed over 5 different seeds {2, 20, 200, 2000, 20000}. We report the results robustness which is expressed by the mean of the standard deviation over the last 20% steps. Table II shows the numerical figures of the measurements discussed above: learning speed, learning stability, Max score, Robustness and Final performance. These results summarise the learning performance reported in Fig. V-B and Fig. V-B.