No-Press Diplomacy from Scratch
Authors: Anton Bakhtin
David J Wu
Adam Lerer
Noam Brown
Venue: NeurIPS 2021 Poster (2021)
Keywords: multi-agent
reinforcement learning
game theory
double oracle
diplomacy

Abstract: Prior AI successes in complex games have largely focused on settings with at most hundreds of actions at each decision point. In contrast, Diplomacy is a game with more than 10^20 possible actions per turn. Previous attempts to address games with large branching factors, such as Diplomacy, StarCraft, and Dota, used human data to bootstrap the policy or used handcrafted reward shaping. In this paper, we describe an algorithm for action exploration and equilibrium approximation in games with combinatorial action spaces. This algorithm simultaneously performs value iteration while learning a policy proposal network. A double oracle step is used to explore additional actions to add to the policy proposals. At each state, the target state value and policy for the model training are computed via an equilibrium search procedure. Using this algorithm, we train an agent, DORA, completely from scratch for a popular two-player variant of Diplomacy and show that it achieves superhuman performance. Additionally, we extend our methods to full-scale no-press Diplomacy and for the first time train an agent from scratch with no human data. We present evidence that this agent plays a strategy that is incompatible with human-data bootstrapped agents. This presents the first strong evidence of multiple equilibria in Diplomacy and suggests that self play alone may be insufficient for achieving superhuman performance in Diplomacy.

