2018

Multi-Agent Common Knowledge Reinforcement Learning

de Witt, Christian A. Schroeder, Foerster, Jakob N., Farquhar, Gregory et al.

Understand

Cooperative multi-agent reinforcement learning often requires decentralised policies, which severely limit the agents' ability to coordinate their behaviour.

In this paper, we show that common knowledge between agents allows for complex decentralised coordination.
Common knowledge arises naturally in a large number of decentralised cooperative multi-agent tasks, for example, when agents can reconstruct parts of each others' observations.
Since agents an independently agree on their common knowledge, they can execute complex coordinated policies that condition on this knowledge in a fully decentralised fashion.

Built on

An experimental study of apparent behavior
Heider, F. and Simmel, M · 1944
Earlier work this paper cites.
Multi-vehicle Flocking Control with Deep Deterministic Policy Gradient Method
Xu, Z., Lyu, Y., Pan, Q., Hu, J., Zhao, C., and Liu, S · 1948
Earlier work this paper cites.
Subjectivity and correlation in randomized strategies
Aumann, R. J. et al · 1974
Earlier work this paper cites.
The electronic mail game: strategic behavior under "almost common knowledge"
Rubinstein, A · 1989
Earlier work this paper cites.
Probabilistic knowledge and probabilistic common knowledge
Krasucki, P., Parikh, R., and Ndjatou, G · 1991
Earlier work this paper cites.
Simple statistical gradient-following algorithms for connectionist reinforcement learning
Williams, R. J · 1992
Earlier work this paper cites.
Multi-agent reinforcement learning: independent vs. cooperative agents
Tan, M · 1993
Earlier work this paper cites.
A course in game theory
Osborne, M. J. and Rubinstein, A · 1994
Earlier work this paper cites.
The dynamics of reinforcement learning cooperative multiagent systems
Claus, C. and Boutilier, C · 1998
Earlier work this paper cites.
Reinforcement learning: an introduction , volume 1
Sutton, R. S. and Barto, A. G · 1998
Earlier work this paper cites.
Sequential optimality and coordination in multiagent systems
Boutilier, C · 1999
Earlier work this paper cites.
Actor-critic algorithms
Konda, V. R. and Tsitsiklis, J. N · 1999
Earlier work this paper cites.
Policy gradient methods for reinforcement learning with function approximation
Sutton, R. S., McAllester, D. A., Singh, S. P., Mansour, Y., et al · 1999
Earlier work this paper cites.
Hierarchical reinforcement learning with the MAXQ value function decomposition
Dietterich, T. G · 2000
Earlier work this paper cites.
Knowledge and common knowledge in a distributed environment
Halpern, J. Y. and Moses, Y · 2000
Earlier work this paper cites.
Hierarchical multi-agent reinforcement learning
Makar, R., Mahadevan, S., and Ghavamzadeh, M · 2001
Earlier work this paper cites.
Learning to coordinate efficiently: a model-based approach
Brafman, R. I. and Tennenholtz, M · 2003
Earlier work this paper cites.
Sparse cooperative Q-learning
Kok, J. R. and Vlassis, N · 2004
Earlier work this paper cites.
Multiagent reinforcement learning for multi-robot systems: a survey
Yang, E. and Gu, D · 2004
Earlier work this paper cites.

Similar

Parallel repetition: simplifications and the no-signaling case
Holenstein, T · 2007
Cited alongside, same era.
A comprehensive survey of multiagent reinforcement learning
Busoniu, L., Babuska, R., and De Schutter, B · 2008
Cited alongside, same era.
A few good agents: multi-agent social learning
Oh, J. and Smith, S. F · 2008
Cited alongside, same era.
Optimal and approximate Q-value functions for decentralized POMDPs
Oliehoek, F. A., Spaan, M. T. J., and Vlassis, N · 2008
Cited alongside, same era.
An overview of recent progress in the study of distributed multi-agent coordination
Cao, Y., Yu, W., Ren, W., and Chen, G · 2013
Cited alongside, same era.
Decentralized anti-coordination through multi-agent learning
Cigler, L. and Faltings, B · 2013
Cited alongside, same era.
Decentralized stochastic control with partial history sharing: a common information approach, 2013
Nayyar, A., Mahajan, A., and Teneketzis, D · 2013
Cited alongside, same era.
Planning with macro-actions in decentralized POMDPs
Amato, C., Konidaris, G. D., and Kaelbling, L. P · 2014
Cited alongside, same era.
Collective action through common knowledge using a Facebook model
Korkmaz, G., Kuhlman, C. J., Marathe, A., Marathe, M. V., and Vega-Redondo, F · 2014
Cited alongside, same era.
The psychology of coordination and common knowledge
Thomas, K. A., DeScioli, P., Haque, O. S., and Pinker, S · 2014
Cited alongside, same era.
The optimality of correlated sampling
Original
Bavarian, M., Ghazi, B., Haramaty, E., Kamath, P., Rivest, R. L., and Sudan, M · 2016
Cited alongside, same era.
Learning to communicate with deep multi-agent reinforcement learning
Foerster, J., Assael, Y. M., de Freitas, N., and Whiteson, S · 2016
Cited alongside, same era.

