Learning Imperfect Information Extensive-form Games with Last-iterate Convergence under Bandit Feedback

We thank the reviewer for the valuable comments and suggestions. Our response to each question is provided in turn below.

Q1. "Firstly, I do not fully understand why ... the sequence-form representation policies."

We would like to remark that we believe it might be possible to obtain a convergence result of the policy profile $(\mu^k,\nu^k)$ in episode $k$ computed by the algorithm using vanilla negentropy regularizer to the NE policy profile $(\mu^{k,\star},\nu^{k,\star})$ of the regularized game in the sense that $\left\|\mu^k-\mu^{k, \star}\right\|\_1$ and $\left\|\nu^k-\nu^{k, \star}\right\|\_1$ are bounded. However, even if this is possible, it is still unclear (at least to us) how to convert this convergence of the policy profile to the convergence of the final NE gap, which is our ultimate learning objective. We refer the reviewer to our discussions in our response to Q3 for details.

Q2. "Secondly, the authors claim that bounding the stability term of OMD with ... I find that no closed-form solution is provided."

Indeed, to our knowledge, bounding the stability term of OMD with Bregman divergence induced by the dilated negentropy regularizer depends on its closed-form update (please see our response to Q3 of Reviewer xgRk for more detailed explanations on this). Nevertheless, we would like to note that our OMD-type Algorithm 1 utilizes Bregman divergence induced by a virtual transition weighted negentropy regularizer, instead of the dilated negentropy regularizer. Hence, the fact that bounding the stability term of our algorithm does not rely on the closed-form solution to Eq. (3) (in our revised paper) does not conflict with the fact that bounding the stability term of OMD with the dilated negentropy regularizer relies on their closed-form update.

We will further clarify this point in the main body of the future version of our paper for better clarity.

Q8. "Could you offer a brief experimental analysis? For instance, discussing the convergence rate and runtime of the proposed algorithm in Kuhn Poker and Leduc Poker."

Thanks for this comment. We now provide the empirical evaluations on Lewis Signaling, Kuhn Poker, Leduc Poker, and Liars Dice game instances. Since we are not aware of any other algorithm that can also learn the (approximate) NE policy profile in IIEFGs with provable last-iterate convergence guarantees under bandit feedback, we compare our algorithm against previous algorithms that converge to the (approximate) NE policy profile in IIEFGs with only average-iterate convergence guarantees on these game instances. In experiments, to save the computation costs, we use a lazy update of our Algorithm 1, where only the policy of the experienced trajectory of infoset action pairs $\set{(x^k\_h,a^k\_h)}\_{h\in[H]}$ in each episode $k$ are updated. For the remaining infoset action pairs that are not experienced by the learner in episode $k$, the losses contributed by the entropy regularization (i.e., the second term in our constructed entropy regularized loss estimator) of these infoset action pairs will be accumulated and will be used to update these infoset action pairs once they are experienced in some future episode, coming from the observation that the losses contributed by the entropy regularization are much smaller than the importance-weighted losses constructed using the rewards in the game (i.e., the first term in our constructed entropy regularized loss estimator). In this way, the resulting computation complexity of our algorithm will only be of $\mathcal{O}(wXA+KXA)$ for running our algorithm in $K$ episodes where $w=\max\_{h\in[H],(x\_h,a\_h)\in\mathcal{X}\_h\times\mathcal{A}}|C(x\_h,a\_h)|$. Our algorithm obtains the fastest convergence rates on Kuhn Poker and Liars Dice and the comparable performance on Lewis Signaling and Leduc Poker against baseline algorithms. In contrast, we observe that some baseline algorithms perform relatively well in some instances but poorly in the remaining ones. The runtime of all the algorithms, including ours, is approximately $10$ hours, $12$ hours, $13$ hours, and $16$ hours for Lewis Signaling, Kuhn Poker, Leduc Poker, and Liars Dice, respectively. Please see Appendix G in the revised version of our paper for detailed discussions on the experimental results (highlighted in green).

We sincerely thank the reviewer again for the thoughtful feedback. We will also incorporate the additional discussions in our responses to Q1-Q6 into the main body of the future version of our paper.

[1] Kozuno et al. Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall. NeurIPS, 21.

[2] Bai et al. Near-Optimal Learning of Extensive-Form Games with Imperfect Information. ICML, 22.

Q5. "Could you explain the limitations of previous regularizers? It would be best if you could provide some simple examples."

The first regularizer that one might come up with is the dilated negentropy regularizer, which is commonly used in the analysis of establishing the average-iterate convergence results for learning IIEFGs [1,2]. The drawback of using such dilated negentropy regularizer is that it is highly unclear how to bound the stability term of the OMD with Bregman divergence induced by dilated negentropy regularizer when the closed-form update of OMD using dilated negentropy regularizer no longer holds (as mentioned in our response to Q3 of Reviewer xgRk). This is exactly our case where we need to constrain the update of OMD onto a subset $\Pi\_{\max }^{k}$ of the full space of the sequence-form representation of policies $\Pi\_{\max }$ (mainly due to the leverage of the entropy regularization). The other potential regularizer might be the vanilla negentropy regularizer. However, as mentioned in our response to Q1 and Q3, it is unclear (at least to us) whether it is possible to upper bound the final $\operatorname{NEGap}\left(\xi^k\right)$ as Pinsker’s inequality applies only to two probability measures and does not hold for two general sequence-form representation of policies $\mu\_1$ and $\mu\_2$ in IIEFGs.

