Efficient $\Phi$-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games
Authors: Brian Hu Zhang
Ioannis Anagnostides
Gabriele Farina
Tuomas Sandholm
Venue: NeurIPS 2024 poster (2024)
Keywords: swap regret
extensive-form games
low-degree deviations
Primary area: algorithmic_game_theory
TL;DR: We develop algorithms to efficiently minimize swap regret with respect to the set of low-degree deviations in extensive-form games.

Abstract: Recent breakthrough results by Dagan, Daskalakis, Fishelson and Golowich [2023] and Peng and Rubinstein [2023] established an efficient algorithm attaining at most $\epsilon$ swap regret over extensive-form strategy spaces of dimension $N$ in $N^{\tilde O(1/\epsilon)}$ rounds. On the other extreme, Farina and Pipis [2023] developed an efficient algorithm for minimizing the weaker notion of linear-swap regret in $\mathsf{poly}(N)/\epsilon^2$ rounds. In this paper, we develop efficient parameterized algorithms for regimes between these two extremes. We introduce the set of $k$-mediator deviations, which generalize the untimed communication deviations recently introduced by Zhang, Farina and Sandholm [2024] to the case of having multiple mediators, and we develop algorithms for minimizing the regret with respect to this set of deviations in $N^{O(k)}/\epsilon^2$ rounds. Moreover, by relating $k$-mediator deviations to low-degree polynomials, we show that regret minimization against degree-$k$ polynomial swap deviations is achievable in $N^{O(kd)^3}/\epsilon^2$ rounds, where $d$ is the depth of the game, assuming a constant branching factor. For a fixed degree $k$, this is polynomial for Bayesian games and quasipolynomial more broadly when $d = \mathsf{polylog} N$---the usual balancedness assumption on the game tree. The first key ingredient in our approach is a relaxation of the usual notion of a fixed point required in the framework of Gordon, Greenwald and Marks [2008]. Namely, for a given deviation $\phi$, we show that it suffices to compute what we refer to as a fixed point in expectation; that is, a distribution $\pi$ such that $\mathbb{E}_{x \sim \pi} [\phi(x) - x] \approx 0$. Unlike the problem of computing an actual (approximate) fixed point $x \approx \phi(x)$, which we show is \PPAD-hard, there is a simple and efficient algorithm for finding a solution that satisfies our relaxed notion. As a byproduct, we provide, to our knowledge, the fastest algorithm for computing $\epsilon$-correlated equilibria in normal-form games in the medium-precision regime, obviating the need to solve a linear system in every round. Our second main contribution is a characterization of the set of low-degree deviations, made possible through a connection to low-depth decisions trees from Boolean analysis.

