Karl Tuyls

JAIR Journal 2025 Journal Article

Empirical Game Theoretic Analysis: A Survey

• Michael P. Wellman
• Karl Tuyls
• Amy Greenwald

In the empirical approach to game-theoretic analysis (EGTA), the model of the game comes not from declarative representation, but is derived by interrogation of a procedural description of the game environment. The motivation for developing this approach was to enable game-theoretic reasoning about strategic situations too complex for analytic specification and solution. Since its introduction over twenty years ago, EGTA has been applied to a wide range of multiagent domains, from auctions and markets to recreational games to cyber-security. We survey the extensive methodology developed for EGTA over the years, organized by the elemental subproblems comprising the EGTA process. We describe key EGTA concepts and techniques, and the questions at the frontier of EGTA research. Recent advances in machine learning are accelerating progress in EGTA, and promise to significantly expand our capacities for reasoning about complex game situations.

JMLR Journal 2024 Journal Article

An Analysis of Quantile Temporal-Difference Learning

• Mark Rowland
• Rémi Munos
• Mohammad Gheshlaghi Azar
• Yunhao Tang
• Georg Ostrovski
• Anna Harutyunyan
• Karl Tuyls
• Marc G. Bellemare

We analyse quantile temporal-difference learning (QTD), a distributional reinforcement learning algorithm that has proven to be a key component in several successful large-scale applications of reinforcement learning. Despite these empirical successes, a theoretical understanding of QTD has proven elusive until now. Unlike classical TD learning, which can be analysed with standard stochastic approximation tools, QTD updates do not approximate contraction mappings, are highly non-linear, and may have multiple fixed points. The core result of this paper is a proof of convergence to the fixed points of a related family of dynamic programming procedures with probability 1, putting QTD on firm theoretical footing. The proof establishes connections between QTD and non-linear differential inclusions through stochastic approximation theory and non-smooth analysis. [abs] [ pdf ][ bib ] &copy JMLR 2024. ( edit, beta )

IJCAI Conference 2024 Conference Paper

Towards a Pretrained Model for Restless Bandits via Multi-arm Generalization

• Yunfan Zhao
• Nikhil Behari
• Edward Hughes
• Edwin Zhang
• Dheeraj Nagaraj
• Karl Tuyls
• Aparna Taneja
• Milind Tambe

Restless multi-arm bandits (RMABs) is a class of resource allocation problems with broad application in areas such as healthcare, online advertising, and anti-poaching. We explore several important question such as how to handle arms opting-in and opting-out over time without frequent retraining from scratch, how to deal with continuous state settings with nonlinear reward functions, which appear naturally in practical contexts. We address these questions by developing a pre-trained model (PreFeRMAB) based on a novel combination of three key ideas: (i) to enable fast generalization, we use train agents to learn from each other's experience; (ii) to accommodate streaming RMABs, we derive a new update rule for a crucial $\lambda$-network; (iii) to handle more complex continuous state settings, we design the algorithm to automatically define an abstract state based on raw observation and reward data. PreFeRMAB allows general zero-shot ability on previously unseen RMABs, and can be fine-tuned on specific instances in a more sample-efficient way than retraining from scratch. We theoretically prove the benefits of multi-arm generalization and empirically demonstrate the advantages of our approach on several challenging, real-world inspired problems.

AAMAS Conference 2024 Conference Paper

Towards Zero Shot Learning in Restless Multi-armed Bandits

• Yunfan Zhao
• Nikhil Behari
• Edward Hughes
• Edwin Zhang
• Dheeraj Nagaraj
• Karl Tuyls
• Aparna Taneja
• Milind Tambe

Restless multi-arm bandits (RMABs), a class of resource allocation problems with broad application in areas such as healthcare, online advertising, and anti-poaching, have recently been studied from a multi-agent reinforcement learning perspective. Prior RMAB research suffers from several limitations, e. g. , it fails to adequately address continuous states, and requires retraining from scratch when arms opt-in and opt-out over time, a common challenge in many real world applications. We propose a neural network-based pre-trained model that has general zero-shot ability on a wide range of previously unseen RMABs.

ICML Conference 2023 Conference Paper

Human-Timescale Adaptation in an Open-Ended Task Space

• Jakob Bauer
• Kate Baumli
• Feryal M. P. Behbahani
• Avishkar Bhoopchand
• Nathalie Bradley-Schmieg
• Michael Chang
• Natalie Clay
• Adrian Collister

Foundation models have shown impressive adaptation and scalability in supervised and self-supervised learning problems, but so far these successes have not fully translated to reinforcement learning (RL). In this work, we demonstrate that training an RL agent at scale leads to a general in-context learning algorithm that can adapt to open-ended novel embodied 3D problems as quickly as humans. In a vast space of held-out environment dynamics, our adaptive agent (AdA) displays on-the-fly hypothesis-driven exploration, efficient exploitation of acquired knowledge, and can successfully be prompted with first-person demonstrations. Adaptation emerges from three ingredients: (1) meta-reinforcement learning across a vast, smooth and diverse task distribution, (2) a policy parameterised as a large-scale attention-based memory architecture, and (3) an effective automated curriculum that prioritises tasks at the frontier of an agent’s capabilities. We demonstrate characteristic scaling laws with respect to network size, memory length, and richness of the training task distribution. We believe our results lay the foundation for increasingly general and adaptive RL agents that perform well across ever-larger open-ended domains.

AAMAS Conference 2023 Conference Paper

Multiagent Learning: From Fundamentals to Foundation Models

• Karl Tuyls

Research in multiagent learning has come a long way over the past few decades, from learning in abstract normal-form games such as Rock-Paper-Scissors, to learning in complex worlds such as Humanoid Soccer, Capture the Flag, Gran Turismo racing, and recently board games such as Diplomacy and Stratego. In this talk I will take you on a journey that starts in the mid 90’s and sheds light on algorithmic progress over the years in multiagent learning systems, uncovering game-theoretic fundamentals for reinforcement learning, adaptability, and decision-making. There have been two major research eras in the field thus far, the predeep multiagent learning and deep multiagent learning periods. I believe we are now at the verge of a third period, multiagent learning with foundation models. We will connect old and new ideas of the first two periods, and lay out interesting challenges ahead of us for the coming era. Specifically, we consider the ways in which the cornerstone ideas of the first two periods may inform the development of generally capable multi-agent foundation models in the future.

JAIR Journal 2022 Journal Article

Evolutionary Dynamics and Phi-Regret Minimization in Games

• Georgios Piliouras
• Mark Rowland
• Shayegan Omidshafiei
• Romuald Elie
• Daniel Hennes
• Jerome Connor
• Karl Tuyls

Regret has been established as a foundational concept in online learning, and likewise has important applications in the analysis of learning dynamics in games. Regret quantifies the difference between a learner’s performance against a baseline in hindsight. It is well known that regret-minimizing algorithms converge to certain classes of equilibria in games; however, traditional forms of regret used in game theory predominantly consider baselines that permit deviations to deterministic actions or strategies. In this paper, we revisit our understanding of regret from the perspective of deviations over partitions of the full mixed strategy space (i.e., probability distributions over pure strategies), under the lens of the previously-established Φ-regret framework, which provides a continuum of stronger regret measures. Importantly, Φ-regret enables learning agents to consider deviations from and to mixed strategies, generalizing several existing notions of regret such as external, internal, and swap regret, and thus broadening the insights gained from regret-based analysis of learning algorithms. We prove here that the well-studied evolutionary learning algorithm of replicator dynamics (RD) seamlessly minimizes the strongest possible form of Φ-regret in generic 2 × 2 games, without any modification of the underlying algorithm itself. We subsequently conduct experiments validating our theoretical results in a suite of 144 2 × 2 games wherein RD exhibits a diverse set of behaviors. We conclude by providing empirical evidence of Φ-regret minimization by RD in some larger games, hinting at further opportunity for Φ-regret based study of such algorithms from both a theoretical and empirical perspective.

AAMAS Conference 2022 Conference Paper

Learning Equilibria in Mean-Field Games: Introducing Mean-Field PSRO

• Paul Muller
• Mark Rowland
• Romuald Elie
• Georgios Piliouras
• Julien Perolat
• Mathieu Lauriere
• Raphael Marinier
• Olivier Pietquin

Recent advances in multiagent learning have seen the introduction of a family of algorithms that revolve around the populationbased training method PSRO, showing convergence to Nash, correlated and coarse correlated equilibria. Notably, when the number of agents increases, learning best-responses becomes exponentially more difficult, and as such hampers PSRO training methods. The field of mean-field games provides an asymptotic solution to this problem when the considered games are anonymoussymmetric. Unfortunately, the mean-field approximation introduces non-linearities which prevent a straightforward adaptation of PSRO. Building upon optimization and adversarial regret minimization, this paper sidesteps this issue and introduces mean-field PSRO, an adaptation of PSRO which learns Nash, coarse correlated and correlated equilibria in mean-field games. The key is to replace the exact distribution computation step by newly-defined mean-field no-adversarial-regret learners, or by black-box optimization. We compare the asymptotic complexity of the approach to standard PSRO, greatly improve empirical bandit convergence speed by compressing temporal mixture weights, and ensure it is theoretically robust to payoff noise. Finally, we illustrate the speed and accuracy of mean-field PSRO on several mean-field games, demonstrating convergence to strong and weak equilibria.

AAMAS Conference 2022 Conference Paper

Scaling Mean Field Games by Online Mirror Descent

• Julien Pérolat
• Sarah Perrin
• Romuald Elie
• Mathieu Laurière
• Georgios Piliouras
• Matthieu Geist
• Karl Tuyls
• Olivier Pietquin

We address the scaling of equilibrium computation in Mean Field Games (MFGs) by using Online Mirror Descent (OMD). We show that continuous-time OMD provably converges to a Nash equilibrium under a natural and well-motivated set of monotonicity assumptions. A thorough experimental investigation on various single and multi-population MFGs shows that OMD outperforms traditional algorithms such as Fictitious Play. We empirically show that OMD scales and converges significantly faster than Fictitious Play by solving, for the first time to our knowledge, examples of MFGs with hundreds of billions states.

NeurIPS Conference 2022 Conference Paper

Turbocharging Solution Concepts: Solving NEs, CEs and CCEs with Neural Equilibrium Solvers

• Luke Marris
• Ian Gemp
• Thomas Anthony
• Andrea Tacchetti
• Siqi Liu
• Karl Tuyls

Solution concepts such as Nash Equilibria, Correlated Equilibria, and Coarse Correlated Equilibria are useful components for many multiagent machine learning algorithms. Unfortunately, solving a normal-form game could take prohibitive or non-deterministic time to converge, and could fail. We introduce the Neural Equilibrium Solver which utilizes a special equivariant neural network architecture to approximately solve the space of all games of fixed shape, buying speed and determinism. We define a flexible equilibrium selection framework, that is capable of uniquely selecting an equilibrium that minimizes relative entropy, or maximizes welfare. The network is trained without needing to generate any supervised training data. We show remarkable zero-shot generalization to larger games. We argue that such a network is a powerful component for many possible multiagent algorithms.

