Efficient Predictive Counterfactual Regret Minimization$^+$ Algorithm in Solving Extensive-Form Games

Some worries about the presentation of the theoretical part of the paper prevent me from recommending acceptance in the current state.

The paper makes the claim that it is the predictions that cause PCFR+ to be unstable and thus slow, but this seems hard to support theoretically. The fact that these algorithms are unstable is in some sense a necessary consequence of their scale-invariance, which has been observed to be a good property for fast algorithms (see e.g. [1]). So, it is strange to see this paper claiming that this instability is suddenly the source of bad performance. Moreover, it is unclear to me that the proposed method resolves this instability (by more than a small approximation): I think for any finite $\alpha$ it should be possible to derive some counterexample in which the strategy jumps from [1, 0] to [0, 1].

The claimed "theoretical improvement" entirely centers around improving the factor $2\sqrt{(2+\alpha)/(1+\alpha)}$ in Theorem 4.1, which is $\sqrt{8}$ for PCFR+ ($\alpha=0$) and $\sqrt{6}$ for $\alpha=1$. This is barely an improvement in theory, and to me does not justify the strong language used by the authors (e.g., "P2PCFR+ exhibits a faster theoretical convergence rate than PCFR+"). Moreover, I am not actually sure that it is an improvement, for example, Theorem 3 of Farina et al (2021) seems to recover the same bound as Theorem 4.1 except with a better constant of $\sqrt{2}$.

The last-iterate convergence of PCFR+ is not known in theory, but in practice it is often very strong, sometimes even better than the linear average. I would recommend that the authors evaluate the last-iterate performance of P2PCFR+ on practical examples as well.

The authors claim that, compared to other recent papers about PCFR+ (e.g., Smooth PCFR+), P2PCFR+ is parameter-free. But this is not true: there is a parameter $\alpha$ to tune! Perhaps more precise is to say that it remains scale-invariant? The practical improvement over PCFR+ is not that great, and I'm not sure it is enough to justify the additional complexity of introducing the hyperparameter $\alpha$.

Relatively minor issues:

• The example in Section 4.1 is impossible. In that example, we have $R^t_I = [2, 0]$, so $\sigma^t(I)= [1, 0]$. But then the instantaneous counterfactual regret $r^t_I$ must be of the form $[0, \cdot]$, not $[-1, 1]$ as in the paper. I think it is possible to get PCFR+ to go from $[1 ,0]$ to $[0, 1]$, but the construction is a bit tricker, e.g., I think you need to make $R^t_I = [0, 0]$.
• Why "P2PCFR+"? There are only two "P"s in "Pessimistic PCFR+", so shouldn't it be "P2CFR+" or "PPCFR+"?
• In Eq. (6) and Theorem 4.2, writing absolute constants such as $2$ and $(2+\alpha)/(1+\alpha)$ (which is bounded in $[3/2, 2]$ for $\alpha \in [0, 1]$) within a big-O is weird. Can you state those results without any big-Os?

[1] Darshan Chakrabarti, Julien Grand-Clément, Christian Kroer (NeurIPS 2024) "Extensive-Form Game Solving via Blackwell Approachability on Treeplexes"

The improvement shown theoretically is not very evident as it just improves a constant. Moreover, I have several concerns regarding the proof of Theorem 1. First of all, I think that the definition of the updates in equation 7 is not consistent with the updates given in the main text. In particular, the first equation just give $\mathbf{R}_t$ and not $\hat{\mathbf{R}_t}$. Then, when applying Lemma A.1 in Line 684 $x^{t+1}$ should be set equal to

$\hat{\mathbf{R}_{t+1}}$

and not to

$\mathbf{R}_{t+1}$.

All these imprecision makes the reading of the proof very difficult.

Moreover, I think that in the step leading to line 706 there is a mistake indeed taking $\alpha = 1$, we get on the right hand side an additional term equal to $\frac{1}{2\eta} (\mathcal{B}(\mathbf{R}^{t+1}, \hat{\mathbf{R}}^t) - \mathcal{B}(\hat{\mathbf{R}}^t, \mathbf{R}^{t+1})).$ The authors end up with the display at line 706 assuming that the above term is negative but why is this the case ?

• (Lines 300-303) The discrepancy $\left\Vert \sigma_i^{t+1}(I) - \sigma_i^t(I) \right\Vert$ is not guaranteed to decrease, since the term $\left\Vert \sigma_i^{t+1}(I) - \tilde{\sigma}_i^{t+1}(I) \right\Vert$ may increase.
• (Line 477) DCFR performs well on large-scale poker games such as HUNL subgames. The paper lacks experimental comparisons on these games.
• (Lines 431, 464) There is a gap between theory and experiments in the selection of the hyperparameter $\alpha$. The theorem states that the theoretical convergence rate improves with the increasing of $\alpha$, and therefore the paper deduces that P2PCFR+ converges faster than PCFR+. However, when $\alpha\rightarrow \infty$, the algorithm reduces to CFR+, which performs worse than PCFR+ in most games. Overall, the theory does not fully explain or guide the selection of $\alpha$, and the authors still rely on grid search to identify a suitable hyperparameter.”

While the idea is interesting, I am not convinced the contribution meets the threshold for publication, despite occasional superior empirical performance:

Unless I have misunderstood, the improvement in the theoretical convergence rate is in a multiplicative constant, it is misleading to say that the proposed algorithm has a better theoretical convergence rate than PCFR+, and in both cases, the range of the multiplicative constant as $\alpha$ is varied over the interval for which the respective theorems hold (as in Theorem 4.2 and Theorem 4.4) is quite small. Also, by using the language the authors use seems to imply that CFR+ has a "faster" theoretical convergence rate than PCFR+ at least when using the "convergence rates" that are worst-case/agnostic to the discrepancy between prediction and observation(perhaps this is a claim the authors would stand by, given their claim that CFR+ dominates PCFR+ empirically).

Given that the theoretical contributions seem minor, it seems to be perhaps the primary contribution is to provide a method with theoretical guarantees that generalizes PCFR+ with an appropriate choice of $\alpha$. While the experiments demonstrate that the proposed method sometimes significantly outperforms the algorithm (as noted above), the experiments should be run on games beyond Kuhn, Leduc, Liar's Dice and Goofspiel (e.g., it would have been better to show performance on a larger variety of different types of games and include for example Battleship and Pursuit-Evasion; it is noted in the original PCFR+ paper itself that the performance of PCFR+ is not as great on poker/poker-like games). Additionally, see the below question about averaging.