Q6. "Could you elaborate on the contribution of your proposed regularizer to the convergence results of the algorithm?"

As we discussed in our response to Q3, the main benefit of our virtual transition weighted negentropy regularizer is that it facilitates the conversion from the convergence of the sequence-form representation of policy profiles to the final convergence of the NE gap via the leverage of the virtual transition. Moreover, we carefully design a virtual transition used in our virtual transition weighted negentropy regularizer, so that the minimum visitation probability contributed by the virtual transition $\min\_{h\in[H],x\_h\in\mathcal{X}\_h} p^x(x\_h)$ is well lower bounded, which is crucial to obtaining a sharp dependence on the infoset space size $X$ and $Y$ of the final convergence rate of the NE gap.

Q7. "Could you provide the computational complexity for solving Eq. (2)?"

Suppose there are $K$ episodes. Let $w=\max\_{h\in[H],(x\_h,a\_h)\in\mathcal{X}\_h\times\mathcal{A}}|C(x\_h,a\_h)|$, where $C(x\_h,a\_h)$ is the set of immediate descendant infosets of $(x\_h,a\_h)$ as defined in Section 3. Then the computation complexity of our Algorithm 2 and Algorithm 1 will be of $\mathcal{O}(wXA)$ and of $\mathcal{O}(wXA+K(XA+\operatorname{Oracle}))$, where $\operatorname{Oracle}$ denotes the computation complexity of an oracle algorithm to solve our Eq. (3) (in the revised version of our paper). If Algorithm 3 and Algorithm 4 are adopted to solve an approximate solution to Eq. (3) (in the revised version of our paper), then $\operatorname{Oracle}$ will be of $\mathcal{O}(wXAT)$ where $T$ is the number of iterations in Algorithm 3 and the total computation complexity of our Algorithm 1 will be of $\mathcal{O}(wXATK)$.

We have now incorporated the above discussion of the computation complexity of our algorithm in Appendix F of our revised paper for better clarity (highlighted in green).

Q3. "The benefits of the proposed regularizer are not clearly articulated. ..., such as its impact on proving the convergence results of the proposed algorithm."

On the positive side, the virtual transition weighted negentropy regularizer used in our Algorithm 1 mainly has the following advantages. First, with the leverage of such regularizer, as mentioned in Eq. (9) (in our revised paper), one is able to obtain an upper bound on $\operatorname{NEGap}$ by $\operatorname{NEGap}\left(\xi^k\right) \leqslant \operatorname{NEGap}\left(\xi^{k, \star}\right)+X\left\|p^x\left(\mu^k-\mu^{k, \star}\right)\right\|\_1+Y\left\|p^y\left(\nu^k-\nu^{k, \star}\right)\right\|\_1$, which involves the constructed virtual transition $p^x$ and $p^y$. Note that the upper bound $\left\|p^x\left(\mu^k-\mu^{k, \star}\right)\right\|\_1$ is tighter than $\left\|\mu^k-\mu^{k, \star}\right\|\_1$ because $p\_{1: h}^x\left(x\_h\right)\leq 1$ for all $x\_h\in\mathcal{X}$. More importantly, since $p\_{1: h}^x \cdot \mu\_{1: h}$ specifies a probability measure over infoset-action pairs as mentioned in Section 4.1, this enables us to further bound $\left\|p^x\left(\mu^k-\mu^{k, \star}\right)\right\|\_1$ by $\mathcal{O}\left(\sqrt{\mathrm{KL}\left(p^x \mu^{k, \star}, p^x \mu^k\right)}\right)$ via Pinsker’s inequality (which is not the case for the difference between the sequence-form representation of policies $\left\|\mu^k-\mu^{k, \star}\right\|\_1$). Second, also thanks to the leverage of the virtual transitions in our regularizer, $\mathrm{KL}\left(p^x \mu^{k, \star}, p^x \mu^k\right)=D\_\psi\left(\mu^{k, \star}, \mu^k\right)$ if $\psi(\mu)=\sum\_{h, x\_h, a\_h} p\_{1: h}^x\left(x\_h\right) \mu\_{1: h}\left(x\_h, a\_h\right) \log \left(p\_{1: h}^x\left(x\_h\right) \mu\_{1: h}\left(x\_h, a\_h\right)\right)$ is the virtual transition weighted negentropy regularizer as defined in Section 4.1. Note that $D\_\psi\left(\mu^{k, \star}, \mu^k\right)$ is an (approximate) contraction mapping guaranteed by our algorithm. Therefore, intuitively, leveraging the virtual transition weighted negentropy regularizer facilitates the conversion from the convergence to the NE profile $\xi^{k,\star}$ to the final convergence of the NE gap, which serves as a key step in obtaining the last-iterate convergence of the NE gap.

