Introduction

We appreciate the thorough review and insightful comments provided by Reviewer EJCG. Your feedback has been instrumental in refining our paper. We have addressed each of your points and have changed the paper to reflect these changes. You can see the changes in blue in the new text.

1. Outputting the Best Found So Far Solution

Reviewer's Comment:
The reviewer suggests outputting the best-found-so-far solution across PSRO iterations to obtain the desired anytime property.

Response:
This is a reasonable suggestion. We had thought about this before submitting the paper but had decided not to include it because it does not perform as well. We have included this in Appendix F.4 in the final version of the paper. It performs better than PSRO but slightly worse than APSRO. A similar result is also evident in Figure 4.a where PSRO performance is near monotonic. Furthermore, we want to point out that this best-so-far technique could also be applied to APSRO and SP-PSRO.

2. PSRO Pure Strategies

Reviewer's Comment:
The paper originally did not clarify that common implementations of PSRO add pure strategies in each iteration.

Response:
We've revised the text (highlighted in blue) to specify that common implementations of PSRO add pure strategies every iteration.

3. ADO and Its Novelty

Reviewer's Comment:
Concerns were raised about the novelty of ADO and its comparison with Range of Skill (RoS) and DO.

Response:
We are upfront in our paper about the similarities of ADO with RoS and DO. We do not view ADO as our primary contribution but rather as a theoretical foundation on which we build the other scalable algorithms. We added to the text: “ADO primarily serves as a foundational element for the development of our subsequent algorithm, APSRO. This foundational role is crucial as it lays the groundwork for APSRO's convergence guarantees.”

4. Focus on Nash Equilibrium (NE)

Reviewer's Comment:
The paper primarily focuses on NE, while PSRO is adaptable to various solution concepts.

Response:
We've added a line clarifying that while our current focus is on two-player zero-sum games and NE. These techniques (at least APSRO) directly carry over to the TMECor solution concept for team games [1].

We are not sure whether that is the type of refinement that the reviewer is asking about. Or perhaps the reviewer is suggesting some normal-form refinement such as CCE. Or, perhaps the reviewers is suggesting some extensive-form refinement such as trembling hand. If the reviewer clarifies what sorts of refinements the reviewer is alluding to, we can try to provide further answers.

5. Ablations

Reviewer's Comment:
Consider including ablation-style experiments.

Response:
In the appendix, we've included additional experiments with SP-PSRO not-anytime and SP-PSRO last-iterate. We believe this covers the additions present in our algorithms. Are there any other particular ablations the reviewer would like us to include?

6. Clarifications and Language

Reviewer's Comment:
Last two weakness bullets: need for clearer language and notation, particularly for an ML audience.

Response:
We have revised the language for clarity, aligning it more closely with the ML audience's familiarity. Notations have been adjusted for consistency and comprehensibility. In particular, we have changed any mention of “empirical game” to “restricted game”. Changes are in blue.

7. Myopically Optimal Policy

Reviewer's Comment:
Clarification on the claim about adding an approximation of the myopically optimal policy. Also the question about adding mixed strategies.

Response:
The work discussed in A.2 does introduce the idea of a least-exploitable distribution, which we point out in the main text. However, that literature does not introduce the concept of adding the best mixed strategy to minimize exploitability the most.

You are right that this line of text is confusing though. The best mixed strategy to add, as you point out (and we also point out in our paper), is the actual Nash equilibrium. This is of course too hard to compute up front so we add a mixed strategy that does something similar to fictitious play that happens to have good empirical performance. As a result, we have changed the line to the following: “In addition to introducing APSRO, we also build on APSRO by adding to the population in each iteration a stochastic policy that is trained via an off-policy procedure.”

Thank you for your thoughtful and detailed feedback. We appreciate your reconsideration of the paper's score.

The main focus of our paper is to introduce new PSRO methods that achieve good performance even before convergence. In large games such as Starcraft, Dark Chess, and Stratego, PSRO may never converge because it requires so many policies. As a result, it is crucial to achieve good performance even before convergence.

