Advantage Alignment Algorithms

## Abstract

Abstract Artificially intelligent agents are increasingly being integrated into human decision-making: from large language model (LLM) assistants to autonomous vehicles. These systems often optimize their individual objective, leading to conflicts, particularly in general-sum games where naive reinforcement learning agents empirically converge to Pareto-suboptimal Nash equilibria. To address this issue, opponent shaping has emerged as a paradigm for finding socially beneficial equilibria in general-sum games. In this work, we introduce Advantage Alignment, a family of algorithms derived from first principles that perform opponent shaping efficiently and intuitively. We achieve this by aligning the advantages of interacting agents, increasing the probability of mutually beneficial actions when their interaction has been positive. We prove that existing opponent shaping methods implicitly perform Advantage Alignment. Compared to these methods, Advantage Alignment simplifies the mathematical formulation of opponent shaping, reduces the computational burden and extends to continuous action domains. We demonstrate the effectiveness of our algorithms across a range of social dilemmas, achieving state-of-the-art cooperation and robustness against exploitation.

### 1 Introduction

Recent advancements in artificial intelligence, such as language models like GPT (Radford et al.,, ), image synthesis with diffusion models (Ho et al.,, ), and generalist agents like Gato (Reed et al.,, ), suggest a future where AI systems seamlessly integrate into everyday human decision-making. While these systems often optimize for the goals of their individual users, this can lead to conflicts, especially in tasks that involve both cooperative and competitive elements. Social dilemmas, as introduced by Rapoport and Chammah, (), describe scenarios where agents acting selfishly achieve worse outcomes than if they had cooperated. A global example is the climate change problem, where individual and national interests in economic growth often clash with the need for collective action to reduce carbon emissions and mitigate environmental degradation. The challenges we have faced in tackling this problem highlight the complexity of aligning individual interests with collective well-being.

As artificially intelligent systems become ubiquitous, there is a pressing need to develop methods that enable agents to autonomously align their interests with one another. Despite this, the deep reinforcement learning community has traditionally focused on fully cooperative or fully competitive settings, often neglecting the nuances of social dilemmas. Sandholm and Crites, () empirically demonstrated that naive reinforcement learning algorithms tend to converge to the worst Pareto suboptimal Nash equilibria of Always Defect in social dilemmas like the Iterated Prisoner’s Dilemma (IPD). , demonstrated that the same is true for policy gradient methods, and introduced opponent shaping (LOLA) to address this gap.

LOLA is an opponent shaping algorithm that influences the behavior of other agents by assuming they are naive learners and taking gradients with respect to simulated parameter updates. Following this approach, other opponent shaping algorithms that compute gradients with respect to simulated parameter updates have shown success in partially competitive tasks, including SOS (Letcher et al.,, ), COLA (Willi et al.,, ), and POLA (Zhao et al.,, ). More recently, LOQA () proposed an alternative form of opponent shaping by assuming control over the value function of other agents via REINFORCE estimators (Williams,, ). This new approach to opponent shaping offers significant computational advantages over previous methods and lays the foundation for our work.

We introduce Advantage Alignment, a family of algorithms designed to shape rational opponents by aligning their advantages when their historic interactions have been positive. We make two key assumptions about reinforcement learning agents: (1) they aim to maximize their own expected return, and (2) they take actions proportionally to this expected return. Under these assumptions, we demonstrate that opponent shaping reduces to aligning the advantages of different players and increasing the log probability of an action proportionally to their alignment. We show that this mechanism lies at the heart of existing opponent shaping algorithms, including LOLA and LOQA. By distilling this objective, Advantage Alignment agents can shape opponents without relying on imagined parameter updates (as in LOLA and SOS) or stochastic gradient estimation that relies on automatic differentiation introduced in DiCE () (as in POLA, COLA, and LOQA). Furthermore, we demonstrate that Advantage Alignment preserves Nash Equilibria, ensuring that our algorithms maintain stable strategic outcomes.

We also introduce Proximal Advantage Alignment, which formulates Advantage Alignment as a modification to the advantage function used in policy gradient updates. By integrating this modified advantage into the Proximal Policy Optimization (PPO) () surrogate objective, we develop a scalable and efficient opponent shaping algorithm suitable for more complex environments. To identify and overcome challenges that arise from scale—which are often overlooked in simpler settings like the Iterated Prisoner’s Dilemma (Rapoport and Chammah,, ) and the Coin Game ()—we apply Advantage Alignment to a continuous variant of the Negotiation Game (Cao et al.,, ) and Melting Pot’s Commons Harvest Open (Agapiou et al.,, ). In doing so, we aim to demonstrate the scalability of our methods and offer insights and solutions applicable to complex, real-world agent interactions.

Our key contributions are:

- •
We introduce Advantage Alignment and Proximal Advantage Alignment (PAA), two opponent shaping algorithms derived from first principles and based on policy gradient estimators.
- •
We prove that LOLA (and its variations) and LOQA implicitly perform Advantage Alignment through different mechanisms.
- •
We extend REINFORCE-based opponent shaping to continuous action environments and achieve state-of-the-art results in a continuous action variant of the Negotiation Game (Cao et al.,, ).
- •
We apply PAA to the Commons Harvest Open environment in Melting Pot 2.0 (Agapiou et al.,, ), a high dimensional version of the tragedy of the commons social dilemma, achieving state-of-the-art results and showcasing the scalability and effectiveness of our methods.

### 2 Background

#### 2.1 Social Dilemmas

Social dilemmas describe situations in which selfish behavior leads to sub-optimal collective outcomes. Such dilemmas are often formalized as normal form games and constitute a subset of general-sum games. A classical example of a social dilemma is the Iterated Prisoner’s Dilemma (IPD) (Rapoport and Chammah,, ), in which two players can choose one of two actions: cooperate or defect. In the one-step version of the game, the dilemma occurs because defecting is a dominant strategy, i.e., independently of what the opponent plays the agent is better off playing defect. However, by the reward structure of the game, both the agent and the opponent would achieve a higher utility if they played cooperate simultaneously. Beyond the IPD, other social dilemmas have been extensively studied in the literature, including the Chicken Game and the Coin Game (Lerer and Peysakhovich,, ), the latter of which has a similar reward structure to IPD but takes place in a grid world. In this paper we introduce a variation of the Negotiation Game (also known as the Exchange Game) (DeVault et al.,, ; Lewis et al.,, ), with a strong social dilemma component. Additionally, we evaluate our method on the Commons Harvest Open environment in Melting Pot 2.0 (Agapiou et al.,, ), which exemplifies a large-scale social dilemma. In this environment, agents must balance short-term personal gains from overharvesting common resources against the long-term collective benefit of sustainable use.

#### 2.2 Markov Games

In this work, we consider fully observable, general sum, $n$-player Markov Games (Shapley,, ) which are represented by a tuple: $\mathcal{M}=(N,\mathcal{S},\mathcal{A},P,\mathcal{R},\gamma)$. Here $\mathcal{S}$ is the state space, $\mathcal{A}:=\mathcal{A}^{1}\times\ldots\times\mathcal{A}^{n}$, is the joint action space for all players, $P:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$ maps from every state and joint action to a probability distribution over states, $\mathcal{R}=\{r^{1},\ldots,r^{n}\}$ is the set of reward functions where each $r^{i}:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ maps every state and joint action to a scalar return and $\gamma\in[0,1]$ is the discount factor.

#### 2.3 Reinforcement Learning

Consider two agents playing a Markov Game, 1 (agent) and 2 (opponent), with policies $\pi^{1}$ and $\pi^{2}$, parameterized by $\theta_{1}$ and $\theta_{2}$ respectively. We follow the notation of Agarwal et al., (), let $\tau$ denote a trajectory with initial state distribution $\mu$ and (unconditional) distribution given by:

$$ $\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}(\tau)=\mu(s_{0})\pi^{1}(a_{0}|s_{0})\pi^{2}( b_{0}|s_{0})P(s_{1}|s_{0},a_{0},b_{0})\ldots$ (1) $$

Where $P(\cdot|s,a,b)$, often referred as the transition dynamics, is a probability distribution over the next states conditioned on the current state being $s$, agent taking action $a$ and opponent taking action $b$. Value-based methods like Q-learning (Watkins and Dayan,, ) and SARSA (Rummery and Niranjan,, ) learn an estimate of the discounted reward using the Bellman equation:

$$ $Q^{1}(s_{t},a_{t},b_{t})=r^{1}(s_{t},a_{t},b_{t})+\gamma\cdot\mathbb{E}_{s_{t+ 1}}\left[V^{1}(s_{t+1})|s_{t},a_{t},b_{t}\right].$ (2) $$

In policy optimization, both players aim to maximize their expected discounted return by performing gradient ascent with a REINFORCE estimator (Williams,, ) of the form:

$$ $\nabla_{\theta_{1}}V^{1}(\mu)=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi ^{2}}}\left[\sum_{t=0}^{\infty}\gamma^{t}A^{1}(s_{t},a_{t},b_{t})\nabla_{ \theta_{1}}\log\pi^{1}(a_{t}|s_{t})\right].$ (3) $$

Here $A^{1}(s,a,b)$ denotes the advantage of the agent taking action $a$ in state $s$ while the opponent takes action $b$.

### 3 Opponent Shaping

Opponent shaping, first introduced in LOLA (), is a paradigm that assumes the learning dynamics of other players can be controlled via some mechanism to incentivize desired behaviors. LOLA and its variants assume that the opponent is a naive learner, i.e. an agent that performs gradient ascent on their value function, and differentiate through an imagined naive update of the opponent in order to shape it.

LOQA () performs opponent shaping by controlling the Q-values of the opponent for different actions assuming that the opponent’s policy is a softmax over these Q-values:

$$ $\hat{\pi}^{2}(b_{t}|s_{t}):=\frac{\exp Q^{2}(s_{t},b_{t})}{\sum_{b}\exp Q^{2}( s_{t},b)},$ (4) $$

where $Q^{2}(s_{t},b_{t}):=\mathbb{E}_{a\sim\pi^{1}}[Q^{2}(s_{t},a,b_{t})]$.
The key idea is that these Q-values depend on $\pi^{1}$, and hence the opponent policy $\hat{\pi}^{2}$ can be differentiated w.r.t. $\theta_{1}$:(^1^11See Appendix A.3 for a derivation of this expression.)

$$ $\nabla_{\theta_{1}}\hat{\pi}^{2}(b_{t}|s_{t})=\hat{\pi}^{2}(b_{t}|s_{t})\left( \nabla_{\theta_{1}}Q^{2}(s_{t},b_{t})-\sum_{b}\hat{\pi}^{2}(b|s_{t})\nabla_{ \theta_{1}}Q^{2}(s_{t},b)\right).$ (5) $$

This dependency of $\pi^{2}$ on $\theta_{1}$ leads to the emergence of an extra term in the policy gradient:

