Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper describes the problem of discovering and acting on "self-explaining deviations" (SEDs) when two or more agents are cooperating in a turn-taking environment such that one agent can deviate from its expected behavior in order to signal to another agent that it has private information indicating that a higher utility situation can be achieved if the other agent also deviates from its expected behavior.  The factored observation stochastic game is modeled as a public POMDP to plan behaviors for all agents jointly.  Two flavors of an algorithm called IMPROVISED are provided to enable the signaling agent to discover such opportunities and enable the signaled agent to  know how to respond to achieve the higher utility.  The approach is evaluated in the context of (1) a novel Trampoline Tiger problem, demonstrating that even in simple scenarios, state-of-the-art deep MARL algorithms like MAPPO and QMIX cannot learn to find and exploit SEDs, and (2) the card game Hanabi, demonstrating that IMPROVISED can find SEDs called finesse plays commonly used by human players but not again not learned by deep MARL approaches and rarely even by a learned model that is trained to replicate human play from observed games. 
strengths_and_weaknesses: Overall, the research is interesting and is relevant to the multiagent planning and reinforcement learning communities at NeurIPS.  The problem and solution are novel as far as I'm aware, and are also relevant to human-agent connections in AI.  The paper is relatively clear and easy to follow.

Given the lack of theoretical analysis, I would have maybe liked to see a little more evaluation on the empirical side.  I appreciated the use of two domains -- one toy problem for illustrating the challenge for state-of-the-art RL methods, as well as a more challenging game playable by humans.  But the paper generally lacked any statistical significance testing (I suspect you'll find improved performance in terms of using finesse, but it is less clear about the difference in overall game scores).  I would have especially appreciated more discussion of the other types of SEDs found in Hanabi and whether those are also categories of moves played by humans or if the algorithm discovered novel strategies that can push the boundary of human play (similar to innovations in backgammon and go by AI agents throughout the years).  Instead, the paper mentions "it can be either that IMPROVISED finds no beneficial deviations or it finds better, non-finesse SEDs".  I suspect the latter happened at least some of the time, given the overall boost in game score compared to the blueprint strategies.

Minor notes:

-- line 157: "where the Bob's" => "where Bob's"
-- line 366: "Dec-POMDs" => "Dec-POMDPs"
questions: 1) Have you analyzed any other SEDs discovered during Hanabi?  How might those SEDs be characterized, and do they follow human wisdom for the game, or have novel strategies been discovered?

2) Where there other types of deviations discovered by IMPROVISED in Hanabi that might not be SEDs?  Could the algorithm be useful for discovering and employing other deviations from blueprint strategies?

3) Have you conducted any statistical significance testing of your results (for sake of completeness of the analysis)?

4) In the Trampoline Tiger problem, is the general lack of discovery of the optimal strategy a problem of not balancing the exploration-exploitation tradeoff properly, or something else?  Given the small size of the game, I would have expected RL to eventually find the optimal strategy and then continue to exploit it.
limitations: The limitations of the approach are adequately described.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper focuses on a specific subclass of coordination problem -- self-explaining deviations (SEDs). SEDs refer to the actions that deviate from reasonable behavior but with the intention of communicating with other agents. This paper first motivates SED with a vividly real-world example and afterward gives a formal definition of it. Then they proposed a novel algorithm to perform SEDs. Their further evaluations of toy games and Hanabi show the strengths of the proposed algorithms. 
strengths_and_weaknesses: Strengths

1. **Importance of the problem**. The problem this paper considers is important. Humans have the ability to coordinate with others using minimal explicit agreement and only relying on information from normal or abnormal actions. This paper formalizes the definition of such behavior as self-explaining deviations and steps forward in this interesting topic. 
2. **Motivation.** This paper is well-motivated. SEDs are very common behaviors of humankind but are rare for AI. Explicitly incorporating SEDs into other baselines might further improve performance.
3. **The novelty of the proposed method**. The proposed method is simple but novel.  
4. **Clarity**. This paper is generally well-written and easy to follow. 



Weaknesses

