Research map / Reinforcement learning / MDPs and planning
Recurrent Reinforcement Learning with Memoroids
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces memoroids, a monoid-based framework unifying efficient linear recurrent memory models, plus tape-based batching (TBB) that removes segment-based truncated BPTT for recurrent RL.
Problem
Recurrent RL under partial observability is usually trained with segment-based batching (truncated BPTT), which truncates gradients, wastes compute on zero padding, and complicates recurrent losses; efficient linear recurrent memory models have not been unified or batched without segments.
Approach
Observes that recurrent updates of efficient memory models obey the associative (monoid) property, defines a memoroid (monoid plus input/output maps) enabling parallel scans, adds a resettable monoid transformation for inline episode resets, and uses it to batch whole episode tapes without segments.
Key results
- TBB improves sample efficiency over SBB across nearly all tested POPGym model/task configurations, including with SBB segment length L=100 (Figure 4, Appendix A).
- In FFM on Repeat Previous, roughly 90% of the Q value is produced outside SBB segment boundaries, and VML spans the full episode while RML is 10 (Figure 3).
- Memoroid discounted return and GAE computation are roughly three orders of magnitude faster than the standard serial implementation (Figure 5).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace Segment-Based Batching with Tape-Based Batching | recurrent RL with S5, LRU, FFM, or LinAttn · POPGym tasks | sample efficiency | Helped |
| use longer SBB segment lengths instead of shorter lengths | recurrent RL · POPGym tasks | evaluation return | Helped |
| replace SBB with TBB | recurrent RL on Repeat First · Repeat First | train time (s): 886.25 -> 886.87 | No clear effect |
| compute discounted returns with the memoroid implementation instead of the standard iterative approach | discounted return computation · variable-length episode batches | runtime | Helped |
Surprising findings
- Learned recurrent Q functions depend on observations far beyond the environment's reward memory length, even when trained with TBB, indicating memory models fail to ignore uninformative history.
- Wall-clock training time is indistinguishable between TBB and SBB despite TBB's theoretically higher O(log B) scan cost.
Limitations
- TBB has O(log B) scan cost versus SBB's O(log L), which could matter for very long sequences such as in-context RL.
- Experiments focus on POPGym long-term memory tasks; Atari results are limited to three seeds and do not test many environments.
- Memoroid-based TBB is likely intractable for RNN or Transformer memory models, so benefit is tied to linear recurrent models.
Experimental setup
Datasets: POPGym Arcade Learning Environment (Atari)
Benchmarks: POPGym Atari (ALE)
Metrics: episodic return sample efficiency Value Memory Length Reward Memory Length wall-clock time
Baselines: Segment-Based Batching (SBB) with L=10 SBB L=20 SBB L=50 SBB L=100 SBB L=80 (Atari) Serial discounted return computation
Builds on: Double DQN Dueling DQN Truncated BPTT S5 Linear Transformer Fast and Forgetful Memory Generalized Advantage Estimation
Closest papers by meaning
- Rethinking Transformers in Solving POMDPs (ICML 2024 · similarity 0.87)
- Stable Hadamard Memory: Revitalizing Memory-Augmented Agents for Reinforcement Learning (ICLR 2025 · similarity 0.87)
- Memo: Training Memory-Efficient Embodied Agents with Reinforcement Learning (NeurIPS 2025 · similarity 0.87)
- Efficient Recurrent Off-Policy RL Requires a Context-Encoder-Specific Learning Rate (NeurIPS 2024 · similarity 0.87)
- Mastering Memory Tasks with World Models (ICLR 2024 · similarity 0.87)
- Real-Time Recurrent Reinforcement Learning (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.