$$ $\nabla_{\theta_{1}}V^{1}(\mu)=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi ^{2}}}\left[\sum_{t=0}^{\infty}\gamma^{t}A^{1}(s_{t},a_{t},b_{t})\left( \underbrace{\nabla_{\theta_{1}}\log\pi^{1}(a_{t}|s_{t})}_{\text{policy gradient term}}+\underbrace{\nabla_{\theta_{1}}\log\pi^{2}(b_{t}|s_{t})}_{ \text{opponent shaping term}}\right)\right].$ (6) $$

demonstrate an effective way to account for this dependency using REINFORCE.
The present work builds on the ideas of LOQA, but reduces opponent shaping to its bare components to derive Advantage Alignment from first principles.

### 4 Advantage Alignment

#### 4.1 Method Description

Figure: Algorithm 1 Advantage Alignment

Motivated by the goal of scaling opponent shaping algorithms to more diverse and complex scenarios, we derive a simple and intuitive objective for efficient opponent shaping. We begin from the assumptions that agents are learning to maximize their expected return, and will behave in a fashion that is proportional to this goal:

###### Assumption 1 .

Each agent $i$ learns to maximize their value function: $\max V^{i}(\mu)$.

###### Assumption 2 .

Each opponent $i$ acts proportionally to the exponent of their action-value function: $\pi^{i}(a|s)\propto\exp\left(\beta\cdot Q^{i}(s,a)\right)$.

Using Equation 6 and substituting $\hat{\pi}^{2}$ in place of $\pi^{2}$ (per Assumption 2), we obtain:

$$ $\nabla_{\theta_{1}}V^{1}(\mu)=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi ^{2}}}\left[\sum_{t=0}^{\infty}\gamma^{t}A^{1}(s_{t},a_{t},b_{t})\left(\nabla_ {\theta_{1}}\log\pi^{1}(a_{t}|s_{t})+\nabla_{\theta_{1}}\log\hat{\pi}^{2}(b_{t }|s_{t})\right)\right].$ $$

The first term is the usual policy gradient. The second term is the opponent shaping term and will be our focus. Approximating the opponent’s policy (right hand side of equation 4) by ignoring the contribution due to the partition function, the opponent shaping term becomes:

$$ $\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{\infty }\gamma^{t}A^{1}(s_{t},a_{t},b_{t})\nabla_{\theta^{1}}Q^{2}(s_{t},b_{t})\right].$ (7) $$

The gradient of the Q-value can be estimated by a REINFORCE estimator, which leads to a nested expectation. empirically showed that this nested expectation can be efficiently estimated from a single trajectory. We take the same approach (see Appendix A.1) to obtain:

$$ $\beta\cdot\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t= 0}^{\infty}\gamma^{t+1}\left(\sum_{k<t}\gamma^{t-k}A^{1}(s_{k},a_{k},b_{k}) \right)A^{2}(s_{t},a_{t},b_{t})\nabla_{\theta^{1}}\text{log }\pi^{1}(a_{t}|s_{ t})\right].$ (8) $$

The expression above captures the essence of opponent shaping: an agent should align its advantages with those of its opponent in order to steer towards trajectories that are mutually beneficial. More precisely, an agent increases the probability of actions that have high product between the sum of its past advantages and the advantages of the opponent at the current time step. For implementation details of the Advantage Alignment formula see Appendix A.6. Equation 8 depends only on the log probabilities of the agent, which allows us to create a proximal surrogate objective that closely follows the PPO () formulation:

$$ $\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\min\left\{r_{n}( \theta_{1})A^{*}(s_{t},a_{t},b_{t}),\;\text{clip}\left(r_{n}(\theta_{1});1- \epsilon,1+\epsilon\right)A^{*}(s_{t},a_{t},b_{t})\right\}\right],\\$ (9) $$

where $r_{n}$ denotes the ratio of the policy (new) after $n$ updates and the original policy (old), and:

$$ $A^{*}(s_{t},a_{t},b_{t})=\left(A^{1}(s_{t},a_{t},b_{t})+\beta\gamma\cdot\left( \sum_{k<t}\gamma^{t-k}A^{1}(s_{k},a_{k},b_{k})\right)A^{2}(s_{t},a_{t},b_{t}) \right).$ (10) $$

This surrogate objective in equation 9 is used to formulate the Proximal Advantage Alignment (Proximal AdAlign) algorithm (see appendix A.7 for implementation details).

Why is Assumption 1 necessary? Assumption 1 allows the agent to influence the learning dynamics of the opponent, by controlling the values for different actions. After one iteration of the algorithm the agent changes the Q-values of the opponent for different actions and, since the opponent aims to maximize their expected return, it must change its behavior accordingly.

###### Assumption 1 .

###### Assumption 2 .

#### 4.2 Analyzing Advantage Alignment

Figure: (a)
Refer to caption: x1.png

Equation 8 yields four possible different cases for controlling the direction of the gradient of the log probability of the policy. As with the usual policy gradient estimator, the sign multiplying the log probability indicates whether the probability of taking an action should increase or decrease. Intuitively, when the interaction with the opponent has been positive (blue in figure 1(a)) the advantages of the agent align with that of the opponent: the advantage alignment term increases the log probability of taking an action if the advantage of the opponent is positive and decreases it if it is negative. In contrast, if the interaction has been negative (red in figure 1(a)) the advantages are at odds with each other: the advantage alignment term decreases the log probability of taking an action if the advantage of the opponent is positive and increases it if it is negative. We now relate existing opponent shaping algorithms to advantage alignment, and argue that these algorithms use the same underlying mechanisms. Theorem 1 shows that LOLA update from  can be written as a policy gradient method with an opponent shaping term similar to equation 10. This shows the fundamental relationship between opponent-shaping dynamics and advantage multiplications. Theorem 2 proves that LOQA’s opponent shaping term has the same form as that of Advantage Alignment, differing only by a scalar term.

###### Theorem 1 (LOLA as an advantage alignment estimator) .

Given a two-player game where players 1 and 2 have respective policies $\pi^{1}(a|s)$ and $\pi^{2}(b|s)$, where each policy is parametrised such that the set of gradients $\nabla_{\theta_{2}}\log\pi^{2}(a|s)$ for all pairs $(a,s)$ form an orthonormal basis, the LOLA update for the first player correspond to a reinforce update with the following opponent shaping term

$$ $\beta\cdot\mathbb{E}_{\tau\sim\Pr_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{ \infty}\gamma^{t}\left(\sum_{k=t}^{\infty}d_{\gamma,{k-t}}\gamma^{k-t}A^{1}_{k }A^{2}_{k-t}\right)\nabla_{\theta^{1}}\log\pi^{1}(a_{t}|s_{t})\right],$ (11) $$

where $A^{i}_{k}:=A^{i}(s_{k},a_{k},b_{k})$ and $d_{\gamma,k}$ is the occupancy measure of the tuple $(a_{k},b_{k},s_{k})$ and $\beta$ is the step size of the naive learner. See appendix A.2 for a proof.

###### Theorem 2 (LOQA as an advantage alignment estimator) .

Under Assumption 2,
the opponent shaping term in LOQA is equivalent to the opponent shaping term in Equation 8 up to $(1-\tilde{\pi}^{2}(b_{k}|s_{k}))$

$$ $\beta\cdot\mathbb{E}_{\tau\sim\Pr_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{ \infty}\gamma^{t+1}\left(\sum_{k<t}^{\infty}\gamma^{t-k}(1-\tilde{\pi}^{2}(b_{ k}|s_{k}))A^{1}_{k}\right)A^{2}_{t}\nabla_{\theta^{1}}\log\pi^{1}(a_{t}|s_{t}) \right],$ (12) $$

$\tilde{\pi}^{2}(b_{t}|s_{t})$ approximates the opponent policy as defined in LOQA. For a proof see appendix A.5.

Having established the connection between existing opponent shaping algorithms and Advantage Alignment, we now focus on analyzing the theoretical properties of Advantage Alignment itself. We investigate the impact of the Advantage Alignment term on Nash equilibria. Theorem 3 demonstrates that Advantage Alignment preserves Nash equilibria, ensuring that if agents are already playing equilibrium strategies, the Advantage Alignment updates will not cause the policy gradient to deviate from them locally.

###### Theorem 3 (Advantage Alignment preserves Nash equilibria) .

Advantage Alignment preserves Nash equilibria. That is, if a joint policy $(\pi_{1}^{*},\pi_{2}^{*})$ constitutes a Nash equilibrium, then applying the Advantage Alignment formula will not change the policy, as the gradient contribution of the advantage alignment term is zero. The proof can be found in Appendix A.8.

###### Theorem 1 (LOLA as an advantage alignment estimator) .

###### Theorem 2 (LOQA as an advantage alignment estimator) .

###### Theorem 3 (Advantage Alignment preserves Nash equilibria) .

### 5 Experiments

#### 5.1 Iterated Prisoner’s Dilemma

We consider the *full history* version of IPD, where a gated recurrent unit (GRU) policy conditions on the full trajectory of observations before sampling an action. In this experiment we follow the architecture used in POLA (Zhao et al.,, ) (for details see appendix B.1). We also consider trajectories of length 16 with a discount factor, $\gamma$, of 0.9. As shown in figure 1(b), Advantage Alignment agents consistently achieve a policy that resembles *tit-for-tat* (Rapoport and Chammah,, ) empirically. Tit-for-tat consists of cooperating on the first move and then mimicking the opponent’s previous move in subsequent rounds.

#### 5.2 Coin Game

The Coin Game is a 3x3 grid world environment where two agents, red and blue, take turns collecting coins. During each turn, a coin of either red or blue color spawns at a random location on the grid. Agents receive a reward of +1 for collecting any coin but incur a penalty of -3 if the opponent collects a coin of their color. A Pareto-optimal strategy in the Coin Game is for each agent to collect only the coins matching their color, as this approach maximizes the total returns for both agents. Figure 2 demonstrates that Advantage Alignment agents perform similarly to LOQA agents when evaluated against a league of different policies: Advantage Alignment agents cooperate with themselves, cooperate with Always Cooperate (AC) and are not exploited by Always Defect (AD).

Figure: Figure 2: League Results of the Advantage Alignment agents in Coin Game: LOQA, POLA, MFOS, Always Cooperate (AC), Always Defect (AD), Random and Advantage Alignment (AdAlign). Each number in the plot is computed by running 10 random seeds of each agent head to head with 10 seeds of another for 50 episodes of length 16 and averaging the rewards.
Refer to caption: x2.png

#### 5.3 Negotiation Game

In the original Negotiation Game, two agents bargain over $n$ types of items over multiple rounds. In each round, both the quantity of items and the value each agent places on them are randomly set, but the agents only know their own values. They take turns proposing how to divide the items over a random number of turns. Agents can end the negotiation by agreeing to a proposal, and rewards are based on how well the agreement matches their private values. If they don’t reach an agreement by the final turn, neither gets a reward.

