Decentralized No-regret Learning Algorithms for Extensive-form Correlated Equilibria (Extended Abstract)

1 Motivation

This work studies decision-making problems in which rational individuals interact with a centralized planner. The centralized planner cannot directly tell the individuals what to do, but the goal of the centralized planner is to steer the individuals' behaviors to mutually beneficial outcomes. There are many real-world problems where we observe this type of interaction, and this is increasingly common in the gig economy we all live in today. Think, for example, of ride-sharing or food delivery platforms, where drivers provide services to customers, and the whole market is centralized through a single app that every agent connects to.

Because the individual decision makers in the system have free will, the central planner has to take into consideration the fact that all of the individual decision makers will act selfishly according to their objectives. Therefore, to get them to behave in a certain way, the central planner must nudge them using the right incentives. This type of soft coordination is already enough to steer the system to social welfare that would be largely impossible in absence of a central planner, so without any form of coordination between the decision makers.

The strategy that the central planner should follow when interacting with decision makers is called a correlated equilibrium in the game theory literature. The key feature of a correlated equilibrium is that all the decision makers receive the right incentives to follow the planner's recommendations. This means that no agent would want to do something different from what they are recommended to do by the central planner. The study of this type of equilibrium goes back to the seminal work on correlated equilibrium by Robert Aumann in 1974 [Aumann, 1974], who was later awarded a Nobel prize in economics for his work on game-theoretic cooperation.

Since then, there has been much effort in scaling up the computation of correlated equilibria and designing algorithms guaranteeing some key properties. In particular, a crucial property that algorithms for computing correlated equilibria should satisfy is decentralization. This essentially means that the behavior and incentives of each agent should be computed independently from the other agents. The decentralization is fundamental for the computation to scale well, and it allows the agents to converge to an equilibrium point without the need for a central planner. Furthermore, decentralization preserves the agents' privacy during the learning process. Indeed, agents should not need to report their true personal preferences back to the central planner or to other decision makers. We also remark that decentralization makes the algorithm robust, since it does not rely on a single point-of-failure. A landmark result by Hart and Mas-Colell in 2000 [Hart and Mas-Colell, 2000] showed that correlated equilibria can be found in such a decentralized way by letting all agents behave independently, according to a simple learning rule.

Unfortunately, the work by Hart and Mas-Colell only applies to one-shot interactions, in which each agent is supposed to interact only once with the system. Agents are not allowed to adjust their behavior based on their observations because they are assumed to act simultaneously, as if it was a rockpaper-scissor kind of interaction. Extending their decentralized approach to the general case where agents act more than once and can adjust their behavior to their observations has been an open question since then. In our work, we close this open problem. This result may foster future applications of game-theoretic solution concepts to real-world decision making, providing ways for individuals to solve hard coordination tasks while pursuing their self-interest.

2 Games, Equilibria, and Learning Dynamics

The Nash equilibrium (NE) [Nash, 1950] is the most common notion of rationality in game theory, and its computation in two-player zero-sum games has been the flagship computational challenge in the area at the interplay between computer science and game theory (see, e.g., the landmark results in heads-up no-limit poker, namely [Brown and Sandholm, 2018] and [Moravˇc´ık et al., 2017]). The assumption underpinning NE is that the interaction among players is fully decentralized. Therefore, an NE is an element of the uncorrelated strategy space of the game, that is, a product of independent probability distributions over actions, one per player. A competing notion of rationality is the correlated equilibrium (CE) proposed by [Aumann, 1974]. A CE is defined as a probability distribution over joint action profiles-specifying an action for each player-and it is customarily modeled via a trusted external mediator that draws an action profile from this distribution, and privately recommends to each player their component. Such probability distribution is a CE if no player has an incentive to choose an action different from the mediator's recommendation, because, assuming that all other players follow their recommended action, the suggested action is the best in expectation.

