Research map / Reinforcement learning / MDPs and planning
Partially Observable Reinforcement Learning with Memory Traces
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 memory traces (exponential moving averages of observations) as a compact history feature for partially observable RL, with sample-complexity analysis versus length-m windows and experiments in random walk TD learning and T-maze PPO.
Problem
Learning in partially observable environments requires long histories, but windows of recent observations become intractable as window length grows; the paper seeks a tractable, sample-efficient history representation.
Approach
Represent history as a memory trace, an exponential moving average of observations z_t = λ z_{t-1} + (1-λ) y_t; show it is injective for λ<1/2 (equivalent capacity to windows) and that Lipschitz functions of traces can be much more sample-efficient than windows for slow forgetting (λ≥1/2), e.g. in the T-maze.
Key results
- In Sutton's noisy random walk with linear TD, memory traces significantly outperform the full length-m window over 100 seeds.
- In the T-maze (corridor length 8), PPO with memory traces learns the task while frame stacking with window length k is outperformed when long memory is required (averaged over 50 seeds).
- Theory: window and trace classes are equivalent in capacity for lambda<1/2 (Lipschitz-trace entropy matches window entropy up to constants), while for lambda=(k-1)/k the T-maze requires window entropy Omega(|Y|^k) versus O(k^(|Y|-1)) for traces.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use memory traces instead of a full length-m window | TD learning with linear function approximation · Sutton noisy random walk | return error | Helped |
| Use a concatenated length-m observation window instead of exponential weighting | TD learning with linear function approximation · Sutton noisy random walk | return error | No clear effect |
| Use two parallel memory traces instead of frame stacking | PPO · T-maze (corridor length k = 8) | success rate | Helped |
Surprising findings
- Injectivity of the memory trace can fail for irrational lambda or infinite histories when lambda>=1/2, with explicit counterexamples.
Limitations
- Theory restricted to offline on-policy evaluation with one-hot observations and Lipschitz function classes.
- Characterizing solvability of environments via transition/emission probabilities is left open.
- Experiments are small-scale (random walk, Minigrid T-maze).
Experimental setup
Datasets: Sutton's noisy random walk (1001 states, 11 observations) T-maze (Minigrid version, corridor length 8)
Benchmarks: Sutton's noisy random walk T-maze (Minigrid)
Metrics: return error average success rate
Baselines: length-m window (full window) frame stacking memoryless policy (lambda=0)
Builds on: eligibility traces frame stacking proximal policy optimization Kirszbraun's theorem
Closest papers by meaning
- Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy (NeurIPS 2024 · similarity 0.91)
- Provable Representation with Efficient Planning for Partially Observable Reinforcement Learning (ICML 2024 · similarity 0.89)
- Offline RL with Observation Histories: Analyzing and Improving Sample Complexity (ICLR 2024 · similarity 0.88)
- Reinforcement Learning with Lookahead Information (NeurIPS 2024 · similarity 0.88)
- Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight (ICLR 2024 · similarity 0.88)
- Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge (AAAI 2024 · similarity 0.88)
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.