We modify the game first by making the values public, otherwise Advantage Alignment would have an unfair edge over PPO agents by using the opponent’s value function. Secondly, we do one-shot, simultaneous negotiations instead of negotiation rounds lasting multiple iterations. Third, we modify the reward function so that every negotiation yields a reward. For a given item with agent value $v_{a}$, the reward of the agent $r_{a}$ depends on the proposal of the agent $p_{a}$ and the proposal of the opponent $p_{o}$ where $p_{a},p_{o}\in[0,5]$:

$$ $r_{a}=\frac{p_{a}\cdot v_{a}}{\max(5,p_{a}+p_{o})}.$ $$

Note that the max operation at the denominator serves to break the invariance of the game dynamics to the scale of proposals. For example, without the max operation, there would be no difference between $p_{a}=1,p_{o}=1$ and $p_{a}=5,p_{o}=5$. The social dilemma in this version of the negotiation game arises because both agents are incentivized to take as many items as possible, but by doing so, they end up with a lower return compared to the outcome they would achieve if they split the items based on their individual utilities. A Pareto-optimal strategy entails allowing the agent to take all the items that are more valuable to them, and similarly for their opponent (this constitutes the Always Cooperate (AC) strategy in Figure 3(a)). We experiment with a high-contrast setting where the utilities of objects for the agents are orthogonal to each other: There are two possible combinations of values in this setup: $v_{a}=5,v_{b}=1$ or $v_{a}=1,v_{b}=5$.

As shown in Figure 3(a), PPO agents do not learn to solve the social dilemma. They learn the naive policy of bidding high for every item which means they get a low return against themselves. PPO agents trained with shared rewards get a high return against themselves, only to be exploited by PPO agents. They do not learn to abandon cooperation and retaliate after they are defected against. Advantage Alignment agents solves the social dilemma. They cooperate with themselves while remaining non-exploitable against Always Defect.

Figure: (a)
Refer to caption: x3.png

#### 5.4 Melting Pot’s Commons Harvest Open

Figure: Figure 4: Comparison of different reinforcement learning algorithms in Melting Pot’s 2.0. Commons Harvest Open. The score is the focal return per capita, min-max normalized between a random agent and an exploiter baseline (ACB agent with an LSTM policy/value network) trained for $10^{9}$ steps. Following the protocol of the Melting Pot contest, we select the best agent out of 10 seeds and evaluate it 100 times.
Refer to caption: x5.png

In Commons Harvest Open (Agapiou et al.,, ), a group of 7 agents interact in a environment in which there is 6 bushes with different amounts of apples. Agents receive a reward of 1 for any apple consumed. Consumed apples regrow with a probability dependent on the number of apples in their $L_{2}$ neighborhood; specifically, if there are no apples nearby, consumed apples do not regrow. This mechanism creates a tension between agents: they must exercise restraint to prevent extinction while also feeling compelled to consume quickly out of fear that others may over-harvest.

There are a number of complications that make the Melting Pot environments particularly challenging. First, the environments are partially-observable: agents can only see a local window around themselves. Second, the partial observations are in the form of high-dimensional raw pixel data. Third, these environments often involve multiple agents—seven in the case of Commons Harvest Open—which increases the complexity of interactions and coordination. Therefore, agents need to remember past interactions with other agents to infer their motives and policies. All these factors, combined with the inherent social dilemma reward structure of the game, make finding policies that are optimal with respect to social and individual objectives a non-trivial task.

We train a GTrXL transformer (Parisotto et al.,, ) for 34k steps, with context length of 30, and compare the normalized focal return per capita of our agents against the baselines in Melting Pot 2.0: Advantage-critic baseline (acb) (Espeholt et al.,, ), V-MPO (vmpo) (Song et al.,, ), options as responses (opre) (Vezhnevets et al.,, ), and prosocial versions of opre (opre_p) and acb (acb_p) that encourage cooperation. We also compare to our own implementations of PPO (ppo) and PPO with summed rewards (ppo_p). Figure 4 shows that our best advantage alignment agent achieves on average $1.63$ normalized per capita focal return in the Commons Harvest evaluation scenarios, significantly outperforming all baselines (see Appendix B.4). Figure 5, qualitatively shows the reason why Proximal Advantage Alignment outperforms PPO and PPO with summed rewards on one of the evaluation scenarios.

Figure: Figure 5: Frames of evaluation trajectories for different algorithms. Qualitatively, we demonstrate that Proximal Advantage Alignment (adalign) also outperforms naive PPO (ppo) and PPO with summed rewards. The evaluation trajectories show how adalign agents are able to maintain a bigger number of apple bushes from extinction (2) for a longer time that either ppo or ppo_p. Note that in the Commons Harvest evaluation two exploiter agents, green and yellow, play against a focal population of 5 copies of the evaluated algorithm.
Refer to caption: x6.png

### 6 Related Work

The Iterated Prisoner’s Dilemma (IPD) was introduced by Rapoport and Chammah, (). *Tit-for-tat* was discovered as a robust strategy against a population of opponents in IPD by Axelrod, (), who organized multiple IPD tournaments. It was discovered only recently that IPD contains strategies that extort rational opponents into exploitable cooperation (Press and Dyson,, ). Sandholm and Crites, () were the first to demonstrate that two Q-learning agents playing IPD converge to mutual defection, which is suboptimal. Later, demonstrated that the same is true for policy gradient methods. Bertrand et al., () were able to show that with optimistic initialization and *self-play*, Q-learning agents find a Pavlov strategy in IPD.

Opponent shaping was first introduced in LOLA , as a method for controlling the learning dynamics of opponents in a game. A LOLA agent assumes the opponents are naive learners and differentiates through a one step look-ahead optimization update of the opponent. More formally, LOLA maximizes $V^{1}(\theta^{1},\theta^{2}+\Delta\theta^{2})$ where $\Delta\theta^{2}$ is a naive learning step in the direction that maximizes the opponent’s value function $V^{2}(\theta^{1},\theta^{2})$. Variations of LOLA have been introduced to have formal stability guarantees (Letcher et al.,, ), learn consistent update functions assuming mutual opponent shaping (Willi et al.,, ) and be invariant to policy parameterization (Zhao et al.,, ). More recent work performs opponent shaping by having an agent play against a best response approximation of their policy (). LOQA (), on which this work is based, performs opponent shaping by controlling the Q-values of the opponent using REINFORCE (Williams,, ) estimators.

Another approach to finding socially beneficial equilibria in general sum games relies on modeling the problem as a meta-game, where meta-rewards correspond to the returns on the inner game, meta-states correspond to joint policies of the players, and the meta-actions are updates to these policies. Al-Shedivat et al., () introduce a continuous adaptation framework for multi-task learning that uses meta-learning to deal with non-stationary environments. MFOS (Lu et al.,, ) uses model-free optimization methods like PPO and genetic algorithms to optimize the meta-value of the meta-game. More recently Meta-Value Learning (Cooijmans et al.,, ) parameterizes the meta-value as a neural network and applies Q-learning to capture the future effects of changes to the inner policies. Shaper (Khan et al.,, ), scales opponent shaping to high-dimensional general-sum games with temporally extended actions and long time horizons. It does so, by simplifying MFOS and effectively capturing both intra-episode and inter-episode information.

Melting Pot 2.0 (Agapiou et al.,, ) introduces a comprehensive suite of multi-agent reinforcement learning environments that focus on social interactions and coordination challenges, providing a valuable benchmark for evaluating the scalability and effectiveness of reinforcement learning algorithms in complex, cooperative-competitive settings. The Negotiation Game, introduced by DeVault et al., (); Lewis et al., () and subsequently refined by Cao et al., (), has proven to be a significant benchmark for studying general-sum games. It integrates elements of strategy and social dilemmas, necessitating that agents balance cooperation and competition to optimize their outcomes. Noukhovitch et al., () analyze this complex benchmark, underscoring its importance in the field. Future investigations will turn towards an even more sophisticated simulation proposed by Zhang et al., (), which involves negotiations among countries and regions with diverse resource distributions and preferences in addressing climate change.

### 7 Conclusion

In this work, we introduced Advantage Alignment, a novel family of algorithms designed to address the fundamental challenge of achieving self-interested cooperation in multi-agent reinforcement learning, particularly in social dilemmas. By deriving our algorithms from first principles, we distilled opponent shaping to its core components, providing a simple yet powerful mechanism to align agents’ advantages and foster mutually beneficial behaviors. Our approach unifies and generalizes existing opponent shaping methods, such as LOLA and LOQA, demonstrating that they implicitly perform Advantage Alignment through different mechanisms. This unification not only simplifies the mathematical formulation of opponent shaping but also reduces computational complexity, enabling more efficient and scalable algorithms.

Our experiments across a range of social dilemmas, including the Iterated Prisoner’s Dilemma, Coin Game, and a continuous action variant of the Negotiation Game, demonstrate that Advantage Alignment consistently achieves state-of-the-art cooperation and robustness against exploitation. Notably, we extended our methods to complex, large-scale, general-sum environments like Melting Pot’s Commons Harvest Open, addressing challenges that arise from partial observability, high-dimensional observations, and multi-agent interactions. In these settings, Advantage Alignment agents learned sophisticated strategies that balance individual and collective interests, showcasing the potential of our algorithms to scale to real-world applications.

The significance of our work lies in providing a principled, efficient, and scalable solution to the longstanding problem of self-interested cooperation in general-sum games. By enabling agents to autonomously align their interests with one another, Advantage Alignment paves the way for more harmonious and socially beneficial interactions in artificial intelligence systems integrated into human decision-making processes. This has profound implications for the development of AI agents in diverse domains, from autonomous vehicles navigating shared environments to AI assistants collaborating with humans and other agents.

## 

## Appendix

### Appendix A Mathematical Derivations

#### A.1 Deriving the Advantage Alignment Formula

In this section we derive the Advantage Alignment formula in equation equation 8 from the opponent shaping expression in equation equation 6 and assumption 2. Recall assumption 2:

$$ $\pi^{i}(a|s)\propto\exp{\beta\mathbb{E}_{b\sim\pi^{3-i}(\cdot|s)}[Q^{i}(s,a,b)]}$ $$

Note that if $i=1,3-i=2$ and if $i=2,3-i=1$.
Recall the opponent shaping policy gradient expression:

$$ $\nabla_{\theta_{1}}V^{1}(\mu)=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi ^{2}}}\left[\sum_{t=0}^{\infty}\gamma^{t}A^{1}(s_{t},a_{t},b_{t})\left( \underbrace{\nabla_{\theta_{1}}\log\pi^{1}(a_{t}|s_{t})}_{\text{(A)}}+ \underbrace{\nabla_{\theta_{1}}\log\pi^{2}(b_{t}|s_{t})}_{\text{(B)}}\right)\right]$ $$