However, the potential downside of our virtual transition weighted negentropy regularizer is that the stability term of OMD is (approximately) enlarged by a factor inversely proportional to $\min\_{h\in[H],x\_h\in\mathcal{X}\_h} p^x(x\_h)$ as we discussed in Section 4.2 (please see Lemma B.1 in Appendix B of our revised paper). Moreover, the effect of $1/\min\_{h\in[H],x\_h\in\mathcal{X}\_h} p^x(x\_h)$ also appears in the analysis of bounding the contraction terms of the Bregman divergence (see, e.g., the proof of Lemma B.7 for bounding Term 4 in Appendix B.2 of our revised paper) and the analysis when establishing the final convergence upper bound of the NE gap (please refer to the proof of Theorem 5.1 in Appendix B.4 of our revised paper). These potential negative impacts of the virtual transition necessitate designing a good virtual transition such that $1/\min\_{h\in[H],x\_h\in\mathcal{X}\_h} p^x(x\_h)$ is well upper bounded. This is directly controlled by our Algorithm 2, which constructs a special virtual transition $p^x$ and guarantees that $1/\min\_{h\in[H],x\_h\in\mathcal{X}\_h} p^x(x\_h)\le X$ for this special virtual transition $p^x$ (please see Lemma A.1 in our revised paper). This eventually guarantees a sharp dependence on the infoset space size $X$ of the final last-iterate convergence rate.

Q4. "The convergence results presented in the paper seem to rely on the exact solvability of Eq. (2). However, Eq. (2) only yields an approximate solution."

Please refer to our response to Q2.

Regarding your response to Q1, I respectfully disagree. Your statement holds true if the strategy space is not $\Pi_{max}$. However, since $\Pi_{max}$ is indeed under consideration, this can be formally proven. The existence of lower bounds for both $\log u$ and $\log v$ ensures the smoothness of the KL divergence.

I also disagree with your response to Q3. If an algorithm is not implementable, it holds no practical value. This perspective might conflict with the views of certain researchers, but ultimately, algorithms are meant to be applied to solve real-world problems.

I notice that your statement seems to suggest that $\Vert \Vert^2_1 \leq KL()$ cannot be proven. However, this is essentially the definition of strong convexity, and I do not see any difficulty in this regard.

We thank the reviewer for the valuable comments and suggestions. Our response to each question is provided in turn below.

Q1. "What is the computational cost required in Algorithms 1 and 2?"

Suppose there are $K$ episodes. Let $w=\max_{h\in[H],(x_h,a_h)\in\mathcal{X}_h\times\mathcal{A}}|C(x_h,a_h)|$, where $C(x_h,a_h)$ is the set of immediate descendant infosets of $(x_h,a_h)$ as defined in Section 3. Then the computation complexity of our Algorithm 2 and Algorithm 1 will be of $\mathcal{O}(wXA)$ and of $\mathcal{O}(wXA+K(XA+\operatorname{Oracle}))$, where $\operatorname{Oracle}$ denotes the computation complexity of an oracle algorithm to solve our Eq. (3) (in the revised version of our paper). If Algorithm 3 and Algorithm 4 are adopted to solve an approximate solution to Eq. (3) (in the revised version of our paper), then $\operatorname{Oracle}$ will be of $\mathcal{O}(wXAT)$ where $T$ is the number of iterations in Algorithm 3 and the total computation complexity of our Algorithm 1 will be of $\mathcal{O}(wXATK)$.

We have now incorporated the above discussion of the computation complexity of our algorithm in Appendix F of our revised paper for better clarity (highlighted in green).

Q2. "My main concern is the lack of experiments to support the theoretical results. ... in practical game scenarios.""Is there any other method that can solve the game described in this paper? If so, how does the empirical performance compare?"

We would like to point out that we believe the main contribution of our work lies in devising the first algorithm for learning the (approximate) NE policy profile in IIEFGs with provable last-iterate convergence guarantees under bandit feedback. As mentioned in our paper, to the best of our knowledge, we are not aware of any other algorithm with similar theoretical guarantees in the same setting. Therefore, we compare our algorithm against previous algorithms that converge to the (approximate) NE policy profile in IIEFGs with only average-iterate convergence guarantees on Lewis Signaling, Kuhn Poker, Leduc Poker, and Liars Dice game instances. Our algorithm obtains the fastest convergence rates on Kuhn Poker and Liars Dice and the comparable performance on Lewis Signaling and Leduc Poker against baseline algorithms. In contrast, we observe that some baseline algorithms perform relatively well in some instances but poorly in the remaining ones. Please see Appendix G in the revised version of our paper for more detailed discussions on the experimental results (highlighted in green).

Q3. Typo.

Thanks for pointing this out. We have now corrected this typo in the revised version of our paper.

We thank the reviewer for the valuable comments and suggestions. Our response to each question is provided in turn below.

Q1. "Although the theoretical side of this paper is strong, simulation parts are completely missing ... validate the last-iterate convergence and potentially the rate of convergence."

Thanks for this comment. We now provide the empirical evaluations on Lewis Signaling, Kuhn Poker, Leduc Poker, and Liars Dice game instances. Since we are not aware of any other algorithm that can also learn the (approximate) NE policy profile in IIEFGs with provable last-iterate convergence guarantees under bandit feedback, we compare our algorithm against previous algorithms that converge to the (approximate) NE policy profile in IIEFGs with only average-iterate convergence guarantees on these game instances. Our algorithm obtains the fastest last-iterate convergence rates on Kuhn Poker and Liars Dice and the comparable performance on Lewis Signaling and Leduc Poker against baseline algorithms. In contrast, we observe that some baseline algorithms perform relatively well in some instances but poorly in the remaining ones. Please see Appendix G in the revised version of our paper for more detailed discussions on the experimental results (highlighted in green).

