linear-recurrent-memory-pomdp-rl

name	linear-recurrent-memory-pomdp-rl
description	Theoretical justification for why linear recurrent neural networks work as memory units in partially observable RL. Constructs linear filters that reproduce HMM belief logits and achieve vanishing state-decoding error under near-deterministic transitions.

Linear Recurrent Memory in POMDP RL

Paper: arXiv:2605.31261 | Submitted: 29 May 2026

Authors: Yike Zhao, Onno Eberhard, Malek Khammassi, Ali H. Sayed, Michael Muehlebach

Core Concept

This work provides theoretical justification for the empirical success of linear recurrent neural networks (LRNNs) as memory units in partially observable reinforcement learning (POMDPs). It constructs two linear filters that mathematically explain LRNN effectiveness.

Key Results

1. Filter 1: Exactly reproduces pre-softmax logits of HMM belief vector → sufficient statistic for optimal policy
2. Filter 2: Achieves vanishing state-decoding error under nearly deterministic transitions → reduces state ambiguity to near zero

Mathematical Framework

1. Hidden Markov Model (HMM) Setup

State: s_t ∈ S (hidden)
Observation: o_t ∈ O (observed)
Transition: P(s_t | s_{t-1})
Emission: P(o_t | s_t)

Belief vector b_t = P(s_t | o_1, ..., o_t)

2. Linear Filter Construction

Filter 1 (Exact Belief Reproduction):

For deterministic transition matrix T:

ℓ_t = T^{-1} · ℓ_{t-1} + f(o_t)

where ℓ_t reproduces exact pre-softmax logits of belief.

This ℓ_t is a sufficient statistic for optimal policy π*(a|ℓ_t).

Filter 2 (Vanishing Decoding Error):

For nearly deterministic T (high diagonal probability):

e_decoder → 0 as T → deterministic

State ambiguity reduced to near zero.

3. Action-Controlled Extension

For POMDPs with action-dependent transitions:

T(a): transition matrix conditioned on action a
ℓ_t(a) = T(a)^{-1} · ℓ_{t-1} + f(o_t, a)

Linear filter becomes time-varying with action-dependent dynamics.

Why Linear RNNs Work

Sufficient Statistics Property

LRNNs approximate the belief vector computation:

• Linear recurrences can reproduce HMM belief logits
• Belief is optimal memory for POMDP decision making
• Linear structure preserves this information

Near-Deterministic Case

When environment transitions are nearly deterministic:

• LRNNs achieve near-perfect state decoding
• Memory requirements minimal
• Linear sufficient for state tracking

Implementation Guidelines

1. Linear Recurrent Unit Design

h_t = A · h_{t-1} + B · x_t
output = C · h_t

• A: Transition dynamics matrix (approximate HMM transition inverse)
• B: Observation embedding
• C: Policy readout

2. Key Design Principles

1. Match transition structure: A should approximate T^{-1} of environment
2. Observation encoding: B transforms observations to filter updates
3. Dimension: State space cardinality determines hidden dimension

3. Training Considerations

• LRNNs can be trained via standard RL (policy gradient, actor-critic)
• Linear structure enables efficient optimization
• No need for complex nonlinear memory

Applications

Primary Use Cases

1. POMDP RL - partially observable environments
2. Recurrent policy networks - memory-efficient architectures
3. Belief-based planning - optimal decision making under uncertainty
4. Efficient RL architectures - reduced computational complexity

When to Use Linear Recurrent Memory

• Partially observable environments
• Near-deterministic dynamics
• Need for efficient, interpretable memory
• Belief-based decision making

Related Architectures

• Mamba/SSMs: Linear recurrent state-space models
• Linear Transformers: Linear attention mechanisms
• RWKV: Receptance Weighted Key Value

Performance Insights

From paper experiments:

• Linear filter serves as strong feature extractor
• Matches or exceeds nonlinear RNN performance in tested games
• More efficient than LSTM/GRU for near-deterministic POMDPs

Activation Keywords

• linear recurrent memory RL
• POMDP belief tracking
• sufficient statistic RL
• state decoding error
• HMM belief vector
• linear RNN theory
• recurrent memory justification

Related Skills

• [[efficient-tdmpc]] - Model-based RL with memory
• [[precise-sde-consistent-rl-flow-matching]] - Flow matching RL
• [[rat-randomized-advantage-transformation]] - Policy optimization

References

• Paper: arXiv:2605.31261 - "Why Linear Recurrent Memory Works in Partially Observable Reinforcement Learning"
• HMM theory: belief vector computation
• Linear RNN architectures: Mamba, RWKV, Linear Transformers

---

Category: reinforcement-learning, POMDP, recurrent-memory, theoretical-RL