A Weighted Mini-Bucket Bound for Solving Influence Diagram

Junkyu Lee, Radu Marinescu, Alexander Ihler, Rina DechterUAI 2019 · OpenReview

Abstract

Influence diagrams provide a modeling and inference framework for sequential decision problems, representing probabilistic knowledge via Bayesian networks and agent preferences through utility functions. Calculating the Maximum Expected Utility (MEU) is a central task but is computationally demanding, often exponential in the induced width of the model. This paper introduces WMBE-ID, a weighted mini-bucket algorithm that provides tight upper bounds on the MEU by interleaving variable elimination with local optimization of weights and cost-shifting functions.

Introduction: The Challenge of Influence Diagrams

Influence Diagrams (IDs) are the standard for modeling sequential decision-making under uncertainty. They extend Bayesian networks by incorporating decision nodes and utility functions, allowing for the calculation of the Maximum Expected Utility (MEU). However, as the complexity of the model grows, the induced width increases, making exact inference intractable for many real-world applications.

An example of an Influence Diagram with state (S), decision (D), and utility (U) nodes.

To address this, researchers rely on upper bounds for the MEU. These bounds are critical for two reasons: they provide an approximate solution when exact methods fail, and they serve as heuristics for search-based algorithms like Branch-and-Bound, enabling more efficient pruning of the search space. Previous methods often struggled with scalability or optimization complexity as the approximation became more detailed.

Methodology: WMBE-ID

The proposed algorithm, WMBE-ID, builds upon the Mini-Bucket Elimination (MBE) framework. MBE manages complexity by partitioning large "buckets" of variables into smaller "mini-buckets" that respect a predefined memory limit, known as the i-bound.

WMBE-ID introduces several key enhancements:

  1. Weighted Mini-Buckets (WMB): By applying Hölder’s and Minkowski’s inequalities, the algorithm creates a parameterized bound using weights (exponents) for power-sum operators.
  2. Interleaved Local Optimization: Unlike previous methods that attempted global optimization, WMBE-ID optimizes weights and cost-shifting functions "on the fly" during the elimination process. This local approach is more robust as the i-bound increases.
  3. Dual Optimization Techniques: The algorithm utilizes Sequential Least Squares Programming (SLSQP) to tune cost-shifting functions and Exponentiated Gradient Descent (EGD) to optimize mini-bucket weights.
  4. Surrogate Objectives: To handle utility functions (which are not simple scalars), the authors derived a scalar surrogate objective to guide the optimization of the bound.

Experimental Evaluation

The researchers tested WMBE-ID across four domains: Factored Finite Horizon MDPs (FH-MDP), Partially Observable MDPs (FH-POMDP), random influence diagrams (RAND), and Bayesian networks converted to IDs (BN). The performance was compared against standard MBE and Join-Graph Dual Decomposition (JGDID), the previous state-of-the-art.

Key Results

The results demonstrate that the best configuration, WMBE-WC2, consistently outperforms JGDID in both bound tightness and scalability.

Performance comparison of various algorithms across different i-bounds and iteration limits. WMBE-WC2 consistently achieves tighter bounds (lower values) than JGDID.

As shown in the experimental data, WMBE-WC2 scales effectively with the i-bound. In many benchmarks, JGDID's performance stagnated or even degraded at higher i-bounds due to the difficulty of global optimization in high-dimensional spaces. In contrast, the local optimization strategy of WMBE-ID allowed it to continue improving the bound as more memory was allocated. Furthermore, WMBE-ID often reached superior bounds in a fraction of the time required by JGDID, demonstrating both efficiency and precision.

Conclusion

WMBE-ID represents a significant advancement in calculating upper bounds for Influence Diagrams. By focusing on local, interleaved optimization of weights and cost-shifting functions, it overcomes the scalability limitations of global decomposition methods. Future work will involve integrating these tighter bounds into search algorithms to accelerate the discovery of exact optimal policies.

Summary updated

Abstract

Influence diagrams provide a modeling and inference framework for sequential decision problems, representing the probabilistic knowledge by a Bayesian network and the preferences of an agent by uti...
BibTeX
@inproceedings{lee2019weighted,
  author = {Junkyu Lee and Radu Marinescu and Alexander Ihler and Rina Dechter},
  title = {{A Weighted Mini-Bucket Bound for Solving Influence Diagram}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=0rI0fDu0ih},
}
Figure