Q2. "why do you choose subset $\Pi_{\max}^{k+1}$ such that $\mu\left(a_h \mid x_h\right) \geqslant \frac{1}{A(k+1)}$, and why constraining this feasible set won't affect the convergence?"

We consider constraining the optimization of OMD onto a subset $\Pi_{\max}^{k}$ of the full space of the sequence-form representation of policies $\Pi_{\max}$ mainly to prevent the second term in the constructed entropy regularized loss estimator from being prohibitively large (Line 6 of our Algorithm 1). Intuitively, there is a trade-off on the choice of the value of the lower bound of $\mu\left(a_h \mid x_h\right)$. If $\min_{a_h\in\mathcal{A}}\mu\left(a_h \mid x_h\right)$ is too small, then the NE gap contributed by using the entropy regularization will be prohibitively large and it is required to control the lower bound of $\min_{a_h\in\mathcal{A}}\mu\left(a_h \mid x_h\right)$ in, for example, our Lemma B.3 and Lemma B.12 (in the revised version of our paper). However, if $\min_{a_h\in\mathcal{A}}\mu\left(a_h \mid x_h\right)$ is too large (i.e., $\Pi_{\max}^{k}$ is too "small"), the unique NE policy profile $\xi^{k, \star}=\left(\mu^{k, \star}, \nu^{k, \star}\right)$ in the regularized game $f_k$ might be too far from the NE policy profile $\xi^\star$ of the original game $f$, as noticed by the reviewer. This intuition is formalized in our Lemma B.2 (in our revised version), where the second term in Eq. (11) of Lemma B.2 is directly proportional to $\min_{a_h\in\mathcal{A}}\mu\left(a_h \mid x_h\right)$ and will be $0$ if $\Pi_{\max}^{k}=\Pi_{\max}$ (i.e., $\min_{a_h\in\mathcal{A}}\mu\left(a_h \mid x_h\right)=0$). More specifically, choosing the constrained set $\Pi_{\max}^{k}$ such that $\mu\left(a_h \mid x_h\right)\geq \frac{1}{Ak^c}$ with $c\geq 1$ as some universal constant that is independent of all the parameters $X, Y, A, B, H$ of the problem will only make the convergence rate of our algorithm worse by a multiplicative constant $c$ and can be suppressed in big O notation. Therefore, we eventually choose our constraint set $\Pi_{\max}^{k}$ such that $\mu\left(a_h \mid x_h\right)\geq \frac{1}{Ak}$. Additionally, the factor of $A$ in the denominator of this constraint is to ensure that the constraint set $\Pi_{\max}^{k}$ is well-defined when $k=1$.

Q3. "It is stated that employing the virtual transition helps to ... Can the authors discuss more on this? And why operating OMD in the space of visitation measure is important?"

Indeed, the constructed virtual transition is utilized in our Algorithm 1 in its sequence-form representation. However, note that the construction of the sequence-form representation of the virtual transition is independent of any policy. Moreover, our algorithm is able to implicitly operate the update of OMD in the space of probability measures over infoset-action pairs precisely because $\left[p\_{1: h}^x \cdot \mu\_{1: h}\right]\left(\cdot, \cdot\right)$, where $\left[p\_{1: h}^x \cdot \mu\_{1: h}\right]\left(x\_h, a\_h\right)=p\_{1: h}^x\left(x\_h\right) \mu\_{1: h}\left(x\_h, a\_h\right)= p\_0^x\left(x\_1\right) \prod\_{h^{\prime}=1}^{h-1} p\_{h^{\prime}}^x\left(x\_{h^{\prime}+1} \mid x\_{h^{\prime}}, a\_{h^{\prime}}\right)\mu(a\_{h^{\prime}}\mid x\_{h^{\prime}})\cdot\mu(a\_{h}\mid x\_{h})$, is a probability measure over infoset-action space $\mathcal{X}\_h\times\mathcal{A}$ for all $h\in[H]$.

