No-Regret Learning in Bayesian Games

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 in corpus (7)

• Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization
• Equilibrium Learning in Combinatorial Auctions: Computing Approximate Bayesian Nash Equilibria via Pseudogradient Dynamics
• Robust Multi-agent Counterfactual Prediction
• Bayesian Persuasion with Sequential Games
• Competitive Policy Optimization
• On the Tractability of Public Persuasion with No Externalities
• Computing Optimal Coarse Correlated Equilibria in Sequential Games