🤖 machine learning

Streaming Reinforcement Learning under Partial Observability with Real-Time Recurrent Learning

This paper introduces recurrent trace units, a diagonal recurrent architecture that enables exact real-time recurrent learning with linear complexity, allowing streaming reinforcement learning agents to effectively handle partial observability and long-term dependencies without relying on replay buffers or batched updates.

Original authors: Noah Farr, Aryaman Reddi, Carlo D'Eramo, Jan Peters

Published 2026-05-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Noah Farr, Aryaman Reddi, Carlo D'Eramo, Jan Peters

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to navigate a maze, but you have two very strict rules:

No Notebooks: The robot cannot look back at its past experiences. It must learn from the current moment only, then immediately forget the data.
Blindfolded: The robot cannot see the whole maze at once. It only sees a tiny slice of the world right in front of it, so it has to remember what happened a few seconds ago to make sense of the present.

This is the challenge the paper tackles: Streaming Reinforcement Learning under Partial Observability.

Here is the breakdown of their solution using simple analogies.

The Problem: The "One-Step" Memory Gap

Most modern AI learns by looking at a "replay buffer"—a giant notebook where it stores thousands of past moves to study later. But in the real world (like a self-driving car or a robot on a factory floor), you often can't store that much data. You have to learn "on the fly," one step at a time. This is called Streaming.

When the robot is also "blindfolded" (partially observable), it needs to remember the past to understand the present. Usually, AI does this by looking back a few steps in its history. But if you can't store the past, you can only look back one step.

The Analogy: Imagine trying to solve a mystery where you can only ask, "What happened right now?" If the clue you need happened 10 steps ago, you are stuck. The paper calls this the "one-step gradient horizon," and it causes the AI to fail at tasks requiring long-term memory.

The Old Solution: The Expensive Calculator

There is a mathematical method called RTRL (Real-Time Recurrent Learning) that can remember everything perfectly without a notebook. It calculates how every single past step affects the current moment.

The Problem: Doing this math is incredibly heavy. For a standard AI brain, the calculation grows so fast (like a snowball turning into an avalanche) that it becomes impossible to run in real-time. It's like trying to solve a Sudoku puzzle in your head while running a marathon.

The New Solution: The "Diagonal" Shortcut

The authors found a clever way to make this heavy math light. They used a specific type of neural network layer called RTU (Recurrent Trace Units).

The Analogy: Think of a standard AI brain as a busy city where every street connects to every other street. To calculate the traffic flow (gradients), you have to check every single intersection.
The RTU Trick: The RTU changes the city layout so that every street only connects to itself. It's a "diagonal" road system. Because the connections are so simple, the math becomes fast and easy (linear time), allowing the robot to do the perfect "remember everything" calculation in real-time without a notebook.

How They Put It Together

The team took existing "Streaming" algorithms (which learn one step at a time) and swapped in these special RTU layers.

The Result: The robot can now learn from a single stream of data, remember long chains of events, and figure out what to do even when it can't see the whole picture.

The Evidence: Did It Work?

The paper tested this on three types of challenges:

The "Memory Chain" Test: Imagine a game where you have to remember a secret number given 100 steps ago.
- Old Streaming AI: Forgot the number after about 16 steps.
- New AI: Remembered it perfectly up to 64 steps. It proved that the "shortcut math" (RTRL) was the key, not just the architecture.
The "POPGym" Memory Games: These are logic puzzles requiring the AI to remember patterns over time.
- Result: The new streaming method solved all five puzzles just as well as the "notebook" methods (batched PPO) that store past data.
The "Blindfolded" Robot (MuJoCo): They tested a robot that had to walk but couldn't see its own speed or position (it had to guess based on memory).
- Result: The streaming robot learned to walk, recovering a large chunk of the performance of the "notebook" robots, even though it never looked back at old data.

The "Staleness" Issue (A Minor Flaw)

The paper also noticed a small side effect. Because the robot is learning while it moves, the math it uses to remember the past is slightly "stale" (like reading a map that was drawn a second ago, while the terrain has already shifted slightly).

