acceptodds
Under review as a conference paper at ICLR 2027

Span-Based Analysis of Distributionally Robust Average-Reward Markov Games

Abstract

We study finite distributionally robust Markov games under the average-reward criterion, where each player evaluates the worst-case average-reward of policies against a player-specific, state–joint-action rectangular ambiguity set. We introduce the uniform optimal-response bias span and develop studies on both equilibrium existence and learning guarantees in terms of this single parameter. Firstly, we show under different chain structures and uncertainty sets, and that a finite guarantees the existence of a stationary statewise robust average-reward Nash equilibrium. We then establish the convergence of Nash equilibria under discounted reward to average reward as the discount factor approaching , and develop a reduction framework to connect them. Furthermore, under total-variation ambiguity and balanced nominal generative-model sampling, we show that a model-based discounted learner with any exact discounted Nash oracle uses samples to learn an -robust average-reward Nash equilibrium, where are the state and joint action space sizes, and is the largest next-state support size. This guarantee holds simultaneously for every exact empirical Nash oracle. A matching lower bound on two-player, two-action games further proves the support factor unavoidable for this balanced, every-oracle interface, implying the tightness of our upper bound.

Primary area:
reinforcement learning
Keywords:
robust markov game, average reward

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_VMK1OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors study the uniform optimal-response bias span HRH_R and its effect on the existence of equilibria and the sample-complexity bound in distributionally-robust average-reward Markov games. They show that when this parameter is finite, stationary robust average-reward Nash equilibria exist, and discounted equilibria with γ\gamma sufficiently close to 11 provide ϵ\epsilon-accurate equilibria for the average-reward problem. They provide sufficient conditions for when this HRH_R is finite, so that the analysis applies. They then establish a sample-complexity bound to such equilibria depending on problem parameters such as the state-space size, action-space size, (an upper bound on) HRH_R. A matching lower-bound construction on two-player, two-action games establishes tightness, up to logarithmic factors, for balanced sampling guarantees covering every empirical Nash oracle.

Critical strengths
  1. I think the paper is generally well written and contains several strong theoretical results, although the presentation is somewhat dense. The use of a common span parameter to connect equilibrium existence and learning guarantees is appealing.
  2. I appreciate the lower-bound results, which strengthen the sample-complexity claims by establishing tightness in the stated setting. The distinction between guarantees for every empirical Nash oracle and guarantees for a carefully chosen oracle is also useful.
Critical weaknesses
  1. To my understanding, the analysis around Theorem 3.4 follows a familiar discounted-to-average reduction strategy from related MDP literature. Although extending this argument to robust Markov games may involve additional difficulties, a clearer explanation in the main text of what is technically new in this result would help clarify its contribution.
  2. The main contribution is clearly theoretical, but a small set of rudimentary synthetic experiments could help illustrate how the theoretical sample-complexity bounds relate to observed behavior. In particular, comparing different equilibrium-selection rules would help demonstrate the significance of the every-oracle guarantee. Honestly, I wouldn't say this is a critical weakness, but rather a presentation improvement.
  3. The learning guarantee requires a supplied bound H≥HRH\geq H_R. Theorem 4.2 provides a computable bound when all TV uncertainty radii are strictly positive, but it is less clear how to obtain an admissible HH in the more general cases where finiteness follows from properties of the unknown transition model. Some discussion of how to choose HH, how conservative the available bounds may be, or whether the method could adapt to an unknown span would help clarify its practical applicability.
Questions for authors
  1. Could the discounted-to-average reduction be combined with a model-free learner under the same assumptions? What additional difficulties would arise, and could a comparable sample-complexity guarantee be preserved? What would this entail?
Reviewer_ih72OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies distributionally robust average-reward Markov games under uniform minimum-span control of response bias functions. It establishes equilibrium results without bias uniqueness and a discounted-to-average-reward reduction. For total-variation uncertainty, it gives sample-complexity guarantees for every admissible empirical equilibrium oracle, with a lower bound showing an additional support-size cost that a favorable selector can avoid.

Critical strengths

The handling of data dependence in Lemma G.10 technically useful: it avoids assuming the intermediate span bounds that the analysis needs to establish. Lemma H.12 also realizes adverse choices through actual empirical Nash equilibria, which gives the oracle-uniform guarantee a concrete statistical interpretation.

