Local and adaptive mirror descents in extensive-form games

Summary

The submission considers the problem of learning epsilon-Nash equilibria from trajectory feedback in zero-sum extensive-form games. The submission focuses on developing that avoids importance sampling over action sequences.

Strengths

The submission is well-written, and the problem and solution are reasonable. The experiments are reasonable choices to demonstrate the efficacy of the solution.

Weaknesses

My main criticism of the submission is that it purports its motivation to be motivated by solving large games. However, using a fixed sampling is untenable for learning good policies in large games, as the target policy and the behavioral policy will become too far apart. Model-free approaches to learning equilibria in large games (i.e., [1, 2]) learn on policy. It would be good for the submission to discuss this discrepancy and how it can be resolved in greater detail. I'll mention that the submission does already acknowledge this point and include some discussion at the end. Also, it is worth noting that [2] showed empirical convergence for an on-policy algorithm with trajectory feedback and no importance sampling over action sequences. It would be interesting for the submission to discuss the feasibility of providing theoretical grounding for those results. [1] From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization (2020) [2] A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games (2023) One other comment I had: > Existing procedures suffer from high variance due to the use of importance sampling over sequences of actions (Steinberger et al., 2020; McAleer et al., 2022). This claim and citation is a bit confusing. The whole point of McAleer et al. (2022) was to address this issue. The submission is citing a paper that refutes the claim of the sentence.

Questions

I guess I'd be curious to hear the author's thoughts on whether providing grounding for [2]'s results is a promising direction.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

I'll mention a limitation of my own review here: I did not confirm the correctness of the theory, so I'll defer to the other reviewer's on that point.

Summary

The paper studies the extensive-form game under the fixed sampling policy framework. It proposes the algorithm based on online mirror descent. The paper gives near-optimal regret bounds for the proposed algorithm, under different learning rate settings. The algorithm is justified with experiments.

Strengths

1. The the paper has detailed introduction and literature review, with a clear description of the problem setting and framework. The paper also makes sufficient comparisons to existing works under the same or different framework. 2. The result has optimal dependency on $T$ and near-optimal dependency on other game-related parameters. The removal of the importance sampling term in the fixed-rate setting is a good contribution. 3. The paper justifies it's theory with experiments. It makes comparison with a benchmark method and experiment result looks convincing.

Weaknesses

1. The framework itself is still confusing. While the authors made some discussion of the framework in section 2.2, the advantage of fixed sampling policy seems not reflected in the paper's theoretical result. And in terms of the regret, the paper's result doesn't improve the regret of simultaneous regret minimization procedures. 2. On the explanation of the theory, the paper can be improved by adding comparison to more benchmarks. The paper only compares the result with the result of simultaneous regret minimization procedure, and the conclusion is the bound matches but doesn't improve the existing result. It could be helpful to understand the paper's result by comparing previous results under the same fixed sampling policy framework.

Questions

From the theorems the fixed and adaptive rate bounds have the same dependency on $T$. Is it correct to understand the motivation of the adaptive rate is only to remove the dependency on the importance sampling term $\kappa$? When the balanced policy is used as the sampling policy, $\kappa$ is reduced to a game-dependent term. In this case, is it correct think the adaptive rate setting as unnecessary?

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

/

Summary

I reviewed an earlier version of this paper. While I have some additional comments, my review is largely similar to my previous review, since the paper has only a few minor edits relative to the previous version, as far as I can ascertain. The paper introduces algorithms designed to approximate Nash equilibria in zero-sum imperfect information games (IIG) with trajectory feedback. Specifically, the authors focus on the fixed-sampling framework. Past approaches have struggled with significant variance, largely due to the utilization of importance sampling across action sequences (McAleer et al. (2022) provide an algorithm that doesn't require importance sampling, but their techniques don't generalize to non-scale invariant regret-minimization-based algorithms such as OMD). The proposed approach employs an adaptive Online Mirror Descent (OMD) algorithm. This involves using adaptive learning rates along with a dilated regularizer. The paper demonstrates that this method ensures a convergence rate of O\tilde(T^{-\frac{1}{2}) with high probability and exhibits a near-optimal dependence on the game parameters, when employed with appropriate choices of sampling policies.

Strengths

The paper provides a strong technical contribution in producing an adaptive trajectory-feedback-based adaptive OMD algorithm that doesn't rely on importance sampling and generalizing DS-OMD to use time-varying regularization. The paper provides empirical evidence for the convergence and variance of their approach, compared to other approaches in the literature, and also provides code for their algorithm.

Weaknesses

The paper could delineate its contributions better. As noted by most reviewers in a previous submission, the similarity to the regret circuit decomposition of CFR is apparent (and noted by the authors). Still, the difference could be further highlighted in the contributions, especially since this was confusing for several reviewers last time. A note was made by the authors last time regarding the interpretation of their method as regularization at the global level (whereas CFR doesn't have this sort of interpretation). While it is mentioned now that the proposed algorithm is an instance of GDS-OMD, I think these things could be further emphasized throughout the paper. Along the same lines, one of the reviewers pointed out last time that things like $h_t$ and $q_t$ are not defined in the main body, and as far as I can tell, this is still an issue, even though the authors indicated that this would be clarified (even if not at the detailed technical level as done in the appendix) in the main body. It would be good for the authors to implement these changes, given that they assured the reviewers they would do this to improve the presentation. One of the reviewers noted last time that the motivation for variance reduction is unclear. I agree with this. While the reviewers mention that variance reduction becomes a concern for performance in function approximation settings, it would be nice to see this in their experiments (since the current empirical evidence for the provided algorithm doesn't seem to indicate that there is much gain in performance beyond the variance reduction with the current approach).

Questions

No specific questions beyond the weaknesses mentioned above.

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes

Response

> We thank Reviewer HP7A for pointing out these empirical results and we will add this reference in our literature review. Before answering, we would like to point out some differences between their theoretical setting and ours. First, they have a strong monotonicity assumption for the underlying operator they consider (in our case, would be). This strong monotonicity assumption does not hold for their experiments, as the operator is linear with respect to the realization plan, hence they need to add some regularization, parameterized by the constant. Second, they consider a full feedback setting in theory, observing the outcomes of all possible trajectories at each episode. There may be a misunderstanding about the point I was making here. I was specifically pointing to their experiments with black box feedback (not full feedback) in Figure 13. The reference provides no theory for these experiments, but I think they are still interesting because they seem to be converging 1) on policy, 2) without importance sampling over sequences, 3) using black box feedback. I would be curious to hear any speculation the authors' may have on whether or not deriving guarantees for algorithms having those properties is a promising direction for this literature.