No-Regret Learning in Bayesian Games

2015/07/02 by Jason D. Hartline, Vasilis Syrgkanis, Hartline, Jason +3 · 2 citations
Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #Computer Science and Game Theory (cs.GT) #Economic theories and models #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #Game Theory and Applications #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.1507.00418

openalex publication_date 2015/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Recent price-of-anarchy analyses of games of complete information suggest that coarse correlated equilibria, which characterize outcomes resulting from no-regret learning dynamics, have near-optimal welfare. This work provides two main technical results that lift this conclusion to games of incomplete information, a.k.a., Bayesian games. First, near-optimal welfare in Bayesian games follows directly from the smoothness-based proof of near-optimal welfare in the same game when the private information is public. Second, no-regret learning dynamics converge to Bayesian coarse correlated equilibrium in these incomplete information games. These results are enabled by interpretation of a Bayesian game as a stochastic game of complete information.

Cited by

• On the Tractability of Public Persuasion with No Externalities
• Computing Optimal Coarse Correlated Equilibria in Sequential Games

Related

• Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchy
• Barriers to Welfare Maximization with No-Regret Learning
• On the Interplay between Social Welfare and Tractability of Equilibria
• Is Learning in Games Good for the Learners?
• The Computable but Not Learnable Information-Value-Free Equilibria and Regulation of Algorithmic Collusion