ICML Conference 2021 Conference Paper

From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization

• Julien Pérolat
• Rémi Munos
• Jean-Baptiste Lespiau
• Shayegan Omidshafiei
• Mark Rowland 0001
• Pedro A. Ortega
• Neil Burch
• Thomas W. Anthony 0001

In this paper we investigate the Follow the Regularized Leader dynamics in sequential imperfect information games (IIG). We generalize existing results of Poincar{é} recurrence from normal-form games to zero-sum two-player imperfect information games and other sequential game settings. We then investigate how adapting the reward (by adding a regularization term) of the game can give strong convergence guarantees in monotone games. We continue by showing how this reward adaptation technique can be leveraged to build algorithms that converge exactly to the Nash equilibrium. Finally, we show how these insights can be directly used to build state-of-the-art model-free algorithms for zero-sum two-player Imperfect Information Games (IIG).

JAIR Journal 2021 Journal Article

Game Plan: What AI can do for Football, and What Football can do for AI

• Karl Tuyls
• Shayegan Omidshafiei
• Paul Muller
• Zhe Wang
• Jerome Connor
• Daniel Hennes
• Ian Graham
• William Spearman

The rapid progress in artificial intelligence (AI) and machine learning has opened unprecedented analytics possibilities in various team and individual sports, including baseball, basketball, and tennis. More recently, AI techniques have been applied to football, due to a huge increase in data collection by professional teams, increased computational power, and advances in machine learning, with the goal of better addressing new scientific challenges involved in the analysis of both individual players’ and coordinated teams’ behaviors. The research challenges associated with predictive and prescriptive football analytics require new developments and progress at the intersection of statistical learning, game theory, and computer vision. In this paper, we provide an overarching perspective highlighting how the combination of these fields, in particular, forms a unique microcosm for AI research, while offering mutual benefits for professional teams, spectators, and broadcasters in the years to come. We illustrate that this duality makes football analytics a game changer of tremendous value, in terms of not only changing the game of football itself, but also in terms of what this domain can mean for the field of AI. We review the state-of-the-art and exemplify the types of analysis enabled by combining the aforementioned fields, including illustrative examples of counterfactual analysis using predictive models, and the combination of game-theoretic analysis of penalty kicks with statistical learning of player attributes. We conclude by highlighting envisioned downstream impacts, including possibilities for extensions to other sports (real and virtual).

ICML Conference 2021 Conference Paper

Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers

• Luke Marris
• Paul Muller
• Marc Lanctot
• Karl Tuyls
• Thore Graepel

Two-player, constant-sum games are well studied in the literature, but there has been limited progress outside of this setting. We propose Joint Policy-Space Response Oracles (JPSRO), an algorithm for training agents in n-player, general-sum extensive form games, which provably converges to an equilibrium. We further suggest correlated equilibria (CE) as promising meta-solvers, and propose a novel solution concept Maximum Gini Correlated Equilibrium (MGCE), a principled and computationally efficient family of solutions for solving the correlated equilibrium selection problem. We conduct several experiments using CE meta-solvers for JPSRO and demonstrate convergence on n-player, general-sum games.

ICLR Conference 2020 Conference Paper

A Generalized Training Approach for Multiagent Learning

• Paul Muller
• Shayegan Omidshafiei
• Mark Rowland 0001
• Karl Tuyls
• Julien Pérolat
• Siqi Liu 0002
• Daniel Hennes
• Luke Marris

This paper investigates a population-based training regime based on game-theoretic principles called Policy-Spaced Response Oracles (PSRO). PSRO is general in the sense that it (1) encompasses well-known algorithms such as fictitious play and double oracle as special cases, and (2) in principle applies to general-sum, many-player games. Despite this, prior studies of PSRO have been focused on two-player zero-sum games, a regime where in Nash equilibria are tractably computable. In moving from two-player zero-sum games to more general settings, computation of Nash equilibria quickly becomes infeasible. Here, we extend the theoretical underpinnings of PSRO by considering an alternative solution concept, α-Rank, which is unique (thus faces no equilibrium selection issues, unlike Nash) and applies readily to general-sum, many-player settings. We establish convergence guarantees in several games classes, and identify links between Nash equilibria and α-Rank. We demonstrate the competitive performance of α-Rank-based PSRO against an exact Nash solver-based PSRO in 2-player Kuhn and Leduc Poker. We then go beyond the reach of prior PSRO applications by considering 3- to 5-player poker games, yielding instances where α-Rank achieves faster convergence than approximate Nash solvers, thus establishing it as a favorable general games solver. We also carry out an initial empirical validation in MuJoCo soccer, illustrating the feasibility of the proposed approach in another complex domain.

ICML Conference 2020 Conference Paper

Fast computation of Nash Equilibria in Imperfect Information Games

• Rémi Munos
• Julien Pérolat
• Jean-Baptiste Lespiau
• Mark Rowland 0001
• Bart De Vylder
• Marc Lanctot
• Finbarr Timbers
• Daniel Hennes

We introduce and analyze a class of algorithms, called Mirror Ascent against an Improved Opponent (MAIO), for computing Nash equilibria in two-player zero-sum games, both in normal form and in sequential form with imperfect information. These algorithms update the policy of each player with a mirror-ascent step to maximize the value of playing against an improved opponent. An improved opponent can be a best response, a greedy policy, a policy improved by policy gradient, or by any other reinforcement learning or search techniques. We establish a convergence result of the last iterate to the set of Nash equilibria and show that the speed of convergence depends on the amount of improvement offered by these improved policies. In addition, we show that under some condition, if we use a best response as improved policy, then an exponential convergence rate is achieved.

NeurIPS Conference 2020 Conference Paper

Real World Games Look Like Spinning Tops

• Wojciech M. Czarnecki
• Gauthier Gidel
• Brendan Tracey
• Karl Tuyls
• Shayegan Omidshafiei
• David Balduzzi
• Max Jaderberg

This paper investigates the geometrical properties of real world games (e. g. Tic-Tac-Toe, Go, StarCraft II). We hypothesise that their geometrical structure resembles a spinning top, with the upright axis representing transitive strength, and the radial axis representing the non-transitive dimension, which corresponds to the number of cycles that exist at a particular transitive strength. We prove the existence of this geometry for a wide class of real world games by exposing their temporal nature. Additionally, we show that this unique structure also has consequences for learning - it clarifies why populations of strategies are necessary for training of agents, and how population size relates to the structure of the game. Finally, we empirically validate these claims by using a selection of nine real world two-player zero-sum symmetric games, showing 1) the spinning top structure is revealed and can be easily reconstructed by using a new method of Nash clustering to measure the interaction between transitive and cyclical strategy behaviour, and 2) the effect that population size has on the convergence of learning in these games.

ECAI Conference 2020 Conference Paper

The Automated Inspection of Opaque Liquid Vaccines

• Gregory Palmer
• Benjamin Schnieders
• Rahul Savani
• Karl Tuyls
• Joscha-David Fossel
• Harry Flore

In the pharmaceutical industry the screening of opaque vaccines containing suspensions is currently a manual task carried out by trained human visual inspectors. We show that deep learning can be used to effectively automate this process. A moving contrast is required to distinguish anomalies from other particles, reflections and dust resting on a vial’s surface. We train 3D-ConvNets to predict the likelihood of 20-frame video samples containing anomalies. Our unaugmented dataset consists of hand-labelled samples, recorded using vials provided by the HAL Allergy Group, a pharmaceutical company. We trained ten randomly initialized 3D-ConvNets to provide a benchmark, observing mean AUROC scores of 0. 94 and 0. 93 for positive samples (containing anomalies) and negative (anomaly-free) samples, respectively. Using Frame-Completion Generative Adversarial Networks we: (i) introduce an algorithm for computing saliency maps, which we use to verify that the 3D-ConvNets are indeed identifying anomalies; (ii) propose a novel self-training approach using the saliency maps to determine if multiple networks agree on the location of anomalies. Our self-training approach allows us to augment our data set by labelling 217, 888 additional samples. 3D-ConvNets trained with our augmented dataset improve on the results we get when we train only on the unaugmented dataset.

JAAMAS Journal 2019 Journal Article

Bounds and dynamics for empirical game theoretic analysis

• Karl Tuyls
• Julien Perolat
• Thore Graepel

Abstract This paper provides several theoretical results for empirical game theory. Specifically, we introduce bounds for empirical game theoretical analysis of complex multi-agent interactions. In doing so we provide insights in the empirical meta game showing that a Nash equilibrium of the estimated meta-game is an approximate Nash equilibrium of the true underlying meta-game. We investigate and show how many data samples are required to obtain a close enough approximation of the underlying game. Additionally, we extend the evolutionary dynamics analysis of meta-games using heuristic payoff tables (HPTs) to asymmetric games. The state-of-the-art has only considered evolutionary dynamics of symmetric HPTs in which agents have access to the same strategy sets and the payoff structure is symmetric, implying that agents are interchangeable. Finally, we carry out an empirical illustration of the generalised method in several domains, illustrating the theory and evolutionary dynamics of several versions of the AlphaGo algorithm (symmetric), the dynamics of the Colonel Blotto game played by human players on Facebook (symmetric), the dynamics of several teams of players in the capture the flag game (symmetric), and an example of a meta-game in Leduc Poker (asymmetric), generated by the policy-space response oracle multi-agent learning algorithm.

IJCAI Conference 2019 Conference Paper

Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent

• Edward Lockhart
• Marc Lanctot
• Julien Pérolat
• Jean-Baptiste Lespiau
• Dustin Morrill
• Finbarr Timbers
• Karl Tuyls

In this paper, we present exploitability descent, a new algorithm to compute approximate equilibria in two-player zero-sum extensive-form games with imperfect information, by direct policy optimization against worst-case opponents. We prove that when following this optimization, the exploitability of a player's strategy converges asymptotically to zero, and hence when both players employ this optimization, the joint policies converge to a Nash equilibrium. Unlike fictitious play (XFP) and counterfactual regret minimization (CFR), our convergence result pertains to the policies being optimized rather than the average policies. Our experiments demonstrate convergence rates comparable to XFP and CFR in four benchmark games in the tabular case. Using function approximation, we find that our algorithm outperforms the tabular version in two of the games, which, to the best of our knowledge, is the first such result in imperfect information games among this class of algorithms.

JMLR Journal 2019 Journal Article

Differentiable Game Mechanics

• Alistair Letcher
• David Balduzzi
• Sébastien Racanière
• James Martens
• Jakob Foerster
• Karl Tuyls
• Thore Graepel

