Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: # Summary

The paper addresses the problem of No Press Diplomacy. It applies existing search techniques to improve on an imitation policy, which is learned with improvements on existing supervised learning methods for the domain. The resulting policy is tested against previous learned agents and humans, showing impressive results.

I recommend accepting this paper. It tackles an important multiagent environment, producing the first agent to demonstrate human-level play. While the techniques used are not especially novel, their success in a complex mixed-motive 7-player game is interesting. I have no major concerns about the paper, except for the specific claim that the agent 'convincingly surpasses human performance' - I think this is overstated and should be removed before acceptance.

 # Strengths

Diplomacy is an important multiagent domain, involving a complex action space and a mixture of cooperation and competition between players, which necessitates new approaches. Research on this domain is timely, building on recent work as well as a long history of AI research. This paper advances the state of the art in this domain.

The search method in the paper (external regret matching on a subsampled game, evaluated with on-policy rollouts) is clearly explained and situated in the existing literature. While it is not particularly novel, the successful application to this type of domain is.

Overall, the experiments performed in the paper demonstrate convincingly that SearchBot is a large improvement on policies learned from imitation, and that it is human level.
 * The results in ad-hoc play with humans are impressive. They clearly show that SearchBot is the standard of a fairly strong human player. This is a particularly important contribution in the domain of Diplomacy; I agree with the authors that performance against humans is the ultimate test, and in a 7-player game it is not clear a priori that an agent that fares well against other agents will also do well against humans.

* Play with expert humans shows that SearchBot is not overly exploitable; it is impressive that experts get well below the average result in this setting.

* The agent exploitability analysis is good, showing that SearchBot is (almost certainly) less exploitable by RL than the blueprint it is based on.

The paper is well-written; related work is addressed well, and the methods and findings are for the most part very clear.

# Weaknesses

## Experiments

I think the claim made in the introduction that it 'convincingly surpasses human-level performance' is too strong, and should be removed or clarified. The natural reading of this is that SearchBot is better than the best human players; but the results in the paper do not bear this out. The reported ranking is 23/1128, and many players in this ranking have played very few games and are unlikely to have an accurate rating. The descriptions elsewhere in the paper (such as the title and conclusions) of 'human-level performance' seem to me to be the appropriate strength of claim.

It is unclear how strong the human players SearchBot faced in the webdiplomacy evaluation were. I think it would be very useful to include some information on this, and on how SearchBot fares against players of different skill levels. This may well affect how meaningful the reported rank is; if SearchBot has overwhelmingly played rather weak players, its rank is probably not comparable with top human players, who presumably face much stronger opposition.

The paper compares to two other agents; the SL and RL version of DipNet. Previous work has compared to the rules-based agent Albert; this has the advantage that this bot is independent of human imitation data. Adding this comparison would be valuable, and would help substantiate the strong claim that SearchBot ‘greatly exceeds the performance of past no-press Diplomacy bots’.

The effects of two key search parameters - rollout length and subgame size - are investigated. However, the effect of the number of iterations of ERM on play strength is not addressed in the paper; I would like to see a similar experiment to those in Figure 1 which looks at this.

Some winrates are presented with confidence intervals, but some in Tables 3, 5 and 6 are not. These should be added.

## Reproducibility

The methods and results are generally well explained, but I think there are a few places where there could be more detail:
* The experiments which do not involve humans do not have a clear explanation of the hyperparameters used (particularly for search). A section like Appendix F should be added for this.
* The experiments between bots used the SoS rules. However, I could not find a description of the circumstances under which games were declared draws.
* The imitation learning architecture is described only as changes to previous work; I think setting out the entire architecture in an appendix would aid reproducibility, as currently the reader needs to read two other papers to reproduce this.
review_title: First demonstration of human-level performance on an important domain

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The authors consider "no-press Diplomacy", a complex game played by humans which involves (limited) cooperation and competition.

The method uses a policy and value function learned from human games, together with a test-time search. The imitation-learned policy is used both to restrict the actions considered in the search and also to roll out the leaf nodes of the search (to a fixed depth, after which the value function is used). The search process is a sampled form of external regret matching.

Several wrinkles required for good performance are clearly motivated and explained, e.g. handling low-entropy policies and large action spaces.