1. **The soundness of the proposed method**. The reviewer thinks the assumptions might be too restrictive, in particular, Assumption 2. What if we remove Assumption 2? How likely is it that the game in real life meets this assumption?
2. **Quality and soundness of empirical evaluation**. (1) The provided results are sound, but the evaluations are conducted only on two games, including a toy game. Can the author show more results of other games or more interpretations of existing results? It is okay if the rebuttal time is not enough for the authors to do extra evaluations. (2) It seems that the algorithms and evaluations are based on two cooperative players. Is it possible to extend this idea to more players? 
questions: Some questions are listed above, and here are other questions. 

1. Is it possible to extend the idea of SEDs to more than 2 players in Definition 1?
2. Is it a common assumption that 'Bob can detect the deviation as $\mathcal{D}(b)$' in Line 211?
3. What do the dash lines between Bob in Figure 2 mean?
4. Can other search algorithms perfectly solve Trampoline Tiger?
limitations: The authors have described enough limitations of their algorithms. And completely solving these limitations might be enough for a new paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper introduces the idea of a “self-explaining deviation” [SED] where an agent does an action that is seemingly irrational with the explicit intention of getting other agents to realize that the (privately observed) state is not what the others think it is, and make them react accordingly. The authors provide a fairly generic definition of an SED, and an algorithm for recognizing such situations and altering the policy accordingly. They provide an evaluation of their approach in both a simple toy problem and the game of Hanabi where this kind of action is common among human players, and not produced by previous computational approaches.

strengths_and_weaknesses: Originality
I’m not aware of work conceptualizing anything similar to SED in either POMDP-adjacent systems, or earlier approaches to recursive modeling of the actions of other agents.

Clarity
In general the paper is written clearly, with good examples. Most of the mathematical content is also fine, although I find4.3/4.4 the most confusing part of the paper, with few examples and given that the rest is fairly straightforward. Presumably the appendix information makes this more clear.

Quality
I don’t find any obvious technical errors in the main body of the paper. There could be a greater discussion in the main body of the computational issues of the two versions of the IMPROVISED algorithm and how they would relate to general scalability of the approach. (this is pointed out in the conclusions, but nothing appears in the main body).

Significance
This is probably the biggest issue? Yes, the authors give a horrifying realistic (but extremely specific) human example, but otherwise confine the analysis to the relatively cerebral and abstract Hanabi. There is a bit of an odd focus in the current DecPOMDP/MARL literature in finding some environment that eliminates or limits explicit communication even though many practical applications don’t have that as a limitation.

questions: The evaluation is conducted in environments were you have an extremely precise model of the environment; would any of this work (even the probabilistic IMPROVISED^P) where the environment model is only learned (or, how good does the model have to be before any of this is applicable?)

limitations: Authors address this directly, no issues.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: ## Summary: 

In multi-agent, partially-observable context, human beings are able to coordinate using very few information at their disposal, e.g. "minimal explicit agreement" and conventions, and reason about new information to extend previous conventions, allowing us to perform so-called *finesse* plays in the card game Hanabi.

This paper proposes a formal definition for such behaviours under the name **Self-Explaining Deviations (SED)**, within the formalism of Factored Observation Stochastic Games (FOSGs),  after applying a public POMDP transformation "that maps cooperative multi-agent settings to equivalent single-agent POMDPs". 

Two assumptions are made though:
1. Sequential and publicly observable actions.
2. Only considers SEDs where the first player's private information is not necessary for coordination.

In short, under these assumptions, SEDs take place when, despite all players expecting a common knowledge blueprint (BP) policy (possibly a Nash equilibrium), an initial player's move deviates from the BP (and possibly from optimality), but it actually provides meaningful information that can be exploited by the subsequent players to choose moves that improves locally the performance, achieving a greater payoff.

The paper highlights the mechanics of SEDs thus defined on a toy example and proceeds to devise an optimization problem whose solving is tantamount to performing SEDs. 
An approximated search algorithm is  thus devised to solve the optimization problem in a tractable fashion, at every player's turn, it is entitled IMPROVISED.

Two variants can be formulated though, IMPROVISED$^E$  and IMPROVISED$^P$, the former is based on the both players choosing there moves by maximizing the expected return in comparison to the BP's one, while the latter enforces the subsequent player to choose its move by maximising the expected improvement over the BP's action.

Note that the proposed algorithm relies on a blueprint policy being available, as it is a search algorithm that is added in a plug-and-play fashion after deployment.

