Value-Function Approximations for Partially Observable Markov Decision Processes

Abstract

Partially observable Markov decision processes (POMDPs) provide an elegant mathematical framework for modeling complex decision and planning problems in stochastic domains in which states of the system are observable only indirectly, via a set of imperfect or noisy observations. The modeling advantage of POMDPs, however, comes at a price -- exact methods for solving them are computationally very expensive and thus applicable in practice only to very simple problems. We focus on efficient approximation (heuristic) methods that attempt to alleviate the computational problem and trade off accuracy for speed. We have two objectives here. First, we survey various approximation methods, analyze their properties and relations and provide some new insights into their differences. Second, we present a number of new approximation methods and novel refinements of existing techniques. The theoretical results are supported by experiments on a problem from the agent navigation domain.

References in corpus (8)

• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• Tractable Inference for Complex Stochastic Processes
• Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
• Stochastic Simulation Algorithms for Dynamic Probabilistic Networks
• Solving POMDPs by Searching in Policy Space
• Approximate Planning for Factored POMDPs using Belief State Simplification
• Planning with Partially Observable Markov Decision Processes: Advances in Exact Solution Method
• Region-Based Approximations for Planning in Stochastic Domains

Cited by in corpus (56)

• A Survey and Critique of Multiagent Deep Reinforcement Learning
• Online Planning Algorithms for POMDPs
• Anytime Point-Based Approximations for Large POMDPs
• Perseus: Randomized Point-based Value Iteration for POMDPs
• Optimal and Approximate Q-value Functions for Decentralized POMDPs
• Finding Approximate POMDP solutions Through Belief Compression
• Partially Observable Markov Decision Processes in Robotics: A Survey
• MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs
• Partially Observable Markov Decision Processes (POMDPs) and Robotics
• Speeding Up the Convergence of Value Iteration in Partially Observable Markov Decision Processes
• Planning for robotic exploration based on forward simulation
• Sensor Scheduling for Energy-Efficient Target Tracking in Sensor Networks
• Point-Based POMDP Algorithms: Improved Analysis and Implementation
• Solving Factored MDPs with Hybrid State and Action Variables
• Searching for a source without gradients: how good is infotaxis and how to beat it
• A Framework for Sequential Planning in Multi-Agent Settings
• Incremental Clustering and Expansion for Faster Optimal Planning in Dec-POMDPs
• Sensor Management for Tracking in Sensor Networks
• Multi-Objective Multi-Agent Planning for Discovering and Tracking Multiple Mobile Objects
• Exploiting Submodular Value Functions For Scaling Up Active Perception
• Hilbert Space Embeddings of POMDPs
• The Actor Search Tree Critic (ASTC) for Off-Policy POMDP Learning in Medical Decision Making
• Partially Observable Markov Decision Process for Recommender Systems
• Shaping Belief States with Generative Environment Models for RL
• Qualitative MDPs and POMDPs: An Order-Of-Magnitude Approximation
• Smoother Entropy for Active State Trajectory Estimation and Obfuscation in POMDPs
• Learning Belief Representations for Imitation Learning in POMDPs
• Vector-space Analysis of Belief-state Approximation for POMDPs
• Temporal Difference Variational Auto-Encoder
• Optimizing Sequential Medical Treatments with Auto-Encoding Heuristic Search in POMDPs
• FHHOP: A Factored Hybrid Heuristic Online Planning Algorithm for Large POMDPs
• Restricted Value Iteration: Theory and Algorithms
• Exploiting Causality for Selective Belief Filtering in Dynamic Bayesian Networks
• Interpreting systems as solving POMDPs: a step towards a formal understanding of agency
• Fast Accurate Beam and Channel Tracking for Two-dimensional Phased Antenna Arrays
• Mind model seems necessary for the emergence of communication
• Optimal Sensing via Multi-armed Bandit Relaxations in Mixed Observability Domains
• Value of structural health information in partially observable stochastic environments
• Inverse Decision Modeling: Learning Interpretable Representations of Behavior
• Deep Latent Competition: Learning to Race Using Visual Control Policies in Latent Space
• Myopic Policy Bounds for Information Acquisition POMDPs
• Control of Probabilistic Systems under Dynamic, Partially Known Environments with Temporal Logic Specifications
• On the Linear Belief Compression of POMDPs: A re-examination of current methods
• Stochastic 2-D Motion Planning with a POMDP Framework
• Instance based Generalization in Reinforcement Learning
• Point-Based Methods for Model Checking in Partially Observable Markov Decision Processes
• Planning on a (Risk) Budget: Safe Non-Conservative Planning in Probabilistic Dynamic Environments
• Sequential Stochastic Optimization in Separable Learning Environments
• On Anderson acceleration for partially observable Markov decision processes
• Deceptive Kernel Function on Observations of Discrete POMDP
• Partially Observed, Multi-objective Markov Games
• Approximate Dynamic Programming based on High Dimensional Model Representation
• Dynamic Programming for POMDP with Jointly Discrete and Continuous State-Spaces
• Tree Exploration for Bayesian RL Exploration
• Verification of Uncertain POMDPs Using Barrier Certificates
• How memory architecture affects learning in a simple POMDP: the two-hypothesis testing problem