This paper investigates a population-based training regime based on game-theoretic principles called Policy-Spaced Response Oracles (PSRO). PSRO is general in the sense that it (1) encompasses well-known algorithms such as fictitious play and double oracle as special cases, and (2) in principle applies to general-sum, manyplayer games. Despite this, prior studies of PSRO have been focused on two-player zero-sum games, a regime wherein Nash equilibria are tractably computable. In moving from two-player zero-sum games to more general settings, computation of Nash equilibria quickly becomes infeasible. Here, we extend the theoretical underpinnings of PSRO by considering an alternative solution concept, α-Rank, which is unique (thus faces no equilibrium selection issues, unlike Nash) and applies readily to general-sum, many-player settings. We establish convergence guarantees in several games classes, and identify links between Nash equilibria and α-Rank. We demonstrate the competitive performance of α-Rank-based PSRO against an exact Nash solver-based PSRO in 2-player Kuhn and Leduc Poker. We then go beyond the reach of prior PSRO applications by considering 3-to 5-player poker games, yielding instances where α-Rank achieves faster convergence than approximate Nash solvers, thus establishing it as a favorable general games solver. We also carry out an initial empirical validation in MuJoCo soccer, illustrating the feasibility of the proposed approach in another complex domain.
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?