Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: Review Update (18/11/2019)
Thank you for the detailed replies and significant updates to the paper in response to all reviewers. You have comfortably addressed all of my concerns and so I have updated my score. I think the paper has improved significantly through the rebuttal stage and therefore the update in my score is also significant to match the far larger contribution to the community that the paper now represents.

--
This paper considers alpha-rank as a solution concept for multi-agent reinforcement learning with a focus on its use as a meta-solver for PSRO. Based on theoretical findings showing shortcomings of using the typical best response oracle, the paper finds a necessity for a new response oracle and proposes preference-based best response.

The theoretical contributions help further the community's understanding of alpha-rank but the method remains somewhat disconnected from other recent related literature. Therefore, I think the paper's subsequent impact could be significantly improved by making more direct comparison to recent results. Specifically:

1) In the 2-player games comparisons are currently made to PRD based on its use in Lanctot et al (NeurIPS, 2017) instead of the more recent PSRO Rectified Nash approach proposed by Balduzzi et al. (ICML, 2019). Please make this direct comparison or justify its exclusion.

2) The preliminary MuJoCo soccer results in Appendix G significantly increase the relevance of this work to the ICLR community given the prior publication of this environment at ICLR 2019. However, the results are currently incomplete. In particular, to again strengthen the link to existing work, comparison of the method proposed in this paper to the agents trained by population based training in Liu et al. (ICLR, 2019) would be a more informative comparison than the preliminary results presented in comparison to the naïve uniform meta-solver.

3) Appendix A includes a brief literature survey. This is important material to position the paper in relation to existing work, particularly for readers not familiar with the area that will rely on this to understand the paper as a self contained reference. Please move this section into the main body of the paper and expand to fully credit the work this paper builds upon.


Minor Comments:
In Appendix C.4 should the reference to Figure C.7 be to Figure C.7a specifically? and the reference to Figure C. 7a be to Figure C. 7b-f inclusive? If so, I believe the available joint strategies in step 4 is missing (1,1,2) as shown in Figure C. 7f.

review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: This paper extends the original PSRO paper to use an $\alpha$-Rank based metasolver instead of the projected replicator dynamics and Nash equilibria based metasolvers in the original. To this end, the paper modifies the original idea of Best-Response (BR) oracle since it can ignore some strategies in $\alpha$-Rank defining SSCC to introduce the idea of _preference-based_ Best-Response (PBR) oracle. The need for a different oracle is well justified especially with the visualization in the Appendix. The main contributions that the paper seems to be going for is a theoretical analysis of $\alpha$-Rank based PSRO compared to standard PSRO. From the PBR's description (especially in Sec 4.3) it seems the paper is intereseted in expanding the population with novel agents rather than finding the "best" single agent which is not well defined for complex games with intransitivities. Nevertheless, it seems that BR is mostly compatible with PBR for symmetric zero-sum two-player games.
The paper performs empirical experiments on different versions of poker. First set of experiments compare BR and PBR with $\alpha$-Rank based metasolver on random games and finds that PBR does better than BR at population expansion as defined. The second set of experiments compare the metasolvers. $\alpha$-Rank performs similarly to Nash where applicable. Moreover it's faster than Uniform (fictitious self-play) on Kuhn. Then the paper tacks on the MuJoCo soccer experiment as a teaser for ICLR crowd.

Overall the paper is quite interesting from the perspective of multiagent learning and I would lean towards accepting. However the paper needs to clarify a lot of details to have any chance of being reproducible.

** Clarifications needed:

- Tractability of PBR-Score and PCS-Score
It's unclear how tractable these are. Moreover these were only reported for random games. What did these scores look like for the Poker games? Could you clarify how exactly these were computed?

- It's somewhat unclear what the lack of convergence without novelty-bound oracle implies. Does this have to do with intransitivities in the game?

- Dependence of $\alpha$?
The original $\alpha$-Rank paper said a lot about the importance of choosing the right value for $\alpha$. How were these chosen? Do you do the sweep after every iteration of PSRO?

- Oracle in experiments?
The paper fails to mention the details about the Oracles being used in the experiments. They weren't RL oracles but more details would be useful. 

- BR not compatible with PBR, albeit not the other way around, meaning one of the solutions you get from PBR might be BR, but can we say which one?

- For MuJoCo soccer was it true PSRO or cognitive hierarchy. In general, the original PSRO paper was partly talking about the scalable approach via DCH. This paper doesn't mention that at all. So were the MuJoCo experiments with plain PSRO? What was the exact protocol there? From the appendix it's unclear how the team-vs-team meta game works with individual RL agents. Moreover how are the meta-game evaluation matrices computed in general? How many samples were needed for the Poker games and MuJoCo soccer?

- The counterexamples in Appendix B3 are quite interesting. Do you have any hypotheses about the disjoint support from games' correlated equilibria?
review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: The paper studies α-Rank, a scalable alternative to Nash equilibrium, across a number of areas. Specifically the paper establishes connections between Nash and α-Rank in specific instances, presents a novel construction of best response that guarantees convergence to the α-Rank in several games, and demonstrates empirical results in poker and soccer games. 

The paper is well-written and well-argued. Even without a deep understanding of the subject I was able to follow along across the examples and empirical results. In particular, it was good to see the authors clearly lay out where their novel approach would work and where it would not and to be able to identify why in both cases. 

My only real concern stems from the empirical results compared to some of the claims made early in the paper. Given the strength of the claims comparing the authors approach and prior approaches, it seems that the empirical results are somewhat weak. The authors make sure to put these results into context, but given the clarity of the results in the toy domains I would have expected clearer takeaways from the empirical results as well. 

Edit: The authors greatly improved the paper, addressing all major reviewer concerns.
review_title: Official Blind Review #3

Meta-review: This paper analyzes and extends learning methods based on Policy-Spaced Response Oracles (PSRO) through the application of alpha-rank.  In doing so, the paper explores connections with Nash equilibria, establishes convergence guarantees in multiple settings, and presents promising empirical results on (among other things) 3-to-5 player poker games.

Although this paper originally received mixed scores, after the rebuttal period all reviewers converged to a consensus. A revised version also includes new experiments from the MuJoCo soccer domain, and new poker results as well.  Overall, this paper provides a nice balance of theoretical support and practical relevance that should be of high impact to the RL community. 
Decision: Accept (Talk)