Summary
The paper studies regret minimization in extensive-form games (EFG). Specifically, they study a notion of regret called linear-swap regret, which measures the regret against linear transformations of the player's sequence-form strategies. This notion is stronger than trigger regret (as trigger deviations can be described as a linear transformation of sequence-form strategies) but weaker than swap regret.
The main technical contribution lies in Theorem 3.1, which states that the set of linear transformations (from the set of sequence-form strategies to itself) is a compact polytope defined by a polynomial (in the game tree size) number of linear constraints.
With that in hand, they leverage the template of Gordon et al. [2008] that produces a $\Phi$-regret minimization algorithm given a no-external-regret minimizer $\Phi$ and a fixed point oracle which returns fixed point of transformations in $\Phi$. In this context, the $\Phi$-regret minimization can be chosen, for example, to be Online Gradient Decent; and the fixed point oracle can be implemented using a Linear Programming Solver (e.g., Ellipsoid algorithm). This results in an efficient algorithm that achieves $\sqrt{T}$ linear-swap regret; which in turn also implies an efficient method for finding the correlated equilibrium that corresponds to linear transformations, that the authors call linear-deviation correlated equilibrium (LCE).
Finally, the authors provide examples to show that the set of LCEs strictly contain**s** the set of CEs, and is strictly contain**ed** in the set of Extensive-form correlated equilibrium (EFCE). They also show that the set of Behavioral correlated equilibrium (BCE) and the set of LCEs are incomparable.
Strengths
The paper is written well; the authors give great background on EFGs, on different notions of correlated equilibrium, and their relation to different notions of regret.
The construction of the algorithm and results are fairly easy to understand, and the authors express well the difference between their results and previous work by providing examples that compare their notion of equilibrium with existing notions.
Finally, I agree that determining *"what is the strongest notion of rationality that can be attained efficiently"* is an interesting open problem, and indeed the paper provide some progress in this direction.
Weaknesses
- There is no obvious algorithmic contribution here: As noted, Theorem 3.1 is the main technical contribution which is purely geometric. Given that, constructing the algorithm is fairly straightforward with the scheme of Gordon et al. [2008].
- While the background the paper gives is quite solid, it is not very proportional to the relatively small amount of attention the authors give to their technical contribution. In particular, while the statement of Theorem 3.1 is clear, it is not very intuitive, and it is hard to understand why it is correct. This is also the main reason that my confidence score is relatively low. I think that some of the preliminaries, as well as the empirical evaluations, could be deferred to the appendix - instead, I think that giving the main proof ideas is more important.
**Missing related work:** I think that the work of Anagnostides et al. (2022) is very relevant here and motivates important questions for future work. Specifically, this work achieves a much better rate of $\log T$ for trigger regret. Thus, it is fairly natural to ask whether this is also attainable for linear-swap regret, especially since they also built upon the template of Gordon et al. [2008].
Anagnostides, I., Farina, G., & Sandholm, T. (2022). Near-Optimal $\Phi $-Regret Learning in Extensive-Form Games. arXiv preprint arXiv:2208.09747.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.