Summary
This paper introduces a method, predictive treeplex Blackwell, for using Blackwell approachability directly on the treeplex in order to perform regret minimization in extensive-form strategy sets. They show that their algorithm achieves $O(\sqrt{T})$ regret (where $O$ hides polynomial factors in the game size), and a smoothed version of their algorithm enjoys $O(1/T)$ convergence toward Nash equilibrium when used by both players in zero-sum game.
Strengths
The method is conceptually very interesting, and shows that Blackwell-based stepsize-invariant regret minimizers are not solely restricted to the simplex. The experiments are comprehensive and illuminate clearly the authors' message about the role of infoset-level stepsize invariance. Thus, despite some minor issues listed below, I am generally in favor of acceptance.
Weaknesses
My most significant issue is simple: although the method is conceptually interesting, it is unclear if it carries any advantages over CFR (see also questions below re. clairvoyant CFR). For example, in theory, by Corollary 4.3 it seems that the convergence rate is something like $O(d^{5/2}/\sqrt{T})$ (since $\hat\Omega \le \sqrt{d}; \lVert \boldsymbol M \rVert_2 \le d$ -- maybe tighter analysis is possible but my point would stand regardless), compared to the $O(d/\sqrt{T})$ achieved by CFR-based methods. Similarly, the method seems consistently outperformed or matched by PCFR+ in basically every game, and the per-iteration complexity is inferior by a logarithmic factor.
Minor notes:
1. In Proposition 3.1, the regret of Algorithm 1 should be expressed in terms of the regret of the regret minimizer on $\mathcal C$. Also, technically, $\text{cone}(\mathcal T)$ is an infinite set, so by "regret of the regret minimizer on $\mathcal C$" I really mean "regret of the regret minimizer on $\mathcal C$ against vectors $\boldsymbol{\hat x} \in \mathcal T$". The proper regret bound holds for OMD/FTRL with gradient dynamics, but these details, I think, should be spelled out. See e.g. Proposition 2 and the discussion afterward in [12].
Questions
1. The paper claims that Smooth PTB+ is the first Blackwell-based $O(1/T)$-converging algorithm for EFGs. But doesn't the algorithm it is based on, namely the Clairvoyant CFR+ algorithm of [14], also achieve the same convergence rate? (see Appendix J of [14]).
1. It is interesting to me that RM+ does not coincide with TB+ when the domain is a simplex (Appendix E). What happens experimentally if you use (P)TB+ instead of (P)RM+ at every information set in CFR?
1. Is it possible to extend the fundamental ideas of this paper beyond treeplexes to other convex sets, to obtain more stepsize-invariant regret minimizers?