Column Generation Algorithms for Constrained POMDPs

Erwin Walraven, Matthijs T. J. SpaanJAIR 2018 · OpenReview

TL;DR

This paper introduces CGCP, a novel algorithm for solving Constrained Partially Observable Markov Decision Processes (Constrained POMDPs), which are crucial for decision-making under uncertainty with resource limitations. CGCP significantly outperforms existing methods by using approximate POMDP solvers and a policy graph representation, enabling efficient planning for both single-agent and multi-agent systems with shared constraints.

What Problem Does This Paper Address?

Many real-world decision-making scenarios involve uncertainty, partial observability, and resource constraints. For instance, managing maintenance for multiple bridges with a limited budget, or optimizing online advertising campaigns within a fixed budget, are complex problems. Constrained POMDPs offer a framework to model these situations, aiming to maximize expected rewards while adhering to resource limits. However, existing methods for solving Constrained POMDPs suffer from scalability issues and often assume discounted costs, which are not always practical. This paper addresses the need for efficient and scalable algorithms that can handle finite-horizon Constrained POMDPs, especially in multi-agent settings with shared constraints.

Methods

The paper proposes an adapted column generation algorithm called CGCP. Column generation is a technique for solving large linear programs by incrementally adding columns (representing policies) that are generated by solving unconstrained subproblems. The novelty lies in how these subproblems are solved:

  • Two-Stage Subproblem Solving: Instead of exact POMDP solvers, CGCP uses a tailored point-based value iteration algorithm for finite-horizon POMDPs. This algorithm efficiently computes an approximate solution.
  • Policy Graphs: The approximate policy obtained from the point-based solver is converted into a policy graph. This representation allows for efficient and exact policy evaluation, which is crucial for computing the coefficients needed for the column generation master problem.
  • Multi-Agent Extension: The framework is extended to handle multi-agent settings where multiple agents act independently but share a global constraint.

Datasets

The paper evaluates its approach on several benchmark domains:

  • Robot Navigation Domains: These are standard POMDP domains from pomdp.org, including MiniHall, Cheese, 4x3, Maze20, and Hallway. Modifications were made to include a trap state and a cost function for non-idle actions.
  • Condition-Based Maintenance Domain: This domain is based on the bridge-repair problem from pomdp.org, modeling multiple bridges requiring maintenance under a budget constraint.
  • Online Advertising Domain: This domain, also from pomdp.org (web-ad), models users with partially observable interests and advertising campaigns with associated costs.

Key Insights and Ideas

  • Approximate Solvers are Key to Scalability: Using approximate POMDP solvers for subproblems, rather than exact ones, is essential for making column generation practical for larger and more complex Constrained POMDPs.
  • Policy Graphs Bridge the Gap: Converting approximate vector-based policies into policy graphs provides an efficient way to evaluate them exactly, ensuring that the generated columns for the master LP are valid. This is a crucial step in maintaining the correctness of the column generation approach.
  • Multi-Agent with Shared Constraints is Tractable: The proposed CGCP algorithm effectively handles multi-agent scenarios where agents are loosely coupled through a shared constraint, a significant step towards solving real-world distributed decision-making problems.
  • Finite Horizon is Crucial: The focus on finite-horizon POMDPs is important because many real-world applications (like maintenance or budget allocation) have a natural time limit, and existing infinite-horizon algorithms with discounting are not always suitable.

Key Results

  • Outperforms State-of-the-Art: CGCP significantly outperforms the current state-of-the-art algorithm CALP (a finite-horizon version) on larger domains, achieving higher expected rewards and smaller gaps between lower and upper bounds, often in less time.
  • Scalability: The method demonstrates good scalability, especially in multi-agent settings, where it can handle problems with multiple agents sharing a global constraint.
  • Near-Optimal Solutions: Experiments show that CGCP computes high-quality, near-optimal solutions while effectively bounding the expected cost. For instance, in the navigation domains, CGCP achieved higher rewards and smaller gaps compared to CALP.
  • Policy Behavior Analysis: The study also analyzed the behavior of policies under tighter constraints, showing that reduced budgets lead to more failures (in maintenance) or more neutral advertising, as expected.

Limitations and Future Work

  • Upper Bound Tightness: The paper acknowledges that the upper bounds computed by CGCP might not always be tight, especially when the point-based algorithm runs for a short period. However, the quality of these bounds improves as the algorithm progresses.
  • Constraint on Expected Cost: The current formulation bounds the expected cost. Future work could explore methods to provide guarantees on the actual probability of constraint violation during execution, which is more challenging in partially observable settings.
  • Master LP Elimination: For larger multi-agent systems, eliminating the central master LP optimization problem by using a distributed optimization scheme is suggested as a future direction.
  • Exactness of Policy Graph Translation: While the policy graph translation is efficient, it's not always exact. The paper discusses methods to quantify and analyze this potential quality difference, noting that it's generally negligible in practice.

Summary updated

BibTeX
@article{walraven2018column,
  author = {Erwin Walraven and Matthijs T. J. Spaan},
  title = {{Column Generation Algorithms for Constrained POMDPs}},
  journal = {J. Artif. Intell. Res.},
  year = {2018},
  url = {https://openreview.net/forum?id=lyY6Sn6Z7W},
}
Figure