Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games
Authors: Brian Hu Zhang
Gabriele Farina
Tuomas Sandholm
Venue: ICLR 2024 poster (2024)
Keywords: extensive-form games
correlated equilibria
no-regret learning
Primary area: reinforcement learning

Abstract: A recent paper by Farina and Pipis (2023) established the existence of uncoupled no-linear-swap regret dynamics with polynomial-time iterations in extensive-form games. The equilibrium points reached by these dynamics, known as linear correlated equilibria, are currently the tightest known relaxation of correlated equilibrium that can be learned in polynomial time in any finite extensive-form game. However, their properties remain vastly unexplored, and their computation is onerous. In this paper, we provide several contributions shedding light on the fundamental nature of linear-swap regret. First, we show a connection between linear deviations and a generalization of communication deviations in which the player can make queries to a ``mediator'' who replies with action recommendations, and, critically, the player is not constrained to match the timing of the game as would be the case for communication deviations. We coin this latter set the untimed communication (UTC) deviations. We show that the UTC deviations coincide precisely with the linear deviations, and therefore that any player minimizing UTC regret also minimizes linear-swap regret. We then leverage this connection to develop state-of-the-art no-regret algorithms for computing linear correlated equilibria, both in theory and in practice. In theory, our algorithms achieve polynomially better per-iteration runtimes; in practice, our algorithms represent the state of the art by several orders of magnitude.

Published as a conference paper at ICLR 2024
MEDIATOR INTERPRETATION AND FASTER LEARNING ALGORITHMS FOR LINEAR CORRELATED EQUILIBRIA IN GENERAL EXTENSIVE-FORM GAMES
Brian Hu Zhang Carnegie Mellon University bhzhang@cs. cmu. edu
Gabriele Farina MIT gfarina@mit.com edu
Tuomas Sandholm Carnegie Mellon University Strategic Machine, Inc. Strategy Robot, Inc
Optimized Markets, Inc. sandholmd cmu edu
ABSTRACT
A recent paper by Farina & Pipis (2023) established the existence of uncoupled no-linear-swap regret dynamics with polynomial-time iterations in extensive-form games. The equilibrium points reached by these dynamics, known as linear cor- related equilibria, currently the tightest known relaxation of correlated equi- librium that can be learned in polynomial time in any finite extensive-form game. However, their properties remain vastly unexplored, and their computation is oner- ous. In this paper, we provide several contributions shedding light on the funda- mental nature of linear-swap regret. First, we show a connection between linear deviations and a generalization of communication deviations in which the player can make queries a "mediator" who replies with action recommendations, and, critically, the player is not constrained to match the timing of the game would the case for communication deviations. We coin this latter set the untimed communication (UTC) deviations. We show that the UTC deviations coincide pre- cisely with the linear deviations, and therefore that any player minimizing UTC regret also minimizes linear-swap regret. We then leverage this connection to de- velop state-of-the-er no-regret algorithms for computing linear correlated equilib- ria, both in theory and in practice. In theory, our algorithms achieve polynomially better per-iteration runtimes; in practice, our algorithms represent the state of the art by several orders of magnitude.
INTRODUCTION
In no-regret learning, player repeatedly interacts with possibly adversarial environment. The task of the player is to minimize its regref, which is defined to be the difference between the utility experienced by the player, and the largest utility that it could have achieved in hindsight if it had played other strategies instead, according to some strategy transformation or deviation. The set of allowable deviations defines the notion of regret, with larger sets corresponding to tighter notions. Two extremes external deviations, which are the set of all constant transformations, and swap deviations, which are all possible functions.
In games, no-regret learning has very tight connection to notions of correlated equilibrium. Each notion of regret has its corresponding notion of equilibrium, which will be reached by a set of players that independently
no-regret algorithms for that notion of regret. External and swap deviations, respectively, correspond to the well-known normal-form coarse correlated equilibrium (Moulin & Vial, 1978) (NFCCE) and normal-form correlated equilibrium (Aumann, 1974) (NFCE). For extensive-form games specifically, other sets of deviations include the trigger deviations (Gordon al., 2008; Farina et al., 2022a), which correspond to extensive-forms correlated equilibrium (von Stengel & Forges, 2008), and the communication deviations (Zhang & Sandholm, 2022; Fujii, 2023), which correspond to communication equilibrium' (Myerson, 1986; Forges, 1986).
'Technically, communication equilibria more broad than (o, (o:)-equilibria where 4. is the set of com- munication deviations: in communication equilibrium, there is explicit mediator who has the power

---

Published as a conference paper at ICLR 2024
In this paper, we consider a notion of regret first studied for extensive-form games by Farina & Pipis (2023), namely, regret with respect to the set of linear functions from the strategy set to itself. This notion is natural stepping stone between external regret, which is very well studied, and swap regret, for which achieving poly(d) T regret, where d is the size of the decision problem and < 1, is a long-standing open problem. We make two main contributions.
The first contribution is conceptual: we give, for extensive-form games, an interpretation of the set of linear deviations. More specifically, we will first introduce a of deviations, which we will call the untimed communication (UTC) deviations that, a priori, seems very different from the set of linear deviations at least on conceptual level. The deviation set, rather than being defined algebraically (linear functions), will be defined in terms of an interaction between a deviator, who wishes to evaluate the deviation function at a particular input, and a mediator, who answers queries about the input. We will show the following result, which is our first main theorem:
Theorem. The untimed communication deviations are precisely the linear deviations.
The mediator-basee framework is more in line with other extensive-form deviation sets-indeed, all prior notions of regret for extensive form, to our knowledge, including all the notions discussed above, can be expressed in terms of the framework. As such, the above theorem places linear deviations firmly within the same framework usually used to study deviations in extensive form.
We will then demonstrate that the set of UTC deviations is expressible in terms of scaled exten- sions (Farina et al., 2019c), opening up access to a wide range of extremely fast algorithms for regret minimization, both theoretically and practically, for UTC deviations and thus also for linear deviations. Our second main theorem is as follows.
Theorem (Faster linear-swap regret minimization). There exists a regret minimizer with regret Od VT) against all linear deviations, and whose per-iteration complexity is dominated by the complexity of computing a fixed point of a linear map ((t) co X + co
In particular, using the algorithm of Cohen et al. (2021) to solve the linear program of finding fixed point, our per-iteration complexity is O(d"), where w =e 2.37 is the current matrix multiplication constant and Ô hides logarithmic factors. We elaborate on the fixed-point computation in Section 6. This improves substantially on the result of Farina & Pipis (2023), which has the same regret bound but whose per-iteration computation involved a quadratic program (namely, an l2 projection), which has higher complexity than linear program (they give bound of )). Finally, we demonstrate via experiments that our method is also empirically faster than the prior method.
2 PRELIMINARIES
Here, we review fundamentals of tree-form decision making, extensive-form games, and online convex optimization. Our exposition and notation mostly follows Farina & Pipis (2023).
2.1 TREE-FORM DECISION MAKING
A tree-form decision problem is a rooted tree where every path alternates between two types of nodes: decision points (j E J) and observation points (or sequences) (a E E). The root node Ø Σ is always observation point. At decision points, the edges called actions, and the player must select one of the legal actions. At observation points, the edges are called observations signals, and the player observes one of the signals before continuing. The number of sequences is denoted = Σ The parent of a node s is denoted p.. The set of actions available at a decision point; j denoted Ay. The set of decision point following an observation point a will be denoted
only to sample a strategy profile, but also to pass private information between players-so communica- tion equilibrium is not necessarily correlated profile at all. This distinction is fairly fundamental: it is the reason why polynomial
algorithms for optimal communication equilibrium can exist extensive-fomm games (Zhang & Sandholm, 2022). We may call a communication equilibrium that also happens to be a cor- related profile a private communication equilibrium, where private denotes that the mediator is not allowed to pass information between players. However, since this paper focuses no-regret learning, we have no reason make this distinction, so we largely ignore it.
2

---

Published as a conference paper at ICLR 2024
Co. An observation node Σ is uniquely identified by its parent decision point and the action a taken at We will hence use ja as an alternative notation for the same observation point.
A sequence-form pure strategy for the player is vector E {0, 1j4 indexed by sequences in Σ, where z(0) = if the player selects every action on the Ø + a path. A sequence-form mixed strategy is convex combination of requence-form pure strategies. We will use X' denote the set of sequence-fore pure strategies. An important property (Romanovskii, 1962; von Stengel, 1996) is that the convex hull of X, which we will denote co X, is described by a system of linear constraints:
x x0)) = 1,
x(p))=
Σ x(ja) Vj J.
(1)
aEA,
Tree-form decision problems naturally encode the decision problems faced by player with perfect recall in an extensive-form game. An extensive-form game with n players is a game of incomplete information played on tree of nodes H. At every non-leaf node h H. the children of are labeled with actions E A₁, Each nonterminal node is assigned to different player, and the player to whom node is assigned selects the action that node. The nodes assigned partitioned into information sets, or infosels; a player cannot distinguish among the nodes in a given infoset, and therefore pure strategy must play the same action at every node in an infoset. Finally, each player has utility function u, Z E. where Z is the set of terminal nodes. We will assume perfect recall, that is, we will assume that players never forget information.
given player are
In extensive-fome game, perfect-recall player's decision problem is tree-form decision prob- lem whose size (number of nodes) is linear in the size of the game tree, and the utility functions are linear in every player's strategy. We will use X; to denote the tree-form decision problem faced by player i. Then the utility functions u, co X, x x... x co X, + R are linear in each player's strategy.
2.2 ONLINE CONVEX OPTIMIZATION AND REREGRET
In online convex optimization (Zinkevich, 2003), a player (or "learnrr") has a strategy set X' S Rdd and repeatedly faces possibly-adversarial environment. More formally, at every iteration t I, the player selects a distribution x E A(X), and an adversary simultaneously selects a utility vector (t) E [0, 1jd. The player then observes the utility u selects a new strategy (t-1) E X, and so on. Our metric of performance will be the notion of Ø-regrel (Greenwald & Jafari, 2003). Given a set of transformations 4 S (cx:
Definition 2.1. The r-rrrett of the player after T timesteps is given by
Rego (T) max PE
E (1)
(1,)) x)
Various choices of & correspond to various notions of regret, with larger sets resulting in stronger notions of regret. In an extensive-forn game, notions of 4-regret correspond to notions of equilib- rium. For each player i E [n], let & S (co X be a set of transformations for player i.
distribution π A(X) x ... Xx) is called a correlated profile. e-((l)--quillibrium is a correlated profile such that EzZz (u;()) viation & E ..- If all players independently run T -.rregret minimizers over their strategy sets Xr the empirical frequency of play E max; Rega, (T)/T. Thus, P-regret minimizers immediately imply no-regret learning algo- rithms converging to (Q:)-equilibria. Some common choices of Φ and corresponding equilibrium notions, are in Table 1. In this paper, our focus will be on linear-swap regret, which is the re- gret against the set L of all linear' maps ó X' + Co.Y. To our knowledge, linear-swap regret was first proposed by Gordon et al. (2008) for general convex spaces. They developed general framework for d-regret minimization, which we now review. We start by observing that any linear & X + 2 is naturally extended to function
uz( xr:)]] < e. for every player i and de-
(n) ..... (T) will be an -qquiiiuui for
co + co X by setting
2 A is the set of functions from B to A
è For sets X' whose affine hull excludes the origin, there is no point in distinguishing afline maps from linear maps. Sequence-for form strategy sets X' are such sets, because (²0) = 1 is always constraint. So, throughout this paper, we will distinguish between linear and affine maps.
3