The authors evaluate against existing bots, against multiple human players on webdiplomacy.net, and against two human experts. In all cases, the authors algorithm outperforms its opponents.

It is not feasible to compute exact exploitability in a game of this size, or even to train an approximate best response against the searching agent. The authors therefore train an approximate best-response RL agent against both the imitation-learned policy and a distillation of the searchbot, strongly suggesting that the distilled search is less exploitable than the imitation-learned policy.

The method described is novel, but also a fairly straightforward extension of prior work to this domain, incorporating a single-ply search on top of an imitation-learned policy. Although there is nothing radically new, the combination of very strong empirical results, and clear & detailed explanation of the methods involved combine to make this a clear accept. I was particularly happy to see the thorough evaluations including bots, a field of humans, and world-class players, and an attempt at investigating exploitability. 

Comments on the paper:
* In figure 3, it might be clearer to plot the two graphs on the same scale.
* In the Qualitative Assessment of SearchBot section, I would have been interested in any comments the human experts might have made.

review_title: Human-Level Performance in No-Press Diplomacy

final_score: rating: 7: Good paper, accept
review_content: In this paper, the authors apply an interesting twist on 1-ply search to the problem of playing no-press Diplomacy. Diplomacy is an especially interesting application, because it is neither zero-sum nor two-player, in contrast to many recent AI success stories.  Before each action, they compute an equilibrium of the next step of the game, assuming that each player will thereafter play according to a "blueprint" strategy learned via imitation learning.  The equilibrium is computed using regret matching.  The resulting agent has very strong performance against both the previous state of the art bots, and against expert human players.

The paper is clearly organized and well written; I thoroughly enjoyed reading it.  The empirical evaluations are careful.  I especially appreciated that the improved blueprint strategy was evaluated on its own (i.e., without search) to clearly separate which benefits came from the improved representation vs. the addition of 1-ply equilibrium search.

The idea of finding the equilibrium for each "stage game" of an extensive form game was new to me, and it appears to be very effective.  My main concern with this paper is that I would have liked to see some sort of justification for why we would expect this to work and where we should expect it to go wrong.  The fact that Diplomacy is non-zero-sum means that we no longer have strong theoretical guarantees about equilibrium's being the "right thing" to play. Should we expect this technique to be broadly applicable, or is it exploiting something specific to Diplomacy?

The equilibrium-search approach is in contrast with simply attempting to best respond to the blueprint strategy (apparently this is the approach of [Anthony 2020]?)  How does your technique compare to this best-response technique?  I see empirical comparisons to [Paquette 2019] but not [Anthony 2020].

I was surprised by just how computationally expensive this technique turns out to be; that is surely a drawback that will need to be addressed.

Overall I think this paper makes a valuable and well executed contribution, and I recommend acceptance.  I have some further minor comments below.

=== Minor comments ===

- p.4: "We add an additional value head...": Can you give some details about the motivation behind this architecture change?

- p.6: "If the bot's performance for each of the 7 powers is weighted equally, this score increases...": this sentence didn't make sense to me.  Possibly it assumes more familiarity with Diplomacy than I have?

- p.6: "This can partly be interpreted through an evolutionary lens...": What does the ESS view add that is not already present in the equilibrium view?  I would either flesh this out a lot more or drop references to ESS entirely.

- p.6: The definition of exploitability on p.6 is wrong because it doesn't subtract off $u_i(\pi)$ (also inconsistent with definition on p.8, which appears to be correct)

review_title: A thorough application of an intriguing approach to an interesting domain

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper proposes a combination of imitation learning and search applied to the multiplayer, simultaneous-move game of no-press Diplomacy. While both techniques have been used before, even in concert, there are some domain-specific challenges: more than two players, simultaneous moves, and a very large branching factor per player. The authors use imitation of human play for value estimates and selection of candidate actions, and External Regret Matching to generate a one-step policy. Experimental validation showed the agent to have strong human-level performance, and was hard to exploit using other machine-learning techniques.

To the best of my knowledge, I agree with the author's claim that the imitation/search agent from this paper is the first to demonstrate human-level performance in the game of Diplomacy. This is a non-trivial result: Diplomacy is a large problem, and is thought to require fairly complicated interaction between players throughout a game, as well as the ability to handle the uncertainty of other player's moves. There is no claim of guaranteed performance across a general class of problems, but the paper's method seems general enough to apply elsewhere.

