Revisiting Game Representations: The Hidden Costs of Efficiency in Sequential Decision-making Algorithms
This work highlights a potential bias in evaluating algorithms for imperfect-information games, which could impact researchers and practitioners in AI and game theory by revealing hidden costs in efficiency.
The paper identifies that modern sequential decision-making algorithms are often benchmarked on games naturally represented as Sequential Bayesian Games, which is a restricted class, and argues that their impressive results may be skewed due to this limitation, aiming to guide future research toward more universally applicable algorithms.
Recent advancements in algorithms for sequential decision-making under imperfect information have shown remarkable success in large games such as limit- and no-limit poker. These algorithms traditionally formalize the games using the extensive-form game formalism, which, as we show, while theoretically sound, is memory-inefficient and computationally intensive in practice. To mitigate these challenges, a popular workaround involves using a specialized representation based on player specific information-state trees. However, as we show, this alternative significantly narrows the set of games that can be represented efficiently. In this study, we identify the set of large games on which modern algorithms have been benchmarked as being naturally represented by Sequential Bayesian Games. We elucidate the critical differences between extensive-form game and sequential Bayesian game representations, both theoretically and empirically. We further argue that the impressive experimental results often cited in the literature may be skewed, as they frequently stem from testing these algorithms only on this restricted class of games. By understanding these nuances, we aim to guide future research in developing more universally applicable and efficient algorithms for sequential decision-making under imperfect information.