Reduced Space and Faster Convergence in Imperfect-Information Games via Pruning

Noam Brown, Tuomas Sandholm
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:596-604, 2017.

Abstract

Iterative algorithms such as Counterfactual Regret Minimization (CFR) are the most popular way to solve large zero-sum imperfect-information games. In this paper we introduce Best-Response Pruning (BRP), an improvement to iterative algorithms such as CFR that allows poorly-performing actions to be temporarily pruned. We prove that when using CFR in zero-sum games, adding BRP will asymptotically prune any action that is not part of a best response to some Nash equilibrium. This leads to provably faster convergence and lower space requirements. Experiments show that BRP results in a factor of 7 reduction in space, and the reduction factor increases with game size.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-brown17a, title = {Reduced Space and Faster Convergence in Imperfect-Information Games via Pruning}, author = {Noam Brown and Tuomas Sandholm}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {596--604}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/brown17a/brown17a.pdf}, url = {https://proceedings.mlr.press/v70/brown17a.html}, abstract = {Iterative algorithms such as Counterfactual Regret Minimization (CFR) are the most popular way to solve large zero-sum imperfect-information games. In this paper we introduce Best-Response Pruning (BRP), an improvement to iterative algorithms such as CFR that allows poorly-performing actions to be temporarily pruned. We prove that when using CFR in zero-sum games, adding BRP will asymptotically prune any action that is not part of a best response to some Nash equilibrium. This leads to provably faster convergence and lower space requirements. Experiments show that BRP results in a factor of 7 reduction in space, and the reduction factor increases with game size.} }
Endnote
%0 Conference Paper %T Reduced Space and Faster Convergence in Imperfect-Information Games via Pruning %A Noam Brown %A Tuomas Sandholm %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-brown17a %I PMLR %P 596--604 %U https://proceedings.mlr.press/v70/brown17a.html %V 70 %X Iterative algorithms such as Counterfactual Regret Minimization (CFR) are the most popular way to solve large zero-sum imperfect-information games. In this paper we introduce Best-Response Pruning (BRP), an improvement to iterative algorithms such as CFR that allows poorly-performing actions to be temporarily pruned. We prove that when using CFR in zero-sum games, adding BRP will asymptotically prune any action that is not part of a best response to some Nash equilibrium. This leads to provably faster convergence and lower space requirements. Experiments show that BRP results in a factor of 7 reduction in space, and the reduction factor increases with game size.
APA
Brown, N. & Sandholm, T.. (2017). Reduced Space and Faster Convergence in Imperfect-Information Games via Pruning. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:596-604 Available from https://proceedings.mlr.press/v70/brown17a.html.

Related Material