Exploring the Promise and Limits of Real-Time Recurrent Learning
Authors: Kazuki Irie
Anand Gopalakrishnan
Jürgen Schmidhuber
Venue: ICLR 2024 poster (2024)
Keywords: recurrent neural networks
real-time recurrent learning
online recurrent learning
reinforcement learning
actor-critic
policy gradients
Primary area: general machine learning (i.e., none of the above)
TL;DR: We evaluate RTRL without approximation using element-wise recurrent networks on many standard RL tasks, and highlight challenges of RTRL rarely discussed in prior work.

Abstract: Real-time recurrent learning (RTRL) for sequence-processing recurrent neural networks (RNNs) offers certain conceptual advantages over backpropagation through time (BPTT). RTRL requires neither caching past activations nor truncating context, and enables online learning. However, RTRL's time and space complexity make it impractical. To overcome this problem, most recent work on RTRL focuses on approximation theories, while experiments are often limited to diagnostic settings. Here we explore the practical promise of RTRL in more realistic settings. We study actor-critic methods that combine RTRL and policy gradients, and test them in several subsets of DMLab-30, ProcGen, and Atari-2600 environments. On DMLab memory tasks, our system trained on fewer than 1.2B environmental frames is competitive with or outperforms well-known IMPALA and R2D2 baselines trained on 10B frames. To scale to such challenging tasks, we focus on certain well-known neural architectures with element-wise recurrence, allowing for tractable RTRL without approximation. Importantly, we also discuss rarely addressed limitations of RTRL in real-world applications, such as its complexity in the multi-layer case.

