Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper addresses the problem of learning an opponent model in a multi-agent environment. What makes learning hard is that the opponent can be learning at the same time. The paper proposes an algorithm, called MBOM, that operates by simulating the reasoning process of the agent in the environment and considering different types of opponents. The process is recursive and uses the environment model to predict the policy improvement of the opponents. The process generates improved models of the opponent, that are then used with Bayesian mixing to produce an estimate of the opponents policy. The MBOM algorithm is tested on two games, the Triangle Game and the One-on-one two player game. Different algorithms are used and their performance is compared with MBOM.
main_review: The method proposed is elegant and seems promising, but I have a number of questions that require clarifications:
1. the method is designed to work with multiple opponents that are treated as a joint opponent.  In both and the Triangle Game and the One-on-One game e there are only two agents.  This raises the issue of what happens in situation when there is more than one opponent.  It would have been useful to have at least one application with multiple agents to understand how well the proposed algorithm addresses the multi-agent opponent modeling as claimed.
.2. The two games used for the experimental work seem to have sequential and not simultaneous moves, and the same applies to the cooperative game. It would have been useful to address the issue in the description.  Again, does the algorithm expect a sequential move game?
3. Not much is said on the opponent types that are assumed, specifically the difference between the naive learner and the reasoning learner.  This is important because the readers need to know how to decide if an opponent is "learnable".   Also, it is not clear if the agent knows the type of opponent (fixed policy, etc) or not.  
4. The computational costs are mentioned as being high, but there is no indication, for instance, of the computing time taken by the examples presented in the paper. The problem of reducing the computational complexity is listed as future work.
5. There are graphs that show performance results for the games, but it is not clear how performance is measured.  Some explanations would help. The performance tables (Table 2 and Table 3) show numerical performance values but do not say what the values represent.
6. The placement of tables and figures is not ideal. They are referenced very far form where they show up in the paper, making the reading harder.
7. The paper does not include any theoretical results, and, given the comments made above, it is hard to understand when the method will work and how well it will work.  
summary_of_the_review: The paper presents a promising method for an agent to learn opponent models in a multi-agent environment. The method is compared empirically with similar algorithms which are outperformed.  Unfortunately, the paper does not provide theoretical guarantees, lacks details in some of the explanations, as listed above, and shows only examples with two agents, an agent and an opponent.  In conclusion, the method seem promising and well thought out,  but it is hard to be understand what are the requirements to make the method applicable in practice.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a model-based opponent recursive reasoning method for MARL problem. The recursive reasoning takes multiple levels of estimation to generate a number of opponents. The first level opponent is obtained by supervised learning from the true opponent actions. Then, with a learned dynamics model, the level-0 opponent interacts with self agent and the dynamics model to generate trajectories, from which by selecting one best response rollout, a better action at the current time step for the opponent is kept and used to estimate the next level opponent, by maximum log-likelihood again. After obtaining a number of levels of opponents, a mixture opponent is learned by softer-softmax weights. Experiments are conducted on multi-agent particle environment and google's football environment, and LOLA-DiCE and Meta-PG are compared.
main_review: Major comments:

1. When estimating the next level opponent, at time step t, the opponent's action is selected from the best action using the rollout with highest value, estimated by expanding k steps with the dynamics model. Below Algorithm 1, "With larger k, the rollout has longer planning horizon, and thus could evaluate the action a^{o*} more accurately" is problematic by noting that the rollout is generated by interacting with a learned dynamics model, which suffers uncertain dynamics error. Moreover, for zero-sum or cooperative setting, the opponent's value is estimated by directly using the negative self agent's value or the self agent's value. This is also questionable since for multi-agent settings, the problem is not an MDP again from the perspective of one agent. So, the value estimated from the self agent's observation conditions on only partial states without knowing the opponent's information. Based on this, the value is not exchangeable. Overall, I think the recursive reasoning part might rise many uncertainty issues and suffer approximation errors at least from the above two ways, and these uncertainty and error can be accumulated for higher level opponent reasoning. Unless the dynamics model error and value estimation error can be analyzed theoretically to guarantee the higher level opponent's value is also higher from the opponent's view, I am wondering whether the proposed recursive reasoning method can consistently generate stronger opponents or not. 