They measured this "staleness" and found a mathematical "correction" (a Taylor correction) that makes the map more accurate, reducing the error significantly.

Summary

The paper doesn't claim this is the absolute best AI for every job. Instead, it claims to have closed a specific gap: It proved you can teach an AI to remember long-term events and handle "blindfolded" situations without using a memory notebook. It does this by using a special, lightweight math trick (RTU + RTRL) that makes perfect memory possible in real-time.

Technical Summary: Streaming Reinforcement Learning under Partial Observability with Real-Time Recurrent Learning

Problem Statement

Streaming Reinforcement Learning (RL) is an online learning paradigm where an agent updates its policy or value function from each incoming sample immediately, without maintaining a replay buffer or using batched updates. While recent work has successfully scaled streaming RL to deep function approximation in fully observable environments using eligibility traces, extending this to partially observable settings (POMDPs) has remained an open challenge.

In partially observable environments, agents must rely on recurrent architectures to maintain a hidden state that captures historical context. However, standard recurrent learning methods face a trade-off in the streaming setting:

Truncated Backpropagation Through Time (TBPTT): In a single-sample update setting, TBPTT collapses to a one-step horizon (TBPTT(1)). This provides only a one-step gradient, which is insufficient for credit assignment over long temporal dependencies.
Real-Time Recurrent Learning (RTRL): RTRL maintains forward-mode gradients incrementally, making it theoretically ideal for streaming. However, for general recurrent architectures (like GRUs or LSTMs), RTRL has prohibitive computational complexity, scaling quartically ( $O(n^4)$ ) with the hidden dimension $n$ .

The paper addresses the gap between the need for long-horizon credit assignment in POMDPs and the computational constraints of streaming updates.

Methodology

The proposed method integrates Recurrent Trace Units (RTUs) with exact Real-Time Recurrent Learning (RTRL) into existing streaming RL algorithms.

Core Architecture: Recurrent Trace Units (RTUs)

RTUs are a diagonal, complex-valued recurrent architecture. Unlike general recurrent units, an RTU layer is defined by:
$h_t = \Lambda h_{t-1} + W x_t$
where $\Lambda$ is a diagonal matrix with complex entries $\lambda_k = r_k(\cos \Omega_k + i \sin \Omega_k)$ . Because each hidden unit connects only to itself (diagonal recurrence), the gradient computation simplifies significantly. This structure allows exact RTRL to be computed with linear time and memory complexity relative to the parameter count, avoiding the $O(n^4)$ bottleneck of standard RTRL.

Integration with Streaming RL

The authors insert a single RTU layer between the observation encoder and the feedforward head (value or policy) of standard streaming algorithms (specifically QRC( $\lambda$ ) for value-based and stream AC( $\lambda$ ) for policy-based control).

The update mechanism involves two distinct traces that compose naturally:

Eligibility Traces: Standard temporal credit assignment traces ( $z_t$ ) used in streaming RL to accumulate gradients over time ( $z_t = \gamma\lambda z_{t-1} + g_t$ ).
RTRL Traces: Forward-mode sensitivity matrices ( $S_t = \partial h_t / \partial \psi$ ) maintained by the RTU layer to propagate gradients through the recurrent state.

Gradient Computation Strategy:

Recurrent Parameters ( $\psi$ ): Gradients are computed using the exact RTRL trace $S_t$ , updated forward at every step.
Head Parameters ( $w$ ): Standard backpropagation is used as there is no temporal dependency.
Encoder Parameters ( $\theta$ ): To avoid the prohibitive cost of maintaining exact traces through a deep encoder, the authors use a one-step approximation. The encoder is credited only for its immediate effect on the current hidden state, ignoring its influence through past states. This is a necessary approximation for deep encoders in the streaming regime.

Staleness Analysis and Correction

The paper acknowledges that under streaming updates, parameters $\psi$ change at every step. Consequently, the RTRL sensitivity matrix $S_t$ accumulates Jacobians evaluated at outdated parameters, leading to "staleness."

