Divergence-Regularized Discounted Aggregation: Equilibrium Finding in Multiplayer Partially Observable Stochastic Games

Thank you for reviewing this paper and providing valuable comments. We have updated the manuscript according to the comments from all reviewers. Here, we reply to your questions and concerns about the paper.

[Weaknesses]

POSGs can neither express untimeable games nor imperfect-recall games.

Yes, we agree with that. We think timeability and perfect recall should be two standard assumptions for common equilibrium-learning algorithms in dynamic games. For clarity, we have specified the EFGs as perfect-recall EFGs.

Also, the reason they require a different representation is because treating them as NFGs is too expensive, not because they involve state.

Yes, we agree with that. But treating them as NFGs actually results in an action space whose size is exponential in the number of distinct information states. The expense is somewhat related to states.

These sentences don't flow correctly.

Thank you for pointing out the expression issues. We have revised them in our current submission.

[Questions]

What's the catch here? Does this require exponential time for small quantal shocks?

Like MMD [1], here we introduce the concept of quantal response equilibrium (QRE), which can be viewed as a class of regularized Nash equilibrium. We also borrow the NFG concept of Nash distribution to further establish a generalized concept in POSGs without relating to specific quantal shocks.

Is this claim based on experimental results for Kuhn poker? That would strike me as far from comprehensive enough to make such a sweeping claim.

Thanks for the comment. We have replaced this claim, as it is indeed not suitable in Appendix D. However, the claim is based on several facts. First, hypomonocoticity relaxes the widely used monotonicity assumption [1, 2, 3] since monotonicity strictly requires $\lambda=0$ rather than $0\leq\lambda<\infty$. Theoretically, we prove that every NFG has a bounded $\lambda$ (Proposition 1). For dynamic games, we numerically estimate the order of magnitude for $\lambda$ to show that it should not be a large quantity in multiplayer Kuhn poker, which we subsequently use as a test environment.

Why does it matter to provide an underestimate of an upper bound?

Thanks for the comment. We also find it inappropriate to specify the computed value as an underestimate and have removed this expression. Now we simply state that when the sampling is sufficient, the supremum of the computed value can be an estimate of a true $\lambda$ and thus reflect its order of magnitude.

How did you tune the parameters of the baselines for the experiments?

For the step size $\eta$, we selected from $\\{0.001,0.002,0.005,0.01,0.1,1\\}$ for each algorithm. Since R-NaD and MMD do not provide experimental results in Kuhn poker with more than two players, we tuned their parameters based on the original settings for 2-player Kuhn poker when applying them to 3-player and 4-player scenarios. For the NFGs, we found the original parameter setting of moving-magnet MMD can already guarantee good performance and thus did not change it.

Did you use Q-values or counterfactual values for R-NaD and MMD for the experiments?

For R-NaD, we used counterfactual values, which its original paper specifies. For MMD, we also used counterfactual values and verified the algorithm in 2-player Kuhn poker. However, we find that they no longer demonstrate a stable performance as DRDA when Kuhn poker has more than two players with more ranks, even if we have tried a range of parameters under different orders of magnitude.

References:

[1] Sokota S, D'Orazio R, Kolter J Z, et al. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. International Conference on Learning Representations, 2023.

[2] Abe K, Ariu K, Sakamoto M, et al. Adaptively perturbed mirror descent for learning in games. International Conference on Machine Learning, 2024.

[3] Perolat J, Munos R, Lespiau J B, et al. From Poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. International Conference on Machine Learning, 2021.

Thanks again for your comments. We are looking forward to having further discussions with you.

Like MMD [1], here we introduce the concept of quantal response equilibrium (QRE), which can be viewed as a class of regularized Nash equilibrium. We also borrow the NFG concept of Nash distribution to further establish a generalized concept in POSGs without relating to specific quantal shocks.

This doesn't isn't really what I was trying to get at. To put it more directly: computing a equilibria in general-sum games is hard from a complexity perspective. How does this jive with DRDA's guarantees? Will it be very slow in the worst case?

Thank you for reviewing this paper and providing valuable comments. We have updated the manuscript according to the comments from all reviewers. Here, we reply to your questions and concerns about the paper.

[Questions]

Q1: The paper uses a more general POSG setting compared to traditional EFGs. What are the core challenges unique to this choice, and how do they affect algorithm design?

The core challenge of using POSG in place of traditional EFG is that POSG can have an infinite horizon, which existing research on EFG hardly deals with. When the time horizon is infinite, the counterfactual value commonly used in the EFG algorithms (like R-NaD) becomes undefined, and we need to re-examine the convergence of learning dynamics under a general action value defined by Eq (3).

Q2: Multi-round DRDA resembles a variant of perturb-based methods from previous work [1]. What advantages does DRDA offer over these established approaches?

