Simplifying Deep Temporal Difference Learning
Authors: Matteo Gallici
Mattie Fellows
Benjamin Ellis
Bartomeu Pou
Ivan Masmitja
Jakob Nicolaus Foerster
Mario Martin
Venue: ICLR 2025 Spotlight (2025)
Keywords: Reinforcement Learning
TD
Theory
Q-learning
Parallelisation
Network Normalisation
Primary area: reinforcement learning

Abstract: $Q$-learning played a foundational role in the field reinforcement learning (RL).
However, TD algorithms with off-policy data, such as $Q$-learning, or nonlinear function approximation like deep neural networks require several additional tricks to stabilise training, primarily a large replay buffer and target networks. Unfortunately, the delayed updating of frozen network parameters in the target network harms the sample efficiency and, similarly, the large replay buffer introduces memory and implementation overheads. In this paper, we investigate whether it is possible to accelerate and simplify off-policy TD training while maintaining its stability. Our key theoretical result demonstrates for the first time that regularisation techniques such as LayerNorm can yield provably convergent TD algorithms without the need for a target network or replay buffer, even with off-policy data. Empirically, we find that online, parallelised sampling enabled by vectorised environments stabilises training without the need for a large replay buffer. Motivated by these findings, we propose PQN, our simplified deep online $Q$-Learning algorithm. Surprisingly, this simple algorithm is competitive with more complex methods like: Rainbow in Atari, PPO-RNN in Craftax, QMix in Smax, and can be up to 50x faster than traditional DQN without sacrificing sample efficiency. In an era where PPO has become the go-to RL algorithm, PQN reestablishes off-policy $Q$-learning as a viable alternative.

Published as a conference paper at ICLR 2025
SIMPLIFYING DEEP TEMPORAL DIFFERENCE LEARN- ING
Matteo Gallici*!
Mattie Fellows*?
Benjamin Ellis?
Bartomeu Poul.3 1.3
Ivan Masmitja
Jakob Nicolaus 2oerster
Mario Martin
Universiittt Politècnica de Catalunya
University of Oxford
Barcelona Supercomputing Center
Institut de Ciències del Mar
[gallici, millicci,maariin (es. upc. edu
(matthew. fel lows benjamin wamin.elliis jakob. foerster) Beng. sxng.ox.. aex.aacuu ba bartomeu. wwr.ome..pouuuleee........... @opuulee@bbcc.e. masmi jaš cic.c.m... csic.es
ABSTRACT
Q-learning played a foundational role in the field reinforcement learning (RL). However, TD algorithms with off-policy data, such as Q-learning, or nonlinear func- tion approximation like deep neural networks require several additional tricks stabilise training, primarily large replay buffer and target networks. Unfortunately, the delayed updating of frozen network parameters in the target network harms the sample efficiency and, similarly, the large replay buffer introduces memory and implementation overheads. In this paper, investigate whether it is possible accelerate and simplify off-policy TD training while maintaining its stability. Our key theoretical result demonstrates for the first time that regularisation techniques such as LayerNorm can yield provably convergent TD algorithms without the need for a target network or replay buffer, even with off policy data. Empirically, we find that online, parallelised sampling enabled by vectorised environments stabilises training without the need for large replay buffer. Motivated by these findings, we propose PQN, our simplified deep online Q-Learning algorithm. Surprisingly, this simple algorithm is competitive with more complex methods like: Rainbow in Atari, PPO- RNN in Craftax, QMix in Smax, and can be up to 50x faster than traditional DQN without sacrificing sample efficiency. In an era where PPO has become the go-to RL algorithm, PQN reestablishes off-policy Q-learning viable alternative. We open-source our code at: http://ggihub..co///ttaa/a/up//p
INTRODUCTION
In reinforcement learning (RL), the challenge of developing simple, efficient and stable algorithms remains open. Temporal difference (TI) methods have the potential to be simple and efficient, but are notoriously unstable when combined with either off-policy sampling or nonlinear function approximation (Tsitsiklis & Van Roy 1997). Starting with the introduction of the seminal deep Q-network (DQN)(Mnih et al. | 2013). many tricks have been developed to stabilise TD for use with deep neural network function approximators, most notably: the introduction of batched learning through replay buffer (Mnih et al. 2013), target networks (Mnih et al.) 2015). trust region based methods (Schulman al. | 2015), double Q-networks (Wang & Blei 2017 Fujimoto al. 2018). maximum entropy methods (Haarnoja et al. 2017 2018) and ensembling (Chen et al. [222]] Out of this myriad of algorithmic combinations, proximal policy optimisation (PPO) (Schulman al. 2017) has emerged the de facto choice for RL practitioners, proving be a strong and efficient bascline across popular RL domains. Unfortunately, PPO is far from stable and simple: PPO does not have provable convergence properties for nonlinear function approximation and requires extensive tuning and additional tricks to implement effectively (Huang et al.
2022a Engstrom et al.) 2020).
Recent empirical studies (Lyle et al.) 2023 2024 Bhatt al. 2024) provide evidence that TD can be stabilised without target networks by introducing regularisation such as BatchNorm (Loffe & Szegedy 2015) and LayerNorm (Ba et al. 20166) Nauman et al. 2024) into the Q-function approximator, Little known about why these techniques work or whether they have unintended side-effects. Motivated by these findings, we ask: are regularisation techniques such as BatchNorm and LayerNorm the key to unlocking simple, efficient and stable RL algorithms? To answer this question, we provide
"qqual Contribution.

---

Published as a conference paper at ICLR 2025
rigorous analysis of regularised TD. We summarise our core theoretical contributions as: I) Introduce a highly general and widely applicable analysis of TD stability; II) we show introducing LayerNorm and la regularisation into the Q-function approximator leads to provable convergence, stabilising nonlinear and/or off-policy TD without the need for targel networks or replay buffers.
Many applications in RL allow for multiple actions to be taken in environment at once, solving parallel world problem. Guided by our theoretical insights, we develop a modern off-policy value- based TD method which we call a parallelised Q-network (PQN): for simplicity, we revisit the original Q Q-learning algorithm (Watkins 1989), which updates Q-function approximator without target network. A recent breakthrough in RL has been running the environment and agent jointly on the
GPU Makoviychuk et al. 2021 Gu et al. 2023 Lu et al. 2022, Matthews et al., 2024b Rutherford 2023] Lange| 2022). However, the replay buffer's large memory footprint makes pure-GPU training impractical with traditional DQN. With the goal of enabling Q-learning in pure-GPU setting, we propose replacing a large replay buffer with a synchronous update across a large number of parallel environments, reducing memory requirements. For stability, we integrate theoretical findings in the form of a regularised deep Q network. We provide a schematic of our proposed PQN algorithm in Fig. ld
ct al.
Environment
LearTnT
Vectorised
Interact
Leaming Exporience
Environment
Ruskey Duthe
Batched
Environment
Leariigg
Q- Valuee
N-Newwrrk
Irwe act
rewmiing
CHMMAO
Interact
O Network
Batch
Borch
Cony
(a) Online Q-Learning
(b) DQN
(c) Distributed DQN
(d) PQN
Figure 1: Classical Q-Learning directly interacts with the environment and updates the learned Q- Q-values at each transition. In contrast, DQN stores experiences in replay buffer and trains Q-network using minibatches sampled from this buffer. Distributed DQN enhances this approach by collecting experiences parallel threads, while a separate process continually trains the network (i.c. a learner module and multiple actors modules run concurrently and independently). Similar to online Q Q-Learnigg PQN trains a Q-network with the experiences as they are collected in the same process, but conducts interactions and learning in batches.
To validate our theoretical results, we evaluated PQN in Baird's 's counterexample, a challenging domain that is provably divergent for off off-policy methods (Baird) (995).. Our results show that PQN can converge where non-regularised variants fails. We provide an extensive empirical evaluation to test the performance of PQN in single-agent and multi-agent settings. Despite its simplicity, our algorithm is competitive in range of tasks; notably, PQN achieves high performances in just few hours in many games of the Arcade Learning Environment (ALE) (Bellemare et al., 2013), competes effectively with PPO on the open-ended Craftax task (Matthews et al. 2024a), and stands alongside state-of-the-ar Multi-Agent RL (MARL) algorithms, such as MAPPO in Overcooked (Carroll et al., 2019) and Hanabi (Bard et al. 2020) and Qmix in Smax (Rutherford al.) 2023). Despite not sampling from a large buffer of historic data, the faster convergence of PQN demonstrates that the sample efficiency loss can be minimal. This positions PQN as a strong method for efficient and stable RL in the age of deep vectorised Reinforcement Learning (DVRL).
We summarise our empirical contributions: I)
we propose PQN, simplified, parallelised, and normalised version of DQN which eliminates the use of both large replay buffers and the target network; II) we demonstrate that PQN is fast, stable, simple to implement, uses few hyperparameters. and is compatible with pure-GPU training and temporal-basee our extensive empirical study demonstrates PQN achieves competitive results significantly less wall-clock time than existing state-of-the-ar methods.
networks such as RNNs, and III)
PRELIMINARIES
Let || denote the e e-nomm and P(X)) the set of all probability distributions over a set X.
2.1 REINFORCEMENT LEARNING
In this paper, we consider the infinite horizon discounted RL setting, formalised as a Markov Decision Process (MDP) (Bellman 1957 Puterman 2014): M = (S,A, Ps. Po, PR, 7) with bounded state space S, bounded action space A, transition distribution Ps : S x A + P(S), initial state distribution Py E P(S), bounded stochastic reward distribution PR S x A + P([-Tmaz+ F'moo]] where T mea E IR < oo and scalar discount factor y E [0, 1). An agent in state s, E taking action a, A observes reward r, Pn(ss, at). The agent's behaviour is determined by policy that
2

---

Published as a conference paper at ICLR 2025
maps a state to distribution over actions: क S + P(A) and the agent transitions to new state $141 ~ (s (t)) As the agent interacts with the environment through policy オ, it follows a trajectory T = (Sn. ao ro, $1 P1,............. 8t-1: 1,-1, 12 8t) with distribution P. For simplicity, we denote state-action pair 24 == (8t, (4) E X where X' == S x A. The state-action pair transitions under policy according to the distribution (x) X' ((x))
The agent's goal is to learn an optimal policy of behaviour x² E IT by optimising the expected discounted sum of rewards over all possible trajectories Js, where: II* = arg max, J is the set of optimal policies for the objective J = B EE== >rre]. The expected discounted reward for an agent in state s; for taking action at is characterised by a Q-function, which is defined recursively through the Bellman equation: (Tx(z)) = 8 (z1), where the Bellman operator 8" projects functions forwards by one step through the dynamies of the MDP: 8 [²"])(( = P (tt) (ra + 7Q"h (3++1)]- Of special interest is the Q-function for an optimal policy x², which we denote (*(xx)) == QT (xx)). The optimal Q-function satisfies the optimal Bellman equation Q" (z²) = B [Q" (2)), where B is the optimal Bellman operator: 5 (2)] =
E. 1 Pa.Psst))rraPPala ( + y max, (s a').
2.2 TEMPORAL DIFFERENCE METHODS
Many RL algorithms employ TD learning for policy evaluation, which combines bootstrapping, state samples and sampled rewards to estimate the expectation the Bellman operator (Sutton 1988). We introduce a Q-function approximation Qo X - R parametrised by ø E & to represent the space of Q-functions. We assume that Qo is initialised from a distribution do ~ Pa. In their simplest form, TD methods estimate the application of a Bellman operator by updating the Q-function approximator parameters according to:
0i+1 = Ø. + ai (r 1 (2') (x)) V V Qo
(I)
where I ~ d", ~ Pn(=), ~ (x) and a, is sequence of stepsizes satisfying the standard Robbins- Munro conditions (Robbins& & Monro 195I):
Assumption 1 (RM Conditions). We assume a; 0 with E aq x and Ei=o of < co.
Here d' E ( is a sampling distribution, and Ju is sampling policy that may be different from the target policy æ. Methods for which the sampling policy differs from the target policy are known as off-policy methods. In this paper, we will study the Q-learning (Watkins) 1989, Dayan 1992) TD update: 0:+1 = Φ; + ar(r + 7 supa Qo (s', a') Qo, VoQ) (z), which aims to learn an optimal Q-function by estimating the optimal Bellman operator. As data in Q-learning is gathered from an exploratory policy μ that is not optimal, Q-learning is an inherently off off-policy algorithm. For simplicity of notation we define the tuple == x')) with distribution Pa and the TD-error vector as:
(2) allowing us to write the TD parameter update as: 6i+1 = oi + a;ā(oi, Typically, dl is the stationary state-action distribution of an ergodic Markov chain but may be another offline distribution such as distribution induced by replay buffer. We introduce the following mild regularity assumptions for our analysis.
8(6,5) 5) = (r + (Q(('') -a
(x())) VoQo(1),
Assumption 2 (Regularity Assumptions). Assume that &b C RR is compact and convex and 8(0, s) is Lipschitz in Φ, S. When updating TD, x ~ dd is either sampled i...d from a distribution with support over X or is sumpled from a geometrically ergodic Markov chain with stationary distribution d'.
The condition of t C Rdd being compact ubiquitous in TD theory and stochastic approximation (Papavassiliou & Russell 1999 Nemirovski et al.] 2009 Maei et al. 2010 Kushner 2010 Lacoste-
Julien et al.) 2012] Bhandari et al. 2018 Wang et al., 2020 Yang et al. 2019 Zhang et al.) 2021) and can be achieved by projecting any o & & back into & using the projection Po(o) == arg minge | o' o- Projection is mathematical formality and should not be required in practice as & can be made large enough to contain all updates when TD is stable and a suitable stepsize regime is chosen. Finally, geometric ergodicity extends traditional notions of aperiodicity and irreducibility in discrete MDPs to the more general continuous state-action space formulations (see Roberts & Rosenthal (2004) for details). It one of the weakest ergodicity assumptions.
We denote the expected TD-error vector as: 8(Φ)= == E.- (5(,, s)}, and define the set TD fixed points as: o² E (0))(() 0}. If TD algorithm converges, must converge to TD fixed point as the expected parameter update is zero for all ø². We remark that convergence to TD fixed point does not imply a value error of zero between the approximate and true Q-function (Kolter 2011).
3

---

