Multi-agent cooperation through learning-aware policy gradients
Authors: Alexander Meulemans
Seijin Kobayashi
Johannes von Oswald
Nino Scherrer
Eric Elmoznino
Blake Aaron Richards
Guillaume Lajoie
Blaise Aguera y Arcas
Joao Sacramento
Venue: ICLR 2025 Poster (2025)
Keywords: multi-agent learning
reinforcement learning
decentralized training
social dilemmas
cooperation
iterated prisoner's dilemma
melting pot
Primary area: reinforcement learning

Abstract: Self-interested individuals often fail to cooperate, posing a fundamental challenge for multi-agent learning. How can we achieve cooperation among self-interested, independent learning agents? Promising recent work has shown that in certain tasks cooperation can be established between ``learning-aware" agents who model the learning dynamics of each other. Here, we present the first unbiased, higher-derivative-free policy gradient algorithm for learning-aware reinforcement learning, which takes into account that other agents are themselves learning through trial and error based on multiple noisy trials. We then leverage efficient sequence models to condition behavior on long observation histories that contain traces of the learning dynamics of other agents. Training long-context policies with our algorithm leads to cooperative behavior and high returns on standard social dilemmas, including a challenging environment where temporally-extended action coordination is required. Finally, we derive from the iterated prisoner's dilemma a novel explanation for how and when cooperation arises among self-interested learning-aware agents.

Published as a conference paper at ICLR 2025
MULTI-AGENT COOPERATION THROUGH LEARNING- AWARE POLICY GRADIENTS
Alexander Meulemans Seijin Kobayashi" Johaaaan von Oswald Nino Scherrer Eric Elmoznino Blake A. 1.shards11223.1... Guillaume Lajoie! 1233,115 Blaise Agüera y Arcas', .Jāo Sacramento'
Google, Paradigms of Intelligence Team, Mila Quebec Al Institute, Université de Montréal,
"MeGill University, CCIARR, "Equal contribution
ameulemans @ google.com seijink @ google.com
ABSTRACT
Self-interested individuals often fail to cooperate, posing fundamental challenge for multi-agent learning. How can we achieve cooperation among self-interested, independent learning agents? Promising recent work has shown that in certain tasks cooperation can be established between learning-aware agents who model the learning dynamics of each other. Here, present the first unbiased, higher- derivative-free policy gradient algorithm for learning-aware reinforcement learn- ing, which takes into account that other agents are themselves learning through trial and error based on multiple noisy trials. We then leverage efficient sequence models condition behavior long observation histories that contain traces of the learning dynamics of other agents. Training long-context policies with our al- gorithm leads to cooperative behavior and high returns on standard social dilem- mas, including a challenging environment where semporally-extnnde action co- ordination required. Finally, we derive from the iterated prisoner's dilemma novel explanation for how and when cooperation arises among self-interested learning-awarr agents.
INTRODUCTION
From self-driving autonomous vehicles to personalized assistants, there is a rising interest in devel- oping agents that can learn to interact with humans (Collins et al., 2024; Gweon al., 2023), and with each other (Park et al., 2023; Vezhnevets et al., 2023). However, multi-agent learning comes with significant challenges that are not present in more conventional single-agent paradigms. This is perhaps best seen through the study of "social dilemmas", general-sum games which model the ten- sion between cooperation and competition in abstract form (von Neumann & Morgenstern, 1947). Without further assumptions, letting agents independently optimize their individual objectives on such games results in poor outcomes and a lack of cooperation (Tan, 1993; Claus & Boutilier, 1998).
First, for general-sum games, reaching equilibrium point does necessarily imply appropriate behavior because there can be many sub-optimal equilibria (Fudenberg & Levine, 1998; Shoham & Leyton-Brown, 2008). Second, the control problem an agent faces is non-stationary from its own viewpoint, because other agents themselves simultancously learn and adapt (Hernandez-Leal et al., 2017). Centralized training algorithms sidestep non- stationarity issues by sharing agent information (Sunehag et al., 2017), but this transformation into a global learning problem is usually prohibitively costly, and impossible to implement when agents must developed separately (Zhang et al., 2021).
The above two fundamental issues have hindered progress in multi-agent reinforcement learning, and have limited our understanding of how self-interested agents may reach high returns when faced with social dilemmas. In this paper, join promising line of work "learning awareness" that has been shown to improve cooperation (Foerster et al., 2018a). The key idea behind such approaches is to take into account the learning dynamics of other agents explicitly, rendering it into a meta-learning problem (Schmidhuber, 1987; Bengio et al., 1990; Hochreiter et al., 2001).
The present paper contains two main novel results on learning awareness in general-sum games. First, we introduce a new learning- aware reinforcement learning rule derived as a policy gradient estimator. Unlike existing methods (Foerster et al., 201 8a;b; Xie et al., 2021; Balaguer al., 2022;

---

Published as a conference paper at ICLR 2025
Lu et al., 2022: Willi et al., 2022; Cooijmans et al., 2023; Khan et al., 2024; Aghajohari et al., 2024), it has a number of desirable properties: (i) it does not require computing higher-order derivatives, (ii) it is provably unbiased, (iii) it can model minibatched learning algorithms, (iv) it is applicable to scalable architectures based on recurrent sequence policy models, and (v) it does not assume access to privileged information, such as the opponents' policies or learning rules. Our policy gradient rule significantly outperforms previous model-free methods in the general-sum game setting. In particular, we show that efficient learning-aware learning suffices to reach cooperation in a challenging sequential social dilemma involving temporally extended actions (Leibo et al., 2017) that we adapt from the Melting Pot suite (Agapiou al., 2023). Second, we analyze the iterated prisoner's 's dilemma (IPD), canonical model for studying cooperation among self-interested agents (Rapoport, 1974; Axelrod & Hamilton, 1981). Our analysis uncovers a novel mechanism for the emergence of cooperation through learning awareness, and explains why the seminal learning with opponent-learning awareness algorithm due to Foerster et al. (2018a) led to cooperation in the IPD.
2 BACKGROUND AND PROBLEM SETUP
We consider partially observable stochastic games (POSGs; Kuhn, 1953) consisting of a tuple AA, Pr. P., O Po. 7, T) with I {l....,m} a finite set of n agents, S the state space, A= X, the joint action space, Pr(Se+1 St, At) the state transition distribution, (So) the initial state distribution, P. = PE S, A) the joint factorized reward distribution with R {R' kee and bounded rewards R², O x XzezO' the joint observation space, Po St. Ac-1) the observation distribution, y the discount factor, the time step, and T the horizon. We superseript i to indicate agent-specific actions, observations and rewards, -i to indicate all agent indices except and we omit the superscript for joint actions, observations and rewards. As agents only receive partial state information, they benefit from conditioning their policies T'' (a) 2 Φ*) on the obser- vation history x = {ož V (Aström, 1965; Kaelbling et al., 1998), with øf the policy parameters. Note that the observations can contain the agent's actions on previous timesteps.
2.1 GENERAL-SUM GAMES AND THEIR CHALLENGES
We focus on general-sum games, where each agent has their own reward function, possibly different from those of other agents. Specifically, consider ther zero-sum nor fully cooperatie... Analyzing and solving such general-sum games while letting every agent individually and independently maximize their rewards (a setting often referred to as "fully-decentralizedd reinforcement learning"; Albrecht et al., 2024) is a longstanding problem in the fields of machine learning and game theory for two primary reasons, described below.
general-sum games that nei-
Non-stationarity of the environment. In a general-sum game, each agent aims to maximize its expected return -)) = E pe E
2 Ri] with po'. the distribution over environ- ment trajectories zт induced by the environment dynamics, the policy a'aa") | x"; of agent i, and the policies - of all other agents. Importantly, the expected return J'( , o d- does not only depend on the agent's own policy, but also on the current policies of the other agents. As other agents updating their policies through learning, the environment which includes the other agents is effectively non-stationary from a single agent's perspective. Furthermore, the actions of an agent can influence this non-stationarity by changing the observation histories of other agents, on which they base their learning updates.
Equilibrium selection. It is not clear how identify appropriate policies for general-sum game. To see this, let us first briefly revisit the concept of a Nash equilibrium (Nash Jr., 1950). For a fixed set of co-player policies Φ-,, one can compute best response, which for agent is given by 6+* = arg max.: J'(Ø", @ "²)). When all current policies & are best response against each other. we have reached a Nash anymore, Vi, Ø' (Ø',, o oh S J )) Various "folk theorems" show that for most POSGs of decent complexity, there exist infinitely many Nash equilibria (Fudenberg & Levine, 1998; Shoham & Leyton-Brown, 2008). This lies at the origin of the equilibrium selection problem in multi- agent reinforcement learning: it is not only important to let multi-agent system converge to Nash equilibrium, but also to target a good equilibrium, as Nash equilibria can be arbitrarily bad. Famously, unconditional mutual defection in the infinitely iterated prisoner's dilemma is a Nash equilibrium. with strictly lower expected returns for all agents compared to the mutual tit-for-tat Nash equilibrium (Axelrod & Hamilton, 1981).
eauilibriuuu equilibrium, where no agent is incentivized to change its policy
2

---

Published as a conference paper at ICLR 2025
2.2 CO-PLAYER LEARNING AWARENESS
We aim to address the above two major challenges of multi-agent learning in this paper. Our work builds upon recent efforts that are based on adding a meta level to the multi-agent POSG, where the higher-order variable represents the learning algorithm used by each agent (Lu et al., 2022: Balaguer et al., 2022; Khan et al., 2024). In this meta-problem, the environment includes the learning dynamics of other agents. At the meta-level, one episode now extends across multiple episodes of actual game play, allowing the "ego agent", i, to observe how its co-players, -i, learn, see Fig. 1. The goal of this meta-agent may be intuitively understood as that of shaping co-player learning to its own advantage.
Provided that co-player learning algorithms remain constant, the above reformulation yields single- agent problem that amenable to standard reinforcement learning techniques. This setup is funda- mentally asymmetric: while the meta agent (ego agent) is endowed with co-player learning aware- ness (i.c., observing multiple episodes of game play), the remaining agents remain oblivious to the fact that the environment is non-stationary. We thus refer to them here as naive agents (see Fig. IB). Despite this asymmetry, prior work has observed that introducing a learning-awe aware agent in a group of naive learners often leads to better learning outcomes for all agents involved, avoiding mutual defection equilibria (Lu et al., 2022: Balaguer et al., 2022; Khan et al., 2024). Moreover, Foer- ster et al. (2018a) has shown that certain forms of learning awareness can lead to the emergence of cooperation even in symmetric cases, a surprising finding that is not yet well understood.
These observations motivate our study, leading us to derive novel efficient learning- awwre reinforce- ment learning algorithms, and to investigate their efficacy in driving a group of agents (possibly composed of both meta and naive agents) towards more beneficial equilibria. Below, we proceed by first formalizing asymmetric co-player shaping problems, which we solve with novel policy gra- dient algorithm (Section 3). In Section 4, we then return to the question of why and when co-player learning awareness can result in cooperation in multi-agent systems with equally capable agents.
A
B
T steps per inner-episode
Naive agent: Takes only intra-episode context into account
B paralle trajectories
Meta agent: Takes intra- and inter-episode context into account
M iinee--epssoees per meta-trajectory
Figure 1: A. Experience data terminology. Inner-episodes comprise T steps of (inner) game play, played between agents B times in parallel, forming a batch of inner-episodes. A given sequence of M inner-episodes forms a meta-trajectory, thus comprising MT steps inner game play. The collection of B meta-trajectorris forms a meta meta-episode. B. During game play, a naive agent takes only the current episode context into account for decision making. In contrast, a meta agent takes the full long context into account. Seeing multiple episodes of game play endows meta agent with learning awareness.
Co-player shaping. Following Lu et al. (2022), we first introduce a meta-game with a single meta-agent whose goal is shape the learning of naive co-players to its advantage. This meta- game is defined formally as a single-agent partially observable Markov decision process (POMDP) ($, Á, Pt, P., P., Ö, 5, M). The meta-state consists of the policy parameters o- of all co-players together with the agent's own parameters d'. The meta-environment dynamics represent the fixed learning rules of the co-players, and the meta-reward distribution represents the expected return J' ') collected by agent during an inner episode, with "inner" referring to the actual game being played. The initialization distribution P. reflects the policy initializations of all players. Fi- nally, we introduce meta-policy u(#"++1 & pm 0) parameterized by 0, that decides the update to the parameter df (the meta-action) to shape the co-player learning towards highly rewarding regions for agent over a horizon of M meta steps. This leads to the co-player shaping problem
M
max E (o
Epn
Σ Jo )m!))
(1)
1
with Pe the distribution over parameter trajectories induced by the meta-dynamics and meta-policy.
3

---

