Compact Representation of Value Function in Partially Observable Stochastic Games

Karel Horák, Branislav Bosanský, Christopher Kiekintveld, Charles A. KamhouaIJCAI 2019 · DOI

TL;DR

This paper tackles the computational intractability of solving Partially Observable Stochastic Games (POSGs) by introducing a novel "summarized abstraction" technique. This method dramatically reduces the dimensionality of the problem by representing player beliefs using compact characteristic vectors (like marginal probabilities), enabling algorithms to scale to much larger, more realistic scenarios.

What Problem Does This Paper Address?

Partially Observable Stochastic Games (POSGs) are powerful models for dynamic multi-agent interactions where players have incomplete information about the game state. However, solving these games is notoriously difficult due to the "curse of dimensionality." Specifically, players need to maintain a probability distribution over possible states (a "belief"). In complex games, especially those with many states, this belief space grows exponentially, making existing algorithms computationally infeasible. This paper aims to overcome this scalability bottleneck by finding a more compact way to represent these beliefs without sacrificing too much solution quality.

Methods

The core innovation is a "summarized abstraction" that projects high-dimensional belief states onto a lower-dimensional space using characteristic vectors. Instead of tracking the full probability distribution over all possible states, the authors propose using marginal probabilities of certain states or properties being true.

Key methodological contributions include:

  • Compact Representation: Defining a characteristic vector x(b) that summarizes a belief b (e.g., x(b) = A * b, where A is a matrix). This allows for a value function V*(x) defined over this compact space.
  • Adapted Fixed-Point Equation: Modifying the standard fixed-point equation for POSGs to work with this compact representation, allowing player 2 (who has perfect information) to choose any belief consistent with the summarized representation.
  • Linear Programming Formulation: Adapting existing linear programming techniques used for solving POSGs to operate on the compact characteristic vectors. This involves modifying constraints to account for the new representation.
  • HSVI Algorithm Modification: Integrating the summarized abstraction into the Heuristic Search Value Iteration (HSVI) algorithm, a state-of-the-art method for solving POSGs. This involves updating the initialization of bounds and the exploration process to use the compact representations.
  • Convexity Proof: Demonstrating that the value function V* in the compact representation remains convex, which is crucial for the stability and convergence of the algorithms.

Datasets

Not discussed in the paper. The authors use randomly generated directed acyclic graphs for their experiments.

Key Insights and Ideas

  • Marginal Probabilities as a Powerful Abstraction: Using marginal probabilities of key properties (like which resources are infected) as characteristic vectors is a surprisingly effective way to capture essential information about the belief state while drastically reducing dimensionality.
  • Scalability is Achievable with Abstraction: The paper demonstrates that by abstracting the belief space, algorithms can scale to problems that were previously intractable, opening up POSGs for more complex, real-world applications.
  • Trade-off Between Quality and Scalability is Minimal: The experimental results show that this abstraction leads to a negligible loss in solution quality (less than 1%) while achieving orders of magnitude improvement in scalability.
  • Domain-Independent Approach: While demonstrated on a cybersecurity example, the core abstraction technique is presented as domain-independent, suggesting its applicability to a wide range of POSG problems.

Key Results

  • Orders of Magnitude Speedup: The proposed algorithm, using summarized abstraction, achieves significantly better scalability compared to the original unabstracted approach, especially for larger problem instances.
  • Negligible Quality Loss: The quality of the solution obtained with the abstracted approach is within 1% of the original approach for the tested instances.
  • Reduced Memory Consumption: The abstracted approach requires significantly less memory, with the 17-vertex instances not exceeding 1GB of memory consumption, whereas the original approach struggled with memory for 11-vertex instances.
  • Practical Solvability: The method enables solving instances that were previously unsolvable due to computational limitations.

Limitations and Future Work

  • Quality Loss: While minimal, there is still a loss in solution quality due to the abstraction. The paper notes that the empirical bounds might be overestimated, suggesting the actual loss could be even smaller.
  • Choice of Characteristic Vectors: The effectiveness of the abstraction depends on the choice of characteristic vectors. The paper suggests that for the cybersecurity domain, marginal probabilities are a good choice, but further research could explore optimal choices for different domains.
  • Upper Bound Representation: Representing the upper bound VUB in the abstracted space was more challenging than the lower bound. The paper outlines a method but acknowledges it's an area that could be further refined.
  • Generalization to Other POSG Subclasses: While the paper focuses on one-sided POSGs, future work could explore extending this abstraction to other subclasses of POSGs.

Summary updated

BibTeX
@inproceedings{horak2019compact,
  author = {Karel Horák and Branislav Bosanský and Christopher Kiekintveld and Charles A. Kamhoua},
  title = {{Compact Representation of Value Function in Partially Observable Stochastic Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/50},
}
Figure