Finally, the paper investigates the proposed algorithms ability to perform a subset of *finesse* plays in Hanabi.
Note that not all SEDs are *finesse* plays. 
Comparisons are made against:
1. a Behaviour Cloning policy trained on human moves, and 
2. SPARTA, another search algorithm applied to Dec-POMDP. 
The BP policy used for that evaluation is the Behaviour Cloning policy.

The evaluation is performed in terms of number of specific *finesse* plays performed over a set of specific *finesse*-able situations. 

Results show that the proposed methods largely outperform both methods in terms the number of *finesse* plays actually performed in *finesse*-able situations.

Also, using this proposed *finesse* benchmark, the paper investigates state-of-the-art MARL agents' ability to perform those specific *finesse* plays. 
While all methods reach the same amount of *finesse*-able situations (~1.2k situations over 1k games), SAD, Other-Play, and OBL are only completing 43%, 33%, and 32% respectively. For comparison, the Behaviour Cloning blueprint reaches 85%.

## Post-Rebuttal and Initial AC-Reviewer Discussion Update:

Following the author's rebuttal, the author-reviewer discussion phases, and the AC-reviewer initial discussion phase, I mean to emphasise the following and detail how I have increased my marks:

1. Following the rebuttal, I acknowledged that the mathematical soundness/clarity issue that I was raising is **very subjective**, i.e. more a matter of taste than a matter of quality. 
Indeed, the maths laid out in the paper are of a fairly good quality, I just would have hoped for better, but I recognised that it is not necessary given that the aim is primarily to communicate efficiently the concept that are presented in the paper, which I find they do perfectly.

2. The paper does not claim reaching a new SotA result on the Hanabi benchmark, yet my statistical significance concerns were regarding the results on the full game experiment benchmark, which I find **misguided**, in the end.

3. Rather, the paper does claim initialising a SotA result on the ability to perform finesse plays on the Hanabi benchmark, and the results on that end are statistically significant, without needing to run any test, given that they show a **5-fold increase** compared to the relevant baseline of SPARTA (and the sanity-check baseline of using solely the Behavior Cloning blueprint).

Thus, in light of this, I think that I mean to champion this paper for providing an excellent theoretical contribution (in formally framing what finesse plays are) and a statistically significant numerical evidence (in showing that their proposed algorithm raises the SotA in finesse-execution testing).

I am therefore updating the marks in my review: 

* raising the mark from 6 to 8, 

* raising the contribution mark from 3 to 4,  

* raising the presentation mark from from 2 to 3.

* raising the soundness mark from 2 to 4.

strengths_and_weaknesses: # Originality :
To my knowledge, the paper is the first to (i) formalise the in-famous *finesse* plays, (ii) propose an evaluation method for them in the game of Hanabi, (iii) propose to build an algorithm to maximise the likelihood of those *finesse* plays.

# Quality:
The quality of the paper is fair.
The math seem marginally sound on the surface, but I will highlight a clarity/soundness issues below.

Reproducibility is maybe a bit lacking due to the lack of details on the limitations and dependences of the algorithm proposed (e.g. the function $f$).

I find a strong issue with the strength of the numerical evidence:

--> Line 361 : Significance : In order to assert the actual significance of these results (despite the sample size being slightly smaller than in previous papers, e.g. 10k games in Other-Play,  cf. Figure 4), (Q1) could you perform statistical analysis of each distributions using, e.g. Kolmogorov-Smirnov tests [1], please ?
This would strongly strengthen my appreciation of the work and contribution here, and I would update my mark accordingly.

Similarly, considering the comparison with SPARTA as a baseline, I think it would be important to provide rollouts and time complexity statistics, please? In order to truly assert whether your proposed algorithms win on most norms or whether there are trade-offs to consider...  

[1] : SciPy's two-sample Kolmogorove-Smirnov test : https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.ks_2samp.html

# Clarity & Soundness: 
I have found the paper to be mainly well-written and to fairly substantiates its claims, but there are a few minor and major issues I would hope to see addressed: 

--> line 60: need to specify $N \in \mathbb{N}$ as the number of players/agents

## --> line 153 : Soundness & Clarity : Timestep in FOSG VS in single-agent public POMDP :

