Best Response Shaping

We thank the reviewer for their time and feedback.

Weaknesses:

Fundamental Issue:

We would like to remind the reviewer that we are not making the assumption that the solutions to our games are symmetric Nash Equilibria: the detective and agent do not share parameters with each other therefore the claim that we assume symmetric NE’s is false and not incorporated into the design of the algorithm. We recognize that the main variation of the algorithm incorporates a self-play loss that, if this were to be the only loss, would make it impossible to learn non-symmetric NE’s in 1-step Matrix form games. But we would like to remind the reviewer that our scope is iterated social dilemmas.

The reviewer states “This is an XOR game where the NE should be two agents taking different actions, which cannot represented by policies with shared parameters.” We present a counter example in the one-step history version of the XOR game. Consider the policy that randomly samples an action uniformly at random until the opponent chooses a different action, and subsequently sticks to their action thereafter. In a self-play setting (therefore a parameter sharing setting) this policy is a Nash equilibrium of the game, and corresponds to the same policy issuing different actions.

Regarding the problematic claims:

The reviewer states “This claim is wrong. Equation (7) is only equivalent to reward sharing with parameter sharing.” We would like to remind the reviewer that, by definition, self-play amounts to parameter sharing, therefore the original claim is not wrong. The reviewer also writes “Self-play with reward sharing'' should refer to the case where "you learn two different policies with different parameters while the game reward is shared across agents". This by definition cannot be self-play.

The reviewer writes “a game is both symmetric and zero-sum if and only if it is a zero game”, this claim is wrong. We are only aware of the definition of “zero-game” in the context of combinatorial games (from wikipedia): “the zero game is the game where neither player has any legal options”. A fundamental assumption of combinatorial games is a turn-taking nature. Therefore any non turn-taking symmetric zero sum game (e.g. rock paper scissors) is not a zero game.

The reviewer states “the concept of symmetric game only applies to two-player games.”, this statement is wrong. N-player symmetric games exist and are clearly defined. Tragedy of the Commons is one of them.

Regarding minor issues:

1. The n-player formulation is standard in the literature and provides a general framework in which the two-player formulation is an instance.

2. This is a correct observation and we currently suspect our statement is not valid. We will remove this statement from the paper.

3. We are aware of some notational inconsistencies and we thank the reviewer for pointing them out, we will definitely correct these.

4. We agree with the reviewer that this part of the notation should be made explicit and we will incorporate it when we introduce it in section 4.1.

We ask the reviewer to reconsider their score.

We thank the reviewer for their time and feedback. We hope we have addressed the raised concerns. As the discussion period is drawing to a close, we kindly ask the reviewer if there are any further concerns or points.

The authors assume the solution is symmetric with parameter sharing in the self-play process. This assumption raises two primary issues:

1. Solving the game with parameter sharing does not necessarily lead to NEs since symmetric NEs may not exist. This has been shown in the XOR game example and the chicken game example. Instead of offering examples, it would be more appropriate for the authors to rigorously prove that the solution is indeed a NE when the game is solved with parameter sharing. However, this seems unattainable, as demonstrated in the XOR game and the chicken game examples

2. Furthermore, I also want to point out that solving the game with parameter sharing and reward sharing does not necessarily lead to cooperative behavior. Consider a symmetric matrix game as shown below.

(0,0), (0,1)
(1,0), (0,0)

Solving the game with reward sharing and parameter sharing by equation 7. yields a policy $\pi=(0.5,0.5)$. For $\pi=(0.5,0.5)$, the expected shared reward is $0.5\times0.5+0.5\times0.5=0.5$. However, the solution that maximizes the shared reward in this game is not symmetric, $\pi_1=(1,0)$ and $\pi_2=(0,1)$. The shared reward of this non-symmetric solution is $1$.

Regarding the problematic claims in Section 4.3.2.

1. "In zero-sum games, this update will have no effect as the gradient would be zero." This is claim is correct but meaningless because in symmetric zero-sum two-player games, the expected return would always be zero if both players are using the same policy.

2. "this is equivalent to training an agent with self-play with reward sharing". Self-play is not equivalent to either parameter-sharing or a symmetric policy. The error lies in the assumption that both players use precisely the same policy in self-play; in self-play, players can employ different policies at the same state.

We would like to thank the reviewer for their time and thoughtful feedback

Weaknesses:

1. What we intended to demonstrate is that BRS produces a final, fixed policy that is not exploitable by a learning policy trained against it. We believe that the performance against MCTS demonstrates that while POLA is exploited, BRS is not. Given that both the MCTS and the learning opponent approximate the best response (but the MCTS is stronger) then we did not feel the necessity of showing the performance against a learning opponent. We do have experimental results against a learning opponent for BRS and POLA and will incorporate them in the paper. We also share the reviewer’s concern that a Stackelberg equilibrium might be undesirable for social welfare and suspect this is the fundamental reason for the need of the prosocial self-play loss. However, it would be helpful for us if the reviewer clarifies what kind of analysis would help solidify these points.