APMD is close to MMD with respect to the update formula and close to R-NaD and DRDA with respect to the learning scheme. The four methods all exhibit certain last-iterate convergence. The theoretical results of APMD and MMD can be directly applied to NFGs, and R-NaD focuses on perfect-recall EFGs under counterfactual value. In comparison, DRDA examines general infinite-horizon POSGs under action value. Besides, the last-iterate convergence of APMD, MMD, and R-NaD all require the monotonicity of the game, while DRDA only requires hypomonotonicity, which is a much less stringent assumption.

Q3: Can prior methods like R-NaD [2] or APMD [1] be directly applied to POSGs, or are there specific limitations in these algorithms that DRDA addresses?

In principle, R-NaD or APMD can be applied to POSGs by replacing the value function with a general action value. However, no existing theoretical or experimental result suggests that the algorithms can still converge under this condition. DRDA addresses this limitation since it is directly established in POSGs under action value. Besides, even using counterfactual values, R-NaD and MMD still cannot converge in multiplayer Kuhn poker (Section 5.2). This suggests that DRDA could be more suitable for solving multiplayer dynamic games.

References:

[1] Abe K, Ariu K, Sakamoto M, et al. Adaptively perturbed mirror descent for learning in games. International Conference on Machine Learning, 2024.

[2] Perolat J, Munos R, Lespiau J B, et al. From Poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. International Conference on Machine Learning, 2021.

Thanks again for your comments. We are looking forward to having further discussions with you.

Thank you for reviewing this paper and providing valuable comments. We have updated the manuscript according to the comments from all reviewers. Here, we reply to your questions and concerns about the paper.

[Weaknesses]

Weakness 1: Thanks for the comment. Currently, we have highlighted that we examine the convergence to a kind of QRE under action value in general POSGs. In comparison, MMD [Sokota] focuses on the original QRE concept in NFGs, and R-NaD [Perolat] considers a kind of QRE under counterfactual value in EFGs. For the connection to MMD, we have aligned the notations in Appendix E.2 of our current submission.

Weakness 2: Thanks for the comment. In fact, the relationship between DRDA and MMD can be established only when the base/magnet policy is fixed as a uniform policy. Under general divergence regularization, the behavior of the two learning dynamics can be quite different, no matter whether the base/magnet policy is changing or not.

Weakness 4: Thanks for the comment. For clarity, we have revised our experiment descriptions in Section 5 and Appendix E.1. For the $\alpha_m$ in the original submission, we clarify that it should be a fixed step size $\eta$ rather than a scheduled learning rate since we only use the simplest Euler's method. In our experiments, the rest-point convergence for single-round DRDA is guaranteed when $\eta$ is kept below the level of $10^{-2}$. Besides, we clarify that SDRDA is the discretization we employ and that an iteration is exactly one step of the Euler algorithm.

[Questions]

Q1: How does multi-round DRDA depend on the gap of single-round DRDA from its rest point? If I understand correctly, this is unknown?

If we understand correctly, the $\mathcal{V}$ in Section 4.2 is the gap that you refer to? This gap approaches zero exponentially fast by Theorem 2 but can still exist in practice. However, the definition of multi-round DRDA requires an oracle $\mathcal{M}$ that assumes the gap to be zero. Therefore, how this gap practically affects multi-round DRDA is indeed unknown.

Q2: How do you explain the "spikes" in Figure 1/2 at the beginning of each new round?

We think the spike is a result of switching the base policy in KL-divergence to the current policy. Since the current policy is not an exact Nash equilibrium, it is unstable under the new regularization (using itself as the base). Therefore, at the beginning of the next round, it quickly comes to another region of policies, which may have a relatively high NashConv.

Q3: In Figure 2, 3-player Kuhn, the "levels" (ignoring the spikes) are not monotonic for DRDA. I find it surprising. How is it possible it converges overall? Is there a measurable quantity that is monotonic? (perhaps regret? or gap from regularized eq?)

Yes, this phenomenon suggests that it may be impractical to directly prove the monotonicity for the NashConv gap itself. However, it is likely that an upper bound of NashConv at the rest point monotonically comes to zero. The exact form of this upper bound, though unknown for now, could be the key to characterizing the convergence of multi-round DRDA. This quantity may not relate to regret, as last-iterate NashConv has no direct relationship with regret in multiplayer games. For example, OFTRL is no-regret, but its last iterate is away from Nash equilibrium in our 3-player NFG experiment. However, we think your second hypothesis deserves further investigation. This quantity could be the equilibrium gap in a game under certain divergence regularization, e.g., using an NE policy as the base. When the original game has a unique Nash equilibrium (corresponding to the unique DA rest point), this gap also approaches zero as the policy approaches the unique NE.