Deep learning is built on the foundational guarantee that gradient descent on an objective function converges to local minima. Unfortunately, this guarantee fails in settings, such as generative adversarial nets, that exhibit multiple interacting losses. The behavior of gradient-based methods in games is not well understood -- and is becoming increasingly important as adversarial and multi-objective architectures proliferate. In this paper, we develop new tools to understand and control the dynamics in $n$-player differentiable games. The key result is to decompose the game Jacobian into two components. The first, symmetric component, is related to potential games, which reduce to gradient descent on an implicit function. The second, antisymmetric component, relates to Hamiltonian games, a new class of games that obey a conservation law akin to conservation laws in classical mechanical systems. The decomposition motivates Symplectic Gradient Adjustment (SGA), a new algorithm for finding stable fixed points in differentiable games. Basic experiments show SGA is competitive with recently proposed algorithms for finding stable fixed points in GANs -- while at the same time being applicable to, and having guarantees in, much more general cases. [abs] [ pdf ][ bib ] &copy JMLR 2019. ( edit, beta )

AAMAS Conference 2019 Conference Paper

Fully Convolutional One-Shot Object Segmentation for Industrial Robotics

• Benjamin Schnieders
• Shan Luo
• Gregory Palmer
• Karl Tuyls

The ability to identify and localize new objects robustly and effectively is vital for robotic grasping and manipulation in warehouses or smart factories. Deep convolutional neural networks (DCNNs) have achieved the state-of-the-art performance on established image datasets for object detection and segmentation. However, applying DCNNs in dynamic industrial scenarios, e. g. , warehouses and autonomous production, remains a challenging problem. DCNNs quickly become ineffective when tasked with detecting objects that they have not been trained on. Given that re-training using the latest data is time consuming, DCNNs cannot meet the requirement of the Factory of the Future (FoF) regarding rapid development and production cycles. To address this problem, we propose a novel one-shot object segmentation framework, using a fully convolutional Siamese network architecture, to detect previously unknown objects based on a single prototype image. We turn to multi-task learning to reduce training time and improve classification accuracy. Furthermore, we introduce a novel approach to automatically cluster the learnt feature space representation in a weakly supervised manner. We test the proposed framework on the RoboCup@Work dataset, simulating requirements for the FoF. Results show that the trained network on average identifies 73% of previously unseen objects correctly from a single example image. Correctly identified objects are estimated to have a 87. 53% successful pick-up rate. Finally, multi-task learning lowers the convergence time by up to 33%, and increases accuracy by 2. 99%.

NeurIPS Conference 2019 Conference Paper

Multiagent Evaluation under Incomplete Information

• Mark Rowland
• Shayegan Omidshafiei
• Karl Tuyls
• Julien Perolat
• Michal Valko
• Georgios Piliouras
• Remi Munos

This paper investigates the evaluation of learned multiagent strategies in the incomplete information setting, which plays a critical role in ranking and training of agents. Traditionally, researchers have relied on Elo ratings for this purpose, with recent works also using methods based on Nash equilibria. Unfortunately, Elo is unable to handle intransitive agent interactions, and other techniques are restricted to zero-sum, two-player settings or are limited by the fact that the Nash equilibrium is intractable to compute. Recently, a ranking method called $\alpha$-Rank, relying on a new graph-based game-theoretic solution concept, was shown to tractably apply to general games. However, evaluations based on Elo or $\alpha$-Rank typically assume noise-free game outcomes, despite the data often being collected from noisy simulations, making this assumption unrealistic in practice. This paper investigates multiagent evaluation in the incomplete information regime, involving general-sum many-player games with noisy outcomes. We derive sample complexity guarantees required to confidently rank agents in this setting. We propose adaptive algorithms for accurate ranking, provide correctness and sample complexity guarantees, then introduce a means of connecting uncertainties in noisy match outcomes to uncertainties in rankings. We evaluate the performance of these approaches in several domains, including Bernoulli games, a soccer meta-game, and Kuhn poker.

AAMAS Conference 2019 Conference Paper

Negative Update Intervals in Deep Multi-Agent Reinforcement Learning

• Gregory Palmer
• Rahul Savani
• Karl Tuyls

In Multi-Agent Reinforcement Learning (MA-RL), independent cooperative learners must overcome a number of pathologies to learn optimal joint policies. Addressing one pathology often leaves approaches vulnerable towards others. For instance, hysteretic Qlearning [15] addresses miscoordination while leaving agents vulnerable towards misleading stochastic rewards. Other methods, such as leniency, have proven more robust when dealing with multiple pathologies simultaneously [29]. However, leniency has predominately been studied within the context of strategic form games (bimatrix games) and fully observable Markov games consisting of a small number of probabilistic state transitions. This raises the question of whether these findings scale to more complex domains. For this purpose we implement a temporally extend version of the Climb Game [3], within which agents must overcome multiple pathologies simultaneously, including relative overgeneralisation, stochasticity, the alter-exploration and moving target problems, while learning from a large observation space. We find that existing lenient and hysteretic approaches fail to consistently learn near optimal joint-policies in this environment. To address these pathologies we introduce Negative Update Intervals-DDQN (NUI- DDQN), a Deep MA-RL algorithm which discards episodes yielding cumulative rewards outside the range of expanding intervals. NUI- DDQN consistently gravitates towards optimal joint-policies in our environment, overcoming the outlined pathologies.

AAMAS Conference 2019 Conference Paper

Robust Temporal Difference Learning for Critical Domains

• Richard Klima
• Daan Bloembergen
• Michael Kaisers
• Karl Tuyls

We present a new Q-function operator for temporal difference (TD) learning methods that explicitly encodes robustness against significant rare events (SRE) in critical domains. The operator, which we call the κ-operator, allows to learn a robust policy in a model-based fashion without actually observing the SRE. We introduce singleand multi-agent robust TD methods using the operator κ. We prove convergence of the operator to the optimal robust Q-function with respect to the model using the theory of Generalized Markov Decision Processes. In addition we prove convergence to the optimal Q-function of the original MDP given that the probability of SREs vanishes. Empirical evaluations demonstrate the superior performance of κ-based TD methods both in the early learning phase as well as in the final converged stage. In addition we show robustness of the proposed method to small model errors, as well as its applicability in a multi-agent context.

AAMAS Conference 2019 Conference Paper

Stability of Human-Inspired Agent Societies

• Joe Collenette
• Katie Atkinson
• Daan Bloembergen
• Karl Tuyls

AAMAS Conference 2018 Conference Paper

A Generalised Method for Empirical Game Theoretic Analysis

• Karl Tuyls
• Julien Perolat
• Marc Lanctot
• Joel Z. Leibo
• Thore Graepel

This paper provides theoretical bounds for empirical game theoretical analysis of complex multi-agent interactions. We provide insights in the empirical meta game showing that a Nash equilibrium of the meta-game is an approximate Nash equilibrium of the true underlying game. We investigate and show how many data samples are required to obtain a close enough approximation of the underlying game. Additionally, we extend the meta-game analysis methodology to asymmetric games. The state-of-the-art has only considered empirical games in which agents have access to the same strategy sets and the payoff structure is symmetric, implying that agents are interchangeable. Finally, we carry out an empirical illustration of the generalised method in several domains, illustrating the theory and evolutionary dynamics of several versions of the AlphaGo algorithm (symmetric), the dynamics of the Colonel Blotto game played by human players on Facebook (symmetric), and an example of a meta-game in Leduc Poker (asymmetric), generated by the PSRO multi-agent learning algorithm.

NeurIPS Conference 2018 Conference Paper

Actor-Critic Policy Optimization in Partially Observable Multiagent Environments

• Sriram Srinivasan
• Marc Lanctot
• Vinicius Zambaldi
• Julien Perolat
• Karl Tuyls
• Remi Munos
• Michael Bowling

Optimization of parameterized policies for reinforcement learning (RL) is an important and challenging problem in artificial intelligence. Among the most common approaches are algorithms based on gradient ascent of a score function representing discounted return. In this paper, we examine the role of these policy gradient and actor-critic algorithms in partially-observable multiagent environments. We show several candidate policy update rules and relate them to a foundation of regret minimization and multiagent learning techniques for the one-shot and tabular cases, leading to previously unknown convergence guarantees. We apply our method to model-free multiagent reinforcement learning in adversarial sequential decision problems (zero-sum imperfect information games), using RL-style function approximation. We evaluate on commonly used benchmark Poker domains, showing performance against fixed policies and empirical convergence to approximate Nash equilibria in self-play with rates similar to or better than a baseline model-free algorithm for zero-sum games, without any domain-specific state space reductions.

ICRA Conference 2018 Conference Paper

Distance-Based Multi-Robot Coordination on Pocket Drones

• Bastian Broecker
• Karl Tuyls
• James Butterworth

We present a fully realised system illustrating decentralised coordination on Micro Aerial Vehicles (MAV) or pocket drones, based on distance information. This entails the development of an ultra light hardware solution to determine the distances between the drones and also the development of a model to learn good control policies. The model we present is a combination of a recurrent neural network and a Deep Q-Learning Network (DQN). The recurrent network provides bearing information to the DQN. The DQN itself is responsible for choosing movement actions to avoid collisions and to reach a desired position. Overall we are able provide a complete system which is capable of letting multiple drones navigate in a confined space only based on UWB-distance information and velocity input. We tackle the problem of neural networks and real world sensor noise, by combining the network with a particle filter and show that the combination outperforms the traditional particle filter in terms of converge speed and robustness. A video is available at: https://youtu.be/yj6QqhOzpok.

ICLR Conference 2018 Conference Paper

Emergence of Linguistic Communication from Referential Games with Symbolic and Pixel Input

• Angeliki Lazaridou
• Karl Moritz Hermann
• Karl Tuyls
• Stephen Clark

The ability of algorithms to evolve or learn (compositional) communication protocols has traditionally been studied in the language evolution literature through the use of emergent communication tasks. Here we scale up this research by using contemporary deep learning methods and by training reinforcement-learning neural network agents on referential communication games. We extend previous work, in which agents were trained in symbolic environments, by developing agents which are able to learn from raw pixel data, a more challenging and realistic input representation. We find that the degree of structure found in the input data affects the nature of the emerged protocols, and thereby corroborate the hypothesis that structured compositional language is most likely to emerge when agents perceive the world as being structured.

AAMAS Conference 2018 Conference Paper

Evolving Coverage Behaviours For MAVs Using NEAT

• James Butterworth
• Bastian Broecker
• Karl Tuyls
• Paolo Paoletti

Dynamic coverage - the problem of covering an area evenly and continuously in order to visit all areas of interest - is an important procedure to optimise for any autonomous surveillance system. This work introduces a novel solution to the multi-agent version of this problem in that it achieves high performance in a completely decentralised manner with no reliance on GPS. It does so by using NEAT [12] to optimise agent neural controllers. The controllers are first realised via simulation and then transferred to Micro-Aerial Vehicles (MAVs). The MAVs are modified to include a Ultra-wideband Frequency (UWB) chip which use radio waves to communicate inter drone distances to one another.

JMLR Journal 2018 Journal Article

Experience Selection in Deep Reinforcement Learning for Control

• Tim de Bruin
• Jens Kober
• Karl Tuyls
• Robert Babuška

