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

Authors: Canzhe Zhao, Yutian Cheng, Jing Dong, Baoxiang Wang, Shuai Li
Primary area: reinforcement learning
Keywords: Extensive-form games; partially observable Markov games (POMGs); last-iterate convergence

Abstract:
We study learning the approximate Nash equilibrium (NE) policy profile in two-player zero-sum imperfect information extensive-form games (IIEFGs) with last-iterate convergence. The algorithms in previous works studying this problem either require full-information feedback or only have asymptotic convergence rates. In contrast, we study  IIEFGs in the formulation of partially observable Markov games (POMGs) with the perfect-recall assumption and bandit feedback, where the knowledge of the game is not known a priori and only the rewards of the experienced information set and action pairs are revealed to the learners in each episode. Our algorithm utilizes a negentropy regularizer weighted by a virtual transition over information set-action space. By carefully designing the virtual transition together with the leverage of the entropy regularization technique, we prove that our algorithm converges to the NE of IIEFGs with a provable finite-time convergence rate of $\widetilde{O}(k^{-\frac{1}{8}})$ with high probability under bandit feedback, thus answering the second question of \citet{Fiegel2023adapting} affirmatively.

Decision: reject
Reviewer scores: 5, 8, 6, 5

Reviews and discussion:
<thread>
creation date:
1729565036186

thread_type:
official_review

<thread_object>
creator: reviewer_usyt

<content>
summary:
This paper establishes the first finite-time last-iterate convergence for learning an appeoximate NE of IIEFGs in the bandit feedback settting. They prove that their algorithm achieves the last-iterate convergence of order $O(k^{-1/8})$ with high probability and of order $O(k^{-1/6})$ in expectation. Also, they provide the lower bound of order $\Omega(k^{-1/2})$ for learning IIEFGs  with last-iterate convergence guarantee in the bandit feedback setting.

strengths:
This paper presents the first finite-time last-iterate convergence results for learning an approximate NE of IIEFGs in the bandit feedback setting. The proposed algorithm achieves a last-iterate convergence rate of $O(k^{-1/8})$ with high probability, $O(k^{-1/6})$ in expectation, and establishes a lower bound of $\Omega(k^{-1/2})$.

weaknesses:
In my view, the theoretical contributions of this paper are sound and without weakness. My concerns are primarily focused on the following aspects:

- The paper's analysis of the limitations of previous regularizers is overly obscure and difficult to comprehend. Firstly, I do not fully understand why the vanilla negentropy regularizer is generally difficult to control the NE gap, given that it directly regularizes the sequence-form representation policies. Secondly, the authors claim that bounding the stability term of OMD with dilated negentropy critically depends on its closed-form update solution. However, when solving Eq. (2), I find that no closed-form solution is provided.

- The benefits of the proposed regularizer are not clearly articulated. Based on the current version, I do not fully understand the advantages of the proposed regularizer, such as its impact on proving the convergence results of the proposed algorithm.

- 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.

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

- Could you elaborate on the contribution of your proposed regularizer to the convergence results of the algorithm?

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

- 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730062478184

thread_type:
official_review

<thread_object>
creator: reviewer_fkcc

<content>
summary:
This paper studies learning in partially observable Markov games with bandit feedback. An algorithm is proposed that leverages the negentropy regularizer weighted by a virtual transition over infosetaction space. The proposed algorithm is proved to obtain last-iterate convergence. A lower bound for learning in imperfect-information extensive-form games under bandit feedback setting is also provided.

strengths:
The considered partially observable setting is significant in practical.The results are well-structured, and the analysis is explained in a way that flows smoothly, making it easy to follow despite the technical complexity. The introduction of the virtual transition seems to be novel in the proof. Overall this paper is well-written.

weaknesses:
My main concern is the lack of experiments to support the theoretical results. I would be particularly interested in seeing how the proposed algorithm performs in practical game scenarios.

questions:
- What is the computational cost required in Algorithms 1 and 2?

- Is there any other method that can solve the game described in this paper? If so, how does the empirical performance compare?

Typo:
- In line 101, there are two 'to'.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730802336410

thread_type:
official_review

<thread_object>
creator: reviewer_xwcs

<content>
summary:
This paper studies the problem of learning approximate NEs in IIEFGs, with the perfect-recall assumption and bandit feedback. They propose an algorithm based on a negentropy regularizer weighted by a virtual transition. The proposed algorithm achieves finite-time last-iterate convergence and is fully uncoupled between the two players involved.