Many real-world strategic interactions involve more than two players with arbitrary (i.e., general-sum) utilities. In those settings, the CE is an appealing solution concept, as it overcomes several weaknesses of the NE. First, the NE is prone to equilibrium selection issues, raising the question as to how players can select an equilibrium while they are assumed not to be able to communicate with each other. Second, computing an NE is computationally intractable, being PPAD-complete even in two-player games [Chen and Deng, 2006; Daskalakis et al., 2009], whereas a CE can be computed in polynomial time. 1 Third, the social welfare that can be attained via an NE may be arbitrarily lower than what can be achieved via a CE [Koutsoupias and Papadimitriou, 1999; Roughgarden and Tardos, 2002; Celli and Gatti, 2018]. Lastly, in normal-form (that is, simultaneousmove) games, the notion of CE arises from simple uncoupled learning dynamics even in general-sum settings with an arbitrary number of players. In words, these learning dynamics are such that each player adjusts their strategy on the basis of their own payoff function, and on other players' strategies, but not on the payoff functions of other players. The existence of uncoupled dynamics enables to overcome the-often unreasonable-assumption that players have perfect knowledge of other players' objectives, while at the same time offering a parallel, scalable avenue for finding equilibria. In contrast, in the case of the NE, uncoupled learning dynamics are only known for the two-player zero-sum setting [Hart and Mas-Colell, 2000; Hart and Mas-Colell, 2003; Cesa-Bianchi and Lugosi, 2006]. The above considerations suggest that CE is oftentimes a better prescriptive solution concept than NE in general-sum and multiplayer settings.

1 In normal-form games, a CE can be computed in polynomial time via linear programming. In extensive-form games, the com-

Extensive-form correlated equilibrium (EFCE), introduced by [von Stengel and Forges, 2008], is a natural extension of the correlated equilibrium to the case of extensive-form (that is, sequential) games. Extensive-form games generalize normal-form games by modeling both sequential and simultaneous moves, as well as imperfect information. In an EFCE, the mediator draws, before the beginning of the sequential interaction, a recommended action for each of the possible decision points (also known as, information sets) that players may encounter in the game, but these recommendations are not immediately revealed to each player. Instead, the mediator incrementally reveals relevant individual moves as players reach new information sets. At any decision point, the acting player is free to deviate from the recommended action, but doing so comes at the cost of future recommendations, which are no longer issued to that player if they deviate. It is up to the mediator to make sure that the recommended behavior is indeed an equilibrium-that is, that no player would be better off ever deviating from following the mediator's recommendations at each information set. Compared to the constraints that characterize the set of CEs in normal-form games, those that define the set of EFCEs in extensive-form games are significantly more complex. Indeed, the main challenge of the EFCE case is that the mediator must take into account the evolution of beliefs of each player as they make observations throughout the game tree.

In general-sum extensive-form games with an arbitrary number of players (including potentially the chance player modeling exogenous stochastic events), the problem of computing a feasible EFCE can be solved in polynomial time in the size of the game tree [Huang and von Stengel, 2008] via a variation of the Ellipsoid Against Hope algorithm [Papadimitriou and Roughgarden, 2008; Jiang and Leyton-Brown, 2015]. [Dud´ık and Gordon, 2009] provide an alternative sampling-based algorithm to compute EFCEs. However, their algorithm is centralized and based on MCMC sampling, which limits its applicability on large-scale problems. In practice, these approaches cannot scale beyond toy problems. On the other hand, methods based on uncoupled learning dynamics usually work quite well in large real-world problems, while retaining the appealing properties of uncoupled dynamics that we discussed above.

putational complexity of computing a CE depends on the specific notion of correlation that is adopted. The problem can be solved in polynomial time for the notion studied in this article.

3 Summary of the Contributions

We focus on the following fundamental research question: is it possible to devise uncoupled learning dynamics that converge to an EFCE? We show that the answer is positive.

In the first part of [Celli et al., 2020], we formalize the notion of trigger regret, simplifying and extending an idea by [Gordon et al., 2008]. Trigger regret is a notion of regret suitable for extensive-form games that naturally expresses the regret incurred by each player for following the recommendations issued by the EFCE mediator, instead of deviating according to some optimal-in-hindsight strategy. Specifically, trigger regret is a particular instantiation of the framework known as phi-regret minimization introduced by [Stoltz and Lugosi, 2007] building on previous work by [Greenwald and Jafari, 2003]. In general, phi-regret minimization operates with a notion of regret defined with respect to a given set of linear transformations on the decision set. In order to define trigger regret, we identify suitable linear transformations that allow us to encode the behavior of trigger agents in the definition of EFCE, which we coin canonical trigger deviation functions. Intuitively, canonical trigger deviation functions encode all the possible ways in which a trigger agent may deviate from the recommendations issued by the EFCE mediator, and instead start playing from that point on according to a different strategy than the recommended one. Our core result on trigger regret is the the following: if each player plays according to a no-trigger-regret learning algorithm, then the empirical frequency of play approaches the set of EFCEs.

