Regret Matching+: (In)Stability and Fast Convergence in Games

Summary

The paper pushed RM+ based algorithm better than $O(\sqrt T)$ theoretically the first time. Specifically, the authors proposed smooth RM+, conceptual RM+ and extragradient RM+ with theoretical regret guarantee.

Strengths

To the best of my knowledge, this paper is the first one to establish RM+ based algorithm with better theoretical gurantee than $O(\sqrt T)$. Before, although people observe $O(1)$ regret guarantee of RM+ in *most* games (there exist counterexamples that make it around $O(T^{0.7})$), there's no variant of RM+ that has better than $O(\sqrt T)$ regret bound. However, this paper proposed a really simple and straight-forward version of RM+ and proved better regret bound. This may partially reveal why RM+ and CFR+ have good performance in many games.

Weaknesses

- The main text of the paper does not reveal much about the proof intuition.

Questions

I'm a bit confused about the CFR part. Does CFR equipped with the new RM+ has constant social regret?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

The authors discussed limitations in the conclusion.

Summary

The authors study $\text{RM}^+$. They show that there are instances of loss sequences in variants of $\text{RM}^+$ unstable. The authors point out that the decisions of $\text{RM}^+$-based algorithms are performed by normalizing an aggregate payoff vector. Hence, if one inputs an instance that is "close" to the origin, two consecutive aggregate payoffs can point in different directions in spite of being relatively close, which could make the algorithm cycle between two strategies. The authors exhibit an example establishing that the potential instability mentioned does indeed occur. The authors then present two methods to the instability discussed dealing with having two consecutive aggregate payoffs being too close to the origin. In one, they simply re-initialize the regret vector too some non-zero amount. The other solution is simply to ignore an area of the space near the origin and projecting onto that space. Not surprisingly, the second method seems to have a better theoretical guarantee but it's more expensive to implement.

Strengths

The paper is very-well written. It was a pleasure to read. I had some very minor comments about the draft in regards to exposition and writing. I also like how natural their solutions are to the issue of instability. The proofs seem to be correct and everything feels very natural, which is probably due to the authors' writing. The experiments also seem reasonable and establish that their methods perform well with random synthetic data.

Weaknesses

Would the authors please put their contribution in context? How "important" it is to the overall community? They have already addressed some of this in the draft, but I was hoping for longer explanation in the rebuttal period. Some small suggestions 1. Generally, I think citations are not appropriate for abstracts since abstracts are often read independently of the full paper, so readers may not have access to the cited sources at that stage. If you want to include a specific reference or highlight previous related work in the abstract, I recommend paraphrasing the information or briefly mention the authors' names and year of publication without the specific citation. This maintains the abstract's clarity and conciseness while still giving credit to the relevant work. I realize adding the references simply as numbers might have done intentionally to hide the identity of the authors. 2. I'd recommend combining the sentences for on lines 45 to 48 "However, in a game setting..." and "Indeed, we identify..." to avoid using the word "this" which is a bit ambiguous. 3. Would it be possible to list the references in increasing order? 4. For the sake of completeness, it would be useful if T were defined as the horizon or something like that before being used. 5. Notation-wide, I think $\Delta(3)$ should probably be $\Delta^3$ on line 169. 6. The definition of $\mathbf{z}^t$ in Theorem 4.1 was a bit unclear to me until I saw it defined in Algorithm, 1. Maybe declare it before like you did for Theorem 5.1 in expression (2) 7. On line 346, when you say "$\text{RM}^+$-based algorithms" I would add in parenthesis to refer to which algorithms are meant (either by number or name)

Questions

Q1: More the smooth predictive RM^+, was there anything essentially different if one uses a different threshold for $||R_1||$? Now, 1 is being used, which seems very reasonable. However, how ``far away" does one need to know from 0 to help stabilization? Like if I were to change 1 for a constant C, how does this affect the theoretical guarantees? Q2: I must be missing something, but I don't fully understand why clairvoyant CFR doesn't seem to perform as well with EFG as it does with matrix games. If you were to use the strategic game equivalent of the EFGs tested, what is the performance. I apologize because there is probably something I'm missing. Q3: In your experiments, it seems the data was generated randomly. This is good to know. However, did you try to create data that would be more "difficult" like maybe a space that is an annulus?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors make an effort of what they have consider and the limitations of their work in terms of experimental results obtained for EFGs I also would like to see how the algorithm performs in "harder" spaces than simply random ones.

Summary

The paper studies variants of the RM+ algorithm for learning in games. They show that RM+ does not satisfy stability, which is an important property for proving good regret bounds, if all players play according to the same algorithm. The paper "fixes" the instability of RM+ by considering a restarting and chopping variant which stabilise RM+ and then prove O(T^{1/4}) and O(1) individual and social regret bounds respectively.

Strengths

For the most part paper is well written and easy to follow. The paper points to the importance of stability for proving sub-sqrt regrets bounds, which I find interesting.

Weaknesses

In my opinion Sec 5 too dense and thus it lacks clarity. I would suggest to put only the main technical result there , or to give a skimmed version, in which the more technical assumptions are deferred to the appendix. I think that 4 statements with little discussion, cannot convey clarity.

