No-Regret Learning in Extensive-Form Games
summary
Introduces Extensive-Form Regret Minimization (EFR), an algorithm that takes a chosen deviation class Φ and minimizes regret relative to Φ with complexity that scales with the size/structure of Φ, and converges to EFCE when Φ is the set of behavioral deviations. EFR encodes known weakenings (causal/reduced, counterfactual, action) at runtime, runs local regret minimizers at each information set like CFR, shows small-game experiments (Goofspiel, Sheriff) where behavioral deviations give higher payoffs, and poses the open question of the largest efficiently learnable Φ.
AI-written summary · about
chapters (24)
- 0:00Introduction
- 0:52Counterfactual regret minimization
- 2:24Normal form games
- 4:20Regret minimization
- 5:13Minimize Regret
- 10:48External vs Internal
- 12:26Internal Regret
- 18:05NoRegret Learning
- 22:15ExtensiveForm Regret Minimizer
- 24:07Correlation Equilibrium
- 24:58Course Correlation
- 26:17Stochastic Matrices
- 27:35Regret Matching
- 29:36Fixed Point
- 29:54Time Selection
- 31:38Weights
- 32:34Information Set
- 33:07Pop Model
- 34:24Swap Deviation
- 35:01Reduction
- 36:04Matching Penny Example
- 38:50Behavioral Deviations
- 46:58Experiments
- 49:30Future
related talks
47mRebel: Combining Deep Reinforcement Learning and Search for Imperfect-Information Games
45mAGT and Machine Learning
39mLet LLMs Wander: Engineering RL Environments
53mIterative preference learning methods for large language model post training
56mOn the Curses of Future and History in Off-policy Evaluation in non-Markov Environments
11mThe Unreasonable Effectiveness of Prompt Learning
41mLet LLMs Wander: Engineering RL Environments
12mLanguage-Model Probabilistic Programming for Improving Autoformalization via Cycle(…)