Solving Games with Functional Regret Estimation

Kevin Waugh, Dustin Morrill, J. Andrew Bagnell, and Michael Bowling. Solving Games with Functional Regret Estimation. In Proceedings of the Twenty-Ninth Conference on Artificial Intelligence (AAAI), 2015. To Appear




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.


  Title = "Solving Games with Functional Regret Estimation",
  Author = "Kevin Waugh and Dustin Morrill and {J. Andrew} Bagnell and Michael Bowling",
  Booktitle = "Proceedings of the Twenty-Ninth Conference on Artificial Intelligence (AAAI)",
  Year = "2015",
  Note = "To Appear",
  AcceptRate = "27%",
  AcceptNumbers = "531 of 1991"

Generated by (written by Patrick Riley) on Fri Feb 13, 2015 15:54:26