Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The main contributions of the paper are twofold:

* on one hand, the paper provides an overview of the main sources of complexity when computing a Nash Equilibrium in two-player zero-sum game with imperfect information. Those are named *backward dependence problem* and *non-correspondence problem*.
* on the other hand, the paper propose a novel resolution scheme that addresses these two problems by combining the Pub-MDP construction developed by Nayyar et al. (2013) with the minmaxKL framework developed by Perolat et al (2021). These two techniques respectively address the backward dependence problem by transforming the game to remove the private information and the non-correspondence problem by guaranteeing a unique Regularized Nash Equilibrium in any subgame.

This is a theoretical paper that introduces and formally defines each concept and gradually constructs the final proposed solving procedure. Small experiments are provided to add empirical evidence of convergence of the proposed method.
strength_and_weaknesses: The strengths of the paper are a well-explained setting, in which the crucial problems are clearly highlighted, a strong formalism adopted, a well explained relation with previous works, and a novel result which connects in an actionable framework imperfect information and perfect information settings.

On the other hand, I found crucial steps of the paper to be difficult to quickly comprehend due to the heavy formalism adopted and a lack of insightful comments (more details on this in the next Clarity section). More importantly, I think that the lack of an algorithmic perspective on the results makes very unclear any evaluation of impact of the proposed framework. I would have liked to see a justified algorithm-like procedure to wrap-up the contribution of the paper, and a transparent evaluation of the time/complexity needed to solve game instances , maybe with a comparison to the CFR algorithm that is currently state-of-the-art.
clarity,_quality,_novelty_and_reproducibility: **Clarity:** the setting of the paper and its main problems are well described and clear to follow. The formalism used is precise and clearly defined. However, two main points of the paper need extra accompanying explanations to improve their clarity. In particular, the Pub-MDP definition is very formal and it is complex to get the overall picture due to the amount of symbols used (especially for the definitions of $\tilde{\mathcal T}$ and $\tilde{s}$). I'd suggest some `\underbrace{}` or an accompanying comment as done in the definition of $\tilde{\mathbb{A}}$ for the Pub-AMG. The other point is Theorem 3. I'd suggest a preliminary explanation of the $q$ distribution (I expect it to be q-values) and the *policy greedification function* $g$ and a expansion of the sketch of proof by including more about the relation between interior image and uniqueness.

I have some questions: 

* regarding the proof of existence of equilibrium in Theorem 3: why isn't it already guaranteed by the Nash theorem?
* regarding the Experiments in Section 7: why was a MMD vs Regularized-BR setting used?
* how does your proposed procedure computationally compare with CFR?

Moreover, some symbols used are unclear and/or undefined:

* $h^{t+1}$ instead of $H^{t+1}$ in the definition of $\tilde{s}$ of the Pub-MDP
* $\pi(H^t_\iota)$ in Definition 5.1
* $q$ in Theorem 3

Typos: "is has" in the sketch of proof of Theorem 3

**Quality**: the paper addresses a complex topic in a rigorous way; even though I did not check any proog in the Appendix apart from the one of Theorem 3, the provided sketches of proofs are sound and can be easily followed by an expert of the related literature

**Novelty**: The Pub-MDP results are well known in the literature thanks to many important papers. Especially Section 4 of Brown et al. (2020) already introduces the PBS as a way to remove private information in a two-player zero-sum game. The real novel result of the paper therefore resides in the use of the minimaxKL framework by Perolat et al. (2021) and it uniqueness of equilibrium guarantee to develop a game-solving procedure.

**Reproducibility**: the theoretical results are well documented and can be easily reproduced. The lack of both a formal procedure and/or open source code may make more difficult the experimental reproducibility of the paper, even though it is not a major issue.
summary_of_the_review: Overall, I find the result offered by the paper and the justifications provided really interesting for the game-solving community. On the other hand, the weaknesses highlighted previously are important issues that should be properly addressed to allows a smoother and comprehensive exposition.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In games of imperfect information, players' payoffs are known, but actions may not be.  An example would be a two player simultaneous move game, whose game tree depicts one player as moving second, but unable to distinguish between the nodes reachable from each of the other player's actions.

As imperfect information complicates reasoning, some method for handling it must be developed when deriving equilibria.

In games in which players' incentives are aligned, it may be enough for one player to announce its strategy (Nayyer et al.).

The current manuscript argues that imperfect information can also be abstracted away from when one player has a unique strategy, allowing the other to determine which node has been reached.
strength_and_weaknesses: **Strengths**

**Weaknesses**