Published as a conference paper at ICLR 2025
2.3 SINGLE-LEVEL CO-PLAYER SHAPING BY LEVERAGING SEQUENCE MODELS
In this paper, we combine both inner- and meta-policies in a single long-context policy, conditioning actions on long observation histories spanning multiple inner game episodes (see Fig. 1B). Instead of hand-designing the co-player learning algorithms, we instead let meta-learning discover the algo- rithms used by other agents. This way, we leverage the in-context learning and inference capabilities of modern neural sequence models (Brown et al., 2020; Rabinowitz, 2019; Akyürek et al., 2023; von Oswald et al., 2023; Li et al., 2023) to both simulate in-context an inner policy, as well as strategi- cally update it based on current estimates of co- co-player policies. This philosophy has been adopted in Khan et al. (2024), in which a flat policy is optimized using an evolutionary algorithm. We compare to this method in Section 3.1, after we derive our meta reinforcement learning algorithm.
To proceed with this approach, we must first reformulate the meta-game. particular, we must deal with difficulty that is not present in single-agent meta reinforcement learning (e.g.. Wang ct al., 2016; Duan et al., 2017), which stems from the fact that co-players generally update their own policies based on multiple inner episodes ("minibatches"), without which reinforcement learning cannot practically make progress. Here, we solve this by defining the environment dynamics over B parallel trajectories, with B the size of the minibatch of inner episode histories that co- co-players use to update their policies at each inner episode boundary (see Fig. IA).
Batched co-player shaping POMDP. We define the batched co-player shaping POMDP (S, A, Pt, Pr, Pi, 0, 5, M, B), with hidden states consisting of the hidden environment states of the B ongoing inner episodes, combined with the current parameters pm of all co-players; environment dynamics P. simulating B environments in parallel, combined with updating the co-player's 's policy parameters o²,, and resetting the environments at each inner episode boundary; initial state distri- bution P: that initializes the co-player policies and initializes the environments for the first inner episode batch; and finally, an ego-agent policy # s(a | hf: parameterized by d', which deter- mines distribution over the batched action ai = 1.b Jb=1 based on the batched long history hj = Jb=1-
(n]- We refer each element of the latter as long history h44", with long time index l run- ning across multiple episodes, from / = until = MT. It should be contrasted to the inner episode history z/. which runs from
1 to T and thus only reflects the current (inner) game history.
The POMDP introduced above suggests using sequence policy (af hi; o') that is aware of the full minibatch of long histories and which produces a joint distribution over all current actions in the minibatch. However, as we aim to use our agents not only to shape naive learners, but also to play against/with each other, we require policy that can be used both a batch setting with naive leamers, and in a annlle-traecctry setting with other learning- aware agents. Within our single-level approach, we achieve this by factorizing the batch-aware policy sF "(a, Øf: into B independent
policies with shared parameters oi, #² (ā; h/: Ø²) = = (aaa) 1.b h Φ²). Thanks to the batched POMDP, we can now pose co-player shaping as a standard (single-level, single-agent expected return maximization problem:
B MT DE
max E
pa
B
R
(2)
1=0
This formulation is the key for obtaining an efficient policy gradient co-player shaping algorithm.
CO-AGENT LEARNING- POLICY GRADIENTS
3.1 A POLICY GRADIENT FOR SHAPING NAIVE LEARNERS
We now provide a meta reinforcement learning algorithm for solving the co-player shaping problem stated in Eq. 2 efficiently. Under the POMDP introduced in the previous section, co-player shap- ing becomes a conventional expected return maximization problem. Applying the policy gradient theorem (Sutton et al., 1999) Eq. 2, we arrive at COALA-PG (co-agent learning-aware policy gradients, cff. Theorem 3.1): a -rriiyggr method compatible with shaping other reinforcement learners that base their own policy updates on minibatches of experienced trajectories.
Theorem 3.1. Take the expected shaping return J( Ep
1 B EI MT R4/0. with Po
the distribution induced by the environment dynamics Pt. initial state distribution P, and policy di.
4

---

Published as a conference paper at ICLR 2025
Naive agent: Palicy updale every inner-episade batch
COALA-PG agent: Policy update after every mela-eplsode
Figure Policy update and credit assignment naive and meta agents. For credit assignment action of naive agent (left) takes only intra-episode context into account. COALA agent (right) takes inter- episode context across the batch dimension into account. For policy updates, naive agent aggregates policy gradients over the inter-batch dimension (dashed blocks) and updates their policy between episode boundaries. In contrast, a COALA agent updates their policy at lower frequency along the meta- meta-cpisode dimension.
Then the policy gradient of this expected return is equal
BBC MT ΣΣ
mrT D
B
MT
] (3)
IO') BBpsr pa
V log T' (aj 3.b (1th))
Σ
We provide a proof Appendix D. There are three important differences between COALA- PG and naively applying policy gradient methods to individual trajectories in a batch. (i) Each gradient term for individual action ai takes into account the future inner episode returns averaged over the whole minibatch, instead of the future return along trajectory b (see Fig. 2). This allows taking into account the influence of this action on the parameter update of the naive learner, which influences all trajectories in the minibatch after that update. (ii) Instead of averaging the policy gradients for each trajectory in the batch, COALA-PG accumulates (sums) them. This is important, as otherwise the learning signal would vanish in the limit of large minibatches. Intuitively, when a naive learner single action on the naive learner's update is
uses a large minibatch for its updates, the effect small (O B )), and this must be compensated by summing all such small effects. (iii) To ensure a correct balance between the return from the current inner episode my and the return from future inner episodes, COALA-PG rescales the current episode return by B. Figure 12 in App. H shows empirically that COALA PG correctly balances the policy gradient terms arising from the current inner episode return versus the future inner episode returns, whereas M-FOS (Lu et al., 2022) and a naive policy gradient that ignores the other parallel trajectories over-emphasize the current inner episode return, causing them to loose the co-player shaping learning signals. We will later show experimentally in Section 5 that correct treatment of minibatches critically affects reinforcement learning performance.
The expectation appearing in the policy gradient expression must be estimated. To reduce gradi- ent estimation variance, we resort to standard practices, including generalized advantage estimation (Schulman et al., 2016) and sampling a meta-batch of B batched trajectories from E Ep (c.f. Ap- pendix A).
Relationship to prior shaping methods. We now contrast our policy gradient algorithm to two closely related methods, M-FOS (Lu al., 2022) and Shaper (Khan al., 2024). Like COALA-PG M-FOS is model-free meta reinforcement learning method. Unlike the approached followed here, though, it aims solve the bilevel co-player shaping problem of Eq. 1, treating meta- and inner- policy networks separately. Moreover, the M-FOS parameter update is not derived as the policy gradient on the batched co-player shaping POMDP introduced above, and current-episode returns overemphasized compared to future-episode returns (see Appendix G). This leads biased parameter update, which results learning inefficiencies. We comment on other existing bilevel shaping methods in Appendix F.
Khan et al. (2024) adopt a single-level sequence policy for their Shaper algorithm, as we do here, but then resort to black-box evolution strategies (Rechenberg & Higen, 1973) to learn the policy. Obtaining an efficient meta reinforcement learning algorithm from a POMDP applicable to such single-level policies is thus our key distinguishing contribution. The unbiased policy gradient prop- erty of our learning rule translates in practice onto learning speed and stability gains, as we will see in the experiments reported in Section 5.
5

---

