Sparse Stochastic Finite-State Controllers for POMDPs

Eric A. HansenUAI 2008

TL;DR

This paper introduces "Sparse Bounded Policy Iteration" (Sparse BPI), a more scalable algorithm for solving Partially Observable Markov Decision Processes (POMDPs). By exploiting the inherent sparsity in learned policies, Sparse BPI significantly reduces computation time, making it practical to find better controllers for complex POMDPs.

What Problem Does This Paper Address?

Decision-making under uncertainty is a fundamental challenge in AI. Partially Observable Markov Decision Processes (POMDPs) provide a powerful mathematical framework for modeling such problems, where an agent must act based on incomplete information about the environment's state. Solving POMDPs is notoriously difficult, especially for infinite-horizon problems where decisions have long-term consequences. A common approach is "Bounded Policy Iteration" (BPI), which represents policies as finite-state controllers (FSCs). However, the computational cost of BPI, particularly in the policy improvement step, grows significantly with the size of the controller, limiting its applicability to larger problems. This paper aims to improve the scalability of BPI by addressing this computational bottleneck.

Methods

The core innovation is Sparse Bounded Policy Iteration (Sparse BPI). The original BPI algorithm improves a controller by solving a linear program (LP) for each node. The complexity of this LP depends on the total number of parameters for a node, which can be large. Sparse BPI leverages the observation that in practice, most of these parameters have zero probabilities, meaning only a small subset are "useful."

Sparse BPI refines the policy improvement step by:

  1. Identifying "Useful" Parameters: Instead of solving the full LP, Sparse BPI iteratively solves reduced LPs that only include the currently identified useful parameters.
  2. Iterative Refinement: It starts with the parameters that are already non-zero. If the current solution isn't optimal, it performs a "backup" for a "tangent belief state" (a specific state of belief where the current policy is locally optimal). If this backup reveals a better outcome, the parameters that led to this improvement are added to the set of useful parameters for the next iteration of the reduced LP.
  3. Guaranteed Convergence: This iterative process continues until no further improvement is possible, at which point the solution from the final reduced LP is equivalent to the solution of the original full LP.

This approach is inspired by techniques used in BPI to add nodes to escape local optima and shares similarities with "column generation" methods in linear programming.

Datasets

The paper evaluates its approach on four benchmark POMDPs: Slotted Aloha, Tiger grid, Hallway, and Hallway2. These are standard test problems in the POMDP literature, originating from Cassandra's POMDP repository. No new benchmarks were introduced.

Key Insights and Ideas

  • Sparsity is Key: The most significant insight is that learned stochastic finite-state controllers are highly sparse. Most parameters (action selection and transition probabilities) are effectively zero, even when controllers are stochastic.
  • Exploiting Sparsity for Scalability: By focusing only on the non-zero parameters, Sparse BPI dramatically reduces the size of the linear programs that need to be solved, leading to substantial speedups.
  • Iterative Improvement of Parameters: The method of iteratively adding parameters based on backups at tangent belief states is an elegant way to find the truly useful parameters without needing to solve the full, large LP upfront.
  • Practical Implications: This work makes BPI more practical for solving larger and more complex POMDPs by improving its scalability with respect to controller size.

Key Results

  • Significant Speedup: Table 3 shows that Sparse BPI is substantially faster than the original BPI algorithm. For controllers with 300 nodes, Sparse BPI runs between 20 and 80 times faster.
  • Constant Improvement Time: The time to improve a single node in Sparse BPI remains relatively constant as the controller size grows, whereas the original BPI's time increases significantly with controller size. This is the primary driver of its improved scalability.
  • Equivalent Improvement: Sparse BPI achieves the same policy improvement as the original BPI algorithm in each iteration.

Limitations and Future Work

  • State Space Complexity: The paper acknowledges that while Sparse BPI addresses controller size complexity, it doesn't directly solve the problem of large state spaces. However, it notes that techniques like value-directed compression can be combined with Sparse BPI.
  • Number of Iterations: For some problems, Sparse BPI might still require a considerable number of iterations to identify all useful parameters for a node. Future work could focus on reducing this number of iterations.
  • Early Termination: The authors suggest that an early termination strategy, stopping when improvement becomes marginal, could further reduce computation time.
  • Integration with Point-Based Methods: They propose integrating point-based methods with policy iteration to potentially identify parameters more efficiently, avoiding the need to solve multiple linear programs per node.

Summary updated

BibTeX
@inproceedings{hansen2008sparse,
  author = {Eric A. Hansen},
  title = {{Sparse Stochastic Finite-State Controllers for POMDPs}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2008},
}
Figure