---

Published as a conference paper at ICLR 2024
Deviations +
Equilibrium concept
References
Constant (extemal). + (0: 2o 2g F X
Normal-form course correlated
Moulin & Vial (1978)
Trigger (see Section 3)
Extensive-fowe correlated Communication
von Stengel & Forges (2008)
Communication (see Section 3) Lineur Untimed communication
Forges (1986); Myerson (1986) Farina Pipis (2023); this paper
Linear correlated
Swap, x
Normal-form correlated
Aumann (1974)
Table I: Some examples of deviation sets + and corresponding notions of correlated equilibrium, in increasing order size of & (and thus increasing tightness of the equilibrium concept)
é : co e x + l==' ((x'), where и E ( is any distribution for which Ex'' x' = x (The choice of distribution is irrelevant because of linearity of expectation, and thus Φ : co + X uniquely defined.)
Theorem 2.2 (Gordon et al., 2008). Let & S LiIN be a convex set of transformations, and let Ræp be a deterministic" external regret minimizer over 4 whose regret after T timesteps is R. Then the following algorithm achieves D-regret R on X after T timesteps: At every timestep t, the player queries R& for a strategy (transformation) dit) E and the player selects a strategy x! E co X that is fixed point of (hit), that is, (()(()))) =((1) Upon observing utility u the player forwards the utility @ + (2l1), ((x(())) to Ro.
Therefore, to construct a PIN minimizer over X, it suffices to be able to (1) minimize external regret over Lr,N, and (2) compute fixed points of transformations ((t), For linear g(()) x + Aæ, computing fixed point amounts to solving linear program. Therefore, the focus of this paper will be on external regret minimizers over the set PLIN-
For extensive-form games, linear-swap regret was recently studied in detail by Farina & Pipis (2023): they provide a characterization of the set LIN when X' is a sequence-fore polytope, and thus derive an algorithm for minimizing -eerrtt over X. Their paper is the starting point of ours.
MEDIATORS AND UTC DEVIATIONS
With the notable exception of linear deviations, most sets of deviations & for extensive-form games are defined by interactions between a mediator who holds a strategy x E X, and a deviator, who should compute the function o(x:) by making queries to the mediator. The set of deviations is then defined by what queries that the player is allowed to make. Before continuing, we will first Section 2.2 in this paradigm. for intuition. For a given decision
formulate the sets & mentioned point j. call an action a E A, the recommended action at j. denoted a(x. j). if x(ja) = 1. Since æ a sequence-form strategy, is possible for a decision point to have no recommended action its parent pj is itself not recommended.
Constant (NFCCE): The deviator cannot to make any queries to the mediator.
Trigger (EFCE): The deviator, upon reaching decision point j. learns the recommended action (if any) at j before selecting its own action.
Communication:
The deviator maintains a state with the mediator, which is sequence a,, initially Ø. Upon reaching a decision point j. the deviator selects decision point j' E C2 (possibly j' * j) which to query the mediator, the deviator observes the recommendation a' = a ((, J'). then the deviator must pick an action E A,. The state is updated to j'a'. Swap (NFCE): The deviator learns the whole strategy æ before selecting its strategy.
An example of communication deviation can be found in Section 5, and further discussion of these solution concepts can be found in Appendix B. Of these, the closest notion to ours is the notion of communication deviation, and that is the starting point of our construction. One critical property of
'A deterministic regret minimizer is one that uses no randomness internally to compute its strategies. When the strategy set (here +) is convex, and the notion is external regret, the learner need not random- ize: since utilities are linear, picking a distribution (+) E A(2) equivalent to deterministically select- ing the point tt)) = Be ø. Thus, we allow the aavadversary (here, the player itself) to utility
(z) (1)) that depends the leamer's choice of db
4

---

