Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper considers the problem of finding a nash equilibrium in two player games where each of the algorithm runs an RL algorithm. In this paper they ask the question -- which nash equilibria does the dynamics converge to in this two player game (where each player optimizes based on a policy gradient algorithm). They construct two player games with multiple nash equilibria; one is a favorable nash equilibria where both players get high rewards while the other is a less favorable nash equilibria where both player only get medium rewards. In such games they first show that in general simply running policy gradient on the natural reward function i.e., the observed payoff will not lead to the desirable nash equilibria. The goal of this paper is to ameliorate this by considering perturbations in the reward space. At a high level, the algorithm learns multiple policies on a class of games generated by sampling multiple reward functions from a family and training one policy per sampled reward function using PG. Then using an evaluation function, the best policy is picked by evaluating each of the learnt policies on the original game.

My comments on this paper are as follows. First, I think the question studied in this paper is well-motivated. In general, controlling for which nash equilibrium a two player (or N-player in general) dynamics should converge to is an important problem. This problem has been extensively considered in the game theory and online learning literature. So the importance naturally extends to the multi-agent RL world. The proposed algorithm here is reminiscent of follow-the-perturbed-leader, where perturbations in the reward space (as opposed to the policy space) leads to improved algorithms. The strengths of this paper are as follows. 

- The initial parts of the paper are well-written. They consider simple toy examples to show that PG can indeed lead to bad equilibria. Then using some stylized analysis, show that sampling from the reward space can indeed overcome this problem (in games where the family of reward functions for which PG converges to the desired nash equilibria is large, yet for the specific game at hand PG leads to a bad equilibria).
- Extensive experimental evaluation. The paper considers a total of four test bed games and shows the benefit of using reward randomization in these settings.  In the supplementary materials there is extensive simulated results on these games. In particular, they fix a particular "true" payoff matrix and then run their algorithm against a few baselines assuming this game.
- The problem considered is important, not just in the artificial game setting but also in many practical applications which can be modeled as a game that ends up having multiple NE.
- Specification of the hyper-parameters of the algorithm used. Also evaluating the algorithms using multiple seeds (which is an important criteria for RL algorithms).

Having said that, here are some of the weakness of this paper.

- The considered algorithm "works" probably because the settings are easy (As defined by convergence to the correct NE by PG algorithms) for an average instance from the space of all instances. In particular, consider the following thought exercise. Let us sample a random payoff matrix from the space of payoffs and run PG on this game. What is the prob. that PG will get stuck at the bad NE? If the answer is that this prob. is high, then it is also likely that the proposed algorithm will not work (since this is essentially the idea being exploited in the algorithm). On the other hand, if the prob. is low then it shows that in general the considered game is easy and this algorithm only optimizes for the "outlier" scenarios. In general, that is the biggest weakness I see in this paper; it makes a pretty strong implicit structural assumption on the games and their corresponding payoff landscape. Am I missing something here?
- I also think this paper could improve its presentation. First, the experimental setup is pretty unclear. What is the reward function in each of the games. I do not see a formal definition. Likewise, the algorithm description itself is pretty informal. It takes a bit of leap of faith in assuming that there exists a well-defined evaluation function (that is computable). It would greatly help the paper in readability if things are written in a formal manner. Moreover, for each of the games (possibly in supplementary) taking a detailed approach to the setup of the game, the reward function and the evaluation function would help in reproducibility and understanding of this paper. Finally, I also think some of the graphs could use better color-schemes or other differentiating factors apart from color. Some of the colors are pretty close to each other and in general harder to read.

My overall evaluation is based on the first point in my weakness section and considering the paper in totality. If the authors can sufficiently answer that question and show convincing experiments and/or explanation I am willing to change my score.
review_title: Important problem, but proposed algorithm probably makes implicit assumptions?

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper focuses on an important problem, the existence of multiple Nash equilibria in strategic games, and proposes a relatively simple mechanism, reward randomization, which allows agents to discover higher-payoff equilibria in games where normal decentralized policy gradient methods would converge to suboptimal ones. What is proposed is to perturb actual rewards with random perturbations, which essentially, to my mind simply creates a range of games agents find themselves in so that the chances are increased that policy search will end up finding more efficient equilibria. 

While the overall idea is interesting, the paper actually lacks a precise problem definition that would also link it to the (huge) literature in the area, which it does refer to, but actually not directly compare to, as the now common deep learning route to solving the fundamental (and notoriously hard) problem is applied, which operates in a completely different setting - training function approximators using an enormous number of games played offline. This cannot be compared to the problems considered in game theory and traditional multiagent reinforcement learning, where policies are learned online from a relatively small number of examples, and an algorithm needs to be able to perform well against very broad classes of opponents, without the benefit of training itself on modified problems pre-play.

That said, I appreciate there is value to the theoretical results that provide some more general evidence for the potential importance of the method. 

The paper makes a lot of assumptions about structure in larger games in order to apply feature-based learning approaches, but one could have approached the whole problem with a simple game and then simply demonstrate how it scales up - it seems like there is not that much to say about the conceptual ideas when one reads all the details. 

An excessive part of the paper is spent on explaining ideas in the stag hunt game and describing the other games, with a lot of further detail included in the lengthy supplementary material, but much of this seems to detail the very specific process of applying the technique and competing alternatives in a few specific games - I don't think much of this adds to our understanding of the problem. 

