Partially Observable Multi-Agent Reinforcement Learning with Information Sharing

Researchers Xiangyu Liu and Kaiqing Zhang have published a significant theoretical advance in multi-agent reinforcement learning (MARL), tackling the long-standing challenge of Partially Observable Stochastic Games (POSGs). In these environments, like teams of robots or autonomous vehicles, each agent operates with incomplete, local information, making optimal coordination notoriously difficult and computationally hard. The paper, the final journal version of an ICML 2023 conference paper accepted to SIAM Journal on Control and Optimization, establishes that leveraging information-sharing among agents is not just an empirical trick but a theoretical necessity for tractability. Their analysis provides concrete computational complexity results, justifying why assumptions of shared common information are required to move beyond intractable oracles and exponential-time solutions.

The core innovation is a new algorithmic framework that constructs an approximate model of the POSG by strategically approximating the shared information. Within this model, the algorithm can find an approximate equilibrium—a stable set of strategies for all agents—in quasi-polynomial time. This represents a major leap from the known hardness results that previously plagued the field. Furthermore, the authors extend their framework beyond competitive equilibrium finding to the more challenging problem of finding team-optimal solutions in fully cooperative settings, known as Dec-POMDPs. By formally bridging control theory's well-studied 'information structures' with MARL, this work opens a principled path toward developing sample- and computation-efficient algorithms for real-world multi-agent systems, from warehouse logistics to distributed sensor networks.