Variants and Invariants in No-Regret Algorithms
summary
Shows that discrete no-regret procedures map to a continuous-time differential inclusion by replacing payoffs with conditional expectations and treating martingale noise via stochastic approximation, then proves external and internal regret vanish by applying Blackwell approachability and a dual Nagumo viability condition. Constructs potentials (gradient gives mixed strategy) to get O(1/T) regret for mirror descent and dual averaging, and shows limit points lie in variational-equation Nash sets when the game’s vector field is dissipative/monotone.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 2:05NoRegret Procedure
- 2:58ExternalRegret
- 3:58Strategy satisfies Eternal Consistency
- 4:12Internal Regret
- 5:07Average
- 6:42Blackwell Theorem
- 7:54Approachability
- 17:37External Regret
- 18:42Invariant Measures
- 34:55Continuous Time
- 35:41Dwell averaging
- 35:59French conjugate
- 36:47Correction term
- 37:18Questions
related talks
47mRebel: Combining Deep Reinforcement Learning and Search for Imperfect-Information Games
42mA Primal-dual Analysis of Margin Maximization by Steepest Descent Methods
32mMulti-Player Multi-Armed Bandit: Can We Still Collaborate at Homes Without "Zoom"?
45mAGT and Machine Learning
56mOn the Curses of Future and History in Off-policy Evaluation in non-Markov Environments
41mSpotlight Talks
01h 17mGeneralization I
39mBayesian Deep Learning with Edward (and a trick using Dropout)