text: To achieve general intelligence, agents must learn how to interact with others in a shared environment: this is the challenge of multiagent reinforcement learning (MARL). The simplest form is independent reinforcement learning (InRL), where each agent treats its experience as part of its (non-stationary) environment. In this paper, we first observe that policies learned using InRL can overfit to the other agents' policies during training, failing to sufficiently generalize during execution. We introduce a new metric, joint-policy correlation, to quantify this effect. We describe an algorithm for general MARL, based on approximate best responses to mixtures of policies generated using deep reinforcement learning, and empirical game-theoretic analysis to compute meta-strategies for policy selection. The algorithm generalizes previous ones such as InRL, iterated best response, double oracle, and fictitious play. Then, we present a scalable implementation which reduces the memory requirement using decoupled meta-solvers. Finally, we demonstrate the generality of the resulting policies in two partially observable settings: gridworld coordination games and poker.
  @cite_35: Fictitious play is a popular game-theoretic model of learning in games. However, it has received little attention in practical applications to large problems. This paper introduces two variants of fictitious play that are implemented in behavioural strategies of an extensive-form game. The first variant is a full-width process that is realization equivalent to its normal-form counterpart and therefore inherits its convergence guarantees. However, its computational requirements are linear in time and space rather than exponential. The second variant, Fictitious Self-Play, is a machine learning framework that implements fictitious play in a sample-based fashion. Experiments in imperfect-information poker games compare our approaches and demonstrate their convergence to approximate Nash equilibria.
  @cite_41: 
  @cite_85: We consider a class of matrix games in which successful strategies are rewarded by high reproductive rates, so become more likely to participate in subsequent playings of the game. Thus, over time, the strategy mix should evolve to some type of optimal or stable state. Maynard Smith and Price (1973) have introduced the concept of ESS (evolutionarily stable strategy) to describe a stable state of the game. We attempt to model the dynamics of the game both in the continuous case, with a system of non-linear first-order differential equations, and in the discrete case, with a system of non-linear difference equations. Using this model, we look at the notions of stability and asymptotic behavior. Our notion of stable equilibrium for the continuous dynamic includes, but is somewhat more general than, the notion of ESS.
  @cite_1: In two-player zero-sum games, if both players minimize their average external regret, then the average of the strategy profiles converges to a Nash equilibrium. For n-player general-sum games, however, theoretical guarantees for regret minimization are less understood. Nonetheless, Counterfactual Regret Minimization (CFR), a popular regret minimization algorithm for extensive-form games, has generated winning three-player Texas Hold'em agents in the Annual Computer Poker Competition (ACPC). In this paper, we provide the first set of theoretical properties for regret minimization algorithms in non-zero-sum games by proving that solutions eliminate iterative strict domination. We formally define in extensive-form games, show that CFR avoids iteratively strictly dominated actions and strategies, and demonstrate that removing iteratively dominated actions is enough to win a mock tournament in a small poker game. In addition, for two-player non-zero-sum games, we bound the worst case performance and show that in practice, regret minimization can yield strategies very close to equilibrium. Our theoretical advancements lead us to a new modification of CFR for games with more than two players that is more efficient and may be used to generate stronger strategies than previously possible. Furthermore, we present a new three-player Texas Hold'em poker agent that was built using CFR and a novel game decomposition method. Our new agent wins the three-player events of the 2012 ACPC and defeats the winning three-player programs from previous competitions while requiring less resources to generate than the 2011 winner. Finally, we show that our CFR modification computes a strategy of equal quality to our new agent in a quarter of the time of standard CFR using half the memory.
  @cite_32: Replicator dynamics model the interactions and change in large populations of agents. Standard replicator dynamics, however, only allow single action interactions between agents. Complex interactions, as modeled by general extensive games, have received comparatively little attention in this setting. Recently, replicator dynamics have been adapted to extensive-form games represented in sequence form, leading to a large reduction in computational resource requirements. In this paper, we first show that sequence-form constraints and realization equivalence to standard replicator dynamics are maintained in general n-player games. We show that sequence-form replicator dynamics can minimize regret, leading to equilibrium convergence guarantees in two-player zero-sum games. We provide the first empirical evaluation of sequence-form replicator dynamics, applied to n-player Kuhn poker with two, three, and four players. Our results show that the average strategies generated by sequence-form replicator dynamics produce approximate equilibrium strategies with increasing accuracy over time.
  @cite_81: 
  @cite_34: Extensive games are a powerful model of multiagent decision-making scenarios with incomplete information. Finding a Nash equilibrium for very large instances of these games has received a great deal of recent attention. In this paper, we describe a new technique for solving large games based on regret minimization. In particular, we introduce the notion of counterfactual regret, which exploits the degree of incomplete information in an extensive game. We show how minimizing counterfactual regret minimizes overall regret, and therefore in self-play can be used to compute a Nash equilibrium. We demonstrate this technique in the domain of poker, showing we can solve abstractions of limit Texas Hold'em with as many as 1012 states, two orders of magnitude larger than previous methods.
  @cite_20: 
summary: There are several algorithms for computing strategies. In zero-sum games (where @math , one can use e.g. linear programming, fictitious play @cite_20 , replicator dynamics @cite_85 , or regret minimization @cite_81 . Some of these techniques have been extended to extensive (sequential) form @cite_35 @cite_41 @cite_32 @cite_34 with an exponential increase in the size of the state space. However, these extensions have almost exclusively treated the two-player case, with some notable exceptions @cite_32 @cite_1 . Fictitious play also converges in potential games which includes cooperative (identical payoff) games.