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

Abstract

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.

arXiv comment83 pages

References in corpus (11)

• Computational Mechanics: Pattern and Prediction, Structure and Simplicity
• Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
• Exploration by Random Network Distillation
• Memory-based control with recurrent neural networks
• Solving POMDPs by Searching in Policy Space
• Learning Finite-State Controllers for Partially Observable Environments
• MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs
• Near Optimal Behavior via Approximate State Abstraction
• On integral probability metrics, ϕ-divergences and binary classification
• On Improving Deep Reinforcement Learning for POMDPs
• BabyAI: A Platform to Study the Sample Efficiency of Grounded Language Learning

Cited by in corpus (3)

• Online Learning for Unknown Partially Observable MDPs
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach
• Common Information based Approximate State Representations in Multi-Agent Reinforcement Learning