Given the public POMDP transformation, aren't the players playing simultaneously for the joint decision rule to be defined? 

I fail to understand what information are the joint decision rule actually considering. 
Indeed, the notation defined around line 84 highlights that the joint decision rule is only using as input the set of information state sets over all players, but the equations (4) and (6) that defines how Bob plays highlights a dependence on Alice's action $a_1$ which is not part of any information state set yet, since it corresponds to a constituant of the next single-agent public POMDP timestep, no?

Or, alternatively, could you clarify when are the information state sets being updated?

I think it brings us back to how the history is being defined as its reliance on the time step $t$ , in the FOSG, makes it ambiguous between each player's turn, if they play sequentially ? 
i.e. Alice plays at time step $t$ and Bob at time step $t+1$ in the FOSG, but the joint decision rule in the equivalent single-agent public POMDP  lacks clarification of when are the information state set computed, maybe?

(Q2) If you understand the soundness and clarity issue that I raise here, then may I propose the following:
1. For clarification, it mind be better to state the Assumption 1 with respect to the FOSG (and maybe place it in the text before introducing the public POMDP transformation).
2. For soundness, it mind be better to rewrite the joint decision rule as $a \equiv \Gamma(s_1^{t}, s_2^{t+1}, ... , s_N^{t+N})$

## --> line 177 : Clarity : Function $f$ :
(Q3) Could you clarify how is $f$ computed? Is it shared between players? 

I remember line 173 stating that it is 'determined by the algorithm designer', but I am not sure I understand the meaning: does it mean that it is like an hyperparameter that needs to be provided for the algorithm to work? 
If so, I would flag it as a critical limitation that needs to be discussed and better detailed, please.
I would welcome a very detailed table maybe showing the mapping that this function performs, if it is relevant?


## --> Equation (1) : Clarity & Soundness : Operator $\circ$
I think that leaving the $\circ$ operator undefined is hurting the clarity and soundness of the claim.

Indeed, its usage on $\Gamma_1$ is ambiguous as $\Gamma_1$ outputs on action $a\in\mathcal{A}$, which is not from the input space of $\Gamma_2$.
I think this boils down to the lack of rigour when stating the dependencies of the history on the timestep $t$ (in the FOSG), e.g.--> line 67 : rendering the the history variable as  $h_t$, given the dependence on the time step $t$ in its constituants. And therefore, the information state set would need such an addition too...

## --> line 234-237 : Clarity : Optimality Argument lacking substance
I am afraid I do not understand the optimality argument that is made in this paragraph. Could you clarify further please, as it is fairly central to the contribution, right? 
(Q4) Could a proof of the optimality be in order, or maybe just the use of some formalism to ground the text to the equations discussed so far, please? 


## --> line 244-245 : Clarity : Jensen Inequality & Alice's conditional behaviour
I am afraid I do not understand the causality link made by this piece of text, nor how Jensen's inequality illustrates Alice's conditional behaviour. It might be obvious but I unfortunately cannot see it in the present form, thus (Q5) may I request a clarification, please?

--> line 245: clarity : shouldn't it be an argmax instead of max?

## --> Figure 3: Result Transparency :
I would suggest the author to display their algorithms' results in Figure 3 (as well as the training curve of the blueprint Behavior cloning alone as a baseline, maybe?), in order to be complete and transparent.

## --> Table 1.b : Clarity and Soundness : Major Issue/Misunderstanding 
I fail to make sense of the Blueprint policy suddenly performing 0 finesse out of finesse-able situations, while it is shown to perform 85% of those as presented in Table 1.a. 

(Q6) Or could it be that I am making a confusion between "situations where a finesse play is performed" and finesse-complete situations, don't they mean the same?
Could it be that they are different depending on which player's action is being evaluated, i.e. the player that initiate the finesse play and peform an SED being opposed to the player(s) who recognises the SED and acts accordingly.

In any case, I would recommend the authors to try to better organise (with subtitles or bold summarising statements at the start of paragraphs, maybe?) the Section 5.4 ; it was difficult to read and make sense of, I must confess :S. 
Maybe all the information are too densely packed in, it might need more breathing room for some examples, e.g. an example of the typical play being evaluated with a turn-by-turn analysis.

