Learning in Games with Best-Response Oracles

on YouTube ↗31m

" summary

Shows that with a best-response oracle and value queries any algorithm needs Omega(sqrt(n)) time to approximate a zero-sum n-by-n game to constant accuracy, by reduction from Aldous local search hard instances. Gives a matching algorithm that runs in O(sqrt(n)/epsilon^2) rounds to get epsilon average regret, using a construction that samples sqrt(n) experts and maintains queues of recent leaders. Result is a tight quadratic speedup over oracle-free learning.

AI-written summary · about

" chapters (5)

1. 0:00Introduction and motivation
2. 16:41Computational model discussion
3. 19:31Main complexity results
4. 21:16Proof via local search
5. 24:59Algorithmic improvements

" related talks

• 49mOracle-Efficient Online Learning or: How to Use Non-Robust Optimization for Robust LearningNika Haghtalab · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 49mFast Rates for No-Regret Learning in General GamesNoah Golowich · Adversarial Approaches in Machine Learning 2022
• 55mLearning Minimax Estimators Via Online LearningPradeep Ravikumar · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 58mMemory-Regret Tradeoff for Online LearningAviad Rubinstein, Binghui Peng · Sketching and Algorithm Design 2023
• 44mParsimonious Learning-Augmented AlgorithmsRavi Kumar · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 12mTheoretical understanding of learning through the computational lensBinghui Peng · Meet the Fellows Welcome Event Fall 2024
• 01h 09mLearning in Games IDrew Fudenberg · Economics and Computation Boot Camp 2015
• 44mSomething for Almost Nothing: Advances in Sub-Linear Time AlgorithmsRonitt Rubinfeld · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)