Off-Policy Actor-Critic with Shared Experience Replay
Authors: Simon Schmitt
Matteo Hessel
Karen Simonyan
Venue:  (2020)
Keywords: Reinforcement Learning
Off-Policy Learning
Experience Replay

Abstract: We investigate the combination of actor-critic reinforcement learning algorithms with uniform large-scale experience replay and propose solutions for two challenges: (a) efficient actor-critic learning with experience replay (b) stability of very off-policy learning. We employ those insights to accelerate hyper-parameter sweeps in which all participating agents run concurrently and share their experience via a common replay module.

To this end we analyze the bias-variance tradeoffs in V-trace, a form of importance sampling for actor-critic methods. Based on our analysis, we then argue for mixing experience sampled from replay with on-policy experience, and propose a new trust region scheme that scales effectively to data distributions where V-trace becomes unstable.

We provide extensive empirical validation of the proposed solution. We further show the benefits of this setup by demonstrating state-of-the-art data efficiency on Atari among agents trained up until 200M environment frames.

Under review as a conference paper at ICLR 2020
OFF-POLICY ACTOR-CRITIC WITH SHARED EXPERIENCE REPLAY
Anonymous authors Paper under double-blind review
ABSTRACT
We investigate the combination of actor-critic reinforcement learning algorithms with uniform large-scale experience replay and propose solutions for two chal- lenges: (a) efficient actor-critic learning with experience replay (b) stability of off off-policy learning where agents learn from other agents behaviour. We employ those insights to accelerate hyper-paramene parameter sweeps in which all participating agents concurrently and share their experience via common replay module. To this end we analyze the bias-variance tradeoff's in V-rrace, form of importance sampling for actor-critic methods. Based on our analysis, we then argue for mixing experience sampled from replay with on- on-policy experience, and propose a new trust region scheme that scales effectively to data distributions where V-trace becomes unstable.
We provide extensive empirical validation of the proposed solution. We further show the benefits of this setup by demonstrating ofate-of-the--e oortth--rttteeee data efficiency Atari among agents trained up until 200M environment frames.
INTRODUCTION
Value-based and actor-critic policy gradient methods are the two leading techniques of constructing general and scalable reinforcement learning agents (Sutton al., 2018). Both have been combined with non-linear function approximation (Tesauro, 1995; Williams, 1992), and have achieved remark- able successes on multiple challenging domains; yet, these algorithms still require large amounts of data to determine good policies for any new environment. To improve data efficiency, experience replay agents store experience in memory buffer (replay) (Lin, 1992), and reuse it multiple times to perform reinforcement learning updates (Riedmiller, 2005). Experience replay allows to generalize prioritized sweeping (Moore & Atkeson, 1993) to the non-tabular setting (Schaul et al., 2015), and can also be used to simplify exploration by including expert (e.g., human) trajectories (Hester et al., 2017). Overall, experience replay can be very effective at reducing the number of interactions with the environment otherwise required by deep reinforcement learning algorithms (Schaul et al., 2015). Replay is often combined with the value-based Q-learning (Mnih et al., 2015), as it is an off-policy algorithm by construction, and perform well even if the sampling distribution from replay is not aligned with the latest agent's 's policy. Combining experience replay with actor-critic algorithms can be harder due to their on-policy nature. Hence, most established actor-critic algorithms with replay such as (Wang et al., 2017; Gruslys et al., 2018; Haarnoja et al., 2018) employ and maintain Q-functions to learn from the replayed off off-po experience.
In this paper, we demonstrate that off off-policy actor-critic learning with experience replay can be achieved without surrogate Q-function approximators using V-trace by employing the following approaches: a) off-policy replay experience needs to be mixed with a proportion of on-policy experience. We show experimentally (Figure 2) and theoretically that the V-trace policy gradient otherwise not guaranteed to converge to a locally optimal solution. b) trust region scheme (Conn et al., 2000; Schulman et al., 2015; 2017) can mitigate bias and enable efficient learning in a strongly off-policy regime, where distinct agents share experience through commonly shared replay module. Sharing experience permits the agents to benefit from parallel exploration (Kretchmar, 2002) (Figures and 3).
Our paper is structured as follows: In Section we revisit pure importance sampling for actor-critic agents (Degris et al., 2012) and V-trace, which is notable for allowing trade off bias and variance

---

Under review as a conference paper at ICLR 2020
in its estimates. We recall that variance reduction is necessary (Figure 4 left) but is biased in V-trace. We derive proposition stating that pfolcy V-trace not guaranteed to converge to a locally optimal solution not even in idcalized scenario when provided with the optimal value function. Through theoretical analysis (Section 3) and experimental validation (Figure 2) we determine that mixing on-policy experience into experience replay alleviates the problem. Furthermore a trust region scheme (Conn et al., 2000; Schulman et al., 2015; 2017) in Section 4 that enables efficient learning even in a strongly off-policy regime, where distinct agents share the experience replay module and learn from each others experience. We define the trust region in policy space and prove that the resulting estimator is correct (i.e. estimates an improved return).
propose
As a result, we present otate-of-the-art data efficiency in Section 5 in terms of median human normalized performance across 57 Atari games (Bellemare et al., 2013), as well as improved learning efficiency on DMLab33 (Beattie et al., 2016) (Table 1).
Sample Efficiency on Atari
500
400
Human Median %
300
IMPALA Meta-Gradient
RAINBOW REACTOR
200
100
DON
10 M
50
100 M
150 M
200
Envirenment Steps per Agent and Level
Other Agents
IMPALA: No Replay (sweep)
LASER: 1m Replay (sweep)
(at 200m Env. Steps)
LASER (no sweeo)
LASER: 9m Shared Replay (sweep)
Figure 1: Sharing experience between agents leads to more efficient syper-parameter sweeps on 57 Atari games. Prior art results are presented as horizontal lines (with scores cited from Gruslys et al. (2018), Hessel et al. (2017) and Mnih et al. (2013)). Note that the only previous agent "R2D2" that achieved a score beyond 400% required more than 3,000 million environment steps (see Kapturowski al. (2019), page 14, Figure 9). We present the pointwise best agent from hyper-parameter sweeps with and without experience replay (shared and not shared). Each sweep contains 9 agents with different learning rate and entropy cost combinations. Replay experiment were repeated twice and ran for 50M steps. To report scores 200M we ran the baseline and one shared experience replay agent for 200M steps.
Comparison of state-of-the-art agents on 57 Atari games trained up until 200M environment steps (per game) and DMLab-30 trained until 10B steps (multi-task; all games combined). The first two rows are quoted from Xu et al. (2018) and Hessel et al. (2019), the third is our implementation of a pixel control agent from Hessel et (2019) and the last two rows are our proposed LASER (L.Arge Scale Experience Replay) agent. All agents use hyper-parameter sweeps expect for the marked.
Table 1:
Atari Median
DMLab-30 Median
DMLab-30 Mean- Caan-Cdpped
IMPALA Meta-Gradient (no sweep)
287.6% 200M
PoPAIt-IMPALA
73.5%
AoAAt-LMPALA+PPicCCCooot
85.5%
77.6%
LASER: Experience Replay (no sweep)
431% at 200M
LASER: Experience Replay
(233% at 50M)
95.1%
79.6%
(370% at 50M),
LASER: Shared Experience Replay
97.2%
81.7%
448% at 200M
2

---