Also, the more I read the paper, the more I am pondering whether evaluation for finesse (in the general sense) should be addressing each players' turn separately?
Indeed, I am assuming it is one thing (a) to realise that a finesse (coordination) play can be performed in a given situation and then be the one to initiate it (player 1), but it is an entirely other thing (b) to be able to understand the resulting SED that occured and choose the right move to maximise payoff (player 2), no?

I am still feeling confused by the function $f$, which is involved in (b) for more than half of the task. I feel the need for it to be better detailed, in that regard too, please?


# Significance :
Most of the results provided may be more compelling if the sample size was similar to previous papers.
That being said, the theoretical significance of the paper is high, but I would really like to see the significance of its results be better asserted.
Please consider addressing the following points:

## --> Line 353 : Missing Results for Human-Cooperation Significance :
What about IMPROVISED$^P$, since it is more valuable for cooperation with humans?

Could you report the number and percentages of finesse-able / finesse-complete situations encountered during these 100 games, please? like in Table 1.a

I think that it would be important to perform this evaluation on a greater number of games, similarly to previous works, in order to assert the statistical significance of the results.

## --> Line 356 : Selfplay vs Crossplay & Zero-Shot Coordination :
As only selfplay scores are presented, it is unclear whether the blueprint agents have developed idiosyncratic policies or not (especially if the behavioral cloning training data only contains one pair of players, for instance ?).

Thus, to provide more transparency and be more in touch with the MARL field's dilemma at large (of which zero-shot coordination is a major problem, especially on the Hanabi benchmark), could you present crossplay performance results (with differently seeded blueprint agents), like in the Other-Play paper, for instance, please? 
Unless maybe it is irrelevant as the algorithm your propose manually computes its own belief at every move and the Monte Carlo rollouts are robust to noise, or something of the kind?

I understand that this is going the extra step, and I would not mind if the authors were not able to address it...

## --> Line 361 : Significance : Statistical Significance Tests :
see section Quality above...
questions: Please see section above for the major questions that are denoted (QX) with X being a digit. 
limitations: I believe the authors have mainly adequately addressed the limitations and potential negative societal impact.
Nevertheless, I would welcome the paper to discuss further the possible limitations of the design, such as (i) the reliance on the shared function $f$ and the fact that it is chosen by the user, or (ii) the reliance on a blueprint policy (e.g. does it have to be the same for all players, and to what extend?), please?
review_title: null

Meta-review: metareview: The reviewers carefully analyzed this work and agreed that the topics investigated in this paper are important and relevant to the field. All reviewers generally shared a positive impression of this work. One reviewer mentioned, as possible limitations, the lack of theoretical analyses and more empirical evaluation. They also (initially) pointed out that the paper lacked statistical significance testing. After the authors' rebuttal, however, the reviewer said they better understood some aspects of the paper, that they appreciated the additional statistical testing analyses, and suggested adding more discussion on such points. Another reviewer agreed that this paper investigates an important problem and that it formalizes many relevant related concepts. As limitations, the reviewer said that the method requires assumptions that may be too restrictive (e.g., Assumption 2). They were also concerned since evaluations were conducted on only two games, one of which is a toy domain. Nevertheless, the reviewer was satisfied with the authors' responses. A third reviewer acknowledged that this work is novel, that the paper is well-written, and that its mathematical contents are well presented. After reading the authors' rebuttal, the reviewer was still concerned with the fact that the computational costs were discussed only for specific runs (and are a significant limitation, as the authors noted). This, the reviewer believes, suggests that the method might have somewhat limited practical applicability. A fourth reviewer brought up many technical questions as part of their review, which (at the time) they thought had not been adequately addressed in the authors' rebuttal. However, the reviewer later said that some of their criticisms regarding the formalization proposed in the paper were not a sufficient reason for rejection. They recognized that resolving such issues was not necessary given that this work aims primarily to communicate the main high-level ideas introduced by the authors. As final feedback to the authors, this reviewer suggested that the authors could provide an open-source implementation of the finesse-execution testing benchmark, so that subsequent works can build upon this new metric and evaluate their algorithms against it. Overall, thus, it is clear that most reviewers were positively impressed with the quality of this work and look forward to an updated version of the paper that addresses the suggestions mentioned in their reviews and during the discussion phase.
confidence: Less certain
Decision: Accept