Efficient Ø-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games
Brian Hu Zhang Carnegie Mellon University bhzhang@cs. cmu. edu
Ioannis Anagnostides Cameggi Mellon University ianagnos@cs. cmu. edu
Gabriele Farina MIT gfarina@mit. edu
Tuomas Sandholm
Carnegie Mellon University Strategic Machine, Inc. Strategy Robot, Inc. Optimized Markets, Inc. sandholm@cs. cmu. edu
Abstract
Recent breakthrough results by Dagan, Daskalakis, Fishelson and Golowich [2023] and Peng and Rubinstein [2023] established an efficient algorithm attaining at most swap regret over extensive-form strategy spaces of dimension N in NO(1/)) rounds. On the other extreme, Farina and Pipis [2023] developed an efficient algorithm for minimizing the weaker notion of linear-swap regret poly(N) rounds. In this paper, develop efficient parameterized algorithms for regimes between these two extremes. We introduce the set of k-mediator deviations, which generalize the untimed communication deviations recently introduced by Zhang, Farina and Sandholm [2024] to the case of having multiple mediators, and we develop algorithms for minimizing the regret with respect this set of deviations in NO( /e² rounds. Moreover, by relating k-mediator deviations to low-degree polynomials, we show that regret minimization against degree-k: polynomial swap deviations is achievable in (O(kd)) /e² rounds, where d is the depth of the game, assuming constant branching factor. For a fixed degree k, this is polynomial for Bayesian games and quasipolynomial more broadly when d Polylog.N-thh the usual balancedness assumption on the game tree. The first key ingredient in our approach is relaxation of the usual notion of fixed point required the framework of Gordon, Greenwald and Marks [2008]. Namely, for given deviation Φ, we show that it suffices compute what we refer to as a fixed point in expectation; that is, a distribution such that [o<x) æ] ss O. Unlike the problem of computing (approximate) fixed point æ xs d(x), which we show is PPAD-hard, there is simple and efficient algorithm for finding solution that satisfies relaxed notion. As a byproduct, we provide, to our knowledge, the fastest algorithm for computing e-correlated equilibria in normal-form games in the medium- regime, obviating the need to solve a linear system in every round. Our second main contribution is characterization of the set of low-degree deviations, made possible through a connection to low-depth decisions trees from Boolean analysis.
actual
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Introduction
Correlated equilibriam (CE), introduced in a groundbreaking work by Aumann [1974], has emerged as one of the most influential solution concepts in game theory. Often contrasted with Nash equi- librium [Nash, 1950], it is regarded by many Nobel laureate, Roger Myerson, "if there is intelligent life on other planets, in a majority of them, they would have discovered correlated equilibrium before Nash equilibrium." Correlated equilibria also enjoy more favorable computational properties: unlike Nash equilibria, they can be expressed as solutions to linear program, thereby enabling their computation in polynomial time, at least in normal-form games [Papadimitriou and Roughgarden, 2008, Jiang and Leyton- Leyton-Brown, 201 IJ. Further, correlated equilibrium arises through repeated play from natural no-regret learning dy- namics [Hart and Mas-Colell, 2000, Foster and Vohra, 1997].
natural; in the words attributed to another
However, many real-world strategic interactions feature sequential moves and imperfect in- formation. In such scenarios, the so-called extensive form constitutes the canonical game representation [Kuhn, 1953, Shoham and Leyton-Brown, 2009]: normal-form description of the game would be prohibitively large. It is startling to realize that 50 years after Aumann's original work, the complexity of computing correlated equilibria in extensive-form games-Ssometing referred to as normal-form correlated equilibria (NFCE) to disambiguate from other pertinent but weaker solution concepts-remains. an outstanding open problem [von Stengel and Forges, 2008, Papadimitriou and Roughgarden, 2008J.
The long-stann standing absence of efficient algorithms for computing an NFCE shifted the focus to nat- ural relaxations thereof, which can be understood through the notion of P-regrer [Greenwald and Hall, 2003, Stoltz and Lugosi, 2007, Rakhlin et al., 2011]. In particular, & represents set of strat- egy deviations; the richer the set of deviations, the stronger the induced solution concept. When t contains all possible transformations, one recovers the notion of corespooris regret. At the other end of the spectrum, coarse correlated equilibria correspond to + consisting solely of constant transformations (aka. external regret). Perhaps the most notable relaxation the extensive-form correlated equilibrium (EFCE) [von Stengel and Forges, 2008], which can be com- puted exactly in time polynomial in the representation of the game tree [Huang and von Stengel, 20083. Considerable interest in the literature has recently been on learning dynamics that minimize Ø-regret (e.g., Morrill et al. [2021a.b]. Bai et al. [2022], Bernasconi et al. [2023]. Noarov et al. [2023], Dudík and Gordon [2009], Gordon et al. [2008], Fujii [2023], Dann et al. [2023], Mansour et al. [2022]). A key reference point in this line of work is the recent construction of Farina and Pipis [2023], an efficient algorithm minimizing linear swap regref-that is, the notion of Ø-regret where contains all linear deviations. Such algorithms lead to an c-equilibrium in time polynomial in the game's 's description and 1/c-aka. fully polynomial-time approximation scheme (FPTAS).
swap
Yet, virtually nothing was known beyond those special cases until recent breakthrough results by Da- gan et al. [2024] and Peng and Rubinstein [2024], who introduced a new approach for reducing swap regret to external regret; unlike earlier reductions [Gordon et al., 2008 Blum and Mansour, 2007, Stoltz and Lugosi, 2005], their algorithm can be implemented efficiently even in certain settings with an exponential number of pure strategies. For extensive-fori games, their reduction implies a polynomial time approximation scheme (PTAS) for computing an e-correlated equilibrium; their algorithm has complexity (1/e)) for games of size N, which is polynomial only when is an absolute constant. Unfortunately. it was thereafter shown that in the usual regime of interest, where instead < pol)( an exponential number of rounds is inevitable even against an oblivious adversary [Daskalakis et al., 2024]. In light of that lower bound, our focus here is on developing al- gorithms attaining better complexity bound of poly(N, 1/e)-the typical guarantee one hopes for within the no-regret framework- by considering more structured but rich class of deviations &.
2 Preliminaries
Before we proceed by giving an overview of our results and technical contributions, we first intro- duce some basic background on tree-form decisions problems and h-regret minimization.

---

2.1 Tree-form decision problems
A tree-form decision problem describes a sequential interaction between a player and a (possibly adversarial) environment. There is tree of nodes. The root is denoted Ø. We will use S to denote a generic node, and p. (where $ + 2 to denote the parent of s. Leaves are called terminal nodes; generic terminal node is denoted points, where the player plays an action, observation points, where the environment picks the next decision point. generic decision point will be denoted j, and the set of actions at j will be denoted AJ. The child node reached by following action a E A, is denoted ja. We will use to denote the number of terminal nodes. We will also assume without loss of generality that all decision points have branching factor at least 2, and that decision and observation points alternate. Thus, the total number of nodes in the tree is also O(N). The depth of decision problem is the largest number of decision points in any not-to-terminal-ee depicted below in Figure 1.
Z. Internal nodes can be one of three types: deciston
path. An example of a tree-form decision problem is
A
T1
B
C
2
3
4
T2
23
24
255
Figure An example of a tree-form decision problem. Decision points are black squares with white text labels; observataion points are white squares. Edges are labeled with action names, which are numbers. Pure strategies in this decision problem are identified with vectors æ = (I), 22, 23, F4, vs) E 1] 1]s satisfying 1 - x2 + I3 xA + 235-
A pure strategy consists of an assignment of one action a E Ay to each decision point j. The tree-form representation of the pure strategy is the vector E {0, 1 where a: m[2] if and only if the player plays all the actions on the Ø + path. Although æ is a vector indexed only by terminal nodes, we also overload notation
1 if and only if the player plays all actions on the Ø + path (In other words, æ[s] = if there exists some 2 > s with ø[*] 1). Multiple pure strategies can have the same tree-form representation, but in this paper we will only concern ourselves with strategies in tree-form representation, and thus for our purposes such strategies will be treated as identical. We will use X C {0, 1) denote the set of tree-form strategies, and sometimes (when context is clear) we will also use X' to denote the tree-form decision problem itself. For a point in the convex hull of X, conv X, we also use the symbol x E conv X. For mixed strategies, we instead use æ E (()). When it is relevant, we assume that utilities are rational numbers representable with (oly(NV) bits.
write æ[s]
2.2 Regret minimization
In the framework of online learning, learner interacts with an adversary over sequence of rounds. In each round, the learner selects a strategy, whereupon the adversary constructs a utility function. Throughout this paper, we operate in the full feedback setting, wherein the learner gets to observe the entire utility function produced by the adversary after each round. We allow the adversary to be strongly adaptive, so that the (linear) utility function at the fth round (1() : 3 x - (u(*), x) can depend on the strategy of the learner at that round; this is a standard assumption (cf. the notion of leaky forecasts in the context of calibration [Foster and Hart, 2018J) that will be used for our lower bound (Theorem 3.3). We assume that utilities belong l {u : (u,, x) < Vo E X3. will be convenient to use ||œ||x == max (u, x) for the induced norm.
We measure the performance of an online learning algorithm as follows. Suppose that t C (conv X²x is set of deviations, If the learner outputs in each round mixed strategy ((() A(X),
3

---

its (time-average) 4 p-regrer [Greenwald and Hall, 2003, Stoltz and Lugosi, 2007] is defined as
Rega T
1
max PEP
E (o((xl))
=0(1))
In the special case where & contains only constant transformations, one recovers the notion of ex- ternal regret. On the other extreme, swap regret corresponds to & containing all functions A' + X..
is sometimes assumed that the learner instead selects each round a strategy x( E conv X. To translate (1) in that case, we introduce the extended mapping of deviation Φ X conv X as Φ² = (e [o(=')) where
conv X' + A(X) is a function that is consistent in the sense that ( [xx] = æ. A canonical example of such function the behavioral strategy map 3 conv X' + ( which returns the unique (ignoring actions decision points reached with probability zero) mixed strategy whose actions at different decision points are independent and whose expectation is æ: We give another example of a consistent map later in Appendix C.2. Accordingly, we let oh denote all extended mappings. In this context, Φ rr-regret is defined as
1 Regao T
Σ d0
d5 (x) -
max of E
We are interested in algorithms whose regret is bounded by c after T = poly(N, 1/c) rounds. We refer such algorithms as fully polynomial no-regret learners.
Remark 2.1. We clarify that all the algorithms allow mixed strategies. The fact that (I) contains expectation over x<() 7(()) is simply how f-regret is defined; at no point does the algorithm actually sample from x(1), Using deterministic algorithms is in line with most of the prior work the full feedback setting.
consider in this paper are deterministic, even when
3 Overview of our results
In this section, we present an overview of our results on parameterized algorithms for minimizing ø-regret in extensive-form games. We shall first describe our results for the special case of Bayesian games with two actions per player, and we then treat general extensive-form games.
3.1 Bayesian games
For now, assume that each player's strategy space is hypercube 13.. Hypercubes linear transformations of tree-form decision problems; in particular, for Bayesian games in which each player has exactly two actions, the strategy space of every player is, up to linear transformations, hypercube. Since our results are particularly clean for the hypercube case, we start with that.
First, we introduce the set of depth-k decision tree deviations $5 which can be described as follows. For each of & N rounds, the deviator first elects a decision point and receives rec- ommendation, whereupon the deviator gets to decide which action to follow in that decision point. More formally, the set of deviations o defined as follows:
1. The deviator observes an index jo E [N].
2. For i I,...,k: k: the deviator selects an index j, E [N], and observes æ[j.].
3. The deviator selects ag 1).
We call attention to the order of operations. In particular, each query j is allowed to depend on previously observed m[j]ss We can assume (WIOG) that the deviator always chooses & distinct indices j. Now, the set of deviations & : {0, 11 >> [0, 1] that can be expressed in the above manner is precisely the set of functions representable (randomized) depth-k decision trees on N variables. To connect ø with the concepts referred to earlier, we clarify that k = 1 corresponds to linear-swap deviations, while k = N captures all possible swap deviations. Our first result is parameterized online algorithm minimizing regret with respect to deviations in & & (All our results are in the full feedback model under strongly adaptive adversary.)
Theorem 3.1. There is an online algorithm incurring (average) - at most in NO /e2 rounds with per-round running time of N (K(k) fe.

---

Next, we consider the set D consisting of all degree-k polynomials Ø [0.1] - 10.13%. Our result for this class of deviations mirrors the one for o but with a worse dependence k.
Theorem 3.2. There is an online algorithm incurring $ polyrre most in NoW") rounds with per-round running time of NO(K)) //c.
We find those results surprising; we originally surmised that even for quadratic polynomials (A: 2) the underlying online problem would be hard in the regime where e I poly(1/N). We will elaborate on our technical approach for establishing those results in Section 4 coming up.
Hardness in behavioral strategies A salient aspect of the previous results, which was intention- ally blurred above, is that the learner allowed to output mixed strategy- probability over {0. 1 1)... In stark contrast, and perhaps surprisingly, when the learner is constrained to output behavioral strategies, that to say, points
a distribution
[0, 1] we show that the problem immediately be- comes PPAD-hard even for degree k = 2 (Theorem complexity assumptions. We are not aware of any such hardness results pertaining to natural online learning problem, necessitating the use of mixed strategies.
-therbby being intractable under standard
The key connection behind our lower bound is an observation by Hazan and Kale [2007]. which reveals that any -regret minimizer is inadvertedly able to compute approximate fixed points of any deviation in 4 (Proposition B. Computing fixed points is in general a well-known (presum- ably) intractable problem. being PPAD- hard. In our context, the set o does not contain arbitrary (Lipschitz continuous) functions [0. N - (0, 1]%, but instead contains multilinear functions from [0. 1] to [0. 1]% To establish PPAD- -ha-hhadneess for our problem, we start with a generalized circuit (Definition I.3), and we show that all gates can be approximately simulated using exclusively gates involving multilinear operations (Proposition 1.7); we defer the formal argument to Appendix I.1. As a result, we arrive at the following hardness result.
Theorem 3.3. If a regret minimizer R outputs strategies in [0, 1]%, it is PPAD-hard to guarantee Regas S e/VN, even with respect to low-degree deviations and an absolute constant e > O.
3.2 Extensive-form games
We next expand our scope to arbitrary extensive- form games. We will assume here that the branching factor of the game is 2 2-any game can be transformed as such by incurring a log b factor overhead in the depth of the game tree. Generalizing T described above, we introduce the set of k- mediator deviations gh Informally, the player here has access to l distinct mediators, which the player can query at any time; a formal definition is given in Section 4. Once again, the case k corresponds to linear-swap deviations. Further, if X' denotes the set of pure strategies, we let poly denote the set of all degree-k deviations X' + X. We establish similar parameterized results in extensive-form games, but which may now also depend on the depth of the game tree d.
Theorem 3.4. There is an online algorithm incurring at most an e poly regret in NO(kdf" jē2 rounds with a per-round running time of NO(ka)² /c. For The both bounds instead scale as NO(K)
We recall that N here denotes the dimension of the strategy space. We further clarify that parameter k appearing in & pasyy is different than the k in & & the former refers to the degree of polynomial, while the latter is the number of mediators. As all k-mediator deviations are degree-k polynomials (but not vice versa), it is to be expected that the bound in the theorem above concerning the former is worse. For a fixed degree & and assuming that the game tree is balanced, in the sense that d = -polylo N, Theorem 3.4 guarantees a quasipolynomial complexity with respect to q poly even when e is itself inversely quasipolynomial. The complexity we obtain for Ti med is more favorable, being polynomial for any extensive- form game.' I Finally, in light of the connection between no- regret learning and convergence to correlated equilibria, our results imply parameterized tractability of the equilibrium concepts induced by & or Φ poly (see Appendix F. 1 for a formal treatment).
'The bounds of Theorem 3.4 when k >> 1 and in particular in the special case of swap regret- are inferior to the ones obtained by Dagan et al. [2024] and Peng and Rubinstein [2024]. As we explain in more detail later in Section 6, bridging those gaps is an interesting open problem.
5

---

4 Technical contributions
From a technical standpoint, our starting point is the familiar template of Gordon et al. [2008] for minimizing f-regret, which consists of two key components. Accordingly, we split our technical overview into two parts.
4.1 Circumventing fixed points
The first key ingredient one requires in the framework of Gordon et al. [2008] is an algorithm for computing an approximate fixed point of any function within the set of deviations. In particular, if X is the of pure strategies and conv X' the convex hull of X, we now work with functions Th 3 Φ6 conv X' - conv X, so that fixed points exist by virtue of Brouwer's theorem." ? As we discussed earlier, this fixed point computation is at least in some sense monne--inhrentte Hazan and Kale [2007] observed that minimizing & -regret is computationally equivalent to computing approximate fixed points of transformations in &" Specifically, an efficient algorithm minimizing & -regrett- with respect to any sequence of utilities-can can be used to compute approximate fixed point of any transformation in &6 (Proposition B.1 in Appendix B). Given that functions in & are generally nonlinear, this brings us to PPAD-hard territory (Theorem 3.3), seemingly contradicting the recent positive results of Dagan et al. [2024] and Peng and Rubinstein [2024].
As we have alluded to, it turns out that there is a delicate precondition on the reduction of Hazan and Kale [2007] that makes all the difference: computing approximate fixed points only necessary the learner outputs points on conv X. In stark contrast, crucial observation that drives our approach that learner who selects probability distribution over does nor have to compute (approximate) fixed points of functions in Q. Instead, we show that it is enough to determine what we refer to as an approximate fixed point in expectation. More precisely, for deviation + 3 Φ : X + conv with an efficient representation, it is enough to compute distribution E Eews x. is quite easy to compute an approximate fixed point in expectation: take any #1 E conv X, and consider the sequence "1....,22 æL conv X such that 0e+1 B((= o(x')
A(X) such that EnZs p(xx) a
for all e, where conv X + (X)) mapping such that Exr~a())/="]] x. Then, for == ((e())()(<=)) we have
EE (0(x) x)) - x = Σ Σ 22t0
[o(x()) - x11 = ( (0(x)) x'6 = L x1100 t=1 x((0)))))
This procedure can replace the fixed point oracle required by the template of Gordon et al. [2008), which is prohibitive when & contains nonlinear functions, as we formalize in Appendix C.
Application to faster computation of correlated equilibria In fact, even in normal-form games where considering linear deviations suffices, computing a fixed point is relatively expensive, amounting solving linear system, dominating the per-iteration complexity. Leveraging instead our new reduction, we obtain the fastest algorithm for computing an approximate correlated equilib- rium in the moderate-pree preeciitteeeriioonnnee regime (Corollary 4.1). In particular, let focus for simplicity on n- player normal- -form games with a succinct representation. Here, each player i E [n] selects as strat- egy probability distribution ni E A(A:), where we recall that A; is finite set of available actions. The expected utility of player is given by u; (T ,.)) = Eay~ "..,,, ~-m, [u, (a),..., a,,)), where u; Ai x An [-1, 1, 1J. We assume that there is expectation oracle that computes the vector
in time bounded by EO A), where A == max; [A,]; it known that EO(n, A) < poly(n, A) for most interesting classes of succinct classes of games [Papadimitriou and Roughgarden, 2008). Using our framework, we arrive at the following result.
We recall that d conv X' ( is used to extend map & X conv X' to map d² conv X conv X
For technical reasons, it is more convenient to work with functions with domain X, which is why we use mapping â to sample a point in X' before applying

---

Corollary 4.1. For any n-player game in normal form, there is an algorithm that computes an e-correlated equilibrium and runs in time
o Alog A (A e?
12 )) (EO(n. A) +
Assuming that the oracle call to (2) (EO (n,,nnnA)))))) A)) does not dominate the per-iteration running time- which is indeed the case in, for example, polymatrix games Coroollay 4.1 gives (to our knowl- edge) the fastest algorithm for computing e-correlated equilibria the moderate-preciistt 2.37 is the exponent of matrix multiplication [Williams et al., 2024]; without fast matrix multiplication, which is widely impractical, the lower bound in- stead reads 2 1/vA. We provide a comparison with previous algorithms in Table and defer the details to Appendix I.3. Finally, we stress that similar improvements be obtained beyond normal-form games using our template; indeed, virtually all prior Ø-regret minimizers rely on some fixed point operation.
regime
1/A5-1 -1 < 1/ log A, where
Table 1: Time complexity for computing e-correlated equilibria in n- n-player normal-fome games with second column suppresses absolute constants and polylogarithmic factors. For simplicity, issues related to bit complexity have been ignored (that is, we work in the RealRAM model of computation).
A actions per player. The
Reference
Time complexity
[EO(m, A) + n 12
Ours (Theorem C.7)
[Anagnostides et al., 2022, Daskalakis al., 2021]
4 (EO(n, A) +
[Dagan et al., 2024, Peng and Rubinstein, 2024]
n. log)/((A)) (nA))E0(n, A) for >>
[Papadimitriou and Roughgarden, 2008]
[Huang and Pan, 2023]
1 (nA4)
Before moving on, it is worth stressing that the discrepancy that has arisen between operating over A(X) versus conv X' is quite singular when it comes to regret minimization in extensive-fome games and beyond. Kuhn's 's theorem [Kuhn, 1953] is often invoked argue about their equivalence, but in our setting it is the nonlinear nature of deviations in & that invalidates that equivalence." 4 To tie up the loose ends, adapt the reduction of Hazan and Kale [2007] show that minimizing p-regret over ((X) necessitates computing approximate fixed points in expectation (Proposition C.3), and we observe that the reductions of Dagan al. [2024] and Peng and Rubinstein [2024] are indeed compatible with computing approximate fixed points in expectation; the latter observation is made precise Appendix F.3.
4.2 Regret minimization over the set of deviations
The second ingredient prescribed by Gordon et al. [2008] is an algorithm minimizing external re- grer but with respect to the set of deviations 4. The crux in this second step lies in the fact that, even in normal-form games, & contains at least an exponential number of deviations, so black-box reductions are of little use here. Instead, the problem boils down to appropriately leveraging the combinatorial structure of d. as we cxplain below.
We will first describe our approach when X' = 10. and we then proceed with the more technical generalization to extensive-form games. The key observation here that regret minimization over & can be viewed as a tree-form decision problem of size NO(K), Terminal nodes in this decision problem are identified by the original index jo E [N], the queries .i. E [N]. their replies aj...., ag E {0. 1}. and finally the action on {0, 1 that is played. Each tree-form strategy q in this decision problem defines function Φq X' - conv X, which is computed by following the
"Kuhn's 's theorem is also invalidated in extensive-forre games with imperfect recall [Piccione and Rubinstein, 1997, Tewolde et al., 2023, Lambert et al., 2019]. in which there is also genuine difference between mixed and behavioral strategies. In such settings, however, is NP -Prdard to even minimize exteral regret.
7

---

strategy through the decision problem. Formally, we have
# II
( = Σ alio. a..... jks 1]
æli a.l ==1
where æ(jr, a:] x = if a 1, and xbioه if a, = 0. Hence 0g is degree-k polynomial in Now, since q + 0g (z)] is linear, it follows that q + (u, (g(x)) also linear for any given IR.. Therefore, a regret minimizer on f5r can be constructed starting from any regret minimizer for tree-form decision problems; for example, counterfactual regret minimization [Zinkevich et al., 2007], or any of its modern variants. This enables us rely on usual techniques for dealing with such problems, eventually leading to a complexity bound of NO(k), as we formalize in Appendix D.
For the set of low-degree polynomials & we leverage a result from Boolean analysis relating (randomized) low-depth decision trees with low-degree polynomials, stated below.
Theorem 4.2 (Midrijanis, 2004). Every degree-k polynomial f {0, 13 {0,1) can be written as a decision tree of depth at most 21
In particular, this implies that & C 22 Consequently, low-degree polynomials can be reduced to low-depth decision trees, albeit with an overhead in the exponent.
Turning to general extensive-form games, we follow a similar blueprint, although there are now additional technical challenges. particular, in what follows, to describe the set of deviations will be convenient to introduce new formalism related to tree-form decision problems.
Definition 4.3. points and observation points have been swapped.
The dual X of X is the decision problem identical to X, except that the decision
Definition 4.4. The interleaving X' @ y is the wer-form decision problem defined follows. There a state s = 82) E S x S2. The root state is the tuple (Ø, 2). The decision problem is defined by the player being able to interact with both decision problems, in the following manner. At each state 8 82):
If 81 and 82 are both terminal then is 8. Otherwise:
If either of the s,s is observation point, then is The children are the states (5/, s-;) where s/ is a child of st. (If both s;8 are observation points, both children si s are selected simultaneously. This can only happen at the root.)
Otherwise, is decision point. The player selects index i E {1,2] at which to act, and a child 5/ to transition to. The next state is (s/, 8-1).
In X @ y, the same state ($1, s2) be reachable through possibly exponentially many paths, because the learner may choose to interleave actions in X' with actions in ) in any order. Thus, each state ($1,82) corresponds to actually exponentially many histories in X' Y. In the discussion below, we will therefore carefully distinguish between histories and states. In light of the above exponential gap between histories and states, it seems wasteful to represent X' @ y as tree. Indeed, Zhang al. [2023] recently studied DAG-form decision problems, and showed that regret minimization on them possible so long as the DAG obeys some natural properties.
Using the language we have now introduced, we can define the set of k-mediator deviations t as the set of reduced strategies in the decision problem X' & p That is, the player has access to not one but k mediators, all holding strategy æ, which the player can query at any time. This is a significant advantage over having just one mediator since the player can send different queries to each of the k mediators (who must all reply according to æ), and therefore can learn more about the strategy x than it could have otherwise. We will call the responses given by the mediator action rec- ommendations. For a graphical illustration of such deviations, refer to Figure 2 (in Appendix E).
Reduced strategies q E π (X @ )oo). once again, induce functions Og : X conv X' given by
Σ
q
ZR
x 1
21 By
8

---

and in particular we have that og is degree-k polynomial. We define & as the set of such deviations. For that set, we show that there a reduction particular type of DAG-form decision problem of size NO(E), As we explained, that formulation is more suitable than tree-form decision problems when the number of possible histories far exceeds the number of states, which is precisely the case when the player is gradually querying multiple mediators as the game progresses.
Finally, we establish a reduction from low-degree polynomials to having few mediators; namely, we show that poly S " where we recall that d is the depth of the game tree. Our basic strategy is to again leverage the connection between low-depth decision trees and low-degree polynomials we described earlier (Theorem 4.2). To do so, we need to cast our problem in terms of functions {0. 1) - {0, 1 instead of X' + X. To that end, we first show how extend degree-k function f - [ to a degree-kd function f {0, 10 + {0, 1): that is. f coincides with f on all points in X' S {0, 11xh (Lemma E.7). This step is where the overhead factor d comes from. The final technical piece is to show that if each component of Φ X + X' can be expressed using K mediators, the same holds for o; the naive argument here incurs another factor of d. but we show that this is in fact not necessary. The details of the above argument are deferred to Appendix E.
5 Further related research
A key reference point is the result of Blum and Mansour [2007], and generalization due to Gordon al. [2008], which reduces minimizing swap regret to minimizing external regret. Specifically, for the probability simplex (AA), it maintains a separate external-regret minimizer, one for each action a E A. Both the per-iteration complexity and the number of iterations required is generally poly- nomial in A == |.A. Therefore, in settings where A is exponentially large in the natural parameters of the problem (such as extensive-form games) it does not appear that the reduction of Blum and Mansour [2007] is of much use. It is tempting to instead rely on the reduction of Stoltz and Lugosi [2005] for minimizing internal regret, a weaker notion than swap regret, which nonetheless suf- ficient for (asymptotic) convergence to correlated equilibria. However, one should be careful when relying on internal regret in settings where A is exponentially large; as we point out in Remark A. internal regret can be smaller than swap regret by up to a factor of A, so it is only meaningful when e S 1/A, a regime which is generally out of reach for regret minimization techniques when A is exponentially large.
This gap motivated the new reduction by Dagan et al. [2024] and Peng and Rubinstein [2024], which we discussed earlier. Beyond extensive-form games, those reductions apply whenever it is possible to minimize external regret efficiently. The complexity of computing correlated equilibria beyond the regime where the precision parameter e is an absolute constant remains major open problem, generally conjectured to be hard [von Stengel and Forges, 2008]; the recent online lower bound the adversarial setting [Daskalakis et al., 2024] provides further evidence in support of that conjecture.
As a result, most prior work has focused on more permissive equilibrium concepts, understood through the framework of 4-regret [Morrill et al., 2021a,b, Farina et al., 2022, Bai et al., 2022, Bernasconi et al., 2023, Noarov et al., 2023, Dudík and Gordon, 2009, Gordon et al., 2008, Fujii, 2023, Dann et al., 2023, Mansour et al., 2022, Sharma, 2024, Cai et al., 2024al). In terms of the most recent developments, Farina and Pipis [2023] established efficient learning dynamics minimizing what is referred to as linear swap regret (cf. Dann et al. [2023], Fujii [2023] for related results in Bayesian games). The solution concept that arises from linear swap regret was later endowed with a natural mediatoorbased interpretation by Zhang et al. [2024], which can be viewed as natural precursor to this work. Convergence to correlated equilibria has also attracted attention in the context of Markov (aka. stochastic) games (e.g., e. [Cai et al., 2024b, Jin et al., 2021, Erez et al., 2023, Liu and Zhang, 2023], and references therein).
Moreover, as we explained earlier, our approach also gives rise to faster algorithm for comput- ing approximate correlated equilibria in certain regime. As we discuss further in Appendix I.3, improving the per-iteration complexity of Blum and Mansour [2007] has received interest in prior work [Ito, 2020, Greenwald et al., 2006, Yang and Mohri, 2017] (see also [Huang and Pan, 2023, Huang et al., 2023]). The main bottleneck lies in the (approximate) computation of stationary dis- tribution of Markov chain, which can be phrased as a linear system. is worth noting that solving linear systems faster than matrix multiplication even for crude approximation is precluded, at least

---

subject to fine- grained complexity assumptions [Bafna and Vyas, 2021]; we are not aware whether such hardness results are also known for computing the stationary distribution of a Markov chain.
Finally, although we have so far mostly directed our attention to the game-theoretic implication of minimizing swap (or indeed ()) regret, namely the celebrated connection with correlated equilibria in repeated games, the notion of swap regret is fundamental solution concept in its own right more broadly in online learning and learning theory. Compared to the more common notion of external regret, swap regret gives rise to a more appealing notion of hindsight rationality; as such, it is often adopted as a behavioral assumption to model learning agents (e.g. [Deng et al., 2019I). It is also fundamentally tied to the notion of calibration [Hu and Wu, 2024], and recently inspired work by Gopalan al. [2023] in the context of multi group fairness.
Conclusions and future research
We provided new family of parameterized algorithms for minimizing Φ-regret in extensive-form games. Our results capture perhaps the most natural class of functions interpolating between linear- swap and swap deviations, namely degree-k deviations. Along the way, we refined the usual tem- plate for minimizing P-regree-- learning-which revolves around (approximate) fixed points [Gordon et al., 2008, Blum and Man- sour, 2007, Stoltz and Lugosi, 2005]. Instead, we showed that it suffices to rely on relaxation that we refer to as an approximate fixed point in expectation, which uunike actual fixed points can always be computed efficiently. Our refinement of the usual template for minimizing Ø-regret is of independent interest beyond extensive- of approximate correlated equílibria even in normal-form games, as it obviates the need to solve a linear system every round. As in the recent works by Dagan et al. [2024] and Peng and Ru- binstein [2024], crucial feature of our approach is to allow the learner to select distribution over pure strategies, for otherwise we showed that regret minimization immediately becomes PPAD-hard (under strongly adaptive adversary).
in many courses on algorithmic game theory and online
games. For example, can speed up the computation
There are many interesting avenues for future research. First, the complexity of our algorithm per- taining to degree-k deviations depends exponentially on the depth of the game tree. We suspect that such a dependency could be superfluous. To show this, it would be enough to refine Lemma E.7 by coming up with an extension whose degree does not depend on the depth of the game tree. It would also be interesting to devise parameterized algorithms for k-mediator deviations that recover as a special case the PTAS of Peng and Rubinstein [2024] and Dagan et al. [2024], so to smoothly interpolate between existing results for linear-swap regret [Farina and Pipis, 2023] and the afore- mentioned results for swap regret; is k = Ō(1/e) enough to capture swap regret?
Finally, perhaps the most important question is to understand the computational complexity of com- puting d--quiliibiaa in extensive-form games. In particular, our results raise the interesting question of whether there is an algorithm (in the centralized model) for computing in polynomial time an exact correlated equilibrium induced by low-degree deviations. Extending the paradigm of Pa- padimitriou and Roughgarden [2008] in that setting presents several challenges, not least because computing fixed points- which are crucial for implementing the separation oracle [Papadimitriou and Roughgarden, 2008]-10 is now computationally hard. Relatedly, we suspect that there is an in- herent connection between fixed points and correlated equilibria, in the spirit of the equivalence between 0-regret minimization and fixed points established by Hazan and Kale [2007].
Acknowledgements
We are grateful to the anonymous reviewers at NeurIPS for their helpful feedback. This material based on work supported by the Vannevar Bush Faculty Fellowship ONR N00014-23-1-2876, National Science Foundation grants RI-2312342 and RI-1901403, ARO award W91 INF2210006,,, and NIH award A240108S001.
References
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. Near-optimal no-regret learning for correlated equilibria in
10

---

multi-playe general-sum games. In STOC '22: 54th Annual ACM SIGACT Symposium on The- ory of Computing, 2022, pages 736-749. ACM, 2022.
Robert Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1:67-96, 1974.
Yakov Babichenko, Christos Papadimitriou, and Aviad Rubinstein. Can almost everybody be almost happy? In Conference Innovations in Theoretical Computer Science (ITCS), 2016.
Mitali Bafna and Nikhil Vyas. Optimal fine- tne-grained hardness of approximation of linear equations. In International Colloquium on Automata, Languages, and Programming, (ICALP), pages 20:1- 20:19, 2021.
Yu Bai, Chi Jin, Song Mei, Ziang Song, and Tiancheng Yu. Efficient phi-regret minimization in extensive-form games via online mirror descent. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
Martino Bernasconi, Matteo Castiglioni, Alberto Marchesi, Francesco Trovò, and Nicola Gatti. Con- strained phi-equilibria. In International Conference on Machine Learning (ICML), 2023.
Avrim Blum and Yishay Mansour. From external to internal regret. J. Mach. Learn. Res., 8:1307- 1324, 2007.
Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yo Yu Wei, and Weigiang Zheng, Tractable local equilibria in non-coneave games. In Proceedings of the Annual Conference on Neural In- formation Processing Systems (NeurIPS), 2024a.
Yang Cai, Haipeng Luo, Chen- Yu Wei, and Weiqiang Zheng. Near-optimal policy optimization for correlated equilibrium in general-sum markov games. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2024b.
Nicolo Besa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 2009.
Xinyi Chen, Angelica Chen, Dean Foster, and Elad Hazan. Ai safety by debate via regret minimiza- tion, 2023.
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng. Anup B. Rao, Aaron Sidford, and Adrian Vladu. Almost-linear time algorithms for markov chains and new spectral primitives for directed graphs. In Proceedings of the Annual Symposium Theory of Computing (STOC), pages 410-419. ACM, 2017.
Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. From external to swap regret 2.0: An efficient reduction and oblivious adversary for large action spaces. Proceed- ings of the Annual Symposium on Theory of Computing (STOC), 2024.
Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. Pseudonorm approachability and applications to regret minimization. In International Confer- ence on Algorithmic Learning Theory (ALT), 2023.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 27604-27616, 2021.
Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm, and Brian Hu Zhang. Exponential lower bounds for minimizing swap regret in extensive-form games, 2024.
Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos. Pure- circuit: Strong inapproximability for PPAD. Proceedings of the Annual Symposium on Foun- dations of Computer Science (FOCS), pages 159-170, 2022.

---

Yuan Deng, Jon Schneider, and Balasubramanian Sivan. Strategizing against no-regret learners. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 1577-1585, 2019.
Miroslav Dudík and Geoffrey J. Gordon. A sampling-
caapling-basedd based approach to computing equilibria in succinct extensive-fom games. In Jeff A. Bilmes and Andrew Y. Ng, editors, UAI 2009, Pro- ceedings of the Twenty-Fifth Conference Uncertainty in Artificial Intelligence, Montreal, QC, Canada, June 18-21, 2009, pages 151-160. AUAI Press, 2009.
Liad Erez, Tal Lancewicki, Uri Sherman, Tomer Koren, and Yishay Mansour. Regret minimization and convergence to equilibria in general-sum markov games. In International Conference on Machine Learning (ICML), 2023.
Gabriele Farina and Charilaos Pipis. Polynomial-time linear-swap regret minimization in imperfect- information sequential games. In Proceedings of the Anmual Conference on Neural Information Processing Systems (NeurIPS), 2023.
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.
Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, Philip Lazos, and Diogo Poças. On the complexity of equilibrium computation first-price auctions. SIAM Journal on Computing, 52(1):80-331, 2023.
Dean Foster and Rakesh Vohra. Calibrated learning and correlated equilibrium. Games and Eco- nomic Behavior, 21:40-55, 1997.
Dean P. Foster and Sergiu Hart. Smooth calibration, leaky forecasts, finite recall, and nash dynamics. Games and Economic Behavior, 109:271-299 2018.
Kaito Fujii. Bayes correlated equilibria and no-regret dynamics. CoRR, abs/2304.05005, 2023.
Anat Ganor and Karthik C. S. Communication complexity of correlated equilibrium with small support. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) 2018.
Paul W. Goldberg and Aaron Roth. Bounds for the query complexity of approximate equilibria.
ACM Trans. Economics and Comput., 4( 4(4):24:1124:225 2016.
Parikshit Gopalan, Michael Kim, and Omer Reingold. Swap agnostic learning, or characteriz- ing omniprediction via multicalibration. In Proceedings of the Annual Conference Neural Information Processing Systems (NeurIPS), 2023. 2023..
Geoffrey Gordon, Amy Greenwald, and Casey Marks. No-regret learning in convex games. In International Conference on Machine Learning (ICML), 2008.
Amy Greenwald and Keith Hall. Correlated Q-learning. In International Conference on Machine Learning (ICML), 2003.
Amy Greenwald, Zheng Li, and Casey Marks. Bounds for regret-matching algorithms. In ISAIM, 2006.
Amy Greenwald, Zheng Li, and Warren Schudy. More efficient internal-regret interaalregrretmmiiiiiingg algo- rithms. In Conference on Learning Theory (COLT), pages -39,2 2008
Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its conse- quences in combinatorial optimization. Combinatorica, 1:169-197, 1981.
Sergiu Hart and Andreu Mas-Colell, A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68: 127-1150, 2000.
Elad Hazan and Satyen Kale. Computational equivalence of fixed points and no regret algorithms, and convergence to equilibria. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2007.
12

---

Lunjia Hu and Yifan Wu. Predict to minimize swap regret for all payoff-bounde tasks. In Proceed- ings of the Annual Symposium on Foundations of Computer Science (FOCS), 2024.
Wan Huang and Bernhard von Stengel. Computing an extensive-form correlated equilibrium in polynomial time. In International Workshop On Internet And Network Economics (WINE), 2008.
Zhiming Huang and Jianping Pan. A near-optimal high-probabiliin swap-regret upper bound for multi-agent bandits in unknown general-sum games. In Proceedings of the Conference on Uncer- lainty in Artificial Intelligence (UAI), 2023.
Zhiming Huang, Kaiyang Liu, and Jianping Pan. End-to-end congestion control as learning for unknown games with bandit feedback. In International Conference on Distributed Computing Systems (ICDCS), 2023.
Shinji Ito. tight lower bound and efficient reduction for swap regret. Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
Albert Jiang and Kevin Leyton- Broonn Polynomial-time computation of exact correlated equilib- rium in compact games. In Proceedings of the ACM Conference on Electronic Commerce (EC), 2011.
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning A simple, efficient, decen- tralized algorithm for multiagent RL. CoRR, 15./2100.14555 2021.
H. W. Kuhn. Extensive games and the problem of information. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games, volume 2 of Annals of Mathematics Studies, 28, pages 193-216. Princeton University Press, Princeton, NJ, 1953.
Nicolas S. Lambert, Adrian Marple, and Yoav Shoham. On equilibria in games with imperfect recall. Games and Economic Behavior, 113:164-185, 2019.
Xiangyu Liu and Kaiqing Zhang. Partially observable multi-agent RL with (quasi-Jeffciieney: The blessing of information sharing. International Conference on Machine Learning (ICML), pages 22370-22419, 2023.
Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. Strategizing against learners in bayesian games. In Conference on Learning Theory (COLT), 2022.
Gatis Midrijanis. Exact quantum query complexity for total boolean functions. arXiv preprint ghamt-ph/0403168 2004.
Dustin Morrill, Ryan D'Orazio, Mare Lanctot, James R. Wright, Michael Bowling, and Amy R. Greenwald. Efficient deviation types and learning for hindsight rationality extensive-form games. In International Conference Machine Learning (ICML), 2021a.
Dustin Morrill, Ryan D'Orazio, Reca Sarfati, Marc Lanctot, James R. Wright, Amy R. Greenwald, and Michael Bowling. Hindsight and sequential rationality of correlated play. In Conference Artificial Intelligence (AAAI), 2021b.
John Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36:48-49, 1950.
Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. High-dimensional prediction for sequential decision making. CORR, 0ix/2310.17651 2023.
Ryan O' Donnell. Analysis of boolean functions. Cambridge University Press, 2014.
Christos H. Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi-player games. Journal of the ACM, 55(3):14:1-14:22 2008
Binghui Peng and Aviad Rubinstein. Fast swap regret minimization and applications to approximate correlated equilibria. Proceedings of the Annual Symposium on Theory of Computing (STOC), 2024.
13

---

Michele Piccione and Ariel Rubinstein. On the interpretation of decision problems with imperfect recall. Games and Economic Behavior, pages 3-24, 1997.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Beyond regret. In Conference on Learning Theory (COLT), 2011.
Aviad Rubinstein. Settling the complexity of computing approximate two-player nash equilibria. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 2016.
Dravyansh Sharma. No internal regret with non-convex loss functions. In Conference on Artificial Intelligence (AAAI), 2024.
Yoav Shoham and Kevin Beyton-Brown Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2009.
Gilles Stoltz and Gábor Lugosi. Internal regret in on-line portfolio selection. Machine Learning, 59 (1-2):125-159, 2005.
Gilles Stoltz and Gábor Lugosi. Learning correlated equilibria in games with compact sets of strate- gies. Games and Economic Behavior, 59(1):187-208, 2007.
Emanuel Tewolde, Caspar Oesterheld, Vincent Conitzer, and Paul W. Goldberg. The computational complexity of single-player imperfect-recal games. In Proceedings of the International Joint Conference on Artificial Intelligence (ICCAI), 2023.
Bernhard von Stengel and Françoise Forges. Extensive-form correlated equilibrium: Definition and computational complexity. Mathematics of Operations Research, 33(4): 1002-1022, 2008.
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2024.
Scott Yang and Mehryar Mohri. Online learning with transductive regret. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), pages 5214-5224, 2017.
Brian Hu Zhang, Gabriele Farina, and Tuomas Sandholm. Team belief DAG: generalizing the se- quence form team games for fast computation of correlated team max-min equilibria via regret minimization. In International Conference on Machine Learning (ICML). volume 202 of Pro- ceedings of Machine Learning Research, pages 40996 41018. PMLR, 2023.
Brian Hu Zhang, Gabriele Farina, and Tuomas Sandholm. Mediator interpretation and faster learn- ing algorithms for linear correlated equilibria in general extensive-form games. In International Conference on Learning Representations (ICLR), 2024.
Martin Zinkevich, Michael Bowling, Michael Johanson, and Carmelo Piccione. Regret minimization in games with incomplete information. In Proceedings of the Annual Conference Neural Information Processing Systems (NIPS), 2007.
14

---

A Further preliminaries
In this section, we introduce some further preliminaries. For additional background, we refer the interested reader to the excellent books of Cesa-Biande and Lugosi [2006] and Shoham and Leyton- Brown [2009]. Before we describe more formally the construction Gordon et al. [2008], we make remark regarding minimizing internal regret in extensive-form games.
Remark A.1 (Swap versus internal regret). When it comes to defining correlated equilibria in normal-form games, there are two prevalent definitions appearing in the literature; one is based on internal regret, while the other swap regret (e-g-, [Ganor and Karthik C. S., 2018, Goldberg and Roth, 2016]). The key difference is that internal regret only contains deviations that swap single action-thereby being weaker. Nevertheless, it is not hard see that swap regret can only be larger by factor of X') [Blum and Mansour, 2007], where we recall that X' denotes the set of pure strategies. So, in normal-form games those two definitions are polynomially equivalent, and in most applications one can safely switch from one to the other.
However, this is certainly not the case in games with an exponentially large action space, such as extensive-form games. In fact, the definition of internal regret itself is problematic when the action set is exponentially large: the uniform distribution always attains error of most 1/ Consequently, any guarantee for 2 1/|2| is vacuous. That is, if | is exponentially large, an algorithm that requires number of iterations polynomial in 1/c-which is what we expect get from typical no-regret dynamics-would need an exponential number of iterations to yield a non- trivial guarantee; this issue with internal regret was also observed by Fujii [2023]. Nevertheless, internal regret in the context of games with an exponentially large action set was used in a recent work by Chen al. [2023], who provided oracle-efficient algorithms for minimizing internal regret.
A.1 The construction of Gordon et al. [2008]
Gordon et al. [2008], building on earlier work by Blum and Mansour [2007] and Stoltz and Lugosi [2005]. came up with a general recipe for minimizing 46 regreet That construction relies on no- regret learning algorithm on the set of deviations Φ6, which we denote by Rę. Then, & rrgrett minimizer on conv X' can be constructed as follows: on each iteration 1..... T, the learner performs the following steps.
1. Receive @l()) from Ryp Select (t) E conv X' as an e-fixed point of 6(1; (x(()) x ||x S.
2. Upon receiving utility (t)) U. pass utility &º e r= + (ul), ( to Rr.
The main guarantee regarding the above algorithm is summarized below.
T
Theorem A.2 (Gordon et al., 2008). Suppose that Reg is the external regret incurred by RR. After T rounds ofthe the above algorithm, we have
1 T
00 -x(0) s Reg" +
max @ E
In Appendix C.I, will relax the requirement of needing (approximate) fixed points, while the same time maintaining the guarantee of Theorem A.2.
B Hardness of minimizing Ø-regret in behavioral strategies
In this section, we show that if the learner is constrained output in reach round strategy in conv X', then there is no efficient algorithm (under standard complexity assumptions) minimizing &8 reerrtt (Theorem 3.3); here, 3 conv X' + A(X) is the behavioral strategy mapping (introduced in the sequel as Definition C.5). the expression of which is not important for the purpose of this section. The key connection is a result by Hazan and Kale [2007], showing that any rrerett minimizer is able to compute approximate fixed points of any deviations in &² We then show that the set of induced deviations, even on the hypereube X' = {0, 1) rich enough to approximate PPAD-han D-ardd fixed-point problems.
15

---

In this context, consider transformation T 3 の² 10. + 10, 1 for which we want to compute an approximate fixed point a E conv 2:; that is, l - ø|12 S e, for some precision parameter e >> O. (It is convenient in the construction below measure the fixed-point error with respect to || I12.) Hazan and Kale [2007] observed that &- minimizer can be readily turned into an algorithm for computing fixed points of any function in Φ as stated formally below. Before proceed. we remind that here and throughout
operate under strongly adaptive adversary, which is quite crucial in the construction of Hazan and Kale [2007].
Proposition B.1 (Hazan and Kale, 2007). Consider a regret minimizer R operating over [0, 11 If T R runs in time poly(N, 1/e) and guarantees Regø. S e for any sequence of utilities, then there is poly(N,1/e, algorithm for computing an (ev/N-fixed point of any 6e E &Φ with respect to || ll2. assuming that of can be evaluated in polynomial time.
Proposition B.1 significantly circumscribes the class of problems for which efficient -regret mini- mization possible, least when operating in behavioral strategies. Indeed, computing fixed points is in general well-known (presumably) intractable problem. In our context, the set 6D does not contain arbitrary (L.ipschitz continuous) functions [0. 1|x - [0. 1/, but instead contains multilin- functions from [0, l to [0, 1| Nonetheless, we show that PPAD-hardness persists in our setting. The basic idea is as follows. We start with a generalized circuit (Definition I.3), and we show that all gates can be approximately simulated using exclusively gates involving multilinear operations (Proposition 1.7). The proof of that claim appears in Appendix I.1. As a result, we arrive at the main hardness result of this section, restated below.
Theorem 3.3. If a regret minimizer R. outputs strategies in [0, 11%, PPAD-hard to guarantee Regas S <//VN, N, even with respect to low-degree deviations and an absolute constant e > O.
We also obtain a stronger hardness result under a stronger complexity assumption put forward by Babichenko et al. [2016] (Theorem 1.9). At first glance, it may seem that the above results are at odds with the recent positive results of Dagan et al. [2024] and Peng and Rubinstein [2024], which seemingly obviate the need compute approximate fixed points. As we have alluded to, the key restriction that drives Theorem 3.3 lies in constraining the learner to output behavioral strate- gies. In the coming section, we show that there is an interesting twist which justifies the discrepancy highlighted above.
C Circumventing fixed points
The previous section, and in particular Theorem 3.3, seems to preclude the ability to minimize c- regret efficiently when the set of (extended) deviations contains nonlinear functions." 5 In this section, will show how to cireumvent this issue via a relaxed notion of what constitutes fixed point (Definition C. In the sequel, we will work with deviations & with domain X' instead of conv X.
C.1 Approximate expected fixed points
The key to our construction is to allow the learner to play distributions over X, not merely points in conv X. and use relaxed notion of fixed point, formally introduced below. Definition C.1. We say that a distribution π E (XX)) is an e-expected fixed point of o E (conv x)* if [|E [o(x) x) Ixx S
The key now is to replace the fixed point oracle in the framework of Gordon et al. [2008] (recalled in Appendix A) with an oracle that instead returns an e-iiedd point in expectation per Definition C.I. The learner otherwise proceeds as in the algorithm of Gordon al. [2008] (our overall construction is spelled out as Algorithm 1 in Appendix 1.2). It is easy to show, following the proof of Gordon et al. [2008], that a fixed point in expectation is still sufficient to minimize 4-regret.
Theorem C.2 (h-regret with eeepecceed fixed points). Suppose that the external regret Ro over +b -T after? T repetitions is at most Reg". Then, the --regret of Algorithm can be bounded as Reg + c.
Analogously to Proposition 1.1, it turns out that there is a certain equivalence between minimizing O in ((X) and computing expected fixed points:
$ For linear functions, fixed points can be computed exactly via linear program.
16

---

Proposition C.3. Consider a regret minimizer RR operating over ( If R runs in time T
poly(N, 1/c) and guarantees Rega I ffrr any sequence of utilities, then there is a poly(N, 1/c) algorithm for computing (+Dx) expeeced fixed points of & D. assuming that we efficiently compute =000)000 (0(x (f) x(1) at any time t. Here, Dx is the diameter of X with respect to -|-112 1/2-
The proof proceeds similarly to Proposition B.I, and so we include it in Appendix 1.2. Next, we present method for computing approximate expected fixed points of functions á ① without having to solve PPAD-hard problem.
C.2 Extending deviation maps to conv X'
First, since we will work both over conv X' and distributions in A(X), we need efficient methods for passing between them. To that end, we introduce the following notion.
Definition C.4. A map 5 conv X' + A(2) is
consistent if (())) x' = and
efficient if, given some Φ E and I E conv X, it easy compute x'(x) ==
[()=) ((x').
We will call the map o² conv X + conv X' the extended map of Φb
One may ask why we use this indirect method of defining Φ² rather than simply directly using the representation of & (for example, as polynomial) to extend é to conv X. The answer is that, even assuming that é X + X' is represented as a multilinear polynomial (which is the representation assumed in the majority of this paper), naively extending that polynomial to domain conv X' will not necessarily result in a function ő conv X' - conv X. For an example, consider the decision problem X' depicted in Figure 1, and consider the function &
- X' given by d(xx) = (an + T3. 42. T2 22, 0). One can easily check by hand that & is indeed function X' - X, but also that, for the strategy x = (1/2, 1/2, 0, 1/2,0) E conv X, we have ((x) = (1/2, 1/4, O, 1/2, 0) & conv X. Thus, we need a more robust way of extending functions X' - conv X to functions conv X + conv X. ideally one that dependent only the function Φ, not its representation.
We now give two methods of constructing consistent and efficient maps 8 conv X + A for tree-form strategy sets X. The first is the behavioral strategy map.
Definition C.S. The behavioral strategy map 3 : conv X' + (AY) is defined as follows: ((x) is the distribution of pure strategies generated by sampling, at each decision point for which æ[j] O, an action a according to the probabilities æ [ajja// / [i]- Formally,
x x|ja]
3(z)[y] :=
II
xb1]
ja:z 1
It is possible for @² be not polynomial even when @ polynomial, because 3 is itself not a polynomial. is clear that 3 is consistent. For efficiency, we show the following claim. Proposition C.6. Let conv X A(X) be the behavioral strategy map. Let X - conv X be expressed as polynomial of degree most k, in particular, Then there is algorithm running in time NO() that, given & and x E conv X, computes & (x).
sum of at most O(N*) terms.
Proof. To compute (()))(()))) (bx'), since & is polynomial, it suffices to compute Re)r)(a)) m(x') for multilinear monomials m of degree most K, that is, functions of the form ms( == ILES 2/2] where S S Z has size at most k. There are two cases. First, there are monomials that are clearly identically zero: in particular, if there are two nodes ja,ja' < S for a o a', then ms = 0 because a player cannot play two different actions at j. For monomials that are not identically zero, we have
xc [ja]
E
[
II
(c))
xb
JOES
ja ja
which is computable in time O(kd). Thus, the overall time complexity is O(ddN*) S. NOW))
17

---

The behavioral strategy map is in some sense the canonical strategy map; when one writes a tree- form strategy a E conv X' without further elaboration on what distribution A ((X) meant to represent, it is often implicitly explicitly assumed to mean the behavioral strategy.
The behavioral strategy map has the unfortunate property that it usually outputs distributions of exponentially-laree support; indeed, if æ E relint conv X' then ((x) is full-upporrt.
The second example we propose, which distributions. In particular, for any æ E conv X. Carathéodory's ' theorem on convex hulls guarantees that is convex combination of N pure strategies 21,..., 2N X. Grötschel al. [1981, Theorem 3.9] moreover showed that there exists an efficient algorithm for computing the appropriate convex combination. Thus, fixing some efficient algorithm for this computational problem. define a Carathéodory map 7 conv X' - A(X)) to be any consistent map that returns a distribution of support at most N. Given such mapping. computing (a(a)) is easy:
call Carathéodory map, always outputs low-support
simply writes Σ; og by computing (xx), and returns (x) = E; 0;p((2;). This only requires a poly( N --imm computation of 7, and N evaluations of the function Φ. As before, when & is degree-k polynomial, the time complexity of computing 67 is bounded by NO(R).
C.3 Efficiently computing fixed points in expectation
Now let conv -> ((x) be consistent and efficient. Consider the following algorithm. Given 4 select æ conv X' arbitrarily, and then for each é > set æe Φ² (xz-1). Finally, select == Eewty 0(w)) E (2)) as the output distribution. By a telescopic cancellation, we have
E (x())
a0] 1|x
1 L
Σ
E m=
(o(r)
(b(x))
x:]
E (-)((_))
[b(x))
x1)
S
2 L
L
as desired. As a result, applying Theorem C.2, we arrive at the following conclusion.
Theorem C.7. Let R& be an regret minimizer on & whose external regret after T iterations is Reg and whose per-iteration runtime is R1, and assume that evaluating the extended map o² conv X' - conv X takes time R2. Then, for every >> there is a learning algorithm on X whose d-regret after T iterations is most Reg + and whose per-iteration runtime is O + R2/e).
The above result provides full black-box reduction from ø-regret minimization external regret minimization on 4 with no need for the possibly-expensivee computation of a fixed point. We note that the iterates of the algorithm will depend on the choice of f-for example, setting 5 = 3 and setting d will produce different iterates.
D Low-degree regret on the hypercube
In this section, we let X' the hypercube {0, 13x, For the convenience of the reader, we first recall that the set of deviations T is defined as follows:
1. The deviator observes an index jo E [N]-
2. For i ,,....,::: k:
The deviator selects an index ji E [N], and observes a [[j.].
3. The deviator selects ag {0, 1}.
As observed earlier, the above process describes tree-form decision problem of size NOO()) In particular, terminal nodes in this decision problem are identified by the original index ju E [N]. the queries fi...., Jss [N], their replies di,.... ag {0.1), and finally the action dn {0, 1) that is played. Each tree-form strategy q in this decision problem defines function dg X - conv X, which is computed by following the strategy a through the decision problem. Namely,
& (x)
Σ
gloo. Ji, an _k, ak. 1]
II
miji, az) s=1
'Applying Carathéodory naively would give N + instead of N. but we can save 1 because the tree-form strategy set is never full dimensional as subset of (0, 13
18

---

where æ(ji, ail = x[ia| if a; = 1, and 1 x if a; O. We see that Qq is a degree-k polynomial æ.
We define & DT. as the set of such functions $g. The "DT" the name t DT stands for decision free: the set of functions Φ X' conv X' that can be expressed in the above manner is precisely the set of functions representable as (randomized) depth-k decision trees on N variables.
For intuition, we mention the following special cases:
D is the set of external deviations.
Pir the set of all single-query deviations, which Fujii [2023] showed to equivalent to the set of all linear deviations when X' is hypercube.
Di is the set of swap deviations.
Since ++ 0g [x] is linear, it follows that q + (u, (x)) also linear for any given u RR.
Therefore, a regret minimizer on Hor can be constructed starting from any regret minimizer for tree-form decision problems, such counterfactual regret minimization [Zinkevich et al., 2007].
Proposition D.1. There NO(k)) (o0t))-ime--er--ouue regret minimizer on T whose external regret at most after NO /ea rounds.
Thus, combining with Proposition C.6 and Theorem C.7, we immediately obtain a br-rreret min- imizer with the following complexity.
Corollary D.2. There is a N /e-time-per-round regret minimizer on X whose & regrett is at most e after NOOK) /e² rounds.
Next, relate depth-k decision trees to low-degree polynomials. Let & be the set of degree-k polynomials & X X. We appeal to result from the literature Boolean analysis, recalled below.
Theorem 4.2 (Midrijanis, 2004). Every degree-k polynomial f 10, + {0,1] can be writlen as a decision of depth most 2k3.
In particular, pply S
4221" DT Corollary D.2 thus also implies &
poly poly- -rggret minimizer:
Corollary D.3. Let X' {0, 13 There is an NO(²) "o-ee)/-etim-ppee /e-time-per-round regret minimizer on X whose q.k poly" regret is at most e after NO(2)) /ea rounds.
It is reasonable to ask whether the above result generalizes to polynomials & X conv X. Indeed, when & S 1 or & = N, every degree-k polynomials é : X + conv X' can be written as convex combination of degree-k polynomials ø X X, even for arbitrary tree-form decision problems." However, this is not generally true. brute-force search shows that the polynomial Φ; {0, 1] + J0, 1]4 given by
1 ( F2, T3, = 31 F1 2212s 2 T22's +
1
+
2 Z3.4
quadratic, but it is not convex combination of quadratics whose range {0, 134. Perhaps more
glaringly, if one could efficiently represent the set of quadratic functions Φ {0. 1 + [0, 1|a
then one could in particular decide whether given quadratic function Φ {0, 1] - R has range [0, 1 But this is coNP-compled problem.
E Extensive-form games
The goal of this section is to extend the results in the previous section to the extensive-form setting, that is, to generalize them to all tree-form decision problems.
For degree and N this is trivial: for degree it is due to Zhang et al. [2024).
19

---

E.1 Interleaving decision problems
We first recall the operations of merging decision problems that will very useful as notation in the subsequent discussion. In particular, given two decision problems X' and ) with node sets Si and S2 respectively, we restate the following definitions previously introduced in Section 4.
Definition 4.3. The dual X of X is the decision problem identical to X, except that the decision points and observation points have been swapped.
Definition 4.4. The interleaving X' 60 y is the tree-form decision problem defined follows. There is a state s = ($1, $2) E S x S2. The root state is the tuple (Ø, Ø). The decision problem is defined by the player being able to interact with both decision problems, in the following manner. At each state 8 ($1, 52):
If 3 and $2 are both terminal then is 8. Otherwise:
If either of the 8;8 is an observation point, then so s. The children are the states (5/, 8-1) where of is child of st. (If both 8;8 are observation points, both children s1 8/2 are selected simultaneously. This can only happen at the root.)
Otherwise, s is a decision point. The player selects an index E {1,2] at which to act, and child s/ to transition to. The next state is (5/, 8-1).
follows immediately from definitions that X = X, and @ associative and commutative. The name and notation for the dual is inspired by the observation that (a: y) 1 for all x X and E X: indeed, the component-win wise product x[>]y[[]] is exactly the probability that one reaches terminal node 2 by following strategy at X's decision points and y at X'ss observation points. We also define the notation x = X 8 ... @ X, where there are l copies of X'
It is important to observe that in X' @ y, the same state (s1, 82) can be reachable through possibly exponentially many paths. This is because the learner may choose to interleave actions in X' with actions in Y in any order, which means that state ($1, corresponds to exponentially many histories in X & V. For that reason, we have to distinguish between histories and states.
In light of the above discussion, it is inefficient to represent X' @ y as tree. Indeed, Zhang et al. [2023] studied DAG-form decision problems, and showed that regret minimization on them is possi- ble when the underlying DAG has some natural properties. We state here an immediate consequence of their analysis, which we will use black box. Intuitively, the below result states that, as long as utility vectors also only depend on the (terminal) state that is reached, regret minimization on an arbitrary interleaving of decision problems X; 3 ... 3 Xx is possible, and the complexity depends only on the number of states.
Theorem E.1 (Consequence of Zhang et al., 2023, Corollary A.4). Let x= X2 8 0 Xx. where X; has terminal node set 2,. Let Z = Z1 .... Zy be the set of terminal states for X. For each such terminal state z E Z, let (z) be the set of histories of X whose state is Define the projection π. : X - 1 by
{<)][=]=
Σ a|u). DEV(*)
Then there exists an efficient regret minimizer T ((2) == (π(x) X) C R its per-round complexity is poly([21), and its regret is c after poly rounds.
Whenever we speak of regret minimizing on interleavings, will always be the case that utility vectors depend only on the state, so we will always be able to apply the above result. We will call vectors 7 (X)) reduced strategies.
Before proceeding, it is instructive to describe in more detail a result of Zhang et al. [2024], which will also use later, in the language of this section. Let X' and y be any two decision problems with terminal node sets Z, and Zg respectively. A reduced strategy q E ( & y) induces linear map dg y + conv X, given by
de (1)[a|]= = Σ (2
22
20

---

A.A.A
A.0.0
A.1.1
A,B,0
A.2.0
0.2.0
8,2,0
C,2.0
2
4
B.2.C
5
B.2,4
B.2.5
3
3
Figure 2: A representation of the deviation 6(x) (x1 + 23, 22 22 Z2, 0) (discussed in Appendix C.2) the decision problem in Figure 1, as a strategy in @ X @ R. iee. with k = 2 mediators. (For an example of one-mediator deviation, see Zhang et al. [2024, Figure 1J.) Again, black squares are decision nodes and white squares are observation nodes. Nodes are laheled with their state representations: the state in X' first (in blue), and the two mediator states after (in red). Similarly, blue edge labels indicate interactions with the decision problem (i.e., playing actions and receiving observations in X), and red edge labels indicate interactions with the mediators (i.e. querying and receiving action recommendations from the mediators). Redundant edges (such as those in which the decision problem in X' has terminated) are omitted. The deviation shown in thick black lines. For example, Ø2 (x) = IyT4 because the only state in which the deviator plays action 2 is when the mediator state is (2.4). (xx) I1 + 23 because the deviator plays action 1 at mediator states (1,1) and (3,0), which would give the formula Φ1 (x) x² + 23 (where
Fp ;= 1 21), but one can easily check that x? Iz 21 + 2y for all x E X.
It is instructive to think, as Zhang al. [2024] detailed extensively in their paper, about what strate- gies q E (X' & Y) represent, and why they induce the linear maps Φq. Decision points j in y become observation points in X & Y at these observation points, the player should observe the action taken by strategy y at j. The player in X' & ) is given the ability to query the strategy y by taking the role of the environment V, while the environment, holding a strategy y E V, takes the role of the player and answers decision point queries with the actions that it plays. The player then uses these queries to inform how plays in the true decision problem X. This is the sense in which q induces map óq: the output 0g is precisely the strategy that would be played if the environment in X' @ y answers the queries by consulting the strategy y. We will call device that answers queries using strategy y a mediator holding strategy y. Zhang et al. [2024] then showed the following fact, which we will use critically and repeatedly in the rest of this paper.
Theorem E.2 (Zhang al., 2024, Theorem A.2). Every linear map à y - conv X induced by some reduced strategy q E T (X' @ )).
E.2 Efficient low-degree swap-regret minimization in extensive-form games
We now proceed with generalizing the results of Appendix D to extensive-form games.
Let X' be any decision problem of dimension and depth d. We will assume WLOG that every decision point in X has branching factor exactly 2. This is without loss of generality, but it incurs loss of O(log b), where is the original branching factor, in the depth. Thus, the below bounds, when d appears, it should be read as Odd b).
21

---

Using the previous notation, the set of k-mediator deviations & is the set of reduced strategies in the decision problem X' @ Xor In particular, we recall that reduced strategies (('' @ X x0k) induce functions 04 X + conv X given by
(x)(]]2]
Σ
g(2,211 2k
x|2]]
Thus, have that og is degree-k polynomial. 4 med is the set of such deviations. For intuition, we once again pose a few special cases:
When the original decision problem's decision space is A (i.e., the decision problem consists of a single root observation point with N children, each of which is a decision point with two actions), we have $ T med- Thus, the results in this section strictly generalize those in the previous section.
Lb medd and d are, as before, the sets of external and swap deviations respectively.
T med is, by Theorem E.2, the set of all linear deviations.
In this context, applying Theorem E.1 gives an efficient mnd -egret minimizer:
Theorem E.3. There is an -ome--iime-r regret minimizer & med whose external regret most after NO(K) /e rounds.
Thus, once again Proposition C.6 and Theorem C.7 have the following consequence. Corollary E.A. There is No /e-time-per-round regret minimizer on X' whose T red-re is at most e after NO(K) /e² rounds.
Next, we discuss extensions of our result to low-degree polynomials. Unfortunately, cannot directly apply Theorem 4.2 to conclude the existence of a regret minimizer on with & - rregett poky
growing as NO(()) //2. There are two issues in attempting do so.
First, when is not the hypercube, polynomials f X - f0. 1} are not total functions. That is, is not necessarily the case that degree-k polynomials f {0, 1} can be extended degree- k polynomials ʃ {0, 11 > {0. 1). which is required in order to apply Theorem 4.2. For an example of this, consider X DD where Dy is the standard basis in R.N. that is, DN {er : i E [[]] where e, E IR is the ith basis vector (in other words, D is the set of vertices of the probability simplex ((N)). Let f D4 + {0, given by f(x) œ 22. Then linear, but there is no linear f 1), 4 + {0, 13 extending f. Indeed, there is more general manifestation of this phenomenon:
Proposition E.5. For every N, there exists a linear map f DN + {0, such that any extension f: (0, 13 + {0, 1} of must have degree at least 22log N).
Proof. Let f (0, 1J + (0, 1) be any degree-k: function. By Theorem 3.4 of O' O'Donnell (2014), f is k22-junta. that is, f(xx depends on at most h-2h entries of Now consider the map f DN + {0, 1} given by f(x) = EigN/2 T. Let f 1] + {0, 1} be an extension of f. Then depends at least N/2
inputs: if F(0) then f depends at least I,,.... ........ 2 [N/2]_ and f(0)) = 1 then f depends on at least x 1/22]+1:-.... NN- Thus, we have N/2 S k:25 which upon rearraging gives l > N).
The second issue is the following. Suppose that mediators were enough to represent a function f X 1). How does one then represent a function Φ X X²? Each coordinate of could be represented using K mediators, but that need not mean the whole function can. In game-theoretic terms, representing coordinate of d(x)) allows the player play single action, necessarily the whole game. Naively, playing the whole game would seem to require K mediators: K mediators for every level of the decision tree, to compute which action to take at each level.
FFormaly, we call f: (0, 1 {0, 1} extension of f X + (0, 1) if f agrees with X.
22

---

We will show that it is possible to circumvent both of these issues: the first with a loss of (d) in the degree of the polynomial that is representable, and the second with no additional loss. In particular, we state our main result below.
T S $ s0kkd) Therefore, for every k. there is NO(kdy /e-iim///eeeeeeeeee /e-time-per-runnd
Theorem E.6.
algorithm whose d -regret at most after NO /e &rounss.
E.3 Proof of Theorem E.6
We dedicate the rest of this section to the proof of Theorem E.6. We deal with the two aforemen-
tioned problems one by one. First, show that every J' admits an extension loss of factor of d in the degree:
Lemma E.7. Every f - {0, 1} of degree admits a degree-kd extension ʃ (0, 13 - {0, 13.
Proof. We claim first that the identity function id X - X' admits degree-d extension, that is, there is a degree-d function id {0, 1 + X' that is the identity on X. Indeed, consider the following function id. Then we define id(a))]ja] recursively as follows:
[ [=]]0]] [p,) (1-=)])0) (p))))
if 0, 0,
id id())
if
a a= 1.
It is easy to check that id is indeed the identity on X' by definition of tree-form decision spaces, and that the degree of id is most the depth of the tree, d. But now, for any ʃ : X' + {0, 1} of degree k, the map ʃ = f a id : {0, 11 + {0, }} has degree at most kd and is an extension of ʃ.
Now we apply Theorem 4.2. That result tells that degrec-kd function f {0, 11 {0, 1} can be evaluated using K = O(kd)s queries. One mediator is certainly more than enough to perform single query, and therefore such function can also be evaluated using K mediators. therefore remains only to address the second problem: namely, the ability to evaluate a function ő : (0. N + {0, 1}. since the output is only binary, in principle only allows us play a single action. But one needs to play d actions to reach the end of the game. Naively, this would require losing another factor of d, for total of O (dd) mediators. However, we now show that is possible to completely circumvent this problem. The notation that we have built up will make this argument perhaps surprisingly short.
Let 6: : X + X' be any function such that each component d2 X + {0, 1}, given by x ++ [2)) expressible using K mediators. By definition, de is expressible as a strategy" qs क ((0, 1) &
p@K). By the argument in the previous section, qz induces a linear map Φ² X - {0, 1].
Now let à: P + X' be the function whose 2th coordinate is S. Every component of o is linear, so & is itself also linear. But then by Theorem E.2, there exists a strategy q E (xx' @ PzK). that is, a K --mediator deviation, that represents &b. This completes the proof.
F Discussion and applications
In this section, we discuss various implications and make several remarks about the framework and results that we have introduced.
F.1 Convergence correlated equilibria
Notions of 4-regret correspond naturally to notions of correlated equilibria. Therefore, our results also have implications for no-regret learning algorithms that converge to correlated equilibria. Here, we formalize this connection. Consider an n-player game in which player i's strategy set is a tree- form strategy set X, and player i's utility is given by multilinear map u; X,
X,
This is a slight abuse of notation since (0, 1} is not a decision problem, but the argument works one interprets (0, }} as the decision problem with single decision node and two child terminal nodes. The sonse in which qu represents Φb is that, if the environment in X S plays according to strategy æ, the player will (eventually) play action (x))
23

---

[-1.1]. For each player i, let D; S (conv X;) be set of deviations for player i. Finally let -= 1......, (n).
Definition F.I. A distribution E ( x... x Xx)) is called correlated profile. A correlated profile x is an e- e-O-equilibrium no player can profit more than e via any of the deviations di E o; to its strategy. That is, Rege (m,), x-1) Ez- (0;
for all players and dy 4
For example, we can define k-mediator equilibria and degree-k swap equilibria by setting 4, to & med and db poly respectively. The following celebrated result follows immediately from the defini- tions of equilibrium and regret.
Proposition F.2. Suppose that every player i plays according regret minimizer whose -eereeet at most after T rounds. Let mi E A(X)) be the distribution played by player i at round I. Let (t) E A(x)) x .... x (Xx) be the product distribution whose marginal on X, is ni (1) Then the
average strategy profile. that is, the distribution + ExE(y (9,, is an e-U-equilibrimm.
Thus, from Theorems E.3 and E.6 it follows, respectively, that, given game I where the dimension of each player's s decision problem is at most N, we have the following results.
Corollary F.3. An e-k-mediator equilibrium can be computed in time NO /ca.
Corollary F.4. An e-degree-k-sway equilibrium can computed in time NO /e5.
The issue of representing the induced correlated distribution is discussed in Appendix G.
F.2 Strict hierarchy of equilibrium concepts
Let E (med, poly]. For every l 2 O, let (T) be the set of t -qquiiibia Т. It clear from definitions that (T) C (T)) Further, even for normal-form games, it is known that coarse- correlated equilibria are not generally equivalent to correlated equilibria, so at least one of these inclusions strict in some games. We now show that all of these inclusions are strict, so that the deviations &h form a strict hierarchy of equilibria." 10
Proposition F.5. For every k 2 1, there exists game I' such that E (I)) & -
Proof. Consider the two-player game I defined as follows.
Pl's 's strategy space is X = [-1, Player 2's strategy space is simply y = 1-1,
Pl's utility function is in (1 Tyy. That is, Pl would like to set # y. P2 gets no utility.
Consider the correlated profile π defined as follows: x is uniform over the 2 pure profiles (x, y) e X' ) such that y = x1 ... Zg. Pl's Pl's expected utility is clearly 0 and there is a swap (i.e., $ devi- ation that yields a profit of 1, namely æ +> ation plays at coordinates other than the first one.) But, since all the x,s are independent, no function of degree less than & can have positive correlation with I22 ... Zg. and thus, there are no profitable deviations of degree less than Thus, स & -equilibrium, but not a =
......) )) (it does not matter what the swap devi-
F.3 Characterization of recent low-swap-regret algorithms in our framework
We have, throughout this paper, introduced and used a framework of Ø-regret that involves fixed points in expectation. Proposition C.3 shows that the ability to compute fixed points in expectation is in some sense necessary for the ability to minimize --rrgret. is instructive to briefly discuss how the recent wwwap-rrgret-mmniiiiee
algorithm of Dagan et al. [2024] and Peng and Rubinstein [2024]
The below result constructs a game that depends on k. It is not the case that there exists a single game for which the inclusion hierarchy is strict: for example, for & 2 N. the set d will already contain all the deviations, so E (I') Es (I') for every 2 N
"These strategy spaces are not technically tree- form strategy spaces, but they are linear transformations of tree-form strategy spaces. so one can also rephrase this argument over frrm-form strategy spaces. For cleanliness of notation, stick to (-1, k as the strategy space.
24

---

fits into this framework. Their algorithm makes no explicit reference to fixed-poin computation, nor to the minimization of external regret over swap deviations they do not explicitly invoke the framework we use in this paper, nor that of Gordon et al. [2008). Where is the expected fixed point hidden, then? While we will not present their entire construction here, it suffices to state the following property of it. At every round i, the learner outputs a distribution x(() E ( that is uniform on L strategies ((b1), ................................ (f.1)) The way to map this into our framework is to consider (+) an approximate fixed point in expectation of the "function" ((()) that maps (t(6.) (11,++1)
for each ( = ,,..., -- 1. With this choice of (,(t), their algorithm indeed fits into our framework.
F,4 Revelation principles (or lack thereof)
Most notions of correlated equilibrium obey some form of revelation principle. Informally, one can treat a player attempting to deviate profitably from a correlated equilibrium as an interaction between a mediator (who sends useful information to the player) and the player (who tries play optimally by using the mediator). When studying the regret of online algorithmss, one assumes that the interaction with the mediator is canonical: the mediator holds with some sampled strategy profile (Z1....;.., ~ π, and in equilibrium every player indeed plays 2;. We say that the rev- elation principle holds for a particular notion of equilibrium if allowing non-canonical equilibria would not expand the set of equilibria. In Appendix H, we give rather general formalization of this notion, which enough to encompass all the notions of correlated equilibrium discussed in the paper. We show that, in this formalism, the revelation principle does not hold for k-mediator equi- libria or degree-k swap equilibria when > 1, and indeed in both cases the set of outcomes that can be induced by non-canonical equilibria is the set of linear-swap outcomes (Theorems H.4 and H.5).
G Representation of strategies
In this section, discuss how strategies T E A(X1 x.. X Xn)) are represented for the pur- poses of all of the results in this paper, and in particular for Corollaries F.3 and F.4. In both cases, at each timestep, each player's strategy x; is a uniform mixture of L O(1ee) strategies 5(x: ((a. )...,, 5(x) (t)t)) and we have
(t)
L
((ml(te)) t=1
(3)
that is, π is a uniform mixture of products of mixtures of strategies that are themselves outputs of 8. Thus, if the strategy map ö is established by convention (for example, as mentioned before, it is
often conventional to take d to be the behavioral strategy map), suffices to output æ (t,f) E conv X; for each i, &.
Suppose that impose slightly more stringent restriction the output format, namely, want ı to be a uniform mixture of products of mixtures of pure strategies. In that case, we can take 8 to be the Carathéodory map."
13 Now, writing x (t.f) EjE[N] ag
(t,6,) (t.f.) for x. (t.6.) X, we set
x;
T
L
ΣΣ
(1,,1) (1...)
म =
L {=1#=1
(4)
So, output consists of the strategies (t.k.)
x!
X and their coefficients
a (t,45) for each f,
H On the revelation principle
In this section, we give a formalization of the revelation principle which encompass all the notions of correlated equilibrium discussed in the paper. In this formalism, the revelation principle does
BuFunnction" " in quotes because the stated & may not he a function at all; for example, the sequence x (6.1) ..... x (f.L) may contain repeats yet be aperiodic.
We remind the reader here that the choice of must be the same one that was used to run the algorithm, so by taking d here, we mean that we are considering distribution that was computed by running our algorithm with that choice of 8. That is, the in Eq. (3) is not the same as the in Eq. (4).
25

---

not hold for k-mediator equilibria or degree-k swap equilibria when k > 1, and indeed in both cases we show that the set of outcomes that can be induced by non-canonical equilibria the set of linear-swap outcomes (Theorems H.4 and H.5).
Let @ be the class of all finite tree-form decision problems. For each pair X E 2 let xx E (conv X²) be subset of deviations. Finally let ④ Ux.ves Px,.. As in the previous section, consider a game where player has strategy set X2 and utility u, : 21 x... x Xx [-1,1]]
Definition H.1. Let ; E D be arbitrary free-form strategy spaces, let E A(1i x x...X V,), and let & E xx for each player i. We call the tuple (1) a generalized profile. A generalized profile is generalized e-D-equllibrim if no player i can profit by switching to different strategy mapping o' V1 - conv X₁ That is,
E (o((),)),, (y - E us (o) o -y +e you
9/-
for all players i and of E Px.y. We call generalized profile canonical if V = X, and Φi X; - conv X; is the identity map for every i.
In this language, the definitions of equilibrium in Appendix F.1 were definitions of canonical equi- libria. Every generalized profile induces canonical profile, namely, the distribution over strat- egy given by sampling y т and returning (dh (..))....; Un (xx.)). Call two generalized profiles equivalent if they induce the same canonical profile. We can now define the revelation principle as follows.
Definition H.2 (Revelation principle). The class of deviations t satisfies the revelation principle if the induced canonical profile of every generalized --D-equilibrium is also an e-f-equilibrium.
For an example, let & be the set of all functions, so that the notion of equilibrium is the normal-form correlated equilibrium. Then one can think of the sample y ~ π as a profile of signals (one signal per player) from correlation device, and di as player i's mapping from signals strategies. Then the revelation principle states that, without loss of generality (up to utility equivalence), one can assume that signals are recommendations of strategies (3/- X.) and players in equilibrium play their recommended strategies (ø, X + conv X; is the identity map).
All notions of equilibrium that have mentioned can be expressed in this language, and the reve- lation principle applies to all of them.
Proposition H.3 (Sufficient conditon for revelation principle). Let 8 be a consistent strategy map in the sense of Appendix C.2. Suppose that, for every o E xx, and so E xxxx, we have i o ó e 4 x Then 4 satisfies the revelation principle.
Proof. Given a generalized c- --u-liuuiibrium (O), 6e) T), let n' be its induced canonical profile. We need show that N' also an equiliibiiuum Consider any hypothetical deviation d/ E xx We have
u (W)(( x-1) aoda!
E
E u.((uf o (.)())) o
y"u
< max
E. (.(0 o (x=
o x
< E (n(di(g)), ( :)) +
you
E u,( x x)
where the second line uses the assumed composition property.
The revelation principle has, of course, been shown for various special cases of equilibrium before us: for example, NFCE Aumann [1974], linear-swap equilibria Zhang et al. [2024], and so on. Our proposition above generalizes these proofs since each of those notions indeed satisfies the requi- site compositional criterion: compositions of arbitrary functions are still arbitrary functions, and compositions of linear maps are linear.
The definition of k-mediator functions and degree-k polynomials are both easy to generalize from the X' + X case to the y -> case. We can therefore define generalized k-mediator equilib- ria and generalized degree-k swap equilibria, and ask whether the revelation principle applies to
26

---

these. Proposition H.3 does not apply, because compositions of k-mediator and degree-k functions will usually require more mediators and a higher degree. Indeed, we now show that the revelation principle fails for these notions when k > 1. We will, in fact, show something quite strong. Recall Proposition F.5, which showed that both canonical & med and canonical T puly are strictly tightnn-
ing notions of equilibrium as l increases. Here we show that this is not the case for generalized equilibria.
Theorem H.4. For every k 2 1, every linear-swap equilibrium is equivalent to a (non-canonical) k-mediator equilibrium.
Proof. Let π be any linear-swap equilibrium. We define a mediator of player i. Given a strategy E X, the mediator will interact with the player as follows. First, for each decision point j of player i, and let aj E Aj be the action that is played by æ. (If x defines no action at j, the mediator (1)
selects one at random). The mediator samples integers az a.....aj (k) [by] uniformly random under the constraint that Ee=1
aj (mod bj). The important property that is derived from the above construction is simply that, in order to learn aj. the player must know all the aj s, and without knowing all of them, the player learns no information whatsoever.
(2)
When the player arrives, the mediator has the following interaction with the player. First, the player must supply an integer é E [k:. We will call the seed. Then, whenever the player sends a decision point; j. the mediator checks whether the decision point sent is consistent with the sequence of decision points previously sent by the player (i.e., if j is possible next-decision-pol the previous decision point sent). If not, the mediator terminates the interaction. If so, the mediator sends (t) to the player.
following
Now consider how a player can use k copies of such a mediator. In order to learn any useful information at all about any decision point j. the player must (1) supply different seed to each of the & mediators, and (2) query decision point j with all mediators. Therefore, the player can essentially only use these mediators as if they were one, giving the same sequence of queries every (5) (mod bj). Thus,
mediator and computing the true action recommendation by computing E. a the player can only implement deviations that it could with a single mediator, which by Theorem E.2 are the linear deviations.
What have thus shown is the following. Let V/ be strategy space that represents the above interaction with the mediator, and let Φ; be the k-mediator deviation that acts according to the previous paragraph. Let x E A() ... Vn) be the distribution in which strategy sampled, the a are sampled according to the first paragraph, and each mediator plays according to the strategy y; that answers queries according to those a s. Then ((V,, (.)"E, is non- canonical & rqquliirii.
is
Theorem H.S. Suppose that every player's strategy space in a given game I is the hypercube X (-1,-111}* Then every linear-swap in I' e'quilibrium is equivalent to a (non-canonical) degree- k-swap equilibrium.
Proof. The proof follows a similar idea to the previous one: we wish to construct a scenario such that, with any polynomial of degree less than k the deviator cannot learn anything about æ. and with a polynomial of degree the deviator can only implement linear functions on æ. Let n be any linear- swap equilibrium. Let ) 1) NA, and index the coordinates of y E y by pairs (j, é) where j E [N] and É E [k:]. Define Φ(y); = [ee][]] y e]. Finally, define the distribution T' E A()") as follows: sampling y n'' is done by sampling æ n, and then, for each player i and index j. sampling -. E
13 uniformly at random under the constraint that II. y: [. E] = x. We will write r'Iæ for the conditional distribution of y n', conditioned on sampling the given x ~ T. Now consider the generalized profile (), db T (i.e., every player shares the same signal set 3' and equilibrium deviation function & y - X²). We see that it is equivalent to (X' id, T) by construction. We claim now that it is a degree-k equilibrium which would complete the proof. Consider any d k function o' y + X, and define a X X by (xz) Ey-ryja ø' (3()) It suffices to show that &e is a linear map, since then deviating to Φi would equate to applying the linear
27

---

deviation v to æ. Indeed, expressing
('vy)
Σ
asms(y)
where ms(y) == II yli, (A))S
(M)
[*]] for some j. in which case By-r' (y) =lj]. That is, the only monomials of nonzero expectation are those which multiply together all the y -s., in which case the expectation is exactly æli]. Thus, we have
we see that E B/ ms y 0 except when S S, (
(x))
Σ as
[ms(y)]
Σ as,
[y)] Σ as, assæa)) æزاه
y~v /
which is indeed linear in æ.
One may wonder at this point about why the above two results do not contradict the fact that NFCE, which supposedly are the Φ. -qquilibiia do satisfy the revelation principle and are certainly nor equivalent to linear-swap equilibria. The answer is that the equivalence between swap deviations and N-mediator deviations only holds for strategy spaces of size at most N-and the strategy spaces V; constructed as part of both proof' have size (at least) Nk. When V/ has size more than N, the set &N med is no longer the set of all functions V/ cony XG In other words, the set of canonical &b a equilibria is equivalent to the set of canonical NFCE, but that does not contradict the fact that there exist non-canonical T -equiliba..
I Omitted proofs
In this section, we provide the proofs omitted from the previous sections.
L1 Proofs from Section
We first provide the missing proofs from Appendix B. We start with Proposition B.1, the statement of which is recalled below.
Proposition B.1 (Hazan and Kale, 2007). Consider a regret minimizer R operating over 1... If R. runs in time poly N, 1/6) and guarantees Regas S e for any sequence of utilities, then there is (N Doly(N,1/e) algorithm for computing an (ev N-fxxe point of any & E &i with respect to || 1122. assuming that Φ can be evaluated in polynomial time.
Proof. Suppose that R outputs strategy (x()) conv X' each time & E [T]. The basic idea is to determine whether | (ze(t)) (011 2 S ev N: if so, the process can terminate as we have identified an Nev/N)-iied point of @ with respect to || ll2- Otherwise, we construct the utility function
ev
n (+) conv 3 x
VN (( - a011 (00 (2:())) at(() x (9)
We note that, by Cauchy-Schware (x)) < 1 since | - (1) S VN; hence, the util- ity function adheres to our normalization constraint. Now, if at all rounds it was the case that | (x)()) (0 > evN, we have
T
T
Regar
2
10 (2)
- Σ
(1
(x
(1) >
(5)
1=1
t=1
= since (0)) (x) ) = 0 and n. (1) (xx())))
vN 1100 (x(()x)))) - x (0) ||2 for all f. E [T]. We conclude that
1
T
(5) contradicts the assumption that Regas < for any sequence of utilities, turn implying that there exists [7] such that ( (x)()) (011 S evN. Given that we can evaluate & in time Poly(N) (by assumption), we can also compute each error || (x(")) (x() || in polynomial time, concluding the proof.
We next turn our attention to the proof of Theorem 3.3. We first observe that कh contains functions of the following form.
28

---

Lemma 1.1. Φ contains all functions of the form
Σ (Si)
II
x
II
(1- =b5))
E @N((N) II mmj]]
II JE(N]/Sx
(1
SISIN
JES,
JEINNNS1
SY
JESN
where o = (oi...., .N). terms to be evaluated as 1.)
13 + 10. (The convention above is that a product with no
Above, we slightly abuse notation by interpreting Sj S [N] as a point in {0, [0.1] Lemma I.1 evident from the definition of the behavioral strategy map B: o² (x) (()=~(())) ((x'), and expanding the expectation gives the expression of Lemma L1 thethe probability of a set S is exactly IiES x1]]] s =(j]). We will show that PPAD-hardness for computing fixed points persists under the set of functions contained in h (per Lemma 1.1).
Our starting point the usual generalized circuit problem (abbreviated as GCIRCUIT), introduced by Chen et al. [2009]; it is a generalization of typical arithmetic circuit but with the twist that it may include cycles. (In what follows, we borrow some notation from the paper of Filos-Ratsike et al. [2023].)
Definition I.2 (Chen et al., 2009). A generalized circuit with respect to set of gate-types G is a list of gates 91, .I..... 9M- Every gate 9i has type G; E G. Depending on its type, 9; may have zero, one or two input gates, which will be index by j, k E [M]. with the restriction that i, k are pairwise distinct.
We denote by v MM] + [0. 1] function that assigns an input gate to a value in [0, 1]. Each gate imposes constraint induced by its corresponding type. For example, let us consider the following types.
Gf = G+, then v(g:) = min(1, v(gg) + v(gx));
if G; G_,, then v(g)) max(0, v(g)) v(ga));
if G; G1, then (g.)) 1;
if G; = G1_, then vg:)) = v(g))) and
if G; Gx then v(g:) v(gz) v vgg)).
In accordance with the above types, we define F [0, 1|M + [0, 1jM to be the function mapping any initial evaluation of the gates to (v(g1),..., (ggm)) The main problem of interest can be now phrased as follows.
Definition 1.3 (e-GCIRCUIT). The problem e- E-GIIRCUIT asks for fixed point of F with respect to ||- lloos that is, an assignment v [M] + [0. 1] such that all gates are e-satisfied.
A satisfying assignment always exists by Brouwer's theorem, but the associated computationa prob- lem is PPAD-hard. In fact, by virtue a recent result of MitssRassskas et al. [2023], PPAD- hardnesddesss persists even if one significantly restricts the type of gates.
Theorem 1.4 (Filos-Rate Ratsikas et al., 2023). Even when G IG+, GI- there is an absolute con- stant é > 0 such that computing an e-fixed point of F with respect to 1l is PPAD-complete! 14
Yet, the addition gate G4 does not induce a multilinear in the form Lemma I.1. We will address this by showing that the gate G. can be approximately simulated via small number of gates with type either G1 or Gx- To provide hetter intuition, we first prove this claim under the assumption that the gates are satisfied exactly, and then proceed with the more general statement. In the sequel, we sometimes use the shorthand notation i = t' + > t E [1' e, + +
Lemma I.5. Any addition gate G- can be approximated with at most e > 0 error using (loo(L//e)/e) gates with type either Gi_ or Gx
M "Deligkas et al. [2022] showed that, for certain variant of this problem, any constant < 0.1 suffices. It Rubinstein [2016] who first proved that the problem is PPAD-hard even for constant 0.
29

---

Proof. Let 10, 1100 E {0,11. 1/. We define the mapping
f 12) + (1 (1 - (1) (12);
We consider the sequence +f ((+1)) (r+1) f(ts-), for 1122..... We will show that
22
min(1, t + +24)) {1 +
(6)
for C log(1/ 1/)) log( +
1 @(log(1/0//c). We first observe that ((tz1) 2 (1 and 17th
-12
((-)
1 + 1/
(2)
(1) We consider two cases.
. t (c) > 11-6. - c, then 11th -1 - +
(1
(C) +t
2 1 - c, in turn implying that min (1, ((1) +
(1) 21 1 - c. This clearly implies (6) as 1 E 10.
In the contrary case, if (()) < 1 - e, then (0) II (()) < < (11-)) Se, where we
used the fact that ((()) (0)
< 1 c. So, min(1, (1,11 + = min(1, ((] (1
(0) + 2 1 (0) 4
(C)
Lemma 1.6, Any addition gate G+ can be approximated with at most e > 0 error using ((lo((L/e)/e) gates with type either G1- or Gx, each with error e' O(e/C) O
Proof. Let 1 (2)
E
10, 1]. We consider the sequence
[0, 3 (ti (1(++) ((++1) = -1-
1- +5 + (() +τ) T= 1,2,
22
Here, (t(T+T), 122 ) can be indeed obtained from (57 ,(7) using 5 gates with type either Gi- or each with error at most c'. We will show that
(()))
= min(1,e + = ( +c c
for C 2 log(6/e]
+ 1 ((lee(1/))/e). Below, we will take e' == e/ (12C). We first observe
log( i-r/12/
that e1
(1+1)
+ 12
(T+1)
= (1) + +bb" + Ge', thereby implying that ( + 1 = (1) + (1) + 6Ce'.
Further,
{(T)
S 5/
(7+1)
+ 5e'. Hence, { s (()) 50e.. We consider two cases.
[0) (C) - c/2, then t 12 2 (C) + 12
(
(C) 6Cd 21 c/2 = since (1)
=
c' c'=C( This implies that min { + +12 2 1 - c, and (7) follows.
In the contrary case, if (C) < 1 e/2, then (C) < (1 - -e/2 + 5CE)) + +
(1 (1- e(1)) ( +é' Thus, e s Ce' + (1 - 1011)// < </4, where we used the fact
(o/()/e) that C log( b + 1. In turn we have t +1 < (( + +t1
(1)
(0)
(C) -CCé' I 1 e/4.
We conclude by observing that (()) = (t) + +15h (0) + 6Ce' = ( + 150h + 3c/4.
As a result, for any absolute constant > 0. we can reduce in polynomial time an G-GIICCITT instance consisting of M gates with a set of types G G. to an GCGCIICUIT instance consisting of ((M) gates with a set of types g' = [GI_, Gx J. so long as = Oc is sufficiently small. Together with Thcorem L4, we arrive at the following conclusion.
Proposition 1.7. Even when G == (Gx,G1-), there is an absolute constant e > 0 such that computing e-fixed point of F with respect to llso is PPAD-complete.
30

---

Having established this reduction, a function F arising from such circuits is clearly multilinear that can be expressed in the form of Lemma I.I. Indeed, we simply observe that, for S [M] and S S [N] with S N = 0. we have
II JES
[ II
x[1)) =
II JE[M]]SUs
(æ]s) +1 -[1))
II JES
x II JES
(1 x(1))
JES
Σ
II
x mijl
II
(L x (]),
S jESUS'
jESUS"
where the summation over all partitions S" of [N] \ USU So, combining with Proposi- tion B.I, we arrive at Theorem 3.3, which is restated below for the convenience of the reader.
Theorem 3.3. a regret minimizer outputs strategies in [0, 1]%, it PPAD-hard to guarantee Regas S <e/VN. even with respect to legree deviations and an absolute constant e 0.
In the above reduction, we used the inequality || 11x S || |l2 so as to translate the guarantee of Proposition B.1 in the language of Theorem L.. That inequality can be loose, and instead let us explain how one can obtain sharper hardness results by relying on a stronger complexity assumption which pertains to the so-called (c, GCIRCUIT problem. This relaxes the e-GCIRCUIT problem by allowing at most 6-fraction of the gates to have an error larger than c. In this context, Babichenko al. [2016) put forward the following conjecture.
Conjecture 1.8 (Babichenko et al., 2016). There exist absolute constants e, 6 > 0 such that solving the (e, (..5)GGRRCUTT problem with M gates requires 20(M) time.
In light of the simplifications observed by Filos- Ratsikas et al. [2023] (Theorem I.4) in conjunction with Lemma 16,, is not hard to show that Conjecture 1.8 can be equivalently phrased by restricting the gates to involve solely multilinear operations analogously to Proposition 1.7. Namely, if the number of gates increases by a factor of C = C(e). it suffices to take (6//C). Now, the point is that Conjecture I.8 is more aligned with guarantee in terms of || - 1|2- Indeed, if at least a d-fraction of the gates incur at least an error, it follows that FF())) - x Z evōvN (we can assume here that NN is an integer). We can thus strengthen Theorem 3.3 as follows.
O(e/C) and 8'
Theorem 199, Suppose that Conjecture 188 holds. If R outputs strategies in [0, 11 guaranteeing
Regae S requires time 2D(N), even with respect to low-degree deviations and an absolute constant <> 0.
1.2 Proofs from Section C
We first spell out the construction that establishes Theorem C.2, which is refinement of the al- gorithm of Gordon et al. [2008] described earlier in Appendix A. In particular, the one but crucial difference lies in using an e-expected fixed point (Line 3). In the context of Algorithm we sume that the interface of a regret minimizer R consists of two components: R. RR.NEXSSTRATEGY() which returns the next strategy of R; and R. OO..EREEUUU..TTT a utility function, whereupon R may update its internal state accordingly.
which provides to R as feedback
Algorithm 1:
r-regret minimizer using fixed points in expectation
Input:
An external regret minimizer Rs over
Output: A Ø-regret minimizer R. over X'
function NEXTŠTRATRGYO
(it) < (
2
3 x (9) + c-expected fixed point of s(9) (Definition C.I)
4 return (4)
function OBSERVEUTILITY(UU))
Set u6 : b 2 (1)), EntO ((x(())))
Rr. OBSSEERVUUUUUIIYY(0SS
We next show that there is certain equivalence between expected fixed points and e-regret mini- mization over A(X), which mirrors the construction of Hazan and Kale [2007].
31

---

Proposition C.3. Consider a regret minimizer R operating over ( If R runs in time 1 poly(N, 1/c) and guarantees Rega I for any sequence of utilities, then there is a poly(N, 1/c) algorithm for computing ) expeectd fixed points of & D. assuming that we efficiently compute =000) ((((())))))))))))))))) x0) at any time t. Here, Dx is the diameter of X with respect to ||. 2
Proof. Suppose that R outputs a strategy (1() E ( At each time t E [7], we can terminate [et (o(x(()) 1l2 I xDx; that is, we have identified an (cDx)) fixed point. Otherwise, construct the utility function
xz =0(0), x(1) x(1)),
n :33 Dx
E (a(t))ar()) (6(xx
Eg (0 (0(x(()) 20))
which indeed satisfies the normalization constraint tu(0(2)) I Now, if at all iterations it was the case that (1)0))<016(00 " > eDx, we have
Regs 2
Σ
T
(e)
(BB E (0((2())1))
(((a))))((()
1 T
Σ
(x
>
T
all)) (al))
1=1
1=1
since u/ (1((1)) and
(t)
E (ett)
[x(((())
E 1(())x(1)) (6)(x(()) - x 20(1)]
Dx
for all & [T]. This contradicts the assumption that Roge I for any sequence of utilities, in turn implying that there exists t E [T]] such that r()) is an e-expected fixed point. Given that, by assumption, we can compute (t))) (())))))) - (+) [ for any time f, the claim follows.
1.3 Proof of Corollary 4.1
In this subsection, we discuss how expected fixed points (per Definition C.I) can be used speed up equilibrium computation even in settings where actual fixed points can be computed in polynomial time. In particular, we recall the following result, which stated earlier in the main body.
Corollary 4.1. For any n-player game in normal form, there is algorithm that computes e-correlated equilibrium and runs in time
o
A2) )) o Alog A (EO(M,A)+ +n E2
Indeed, using the algorithm of Blum and Mansour [2007) instantiated with MWU, 15 one can guarantee (average) swap regret bounded as O P(AAlog A/T), where T is the number of iterations; hence, taking T ( log A/e)) guarantees at most swap regret for each player. Further, a function stochastic matrix
here be represented point in time ((4²) via matrix-vector product. As a result, each iteration of Algorithm 1 can be implemented with single oracle call to (2), along with n updates- for each player-each of which has complexity bounded as O(A2/e /e) (Theorem C.7). This implies Corollary 4.1.
states; such, can be evaluated any
Let compare the complexity of Corollary 4.1 with prior results. First, when > 0 the best running time follows from the recent algorithms of Dagan et al. [2024] and Peng and Rubinstein [2024], but those quickly became superpolynomial even when of iterations their algorithm scales as (log A 4)0(1/0) On the other end the spectrum, one can compute exact correlated equilibrium in polynomial time using the "cllispoid against hope" algo- rithm [Papadimitriou and Roughgarden, 2008, Jiang and eeytoon-rowwr 2011]. The original paper by Papadimitriou and Roughgarden [2008] did not specify the exact complexity of the algorithm, but the subsequent work of Jiang and Leyton-Broot -Boown [201 1]-whichh analyzed a slightly different
//log& A; indeed, the number
The exponential weights map can generate irrational outputs, but this can be addressed by truncating to sufficiently large number of bits, which does not essentially affect the regret.
32

---

version based on a derandomized separation oracle- came up with a bound of n A in terms of the number of iterations of the ellipsoid; the overall running time higher than that. While the analysis of Jiang and Leyton-Brown [2011] I] can likely be significantly improved- as acknowledged by the authors, we do not expect that algorithm to be competitive unless one searching for very high-precision solutions.
The original algorithm of Blum and Mansour 22007]-instantitter as usual with Mwu-requires computing a stationary distribution of a Markov chain in every iteration. This amounts to solving a linear system, which in theory requires running time of O(A"), where w R 2.37 is the exponent of matrix multiplication [Williams et al., 2024]. Without fast matrix multiplication-VV wwihhhh is currently widely impractical the running time would instead be O(4*). strict improvement over that running time can be obtained using the optimistic counterpart of MWU (OMWU) [Duskalakis et al., 2021], which has been shown to reduce the number of iterations to ((A/c) without essentially affecting the per-iteration complexity. Corollary 4.1 improves over that in the regime where c Z 1/A8 -T, where w = 2.37 is the exponent of matrix multiplication [Williams et al., 2024]; without fast matrix multiplication, the lower bound is instead e 2 1/VA.
Another notable attempt at improving the complexity of Blum and Mansour [2007] was made by Greenwald et al. [2008] using power iteration. For parameter 2 1, their algorithm guarantees at most O( AAp/T) average internal regret with per-iteration complexity of (2AA2/p /p) (without fast matrix multiplication). Casting this guarantee in terms of swap regret, and observing that the overall running time is invariant p. we see that the resulting complexity is no better than that via OMWU, which we discussed earlier; the approach of Greenwald et al. [2008] is based on regret matching, which incurs an inferior regret bound compared to MWU, but is nevertheless known to per- form well in practice. An improvement to the algorithm Blum and Mansour [2007] was obtained by Yang and Mohri [2017], but requires a further assumption on the minimum probability given to every expert; it is unclear whether such an assumption can be guaranteed in general.
The above discussion concerns algorithms operating with full feedback. In the bandit feedback, Ito [2020] came up with a way to update a single column in each iteration, but it still requires computing a stationary distribution in every iteration. Ito [2020] claims that this can be achieved in time almost quadratic time through the work of Cohen et al. [2017]; however, the complexity of the algorithm of Cohen et al. [2017] depends on the condition number of the Markov chain, and it unclear how to bound that in our setting. On the other hand, algorithms in the bandit setting do not require access to expectation oracle. This can be beneficial in certain settings, but our discussion here focuses on the regime where the expectation oracle does not dominate the per-iteration complexity. We conjecture that Theorem C.7 can be generalized to the bandit setting, in which case our improvement will also manifest in the regime where the cost of the expectation oracle far outweighs the per- iteration complexity of Theorem C.7, but that is not within our scope in this paper.
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims made in the abstract and introduction are proven in Appendices C to and
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
All limitations and assumptions are stated Appendices E and I.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specificattin, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [es]]
34

---

Justification:
The full set of assumptions and proofs are given in Appendices C to E and I.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
35

---

Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nipp) cc/
vublic/guides/Cee Saaiidde/oodSSumiisee
Policy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips cc/ wtcp/publcc/gee htapiic/ggui////ee wewiddeeeoeeeubbeeeeeeeee ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
36

---

is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http:/rrppp..pppppppeeeettticeae
Answer: [Yes]
Justification:
The contribution of the paper is theoretical, and conforms in every respect with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification:
The contribution of the paper is thcoretical, and we do foresee any societal
impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
37

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility MI).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
[NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi thcode com/ /attaset has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
38

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsoureing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "NRLicIGwKt", "reviewer": "Reviewer_VzB7", "summary": "This work seems to design some fast regret minimization algorithms. However, to be honest, I could not find the learning protocols nor understand the learning problem set-up. It is hard for me to find what information is revealed in each round after taking some action. \nSo, I suggest adding some simple applications to help readers to understand the learning protocol, for example, the tree-form decision problems.\n\nMajor comments:\n\nIs there any lower bound? How can I measure the tightness of the presented results?\nIs it related to P vs NP?  Can it be reduced to an NP-hard problem?\nFor theoretical analysis, is it finite-time analysis or asymptotic analysis?\nI know it is a theory work, but is it any experiments?\n\nMinor comments:\n\nIn Line 110, a comma is missing in $\\{ \\ \\}$.\n\nIn Line 143, it is better to say $x[j]'s$.\n\n\n\nIn Line 271, it should be \\citep{} for the citation.", "questions": "see the first box", "limitations": "I hope to see some experiments though", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "see the first box", "weaknesses": "see the first box", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q: *However, to be honest, I could not find the learning protocols nor understand the learning problem set-up.*\n\nA: We will clarify further how the learning protocol proceeds in the revised version. Note that we operate in the standard model when it comes to learning in extensive-form games.\n\n\nQ: *Is there any lower bound? How can I measure the tightness of the presented results? Is it related to P vs NP? Can it be reduced to an NP-hard problem?*\n\nA: The paper [Anonymous, 2024] that was included in the supplemental materials shows an exponential lower bound in the case of *swap regret*, that is, when $k=N$. One can interpret our results as \"interpolating\" between the known extreme cases of $k=1$ (where efficient algorithms exist due to Farina & Pipis [2023] and Zhang et al [2024]) and $k=N$, where the above lower bound holds. See also response to aMpb's Q1 below.\n\n\nQ: *For theoretical analysis, is it finite-time analysis or asymptotic analysis?*\n\nA: The theoretical analysis is all finite-time. Each theorem specifies an upper bound on the number of rounds required to achieve a certain equilibrium gap $\\epsilon$. The big-O notation hides only absolute constants.\n\nQ: *I know it is a theory work, but is it any experiments?*\n\nA: We agree that the main merit of the paper is theoretical. Our notion of rationality is the strongest that can be efficiently (i.e., at a polynomially sublinear regret rate) guaranteed in imperfect-information sequential games (i.e., extensive-form games), a fundamental class of strategic interactions. We have not run experiements using our algorithm, but we agree that this may be something interesting to do in the future.\n\nThank you for pointing out the minor errors. We will fix them in the next version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "c9nJv79H7n", "reviewer": "Reviewer_aMpb", "summary": "This work aims to bridge the gap between the $N^{O(1/\\varepsilon)}$ result for attaining the $\\varepsilon$ swap regret and the $\\operatorname{poly}(N)/\\varepsilon^2$ result for attaining the $\\varepsilon$ linear-swap regret for extensive-form games. To this end, the authors generalize the untimed communication deviations proposed by [1] to k-mediator deviations. The authors prove that obtaining the $\\varepsilon$ regret w.r.t. the set of k-mediator deviations in $N^{O(k)}/\\varepsilon^2$ rounds is achievable. As several byproducts, the authors show a sample complexity of $N^{O(kd)^3}/\\varepsilon^2$ for minimizing the regret against degree-k polynomial deviations, and an algorithm with the lowest computation complexity to compute the $\\varepsilon$-correlated equilibria in normal-form games in the medium-precision regime.\n\n[1] Zhang et al. Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Extensive-Form Games. ICLR, 24.", "questions": "Please see the weakness part above.", "limitations": "Not applicable.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.\tThe motivation to bridge the gap between the $N^{O(1/\\varepsilon)}$ result for attaining the $\\varepsilon$ swap regret and the $\\operatorname{poly}(N)/\\varepsilon^2$ result for attaining the $\\varepsilon$ linear-swap regret is of interest.", "weaknesses": "My main concern regarding this work is the presentation. Several key parts of the current writing are not very clear and somewhat hard to follow, detailed as follows. \n\n1.\tThe main motivation of this work is to bridge the gap between the $N^{O(1/\\varepsilon)}$ result for attaining the $\\varepsilon$ swap regret and the $\\operatorname{poly}(N)/\\varepsilon^2$ result for attaining $\\varepsilon$ linear-swap regret in previous works. Does the current result of the $N^{O(k)}/\\varepsilon^2$ sample complexity for obtaining the $\\varepsilon$ regret w.r.t. the set of k-mediator deviations well interpolate between the above two results? It is a bit strange that there seem to be no discussions about the relationship between the results in this work and the two results in previous works. I think the result in this work replicates the $\\operatorname{poly}(N)/\\varepsilon^2$ result when $k=1$, but it is unclear to me in which sense the result in this work will replicate the previous $N^{O(1/\\varepsilon)}$ result.\n2.\tWhy do we need to relate the k-mediator deviations to low-degree polynomials? After relating the k-mediator deviations to low-degree polynomials, the convergence rate is worse by a $N^{O(k^2d^3)}$ factor. There might be some benefits in doing so, but I did not seem to find the relevant descriptions in the paper.\n3.\tThere is a rich line of most related works in the literature, while it is currently a bit heavy to fully understand the advantages of the results in this work against those in previous works merely from the statements in Section 5. It would be better if a table reflecting the convergence rate, the computation complexity, and the required regime of $\\varepsilon$ of the results in this work and those in previous works is included in the paper.\n4.\tThere is an expectation taken over the randomness of the player in the regret defined in Eq. (1), while the previous works study high probability regret (say [2,3]). As such, it seems that the algorithm in this work can only obtain approximate correlated equilibria in expectation, while previous works can obtain the approximate correlated equilibria with high probability. I would suggest the authors incorporate necessary discussions about this point.\n5.\tFor Section 4.1, it seems that the proposed operation of approximating fixed points in expectation can only work with finding approximate correlated equilibria in expectation. Can this trick be extended to the case of finding approximate correlated equilibria with high probability? This is also somewhat related to my question above.\n6.\tIn Line 135, it is not clear to me what is the purpose of constructing the depth-k decision tree deviations. It would be better to first introduce the motivation for doing so before diving into the details of its construction.\n7.\tAt the end of the statement of Theorem 3.4, it seems that it should be something like $N^{O(k)}/\\varepsilon$ (or $N^{O(k)}/\\varepsilon^2$) instead of $N^{O(k)}$?\n8.\tIn Line 228, what does it mean by “succinct representation”?\n9.\tFor Section 4.2, my understanding is that the authors consider a more convenient and suitable formulation than the tree-form formulation to better leverage the connection between low-depth decision trees and low-degree polynomials. Are there any technical difficulties in achieving this?\n10.\tIn this work, most of the time $\\Phi$ is termed as the set of the deviations while sometimes it is termed as the set of the transformation functions. I would suggest the authors unify the descriptions for clarity. \n\nOverall, the current writing prevents me from well evaluating the significance of the results and the technical novelty of this work and hence I am not able to recommend an acceptance of this work.\n\n[2] Bai et al. Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent. NeurIPS, 22.\n\n[3] Farina et al. Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games. NeurIPS, 23.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. *On \"Bridging the gap\"*: You are correct: while we match the $\\text{poly}(N)/\\epsilon^2$ result for linear-swap regret when $k=1$, we do not match the $N^{\\tilde O(1/\\epsilon)}$ bound for swap regret shown by Dagan et al. and Peng and Rubinstein. \n2. *$k$-mediator deviations and low-degree polynomials*: Note that the $k$ in the $N^{O(k)}/\\epsilon^2$ bound refers to something different than the $k$ in the $N^{O(k^3)}/\\epsilon^2$ bound: the former is the number of mediators; the latter is the degree of a polynomial. As all $k$-mediator deviations are degree-$k$ polynomials (but not vice-versa), it should not be surprising that our bound in the latter case is worse.\n3. Thanks for the suggestion. We have created a table comparing the results in that section to past results, and attached it in our message to all reviewers. We will include this table in the next version.\n4. A clarification here: Our algorithms are *deterministic*--they produce as their output on each round $t$ a *distribution* $\\pi^t$. The fact that Eq. (1) contains an expectation simply is how regret is defined, and does not denote that the algorithm ever actually samples from $\\pi^t$. We will makes this more clear in the revised version as we see that it can cause confusion.\n5. Like above, a \"fixed point in expectation\" is actually a *distribution* $\\pi^t$, which is computed by a deterministic algorithm.\n6. There are (at least) two reasons to consider the set of depth-$k$ decision trees: first, they are by themselves a fairly natural class of functions, and second, our result about low-degree deviations fundamentally uses a connection between degree-$k$ polynomials and depth-$O(k^3)$ decision trees (Theorem 4.2). We will add a note about this to the next version.\n7. That sentence should read \"For $\\Phi^k_\\text{med}$, the same bounds hold except that both instances of $N^{O(kd)^3}$ should be replaced by $N^{O(k)}$.\" We will fix this in the next version.\n8. \"Succinct\" here simply means the game is given by an efficient oracle for computing the utility vectors (Eq. (2)), rather than as an explicit payoff tensor. This is fairly standard language, also used by (among many other papers) the cited paper [Papadimitriou and Roughgarden 2008]\n9. In the first part of Section 4.2, to provide better intuition about the general case, we indeed focus on a very specific type of tree-form decision problems (corresponding to the hypercube). As the reviewer points out, this is convenient because of the connection between low-depth decision trees and low-degree polynomials (Theorem 4.2). The main technical challenge is to extend this to general tree-form decision problems, and that is the subject of the rest of Section 4.2.\n11. Thank you. As you correctly point out, \"deviation\" and \"[strategy] transformation function\" are the same thing. We'll unify the terminology in the next version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nVMp494jPM", "reviewer": "Reviewer_o8Ue", "summary": "This paper explores and advances the research direction of linear-swap regret in extensive-form games, extending it to low-degree swaps and bridging the gap to results on general swap regret. The technical contributions include the concept of k-mediator deviations, which relate to low-degree polynomials and depth-k decision trees on n>>k variables, and a crucial observation that if a player is allowed to output a probability distribution over strategies, computing it is sufficient to compute an approximate fixed point of the deviations in expectation.\n\nThe concept of depth-k deviations allows a deviator to select an action after observing a strategy on a single terminal for k adaptive rounds. Choosing $k=1$ or $k=N$ leads to linear-swap deviations or all swap deviations, respectively. The main results are as follows:\n\n1. For depth-k deviations and the strategy space of a hypercube, there is an online learning algorithm that achieves at most $\\\\epsilon$ average $\\\\Phi$-regret in $N^{O(k)} / \\\\epsilon^2$ rounds with $N^{O(k)} / \\\\epsilon$ running time per round.\n\n\n1. For deviations that are polynomials of degree k and the strategy space of a hypercube, there is an online learning algorithm that achieves at most $\\\\epsilon$ average $\\\\Phi$-regret in $N^{O(k)} / \\\\epsilon^2$ rounds with $N^{O(k^3)} / \\\\epsilon$ running time per round.\n2. It is PPAD-hard to guarante a regret of at most $\\\\epsilon / \\\\sqrt{N}$ if a regret minimizer outputs a single strategy in $\\[0,1\\]^N$.\n\n3. For depth-k deviations and extensive-form games, there is an online learning algorithm that achieves at most $\\\\epsilon$ average $\\\\Phi$-regret in $N^{O(k)} / \\\\epsilon^2$ rounds with $N^{O(k)} / \\\\epsilon$ running time per round.\n\n4. For deviations that are polynomials of degree k and extensive-form games of depth $d$, there is an online learning algorithm that achieves at most $\\\\epsilon \\\\Phi$ average $\\\\Phi$-regret in $N^{O(kd)^3} / \\\\epsilon^2$ rounds with $N^{O(kd)^3} / \\\\epsilon$ running time per round.", "questions": "Could you elaborate on the difference between mixed strategies and probability distributions over strategies? Is it true that the worst-case regret for the former is bounded, but (at least in your results) the worst-case regret is unbounded?\n\nNote: As a reader who is completely unfamiliar with the topic, the preliminaries could have covered a *deviations*.", "limitations": "/", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The results bridge the gap between linear swap and arbitrary swap regret.\n- The technical contributions show the advantage of probabilistic strategies with respect to hardness, i.e., that a fixed point in expectation is enough for optimization.", "weaknesses": "- It seems the gap is bridged \"from below\", i.e., for large $k$ the results may become worse than known bounds.\n- ~~Allowing the learner to output probability distributions of strategies seems to weaken the model and/or the guarantees of results in this model, e.g., more than allowing mixed strategies over pure strategies does.~~ (edit: see rebuttal)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*It seems the gap is bridged \"from below\", i.e., for large $k$ the results may become worse than known bounds.*\n\nThis is correct, in particular, for $k > \\tilde O(1/\\epsilon)$ our bounds become worse than those of Peng and Rubinstein [2024] and Dagan et al [2024]. \n\n*Allowing the learner to output probability distributions of strategies seems to weaken the model and/or the guarantees of results in this model, e.g., more than allowing mixed strategies over pure strategies does.*\n\nWe do not believe that working with mixed rather than behavioral strategies (see also next response regarding the difference between mixed and behavioral) is \"weakening\" in any meaningful sense. Indeed:\n* In Theorem 3.3, we show that if a learner is restricted to playing only behavioral strategies, it is PPAD-hard to achieve $\\Phi$-regret $\\epsilon/\\sqrt{N}$ even when $\\Phi$ is the set of degree-$k$ polynomials and $k$ and $\\epsilon$ are absolute constants. Thus, in some sense, going beyond behavioral strategies to use mixed strategies is *necessary* to achieve efficient learning algorithms.\n* Peng and Rubinstein [2024] and Dagan et al [2024] also use mixed rather than behavioral strategies to achieve their result (this should be unsurprising, given the previous bullet!)\n\n*Could you elaborate on the difference between mixed strategies and probability distributions over strategies?*\n\nA mixed strategy *is* a probability distribution over pure strategies. The reviewer might be confusing a mixed strategy with a *behavioral* strategy. A behavioral strategy is a mixed strategy that selects actions independently at every decision point. Each point $\\boldsymbol x \\in \\text{conv}(\\mathcal X)$ essentially uniquely\\* specifies a behavioral strategy, but does not uniquely specify a mixed strategy.\n\n\\*except at decision points reached with probability zero\n\n*Is it true that the worst-case regret for the former is bounded, but (at least in your results) the worst-case regret is unbounded?*\n\nAs stated above, Theorem 3.3 shows that no efficient regret minimizer can exist that only uses behavioral strategies, unless P = PPAD. Theorems 3.1, 3.2, and 3.4 show that, when mixed strategies are permitted, efficient regret minimizers *do* exist.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thanks for the reviews! We have attached to this message a pdf containing two tables which compare the results of this paper to results of past papers. We will include both of these tables in the next version.

Meta-review: The submission gives a (slow but) polynomial time algorithm for minimizing \Phi-regret wrt to a few classes of deviations such as low-degree swaps. This generalizes previous work on linear deviations. 

The reviews and discussion were inconclusive, so I also read the paper myself. 
Some points:

1. Two reviewers (and I, independently) were annoyed with the claim in the abstract that in this paper "take[s] a step toward bridging the gap between those two results". The bounds in the paper deteriorate quickly when $k$ is large. 

2. The authors don't bother motivating the classes of deviations that they consider. I feel like this is a major drawback.

3. I really like the separation behavioral and more general mixed strategies! I feel like this a nice and somewhat surprising contribution. 

4. There were some concerns in reviews about presentation. 


Overall I'm leaning toward accepting the paper due to #3. This is in hope that the authors address #4, and soften the abstract to address #1.
Decision: Accept (poster)