Under review as a conference paper at ICLR 2020
2 THE ISSUE WITH IMPORTANCE SAMPLING: BIAS AND VARIANCE IN V-TRACE
V-trace importance sampling is popular off-policy correction for actor-critic agents (Espeholt et al., 2018). In this section we revisit how V-trace controls the (potentially infinite) variance that arises from naive importance sampling. We note that this comes the cost of biased estimate (see Proposition I) and creates a failure mode (see Proposition 2) which makes the policy gradient biased. discuss our solutions for said issues in Section 4.
llyperparameter sweeps:
Hype par armeler sweeps: amounts replay
experience replay capacity
100
90
90
80
Median
70
50
40
2
4
6 B
10
Environment Steps
Environment Steps
Baseline: replay
LASER: 50% replay
Baseline: no replay
LASER: 3M replay
LASER: 37.5% replay
Ablation: all replay
LASER: 10M replay
Figure 2: Left: Learning entirely off off-pc from experience replay fails, while combining on on-policy data with experience replay leads to improved data efficiency: We present sweeps DMLab- 30 with experience replays of 10M capacity. ratio of 87.5% implics that there are replayed transitions in the batch for each online transition. Furthermore replay" which however draws all samples from replay. Its batch thus does not contain any online data and we observe significant performance decrease (see Proposition 2 and The shading represents the point-wise best and worst replica among 3 repetitions. The solid line is the mean. Right: The effect of capacity in experience replay with 87.5% replay data per batch on sweeps on DMLab-30. Data-effe Data-efficiency improves with larger capacity.
consider an agent identical "LASER 87 87.5%
Hyperparameter sweeps: shared expertence replay
PBT sweeps:
shared experience replay
100
100
90
80
80
Median
Median
70
60
50
50-
40
2.8
4.8
6.8
8
10
B
2.8
4.8
6
8
10
B
Baseline: no replay
Naively shared
Baseline: no replay
Naively shared
LASER: not shared
LASER: shared trust region
LASER; not shared
LASER: shared + trust region
Figure 3: Left: Naively sharing experience between distinct agents in a hyper-paramess sweep fails (green) and is worse than the no-replay baseline (blue). The proposed trust region estimator mitigates the issue (red). Right: Combining population based training with trust region estimation improves performance further. All replay experiments use capacity of 10 million observations and 87.5% replay data batch.
2.1 REINFORCEMENT LEARNING
We follow the notation of Sutton al. (2018) where agent interacts with its environment, to collect rewards. On each discrete time-step t, the agent selects an action a,; it receives in return a reward r, and observation oc+1, encoding partial view of the environment's state 8141- In the fully
3

---

