Solving POMDPs by Searching in Policy Space

Eric A. HansenUAI 1998

TL;DR

This paper introduces a novel approach to solving Partially Observable Markov Decision Processes (POMDPs) by searching directly in the space of policies, represented as finite-state controllers. This method offers a more efficient alternative to traditional value iteration by avoiding computationally expensive dynamic programming updates, leading to faster convergence and potentially solving larger problems.

What Problem Does This Paper Address?

POMDPs are powerful models for planning and control in situations with uncertainty about the system's state. The standard approach to solving them involves dynamic programming, which iteratively refines a "value function" that implicitly defines an optimal policy. However, this value iteration method is computationally intensive, especially for problems with many states, actions, or observations. The core challenge is finding efficient ways to compute optimal policies for POMDPs, particularly for infinite-horizon problems where the value function can be complex. Existing methods often struggle with scalability due to the computational burden of the dynamic programming update.

Methods

The paper proposes two algorithms that search in "policy space" rather than "value function space":

  • Policy Iteration: This algorithm explicitly represents a policy as a finite-state controller. It iteratively improves this controller by:
  • Policy Evaluation: Computing the value function of the current finite-state controller.
  • Policy Improvement: Performing a dynamic-programming update to generate a set of "improved" vectors. These vectors are then used to modify the existing finite-state controller by changing machine states, adding new ones, or pruning redundant ones. This process continues until convergence.
  • Heuristic Search: This is a refinement of the policy iteration approach. Instead of performing a full dynamic-programming update (which considers all possible belief states), it uses a forward search from a specific starting belief state. This search explores a tree of belief states, computing upper and lower bounds. The key innovation is that it modifies the finite-state controller only if the search finds a way to improve the value for the starting belief state. This focuses computational effort on relevant parts of the state space and can lead to smaller, more efficient controllers.

The paper highlights that representing policies as finite-state controllers simplifies policy evaluation and allows for a more direct way to improve policies.

Datasets

Not discussed in the paper. The paper uses "test problems" from other research (e.g., Cassandra et al. 1997) which are described as having a certain number of states, actions, and observations, but specific datasets are not detailed.

Key Insights and Ideas

  • Policy Space Search is Viable: The paper demonstrates that searching directly in the space of policies, represented as finite-state controllers, is a practical and potentially more efficient alternative to value function search for POMDPs.
  • Finite-State Controllers as Policy Representation: Representing policies as finite-state controllers is a crucial enabler. It makes policy evaluation straightforward and allows for incremental improvements to the policy.
  • Heuristic Search for Efficiency: The heuristic search algorithm offers a significant advantage by focusing computational effort on the regions of belief space that are likely to be reached from a specific starting belief state. This contrasts with policy iteration, which aims to optimize for all possible belief states, often leading to larger controllers.
  • Smaller Controllers for Specific Tasks: Heuristic search can find smaller, yet effective, finite-state controllers for specific starting belief states, which can be more desirable than a controller optimized for all possible states.
  • Avoiding the Dynamic Programming Bottleneck: Both proposed algorithms aim to mitigate the computational burden of the dynamic programming update, which is the primary bottleneck in solving POMDPs. Heuristic search, in particular, avoids it altogether for policy improvement.

Key Results

  • Policy Iteration Performance: Table 1 shows that policy iteration consistently outperforms value iteration on nine test problems, often dramatically reducing the time to convergence to e-optimality.
  • Heuristic Search Potential: The heuristic search algorithm shows promise for solving problems that are computationally prohibitive for dynamic programming. For a 20-state maze problem, it found a controller with 96 machine states and a value of 52.2, significantly outperforming a controller found by policy iteration (172 states, value 34.3) after a limited search.
  • Convergence Guarantees: Both policy iteration and heuristic search are shown to converge to e-optimal policies in a finite number of iterations.

Limitations and Future Work

  • Memory Constraints: The heuristic search algorithm, particularly when using AO*, can run out of memory when trying to reduce the error bound further, especially if the upper bound function is not a good estimate.
  • Upper Bound Quality: The performance of heuristic search is sensitive to the quality of the upper bound function used for evaluating fringe nodes. Poor estimates can lead to excessive search tree expansion.
  • Implementation of Advanced Techniques: The authors plan to implement more sophisticated upper bound functions and memory-bounded versions of AO* to address memory limitations and improve performance.
  • Broader Testing: The authors acknowledge that their results are preliminary and plan to test the heuristic search algorithm on a wider range of problems to determine how far this approach can extend the solvable POMDPs.
  • Optimal Finite-State Controllers: Not all POMDPs have optimal finite-state controllers, and policy iteration may simply find increasingly close approximations.

Summary updated

BibTeX
@inproceedings{hansen1998solving,
  author = {Eric A. Hansen},
  title = {{Solving POMDPs by Searching in Policy Space}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1998},
}
Figure