Reproduce “Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and 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
Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng
Researchers from Yale, MIT, USC, and UVA introduced "proximal regret" and its corresponding "proximal correlated equilibria" (PCE) as a new, tractable solution concept for online learning and games. They demonstrated that standard Online Gradient Descent (GD) and Mirror Descent (MD) algorithms inherently minimize this stronger form of regret with optimal O(sqrt(T)) bounds, bridging the gap between coarse and correlated equilibria.
Key insights
- Proximal regret offers a new, tractable class of solution concepts (PCE) that are strategically stronger than CCE yet efficiently computable, residing between CCE and CE.
- Online Gradient Descent's efficacy stems from its inherent ability to minimize proximal regret for a wide class of functions, providing a deeper theoretical justification for its widespread empirical success.
- A novel key inequality was developed to prove the sublinear regret bound for GD, allowing non-telescoping terms to be managed in the analysis.
- Optimistic Gradient Descent further improves learning dynamics in multi-agent games, achieving faster convergence to approximate PCE and constant social proximal regret.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.