Under review as a conference paper at ICLR 2020
observable case, the RL problem is formalized as a Markov Decision Process (Bellman, 1957): tuple (S,A, p. 7), where S,A denotes finite sets of states and actions, p models rewards and state transitions (so that re: $t+1 p(s,, at)), and y is fixed discount factor. A policy is mapping T (a]s) from states to action probabilities. The agent seeks an optimal policy π." that maximizes the value, defined the expectation of the cumulative discounted returns G2 = >k= Trtk.-
Off-policy learning is the problem of finding, or evaluating, a policy π from data generated by a different policy μ.. This arises in several settings. Experience replay (Lin, 1992) mixes data from multiple iterations of policy improvement. In large-scale RL, decoupling acting from learning (Nair al., 2015; Horgan et al., 2018; Espeholt et al., 2018) causes the experience lag behind the latest agent policy. Finally, it is often useful to learn multiple general value functions (Sutton et al., 2011; Mankowitz. et al., 2018; Lample& Chaplot, 2016; Mirowski et al., 2017; Jaderberg et al., 2017b) or options (Sutton et al., 1999; Bacon et al., 2017) from a single stream of experience.
2.2 NAIVE IMPORTANCE SAMPLING
On-policy n-step bootstraps give more accurate value estimates in expectation with larger n (Sutton et al., 2018). They are used in many reinforcement learning agents (Mnih et al., 2016; Schulman et al., 2017; Hessel et al., 2017). Unfortunately n must be chosen suitably as the estimates variance increases with too.
is desirable to obtain benefits akin to n-step returns in the off- off-policy case. To this end multi-step importance sampling (Kahn, 1955) can be used. This however adds another source of (potentially infinite (Sutton et al., 2018)) variance to the estimate.
Importance sampling can estimate the expected return V from trajectories sampled from 14 * n, as long as j is non-zero whereever æ is. We employ a previously estimated value function V as a bootstrap to estimate expected returns. Following Degris et al. (2012), multi-step formulation of the expected return is
(T(()) = E,. V(si) Σ k=U
Te+i
80+R
(I)
where E,, denotes the expectation under policy μl up to episode termination, 8.V = Pt-
(V(++)) - Vss)) ) is the temporal difference error in consecutive states 81+1, 8t, and n. = n. (t). Importance sampling estimates can have high variance. Tree Backup (Precup et al., 2000), and Q(A) (Sutton et al., 2014) address this, but reduce the number of steps before bootstrapping even when this undesirable (as in the on-policy case). RETRACE (Munos et al., 2016) makes use of full returns in the on- on-policy case, but it introduces a zero-mean random variable at each step, adding variance to empirical estimates in both on- and off-policy cases.
2.3 BIAS- VARIANCE ANALYSIS & FAILURE MODE OF V-TRACE IMPORTANCE SAMPLING
V-trace (Espeholt et al., 2018) reduces the variance of importance sampling by trading off variance for a biased estimate of the return - resulting in failure mode (see Proposition 2). uses clipped impor- tance sampling ratios to approximate V by V*(ss) V(s)) ({s)>EK=)) K-1 7
[ k-1 a P: where V is learned state value estimate used to bootstrap, and pt = min / TTe/Me, p). = min [ e] are the clipped importance ratios. Note that, differently from RETRACE, V-trace fully recovers the Monte Carlo return when policy. It similarly reweights the policy gradient as:
Ek=o
VV*
(s+) def E,, [p. V(lg (1: + 7V" (8(+1))
Note that VV*(5), (st) recovers the naively importance sampled policy gradient for e - 0o. In the literature, it is common to subtract baseline from the action-valus estimate + ($(41) to reduce variance (Williams, 1992). omitted here for simplicity. The constants p 2 à 2 (typically chosen p = ē 1) define the level of clipping, and improve stability by ensuring bounded variance. For any given p. the bias introduced by V-trace in the value and policy gradient estimates increases with the difference between π and p. We analyze this in the following propositions.
Proposition 1. The V-trace value estimate V is biased: It does not match the expected return of but the return of a related implied policy ât defined by equation 3 that depends on the behaviour
4

---

Under review as a conference paper at ICLR 2020
policy p.:
min [p)((a()), x(a2=)) Enen min pou (b))) o ((b(r))
Proof. See Espeholt al. (2018).
Note that the biased policy n. can be very different from Hence the V-trace value estimate V may be very different from V as well. As an illustrative example, consider two policies over set of two actions, c.g. "left" and "right" represented as tuple of probabilities. Let us investigate ( 3) and π = (1 Φ x)) defined for any suitably small I 1. Observe that и and lr share no trajectories (state-action sequences) in the limit as á and they get more focused on one action. A practical example of this could be two policies, one almost always taking a left turn and one always taking the right. Given sufficient data either policy is possible to estimate the value of the other e.g. with naive importance sampling. However observe that V-trace with p 1 will always estimate biased value even given infinite data. Observe that min [u(a|z), π [aa[x]] ] = min [ø, 1 ø] for both actions. Thus म. is uniform rather than resembling the policy. The V-trace estimate V would thus compute the average value of "left" and "right" poorly representing the true V
Proposition 2. The V-trace policy gradient is biased: given the the optimal value function V the V-trace policy gradient does not converge to a locally optimal x² for all off-policy behaviour distributions μ.
Proof. See Appendix C.
MIXING ON- AND OFF-POLICY EXPERIENCE
In Proposition 2 we presented a failure mode in V-trace where the variance reduction biases the value estimate and policy gradient. V-trace computes biased Q-estimates Q" # Q resulting in wrong local policy gradient: V (Q a)l + VEs(els) [Q(s, In equation 10 we show that (s, = Q(s, ()s,,)((sss a) where w(s, a) = min 1, ((a 1
The question of how biased the resulting policy will depends on whether the distortion changes the argmax of the Q-function. Little distortions that do not change the argmax will result in the same local fixpoint of the policy improvement. The policy will continue to select the optimal action and will not be biased at this state. The policy will however be biased if the Q- Q-function is distorted too much. For example consider a w(s, a) that swaps the argmax for the 2nd largest value, the regret will then be the difference between the maximum and the 2nd largest value. Intuitively speaking the more distorted the Q", the larger will be the regret compared to the optimal policy.
More precisely, the regret of learning policy that maximizes the distorted Q" at state is:
R(s) Q(8, a*) Q(, Quctual) max ((s, b) Q(s, Ouctual)
where a" argmax, (Q, is the optimal action according to the real Q and Oactual mrgmax[Q"(ss a)] argmax[((ss, a)w(s, a)], is the optimal action according the distorted Q For generality, we denote A as the set of best actions covering the case with multiple with identical optimal Q-values.
Proposition 3 provides mitigation: Clearly the V-trace policy gradient will converge to the same solution as the true on-policy gradient the argmax of the Q-function is preserved all states in tabular setting. We show that this can be achieved by mixing a sufficient proportion a of on on-policy experience into the computation.
We show in equation 13 in the Appendix that choosing such that
(x, (s, d' d' for Q" Q(s, a)s,a) Q(s,a*) Q(s
max -
d=(s)
will result in policy that correctly chooses the best action at state Note that I-a
5

---

Under review as a conference paper at ICLR 2020
Intuitively: the larger the action value gap of the real Q-function Q(s.a') Q(s.)) the lower the right hand side and the less on- on-policy data required. If maxx](Q(s b) b) Q(s, aa(ss"" )w[[[, a a")] is negative, then may be as small zero and enabling even pure off- off- policy learning. Finally note that the right hand side decreases due to dH (s)/d" (s) if æ visits the state more often than μ.
All of those conditions is accessible. How to use imperfect Q-function estimates to adaptively choose such an a remain a question for future research.
be computed and checked if accurate Q-function and state distribution
We provide experimental evidence for these results with function approximators in the 3-dimensional simulated environment DMLabb30 with various a 2 1/8 in Section 5.3 and Figure 2. We observe that a 1/8 is sufficient to facilitate stable learning. Furthermore it results in better data-efficiency than pure on-policy learning as it utilizes off off-policy replay experience.
Proposition 3. Mixing on-policy data into the V-trace policy gradient with the ratio reduces the bias by providing a regularization to the implied state-action values. In the general function approximation case it changes the off-policy V-trace policy gradient from E d' (s) [[Q(s, a) log म (a]s)] to E. Ex [Q (s, a) V log πI [als]] where Q = Qd (s)a + Q dz))
a) is a regularized state- action estimate and d", dl' are the state distributions for and μs. Note that there exists S 1 such
that Q" has the same argmax (i.e. best action) as Q.
Proof. See Appendix C.
Mixing online data with replay data has also been argued for by Zhang & Sutton (2017), a heuristic way of reducing the sensitivity of reinforcement learning algorithms to the size of the replay memory. Proposition 3 grounds this in the theoretical properties of V-trace.
4 TRUST REGION SCHEME FOR OFF-POLICY V-TRACE
To mitigate the bias and variance problem of V-trace and importance sampling we propose a trust region scheme that adaptively selects only suitable behaviour distributions when estimating the state-value of π. To this end we introduce a behaviour relevance function that classifies hehaviour as relevant. We then define a trust-region estimator that computes expectations (such expected returns, or the policy gradient) only on relevant transitions. In proposition 4 and 5 we show that this trust region estimator indeed computes new state-value estimates that improve over the current value function. While our analysis and proof is general we propose suitable behaviour relevance function in section 4.3 that employs the Kullback Leibler divergence between target policy æ and implied policy म, KL (-Is)) We provide experimental validation in Figure 3.
4.1 BEHAVIOUR RELEVANCE FUNCTIONS
In off-policy learning often consider family of behaviour policies either indexed by training iteration t: My = {prlt < T for experience replay, or by a different agent k: Mx = [/ug/ E K) when training multiple agents. In the classic experience replay case we then sample a time and locate the transition that was generated earlier via This extends naturally to the multiple agent case where we sample an agent index It and then obtain transition for such agent or tuples of (ke t). Without loss of generality we simplify this notation and index sampled behaviour policies by random variable algorithms process transitions т notation, given equation (1) and a bootstrap V, the expectation of importance sampled off-policy returns at state st is described by:
Z that represents the selection process. While online reinforcement learning
off-policy algorithms process μl for Z. In this
V (s:) Eg Eps1z
( (s:)]
where (s.) V(s.) + D * III
mett
desh V is a single importance sampled return.
nets
Note that the on-pol return GT (s:) (ss)) + E 7* rr4k-
Above E,, represents the expectation of sampling from a given A4z The conditioning on 2 is a notational reminder that this expectation does not sample or μl, but experience from μz. For any

---

Under review as a conference paper at ICLR 2020
sampled we obtain Na and observe that the inner expectation wrt. experience of μt in equation (4) recovers the expected on-policy return in expectation:
Epals ( (st)) = Epal=
V(s))
+
Teti
1ethV
k=0
(=0
20
k
E
((s))
Maitti
(5)
M2,tti
k=0
00
Ei
V(s)) +
Σ
7
Te+k
Ex [
Thus V
(st)). This holds provided that μlg is non-zero wherever и is. This fairly standard assumption leads us straight to the core of the problem: may be that some behaviours μe are ill-suited for estimating the inner expectation. However, standard importance sampling applied to very off-policy experience divides by small resulting in high or even infinite variance. Similarly, V-trace attempts to compute estimate of the return following resulting in limited variance at the cost of biased estimate in turn.
"ixx (s,) = Eg E, (Gt = Ex (G*.
The key idea of our proposed solution is compute the return estimate for each state only from a subset of suitable behaviours jáz:
Mp,x($) (uul= = E and B(T, 8) < b}
as determined by a behaviour relevance function ((T, s) (Mz, M) + R and a threshold b. The behaviour relevance function decides if experience from behaviour is suitable compute an expected return for л. It can be chosen to control properties of Vmix by restricting the expectation on subsets of Z. In particular can be used to control the variance of an importance sampled estimator: Observe that the inner expectation E,,, [GT,P(s)) =] in equation (4) already matches the expected return VA, Thus we can condition the expectation on arbitrary subsets of without changing the expected value of V* This allows us to reject high variance G without introducing a bias in V The same technique can be applied to V-trace where we can reject return estimates with high bias.
4.2 DERIVATION OF TRUST REGION ESTIMATORS
Using a behaviour relevance funetion B(s) we can define a trust region estimator for regular impor- tance sampling (IS) and V-trace and show their correctness.
We define the trust region estimator as the conditional expectation
V Virusted (8t) E,
[ Me. (st) Me E Ms,
[GT.
(6)
with X-returns G, chosen Gis for importance sampling and Gverace for V-trace:
k Anya, (0144)
Gis (8+) = V(+)
Tets Se+&V
M2
A=
1=0
Virrae Vittace (8t) = V(+)) +
Am,a (se4s) da (8e+k)
(8)
k=0
1=0
where (5)) is designed constraint Monte-Carlo bootstraps to relevant behaviour: > (vt) =
and C2,t+4 are behaviour dependent clipped importance Virace are multi-step return estimators with adaptive length. Note that only estimators with length 2 1 are used in Vilustd Due to Minkowski's 's inequality the trust region estimator thus shows at least the same contraction as 1-step bootstrap, but can faster due to its adaptive nature:
(() and Pa.t+ = min Tete
rations. Thus both G and G.
Proposition 4. Let Ht be set of importance sampling estimators defined in equation 7. Note that they all have the same fix point v and contract with at least 7/. Then the contraction properties carry over to a wusttdd In particular Virusted
V S VV V*
7

---

Under review as a conference paper at ICLR 2020
Proof. See Appendix C.
Proposition 5. Lel G be set of V-trace estimators (see equation 8) with corresponding fixed points V (see equation 3) to which they contract at a speed of an algorithm and behaviour specific Te- Then V trusted moves towards V Ezlu,eMs,ni [V*] shrinking the distance follows m== - V=) (V>) I Tmax max,, (V -V*) with
V trusted V 0o
< &maxp,,
7max = , (s.) 1z2
Proof. See Appendix C.
Virace from the esti- mation of V trusted- Recall that V-trace fixed points V2 are biased. Thus allows to selec- tively create the V-trace target 8 E.. (+:) [V*] and control its bias and the shrinkage , Ma. (ax) (V(s) V (s)) (see Proposition 5). Similarly can control cases where can not use the exact importance sampled estimator. The same approach based on nested expectations can be applied the expectation of the policy gradient estimate and allows control the bias and
Note how the choice of 3 and thus M3.- enables us to discard ill-suited GT
greediness (see Proposition 2) there as well.
4.3 IMPLEMENTATION DETAILS
In Proposition 5 we have seen that the quality of the trust region V-trace return estimator depends on 3. A suitable choice of /3 can move the return estimate V closer to V and improve the shrinkage by reducing max,,, M.. (*+) [7 (V(s)
(*(s)) Hence, employ a behaviour relevance function SKI. that rejects high bias transitions by estimating the Kulback- divergence between the target policy ı and the implied policy 7y. for sampled behaviour uzz- Recall from Proposition that Ty. determines the fixed point of the V-trace estimator for behaviour μlz and thus determines the bias in V=
BKI (T,, s) KL (+ss)
Note that the behaviour probabilities H4 can be evaluated and saved to the replay when the agent executes the behaviour, similarly the target policy represented by the agents neural network. Using both and equation 3, ft can be computed. For large or infinite action spaces a Monte Carlo estimate of the KL divergence can be computed.
is possible to define separate behaviour relevance functions for the policy and value estimate. For simplicity we reject transitions entirely for all estimates and do not consider rejected transitions for the policy gradient and value gradient updates or auxiliary tasks. As described above we stop the Monte- Carlo bootstraps once they reach undesirable state-behaviour pairs. Note that this censoring procedure is computed from state dependent ल(T, (4 and ensures that the choice of bootstrapping does not depend on the sampled actions. Note that rejection by an action- based criteria such as small x (a) (((s))(())))))))))))))({)) would introduce an additional bias which we avoid by choosing 9KL.
EXPERIMENTS
We present experiments to support the following claims:
Section 5.2: Uniform experience replay obtains comparable results as prioritized experience replay, while being simpler to implement and tune.
Using fresh experience before inserting in experience replay better than learning purely off-policy from experience replay in line with Proposition 3.
Section 5.3:
Section 5.4: Sharing experience without trust region performs poorly as suggested by Proposition 2. Off-Policy Trust-Region V-trace solves this issue.
Section 5.5: Sharing experience take advantage of parallel exploration and obtains state-of-the-art performance on Atari games, while also saving memory through sharing a single experience replay.
8

