Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes to learn a history-dependent value function and sample actions from a fixed sampling policy to replace the importance sampling and reduce variance.

Overall, this paper is well-written and easy to follow, the reviewer is not very professional in the field of CFR, but still catches most of the content.

*** The reviewer has reviewed this paper in neurips2022, since most of the concerns are addressed by the reply at that time, the reviewer would suggest acceptance at this time. 

There are still some minor questions as follows. 
strength_and_weaknesses: Strength:

(1) This paper is well-written and easy to follow, the background part and related work are very detailed.

(2) The authors give proof of the upper bound of ESCHER assuming a fixed sampling policy.

(3) The additional Table 2 in this version clearly shows the differences between ESCHER and previous works 

Weaknesses:

(1) ESCHER proposes a two-stage iteration, which may not be a good practice (also discussed in the Limitation part). The gap between the outer fixed sampling policy and the inner regret learning should be addressed experimentally or theoretically.

(2) In the neurips2022 rebuttal, the authors also agreed that "Yes, retraining a value function every iteration is slow, but that's not the main point of the paper", therefore, it is expected to estimate the additional overheads for training the value function. And some of the results should be presented in another way. For example, the x-axis in Figure 3 is the number of iterations, which may guide the reader that ESCHER converges much faster than DREAM and OS-MCCFR, but the effort within an iteration should be noted.

(3) The correlation between the high variance of the regret estimator and the low performance/winrate of the algorithm should be addressed. Since the algorithm may have a larger variance due to its unique settings and hyperparameters but can perform well in practice (e.g., proximal policy optimization), the authors are encouraged to give more evidence why ESCHER is better.




clarity,_quality,_novelty_and_reproducibility: sound
summary_of_the_review: see above
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors study the approximation of  Nash equilibrium in very large extensive-form games with prefect recall. One line of research approximates with the use of neural networks the tabular algorithm: counterfactual regret minimization (CFR). One issue with these methods is that they train a neural network with targets that can have extremely high variance due to the use of importance sampling estimation (of the counterfactual regret). The authors propose the ESCHER algorithm a model-free method that does not require any importance sampling. They prove that the tabular version is guaranteed to converge to an approximate Nash equilibrium with high probability. Experimentally they show that both the tabular version and the deep version of ESCHER enjoy a smaller variance than several baselines such that Outcome Sampling MCCFR in the tabular case and NFSP and DREAM in the function-approximation case. Furthermore they show that ESCHER outperform NFSP and DREAM on three games: Phantom Tic-Tac-Toe, Dark Hex 5 and Dark Chess.
strength_and_weaknesses: *Strength

- An importance sampling free algorithm for imperfect information games

*Weaknesses

- Lack of clarity.
clarity,_quality,_novelty_and_reproducibility: #Review

Dealing with the high variance of MCCFR type algorithms, especially in the non-tabular case is an import question. Thus, I think  the proposed solution is a valuable contribution since it seems to solve this issue. However, the presentation of the submission does not meet the requirement of what I would consider acceptable for this venue. In particular several key quantities are ill-defined or  not defined at all, see specific comments. Also, some parts of the algorithms that should be discuss thoroughly are left unspecified, see specific comments. For these reasons, in the overall, it is hard to asses the quality of the presented method. Furthermore, we could expect more discussion (experimentally and theoretically trough min_s w(s)) on the choice of the sampling policy and the effects of this choice.  The proofs seem correct as far as I checked. We would expect access to the code used for the experiments.



#General comments:
- The code for the experiments is not available.
- As notice in Figure 3, it seems that the high variance is not an issue in the tabular case. Can you elaborate on the conjecture 'that high regret estimator variance makes neural network training unstable without prohibitively large buffer sizes'. Could you also think about experiments that may support this conjecture.