Critical weaknesses
  1. The independent contribution needs sharper positioning. Uniform span control over opponents appears in Roch and Wang, while minimum-span arguments, the H + σH² dependence, and discounted reductions have close precedents in Yang, Chen, and Chi and related work. There is technical work here, but I had difficulty judging how much the main conclusions advance beyond those ingredients. A direct theorem-level comparison would help me understand the significance of the refinements.

  2. The universal oracle requirement needs stronger motivation. The lower bound assumes balanced sampling and a guarantee for every admissible empirical oracle; a favorable selector avoids the additional cost on the same family. I think this is an interesting distinction, but it limits what the lower bound says about learning algorithms more generally. I would like to understand when an algorithm actually needs this stronger guarantee. The relationship to the empirical-equilibrium guarantees of Subramanian, Sinha, and Mahajan (2023) also needs clarification.

Questions for authors
  1. Could you compare the results with Roch and Wang and with Yang, Chen, and Chi, specifying the new conclusions and obstacles resolved by Theorem 3.3 and Lemma G.10?
  2. How do the guarantees compare with Theorem 3 and Remark 5 of Subramanian, Sinha, and Mahajan (2023), under matched normalization, sampling assumptions, and equilibrium quantifiers?
  3. Which existing planning method or principled equilibrium-selection rule motivates this oracle interface, and when does it meet the Nash-gap requirement?

I think this paper has potential. If the authors can clarify the contribution relative to prior work and provide a convincing motivation for the oracle-uniform guarantee, I would be open to raising my assessment.

References

  • Zachary Roch and Yue Wang. Distributionally Robust Markov Games with Average Reward.
  • Yuepeng Yang, Yuxin Chen, and Yuejie Chi. Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions.
  • Jayakumar Subramanian, Amit Sinha, and Aditya Mahajan. Robustness and Sample Complexity of Model-Based MARL for General-Sum Markov Games.
Reviewer_adUsOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies a span-based analysis of distributionally robust average-reward Markov games. Under a uniformly bounded optimal-response bias span, the authors provides stationary robust Nash equilibrium existence without requiring bias uniqueness and provides a quantitative discounted-to-average reduction. Under total-variation uncertainty and balanced generative-model sampling, it derives a sample-complexity upper bound and a matching lower bound for guarantees that must hold uniformly over all exact empirical discounted Nash oracles on a fixed-action class.

Critical strengths
  1. Removing the bias-uniqueness requirement from the analysis is a substantive improvement over the weak-communication result of Roch and Wang (2026). The argument jointly tracks policies and normalized response values along a vanishing-discount sequence.

  2. The empirical equilibrium selects opponents and continuation values using the same samples that estimate the transition model. The simultaneous concentration event and center-path analysis address this dependence explicitly.

  3. The lower-bound construction shows that an exact empirical equilibrium can generalize poorly under an unfavorable selection rule. The accompanying favorable-oracle construction helps clarify the scope of this phenomenon and provides directions for subsequent algorithm design.

Critical weaknesses
  1. Equilibrium existence and discounted approximation of average-reward equilibria were already studied by Roch and Wang (2026), while the H+σH2H + \sigma H^2 dependence is connected to single-agent results such as Yang et al. (2026). The distinctive contributions are therefore the removal of bias uniqueness and the uniform statistical analysis over data-dependent opponents and equilibrium choices. These are meaningful advances, but the contribution to implementable learning methods is comparatively limited.

  2. The learner can query every state-joint-action pair and obtain the same number of independent samples from each row. Then, the analysis excludes the costs of reaching states, coordinating joint actions, resetting the system, and exploring safely. This is a standard and legitimate theoretical access model, but it does not establish feasibility in environments where data must be collected through sequential interaction. The requirement of a supplied finite bound H≥HRH \ge H_R, uniformly over all stationary opponents, adds another practical limitation.

  3. The appendix appropriately allows an approximate oracle satisfying

    Gap⁡^γ(π^)≤H/4.\widehat{\operatorname{Gap}}_{\gamma}(\hat{\pi}) \le H/4.

    Thus, my concern is not that the theory requires exact computation. Rather, the paper does not instantiate a solver that achieves this tolerance, provide an operational stopping or verification procedure, or evaluate a practical approximate implementation. Abstracting equilibrium computation is reasonable for statistical analysis, but it leaves a substantial gap between the sample guarantee and a usable learning method. Since equilibrium selection is central to the paper, the absence of even a small experiment comparing selection rules and numerical solvers makes the practical relevance of the main phenomenon difficult to assess.

  4. The support-dependent lower bound concerns balanced sampling and guarantees covering every exact empirical oracle. It does not establish that the same dependence is unavoidable for a deliberately designed selection rule or an adaptive learner. Moreover, the joint upper-lower matching is established on a two-player, two-action class. The paper acknowledges these distinctions, but they materially limit the interpretation of the result as a characterization of the general learning problem.

