Tags:indistinguishability, lifting, multi-agent decision making and partially observable stochastic games
Abstract:
Partially observable stochastic games 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 space 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 partially observable stochastic games, reducing the complexity to polynomial, and presents a lifted solution approach.