The writing was generally clear, although asking "could I duplicate these results?" did raise a few questions about some details.
The experimental results against humans seem well constructed, and do a reasonable job to support the claim that the agent demonstrates human-level play. The assorted exploitability-inspired experiments help support the notion that the agent's play is strong, rather than just doing well based on some peculiarity of human play.

---------- specific issues

section 2.2 "(which can also be represented as v_i(a_i, a_{-i})."
Closing parenthesis missing?

"ERM guarantees that R^t_i(a_i) in \mathcal{O}(\sqrt{t}). If R^t_i(a_i) grows sublinearly for all players' actions, as in ERM, then the average policy over all iterations converges to a NE in two-player zero-sum games and in general the empirical distribution of players' joint policies converges to a CCE as t approaches infinity."
How does the sampling interact with this? The regret bound is w.r.t. the probabilistic policy pi^t_i, but sampled a_{-i}. Connecting this bound to describe the joint behaviour (i.e., Nash eq'm) prThis paper proposes a combination of imitation learning and search applied to the multiplayer, simultaneous-move game of no-press Diplomacy. While both techniques have been used before, even in concert, there are some domain-specific challenges: more than two players, simultaneous moves, and a very large branching factor per player. The authors use imitation of human play for value estimates and selection of candidate actions, and External Regret Matching to generate a one-step policy. Experimental validation showed the agent to have strong human-level performance, and was hard to exploit using other machine-learning techniques.

To the best of my knowledge, I agree with the author's claim that the imitation/search agent from this paper is the first to demonstrate human-level performance in the game of Diplomacy. This is a non-trivial result: Diplomacy is a large problem, and is thought to require fairly complicated interaction between players throughout a game, as well as the ability to handle the uncertainty of other player's moves. There is no claim of guaranteed performance across a general class of problems, but the paper's method seems general enough to apply elsewhere.

The writing was generally clear, although asking "could I duplicate these results?" did raise a few questions about some details.
The experimental results against humans seem well constructed, and do a reasonable job to support the claim that the agent demonstrates human-level play. The assorted exploitability-inspired experiments help support the notion that the agent's play is strong, rather than just doing well based on some peculiarity of human play.

---------- specific issues

section 2.2 "(which can also be represented as v_i(a_i, a_{-i})."
Closing parenthesis missing?

"ERM guarantees that R^t_i(a_i) in \mathcal{O}(\sqrt{t}). If R^t_i(a_i) grows sublinearly for all players' actions, as in ERM, then the average policy over all iterations converges to a NE in two-player zero-sum games and in general the empirical distribution of players' joint policies converges to a CCE as t approaches infinity."
How does the sampling interact with this? The regret bound is w.r.t. the probabilistic policy pi^t_i, but sampled a_{-i}. Connecting this bound to describe the joint behaviour (i.e., Nash eq'm) proceeds easily when considering the joint pi^t. However, in this case the joint is only connected by the specific sampled actions. Does the statement about convergence to NE apply to sampled ERM (With high probability? In expectation?) or only to ERM? 

Table 1
What are T=0.5 and T=0.1?  I assume they're the temperature parameter, for action selection in DipNet, but this isn't described until later.

Figure 1, "Sampling a single action leads to poor performance"
How is the graph intended to be interpreted? In the graph, 1 search action looks to be significantly better than the blueprint.

"M_i is a hyperparameter that is proportional to the number of units controlled by player i."
Proportional how? If power i controls n units, the algorithm will sample M_i actions? M_i*n actions? k*n actions for some hyperparameter k? Please clarify this sentence.
Are the samples select independently across units somehow, or just the top orders for the round (for that possibly very large number of actions)?

"We compute a policy for each agent by running the sampled algorithm described in Equation 1 and Equation 2".
Section 2.2 describes a few modifications, one of which would seem to modify equation 2. Maybe saying instead that it is running the sampled algorithm described in Section 2.2?
How many iterations are used?

"If our agent is an ESS (or Nash equilibrium), then a population of players all playing the agent's policy could not be 'invaded' by a different policy."
Wouldn't this only apply to ESS, not Nash eq'm in general? 

Section 4.2.1
What does a sum-of-squares score of 0.54 or 0.42 represent? Are those scores good? Huge? Tiny? The drop is statistically significant. Is that drop of ~0.12 large? Small? Are we supposed to care about the drop? Or just how low they both are? Or just how low the SearchBot-clone result is?
It seems like this section would be helped by having a short summary statement of the conclusions the authors would like to draw.

Section 4.2.2
It was nice to see that the humans beat the human-imitation blueprint, while they struggled quite a bit against SearchBot. It might be worth specifically noting that not only was the blueprint imitation an improvement on DipNet in this setting, it was specifically the search method making the largest improvement.

Section 4.2.3
CFR->ERM?  The text talks about plotting versus the number of ERM iterations, while the figure talks about CFR.

Figure 3
What exactly is the average being talked about in the first paragraph? The averaging mention in Section 2.2 (which is not used during search in normal play)? The self-play strategy profile which is a combination of one strategy from each of the 7 runs (not really an average)?  Something else?
Is "average" in the first paragraph different than "average" in the right figure? The average line on the left doesn't seem to match the average line on the right: on the right, there seems to be a slight bump upwards at the end, which doesn't seem to be present on the left.

On the right plot, why not include all (or at least multiple) independent plots, to give a more complete picture of the variance?

Include some mention or mark indicating how many iterations are used during play? As is, I don't know how this graph relates to the search as used in SearchBot.oceeds easily when considering the joint pi^t. However, in this case the joint is only connected by the specific sampled actions. Does the statement about convergence to NE apply to sampled ERM (With high probability? In expectation?) or only to ERM? 

Table 1
What are T=0.5 and T=0.1?  I assume they're the temperature parameter, for action selection in DipNet, but this isn't described until later.

Figure 1, "Sampling a single action leads to poor performance"
How is the graph intended to be interpreted? In the graph, 1 search action looks to be significantly better than the blueprint.

"M_i is a hyperparameter that is proportional to the number of units controlled by player i."
Proportional how? If power i controls n units, the algorithm will sample M_i actions? M_i*n actions? k*n actions for some hyperparameter k? Please clarify this sentence.
Are the samples select independently across units somehow, or just the top orders for the round (for that possibly very large number of actions)?

"We compute a policy for each agent by running the sampled algorithm described in Equation 1 and Equation 2".
Section 2.2 describes a few modifications, one of which would seem to modify equation 2. Maybe saying instead that it is running the sampled algorithm described in Section 2.2?
How many iterations are used?

"If our agent is an ESS (or Nash equilibrium), then a population of players all playing the agent's policy could not be 'invaded' by a different policy."
Wouldn't this only apply to ESS, not Nash eq'm in general? 

Section 4.2.1
What does a sum-of-squares score of 0.54 or 0.42 represent? Are those scores good? Huge? Tiny? The drop is statistically significant. Is that drop of ~0.12 large? Small? Are we supposed to care about the drop? Or just how low they both are? Or just how low the SearchBot-clone result is?
It seems like this section would be helped by having a short summary statement of the conclusions the authors would like to draw.

Section 4.2.2
It was nice to see that the humans beat the human-imitation blueprint, while they struggled quite a bit against SearchBot. It might be worth specifically noting that not only was the blueprint imitation an improvement on DipNet in this setting, it was specifically the search method making the largest improvement.

Section 4.2.3
CFR->ERM?  The text talks about plotting versus the number of ERM iterations, while the figure talks about CFR.

Figure 3
What exactly is the average being talked about in the first paragraph? The averaging mention in Section 2.2 (which is not used during search in normal play)? The self-play strategy profile which is a combination of one strategy from each of the 7 runs (not really an average)?  Something else?
Is "average" in the first paragraph different than "average" in the right figure? The average line on the left doesn't seem to match the average line on the right: on the right, there seems to be a slight bump upwards at the end, which doesn't seem to be present on the left.

On the right plot, why not include all (or at least multiple) independent plots, to give a more complete picture of the variance?

Include some mention or mark indicating how many iterations are used during play? As is, I don't know how this graph relates to the search as used in SearchBot.

=-=  Comments after author discussion
(Minor) concerns have been addressed.  Thank you for the revisions.
review_title: Official Blind Review #4

Meta-review: All reviewers agree that this paper is very solid work, that presents great progress in no-press diplomacy. The method and presented experiments are of very good quality and the work merits to be presented at ICLR.
Decision: Accept (Oral)