Piecewise Linear Dynamic Programming for Constrained POMDPs

Joshua D. Isom, Sean P. Meyn, Richard D. BraatzAAAI 2008

Introduction

In complex decision-making environments, agents often face the dual challenge of optimizing performance while adhering to strict safety or resource constraints. For instance, a maintenance engineer aims to minimize operational costs but must ensure the probability of structural failure remains below a critical threshold. These scenarios are formally modeled as Constrained Partially Observable Markov Decision Processes (CPOMDPs).

While standard POMDPs—which account for state uncertainty—have established exact solution methods, CPOMDPs are significantly more challenging due to the uncountably infinite nature of the belief state. This paper presents the first exact dynamic programming update for CPOMDPs, bridging the gap between constrained optimization and continuous belief-space planning.

Problem Formulation

The core difficulty in CPOMDPs lies in the "pruning" process, which is essential for maintaining a manageable set of value vectors. In unconstrained settings, pruning identifies vectors that are never optimal for any belief state. In the constrained case, a vector is only considered "best" if it minimizes cost among the subset of vectors that satisfy the specified constraints.

The authors evaluate their approach using a classic "Quickest Change Detection" problem. In this model, a system's state transitions at an unknown time, and the agent must detect this change as quickly as possible (minimizing delay) while keeping the false alarm probability below a fixed threshold $\alpha$.

State transition diagram for the quickest change detection problem.

Methodology: Vector Pairs and MILP Pruning

The proposed algorithm extends the standard "Incremental Pruning" method by representing the value function as pairs of piecewise linear vectors $(v_r, v_c)$. Here, $v_r$ denotes the expected reward or cost, and $v_c$ represents the expected constraint valuation for a given belief state.

The "secret sauce" of POMDP solvers is the pruning operation, which discards vectors that are dominated by others across the entire belief space. In unconstrained POMDPs, this is typically achieved through Linear Programming (LP). However, CPOMDPs introduce a conditional requirement: a vector is only "best" if it yields the lowest cost among those that satisfy the constraint threshold. The authors bridge this gap by introducing discrete binary variables to handle the conditional logic, effectively transforming the pruning step into a Mixed Integer Linear Program (MILP). This allows the solver to filter out sub-optimal or non-compliant policies while maintaining the piecewise linear structure of the value function.

Piecewise linear representation of reward ($v_r$) and constraint ($v_c$) value functions across belief states.

This MILP-based update can be integrated into policy iteration algorithms, such as Hansen’s, to improve finite-state controllers for both indefinite and infinite-horizon problems.

Key Insights and Results

The research yields several critical insights:

  • Duality of Value: Effective CPOMDP solvers must track the "shadow" of the constraint function alongside the objective function throughout the dynamic programming recursion. This dual representation is essential for ensuring that constraints are respected at every step of the planning horizon.
  • Optimal Thresholds: In numerical tests (e.g., $\alpha = 0.20$), the exact method outperformed common heuristics. While a standard heuristic might sound an alarm when the probability of change exceeds $1-\alpha$ (0.80), the CPOMDP approach identified a more nuanced threshold of 0.40, achieving a significantly lower expected detection delay of approximately 4 units.
  • Mathematical Foundation: The paper successfully extends the piecewise linear representation—the gold standard for exact POMDP solutions—to the constrained domain, providing a rigorous framework for future developments.

Limitations and Future Outlook

Despite its theoretical significance, the exact method faces computational hurdles. POMDPs are PSPACE-complete, and the addition of MILP to the inner loop increases overhead, limiting the current implementation to modestly sized problems.

Future research should leverage this MILP framework to develop approximate methods, such as point-based solvers, which update the value function only at specific belief points to enhance scalability for larger state spaces. Such advancements would make exact or near-exact CPOMDP solutions viable for complex, real-world robotics and industrial control applications.

Summary updated

BibTeX
@inproceedings{isom2008piecewise,
  author = {Joshua D. Isom and Sean P. Meyn and Richard D. Braatz},
  title = {{Piecewise Linear Dynamic Programming for Constrained POMDPs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure