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

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

Q1. Specifically, the techniques seem to me ... when proper distance generating function are employed).

Thank you for this comment. Indeed, our analysis scheme is inspired by [1], as we have mentioned in Remark 5.5 of our paper. However, we would also like to remark that a key distinction between our work and [1] is that [1] uses the vanilla negentropy regularizer while we use a virtual transition-weighted negentropy regularizer. Simply using the vanilla negentropy regularizer in our problem can still guarantee a finite-time last-iterate convergence result as mentioned in Remark 5.4 of our paper, but doing so will not be able to obtain computationally efficient approximate policy updates. In contrast, with the leverage of the virtual transition-weighted negentropy regularizer, our algorithm simultaneously permits efficient approximate policy updates (please see the end of Section 4.1 and Appendix A in our paper for details) and guarantees a meaningful last-iterate convergence.

Besides, we fully agree that closed-form updates for OMD are common in IIEFGs. And it is precisely for this reason that we would like to make our algorithm computationally efficient as well. Nevertheless, we would like to note that, though dilated negentropy is common in existing literature studying IIEFGs (say, [2,3,4]), we did not use the dilated negentropy as the regularizer in our algorithm. Though it is well known that dilated negentropy admits efficient closed-form policy updates, using dilated negentropy in our problem can only lead to a vacuous convergence rate that is exponentially large in $X$, as illustrated in Section 4.1 of our paper. In contrast, as aforementioned, we leverage the negentropy weighted by the virtual transition over the infoset-action spaces. Importantly, this virtual transition is specifically designed to maximize the minimum sequence-form "visitation probability" of all the infoset-action pairs, so as to ensure a last-iterate convergence with meaningful dependence on $X$. Our virtual transition is directly computed by our Algorithm 2, and the construction of such a virtual transition is never exploited in existing literature for studying IIEFGs, let alone in [1]. Therefore, we believe our algorithmic design as well as the result is meaningful and valuable to the literature.

We hope the above explanations would be helpful to address the concerns of the reviewer about our technical contributions, and we will explicitly incorporate the above discussions into the revision of our paper for better clarity.

Q2. Which are the fundamental differences of this work with respect to (Cai et al. 2023)?

Please see our response to the question above.

[1] Cai et al. Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback. NeurIPS, 2023.

[2] Hoda et al. Smoothing techniques for computing nash equilibria of sequential games. MOR, 2010.

[3] Kroer et al. Faster First-Order Methods for Extensive-Form Game Solving. EC, 2015.

[4] Kozuno et al. Learning in two-player zero-sum partially observable markov games with perfect recall. NeurIPS, 2021

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

Q1. Additional References.

Thank you for referring to this! We compare our work with some notable works studying achieving last-iterate convergence in games with noisy feedback [1,2,3]. Specifically, [1,2,3] establish algorithms for solving two-player zero-sum matrix games or multi-player monotone games with noisy gradient feedback, where the noisy feedback for all the actions is observable. In contrast, we study learning IIEFGs with bandit feedback. That is, only the rewards of the experienced infoset-action pairs are revealed to the players. For the infoset-action pairs that are not experienced in one episode, no information regarding them is revealed, not even the noisy rewards. Hence, their algorithms are not directly applicable to our problem, and our results might not be directly comparable to theirs. Actually, in Sec. 8 of [2], the authors say that bandit feedback is a scheme with more limited feedback, and in Sec. 8 of [3], it is also mentioned that extending their results from the noisy feedback setting to the bandit feedback is a challenging future direction.

We will explicitly incorporate the above discussions in the revision of our paper for completeness.

Q2. "it would be nice to ... why virtual transition is necessary."

Thanks for this comment! The primary effect of using a virtual transition-weighted negentropy regularizer is to ensure the algorithm can be approximately updated in a computationally efficient manner. Indeed, using a vanilla negentropy regularizer without the virtual transition can also lead to a finite-time last-iterate convergence for our problem, but in this way, the policy cannot be efficiently updated, as illustrated in Remark 5.4.

Particularly, in matrix games, the policy space is simply the probability simplex over all the actions, and it is well known that using OMD/FTRL with vanilla negentropy regularizer admits a closed-form multiplicative update (see, e.g., Chap. 28 of [4]). However, in general IIEFGs, this is no longer the case since each sequence-form policy is not a probability measure over infoset-action space. Fortunately, the inner products between sequence-form virtual transitions and sequence-form policies are still probability measures over infoset-action space. Therefore, using a virtual transition-weighted negentropy regularizer permits efficient policy updates (please see Prop. A.1 in Appendix A). On the other hand, the downside of using a virtual transition-weighted negentropy regularizer is that it will enlarge the stability term (approximately) by a factor of $\frac{1}{p_{1: h}^x(x_h)}$ (please see Lem. D.1 in Appendix D). Therefore, it necessitates choosing a good virtual transition with $p_{1: h}^x(x_h)$ well lower-bounded, which is guaranteed by our Algorithm 2 (please see Lem. B.1 for details).

We will incorporate the above explanations in our revised paper for clarity.

Q3. Lower Bound.

The main difference is that our lower bound only applies to the class of algorithms with last-iterate convergence. Technically, as shown in Appendix H, the proof idea of our lower bound is that any algorithm with $\Theta(k^{-\alpha})$ ($\alpha\in(0,1)$) last-iterate convergence can also guarantee a $\Theta(K^{1-\alpha})$ regret. Thus, we can prove the lower bound for the last-iterate convergence by contradiction using the existing regret minimization lower bound of $\Omega(\sqrt{XAK})$ in learning IIEFGs with bandit feedback (say, Thm. 6 in [5]; Thm. 3.1 in [6]). Our reduction is specifically designed for the class of algorithms with last-iterate convergence and does not directly work for the class of algorithms only with average-iterate convergence. On the other hand, we note that the hard instance used in our lower bound of last-iterate convergence is the same as that in [6], as the hard instances in the proofs of lower bounds of regret minimization and sample complexity are the same [5,6].