Q4: Finding NE outside of constant-sum games is PPAD-hard as I'm sure the authors are well aware of. Perhaps it is hard to remove the uniqueness assumption because of that?

Yes, we agree that the uniqueness assumption serves to keep the problem out of PPAD-complete. However, as is claimed in our response to Reviewer W41z (Q3), we find that the uniqueness of rest point may not be a necessary condition since it can be somewhat replaced by other distinct assumptions like individual concavity. It may also require an auxiliary assumption to establish an explicit convergence rate for multi-round DRDA.

Q5: Can you please run the algorithm on typical POSG games like the tiger, and compare to methods like HSVI?

Currently, we have run a 5-round DRDA ($10^3$ iterations per round, $\epsilon=0.1, \eta=0.01$) in Adversarial Tiger game and Competitive Tiger game under time horizon $H\in\\{2,3,4\\}$ and compared our result with the best result reported in [1]. Among HSVI, random search, informed search, SFLP, and CFR+ algorithms, SFLP demonstrates the best performance in all six cases (reported in Table 2 of [1]). However, SFLP is clearly outperformed by DRDA when we align the performance measure using NashConv:

In Adversarial Tiger with $H=4$, SFLP is reported to achieve a 0.32 NashConv using 8 sec, while DRDA can achieve a 0.017 NashConv in 8 sec (terminating with a 0.010 NashConv in 10 sec).

In Competitive Tiger with $H=3$, SFLP is reported to achieve a 0.36 NashConv using 48 sec, while DRDA achieves a 0.028 NashConv within 3 sec.

In Competitive Tiger with $H=4$, SFLP is reported to achieve a 0.48 NashConv using 14 min, while DRDA achieves a 0.024 NashConv within 5 min.

For the other three cases, SFLP is reported to achieve NashConv below 0.16 or 0.24 in 1 sec, while DRDA terminates with NashConv below $10^{-4}$ also in 1 sec. We have additionally provided the tiger game results in Section 5.2 (Figure 3) and Appendix F.4 (Table 7) of our current submission.

Q6: Can you please compare the algorithm also with Smoothed Predictive Regret Matching+ (with restarts)?

Yes, we have run stable/smooth PRM+ (with restart/projection; see [2]) in the NFGs and EFGs. However, we find the two techniques (stabilizing/smoothing) do not have an actual effect on the original PRM+ except in our 3-action bimatrix game, as the individual maximum regrets do not come below $1$ after initialization in the other 4 game scenarios. For the NFGs, the last iterates of PRM+ do not converge, while the stabilized one in the 3-action bimatrix game eventually converges at a high precision. In 3-player Kuhn poker, PCFR+ exhibits certain last-iterate convergence around $10^{-6}$. In 4-player Kuhn poker, PCFR+ oscillates around $10^{-3}$. In comparison, DRDA is eventually at the level of $10^{-10}$ and $10^{-6}$, respectively. Therefore, DRDA has a clear advantage over PRM+ in 4 out of the 5 games. We have additionally provided the last-iterate learning curves for PCFR+ in Section 5.2 of our current submission.

Q7: How much tuning did the experiments require? The discussion is missing.

For the step size $\eta$, we selected the best one from $\\{0.001,0.002,0.005,0.01,0.1,1\\}$ for each algorithm. The other parameters for DRDA and R-NaD were slightly tuned to guarantee the two algorithms at least converge in each single round. The parameters of moving-magnet MMD were tuned based on the setting mentioned in its original paper. In Appendix E.3 of our current submission, we further provide a discussion about the parameter selection for DRDA.

References:

[1] Delage A, Buffet O, Dibangoye J S, et al. HSVI can solve zero-sum partially observable stochastic games. Dynamic Games and Applications, 2024, 14(4): 751-805.

[2] Farina G, Grand-Clément J, Kroer C, et al. Regret matching+: (In)stability and fast convergence in games. Advances in Neural Information Processing Systems, 2024, 36.

Thanks again for your comments. We are looking forward to having further discussions with you.

Line 299: Currently, we also find it hard to directly prove that it always exists. In our current submission, we add the existence of GND as an extra condition in the second statement of Theorem 3. Still, the assumptions in Theorem 4 and the first statement of Theorem 3 do not change since Nash equilibrium (i.e., GND under $\epsilon=0$) always exists. For the definition of GND, it serves to relate a game to a learning dynamic under the same regularization. In NFGs, Nash distribution corresponds to the rest point of discounted FTRL. For POSGs, Definition 4 provides a GND concept that can "characterize" the rest point of DRDA (by Theorem 1). Actually, after examining a range of potential GND definitions, we find that Lemma 3 and Theorem 1 still hold if we replace the terms $\Pr\left(h _ t|\pi _ *\right)$ in Definition 4 with $\Pr\left(h _ t|(\pi ^ i,\pi _ * ^{-i})\right)$. This provides another form of GND definition, and we only require a policy to satisfy either one when applying Theorem 3 in practice.

