Nash Approximation Gap in Truncated Infinite-horizon Partially Observable Markov Games
This addresses the computational challenge of solving multi-agent sequential decision-making under asymmetric information in infinite-horizon settings, which is incremental as it builds on existing reformulation approaches.
The paper tackles the intractability of infinite-horizon Partially Observable Markov Games (POMGs) by proposing a finite-memory truncation framework that approximates them as finite-state, finite-action Markov games, showing that Nash equilibria of the truncated game are ε-Nash equilibria of the original POMG with ε → 0 as truncation length increases.
Partially Observable Markov Games (POMGs) provide a general framework for modeling multi-agent sequential decision-making under asymmetric information. A common approach is to reformulate a POMG as a fully observable Markov game over belief states, where the state is the conditional distribution of the system state and agents' private information given common information, and actions correspond to mappings (prescriptions) from private information to actions. However, this reformulation is intractable in infinite-horizon settings, as both the belief state and action spaces grow with the accumulation of information over time. We propose a finite-memory truncation framework that approximates infinite-horizon POMGs by a finite-state, finite-action Markov game, where agents condition decisions only on finite windows of common and private information. Under suitable filter stability (forgetting) conditions, we show that any Nash equilibrium of the truncated game is an $\varepsilon$-Nash equilibrium of the original POMG, where $\varepsilon \to 0$ as the truncation length increases.