See below.  On the latter, I am primarily concerned that the manuscirpt's density makes it difficult to read and understand.
clarity,_quality,_novelty_and_reproducibility: **Clarity**
- to me, basic elements of the paper were unclear, including what type of equilibrium we are interested in (Nash, subgame perfect, Perfect Bayesian...)
- lists of specialist notation are provided at a number of points without sufficient explanation for a non-specialist reader to understand
- I would like to see the reasoning related more tightly to more 'mainstream' game theory.  (How, for example, is this related to work developing from Mailath and Samuelson's imperfect observability?)

**Quality**
- it is hard for me to assess this given my concerns about clarity, above.  I _think_ that the paper's point is simple: uniqueness removes uncertainty.

**Novelty**
- I have not seen arguments quite like this before
- the paper itself suggests (e.g. around Corollary 1) that some of its main results can be found elsewhere

**Reproducibility**
- not attempted
summary_of_the_review: Overall, I felt that the paper was trying to pack too much specialist material in, without motivating it enough for a more general reader to understand.  This also meant, unfortunately, that the paper was only able to motivate its connection to machine learning in passing.

If the manuscript is not accepted here, I think it could be a fruitful exercise to rewrite it for submission to a dedicated game theory journal.  This would allow it more 'space to breathe', without the tight page limit, and require it to connect more tightly to the existing literature, strengthening its foundations.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In two-player zero-sum games, when we modify utility objective of minimax optimization with an appropriate regularization term, it is always possible to find a unique solution that has error at most $\epsilon > 0$ in the original optimization problem. This is an important previous result from [1]. Let's call any such objective modification "uniqueness-guaranteeing" (UG).

This paper shows that solution of UG optimization tackles the "non-correspondence problem" between the subgame strategies and the trunk strategies (part of the game played above the subgame), simply from the virtue of UG solution being unique (so there is no danger of using two incompatible equilibria). 
In contrast, in the existing literature, the correspondence has been solved for arbitrary equilibria using gadget games [2].
This work shows that one can use value-solving subgames [3] when using UG, without the need to use the gadget game.

Value-solving subgames are rooted in public belief states, where players publicly announce what strategies they played so far.
Authors thus identify that optimizing minimax UG objective in imperfect-information game is equivalent to optimizing minimax UG objective in what authors call "perfect-information" PuB-AMGs.

[1] From poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization.

[2] Solving imperfect information games using decomposition.

[3] Rethinking formal models of partially observable multiagent decision making.

[4] Sound algorithms in imperfect information games

[5] Player of games.

strength_and_weaknesses: Strengths:
+ Provably correct solution of the non-correspondence problem without using gadget games. This is important, because empirically strategies in gadget games converge very slowly, often at rate close to their upper bound, and value-solving subgames are empirically fast. 
+ Authors generalize result from [1], i.e. what regularizations are UG.

Weaknesses:
- I find introduction of PuB-AMGs and calling them "perfect-information" games misleading at best, and disingenuous at worst. 
  A similar "perfect-information" game transformation would be to let a player pick a strategy for the whole game, announce it publicly, and let opponent do the same, and evaluate the expected utility of the game. Pub-AMGs trick is the strategies are additionally factored over public states.
  One could get a superficial impression that with the transformation, you can take any off-the-shelf algorithm for perfect-information games, such as AlphaZero, to find an equilibrium in imperfect-information games, which is not true. In this sense the reduction is not particularly useful. I view it as "rebranding" of value-solving games as a new concept, i.e. the PuB-AMGs.
  Futher, the diagram in Figure 1 suggests that PuB-AMGs are fully observable. This is false. The players do not receive full observations about what is going on the game -- they do not receive opponent's observations.
- The non-correspondence problem has been studied before and is not cited, i.e. [4].
- There is a missing text on limitations of the method:
  - Computing KL-regularized equilibrium for arbitrary small $\epsilon > 0$ is slow. Further, computing regularized equilibrium in sequential games needs recursive computation of regularized best responses, yielding asymptotic complexity of $O(T^D)$, where D is depth of the game and T is number of regret minimizer iterations. The algorithm has been applied to Kuhn Poker (with some tricks to make if faster, as explained in appendix), and is impractical for even slighly bigger game, like Leduc Poker.
  - A lot of the practical speedups of CFR-based methods comes from pruning unreachable subtrees. When using regularized equilibria, all actions are in the support, and no subtrees can be pruned.
- In introduction, authors write existing approaches are hampered by discontinous functions (i.e. values for AOH not being convex in terms of their associated beliefs). However, [5] proved that approximative value functions, unlike optimal value functions, can be made continuous. Additionally, authors do not prove whether their approach yields continous functions or not.

Other comments:
- Definition 6.1. \rho in  is not defined.
- Definition 5.1. R is a real-valued funtion of what? What is pi(H_i^t) ?
- Experiments: Regularized exploitability is undefined.
- Is annealed regularization the same algorithm as in [1], i.e. double-iteration algorithm where one approximates reg. equilibrium, and then iterates over the regularization step size (to speed-up convergence)?
- "We observe that all objectives with positive regularization converge to zero regularized exploitability, in accordance with our theory." -- Can you refer the theorem?
- Figure 4,5: Why did you pick 1/sqrt(t) and 1/t, and not just one consistenly?
- I would be interested in comparison of minimaxEnt/minimaxKL in experiments.

clarity,_quality,_novelty_and_reproducibility: The paper was well written, however I think it would be made clearer if it was written using the existing concept of value-solving subgames, instead of introducing new game formalism.
Some symbols and terms were not defined. Sometimes I could guess their meaning from related literature, but a clarifying revision is required.
Solving non-correspondence problem using value-solving subgames is a straightforward application of [1], and generalization of UG is an application of brouwer FP theorem.


summary_of_the_review: Overall I like the direction of the paper. It has two substantial contributions, solving non-correspondence problem using value-solving subgames, and generalization of UG.
The paper could be made stronger by including experimental comparisons with gadget games to show (if) convergence to equilibrium shows faster in practice.
However, addressing all the criticism would require a major rewrite. I recommend authors to resubmit their revised work.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper makes an interesting contribution to the problem of finding equilibria in partial information games through the addition of public information. However, it does not very clearly position itself to the state of the art and it does not compare with alternative techniques experimentally. 
justification_for_why_not_higher_score: Although the paper is mainly theoretical, an experimental comparison with alternative techniques would normally be necessary. One reviewer thinks a major re-write would be necessary, and I also agree.
Decision: Reject