Experience replay is a technique that allows off-policy reinforcement-learning methods to reuse past experiences. The stability and speed of convergence of reinforcement learning, as well as the eventual performance of the learned policy, are strongly dependent on the experiences being replayed. Which experiences are replayed depends on two important choices. The first is which and how many experiences to retain in the experience replay buffer. The second choice is how to sample the experiences that are to be replayed from that buffer. We propose new methods for the combined problem of experience retention and experience sampling. We refer to the combination as experience selection. We focus our investigation specifically on the control of physical systems, such as robots, where exploration is costly. To determine which experiences to keep and which to replay, we investigate different proxies for their immediate and long-term utility. These proxies include age, temporal difference error and the strength of the applied exploration noise. Since no currently available method works in all situations, we propose guidelines for using prior knowledge about the characteristics of the control problem at hand to choose the appropriate experience replay strategy. [abs] [ pdf ][ bib ] &copy JMLR 2018. ( edit, beta )

IROS Conference 2018 Conference Paper

Fast Convergence for Object Detection by Learning how to Combine Error Functions

• Benjamin Schnieders
• Karl Tuyls

In this paper, we introduce an innovative method to improve the convergence speed and accuracy of object detection neural networks. Our approach, Converge-fast-auxnet, is based on employing multiple, dependent loss metrics and weighting them optimally using an on-line trained auxiliary network. Experiments are performed in the well-known RoboCup@Work challenge environment. A fully convolutional segmentation network is trained on detecting objects' pickup points. We empirically obtain an approximate measure for the rate of success of a robotic pickup operation based on the accuracy of the object detection network. Our experiments show that adding an optimally weighted Euclidean distance loss to a network trained on the commonly used Intersection over Union (IoU) metric reduces the convergence time by 42. 48%. The estimated pickup rate is improved by 39. 90%. Compared to state-of-the-art task weighting methods, the improvement is 24. 5% in convergence, and 15. 8% on the estimated pickup rate.

NeurIPS Conference 2018 Conference Paper

Inequity aversion improves cooperation in intertemporal social dilemmas

• Edward Hughes
• Joel Leibo
• Matthew Phillips
• Karl Tuyls
• Edgar Dueñez-Guzman
• Antonio García Castañeda
• Iain Dunning
• Tina Zhu

Groups of humans are often able to find ways to cooperate with one another in complex, temporally extended social dilemmas. Models based on behavioral economics are only able to explain this phenomenon for unrealistic stateless matrix games. Recently, multi-agent reinforcement learning has been applied to generalize social dilemma problems to temporally and spatially extended Markov games. However, this has not yet generated an agent that learns to cooperate in social dilemmas as humans do. A key insight is that many, but not all, human individuals have inequity averse social preferences. This promotes a particular resolution of the matrix game social dilemma wherein inequity-averse individuals are personally pro-social and punish defectors. Here we extend this idea to Markov games and show that it promotes cooperation in several types of sequential social dilemma, via a profitable interaction with policy learnability. In particular, we find that inequity aversion improves temporal credit assignment for the important class of intertemporal social dilemmas. These results help explain how large-scale cooperation may emerge and persist.

AAMAS Conference 2018 Conference Paper

Lenient Multi-Agent Deep Reinforcement Learning

• Gregory Palmer
• Karl Tuyls
• Daan Bloembergen
• Rahul Savani

Much of the success of single agent deep reinforcement learning (DRL) in recent years can be attributed to the use of experience replay memories (ERM), which allow Deep Q-Networks (DQNs) to be trained efficiently through sampling stored state transitions. However, care is required when using ERMs for multi-agent deep reinforcement learning (MA-DRL), as stored transitions can become outdated when agents update their policies in parallel [9]. In this work we apply leniency [22] to MA-DRL. Lenient agents map state-action pairs to decaying temperature values that control the amount of leniency applied towards negative policy updates that are sampled from the ERM. This introduces optimism in the valuefunction update, and has been shown to facilitate cooperation in tabular fully-cooperative multi-agent reinforcement learning problems. We evaluate our Lenient-DQN (LDQN) empirically against the related Hysteretic-DQN (HDQN) algorithm [20] as well as a modified version we call scheduled-HDQN, that uses average reward learning near terminal states. Evaluations take place in extended variations of the Coordinated Multi-Agent Object Transportation Problem (CMOTP) [6]. We find that LDQN agents are more likely to converge to the optimal policy in a stochastic reward CMOTP compared to standard and scheduled-HDQN agents.

NeurIPS Conference 2018 Conference Paper

Re-evaluating evaluation

• David Balduzzi
• Karl Tuyls
• Julien Perolat
• Thore Graepel

Progress in machine learning is measured by careful evaluation on problems of outstanding common interest. However, the proliferation of benchmark suites and environments, adversarial attacks, and other complications has diluted the basic evaluation model by overwhelming researchers with choices. Deliberate or accidental cherry picking is increasingly likely, and designing well-balanced evaluation suites requires increasing effort. In this paper we take a step back and propose Nash averaging. The approach builds on a detailed analysis of the algebraic structure of evaluation in two basic scenarios: agent-vs-agent and agent-vs-task. The key strength of Nash averaging is that it automatically adapts to redundancies in evaluation data, so that results are not biased by the incorporation of easy tasks or weak agents. Nash averaging thus encourages maximally inclusive evaluation -- since there is no harm (computational cost aside) from including all available tasks and agents.

AAMAS Conference 2018 Conference Paper

SCC-rFMQ Learning in Cooperative Markov Games with Continuous Actions

• Chengwei Zhang
• Xiaohong Li
• Jianye Hao
• Siqi Chen
• Karl Tuyls
• Zhiyong Feng

Although many reinforcement learning methods have been proposed for learning the optimal solutions in single-agent continuous action domains, multiagent coordination domains with continuous action have received relatively few investigations. In this paper, we propose an independent learner hierarchical method, named Sample Continuous Coordination with recursive Frequency Maximum Q-Value (SCC-rFMQ), which divides the coordination problem into two layers. The first layer samples a finite set of actions from the continuous action spaces by a sampling mechanism with variable exploratory rates, and the second layer evaluates the actions in the sampled action set and updates the policy using a multiagent reinforcement learning coordination method. By constructing coordination mechanisms at both levels, SCCrFMQ can handle coordination problems in continuous action cooperative Markov games effectively. Experimental results show that SCC-rFMQ outperforms other reinforcement learning algorithms.

ICML Conference 2018 Conference Paper

The Mechanics of n-Player Differentiable Games

• David Balduzzi
• Sébastien Racanière
• James Martens
• Jakob N. Foerster
• Karl Tuyls
• Thore Graepel

The cornerstone underpinning deep learning is the guarantee that gradient descent on an objective converges to local minima. Unfortunately, this guarantee fails in settings, such as generative adversarial nets, where there are multiple interacting losses. The behavior of gradient-based methods in games is not well understood – and is becoming increasingly important as adversarial and multi-objective architectures proliferate. In this paper, we develop new techniques to understand and control the dynamics in general games. The key result is to decompose the second-order dynamics into two components. The first is related to potential games, which reduce to gradient descent on an implicit function; the second relates to Hamiltonian games, a new class of games that obey a conservation law, akin to conservation laws in classical mechanical systems. The decomposition motivates Symplectic Gradient Adjustment (SGA), a new algorithm for finding stable fixed points in general games. Basic experiments show SGA is competitive with recently proposed algorithms for finding local Nash equilibria in GANs – whilst at the same time being applicable to – and having guarantees in – much more general games.

EWRL Workshop 2018 Workshop Paper

Towards learning to best respond when losing control

• Richard Klima
• Daan Bloembergen
• Michael Kaisers
• Karl Tuyls

Many applications require control policies that are robust against rare but significant deviations, for example caused by hardware failures or adversarial attacks. In this article we propose a reinforcement learning method that uses a prior belief over potential compromisation to learn such a robust policy without requiring observations of the event during training. Our method can be easily combined with different standard reinforcement learning algorithms such as Q-learning and Expected SARSA. Experiments in a multi-agent coordination domain show that our method improves performance of standard algorithms, both with and without communication between the agents that occasionally lose control.

AAMAS Conference 2018 Conference Paper

Value-Decomposition Networks For Cooperative Multi-Agent Learning Based On Team Reward

• Peter Sunehag
• Guy Lever
• Audrunas Gruslys
• Wojciech Marian Czarnecki
• Vinicius Zambaldi
• Max Jaderberg
• Marc Lanctot
• Nicolas Sonnerat

We study the problem of cooperative multi-agent reinforcement learning with a single joint reward signal. This class of learning problems is difficult because of the often large combined action and observation spaces. In the fully centralized and decentralized approaches, we find the problem of spurious rewards and a phenomenon we call the “lazy agent” problem, which arises due to partial observability. We address these problems by training individual agents with a novel value-decomposition network architecture, which learns to decompose the team value function into agent-wise value functions.

NeurIPS Conference 2017 Conference Paper

A multi-agent reinforcement learning model of common-pool resource appropriation

• Julien Pérolat
• Joel Leibo
• Vinicius Zambaldi
• Charles Beattie
• Karl Tuyls
• Thore Graepel

Humanity faces numerous problems of common-pool resource appropriation. This class of multi-agent social dilemma includes the problems of ensuring sustainable use of fresh water, common fisheries, grazing pastures, and irrigation systems. Abstract models of common-pool resource appropriation based on non-cooperative game theory predict that self-interested agents will generally fail to find socially positive equilibria---a phenomenon called the tragedy of the commons. However, in reality, human societies are sometimes able to discover and implement stable cooperative solutions. Decades of behavioral game theory research have sought to uncover aspects of human behavior that make this possible. Most of that work was based on laboratory experiments where participants only make a single choice: how much to appropriate. Recognizing the importance of spatial and temporal resource dynamics, a recent trend has been toward experiments in more complex real-time video game-like environments. However, standard methods of non-cooperative game theory can no longer be used to generate predictions for this case. Here we show that deep reinforcement learning can be used instead. To that end, we study the emergent behavior of groups of independently learning agents in a partially observed Markov game modeling common-pool resource appropriation. Our experiments highlight the importance of trial-and-error learning in common-pool resource appropriation and shed light on the relationship between exclusion, sustainability, and inequality.

NeurIPS Conference 2017 Conference Paper

A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning

• Marc Lanctot
• Vinicius Zambaldi
• Audrunas Gruslys
• Angeliki Lazaridou
• Karl Tuyls
• Julien Perolat
• David Silver
• Thore Graepel