Published as a conference paper at ICLR 2024
communication deviations is that the mediator and deviator "share clock": for every decision point reached, the deviator must make exactly one query to the mediator. As the name suggests, our set of untimed deviations results from removing this timing restriction, and therefore allowing the deviator to make any number (7ero, one, or more than one) of queries to the mediator for every decision point reached. We formally define the decision problem faced by an untimed deviator follows.
Definition 3.1. The UTC decision problem corresponding to given tree-form decision problem is defined as follows. Nodes are identified with pairs (s, 8) where 8, E E U J. 8 represents the state of the real decision problem, and represents the state of the mediator. The root is (Ø, ) E E.
1. (0, x Σ is an observation point. The deviator observes the next decision point
j E Co. and the resulting decision point (j.
2. (j. J) E I x I is observation point. The deviator observes the recommendation a( a(x.J). and the resulting decision point is (j.ja).
3. (i, 7) I is decision point. The deviator can choose either play action a E Aj or to query a decision point J E Ca- In the former case, the resulting observation point is (ja, ō) for E Ay; in the latter case, the resulting observation point (j.J).
Any mixed strategy of the deviator in this decision problem defines function o X + X, where (a) the probability that an untimed deviator plays all the actions on the path to a when the mediator recommends according to pure strategy We thus define:
Definition 3.2. An UTC deviation is any function @ X co X' induced by mixed strategy of the deviator in the UTC decision problem.
Clearly, the set UTC deviations at least as large as the set communication deviations, and at most as large as the set of swap deviations. In the next section, we will discuss how to represent UTC deviations, and show that UTC deviations coincide precisely with linear deviations.
4 REPRESENTATION OF UTC DEVIATIONS AND EQUIVALENCE BETWEEN UTC AND LINEAR DEVIATIONS
Since UTC deviations are defined by a decision problem, one method representing such devi- ations is to express it as a tree-form decision problem and use the sequence-form representation. However, the UTC decision problem is not a tree-it is a DAG, since there are multiple ways of reaching any given decision point (j. ō) depending on the ordering of the player's past actions and queries. Converting
tree by considering the tree of paths through the DAG would result in an exponential blowup: decision point (), where is at depth & and ő is at depth E, can be reached in roughly (k++)) ways, the total number of paths can be exponential in the depth of the decision problem even when the number of sequences, d = [-], is not.
However, still possible to define the "sequence form" of pure deviation in our UTC decision problem follows:: it is pair of matrices (A, B) where A E {0, {0, 1X encodes the part cor- responding to sequences (a, σ). and B E {0, 1]3x3 encodes the part corresponding to decision 1 if the deviator plays all the actions
points (i.3). a) (a,ā), and similarly B(j.ā) = 1 if the deviator plays all the actions on some path to observation node (). Since the only possible way for two paths to end at the same observation point is for the deviator to have changed the order of actions and queries, for any given pure strategy of the deviator, most one path can exist for both cases. Therefore, the set of mixed sequence-fore deviations can be expressed using the following set of constraints:
some path to observation point
A(p;, BB.jpa) = Σ A(ja,7) B(JJ)
VjEJTōE
aEA,
FEC
A( A =
Vō + Ø
A, 2
"This construction is special case of the more general construction of sequence forms for DAG decision problems explored by Zhang al. (2023) in the case of team games.
5

---

Published as a conference paper at ICLR 2024
where, in slight abuse of notation, define B(j. pe) 0 for every E J. Moreover, for any pair of matrices (A, B) satisfying the constraint system and therefore defining some deviation : X' - co X. it is easy to compute how & acts any E d: the probability that the deviator plays all the actions on the Ø > a path is simply given by
= =z())A(,,)=(Aazk) DEE
and therefore is nothing more than matrix multiplication with A, that is, d(x:) Ax.. We have thus shown that every UTC deviation is linear, that is, urTc C & In fact, the reverse inclusion holds too:
Theorem 4.1. The UTC deviations are precisely the linear deviations. That is, PUTC 0LIN-
The proof is deferred Appendix D. Since the two sets equivalent, in the remainder of the paper, we will use the terms UTC deviation and linear deviation (similarly, UTC regret and linear-swap regret) interchangeably.
5 EXAMPLE
In this section, we provide an example in which the UTC deviations are strictly more expressive than the communication deviations. Consider the game in Figure 1. The subgames rooted D and E are guessing games, where A must guess v's action, with a large penalty for guessing wrong. Consider the correlated profile that mixes uniformly among the four pure profiles (a,, bj. C1, f;, 9₁) for i,j (1, In this profle, the information that needs to guess perfectly is contained in the recommendations: the recommendation A tells how guess at D, and the recommendation at B tells it how to guess at E. With communication deviation, A cannot access this information in a profitable way, since upon reaching C, must immediately make its first mediator query. Hence, this profile is communication equilibrium. However, with untimed communication deviation, A can profit: it should, upon reaching C. play action C2 without making a mediator query, and then query A if it observes D, and B if it observes E. This deviation is allowed only due to the untimed nature of UTC deviations allows the deviating player to delay its query to the mediator until reaches either D or E. In timed communication deviation, this deviation is impossible, because the player must make its first query (A, B, or C) before reaching D or E, and thus that query cannot be conditioned on which one of D E will be reached.
Another example, where the player can profit from making more than one query, and untimed devi- ations affects the set of possible equilibrium outcomes, can be found in Appendix C.
REGRET MINIMIZATION ON PUTC
In this section, we discuss how Theorem 4.1 can be used to construct very efficient LiN--eereet minimizers, both in theory and in practice. The key observation use here is due Zhang et al. (2023): they observed that DAG decision problems have a structure that allows them to be expressed as scaled extensions, allowing the application of the counterfactual regret minimization (CFR) framework (Zinkevich et al., 2007: Farina et al., 2019a):
Theorem 6.1 (CFR for LiN, special case of Zhang et al., 2023). CFR-based algorithms can be used to construct an external regret minimizer on PUTC (and thus also on & with Odd regret and ((d) per-iteration complexity.
Applying Theorem 2.2 now yields:
Theorem 6.2. CFR-based algorithums be used construct PLix-regret minimizer with ( regret. and per-iteration complexity dominated by the complexity of computing fixed point of a linear transformation (f(t) X X.
'The actions/queries A makes at A and B are irrelevant, because A only cares about maximizing utility, and it always gets utility 0 regardless of what it does. In the depiction of this deviation in Figure 2, the deviator always plays action at A and B.

---

Published as a conference paper at ICLR 2024
A
B
c
22
b1
D
C1
E
11
d2
e1
62
91
92
92
+1
10
-10
+1
+1
10
10
+1
Figure 1: An example extensive-form game in which communication deviations strict subset of UTC deviations. There are two players, Pl (A) and P2 (V). Infosets for both players are labeled with capital letters (e.g., A) and joined by dotted lines. Actions are labeled with lowercase letters and subscripts (e.g., a1). Pl's 's utility is labeled on each terminal node. P2's utility is zero everywhere (not labeled). Boxes are chance nodes, at which chance plays uniformly at random.
A
8
B
0
31 32
b1
b2
C1
C2
d1
d2
Ø
1
0g
d
e
b
b2
C:
B
E
a
a
Ca
di
da
D
did2
d
e e
0,02
02
Figure 2: A part of the UTC decision problem for corresponding to same game. Nodes labeled are decision points for A; boxes are observation points. "..." denotes that the part of the decision problem following that edge has been omitted. Terminal nodes are unmarked. Red edge labels indicate interactions with the mediator; blue edge labels indicate interactions with the game. The profitable untimed deviation discussed in Section 5 is indicated by the thick lines. The first action taken in that profiable deviation, C2, is not legal for timed deviator, because timed deviator must query the mediator once before taking its first action. The matrices (lower-left corner) are the pair of matrices (A, B) corresponding that same deviation. All blank entries O.

---

Published as a conference paper at ICLR 2024
4-Player Kuhn poker
Ridesharing game
Average linear swap regret
10
Average linear swap regret
10
10-1
10-1
10
10-2
10-3
10
10"4
Farina & Pipis (2023)
10-4 4
Farina & Pipis (2023)
UTC dynamics (this paper)
UTC dynamics (this paper)
10
10
10
10
10a
10a
10a
10a
10
10
10a
10a
10
10
Iteration
Iteration
3-Player Leduc poker
Sheriff of Nottingham
Average linear-s wap regret
Average linear-s wap regret
100
10-1
10
10"2 22
10
Farina & Pipis (2023)
Farina & Pipis (2023)
10
UTC dynamics paper)
UTC dynamics paper)
10
10
10a
10a
10
10
10
10
10a
10a
10
10
Iteration
Iteration
Figure 3: Experimental comparison between our dynamics and those of Farina & Pipis (2023) for approximating a linear correlated equilibrium in extensive-form games. Each algorithm was run for maximum of 100,000 iterations or 6 hours, whichever was hit first. Runs that were terminated due the time limit are marked with square
As mentioned the introduction, this significantly improves the per-iteration complexity of linear- swap regret minimization. Fixed points can be computed by finding feasible solution to the constraint system {x X. x}. where æ X' expressed using the sequence- form con- straints (1). This is linear program with ((d) variables and constraints, so the LP algorithm of Cohen et al. (2021) yields fixed-point computation algorithm with runtime O(d").
For comparison, the algorithm of Farina & Pipis (2023) requires an le projection onto X' on every iteration, which requires solving convex quadratic program; the authors of that paper derive bound of Odd which, although polynomial, much slower than our algorithm. CFR-based algorithms are currently the fastest practical regret minimizers (Brown & Sandholm, 2019; Farina al., 2021)therrefore showing that our method allows such algorithms to be applied also a significant practical step. In Section 7, we will show empirically that the resulting algorithm is significantly better than the previously-knows state the art, terms both per-iteration time complexity and number of iterations.
7 EXPERIMENTAL EVALUATION
We empirically investigate the performance of our learning dynamics for linear correlated equilib- rium, compared the recent algorithm by Farina & Pipis (2023). We test on four benchmark games:
4-player Kuhn poker, multiplayer variant of the classic benchmark game introduced by Kuhn (1950). The deck has cards. This game has 3,960 terminal states.
A ridesharing game, two-player general-sum game introduced as benchmark for welfare- maximizing equilibria by Zhang et al. (2022). This game has 484 terminal states.
3-player Ledue poker, three- player variant of the classic Ledue poker introduced by Southey et al. (2005). Only one bet per round allowed, and the deck has 6 cards (3 ranks, suits). The game has 4,500 terminal states.
8

---

Published as a conference paper at ICLR 2024
Game
Our algorithm
Farina Pipis (2023)
Speedup
4-Player Kuhn poker
5.65ms
0.30ms
195ms
7ms
35x
Ridesharing game 3-Player Leduc poker
676μs
+
80ps
160ms + 7ms
237x
42.0ms
0.7ms
12.1s
1.0s
287x
Sheriff of Nottingham
114ms
16ms
50.2s + 9.6s
442x
Table 2: Comparison of average time per iteration. For each combination of game instance and algorithm, the mean and standard deviation of the iteration runtime are noted.
Game
Target gap
Our algorithm
Farina & Pipis (2023)
Speedup
4-Player Kuhn poker Ridesharing game
10-4
32.8s
5h 25m
595x
9 x 10
8,89s
4h 07m
1667 x
3-Player Ledue poker
0.224
2.12s
6h 00m
10179x
Sheriff of Nottingham
2.06
2.00s
6h 00m
10800x
Table 3: Comparison of time taken to achieve a particular linear swap equilibrium gap. The gap is whatever gap was achieved by the algorithm of Farina & Pipis (2023) before termination.
Sheriff of Nottingham, two-player general-sum game introduced by Farina et al. (2019h) for its richness of equilibrium points. The smuggler has 10 items, maxmimum bribe of 2, and rounds to bargain. The game has 2,376 terminal states.
We run our algorithm based on the UTC polytope, and that of Farina Pipis (2023) (with the learning rate 0.1 as used by the authors), for limit of 100,000 iterations or 6 hours, whichever hit first. Instead of solving linear programs find the fixed points, we use power iteration, which is faster in practice. All experiments were run on the same machine with 32GB of RAM and processor running at nominal speed of 2.4GHz, For our learning dynamics, we employed the CFR algorithm instantiated with the regret matching* (Tammelin, 2014) regret minimizer at each decision point (see Theorem 6.1). Experimental results are shown in Figure 3.
One of the most appealing features of our algorithm is that allows CFR-based methods to apply. CaRebased methods are the fastest regret minimizers in practice, so it is unsurprising that using them results in better convergence seen in Figure 3. Another appealing feature is that method sidesteps the need projecting onto the set of transformations. This is in contrast with the algorithm of Farina & Pipis (2023), which requires an expensive projection every iteration. We observe that this difference results in a dramatic reduction in iteration runtime between the two algorithms, which quantify in Table 2. So, we remark that when accounting for time instead of iterations the x-axis of the plots in Figure 3, the difference in performance between the algorithms appears even stronger. Such plot is available in Appendix E.
CONCLUSION AND FUTURE RESEARCH
In this paper, we have introduced a new representation for the set of linear deviations when the strategy space is sequence form. Our representation connects linear deviations to the mediator- based framework that more typically used for correlation concepts extensive-form games, and therefore gives a reasonable game-theoretic interpretation of what linear equilibria represent, It also leads to state-of-the-art no-linear-regre algorithms, both in theory and in practice. Several natural questions remain open:
1. Is there an algorithm whose swap regret is poly(d) T for < in extensive-form games? (See also Appendix B for some recent progress on this problem.)
2. What would be a reasonable definition of untimed communication equilibrium, as refine- ment of communication equilibrium (see also Appendix A.6)?
3. For extensive-form correlated equilibrium, it is possible to achieve poly(d) log(T)) re- gret (Anagnostides et al., 2023), and to compute exact equilibria polynomial time (Huang & von Stengel, 2008). Can one extend these results to linear equilibria?

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This material is based on work supported by the Vannevar Bush Faculty Fellowship ONR N00014-23-1-2876, National Science Foundation grants RI-2312342 and RI-1901403, ARO award W911NF2210266, and NIH award A2401085001.
REFERENCES
Ioannis Anagnostides, Gabriele Farina, and Tuomas Sandholm. Near-optimal phi-regret learning in extensive-fome games. In International Conference on Machine Learning (ICML), 2023.
Robert Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economicx, 1:67-96, 1974.
Noam Brown and Tuomas Sandholm. Solving imperfect-inforration games via discounted regret minimization. In AAAI Conference on Artificial Intelligence (AAAI). 2019.
Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM (JACM), 68(1):1-39, 2021.
Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. From external to swap regret 2.0: An efficient reduction and oblivious adversary for large action spaces. arXiv preprint Ttt::2310.19788 2023.
Gabriele Farina and Charilaos Pipis. Polynomial-tine linear-swap regret minimization in imperfect- information sequential games, arXiv preprint arXiv:2307.0544 004440, 2023.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Regret circuits: Composability of regret minimizers. In International Conference Machine Learning, pp. 1863-1872, 2019a.
Gabriele Farina, Chun Kai Ling, Fci Fang, and Tuomas Sandholm. Correlation in extensive-fome games: Saddle-point formulation and benchmarks. In Conference Neural Information Pro- cessing Systems (NeurIPS), 2019b.
Gabriele Farina, Chun Kai Ling, Fei Fang, and Tuomas Sandholm. Efficient regret minimization algorithm for extensive-form correlated equilibrium. Conference on Neural Information Pro- cessing Systems (NeurIPS), 2019c.
Gabriele Farina, Andrea Celli, Nicola Gatti, and Tuomas Sandholm. Connecting optimal ex-ante collusion in teams to extensive-form correlation: Faster algorithms and positive complexity re- sults. In International Conference on Machine Learning, 2021.
Gabriele Farina, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Simple uncoupled no-regret learning dynamics for extensive-form correlated equilibrium. Journal of the ACM, 69(6):1441, 2022a.
Gabriele Farina, Chung-Wei Lee, Haipeng Luo, and Christian Kroer. Kernelized multiplicative weights for 0/1-polyhedral games: Bridging the gap between learning extensive and normal-form games. In International Conference on Machine Learning (ICML), pp. 6337-6357. PMLR, 2022b.
Francoise Forges. An approach to communication equilibria. Econometrica: Journal of the Econo- metric Society, pp. 1375-1385, 1986.
Françoise Forges and Frédéric Koessler. Communication equilibria with partially verifiable types. Journal of Mathematical Economics, 41(7):793-811 2005.
Kaito Fujii. Bayes correlated equilibria and no-regret dynamics. arXiv preprint arXiv:2304.05005, 2023.
Geoffrey Gordon, Amy Greenwald, and Casey Marks. No-regret learning in convex games. In 25th international conference Machine learning, pp. 360-367. ACM, 2008.
10

---

Published as a conference paper at ICLR 2024
Amy Greenwald and Amir Jafari. A general class of no-regret learning algorithms and game- theoretic equilibria. In Conference on Learning Theory (COLT), Washington, D.C., 2003.
Wan Huang and Bernhard von Stengel. Computing an extensive-form correlated equilibrium in
polynomial time. In International Workshop on Internet and Network Economics, pp. 506-513. Springer, 2008.
Andrew Kephart and Vincent Conitzer. The revelation principle for mechanism design with signaling costs. ACM Transaction on Economics and Computation (TEAC), 9(1):1-35, 2021.
H. W. Kuhn. A simplified two-person poker. In H. W. Kuhn and A. W. Tucker (eds.). Contributions to the Theory of Games, volume of Annals of Mathematics Studies, 24, pp. 97-103. Princeton University Press, Princeton, New Jersey, 1950.
H. Moulin and J.-P. Vial. Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3-4):201- 221, 1978.
Roger B Myerson. Multistage games with communication. Econometrica: Journal of the Econo- metric Society, pp. 323-358, 1986.
Binghui Peng and Aviad Rubinstein. Fast swap regret minimization and applications to approximate correlated equilibria. arXiv preprint arX1v:2310.19677, 2023.
I. Romanovskii. Reduction of game with complete memory matrix game, Soviet Mathematics, 3, 1962.
Finnegan Southey, Michael Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: Opponent modelling in poker. In Conference on Uncertainty in Artificial Intelligence (UAI), July 2005.
Oskari Tammelin. Solving large imperfect information games using cfr+. arXiv: 2014.
arXiv preprint
Bernhard von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220-24,, 1996.
Bernhard von Stengel and Françoise Forges. Extensive-form correlated equilibrium: Definition and
computational complexity. Mathematics of Operations Research, 33044):002-100 2008.
Brian Hu Zhang and Tuomas Sandholm. Polynomial-time optimal equilibria with mediator in extensive-form games. In NeurlPS, 2022.
Brian Hu Zhang, Gabriele Farina, Andrea Celli, and Tuomas Sandholm. Optimal correlated equilib- ria in general-sum extensive-form games: Fixed-paramete algorithms, hardness, and two-sided column-generatio arXiv preprint arXiv:2203.0718// 2022.
Brian Hu Zhang, Gabriele Farina, and Tuomas Sandholm. Team belief dag: Generalizing the se- quence form to team games for fast computation of correlated team max equilibria via regret minimization. In International Conference on Machine Learning (ICML), 2023.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference on Machine Learning (ICML), pp. 928-936, Washington, DC, USA, 2003.
Martin Zinkevich, Michael Bowling, Michael Johanson, and Carmelo Piccione. Regret minimization in games with incomplete information. In Conference on Neural Information Processing Systems (NeurIPS), 2007.
11

---

Published as a conference paper at ICLR 2024
A DISCUSSION
Here, we discuss few points of interest about UTC and linear deviations.
A.1 THE CONVEX HULL OF PURE DEVIATIONS
In our definitions, we were careful to allow transformations & ① to map from the set of pure strategies, X, to convex hull co,Y, instead of insisting that every pure strategy map onto another pure strategy. One might ask whether this makes difference in definitions. For example, if in Definition 2.1 we restrict our attention to Ø : X + X. does the definition change? In symbols, for a given set of transformations t is + C co & where T = {o E + o(x) E X Vo E X}? For the other sets of deviations mentioned in this paper (external, swap, trigger, and communication), the answer is already known to be positive.
Our equivalence theorem between UTC and linear deviations gives an answer to this question for the set of linear deviations as well. Since the UTC deviations are defined by a decision problem, every mixed UTC deviation is by definition equivalent to distribution over pure UTC deviations. That is, the vertices of Purc are the pure UTC deviations: they map pure strategies X' to pure strategies. Since PUTC PI.NN this proves:
Corollary A.1. When X is a sequence form polytope, the extreme points of L are the linear maps 6: X, i.e., the linear maps that map pure strategies to pure strategies. Thus, $LIN LLIN
This result is not obvious priori. For example, it fails to generalize to other sets of functions Φ, or LIN for polytopes X that are not sequence- polytopes:
Other sets of functions Φ: Let t { consist of single constant function Φ x ++ xx, where x E (co \ X. Then & is empty, so & co T.
Non-sequence-forte polytopes: Take X' to be a trapezoid ABCD where AB is the longer of the two bases and consider the linear map Φi with ((A) D, Φ(D) = A, and of B) = C. Then an extreme point of LLIN, but o(C') will lie somewhere along segment AB, but at neither endpoint- -that is, not at vertex. Figure 4 has a visual depiction.
= 6(A)
C = xBB)
A 4=6(D)
d(C)
B
Figure 4: A visual depiction of the argument that Corollary A.l cannot generalize to all polytopes. The affine map e maps the large blue polygon onto the small orange polygon, and a vertex of the set of linear maps from polygon ABCD to itself, yet ((C) is not vertex of ABCD.
A.2 GENERALIZATION TO ARBITRARY PAIRS OF POLYTOPES
Our main result characterizes the set of linear maps o X + X' for sequence-form polytopes X. However, is actually more general than this: an identical proof works characterize the set of linear maps Φ y - co. for any (possibly different!) sequence form polytopes X' and y. Hence, we have shown:
Theorem A.2. Let X.y be sequence-fome strategy sets. The linear maps y + co X are precisely the functions induced by strategies in the DAG decision problem whose nodes identified with pairs (s, 3), where s E Ex U Jx and E Ey U Jy, and which behaves analogously to Definition 3.1.
12

---

Published as a conference paper at ICLR 2024
Although mostly concerned with the case X' = y/ in this paper, state this extension in the hope that may be independent interest. We will also use in the proof of the revelation principle (Theorem A.
A.3 UNIQUENESS OF REPRESENTATION
The statement of Theorem 4.1 discusses Putc and PLIN sets of functions & S (co xxx It does not imply that for every linear map & : X' - co X' there is exactly one representation of Φ as a deviator strategy in the UTC decision problem, only that there is at least one representation. Indeed, the external deviations (constant functions @ x + x" for fixed x" E co X' can be represented via a large number of different strategies in the UTC decision problem: the deviator may send any number of queries to the mediator, before eventually deciding to ignore the queries and play according to xx, and such deviator would still represent the external deviation Φ
Similarly, Theorem 4.1 also does not imply that every matrix A E R representing a linear map AA X co X' is part of a pair (A, B) satisfying the system of equations (2). Indeed, the proof of Theorem 4.1 only shows that for every linear Φ X - co X, there is at least one pair (A, A) satisfying (2) where A represents Φb It is easy construct matrices A that represent linear maps, yet cannot satisfy (2), by changing the first row of A to some other vector e with e x = 1 for all X.
A.4 WHEN UNTIMED AND TIMED COMMUNICATION DEVIATIONS COINCIDE
If all players have only one layer of decision nodes, the game is single-stage Bayesian game- that special case, the communication deviations and linear deviations will coincide". This property was also proven by Fujii (2023), but framework gives particularly simple proof via Theo- rem 4.1: for any UTC deviation in a single-stage game, the deviator makes either no queries or one query to the mediator. A communication deviator can simulate the same function by making the same query (if any), or, if the UTC deviator makes no query. by making an arbitrary query and ignoring the reply. It turns out that the converse also essentially true:
Theorem A.3. Consider any decision problem with no nontrivial decision points-thal is, the player has at least two legal actions at every decision point. The (limed) communication deviations coincide with the untimed communication deviations (and hence also the linear deviations) if and only if every path through the decision problem contains at most one decision point.
Proof. The if direction was shown above and by Fujii (2023), so it suffices to show the only if direction. Suppose there are two decision points, A and B, such that B is child of action an at A. Let 02 be another action at A, and let by and by be two actions at B. (The game in Figure 5 has such structure). Consider any deviation e that plays action a; if it is recommended 6;, for It is easy to construct untimed deviations with this behavior, but timed deviations cannot have this behavior, because timed deviation cannot know the recommendation B while still decision point A.
{1, 2}.
A.5 RELATION BETWEEN OUR REPRESENTATION AND THAT OF FARINA & PIPIS (2023)
Our paper and the paper of Farina & Pipis (2023) both take similar approaches to minimizing L regret: both papers use the framework of Gordon et al. (2008) reduce the problem minimizing external regret over the set of linear maps, and then derive a system of constraints for the set of matrices A E IR ΣxE that represent linear maps. The representations are, however, significantly different:
The representation Farina & Pipis (2023) cannot be expressed in scaled extensions. As such, that paper was forced resort to less efficient regret minimization techniques. This difference is what allows us to improve upon their results.
As technical note, the representation of Farina & Pipis (2023) will always result in matrix A E IR XxΣ where the columns of A corresponding to nonterminal sequences are
7 Heere, by two sets of deviations deviations,coinciding coinciding, we mean that the same set of deviation functions ő X - co.2 X'
available both deviators.
13

---

Published as a conference paper at ICLR 2024
filled with zeros. While this is without loss of generality due the constraints defining the sequence form, it sometimes results in intuitively-strane strangg representations: for example, their representation does not represent the identity map Id X' + X' the identity matrix I E REXE, whereas our representation will.
While our representation generalizes to arbitrary pairs of sequence- form polytopes accord- ing to Appendix A.2, theirs generalizes even further, to functions Φ : y - X' as long as y is sequence form and X has some small set of linear constraints (not necessarily sequence form) describing it. We likely cannot hope for our representation to generalize as far: our proof of equivalence relies fundamentally on both input and output being sequence-form strategy sets.
A.6 UNTIMED COMMUNICATION EQUILIBRIA
The UTC deviations, like all sets of deviations, give rise notion of equilibrium. We define:
Definition A.4. In an extensive-fore game, an untimed private communication equilibrium is a correlated profile that is ( where 4; is player i's set of UTC deviations.
We add the word "private" here the name to emphasize the fact that the mediator must have a separate interaction with each player-that is, the mediator cannot use its interactions with one player to inform how it gives recommendations to another player. This is enforced by the fact that the equilibrium is correlated profile. See Footnote regarding why this distinction is important.
Defining untimed communication equilibrium without such a privacy restriction seems to a subtle task, and is orthogonal to and beyond the scope of the present work. However, we will make few informal comments here. Untimed communication equilibria (without the privacy constraint) are difficult to define in way that does not quickly collapse to the regular notion of communication equilibrium. In games with three or more players, the mediator is always guaranteed that two of the players have not deviated, and those two players will have messages synchronized with the game clock. Therefore, under reasonable assumptions on how often each player makes moves, the mediator will immediately know if the deviating player sending out-of-order messages, and this concept would reduce immediately to the regular communication equilibrium. It is entirely unclear how to define a notion of untimed (non-prite privatee communication equilibrium that does exhibit such a collapse.
In two-player games, is possible that there is reasonable way to define untimed communication equilibria. The above collapse does not apply, because the mediator will not know which player is the one sending out-of-timing messages. However, this definition would still be rather subtle- for example, when do the out-of-order messages arrive to the mediator, relative to the other player's messages? We leave these issues to future work.
A.7 REVELATION PRINCIPLE FOR UNTIMED PRIVATE COMMNUNICATIOS EQUILIBRIUM
All the other notions of equilibrium involving mediator, discussed in Section 3, obey a revelation principle, which we now discuss using the example of normal-fome correlated equilibrium. The original definition of Aumann (1974) did not initially refer to correlated profiles; instead, the defi- nition posited an arbitrary joint distribution of correlated signals. In this section, we break down the notions of equilibrium that we have defined so far, and reconstruct them from the perspective of this arbitrary set of signals, and show that the resulting notions are cquivalent for our notion of untimed private communication equilibrium.
We start with NFCE as an illustrative example. Let स E ASS X X Sn), where S, an arbitrary set of signals for player i. The mediator samples joint signal (si,..., Sn) и,, and then each player privately observes its own signal s; and selects (possibly at random) a strategy x E X. An NFCE is then tuple (T,, di...., @n), where S - co X' is the function by which player i selects its strategy given a signal, such that each player's choice of oi maximizes that player's utility given n and the other éis, that is,
(s)) u.(o)(s)), (_. (S
E
14

---

Published as a conference paper at ICLR 2024
for every player i and other possible function 6 S; + co An NFCE is direct if S; X; and 0i : X - co X; is the identity function. The revelation principle states that every NFCE is outcome-equivalent to a direct equilibrium.
To generalize this to extensive-form and communication equilibria (timed and untimed), we follow the approach of Myerson (1986); Forges (1986). In their approach, a mediator of player i is map M, : S. St (where S is the set of all sequences over S, of length < H. and H is some large but finite number (at least the depth of player i's decision problem.) that determines what message the mediator sends in reply to a player whose message history with the mediator is a finite sequence s {. We will assume that S; at least is expressive enough to send an empty message, a decision point, or an observation point: S, 2 T. E, LI {-). The three notions of extensive-fore form correlated equilibrium, private communication equilibrium, and untimed private communication equilibrium will differ in how the player interacts with the mediator. We will describe player i's interactions by set of functions Φ; S (co X. where M; is a set of mediators: each function di &; represents the player i choosing how it interacts with the mediator and how it uses those interactions to inform its choices of action. Then, as before, equilibrium is a tuple (IT, $1...., ,,)) where & E AM x ...MM)) ) is distribution over mediators and no player i can profit by switching to a different df E t; The three notions above then differ in the choice of set Φ2.
Extensive-fomn correlated equilibria equilibria where T. is the set of interactions in which the player, upon reaching a decision point j. must send that decision point to the mediator.
Private communication equilibria are equilibria where o; is the set of interactions in which the player, upon reaching a decision point j. must send a single message (which may or may not be the decision point j) to the mediator.
Untimed private communication equilibria are equilibria where Φ; is the set of interactions in which the player, upon reaching a decision point j, may send any number of messages to the mediator.
The direct mediator M, for a pure strategy x; E Xr is the mediator who acts by sending the recommendation at infoset j if and only if the message history matches the Ø; - path, otherwise I. Formally, M (s) a (z.;. j) if s = (f(1), a1)), ,(2) ......) is the path to j in player i's decision tree, and I. otherwise. We write M == (M. x, E X.} for the set of direct mediators on X,
Notice that, for direct M,, the sets of interactions valid for each of the three equilibrium notions reduces to the sets of deviations defined in Section 3. Analogous to the NFCE case, an equilibrium (IT, of ... 27)) (in any of the previous three notions) is called direct if is distribution over direct mediators, and of is the map M + x; (which is the analogy of the identity map). We are now ready to state the revelation principle for these notions.
Theorem A.5 (Revelation principle: for EFCE, proven by von Stengel & Forges (2008); for com- munication equilibrium, proven by Myerson (1986); Forges (1986) and refined by Zhang & Sand- holm (2022)). For EFCE and (private) communication equilibrium, every equilibrium outcome- equivalent to a direct equilibrium.
Our main result in this section is that the same holds for untimed private communication equilibrium:
Theorem A.6 (Revelation principle for untimed private communication equilibrium). Every un- timed private communication equilibrium is outcome-equivalen to direct untimed private commu- nication equilibrium.
Proof. Let (I, oi,,.. 2n) be some (possibly indirect) equilibrium. Observe that we can view the mediator as holding a strategy y E Vi, where Y/ is the decision problem whose nodes correspond sequences s E S.H.. i.e., to message histories. Notice that, by construction of the message set S, ) contains a copy of each X; within it, and that direct mediators M, constrain themselves to states within this copy of X; by terminating the interaction (sending L forever) if the history of communication fails to match state in player i's decision problem. We will use this fact later.
By outcome-equivalen,, we mean that the distribution over terminal nodes in the extensive-form game is the same both equilibria.
15

---

Published as a conference paper at ICLR 2024
By Theorem A.2, each player's strategy set @ is the set of linear maps 3; - co X, Now, sider the direct profile (T" ...... ........ .,,,) where x² E A(Mi x ... x M;) is given by sampling (M....., M,) n, sampling E; E X; from any distribution whose expectation o; (M;) for every player i, and finally outputting (MP) :.... M Clearly, this profile is outcome-equivalen to the original profile, so it only remains to show that it is also equilibrium. Consider any deviation of of player from the direct equilibrium.
We proceed by contrapositive. Suppose that ( .i....,, is not an equilibrium: player has profitable deviation o; Since a direct mediator is constrained, as above, to act within player i's decision problem, & can be expressed as UTC deviation of X;
X, Since all UTC deviations are linear, of is itself linear, and can also be extended to a function o' co - co Xg Now let 4/s : Di - Co K be given by 1i: df o di, and observe that, since the composition of linear functions is linear, the is linear map, that is, th 4; Moreover, by construction, the profiles
(x, 1h4, )-1) and (x", 6/ >=;) must induce the same outcome distributions- and therefore, 4) is profitable deviation against the original equilibrium (I,, $1 01...., Un))
This result justifies the definitions of equilibrium we have been using throughout the paper before reaching this point. We remark that, although the proof is usually not difficult, the revelation princi- ple is not given or automatic fact that can be assumed without proof: there are other settings where it fails, such as when the deviator's 's set of allowable messages depends its true type in nontrivial manner (e.g., Forges & Koessler, 2005; Kephart & Conitzer, 2021).
B PREVIOUS -- D-REGRET ALGORITHMS
Citation
Deviation set (+)
Regret bound
Complexity
CFR?
Zinkevich et al. (2007)
External
O(dvT)
O(d)
Yes
Farina et al. (2022b)
External
O(vdT)
O
No
Farina et al. (2022a)
Trigger
O(dvT)
FP Yes
Fujii (2023)*
Communication
((VdT)
FP
No
Farina & Pipis (2023)
Linear
O(dvT)
QP
No
This paper
Linear
(T)
FP
Yes
Peng Rubinstein (2023)
Swap
T Ō logd log
Oddlgg T)
Yes
Dagan et al. (2023)
Table 4: Comparison of &-regret minimizing algorithms for extensive-form games. Complexity is per-iteration. "QP" and "FP" denote solving quadratic program and fixed-point problem, respec- tively. CFR? denotes whether the algorithm based on the CFR framework. which important in practice because, as stated in the body, CFR-based methods are the best practical regret minimizers. 4: The algorithm and analysis Fujii (2023) only applies to single-step Bayesian games, not gen- eral extensive-form games.
Table 4 summarizes the various d-regret algorithms known for extensive-form games. As suggested by the table, the main improvements of our algorithm compared to that of Farina & Pipis (2023) in the same setting are (1) the faster per-iteration complexity (fixed-poin) computation versus quadratic program), and (2) the enabling of the use of the CFR framework, which leads to faster practical per- formance. The remarkable result of Peng & Rubinstein (2023) and Dagan et al. (2023) is very recent and in parallel with our work, and shows that there exists a PTAS for NFCE (with runtime roughly d ((1/e)). It remains open problem whether there exists swap-regret minimizing algo- rithm whose regret is poly(d) T for some c < 1, which would imply an FPTAS for NFCE in extensive-form games.
16

---

Published as a conference paper at ICLR 2024
A
B
02
83
2
C1
Figure 5: Another example. The notation is shared with Figure 1. In this example, à 's strategy set equivalent to a simplex, so the linear deviations coincide with its swap deviations. As such, we will not bother to depict the UTC decision problem matrices.
C ANOTHER EXAMPLE
In this section, we provide another example of untimed communication deviations, especially as they differ from (timed) communication deviations. Consider the game in Figure 5. Consider the correlated profile that mixes uniformly between the pure profiles (a1, b1, C1) and (a1, b2, C2). This is communication equilibrium: cannot profitably deviate, because its utility in the B subgame always O, and it chooses to disobey the recommendation a its expected utility will be also O, because it cannot ask for another recommendation before choosing what action to play. However, has the following profitable UTC deviation: ask for the recommendation at B before deciding which action play at A. If the recommendation is b1, play a2: if the recommendation is b2, play ag.
Notice that, this example, 's decision problem is essentially that normal-form game; there- fore, its linear deviations coincide with its swap deviations. However, due to the timing restriction on communication deviations, the communication deviations are more restricted than the swap de- viations.
This example also shows that the untimed private communication equilibria (see Appendix A.6) are nutcome-equivalet the timed private communication equilibria: in this game, every corre- lated profile is a distribution over terminal nodes (outcomes), so the fact that there exists a private communication equilibrium with profitable UTC deviation is enough to disprove outcome equiva- lence.
D PROOF OF THEOREM 4.1
Theorem 4.1. The UTC deviations are precisely the linear deviations. That is, Purc PLINN-
We start with a lemma.
Lemma D.1. Let f X Rzo be linear map, where X is sequence-form strategy space. Then there exists a unique vector c such that:
1. [(x)) c x for all X,
2. has all nonnegative entries, and
3. for every decision point there is at least one action a such that e(ja) = 0.
Proof. Let f(x) c. x. where e is currently arbitrary (i.e., it may not satisfy (2) and (3)). Then, for each decision point j in bottom-up order, let cj) == min, c(ja). Subtract c* (j) from c(ja) for every action a, and add c* (j) to c(p,). Since satisfies the constraint æ(p,) E, x(ja), this does not change the validity of c, and by the end of the algorithm, (2) and (3) will be satisfied except possibly that c(2) O. To see that c(Ø) > 0, let be the pure strategy that plays the zeroing action a specified by (3) at every decision point. Then, by construction, x = c(Ø) 2 0. To see that is unique, note that there
choice any step in the above process: the transformation
17

---

Published as a conference paper at ICLR 2024
performed at each decision point is the only way satisfy conditions (2) and (3) without changing the linear map.
Now let A represent a linear map X' - X, where the rows of A are represented according to the above lemma. That is, A has all nonnegative entries, and moreover for any j E J and a E, we have (a, ja) = 0 for some action It remains only to show:
Lemma D.2. There exists matrix B such that (A, B) satisfies all constraints in the constraint system (2).
Proof. A(2,0) = and a( 0 for ø * Ø follow from the fact that (A))( 1 for all æ, that is A X + [0, 1] is the identically-1 function, which by Lemma D.I has the above form. We are thus left with the main constraint,
O)) + B(j.pa)= = Σ o) + Σ B(i.J)
(3)
aEA;
JEC,
for every (j,ō) E E.
Define B and another matrix B E R.XE follows:
B(j,ō) = Σ A(ja,5) + DBC.J. Alj.
aεA,
JEC,
B(i.)) min B(j.ja) aεAz
To that B satisfies all the constraints (3), let be any fully-mixed strategy, and I be any decision point. Then:
0= Σ
(ja) (p))
aεd,
Σ (
Σ
A(ja, - Ap)
dEH
aEA;
Σ KER
B(j,ō)
Σ B
JECa
Σ
a(ja) (
aEAs
> Σ B(i.))
Σ x(Ja) x(p7) =0
Thus, the incquality must in fact be an equality, and since all its terms are nonnegative, we thus have B(j.ja) B(j.3) for all a E Ay. so the constraints (3) are satisfied by definition of B.
To that B 0, suppose not. Let (j,J) be last (i.e., farthest from the root, with respect the ordering of the DAG) pair for which B(j.]) < O. Then, for any action E Az. we have
A(pj. + B(j.))
Σ A(ja,Ja) + Σ B(j.)) aEA;
JEE
where the inequality because (j-J) is farthest from the root so all the terms on the right-hand side nonnegative. Therefore, A(p,. O. But this should hold for every action ã, contradicting the construction of A, which includes the condition that there must exist a for which A (pp..ja) 0.
18

---

Published as a conference paper at ICLR 2024
E ADDITIONAL PLOTS
Below we present a variant the plots in Figure 3, in which time (and not iterations) is reported on the x-axis.
4-Player Kuhn poker
Ridesharing game
Average linear-s swap regret
10"
Average linear- -wap regret
10
10-1
10
10
10
10-3
10-3
Farina & Pipis (2023)
10
Farina & Pipis (2023)
10"
UTC dynamics (this paper)
UTC dynamics (this paper)
10-5
10
10
10
10²
10a
10
10-1
10
10a
Time [s]
Time [s]
3- 3-Player Ledue poker
Sheriff of Nottingham
Average linear- linear-swapp swap regret
Average linear-s linear-swap swap regret
10"
10
10-1
10
10-2
10-1
Farina & Pipis (2023)
Farina & Pipis (2023)
10-3
UTC dynamics (this paper)
10-2
UTC dynamics (this paper)
100
10
10a
10
10a
10
10
10a
103
10
Time [s]
Time [s]
Figure 6: Experimental comparison between our dynamics and those of Farina Pipis (2023) for approximating linear correlated equilibrium in extensive-form games. Each algorithm
for
a maximum of 1 ,00 iterations or 6 hours, whichever was hit first. Runs that were terminated due the time limit are marked with square Compared Figure 3, the plots in this figure have time on the x-axis.
19


Reviews:
[{"review_id": "94rzKulPoP", "reviewer": "Reviewer_xFFq", "summary": "This paper studies regret minimization for extensive-form games. In detail, the authors established a relationship between the linear deviation and the proposed UTC deviation. Therefore, any algorithms which are used to minimize the UTC regret is equal to minimize the linear swap regret. The authors showed sublinear regret bound and experiment results to suggest that the proposed algorithms are the state of the art.", "questions": "See weaknesses section.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper is technically sound, and the experiment results are also comprehensive.", "weaknesses": "The presentation of this paper can be further improved. In order to further demonstrate the contribution of this work, the authors can have a table which records all existing algorithms for linear-swap regret, as well as their computational complexity. Right now it is a little bit hard for the readers to even identify which of the algorithms (UTC-based CFR or algorithms from Farina and Pipis) are better. Another suggestion is the presentation of Section 5. I understand that the authors want to use the example to demonstrate that UTC is more expressive than communication deviation. However, I spend several hours and still can not get an intuitive understanding about why such a claim hold. For instance, why A and B are 'irrelevant' according to footnote 6? I suggest the authors rewrite Section 5 by reorganizing the Figure 1 into several smaller figures with shorter captions. That would make the demonstration much clearer. \n\nFollowing the above comment, I can not tell what is the key contribution of this work. The main theorem (Theorem 4.1) suggests that the deviation sets $\\Phi_{lin}$ and $\\Phi_{UTC}$ are identical, and later the authors suggested CFR in Zhang et al. can be used to solve UTC, which can be further used to solve linear deviation. How the exactly can CFR be applied to linear deviation? A reduction process is expected, similar to what has been done in Theorem 2.3 (an existing result). Meanwhile, why people are interested in forming the equivalence between UTC and linear deviation but not some other types of game and linear deviation? Last, the authors suggested that the per-iteration complexity of CFR depends on the complexity of computing a fixed point iteration problem. How should we compare such a complexity with previous approaches, like Farina & Pipis (2023)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uT3HY1HkG8", "reviewer": "Reviewer_JkDA", "summary": "This paper studies the computation of a relaxed version of correlated equilibria, known as linear correlated equilibria. The authors take a regret minimization perspective and design their algorithm for computing linear correlated equilibria by designing algorithms that minimize linear-swap regret. They demonstrate an equivalence between linear deviation and a generalization of communication deviations, where the deviator can send untimed queries to the mediator. Hence, minimizing linear swap-regret can be done via minimizing regret defined under such deviations with untimed communications. Invoking a previous result on the latter problem then gives a linear-swap regret minimizer. Experiments based on several types of games are further conducted, which demonstrate significant improvement of the proposed algorithm compared with existing ones.", "questions": "- Could you provide some intuition why deviations in EFGs need to be defined as interactions betweem a mediate and a deviator?\n\n- There seem to be some typos in Theorem 2.3. On the second line, \"where x^{(t)} \\in X ... \" Do you mean x^{(t)} \\in \\Phi instead of X? The utility vector u^{(t)} in this sentence also seems to come from nowhere. And when you say \"deterministic\" external regret, the notion of deterministic seems undefined.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is overall clean and rigorously written. The problem studied is interesting and results presented look sound technically. The empirical results also provide significant improvement in comparison to existing approaches.", "weaknesses": "Some parts of the paper seems to lack necessary details, making them quite hard to follow. In particular, the communication deviations and the UTC decision problem in Section 3 are introduced in a very abstract language. For readers not familiar with previous work on communication equilibrium, it would be quite hard to understand why these concepts are defined in described ways. For example, when communication deviations are introduced, it is said that the deviator will maintain a state with the mediator, but there is no explanation about why there needs to be a state. The introduction of the interaction between the mediator and the deviator also lacks intuitions. Overall, while I find the previous sections clear and informative, Section 3 seems to appear a bit abruptly. It might be helpful to provide some more details about comminication equilibrium, or introduce the concepts in this section along with the example in Section 5 (I think I understand them better after reading the example). \n\nSome typos: \n\n- In Section 5, the sentence \"must immediately its first mediator query\" reads problematic.\n\n- In the paragraph above Section 7, \"this significant(ly) improves\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9XrtFhIwS3", "reviewer": "Reviewer_EjBw", "summary": "This paper makes a conceptual step towards the design of swap regret minimizing algorithms. In particular, inspired by the $\\Phi$-regret framework they introduce a set of deviation mappings called untimed communication (UTC) deviations that are shown to be equivalent to the set of linear deviations. These linear deviations have been recently shown to be useful in obtaining sublinear regret in polynomial time for sequential games. Following that, the authors show that UTC deviations are expressible in terms of scaled extensions, which allows them to apply CFR to learn linear correlated equilibrium much faster than the indicative previous work of Farina and Pipis. Finally, several experiments are shown that corroborate the theory and show fast convergence to linear correlated equilibria.", "questions": "- If a generic definition of untimed communication equilibrium cannot be derived, are there relaxations thereof that can be derived in your framework?\n- What is the next reasonable step beyond linear deviations in the search for swap regret minimization?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper is well written and the structure is clear. Moreover, showing a connection between linear deviations and communication deviations draws a novel parallel with standard sequential deviation sets. This opens up a wealth of potential untimed deviation mappings (along with accompanying equilibrium concepts) to be studied in future. The example presented also gives an intuitive understanding of the deviation and how it can be useful. Finally, the empirical performance of the CFR algorithm instantiated with regret matching+ greatly speeds up convergence to the linear correlated equilibria.", "weaknesses": "While showing a connection between linear and communication deviations is a very neat result, the paper does not seem to be very substantial in otherwise exploring the full potential of this new class of deviations. The ability to obtain faster convergence to linear correlated equilibria is welcomed, but relies on an existing algorithm. In that sense, the major contribution of this work is introducing UTC as a part of the framework for which fast convergence to equilibria can be obtained. Other than that, none of the other results shown seem technically significant. To alleviate this, more discussion or results about the nature of untimed communication equilibria would be helpful, should space allow (perhaps a section about connections to standard communication equilibria, which has been written in the appendix already).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QbL8VDs6UF", "reviewer": "Reviewer_YUk3", "summary": "This paper introduces an extension of communication deviation, termed UTC deviations, and theoretically proves that UTC deviations are equivalent to linear deviations in the context of online convex optimization. Given that UTC deviations can be represented using DAG decision problems, regret minimization algorithms like CFR, when applied to these decision problems, can also be utilized to minimize linear swap regrets in online convex optimization scenarios. Building upon prior findings, employing CFR as a $\\Phi_{LIN}$-regret minimizer not only promises the same $O(\\sqrt{T}d^2)$ upper bound but also offers superior computational efficiency by avoiding the need for an expensive projection. Empirical evaluations further demonstrate that CFR achieves reduced average regrets and requires significantly less runtime.", "questions": "- Can you provide some explanations for why CFR achieves a better regret than the algorithm in Farina & Pipis (2023)? Figure 2 is presented without accompanying discussion.\n- Since both CFR and Farina & Pipis (2023) offer an upper bound of $O(\\sqrt{T}d^2)$, is it possible to demonstrate that this is also the lower bound?\n- Could you elaborate on how to employ the algorithm from Cohen et al. (2021) to achieve $\\tilde{O}(d^w)$ complexity? What is the linear program that must be solved in formal? This addition would make the paper easier to read.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 1, "contribution": 3, "strengths": "- The paper bridges decision problems and the online learning problem by proving the equivalence of UTC deviations and linear deviations. This enables the use of algorithms, such as CFR, in online optimization problems to minimize linear swap regrets.\n- The paper provides an intuitive example of a UTC deviation and demonstrates that UTC deviations do not necessarily have to be communication deviations\n- The empirical analysis is very persuasive to me. The experimental settings and results are explained clearly.", "weaknesses": "- There is no improvement in regrets when using CFR based on UTC dynamics. Although Figure 2 shows that the regret of CFR outperforms that of Farina & Pipis (2023), the paper does not provide an explanation for this.\n- The paper provides only an informal proof of why UTC dynamics have better computational efficiency than Farina & Pipis (2023) in Section 1. A more formal discussion is required and should be placed in Section 6, rather than in the introduction.\n- Some notations, such as ${\\text co}{\\mathcal X}$, are used before being defined.\n- I cannot locate a formal definition of linear deviations. Given its frequent use in this paper, at the very least, an explanation is necessary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)