Quantifying Zero-shot Coordination Capability with Behavior Preferring
  Partners
Xihuai Wang Shao Zhang Wenhao Zhang Wentao Dong Jingxiao Chen Ying Wen Weinan Zhang
Zero-shot coordination (ZSC) is a new challenge focusing on generalizing
learned coordination skills to unseen partners. Existing methods train the ego
agent with partners from pre-trained or evolving populations. The agent's ZSC
capability is typically evaluated with a few evaluation partners, including
human and agent, and reported by mean returns. Current evaluation methods for
ZSC capability still need to improve in constructing diverse evaluation
partners and comprehensively measuring the ZSC capability. We aim to create a
reliable, comprehensive, and efficient evaluation method for ZSC capability. We
formally define the ideal 'diversity-complete' evaluation partners and propose
the best response (BR) diversity, which is the population diversity of the BRs
to the partners, to approximate the ideal evaluation partners. We propose an
evaluation workflow including 'diversity-complete' evaluation partners
construction and a multi-dimensional metric, the Best Response Proximity
(BR-Prox) metric. BR-Prox quantifies the ZSC capability as the performance
similarity to each evaluation partner's approximate best response,
demonstrating generalization capability and improvement potential. We
re-evaluate strong ZSC methods in the Overcooked environment using the proposed
evaluation workflow. Surprisingly, the results in some of the most used layouts
fail to distinguish the performance of different ZSC methods. Moreover, the
evaluated ZSC methods must produce more diverse and high-performing training
partners. Our proposed evaluation workflow calls for a change in how we
efficiently evaluate ZSC methods as a supplement to human evaluation.