2. What is the case when the problem is not zero-sum? Also, when there are more than one opponents, would the recursive reasoning becomes more complicated, because when use a model to generate rollouts, the best response rollout should be selected by considering other opponents' actions?

3. In the experiments, two-player games are considered. I think the original LOLA and a plain RL baseline without any reasoning should also be compared as references. Moreover, as the number of levels of IOPs and the length of rollouts k are important factors in the proposed method, these hyper-parameters should be studied with sufficient empirical results, which are absent from the current contexts. Most importantly, I think experimental results that can visualize the difference and improvements along the opponent models from lower level to higher level should be crucial to support the effectiveness of the proposed recursive reasoning. However, these results are not considered in the current experiment section.

Overall, this paper proposes an interesting recursive way for modeling the opponent's policy, while there exists many issues to be solved in revisions.
  


summary_of_the_review: An interesting model-based opponent modeling method in MARL while approximation errors in recursive reasoning and more explanatory experimental results should be considered.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes MBOM, a scheme for multi-agent reinforcement learning, which flexibly adapts to opponents with different or unknown learning abilities by relying on recursive reasoning.  The paper evaluates the algorithm on two competitive environment, empirically comparing to other baseline and state-of-the-art schemes.
main_review: The paper address a significant problem of multi-agent reinforcement learning in the setting when agents are 1) heterogeneous 2) learn/reason about each other and adapt their policies based on observations of other agents' behavior. In the general discussion, the paper covers relevant related work, and discusses challenges and limitations. Empirical evaluations conclude both quantitative evaluation of performance and insights on the possible mechanisms and causes of observed performance patterns, and justifications of the proposed algorithm. This research can potentially become a significant and influential contribution to reinforcement learning community.

That said, I have several reservations about the paper and would like to see if they can be addressed in a revision. 

1) The empirical evaluation is not well aligned with related work. It compares MOBM with other baselines on three domains, one of them is collaborative and two are competitive. It seems that none of these domains appears in the same form in the cited work to which the new algorithm compared. Since this paper claims that SOTA, I would anticipate that the comparison is performed on domains on which the baselines claim SOTA, in addition to the new domains introduced or adapted in the paper.

2) The main idea of the paper is in representation learning for recursive epistemic reasoning. However, convergence of such reasoning, and soundness of Bayesian mixing of such methods is not theoretically analyzed. This is not obvious at all that recursive epistemic reasoning (theory of mind) works in competitive domains, and what are the restrictions/conditions under which it is sound. 
  a) First, recursive epistemic reasoning is applied to competitive tasks. It is easy to show that it does not always converge. Consider Bob and Alice and two bars settings. Bob and Alice slightly prefer bar A, but both what to avoid each other. This is a competitive setting. Let us reason with Alice. On level 0, Alice chooses bar A. On level 1, Alice realizes that Bob chooses bar A too, so she chooses bar B. On level 2, Alice thinks about Bob choosing bar B on level 1 so she chooses bar A. On level 3, she would switch to bar A again, and so on. No convergence. By making Bob's and Alice's policies probabilitistic the analysis can be made more interesting, but still not converging under certain conditions to any equilibrium. This is not an edge case but a general property of recursive reasoning, which does not seem to be addressed in the paper.
 b) Second, recursive reasoning is built upon the best imagined action of the opponent. This is a problematic setting, related to Newcomb's paradox. Consider, again Bob and Alice, in a setting in which Alice has equal preferences regarding the bars and attributes reward 1 to avoiding Bob and 0 to meeting him. Bob chooses the first bar in 55% of cases; Alice employs a single level of epistemic
reasoning. It is easy to see that the optimal policy for Alice is to always go to the second bar for the expected reward or 0.55.
However, the policy inferred using conditioning on the best anticipated move of the opponent is  is for Alice to choose the second bar with
probability of 0.55, for the expected reward of 1! This is because Alice's decision is (erroneously) conditioned on Bob's
anticipated choice of a bar, and hence Alice pretends that she can always choose the other bar (which she cannot). This issue also seems to be omitted in the paper. The agent behavior may seen reasonable in the complicated settings of the proposed domains, but in general I suspect that the algorithm is not sound.