Our method, SP-PSRO, is designed with this practicality in mind, ensuring that the strategies developed in the initial phases not only effectively explore the strategy space but also greatly improve performance before convergence. This approach aligns with the anytime-ness concept, which we believe is not merely a theoretical aspect but a critical feature in the real-world application of our algorithm. It ensures that at any point of early termination, the strategies are optimally effective, addressing the challenge of computational feasibility in large games.

We have added the following sentences to the introduction to better reflect this framing:

• "In large games like dark chess and Starcraft, where PSRO may never converge, the early performance holds paramount importance. Our approach with SP-PSRO is tailored to this reality, ensuring robust performance from the outset. Recognizing that the completion of the full training procedure in such extensive games is a rare occurrence, the anytime property of our proposed method takes on a critical role, delivering viable strategies at any stage of the iterative process."

• "Our empirical results demonstrate SP-PSRO's superior performance in reducing exploitability before convergence across various games, a testament to its practical effectiveness."

• "While APSRO serves as a foundational concept in our research, the leap to SP-PSRO marks a significant advancement, particularly in terms of reducing exploitability before PSRO has neared convergence."

We would also like to make the clarification that anytime-ness is achieved by solving a modified restricted game with a solution resilient to adding strategies that would normally hurt standard PSRO in the short term. Building on the benefits of anytime-ness, better strategy exploration helps us achieve lower exploitability early on in training. This is done by more sample-efficiently building effective populations able to represent important interactions in the full game. By providing both anytime-ness and better strategy exploration, the methods introduced in the work help us achieve reliably better performance in earlier stages of training and under smaller experience budgets.

We hope this clarification strengthens the understanding of our work's contributions and its practical significance in the field. Please let us know if there is anything we can further change.

Introduction

We appreciate the thoughtful review of our paper and your vote of acceptance. However, we believe that the concerns raised can be addressed in future work and that our current contributions stand on their own.

Scalability

Our algorithms are not inherently limited by the size of the game. The theoretical underpinnings of ADO, APSRO, and SP-PSRO ensure scalability. Their performance in larger games is a matter of computational resources rather than algorithmic capability. Indeed, PSRO has already been shown to scale to large games such as Barrage Stratego. Our experiments on Leduc poker and Liar's Dice, while seemingly limited, were chosen due to their relevance in the field. These games, though not as large as limit Texas Hold'em or Atari games, still present significant challenges in terms of state space and strategy complexity, providing a robust testbed for our algorithms. Further demonstrating performance on large games is outside the scope of this paper.

Comparison with Other Methods

It is crucial to understand that our algorithms are specifically designed to converge to Nash equilibrium. While comparisons with population-based and league training methods could be interesting, these methods are not guaranteed to converge to a Nash equilibrium, as shown in previous works on PSRO [1]. We did not include these other methods such as PSRO Rectified Nash PSRO [3] because it has already been shown not to converge to a Nash equilibrium. However, since the reviewer asked, we have included results with PSRO Rectified Nash in the appendix.

Generalization

Great point. We agree that extending our approach to multi-agent settings is a valuable avenue. While our current work focuses on two-agent environments, the methodologies and insights gained provide a stepping stone for tackling more complex scenarios. Adapting our algorithms for multi-agent settings is part of our ongoing research. We are exploring ways to compute exploitability and develop strategies in these environments. One particular path we are exploring is to combine techniques from this paper with techniques from this recent paper [2] for finding TMECor in team games. Thankfully, TMECor provides a similar notion of exploitability as in two-player zero-sum games. We have added text in the discussion and limitation about this aspect.

Conclusion

Our work represents a significant step forward in improving scalable PSRO algorithms while maintaining convergence guarantees. While there are always avenues for further research and improvement, we believe our contributions are solid, well-founded, and a valuable addition to the field. We hope this rebuttal clarifies our position and the strengths of our work. Thank you for your consideration.

