# Approximate information state for approximate planning and reinforcement learning in partially observed systems

arXiv: https://arxiv.org/abs/2010.08843 · HTML: https://mlsanity.com/paper/2010.08843/

## Key facts

- Cited by 70 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2020.

## Built on by (most cited first, 30 of 70)

- [Bridging State and History Representations: Understanding Self-Predictive RL](https://mlsanity.com/paper/2401.08898/) (2024)
- [Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent States](https://mlsanity.com/paper/2102.05261/) (2021)
- [Next-Latent Prediction Transformers Learn Compact World Models](https://mlsanity.com/paper/2511.05963/) (2025)
- [RePo: Resilient Model-Based Reinforcement Learning by Regularizing Posterior Predictability](https://mlsanity.com/paper/2309.00082/) (2023)
- [Online Learning for Unknown Partially Observable MDPs](https://mlsanity.com/paper/2102.12661/) (2021)
- [BetaZero: Belief-State Planning for Long-Horizon POMDPs using Learned Approximations](https://mlsanity.com/paper/2306.00249/) (2023)
- [Finite-Time Analysis of Natural Actor-Critic for POMDPs](https://mlsanity.com/paper/2202.09753/) (2022)
- [Informed POMDP: Leveraging Additional Information in Model-Based RL](https://mlsanity.com/paper/2306.11488/) (2023)
- [Reinforcement Learning in Non-Markovian Environments](https://mlsanity.com/paper/2211.01595/) (2022)
- [ContraBAR: Contrastive Bayes-Adaptive Deep RL](https://mlsanity.com/paper/2306.02418/) (2023)
- [A Unified View on Solving Objective Mismatch in Model-Based Reinforcement Learning](https://mlsanity.com/paper/2310.06253/) (2023)
- [iQRL -- Implicitly Quantized Representations for Sample-efficient Reinforcement Learning](https://mlsanity.com/paper/2406.02696/) (2024)
- [Agent-state based policies in POMDPs: Beyond belief-state MDPs](https://mlsanity.com/paper/2409.15703/) (2024)
- [Common Information based Approximate State Representations in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.12603/) (2021)
- [Connected and Automated Vehicles in Mixed-Traffic: Learning Human Driver Behavior for Effective On-Ramp Merging](https://mlsanity.com/paper/2304.00397/) (2023)
- [Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments](https://mlsanity.com/paper/2311.00123/) (2023)
- [Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach](https://mlsanity.com/paper/2402.19265/) (2024)
- [How to Explore with Belief: State Entropy Maximization in POMDPs](https://mlsanity.com/paper/2406.02295/) (2024)
- [Periodic agent-state based Q-learning for POMDPs](https://mlsanity.com/paper/2407.06121/) (2024)
- [A Theoretical Justification for Asymmetric Actor-Critic Algorithms](https://mlsanity.com/paper/2501.19116/) (2025)
- [On learning history based policies for controlling Markov decision processes](https://mlsanity.com/paper/2211.03011/) (2022)
- [Approximate information state based convergence analysis of recurrent Q-learning](https://mlsanity.com/paper/2306.05991/) (2023)
- [Decision Transformer as a Foundation Model for Partially Observable Continuous Control](https://mlsanity.com/paper/2404.02407/) (2024)
- [A Framework for Effective AI Recommendations in Cyber-Physical-Human Systems](https://mlsanity.com/paper/2403.05715/) (2024)
- [Exploring Time-Step Size in Reinforcement Learning for Sepsis Treatment](https://mlsanity.com/paper/2511.20913/) (2025)
- [Towards Data-Driven Offline Simulations for Online Reinforcement Learning](https://mlsanity.com/paper/2211.07614/) (2022)
- [Cost-Driven Representation Learning for Linear Quadratic Gaussian Control: Part I](https://mlsanity.com/paper/2212.14511/) (2022)
- [Approximate Information States for Worst-Case Control and Learning in Uncertain Systems](https://mlsanity.com/paper/2301.05089/) (2023)
- [Worst-Case Control and Learning Using Partial Observations Over an Infinite Time-Horizon](https://mlsanity.com/paper/2303.16321/) (2023)
- [Representation Learning For Efficient Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2406.02890/) (2024)

## Abstract (arXiv)

We propose a theoretical framework for approximate planning and learning in partially observed systems. Our framework is based on the fundamental notion of information state. We provide two equivalent definitions of information state -- i) a function of history which is sufficient to compute the expected reward and predict its next value; ii) equivalently, a function of the history which can be recursively updated and is sufficient to compute the expected reward and predict the next observation. An information state always leads to a dynamic programming decomposition. Our key result is to show that if a function of the history (called approximate information state (AIS)) approximately satisfies the properties of the information state, then there is a corresponding approximate dynamic program. We show that the policy computed using this is approximately optimal with bounded loss of optimality. We show that several approximations in state, observation and action spaces in literature can be viewed as instances of AIS. In some of these cases, we obtain tighter bounds. A salient feature of AIS is that it can be learnt from data. We present AIS based multi-time scale policy gradient algorithms. and detailed numerical experiments with low, moderate and high dimensional environments.