Based on the above, I would appreciate a formal theoretical treatment and an empirical evaluation to be improved in a revised version of the paper.


summary_of_the_review: An interesting line of research but theoretical analysis and empirical evaluation should be improved in a revised version.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Agents learning in systems with other-agents that may be simultaneously learning presents the original agent with a dynamic learning problem. Critically, the agent does not know if the other-agents are non-learning, learning, or learning using recursive-reasoning. One such solution to this problem is to design a learning algorithm that accounts for how the other-agents may update their policy from the shared experiences, effectively eliminating the aforementioned problem. This work attempts to design such an algorithm without relying on any assumptions on the other-agent's learning algorithm. Their proposed algorithm, Model-Based Opponent Modeling (MBOM), learns parallel opponent models that are trained using various depths of recursive reasoning. Then, when played against an opponent, the agent can select the most likely opponent model (level-0: non-learning opponent, level-1: learning-opponent, level-k: k-1 level recursivly learning opponent). This algorithm assumes a centralized training and decentralized execution setting for two-player fully-observable general-sum games. 
main_review: **Review**
This paper offers an interesting idea of effectively simultaenously modelling the same opponent under differing assumptions of their learning's complexity. It then used model-based predictive control with whichever opponent model is most similar to the opponents recent behavior (measured by comparing realization plans). This is a good, straight-forward, solution to the uncovered problem. Despite this, I am concerned both by the lacking of methodological details required to evaluate their empirical results, and the amount unsupported claims scattered throughout the paper. 

**Major Comments**
- The set of baseline methods used are incredibly sophisticated making cross-comparisons very challenging. Simpler baselines should be included to help understand the benefit of the additional sophistication. Some easy examples are: variations on direct BR. Train a BR directly against a single opponent, mixture of the opponents, etc.. Moreover, a BR can be trained against the evaluation opponents to set an approximate upper bound on the performance these methods. Naive learner and regular LOLA can also be a baseline method, similar with other recrusive reasoning approahes discussed.
- The proposed major contribution of this work is a learning-aware learning algorithm that is independent of the other-agent's learnin algorithm. This includes many claims about various levels of required recursive reasoning being necessary to achieve desired results. I would have liked to see quantitive and qualitative experiments that analyze the inter-relation of the levels of recursive reasoning of the agent wrt the levels of recursive reasoning performed by the other-agent. This would help the reader understand how necessary and under what settings MBOM is useful. Moreover, analysis into the distribution over the IOPs can provide further insights.
- The authors liter throughout the paper unsupported claims that are often easily disproven. These distract the reader and undermine the credibility of the authors and the results herewithin. I've pointed out some of these within the Minor comments. Please ensure that claims are supported by either theoretical/empirical evidence or approriate citations.
- I am having trouble following the construction and evaluation methodology wrt to the opponent policies. It would be helpful if included, perhaps in the appendix, was more details regarding the construction of the set of opponent policies. Especially focusing on evidence that supports that these policies are both diverse and represent a good coverage of the strategic space of the game. Additionally, how each evaluated algorithm was tuned and the opponent's algorithms. Without these details it's hard to appreciate the results provided and support claims such as "out of distribution opponents" -- your evaluation opponents may in-fact be within the same distribution and there is another issue.
- If the coin game is a "high-dimension expansion" of IPD, it's confusing to me why there is an absolute failure to learn in LOLA-DiCE in Sec 5.3. IPD is the evaluation domain that is used in their work. Are you using their original implementation, or how have you evaluated that this method is working correctly? Has equal/sufficient tuning been applied to this method?
- The "Bayesian mixing" methods proposed share many similarities with previous work on purification of mixed-strategy opponents and realization plans. Appropriate citations and dicussions of these relationships is necessary to contextualize the contributions here.

