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

Authors: Runyu Lu, Yuanheng Zhu, Dongbin Zhao
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: partially observable stochastic game, Nash distribution, divergence regularization, hypomonotonicity, last-iterate convergence, Nash equilibrium

Abstract:
This paper presents Divergence-Regularized Discounted Aggregation (DRDA), a multi-round learning system for solving partially observable stochastic games (POSGs). DRDA is based on action values and applicable to multiplayer POSGs, which can unify normal-form games (NFGs), extensive-form games (EFGs) with perfect recall, and Markov games (MGs). In each single round, DRDA can be viewed as a discounted variant of Follow the Regularized Leader (FTRL) under a general value function for POSGs. While previous studies on discounted FTRL have demonstrated its last-iterate convergence towards quantal response equilibrium (QRE) in NFGs, this paper extends the theoretical results to POSGs under divergence regularization and generalizes the QRE concept of Nash distribution. The linear last-iterate convergence of single-round DRDA to its rest point is proved under the assumption on the hypomonotonicity of the game. When the rest point is unique, it induces the unique Nash distribution defined in the POSG, which has a bounded deviation from Nash equilibrium (NE). Under multiple learning rounds, DRDA keeps replacing the base policy for divergence regularization with the policy at the rest point in the previous round. It is further proved that the limit point of multi-round DRDA must be an exact NE (rather than a QRE). In experiments, discrete-time DRDA can converge to NE at a near-exponential rate in (multiplayer) NFGs and outperform the existing baselines for EFGs, MGs, and typical POSGs.

Decision: accept (poster)
Reviewer scores: 6, 8, 6, 8

Reviews and discussion:
<thread>
creation date:
1729804956320

thread_type:
official_review

<thread_object>
creator: reviewer_luwx

<content>
summary:
The submission studies a regularized variant of FTRL for solving for equilibria. The submission derives continuous-time limit point results for convergence to Nash equilibria in general-sum settings and compares experimentally to a variety of baselines.

strengths:
Converging to Nash in general-sum settings is a very difficult problem. Let me also say that I did not attempt to go through the submission's math. I evaluated the submission's soundness, presentation, and contribution as "fair" largely because I lack expertise to judge the novelty or correctness of the technical contribution. Similarly, I evaluated the submission as a 6 as I feel I lack the expertise to verify its value. Should other reviewers possess greater expertise I will defer to them, though I do feel confident saying that the writing is unclear in important places and the experimental results are weak. I'm also a bit concerned about the tension between the complexity results for computing equilibria in general-sum games and the claims made in the submission.

weaknesses:
> solving partially observable stochastic games (POSGs), which unify normal-form games (NFGs), extensive-form games (EFGs),
and Markov games (MGs).

This isn't correct. In contrast to EFGs, POSGs can neither express untimeable games nor imperfect-recall games.

> While a wide range of game-theoretic learning dynamics, including no-regret dynamics and best response dynamics, were primarily analyzed in static normal-form games (NFG), many real-world games are dynamic and thus require to be solved under a different game representation

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

>  imperfect information game

Requires hyphen.

>  For example, the perfect information game of Go can be formulated as a Markov game (MG) by ignoring the action
of the waiting player. The imperfect information game of Texas Hold’em is commonly formulated as
an extensive-form game (EFG). In view of this requirement,

These sentences don't flow correctly.

> As an extension of MGs, partially observable stochastic games (POSGs) introduces imperfect information and is capable of unifying NFGs, EFGs, and MGs.

Again, not true re EFGs.

> forizon

> The existence of the rest point of single-round DRDA is thus proved.

It's not clear to me why this is a non-trivial result.

> Theorem 1. In a POSG, every GND ⃗π∗ under ϵ > 0 induces a rest point (⃗v(⃗π∗), ⃗π∗) in single-round
DRDA, and every GND ⃗π∗ under ϵ = 0 (i.e., Nash equilibrium) induces a DA rest point (⃗v(⃗π∗), ⃗π∗).