2. Regarding [1], we believe that a similar algorithm that approximates the proximal point method would be prohibitively expensive in the context of reinforcement learning. [1] scales linearly in $k$ but the underlying function w.r.t. which gradients would be computed is an approximation of the value function. This implies that to compute a single parameter update $k$ different unrollings of different policies would be required in the environment. Moreover, by the recursive structure of the update equation, these unrollings would have to be computed sequentially. This is not even considering the high variance that the chained estimators of the value function would have. Also, notice that [1] is not too different from POLA in terms of complexity.

3. We will include the training curves for these algorithms, but considering more complicated social dilemmas puts BRS to a higher standard than its predecessors, namely POLA.

4. We thank the reviewer for pointing out these typos and we will fix them.

Questions:

1. We thank the reviewer for taking the time to read through the proof and will do our best effort to clarify it. These two statements refer to different properties of the game. In particular $r^1(s_t, a_t, b_t) = -r^2(s_t, b_t, a_t)$ refers to the zero sum property and $r^1(s_t, a_t, b_t) = r^2(o_t, b_t, a_t)$ refers to the symmetry property. The key observation is that $s_t \neq o_t$, therefore $r^1(s_t, a_t, b_t) = r^2(o_t, b_t, a_t)$ does not imply $\mathbb{E}\left[R^1(\tau)\right] =\mathbb{E}\left[R^2(\tau)\right]$. The correct implication would look something of the form $\mathbb{E}\left[R^1(\tau)\right] =\mathbb{E}\left[R^2(\tau_o)\right]$ where for each $\tau$ there exists a $\tau_o$ with the same probability (in the self-play case). As an example consider a state $s_t$ in the Coin Game where the blue player takes the blue coin and the red player does not. The $o_t$ state refers to an analogous state in which the red player takes the red coin and the blue player does not. By symmetry of the game it should be the case that $r^1(s_t, a_t, b_t) = r^2(o_t, b_t, a_t)$. And, if the game rewards are set appropriately, it can simultaneously hold that $r^1(s_t, a_t, b_t) = -r^2(s_t, b_t, a_t)$ (that would correspond to the red player being punished with a negative reward of what the blue player got for taking the blue coin in state $s_t$).

References:

[1] Recursive Reasoning in Minimax Games: A Level k Gradient Play Method

We would like to thank the reviewer for their time and thoughtful feedback

Weaknesses:

Missing References

We appreciate the reviewer pointing these references out, we will include them in the literature review. We would like to clarify that [1] makes two major assumptions that significantly simplify the problem. First, [1] is restricted to normal form games so the best response that is being computed corresponds to a mixed strategy. In contrast, BRS computes an approximation to the best response in policy space, which is significantly harder (and unclear how to do using [1]). Second, because [1] deals with matrix form games, it is relatively straightforward to define a sampling method for the policies, in their case a Determinantal Point Process, due to the linear nature of the underlying strategies. In contrast BRS adds diversity to fictitious play by keeping a replay buffer of encountered agents and adding noise to the policy parameters. So it remains unclear to us how a) [1] is able to scale beyond normal form games into games that require a neural network policy parameterization and b) that [1] provides a solution to social dilemmas.

Limitations:

Our method assumes that the rewards for all agents are visible but we would like to remind the reviewer that this kind of assumptions are normal in the literature: POLA makes this assumption and LOLA makes a stronger one (assuming access to policy parameters). The reviewer correctly points out that this limits the application of BRS to non-cooperative settings where the reward may be privately received.

What we intended to say by writing “partially-competitive games” was social dilemmas so we will probably change all the appearances of this term to clarify the scope of our paper. We are not providing a solution for zero sum or fully cooperative games.

Regarding the conclusion, the reviewer correctly points out that BRS is not a method that works for n-player games as it is stated in the limitations of the paper. However, because BRS allows for the use of neural network policies it can scale to more complex games that use higher dimensional representations of the environment.

Questions

1. In BRS since the policies are non-linear, diversity is found using a replay buffer of policies and adding gaussian noise to the parameters of these policies. Which contrasts with the Determinantal Point Processes used in [1] and [2]. However, diversity seems to be not necessary for the Coin Game experiments as shown in the ablation section.

2. BRS cannot be applied to games where the reward for the other player remains unobserved unless that reward can be inferred from the behavior of the other player. Nonetheless, similar assumptions are done in the literature and used only during training; at deployment time the assumption is not necessary.

