Regret Circuits: Composability of Regret Minimizers

Gabriele Farina, Christian Kroer, Tuomas Sandholm
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:1863-1872, 2019.

Abstract

Regret minimization is a powerful tool for solving large-scale problems; it was recently used in breakthrough results for large-scale extensive-form game solving. This was achieved by composing simplex regret minimizers into an overall regret-minimization framework for extensive-form game strategy spaces. In this paper we study the general composability of regret minimizers. We derive a calculus for constructing regret minimizers for composite convex sets that are obtained from convexity-preserving operations on simpler convex sets. We show that local regret minimizers for the simpler sets can be combined with additional regret minimizers into an aggregate regret minimizer for the composite set. As one application, we show that the CFR framework can be constructed easily from our framework. We also show ways to include curtailing (constraining) operations into our framework. For one, they enable the construction of CFR generalization for extensive-form games with general convex strategy constraints that can cut across decision points.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-farina19b, title = {Regret Circuits: Composability of Regret Minimizers}, author = {Farina, Gabriele and Kroer, Christian and Sandholm, Tuomas}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {1863--1872}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/farina19b/farina19b.pdf}, url = {https://proceedings.mlr.press/v97/farina19b.html}, abstract = {Regret minimization is a powerful tool for solving large-scale problems; it was recently used in breakthrough results for large-scale extensive-form game solving. This was achieved by composing simplex regret minimizers into an overall regret-minimization framework for extensive-form game strategy spaces. In this paper we study the general composability of regret minimizers. We derive a calculus for constructing regret minimizers for composite convex sets that are obtained from convexity-preserving operations on simpler convex sets. We show that local regret minimizers for the simpler sets can be combined with additional regret minimizers into an aggregate regret minimizer for the composite set. As one application, we show that the CFR framework can be constructed easily from our framework. We also show ways to include curtailing (constraining) operations into our framework. For one, they enable the construction of CFR generalization for extensive-form games with general convex strategy constraints that can cut across decision points.} }
Endnote
%0 Conference Paper %T Regret Circuits: Composability of Regret Minimizers %A Gabriele Farina %A Christian Kroer %A Tuomas Sandholm %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-farina19b %I PMLR %P 1863--1872 %U https://proceedings.mlr.press/v97/farina19b.html %V 97 %X Regret minimization is a powerful tool for solving large-scale problems; it was recently used in breakthrough results for large-scale extensive-form game solving. This was achieved by composing simplex regret minimizers into an overall regret-minimization framework for extensive-form game strategy spaces. In this paper we study the general composability of regret minimizers. We derive a calculus for constructing regret minimizers for composite convex sets that are obtained from convexity-preserving operations on simpler convex sets. We show that local regret minimizers for the simpler sets can be combined with additional regret minimizers into an aggregate regret minimizer for the composite set. As one application, we show that the CFR framework can be constructed easily from our framework. We also show ways to include curtailing (constraining) operations into our framework. For one, they enable the construction of CFR generalization for extensive-form games with general convex strategy constraints that can cut across decision points.
APA
Farina, G., Kroer, C. & Sandholm, T.. (2019). Regret Circuits: Composability of Regret Minimizers. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:1863-1872 Available from https://proceedings.mlr.press/v97/farina19b.html.

Related Material