This also seems kind of trivial to me.

---

Other weaknesses:
- The results are continuous time, not discrete time.
- The games studied in the experiments seem quite limited.

questions:
> On the other hand, 

On the other hand compared to what?

> For general-sum games, the last iterate of a “discounted” variant of FTRL, first examined in Leslie & Collins (2005), is proved to converge to the solution concept of Nash distribution (Coucheney et al., 2015; Gao & Pavel, 2021), a specific form of quantal
response equilibrium (QRE) (McKelvey & Palfrey, 1995)) defined in NFGs.

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

>  Therefore, the hypomonotonicity assumption used in our convergence analysis should not be regarded as a strong
assumption.

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.

> These underestimates could reflect the order of magnitude of the true global hypomonotonicity value
λ, which must be an upper bound for the local hypomonotonicity required in Theorem 2.

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

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

Did you use Q-values or counterfactual values for R-NaD and MMD for the experiments?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730648553417

thread_type:
official_review

<thread_object>
creator: reviewer_kwq7

<content>
summary:
This paper introduces Divergence-Regularized Discounted Aggregation (DRDA), a multi-round learning method designed for partially observable stochastic games. DRDA builds on a discounted version of Follow the Regularized Leader, adapting it for POSGs to address imperfect information and infinite horizons. The authors expand on previous work showing last-iterate convergence to quantal response equilibrium by defining a generalized Nash distribution, which extends the QRE concept to POSGs via divergence regularization.

strengths:
1. This paper builds on prior work by extending last-iterate convergence from NFGs and EFGs to POSGs, with theoretical proofs, broadening the method's applicability.
2. It introduces the concept of a generalized Nash distribution, enhancing the QRE framework through divergence regularization.
3. Convergence proofs are provided for both single-round and multi-round DRDA, strengthening the method's theoretical foundation.
4. Experimental results demonstrate that DRDA outperforms existing methods across various benchmarks.

weaknesses:
See Questions.

questions:
1. 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?
2. Multi-round DRDA resembles a variant of Perturb-based methods from previous work [1]. What advantages does DRDA offer over these established approaches?
3. 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730672454660

thread_type:
official_review

<thread_object>
creator: reviewer_rhfe

<content>
summary:
This paper introduces a new algorithm for finding a Nash equilibrium in partially observable stochastic games (POSGs), which include setting with an infinite horizon. 
The algorithm, abbreviated DRDA, is inspired by previous work on finding epsilon-regularized Nash equilibria, which have limitations of a finite horizon and may not always have convergence guarantees in a multi-player setting.
They generalize the epsilon-regularized Nash equilibria to include the discounting factor of infinite-horizon POSGs, to form what they call a generalized Nash distribution (GND).
DRDA can be formulated as an ODE, which is solved repeatedly in multiple rounds to converge to an NE in the limit.

While the theory for convergence requires an assumption that is not clear if it can be satisfied in all games (rest point of DRDA is unique => GND has bounded deviation from NE) and the theory of multi-round DRDA converge is not well established, experiments show that the DRDA converges to a high precision in small games, at a near-exponential rate.
Moreover, they provide linear convergence bounds under some hypomonotonicity assumptions.

strengths:
- Paper is well written, given the high complexity of the topic.
- They show linear convergence if epsilon > lambda, the hypomonotonicity constant. I find the hypomonotonicity intriguing. I think it's likely to  see future follow-ups on this work.

