Advantage Alignment Algorithms

We really appreciate the feedback provided for the reviewer and will try to address the concerns/weaknesses to the best of our knowledge:

1. We also believe that these sections might be a little short, but due to the page limit it is very difficult to do modifications to them given that we would have to compromise on other sections of the paper that we believe are equally crucial.

2. This is a very valid observation and we will definitely add it to the paper, thank you. Our evaluation protocol is the same as LOQA: we train a policy using our algorithm, and deploy it in a zero-shot setting against a distribution of policies. We never do fine-tuning against other policies. Our robustness comes from the opponent shaping term and from training against past versions of the agent’s policy (agent replay buffer).

3. This increase in the log probabilities corresponds to retaliatory behavior. To understand why this kind of behavior is desirable, a good intuition comes from the Prisoner’s dilemma. Here, when an agent increases the probability of defection given that the other player has defected, it implicitly diminishes the Q-value of defection for the other agent. By reducing the Q-value of defection, the Q-value of cooperation becomes relatively better and agents are therefore more likely to cooperate. Similarly, in games where defection is a viable strategy, retaliation against it is desirable as it makes defection less likely to happen in the first place.

4. This is explored in more detail in the response to all reviewers above. A great part of our contribution is understanding, mathematically, what the gradient of LOQA is doing in the first place. LOQA has two big disadvantages with respect to Advantage Alignment, which are: lacking a PPO formulation and being intractable in continuous action spaces. We want to stress that “outperforming” is a very strong word in the multi-agent setting. This is especially nuanced here, since the performance of a policy depends on the distribution of the policies that it is evaluated against. Therefore there are almost always compromises. In the Coin Game for instance, LOQA shows higher return against itself and always defect compared to Advantage Alignment. But similarly, Advantage Alignment has a higher return against POLA and MFOS compared to LOQA. The differences are very small and both policies seem to be quite robust, which leads us to believe that we are very close to “solving” the Coin Game, in the sense of generating fixed policies that perform well against a distribution of strategies.

5. We want to clarify that Advantage Alignment has the same computational complexity as LOQA, which stressed the significant wall-clock advantages of REINFORCE based opponent shaping compared to other opponent shaping techniques including LOLA, POLA and MFOS. Additionally, Advantage Alignment has the extra empirical computational advantages of PPO.

Minor Comments:

1. We will add the definition of the Advantage function in the paper: $A^i(s_t, a_t, b_t) := Q^i(s_t, a_t, b_t) - V^i(s_t)$.
2. The equation is correct, please refer to [1]. One may write an expectation over $r$ as well if we assume that the reward function is stochastic, which is not for any of our settings.
3. The connection lies in that, if one were to expand equation 6, one would have to write it in terms of equation 5. This is because equation 6 takes the gradient of $\log \hat{\pi}^2$ requires calculating the gradient of $\hat{\pi}^2$. But there is indeed a typo here, where we should use $\hat{\pi}^2$ in equation 6, so thank you for pointing this out.

Questions:

1. Since this has been a point that has been brought up by other reviewers too, we delve in more detail about the similarities, differences, and advantages of Advantage Alignment compared to LOLA and LOQA in the reply to all reviewers above.

2. We have addressed this in point 3, above. But to clarify even further, this quadrant in Figure 1.a. corresponds with retaliatory behavior: it increases the probability of taking an action that hurts the opponent when the past interactions are negative.

We kindly ask the reviewer to reconsider their score if we have addressed their concerns.

References

[1] Agarwal, A., Jiang, N., Kakade, S., and Sun, W. (2021). Reinforcement Learning: Theory and Algorithms. Preprint.

We wanted to thank the reviewer for their feedback and for their appreciation of our paper. We also believe that the quality of the paper is good. Having said that, we now address the reviewer’s technical concerns:

