Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies partially observable extensive games with perfect recall. They propose a computationally efficient model-free algorithm with $\sqrt{T}$-regret. The algorithm works by reducing the tree-structured game to a linear bandits problem and then applying some variant of EXP-IX (similar to Jin et al., 2020) to solve it.

main_review: This paper is well-written and easy to follow. The new algorithm looks computationally efficient and has regret guarantee matching the best known result. Moreover, it can also play favourably against adversarial components. 

Is the conversion to online linear bandits first proposed in this work? If not, maybe it would be better to point this out explicitly in section 3.1. Besides, the algorithm designed in this paper bears much similarity to Jin et al., 2020. I feel it’s worthwhile to point it out in the paper.

Could you provide a direct comparison between this paper and Lanctot et al. (2009); Farina et al. (2020) in terms of computational complexity? I believe this comparison is necessary especially when these works have the same regret.

How do you compare this work to [1]? I think it would be interesting to compare the two settings studied in this paper and [1]. Which setting is more general or practical? 

Overall this is an interesting paper making reasonable contributions. 

[1] A Sharp Analysis of Model-based Reinforcement Learning with Self-Play.
Qinghua Liu, Tiancheng Yu, Yu Bai, Chi Jin. ICML 2021


limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of learning Nash equilibrium policies in two-player zero-sum extensive games, under the assumption of bandit feedback. The authors propose an algorithm that is based on Implicit Exploration and OMD, and they provide an high-probability regret bound that scales sub-linearly in the number of iterations and polynomially in the size of the game. Interestingly, the regret bound holds even in an online setting (not in self-play) in which both the policies of the opponent and the game structure are chosen adversarially.
main_review: Originality: The problem studied in the paper is not novel, but it recently received a lot of attention in the literature. The ideas used in the paper are novel; in particular that of using Implicit Exploration.

Quality: As far as I am concerned, the proofs are correct.