---

Under review as a conference paper at ICLR 2020
5.1 EXPERIMENTAL SETUP & METHODOLOGY
We use the V-trace distributed reinforcement learning agent (Espeholt et al., 2018) as our baseline. In our experiments we consider two experimental platforms: Atari and DeepMind Lab. On Atari we consider the common single task training regime, where different agent is trained, from scratch, on each of the tasks. Following Xu ct al. (2018) we use a discount of 0.995. Motivated by recent work by Kaiser et al. (2019), we use the IMPALA deep network and increased the number of channels 4x. We use 96% replay data per batch. Differently from Espeholt et al. (2018), we do not use gradient clipping by norm (Pascanu et al., 2012). Updates are computed on mini-batches of 32 (regular) and 128 (replay) trajectories, each corresponding to 19 steps in the environment. In the context of DeepMind Lab, we consider the multi-task suite DMLab-30 (Espeholt al., 2018), as the visuals and the dynamics are more consistent across tasks. Furthermore the multi-task regime is particularly suitable for the investigation of strongly off off-policy data distributions arising from sharing the replay across agents, as concurrently learning agents can easily be stuck in different policy plateaus, generating substantially different data (Schaul et al., 2019). As in Espeholt et al. (2018), in the multi-task setting each agent trains simultaneously on uniform mixture of all tasks rather than individually on each game. The score of an agent is thus the median across all 30 tasks. Following Hessel et al. (2019), we augment our agent with multi-task Pop-Art normalization and PixelControl. We use a PreCo LSTM (Amos et al., 2018) instead of the vanilla one (Hochreiter & Schmidhuber, 1997). Updates are computed mini-batches of multiple trajectories chosen above, each corresponding to 79 steps in the environment. In early experiments we found that computing the entropy cost only on the online data provided slightly better results, hence we have done so throughout our experiments.
In all our experiments, experience sampled from memory is mixed with online data within each mini- batch - following Proposition 3. Episodes are removed in a first in first out order, so that replay always holds the most recent experience. Unless explicitly stated otherwise we consider hyper-pane syper-parameter sweeps, some of which share experience via replay. In this setting multiple agents start from-scrated run concurrently at identical speed, and add their new experience into a common replay buffer. All agents will then draw uniform samples from the replay buffer. On DMI Lal-303 we consider both regular hyper-parameter sweeps and sweeps with population based training (PBT) (Jaderberg et al., 2017a). On DMLab-30 sweeps contain 10 agents with parammerrretters sampled similar as Espeholt et al. (2018) but fixed RMSProp E = 0.1. On Atari sweeps contain agents with different constant learning rate and entropy cost combinations {3 10-1,01-0000 6- 10-4, 1.2 10 10-3) {5- 10-3, 1 10-2,2 2. 10-2) (distributed by factors {1/2, 1,2] around the initial parameters reported in Espeholt et al. (2018)). Although our focus is efficient hyper-paramette sweeps given crude initial parameters,
also
present a single-agent LASER experiment using the same tuned schedule as Espeholt et al. (2018), 8), a 87.5% replay ratio and a 15M replay. We store the entire episodes in the replay buffer and replay each episode from the beginning. using the most recent network parameters to recompute the LSTM states along the way: this is particularly critical when sharing experience between different agents, which may have arbitrarily different state representations.
5.2 UNIFORM AND PRIORITIZED EXPERIENCE REPLAY
Prioritized experience replay has the potential to provide more efficient learning compared to uniform experience replay (Schaul et al., 2015; Horgan et al., 2018). However, it also introduces a number of new tyyer--arameete and design choices: the most critical are the priority metric, how strongly to bias the sampling distribution, and how to correct for the resulting bias. Uniform replay is instead almost parameter-free, requires little tuning and can be easily shared between multiple agents. Experiments provided in Figure 4 in the appendix showed little benefit of actor critic prioritized replay on DMLab-30. Furthermore priorities are typically computed from the agent specific metrics such the TD-error, which are ill-defined when replay is shared among multiple agents. Hence used uniform replay for our further investigations.
5.3 MIXING ON- AND OFF-POLICY EXPERIENCE AND REPLAY CAPACITY
Figure 2 (left) shows that performance degrades significantly when online data is not present in the batch. This experimentally validates Propositions and 3 that highlight difficulties of learning purely off-policy. Furthermore Figure 2 (right) shows that best results obtained with experience replay
9

---