Beyond these criticisms, the paper is generally clearly written, and appears technically sound. 
review_title: Successful application of reward perturbation techniques to identify high-value equilibria that offers limited insights

final_score: rating: 7: Good paper, accept
review_content: This work proposes and evaluates reward randomization as a strategy to discover efficient policies in multi-agent games. By perturbing the reward structure of a game, the authors show that policy gradient techniques can find better equilibria and lead to complex new behaviors.

Reward randomization is a fairly intuitive technique. In matrix form games, this just involves replacing the game's rewards with those drawn from some distribution. In more complex games, the authors propose distilling the game's reward structure into a small number of components and randomizing the weights placed on those components to compute the total payoff. The authors demonstrate that both theoretically and empirically, Reward-randomized Policy Gradient (RPG) outperforms standard baseline techniques. It also produces a diverse set of candidate policies, which the authors demonstrate can be used to train an adaptive agent.

The paper is clear and well-written. The figures are helpful and detailed. Overall, my impression is positive.

Some analysis of the sensitivity of this method would have helped. Much of the complexity is folded into choosing an appropriate reward distribution, and it would be good to know how dependent the results are on being able to choose a "good" distribution from which to sample.

I would have appreciated more of a discussion about why reward randomization works. Fundamentally, this appears to rely on the idea that while the action space may in general be very large, for most natural games, there are no reasonable reward schemes that incentivize the vast majority of these behaviors. As a result, it is feasible to explore the space of potentially optimal policies simply by exploring the space of reasonable rewards. Can this statement be formalized? And how well does it generalize to games other than the ones considered?
review_title: Review

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes to use reward randomization to explore the policy space in multi-agent games. The idea is that in most of multi-agent games multiple Nash Equilibriums exist with different payoffs. The goal is to find the NE that provides the highest payoff. 
Policy Gradient and its variants, which have obtained a lot of practical successes, in general fail to find the NE with the highest payoff. 
A first approach could be to re-start PG with different initializations for finding different NEs and then selects the best one. 
In contrast, the authors propose to randomize the reward structure for exploring different policies. Then the policies are optimized on different reward structures with PG. The policy that leads to the highest payoff is selected and then optimized with PG on the original structure of rewards.
The authors provide some theoretical results to show that reward randomization has a highest probability to find the best NE than random initializations of PG. 
The authors also propose to use reward randomization for learning an agent against different type of opponents. 
The experiments are done on three games and show the interest of their approach in comparison with several baselines.

The paper is well written, proposes interesting ideas supported by analytical and experimental results. However the reviewer has some remarks, concerns and questions.

Concerning Theorem 1, O(\epsilon) for a probability is not a strong result: it can be higher than 1. After looking the proof, the reviewer thinks that it seems possible to provide the right expression of the probability of finding the high payoff NE. 

Concerning Theorem 2, the proof is quite informal and the reviewer is not sure that it is correct. In particular, it is not clear if the same condition than in Theorem 1 is necessary: a-b = \epsilon (d-c). In the statement it seems not because a,b,c,d are uniformly sampled and there is no \epsilon in the statement, but the remark stating that RR necessitates at most O(\log1/\epsilon) times to achieves 1-\epsilon suggests that it does. 
Moreover the reviewer thinks that the proposed analysis (statements of Theorem 1 and 2) will be more convincing if the number of starts, needed by the two approaches for finding w.h.p the high payoff NE, is compared (as you did in the remark).

In Algorithm 2, the authors write that the policy \pi’_2 is drawn from \Pi_2, but in the experiments section 5.3, the authors explain that \Pi_2 is carefully built, meaning that the policies in \Pi are chosen to be effective. This step is not in Algorithm 2, which is still correct, but this suggests that if \Pi_2 is not well chosen Algorithm 2 does not work.
This leads to my main concern. The rewards seem to be uniformly sampled with the constraint that their sum is no more than C_{max}. However, with this kind of uniform sampling the set of games used for exploring policies contains a lot of games that does not respect the constraints induced by the original game M. For instance in stag-hunt we have a \geq b \geq d > c. Using uniform sampling most of the induced games do not respect this reward structure. So it can lead to inefficient policy. For instance if a < b and a < d an efficient policy is to not track the stag and to hunt the hare. The reviewer understands that the diversity of rewards allows the diversity of obtained policies, but the reviewer is wondering if sampling the rewards with respect to the reward constraints of the game is not enough to obtain the diversity of policies. At a minimum, it could be interesting for the reader to have this reasonable baseline. By the way, may be this baseline allows Algorithm 2 working without carefully choosing the set of policies \Pi.

Overall, the paper is interesting, but the reviewer thinks that it could be better. The reviewer can change his mind if his concerns are answered.


___________________________


After the rebuttal I raised my score.

review_title: The paper is interesting but it could be improved

Meta-review: All the reviewers are in favor of accepting this paper, which demonstrates both theoretically and empirically the value of reward randomization in solving multi-agent reinforcement learning problems. The rebuttal phase was crucial in improving the quality and evaluation of the submission. I am glad to recommend acceptance.
Decision: Accept (Poster)