Unbiased Self-Play

Shohei Ohsawa

Abstract

In multi-agent reinforcement learning (MARL), agents often operate in non-cooperative environments with limited local observations. This information asymmetry frequently leads to deceptive communication strategies, where agents withhold or bias information to maximize individual gains, ultimately hindering global coordination. We introduce Truthful Self-Play (TSP), a framework that applies mechanism design principles to decentralized environments. By incorporating "imaginary rewards" and a peer prediction mechanism, TSP incentivizes agents to share honest internal states. Our evaluation across complex tasks—including Predator-Prey, Traffic Junction, and StarCraft: Brood War—demonstrates that TSP significantly outperforms existing communication-based MARL models by fostering emergent honesty and superior coordination.

Introduction

Effective coordination in multi-agent systems relies heavily on the exchange of information. However, in decentralized settings where agents have divergent goals or incomplete world views, communication can become a liability. Without a central authority to verify claims, agents often converge on deceptive local optima. Traditional self-play methods struggle in these scenarios because they lack a mechanism to enforce truthfulness. Truthful Self-Play (TSP) addresses this by treating honesty as a technical requirement for valid state representation, ensuring that shared information is both useful and accurate.

The Truthful Self-Play (TSP) Framework

TSP generalizes standard self-play by introducing a "truth serum" for decentralized agents. The framework is built on three pillars:

1. Imaginary Rewards

To shift agent incentives without altering the environment's fundamental physics, TSP introduces "imaginary rewards." These are internal signals passed between agents that sum to zero across the entire system. While they do not change the total social welfare, they redistribute individual payoffs to favor honest communication.

2. Peer Prediction and Action-Based Verification

A core challenge in MARL is the lack of a ground-truth oracle. TSP overcomes this using a peer prediction method inspired by proper scoring rules. Instead of comparing an agent's message to the "truth," the system evaluates the message based on the subsequent actions of the receiving agents. If a message leads to successful coordination or matches the receiver's later observations, the sender is rewarded; otherwise, it is penalized.

3. Graph Laplacian Regularization

To maintain mathematical stability and ensure rewards remain unbiased, TSP utilizes a graph Laplacian matrix ($\Delta$). This regularization technique distributes penalties for deceptive signaling across the network, keeping the agents' collective focus on the global objective.

Experimental Evaluation

The TSP framework was tested in three diverse multi-agent environments designed to challenge coordination and communication:

Evaluation environments: (a) Predator-Prey grid world, (b) Traffic Junction intersection management, and (c) StarCraft: Brood War combat and exploration tasks.
  • Predator-Prey (PP): A grid-based task where predators with limited vision must communicate to coordinate and trap a mobile prey.
  • Traffic Junction (TJ): A high-density navigation task where up to 20 agents must cross intersections without colliding, requiring precise signaling of intentions.
  • StarCraft: Brood War (SC): Complex scenarios requiring the decoupling of observations, such as Medics finding enemies or Marines coordinating against Zealots.

Key Results and Discussion

TSP was benchmarked against state-of-the-art models, including CommNet and IC3Net.

Performance Gains

In the challenging Traffic Junction (TJ-20) scenario, TSP-optimized agents achieved a score of 132.60, vastly outperforming standard IC3Net (216.31) and CommNet (463.91). Note that in these metrics, lower negative values indicate better performance. Similarly, in StarCraft Combat, TSP reduced the negative reward from 3.815 to 1.717, effectively doubling coordination efficiency.

Emergent Honesty

Beyond raw performance, TSP agents exhibited a marked increase in the "truthfulness" of their communications. Learning curves indicate that while standard agents remain trapped in deceptive patterns, TSP agents rapidly learn to share true state representations, as verified by the peer prediction scores. This suggests that truthfulness is not just a constraint but a catalyst for reaching global optima.

Conclusion and Future Directions

Truthful Self-Play demonstrates that mechanism design can be successfully integrated into decentralized MARL to solve the problem of deceptive communication. By using actions as a proxy for truth, TSP enables agents to reach global optima without a supervisor.

Future work will address the sensitivity of the "mass parameter" ($\beta$), which currently requires manual tuning. Additionally, incorporating social choice theory could ensure that the truthful equilibrium remains fair to all participating agents, preventing scenarios where honesty disproportionately penalizes specific individuals.

Summary updated

BibTeX
@inproceedings{ohsawa2023unbiased,
  author = {Shohei Ohsawa},
  title = {{Unbiased Self-Play}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=WVRb98rwbv9},
}
Figure