weaknesses:
- The theorems 1, 2 and 4 look similar to the results found in [Sokota] and [Perolat], extended to the POSGs. I did not investigate the exact differences, but these links deserve more highlights. Connection to MMD is written about in the Appendix, but as the update equations are written in two different notations I found it hard to follow in a limited time.
- Connected to previous the previous point, in experiments they compare with moving-magnet version of MMD, as L431 "MMD is close to DRDA", which they also abbreviate as MMD, while this version is substantially different from the non-moving-magnet base case. (Perhaps MMM would be a better abbreviation.) This makes me concerned that the real innovation of this paper is showing linear convergence under the hypomonotonicity assumption. 
- I would enjoy more thorough discussion of the experiment results, see also the questions.
- Appendix E: The Euler method used for single-round DRDA -- SDRDA -- has a learning rate whose schedule is not mentioned in the paper and its relation to the rest point convergence in Theorem 2 is not clear. Also, in experiments they used MDRDA, which uses the Euler-based SDRDA. At first, based on the main paper text, I was under the impression that the discretization of Eq (6) is used for DRDA in the experiments, but the actual algorithm used is different. What is considered as an iteration exactly? One step of the Euler algorithm? It would be helpful to correctly label the algorithm in experiments as MDRDA.

questions:
- How does multi-round DRDA depend on the gap of single-round DRDA from its rest point? If I understand correctly, this is unknown?
- How do you explain the "spikes" in Figure 1/2 at the beginning of each new round?
- 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?)
- 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?
- Can you please run the algorithm on typical POSG games like the tiger, and compare to methods like HSVI?
- Can you please compare the algorithm also with Smoothed Predictive Regret Matching+ (with restarts)? 
- How much tuning did the experiments require? The discussions is missing.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730719492622

thread_type:
official_review

<thread_object>
creator: reviewer_w41z

<content>
summary:
The paper introduces a new variant of multi-round discounted FTRL (called DRDA) which works in general (n-player, general-sum, partially observable, simultaneous or sequential action) games. The paper shows that the new algorithm converges (last-iterate) to a generalized Nash distribution (a Nash equilibrium of a regularized version of the game). Under an assumption (unique rest point), multi-round DRDA is proved to converge to an NE.

strengths:
General games are hard. Any work that attempts to learn and prove convergence in this setting is important to the community.

Last-iterate convergence is valuable, especially compared to average-iterate algorithms that are common in the field.

Experimental results look impressive.

weaknesses:
No discussion on the assumptions.

Tabular.

Single experiment seed runs.

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

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

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?

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

Minor:

* Line 16: “General value function”. I was unsure what this meant at first read through. A Non-zero sum value function?
* Line 39: Go is more naturally formulated as an EFG. Is there a more natural example for MGs?
* Line 69: If I am reading this right, “Nash distribution” is distinct from “Nash equilibrium”?
* Line 109: Is the set of all joint observations ever used? It seems like a strange quantity.
* Line 169/184/203/…: Please use inline math styling.
* Line 169: I am curious if using sum over player convs (rather than max) is important? I realize both would be zero at equilibrium. 
* Line 183: Should a have a superscript: a^i? Because it is player i’s action, rather than a joint action?
* Line 225: Is this not more like a q-value? Why use v rather than q for the notation?
* Line 299: Does a GND always exist? It is not clear to me since any perturbation away from pi_base will result in: u^i(pi^i, pi^01_*) - u^i(pi_*) <= epsilon * (some negative value)

Score:

I am willing to raise the score after discussion with co-reviewers. Although I like the results, my main concern is how novel the contributions are compared to previous works. I would also like to be reassured that the method routinely converges -- I do not have a good intuition of how strong of an assumption single-resting point is. Furthermore, any answers to the questions I have asked will also likely improve my understanding and appreciation of the work.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732711803364

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response to All Reviewers

comment:
Dear reviewers,

Thank you for reviewing this paper. We greatly appreciate your effort in reading the paper and providing valuable comments. Your suggestions are quite helpful for us to improve the quality of this paper. Based on your comments and suggestions, we have made a revision to our manuscript and updated the submission. The major modifications involve Section 1 (Introduction), Section 5 (Experiments), Appendix B.2 (Related to Individual Concavity), Appendix D (Game Hypomonotonicity), Appendix E (Implementation Details), and Appendix F.4 (Tiger Game). The additional/revised contents have been highlighted in blue/green. We will be happy if our responses and modifications can address your concerns and improve your appreciation of this work. If you find something unclear, please feel free to point it out. We are more than delighted to have further discussions and improve our manuscript.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper studies equilibrium-computation in partially observable stochastic games (POSGs), by developing a Divergence-Regularized Discounted Aggregation approach. Focusing on the continuous-time dynamics, last-iterate convergence was established, locally and asymptotically. Overall, the paper is well-written and easy to follow. Despite the mostly positive reviews, after more careful reading myself, I have some reservations about recommending a clear acceptance. 