We expand the term (B) above splitting the expectation, by assumption 2, we can write:

$$ $\displaystyle\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_ {t=0}^{\infty}\gamma^{t}A^{1}(s_{t},a_{t},b_{t})\nabla_{\theta_{1}}\log\pi^{2} (b_{t}|s_{t})\right]$ $\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum _{t=0}^{\infty}\gamma^{t}A^{1}(s_{t},a_{t},b_{t})\nabla_{\theta_{1}}\log\exp \mathbb{E}_{a\sim\pi^{1}(|s_{t})}[Q^{2}(s_{t},a,b_{t})]\right]$ $\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum _{t=0}^{\infty}\gamma^{t}A^{1}(s_{t},a_{t},b_{t})\nabla_{\theta_{1}}\mathbb{E} _{a\sim\pi^{1}(|s_{t})}[Q^{2}(s_{t},a,b_{t})]\right].$ $$

where is the second line we used the fact that the expected advantage is zero.
For convenience of notation we define:

$$ $r^{i}_{t}:=r^{i}(s_{t},a_{t},b_{t}),\;A^{i}_{t}:=A^{i}(s_{t},a_{t},b_{t})$ $$

These are the reward and advantage of agent $i$ at time step $t$ after taking action $a_{t}$ and opponent taking action $b_{t}$. From the Bellman equation equation 2 we expand as follows:

$$ $\displaystyle\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_ {t=0}^{\infty}\gamma^{t}A^{1}(s_{t},a_{t},b_{t})\nabla_{\theta^{1}}\mathbb{E}_ {a\sim\pi^{1}(|s_{t})}[Q^{2}(s_{t},a,b_{t})]\right]$ (13) $\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum _{t=0}^{\infty}\gamma^{t}A^{1}_{t}\nabla_{\theta^{1}}\left(\mathbb{E}_{s^{ \prime}}\left[r^{2}_{t}+\gamma\cdot V^{2}(s^{\prime})\biggr{|}s_{t},b_{t} \right]\right)\right]$ (14) $\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum _{t=0}^{\infty}\gamma^{t+1}A^{1}_{t}\nabla_{\theta^{1}}\mathbb{E}_{s^{\prime}} \left[V^{2}(s^{\prime})\biggr{|}s_{t},b_{t}\right]\right]$ (15) $\displaystyle=\mathbb{E}\underset{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}{} \left[\sum_{t=0}^{\infty}\gamma^{t+1}A^{1}_{t}\mathbb{E}_{\tau^{\prime}\sim \text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{k=0}^{\infty}\gamma^{k}A^{2}_{k} \nabla_{\theta^{1}}\text{log }\pi^{1}(a_{k}^{\prime}|s_{k}^{\prime})\biggr{|}s _{t},b_{t}\right]\right]$ (16) $\displaystyle=\mathbb{E}\underset{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}{} \left[\sum_{t=0}^{\infty}\mathbb{E}_{\tau^{\prime}\sim\text{Pr}_{\mu}^{\pi^{1} ,\pi^{2}}}\left[\sum_{k=0}^{\infty}\gamma^{k+t+1}A^{1}_{t}A^{2}_{k}\nabla_{ \theta^{1}}\text{log }\pi^{1}(a_{k}^{\prime}|s_{k}^{\prime})\biggr{|}s_{t},b_{ t}\right]\right]$ (17) $\displaystyle=\mathbb{E}\underset{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}{} \left[\mathbb{E}_{\tau^{\prime}\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[ \sum_{t=0}^{\infty}\sum_{k=t+1}^{\infty}\gamma^{t+k+1}A^{1}_{t}A^{2}_{k}\nabla _{\theta^{1}}\text{log }\pi^{1}(a_{k}^{\prime}|s_{k}^{\prime})\biggr{|}s_{t},b _{t}\right]\right]$ (18) $\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum _{t=0}^{\infty}\sum_{k=t+1}^{\infty}\gamma^{t+k+1}A^{1}_{t}A^{2}_{k}\nabla_{ \theta^{1}}\text{log }\pi^{1}(a_{k}|s_{k})\right].$ (19) $$

We use the Bellman equation in line (14). In line (17), we use the fact that $\gamma^{t}A^{1}(s_{t},a_{t},b_{t})$ is measurable w.r.t. the natural filtration of the process up to time $t$, $\mathcal{F}_{t}$, and the independence of the two terms conditioned on $\mathcal{F}_{t}$ by the Markov property. In line (18) we use linearity of expectation. In line (19) we use the rule of the iterated expectations. Reorganizing the summations in causal form we get the final form:

$$ $\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{\infty }\gamma^{t+1}\left(\sum_{k<t}\gamma^{t-k}A^{1}(s_{k},a_{k},b_{k})\right)A^{2}( s_{t},a_{t},b_{t})\nabla_{\theta^{1}}\text{log }\pi^{1}(a_{t}|s_{t})\right].$ ( 8 ) $$

#### A.2 Proof of Theorem 1

###### Lemma 1 (Policy changes under gradient ascent) .

Given a policy $\pi_{\theta}(a|s)$ parametrised such that the set of gradients $\nabla_{\theta}\log\pi_{\theta}(a|s)$ for all pairs $(a,s)$ form an orthonormal basis, and a value function $V(\theta)$, the following holds:

$$ $\displaystyle\frac{d}{d\alpha}\pi_{\theta+\alpha\nabla_{\theta}V}(a|s)=\nabla_ {\theta}V\cdot\nabla_{\theta}\pi_{\theta}(a|s)$ $\displaystyle=d_{\gamma}(s)\pi_{\theta}(a|s)^{2}A(a|s)$ (20) $\displaystyle d_{\gamma}(s)$ $\displaystyle\equiv\sum_{t=0}^{\infty}\gamma^{t}Pr(s_{t}=s)$ (21) $\displaystyle A(a|s)$ $\displaystyle\equiv Q(a|s)-V(s)$ (22) $$

###### Proof.

The policy gradient theorem gives us:

$$ $\displaystyle\nabla_{\theta}V(\theta)$ $\displaystyle=\mathbb{E}_{\tau\sim\pi}\sum_{t=0}^{\infty}\gamma^{t}A(a_{t}|s_{ t})\nabla_{\theta}\log\pi_{\theta}(a_{t}|s_{t})$ (23) $\displaystyle=\sum_{(s,a)}d_{\gamma}(s)\pi_{\theta}(a|s)A(a|s)\nabla_{\theta} \log\pi_{\theta}(a|s)$ (24) $$

Taking the dot product of this expression with $\nabla_{\theta}\pi_{\theta}(a^{\prime}|s^{\prime})=\pi_{\theta}(a^{\prime}|s^{
\prime})\nabla_{\theta}\log\pi_{\theta}(a^{\prime}|s^{\prime})$ and invoking the assumed orthonormality of gradients:

$$ $\displaystyle\nabla_{\theta}\pi_{\theta}(a^{\prime}|s^{\prime})\cdot\nabla_{ \theta}V(\theta)$ (25) $\displaystyle=\sum_{(s,a)}d_{\gamma}(s)\pi_{\theta}(a|s)\pi_{\theta}(a^{\prime }|s^{\prime})A(a|s)\bigg{(}\nabla_{\theta}\log\pi_{\theta}(a|s)\cdot\nabla_{ \theta}\log\pi_{\theta}(a^{\prime}|s^{\prime})\bigg{)}$ (26) $\displaystyle=d_{\gamma}(s^{\prime})\pi_{\theta}(a^{\prime}|s^{\prime})^{2}A(a ^{\prime}|s^{\prime})$ (27) $$

∎

Theorem 1. (LOLA policy gradient)
Given a two-player game where players 1 and 2 have respective policies $\pi^{1}(a|s)$ and $\pi^{2}(b|s)$, where each policy is parametrised such that the set of gradients $\nabla_{\theta_{2}}\log\pi^{2}(a|s)$ for all pairs $(a,s)$ form an orthonormal basis, the LOLA update for the first player correspond to a reinforce update with an advantage

$$ $A_{LOLA}^{*}(s_{t},a_{t},b_{t})=A^{1}(s_{t},a_{t},b_{t})+\beta\cdot\sum_{k=t}^ {\infty}d_{\gamma,{k-t}}\gamma^{k-t}A^{1}_{k}A^{2}_{k-t}.$ ( 11 ) $$

where $A^{i}_{k}:=A^{i}(s_{k},a_{k},b_{k})$ and $d_{\gamma,k}$ is the occupancy measure of the tuple $(a_{k},b_{k},s_{k})$

###### Proof.

LOLA () optimizes the return of the agent under an imagined optimization step of the opponent (assuming the opponent is a naive learning algorithm). Under their notation, a LOLA agent optimizes $V^{1}(\theta_{1},\theta_{2}+\Delta\theta_{2})$ where $\Delta\theta_{2}$ is a gradient ascent step on the parameters of the opponent $\theta_{2}$. Note that along this proof because we consider the method proposed by () we use their way to compute gradients. Particularly, one does not use Assumption 2, and consequently assume that $\nabla_{\theta_{1}}\log\pi_{\theta_{2}}=0$ (and respectively $\nabla_{\theta_{2}}\log\pi_{\theta_{1}}=0$.)

Since computing this value function explicitly is difficult, LOLA uses the first-order Taylor expansion surrogate objective:

$$ $V^{1}(\theta^{1},\theta^{2}+\Delta\theta_{2})\approx V^{1}(\theta_{1},\theta_{ 2})+\left(\Delta\theta_{2}\right)^{T}\nabla_{\theta_{2}}V^{1}(\theta_{1}, \theta_{2})$ (28) $$

The gradient of the expression above w.r.t. the parameters $\theta_{1}$ of the agent is given by

$$ $\nabla_{\theta_{1}}V^{1}(\theta^{1},\theta^{2}+\alpha\nabla_{\theta_{2}}V^{2}( \theta_{1},\theta_{2}))=\nabla_{\theta_{1}}V^{1}(\theta_{1},\theta_{2})+\beta \left(\nabla_{\theta_{1}}\nabla_{\theta_{2}}V^{1}(\theta^{1},\theta^{2})\right )\nabla_{\theta_{2}}V^{2}(\theta_{1},\theta_{2}).$ (29) $$

The first-order terms above is computed using the Advantage form of the REINFORCE estimator, which is given by equation equation 3. derive the following REINFORCE estimator for the second-order term:

$$ $\displaystyle\nabla_{\theta_{1}}\nabla_{\theta_{2}}V^{1}(\theta^{1},\theta^{2})$ (30) $\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum _{t=0}^{\infty}\gamma^{t}r^{1}_{t}\left(\sum_{k=0}^{t}\nabla_{\theta_{1}}\log \pi^{1}(a_{t}|s_{t})\right)\left(\sum_{k=0}^{t}\nabla_{\theta_{2}}\log\pi^{2}( b_{t}|s_{t})\right)^{\top}\right]$ (31) $$

