acceptodds
Under review as a conference paper at ICLR 2027

Independent Reinforcement Learning in Discounted Markov Games

Abstract

In this work, we study radically uncoupled learning in discounted general-sum Markov games. Assuming “ for ", we show that, for every fixed discount factor, there is no polynomial-time algorithm for computing inverse-polynomially accurate coarse correlated equilibria in discounted general-sum Markov games when players learn independently in decentralized settings. Complementing this hardness result, we present what appears to be the first radically uncoupled algorithm that achieves sub-exponential convergence to coarse correlated equilibria in discounted general-sum Markov games, without imposing any structural assumptions on the game, under both full-feedback and partial-feedback settings. Our approach builds on a layered variant of optimistic mirror descent, equipped with an increasing step-size schedule designed to address the multi-agent setting.

Primary area:
learning theory
Keywords:
Learning in games, General-sum Markov games, Multi-Agent Systems

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_YqNDOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies radically uncoupled learning in general-sum Markov games, with regret measured against history-dependent deviations. The authors propose layered optimistic mirror descent with smoothed entropy and different learning rates across the horizon. They establish a finite-horizon average-regret rate of order T−3/(3H+1)T^{-3/(3H+1)} and extend the result to trajectory feedback under a reachability assumption. Truncation gives a quasi-polynomial iteration bound for discounted games at a fixed discount factor; the trajectory sample bound also depends on reachability. The paper gives an ETH-for-PPAD hardness result for sufficiently accurate sparse mixtures of product Markov policies and includes small numerical examples.

This paper investigates fully uncoupled learning in general-sum and Markov games, where regret is measured against history-dependent deviations. The authors propose a layered optimistic mirror descent method that incorporates smoothed entropy and employs time-varying learning rates. They establish an average regret bound for a finite time horizon of order T−3/(3H+1)T^{-3/(3H+1)} and extend these results to the setting of trajectory-based feedback under a reachability assumption. For discounted games with a fixed discount factor, a truncation approach yields a quasi-polynomial iteration complexity bound; the sample complexity for trajectory-based feedback also depends on the reachability assumption. Furthermore, the paper gives an ETH-for-PPAD hardness result for sufficiently accurate sparse mixtures of product Markov policies and includes small numerical examples.

Critical strengths

The paper studies an important problem, and I find the computational lower-bound result particularly interesting. I also appreciate the attempt to characterize both the achievable convergence guarantees and the computational limitations of independent learning in discounted Markov games.

Critical weaknesses
  1. The interpretation of the hardness result seems broader than what Theorem 4 formally establishes. Theorem 4 fixes a support exponent CC and then chooses a sufficiently large accuracy exponent K=K(γ,C)K=K(\gamma,C). However, the conclusion states that there is no polynomial-time algorithm for computing CCE in discounted general-sum Markov games, and lines 463–464 suggest that quasi-polynomial time is essentially the best one can hope for. I do not see how these stronger claims follow from the theorem as stated.

    In particular, consider an algorithm whose running time is polynomial in both the game size and 1/ε1/\varepsilon. The number of profiles in its output could also depend polynomially on both quantities. After setting ε=∣G∣−K\varepsilon=|G|^{-K}, the corresponding support exponent may depend on KK, whereas Theorem 4 chooses KK after fixing CC. It is therefore unclear to me how the stated result rules out such an algorithm. The restriction to sparse distributions over product Markov profiles is also important.

    I am not sure whether I am missing an additional argument, or whether the issue is mainly with the interpretation of the result rather than the proof itself. I would appreciate clarification on this point, particularly since the hardness result is one of the main contributions of the paper.

  2. Some assumptions and complexity dependencies should be explained more clearly. First, the ETH for PPAD assumption is central to the lower-bound result, but its formal statement only appears in Appendix E.2. I suggest briefly introducing the assumption in Section 4, explaining its role in the reduction, and referring readers to Appendix E.2 for the details.

    Second, the abstract and conclusion should be more explicit about the reachability assumption needed for the partial-feedback result. Definition 7, Theorem 2, and Corollary 2 all state this condition, and the sample complexity bound retains a factor of 1/κ1/\kappa. Since both the truncation horizon and the exploration floor depend on the target accuracy, I think the authors should clarify how κ\kappa is treated as these parameters change. In particular, it is not clear to me whether the claimed quasi-polynomial complexity under partial feedback assumes a uniform lower bound on κ\kappa, or how its dependence on the target accuracy is otherwise accounted for.

