  Memory models such as Recurrent Neural Networks (RNNs) and Transformers
address Partially Observable Markov Decision Processes (POMDPs) by mapping
trajectories to latent Markov states. Neither model scales particularly well to
long sequences, especially compared to an emerging class of memory models
sometimes called linear recurrent models. We discover that we can model the
recurrent update of these models using a monoid, leading us to reformulate
existing models using a novel memory monoid framework. We revisit the
traditional approach to batching in recurrent RL, highlighting both theoretical
and empirical deficiencies. We leverage the properties of memory monoids to
propose a batching method that improves sample efficiency, increases the
return, and simplifies the implementation of recurrent loss functions in RL.
