Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents an algorithm for playing 2-player zero-sum repeated games that attempts to effectively balance the ability to model and exploit other agents while not opening one’s self to exploitation.  Limited results in Khun Poker when paired with three different algorithms are presented, with comparison to a handful of other methods.

main_review: Initial reflection for context: The paper addresses an old problem that has, from my perspective, been re-hashed repeatedly over the last several decades.  Despite being foundational and somewhat simple, the answers remain extremely difficult and hard to come by (I argue that the problem itself is ill-posed).  It is within this view that I base my review.

Strengths:

+ The paper is, for the most part, well-written and polished.  The technical description of the algorithm is detailed and seems solid (albeit I found the algorithm description difficult to follow).

+ I really like the two measures the paper analyzes: ability to exploit and exposure to exploitation.  This trade-off is central to the problem at hand.  (I expound on this a bit in the weaknesses portion of the paper).

+ For the empirical results that are presented, the algorithm appears to perform well.  The results are limited, and in some sense can be viewed as simply anecdotal.  However, I also do not want to diminish the strength of this contribution, as getting an algorithm to do this even in this limited context is no small accomplishment.

Weaknesses:

- I read the results differently than how they are discussed in the text of the paper (which seems to be bent on advocating, perhaps understandably so, for the algorithm presented in the paper).  To me, the key insight of the paper is the trade-off between exploitability and exploitation.  I’m not sure what the ideal trade-off between these measures is, but we could (for example) weight them equally.   If we do that, Figure 2 clearly shows that exploitability has higher magnitude across the algorithms than does exploitation.  If we simply subtract exploitability from exploitation, it appears to me that only PSRO has a positive value, suggesting it may be the best algorithm in this case among the 5 presented (though, again, the trade-off assessment of equal value between the metrics is subjective).  In the second set of results shown in Table 1, a similar trend continues, except that CEPSOM also has positive weight.  But the results don’t seem to be telling me that CEPSOM necessarily obtains a better trade-off than PSRO (which is essentially minimax in this game, as I understand it).

- In all honesty, it is hard to make any general assessment about EPSOM and CEPSOM from these limited results.  Is there some opponent that could really exploit CEPSOM.  If so, when and how?  If not, when and how?  The authors state at the outset of the paper that they are not interested in self play.  But self play is a foundational comparison in this domain, as any good algorithm would be adopted by other agents over time necessitating a successful algorithm to be good (in some sense) in self play.  But modeling copies of one’s self is often problematic.

- I do not understand Figure 3.

Again, this topic has been addressed for decades now, and I don’t know that we are any closer now to solving the problem than we were decades ago.  Perhaps that is because the problem itself is, in a loose sense, ill-posed — claiming algorithms are better than each other in this domain with trade-offs are largely subjective.  That is why I like the set of metrics (exploitation and exploitability) present in this paper — it looks at the (messy) trade-off of the problem.  I wish the authors had taken that trade-off further in their analysis.  If they are will to do that, I can envision the paper as a worthy contribution.

limitations_and_societal_impact: The paper doesn't explicitly address these aspects.  The limitations of the evaluation need to be further stated.  I don't think there is anything really to say about societal impact.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: The paper proposes to use the Dirichlet process for opponent modelling in games. It argues that the approach is particularly suitable for non-stationary opponents. It then proposes an algorithm to compute a counter-strategy to the model based on the restricted Nash response. Empirical evaluation on Kuhn poker shows that this approach can exploit a non-stationary learning opponent similarly to one of pre-existing methods, while maintaining relatively slow exploitability.
main_review: Originality: The problem of opponent modeling in games has been extensively studied before. The idea to use the Dirichlet process (DP) to solve it may be new and is well motivated in the paper.

Clarity: The paper is reasonably clear and understandable. However, it would be further improved by use of examples to demonstrate the notions and algorithms on a specific tiny game.

Quality: The notation and basic claims in the paper seem sound. My main concern is with the positioning with respect to the related work and the quality of the empirical evaluation.

