Constructing Imperfect Recall Abstractions to Solve Large Extensive-Form Games
share
Extensive-form games are an important model of finite sequential interaction between players. The size of the extensive-form representation is, however, often prohibitive and it is the most common cause preventing deployment of game-theoretic solution concepts to real-world scenarios. The state-of-the-art approach to solve this issue is the information abstraction methodology. The majority of existing information abstraction approaches create abstracted games where players remember all their actions and all the information they obtained in the abstracted game -- a property denoted as a perfect recall. Remembering all the actions, however, causes the number of decision points of the player (and hence also the size of his strategy) to grow exponentially with the number of actions taken in the past. On the other hand, relaxing the perfect recall requirement (resulting in so-called imperfect recall abstractions) can significantly increase the computational complexity of solving the resulting abstracted game. In this work, we introduce two domain-independent algorithms FPIRA and CFR+IRA which are able to start with an arbitrary imperfect recall abstraction of the solved two-player zero-sum perfect recall extensive-form game. The algorithms simultaneously solve the abstracted game, detect the missing information causing problems and return it to the players. This process is repeated until provable convergence to the desired approximation of the Nash equilibrium of the original game. We experimentally demonstrate that even when the algorithms start with trivial coarse imperfect recall abstraction, they are capable of approximating Nash equilibrium of large games using abstraction with as little as 0.9
READ FULL TEXT