Efficient Competitive Self-Play Policy Optimization
Authors: Yuanyi Zhong
Yuan Zhou
Jian Peng
Venue:  (2021)
Keywords: self-play
policy optimization
two-player zero-sum game
multiagent

Abstract: Reinforcement learning from self-play has recently reported many successes. Self-play, where the agents compete with themselves, is often used to generate training data for iterative policy improvement. In previous work, heuristic rules are designed to choose an opponent for the current learner. Typical rules include choosing the latest agent, the best agent, or a random historical agent. However, these rules may be inefficient in practice and sometimes do not guarantee convergence even in the simplest matrix games. This paper proposes a new algorithmic framework for competitive self-play reinforcement learning in two-player zero-sum games. We recognize the fact that the Nash equilibrium coincides with the saddle point of the stochastic payoff function, which motivates us to borrow ideas from classical saddle point optimization literature. Our method simultaneously trains several agents and intelligently takes each other as opponents based on a simple adversarial rule derived from a principled perturbation-based saddle optimization method. We prove theoretically that our algorithm converges to an approximate equilibrium with high probability in convex-concave games under standard assumptions. Beyond the theory, we further show the empirical superiority of our method over baseline methods relying on the aforementioned opponent-selection heuristics in matrix games, grid-world soccer, Gomoku, and simulated robot sumo, with neural net policy function approximators.

Under review as a conference paper at ICLR 2021
EFFICIENT COMPETITIVE SELF-PLAY POLICY OPTI- MIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Reinforcement learning from self-play has recently reported many successes. Self-play, where the agents compete with themselves, is often used to generate training data for iterative policy improvement. In previous work, heuristic rules are designed to choose an opponent for the current learner. Typical rules include choosing the latest agent, the best agent, or a random historical agent. How- ever, these rules may be inefficient in practice and sometimes do not guarantee convergence even in the simplest matrix games. This paper proposes new algo- rithmic framework for competitive self-play reinforcement learning in two-player zero-sum games. We recognize the fact that the Nash equilibrium coincides with the saddle point of the stochastic payoff function, which motivates ideas from classical saddle point optimization literature. Our method simultane- ously trains several agents and intelligently takes each other opponents based on a simple adversarial rule derived from a principled perturbation-based saddle optimization method. We prove theoretically that our algorithm converges approximate equilibrium with high probability in convex-concave games under standard assumptions. Beyond the theory, we further show the empirical superior- ity of our method over baseline methods relying on the aforementioned opponent- selection heuristics in matrix games, grid- forlwwrldd soccer, Gomoku, and simulated robot sumo, with neural net policy function approximators.
borrow
INTRODUCTION
Reinforcement learning (RL) from self-play has drawn tremendous attention over the past few years. Empirical successes have been observed in several challenging tasks, including Go (Silver et al., 2016; 2017; 2018), simulated hide-and-seck (Baker et al., 2020), simulated sumo wrestling (Bansal al., 2017), Capture the Flag (Jaderberg (Vinyals et al., 2019), and poker (Brown & Sandholm, 2019), to name a few. During RL from self- play, the learner collects training data by competing with opponent selected from its past self or an agent population. Self-play presumably creates an auto-curricllmm for the agents to learn at their own pace. At each iteration, the learner always faces an opponent that is comparably in strength to itself, allowing continuous improvement.
al., 2019), Dota (Berner al., 2019), StarCraft II
The way the opponents are selected often follows human-designed heuristic rules in prior work. For example, AlphaGo (Silver et al., 2016) always competes with the latest agent, while the later gener- ation AlphaGo Zero (Silver et al., 2017) and AlphaZero (Silver et al., 2018) generate self eelf-play data with the maintained best historical agent. In specific tasks, such as OpenAl's sumo wrestling, com- peting against a randomly chosen historical agent leads to the emergence of more diverse behaviors (Bansal et al., 2017) and more stable training than against the latest agent (Al-Shedivat et al., 2018). In population based training (Jaderberg et al., 2019; Liu et al., 2019) and AlphaStar (Vinyals et al., 2019), an clite or random agent is picked from the agent population the opponent.
Unfortunately, these rules may be inefficient and sometimes ineffective in practice since they do not necessarily enjoy last-iterate convergence to the "average-case optimal" solution even in tabular matrix games. In fact, in the simple Matching Pennies game, self-play with the latest agent fails to converge and falls into oscillating behavior, shown in Sec. 5.
In this paper, we develop an algorithm that adopts a principle-derive opponent-selection rule to alleviate some of the issues mentioned above. This requires clarifying first what the solution of

---