First, the idea of adding (magnet) regularization to obtain last-iterate convergence in learning in games is not that novel, see e.g., earlier works [1,2,3,4,6,7] (in addition to what has been mentioned in the paper). In particular, for EFGs, [1] showed that last-iterate to QRE can be obtained without unique NE assumption, and the algorithm there is discrete-time, and the convergence results are non-asymptotic and global; for MGs (including NFGs), [2,3] introduced the idea of regularization and obtained last-iterate convergence that is "non-asymptotic" and "global" also; for "discounted FTRL" (as named in the paper, which is essentially a continuous-time version of the update rule in [5], as also pointed out by the authors), [4] has global (asymptotic) convergence guarantees, exactly based on [5], for Markov games; the "anchor-policy" regularized idea, which is essentially the single-round DRDA, in fact first appeared and validated in [6,7] (to my knowledge). However, these closely-related results (some with stronger guarantees) were not mentioned nor compared numerically, making it a bit hard and misleading for the readers/reviewers to accurately assess the contributions of the paper. The existence of MMD [8] further weakened the novelty of the proposed dynamics, as they share quite some similarities (as also pointed out in the Appendix). It would have been better if these results were well acknowledged in the main paper, and the new dynamics were sold as "extensions" or at least "inspired" by these algorithms.

Second, it would have been better if the theoretical contribution was stronger. The results were not only asymptotic and local, but also relied on strong assumptions such as the existence of a (local) compact region such that $\lambda$-hypomonotonicity is satisfied and contains a rest point, the initialization within such a region, as well as the choice of $\epsilon$ that depends on $\lambda$; the uniqueness of DA's rest point, etc. In particular, the results in Theorem 4 for multi-round DRDA relied on "the convergence of the rest-point sequences" (together with the uniqueness of the rest-point), which IMO should be part of the "convergence guarantees" one needs to prove. The only case where the $\lambda$-hypomonotonicity is "global" is the NFG case (for which there already exist stronger results), which made the significance of the condition a bit weaker, especially given that the title and the theme of the paper is to "unify" results under the POSG framework (beyond NFGs). It was not very clear what the technical challenges were in proving the main theorems (compared to the existing results mentioned above, and given some key results from [9]). It would have been a stronger case if the experimental results were more extensive. However, compared to other closely-related works, e.g., [6,7,8], the experiments mostly focused on small-scale problems, and it was not clear if the methods scale well in larger games, as [6,7,8].

Third, the technical rigor and clarity of the exposition may need a bit more care. It is known that POSGs are very hard to solve in general, not to mention "general-sum" POSGs. The current title, abstract, and writing in several places left the impression (especially for the general audience) that the proposed algorithms "solve" POSGs, which is not the case given the above comments on the theoretical results. Moreover, it was emphasized that the authors considered POSGs in order to "unify" NFGs, EFGs, and MGs. However, it is not clear any other POSGs beyond these cases can be covered. In fact, in the main results, it is not clear whether any of these games, or in fact, any POSGs, satisfy the "(local) $\lambda$-hypomonotonicity" property, besides the NFG. Also, as Reviewer LUwx pointed out, EFGs without perfect recall cannot be covered by POSGs, and, although general POSGs (without the tree structure) can still be represented by EFGs, the representation blows up. It would have been better to only claim contributions to NFG, EFG with perfect recall, and MGs (instead of general POSGs). But still, connecting the assumptions in the theory with the structures of these games would help make the case. 

Overall, I found this paper a borderline case, and suggest the authors carefully incorporate the feedback from this round (from both the reviewers and the area chair) in preparing the next version of the paper.