Solving POMDPs by Searching the Space of Finite Policies

Abstract

Solving partially observable Markov decision processes (POMDPs) is highly intractable in general, at least in part because the optimal policy may be infinitely large. In this paper, we explore the problem of finding the optimal policy from a restricted set of policies, represented as finite state automata of a given size. This problem is also intractable, but we show that the complexity can be greatly reduced when the POMDP and/or policy are further constrained. We demonstrate good empirical results with a branch-and-bound method for finding globally optimal deterministic policies, and a gradient-ascent method for finding locally optimal stochastic policies.

arXiv commentAppears in Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI1999)

References in corpus (4)

• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• Solving POMDPs by Searching in Policy Space
• Learning Finite-State Controllers for Partially Observable Environments
• Learning Policies with External Memory

Cited by in corpus (21)

• Perseus: Randomized Point-based Value Iteration for POMDPs
• Finding Approximate POMDP solutions Through Belief Compression
• The Complexity of Decentralized Control of Markov Decision Processes
• Learning Finite-State Controllers for Partially Observable Environments
• MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs
• Nonapproximability Results for Partially Observable Markov Decision Processes
• Learning Policies with External Memory
• Delay-aware BS Discontinuous Transmission Control and User Scheduling for Energy Harvesting Downlink Coordinated MIMO Systems
• Decentralized Delay Optimal Control for Interference Networks with Limited Renewable Energy Storage
• Low Complexity Delay-Constrained Beamforming for Multi-User MIMO Systems with Imperfect CSIT
• Optimized Bacteria are Environmental Prediction Engines
• The Complexity of Approximately Solving Influence Diagrams
• Memory-Limited Partially Observable Stochastic Control and its Mean-Field Control Approach
• My Brain is Full: When More Memory Helps
• Formal Methods for Autonomous Systems
• Sparse Stochastic Finite-State Controllers for POMDPs
• Data Collection versus Data Estimation: A Fundamental Trade-off in Dynamic Networks
• Learning What to Memorize: Using Intrinsic Motivation to Form Useful Memory in Partially Observable Reinforcement Learning
• Stochastic Shortest Path with Energy Constraints in POMDPs
• How memory architecture affects learning in a simple POMDP: the two-hypothesis testing problem
• Near-Optimal Design for Fault-Tolerant Systems with Homogeneous Components under Incomplete Information