Research
Constant Individual Regret in General Games
arXiv:2608.31166v1 Announce Type: new Abstract: Uncoupled no-regret dynamics provide a decentralized route to equilibrium, but prior guarantees for individual regret retain a polylogarithmic dependenc
arXiv:2608.31166v1 Announce Type: new Abstract: Uncoupled no-regret dynamics provide a decentralized route to equilibrium, but prior guarantees for individual regret retain a polylogarithmic dependence on the horizon. We remove this dependence for every finite N-player normal-form game under full-information feedback. We introduce ECHO-OFTRL: optimistic follow-the-regularized-leader (OFTRL) equipped with an EMA cascade for high-order optimism (ECHO), where EMA denotes exponential moving average. The algorithm is deterministic and fully uncoupled. If m_{max} denotes the largest action-set size, then, simultaneously for every horizon Tgeq1, it guarantees that each of the N players in the game incurs regret upper bounded by O(extrm{poly}(N, log m_{max})). Our algorithm leverages a new form of optimism inspired by modern filter design.
Related
- Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization
- Optimal Alternating Regret for Online Learning and Games
- Minimax Alternating Regret for the Experts Problem and Online Convex Optimization
Source: arXiv cs.LG | 2026-09-01