Efficient $\Phi$-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 19:34:40

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.

Main paper: 
  
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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. 
So, I suggest adding some simple applications to help readers to understand the learning protocol, for example, the tree-form decision problems.

Major comments:

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?
For theoretical analysis, is it finite-time analysis or asymptotic analysis?
I know it is a theory work, but is it any experiments?

Minor comments:

In Line 110, a comma is missing in $\{ \ \}$.

In Line 143, it is better to say $x[j]'s$.



In Line 271, it should be \citep{} for the citation.
strength_weakness: strength_weakness: see the first box
questions: questions: see the first box
limitations: limitations: I hope to see some experiments though
paper_summary: paper_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.

[1] Zhang et al. Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Extensive-Form Games. ICLR, 24.
strength_weakness: strength_weakness: 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. 

1.	The 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.
2.	Why 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.
3.	There 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.
4.	There 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.
5.	For 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.
6.	In 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.
7.	At 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)}$?
8.	In Line 228, what does it mean by “succinct representation”?
9.	For 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?
10.	In 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. 

Overall, 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.

[2] Bai et al. Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent. NeurIPS, 22.

[3] Farina et al. Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games. NeurIPS, 23.
questions: questions: Please see the weakness part above.
limitations: limitations: Not applicable.
paper_summary: paper_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.

The 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:

1. 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.


1. 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.
2. 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$.

3. 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.

4. 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.
strength_weakness: strength_weakness: - It seems the gap is bridged "from below", i.e., for large $k$ the results may become worse than known bounds.
- ~~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)
questions: 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?

Note: As a reader who is completely unfamiliar with the topic, the preliminaries could have covered a *deviations*.
limitations: limitations: /

Comments: comment: Thank you for the replies. Most of my concerns have been solved. I now believe the results of this work might be of interest to the community. However, as noted before, some parts of the presentation of this work are not clear enough and I believe it might need an in-depth revision in the future for better clarity. As such, I have marginally increased my score to 5.
Thank you for the response. Our algorithm is indeed deterministic. We never sample an action from $\pi^t$. The output of the learner is that distribution instead of a sample from it. This is similar to Hedge where the output is a distribution over actions, as opposed to EXP3 where the output is a sample from the distribution. Using deterministic algorithms is in line with much of the prior work on the subject; see, for example, [1,2,3] and references therein. Also, note that we operate in the full feedback model, and not under bandit feedback (see Lines 105-107 in our paper). In that setting, there are many well-known deterministic algorithms with sublinear regret, such as online gradient descent and Hedge, so the lower bound cited by the reviewer is not applicable.

We hope this clarifies the reviewer’s question, and we will highlight further in the revision that no randomization is used in our algorithm.

[1] Piliouras et al. Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update, NeurIPS 2022

[2] Daskalakis et al. Near-Optimal No-Regret Learning in General Games, NeurIPS 2021

[3] Syrgkanis et al. Faster Convergence of Regularized Learning in Games, NIPS 2015
Thanks for your responses. However, I am still not fully convinced by your responses to Q4 and Q5. Why is your algorithm deterministic? Since in each round, your algorithm will actually sample an action $x^t\sim \pi^t$, it can hardly be said that your algorithm is deterministic unless all the $\pi^t$'s are Dirac measures over the action space. Further, even if your algorithm is deterministic, why could you guarantee a sublinear regret result against the adversary? It is known that a deterministic algorithm can have linear regret against adversarial multi-armed bandits [4].

[4] Lattimore et al. Bandit Algorithms. 2020.
Thank you for the response and the clarifications! Based on your explanations and pointing out that I was at least partially confused about different types of strategies, I withdraw the second weakness. Given that my rating is an educated guess because of my lack of expertise, it affects my rating slightly positively, but in a way that's not mirrored by the rating scale.