We present a novel approach for identifying approximate role-symmetric Nash equilibria in large simulation-based games. Our method uses neural networks to learn a mapping from mixed-strategy profiles to deviation payoffs-the expected values of playing pure-strategy deviations from those profiles. This learning can generalize from data about a tiny fraction of a game's outcomes, permitting tractable analysis of exponentially large normal-form games. We give a procedure for iteratively refining the learned model with new data produced by sampling in the neighborhood of each candidate Nash equilibrium. Relative to the existing state of the art, deviation payoff learning dramatically simplifies the task of computing equilibria and more effectively addresses player asymmetries. We demonstrate empirically that deviation payoff learning identifies better approximate equilibria than previous methods and can handle more difficult settings, including games with many more players, strategies, and roles. Simultaneous-move games are among the most general tools for reasoning about incentives in multi-agent systems. The standard mathematical representation of a simultaneousmove game is the normal-form payoff matrix. It describes incentives in a multi-agent system by listing the strategies available to each agent and storing, for every combination of strategies the agents may jointly select, the resulting utility for each agent. This tabular representation grows exponentially: the payoff matrix for a normal form game with n players and m strategies per player stores utilities for each of m n pure-strategy profiles. As a result, explicit normal-form representations are typically employed only for games with a very small number of players and strategies. To study larger games, it is common to replace the explicit payoff table with a more compact representation of the utility function, from which payoff values can be computed on demand. However, pure-strategy utility functions are generally not sufficient for computing Nash equilibria. Instead, Nash-finding algorithms typically depend on one or more of the following quantities being efficiently computable: best responses to profiles of mixed strategies, deviation payoffs of mixed-strategy profiles (the expected utility of deviating to a pure-strategy, holding other agents' mixed strategies fixed), This means that analyzing large games typically requires carefully selecting a compact representation of the utility function that supports efficient computation of mixedstrategy deviation payoffs. For certain classes, like actiongraph games (Jiang, Leyton-Brown, and Bhat 2011), these representations are known, but in other cases, no such representation is available. Moreover, identifying such a compact structure can be challenging, even when it does exist. In this paper, we explore a machine learning approach to efficiently approximating deviation payoffs and their derivatives, under the hypothesis that sufficiently close approximation of these quantities will tend to yield -Nash equilibria. At the core of the approach is the idea that the expected payoffs of a mixed-strategy profile can be estimated by the payoffs of pure-strategy profiles sampled from that mixed-strategy profile. Such sampling is extremely noisy, but by sampling from many different mixed-strategy profiles and employing machine learning algorithms that generalize across related mixed strategies, we can estimate a deviation payoff function for the entire game. Our methods are applicable in settings where a specific compact structure is not known in advance, but where payoff estimates for arbitrary pure-strategy profiles can be acquired. This setting is common in simulation-based games ) and other multi-agent reinforcement learning settings including sequential social dilemmas (Leibo et al. 2017 ). Many of these applications can involve large numbers of symmetric players and would benefit from analysis that scales efficiently and accurately by leveraging these symmetries. Much recent progress in game-theoretic settings has been achieved by the application of machine learning to large extensive-form games. In Go and poker, the extensive form is well-defined, but is far too big to be constructed explicitly, so high-level play Moravčík et al. 2017) and approximate equilibrium analysis (Heinrich, Lanctot, and Silver 2015) have required the aid of machine learning based algorithms. These algorithms run simulations to estimate payoffs for various game states and use learning to generalize to unexplored parts of the game tree. Our work employs a similar approach, generating observations by simulation and making generalizations by machine learning only in the context of normal-form deviation payoffs, instead of extensive-form state or state-action values. In the context of simultaneous-move games, a variety of game models more compact than the normal-form payoff matrix have been explored. Graphical games (Kearns 2007) exploit independence among players, action-graph games (Jiang, Leyton-Brown, and Bhat 2011) exploit independence or partial independence among strategies, and resourcegraph games (Jiang, Chan, and Leyton-Brown 2017) exploit independence among sub-decisions that comprise strategies. All of these models can, in particular contexts, exponentially reduce the size of the game representation. But they all require detailed knowledge of a game's structure, which is unlikely to be available in the setting of simulation-based games. When a precise compact model is not known in advance, it may still be possible to induce the parameters of such a model from simulated or observed data. Duong et al. (2009) construct graphical games from payoff data, and Honorio and Ortiz (2015) construct linear influence games from behavioral data. An advantage of these approaches is that the resulting models can offer structural insight that may generalize to other related settings. However, they suffer from significant limitations in that only the specifically targeted type of structure can be learned. So these approaches are only useful when the analyst has advance knowledge of the payoff structure. In contrast, deviation payoff learning is agnostic to the detailed structure of the payoff functions, making it applicable to a far wider variety of simulation-based games. We are aware of two papers that have addressed the problem of learning generic models of simultaneous-move games from simulation-based data. The first learns payoff functions that generalize over continuous strategy spaces (Vorobeychik, Wellman, and Singh 2007) . The regression takes as input a single-parameter description of a player's strategy and a single-parameter summary of the profile of opponent strategies and outputs a utility. For all but the simplest regression methods, equilibrium computation requires using the learned functions to fill in a payoff matrix for a discretization of the strategy space. This matrix grows exponentially with the number of players, prohibiting analysis of large games with complex payoff functions. Closest to the present work, Wiedenbeck, Yang, and Wellman (2018) learn payoff functions of symmetric games. For each strategy, a regressor takes as input a pure-strategy opponent-profile and outputs a utility. They provide an approximation method for deviation payoffs that allows for computation of role-symmetric -Nash equilibria. This approach can learn complicated payoff functions and scales well in the number of players. However, the approximation method, which is only valid for fully-symmetric games learned via RBF kernel Gaussian process regression, is prohibitively expensive, and thereby limited to small data sets from games with small numbers of pure strategies. We compare against this method in our experiments and demonstrate favorable results for deviation-payoff learning.
Subsequently, Sokota et al. REF provide an advancement over the previous work, using neural networks to approximate the utility function (instead of GPs) and providing a way to guide sampling so as to focus it on the neighborhood of candidate equilibrium points.
Learning Deviation Payoffs in Simulation-Based Games
AAAI
Computer Science