Under review as a conference paper at ICLR 2020
of 10M capacity and 87.5% ratio. A ratio of 87.5% 7/8 corresponds to replay samples for each online sample. We have considered ratios of 1/2,3/4, and 7/8 and observed stable training for all of them. Observe that among those values, larger ratios more data-cfficient as they take advantage of more replayed experience per training step.
5.4 SHARED EXPERIENCE REPLAY WITH OFF-POLICY TRUST REGION V-TRACE
In line with proposition 2 we observe in Figure 3 (left) that hyper- parameter sweeps without trust- region are even surpassed by the baseline without experience replay. State-of-the-arr results are obtained in Figure 3 (right) when experience is shared with trust-region in PBT sweep.
Observe that this indicates parallel exploration benefits and saves memory at the same time: in our sweep of 10 replay agents the difference between 10 x 10M (separate replays) and 10M (shared replay) 10-fold. This effect would even more pronounced with larger sweeps.
As discussed in section 2.3, the bias in V-trace occurs due to the clipping of importance ratios. A potential solution of reducing the bias would be to increase the P threshold to clip less aggressively and accept increased variance. Figure 4 in the appendix shows that this is not solution.
5.5 EVALUATION ON ATARI
We apply our proposed agent Atari which has been long established suite to evaluate reinforcement algorithms (Bellemare et al., 2013). Since we focus on sample-efficient learning we present our results in comparison to prior work 200M steps (Figure 1). Shared experience replay obtains even better performance than not shared experience replay. This confirms the efficient use of parallel exploration (Kretchmar, 2002). The fastest prior agent to reach 400% presented by Kapturowski et al. (2019) requiring more than 3.000M steps. LASER with shared replay achieves 423% in 60M per agent. Given 200M steps it achieves 448%. We also present a single (no sweep) LASER agent that achieves 431% in 200M steps.
CONCLUSION
We have presented LASER - an off-policy actor-critic agent which employs large and shared experience replay to achieve data-efficiency. By sharing experience between concurrently running experiments in ppprmmer sweep it is able to take advantage of parallel exploration. As a result it achieves state-of- the-art art data efficiency on 57 Atari games given 200M environment steps. Furthermore achieves competitive results on both DMLab-30 and Atari under regular, not shared experience replay conditions.
To facilitate this algorithm we have proposed two approaches: a) mixing replayed experience and on-policy data and b) trust region scheme. We have shown theoretically and demonstrated through a series of experiments that they enable learning in strongly off-policy settings, which present a challenge for conventional importance sampling schemes.
REFERENCES
Brandon Amos, Laurent Dinh, Serkan Cabi, Thomas Rothörl, Sergio Gomez Colmenarejo, Alistair Muldal, Tom Erez, Yuval Tassa, Nando de Freitas, and Misha Denil. Learning awareness models. In ICLR, 2018
Pierre-Lue Bacon, Jean Harb, and Doina Precup. The option-critic architecture. AAAI, 2017.
Charles Beattie, Joel Z. Leibo, Denis Teplyashin, Tom Ward, Mareus Wainwright, Heinrich Küttler, Andrew Lefrancq, Simon Green, Víctor Valdés, Amir Sadik, Julian Schrittwieser, Keith Anderson, Sarah York, Max Cant, Adam Cain, Adrian Bolton, Stephen Gaffney, Helen King, Demis Hassabis, Shane Legg, and Stig Petersen. Deepmind lab. Arxiv, abs/161 2016.
Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The Arcade Learning Environment: An evaluation platform for general agents. JAIR, 2013.
10

---

Under review as a conference paper at ICLR 2020
Richard Bellman. A markovian decision process. Journal of Mathematics and Mechanics, 1957.
Andrew R. Conn, Nicholas I. M. Gould, and Philippe L. Toint. Trust- Prust-Region Methods. SIAM, Philadelphia, PA, USA, 2000.
Thomas Degris, Martha White, and Richard S. Sutton. Off-po actor-critic. In ICML, 2012.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, Shane Legg, and Koray Kavukcuoglu. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. In ICML, 2018.
Audrunas Gruslys, Will Dabney, Mohammad Gheshlaghi Azar, Bilal Piot, Mare Bellemare, and Remi Munos. The reactor: fast and sample-efficient actor-critic agent for reinforcement learning. In ICLR, 2018.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In ICML, 2018.
Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Daniel Horgan, Bilal Piot, Mohammad Gheshlaghi Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. Arxiv, abs/1710.02298. 2017.
Matteo Hessel, Hubert Soyer, Lasse Espeholt, Wojeiech Czarnecki, Simon Schmitt, and Hado van Hasselt. Multi-task deep reinforcement learning with popart. In AAAI, 2019.
Todd Hester, Matej Vecerik, Olivier Pietquin, Marc Lanciot, Tom Schaul, Bilal Piot, Andrew Sendonaris, Gabriel Dulac-Amold, Ian Osband, John Agapiou, Joel Leibo, and Audrunas Gruslys. Learning from demonstrations for real world reinforcement learning. In AAAI, 2017.
Sepp Hochreiter and Jürgen Schmidhuber Long short-term memory. Neural Comput., 178: 1780, November 1997. ISSN 0899-7667. doi: 10.11622neco. http://ccoo.99..9.. 1997.9.8.178
Dan Horgan, John Quan, David Budden, Gabriel Barth-Maron, Mattco Hessel, Hado van Hasselt, and David Silver. Distributed prioritized experience replay. In ICLR, 2018.
Max Jaderberg. Valentin Dalibard, Simon Osindero, Wojeiech M. Czamecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, Chrisantha Fernando, and Koray Kavukcuoglu. Population based training of neural networks. Arxiv, abs/171 1.09846, 2017a.
Max Jaderberg, Volodymyr Mnih, Wojeiech Marian Czarnecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. ICLR, 2017b.
Herman Kahn. Use of different monte carlo sampling techniques. Santa Monica, Calif., 1955.
Lukasz Kaiser, Mohammad Babacizadch. Piotr Milos, Blazej Osinski, Roy H. Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, Ryan Sepassi, George Tucker, and Henryk Michalewski. Model-based reinforcement learning for atari. Arxiv, 0as/1903.00333 2019.
Steven Kapturowski, Georg Ostrovski, John Quan, Remi Munos, and Will Dabney. Recurrent experience replay distributed reinforcement learning. ICLR, 2019.
R.M Kretchmar. Parallel reinforcement learning. SC12002, The 6th World Conference on Systemics, Cybernetics, and Informatics. Orlando, FL, 2002.
Guillaume Lample and Devendra Singh Chaplot. Playing FPS games with deep reinforcement learning. AAAI, 2016.
Long-Ji Lin. Reinforcement Learning for Robots Using Neural Newworks. PhD thesis, Pittsburgh, PA, USA, 1992. UMI Order No. GAX93-22750.
Daniel J. Mankowitz, Augustin Zidek, André Barreto, Dan Horgan, Matteo Hessel, John Quan, Junhyuk Oh, Hado van Hasselt, David Silver, and Tom Schaul. Unicorn: Continual learning with a universal, off-policy agent. Arxiv, abs/ ///18002.8224 2018.

---

Under review as a conference paper at ICLR 2020
Piotr Mirowski. Razvan Pascanu, Fabio Viola, Hubert Soyer, Andrew J. Ballard, Andrea Banino, Misha Denil, Ross Goroshin, Laurent Sifre, Koray Kavukcuoglu, Dharshan Kumaran, and Raia Hadsell. Learning to navigate in complex environments. In ICLR, 2017.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. Playing atari with deep reinforcement learning. Arxiv, abs/1312.5602, 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-55 223-5333, 2015.
Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lillicrap. Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In ICML., 2016.
Andrew Moore and C. G. Atkeson. Prioritized sweeping: Reinforcement learning with less data and less real time. Machine Learning, 13, October 1993.
Remi Munos, Tom Stepleton, Anna Harutyunyan, and Mare Bellemare. Safe and efficient off- off-policy reinforcement learning. In NIPS. 2016
Arun Nair, Praveen Srinivasan, Sam Blackwell, Cagdas Alcicek, Rory Fearon, Alessandro De Maria, Vedavyas Panneershelvam, Mustafa Suleyman, Charles Beattie, Stig Petersen, Shane Legg, Volodymyr Mnih, Koray Kavukcuoglu, and David Silver. Massively parallel methods for deep reinforcement learning. Arxiv, abs/
2015.
David S. Olton. Mazes, maps, and memory. American Psychologist, 1979.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. Understanding the exploding gradient problem. Arxiv, abs/1211.5063. 2012.
Doina Precup, Richard S. Sutton, and Satinder Singh. Eligibility traces for off-policy policy evaluation. In ICML, 2000.
Martin Riedmiller. Neural fitted iteration first experiences with data efficient neural reinforce- ment learning method. In ECML, 2005.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In ICI.R, 2015.
Tom Schaul, Diana Borsa, Joseph Modayil, and Razvan Pascanu, Ray interference: a source of plateaus in deep reinforcement learning. 2019.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1889-1897, Lille, France, 07-09 Jul 2015. PMLR.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. Arxiv, 0bs//1007006444 2017.
Richard Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: framework for temporal abstraction in reinforcement learning. Artif. Intell., 112(1-2):111-11,, Augus 1999. ISSN 0004-3702, doi: (0.0066/50004433700000000003
Richard S. Sutton, Joseph Modayil, Michael Delp, Thomas Degris, Patrick M. Pilanski, Adam White, and Doina Precup. Horde: A scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction. Proc. of 10th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2011). 2011.
Richard S. Sutton, Ashique Rupam Mahmood, Doina Precup, and Hado van Hasselt. new q(A)
with interim forward view and Monte Carlo equivalence. In ICMI., 2014.
12

