mlsanityData to 14 Oct 2026

Provable Reinforcement Learning with a Short-Term Memory

arXiv 2202.03983 ↗First posted 8 Feb 2022cs.LG cs.AIcited by 40

Not on the map. Why?

Abstract (arXiv)

Real-world sequential decision making problems commonly involve partial observability, which requires the agent to maintain a memory of history in order to infer the latent states, plan and make good decisions. Coping with partial observability in general is extremely challenging, as a number of worst-case statistical and computational barriers are known in learning Partially Observable Markov Decision Processes (POMDPs). Motivated by the problem structure in several physical applications, as well as a commonly used technique known as "frame stacking", this paper proposes to study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length m. We establish a set of upper and lower bounds on the sample complexity for learning near-optimal policies for this class of problems in both tabular and rich-observation settings (where the number of observations is enormous). In particular, in the rich-observation setting, we develop new algorithms using a novel "moment matching" approach with a sample complexity that scales exponentially with the short length m rather than the problem horizon, and is independent of the number of observations. Our results show that a short-term memory suffices for reinforcement learning in these environments.

Key facts. Cited by 40 papers in the map (data through 14 Oct 2026). Builds on 24 of its 46 references that are in the map. First posted on arXiv 8 Feb 2022.

Builds on

24 of 46 references.

References · 24

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2019Dream to Control: Learning Behaviors by Latent Imaginationcited by 1,653
  3. 2017Rainbow: Combining Improvements in Deep Reinforcement Learningcited by 786
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  5. 2015Deep Recurrent Q-Learning for Partially Observable MDPscited by 465
  6. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  7. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  8. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  9. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  10. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  11. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  12. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
12 more
  1. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  2. 2018Deep Variational Reinforcement Learning for POMDPscited by 125
  3. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  4. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  5. 2019Online Control with Adversarial Disturbancescited by 92
  6. 2018Non-asymptotic Identification of LTI Systems from a Single Trajectorycited by 78
  7. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  8. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  9. 2019Learning Linear Dynamical Systems with Semi-Parametric Least Squarescited by 58
  10. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 52
  11. 2018On Improving Deep Reinforcement Learning for POMDPscited by 50
  12. 2016A PAC RL Algorithm for Episodic POMDPscited by 37

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 10; 2023: 12; 2024: 8; 2025: 7; 2026: 3.

40 papers.

Sort:

By area:

  1. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  2. 2022PAC Reinforcement Learning for Predictive State Representationscited by 43
  3. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  4. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  5. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  6. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  7. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 18
  8. 2022Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiencycited by 16
  9. 2023Lower Bounds for Learning in Revealing POMDPscited by 15
  10. 2024Diffusion Spectral Representation for Reinforcement Learningcited by 15
  11. 2022Finite-Time Analysis of Natural Actor-Critic for POMDPscited by 13
  12. 2023Provable Representation with Efficient Planning for Partial Observable Reinforcement Learningcited by 10
28 more
  1. 2024On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcited by 10
  2. 2025Partially Observable Reinforcement Learning with Memory Tracescited by 9
  3. 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDPcited by 8
  4. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 8
  5. 2022Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Makingcited by 6
  6. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  7. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 6
  8. 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
  9. 2023Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsightcited by 4
  10. 2023Prospective Side Information for Latent MDPscited by 4
  11. 2025Scalable Policy-Based RL Algorithms for POMDPscited by 4
  12. 2024Near-Optimal Learning and Planning in Separated Latent MDPscited by 3
  13. 2024Tractable Offline Learning of Regular Decision Processescited by 3
  14. 2024Abstract Reward Processes: Leveraging State Abstraction for Consistent Off-Policy Evaluationcited by 3
  15. 2025Guided Policy Optimization under Partial Observabilitycited by 3
  16. 2025To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learningcited by 3
  17. 2025Spectral Representation-based Reinforcement Learningcited by 3
  18. 2024Generalizing Multi-Step Inverse Models for Representation Learning to Finite-Memory POMDPscited by 2
  19. 2023Provable Robustness for Streaming Models with a Sliding Windowcited by 1
  20. 2024Preparing for Black Swans: The Antifragility Imperative for Machine Learningcited by 1
  21. 2026Why Linear Recurrent Memory Works in Partially Observable Reinforcement Learningcited by 1
  22. 2023Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Informationcited by 0
  23. 2023Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbationscited by 0
  24. 2023Representation Learning in Low-rank Slate-based Recommender Systemscited by 0
  25. 2023Safe Reinforcement Learning in Tensor Reproducing Kernel Hilbert Spacecited by 0
  26. 2025Quantifying Memory Use in Reinforcement Learning with Temporal Rangecited by 0
  27. 2026Smaller Abstract State Spaces Enable Cross-Scale Generalization in Reinforcement Learningcited by 0
  28. 2026A Decentralized Partially Observable Team Decision Methodology with Delayed Information Sharingcited by 0