[1] McAleer, Stephen, et al. "Pipeline PSRO: A scalable approach for finding approximate nash equilibria in large games." Advances in neural information processing systems 33 (2020): 20238-20248.

[2] McAleer, Stephen, et al. "Team-PSRO for Learning Approximate TMECor in Large Team Games via Cooperative Reinforcement Learning." Thirty-seventh Conference on Neural Information Processing Systems. 2023.

[3] Balduzzi, David, et al. "Open-ended learning in symmetric zero-sum games." International Conference on Machine Learning. PMLR, 2019.

Firstly, we would like to extend our sincere gratitude for the time and effort you have dedicated to reviewing our paper. We appreciate the opportunity to address the concerns you have raised. We believe that we have sufficiently addressed each of your points and have updated the paper with these changes in blue.

Regarding Clarity and Appendix References

We acknowledge your suggestion for clearer guidance towards the appendix, especially concerning our experimental framework. In our revised manuscript, we have included references to the appendix to clear up confusion. Revised text is in blue.

Monotonicity of Exploitability Curve

APSRO indeed does not show a completely monotone decrease in exploitability due to the imprecision in the best response and no-regret procedure. However, our experiments show that in most settings APSRO does not increase exploitability as much as PSRO. Furthermore, APSRO is a core component of SP-PSRO, which exhibits drastic increases in performance.

Complexity of SP-PSRO

Your observation about the complexity of the SP-PSRO algorithm is well-taken. Appendices F.1 and F.2 demonstrate that each component of SP-PSRO is in fact necessary.

Details on Restricted Games and Nash Equilibrium

In response to your suggestion, we have updated the text with clearer references to the appendix, which contains a detailed description of the restricted games and the methods used for approximating Nash equilibria, ensuring a clearer understanding of these critical aspects. We have also included a proof of Theorem 3.

Population Size and Policy Storage

We have updated the appendix to include data on the population sizes and disk space usage for deep RL experiments. The largest population we generated had 148 policies when running SP-PSRO on 4-Repeated RPS, taking 22MB of storage.

Clarifications on Notations and Procedures

• We have included a reference to DO in the appendix to clear up the beginning of section 3
• \pi_i \in \Pi_i is indeed a single policy. We have updated the paper to make this clearer.
• We have included a reference to the exact regret minimization procedure in the appendix at the beginning of section 4
• We have included a reference to Appendix K.3 for SP-PSRO details of how we compute the time average. We also include in Appendix F.2 ablations showing that the time-average variant of SP-PSRO is necessary. Intuitively, we need to do time-averaging to achieve a good mixed strategy.
• We did not include ADO in our normal form games because the performance was almost exactly the same as APSRO, so we didn’t want to make it confusing to read. We have included references to the appendix for training details. We didn’t use the same horizon because some games converged faster. Would you like us to include these results for the camera-ready version?
• We have included a reference to the Appendix for training details. Our intuition, as also described in the paper, is that one should include mixed strategies in the population. Ideally, these mixed strategies will be very close to a NE, so that is why we use a modified fictitious play procedure to produce the mixed strategies. You are right that SP-PSRO seems to have a big boost in performance at the beginning, but we don’t see other methods like PSRO or APSRO overtaking it. This makes sense because we can only improve our population by adding a policy to it, as long as we then output the least-exploitable distribution. As to the non-monotonicity of APSRO in Tiny Battleship, we acknowledge the limitation in predicting when APSRO might outperform PSRO. We hypothesize that APSRO's no-regret procedure was unable to find a satisfactory solution given the small budget allocated to each DO iteration. Hyperparameter tuning may yield better results. We have, however, observed consistent improvements in most games tested.
• We do not extend the length of experiments because we do not witness the exploitability lines crossing in normal form experiments, and each run already takes multiple days to complete. We included a reference to the appendix which contains the details of how we compute average strategies.

In conclusion, we have addressed all the concerns you have raised. We are confident that these revisions will significantly enhance the clarity, quality, and impact of our work. Once again, thank you for your constructive feedback and for contributing to the improvement of our paper.