Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games

Can you provide some explanations for why CFR achieves a better regret than the algorithm in Farina & Pipis (2023)? Figure 2 is presented without accompanying discussion.

PCFR+ performs better than projected gradient descent, both in terms of per-iteration complexity and in terms of empirical performance. However, PCFR+ can only be applied to certain convex sets (unlike projected gradient descent, which applies to any convex set). One of the key contributions of our paper is indeed in showing that, through a different characterization of $\Phi_\text{Lin}$ (specifically, the constraints that define $\Phi_\text{UTC}$), algorithms such as PCFR+ can be employed. The practical merits of CFR-family algorithms have been documented by many researchers before us, which established that family as a natural default choice for tree- and DAG-form decision spaces. Indeed, the fact that our construction, unlike that of Farina & Pipis, allows the application of CFR-family algorithms---thus enabling this practical improvement---is, in our minds, one of the main merits of our approach.

Since both CFR and Farina & Pipis (2023) offer an upper bound of $O(\sqrt{T} d^2)$, is it possible to demonstrate that this is also the lower bound?

We do not believe that this bound is tight, in fact. For example, in games, there are ways to achieve $\text{poly}(d) \cdot \log(T)$ regret for EFCE, as we discuss in the conclusion section. Also, CFR usually doesn't get the optimal theoretical guarantees: for example, for external regret on tree-form decision problems, KOMWU [3] improves upon it by a quadratic factor. Both of these ideas seem somewhat tricky to extend to linear deviations; we leave these as open questions for future work.

[3] G Farina, CW Lee, H Luo, C Kroer (ICML 2022). "Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games"

Could you elaborate on how to employ the algorithm from Cohen et al. (2021) to achieve $\tilde O(d^\omega)$ complexity? What is the linear program that must be solved in formal? This addition would make the paper easier to read.

Cohen et al. (2021) show that linear programs with $d$ variables/constraints can be solved in time $\tilde O(d^\omega)$. The fixed-point problem is just an LP feasibility problem of the form "find $\mathbf x \in \mathbb R^d$ such that $\mathbf x \in \mathcal X$ and $\mathbf A\mathbf x = \mathbf x$", where $\mathbf A$ is the matrix representing the linear deviation and the constraint $\mathbf x \in \mathcal X$ can be represented with $O(d)$ constraints via the sequence form (first equation, page 3). This LP is also stated in the paper at the end of Section 2. In the updated version, we have included a forward pointer from the introduction to Section 6, where the fixed point problem is discussed in more detail.

more discussion or results about the nature of untimed communication equilibria would be helpful, should space allow (perhaps a section about connections to standard communication equilibria, which has been written in the appendix already).

Appendix A.6 defines the untimed private communication equilibrium, which partially addresses the reviewer's question. We wanted to place it in the body; unfortunately, space did not permit this, but we agree with the reviewer that the appendix contains interesting content. Defining the untimed (non-private) communication equilibrium seems quite tricky, as we pointed out in a footnote. Since the reviewer seems interested in this, we will now elaborate a bit more.

The untimed private communication equilibrium is easily defineable. We define it in Appendix A.6, and also prove the relevant revelation principle. As we state, the word private here is included to emphasize the fact that untimed private communication equilibria are correlated strategy profiles, and that this corresponds to a sort of privacy constraint, where the mediator cannot pass information between players. This is unlike the usual communication equilibrium definition: communication equilibria may not be strategy profiles at all, because the mediator can effectively "pass information" between players.

Untimed communication equilibria (without the privacy constraint) are far more tricky to define, especially in a way that doesn't quickly collapse to the regular notion of communication equilibrium. The following is not formal but should give some intuition. In a 3-player game, the mediator is always guaranteed that two of the players have not deviated, and those two players will have messages synchronized with the game clock. Therefore, under reasonable assumptions on how often each player makes moves, the mediator will immediately know if the deviating player is sending out-of-order messages, and this concept would reduce immediately to the regular communication equilibrium.

