Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games

Dustin Morrill, Ryan D’Orazio, Marc Lanctot, James R Wright, Michael Bowling, Amy R Greenwald
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:7818-7828, 2021.

Abstract

Hindsight rationality is an approach to playing general-sum games that prescribes no-regret learning dynamics for individual agents with respect to a set of deviations, and further describes jointly rational behavior among multiple agents with mediated equilibria. To develop hindsight rational learning in sequential decision-making settings, we formalize behavioral deviations as a general class of deviations that respect the structure of extensive-form games. Integrating the idea of time selection into counterfactual regret minimization (CFR), we introduce the extensive-form regret minimization (EFR) algorithm that achieves hindsight rationality for any given set of behavioral deviations with computation that scales closely with the complexity of the set. We identify behavioral deviation subsets, the partial sequence deviation types, that subsume previously studied types and lead to efficient EFR instances in games with moderate lengths. In addition, we present a thorough empirical analysis of EFR instantiated with different deviation types in benchmark games, where we find that stronger types typically induce better performance.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-morrill21a, title = {Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games}, author = {Morrill, Dustin and D'Orazio, Ryan and Lanctot, Marc and Wright, James R and Bowling, Michael and Greenwald, Amy R}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {7818--7828}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/morrill21a/morrill21a.pdf}, url = {https://proceedings.mlr.press/v139/morrill21a.html}, abstract = {Hindsight rationality is an approach to playing general-sum games that prescribes no-regret learning dynamics for individual agents with respect to a set of deviations, and further describes jointly rational behavior among multiple agents with mediated equilibria. To develop hindsight rational learning in sequential decision-making settings, we formalize behavioral deviations as a general class of deviations that respect the structure of extensive-form games. Integrating the idea of time selection into counterfactual regret minimization (CFR), we introduce the extensive-form regret minimization (EFR) algorithm that achieves hindsight rationality for any given set of behavioral deviations with computation that scales closely with the complexity of the set. We identify behavioral deviation subsets, the partial sequence deviation types, that subsume previously studied types and lead to efficient EFR instances in games with moderate lengths. In addition, we present a thorough empirical analysis of EFR instantiated with different deviation types in benchmark games, where we find that stronger types typically induce better performance.} }
Endnote
%0 Conference Paper %T Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games %A Dustin Morrill %A Ryan D’Orazio %A Marc Lanctot %A James R Wright %A Michael Bowling %A Amy R Greenwald %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-morrill21a %I PMLR %P 7818--7828 %U https://proceedings.mlr.press/v139/morrill21a.html %V 139 %X Hindsight rationality is an approach to playing general-sum games that prescribes no-regret learning dynamics for individual agents with respect to a set of deviations, and further describes jointly rational behavior among multiple agents with mediated equilibria. To develop hindsight rational learning in sequential decision-making settings, we formalize behavioral deviations as a general class of deviations that respect the structure of extensive-form games. Integrating the idea of time selection into counterfactual regret minimization (CFR), we introduce the extensive-form regret minimization (EFR) algorithm that achieves hindsight rationality for any given set of behavioral deviations with computation that scales closely with the complexity of the set. We identify behavioral deviation subsets, the partial sequence deviation types, that subsume previously studied types and lead to efficient EFR instances in games with moderate lengths. In addition, we present a thorough empirical analysis of EFR instantiated with different deviation types in benchmark games, where we find that stronger types typically induce better performance.
APA
Morrill, D., D’Orazio, R., Lanctot, M., Wright, J.R., Bowling, M. & Greenwald, A.R.. (2021). Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:7818-7828 Available from https://proceedings.mlr.press/v139/morrill21a.html.

Related Material