The authors derive a theoretical bound on this staleness error, showing it scales linearly with the step size and the credit-assignment horizon.
They propose a first-order Taylor correction to the sensitivity update. By approximating the change in the immediate Jacobian based on the parameter update $\Delta \psi$ , they reduce the staleness error from $O(\eta)$ to $O(\eta^2)$ .

Key Contributions

Algorithm: A streaming deep RL algorithm for partially observable environments using RTUs trained with exact RTRL. It requires no replay buffer and no batched updates.
Diagnostic Validation: A MemoryChain experiment demonstrating that this combination sustains credit assignment over chain lengths (up to 64 steps) where streaming baselines using feedforward networks, GRUs, or RTUs with TBPTT(1) collapse.
Empirical Performance: Evidence on five POPGym memory tasks and partially observable MuJoCo continuous control tasks showing the streaming approach is competitive with batched PPO, solving all POPGym tasks and recovering a substantial fraction of batched performance on MuJoCo.
Staleness Analysis: A quantitative analysis of RTRL sensitivity staleness under streaming updates, providing a steady-state error bound and demonstrating the efficacy of a first-order Taylor correction in tightening this bound.

Experimental Results

MemoryChain (Credit Assignment Horizon)

On a diagnostic task requiring the agent to recall a binary cue after $L$ steps:

Baselines: Feedforward networks, GRUs with TBPTT(1), and RTUs with TBPTT(1) all collapsed to near-zero returns for chain lengths $L > 16$ .
Proposed Method: RTU with exact RTRL maintained high performance up to $L=48$ and remained competitive up to $L=64$ . This confirms that the gradient method (RTRL), not just the architecture, is the critical factor for long-horizon credit assignment in streaming.

POPGym (Discrete Memory Tasks)

Evaluated on five tasks (Autoencode, Concentration, CountRecall, HigherLower, RepeatFirst):

Two streaming variants (QRC( $\lambda$ )-RTU and stream AC( $\lambda$ )-RTU) were compared against a batched PPO-RTU baseline.
The two streaming methods were complementary: stream AC( $\lambda$ )-RTU succeeded on three tasks where QRC( $\lambda$ )-RTU failed, and vice versa.
Result: Together, the streaming methods solved all five tasks, matching the performance of batched PPO without storing past trajectories.

Masked MuJoCo (Continuous Control)

Evaluated on locomotion tasks (Ant, HalfCheetah, Hopper, Walker2d) with masked velocities or positions:

The streaming method (stream AC( $\lambda$ )-RTU) was competitive with batched PPO-RTU on several tasks (e.g., matching on HalfCheetah-P, outperforming on Walker2d-V).
While it trailed batched PPO on some tasks (e.g., Walker2d-P), it recovered a substantial fraction of the batched performance, demonstrating feasibility for continuous control under partial observability without replay buffers.

KMemoryChain (Staleness Quantification)

A variant of MemoryChain designed to continuously exercise the RTRL trace:

Staleness was measured as the $\ell_2$ distance between the online sensitivity matrix and a reference recomputed with current parameters.
Staleness increased with the memory horizon $K$ , consistent with theoretical bounds.
The Taylor correction significantly reduced staleness, particularly at longer horizons ( $K=16$ ), and corresponded to faster learning and more stable training curves in the high-staleness regime.

Significance and Claims

The authors explicitly state modesty regarding their claims:

No State-of-the-Art (SOTA) Claim: They do not claim to achieve the absolute best performance on any single benchmark compared to unconstrained batched methods.
Primary Contribution: The significance lies in closing the gap between streaming RL and partial observability. They demonstrate that it is possible to perform deep RL in POMDPs with the strict constraints of streaming (no replay buffer, single-sample updates) by combining RTUs with exact RTRL.
Applicability: The method is positioned for scenarios where resource constraints are real, such as on-device learning, real-time control, and lifelong learning, where storing past trajectories is impractical.

The paper concludes that while the gap to batched performance remains in some continuous control tasks, the proposed method successfully extends the streaming paradigm to complex, partially observable environments, validating the viability of exact RTRL with linear complexity in deep RL.