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.
Cite
Text
Hartline et al. "No-Regret Learning in Bayesian Games." Neural Information Processing Systems, 2015.Markdown
[Hartline et al. "No-Regret Learning in Bayesian Games." Neural Information Processing Systems, 2015.](https://mlanthology.org/neurips/2015/hartline2015neurips-noregret/)BibTeX
@inproceedings{hartline2015neurips-noregret,
title = {{No-Regret Learning in Bayesian Games}},
author = {Hartline, Jason and Syrgkanis, Vasilis and Tardos, Eva},
booktitle = {Neural Information Processing Systems},
year = {2015},
pages = {3061-3069},
url = {https://mlanthology.org/neurips/2015/hartline2015neurips-noregret/}
}