Self-Explaining Deviations for Coordination
Authors: Hengyuan Hu
Samuel Sokota
David J Wu
Anton Bakhtin
Andrei Lupu
Brandon Cui
Jakob Nicolaus Foerster
Venue: NeurIPS 2022 Accept (2022)
Keywords: multi-agent
planning
zero-shot coordination

Abstract: Fully cooperative, partially observable multi-agent problems are ubiquitous in the real world. In this paper, we focus on a specific subclass of coordination problems in which humans are able to discover self-explaining deviations (SEDs). SEDs are actions that deviate from the common understanding of what reasonable behavior would be in normal circumstances. They are taken with the intention of causing another agent or other agents to realize, using theory of mind, that the circumstance must be abnormal. We motivate this idea with a real world example and formalize its definition. Next, we introduce an algorithm for improvement maximizing SEDs (IMPROVISED). Lastly, we evaluate IMPROVISED both in an illustrative toy setting and the popular benchmark setting Hanabi, where we show that it can produce so called finesse plays.


Self-Explaing Deviations for Coordination
Hengyuan Hu*t Stanford University hengyuan @ edu
Samuel Sokota"
David Wu Meta dwu @ meta.com
Carnegie Mellon University ssokota andrew.cmu.edu
Anton Bakhtin
Andrei Lupu
Brandon Cui! Mosaic ML brandon @ mosaicml.com
Meta AI yolo meto@meta.com
Meta Al & FLAIR, University of Oxford alupu meta.ccmmm
Jakob N. Foerster
FLAIR, University of Oxford jakob.foerster wen.@enngg... on..ox.ac.uk
Abstract
Fully cooperative, partially observable multi-agent problems are ubiquitous in the real world. In this paper, we focus on specific subclass of coordination problems in which humans are able to discover self-explaining deviations (SEDs). SEDs are actions that deviate from the common understanding of what reasonable behavior would be in normal circumstances. They are taken with the intention of causing another agent or other agents realize, using theory of mind, that the circumstance must be abnormal. We motivate this idea with real world example and formalize definition. Next, we introduce an algorithm for improvement maximizing SEDs (IMPROVISED). Lastly, we evaluate IMPROVISED both in an illustrative toy setting and the popular benchmark setting Hanabi, where we show that it can produce called finesse plays.
Introduction
Humans generally assume other humans follow certain social norms when acting in the society and interpret behavior using these norms to infer hidden information about the world. For example, when driver sees ahead or the car is broken. However, humans also have the ability to improvise when the conventional actions restricted there exist other actions that bring about superior outcomes. Taking the event Figure | as an example, the caller deviates from the conventional practice of stating the situation truthfully because it would have negative consequences. This type of deviation involves two noteworthy aspects. First, can be detected by the dispatcher because it appears to be a mistake under common practice. Second, the dispatcher's response can be independently decided by both individuals based on the common understanding of the world and the deviation chosen by the caller.
ahead suddenly stopping
road, they may infer that there is some accident
We refer to this type of phenomena self-explaining deviations (SEDs). SEDs are actions that, under normal circumstances, would not make sense, given the agents' common understanding. They executed with the intention that teammates will use theory of mind deduce that the situation unusual in a particular way, and will adapt their behavior to account for this additional information.
"Equal Contribution.
1 Work done while at Meta
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Dispatcher: Oregon 911.
Caller: I would like to order pizza at...
Dispatcher: You called 911 to order a pizza?
Caller: Uh, Yeah, apartment...
Dispatcher: This is the wrong number to call for a pizza.
Caller: No no no... you're re not understanding me.
Dispatcher: I'm getting you now. Is the other guy still there?
Caller: Yep. I need a large pizza.
Dispatcher: All right. How about medical. You need medical?
Caller: No. With pepperoni.
Dispatcher: Turn your sirens off before you get there. Caller ordered a pizza. And agreed with everything I said that there's s domestic violence going on.
Figure 1: real-life self-explaining deviation.
For contribution. we first formalize the problem setting and definition of SEDs. Then we introduce a novel planning algorithm, IMPROVement maximizing Self-Explaining Deviations (IMPROVISED), for performing SEDs. We show that, under some assumptions, IMPROVISED performs the optimal SED in terms of expected return maximization. Next, we provide a motivating experiment, illustrating that in a small toy problem designed to require SEDs to perform optimally, IMPROVISED is able to compute an optimal joint policy, whereas other multi-agent learning algorithms are not. Lastly, we present experiments on the large scale benchmark Hanabi (.. where we show that IMPROVISED is able to produce finesse plays, which is one of the most interesting techniques that human experts perform frequently.
Background
FOSG and Public POMDP For our notation, we use an adaption of factored observation stochastic games (FOSG) 77. W is the set of world states and w² is a designated initial state. A Ai x.....X. AAN AN is the space of joint actions. T the transition function mapping W x A - A(W). R: W x A + IK is the reward function. O (Oprv())..... (N). Ppn) is the observation function where O Opivt):: W x A W - (prv(s) specifies the private observation that player i receives. Open W A W + Opuh specifies the public observation that all players receive. O,-O,(w,dd a, (O pao(e) (w, a, w'), (w,, w')) is player i's observation and a history is finite sequence h (w a ..... w²). The set of histories is denoted by H. The information state for player at h (wo, 0 ...., w²) is (h) = (0,, ....... Ot). The information state space for player i is S; = {s:(h) h H). The legal actions for player at 8; is denoted A, (s:). A joint policy is tuple π = (TI. TN). where policy π; maps S + (AA)). The public state at is the sequence Spus (h) = Span (s:(s)))) = (O0 puhs..... Ot.)). The information state set for player at E Spbs is (s) = {s; S, Spup (p s}. where Spub is the space of public states. Finally, the reach probability of under π is (T().
Rather than working with in multi-agent setting directly, we invoke the public POMDP transformation that maps cooperative multi-agent settings to equivalent single-agent POMDPs. Given a common- payoff FOSG (N,W, w", A, R, O), we can construct equivalent public POMDP IC (W, t0 Á. R, θ) follows: The world states of the public POMDP W is the set (s)..
h H}. The initial world state of the public POMDP n is the tuple (s1(h") ".......(((())) (h")).
The actions of the public POMDP are called joint prescriptions. components. The ith component of it Т; is the prescription for player i. A prescription T; maps 8; to an element of As(s,) for each 8; E (h)): it instructs a player in the common-payoff FOSG how to act as a function of its private information. Given w (S1, 8n) and I, the transition distribution (w. I') is induced by T((s sn), a). where = I((s)..... sn)) =
denoted by I and has N
Given ih ($1...., Sn) and vt (s',...,,', s,), the reward and observa-
II'' original game sequential, prescriptions for non-acting players map "no-ops".

---

tion are given by R(Ø, r, 20 R((s1.... sp), ((( (s)...... and O = Pur
S,)), (s)..... 5)), respectively.
Every policy in the public POMDP corresponds to joint policy in the underlying common-payoff FOSG, which receives exactly the same expected return. Therefore, it is sufficient work with the public POMDP. See
14 |5
for further discussion.
When the public POMDP is considered of the form b²: (sf...., st) + pr p...__ (sf, ................................ s'y s(us). In words, this is the joint distribution over private information states, conditioned on the historical policy (T") ,T.....,T" I.-)) and the public state sun. This public belief MDP is abbreviated as the PuB-MDP.
belief MDP, rather than POMDP, its belief states are
3 Self-Explaiingg Deviations
While the name self-explaining deviation (SED) is novel to this work, the idea behind SEDs is not. One example of SEDs comes from the cooperative card game Hanabi [1] in the form of a play called "finesse". Readers unfamiliar with Hanabi and finesse may first jump to Section 5.2 and Section 5.3 for the detailed descriptions. In a finesse play, the acting player, i.e., the first player who initiates the deviation as part of the finesse, intentionally communicates misleading information to receiving player, which would hurt the team's 's score if the receiving player acted upon it using the established convention. The second player in the finesse, who acts after the first player but before the receiving player, realizes that the first player must have deviated from the established convention after observing the seemingly disastrous move. Knowing that the first player rational, the second player realizes that there must be way that they can also deviate to reach better outcome than the one that the original convention would have led to. After the second player plays its part of the joint deviation, the original information from the first player is no longer misleading and the subsequent players can continue follow the prior conventions.
SEDs may take place in any cooperative situation with at least two players where common knowledge blueprint policies that players follow under normal assumptions exist. Intuitively, SEDs capture a form of joint deviations where one agent takes an action that at first appears to be a mistake or otherwise highly off- off-policy from another player's perspective, i.c. zero or low probability under the blueprint. On the presumption that the first agent chose that action intelligently and deliberately and there an off-policy action for the observing agent that could potentially result in an even-better-than normal outcome for both, the observing agent may reason that the first agent "intends" them to take it to take leap of faith that the first agent has not erred, but rather knows both agents can get that better outcome, even if the observing agent does not have the information themselves to prove that this outcome will result. This work uses the term SEDs to describe this phenomenon of communication via apparent mistakes in a general context. We formalize SED in Section 3.1 and propose IMPROVISED, a novel planning algorithm that performs the optimal SEDs under some assumptions, in Section
3.1 Examining Self-Explaining Deviations
We are now ready to investigate SEDs. To facilitate investigation, let's consider the trampoline-tiger game in Figure aa an exam- ple. In this game, Alice is standing while Bob stands on the ground next to a lever. Pulling the lever will either deploy trampo- line below the balcony, or release a tiger. From above, Alice can observe which is the case, and then Alice decides whether to jump off the bal- cony (Y) or not (N). Bob observes Alice's choice but does not know whether the lever will deploy a trampoline or tiger, and decides pull the lever (Y) or not (N). Alice wants to get down from the balcony but will die from the fall un- less Bob pulls the lever and it releases trampo- line. If Bob pulls the lever and releases tiger,
10%
balcony,
Alice
jumps?
Bob
Bob
Bob
Bob
Noth happera (0)
Bob Eaten (330)
Alice Crashes (+10)
Allon Exaehes and Uata Exten (-220
Alkzn Lands on Ttampoline (12)
Figure 2: Alice knows whether Bob's 's lever will deploy tiger trampoline, and then jumps or not. Bob observes only Alice's action and then pulls the lever not. Dotted lines between two Bob nodes means that Bob cannot distinguish them.
it will eat Bob.
3

---

Consider the joint policy (* + HHN N). While not optimal, this joint policy is not unreasonable, as Bob won't 't be eaten and Alice won't fall her death. Indeed, independent of the probability of trampoline, this joint policy is a Nash equilibrium. In addition, as we shall see in Section 5.1 range of MARL algorithms converges to this solution. However, there is a clear opportunity for SED under this blueprint. If there is a tiger, Alice should obviously never jump. So if Bob observes Alice choosing to jump and trusts that Alice intelligent and would only have chosen to jump if it could lead to a better result, Bob should realize that there must be trampoline. Therefore Alice should trust that Bob will pull the lever she jumps, as a result.
Under any planning algorithm that considers only unilateral deviations, Bob and Alice can't escape the original local optimum. Alice will never jump because she under the belief that Bob will choose not to pull the lever. Therefore, finding SEDs in general requires considering multi-lateral deviations, iee. simultaneous deviations by more than one player.
Since finding multi-lateral deviations in general games with partially observable state is a complex problem, we restrict our focus to settings satisfying the following assumptions:
Assumption 1. We assume sequential and publicty observable actions.
SEDs may still be possible with partially-bbeeraable actions, but for simplicity we focus on when Bob can directly observe Alice deviate from the blueprint, rather than having to deduce it from partial or incomplete observations.
Assumption 2. We consider only cases where Bob's 's private information is not necessary for coordi- nating on the SED.
For simplicity, we always refer to the first player who initiates the joint deviation as the Alice and the second player who figures out Alice's intention and plays their part of the joint deviation Bob in the following discussions beyond the scope of this toy game. In other words, we only consider SEDs where Bob needs only act as a function of the common-knowleee state and the Alice's action, rather as function of private knowledge of their own.
Under these assumptions, define the SED follows:
Definition 1. Given a common knowledge blueprint (BP) policy म, common public belief of Alice and Bob b, and information state of Alice 81, SED is any pair of joint deviations (a', db) for Alice and Bob that satisfy all the following conditions:
(b, 81, ai,, ab)== 2 (b, $1). i.e., gives higher expected future return than BP; P(a'l n. b) S e, i.e., at is highly unlikely under π under the common belief;
dh f(b, d²),, i.e. al is a functinn of the public belief and Alice's 's deviation action.
Here, (r 81, a2)) Alice's estimate of the expected future return after executing the optional a1 and following afterwards, and e is a hyper-parameter algorithm designer under the constraint that f only takes and a' as input. It is used both by Alice to predict Bob's response and by Bob to decide the response independently.
The function f is determined by the
4 IMPROVISED
In this section derive IMPROVISED, algorithm to perform the SEDs. The core of the algorithm is to find function ff under the constraint of SED and an optimization procedure that Alice uses to decide whether to deviate given her information state s1 and possible responses a2 f from Bob.
4.1 Defining the Optimization Problem
With the observations in the prior sections, we are ready to write selecting a SED as a PuB-MDP optimization problem:
max max qm (b, [2), q- (b)l
11,1's
max Egyss max ( (b, $1 Ii (2).
Fi.T2
max Esyse max (a (6, (()) (6..))) 11,

---

where 111 is the prescription for the acting player at current time step and I2 is the prescription for the acting player the subsequent time step, denotes function composition, and, in accordance with Definition generic multi-lateral search in the PuB-MDP. The LHS is ranging over Alice and Bob's preseriptions such that, if Alice uses 1 and Bob uses 22 in belief state b, and all the players play according to thereafter, the expected return maximized. The first equality holds simply based on the fact that Alice is able to observe 8 and the fact Alice can always decide to opt into the blueprint (because Bob knows which actions are supported by the blueprint, he can opt in exactly when Alice opts in, and play according to the deviation otherwise). The second equality holds by applying Assumptions D and which imply both that Bob can observe Alice's 's action and that is the only thing he needs to condition his decision upon (note that the change of the set over which r2 ranges is left implicit).
2 ranges over the space of Al. The series of equalities above begins with
4.2 An Easier Special Case
Unfortunately, expression ① remains difficult to optimize, as the number of I and 2 is combinato- rial. To ameliorate, we can apply the simplifying constraint of only allowing Alice and Bob to deviate for a single action pair regardless of Alice's information state $1. For simplicity, we also set O. Let (bb be the set of plausible deviation actions for Alice, i.e., action that cannot be played under blueprint: D(b) == {a1 E A [Vs1 E [a]](1) [81) = 0}. Let be the set of all plausible actions that Bob can play in response in every possible state, i.... R == Neyes, A2())) If R 0, Alice will skip searching for SED this turn and follow BP. Now we can augment the expected value of a
deviation with the allowed range of actions:
gxx (b, 81, 01, 02). if a E D(b), a2 E R, otherwise.
i- (b, 81, 01, 02)
(2)
-0, x0,
Then rewrite equation using our newly defined function as follows:
(ai, a5) = argmax,, a .a Es max[g= (b, $1, a1 a2), 9u (b, s1)].
(3)
These values could be found in O([s; | A2l) time, given the two inner functions. Moreover, as all of these depend only on the public belief state, both players can compute them independently, assuming that there are no ties.
Once the deviation pair is computed, Alice decides whether to proceed with the deviation or not given her private information: Alice plays aj (= 81, aj, a5) > (=(b, 81) and the blueprint action otherwise. It is possible that (a), a5) is not valid deviation pair if no plausible deviations exist, e.g., af could be outside of (6)). However, in this case gx (b, 81, aj, aτ) is - -oo, and so Alice will resort to playing blueprint. Bob can detect the deviation ((b) is public knowledge and aj E D(b). Therefore, depending on his observation, he can either play az or respond as usual.
We can represent the value of the policy that allows single deviation at b and plays blueprint afterwards as: ot (b) = maxa; aaz Es,<d max[q= (b, $1, a1 02); 9n (b, s1)]. It is easy to see that &f 2 qn i... this algorithm has weak policy improvement guarantee.
If we apply this procedure the tiger-trampoline game with blueprint policy that always no-ops:
thr (b)
max E,,~b max [4 (b, 81, 01, a2). 9z (b, s1)]
.1.4g
max P(tiger) max (b, tiger, a1 02),
01,02
P(trappoline) max(q (b, trampoline, a1, (2).2)) 0)]
P(rrappoline).
As expected, we obtain a policy improvement with value equal to the probability of a trampoline. We discover the SED where Alice jumps when trampoline is present and Bob pulls the lever. We provide a proof-of-principee implementation of IMPROVISED in the trampoline-tiger game that can be online https::
4.3 Coordination by Extending Conventions
In coordination context, we cannot require Bob to perform arbitrary symmetry breaking, i.e., choose an action among several with the same expected value. For example, consider a case in which
5

---

set of multiple action pairs tied for having the maximal value {(a1 = =I (), I, = 2), (a, w, 02 2.}. Say that Alice picks a z. This problematic for Bob because he has no information about whether Alice is selecting x: because she is in information state in which (x, v) good or whether she is in an information state in which (x,, 2) is good (the states for which they are good may be disjoint).
One way resolve this issue force Alice to respect Bob's inability break ties by making the response function stochastic, c.g., softmax over the expected values. That is, given that Alice deviates with 01, Alice assumes that Bob plays
a softmax [Eai~ max (ix (b, 81, (11 (2), 4w (b, 81 s1)]/t]
with temperature hyper- sypee--aramettr t control the sharpness of the distribution. Then Alice chooses to deviate using
argmax,, E, (at Qx (6, $1, 01, a2), dr (b, st)].
(5)
Bob can either play according to the softmax or select the single maximum, as Alice has already picked the deviation assuming that Bob cannot break symmetries.
4.4 Taking Alice's Information State Into Account
Our discussion above has largely ignored the fact that Alice can perform different deviations given her information state $1 (i.e., private observation). Define the response function f(b, a1) softmax,, [E.,>b = (b, $1, a1 a2),)22.0. 4r (b, st]]/t]. Given that Alice knows Bob will respond ac- cording 02 f(b,a1), a1), Alice is free optimize her action by taking her information state back into consideration. By applying Jensen's inequality, we observe that
max Eg, wo max Eng- 9n (b, $1, a1 02), 9m (b. $1)
E max max [Euz (0h.e)) gr (b, 81, a1 02), qu (b. si)]
Therefore, at information state 81, Alice opts out of the blueprint if the optimal deviation action, aj maxa, (b,a)( qz 81, 41, a2), exceeds the expected return of the BP, (b, 81). This is the final formulation IMPROVISED Please refer the Appendix for the detailed pseudocode.
We also define IMPROVISED* where Bob plays according to the probability of improvement
a ~ softmaxo, [E.,~b / (qx (b, $1, a1, a2) qx (b, s s1)]/t]
(6)
where / the indicator funetion and Alice selects any action maximizing the expected improvement. While IMPROVISED does not maximize the expected return as IMPROVISEDE does, may better reflect human SEDs since it finds deviation pairs that maximize the probability of improvement.
Experiments
We test the IMPROVISED in two different settings. The first setting is the trampoline-tiger game explained before. Secondly, we apply IMPROVISED to three-player Hanabi, where we start from a blueprint trained on human data. We provide the code for our Hanabi ex- periments at pyhanabi/finesse py
5.1 Trampoline Tiger
As illustrated in Section 4.2. in the trampoline-tiger game IMPROVISED and IMPROVISED" both recover the optimal SED, when starting from the no-op BP 100% of the runs. Alice will decide to jump whenever there is trampoline and Bob then pulls the lever open the door, leading to the optimal expected return of 0.1.
For comparison, we also ran 20 unique seeds of MAPPO [88 and 24 different hyper-parameter combinations of QMIX [12] on the trampoline-tiger problem. The results are shown in Figure D All runs converged rapidly to policy that avoids the highly negative payoffs, but only 2/20 of the

---

0.15
0.10
0.00
-0,05
Meai test
-0.10
-0.15
-0.20
-025
MAPPO
QMIX
100000
200000
300000
400000
500000
Training timesteps
Figure 3:
The plot shows 20 independent runs of MAPPO (solid lines) and 24 of QMIX (dashed lines) on the tiger-trampoline toy problem. Only 2 MAPPO runs find the optimal strategy while no QMIX run does.
MAPPO runs and 0/24 of the QMIX runs discovered the optimal strategy within 500k timesteps, leading to average reward across runs of 0.01 for MAPPO and 0.0 for QMIX.
In our experiments, a variety of other standard multi- auent- learning techniques could not solve this toy problem at all, including value-decomposition network 17 and simplified action decoder 4
5.2 Hanabi
Hanabi a benchmark challenge for multi-agent coordination. Briefly, Hanabi, there is card deck consisting of 5 different suits (colors) and 5 ranks of cards within each suit, for total of 25 unique combinations, with some duplicates. Two to five players cooperatively take turns playing cards, giving hints to other players, discarding. Players may their partners' hands, but not their own The team's goal to play exactly one card of each rank in each suit in increasing order, scoring I point per successful play. Upon three plays of cards duplicated out-of-order, the players lose and instead score Giving hint spends one of shared hint tokens, allowing one to name a color or rank in partner's 's hand and indicate all cards of that color or rank in that hand. Discarding card replenishes one hint token. For a more thorough description of the rules and basic strategy see []]
5.3 What is Finesse?
clear example of SED is the finesse move in Hanabi. We will recap it briefly here, for a more detailed explanation, see [1]. For convenience, we always refer to the acting player of given turn as player I and the players who move subsequently player 2, player and so forth.
As mentioned earlier in Section B]
The standard, vanilla form of the finesse in Hanabi occurs when player gives hint player 3 (i.c. the player who moves two steps later) that, under the conventions common between the players, implics that player 3 should play particular card. Unbeknownst to player 3, that card, if played, would be out-of-order and would fail. Instead, player has just drawn the card that is both playable and if played makes player 3's card playable next. Player is expected to realize that the only way that player I's hint could be good rather than a failure player 2 themself has newly drawn this exact card, and to take a leap of faith and play that newly drawn card blindly, having explicit information about it. The end result is that player signals in only one action for both other players each successfully play a card-a a large gain.
While other finesse- like patterns are possible, in our Hanabi experiments for simplicity we focus only on those finesse moves that follow the pattern described above.
7

---

Model
Finesse-able
Finessc-complete
Method
Finesse
SAD
1375
597 (43,42%)
Blueprint
0
Other-Play
1537
512 16)
SPARTA
52
OBL (Level 5)
1100
356 (32.36%)
IMPROVISED
264
Behavior Clone
1376
1183 (85.97%)
IMPROVISED 269
(a) Number of finesse-able situations over 1000 games and % of those where player 3 will correctly respond to complete the finesse if player and 2 were forced to play the finesse move. The Behavior Clone model has much higher chance to complete finesse.
(b) Number of finesses executed by different methods at 1000 finesse- complete situations using Behavior Clone agent from Table aa blueprint.
Table I: IMPROVISED for Finesse in Hanabi
5.4 IMPROVISED in Hanabi
We design experiments evaluate IMPROVISED in Hanabi from both qualitative and quantitative perspectives. In the qualitative evaluation, we study whether IMPROVISED can indeed perform fi- nesses in manually selected situations where finesse could be completed (finese- situations). We are particularly interested in the finesse style SEDs as they are the most natural and intuitive way to demonstrate IMPROVISED's ability to perform SEDs. Note that IMPROVISED discovers many types of SEDs in Hanabi beyond the finesse style moves because it searches for any beneficial joint de- viations that when player initiates deviation, player 2 can independently figure out the correct de- viation in response. However, other types of SEDs may be hard for humans to interpret and less intu- itive to analyze and present. In the quantitative evaluation, we show that IMPROVISED as a planning algorithm improves the expected return when applied to test finesse-able situations and entire games.
To implement IMPROVISED in Hanabi, we first need a belief function from which we can sample game states given either public or private knowledge of the game to perform Monte Carlo rollouts. Luckily, the belief over possible hands in Hanabi can be computed analytically [ The belief is first initialized to cover all possible hands and then incrementally updated by filtering out hands that contradict with public knowledge revealed through hints and that would have caused the players to pick different moves at each time step. Since we are mainly concerned with the finesse style SEDs in the experiments, we restrict the search action space A1 to contain only the hint moves that target player 3 and Ag to contain only the play moves. Player I and player 2 compute their own copies of the response function f independently. The detailed hyyer-paramettes and computational cost are in Section C
Finessable Situation Experiments To check IMPROVISED's ability to perform finesse, we first generate situations where seasoned human players may carry out finesse moves. We use blueprint policy π to generate selfplay games over a range of decks (game seeds) and look for situations where player 1 observes that player 2's newest draw card is playable and has not been hinted at and where player 3 holds an un-hinted card that can be played after player plays their newest card (finesse-able situations). Then we manually override player I's and player 2's moves in finesse-able situations to carry out the finesse and check if player will play the designated card under the blueprint to make the finesse complete and worthwhile cannese-completr situations). We experiment with 4 different blueprints and show their statistics of finesse-complete situations over 1000 game seeds in Table La All the agents are trained following the settings in corresponding prior works. Although finesse-able situations are common in the games played by all four agents, the first three RL agents trained without human data rarely complete manually enforced finesse move, making them undesirable for the subse- quent experiment. It also worth noting that none of the RL blueprints perform finesses by themselves while the behavior clone agent performs only finesse out of the 1183 finesse-complete situations.
Finesse Execution Experiments We apply both IMPROVISED and IMPROVISED with the behavior clone blueprint on 1000 randomly chosen finesse- complet situations to check how many finesse it performs. The results are shown in Table [b] Due to the novelty of this problem setting, there has been no prior method to directly compare against. For reference, we run SPARTA [8) strong search algorithm for Dec-POMDP designed to find unilateral deviations that maximize the expected return, on the same situations with the same restrictions on the set of actions that the agents may deviate to. From the table, we see that both IMPROVISED algorithms perform significantly more finesses, indicating their effectiveness in finding SEDs on the fly. In the situations where
8

---

IMPROVISED does not perform finesses. it can either be that IMPROVISED finds no beneficial deviations finds better, non-finesse SEDs. is also interesting see that IMPROVISED" finds roughly the same amount of finesses as IMPROVISED
Full Game Experiments Then, we run IMPROVISED on the full game of Hanabi. At any time step. the active player will first check whether a deviation has been initiated by other players by checking whether previous players have picked actions with low probability under the blueprint. If a deviation has been initiated, they will play their corresponding role as either player 2 or player 3. Otherwise the active player will decide whether to deviate using the IMPROVISED method. Over fixed set of 100 game seeds, IMPROVISED and IMPROVISED* perform 29 and 21 finesses respectively, while SPARTA only performs 3. Although it is still much less frequent than what expert human players will do, IMPROVISED is nonetheless meaningful step along this novel and challenging direction.
Although our work focused on understanding and replicating this human capability rather than optimizing for self-play score, we also report quantitative results showing noticeable increase in score using IMPROVISED compared to the plain blueprint. If we run IMPROVISED only at the 1000 finesse-complete situations from Table lb and use blueprint for the rest of the timesteps, then IMPROVISED and IMPROVISED achieve average scores of 18.08 + 0.28 and 18.18 + 0.27 respectively while the blueprint gets 17.18 + 0.28 on those same games. When we run IMPROVISED on the full game, we improve the average score from 17.80 0.85 to 23.54 + 0.14.
Related Work
Public Belief Methods Our method builds prior work that models Dec-POMDPs PuB- MDPs [TO m 2
15 16. PuB-MDPs enable theoretically sound planning algorithms without having to reason about the agents' entire policies because the public belief state serves sufficient statistic for planning. For example, SPARTA [ conducts a one-step lookahead starting from the public belief state and chooses the action that maximizes expected value assuming all players play according to a Nommon-knowledh deviations from the BP rather than multilateral deviations, because searching over all of the latter would be intractable. As discussed in Section 3.1 discovering SEDs may require considering multi- lateral deviations from the BP. IMPROVISED is able discover these multi-lateral deviations by searching over a constrained set of multi- lateral deviations.
BP thereafter. However, SPARTA searches only for unilateral
Human-Like Coordination Outside of this work, another notable work in the direction of incorpo- rating human-like behavior into AI agents is that of Ma et al. (9. Ma et al. [ show that certain archi- tectures have better inductive biases for respecting the correspondence between action features and ob- servational features. Our work is complementary in the sense that we investigate phenomenon that occurs in unusual situations, whereas Ma al. 99] investigate a phenomenon that occurs by default.
Conclusions
Coordinating with others using minimal explicit agreement and extending conventions' "on the fly" is one of the most intriguing reasoning capabilities. In this paper we formalize the definition of such behavior as reefaaxplann deviations. We showed that existing methods tend not perform these types of deviations and presented an algorithm called IMRROVISED that can both discover them and respond correctly when they are being carried out by other agents at test time.
Limitations and Future Work We see two main limitations of IMPROVISED that would be worth addressing in future work. The first is the fact that IMPROVISED requires exact knowledge of all teammates' policies and assumes that other teammates are also running IMPROVISED. In real coordination settings, it is both unrealistic assume exact knowledge of the policies of externally specified teammates and unrealistic to assume that those teammates are implementing the same SED algorithm. The second the computational cost of IMPROVISED, to estimate many crucial quantities at test time (more details in the appendix). One concrete direction toward addressing this issue is to derive learning based version of IMPROVISED by learning the Q-function q(b, $1, 01, az).
requires Monte Carlo rollouts

---

References
[1] N. Bard, J. Foerster, S. Chandar, N. Burch, M. Lanctot, H. F. Song, E. Parisotto, V. Dumoulin, S. Moitra, E. Hughes, Dunning, S. Mourad, H. Larochelle, M. G. Bellemare, and M. Bowling. The hanabi challenge: A new frontier for ai research. Artificial Intelligence, 280, 2020. URL https://dda
1111111116..aaaa artint......... 103216
[2] S. Dibangoye, C. Amato, Buffet, and F. Charpillet. Optimally solving dec-pomdps as continuous-state mdps. Journal of Artificial Intelligence Research, 55:443-497, 2016.
[3] J. N. Foerster, H. F. Song, E. Hughes, N. Burch, I. Dunning, S. Whiteson, M. Botvinick, and M. Bowling. Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning. In Proceedings of the 36th International Conference on Machine Learning, pages 1942-1951.
PMLR, 2019.
[4] H. Hu and J. N. Foerster. Simplified action decoder for deep multi-agent reinforcement learning. In International Conference on Learning Representations, 2020. URL httf//orumddddixxmm3e
[5] H. Hu, A. Lerer, A. Peysakhovich, and J. Foerster. "Other-play" for zero-shot coordination. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 4399 4410. PMLR, 13-18 Jul 2020.
[6] H. Hu, A. Lerer, B. Cui, L. Pineda, D. Wu, N. Brown, and N. Foerster. Off-belief learning. (To Appear) ICML, 2021. URL httpp::/s///ar http://////aii.oo//aa/////////
.40000
[7] V. Kovarík, M. Schmid, N. Burch, M. Bowling, and V. Lisý. Rethinking formal models of partially observable multiagent decision making. CoRR, abs/1906.11110 2019. URL
http://arxis: org wwwp://w.wrrg////////e//// w9tpaa///....///// 11110
[8] A. Lerer, H. Hu. J. N. Foerster, and N. Brown. Improving policies via search in cooperative partially observable games. In AAAI, 2020.
[9] M. Ma, J. Liu, S. Sokota, M. Kleiman-Weiner, and J. N. Foerster Learning to coordinate with humans using action features. CoRR, abs/2201.12658, 2022. hoLlhttss://rxiiit org/arst /bs/ 2201 12658
[10] A. Nayyar, A. Mahajan, and D. Teneketzis. The Common-Infommnn Approntt Decentral- ized Stochastic Control. Springer Verlag, 2014. doi: 10. 10.100779978-33319-2211500
[11] F. A. Oliehock. Sufficient plan-time statisties for decentralized pomdps. In Twenty-Third International Joint Conference on Artificial Intelligence. Citeseer, 2013.
[12] T. Rashid, M. Samvelyan, C. Schroeder, G. Farquhar, J. Foerster, and S. Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. Interna- lional Conference on Machine Learning, pages 4295-4304. PMLR, 2018.
[13] M. Samvelyan, T. Rashid, S. de Witt, G. Farquhar, N. Nardelli, T. G. J. Rudner, C.-M. Hung, P. H. S. Torr, J. Foerster, and S. Whiteson. The StarCraft Multi-Agent Challenge. CoRR, abs/1902.04043. 2019.
[14] S. icy
Games with Approximate Pol- https://eraa.lbraa 17dd00aa-ec13 4cd4 8e30 a7765d8c5ccc
Sokota. Iteration, 2020.
Solving Common-Payoff
URL
waa.berta.ca/itens.
[15] S. Sokota, E. Lockhart, F. Timbers. E. Davoodi, R. D'Orazio, N. Burch, M. Schmid, M. Bowling, and M. Lanctot. Solving common-per payoff games with approximate policy iteration. In Thirty- Fifth AAAI Conference on Artificial Intelligence, AAAl 2021, Thirry-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, FAAI 2021, Virtual Evení, February 2-9, 2021, pages 9695-9703 AAAI Press, 2021. URL. sattps://oyy aaai, orgg iid/xxndxxx///// wrg/index...
10

---

[16] S. Sokota, H. Hu, J. Wu, J. Z. Kolter, J. N. Foerster, and N. Brown. A line-tuning approach belief state modeling. International Conference on Learning Representations, 2022. URL
nttps://openrevier. http:://oppneeveeee.eeeforoorr het//forum2dd-c227DD0..
[17] P. Sunehag, G. Lever, A. Gruslys, W. M. Czarnecki, V. Zambaldi, M. Jaderberg. M. Lanctot, N. Sonnerat, Z. Leibo, K. Tuyls, and T. Graepel. delue-Decomposition Networks For Cooperative Multi-Agent Learning Based On Team Reward. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 18, pages 2085-2087, Richland, SC, July 2018. International Foundation for Autonomous Agents and Multiagent Systems.
[18] C. Yu, A. Velu, E. Vinitsky, Y. Wang, A. Bayen, and Y. Wu, The surprising effectiveness of mappo in cooperative, multi-agent games, 2021.


Reviews:
[{"review_id": "uNPxBljH_g", "reviewer": "Reviewer_4pB2", "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. ", "questions": "Some questions are listed above, and here are other questions. \n\n1. Is it possible to extend the idea of SEDs to more than 2 players in Definition 1?\n2. Is it a common assumption that 'Bob can detect the deviation as $\\mathcal{D}(b)$' in Line 211?\n3. What do the dash lines between Bob in Figure 2 mean?\n4. 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. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. **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. \n2. **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.\n3. **The novelty of the proposed method**. The proposed method is simple but novel.  \n4. **Clarity**. This paper is generally well-written and easy to follow. \n\n\n\nWeaknesses\n\n1. **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?\n2. **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? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_XtrjEP34aM", "reviewer": "Reviewer_tWnN", "summary": "## Summary: \n\nIn 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.\n\nThis 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\". \n\nTwo assumptions are made though:\n1. Sequential and publicly observable actions.\n2. Only considers SEDs where the first player's private information is not necessary for coordination.\n\nIn 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.\n\nThe 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. \nAn approximated search algorithm is  thus devised to solve the optimization problem in a tractable fashion, at every player's turn, it is entitled IMPROVISED.\n\nTwo 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.\n\nNote 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.\n\nFinally, the paper investigates the proposed algorithms ability to perform a subset of *finesse* plays in Hanabi.\nNote that not all SEDs are *finesse* plays. \nComparisons are made against:\n1. a Behaviour Cloning policy trained on human moves, and \n2. SPARTA, another search algorithm applied to Dec-POMDP. \nThe BP policy used for that evaluation is the Behaviour Cloning policy.\n\nThe evaluation is performed in terms of number of specific *finesse* plays performed over a set of specific *finesse*-able situations. \n\nResults show that the proposed methods largely outperform both methods in terms the number of *finesse* plays actually performed in *finesse*-able situations.\n\nAlso, using this proposed *finesse* benchmark, the paper investigates state-of-the-art MARL agents' ability to perform those specific *finesse* plays. \nWhile 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%.\n\n## Post-Rebuttal and Initial AC-Reviewer Discussion Update:\n\nFollowing 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:\n\n1. 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. \nIndeed, 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.\n\n2. 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.\n\n3. 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).\n\nThus, 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).\n\nI am therefore updating the marks in my review: \n\n* raising the mark from 6 to 8, \n\n* raising the contribution mark from 3 to 4,  \n\n* raising the presentation mark from from 2 to 3.\n\n* raising the soundness mark from 2 to 4.\n", "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.\nNevertheless, 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?\n", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Originality :\nTo 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.\n\n# Quality:\nThe quality of the paper is fair.\nThe math seem marginally sound on the surface, but I will highlight a clarity/soundness issues below.\n\nReproducibility 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$).\n\nI find a strong issue with the strength of the numerical evidence:\n\n--> 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 ?\nThis would strongly strengthen my appreciation of the work and contribution here, and I would update my mark accordingly.\n\nSimilarly, 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...  \n\n[1] : SciPy's two-sample Kolmogorove-Smirnov test : https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.ks_2samp.html\n\n# Clarity & Soundness: \nI 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: \n\n--> line 60: need to specify $N \\in \\mathbb{N}$ as the number of players/agents\n\n## --> line 153 : Soundness & Clarity : Timestep in FOSG VS in single-agent public POMDP :\n\nGiven the public POMDP transformation, aren't the players playing simultaneously for the joint decision rule to be defined? \n\nI fail to understand what information are the joint decision rule actually considering. \nIndeed, 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?\n\nOr, alternatively, could you clarify when are the information state sets being updated?\n\nI 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 ? \ni.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?\n\n(Q2) If you understand the soundness and clarity issue that I raise here, then may I propose the following:\n1. 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).\n2. 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})$\n\n## --> line 177 : Clarity : Function $f$ :\n(Q3) Could you clarify how is $f$ computed? Is it shared between players? \n\nI 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? \nIf so, I would flag it as a critical limitation that needs to be discussed and better detailed, please.\nI would welcome a very detailed table maybe showing the mapping that this function performs, if it is relevant?\n\n\n## --> Equation (1) : Clarity & Soundness : Operator $\\circ$\nI think that leaving the $\\circ$ operator undefined is hurting the clarity and soundness of the claim.\n\nIndeed, 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$.\nI 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...\n\n## --> line 234-237 : Clarity : Optimality Argument lacking substance\nI 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? \n(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? \n\n\n## --> line 244-245 : Clarity : Jensen Inequality & Alice's conditional behaviour\nI 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?\n\n--> line 245: clarity : shouldn't it be an argmax instead of max?\n\n## --> Figure 3: Result Transparency :\nI 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.\n\n## --> Table 1.b : Clarity and Soundness : Major Issue/Misunderstanding \nI 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. \n\n(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?\nCould 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.\n\nIn 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. \nMaybe 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.\n\nAlso, 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?\nIndeed, 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?\n\nI 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?\n\n\n# Significance :\nMost of the results provided may be more compelling if the sample size was similar to previous papers.\nThat 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.\nPlease consider addressing the following points:\n\n## --> Line 353 : Missing Results for Human-Cooperation Significance :\nWhat about IMPROVISED$^P$, since it is more valuable for cooperation with humans?\n\nCould you report the number and percentages of finesse-able / finesse-complete situations encountered during these 100 games, please? like in Table 1.a\n\nI 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.\n\n## --> Line 356 : Selfplay vs Crossplay & Zero-Shot Coordination :\nAs 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 ?).\n\nThus, 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? \nUnless 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?\n\nI understand that this is going the extra step, and I would not mind if the authors were not able to address it...\n\n## --> Line 361 : Significance : Statistical Significance Tests :\nsee section Quality above...", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JgROBAWQmXW", "reviewer": "Reviewer_y99U", "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.\n", "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?)\n", "limitations": "Authors address this directly, no issues.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality\nI’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.\n\nClarity\nIn 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.\n\nQuality\nI 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).\n\nSignificance\nThis 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-zpx5VYIz_C", "reviewer": "Reviewer_t5d6", "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. ", "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?\n\n2) 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?\n\n3) Have you conducted any statistical significance testing of your results (for sake of completeness of the analysis)?\n\n4) 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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nGiven 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.\n\nMinor notes:\n\n-- line 157: \"where the Bob's\" => \"where Bob's\"\n-- line 366: \"Dec-POMDs\" => \"Dec-POMDPs\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept