💻 computer science

Expected Return Symmetries

This paper introduces "expected return symmetries," a broader class of symmetries that subsumes traditional environment symmetries, enabling agents in decentralized multi-agent settings to achieve superior zero-shot coordination without requiring prior knowledge of ground truth symmetries.

Original authors: Darius Muglich, Johannes Forkel, Elise van der Pol, Jakob Foerster

Published 2026-06-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Darius Muglich, Johannes Forkel, Elise van der Pol, Jakob Foerster

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Left-Handed" vs. "Right-Handed" Dilemma

Imagine two robots are trained separately to play a cooperative game, like a high-stakes version of Hanabi (a card game where you can't see your own cards) or Overcooked (a chaotic cooking simulator). They are both brilliant at the game when playing with themselves.

However, when you take Robot A and pair it with Robot B for the first time, they fail miserably. Why?

Because during their solo training, they accidentally invented their own secret languages.

Robot A learned that if the other player puts a card down, it means "I'm happy."
Robot B learned that the same action means "I'm angry."

In the paper's terms, this is called mutually incompatible symmetry breaking. The robots found a solution that worked for them individually, but because they didn't agree on which version of the solution to use, they are like two people trying to shake hands, but one offers their left hand and the other offers their right. They are both "correct" in their own minds, but they can't coordinate.

The Old Solution: "Other-Play" (The Rulebook Approach)

Previously, researchers tried to fix this by teaching robots to respect the environment's symmetries.

Think of the game environment as a room with four identical doors. If you walk through the North door, you get a reward. If you walk through the South door, you get the exact same reward. The room is "symmetric."

The Old Method: The researchers told the robots, "Hey, North and South are the same. Don't just memorize 'North is good.' Memorize 'Any door that looks like North is good.'"
The Limitation: This works well for obvious things like colors or directions. But it fails when the "sameness" isn't about the room's layout, but about the strategy itself. It's like telling the robots, "It doesn't matter if you wear a red hat or a blue hat," but failing to realize that sometimes, wearing a specific type of hat is the only way to signal "I'm ready to cook" to a partner.

The New Solution: "Expected Return Symmetries" (The "What Works" Approach)

The authors of this paper propose a smarter way to find these hidden connections. Instead of looking at the rules of the room (the environment), they look at the results (the rewards).

They introduce a concept called Expected Return Symmetries.

The Analogy: The "Magic Mirror"
Imagine you have a magic mirror. If you stand in front of it and do a specific dance move, you get a gold star.

Old View: The mirror only reflects things that look exactly the same (e.g., if you raise your left hand, the reflection raises its right hand).
New View (Expected Return): The mirror is smarter. It asks, "If I change your dance move to something completely different, do you still get a gold star?"

If the answer is yes, then those two different dance moves are "symmetric" in the eyes of the paper. They might look totally different, but they lead to the same success.

The paper argues that by training robots to recognize these "result-based" symmetries, they become much more flexible. They learn that "Action X" and "Action Y" are interchangeable because they both lead to a happy outcome, even if the game rules don't explicitly say they are the same.

How They Did It (The "Trial and Error" Machine)

The paper doesn't just guess these symmetries; they built a method to find them automatically.

The Pool of Experts: They first trained a bunch of robots to be experts at the game (using a method called Self-Play).
The Shuffling Game: They then took these expert robots and started "shuffling" their behaviors. They tried swapping actions, changing observations, and mixing up strategies.
The Scorekeeper: They asked, "If we swap Robot A's strategy with Robot B's strategy, do they still get the same high score?"
- If the score stays high, that swap is a valid "Expected Return Symmetry."
- If the score crashes, that swap is bad.
The Result: They found a set of "magic swaps" that preserve the success of the game. They then taught new robots to use these swaps during training.

The Results: Why It Matters

The paper tested this on three different scenarios:

A Simple Lever Game: A basic coordination task.
Overcooked V2: A complex cooking game where timing and communication are key.
Hanabi: A very difficult card game with hidden information.

The Findings:

Robots trained with this new "Expected Return" method coordinated significantly better with strangers than robots trained with the old "Environment Symmetry" method.
In the Overcooked game, the new method reduced the gap between "playing with yourself" and "playing with a stranger" by a huge margin.
In Hanabi, which is notoriously hard for AI to coordinate on, the new method outperformed the previous state-of-the-art methods, even though the new method didn't have a "cheat sheet" of the game's rules (like knowing that Red and Blue are just color swaps).

The Bottom Line

The paper claims that to make AI agents work well together without prior coordination, we shouldn't just teach them the rules of the game. Instead, we should teach them to recognize which different behaviors lead to the same success.

By focusing on the outcome (the expected return) rather than just the input (the environment's layout), the robots learn a broader, more flexible set of "secret handshakes." This allows them to adapt to new partners much faster and more effectively, solving the "left hand vs. right hand" problem that has plagued multi-agent AI for years.

Technical Summary: Expected Return Symmetries

Problem Statement
In cooperative multi-agent reinforcement learning (MARL), a fundamental challenge is Zero-Shot Coordination (ZSC): the ability of agents trained independently to coordinate effectively with new partners at test time without prior communication. A primary failure mode in ZSC is mutually incompatible symmetry breaking. When agents train in isolation, they may converge on equivalent but incompatible policies (e.g., one team agrees to signal "play" with the color blue, while another uses red).

Existing solutions, such as the Other-Play (OP) objective, address this by enforcing compatibility among policies equivalent under Dec-POMDP symmetries (relabelings of states, actions, and observations that leave transition and reward functions invariant). However, this approach has two limitations:

Coordination Failure Modes: Environmental symmetry breaking is only one type of coordination failure. Agents may still over-coordinate by forming overly specific conventions even in the absence of non-trivial Dec-POMDP symmetries.
Accessibility of Symmetries: Current methods require a priori knowledge of the environment's symmetries. Automatically discovering these symmetries in large-scale Dec-POMDPs is often computationally infeasible, and many methods rely on privileged information (e.g., ground truth dynamics or symmetry groups) that is unavailable in real-world settings.

Methodology
The paper introduces Expected Return (ER) Symmetries, a broader class of symmetries that contains Dec-POMDP symmetries as a subgroup.

Definition: A transformation $\phi$ is an ER symmetry if it preserves the set of self-play optimal Boltzmann-exploratory policies ( $\Pi^*_\alpha$ ). Specifically, $\Phi_{ER} = \{ \phi \in \Psi \mid \forall \pi \in \Pi^*_\alpha: \phi(\pi) \in \Pi^*_\alpha \}$ . Unlike Dec-POMDP symmetries, which require invariance of the transition and reward functions, ER symmetries only require that the transformation maps optimal policies to other optimal policies (preserving expected return).
Theoretical Properties: The authors prove that $\Phi_{ER}$ forms a group under function composition. Crucially, $\Phi_{ER}$ is a strict superset of Dec-POMDP symmetries in many cases, capturing coordination differences based on strategy rather than just label permutations.
Learning Algorithm: Since $\Phi_{ER}$ $Φ_{E R}$ is not known a priori, the paper proposes scalable methods to learn approximate ER symmetries using gradient-based optimization without access to ground truth symmetries or environment dynamics.
- Objective 1 (Return Preservation): Maximize the expected return of transformed policies: $\max_\theta \mathbb{E}_{\pi \sim \Pi'} [J(\phi_\theta(\pi))]$ , where $\Pi'$ is a pool of self-play optimal policies.
- Objective 2 (Compositionality & Invertibility): A regularized objective is introduced to ensure the learned transformations form a group (enforcing closure and invertibility) by penalizing deviations from identity after double application and maximizing returns under composed transformations.
- Objective 3 (Cross-Play Maximization): An alternative approach optimizes directly for cross-play performance between pairs of policies.
- The method assumes minimal structure: it fixes the state transformation to identity and learns observation and action transformations (often via search over action permutations and neural networks for observations).

Key Contributions

Definition of ER Symmetries: The paper defines a new symmetry group based on the preservation of expected returns for optimal policies, which subsumes traditional Dec-POMDP symmetries.
Model-Free Discovery: The authors introduce algorithms to learn these symmetries purely from agent-environment interactions, requiring no privileged information about the environment's structure or dynamics.
Improved ZSC Performance: The paper demonstrates that combining the OP learning rule with learned ER symmetries significantly outperforms standard self-play and OP with Dec-POMDP symmetries in preventing over-coordination.
Robustness in Challenging Settings: The method is shown to succeed in environments where state-of-the-art methods like Off-Belief Learning (OBL) and Cognitive Hierarchies fail (e.g., specific lever games and Overcooked V2).

Experimental Results
The authors evaluate their method across four environments:

Iterated Three-Lever Game: In this setting, ER symmetries coincide with Dec-POMDP symmetries, and the method successfully recovers the optimal ZSC policy.
Toy Coordination Game: The method successfully recovers a non-trivial ER symmetry (an action swap) that is not a Dec-POMDP symmetry, demonstrating the ability to discover symmetries outside the traditional group.
Overcooked V2: In this asymmetric, stochastic benchmark, agents using learned ER symmetries achieved a mean cross-play (XP) score of 15.8, significantly outperforming the self-play baseline (6.74) and reducing the variance in coordination outcomes.
Hanabi: In this complex card game, agents using 11 learned ER symmetries achieved a mean XP score of 21.64, outperforming both the standard IPPO baseline (4.02) and the IPPO baseline constrained by all 120 known Dec-POMDP symmetries (8.61). The results indicate that ER symmetries better preserve optimality while enforcing compatibility.

Significance and Claims
The paper claims that Expected Return Symmetries represent a significant advancement in ZSC by:

Generalizing Symmetry: Moving beyond rigid environmental invariances to a more flexible, policy-centric definition of symmetry that better addresses the diversity of optimal strategies.
Removing Privileged Information: Being the first symmetry-based method to improve ZSC without requiring a priori knowledge of symmetries or dynamics, making it applicable to settings where such information is unavailable.
Solving Coordination Failures: Providing a solution to over-coordination that is effective even in environments where previous symmetry-based or diversity-based methods (like OBL) fail.

The authors acknowledge limitations, noting that the expressivity of the search space (restricted to bijections on action/observation spaces) may not be sufficient for all environments (e.g., the two-lever game variant) and that the success of the method depends on the quality of the policies used to learn the symmetries.