Then

Three years of the robocup standard platform league drop-in player competition
Genter, K., Laue, T., and Stone, P · 2017
Later among the works it cites.
Cooperative multi-agent control using deep reinforcement learning
Gupta, J. K., Egorov, M., and Kochenderfer, M · 2017
Later among the works it cites.
Federated control with hierarchical multi-agent deep reinforcement learning
Original
Kumar, S., Shah, P., Hakkani-Tur, D., and Heck, L · 2017
Later among the works it cites.
Learning for multi-robot cooperation in partially observable stochastic environments with macro-actions
Original
Liu, M., Sivakumar, K., Omidshafiei, S., Amato, C., and How, J. P · 2017
Later among the works it cites.
Multi-agent actor-critic for mixed cooperative-competitive environments
Original
Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, P., and Mordatch, I · 2017
Later among the works it cites.
Deep decentralized multi-task multi-agent RL under partial observability
Original
Omidshafiei, S., Pazis, J., Amato, C., How, J. P., and Vian, J · 2017
Later among the works it cites.
Multiagent bidirectionally-coordinated nets for learning to play starcraft combat games
Original
Peng, P., Yuan, Q., Wen, Y., Yang, Y., Tang, Z., Long, H., and Wang, J · 2017
Later among the works it cites.
Agreeing to cross: how drivers and pedestrians communicate
Original
Rasouli, A., Kotseruba, I., and Tsotsos, J. K · 2017
Later among the works it cites.
Value-decomposition networks for cooperative multi-agent learning
Original
Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zambaldi, V., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., et al · 2017
Later among the works it cites.
Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real World
Original
Tobin, J., Fong, R., Ray, A., Schneider, J., Zaremba, W., and Abbeel, P · 2017
Later among the works it cites.
FeUdal Networks for Hierarchical Reinforcement Learning
Original
Vezhnevets, A. S., Osindero, S., Schaul, T., Heess, N., Jaderberg, M., Silver, D., and Kavukcuoglu, K · 2017
Later among the works it cites.
Starcraft II: a new challenge for reinforcement learning
Original
Vinyals, O., Ewalds, T., Bartunov, S., Georgiev, P., Vezhnevets, A. S., Yeo, M., Makhzani, A., Küttler, H., Agapiou, J., Schrittwieser, J., Quan, J., Gaffney, S., Petersen, S., Simonyan, K., Schaul, T., van Hasselt, H., Silver, D., Lillicrap, T. P., Calderone, K., Keet, P., Brunasso, A., Lawrence, D., Ekermo, A., Repp, J., and Tsing, R · 2017
Later among the works it cites.
Counterfactual multi-agent policy gradients
Foerster, J., Farquhar, G., Afouras, T., Nardelli, N., and Whiteson, S · 2018
Closest in time.
Cooperative and Distributed Reinforcement Learning of Drones for Field Coverage
Original
Pham, H. X., La, H. M., Feil-Seifer, D., and Nefian, A · 2018
Closest in time.
QMIX: monotonic value function factorisation for deep multi-agent reinforcement learning
Rashid, T., Samvelyan, M., de Witt, C. S., Farquhar, G., Foerster, J., and Whiteson, S · 2018
Closest in time.
Learning to communicate implicitly by actions
Original
Tian, Z., Zou, S., Warr, T., Wu, L., and Wang, J · 2018
Closest in time.
Training Deep Networks with Synthetic Data: Bridging the Reality Gap by Domain Randomization
Original
Tremblay, J., Prakash, A., Acuna, D., Brophy, M., Jampani, V., Anil, C., To, T., Cameracci, E., Boochoon, S., and Birchfield, S · 2018
Closest in time.
The starcraft multi-agent challenge
Original
Samvelyan, M., Rashid, T., de Witt, C. S., Farquhar, G., Nardelli, N., Rudner, T. G. J., Hung, C.-M., Torr, P. H. S., Foerster, J., and Whiteson, S · 2019
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…