Optimal No-Regret Learning in General Games via Clairvoyant MWU

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=GgLEa5YLEQ4


Duration: 1:22:20
701 views
8

Georgios Piliouras (Singapore University of Technology and Design)
https://simons.berkeley.edu/talks/optimal-no-regret-learning-general-games-clairvoyant-mwu
Learning in the Presence of Strategic Behavior

In this paper we solve the problem of no-regret learning in general games. Specifically, we provide a novel, simple and efficiently computable learning algorithm, Clairvoyant Multiplicative Weights Updates (CMWU), that achieves constant regret in all normal-form games with fixed step-sizes. The cumulative regret of our algorithm provably decreases linearly as the step-size increases. Our findings depart from the prevailing paradigm that vanishing step-sizes are a prerequisite for low regret as championed by all state-of-the-art methods to date. Our arguments extend well beyond normal-form games with little effort.



Other Videos By Simons Institute for the Theory of Computing


2022-04-01How (Not) to Run a Forecasting Competition: Incentives and Efficiency
2022-04-01The Challenge of Understanding What Users Want: Inconsistent Preferences and Engagement Optimization
2022-04-01Learning, Incentivizing Improvement, and Fairness in the Presence of Strategic Agents
2022-03-31The Transfer Performance of Economic Models
2022-03-31Analysis of the Alternating Mirror Descent for Constrained Min-Max Games
2022-03-31In Praise of Game Dynamics
2022-03-31Experimental Evidence of Individual Human Learning in Games
2022-03-30Aggregating Conflicting Forecasts
2022-03-30Beyond Open Loop Algorithm Design: Learning from Decision-Dependent Data
2022-03-30Predicting Cooperation Rates With A Learning Model
2022-03-30Optimal No-Regret Learning in General Games via Clairvoyant MWU
2022-03-29Forecast Hedging, Calibration, And Game Equilibria
2022-03-29Mechanisms To Procure Information Without Verification
2022-03-29Identification Analysis In Models With Set Valued Predictions
2022-03-29What Does It Take To Be a Good Fisherman?
2022-03-28The Limits Of Regularized Learning In Games
2022-03-25Kernel Methods For Causal Inference
2022-03-25New Approaches To Learning Nonparametric (Latent) Causal Graphical Models
2022-03-25Collaborative Causal Discovery With Atomic Interventions
2022-03-25Simple Yet Efficient Estimators For Network Causal Inference...
2022-03-25Active Invariant Causal Prediction: Experiment Selection Through Stability


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Learning in the Presence of Strategic Behavior
Georgios Piliouras