Tuesday, January 19, 2016. 12:00PM. NSH 3305.
Noam Brown - Simultaneous Abstraction and Equilibrium Finding
The leading approach for solving large games of imperfect information is to find a Nash equilibrium in a smaller, abstract version of the game and then map the solution back to the original game. However, it is difficult to know what information and which actions to discard or include in the abstraction without first solving the game, and it is infeasible to solve the game without first abstracting it. We introduce a method that combines abstraction with equilibrium finding by enabling the abstraction to change during run time. This allows an agent to begin learning with a coarse abstraction, and then to strategically refine the abstraction at points that the strategy computed in the current abstraction deems important. The algorithm can switch to the refined abstraction at the cost of a single traversal while provably not having to restart the equilibrium finding. Experiments show it can outperform fixed abstractions at every stage of the run: early on it improves as quickly as equilibrium finding in coarse abstractions, and later it converges to a better solution than does equilibrium finding in fine-grained abstractions.