Factored Models for Probabilistic Modal Logic

Afsaneh Shirazi, Eyal AmirAAAI 2008

Abstract

Reasoning about nested probabilistic beliefs—what one agent believes about another's knowledge—is fundamental to strategic interaction but suffers from severe state explosion in traditional models. This paper introduces Graphical Kripke Models (GKMs), a factored representation that applies Bayesian Network principles to probabilistic modal logic. By exploiting conditional independence, GKMs allow for efficient reasoning in massive state spaces. We present algorithms for exact and approximate inference, including Ordered Variable Elimination (OVE) and Confidence Sampling (CoSa), demonstrating their effectiveness in complex domains like Texas Hold'em Poker.

Introduction

In artificial intelligence, agents must often navigate "nested" beliefs (e.g., "I think there's a 60% chance you think I'm bluffing"). Standard Probabilistic Modal Logic uses Kripke structures, which represent every possible world state as a node in a graph. However, in games like Texas Hold'em, the state space exceeds $10^{12}$ configurations, making explicit representation impossible. Furthermore, reasoning about nested modalities typically requires multiple iterations through these states. Previous "flat" methods failed to exploit the conditional independence inherent in many real-world variables.

Graphical Kripke Models (GKMs)

The authors propose the Graphical Kripke Model (GKM) to address this bottleneck. Instead of an atomic state graph, a GKM uses a Bayesian Network (BN) to represent relationships between the "actual" state ($Z^a$) and "hypothetical" states ($Z^h$) considered possible by an agent.

A chain of nested beliefs represented as a Graphical Kripke Model.

By factoring states into sets of variables, the model can skip redundant calculations. For instance, if an agent's belief about a specific card does not depend on an opponent's hidden hand, the GKM exploits this independence to maintain a compact representation.

Inference Algorithms

The paper introduces three primary algorithms for reasoning within GKMs:

  1. QuAn (Query Answering): Reduces expectation queries (e.g., "What is the expected value of X?") to standard BN inference.
  2. OVE (Ordered Variable Elimination): Standard BN inference is insufficient for nested inequalities (e.g., $P(\text{Agent 1 thinks } P(\text{Agent 2 thinks X}) > 0.5) > 0.7$). OVE is a modified variable elimination scheme that respects the hierarchical order of these nested probabilistic layers.
  3. CoSa (Confidence Sampling): For models where exact inference is intractable, CoSa provides a sampling-based approach. It addresses the "sampling trap"—where error rates may not converge if a probability is exactly at a threshold—by calculating a confidence level based on sample distribution.

Key Results

The approach was evaluated using simulated games, primarily Texas Hold'em Poker, which provides a high-dimensional state space. The results show that OVE and CoSa significantly outperform previous state-of-the-art methods like KBU and ToDo.

Running time comparison across different inference methods as the depth of nested modal functions increases.

As shown in the performance data, OVE scales linearly with the depth of nested beliefs and is substantially faster than explicit-state methods. In the Poker domain, where explicit models cannot even be stored, GKMs remained compact, and the proposed algorithms returned answers within seconds. Additionally, the CoSa sampling algorithm demonstrated exponential speedups over previous approximate reasoning methods like ARea 10.

Conclusion

GKMs provide a powerful framework for scaling probabilistic modal logic to real-world dimensions. By moving from explicit state graphs to factored Bayesian representations, the authors enable complex strategic reasoning in domains previously considered computationally untouchable. Future work includes extending the framework to dynamic models that update based on observations and developing methods to learn GKMs directly from data.

Summary updated

BibTeX
@inproceedings{shirazi2008factored,
  author = {Afsaneh Shirazi and Eyal Amir},
  title = {{Factored Models for Probabilistic Modal Logic}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure