No-Regret Learning in Bayesian Games
Jason Hartline, Vasilis Syrgkanis, Eva Tardos
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.
BibTeX
@inproceedings{NIPS2015_3e7e0224,
author = {Hartline, Jason and Syrgkanis, Vasilis and Tardos, Eva},
booktitle = {Advances in Neural Information Processing Systems},
editor = {C. Cortes and N. Lawrence and D. Lee and M. Sugiyama and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {No-Regret Learning in Bayesian Games},
url = {https://proceedings.neurips.cc/paper_files/paper/2015/file/3e7e0224018ab3cf51abb96464d518cd-Paper.pdf},
volume = {28},
year = {2015}
}