3. We do not know the answer to this question but we believe it is a very important one that should be explored in future work. Weakest link resembles Pure Diplomacy in the necessity for cooperation during the initial stages of the game and the need for competitive policies afterwards, and Pure Diplomacy has been one of the setups that we are interested in pursuing. We also believe BRS may work in a two player game with this structure, because the first gradient component (against the detective) induces adversarial behavior whereas the second one (self-play) induces cooperative behavior.

Under these considerations, would you be willing to increase your score?

References:

[1] Perez-Nieves, Nicolas, et al. "Modelling behavioural diversity for learning in open-ended games." International conference on machine learning. PMLR, 2021.

[2] Yang, Yaodong, et al. "Multi-agent determinantal q-learning." International Conference on Machine Learning. PMLR, 2020.

We deeply thank the reviewer for their thorough, detailed, and in-depth feedback. Here is our response. (Sorry, we needed to cut the response to two parts)

Weaknesses:

Originality:

We will indeed include PSRO in our literature review as it highlights the contribution of BRS over previous existing approaches. PSRO extends an existing set of policies by the best response policy to a meta-strategy of previous policies. PSRO does not differentiate through this best response generation mechanism. This is in contrast to the essence of BRS. Let’s imagine PSRO on IPD. First, it starts with a random policy. Next, always defect as the best response is added. Next, the best response to the existing set is added which is again always defect. Therefore, PSRO cannot discover tit for tat(TFT) on IPD. However, BRS is different. BRS trains an agent against a best response opponent by being aware that the opponent will be the best response. That pushes BRS to learn TFT.

Clarity:

1. We thank the reviewer for their deep reading of the paper. We will rewrite the description of the algorithm to make it clear that the agent and the detective are being trained simultaneously.

2. We will define BRS-NOSP when we describe BRS.

3. The QA description shows that the detective can use any conditioning mechanism that requires querying the agent in different states. The choice for the coin game was an instance of the QA.

4. Diplomacy is mentioned as a large-scale game in which without forming local alliances it is impossible to win the game. Because naive RL agents don’t develop the necessary reciprocation based cooperation the successful approaches train on human data. Therefore, one long term goal is to train agents that do well on Diplomacy without any human data to teach them the tit for tat like behavior.

5. We don't have an Equation 12; perhaps you're referring to Equation 2? Indeed, we will make it clear that theta2_star represents the entire optimization process, encompassing differentiation throughout. We appreciate the reviewer's clarification on this.

Quality:

We agree that more seeds for POLA is more desirable to hinder variance. We will include more POLA seeds for the camera ready version.

POLA is the only method that gives us a strong baseline for the coin game. We agree with the reviewer that while we care about generating a static policy, POLA cares more about learning online. However, the POLA authors themselves evaluate the final POLA against always defect and always cooperate opponents indicating interest in studying the properties of static final policy. Also, producing a final static policy that does well against learning opponents is valuable.

Significance:

We argue if one wants to deploy an agent in an environment full of other learning opponents maximizing their own return (naive RL) - which we believe is most cases in the real world - one would rather deploy an BRS agent than a POLA agent.

To make our argument more concrete, we show BRS agents are closer to tit for tat in IPD.

First, the best response to TFT on IPD is always cooperate. This is important as learning opponents find the best response to the deployed agent eventually. Our MCTS experiments show that while the best response to BRS is almost always cooperation, this is not the case for POLA.

Second, TFT agents always cooperate with themselves. This is not the case for POLA while it is for BRS agents. Third, As TFT starts with cooperation at the first move it gets a lower return in head to head game with always defect. But, that is a desirable property of TFT for social settings, assuming cooperation and also keeping the door open for forgiveness. BRS agents are exploited slightly more by always defect than POLA agents. But, first, still compared to always cooperate they are exploited much less. Second, the always defect is not being a rational opponent against BRS here as it could have a much higher return if it had cooperated. Third, this tendency of BRS to break the defect loops while making it a bit more exploited against always defect gives it its ability to cooperate with itself.

Regarding the head to head results, we don’t think solving social dilemmas is about comparing head to head results between two algorithms and indicating the algorithm with the higher return as the winner. TFT gets exploited by always defect but still tit for tat is a much better strategy. We can’t have complete non-exploitability and complete cooperation at the same time but we argue BRS makes a better trade off.

Regarding scalability, BRS is more scalable than Good Shepherd which differentiates through a gigantic computational graph of the opponent learning from scratch to convergence. But, we agree with the reviewer, BRS needs to do the required simulations and this limits its scalability. More advanced question answering mechanisms can improve the sample efficiency.