# On-the-fly Strategy Adaptation for ad-hoc Agent Coordination

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 70 references that are in the map.
- First posted on arXiv 8 Mar 2022.

## Builds on (most cited first, 30 of 33)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Rainbow: Combining Improvements in Deep Reinforcement Learning](https://mlsanity.com/paper/1710.02298/) (2017)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Learning to Communicate with Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1605.06676/) (2016)
- [Illuminating search spaces by mapping elites](https://mlsanity.com/paper/1504.04909/) (2015)
- [Learning Multiagent Communication with Backpropagation](https://mlsanity.com/paper/1605.07736/) (2016)
- [On the Utility of Learning about Humans for Human-AI Coordination](https://mlsanity.com/paper/1910.05789/) (2019)
- [Emergence of Grounded Compositional Language in Multi-Agent Populations](https://mlsanity.com/paper/1703.04908/) (2017)
- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- ["Other-Play" for Zero-Shot Coordination](https://mlsanity.com/paper/2003.02979/) (2020)
- [The Hanabi Challenge: A New Frontier for AI Research](https://mlsanity.com/paper/1902.00506/) (2019)
- [Open Problems in Cooperative AI](https://mlsanity.com/paper/2012.08630/) (2020)
- [Collaborating with Humans without Human Data](https://mlsanity.com/paper/2110.08176/) (2021)
- [Effective Diversity in Population Based Reinforcement Learning](https://mlsanity.com/paper/2002.00632/) (2020)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents](https://mlsanity.com/paper/1712.06560/) (2017)
- [Off-Belief Learning](https://mlsanity.com/paper/2103.04000/) (2021)
- [Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1811.01458/) (2018)
- [Multi-Agent Adversarial Inverse Reinforcement Learning](https://mlsanity.com/paper/1907.13220/) (2019)
- [Simplified Action Decoder for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1912.02288/) (2019)
- [Prosocial learning agents solve generalized Stag Hunts better than selfish ones](https://mlsanity.com/paper/1709.02865/) (2017)
- [Multi-Agent Determinantal Q-Learning](https://mlsanity.com/paper/2006.01482/) (2020)
- [Improving Policies via Search in Cooperative Partially Observable Games](https://mlsanity.com/paper/1912.02318/) (2019)
- [Continuous Coordination As a Realistic Scenario for Lifelong Learning](https://mlsanity.com/paper/2103.03216/) (2021)
- [Ridge Rider: Finding Diverse Solutions by Following Eigenvectors of the Hessian](https://mlsanity.com/paper/2011.06505/) (2020)
- [Diverse Agents for Ad-Hoc Cooperation in Hanabi](https://mlsanity.com/paper/1907.03840/) (2019)
- [Survey of Self-Play in Reinforcement Learning](https://mlsanity.com/paper/2107.02850/) (2021)
- [Minibatch Gibbs Sampling on Large Graphical Models](https://mlsanity.com/paper/1806.06086/) (2018)

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

- [Towards Few-shot Coordination: Revisiting Ad-hoc Teamplay Challenge In the Game of Hanabi](https://mlsanity.com/paper/2308.10284/) (2023)
- [Who Needs to Know? Minimal Knowledge for Optimal Coordination](https://mlsanity.com/paper/2306.09309/) (2023)
- [Knowledge-based Reasoning and Learning under Partial Observability in Ad Hoc Teamwork](https://mlsanity.com/paper/2306.00790/) (2023)
- [Zero-Shot Coordination in Ad Hoc Teams with Generalized Policy Improvement and Difference Rewards](https://mlsanity.com/paper/2510.16187/) (2025)
- [On Quantified Observability Analysis in Multiagent Systems](https://mlsanity.com/paper/2310.02614/) (2023)
- [On the Complexity of Learning to Cooperate with Populations of Socially Rational Agents](https://mlsanity.com/paper/2407.00419/) (2024)
- [Zero Shot Coordination for Sparse Reward Tasks with Diverse Reward Shapings](https://mlsanity.com/paper/2604.25076/) (2026)

## Abstract (arXiv)

Training agents in cooperative settings offers the promise of AI agents able to interact effectively with humans (and other agents) in the real world. Multi-agent reinforcement learning (MARL) has the potential to achieve this goal, demonstrating success in a series of challenging problems. However, whilst these advances are significant, the vast majority of focus has been on the self-play paradigm. This often results in a coordination problem, caused by agents learning to make use of arbitrary conventions when playing with themselves. This means that even the strongest self-play agents may have very low cross-play with other agents, including other initializations of the same algorithm. In this paper we propose to solve this problem by adapting agent strategies on the fly, using a posterior belief over the other agents' strategy. Concretely, we consider the problem of selecting a strategy from a finite set of previously trained agents, to play with an unknown partner. We propose an extension of the classic statistical technique, Gibbs sampling, to update beliefs about other agents and obtain close to optimal ad-hoc performance. Despite its simplicity, our method is able to achieve strong cross-play with unseen partners in the challenging card game of Hanabi, achieving successful ad-hoc coordination without knowledge of the partner's strategy a priori.