Information State Embedding in Partially Observable Cooperative Multi-Agent Reinforcement Learning

Weichao Mao, Kaiqing Zhang, Erik Miehling, Tamer Basar

Introduction

In cooperative multi-agent reinforcement learning (MARL), agents must coordinate their actions to achieve a shared goal. However, in many real-world scenarios, agents only have partial observability of the environment. To act optimally in these Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs), an agent theoretically needs to track its entire history of observations and actions. This leads to the "curse of history," where the history space grows exponentially over time, making the problem NEXP-complete.

Existing deep learning methods often use end-to-end architectures to handle this complexity, but these "black-box" approaches often lack theoretical performance guarantees and can be unstable. This paper introduces an "embed-then-learn" framework that addresses these challenges by compressing local histories into fixed-size information state embeddings.

The Embed-Then-Learn Framework

The proposed framework decouples the representation of history from the learning of control policies through a two-stage pipeline:

  1. Embed: A compact summary, termed an information state embedding, is extracted from the raw history space. The authors define an $(\epsilon, \delta)$-information state embedding, where $\epsilon$ represents the error in predicting future rewards and $\delta$ represents the error in predicting future beliefs.
  2. Learn: These fixed-size embeddings serve as inputs to standard MARL algorithms, such as Deep Q-Networks, to learn optimal control policies.
The embed-then-learn architecture showing the transition from growing history space to fixed-dimension embedding space, followed by value network learning.

Key Technical Components

  • RNN-E (RNN Embedding): The framework utilizes Recurrent Neural Networks (specifically LSTMs) to map local histories to a fixed-size vector. Unlike standard end-to-end approaches, the LSTM hidden state is treated as a formal information state.
  • Theoretical Error Bounds: A significant contribution of this work is the proof that value function error (expected reward) is bounded linearly by the time horizon $T$ and the compression errors $(\epsilon, \delta)$. This provides a mathematical bridge between representation quality and final policy performance.
  • Parameter Sharing: To mitigate non-stationarity during training, agents share neural network weights, enhancing both stability and training speed.

Experimental Evaluation

The authors evaluated the RNN-E approach against several baselines, including Finite Memory Compression (FMC), Principal Component Analysis Compression (PCAC), and centralized solvers like oSARSA and FB-HSVI. Testing was conducted on classic Dec-POMDP benchmarks:

  • Grid3x3corners: A coordination task where agents must navigate to specific corners.
  • Dectiger: A multi-agent version of the "Tiger" problem requiring coordinated listening before acting.
  • Boxpushing: A task requiring two agents to cooperate to move a heavy object.

Key Results

As shown in the table below, the RNN-E approach achieved competitive performance, often matching or exceeding state-of-the-art centralized solvers and significantly outperforming other learning-based baselines like oSARSA.

Performance comparison across Grid3x3corners, Dectiger, and Boxpushing benchmarks for various horizons (T).

Beyond raw performance, the researchers found that:

  • Memory Superiority: In tasks requiring long-term memory (like a modified Grid3x3corners), RNN-E successfully summarized the entire history, whereas FMC (which only looks at the last $M$ steps) failed.
  • Efficiency: The method converged faster than centralized algorithms that require solving complex linear programs at each step.
  • Predictive Power: Standard variance-based compression (PCA) failed because it does not prioritize the information necessary for predicting future rewards and states, highlighting the importance of the $(\epsilon, \delta)$ formulation.

Conclusion

By separating history embedding from policy learning, this framework provides both a practical tool for solving complex MARL problems and a theoretical foundation for understanding how history compression affects performance. While challenges remain in explicitly quantifying RNN compression errors during training, the linear error propagation proof offers a promising path for future research in robust, scalable multi-agent systems.

Summary updated

BibTeX
@inproceedings{mao2020information,
  author = {Weichao Mao and Kaiqing Zhang and Erik Miehling and Tamer Basar},
  title = {{Information State Embedding in Partially Observable Cooperative Multi-Agent Reinforcement Learning}},
  booktitle = {CDC},
  year = {2020},
  doi = {10.1109/cdc42340.2020.9303801},
}
Figure