Questions for authors

See the "Critical Weakness" Section

2 comments

Thank you for your careful reading and comments.

1. Interpretation of the hardness result.

Thanks for pointing it out, which we agree with. We have changed the scope of the result accordingly, which is weaker than what we had originally claimed. In particular, we agree that our result does not provide a hardness result for a fixed discount factor. Moreover, we have added Corollary 3 in the updated version to address this issue.

2. Presentation of ETH for PPAD.

We have added a brief explanation of ETH for PPAD in Section 4 to give a rough idea of it, and described its role in our reduction result. However, since a complete description of this assumption is rather involved, we have decided to include the complete treatment in Appendix E.2 instead due to the page constraints.

3. Dependence on κ\kappa.

We are thankful to the reviewer for pointing out a gap in our result. We have clarified that the partial-feedback guarantees assume a known positive reachability bound κ\kappa that is independent of the target accuracy. Theorem 2 requires the same κ\kappa across the accuracy-dependent exploration floors. Corollary 2 requires the same κ\kappa truncation horizons and exploration floors for any accuracy parameter ε\varepsilon.

Dear Reviewer, We hope our clarifications and additional changes have addressed your concerns. As the discussion period is nearing its end, we would appreciate it if you could review our responses.

Thank you again for your time and feedback. We would be happy to address any remaining concerns!

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

This paper studies uncoupled learning in discounted general-sum Markov games. In this setting, each player is fully independent, i.e., players cannot observe the other players' policies, nor can they communicate. The paper aims to have all players achieve small external regret through fully independent learning processes, so that Π^T\hat{\Pi}_T approaches a coarse correlated equilibrium (CCE). Classical V-learning guarantees that an output policy produced after training is close to a CCE, whereas this paper provides online regret guarantees over the training process.

The paper first proposes Layered Optimistic Online Mirror Descent for finite-horizon Markov games. The algorithm uses smaller step sizes in earlier layers and larger step sizes in later layers. This design is very natural. Policies in earlier layers change slowly, while policies in later layers can adjust more quickly, which is a common strategy in RL. The authors then extend the algorithm to partial feedback and, via time-truncation, obtain quasi-polynomial theoretical guarantees in the discounted setting. In addition, the paper proves that if the ETH for PPAD holds, there is no independent learning algorithm that can find a sufficiently accurate CCE in polynomial time for all games of this class.

Critical strengths

The problem studied in this paper is of significant theoretical importance. Each player is fully independent, and the paper considers online regret, which increases the difficulty of the problem. The algorithm design is clear and well-motivated. Policies in earlier layers affect the probability of reaching later states, so having earlier layers update slowly and later layers update quickly is a reasonable strategy, and also a common one in RL. The theoretical analysis covers not only full feedback but also partial feedback. Moreover, the paper discusses both upper bounds for the algorithm and computational lower bounds. Overall, it is a fairly complete theoretical work.

Critical weaknesses
  1. The (κ,ζ)(\kappa, \zeta)-reachability assumption in Definition 7 is rather strong. Intuitively, κ>0\kappa > 0 makes the Markov game technically similar to solving a normal-form game at each state one by one.
  2. The experiments are too small in scale. The experiments in Appendix F.2 involve only 2–3 players, each with only 2 actions, and a horizon of only 2–3. Empirical validation on larger-scale experiments would better demonstrate the effectiveness of the algorithm. In addition, the algorithm has many hyperparameters, such as the block length BB, the action-exploration floor ζ\zeta, and others. It would be better to provide a sensitivity analysis of these hyperparameters.
Questions for authors
  1. Is it possible to slightly relax Definition 7 and still obtain convergence guarantees without strictly relying on κ>0\kappa > 0?
  2. Could the effectiveness of the algorithm be validated on larger-scale experiments?
3 comments