(1) Related work. Opponent modelling in games is a classical problem with many solutions. This paper reviews a part of this literature, but it does not provide theoretical or empirical arguments on superiority of the proposed approach to the existing ones. A natural candidate for the context of the paper would be, for example, the implicit agent modelling framework [A], but at least a compelling argument of superiority to [10,15,49] either theoretically or empirically should be provided.

(2) Computational complexity. There is no discussion of the computational complexity of the proposed method. It looks much more expensive than some of the alternatives mentioned above and the evaluation is only on a tiny game. How well scalable would the approach be to larger games?

(3) Experimental evaluation. The experiments are performed on one small game against one opponent on 5 runs of the system, without any statistical analysis of the confidence intervals. It is not sufficient to make any conclusions.

Significance: The proposed approach might be a good idea. However, without a clear comparison to competing methods, I do not think someone would choose to implement and use it on some practical problem. From the theoretical perspective, I understand the paper as an application of an existing method of DP to the problem of opponent modelling. Hence, there is no theoretical advancement. If it is not so, I assume the authors will argue for the theoretical novelty in the rebuttal. 



References:

[A] Bard, N., Johanson, M., Burch, N., & Bowling, M. (2013, May). Online implicit agent modelling. In Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems (pp. 255-262).

limitations_and_societal_impact: There is not much discussion on limitations or societal impact. Thorough discussion of computational costs would certainly be an improvement. I do not believe the paper has substantial societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper presents a new approach for learning to play against an opposing agent in a two-player zero-sum game that can transition among an arbitrary set of strategies. Experiments in two-player Kuhn poker demonstrate that the approach obtains high degrees of exploitation and low values of exploitability compared to several benchmark approaches.


main_review: There appears to be a major problem with the paper. The main algorithm uses an RNR solver based on an LP formulation that is provided in the appendix, but this formulation is incorrect.

In particular, the first LP on page 579 on page 14 is incorrect, since the vector y_a is defined incorrectly on line 578. It should be y_a(j) = p pi_fix(a)  for j != a, not y_a(j) = 0 for j != a (the j=a case is correct).

There also should not be a need for the second LP, since player 1’s strategy should correspond to the dual variables from the first LP.

The second LP does appear correct, though the second set of constraints (pi^2(a) <= p pi_fix(a) + 1 – p) is redundant and implied by the final two constraints. 

Since the algorithms are based on an incorrect formulation, I assume all the experiments are incorrect, so I can’t really assess them further.

I think that overall the problem is important and the approach is promising.

Some other minor comments:
37: dominated actions are not the only forms of irrationality in games. In fact, dominated actions are very rare in realistic poker games. See “Mistakes in Games” Ganzfried DAI 2019.

38: a NE -> an NE 

naive -> naïve 

90: Seems weird to cite a recent 2020 paper for the result that two-player zero-sum games can be solved in polynomial time by an LP.

109: States that the approaches can be extended to multiplayer games, but RNR is defined only for two-player zero-sum games, so it should be elaborated on how the approach is applicable to multiplayer games.

Section 3.1 seems to just present the standard definition of a normal-form game. I’m not sure why it is called a “meta normal-form game.” What is the “meta” part referring to that differentiates from a standard NFG?

Footnote i refers to stochastic games, while the model in the paper is just for normal-form games. Why is there a reference to stochastic games here?

The game model described is for normal-form games, but experiments are on Kuhn poker, which is an extensive-form imperfect-information game. 

152: life-time -> lifetime

156: why use a maximum-a-posteriori approach instead of alternatives?

163: rolls-out -> rolls out

It would be helpful if some more information about the PPO algorithm is included, since it is the opposing agent as well as one of the benchmark algorithms.

I think it might be helpful to include a static Nash equilibrium strategy as an additional benchmark strategy (there are multiple equilibria in this game, so perhaps some of the extreme point NE can be used).

Does “stds” mean “standard deviations”?