Moreover, leveraging the virtual transition weighted negentropy and thus implicitly operating the update of OMD in the space of probability measures over infoset-action pairs is important mainly due to the following reasons. First, in this way, as mentioned in Eq. (9) (in the revised version of our paper), one is able to obtain an upper bound on $\operatorname{NEGap}$ by $\operatorname{NEGap}\left(\xi^k\right) \leqslant \operatorname{NEGap}\left(\xi^{k, \star}\right)+X\left\|p^x\left(\mu^k-\mu^{k, \star}\right)\right\|\_1+Y\left\|p^y\left(\nu^k-\nu^{k, \star}\right)\right\|\_1$, which involves the constructed virtual transition $p^x$ and $p^y$. Note that the upper bound $\left\|p^x\left(\mu^k-\mu^{k, \star}\right)\right\|\_1$ is tighter than $\left\|\mu^k-\mu^{k, \star}\right\|\_1$ because $p\_{1: h}^x\left(x\_h\right)\leq 1$ for all $x\_h\in\mathcal{X}$. More importantly, since $p\_{1: h}^x \cdot \mu\_{1: h}$ specifies a probability measure over infoset-action pairs as mentioned above (and in Section 4.1), this enables us to further bound $\left\|p^x\left(\mu^k-\mu^{k, \star}\right)\right\|\_1$ by $\mathcal{O}\left(\sqrt{\mathrm{KL}\left(p^x \mu^{k, \star}, p^x \mu^k\right)}\right)$ via Pinsker’s inequality (which is not the case for the difference between the sequence-form representation of policies $\left\|\mu^k-\mu^{k, \star}\right\|\_1$). Second, also thanks to the leverage of the virtual transitions, $\mathrm{KL}\left(p^x \mu^{k, \star}, p^x \mu^k\right)=D\_\psi\left(\mu^{k, \star}, \mu^k\right)$ if $\psi(\mu)=\sum\_{h, x\_h, a\_h} p\_{1: h}^x\left(x\_h\right) \mu\_{1: h}\left(x\_h, a_h\right) \log \left(p\_{1: h}^x\left(x\_h\right) \mu\_{1: h}\left(x\_h, a\_h\right)\right)$ is the virtual transition weighted negentropy regularizer as defined in Section 4.1. Notice that $D\_\psi\left(\mu^{k, \star}, \mu^k\right)$ is an (approximate) contraction mapping guaranteed by our algorithm. Therefore, intuitively, operating the update of OMD in the space of probability measures over infoset-action pairs eventually facilitates the conversion from the convergence to the NE policy profile $\xi^{k,\star}$ to the final convergence of the NE gap, which is our ultimate learning objective.

Q4. "It seems that the virtual transition is fixed at the beginning (once the game tree is fixed), ... to further improve the convergence rate?"

Thanks for this comment. Currently, our virtual transition is constructed at the very beginning of the game because in our setting the game tree structure of the IIEFG instance is fixed and known (note that terminology of "bandit feedback" in our current work indicates that the reward functions $r$ and the transition probabilities over the underlying state space instead of the game tree structure are unknown). In cases where the game tree structures are unknown, we believe utilizing the historical information of the experienced infoset-actions to construct an importance-weighted virtual transition estimator is a promising approach, as the reviewer has pointed out. We leave this interesting extension as our future direction.

Thanks for the detailed feedback. I may have to take a more careful look at the calculation later. But in your response for Q3 you mentioned several issues like whether $\tilde{\mu}^{k+1}\leq \mu^k$. Shouldn't these also the case in the analysis for non-clipped policy space (like in Kozuno et al)? They should have dealt with this, right?

But actually, my original suggestion is simpler than that in your response. As in your response, we have

$\text{Stability} \leq \sum_k \left( \langle \mu^k - \mu^{k+1},\hat{\ell}^k \rangle - \frac{1}{\eta} D_\psi(\mu^{k+1}, \mu^k)\right)$

$= \sum_k \max_{\mu\in \Pi_{max}^{k+1}} \left( \langle \mu^k - \mu,\hat{\ell}^k \rangle - \frac{1}{\eta} D_\psi(\mu, \mu^k)\right)$
// You can also use "$\leq$" in this line, but it's actually an equality based on Eq.(3) in the paper

$\leq \sum_k \max_{\mu\in \Pi_{max}} \left( \langle \mu^k - \mu,\hat{\ell}^k \rangle - \frac{1}{\eta} D_\psi(\mu, \mu^k)\right)$

Then in the last line, the max solution for $\mu$ is the "$\mu^{k+1}$ in the non-clipped policy space $\Pi_{max}$". Then you can use the closed form solution to bound this stability term?

Q3. "Why is bounding the stability of dilated negentropy critically relies on its closed form? This is not the case for general OMD." (Cont.)

Fortunately, when the feasible set is the full $\Pi_{\max}$, it has been observed that the stability term of OMD with dilated negentropy regularizer can be bounded by

in contrast to the general bound of $\frac{1}{\eta}\sum_{k=1}^t D\_{\psi}\left(\mu^k, \widetilde{\mu}^{k+1}\right)$ in $(\*\*)$. Notice that this is slightly tighter than $\frac{1}{\eta}\sum\_{k=1}^t D_{\psi}\left(\mu^k, \widetilde{\mu}^{k+1}\right)$ as ${\mu}^{k+1}$ is the Bregman projection of $\widetilde{\mu}^{k+1}$ onto $\Pi\_{\max}$ and $D\_{\psi}\left(\mu^k, {\mu}^{k+1}\right)+D\_{\psi}\left( {\mu}^{k+1},\widetilde{\mu}^{k+1}\right)\le D\_{\psi}\left(\mu^k, \widetilde{\mu}^{k+1}\right)$ (see, e.g., Lemma 8 in [2]). And $(\*\*\*)$ can be eventually upper bounded as $\sum\_{k=1}^t\sum\_{h=1}^H\mu^k\_{1:h}(x^k\_h,a^k\_h)\widehat{\ell}^k\_h(x^k\_h,a^k\_h)^2$ [2]. However, we note that obtaining the upper bound of the stability term in $(\*\*\*)$ relies on the closed-form update of $\mu^{k+1}$ when the feasible set is the full $\Pi\_{\max}$ and we believe this closed-form update of $\mu^{k+1}$ no longer holds in our case where we need to constrain the feasible set to a subset $\Pi\_{\max}^{k}\subset \Pi\_{\max}$. Therefore, it is unclear (at least to us) whether the stability term of OMD with dilated negentropy regularizer can still be upper bounded by $(***)$ in our case.