Questions for authors
  1. Can you highlight a representative, nontrivial multiplayer example that is excluded by the previous existence theorem but covered by your result? Relating it to the appendix examples and quantifying its response span would help clarify the significance of the relaxed assumptions.

  2. Which concrete approximate solver would you recommend for the empirical discounted game, and how could its discounted Nash-gap tolerance be checked? I do not expect a complete solution to general-sum equilibrium computation, but a specific instantiation on a tractable subclass would substantially improve the algorithmic interpretation.

  3. Could you provide a controlled experiment comparing favorable and unfavorable selection rules, ideally alongside a numerical solver, using the same transition samples? Reporting the population average-reward Nash gap as a function of sample size or successor-support size would directly illustrate the main claim. A fixed-instance learning curve should be distinguished from the budget-dependent family used in the lower-bound proof.

3 comments
AuthorsOpenReview ↗

Discussion Follow-Up

Dear reviewer,

Thank you again for your detailed reviews. We would appreciate it if you could look at our response before the discussion period closes and let us know if we addressed your concerns or if you still have any. In brief, we clearly discussed the contributions and compared with prior works at theorem-level, developed an implementable planner and develop numerical experiments to verify our claims, and clarified some concerns like scopes of lower bound and how the constant HH can be obtained.

We sincerely appreciate again for your time. If any concern remains, we would be glad to address it during the discussion.

Thank you. Authors

Thank you for the detailed response. The concrete solver, residual certificate, and additional experiments substantially address my concerns about implementation and equilibrium selection. I appreciate the authors’ efforts to address my concerns:

  • Implementation: The planner, residual certificate, and tractable subclass substantially address my concern about implementing the approximate oracle.
  • Experiments: Comparing selectors and a numerical solver on identical datasets directly addresses my request for controlled evidence.
  • Novelty and assumptions: The theorem-level comparisons and separating example clarify the advance over prior work.
  • Lower-bound interpretation: Distinguishing every-oracle guarantees from designed or adaptive learners clarifies the results’ scope.

These additions helped me understand the paper’s significance, especially data-dependent equilibrium selection and guarantees covering different certified solver outputs.

However, my initial concern about the practical significance of the learning guarantee remains. While the analysis controls estimation error under balanced generative sampling, it does not establish how the required coverage can be obtained through actual trajectory-based interaction, or account for the associated collection time and exploration cost. This gap may be particularly consequential in robust games, where rarely visited states or joint actions can matter for worst-case evaluation and unilateral deviations. A finite uniform response span does not itself resolve this issue.

A useful test would compare generative and trajectory-based sampling under the same transition budget, reporting coverage and population Nash gap.

  1. A small, finite-buffer, two-player communication game implemented through the PettingZoo Parallel API would allow a controlled comparison with a known ground-truth transition model.
  2. For broader application-oriented evaluation, ns3-gym provides a networking simulation interface that could be adapted to a multi-agent communication game.
  3. SUMO-RL supports multi-agent traffic-signal control.

Such evidence would help clarify how directly the theoretical guarantee translates into useful equilibrium learning from sequentially collected data.

AuthorsOpenReview ↗

Response to your follow-up

Thank you for confirming that the solver, certificate, and experiments resolve the implementation and selection concerns. We agree that a finite HRH_ {\rm R} does not resolve the remaining point. The revision adds Appendix L (pp. 65–68), whose message is: trajectory data change the sample size of Theorem 5.1 only by a coverage factor, the time the nominal dynamics need to visit every (state, joint action) pair, or row, NN times; the estimation guarantee is otherwise unchanged. We prove both parts, explain why the factor cannot be removed in general, and verify both with the test you proposed.

