Kernelized Multiplicative Weights for 0/1-Polyhedral Games:...
summary
Paper proves that Optimistic Multiplicative Weights on the normal-form equivalent of an extensive-form game is simulatable with D+1 kernel evaluations per update, where D is tree dimension, by using a 0/1 feature map and a kernel computed bottom‑up with sums and products over subtrees. The resulting Kernelized OMWU runs in linear-time per iteration in tree size (amortized from a naive quadratic), requires strategy polytopes with 0/1-coordinate vertices, inherits polylogarithmic and near-constant regret guarantees, yields last-iterate convergence and tighter dependence on tree size than prior EFG methods.
AI-written summary · about
chapters (9)
- 0:00Start
- 25:46Normal-Form Games
- 33:54Main theorem
- 35:57Idea #1
- 40:24Intuition
- 42:27Kernel of 2
- 43:44Summary
- 45:58Inspirations
- 46:38Open Questions
related talks
41mSpotlight Talks
59mPCPs and Global Hyper-contractivity 1
56mOn the Curses of Future and History in Off-policy Evaluation in non-Markov Environments
01h 00mPCPs and Global Hyper-contractivity 3
45mAGT and Machine Learning
01h 09mEquivariant RL
30mUnfamiliar Terrain
01h 04mPCPs and Global Hyper-Contractivity 2