Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper studies reinforcement learning algorithms in a specific subset of multi-agent environments that are 'dominance solvable'. This means that, given an initial set of strategies in the game, if we iteratively remove 'dominated strategies' (those whose utility is strictly less than another strategy independent of the strategies used by other agents), then only one strategy remains for each player. The remaining strategy is called the iterated dominance solution. The paper proves the convergence of certain RL algorithms (REINFORCE in the 2-action case, and importance weighted monte-carlo policy iteration in the multi-action case) for normal-form games. The paper demonstrates the utility of this via mechanism design: in a principal-agent problem where one can design the rewarding scheme given by a 'principal agent' to various (RL) sub-agents, rewarding schemes motivated by iterated dominance guarantees the best solution for the principal agent, whereas schemes motivated by Nash equilibria do not. 

The paper is quite well-written and understandable. To my knowledge, the idea is novel and has not yet been explored in the RL literature (UPDATE: based on Reviewer #1's review, this may not be the case. I'll wait to hear the author response to this). I did not check the proofs thoroughly. However, the experiments in the principal-agent problem make sense, and it's interesting to see that iterated dominance reward schemes results in good performance for the principal agent. I appreciate that, while the main results in the paper are limited to normal-form games (which are quite restricted), there are empirical results in the appendix showing the extension to Markov games with multiple timesteps, suggesting that the applicability of iterated dominance reward schemes extend beyond the simple two-action case, where no temporally extended decisions need to be made. Even so, the Markov game considered is fairly simplistic. 

My personal curiosity about this paper revolves around scaling to real-world applications. This is not really discussed in the paper; the conclusion talks about directions for future work, for example expanding the number of RL algorithms where convergence can be proven, or producing complexity bounds for convergence. What I want to know is: what sorts of games can we compute the iterated dominance reward schemes for? How can this be applied when the space of policies becomes too large to be enumerated (and thus determining whether a policy is strictly dominated becomes impossible)? I don't expect this paper to solve these issues, but it would be nice to have a discussion of them. 

Overall, I'd say this paper is interesting to the multi-agent RL community and I could imagine others building off of this work, so I err on the side of acceptance. 


Small fixes:
- Our proof of Theorem 3.1 -> Theorem 3.2
- I'd recommend extending the captions of figures 6-8 and 9-11 in the Appendix. 
- Close bracket in Section 6.3 title
review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: This paper studies independent multi-agent reinforcement learning (MARL) in dominance solvable games. The main contribution of this paper is that the authors have proved the convergence to the iterated dominance solution for two RL algorithms: REINFORCE (Section 3.1, binary action case only) and Importance Weighted Monte-Carlo Policy Improvement (IW-MCPI, Section 3.2). Empirical analysis for principal-agent games is demonstrated in Section 4.

The paper is interesting in general, however, I do not think this paper has quite met the (very high) standard of ICLR, due to the following limitations:

1) As the authors have mentioned, the dominance solvable games are quite limited.

2) This paper only has *convergence* results, but does not have *convergence rate* results. In other words, the authors have not proved how fast the agents converge to the iterated dominance solution. Might the authors establish a convergence rate result such as a regret bound?

3) This paper assumes an unrealistic setting in which when one agent learns, the strategies (policies) of all the other agents are fixed. In other words, the agents learn in a round-robin fashion, rather than learn simultaneously. I do not think this setting is realistic in most practical problems.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: The main idea of this paper is to solve multi-agent reinforcement learning problem in dominance solvable games. The paper reviewed general multi-agent reinforcement learning and general norm-form game in game theory. The authors aim to recover multi-agent policies through independent MARL in norm-form dominance-solvable games. The paper states that one of solution concepts of dominance-solvable games is iterated dominance solution, which is different from Nash Equilibrium and may be more suitable under certain scenarios. Furthermore, the paper considers two common RL methods for control and learning policy: REINFORCE and Monte-Carlo policy iteration. The main contribution of the paper is to prove that both REINFORCE in binary action case and Monte-Carlo algorithms find the agents’ policies converging to the iterated dominance solution. The interesting aspect of this paper is that iterated dominance solution based reward scheme can guarantee convergence to the desired agents policies at a cheaper cost in practical principal-agent problems. In appendix, the paper extended its conclusion to Markov games and three possible action cases. To the current status of the paper, I have a few concerns below.

1.	It takes too much space for preliminary work and basic concepts, in Sec 1.1 (preliminary) and Sec 2 (MA-RL and Dominance-Solvable Games).
2.	The notations are inconsistent and unnecessarily complicated. For example, for agent i “its possible actions are the strategies in S_i” (section 2); any action “a \in S_i” (section 2,1); for agent i “for all s_i \in S_l” (Algorithm 1 line 2). It can be consistent to use the same notation to describe the same term. Moreover, “a score per action, x_1, …, x_{m_i}” and “each agent starts with initial logits for x_1, …, x_n”. Formally, the corner mark in the same location should represent the uniform meaning. 
3.	Typos: lemma 3.1 proof “g = … (r_{s_h}-r_{s_h})” should be “g = … (r_{s_h}-r_{s_l})”; above section 3.2 “our proof of Theorem 3.1”, should be “Lemma 3.1”.

review_title: Official Blind Review #3

final_score: rating: 1: Reject
review_content: This work studies learning under independent MARL, and shows theoretically and experimentally that two independent MARL algorithms converge for games that can be solved by iterated dominance.

This work is clear and well-written, but I do not understand what the contribution of this work is to the literature. The fact that standard MARL learning rules (e.g. independent Q learning) converge in games with iterated dominance solutions is a very well-known result in Learning in Games (see [1], [2]). The authors examined slightly different learning rules (REINFORCE and MCPI), but I would expect that almost any reasonable learning rule would converge in iterated-dominance-solvable games; if anything, it would be surprising if this were *not* the case. The applications of the convergence result result to "noisy effort" games is pretty standard and the results expected based on the theory.

Question to the authors:
- How does this work differ from the known results about convergence of naive learners in iterated-dominance-solvable games?

[1] Michael Bowling, "Convergence Problems of General-Sum Multiagent Reinforcement Learning", Sec. 5.2
[2] Fudenberg & Levine, 1999
review_title: Official Blind Review #1

Meta-review: The paper proofs that reinforcement learning (using two different algorithms) converge to iterative dominance solutions for a class of multi-player games (dominance solvable games). 

There was a lively discussion around the paper. However, two of the reviewers remain unconvinced of the novelty of the approach,  pointing to [1] and [2], with [1] only pertaining to supermodular games. The exact contribution over such existing results is currently not addressed in the manuscript.  There were also concerns about the scaling and applicability of the results, as dominance solvable games are limited. 

[1] http://www.parisschoolofeconomics.eu/docs/guesnerie-roger/milgromroberts90.pdf
[2] Friedman, James W., and Claudio Mezzetti. "Learning in games by random sampling." Journal of Economic Theory 98.1 (2001): 55-84.
Decision: Reject