In Table 1 the standard deviations seem very large compared to the payoff values, which indicate that additional experiments should be run.

Additional comments after the responses and discussion:

Based on the response it is likely that the authors probably used the correct LP formulation in the experiments and just wrote it wrong in the paper.

The authors claim that they have done additional experiments that achieve the same result. I'm not sure if we can just take their word. I think it is necessary to obtain statistical significance, and the current results do not come near this. In the response to 8Pgk they state that they also have comparisons against other benchmark agents SAM and MCCFR that show superiority of the new approach. But again I'm not sure if we can take into account results not in the paper. I would lean towards marginal acceptance if results showing statistical significance as well as comparisons against SAM and MCCFR were included.

I would still be interested in seeing a comparison against static NE strategies (there are multiple NE). I think this is a very important benchmark to include.

Author response:
"Mistakes in Games (Ganzfried 2019): Thank you for pointing out this interesting work. We will reword “dominated actions” to “dominated strategies” and discuss the difference between the two terms with reference to the work."

That paper actually shows that both dominated actions and strategies are very rare in realistic poker games, and proposes a new concept of a "mistake" that is more prevalent.




limitations_and_societal_impact: I don't see any potential negative societal impact of the work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work proposes an approach to learning against non-stationary opponents, where the non-stationarity comes from the learning dynamics in contrast to previous work which assumes a set of possible strategies over the opponents.

The opponent model is learned with Dirichlet Process and from it it's used together with a previous work (RNR) and meta learning  to produce a safe strategy.

The approach seems novel and improving previous works. I have some questions about experiments and limitations.

main_review: Originality
-I think a relevant work that is missed is "Safe Opponent Exploitation"
-I also would like to understand more about your contribution and previous work related to: 
"Recently proposed streaming inference algorithms [23, 41] enable the DP mixture model to solve online non-stationary problems in a truly non-parametric way.  In this paper, we adopt this approach to model and simulate a non-stationary opponent for MARL."

Quality
- I would have liked to see ablation results for the "correction" mechanism, how robust are the result with respect to the hyperparameter $eta$
- The paper mentions many times that the approach learns online, however in the conclusions
"It can be a heavy burden on an agent if it learns an opponent model from scratch online. Therefore, a more realistic way for utilizing the power of an opponent model is offline training and online prediction"
 I'm a bit confused which parts are online, which parts offline.


Clarity
- "Our approach, EPSOM, is not limited to the self-play setting."
 I think EPSOM should *not* be used in self-play?
- Figure 1 needs a better a more descriptive caption
- I really like the exploitability and exploitation measures, I think you can add another result where those are the axes and you plot the results of different algorithms.
- Figure 3 is a bit hard to interpret
- Line 275: "the training agent becomes risk-adverse"  why?

Significance
- Would this approach work for general sum games?
- Would be interesting to see more experiments with more opponents and see how it scales
- Both PPO and TRPO are algorithms that limit the change in the policy from one step to another, I would be interested to see EPSOM with more "drastic" changes.
- "EPSOM is limited by its computation and memory complexity. Naively applying EPSOM to more
 complex problems requires a great amount of resources." I appreciate the comment, however, I think more details would improve the paper.

Minor:
Line 290: "use an agent learning"
limitations_and_societal_impact: No discussion on this topic
review_title: null

Meta-review: There was a detailed discussion about this paper, and the relationship to Bard et al. was controversial, with some reviewers considering this a necessary benchmark and others agreeing with the authors that it isn't (necessarily).  Since it's controversial, I'm inclined to not make the decision based on the Bard et al. concern (though I encourage the authors to make sure to have really thought this through before a next submission).  Even so, the overall level of excitement among the reviewers is a bit low for acceptance, lacking any real advocate for the paper.  The additional experiments provided by the authors are appreciated and will be good to include in detail in a future version.  

I'll mark the paper as "reject but could be bumped up to accept" though I understand this means it's very likely to be rejected.
Decision: Reject