2020

"Other-Play" for Zero-Shot Coordination

Hu, Hengyuan, Lerer, Adam, Peysakhovich, Alex et al.

Understand

We consider the problem of zero-shot coordination - constructing AI agents that can coordinate with novel partners they have not seen before (e.g.

humans).
Standard Multi-Agent Reinforcement Learning (MARL) methods typically focus on the self-play (SP) setting where agents construct strategies by playing the game with themselves repeatedly.
Unfortunately, applying SP naively to the zero-shot coordination problem can produce agents that establish highly specialized conventions that do not carry over to novel partners they have not been trained with.

Built on

The strategy of conflict
Schelling, T. C · 1980
Earlier work this paper cites.
Evolution of smartn players
Stahl, D. O · 1993
Earlier work this paper cites.
The nature of salience: An experimental investigation of pure coordination games
Mehta, J., Starmer, C., and Sugden, R · 1994
Earlier work this paper cites.
Td-gammon, a self-teaching backgammon program, achieves master-level play
Tesauro, G · 1994
Earlier work this paper cites.
Cognition and behavior in normal-form games: An experimental study
Costa-Gomes, M., Crawford, V. P., and Broseta, B · 2001
Earlier work this paper cites.
Deep blue
Campbell, M., Hoane Jr, A. J., and Hsu, F.-h · 2002
Earlier work this paper cites.
Taming decentralized pomdps: Towards efficient policy computation for multiagent settings
Nair, R., Tambe, M., Yokoo, M., Pynadath, D., and Marsella, S · 2003
Earlier work this paper cites.
Approximate homomorphisms: A framework for non-exact minimization in markov decision processes
Ravindran, B. and Barto, A. G · 2004
Earlier work this paper cites.
Multi-agent reinforcement learning: A survey
Busoniu, L., Babuska, R., and De Schutter, B · 2006
Earlier work this paper cites.
Evolutionary dynamics: exploring the equations of life
Nowak, M. A · 2006
Earlier work this paper cites.
Lossless abstraction of imperfect information games
Gilpin, A. and Sandholm, T · 2007
Earlier work this paper cites.
Social reward shaping in the prisoner’s dilemma
Babes, M., Munoz de Cote, E., and Littman, M. L · 2008
Earlier work this paper cites.
Ad hoc autonomous agent teams: Collaboration without pre-coordination
Stone, P., Kaminka, G. A., Kraus, S., and Rosenschein, J. S · 2010
Earlier work this paper cites.
Beyond equilibrium: Predicting human behavior in normal-form games
Wright, J. R. and Leyton-Brown, K · 2010
Earlier work this paper cites.
Empirical evaluation of ad hoc teamwork in the pursuit domain
Barrett, S., Stone, P., and Kraus, S · 2011
Earlier work this paper cites.
Behavioral game theory: Experiments in strategic interaction
Camerer, C. F · 2011
Earlier work this paper cites.
An empirical study of potential-based reward shaping and advice in complex, multi-agent systems
Devlin, S., Kudenko, D., and Grześ, M · 2011
Earlier work this paper cites.

Similar