There has been a resurgence of interest in multiagent reinforcement learning (MARL), due partly to the recent success of deep neural networks. The simplest form of MARL is independent reinforcement learning (InRL), where each agent treats all of its experience as part of its (non stationary) environment. In this paper, we first observe that policies learned using InRL can overfit to the other agents' policies during training, failing to sufficiently generalize during execution. We introduce a new metric, joint-policy correlation, to quantify this effect. We describe a meta-algorithm for general MARL, based on approximate best responses to mixtures of policies generated using deep reinforcement learning, and empirical game theoretic analysis to compute meta-strategies for policy selection. The meta-algorithm generalizes previous algorithms such as InRL, iterated best response, double oracle, and fictitious play. Then, we propose a scalable implementation which reduces the memory requirement using decoupled meta-solvers. Finally, we demonstrate the generality of the resulting policies in three partially observable settings: gridworld coordination problems, emergent language games, and poker.

AAMAS Conference 2017 Conference Paper

Decentralised Online Planning for Multi-Robot Warehouse Commissioning

• Daniel Claes
• Frans Oliehoek
• Hendrik Baier
• Karl Tuyls

Warehouse commissioning is a complex task in which a team of robots needs to gather and deliver items as fast and efficiently as possible while adhering to the constraint capacity of the robots. Typical centralised control approaches can quickly become infeasible when dealing with many robots. Instead, we tackle this spatial task allocation problem via distributed planning on each robot in the system. State of the art distributed planning approaches suffer from a number of limiting assumptions and ad-hoc approximations. This paper demonstrates how to use Monte Carlo Tree Search (MCTS) to overcome these limitations and provide scalability in a more principled manner. Our simulation-based evaluation demonstrates that this translates to higher task performance, especially when tasks get more complex. Moreover, this higher performance does not come at the cost of scalability: in fact, the proposed approach scales better than the previous best approach, demonstrating excellent performance on an 8-robot team servicing a warehouse comprised of over 200 locations.

KER Journal 2017 Journal Article

Environmental effects on simulated emotional and moody agents

• Joe Collenette
• Katie Atkinson
• Daan Bloembergen
• Karl Tuyls

Abstract Psychological models have been used to simulate emotions within agents as part of the decision-making process. The body of this work has focussed on applying the process of decision making using emotions to social dilemmas, notably the Prisoner’s Dilemma. Previous work has focussed on agents which do not move around, with an initial analysis on how mobility and the environment can affect the decisions chosen. Additionally simulated mood has been introduced to the decision-making process. Exploring simulated emotions and mood to inform the decision-making process in multi-agent systems allows us to explore in further detail how outside influences can have an effect on different strategies. We expand and clarify aspects of how agents are affected by environmental differences. We show how emotional characters settle on an outcome without deviation by providing a formal proof. We validate how the addition of mood increases cooperation, while also showing how small groups achieve this quicker than large groups. Once pure defectors are added, to test the resilience of the cooperation achieved, we see that while agents with a low starting mood achieve a payoff closest to the pure defectors, they are reduced in numbers the most by the pure defectors.

EUMAS Conference 2017 Invited Paper

Multiagent Learning Paradigms

• Karl Tuyls
• Peter Stone 0001

Abstract “Perhaps a thing is simple if you can describe it fully in several different ways, without immediately knowing that you are describing the same thing” – Richard Feynman This articles examines multiagent learning from several paradigmatic perspectives, aiming to bring them together within one framework. We aim to provide a general definition of multiagent learning and lay out the essential characteristics of the various paradigms in a systematic manner by dissecting multiagent learning into its main components. We show how these various paradigms are related and describe similar learning processes but from varying perspectives, e. g. an individual (cognitive) learner vs. a population of (simple) learning agents.

IROS Conference 2017 Conference Paper

NOctoSLAM: Fast octree surface normal mapping and registration

• Joscha-David Fossel
• Karl Tuyls
• Benjamin Schnieders
• Daniel Claes
• Daniel Hennes

In this paper, we introduce a SLAM front end called NOctoSLAM. The approach adopts an octree-based map representation that implicitly enables source and reference data association for point to plane ICP registration. Additionally, the data structure is used to group map points to approximate surface normals. The multi-resolution capability of octrees, achieved by aggregating information in parent nodes, enables us to compensate for spatially unbalanced sensor data typically provided by multi-line lidar sensors. The octree-based data association is only approximate, but our empirical evaluation shows that NOctoSLAM achieves the same pose estimation accuracy as a comparable, point cloud based approach. However, NOctoSLAM can perform twice as many registration iterations per time unit. In contrast to point cloud based surface normal maps, where the map update duration depends on the current map size, we achieve a constant map update duration including surface normal recalculation. Therefore, NOctoSLAM does not require elaborate and environment dependent data filters. The results of our experiments show a mean positional error of 0. 029 m and 0. 019 rad, with a low standard deviation of 0. 005 m and 0. 006 rad, outperforming the state-of-the-art by remaining accurate while running online.

IROS Conference 2016 Conference Paper

Improved deep reinforcement learning for robotics through distribution-based experience retention

• Tim de Bruin
• Jens Kober
• Karl Tuyls
• Robert Babuska

Recent years have seen a growing interest in the use of deep neural networks as function approximators in reinforcement learning. In this paper, an experience replay method is proposed that ensures that the distribution of the experiences used for training is between that of the policy and a uniform distribution. Through experiments on a magnetic manipulation task it is shown that the method reduces the need for sustained exhaustive exploration during learning. This makes it attractive in scenarios where sustained exploration is in-feasible or undesirable, such as for physical systems like robots and for life long learning. The method is also shown to improve the generalization performance of the trained policy, which can make it attractive for transfer learning. Finally, for small experience databases the method performs favorably when compared to the recently proposed alternative of using the temporal difference error to determine the experience sample distribution, which makes it an attractive option for robots with limited memory capacity.

ICRA Conference 2016 Conference Paper

Local histogram matching for efficient optical flow computation applied to velocity estimation on pocket drones

• Kimberly McGuire
• Guido C. H. E. de Croon
• Christophe De Wagter
• Bart D. W. Remes
• Karl Tuyls
• Hilbert J. Kappen

Autonomous flight of pocket drones is challenging due to the severe limitations on on-board energy, sensing, and processing power. However, tiny drones have great potential as their small size allows maneuvering through narrow spaces while their small weight provides significant safety advantages. This paper presents a computationally efficient algorithm for determining optical flow, which can be run on an STM32F4 microprocessor (168 MHz) of a 4 gram stereo-camera. The optical flow algorithm is based on edge histograms. We propose a matching scheme to determine local optical flow. Moreover, the method allows for sub-pixel flow determination based on time horizon adaptation. We demonstrate velocity measurements in flight and use it within a velocity control-loop on a pocket drone.

ECAI Conference 2016 Conference Paper

Socially-Aware Multiagent Learning: Towards Socially Optimal Outcomes

• Xiaohong Li 0001
• Chengwei Zhang 0001
• Jianye Hao
• Karl Tuyls
• Siqi Chen 0001
• Zhiyong Feng 0002

In multiagent systems the capability of learning is important for an agent to behave appropriately in face of unknown opponents and a dynamic environment. From the system designer's perspective, it is desirable if the agents can learn to coordinate towards socially optimal outcomes, while also avoiding being exploited by selfish opponents. To this end, we propose a novel gradient ascent based algorithm (SA-IGA) which augments the basic gradient-ascent algorithm by incorporating social awareness into the policy update process. We theoretically analyze the learning dynamics of SA-IGA using dynamical system theory, and SA-IGA is shown to have linear dynamics for a wide range of games including symmetric games. The learning dynamics of two representative games (the prisoner's dilemma game and coordination game) are analyzed in detail. Based on the idea of SA-IGA, we further propose a practical multiagent learning algorithm, called SA-PGA, based on the Q-learning update rule. Simulation results show that an SA-PGA agent can achieve higher social welfare than previous social-optimality oriented Conditional Joint Action Learner (CJAL) and also is robust against individually rational opponents by reaching Nash equilibrium solutions.

ECAI Conference 2016 Conference Paper

Space Debris Removal: A Game Theoretic Analysis

• Richard Klíma
• Daan Bloembergen
• Rahul Savani
• Karl Tuyls
• Daniel Hennes
• Dario Izzo

We analyse active space debris removal efforts from a strategic, game-theoretic perspective. An active debris removal mission is a costly endeavour that has a positive effect (or risk reduction) for all satellites in the same orbital band. This leads to a dilemma: each actor (space agency, private stakeholder, etc.) has an incentive to delay its actions and wait for others to respond. The risk of the latter action is that, if everyone waits the joint outcome will be catastrophic leading to what in game theory is referred to as the 'tragedy of the commons'. We introduce and thoroughly analyse this dilemma using simulation and empirical game theory in a two player setting.

IROS Conference 2015 Conference Paper

2D-SDF-SLAM: A signed distance function based SLAM frontend for laser scanners

• Joscha-David Fossel
• Karl Tuyls
• Jürgen Sturm

We introduce a novel approach to simultaneous localization and mapping for robots equipped with a 2D laser scanner. In particular, we propose a fast scan registration algorithm that operates on 2D maps represented as a signed distance function (SDF). Using SDFs as a map representation has several advantages over existing approaches: while classical 2D scan matchers employ brute-force matching to track the position of the robot, signed distance functions are differentiable on large parts of the map. Consequently, efficient minimization techniques such as Gauss-Newton can be applied to find the minimum. In contrast to occupancy grid maps, the environment can be captured with sub-grid cell size precision, which leads to a higher localization accuracy. Furthermore, SDF maps can be triangulated to polygon maps for efficient storage and transfer. In a series of experiments, conducted both in simulation and on a real physical platform, we demonstrate that SDF tracking is more accurate and efficient than previous approaches. We outperform scan matching on occupancy maps in simulation by ~270% in terms of root mean squared deviation (RMSD) with a ~63% lower standard deviation. In the real robot experiments, we obtain a performance advantage of ~14% RMSD with a ~25% lower standard deviation.

JAIR Journal 2015 Journal Article

Evolutionary Dynamics of Multi-Agent Learning: A Survey

• Daan Bloembergen
• Karl Tuyls
• Daniel Hennes
• Michael Kaisers

The interaction of multiple autonomous agents gives rise to highly dynamic and nondeterministic environments, contributing to the complexity in applications such as automated financial markets, smart grids, or robotics. Due to the sheer number of situations that may arise, it is not possible to foresee and program the optimal behaviour for all agents beforehand. Consequently, it becomes essential for the success of the system that the agents can learn their optimal behaviour and adapt to new situations or circumstances. The past two decades have seen the emergence of reinforcement learning, both in single and multi-agent settings, as a strong, robust and adaptive learning paradigm. Progress has been substantial, and a wide range of algorithms are now available. An important challenge in the domain of multi-agent learning is to gain qualitative insights into the resulting system dynamics. In the past decade, tools and methods from evolutionary game theory have been successfully employed to study multi-agent learning dynamics formally in strategic interactions. This article surveys the dynamical models that have been derived for various multi-agent reinforcement learning algorithms, making it possible to study and compare them qualitatively. Furthermore, new learning algorithms that have been introduced using these evolutionary game theoretic tools are reviewed. The evolutionary models can be used to study complex strategic interactions. Examples of such analysis are given for the domains of automated trading in stock markets and collision avoidance in multi-robot systems. The paper provides a roadmap on the progress that has been achieved in analysing the evolutionary dynamics of multi-agent learning by highlighting the main results and accomplishments.

