Inference-Based Deterministic Messaging For Multi-Agent Communication

Varun Bhatt, Michael Buro

Abstract

Communication is essential for coordination among humans and animals. Therefore, with the introduction of intelligent agents into the world, agent-to-agent and agent-to-human communication becomes necessary. In this paper, we first study learning in matrix-based signaling games to empirically show that decentralized methods can converge to a suboptimal policy. We then propose a modification to the messaging policy, in which the sender deterministically chooses the best message that helps the receiver to infer the sender's observation. Using this modification, we see, empirically, that the agents converge to the optimal policy in nearly all the runs. We then apply this method to a partially observable gridworld environment which requires cooperation between two agents and show that, with appropriate approximation methods, the proposed sender modification can enhance existing decentralized training methods for more complex domains as well.

Introduction

In cooperative multi-agent reinforcement learning (MARL), agents must often share private information to achieve common goals. However, training agents to communicate effectively from scratch in a decentralized manner is a significant challenge. A common failure mode is the "vicious cycle": if a receiver has not yet learned to interpret a message, it ignores it; consequently, the sender receives no reward signal to make the message informative, leading to underutilized communication channels and suboptimal coordination.

This paper addresses this challenge by introducing a novel communication strategy where the sender agent selects messages by simulating the receiver’s inference process. By deterministically choosing messages that maximize the likelihood of the receiver identifying the true state, agents can break out of suboptimal traps and consistently reach optimal policies.

Methodology: Inference-Based Messaging

The core contribution is Inference-Based Messaging, which shifts the sender's objective from simple trial-and-error mapping to a more structured "mental simulation" of the receiver.

  1. Bayesian Inference: The sender calculates the posterior probability $p(s|m)$, asking: "If I send message $m$, how likely is the receiver to correctly infer that I am in state $s$?"
  2. Deterministic Selection: Instead of a stochastic policy, the sender deterministically selects the message $m$ that maximizes this posterior probability.
  3. Deep RL Approximation: For complex environments like gridworlds, the authors utilize an LSTM to handle partial observability and maintain an exponentially weighted moving average to estimate message probabilities ($p(m)$) across training batches.

Two variants are explored: Info-Q (where the receiver uses Q-Learning) and Info-Policy (where the receiver uses Policy Gradient methods).

Experimental Setup

The approach was evaluated across three distinct environments:

  • The Climbing Game: A 3x3 matrix coordination game characterized by high-reward optimal actions surrounded by high-penalty "traps."
  • Random Payoff Signaling Games: 1,000 randomly generated payoff matrices (sizes 3x3 and 32x32) to test generalizability.
  • Treasure Hunt (Gridworld): A multi-step task where one agent sees the goal and another must reach it, requiring high-fidelity communication.

Results and Analysis

The proposed method demonstrated significant improvements in convergence stability and final performance across all tasks. In the Climbing Game, Info-Q reached the optimal policy in nearly 100% of runs, whereas standard Independent Q-Learning (IQL) frequently converged to suboptimal equilibria.

Comparison of convergence between IQL and Info-Q. IQL often fails to find the optimal diagonal mapping, while Info-Q consistently converges to the optimal policy.

As shown in the heatmap above, IQL often splits its actions between optimal and suboptimal choices, whereas Info-Q's deterministic inference bias forces the agents toward the global optimum. This robustness was even more pronounced in large-scale 32x32 random signaling games, where standard algorithms like Hysteretic-Q and Lenience struggled to scale.

Learning curves showing the percentage of optimal actions over time for various algorithms. Info-Q and Info-Policy significantly outperform standard decentralized methods.

In the gridworld Treasure Hunt task, the inference-based method achieved a final reward of 14.29 ± 1.26, significantly outperforming the "No-Bias" baseline of ~11.55. When combined with other techniques like "positive listening" losses, the performance reached 15.48, setting a new benchmark for these complex domains.

Conclusion and Future Work

Inference-based deterministic messaging effectively bypasses the initial "noise" phase of communication training by forcing the sender to be as understandable as possible from the outset. While the method introduces some computational overhead due to the inference simulation, its ability to stabilize coordination in large state spaces is a significant advancement.

Future research will focus on more efficient inference approximation techniques and testing the framework in high-dimensional, continuous action spaces beyond the current gridworld and matrix game benchmarks.

Summary updated

Abstract

Communication is essential for coordination among humans and animals. Therefore, with the introduction of intelligent agents into the world, agent-to-agent and agent-to-human communication becomes necessary. In this paper, we first study learning in matrix-based signaling games to empirically show that decentralized methods can converge to a suboptimal policy. We then propose a modification to the messaging policy, in which the sender deterministically chooses the best message that helps the receiver to infer the sender's observation. Using this modification, we see, empirically, that the agents converge to the optimal policy in nearly all the runs. We then apply this method to a partially observable gridworld environment which requires cooperation between two agents and show that, with appropriate approximation methods, the proposed sender modification can enhance existing decentralized training methods for more complex domains as well.
BibTeX
@inproceedings{bhatt2021inference,
  author = {Varun Bhatt and Michael Buro},
  title = {{Inference-Based Deterministic Messaging For Multi-Agent Communication}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=TEvoKaeI0kC},
}
Figure