Summary
The draft considers solving the extended-form game (EFG) with extrapolated block-coordinate descent methods, proving that it achieves O(1/T) convergence. The authors further show that with a restarting strategy, the proposed algorithm may be comparable sometimes to state-of-the-art algorithms like CFR+. In my understanding, the proposed algorithm is essentially a generalization of the CODER algorithm proposed by Song [37] in a way from coordinate descent (CD) to blockwise CD and specializes the domain to be linear functional and treeplex. I.e., the algorithm is essentially the same (line-by-line corresponded) as CODER but generalizes the scalar coordinate to blocks of "separable" variables. For the specialization, the authors focus on the context of EFG with bilinear score function and 2-player treeplex (linear probability simplex), where the prox is taken on L1-norm instead of the L2-norm by CODER. Implementation-wise, the proposed algorithm uses the recursive structure of the treeplex for efficient linear time computation.
Strengths
The major contribution of the draft is that it provides an instance to efficiently implement the CODER algorithm on EFG with blockwise L1 proximal and shows that with restarting, such implementation may be comparable with the state-of-the-art algorithm like CFR+. It also analyzes the scenario and provides an O(1/T) convergence rate without dependence on the number of variables. To summarize, the draft shows that a simple CODER extrapolation works well when taking L1 specialization on EFG.
Weaknesses
However, I would like to claim that the original CODER method may already cover the blockwise updates. I.e., if you look into the proof of CODER, it generally does not use the scalar property of the proximal and treats variables as blocks. They are using the $d$-dimension notation for simplicity and already claiming they are doing block CD in their abstract. In the EFG case, the d=2, so naturally (if the proximal works), the convergence complexity doesn't depend on the number of variables since blocks=2 is a constant. So the draft's theoretical result (independence on the number of variables) is not surprising. And the proposed method does not relax the "separability assumption" since the 2-player treeplex is separable as two blocks. The major difference/contribution here is that it performs the analysis on the L1 proximal and does the analysis.
Further, although it's good to see that the simple method works with restarting, the restarting part doesn't have theoretical support. I.e., without restarting, the theoretically supported method is not comparable to the state-of-the-art. And with restarting, the "full" method is comparable but not really much better than CFR+. Thus these factors put the paper in a borderline condition. However, the analysis seems solid, and I would give a borderline acceptance.
Questions
1. (Figure 2) Only doing the step-size optimization for your method and not the baseline is tricky for the experiment. For fairness, it should be either all constant step-size or all step-size tuned for the baseline. Otherwise, the reader cannot be sure whether the proposed method is better than MP.
2. (Figure 4) The vertical drop in the curves looks like either a numerical issue or a wrong optimal value.
3. (Algorithm 1) Adding parenthesis and denoting what you maintain in the computation may be good for clarity.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
Not applicable since the paper does not have a limitation section.