Technical Summary: Shaping Zero-Shot Coordination via State Blocking

Problem Statement

Zero-Shot Coordination (ZSC) aims to enable multi-agent systems to cooperate with independently trained partners (including humans) without prior joint interaction. While existing methods like Self-Play (SP) are effective for agents trained together, they often converge to a single coordination convention, leading to severe performance degradation when paired with partners trained under different random seeds or methods (Cross-Play, XP).

Prior approaches attempt to mitigate this by increasing partner diversity through populations, randomized policies, or environment modification. However, these strategies often fail to capture a diverse set of structured suboptimal coordination modes. They either produce behaviors that are too similar to the optimal convention or introduce unstructured variability that does not generalize well. Furthermore, environment-diversity approaches often require explicit access to or modification of the environment, which limits their applicability. The core challenge remains: how to systematically expose an ego agent to a diverse set of structured, suboptimal partner behaviors without modifying the underlying environment or requiring external human data.

Methodology: State-Blocked Coordination (SBC)

The authors propose State-Blocked Coordination (SBC), a framework that induces structured diversity in partner behaviors by creating virtual environmental variations through state blocking.

1. State-Blocked MDP (SB-MDP)

SBC defines a modified Markov Decision Process where specific states are designated as "penalty states."

• Mechanism: A set of penalty states $\tilde{S}$ is selected from the replay buffer. The reward function is modified to penalize transitions into these states:
  $$\tilde{R}(s_t, a_t, s_{t+1}; \tilde{S}) = R(s_t, a_t, s_{t+1}) - \alpha \sum_{\tilde{s} \in \tilde{S}} \frac{1}{\|s_{t+1} - \tilde{s}\|^2 + \epsilon}$$
  where $\alpha$ is the penalty coefficient.
• Effect: By forcing partners to avoid specific states while still completing the task, the SB-MDP induces distinct, locally optimal coordination strategies. These strategies represent structured suboptimal behaviors that differ from the global optimum but remain task-valid.

2. Training Procedure

SBC employs a two-stage training process involving a blocking-aware policy and a normal ego policy:

• Blocking-Aware Policy ($\tilde{\pi}$): This policy is trained in the SB-MDP. It conditions on the specific set of blocked states $\tilde{S}$ as input. By sampling diverse penalty-state sets during training, the system generates a family of blocking-aware partners, each adhering to a different coordination convention dictated by its specific blocked states.
• Normal Ego Policy ($\pi_e$): The final policy used at test time is trained in the original MDP (without penalty state inputs). It is exposed to a mixture of:
  1. Standard Self-Play partners (copies of itself).
  2. Blocking-aware partners (trained in SB-MDPs but acting in the original MDP during the ego's training).
     This exposure allows the ego agent to learn to coordinate with a broad spectrum of structured behaviors without overfitting to a single convention.

3. Value-Guided Penalty-State Scheduling

To prevent the selection of penalty states that are critical to task completion (which would degrade partner performance too severely), SBC introduces a scheduling mechanism:

• Criticality Metric: The value gap $\Delta V(\tilde{s}) = V^{\pi}(s_0) - \tilde{V}^{\tilde{\pi}}(s_0, \tilde{s})$ quantifies how much a state's blocking degrades the return.
• Sampling Strategy: Penalty states are sampled with probability $P(\tilde{s}) \propto \exp(-\beta \Delta V(\tilde{s}))$.
• Annealing: The temperature $\beta$ is annealed from 0 to 1. Early in training, sampling is nearly uniform to maximize diversity. Later, the scheduler progressively down-weights highly critical states, focusing on blocking configurations that induce meaningful but not catastrophic suboptimal behaviors.

4. Additional Components

To further enhance robustness, SBC incorporates:

• Partner-Action Prediction: An auxiliary model predicts partner actions, which are fed into the ego policy to aid adaptation.
• Random Action Injection: Partners occasionally execute random actions to improve robustness to deviations.

Key Contributions

1. Framework: Introduction of SBC, a method that generates structured partner diversity via state blocking without modifying the environment's transition dynamics or requiring external data.
2. Mechanism: The formulation of the State-Blocked MDP and the value-guided scheduling strategy to balance diversity with task feasibility.
3. Performance: Demonstration that SBC achieves superior Zero-Shot Coordination performance across multiple benchmarks, significantly reducing the gap between Self-Play and Cross-Play scores.
4. Human-AI Coordination: Validation that SBC effectively coordinates with both human proxies and real human participants, outperforming existing baselines in terms of task return, collision reduction, and perceived coordination fluency.

Experimental Results

The authors evaluated SBC on Multi-Destination Spread and Overcooked v1 (five layouts), comparing against baselines including IPPO, FCP, MEP, E3T, GAMMA, and CEC.

• Multi-Destination Spread: SBC achieved an XP score of 957.2 (vs. 77.4 for IPPO) with a Gap of 24.8 (vs. 912.6 for IPPO). It was the only method to maintain high performance in both SP and XP.
• Overcooked v1: SBC consistently outperformed baselines in Cross-Play across all layouts. For example, in the Coordination Ring layout, SBC achieved an XP of 316 (Gap 17), whereas IPPO scored 41 (Gap 246). SBC also maintained or improved Self-Play performance compared to other methods.
• Held-Out XP: SBC demonstrated robust generalization to partners trained with different ZSC methods, not just different seeds.
• Human-AI Evaluation: In experiments with 40 real human participants, SBC achieved the highest scores on all five layouts. It resulted in the lowest number of collisions per delivery and the highest participant ratings for coordination fluency on a 7-point Likert scale.

Significance and Claims

The paper claims that SBC addresses the fundamental limitation of existing ZSC methods: the inability to construct diverse yet structured suboptimal partner behaviors. By inducing "blocking-aware" partners, SBC exposes the ego agent to a wide range of coordination conventions, enabling robust generalization to unseen partners.

The authors emphasize that:

• SBC does not require explicit environment modification (unlike CEC) or large-scale human data collection.
• The method improves coordination with human partners, suggesting that exposure to diverse, locally optimal strategies helps agents adapt to human idiosyncrasies.
• While SBC introduces hyperparameters ($\alpha$ and $K$), the value-guided scheduling makes the method robust to moderate variations, and the computational overhead is modest compared to the performance gains and compared to heavier baselines like GAMMA or CEC.

The work positions SBC as a practical step toward deploying cooperative AI agents that can seamlessly integrate with independently trained systems and human collaborators in real-world scenarios.