Reproduce “Regret Matching+: (In)Stability and Fast Convergence in Games” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, Haipeng Luo
Researchers developed stabilized versions of the Regret Matching+ algorithm, demonstrating that existing RM+ variants can be unstable, which limits their theoretical convergence. The new stable algorithms achieve faster theoretical guarantees of O(T^-1/4) individual regret and O(1) social regret, outperforming the previous O(T^-1/2) bounds and showing improved empirical performance in various games.
Key insights
- Standard Regret Matching+ and its predictive variants can exhibit instability due to their normalization step, leading to rapid strategy oscillations detrimental to other players' convergence.
- Implementing stability directly into RM+-based algorithms is crucial and sufficient to achieve theoretically faster regret bounds, matching or exceeding those of optimistic OMD.
- A novel "Conceptual RM+" framework, leveraging fixed-point approximations, provides O(1) individual regret and extends effectively to complex extensive-form games.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.