Fast Rates for No-Regret Learning in General Games
summary
Shows that when all players use Optimistic Hedge in finite general‑sum games each player’s external regret falls to roughly O(log |A| · log^4 T) — i.e., near polylog T rather than √T — proved by a path‑length bound plus a stability‑based reduction using a proper online learner and sequential covers. Extends to swap regret (≈ players×actions×log^4 T) and to infinite games with finite Littlestone dimension, giving regret ~T^{1/4}·poly(Littlestone); results are constructive and proven.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 1:25Repeated Game
- 2:47Background
- 4:55Model
- 7:04Hedge
- 9:53Main Result
- 12:06Proof
- 15:10Extensions
- 20:42Twoplayer zerosum game
- 22:26Nash equilibrium
- 28:15Overview
- 29:04Little Dimension
- 33:25Improper Learning
- 37:24Stability
- 42:08Conclusion
related talks
01h 17mOnline Reinforcement Learning and Regret
58mMemory-Regret Tradeoff for Online Learning
48mA Simple Condition for Constant Regret in Online Decision-Making
44mParsimonious Learning-Augmented Algorithms
31mLearning in Games with Best-Response Oracles
35mOnline Optimization and Learning Under Long-Term Convex Constraints and Objectives
46mDynamic Regret Minimization for Bandits without Prior Knowledge
42mBypassing the Impossibility of Online Learning Thresholds: Unbounded Losses and Transductive Priors