TIST Journal 2015 Journal Article

Metastrategies in Large-Scale Bargaining Settings

• Daniel Hennes
• Steven De Jong
• Karl Tuyls
• Ya’akov (Kobi) Gal

This article presents novel methods for representing and analyzing a special class of multiagent bargaining settings that feature multiple players, large action spaces, and a relationship among players’ goals, tasks, and resources. We show how to reduce these interactions to a set of bilateral normal-form games in which the strategy space is significantly smaller than the original settings while still preserving much of their structural relationship. The method is demonstrated using the Colored Trails (CT) framework, which encompasses a broad family of games and has been used in many past studies. We define a set of heuristics (metastrategies) in multiplayer CT games that make varying assumptions about players’ strategies, such as boundedly rational play and social preferences. We show how these CT settings can be decomposed into canonical bilateral games such as the Prisoners’ Dilemma, Stag Hunt, and Ultimatum games in a way that significantly facilitates their analysis. We demonstrate the feasibility of this approach in separate CT settings involving one-shot and repeated bargaining scenarios, which are subsequently analyzed using evolutionary game-theoretic techniques. We provide a set of necessary conditions for CT games for allowing this decomposition. Our results have significance for multiagent systems researchers in mapping large multiplayer CT task settings to smaller, well-known bilateral normal-form games while preserving some of the structure of the original setting.

ECAI Conference 2014 Conference Paper

Influencing Social Networks: An Optimal Control Study

• Daan Bloembergen
• Bijan Ranjbar Sahraei
• Haitham Bou-Ammar
• Karl Tuyls
• Gerhard Weiß 0001

We study the evolution of cooperation in social networks, aiming in particular at ways of influencing the behavior in such networks using methods and techniques from optimal control theory. This is of importance to many scenarios where politicians or policy makers strive to push consensus on some topic that may seem suboptimal from individuals' perspectives. To this end, we employ the Continuous Action Iterated Prisoner's Dilemma (CAIPD) as model for the interactions in a social network. This model describes how neighboring nodes influence each other, and in effect determines how different strategies may spread through the network. We extend this model, incorporating a mechanism for external influence on the behavior of individual nodes. Next we prove reachability of an arbitrary network-wide agreement using the Lyapunov's Direct Method. Based on the theory of Linear-Quadratic Trackers we propose a step-wise iterative control algorithm, and show the effectiveness of the proposed controller in various Small World and Scale Free social networks.

ECAI Conference 2014 Conference Paper

Spatial evolutionary game-theoretic perspective on agent-based complex negotiations

• Siqi Chen 0001
• Jianye Hao
• Gerhard Weiß 0001
• Karl Tuyls
• Ho-fung Leung

The complexity of automated negotiation in a multi-issue, incomplete-information and continuous-time environment poses severe challenges, and in recent years many strategies have been proposed in response to this challenge. For the traditional evolution, strategies are studied in games assuming that "globally" negotiates with all other participates. This evaluation, however, is not suited for negotiation settings that are primarily characterized by "local" interactions among the participating agents, that is, settings in which each of possibly many participating agents negotiates only with its local neighbors rather than all other agents. A new class of negotiation games is therefore introduced that take negotiation locality (hence spatial information about the agents) into consideration. It is shown how spatial evolutionary game theory can be used to interpret bilateral negotiation results among state-of-the-art strategies.

AAAI Conference 2014 Conference Paper

Theory of Cooperation in Complex Social Networks

• Bijan Ranjbar-Sahraei
• Haitham Bou Ammar
• Daan Bloembergen
• Karl Tuyls
• Gerhard Weiss

This paper presents a theoretical as well as empirical study on the evolution of cooperation on complex social networks, following the continuous action iterated prisoner’s dilemma (CAIPD) model. In particular, convergence to network-wide agreement is proven for both evolutionary networks with fixed interaction dynamics, as well as for coevolutionary networks where these dynamics change over time. Moreover, an extension to the CAIPD model is proposed that allows to model influence on the evolution of cooperation in social networks. As such, this work contributes to a better understanding of behavioral change on social networks, and provides a first step towards their active control.

JAAMAS Journal 2013 Journal Article

A decentralized approach for convention emergence in multi-agent systems

• Mihail Mihaylov
• Karl Tuyls
• Ann Nowé

Abstract The field of convention emergence studies how agents involved in repeated coordination games can reach consensus through only local interactions. The literature on this topic is vast and is motivated by human societies, mainly addressing coordination problems between human agents, such as who gets to redial after a dropped telephone call. In contrast, real-world engineering problems, such as coordination in wireless sensor networks, involve agents with limited resources and knowledge and thus pose certain restrictions on the complexity of the coordination mechanisms. Due to these restrictions, strategies proposed for human coordination may not be suitable for engineering applications and need to be further explored in the context of real-world application domains. In this article we take the role of designers of large decentralized multi-agent systems. We investigate the factors that speed up the convergence process of agents arranged in different static and dynamic topologies and under different interaction models, typical for engineering applications. We also study coordination problems both under partial observability and in the presence of faults (or noise). The main contributions of this article are that we propose an approach for emergent coordination, motivated by highly constrained devices, such as wireless nodes and swarm bots, in the absence of a central entity and perform extensive theoretical and empirical studies. Our approach is called Win-Stay Lose-probabilistic-Shift, generalizing two well-known strategies in game theory that have been applied in other domains. We demonstrate that our approach performs well in different settings under limited information and imposes minimal system requirements, due to its simplicity. Moreover, our technique outperforms state-of-the-art coordination mechanisms, guarantees full convergence in any topology and has the property that all convention states are absorbing.

AAMAS Conference 2013 Conference Paper

A Macroscopic Model for Multi-Robot Stigmergic Coverage

• Bijan Ranjbar-Sahraei
• Gerhard Weiss
• Karl Tuyls

This paper explores a multi-robot coverage approach called StiCo (for“Stigmergic Coverage”) by deriving a probabilistic macroscopic model. The proposed model makes it possible to quickly and efficiently study the swarm-type behavior of StiCo, and also allows for making predictions about its long term behavior. The model is validated in a twofold way: through computer simulations, and with real robots.

IJCAI Conference 2013 Conference Paper

Conditional Restricted Boltzmann Machines for Negotiations in Highly Competitive and Complex Domains

• Siqi Chen
• Haitham Bou Ammar
• Karl Tuyls
• Gerhard Weiss

Learning in automated negotiations, while useful, is hard because of the indirect way the target function can be observed and the limited amount of experience available to learn from. This paper proposes two novel opponent modeling techniques based on deep learning methods. Moreover, to improve the learning efficacy of negotiating agents, the second approach is also capable of transferring knowledge efficiently between negotiation tasks. Transfer is conducted by automatically mapping the source knowledge to the target in a rich feature space. Experiments show that using these techniques the proposed strategies outperform existing state-of-the-art agents in highly competitive and complex negotiation domains. Furthermore, the empirical game theoretic analysis reveals the robustness of the proposed strategies.

AAMAS Conference 2013 Conference Paper

OctoSLAM: A 3D Mapping Approach to Situational Awareness of Unmanned Aerial Vehicles

• Joscha-David Fossel
• Daniel Hennes
• Sjriek Alers
• Daniel Claes
• Karl Tuyls

Unmanned aerial vehicles (UAVs) have recently become widely available to the research community. A common vision is that such (semi-)autonomous airborne agents can be beneficial in numerous scenarios, e. g. urban search and rescue. However, when deploying computationally restricted UAVs in these real life scenarios, various challenges from multiple research domains arise. These include situational awareness, controlling, planning, and learning. The focus of this demonstration is on situational awareness of agents capable of 6D motion, in particular UAVs. We propose the integration of 2D laser range finder, altitude, and attitude sensor data to compose 3D maps of the environment. Experiments show significant improvement in the localization and representation accuracy over current 2D map methods.

AAMAS Conference 2013 Conference Paper

StiCo in Action

• Bijan Ranjbar-Sahraei
• Sjriek Alers
• Karl Tuyls
• G erhard Weiss

StiCo is a Stigmergic Coverage approach, which is previously designed for dispersion of robots in a communicationlimited environment. In contrast to the existing coverage approaches, StiCo does not rely on direct communication between robots, and does not require any data storage or computational power for the robots. The main building block of StiCo is using environmental markers for transferring information between robots. Therefore, in this paper the practical requirements for implementation of StiCo in a real world experiment with a swarm of e-pucks are described and the coverage behavior of StiCo is validated by various experiments.

AAMAS Conference 2012 Conference Paper

A Common Gradient in Multi-agent Reinforcement Learning

• Michael Kaisers
• Daan Bloembergen
• Karl Tuyls

AAMAS Conference 2012 Conference Paper

CALU: Collision Avoidance with Localization Uncertainty

• Daniel Claes
• Daniel Hennes
• Karl Tuyls
• Wim Meeussen

CALU is a multi-robot collision avoidance system based on the velocity obstacle paradigm. In contrast to previous approaches, we alleviate the strong requirement for perfect sensing (i. e. global positioning) using Adaptive Monte-Carlo Localization on a per-agent level.

IROS Conference 2012 Conference Paper

Collision avoidance under bounded localization uncertainty

• Daniel Claes
• Daniel Hennes
• Karl Tuyls
• Wim Meeussen

We present a multi-mobile robot collision avoidance system based on the velocity obstacle paradigm. Current positions and velocities of surrounding robots are translated to an efficient geometric representation to determine safe motions. Each robot uses on-board localization and local communication to build the velocity obstacle representation of its surroundings. Our close and error-bounded convex approximation of the localization density distribution results in collision-free paths under uncertainty. While in many algorithms the robots are approximated by circumscribed radii, we use the convex hull to minimize the overestimation in the footprint. Results show that our approach allows for safe navigation even in densely packed environments.

AAMAS Conference 2012 Conference Paper

MITRO: an augmented mobile telepresence robot with assisted control

• Sjriek Alers
• Daan Bloembergen
• Max B
• uuml; gler
• Daniel Hennes
• Karl Tuyls

We present MITRO: Maastricht Intelligent Telepresence RObot, a custom-built robot system specifically designed for augmented telepresence with assisted control. Telepresence robots can be deployed in a wide range of application domains, and augmented presence with assisted control can greatly improve the experience for the user.

AAMAS Conference 2012 Conference Paper

Multi-robot collision avoidance with localization uncertainty

• Daniel Hennes
• Daniel Claes
• Wim Meeussen
• Karl Tuyls