Now, we use the following fact

$$ $\sum_{t=0}^{\infty}c_{t}(\sum_{k=0}^{t}a_{k})(\sum_{l=0}^{t}b_{l})=\sum_{t=0}^ {\infty}c_{t}\sum_{S=0}^{t}\sum_{k=0}^{S}a_{k}b_{S-k}=\sum_{S=0}^{\infty}\sum_ {t=S}^{\infty}\sum_{k=0}^{S}a_{k}b_{S-k}c_{t}=\sum_{S=0}^{\infty}\sum_{k=0}^{S }a_{k}b_{S-k}\sum_{t=S}^{\infty}c_{t}$ $$

to expand the second order term beginning from equation 29, to bring out the advantage $A_{t}^{1}$:

$$ $\displaystyle\nabla_{\theta_{1}}\nabla_{\theta_{2}}V^{1}(\theta^{1},\theta^{2})$ (32) $\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum _{t=0}^{\infty}\gamma^{t}r^{1}_{t}\left(\sum_{k=0}^{t}\nabla_{\theta_{1}}\log \pi^{1}(a_{t}|s_{t})\right)\left(\sum_{k=0}^{t}\nabla_{\theta_{2}}\log\pi^{2}( b_{t}|s_{t})\right)^{\top}\right]$ (33) $\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum _{S=0}^{\infty}\left(\sum_{k=0}^{S}\nabla_{\theta_{1}}\log\pi^{1}(a_{k}|s_{k}) \nabla_{\theta_{2}}\log\pi^{2}(b_{S-k}|s_{S-k})^{\top}\right)\sum_{t=S}^{ \infty}\gamma^{t}r^{1}_{t}\right]$ (34) $\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum _{t=0}^{\infty}\left(\sum_{k=0}^{t}\nabla_{\theta_{1}}\log\pi^{1}(a_{k}|s_{k}) \nabla_{\theta_{2}}\log\pi^{2}(b_{t-k}|s_{t-k})^{\top}\right)\sum_{l=t}^{ \infty}\gamma^{l}r^{1}_{l}\right]$ (35) $\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum _{t=0}^{\infty}\left(\sum_{k=0}^{t}\nabla_{\theta_{1}}\log\pi^{1}(a_{k}|s_{k}) \nabla_{\theta_{2}}\log\pi^{2}(b_{t-k}|s_{t-k})^{\top}\right)\gamma^{t}\mathbb {E}\left[\sum_{l=0}^{\infty}\gamma^{l}r^{1}_{l+t}\right]\right]$ (36) $\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum _{t=0}^{\infty}\left(\sum_{k=0}^{t}\nabla_{\theta_{1}}\log\pi^{1}(a_{k}|s_{k}) \nabla_{\theta_{2}}\log\pi^{2}(b_{t-k}|s_{t-k})^{\top}\right)\gamma^{t}Q^{1}(s _{t},a_{t},b_{t})\right]$ (37) $\displaystyle=\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum _{t=0}^{\infty}\left(\sum_{k=0}^{t}\nabla_{\theta_{1}}\log\pi^{1}(a_{k}|s_{k}) \nabla_{\theta_{2}}\log\pi^{2}(b_{t-k}|s_{t-k})^{\top}\right)\gamma^{t}A^{1}_{ t}\right],$ (38) $$

where we reorder the terms of the summation to sum over future rewards instead of past gradient terms in line 34, we use the law of iterated expectation in line 36 and a baseline subtraction in line 38.

Per Equation equation 29, we multiply this Hessian with the gradient of the value function

$$ $\displaystyle\nabla_{\theta_{2}}V^{2}(\theta_{1},\theta_{2})$ $\displaystyle=\mathbb{E}_{\tau\sim\pi}\sum_{t=0}^{\infty}\gamma^{t}A^{2}(a_{t} ,b_{t}|s_{t})\nabla_{\theta_{2}}\log\pi^{2}(b_{t}|s_{t})$ (39) $\displaystyle=\sum_{(s,a,b)}d_{\gamma}(a,b,s)A^{2}(a,b|s)\nabla_{\theta_{2}} \log\pi^{2}(b|s)$ (40) $$

where where $d_{\gamma}(a,b,s)$ is the occupancy measure of the state actions tuple $(a,b,s)$, and use the assumption that the gradients $(\nabla_{\theta_{2}}\log\pi^{2}(a|s))_{(a,s)}$ form an orthonormal basis to obtain

$$ $\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{\infty }\left(\sum_{k=0}^{t}\nabla_{\theta_{1}}\log\pi^{1}(a_{k}|s_{k})d_{\gamma}(a_{ t-k},b_{t-k},s_{t-k})A^{2}_{t-k}\right)\gamma^{t}A^{1}_{t}\right].$ $$

To completes the proof, we finally need to switch the summations to get

$$ $\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{\infty }\left(\sum_{k=t}^{\infty}\gamma^{k}A^{1}_{k}d_{\gamma}(a_{k-t},b_{k-t},s_{k-t })A^{2}_{k-t}\right)\nabla_{\theta_{1}}\log\pi^{1}(a_{t}|s_{t})\right].$ $$

∎

###### Lemma 1 (Policy changes under gradient ascent) .

###### Proof.

###### Proof.

#### A.3 Gradient of LOQA

Recall the opponent policy approximation used in LOQA, which takes a softmax over the Q-values of the opponent. We assume exact estimates of these Q-values:

$$ $\hat{\pi}^{2}(b_{t}|s_{t}):=\frac{\exp Q^{2}(s_{t},a_{t},b_{t})}{\sum_{b}\exp Q ^{2}(s_{t},a_{t},b)}$ ( 4 ) $$

Note that $\hat{\pi}^{2}(b_{t}|s_{t})$ is differentiable w.r.t. the parameters $\theta_{1}$ of the policy of the agent because the Q-values depend on $\pi_{1}$. Therefore, we can use the policy gradient theorem (see ) to differentiate the value function of the opponent w.r.t. the parameters of the agent. For convenience of notation we define:

$$ $Q^{i}_{t}(b):=Q^{i}(s_{t},a_{t},b)$ $$

Computing the gradient of the approximated opponent’s policy we get:

$$ $\displaystyle\nabla_{\theta_{1}}\hat{\pi}^{2}(b_{t}|s_{t})$ $\displaystyle=\nabla_{\theta_{1}}\left(\frac{\exp Q^{2}(s_{t},a_{t},b_{t})}{ \sum_{b}\exp Q^{2}(s_{t},a_{t},b)}\right)$ (41) $\displaystyle=\frac{\nabla_{\theta_{1}}\exp Q^{2}_{t}(b_{t})}{\sum_{b}\exp Q^{ 2}_{t}(b)}-\frac{\exp Q^{2}_{t}(b_{t})\nabla_{\theta_{1}}\sum_{b}\exp Q^{2}_{t }(b)}{\left(\sum_{b}\exp Q^{2}_{t}(b)\right)^{2}}$ (42) $\displaystyle=\frac{\exp Q^{2}_{t}(b_{t})\nabla_{\theta_{1}}Q^{2}_{t}(b_{t})}{ \sum_{b}\exp Q^{2}_{t}(b)}-\frac{\exp Q^{2}_{t}(b_{t})\sum_{b}\exp Q^{2}_{t}(b )\nabla_{\theta_{1}}Q^{2}_{t}(b)}{\left(\sum_{b}\exp Q^{2}_{t}(b)\right)^{2}}$ (43) $\displaystyle=\frac{\exp Q^{2}_{t}(b_{t})}{\sum_{b}\exp Q^{2}_{t}(b)}\left( \nabla_{\theta_{1}}Q^{2}_{t}(b_{t})-\sum_{b}\frac{\exp Q^{2}_{t}(b)\nabla_{ \theta_{1}}Q^{2}_{t}(b)}{\sum_{b}\exp Q^{2}_{t}(b)}\right)$ (44) $\displaystyle=\hat{\pi}^{2}(b_{t}|s_{t})\left(\nabla_{\theta_{1}}Q^{2}_{t}(b_{ t})-\sum_{b}\hat{\pi}^{2}(b|s_{t})\nabla_{\theta_{1}}Q^{2}_{t}(b)\right),$ (45) $$

where we used the quotient rule in line (42) and equation equation 4 in line(45).
By the chain rule, the gradient of the log probability is:

$$ $\nabla_{\theta_{1}}\log\hat{\pi}^{2}(b_{t}|s_{t})=\frac{\nabla_{\theta_{1}} \hat{\pi}^{2}(b_{t}|s_{t})}{\hat{\pi}^{2}(b_{t}|s_{t})}=\nabla_{\theta_{1}}Q^{ 2}_{t}(b_{t})-\sum_{b}\hat{\pi}^{2}(b|s_{t})\nabla_{\theta_{1}}Q^{2}_{t}(b).$ $$

This concludes the derivation.

#### A.4 Gradient of LOQA in Continuous Action Spaces

We derive the gradient of the opponent’s policy $\pi^{2}(b|s)$ with respect to the agent’s parameters $\theta_{1}$, assuming a continuous action space.

The opponent’s policy is defined as:

$$ $\pi^{2}(b|s)=\frac{\exp(Q^{2}(s,b))}{\int_{\mathcal{A}}\exp(Q^{2}(s,b^{\prime} ))\,db^{\prime}},$ (46) $$

where $Q^{2}(s,b)$ is the Q-value of the opponent for action $b$, and $\mathcal{A}$ is the continuous action space.

Our goal is to compute the gradient of $\pi^{2}(b|s)$ with respect to $\theta_{1}$, the parameters of agent 1, which affect $Q^{2}(s,b)$ through interactions.

Taking the log of $\pi^{2}(b|s)$, we get:

$$ $\log\pi^{2}(b|s)=Q^{2}(s,b)-\log\left(\int_{\mathcal{A}}\exp(Q^{2}(s,b^{\prime }))\,db^{\prime}\right).$ (47) $$

The gradient of $\log\pi^{2}(b|s)$ with respect to $\theta_{1}$ is:

$$ $\nabla_{\theta_{1}}\log\pi^{2}(b|s)=\nabla_{\theta_{1}}Q^{2}(s,b)-\nabla_{ \theta_{1}}\log\left(\int_{\mathcal{A}}\exp(Q^{2}(s,b^{\prime}))\,db^{\prime} \right).$ (48) $$

Next, we compute the gradient of the log partition function $Z(s)=\int_{\mathcal{A}}\exp(Q^{2}(s,b^{\prime}))\,db^{\prime}$:

