SPEAKER: Andrew Gilpin
TIME: Wednesday 12-1pm, February 28, 2007
PLACE: NSH 1507
TITLE: Nesterov’s excessive gap technique and poker
ABSTRACT:
For the generic convex optimization problem of minimizing a (non-smooth) convex function f(x) over a convex domain D, any subgradient method requires O(1/epsilon^2) iterations for obtaining an epsilon-solution. However, this analysis is based on a black-box oracle access model for f and D. Recently, Nesterov developed the excessive gap technique which yields an algorithm needing only O(1/epsilon) iterations to obtain an epsilon-solution in certain problems having a non-smooth convex objective with a certain max-like structure.
In this talk I will present the general theory behind Nesterov’s excessive gap technique, and I will describe how we extended the basic framework to handle the problem of computing approximate Nash equilibria in two-person zero-sum sequential games of imperfect information. Also, I will discuss some additional heuristics we developed which yield even faster convergence in practice.
Finally, I will describe how we used this algorithm (along with our recent advances in automated abstraction for sequential games of imperfect information) to develop an extremely competitive heads-up Texas Hold’em poker player.
This talk describes joint work with Samid Hoda, Javier Pena, Tuomas Sandholm, and Troels Sorensen.
