# Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games

arXiv: https://arxiv.org/abs/2106.04958 · HTML: https://mlsanity.com/paper/2106.04958/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 44 references that are in the map.
- First posted on arXiv 9 Jun 2021.

## Builds on (most cited first, 22 of 22)

- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures](https://mlsanity.com/paper/1802.01561/) (2018)
- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [Learning Robust Rewards with Adversarial Inverse Reinforcement Learning](https://mlsanity.com/paper/1710.11248/) (2017)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Google Research Football: A Novel Reinforcement Learning Environment](https://mlsanity.com/paper/1907.11180/) (2019)
- [A Divergence Minimization Perspective on Imitation Learning Methods](https://mlsanity.com/paper/1911.02256/) (2019)
- [Effective Diversity in Population Based Reinforcement Learning](https://mlsanity.com/paper/2002.00632/) (2020)
- [Open-ended Learning in Symmetric Zero-sum Games](https://mlsanity.com/paper/1901.08106/) (2019)
- [Game-Theoretic Multiagent Reinforcement Learning](https://mlsanity.com/paper/2011.00583/) (2020)
- [Towards Playing Full MOBA Games with Deep Reinforcement Learning](https://mlsanity.com/paper/2011.12692/) (2020)
- [Real World Games Look Like Spinning Tops](https://mlsanity.com/paper/2004.09468/) (2020)
- [Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games](https://mlsanity.com/paper/2006.08555/) (2020)
- [Random Expert Distillation: Imitation Learning via Expert Policy Support Estimation](https://mlsanity.com/paper/1905.06750/) (2019)
- [Energy-Based Imitation Learning](https://mlsanity.com/paper/2004.09395/) (2020)
- [Modelling Behavioural Diversity for Learning in Open-Ended Games](https://mlsanity.com/paper/2103.07927/) (2021)
- [Multi-Agent Determinantal Q-Learning](https://mlsanity.com/paper/2006.01482/) (2020)
- [Diversity-Inducing Policy Gradient: Using Maximum Mean Discrepancy to Find a Set of Diverse Policies](https://mlsanity.com/paper/1906.00088/) (2019)
- [GDPP: Learning Diverse Generations Using Determinantal Point Process](https://mlsanity.com/paper/1812.00068/) (2018)
- [Diverse Auto-Curriculum is Critical for Successful Real-World Multiagent Learning Systems](https://mlsanity.com/paper/2102.07659/) (2021)
- [Online Double Oracle](https://mlsanity.com/paper/2103.07780/) (2021)
- [Diversity-Promoting Bayesian Learning of Latent Variable Models](https://mlsanity.com/paper/1711.08770/) (2017)

## Built on by (most cited first, 14 of 14)

- [Maximum Entropy Population-Based Training for Zero-Shot Human-AI Coordination](https://mlsanity.com/paper/2112.11701/) (2021)
- [Offline Pre-trained Multi-Agent Decision Transformer: One Big Sequence Model Tackles All SMAC Tasks](https://mlsanity.com/paper/2112.02845/) (2021)
- [Cooperative Open-ended Learning Framework for Zero-shot Coordination](https://mlsanity.com/paper/2302.04831/) (2023)
- [Continuously Discovering Novel Strategies via Reward-Switching Policy Optimization](https://mlsanity.com/paper/2204.02246/) (2022)
- [TiZero: Mastering Multi-Agent Football with Curriculum Learning and Self-Play](https://mlsanity.com/paper/2302.07515/) (2023)
- [TiKick: Towards Playing Multi-agent Football Full Games from Single-agent Demonstrations](https://mlsanity.com/paper/2110.04507/) (2021)
- [A Game-Theoretic Approach for Improving Generalization Ability of TSP Solvers](https://mlsanity.com/paper/2110.15105/) (2021)
- [Measuring the Non-Transitivity in Chess](https://mlsanity.com/paper/2110.11737/) (2021)
- [Online Markov Decision Processes with Non-oblivious Strategic Adversary](https://mlsanity.com/paper/2110.03604/) (2021)
- [On the Convergence of Fictitious Play: A Decomposition Approach](https://mlsanity.com/paper/2205.01469/) (2022)
- [JiangJun: Mastering Xiangqi by Tackling Non-Transitivity in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2308.04719/) (2023)
- [Fusion-PSRO: Nash Policy Fusion for Policy Space Response Oracles](https://mlsanity.com/paper/2405.21027/) (2024)
- [Diverse Policies Converge in Reward-free Markov Decision Processe](https://mlsanity.com/paper/2308.11924/) (2023)
- [Feint Behaviors and Strategies: Formalization, Implementation and Evaluation](https://mlsanity.com/paper/2403.07932/) (2024)

## Abstract (arXiv)

Measuring and promoting policy diversity is critical for solving games with strong non-transitive dynamics where strategic cycles exist, and there is no consistent winner (e.g., Rock-Paper-Scissors). With that in mind, maintaining a pool of diverse policies via open-ended learning is an attractive solution, which can generate auto-curricula to avoid being exploited. However, in conventional open-ended learning algorithms, there are no widely accepted definitions for diversity, making it hard to construct and evaluate the diverse policies. In this work, we summarize previous concepts of diversity and work towards offering a unified measure of diversity in multi-agent open-ended learning to include all elements in Markov games, based on both Behavioral Diversity (BD) and Response Diversity (RD). At the trajectory distribution level, we re-define BD in the state-action space as the discrepancies of occupancy measures. For the reward dynamics, we propose RD to characterize diversity through the responses of policies when encountering different opponents. We also show that many current diversity measures fall in one of the categories of BD or RD but not both. With this unified diversity measure, we design the corresponding diversity-promoting objective and population effectivity when seeking the best responses in open-ended learning. We validate our methods in both relatively simple games like matrix game, non-transitive mixture model, and the complex textitGoogle Research Football environment. The population found by our methods reveals the lowest exploitability, highest population effectivity in matrix game and non-transitive mixture model, as well as the largest goal difference when interacting with opponents of various levels in textitGoogle Research Football.