$$ $\nabla_{\theta_{1}}\log Z(s)=\frac{\nabla_{\theta_{1}}Z(s)}{Z(s)}=\frac{1}{ \int_{\mathcal{A}}\exp(Q^{2}(s,b^{\prime}))\,db^{\prime}}\int_{\mathcal{A}} \exp(Q^{2}(s,b^{\prime}))\nabla_{\theta_{1}}Q^{2}(s,b^{\prime})\,db^{\prime},$ (49) $$

which simplifies to:

$$ $\nabla_{\theta_{1}}\log Z(s)=\int_{\mathcal{A}}\pi^{2}(b^{\prime}|s)\nabla_{ \theta_{1}}Q^{2}(s,b^{\prime})\,db^{\prime}.$ (50) $$

Now, applying the chain rule to compute the gradient of $\pi^{2}(b|s)$, we get:

$$ $\nabla_{\theta_{1}}\pi^{2}(b|s)=\pi^{2}(b|s)\left(\nabla_{\theta_{1}}Q^{2}(s,b )-\int_{\mathcal{A}}\pi^{2}(b^{\prime}|s)\nabla_{\theta_{1}}Q^{2}(s,b^{\prime} )\,db^{\prime}\right).$ (51) $$

We are allowed to interchange the gradient and the integral by applying Leibniz’s rule, which holds under the following conditions:
1. $\exp(Q^{2}(s,b^{\prime}))$ and its gradient $\nabla_{\theta_{1}}\exp(Q^{2}(s,b^{\prime}))$ are continuous, as both the exponential function and the Q-value function $Q^{2}(s,b^{\prime})$ are smooth.
2. The integral $\int_{\mathcal{A}}\exp(Q^{2}(s,b^{\prime}))\,db^{\prime}$ converges due to the boundedness of $Q^{2}(s,b^{\prime})$ or a rapid decay over the action space.
3. We assume $\nabla_{\theta_{1}}Q^{2}(s,b^{\prime})$ is bounded, ensuring the interchange of the gradient and integral is well-defined. Thus, the final expression for the gradient of the opponent’s policy is:

$$ $\nabla_{\theta_{1}}\pi^{2}(b|s)=\pi^{2}(b|s)\left(\nabla_{\theta_{1}}Q^{2}(s,b )-\int_{\mathcal{A}}\pi^{2}(b^{\prime}|s)\nabla_{\theta_{1}}Q^{2}(s,b^{\prime} )\,db^{\prime}\right).$ (52) $$

The Integral above is intractable, which makes continuous action LOQA hard to scale.

#### A.5 Proof of Theorem 2

###### Proof.

In practice, LOQA deviates from the approach discussed in Appendix A.3. Specifically, it does not differentiate through all of the Q-values, but only through that of the action $b_{t}$ actually observed in the sampled trajectory:

$$ $\tilde{\pi}^{2}(b_{t}|s_{t}):=\frac{\exp Q^{2}(s_{t},a_{t},b_{t})}{\exp Q^{2}( s_{t},a_{t},b_{t})+\sum_{b\neq b_{t}}\underbrace{\exp Q^{2}(s_{t},a_{t},b)}_{ \text{non-differentiable}}}$ (53) $$

This choice is made because the trajectory provides an estimate of the Q-value of each opponent action $b_{t}$.
This estimate statistically depends on the agent’s actions $a_{<t}$ and therefore can be stochastically differentiated w.r.t $\theta_{1}$ using REINFORCE.
The other Q-values will be estimated by function approximators, which depend only implicitly on $\theta_{1}$ and cannot be differentiated.

Differentiating equation 53 leads to a simplified gradient:

$$ $\displaystyle\nabla_{\theta_{1}}\tilde{\pi}^{2}(b_{t}|s_{t})$ $\displaystyle=\nabla_{\theta_{1}}\left(\frac{\exp Q^{2}(s_{t},a_{t},b_{t})}{ \exp Q^{2}(s_{t},a_{t},b_{t})+\sum_{b\neq b_{t}}\exp Q^{2}(s_{t},a_{t},b)}\right)$ (54) $\displaystyle=\nabla_{\theta_{1}}\exp Q^{2}_{t}(b_{t})\frac{\left(\exp Q^{2}_{ t}(b_{t})+\sum_{b\neq b_{t}}\exp Q^{2}_{t}(b)\right)-\exp Q^{2}_{t}(b_{t})}{ \left(\exp Q^{2}_{t}(b_{t})+\sum_{b\neq b_{t}}\exp Q^{2}_{t}(b)\right)^{2}}$ (55) $\displaystyle=\exp Q^{2}_{t}(b_{t})\nabla_{\theta_{1}}Q^{2}_{t}(b_{t})\frac{ \sum_{b\neq b_{t}}\exp Q^{2}_{t}(b)+\exp Q^{2}_{t}(b_{t})-\exp Q^{2}_{t}(b_{t} )}{\left(\exp Q^{2}_{t}(b_{t})+\sum_{b\neq b_{t}}\exp Q^{2}_{t}(b)\right)^{2}}$ (56) $\displaystyle=\tilde{\pi}^{2}(b_{t}|s_{t})(1-\tilde{\pi}^{2}(b_{t}|s_{t})) \nabla_{\theta_{1}}Q^{2}_{t}(b_{t}).$ (57) $$

By the chain rule, the gradient of the log probability is

$$ $\nabla_{\theta_{1}}\log\tilde{\pi}^{2}(b_{t}|s_{t})=\frac{\nabla_{\theta_{1}} \tilde{\pi}^{2}(b_{t}|s_{t})}{\tilde{\pi}^{2}(b_{t}|s_{t})}=(1-\tilde{\pi}^{2} (b_{t}|s_{t}))\nabla_{\theta_{1}}Q^{2}_{t}(b_{t}).$ (58) $$

The difference between LOQA and Advantage Alignment lies in the extra scaling factor $(1-\tilde{\pi}^{2}(b_{t}|s_{t}))$ which accounts for the partition function. Plugging equation 58 into the generalized policy gradient equation equation 6 proves the theorem.
∎

###### Proof.

#### A.6 Advantage Alignment Implementation

To more clearly see the Advantage Alignment formula as an influence over each individual log probability term recall the formulation:

$$ $\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{\infty }\gamma^{t+1}\left(\sum_{k<t}\gamma^{t-k}A^{1}(s_{k},a_{k},b_{k})\right)A^{2}( s_{t},a_{t},b_{t})\nabla_{\theta^{1}}\text{log }\pi^{1}(a_{t}|s_{t})\right].$ ( 8 ) $$

The $\gamma^{t}$ term helps regularize the linear scaling of the sum of the advantages of the agent. Alternatively one could regularize using $1/(1+t)$ instead:

$$ $\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{\infty }\frac{1}{1+t}\left(\sum_{k<t}A^{1}(s_{k},a_{k},b_{k})\right)A^{2}(s_{t},a_{t} ,b_{t})\nabla_{\theta^{1}}\text{log }\pi^{1}(a_{t}|s_{t})\right].$ (59) $$

Which accounts to increasing the probability of the actions that align the sum of the past advantages of the agent up to the current time-step $t-1$ and the advantage of the opponent at the current time-step, $t$. In our implementation we use equation equation 59, as it considers more terms in the future and works better in practice.

#### A.7 Proximal Advantage Alignment

Figure: Algorithm 2 Proximal Advantage Alignment

We can combine the two policy gradient terms into a single one to come up with a proximal Advantage Alignment formulation:

$$ $\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{\infty }\gamma^{t}A^{1}_{t}\nabla_{\theta^{1}}\log\pi^{1}(a_{t}|s_{t})+\beta\gamma \sum_{t=0}^{\infty}\gamma^{t}\left(\sum_{k<t}\gamma^{t-k}A^{1}_{k}\right)A^{2} _{t}\nabla_{\theta^{1}}\log\pi^{1}(a_{t}|s_{t})\right]$ (60) $$

Where $\beta$ is the weight put into the Advantage Alignment loss (the negative inverse of the Boltzmann constant times the temperature). Then we have:

$$ $\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{\infty }\gamma^{t}\left(A^{1}_{t}+\beta\gamma\left(\sum_{k<t}\gamma^{t-k}A^{1}_{k} \right)A^{2}_{t}\right)\nabla_{\theta^{1}}\text{log }\pi^{1}(a_{t}|s_{t}) \right].$ (61) $$

This is just the normal advantage policy gradient with a modified advantage $A^{*}$:

$$ $\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\sum_{t=0}^{\infty }\gamma^{t}A^{*}_{t}\nabla_{\theta^{1}}\text{log }\pi^{1}(a_{t}|s_{t})\right], \text{ where }A^{*}_{t}=A^{1}_{t}+\beta\gamma\left(\sum_{k<t}A^{1}_{k}\right)A ^{2}_{t}.$ (62) $$

Recall the Trust Region Policy Optimization (TRPO) () objective, we want to maximize the value function while maintaining the updated policy close in policy space:

$$ $\displaystyle\max_{\theta^{1}}V^{1}(\mu)$ (63) $\displaystyle\text{s.t. }\sup_{s}\left\|\pi^{1}(\cdot|s)-\pi_{n}^{1}(\cdot|s) \right\|_{\text{tv}}\leq\delta$ $$

We can use the PPO () surrogate objective:

$$ $\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\min\left\{r_{n}( \theta_{1})A^{1}_{t},\;\text{clip}\left(r_{n}(\theta_{1});1-\epsilon,1+ \epsilon\right)A^{1}_{t}\right\}\right]$ (64) $$

Now we apply it to the Advantage Alignment formulation that uses the modified advantage on the policy gradient equation 62:

$$ $\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{\pi^{1},\pi^{2}}}\left[\min\left\{r_{n}( \theta_{1})A^{*}_{t},\;\text{clip}\left(r_{n}(\theta_{1});1-\epsilon,1+ \epsilon\right)A^{*}_{t}\right\}\right],$ ( 9 ) $$

where we denote $\pi^{1}_{n}(a_{t}|s_{t})$ to be the updated policy and $r_{n}(\theta_{1})=\pi^{1}_{n}(a_{t}|s_{t})/\pi^{1}(a_{t}|s_{t})$ is the ratio between the updated policy and the old policy. We used generalized advantage estimation (GAE) (Schulman et al.,, )
to compute the advantages in this expression. Algorithm 2 summarizes the implementation of Proximal Advantage Alignment.

#### A.8 Proof of Theorem 3

Let $\theta_{1},...,\theta_{n}$ be the parameter each agent, $\pi_{\theta_{i}}(a|s)$ be the policies represented by those parameters, and $V_{i}(\theta_{1},...,\theta_{n})$ be the value function of agent $i$ as a function of all the other agents.

###### Lemma 2 (Zero Advantages At Nash) .

