Solving Games with Functional Regret Estimation

January 2015

Solving Games with Functional Regret Estimation

Authors:

Kevin Waugh, Dustin Morrill, J. Andrew (Drew) Bagnell, and Michael Bowling

Abstract:

We propose a novel online learning method for minimizing regret in large extensive-form games. The approach learns a function approximator online to estimate the regret for choosing a particular action. A no-regret algorithm uses these estimates in place of the true regrets to define a sequence of policies. We prove the approach sound by providing a bound relating the quality of the function approximation and regret of the algorithm. A corollary being that the method is guaranteed to converge to a Nash equilibrium in self-play so long as the regrets are ultimately realizable by the function approximator. Our technique can be understood as a principled generalization of existing work on abstraction in large games; in our work, both the abstraction as well as the equilibrium are learned during self-play. We demonstrate empirically the method achieves higher quality strategies than state-of-the-art abstraction techniques given the same resources.
@conference{Waugh-2015-17187,
author = {Kevin Waugh And Dustin Morrill And J. Andrew (Drew) Bagnell And Michael Bowling},
title = {Solving Games with Functional Regret Estimation},
booktitle = {Proceedings of 29th AAAI Conference on Artificial Intelligence (AAAI '15)},
year = {2015},
month = {January},
pages = {2138 - 2144},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.