Questions

1. It seems that for the restarting trick you cannot prove O(1) social regret. Is this because restarting may happen at different times for different players? If so I think you should include a larger discussion on this. Moreover in the abstract it seems like both restarting and chopping would give O(1) social regret. I think you should state explicitly in the abstract that only holds for the chopping variant. 2. Do you conjecture that O(1) social is only hard to prove for the restarting method or that is not reached?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

yes

Summary

This paper studies the RM+ algorithm and its variants in the context of learning in games. - They first show that RM+ and predictive RM+ can be unstable in certain environments. Although the unstable player benefits from instability, the regret of other players may blow up because they are forced to make predictions in an unstable environment. - Then they provide several approaches to stabilize RM+. - The first approach, called **stable predictve RM+**, requires each player to (asynchronously) restart whenever $\mathbf{R}^t_i$ becomes small. Although this stabilizes the algorithm and guarantees $O(T^{1/4})$ regret for each player, it's hard to bound the social regret by $O(1)$ . - The second approach is called **smooth predictive RM+**. It chops off the area of decision space that is too close to the origin by adding projection steps. Besides individual regret bounds, this approach also guarantees $O(1)$ social regret. - They also propose **Conceptual RM+** (and the one fixed-point approximation of it) that achieves $O(1)$ individual regret and **Extragradient RM+** that achieves $O(1)$ social regret. - The authors conduct experiments on matrix games and extensive-form games.

Strengths

- The paper contributes to the theoretical understanding of the RM+ and its variants. It is the first one to show the instability of RM+ and predictive RM+ by concretely constructing a hard case that exhibits the $T^{-0.5}$ convergence rate. - The paper proposes several variants of RM+ that not only have appealing theoretical guarantees on both individual regret and social regret, but also perform well in experiments. - The paper is very well-written. The authors clearly explain the intuition behind the theoretical results.

Weaknesses

- In section 3, the authors construct a hard case for RM+ and predictive RM+ where the empirical convergence rate are on the order of $T^{-0.5}$. However, the residue errors of the linear fit in Figure 1 are quite large. Providing a theoretical proof that the asymptotic convergence rate is indeed $T^{-0.5}$ would strengthen the result. - Given the connection between RM+ and OMD in [12] and the fast convergence properties of OMD in games, the performance guarantee for the stabilized variants of RM+ do not seem surprising. Nonetheless, as mentioned by the authors, RM+-based algorithms are not inherently stable, so they need extra considerations. - The experiments show the strong performances of the proposed algorithms compared to RM+ and PRM+. It would be better if the authors also compared their performance with the optimistic/predictive FTRL/OMD algorithms that enjoy fast convergence rates in theory.

Questions

In the proof of Theorem 3.1, the authors constructed an example where the precision of the losses increases with $T$ (the minimum value is exponentially small), a scenario that may not practically appear. - Is this phenomenon of increasing precision the fundamental reason of instability, or is it merely an artifact of the proof? - Does this same phenomenon appear in the subsequent experiments involving the $3\times3$ matrix game? - If a bounded precision assumption were introduced, could this potentially stabilize RM+ or PRM+?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes

Summary

The paper focuses on investigating the stability of the Regret Matching+ based algorithm. It demonstrates that both RM+ and predictive RM+ algorithms exhibit instability, leading to significant regret for other players within a game setting. To address this issue, the authors propose two methods: restarting and chopping off. By incorporating these methods, the authors introduce several variants of RM+-based algorithms, including stable/smooth Predictive RM+, conceptual RM+, and Extragradient RM+. The paper also provides theoretical regret bounds for these proposed algorithms, further establishing their efficacy in mitigating instability and reducing regret.

Strengths

One of the key contributions of this paper is the theoretical speedup provided for the RM+ based algorithm, which is crucial for achieving fast convergence in games. By offering improved convergence guarantees, the proposed advancements in the algorithm can significantly enhance its practical utility. The writing in the paper is well-organized and clear, effectively conveying the technical details. The strength of the paper's technical aspects further adds to its overall quality, making it more accessible and understandable for readers. The comprehensive experimental results presented in the paper further enhance its credibility. Notably, the authors also consider the application of the algorithm in extensive form games, which is important for real-world scenarios. This consideration highlights the practical relevance and versatility of the proposed techniques. Overall, the paper provides valuable theoretical insights, demonstrates technical proficiency, and showcases the practical applicability of the proposed algorithm, making it a strong contribution to the field.

Weaknesses

Just a small point about presentation. It would be beneficial for the authors to consider organizing the algorithms discussed in the paper by creating a table. This table can help provide a clear overview of the different algorithms, highlighting their similarities and differences.

Questions

The thoerem need $\eta$ to be small. However, in the matrix game experiment, $\eta$ is chose as $10$. Is $\eta = 10$ too big in this setting?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The authors have adequately addressed the limitations.

I have read the author(s)'s rebuttal comments

Thank you for your comments. I have read them and I have changed my review accordingly.