Published as a conference paper at ICLR 2025
2.3 VECTORISED ENVIRONMENTS
Parallelising the interactions between an RL agent and a learning environment is standard method for speeding up training. classical frameworks like Gymnasium (Towers et al. 2023), this achieved by processing multiple environments via multi-threading. In more recent GPU GPU-based frameworks like IsaacGym (Makoviychuk et al. 2021), ManiSkil12 (Gu et al. Craftax (Mathhww et al.) 2024b). JaxMARL (Ruthertord et al. (023) the environments' operations are vectorised, meaning that they are performed together using batched tensors. This allows an agent easily interact with thousands of environments, and enables the compilation of end-to-end GPU learning pipelines, which can accelerate the training of on-policy agents like PPO and A2C by orders of magnitude (Makoviychuk et al.) 2021 Weng et al. 2022, Gu et al. 2023 Lu al.) 2022). Unfortunately, end-to-end single-GPU training is not compatible with traditional off-policy methods like DQN for two reasons: firstly, maintaining a replay buffer in GPU not feasible in complex environments, as it would occupy most of the GPU memory; and secondly, the convergence of off-policy methods demands very high number of updates relation to the sampled experiences (DQN traditionally performs one gradient step per environment step). Commonly, parallelisation of Q-Learning (like in Ape-X (Horgan et al. 2018), R2D2 (apturowski et al. 2018) and a recent method presented in Li et al. (2023)) is achieved by continuously training the Q-network in separate process in order to keep up with the fast sampling (see Fig. [T], a setup that is not feasible in a
2023). Jumanji (Bonnet et al. (024),
single Pure-GPU setting. For this reason, all referenced frameworks primarily provide PPO or A2C baselines, i.e. vectorised RL lacks a off- ooficol Q-learning baseline.
2.4 RELATED WORK
Our paper makes several significant contributions across range of interconnected threads in RL research. We provide an extensive discussion of all related work in Appendix A
Ø++1
ANALYSIS OF REGULARISED TD
Φ
(gd(
Proofs for all theorems and corollaries can be found in Appendix B Building on (Bhandari al., 2018 Fellows al.) 2023), we now develop a powerful and general Jacobian analysis tool to characterise stability of TD approaches used in practice (Section 3.I). We then apply this analysis to regularised TD, confirming our theoretical hypothesis that careful application of LayerNorm and 12 regularisation can stabilise TD (Section 3.2). Finally, we compare LayerNorm to BatchNorm regularisa- tion techniques in Section 3.3, explaining our preference for LayerNorm. Recalling that I (s,a), we remark that our results can be derived for value functions by setting x = s in our analysis.
Φ
Figure 2: Geometric interpre-
tation of TD stability crite- rion. Expected updates in the shaded ball ensure contrac- tion mapping.
3.1 STABILITY OF TD
As TD updates aren't 't gradient of any objective, they fall under the more general class of algorithms
known as stochastic approximation (Robbins & Monro, [951] Borkar 2008). Stability is not guaranteed in the general case and convergence TD methods has been studied extensively (Watkins)
& DDaaan 1992] Tsitsiklis & Van Roy] 1997: Dalal et al., 2017| Bhandari et al., 2018 Srikant &
Ying 2019). We now extend the methods of Fellows et al. (203)) to study general nonlinear TD in a Markov chain, meaning our analysis applies exactly to TD methods used in practice. Key to
determining stability of the TD updates is establishing that the Jacobian is negative definite:
TD Stability Criterion: Define the TD Jacobian as J(Ø) Vgδ(Φ). The TD stability criterion holds if the Jacobian is negative definite, that is: v J(d) 0 for any test vector v & 0 and & E Φ. except possibly on set of measure O.
Intuitively, the Jacobian replaces the Hessian from classical optimisation theory (Boyd & Vanden berghe, 2004), which measures curvature of the underlying objective, thereby ensuring convexity. As TD methods are not a gradient of any objective, the TD stability condition instead implies 8(d)) (Ø.- x²) < 0 for all &i, ensuring the expected update vector will always move the parameters closer to fixed point with a sufficiently small stepsize. We sketch a geometric interpretation in Fig. 2 Mathematically, if the TD stability criterion holds, then stepsizes approach zero in the limit lim, -oc ag = 0, there exists some t such that for every i > t each update is a contraction mapping: o' II]. This key condition allows to prove convergence of TD:
E |1+1 x01]] < E (1
4

---

Published as a conference paper at ICLR 2025
Theorem 1 (TD Stability). Let Assumptions 7 and 2 hold. If the TD criterion holds then the TD updates in Eq. converge with: lim; E
0 x- 11 0.
We can split the TD Jacobian condition into two separate off-policy and nonlinear components: v J()) Conrolicy| (Qp. dd)) + CNonlimeur (Qe) (Q)), whose negativity ensure the overall TD stability criterion is satisfied (see Appendix [B.I). This naturally yields two forms of TD instability:
Off-policy Instability: The TD stability criterion can be violated if:
Compolicy (Q d3)) = P, (v T V ( - -Ez-d (o))o)(())) 0, (3) does not hold for any test vector v. To better understand the off-policy component, we invoke the Cauchy-Schward inequality show Egp., (v (o=))Q S Exadd (u v=lo(z)) is key to proving Comratay (Q d! < 0 (see Appendix B.1 for derivation). Unfortunately, ergodic theory reveals this condition only holds in the on-policy sampling regime, i.e. when dh = d for both i.i.d. or Markov chain sampling. For off-policy sampling, the distributional shift between the target policy and the sampling policy y can cause the expectation RR [c VoQo(z")) to be arbitrarily large. We conclude that ConPolicy (Qo, d't) characterises the degree of distributional shift that TD can tolerate before becoming unstable and off-policy sampling is key source of instability in TD, especially in algorithms such as Q-learning.
Nonlinear Instability: The TD stability criterion can be violated if:
(4) does not hold for any test vector v. This condition does not apply in the linear case second order derivatives are zero: (z) = 0. In the nonlinear case, the left hand side of the inequality can be arbitrarily positive depending upon the specific MDP and choice of function approximator Hence nonlinearity is a key source of instability in TD which is characterised by CNomlinear (Qail )... Together both off ooflpplicy and nonlinear instability formalise the deadly triad (Sutton & Barto [2018a] van Hasselt et al.) 2018) and TD can be unstable if either Conditions or are not satisfied. We now investigate how LayerNorm with f2 regularisation can tackle these sources of instability.
CNoolinear (imalincar(()) (Q+) == Ex=., [(r +20((=)) Qs (zx))o""'
< 0,
3.2 STABILISING TD WITH LAYERNORM + l REGULARISATION
To understand how LayenNorm with e regularisation stabilises TD, we study the following Q- function approximator:
(x(x) = Opea o LayerNorm [OP1e o .xx).
(5)
the parameter vector where M RR is k x matrix where each row ||m is bounded, w É IR* is vector of final layer weights where ||w||| is bounded and Pre and Post are element-wise C² continuous activations with bounded 2nd order derivatives. We assume the final activation Post is Lipschiip with Poss (0) = 0 (c.g. tanh, identity, GELU, ELU...).
Here @ = [w) [e T]
LayerNorm (Ba et al. 2016) is defined glement-wise as:
f(()) - - E (z)
1 Vk V E V E 5 (z)))) +
LayerNorm [f(x)]
(6)
where e >> 0 is small constant introduced for numerical stability. Deeper networks with more LayerNorm layers may be used in practice, however our analysis reveals that only the final layer weights affect the stability of TD with wide LayerNorm neural networks. We observe that adding LayerNorm does not affect the representational capacity of the network as it merely rescales the input according standard Gaussian. The output is then rescaled due to the final linear layer. As k increases, the empirical mean and standard deviations in Eq. (6) approach their true expectations, thereby increasing the degree of normalisation provided. Using the LayerNorm Q-function, we can bound the off-policy and nonlinear components of the TD stability condition:
Lemma 2. Let Assumption M apply. Let ew be the first k components of the test vector [o TT associated with with layer parameters w, and UM be the remaining components, associated with the matrix parameters Vec(M). Using the LayerNorm Q-function defined in Eq. ():
Off-Policy Bound:
ComPotioy (23 d S w| 2L/0/2|] + (11m)1//k),
(7)
Nonlinear Bound:
CNoalinear ( (Q²)) = O (1o11///R)
(8)
almost surely for any test vector and any state-action transition pair x, x' E X.
5

---

Published as a conference paper at ICLR 2025
Analysis in Eq. 7 and Eq. (8) of Lemma reveals that the degree of regularisation increases. that is in the limit l + oo, all nonlinear instability can be mitigated: lim CNoalincar
( (2)) =
and residual term left the off-po bound: limg->zo Compoticy (Q d't) - || ///0//221 The nonlinear bound in Eq. (8) can be explained using established theory of wide neural networks; as layer width increases, second order derivative terms tend to zero (Liu et al. 2020). Our proof extends this theory, showing that LayerNorm preserves this property.
As linear function approximators still stuffer from off off-policy instability due the distributional shift between π and μr, linearisation of wide networks cannot explain the bound in Eq. 7 Instead, our proof for Lemma reveals this bound is due to the normalising property of LayerNorm, which upper bounds the expected norm: Ex [|]LayerNorm" (M [Mæl]]] I regardless of the sampling
distribution d' or magnitude of M. This yields bound with residual term of m| -2L00/211 that is independent of æ and μr, overcoming the distributional shift issue responsible for off-policy instability. We tackle it by targeting & with e² regularisation using the following TD update vector:
6/g (t) 5) = 8h (Ø,5) 5) ((n (TLLew//)
[w]
(ec( ved(aa))
0
+ (1 (1-1)
0
for any 1) > 1 where 5² (0. 5) is the TD update vector from Eq. (2) using the LayerNorm critic from Eq. (5) respectively. Eq. 9 yields a bound:
ConPolicy (Q d() S (1 (1-n) (|o0w///m//21 [|a (14)),
which implies Compoteey a d O with sufficiently large k meaning the TD stability criterion will be satisfied. We now formally confirm now this intuition:
Theorem 2. Let Assumption 2 apply. Using the LayerNorm regularised TD update ( s) in Eq. (9). there exists some finite k' such that the TD stability criterion holds for all l >> k..
In Section 5.] we test our theoretical claim in Theorem P Jemprrccally, demonstrating that LayerNorm + f² regularisation can stabilise Baird's counterexample, an MDP intentionally designed to cause TD to diverge (Baird 1995). We remark that whilst adding an l² regularisation term -1j to all parameters can stabilise TD alone, large 1) recovers a quadratic optimisation problem with minimum at Φ = 0. pulling the TD fixed points towards O. Hence, we suggest F (f-regllarisation should be used sparingly; only when LayerNorm alone cannot stabilise the environment and initially only over the final layer weights. Aside from Baird's counterexample, we find LayerNorm without L2 regularisation can stabilise all environments in our extensive empirical evaluation in Section 3
3.3 LAYERNORM AND BATCHNORM TD
We have seen from Theorem 2 that LayerNorm l regularised TD can stabilise TD by mitigating the effects of nonlinearity and off-policy sampling. Empirical evidence suggests that BatchNorm (Toffe & Szegedy, 2015) regularisation, which essential for stabilising algorithms such as CrossQ (Bhatt et al.) 2024), may also possess similar properties to LayerNorm. It is natural to ask: 'what are the potential benefits of LayerNorm over BatchNorm methods?'
Naïvely applying BatchNorm presented by loffe & Szegedy (2015) does not stabilise TD as CrossQ does not succeed without applying several modifying 'tricks' such as double Q-learning, batch renormalisation using running statistics and calculating the batch statisties from mixture of datasets (Bhatt et al., 2024). In contrast, LayerNorm + l² regularisation benefits from the strong theoretical guarantees in Theorem without burdening practioners with additional tricks and their associated hyperparameter tuning. Additionally. compared to BatchNorm, LayerNorm does not require memory or estimation of the running batch averages.
Our empirical analysis in 5 that BatchNorm can degrade performance in some cases, while in others it can improve results if applied early in the network. Therefore, we don't 't dismiss BatchNorm outright, but a thorough theoretical analysis is needed to fully understand its practical effects. Nonetheless, we recommend starting with LayerNorm and g² regularisation as a strong, simple baseline for stabilising TD algorithms before experimenting with alternatives like BatchNorm.
4 PARALLELISED Q-LEARNING
Guided by analysis in Section B develop simplified version of deep Q-learing to exploit the power of parallelised sampling with minimal memory requirements and without target networks. The Q-Network is regularised with network normalisation (preferably LayerNorm) and (2 regularisation

---

Published as a conference paper at ICLR 2025
required (see Eq. (9)) As we developing online algorithm, is straightforward exploit n-step returns. In Algorithm [ we present PQN with A-returns, which is a parallelised variant of the approach of Daley & Amato (2019). An exploration policy Tappoor (e-greedy for this paper) is rolled out for a small trajectory of size T: (8i; (1, 0,, 8+41 ... 8(4T). Starting with Ri+r max, Qo(s d') the targets are computed recursively back time from R R using: R = [ARt) + (1 X) max,' Qo a')] or ItA = 7; s, is a terminal state, We provide derivation of our approach in Appendix B.4 Due the use of X-returns and minibatches, require a small buffer of size
containing interactions from the current exploration policy.
The special case À = 0 with T is equivalent to a vectorised variant of Watkins (1989's original Q-learning algorithm with LayerNorm La regularisation where / separate interactions occur in parallel with the environment.
Algorithm PQN with X-returns
PQN with A-returns is simpler than ex- isting state-of-the-art X-based algorithms such as Retrace (Munos et al.) 2016) which adopt computationally intensive techniques to handle the computation of A-targets. Similarly, an implementation of PQN using RNNS only requires sam- pling trajectories for multiple time-steps
1: initialise regularised Q-network parameters
2: 80 Po.
3: for each episode do
4:
for each i E {0, 1....... 1 13 (in parallel) do
5:
at MEsphon (st) (e.g. e-greedy)
6:
ri Pa(si, ai) 8141 (s ai),
7:
L 1+1
8:
end for
and then back paok-propaggting the gradient
9:
if I mod T = 0 then
through time in the learning phase. In contract existing approaches like R2D2
10:
calculate R to R for number epocks do for mumber of minibatches do
11:
(Kapturowski et al., 2018) that integrate
13:
draw minibatch B size b < I T from
RNNs with replay buffers must handle hid- den states of trajectories collected with old policies during replay. A basic multi-
Tt- and (0.... ... 1- @ + E V Ei.e (R. (x))))
14:
agent version of PQN for coordination
15:
end for
16:
end for
problems can be obtained by adopting
17:
end
Value Network Decomposition Networks
18:
end for
(VDN) (Sunchag et al., 2017b), i.c. opti-
mising the joined -ation-vvluu function as a sum of the single agents action-values. Finally, similar to PPO, is possible increase PQN's sample efficiency by dividing the collected experiences into multiple minibatches and using them multiple times within epochs.
Table summarises the advantages of PQN in comparison to popular methods. Compared to traditional DQN and distributed DQN, PQN enjoys ease of implementation, fast execution, very low memory requirements, and high compatibility with GPU-based training and RNNs. The only algorithm that shares these attributes PPO. However, although PPO is principle simple algorithm, its success is determined by numerous interacting implementation details (Huang et al.) 2022a Engstrom et al., 2020), making the actual implementation challenging. Moreover, PQN uses few main hyperparameters, namely the number of parallel environments, the learning rate and epsilon with its decay, plus the value for X-returns are used. We emphasise that, whilst PQN can be using single environment interaction at each timestep (i.e. with = 1, 1), yielding stable, regularised Q-learning algorithm without a replay buffer (see Fig. 10). PQN is also designed exploit vectorisation solve parallel world problems, i.e. applications trained in simulators where parallelisation advantageous and possible.
Table 1 Advantages and Disadvantages of DQN, Distributed DQN, PPO and PQN.
DQN
Distr. DQN
PPO
PQN
Implementation
Easy
Difficult
Medium
Very Easy
Memory Requirement
High
Very High
Low
Low
Training Speed
Slow
Fast
Fast
Fast
Sample Efficient
Yes
No
Yes
Yes
Compatibility with RNNs Compatibility end-to-end GPU Training Amount of Hyper-Parameters
Medium
Medium
High
High
Low
Low
High
High
Medium
High
Medium
Low
Convergence
No
No
No
Yes
7

---

Published as a conference paper at ICLR 2025
Ton douts Leg)
Austfew
Maitun Nontunnmaati Numatttd Sove 05
250%
1,00
Abers 10---0 Soome
200
200%
Kanbon
10
0.75
PgM
10
100
100%
0000 Ber. 100.
DBON
BRON
0.50
10
0.25
0.0 0.5
2.0
0
3 Normalisod Score
1
2
Single Game Full Suite
Frames 1c8
Frames
1e8
(a) Atari-10 Score
(b) Atari-57 Median
(c) Atari-57 Score Profile
(d) Speed Comparison
Figure 4: (a) Comparison between PPO and PQN in Atari-10. (b) Median score of PQN in the full Atari suite of 57 games. (c) Percentage of games with score higher than human score. (d) Computational time required to single game and full ALE suite for PQN and DQN implementation CleanRL. In (c) and (d) performances of PQN are relative to training for 400M frames.
4.1 BENEFITS OF ONLINE Q Q-LEARNING WITH VECTORISED ENVIRONMENTS
Vectorisation of the environment enables fast collection of many parallel transitions from independent trajectories. De- t-E noting the stationary distribution at time / of the MDP under policy n; as d uniformly sampling from replay buffer con- taining historic data estimates sampling from the average of
d
p Eiso of
all distributions across all timesteps: 2'+1 Ei d con- trast, vectorised sampling in PQN estimates sampling from the stationary distribution d at timestep t', We sketch the differ- ence in these sampling regimes in Fig. Coloured lines rep- resent different state-actions trajectories across the vectorised environment as function of timestep t. Crosses represent samples drawn for each algorithm at timestep t'.
DQN
PQN
Figure 3: Sketch of Sampling Regines DQN and PQN
PQN's sampling further aids algorithmic stability by better approximating this regime in two ways: firstly, the parallelised nature help exploration since the (potential) natural stochasticity in the dynamics means even a greedy policy will explore several different states in parallel. Secondly, by taking multiple actions in multiple states, PQN's sampling distribution is a good approximation of the true stationary distribution under the current policy: as time progresses, ergodic theory states that this sampling distribution converges to d' In contrast, sampling from DQN's replay buffer involves sampling from an average of older stationary distributions under shifting policies from single agent, which will be more offline and take longer to converge, as illustrated in Fig. 3 We emphasise
that PQN is still an off-policy approach since it uses two different policies optimise the Bellman
equations: the e-greedy policy for the current timestep and the current policy for the next. Notice that 1, mcaning that it approximates value function from
at beginning of training PQN uses normalisation to mitigate off off-policy instability identified in completely random policy. This requires Section 3
EXPERIMENTS
In contrast to prior work in Q-learning, which has focused heavily on evaluation in the Atari Learning Environment (ALE) (Bellemare et al. (0013), probably overfitting this environment, we evaluate PQN on a range of single- and multi-agent environments, with PPO as the primary baseline. We summarise the memory and sample efficiency of PQN in Table 2 Due to our extensive evaluation, additional results are presented in Appendix D All experimental results are shown as mean of 10 seeds, except in ALE where we followed a common practice of reporting 3 seeds.
5.1 CONFIRMING THEORETICAL RESULTS
Fig. shows that together LayerNorm + L can stabilise TD Baird's counterexample (Baird 1995). challenging environment that is intentionally designed to be provably divergent, even for linear function approximators. Our results show that stabilisation is mostly attributed to the introduction of LayerNorm. Moreover the degree of (*-regllarisation needed small just enough mitigate off- off-policy stability due to final layer weights according to Theorem 2 and it makes relatively little difference when used in isolation.
5.2 ATARI
To save computational resources, we evaluate PQN against PPO in the Atari- 10 suite of games from the ALE, which estimates the median across the full suite using smaller sample of games. PQN
8

---

Published as a conference paper at ICLR 2025
18
1000
1.00
12
Win Rate IQM
0.75
Mac Noraaiod
0.75
Low (eg)
Mesuma
0.50
0.50
022
0.25
10a
010
0
5000
1
0.0
0.5
Ta
0.0
23 Timestops
5.0
Episodes
Timesteps
Timesteps
le?
leb
Timesteps 1e10
(a) Baird's Counter.
(b) Craftax
(c) Smax
(d) Overcooked
(e) Hanabi
Figure 5: Results in Baird's Counterexample. Craftax and Aultt-Agent tasks. For Smax, report the Interquartile Mean (IQM) of the Win Rate on the most popular maps. For Overcooked, we report the IQM of the returns normalized by the maximum obtained score in the classic 4 layouts. In Hanabi, we report the returns of self-play in the 2-player game.
outperforms PPO in terms of sample efficiency, final score, and training time (1 hour compared to 2.5 hours for PPO), and also surpasses sample-efficient methods like couble-DQN and Prioritised DDQN in the same number of frames, despite these methods being trained for several days and using over 16 times more gradient updates (12.5M compared to 780k for PQN). To further test our method, we train PQN on the full suite of 57 Atari games. Fig. 4d shows that the time needed to train PQN on the full Atari suite is equivalent to the time required to train traditional DQN methods on a single gamd"] With additional budget of 100M frames (30 minutes of training). PQN achieves the median score of Rainbow (Hessel et al.] 2018), which is still a SOTA method in ALE for sample efficiency but requires around 3 days of training per game, meaning that PQN can be considered 50x faster. While Rainbow is slightly more sample efficient, it's important to note that Rainbow is a much more complex system, designed specifically for Atari. Moreover, parallelisation of Q-Learning has traditionally sacrificed far more sample efficiency than PQN. For instance, Ape-X struggles to solve even the simplest Atari game, Pong, within 200M frames (Horgan et al. 2018). In this regard, PQN represents a significant advancement in Q-Learning research, offering a balanced compromise between speed, simplicity, and sample efficiency.
In Appendix D we provide detailed data from these experiments, comparison with Dopamine- Rainbow using the IQM score, and a comparative bar chart (Fig. [3) of the performances of algorithms in all the games. In this chart, we show that PQN reaches human-level performance in 40 of the 57 games of the ALE, underperforming mainly in the hard-exploration games, suggesting that the e-greedy exploration used by PQN is too simple to solve ALE, and indicating a clear research direction to improve the method.
5.3 CRAFTAX
Craftax (Mathhews et al. 2024b) is an open-ended RL environment based on Crafter (Hafner 2021) and Nethack (Künlerr al.] 2020). It challenging environment that requires agent solve multiple tasks before completion. By design, Craftax is fast to run in pure-GPU setting, but existing benchmarks are based solely on PPO. The observation size of the symbolic environment around 8000 floats, making a pure-GPU DQN implementation with a buffer prohibitive, as it would take around 30GBs of GPU-ram. PQN can provide an off- off- policy Q-learning baseline without using GPU memory for replay buffer. Following the Craftax paper, we evaluate for 1B steps and compared PQN to PPO using both an MLP and an RNN. The RNN results are shown in Fig. (5b] PQN is more sample efficient and with RNN obtains higher score of 16 % against the 15.3% of PPO-RNN. The two methods also take a similar amount of time to train. PQN offers researchers a simple, successful Q-learning alternative to PPO that can be run on GPU in this challenging environment.
5.4 MULTI-AGENT TASKS
When dealing with multi-agent problems, any replay buffer needs to store observations for all agents, increasing the memory requirements up to hundreds of gigabytes. Additionally, RNNs are highly effective in handling the individual agents' partial observability of the environments and credit assignment, a key challenge in MARL, is typically addressed with vasue-based methods SSunehag et al. (2017b); Rashid et al. (2020a). Therefore, memory-efficiem
RNN-compatible and value- based method is highly desirable. We evaluate PQN combined with VDN in Hanabi (Bard et al.. 2020). SMAC-SMACV2 (Ellis al. 2024, (Samvelyan et al. 2019) (in its JAX-vectorised version, Smax) (Rutherford et al. 2023), and Overcooked (Carroll et al. 2019). Smax is a faster version of SMAC, running entirely on a single GPU. Notably, when at least 20 agents are active in the environment, replay buffer can consume all available memory on a typical 10GB GPU. PQN-VDN runs successfully on Smax without large buffer, outperforming MAPPO and QMix. Remarkably, PQN learns coordination policy even in the most difficult scenarios in about 10 minutes, compared
DQN training time was optimistically estimated using the JAX-hased CleanRI. DQN implementation.

---

Published as a conference paper at ICLR 2025
200
-Lasefion
200
Retrns (e.cctt.e Mac)
Mox Nomalliee JQM
1.00+
Atart to Scoe.
-Basthin
Modi ie Sone
10
0.75
10
100-
100
0.50
PON
0.25
0-
PMNi-buleer
0.00
Frames le8
I
0.0
Timesteps lc9
0.
1:0
Frames
les
Time (Hours)
18
36
6.
Timesteps le?
0.5
13
(a) Normalisation in (b)
Normalisation in (c) X-returns in Atari- (d) Replay Buffer in (e) Num. Environ-
Atari-10
Craftax
10
Craftax
ments in MinAtar
Figure 6: Ablations confirming the importance of the different components of our method.
to QMix's 's 1 hour (see Fig. 17). Similarly, PQN outperforms the replay-buffer- based version of VDN and PPO in Overcooked, and is significantly more sample-efficient than MAPPO in Hanabi, where achieves an average score of 24 points.
5.5 ABLATIONS
To examine the effectiveness of PQN's algorithmic components, we perform the following abla- tions.
Regularisation: In Fig. oal we examine the impact of regularisation on performance in the Atari- suite. Results show that LayerNorm significantly improves performance, supporting the theoretical findings in Section 3 while BatchNorm can degrade performance when applied through the network. Additionally, applying the additional tricks from CrossQ further worsens PQN's performance.
Input Normalisation: In preliminary experiments, we observed that BatchNorm significantly improves PQN performances in Craftax. Figure [b] compares the performance of PQN RNN with BatchNorm, LayerNorm, and normalisation in the two cases where BatchNorm is applied to the input before the first hidden layer or not. Without input normalisation, BatchNorm provides substantial boost. However, PQN performs best when only the input to the first layer is batch normalised, and applying LayerNorm to the rest of the network offers similar improvement. This suggests BatchNorm can be effective as input normalisation, particularly in scenarios like Craftax with large, sparse observation vectors.
Varying A: In Fig. 6c we compare different values of in Atari- We find that value of A = 0.65 performs the best by significant margin. It significantly outperforms À = 0 (which is equal to performing I-step update with the traditional Bellman operator) confirming that the use of X-retumns represents important design choice over one-step TD.
Replay Buffer: In Fig. 6dd we compare PQN from with a variant that maintains a standard sized replay buffer of 1M of experiences in GPU using Flashbax TToleoo al. (2023). This version converges to the same final performance but takes ~-6 longer to train, which is likely due to the constant need to perform random access of a buffer of around 30GBs. This reinforces our core message that large memory buffer should be avoided in pure GPU training.
Number of Environments: PQN can learn even with small number of environments but clearly benefits from collecting more experiences in parallel (Fig. be). As expected, PQN is also significantly faster when greater parallelisation is used, (see Fig. 10 in Appendix).
6 CONCLUSION
Table 2: Summary of Memory Saved and Speedup of PQN Compared to Baselines. The Atari speedup is relative to the traditional DQN pipeline, which runs single environment the CPU while training the network on GPU. Smax and Craftax speedups are relative to baselines that also run entirely on GPU but use a replay huffer. The Hanabi speed-up is relative to an R2D2
We have presented the first rigorous analysis explain- ing the stabilising properties of LayerNorm and f regularisation in TD methods. These results allowed us to develop PQN, simple, stable and efficient regularised Q-learning algorithm without the need for target networks or a large replay buffer. PQN exploits vectorised computation to achieve excellent performance across an extensive empirical evalu- ation with significant boost in computational ef- ficiency and without sacrificing sample efficiency. PQN offers a simple pipeline that is easy to imple- ment and out-of-the-box compatible with key ele- ments in RL, such as X-returns and RNNs, which are otherwise difficult to use in current Q-Learning implementations. Additionally, it provides a valuable baseline for multi-agent systems. By saving the memory occupied by large replay buffers, PQN paves the way for a generation of powerful but stable algorithms that exploit end-to-end GPU vectorised deep RI.
implementation.
Memory Saved
Speedup
Atari
26gb 10gb (up to hundreds)
50x
Smax Hanabi
6x
250gb
4x
Craftax
31gh
6x
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
All our experiments can be replicated with the following repository:
Proofs for all theorems and corollaries can be found in
Appendix
ACKNOWLEDGMENTS
Mattie Fellows is funded by a generous grant from the UKRI Engineering and Physical Sciences Research Council EP/Y02848 1/1. Jakob Nicolaus Foerster is partially funded by the UKRI grant EP/Y028481/1 (originally selected for funding by the ERC). Jakob Nicolaus Foerster also supported by the JPMC Research Award and the Amazon Research Award.
Matteo Gallici was partially founded by the FPI-UPC Santander Scholarship FPI-UPC .3. Ivan Masmitja is partially founded by the European Union's Horizon Europe programme under grant agreement No 101 12883, as part of DIGI4ECO. This work also acknowledges the Spanish Ministerio de Ciencia, Innovacion y Universidades (BITER-ECO: PID2020- 114732RBC3)) 1), the the Spanish National Program Ramon y Cajal RYC2022-038056-1 (IM) and "Severo Ochoa Centre of Excellence" accreditation (CEX2019-000928.
REFERENCES
Matthew Aitchison, Penny Sweetser, and Marcus Hutter. Atari-5:
Distilling the arcade learning environment down five games. In International Conference on Machine Learning, pp. 421-438.
PMLR, 2023, C
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. arXiv preprint 1677 2016.
3.2
Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Zhaohan Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benchmark.
In International Conference on Machine Learning (ICML), pp. 507-517. PMIR, 2020. A.T
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Proceedings of the Twelfth International Conference on Machine Learning (ICML), pp. 30-37, 1995. doi: 10. 10.1.1.48.3255 48.266. [ 3.2 5.1
Nolan Bard, Jakob N Foerster, Sarath Chandar, Neil Burch, Mare Lanctot, H Francis Song, Emilio Parisotto, Vincent Dumoulin, Subhodeep Moitra, Edward Hughes, et al. The Hanabi challenge: A new frontier for ai research. Artificial Intelligence, 130:103216, 2020.
| 5.4
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
5
Richard Bellman. markovian decision process. Journal of Mathematics and Mechanics, 6(5):
1957. ISSN 00955905,, 19435274. URL www.http:11 /ww.. istor..... /tw.tssrrorro...........e.rr stable/
24900506 211
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. arXiv preprint arXiv:1806.024500 2018. 2.2
A.2 B.2
Aditya Bhatt, Daniel Palenicek, Boris Belousov, Max Argus, Artemij Amiranashvili, Thomas Brox, and Jan Peters. Crossq: Batch normalization in deep reinforcement learning for greater sample efficiency and simplicity. The Twelfih International Conference on Learning Representations, 2024. htt.tttss://pereiiiiet
A.3
Clément Bonnet, Daniel Luo, Donal Byrne, Shikha Surana, Sasha Abramowitz, Paul Duckworth, Vincent Coyette, Laurence I. Midgley, Elshadai Tegegn, Tristan Kalloniatis, Omayma Mahjoub, Matthew Macfarlane, Andries P. Smit, Nathan Grinsztajn, Raphael Boige, Cemlyn N. Waters, Mohamed A. Mimouni, UIrich A. Mbou Sob, Ruan de Kock, Siddarth Singh, Daniel Furelos- Blanco, Victor Le, Arnu Pretorius, and Alexandre Laterre. Jumanji: diverse suite of scalable reinforcement learning environments in jax, 2024. URL htttp::: /arxiv. org/
abs /ag//b//// 2306
09884 2.3
11

---

Published as a conference paper at ICLR 2025
Vivek Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint. Hindustan Book Ageney Gurgaon, 01 2008. ISBN 978881-859311-5--2 doi: 10.1007/978- 90177788-38882--3388 3.1
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
3.1
Micah Carroll, Rohin Shah, Mark K Ho, Tom Griffiths, Sanjit Seshia, Pieter Abbeel, and Anca Dragan. On the utility of learning about humans for human-ai coordination. Advances in neural information processing systems, 32, 2019. 5.4
Pablo Samuel Castro, Subhodeep Moitra, Carles Gelada, Saurabh Kumar, and Marc G. Bellemare.
Dopamine: A Research Framework for Deep Reinforcement Learning. 2018. URL http:
06110
12
Xinyue Chen, Che Wang, Zijian Zhou, and Keith W. Ross. Randomized ensembled double q-learning:
Learning fast without a model. The Ninth International Conference on Learning Representations (ICLR), abs/2101.05982, 2021.
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analysis for TD(0) with linear function approximation. arXiv preprint arXiv:1704.01161, 2017. 3.1 A.2
Brett Daley and Christopher Amato. Reconciling X-returns with experience replay. Advances in Neural Information Processing Systems, 32, 2019.
B.4
Peter Dayan. The convergence of TD(A) for general X. Mach. Leamn, 8(3 4):34143411333 May 1992. ISSN 0885-6125. doi: 10.10077BF00999200. URL httpttss//oo...22200..000
BF00992701 2.2
Christian Schroeder De Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip HS Torr, Mingfei Sun, and Shimon Whiteson. Is independent learning all you need in the starcraft multi-agent challenge? arXiv preprint arXiv:20/ 1.09533, 2020. A.5
Benjamin Ellis, Jonathan Cook, Skander Moalla, Mikayel Samvelyan, Mingfei Sun, Anuj Mahajan, Jakob Foerster, and Shimon Whiteson. SMACv2: An improved benchmark for cooperative multi- agent reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
5,4
Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph, and Aleksander Madry. Implementation matters deep policy gradients: case study on ppo and trpo. In International Conference on Learning Representations, 2020.
Mattie Fellows, Matthew Smith, and Shimon Whiteson. Why target networks stabilise temporal difference methods. In International Conference Machine Learning, 2023.
A.2
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. Proceedings of the Thirty-Secome AAAI Conference on Artificial Intelligence, pp. 2972-2982, 2018. A.5
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. International Conference Machine Learning, abs/ abs/|882.00947. 2018.
Jiayuan Gu, Fanbo Xiang, Xuanlin Li, Zhan Ling, Xiqiang Liu, Tongzhou Mu, Yihe Tang, Stone Tao, Xinyue Wei, Yunchao Yao, Xiaodi Yuan, Pengwei Xie, Zhiao Huang, Rui Chen, and Hao Su. Maniskill2: A unified benchmark for generalizable manipulation skills. In International Conference on Learning Representations, 2023.
Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1352-1366 1361, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR. URI. http: httptttppppppcp.eeeiptpcooo http:///mm.rrppeeee/////aaaaaaaa
html 1
12

---

Published as a conference paper at ICLR 2025
Tuomas Haamojja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft Actor-Critics Off-policy maximum entropy deep reinforcement learning with stochastic actor. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1861-1870, Stockholmsmässan Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http:http:::pcceeeee ngs. ml press/ wr80/haarnjjal@.. html
Danijar Hafner. Benchmarking the spectrum of agent capabilities. In
The Ninth International
Conference on Learning Representations, 2021. 5.3
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, 2018. 5.2
Matthew W. Hoffman, Bobak Shahriari, John Aslanides, Gabriel Barth-Maron, Nikola Momchev, Danila Sinopalnikov, Piotr Stańczyk, Sabela Ramos, Anton Raichuk, Damien Vincent, Léonard Hussenot, Robert Dadashi, Gabriel Dulac-Amold, Manu Orsini, Alexis Jacq. Johan Ferret, Nino Vieillard, Seyed Kamyar Seyed Ghasemipour, Sertan Girgin, Olivier Pietquin, Feryal Behbahani, Tamara Norman, Abbas Abdolmaleki, Albin Cassirer, Fan Yang. Kate Baumli, Sarah Henderson, Abe Friesen, Ruba Haroun, Alex Novikov, Sergio Gómez Colmenarejo, Serkan Cabi, Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Andrew Cowie, Ziyu Wang, Bilal Piot, and Nando de Freitas. Acme: research framework for distributed reinforcemeett learning. arXiv preprint arXiv:2006.00999 2020.
A.
Dan Horgan, John Quan, David Budden, Gabriel Barth-Maron, Matteo Hessel, Hado Van Hasselt, and David Silver. Distributed prioritized experience replay. arXiv preprint arXiv:1803.00933.
2018. 2.3 5.2 C
Hengyuan Hu, Adam Lerer, Brandon Cui, Luis Pineda, Noam Brown, and Jakob Foerster. Off-belief learning. In International Conference on Machine Learning, pp. 4369-4379, PMLR, 2021. C
Shengyi Huang, Rousslan Fernand Julien Dossa, Antonin Raffin, Anssi Kanervisto, and Weixun Wang. The 37 implementation details of proximal policy optimization. In ICLR Blog Track, 2022a. URL 25/ppo- www.mppmmmmettiioommm.mm wnw.aattioooneeddls.... impleneenaaiionddttalll//
Shengyi Huang, Rousslan Fernand Julien Dossa, Chang Ye, Jeff Braga. Dipam Chakraborty, Kinal Mehta, and João G.M. Araújo. Cleanrl: High-quality single-file implementations of deep reinforce- ment learning algorithms. Jourmal of Machine Learning Research, 23(274):1-18, 2022b. URL
http:// http::/mmmrrrrogoo www.r..rrgpppppprre /23/2v/121122 1342211111...1 html
C
Sergey loffe and Christian Szegedy. Batch normalization: accelerating deep network training by reducing internal covariate shift. In Proceedings of the 32nd International Conference International Conference on Machine Learning Volume 37, ICML'15, pp. 448-456. JMLR.org,
2015. 3.3
Steven Kapturowski, Georg Ostrovski, John Quan, Remi Munos, and Will Dabney. Recurrent experience replay in distributed reinforcement learning. In The Sixth International Conference on Learning Representations (ICI.)) 2018. 2.3
A.1
J. Kolter. The fixed points of off-policy td. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 24, Cur- Associates, Inc., 2011. URL ht http:::::pp/pocceeeiiioo www.:newurii.eeeeee ctppape.cpppppppppppp files/
2.2
Tadashi Kozuno, Yunhao Tang, Mark Rowland, Remi Munos, Steven Kapturowski, Will Dabney, Michal Valko, and David Abel. Revisiting peng's 's q(lambda) for modern reinforcement learning. In
Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 5804. PMLR. mirr wttppppwwssss..ppppeeppp html
18-24 Jul 2021. URL https: A.4
13

---

Published as a conference paper at ICLR 2025
Harold J. Kushner. Stochastic approximation: survey. Wiley Interdisciplinary Reviews: Com- putational Statistics, 2, 2010. URL/httss://app www.antiiiccooo....oooooooooaeae
15194610 2.2
Heinrich Küttler, Nantas Nardelli, Alexander Miller, Roberta Raileanu, Marco Selvatici, Edward Grefenstette, and Tim Rocktäschel. The nethack learning environment. Advances in Neural Information Processing Systems, 33:7671-7684, 2020. 5.3
Simon Lacoste-Julien, Mark Schmidt, and Francis Bach. A simpler approach obtaining an o(1/t)
convergence rate for the projected stochastic subgradient method. 12 2012. 2.2
Robert Tjarko Lange, gymmax: A JAX-bused reinforcement learning environment library, 2022. URL http:://githi com wtt.c./toooo......aggee////e//ee gymmax
Zechu Li, Tao Chen, Zhang- Wei Hong, Anurag Ajay, and Pulkit Agrawal. Parallel q-leaming: Scaling off-policy reinforcement learning under massively parallel simulation. In International Conference on Machine Learning, pp. 19440-19459, PMLR, 2023. 2.3
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant, In Proceedings of the 34th International Conference on Neural Information Processing Systems, NeurlPS 2020, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829544 3.2 B.3
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. arXiv preprint 1xXiv:1908.03200 2019. C
Ryan Lowe, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative--oompttiiee environments. Advances in neural information processing systems, 30, 2017. A.5
Chris Lu, Jakub Kuba, Alistair Letcher, Luke Metz. Christian Schroeder de Witt, and Jakob Foerster. Discovered policy optimisation. Advances in Neural Information Processing Systems, 35:16455- 16468, 2022. 2.3
Clare Lyle, Zeyu Zheng, Evgenii Nikishin, Bernardo Avila Pires, Razvan Pascanu, and Will Dabney, Understanding plasticity neural networks. In International Conference on Machine Learning. pp. 23190-23211. PMIR, 2023. A.2 A.3
Clare Lyle, Zeyu Zheng, Khimya Khetarpal, Hado van Hasselt, Razvan Pascanu, James Martens, and Will Dabney. Disentangling the causes of plasticity loss in neural networks. arXiv preprint 18762, 2024.
A.3
Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, and Richard S. Sutton. Toward off-policy learning control with function approximation. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML' 10, pp. 719-726, Madison, WI, USA, 2010. Omnipress. ISBN 9781605589077. 2.2
Viktor Makoviychuk, Lukasz Wawrzyniak, Yunrong Guo, Michelle Lu, Kier Storey, Miles Macklin, David Hoeller, Nikita Rudin, Arthur Allshire, Ankur Handa, and Gavriel State. Isaac gym: High performance gau-based physics simulation for robot learning, 2021. 2.3
Michael Matthews, Michael Beukman, Benjamin Ellis, Mikayel Samvelyan, Matthew Jackson, Samuel Coward, and Jakob Foerster. Craftax: A lightning fast benchmark for open-ended rein- forcement learning. arXiv preprint 3rXiv:2402.16800 2024a. C
Michael Matthews, Michael Beukman, Benjamin Ellis, Mikayel Samvelyan, Matthew Jackson, Samuel Coward, and Jakob Foerster. Craftax: A lightning- fast benchmark for open-ended rein- forcement learning. arXiv preprint arXiv:2402.16688 16801, 2024b. 2.3 5.3
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforeement learning. arXiv preprint arXiv:1312.566 2013. URL httt::/arxiv. wwg. 2bb.//11...600 1rriv1312256022oomee NIPS Deep Learning Workshop 2013.
cite
14

---

Published as a conference paper at ICLR 2025
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Pe- tersen, Charles Beattie, Amir Sadik, loannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep rein- forcement learning. Nature, 518(7540):529 5333, February 2015. ISSN 00280836. URL
http://dx wtt.::/..o....ogg..ooooo www..................11 www.11/0//naauue122222
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap. Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Maria Florina Balcan and Kilian Q. Weinberger (eds.). Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1928 1937, New York, New York, USA, 20 22 Jun 2016. PMLR. URLhttps //proceedings mlr press / 1448mmnnaal 6 html
A.I
Remi Munos, Tom Stepleton, Anna Harutyunyan, and Mare Bellemare. Safe and efficient off- policy reinforcement learning. In D. Lee, M. Sugiyama, U. Luxburg. I. Guyon, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 29, Curran Asso- ciates, Inc., 2016. URL /tL/ttttps://prrceedddng www.:nngg......rr......... cc/paper files/paper/ Papeeaappere.e pdf
A.4
Michal Nauman, Matcusz Ostaszewski, Krzysztof Jankowski, Piotr Miłos, and Marck Cygan, Bigger, regularized, optimistic: scaling for compute and samplc-efficient continuous control, 2024. URL
https:///axix: org/ abs 2405. 16588
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal Optimizatiion, 19(4):1574 1609, 2009. doi: 10.1137/ 070704277. URL httt:::t::////.. //doi./oii./o http:///o....//....11//..0 1t.../.000//0....0..........0000 1137700770777777
2.2
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 29, Curran Asso- ciates, Inc., 2016. URL htt.httss://prrceeeett
neurips......m www.:ruwwwrw...r.rarrreee wc/paper.p.pp.....e files/paper/
www.ssoff-aapr..oom pdf
C
Ian Osband, Yotam Doron, Matteo Hessel, John Aslanides, Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba Szepesvari, Satinder Singh, al. Behaviour suite for reinforce- ment learning. arXiv preprint arXiv: 035668 2019. C
Vassilis A. Papavassiliou and Stuart Russell. Convergence of reinforcement learning with general function approximators. In Proceedings of the 16th International Joint Conference on Artificial Intelligence Volume 2, IJCAI' 99, pp. 748-755, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc.
Jing Peng and Ronald Williams. Incremental multi-step q-learnin. In William W. Cohen and Haym Hirsh (eds.), Machine Learning Proceedings 1994, pp. 226-232. Morgan Kaufmann, San Francisco (CA), 1994. ISBN 978-1-55860-
doi: https://doi.org// 1011110000009998-5555566 335-6.500335 URL h 7 www. www.sccciieeeiiieeeecccccee com/ sci cctmm//sc.eencaaaarrieeeppppppp
E8781558603355500333 A.4
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John
Wiley & Sons, 2014. 2.1
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farguhar, Jakob Foerster, and Shimon Whiteson. Monotonic value function factorisation for deep multi-agent reinforcement
learning. Journal of Machine Learning Research, 21 2020a. 5.4
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Monotonic value function factorisation for deep multi-agen reinforcement learning. Journal of Machine Learning Research, 21 (1 2020b. A.5
Herbert Robbins and Sutton Monro. A Stochastic Approximation Method.
The Annals of Math- URL https
ematical Statistics, 22(3):400- 407, 1951, doi:
(eter//....1...... 121 2214/aamms /
2.2
3.1
15

---

Published as a conference paper at ICLR 2025
Gareth O. Roberts and Jeffrey S. Rosenthal. General state space Markov chains and MCMC algorithms. Probability Surveys, 1 ((none):20 71, 2004, doi: 10. 01.21//115957704400000022 URL
https::/doi org. 1ttp:/....11111141111111 1tt.:///....11111111111101011110
2.2
Alexander Rutherford, Benjamin Ellis, Matteo Gallici, Jonathan Cook, Andrei Lupu, Gardar Ing- varsson, Timon Willi, Akbir Khan, Christian Schroeder de Witt. Alexandra Souly, et al. Jaxmarl: Multi-agent rl environments in jax. arXiv preprin! urXiv:2311.10005 2023.
2.3 5.4
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder De Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint urXiv::9022 942404043, 2019, 5.4
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. URL wttptttss//pcceeeeeesess http://333/schhmma13333 ht.ll
mlr
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy 2017. URL
optimization algorithms. CoRR,
abs/
2707.06344
Kyunghwan Son, Daewoo Kim, Wan Ju Kang. David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International Conference on Machine Learning (ICML.. pp. 5887-5896. PMLR, 2019. A.5
Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and td learning. In Conference on Learning Theory, pp. 2803-2830 PMLR, 2019. 3.1 A.2
Peter Sunchag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanetot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. valooodeconnooittoon networks for cooperative multi-agent learning. arXiv preprint arXiv: / 700.05526, 2017a. A.5
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanetot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, et al. deloposccoooooiiionn networks for cooperative multi-agent learning. arXiv preprint arXiv: arXiv: 1706.05296 2017b.
4 5.4
Richard S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 3 10:9-44, Aug 1988. ISSN 1573-0565. doi: 10. 1007/BF0000 15009. 2.2
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 201 8a. URL httt:p://iiccoppeestiiaaa..errrt wwt./oooo/teetbbbbbeeeeeoeo
2nd.htm
Richard S Sutton and Andrew Barto. Reinforcement learning: An introduction. MIT press, 2018b.
C
Edan Toledo, Laurence Midgley, Donal Byrne, Callum Rhys Tilbury, Matthew Macfarlane, Cyprien Courtot, and Alexandre Laterre. Flashbax: Streamlining experience replay buffers for reinforce- ment learning with jax, 2023.
com/ http://hwww....ooeeeacceee/eaaaa
5,5
Mark Towers, Jordan K. Terry, Ariel Kwiatkowski, John U. Balis, Gianluca de Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Arjun KG, Markus Krimmel, Rodrigo Vicezt-icente, Andrea Pierré, Sander Schulhoff, Jun Jet Tai, Andrew Tan Jin Shen, and Omar G. Younis. Gymnasium, March 2023. httpstts::2 :ttp:::::///eooooooo www.o/.oodoo/ooom htt.p//ww...raeeeerrr/////110/.0
2.3
J. N. Tsitsiklis and B. Van Roy. An analysis of temporal-difii differrecee learning with function approxi- mation. IEEE Transactions on Automatic Control, 42(5):674-690, May 1997. ISSN 2334-3303. doi: 00.1100/9.58087
Hado van Hasselt, Yotam Doron, Florian Strub, Matteo Hessel, Nicolas Sonnerat, and Joseph Modayil. Deep Reinforcement Learning and the Deadly Triad. working paper or preprint, December 2018.
URL httpt::://// //has wwwennccececccccccccccoo 0111-1949300
3.1
16

---

Published as a conference paper at ICLR 2025
Lingxiao Wang, Qi Cai, Zhuoyan Yang, and Zhaoran Wang. On the global optimality of model-
agnostic meta-learning: reinforcement learning and supervised learning. Proceedings of the 37th International Conference on Machine Learning, ICML'20, JMLR.org, 2020. 2.2
Yixin Wang and David Blei. Frequentist consistency of variational bayes. Journal of the American Statistical Association, 05 2017. doi: 10. 1080000/11 (1ee6622244440000 459.2018. 1473376. I
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Mare Lanctot, and Nando Freitas. Dueling network architectures for deep reinforcement learning. In International Conference on Machine
Learning (ICML), pp. 1995-2003, PMLR. 2016. C
Christopher J. C. H. Watkins and Peter Dayan. Technical note: -learning. Mach. Learn,, 8(3-4) 279-292, May 1992. ISSN 0885-6125. doi: 10. N0.1007/BB009992698, URL htthht:ps//oll.. org/
10 19.1007//0 9F00996600009888888 992698
3.1
Christopher John Cornish Hellaby Watkins. Learning from Delayed Rewards. PhD thesis. King's College, University of Cambridge, Cambridge, UK. May 1989. URL http://www: CS. rhul
ac. ac.uk/-chriss sw new stwewtthheissseeeeee pdf
Jiayi Weng, Min Lin, Shengyi Huang, Bo Liu, Denys Makoviichuk, Viktor Makoviychuk, Zichen Liu, Yufan Song. Ting Luo, Yukun Jiang, Zhongwen Xu, and Shuicheng Yan. EnvPool: A highly parallel reinforcement learning environment execution engine. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Ad- vances in Neural Information Processing Systems, volume 35, pp. 22409-22421. Cur- ran Associates, Inc., 2022. URL fttp:://proceednnss.eeurriii cc/paprr
fi
Datasets and Benchmarks.pdi 2.3
Zhuora Yang. Yuchen Xie, and Zhaoran Wang. A theoretical analysis of deep q-learning. 2019, 2.2
Kenny Young and Tian Tian. Minatar: An atari-inspired testbed for thorough and reproducible reinforcement learning experiments. arXiv preprint arXiv: 0317900,0376,,.. 2019, C
Chao Yu, Akash Velu, Fugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo cooperative multi-agent games. Advances in Neural Information Processing Systems, 35:24611-24624, 2022. A.5
Yang Yue, Rui Lu, Bingyi Kang, Shiji Song, and Gao Huang. Understanding, pre- dicting and better resolving q-value divergence in offline-rl. In A. Oh, T. Naumann, Saenko, M. Hardt, and S. Levine (eds.), Advances Neural In-
A. Globerson, http:////ppppccccioi..//////aaaa formation Processing Systems, volume 36, pp. 60247-60277. Curran Associates, Inc.. h
2023. URL htattps://prooeeedigg.... wewpeeedddiinn....uuueeeeeeeeeee www.:sssssrspspc.cpppccceeeeeeee http:pppprr.iileeepppp//2/2/222 File/ FLle://obba11ee77ddd722ddddddddd
.df A.2
Shangtong Zhang, Hengshuai Yao, and Shimon Whiteson. Breaking the deadly triad with target network. Proceedings of the International Conference on Machine Learning, Unknown Month
2021. |RLR 2.2
17

---

Published as a conference paper at ICLR 2025
A RELATED WORK
A.1 ASYNCHRONOUS METHODS AND PARALLELISATION OF Q-LEARNING
Existing attempts to parallelise Q-learning adopt a distributed architecture, where a separate process continually trains the agent and sampling occurs in parallel threads which contain delayed copy of its parameters (Horgan et al. 2018; Kapturowski et al. 2018: Badia et al. 2020 Holfman et al.) 2020). On the contrary, PQN samples and trains in the same process, enabling end-to-end single GPU training. While distributed methods can benefit from separate process that continuously train the network, PQN is easier to implement, doesn't 't introduce time-lags between the learning agent and the exploratory policy. Moreover, PQN can be optimised to be sample efficient other than fast, while distributed system usually ignore sample efficiency.
Mnih al. ( propose an asynchronous Q-learning, parallelised version of Q-learning which performs updates of a centralised network asynchronously. Compared to PQN, asynchronous Q- learning still uses target networks and accumulates gradients over many timesteps to update the network. Moreover, it is a multi-threaded approach where each worker independently performs exploration and gradient updates with its own target network. This setup results in each actor being optimised independently with its own experiences and objective, introducing significant noise into the central learner that periodically unifies the gradients. Finally, the algorithm relies on collecting historical data: "We also accumulate gradients over multiple timesteps before they are applied" (Mnih) ct al. 2016). This undermines a key benefit of parallelised methods, which is avoiding the use of data collected under historic policies (see Section
PQN is a synchronous method where a single actor interacts with vectorised environments, and a single gradient computed at once using all the experiences. PQN can be seen as the synchronous version of that asynchronous Q- Q-Learning algorithm, which has never been implemented before. Note that moving from asynchronous to synchronous, removing the target networks, and avoiding multi-step gradient accumulation drastically changes the optimisation procedure and implementation, resulting in much simpler and more stable algorithm. To our knowledge, we are the first to unlock the potential of a parallelised deep Q-learning algorithm with minimal memory requirements and without target networks.
A.2 ANALYSIS OF TD
Most prior approaches analysing TD focus on linear function approximation. Tsitsiklis & Van Roy (1997) first proved convergence of linear, on-policy TD, arguing that the projected Bellman operator in this setting is contraction. Dalal et al. (2017) give the first finite time bounds for linear TD(0), under an i.i.d. data model similar to the one that we use here. Bhandari al. (2018) provide bounds for linear TD in both the i.i.d. and Markov chain setting. Srikant& & Ying (2019) approach the problem from the perspective of Ordinary Differential Equations (ODE) analysis, bounding the divergence of Lyapunov function from the limiting point of the ODE that arises from the TD update scheme. Analysis of pure TD in the general nonlinear and Markov chain sampling regime is lacking.
Two papers that are most closely related to our work are: (Fellows et al. 2023) and (uue al. 2023).
Yuue et al. 2023) analyses the effect of LayerNorm in TD, however there are several important differences. Firstly, the paper analyzes the neural tangent kernel (NTK) of the update, which only exists in the limit of infinite width networks and does not capture the nonlinear instability that we analyse. We make such assumption as this will never hold in practice. Instead, we use the analysis Fellows et al.] (202)) which predates (Yue et al., (023) and provides a more general framework for studying TD with finite width nonlinear networks. Moreover, |Fellows et al. (2023) provide key results on establishing stability of general TD using an eigenvalue analysis this is more general but
remarkably similar to Yue et al. (2023)' 's SEEM framework. We extend these results to Markov chain sampling with normalised regularisation.
Yue et al. (023) claim that LayerNorm alone can stabilise TD. Under our more general and applicable analysis, as our results show, LayerNorm without e regularisation cannot completely stabilise TD for all domains. This is because for stability, the Jacobian eigenvalues need to be strictly negative. As Lemma 2 shows, there may still be residual positive term that prevents this. Our empirical results in Barr''s 's counterexample confirm this, showing that the algorithm can only be stabilised using normalisation. Existing empirical research (Lyle al. 2023) also supports this.
18

---

Published as a conference paper at ICLR 2025
A.3 REGULARISATION IN RL
CrossQ is a recently developed off-po algorithm based on SAC that removes target networks and introduces BatchNorm into the critic (Bhatt et al. 2024). CrossQ demonstrates impressive performance when evaluated across a suite of MuloCo domain with high sample and computational efficiency, however no analysis is provided explaining its stability properties or what effect introducing BatchNorm has. To develop PQN, we performed rigorous analysis of LayerNorm in TD. Here is a complete list of the differences between CrossQ and PQN:
CrossQ is based on a soft-actor critic architecture for continuous action control. Its entropy- based actor objective optimises a stochastic policy, On the contrary, PQN consists of single, simple value network optimised with the standard Bellman Equations, which is used to learn a deterministic policy for discrete actions.
CrossQ is not parallelised, i.c., it interacts with single environment at time, while fundamental contribution of PQN is handling parallel environments for faster training on modern hardware. Parallelisation of Q-Learning algorithms is not trivial: one cannot simply interact with multiple environments while leaving the rest of the learning pipeline unchanged, this drastically modifies the ratio between interactions with the environments and the number of gradient updates. PQN approaches this problem by offering a sample-efficient implementation based normalisation, Q-Lambda, and miin-bbtchhs/mini-ppoco. updates.
CrossQ uses a large replay buffer containing data from historical policies to perform updates, while PQN obtains mini-batches directly from interactions with parallel environments under a single policy.
CrossQ not directly compatible with Q-Lambda and Recurrent Neural Networks because of the overhead introduced by the replay buffers: the use of old experiences in the update step makes computation of Q-Lambda unsafe, and the use of hidden states for the RNNs problematic. To include these methods in CrossQ one should add, e.g.. Retrace and Burn-In techniques. Conversely, the theoretical absence of replay buffer PQN allows us to use them out of the box. Note that these are crucial in many scenarios (see Q-Lambda ablation for Atari and MLP-RNN results in Craftax).
There is no theoretical analysis of normalisation in CrossQ and empirical evidence limited to six Mujoco continuous tasks. This is not sufficient to make any reasonable claims for its performance in general RL scenarios. We give theoretical basis for method and we compare it with baselines across 79 discrete-actio action tasks (2 Classic Control tasks, MinAtar games, 57 Atari games, Craftax, 9 Smax tasks, 5 Overcooked, and Hanabi). The limited evaluation provided for CrossQ is concerning, and the results in Mujoco might not reflect its true capabilities. Our results in Atari demonstrate it.
PQN is designed for complete GPU implementation and to be compatible with end-to-end compilation, which is a fundamental step for bringing Q-Learning into modern RL research (currently dominated by PPO). CrossQ does not tackle this problem, instead favouring a standard pipeline (which consists of interacting with one environment sampling from the replay buffer updating the network repeat) with the addition of normalisation. This pipeline is exactly the same as that used by DQN in our Atari experiments, where we show that PQN is between 50x and 100x faster and uses 26 times less memory.
The benefits of regularisation have also been reported in other areas of the RL literature. Lyle et al. (Lyle et al. 2023 2024) investigate plasticity loss in off-policy RL, phenomenon where neural networks lose their ability to fit a new target functions throughout training. They propose LayerNorm (yle et al. 2023) and LayerNorm with e regularisation (Lyle et al. (024)), as solution to this problem, and show improved performance on the Atari Learning Environment, but they also use other methods of stabilisation, such target networks, that we explicitly remove. In addition, they provide no formal analysis explaining stability.
A.4 MULTI-STEP Q-LEARNING
The concept of n-step returns in reinforcement learning extends the traditional one-step update to consider rewards over future timesteps. The n-step return for state-action pair (s,a) a) is defined as the cumulative reward over the next n steps plus the discounted value of the state reached after n steps. Several variations of n-step Q-learning have been proposed to enhance learning efficiency and
19

---

Published as a conference paper at ICLR 2025
stability. Peng & Williams (994) introduced variation known as Q(A), which integrates eligibility traces to account for multiple time steps while maintaining the off-policy nature of Q-learning. Replay buffers are difficult to combine with Q()), standard methods like DQN use single-step TD learning. The most relevant work that aimed to use ((A) with a replay buffer is Retrace (Munos al., 2016). More recent methods have tried to reconcile X-returss with the experience buffer Daley & Amato (2019) most notably in TD3 Kozuno et al. (2021).
A.5 AGENT DEEP Q LEARNING
Q-learning methods are a popular choice for multi-agent RL (MARL), especially the purely cooperative centralised training with decentralised execution (CTDE) setting (Foerster et al. 2018 Lowe et al. 2017). CTDE, global information made available at training time, but not at test time. Many of these methods develop approaches to combine individual utility functions into a joint estimate of the Q function: Son al. (209)) introduce the individual-ghe ciriuuul-loobl-maall (IGM) principle to describe when centralised Q function can be computed from individual utility functions in decentralised fashion; Value Decomposition Networks (VDN) (Sunchag et al., (0177) combines individual value estimates by summing them, and QMIX (Rashid et al. (202bb) learns hypernetwork with positive weights to ensure monotonicity. All these methods can be combined with PQN, which parallises the learning process.
IPPO (De Witt et al. 2020) and MAPPO Yu et al. 2022) use vectorised environments, adapting a single-agent method for use in multi-agent RL. These are both on-policy actor-critic based methods based on PPO.
B PROOFS AND DERIVATIONS
B. DERIVATION OF TD STABILITY RESULTS
We start by examining the TD Jacobian to separate the TD stability condition into two components. From the definition the TD Jacobian:
( (o)(o) = VoBenn10(0,s))
= Es-p, V [
1BgmP, [ooo(ct)V E.w [ollc
= >EErP,
- Band [oloce]V
+EowP, Q(()) (2)(1))
hence, write the TD Jacobian condition
J(pju= >Bo)p==BEnR V Vo Eanay (olo(t))Vol(
+ Bewr, + (Q0(1'))((0))))) Q. ( [
=Beup, V V (002
Ennay ( (v
+ Es~P [[r 22 Q0(x)) (x)
= ComPootcy ( d + CNontincar (
yielding the two stability components introduced in Section 3.1 Next, we investigate the effect that off-policy sampling has on Compoolcyy @+:- dd)):
ConPolicy (2/, d = P. [V' We now apply the Cauchy-Schware inequality to separate the expectations in the first term:
- Ex-ar ( (o)o
(10)
E EsPP. [v (oQo("")V o) < BENP, [o (ooolce")oo
v BEWR (o
BawPe [[0 (oTTo(((<))) ESW.P [1T (oQo(())))
[ (oTTo Exnat (o
Bawp
20

---

Published as a conference paper at ICLR 2025
Substituting into Eq. (10) yields:
Compolicy (Q d²) S VV BEWP, [ Vol((=²)))
Exnd= (
Evend [(v (v=Vooo(=)))
Now, as 7 E [0, 1). to prove that Compolicy (Q (s: d
< 0,, we require that Es-P, [(TTolo(t)))]
Bggnd [00 (oT yielding:
Compolicy (2 d S V Exnd' (oloo((()))
Baadd [Vovo))()))
= (7 B) (oTvoo((=))
B.2 THEBOREM ANALYSING TD
We now characterise the convergence of TT in our general setting, Our proof is structured as follows: we first bound the expected norm one timestep into the future in terms of the expected norm at the current timestep: Ea,-s: ||0x+1 111 I Constant E- | 11 + RRssidual, where Residual, is a residual term that accounts for the variance of the updates and sampling from the Markov chain. This is done by expanding |l 1²2 and following the algebra to Ineq. 11 of Theorem I To bound the residual term, we then invoke Lemma Bounding the variance contribution results naturally from our Lipschitz assumption. Bounding the Markov contribution follows from the definition of geometric ergodicity and our proof similar to BBaanari et al. (2018). Crucially, this bound implies lim,++o Residual, O. We then use the fundamental theorem of calculus to show that the TD stability criterion implics Constant < 1 for small enough a; (see Eq. (12). ). This demonstrates that the TD updates are contraction mapping with decaying residual term, allowing to verify convergence the remainder of the proof.
Theorem 1 (TD Stability). Let Assumptions updates in Eq. converge with:
7 and hold. the TD criterion holds then the TD
lim E | -0-13]
- =0
Proof. We use the notation [- to denote the expectation over (So....S;-11 and Es to denote the expectation over s; conditioned on S--1. Substituting for di+1 = Φs + a,,(dii {) into
|| + yields:
-s |10+41 - 0-|]] = -E,.- [ - a) --]]]
af s1)1 -B,s - - 0012= 20,0 si) (0:
- Φ²) (0:
-E-g
|10: 0²112- -2a,E - (6(0r, <i)l (0: 0²) + a a [1((01)))11]]
=E
|00 0²1²² 20 (B -s. (6(0)) s:) 5(6:) o(b:)) (Ør - x0)
+ af k - [10((r st)1121]
-E-g |0: 1-122 2a, (Ø: x*)
+ 2a; (Ex.1-s. 18(0,, s:)] - 5(0))) (Ø: - (bi-)))+ + - a [1)(11)s))11]]]
<B-g,
||o. - 0-12-- (0,) (0. - -0)]
+ 20
E. (s 18 st)] - ((0))) T (0:: -
(0:- Φ³)
to² Be.- [1r,, s))1 (11)
Non itd. term
Variance term
21

---

Published as a conference paper at ICLR 2025
where have isolated the contribution of variance and non-iidd. sampling in deriving the final line. We now bound the non-i.id. contribution total variation and variance term using Lemma
(6) -0y) o³) + 20; p' + or Cvar- -s,-s [lok+11 - -5-11 ST- [l1bk 0/1 20,0(0;) (0:
Note that for i.i.d. sampling, -s (6 s:)] = BR [6(0;, s:)] - ō((;) and so Markow = 0. Next, we re-write 8(bs) to contain factor of Φ0; 6² Define the line joining o to Φi as {(I)
Φ; 1(0; -²)) Under Assumption
2
we apply the fundamental theorem of calculus integrate
along this line, yielding:
8(0,) 5(()) 5(()),
8( {(0) 8(6 ((1)),
0,8(6 e(I)dlI,
Vag(ó = (()) xz )dl,
J( (()) x*),
J(d: -()=
where we have used the chain rule to derive the fourth line and introduced the notation J= Soz J(o= (ll Substituting yields:
Ea,-s [10241 - <591]]] SE=G. [10: +0112+20 2a;(0; oa) - Φい)
20, Markko Ovar.
Now, the TD criterion: a. J()v holds almost everywhere, follows that:
(
J(H - (())d()) -
=
= (6:- -0 6²) = (6: T²) T (J+JT) (Ø:: -0)) 5 -Amin 112
where Amin > 0 is the smallest (in magnitude) eigenvalue of - + JT). Substituting yields:
E [10111- 0011 < EE. [10. 0-12] 2aidmii)) + 22, 0' + a Ovar. (12)
Re-arranging yields:
2 (t, [110)- -00112]
< E E_ss.
||0. - -6-1|] - E E.,. -
[10etz [001]]-011]] 22, Markou + af Cvar..
22

---

Published as a conference paper at ICLR 2025
Summing over i up timestep t and using the telescoping property of the series yields:
|10b. 0011²)
2Amin
1=0
I B-
10000 (-1²²] - Exa-- [10et1 - 0-11²] + 20 Markuv
Σ
asp' + Cvar
Σ
1=0
i=0
< E -s-s
1000 0-1]²] + Marko
Σ
aup' + Vaa
Σ
10
1=0
a4 B-s, Si |10; 0712]]
Vf =0 Cts
Am0
1
E
1100 - x2-12
Ei aip'
+ Ovar Ei=o of
+ 2C Markow
(13)
2Amin
21'0000 0y1
21=0 Uii
~P== Op
where the penultimate bound follows from E [10441 +11 the limit -> oc, we observe that by the Cauchy- -Shwwar inequality:
0. In preparation for taking
aap' Σ Jalll's S
Σ atp2i
Now, from Assumption lim Eizo as < co, hence:
lim
app'
lim
af
lim
2 0(1)
k=0
1=0
1=0
As 3o Ei Og co, this implies:
0 aip" 0.
lim
= ai
We are now ready to take limits of Inq.
13 yielding:
lim
E |10: 001]]] 0.
(14)
Σ =0 ay
Eq. [4 proves our desired result:
lim R-g, [10b: - -0-13]]= = =0
To see why, assume this does not hold, that is lim B-s, [10bs - xz1
# 0. This implies there
exists some infinite length sub-sequence S such that for all E
E- |10e x-] 0,
hence, as all quantities are positive:
a:
E-g [1 1100-0012
Oi E_g, [|0: 0-]1]] > 0, Ev=0 ag
2 lim
Er ay
+
iES
which is contradiction.
Lemma 1. Let Assumption and p (0,1) such that:
2 hold. Then there exist constants: 0 < Matkoo < <00, 0 < Cvar < 00
E-c; (Eal-5. (6(or, st) -6())) (oi: 5+)
CMartonp Es,-s, [10((2, [108(01,5)]]P]] < Cvar.
23

---

Published as a conference paper at ICLR 2025
Proof. For both results, use the fact that, because Ob is compact and X' is bounded, rewards bounded and d(Ø, <) is Lipschitz under Assumption 2 8 <) is bounded almost everywhere. To prove the first bound, denote the marginal probability distribution of the i-th timestep element in the Markov chain &i as P with density:
p²(s.) = /((-srsi)d(-s))
Under this notation we write:
E-s,
(Ba.1-
[ô(0s, st)] 8(0i)) (Ø, 00)
E Essisi
(o(d), (t) - BR 16(0;, <))) T (Ø: -o0-))))
=E E cc,e
si) (Ø: 00) - ER 16(0:: </1 (Ø: - -5-)
= -sss
[8(0 si) (Ø: ((0x-())-- - Bejxp, [8(0:.5]) 5t) (Ø: (0:-
[ [E-w)p)s))) [6(0;, si) (Ø: - [p)- BeEP [B-s)P [8(dr, si) (0: -
o²]]]
(15)
where (<)) is the backwards conditional distribution in the Markov chain with density:
(((s)())) si (3((s)
Introducing the notation:
g(s:) E --a-Pi(s) [8(0), st) (di- 6²)]
write Eq. 15
E E-s,
se
(Eail -a (o(0r, - (Ø: (Øi- -0'
- [g(s)]] BaN [g(s;)],
Beg [BarpP(ss)) [g(s;)] ERI-P, [g(s:)]]
g((a)
g(<x)
= =Eso 9max
(16)
Imax
9max
where Jmax = maxx(g(s)) < oo almost everywhere, which follows from the fact that d(0, s) is bounded almost everywhere, implying g(s) is also bounded almost everywhere. Now, as 9(-)
Aum
X' TR X > [-1, 1}. we can bound Eq. (66) in total variation using Roberts & Rosenthal Proposiioonnno 3b]:
g((=)
g(si)
)}
Eep
fmax P(s)))()))
5
Jmnax
Jmnx
g(5i)
(Ss))
Eso
Jmax
E Be
13 P.
Fmax
Imax
g((i)
g((i)
2mmxx Eeo
E
Eei P.
2
Jmnax
Fmux
1
<20 Beo
sup
ERIPPita) [[(si)] ER [[ssi]]]
2
f-XXXXX-1-11
-2nmaxx Egp
(V((P(
(17)
where (so) is the total variational distance between the marginal distribution P (so) (conditioned on initial observations) and the steady state distribution P.- Now, the Markov chain is geometricaly ergodic, by definition there exists some function M (So) and constant p E [0.1) 1) such
that:
TV(PP((>))).)) M(so)p',
24

---

Published as a conference paper at ICLR 2025
almost surely (see Roberts & Rosenthal our desired result:
(Section 3.4]), hence substituting into Eq.
17)
yields
E
(Bei-s. (8(0s, s:)] 5()))) (Ø: -
S graux Een [TV(P'((o)])..]
2masx Beo [M(s))
-2mmxx Beo
[M(ss)] p²
=OMarkopp'
where CMarkov 29max Ex [M() < oc. Our second bound follows from the fact that 5(Ø, s) is bounded almost everywhere. This implies there exists some Cvar such that ((((),))ll I Cva almost everywhere, hence:
B [110(0t, st)11 I Ovar
B.3 THEOREM STABILISING TD WITH LAYERNORM AND l REGULARISATION
Notation:
For all proofs in this section, we introduce the following simplifying notations:
fM(2) =ree MMx
1 f(()) (z)
LayerNorm (z))
Vk
f(f(z)
where i [ (x) and (z) the element-wise empirical mean and standard deviation of the output f(z):
=)) = - off(x)) =
Finally, we write M terms of row vectors:
mg
m
mk
and split the test vector into the corresponding & sub-vectors:
Ju'
Umng Umy
my
where U.p is a vector with the same dimension as the final weight vector w and each um; E R has the same dimension as We will make use of the following three key properties of LayerNorm: Proposition 1. Let f X + R be a vector- valued function such that all components fç are bounded, then:
|aaeerNrrm [f())]] <
0, (aorrNomm([(())) 0 -- 1(i=)) j) )
0r,0, LayerNorm,[[(a)) 0 - (1(t= j) 1(t 10j 8) ++
25

---

Published as a conference paper at ICLR 2025
Proof. Our first result follows directly from the definition of LayerNorm: Ilf(z) (
[|LayerNomm($(s]]]] Vk o[f((z)
1= (f((z) (()(()))
([f((z)
Ee (fi(z) LI (x))² +c
o[f((x)
olf((t) a[ʃ(())
1,
as required. For our second result, we take partial derivatives with respect the ith input channel to the LayerNorm:
L(i -
((x)-Afflee
o1)(2²)2 o2 )
0y LayerNorm(((xx)
Vk
(())(z)
1
() Vk LayerNorm ((x))
0g o1((())
([f((z)
o[f((z)
Finding the derivative of the empirical variance yields:
(z = 1
Σ (J((z) (0)))
K E=
Σ -10))))1()))+++++++) +6 0j:
E - -100))
2
i=0
(1(==1) 1)
- (1)(
ko)fl(z)
1=0
K-1
Σ f(x) H Σ
k-1
E(i(o) - ALI (z))
k-
f((x) (x))
Σ
M(x) (1))
ko(f(())
K
1=0
-M])()
S1xx) - 1 [ (x:
= Vk LayerNorm([f(a)]]
hence:
0y, LayerNorm"([[x))
[) LageNomm///c////yeeemmm///]]]]))
(18)
Vkolfl(x)
= - ( VR
1(i (ii==) ; )
where we use the fact that LayerNorm [x)) = vk to derive the final line. To prove our third result, we start with the first order partial derivative using Eq. (8)
Oj. LayerNorm(((+))] Vkolf(())
((1 j)
LayerNorm [[ar]LayerrNomm ((x)))
K
26

---

Published as a conference paper at ICLR 2025
Taking partial derivatives with respect to f. yields:
0z,0,, Sr LayerNormm (x))]
[[(1=)) [ho]f((x)²
0,,0(1((z)
1
1:
k 3. dz [a LaagellyyyyyrN + LaayeNoomm/(fc)j)joaaaaeoott
0lf((z)
1(t= j) 1)) + + ( (1(t=s) 5) x) 1)) 0 k (10 s) + ))
0 k
(((t=)) j) 1(t 5) + 1(j = 5) + )))
=0 k=
as required.
We are now ready to prove our main result. Most of the work is done by proving Lemma 2 once the bounds in Lemma have been established, the result follows by subtracting the regularisation term from the off policy and nonlinear components of the TD stability condition. We split the proof of Lemmaa into two parts. Firstly, we bound the off-policy contribution by splitting it further into components that affect the final layer weights and the other matrix weights. By doing so, we find a residual term remains that is only affected by the final layer weights (Lemma 3). Secondly, we bound the non-linear contribution in Lemma by isolating the second order derivative of the function approximator. What remains is to show this term decays as 1/VR, which we prove in Lemma Our proof of Lemma ii is similar to Liu et al. (2020).
Theorem 2. Let Assumption apply. Using the LayerNorm regularised TD update (
(db, s) in Eq. ( there exists some finite k' such that the TD stability criterion holds for all k > K'
Proof. From the definition of the expected regularised TD error vector:
reg (0) = EgpP,
[(r + (0% - (x)) V (o))(a))
(1((24 L )
+ (n 1) [veccan))
17
0
v T V (00mz(0)0 E.WP. [(r + Q2))2)) 2 T [z))(=)
+ EenPe [oT
- va0% (z)) v Tv)
(2LPOe)
2
||:,o112 (n 1)|
= ConPoticy (2), d²)) + CNoontinear (Q.))
7 Topaa
2
|| - (n - -1][[u-m 1|.
2
Applying Lemma a taking the limit & + yields:
lim = 10000
2 (1 |uml (1 || < 0,
almost everywhere, which follows from the fact 1) > 1, hence, by the definition of the limit, there
must exist some finite k' such that for all & > k/:
VV gh (o)u < 0,
almost everywhere, as required.
Let Assumption apply. Let vw be the first k components of the test vector [[o UM associated with final layer parameters w. and UM be the remaining components, associated with the matrix M parameters. Using the LayerNorm Q-function defined in Eqq 45):
Lemma 2.
Off-Policy Bound:
ConPolicy (2:s d < w| "/mm/2| + O (1|=m11//)
Nonlinear Bound:
Crvmntinea (Qt)) O (lol)//z))
almost surely for any test vector and any state-action transition pair x; x! E X.
27

---

Published as a conference paper at ICLR 2025
Proof. By definition of the off off-policy and nonlinear contribution terms:
Convolicy (2's d²)) > ( V (0 Exndy ( (oO(())))
Coanlimear (%) E [(r 2²((2 -2())))'' v (z))
Applying Lemma 3 and Lemma 4 yields:
ComPolicy Q dta)
=BuNP, T VoQg("") ( (o (oTV
1 (1cAs11)) VoQ
(1/reallital)
<BEuPs
+0
2
k
y I Uwll
lluael(2) )
+0
k
CNollinsar (9%) = BeNp [(r +
+0 10% - 2+(x)) (1)))
<RowPs (1 10% (
| 2
as required.
Lemma 3 (Mitigating Off- Off-policy Instability). Under Assumption 2 using the LayerNorm critic in
Eq. (5)
(1Lrounlee ( ) + [lemmll)
V VEO 8 (- ( Vo)
(19)
k
almost surely for any lest vector and any stale-action transition pair x, x' E X.
Proof. Using the notation introduced at the start of Appendix B.3 we start by splitting the left hand
side of Eq. (19) into two terms, determining the stability of the final layer weights and one for the matrix vectors:
-- (o Vo To V (((=)) ti - (v (
(nu m.,
Oz V 22(2) Un. "n, Vm, (x)
(20)
We first focus on the term determining stability of the final layer weights. Taking derivatives of the critic with respect the final layer weights w yields:
V an 2s -opa LayerNorm" & [far(x')),
hence:
V (x('))
|| Poss LayerNorm" [f
| o LayerNorm [f Pos (0)l,,
S LayerNorm*
<
Oll. [[M (*')]l
p LayerNorm
< Loost
(21)
where we have used the fact that p.aa(-) is Looat -ioo--Lipschtzz to derive the third line and ap- plied [|LayeNNorm* [fM(x']]] < from Proposition to derive the final line. We then bound
u V V ('' Q (z) Une as:
w0 V.
ow <
(5))) cal.
< Lpoal || V/ VZ ( vwll
28

---

Published as a conference paper at ICLR 2025
Defining (T) uwl
T yields:
vo vw - (w Vn((a))) s < /lllw//l || Qa(a) Bno - ( Unal
LPost Dew || E,
I max (7 Puss 1/ c2)
Our desired result follows from the fact that the function y yT /ooll x² maximised at e y w= hence:
Yu Ve V vw - (1 V QZ - poal Murl
(7 P (lesss//wrr] 2
2
2
y L /ewll
Substituting into Eq. 20 yields:
Vol% (0 (o( - ?IPoaal (TIraalluall)
Σ (uo vm, (=') (z) Um. um m, ( (x() 2m0
(22)
We now bound the remaining terms (i.e. those that characterise stability of the matrix row vectors) by taking derivatives of the critic with respect to each matrix row vector: m,
V m, 2 (x) = V w dPos o LayerNorm* (x)),
wj mm, Posa (LayerNorm [f (x))).
Applying the chain rule to find an expression for the derivative:
V m: (5(z)
oy (LayerNorm [far()))) Ln,,eNNoommm [fM(x)],
(LayerNNo) ( [fM[2)] opr (mTTm)))) x)x,
where the and Pou denote the derivatives of the activation functions, which are bounded almost surely from the Lipschitz assumption, hence:
tre (m. x), oost (LayerNorm) (x)) O(1)
Using this, we bound
V m. (x) T Um.
as:
V m: (x) Um. [mmm
( [f^r uT
j=0
Now, as each element (x) Lipschitz and defined over bounded set of parameters m, and inputs X' it follows that (M,(()) must be bounded function. We can thus apply the derivative bound yielding:
to 0, Layerromm [f (x)) from Proposition
1(i 5)
V m. 2x(2) Umall
K
Wi
Vm 2,
Vk
1=
L(i = j) - 1
Vk
0
Uyn 2.,
T
Vk
29

---

Published as a conference paper at ICLR 2025
where have used the fact that w, = (1) in deriving the second line. Finally, use this result to bound each V m, Q (2") Um, and V m. Q7 Um, term in Eq. 22
(1Leoaalewull 2 (
y
(u Qx)))))
2
? Umm M. 2x(x0)) V.. Vm. Umll + Jum Vm,
y LPoss Mevll
カ-1
7 | 2'| I + Iun m1²)
+0
2
y Poos pwoll
+0
em 11? (2112"|11az1| + ||xr11?)
2
Now, it follows from the definition of the euclidean norm:
|ommlll 11 = ||w 1|
and by the definition of the state-action space of the MDP in Section 2.1
| ||''|| O(1),
hence:
(V < (1Invallingg ([Trmalltual)) + (1lrrel
[Iwar]] 11?
YU
2
as required.
Lemma 4 (Mitigating Nonlinear Instability). Under Assumption defined in Eq. 5
2
using the LayerNorm Q-uuction
||011
(==) u (2Q)())) o
VT
almost surely for any test vector and any state-action transition pair x, xf E X.
Proof. We start by bounding the TD error, second order derivative and test vector separately:
(r (a') Qz())) o' v (z)))) s ((r + 70) (z)) (V [o11,
By the definition of the LayerNorm Q Q-function:
(x) S ||l||| Poea o LayerNorm* [f)](=
< ||w||| Lpost
where the final line follows from Eq. 21 As the reward is bounded by definition and |/||| is bounded
under Assumption 2 we can bound the TD error vector as:
1(r + 10 (=(r))
hence:
(r + (11'')) Oz(x)) V20 | (x) ||:1
Our result follows immediately by using Lemma 5 to bound the second order derivative:
||
( + - ( o
k
30

---

Published as a conference paper at ICLR 2025
Lemma 5. Let Assumption hold. (x)]
= O (#t.
Proof. Using the notation introduced at the start of Appendix B.3 with respect to the j-t matrix element as: , LayerNorm [x)( Using the chain rule, find the partial derivatives with respect to each element as:
denote the partial derivative
mm,, LayerNorm [fM(x)]
0j LayerNormi [far Omn, Six Ög LayerNorm [fas (2)] o (m 2))2g,
where Pre denotes the derivatives of the activation function, which is bounded almost surely from the Lipschitz assumption, hence applying Proposition I follows:
mm LayerNormf [far (x)] = 0 100.LayeNNmm [x))
= 0 k (10 (1(1=))+ +1/²) ))
1)
We find similar result for the second order derivative:
mm,, ama, LayerNorm [JM( 0 LayenNomf [fM((]]] ofe (m, w)rrore (i=00
+ @g oy LayerNorm [f)r Isr
Og LayerronN [f ohe (mf x) 2) s)
+ 0g 0, J.y.eaayrNNomm [x)r of (m x) x)x+,
where ofe denotes the second order derivative, which is bounded by assumption, hence:
Om, Sm.., LayerNorm [far(x)]
=0 Lay.rryerN [f)r) 1(i = s) (0,, 0, LayeerNom [fa))
= 1(1 = s)k= (101- = i) + : O ( (10=-)) + 1(i (i== + 101 = 101=
+ ))
We now use these results find the partial derivatives of the LayerNorm Q-function. Starting with Duc, Omn. (z):
Oy, Pm,, 2t (x) 0man
wrOmi, (aaaeooo
= 0m.
wiohon (LayerNorm([ (x)] (x)),
k-1
w (A=2) - 110=))+0(#))
0
1=0
) 0 (R-$)
([u= 0
(23)
31

---

Published as a conference paper at ICLR 2025
and now for mm,, Omrr (z)):
mm.,Om, (2)2) Dm...
Σ wi
Layerroo""[
Pon (f (aan Layeroorff [far (z))),
1(i (1((i=s))= (((i=s)k-+ s)h 1(1 +)]
11 0
[111= i) 1( 8) + 1(1= 5) + )
k
(1) (k) (1(==)) oo )1)) [(1 (I(I= 1) o 1k
+0
(1(1 f) #1 0 ( +) 1 s) (1)
=0
Σ Olm (1) [[1 (1(1= 5) +0 +0
(1) (1)) [11 1) (1(==))+ +0 )1))
0 (1-1)
1(i (()==)) 8) + +
+
k
1(i = 8) +
12
1
= 0 (k )
() + o
k ()
(24)
where oaac (z) denotes the second order derivative and we have used the fact that oeaa (-) and ooor (-) are bounded by assumption.
Now, from the definition of the Matrix 2-norm:
[=00(=)1== = sup V20g
for any test vector. As the Q-function is linear in w, we can ignore second order derivatives with respect to elements of w as their value is zero. The matrix norm can then be written in terms of the partial derivatives of (x) as:
1 sup
I
ΣΣΣ Umi., Om, am,, (1)
TT v
ΣΣΣΣ i=0
Um: 0m,, 0m. 2%s (3) (zr)em).))
We now bound the partial derivatives using:
Du,, am., 0x(x)= = 0 0 1(u ([u=1)+t 10
)
(K)
Dm,, 0m,, Q5(1)) 0 | (x=
1(i= 8) 0
1
1
32

---

Published as a conference paper at ICLR 2025
from Eq. 23 and Eq.
24 yielding:
R- d-1
[L(u (1(==i++(#))
k 3
Σ
sup
Umi,z Vwn
u v
1=
1 )
[(i= 5) +0
1=
1= == 1=0
11k
Σ
ΣΣ
([(==)) i) + 0 #
sup
Uwa
Umi.i
u=0
==
1-Id=1
h-
dd
Uma.t (1(i=))+0) 9) +o
Umi
i=0 1=0
k-1d-1
0
sup TT
1
Σ
Una 0(1+
+
Um O11)
am0
x= 0
R-1d-1
=0
(K-2
1
sup
v
Wn
+
m,.
4=0
1= 1=
Using the definition v -T==
1 Wi
+ Σ/=
Z==0 h
mi yields our desired result:
120
=0 -0(K5 (
sup (TTT).
=0 ( (1),
0F (b-+)
33

---

Published as a conference paper at ICLR 2025
B.4 DERIVATION OF RECURSIVE X-RETURNS.
The original proof can be found in Daley & Amato (0119, Appendix D), which we repeat and adapt here for convenience. We wish to write R as a function of R2,1- First, note the general recursive relationship between n-step returns:
R &
(n-1) = Tk + + R
(25)
k+1
Let N T - t. Starting with the definition of the A-return,
N
R² (1 )) Σ
R((
+ -N 11, (N)
N
= (1 R) (1)
+ (1- X)
Σ
1 (1)
+ +
n=2
N-1
(1 R) (1) +
(1 A)
Σ
1 --1
rtt r r R2(47 + 1 (re 7
( 7 "
n=2
N-1
(1 1uRe Art 7 (1 (1-X) A)
Σ
Xn R + 22 (N
N
= (1 -)nR + \r + 77
(1 (1- 2)
Σ
X m1 + X N R (N-1)
n'=1
(1 1)T( \r; + +711/21
(1) -AR + ^r; + 71lli++1
rt + 7 max Q(s', d') ~rre + 7 max Q(s', d')) + +Ar, 7/11/11
+ max Q(s', a') + + 7Amax Q(s's
r: + 7 AR + (1 A) max a()),
a'
where used the recursive relationship for (n) in Equation 25 and the substitution (1) rs + max,' Q(s',a') Finally, we note that in our implementation, we replace the true value function with function approximator.
C EXPERIMENTAL SETUP
All experimental results are shown as mean of 10 seeds, except in Atari Learning Environment (ALE) where we followed common practice of reporting 3 seeds. They were performed on single NVIDIA A40 by jit-compiling the entire pipeline with Jax in the GPU, except for the Atari experiments where the environments run on an AMD 7513 32-Core Processor. Hyperparameters for all experiments can be found in Appendix D We used the algorithm proposed in Algorithm [ All experiments used Rectified Adam optimiser Liu et al. (2019). We didn't 't find any improvements in scores by using RAdam instead of Adam, but found it more robust in respect to the epsilon parameter, simplifying the tuning of the optimiser.
Baird's 's Counterexample For these experiments, we use the code provided as solutions to the problems of (Sutton& & Barto 2018b) We use single-layer neural network with hidden size of 16 neurons, with normalisation between the hidden layer and the output layer. To not include additional parameters and completely adhere theory, we don't learn affine tranformation parameters in these experiments, which rescale the normalised output by a factor and add a bias B. However, in more complex experiments we do learn these parameters.
httpp:: httpa////e......oooooooon//aaa//
1earei i ng an i roductiion
tree/main
34

---

Published as a conference paper at ICLR 2025
DeepSea For these experiments, we utilised simplified version of Bootstrapped-DO" (Osband et al. 2016), featuring an ensemble of 20 randomly initialised policies, each represented by two- layered MLP with middle-layer normalisation. We did not employ target networks and updated all policies in parallel by sampling from shared replay buffer. We adhered to the same parameters for Bootstrapped-DO2 as presented in Osband et al. (2019).
MinAtar We used the vectorised version of MinAtar (Young & Tian 2019) present in Gymnax and tested PQN against PPO in the 4 available tasks: Asterix, Spacelnvaders, Freeway and Breakout. PQN and PPO use both a Convolutional Network with 16 filters with 3-sized kernel (same as reported in the original MinAtar paper) followed by 128-sized feed-forward layer. Results in MinAtar are reported in Fig. 9 Hyperparameters were tuned for both PQN and PPO.
Atari We use the vectorised version of ALE provided by Enypool for a preliminary evaluation of method. Given that our main baseline is the CleanRL (Huang al. (022b) implementation of PPO (which also uses Enypool and Jax), we used its environment and neural network configuration. This configuration is also used in the results reported in the original Rainbow paper, allowing to obtain additional baseline scores from there. Aitchison et al. (Aitchison et al. 2023) recently found that the scores obtained by algorithms in of the Atari games have a high correlation with the scores obtained in the entire suite, and that 10 games can predict the final score with an error lower than 10%. This due to the high level of correlation between many of the Atari games. The results we present for PQN are obtained by rolling out a greedy-policy in 8 separate parallel environments during training, which more effective than stopping training to evaluate on entire episodes, since in Atari they can last hundreds of thousands of frames. We did not compare with distributed methods like Ape-X and R2D2 because they use an enormous time-budget (5 days of training per game) and frames (almost 40 Bilions), which are outside our computational budget. We comment that these methods typically ignore concerns of sample efficiency. For example Ape-X (Horgan et al., 2018) takes more than 100M frames to solve Pong, the easiest game of the ALE, which can be solved in few million steps by traditional methods and PQN.
Craftax We follow the same implementation details indicated in the original Craftax paper Matthews al. (2024a). Our RNN implementation is the same as the MLP one, with an addtional LSTM Layer before the last layer.
Hanabi We used the Jax implementation of environments present in JaxMARL. Our model doesn't 't use RNNs this task. From all the elements present in the R2D2-VDD presented in Hu et al. (2021), only used the duelling architecture Wang et al. (2166). Presented results of PQN are average across 100k test games.
Smax We used the same RNN architecture of QMix present in JaxMARL, with the only difference that we don't use a replay buffer, with added normalisation and Q()). We evaluated with all the standard SMAX maps excluding the ones relative to more than 20 agents, because they could not be run with traditional QMix due memory limitations.
Overcooked We used the same CNN architecture of VDN present in JaxMARL, with the only difference that we don't 't use replay buffer, with added normalisation and (()).
D FURTHER RESULTS
1018
Truc
Truc
True
1046
Leaerfarm
Loos (log)
Salvec
Layc
Lepobtacc
10
BackNers
0
5000
10000
10000
10000
Episodes
Episodes
Episodes
Episodes
(a) Baird's C.example
(b) DeepSea, depth 20
(c) DeepSea, depth 30
(d) DeepSea, depth
Figure 7: Results from theoretical analysis in Baird's Counterexample and DeepSea.
35

---

Published as a conference paper at ICLR 2025
900
-10
400
100
300
-200
200
100
400
400
-500
-500
100
200
250000
100200
50
100
150
250
250000
500000
Time (sccondss
Timestops
Time (Seconds)
Frames
(a) CartPole: Training Time
(b) CartPole: 10 Seeds
(c) Acrobot: Training Time
(d) Acrobot: 10 Sceds
Figure 8: Results in classic control tasks. The goal of this comparison is to show the time boost of PQN relative a traditional DQN agent running single environment in the cpu. PQN is compiled run entirely on gpu. achieving a 10x speed-up compared to the standard DQN pipeline.
Asterix
Spacelnvaders
Freeway
Breakout
75
Epusode Keturns
60
40
100
40
50
20
20
25
01
0.0
0.0
0.0
1.0
1.0
Timestop
Timestop
Timestop
Timessop
PPO
PQN
Figure 9: Results in MinAtar
Max Normalised 1QM
1.00
Max Normalised IQM
1.00
0.75
0.75
0.50
0.50
128
256
0.25
0.25
0.00
0.00
0.0
0.5
1.0
0
2000
4000
Timesteps
1e7
A Average Time (s)
(a) IQM sample effincency on MinAtar tasks varying the number of parallel environments.
(b) IQM time effincency on MinAtar tasks varying the number of parallel environments.
learn with Figure 10: Ablation study varying the number of parallel enviromments in Minatar. PQN
small number environments but clearly benefits from collecting more experiences in parallel. PQN is also significantly more time-efficient when more environments are used in parallel (time is considered for running 10 seeds in parallel). For a fair comparison, we adjusted the number of minibatches and epochs so that PQN performs the same number of gradient steps with the same batch size (or, where not possible, with adjusted learning rate) every number parallel environments considered.
36

---

Published as a conference paper at ICLR 2025
20
20
10
10
10
Retmm
Betmms
-10
-10
-20
-20
-20
4
Time (minutes)
Time (minutes)
Frames
(a) Atari-Pong: PQN training
(b) Atari-Pong: Time Comparison
(c) Atari-Pong: Performances
Figure 11: Comparison between training Q-Learning agent Atari-Pong with PQN and the CleanRI. implementation of DQN. PQN can solve the game by reaching a score of 20 in less than 4 minutes, while DQN requires almost 6 hours. As shown in the plot on the right, this doesn' It result in loss of sample efficiency, as traditional distributed systems like Ape-X need more than 100 million frames solve this simple game.
Table 3: Scores in ALE.
Method (Frames)
Time (hours)
Gradient Steps
Atari-10
Atari-57 Median
Atari-57 Mean
Atari-57
Score
>uman
PPO (200M)
2.5
780k
165
PQN (200M)
780k
191
PQN (400M)
2
1.4M
243
245
1440
40
Rainbow (200M)
100
12.5M
239
230
1461
43
2.5
PON
10M
1.225
0
4
8
12
Hours
Figure 12: IOM computed over 3 seeds when training PQN with the ALE configuration proposed by Dopamine Castro al. (2018). This configuration incorporates sticky actions and doesn't the done flag when agent loses life. With this setup, PQN can outperform Rainbow, (almost hours), corresponding to 800 million frames, indicating a loss of sample efficiency. Sample efficiency might be recovered in this configuration by using larger network or tuning the hyperparameters, but we leave this future work. PQN is still much faster to train than Dopamine agent, which requires multiple days depending on hardware.
requires significantly more compute time
37

---

Published as a conference paper at ICLR 2025
% of Improvement over Rainbow
20
15
5
Skarz-o
Mosrzin Meerziasttoggggg Bivedgo
KingFoMeeeest
Sunoard S-
G Gipheedd
Rugg -5
Cney Cimberas
Miatlend
Breakoatis
Kell i
Gutiped-s5
Namch mecchndddnn thiibmmm-ss
Winsst/WWeee
Deloake
Cheppe DeperGnnater Don
Vanure
Artmntio
Bosth
Game
Figure 13:
Improvement of PQN over Rainbow, Results refer PQN trained for 400M frames, i.c. hours of
GPU time.
Amidar-v5
Bowling-v5
Frostbite-v5
KungFuMaster-v5
Riverruid-v5
2000
S0
5000
40000
20000
Epiaaoda
1000
10000
0
Timestop
Timestop
Timestop
Timestop
Timestop Qbert-v5
BattleZone-v5
DoubleDunk-vS
ThinTTG-Gamm
Phoenix-v5
Eipoode Rotuens
40000
100000
20000
10000
20000
Timestep
Timestop
lnk
Timestep
Timestep
Timestop 16
PQN
CmecQ
PQN (BatchNorm)
PPO
Figure 14: Atari Results
60
Bchaviour Policy
Atari-10 10 Score
Learned Policy
30
0
2 Frames 1e8
Figure 15: PQN learns policy from almost random policy. To further test PQN's off-policiness, conducted an experiment on Atari10 games using a highly random policy for collecting data, gradually shifting from 100% random to 70% random during training. As expected, the resulting policy was less effective compared to one with more exploitation. However, the key finding is that PQN can still learn a policy even when off policiiiss is extremely high i.c., when data is collected almost randomly from the environment, without following the learning policy.
38

---

Published as a conference paper at ICLR 2025
15
15
16
Returns (% Max)
Returns (% of Max)
Returns (% of Max)
10
12
10
8
5
PQN RNN PPO-RNN
PQN PQN+buffer
PPO
0.0
0.5
1.0
0.0
0.5
1.0
0
18
36
Timesteps
1c9
Timesteps
le9
Time (Hours)
(a) Craftax with MLP networks
(b) Craftax with RNN networks
(c) Craftax with MLP and Buffer
Figure Left: comparison between PPO PQN in Craftax. Center: comparison with RNN versions of the two algorithms. Right: time to learn for 1c9 timesteps keeping a replay buffer GPU.
2s3z
3s_vs_5z 5z
3s5z $s5z_vs_3aes vs_3s6z
1.0
1.0
0.8
0.8
0.6
0.6
0.6
Win
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
0.00
0.25
0.50
0.75
0.00
0.25
0.50
0.75
1,00
0.00
0.25
0.50
0.75
Timestep
10?
Timestep
ud?
Timestep
5m_vs uin_v____ vs__v__f vs_6m
3s5z
6h_ th_vs__ 8z
1.0
1.0
0.8
Win Rate
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Timestep
10?
Timestep
10?
Timestep
le?
10m_vs. Lim_vs_lin 11
smacv2 units
smacv2_10_uus units
0.8
0.8
0.6
Win Rate
0.6
0.4
0.2
0.2
0.24
0.0
0.0
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Timestep
10?
Timestep
le?
Timestep
tet
IPPO
MAPPO
IQL
QMIX
VDN
PQN
Figure 17: Results in Smax
39

---

Published as a conference paper at ICLR 2025
350
SMAX QMIX Butfer
Memory Usage (GB)
NVIDIA H100 Memory
175
75
150
Number of Units
Figure 18: The buffer size scales quadratically in respect to the number of agents in SMAX.
Cramped Room
Asymm Advantages
Coord Ring
Forced Coord
Counter Circuit
300
Epasdds Rehuras
300
400
200
200
100
200
100
100
0
0
0
5
5
Timestep
Timestep
Timestep
Timestep
Timestap
IQL
PQN
Figure 19: Results in Overcooked
E HYPERPARAMETERS
Table 4: Craftax RNN Hyperparameters
Parameter
Value
NUM BNVV
1024
NUM STE_STEPS
128
EPS START
1.0
EPS FINISH
0.005
EPS DECAY
0.1
NUM MINIBATCHES
NUM LUM_EPOCHS
NORM INPUT
True
NORM_TYPE TYPE
"batch_norm"
HIDDEN SIZE
512
NUM LAYERS
NUM_RNN_ LOIIRNNNNNERRR
ADD_LAST, ACTTTONTTATTON
True
LR
0,0003
MAX
0.5
LR LINEAR_DECA.
True
REW SCALE
1.0
GAMMA
0.99
LAMBDA
0.5
40

---

Published as a conference paper at ICLR 2025
Table 5: Atari Hyperparameters
Parameter
Value
NUM ENVs
128
NUM STEPS
32
EPS _SSRT
1.0
EPS [IS_FINISH
0.001
0.1
NUM EPOCHS
NUM MINIBATCHES
32
NORM INPUT
False
HORM_TYPE
"layer_norm" norm"
LR
0.00025
MAX GRAD_NORY
10
LR LELEANAARDEER
False
GAMMA
0.99
LAMBDA
0.65
Table 6: SMAX Hyperparameters
Parameter
Value
NUM ENVS
128
MEMORY WINDOW
NUM STEPS
128
HIDDEN SIZE
512
NUM NUM_LAYER LAYERS
NORM INPUT
True
NORM_TYPE TYPE
"batch_normi porc__
EPS START
1.0
EPS_ FINISH
0.01
EPS DECAY
0.1
MAX GRAD NORM
JUM_IINIBATCHHS
16
NUM_EPOCHS
LR
0.00025
LR L
True
GAMMA
0.99
LAMBDA
0.85
41

---

Published as a conference paper at ICLR 2025
Table 7: Overcooked Hyperparameters
Parameter
Value
LEM_ENVs
64
NUM WUM_STPPS
16
HIDDEN SIZE
512
NUM LAYERS
NORM INPUT
False
NORM TYPE
"layer "layer_norm" "erer_norm"
EPS START
1.0
EPS_ FINISH
0.2
EPS SES_DECAY
0.2
MAX GRAD NORM
NUM MINIBATCHES
16
NUM_ _MMCEPSCHS
LR
0.000075
LR LI_EAAAR__D DECAY
True
GAMMA
0.99
LAMBDA
0.5
Table 8: Hanabi Hyperparameters
Parameter
Value
NUM ENVS
1024
NUM_STEPS STEPS
1
TOTAL TIMESTEPS
le10
HIDDEN_SIZI
512
N LAYERS
3
NORM TYPE
layer_norm norm
DUELING
True
EPS STARR
0.01
DIS_IINISH
0.001
EPS DECAY
0.1
MAX_GRAD NORM
0.5
NUM MINIBATCHES
1
NUM EPOCHS
1
LR
0.0003
LR DECAY
False
GAMMA
0.99
42

---

Published as a conference paper at ICLR 2025
Game
Rainbow
PQN
Alien
9491.70
6970.42
Amidar
5131.20
1408.15
Assault
14198.50
20089.42
Asterix
428200.30
38708.98
Asteroids
2712.80
45573.75
Atlantis
826659.50
845520.83
BankHeist
1358.00
1431.25
BattleZone
62010.00
54791. 6.7
BeamRider
16850.20
23338.83
Berzerk
2545.60
18542.20
Bowling
30.00
28.71
Boxing
99.60
99.63
Breakout
417.50
515.08
Centipede
8167.30
11347.98
ChopperCommand
16654.00
129962.50
CrazyClimber
168788.50
171579.17
Defender
55105.00
140741.67
DemonAttack
111185.20
133075.21
DoubleDunk
-0.30
-0.92
Enduro
2125.90
2349.17
FishingDerby
31.30
46.17
Freeway
34.00
33.75
Frostbite
9590.50
7313.54
Gopher
70354.60
60259.17
Gravitar
1419.30
1158.33
Hero
55887.40
26099.17
IceHockey
1.10
0.17
Jamesbond
20000.00
3254.17
Kangaroo
14637.50
14116.67
Krull
8741.50
10853.33
KungFuMaster
52181.00
41033.33
MontezumaRevenge
384.00
0.00
MsPacman
5380.40
5567.50
Name ThisGame
13136.00
20603.33
Phoenix
108528.60
252173.33
Pitfall
0.00
-89.21
Pong
20.90
20.92
PrivateEye
4234.00
100.00
Qhert
33817.50
31716.67
Riverraid
20000.00
28764.27
RoadRunner
62041.00
109742.71
Robotank
61.40
73.96
Seaquest
15898.90
11345,00
Skiing
11295.880
29975..1
Solaris
3560.30
2607.50
SpaceInvaders
18789.00
18450.83
StarGunner
127029.00 .00
331300.00
Surround
9.70
5,88
Tennis
0.00
-1.04
TimePilot
12926.00
21950.00
Tutankham
241.00
264.71
UpNDown
100000.00
308327.92
Venture
5.50
76.04
VideoPinball
533936.50
489716.33
WizardOrWor
17862.50
30192.71
YarsRevenge
102557.00
129463.79
Zaxxon
22209.50
23537.50
Table 9: ALE Scores: Rainbow PQN (400M frames)
43


Reviews:
[{"review_id": "S2RsQSuwOU", "reviewer": "Reviewer_LgPr", "summary": "Modern deep-reinforcement learning resorts to techniques such as replay buffers and target networks to provide stability with nonlinear off-policy learning. However, learning becomes unstable without a replay buffer or target networks and can diverge. Recently, several works suggested using layer normalization or layer normalization in addition to l2 regularization to remedy this learning instability issue. This paper theoretically studies layer normalization’s role and identifies how layer normalization helps with stability and convergence. The paper also proposed a new method called PQN that uses layer normalization and parallelized environments to stabilize learning. The authors show the effectiveness of their method through a series of experiments on different domains of environments.", "questions": "- Is PPO using the same number of parallel environments as PQN in all experiments? I couldn’t find this information in the paper. Could you share this information and add it to the paper’s revision?\n- In line 428, the authors refer to a histogram in Appendix E, but there is no histogram. Do they mean the bar plot in Figure 12?\n- Typically, layer norm is not applied to the post-activation but instead to the pre-activation. This is an important distinction. The theory still works with the preactivation layer norm as long as you don’t use activation functions that scale up the inputs.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work on simplifying deep reinforcement learning and removing techniques that might not be necessary, like replay buffer and target networks, is undoubtedly fundamental to deep reinforcement research. This has vast implications for rethinking the widely existing deep RL approaches and can help in other important directions, like scaling RL with the number of parameters/samples. This paper provides a unique view that challenges existing beliefs on the importance of replay buffers and target networks. The approach is effective and efficient since it can be implemented parallelized on GPU, which outperforms other baselines with respect to wall clock time.", "weaknesses": "- The theoretical part of the manuscript is largely incoherent. \n  - The current manuscript scatters many things in the theory parts. It lacks a proper flow of ideas when describing the theoretical results and their implications, which makes it difficult to follow. Currently, it reads as bullet points, listing findings quickly without proper linking between subsequent findings or results.\n  - For example, the current theorems and lemmas are not well integrated with the text before and after them. They read as detached components, making reading unnecessarily harder.\n  - Notations can be improved. I suggest following Sutton & Barto (2018).\n  - Two things that are instrumental for the results based on Jacobian analysis: inequality 3 and inequality 4. More discussion is needed to understand these two conditions and their implications.\n  - Off-policy instability and nonlinear instability require their own theorem statements and separate proofs (even if previous works have shown them). In addition, the TD stability criterion needs a theorem statement about contraction mapping. \n  - The connection for why l2 is needed was not clear. It was directly introduced after layer norm without proper linking.\n- PQN solves a problem different from the baseline DQN, but this was never discussed\n  - The authors emphasize that PQN does not use a replay buffer or target network as an advantage over other methods, which is great. However, a similar emphasis is needed for the fact that PQN requires parallel environments and probably may fail if a single environment were used (the setting of the other baselines). Additionally, PQN solves another orthogonal problem (parallelized worlds) to the original RL problem (single world).\n  - Figure 1 is inaccurate. The replay buffer is part of the agent, not an external component. This needs to be fixed.\n  - The difference between Distributed DQN and PQN is unclear from Figure 1, although both solve the same problem (parallelized worlds), especially the point on synchronism and GPU is not clear.\n- The paper has several inaccuracies.\n  - The authors claim that their PQN is based on Peng’s Q($\\lambda$), but the actual algorithm does not use eligibility traces. Instead, the authors use Q-learning with $\\lambda$-return. This needs to be corrected. Additionally, the equation (line 326) needs to be derived from the first principle to make the paper accessible to the unfamiliar reader.\n  - Algorithm 1 is Q-learning with one-step targets. The authors mention that they use $\\lambda$-return target, so Algorithm 1 needs to be replaced with the algorithm actually used (Algorithm 2 in Appendix C).\n  - The authors claim they stabilize learning Baird’s counterexample and use Figure 7a to demonstrate that. However, in Figure 7a, the error increases from the starting point until it plateaus. I don’t think meaningful learning has happened since the error has increased instead of decreased. I see that with layer norm or layer norm + L2 regularization, the error doesn’t increase without bound but at the same time, the problem is not solved either.\n- Unfair or unclear empirical evaluation\n  - The authors compare algorithms that work with parallel environments against ones that do not, which requires careful experiments to compare them. \n  - In Figure 3, the authors need to write rainbow (200M) or DQN (200M) to understand what those horizontal lines represent clearly.\n  - When the authors say that PQN was trained for 400M frames, does that include the parallel environments? For example, if 128 parallel environments are used (according to Table 5), does this mean 3.125M frames were collected from each environment, resulting in a total of 400M frames, or does it mean that 400M frames were collected from each environment, resulting in 128x400M=51200M overall frames? The first option gives a fair comparison, but the second option is biased towards PQN since significantly more experience is used. I would like the authors to clarify this point.\n  - The authors used only 3 independent runs for Atari, relying on precedence.  This is a too low number to provide any statistical significance. Even if something was accepted before, it does not mean it is correct. I highly suggest the authors increase the number of independent runs to at least 10. This should be possible since both PQN and PPO are efficient (small clock time) and easy to run, according to the paper's claims.\n  - The authors mentioned that DQN/Rainbow uses 50M updates compared to 700k updates for PQN. I think it is unclear how these numbers are obtained, especially for PQN.\n  - In Figure 6a, PQN still learns well without divergence when no layer normalization is used. What is the reason? Why has no divergence happened?\n  - Since the authors compare against DQN and Rainbow (methods that use a single environment), an ablation where a different number of environments are considered (e.g., n=1 and n=10) to understand the provided stability coming from parallelized environments. I think parallel environments make the gradient signal more reliable compared to the single environment case, which is more prone to noisy gradients. This may be instrumental for PQN; thus, an ablation is needed.\n\n&nbsp;\n\n**Minor issues:**\n\n- line 9 in Algorithm 1 and line 10 in Algorithm 2 are incorrect. The negative sign should be a plus. Additionally, I think the use of $\\texttt{StopGrad}$ can be eliminated with the TD error vector you gave in Eq. 2\n\n&nbsp;\n&nbsp;\n\nOverall, I believe the ideas from this paper could serve as a good contribution to the community, but the current manuscript is not ready for publication and needs significant improvement. I'm willing to increase my score, given that the authors improved their manuscript's quality by 1) rewriting the theoretical part to make it coherent and more rigorous, 2) Fixing the inaccuracies, and 3) improving the empirical evaluation quality.", "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": "", "extra_scores": {}}, {"review_id": "bDc6pjaZQP", "reviewer": "Reviewer_gFms", "summary": "This paper proposes simplifications to multiple components of the Deep Q-Network (DQN)/TD learning method to enable more efficient training on a single GPU, offering a potential DQN baseline for future research. The modifications include:\n- Eliminating target network tricks: The authors theoretically demonstrate that combining layer normalization with L2 regularization leads to convergent temporal difference (TD) learning. They then conducted experiments to validate this empirically by removing the target network update tricks.\n- Removing replay buffer for experience replay: The paper identifies the replay buffer as a memory bottleneck that limits single-GPU training. While directly removing the replay buffer impacts sample efficiency, the paper demonstrates that when combined with vectorized environments, the GPU-based training method achieves better wall-clock time efficiency.\n- Batch-wise rollout using vectorized environments: The paper implements DQN training in a batch-wise manner, leveraging GPU parallelization (after removing the replay buffer). Instead of single actor rollout, the paper uses vectorized environments to generate rollouts in batch.\n\nTo validate their approach, the authors conduct comprehensive experiments on both theoretical/proof-of-concept environments (Baird's counterexample) and standard benchmarks (Atari and Crafter). Their results show that the proposed Parallelized Q-Network (PQN) achieves comparable performance to well-known baselines like PPO and Rainbow. Through ablation studies, they further demonstrate the importance of network normalization and justify the removal of the replay buffer.", "questions": "- Including Baird's counterexample results in the main text would strengthen the paper in my opinion, by providing a clearer connection between the theoretical analysis and experimental validation.\n- (Minor) The PPO baseline comparison in Figure 3 could be more consistent, though I understand the thinking to save compute. The paper could either compare both methods using 4e8 training frames in Figure 3(a), or include PPO results directly in Figure 3(b) across all Atari environments. Either approach would more effectively demonstrate PQN's competitiveness against established policy gradient methods, in terms of sample efficiency.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This paper is well-written and easy to follow, with clear presentation of both theoretical derivations and experimental results.\n- The paper's motivation is clear and compelling enough to me: it mainly provides a simplified Q-learning baseline that effectively leverages GPU parallelization and vectorized environments.\n- The proposed experimental evaluation is relatively comprehensive: it covers multiple domains including proof-of-concept environments, standard single-agent benchmarks such as Atari and Crafter, and multi-agent scenarios. They also covers variants of the Q learning methods to support the claim better in general.", "weaknesses": "There is no major weakness of this paper, but feel free to check the question section for minor questions.", "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": "", "extra_scores": {}}, {"review_id": "Kxzo3O9b7A", "reviewer": "Reviewer_Jf9o", "summary": "This paper analyses stability in temporal difference (TD) methods. The main contributions are theoretical proofs that (i) TD instability can be established using a Jacobian evaluated on the unit circle; and (ii) using the Layernorm regularisation technique can ensure stability. This then leads the authors to propose a deep Q-learning algorithm called PQN which is comptetive with the PPO approach to reinforcement learning.", "questions": "One question I have is why does the Jacobian have to be negative definite on the unit Circle? Why is simple negative definiteness not enough? Since any vector can be written as || u || = c || v || where c is a positive constant, it seems that simply negative definiteness of the Jacobian is required? It would be helpful to the reader if the authors could give more justification and/or insight into the reason negative definiteness on unit circle is required, or the authors may wish to reconsider their results and see whether the restriction can be removed.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper is well written, well formatted and quite readable. The authors present the essence of their results very well and show that stability of TD algorithms reduces to checking that a Jacobian is negative definite on the unit circle. This is a nice succinct and somehow intuitive result. Given the complexity of the proof, it was good to see the summary presented so concisely. \n\nOther results are then presented after this, including some insight into the causes of instability and then the approach using the layernorm to obtain stabilisation. The presentation here was not as clear as the above, but still acceptable and still concise. \n\nThe authors claim that their parallelised version of Q learning is motivated well and this seems to be backed up by experiments.\n\nThe overall implications of the authors' results are very significant: they have discovered and captured the root cause for TD instability, they have proposed an improvement which guarantees instability and they have showed that their new PQN performs exceptionally well on some examples.", "weaknesses": "A criticism is that the proof of the main theoretical results is long (there are 20 pages of additional material) and I would say not particularly well organised. Before the authors give the proofs, in my view, it would be good for them to outline the main steps. I found the proofs hard to follow and as one goes through the proofs, there is a feeling of being somewhat adrift. In other words, the summary in the main paper is good; the actual proofs in the appendix are less well clear.", "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": "", "extra_scores": {}}, {"review_id": "iGK2IgCRKf", "reviewer": "Reviewer_KANn", "summary": "This paper introduces Parallelised Q-Network (PQN), a streamlined deep online Q-Learning algorithm. PQN comprises two key components: a TD Learning objective without a target network, which instead applies layer normalization and L2 regularization, and a parallelized sampling approach that avoids the use of a replay buffer by leveraging vectorized environments. The authors provide theoretical analysis to support the claim that regularization can stabilize TD Learning in the absence of target networks. PQN demonstrates competitive performance across a wide range of environments, achieving results in significantly less wall-clock time.", "questions": "See above", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. PQN is straightforward and easy to implement. It removes the need for a target network and simplifies TD Learning.\n2. The paper includes theoretical analysis showing that regularization can help keep TD Learning stable without using target networks.\n3. PQN achieves higher computational efficiency compared with baseline methods, with minimal impact in sample efficiency.", "weaknesses": "1. It’s somewhat counterintuitive that PQN maintains sample efficiency while training only on online samples without a replay buffer. Additional explanation would help readers understand this aspect better.\n2. The removal of the target network in TD Learning and the parallelized sampling are independent components of the algorithm, yet their individual contributions to overall performance are unclear. More controlled experiments, like the one in Figure 6.d, would clarify the impact of each component.\n3. The parallelized sampling approach depends on vectorized environments, which feels more like an engineering choice than a novel contribution and is not feasible in many real-world applications. A significant portion of the wall-clock savings seems to come from this aspect. If my understanding is correct, DQN could also potentially eliminate the replay buffer and use a similar parallelized sampling approach. It would be informative to see how DQN performs under this setup.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)