**Minor Comments (not directly impacting score)**
- Abstract (and throughout), "opponents who are learning simultaneously or cpaable of reasoning" please be careful about mentioning reasoning vs recursive reasoning, and define these terms early. I.e., reasoning doesn't say anything, should only use recursive reasoning.
- Sec 1, Par 1, "interacting with diverse opponents make the enviroment nonstationary" this is not correct, stationarity of the environment is independent of the opponent. Upon abstracting the environment and other-agents into a black-box meta-environment, this meta-environment is only nonstationary if one of the components, environment or other-agent, is non-stationary (in the case of the other-agent being stochastic as mentioned here is insufficient).
- Sec 1, Par 3, "Inspired from the ... mechanics of the environment." I don't find this intuitive, humans  do not understand the reuls and mechanics of our environment. Suggestion, weaken staement, provide citations to recursive reasoning literature; esp. levels of recursive reasoning humans typically do
- Sec 1, Par 3, "Inspired from the intuition that human could anticipate ..." Awkward
- Sec 1, Par 3, "The higher-level oppoennt model reasons more deeply and thus more competitive" Awkward, and not strictly true, please justify such a claim.
- Sec 1, Par 3, "a certain-level opponnt model", undefined terminology
- Sec 2.1, Par 1, "it is a big challeng to form robust policy" Awkward
- Sec 2.1, Par 2, "One simple idea ... is encountered", worth mentioning that this requires either the agent being notified of the opponent changing or defining a function that signals opponent change -- big assumptions, the later being error prone.
- Sec 2.1, Par 2, "A better appraoch is to represent an opponent's policy with an embedding vector",  why is this a better approach? Please justify. It seems full models would be more accurate, but embeddings offer a more computationally tractable solution.
- Sec 2.1, Par 3, "Since PR2 uses the agent's.... only be applied in cooperative environments." This isn't true. Similar to this work, if assumptions are made about the game, such as zero-sum, we can infer opponent Q-values. 
- Sec 2.1, Par 3, "However, these methods use ... cannot handle diverse opponents in execution." This is not generally true. The effectivness of a method's generalization to held-out opponent policies depends on how well the fixed set of agents covers the strategic landscape of the game. A point that the proposed algorithm is also vulnerable too. 
- Sec 2.1, Par 4, "These meta-learning based methods require .... same learning algorithm" why does the trajectory distribution imply similarity in learning algorithm?
- Sec 2.2, Par 1, "Model-based RL allows the agent to have access to the transition function" Careful with phrasing, this isn't true. They depend on a transition function that may be learned or exact.
- Sec 4.1, Par 1, "To adapt to the learning and reasoning opponent... more deeply than the opponent" why must this be true?
- Sec 4.1, Par 2, "obtain the level-0 IOP", Awkward
- Sec 4.2, Par 1, "recursive imagination" lots of interchanging of terminiolgy between simulation/imagination/reasoning, suggest adopting and defining one nomenclature and staying consistent. 
- Sec 4.2, Par 1, "a softy" ?
- Sec 4.2, Par 1, How are you calculating p(i)?
- Sec 4.2, Par 1, distinquishing where the prior work softer-softmax ends and modificaitons to work in this application begins can help the reader better understand contributions. 
- Sec 5.2, Par 1, "The learning of LOLA-DiCE ... opponent quickly and effectively." This presumes you're training LOLA-DiCe against a set of opponent policies, which is not the same problem defn the solution was designed for; however, with batches of experiences carefully constructed across the opponent policies the gradient information could be effective. Especially when the gradients agree.
- Sec 5.2, Par 1, please avoid describing results as significant without corresponding statistical tests
- Sec A, Triangle mispelled in table.


summary_of_the_review: I recommend rejecting the paper in its current state. While the authors identify a problem and provide a nice and simple solution to the problem, these are undermined by experiments that are underspecified and a lack of analytical experiments into the interworkings of the algorithm.
review_title: null

Meta-review: This paper tackles the challenging problem of learning against an opponent that may or may not be simultaneously learning as well. The key contribution of this paper is a learning algorithm that accounts for how the opponents may update their policies from past interactions. The proposed algorithm, MBOM, relies on the environment model to model a hierarchy of opponents using different depths of recursive reasoning (from non-learning agents to deep recursive agents). It is agreed that this papers studies an important problem and shows promise. However, the current results aren't convincing enough. In particular, since there is no theoretical analysis, more empirical validation of the method is expected. The current experiments only considers a single opponent, and it is unclear how well the method works given accumulated errors through the recursion. Future submissions would benefit from additional empirical analysis (e.g., ablations) to help understand when and why MBOM works.
Decision: Reject