Asymptotic Extinction in Large Coordination Games
Desmond Chan, Bart de Keijzer, Tobias Galla, Stefanos Leonardos, Carmine Ventre · 2024
Read Asymptotic Extinction in Large Coordination Games by Desmond Chan, Bart de Keijzer, Tobias Galla, Stefanos Leonardos, Carmine Ventre (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15461.txt.
Introduction
Desmond Chan and co-authors present a game theory paper, published in 2024, on how learning agents settle, or fail to settle, in large coordination games. Players in such games gain by matching each other's choices, and many learn through Q-learning, which updates the value of actions from past rewards. That method can fail to converge or pick a poor balance point when several exist.
The authors find the critical rate of exploration that forces convergence to a single fixed point. That rate grows with the number of players and with how closely their payoffs align. In very large games the balance point drifts to the edge of the action space, leaving a fixed share of actions almost never played.
Catalog record
| CREATOR | Desmond Chan, Bart de Keijzer, Tobias Galla, Stefanos Leonardos, Carmine Ventre |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-15461
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Asymptotic Extinction in Large Coordination Games Desmond Chan, Bart de Keijzer, Tobias Galla, Stefanos Leonardos, Carmine Ventre Abstract We study the exploration-exploitation trade-off for large multiplayer coordination games where players strategise via Q-Learning, a common learning framework in multi-agent reinforcement learning. Q-Learning is known to have two shortcomings, namely non-convergence and potential equilibrium selection problems, when there are multiple fixed points, called Quantal Response Equilibria (QRE). Furthermore, whilst QRE have full support for finite games, it is not clear how Q-Learning behaves as the game becomes large. In this paper, we characterise the critical exploration rate that guarantees convergence to a unique fixed point, addressing the two shortcomings above. Using a generating-functional method, we show that this rate increases with the number of players and the alignment of their payoffs. For many-player coordination games with perfectly aligned payoffs, this exploration rate is roughly twice that of p p -player zero-sum games. As for large games, we provide a structural result for QRE, which suggests that as the game size increases, Q-Learning converges to a QRE near the boundary of the simplex of the action space, a phenomenon we term asymptotic extinction, where a constant fraction of the actions are played with zero probability at a rate o ( 1 / N ) o(1/N) for an N N -action game. 1 King’s College London, 2 Institute for Cross-Disciplinary Physics and Complex Systems (IFISC, CSIC-UIB) [email protected] , bart.de \_ [email protected], [email protected], [email protected] , [email protected] Introduction Multi-agent systems are an increasingly relevant area in AI research. They typically consist of learning agents trying to coordinate to reach specific outcomes, such scenarios are prevalent in fields ranging from economics ( March 1991 ) , robotics and distributed systems ( Panait and Luke 2005 ) . A key challenge in these settings is balancing exploration and exploitation in high-dimensional action spaces. Exploration is required for the discovery of optimal strategies; this can come at the expense of short-term rewards. Effectively exploring such complex spaces can be a critical point of failure, preventing convergence to “good” outcomes. In multi-agent reinforcement learning (MARL), coordination scenarios consisting of interacting agents, can be represented as games. Throughout this work, we will focus on Q-Learning, one of the most widely used methods in MARL, as it provides a framework to analyse the exploitation-exploration trade-off algorithmically. The fixed points of Q-Learning are Quantal Response Equilibria (QRE) ( Leonardos, Piliouras, and Spendlove 2021 ; Leonardos and Piliouras 2022 ) , which always assign positive probability to all actions of finite games and for low exploration rates approximate the Nash Equilibria (NE) for the underlying game. Coordination games are characterised by players’ payoffs being aligned in a manner to incentivise picking mutually beneficial actions. In such settings, agents following the Q-Learning algorithm over a fixed game can exhibit two different dynamical behaviours: (i) Convergence to a unique fixed point (at high exploration rates) – where agents reach the same, joint fixed point regardless of initial conditions; and, (ii) Convergence to multiple equilibria (at low exploration rates) – the final strategy profiles agents converge to is dependent on initial conditions. The effectiveness of Q-Learning is influenced by which of these two outcomes emerges during the learning process. This paper investigates the dynamical behaviour of Q-Learning over large, multi-player coordination games where the payoff matrices are randomly drawn from multivariate Gaussians. In each game, the payoffs matrices are randomly-generated and held fixed. Players are assigned random initial strategies and we study the emerging dynamics. Related Work and Our Contribution. The study of random competitive games was considered in ( Galla and Farmer 2013 ) , which was inspired by replicator models in the context of biological evolution ( Opper and Diederich 1992 ; Galla 2006 ) . Following this line of work, we characterise, through the use of random games, the typical behaviour in complex, coordination games a priori the learning process. Our work complements and extends the results in ( Sanders, Farmer, and Galla 2018 ) to coordination games. Our theoretical analysis suggest in coordination games with large action sets of size N , a constant, non-zero proportion of actions are played with a frequency of o(1/N) . We call this effect asymptotic extinction . This extinction rate is asymptotic and varies with the model parameters. While simulations cannot fully quantitatively confirm this effect, simulation results are broadly consistent with our theoretical analysis. Taking this effect into account, a minimum exploration rate T_{\text{crit}} , which guarantees convergence to a unique fixed point can be found over games with varying number of players and degree of payoff correlation. Preliminaries Multiplayer normal form games. A p player, N action normal form game, \mathcal{G} , is defined by a tuple, \mathcal{G}=(\mathcal{P},\mathcal{A},\Pi) , where \mathcal{P}:=\{1,2,\dots,p\} is the set of players , and \mathcal{A}:=\{1,\ldots,N\} is a set of actions. Each player in \mathcal{G} chooses an action, resulting in an action profile , i.e., an element \mathbf{a}\in\mathcal{A}^{p} . Thus, for an action profile \mathbf{a} , we write a_{i} to refer to Player i ’s chosen action in \mathbf{a} . Furthermore, we use \mathbf{a}_{-i} to refer to vector obtained from \mathbf{a} by removing the i th coordinate. The notation (b,\mathbf{a}_{-i}) then refers to the vector obtained from \mathbf{a} by replacing the value at coordinate i with b (so that \mathbf{a}=(a_{i},\mathbf{a}_{-i}) . For each action profile, every player experiences a certain payoff which players want to maximise. Payoffs are specified by the payoff function \Pi:\mathcal{A}^{p}\rightarrow\mathbb{R}^{p} , where for i\in\mathcal{P} and \mathbf{a}\in\mathcal{A}^{p} , the payoff for Player i on action profile \mathbf{a} is given by \Pi(\mathbf{a})_{i} . Players can choose their actions probabilistically. This gives rise to the notion of a strategy \mathbf{x} , which is a probability distribution over \mathcal{A} . Thus, \mathbf{x} is a point on the (N-1) -simplex \Delta_{N}=\{\mathbf{x}\in\mathbb{R}^{n}_{\geq 0}\ :\ x_{1}+\cdots+x_{N}=1\} . Interior points of the simplex correspond to strategies where all actions are played with positive probability (x_{i}>0,\forall i) . Points not in the interior are known as boundary points . Similar to the notion of an action profile, a strategy profile is a choice of strategy by each of the players, and is hence given by an element \mathbf{x}=(\mathbf{x}^{1},\ldots,\mathbf{x}^{p})\in\Delta_{N}^{p} . A strategy profile \mathbf{x} , induces a probability distribution over action profiles, and we define the payoff R(\mathbf{x})^{i} of Player i for \mathbf{x} from \Pi , as the expected value of the payoff of the random action profile: R(\mathbf{x})^{i}=\sum_{\mathbf{a}\in\mathcal{A}^{p}}\Pi(\mathbf{a})_{i}\prod_{i\in\mathcal{P}}x^{i}_{a_{i}}. (1) Similar to our notation for action profiles, for a strategy profile \mathbf{x} we use \mathbf{x}^{-i} to refer to the vector obtained from \mathbf{x} by removing the strategy of Player i from it. The notation (y,\mathbf{x}^{-i}) then refers to the vector obtained from \mathbf{x} by replacing \mathbf{x}^{i} with y\in\Delta_{N} . Furthermore, we sometimes abuse notation and write (a,\mathbf{x}^{-i}) , for an action a\in\mathcal{A} , to denote (\mathbf{e}_{a},\mathbf{x}^{-i}) , where \mathbf{e}_{a} denotes the vector with a 1 at coordinate a and 0 s at all other coordinates. Constructing payoff matrices. To generate a game, we draw the payoff matrix, \Pi , from a multivariate Gaussian with mean 0 which treats all players symmetrically 1 1 1 The choice of Gaussian distribution can be motivated by a maximum entropy and universality argument ( Tao and Vu 2011 ) See