Published as a conference paper at ICLR 2024
EXPLORING THE PROMISE AND LIMITS OF REAL-TIME RECURRENT LEARNING
Kazuki Irie't Anand Gopalakrishnan' Jürgen Schmidhuber
Center for Brain Science, Harvard University, Cambridge, MA, USA
The Swiss AI Lab, IDSIA, USI & SUPSI, Lugano, Switzerland
3 AT Initiative, KAUST, Thuwal, Saudi Arabia
k kirieefar fas hwwvarr.aaa...... edu, fanand, juergen)eidsia.co
ABSTRACT
Real-time recurrent learning (RTRL) for sequence- processing recurrent neural net- works (RNNs) offers certain conceptual advantages over backpropagation through time (BPTT). RTRL requires neither caching past activations nor truncating context, and enables online learning. However, RTRL's time and space complexity make it impractical. To overcome this problem, most recent work on RTRL focuses on approximation theories, while experiments Here we explore the practical promise of RTRL in more realistic settings. We study actor-critic methods that combine RTRL and policy gradients, and test them in several subsets of DMLab-30, ProcGen, and Atari-2600 environments. On DMLab memory tasks, our system trained on fewer than 1. B environmental frames is competitive with or outperforms well-known IMPALA and R2D2 baselines trained on 10 frames. To scale to such challenging tasks, we focus on certain well-known neural architectures with element-wise recurrence, allowing for tractable RTRL without approximation. Importantly, we also discuss rarely addressed limitations of RTRL in real-world applications, such as its complexity in the multi-layer case
often limited to diagnostic settings.
INTRODUCTION
There are two classic learning algorithms to compute exact gradients for prquence-processiie re- current neural networks (RNNs): real-time recurrent learning (RTRL: Williams & Zipser (1989b a);
Robinson Fallside (1987): Robinson (1989) and backpropagation through time (BPTT: Rumelhart et al. Werbos (199). reviewed in Sec. 2}. In practice, BPTT is the only one commonly used today, simply because BPTT is tractable while RTRL is not. In fact, the time and space complexities of RTRL for a fully recurrent NN are quartic and cubic in the number of hidden units, respectively, which are prohibitive for any RNNs of practical sizes in real applications. Despite such an obvious complex- ity bottleneck, RTRL has certain attractive conceptual advantages over BPTT. BPTT requires cache activations for each new element of the sequence processed by the model, for later gradient compu- tation. As the amount of these past activations to be stored grows linearly with the sequence length, practitioners (constrained by the actual memory limit of their hardware) use the so-called truncated BPTT (TBPTT: Williams & Peng (1900)) where they specify the maximum number of time steps for this storage, giving up gradient components-ang therefore credit assignments teett go beyond this time span. In contrast, RTRL, does not require storing past activations, and enables computation of untruncated gradients for sequences of any arbitrary length. In addition, RTRL is an online learning algorithm (more efficient than BPTT to process long sequences the online scenario) that allows for updating weights immediately after consuming every new input (assuming that the external error feed- back to the model output is also available for each input). These attractive advantages RTRL still actively motivate certain researchers to work towards practical RTRL (c.g.. Tallec & Ollivier (2018); Mujika et al. (2018); Benzing et al. (2019); Menick et al. (2021): Silver et al. (2022)), while others
also motivated by the biological plausibility (e.g., |ellee et al. (019)) Lemmel & Grosu (2023)
The root of RTRL's high complexities is the computation and storage of the so-called sensitivity matrix whose entries derivatives of the hidden activations w.r.t. each trainable parameter of the
Our code is public: httpt::p//////t http::::///ittub.cooo IDS rtrl =11stm Work done IDSTA.

---

Published as a conference paper at ICLR 2024
model involved in the recurrence (see Sec. Most recent research RTRL focuses introducing approximation methods into the computation and storage of this matrix. For example, Menick et al.
(202T) introduce sparsity in both the weights of the RNN and updates of the temporal Jacobian (which
18 an intermediate matrix needed to compute the sensitivity matrix). Another line of work (Tallec) & Ollivier 2018 Mujika et al., 2018 [Benzing et al.) 2019) proposes estimators based on low-rank decompositions of the sensitivity matrix that are less expensive to compute and store than the original one. Silver one./Silver et al. (2022) explore projection-based approximations of the sensitivity. The main research question in these lines of work is naturally focused around the quality of the proposed approximation method. Consequently, the central goal of their experiments is typically to test syper--arameters and configurational choices that control the approximation quality in diagnostic settings, rather than evaluating the full potential of RTRL in realistic tasks. the end, we still know very little about the true empirical promise of RTRI. Also, assuming that a solution is found to the complexity bottleneck, what actual applications or algorithms would RTRL unlock? In what scenarios would it be beneficial to replace BPTT by RTRL in today's 's deep learning?
Here we propose to study RTRL by looking ahead beyond research on approximations. We explore the full potential of RTRL in the settings where approximation is needed, while at the same time, not restricting ourselves to toy tasks. For that, we focus on special RNN architectures with element- wise recurrence, that allow for tractable RTRL without any approximation. In fact, the quartic/cubic complexities of the fully recurrent NNs can be simplified for certain neural architectures. Many well- known RNN architectures, such as Quasi-RNN: RNNSs (Bradbury et al.] (017)) and Simple Recurrent Units (Lei et al. 2018), and even certain linear Transformers (Katharopoulos et al., 2020 Schmidhuber et al. 202Tp, belong to this class of models (see Sec. (.1). Note that the core idea underfying this observation is technically not new: Mozer (1989 1991] and Gori et al. (1899 already explore an RNN architecture with this property in the late 1980s (even though the problematic multi- layer case is ignored; we discuss it in Sec. 5). and Javed et al. (2021 2023) also exploit this in the architectural design of their RNNs. While such special RNNs may suffer from limited computational capabilities on certain tasks (i.e., one can come up with synthetic/algoritmiic task where such models fail; see Appendix[B.2) B.2), they also often perform on par with fully recurrent NNs on many tasks (at least, this is the case for the tasks explore in our experiments). For the purpose of this work, the RIRLL-tractability property outweighs the potentially limited computational capabilities: these architectures allow to focus on evaluating RTRL on challenging tasks with scale that goes beyond the one typically used in prior RTRL work, and to draw conclusions without worrying about the quality of approximation. We study an actor-critic algorithm (Konda & Tsitsiklis 1999; /Sutton et al. 1999 Mnih et al. (016) that combines RTRL and recurrent policy gradients (Wierstra et al. (010)). allowing credit assignments throughout an entire episode reinforcement learning (RL) with partially observable Markov decision processes (POMDPs; Kaelbling et al.) (1998); y); [Schmidhuber (1990)). We
test the resulting algorithm, Real-Time Recurrent Ariti-Critic method (R2AC), in several subsets of
DMLab-30 (Beattic et al. 2016). ProcGen (Cobbe et al. 2020), and Atari 2600 (Bellemare et al. 20133)
environments, with a focus on memory tasks. In particular, on two memory environments of DMLab- 30, our system is competitive with or outperforms the well-known IMPALA (Espeholt et al. 2018)
and R2D2 (Kapturowski et al. 2019) baselines, demonstrating certain practical benefits of RT RL at scale. Finally, working with concrete real-world tasks also sheds lights further limitations of RTRL that are rarely (if not never) discussed in prior work. These observations are important for future research on practical RTRL. We highlight and discuss these general challenges of RTRL (Sec. 5).
2 BACKGROUND
Here we first review real-time recurrent learning (RTRL; Williams & Zipser (1989 a); Robinson & Fallside (1987): Robinson (189)), which is a gradient-based learning algorithm for sequence- processing RNNs an alternative to the now standard BPTT.
Preliminaries. Let T. N, and D be positive integers. We describe the corresponding learning algorithm for the following standard RNN architecture (Elman 1990) that transforms an input atl) E R to an output h(t) E R at every time step / as
s() W=(() + Rh(l-11 ;
= -0)=)((())))
(I)
where W E NXD and R E R NXN are trainable parameters, s(t) E RN and a denotes the element-wise sigmoid function (we omit biases). For the derivation, it is convenient to describe each
2

---

Published as a conference paper at ICLR 2024
component (t) R of vector s(t) for [I,..,,
D
N
sx = Σ (n, + Σ
(s 1))
(2)
n=1
n=
In addition, we consider some loss function (1, - - L(t) R computed on an arbitrary sequence of length ' where [()) E IR is the loss at each time step i, which is function of k(()) (we omit writing explicit dependencies over the model parameters). Importantly, we assume that L(t) can be computed solely from (t(t) at step (i.e., [(t) has no dependency on any other past activations apart from h 1) which needed compute h(t)).
The role of a gradient-based learning algorithm is to efficiently compute the gradients of the loss OL (1,T)
OW. E IR for all i E (1,..,N] N} and w.r.t. the trainable parameters of the model, i.e.,
j E {1,..., D}. and O (1,T) R all i,j {1,..., N). RTRL and BPTT differ in the way a
to compute these quantities. While we focus on RTRL here, for the sake of completeness, we also provide an analogous derivation for BPTT in Appendix A.3
Real-Time Recurrent Learning (RTRL). RTRL can be derived by first decomposing the total loss C (1. T) over time, and then summing all derivatives of each loss component L(t) w.r.t. inter- mediate variables (t) for all k E (1,..., N):
dc (1,T)
T ac(t)
T
N
Oc(t)
@sx(t) OW.s
(3)
aW.
OW
(t)
In fact, unlike BPTT that can only compute the derivative of the total loss (1,a) efficiently, RTRL is an online algorithm that computes each term OL(() through the decomposition above. aW,,
The first factor aC(1) can be straightforwardly computed through standard backpropagation (as
(t)
stated above, we assume there is no recurrent computation between s(t) and L(t)). For the second (1) which is an element of the so-called sensitivity matrix/tensor, we can derive a forward
factor OW.;
recursion formuul,, which can be obtained by directly differentiating Eq
@sy(t) aw x1)(
(t
Σ Ru.no' (sn 1)) OW.,
where L denotes the indicator function: 1 = if h: = i, and O otherwise, and a' denotes the derivative of sigmoid, i.e, o'ss, 1)) (s, 1)) (s, 1))). The derivation
is similar for @C(l)
(1)(() As this algorithm oR where we obtain recurrent formula to compute oR:
requires to store (s
DW. and @su(() its space complexity is O(N2(D + N)) O(N3). The time .R.
complexity update the sensitivity matrix/tensor via Eq, 4 O(N*). To be fair with BPTT, it should be noted that O(N4) is the complexity for one update; this means that the time complexity to process a sequence of length T is O4.
Thanks to the forward recursion, the update frequency of RTRL is flexible: one can opt for fully online dC(t)
learning, where we update the weights using aw at every time step, or accumulate gradients for several time steps. It should be noted that frequent updates may result in staleness of the sensitivity
matrix, as it accumulates updates computed using old weights (Eq. 4).
Note that algorithms similar RTRL have been derived from several independent authors (see, e.g., Robinson & Fallside (1987); ;; Kuhn et al. (1990); Gori et al. (1989): Mozer (1989), or /Pearlmutter
(1989); Gherrity (1989) for the continuous-time time version).
3

---

Published as a conference paper at ICLR 2024
3 METHOD
Our main algorithm is actor-critic method that combines RTRL with recurrent policy gradients, using a special RNN architecture that allows for tractable RTRL. Here we describe its main com- ponents: an element-wist LSTM with tractable RTRL (Sec. 3.1. and the actor-critic algorithm that
builds upon IMPALA Esppeolt et al. 2018) (Sec. 3.2
3.1 RTRL FOR LSTM WITH ELEMENT-WISE RECURRENCE (ELSTM)
The main RNN architecture
in this work is variant of long short-term memory (LSTM; (Hochreiter & Schmidhuber (197)) RNN with element-wise recurrence. Let @ denote element-wise multiplication, each time step it first transforms an input vector (t)) E RD recurrent hidden state c(t) E R as follows:
f(t) = oFF((t) + w o -c(t-1)) x(t) = tanh Zzx(t) + w o c(t c(t) f(t) o 1)+ (1-)(t)) 3 xtt)
(5)
(6)
where f(t) RR,, =(t) E N are activations, F E RND and Z E NxD are trainable weight matrices, and w/ E R and w E R are trainable weight vectors. These operations are followed by gated feedforward NN to obtain an output h(t) E R as follows:
(t ((Ox(t)) Woc(t)); h(t) o(t) c(t)
where O E RNND and Wo NNN trainable weight matrices. This architecture be as an extension of Quasi-RNN (Bradbury et al. 2017) with element-wise recurrence in the gates, Simple Recurrent Units (Lei al. 2018) without depth gating, and also relates to many others (Li et al. 2018 Mozer 1989 Gonnet & Deselaers 2020 Gupta et al. 2022] Orvieto et al.) (023). While one could further discuss myriads of architectural details (Greff al.) 22166), most of them are irrelevant to our discussion on the complexity reduction in RTRI,; the only essential property here is that "recurrence" is element-wisg (whose limitations we discuss Appendix B.2).. We use this simple architecture above, an LSTM with element- recurrence (or eLSTM), for all our experiments.
Furthermore, we restrict ourselves to the one-layer case (we discuss the multi-layer case later in Sec. (5) where we assume that there is no recurrence after this layer. Based this assumption, gradients for the parameters O and Wo in Eq. can be computed by standard backpropagation, as they are not involved in recurrence. Hence, the sensitivity matrices need for RTRL (Sec. ( are: @c(l) dc(l)
OF az E NNNND and ōe(() de(()) Ow iw= E NRN Through trivial derivations (we provide the full derivation in Appendix A.I. we can show that each of these sensitivity matrices can be computed
using tractable forward recursion formula. For example for de(t) OF we have, for i, E {1,..,, N
and E (1,.... D}.
f((t) = -(0-)))))))()
-1- (,(t) f((t) + w/ f((t) + w/2(t)
2,(t) = (1- (1)()) ((())((12;(tt3))
(8)
(9)
(c,(t) (t))),,()) + (t) dc, 1) OF.,
Oc₂ (t)
and
=0 for all + i.
(10)
OF
OF.
where we introduce three intermediate vector f(1), (()) a(t) E RN with components f((t), ((), ct) E R. Consequently, the gradients for the weights can be computed as:
OC(1) N aC(l) x OF.J (cx(t) OF (t, OF.
dcx(t) aC(I)
dei(l)
x
(11)
Finally, compactly summarise these equations using standard matrix operations. By introduc-
de,(1) E R, and e(t) E TRN with es(1) = dc,(t)
HC(()) E TR.
ing notations (1) E RND with (ty(t) = OF.
4

---

Published as a conference paper at ICLR 2024
for E {1, ...,,................. NY and j E {1, {1. D), Eqs. 8 11
above can be written as:
f(t) (c(t - 1) - (t)) C (t) @ (1 (1- f(t)) : 2(t) - (1)
(12)
é(t) f(t) w/ @ f(t + : @
(13)
ac(t) OF
F(1) f()) a=)) + diag( ((1) F(1 1)
di)g(e(t))
(14)
where, for notational convenience, we introduce a function diag: R + R-NNN that constructs a diagonal matrix whose diagonal elements are those of the input vector; however, in practical implementations (c.g., in PyTorch), this can be directly handled vector-matrix multiplications with broadcasting (this is an important note for complexity analysis). & denotes outer-product. We can derive analogous equations for other parameters Z, w and w² (as well as biases which omitted here) using the same intermediate variables (f(1), (1), ē(t): Eqs. 12
13 ; see Appendix A.
The RTRL algorithm above requires maintaining sensitivity matrices Ftt E IR. Nx and analogously defined (t) E NDD w-((t) E RN,, and (t) E RN (see Appendix A.1 thus. the space complexity is O(DN)- ~ O(22). The per-step time complexity is O(N2) (see Eqs. 8 L1). Hence,
this algorithm is tractable. Importantly, these equations T2 14 can be implemented as simple PyTorch code (just like the forward pass of the same model; Eqs. 5 without any non-standard logics. Note that many approximations of RTRL involve computations that are not well supported yet in standard deep learning libraries (e.g.. efficiently handling custom sparsity in Menick et al. (2021)), which an extra barrier for scaling RTRL through these methods in practice.
Note that the derivation of RTRL for element- wise recurrent nets not novel: similar methods can be found in Mozer ( (189 1991): Gori et al. (1989) from the late 1980s. This result itself is also not very surprising, since element wise recurrence introduces obvious sparsity in the temporal Jacobian (which is part of the second term in Eq. 4 Nethertheless, we are not aware of any prior work pointing out that several modern RNN architectures such as Quasi-RNN (Bradbury et al.) 2017) or Simple Recurrent Units (Lei et al. 2018) yield tractable RTRL (in the one-layer case). Also, while this is not the focus of our experiments, we show an example of linear Transformers/Fast Weight Programmers (Katharopoulos et al. 20200] [Schmidhuber] 1991 Schlag et al.) (021) that have tractable RTRL (details can be found in Appendix [A.2). which is another conceptually interesting result. We also note that the famous L.STMalloritthm (Hochreiter & Schmidhuber 1997) (companion learning algorithm for the LSTM architecture) is a diagonal approximation of RTRI, so is the more recent SnAp-I 1 of Menick ctt al. (202I). Unlike in these works, the gradients computed by our RTRL algorithm above are exact for our cLSTM architecture. This allows us to draw conclusions from experimental results without worrying about the potential influence of approximation quality. We can evaluate the full potential of RTRL for this specific architecture.
Finally, this is also an interesting system from the biological standpoint. Each weight in the weight matrix/synaptic connections (c.g., F E IR NxD
D) is augmented with the corresponding "memory" (t) E NxD tied to its own learning process, which is updated in online fashion, as the model observes more and more examples, through an Hebbian/outer product-based update rule (Eq, Left))))
3.2 REAL-TIME RECURRENT ACTOR-CRITIE POLICY GRADIENT ALGORITHM (R2AC)
The main algorithm we study in this work, Real-Time Recurrent Actor-Critic method (R2AC), combines RTRL with recurrent policy gradients. Our algorithm builds upon IMPALA (Espeholt et al. 2018). Essentially, we replace the RNN architecture and its learning algorithm. LSTM/TBPIT in the standard recurrent IMPALA algorithm, by our eLSTM/RTRL (Sec.3.1) While we refer to the original paper [Espeholt et al. 2018) for basic details of IMPALA, here we recapitulate some crucial aspects. Let M denote a positive integer. IMPALA a distributed actor-critic algorithm where each actor interacts with the environment for a fixed number of steps M to obtain a catte-action-ewaard trajectory segment of length M to be used by the learner to update the model parameters. M is an important parammer that is used to specify the number of steps M for M-step TD learning (Sutton& & Barto 1998) of the critic, and the frequency of weight updates. Given the same number of environmental steps used for training, systems trained with smaller M apply more weight updates than those trained with a higher M. For recurrent policies trained with TBPTT, M also represents the BPTT span (i.e., BPTT is carried out on the M-length trajectory segment; no gradient is propagated
5

---

Published as a conference paper at ICLR 2024
farther than M steps back in time; while the last state of the previous segment is used as the initial state of the new segment in the forward pass). In the case of RTRL, there is no gradient truncation, but since M controls the update frequency. the greater the M, the less frequently we update the parameters, and it potentially suffers less from sensitivity matrix staling. This setting allows for comparing TEPTT and RTRL in the setting where everything is equal (including the number of updates) except the actual gradients applied to the weights: truncated vs. untruncated ones.
se
Note that for R2AC with M 1. one could obtain a fully online recurrent actor-critic method. However, in practice, it is known that M > is crucial (for TD learning of the critic) for optimal performance. In all our experiments, we have M 1. Our main focus is evaluate learning with untruncated gradients, rather than the potential for online learning (discussed in Appendix B.3
EXPERIMENTS
Here we present the main experiments of this work: RL in POMDPs using realistic game environments requiring memory. Other synthetic/diagnosiic experiments reported in Appendix 1.1 B.2
DMLab Memory Tasks. DMLab-30 (Beattie al. 2016) is a collection of 30 first-person 3D game environments, with mix of both memory and reactive tasks. Here we focus on two well-known environments, zooms_sed sooms_seleee wnommttttttttt.....oo.... chinghhb
and rooms_wal emaze, which are both categorised as "memory" tasks according to Parisotto et al. (2020). The mean episode lengths of these tasks are about 100 and 1000 steps, respectively. As we apply an action repetition of 4, each "step" corresponds to 4 environmental frames here. We refer to Appendix B.3 for further experimental details. Our model architecture is based on that of IMPALA (Espeholt et al. 2018). Both RTRL and TBPTT systems Everything is equal between these two systems except that the gradients are truncated in TBPTT but not in RTRL. To reduce the overall compute needed for the experiments, we first pre-train TBPTT model for 50 M steps for www.ssseeect_nnooee for rooms waterma ze. Then, for all main training runs in this experiment, we initialise the parameters of the convolutional vision module from the same pre-trained model, and keep these parameters frozen (and thus, only train the recurrent layer and everything above it). For these main training runs, we train for 30 M and 100 M steps for rooms .se Lect _no.mat ching-ob ject and rooms sooms_wateee watermaz
our eLSTM (Sec. 3.1 as the recurrent layer with hidden state size of 512.
wwwhcchinoooo ject, and for 200 M steps
respectively; resulting in the total of 320 M and 1.2 B environmental frames. We compare RTRL and TBPTT for different values of M E {10, 50, 100} which influences: the weight update frequency, M step TD learning, and for TBPTT, the backpropagation span (Sec. (..2).
Table shows the corresponding scores, and the left and middle parts of Figure I show the training curves. We observe that for select nonmat chimatchhin ng object which has a short mean episode length of 100 steps, the performance of TBPTT and RTRI. is similar even with M 50. The benefit of RTRL is only visible in the case with AM- = 10. In contrast, for the more challenging rooms_wat e rmaze task with the mean episode length of 1000 steps, RTRL outperforms TBPTT for all values of M E {10, 50, 100). Furthermore, with M = 50 or 100, our RTRL system outperforms the IMPALA and R2D2 systems from prior work (Kapturowski et al. 2019), while trained on fewer than 1.2 B frames. Note that R2D2 systems (Kapturowski et al.) 2019) are trained without action repetitions, and with a BPTT span of 80. This effectively demonstrates the practical benefit of RTRL in realistic task requiring long-span credit assignments.
In Appendix B.3 pacts in a mostly reactive task (by testing our system on one environment of DMLab-30, room_keys soryssddorssspppp .doors.puzzle, which is categorised as reactive task according to Parisooto et al. 22020). There, we also report practical computational costs, and discuss online learning.
also show that RTRL does not have any unexpected negative im-
ProcGen. We test R2AC in another domain: ProcGen (Cobbe et al. 2020). We focus on one environment in the standard hard-mode, Chaser, which shows clear benefits of recurrent policies over those without memory (further details in Appendix B.4). Chaser is similar to the classic game "Pacman," effectively requiring some counting capabilities to fully exploit power pellets valid for a limited time span. The mean episode length for this task is about 200 steps, where each step is an environmental frame as we apply no action repeat for ProeGen. Unlike in the DMLab experiments above, here we train all models from scratch for 200 M steps without pre-training the vision module

---

Published as a conference paper at ICLR 2024
Scores on two memory environments of DMLab-30. Numbers on the top part are copied from the respective papers for reference. For both rooms weweeeeeeeeeeeee weceeeteeeeeee wwweeet..oomeee cont.noomatteom chingtchhiiiiiee sching-bb -ogbbbby ject and rooms scoos_wateee www.wwatteaaaeeee......ee we report mean and standard deviation computed over training seeds (each using 3 sets of 100 test episodes; see Appendix [B33). "frames" indicates the number of environmental frames used for training. M is the hyper-parameter that controls weight update frequency, M-step TD learning, and backpropagation span for TBPTT in IMPALA (see Sec. 3.2)
Table 1:
frames
M
select.nonmater ch
wate rmaze
IMPALA (Espeholt et al.
2018)
1
100
7.3
26.9
IMPALA ( Kapturowski et al.
2019)
10
100
39.0
47.0
R2D2 Kapturowski cf al.
2019)
I0B
2.3
45.9
R2D2+ Kaplurowwkii et al.
2019)
10
63.6
49.0
TBPTT
54.5 + 1.1
15.8 0.9
1.2B
10
RTRL
61.8 + 0.5
40.2 + 5.6
TBPTT RTRL
61.4 + 0.5
44.5 + 1.5
1.2B
50
62.0 + 0.4
52.3
TBPTT
61.7 + 0.1
45.6 4.7
1.2B
100
RTRL
62.2 + 0.3
54.8 + 4.3
TDPTT RTL
TOPTT
NTTL
Foodlomoud
Stoca
Stoss
Steps
(a) Non-matching. M 10
(b) Watermaze, M = 10
(c) Chaser, M 5
18TTT
43
92
13
301
050
175 229
(d) Non-matching, M 100
Watermaze, M 100
(f) Chaser, M 50
Figure 1: Training curves on DMLab-30 wwmmmssseeett.ooom www.ettnnmtaatinnnn.ooom ciw.mmttccin...oeec...... (Non- matching) and zooms watermaze (Watermaze), and Procgen Chaser environments.
(since training the vision parameters using RTRL is intractable, they are trained with truncated gradients, i.e., only the recurrent layer trained using RTRL: further discussed Sec. We compare RTRL and TBPIT with M = 5 or 50. The training curves are shown in the right part of Figure Similar the rooms se no nonmat ching case above, with sufficiently large M 50, there is no difference between RTRL and TBPTT, while we observe benefits of RTRL when M = 5.
Atari. Apart from some exceptions (such as Solaris (Kapturowski et al. 2019)), many of the Atari game environments are considered to be fully observable when observations consist stack frames (Mnih et al.) 2015 Hausknecht & Stone, 2015). However, it is also empirically known that, for certain games, recurrent policies yield higher performance than the feedforward ones having only access to 4 past frames (see, e.g., Mott al. 2019); Kapturowski et al. (2019); Irie et al. (2021)) Here our general goal is to compare RTRL to TEPTT more broadly. We use five Atari environments: Breakout, Gravitar, Ms MsPacman, h*bert, and Seaquest, following Kapturowski al. 2019) selection
7

---

Published as a conference paper at ICLR 2024
240
185
3400
3000
2000
3000
TOPTT
TOPTT RTR.
BTIL
6.9
STEPS
Stgps
500g
14
(a) Breakout
(b) Gravitar
(c) MsPucman
12:00
12000
8400
2.00
TIPTT
2002
TSPTT
Stapa
(d) QeBt
(c) Seaquest
Figure 2: Learning curves on five Atari environments
for evaluating their R2D2. Here we use M = 50, and train for 200 M steps (with the action repeat of 4) from scratch. The learning curves are shown in Figure 2 With the exception of MsPacman (note that, unlike ProeGen/Chaser above, 4-frame stacking used) where we observe a slight performance degradation, RTRL performs equally well or better than TBPTT in all other environments.
Comparison to other baselines. Table report comparisons to other architectures and learning algorithums on the DMLab-30 memory tasks. The top-part of Table is pure architecture comparison using TBPTT for all models. We denote by 'feLSMM' am intermediate architecture between the stan- dard LSTM and our eLSTM, obtained by replacing the element- wise recurrence in Eq. 5 of eLSTM by the full recurrence (i.e, weight vectors w and w in Eq. are replaced by weight matrices; see Ap- pendix (n.5 for full details). eLSTM outperforms LSTM, while feLSTM performs similarly. RTRL for feLSTM is not tractable as it contains the full recurrence. The bottom-part of Table 2 shows that our exact RTRL using eLSTM clearly outperforms an approximate RTRL, SnAp- applied to feLSTM.
Table 2: Scores on two memory environments DMLab-30 for M 100 (see also Table
Architecture
Recurrence
Learning Algorithm
select.nennatee
watermaze
LSTM feLSTM
full
TBPTT
61.7 - 0.5
37.6 + 5.3
full
TBPTT
61.5 + 0.4
43.2 1 4.7
eLSTM
element-wise
TBPTT
61.7 + 0.1
45.6 4.7
fc full
SnAp-1 RTRL
53.6 + 0.8
27.7 + 3.2
cLSTTM
element-wise
62.2 + 0.3
54.8 + 4.3
5 LIMITATIONS AND DISCUSSION
Here we discuss limitations of this work, which also shed light on more general challenges of RTRL. Other limitations of our setting can be found in Appendix B.2
Multi-layer case of our RTRL, The most crucial limitation of our tractable-RTRL. algorithm for element-wise recurrent nets (Sec. 3.1) is its restriction to the one-layer case. By stacking two such layers, the corresponding RTRL algorithm becomes intractable as we end up with the same complexity bottleneck as in fully recurrent networks. This is simply because by composing two such element- wise recurrent layers, obtain an NN which contains some cooleecco transformations over time as a whole. This can be easily seen in the following equations. By introducing extra superscripts to denote the layer number, in stack of two element-wise LST layers of Eqs. 6 (we remove the
8

---

Published as a conference paper at ICLR 2024
output gate), express the recurrent state (t) of the second layer step t function of the recurrent state el (t- 1) of the first layer from the previous step follows:
(1)
(1) 2 (()
(( o oz (2)
(15)
f (t) o o(F (t)+ oc
(16)
((F(2) (f
1)+ (t=
(t) o 2 x0()) +...)
(17)
= =F (() о - 1)+ 1-
2 (1+
(18)
By looking at the first term of Eq. 13 and that of Eq. 18 one can that there is full recurrence between (t) and (t 1) via F(2,, which brings back the quartic/cubic time and space complexity for the sensitivity of the recurrent state the second layer w.r.t. parameters of the first layers. This limitation is not discussed in prior work (Mozer) 1989; 1991).
Complexity of multi-layer RTRL. in general. Generally speaking, RTRI. for the multi-layer case (a standard setting in modern deep learning) is rarely discussed (except Meert & Ludik (1977) and more recently Javed et al. (2023): Zucchet et al. (2023). ). There are two important remarks to be made here.
First of all, even in an NN with a single RNN layer, if there is a layer with trainable parameters whose output is connected to the input of the RNN layer, a sensitivity matrix needs to be computed and stored for each of these parameters. A good illustration is the policy net used in all our RL experiments where our LLST layer takes the output of a deep (feedforward) convolutional net (the vision stem) input. As training this vision stem using RTRL requires dealing with the corresponding sensitivity matrix, which is intractable, we train/pretrain the vision stem using TBPTT (Sec. D This is an important remark for RTRL research in general. For example, approximation methods proposed for the single-layer case may not scale to the multi-layer case, e.g., to exploit sparsity in the policy net above, not enough assume weight sparsity the RNN layer, but also in the vision stem.
Second, the multi-layer case introduces more complexity growth to RTRL than to BPTT. Let L denote the number of layers. We seemlessly use BPTT with deep RNNs, as its time and space complexity is linear in L.. This is not the case for RTRL. With RTRL., for each recurrent layer, we need to store sensitivities of all parameters of all preceding layers. This implies that, for an I.-layer RNN, parameters in the first layer require L sensitivity matrices, L 1 for the second layer, .... etc., resulting - 1 = L(L + 1)/2 sensitivity matrices to be computed and stored. Given
in L (L - 1) +... + that multi-layer NNs are crucial today, this remains a big challenge for practical research.
Principled vs. practical solution. Another important aspect of RTRL research is that many re- alistic memory tasks have actual dependencies/credt assignment paths that are shorter than the maximum BPTT span we can afford in practice. In our experiments, with the exception of DMLab rooms waterma ze (Sec. + no task actually absolutely requires RTRL in practice; TBPTT with a large span suffices. Future improvements of the hardware may give a further advantage to TBPTT; the practical (simple) solution offered by TBPTT might be prioritised over the principled (complex) RTRL solution for dealing with long-span credit assignments. This is also somewhat reminiscent of the Transformer vs. RNN discussion regarding sequence processing with limited vs. unlimited context.
Sequence-level parallelism. While our study focuses on evaluation of untruncated gradients, another potential benefit of RTRL is online learning. For most standard self/supervised tasks such as language modelling, however, modern implementations are optimised to exploit access to the "full" sequence, and to leverage parallel computation across the time axis (at least for training: further discussed in Appendix [B.2). While some hybrid RTRL-BPTT approaches (Williams) (189);; Schmidhuber [192): Williams & Zipser 1995); see Appendix A.4) may still be able to exploit such parallelism, fast online learning remains open engineering challenge even with tractable RTRL.
6 CONCLUSION
We demonstrate the empirical promise of RTRL in realistic settings. By focusing on RNNs with element-wiss recurrence, we obtain tractable RTRL without approximation. We evaluate our rein- forcement learning RTRL-based actor-critic in several popular game environments. In one of the challenging DMLab-30 memory environments, and R2D2 baselines which use many more environmental steps. We also highlight general important limitations and further challenges of RTRL rarely discussed in prior work.
system outperforms the well-known IMPALA

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
We thank Róbert Csordás for helpful suggestions for the figures, and help with installing DMLab. This research was partially funded by ERC Advanced grant no: 742870, project AlgoRNN, and by Swiss National Science Foundation grant no: 200021 192356, project NEUSYM. We are thankful for hardware donations from NVIDIA and IBM. The resources used for this work were partially provided by Swiss National Supercomputing Centre (CSCS) project s 145 and d123.
REFERENCES
Charles Beattie, Joel Z Leibo, Denis Teplyashin, Tom Ward, Mareus Wainwright, Heinrich Küttler, Andrew Lefrancq, Simon Green, Victor Valdés, Amir Sadik, et al. Deepmind lab. Preprint 1612.030/ 2016.
Guillaume Bellec, Franz Scherr, Elias Hajek, Darjan Salaj. Robert Legenstein, and Wolfgang Maass. Biologically inspired alternatives to hackpropagation through time for learning in recurrent neural nets. Preprint arXiv: (a0:::99100940 2019.
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.
Frederik Benzing, Marcelo Matheus Gauy, Asier Mujika, Anders Martinsson, and Angelika Steger. Optimal kronecker-sum approximation of real time recurrent learning. In Proc. Int. Conf. on Machine Learning (ICML), volume 97, pp. 604-613, Long Beach, CA, USA, June 2019.
James Bradbury, Stephen Merity, Caiming Xiong, and Richard Socher. Quasi-recurrent neural networks. In Int. Conf. Learning Representations (ICLR), Toulon, France, April 2017.
Karl Cobbe, Christopher Hesse, Jacob Hilton, and John Schulman. Leveraging procedural generation to benchmark reinforcement learning. In Proc. Int. Conf. on Machine Learning (ICML), pp. 2048-2056, Virtual only, July 2020.
Jeffrey L Elman. Finding structure in time. Cognitive science, 14(2):179-211, 1990.
Lasse Espeholt, Hubert Soyer, Rémi Munos, Karen Simonyan, Volodymyr Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, Shane Legg, and Koray Kavukcuoglu. IMPALA: scalable distributed Reep-RL with importance weighted actor-learner architectures. Proc. Int. Conf. on Machine Learning (ICML), pp. 1406-141 1415, Stockholm, Sweden, July 2018.
Angela Fan, Thibaut Lavril, Edouard Grave, Armand Joulin, and Sainbayar Sukhbaatar. Addressing some limitations of Transformers with feedback memory. Preprint 2002:0000 2020..
Michael Gherrity, A learning algorithm for analog, fully recurrent neural networks. Proc. Int. Joint Conf. on Neural Networks (IJCN), volume 643, 1989.
Pedro Gonnet and Thomas Deselaers. IndyLSTMs: Independently recurrent LSTMS, Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP), pp. 3352-3356, Barcelona, Spain, May 2020.
Marco Gori, Yoshua Bengio, and Renato De Mori. BPS: A learning algorithm for capturing the dynamic nature of speech. In Proc. Int. Joint Conf. on Neural Networks (IJCNN), pp. 417-423, Washington, DC, USA, 1989.
Klaus Greff, Rupesh K Srivastava, Jan Koutník, Bas R Steunebrink, and Jürgen Schmidhuber. LSTM: A search space odyssey. IEEE transactions neural networks and learning systems, 28(10): 2222-2232, 2016.
Ankit Gupta, Albert Gu, and Jonathan Berant. Diagonal state spaces effective structured state spaces. In Proc. Advances in Neural Information Processing Systems (NeurIPS), New Orleans, LA, USA, November 2022.
10

---

Published as a conference paper at ICLR 2024
Matthew J. Hausknecht and Peter Stone. Deep recurrent Q-learning for partially observable MDPs. In AAAI Fall Symposia, pp. 29-37, Arlington, VA, USA, November 2015.
Matteo Hessel, Hubert Soyer, Lasse Espeholt, Wojciech Czarnecki, Simon Schmitt, and Hado van Hasselt. Multi-task deep reinforcement learning with popart. Proc. AAAI Conf. on Artificial Intelligence, pp. 3796-3803, Honolulu, HI, USA, January 2019.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):
1997.
Kazuki Irie, Imanol Schlag, Róbert Csordás, and Jürgen Schmidhuber. Going beyond linear transform- ers with recurrent fast weight programmers. In Proc. Advances Neural Information Processing Systems (NeurIPS), Virtual only, December 2021.
Kazuki Irie, Róbert Csordás, and Jürgen Schmidhuber. Practical computational power of linear transformers and their recurrent and self-referential extensions. In Pruc. Conf. Empirical Methods in Natural Language Processing (EMNLP), Sentosa, Singapore, 2023.
Khurram Javed, Martha White, and Richard S. Sutton. Scalable online recurrent learning using columnar neural networks. Preprint arXiv:2103.05787, 2021.
Khurram Javed, Haseeb Shah, Rich Sutton, and Martha White. Scalable real-time recurrent learning using columnar-constructive networks. J. Mach. Learn. Res., vol.24, 2023.
Leslie Pack Kaelbling, Michael Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2);99-13, 1998.
Steven Kapturowski, Georg Ostrovski, John Quan, Rémi Munos. and Will Dabney. Recurrent experience replay in distributed reinforcement learning. In Int. Conf. on Learning Representations (ICLR), New Orleans, LA, USA, May 2019.
Angelos Katharopoulos, Apoory Vyas, Nikolaos Pappas, and François Fleuret. Transformers are RNNs: Fast autoregressive transformers with linear attention. In Proc. Int. Conf. on Machine Learning (ICML), Virtual only, July 2020.
Vijay R. Konda and John N. Tsitsiklis. Actor-critic algorithms. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 1008-1014, Denver, CO, USA, November 1999.
Ben Krause, Emmanuel Kahembwe, lain Murray, and Steve Renals. Dynamic evaluation of neural sequence models. In Proc. Int. Conf. on Machine Learning (ICMI., pp. 2771-2780, Stockholm, Sweden, July 2018.
Gary Kuhn, Raymond L Watrous, and Bruce Ladendorf. Connected recognition with a recurrent network. Speech Communication, 9()):11-8, 1990.
Heinrich Küttler, Nantas Nardelli, Thibaut Lavril, Marco Selvatici, Viswanath Sivakumar, Tim Rocktäschel, and Edward Grefenstette. Torchbeast: PyTorch platform for distributed RI. 2019.
Preprint wwtxiv:/910.00
Tao Lei, Yu Zhang, Sida I. Wang, Hui Dai, and Yoav Artzi. Simple recurrent units for highly parallelizable recurrence. In Proc. Conf. Empirical Methods in Natural Language Processing (EMNLP), pp. 4470 4481, Brussels, Belgium, November 2018
Julian Lemmel and Radu Grosu. Real-time recurrent reinforcement learning. Preprint
arXiv:231 1.04830 2023.
Shuai Li, Wanqing Li, Chris Cook, Ce Zhu, and Yanbo Gao. Independently recurrent neural network (IndRNN): Building longer and deeper RNN. In Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), pp. 5457-5466, Salt Lake City, UT, USA, June 2018.
Kürt Meert and Jacques Ludik. A multilayer real-time recurrent learning algorithm for improved convergence. In Proc. Int. Conf. on Artificial Neural Networks (ICANN), pp. 145-450, Lausanne, Switzerland, October 1997.
11

---

Alexander Mott, Daniel Zoran, Mike Chrzanowski, Daan Wierstra, and Danilo Jimenez Rezende. Towards interpretable reinforcement learning using attention augmented agents. In Proc. Advances Vancouver, Canada, Published as a conference paper at ICLR 2024
Jacob Menick, Erich Elsen, Utku Evci, Simon Osindero. Karen Simonyan, and Alex Graves. Practical real time recurrent learning with a sparse approximation. In Int. Conf. on Learning Representations (ICLR), Virtual only, May 2021.
William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. A formal hierarchy of RNN architectures, In Proc. Association for Computational Linguistics (ACL),
pp. 443-459, Virtual only, July 2020.
Tomás Mikolov, Martin Karafiát, Lukás Burget, Jan Cernocký, and Sanjeev Khudanpur. Recurrent neural network based language model. In Proc. Interspeech, pp. 1045-1048, Makuhari, Japan, September 2010.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529 533, 2015.
Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Proc. Int. Conf. on Machine Learning (ICML), pp. 1928-1937, New York City, NY, USA, June 2016.
in Neural Information Processing Systems (NeurIPS), pp. December 2019.
Michael C. Mozer. A focused backpropagation algorithm for temporal pattern recognition. Complex Systems, 3(4):349-311, 1989.
Michael C. Mozer. Induction of multiscale temporal structure. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 275-282, Denver, CO, USA, December 1991.
Asier Mujika, Florian Meier, and Angelika Steger. Approximating real-time recurrent learning with random kronecker factors. In Proc. Advances Neural Information Processing Systems (NeurIPS), pp. 6594-6603, Montréal, Canada, December 2018.
Antonio Orvicto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences. Proc. Int. Conf. on Machine Learning (ICML), Honolulu, Hawaii, USA, July 2023.
Fabian Paischer, Thomas Adler, Vihang Patil, Angela Bitto- Nemling, Markus Holzleitner, Sebastian Lehner, Hamid Eghbal-Zadeh, and Sepp Hochreiter. History compression via language models in reinforcement learning. In Proc. Int. Conf. Machine Learning (ICML), Baltimore, MD, USA, July 2022.
Emilio Parisotto, Francis Song, Jack Rae, Razvan Pascanu, Caglar Gulcehre, Siddhant Jayakumar, Max Jaderberg, Raphael Lopez Kaufman, Aidan Clark, Seb Noury, Matthew M. Botvinick, Nicolas Heess, and Raia Hadsell. Stabilizing Transformers for reinforcement learning. In Proc. Int. Conf. on Machine Learning (ICML), pp. 7487-7498, Virtual only, July 2020.
Barak A Pearlmutter. Learning state space trajectories in recurrent neural networks. Neural Compu- tation, 1(2):263-269, 1989.
Anthony J Robinson. Dynamic error propagation networks. PhD thesis, University of Cambridge, 1989.
Anthony Robinson and Frank Fallside. The utility driven dynamic error propagation network, volume 1. University of Cambridge Department of Engineering Cambridge, 1987.
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by back-propagating errors. nature, 323(6888) 1986.
Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber. Linear Transformers are secretly fast weight programmers. In Proc. Int. Conf. Machine Learning (ICML), Virtual only, July 2021.
12

---

Published as a conference paper at ICLR 2024
Jürgen Schmidhuber. An on-line algorithm for dynamic reinforcement learning and planning in reactive environments. In Proc. Int. Joint Conf. on Neural Networks (IJCNN), pp. 253-255 San Diego, CA, USA, June 1990.
Jürgen Schmidhuber. Learning control fast-weight memories: An alternative recurrent nets. Technical Report FKI--17-911, Institut für Informatik, Technische Universität München, March 1991.
Jürgen Schmidhuber. A fixed size storage o(n²) time complexity learning algorithm for fully recurrent continually running networks. Neural Compulation, 4(2):243-248, 1992.
David Silver, Anirudh Goyal, Ivo Danihelka, Matteo Hessel, and Hado Hasselt. Learning by directional gradient descent. In Int. Conf. on Learning Representations (ICLR), Virtual only, April 2022.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 1998.
Richard S. Sutton, David A. McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 1057-1063, Denver, CO, USA, November 1999.
Corentin Tallec and Yann Ollivier. Unbiased online recurrent optimization. In Int. Conf. on Learning Representations (ICLR), Vancouver, Canada, April 2018.
Paul Werbos. Backpropagation through time: what it does and how do it. Proceedings of the IEEE, 78( 18500))1500-1560, 1990.
Daan Wierstra, Alexander Förster, Jan Peters, and Jürgen Schmidhuber. Recurrent policy gradients. Logic Journal of IGPL, 18(2):620-634, 2010.
Ronald Williams. Complexity of exact gradient computation algorithms for recurrent neural networks. Technical report, NU-CCS-89-27, Northeastern University, College of Computer Science, 1989.
Ronald J Williams and Jing Peng. An efficient gradient-basee algorithm for online training of recurrent network trajectories. Neural computation, 2(4):490-501, 1990.
Ronald Williams and David Zipser. Experimental analysis of the real-time recurrent learning algorithm. Connection science, 1(1):77111, 1989a.
Ronald J Williams and David Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural computation, ((2):270-280, 1989b.
Ronald J Williams and David Zipser. Gradient-based learning algorithms for recurrent networks and their computational complexity. Backpropagation: Theory, architectures, and applications, 433: 17, 1995.
Nicolas Zucchet, Robert Meier, Simon Schug, Asier Mujika, and João Sacramento. Online learning of long-range dependencies. In Proc. Advances in Neural Information Processing Systems (NeurIPS), New Orleans, LA, USA, December 2023.
13

---

Published as a conference paper at ICLR 2024
A DERIVATIONS
A. RTRL FOR LSTM WITH ELEMENT-WISE RECURRENCE
In Sec. 3.1 we only show RTRL equations (Eqs. 14p for one weight matrix eLSTM (F in Eq. Here we provide complete equations and their derivations for all other parameters.
First of all, the exact eLSTM architecture used all our experiments use biases ,', 6 RR,, i.e., Eqs. 5 are replaced by:
(()) - ((F((t) w
clt 1) b)) z(t) tanh( tanh(Za(()) + w o 1) b²) (19) RNXNXD, and Oc(t) Oc(t)
0c(t) dc(t)
Therefore, addition to
Ow Ow E RNXN, we also have
OF
oz
dc(t) dc(t) 0b ab E RNNN as the sensitivity matrices to computed/stored for RTRL. Note that adding
these biases do not change the RTRL equations for F presented Eq. Sec. 3.1
We recall that we define e(t) E T with e;(() = (C(()
(t,(t) E IR for E (1,..., N) in Sec. 3.1 which
can be computed using standard backpropagation (as we assume that we have no recurrent layer between c(t) and [()).
also recall that, for convenience, we introduce three following intermediate variables ((), E N which appear in several equations.
f(t) (c(t 1) x(t)) ft) o -1- (1))(t)
2(t) -1 f(t) @ x())²)
ē(t) = f() + w o f(t) + w o =(t)
13
The complete list of our RTRL equations is as follows.
de,(t)
Equations for F. We define F(I) E NXD with Fiy(()
R.
FF,,
aC(t)
F(t) = f(t) x()) + diag(c(t))F(t -1)
diag(e(t))F(()
14
OF
dc,(t)
Equations for Z. We define 2(1) E NRD with Zi
OZ.. E R..
OC(t)
2t) a(t) x(t) + diag(e(t))2(t -1)
(iag(e(t))2(t)
(20)
az
Equations for w/. We define v/ (1) E R with w/ (1) dc,(t)
E R.
Ow!
OL(I)
i (t) = () a (1 :
= e(t) 2 (t(
(21)
dw
Equations for v We define uh E R with (t(( = (c,
Ow E R.
OC(L) Ow
w (t) 2(t c(t 10--1)--- é(t) (t--) 1)
e(t) O 10
(22)
Equations for b'. We define (1) E N with (1) (1, E..
ob!
aC(t)
(((t)= - f(t) + a(t) o 0' 1)
0b = e(t) 2 ((())
(23)
14

---

Published as a conference paper at ICLR 2024
(t,(t)
Equations for b². We define (*(t) R with (²())
E R.
db
0C(1)
(t) =t) 2(t) o (1 (t-1) (1-1)
e(t) ② (1)
(24)
ab
Note that the actual implementation is tested by comparing the gradients computed through our RTRL algorithm against those computed by BPTT (using the common PyTorch reverse-mode automatic differentiation).
Now we provide the corresponding derivations. Let k E {I,..., N and j E {I,...,
Derivation for F. Common to all cases, the goal is to compute the gradients of the loss w.r.t. the corresponding model parameter. Since we assume there no recurrent layer after this layer (see our settings of Sec. 2 we can express the corresponding gradient
ac(t) FF.
N
aC(t)
Ocx(t)
(25)
(t)
OF.5
k=1
0C(t)
As assume we can compute the first factor
(1) using standard backpropagation, what
Oc, (1)
(1)
remains to be computed is the second factor
The direct differentiation of Eq. 6 yields:
FF.jj
dcx(1) (c - 1) -1)) (1)
(c + (1 -f((1)) FF.
(z)
ft((I)
(26)
FF.
F..
OF.j
Now, we explicitly compute aF.j and (t)
(f)
OF. as:
0ff((t)
w dt 1)
dzx(t) (f)w Ocx(t 1)
(t((t) 2z, (t)(
(27)
OF,
OF.
OF.j
OF.j
where 2'()) R are the "derivatives" of ft) (sigmoid) and xtt) (tanh), i.c.
f'(1) (() @ f())
21(1)= = 211)
(28)
Now by substituting Eqs. 27 in Eq. 26 we obtain the following forward recursion equation:
(1) (cx - ( (()))
(29)
aF.jj
+ +(aa()) + (cx(1 - 1) =xx ()){{((()) + (()))
Oci (t (t-1)
(30)
FF.j
(e):(0)
Since the sensitivities are initialised by zero, i.e., zero if and only 1 = i, it follows that, for any t,
0, and the additive term in Eq. 29 non
aF.j
dcr(1)
if
k #i.
(31)
OF.,
The other entries (the case where & = i) can be compactly represented using intermediate variables
introduced above (f(t), (t), e(t): Eqs. 12 13 as follows:
@c,(t) (c,(t - - (t))f
DF.
+ (Fi(t) (ci(t 1) (t) + +1 +(()))((((()) (c,
(32)
OF.s
= =(())x((() + (f((t) + ft))/ + (t())))) dc,(t -1) 1) OF.
(33)
= ((()),;(() + c,(() @c,(t -1)
(34)
F
15

---

Published as a conference paper at ICLR 2024
(c,(t)
Finally, by introducing the notation Ft)) e RNDD with (t)
E RR we arrive at
j
Eq. 14 Left. Eq. [4ght for the loss gradients is obtained by simplifying Eq. sum reduces to one term).
25 using Eq. 31 (the
The derivation is similar for Z. We now show the derivation for w'.
Derivation for w.. Starting over, the goal is to compute the following gradient
ac(t)
N
aC(t)
Ocx(t)
Ocx(t) tw!
ex(t)
(35)
ow dck(t) (t)
Ow
The direct differentiation through Eq. 1 yields:
dcx(t) (ca(t 1) (()(()))
(t)
Ocu(t- dc + (1 fa(()) Ozx(t)
fa(l)
(36)
iw!
Ow!
Ow!
ino!
Now, we explicitly compute (t) Ow!
and (zx(t)
which yields:
ow!
(f (1) cx(( 1)lk=i w
dca(t - 1)
(z)(t) (!)w dcu(t 1) Ow!
(37)
iw!
Ow!!
Ow!
Now by substituting Eqs.
37 in Eq.
36 we obtain the following forward recursion equation:
dca(() = (1- (1) 1)T
(38)
tw!
Ock (t (t-1)
(Ia(0) (cu(l ( (z))s)((())) + + (L=Js(0)=(((00))
(39)
One!
Oc - 1)
Similar to the derivation for F, as the sensitivities are initially zero, i.e.,
0, and
Ow
non-zero terms are added only to the entries where it i, it follows that for any t, dcx(()
0 if
Ow!
+ and the non-zero entries are:
dea(l) f(())attt - &((() dc Ow!
a(()
(40)
Ow!
which finally yields Eq. 21
The derivation is almost the same for by, except that, instead of cx 1) in Eq J==-- Finally, the derivations are also similar for w and b²
37 obtain
A.2 TRACTABLE RTRL FOR CERTAIN LINEAR TRANSFORMERS/FAST WEIGHT PROGRAMMERS
While the main focus of this work is to evaluate tractable RTRL using eLSTM, we also discuss that there are several neural architectures with tractable RTRL in the one-layer case. Here we show that RTRL is also tractable for certain "simple" one-layer linear Transformers/Fast Weight Programmers (FWPs: Katharopoulos et al. (2020): (Schmidhuber (199T): [Schlag et al. (202T): [rre al. (202T).
The FWP in question transforms an input (+f) E R to an output y(t) E RV at each time step t, as follows:
[k((). v(), {()) = V<(()) ((I) W (V v()) @ k(I)
(41)
(42)
(t) = W (f)
(43)
where k(t) E RN v(t) E R. q(t) E RN (t) E NNN, with trainable parameters K E NNN V NNN and Q N (we the same dimension N everywhere for simplicity, but the
16

---

Published as a conference paper at ICLR 2024
following derivation remains valid for the general case where ztt) is of dimension D; the only requirement is that (t) and (t) are of the same dimension).
Let ú,j N). Using the same definition of the loss [(t) defined in Sec. 2 the goal is
to compute ac(t) ac(t) ac(t) Since q(t) is not involved in the recurrent loop (here we "K.j V
8Q0j"
are again under the one-layer assumption), the gradients ac(()
aQ.,j can be computed using standard and aC(L)
backpropagation. Hence, we focus on ac(I)
akij VV..j Here we provide the RTRL derivation
for OC(L)
OC(I)
(the derivation for VV.
is analogous). Let 1, m, i and denote positive integers. As in
OK J
Sec. it is practical to write down each element Wi,m(t) E R of (t)) RNNN, well each element km (t) R of k<t) R.V for all 1, {I,..., N):
Wmm (t) Wi, 1) + (t)
(44)
N
(t) Σ km.tta()
(45)
n=1
The goal is to compute the following gradient:
ac(t)
N
OC(t)
OWim(()
(46)
oKij
OW (t)
akij
I=1 m=1
aC(t)
The first factor dWim (t)
be computed using standard backpropagation (no recurrence involved).
We derive a forward recursion formula for the second factor by differentiating Eq. 44
WWim(t (t)
aW (t 1) + (t) 0km
(47)
akis
OKis
0Kijj
Now, differentiating Eq. 45 yields:
m +
0km (t)
0k((1)
(48)
oK,,
a1
Otherwise
Ōkm 0K,,
This last equation a source of complexity reduction: in the 3-dimentional tensor terms are zero, and non-zero component only depends on j. Eq, 47 becomes:
many
m +
OW (t) aKij
ak,, oW 1) + (t)a,((()
(49)
Otherwise
Since the term added at each step, (t) only depends on and j. by introducing a matrix (1)1) N such that, for all I,j (1,..,, NY. (()(1) @Wi,(1) for all (1,...,N) aK, can compactly express the 4-dimensional sensitivity tensor with elements
OWrm (t) using the 2- OK,
dimensional sensitivity matrix with elements (1) through sparsity and parameter-sharing obtained directly consequences of the forward computation of the FWP defined above. Hence, the space complexity of RTRL is reduced to ( Now Eq. 46 greatly simplifies:
OC(t) oK,j
ac(t)
OW,m (t)
aC(t)
OWia(t)
X
(50)
WW (L)
OKis
OW,, OKi,
17

---

Published as a conference paper at ICLR 2024
DC(() (t)) Eq. 50 can be computed through
By defining a matrix E(t) E N such that (t)
one simple matrix multiplication; and Eq. 49 yields a simple forward recursion formula for (t):
aC(t) 0K
((t) (t)
((t) K(t 1) + u(t) @ x(t)
(51)
where denotes transpose. The time complexity of Eq. 51 Left (for one update) is O(N)) which is tractable. The batch version of Eq. Left can be implemented as batch matrix-matrix multiplication in standard deep learning libraries.
The derivation is analogous for V (by analogously defining (tt) which yields:
ac(t) av (())(()) : v(I) - V 1) + k()) @ ax(1)
(52)
In summary, RTRL for this simple FWP is tractable with the time/space complexities O(N-) and ((N3). As for eLSTM (Sec. 5). this result is only valid for the one-layer case. Also note that the standard FWP (see e.g., et al. (202T) applies softmax on both key and query vectors; here we need to remove such an activation function applied to the key (see Eq. 42 to make RTRL tractable.
A "biological" memory system view. The resulting system (consisting of the neural architecture, plus the RTRL learning algorithm) forms an interesting type of memory "organism." The system maintains two kinds of "synaptic" memories in online fashion: the fast weight matrix W(t) is short-term memory where the system stores information required to solve the task at hand (memory based on input observations; Eq. 42), while sensitivity matrices (t) and (t) (paired to the model's weight matrices K (tt and (t)) store another memory required for learning (memory based on external feedback to model outputs; Eqs. 51 and 52 Right).
Remarks. Strictly speaking, RTRL is the name of the learning algorithm when forward-man automatic differentiation (AD) is applied to RNNs. Here we refer to RTRL as generic name referring the forward AD applied any sequence models including linear Transformers. Regarding the standard Transformer: we note that a Transformer anyway needs to store all past activations even for its forward pass, and we are not aware of any straightforward RTRL-like online learning algorithm that leads to complexity reduction of any form (compared to real-time BPTT (Williams & Zipser 1995))
A.3 BACKPROPAGATION THROUGH TIME (BPTT)
In Sec. [ we review RTRL. For the sake of completeness, here we review BPTT using the same notations and settings described in Sec. 2
BPTT can be obtained by directly summing derivatives of the total loss Crotal T) w.r.t. all interme- diate variables & (4) for all l: E (1...., and {1,.... T):
C (1,T)
T
O (1,T) asp(1)
(53)
OW i.j
@s+(t)
(t.
where we introduce the notation 08k(1)
denoting the derivative of & w.r.t. the variable
OW., (.;())
representing the weight W., at time t, W (meaning that 8R (t is constant w.r.t (t)(t) and
thus. @sx(t) is only the first term of ask Eq. i... @t.,(t) (t) This allows (t)
0sx(1)
oW.,
d (1, T)
T deual (1, T) @W.)(T)
us to write gradients w.r.t. the weights at specific time step, e.g.,
OW,j
18

---

Published as a conference paper at ICLR 2024
By introducing the classic notation 8()) E IR with dx(1) = Hluuaal (1,
E forall & (1,..,
(s)(1)
(c) Σ aC(T)
aC(T)
OC(1)
T
0L(T)
Σ
+ Σ
(54)
(tx
(t)
(t)
(sx(t)
r=t+1
0C(1)
N
T
OC(T)
11 ( +1)
Σ
(55)
(ts(t)
0s, (t +
(ts
a=1
r=
T
OC(T)
Since
Σ
(t = 6n (t + 1) in Eq. 55, we obtain the backward recursion formula for 8(t):
r=t+1
aC(t)
0s (t++)
ac(t)
N
(t) (1)
+ Σ
8n +
+ @sk(1)
Σ
dt no',,o (56)
(1x(1)
n=1
n=1
aCinmal (1,T)
T N (+)
0sx(t) aW.
ΣΣ
Σ (t)
(57)
OW
In the end, all quantities involved in these equations can be expressed as matrix-matrix/venn multiplications, element-wise vector multiplications C or outer products between two vectors 6b:
aC(I) 8(t) (s()) L))
OC (1,T)
Σ 8(t) @ xt))
(58)
OW
aLtotl (1,T)
The formula for
aR can be derived analogously. This is the derivation which is obtained
as a "natural" extension of the standard backpropagation algorithm for feedforward networks, by unfolding the RNN over time. BPTT requires to store intermediate activations s(t) E R (and inputs (t) I R) for all t E {1..., T). resulting in the space complexity of O(T(N + D)) ~ O(TN).
C (1, T)
We can only compute the gradients ow
after going through the entire sequence (because of
the backward recursion to compute 8()) Eq. 58 Left). The (per-update) time complexity is O(T
(thus, the corresponding per-step time complexity is O(N2))
Technically speaking, one could also adopt BPTT for online learning (by applying BPTT at each time step; real-time BPTT (Williams & Zipser 1995)). However, this would result in many redundant computations, with time complexity of order of O(T2N2) which is intractable in practice, and more expensive than RTRL's ONN)) for long sequences with T > N.
A.4 A HYBRID BPTT-RTRL METHOD
As discuss in Sec. 5 fully online learning is computationally sub-optimal for certain sequence processing applications as it prevents parallel computation over time. In fact, the sequence-level parallelism is extra advantage of BPTT over RTRL that is not captured by the complexity analysis; even for fully recurrent NNs, many operations can be parallelised over the time dimension (c.g., the linear transformation of the input axt) in Eq 1. When fully online learning is not crucial, hybrid approach (Williams 1989 Schmidhuberr 1992. Williams & Zipser 1995) that combines BPTT and RTRL is more attractive than RTRL to compute untruncated gradients efficiently.
Such hybrid method is a segment-wise online algorithm. The main idea is to chunk sequences into segments, and to process sequences by applying BPTT to each segment while carrying over sensitivitics needed by RTRL segment boundarics to compute untruncated gradients. Here review Schmidhuber (1992)'s 's derivation in the setting of Sec. 2 Let to. f1, K and S be positive integers. In addition to the notations already introduced above (including the notation (t,(t) that Appendix
denotes the variable corresponding to weights W., at specific time step t; introduced A.3), L(t,, & to denote the sum of losses L(t) for t from step to to t, (both inclusive).
The algorithm iterates over segments of length S that constitute the full sequence of length T (naturally, the length of the last segment is shorter than equal to S). At iteration step K
19

---

Published as a conference paper at ICLR 2024
assume that K segments are already processed, i.e., by denoting to K S, three quantities
OC(1, to)
to Σ (sx(to)
(W (t(t and W Wk,s,((t)) (to)
(T) are computed and cached for all i, k E {1, N}
r=1
and E (1,.... DJ. We process the next segment as follows:
OC t0 5) tC( aC(to + +1,00 11.40+30 S)
(59)
oW.s 1.
aW.
The first term is computed by the previous iteration. We need to compute the second term:
ac(to + 1, +
to aC(to + 1,
(60)
aWij
(W.)(T)
actto + 1, + S)
to
aC(to + 1, + S)
(61)
@W.j(T)
(W.
+=
All quantities involved in the second term in Eq. 61 are within the current segment (to + 1, to S).
Thus, this term can be efficiently computed using BPTT (see Appendix A.3)
The first term in Eq. 61 is trickier since need to compute the gradients of the losses in the segment (to + 1, to + S) w.r.t. weight variables from the segment (1, to). This term can be computed through RTRL-style computations:
@C(to + +1,10+ (W
aC(to + 1, S) @su(to)
(sx(
(62)
(T)
We recognise that the first factor (we denote (to)) be computed as function of 5(tg + 1) (see the definition in Eq. (54) already computed by BPTT to compute the second term of Eq. 61 above (almost 8 (to) through the backward recursion of Eq. 56 but without the first term),
(tu) aC(to 1, S) @sx(to)
la+S
OC(t)) @sp(to)
Σ
8n R) (sx (tx()))
(63)
1
Eq. 62 becomes:
to aL(to + 1, +
to
N
OSk (to)
N
to
Osp(to)
(to)
( @W.,(T)
(64)
@W))(T)
(T)
Aml
Amm
@sx(ta) is computed while processing the where assume the last term Wa Σ
(T)
previous segment; this completes the computation of the gradient Eq. 59 i.e., for the last segment, this terminates the algorithm. If the current segment is not the last one, we have compute W Wto + S) needed the next iteration. This can be achieved by the following forward recursion:
Os + S) to (sp + +S) aw (T)
ta+
Osk (to +
WRAS + S)
+
(65)
(W)
@W,)(T)
T=
to
as (lo S) @st(ta)
tots
N
Osu(to +) 0s((T)
(66)
@s1(1o) @Wi)(T)
ds((T) @W.5(T)
1=1
We introduce the notation HT,(T) (t + S) for (to. to +...., + S} which can be
(s: (T)
computed during BPTT in the segment (lo + 1,40 + S) through the following backward recursion:
Hai(T) = o' (s((())
Σ
H Ham (T + 1) Rmm,
(67)
20

---

Published as a conference paper at ICLR 2024
with (tu + 5) 1ffk= and otherwise. Now Eq. 66
be expressed as:
to
@si(to)
as((T)
Wto +5)
Σ
(to
(T.(T)
(68)
(W
(T)
r=to+
N Haa(to)Waas(to)
to+S
+
Σ (z)(())
(69)
-=to11
We remind that (T)
(in the last term of Eq. 68) can be simply computed by differentiating
(T)
(si(T)
Eq.
(T) =r(())(=(). We cache the following quantities process the next segment:
(tu + 5), (to + 5). and ac(1, + + for all i, (1,..., N) and (l,..., D}. aW.s
The space complexity of this algorithm is O(N3), i.e., the same in RTRL, because of W Wa, (f)) to be stored. The time complexity is less than RTRL since it requires the RTRL-like computation of Eq. 669 only once per segment, i.e., only every S steps. Assuming ~ O(N), the per-step time complexity is reduced to O(N3). In addition, this algorithm allows us leverage parallel computation over the time dimension (through BPTT; even though the BPTT part is anyway less expensive than the RTRL part). This hybrid algorithm is conceptually more attractive than the pure RTRL for scenarios where RTRL's fully online learning property is not crucial, e.g., training of language models (as discussed in Sec. and Appendix B.1 actor-critic methods using large M (Sec. 3.2).
A.5 FELSTM ARCHITECTURE
Here we introduce 'fLLSTM architecture that is an LSTM variant involving full recurrence, which the closest to our eLSTM. We introduce this architecture that we can compare our "eLSTM + exact RTRL" system with some fully recurrent RNN trained with an RTRL approximation in Table 2
In fact, careful readers might note that, strictly speaking, such comparison is not "fair" in the sense that we change both the base RNN architecture and the learning algorithm, given that the choice of the base RNN architecture itself influences the performance: we have already shown that eLSTM outperforms LSTTM on these tasks (Table ( To minimize this architectural discrepancy, our fully recurrent architecture, "feLSTM," is obtained by minimally modifying the eLSTM architecture.
"feLSTM" is obtained by replacing the element wise recurrence of eLSTM in Eq. by:
f(1) (FF((() W W'e(l- - 1)) =(1) = tanh Zxx(() + Woe(L - 1))
(70)
where W/ N and a NNN trainable weight matrices. All other equations remain
the same as in eLSTM. Because of this full recurrence, RTRL for this model is not tractable. This allows us compare "eLSTM exact RTRL" v. "feLSTM approximate RTRL (SnAp-1; S:nAp-l:MMnnckk Menick et al. ) in Table while keeping the base RNN architecture as close as possible.
B EXPERIMENTAL DETAILS, EXTRA RESULTS AND REMARKS
B.1 DIAGNOSTIC TASKS
Copy task. Since the main focus of this work to evaluate RTRL-based algorithms beyond diagnostic tasks, we only conduct brief experiments on a classic diagnostic task used in recent RTRL research work focused on approximation methods (Tallec Benzing et al. 2019. Menick et al., 2021 [ilver et al. 2022): the copy task. Let & be positive integer. Sequences in the copy task have a length 26 where the & first symbols are either 0 or 1, and all others are #. The task is to sequentially read symbols in such sequence, and to output the binary pattern presented in the first part of the sequence when reading the sequence of # in the second part. We conduct experiments with l {50, 500}. Unlike prior work (see, e.g.. [Benzing et al. (2019)), do not introduce any curriculum learning; we train models from scratch on the entire dataset containing sequences of length ranging from 2 to 2f. Note that we do not conduct much of pyrer-r
Ollivier) 2018 Mujika et al., 2018
21

---

Published as a conference paper at ICLR 2024
search; we find that for this task, trying few values is enough to find configurations that achieve 100% accuracy. The corresponding hyper- parameersss are as follows. Respectively for = (50, 500), we use 3.3e-)) )), a batch size of (512, 128), and hidden layer size of (1024, 2048). learning rate of (1e +, 3e
We apply a gradient norm clipping of 1.0, and use the Adam optimiser. The model has no input embedding layer; one-hot representations of the input symbols are directly fed to the recurrent eLSTM layer (Sec. (Sec.3.1) [.1]] Since our RTRL algorithm (Sec. 3.I requires no approximation, and the task is trivial, we achieve 100% accuracy provided that the RNN size is large enough and that training hyper- hhper-paraman parameterm are properly chosen. We confirm this for sequences with lengths of up to 1000.
B.2 REMARKS AND LIMITATIONS
Remarks on computational capabilities of eLSTM. As noted in the introduction, eLSTM has certain limitations in terms of computational capabilities. In fact, certain theoretical results/lmitaaiins known for one-layer Quasi-RNN (Merrill et al. (220)) directly apply to eLSTM (and other element- wise recurrent NNs). While we do not observe any empirical limitations on the main tasks of this work (Sec. 4. we find one algorithmic task on which eLSTTM ís not successful (at least we failed to find successful configurations), which is the code execution task (Fan et al. 2020; Iric et al. (021)) While we refer to the corresponding papers for the task description, this task requires the model to maintain dynamically changing values of a certain number of variables. We are not successful at finding any configuration of our eLSTM that achieves 100% sequence-level accuracy this task, while this is straightforward with the standard fully recurrent LSTM (see also Irie et al. (2023)).
Remarks on language modelling and supervised learning. Another popular "diagnostic" task used in recent RTRL research is small-scale language modelling (see, e.g., Beszing et al. (2019)) However, as we already discuss in Sec. 5] in practice, language modelling may not be the best target application of RTRL in modern deep learning (apart from test-time online adaptation, i.e., dynamic evaluation (Mikolov et al. 2010: Krause et al., 2018), maybe). While we also conduct brief language modelling experiments using the Penn Treebank dataset (as in Benzing et al. (2019) in our preliminary studies, we do not find any interesting result (beyond tiny perplexity improvements) that is worth being reported here. Unfortunately, our I-layer architecture too limited to perform well on modern language modelling tasks (dominated by deep models/Tran Transformers) or any other meaningful supervised tasks at scale. If we restrict ourselves to 1-layer models, the task has to be limited to toy setting similar to those used in prior works, contradicting our original objective of "going beyond diagnostic tasks."
As general note, for RTRL to scale beyond toy tasks in supervised learning, it would require an optimised implementation such as a custom CUDA kernel (to be competitive with today's highly optimised TBPTT implementations). This would require further engineering efforts (but also some thoughts on the algorithm too: in Appendix [A.4 we mention the RTRL-BPTT hybrid as a more promising RTRL variant for supervised learning), which we leave for future work.
B.3 DMLAB
Experimental Details. Here we provide details of our DMLab experiments. We use two memory tasks rooms_selle wwt.sseeeeecttnmmcccceceeecc oowhhiingobbbbeeeeoo ject and rooms watermawtraaaaaa ze, and one reactive task room foomm_kys__dorrs puzzzee in Sec. 4 For the corresponding task descriptions and examples of game screenshots, we refer to https://github.com com/ watps//eeees/cee /ttp//ttrbbbtttt/ddmllaaaaaaabae
We use observations based on DMLab's RGB INGERLEVELEEED Our base model architecture IMPALA's deep variant (Espeholt et al. 2018). Action space discretisation is also based on IMPALA (Espeholt et al.) 2018). Note that, unlike our work, some prior work (e.g., R2D2 (Kapturowski et al. (019h) use some "improved" versions of the action space discretisation (Hessel et al. 2019). Regarding the reward clipping. no sophisticated asymmetric clipping (Espeholt et al. 2018 is used but the simple |-1, 1] clipping. Training sypper-parameeers//offgggg
-ont -ow--oooo-----a------ mow.e/eeeeecc--ooottootcnncnnnnn
are listed Table 4 For the memory tasks, pre-training (Sec. 4 is done using TEPTT with M = 100. Our implementation is based on torchbeast (Kittler al.) 2019). We run three main training runs. Each run requires about a day of training V100 GPU (this is also the case with ProcGen and Atari). Also note that DMLab is CPU intensive. For evaluation, we first evaluate the final model checkpoint on three sets of 100 test episodes each;
22

---

Published as a conference paper at ICLR 2024
Table 3: Scores on two memory environments of DMLab-30 for M 10 and M 50.
M
Architecture
Recurrence
Learning Algorithm
select.nenmatch
waternaze
M- =
50
LSTM
full
TBPTT
61.6 0.6
17.2 1 3,0
feLSTM
full
TBPTT
61.4 11.4003 0.3
35.2 +: 3.8
eLSTM
element- wise
TBPTT
61.4 = 0.5
44.5 +
feLSTM
full
SnAP-1
53.5 0.6
24.2 1 2.2
cLSTM
element- wise
RTRL
62.0 0.4
52.3 1.9
M 10
LSTM
full
TBPTT
9.3 = 0.9
15.3 + 2.0
feLSTM
full
TBPTT
51.1 = 1.5
11.4 +
cLSTM element- wise
TBPTT
54.5 = 1.1
15.8 - 0.9
feLSTM
full
SnAP-1
49.2 0.3
24.7
cLSTM
element-wise
RTRL
61.8 = 0.5
40.2 = 5.6
resulting in three mean test scores for each training run. We average these scores to obtain a single mean score for each training run. The final number we report is the mean and standard deviation of these scores across three training runs.
Extra Results. To show that RTRL does not have any unexpected negative impacts in mostly reac- tive task, we also test our system on one environment of DMLab-30, room_keys seeey_ddorrsssoee wpw.ssllzeeee le, which is categorised as a reactive task according to Parisotto et al. (022). We train with M 100 for 100 M steps (with the action repeat of 4) from scratch. The mean episode length is about 450 steps. Table 5 rightmost column shows the scores. Effectively, all feedforward, TBPTT, and RTRL systems perform nearly the same (at least within 100 M steps/400 M frames). We note that these the one reported by the original IMPALA (Espeholt al. 2018) which is 28.0 after training on 1 B frames, which is much worse than the score reported by Kapturowski et al. (2019) for IMPALA trained using 10 frames (54.6).
scores are comparable
Table is similar to Table 2 but for M = 10 and M = 50.
Remarks on Online Learning. A potential benefit of small M is more online learning which could be more sample efficient. At least on DMLab rooms se select nonmat ching ob ject (Figure la vs ld.. we do observe some sample efficiency benefits of RTRL with a small M: at about 2.5 M steps, RTRL with M = 10 achieves a score over 50, while the one with M = 100 is below 40 at the same number of steps. However, if the goal is to obtain the best performing model, our conclusion is that too small M is indeed not good idea (more online learning deteriorates the performance, likely due to sensitivity staling). We note that it is rare that we can conduct such experiments using exact RTRL without worrying about the approximation quality, which is benefit of our framework.
Practical Computational Costs. While our code is not optimised to fully leverage the computa- tional advantages of RTRL,, here provide some insightful numbers regarding the computational costs. Training an RTSTM-RRLL with hidden size N=512, batch size 32 and M=100, using the frozen vision module on rooms cooms_water e rmaze e requires about GB GPU memory (corresponding to our experimental setting of Table I.. This is comparable to that of TBPTT for M=100; in fact the memory requirements of TBPTT for M (100, 50, 100, 300) are respectively: {1.4, 2.9, 4.8, 12} GB (the corresponding empirical law is 0.038 M + 1 GB). Therefore, in order to compute the untruncated gradients as in RTRL using TBPTT for rooms watermaze (simply assuming that M=1000 is needed, as 1000 is the average episode length for rooms watermazer ze), the correspond- ing memory requirement greater than GB. In contrast, RTRL. using only 5 GB allows to compute untruncated gradients and yields good performance (Table [.
Regarding the actual wall clock time (measured on differentiation is bit faster (1900 steps per second) than our httLL//usoom-foowaddddffeeeree
(1250 steps per second) but again, our implementation is not professionally optimised, and leaves much room for improvements (formally, the time complexity of O(MN2) is the same for TBPTT and RTRL applied to our eLSTM, but RTRL requires some extra overheads such as copying large sensitivity matrices extra recurrent states).
23

---

Published as a conference paper at ICLR 2024
Table Hyper-parametert for RL experiments. Parameters at the bottom are common all settings (which are essentially taken from the Atari configuration of Espeholt et al. (2018).
Parameters
DMLab
Atari
Proegen
Input image dimension
3x96x72
1x84x84
3x64x64
4-frame stack
No
Yes
No
Action repeat
4
4
No
RNN dimension
512
256
256
Number of IMPALA actors
48
Discount
0.99
Learning rate Batch size Gradient clipping
0.0006
32
40
Loss scaling factors (baseline, entropy) RMSProp (alpha, epsilon, momentum)
(0.5, 0.01)
(0.99, 0.01, 0)
B.4 PROCGEN
All our experimental settings ProcGen environments are the same as for DMLab described above. except that no action repeat is used (see Table 4 for comprehensive overview). Following (Cobbe
2020), we use 500 levels for training. ct al.
solvable using feedforward policy even without frame-stacking (Cobbe et al. 2020). Note that there is a so-called memory-mode for certain games, making the task partially observable by making the world bigger, and restricting agents' observations area around them. However, as has been already reported in Paischer et al. (2022), we confirm that even in these POMDP settings, both the feedforward and LSTM baselines perform similarly. In our experiments, Chaser is the only ProcGen environment where we observe clear benefits of recurrent policies. our preliminary studies, we also test Caveflyer/hard, Caveftyer/memory. Dodge- bull/memory, Jumper/hard, Jumper/memory, and Maze/memory. However, in these environments, we do not observe any notable benefits of LSSTM-based policies over the feedforward baseline, except some improvements in Dodgeball/memory mode: 10.1 + 0.4 (feedforward) vs. 12.7 + 0.6 (LSTM) on the training set.
Most ProcGen environments
limited
B.5 ATARI
All experimental settings in the Atari environments the same for DMLab described above, except that 4-frame stacking is used (see also T and that we use 5 sets of 30 episodes each for evaluation. As stated the main text, our selection of five environments follows Kapturowski et al. (2019). Regarding other tasks, we also consider Solaris from Atari, as Kapturowski et al. (2019) find longer BPTT spans useful for this task. However, they achieve such improvements by training for 10B environment frames, which are beyond our compute budget (800 M frames is our reasonable number); we tried up to 4 steps, but without observing benefits of RTRL. Similarly, no real benefit of RTRL is observed on Skiing within this number of steps (except that RTRL and Feedforward agents immediately achieve a score around -8987 but remain stuck there forever, while the score TBPTT- based agents gradually increases but only until circa - 17418). Other scores reported in Table
Table 5: Scores Atari and DMLab-reactive (rooms keys doors puzzle) environments.
Breakout
Gravitar
MsPacman
Qebert
Seaquest
Feedforward
234 +
1084 + 54
3020 + 305
7746
1356
4640
3998
26.6 1.1
TBPTT
305 + 29
1269 + 11
3953 = 497
11298 615
12401 1694
26.1 0.4
RTRL
275 + 53
1670 + 358
3346 = 442
12484 + 1524
12862 + 961
26.1 + 0.9
24


Reviews:
[{"review_id": "Vkk3pR9Hr7", "reviewer": "Reviewer_PxbF", "summary": "In this paper, the authors explore the advantages of real-time recurrent learning (RTRL) compared to truncated BPTT in many reinforcement learning settings scoped to memory tasks. They use a variant of LSTM with element-wise recurrence in a singe layer to make RTRL tractable, and show that RTRL does have an advantage over truncated BPTT in these scenarios. They also provide a discussion of the difficulty of using RTRL in multi-layer recurrent networks.", "questions": "- Why does IMPALA with TBPTT+eLSTM do better than standard IMPALA (with LSTM+TBPTT presumably?)\n- Is having a small value of M beneficial for RTRL in any other way? Not clear what the motivation for studying the effect of M is.\n\n## Clarity:\n- The specific tasks the authors test on is not described anywhere in the paper (the Appendix points to a webpage). Having this would help a lot with understanding the tasks used in the paper.\n- The differences between the baseline methods of various variants of IMPALA and R2D2 are not sufficiently described.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "While RTRL is known to be computationally intractable in the general case, there has not been much prior work in exploring if specific architectural choices can help make exact RTRL more feasible and useful. Especially given the potential advantages RTRL could have due to its computational requirements being independent of sequence length unlike many other sequence models. So this work is very timely and relevant to the community, and the use of element-wise recurrence to make exact RTRL feasible is novel to my knowledge. \n\nThe authors demonstrate many tasks where RTRL with this architecture does better than truncated BPTT, which is very interesting given the very limited recurrence used. The discussion of multi-layer RTRL is also significant and useful to the community. Overall, the quality and clarity of the paper are high.", "weaknesses": "- The elementwise recurrence that the authors propose for eLSTM is very similar to that used in IndyLSTM [1], but a comparative discussion and citation is missing.\n- Since exact RTRL computes exactly the same gradient as full BPTT, a specific analysis of why TBPTT rather than BPTT is used in each of the demonstrated tasks would be important to provide context (for e.g. in regards to memory requirements).\n- A discussion/analysis of the computational expressivity of having restricted recurrent and its implications is missing.\n- On a related note, a discussion (or even speculation) of why eLSTM works as well as it does given its limited recurrence would be useful.\n- Certain combinations of baselines are missing: eLSTM with SnAP-1, full BPTT.\n- The clarity of the experiments section could be improved. See below in \"Questions\".\n\n[1] (Gonnet & Deselaers 2019) https://arxiv.org/abs/1903.08023", "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": "bUooBS1mZb", "reviewer": "Reviewer_8WmR", "summary": "This work studies RTRL method on element-wise recurrent neural networks, examined with the actor-critic policy gradient algorithm (R2AC) on reinforcement learning tasks. Although the eLSTM architecture was not first proposed by authors, the connection between element-wise recurrence and RTRL training was first pointed out. The eLSTM, RTRL and R2AC are examined together on several subsets of DMLab-30, ProcGen and Atari-2600 envrionments and outperforms the IMPALA and R2D2 baselines trained on 10B frames.", "questions": "1. The variances shown in Figure 2 across different Atari environments are not consistent. For example, in Gravitar the variance for RTRL is larger than the other two and it’s the opposite in Seaquest. But overall it seems RTRL has a larger variance. Could the authors provide some explanation or intuition for that?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The study of RTRL on element-wise recurrence provides a clean examination condition to study the potential of RTRL learning algorithm. From the provided experimental results the RTRL outperforms TBPTT on eLSTM and other baselines on most of the tasks. \n2. Very clear writing, easy to follow. It is a big strength that the authors provided a thorough analysis of the limitations including multi-layer RTRL, the practicality of RTRL etc.", "weaknesses": "1. Only one element-wise RNN instantiation, namely the eLSTM was provided for comparison. It would be better to show the generality of the method on some other element-wise RNN instantiations.\n2. The experiments are conducted on reinforcement learning tasks, which is fine as it is stated clearly as the study goal. However, it would be much more convincing if it is shown with certain supervised learning tasks.", "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": "J23ngJaa4t", "reviewer": "Reviewer_nFUx", "summary": "Real-time recurrent learning enables computing gradients in RNNs as the input sequence is processed. However, its complexity makes it impractical in realistic scenarios. In this work, the authors introduce a new version of the LSTM architecture for which RTRL is exact and cheap. They test the resulting algorithm in realistic RL tasks and show that it performs competitively to alternatives (TBPTT as well as approximations of RTRL on more standard LSTM architectures).\n\n**After rebuttal**: After clarifications from the author, I would like to increase my score from 5 to 7. Given that 7 does not exist, I updated it to 6.", "questions": "The paper focuses on one layer, but mentions that multiple layers are key in deep learning. Would the experimental results presented here would benefit from RNNs with multiple layers? From the vision module being fine-tuned?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper studies in depth the known, yet underappreciated, fact that RTRL becomes much cheaper when recurrence is element-wise. The paper nicely cites early references containing similar insights. The empirical results show that it is better to change the architecture so that RTRL becomes exact, rather than approximating it to make it tractable.", "weaknesses": "I see three main weaknesses:\n\n- Most of the experimental results (all except baseline comparison) seem to some extent obvious to me: the only difference between TBPTT to RTRL is an extended context length. It is thus not surprising that RTRL > TBPTT in all experiments. The context length for TBPTT is relatively short (it seems far smaller than the one modern GPUs would offer) so those experiments do not seem to answer the question:\n    > In what scenarios would RTRL be able to replace BPTT in today’s deep learning?\n    \n    asked by the authors. Adding a baseline that uses as much context length as possible would help better contextualize the findings of the paper. To me, this is the main weakness of the paper, and fixing it may require substantial changes.\n    \n- The paper is missing a few relevant references:\n    - Bellec et al. 2017: RTRL from a computational neuroscience perspective. One of the main contributions of the paper is to discuss how RTRL can be implemented biologically through eligibility traces.\n    - Gupta et al. 2022: show that it is possible to parametrize some classes of linear RNNs (more precisely linear SSMs) diagonally, without losing too much performance. Orvieto et al. 2023, which is cited in this paper, build on this result.\n    - Zucchet et al. 2023: show that spatial backpropagation combined with element-wise complex-valued recurrence enables learning multilayer networks with a performance close to the one of BPTT.\n- The paper mentions the multilayer case as an important limitation but does not discuss any possible or existing solutions (layer-wise training of Javed et al. 2023 / spatial backpropagation of errors of Zucchet et al. 2023)", "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": "hhTMFxgKnJ", "reviewer": "Reviewer_cmdn", "summary": "The authors explore the practicality of RTRL as a method for learning in RNNs. In particular, the authors consider an RNN architecture whereby RTRL is relatively cheap to employ, and demonstrate its advantages over standard truncated BPTT on a range of reinforcement learning tasks.", "questions": "- The authors suggest that their work shows tractable RTRL in Quasi-RNN (Bradbury et al. 2017) and Simple Recurrent Units (Lei et al. 2018). I understand this for the latter, since as far as I understand the eLSTM is just a one-layer instance, but I don't understand this for Quasi-RNN. Doesn't this architecture use convolutions? Does that also mean that RTRL has a space/time complexity of N^2?\n- The authors state that, \"in practice, it is known that M > 1 is crucial (for TD learning of the critic) for optimal performance\". Is this true? My belief was that one-step TD learning was frequently employed. Is there a relevant citation?\n- How were the hyperparameters (Table 5) selected?\nTypos: \n- Mozer (1989; 1991) already explore an RNN -> Mozer (1989; 1991) already explored/s an RNN\n- several modern RNN architectures such Quasi-RNN -> several modern RNN architectures such as Quasi-RNN", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- paper is generally well written\n- though RTRL has now been around for some decades, its practical applications remain unclear. Towards this end the authors do offer interesting results which should be interesting to the broader ML community\n- the RNN architecture based on element-wise application the authors use, though not novel itself, offers an interesting avenue for making RTRL more practical", "weaknesses": "- One concern I have is that the authors do not convincingly demonstrate the benefit of their model compared to the status quo, which is a fully connected RNN + truncated BPTT. In terms of complexity, the authors do reduce the memory/computational cost on pointwise RNNs to order N^2 which is certainly better than RTRL on standard RNNs, but this is still as expensive as BPTT on a fully connected RNN. In fact, for a pointwise RNN I wonder if BPTT is in fact of order N (as the forward pass?) - so still cheaper than RTRL - but I may be incorrect there. In terms of performance, the authors show that eLSTM + RTRL outperforms truncated BPTT on all RNN arhitectures for one task (watermaze) which is impressive, but I would have liked to seen this for more tasks; e.g. can RTRL outperform fully connected RNN + BPTT on any of the 5 Atari tasks in Fig 2?\n- Related to the above, it is not clear whether online learning has any intrinsic benefits for performance. The authors note that online learning \"allows for updating weights immediately after consuming very new input\", but in practice the weights are only updated at the same rate as truncated BPTT (at rate M) to avoid 'sensitivity matrix staling'. I appreciate this is a difficult question to answer, and I believe this shortcoming is mentioned as the last presented limitation, but I think this deserves more direct clarification/exploration given the subject of this work.  \n- All main results presented are with respect to performance in reinforcement learning (RL) tasks, but what about supervised learning tasks? e.g. sequence modeling in language. The authors do use the 'copy task', which is a supervised learning task, as a diagnostic task, but I would have liked to see comparisons with BPTT for hard supervised learning tasks. Or at least a rational for only considering RL tasks\n- The connection to biology and the 'memory' trace (e.g. Eqs 12-14) is interesting but not presently quite vague/weak. Some references to biological evidence for such traces (e.g. eligibility traces) would be advised.\n- Given this is a paper which explores the practical/emperical outcomes of RTRL, I would advise a more thorough analysis of the ideal conditions for RTRL. For example, why do the authors believe RTRL is only valuable in some of the 5 Atari environments in Fig 2? For what types of task would RTRL be ill-advised? The space for technical description and equations in the main text is significant (e.g. equations 8-14) and in general I believe this should be in part sacrificed (to the Appendix) for more intepretability of the results.", "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 (poster)