On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games

Thanks for your feedback!

Q1: “Is there some motivation in preferring a FOM rather than kernelization?”

A1: Given that FOMs have been extensively explored in the literature, they can benefit from the existing techniques. An example of this is the adoption of the COMD approach in our paper, which leads to a better theoretical convergence rate for learning CCE in extensive-form games. Also, FOMs are more flexible than kernelization, in general. With kernelization, one would be restricted to (variants of) the multiplicative weights update algorithm. In contrast, our DilEnt result can be applied to any first-order method that requires a strongly convex regularizer (including adaptive-stepsize methods, mirror prox, Nesterov’s excessive gap technique, etc., which do not have a kernelization equivalent). Furthermore, the analytic tools we introduce, including the treeplex norms, are likely of independent interest for first-order methods on extensive-form strategy sets and might apply to other regularizers as well.

Q2: “In the Clairvoyant OMD result, is the regret bound achieved by an efficient algorithm? Because clairvoyance requires solving a fixed-point problem, right?”

A2: Yes, COMD is indeed efficient. The fixed-point problem is solved via fixed-point iteration. By proving that the fixed-point iteration steps are contractions with respect to the treeplex norm (Lemma 4.5), the fixed-point subproblem is guaranteed to be solved at $\varepsilon$-approximation in logarithmic iterations in $1/\varepsilon$.

Q3: “Could the results obtained by either first-order methods with DilEnt or KOMWU hold for last-iterate convergence?”

A3: While this paper was not concerned with last-iterate convergence guarantees, by applying our new analysis framework to the result in [1], it should be straightforward to establish last-iterate convergence guarantees with a better dependency on game size in the settings for which [1] guarantees convergence.

Q4: “Regarding the lower bound of Theorem 5: is the result in the adversarial setting, where one player employs some algorithm and the other players decide "in the worst case" for the algorithm?”

A4: Yes, the result given by Theorem 5.1 is in the adversarial setting, which exactly matches the upper bound provided in Theorem 4.4. This is the standard online learning setting in which the usual lower bounds (for example, $\Omega(\sqrt{T \log n})$ for a probability simplex) are given. Lower bounds in the learning-in-games settings are widely unknown.

[1] Lee, Chung-Wei, Christian Kroer, and Haipeng Luo. "Last-iterate convergence in extensive-form games." Advances in Neural Information Processing Systems 34 (2021): 14293-14305.

Thanks for your feedback!

Q1: “The main takeaway message of the paper might be the lower bound, which establishes that the results of [2] cannot be improved by adopting the DGF approach. If this is the case, highlighting this point would greatly benefit the paper.”

A1: Thanks for the suggestions. In our opinion, however, the main takeaway of the paper is twofold. One is the lower bound, which suggests that KOMWU [2] is nearly optimal—as you said. The other, which we think is very important, is the analysis technique based on the treeplex norms. We believe that this contribution creates important analytical tooling that can be of independent interest for future research on regularization of these important combinatorial domains. As a byproduct, we are able to establish that the DilEnt regularizer achieves the near-optimal diameter-to-strong-convexity ratio for EFGs with full-information feedback. This also reconciles the more ad-hoc analysis based on kernelization (references [1,2] in your review) with the standard analysis of first-order methods and mirror descent, resolving the disconnect in the analysis.

Q2: “Regarding the improved rate for CCE through the use of Clairvoyant Mirror Descent, is the current result truly necessary to achieve this improvement?”

A2: This question is more speculative and it’s hard to know for sure. But, we are fairly confident that the new analytic tools we introduced, that are in line with the standard analysis of mirror descent-based algorithms, provide the natural groundwork for analyzing the algorithm. In particular, Clairvoyant MWU uses fixed-point iterations on a map that has to be shown to be contractive with respect to some norm. The treeplex norm is a very natural candidate for extensive-form games, as we show in the paper. It does not seem immediately straightforward to replicate these results for the kernelization approach.

[1] Bai, Yu, et al. "Efficient Phi-regret minimization in extensive-form games via online mirror descent." Advances in Neural Information Processing Systems 35 (2022): 22313-22325.

[2] Farina, Gabriele, et al. "Kernelized multiplicative weights for 0/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games." International Conference on Machine Learning. PMLR, 2022.

Thanks for your feedback!

Q: “Could you provide some hindsight on how are the treeplex, diameter-to-strong-convexity ratio of DilEnt used?”

A: The ratio between diameter and strong convexity of the regularizer on the feasible set (in the case of extensive-form games, the feasible set of every player is their sequence-form strategy polytope, also known as treeplex) is a key quantity in the performance of mirror descent-based algorithms. Intuitively, the performance degrades the more the diameter is large (as there is more “space” to search over), and increases the more the regularizer is bowl-shaped (i.e., strongly convex), as the minimum of the function becomes easier to predict. Of course, there is a tradeoff between these two parameters: if the regularizer is too strongly convex, then it grows really fast, making the diameter of the set $D_\varphi := \max_{x \in Q} D_\varphi(x \| x_1) = \max_{x \in Q} \varphi(x) - \min_{x \in Q} \varphi(x)$, larger.

Thanks for the suggestion, we will include this intuitive discussion in the revision.

Thanks for your feedback and your praise of our paper!

We address the two weaknesses you mentioned:

• Your claim that our paper does not deal with “partial information” is wrong. The techniques of the paper apply to imperfect-information extensive-form games. You are however right that the paper focuses on the case of perfect-recall games (i.e., players that do not forget their observations). This is a standard assumption. Equilibrium computation and learning in imperfect-recall games is known to be computationally intractable.

• Regarding empirical validation: you are right that we dedicated the entire paper on developing theoretical contributions. However, other work has examined the empirical performance of the DilEn regularizer (e.g., [1]), though without the theoretical understanding and machinery that we introduce in this paper to analyze its metric properties.

[1] Lee, Chung-Wei, Christian Kroer, and Haipeng Luo. "Last-iterate convergence in extensive-form games." Advances in Neural Information Processing Systems 34 (2021): 14293-14305.