Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games
Authors: Gabriele Farina
Charilaos Pipis
Venue: NeurIPS 2023 poster (2023)
Keywords: online learning
algorithmic game theory
extensive form games
correlated equilibrium
swap regret
linear swap regret
TL;DR: We show that it is possible to construct polynomial-time no-regret dynamics with respect to all linear strategy transformations in extensive-form games, thus giving an efficient algorithm converging to a stronger notion of sequential rationality.

Abstract: No-regret learners seek to minimize the difference between the loss they cumulated through the actions they played, and the loss they would have cumulated in hindsight had they consistently modified their behavior according to some strategy transformation function. The size of the set of transformations considered by the learner determines a natural notion of rationality. As the set of transformations each learner considers grows, the strategies played by the learners recover more complex game-theoretic equilibria, including correlated 
equilibria in normal-form games and extensive-form correlated equilibria in extensive-form games. At the extreme, a no-swap-regret agent is one that minimizes regret against the set of all functions from the set of strategies to itself. While it is known that the no-swap-regret condition can be attained efficiently in nonsequential (normal-form) games, understanding what is the strongest notion of rationality that can be attained efficiently in the worst case in sequential (extensive-form) games is a longstanding open problem. In this paper we provide a positive result, by showing that it is possible, in any sequential game, to retain polynomial-time (in the game tree size) iterations while achieving sublinear regret with respect to all linear transformations of the mixed strategy space, a notion called no-linear-swap regret. This notion of hindsight rationality is as strong as no-swap-regret in nonsequential games, and stronger than no-trigger-regret in sequential games—thereby proving the existence of a subset of extensive-form correlated equilibria robust to linear deviations, which we call linear-deviation correlated equilibria, that can be approached efficiently.

Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Informatio Sequential Games
Gabriele Farina MIT gfarina@mit. edu
Charilaos Pipis
MIT chpipis@mit.cm edu
Abstract
No-regret learners seek to minimize the difference between the loss they cumu- lated through the actions they played, and the loss they would have cumulated in hindsight had they consistently modified their behavior according to some strategy transformation function. The size of the set of transformations considered by the learner determines a natural notion of rationality. As the set of transformations each learner considers grows, the strategies played by the learners recover more complex game-theoretic equilibria, including correlated equilibria in normal-form games and extensive- form correlated equilibria in extensive- games. At the extreme, a no-swap-regrel agent is one that minimizes regret against the set of all functions from the set of strategies itself. While it is known that the no- swap-regret condition can be attained efficiently in nonsequential inormal-form games, understanding what is the strongest notion of rationality that can be attained efficiently in the worst case in sequential (extensive- open problem. In this paper we provide a positive result, by showing that possible, in any sequential game, to retain polynomial-ting time (in the game tree size) iterations while achieving sublinear regret with respect all linear transformations of the mixed strategy space, notion called no-lineas no-linear-swap regret. This notion of hindsight rationality as strong as no-swap-regret in nonsequential games, and stronger than no-trigger-regret in sequential games ghees-thereby proving the existence a subset extensive- correlated equilibria robust to linear deviations, which we call linear-deviation correlated equilibria, that can be approached efficiently.
games is a longstanding
1 Introduction
The framework of regret minimization provides algorithms that players can use to gradually improve their strategies in repeated game, enabling learning strong strategies even when facing unknown and potentially adversarial opponents. One of the appealing properties of no-regret learning algorithms that they are uncoupled, meaning that each player refines their strategy based on their own payoff function, and on other players' strategies, but not the payoff functions of other players. Nonetheless, despite their uncoupled nature and focus on local optimization of each player's utility, it is of the most celebrated results in the theory of learning in games that in many cases, when all players are learning using these algorithms, the empirical play recovers appropriate notions of equilibrium global notion of game-theoree theoretic optimality. Strategies constructed via no-regret learning algorithms (or approximations thereof) have been key components in constructing human- level and even superhuman Al agents in variety of adversarial games, including Poker [Moravčík et al., 2017, Brown and Sandholm, 2018, 2019], Stratego [Perolat et al., 2022], and Diplomacy [Bakhtin et al., 2023).
In regret minimization, each learning agent seeks to minimize the difference between the loss (opposite of reward) they accumulated through the actions they played, and the loss they would have
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

accumulated in hindsight had they consistently modified their behavior according to some strategy transformation function. The size of the set of transformation functions considered by the learning agent determines a natural notion of rationality of the agent. Already when the agents seeks to learn strategies that cumulate low regret against constant strategy transformations only-a notion of regret called external regret-the average play of the agents converges to a Nash equilibrium in two-player constant-sum games, and to a coarse correlated equilibrium in general-sum multiplayer games. As the sets of transformations the each agent considers grows, more complex equilibria can be achieved, including correlated equilibria in normal-form games (Foster and Vohra [1997], Fudenberg and Levine [1995, 1999], Hart and Mas- Calell [2000, 2001]; see also the monograph by Fudenberg and Levine [1998]) and extensive-fom correlated equilibria in extensive- forenssie-fommeeeee games [Farina et al.. 2022]. At the extreme, a maximally hindsight- rational agent is one that minimizes regret against the set of all functions from the strategy space to itself (aka. swap regret). While it is known that maximum hindsight rationality can be attained efficiently in nonsequential (normal-form) games [Stoltz, and Lugosi, 2007, Blum and Mansour, 2007], it is a major open problem to determine whether the same applies sequential (i.e., extensive-form) games, and more generally what is the strongest notion of rationality that can be attained efficiently in the worst case in the latter setting.
In this paper, we provide a positive result in that direction, by showing that hindsight rationality can be achieved efficiently in general imperfect-infor information extensive-fom games when one restricts to the set of all linear transformations of the mixed strategy space notion called linear-sway swaa regret, and that coincides with swap regret in normal-fome games. In order to establish the result, we introduce several intermediate results related to the geometry of sequence- forme strategies in extensive-fore games. In particular, a crucial result is given in Theorem 3.1, which shows that the set of linear functions Me-p from the sequence-fore form strategy set Q of player in an extensive-form game to generic convex polytope P can be captured using only polynomially many linear constraints in the size of the game tree and the number of linear constraints that define P. Applying the result the special case p = Q, we are then able to conclude that the the polytope of linear transformations M from the sequence-form strategy set itself can be captured by polynomially many linear constraints in the size of the game tree, and the norm of any element is polynomially bounded. The polynomial characterization and bound for Ma+ is used in conjunction with an idea of Gordon et al. [2008] to construct no-linear-swe swap-regret minimizer for the set of strategies Q starting from two primitives: i) a no-external-regee regret algorithm for the set of transformations Mo- and ii) an algorithm to compute fixed point strategy for any transformation in Me- In both cases, the polynomial representation of Mo- established through Theorem 3.1 plays a fundamental role, allows, on the one hand, to satisfy requirement ii) using linear programming. On the other hand, it enables us to construct no-external-regree algorithm that outputs transformations in Mo- with polynomial-time iterations, by leveraging the known properties of online projected gradient descent, polytopes.
exploiting the tractability of projecting onto bllynommallyy-epreeeentta
Finally, in the last section of the paper we turn our attention away from hindsight rationality to focus instead on the properties of the equilibria that our no-linear-swap.. in extensive-form games. The average play of no-linear-swap-ree swap-rr-waa-rrgree dynamics recover players converges to set of equilibria that we coin linear-deviation correlated equilibria (LCEs)) LCEs form a superset of correlated equilibria and a subset of extensive- form correlated equilibria in extensive-forn games. In Section we show that these inclusions are in general strict, and provide additional results about the complexity of computing mexiare- LCE.
Related work As mentioned in the introduction, the existence of uncoupled no-regret dynamics leading to correlated equilibrium (CE) in multiplayer normal-form games is a celebrated result dating back at least the work by Foster and Vohra [1997]. That work inspired researchers to seek uncoupled learning procedures in other settings as well. For example, Stoltz and Lugosi [2007] studies learning dynamics leading to CE in games with an infinite (but compact) action set, while Kakade et al. [2003] focuses on graphical games. In more recent years, growing effort has been spent towards understanding the relationships between no-regret learning and equilibria in imperfect- information extensive-form games, the settings on which we focus. Extensive-fomm games pose additional challenges when compared to normal-form games, due to their sequential nature and presence of imperfect information. While efficient no-external-regret learning dynamics for extensive- form games are known (including the popular CFR algorithm [Zinkevich et al., 2008]), as of today not much is known about no-swap-regret and the complexity of learning CE in extensive- form games.
2

---

In recent work, Anagnostides et al. [2023] construct trigger- dynamics that converge to EFCE at a rate of ( log T whereas our regret dynamics converge to linear-deviation correlated equilibria at slower rate of O While the aforementioned paper proposes general methodology that applies to CEs in normal-form games and EFCE/EFCCE sequential games, the authors' construction fundamentally relies on being able to express the fixed points computed by the algorithm as (linear combinations of) rational functions with positive coefficients of the deviation matrices. For EFCE and EFCCE this fundamentally follows from the fact that the fixed points can be computed inductively, solving for stationary distributions of local Markov chains at each decision point. The no-linear-swap regret algorithm proposed in our paper does not offer such local characterization of the fixed point and thus, we cannot immediately transfer the improved regret bounds to our case.
The closest notion to CE that is known to be efficiently computable in extensive-form games is extensive-form correlated equilibrium (EFCE) [von Stengel and Forges, 2008, Huang and von Stengel, 2008]. The question of whether the set of EFCE could be approached via uncoupled no- regret dynamics with polynomial-time iterations settled in the positive [Farina et al., 2022, Celli et al., 2020]. In particular, Farina et al. [2022] show that EFCE arises from the average play of no-trigger-regre algorithms, where trigger deviations are a particular subset of linear transformations of the sequence-fon form strategy polytope Q of each player. Since this paper focuses on learning dynamics that guarantee sublinear regret with respect to any linear transformation of Q, it follows immediately that the dynamics presented in this paper recover EFCE as special case.
the size of the extensive-form games was recently
The concept of linear-swap-regre minimization has been considered before in the context of Bayesian games. Mansour et al. [2022] study a setting where a no-regret learner competes in two-player Bayesian game with a rational utility maximizer, that is a strictly more powerful opponent than a learner. Under this setting, it can be shown that in every round the optimizer is guaranteed to obtain at least the Bayesian Stackelberg value of the game. Then they proceed to prove that minimizing linear-swap regret is necessary if want to cap the optimizer's 's performance at the Stackelberg value, while minimizing polytope-swap regret (a generalization of swap regret for Bayesian games, and strictly stronger than linear-swap) is sufficient to cap the optimizer's performance. Hence, these results highlight the importance of developing learning algorithms under stronger notions of rationality, as is our aim in this paper. Furthermore, these results provide evidence that constructing a no-linear swap regret learner, as is our goal here, can present benefits when compared to other less rational learners. In a concurrent paper, Fujii [2023] defines the notion of untruthful swap regret for Bayesian games and proves that, for Bayesian games, it is equivalent to the linear-swap regret which is of interest in our paper.
Bayesian games can be considered as special case of extensive-form games, where a chance node initially selects one of the possible types θ for each player. Thus, our algorithm minimizing linear- swap regret in extensive-form games also minimizes linear-swap regret in Bayesian games. However, we remark that our regret bound depends polynomially on the number of player types |e] as they are part of the game tree representation, while Fujii [2023] has devised an algorithm for Bayesian games, whose regret only depends on log (+].
Finally, we also mention that nonlinear deviations have been explored in extensive-form games, though we are not aware of notable large sets for which polynomial be devised. Specifically, we point to the work by Morrill et al. [2021], which defines the notion of "behavioral deviations". These deviations are nonlinear with respect to the sequence-fore tion of strategies in extensive-form games. The authors categorize several known or novel types of restricted hehavioral deviations into a Deviation I Landscape that highlights the relations between them. Even though both the linear deviations, we consider in this paper, and the behavioral deviations seem to constitute rich measures of rationality, none of them contains the other and thus, linear deviations do not fit into the Deviation Landscape of Morrill et al. [2021] (see also Remark E.2).
no-regret dynamics can
representa-
2 Preliminaries
We recall the standard model of extensive-form games, well as the framework of learning in games.
3