This paper describes a multi-robot collision avoidance system based on the velocity obstacle paradigm. In contrast to previous approaches, we alleviate the strong requirement for perfect sensing (i. e. global positioning) using Adaptive Monte-Carlo Localization on a per-agent level. While such methods as Optimal Reciprocal Collision Avoidance guarantee local collision-free motion for a large number of robots, given perfect knowledge of positions and speeds, a realistic implementation requires further extensions to deal with inaccurate localization and message passing delays. The presented algorithm bounds the error introduced by localization and combines the computation for collision-free motion with localization uncertainty. We provide an open source implementation using the Robot Operating System (ROS). The system is tested and evaluated with up to eight robots in simulation and on four differential drive robots in a real-world situation.

AAMAS Conference 2012 Conference Paper

Reinforcement Learning Transfer via Sparse Coding

• Haitham Bou Ammar
• Karl Tuyls
• Matthew Taylor
• Kurt Driessen
• Gerhard Weiss

Although Reinforcement Learning (RL) has been successfully deployed in a variety of tasks, learning speed remains a fundamental problem for applying RL in complex environments. Transfer learning aims to ameliorate this shortcoming by speeding up learning through the adaptation of previously learned behaviors in similar tasks. Transfer techniques often use an inter-task mapping, which determines how a pair of tasks are related. Instead of relying on a hand-coded inter-task mapping, this paper proposes a novel transfer learning method capable of autonomously creating an inter-task mapping by using a novel combination of sparse coding, sparse projection learning and sparse Gaussian processes. We also propose two new transfer algorithms (\emph{TrLSPI} and \emph{TrFQI}) based on least squares policy iteration and fitted-Q-iteration. Experiments not only show successful transfer of information between similar tasks, inverted pendulum to cart pole, but also between two very different domains: mountain car to cart pole. This paper empirically shows that the learned inter-task mapping can be successfully used to (1) improve the performance of a learned policy on a fixed number of samples, (2) reduce the learning times needed by the algorithms to converge to a policy on a fixed number of samples, and (3) converge faster to a near-optimal policy given a large number of samples.

AAMAS Conference 2011 Conference Paper

Bee-Inspired Foraging In An Embodied Swarm

• Sjriek Alers
• Daan Bloembergen
• Daniel Hennes
• Steven De Jong
• Michael Kaisers
• Nyree Lemmens
• Karl Tuyls
• Gerhard Weiss

We show the emergence of Swarm Intelligence in physical robots. We transfer an optimization algorithm which is based on beeforaging behavior to a robotic swarm. In simulation this algorithm has already been shown to be more effective, scalable and adaptive than algorithms inspired by ant foraging. In addition to this advantage, bee-inspired foraging does not require (de-)centralized simulation of environmental parameters (e. g. pheromones).

AAMAS Conference 2011 Conference Paper

Distributed Cooperation in Wireless Sensor Networks

• Mihail Mihaylov
• Yann-A
• euml; l Le Borgne
• Karl Tuyls
• Ann Now
• eacute;

We present a game-theoretic self-organizing approach for scheduling the radio activity of wireless sensor nodes. Our approach makes each node play a win-stay lose-shift (WSLS) strategy to choose when to schedule radio transmission, reception and sleeping periods. The proposed strategy relies only on local interactions with neighboring nodes, and is thus fully decentralized. This behavior results in shorter communication schedules, allowing to not only reduce energy consumption by reducing the wake-up cycles of sensor nodes, but also to decrease the data retrieval latency. We implement this WSLS approach in the OMNeT++ sensor network simulator where nodes are organized in three topologies -line, grid and random. We compare the performance of our approach to two state-of-the-art scheduling protocols, namely S-MAC and D-MAC, and show that the WSLS strategy brings significant gains in terms of energy savings, while at the same time reduces communication delays. In addition, we show that our approach performs particularly well in large, random topologies.

AAMAS Conference 2011 Conference Paper

Empirical and Theoretical Support for Lenient Learning

• Daan Bloembergen
• Michael Kaisers
• Karl Tuyls

Recently, an evolutionary model of Lenient Q-learning (LQ) has been proposed, providing theoretical guarantees of convergence to the global optimum in cooperative multi-agent learning. However, experiments reveal discrepancies between the predicted dynamics of the evolutionary model and the actual learning behavior of the Lenient Q-learning algorithm, which undermines its theoretical foundation. Moreover it turns out that the predicted behavior of the model is more desirable than the observed behavior of the algorithm. We propose the variant Lenient Frequency Adjusted Q-learning (LFAQ) which inherits the theoretical guarantees and resolves this issue. The advantages of LFAQ are demonstrated by comparing the evolutionary dynamics of lenient vs non-lenient Frequency Adjusted Q-learning. In addition, we analyze the behavior, convergence properties and performance of these two learning algorithms empirically in the Battle of the Sexes (BoS) and the Stag Hunt (SH). Significant deviations arise from the introduction of leniency, leading to profound performance gains in coordination games against both lenient and non-lenient learners.

AAMAS Conference 2011 Conference Paper

Metastrategies in the Colored Trails Game

• Steven De Jong
• Daniel Hennes
• Karl Tuyls
• Ya'akov (Kobi) Gal

This paper presents a novel method to describe and analyze strategic interactions in settings that include multiple actors, many possible actions and relationships among goals, tasks and resources. It shows how to reduce these large interactions to a set of bilateral normal-form games in which the strategy space is significantly smaller than the original setting, while still preserving many of its strategic characteristics. We demonstrate this technique on the Colored Trails (CT) framework, which encompasses a broad family of games defining multi-agent interactions and has been used in many past studies. We define a set of representative heuristics in a three-player CT setting. Choosing players' strategies from this set, the original CT setting is analytically decomposed into canonical bilateral social dilemmas, i. e. , Prisoners' Dilemma, Stag Hunt and Ultimatum games. We present a set of criteria for generating strategically interesting CT games and empirically show that they indeed decompose into bilateral social dilemmas if players play according to the heuristics. Our results have significance for multi-agent systems researchers in mapping large multi-player task settings to well-known bilateral normal-form games in a way that facilitates the analysis of the original setting.

EUMAS Conference 2011 Conference Paper

Multi-agent Learning and the Reinforcement Gradient

• Michael Kaisers
• Daan Bloembergen
• Karl Tuyls

Abstract This article shows that seemingly diverse implementations of multi-agent reinforcement learning share the same basic building block in their learning dynamics: a mathematical term that is closely related to the gradient of the expected reward. Gradient Ascent on the expected reward has been used to derive strong convergence results in two-player two-action games, at the expense of strong assumptions such as full information on the game that is being played. Variations of Gradient Ascent, such as Infinitesimal Gradient Ascent (IGA), Win-or-Learn-Fast IGA, and Weighted Policy Learning (WPL), assume a known value function for which the reinforcement gradient can be computed directly. In contrast, independent multi-agent reinforcement learning algorithms that assume less information on the game being played such as Cross learning, variations of Q-learning and Regret minimization base their learning on feedback from discrete interactions with the environment, requiring neither an explicit representation of the value function nor its gradient. Despite this much stricter limitation on information available to these algorithms, they yield dynamics which are very similar to Gradient Ascent and exhibit equivalent convergence behavior. In addition to the formal derivation, directional field plots of the learning dynamics in representative classes of two-player two-action games illustrate the similarities and strengthen the theoretical findings.

EUMAS Conference 2011 Conference Paper

Reinforcement Learning Transfer Using a Sparse Coded Inter-task Mapping

• Haitham Bou-Ammar
• Matthew E. Taylor
• Karl Tuyls
• Gerhard Weiß 0001

Abstract Reinforcement learning agents can successfully learn in a variety of difficult tasks. A fundamental problem is that they may learn slowly in complex environments, inspiring the development of speedup methods such as transfer learning. Transfer improves learning by reusing learned behaviors in similar tasks, usually via an inter-task mapping, which defines how a pair of tasks are related. This paper proposes a novel transfer learning technique to autonomously construct an inter-task mapping by using a novel combinations of sparse coding, sparse projection learning, and sparse pseudo-input gaussian processes. Experiments show successful transfer of information between two very different domains: the mountain car and the pole swing-up task. This paper empirically shows that the learned inter-task mapping can be used to successfully (1) improve the performance of a learned policy on a fixed number of samples, (2) reduce the learning times needed by the algorithms to converge to a policy on a fixed number of samples, and (3) converge faster to a near-optimal policy given a large amount of samples.

AAMAS Conference 2010 Conference Paper

Frequency Adjusted Multi-agent Q-learning

• Michael Kaisers
• Karl Tuyls

Multi-agent learning is a crucial method to control or find solutions for systems, in which more than one entity is adaptive. In today's interconnected world, such systems are ubiquitous in many domains, including auctions in economics, swarm robotics in computer science, and politics in social sciences. Multi-agent learning is inherently more complex than single-agent learning and has a relatively thin theoretical framework supporting it. Recently, multi-agent learning dynamics have been linked to evolutionary game theory, allowing the interpretation of learning as an evolution of competing policies in the mind of the learning agents. The dynamical system from evolutionary game theory that has been linked to Q-learning predicts the expected behavior of the learning agents. Closer analysis however allows for two interesting observations: the predicted behavior is not always the same as the actual behavior, and in case of deviation, the predicted behavior is more desirable. This discrepancy is elucidated in this article, and based on the new insights Frequency Adjusted Q- (FAQ-) learning is proposed. This variation of Q-learning perfectly adheres to the predictions of the evolutionary model for an arbitrarily large part of the policy space. In addition to the theoretical discussion, experiments in the three classes of two-agent two-action games illustrate the superiority of FAQ-learning.

JAAMAS Journal 2010 Journal Article

Human-inspired computational fairness

• Steven De Jong
• Karl Tuyls

Abstract In many common tasks for multi-agent systems, assuming individually rational agents leads to inferior solutions. Numerous researchers found that fairness needs to be considered in addition to individual reward, and proposed valuable computational models of fairness. In this paper, we argue that there are two opportunities for improvement. First, existing models are not specifically tailored to addressing a class of tasks named social dilemmas, even though such tasks are quite common in the context of multi-agent systems. Second, the models generally rely on the assumption that all agents will and can adhere to these models, which is not always the case. We therefore present a novel computational model, i. e. , human-inspired computational fairness. Upon being confronted with social dilemmas, humans may apply a number of fully decentralized sanctioning mechanisms to ensure that optimal, fair solutions emerge, even though some participants may be deciding purely on the basis of individual reward. In this paper, we show how these human mechanisms may be computationally modelled, such that fair and optimal solutions emerge from agents being confronted with social dilemmas.

AAMAS Conference 2009 Conference Paper

State-Coupled Replicator Dynamics

• Daniel Hennes
• Karl Tuyls
• Matthias Rauterberg

This paper introduces a new model, i. e. state-coupled replicator dynamics, expanding the link between evolutionary game theory and multiagent reinforcement learning to multistate games. More precisely, it extends and improves previous work on piecewise replicator dynamics, a combination of replicators and piecewise models. The contributions of the paper are twofold. One, we identify and explain the major shortcomings of piecewise replicators, i. e. discontinuities and occurrences of qualitative anomalies. Two, this analysis leads to the proposal of the new model for learning dynamics in stochastic games, named state-coupled replicator dynamics. The preceding formalization of piecewise replicators general in the number of agents and states - is factored into the new approach. Finally, we deliver a comparative study of finite action-set learning automata to piecewise and state-coupled replicator dynamics. Results show that statecoupled replicators model learning dynamics in stochastic games more accurately than their predecessor, the piecewise approach.