Q4. "Stability term is related to ... So why not the stability term in \Pi_max smaller than that in the entire space, and existing analysis suffices?"

Yes, we fully agree that the stability term of OMD/FTRL actually evaluates how much the iterate moves between rounds. However, as aforementioned, when $\psi$ is the dilated negentropy regularizer, the stability term in our constrained case can indeed be upper bounded by $\frac{1}{\eta}\sum_{k=1}^t D_{\psi}\left(\mu^k, \widetilde{\mu}^{k+1}\right)$, as in the case where the feasible set is the full space of sequence-form representation of policies $\Pi_{\max}$. Nevertheless, this seems difficult (at least for us) to further upper bound it as illustrated above. On the other hand, we believe the closed-form update of $\mu^{k+1}$ in our constrained case no longer holds, thus it is also unclear whether the stability term in our case can be upper bounded by $\frac{1}{\eta}\sum_{k=1}^t D_{\psi}\left(\mu^k, {\mu}^{k+1}\right)$. If there is truly a way to upper bound the stability term in our case by $\frac{1}{\eta}\sum_{k=1}^t D_{\psi}\left(\mu^k, {\mu}^{k+1}\right)$, we believe previous analysis will suffice since $D_{\psi}\left(\mu^k, {\mu}^{k+1}\right)\le D_{\psi}\left(\mu^k, \widehat{\mu}^{k+1}\right)$ (let $\widehat{\mu}^{k+1}=\arg\min_{\mu\in\Pi_{\max}}D_{\psi}(\mu,\widetilde{\mu}^{k+1})$ be the Bregman projection of $\widetilde{\mu}^{k+1}$ onto the full $\Pi_{\max}$) and $D_{\psi}\left(\mu^k, \widehat{\mu}^{k+1}\right)$ can be upper bounded by $\sum_{k=1}^t\sum_{h=1}^H\mu^k_{1:h}(x^k_h,a^k_h)\widehat{\ell}^k_h(x^k_h,a^k_h)^2$ as discussed above. Therefore, as it is unclear whether the stability term in our case can be upper bounded by $\frac{1}{\eta}\sum_{k=1}^t D_{\psi}\left(\mu^k, {\mu}^{k+1}\right)$, it seems not feasible to compare the stability term in our case with that in the case where the feasible set is the full $\Pi_{\max}$ and leverage existing analysis.

We would like to thank the reviewer once again for the insightful feedback. We will also incorporate the discussions in our responses to Q3 and Q4 into the main body of the future version of our paper for better clarity.

[1] Lattimore et al. Bandit Algorithms. 2020.

[2] Kozuno et al. Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall. NeurIPS, 21.

Q3. "Why is bounding the stability of dilated negentropy critically relies on its closed form? This is not the case for general OMD."

Indeed, in general, for OMD with Bregman divergence induced by any regularizer $\psi$, one can always bound the stability term as follows (consider the time-invariant learning rate $\eta$ for simplicity) [1]:

where $\widetilde{\mu}\_{k+1}=\operatorname{argmin}\_{\mu \in\mathbb{R}^{A}\_{\ge 0}} \eta\left\langle \mu, \widehat{\ell}^k\right\rangle+D\_{\psi}\left(\mu, \mu^k\right)$. To further bound the above display, a typical method to consider using Young-Fenchel inequality and Taylor’s theorem to upper bound $(\*)$ and $(\*\*)$ as local norms:

where $z^k=\alpha\mu^{k+1}+(1-\alpha)\mu^k$ and $\widetilde{z}^k=\beta\widetilde{\mu}^{k+1}+(1-\beta)\mu^k$ for some $\alpha,\beta\in(0,1)$. When $\psi$ is chosen as a common regularizer such as negentropy, $\alpha$-Tsallis entropy or log-barrier regularizer, it usually happens that $\widetilde{\mu}^{k+1}(a)\lesssim\mu^k(a)$ and we can obtain an explicit form of the inverse of the Hessian $\nabla^{-2}\psi(\cdot)$ as the Hessian $\nabla^{2}\psi$ is usually a diagonal matrix. Therefore, even when we constrain the optimization of OMD/FTRL onto a smaller subset of the probability simplex and $\mu^{k+1}$ does not admit a closed-form update, we can still bound the stability term by $O(\eta\sum\_{k=1}^t\sum\_{a\in\mathcal{A}}\widehat{\ell}^k(a)^2\mu^k(a)^\alpha)$ ($\alpha=1$ for negentropy, $\alpha=2$ for log-barrier and $\alpha\in(0,1)$ for general $\alpha$-Tsallis entropy).