For all Nash Equilibria of the game, if there exist parameters $\theta_{1}^{*},...,\theta_{n}^{*}$ such that $\pi_{\theta_{i}^{*}}=\pi_{i}^{*}$, where $\pi_{i}^{*}$ is the policy of agent $i$ at the Nash, then for all action-state pairs with non-zero probability under the Nash policies, we have $A_{i}(a|s)=0$.

###### Proof.

By the Bellman Optimality Equation, at an optimal policy the value of agent $i$ becomes $V_{i}^{*}(s)=\arg\max_{a}Q^{*}(a,s)$, hence all actions with non-zero probability under $\pi_{i}^{*}$ have the same $Q^{*}(a,s)$, and since $A(a,s)\equiv Q(a,s)-V(s)$, the advantage will vanish.
∎

We now use lemma 2 to prove that the Advantage Alignment term is zero at a Nash equilibrium.

###### Proof.

Under Advantage Alignment, the updates we take can be represented by

$$ $\displaystyle\theta^{\prime}_{i}$ $\displaystyle\leftarrow\theta_{i}+\alpha\cdot\mathbb{E}_{\tau\sim\text{Pr}_{ \mu}^{\pi^{i},\pi^{-i}}}\left[\sum_{t=0}^{\infty}B^{i}_{t}\>\nabla_{\theta_{i} }\log\pi_{\theta_{i}}(a_{t}|s_{t})\right]$ (65) $\displaystyle B^{i}_{t}$ $\displaystyle\equiv A^{i}_{t}+\beta\cdot\mathbb{E}_{\tau\sim\text{Pr}_{\mu}^{ \pi^{i},\pi^{-i}}}\left[\sum_{j\neq i}\left(\sum_{k<t}\gamma^{t-k}A^{i}_{k} \right)A^{j}_{t}\right]$ (66) $$

But by lemma 2, $A^{j}(b_{t}|s_{t})=0$ for all actions at a Nash, hence the second term vanishes, as does the first term for the same reason.
∎

###### Lemma 2 (Zero Advantages At Nash) .

###### Proof.

###### Proof.

### Appendix B Experimental Details

#### B.1 Iterated Prisoner’s Dilemma

We use an MLP layer connected to a GRU followed by another MLP head for both the actor and critic networks, similar to the architecture used in POLA (Zhao et al.,, ). We also use a replay buffer of agents collected during training, following . All of our IPD experiments run in 50 minutes in a nvidia A100 gpu.

**Table 1: IPD Hyperparameters**
| Parameter | Value |
| --- | --- |
| Actor Training Optimizer | Adam |
| Actor Training Entropy Beta | 0.15 |
| Actor Training Learning Rate (Actor Loss) | 0.0001 |
| Advantage Alignment Weight | 0.3 |
| Actor Hidden Size | 64 |
| Layers Before GRU | 1 |
| Q-Value Training Optimizer | Adam |
| Q-Value Training Learning Rate | 0.001 |
| Q-Value Training Target EMA Gamma | 0.99 |
| Q-Value Hidden Size | 64 |
| Batch Size | 2048 |
| Self-Play | True |
| Reward Discount Factor | 0.9 |
| Agent Replay Buffer Capacity | 10000 |
| Agent Replay Buffer Update Frequency | 1 |
| Agent Replay Buffer Current Agent Fraction | 0 |
| Advantage Alignment Discount Factor | 0.9 |

#### B.2 Coin Game

We use the same architecture used for IPD with an MLP connected to a GRU unit, followed by another MLP. We experimented with both Advantage Alignment (Equation equation 8) and Proximal Advantage Alignment (Equation equation 9), with Advantage Alignment performing better (this is the one we used). All of our Coin Game experiments run in 30 minutes in a nvidia A100 gpu.

**Table 2: Coin Game Hyperparameters**
| Parameter | Value |
| --- | --- |
| Actor Training Optimizer | Adam |
| Actor Training Entropy Beta | 0.1 |
| Actor Training Learning Rate (Actor Loss) | 0.002 |
| Advantage Alignment Weight | 0.25 |
| Actor Hidden Size | 64 |
| Layers Before GRU | 1 |
| Q-Value Training Optimizer | Adam |
| Q-Value Training Learning Rate | 0.005 |
| Q-Value Training Target EMA Gamma | 0.99 |
| Q-Value Hidden Size | 64 |
| Batch Size | 512 |
| Self-Play | True |
| Reward Discount Factor | 0.96 |
| Agent Replay Buffer Capacity | 10000 |
| Agent Replay Buffer Update Frequency | 10 |
| Agent Replay Buffer Current Agent Fraction | 0 |
| Advantage Alignment Discount Factor | 0.9 |

#### B.3 Negotiation Game

We experimented with both Advantage Alignment (Equation equation 8) and Proximal Advantage Alignment (Equation equation 9), with the original Advantage Alignment performing better.

Agent’s Architecture:
The game observations are a concatenation of the availability of the items, agent’s value for each item, opponent’s value for each item, and previous round proposals. This makes up for an input vector of length $15$. The previous round proposals are especially important as the agents need to examine whether the opponent defected against them by proposing high proposals for item in which the value of the item is higher for the agent compared to the value of the item to the opponent. In other words, if the opponent wanted to gain a little return in exchange of huge loss to the agent, defecting.

Encoder:The observation is then processed by an encoder. The encoder is a GRU network. The GRU network consists of first two Linear Layers with a relu non-linearity in between. Then it is passed to a GRU unit.

Critic: The output of the GRU is then fed to a two-layer MLP with relu non-linearities for the critic module of the agent. Additionally, we concatenate the output of the encoder with the time, the index of the step of the game, for the value function as otherwise it would be hard to estimate the value of the state without knowing how long the game is going to go on for.

Actor: The actor is the most complex component as it deals with continuous actions. The output of the encoder is passed to an MLP with relu non-linearities and the output of the MLP is passed to a $\tanh$ activation and scaled by $2.5$, the output of this MLP is used as the mean of a normal distribution. The logarithm of the standard deviation is modeled by a single global parameter in the actor. Next, a sample of this normal distribution is passed through a $\tanh$ activation and scaled and shifted back to $(0,5)$. Computing the log probability of this transformations requires careful implementation. Especially if the $\operatorname{atanh}$ operation that is used is numerically unstable. Please refer to the code released with this paper for the exact implementation.

Hyperparameters:
Please refer to 3 for the hyperparameters used in our negotiation game experiments. We use a replay buffer on our gather trajectories although the rate that it is mixed with fresh trajectories is small.

**Table 3: Negotiation Game Hyperparameters**
| Parameter | Value |
| --- | --- |
| Actor Training Optimizer | Adam |
| Trajectory Length | 50 |
| Encoder Layers | 2 |
| MLP Model Layers | 2 |
| Replay Buffer Size | 100000 |
| Replay Buffer Update Size | 500 |
| Replay Buffer Off-policy Ratio | 0.05 |
| Q-Value Training Optimizer | Adam |
| Optimizer (Actor) Learning Rate | 0.001 |
| Optimizer (Critic) Learning Rate | 0.001 |
| Entropy Beta | 0.005 |
| Advantage Alignment Weight | 3.0 |
| Self-Play | True |
| Batch Size | 16384 |
| Gradient Clipping Norm | 1.0 |

Note that the optimization of the agents in the negotiation game is unstable, preventing us from taking the last checkpoint. In our experiments in Fig 3(a) we select the checkpoint that corresponds to the best achieved return for the agent during the optimization of the agent and the opponent. While we are not completely certain, we observe the instability happens when the policy distribution concentrates around the maximum possible proposal which is $5$. We clipped the $\operatorname{atanh}$ operation in our implementation for more numerical stability. All of our Negotiation Game experiments run in 1 hour on a nvidia A100 gpu.

#### B.4 Melting Pot’s Commons Harvest Open

We experimented with both Advantage Alignment (Equation equation 8) and Proximal Advantage Alignment (Equation equation 9), with Proximal Advantage Alignment performing better.

Agent’s Architecture: In the Commons Harvest Open environment, agents receive observations consisting of a local view of the environment in the form of raw pixel data. Each observation is an image frame capturing the agent’s immediate surroundings. We use a 3 layer convolutional neural network, following (Mnih et al.,, ), to encode the observations, which are then passed to a GTrXL tranformer (Parisotto et al.,, ).

Encoder: The observation frames are processed by an encoder. The encoder is a GTrXL transformer network (Parisotto et al.,, ). The GTrXL network consists of 3 transformer layers, each with a model dimension of 192 and a feedforward dimension of 192. The transformer is capable of handling sequences up to a maximum length of 1000 steps, capturing temporal dependencies in the agents’ observations. In practice, we use a context length of 15.

Critic: The output of the encoder is then fed to a two-layer Multi-Layer Perceptron (MLP) with ReLU non-linearities for the critic module of the agent. To provide temporal context, we concatenate the current time step to the encoder’s output before feeding it to the critic. This helps the critic estimate the value of the state more accurately, as the remaining time in an episode can affect the expected return.

Actor: The actor network shares the encoder with the critic. The output of the encoder is passed through another MLP with ReLU non-linearities to produce logits over discrete action choices. The policy is modeled as a categorical distribution over these actions, which include turning around, moving in different directions, and zapping other agents.

Hyperparameters: Please refer to Table 4 for the hyperparameters used in our Commons Harvest Open experiments.

**Table 4: Commons Harvest Open Hyperparameters**
| Parameter | Value |
| --- | --- |
| Self-Play | True |
| Batch Size | 512 |
| Optimizer (Actor) Learning Rate | $1\times 10^{-5}$ |
| Optimizer (Critic) Learning Rate | $1\times 10^{-5}$ |
| Entropy Beta | 0.1 |
| Advantage Alignment Weight | 1.0 |
| Clip Gradient Norm | 10.0 |
| Transformer Layers | 3 |
| Transformer Model Dimension | 192 |
| Transformer Feedforward Dimension | 192 |
| Discount Factor ($\gamma$) | 0.99 |
| PPO Clip Range | 0.1 |
| PPO Updates per Batch | 2 |
| Normalize Advantages | True |
| Context Length | 15 |

We use a parallelized environment with 6 copies of Commons Harvest Open to make training more efficient. Following LOQA (), we keep a replay buffer of past agent parameters to ensure robustness against a distribution of policies. From this replay buffer we sample 2 agents at each iteration and play against 5 self-play agents with the current version of the policy. For each environment, we use the 5 on-policy trajectories to compute losses for the actor and critic. In total, our Commons Harvest Open experiments last 24 hours on an nvidia L40s gpu.

### Appendix C Additional Figures

#### C.1 Negotiation Game Training Curves

Figure 6 shows the training curves of Advantage Alignment on 10 seeds.

Figure: Figure 6: Training curves of Advantage Alignment averaged over 10 seeds.
Refer to caption: x7.png

#### C.2 Coin Game Full League Results