---

2.1 Extensive-Form Games
While normal-form games (NFGs) correspond to nonsequential interactions, such as Rock-Paper Scissors, where players simultaneously pick one action and then receive a payoff based what others picked, extensive-form games (EFGs) model games that are played on a game tree. They capture both sequential and simultancous moves, well as private information and are therefore very general and expressive model of games, capturing chess, go, poker, sequential auctions, and many other settings as well. We now recall basic properties and notation for EFGs.
Game tree In an n-player extensive-form game, each node in the game tree is associated with exactly one player from the set {1, (I...., n. U {c). where the special player c-called the chance player-is used to model random stochastic outcomes, such as rolling a die or drawing cards from deck. Edges leaving from a node represent actions that player can take at that node. To model private information, the game tree is supplemented with an information partition, defined as a partition of nodes into sets called information sets. Each node belongs to exactly information set is a nonempty set of tree nodes for the same Player i. An information set for Player i denotes collection of nodes that Player i cannot distinguish among, given what she has observed so far. (We remark that all nodes in a same information set must have the same set of available actions, or the player would distinguish the nodes). The of all information sets of Player is denoted Ji- In this paper, we will only consider perfect-recall games, that is, games in which the information sets are arranged in accordance with the fact that no player forgets what the player knew earlier.
information set, and each
Sequence-form strategies Since nodes belonging to the same information set for a player are indistinguishable to that player, the player must play the same strategy each of the nodes. Hence, strategy for a player is exactly a mapping from an information set to a distribution over actions. In other words, it is the information sets, and not the game tree nodes, that capture the decision points of the player. We can then represent a strategy for a generic player as a vector indexed by each valid information set-action pair (j. a). Any such valid pair is called sequence of the player; the set of all sequences is denoted as Σ, == ((jaa) j E J. a E A,} U ( where the special element @ is called empry sequence. Given information set j E To, defined as the last pair (j, a) E Σ, encountered on the path from the root to any node v E j; if no such pair exists we let P. Ø. Finally, we denote by C, the children of sequence the information sets j E T, for which Pj = a. Sequences a for which C, is an empty set are called terminal; the set of all terminal sequences is denoted E
denote by Pj the parent sequence of j.
Σ,, defined as
Example 2.1. Consider the tree-form decision process faced by Player 1 in the small game of Figure/ (Left). The decision process has four decision nodes J1 {A, B, C, D} and nine sequences including the empty sequence Ø. For decision node D, the parent sequence is pD = A2; B and C
is pB A1; for A it the empty sequence PA 2.
Sequence-form constraints:
x [ 1,
x A1
+ x A2 = x 10
x B3
+ x B4
x A1
2: C5
+ C6 = x
789
xc (D7 + x: D8
+ DD9
= x A2).
t
Figure 1:
(Left) Tree-form decision process considered in the example. Black round nodes belong to Player 1; white round nodes to Player 2. Square white nodes are terminal nodes in the game tree, payoffs are omitted. Gray bags denote information sets. (Right) The constraints that define the sequence- form polytope Q₁ for Player 1 (besides nonnegativity).
reduced- reduced-normall-onn normal-form plan for Player i represents deterministic strategy for the player as a vector E {0. 13 where the entry corresponding to the generic sequence x æ[ja] is equal to 1 if the player plays action a at (the nodes of) information set j E Jr. Information sets that cannot be reached based on the strategy do not have any action select. A crucial property of the reduced-normal-fom plan representation of deterministic strategies the fact that the utility of any player a multilinear function in the profile of cortteedd--ooma---- plans played by the players. The set of all reduced-

---

normal-form plans of Player i is denoted with the symbol II, Typically, the cardinality of II; is exponential in the size of the game tree.
The convex hull of the set of soatuced-orrml-fform plans of Player is called the sequence-form polytope of the player, and denoted with the symbol Q (T,, It represents the set of all randomized strategies in the game. An important result by Romanovski [1962], Koller et al. [1996], von Stengel [1996] shows that 2, can be captured by polynomially many constraints in the size of the game tree, as we recall next.
Definition 2.2. The polytope of sequence-form strategies of Player i is equal to the convex polytope
(1) x x|0|= = (2) EoEA, æbja| mr(p))
Vj VjEJ }
2 2= x R
As an example, the constraints that define the sequence- form polytope for Player I in the game of Figure (Left) are shown in Figure (Right). The polytope of sequence-forn strategies possesses a strong combinatorial structure that enables speeding up several common optimization procedures and will be crucial in developing efficient algorithms to converge to equilibrium.
2.2 Hindsight Rationality and Learning in Games
Games are one of many situations in which a decision-maker has to act in an online manner. For these situations, the most widely used protocol is that of Online Learning (e.g.. see Orabona [2022]). Specifically, each learner has set of actions or behavior they can employ X' S R (in extensive-fom games, this would typically be the set of reduced noreeed-oommlloomm strategies). At each timestep t the learner first selects, possibly at random, an element E X, and then receives a loss (opposite of utility) function ((()) : X' + R. Since as we observed the above utilities in EFGs are linear in each player's reluced-normal--oom plans, for the rest of the paper we focus on the case in which the loss function g(t) is linear, that is, of the form g(t)
(L(1), (")).
widely adopted objective for the learner that of ensuring vanishing average regret with high probability. Regret is defined as the difference between the loss the learner cumulated through their choice of behavior, and the loss they would have cumulated in hindsight had they consistently modified their behavior according to some strategy transformation function. In particular, let & be desired set of strategy transformations Φ: X + X' that the learner might want to learn not to regret. Then, the learner's 's 0-regret is defined the quantity
R-Reg (T) = max @
(1002200 (1) -(((())) ((()))
1=1
A no-gb-regre algorithm (also known Ø-regret minimizer) is one that, at all times T, guarantees with high probability that Re-Re((T) = o(T") no matter what is the sequence of losses revealed by the environment. The size of the set Tb of strategy transformations defines a natural measure rationality (sometimes called hindsight rationality) for players, and several choices have been discussed in the literature. Clearly, as & gets larger, the learner becomes more rational. On the flip side, guaranteeing sublinear regret with respect to all transfornations in the chosen set t might be intractable in general. On one end of the spectrum, perhaps the smallest meaningful choice of & is the set of all constant transformations 4ceast = {os i + d: jaxx In this case, -coost-regre is also called external regret and has been extensively studied in the field of online convex optimization. On the other end of the spectrum, swap regret corresponds to the setting in which & is the set of all transformations X' + X. Intermediate, and of central importance in this paper, is the notion of linear-swap regret, which corresponds the case in which
+ x + Ax A dxd with AZ E X VI X}
(linear-swap deviations)
is the set of all linear transformations from X to itself.
An important observation that when all considered deviation functions in & are linear, an algorithm guaranteeing sublinear Ø-regret for the set X can be constructed immediately from a deterministic
For the purposes of this paper, the adjective linear refers to the fact that each transformation can be expressed in the form æ + Ax for appropriate matrix A.
5

---

no-D-regret algorithm for X' ( by sampling X' 3 a from any x' E A" so as to guarantee that E[æ] x'. Since this is exactly the setting we study in this puper, this folklore observation (see also Farina et al. [2022]) enables us to focus on the following problem: does a deterministic no- r-rerett algorithm for the set of sequence-
strategies = Q of any player in an extensive-form game, with guaranteed sublinear 0-regret in the worst case, exist? In this paper we answer the question for the positive.
From regret to equilibrium The setting of Learning in Games refers the situation in which all players employ a learning algorithm, receiving as loss the negative of the gradient of their own utility evaluated in the strategies output by all the other players. A fascinating aspect of no- no-ret learning dynamics is that if each player of a game employs a no-4-regret algorithm, then the empirical frequency of play converges almost surely the set of @-equilibria, which are notions correlated equilibria, in which the rationality of players is bounded by the size of the set Φ. Formally, for a set of strategy deviations, Q-equilibrium is defined follows.
Definition 2.3. For n-player extensive-form game G and a set &; of deviations for each player, a { J-qquilibrium is a joint distribution μ. E A(II x ... x lln) such that for each player i, and every deviation & E D; it holds that
Eur=lu;(()) 2 Eu-ului x xi-))
That is, player i has an incentive to unilaterally deviate from the recommended joint strategy using any transformation & E $
This general framework captures several important notions of equilibrium across variety of game theoretic models. For example, in both NFGs and EFGs, no-external regret dynamics converge to the set of Coarse Correlated Equilibria. In NFGs, no-swap regret dynamics converge to the set of Correlated Equilibria [Blum and Mansour, 2007]. In EFGs, Farina et al. [2022] recently proved that a specific subset & of linear transformations called trigger deviations lead the set of EFCE.
Reducing r-regret to external regret An elegant construction by Gordon et al. [2008] enables constructing no-f-regret algorithms for generic set X' starting from no-external-regret algorithm for क. We briefly recall the result.
Theorem 2.4 (Gordon et al. [2008]). Let R be external regret minimizer having the set of transformations & as its action space, and achieving sublinear external regret Reg(*), Additionally, assume that for all & E there exists a fixed point (xx) x X. Then, h-regret minimizer Ra can be constructed as follows:
To output strategy (!) iteration I of Ra, obtain an output 6100 t of the external regret minimizer R, and return one of its fixed points x! = (30((())))
For every linear loss function g(9) received by R4,, construct the linear function (()) +
g(t) ()( and pass it loss
Let (-Ree(() be the --regret of Ry. Under the previous construction, it holds that
R-Reg
-Reg(T)
11
Thus, i is an external regret minimizer then Ry a D-regret minimizer.
3 No-Linear-Swap Regret Algorithm with Polynomial-Time Iterations
In this section, describe our no-linear-swap-eee no-linear-swaa-reerret algorithm for the set of sequence-forn strategies Q of a generic player in any perfect-recall imperfect-information extensive-fome game. The algorithm follows the general template for constructing Ø-regret minimizers given by Gordon al. [2008] and recalled in Theorem 2.4. For this we need two components:
i) an efficient external regret minimizer for the set Mo of all matrices inducing linear trans- formations from Q to Q.
ii an efficiently computable fixed point oracle for matrices A -M-- returning Ax Q.

---

The existence of a fixed point, required in ii), is easy to establish by Brouwer's fixed point theorem, since the polytope of sequence-fom strategies compact and convex, and the continuous function ++ Az maps Q to itself by definition. Furthermore, as it will become apparent later in the section, all elements A E Ma- have entries in [0. 1|=X2. Hence, requirement ii) can be satisfied directly by solving the linear feasibility program {find æ Aæ I. a 2) using any of the known polynomial-time algorithms for linear programming. Establishing requirement i) is where the heart of the matter is, and it is the focus of much of the paper. Here, we give intuition for the main insights that contribute to the algorithm. All proofs are deferred to the appendix.
3.1 The Structure of Linear Transformations of Sequence-Forre Strategy Polytopes
The crucial step in our construction is to establish a series of results shedding light on the fundamental geometry of the set Me- of all linear transformations from a sequence-fore polytope Q to itself. In fact, our results extend beyond functions from Q Q to more general functions from Q to generic compact polytope P == {a E R Pæ = p. x 2 0} for arbitrary P and p. We establish the following characterization theorem, which shows that when the functions are expressed in matrix form, the set M2-pP can be captured by polynomial number of constraints. The proof is deferred to Appendix B.
Theorem 3.1. Let Q be sequence-form strategy space and let P be any bounded polytope of the form P = {xx E R Px = p. x 2 0} S [0,>]", where P E Rexd, Then, for any linear function f: + P, there exists a matrix A in the polytope
(A(ja) =b
Vja E E VOE EL
A(o) =0
(5)
Ejecs by = p
Me-p = A .... Ao) ... Rx
(6) Ejec, by = bj
Vja Ej
(7) A(r) E 70,
VOEΣ VjEJ
(8) bj E R²
such that f(xx) = Ax for all x E Q Conversely, any A E MM-- defines a linear function + Ax from to P, that is, such that AT E P for all x E Q
The proof operates by induction in several steps. At its core, it exploits the combinatorial structure of sequence-foo forrn strategy polytopes, which can decomposed into sub-problems using a series of Cartesian products and convex hulls. A high-level description of the induction is as follows:
The Base Case corresponds to the case of being at a leaf decision point. In this case, the set of deviations corresponds to all linear transformations from a probability n-simplex into a given polytope P. This set is equivalent to all d x n matrices whose columns are points in P, which can easily be verified formally. This corresponds to constraint (3) in the characterization of Me-PP.
For the Inductive Step, we are at an intermediate decision point j. that is, one for which at least one action leads to further decision points.
In Lemma B.8 we show that any terminal action a at j leads to a column in the transformation matrix that is necessarily a valid point in the polytope P. This is similar to the base case, and again leads to constraint (3) in the characterization.
In Lemma B.7, we look at the other case of non-terminal action j. We prove that there always exists an equivalent transformation matrix whose column corresponding to sequence ja is identically 0 (constraint (4)). This allows for the "crux" of the transformation to happen in the subtrees below ja or equivalently, the subtrees rooted at the children decision points Cja of ja.
key difficulty to conclude the proof using the assumption of the inductive step to characterize all such valid transformations. The set of strategies in the subtrees rooted at the children decision points C,. is general the Cartesian product the strategies in these subtrees. This explains the need for the fairly technical Proposition B.4, whose goal is to precisely characterize valid transformations of Cartesian products. This leads to constraints (5) and (6) in our final characterization.
7

---

We also remark that while the theorem calls for the polytope P to be in the form P fa E ie Pæ p. 2 0}. with little work the result can also be extended handle other representations such {a R Pæ 2 p}. We opted for the form specified the theorem since it most directly leads to the proof, and since the constraints that define the sequence-form strategy polytope (Definition 2.2) are already in the form of the statement.
In particular, by setting P = Q in Theorem 3.1 (in this case, the dimensions of P will be k = | and d = [Σ), conclude that the set of linear functions from Q to itself is compact and convex polytope Mo- S [0, 11 xx*x, defined by ( linear constraints. As discussed, this polynomial characterization of MM-2 2 the fundamental insight that enables polynomial-time minimization of linear-swap regret in general extensive-form games.
3.2 Our No-Linear-Swap Regret Algorithm
From here, constructing no-externa--regeet algorithm for Mo- is relatively straightforward, using standard tools from the rich literature of online learning. For example, Algorithm we propose solution employing online projected gradient descent [Gordon, 1999, Zinkevich, 2003].
Algorithm 1: (-Regret minimizer for the set MM-+
Data: (1) E Ma-s and fixed point (1) of A learning rates v/()) > 0
for i 1,2,... do
Output (1)
Receive g(() and pay (e(t),x(1)) x(1)
Set (() = (xx
A(++) = I (A - (n (()) = arg miny |A - (0 Y
Compute fixed point ((++1) A ((+1)) ((+1) Q of matrix A (t-1)
Combining that no-extermal-regret algorithm for with the construction by Gordon et al. [2008], we can then establish the following linear-swap regret and iteration complexity bounds for Algorithm 1. Theorem 3.2 (Informal). Let E denote the set of sequences of the learning player in the extensive- form game, and let vf()) = 1/vt for all t. Then, for any sequence of loss vectors e(() E [0, 1J=, Algorithm I guarantees linear-swap regret ((EE)2/)) after any number T of iterations, and runs in (ppoly( log? t) time for each iteration t.
The formal version of the theorem is given in Theorem D.I. is worth noting that the polynomial- sized description of Me- is crucial in establishing the polynomial running time of the algorithm, both in the projection step (5) and in the fixed point computation step (6). We also remark that the choice of online projected gradient descent combined with the ellipsoid method for projections were arbitrary and the useful properties of Mo- are retained when using it with any efficient regret minimizer.
4 Linear-Deviation Correlated Equilibrium
As we discussed in the preliminaries, when all players a game employ no-u-regret learning algorithms, then the empirical frequency of play converges to the set of Φ-equilibria almost surely. Similarly, when & = MM the players act based on mno-linerr-wwap regret" dynamics and converge notion of d-cquilibrium we call linear-deviation correlated equilibrium (LCE). In this section we present some notable properties of the LCE. In particular, we discuss its relation to other already established equilibria, well the computational tractability of optimal equilibrium selection.
4.1 Relation CE and EFCE
The ---rerett minimization framework, offers natural way to build a hierarchy of the corresponding ø-equilibria based on the relationship of the & sets of deviations. In particular, if for the sets t1, 42 it holds that i S 22 then the set of dg-cquilibria is subset of the set of --quuiiiibia Since

---

the Correlated Equilibrium is defined using the set of all swap deviations, we conclude that any @-equilibrium, including the LCE, is superset of CE. What is the relationship then of LCE with the extensive-form correlated equilibrium (EFCE)? Farina et al. [2022] showed that the set & inducing EFCE is the set of all "trigger deviations", which can be expressed as linear transformations of extensive-form strategies. Consequently, the set EP is a subset of all linear transformations and thus, it holds that CE C LCE C EFCE. In examples E, and E.3 of the appendix we show that there exist specific games in which either CE & LCE, or LCE of EFCE. Hence, we conclude that the previous inclusions are strict and holds CE & LCE ç EFCE.
For Example E. we use a signaling game from von Stengel and Forges [2008] with known EFCE and we identify linear transformation that is not captured by the trigger deviations of EFCE. Specifically, it is possible to perform linear transformations on sequences of subtree based on the strategies on other subtrees of the TFSDP, For Example E.3 we have found specific game through computational search that has a LCE which is not a normal-form correlated equilibrium. To do that we identify particular normal-form swap that non-linear.
Empirical evaluation To further illustrate the separation between no- sineea--waa--egeee dynamics and no-trigger-regnn dynamics. used for EFCE, we provide experimental evidence that minimizing Linear-swap-reee also minimizes trigger-regret (Figure 2, left), while minimizing rigger-regret does not minimize linear-swap regret. Specifically, in Figure 2 we compare our no-linear-swap-regee learning dynamies (given in Algorithm 1) to the no-trigger-regret algorithm introduced by Farina et al. [2022]. More details about the implementation of the algorithms is available in Appendix F. In the left plot, we measure on the y-axis the average trigger regret incurred when all players use one or the other dynamics. Since trigger deviations are special cases of linear deviations, as expected, we observe that both dynamics are able to minimize trigger regret. Conversely, in the right plot of Figure 2, the y-axis measures linear-wwap-regeet. We observe that while our dynamics validate the sublinear regret performance proven Theorem 3.2, the no-trigger-regre dynamics of Farina et al. [2022] exhibit an erratic behavior that is hardly compatible with a vanishing average regret. This suggests that no-linear seaprrrrt indeed strictly stronger notion of hindsight rationality.
Three-player Kuhn poker (13 ranks)
Three-player Kuhn poker (13 ranks)
0.005
0.05
No- No-lineur- www-linuurswaa--pee rogret dynamics
Avergge lincar-swapp swap regret
No-limear-swap wwap-regretttttttooeeeeeeeeeeeee dynamics
Average trigger regret
0.004
No-trigget-regret dynamies
0.04
No-trigger-regeet dynamics
0.003
0.03
0.002
0.02
0.001
0.01
0.000
0.00
5000
10000
15000
20000
5000
10000
15000
20000
Iteration
Iteration
Figure 2: (Left) Average trigger regret per iteration for both a lincar-swap swap-rereet minimizer and a trigger-regret minimizer. (Right) Average linear-swap regret per iteration for the same two minimizers.
4.2 Hardness of Maximizing Social Welfare
In many cases we are interested in knowing whether it is possible to select an Equilibrium with maximum Social Welfare. Let MAXPAY-LCE be the problem of finding an LCE in EFGs that maximizes the sum (or any linear combination) of all player's utilities. Below, we prove that we cannot efficiently solve MAXPAY-LCE, unless P=NP, even for 2 players if chance moves are allowed, and even for 3 players otherwise. We follow the structure of the same hardness proof for the problem MAXPAY-CE of finding an optimal CE EFGs. Specifically, von Stengel and Forges [2008) use a reduction from SAT to prove that deciding whether MAXPAY-CE can attain the maximum value is ha-hard even for players. To do that, they devise a way to map any SAT instance into a polynomially large game tree in which the root is the chance player, the second level corresponds to player, and

---

the third level corresponds to the other player. The utilities for both players are exactly the same, thus the players will have to coordinate maximize their payoft irrespective of the linear combination of utilities we aim to maximize.
Theorem 4.1. For two-player, perfect-recall extensive-form games with chance moves, the problem MAXPAY-LCE. is not solvable in polynomial time, unless P=NP.
Remark 4.2. The problem retains its hardness if we remove the chance node and add a third player instead. As showed in von Stengel and Forges [2008], in that case can always build polynomially-sizee sized game tree that forces the third player to act as a chance node.
Conclusions and Future Work
In this paper we have shown the existence of uncoupled no-linear-swap regret dynamics with polynomial-time iteration complexity in the game tree size in any extensive-form game. This significantly extends prior results related to extensive-form correlated equilibria, and begets learning agents that learn not to regret a significantly larger set of strategy transformations than what was known to be possible before. A crucial technical contribution made to establish our result, and which might be of independent interest, is providing a polynomial characterization of the set of all linear transformations from that such a set of transformations can be expressed as a convex polytope with a polynomial number of linear constraints, by leveraging the rich combinatorial structure of the sequence-fore forrnce-form strategies. Moreover, these no-linear-wwar regret dynamics converge to -near-deviation correlated equilibria in extensive-form games, which are novel type of equilibria that lies strictly between normal-form and extensive-form correlated equilibria.
sruence-form strategy polytope itself. Specifically, we showed
These new results leave open few interesting future research directions. Even though know uncoupled dynamics converging to lincar-deviation correlated
that there exist polynomial-tin equilibrium, we conjecture that it is also possible obtain efficient centralized algorithm similar to the Ellipsoid Against Hope for computing EFCE in extensive-form games by Huang and von Stengel [2008]. Additionally, it is intriguing question understand whether no-linear-swer swap regret algorithm exists that achieves Ollog T) regret per-player, as is the case for no-trigger regret [Anagnostides al., 2023]. Furthermore, it would be interesting further explore problems of equilibrium selection related to LCE, possibly by devising suitable Fixed-Paramelt A Algorithms in the spirit of Zhang et al. [2022]. Finally, the problem of understanding what is the most hindsight rational type of deviations based on which we can construct efficient regret minimizers in extensive-form games remains a major open question.
References
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisy, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):pp- 508-513, 2017.
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418-424, 2018.
Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, 365(6456): 885-890, 2019. doi: 10. 10.11 /211////eenee..ay2400000
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T. Connor, Neil Burch, Thomas Anthony, Stephen McAleer, Romuald Elie, Sarah H. Cen, Zhe Wang, Audrunas Gruslys, Aleksandra Malysheva, Mina Khan, Sherjil Ozair, Finbarr Timbers. Toby Pohlen, Tom Eccles, Mark Rowland, Mare Lanctot, Jean- -ean-Baptiste Lespiau, Bilal Piot, Shayegan Omidshafici, Edward Lockhart, Laurent Sifre, Nathalic Beauguerlange, Remi Munos, David Silver, Satinder Singh, Demis Hassabis, and Karl Tuyls. Mastering the game of Stratego with model-free multiagent reinforcement learning. Science, 378(6623):99099) 996, 2022.
Anton Bakhtin, David J Wu, Adam Lerer, Jonathan Gray, Athul Paul Jacob, Gabriele Farina, Alexan- der H Miller, and Noam Brown. Mastering the game of no-press Diplomacy via human-regularizedd reinforcement learning and planning. International Conference on Learning Representations (ICLR), 2023.
10

---

Dean P. Foster and Rakesh V. Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21(1)::00555 55, 1997.
Drew Fudenberg and David Levine. Consistency and cautious fictitious play. Journal of Economic Dynamics and Control, 19(5-7): (1117)):065-10000 1089, 1995.
Drew Fudenberg and David K Levine. Conditional universal consistency. Games and Economic Behavior, (111-2):104-1333 130, 1999.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading correlated equilibrium. Econometrica, 68(5): 127-1115, 2000.
Sergiu Hart and Andreu Mas-Colell. A general class of adaptive strategies. Journal of Economic Theory, 98(1):26-54, 2001.
Drew Fudenberg and David K Levine. The theory of learning in games, volume MIT press, 1998.
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). 2022.
Gilles Stoltz and Gábor Lugosi. Learning correlated equilibria in games with compact sets of strategies. Games and Economic Behavior, 59(1): 2007.
Avrim Blum and Yishay Mansour. From external to internal regret. J. Mach. Learn. Res., 2007.
Geoffrey Gordon, Amy Greenwald, and Casey Marks. No-regret learning convex games. In International Conference Machine learning, pages 360-367, 2008.
Sham Kakade, Michael Kearns, John Langford, and Luis Ortiz. Correlated equilibria in graphical games. In Proceedings of the 4th ACM Conference on Electronic Commerce, pages 42-47, 2003.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In Advances in Neural Information Processing Systems, pages 1729-1736, 2008
Ioannis Anagnostides, Gabriele Farina, and Tuomas Sandholm. Near-optimal de-rerett learning in extensive-form games. In International Conference on Machine Learning (ICML), 2023.
B. von Stengel and F. Forges. Extensive-form correlated equilibrium: Definition and computational complexity. Mathematics of Operations Research, 33(4): 1022, 2008
Wan Huang and Bernhard von Stengel. Computing an extensive-form correlated equilibrium in polynomial time. In International Workshop Internet and Network Economics, pages 506-513. Springer, 2008
Andrea Celli, Alberto Marchesi, Gabriele Farina, and Nicola Gatti. No-regret learning dynamics for extensive-form correlated equilibrium. In Advances in Neural Information Processing Systems, volume 33, 2020.
Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. Strategizing against Learners in Bayesian games. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 5221-5252. PMLR, 02-05 Jul 2022.
Kaito Fujii. Bayes correlated equilibria and no-regret dynamics, 2023.
Dustin Morrill, Ryan D' D'Orzio, Mare Lanetot, James R. Wright, Michael Bowling, and Amy R. Greenwald. Efficient deviation types and learning for hindsight rationality in extensive-form games. In Proceedings of the 38th International Conference Machine Learning, ICML. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 7818-7825 PMLR, 2021.
I. Romanovskii, Reduction of a Game with Complete Memory to Matrix Game, Sovie! Mathematics, 3, 1962.

---

Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel. Efficient computation of equilibria for extensive two-person games. Games and Economic Behavior, 14(2):247-259, 1996.
Bernhard von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):200-246, 1996.
Francesco Orabona. Modern Introduction Online Learning, 2022.
Geoffrey Gordon. Regret bounds for prediction problems. In Proceedings of 12th Annual Conference on Computational Learning Theory (COLT '99), pages 29 40, July 1999.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML' '3, page 928-935. AAAI Press, 2003.
Brian Hu Zhang, Gabriele Farina, Andrea Celli, and Tuomas Sandholm. Optimal correlated equilibria in general-sum extensive-fomm games: eaxameparameter algorithms, hardness, and two-sided volumm-generatte In David M. Pennock, Ilya Segal, and Sven Seuken, editors, EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA. July 15, 2022, pages 1119-1120. ACM, 2022.
Nisheeth K. Vishnoi. Algorithms for Convex Optimization. Cambridge University Press, 2021.
Bernd Gärtner and Jirí Matousck. Approximation Algorithmss and Semidefinite Programmingg Springer Publishing Company, Incorporated, 2014.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL httph:ttp////.. /www. gurobi com.
H. W. Kuhn. A Simplified Two-Person Poker. In Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games, volume 1 of Annals of Mathematics Studies, 24, pages 97-103. Princeton University Press, Princeton, New Jersey, 1950.
12

---

A
Additional Extensive-Form Game Notation
In the proofs, we will make use of the following symbols and notation.
Symbol
Description
Ti Set of all Player i's infosets. Set of actions available at any node in the information set j.
A
M,
Set of sequences for Player defined as 2 = {(i a) i J, E Aj} (()) where the special element Ø is called the empty sequence. Set of terminal sequences for Player i.
Ø
Pj
Parent sequence of j, defined as the last pair (i,a) E Σg encountered on the path from the root to any information set j.
C,
Set of all "children" of sequence defined as the information sets j E J having as parent Pj O.
j Rj
Information set j E J is an ancestor of j' E J. that is, there exists a path in the game tree connecting a node E to some node h E Sequence o precedes sequence o', where a, o' belong to the same player.
a
a azi
Sequence o (j', a') is such that ž Sequences j E I and all of its descendants, Σσ == for E:o = j}.
Σzj
Q
grruence-form strategies of Player (Definition 2.2).
Q-
Sequence- form strategies for the subtree rooted at E J (Definition A.1). Reduced-normal-fore plans (a.k.a. deterministic sequence-form strategies) of Player i.
IT;
Reduuce-nnomal-ffore -frm plans (a.k.a. deterministic sequence- form strategies) for the subtree rooted at j E J.
Table 1: Summary of
game-theoretic notation used in this paper. Note that we might skip player- specific subscripts when they can inferred.
Furthermore, when the subscript referring to players be inferred or is irrelevant (that is, the quantities refer to generic player), then we might skip it.
As hinted by some of the rows in the above table, we will sometimes find it important to consider partial strategies that only specify behavior at decision node j and of its descendants j' > j. We make this formal through the following definition.
Definition A.1. The set of sequence-fon form strategies for the subtree rooted denoted Qz is the set of all vectors x E 2 such that probability-aass-coerrriii constraints hold at decision node j and all of its descendants j' > j. specifically
(10) EncA, ælj'a| xlp VJ' }
(9)
EnEA, æ[ja]
2=1=
R R
Finally, we define the symbol Σ to be the set of all terminal sequences for Player i. Thus, the set Σ, Σt would give us all the non-terminal sequences of that player.
Access to coordinates By definition, sequence-form strategies are vectors indexed by sequences.
To access the coordinate corresponding sequence σ, we will use the notation x[o].. Occasionally, we will need to extract a subvector corresponding to all sequences that are successor of an information set j. that is, all sequences ž j. For that, we use the notation j].
Remark on the structure of sequence-form strategies We further remark the following known fact about the structure of sequence-form strategies. Intuitively, it crystallizes the idea that sequence- form strategies encode product of probabilities actions on the path from the root to any decision point. The proof follows directly from the definitions.
13

---

Lemma A.2. Let Ji be an information set for generic player. Then, given any sequence-form strategy Qn action E Aj, and child information set j' Caa there exists sequence-form stralegy æz E 22 such that
x 12 j'I =
B Proof of the Characterization Theorem (Theorem 3.1)
In this section we prove the central result of this paper, the characterization given Theorem 3.1 of linear functions from the requence-form strategy polytope Q to the generic polytope P = {a E R Pæ p, x 2 0), where P E kxd and p E IR*
We will prove the characterization theorem by induction on the structure of the extensive-form strategy polytope. To do so, it will be useful to introduce few additional objects and notations. We do so the next subsection.
B.1 Additional Objects and Notation Used in the Proof
First, we introduce a parametric version of the polytope P, where the right-hand side vector is made variable.
Definition B.1. Given any b IR k will denote with P(b) the polytope
P(b) = (a Rd Pa = b, x 2 0}.
particular, P(p).
Furthermore, introduce the equivalence relation S to indicate that two matrices induce the same linear function when restricted to domain D.
Definition B.2. Given two matrices A, of the same dimension, we write A = Bf Bæ for all x E D. Similarly, given two sets U, V of matrices we write U =p V to mean that for any A E U there exists E with A P B, and vice versa.
Additionally, introduce symbol to denote the set of all matrices that induce linear functions from a set Ll to a set V.
Definition B.3, Given any sets U, V we denote with Lu-sy the set of all matrices that induce linear transformations from U to V. that is,
Lu-v = {A Ax E for all x E Uz.
Finally, we remark that for a matrix A whose columns are indexed using sequences a E E, we represent its columns as Aaa)- Furthermore, for sequence-form strategies Q, we use x[o] to represent their entries, and a Ex] to represent vector consisting only of the entries corresponding to sequences Ez
B.2
Key Tool: Linear Transformations of Cartesian Products
We are now ready to introduce the following Proposition, which will play an important role in the proof of Theorem 3.1.
Proposition B.4. Let .e. Um be sets, with 0 & aff 2 for all 1,..., any i = 1,...,m m and any b, E Rk, let Mu.-P((bi) be such that Mu.-)P(b) Su. Lu.-P((b)) Then, for all b E R
....... m. Furthermore, for
(11) A; Mu--p((
Vi (1, (1....., m)
La4 ... PP()) Su x... xthm)
[A1 [AIl... Amm]
(12) b +...+ bm
(13) b, ER
Vie (l....,,. m}
(14)
"Instead of the condition 0 & aff 44, we could equivalently state that there exists T. such that n,T x. = for all E 24 using the properties of affine sets.
14

---

Proof. We prove the result by showing the two directions of the inclusion separately.
First, we show that for any b R any matrix A [A Am] that belongs to the set on the right-hand side of (14) induces a linear transformation from 21 x ... x tmn to P(b) and thus belongs to Lan xxx)))) To that end, note that for any (Z1,...,, Rm)
Ui x
x Um.
Ax Σ A 0. and P(Ax)
Σ i=1
PA E
Σ i=1
b:
(22
where both cases we used the fact that A, maps any point in to point in P(b,) = {
Py b, y 2 0} by (11). Hence Ax P(b) for all U1 x .... ... Ums as wanted to show.
(C) We now look at the converse, showing that for any E R and matrix B = B B.] E Lit, x--xX) there exists matrix A [A1 ... Am] that satisfies constraints (11)-(13) and such that Bæ = Aæ for all æ E U1 x .... Um- As a first step, in the next lemma we show that B is always equivalent another matrix B = [B]
B 2th x.. xlhm) B that satisfies B, 2 for all = 1...., m and p; E U4.
Lemma B.5. There exist B B'd such that B x B' = B and furthermore, for all i 1, ....., m. B 2 0 for all a E Eik
B.
Proof of Lemma B.5. Since 0 & al for all i I,..., by hypothesis, then there exist vectors т; such that T3 æ; = for all w, E Ur For any E (l....,d) and e (I,..., m 1]. let
[k] == min [B] zell,
Ak E (I.....a).
B = B, - B.T,"
Furthermore, let f3 == Σ. 2n B. and B', B, + 3m T Is immediate to check that B', is such that B'x = Bæ for all æ E U₁ X ... x Um for all = 1,... m and
the matrix B' = [ that is, B' - xl..)....)) B. We now show that B x; Uy. Expanding the definition of B; and Br, for all i {I,.... m 1}, x Uc and
& E {l,...,d},
(B(x,)[M = [B (A.) (T.T.:) = -B,,. min (B, [M] 2 O.
d. Eld,
Hence, it only remains to prove that the same holds for m. To that end, fix any E (I....,d .d and D.. E Um, and let a. E arg min et, (B,x,)[A Using the fact that all vectors Pbb) are nonnegative, x² (æ),.... x Fm)
for all E (1, ....... 1
Ui ... x Um must satisfy Bx* 2 0. Hence,
m-
S (Bx*) [k] (B.
[M]
[k] +
Σ (Ba (Bm [k] +
Σ
B (B' F.m [k]
thus concluding the proof of the lemma.
Since B' (14x.... xll.)) B, and B maps to P(b), for all (011 (,,, am) E Eh x... x tmm
we must have
b b= P(Bx))
Σ PBCa.
Since we can pick the æ, for different indices independently. it follows that PB,æ, must be a constant function of æ; E U4 that is, there must exist vectors bi...., bm E R such that
b
bm. = b, and PB - b:
Va; E Ui
Since in addition Bix; 2 0 (by construction of the B(), this means that B E Lu::-P(hh)) Finally, using the hypothesis that Lu, Pbb.) Su. MM,,-((b:,, there must exist A, Mu..P((.). with A, u B', for all i = I....,m. This concludes the proof.
15

---

B.3 Characterization of Linear Functions of Subtrees
The following result can be understood as a version of Theorem 3.1 stated for each subtree, rooted at some decision node, of the decision space.
Theorem B.6. For any decision node j E I and vector b, E R2, let
(15) PAG'a by
Vj'd' E Σn no
(16)
Agray =
Vj'd E Ex) E
MP2,+
[... A (ja)
(17)
Eyrecga bY" = by
Vj'd EZn 12
(18) Agraa) 0
Vj'd' Σzj
CRUMELS
(19) by E R
vj'
(20)
Then, Me, =zz Le
Before continuing with the proof, we remark a subtle point: unlike (7), which constraints each column have entries in [0, 7). (18) only specifies the lower bound at zero, but no upper bound. Hence the tilde above the symbol of this Theorem. Consequently, the matrices in the set M -b,(),) need not have bounded entries. In that sense, Theorem B.6 is slightly different from Theorem 3.1. We will strengthen (18) to enforce a bound on each column when completing the proof of Theorem 3. the next subsection.
Proof. To aid us with the proof, we first express the definition of Mo.,-P(P in a way that better captures the inductive structure we need. By direct inspection of the constraints, the set M (P(()) satisfies the inductive definition
A A (ga) ...] RdxErs such that:
(21) (jo) = bj
Va E A : ja E 7
(22) A(ja) =0
Va Ay: ja E
M M2z)+P(6,) =
(23) Eyec, by = bj
AE:Ajjja E
(24) [A(o)lats' E EMo (
Va Aj.J" Cga
(25) A(ja) 2 0
Va Aj Va E Aj,J' E Cja
(26) by: E R
(27)
We prove the result by structural induction on the tree-form decision process.
Base case. We start by establishing the result for any terminal decision node j E J, that is, for which all sequences (ja
AA, terminal. In this case, the set Øz is the probability simplex A{ija a E A,1). Thus, for matrix A to map all x E Q= to elements in the convex polytope P(b,) is both necessary and sufficient that all columns of A be elements of P(b;). ). It is necessary because if Aær E P(b;) for all æ E Oz then for the indicator vector with a: jajj
get Av: A (مر) E P(b;). And, it is sufficient because any Q= represents convex combination of the columns Aga))
The set defined by these constraints matches exactly the set Me -P(b,) defined in the statement: since all sequences ja are terminal, in this case reduces to
Mo = {[
(28)
PAGa) = VaE VaE
}
A (ja) ....] R
(29) A(aa)
that is, the set of matrices whose columns are elements of P(b;). So. we have (-P(b))())) fe- with equality, which immediately implies the claim
Me (P((,) E (P
16

---

Inductive step. We now look at general decision node j E J, assuming as inductive hypothesis that the claim holds for any j' > j. Below we prove that Me, (P(b,) =oz fe_, -Pb,) as well.
(9) We start by showing that for any bj E RR, and A Mo.;-P(b, have Ax P(b,). From (18) it is immediate that A has nonnegative entries, and since any vector a E ET also has nonnegative entries, it follows that Ax 2 0. Hence, it only remains to show that P(Az) by. Using Lemma A.2, for any j' E HaEA, there exists Ezyy 2z5' such that x:
[=E=n/ æíja| zzjz Hence, have
P(Ax)= = Σ PA (Ja) [ja] + aEA,
Σ
Σ S'ECaa
PA ( Bz5r)
o jagD
Σ
x[ja] GA) + Σ
x[ja| Σ
(from (22))
aE.A, jaE
aeA, jugs.
J'EC,a
Σ aEA,
æ[ja] bj + Σ
æija| Σ by
(from (21) and (24))
aEA,
J'ECJa
jaEE
jaqz
Σ aEAA; ja
æ[ja] - by + Σ
xbja]
(from (23))
aEA;
ju
bj Σ
æ[ja]= bj-
(from Definition 2.2)
aeA,
()) Conversely, consider any B E (o2)-)(())) We will show that there exists matrix A E Me-,-Pun such that _ A. First, we argue that there exists a matrix B' = with the property that the column B' (ja) corresponding to any nonterminal sequence is identically zero.
Lemma B.7. There exists B' S B such that (Bja) = 0 for all a E Aj such that ja \E
Proof. Fix any a E A, such that ja is nonterminal. Then, by definition there exists least one decision node j' whose parent sequence is ja. Consider now the matrix B" obtained from "spreading" column B Bija] onto Bijaar) (a' E Ayy),, that is, the matrix whose columns are defined according to the following rules: (i) B" (ja) O, (ii) B" Byjarr = B'yay + B for all a' E Ay, (iii) B%,, = B everywhere else. The column (ja) is identically zero by construction, and all other columns B'jayy a' E Aj \ {a}. the same B. Most importantly, since from the sequence-forn constraints Definition 2.2 any sequence-form strategy a E 2² satisfies the equality æija] = "''EA, ælj'a'], the matrix B" satisfies
B"x Ba for all E 2z i.e., B" _ B. Iterating the argument for all actions a A yields the statement.
Consider now any A, that leads to terminal sequence ja E Σz E- The vector ija defined as having a in the position corresponding to ja and ( everywhere else is valid sequence-form strategy vector, that is, 1ja Q² Hence, since B' maps Q ; to P(b,), it is necessary that B' (Jaa P(b;), that is, B ((aa) 2 0 and PB bj. In other words, we have just proved the following.
Lemma B.8. For any A, such that ja E En 0 EJ, B' ((a) and PB b,.
17

---

Combined, Lemmas B.7 and B.8 show that B' satisfies constraints (21), (22), and (25). Consider now any action E A, that defines a nonterminal sequence ja Σ> E' For each child decision point j' E Cja: let znj E Qr be a choice of strategy for that decision point, and denote B the submatrix of B' obtained by only considering the columns (B()) corresponding to sequences a ž j'. The vector æ defined according to æ[ja] = x|> r = z²zj for all j' Cja. and 0 everywhere else is a valid sequence-form strategy a E jzj. and therefore B'æ E P(b,) since B' 0 B and hypothesis. Therefore, using the fact that B (ja)
-----)(b,)) by by Lemma B.7, we conclude that
P(b,) 3 B'
Σ B B
Because the above holds for any choice of æzj" E Ozy' it follows that the matrix [-... B' ....] E Lixyec e~ y Hence, applying Proposition B.4 (note that e aff 2n since IoEA, æ[j'a| for all æ E Φ2, by Definition A. together with the inductive hypothesis, we conclude that for each j' Cja there exist vector by E R and a matrix Azj E / such that Ejec, by = bj and .... B E ...] Exyecya R [... A ...... We can therefore replace all columns corresponding to B'z3 with those of Agj, obtaining a new matrix _oz, B'. Repeating the argument for each ja Σz j E finally yields new matrix that is بxn, B and satisfies all constraints
given in (27), as we wanted to show.
B.4 Putting all the Pieces Together
Finally, we are ready to prove the main result of the paper.
Theorem 3.1. Let be a sequence-forn strategy space and let be any bounded polytope of the form P = {x E Rd Pæ p.æ x 2 0) S |0.>|%, where P E R kxdd Then, for any linear function
f: Q P. there exists a matrix A in the polytope
(3) PA(ja) = =b,
Vja E E+ VOE
(4) A(o) = =0
(5) Ejeco by =
Me-p== == A A= [... A(o) ... ERRE
(6) Epec, by bj
VjaE>i>'
(7) A(a) y0
VOEΣ
(8) bj E
VjEJ
such that f(x) Ax for all E Q Conversely, any A MM-x defines linear function x b Ax from Q to P, that is, such that Ax E P for all x E Q
Proof of Theorem 3.1. We prove the result in two steps. First, show that
(30)
PA(ja) (ja) = bj
Ej E
(31)
Asa) =
V
(32)
Eyeco by = P
Lo-D S Me-p:=
A = A(o) .... E RxXE
(33) Ee by b
VjaE
(34)
A(r) 0
Y
(35) by E R
VjEJ
where the difference between Mo-p and MM-x lies in constraint (34), which only lower bound (at zero) for each entry the matrix, as opposed to a bound [0, 7] as in (7). Using the definition of Me given in (20) (Theorem B.6), the set Me+r can be equivalently written as
(36)
A(ø) -0
(37)
Σjeca bj =
M A = .... A ....
R dxx
(38)
[A(o)loss E EM
VjECa Co Vj Co
(39)
by E E
18

---

To show that Me-p =e Le-P, we proceed exactly like in the inductive step of the proof of Theorem B.6. Specifically, let A MMapp and a Q be arbitrary. From Definition 2.2 it follows that x [| 2z for any j E Ce and therefore, denoting Arj = (a)))oz)
P(Ax) (36)
Σ jECa
(A
(38)
bj
(38)
P,
Ax
(36)
Σ A 2 0.
(38)
JEC
jECa
which shows that Ax E P. Since A and æ were arbitrary. it follows that Ma-p _ Ce-p. Conversely, let B Ce+p be arbitrary, and fix root decision node j Cz. Then, can "spread out" the column ((e) by adding it to each (jja) a E A, by constructing the matrix CO-P 3 B' o defined by (i) B3 = 0, (ii) B (j) = (Baa) + BBeen for any a A and (iii) (,)) = (() everywhere else. Pick now any vectors {ΙΣ} E 22 : Cz). ). and consider the vector defined as x0Ø]
and x|Σ>>| l znj for all Co. The vector is valid sequence-forn strategy, that is, æ E Q. Let now B = [ (o)oooz From the fact that B'a a E P, together with the fact that by construction B' (2) = 0, conclude that
B'x
Σ BB jEC₂
Since the inclusion above holds for any choice of {ズ>} E Qzyije E Cz ). and since for all j E Co the vector 0 & aff 2= (indeed, EaEd, æ[ja| Proposition B.4 together with Theorem B.6 we conclude that for each j E Ca there exists a vector b, E R and a matrix A _M such that Ejece bj p and A = B'zj- By replacing the submatrices B with A in B' we then obtain an equivalent matrix that satisfies all constraints that define Me-P. In summary, we have Me-p = Ce-P.
for all D by Definition A.1), from
To conclude the proof, now show that Me-r -M-p. First, make the straightforward observation that any A E Me-p also belongs to Me-p, as the constraint that define the latter set are only looser. Hence, only need to show that any B E Mo+p also satisfies constraint (7). Since B _Me+P, all columns of B are nonnegative (constraint (34)). Furthermore, since Me-p = LQ-P, clearly Bæ P for all æ Q. Fix now any sequence
Σ, and consider any strategy x E Q that puts proability mass 1 on all the actions on the path from the root to a included, that is, any Q with z = 1. Then, from the nonnegativity of the columns of B, follows that
e Br 2 B(a)-
Since by definition of y any point in P belongs to [0, y1d, we then conclude that B (a) 10, implying that B e Me-sp as we wanted to show.
C Corollaries of the Characterization Theorem
We mention two direct corollaries of Theorem 3.1 that slightly extend the scope the characterization. The first corollary asserts that the polytope Mo-p characterizes not only all linear functions from Q to P, but also all affine functions.
Corollary C.1 (From linear to affine functions). Let Q be sequence-form strategy space and let P be any polytope. Then, for any affine function g Q - P. there exists a matrix in the polytope M defined in Theorem 3.1 such that g(æ:) = A for all E Q. Conversely, any A E MM induces an affine function from to P.
Proof. The second part of the statement is trivial since any linear function is also affine, and any A E EMorp induces linear function from to P. Let g(x) = =(xx) + be any affine function, where f is appropriate linear function from Q to P and b E R². Since q[00] = for all Q the function g coincides on Q with the function ğ 9 a + f(x)) + b a1(2), which linear function of æ. Hence, from the first part of Theorem 3.1 there exists A E M such that Ax g( (x) = g(x) for all x E Q
The second corollary of Theorem 3.1 extends the characterization to the alternative definition of polytope as bounded set the form C (y E R Cy S c). by first introducing slack variables and rewriting the polytope in the form handled by Theorem 3.1.
19

---

Corollary C.2 (Alternative polytope representations), Let Q be sequence-fome strategy polytope,
and C { E R" .Cy I cj S [- 7 be a bounded polytope, where -R mmx. Let k = max |cc]oo ) and introduce the polytope
P { (8,)) X
[
! - -c CC,
y 8
knl
2 0 C
10,2,]ntm
which is of the form handled by Theorem 3.1. For any affine function g + C, there exists matrix A in the polytope
Me-c = [Mee] - r1 ( ... R
M Z
Ma-s
MER Ž
R mxx
such that g(z) Ax for all Q. Conversely, any A E MMec induces affine function from Q too
Proof. We begin by proving that C S [->,,] implies P S [0,2 27| Consider any (ÿ.s) E P and set y = - y1. Then, this is a valid C S [-y,>] 71" and, consequently, ÿ E [0, 2y/".. For the y 7 from before. By definition of
slack variables it holds that kns and by y 2 1,,, we conclude that c Cy S (k + n7k)1 = E [0, 27)""
Cy, where
Now let g Q > C. be any affine function from Q to C. Then we can define an affine function f: Q + P such that
f(x) = [g(z)) + 7
for all æ Q. By Corollary C.1 know that M-+ characterizes all affine functions from Q to P. including the previous function f. Thus, there exists an M R such that g(x) + y1 Mæ for all æ E Q. Since æ x1Ø]- for all æ E 2, we conclude that there exists A E MM- such that g(x) = Ax = Mæ - >1 for all x E Q.
Conversely, consider any A E Mo- and define g(x) = Ax. That is, there exist suitable R mxE that satisfy the constraints of polytope Mo-c. Then for all x Q holds g(x) = Ma= y1, and (ý, 8) E P where ý Mæ and 8 Za. Thus, by construction of P, as we also argued in the beginning of the proof, conclude that g(æ) y 71 EC
M E rx
D Additional proofs
Theorem D.1. Let Σ denote the set of sequences of the learning player in the extensive-form
game, and let (0 = 1/vī for all I. Then, for any sequence of loss vectors g()) E [0,1]3 Algo- rithm guarantees linear-swap regret 0(E)/T/T)) after any number T of iterations, and runs in O( [og(( El) log" 1) time for each iteration L.
Proof of Theorem 3.2. First we focus on the linear-swap regret bound. Based on Gordon al. [2008] the 2-regret equals external regret over the set & of transformations. In our case & is the set Mo- of all valid linear transformations and the losses for the external regret minimizer are functions A (E(1), Az) A (((2), (x) .... Equivalently, where ( is the component-wiss inner product for matrices and (() g(t) (ax()))T which is a rank-one matrix. Let D be an upper bound on the diameter of Mo+ and L be such that [|] < L for all t. Then, based on Orabona [2022] we can bound the external regret for this instance of Online Linear Optimization by picking r) = LVe which gives a regret of O(DLVT).
write these A + (L( A) F.
D.
Since A E [0, 1| we get D = |Σ|, and since {(t) (0()) E [0, 1 we get I. = E. This results in the desired linear-swap regret of O()))TT).
However, in previous analysis assumed that it is possible compute exact solution (++1) Me .e (A (() of the projection step, which is an instance of convex quadratic programming, meaning that we can only get an approximate solution [Vishnoi, 2021]. J. the following Lemma we prove that e-approximate projection does not affect the regret for single iteration of
20

---

the algorithm, if E is sufficiently small. The inequality we prove is similar to the one in Lemma 2.12 from Orabona [2022].
Lemma D.2. Let Y = MLMe-l (A - (0) and suppose that A (++1) E Mo- is such that
|| (++1) Y 1 S (t) then for any X E MM it holds
(L X A (1))
1
(1(+)) -X12 +
(0)
L
D 17(1) e(t)
27(())
27((3)
Proof. From Lemma 2.12 of Orabona [2022] we know that
(L X - A S
1
AA (0)
Y - X
1 +
1700)
(1) I
21yl0)
2ny(0)
2
Additionally, it holds that
|
(t-1) (t-1) X p || (H41) Y + Y - x
((++)) Y Y X + ((41) Y,, Y" Y"-X-= F))
I Y -X + 2(A (1-1) - -Y", -Y'AA(H) A(H1) +Y xX
YY X| + 2
2(A((-1) (t-1)
-Y,, -X)F
Y X A
(1+1) -Y-IIAAAA X||r
S YY X + (1)
The Lemma follows by combining the previous two inequalities.
If we set (+) 1/t5/2 then for our choice of r7 =D_ "Vi the error term becomes L/t?. Summing over timesteps we thus get an additive error of O(L) = O(EE)) the regret, and our total linear-swap regret bound remains ((E))VT).
We now move to analyzing the per-iteration time complexity of Algorithm 1. The most computation- ally heavy steps are (5) and (6). To compute the fixed point at step (6) we can use any polynomial time LP algorithm. We can also perform the projection step (5) in polynomial time using the ellipsoid method [Vishnoi, 2021]. For this we reduce it to a suitable Semidefinite Program with (( variables and use the Cholesky factorization [Gärtner and Matousek, 2014] as the separation or- acle, thus responding to separation queries in O(E))) time. Note that it is possible to guarantee ||A (1+1) - 11 3 (1) as the ellipsoid method can output point A (++1) MM such that [|
|A (0) - (0 - A [++1) < ||A() - (() - YY"I + e and furthermore, the Frobenius norm a 2-strongly convex function.
To apply the ellipsoid method we further need bounds on the Frobenius norm of Y E MM and the maximum projection distance. For the norm of Y, we pick an upper bound of R = D = [ For the lower bound r we note that Yx E Q for all x E Q. which implies Yiø| = = | 2 1. Thus we get 2 ΣT. Similarly, we bound the projection distance between 0 and D. Based on
these bounds and on Theorem 13.1 from Vishnoi [2021] conclude that the total per-iteration time complexity of Algorithm I is O (12)10 log((2]) log2())) (t)).
Theorem 4.1. For two-player, perfect-recad extensive-form games with chance moves, the problem MAXPAY-LCE is not solvable polynomial time, unless P=NP.
Proof. We use the exact same argument employed in the paper by von Stengel and Forges [2008] by reducing SAT to the MAXPAY-LCE problem. Specifically, for each instance of SAT having n clauses and m variables we construct two-player extensive-form game of size polynomial in n and m. the beginning, there a chance move that picks one of possible actions uniformly at random one for each SAT clause. Then is the turn of Player 2 who has distinct singleton information sets corresponding to the chance node actions, and respectively to the n clauses of the SAT instance. Let
L, be the set of literals (negated non-negated variables) included in the i-th clause of the SAT
21

---

instance. In information set i of Player there exist | actions, one for each literal in L, Finally, each literal leads to different decision node for Player who has as many decision nodes as the number of literals in the SAT' instance, and in each node there exist exactly 2 possible actions: TRUE and FALSE. However, Player only has m information sets corresponding to the m SAT variables with each information set grouping together all nodes corresponding to literals of the variable This way, Player only chooses the truth value of a variable without knowing from which literal Player 2 has picked this variable. The utilities for both players are equal to if the truth value picked by Player satisfies the literal picked by Player and both utilities are otherwise.
In this game, there exists a pure strategy attaining payoff 1 for each player if and only if the SAT instance is satisfiable namely Player always acts based on the satisfying assignment and Player picks for every clause a literal that is known to be TRUE. Otherwise, the maximum payoff for each pure strategy
most - 1/n. Given that LCE describes convex combination of pure strategies, it follows that the maximum total expected payoff of the the sum of the two players' utilities will either be 2 when the SAT instance satisfiable, or it will be at most 2(1 1/n) when the instance not satisfiable. Additionally, this holds not just for the sum but for any linear combination of player utilities. Thus, the problem of deciding whether MAXPAY-LCE can attain a value of least is NP-hard for any linear combination of utilities.
E Examples
Example E.1 (EFCE + LCE), Consider the following 2-player signaling game presented by von Stengel and Forges [2008]
1/2
Player
Nature
O Player 2
Terminal node
G
B
Information set
N
YG
X
Ví
Y
4
10
Below are the normal-form payoff matrix the signaling game (left) and the extensive-form correlated equilibrium (right) given by von Stengel and Forges [2008]:
2
Ixly
Ixry
rxly
TXPY
Ixly
IxTy
rxly
TXPY
XcXB
5,5
5,
0, 6
0, 6
XeXB
0
1/4
0
0
XGYB
5,5
2, 8
3.3
0,6
XeYB
0
1/4
0
0
YgXB
5,5
3,3
2, 8
0,6
YeXB
0
1/4
YeYB
5,5
5,5
0,6
YOYB
0
1/4
22

---

However, we can observe that this EFCE is not linear-deviatio correlated equilibrium because, for example, Player I can increase their payoff by value 3/2 using the following transformation:
XGXB XeXB
i.e. map the reduced-nor
plan (1,0,1,0) (1,0,
XeYB XcXB
i.e., map the deduced-norman normal-form plan (1,0,0,1) + (1,0,1,0)
YGXB YeYB
i.e., map the reduced-normal normal-form plan (0,1,1,0) (0,1,0,1)
YoYB + YGYB
i.e., map the pallced-normale normal-form plan (0,1,0,1) -0, (0, 10,1,
(Above, have implicitly assumed that the strategy vectors encode probability of actions in the arbitrary order XG. YG, XB. YB). The above transformation is linear, since it can be represented via the matrix
This would swap the pure strategy XGYB with XGXB B and strategy YGXB with YGYB. Crucially, the strategy the subtree of information set G. Thus, the transformed value for each sequence does not purely depend on the ancestors of that sequence. but can also depend on strategies belonging to "sibling" subtrees. Hence, this example proves that LCE + EFCE.
determined by the strategy the subtree of information
In fact, we can even verify that in this toy example the of LCE coincides with the of all normal-form CE. We refer the interested reader to von Stengel and Forges [2008] for more detailed discussion of the different behaviors that players exhibit EFCE normal-form CE, which in this specific example also corresponds to a comparison between the EFCE and the LCE.
Remark E.2. The linear transformation given Example E. also serves to show that the Behav- ioral Deviations defined in Morrill et al. [2021] not superset of all linear transformations. Additionally, behavioral deviations are not a subset of linear transformations, as the latter act only incomparable.
on reduced strategies. Thus the two sets of deviations
Example E.3 (LCE + CE). This example was found through computational search. Consider the 2-player game with the following game tree:
Legend
Player
X
Nature
O Player
Terminal node
Information
1/4
A2
B
A
B2
B2
B
Q
W
W
-310
2
202
-315
2
4
Based the previous game tree, the normal-form payoff matrix of the game is shown below.
23

---

2
Q:Wi
Q.W,
Q.Wi
Q.W,
A
50.5, 0.0
50.5, 0.25
-27.75, -78.75
-27.75,
B2
0.0, 0.0
0.5, 1.0
-0.75, 0.0
-0.25, 1.0
A
50.0, 0.5
49.5, -0.75
-27.5, -79.5
A2
-0.5, 0.5
-0.5, 0.0
0.0, 0.5
0.0, 0.0
We can now verify that the following is linear-deviation correlated equilibrium for this game. The verifcation can be done computationally by expressing all constraints of Theorem 3.1 as a Linear Program.
Q.W
Q.
Q,Wi
Q,W,
A
1/5
0
0
0
A
0
1/5
0
0
A
1/5
0
A2 B2
0
1/5
1/5
However, the swap [A1 + B1, A2B1 + B1 can increase player I's payoff by 50.5.
Furthermore, verify thut this swap is not linear follows. First assume that it was linear and could be written as matrix E (0, 185X, Then the matrix has to be consistent with the following transformations:
A + A,
A₁ + A,
AgB A
A₂ + A₂B2
For convenience of referring to matrix rows and columns we number the four sequences as:
:1:0, A2:
B :2:2
B2:3 33
If we focus on the second transformation, A, + A, we conclude that A|: 0] + A|:.3] 3, A[1,3] A[3.3] = Now, if we subtract the respective equations of the last Iwo swaps get A A|: -1,-,,,
(1, 1,0)T which implies that A[1,
Since A E [0, 1] 1| the last equation implies A[1,3] = which contradicts the previous constraint of A|1, 0. Thus, have found valid normal-form swap that cannot be expressed as a linear transformation of sequence-form strategies. Hence, this example proves that LCE # CE.
Details on Empirical Evaluation
In this section we provide details about the implementation of our algorithm, as well the compute resources and game instances used.
24

---

Implementation of our no-linear-swap--rege dynamies We implemented our no no-linear-swar regret algorithm (Algorithm 1) in the C++ programming language using the Gurobi commercial optimization solver [Gurobi Optimization, LLC., 2023], version 10. We use Gurobi for the following purposes.
To compute the projection needed on Line 5 of Algorithm 1. We remark that while Gurobi linear and integer linear programming solver, modern versions include tuned code for convex quadratic programming. In particular, we used the barrier algorithm to compute the Euclidean projections onto the polytope Me- required at every iteration of our algorithm.
is typically recognized
To compute the fixed points of the matrices A E Mo- that is, finding Q 9 a = Ax. As discussed in Section 3 this is polynomially-sizen linear program.
To measure the linear-swap regret incurred after any T iterations, which is plotted on the y-axes of Figure 2. This corresponds to solving the linear optimization problem
T
Σ ell
(( Ax
max AeMo-o
T
We did very minimal tuning of the constant learning rate used for online projected gradient descent, trying values E {0.05, 0.1, 0.53 (we remark that a constant value of 1j Re 1/vT is theoretically sound). We found that 7 = 0.1, which is used in the plots of Figure 2, performed best.
Implementation of ne-rritger-regret dynamies We implemented the no-trigger-regret algorithm of Farina et al. [2022] in the C++ programming language. In this case, there is no need to use Gurobi, since, as the original authors show, the polytope of trigger deviation functions admits a convenient combinatorial characterization that enables us to sidestep linear programming, Rather, we implemented the algorithm and the computation of the trigger regret directly leveraging the combinatorial structure.
Computational resources used Minimal computational resources were used. All code ran on a personal laptop for roughly 12 hours.
Game instance used We ran our code on the standard benchmark game of Kuhn poker Kuhn [1950]. We used three-player variant of the game. Compared to the original game, which only considers a simplified deck make of cards out of only three possible ranks (Jack, Queen, or Kind), we use full deck of 13 possible card ranks, The game has 156 information sets, 315 sequences, and 22308 terminal states.
G Further Remarks on the Reduction from No-O-Regret to External Regret
A no- no-4-regreet algorithm is typically defined as outputting deterministic behavior from finite set X' (for example, deterministic reduced-normal- normal-form plans in extensive-form games, or actions in normal-form games), which can be potentially sampled at random. This is the setting used by, for example, Hart and Mas-Colell [2000] and Farina et al. [2022]. However, we remark that when the transformations à E Φ are linear, any such device can be constructed starting from an algorithm that outputs points x' E X' = conv (X'), and then sampling æ unbiasedly in accordance with x', that is, so that EE [x]]] = x'. The reason why this is useful is that constructing the latter object is usually simpler, as X' optimization techniques that have been developed over the years.
closed and convex set, and is therefore amenable to the wide array of online
More formally, let be a of linear transformations that map to itself. A no- no-h-regret algorithm for X" conv(2t) guarantees that, matter the sequence of loss vectors g())
T
Rd (T) max OED [=1
Σ
(e0), x (() ((x((t)))
grows sublinearly. Consider now algorithm that, after receiving t0 conv(X'), samples (+)) E X' unbiasedly, that is, so that E(x(()) (()) Then, by linearity of the transformations and
25

---

using the
concentration inequality, we obtain that for any > 0,
T (eto x -)(x(())) so (VIlOS _
P R
max PEO
21-6,
where the big- thetthe notation hides constants that depend on the payoff range of the game and the diameter of X' (a polynomial quantity in the game tree size). This shows that as long as the regret of the no- no-9-algorithm that operates over X' is sublinear, then so is that of an algorithm that outputs points on X' by sampling unbiasedly from X, We refer the interested reader to Section 4.2 ("From Deterministic to Mixed Strategies") of Farina et al. [2022].
26


Reviews:
[{"review_id": "HdST9ljL9S", "reviewer": "Reviewer_V8FX", "summary": "This paper focuses on addressing the challenge of minimizing linear swap regret in extensive form games, which is considered a stronger notion compared to trigger regret in Extensive Form Correlated Equilibrium (EFCE). To achieve efficient implementation of the Phi-regret minimization problem (where Phi set contains all linear swap transformation), the authors provide a polynomial-sized description of all linear swap operators. This result shows that there exists a no linear swap regret algorithm with polynomial-time iteration complexity based on the size of the game tree. Additionally, the paper presents experimental results that illustrate how the equilibria achieved through the no linear swap regret algorithm exhibit greater strength compared to EFCE.", "questions": "1. Is there any intuition behind the linear swap transformation, apart from its linearity? For instance, can LCE be interpreted with the presence of a mediator? Why do you believe LCE is an equilibrium worth considering?\n\n2. Maximizing social welfare is known to be challenging. However, in your experiments, did you observe any significant differences in social welfare between No-linear-swap-regret dynamics and No-trigger-regret dynamics?\n\n3. Since No-linear-swap-regret dynamics are stronger than No-trigger-regret dynamics. The result in Figure 2 is expected. What about the running times? Is the running time of no-linear-swap-regret dynamics substantially larger?\n\n[1] Zhang, Brian, and Tuomas Sandholm. \"Polynomial-time optimal equilibria with a mediator in extensive-form games.\" Advances in Neural Information Processing Systems 35 (2022): 24851-24863.", "limitations": "The authors have partially addressed the limitations of their work, though there is space for improvement (see the section Weaknesses).", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper introduces a novel and essential contribution by providing a polynomial characterization of the set of all linear transformations from a sequence-form strategy polytope to itself. This characterization holds significant value for future research on linear-swap-regret.\n\n\n", "weaknesses": "The contribution of this paper may be perceived as limited. The primary and significant contribution lies in the polynomial description of the linear swap transformation set. Given the sequential structure of the sequence form strategy, this finding is not entirely unexpected.\n\nIt appears that the paper lacks some intuitive explanations regarding the concept of linear swap (further details can be found in the questions raised). There is a sense that LCE (Linear Swap Correlated Equilibrium) is merely one equilibrium between CE (Correlated Equilibrium) and EFCE (Extensive Form Correlated Equilibrium), which is relatively easy to compute. The experimental results may not comprehensively demonstrate the potential and strength of LCE\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and observations on our work. Below we address the questions raised.\n\n(Q1) We believe linear-deviation correlated equilibria (LCEs) are most naturally understood as the name of the equilibrium points that emerge from the higher-rationality no-regret learning agents we construct. To recap briefly, our main goal in this paper is to make progress on the challenging question of what is the strongest notion of no-regret learning/hindsight rationality that can be attained in polynomial time in imperfect-information sequential multiagent settings. The best prior results only applied to extremely structured and isolated subsets of linear transformations, including EFCE deviations and communication deviations (exhibiting a large gap compared to what is instead possible in matrix/nonsequential games, where no-swap-regret can be attained efficiently). In our paper, we show that learning to be robust (i.e. not regret) **any** linear transformation can be guaranteed in polynomial time, subsuming virtually all prior known notions (including EFCCE, EFCE, and the very recent work on communication equilibria in Bayesian games by Fujii [1]). Another reason to care about this notion of rationality is that it has been recently shown by Mansour et al. [2] that all weaker notions of rationality automatically allow the environment to exploit the agent.\n\nOne can also think of LCE in the context of a mediator (correlation device) that samples strategy profiles and recommends the corresponding pure strategies to players. The mediator’s concern is to find a correlated distribution of play such that no player would be better off by deviating unilaterally using any linear transformation of their strategy. This is akin to, but significantly more general than, EFCE, where the players can only use trigger deviations, a special class of linear transformations. However, while trigger deviations can be re-interpreted as the players being able to transform behavior conditionally only on the recommendation of one information set, we do not know if such an intuitive interpretation can be given about the set of all linear deviations. While this paper is mostly focused on the learning and computational aspects, exploring these game-theoretic modeling questions for LCE is an interesting question for future work.\n\n[1] Kaito Fujii, 2023. Bayes correlated equilibria and no-regret dynamics. Arxiv.\n\n[2] Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan, 2022. Strategizing against learners in bayesian games. COLT.\n\n(Q2) Thanks for the interesting question. Since LCE is a subset of EFCE, the maximum social welfare that can be achieved by LCE can only be $\\leq$ of that reachable by EFCE (intuitively, the agents are more rational, so it takes more effort to incentivize them towards any correlated behavior). Indeed, we empirically observe that the utility reached by LCE is lower than that of EFCE in the experiments of Figure 2. You can observe this for example in the experimental data we included in the supplemental material, together with the implementation of our dynamics.\n\n(Q3) One thing we wanted to demonstrate with Figure 2 is that in practice there is indeed a perceptible difference between the regret achieved by no-swap and no-trigger regret dynamics, even in fairly small and simple games.\n\nThe per-iteration time complexity of our linear-swap regret minimization algorithm is worse than that of the trigger-regret minimization algorithm, due to the projection step and the explicit computation of the fixed point (steps (5) and (6) of Algorithm 1). While the algorithm that we provide in the paper (based on the ellipsoid method) is enough for showing that minimizing linear-swap regret can be done in polynomial-time, we conjecture that a better understanding of the geometry of the linear deviations polytope could enable sidestepping the expensive ellipsoid method used in our projection step and lead to provably and practically better running times. We leave this interesting question for future work.\n\n(W) Finally, we would like to leave a small comment on the sentence \"Given the sequential structure of the sequence form strategy, this finding is not entirely unexpected.\" from the Weaknesses section. Specifically, we would like to highlight that the proof of this characterization is very far from trivial, as is also evident from the appendix included in the supplemental material.\n"}, {"review_id": "Zsc4tgSOvs", "reviewer": "Reviewer_vZdR", "summary": "The paper studies regret minimization in extensive-form games (EFG). Specifically, they study a notion of regret called linear-swap regret, which measures the regret against linear transformations of the player's sequence-form strategies. This notion is stronger than trigger regret (as trigger deviations can be described as a linear transformation of sequence-form strategies) but weaker than swap regret.  \n\nThe main technical contribution lies in Theorem 3.1, which states that the set of linear transformations (from the set of sequence-form strategies to itself) is a compact polytope defined by a polynomial (in the game tree size) number of linear constraints. \n\nWith that in hand, they leverage the template of Gordon et al. [2008] that produces a $\\Phi$-regret minimization algorithm given a no-external-regret minimizer $\\Phi$ and a fixed point oracle which returns fixed point of transformations in $\\Phi$. In this context, the $\\Phi$-regret minimization can be chosen, for example, to be Online Gradient Decent; and the fixed point oracle can be implemented using a Linear Programming Solver (e.g., Ellipsoid algorithm). This results in an efficient algorithm that achieves $\\sqrt{T}$ linear-swap regret; which in turn also implies an efficient method for finding the correlated equilibrium that corresponds to linear transformations, that the authors call linear-deviation correlated equilibrium (LCE).\n\nFinally, the authors provide examples to show that the set of LCEs strictly contain**s** the set of CEs, and is strictly contain**ed** in the set of Extensive-form correlated equilibrium (EFCE). They also show that the set of Behavioral correlated equilibrium (BCE) and the set of LCEs are incomparable.\n\n", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is written well; the authors give great background on EFGs, on different notions of correlated equilibrium, and their relation to different notions of regret. \nThe construction of the algorithm and results are fairly easy to understand, and the authors express well the difference between their results and previous work by providing examples that compare their notion of equilibrium with existing notions.\nFinally, I agree that determining *\"what is the strongest notion of rationality that can be attained efficiently\"* is an interesting open problem, and indeed the paper provide some progress in this direction.", "weaknesses": "- There is no obvious algorithmic contribution here: As noted, Theorem 3.1 is the main technical contribution which is purely geometric. Given that, constructing the algorithm is fairly straightforward with the scheme of Gordon et al. [2008].\n- While the background the paper gives is quite solid, it is not very proportional to the relatively small amount of attention the authors give to their technical contribution. In particular, while the statement of Theorem 3.1 is clear, it is not very intuitive, and it is hard to understand why it is correct. This is also the main reason that my confidence score is relatively low. I think that some of the preliminaries, as well as the empirical evaluations, could be deferred to the appendix - instead, I think that giving the main proof ideas is more important.\n\n**Missing related work:** I think that the work of Anagnostides et al. (2022) is very relevant here and motivates important questions for future work. Specifically, this work achieves a much better rate of $\\log T$ for trigger regret. Thus, it is fairly natural to ask whether this is also attainable for linear-swap regret, especially since they also built upon the template of Gordon et al. [2008].\n\nAnagnostides, I., Farina, G., & Sandholm, T. (2022). Near-Optimal $\\Phi $-Regret Learning in Extensive-Form Games. arXiv preprint arXiv:2208.09747.‏", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and observations on our work. Below we address the weaknesses discussed:\n\n(W1) The geometric contribution is the key to the algorithmic contribution of the paper: the structure provided by our characterization theorem (Thm 3.1) is what enables constructing agents minimizing regret with respect to all linear deviations in polynomial time in imperfect-information sequential games. Hence, one cannot untangle the two: without the geometric contribution, there is no algorithmic contribution.\n\nAs correctly mentioned in the review, Gordon et al. [2008] provide an elegant recipe for constructing a no-$\\Phi$-regret algorithm, as long as two key ingredients can be provided: a polynomial-time (per iteration) no-external-regret algorithm for the set of deviations $\\Phi$, and an efficient fixed point oracle. The first of these components can be rather complicated, as is the case in our paper, since the structure of the set of deviation functions $\\Phi$ can be arbitrarily complex.\n\n\n(W2) Thank you for proposing this improvement in our paper presentation. Since the camera ready allows an extra content page, we will use that to include a more detailed intuition of its main proof ideas. We include here below a more high-level, intuitive description of the theorem and the challenges arising in its proof.\n\nThe proof proceeds by induction on the game tree as follows:\n\n* The Base Case (appendix, pg. 15) corresponds to the case of being at a leaf decision point, that is, an information set for which all actions lead to termination of the game. In this case, the set of deviations corresponds to all linear transformations from a probability $n$-simplex into a given polytope $\\mathcal{P}$ in $\\mathbb{R}^d$. This set is equivalent to all $d$ x $n$ matrices whose columns are points in $\\mathcal{P}$, which is not hard to verify mathematically. This corresponds to constraint (3) of our characterization.\n\n* For the inductive step, we are at an intermediate decision point (information set of the learning player), that is, one for which at least one action leads to further decision points. Let j be the decision point.  \n\n  In Lemma B.8 we show that any terminal action a at j (that is, such that no further decision points follow under that) leads to a column in the transformation matrix that is necessarily a valid point in the polytope $\\mathcal{P}$. This is similar to the base case, and leads to constraint (3) in our formulation.  \n\n  In Lemma B.7, we look at the other case of a nonterminal action a at j (that is, such that one or more further decision points follow under that) is such that the corresponding column in the transformation matrix is identically 0 (constraint (4)) without loss of generality. This allows for the \"crux\" of the transformation to happen in the subtree rooted at ja. A key difficulty is in characterizing all valid transformations at such a subtree. In particular, several decision points can have ja as their parent sequence. The set of strategies in the subtree rooted at ja is therefore in general the Cartesian product of subtrees rooted at each of the decision points whose parent sequence is ja. This intuitively explains the need for the (fairly technical and involved) Proposition B.4, whose goal is to precisely characterize valid transformations of Cartesian products. The characterization for the Cartesian products leads to constraints (5) and (6) in our final characterization.\n\n\n(Missing related work) Thank you for the intriguing question, we will definitely include a discussion about that paper in the revision. The question as to whether $O(\\log T)$ regret per-player can be attained in self-play is very interesting. While the paper you mentioned proposes a general methodology that applies to CEs in normal-form games and EFCE/EFCCE in sequential games, the authors’ construction fundamentally relies on being able to express the fixed points computed by the algorithm as (linear combinations of) rational functions with positive coefficients of the deviation matrices. In the case of CEs, this characterization follows from the Markov chain tree theorem, while in EFCE and EFCCE this fundamentally follows from the fact that the fixed points can be computed inductively, solving for stationary distributions of local Markov chains at each decision point. In the case of linear transformations considered in our paper, such a local characterization of the fixed point is unknown. We will definitely include a discussion about this, thanks again for the suggestion.\n"}, {"review_id": "JoXODODEJf", "reviewer": "Reviewer_qFDY", "summary": "This paper studies the convergence of uncoupled strategies to a weakened notion of equilibria called \"linear-deviation correlated equilibrium\". This equilibrium is reached when all players minimise the no-linear-swap regret which is a specialisation of Phi-equilibria when the set of deviations Phi is the set of all linear transformation from the set (mixed) strategy to itself.\nThe authors provide efficient implementation of such no-linear-swap regret algorithms and prove that the set of linear-deviation correlated equilibria is a subset of extensive form correlated equilibria. The technical tool used is the of of Gordon 2008 which converts a regret minimiser for the space of deviations to a regret minimiser for the strategy set.", "questions": "1) Th 31 seems to be the main technical statement of the paper. What are the main challenges of proving this statement? A better intuition of its implications/design would be appriciated\n2) Motivate LCE (see Weaknesses)\n3) Figure 2 only proves that the inclusions of CE, LCE and EFCE are strict, but is somewhat uninteresting once we have a theorem stating it. What happens is in Figure 2 left you put there time instead of iterations? If the no-linear-swap regret algorithm runs faster then the one that minimises only the trigger-regret this would be a better algorithm for finding EFCEs.", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper aims to solve an important problem, which is the complexity of CE in EFG.\nThe paper is easy to read, clear and well written and the results seems non-trivial", "weaknesses": "The notion of LCE is not well motivated. The authors prove that LCE are EFCE but, while EFCE are well motivated in EFG, LCE do not seems to have any practical meaning. Also the algorithm presented in the paper is slower at converging to EFCEs then the one specifically designed for them (Figure 2 left) and thus do not contribuite in this regard.\nThe main weakness is that LCE are not an interesting equilibrium to converge to, except from their connection to EFCEs. The author should motivate the introduction of this new equilibria for example by finding examples in which LCE are a reasonable solution concept while other EFCEs are not. Without this the point the paper seems a technical exercise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and observations on our work. Below we address the 3 questions raised:\n\n(Q1) Thanks for the feedback. As mentioned to Reviewer vZdR, we will use the extra content page to revise our paper and include a more detailed intuition of its main proof ideas. We include a high-level, intuitive description of the theorem and the challenges arising in its proof in our response to Reviewer vZdR.\n\n(Q2) We disagree that LCE is interesting only in relation to EFCE. No-trigger-regret agents are robust (hindsight rational) only to trigger deviations, which are a measure-zero set of linear transformations. The question as to what is the highest notion of regret that can be minimized efficiently in imperfect-information sequential games is natural and established. An interesting recent development by Mansour et al. [1] is that all notions of rationality weaker than ours automatically allow the environment to exploit the agent. We believe that the play of higher-rationality no-regret learning agents is intrinsically interesting. LCE is the name of the equilibrium points reached by such agents. We expect that future work will analyze LCE’s game-theoretic properties beyond the online learning-related properties already uncovered by us and Mansour et al.\n\n[1] Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan, 2022. Strategizing against learners in bayesian games. COLT.\n\n(Q3) One thing we wanted to demonstrate with Figure 2 is that in practice there is indeed a perceptible difference between the regret achieved by no-swap and no-trigger regret dynamics, even in fairly small and simple games.\n\nOur no-linear-swap-regret algorithm can be used to minimize any kind of regret that linear-swap deviations subsume (such as the trigger regret). However, the per-iteration time complexity of our linear-swap regret minimization algorithm is worse than that of the trigger-regret minimization algorithm, due to the projection step and the explicit computation of the fixed point (steps (5) and (6) of Algorithm 1). While the algorithm that we provide in the paper (based on the ellipsoid method) is enough for showing that minimizing linear-swap regret can be done in polynomial-time, we suspect that a better understanding of the geometry of the linear deviations polytope could enable sidestepping the expensive ellipsoid method used in our projection step and lead to provably and practically better running times. We leave this interesting question for future work.\n"}, {"review_id": "tS6sh3lnaq", "reviewer": "Reviewer_Dcee", "summary": "Authors introduce a new class of correlated equilibria called linear-deviation correlated equilibria, which can be approached efficiently if all players attain sublinear linear-swap regret.\nThey show LCEs are distinct from correlated equilibria and extensive-form correlated equilibria and the hardness of maximizing social welfare in LCEs. Finally, they show the difference in no-linear-swap-regret dynamics and no-trigger-regret dynamics to support their theoretical results on a small game. ", "questions": "- I think it would be of great pedagogical value to make a visual depiction of the different classes of equilibria similar to https://www.cs.cmu.edu/~ggordon/CE/ -- but I understand this might not be possible because the high dimensionality of the joint strategy space. \n- Do you think there exists a linear program to find LCEs? If not, why?\n", "limitations": "Limitations are adequately addressed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Introduction of new correlated equilibrium class.\n- Technical contribution of a polynomial characterization of the set of all linear transformations from a sequence-form strategy polytope to itself.\n- General algorithm for minimizing linear-swap regret.\n- Shows relation to existing equilibrium classes.\n- Very clearly written paper that I expect will be built upon in the future.\n", "weaknesses": "- This is a theoretical paper and it is not clear what would be the motivation to approach LCEs in practice, compared to another correlation classes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and observations on our work. Below we address the questions raised and the discussed weaknesses:\n\n(Q1) Thank you, that would indeed be interesting. As you hinted, one likely key difficulty in constructing such a representation is the fact that interesting sequential games (even when extremely simple) tend to have a relatively large number of strategy profiles, which might make a low-dimensional visualization impossible. We remark that focusing on games with sequential moves is necessary in this case, as the special case of normal-form games is not interesting enough since there the EFCE, LCE and CE all coincide. However, we will try to see what we can do for the final version.\n\n(Q2) We agree that this is a very interesting question, to which we also alluded in the future work section (Section 5). In particular, we suspect that it might be possible to devise an efficient centralized algorithm making clever use of LPs in the spirit of Ellipsoid Against Hope that is able to compute one LCE. That is, an algorithm that computes some valid LCE which, however, is not guaranteed to be optimal in any sense. On the other hand, using an LP to *optimize* over the set of LCEs is impossible due to complexity barriers (Thm 4.1).\n\n(W1) Our goal in this paper is to make progress on the challenging question of what is the strongest notion of rationality that can be efficiently attained in EFGs. We believe that the linear-deviation correlated equilibrium (LCE) is worth defining because it emerges from these no-linear-swap regret dynamics, which constitute a natural class of learning dynamics.\n\nAn interesting recent development by Mansour et al. [1] is that all notions of rationality weaker than ours automatically allow the environment to exploit the agent. We believe that the play of higher-rationality no-regret learning agents is intrinsically interesting. LCE is the name of the equilibrium points reached by such agents. We expect that future work will analyze LCE’s game-theoretic properties beyond the online learning-related properties already uncovered by us and Mansour et al.\n\n[1] Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan, 2022. Strategizing against learners in bayesian games. COLT.\n"}]

Author rebuttal:
We thank all the reviewers for the detailed comments and constructive feedback. We have addressed the reviewers’ comments/questions individually below.

Meta-review: This paper proposes a new notion of correlated equilibrium called linear-deviation correlated equilibrium (LCE) for extensive-form games (EFGs) that is stricter than the commonly studied EFCE, yet still admits polynomial-time algorithm using an explicit characterization of the strategy deviation set. After rebuttal, all reviewers are positive about the contributions of this paper to the EFG literature. Therefore I recommend acceptance.
Decision: Accept (poster)