We thank the reviewer for the assessment of the theoretical contributions and the suggestions.

1. Reachability assumption.

We agree that Definition 7 is restrictive, but, to the best our knowledge, similar assumptions are common in the current literature (Wei et al., 2021; Erez et al., 2023; Cai et al., 2023). Its role is to ensure sufficient exploration and thereby obtain the stated sample complexity.

The factor κ\kappa can be removed at the cost of exponential dependence on the number of players on the regret bound, which is not tractable in the sense that the bounds we obtain are no longer quasi-polynomial-time in the input variables. This applies to both discounted and undiscounted cases. We also remark that we use the undiscounted case as an intermediate step for our results on the discounted case.

2. Larger-scale experiments.

Following the reviewer's suggestion, we have added finite-horizon congestion games as additional experiments in Appendix F.2.5: the distancing game of Leonardos et al. (2022) and the Markov congestion game of Guo et al. (2026).

We evaluate Algorithm 2 under partial feedback for K=1000K=1000 blocks of B=500B=500 episodes, totaling 500,000500{,}000 episodes per run, with ζ=0.05\zeta=0.05 and η0=0.5\eta_0=0.5. Figure 2 reports averages over five independent runs. The computed upper bound on the CCE gap verifying our theoretical results.

Dear Reviewer, We hope our clarifications and additional experiments have addressed your concerns. As the discussion period is nearing its end, we would appreciate it if you could review our responses.

Thank you again for your time and feedback. We would be happy to address any remaining concerns!

Thank you for your response. I think the clarification about reachability assumption and additional experiments are clear. I will maintain the rating

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

The paper is studying independent general-sum Markov games , i.e there is no communication and shared randomness among the players, under both finite horizon and discounted settings. The objective is to achieve no external regret guarantees for each player (CCE), where the deviation set is all history-dependent policies. Previous work (Foster et al) showed epsilon-regret bound is not possible in a polynomial number of iterations (polynomial in epsilon, size of the game, and horizon of the MDP)

The paper proposes an algorithm that via self-play, it converges to the set of CCEs in the rate of O(T−3/(3H+1))O(T^{-3/(3H+1)}), under full informaiton case, i.e. knowing the action-value function. Also, they modify this algorithm for the partial feedback setting and obtain an algorithm converging to a \epsilon-CCE under polynomial dependence on \epsilon and exponential dependence on H. They also transfer the algorithm in the finite horizon to the discounted setting via a truncation of the MDP. Finally, they propose a hardness result that showing that there is no polynomial algorithm for solving the search problem of finding discounted CCE, even under communicatoin and shared randomness among the players. They also show the results on toy Markov games empirically.

Critical strengths
  1. First result in the independent general sum Markov games: To the best of our knowledge, this is the first algorithm with sub-linear regret bound for the general sum MG where the set of deviations is history-dependent policies.

  2. A simple and clean mechanism for choosing increasing layered dependent learning rates in OOMD and the history-level regret decomposition, which allows us to control the occupancy drift of the history-dependent policies.

  3. The computational complexity is polynomial in the number of players, since each player is updating using its own Q function and it is independent.

Critical weaknesses

The main weakness is regarding the limited novelty and the presention of the work:

  1. Novelty: The main structure of the algorithm is from Erez et al 2023 (OOMD with the blocked estimation of Q), also the hardness result is the emebeded result of Foster et all in the discounted setting.

  2. Presentation: There is notable room for improving the presentation. For example, the main novelty of the work which was using increasing learning rates, is not represented in a way that this is the main trick to overcome the history-dependent policies. Also, the results of this paper, the upperbound rates and the lowerbound, are not presented in contrast or in comparison with the previous work to show the value of this work. A table of convergence rates and the assumptions used in the other work would be very useful.

  3. Minor ones:

  • Knowledge of the Q function and The Coverage assumption: I put this in the minor ones becasue it the criticized point is not only regarding this paper, and it has appeared in other works too. Having an exact knowledge of Q function for the learner is a very strong assumption which basically requires to know the other players policy, tranisition kernel. This is in contrast to the motivation of radically independent setting of this work. So the result that is more in the sprit of radically indepence is the partial feedback result, which also needs the strong assumption of reachability. For example the V-learning algorithm (The PAC to regret version of it) does not need this recheability assumption, and its additional assumption of share randomness only at the end of learning would be milder. It would be helpful that this trade of was clarifed in the paper.

  • The paper misdescribes Erez et al. saying it only works in the case that the players do not affect other player's transition which is not true and that is an special case in the other paper.

  • The dependence on (1/1-\gamma) is not mentioned in the discounted setting's theorem/corollary.