Figure 7 shows the head-to-head results of all agents we experimented with in a league.

Figure: Figure 7: The head-to-head results of all variants of the coin game agents experimented with in this paper. All numbers are an average of 10 seeds of one type of agent with 10 seeds of another type of agent, where each pair play 32 games. We ablate Advantage Alignment masking different components of the gradient. Cooperative (C), masks when both advantages are positive; Empathetic (E), masks when the advantage of the agent is positive and the advantage of the opponent is negative; Vengeful (V), masks when the advantage of the agent is negative and the advantage of the opponent is positive; Spiteful (S), masks when both advantages are negative.
Refer to caption: x8.png

#### C.3 Ablation Study Commons Harvest Open

Figure: Figure 8: Sample trajectories for Proximal Advantage Alignment agents with different $\beta$ weight. We select the best of 10 seeds for each value of $\beta$. On the first row: $\beta=0.5$, agents reach a policy where they try to consume the apples as fast as possible. On the second row: $\beta=1$, agents reach a ”bush guarding” policy, zapping any other agents coming into the same bush. On the third row: $\beta=2$, agents reach a policy where they rotate around specific paths, preventing the extinction of the bushes.
Refer to caption: x9.png

Interestingly the value of $\beta$, which is used to control the weight of the advantage alignment term in equation 10, leads agents to converge to different policies. With a low value of the weight ($\beta=0.5$), we empirically observed that most runs converge to a greedy policy that attempts to consume apples as soon as possible. With a value of $\beta=1$, we find policies that show a ”bush guarding” behavior preventing other agents from approaching their bush, and consuming apples within that bush with moderate restraint. This is the policy that shows the best evaluation performance in figure 4. With high values of the weight ($\beta=2$), most runs find a rotating strategy in which agents stick to eating only a subset of the apples on each bush. This policy has the highest pro-social return out of all of them. However, the rotating strategy is also vulnerable to exploitation from greedy agents and does poorly in the evaluation scenarios. Figure 8 showcases what these policies look like in practice.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 8
presentation: 4
questions: Additional clarification questions:
- Fig6 seems to indicate that Advantage Alignment is not really stable (increasingly noisy rewards, partial collapse towards the end of training against AC and AD). Is it sensible to hyperparameters? Or is there another reason for this behavior?
- Fig4 selects the best agent out of 10 seeds. Given the variance observed for the Negotiation Game in Fig6 (which granted is not the same game as Fig4), how representative are the results in Fig4?
- I am curious how Advantage Alignment can play against AD or AC if it can't change its policy (AD and AC are fixed policies). Doesn't this break Assumption 1?


Overall, I recommend for acceptance, for the strengths listed above (theoretically sound, well motivated, experimentally justified).
soundness: 4
strengths: Strengths:
- This paper follows a long line of work on opponent shaping (LOLA, POLA, COLA, LOQA) and builds on LOQA to propose a new opponent shaping algorithm. While it feels a bit incremental, I find the work very well motivated, and theoretically justified. Extensive experiments on different domains and with relevant baselines confirm its practical performance.
summary: This work aims to encourage cooperation in normal form games through opponent shaping. This is done by proposing Advantage Alignment, where the product of the advantages of the player's value-network and the opponent's value-network are used to update the policy. This means that, when advantages are aligned (i.e., they have the same sign), the log probabilities increase or decrease accordingly. The authors show theoretically that LOLA and LOQA, 2 other opponent shaping algorithms, also follow the advantage alignment principles. They then experimentally validate advantage alignment on Coin Game, Negotiation Game, and the high-dimensional Commons Harvest Open environment.
weaknesses: Concerns:
- Having access to the opponent's value function results in a specific setting where all the player's preferences are public. The negotiation game completely changes if we know the preferences of the opponent, and we could devise a simple strategy that maximizes the average utility of both players. Since the utilities in this experiment are orthogonal to each other, there does not seem to be any real dilemma. For these reasons, I believe the insights gained from the Negotiation Game experiments to be limited.
- Advantage Alignment uses the product of advantages to align the policy. When there are more than 2 players involved (as in Commons Harvest Open), does the alignment depend on the product of the advantages of all players? If so, if a single agent does not cooperate, the whole alignment product fails. This would limit the scaling of Advantage Alignment to $n$ players.

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 4
questions: - For the coin game, in the always defect case, LOQA receives slightly higher return than Advantage Alignment. Do you have any ideas for why this is?
-  In figure 3, there is mention of green values to show cooperation, but I do not see the green values in the figure.
- In Appendix 6, you mention that equation 59 uses the sum of past advantages of the agent up to the current time step and the advantage of the opponent at the current time step. Did you experiment with much tuning for number of terms to include in the sum of past advantages or number of future terms?
soundness: 3
strengths: This paper is very well-written, and I appreciated how the authors helped the reader build intuition and understanding of the significance of their technique in section 4. The experiments served to reiterate the strength of their algorithm's performance, and the authors gave solid context for why each environment was selected.
summary: This paper focuses on opponent shaping.  They propose an opponent shaping formulation that aligns the advantages of interacting agents, thereby simplifying the mathematical formulation of opponent shaping and reducing the associated computational complexity. In this formulation, the probability of future mutually beneficial actions is increased when their interaction has been positive. They demonstrate their methodologies' effectiveness on several social dilemmas and connect opponent shaping's past successes with this new advantage alignment formulation.
weaknesses: The main concern I have with the paper is its individuality from the LOQA work, which concerns a similar technique, applied on similar problems, that achieves similar results. Both the more complex experiments (negociation and and harvest open) and the attached proofs in the appendix helped differentiate some of the beneficial aspects of Advantage Alignment in terms of scalability.

---

confidence: 4
contribution: 2
initial_rating: 8
presentation: 3
questions: See concerns in weaknesses. If the these concerns can be resolved, I will consider to raise the score. However, for the moment I can only give a reject due to those concerns.
soundness: 2
strengths: 1. This paper proposed an original idea that derives the advantage alignment to implement the policy gradient with respect to the opponent (the opponent shaping term), which can reduce the computational complexity. This paradigm has been shown to have connections to previous opponent shaping approaches, which is a progress in this research direction.
2. The general quality of this paper is good. Although there are some technical points that I require some furtehr clarifications, most of proofs are correct to my best knowledge. The theorem proofs are actually dependent on assumptions raised in this paper, and assumptions are provided with explanations. The experiments were conducted on sufficient banchmarks, in comparison with multiple baselines. Furthermore, the results not only include the numeric results, but also involve some demonstrations of test case, which make the paper more comprehensive. 
3. This paper is well written. It has a clear motivation in Introduction and a thorough introduction of social delimma and opponent shaping. For those people who are not doing research in this direction, it is still friendly enough for them to catch up. 
4. As for the significance of the research problem, social delimma, it is surely a significant problem. The main reason from my own perspective is that it can simulate a class of social problems. About the opponent shaping direction, the significance to me is sceptical, since the requirement of opponent's knowledge seems like a bit strong assumption. However, I do not deny that this is a necessary step towards the weaker and more realistic assumptions. As a result, this paper is significant within the resesrch community of opponent shaping.
summary: This paper investigated a long-standing research problem in multi-agent systems and game theory, named social dilemma. To address this problem, this paper stood on the side of opponent shaping and proposed a method that attempted to align advantages of various agents, to achieve a compromise between social welfare and self-interests. The main assumption lies in the connection between the opponent's policy gradient and the agent's policy parameters. Building on this, this paper proposed a paradigm called Advantage Alignment, and a corresponding RL algorithm based on PPO. This paper also unified other approaches of opponent shaping, such as LOLA and LOQA, in the paradigm of Advantage Alignment. The experimental results on various tasks showed the effectiveness of the proposed Advantage Alignment.
weaknesses: I have some technical concerns about this paper, which are specifically listed as follows:
1. In line 720, could you explain why the $\beta$ term is missing?
2. In line 739, could you give more details about how equation (16) is derived from equation (15)?
3. In line 755, could you give more details about how to transform from (19) to (8), step by step?
4. In line 773, could you give more details about how equation (24) is derived from equation (23)?
5. In line 783, even with the assumption of orthonormal gradients, it is still not clear why equation (27) can be derived from equation (26). Could you please clarify this step by step?
6. In line 792, is $A^{*}_{\text{LOLA}}$ equal to $V^{1}$?
7. In line 809, could you explain why $\alpha \nabla_{\theta_{2}} V^{2}(\theta_{1}, \theta_{2})$ is equal to $\Delta \theta_{2}$?
8. In line 1001, there is a typo: equation equation -> equation.

Additionally, I also have some concerns about the experimental analysis:

9. In the results shown in Figure 1b, could you give some intuitive interpretation on the asymmetry between the results of CD and DC? For example, is it related to your theoretical claims?

---

confidence: 2
contribution: 3
initial_rating: 5
presentation: 2
questions: - Could the authors explain how LOLA and LOQA and AdAlign are related? I see the derivation in Theorem 1 and 2 but do not understand the implication and how they differ in terms of their training objectives.
- It is not clear why increasing the log prob when both agents' advantages are negative is desirable (Eq. 8 and Fig. 1a). Can the authors elaborate on this?
soundness: 3
strengths: - The proposed derivation is novel, and provides novel insight on opponent shaping methods
- The paper is theoretically grounded and well motivated.
- The resulting derivation unifies prior works nicely (Theorem 1 and 2).
- Broad suite of baselines and evaluation environments.
summary: The paper proposes a novel method for opponent shaping based on the advantage functions of the interacting agents. The derivation unifies prior works through the lens of advantage alignment. Empirically, the proposed method is effective in learning complex coordination behaviors under various multi-agent environments.
weaknesses: - I wish Section 2 and 3 are more detailed, and cover more technical background on prior works. The additional information would allow the reader appreciate the contribution much better.
- The evaluation protocol is not provided. For readers that have little background in opponent shaping, it is not clear if the agent is trained prior to the evaluation or being trained (and thus adapted) during the evaluation episodes.
- It is not clear why increasing the log prob when both agents' advantages are negative is desirable (Eq. 8 and Fig. 1a).
- To my understanding, the proposed method does not outperform the baselines LOQA algorithm. The authors should discuss the differences and why it is desirable to use the proposed method over LOQA.
- The paper claims that the proposed method is more efficient than the baseline but does not elaborate on this aspect.

Minor comments:
- The advantage function is not defined mathematically.
- I believe Eq.2 is not the right expression, though I think this does not affect the main derivation of the paper.
- The connection between Eq.5 and Eq.6 is not explained.

Meta-review: This paper proposes a new opponent shaping algorithm and a unified interpretation encompassing several others like LOLA and its relatives. They tested their algorithm on various environments including challenging ones such as Melting Pot environments. After discussion, all reviewers were happy with the paper.

Decision: Accept (Oral)