Perhaps in two-player games there is some interesting way to define untimed communication equilibrium (since the above issue does not arise---the mediator wouldn't know which player is out of order and which player is not), but this remains quite subtle and mostly outside the scope of the paper; we leave it to future work.

What is the next reasonable step beyond linear deviations in the search for swap regret minimization?

A very timely question! Two simultaneous very recent preprints [1, 2], both appearing after the ICLR submission deadline, have recently demonstrated that there exist efficient swap-regret minimizers for extensive-form games with regret $T \cdot \tilde O(\frac{\log d}{\log T})$, implying that it is possible to compute $\varepsilon$-NFCE in time $d^{\tilde O(1/\varepsilon)}$. (Note that this is in stark contrast with linear-swap regret, which can be minimized in $\text{poly}(d,1/\varepsilon)$ time instead of paying exponential cost in $1/\varepsilon$). A very natural open question remains as to whether it is possible to compute NFCE in time $\text{poly}(d, 1/\varepsilon)$.

[1] B Peng and A Rubinstein (arXiv 2023). "Fast swap regret minimization and applications to approximate correlated equilibria"

[2] Y Dagan, C Daskalakis, M Fishelson, and N Golowich (arXiv 2023). "From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces"

The main purpose of the example in Section 5 is precisely to clarify the relevant concepts, and we are glad that the reviewer found it helpful in understanding. We have added a forward pointer to the example in Section 3, as well as a schematic/table of the different solution concepts (Table 1).

Thank you for pointing out the typos; we have fixed them.

Could you provide some intuition why deviations in EFGs need to be defined as interactions between a mediator and a deviator?

It is not a requirement for a set of deviations to be defined as an interaction between mediator and deviator. Indeed, for example Farina and Pipis did not give this interpretation (and instead left the question open). From a game-theoretic modeling point of view, however, the question is important, as correlated equilibria and its variants---in fact all of them except linear-correlated equilibria before our paper---are defined in this way. This sort of mediator-deviator interaction is a very convenient framework for thinking about sets of deviations $\Phi$, and one important contribution of this paper is to place linear deviations also within the framework. The second important contribution of this paper is in showing that this improved understanding based in the language of mediators enables significant computational speedups. So, it is up to a reader and their background whether they are motivated more by the game-theoretic modeling or by the computational results; this paper contributes to both. (See also answer to Reviewer xFFq.)

There seem to be some typos in Theorem 2.3. On the second line, "where x^{(t)} \in X ... " Do you mean x^{(t)} \in \Phi instead of X? The utility vector u^{(t)} in this sentence also seems to come from nowhere.

The where clause is misplaced and should simply be removed. We have done this in the updated version.

And when you say "deterministic" external regret, the notion of deterministic seems undefined.

A deterministic regret minimizer is simply one that does not use randomness internally to compute its strategies. All regret minimizers we study in this paper are deterministic. We have clarified this in the updated version.

In order to further demonstrate the contribution of this work, the authors can have a table which records all existing algorithms for linear-swap regret, as well as their computational complexity. Right now it is a little bit hard for the readers to even identify which of the algorithms (UTC-based CFR or algorithms from Farina and Pipis) are better.

We know of only two algorithms for this problem---ours, and that of Farina and Pipis. As clearly stated at various points in the paper including the abstract, ours has significantly better per-iteration complexity in theory, and all-around better performance in practice.

If the reviewer is asking about comparisons between our algorithms and other $\Phi$-regret algorithms, we have included a table with such a comparison in Appendix B.

Why A and B are 'irrelevant' according to footnote 6?

That is because, at decision points A and B in the game, player $\blacktriangle$ is guaranteed utility exactly 0 regardless of what it does. Since a deviating player only cares to maximize its utility, what it does at these decision points is irrelevant.

The key point in the example is that the untimed nature of the deviations allows the deviating player to delay its query to the mediator until it reaches either infoset D or infoset E, and then decide which query to make based on which infoset was reached (A if D is reached, and B if E is reached). In a timed communication deviation, this behavior is impossible, because the player must make its first query (infoset A, B, or C) before reaching D or E, and thus that query cannot be conditioned on whether D or E will be reached.

We've updated the submission to add some more detail about this.

Following the above comment, I can not tell what is the key contribution of this work. [...] How the exactly can CFR be applied to linear deviation?

You are correct that the main theorem asserts that the set of deviations $\Phi_\text{Lin}$ (studied directly by Farina and Pipis) is equal to the set $\Phi_\text{UTC}$ that we introduce. This an important statement, for two different reasons:

• Mathematically, the structure of the constraints that define $\Phi_\text{UTC}$ expose a combinatorial structure that is significantly more amenable to computational techniques, namely, that of a DAG decision problem. The DAG structure of $\Phi_\text{UTC}$ is what enables the use of (a variant of) the CFR algorithm, which is extremely efficient---the cited paper Zhang et al (2023) gives more detail on the application of CFR to arbitrary DAGs. CFR could not be applied by Farina and Pipis, who instead are forced to use an algorithm whose stated (polynomial) complexity scales as the tenth power of the number of actions in the extensive-form game (see also answer below).
• Conceptually, $\Phi_\text{UTC}$ gives an interpretation of linear deviations in the language of correlation devices (aka mediators), which is the standard game-theoretic model underpinning correlated equilibrium and its variants. Farina and Pipis has left the question open, and instead studied the question from a learning-in-games angle.

A reduction process is expected, similar to what has been done in Theorem 2.3 (an existing result).

We use Theorem 2.3 (implicitly) as part of the proof of Theorem 6.1 (Theorem 2.3 is what allows us to say that an external regret minimizer on $\Phi_\text{Lin}$, which is what we have constructed, implies a $\Phi_\text{Lin}$-regret minimizer). We have clarified this in the updated verison.

Last, the authors suggested that the per-iteration complexity of CFR depends on the complexity of computing a fixed point iteration problem. How should we compare such a complexity with previous approaches, like Farina & Pipis (2023)?

Farina & Pipis's algorithm requires, on every iteration, (1) a fixed-point operation and (2) an $\ell_2$ projection onto the polytope. The latter step, though polynomial, is very expensive: in theory, it requires solving a convex quadratic program, and Farina & Pipis (Theorem D.1) bound the per-iteration complexity as $\tilde O(d^{10})$. By virtue of the identification of $\Phi_\text{Lin}$ and our $\Phi_\text{UTC}$, which presents a much more favorable structure of constraints, our paper shows that the projection can be removed altogether, and that fast approaches such as CFR can be used instead.

The complexity of computing the fixed point (needed by both Farina and Pipis, and by us) can in theory and in practice be computed far faster than this: theoretically, computing a fixed point can be done via a linear program in time $\tilde O(d^\omega)$, where $\omega \approx 2.37 < 10$. (see also response to Reviewer YUk3 for further discussion on the fixed point computation)

Practically, power iteration is usually sufficient to compute a fixed point and can be much faster than linear programming as well; that is what we use in the experiments (we have clarified this in the updated version)