AAMAS Conference 2009 Conference Paper

Stigmergic Landmark Foraging

• Nyree Lemmens
• Karl Tuyls

In this paper, we describe a nature-inspired optimization algorithm based on bee foraging behavior. This algorithm combines the high performance of bee path-integration navigation with ant-like stigmergic behavior in the form of landmarks. More precisely, each individual landmark can be created at any walkable state in the environment and contains a collection of direction markers with which visiting agents can find their way in an unknown environment. A landmark can either be represented by an agent or any other information distributing object (e. g. , a RFID). Essentially, we implement ant recruitment behavior based on pheromone. However, instead of using attracting or repelling pheromone in every state of the environment, we only update directional information at key locations in the environment. The resulting algorithm, which we call Stigmergic Landmark Foraging (SLF), proves to be very efficient in terms of building and adapting solutions.

AAMAS Conference 2008 Conference Paper

Artificial agents learning human fairness

• Steven De Jong
• Karl Tuyls
• Katja Verbeeck

Recent advances in technology allow multi-agent systems to be deployed in cooperation with or as a service for humans. Typically, those systems are designed assuming individually rational agents, according to the principles of classical game theory. However, research in the field of behavioral economics has shown that humans are not purely self-interested: they strongly care about fairness. Therefore, multi-agent systems that fail to take fairness into account, may not be sufficiently aligned with human expectations and may not reach intended goals. In this paper, we present a computational model for achieving fairness in adaptive multi-agent systems. The model uses a combination of Continuous Action Learning Automata and the Homo Egualis utility function. The novel contribution of our work is that this function is used in an explicit, computational manner. We show that results obtained by agents using this model are compatible with experimental and analytical results on human fairness, obtained in the field of behavioral economics.

KER Journal 2008 Journal Article

Fairness in multi-agent systems

• Steven De Jong
• Karl Tuyls
• Katja Verbeeck

Abstract Multi-agent systems are complex systems in which multiple autonomous entities, called agents, cooperate in order to achieve a common or personal goal. These entities may be computer software, robots, and also humans. In fact, many multi-agent systems are intended to operate in cooperation with or as a service for humans. Typically, multi-agent systems are designed assuming perfectly rational, self-interested agents, according to the principles of classical game theory. Recently, such strong assumptions have been relaxed in various ways. One such way is explicitly including principles derived from human behavior. For instance, research in the field of behavioral economics shows that humans are not purely self-interested. In addition, they strongly care about fairness. Therefore, multi-agent systems that fail to take fairness into account, may not be sufficiently aligned with human expectations and may not reach intended goals. In this paper, we present an overview of work in the area of fairness in multi-agent systems. More precisely, we first look at the classical agent model, that is, rational decision making. We then provide an outline of descriptive models of fairness, that is, models that explain how and why humans reach fair decisions. Then, we look at prescriptive, computational models for achieving fairness in adaptive multi-agent systems. We show that results obtained by these models are compatible with experimental and analytical results obtained in the field of behavioral economics.

AAMAS Conference 2008 Conference Paper

Switching Dynamics of Multi-Agent Learning

• Peter Vrancx
• Karl Tuyls
• Ronald Westra
• Ann Now
• eacute;

This paper presents the dynamics of multi-agent reinforcement learning in multiple state problems. We extend previous work that formally modelled the relation between reinforcement learning agents and replicator dynamics in stateless multi-agent games. More precisely, in this work we use a combination of replicator dynamics and switching dynamics to model multi-agent learning automata in multi-state games. This is the first time that the dynamics of problems with more than one state is considered with replicator equations. Previously, it was unclear how the replicator dynamics of stateless games had to be extended to account for multiple states. We use our model to visualize the basin of attraction of the learning agents and the boundaries of switching dynamics at which an agent possibly arrives in a new dynamical system. Our model allows to analyze and predict the behavior of the different learning agents in a wide variety of multi-state problems. In our experiments we illustrate this powerful method in two games with two agents and two states.

JMLR Journal 2008 Journal Article

Theoretical Advantages of Lenient Learners: An Evolutionary Game Theoretic Perspective

• Liviu Panait
• Karl Tuyls
• Sean Luke

This paper presents the dynamics of multiple learning agents from an evolutionary game theoretic perspective. We provide replicator dynamics models for cooperative coevolutionary algorithms and for traditional multiagent Q-learning, and we extend these differential equations to account for lenient learners: agents that forgive possible mismatched teammate actions that resulted in low rewards. We use these extended formal models to study the convergence guarantees for these algorithms, and also to visualize the basins of attraction to optimal and suboptimal solutions in two benchmark coordination problems. The paper demonstrates that lenience provides learners with more accurate information about the benefits of performing their actions, resulting in higher likelihood of convergence to the globally optimal solution. In addition, the analysis indicates that the choice of learning algorithm has an insignificant impact on the overall performance of multiagent learning algorithms; rather, the performance of these algorithms depends primarily on the level of lenience that the agents exhibit to one another. Finally, the research herein supports the strength and generality of evolutionary game theory as a backbone for multiagent learning. [abs] [ pdf ][ bib ] &copy JMLR 2008. ( edit, beta )

AAMAS Conference 2007 Conference Paper

Theoretical Advantages of Lenient Qlearners: An Evolutionary Game Theoretic Perspective

• Liviu Panait
• Karl Tuyls

This paper presents the dynamics of multiple reinforcement learning agents from an Evolutionary Game Theoretic (EGT) perspective. We provide a Replicator Dynamics model for traditional multiagent Q-learning, and we extend these differential equations to account for lenient learners: agents that forgive possible mistakes of their teammates that resulted in lower rewards. We use this extended formal model to visualize the basins of attraction of both traditional and lenient multiagent Q-learners in two benchmark coordination problems. The results indicate that lenience provides learners with more accurate estimates for the utility of their actions, resulting in higher likelihood of convergence to the globally optimal solution. In addition, our research supports the strength of EGT as a backbone for multiagent reinforcement learning.

AIJ Journal 2007 Journal Article

What evolutionary game theory tells us about multiagent learning

• Karl Tuyls
• Simon Parsons

This paper discusses If multi-agent learning is the answer, what is the question? [Y. Shoham, R. Powers, T. Grenager, If multi-agent learning is the answer, what is the question? Artificial Intelligence 171 (7) (2007) 365–377, this issue] from the perspective of evolutionary game theory. We briefly discuss the concepts of evolutionary game theory, and examine the main conclusions from [Y. Shoham, R. Powers, T. Grenager, If multi-agent learning is the answer, what is the question? Artificial Intelligence 171 (7) (2007) 365–377, this issue] with respect to some of our previous work. Overall we find much to agree with, concluding, however, that the central concerns of multiagent learning are rather narrow compared with the broad variety of work identified in [Y. Shoham, R. Powers, T. Grenager, If multi-agent learning is the answer, what is the question? Artificial Inteligence 171 (7) (2007) 365–377, this issue].

JAAMAS Journal 2006 Journal Article

Exploring selfish reinforcement learning in repeated games with stochastic rewards

• Katja Verbeeck
• Ann Nowé
• Karl Tuyls

Abstract In this paper we introduce a new multi-agent reinforcement learning algorithm, called exploring selfish reinforcement learning (ESRL). ESRL allows agents to reach optimal solutions in repeated non-zero sum games with stochastic rewards, by using coordinated exploration. First, two ESRL algorithms for respectively common interest and conflicting interest games are presented. Both ESRL algorithms are based on the same idea, i. e. an agent explores by temporarily excluding some of the local actions from its private action space, to give the team of agents the opportunity to look for better solutions in a reduced joint action space. In a latter stage these two algorithms are transformed into one generic algorithm which does not assume that the type of the game is known in advance. ESRL is able to find the Pareto optimal solution in common interest games without communication. In conflicting interest games ESRL only needs limited communication to learn a fair periodical policy, resulting in a good overall policy. Important to know is that ESRL agents are independent in the sense that they only use their own action choices and rewards to base their decisions on, that ESRL agents are flexible in learning different solution concepts and they can handle both stochastic, possible delayed rewards and asynchronous action selection. A real-life experiment, i. e. adaptive load-balancing of parallel applications is added.

JAAMAS Journal 2005 Journal Article

An Evolutionary Dynamical Analysis of Multi-Agent Learning in Iterated Games

• Karl Tuyls
• Pieter Jan ’T Hoen
• Bram Vanschoenwinkel

Abstract In this paper, we investigate Reinforcement learning (RL) in multi-agent systems (MAS) from an evolutionary dynamical perspective. Typical for a MAS is that the environment is not stationary and the Markov property is not valid. This requires agents to be adaptive. RL is a natural approach to model the learning of individual agents. These Learning algorithms are however known to be sensitive to the correct choice of parameter settings for single agent systems. This issue is more prevalent in the MAS case due to the changing interactions amongst the agents. It is largely an open question for a developer of MAS of how to design the individual agents such that, through learning, the agents as a collective arrive at good solutions. We will show that modeling RL in MAS, by taking an evolutionary game theoretic point of view, is a new and potentially successful way to guide learning agents to the most suitable solution for their task at hand. We show how evolutionary dynamics (ED) from Evolutionary Game Theory can help the developer of a MAS in good choices of parameter settings of the used RL algorithms. The ED essentially predict the equilibriums outcomes of the MAS where the agents use individual RL algorithms. More specifically, we show how the ED predict the learning trajectories of Q-Learners for iterated games. Moreover, we apply our results to (an extension of) the COllective INtelligence framework (COIN). COIN is a proved engineering approach for learning of cooperative tasks in MASs. The utilities of the agents are re-engineered to contribute to the global utility. We show how the improved results for MAS RL in COIN, and a developed extension, are predicted by the ED.

KER Journal 2005 Journal Article

Evolutionary game theory and multi-agent reinforcement learning

• Karl Tuyls
• Ann Nowé

In this paper we survey the basics of reinforcement learning and (evolutionary) game theory, applied to the field of multi-agent systems. This paper contains three parts. We start with an overview on the fundamentals of reinforcement learning. Next we summarize the most important aspects of evolutionary game theory. Finally, we discuss the state-of-the-art of multi-agent reinforcement learning and the mathematical connection with evolutionary game theory.

EUMAS Conference 2005 Conference Paper

Privacy in Multi-Agent Learning: Securely Inducing a Multi-Agent Decision Tree

• Karl Tuyls
• Bart Kuijpers

AAMAS Conference 2003 Conference Paper

A Selection-Mutation model for Q-learning in Multi-Agent Systems

• Karl Tuyls
• Katja Verbeeck
• Tom Lenaerts