Published as a conference paper at ICLR 2025
4 WHY IS LEARNING AWARENESS BENEFICIAL ON GENERAL-SUM GAMES?
We have established that co-player shaping can be cast as single-agent reward maximization prob- lem whenever there a single learning- aware player amongst group of learners that are otherwise naive. This allowed us to derive policy gradient shaping method. However, such an asymmetric setup cannot in general be taken for granted. In our experimental analyses, we therefore consider the more realistic scenario where qqually-capable learning aware agents try shape each other.
As reviewed in Section 2.2, prior work has shown that learning- awareness can result in better out- comes in general-sum games, but the origin and conditions for the occurrence of this phenomenon are not yet well understood. Here, we shed light on this question by analyzing the interactions of agents with varying degrees of learning-awareness in analytically tractable matrix game setting. This leads us to uncover a novel explanation for the emergence of cooperation in general-sum games.
4.1 THE ITERATED PRISONER'S ' DILEMMA
We focus on the infinitely iterated prisoner's ' dilemma (IPD), the quintessen- tial model for understanding the challenges of cooperation among self- interested agents (Rapoport, 1974; Axelrod & Hamilton, 1981). The game goes on for an indefinite number of rounds, where for each round of play two players (i = 1,2) meet and choose between two actions, cooperate defect, a; E d}. The rewards collected as a function of the actions of d (2,-1) (0,0)
Table 1: Single-round IPD rewards (r', r²).
(1,1)
(-1,2)
both agents are shown in Table 1. These four rewards are set so to create a social dilemma. When the agents meet only once, mutual defection is the only Nash equilibrium; self-interested agents thus end up obtaining low reward. In the infinitely iterated variant of the game, there exist Nash equilibria involving cooperative behavior, but these are notoriously hard to converge to through self-interested reward maximization.
We model each agent through a tabular policy (a | x1: that depends only on the previous action of both agents, x; [a/_]_ Their behavior is thus fully specified by five parameters, which determine the probability of cooperating in response to the four possible previous action com- binations together with the initial cooperation probability. For this game, the discounted expected return J' .d2) can be calculated analytically. We exploit this property and optimize policies by performing exact gradient ascent on the expected return (c.f. Appendix C for details).
4.2 EXPLAINING COOPERATION THROUGH LEARNING AWARENESS
Based on the experimental results reported Fig. 3, we now identify three key findings that establish how learning awareness enables cooperation to be reached in the iterated prisoner's 's dilemma:
Finding 1: Learning-aware agents extort naive learners. We first pit naive against learning- aware agents. We find that the latter develop extortion policies which force naive learners onto unfair cooperation, similar to the zero-determinant extortion strategies discovered by Press & Dyson (2012) (c.f. Appendix C.I). Even when learning-ave aware agent is initialized at pure defection, maximizing the shaping objective of Eq. 2 lets it escape mutual defection (see Fig. 3A).
Finding 2: Extortion turns into cooperation when two learning-aware players face each other. After developing extortion policies against naive learners (grey shaded area in Fig. 3B), we then let two learning-aware agents (C1 and C2 in Fig. 3B) play against each other after. We see that optimizing the co-player shaping objective turns extortion policies into cooperative policies. Intu- itively, under independent learning, an extortion policy shapes the co-player to cooperate more. We remark that the same occurs if learning aware agents play against themselves (self-play; data not shown). This analysis explains the success of the annealing procedure employed by Lu et al. (2022), according to which naive co-players transition to self-play throughout training.
Finding 3: Cooperation emerges within groups of naive and learning-aware agents. Findings 1. and 2. motivate studying learning in group containing both naive and learning-wwan agents, with every agent in the group trained against each other. This mixed group setting yields a sum of two distinct shaping objectives, which depend whether the agent being shaped is learning-aware or naive. The gradients resulting from playing against naive learners pull against mutual defection and towards extortion, while those resulting from playing against other learning-awee aware agents push away from extortion towards cooperation. Balancing these competing forces leads to robust cooperation, Fig. 3C (left). Intriguingly, mutual unconditional defection is no longer Nash equilibrium

---

Published as a conference paper at ICLR 2025
Meta Nalve
B
Two phases of training
Pool: Naive and Meta
Pool: Meta
1.0
Avg. reward
1.0
Avg. reward
Avg. reward
0.8
M1 vs M2
reward
M1 vs M2
0.6
M2 vs M1
0.4
M2 vs M1
Naive
vs M2
0.5
Naive Meta
M2 M1
0.4
0.0
M1 vs Nalve
0.2
0.0
M2 vs Naive
0.0-
0.0
1000
2000
3000
2000
4000 6000
0
2000
4000
2000
4000
Training Iteration
Training Iteration
Training Iteration
Training Iteration
Figure 3: (A) Learning-aware agents learn to extort naive learners, even when initialized with pure defection strategy. (B) An extortion policy developed against naive agents (shaded area period) turns into cooperative one when playing against another learning-aware agent (MI & M2). (C) Cooperation emerges within mixed training pools of naive and learning-ave aware agents, but not in pools of Baaming-awart agents only. The shaded regions represent the interquartile range (25th to 75th quantiles) across 32 random seeds
in this mixed group setting, and agents initialized with unconditional defection policies learn to cooperate (see Appendix C.I). By contrast, pure group of learning-awan aware agents cannot escape mutual defection, see Fig. 3C (right). This can be explained by the fact that the agents can no longer observe others learn, and must deal again with non- non- stationary problem. The resulting gradients do not therefore contain information on the effects of unconditional defection on the future strategies of co-players, or that policies the vein of tit-for-tat can shape co-players towards more cooperation.
Our analysis thus reveals a surprising path to cooperation through heterogeneity. The presence of siort-sighted agents that greedily maximize immediate rewards turns out to be essential for full cooperation to be established among far-sighted, learning-awan agents.
4.3 EXPLAINING WHEN AND HOW COOPERATION ARISES WITH THE LOLA ALGORITHM
We next analyze the seminal Learning with Opponent-Learee Awareness (LOLA; Foerster et al., 201 8a) algorithm. Briefly, LOLA assumes that co-players update their parameters with M naive gradient steps, and estimates the total gradient through a look-ahead update:
LOLA
J
M Σ
S.L. 4,0
a 00--""
8'
8'
10'0" Apo ] (4)
doi
with d the total derivative taking into account the effect of of on the parameter updates AØo
dgr and DΦ- the partial derivative. Note that Eq. 4 considers the LOLA-DICE update (Foerster et al., 2018b), an improved version of LOLA. In Appendix E, we show that Eq. 4 can be derived as a special case of COALA-PG. Note that LOLA-DICE estimates the policy gradient in Eq. 4 by explicitly backpropagating through the co-player's 's parameter update using higher-order derivatives, whereas COALA-PG leads to a novel giggher-order-deriiaaivv--reee estimator of Eq. 4 (see Appendix E).
Above, we showed that the two main ingredients for learning to cooperate under selfish objectives (i) observe that one's actions influence the future behavior of others, providing shaping gradients pulling away from defection towards extortion, and (ii), also play against other extortion agents immune being shaped on the fast timescale, providing gradients pulling away from extortion towards cooperation. We then showed that both ingredients can be combined by training agents in a heterogeneous group containing both naive and learning- aware agents.
We can explain the emergent cooperation in LOLA by observing that LOLA also combines both ingredients, albeit differently from the heterogeneous group setting. The look-ahead rule (Eq. 4) computes gradients that shape naive learners performing M naive gradient steps. Unique to LOLA however, these simulated naive learners are initialized with the parameters Φ of other LOLA agents. If the number of look-ahead steps is small, the updated naive learner parameters stay close to Φ mimicking playing against other extortion agents. This then results in emergent cooperation.
Fig. 4A confirms that LOLA-DICE with ground-truth gradients and with few look-ahead steps leads to cooperation on the iterated prisoner's 's dilemma. However, as the number of look-ahead steps increases, the naive learner starts moving too far away from its d= initialization, removing the second ingredient, thus leading to defection. In Fig. 4, we take the policy resulting from LOLA- training with many look-ahead steps, and train new randomly initialized naive learner against this

---

Published as a conference paper at ICLR 2025
A
look aheads
10 look aheads
B
look-ahesds
10 look-aheads
look-aheads
looicaheeds
LOLA 20 look aheads
leeldaheads
20 look-aheads
look aheads
random leamer
look aheads
Aug. reneerd
0.8-
Avg. roward
Aug. roward
0.5
0.6-
0.44
0.4
0.2
1000
3000
4000
10 15
1,000
2000
3000
4000
Gradient
Lool-
Gradient
Figure 4: (A) Performance of two agents trained by LOLA-DICE on the iterated prisoner's dilemma with analytical gradients for various look-ahead steps (only the performance of the first agent is shown). (B) Per- formance of a randomly initialized naive learner trained against the fixed LOLA 20 look-aheads policy taken from the end of training of (A). (C) Same setting as (A), but with the naive gradient À p J o)²) added to the LOLA-DICE update, with À a hyperparameter (c.f. Appendix C). Shaded regions indicate standard error computed over 64 seeds.
fixed LOLA policy. The results show that the LOLA policy extorts the naive learner into unfair cooperation, confirming that with many look-ahead steps, only a shaping incentive is present in the LOLA update, resulting in extortion policies. Hence, the low reward in Fig. 4A for LOLA agents with many look-ahead steps does not result from unconditional defection, but instead from both LOLA policies trying to extort the other one. Finally, we can improve the performance of LOLA with many look-ahead steps by explicitly introducing ingredient 2 by adding the partial gradient 06 J' ") to Eq. see Fig. 4C.
5 EXPERIMENTAL ANALYSIS OF POLICY GRADIENT IMPLEMENTATIONS
The results presented in the previous sections were obtained by performing gradient ascent on ama- lytical expected returns. This assumes knowledge of co-player parameters, and it only possible on restricted number of games which admit closed-form value functions. We now move to the general reinforcement learning setting, aiming at understanding (i) when meta-agents succeed in exploiting naive agents, and (īi) when cooperation is achieved among meta-agents.
5.1
AGENTS TRAINED WITH COALA-PG MASTER THE ITERATED PRISONER DILEMMA
A
Meta
Defection within meta episode training
Training pool: meta and nalve
COALA
Avg. reward
1.0-
[ 0.75
Naive vs CO
COALA.PG Nalve
Avg. roward
Batch-unaware COALA/P
COALA
0.50
Naive
0.5
Batch-unaware A-P
Naive vs N-FOS
LOLA
M:FOS
0.25
LOLA vi Naive
Meta Agent
0.0
0.00
LOLA
Only Pool
1000
2000
3000
5000
10000
15000
1000
2000
3000
Training iteration
Mcta opisode step
Training iteration
Figure 5: Agents trained by COALA-PG play iterated prisoner's dilemma. (A): When trained against naive agents only, COALA-PO-Leeeee
agents extort the latter and reach considerably higher reward than other baseline agents. The stars (*) indicate overlapping curves of the corresponding color at that point (B): When analyzing the behavior of the agents within one meta-episode, we observe COALA- FG-trained agents shaping naive co- co-players, lcading to low defection rate in the beginning, which is then exploited towards the end. M- FOS on the other hand defects from the beginning, achieving lower reward, thus failing properly optimize the shaping problem. Batch-unaware unaware COALA performs identically to M-FOS and is therefore omitted. (C): Average performance of meta agents playing against other meta agents, when training group of meta agents against a mixture of naive and other meta agents. Such agents trained with COALA- PPG cooperate when playing against each other, but fail do when trained with baseline methods. When removing naive agents from the pool, meta agents also fail to cooperate, as predicted Section 3. Shaded regions indicate standard deviation computed over 5 seeds.
We train long-context sequence policy n (aat b.b | : oi') with the COALA-PG rule to play the (finite) iterated prisoner's is dilemma, see Appendix B. We choose a Hawk recurrent neural network as the policy backbone (De et al., 2024). Hawk models achieve transformer-level performance at scale, but with time and memory costs that grow only linearly with sequence length. This allows processing efficiently the long history context b.b which contains all actions played by the agents
8

---

Published as a conference paper at ICLR 2025
across episodes. Based on the results of the preceding section, consider mixed group setting, pitting COALA-PG-traine agents against naive learners as well as other equally capable learning- aware agents. Naive learners are equipped with the same policy architecture as the agents trained by COALA PG, but their context limited the current inner game history z2.6.
In Fig. 5, we see that COALA- PG reproduces the analytical game findings reported in the previous section: leaming-aware agents cooperate with other learning-aware agents, and extort naive learners. Importantly, the identity of each agent is not revealed to learning-awan agent, which must there- fore infer in-context the strategy used by the player faces. Likewise, we find that the LOLA-DICE (Eq. 4) estimator behaves as in the analytical game. This result complements previous experiments with LOLA on tabular policies (Foerster et al., 201 2018a;b), suggesting that there broad class of efficient learning-aware reinforcement learning rules that can reach cooperation with more complex context-dependent sequence models. We note that LOLA achieves this by explicitly differentiating through co-player updates, which requires access their parameters and gives rise to higher-order derivatives. Our rule lifts these requirements, while maintaining learning efficiency.
By contrast, the whole group falls into defection when training the exact same sequence model with the M-FOS rule, which weighs disproportionately future vs. current episode returns. We note that the experiments reported by Lu et al. (2022) were performed with tabular policy and analytical inner game returns, for which cooperation could be achieved with the M-FOS rule. This shows how crucial the unbiased policy gradient property of COALA PG is for co-player shaping by meta reinforcement learning to succeed in practice. The same failure to beat defection occurs when using a naive policy gradient ablation which does take co-player batching into account. We refer to Appendix G for expressions for this baseline as well as the M-FOS rule. When training against M-FOS agents, our COALA-PO agents successfully shape M-FOS agents into cooperative behavior (c.f. Appendix H.3).
5.2
AGENTS TRAINED WITH COALA-PG COOPERATR, ON A SEQUENTIAL. SOCIAL DILEMMA
A
B
fvg. rewerd meto agents
Cleaning Disercpancy
0.35
0.20
0.06
zappeed
0.30
0.15
0.25
0.20
0.10
0.02
0.15
500
1000
1500
2000
2500
500
1000
1500
2000
2500
500
1000
1500
2000
2500
Training horation
Training Iteration
Triningg Itaration
COALA-PG
M-FOS
LOLA
Batch-unaware COALA-PG
Figure Agents trained by COALA-PG against naive agents only successfully shape them in CleanUp-lite. (A) POALLA-G-trringg agents better shape naive opponents compared to baselines, ob- taining higher return. (B and C) Analyzing behavior within a single meta-episode after training reveals that COALA outperforms baselines and shapes naive agents, (i) exhibiting lower cleaning discrepancy (absolute difference in average cleaning time between two agents), and (ii) being less often zapped. Shaded regions indicate standard deviation computed over 5 seeds.
Finally, we consider which is part of the Melting Pot suite of multi-agent environments (Agapiou et al., 2023). We briefly describe the game here, and provide additional details on Appendix B. On a high level, a two-player game that models the social dilemma known as the tragedy of the commons (Hardin, 1968). A player receives rewards by picking up apples. Apples are spontancously generated in an orchard, but the rate of generation is inversely proportional the pollution level of nearby river. Agents can spend time cleaning the river to reduce the pollution level, and thus increase the apple generation rate. and harvesting to maximize the return. In multi-player setting however, this gives room for "freerider" who never cleans and always harvests, letting the opponent clean instead. At any time point, agents can "zap" the opponent, which would result in the opponent being frozen for number of time steps, unable to harvest or clean. In contrast to matrix games, this game is a sequential social dilemma (Leibo et al., 2017), where cooperation involves orchestrating multiple actions.
DtranUp-liter a simplified two-player version of the CleanUp game,
CleanUp-lite
single-player game, an agent would balance out cleaning

---

Published as a conference paper at ICLR 2025
As in the previous section, model agent behavior through Hawk sequence policies, and compare COALA-PG to the same baseline methods as before. Naive agents here would learn too slowly initialized from scratch, and are therefore handled differently, Appendix B.2.2. In Figs. 6 and 7, we see that agents trained by COALA-PC reach significantly higher returns than previous model- free haselines, establishing mutual cooperation protocol with other learning-aware agents, while exploiting naive ones. We further describe below the qualitative behavior found in the simulations.
Exploitation of naive agents. -G-trannd agents shape the behavior of naive ones their advantage (c.f. Figure 6). Our behavioral analysis reveals two salient features. First, COALA- DOALA-PG PG successfully shapes naive opponents zap less often throughout the meta-episode. Less overall zapping means that agents can harvest more apples while the pollution level is low, thus increasing the overall reward. Second, COALA-PG successfully shapes naive co-players to clean significantly more often compared to the COALA-PG agent, resulting in lower average pollution level and higher average apple level (c.f. Figure in App. H). Interestingly, the naive learners benefit from the shaping from COALA- PG agents, reaching higher average reward compared to playing against other baselines (c.f. Figure 13).
A
B
Avg. reward mete egents
0.20
Cleaning Dicrepancyy
0.20
0.15
Nua zap rate
0.2
0.10
0.10
0.05
0.00
10000
20000
30000
10000
20000
30000
10000
20000
30000
Triining iteraiin
Training iteration
Training iter elion
COALA-G
Batch-unaware COALA-G
Meta Only Pool
Figure 7: Agents trained with COALA-PG against mixture of naive and other meta agents learn to cooperate in CleanUp-lite. (A) COALA-PG-trainge agents obtain higher average reward than bascline agents when playing against each other. and C): COALA-PG leads a more fair division cleaning efforts and lower zapping rates. Shaded regions indicate standard deviation computed over seeds.
Learning-awant agents cooperate. We similar trends when introducing other COALA-PG trained agents the game, see Fig. 7. Essentially, COALA-PG allows for higher apple production because of lower pollution, and lower zapping rate. We see that training time the zapping rate goes down, and COALA-PG agents have a fairer division of cleaning time compared to baselines. Interestingly, the zapping rates averaged over the meta-episode lower than in the pure shaping setting (i.e., with naive co-players only), indicating that learning-ave agents mutually shape each other to zap less.
CONCLUSION
We have shown that learning awareness allows reaching high returns in challenging social dilemmas, designed to make independent learning difficult. We identified key conditions for this occur. First, we found it necessary to take into account the stochastic minibatched nature the updates used by other agents. This is one distinguishing aspect of the COALA-PG learning rule proposed here, which translates into a significant performance advantage over prior methods. Second, learning- aware agents had be embedded in heterogeneous group containing non-learning-awar agents.
An important component of our result is the ability to leverage modern and scalable sequence mod- els. Modern sequence models have scaled favorably and in predictable manner, most notably in autoregressive language modeling (Kaplan et al.. 2020). and our results suggest important gains could be made applying similar approaches to multi-agent learning. Our method shares key as- pects with the current scalable machine learning approach: unbiased stochastic gradients, sequence model architectures that are amenable to gradient-based learning, and in-context learnin/iinferenc.. Moreover, focused the setting of independent agent learning, which scales well in parallel by design. We thus see as an exciting question to investigate the approach pursued here at larger scale and in wider range of environments. The resulting self-organized behavior may display unique cial properties that are absent from single-agent machine learning paradigms, and which may open new avenues towards artificial intelligence DDuéñez-Guzmár et al., 2023).
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
We would like to thank Maximilian Schlegel, Yanick Schimpf, Rif A. Saurous, Joel Leibo, Alexan- der Sasha Vezhnevets, Aaron Courville, Juan Duque, Milad Aghajohari. Razvan Ciuca, Gauthier Gidel, James Evans and the Google Paradigms of Intelligence team for feedback and enlightening discussions. GL and BR acknowledge support from the CIFAR chair program. EE acknowledges support from a Vanier scholarship from the government of Canada
REFERENCES
John Agapiou, Alexander Sasha Vezhnevets, Edgar A.
Jayd Matyas, Yiran Mao, Peter Sunehag, Raphael Köster, Udari Madhushani, Kavya Kopparapu, Ramona Comanescu, D. J. Strouse, Michael B. Johanson, Sukhdeep Singh, Julia Haas, Igor Mordatch, Dean Mobbs, and Joel Z. Leibo. Melting Pot 2.0. arXiv preprint arXiv:2211.137466 2023.
Milad Aghajohari, Juan Agustin Duque. Tim Cooijmans, and Aaron Courville. Loqa: Learning with opponent q-learning awareness. arXiv preprint arXiv:2405.01035, 2024.
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algorithm is in-context learning? Investigations with linear models. In International Conference Learning Representations, 2023.
Stefano V. Albrecht, Filippos Christianos, and Lukas Schäfer. Multi-Agent Reinforcement Learning: Foundations and Modern Approaches. MIT Press, 2024.
Robert Axelrod and William D. Hamilton. The evolution of cooperation. Science, 211 1396, March 1981.
Igor Babuschkin, Kate Baumli, Alison Bell, Surya Bhupatiraju, Jake Bruce, Peter Buchlovsky, David Budden, Trevor Cai, Aidan Clark, Ivo Danihelka, Antoine Dedieu, Claudio Fantacci, Jonathan Godwin, Chris Jones, Ross Hemsley, Tom Hennigan, Matteo Hessel, Shaobo Hou, Steven Kapturowski, Thomas Keck, Iurii Kemaev, Michael King, Markus Kunesch, Lena Martens, Hamza Merzic, Vladimir Mikulik, Tamara Norman, George Papamakarios, John Quan, Roman Ring, Francisco Ruiz, Alvaro Sanchez, Laurent Sartran, Rosalia Schneider, Eren Sezener, Stephen Spencer, Srivatsan Srinivasan, Miloš Stanojević, Wojciech Stokowiec, Luyu Wang, Guangyao Zhou, and Fabio Viola. The DeepMind JAX Ecosystem, 2020.
Jan Balaguer, Raphael Koster, Christopher Summerfield, and Andrea Tacchetti. The good shepherd: An oracle agent for mechanism design. arXiv preprint arXiv: 10135, 2022.
Yoshua Bengio, Samy Bengio, and Jocelyn Cloutier. Learning a synaptic learning rule. Techni- cal report, Université de Montréal, Département d' I'Iformatique et de Recherche opérationnelle, 1990.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman- Milne,, and Qiao Zhang. JAX: composable transformations of Python+NumPP programs, 2018
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D. Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Merbeert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu. Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. Advances in Neural Information Processing Systems, 33, 2020.
Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multia- gent systems. AAAI/IAAI, 1998(746-752):2, 1998.
Katherine M. Collins, Ili Sucholutsky, Umang Bhatt, Kartik Chandra, Lionel Wong. Mina Lee, Cedegao E. Zhang, Tan Zhi-Xuan, Mark Ho, Vikash Mansinghka, Adrian Weller, Joshua B. Tenenbaum, and Thomas L. Griffiths. Building machines that learn and think with people. arXiv preprint 4408 20v:24408.03443. 2024.
11

---

Published as a conference paper at ICLR 2025
Tim Cooijmans, Milad Aghajohari, and Aaron Courville. Meta-value learning: general framework for learning with learning awareness. arXiv preprint arXiv:2307.08863, 2023.
Soham De, Samuel L. Smith, Anushan Fernando, Aleksandar Botev, George Cristian- Al- bert Gu, Ruba Haroun, Leonard Berrada, Yutian Chen, Srivatsan Srinivasan, Guillaume Des- jardins, Arnaud Doucet, David Budden, Yee Whye Teh, Razvan Pascanu, Nando De Freitas, and Caglar Gulcehre. Griffin: mixing gated linear recurrences with local attention for efficient lan- guage models. arXiv preprint arXiv:2402.19422 2024.
Yan Duan, John Schulman, Xi Chen, Peter L. Bartlett, Ilya Sutskever, and Pieter Abbeel. RL2: Fast reinforcement learning via slow reinforcement learning. International Conference on Learning Representationss 2017.
Edgar A. Duéñezz-Gzzmán, Suzanne Sadedin, Jane X. Wang, Kevin R. McKee, and Joel Z. Leibo. A social path to human-like artificial intelligence. Nature Machine Intelligence, 5(11):1181-118) 2023.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference on Machine Learning, 2017.
Jakob Foerster, Richard Y. Chen, Maruan Al-Shedivat, Shimon Whiteson, Picter Abbeel, and Igor Mordatch. Learning with opponent-leariing awareness. In International Conference on Au- tonomous Agents and Multiagent Systems, 2018a.
Jakob Foerster, Gregory Farquhar, Maruan Al-Shedivat, Tim Rocktäschel, Eric Xing, and Shimon Whiteson. DiCE: The infinitely differentiable Monte Carlo estimator: In International Conference on Machine Learning, 2018b.
Drew Fudenberg and David K Levine. The theory of learning in games, volume 2. MIT press, 1998.
Hyowon Gweon, Judith Fan, and Been Kim. Socially intelligent machines that learn from humans and help humans learn. Philosophical Transactions of the Royal Society A: Mathematical, Physi- cal and Engineering Sciences, 381 38812238)) (2251):20220048, July 2023.
Garrett Hardin. The tragedy of the commons. Science, 162(3855):1243-12222 1968.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 585(7825):357-362, 2020.
Jonathan Heek, Anselm Levskaya, Avital Oliver, Marvin Ritter, Bertrand Rondepierre, Andreas Steiner, and Marc van Zee. Flax: A neural network library and ecosystem for JAX, 2024. URL
http:// / thub www.cooo/oooo//oooooooooooooooo. le/oogll/// e/ flax.
Pablo Hernandez-Leal, Michael Kaisers, Tim Baarslag, and Enrique Munoz De Cote. A sur- vey of learning in multiagent environments: Dealing with statiiootiii arXiv preprint arXiv:1707.09188, 2017.
Sepp Hochreiter, A. Steven Younger, and Peter R. Conwell. Learning to learn using gradient descent.
In International Conference on Artificial Neural Networks, Lecture Notes Computer Science. Springer, 2001.
J. D. Hunter. Matplotlib: A 2D graphics environment. Computing in Science & Engineering, 9(3): 90-95, 2007.
Leslie Pack Kaelbling, Michael L. Littman, and Authony R. Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1):99-134, 1998.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint 2rX.v.2001.08361, 2020.
12

