Flexible Policy Construction by Information Refinement

Michael C. Horsch, David L. PooleUAI 1996

TL;DR

This paper introduces an iterative algorithm, DT1, for constructing decision policies in influence diagrams. It builds decision trees incrementally, offering a flexible "anytime" approach that provides usable, albeit sub-optimal, policies even before full computation, making it suitable for resource-bounded decision-making.

What Problem Does This Paper Address?

Decision problems are often modeled using influence diagrams (IDs), which represent complex sequences of decisions and uncertainties. While traditional methods can find optimal policies, they often require computationally expensive, exhaustive searches. This is problematic in real-world scenarios where computational resources are limited or decisions must be made quickly. The paper addresses the need for flexible algorithms that can produce good policies rapidly and improve them incrementally as more computational resources become available.

Methods

The core of the paper is the DT1 algorithm, which constructs decision functions (policies) for each decision node in an influence diagram as a decision tree. These trees are built incrementally:

  • Initialization: A decision tree starts as a single leaf representing a default action.
  • Extension: The algorithm iteratively refines the tree by replacing a leaf with an internal node representing an observable variable. New leaves are added for each possible value of this variable, each representing an action.
  • Greedy Extension: The paper proposes a greedy strategy for choosing which variable to add at each step. It selects the variable that maximizes the expected value of improvement (EVI) for the current leaf.
  • Leaf Selection Heuristic: For choosing which leaf to extend, the paper explores a post hoc heuristic (prioritizing leaves that previously led to the greatest expected value increase) and a random approach.
  • Computational Engine: The algorithm relies on Bayesian networks (BNs) to compute expected values and posterior probabilities, leveraging existing efficient inference techniques.

The key novelty lies in the incremental, anytime nature of the algorithm, contrasting with traditional static, optimal-only approaches.

Datasets

Not discussed in the paper. The authors use a well-known example, the "Car Buyer Problem," and generate random influence diagrams for evaluation.

Key Insights and Ideas

  • Anytime Policies: The most significant insight is that useful, sub-optimal policies can be constructed incrementally. This is crucial for agents operating under time or computational constraints.
  • Decision Trees as Policies: Representing decision functions as trees provides a structured and interpretable way to encode policies, especially when dealing with information dependencies.
  • Trade-off between Tree Size and Computation: The greedy approach tends to produce smaller, more complex trees, while random approaches might generate larger trees with similar computational effort in early stages.
  • Asymmetries Matter: The paper highlights how asymmetries in decision problems (e.g., logical impossibilities) can significantly impact the efficiency of decision tree construction and the size of the optimal tree.

Key Results

  • Incremental Improvement: The DT1 algorithm guarantees that each iteration produces a decision tree with an expected utility no less than the previous one.
  • Computational Efficiency: While the asymptotic number of BN computations is a constant factor larger than traditional dynamic programming, DT1 offers an "anytime" advantage. For the Car Buyer problem, the first usable policy was available after just 2 BN calculations, with an expected value close to optimal.
  • Greedy vs. Random: The greedy approach for extension can be computationally expensive for small contexts but leads to smaller trees. The random approach is less computationally demanding overall but may produce larger trees.
  • Multi-stage IDs: Applying DT1 to multi-stage influence diagrams using a sweep-back approach loses the anytime property, but preliminary results show promise in efficiently finding optimal policies.

Limitations and Future Work

  • Myopic Nature: The DT1 algorithm is myopic, meaning it makes locally optimal choices at each step, which doesn't guarantee global optimality for the entire tree construction process.
  • Heuristic Weakness: The post hoc heuristic for leaf selection is noted as potentially weak, and the authors are investigating better methods.
  • Multi-stage Anytime Property: The anytime property is lost when applying DT1 to multi-stage IDs sequentially. The authors are exploring ways to balance computational effort across stages.
  • Stopping Criteria: The paper does not discuss specific stopping criteria for the algorithm, leaving this as an open area.
  • Hyper-greedy Approach: The authors mention exploring a "hyper-greedy" approach as a future direction.

Summary updated

BibTeX
@inproceedings{horsch1996flexible,
  author = {Michael C. Horsch and David L. Poole},
  title = {{Flexible Policy Construction by Information Refinement}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1996},
}
Figure