Last Round Convergence and No-Dynamic Regret in Asymmetric Repeated Games

Le Cong Dinh, Tri-Dung Nguyen, Alain B. Zemhoho, Long Tran-Thanh
Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:553-577, 2021.

Abstract

This paper considers repeated games in which one player has a different objective than others. In particular, we investigate repeated two-player zero-sum games where the column player not only aims to minimize her regret but also stabilize the actions. Suppose that while repeatedly playing this game, the row player chooses her strategy at each round by using a no-regret algorithm to minimize her regret. We develop a no-dynamic regret algorithm for the column player to exhibit last round convergence to a minimax equilibrium. We show that our algorithm is efficient against a large set of popular no-regret algorithms the row player can use, including the multiplicative weights update algorithm, general follow-the-regularized-leader and any no-regret algorithms satisfy a property so called “stability”.

Cite this Paper

BibTeX
@InProceedings{pmlr-v132-dinh21a, title = {Last Round Convergence and No-Dynamic Regret in Asymmetric Repeated Games}, author = {Dinh, Le Cong and Nguyen, Tri-Dung and Zemhoho, Alain B. and Tran-Thanh, Long}, booktitle = {Proceedings of the 32nd International Conference on Algorithmic Learning Theory}, pages = {553--577}, year = {2021}, editor = {Feldman, Vitaly and Ligett, Katrina and Sabato, Sivan}, volume = {132}, series = {Proceedings of Machine Learning Research}, month = {16--19 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v132/dinh21a/dinh21a.pdf}, url = {https://proceedings.mlr.press/v132/dinh21a.html}, abstract = {This paper considers repeated games in which one player has a different objective than others. In particular, we investigate repeated two-player zero-sum games where the column player not only aims to minimize her regret but also stabilize the actions. Suppose that while repeatedly playing this game, the row player chooses her strategy at each round by using a no-regret algorithm to minimize her regret. We develop a no-dynamic regret algorithm for the column player to exhibit last round convergence to a minimax equilibrium. We show that our algorithm is efficient against a large set of popular no-regret algorithms the row player can use, including the multiplicative weights update algorithm, general follow-the-regularized-leader and any no-regret algorithms satisfy a property so called “stability”.} }
Endnote
%0 Conference Paper %T Last Round Convergence and No-Dynamic Regret in Asymmetric Repeated Games %A Le Cong Dinh %A Tri-Dung Nguyen %A Alain B. Zemhoho %A Long Tran-Thanh %B Proceedings of the 32nd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Vitaly Feldman %E Katrina Ligett %E Sivan Sabato %F pmlr-v132-dinh21a %I PMLR %P 553--577 %U https://proceedings.mlr.press/v132/dinh21a.html %V 132 %X This paper considers repeated games in which one player has a different objective than others. In particular, we investigate repeated two-player zero-sum games where the column player not only aims to minimize her regret but also stabilize the actions. Suppose that while repeatedly playing this game, the row player chooses her strategy at each round by using a no-regret algorithm to minimize her regret. We develop a no-dynamic regret algorithm for the column player to exhibit last round convergence to a minimax equilibrium. We show that our algorithm is efficient against a large set of popular no-regret algorithms the row player can use, including the multiplicative weights update algorithm, general follow-the-regularized-leader and any no-regret algorithms satisfy a property so called “stability”.
APA
Dinh, L.C., Nguyen, T., Zemhoho, A.B. & Tran-Thanh, L.. (2021). Last Round Convergence and No-Dynamic Regret in Asymmetric Repeated Games. Proceedings of the 32nd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 132:553-577 Available from https://proceedings.mlr.press/v132/dinh21a.html.

Related Material