1. There is indeed a $\beta$ factor missing here, and we will correct this, thank you.
2. To proceed from equation 15 to equation 16, we simply use the policy gradient theorem, in particular the Advantage form of the policy gradient which is detailed in [1]. We will add this clarification on our derivation as well.
3. In general if we have a double sum $\sum_{i=0} ( \sum_{j=i+1} a_i b_j )$, this is equivalent to $\sum_{j=0} \sum_{i<j} a_i b_j = \sum_{j=0} b_j \sum_{i<j} a_i$, this is because we are essentially summing over all tuples of natural numbers $(i,j)$ for which $j>i$. Now setting $a_i = \gamma^i A_i^i$ and $b_j = \gamma^{1+j} A^2_j \nabla_{\theta_1} \log \pi^1_j$ gives us the desired result.
4. We expand the steps as follows: $\begin{aligned} \nabla_{\theta}V(\theta) &= E_{\tau \sim \pi} \sum_{t=0}^{\infty}\gamma^t A(a_t|s_t) \nabla_\theta \log \pi_{\theta}(a_t|s_t)\\\\ &= \sum_{t=0}^{\infty} \gamma^t E_{\tau \sim \pi} [A(a_t|s_t) \nabla_\theta \log \pi_{\theta}(a_t|s_t)]\\\\ &= \sum_{t=0}^{\infty} \gamma^t \sum_{s_t, a_t} P(a_t,s_t) A(a_t|s_t) \nabla_\theta \log \pi_{\theta}(a_t|s_t) \\\\ &= \sum_{t=0}^{\infty} \gamma^t \sum_{s_t} P(s_t) \sum_{a_t} \pi_{\theta}(a_t|s_t) A(a_t|s_t) \nabla_\theta \log \pi_{\theta}(a_t|s_t) \\\\ &= \sum_{t=0}^{\infty} \gamma^t \sum_s P(s_t=s) \sum_a \pi_{\theta}(a|s) A(a|s) \nabla_\theta \log \pi_{\theta}(a|s) \\\\ &= \sum_s \left(\sum_{t=0}^{\infty} \gamma^t P(s_t=s)\right) \sum_a \pi_{\theta}(a|s) A(a|s) \nabla_\theta \log \pi_{\theta}(a|s) \\\\ &= \sum_s d_{\gamma}(s) \sum_a \pi_{\theta}(a|s) A(a|s) \nabla_\theta \log \pi_{\theta}(a|s) \\\\ &= \sum_{(s,a)} d_{\gamma}(s) \pi_{\theta}(a|s) A(a|s)\nabla_\theta \log \pi_\theta(a|s) \end{aligned}$ Where from equation 2 to 3 we used the fact that for any function of a state-action pair $f(a, s)$, we have: $\begin{aligned} E_{\tau \sim \pi} f(a_t, s_t) &= \sum_\tau P(\tau) f(a_t, s_t) \\\\ &= \sum_{a_t, s_t} f(a_t, s_t) \sum_{t_1 \neq t} \sum_{t_2 \neq t} \dots P(\tau) \\\\ &= \sum_{a_t, s_t} P(a_t, s_t) f(a_t, s_t) \end{aligned}$where in the last step we have just marginalised $P(\tau)$ over all time-steps except for $t$, setting $f(a_t, s_t) = \nabla_\theta \log \pi_{\theta}(a_t|s_t)$ gives the intended result.
5. Assuming orthonormality simply means that $\nabla_{\theta} \log \pi_\theta(a|s) \cdot \nabla_{\theta} \log \pi_\theta(a'|s') = 0$ for all $(a,s) \neq (a', s')$, hence the sum over all state-action pairs collapses to a single term, which contains the $(a', s')$ pair. The gradient dot product for that pair is assumed to be $1$ again by the orthonormality assumption. We will note that this orthonormality assumption is exactly true in the tabular case. i.e. if the parameters $\theta_i$ of our policy are exactly $\log \pi(a|s)$ for all possible $(a,s)$, then this assumption is exact.
6. Here $A^*_{LOLA}(s_t, a_t, b_t)$ is the new advantage that should be put into the policy gradient theorem in order to get the update direction for a LOLA agent. It's not equal to $V^1$.
7. This is the assumption that LOLA makes about the opponent, it is true by hypothesis. LOLA takes $\Delta \theta_2 = \alpha\nabla_{\theta_2} V^2$ because it assumes that the opponent is a naive learner (i.e. doesn't incorporate opponent-shaping information), and hence would take a gradient step by greedily maximizing its value function.
8. Thank you, we will fix it.
9. In figure 1b, the state CD corresponds to a previous state which is "player 1 cooperated, and player 2 defected", DC is the reverse, "player 1 defected, and player 2 cooperated". This figure illustrates that our algorithm finds the tit-for-tat policy, which cooperates if the opponent cooperated in the last turn, but defects otherwise. This asymmetry between CD and DC is very important, cooperating in both states means that our agent doesn't punish opponent defection.

We hope that our responses have satisfactorily addressed the reviewer's concerns, and we appreciate your positive comments regarding the originality, quality, clarity, and significance of our work. In this light we kindly ask the reviewer to reconsider their score.

References

[1] Agarwal, A., Jiang, N., Kakade, S., and Sun, W. (2021). Reinforcement Learning: Theory and Algorithms. Preprint.

Thanks for your answers. Most of my concerns have been addressed. However, I suggest the authors may add the explanations for question 5 and question 3 to the revised paper.

I will raise my score to 6, as I cannot recognize more impact of this paper that can convince me to give 8.

We thank the reviewer for their kind comments and adress their concerns:

Weaknesses

The crucial difference between LOQA and Advantage Alignment lies in the ability to leverage PPO as a base optimizer instead of a Reinforce gradient estimator, which is very desirable for going beyond very simple toy environments like the coin game. We start from the same general assumptions as LOQA, but by phrasing our algorithm in terms of modifications to the advantages (and not through additional gradient terms like in LOQA), we can use off-the-shelf PPO. This greatly simplifies the implementation, and provides a much more scalable (in terms of environment complexity) opponent-shaping algorithm. LOQA by itself does not scale to environments like commons_harvest, so this is not a trivial difference, but a critical component needed for complex multi-agent tasks. LOQA also does not work for continuous action spaces, whereas Ad-Align is easily extendable to that case. Overall we see Ad-Align both as a more scalable successor to LOQA, and as a conceptual lens through which to view opponent-shaping as a whole, as mentioned in the response to all reviewers.

Questions:

1. Our policies are neural network policies that condition on the entire history of observations, so it is very likely that the two algorithms converge to slightly different criterias for defection, i.e. how many times they observe defection before defecting themselves. On a related note, interpreting these policies is difficult for the exact same reason, the space of possible policies is very vast. What is interesting is that, although LOQA outperforms Advantage Alignment in the always-defect evaluation it does not in the evaluation against other exploitative policies like those of POLA and MFOS.
2. That is a typo, the caption should say that Blue values mean cooperation, thank you.
3. For the IPD, Coin Game and Negotiation Game experiments we used a context length of 16 and a discount factor of 0.9 without further experimentation. This is standard in the opponent-shaping community as it nicely approximates “infinite” returns. For the Meltingpot experiments we tried different context lengths of 30, 60, 80 and 100, with 30 working best. We believe the fundamental tradeoff between more expressive state representation and compute speed greatly favored speed in the context of Commons Harvest Open. In other words it is more valuable to have more parameter updates at the expense of context length in this environment.

We thank the reviewer for their positive comments and constructive feedback. We address the reviewer’s concerns and questions:

Concerns:

1. First we want to clarify that preferences are not completely orthogonal, since the minimum value for any item is one, either player always gets utility for any extra item taken. We agree that the negotiation game changes if the preferences are public, and that a very simple strategy can maximize the utility of both players, but this makes the failure of naive PPO all the more evident! The environment should be trivial to solve, yet we see current methods fail even in this simplified case.

2. In the many-player scenario, the policy gradient term becomes: $\nabla_{\theta_1}V^{1}(\mu) = E_{\tau}\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} \sum_{j\neq 1} \log \pi^j (b_t | s_t)\right)\right]$ And we will have a separate opponent-shaping term for each opponent (all of our math runs the same for each term in the sum over $j$). The new advantages do not depend on the product of all the players' advantages (which would indeed be catastrophic for scaling), but simply as the sum of 2-player advantages, i.e., our 2-player advantage update equation (for player 1, ommiting discount factors) $A_t = A^1_t + \beta \left(\sum_{k<t} A^1_k \right)A^2_t$ becomes in the n-player case: $A_t = A^1_t + \beta \left(\sum_{k<t} A^1_k\right)\left[\sum_{j\neq1}^n A^j_t\right]$ Which is simple to compute and has a natural interpretation as viewing the system of other $n-1$ agents as a single agent with advantages $\sum_{j\neq 1}^n A^j_t$. We believe this property of advantage alignment makes it especially suitable to many-player environments. It is also easy to implement using matrix multiplication.