Questions for authors

First of all, I would appreciate reading your opinion on the previously mentioned points in the strengths and weaknesses section. However, there is an additional question:

  1. How does the sparsity of your full-information guarantee, Tε=⌈(C/ε)(3H+1)/3⌉=exp⁡(Θ(Hlog⁡(H/ε)))T_\varepsilon=\lceil (C/\varepsilon)^{(3H+1)/3}\rceil=\exp(\Theta(H\log(H/\varepsilon))), compare with the barrier of Foster et al. (2023), under which no polynomial-time algorithm can output a TT-sparse ε\varepsilon-CCE with T<exp⁡(cε2H)T<\exp(c \varepsilon^2H)? Could you discuss on this that why the paper has polinomial dependene in ϵ\epsilon?

Suggestion: In the discounted setting, maybe because we already have \gamma^h, maybe the changing learning rate can exploit this property and get better results.

3 comments

We thank the reviewer for the careful reading and comments.

1. Foundations and additional contributions.

Although we build on results of Erez et al. (2023) and Foster et al. (2023), we extend their analyses by introducing different update schemes on the algorithmic side and by identifying a particular normal-form game under which one can obtain a complexity lower bound. Since in complexity theory the worst-case complexity bounds usually depend on particular constructions, we believe the latter is a sufficient theoretical contribution rather than a trivial incremental result even though we heavily rely on the gadgets introduced by Foster at al.

In particular, on the algorithm side, we decompose the regret over possible histories and controlling the resulting variation using bounded-divergence regularization and increasing learning rates. In contrast, Erez et al. (2025), the corrected version, uses possibly unbounded log-barrier regularization, constant step-sizes and a state-based regret analysis. This allows us to extend Erez et al. results to online external-regret guarantees against all history-dependent deviations, which is not covered by their particular treatment. On the hardness side, we use Foster et al.'s sparse-CCE reduction by relying on their gadgets; but, we identify a particular game under which our hardness result holds. We believe that this identification is non-trivial.

2. Presentation and comparison with prior work.

We have made revisions in Section~2.1 to elaborate further why we have increasing step-sizes when the deviations are allowed to depend on the whole history.

3. Exact QQ-feedback, reachability, and V-learning. Although, lower bounds on transition dynamics are restrictive, they are common in the current literature (Wei et al., 2021; Erez et al., 2023; Cai et al., 2023). Furthermore, we have clarified the tradeoff between our method and V-learning based methods in Appendix A.

4. The version of Erez et al. being compared.

Thank you for pointing out the need to clarify this comparison. Our discussion refers to the corrected 2025 version on arXiv, which points out a substantial technical error regarding their main result. In particular, its addendum explains that their general-transition regret bound cannot hold due to an unjustified step in their proof that cannot be recovered without further assumptions. The independent-transition setting retains an unconditional sublinear-regret guarantee. Our algorithmic contribution is an unconditional sublinear regret under general action-dependent transitions. In particular, our paper concerns unconditional sublinear regret under general action-dependent transitions, compared to the linear regret found in Erez et al. in the same case. We have made changes in the introduction section to emphasize these points.

5. Dependence on the discount factor.

We have made the dependence on the factor 1/(1−γ)1/(1-\gamma) explicit in Corollaries 1 and 2 and in their proofs in Appendices D.1 and D.2.

6. Sparsity and the barrier of Foster et al.

There are two complementary comparisons. First, our full-information theorem guarantees an ε\varepsilon -CCE after