No-Press Diplomacy from Scratch
Anton Bakhtin David Wu Adam Lerer Noam Brown
Facebook Al Research {yolo, alleerr noambrowm)@ff..omm
Abstract
Prior Al successes in complex games have largely focused on settings with at most hundreds of actions at each decision point. In contrast, Diplomacy is game with more than 1020 possible actions per turn. Previous attempts to address games with large branching factors, such Diplomacy, StarCraft, and Dota, used human data to bootstrap the policy or used handcrafted reward shaping. In this paper, we describe algorithm for action exploration and equilibrium approximation in games with combinatorial action spaces. This algorithm simultaneously per- forms value iteration while learning policy proposal network. A double oracle step is used to explore additional actions to add to the policy proposals. At each state, the target state value and policy for the model training are computed via an equilibrium search procedure. Using this algorithm, we train an agent, DORA, completely from scratch for popular two-player variant Diplomacy and show that it achieves superhuman performance. Additionally, we extend our methods full-scale no-pre no-press Diplomacy and for the first time train an agent from scratch with no human data. We present evidence that this agent plays a strategy that is incompatible with human-data bootstrapped agents. This presents the first strong evidence of multiple equilibria in Diplomacy and suggests that self play alone may insufficient for achieving superhuman performance in Diplomacy.
Introduction
Classic multi-agent Al research domains such as chess, Go, and poker feature action spaces with at most thousands of actions per state, and are therefore possible explore ex-
PRU
haustively a few steps deep. In contrast, modern multi-agent AI benchmarks such as StarCraft, Dota, and Diplomacy fea- ture combinatorial action spaces that are incredibly large. In StarCraft and Diplomacy, this challenge has so far been ad- dressed by bootstrapping from human data [32 24 3 I1. In
KNG
KIE
SIZ
WARf
ROW
MUS
FIR
AAS
MAR
BUD
Dota, this challenge was addressed through careful expert- designed reward shaping [4)
RUS
In contrast, in this paper we describe an algorithm that trains agents through self play without any human data and can accommodate the large action space of Diplomacy, a long- standing AI benchmark game in which the number of legal actions for player on turn often more than 1020 (44]
Figure 1: France (blue) would be in a strong position were it not for ex- actly two actions that Austria (red) can play to dislodge the unit in Tyr. The probability of sampling one of them randomly is roughly 10 1
We propose form of deep RL. (reinforcement learning) where each visited state the agent approximates Nash equilibrium for the stage game with I-step lookahead search, plays the equilibrium policy, and uses the equilibrium value the training target. Since the full tion space is too large to consider, this equilibrium is computed over a smaller set of candidate
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

actions. These actions are sampled from an action proposal network that is trained in unison with the value model. We show that our deep Nash value iteration algorithm, when initialized with a human-boots human-bootstrapped model, defeats multiple prior human-derived agents in no-press Diplomacy by a wide margin.
Next, we investigate training an agent completely from scratch with no human data in Diplomacy. In order to improve action exploration when training from scratch, the proposal actions are augmented with exploratory actions chosen through a double-oracle-like process, and if these discovered actions end up as part of the equilibrium then they will be learned by the proposal network. Using this technique, which we call DORA (Double Oracle Reinforcement learning for Action exploration), we develop superhuman agent for popular two-player variant of Diplomacy. Our agent trained purely through self-play with no human data and no reward shaping.
We also train a DORA agent for the 7-player game of no-press Diplomacy, the first no-press Diplo- macy agent to be trained entirely from scratch with no human data. When 6 DORA agents play with I human-data-bene based agent, all human-data-based agents perform extremely poorly. However, when one DORA agent plays with 6 human-data-ban suggest that self-play in 7-player Diplomacy may converge to equilibria that are incompatible with typical human play. This is in contrast to previous large-scale multi-agent benchmarks like mul- tiplayer poker [9] and validates Diplomacy as a valuable benchmark for learning policies that are compatible with human behavior.
agents, the bot underperforms. These results
2 Background and Related Work
2.1 Description of Diplomacy
In this section we summarize the rules of Diplomacy. For a more detailed description, see [24]. No-press Diplomacy is zero-sum board game where 7 players compete for control on map of Europe. The map contains 75 locations, 34 of which are supply centers (SCs). Each player begins with 3-4 units and 3-4 SCs and a player wins by controlling a majority (18) of the SCs. no player controls majority and all remaining players agree to draw, then the victory is divided between the uncliminated players. In case of draw, we use the Sum-of-Squaree (SoS) scoring system that defines the score of player i as C?/ C?/E, Σ, Cb, where C; is the SC count for player i.
Each turn during movement, all players simultaneously choose action composed of one order for every unit they control. An order may direct a unit to hold stationary, to move to an adjacent location, to support nearby unit's hold move, move across water via convoy, to act as the convoy for another unit. Because a player may control up to 17 units with an average of 26 valid orders for each unit, the number of possible actions is typically too large to enumerate. Addition- ally. in Diplomacy, often supports or other critical orders may be indistinguishable from a no-op except in precise combinations with other orders or opponent actions. This makes the action space challenging to learn with black-box RL. Actions are simultancous, so players typically must play a mixed strategy to avoid being predictable and exploitable.
In the popular France vs. Austria (FvA) variant of Diplomacy, the number of players is reduced to two, but the victory condition and all game rules, including the number of locations and centers, remain the same. FvA serves as an effective way to isolate the challenge of an astronomically large imperfect-iiformation action space from the challenge of Diplomacy's multi-agent nature.
2.2 Stochastic Games
Stochastic games (26] are a multi-agent generalization of Markov decision processes. At each state, each player chooses an action and the players' joint action determines the transition to the next state. Formally, at each state s E S agents simultaneously choose a joint action a = (aj...., av) E A A1x--.XAN, where A is the number of players. Agents then receive a reward according to a vector function r(s, a) E R and transition to new state s' f(s, a). The game starts at initial state s and continues until a terminal state is reached, tracing a trajectory T = ((5", a²), "),,,. (o--1, a1-))) where [(s'_1, -111) is terminal. Each agent i plays according to a policy म; S + AA, where A A, is a set of probability distributions over actions A,. Given a policy profile π = (II,,..., Tw),, the probability of a trajectory is p(T| = [( p(a) a (s)),, and we define the vector of
2

---

r'r(st: expected values of the game rooted at state s as V(T,5) s) = Eier(,) P(T|TT) -(T)))) )e at) where T(s) the set of terminal trajectories beginning at s. We denote by V(T) := (TT, s0) the value of a game rooted in the initial state. We denote by πT the policies of all players other than i.
A best response (BR) for agent i against policy profile л is any policy that achieves maximal expected value. That is, gं is a BR to π if Vi(TT --1) = max V((T),==.) A policy profile Nash equilibrium (NE) if all players' policies BRs each other. Letting V, be the ith component of V, π is NE if:
W VT(TT) 2 ((T).T.))
An e-NE is policy profile in which agent can only improve its expected reward by at most by switching to a different policy. If a policy profile is an e-NE, we say its exploitability is e.
We may also talk about Nash equilibria for one stage of the game rather than the whole game. For any state s, supposing we have values Qss, a) that represent the expected values of playing joint action a in state assuming some policy profile is played thereafter, we may define new 1-step game where instead the game ends immediately after this action and ((s, a) is itself the final reward. For such stage games, notationally we denote NE using the symbol rather than x.
2.3 Nash Q-Learning
Value iteration methods such Nash-Q have been developed that provably converge to Nash equilibria in some classes of stochastic game, including 2p0s (two-player zero-sum) stochastic games [9 [4]. Nash-Q learns joint Q values Q(s, a) that aim converge to the state-action value of (8, a) assuming that some NE æ is played thereafter. This is done by performing 1-step updates on a current estimated function Q as standard Q-learning, but replacing the max operation with stage game NE computation.
Formally, suppose that is played in leading to s'. A NE o, ag E AA4 is computed for the stage game at s' whose payoffs for each joint action are specified by the current values of Q(s', a'). The value of this game to each player assuming this NE is then used as the target values of Q a.) The update rule is thus:
Q(s,a) + ( (1-a)((s.)) + + [a(a))((saa))
(I)
where a is the learning rate, 7 is the discount factor, and (a) = 11. (a,s) is the probability of joint action
As presented later in Section 3.1 the foundation of our algorithm is an adaptation of Nash Q- Learning, with several modifications to make it suitable for deep RL and adjusted to use value function rather than Q function.
2.4 Double Oracle
Double oracle (DO) is an iterative method for finding a NE over a large set of actions in a matrix game (22. It leverages the fact that computing best response is computationally much cheaper than computing a NE. Starting from a small set of candidate actions A C A; for each player i, on each iteration it computes NE af in the matrix game restricted to the candidate actions A'. Then, at each iteration t for each player i it finds the best response action a (+1 A to the restricted NE of and creates A = A₁ A(att Formally, a is an action in the full action set A; that satisfies
d ++ arg max
Σ (o.s,a,...,,4111... d', a.t1............................ aN) II [a)(),) jØ1
a'EA; acA'
DO-inspired methods have been used in variety of other work for handling large or continuous action spaces [75] 18 21). Although in the worst case the equilibrium policy may have support over large fraction of the action space, in practice in many problems small subset of actions may suffice, and in this case DO-based methods can be computationally efficient due to being able to restrict equilibrium computation only tiny fraction of the total number of actions.
As we will present in Section 3.2 we make use of a DO-like procedure both within the RL loop and at inference time, and show it to be an effective way introduce novel good actions to the policy.
3

---

2.5 Regret Matching
Both Nash-Q Q-Leannin and DO require the computation of NEs in matrix games, which we approxi-
mate using the iterative regret matching (RM) algorithm [3|[3], as has been done in past work [TT].
RM is only guaranteed to converge to a NE in 2p0s games and other special classes of games [[2].
Nevertheless, past work has found that it produces competitive policies that have low exploitabil-
ity in important non-2p0s games including six six-player poker and no-press Diplomacy therefore use RM to approximate NE in restricted matrix games during DO.
We
In RM, each player has regret value for each action a; A. The regret on iteration t is denoted (a)). Initially, all regrets are zero. On each iteration & of RM, (a;) is set according to
max(U, Regret M.eA max Regnet
if EafeA, max Regret (a()) > 0
(a.))
(3)
otherwise
Next, each player samples an action of from A, according to of and all regrets are updated such that
Regret +1 (a:) (agret((a;) 2 vg a":))
Σ dEA.
o((d)ev(d, a"r,,
where (z(a) is the utility of player in the matrix game. This sampled form of RM guarantees that the average policy over all iterations converges to a c-NE in 2p0s games at a rate of at worst (x))) iterations with high probability [17]. In order improve empirical performance, we use linear RM [8. which weighs updates on iteration / by | We also use optimism [30]. in which the most recent iteration is counted twice when computing regret.
3 Algorithms
We now describe DORA in detail. DORA simultaneously learns state-value function and an ac- tion proposal distribution via neural networks trained by bootstrapping on an approximate Nash equilibrium for the stage game each turn. A DO-based process is used to discover actions.
3.1 Deep Nash Value Iteration
The core of the learning procedure is based on Nash Q-Learning as presented in Section 2.3 but simplified to use only a value function, with adaptations for large action spaces and function ap- proximation.
Approximating a Q-function in a game with an action space as large as Diplomacy is challenging. However, in Diplomacy as in many other domains, the reward r(s, a) depends only on the next state = f(s a) and not on how it was reached, and since the transition function is known and can be simulated exactly, we redefine r to be function of just the next state s', In that case, we can rewrite Update Rule[T (fom Section 2.3) in terms of a state value function:
V(s) - -1- (s)) + a(r(s)
"ala')
(5)
Since the state space large, we use deep neural network V(s; 0,) with parameters O, approxi- mate Vss). Since the action space is large, exactly computing the Nash equilibrium for the 1-step matrix game a state is also infeasible. Therefore, parameters 0x that approximates the distribution of actions under the equilibrium policy at state s. We generate a candidate action set state s by sampling N₂ actions from (s; 0x) for each player and selecting the No < No actions with highest likelihood. We then approximate a NE via RM (described in Section 2.5 in the restricted matrix game in which each player is limited their N. actions assuming successor states' values are given by our current value network V(s; 0p).
train a policy proposal network (ss; 0,) with
We explore states via self-play to generate data, with both players following the computed NE policy with an probability of instead exploring a random action from among the N. proposals. Also, in
In practice, rather than weigh iteration i's updates by I we instead discount prior iterations by #F in order reduce numerical instability. The two options mathematically equivalent.

---

At a high level our algorithm is similar to previous algorithms such as AlphaZero 28 and ReBeL [6] that update both policy and value network based self-play, leveraging simulator of the envi- ronment to perform search. The biggest differences between our algorithm and AlphaZero are that 1-ply RM acts as the search algorithm instead of Monte Carlo tree search (just in [II), the value update is uses a 1-step bootstrap instead of the und-of-game-vee eration be off-policy if desired), and the policy network acts (which allows the trajectory gen- place of fg and f,, self-play uses slightly- versions of the networks 6, and 0z to compute that are only updated periodically from the latest 02 and 8x in training. a normal practice that improves training stability [23]. We then regress the value network towards the computed stage game value under the NE a using MSE loss (whose gradient step is simply the above update rule), and regress the policy proposal network towards a using cross entropy loss:
ValueLoss(O..) 2 V(s;0,) - r(s) - "o(a''
(6)
PolicyLoss(Pe) Σ Σ 02(0) log (s, ag 0x)
o,EA,
We show in Appendix [ that in 2p0s games, the exact tabular form of the above algorithm with mild assumptions and without the various approximations for deep RL provably converges to NE. Outside of 2p0s games and other special classes, both Nash Q-learning and RM lack theoretical guarantees; however, prior work Diplomacy and 6-player poker have shown that similar ap- and we also observe that DORA performs proaches still often perform well in practice 11 3
well in 7-player no-press Diplomacy.
action proposer for the search but does not regularize the search thereafter. Our algorithm is also similar to a recent method to handle large action spaces for Q-learning 31 and reduces to it in single-agent settings.
3.2 Double-OracleBBaeed Action Discovery
The algorithm in Section 3.1 relies on the policy network to generate good candidate actions. How- ever, good actions initially assigned too low of probability by the network may never be sampled and reinforced. To address this, we use mechanism based on double oracle, described in Sec- tion 2.4, to introduce novel actions. However, vanilla DO requires computing the expected value of all actions against the restricted matrix game NE. Since our action space is too large to enumerate, we generate only a pool of N, >> N₂ actions consider.
A natural idea to generate this pool would be to sample actions uniformly at random from all actions. However, our results in Section 5.10 show this approach performs poorly. Intuitively, combinato- rial action space as large as in Diplomacy often only minuscule fraction of actions are reasonable, so random sampling exceedingly unlikely to find useful actions (see Fig for an example).
We instead generate the pool of Np actions for a player by generating local modifications of the candidate actions already in the restricted matrix game equilibrium. We first sample uniformly among the player's Na (d S c) most probable actions in that equilibrium. Next, for each sampled action, we randomly sample single location on the map and consider all units of the player adjacent to the location. For those units, we randomly choose legal valid new orders. We add the order in this pool that best-responds the equilibrium as a new candidate action, and DO proceeds as normal.
As shown in Table 3 we found this method action sampling to outperform simply picking legal and valid combinations of orders uniformly at random. Intuitively, this is likely because locality in Diplomacy, as in a wide variety of other problem domains and algorithms, is powerful inductive bias and heuristic. Perturbations of good actions are vastly more likely than random actions to also be good, and spatially
actions are more likely to need to covary than spatially-disten ones.
To further improve the scalability of our algorithm, we apply several additional minor approxi- mations, including computing some of the above expected values using sampling and capping the number of DO iterations we perform. For details, see Appendix [
5

---

Algorithm Approximated Double Oracle Implementation and Methods
We describe our implementation of the above algorithms and training methods as applied training in Diplomacy. For details on the exact parameters, see Appendix D The code and the models are available online
4.1 Data Generation and Training
We implement deep Nash value iteration following the same considerations as deep Q-learning. Multiple data generation workers run self-play games in parallel. The policy and value targets on each turn along with the game state they correspond to are collected in shared experience replay buffer and sampled by set of training workers to train the networks. The policy proposal and value networks used by the data generation workers are only periodically updated from those in training.
During self play, each agent plays according to its part of the computed approximate-Ne -N policy with probability 1 - and with probability plays a uniformly random action from the N₂ actions obtained from the policy proposal network. We also to quickly introduce diversity from the opening state, similar to the use of larger early exploration settings in other work, for example AlphaZero 29 28). Detailed parameters
larger values of the first turns
Appendix D
1: function FINDEQUILBRIUMWWHHHOOO N... Np. Nators. Nc)
2:
SAMRREACTIOOSFRROPPPPPSLLLLEEEEE a < COMPUTEHQUI.IRIIMG, A)
3:
4:
for t = (1..Naters) do
5:
modified < 0
6:
for = (I..NNieoyers) do
7:
A, GENERATEACTIONSS( Ai, Np)
Uniform sampling local modification
8:
0, Ea-a [Vi(f(s, a);
9:
a7 of arg max En En [V(([(s.a):0.))
a,EA,
if c 0; > then
11:
A; < A, U[a3}
12:
+- COMPUTEEQUILLBRIUMG, A)
13:
modified +-
modiiedd then
15:
Break
return o
16:
function GINNRITTACTOONI.CCAANOOTTTTTTTT Abase: Nz)
17:
At
0
while [A] Nx
19:
a f- SAMPLEACTION(AIs.)
20:
loc SAMPLEMAPLOCATIONS
21:
clique GETNEEGHHOURSS(OOO)
22:
a' RAAAAAACOOODDIATMMMOORRTTTTTTOOO chique
23:
A + AU('}
return A
4.2
Model Architecture
Our model closely follows the encoder-decoder architecture of [I]. We use the policy head model the policy proposal distribution and the value head predict the expected values of the players.
We found several adjustments be effective for moved all dropout layers, as we found this to improve training stability. Secondly, we replaced the graph convolution-basee removing the need to hardwire the adjacency matrix of the Diplomacy map into the architecture. Lastly, we also split the network into separate policy and value networks. Since our regret mini- mization procedure is essentially only 1-ply search, the states on which we need to evaluate policy
in deep Nash-based RL. Firstly, we
encoder with simpler transformer encoder, improving model quality and

---

(the current state) and value (the states after one turn) are disjoint, so there is no gain to comput- ing both policy and value in one network query, and we found splitting the networks improved the quality and effective capacity of the models. We measure the impact of these choices in Table 2 and describe the architecture in more detail in Appendix A
and
4.3 Exploitability Testing
To obtain a metric of the exploitablity of our final agents, we also train additional exploiter agents that rather than attempting play an equilibrium, instead hold the exploited agent fixed and attempt to converge to a best response. We compare two approaches.
In the first approach, we reimplement the same actor-critic method with sampled entropy regulariza- tion previously used in [I]] for 7-player no-press Diplomacy and apply to 2-player FvA. this approach, the other agent is treated as a black box, reducing the problem to just a standard Markov Decision Process to which we can apply classical RL techniques. Namely, we use Impala [10], an asynchronous version of actor-critic algorithm. Since search agents may take several seconds to act, [T first trained a policy network to copy the behavior of the search agent and then applied RL to exploit this proxy agent. The proxy agent acts much faster, which enabled generating data faster. In contrast, we optimized the training loop so that it was possible to train to exploit the search agent directly without first generating proxy policy network agent.
In the second approach, we begin with the policy and value models of the exploited agent and resume deep Nash value iteration, except with a single simple modification, described in Appendix E. that results in learning a best response rather than an equilibrium.
5 Results
Diplomacy features two main challenges for Al research: its large combinatorial action space and its multi-agent (non-2p0s) nature. DORA is intended address the former challenge. To measure its effectiveness on just the action-cxploration aspect, we first present results in a 2p0s variant of Diplomacy called France vs. Austria (FvA). We show DORA decisively beats top humans in FvA.
Next, we present results for 7-player no-press Diplomacy, which has been a domain for much prior research 24 B [1] We train DORA agent from scratch with human data and test it against pre-trained models from previous work [24 I In the 6v1 setting, (six DORA agents playing with one copy of another bot) DORA wins overwhelmingly against all other agents. However, in the Iv6 setting (one DORA agent playing with six copies of another bot), DORA does slightly worse than previous search agents that leveraged human data. Our results suggest that DORA converges to strong play within an equilibrium (i.e., a "metagame") that is very different from how humans play. Finally, we present results showing that adding our RL algorithm on top of boottappoo model clearly beats prior bots in both the I Iv6 and 6v1 settings.
5.1 Results in 2-player France vs. Austria
Austria
France
Total
Average score (+variance reduction)
89%15%
7% 73%
66%.
78%.14%
Raw average score
100%11%
87%.16%
# games
13
13
26
Table 1: Head-to-head score of DORA versus top FvA players pebdåplomacyy .nt. The + shows one
standard error. Variance reduction (Appendix C was used compute average scores from raw average scores. Note that for raw Austria score, because DORA managed to win all games, anomalously the sample standard deviation is technically O. The true standard deviation is of course larger but cannot be estimated.
In 2-player FvA, we tested our final DORA agent against multiple top players of this variant, inviting them play a series of games against our agent. All players were allowed to play arbitrary number of practice games against the agent before playing official counted games. Prior to running the games, we also implemented a simple variance reduction method, described in Appendix C
"eee Appendix Dft the details.
7

---

In Table 1 we report both the raw and variance-reduced average scores. DORA defeats top human players by large and highly sigmificant margin, with an average score of 78% after variance reduc- tion. It also wins significantly more than half of games as France, the side considered much harder to play These results show DORA achieves a level of play FvA above that of top humans.
We ran several ablations to loosely estimate the relative importance of the various components con- tributing our final agent for France Austria.
Architecture
Final Elo
Params
GraphConv
898 + 13
46.8M
TransformerEnc 5x192
1041 =
9.3M
TransformerEnc 10x224
1061 = 12
12.4M
TransformerEnc 10x224 (Separate)
1123 = 13 24.8M
Table 2: Effect in FvA of the architecture final strength after RL, and number of parameters. GraphCony the architecture achieving SOTA in supervised learning from [1], and similar to other past work 24 3 TransformerEnc b bx replaces the graph-conv encoder with a transformer encoder with blocks and f feature channels. "Separate" uses separate value and policy networks instead of shared network with two heads. Elos
are based 100 games against each of several internal baseline agents, including the agents Table
GraphConv vs Transformers
DO Method During RL Training
Final Elo
No DO
927 + 13
DO, uniform random sampling
956 + 13
DO, local modification sampling
1023 = 13
Table 3: Effect of DO methods during training on final FvA agent strength. Local modification sampling improves results greatly, whereas uniform random sampling relatively ineffective. Elos one standard error were computed based on 100 games against each of several bascline agents, including the agents in Table [
Double Oracle at Training Time See Table 2 Although not primary focus of this paper, we found that at least for use in RL, changing our model architecture to use a transformer encoder rather than graph-convolution encoder in Section 4.2 resulted in significant gains over prior neural net- work architectures in Diplomacy 24
while using fewer parameters and still being similarly fast or faster in performance. Enlarging the model and splitting the network led to further gains.
See Table We demonstrate the effectiveness of our DO method in finding improved actions during training. DO's 's ability to discover new strong actions for the policy proposal network to learn makes a big difference in the final agent. Local modification sampling effective, whereas random sampling is relatively ineffective.
Double Oracle at Inference Time See Table We also demonstrate the effectiveness of our DO method in finding improved candidate actions at inference time. Uniform random sampling among legal actions generate the action pool for finding best responses only improves the weakest of our baseline agent at inference time, due to being ineffective at finding better actions within the huge action space, whereas local modification sampling improves all baselines inference time.
5.1.1 Exploitability
We implemented and tested both algorithms from Section exploitability of agents. We also test variant where we adapt deep Nash value iteration for exploitation just as in the second method, but disable policy learning the value network learns to predict states of higher exploitability, but the policy proposal network is fixed and does not learn.
4.3 to estimate a lower bound on the
The results against our best agent are in Table We find that despite being of superhuman strength, the agent is still relatively exploitable. In 2p0s ange-action-space setting, this is not necessarily
Between agents of similar strength often observe France winning only about third of games Austria.

---

Model used by both players
Model1
Model2
Model3
DO Method used by measured player 4
None
0.510
0.5.1
0.5.0
DO, uniform random sampling
0.75=00.02
0.48=0.02
0.47=0.02
DO, local modification sampling
0.8010.02
0.5910.02
0.56
Table 4: Effect of using DO at inference time in FvA. Each entry is the average score when both players play the column agent, but one player uses a DO variant at inference time. 1oddel1-Mode33 are models of increasing quality developed over the course of our research, with the major differences being that Model1 I uses trained value network with fixed proposal network, Model2 uses GraphConv encoder, and Model3 uses small Transformer encoder. Stronger agents require better sampling methods find candidate actions that help.
vs DORA
vs DORA inference-time DO
Actor-Critic PG [1]
77. 77.0%
Deep Deep Nash- Derived Exploiter, values only
Exploiter
90.5%.10.4%
85.8% 1...5% 60.5%...77
65.7%.1.66
Table 5: Win rates for exploiter bots trained with different techniques against hest FvA agent with and without inference-time DO. The + shows one standard error. Actor-Critic PG vs DORA with inference-time DO was not run due to computational cost.
surprising. For example in Go, another game with moderately large action space, there exist gaps of more than 1000 Elo (nearly 100% winrate) between different agents, all of which are superhuman, with explicit training for exploitation as Diplomacy, exploiting a fixed agent is much easier than training an agent with low exploitability, since the exploiting agent does not need to precisely balance the probabilities of its actions.
[27]. Moreover, in imperfect- inperfect-informatii information games such
Nonetheless, we also observe that our adaptation of the deep Nash value iteration method greatly outperforms the simpler actor-critic method from [1I], and that both value learning and DO-based policy learning are important for its performance, with value learning improving over the baseline from 50% to 60.5%, and policy learning improving further to 85.8% winrate over DORA.
We also observe that applying DO at inference time reduces the exploitability, from 90.5% using our strongest exploiter agent to 85.8%. Even at inference time, DO continues to find and suggest new effective actions that would otherwise be overlooked by the policy proposal network.
5.2 Results in 7-player No-Press Diplomacy
We also applied our methods to 7-player no-press Diplomacy, training a DORA agent entirely from scratch with no human data in this more-challenging domain. For comparison, also trained an agent via deep Nash value iteration beginning from policy and value networks first trained on human games. Our best results were achieved when we forced the agent to the human- -uman--nitialized policy for action proposal during training games, never updating it, and also stopping the training early additional ablations in Appendix H). Since do not update the action proposal policy used in training games, we also do not apply DO for this agent, and so we refer to this agent as HumanDNVI- NPU ("deep Nash value iteration, no proposal update"). The results reported in Table Note that as these are 7-player games, the expected score if the agents perform equally well is 1/7 14.3%.
Unlike in 2p0s settings, in competitive multi-agent game, particularly where agents must temporarily ally and coordinate to make progress, there may be multiple different equilibria that are mutually incompatible [20]. An agent playing optimally under one equilibrium may perform very poorly in a pool of agents playing a different equilibrium.
such Diplomacy
For example in Diplomacy, it may be mutually benefit two agents to ally to attack a third, but in such cases players must often coordinate on a choice, for example on which unit attacks and which unit supports, or on which region to attack. Since an order and support must exactly match to be effective, each choice may be a stable equilibrium on its own. But an agent that plays one choice in population of agents that always play another in that situation will fail to match and will do poorly.

---

1x 4 vs 6X -
DipNet 24
SearchBot 11
DORA
HumanDNVI-NPU
DipNet (24)
0.8%=#..1%
0.0%+0000%
0.1%++0.0%
SearchBot
49.4%..2.6%
1.1 1.1%.10.4%
0.5%..0.29%
DORA
22.8% 22.2%
11.0%.1.5%
2.2%610.4%
HumanDDVI-NPU
45.6%12.66%
36.3%:12.4%
3.2%.10.7%
DipNet- Transf
23.4%612.2%
2.1%%10.7%
0.0%.10.0%
0.3%
SearchBot- Transf
48.1%:12.6%
13.9%
0.5%.10.33
0.9%:1..2%
SoS scores of various agents playing against 6 copies of another agent. The + shows standard error. Note that equal performance nent, while performing much worse on the 1x side with human-like opponents. The last 2 rows are equivalent to first 2 rows, but are retrained with the same architecture as self-play agents, i.c. TransformerEnc 5x192, showing the effect of architecture these baselines separately from deep Nash RL methods.
Table 6:
Rs 14.3%. The non-human DORA performs very well as oppo-
Ix 6x
DORA
DORA (alternate run)
DORA
7.5%1100%
DORA (alternate run)
3.2%++077%
Table 7: SoS scores between two runs of DORA, agent versus copics of other. The + shows one standard error. Note that equal performance would be 1/7 s 14.3%.
Our results are consistent with DORA converging roughly to an equilibrium that very different than the one played by humans, but playing well within that equilibrium. DORA achieves only about an 11% winrate in 1-vs-6 setting against one of the strongest prior human-data-bass agents, SearchBot [1] (tying would be score of 1/7 = 14.3%). However, SearchBot fares even worse with 1-vs-6 setting against DORA.
only 1.1% 1% winrate
Against a second DORA trained with different random seed (Table 7 each DORA scores only about 3-8% against the other 1-vs-6. This suggests that different DORA runs may converge to different equilibria from each other.
Our results with HumanDNVI-NPU are also consistent with reinforcement learning converging to inconsistent equilibria. HumanDNVI-NPU soundly defeats SearchBot, the prior SOTA, winning 36.3% of games 1-vs-6, while SearchBot wins only 0.5% in the reverse matchup. Starting from a human-likk like policy, deep Nash value iteration massively improves the strength of the agent. Yet HumanDNVI-NPP still does extremely poorly vs DORA, and vice versa. Our results seem to sug- gest that in 7-player no-press Diplomacy, deep Nash value iteration converges to an equilibrium in which outside agents cannot compete, even agents trained independently by the same method, but that which equilibrium is found depends on initialization, with some equilibria performing far better versus human-like players than others. See also Appendix H for additional ablations and experiments.
Conclusions and Future Work
Diplomacy has been benchmark for Al research for two main reasons: its massive combinatorial action space and its multi-agent nature. We show that DORA achieves superhuman performance in 2- player Diplomacy without any human data or reward shaping, despite the combinatorial action space and imperfect information. DORA therefore effectively addresses the first challenge of Diplomacy.
Additionally, we show that DORA in full-scale 7-player no-press Diplomacy approximates equi- librium that differs radically from human-data-based agents. When one human-data-hann agent plays against a population of DORA agents, the one agent loses by wide margin. Similarly, one DORA agent against population of human-data-based agents does not exceed an average level of performance. These 7-player results provide evidence that self-play from scratch may be insufficient to achieve superhuman performance in Diplomacy, unlike other multiplayer games such as 6-player poker 19]. Furthermore, the results suggest that there may be wide space of equilibria, with some differing dramatically from human conventions. DORA provides the first competitive technique for exploring this wider space of equilibria without being constrained human priors.
10

---

References
[1] Lukáš Adam, Rostislav Horčík, Tomáš Kasl, and Tomás Kroupa. Double oracle algorithm for computing equilibria in continuous games. 09 2020.
[2] Thomas Anthony. Ghost-ratings, 2020.
[3] Thomas Anthony, Tom Eccles, Andrea Tacchetti, János Kramár, Ian Gemp, Thomas C Hudson, Nicolas Porcel, Mare Lanctot, Julien Pérolat, Richard Everett, et al. Learning to play no-press diplomacy with best response policy iteration. arXiv preprint arXiv:2006.0440 2020.
[4] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota with large scale deep reinforcement learning, arXiv preprint (xXxv::912.0666888 2019.
[5] David Blackwell et al. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1):1-8, 1956.
[6] Noam Brown, Anton Bakhtin, Adam Lever, and Qucheng Gong. Combining deep reinforce- ment learning and search for imperfect-informatio games. arXiv preprint arXiv:2007.13544 2020.
[7] Noam Brown and Tuomas Sandholm. Simultaneous abstraction and equilibrium finding in games. In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
[8] Noam Brown and Tuomas Sandholm. Solving imperfect-information games via discounted regret minimization. In Proceedings of the AAAI Conference on Artificial Intelligence, vol- ume 33, pages 1829-1836, 2019.
[9] Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, page eaay2400, 2019.
[10] Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep- with importance weighted actor-learner architectures. arXiv preprini arXiv: 1002.00600.. 2018.
[11] Jonathan Gray, Adam Lerer, Anton Bakhtin, and Noam Brown. Human-level performance in no-press diplomacy via equilibrium search. arXiv preprint arXiv:2010.02923, 2020.
[12] James Hannan. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, 3:97-139, 1957.
[13] Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equi- librium. Econometrica, 68(5):117-11150, 2000.
[14] Junling Hu and Michael P Wellman. Nash Icarmnng for general-sum stochastic games. Jour- nal of machine learning research, 4(Nov):1039-1069, 2003.
[15] Manish Jain, Dmytro Korzhyk, Ondicj Vančk, Vincent Conitzer, Michal Péchouček, and Milind Tambe. A double oracle algorithm for zero-sum security games graphs. In The 10th International Conference on Autonomous Agents and Multiagent Systems- Volume 1, pages
327-334 2011.
[16] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arxiv: 1412.6980, 2014.
[17] Mare Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling. Monte carlo sampling for regret minimization in extensive games. In Advances in neural information processing systems, pages 1078-1086, 2009.
[18] Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent re- inforcement learning. In nternational Conference on Neural Information Processing Systems, pages 4193 4206, 2017.
[19] Michael L Littman. Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
[20] Dunean Luce and Howard Raiffa. Games and decisions: Introduction and critical survey. Courier Corporation, 1989.

---

[21] Stephen Mcaleer, JB Lanier, Roy Fox, and Pierre Baldi. Pipeline psro: A scalable approach for finding approximate nash equilibria in large games. In H. Larochelle, M. Ranzato, R. Had- sell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20238-20248. Curran Associates, Inc., 2020.
[22] Brendan McMahan, Geoffrey Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In International conference on machine learning, pages 536-543. 2003.
[23] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(75400:559-533, 2015.
[24] Philip Paquette, Yuchen Lu, Seton Steven Bocco, Max Smith, O-G Satya, Jonathan K Kum- merfeld, Joelle Pineau, Satinder Singh, and Aaron C Courville. No-press diplomacy: Modeling multi-agent gameplay. In Advances in Neural Information Processing Systems, pages 4474- 4485, 2019.
[25] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in neural information processing systems, pages 8026-8037, 2019.
[26] Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 19900000955-1100, 1953.
[27] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanc- tot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484, 2016.
[28] David Silver, Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general re- inforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1 1:01:):::11--114444 2018.
[29] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et Mastering the game of go without human knowledge. Nature, 550(7676):354, 2017.
[30] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems, pages 2989-2997, 2015.
[31] Tom Van de Wiele, David Warde-Farley, Andriy Mnih, and Volodymyr Mnih. Q-learning in enormous action spaces via amortized approximate maximization. arXiv preprint arXiv:2001.08/16. 16, 2020.
[32] Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grand- master level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350-- 354, 2019.
12


Reviews:
[{"review_id": "jifibUd-M3E", "reviewer": "Reviewer_MTQy", "summary": "The paper proposes learning methods for the No-Press variant of the board game Diplomacy. \n\nThe method uses an equilibrium search method (similar to [9]) to solve for Nash in a single turn of the game, estimating future returns with a value function one turn in the future. Then a policy is trained to predict the equilibrium found, while the value function is trained to predict the values of the Nash equilibrium, which implements value iteration.\n\nThe equilibrium search method is based on prior work [9]. This tackles the large action space by restricting search to only the most likely actions from a policy network. This is extended in this work by using Double Oracle to expand the action set, and using a Diplomacy-specific method to generate proposal actions, which exploits the graph structure of the game. The paper also introduces a transformer-based model for learning to play Diplomacy, which outperforms previous Graph-Network approaches, and advances methods to estimate the exploitability of a Diplomacy agent.\n\nExperimental results show that this results in an agent that can defeat human opponents convincingly in a 2-player variant of Diplomacy.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "This paper is well written and easy to follow. The methods used are appropriate to the domain, and experimental data supports the claims of the paper well. I like that the human challengers were given an opportunity to practice against the agent before playing the test games. \n\nIt is a shame that no tester played many games - I assume this also means they played only some practice games too - as I’d be interested to see whether a player could improve against the bot with much more practice.\n\nI didn’t find the techniques proposed particularly surprising, the paper seems to represent a judicious combination of existing ideas, rather than major algorithmic innovation.\n\nHowever, Diplomacy is a very challenging domain, and there are many details that were considered here to perform well in it, which future researchers could build upon. In so doing, this paper provides useful empirical evidence about the efficacy of those methods in an important domain.\n\nI particularly value that this paper demonstrates that the following are true:\n1. Existing methods are sufficient to achieve superhuman results in the 2-player zero-sum version of Diplomacy, learning from scratch.\n2. The same methods are (likely) unable to do the same for the otherwise similar 7-player variant. As the paper notes, this was not the case for many-player poker.\n\nThis motivates and enables researchers to extend beyond 2-player zero sum in an interesting domain. I think that moving beyond 2p0s would be of considerable value to the field.\n\n\nOther points:\n\nAre the results from single training runs of the methods, or from multiple seeds? If the former, can additional replications be included? Are the standard errors only over measurements, or also over repetitions of the training procedure?\n\nI’m not a fan of the name “Deep Nash Learning”, because multiple algorithms already exist that combine deep learning with theoretically sound approaches to finding a Nash equilibrium. Perhaps something like Deep Nash Value Iteration would be more descriptive?\n\nIn Table 6, could you include your best human imitation learning agent? Several works since DipNet have reported improvements on DipNet, and it would be interesting to see how the state of the art for Imitation learning compares.\n\nThe conclusion that the method allows non-human equilibria to be explored in 7-player Diplomacy misses the more important point that incompatible equilbria exist and are a problem for learning based approaches, which hadn't previously been demonstrated. It is not clear that more than one alternative equilibrium can be found by DORA, though.\n\nLine 492 (appendix) and later: citation maybe should be of [9], not [10]? The citation in line 653 has a similar off-by-one error.\n\nThe comment in lines 573-576 clarifies what I had thought was a typo in Algorithm 1. It might be worth including a comment in the main text? In the 7 player version, was this still done player-by-player, as the sampling for regret matching and potential BR value estimation means that this comment is perhaps no longer valid?\n\nFor the camera-ready version, could the HumanDNL experiment be repeated with the same settings as the from-scratch version?\n\nAre there any insights to be had about the agents’ play styles, either in 1v1 or 7-player Diplomacy?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, except for points raised above", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "VCmEr3vR8lw", "reviewer": "Reviewer_4wnr", "summary": "This paper builds off of Gray et. al. by swapping out the blueprint that is trained on human data with one that is trained from scratch using a deep learning variant of Nash-Q learning. The new method is able to achieve what appears to be superhuman performance in 1v1 Diplomacy and also does well but with mixed results in 6v1 Diplomacy against existing methods. ", "questions": "", "limitations": "", "rating": 6, "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": "(This review has been edited. Initially I thought that the performance on 1v1 was not superhuman because I thought the authors just played against some top players online, but after looking through the supplemental materials they played against multiple players including the top rated player in the world and had a winning record against all players. I think this qualifies as being superhuman, and for that reason change my review to accept. I should have verified this earlier, my apologies.)  \n\nDiplomacy has emerged as a new benchmark in the field, and is a very large and complicated game. The authors are able to do well on this game, which is impressive. Most importantly, they are able to achieve superhuman performance on 1v1 Diplomacy for the first time. \n\nHowever, as described in my summary of the paper, it seems that the main contribution of this paper is changing the blueprint strategy of Gray et. al. and replacing it with a deep learning version of Nash Q learning. The resulting method achieves about the same performance as the Gray et. al. paper. Although the Gray et. al. paper does not compare performance in 2-player games, my guess is that it would do similarly well as DORA did. \n\nI don’t think the methods introduced are extremely novel or general. They seem to be modifications of existing methods (Nash Q Learning) to get it to work on Diplomacy. With that being said, the performance on two-player Diplomacy appears to be superhuman. Even if I suspect that SearchBot might also have been superhuman at 1v1 Diplomacy, they do not include these results in their paper. \n\nI am still ambivalent about this paper. The method is not very novel and it is not clear that other methods would not have worked on this domain. As a result, I am not sure how others can build on this work. The authors do not present this method as a general method that will work well for any 2p0s Markov game, to do so they should have compared directly against other algorithms across a number of games.  However, this is the first paper to achieve superhuman performance on a large 2-player zero-sum game that has been popular with the research community, and for that reason I vote to accept. \n\n____________________\nI have read the rebuttal and the other reviews and do not change my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "HbsP4GwEuHy", "reviewer": "Reviewer_GFW6", "summary": "The paper proposes an approach called DORA for building agents for the Diplomacy board game, which is a long standing AI challenge. The key achievement in the paper is constructing agents in a way that does not rely on imitating human gameplay (as opposed to some recent works which at least in part leverages historical game data). Diplomacy is hard because it has a large action space and as it is a game with many players (7 in the full game, but only two int eh France/Austria variant). The results are very good for the two player (France/Austria) variant against people. The results are more mixed in the 7 player game - when there are many copies of DORA, it does very well, but less well when there are many copies of another bot and one DORA player. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Diplomacy is a great AI research domain, and there has been several papers on this challenge. The authors do discuss what makes the game hard (in particular a large action space and having many players). However, Diplomacy is just a board game, so I think the authors should extend the discussion of why this domain is so important, or explain how the techniques developed here could extend to other domains. Is there a real-world application where these methods could be used? \n\nAt a high level, the new DORA algorithm combines ideas from several existing approachs, in particular AlphaZero (Monte-Carlo Tree Search based methods), ReBel, and double oracle and regret matching methods. As the authors explain, this is a combination of various existing building blocks, but combined in a new way, where teh the MCTS based search is replaced with a regret matching approach, and where the policy network acts to propsoe actions for the search, but not regularizes the search after; the authors also nicely discuss the connection to Nash-Q learning. All in all, I think the algorithm is very interesting, and I wish the authors had investigated at least several small additional domains to see whether they get a good advantage there (again, to me Diplomacy is a very interesting domain, but to show true value you need to show the approach generalizes further, even to multiple simple games). \n\nEmpirically, I also find the results a bit mixed (or rather, the current write-up overclaims with respect to what the results actually show). The two player case is a two player zero sum game. For such games, computing a Nash equilibrium is polynomially solvable (using for example a very simple linear program). In Diplomacy, the action space is enourmous, so this direct approach does not work, but there are other tractable alternatives. Hence, I find this part of the paper a bit less interesting or surprising. The 7 player variant does indeed look far more challenging, but in this case, the results are mixed. The more realistic scenario is the one where you can place one of your agents in a tournament, but the remaining players would be controlled by other players (it is unlikely that you would get to control six out of the seven players in each game). And in this scenario the performance of the agents is not as strong. The authors consider this some form of an equilibrium selection problem, but I'm not sure this is really the case. Either way, it'd be good to include multiple existing bots in such tournaments. \n\nOverall I quite like the paper, as it proposes interesting algorithms. But the claims seem a bit to strong to be justified by the existing results. Also, the key success here is not constructing much stronger agents that those available before, but rather doing so without imitation learning, in a nice algorithm that draws inspiration from existing approaches, and I'd feel much more confortable with this kind of a presentation. \n\nThe paper is reasonably readable (in particular the discussion of existing methods). It would be good to have a high level figure of the building blocks of the algorithm, and a table comparing this DORA agent with existing approach (the key building blocks they use, whether it is a supervised learning method or RL or a combination, does it use human data, runtime etc).\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper adequently adresses this (really this is a board game, I do not see how a good AI for playing a board game would have negative societal impact). ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "15sXv-s_K_", "reviewer": "Reviewer_k87e", "summary": "Diplomacy is a complex 7-player strategy game that poses a challenge for RL due to its simultaneous moves and combinatorially large action space. In recent years significant progress has been made on learning human-level play by starting from imitation learning on a dataset of human play from websites, and then using some policy improvement algorithms. This paper tackles the exploration problem, introducing a policy improvement algorithm that reaches competitive-quality play without requiring a dataset, using Nash Q-learning, a double oracle-like method, regret matching, and geographically local perturbations for action proposals. They also find advantage from switching to a transformer-based architecture.\n\nTheir method (DORA) exhibits strong results in 1v1 human play, as well as being the first from-scratch agent able to play on par with DipNet (an imitation baseline) in a 1v6 setting, in a metagame that DORA wasn’t trained in.\n\nSeparately, their policy improvement method on top of an imitation network beats previous SOTA (SearchBot).", "questions": "", "limitations": "", "rating": 8, "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": "This paper addressed a significant shortcoming in the existing literature: the equilibrium selection aspect of Diplomacy could not be explored because competitive algorithms couldn’t get off the ground without human play as a starting point. Therefore, any moves that were outside the human play distribution could not be explored effectively. This is an important contribution. It’s not very surprising, but it is great to see that a clever type of local perturbation is able to find good action proposals and explore the action space.\n\nThe paper established strong results in three regimes of no-press Diplomacy: France v Austria, 7-player Diplomacy within the human metagame, and 7-player Diplomacy “from scratch”. These need to be understood separately.\n\nThe 1v1 result is very convincing, being evaluated in a well-explained way using expert human players, and surpassing them overall. The paper tackles the key problem for this game variant.\n\nThe 7-player from-scratch result is also well-presented and impressive, and novel, building on a novel sampling-based generalization of double oracles to reach a new equilibrium in which existing human-data-based agents are beaten, while still performing reasonably well in the human-data metagame.\n\nThe seeming SOTA result using human data (rather than the double oracle action exploration method) is also very interesting, and the paper would benefit from more data and exposition of what makes up that substantial advantage over SearchBot; for example whether it’s an improved policy at inference time (with comparable computational cost), or whether it’s due to the Deep Nash Learning on top of the imitation network.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "04F-ND9XlV", "reviewer": "Reviewer_xC8k", "summary": "This paper describes an algorithm that trains agents through self-play with no human data and no reward shaping, and can accommodate the large action space of Diplomacy. It is an algorithm for action exploration and equilibrium approximation in games with combinatorial action spaces. This algorithm simultaneously performs value iteration reinforcement learning while learning a policy proposal network. Meanwhile, a double oracle step is used to explore additional actions to add to the policy proposals. They train an agent completely from scratch for a 2-player variant of Diplomacy and show that it achieves superhuman performance. They also train an agent for the 7-player no-press Diplomacy entirely from scratch with no human data for the first time and show that this agent differs radically from past agents that required human data. This approach therefore opens up the ability to investigate novel ways of playing the game.\n", "questions": "", "limitations": "", "rating": 6, "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": "The idea of approximating Nash equilibrium limited to a candidate actions set and leveraging a modified double oracle mechanism to introduce novel actions for exploration is original and feasible to deal with large action space. In experiments, their agents trained without human data achieve superhuman performance in a 2-player variant of Diplomacy and converge to an equilibrium in 7-player no-press Diplomacy. While some intuitive explanations are given, the theoretical support for the proposed approach is still weak. The following are comments that the authors need to address.\n\nMajor comments: \n\nIn line 170, as you regress the policy proposal network toward the NE policy profile using cross entropy loss, why do you need the policy proposal network? Why not directly use the NE policy profile to generate a candidate action set?\n\nIn line 160 a candidate action set at state s is generated by sampling N_b actions from policy proposal network \\pi and selecting the N_c actions with highest likelihood. Why not just sample N_c actions from \\pi? \n\nAs described in Section 4.2, the model closely follows the encoder-decoder architecture of [9]. Beside replacing graph convolution-based encoder with a simpler transformer encoder, the adjustments to the model architecture contain removing dropout layers and using seperate policy and value networks. Therefore, in Section 5.1, more ablation studies are required to distinguish the contributions of these adjustments to the performance of the agent.\n\nIn line 311, you mentioned that “in a competitive multi-agent game where agents must temporarily ally and coordinate, one expects that there may be a large number of different equilibria that are mutually incompatible”. Is there any theoretical support for this statement? It is better to provide more analysis and a more concrete image of the different equilibrium.\n\nSince the experiment on the 2p0s variant of Diplomacy is one of the main results, more detailed information about the game (FvA) should be provided, such as the number of locations, the average number of possible actions per turn, etc.\n\nMinor Comments: \n\nWhy is there a discount factor in the update rule in equation (5), but not in the definition of state value function in line 86?\n\nThe symbol v in equation (4) is undefined. \n\nThe equation (5) is confusing. According to line 154 where you redefine r to be a function of just the next state, r(s) should be r(s’). \n\nThe term “2p0s games” is used several times without definition. Even if I can get it could be 2-player zero-sum games. \n\nIn the second line of Algorithm 1, why does the function SAMPLEACTIONSFROMPROPOSALNET() include N_p as an input? As you described in line 191, N_p should be the number of actions in the pool generated in DO.\n\nIn line 242, more description for the first actor-critic method based exploiter agent is required.\n\nIn the column of Austria in Table 1, it is strange that the variance-reduced average score has higher standard error than the raw average score. \n\nIn Table 3, what kinds of Architecture is used? If Transformers are used, the result seems not better than those in Table 2. \n\nIn Table 4, it is unclear about the architecture of Model 1 (a trained value network with a fixed proposal network).\n\nIn line 486, “It is essentially identical to the architecture in [10]”, the main paper is [9] ( see line 226).\n\nIn Appendix B, the theoretical convergence of Deep Nash Learning in 2p0s games is only guaranteed in the tabular setting and when the candidate set contains all legal actions. However, under the condition of large action space, these assumptions appear to be contradictory to the main problem this paper likes to solve. \n\nIn line 511, based on the Bellman equation in reinforcement learning, the relation between Q and value function should be Q(s,a)=r(s,a)+V(f(s,a)) instead.\n\nThe statement in line 573 is unclear. What is the relation between “finding a best response for only one player at a time” and “recomputing the NE”? Which step in the algorithm does “recomputing the NE” refer to?\n\nThe paragraph from line 136-142 is the same as Section 2.2 in [9].\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a self-play algorithm to learn to play Diplomacy entirely from scratch. Diplomacy is an extremely large challenge domain and as such, has previously required human data to perform competitively. The paper presents DORA which addresses these challenges with various solutions inspired by the literature: a basic change to Nash Q-learning to use (state-based) value functions, double oracle to address/prune the action space, and an equilibrium search. The paper lacks in novelty and breadth of applicability due to simply combining various known methods together for a focused application to a specific domain. Still, the domain in question is a particularly interesting one and has garnered recent interest from the MARL community. Also, the results themselves are novel, showing that DORA is enough to reach super-human in the two-player zero-sum variant without human data, but the same method applied to n-player had mixed success (unlike the case of poker). These results will be of significant interest to MARL researchers, and the paper makes valuable contribution to the community.
Decision: Accept (Poster)