What Game Are We Playing? End-to-end Learning in Normal and Extensive Form Games

What Game Are We Playing? End-to-end Learning in Normal and Extensive Form Games

Chun Kai Ling, Fei Fang, J. Zico Kolter

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 396-402. https://doi.org/10.24963/ijcai.2018/55

Although recent work in AI has made great progress in solving large, zero-sum, extensive-form games, the underlying assumption in most past work is that the parameters of the game itself are known to the agents.  This paper deals with the relatively under-explored but equally important "inverse" setting, where the parameters of the underlying game are not known to all agents, but must be learned through observations.  We propose a differentiable, end-to-end learning framework for addressing this task.  In particular, we consider a regularized version of the game, equivalent to a particular form of quantal response equilibrium, and develop 1) a primal-dual Newton method for finding such equilibrium points in both normal and extensive form games; and 2) a backpropagation method that lets us analytically compute gradients of all relevant game parameters through the solution itself.  This ultimately lets us learn the game by training in an end-to-end fashion, effectively by integrating a "differentiable game solver" into the loop of larger deep network architectures. We demonstrate the effectiveness of the learning method in several settings including poker and security game tasks.
Keywords:
Agent-based and Multi-agent Systems: Noncooperative Games
Machine Learning: Deep Learning
Agent-based and Multi-agent Systems: Algorithmic Game Theory