---

Published as a conference paper at ICLR 2025
Akbir Khan, Timon Willi, Newton Kwan, Andrea Tacchetti, Chris Lu, Edward Grefenstette, Tim Rocktäschel, and Jakob N. Foerster. Scaling opponent shaping to high dimensional games. In International Conference Autonomous Agents and Multiagent Systems, 2024.
Dong Ki Kim, Miao Liu, Matthew Riemer, Chuangchuang Sun, Marwa Abdulhai, Golnaz Habibi, Sebastian Lopez-Cot, Gerald Tesauro, and Jonathan How. A policy gradient algorithm for learning to learn multiagent reinforcement learning. International Conference on Machine Learning. 2021.
H. W. Kuhn. Extensive games and the problem of information. Princeton University Press, 1953.
Michael Laskin, Luyu Wang, Junhyuk Oh, Emilio Parisotto, Stephen Spencer, Richie Steigerwald, D. Strouse, Steven Hansen, Angelos Filos, Ethan Brooks, Maxime Gazeau, Himanshu Sahni, Satinder Singh, and Volodymyr Mnih. In-context reinforcement learning with algorithm distilla- tion. arXiv preprint arXiv:2210. 2022.
Joel Z. Leibo, Vinicius Zambaldi, Mare Lanctot, Janusz Marecki, and Thore Graepel. Multi- agent reinforcement learning in sequential social dilemmas. In International Conference Au- tonomous Agents and Multiagent Systems, 2017.
Yingcong Li, Muhammed Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak. Transformers as algorithms: generalization and stability in in-context learning. International Conference on Muchine Learning, 2023.
Christopher Lu, Timon Willi, Christian Schroeder De Witt, and Jakob Foerster. Model-free oppo- nent shaping. In International Conference on Machine Learning, 2022.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International Conference Machine Learning, 2016.
John F. Nash Jr. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36(1):48-444 114448949111 1950.
Joon Sung Park, Joseph O'Brien, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. Generative agents: Interactive simulacra of human behavior. In Proceed- ings of the 36th Annual ACM Symposium on User Interface Software and Technology, 2023.
William H. Press and Freeman J. Dyson. Iterated Prisoner's 's Dilemma contains strategies that dom- inate any evolutionary opponent. Proceedings of the National Academy of Sciences, 109(26): 10409-10413, 2012.
Neil C. Rabinowitz. Meta-leamnrs' learning dynamics are unlike learners'. arXiv preprint 100501190. 2019.
Anatol Rapoport. Prisoner's s dilemma dillemaa-recoleectinii recollections and observations. In Game Theory as a Theory of a Conflict Resolution, pp. 17-34. Springer, 1974.
Ingo Rechenberg and M. Eigen. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzbon, Verlag, 1973.
Jürgen Schmidhuber. Evolutionary principles in self-referential learning, or on learning how to learn: the meta-meta-... hook. Diploma thesis, Institut für Informatik, Technische Universität München, 1987.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. ICLR, 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 1XXi:17077003447 2017.
Yoav Shoham and Kevin Leyton-Browd Brown. Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008
13

---

Published as a conference paper at ICLR 2025
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls, and Thore Graepel. Value- decomposition networks for cooperative multi-agent learning, arXiv preprint arXiv:1706.0522 2017.
Richard S. Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances Neural Information Processing Systems, 12, 1999.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In International Conference on Machine Learning, 1993.
Alexander Sasha Vezhnevets, John P. Agapiou, Avia Aharon, Ron Ziv, Jayd Matyas, Edgar A. Duéñez-Guzmmá, William A. Cunningham, Simon Osindero, Danny Karmon, and Joel Z. Leibo. Generative agent-based modeling with actions grounded in physical, social, or digital space using Concordia. arXiv preprint arXiv:2312.0366. 2023.
John von Neumann and Oskar Morgenstern. Theory of games and economic behavior. Princeton University Press, 1947.
Johannes Oswald, Eyvind Niklasson, Maximilian Schlegel, Seijin Kobayashi, Nicolas Zucchet, Nino Scherrer, Nolan Miller, Mark Sandler, Blaise Agüera Arcas, Max Vladymyrov, Razvan Pascanu, and João Sacramento. Uncovering mesa-optimization algorithms in Transformers. arXiv preprint ar 005888, 2023.
Jane X Wang. Zeb Kurth-Nelson, Dhruva Tirumala, Hubert Soyer, Joel Z. Leibo, Remi Munos, Charles Blundell, Dharshan Kumaran, and Matt Botvinick. Learning reinforcement learn. arXiv preprint 10Xiv:/611.000000 2016.
Timon Willi, Alistair Hp Letcher, Johannes Treutlein, and Jakob Foerster. COLA: consistent learn- ing with opponent-learinng awareness. In International Conference on Machine Learning. 2022.
Annie Xie, Dylan Losey, Ryan Tolsma, Chelsea Finn, and Dorsa Sadigh. Learning latent represen- tations influence multi-agent interaction. In Conference on Robot Learning, 2021.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pp- 321-384, 2021.
Stephen Zhao, Chris Lu, Roger B. Grosse, and Jakob Foerster. Proximal learning with opponent- learning awareness. Advances in Neural Information Processing Systems, 35, 2022.
Karl Johan Aström. Optimal control of Markov processes with incomplete state information I. Journal of Mathematical Analysis and Applications, 10:174-205, 1965.
14

---

Published as a conference paper at ICLR 2025
A A2C AND PPO IMPLEMENTATIONS OF COALA-PG
We use both Advantage Actor-Critic (A2C) (Mnih et al., 2016) and Proximal Policy Optimization (PPO) Schulman et al. (2017) for COALA policy gradient estimate. We detail here how merge these methods with our COALA-PG method.
A.1 REINFORCE ESTIMATOR
For the reader's convenience, we display the COALA policy gradient below. We remind for refer- ence, that my the inner episode index corresponding to the meta episode time step L.
]
V Vo. ((0))
18 pay
log x (aj i.b
11
Ry
k=
(5)
The batch-unaware COALA policy gradient, which we use as baseline method for shaping naive learners, is given by
B
MT V
Tmu Σ
MT Σ
V J(') = pss
log log
R
Rib
(6)
B
6=1
k=Tm, +1
Note that when we play against other meta agents instead naive learners, all parallel POMDP trajectories in the batch are independent, and hence can correctly use the batch-unaware COALA policy gradient for this setting.
Finally, the M-FOS policy gradient (c.f. Appendix G) is given by
B
NT
m
B
MT
] (7)
( = E Epp
ΣΣ
de log xt' (a (111))
D V=Ik=Tmiti
R
Lb=1
The difference between M-FOS and COALA-PG is the B scaling factor for the current inner episode return. This scaling factor is crucial for correct balance between gradient contributions arising from the current inner episode, and future inner episodes. Without this scaling factor, the contributions from future inner episodes required for learning to shape the co-players vanish for large inner batch sizes.
We can construct REINFORCE estimators by sampling directly from the above expectations. How- this leads to policy gradients with prohibitively large variance. Hence, in the following sections we will derive improved advantage estimators to reduce the variance of the policy gradient estimates.
A.2 VALUE FUNCTION ESTIMATION
One of the easiest ways to use value functions for reducing the variance in the policy gradient estimator, is to subtract a baseline from the return estimator. In the COALA-PG equation 5, the straightforward value function learn is
(
T mg
B
MT
]
v(h(2) = (-1ff))))))
Σ km
Σ
Ri.
(8)
8
Jom
Tm
As the environment is reset after each inner episode, the second term can simplified by merging expectations over the different parallel trajectories:
T mm
MP Σ
]
E Epa (11n5))
Σ
Ri.6'
B
A=Tma TmuTT
15

---

