Abstract
Since the early 1990's, Markov decision processes (MDPs) and their partially observable counterparts (POMDPs) have been widely used by the AI community for planning under uncertainty. POMDPs offer a rich language to describe situations involving uncertainty about the domain, stochastic actions, noisy observations, and a variety of possible objective functions. Even though an optimal solution may be concise, current exact algorithms that use dynamic programming often require an intractable amount of space. POMDP approximation algorithms can operate with a limited amount of memory, but as a consequence they provide very weak theoretical guarantees. In contrast, we describe a new approach that addresses the space requirement of POMDP algorithms while maintaining well-defined optimality guarantees.
Introduction
Planning in real-world environments is inherently complex due to uncertainty. Partially Observable Markov Decision Processes (POMDPs) provide a robust framework for modeling such environments, where agents must act based on noisy sensors and incomplete information. However, solving POMDPs optimally is notoriously difficult; the optimal choice depends on the entire history of observations, leading to an exponential explosion in memory requirements.
To mitigate this, researchers often employ Finite-State Controllers (FSCs), which represent policies as fixed-size "brains" with a set number of internal nodes. The challenge lies in optimizing these controllers. Existing methods, such as Bounded Policy Iteration (BPI) or Gradient Ascent (GA), frequently converge to local optima because they rely on one-step lookaheads or struggle with the complex constraints of probability distributions. This paper introduces a novel formulation of the POMDP policy search as a Quadratically Constrained Linear Program (QCLP), enabling the use of global optimization techniques to find high-quality, compact controllers.
Methodology
The proposed approach shifts the search for an optimal fixed-size controller into the realm of nonlinear programming. By formulating the problem as a QCLP, the authors can leverage powerful off-the-shelf solvers like SNOPT (Sequential Quadratic Programming).
The QCLP Formulation
The key innovation lies in how the variables and constraints are structured:
- Merged Variables: Action selection and node transition probabilities are combined into a single set of variables ($x$).
- Bellman Constraints: The Bellman Equation is used as a primary constraint. Since the equation involves multiplying controller probabilities by the resulting values, the constraints become quadratic.
- Objective Function: The goal is to maximize the expected value of the starting state.
Unlike iterative local updates, this formulation accounts for the infinite-horizon value of the controller during optimization, allowing for more effective navigation of the policy space.
Experimental Evaluation
The QCLP approach was evaluated on two classic POMDP benchmarks:
- Hallway Domain: A grid-world navigation problem with 57 states, 21 observations, and 5 actions, characterized by high sensor noise.
- Machine Maintenance: A larger problem with 256 states, involving the management of four independent, degrading components.
Results and Discussion
The experimental results demonstrate that the QCLP formulation consistently outperforms state-of-the-art methods like BPI and Biased BPI across various controller sizes.
In the Hallway domain, QCLP achieved significantly higher values across all tested controller sizes. A similar trend was observed in the Machine Maintenance domain, where a 4-node QCLP controller outperformed BPI controllers of any size tested.
Key insights from the results include:
- Infinite Lookahead: By capturing the long-term value of parameter changes, QCLP avoids the "short-sightedness" of one-step lookahead methods.
- Stochasticity: The optimization naturally finds optimal stochastic strategies, which are often superior to deterministic ones for small controllers.
- Compactness and Efficiency: A 10-node QCLP controller achieved a 40% higher value than a 1500-node controller from previous literature, while requiring only 0.21% of the computation time. In the machine maintenance task, solutions reached approximately 92% of the theoretical MDP upper bound.
Conclusion and Future Work
While the QCLP formulation is nonconvex—meaning solvers may still find local optima—it provides a significant leap in solution quality and memory efficiency compared to previous local search methods. Future work includes developing customized solvers tailored to the specific structure of POMDP QCLPs to improve scalability and extending the framework to multi-agent decentralized POMDPs.
Summary updated