However, when it comes to the case of using the dilated negentropy regularizer in IIEFGs, the situation becomes more complicated. Recall the dilated negentropy is defined as $\psi(\mu)=\sum\_{h, x\_h, a\_h} \mu\_{1: h}\left(x\_h, a\_h\right) \log \left(\frac{\mu\_{1: h}\left(x\_h, a\_h\right)}{\mu\_{1: h}\left(x\_h\right)}\right)$. For any $\mu\in\mathbb{R}^{XA}\_{> 0}$, $\mu\_{1: h}\left(x\_h\right)$ can be regarded as either $\mu\_{1: h+1}\left(x\_{h+1}\right)=\mu\_{1:h}(x\_h,a\_h)$ (here $(x\_h,a\_h)$ is such that $x\_{h+1}\in C(x\_h,a\_h)$) or $\mu\_{1: h}\left(x\_{h}\right)=\sum\_{a\_h\in\mathcal{A}}\mu\_{1:h}(x\_h,a\_h)$. Note that if these two conditions simultaneously hold, then $\mu\in\Pi\_{\max}$ is a valid sequence-form representation of policy. If we constrain the optimization of OMD onto the subset $\Pi\_{\max}^{k}\subset \Pi\_{\max}$, we can still bound the stability term as $O(\sum\_{k=1}^t \eta\|\widehat{\ell}^k\|\_{\nabla^{-2}\psi(\widetilde{z}^k)}^2)$. However, it is highly unclear (at least to us) how to further bound this local norm for two reasons.

• First, $\eta\widehat{\ell}^k+\nabla \psi(\widetilde{\mu}^{k+1})-\nabla \psi({\mu}^{k})=0$ still holds, but it is unclear whether $\widetilde{\mu}^{k+1}\_{1:h}(x\_h,a\_h)\lesssim\mu^k\_{1:h}(x\_h,a\_h)$ still holds. If we regard $\mu\_{1: h+1}\left(x\_{h+1}\right)=\mu\_{1:h}(x\_h,a\_h)$ in dilated negentropy, the gradient will be such that

​If we regard $\mu\_{1: h}\left(x\_{h}\right)=\sum\_{a\_h\in\mathcal{A}}\mu\_{1:h}(x\_h,a\_h)$ in dilated negentropy, the gradient will be such that

In either way, different $\mu\_{1:h}(x\_h,a\_h)$'s are coupled with each other, and thus it is unclear whether $\widetilde{\mu}^{k+1}\_{1:h}(x\_h,a\_h)\lesssim\mu^k\_{1:h}(x\_h,a\_h)$ still holds.

• Further, even if it can be shown that $\widetilde{\mu}^{k+1}\_{1:h}(x\_h,a\_h)\lesssim\mu^k\_{1:h}(x\_h,a\_h)$, the Hessian $\nabla^{2}\psi$ is non-diagnoal regardless whether we regard $\mu\_{1: h+1}\left(x\_{h+1}\right)=\mu\_{1:h}(x\_h,a\_h)$ or $\mu\_{1: h}\left(x\_{h}\right)=\sum\_{a\_h\in\mathcal{A}}\mu\_{1:h}(x\_h,a\_h)$. As such, it is unclear how to obtain the explicit form (or at least an upper bound) of the inverse of the Hessian $\nabla^{-2}\psi(\cdot)$. Therefore, it is unclear how to evaluate and upper bound this local norm.

We thank the reviewer for the valuable comments and suggestions. Our response to each question is provided in turn below.

Q1. "though the virtual transition seems to be the main innovation of this paper, I am not sure whether it is indeed needed (see related questions in the Questions section).";"Does the algorithm still work if replacing the p^x(x_h) in Line 278 simply by 1/X ... If not, can you point out where the analysis might break?"

We now provide further explanations on why we need the proposed virtual transition as well as an illustrative example, the figure of which is shown in Appendix A.1 in the revision of our paper. For ease of discussion, there is only one action $a$ and $H=4$ in this example. Each infoset $x$ in the game tree of this example satisfies $|C(x,a)|=2$ except for infoset $x\_{2,1}$, which is such that $|C(x\_{2,1},a)|=n$ with some $n\geq 2$. Now suppose we use the uniform distribution $p$ as a virtual transition over infoset-action spaces. Then for all the descendants $\set{x\_{4,i}}\_{i=1}^{2n}$ on step $h=4$ of infoset $x\_{2,1}$, one can see that $p\_{1:H}(x\_{H,i})=\frac{1}{2} \cdot \frac{1}{n} \cdot \frac{1}{2}=\frac{1}{4n}$, while there are only $X=9+3n$ infosets in total. As such, it will happen that $p\_{1:H}(x\_{H,i})< \frac{1}{X}$ when $n> 9$. Actually, one can easily construct an IIEFG instance such that $\min_{x\_H\in\mathcal{X}\_H}p\_{1:H}(x\_{H})\leq \mathcal{O}(\frac{1}{n^m})$ and $X=\mathcal{O}(mn+c)$ with $c$ as a parameter that depends on $m$ but not $n$ for uniform virtual transition $p$. Therefore, when using uniform distribution $p$ as a virtual transition, $\max\_{x\_H\in\mathcal{X}\_H} 1/p\_{1:H}(x\_{H})$ might be prohibitively large and lead to a convergence rate with much worse dependence on $X$ than the virtual transition constructed in our Algorithm 2. This is the reason why we do not simply choose the uniform transition as the virtual transition in our algorithm and analysis.

Q2. "Can you explain why 1/X * 1/p^x_{1:h}(x_h) <= 1 (claimed in the last line of Page 23)?"