Plan-based reward shaping for multi-agent reinforcement learning
Devlin, S. and Kudenko, D · 2016
Cited alongside, same era.
Learning to communicate with deep multi-agent reinforcement learning
Foerster, J., Assael, I. A., De Freitas, N., and Whiteson, S · 2016
Cited alongside, same era.
Deep learning for predicting human strategic behavior
Hartford, J. S., Wright, J. R., and Leyton-Brown, K · 2016
Cited alongside, same era.
Coordinate to cooperate or compete: abstract goals and joint intentions in social interaction
Kleiman-Weiner, M., Ho, M. K., Austerweil, J. L., Littman, M. L., and Tenenbaum, J. B · 2016
Cited alongside, same era.
Multi-agent cooperation and the emergence of (natural) language
Original
Lazaridou, A., Peysakhovich, A., and Baroni, M · 2016
Cited alongside, same era.
Learning multiagent communication with backpropagation
Sukhbaatar, S., Fergus, R., et al · 2016
Cited alongside, same era.
An intentional ai for hanabi
Eger, M., Martens, C., and Córdoba, M. A · 2017
Cited alongside, same era.
Stabilising experience replay for deep multi-agent reinforcement learning
Foerster, J., Nardelli, N., Farquhar, G., Afouras, T., Torr, P. H., Kohli, P., and Whiteson, S · 2017
Cited alongside, same era.
The theory is predictive, but is it complete? an application to human perception of randomness
Kleinberg, J., Liang, A., and Mullainathan, S · 2017
Cited alongside, same era.
A unified game-theoretic approach to multiagent reinforcement learning
Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Pérolat, J., Silver, D., and Graepel, T · 2017
Cited alongside, same era.
Maintaining cooperation in complex social dilemmas using deep reinforcement learning
Original
Lerer, A. and Peysakhovich, A · 2017
Cited alongside, same era.
Multi-agent actor-critic for mixed cooperative-competitive environments
Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, O. P., and Mordatch, I · 2017
Cited alongside, same era.

Then

Learning social conventions in markov games
Original
Lerer, A. and Peysakhovich, A · 2018
Later among the works it cites.
Prosocial learning agents solve generalized stag hunts better than selfish ones
Peysakhovich, A. and Lerer, A · 2018
Later among the works it cites.
Vehicle community strategies
Original
Resnick, C., Kulikov, I., Cho, K., and Weston, J · 2018
Later among the works it cites.
Value-decomposition networks for cooperative multi-agent learning based on team reward
Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zambaldi, V., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., et al · 2018
Later among the works it cites.
Shaping representations through communication
Tieleman, O., Lazaridou, A., Mourad, S., Blundell, C., and Precup, D · 2018
Later among the works it cites.
On the utility of learning about humans for human-ai coordination
Carroll, M., Shah, R., Ho, M. K., Griffiths, T., Seshia, S., Abbeel, P., and Dragan, A · 2019
Later among the works it cites.
To populate is to regulate
Original
Fitzgerald, N · 2019
Later among the works it cites.
Predicting and understanding initial play
Fudenberg, D. and Liang, A · 2019
Later among the works it cites.
A survey and critique of multiagent deep reinforcement learning
Hernandez-Leal, P., Kartal, B., and Taylor, M. E · 2019
Later among the works it cites.
Simplified action decoder for deep multi-agent reinforcement learning
Original
Hu, H. and Foerster, J. N · 2019
Later among the works it cites.
Improving policies via search in cooperative partially observable games
Original
Lerer, A., Hu, H., Foerster, J., and Brown, N · 2019
Later among the works it cites.
Learning to learn to communicate, 2019
Lowe, R., Gupta, A., Foerster, J., Kiela, D., and Pineau, J · 2019
Later among the works it cites.
Theory of minds: Understanding behavior in groups through inverse planning
Shum, M., Kleiman-Weiner, M., Littman, M. L., and Tenenbaum, J. B · 2019
Later among the works it cites.
The hanabi challenge: A new frontier for ai research
Bard, N., Foerster, J. N., Chandar, S., Burch, N., Lanctot, M., Song, H. F., Parisotto, E., Dumoulin, V., Moitra, S., Hughes, E., et al · 2020
Closest in time.
Adversarially guided self-play for adopting social conventions
Original
Tucker, M., Zhou, Y., and Shah, J · 2020
Closest in time.
Plannable approximations to mdp homomorphisms: Equivariance under actions
Original
van der Pol, E., Kipf, T., Oliehoek, F. A., and Welling, M · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

&#34;Other-Play&#34; for Zero-Shot Coordination

Understand

Built on

Similar

Then

Beyond the bibliography

Built on

Similar

Then

Beyond the bibliography

"Other-Play" for Zero-Shot Coordination