strengths:
This paper is in general well-written and smooth to follow. The authors did a great job in introducing the background literature, and in motivating the design of the proposed algorithm. The theoretical results, namely the finite-time last-iterate convergence for learning approximate NEs in IIEFGs, are of vital importance in the literature, and the theoretical proofs seem to be rigorous. The results of this paper serve as an important step towards improving the last-iterate convergence guarantee.

weaknesses:
Although the theoretical side of this paper is strong, simulation parts are completely missing. I would appreciate the authors could simulate the proposed algorithm on several example settings to validate the last-iterate convergence and potentially the rate of convergence.

questions:
- Intuitively, 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?
- It is stated that employing the virtual transition helps to operate OMD in the space of visitation measure instead of sequence-form representations of policies. However, as is shown in Eq (5), the virtual transition is directly related to a sequence-form representation. Can the authors discuss more on this? And why operating OMD in the space of visitation measure is important?
- It seems that the virtual transition is fixed at the beginning (once the game tree is fixed), could one potentially define an adaptive virtual transition, utilizing the historical bandit feedback up till now to further improve the convergence rate?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730806934410

thread_type:
official_review

<thread_object>
creator: reviewer_xgrk

<content>
summary:
The paper proposes an algorithm for two-player zero-sum imperfect information extensive-form game with bandit feedback. The algorithm ensures that if both players use it simultaneously, the last iterate of their strategies converge to the Nash equilibrium in a rate of t^{-1/8} (or t^{-1/6} in expectation). The technique is based on negative entropy regularization that has been utilized in normal-form game / Markov game, with the additional technique called virtual transition.

strengths:
- This works gives the first algorithm for 2p0s imperfect information extensive-form game with polynomial-time last-iterate convergence guarantee under bandit feedback. 
- This work introduces a virtual transition technique designed to regularize policy updates in extensive-form games, driving last-iterate convergence. This approach adapts the commonly used entropy regularization technique from normal-form games to the extensive-form game setting.

weaknesses:
- The work seems to be a straightforward extension from Cai et al. (2023), which studies last-iterate convergence in normal-form game with bandit feedback. This is not a major concern though, as it speaks more to the simplicity of the setting than to the insufficiency of the solution. 
On the other hand, 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).

questions:
- Can you explain why 1/X * 1/p^x_{1:h}(x_h) <= 1 (claimed in the last line of Page 23)?  
- Does the algorithm still work if replacing the p^x(x_h) in Line 278 simply by 1/X (essentially making p^x a uniform distribution over infoset)?  If this is possible, then Line 278 is essentially not using virtual transition because you can absorb the factor 1/X into \epsilon_k.  If not, can you point out where the analysis might break? 
- I do not quite understand the explanation in Line 340-344. Why is bounding the stability of dilated negentropy critically relies on its closed form? This is not the case for general OMD.  Stability term is related to how much the iterate moves between rounds, and the stability term in a "more constrained case" is smaller than that in a "less constrained case". So why not the stability term in \Pi_max smaller than that in the entire space, and existing analysis suffices?
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper examines the problem of learning approximate Nash equilibria in two-player zero-sum imperfect information extensive-form games (IIEFGs). The authors model IIEFGs as partially observable Markov games (POMGs) with perfect recall and bandit feedback, i.e., the game’s structure is a priori unknown, and only the rewards of experienced information set-action pairs are observed in each episode. They propose an algorithm that employs a negentropy regularizer weighted by a virtual transition over the information set-action space. By carefully designing this virtual transition and leveraging entropy regularization techniques, the authors prove that the proposed algorithm converges to Nash equilibrium with a finite-time (last-iterate) convergence rate of $\widetilde{O}(k^{-\frac{1}{8}})$ with high probability under bandit feedback.

This paper was discussed extensively between authors and reviewers, and Reviewer xgRk in particular went into great depth discussing both technical and conceptual details. One of the main concerns raised was that the paper seems, in certain regards, incremental over previous work by Cai et al., and the reason to include the virtual transitions is somewhat uncompelling - especially because it seems motivated by low-level proof details as opposed to conceptual reasons. This reliance on virtual transitions means that the algorithm requires full prior knowledge of the game's infosets, in contrast to prior work by, e.g., Kozuno et al., which only requires updates on the infosets that a player actually visits during play. Reviewer USyT also pointed out several computational complexity issues with the authors' approach which were not adequately addressed by the authors during the discussion phase.

In the end, despite some partial improvement in the reviewers' assessment of this work, it was not possible to make a clear case that the paper meets the (admittedly high) acceptance criteria of ICLR, so a decision was reached to make a reject recommendation to the program chairs.