In the rest of [Celli et al., 2020], we provide an efficient (that is, requiring time polynomial in the size of the game tree at each iteration) algorithm that minimizes trigger regret. The algorithm is based on the general template for constructing phi-regret minimization algorithms given by [Gordon et al., 2008], extending prior work by [Hazan and Kale, 2008]. Before one can use that template, two missing pieces need to be solved:

1. constructing an efficient regret minimizer for the set of all valid canonical trigger deviation functions, and
2. showing that any convex combination of canonical trigger deviation functions admits a fixed point strategy, and that such fixed point can be computed efficiently.

We solve the first point by exploiting the non-trivial combinatorial structures of the set of canonical trigger deviation functions, and the second point by giving an efficient incremental procedure to compute the fixed point strategy in a top-down traversal of the game tree. Our resulting algorithm minimizes trigger regret, guaranteeing O(√T) trigger regret with high probability after T iterations and requiring time polynomial in the size of the game tree at each iteration. Thus, when all players play according to the uncoupled learning dynamics defined by our algorithm, the empirical frequency of play after T game repetitions is proven to be a O(1/√T)- approximate EFCE with high probability, and an EFCE almost surely in the limit. These results generalize the seminal work by [Hart and Mas-Colell, 2000] to the extensive-form game case via a simple and natural framework.

4 RelatedWorks

The study of adaptive procedures leading to a CE dates back to at least the seminal works by [Foster and Vohra, 1997], [Fudenberg and Levine, 1995; Fudenberg and Levine, 1999], and [Hart and Mas-Colell, 2000; Hart and Mas-Colell, 2001]; see also the monograph by [Fudenberg and Levine, 1998]. In particular, the work by [Hart and Mas-Colell, 2000] proves that simple dynamics based on the notion of internal regret converge to a CE in normal-form games. The strategy that the authors introduce-the so-called regret matching-is conceptually simple, and guarantees that if all players follow this strategy, then the empirical frequency of play converges to the set of CEs (see also [Cahn, 2004]). Other works describe extensions to the models studied in the aforementioned papers. For example, [Stoltz and Lugosi, 2007] describe an adaptive procedure converging to a CE in games with an infinite, but compact, set of actions, while [Kakade et al., 2003] consider efficient algorithms for computing correlated equilibria in graphical games.

In more recent years, a growing effort has been devoted to understanding the relationships between no-regret learning dynamics and equilibria in extensive-form games. These games pose additional challenges when compared to normalform games, due to their sequential nature and the presence of imperfect information. While in two-player zerosum extensive-form games it is widely known that no-regret learning dynamics converge to an NE-with the counterfactual regret minimization (CFR) algorithm and its variations being the state of the art for equilibrium finding in such games [Zinkevich et al., 2008; Tammelin, 2014; Tammelin et al., 2015; Lanctot et al., 2009; Brown and Sandholm, 2019]-the general case is less understood. [Celli et al., 2019] provide some variations of the classical CFR algorithm for n-player general-sum extensive-form games, showing that they provably converge to a normal-form coarse correlated equilibrium, which is based on a form of correlation that is less appealing than that of EFCE in sequential games.

Finally, we mention relevant literature subsequent to the conference version of this article. In a recent paper, [Morrill et al., 2020] conduct a study of different forms of correlation in extensive-form games, defining a taxonomy of solution concepts. Each of their solution concepts is attained by a particular set of no-regret learning dynamics, which is obtained by instantiating the phi-regret minimization framework [Greenwald and Jafari, 2003; Stoltz and Lugosi, 2007; Gordon et al., 2008] with a suitably-defined deviation function. As part of their analysis, [Morrill et al., 2020] investigate some properties of the well-established CFR regret minimization algorithm [Zinkevich et al., 2008] applied to nplayer general-sum extensive-form games, establishing that it is hindsight-rational with respect to a specific set of deviation functions, which the authors coin blind counterfactual deviations. Moreover, in a very recent working paper, [Morrill et al., 2021] extend their prior work [Morrill et al., 2020] by identifying a general class of deviations-called behavioral deviations-that induce equilibria that can be found through uncoupled no-regret learning dynamics.