www.:e/.uuureeeisseeee Published as a conference paper at ICLR 2025
Which has additional I factor the left term compared to conventional value function that would need to be learnt when playing e.g. against another meta agent equation 6. This is undesirable for several reasons, one of which being that as B increases, the value target becomes increasingly insensitive to the inner episode return, which makes learning difficult. Another reason that the target magnitude between when playing against naive agent meta agent can significantly differ. Finally, for simplicity reasons, we want value function that we can use both when playing against naive learners, as well as other meta agents.
We can solve these issues by instead learning the value function for the batch-unaware returns, and introducing some specialized reweighing when playing against naive learners, which we will see later.
(mm
MT Σ T=
((( E Epotc1132)
Rio
(10)
As such, the same value function can be used for both when playing against naive or a meta agent. In practice, we trade off variance and bias for learning the value funetion by using TD(A) targets. Algorithm 1 shows how to compute such targets with general algorithm, which we later can also repurpose for Generalized Advantage Estimation (Schulman et al., 2016) and M- FOS value functions. For computing the TD(X) targets for learning our value functions, we use no normal i wee.ceerentteeeeeee www.ureettepssoeeFFa...... sode=Fa se and the given trajectory batch originates from playing against another meta agent.
when
Algorithm Batch Lambda Returns
Input: Tt. discount,
X, average future episodes, normalize current episode,
Output: returns
seqJen + st.shape[1]
batch_size t- rt.shape[0]
if normalize normalize.current.ppe www.rretteeepioooee... then
normalization &- batch size else
normalization + episode end & (range(seq len) mod inner episode length) == (inner episode length
1)
acc t vel: -1]
global_ace mean(vel:
for = seq_len to
if www.rraeeffuuueeeeiiisseee and episode_end[[] then acc global ace
acc + -- ttl:::tt//oommmlicoooo in/oomaalzzaiinn + discount x ((1 - A) x vel: t| x x acc)
global acc mean(r, + discount x ((1 A) x et/[,t] + global acc)) returns|: || t] <- acc
return returns
A.3 GENERALIZED ADVANTAGE ESTIMATION
We now how the above value estimation can be used to update the policy following COALA-PG Ultimately we want an unbiased estimate of the advantage function, as this allows the usage of algorithms like PPO A2C.
The advantage of state h and action of
3.b against naive agent is
16

---

Published as a conference paper at ICLR 2025
MT
, 2.8 =E =B (-18) h ja;" "a;")
1
R
b
(11)
B
B
b
Kim
Tmp+1
T'm
B
MT
(-11
(-1ng-9)
R
Ri. k
(12)
B
B
V
Km TonkkTTT
Tmyl1
We can reformulate the expression using V as follows:
Tmm 1
B
MT
A(h ( =B pai (-19
B
R
B
Σ
R
(13)
k=l
#=1
T=mm++
1 ( B
por (-16f%))
por
V(hTmat bz
(14)
A simple advantage estimator would be the Monte-Carlo estimate of the above. However, we can trade-off variance with bias by using the Generalized Advantage Estimator (Schulman al., 2016). Using similar logic as for the equation above, we can compute the COALA version of the GAE by reusing the bat catch
algorithm (c.f. Algorithm follows:
Instead of the rewards of the trajectory, we provide the TD errors re + +V++11 V. as input for r t.
We provide 7 input for dis
We provide 1.0 as input for A
We put average.future..pssoo. and normal both on True.
For computing the GAE for the batch-unaware COALA-PG baseline, follow the same approach except putting average future epi sodes and normal i ze current ep sode both on False se. For computing the GAE for the M-FOS baseline (c.f. G), follow the same approach except putting average..utuur..pp.oooo on True and www.aaaic...uuuree...ppooooo on False.
A.4 A2C AND PPO IMPLEMENTATIONS
We can now use the above advantage estimates directly into A2C and PPO implementations. Below, we list few tweaks of classical reinforcement learning tricks that we used in our implementation.
Advantage normalization: as is common with PPO implementations, we investigate the use of advantage normalization. Given a batched trajectory of advantage estimation over which the policy should be updated, the trick consists centering the advantage estimates over the batched trajectory. Empirically, naive and meta learners, it was beneficial to apply the centering separately for the 2 types of meta-trajectorres (playing against naive learners playing against other meta agents).
found out that when playing against a mixture of
Reward rescaling: as another way to prevent issues stemming from large value target, we investigate simply rescaling the reward of an environment when appropriate. Effectively, the reward is rescaled for the value and policy gradient computation, but all metrics are reported by reverting the scaling, i.e. reported in the original reward scale.
17

---

Published as a conference paper at ICLR 2025
B EXPERIMENTAL DETAILS
B.I ENVIRONMENTS
B.1.1 ITERATED PRISONER'S DILEMMA (IPD)
We model the IPD environment as follows:
State: The environment has 5 states, that label by so, (c, d), (d, (d. d).
Action: Each agent has 2 possible actions: cooperate (c) and defect (d).
Dynamics: Based on the action taken by each agent in the previous time step, the state of the environment is set to the states (41, 02) where d1, 42 are respectively the previous action of the first and second player the environment. The assignment of who is first and second is made arbitrarily and fixed.
Initial state: The initial state is always set to Su-
Observation: The agents observe directly the state, modulo a permutation of the tuple to ensure a symmetry of observation. The 5 possible observations are then encoded as one-hot encoding.
At every timestep, each agents receive a reward following the reward matrix in Table
Reward:
B.1.2 CLEANUP-LITE
CleanUp lite is simplified two-player version of the CleanUp game, which is part of the Melting Pot suite of multi-agent environments (Agapiou et al., 2023). It is modelled as follows:
river, and the left one orchard. Cells in the river column be occupied by dirt. Cells in the orchard column can occupied by an apple. The world state also contains the position of each agent, and their respective zapped state
State: The world a 2D grid size 54. The right column
There exists actions: {move right, move left, move up, moved down, zap, do nothing].
Action:
Dynamics: the environment evolves at every timestep in the following order:
1. When there at least one cell in the river column that is not occupied by dirt, new patch of dirt is spawned with probability Ppollution 0.35, and placed randomly on one of the free cells in the river column.
2. When there is at least one cell in the orchard column that is not occupied by dirt, new apple is spawned with probability Papple
min(1, P/Pncho/)) where Pitreshold 3 and P the total number of dirt cells in the environment. The spawned apple placed randomly on one of the free cells in the orchard column.
When an agent that not zapped visits a cell with an apple, it harvests the apple and gets a reward of 1. The apple is replaced by an empty cell
4. When agent that is not zapped visits cell with dirt patch, it cleans the dirt patch and replaces it by an empty cell.
Finally, an agent zapping has a Pzop = 0.9 probability of successfully zapping the co-player, if the co-player is maximally 2 cells away from the agent. If the zapping is successful, the opponent is frozen for tzmp timesteps, during which it is frozen and cannot be further zapped.
6. Agents can move around with the {move right, move left, move up. moved down) actions.
Initial state: Agents are randomly placed on the grid, unzapped, there are no apples at initialization and 3 dirt patches randomly placed in the river column.
Observation: the observation contains full information about the environment. Each agent sees the position of each agent encoded flattened one-hot grid indicating the position in the grid, the full grid as a flattened grid with one-hot objects (apple, dirt, empty), and the state of all agents (zapped non-zapped). The observation is symmetric.
18

---

Published as a conference paper at ICLR 2025
Reward: An agent that picks up apple receives reward of Tapple in that timestep.
B.2
TRAINING DETAILS
Here, describe the procedure that in our experiments to train meta agents in an arbitrary mixture of naive and other meta agents (who themselves are learning). A single parameter, Praive indicating the probability of encountering a naive agent, controls the heterogeneity of the pool that a meta agents trains against. If Phaive 1, the meta agents are trained only against naive opponents, and thus the training corresponds to a pure shaping setting. If Paaive 0, meta agents are only trained against other meta agents.
Given a set of meta agent parameters {ø:}, and a set of naive agent parameters (vi), training iteration updates each parameters as follows.
B.2.1
META AGENTS
The meta-agent parameters are updated simultaneously. For each parameter oi, the following update applied:
First, meta batch of opponents is sampled. Each opponent is bierarchically sampled by first determining whether it is naive opponent (with probability Puiive), and then sampling uniformly from { or { accordingly. The sampling done with replacement, and disallowing sampling of oneself.
2. For each opponent, generate a batch of B trajectories of length TM, where M is the num- ber of inner episode, and T the episode length the environment. Crucially, after every T steps, the environment terminates and is reset, and, if the opponent is naive, the previous batch of length T trajectories used to update its parameter following a RL update rule of choice.
3. For each collected batched trajectories, the policy gradient of the meta agent parameter is computed following the COALA-PG update rule (or other baselines, c.f. G) if the opponent is naive, and the standard policy gradient otherwise otherwise (i.e. the batch and meta hatch dimensions are flattened). Crucially, the done signals from the inner episodes are ignored. The gradient is then averaged, and the parameter updated.
B.2.2 NAIVE AGENT
The naive agent parameters used to initialize the naive opponents when training the meta agents, but the resulting trained parameters are discarded. The initialization may or may not be nonetheless updated during training. In more challenging environment however, training from scratch until good performance is achieved in a single meta trajectory may require prohibitively many inner episodes. To avoid this, in some of experiments, each training iteration, set each {1b)) to be equal to one of the {. This ensures that naive agents are initialized as an already capable agent, and possible due to our choice of common architecture between naive and meta agents (c.f. below). In that case, we say that the naive agents are dynamic. Otherwise, naive agent is always initailized at one of a predefined static set of parameters.
B.3 ARCHITECTURE
We choose a Hawk recurrent neural network as the policy and value function backbone (De al., 2024), for all methods, both for meta and naive agents. First, linear layer projects the observation into an embedding space of dimension 32. Then, a single residual Hawk recurrent neural network with LRU width 32, MLP expanded width 32 and 2 heads follows. Finally, RMS normalization layer is applied, after which linear readouts, one for the value estimate, and the other for the policy logits, are applied.
All meta agent and naive agent parameters are initialized following the standard initialization scheme of Hawk. The last readout layers are however initialized to 0.
19

---

Published as a conference paper at ICLR 2025
Table 2: Hyperparameter fixed for the IPD experiments
IPD Hyperparameter
Pure Shaping
Mixed Pool
training.iteration
3000
3000
meta batch size
128
128
batch size (B)
16
16
num_inner.episode (M)
20
20
imer.episode.length (T)
10
10
p-naive
1.
0.75
population.size (meta)
4
population.size (naive)
10
10
dynamic naive agents
False
False
B.4 HYPERPARAMETERS FOR EACH EXPERIMENT
In all experiments, we first fix the environment hyperparameters. order to find the suitable hy- perparameter for each methods, hyperparameters, and select the best hyperparameters over after averaging over seeds. The final performance and metrics are then computed using fresh seeds.
perform for each of them sweep over reinforcement learning
In all our experiments, naive agents update their parameters using the Advantage Actor Critic (A2C) algorithm, without value bootstrapping the batch of length T trajectories. The hyperparameter for all experiments, can be found on Table 8.
We perform 2 experiments in the IPD environment, the pure Shaping experiment with Pnuive to investigate the shaping capabilities of meta agents, and (ii) the mixed pool setting with Paaive 0.75, to investigate the collaboration capabilities of meta agents. For both experimental setting, we show the environment hyperparameters Table 2. All meta agents are trained by PPO and Adam optimizer. For each method, we sweep hyperparameters over range specified in Table 3. Table 4 shows the resulting hyperparameters for all methods.
IPD, Figure 5
Table 3: The range of values swept over for hyperparameter search for each method for the IPD enviromment
RL Hyperparameter
Range
wowanttaes.normal/. limaaiioiinon
Falsse, Truc}
value_discomd (Y)
(0.999, 1.0}
gae lambla (Agae)
(0.98, 1.0] {0.003, 0.001,0.0003
learning.rate
Cleanup, Figure Likewise, have the pure shaping (Figure and mixed pool (Figure 7) ex- periment in the Cleanup-lite environment. For both experimental setting, we show the environment hyperparameters in Table All meta agents are trained by PPO and Adam optimizer for the pure shaping setting, while using A2C and SGD for the mixed pool setting. For each method, we sweep hyperparameters over range specified in Table Table shows the resulting hyperparameters for PPO for all methods.
20

---

Published as a conference paper at ICLR 2025
Table 4: Hyperparameters used for the IPD Shaping and Mixed Pool experiments. Despite the search, the hyperparameter chosen for each method were identical
RL Hyperparameter
Pure Shaping
Mixed Pool
algorithm
PPO
PPO
ppo.nminibat.ches
2
2
ppo_nepochs
4
spo.clippinggeepsiloo
0.2
0.2
value.coefficient
0.5
0.5
clip-value
True
True
entropy reg
0
advantage normal ization
False
False
reward_rescaling
0.05
0.05
1
Ata
1
Agae
1
optimized
ADAM
ADAM
adam adameepsilon
0.00001
0.00001
learning rate
0.0003
0.0003
max.grad_nerm
Table 5: Cleanup hyperparameters
Hyperparameter fixed for the Cleanup experiments
Pure Shaping
Mixed Pool
training.iteration
3000
30000
meta.batch.size
512
512
batch-size (B)
32
64
num inner episode (M)
100
inner sode length (T)
64
64
p.naive
1.
0.75
population.size (meta)
1
population.size (naive)
10
dynamic.naive.agents
False
True
Table 6: The range values swept over hyperparameter search each method Cleanup environ-
ment
RL Hyperparameter
Pure Shaping
Mixed Pool
advantages normal zaation
False, Truc}
False, True}
val vaalue discount (y)
(0.999, 1.0)
[1.0]
learning.rate
{0.003, 0.001, 0.0003]
00.03, 0.5, 1.0,
optimizer
[ADAM]
SSGD)
21

---

Published as a conference paper at ICLR 2025
Table 7: Hyperparameters used for the Cleanup Shaping and Cleanup Pool experiments.
RL Hyperparameter
Cleanup Shaping
Cleanup Pool
Coala
Batch Unaware
M-FOS LOLA
Coala
Batch Unaware
M-FOS
LOLA
algorithm
PPO
PPO
PPO
A2C
A2C
A2C
ppo aminibatcies
2
2
epo_nepachs
ppoJol iguepst
0.2
0.2
0.2
value.costficiee
0.5
clip value
True
True
True
True
True
True
True
entropy_regee
D
0 Trie
advantage.norma saat on
True
True
True
Trme
Trm
True
True
Au
reward_reacalling
0.1
0.1
0.1
0.1
0.1
Agan
optimizer
ADAM
ADAM
ADAM
SGD
SGD
SGD
SGD
SGD
adan_opsilon
0.00001
0.00001 0.001
0.00001
lea-ning_rate
0.001
0.003
0.1
0.1
0.03
0.03
0.03
max.grad.norm
1
1
Table 8: Naive agent hyperparameters used across different settings
RL Hyperparameter
IPD Shaping
IPD Mixed
Cleanup Shaping
Cleanup Mixed
algorithm
A2C
A2C
A2C
A2C
advantaages.normalllaaaii
Truc
True
True
True
reward.rescaling
0.05
0.05
0.1
0.1
(x)
0.99
0.99
0.99
1
td.lambda (Aaa)
1.0
1.0
1.0
1.0
gae_lambda (Aras)
1.0
1.0
1.0
1.0
value.coefficiien
0.5
0.5
0.5
0.5
entropy.reg
0.0
0.0
0.0
0.0
optimizer
ADAM
ADAM
ADAM
SGD
adam.cpsilon
0.00001
0.00001
0.00001
learning.rate rate
0.005
0.005
0.005
max.grad.norm
1.0
1.0
1.0
1.0
22

---

Published as a conference paper at ICLR 2025
C THE ANALYTICAL ITERATED PRISONER'S DILEMMA
For the experiments in Section 4 and 4.3, we analytically compute the discounted expected return of an infinitely iterated prisoner's dilemma, and its parameter gradients. Automatic differentiation al- lows us then to explicitly backpropagate through the learning trajectory of naive learners, to compute the ground-truth meta update. In the following, we provide details on this approach.
For both the naive learners and learning-aware meta agents, we consider tabular policies @ taaking into account the previous action of both agents:
[ 0 02 Ozg Til
with a ( the probability of cooperating in the initial state (with sigmoid σ), and the next pa- rameters the logits of cooperating in states CC, CD, DC and DD respectively (CD indicates that first agent cooperated, and the second agent defected). As we use a tabular policy for the meta agents, they cannot accurately infer the opponent's 's parameters from context, but its policy gradient updates of still inform it regarding the learning behavior of naive learners. Hence the meta agent can learn to shape naive learners while using a tabular policy, for example through zero-determinant extortion strategies (Press & Dyson, 2012). Using both policies, we can construct a Markov matrix providing the transition probabilities of one state to the next, ignoring the initial state.
=
(o(oha) @ (of.a) o
(1 a(tia) @ -(
with @ the element-wist product. Given the payoft vectors p² (1,1, and 1, and initial state distribution 80 = [or (o
o (+ we can write the expected discounted return of agent as
8
J' = -
Σ
En' MM'
(15)
This discounted infinite matrix sum is a Neumann series of the inverse - -M)- with the identity matrix. This gives us:
- 7
(16)
Both M and Sy depend on the agent's s policies, and we can compute the analytical gradients using automatic differentiation (we use JAX).
We model naive learners o² as taking gradient steps on J with learning rate naaive. The co-player shaping objective for meta agent i is now
J(
M
AAO
θ s.t. A,0 + = naaive o0 ' 0 00
Apo
(17)
When a learning- aware meta agent faces naive learner, we compute the shaping gradient by ex- plicitly backpropagating through J(Ø)), using automatic differentiation. When a learning-aware meta agent faces another meta agent, we compute the policy gradient as the partial gradient on J' o ()) as with tabular policies, the meta agents deploy the same policy in each inner episode, and hence averaging over inner episodes is equivalent to playing single episode of meta vs meta. For training the meta agents, we use a convex mixture of the gradients against naive learners and gradients against the other meta agent, with mixing factor Pnaive. For the gradients against naive learners, we use batch of randomly initialized naive learners of size me abatabth ch. We use the adamw optimizer from the Optax library to train the meta agents, with default hyperparameters and learning rate V/meta-
For the LOLA experiments of Section 4.3, compute the ground-truth LOLA-DICE updates equation 4 by initializing a naive learner with the opponent's parameters, simulate M naive up- dates (look-aheads) following partial derivatives of J', and backpropagating through the final re- turn J (0', 0 Σ A,o-)) including backpropagating through the learning trajectory. For Fig. 4, we train two separate LOLA agents against each other and report the training curves of the first agent (the training curves of the second agent similar, data not shown). Using self-play
23

---

Published as a conference paper at ICLR 2025
Regressi
Shaping poicy
20-
10-1
10-1
1:0m1
101
Begrosolon
Figure 8: Histogram of the regression losses after fitting the (x. d) parameters the learned co-player shap- ing policics from Figure 3A for 64 random seeds, versus fitting the (x, Φ) parameters 64 uniform random policies.
instead of other-play resulted in similar results with the same main conclusions (data not shown).
For all experiments, used the following hyperparemeters: 7 0.95, 7/meta 0.005, Thaive (except for 1-look-ahead, where we used V/naive = 10). For Figure 4C, we used a convex mixture of the LOLA-DICE gradient and the partial gradient on J' J'(Ø² o= with mixing factor Pnaive. We used Pnaive 1, 1, 0.75, 0.6, 0.4 for look-aheads 1, 2, 3, 10 and 20 respectively.
C.I ADDITIONAL RESULTS ON THE ANALYTICAL IPD
Learning-aware agents extort naive learners following Beero-Determinan--ite extortion strate- gies. Figure 3A shows that learning-awan agents trained against naive learners find a policy that extorts the naive learners into unfair cooperation. Here, we investigate the resulting extortion poli- cies in more detail, and show that they are similar to the Zero-Determinant extortion strategies discovered by Press & Dyson (2012). determenermnnnt extortion strategies are parameterized by and @ as follows (with (T, R, S) =
(2, 1,0, -1) the rewards of the prisoner's dilemma):
R R-8 P
P1 = 1 -(x 1) P-S S
T P P2 = 1 Φ
1 p P-S
(18)
T- P
P3 = 1
x P-S
P4 = 0
with X 2 and 0 < á (X-S)+X(-P) For X and = (P-S)-(T-P) p. we recover the tit- for-tat strategy, representing the fair shaping strategy, whereas for higher values of ri, the resulting policies extort the naive learner into unfair cooperation. Note that Press & Dyson (2012) did not consider a po parameter, as there theory is independent of the choice for po-
To investigate whether learned co-player shaping policies related to ZD extortion strategies, we take the converged policy ((²') after training with the pure shaping objective (c.f. Figure 3A), and fit the parameters (x, σ) to the regression loss [[a(d")[] 5] -p- 2 (x, o) with 22 ø) the ZD extortion policy of Eq. 18. Figure 8 shows that policies learned with the co-player shaping objective can be well aproximated by ZD extortion policies, whereas random policies cannot. The ZD extortion policies of Eq. 18 consider undiscounted infinitely repeated matrix games, whereas we consider discounted infinitely repeated prisoner's dilemma with discount y 0.999. Furthermore, our shaping objective considers the cumuluted returns over the whole learning trajectory of the naive learner, in contrast to Z.D extortion strategies that are optimized for the maximizing the return the last inner episode. Hence, we should not expect exact match between the learned policies a (d') and the ZD extortion strategies.
(x.
Mutual unconditional defection is not Nash equilibrium in the mixed group setting. First, we check numerically whether mutual unconditional defection results in a zero gradient, necessary condition for being Nash equilibrium. As probability corresponds to infinite logits,
24

---

Published as a conference paper at ICLR 2025
A
Mixed group triining starting defection
B
evelution starting from defection
1.2
15
CC
1.0-
10
CD
0.8
logite Srom stoll
DD
Shuping reward Other play reward
0.4
0.2
-5-
0.0
-10
2500
5000
7500
0
2500
51000
7500
10000
Gradient step
Grodient stop
Figure 9: (A) Average reward during training mixed group setting with both agents starting from an unconditional defection policy, when evaluating the learned policy versus naive agents (shaping reward) and versus the other learned policy (other-play reward). (B) Parameter trajectory in logit space of the first agent (the second agent has similar learning trajectories, data not reported). Shaded regions indicate 0,25 and 0.75 quantiles, and solid lines the median over 8 random seeds.
parameterize our policy now directly in the probability space instead of logit space, and consider projected gradient ascent to the probability simplex, i.c. clipping the updated parameters between O and For non-zero mixing factors Pusives this results in a projected gradient that is 0 everywhere, except for the parameter corresponding to the DC state. For shaping naive learners, it is beneficial to reward co-players that cooperate by also cooperating with non-zero probability afterwards. Hence, when an agent with pure defection policy plays against naive learners, the resulting gradient will push it out of the pure defection policy.
Figure 9A shows that when we train unconditional defection policies in the mixed group setting with the same hyperparameters as for Figure 3C, the agents escape mutual defection and learn to cooper- ate. Note that the agents quickly learn how to shape naive learners, and that it takes a bit longer to learn full cooperation, as the shaping objective does not provide pressure to increase the cooperation probability in the starting state. However, the shaping policies of the meta agents longer unconditional defection, playing against other meta agents provides a pressure to increase the cooperation probability, eventually leading a phase transition towards cooperation. Figure 9B shows the parameter trajectory in logit space over training, showing that indeed the agents adjust quickly their parameters for shaping, and eventually also the initial state cooperation probability, leading to cooperation against other meta agents. As our policies are parameterized in logit space, we initialize them log 0.01 instead of exactly zero cooperation probability to avoid infinities.
not any
Tit for Tat is not Nash equilibrium in the mixed group setting. Figure 10 repeats the same analysis but now starting from Tit for Tat policies, showing that mutual Tit for Tat is not a Nash equilibrium in our mixed pool setting. As we show in Figure 10C, this is caused by the possibility to shape naive learners faster by deviating from a strict tit for tat policy. Note that even though the resulting policies are not perfect tit for tat, they still fully cooperate when played against each other.
D PROOFS
R(,) with pa the distribution induced by the environment dynamics Pt. initial state distribution P, and policy oi Then the policy gradient of this expected return is equal to
Theorem D.1. Take the expected shaping return J(6') Eus DEEEER
MT
MT ΣΣ
T 1
B
MT
]
Voi J( Epp
V log n (a
3.b
(19)
V=1'==m/T+1
Proof. In the co-player shaping batched POMDP there is only one agent that is relevant for the policy gradient, as all other agents naive learners and subsumed in the environment dynamics. Hence, to avoid overloading notations, we drop the superscript in the parameters, actions, policy and histories. Furthermore, use the notation d; = {af [a b== and similarly for hy.
25

---

Published as a conference paper at ICLR 2025
Mixod sooup tocning statnng from for
B
Perm eveluiion stcting from tal
Main agest rewari duzing nsive leazner Injecurry
L0
15
0.9
09
10
0.8
Mag forr woa
CC
0,3
0.7
DC
06
00.
Sluying Othesplay reward
Leamndd policy vs mane kaamer
0.5
-10
04
2500
5000
1500
10000
2500
5000
7500
10000
10
15
Gradlent stop
Guadonn stop
Grodicnt sap
Figure 10: (A) Average reward during training a mixed group setting with both agents starting from tit for tat policy, when evaluating the learned policy versus naive agents (shaping reward) and versus the other learned policy (other-play reward). (B) Parameter trajectory in logit space of the first agent (the second agent has similar learning trajectories, data not reported). (C) The reward of main agent when playing against naive learner over trajectory
naive learning steps, showing that the policy learned after convergence the mixed group setting shapes a naive learner faster compared to a tit for tat policy. Shaded regions indicate 0.25 and 0.75 quantiles, and solid lines the median over 8 random seeds.
We start by writing down the gradient of J(Ø) E tions in its expectation explicit.
[ 3
D Ei MT 14/0)
making the summa-
MT
V VOJ(
V
ΣΣΣ
Σ
(0()) Pr) hu, oz)
1 B
1=0 r HHH
with R R the joint reward space, H, the joint space over possible batched histories up until timestep l, and (aa
hu)
T T(a ht). Applying the chain rule leads
V VOJ( Σ MT
Σ v (hi) Pr) hi ai) B b
Σ rt...
1=0 HER ar a.E AHEH
MT
3ΣΣΣ
Ph())o P(r h4, ai) B Σr
1=0 MER MERaEANEH
as the reward dynamics P(r ht) are independent of the policy parameterization d. We first inves- tigate the gradient of the marginal distribution V (aphh)),,, by marginalizing over the joint trajectory distribution.
V Vopo (hi) V
Σ
P(h 11-1,0111
P(h an--i,a-1))FC hr) Pa
II
tav t
Σ
P(h h-1,
II Pdl
P(hy 11--1,r-1) hr) 1ddl
Σ
V log 7 ((ppr (w)))
lay Ahh
Epp
Σ V (aa hv) Mdl
with far A. (hy E Hr hrer the joint space over all actions and histories over timesteps 1' < I. In the second line, we used the chain rule and Van v log π. In the third line we renamed the index (" l'.
Filling this expression for V (hu) into our expression for (Ø). combined with the log trick V = =Va log ग and using the expectation notation for clarity of notation, we end up with
MT
VoJ(
Ep
log ((v hwr)
PS1
26

---

Published as a conference paper at ICLR 2025
Reordering the summations, and using a(a hi) II TTaß
ht)) leads to
V [o)
= pe V (aa
(a} ht))
Finally, actions can only influence the other parallel trajectories through the parameter updates of the naive learners in the environment, which takes place at the inner episode boundaries. Hence, during the current inner episode (before a naive learner update takes place), rewards ry are independent of actions af for b o b' As Eawz [clog (a h)] = 0 for a constant c independent of the actions, the policy gradient is equal
B MT ΣΣ
V J
Epo
V log r(a hP)
B
B
\==1'=m:T-1
with my the inner episode index corresponding to timestep thereby concluding the proof.
Theorem D.2. Assuming that (i) the COALA policy is only conditioned on inner episode histories Fm,t instead of long histories hi and (ii) the naive learners are initialized with the current pa- rameters 6- of the other agents, then the COALA-PG update on the batched co-player shaping POMDP is equal to
m (TgTT)
V J(O")
Σ E pe
J
0'.00' .
0²,
Ad Σ
(20)
dØ
q=1
with Ao (ZG,T the naive learner's update based on the batch of inner-episode histories ēq, and d døz the total derivative, taking into account both the influence of o' through the first argument of - - (Fg,))) as well as through the parameter updates A by adjusting the distribution over T.TT.
Proof. We start by restructuring the long-history expected return J of the batched co- co-player shaping POMDP into sum of inner episode expected returns J from the multi-agent POSG, leveraging the assumptions that the COALA policy only conditioned on inner episode histories o,n, instead of long histories h 5.b and (ii) the naive learners are initialized with the current parameters Φ of the other agents.
B
MT
J(o0) Epp
R
b=1
M-1
(m+
E Exs
1
Σ
Rib
B
m=U
bm
(=mI+1
M-1
B
(m+1))p
Σ
E
pe (Tmmr)
Σ
F
m
Σ
Rdbb
I=
M-1
m
E pot
j
A@ (Zgg(())))))))))))(()
M=U
9=1
with pd' o ++>", Ae ((.,T) the distribution induced by the environment dynamics of the multi- agent POSG, played with policies (0", + Ex (F)r))) The step from line two to three is made possible by the assumption that the COALA policy x² is only conditioned on inner episode histories o/h instead of long histories h.... This ensures that the distribution p over the batch of inner-episode histories 1. only depends on (Ø', (6f Σn AΦ- the policy m does not take previous observations from before the current inner episode boundary into account.
27

---

Published as a conference paper at ICLR 2025
A policy gradient takes into account the full effect of the parameters of policy the trajectory distribution induced by the policy. In our batched co-player shaping POMDP, the trajectory distri- bution induced by policy of influences the reward distribution in the concatenated POSG, well as the naive learner's current parameters through the inner episode batches they use for their updates. Hence, we have that
(0
V VoiJ(
Σ E m=0
poi
Σ
Ao
[gg (Zg.r)
dØ
with des the total derivative, taking into account both the influence of through the first argument of Jd + Σx= (k,,)) as well as through the parameter updates A by adjusting the distribution over Tg thereby concluding the proof.
E RELATING COALA-PG TO LEARNING WITH OPPONENT-LEARNING AWARENESS (LOLA)
In this section, we establish formal relationship between COALA-PG and Learning with Opponent-Lcarinng Awareness (LOLA; Foerster al., 2018a), the seminal work that spearheaded the learning awareness field. In doing so, we further show how COALA-PG can be used to derive new LOLÁ gradient estimator that does not require higher-order derivative estimates.
LOLA considers POSG (c.f. Section 2.2) with agent policies (#' Φ-*), and expected return Jo )) Recall from Section 4 that instead of estimating the naive gradients V''''(Ø', " LOLA anticipates that co-players update their parameters with M naive gradient steps. The im- proved LOLA-DICE (Foerster et al., 2018b) update reads:
LOLA
Jr
Φ 1.00
Σ
s.t. A,0 = a
o² 0' +
def
(21)
with dg. the total derivative taking into account the effect of ø² on the parameter updates Ay0
and 0ø the partial derivative.
Despite the apparent dissimilarities of the two algorithms, we now show in Theorem E.1 that special case of COALA-PG we can estimate the gradient of a similar objective to the LOLA-DICE method. We consider mixed agent group of meta agents (ø', <)=",, and naive learners.
Theorem E.1. Assuming that (i) the COALA policy is only conditioned inner episode histories 3.b Jm,t (instead of long histories bi ), with subscript m = 1,..., M indexing histories over meta- steps, and (ii) the naive learners are initialized with the current parameters & & of the other agents, then the COALA- PPG update on the batched co-player shuping POMDP equals
)
VarJ(
Σ E
pot
Σ A
~ (ZgTT)
(22)
dØ
m=0
9=1
with A ( the naive learner's update based on the batch of inner-episode histories Zg,T-
Compared to the LOLA-DICE gradient of Eq. 21, there are two main differences. (i) LOLA-DICE assumes that the naive learner takes a deterministic gradient step on J, whereas COALA-PG takes into account that the naive learner takes stochastic policy gradient step based on the current mini- batch of inner policy histories. When is linear, we can bring the expectation in the COALA-PG expression inside, resulting in the deterministic gradient, but in general J is nonlinear. DICE considers only the average inner episode return J after M naive learner updates, whereas COALA-PG considers the whole learning trajectory.
(ii) LOLA-
The above two differences are rooted in the distinction of the objectives on which LOLA-DICE and COALA-PG estimate the policy gradient. A bigger difference arises how both methods estimate
28

---

Published as a conference paper at ICLR 2025
the policy gradient. As LOLA-DICE assumes that the naive learner takes deterministic gradient up- dates, their resulting gradient estimator backpropagates explicitly through this learning update, re- sulting in higher-order derivative estimates. By contrast, COALA-PG assumes that the naive learner takes stochastic gradient updates, and can hence estimate the policy gradient through measuring the effect of o² on the distribution of F1,T, and thereby the resulting co-player parameter updates, without requiring higher-order derivatives.
We emphasize that both estimators have their strengths and weaknesses. When LOLA-DICE has access to an accurate model of the co-players and their learning algorithm, explicitly backpropagat- ing through this learning algorithm and model can provide detailed gradient information. However, when the co-player and learning algorithm model are inaccurate, the detailed higher-order deriva- tive information can actually hurt (Zhao al., 2022). this case, a betber--rdder-eervaaiv----eee approach such as COALA-PG can be beneficial.
In sum, in contrast to existing methods, we introduce a return estimator that avoids higher-order derivative computations while taking into account that other agents are themselves undergoing mini- batched reinforcement learning. Furthermore, while methods of the LOLA type require an explicit model of the opponent and its update function, COALA-PO allows for more flexible modeling. Im- portantly, this enables exploiting the information in long histories that cover multiple inner episodes with a powerful sequence model, for which credit assignment can be carried out over long time scales. This makes it possible to combine implicit co-player modeling with modeling the learning of co-players, process known algorithm distillation (Laskin al., 2022).
F DERIVING PRIOR SHAPING ALGORITHMS FROM EQ. 1
The general shaping problem due to Lu et al. (2022) presented in Eq. 1, which we repeat below for convenience, captures many of the relevant co-player shaping techniques in the literature.
M Σ Patars
max LE P.( Bp
I'mO'm mm))
(23)
J
M-FOS solves this co-player shaping problem without making further assumptions (Lu al., 2022). Good Shepherd uses a stateless meta-policy p( 0) = 8( 0). with 6 the Dirac-delta distri- bution (Balaguer et al., 2022). Meta-MAPG (Kim et al., 2021) meta-learns an initialization ob in the spirit of model-agnostic meta-lcarning (Finn et al., 2017). and lets every player learn by following gradients on their respective objectives. The meta-value learning method (Cooijmans et al., 2023) models the meta-policy p( 6t 2mi;;) V mm (ym") parameterized by 0. Finally, we recover single LOLA update step (Foerster et al., 201 8a) by initializing (oh. < with the current parameters of all agents, taking M = Mstart = 1, using a stateless meta-policy pa(o,, 0) 6(02.. = 0) and taking a single gradient step w.r.t 0 instead of solving the shaping problem convergence.
0) as the gradient on a meta-value function
G DETAIL ON BASELINE METHODS
G.1 BATCH-UNAWARE COALA PG
We remind that the policy gradient expression for COALA is as follows
MT ΣΣ
B MT
]
V J(H
E p
V oe log (a 1)
Ri
(24)
B
The batch-unaware COALA PG is the naive baseline, consisting in applying policy gradient methods to individual trajectories in batch, i.e.
MT
MT
di batch-unaware J(6') par
V Φe log n' (a
i.b
Σ
R2b
(25)
B
1=1
k=
29

---

Published as a conference paper at ICLR 2025
COALA-PG agent
Paraliel, Batch-Unaware Agent
MT
MT
Figure 11: Diagram visualizing the difference between the COALA-PG update and the batch unaware COALA policy gradient update.
Figure 11 visualizes the main difference between the COALA-PG update and the batch-unaware COALA-PG update.
G.2 M-FOS
Lu et al. (2022) consider both a policy gradient method and evolutionary search method to optimize the shaping problem of Eq. 1. Here, we focus on the M-FOS policy gradient method, which was used by Lu et al. (2022) in their Coin Game experiments, which is their only experiment that goes beyond tabular policies. M-FOS uses distinct architecture with recurrent neural network inner policy, which receives an extra conditioning vector as input from a meta policy that processes inner episode batches. As shown by Khan et al. (2024), we can obtain better performance by combining both inner and meta policy in a single sequence model with access to the full history fı containing all past inner episodes. Hence, we use this improved architecture for our M-FOS baseline, which we train by the policy gradient method proposed by Lu et al. (2022). This allows us to use the same architecture for both M-FOS and COALA.
As the manuscript of (Lu et al., 2022) does not explicitly mention how to deal with the iuner-batcl dimension of naive learner, we reconstruct the learning rule from their publicly available codebase. By denoting by my the inner episode index corresponding to the meta episode time step 1, the update as follows:
Tim R
MT
J(O') =B po
de I' (a
R
B
(26)
We note that when taking the inner-episode boundaries into account in the COALA-PG update, due to some terms disappearing from the expectation, the expression becomes
B
MT
Tme
B
MT
V J(O') = E
ΣΣ
log 7' (a 11
B
lo
(27)
One can see that the M-FOS update rule closely resembles COALA-PG, except for the fact that B in front of the reward of the current inner episode. As we show in our
it is lacking a factor 1 experiments, this biases the policy gradient and introduces inefficiencies the optimization.
H ADDITIONAL EXPERIMENTAL RESULTS
H.1 BALANCING GRADIENT CONTRIBUTIONS
The main difference between COALA-PG (c.f. Eq. 3) and M-FOS is the scaling of the current reward-episode. The main difference between COALA-PG equation and M-FOS equation 7 is that COALA-PG scales the return of the current inner episode by म. whereas M-FOS does not. This scaling is crucial, the the influence of action future inner episodes is of order O(+) because
30

---

Published as a conference paper at ICLR 2025
Ratio future shaping gradient / current inner episode gradient WW AWW
Arw
COALA+G
MFDS
Batch-unaware COALA-PG MMyh
10
M MAY
105
150
250
Training steps
Figure 12: Y-axis: Ratio of the magnitude of the policy gradient contribution arising from future inner episode returns (the co-player shaping learning signal) w.r.t. the gradient contribution arising from the current inner episode return. X-axis: meta gradient steps on the iterated prisoner's 's dilemma, a mixed group setting cor- responding to the setting of Fig. 5C, and an increased meta-batch size of 2048 to reduce the variance of the gradient estimates.
the naive learner averages its update over the B inner episode trajectories. Hence, by scaling the inner episode return by 1. COALA-PG ensures that both contributions have the same scaling w.r.t T:
B, and finally by summing the policy gradient over the minibatch instead of averaging, with a policy gradient of (1). M-FOS and batch-unaware COALA do not scale the current inner episode return, which causes the co co-player shaping learning signal to vanish w.r.t. the current inner episode return, resulting in poor shaping performance.
end up
Figure 12 confirms that empirically, COALA-PG correctly balances the gradient contributions from the current inner episode return with those from future inner episode returns. In contrast, M-FOS and batch-unaware COALA have unbalanced gradient contributions, with the co-player shaping gradient contribution vanishing w.r.t. the current inner episode return contribution.
H.2
DETAILED RESULTS ON C.RRAKUP-TTTE
A
B
C
Avg. reverd mete agent
Claniing Discrcancy
0.15
0.20
Zappeed
0.06
0.25
0.02
0.15
300
1000
1500
2000
2500
500
1000
1500
2000
2300
500
1000
1500
2000
2500
Trininn neration
Training Iteration
Taining iteratioo
Avg. reward ralve agents
0.05
4.2
0.04
Avcrage Pollution
4.0
0.6
0.03
Average
0.02
3.6-
500
1000
1500
2000
2500
500
1000
1500
2000
2500
500
1500 :000
2000
2500
Training Iterrtion
Triniing Reretion
Training iteration
COALA
M.FOS
LOLA
Batch COALA
Figure 13: Agents trained by COALA-PG against naive agents only successfully shape them in CleanUp-lite. (A) COALA- A-PG-trained agents better shape naive opponents compared to baselines, ab- taining higher return. (B and C) Analyzing behavior within single meta-episode after training reveals that COALA outperforms baselines and shapes naive agents, exhibiting lower elcaning discrepancy (absolute difference in average cleaning time between reward of naive learners is higher when playing with CCALA-PG agents compared to other agents. (E and F): COALA-PG results in lower average pollution level and higher average apple level. Shaded regions indicate standard deviation computed over 5 seeds.
two agents), and (ii) being less often zapped.
(D) Average
31

---

Published as a conference paper at ICLR 2025
B
Aug rewerd meto egents
0.20
Cleaning Discrejancy
0.20
0.2
0.10
0.00
10000
20000
30000
10000
20000
30000
10000
20003
50000
Training neration
Training teration
Training iteration
Average Apple Uevel
1.00
Rverage Pollution Level
4.0
3.5
0.50
3.0
0.25
10000
30000
10000
30000
Iteration
Traininn
COALA-PG
M-F05
LOLA
Batch-unaware COALA-PG
Meta Agent Only
Figure 14: Agents trained with COALA-PG against mixture of naive and other meta agents learn to cooperate in CleanUp-lite. (A) COALA-PG-trrin agents obtain higher average reward than baseline agents when playing against each other. and C): COALA-PO leads to more fair division cleaning efforts and lower zapping rates. (D and E): COALA-PA PPG results in lower average pollution level and higher average apple level. Shaded regions indicate standard deviation.
H.3 TRAINING A COALA-PG AGENT VERSUS AN M-FOS AGENT ON ITERATED PRISONER DILEMMA
We investigate training COALA-PG versus M-FOS agent, our strongest performing meta-agent baseline. In this setup, we still use mixture naive learners and meta agents. Only now when COALA-PG agent either plays against an M-FOS agent or naive learner, and an M-FOS agent either plays against a COALA- PG agent or a naive learner. We found that COALA- PG successfully shapes M-FOS into cooperation, reaching average rewards of 0.850 + 0.037 for COALA-PA and 0.853 + 0.017 for M-FOS. This is in stark contrast to when M-FOS agents only play against other M-FOS agents and naive learners, which converges mutual defection.
We did not investigate training a COALA- PG agent versus a LOLA agent, as the training setup of both agents is fundamentally different, and would pose unfair disadvantage for LOLA agents. LOLA agent learns on the same timescale as naive learners, taking a few look-ahead steps into account in its update. Hence, the full learning trajectory of LOLA agent considered as one meta trajectory for a COALA-P PG agent. As COALA PG agents would play many different meta trajectories, always against freshly initialized LOLA agent, this would give COALA-PA detailed information about the learning behavior of LOLA agents, whereas LOLA agents are left in the dark as they cannot observe the meta updates of COALA-PG, Hence, COALA-PA PG would extort LOLA agents similar to naive learners.
I SOFTWARE
The results reported in this paper were produced with open-source software. We used the Python programming language together with Google JAX (Bradbury al., 2018) framework, and the NumPy (Harris et al., 2020), Matplotlib (Hunter, 2007), Flax (Heck al., 2024) and Optax (Babuschkin al., 2020) packages.
32


Reviews:
[{"review_id": "PIeO0byRW3", "reviewer": "Reviewer_xxyH", "summary": "This paper introduces a new learning-aware reinforcement learning rule derived as a policy gradient estimator. Instead of using long histories of samples, the policy gradients consider the stochastic minibatch updates used by other agents. The results show improvements in some mixed environments. Overall, the paper is well-written and well-organized. The notations are standard, and the theorems are sound.", "questions": "please see the weaknesses", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and well-organized. \n2. Theoretical proofs are complete and sound.", "weaknesses": "1. The motivation for proposing COALA-PG is unclear. It’s not obvious whether the issue is related to variance or other issues when using mini-batches. The authors suggest that larger mini-batches could pose a problem, but this may lead to higher variance in reward summation. However, these points are not extensively discussed in the manuscript. Additionally, compared to M-FOS, it appears that COALA-PG uses the 1/B term to scale rewards, but it seems that this scaling is still related to controlling the policy gradient’s variance.\n\n2. Why not use a Q-function instead of summing rewards?\n\n3. In Theorem 3.1, what is the advantage of using batches of inner episode histories instead of a long history? Are there any theoretical insights supporting this approach?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wlY6dzZMJW", "reviewer": "Reviewer_GXnN", "summary": "This study presents a framework for multi-agent cooperation in partially observable general-sum games to enable agents to adaptively cooperate in non-stationary environments by conditioning their policies on past interactions. The COALA-PG method introduces improved policy calculation through accumulated gradients and variance reduction that enhances stability and computational efficiency. The framework is tested on benchmark tasks such as the Iterated Prisoner´s Dilemma and the Cleanup game, demonstrating cooperative behavior among decentralized agents.", "questions": "1. Given that full history dependency may reduce partially observable settings to fully observable ones in discrete environments, have the authors conducted a sample complexity analysis for handling true partial observability, where agents have limited access to or storage for historical data?\n2. Could the authors elaborate on their choice of the Iterated Prisoner´s Dilemma and Cleanup as experimental benchmarks? \n3. Could the authors discuss whether any convergence properties have been considered for COALA-PG? Given the absence of a formal convergence analysis, how do the authors anticipate the framework will behave in non-stationary environments?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. **History-Dependent Adaptation for Multi-Agent Cooperation:** The paper introduces a promising approach that enables agents to adaptively cooperate by conditioning policy updates on observation histories. This allows agents to respond to non-stationarity in general-sum games, specifically handling the evolving distributions of co-agent strategies as each agent independently learns and adapts over time. By incorporating these historical observations, the framework aims to maintain effective cooperation even as the behaviors of other agents shift dynamically, without explicitly modeling the non-stationarity or learning dynamics of other agents.\n2. **Theoretical and Practical Advancements in Policy Gradient Estimation:** Theorems 3.1 and 3.2 present a robust policy gradient estimation method specifically designed for cooperative multi-agent learning. COALA-PG´s use of accumulated gradients and minibatch summation approach improves stability and adaptability without requiring higher-order gradients. This makes COALA-PG more scalable in comparison to methods like LOLA-DICE. Additionally, the use of value function baselines in gradient estimation reduces variance which increases COALA-PG´s practical applicability.\n3. **Supporting Results Against Naive Learner Baselines:** Empirical comparisons demonstrate that COALA-PG outperforms naive, non-history-conditioned learners, demonstrating the benefit of history dependency in non-stationary environments.", "weaknesses": "1. **Full History Dependency:** While history dependency enables adaptability, it may approximate full observability, especially in discrete environments. By accumulating state-action information over time, agents in discrete settings could essentially reconstruct the environment as if fully observable, reducing the framework´s applicability in scenarios where true partial observability is intended.\n2. **Simplistic Experimental Scenarios:** The chosen experiments, such as the Iterated Prisoner’s Dilemma (IPD) and Cleanup, are relatively simple and do not fully demonstrate the framework´s ability to manage partial observability or complex, dynamic cooperation. IPD lacks multi-step state evolution, and while Cleanup provides more interaction, it still operates in a low-dimensional grid setting, which is easier for agents to handle than high-dimensional or real-world environments.\n3. **Lack of Convergence Analysis:** COALA-PG lacks formal guarantees of stability or convergence in non-stationary environments. This leaves open questions about COALA-PG´s ability to adapt as agent strategies evolve. The study would benefit from additional theoretical or empirical validation to support its effectiveness in highly dynamic settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gjnS5DxzE4", "reviewer": "Reviewer_pFwY", "summary": "To solve two challenges of general-sum games: 1. Non-stationarity of the environment, hard to choose a good equilibrium. The author propose an unbiased, higher derivative-free policy gradient algorithm for learning-aware RL, which considers how the action will influence the other agent's policy changing: They do policy gradient in meta-episode. They have extensive theoratic comparison of their meta policy gradient with prior works. And have interesting findings in the iterated prisoner's dilemma and a grid-world-like social dilemma \"CleanUp\".", "questions": "None", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Clear writing, clear concept definition.\n2. extensive theoratic comparison with prior works and experiments on two non-trivial settings.\n3. enough details of implementation in the appendix.", "weaknesses": "This may be difficult, but it would be great if you could show the efficiency of your method on more difficult environments of deep MARL beyond matrix game or grid world (like Agar.io[1])\n\n[1]: Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization, ICLR 2021", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TFuqvAe3Tq", "reviewer": "Reviewer_fP5Y", "summary": "The paper introduces a novel policy gradient algorithm for learning-aware reinforcement learning, which allows agents to model the learning dynamics of other agents. This approach enables cooperative behavior among self-interested agents, even in complex scenarios like temporally extended action coordination. The algorithm avoids higher-order derivatives, and can handle mini-batched learning. Additionally, the paper provides a theoretical explanation for the emergence of cooperation in the iterated prisoner's dilemma based on learning awareness and agent heterogeneity.", "questions": "1.\tWhat are the key differences between the proposed batched co-player shaping POMDP and a standard POMDP with parallel environments? Equation 3 appears to simply sum rewards across parallel environments, making it unclear what distinct advantages this formulation provides.\n2.\tThe font size in the figures is too small, making it difficult to read. Enhancing font size and clarity would significantly improve readability.\n3.\t There are well-known baseline methods in the mixed-motive game literature, particularly within the Cleanup environment. Why does the paper not include comparisons with these established methods?\n4.       More information is needed on the simplified Cleanup environment. How does it differ from the standard Cleanup environment, and what are the implications of these differences for the study’s findings?\n5.\t While the paper aims to address a mixed-motive game, the problem is formulated as a general-sum game. In my view, general-sum games are not fully equivalent to mixed-motive games. Could you clarify the rationale behind this formulation choice?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper tackles a core issue in multi-agent learning - fostering cooperation among self-interested agents.\n2. The introduction of the first unbiased, higher-derivative-free policy gradient algorithm for learning-aware reinforcement learning is a significant contribution.\n3. The proposed algorithm appears to outperform existing methods in achieving cooperation.\n4.The paper proposes a novel explanation for cooperation emergence based on learning-awareness and agent heterogeneity in the iterated prisoner's dilemma.", "weaknesses": "In my view, the “elegant” formulation and the batched co-player shaping POMDP appear similar to a parallel environment POMDP setup, while COALA-PG seems more like a delayed optimization applied after several episodes. This raises concerns about the true novelty and contribution of the work. I have a few specific questions regarding this point.\n\nIt’s entirely possible that I may not yet have fully understood the paper. However, improving the paper’s clarity and structure would make it more accessible and easier to follow.\n\nI look forward to discussing these points with the authors, and I am open to raising my score if my concerns are addressed satisfactorily.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kYn10iLAS2", "reviewer": "Reviewer_MZki", "summary": "The paper brings sound improvements over the current opponent shaping methods for non-cooperative general-sum games with self-interested learners. The core contributions over the existing methods are introducing a policy-gradient method (COALA-PG) capable of shaping other learners without making any assumptions on learners' optimization functions due to the sequential and batched nature of the expected return to be maximized. The method is evaluated on Iterated Prisoner's Dilemma and CleanUp environments. COALA-PG is compared to M-FOS and variants of itself as a baseline and investigation of how the pool of learners, whether they are meta or naive learners, affect reaching cooperation.", "questions": "* Why is there no experiment for LOLA?\n* Why does batch-unaware COALA-PG perform so similar to M-FOS, while the batch-aware COALA-PG surpasses it? Did you investigate how gradients change and why the batch-aware gradients work so well?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "* Introduction of a novel unbiased policy gradient formulation to shape naive learners that does not need to know the learners' optimization functions but can infer them by sequence modeling.\n* Comparisons showing the effect of how learners are pooled (meta vs naive or meta vs meta etc.) give insight into how shaping is achieved.\n* COALA-PG improves performance over M-FOS.\n* The figures are informative.", "weaknesses": "* There is insufficient explanation on why COALA-PG is so much better than batch-unaware COALA-PG which perform very similar to M-FOS. The credit assignment figure is a nice visualization to give intuition, but it does not provide concrete explanation and we have to speculate. Since batch-awareness is the main factor that makes COALA-PG's performance superior, it is difficult to attribute the success to sequence modeling and inferring the learning dynamics. There should be an investigation into how batch-awareness affect and change gradients and why batch-unaware COALA-PG is performs similar to MFOS.\n* Baselines are insufficient. The only shaping method compared is the MFOS. Although mentioned in the paper, no comparison to Shaper is done in experiments. There is no comparison to LOLA either; even though MFOS is already expected to outperform LOLA, still a verification should have been done.\n* There is no versus for different shaping methods, i.e. there is no experiment on how COALA-PG shapes M-FOS and vice versa.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BhiN7xvrqe", "reviewer": "Reviewer_UL6h", "summary": "This work proposes a new paradigm for MARL that enables agents to be aware of inter-episode dynamics and presents compelling experimental results in both the iterated prisoner’s dilemma and a grid-world sequential social dilemma.", "questions": "Questions are mentioned in the weaknesses part.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This work addresses a central challenge in MARL.\n- The proposed framework (Figures 1 and 2) is important.\n- The method parameters are thoroughly detailed in the appendix.\n- Finding 1 is especially intriguing.", "weaknesses": "- Line 114: The metric used in this work is ambiguous. Could you clarify which metric is applied in subsequent sections? What expectations should we have to claim that the proposed method outperforms other algorithms?\n\t- In Line 485, it appears the objective is solely the meta-agent's reward rather than equilibrium. Can we then say that this work is aimed at developing an algorithm to exploit naive agents?\n\t- Or is this an agent-based simulation method?\n\n- Line 191: The definition states that the \"state\" in this game includes all agents' policy parameters. This creates an exponentially large space, especially when agents are assumed to use neural networks. In this case, the state encompasses the combined network parameters of all agents.\n\t- To implement a meta-agent in this setting, does the input of its policy network include the policy network parameters of other naive agents? If so, how is this optimized and implemented?\n\t- According to equation (4) and (5), I suppose that the meta agent does not input the others' parameters to its own policy network, but treats it by sampling the gradient. Then why is this estimation unbiased? Using sampling method does not seem to solve the non-stationarity issue. And this contradicts the motivation of this method.\n\t- If there are two meta-agents in the training phase, how do they treat each other? Are their gradient chains intertwined, or do they simply treat one another as naive agents?\n- Line 998: The proof relies on Sutton’s policy gradient theorem, which assumes a fully observable environment. But Line 72 states that this environment is partially observable. Does the derivation still hold in this case? (I doubt the gradient computation is exact in this context, but I understand it may be an acceptable estimate for experimental purposes.)\n\t- Equation (4) shouldn’t be an equality but should have a scaling factor.\n- Line 370: This experiment begins from a specific initialization point. The maximum expected reward is slightly lower than the cooperation reward of 1. Although this is a challenging case, what would results look like for different initialization points? Can a learning-aware agent achieve better outcomes (with an expected reward greater than 1)?\n- Figure 3B and 3C: Does the proposed method require interaction with naive agents to initiate training?\n- Why is there no comparison between COALA and M-FOS in Figure 5?\n\nMinors:\n\n- Why are all references in blue font? This formatting seems differ from other submissions.\n- In Lines 14, 33, 49, 106, 122, 161, 185, 478, and 479, the single quotation marks should be replaced with double quotation marks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)