Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search

Arindam Khaled, Eric A. Hansen, Changhe YuanUAI 2013

TL;DR

This paper introduces a novel branch-and-bound search algorithm for solving Limited-Memory Influence Diagrams (LIMIDs), a more general class of decision problems than traditional Influence Diagrams. By transforming the problem into an AND/OR graph and employing context-based merging of decision nodes, their approach significantly improves efficiency for complex, multi-stage decision-making scenarios.

What Problem Does This Paper Address?

Influence Diagrams (IDs) are powerful graphical models for representing decision problems under uncertainty. However, traditional IDs rely on strict assumptions like "regularity" (decisions are temporally ordered) and "no-forgetting" (decisions can depend on all past observations). These assumptions limit their applicability to real-world problems where agents might not remember all past information or where decisions are made more concurrently. Limited-Memory Influence Diagrams (LIMIDs) relax these assumptions, allowing for more flexible modeling, but they are significantly harder to solve. Existing algorithms for LIMIDs are either limited in scope or computationally expensive. This paper addresses the challenge of efficiently finding optimal strategies for these more general LIMIDs.

Methods

The core contribution is an exact algorithm for solving LIMIDs based on branch-and-bound search. This approach builds upon existing branch-and-bound methods for traditional IDs but adapts them for LIMIDs in several key ways:

  • AND/OR Graph Search: Instead of an AND/OR tree, the algorithm searches an AND/OR graph. This is crucial because LIMIDs allow for different histories to lead to the same decision point, creating redundant subproblems that can be merged in a graph structure.
  • Context-Based Merging of OR Nodes: To exploit the graph structure, the algorithm identifies and merges "equivalent" OR nodes (representing decision variables). Equivalence is determined by a "context," which captures the relevant information available to a decision maker at that point, reflecting the limited memory. This prevents redundant computation.
  • Special AND (SAND) Nodes: For conditionally-independent decision scenarios (where multiple decisions can be made in parallel), a new "SAND" node type is introduced in the AND/OR graph to handle these parallel expansions efficiently.
  • Incremental Join Tree Evaluation: The algorithm leverages an incremental join tree evaluation method to efficiently compute probabilities and upper bounds needed for pruning the search graph. This method is adapted to work with the AND/OR graph structure.
  • Relaxed Influence Diagram for Bounds: To compute upper bounds for pruning, a "relaxed ID" is constructed. This relaxed ID is easier to solve and provides an upper bound on the optimal utility of the original LIMID.

Datasets

The paper evaluates its algorithm on three types of problems:

  • Maze Navigation Problem: A standard benchmark problem used to illustrate LIMIDs, with varying numbers of stages.
  • Multi-Agent Tiger Behind Door Problem: A finite-horizon Dec-POMDP representing cooperative multi-agent decision-making, where agents have limited awareness of each other.
  • Randomly-Generated LIMIDs: A set of LIMIDs generated with varying numbers of stages and complexity, designed to test the algorithm's scalability.

No new datasets were introduced; rather, existing problem formulations were used to demonstrate the algorithm's effectiveness.

Key Insights and Ideas

  • Graph vs. Tree for LIMIDs: The fundamental insight is that the search space for LIMIDs is naturally a graph, not a tree, due to relaxed memory assumptions. Merging equivalent decision nodes (OR nodes) in this graph is essential for efficiency.
  • Context is Key for Merging: Defining and computing the "context" of a decision node is the critical mechanism for identifying redundant subproblems and enabling graph-based search.
  • Efficiency through Graph Representation: By moving from an AND/OR tree to an AND/OR graph, the algorithm avoids re-solving the same decision scenarios multiple times, leading to significant computational savings.
  • SAND Nodes for Parallelism: The introduction of SAND nodes elegantly handles situations where multiple decisions can be made concurrently, a common scenario in more general decision problems.

Key Results

The experimental evaluation demonstrates the effectiveness of the proposed algorithm:

  • Scalability: The algorithm successfully solves problems with increasing numbers of stages, outperforming previous methods on complex LIMIDs. For instance, it solves a 10-stage maze navigation problem with 10^156 possible strategies.
  • Efficiency: The algorithm shows significant speedups, especially on problems with many stages or cooperative decision-making aspects. For example, the multi-agent tiger problem is solved optimally for up to eight stages in under an hour.
  • Pruning Effectiveness: A substantial portion of the search space is pruned, with approximately 40% of pruning attributed to bounds and the rest to zero-probability branches.

Limitations and Future Work

  • Bounds Simplification: The authors acknowledge that the bounds used in their current implementation are relatively simple (equivalent to assuming perfect information). They suggest that improving these bounds could lead to even more pruning and faster search.
  • Context Merging Improvement: The context-based merging approach is described as simple and could potentially be improved for greater efficiency or to find more compact representations of optimal strategies.
  • Comparison to MPU: While the paper discusses the state-of-the-art Multiple Policy Updating (MPU) algorithm, a direct, comprehensive comparison is not provided. Future work could involve a more detailed characterization of the relative performance of their branch-and-bound approach versus MPU.
  • Treewidth Limitations: The scalability of their approach appears to be related to the treewidth of the relaxed LIMID, which is often smaller than the original LIMID's treewidth. Further investigation into this relationship and its implications for scalability is warranted.

Summary updated

BibTeX
@inproceedings{khaled2013solving,
  author = {Arindam Khaled and Eric A. Hansen and Changhe Yuan},
  title = {{Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2013},
}
Figure