A Minimax Approach to Ad Hoc Teamwork
Victor Villin, Thomas Kleine Buening, Christos Dimitrakakis · 2025
Read A Minimax Approach to Ad Hoc Teamwork by Victor Villin, Thomas Kleine Buening, Christos Dimitrakakis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-02377.txt.
Introduction
Victor Villin, Thomas Kleine Buening, and Christos Dimitrakakis study teamwork among AI agents in a 2025 paper. In ad hoc teamwork, an agent must work well with partners it has never met and cannot train with first. Most past methods assume partners follow one fixed pattern, which can fail badly with odd partners.
The authors take a cautious route: they train for the worst case over a range of possible partners. That stance trades some best-case skill for stronger guarantees when partners surprise them. In tests, including cooking tasks where agents must coordinate, their method proved more robust than self-play and other common training styles. The paper stresses that the choice of training partners shapes how safe a team agent will be.
Catalog record
| CREATOR | Victor Villin, Thomas Kleine Buening, Christos Dimitrakakis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-02377
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Minimax Approach to Ad Hoc Teamwork Victor Villin, Thomas Kleine Buening, Christos Dimitrakakis Abstract . We propose a minimax-Bayes approach to Ad Hoc Teamwork (AHT) that optimizes policies against an adversarial prior over partners, explicitly accounting for uncertainty about partners at time of deployment. Unlike existing methods that assume a specific distribution over partners, our approach improves worst-case performance guarantees. Extensive experiments, including evaluations on coordinated cooking tasks from the Melting Pot suite, show our method’s superior robustness compared to self-play, fictitious play, and best response learning. Our work highlights the importance of selecting an appropriate training distribution over teammates to achieve robustness in AHT. A. El Fallah Seghrouchni, Y. Vorobeychik, S. Das, A. Nowe (eds.) Conference: Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025); May 19 – 23, 2025; Detroit, Michigan, USA 441 1. Introduction Domain generalisation is often crucial in Reinforcement Learning (RL) and is typically assessed by placing an agent in novel environments ( Cobbe et al., 2019 ) . Likewise, in Multi-Agent Reinforcement Learning (MARL), generalisation to new agents can be evaluated by pairing a trained policy with unseen actors ( Barrett et al., 2011 ; Hu et al., 2020 ; Leibo et al., 2021 ; Agapiou et al., 2023 ) . While zero-shot domain adaptation is a valuable property ( Higgins et al., 2017 ; Schäfer, 2022 ) , it is equally important to ensure proper transfer to new behaviours in multi-agent settings, especially in situations where undesired interactions may arise ( Gleave et al., 2019 ) . More specifically, Ad Hoc Teamwork (AHT) occurs when an agent, initially unfamiliar with its teammates, must collaborate to achieve a common goal. In a world where autonomous agents are being progressively introduced in such tasks, cooperation with humans is becoming a major concern ( Stone et al., 2010 ; Ji et al., 2023 ) . Efforts in AHT have primarily focused on learning and inferring behavioural models or teammates types ( Barrett et al., 2011 ; Albrecht et al., 2015 ; Barrett et al., 2017 ; Chen et al., 2020 ; Muglich et al., 2022b ) , adapting to behaviour shifts ( Ravula et al., 2019 ) , and enhancing generalisation by encouraging diversity in partners during training ( Jaderberg et al., 2019 ; Hu et al., 2020 ; Charakorn et al., 2020 ; Lupu et al., 2021 ; Strouse et al., 2021 ) . However, these methods provide limited guarantees on the worst-case AHT performance. A multi-agent system can encompass numerous and diverse scenarios , each characterised by its actors. For example, autonomous cars operate alongside human drivers and other autonomous vehicles. Similarly, in a surgical setting, a robot may need to cooperate with surgeons who have a wide range of different habits and expertise. In each of these scenarios, we can adopt the perspective that the focal actors are controlled by an automated agent, whereas the other actors are viewed as fixed, forming the background of the task ( Leibo et al., 2021 ; Agapiou et al., 2023 ) . These scenarios can be viewed as distinct environments, as each combination of background actors induces different transition dynamics and reward functions. A common practice involves constructing representative scenarios and training a policy on a uniform distribution over them ( Strouse et al., 2021 ; Lupu et al., 2021 ) . However, this only optimises performance for that specific distribution. Recent studies in zero-shot domain transfer showed that selecting an appropriate prior over training environments is key to learning robust policies ( Pinto et al., 2017 ; Dennis et al., 2020 ; Garcin et al., 2023 ; Jiang et al., 2021 ; Buening et al., 2023 ; Li et al., 2024 ) . Intuitively, this insight should apply to the AHT setting as well, suggesting that choosing a specific prior over scenarios/partners may improve the robustness of learned policies. Assuming that no information is available about the teammates at test time (and their distribution), we consider the worst possible prior over the training set of partners given our policy, an idea adopted from the minimax-Bayes concept ( Berger, 1985 ) . Contributions. We make the following contributions: (1) We adapt Minimax-Bayes Reinforcement Learning (MBRL) ( Buening et al., 2023 ) to the AHT setting, reasoning about uncertainty with respect to partners rather than environments (Section 4 ). (2) We examine the advantages of using utility and regret for AHT robustness, and provide solutions to target either metric (Section 5 ). (3) We study out-of-distribution robustness guarantees (Section 6 ). (4) We propose a Gradient Descent-Ascent (GDA) ( Lin et al., 2020 ) based algorithm, in conjunction with policy-gradient methods, and discuss its convergence for softmax policies (Section 7 ). (5) We conduct extensive experiments to evaluate our approach. We deploy learned policies on both seen and unseen scenarios for cooperative problems, including a partially observable cooking task from the Melting Pot suite ( Leibo et al., 2021 ; Agapiou et al., 2023 ) . We compare our approach against Self-Play (SP), Fictitious Play (FP) ( Brown, 1951 ; Heinrich et al., 2015 ) as well as learning a policy w.r.t. a fixed uniform distribution over scenarios ( Lupu et al., 2021 ) , which is related to fictitious co-play ( Strouse et al., 2021 ) , as both learn the best response to a population of policies (Section 8 ). (6) Our results confirm the theory and empirically demonstrate that our approach leads to the most robust solutions for both simple and deep RL coordination tasks, even when teammates are adaptive. 2. Related Work Ad Hoc Teamwork. In AHT, we are interested in developing agents capable of cooperating with other unfamiliar agents without any form of prior coordination ( Rovatsos and Wolf, 2002 ; Stone et al., 2010 ; Barrett et al., 2011 ; Barrett et al., 2017 ) . Popular approaches usually involve some form of Population Play (PP), where policies forming a population are learning by interacting with each other ( Lupu et al., 2021 ; Muglich et al., 2022a ; Leibo et al., 2021 ; Agapiou et al., 2023 ) . Key strategies for ensuring generalisation to new partners include promoting policy diversity within the training population ( Charakorn et al., 2020 ) and preventing overfitting to training partners ( Lanctot et al., 2017 ) . Both Lupu et al. (2021) and Strouse et al. (2021) previously showed that learning a best response to a more diverse population leads to improved generalisation. Additionally, Jaderberg et al. (2019) showed the effectiveness of PP when diversity is encouraged through evolving pseudo-rewards. However, PP still struggles with producing policies that are robustly collaborative with new partners and sometimes exhibits overfitting ( Carroll et al., 2019 ; Leibo et al., 2021 ; Agapiou et al., 2023 ) . To further improve AHT, several works suggest inferring the teammates’ models/types, maintaining a belief about ad hoc partners based on previous interactions within an episode ( Barrett et al., 2011 ; Albrecht et al., 2015 ) . This was shown to help substantially in the partially observable setting ( Gu et al., 2021 ; Ribeiro et al., 2023 ; Dodampegama and Sridharan,