Counting Agents in Partially Observable Stochastic Games

Karabulut, Nazlı Nur; Braun, Tanya

Abstract

Multi-agent decision-making under uncertainty can be modelled using partially observable stochastic games (POSGs), with numerous agents, partial observability, stochastic dynamics, and individual goals. However, POSGs are notoriously difficult to solve due to their exponential dependence on the number of agents. In this work, we present counting POSGs using the lifting technique of counting to compactly encode symmetries in a POSG, which enables using representative policies. We exploit the encoding for a counting version of the multi-agent dynamic programming operator to solve such a POSG. Doing so reduces the exponential dependence on the number of agents to a polynomial one, making the problem tractable with respect to agent numbers.