acceptodds
Under review as a conference paper at ICLR 2027

Offline Equilibrium Computation in Convex Markov Games

Abstract

Convex Markov games extend Markov games to utilities beyond expected returns, capturing essential notions such as fairness, safety, and imitation. This expressiveness stems from evaluating the global game status through concave functions of state–action occupancies. However, this non-linearity makes policy updates dependent on the current occupancy, formalized as a shadow reward. Consequently, computing equilibria of convex Markov games requires tracking the current occupancy at every update, through fresh environment interactions or an exact transition model, making the process computationally expensive. We ask whether such equilibria can instead be approximated purely from logged multi-agent play. We propose cMG-DICE, which combines the shadow reward formulation with stationary distribution correction estimation (DICE) so that each agent's best response reduces to a single minimization over logged transitions. We demonstrate the efficacy of this framework by approximating equilibria under diverse utilities and initial joint policies on tabular games and the Clean Up environment from a single dataset, bypassing the need to restart costly online optimization from scratch for each new equilibrium.

Primary area:
reinforcement learning
Keywords:
Multi-agent reinforcement learning, Offline reinforcement learning

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_ncc1OpenReview ↗
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

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\alpha=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ϵu2\epsilon_u-potential game, where ϵu\epsilon_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+δ2\epsilon_u+\delta stop with regularized exploitability at most 2ϵu+δ2\epsilon_u+\delta. In cyclic Markov games such as the NoSDE game, this bound is uninformative (2ϵu=1.02\epsilon_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 10410^4 transitions of uniform play, starting from the same joint policy. With α≤0.1\alpha \le 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 α\alpha (Figure 6, right); at α=0.02\alpha=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.

Thank you very much for the detailed answer to my question on cycles! I really appreciate it.

Reviewer_f66qOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies offline equilibrium computation in convex Markov games, where agents optimize concave functions of the joint state–action occupancy rather than fixed expected rewards. Such utilities can express objectives including fairness, imitation, and behavioral diversity. Their gradients, called shadow rewards, depend on the current occupancy, making policy improvement more involved than in standard Markov games.

The proposed cMG-DICE method combines a shadow-reward formulation with stationary distribution correction estimation. Each agent computes a regularized best response against fixed opponents through an optimization over logged transitions, and the agents update alternately. The paper bounds the effect of data regularization on target-game exploitability and provides additional convergence analysis for the welfare-utility family used in the experiments. Experiments on three tabular games and the seven-agent Clean Up environment investigate equilibrium approximation, utility and initialization dependence, and offline prediction of returns and shadow rewards.

Critical strengths
  • The paper addresses a meaningful extension of offline multi-agent learning: agents may have different concave utilities whose effective reward signals change with their behavior. Combining shadow-reward optimization with opponent-aware occupancy correction provides a principled way to compute regularized best responses from logged data. The formulation also clarifies the relationship between nonlinear utilities and existing DICE methods.

  • The tabular experiments evaluate target-game exploitability using exact best responses and investigate how utility preferences and initialization affect equilibrium selection. The checks of learned shadow rewards and offline return predictions are also useful because they examine quantities central to the proposed method. Clean Up provides additional evidence that the approach can improve upon behavior cloning under several objectives, including objectives different from those used to generate the data.

Critical weaknesses

Weakness 1

  • Proposition 1 bounds target-game exploitability conditional on already obtaining a policy with small exploitability in the regularized game. It therefore controls regularization bias but does not establish that cMG-DICE reaches such a policy. Proposition 2 provides further analysis for a particular welfare-utility family, with the general-sum termination result relying on exact best responses and a gain-threshold update condition.
  • The connection between these results and the proposed training procedure remains incomplete. In particular, the analysis does not account for approximate solution of each best response or policy extraction with function approximation. These errors can affect both the shadow rewards and the resulting joint policy. Consequently, it is difficult to determine the scope of the paper’s equilibrium-learning guarantee beyond the selected tabular experiments. This is consequential because approximation of target-game Nash equilibria is the paper’s central objective.

Weakness 2

  • Section 5 compares cMG-DICE with independent learners receiving fixed shadow rewards. However, these baselines also differ in their treatment of opponents and in whether regularization is applied to marginal or joint occupancies. Giving an independent learner the final shadow-reward weights learned by cMG-DICE therefore does not isolate whether learning those weights jointly is necessary.

  • The reported improvements support the effectiveness of the complete method relative to the selected baselines, but provide weaker evidence for the specific explanation advanced in Q6. A more informative comparison would retain the same opponent-aware learning procedure and joint regularization while freezing the shadow-reward weights, either at the data-derived values or at the final learned values. Since the proposed method combines closely related existing components, identifying the contribution of the changing shadow reward is important for assessing its significance.

Questions for authors
  • Could the authors state precisely which guarantees apply to the implemented cMG-DICE procedure? In particular, Proposition 1 assumes small regularized exploitability, while Proposition 2 uses exact best responses and, for differing utilities, a gain-threshold condition. Is there a bound incorporating approximate best responses, finite-data estimation, and policy-extraction error? If such a bound is unavailable, can the authors report regularized exploitability or best-response improvement during training to demonstrate how closely the implementation satisfies the theoretical conditions?

  • Can the authors compare cMG-DICE with the same opponent-aware learner and joint-occupancy regularizer, but with shadow-reward weights frozen at the data-derived values? A corresponding comparison using the final learned weights would also help distinguish the difficulty of identifying appropriate weights from the benefit of the underlying joint-occupancy optimization. These comparisons would materially clarify the interpretation of Q6 and the contribution beyond existing DICE machinery.

  • Could the authors clarify whether the returns defining the training utility, shadow-reward updates, deviation learner, and reported exploitability use the same discounting and horizon? The experimental details indicate discounted training but undiscounted episode-level utility evaluation, which can change incentives in an environment with delayed benefits from cleaning. Additionally, since learned best responses provide lower bounds on exploitability, how sensitive are the main comparisons to deviation initialization and training budget? Establishing a consistent target objective and a sufficiently strong deviation search is important for interpreting the reported equilibrium improvements.

3 comments

Dear Reviewer f66q,

We deeply thank the reviewer for the careful reading and the detailed questions. We address them below.

Q1. How the propositions relate to the implemented procedure

Figure 7 (Appendix H) summarizes our answer. It tracks the regularized and target-game exploitability during training for both the exact alternation and the approximate alternation (Algorithms 1 and 2 in Appendix B), on El Farol and on the NoSDE game, a cyclic Markov game. All of our experiments use Algorithm 2: each agent in turn takes one gradient step on its dual (12) and one on weighted behavior cloning, rather than solving its best response exactly. This was described in Appendix F, and we now state it in Section 3.2 to make it explicit. Below, we explain how each proposition relates to Algorithms 1 and 2, with reference to Figure 7.

Proposition 1. As the reviewer notes, Proposition 1 does not show that cMG-DICE reaches a small regularized exploitability. It bounds the target-game exploitability of any joint policy, including the output of Algorithm 2, by its regularized exploitability plus a term proportional to α\alpha. In Figure 7, the gap between the target-game (dashed) and regularized (solid) curves stays within this term at every checkpoint.

Proposition 2. Whether the alternation reaches a small regularized exploitability is the subject of Proposition 2. In the revision, it was extended to cover any continuous utility, not only the welfare family of the submission: every such game is a 2ϵu2\epsilon_u-potential game, where ϵu\epsilon_u measures how far the agents' utilities are from their average. It analyzes a variant of Algorithm 1 in which agents move only on gains above 2ϵu+δ2\epsilon_u+\delta, and guarantees that this variant stops with regularized exploitability at most 2ϵu+δ2\epsilon_u+\delta.

When ϵu\epsilon_u is small, as on El Farol, Algorithm 1 itself, which moves on every gain without the threshold, is sufficient: it reaches an equilibrium of the regularized game (Figure 7). To examine an extreme case, we added the NoSDE game in Appendix H, a cyclic Markov game whose 2ϵu2\epsilon_u spans the full range of the normalized returns. There, the threshold is so high that no exact best response exceeds it, so we ran Algorithm 1, and it can cycle without reducing the regularized exploitability (Figure 7). The approximate alternation (Algorithm 2) resolves this in the same game, as we show below.

Approximate best responses. We agree that a bound accounting for approximate best responses, finite data, policy extraction and function approximation is important, and this work has not covered it. Instead, as the reviewer suggested, we show empirically that Algorithm 2 reduces the regularized exploitability during training: in Figure 7, it brings the regularized exploitability below 0.0020.002 on both games, including the NoSDE game. On Clean Up, where exact best responses are not available, we measure the target-game exploitability with best responses learned by single-agent RL under several settings, to evaluate the exploitability reliably, as described in Q3.

Q2. Separating the contributions of learned shadow rewards and joint regularization

We fully agree with the reviewer. Following the reviewer's suggestion, we kept the opponent-aware learner and the joint regularization of cMG-DICE and froze μ\mu at μD=∇F(JD)\mu^{\mathcal{D}}=\nabla F(J^{\mathcal{D}}) (Table 2, column (vi)). Freezing μ\mu at the final learned values μ∗\mu^{\ast} instead is in effect cMG-DICE itself (column (v)), since the learned μ\mu converges to μ∗\mu^{\ast} at the equilibrium it reaches.

On Clean Up, with the welfare utilities of the paper and the given data, freezing μ\mu leaves the exploitability of cMG-DICE unchanged (8 cells, 3 seeds each), and cMG-DICE remains less exploitable than the independent learners by 0.029±0.0040.029\pm0.004, against 0.031±0.0040.031\pm0.004 with μ\mu learned. In this setting, estimating μ\mu from the data is sufficient, and the improvement over the independent learners comes from the regularization of the joint occupancy rather than of each agent's own.

However, this does not mean that cMG-DICE need not learn μ\mu and can simply estimate it from the data: it depends on how the agents' utilities are given and on the distribution of the dataset. As a counterexample, Appendix I changes the utilities so that every agent triples the weight on one particular agent's return, on the iterated prisoner's dilemma with uniform data. Over ρ∈{1,3}\rho\in\{1,3\} and λ∈{0.25,0.75,1}\lambda\in\{0.25,0.75,1\}, cMG-DICE reaches an equilibrium of the regularized game in all six cells, with target-game exploitability at most 0.0030.003, whereas with μ\mu fixed at μD\mu^{\mathcal D} it reaches none, with target-game exploitability 0.170.17–0.610.61. μD\mu^{\mathcal D} is computed at the equal returns of the uniform data and keeps the favored agent's weight large, whereas the learned μ\mu lowers it as that agent's return grows. We have revised the discussion of Q6 in Section 5 accordingly.

Q3. Consistent target objective and ablations for the deviation search

We agree that a consistent objective and a sufficiently strong deviation search are both crucial for the validity of our results.

Evaluation. Appendix F stated that the evaluation was undiscounted, a typo carried over from an earlier stage of this work, and we have corrected it. The training utility, the shadow-reward updates, the deviation learner and the reported exploitability all use the same return, discounted with γ=0.99\gamma=0.99 over the full 10001000-step episode of Clean Up.

Deviation search. To check whether a stronger deviation would measure a higher exploitability, we ran ablations on the single-agent RL that learns the best response, varying its budget, initialization, seed and entropy bonus on four cells of Table 2 (settings in Appendix F, results in Appendix G). The main comparisons were not sensitive to these choices: taking the maximum over all variations leaves the ranking of the methods unchanged in every re-evaluated cell. The largest increase came from the budget: raising it from the 2×1072\times 10^7 steps of the main text to 10810^8 raised the exploitability by at most 0.0240.024, without changing the ranking.

I thank the authors for their response. The revised version improved both the evidence and the explanation of what the method achieves. I particularly appreciate the controlled comparison and the revised interpretation of the Clean Up results. Some limitations remain, but I would like to increase my score.

Reviewer_ht42OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes cMG-DICE for offline equilibrium computation in games with general concave utilities of joint state-action occupancies. Fenchel and Lagrangian duality transform each regularized best response into a minimization over a shadow reward and a Bellman flow multiplier. The analysis relates regularized-game exploitability to target-game exploitability and studies exact best-response dynamics for a particular utility family. Experiments on three tabular games and Clean Up evaluate the method across different target utilities, with additional tabular studies examining the effect of policy initialization on equilibrium selection.

Critical strengths
  1. The paper formulates the offline learning problem as a regularized optimization problem and proposes cMG-DICE for approximating Nash equilibria in convex Markov games using only offline logged data. Its theoretical analysis also clarifies the effect of regularization and provides a bound relating regularized game exploitability to target game exploitability.
  2. Experiments on tabular games and Clean Up demonstrate the flexibility of reusing offline datasets under varying utilities. The tabular studies provide additional insight into how initialization influences equilibrium selection.
Critical weaknesses
  1. The convergence analysis of the proposed algorithm is limited in scope. Proposition 2 analyzes exact best-response dynamics only for the specific utility family defined in Eq.(13). It does not establish convergence guarantees for general classes of concave utilities supported by the framework.
Questions for authors
  1. See weaknesses above. Would the convergence analysis extend to other utility classes under explicit structural assumptions? Further theoretical analysis of the algorithm would strengthen the theoretical foundations of the proposed method.
1 comment

Dear Reviewer ht42,

We thank the reviewer for the careful reading and the precise question. We agree that stating Proposition 2 only for the family (13) in the submission ((14) in the revision) understated its scope: most of the derivation does not depend on the form of this family, so it can be extended to the general continuous concave utilities of convex Markov games. To make this clear, we have revised the first half of Section 4.1 (in blue), with two changes.

  1. Generality. Proposition 2 is now stated for general utilities. Their structure enters only through the largest externality ϵu:=max⁡isup⁡d∣ui(d)−uˉ(d)∣\epsilon_u:=\max_i\sup_d|u_i(d)-\bar u(d)|, where uˉ\bar u is the average utility, and alternating exact best responses that move only on gains above 2ϵu+δ2\epsilon_u+\delta stop with regularized exploitability at most 2ϵu+δ2\epsilon_u+\delta. When all agents share one utility, ϵu=0\epsilon_u=0 and no threshold is needed, and (14) is treated as an example in Appendix C.
  2. Readability. We revised the writing of the section so that the two propositions connect clearly: Proposition 1 bounds the target-game exploitability given the exploitability in the regularized game, and Proposition 2 bounds the latter in terms of the agents' utilities.

While the full details are in the revised paper, we would be glad to elaborate on Proposition 2 upon request.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.