Under review as a conference paper at ICLR 2021
self-play RL should be. From the game-theoretical perspective, Nash equilibrium is fundamental solution concept that characterizes the desired "average-case optimal" strategies (policies). When each player assumes other players also play their equilibrium strategies, gain more by unilaterally deviating to another strategy. Nash, in his seminal work (Nash, 1951), has established the existence result of mixed-strategy Nash equilibrium of any finite game. Thus solving for a mixed-strategy Nash equilibrium is a reasonable goal of self-play RL.
one in the game can
We consider the particular case of two-player zero-sum games as the model for the competitive self- play RL environments. In this case, the Nash equilibrium is the same as the (global) saddle point and as the solution of the minimax program m maxzeY f fz. y). We denote z, y as the strategy profiles (in RL terminology. policies) and f as the loss for or utility/reward for y. A saddle point "e",y") E X x Y, where X, are the sets of all possible mixed-strategies (stochastic policies) of the two players, satisfies the following key property
f(x",)) S ((=,,") S f(x,y"), Va E Xyy EY
(1)
Connections to the saddle problem and game theory inspire us to borrow ideas from the abundant literature for finding saddle points in the optimization field (Arrow et al., 1958: Korpelevich, 1976; Kallio& & Ruszczynski, 1994; Nedić & Ozdaglar, 2009) and for finding equilibrium in the game theory field (Zinkevich et al., 2008; Brown, 1951; Singh et al., 2000). One particular class of method, i.e., the perturbation--aseed subgradient methods to find the saddles (Korpelevich, 1976; Kallio & Ruszczynski, 1994), is especially appealing. This class of method directly builds upon the inequality properties in Eq. 1, and has several advantages: (1) Unlike some algorithms that require knowledge of the game dynamics (Silver et al., 2016; 2017; Nowé et al., 2012). it requires only subgradients; thus, is easy to be adapted policy optimization with estimated policy gradients. (2) For convex- concave functions, it is guaranteed to converge in its last iterate instead of an average iterate, hence alleviates the need compute any historical averages as in Brown (1951); Singh et al. (2000); Zinkevich et al. (2008), which can get complicated when neural nets are involved (Heinrich & Silver, 2016). (3) Most importantly, it prescribes simple principled way to adversarially choose self-play opponents, which can be naturally instantiated with a concurrently-traiee trained agent population.
To summarize, we apply ideas from the certurbation-based methods of classical saddle point op- timization to the model-free self-play RL regime. This results in a novel population-basee policy gradient method with a principled adversarial seponent-selection rule. Analogous to the standard model-free RI. setting, we assume only "naive" players (Jafari et al., 2001) where the game dynamic is hidden and only rewards for their own actions are revealed. This enables broader applicability to problems with mismatched or unknown game dynamics than many existing algorithms (Silver et al., 2016; 2017; Nowé et al., 2012). In Sec. 4, we provide an approximate convergence theorem for convex-concad games as sanity check. Sec. 5 shows extensive experiment results favoring our al- gorithm's 's effectiveness in several games, including matrix games, grid-world soccer, a board game, and challenging simulated robot sumo game. Our method demonstrates higher per-agent sample efficiency than baseline methods with alternative opponent-selection rules. Our trained agents also outperform the baseline agents on average in competitions.
2 RELATED WORK
Reinforcement learning trains a single agent to maximize the expected return in an environment (Sut- ton & Barto, 2018). Multiagent reinforcement learning (MARL), of which two-agent is a special case, concerns multiple agents taking actions in the same environment (Littman, 1994). Self-play is training paradigm to generate data for MARL and has led great successes, achieving super- human performance in several domains (Tesauro, 1995; Silver et al., 2016; Brown & Sandholm, 2019). Applying RL algorithms naively as independent learners in MARL sometimes produces strong agents (Tesauro, 1995) but not always. People have studied ways to extend RI. algorithms specifically to MARL,, e.g., minimax-Q (Lituman, 1994), Nash-Q (Hu & Wellman, 2003), FoL.F-PG (Bowling & Veloso, 2002), etc. However, most of these methods are designed for tabular RL only, therefore not readily applicable to continuous state action spaces or complex policy functions where madieent-based policy optimization methods are preferred. Recently, Bai & Jin (2020), Lee et al. (2020) and Zhang et al. (2020) provide theoretical regret or convergence analyses under tabular or other restricted self-play settings, which complement our empirical effort.
There are algorithms developed from the game theory and online learning perspective (Lanctot et al., 2017; Nowé et al., 2012; Cardoso al., 2019), notably Tree search, Fictitious self-play (Brown,
2

---

Under review as a conference paper at ICLR 2021
1951), Regret minimization (Jafari et al., 2001; Zinkevich al., 2008), and Mirror descent (Mer- tikopoulos et al., 2019; Rakhlin & Sridharan, 2013). Tree search such as minimax and alpha-beta pruning is particularly effective in small-state games. Monte Carlo Tree Search (MCTS) is also ef- fective in Go (Silver et al., 2016). However, Tree search requires learners to know (or at least learn) the game dynamics. The other ones typically require maintaining some historical quantities. In Fictitious play, the learner best-responds to a historical average opponent, and the average strategy converges. Similarly, the total historical regrets in all (information) states are maintained in (coun- terfactual) regret minimization (Zinkevich et al., 2008). Furthermore, most of those algorithms are designed only for discrete state action games. Special care has be taken with neural net function approximators (Heinrich & Silver, 2016). On the contrary, our method does not require the compli- cated computation of averaging neural nets, and is readily applicable to continuous environments.
In two-player zero-sum games, the Nash equilibrium coincides with the saddle point. This enables the techniques developed for finding saddle points. While some saddle-point methods also rely on time averages (Nedić & Ozdaglar, 2009), a class of verturbation--asee gradient method is known to converge under mild convex-concave assumption for deterministic functions (Kallio & Ruszczyn- ski, 1994; Korpelevich, 1976; Hamm & Noh, 2018). We develop sampling version of them for stochastic RL objectives, which leads to a more principled and effective way of choosing opponents in self-play. Our adversarial opponent-selection rule bears a resemblance to Gleave al. (2019). However, our goal is to develop an effective self-play RL algorithm, while Gleave et al. (2019) aims at attacking deep self-play learned policies. recent work by Prajapat et al. (2020) tackles the self-play policy optimization problem differently from ours by employing a bilinear approximation to the game. Finally, although the algorithm presented here builds upon policy gradient, the same framework may be extended to other RL algorithms such as MCTS thanks to a recent interpretation of MCTS as policy optimization (Grill et al., 2020). Our way of leveraging Eq. 1 in a population may potentially work beyond gradient-based RL, e.g., in training generative adversarial networks similarly to Hamm & Noh (2018) due to the same minimax formulation.
3 METHOD
Classical game theory defines two-player zero-sum game as tuple (X, )) where X, Y are the sets of possible strategies of Players and respectively, and f: X x Y + R is a mapping from a pair of strategies to a real-valued utility/reward for Player 2. The game is zero-sum (fully com- petitive), so Player I's reward is -f. This is a special case of the Stochastic Game formulation for Multiagent RL (Shapley, 1953) which itself is an extension to Markov Decision Processes (MDP).
We consider mixed strategies induced by stochastic policies T. and T.. The policies can be parame- terized functions in which case X, Y are the sets of all possible policy parameters. Denote a as the action of Player and b, as the action of Player 2 at time I, let T be the time limit of the game, then the stochastic payoff f writes as
f(z v) = a CerKy,bera
Σ rr(ss, bi)
The state sequence {st] follows transition dynamic P(se+ 1st, ax be). Actions are sampled according to action distributions Ty (-1a,) and (-1s)) And r(s,, O2 be) is the reward (payoff) for Player 2 at time t. determined jointly by the state and actions. We use the term 'agent' and 'player' interchangeably. While we consider an agent pair (z, y) in this paper, in some cases (Silver et al., 2016), x = y can be enforced by sharing parameters if the game is impartial. The discounting factor weights between short- and long-term rewards and is optional.
Note that when one agent is fixed, taking y as an example, the problem .r is facing reduces to an MDP if we define a new state transition dynamic Pnew (8++1 18,, a.) = Σt, P(* ||s,, de, b)) (,)) (b.ls:) and a new reward Fnew (St, az) Σs, r(st, ((, at, by be) (bb))bb))))))))))))))))))))))( (be)s)). This leads to the naive gradient descent- ascent algorithm, which provably works in strictly convex-concave games (where is strictly convex in and strictly concave in y) under some assumptions (Arrow et al., 1958). However, in general, it does not enjoy last-iterate convergence to the Nash equilibrium. Even for simple games such as Matching Pennies and Rock Paper Scissors, as we shall see in our experiments, the naive algorithm generates cyclic sequences of x* y that orbit around the equilibrium. This motivates us to study the perturbation-basee method which converges under weaker assumptions.
3

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Perturbation- self-play policy optimization of an agent population.
Input: N: No iterations; T): learning rates; my: sample size; n:: population size; I: N" inner updates;
Result: n pains of policies;
Initialize (x) (,), = .,
for k 0, 1, .......... N do
Evaluate fa" v Vi,j E.... with Eq. 4 and sample size ma;
io 1, 1.... W do
Construct candidate opponent sets C2 = {v² = == 1... I....) and C = (af ==::::=1..mm 1...m)) Find perturbed of arg max f(a y). perturbed uf = arg min, (x,
Invoke single-agent RL algorithm (e.g., A2C, PPO) on x for / times that:
Estimate policy gradients 92, == efr) with sample size ma (c.g. Eq. 5);
Update policy by x; 2 + x mag=. (or RmsProp);
Invoke single-agent RL algorithm (e.g.. A2C, PPO) on y. for / times that:
Estimate policy gradients 9y: V. (u, vt) with sample size my:
11
12
Update policy by U, k++1
+ y/ + n. (or RmsProp);
13 return {<x vv( 1:m
Recall that the Nash equilibrium has to satisfy the saddle constraints Eq. 1: f(x", S f(x" y") < f(. v²). The perturbation based methods build upon this property (Nedić & Ozdaglar, 2009; Kallio & Ruszczynski, 1994; Korpelevich, 1976) and directly optimize for solution that meets the con- straints. They find perturbed points u of Player I and of Player 2, and use gradients at (ar, v) and (u, v) to optimize x and y respectively. Under some regularity assumptions, gradient direction from a single perturbed point is adequate for proving convergence for (not strictly) convex-concan functions (Nedić & Ozdaglar, 2009). They can be easily extended to accommodate gradient based policy optimization and the stochastic RL. objective in Eq. 4.
We propose to find the perturbations from an agent population, resulting in the algorithm outlined in Alg. 1. The algorithm trains n pairs of agents simultaneously. At each rounds of training, we first n² pairwise competitions save sample complexity, we can use these rollouts to do one policy update as well. Then a simple adversarial rule (Eq. 3) is adopted in Alg. 16 to choose the opponents adaptively. The intuition is that of and uf are the most challenging opponents in the population for the current and yr.
the evaluation step (Alg. 1 L3),, costing n²mn trajectories. To
u arg max f(e) ((x..)). y). yECt,
un arg min f(x, v²). aECt
(3)
The perturbations w and uº always satisfy fa w 2 [(u v²"), since max f(x v) 2 fat2 v/t) 2 minzect, f(r,v/)) Then we run gradient descent on at with the perturbed of as opponent to minimize f( ) and run gradient ascent on y to maximize f(u v²²). Intuitively, the duality gap between min, max, f(z y) and max, min, fax y), approximated by f( ot) [',,,, v/"), is reduced, leading (x+, v/² to converge to the saddle point (equilibrium).
We build the candidate opponent sets in 1.5 of Alg. 1 simply the sanecurrennly-trainee n-agent pop- This is due to the following considerations. An alternative source of candidates is the fixed known agents such as rule-based agent, which may not be available in practice. Another source is the extragradient methods (Korpele- vich, 1976; Mertikopoulos al., 2019), where extra gradient steps are taken on y before optimizing x. The extragradient method can be thought of as local approximation to Eq. 3 with neigh- borhood opponent set, thus is related to our method. However, this method could be less efficient because the trajectory sample used in the extragradient steps is wasted as it does not contribute to actually optimizing y- Yet another source the past agents. This choice motivated by Fictitious play and ensures that the current learner always defeats past self. However, experiments, self-play with a random past agent may learn slower than our method. We expect all agents in the population in our algorithm to be strong, thus provide stronger learning signals.
ulation. Specifically, Ch. (uf yh and C*., = (a*..... ..k
shall see in the
Finally, we use Monte Carlo estimation to compute the values and gradients of f. In the classical game theory setting where the game dynamic and payoff are known, it is possible to compute the exact values and gradients of f. But in the model-free MARL setting, we have to collect roll-out trajectories to estimate both the function values through policy evaluation and gradients through
4

---

Under review as a conference paper at ICLR 2021
the Policy gradient theorem (Sutton & Barto, 2018). After collecting independent trajectories H1(, +()))))) we can estimate f(x, v) by
m
f(, v)
And given estimates (s, a; v) to the state-action value Q2 a;y) (assuming an MDP with y as fixed opponent of 2),, we construct an estimator for V, fz, 3) (and similarly for vud given Q2y by
T
v.l(z,))
V. n. T d(:.)).
(5)
CONVERGENCE ANALYSIS
We establish an asymptotic convergence result in the Monte Carlo policy gradient setting in Thm. for a variant of Alg. 1 under regularity assumptions. This variant sets 1 = and uses the vanilla SGD as the policy optimizer. We add stop criterion f( u²) f( v z e after Line with an accuracy parameter e. The full proof can be found in the appendix. Since the algorithm is symmetric between different pairs of agents the population, we drop the subscript for text clarity.
Assumption (A1). X, Y S Rd are compact sets. As a consequence, there exists D s. V21, X, |2|| x2I11 & D and Vy1, 322 E Y, 1 I. D. Assume C2 C are compact subsets of X and Y. Further, assume f: X X Y + I. is bounded convex-concave function.
Theorem (Convergence with exact gradients (Kallio & Ruszezynski, 1994)). Under AI, if a se- quence (x* .y²) + (., 9) A f(*", )²) f(u,, y²) + implies (&. ②) saddle point, Alg. (replacing estimates with true values) produces a sequence {(x* } convergent a saddle.
The above case with exact sub- gradients is easy since both f and f are deterministic. In RL setting, we construct estimates for fxr y) and v..f. v,,f with samples. Intuitively, when the samples are large enough, we can bound the deviation between the true values and estimates by concentration inequalities, then the proof outline similar to Kallio Ruszezynski (1994) also goes through.
Thm. 2 requires an extra assumption on the boundedness of Q and gradients. By showing the policy gradient estimates are approximate sub-/super-gradients gradients of f. we are able to prove that the output (x:" N of of Alg. is an approximate Nash equilibrium with high probability.
Assumption 2 (A2). The Q value extimation Q is unbiased and bounded by R, and the policy has bounded gradient ||V log no {o(a)))) I B.
Theorem 2 (Convergence with policy gradients). Under AI, A2, let sample size at step k be m& 2 R2 g2 Da log 82-x) and learning rate mhe = a + with O S a S 2, then with probability least (6)) the Monte Carlo version of Alg. I generates a sequence of points {sx ) convergent
Ω
Ey -e
-pprrxxiiieee equilibrium (σ. ū), that is Vr XX (x, O(1) f(z, () < f v) + O(e).
Discussion. The theorems require be convex in and concave in y. but not strictly, which is weaker assumption than Arrow et al. (1958). The purpose of this simple analysis is mainly a sanity check for correctness. It applies to the setting in Sec. 5.1 but not beyond, as the assumptions do not necessarily hold for neural networks. The sample size is chosen loosely as we are not aiming at a sharp finite sample complexity analysis. In practice, we can find suitable my (sample size) and yn (learning rates) by experimentation, and adopt a modern RI. algorithm with an advanced optimizer (c.g., PPO (Schulman et al., 2017) with RmsProp (Hinton et al.)) in place of the SGD updates.
5 EXPERIMENTS
We empirically evaluate algorithm in several games with distinct characteristics.
Compared methods. In Matrix games, compare naive mirror descent method, which is essentially Self-play with the latest agent, to verify convergence. In the rest of the environments, we compare the results from the following methods:
5

---

Under review as a conference paper at ICLR 2021
1. Self-play with the latest agent (Naive Mirror Descent). The learner always competes with the most recent agent. This is essentially the Gradient Descent Ascent method by Arrow- Suuwicz-Uzawa (Arrow et al., 1958) the naive mirror/allermating descent.
2. Self-play with the best past agent. The learner competes with the best historical agent main- tained. The new agent replaces the maintained agent if beats the existing one. This is the scheme in AlphaGo Zero and AlphaZero (Silver et al., 2017; 2018).
3. Self-play with a random past agent (Fictitious play). The learner competes against ran- domly sampled historical opponent. This is the scheme in OpenAl sumo (Bansal et al., 2017; Al-Shedivat et al., 2018). It is similar to Fictitious play (Brown, 1951) since uniformly ran- dom sampling is equivalent to historical average. However, Fictitious play only guarantees convergence of the average-iteral -terate but not the last-iterate agent.
4. OURS(n 2, 4, 6,...). This is our algorithm with a population of pairs of agents trained simultancously, with each other as candidate opponents. Implementation can be distributed.
Evaluation protocols. We mainly measure the strength of agents by the Elo scores (Elo, 1978). Pairwise competition results are gathered from a large tournament among all the checkpoint agents of all methods after training. Each competition has multiple matches account for randomness. The Elo scores are computed by logistic regression, as Elo assumes a logistic relationship P(A wins) + (dra()raw) = 1/(1 + 10 ). A 100 Elo difference corresponds to roughly 64% win-rate. The initial agent's Elo is calibrated to Another way to measure the strength to compute the average rewards (win-rates) against other agents. We also report average rewards in the appendix.
5.1 MATRIX GAMES
We verified the last-iterate convergence to Nash equilibrium in several classical two-player zero- sum matrix games. In comparison, the vanilla mirror descent/ascent is known to produce oscillating behaviors (Mertikopoulos al., 2019). Payoff matrices (for both players separated by comma), phase portraits, error curves, and our observations are shown in Tab. 1,2,3,4 and Fig. 1,2,3,4.
We studied two settings: (1) OURS(Exact Gradient), the full information setting, where the players know the payoff matrix and compute the exact gradients on action probabilities; (2) OURS(Policy Gradient), the reinforcement learning or bandit setting. where each player only receives the reward of its own action. The action probabilities were modeled by probability vector E A2. We estimated the gradient w.r.t p with REINFORCE estimator (Williams, 1992) with sample size m, = 1024, and applied ?i = 0.03 constant learning rate SGD with proximal projection onto 42. We trained = 4 agents jointly for Alg. and separately for the naive mirror descent under the same initialization.
5.2 GRID-WORLD SOCCER GAME
We conducted experiments in a grid-world soccer game. Similar games were adopted in Littman (1994) and He et al. (2016). Two players compete in a grid world, starting from random positions. The action space is {up, down, left, right, noop]. Once a player scores a goal, it gets positive reward 1.0, and the game ends. Up to T = 100 timesteps are allowed. The game ends with a draw if time runs out. The game has imperfect information, as the two players move simultaneously.
The policy and value functions were parameterized by simple one-layer networks, consisting of one-hot encoding layer and a linear layer that outputs the action logits and values. The logits are transformed into probabilities via softmax. We used Advantage Actor-Critic (A2C) (Mnih et al., 2016) with Generalized Advantage Estimation (Schulman et al., 2016) and RmsProp (Hinton et al.) as the base RL algorithm. The kept track of the per-agent number of trajectories (episodes) each algorithm used for fair comparison. Other ayper-parameters are listed in the appendix. All methods were run multiple times to calculate the confidence intervals.
were N = 50, = 10, my = 32 for Alg. 1. We
In Fig. 5, OURS(n = 2, 4, 6) all perform better than others, achieving higher Elo scores after experi- encing the same number of per-agent episodes. Other methods fail to beat the rule-based agent after 32000 episodes. Competing with a random past agent learns the slowest, suggesting that, though it may stabilize training and diversify behaviors (Bansal et al., 2017), the learning efficiency is not high because a large portion of samples is devoted to weak opponents. Within our method, the perfor- mance increases with larger n, suggesting a larger population may help find better perturbations.
5.3 GOMOKU BOARD GAME
We investigated the effectiveness in the Gomoku game, which is also known as Renju, Five-in-a-row. In our variant, two players place black or white stones on 9-by-9 board in turn. The player who

---

Under review as a conference paper at ICLR 2021
Game payoff matrix
Phase portraits and error curves
have Nitor Destree
(bac Gradimm
Grasked)
86
Heads
Tails
Heads
1,
Tails
1:10000
1,24000
Tab. 1: Matching Pennies, classical game where two players simultaneously turn their pennies heads or tails. the pennics match, Player 2 (Row) wins one penny from Player (Column); otherwise, Player wins. (Pa (head), P, (head)) (g. 1) is the unique Nash equilibrium with game value
20 46
Fig. 1: Matching Pennies. (Top) The phase por- traits. (Bottom) The squared Le distance the equilibrium. Four colors correspond the agents in the population with 4 initial points.
Heads
Tails
Heads
2, -2
0,0
Tails
-1,1 1 2, -2
Tab. 2: Skewed Matching Pennies.
E25
Syheoh
03 in K.an
351 33 525
Observation: the leftmost column of Fig. 1,2, the naive mirror descent does not converge point- wisely; Instead, it is trapped in a cyclic behav- ior. The trajectories of the probability of playing Heads orbit around the Nash, showing as circles in the phase portrait. On the other hand, method enjoys approximate last-iterate convergence with both exact and policy gradients.
Fig. Skewed Matching Pennies. The unique Nash equilibrium is (1' (heads), Py (heads) (3. () with value 0.8.
Rock
Paper
Scissors
Rock
0,0
-1,1
I,
Paper
1, 1,-1
0,0
- 1,
Scissors
1,,
1,
0,0
Tab. 3: Rock Paper Scissors.
Observation: Similar observations occur the Rock Paper Scissors game (Fig. 3). The naive method circles around the corresponding equi- librium points ( and ( while our method converges with diminishing error.
Fig. Rock Paper Scissors. (Top) Visualiza- tion Player I's strategies (ya) one of the agents in the population. (Down) The squared distance equilibrium.
a 1,
0.5. 0.5
1,
0.5, 0.5
Tah. 4: Extended Matching Pennies.
Observation: Our method has the benefit of pro- ducing diverse solutions when there exist multi- ple Nash equilibria. The solution for row player is r = (L) t), while any interpolation between (1 2. 0) and (0, 3 is equilibrium column strategy. Depending on initialization, agents in our method converges to different equilibria.
Fig. 4: Visualization of the row player's strate- gies. (Left) Exact gradient; (Right) Policy gra- dient. The dashed line represents possible equi- librium strategies. The four agents (in different colors) the population trained by our algo- rithm (n = 4) converge differently.

---

Under review as a conference paper at ICLR 2021
Selppi mi Selipiy
153
300
(day ra taiken
20
13
Oura (am
65 Fer cer.tertt ko-
2030 36930 3500s
25900 28003
400009
Epiooks
Fe-dgem Esleede
Fig. 5: Soccer Elo curves aver- aged over 3 runs (random seeds). For OURS(n), the average is over 3n agents. Horizontal lines show
Fig. 6: Gomoku Elo curves av- eraged over 10 runs for the hase- line methads, 6 runs (12 agents) for
Fig. 7: RoboSumo Ants Elo curves averaged over 4 runs for the base- line methods, 2 runs for OURS(n 4, 8). A close-up is also drawn for better viewing.
OuRS(n = 2), 4 runs (16 agents) for OURS(N = 4), and runs (18 agents) for OURS(n = 6).
the scores of the rule-based and the random-action agents.
" In all three figures, bars show the 95% confidence intervals. We compare per-agent sample efficiency.
gets an unbroken row of five horizontally, vertically, or diagonally, wins (reward 1). The game is a draw (reward 0) when no valid move remains. The game is sequential and has perfect information.
This experiment involved much more complex neural networks than before. We adopted 4- layer convolutional ReLU network (kernels (5, 5, 1). channels (16, 32, 64, 1), all strides 1) for both the policy and value networks. Gomoku is hard to train from scratch with pure model-free RL without explicit tree search. Hence, we pre-trained the policy nets on expert data collected from ren junfffll inne com. We downloaded roughly 130 thousand games and applied behav- ior cloning. The pre-trained networks were able to predict expert moves with R 41% accuracy and achieve average score of 0.93 (96% win and 4% lose) against a random-action player. We adopted the A2C (Mnih et al., 2016) with GAE (Schulman et al., 2016) and RmsProp (Hinton et al.) with learning rate T//- 0.001. Up to N 40 iterations of Alg. were run. The other hyperparameters were the same as those in the soccer game.
able to improve upon the behavior cloning policies significantly. OURS(n = 2, 4, 6) demonstrate higher sample efficiency by achieving higher Elo ratings than the alternatives given the same amount of per-agent experience. This again suggests that the opponents are chosen more wisely, resulting in better policy improvements. Lastly, the more complex policy and value functions (multi-layer CNN) do not seem to undermine the advantage of our approach.
In Fig. 6, all methods
5.4 ROBOSUMO ANTS
Our last experiment is based on the RoboSumo simulation environment Al-Shedivat et al. (2018) and Bansal et al. (2017), where two Ants wrestle in an arena. This setting is particularly relevant to practical robotics research, as we believe success in this simulation could be transferred into the real- world. The Ants move simultancously, trying to force the opponent out of the arena onto the floor. The physics simulator is MuJoCo (Todorov et al., 2012). The observation space and action space continuous. This game is challenging since it involves complex continuous control problem with sparse rewards. Following Al-Shedivat et al. (2018) and Bansal et al. (2017), we utilized PPO (Schulman et al., 2017) with GAE (Schulman et al., 2016) as the base RL algorithm, and used a 2-layer fully connected network with width 64 for function approximation. Hyper-parameters N 50, my 500. In Al-Shedivat al. (2018), random past opponent is sampled in self- play, corresponding to the "Self-play w/ random past" baseline here. The agents are initialized from imitating the pre-trained agents of Al-Shedivat et al. (2018). We considered our method. From Fig. 7, we observe again that OURS(N = 4, 8) outperform the baseline methods by a statistical margin and that our method benefits from a larger population size.
4 and n 8 for
6 CONCLUSION
We propose new algorithmic framework for competitive self-play policy optimization inspired by a perturbation subgradient method for saddle points. Our algorithm provably converges in convex- concave games and achieves better per-agent sample efficiency in several experiments. In the future, we hope to study a larger population size (should we have sufficient computing power) and the possibilities of model-based and off- off-policy self-play RL under our framework.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Maruan Al-Shedivat, Trapit Bansal, Yura Burda, Ilya Sutskever, Igor Mordatch, and Pieter Abbeel. Continuous adaptation via meta-learning in nonstationary and competitive environments. In In- ternational Conference on Learning Representations, 2018. 1, 6,
Kenneth Joseph Arrow, Hirofumi Azawa, Leonid Hurwicz, and Hirofumi Uzawa. Studies in linear and non-linear programming, volume 2. Stanford University Press, 1958. 2, 5,
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. arXiv preprint arXiv:2002.044017, 2020.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. In International Conference Learning Representations, 2020.
Trapit Bansal, Jakub Pachocki, Szymon Sidor, Ilya Sutskever, and Igor Mordatch. Emergent com- plexity via multi-agent competition. ICLR, 2017. 1, 6,8,8
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, al. Dota 2 with large scale deep reinforcement learning. arXiv preprint 1rXiv:1912.0660 2019.
Michael Bowling and Manuela Veloso. Multiagent learning using variable learning rate. Artificial Intelligence, 136(2):215-250, 2002. 2
George W Brown. Iterative solution of games by fictitious play. Activity analysis of production and
allocation, 13(1):374-376, 1951. 2,
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885-890, 2019. 1,2
Adrian Rivera Cardoso, Jacob Abernethy, He Wang, and Huan Xu. Competing against nash equilib- ria in adversarially changing zero-sum games. In International Conference on Machine Learning, pp. 921-930, 2019.
Arpad Elo. The rating of chessplayers, past and present. Arco Pub., 1978. 6
Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell. Adver- sarial policies: Attacking deep reinforcement learning. In International Conference on Learning Representations, 2019. 3
dean-Bastien Grill, Florent Altché, Yunhao Tang.
Thomas Hubert, Michal Valko, Ioannis Antonoglou, and Rémi Munos. Monte-carlo tree search as regularized policy optimization. ICML, 2020. 3
Jihun Hamm and Yung- Noh. K-beam minimax: Efficient optimization for deep adversarial learning. ICML, 2018.
He He, Jordan Boyd-Graber, Kevin Kwok, and Hal Daumé III. Opponent modeling in deep rein- forcement learning. ICML, 2016.
Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfect- information games. /rXiv:/603.011
2016. 2,
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6a overview of mini-batch gradient descent. 5, 6,
Junling Hu and Michael P Wellman. Nash q-learning for general-sum stochastic games. JMLR, 1039 2003.
M Jaderberg. WM Czarnecki. I Dunning, Marris, G Lever, AG Castaneda, C Beattie, NC Rabi- nowitz, AS Morcos, Ruderman, et al. Human-level performance in multiplayer games with population-based reinforcement learning. Science, 364(6443):859-$666 2019.

---

Under review as a conference paper at ICLR 2021
Amir Jafari, Amy Greenwald, David Gondek, and Gunes Ercal. On no-regret learning, fictitious play, and nash equilibrium. ICML, 2001. 2,3
MJ Kallio and Andrzej Ruszczynski. Perturbation methods for saddle point computation. 1994. 2, 3, 4, 5, 16
GM Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976. 2, 3,4
Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach multiagent rein- forcement learning. In Advances in neural information processing systems, pp. 4190-4203, 2017.
Chung Wei Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Linear aas-iterate convergence for matrix games and stochastic games. arXiv preprint 1rXiv:2006.09517, 2020. 2
Michael L Littman. Markov games as framework for multi-agent reinforcement learning. In
Machine Learning, pp. 157-163. Elsevier, 1994. 2,
Siqi Liu, Guy Lever, Josh Merel, Saran Tunyasuvunakool, Nicolas Heess, and Thore Graepel. Emer- gent coordination through competition. ICLR, 2019.
Panayotis Mertikopoulos, Houssam Zenati, Bruno Lecouat, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent saddle-point problems: Going the extra (gradient) mile. ICLR, 2019. 3, 4,
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In JCML, pp.
2016. 6,
John Nash. Non-cooperative games. Annals mathematics, pp. 286-295, 1951. 2
Angelia Nedić and Asuman Ozdaglar. Subgradient methods for saddle-point problems. Journal of optimization theory and applications, 2009. 2, 3,4
Ann Nowé, Peter Vrancx, and Yann-Michaël De Hauwere, Game theory and multi-agent reinforce- ment learning. Reinforcement Learning, pp. 441, 2012. 2
Manish Prajapat, Kamyar Azizzadenesheli, Alexander Liniger, Yisong Yue, and Anima Anandku- mar. Competitive policy optimization. arXiv preprint arXiv:2006. 106/1, 2020.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable se- quences. In Advances in Neural Information Processing Systems, pp. 3066-3074, 2013.
John Schulman, Philipp Moritz, Sergey Levine, et High-dimensional continuous control using generalized advantage estimation. ICLR, 2016. 8
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 1tXXi:1707.0634477 2017,
Lloyd S Shapley. Stochastic games. PNAS, 39(10):1095-1100 1953.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwiesser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. Nature, 529(7587):484, 2016. 1, 2,
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):354, 2017. 1,
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self- Science, 362(6419): 140- 1144, 2018.
10

---

Under review as a conference paper at ICLR 2021
Satinder Singh, Michael Kearns, and Yishay Mansour, Nash convergence of gradient dynamics in general-sum games. UAI, 2000.
Richard Sutton and Andrew Barto. reinforcement learning: an introduction. MIT press, 2018. 2, 5
Gerald Tesauro. Temporal difference learning and td-gammon. Communications of the ACM, 38(3): 58 58-68, 1995.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine model-based control. In 2012 IEEE/RSJ International Conference Intelligent Robots and Systems, pp. 5026-5033. IEEE, 2012.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350-354, 2019.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-255 1992. 6
Kaiqing Zhang, Sham M Kakade, Tamer Başar, and Lin F Yang. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. arXiv preprint arXiv:2007.07461, 2020. 2
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In Advances in neural information processing systems, pp. 1736, 2008. 2,

---

Under review as a conference paper at ICLR 2021
A EXPERIMENT DETAILS
A.1 ILLUSTRATIONS OF THE GAMES IN THE EXPERIMENTS
Illustration
Properties
Fig. 8: Illustration of the 6x9 grid-world soccer game. Red and blue represent the two teams A and B. At start, the players are initialized random positions on re- spective sides, and the ball is randomly assigned to one team. Players move up, down, left and right. Once a player scores goal, the corresponding team wins and the game ends. One player can intercept the other's ball by crossing the other player.
Observation space:
Tensor of shape [5.], (I UA TB, yB, has ball)
Action space: (up, down, left, right, noop) Time limit:
50 moves
Terminal reward:
+1 for winning team
1 for losing team
timeout
Fig. 9: Illustration of the Gomoku game (also known Renju, five-in-a-row). We study the 9x9 board variant. Two players sequentially place black and white stones on the board. Black goes first. A player wins when he or she gets five stones row. In the case of this illustration, the black wins because there five consecu- tive black stones in the 5th row. Numbers the stones indicate the ordered they are placed.
Observation space:
Tensor of shape 19,9.3]. last dim O: vacant, 1:
black, 2: white
Action space:
Any valid location on the
9x9 board
Time limit:
41 moves per-player
Terminal reward:
+1 for winning player
for losing player
0 if timeout
Fig. 10: Illustration of the RoboSumo Ants game. Two ants fight in the arena. The goal is to push the opponent or down to the floor. Agent positions are initialized be random at the start of the game. The game ends in draw if the time limit is reached. In addition the terminal +1 reward, the environment comes with shaping rewards (motion bonus, closeness opponent, etc.). In order make the game zero-sum, we take the difference be- tween the original rewards of the two ants.
of the arena
Observation space: R
Action space: R
Time limit:
100 moves
Reward:
r2 rt prggy r
Terminal +1 or 0.
A.2 HYPER-PARAMETERS
The hyper-parameters in different games are listed in Tab. 5.
A.3 ADDITIONAL RESULTS
Win-rates (or average rewards). Here we report additional results in terms of the average win- rates, or equivalently the average rewards through the linear transform win-rate = 0.5 + 0.5 reward, agent, the values are the average of f(z :)
in Tab. 6 and 7. Since treat each (z). 9:) pair and f(: yi) in the first table. The one-side f(- y:) win-rates are in the second table. Mean and 95% confidence intervals estimated from multiple runs. Exact numbers of runs are in the captions
12

---

Under review as a conference paper at ICLR 2021
Tab. 5: flyper-arammeter..
Hyper-param Game
Soceer
Gomoku
RoboSumo
Num. of iterations
50
40
50
0 + 0.001 in first
Learning rate 7/k
0.1
3e-5 + 0 linearly
steps then 0.001
Value func learning rate
(Same as above.)
(Same as above.)
9e-5
Sample size my Num. of inner updates /
32
32
500
10
10
10
Env. time limit
50
41 per-player
100
PPO, clip 0.2, mini- batch 512, epochs 3
Base RL algorithm
A2C
A2C
Optimizer
RmsProp, a = 0.99
RmsProp, = 0.99
RmsProp. a = 0.99
Max gradient norm
1.0
1.0
0.1
GAE À parameter
0.95
0.95
0.98
Discounting factor 7
0.97
0.97
0.995
Entropy bonus coef.
0.01
0.01
0
Sequential
Sequential
[mnear[1206644
Conv|c16.k5,p2),
TanH,
ReLU,
Linear[64464J,,
Sequential
Conv[c32,k5,p2),
TanH,
(5eH2)[5832),
ReLU,
Linear[64,8),
Policy function
Linear[5832.5),
Conv|c64.k3.pl),
TanH.
Softmax,
ReL.U,
GaussianDist
CategoricalDisst
Conv[e1.k1]
Tanh ensures the mean of the Gaussian is be- tween and 1. The density is corrected.
Spatial Softmax,
CategoricalDist
Sequential Linear[120.64] 120,64],
Share Conv layers with the policy, but additional heads: global average and Linear[64,1]
Sequential OncHor[5832).
TanH, Linear[64464J],
Value function
Linear[5832,1]]
TanH, Linear[64,1]]
13

---

Under review as a conference paper at ICLR 2021
of Fig. 5,6,7 of the main paper. The message is the same as that suggested by the Elo scores: Our method consistently produces stronger agents. We hope the win-rates may give better intuition about the relative performance of different methods.
Tab. 6: Average win-rates (E [o, 1D between the last-iterate (final) agents trained by different algo- rithms. Last two rows further show the average over other last-iterate agents and all other agents (historical checkpoint) included in the tournament, respectively. Since an agent consists of an (z. y)
pair, the win-rate is averaged on and y, i.e. win(col vs row) = f(="m "-(-(((am xd 0.5 0.5.
2
The lower the better within each column; The higher the better within each row.
Soccer Self-play rand
Soccer
Self-play latest
Self-play best
Ours (n=2)
Ours (nm4)
Ours (nmb)
Self play latesi
0.533 1 0.044
0.382 1 0.082
0.662 1 0.054
0.691 1 0.029
0.713 0.032
Self-play best
0.467 0.044
0,293 0.059
0.582 + 0.042
0.618 + 0.031
0.661 0.03
Self play rand
0.618 1: 0.082
0.707 1 0.059
0.808 1 0.039
0.838 1 0.028
0.844 1: 0.043
(n=2)
0.338 0.054
0.418
0.042
0.192 4 0.039
0.549 + 0.022
0.535 0.022
Ours (n=4)
0.309 + 0.029
0.382 = 0.031
0.162 = 0.028
0.451
0.022
0.495 + 0.023
Ours (n=6)
0.287 0.032
0.339 = 0.030
0.156 + 0.043
0.465
0.022
0.505 + 0.023
Last-lter average
0.357 0.028
0.428
0.028
0.202
0.023
0.632
0.023
0.608 + 0.018
0.385 + 0.022
Overall averuge
0.632 1. 0.017
0.676 1 0.014
0.506 1: 0.020
0.749 1. 0.009
0.775 1. 0.006
0.776 1. 0.008
(b) Gomoku
Gomoku
Self-play latest
Self-play
Self-play rand
Ours (n=2)
Ours (n=4)
Ours (n=6)
Salf-play latest
0.523 = 0.026
0.402 0.032
0.551 0.022
0.371 = 0.018
0.376 +
Self-play best
0.477 + 0.026
0.433 = 0.031
0.532 + 0.024
0,551 + 0.018
0.560 + 0.020
peaf-play rand
0.538 1: 0.032
0.567
0.599
1: 0.022
0.638
Ours (n=2)
0.449 +: 0.024
0.468 + 0.024
0.401 + 0.027
0.528 + 0.015
0.545 + 0.017
Ours (n=4)
0.429 0.018
0.449
0.018
0.412 - 0.022
0.472 0.015
0.512 0.013
Ours (n=6)
0.421 0.017
0.410
= 0.020
0.362
0.020
0.455 + 0.017
0.488 + 0.013
Last-iter average
0.455 1 0.010
0.479
= 0.011
0.4
= 0.012
0.509
+ 0.010
0,337
1 0.008
0.560 E 0.008
Overall average
0.541 0.004
0.561
0.004
0.499 1: 0.005
0.583 0.004
0.599
1 0.003
0.615 0.003
RoboSumo
RoboSurno
Selt-play latest
Self-play
best
Self-play rand
Ours (m=4)
Ours (n=8)
Self-play lntest
0.502 = 0.012
0.493 = 0.013
0.511 + 0.011
0.510 + 0.010
Self-play best
0.498 0.012
0.506 0.011
0.514 + 0.008
0.512
Self Seaf-play rand
0.507 1: 0.013
0.494 = 0.014
0.508
1 0.011
0.515 1: 0.011
Ours (n=4)
0.489 0.011
0.486
0.008
0.492
0.011
0.516 0.008
Ours (nm8)
0.490 + 0.010
0.488
0.010
0.485
0.011
0.484 + 0.008
Last-iter average
0.191 + 0.006
0.191
= 0.003
0.192
= 0.006
0.500 + 0.005
0.514 0.005 0.006
Overall average
0.531 0.004
0.004
0.530
0.004
+ 0.003
0.545
0.003
Training time. Thanks the easiness of parallelization, the proposed algorithm enjoys good seal- ability. We can either distribute the n agents into n processes to run concurrently, or make the roll- outs parallel. Our implementation took the later approach. In the most consuminnn RoboSumo Ants experiment, with 30 Intel Xeon CPUs, the baseline methods took approximately 2.4h, while Ours (n=4) took 10.83h to train (x4.5 times), and Ours (n=8) took 20.75h (x8.6 6 times). Note that, Ours (n) trains agents simultaneously. If we train agents with the baseline methods by repeating the experiment n times, the time would be 2.4n hours, which is comparable to Ours (n).
Chance of selecting the agent itself as opponent. One big difference between our method and the compared baselines is the ability to select opponents adversarially from the population. Consider the agent pair (I,, v.). When training x,, our method finds the strongest opponent (that incurs the largest loss on I.2) from the population, whereas the baselines always choose (possibly past versions of) yi- Since the candidate set contains yr, the "fall-back" case is to use y/ as opponent in our method. We report the frequency that y chosen as opponent for x; (and x; for y likewise). This gives a sense of how often our method falls back to the baseline method. From Tab. 8, we can observe that, as n grows larger, the chance of fall-back is decreased. This is understandable since a larger population means larger candidate sets and larger chance to find good perturbations.
B PROOFS
We adopt the following variant of Alg. in our asymptotic convergence analysis. For clarity, we investigate the learning process of one agent in the population and drop the i index. C and Cjty
14

---

Under review as a conference paper at ICLR 2021
Tab. 7: Average one-sided win-rates (E 00, 1)) between the last-iterate (final) agents trained by different algorithms. The win-rate is one-sided, i.e., win vs x: x="") f(="" y x 0.5 + 0.5.
The lower the better within each column; The higher the better within each row.
(a) Soccer
row at \
Selt-play
Self-play
Self-play rand
Ours (n=2)
Ours (nm4)
Ours (0m6)
Self play latest
0.536 1 0.054
0.564 1 0.079
0.378 1 0.103
0.674 1 0.080
0.728 1 0.039
0.733 0.048
Self-play best
0.497 + 0.065
0.450 + 0.064
0.306 + 0.106
0.583 0.056
0.601 + 0.039
0.642 + 0.050
Self-play rand
0.614 0.163
0.719
0.090
0.481 0.102
0.796
0.0071
0.816 + 0.039
0.821
Ours (n=2)
0.350 + 0.051
0.419 = 0.037
0.181 : 0.049
0.451 - 0.037
0.525 + 0.031
0.553 + 0.034
(m=4)
0.346
0.365
0.047
0.033
1
0.494 0.033
Ours (n=6)
0.308 0.042
0.319 = 0.052
0.136 + 0.050
0.483
0.043
0.505 + 0.030
0.515 + 0.032
Last-iter average
0.351 + 0.033
0.422 = 0.036
0.188 = 0.028
0.625
- 0.029
0.601
+ 0.021
0.587 + 0.026
Overall average
0.651 0.017
0.665 0.016
0.502 0.021
0.745
0.010
0.771 0.006
0.775 0.009
Gomoku
row at col
Self-play latest
Self-play best
Self-play rand
Ours (n=2)
Ours (n=4)
Ours (nmb)
Self play latest
0.481 1: 0.031
0.540 1 0.038
0.488 1 0.050
0.594 1. 0.041
0.571 1: 0.026
0.586 0.030
Self-play best
0.494 +: 0.033
0.531 0.030
0.471 0.049
0.597 0.040
0.562 + 0.024
0.572 +: 0.028
Self-play rand
0.565
0.036
0.605 = 0.036
0.572 = 0.051
0.668 0.040
0.617 + 0.027
0.617 + 0.029
(m=2)
0.491
0.568
0.552 0.025
Ours (n=4)
0.428 = 0.022
0.461 = 0.024
0.440 = 0.035
0.515 0.002
0.491 + 0.017
0.503 + 0.020
Ours (n=6)
0.435 0.021
0.453 = 0.026
0.370 + 0.028
0.462 0.005
0.479 + 0.018
0.467 0.017
Last-iter average
0.472 1 0.012
0.506 0.014
0.438
0.017
0.649 0.001
0.330
+ 0.011
0.364
0.012
Overall average
0.548 + 0.005
0.585 = 0.005
0.536 = 0.007
0.631 + 0.006
0.608 + 0.001
0.617 + 0.001
(c) RobeSumo
mw at \ y
Self-play latest
Self.play best
Self-play rand
Ours (n=4)
(n=S)
Self play latest
0.516 1 0.022
0.494
0.020
0.491
0.023
0.502
1 0.017
0.511
0.016
Self-play hest
0.480 -: 0.018
0.504 = 0.023
0.503
0.022
0.506 + 0.014
0 0.014
Self rund
0.505 0.001
0.494
0.026
1: 0.017
0.016
Ours (n=4)
0.480 0.018
0.479 = 0.012
0.502 1 0.016
0.496
1 0.009
0.517
(n=8)
0.491 + 0.012
0.484 = 0.016
0.485
0.016
0.486
+ 0.012
0.491
Last iter average
0.489 0.008
0.485 0.008
0.495
0.009
0.500
1 0.007
0.514 0.007
Overall average
0.528 + 0.004
0.521 0.004
0.530 + 0.005
0.534
+ 0.003
0.544 + 0.003
Tab. 8: Average frequency of using the agent itself opponent, in the Soccer and Gomoku exper- iments. The frequency is calculated by counting over all agents and iterations. The + shows the standard deviations estimated by runs with different random seeds.
Method
Ours (n = 2)
Ours (n 4)
Ours (n 6)
Frequency of self (Soccer)
0.4983 0.0085
0.2533 0.0072
0.1650 + 0.0082
Frequency of self (Gomoku)
0.5063 + 0.0153
0.2312 + 0.0111
0.1549 + 0.0103
not set simply the population for the sake of the proof. Alternatively, we pose some assumptions. Setting them to the population as in the main text may approximately satisfy the assumptions.
Algorithm 2: Simplified perturbation- self-play policy optimization of one agent.
Input: 7): learning rates, my: sample size;
Result: Pair of policies (I,
Initialize æ² x²;
for k 0, L,..... do
Construct candidate opponent sets Oj and Cl; Find perturbed * = arg yax f(a", y) and perturbed u² arg min, f(x,8*) where the evaluation is done with Fq. 4 and sample size Compute estimated duality gap Es f(a* x flu" "
if EA 3c then return (a*.y")
Estimate policy gradients g² = Va v² and Ot = Vas(u" (u", )²²) w/ Eg. 5 and sample size my; Update policy parameters with x t x² nag and y c+1 + 2² + n:0s;
B. PROOF OF THEOREM 1
We restate the assumptions and the theorem here clearly for reference.
15

---

Under review as a conference paper at ICLR 2021
Assumption B.1. X,Y Rd (d > 1) compact sets. As consequence, there exists D 1, s.C.,
10 22 X, | æ2l11 S D and Vyn 1/2 E YY, 11y1 y2ll1 S D.
Further, assume f: X x Y + R is bounded convex-concuve function.
Assumption B.2. C C5 compact subsets of X and Y. Assume that sequence (x*, 3²) (2,9) () f(a", - f(u", (()
for some e* E Cy and u² E C implies (#. 9) is saddle point. Theorem (Convergence with exact gradients (Kallio & Ruszczynski, 1994)). Under As- sump. B.2, let the learning rate satisfies
E
1
19
Alg. 2 (when replacing all estimates with true values) produces a sequence of points {(a*, } convergent saddle point.
Assump. B.1 is standard, which is true is based on payoff table and X, Y are probability simplex as in matrix games, or if f is quadratic and X, Y are unit-norm vectors. Assump. B.2 about the regularity of the candidate opponent sets. This true if Cyy, Cf are compact and f( e²) f(u", v²) = 0 only at saddle point (u²,"*) E C x C. An trivial example would be Ct = = C,C Y. Another example would be the proximal regions around x* y² In practice, Alg. constructs the candidate sets from the population which needs to adequately large and diverse to satisfy Assump. B.2 approximately.
The proof is due to (Kallio & Ruszczynski, 1994), which we paraphrase here.
Proof. We shall prove that one iteration of Alg. 2 decreases the distance between the current (x* yy*) and the optimal (x",²"). Expand the squared distance.
| x²12 < 1 + Thg x= 2
1|
-x11=
2
21p (o- a x²) + m 19.1
(6)
From Assump. B.I, convexity of [(x, v) on gives
(g th xx) 2 f(x" f(x" ,()
which yields
| k+1 1²1 2 < 1|+²* x²112 1 2me (f*t) - f(x" x²)) n
(8)
Similarly for y concavity of f(x v) on gives
1y h+1 11 < 11a/ - y 11² + 2np ( (f("", 3/ +
(9)
Sum the two and notice the saddle point condition implies
f(x", < f(x",'l''" 3²) S f(u,,"'
(10)
we have
Wa+1 == 1x k++ 112 + 11y - 1112
< 1|a - =1111 + 111"* - 1²1
(11)
21j (s(a*, x - f(x" ,² s(u ((",,") f(u2 (a))))))) + (1lgt) lla5(12)
211z Ex + 212 [1 + 11))
If the learning rate satisfies 7 E, = Since W, is bounded below by O, therefore E₁ - 0. Following from Assump. B.2, the convergent point limg-zoe (IR. yk (x* )²) is saddle point.
E.
++115|11 the sequence { Joc is strictly decreasing unless
16

---

Under review as a conference paper at ICLR 2021
B.2 PROOF OF THEOREM 2
We restate the additional Assump. B.3 and the theorem here for reference. Assump. B.2 is replaced by the following approximated version B.4.
Assumption B.3. The total return is bounded by R, i.e., YEr I R. The Q value es- timator Q is unbiased and bounded by R (QQ R). And the policy has bounded gradient max ( V log ne (a sool } s B in terms of Loo norm.
Assumption B.4. Cy. C are compact subsets of and Assume iteration k for some (f; 0)
X x
V(u E C C y f(u, 0) - f(s, 0) - f(t, te
implies
EXYY, f(u. - S f(ä, 0) E f(0, v) t
namely, (#; () is an e-approximate saddle point.
Theorem 2 (Convergence with policy gradients). Under Assump. B.I,B.3,B.4, let sample size at step k be
D2
2d 82-k
m
e²
log
and, with 0 S a S.2, 2, let the learning rate
Ex 2
11 1
Then with probability at least 1 - O6)), the Monte Carlo version of Alg. 2 generates sequence of points (x 1y*) } j== convergent to an O -uprroximmt equilibrium (ž. 1). That is
X
f(x, OEe) s f(z S (α. + O(e).
In the stochastic game (or reinforcement learning) setting, construct estimates for f y) (Eq. 4) and policy gradients VaJ,, v,J (Eq. 5) with samples. Intuitively speaking, when the samples are large enough, can bound the deviation between the values and the estimates by concentration inequalities, then the similar proof outline also goes through.
Let us first define the concept of e-subgradient for convex functions and e-supergradient for concave functions. Then we calculate how many samples are needed for accurate gradient estimation in Lemma 3 with high probability. With Lemma gradient estimates are good enough to be e-subgradients when sample size is large in Lemma 4.
will be able to show that the Monte Carlo policy
Definition 1. An e-subgradient of a convex function h : 12 + at is g E Rdd that satisfies
x' - x) c. Væ', h(x') hxx) 2 (9
Similarly, e-supergradient of concave function h Rd R a is
Bd that satisfies
Vz', h((') - h(z) < (g. x' - x) te. Lemma 3 (Policy gradient sample size). Consider y alone and treat the problem as MDP. Suppose Assump. B.3 is satisfied. Then with independently collected
B2
2d
log
2
8
trajectories ((s), a, ) the policy gradient estimate
m Σ
1
v Vog
log To (at
is c-close the true gradient V with high probability, namely.
Pr (
Vb <)) 1
Proof. It directly follows from Hoeffding's 's inequality and the union bound, since the range of each sample point is bounded by RB and by the policy gradient theorem EVj Vf.
n
17

---

Under review as a conference paper at ICLR 2021
Lemma 4 (Policy gradients are sub-/super- gradients). Under Assump. B.I, the policy gradient estimate ,ff in Lemma is an eD-subgradien of a, i.e for all x' E X,
f f(x,V) 2 (Val. x) -cD
with probability 2 1 - 6. (And vf is e +D-suppr-grrddent for y.)
Proof. Apply the telescoping trick,
(V - x) = (V.f Vaf V.f. -x)
(VzJ,e' (Va) Vaf,a' 2 f + V Vef. x' x).
(12)
With the sample size in Lemma 3, we know it holds that max, V f Vzfli S with probability Hence, by Holder's inequality, the last part satisfies
V V v -x) (V - V..1. i' =)) 2 - V../loollee - x111 2 -eD. (13)
The proof vyf being -ussuper-grddient for y is similar, hence omitted.
Similarly for accurate function value evaluation, we have the following lemma on sample size, which directly follows from Hoeffding's inequality.
Lemma (Evaluation sample size). Suppose Assump. B.3 holds. Then with independently collected m
m Σi, I' Fe is e-close to the true gradient f with high probability, namely, Pr (1lf flloo 5) 2 8.
2R log & trajectories { ai rf)) the value estimate f 1
Now we prove our main theorem which guarantees the output of Alg. is an approximate Nash with high probability. This is done by using Lemma 4 in place of the exact convexity condition to analyze the relationship between Wa and Wk+1, using Lemma bound the error of policy evaluation, and analyzing the stop condition carefully.
Proof. (Theorem 2.)
Suppose (x": y²" is one saddle point of We shall prove that one iteration of Alg. 2 sufficiently decreases the squared distance between the current (x* 3²* and (x",y") defined Wi == 1| x² 12112 + l|y - 112.
Relation between We and WK+17 Note that
W = || 1+1 112
I|a* na. x²1 11 x²112 27 (g x -x") + 11 (14)
By Lemma the gradient estimate oft with sample size my is an e-subgradient on with probability at least 1 5/2*.. i.e.,
(g x x²) 2 , f(x", x²
(15)
Plugging back into Eq. 14, get
|1x xx 112 I|a
x01 27 (slat, (0)) 5(x" (0)) + n1llot11?
(16)
Similarly for , since gf: is a super-gradient by Lemma 4,
| k+1 1 lIv 1² 2m (s(u* 5² (s("*, Su .x) + +c) + 1
11
(17)
Sum the two inequalities above, and notice the saddle point condition implies
f(x ) ) < f(x", ,v²) S (u*tv"")
18

---

Under review as a conference paper at ICLR 2021
have the following inequality holds with probability --29% -20/2*,
Wk+1
|| x²11 11 v²11
- 1| x=11 + 11y* y²11
(18)
27 2m (f(x r²t) - =fxx", ,0)) - f(u², ,, y²) + f(u "("",)")) 26) + (1l + +1s < W/ - 21) 26) + nhe (11 + | 1²)
Accurate estimation of Ex: In Eq. 18, the second term involves Eg which is unknown to the algorithm. Recall that (u o²) = f(**, v²) f(u", y²) and the empirical estimate Ex = fa² ,²t) - f(u", ,y") in Alg. 2 Line 5.
By Lemma 5, when the sample size my is chosen as in Theorem 2, with probability 28
a2c
1f(x", 5(x", x0)) 1
BD S
and
f(u",00) - f(u8, ,0,,
" $
Sc.
BD
Thus Eg is 2e-accurate because
Ex - 2c = f(xl/(l" 14) - c f-u" ,,,, - = Es
(19)
S f(a wh
f(u v²² kB + 2c.
Case (I). Stop condition in Alg. 2 Line 6: If there does exist (u, C O such that
Ex (u, v) > 3c, meaning v(u,o) v) E C x Cy.y Eg I 3c. We can conclude
E f( v) f(u, )* Ex 3c 5c
(20)
with probability at least
d2
2
Set v = x and u = x respectively the above inequality, we obtain v(u, v) E C+ x Ctty
f(u, /²t) 5c < f(x", 3²) S f(x". u) + 5c.
(21)
Following from Assump. B.4, this implies Yuu, v) E X xXY, fu. y²) 5c 5e f(x ,/0) S ,1) 5e, which suggests (z% x is an approximate saddle point (equilibrium).
+))+
On the other hand, we want to bound the failure probability. Define events
F(g) == "Ig gl I c true"
for g [s2. P2. f(= v),, fu 88) ot. f( )² ... }. By De Morgan's law and the union bound.
Pr all MC estimates till step are accurate) ]
k
= Pr iN F( n F()))) n F(f(d F(F
1=0
1 Pr
F(g..) n.. F(f(u(.v))
(22)
1=1
2 1 O
2
1=0
2 1 - (8))
This means that inaccurate MC estimation (failure) occurs with small probability O()). The purpose of the increasing m& w.r.t. lo is to handle the union bound and the geometric series here. So, when the algorithm stops, returns (z. 7) = (æx, yk) as a 5e-approximate solution to the saddle point (equilibrium) with high probability.
19

---

Under review as a conference paper at ICLR 2021
Case (2). Sufficient decrease of Wa: Otherwise, if the stop condition is not triggered, have
picked u² of such that Fg > 3c. With probability 1 - 26, Ex > Fgx 2c 2 With the chosen
learning rate 7) in the theorem statement, Wx strictly decreases by at least
a a)c² 18
a a))²
W Wk+1
> 0.
(23)
1 2
BR
Since WR is bounded below by O, by the monotone convergence theorem, there exists a finite such that Wo I h a and no (u, v) can be found to decrease W₁ more than 3c. In this case, V(u,e) v) E C x Cg Es (u, S 3e, which is exactly the stop condition in Case (1). This means the algorithm will eventually stop, and the proof is complete.
2
Remark The sample size chosen very loosely. More efficient ways to find perturbations (e.g.- best-arm identification), to better characterize or cover the policy class and to better utilize trajec- tories (e.g., especially off-policy evaluation w/ importance sampling) can potentially reduce sample complexity. In practice, we found on-policy methods which do not reuse past experience such as A2C and PPO work well enough.
Remark Assump. B.4 is rather strong assumption on the candidate opponent sets. In theory, we can construct an e-covering of to satisfy the assumption. In practice, in population-bas bbased training of Alg. 1, this assumption can be roughly met if n is large or diverse enough. We found relatively small population with randomly initialized agents already brought noticeable benefit.
Remark The proof requires a variable learning rate 77k- However, the intuition that the learning rate needs to be small, did in experiments.
20


Reviews:
[{"review_id": "SWZ6QotRgkq", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors present a rule for selecting opponents for self-play training in zero-sum games: Train each agent i against the agent j that is \"hardest\" for i (in the sense that i's payoff is least among all candidate opponents when playing against j).  This principle is justified by appeal to \"perturbation-based subgradient methods\" in saddle-point optimization.  Last-iterate (as opposed to average-iterate) convergence to equilibrium is demonstrated both analytically and experimentally.\n\nThe evaluation is very thorough.  The empirical baselines are appropriately chosen.  The principled grounding of the selection procedure in saddle-point optimization was especially interesting, as I have not encountered that corner of optimization before.  The exposition is clearly written and well organized.\n\nI have somewhat mixed feelings about this paper.  On the one hand, it's hard to believe that \"train against the toughest opponent\" as a selection rule has never been tried before.  On the other hand, the argument for the method is extremely convincing.  Overall I am in favor of acceptance. \n\nIt would be valuable for the authors to explicitly highlight the novel aspects of their contribution compared to [Balduzzi et al 2019], \"Open-ended Learning in Symmetric Zero-sum Games\", which rejects the \"play against toughest (for me) opponent\" approach explicitly because it collapses to equilibrium play.  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NsA2U2MdX1c", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors study the problem of optimization in two-player competitive zero-sum sequential games where the objective function is convex-concave in players' strategies. They relax the convex-concave assumption for the empirical study.\n\nThis problem is an important and challenging problem in the field of reinforcement learning.\n\nThe authors propose a policy gradient-based method and argue that it converges to the game's Nash equilibrium. They also conduct a series of empirical studies to show the significance of their method. \n\nWhile this is a challenging problem, my judgment is that the paper is not ready for publication yet.\n\n1) The presentation of theorem 1:\nThe authors state that if \"a sequence of (x^k,y^k)->(xhat,yhat) \\wedge f(x^k,y^k) -f(u^k,y^k)-> 0 implies (xhat,yhat) is a saddle point\". \nI am not sure I follow this sentence. \n1-a) First, please clear up the notation when you use \\wedge. For example, say ((x^k,y^k)->(xhat,yhat)) \\wedge (f(x^k,y^k) -f(u^k,y^k)-> 0) since \\wedge someitmes also means minimum. \n1-b) In thm1, do the authors mean \nif \"a\" sequence (x^k,y^k) for k>0, satisfies the following conditions ((x^k,y^k)->(xhat,yhat)) and (f(x^k,y^k) -f(u^k,y^k)-> 0), then (xhat,yhat) is a saddle point?\nIf that is the case, please consider rewording the thm1. \nAlso, if that is the case, for what \\nu^k and u^k?\n\n1-c) Algorithm 1 seems to produce a sequence of sets rather than (x^k,y^k). Please clarify it in your theorem.\n\n1-d) If \\nu^k and u^k are some quantities that are produced by your algorithm, then the theorem seems not to be well-stated. Because I am not sure what sequence of \\nu^k and u^k the algorithm produces in order for me to see what space of X and Y you are dealing with. \n\n1-e) I see the same lack of clarity in the proof of thm1. \n\n2) In assumption 1, you state that the sets C_x^k and C_y^k are compact subsets of X and Y. However, these are what your algorithm produces. So probably, you may want to design your algorithm such it guarantees such a requirement. \n\n3) E_k seems to be not defined. \n\nAs the authors stated, the main contribution of this paper is not the theory. And the theoretical study in this paper is to motivate their algorithm.\n4) Empirical study. \nI found the empirical study in this paper, somewhat not convincing. \nIf the contribution is empirical, it would be useful to compare it with existing methods.\nI realized that the authors did not mention the work of \n\"Learning with Opponent-Learning Awareness\" which proposes LOLA. Also, the authors mention the work of \"Competitive policy optimization\". \nI strongly encourage the authors to make a clear empirical study and compare their method with prior works.\n\nSince the proposed algorithm seems like a well-known traditional per-step best response method, such comparisons are helpful for future submission.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "D8RuTeBT1H_", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n1. Summary:\n\nThis paper addressed an interesting topic on competitive self-play reinforcement learning on two-player zero-sum games. Typically, many self-play methods are only average-case optimal and self-play with latest agent fails to converge. I believe this is a big issue for many self-play because averaging past policies for each player during self-play iterations is very difficult especially for large-scale games.\nThe author tried to solve this problem by perturbation-based subgradient method because of its three advantages:\n(1) it only requires to know the subgradients rather than the game dynamics;\n(2) it's guaranteed to converge in its last iterate rather than the average iterate for convex-concave functions;\n(3) it's very simple to select the opponent in the self-play training.\nThe authors evaluate this method on some small games and the experimental settings/results are well.\nOverall, I like this paper. However, there are some issues or weakness in the current version, I tend to vote minor reject. \nNote, if the author can address the key issues well, i can increase my score.\n\n2. Some Concerns/weakness:\n\n(1) For convex-concave functions, the perturbation-based subgradient method is guaranteed to converge in its last iterate. Does its convergence hold for deep learning settings?\n\n(2) I'd like to see the performance on large-scale settings.\nI think the strength of this method is to solve large-scale game, because it's expensive to average policies for the past iterations for many self-play methods. The author only evaluates the method on small settings, it's not very convincing because when solving small games, self-play with average policies is not expensive.\n\n(3) The author missed some important related papers, such as neural counterfactual regret minimization [1, 2] and exploitability descent [3]. These methods also address the problem of average-case optimal. It will benefit readers if you can talk about these methods.\n\n(4) the baseline is so weak, it will be better to compare against counterfactual regret minimization method and Johannes Heinrich's deep fictitious self-play method.\n\n3. Questions:\n\n(1) For large-scale games, does it need large population size $n$?\n\n(2) Does it time-consuming to solve perturbed $v^{k}_i$ and $u^{k}_i$ for step 6 in Algorithm 1?\n\n(3) Why not use exploitability to evaluate different methods? It's a standard metric in imperfect information games. It will be good if you can evaluate the method on one of poker game, such as leduc.\n\n(4) \"Four colors correspond to the 4 agents in the population with 4 initial points\" in Figure 1, do you mean there are the population size is 4 and there are 4 different initial policies?\n\n(5) what's exact gradient in \"On the other hand, our method enjoys approximate last-iterate convergence with both exact and policy gradients.\"\n\n(6) page 4, Algorithm 1, $N^0$ iterations, $N^0$ inner updates.  $N^0$ is a typo?\n\n\nSome key references:\n\n[1] Brown, N., Lerer, A., Gross, S. and Sandholm, T., 2019, May. Deep counterfactual regret minimization. In International conference on machine learning (pp. 793-802).\n\n[2] Li, H., Hu, K., Zhang, S., Qi, Y. and Song, L., 2018. Double neural counterfactual regret minimization. ICLR, 2020. https://openreview.net/pdf?id=ByedzkrKvH\n\n[3] Lockhart, E., Lanctot, M., Pérolat, J., Lespiau, J.B., Morrill, D., Timbers, F. and Tuyls, K., 2019. Computing approximate equilibria in sequential adversarial games by exploitability descent. arXiv preprint arXiv:1903.05614.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1oETMjfNMvr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe paper “Efficient Competitive Self-Play Policy Optimization” introduces a new self-play scheme for solving zero-sum two-player games. It is suggested to train a population of N agents in parallel, where each agent is matched against the comparatively strongest opponent in the next round of training. As baselines, the paper considers self-play against the best, the latest and random snapshots from the training history of only a single agent.\n \nStrong:\nThe submission is well motivated and seems to state relevant related work.\nThe proposed algorithm seems straightforward and is presented in a clear and understandable way.\nThe proposed scheme solves for the Nash equilibrium for non-transitive matrix games with MC targets.\nThis is shown empirically and amended with a convergence proof.\nThe paper includes deep RL experiments for which the proposed algorithm results in better sample efficiency per agent.\n \nWeak:\nThe last positive point also highlights the main weakness of the paper: I am not convinced, that the efficiency of RL self-play is best measured per agent. In the appendix, it is rightfully argued, that part of the training could be parallelized. However, the conclusion that the baseline experiments thus could be repeated N times, seems to ignore that the additional compute could be used to train stronger opponents also for the baselines. The experiments don’t account for this. \nFurther, the algorithm requires the evaluation of each agent-match-up combination for each round to choose the next opponent and thus involves policy roll-outs that are quadratic in the population size. This seems very expensive especially for larger populations. To highlight the efficiency of the approach in the title of the paper thus might be a misnomer.\n \nRecommendation:\nIn its current form, I thus vote for a weak reject.\n \nSupport:\nI acknowledge the paper and its results to be of interest for self-play in RL. However, in my opinion, the paper fails to properly account for the weakness of its approach. (I believe the paper to become stronger, if the efficiency of the approach was discussed critically.)\n \nRating: 5 out of 10\n \nConfidence: 3 out of 5\n \nCoE: I don’t see the paper in violation of the ICLR’s Code of Ethics.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigate an interesting problem of multi-agent RL with self-play. We agree with the reviewers that the paper requires more work before it can be presented at a top conference.  We would  encourage the authors to use the reviewers' feedback to improve the paper and resubmit to one of the upcoming conferences.

Decision: Reject