We will further clarify this in the revision of our paper.

Q4. "What does one traversal mean?"

Due to the perfect recall condition, all the infoset-action pairs $\mathcal{X}\times\mathcal{A}$ across different steps $h$ form a tree. This tree can be constructed by performing the search (e.g., DFS, BFS) over all the infoset-action pairs one time.

We will include the above explanations in the revision of our paper.

[1] Abe et al. Last-iterate convergence with full and noisy feedback in two-player zero-sum games. AISTATS, 23.

[2] Abe et al. Adaptively Perturbed Mirror Descent for Learning in Games. ICML, 24.

[3] Abe et al. Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games. ICLR, 25.

[4] Lattimore et al. Bandit Algorithms. 20.

[5] Bai et al. Near-optimal learning of extensive-form games with imperfect information. ICML, 22.

[6] Fiegel et al. Adapting to game trees in zero-sum imperfect information game. ICML, 23.

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

Q1. "The paper mentions ... not include them in the main paper."

Thanks for pointing this out. We will be sure to explicitly include more descriptions of the experiments in the main paper body.

Q2. Additional References.

Thanks again for noting these additional references! We compare our work with these works as follows:

• [1] establishes algorithms for solving two-player zero-sum MGs with $\widetilde{{O}}(k^{-1 / 3})$ last-iterate convergence. However, they study fully observable MGs while we study partially observable MGs. Further, they require full-information gradient feedback while we only require the bandit feedback. Note that computing the full-information gradient feedback even requires the knowledge of the state transitions (please see Sec. 2.2 of [1]).

• For the comparisons with [2,3,4], please see our response to Q1 of reviewer T2uG.

• Our work and [5] both study MGs with bandit feedback. However, we remark that they study fully observable MGs while we study partially observable MGs. Further, they require the assumption that the Markov chain can be irreducible and aperiodic for some policy. Therefore, we believe their algorithm is not directly applicable to our problem and our results are not directly comparable to theirs. Besides, our algorithm is OMD-based and can still guarantee a sublinear regret of $\widetilde{{O}}(k^{7 / 8})$ when the opponent is an adversary, while the policy in [5] is updated via constructing approximations of the best response to the opponent's policies and it is not clear whether their algorithm can guarantee a sublinear regret in the presence of a potentially adversarial opponent.

We will include all the above discussions in our revised paper for better clarity.

Q3. Experiment Results.

We fully agree that on Lewis Signaling, the performance of our algorithm overlaps with that of the baseline algorithms. However, we believe the experiment results show that our algorithm performs relatively well across all game instances, and though there might be some baseline that performs similarly to our algorithm on some game instances, this baseline algorithm might not be able to converge fast on other game instances, as the last-iterate convergences of all the baseline algorithms are not theoretically guaranteed.

Specifically, as mentioned in Appendix I, on the remaining game instances that are harder to learn (note that $X=3$, $A=3$ on Lewis Signaling, while $X=6$, $A=2$ on Kuhn Poker, $X=468$, $A=3$ on Leduc Poker and $X=12288$, $A=13$ on Liars Dice), only baseline BalancedFTRL converges as fast as our algorithm on Leduc Poker. However, our algorithm converges faster than BalancedFTRL on Liars Dice, and there is clearly a large gap between our algorithm and it on Kuhn Poker during episode $10^5$ to $10^7$. The other baseline with notable performance is BalancedOMD. Nevertheless, we also would like to note that, though BalancedOMD tends to have a similar NE gap at the very end on Kuhn Poker and Leduc Poker, our algorithm converges relatively faster than BalancedOMD up to episode $10^5$ on Kuhn Poker and $10^7$ on Leduc Poker. More importantly, the performance of BalancedOMD is the worst among all the baselines on the hardest game instance Liars Dice, and our algorithm converges clearly faster than BalancedOMD on this instance.

Q4. "The virtual transition is an important tool used in the paper ..., using fewer math expressions."

Please see our response to Q2 of reviewer T2uG.

Q5. "I do not agree with the discussion on ..."

We agree that if linear function approximation is leveraged, the average policy can be obtained by applying a moving average over the parameters online. Our original statement on the LHS of Line 55-57 might not be appropriate, as we now realize, and we will revise it accordingly. When using nonlinear function approximation, averaging the parameters of nonlinear function approximation is of course possible, but our original statement on the LHS of Line 61-63 intended to indicate that simply averaging the parameters of nonlinear function approximation might not be able to obtain the average policy. To see this, let $f(x)=x^2$, $x_1=1$ and $x_2=5$. Then $f(\frac{x_1+x_2}{2})=9\ne \frac{f(x_1)+f(x_2)}{2}=13$. We will also revise this part for better clarity.

[1] Zeng et al. Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games. NeurIPS, 20.

[2] Abe et al. Last-iterate convergence with full and noisy feedback in two-player zero-sum games. AISTATS, 23.

[3] Abe et al. Adaptively Perturbed Mirror Descent for Learning in Games. ICML, 24.

[4] Abe et al. Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games. ICLR, 25.

[5] Chen et al. A finite-sample analysis of payoff-based independent learning in zero-sum stochastic games. NeurIPS, 23.

[6] Lattimore et al. Bandit Algorithms. 20.