Questions:

1. This kind of instabilities are more apparent in the negotiation game but certainly not unique to it. Compared to single agent reinforcement learning, multi-agent reinforcement learning has the complication of the non-stationary property of the environment. Every time another agent updates their policy, this affects the transition dynamics, making training much more unstable. In our setup we have discovered that training against a (diverse) replay buffer of past policies is crucial for improving stability. However this solution is still not completely immune to complications. A common problem is that the replay buffer of agents saturates with policies with very similar behavior. In the case of the negotiation game we believe that the replay buffer saturates with cooperative policies and the agent forgets about retaliatory behavior since it is less likely to ever observe it in the first place. Ultimately this leads to performance drops against the Always Defect policy.

2. We want to establish that getting even a single seed that performs well in Meltingpot environments is already a very strong signal. The Meltingpot contest was won by single-seed hand-crafted policies that used domain knowledge about the environment to design strategies that maximize the utility of each individual game. Hence, getting a trained policy that performs well is already a non-trivial result. Having said that, out of our 10 seeds 3 get strong results temporarily at different stages of training. Since the stages of training are non-overlapping for the different seeds, it is hard to do an average-case analysis as it is standard in the single agent reinforcement learning literature. Since submitting, we have been arduously working on improving the stability of our runs by exploring auxiliary self-supervised losses and improving engineering components of our code (e.g. bigger agent replay buffers). Preliminary results look very promising, and our seeds are able to maintain high evaluation scores for significantly longer periods of time, compared to those at the time of submission.

3. This is related to our evaluation protocol (see reply to all reviewers), which is training our policies using the Advantage Alignment PPO policy gradient at training time and deploying in a zero-shot setting. As such, the assumptions are only valid at training time: since we train in a self-play setting, Assumption 1 holds. After training, we get a fixed policy that has dependence only on the past observations, therefore, it is straightforward to evaluate it against any opponent policy: we just run episodes against them.