---

Under review as a conference paper at ICLR 2020
Richard S. Sutton, Andrew G. Barto, and Francis Bach. Reinforcement Learnigg: An Introduction. MIT press, 2018.
Gerald Tesauro. Temporal difference learning and gammon. Commun. ACM, 38(3):88--0) 68, March 1995. ISSN 0001-0782. doi: 10.1 10/14423333002233444
Edward C. Tolman. Cognitive maps in rats and men. The Psychological Review, 1948.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double Q- learning. In AAAI, 2016.
Ziyu Wang, Victor Bapst, Nicolas Heess, Volodymyr Mnih, Remi Munos, Koray Kavukcuoglu, and Nando Freitas. Sample efficient actor-critic with experience replay. ICLR, 2017.
Williams. Simple statistical gradient-follwingg algorithms for connectionist reinforcement learning. ML, 1992.
Zhongwen Xu, Hado P van Hasselt, and David Silver. Meta-gradient reinforcement learning. In NIPS. 2018.
Shangtong Zhang and Richard S. Sutton. A deeper look at experience replay. Arxiv, abs/1712.012777 2017.
APPENDIX A ADDITIONAL EXPERIMENTS
A.1 REDUCED CLIPPING IN V-TRACE DOES NOT ENABLE SIARRED EXPERIENCE REPLAY
Increasing the clipping constant in V-trace reduces bias in favour of increased variance. We investigate if reducing bias in this manner enables sharing experience replay between multiple agents syper-parameter sweep. Figure 4 (left) shows that this a solution, thus motivating our trust region scheme.
PBT sweep:
pria-itizing experience replay by advantage
shared Hypersarameter
roplay (various V-trace rhos)
90
100
80
90
Median
75
80
70
65
60
60
50
55
40
2.0
Environment Steps
4.0
B
B
10
2B
Environment Steps
4
B
8
10
Raseline: no replay
Nalvely shared (o=?)
Baseline: no replay
Prioritized #=0.5
Nalvely shared (p=:
Naively shared (o
Uniform replay
Prddritized #=
Increasing the V-trace clipping constant f does not enable shared experience replay. In fact sharing experience replay in this particular way is worse than pure online learning. This motivates the of our proposed trust region scheme. On side note, increased clipping thresholds resulting in worse performance verifies the importance of variance reduction through clipping. Right: Median human normalized performance across 30 tasks for the best agent in sweep, averaged across 2 replicas. All replay experiments use 50% replay ratio and capacity of 3 million observations. We investigate if uncorrected LSTM states can be used in combination with different replay modes. We consider uniform sampling and prioritization via the critic's 's loss, and include both full (3 = 1) and partial (3 0.5) importance corrections
Figure 4: Left:
13

---

Under review as a conference paper at ICLR 2020
A.2 PRIORITIZED AND UNIFORM EXPERIENCE REPLAY, LSTM STATES
With prioritized experience replay each transition is sampled with probability P(T) x pG, for suitable unnormalized priority score p- and a global tunable parameter a. It is common (Schaul et al., 2015; Horgan et al., 2018; Hessel et al., 2017) to then weight updates computed from that sample by 1/ P( for 0 < 3 S 1, where 3 = fully corrects for the bias introduced in the state distribution. In one step temporal difference methods. typical priorities are based on the immediate TD-error, and are typically recomputed after a transition is sampled from replay. This means low priorities might stay low and get stale even if the transition suddenly becomes relevant. To alleviate this issue, the sampling distribution is mixed with uniform, controlled by a third hyper parameter
The performance of agents with prioritized experience replay can be quite sensitive to the hyper- parameters a, B, and e.
critical practical consideration is how to implement random access for recurrent memory agents such as agents using an LSTM. Prioritized agents sample presumably interesting transition from the past. This transition may be at any position within the episode. To infer the correct recurrent memory-state at this environment-state all earlier environment-statte within that episode would need to be replayed. A prioritized agent with a random access pattern would thus require costly LSTM refreshes for each sampled transition. If LSTM states are not recomputed representational missmatch (Kapturowski et al., 2019) occurs.
Sharing experience between multiple agents amplifies the issue of LSTM state representation miss- match. Here each agent has its own network parameters and the state representations between agents may be arbitrarily different.
As a mitigation Kapturowski et al. (2019) use a burn-in window or to initialize with a constant starting state. We note that those solutions can only partially mitigate the fundamental issue and that counter examples such as arbitrarily long T-Mazes (Tolman, 1948; Olton, 1979) can be constructed easily.
We thus advocate for uniform sampling. In our implementation we uniformly sample episode. Then we replay each episode from the beginning. using the most recent network parameters to recompute the LSTM states along the way: this is particularly critical when sharing experience between different agents, which may have arbitrarily different state representations.
This solution is exact and cost-efficient as it only requires one additional forward pass for each learning step (forward + backward pass).
An even more cost efficient approach would be not refresh LSTM states at all. Naturally this comes at the cost of representational missmatch. However it would allow for an affordable implementation of prioritized experience replay. We investigate this in Figure 4 (right) and observe that it is not viable. We compare a baseline V-trace agent with no experience replay, one with uniform experience replay, and two different prioritized replay agents. We do not refresh LSTM states for any of the agents.
The uniform replay agent is more data efficient then the baseline, and also saturates at higher level of performance. The best prioritized replay agent uses full importance sampling corrections (93 1). However it performs no higher than with uniform replay. We therefore used uniform replay with full state correction for all our investigations in the paper.
A.3 EVALUATION PROTOCOL
For evaluation, we average episode returns within buckets of IM (Atari) and 10M (DMLab) envi- ronment steps for each agent instance, and normalize scores on each game by using the scores of a human expert and a random agent (van Hasselt et al., 2016). In the multi-task setting, we then define the performance of each agent as the median normalized score of all levels that the agent trains on. Given the use of population based training, we need to perform the comparisons between algorithms at the level of sweeps. We do by selecting the best performing agent instance within each sweep at any time. Note that for the multi-task setting, our approach of first averaging across many episodes, then taking the median across games, DMLab further downsampling to 100M env steps, and only finally selecting the maximum within the sweep, results in substantially lower variance than if we to compute the maximum before the median and smoothing.
14

---

Under review as a conference paper at ICLR 2020
All DMLab-30 sweeps repeated 3x with the exception of p and 4 in Figure 4. We then plot a shaded area between the point-wise best and worst replica and a solid line for the mean. Atari sweeps having 57 games summarized and plotted by the median of the human noman-normalized scores.
APPENDIX B ALGORITHM PSEUDOCODE
We present algorithm pseudocode for LASER with trust region (Algorithm 1). For clarity we present a version without LSTM and focus the single agent case. The multi-agent case is simple extension where all agents save to the same replay database and also sample from the same replay. Also each agent starts with different network parameters and hyper-parametert The LSTM state recomputation can be achieved with Replayer Threads (nearly identical to Actor Threads) that sample entire epsiodes from replay, step through them while reevaluating the LSTT state and slice the experience into trajectories of length T. Similar to regular LSTM Actor Threads from Espeholt et al. (2018) the Replayer Threads send each trajectory together with an LSTM state the learning thread via a queue. The Learner Thread initializes the LSTM with the transmitted state when the LSTM is unrolled over the trajectory.
Algorithm 1 Single Agent LASER with Trust Region
Initialize parameter vectors 0. Initialize πj 7Tg.
Actor Thread:
while training is ongoing do
Sample trajectory unroll = (TE (TE),E of length T by acting in the environment using the latest TA where = (st, at. Tt, p4 = T (stl))) Enqueue u into Lerner Queue, wait if full.
Add u into Replay Database.
Remove oldest trajectory if database has reached desired capacity limit.
end while
Learner Thread:
Given: Batch size B, online fraction
for training iteration & do
Form training batch U (uI..e( of B trajectories of length T, by dequeuing Ba trajectories from Lerner Queue and sampling B(1 a) trajectories from Replay Database. Evaluate the target policy 2 on the sampled transitions U: i.c. (T(.).1))) Compute behaviour relevance mask M with Ma.- = (L(T(()b,))) (1b,t) < 6 where Ma,t: Sb, are obtained from Ub.--
Compute trust-region V-trace return Ve, using 8 where X (8b.e) ( Mo,e- Let [Lv (0)),,- (Vi. (s
Let Ar,b = V.6 - (*t,)) and [T (0))e, = Pr, log ( Ac.. where p is the clipped v-trace importance sampling ratio.
Perform gradient update to 0 using V E.,(<v + Lp(0))r, denote the resulting as
TR++1 end for
APPENDIX C PROPOSITIONS
We have stated five propositions in our paper for which we provide proofs below.
Proposition 1. The V-trace value estimate V is biased: It does not match the expected return of ा but the return of a related implied policy ă defined by equation 9 that depends on the behaviour policy p:
min (pj((a))) [<a[=)]
(9)
EbEa min (pn(b)=),
Proof. See Espeholt et al. (2018).
15

---

Under review as a conference paper at ICLR 2020
Proposition 2. The V-trace policy gradient is biased: given the the optimal value function V the V-trace policy gradient does not converge to a locally optimal n² for all off aff-policy behaviour distributions μ.
Proof. Proof by contradiction:
Consider a tabular counter example with a single (locally) optimal policy at s, given by x-" (5()) =
argmax, [aaEA r(aass))2* (a, st)] that always selects the action argmax,[""0 (a, 8t).
Even in this ideal tabular setting V-trace policy gradient estimates different H* rather than the optimal x as follows
VV* (8))
Ep lpc(re + (V*((V++) (sc+)V
Ey Ip.Q" (st, a.) V log (arls:))
( se)
Ep
min
Q as) (acls)))
pla st)
st)
min p(ar(())
Ep
(5 at) V log T(ar()))
(10)
[u(a 8t)
(())(s))
min 1, (())
E
Q* (st; at) ((rls()))))
x(ae|
Ex (s))),))) (st, az) log (acls:))
E, (se, 0z) log (ac(s))
Observe how the optimal Q-function Q" scaled by w(s,, at) min [1, m
S resulting
x()ele))
in implied state-action values Q* This penalizes actions where ((ae)s;) < (a)))) and makes
V-trace greedy w.r.t. to the remaining ones. Thus p can be chosen ad adversarially to corrupt the optimal state action value. Note that f is constant typically chosen be 1.
To prove the lemma consider counter example such as an MDP with two actions and Q (2,5) 5) and μ = (0.9, 0.1) and initial favourable. Abusing notation μı/T (1.8, 0.2). Thus Q* =(2 1,5 0.2) = (2, 1). Therefore π = (1 wrongly selects the first action.
(0.5, 0.5). Here the second action with expected return is clearly
Proposition 3. Mixing on-policy data into the V-trace policy gradient with the ratio a reduces the bias by providing regularization to the implied state-action values. In the general function approximation case il changes the off-policy V-trace policy gradient from E, (s) [[(ss, a) log ग ())s]] to
E.E, E. (s, a) V log x [a]s)] where Q" Qd" (s)a + ds)) a) regularized state- action estimate and d" dl' are the state distributions for and Note that there exists a S 1 such
that QO has the same argmax (i.e. best action) Q.
Proof. Note that the on-policy policy gradient is given by
(T) = Σ dt (T) E, [Q(s, a (lg
Similarly the off-policy V-trace gradient is given by
(Jo Σ d Es) Q(s.
with the V-trace distortion factor w(s,, a.) ) min [, p(ee x(o, [c)
< that can de-emphasize action
values and Q (s, a) a8),))((ss))))
16

---

Under review as a conference paper at ICLR 2020
The a-interpolation of both gradients can be transformed as follows:
VaJon + (1- - (o)))a))( a Σ d' (s) ((s.))
Σ d' [d
d" (1s.)
+
(1
Σ ( +
0 =
d d" (s)a (0
Σ (og
(11)
for Q (s, a) = (s)) + (s)
Interpretation of Proposition 3 As discussed in section the V-trace policy gradient will have the correct local fixpoint state if the argmax of the state-value function is preserved despite the distortion: i.e. if argmax, [Q(s, a)] = argmax,
(I (s, a)). Respectively when mixing in an [0, 1) share of online data the fixpoint will be preserved if
argmax, [Q(s, a)) argmax, ( (s,a)
(12)
Let a" argmaxy (Q, be any best action and A be set of best actions. Then equation 12 is equivalent to:
as. (s, b) Vb &b A"
Using the definition of Q" this can be rewritten as:
((s, a" "d" (s)a + Q" a" )d (s) - a) > ((s (s)a + (* - a) Ab & A
Which can rearranged to:
[Q(s, a (s
b)d ()d
a) vb A
By definition Q(s, dd) (s) Q(, b)dd (s) > 04b & A", hence:
(s (s, (s) 1-a Q(s.a*) Qs, (s)(s)
4h AbEA" A*
It follows that the policy gradient will have the same local fixpoint if
Cx
Q"(ssb))(((ss0
(s. - (8, a*)
d')(s)
max bg
-(s,at)-Q1
d=((s)
(13)
Note that - 00 - 1. Mixing-in more online data thus increases the left hand side. Also note that the right hand side decreases due to (s) (s) if i visits the state s more often than μ. Furthermore the larger the action value gap in the real Q-function Q(s, right hand side. Finally the denominator will be negative if max IQ" (s, b)] < Q" (s, thus enabling correct learning even in the pure off- off-policy case with 0.
Q(s, b) the lower the
17

---

Under review as a conference paper at ICLR 2020
Note that all of those conditions can be computed and checked if accurate Q-function and state distribution is accessible. How to use imperfect Q-function estimates to adaptively choose such an a remain question for future research.
Proposition 4. Let Gis be a set of importance sampling estimators as defined in equation 7. Note that they all have the same fix point V and contract with at least 7/. Then the contraction properties carry over to V
trusted In particular |
V* S < IV V* 100
Proof. Let consider the set of importance sampling estimators defined in 7 and note that they all contract to the same fixed point V with at least E [G1s (s) - VT(s) S
Y [V
- (s) for any state s.
By Minkowski's inequality the contraction properties of importance sampled Monte-Carlo bootstraps carry over to iuusted which is a p(z)uz u2 E Ms,x(8;) weighted average:
Verusted (s))
Eg
E
GTs (s)] us E Mo.r( -
Epal= 19 (s)] - (s) E MM
Eg
E
E G1s (s)] v (*((s)) luz Mann(
(14)
E.
Y (V()) Vn (s) M2 E Ma)r((s)
Proposition 5. Let Gitrce be set of V-trace estimators (see equation with corresponding fixed points V (see equation 3) to which they contract at a speed of an algorithm and behaviour specific U2z Then trusted moves towards V BeluuEMs.. [V*] shrinking the distance as follows
Virstedd -V8 0o < &maxp,eMa..ta (V V²) ( I 7max
IVV - V*y with
Imax
Proof. Recall the contraction properties of a V-trace importance sampled Monte-Carlo bootstraps Geeraee being
Ep.1= (Gvttac V (s) n= ((s)
for an algorithm and behaviour specific 7)= < for z dependent fixed point V and for any bootstrap V. We then show that V trusted moves towards the weighted average of fixed points V = Es) [V*], since
V
Virusted (s) - V <
Tmax
max E.EMs
(V(s) (*)
holds for any bootstrap function V as we show below.
Virusted (5) - =
Ez E E GT (5) (5)] V+))/ Mancow))
E.
E la GT (5)] (*) Ie= Man((s))
Eg
(VV)
- (s)) us E Mar
(15)
max
(V<(V(s) (*(
n. ((,
< Mmax
(V(s) (*))) max
ne (
18

---

Under review as a conference paper at ICLR 2020
APPENDIX D DETAILED ATARI RESULTS
We display the Atari per-level performance of various agents at 50M and 200M environment steps in Table 2. The scores correspond to the agents presented Figure 1. The LASER scores are computed by averaging the last 100 episode returns before 50M or respectively 200M environment frames have been experienced. Following the procedure defined by Mnih et al. (2015) we initialize the environment with a random number of no-op actions (up to 37 in our case). Again following Mnih al. (2015) episodes are terminated after 30 minutes of gameplay. Note that Xu et al. (2018) have not published per-level scores. Rainbow scores are obtained from Hessel et al. (2017).
19

---

Under review as a conference paper at ICLR 2020
Table 2: Per level performance of various agents at 50M and 200M environment steps (see Figure 1).
LASER Shared
LASER Shared
LASER
Rainbow (no sweep at 200M)
Game
(sweep at 50M)
(sweep at 200M)
(no sweep at 200M)
alien
18635.3
18277.3
35565.9
9491.7
amidar
1838.3
2695
1829.2
5131.2
assault
26027.1
40603.2
21560.4
14198.5
asterix
496735.0
240770
240090
428200
asteroids
232651
257420.1
213025
2712.8
atlantis
889934.0
866584
841200
826660
bank_heist
1333.1
1712.8
569.4
1358
battle zone
66900
131880.0
64953.3
62010
beam_ride rider
80830.5
125795.2
90881.6
16850.2
berzerk
46651.6
64513.1
25579.5
2545.6
bowling
42.4
47.4
48.3
30
boxing
99.8
99.4
100.0
99.6
breakout
852.5
850.3
747.9
417.5
centipede
208008
409702.8
292792
8167.3
chopper_commpe command
24814
727333
761699.0
16654
crazy_elimber
160494
88818
167820
168788.5
defender
355447
369397.0
336953
55105
demon attack
133557
138000.6
133530
111185
double dunk
0.1
23,5
14
-0.3
enduro
2125.9
fishing_derby
45.4
62.6
45.2
31.3
freeway
34.0
34.0
34.0
frostbite
5297.4
2230.8
5083.5
9590.5
gopher
86222.2
39721.2
114820.7
70354.6
gravitar
1360.5
2812.0
1106.2
1419.3
hero
30159.2
36510.6
31628.7
55887.4
ice hockey
20.2
38.7
17.4
1.1
jamesbond
21663
60402.5
37999.8 8
19809
kangaroo
13932
14187
14308
14637.5
knull
9559.3
5743.6
9387.5
8741.5
kung_fu mmn_ffu_matter master
65032
81792
607443.0
52181
montezuma_reventg
1
0.3
384,0
ms _s__pamman name this game
6089.3
6890.7
6565.5
5380.4
25998.9
27910.7
26219.5
13136
phoenix
458355
628711.6
519304
108529
pitfall
-0.2
-0.2
-0.6
0.0
pong
21.0
21.0
21.0
20.9
private_eye
100
100
96.3
4234.0
qhert
20283.8
24600.8
21449.6
33817.5
riverraid
24138.1
35491.5
40362.7
22920.8
road runner
52942
63762.0
45289
62041
robotank
63.6
67.8
62.1
61.4
seaquest
1802.2
557213.3
2890.3
15898.9
skiing
-8904.8
-8980.1
29968.4
12957.8
solaris
2222.4
3017.6
2273.5
3560.3
space_invaders
36071.4 1.4
53124.3
51037.4 4
18789
star_gunner
331327
602540.0
321528
127029
surround
9.8
9,8
8.4
tennis
0
12.2
time_pilan peee_pplotttt_
77899
113603,0
105316
12926
tutankham
251.8
268.5
278.9
241
up_n_down
341988
368586.5
345727
125755
venture
0
5.5
video_ aadeo_pinball
513121
397451
511835
533936.5
wizard_ of wor
22280
45335.0
29059.3
17862.5
vars_revenge
145055
144370
166292.3
102557
zaxxon
50486
106862.0
41118
22209.5
20


Reviews:
[{"review_id": "ryxo9N4wKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors investigate off-policy actor-critic reinforcement learning where they want to make use of shared experience replay. Two approaches were suggested and compared. One was to mix replayed experience with on-policy data and the other was to create trust regions that only selects well-behaved behavioral distributions for state value estimation.\nAccording to the authors the several experiments provide evidence that their algorithm achieves competitive or even state-of-the-art results in data efficiency. They underpin this with some theoretical analysis.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "rJget8QTtH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims to improve the efficiency of the actor-critic method. The authors first analyzed the cause of instability in the prior work, from the perspective of bias and variance. Two remedies were then presented: (i) mixing the experience replay with online learning; (ii) proposing a trust region scheme to select the behavior policies. The authors finally tested the proposed method on Atari games, and showed the better results, compared with the state-of-the-art methods.\n\nIn my opinion, the empirical results are impressive, and the authors also provided some insights for the motivation. Given the results on Atari games, this paper could be a great contribution on the actor critic methods. The propositions are presented to support relevant claims, while their significance seems a bit limited, and some further clarification is necessary. The authors also need to address a few confusing statements and missing details.\n\n1. In Proposition 3, the authors claimed that mixing with on-policy data can reduce the bias. I checked the proof but did not find anything relevant. Also, what is the amount of bias reduced?\n2. In Equation (1), could you provide a formal definition for \"V\"? \n3. The authors claimed at the beginning of Section 4 that the trust region method was proposed to mitigate the bias and variance problem of V-trace. However, I did not see how this is reflected in Propositions 4 and 5. Is this statement only based on empirical results?\n4. It was mentioned right below Equation (4) that \"Observe how this inner expectation ... matches the on-policy return...\". Could you provide a formal proof?\n5. What are the hyperparameters for the 9 agents used in Figure 1? Also, how did you choose \"b\" in trust region?\n6. A few notation issues / typo:\n(1) it's -> its\n(2) In Equation (5), should \"z \\in M_{\\beta, \\pi} (s_t)\" be \"\\mu_z \\in M_{\\beta, \\pi} (s_t)\"?\n(3) At the 2nd line of Page 7, should the content for the indicator function be \"\\beta (\\pi, \\mu, s_t) < b\"?\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HygTpk4Z9S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper investigates off-policy actor critic (AC) learning with experience replay using V-trace. It shows that V-trace policy gradient is not guaranteed to converge to a local optimal solution. To mitigate the bias and variance problem of V-trace and importance sampling, a trust region approach is proposed to adaptively selects only suitable behavior distributions when estimating the state-value of a policy. To this end, a behavior relevance function (KL divergence) is introduced to classify behavior as relevant. The proposed learning method LASER demonstrates the state-of-the-art data efficiency in Atari among agents trained up until 200M frames. In all, this paper is well motivated and technically sound. The draft can be improved by making it more self-contained by providing a sketch of the proof rather than refer everything to the appendix. Also it might be helpful to provide a pseudocode of LASER to help readers better understand the technical details. \n\nOther comments and questions:\n\n1) When talking about the selection process, z is treated as a random variable. What is its distribution?\n2) what does “very off-policy learning” mean?\n3) In figure 3(left), why “LASER: shared + trust region” performs worse than “LASER: not shared”? \n4) In proposition 3. Q^w should be explained in the main text.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an off-policy actor-critic scheme where i) a buffer storing the trajectories from several agents is used (off-policy replay) and mixed with the on-line data from the current agent; ii) a trust-region estimator is used to select trajectories that are sufficiently close to the current policy (e.g. in the sense of a KL divergence).

As noted by the reviews, the results are impressive. 

Quite a few concerns still remain:
* After Fig. 1 (revised version), what matters is the shared replay, where the agent actually benefits from the experience of 9 other different agents; this implies that the population based training observes 9x more frames than the no-shared version, and the question whether the comparison is fair is raised;
* the trust-region estimator might reduce the data seen by the agent, leading it to overfit the past (Fig. 3, left);
* the influence of the $b$ hyper-parameter (the trust threshold) is not discussed. In standard trust region-based optimization methods, the trust region is gradually narrowed, suggesting that parameter $b$ here should evolve along time. 


Decision: Reject