Speeding Up Exact Solutions of Interactive Dynamic Influence Diagrams Using Action Equivalence

Yifeng Zeng, Prashant DoshiIJCAI 2009 · OpenReview

Abstract

Interactive dynamic influence diagrams (I-DIDs) are graphical models for sequential decision making in partially observable settings shared by other agents. Algorithms for solving I-DIDs face the challenge of an exponentially growing space of candidate models ascribed to other agents over time. Previous approaches for exactly solving I-DIDs group together models having similar solutions into behaviorally equivalent classes and update these classes. We present a new method that, in addition to aggregating behaviorally equivalent models, further groups models that prescribe identical actions at a single time step. We show how to update these augmented classes and prove that our method is exact. The new approach enables us to bound the aggregated model space by the cardinality of other agents' actions. We evaluate its performance and provide empirical results in support.

Introduction

Interactive dynamic influence diagrams (I-DIDs) provide a powerful graphical framework for sequential decision-making in multiagent environments. However, they suffer from a significant computational bottleneck known as the "curse of history." As time progresses, the number of potential models an agent must maintain for its counterparts grows exponentially, making exact solutions difficult to achieve for long horizons.

The Challenge: Model Space Explosion

To act optimally, an agent must predict the actions of others by modeling their beliefs, preferences, and capabilities. In an I-DID, these models are updated with every new observation and action. Previous exact solvers attempted to manage this by grouping models into behaviorally equivalent (BE) classes—sets of models that would produce identical policy trees for all future steps. While helpful, BE still fails to scale for complex, long-term problems because the space of possible policy trees remains vast.

A two-slice I-DID showing the temporal transition of states, actions, and model classes.

Methodology: Action Equivalence

The authors propose a more aggressive aggregation technique called Action Equivalence (AE). This method shifts the focus from long-term behavioral patterns to immediate decision-making.

1. Action vs. Behavioral Equivalence

While behavioral equivalence requires models to be identical across all future time steps, Action Equivalence groups models that prescribe the same optimal action at the current time step. By focusing on what an agent does "now," the complexity of the model space is drastically reduced.

2. Bounding Complexity

A major advantage of this approach is that the number of AE classes is strictly bounded by the cardinality of the other agent's action space ($|A_j|$). Since any agent only has a finite set of actions, this turns an unmanageable exponential growth into a stable computational requirement.

3. Exact Probabilistic Updates

A key contribution of the paper is the proof that this simplification remains mathematically exact. The authors developed a new way to calculate transition probabilities between action classes. Even though models in one action class might diverge in their future behavior, the predictive distribution over the other agent's immediate actions remains identical to the full model set.

Illustration of merging policy trees in the Tiger problem, a technique used to manage model complexity.

Empirical Evaluation

The researchers evaluated the "Exact-AE" method on two classic benchmarks: the Multiagent Tiger Problem and Multiagent Machine Maintenance (MM).

  • Significant Speedup: In Level 2 I-DIDs (where agents model others who are also modeling them), Exact-AE was significantly faster than the previous state-of-the-art (Exact-BE).
  • Extended Horizons: For the Tiger problem, the new method solved for 11 horizons, nearly doubling the 6-horizon limit of previous exact methods. It reached 10 horizons in the Machine Maintenance problem.
  • Efficiency: The results showed that Exact-AE maintains fewer model classes at larger horizons and never exceeds the number of available actions for the other agent.

Conclusion

By focusing on immediate actions rather than exhaustive future contingencies, Action Equivalence provides a breakthrough in solving I-DIDs exactly. This approach not only speeds up computation but also provides a new optimal benchmark for evaluating faster approximation techniques in complex, multiagent environments.

Summary updated

Abstract

Interactive dynamic influence diagrams (I-DIDs) are graphical models for sequential decision making in partially observable settings shared by other agents. Algorithms for solving I-DIDs face the challenge of an exponentially growing space of candidate models ascribed to other agents, over time. Previous approach for exactly solving I-DIDs groups together models having similar solutions into behaviorally equivalent classes and updates these classes. We present a new method that, in addition to aggregating behaviorally equivalent models, further groups models that prescribe identical actions at a single time step. We show how to update these augmented classes and prove that our method is exact. The new approach enables us to bound the aggregated model space by the cardinality of other agents' actions. We evaluate its performance and provide empirical results in support.
BibTeX
@inproceedings{zeng2009speeding,
  author = {Yifeng Zeng and Prashant Doshi},
  title = {{Speeding Up Exact Solutions of Interactive Dynamic Influence Diagrams Using Action Equivalence}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=ByWb_7zObS},
}
Figure