# Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games

arXiv: https://arxiv.org/abs/2511.01852 · HTML: https://mlsanity.com/paper/2511.01852/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 81 references that are in the map.
- First posted on arXiv 3 Nov 2025.

## Builds on (most cited first, 30 of 42)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Strategizing against No-regret Learners](https://mlsanity.com/paper/1909.13861/) (2019)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games](https://mlsanity.com/paper/2204.11417/) (2022)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [Near-Optimal No-Regret Learning Dynamics for General Convex Games](https://mlsanity.com/paper/2206.08742/) (2022)
- [Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2104.01520/) (2021)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games](https://mlsanity.com/paper/2202.00237/) (2022)
- [Pareto-Optimal Algorithms for Learning in Games](https://mlsanity.com/paper/2402.09549/) (2024)
- [Full Swap Regret and Discretized Calibration](https://mlsanity.com/paper/2502.09332/) (2025)
- [Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games](https://mlsanity.com/paper/2401.15240/) (2024)
- [Gradient Equilibrium in Online Learning: Theory and Applications](https://mlsanity.com/paper/2501.08330/) (2025)
- [The Relationship between No-Regret Learning and Online Conformal Prediction](https://mlsanity.com/paper/2502.10947/) (2025)
- [High-Dimensional Calibration from Swap Regret](https://mlsanity.com/paper/2505.21460/) (2025)
- [Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games](https://mlsanity.com/paper/2412.20291/) (2024)
- [Regulation of Algorithmic Collusion](https://mlsanity.com/paper/2401.15794/) (2024)
- [Faster Rates for No-Regret Learning in General Games via Cautious Optimism](https://mlsanity.com/paper/2503.24340/) (2025)
- [Correlated and Coarse equilibria of Single-item auctions](https://mlsanity.com/paper/1601.07702/) (2016)

## Built on by (most cited first, 3 of 3)

- [From No-Regret to Strategically Robust Learning in Repeated Auctions](https://mlsanity.com/paper/2601.03853/) (2026)
- [Optimal Coarse Correlated Equilibria in Mean Field Games: Linear Programming and No-Regret Learning](https://mlsanity.com/paper/2606.20062/) (2026)
- [Learning in Continuous Games from Pairwise Preference Feedback](https://mlsanity.com/paper/2610.05428/) (2026)

## Abstract (arXiv)

Learning and computation of equilibria are central problems in game theory, theory of computation, and artificial intelligence. In this work, we introduce proximal regret, a new notion of regret based on proximal operators that lies strictly between external and swap regret. When every player employs a no-proximal-regret algorithm in a general convex game, the empirical distribution of play converges to proximal correlated equilibria (PCE), a refinement of coarse correlated equilibria. Our framework unifies several emerging notions in online learning and game theory-such as gradient equilibrium and semicoarse correlated equilibrium-and introduces new ones. Our main result shows that the classic Online Gradient Descent (GD) algorithm achieves an optimal O(√T) bound on proximal regret, revealing that GD, without modification, minimizes a stronger regret notion than external regret. This provides a new explanation for the empirically superior performance of gradient descent in online learning and games. We further extend our analysis to Mirror Descent in the Bregman setting and to Optimistic Gradient Descent, which yields faster convergence in smooth convex games.