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.

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

References in corpus (2)

• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• Solving POMDPs by Searching in Policy Space

Cited by in corpus (6)

• The Complexity of Decentralized Control of Markov Decision Processes
• MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs
• Nonapproximability Results for Partially Observable Markov Decision Processes
• The Complexity of Approximately Solving Influence Diagrams
• My Brain is Full: When More Memory Helps
• Sparse Stochastic Finite-State Controllers for POMDPs