References:

[1] Daskalakis C, Panageas I. Last-iterate convergence: Zero-sum games and constrained min-max optimization. 10th Innovations in Theoretical Computer Science, 2019.

[2] Lee C W, Kroer C, Luo H. Last-iterate convergence in extensive-form games. Advances in Neural Information Processing Systems, 2021, 34: 14293-14305.

Thanks again for your comments. We are looking forward to having further discussions with you.

Thank you for reviewing this paper and providing valuable comments. We have updated the manuscript according to the comments from all reviewers. Here, we reply to your questions and concerns about the paper.

[Questions]

Q1: Can you say anything about what equilibria is being selected by DRDA compared to other methods?

Like magnetic mirror descent (MMD) and regularized Nash dynamics (R-NaD), single-round DRDA finds a kind of quantal response equilibrium (QRE). However, DRDA examines the convergence to a type of QRE under action value in general POSGs. In comparison, MMD focuses on the original QRE concept in NFGs, and R-NaD studies a type of QRE under counterfactual value in EFGs. For DRDA with multiple rounds, it aims to find the Nash equilibrium in a less and less perturbed game (which eventually becomes the original game).

Q2: How realistic is the local hypomonotonicity assumption? I don’t think this is addressed in the text.

Hypomonotonicity relaxes monotonicity by allowing $\lambda$ to be non-zero, and local hypomonotinicity further relaxes (global) hypomonotonicity by allowing the property to hold in a local policy set rather than the entire $\Pi$. In the paper, we have actually provided some evidence to show that global hypomonotonicity is already a realistic assumption. For static games, we theoretically prove every NFG has a bounded $\lambda$ (Proposition 1). For dynamic games like Kuhn poker, we estimate the order of $\lambda$ in Appendix D and find it should not be a large quantity.

Q3: How realistic is the single rest point assumption? Is the single rest point a feature of the game, learning dynamics, or both? Do the games in the experiments section have this property? What happens if they do not have this property?

The uniqueness of rest point in DRDA is analogous to the uniqueness of equilibrium in a game (regularized under corresponding $\epsilon$ and $\pi_{base}$). Since the learning dynamic is actually induced by the game, the uniqueness of rest point is essentially a game feature. Some existing theoretical works on last-iterate convergence (e.g., [1] and [2]) also assume the uniqueness of NE, which is not guaranteed to hold in real-world games. However, even when the uniqueness of the rest point does not hold, DRDA can still work in reality. For example, in Appendix B.2 of our current submission, we prove the same NashConv bound in addition to Theorem 3 when the game is individually concave (e.g., the NFGs in the experiment). That is to say, the uniqueness of the rest point should not be viewed as a necessary condition.

Q4: The experiments look like single seed runs. Did you run a parameter sweep?

Yes, the algorithms do not involve randomness when starting from a uniform policy (by default). However, we did run the algorithms under different parameter settings. For the step size $\eta$, we selected the best one from $\\{0.001,0.002,0.005,0.01,0.1,1\\}$ for each algorithm. The other parameters for DRDA and R-NaD were slightly tuned to guarantee the two algorithms at least converge in each single round. The parameters of moving-magnet MMD were tuned based on the setting mentioned in its original paper. In Appendix E.3 of our current submission, we further provide a discussion about the parameter selection for DRDA.

[Minor]

Line 16: We say the (action) value function is "general" because it considers both imperfect information and infinite horizon. In comparison, the widely used concept of counterfactual value is undefined when the time horizon is infinite.

Line 39: Yes, pursuit-evasion games and video games like fighting games are naturally formulated as MGs.

Line 69: Yes, Nash distribution is a type of QRE and is distinct from Nash equilibrium. It can be viewed as an equilibrium in a perturbed/regularized game, while NE is for the original game.

Line 109: This set is not explicitly used in this paper, but it is generally required in the POSG definitions.

Line 169/184/203/…: Thank you for mentioning the styling. We have revised them in our current submission.

Line 169: No, it is not important. What you refer to could be directly called exploitability and is also commonly used.

Line 183: The notation $a$ here is different from \vec{a} and actually indicates $a^i$. Since all players share the same action set $\mathcal{A}$, we do not specify the superscript of $a$ here in order to match the subscript of $\pi^i_a$.

Line 225: Yes, it is actually a state-action value. But it is just common to use a general notation $v$ as such (not related to the function $V(\cdot)$) when it comes to defining the (hypo)monotonicity of the game.