\right)^{H+1/3} \right\rceil$$ episodes, with empirical support at most $T_\varepsilon$. Foster et al.'s Lemma D.4 permits extraction of a $4\varepsilon$ -Nash equilibrium from an $\varepsilon$ -CCE represented by $T$ product Markov profiles when \$ T<\exp\left(\frac{H\varepsilon^2}{16}\right).\$ Our stated constant satisfies $$C_*^{\mathrm{SE}}(H) \ge 12mH^3A_{\log} \ge 12\log 2>8, \qquad A_{\log}:=\max_i\log(|A_i|+1)$$ for a particular construction. Consequently, for $H\ge1$ and $0<\varepsilon\le1$ , $$T_\varepsilon \ge \left( \frac{C_*^{\mathrm{SE}}(H)}{\varepsilon} \right)^{H+1/3} > 8^H > \exp\left(\frac{H\varepsilon^2}{16}\right).$$ Thus, our upper-bound guarantee is not contained within their sparsity threshold. Second, Algorithm 1 runs in super-polynomial time on the class introduced by them. Using the notation of their proof of Theorem 3.2 and assumptions, $n$ bounds the Markov-game encoding size as $$T_\varepsilon = \exp\bigl(\Theta(\sqrt n\log n)\bigr) = n^{\Theta(\sqrt n)}.$$ It consequently does not provide the polynomial-time sparse-CCE computation that, through their reduction, would imply polynomial-time computation of the underlying Nash equilibrium. The polynomial dependence of the upper bound of $T_{\varepsilon}$ on $1/\varepsilon$ holds only for a given fixed horizon length (with degree $H+1/3$ ). Thus, it is not a polynomial guarantee in the encode size of the Markov game and $\frac 1\varepsilon$. **7. Exploiting discounting in the step-size schedule.** We thank the reviewer for this suggestion.

Dear Reviewer, We hope our clarifications and additional changes have addressed your concerns. As the discussion period is nearing its end, we would appreciate it if you could review our responses.

Thank you again for your time and feedback. We would be happy to address any remaining concerns!

We thank the authors for their detailed response and the revised manuscript.

  • Erez et al. We appreciate the clarification. Our comment was based on the ICML 2023 version; in light of the 2025 addendum, the paper’s description is accurate, and we withdraw this point. This also changes our assessment of the contribution. As far as we can tell, Theorem 1 now provides the only unconditional sublinear-regret guarantee for independent learning in general-sum Markov games with action-dependent transitions, and it holds against history-dependent deviations. The components that fail in Erez et al. (bounded divergence on the decision set combined with path-length control) are precisely those this paper handles differently. However one small correction to the response: the addendum states that the corrected bound contains an execution-dependent term that cannot be bounded in general. This reflects the absence of a guarantee rather than a demonstration of linear regret, so we would avoid describing their result as “linear regret.”

  • Hardness. We still view the lower bound as a fairly direct extension of Foster et al. (2023). Their Corollary 3.4 already combines ETH for PPAD with Rubinstein’s (2016) hard instances in the finite-horizon setting, so the choice of source game is not new in itself; the main additions are the discounted embedding and the new Corollary 3. We appreciate that the revision now clearly states that Corollary 3 does not establish the optimality of the upper bound.

  • Sparsity and the barrier of Foster et al. Thank you; this answers our question.

  • Other points. We confirm that the 1/(1−γ)1/(1-\gamma) dependence is now explicit. The added discussions of the step-size schedule (Section 2.1) and of the trade-off with V-learning (Appendix A) are helpful.

  • Suggestions.

  1. We still recommend adding the comparison table we suggested earlier, covering rates, deviation classes, feedback models, and assumptions for V-learning, SPoCMAR, Erez et al. (2023/2025), the stage-based OFTRL methods, and this work. We believe it would help readers place the contribution, especially given the changed status of Erez et al.
  2. Minor (writing): The formal statement of Theorem 4 (Appendix E.5) asserts that “there exists a discounted two-player general-sum Markov game such that no polynomial-time algorithm solves” the problem. Since hardness is a statement about a family of instances, we suggest restating it over the family {F~H(n),γ(M^)}\{\tilde F_{H(n),\gamma}(\hat M)\} and tidying the opening of the proof (“Suppose not. Take KK … that violates the running hypothesis”).

In light of the revision and the clarification regarding Erez et al, we are raising our score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.