This question is directly related to the last one. This is due to that our constructed virtual transition $p^x$ satisfies $\min\_{x\_h\in\mathcal{X}\_h,h\in[H]}p^x\_{1:h}(x\_h)\ge \frac{1}{X}$, guaranteed by the following lemma.

Lemma. For any $h\in[H]$ and $x\_h\in\mathcal{X}\_h$, the constructed virtual transition $p^x$ guarantees that $1/p^x\_{1:h}(x_h)\leq X$.

Proof. Clearly, $p^x\_{1:h}(\cdot)$ is minimized at $h=H$ for some $x\_H\in\mathcal{X}\_H$ by the definition of the sequence-form representation of virtual transition. By the construction of $p^x\_{1:h}(\cdot)$ in Algorithm 2, one can deduce that $\forall x\_H\in\mathcal{X}\_H$, it holds that (understanding $\set{(x\_h,a\_h)}\_{h\in[H-1]}$ as the unique trajectory leading to $x_H$ below)

where $c[\cdot]$, $q[\cdot]$, and $d[\cdot,\cdot]$ are defined in our Algorithm 2; and $(i)$ is due to $c[x\_{H-1}]=\max\_{a\in\mathcal{A}} d[x\_{H-1},a]\geq d[x\_{H-1},a\_{H-1}]$.

Q.E.D.

This property of our constructed virtual transition $p^x$ serves as a key ingredient in the analysis (e.g., when bounding our Term 4 as noticed by the reviewer and when establishing the final convergence upper bound of the NE gap in the proof of Theorem 5.1 in our Appendix B.4) and we have now incorporated this lemma together with the discussions above into Appendix A of our revised paper for better clarity (highlighted in green).

First, the analysis in [1] should be able to bound $D_\psi(\mu^k, \hat{\mu}^{k+1})$ in your case. If you read their Lemma 7 and the part in Lemma 6 that bounds $D_\psi(\mu^k, \hat{\mu}^{k+1})$ carefully, you can find that they hold for any $\mu^k\in\Pi_{\max}$. The only requirement is that $\hat{\mu}^{k+1}$ is one-step update from $\mu^k$, that is, $\hat{\mu}^{k+1}=\text{arg} \min_{\mu\in\Pi_{\max}} \left(\eta \langle \mu,\hat{\ell}^k \rangle + D_\psi(\mu, \mu^k)\right)$.

Below, I continue my previous calculation to show that the stability term is upper bounded by $\frac{1}{\eta}D_\psi(\mu^k ,\hat{\mu}^{k+1})$. The calculation below are essentially the same as in [1] for the $\Pi_{\max}$ space.

$\text{Stability} \leq \sum_k \max_{\mu\in \Pi_{max}} \left( \langle \mu^k - \mu,\hat{\ell}^k \rangle - \frac{1}{\eta} D_\psi(\mu, \mu^k)\right)$

$= \sum_k \left( \langle \mu^k - \hat{\mu}^{k+1},\hat{\ell}^k \rangle - \frac{1}{\eta} D_\psi(\hat{\mu}^{k+1}, \mu^k)\right)$.

Next, we show that the right-hand side above is equal to $\sum_k \frac{1}{\eta} D_\psi(\mu^k, \hat{\mu}^{k+1})$. This is shown below:

$D_\psi(\mu^k ,\hat{\mu}^{k+1}) + D_\psi(\hat{\mu}^{k+1}, \mu^k)$

$=\sum_{h}\sum_{x_h,a_h} (\mu_{1:h}^k(x_h,a_h) - \hat{\mu}^{k+1}_{1:h}(x_h, a_h)) \log \frac{\mu_h^{k}(a_h | x_h) } {\hat{\mu}^{k+1}_h(a_h|x_h) }$

$=\sum_{h}\sum_{x_h,a_h} (\mu_{1:h}^k(x_h,a_h) - \hat{\mu}^{k+1}_{1:h}(x_h, a_h))$ $\left( \mathbf{1} _{(x_h, a_h)=(x_h^k, a_h^k)}\left(\eta \hat{\ell}^k(x_h,a_h) - \log Z^k _{h+1}\right)+ \mathbf{1} _{x_h=x_h^k}\left(\log Z^k_h\right) \right)\ \ \$ // By Eq.(7) in [1]

$=\eta \langle \mu^k - \hat{\mu}^{k+1}, \hat{\ell}^k \rangle - \sum_{h=1}^H \left(\mu_{1:h}^k(x_h^k,a_h^k) - \hat{\mu}^{k+1}_{1:h}(x_h^k, a_h^k)\right)\log Z^k _{h+1}$ $+ \sum _{h=1}^H \left(\mu _{1:h}^k(x_h^k) - \hat{\mu}^{k+1} _{1:h}(x _h^k)\right)\log Z^k _{h}$

$=\eta \langle \mu^k - \hat{\mu}^{k+1}, \hat{\ell}^k \rangle - \sum_{h=2}^H \left(\mu_{1:h}^k(x_h^k) - \hat{\mu}^{k+1}_{1:h}(x_h^k)\right)\log Z^k _{h} + \sum _{h=1}^H \left(\mu _{1:h}^k(x_h^k) - \hat{\mu}^{k+1} _{1:h}(x _h^k)\right)\log Z^k _{h}$