Clarity: Overall, the paper is clear, but there are some minor typos and I have some suggestions:
- Line 9: "Moreover..." => "Moreover,...".
- Line 19: "max..." => "max-...".
- Line 58: "consider" => "considers".
- Line 66: It is not clear to which algorithm the sentence "This algorithm..." refers to.
- Line 69: "such that" => "such as".
- Line 96: Is it "O(H)" or "O(H A)"?
- Line 120: "p_0" is missing from the definition.
- Line 128: "define" => "defined"; I think it's better to define "X_h" here.
- Section 2: The notation is cumbersome and hard to follow; I would suggest the authors trying to avoid the use of multiple subscripts and apices and that of many indexes, such as "h", "h'", and "k". (Don't know actually if notation can be improved easily).
- Line 184: "gives" => "give".
- Line 9 in Algorithm 1: "with..." is redundant.
Also, it seems to me that the algorithm is working over the sequence-form strategy space. Am I correct? If yes, why didn't you frame the whole technical contribution in the sequence-form setting? I think that would have helped clarifying notation and presentation.

Significance: The paper provides a good contribution to its field, and I think it fits well within the scope of the NeurIPS conference.
limitations_and_societal_impact: Adequate.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes Implicit Exploration Online Mirror Descent (IXOMD) algorithm that achieves sublinear regret in unknown extensive-form two-player zero-sum games with high probability. The setup is that player learn rewards only when actions are taken at some step, and do not learn about counterfactual reward they could have earned, have they made a different choice in the iteration. IXOMD is an adaptation of OMD, it uses importance sampling estimator of the losses with implicit exploration (to appropriately weigh the reward of the action taken and reduce its possibly high variance) and dilated entropy distance-generating function as a regularizer for the computation of next-step strategies.
Authors prove that IXOMD achieves sublinear regret with appropriate setting of the algorithm hyperparameters - the learning rate and the exploration penalty. Thus the algorithm can be used to approximate Nash equilibria (if both players use the algorithm) with high probability.

main_review: The paper is quite dense in notation, but clear and easy to follow. The proposed OMD adaptation achieves a high-probability regret bound, compared to other OMD adaptations that achieve the bound only in expectation. As authors note, there exist several other algorithms for their proposed online setting, and while they claim to achieve a better convergence rate in theory, it is a bit shame that they did not compare them in experiments as well. Especially, when other works [1] found that in practice CFR-based methods are still faster than OMD, despite worse convergence rates of CFR. Adding the experiments would improve my rating.

I do not understand the classification of "adversarial game" in Table 1. Some algorithms were classified as incapable of playing in the setting where the adversary also picks the game to play. This is a trivial game transformation, that can be formally achieved as the opponent has an additional decision node in which it picks the game to play, and thus this is a well specified large game (that can be decomposed into the multiple sub-games). Perhaps authors meant the adversary can pick any game whatsoever, from an infinite number of games? But wouldn't such an unlimited choice make the convergence rates vacuous, as they all depend on the number of infosets (that would be infinite as well?)

Authors write that "IXOMD requires almost no prior knowledge of the game. [..] We only require an oracle providing the possible actions at encountered information sets and a bound on A, B, and H to tune optimally the learning rate". 
However, in Remark 3, to set the learning rate and exploration, also the time horizon T is used. Without the knowledge of the time horizon the regret bound can still contain the bias caused by the exploration. This should be mentioned as another (theoretical) limitation when this algorithm can be used. In constrast, for example [2,3] have worse convergence rates, but their algorithm is independent of the time horizon, because the hyperparameters do not depend on time, thus may be suitable in a repeated play where we do not know the time horizon.

Other comments:
- L37-38 while CFR+ achieves 1/sqrt(T) in theory, in practice it is often 1/T and it does not need a choice of hyperparameters.


[1]  Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions

[2]  Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games. 

[3]   Stochastic Regret Minimization in Extensive-Form Games.
limitations_and_societal_impact: The time horizon should be discussed, see the main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies self-play algorithms in extensive form games with imperfect information. The proposed algorithm, IXOMD, can achieve the best-known sample complexity and achieve several desirable properties.
main_review: I have a few concerns about the results:

1. How is the POMG setting in this paper related to EGII? Are they just one thing? Because the name of POMG always reminds me of general MG, where you don't have a tree structure.

2. The idea of reduce the problem into online linear bandit optimization and use a different divergence are brilliant. My understanding is that they are borrowed from existing literature and this paper improves them to high probability regret bound, right? Then I think maybe the authors want to make this explicit and add some explanation. For example, I don't understand why we need dilated entropy instead of KL as in adversarial MDP?

3. On time complexity. The authors claim the proposed algorithm requires only O(HA) time per episode. However, there are many existing works on computational barriers in POMDP, which is a special case of POMG. For example, see the discussion in 1.1 in [2]. Why this is not a contradiction?

4. On related work. The authors have made a long remark on related work on adversarial MDP. Actually, I think a more related setting is self-play algorithms in MG (with perfect information). Comparing with the sample complexity of algorithms for MG can also highlight the unique challenge in POMG. For example. see [3][4][5]

5. On the setting. In the related work section, the authors make the difference between full information and bandit information. So in the bandit feedback setting, can we see the state (instead of just the observation)? I know the algorithm proposed in this paper doesn't need this additional information, just a question concerning the setup. Furthermore, a natural question will be, it seems knowing the state when rolling out a trajectory doesn't help to achieve a better rate (by comparing the rate with existing works). Am I understanding correctly?

[1]  Regret Minimization in Games with Incomplete Information 

[2] Sample-Efficient Reinforcement Learning of Undercomplete POMDPs

[3] Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium

[4] Provable Self-Play Algorithms for Competitive Reinforcement Learning

[5] Near-Optimal Reinforcement Learning with Self-Play
limitations_and_societal_impact: This part is good.
review_title: null

Meta-review: This paper studies partially observable extensive games with perfect recall. They propose a computationally efficient model-free algorithm with sqrt(T) regret. All reviewers believe the results are solid and strong, and the techniques used in this paper are interesting. Therefore, we recommend acceptance.
Decision: Accept (Poster)