Real Algebraic Geometry in Computational Game Theory
summary
Proves a worst-case convergence bound for Howard's policy-iteration on concurrent reachability games, showing iterations are bounded by a doubly-exponential-type function of positions and action counts (and hence depend exponentially on the required precision). The proof uses real algebraic geometry tools from Basu-Pollack-Roy (a low-degree universal representation / sampling lemma) to give a concrete patience bound (minimum nonzero probability size) and constructs a matching example, yielding a tight exponential lower bound and a verified algorithmic consequence.
AI-written summary · about
chapters (11)
- 0:00Start
- 0:13Computational Game Theory
- 7:01R.A.G. engine: The Sampling Theorem
- 9:33Concurrent Reachability Game (CRG)
- 15:05Howard's algorithm for CRGS
- 17:16Properties
- 17:39Main theorem
- 19:04Value iteration dynamic
- 19:37Step 2: Reduction to bounding patience
- 20:33Step 3: Bounding patience using RAG.
- 23:18Tight example
related talks
20mThe Complexity of Infinite-Horizon General-Sum Stochastic Games
28mConfounding-Robust Policy Evaluation In Infinite-Horizon Reinforcement Learning
40mExtending Generalization Theory Towards Addressing Modern Challenges in Machine Learning
37mComputing Probabilistic Bisimilarity Distances via Policy Iteration
01h 12mA Brief Introduction to Algorithms, Game Theory and Risk-Averse Decision Making
01h 11m(Hidden) Symmetries of Computational Problems (continued)
15mMulti-Agent Reinforcement Learning In Stochastic Games: From Alphago To Robust Control
01h 06mLearning in Games II