Abstract
Partially observable stochastic games (POSGs) are the standard for modeling multi-agent competition under uncertainty, but they suffer from the "nested belief" problem, making them computationally intractable for most real-world scenarios. This paper introduces PO-POSGs, a subclass where public observations synchronize player beliefs. We prove that the value function for these games is convex-concave and present a practical algorithm based on Heuristic Search Value Iteration (HSVI) using a new construct called $\alpha\beta$-vectors. Our method is the first to solve infinite-horizon POSGs with mutual partial information at scale, successfully handling games with hundreds of states in strategic domains like patrolling and Lasertag.
Introduction
In multi-agent systems, POSGs are the "gold standard" for modeling competitive interactions where players have imperfect information and the game can go on indefinitely. A classic example is a security guard patrolling a warehouse while an intruder watches from the shadows. The massive hurdle in solving general POSGs is the problem of nested beliefs: Player A has a belief about the state, but also a belief about Player B’s belief, and a belief about Player B’s belief about Player A’s belief, and so on. This leads to a "doubly-exponential" explosion in complexity, making general POSGs impossible to solve for anything but the smallest toy problems.
Researchers usually circumvent this by simplifying the game (e.g., making it one-sided or finite-horizon). This paper identifies a middle ground: a subclass of games called POSGs with Public Observations (PO-POSGs) that is expressive enough for real-world security scenarios but structured enough to avoid the nested belief trap.
Methodology
The authors propose PO-POSGs based on two key characteristics: a factored state space where players see their own private state perfectly, and the requirement that any information changing a player's belief about their opponent must be public. Because both players see these signals, they can perfectly track what the other player is thinking, which "collapses" the nested belief hierarchy.
The Algorithm: HSVI for PO-POSGs
To solve these games, the authors adapted Heuristic Value Iteration Search (HSVI). In standard POMDPs, a convex value function is represented by $\alpha$-vectors. However, in zero-sum PO-POSGs, the value function is convex in the maximizing player's belief and concave in the minimizing player's belief.
The authors introduced $\alpha\beta$-vectors to represent a linear bound ($\alpha$) positioned at a specific opponent belief ($\beta$). The algorithm explores the belief space and uses Linear Programming (LP) to update upper and lower bounds of the game's value, narrowing the "gap" until it reaches a desired precision ($\epsilon$).
Experimental Evaluation
The algorithm was evaluated on two complex strategic domains:
- Patrolling Games: Based on a defender protecting targets on a graph against an intruder. The authors used random graphs (up to 15 nodes/hundreds of states) generated via the Dorogovtsev-Mendes model.
- Lasertag: A grid-based pursuit-evasion game (3x3 and 4x4 grids) where players move and use a laser to "tag" the opponent. This is a more complex version of the classic "Tag" problem from POMDP literature.
Key Results
The algorithm demonstrated significant scalability, successfully solving patrolling games with hundreds of states. For example, an 11-vertex patrolling instance was solved in approximately 5 minutes (307s).
In the Lasertag domain, the algorithm achieved an average excess gap of only 10% within a 5-hour limit on 4x4 grids, while 3x3 grids were solved in under 8 seconds. This represents the first practical, domain-independent algorithm for infinite-horizon POSGs where both players have partial information about each other.
Conclusion and Future Work
By ensuring that all belief-modifying observations are public, players stay "in sync," removing the need to model recursive beliefs. While the current framework relies on discounted rewards and a factored state assumption, it provides a theoretical guarantee that point-based approximation algorithms like HSVI are viable for this class of games. Future work will explore average-reward objectives and scenarios involving shared environment states that neither player sees perfectly.
Summary updated