- Rating
- 4
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper generalizes the distribution correction estimation (DICE) method for offline single-agent RL to multi-agent general-sum convex Markov games, where agents may have different concave utilities. The proposed offline algorithm cMG-DICE approximates the equilibrium of the regularized game based on a fixed dataset of logged transitions. The regularization keeps the resulting joint state-action occupancy close to the fixed dataset. The algorithm applies best-response dynamics, where each agent repeatedly, in every iteration, computes its best response w.r.t. the fixed current opponents' strategy. The main technical contribution consists in the best response computation. Using shadow rewards, the authors manage to reformulate the best response max-min optimization problem into a minimization problem over shadow rewards and Lagrangian multipliers. The authors use the resulting updates to seek an equilibrium of the regularized game, and relate its exploitability to that of the target game under data-coverage assumptions.
Critical strengths
Offline methods are surely useful and the experimental results show that the proposed method can generate low-exploitable strategies in the original (not regularized) game. Further, I appreciate the technical derivation of the offline best-response objective that handles the particular agent utilities.
Critical weaknesses
As a weakness of the proposed cMC-DICE algorithm, I see its convergence and exploitability guarantees. The paper gives finite-convergence guarantees only for a rather limited class of near-potential games. In general, I guess that the best response dynamics can produce cycles.
Questions for authors
How to handle situations when the best-response dynamics does not converge? Can it happen?
2 comments
Thank you very much for the detailed answer to my question on cycles! I really appreciate it.
Dear Reviewer ncc1,
We thank the reviewer for the careful reading and the insightful question. To support the answer below, we added a simple experiment on the NoSDE game [1], a sequential version of a cyclic game such as matching pennies, to Appendix H, with a figure (Figure 6, at α=0.1) showing how cMG-DICE can cycle and how we handle it.
Can the dynamics cycle? (Sections 3.2 and 4.1, Appendix H)
Yes, when the agents update by exact best responses, the dynamics can cycle in a cyclic game. Proposition 2 in the revision holds for general continuous utilities: every such game is a 2ϵu-potential game, where ϵu is the largest externality, the deviation of an agent's utility from the average utility, and alternating exact best responses that move only on gains above 2ϵu+δ stop with regularized exploitability at most 2ϵu+δ. In cyclic Markov games such as the NoSDE game, this bound is uninformative (2ϵu=1.0, the full range of the normalized returns), and the exact alternation (Algorithm 1), which moves on every gain, can cycle (Figure 6).
How we handle it. (Section 3.2) Our practical implementation uses the approximate alternation (Algorithm 2), which takes one gradient step per agent per turn instead of solving each best response to its minimum. Both alternations stop only at a Nash equilibrium of the regularized game, and the approximate one can settle where the exact one cycles (Figure 6).
This approximate alternation is not a new method: experiments in the submission already used it. However, we described it only in the experimental details (Appendix F) and not in the method section. As it is an important part of cMG-DICE, we added a paragraph to Section 3.2 to make it explicit, and Appendix H compares the exact and the approximate alternations.
cMG-DICE on the NoSDE game. (Full result in Appendix H) The NoSDE game is a two-state Markov game whose best responses cycle, and value-iteration methods are known not to converge to its unique stationary equilibrium [1]. We ran the two alternations from 104 transitions of uniform play, starting from the same joint policy. With α≤0.1, the exact alternation keeps cycling with target-game exploitability about 0.33 (Figure 6, left). The approximate alternation settles at the equilibrium of the regularized game for every α (Figure 6, right); at α=0.02 it reaches send probabilities (0.649, 0.403), close to the stationary equilibrium (2/3, 5/12), with target-game exploitability 0.006.
While the full details are in the revised paper, we would be glad to elaborate upon request.
[1] M. Zinkevich, A. Greenwald, and M. L. Littman. Cyclic equilibria in Markov games. In Advances in Neural Information Processing Systems 18, 2005.