Lifting Partially Observable Stochastic Games

Karabulut, Nazlı Nur; Braun, Tanya

Abstract

Partially observable stochastic games (POSGs) are a Markovian formalism used to model a set of agents acting in a stochastic environment, in which each agent has its own reward function. As is common with multi-agent decision making problems, the model and runtime complexity is exponential in the number of agents, which can be prohibitively large. Lifting is a technique that treats groups of indistinguishable instances through representatives if possible, yielding tractable inference in the number of objects in a model. This paper applies lifting to the agent set in POSGs, yielding so-called isomorphic POSGs that have a model complexity no longer dependent on the number of agents, and presents a lifted solution approach that exploits this lifted agent set for space and runtime gains.