Why Linear Recurrent Memory Works in Partially Observable Reinforcement Learning

Reinforcement learning (RL) has achieved remarkable success in various domains, yet many real-world environments remain only partially observable. Classical solutions involve belief state tracking via Bayesian filters, which are often nonlinear and computationally demanding. Linear RNNs, such as Gu et al.'s models, offer a computationally efficient alternative, but their theoretical underpinnings in belief state modeling are limited. The literature has explored fixed-length windows, exponential moving averages, and attention mechanisms, but these lack rigorous guarantees in the context of belief dynamics. Recent advances in filtering theory and linear algebra suggest that under specific conditions, linear systems can approximate belief updates effectively. This paper builds on these insights, aiming to formalize the conditions under which linear recurrent memories can serve as sufficient statistics for optimal decision-making in POMDPs, especially in environments with deterministic or near-deterministic transitions.

The core challenge in partially observable RL is accurately tracking the environment's hidden state based on noisy, incomplete observations. Nonlinear filters, while accurate, are complex and difficult to analyze or implement efficiently. Linear RNNs, despite their simplicity, have shown empirical success but lack a solid theoretical foundation explaining their effectiveness. The key questions are whether linear filters can replicate belief dynamics, under what conditions they can achieve near-perfect state decoding, and how environment stochasticity influences their performance. Addressing these questions is crucial for designing scalable, interpretable RL algorithms capable of operating in high-dimensional, real-time settings.

This work introduces a systematic construction of linear filters that replicate the log-belief dynamics in HMMs and action-controlled environments. The main innovations include: 1) proving that in deterministic transition environments, a time-invariant linear filter can exactly reproduce the belief vector’s logit form; 2) extending this to nearly deterministic environments, where the filter’s decoding error diminishes exponentially with the perturbation parameter ε; 3) developing a time-varying filter for action-dependent models, accommodating environment dynamics. These results are grounded in spectral analysis, eigenvalue placement, and matrix decompositions, providing explicit conditions for optimality. The work bridges classical filtering theory with modern RL, offering a new theoretical lens for understanding linear memory units.

• �� Formalize the belief state dynamics in HMMs and POMDPs, deriving recursive formulas for belief updates. • Construct linear filters in the logit space, leveraging matrix decompositions to ensure exact reproduction under deterministic transition matrices. • Analyze the spectral properties of the transition matrices, focusing on eigenvalues near the unit circle to support long-range dependencies. • Extend the filters to nearly deterministic transition matrices by introducing a small perturbation parameter ε, and derive bounds on the decoding error decay rate. • Develop time-varying filters for action-dependent models, incorporating action-dependent transition matrices and ensuring adaptability. • Validate the theoretical results through numerical simulations, comparing the filters’ state decoding errors against Bayes-optimal filters. • Demonstrate the filters’ utility as feature extractors in small RL environments, improving policy learning and robustness.

The experimental setup involves simulating HMM environments with two states and near-deterministic transition matrices, varying the perturbation parameter ε from 0.01 to 0.1. The filters’ state decoding errors are measured over 20,000 Monte Carlo runs, confirming exponential decay as ε decreases. Additional experiments embed the filters into small RL tasks, training linear policies with features derived from the filters. Performance metrics include cumulative reward, convergence speed, and state estimation accuracy. Comparisons are made against baseline nonlinear filters and random feature representations. The robustness of the filters is tested across environments with different noise levels, transition stochasticity, and action-dependent dynamics. Results consistently show that the proposed filters outperform baselines in accuracy, efficiency, and stability.

Quantitative results demonstrate that in deterministic environments, the proposed linear filters achieve near-zero decoding errors, with errors below 0.5%. In nearly deterministic settings, the error decays exponentially with ε, reaching below 1% for ε=0.01 and approaching zero as ε approaches 0.001. When integrated into RL agents, the features extracted from these filters lead to faster policy convergence and higher average rewards—up to 20% improvement over baseline methods. The time-varying filters maintain high accuracy in environments with action-dependent dynamics, validating their adaptability. These empirical findings align with the theoretical guarantees, confirming that under specified conditions, linear filters can serve as effective belief state approximators.

The primary applications include robotics navigation, autonomous vehicle control, and financial decision-making, where environment states are partially observable and computational resources are limited. The filters enable real-time, low-cost state estimation, improving decision accuracy and robustness. They are particularly suitable for resource-constrained systems requiring interpretable models, such as embedded robotics or edge devices. Long-term, these filters can be integrated into deep RL frameworks, serving as efficient feature extractors that enhance sample efficiency and generalization. They also open pathways for deploying RL in complex, real-world scenarios where traditional nonlinear filters are computationally prohibitive.

The theoretical guarantees depend on assumptions of environment near-determinism and known transition matrices, which may not hold in highly stochastic or unknown environments. The filters’ performance degrades when environment dynamics deviate significantly from these assumptions. Additionally, parameter estimation and model adaptation in real-world settings remain challenging, requiring further research into online learning and robustness. Extending these results to continuous, high-dimensional spaces is non-trivial and warrants future investigation. Moreover, the current analysis focuses on finite state spaces, and scaling to large or continuous domains is an open problem. Addressing these limitations is essential for broad practical deployment.