#Specific comments:
- P2, Section 2: Could the utility be non-zero at non terminal state?
- P2, Section 2: Why the observation should depends on (w,a,w') and not only w'? 
- P2, Section 2: Abbreviation RL not defined.
- P2, Section 2: The best response is not necessarily unique then BR could be a set as you defined it.
- P3, Section 2.1: Section 8.
- P3, Section 2.1: Could you define precisely \eta^\pi(h)? In (1), \eta^\pi(h,z) is not defined neither u_i(z) (= \mathcal{U}_i(z)?) . Similarly (2) is hard to read without the definition of the used quantities.
- P3, Section 2.1: The average policy (of CFR?) converges in which sense? What is e(\bar{\pi}^T)?
- P5, above (4): Can you explain why sampling uniformly over actions allows to roughly 'visits every information set equally'?
- P5, (5): It seems that q(\pi,h,a) is never properly defined.
- P5, below (6): Policy b instead of \pi'?
- P6, Algorithm 1: For self-completeness you could defined what is the regret matching algorithm. And can you explain how exactly you can compute \hat{r} from the sampled trajectory \tau from \tilde{p}. In particular is it easy to compute q_i and v_i? In general it could be useful to state to which oracles you agent has access.
- P6, Theorem 1: What do you mean by 'the regret accumulated by each agent', is this regret defined somewhere?
- P6, Section 4: Which policies do you use exactly to fill the first replay buffer?
- P7, Table 2: Add a reference for the baselines you compare with. And bootstrapped baseline in the first row.
- P7, Section 4: What is the quantity that you want to approximate with R_i(s,a|\psi) exactly? Is there any difficulties in approximating a running sum? How do you concretely handle the dependence over the policy \pi in the q-value network  q_i (\pi, h, a|\theta)? How do you train the average policy network and the value network exactly?
- P6, Algorithm 2: It seems that the replay buffer and update of the value network do not appears in the algorithm.
- P8, Figure 1: Can you precise how many seeds did you use in the experiments?
- P13, Proposition 1: \hat{\pi}_i and v_i(\pi) is not defined.
- P14: Can you provide a pointer for the regret bound of regret matching or even rewrite the results. 
- P15: I'm not sure I understand the end of the sentence: 'translate linearly into additive regret overhead'.
- P15, Section 7: Can you provide an upper bound on 1/min_s w(s) in the case where you use as sampling policy the one uniform over actions.
summary_of_the_review: See above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper develops an algorithm, ESCHER, to reduce the variance of CFR with deep learning by avoiding importance sampling.
strength_and_weaknesses: The intuition looks pretty reasonable to me. However, I still have some questions regarding ESCHER before I can recommend accepting.
1. In Section 3 it's claimed sampling using a fixed distribution (what I think is the $\tilde{\pi}$ here) can avoid importance sampling. Why this is the case? I don't think this claim is supported properly.
2. In the last line of equation (6), $w(s)$ is defined via $\pi'$ but I think it comes from the sampling strategy $\tilde{\pi}$ right? Why is the inconsistency here? Is this a typo or I have missed something important?
3. It looks to me very obvious that if an oracle of value function is available, we never need to use importance sampling because we can compute the counterfactual regret directly. I don't think this makes any essential improvement, since we may still need important sampling to estimate these value functions from samples. How should this be handled? Actually, I think this is more important than the content discussed in detail in section 3, and the authors may want to explain more about that.
4. I think it will be super helpful it the authors can give some intuition on why it's possible to avoid using importance sampling at all. Say for the strategic-form game, can we also avoid using importance sampling in Mento Carlo using the proposed approach? Or is there any certain character of  EFG such makes this possible?
clarity,_quality,_novelty_and_reproducibility: The paper is clear and the idea is novel. For validness I indeed have some concerns raised above.
summary_of_the_review: The paper develops an algorithm, ESCHER, to reduce the variance of CFR with deep learning by avoiding importance sampling. The motivation looks sound to me but I need to be convinced how the remaining part hidden from oracle of value function can be addressed before recommending accept.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary:
The paper develops an algorithm, ESCHER, to reduce the variance of CFR with deep learning by avoiding importance sampling in games. . They prove a theory for the tabular setting that the algorithm is guaranteed to converge to an approximate Nash equilibrium with high probability. Experimentally, they show that ESCHER enjoy a smaller variance than several baselines. Furthermore they show that ESCHER outperform NFSP and DREAM on three games: Phantom Tic-Tac-Toe, Dark Hex 5 and Dark Chess.

Strength:
- Paper well-written and easy to follow
- An importance sampling free algorithm for imperfect information games
- Algorithm outperforms baselines in a number of games

Weakness:
- The biggest weakness of the ESCHER approach is the sampling policy. It appears that the policy is an arbitrary or uniform policy. It is hard to believe such a policy can work in any environment that need to make sequential decisions. The theory part requires this assumption to provide guarantees. But the constant hiding in Theorem 1 can be exponential. Indeed, experimentally, the algorithm has good performance. It would be stronger if the authors could explain why the uniform policy works for these cases and what is the bound of the const in Theorem 1. 

justification_for_why_not_higher_score: It would be stronger if the authors could explain why the uniform policy works for these experiments and what is the bound of the const in Theorem 1. 

justification_for_why_not_lower_score: The experiments demonstrate the efficacy of the proposed approach and the paper can be accepted.
Decision: Accept: poster