1. Estimation is unchanged (Theorem L.1(a)). One key difference is that trajectory transitions are not i.i.d.: the row visited next depends on the past. Each visit to a row, however, draws a fresh next state from its nominal distribution, so the trajectory can be generated from pre-drawn i.i.d. sequences, one per row, with the kk-th visit to a row using the kk-th entry. A row's data are then the first KK entries of an i.i.d. sequence, so the dependence enters only through the random, data-dependent visit count KK. A union bound over all prefix lengths makes the concentration step of Theorem 5.1 hold at this random KK, at a logarithmic cost. Hence, under any collection rule, fixed or adaptive, a learner that plans on all observed transitions satisfies Theorem 5.1 once every row has NN visits.

2. The cost is the coverage factor (Theorem L.1(b)–(c)). For a fixed collection rule, coverage takes O~(thitNtot/(SA×))\widetilde O(t_ {\rm hit}N_ {\rm tot}/(SA_ \times)) transitions, where thitt_ {\rm hit} is the largest expected hitting time of a pair. Conversely, from stationarity it needs at least N/(2μmin⁡)N/(2\mu_ {\min}) transitions, where μmin⁡\mu_ {\min} is the smallest stationary frequency of a pair. Since thit≥1/μmin⁡≥SA×t_ {\rm hit}\ge 1/\mu_ {\min}\ge SA_ \times, the factor over the generative budget is of order one only when all rows are visited at comparable rates. Uniform play covers every row if and only if the nominal transition graph is strongly connected, and adaptive collection (GOSPRL, Tarbouriech et al., NeurIPS 2021) reduces the factor to the nominal diameter DD.

3. The factor cannot be removed in general (Appendix L.2). Under full-simplex TV balls, every robust expectation contains σmin⁡xv(x)\sigma\min_ x v(x), so the worst state, possibly a rarely visited one, enters every Bellman update; Nash gaps evaluate off-path deviations; and our guarantee covers data-selected profiles. Theorem 6.1 also bounds trajectory learners, which a generative learner can simulate, and its proof needs order A×(H+σH2)/ε2A_ \times(H+\sigma H^2)/\varepsilon^2 samples at each of ⌊S/2⌋\lfloor S/2\rfloor decision states. Coverage thus requires nominal reachability, which HR<∞H_ {\rm R}\lt \infty does not supply: rows of a state that trajectories never reach are never observed, yet nature can move mass there.

4. Empirical verification (Appendix L.3, Table 6, Figure 2). We used a two-transmitter finite-buffer game with a known model (S=16S=16, A×=4A_ \times=4, arrival rate λ\lambda, TV radii of Appendix A); all 6,000 runs use one planner and are certified with C≤10−9C\le10^{-9}. Mean population Nash gaps over 100 data sets (95% intervals in Table 6), with N=Ntot/64N=N_ {\rm tot}/64:

λ\lambdaNtotN_ {\rm tot}generativetrajectory, same budgetrows visited (%)Tcov/NtotT_ {\rm cov}/N_ {\rm tot}trajectory to coverage
0.310240.01590.0144100.02.130.0052
0.340960.00340.0004100.01.710.0009
0.3163840.00020.0000100.01.500.0000
0.210240.01090.011996.213.10.0030
0.240960.00110.004799.911.30.0007
0.2163840.00030.0016100.010.60.0009
0.1510240.00480.019783.271.80.0013
0.1540960.00130.007795.866.70.0008
0.15163840.00080.002999.762.90.0007

Both of our claims are verified. With the extra transitions needed for coverage, the trajectory's gap is at most the generative one in eight of nine settings. Its collection time Tcov/NtotT_ {\rm cov}/N_ {\rm tot} is within 12% of the predicted factor 1/(SA×μmin⁡)=1.351/(SA_ \times\mu_ {\min})=1.35, 10.010.0, and 58.758.7 at N=256N=256. At equal budgets, the factor appears as a gap penalty when full buffers are rare (λ=0.15\lambda=0.15), but not when visitation is nearly uniform (λ=0.3\lambda=0.3).

In summary, our guarantees are modular: the reduction (Theorem 3.4) holds for every stationary profile however it is computed, the statistical step for every certified solver and collection rule once all rows are covered, and only the collection time depends on how the data are collected. We bound it but do not optimize exploration, as it will require online regret-typed analysis and is far beyond the scope of our paper.

If this resolves your remaining concern, we would be grateful if you would reconsider your assessment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.