A game-theoretic model and best-response learning method for ad hoc coordination in multiagent systems

By Stefano V. Albrecht, Subramanian Ramamoorthy. 2013

134 citations recorded by the source corpus.

The ad hoc coordination problem is to design an ad hoc agent which is able to achieve optimal flexibility and efficiency in a multiagent system that admits no prior coordination between the ad hoc agent and the other agents. We conceptualise this problem formally as a stochastic Bayesian game in which the behaviour of a player is determined by its type. Based on this model, we derive a solution, called Harsanyi-Bellman Ad Hoc Coordination (HBA), which utilises a set of user-defined types to characterise players based on their observed behaviours. We evaluate HBA in the level-based foraging domain, showing that it outperforms several alternative algorithms using just a few user-defined types. We also report on a human-machine experiment in which the humans played Prisoner's Dilemma and Rock-Paper-Scissors against HBA and alternative algorithms. The results show that HBA achieved equal efficiency but a significantly higher welfare and winning rate.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Tasks (2020, background): “In Level-Based Foraging (LBF) [Albrecht and Ramamoorthy, 2013, Albrecht and Stone, 2017] agents must collect food items which are scattered randomly in a grid-world.”
A survey and critique of multiagent deep reinforcement learning (2018, background): “particular in the context of self-play learning and ad-hoc teams [306, 307, 308].”
Comparative Evaluation of Multi-Agent Deep Reinforcement Learning Algorithms (2020, background): “LBF: In Level-Based Foraging [3] (LBF), a group of agents must collect items which are spread randomly in a grid-world.”
Autonomous agents modelling other agents: A comprehensive survey and open problems (2017, methodology): “…ﬀ erent stationary behaviours (Hernandez-Leal et al., 2017; Bard and Bowling, 2007), by deﬁning behaviours as blackbox mappings over the entire interaction history (Albrecht et al., 2016), or by prioritising recent observations over past ones (Albrecht and Ramamoorthy, 2013; Billings et al., 2004).”
Shared Experience Actor-Critic for Multi-Agent Reinforcement Learning (2020, background): “2c: LBF [1, 3] is a mixed cooperative-competitive game which focuses on the coordination of the agents involved.”
Making friends on the fly: Cooperating with new teammates (2017, unknown): “Another approach to scaling ad hoc teamwork beyond only matrix games is the work of Albrecht and Ramamoorthy [4, 5], though they also consider matrix games in their work.”
Towards Open Ad Hoc Teamwork Using Graph-based Policy Learning (2020, methodology): “For comparison, in Wolfpack and LBF we used 100 units.”
A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity (2017, background): “Similarly, ad-hoc coordination is the problem of designing an agent that is able to be flexible and efficient in a multiagent system that admits no prior coordination among the agents (Albrecht and Ramamoorthy, 2013).”
Reasoning about Hypothetical Agent Behaviours and their Parameters (2017, methodology): “Some methods assume discrete (usually finite) type spaces [3, 9, 14] while others assume continuous type spaces [15,36].”