Multiplicative Weights Updates with Constant Step-Size in Graphical Constant-Sum Games
Abstract
Since Multiplicative Weights (MW) updates are the discrete analogue of the continuous Replicator Dynamics (RD), some researchers had expected their qualitative behaviours would be similar. We show that this is false in the context of graphical constant-sum games, which include two-person zero-sum games as special cases. In such games which have a fully-mixed Nash Equilibrium (NE), it was known that RD satisfy the permanence and Poincare recurrence properties, but we show that MW updates with any constant step-size eps > 0 converge to the boundary of the state space, and thus do not satisfy the two properties. Using this result, we show that MW updates have a regret lower bound of Omega( 1 / (eps T) ), while it was known that the regret of RD is upper bounded by O( 1 / T ).
BibTeX
@inproceedings{NEURIPS2018_90e13578,
author = {Cheung, Yun Kuen},
booktitle = {Advances in Neural Information Processing Systems},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Multiplicative Weights Updates with Constant Step-Size in Graphical Constant-Sum Games},
url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/90e1357833654983612fb05e3ec9148c-Paper.pdf},
volume = {31},
year = {2018}
}