Paper deep dive
Independent Reinforcement Learning in Discounted Markov Games
Asrin Efe Yorulmaz, Ugur Aydin, Tamer Basar
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 9/2/2026, 4:55:44 AM
Summary
This paper investigates independent (radically uncoupled) reinforcement learning in discounted general-sum Markov games. It establishes a computational hardness result assuming ETH for PPAD, proving that no polynomial-time algorithm can compute inverse-polynomially accurate coarse correlated equilibria (CCE) in this setting. Complementing this, the authors propose a layered variant of optimistic mirror descent with an increasing step-size schedule that achieves sub-exponential convergence to CCE for both full-feedback and partial-feedback scenarios, without structural restrictions on the game.
Entities (7)
Relation Signals (6)
Optimistic Mirror Descent → providesguaranteefor → Sub-exponential Convergence
confidence 96% · provide what appears to be the first radically uncoupled algorithm with sub-exponential convergence guarantees
Discounted General-Sum Markov Games → hascomputationalcomplexity → PPAD-hard
confidence 95% · computing stationary Markov-CCEs in discounted general-sum stochastic games is PPAD-hard
Optimistic Mirror Descent → isappliedto → Discounted General-Sum Markov Games
confidence 95% · Our algorithm is a layered variant of optimistic mirror descent... in discounted general-sum Markov games
Radically Uncoupled Learning → isincompatiblewith → Polynomial-time CCE Computation
confidence 94% · there is no polynomial-time algorithm for computing inverse-polynomially accurate coarse correlated equilibria... when players learn independently
Full-Feedback → supports → Sub-exponential Convergence
confidence 92% · establish sub-exponential convergence guarantees for each case [full-feedback and partial feedback]
Partial Feedback → supports → Sub-exponential Convergence
confidence 92% · establish sub-exponential convergence guarantees for each case [full-feedback and partial feedback]
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In this work, we study radically uncoupled learning in discounted general-sum Markov games. Assuming ``$\mathsf{ETH}$ for $\mathsf{PPAD}$", 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 provide what appears to be the first \emph{radically uncoupled} algorithm with sub-exponential convergence guarantees to coarse correlated equilibria in discounted general-sum Markov games without imposing any structural restrictions on the game. Our algorithm is a \emph{layered} variant of optimistic mirror descent with an increasing step-size schedule tailored to the multi-agent setting. Finally, we develop both full-feedback and partial feedback versions of the aforementioned algorithm and establish sub-exponential convergence guarantees for each case.
Tags
Links
- Source: https://arxiv.org/abs/2609.00504v1
- Canonical: https://arxiv.org/abs/2609.00504v1
Trouble viewing inline? Open PDF directly →
Full Text
224,554 characters extracted from source content.
Expand or collapse full text
Independent Reinforcement Learning in Discounted Markov Games Asrın Efe Yorulmaz Note: Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign, Urbana, IL, 61801, USA, ay20@illinois.edu Uğur Aydın Note: Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign, Urbana, IL, 61801, USA, uaydin2@illinois.edu Tamer Başar Note: Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign, Urbana, IL, 61801, USA, basar1@illinois.edu Abstract In this work, we study radically uncoupled learning in discounted general-sum Markov games. Assuming “ ETH for PPAD”, 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 provide what appears to be the first radically uncoupled algorithm with sub-exponential convergence guarantees to coarse correlated equilibria in discounted general-sum Markov games without imposing any structural restrictions on the game. Our algorithm is a layered variant of optimistic mirror descent with an increasing step-size schedule tailored to the multi-agent setting. Finally, we develop both full-feedback and partial feedback versions of the aforementioned algorithm and establish sub-exponential convergence guarantees for each case. 1 Introduction Multi-agent reinforcement learning (MARL) studies how multiple decision-making agents learn and act in a shared environment, where each agent seeks to optimize its own objective while adapting to the behavior of others (Buşoniu et al., 2008; Zhang et al., 2021). This framework has become a central modeling paradigm for large-scale decision-making systems involving both cooperation and competition. Its recent applications range from strategic game playing—including Go, poker, Stratego, and Diplomacy (Silver et al., 2016; Brown and Sandholm, 2018; Perolat et al., 2022; Kramár et al., 2022; Bakhtin et al., 2022)—to large language models (Park et al., 2025; Wan et al., 2025), robotics (Levine et al., 2017), quantitative finance (Zhang et al., 2024), intelligent transportation (Shalev-Shwartz et al., 2016), cybersecurity (Malialis and Kudenko, 2015), and economic policy design (Zheng et al., 2022). These applications motivate algorithms that are not only computationally and statistically efficient, but also robust to decentralization, limited information, and strategic non-stationarity. The standard mathematical model for the theoretical study of MARL is stochastic games, also known as Markov games (Shapley, 1953; Littman, 1994). In a Markov game, interaction unfolds over a sequence of states. At each state, all players choose actions simultaneously; each player receives a reward depending on the current state and the joint actions; and the next state is drawn from a transition kernel that also depends on the joint actions. Thus, Markov games extend Markov decision processes (MDPs) to multi-agent environments, while also extending normal-form games to dynamic environments with state-dependent rewards and transitions. This combination creates difficulties that are absent from each of these two special cases. In contrast to single-agent MDPs, the value of a player’s policy depends on the policies chosen by the other players, and thus optimality must be replaced by an equilibrium notion. In contrast to normal-form games, a player’s current action affects not only her immediate reward, but also the future state distribution on which later strategic interactions take place. Consequently, equilibrium computation in Markov games combines the fixed-point nature of equilibrium computation in normal-form games with the intertemporal structure of dynamic decision-making. In this work, we focus on a fully decentralized information model for MARL, namely independent or radically uncoupled learning (Foster et al., 2023; Foster and Peyton, 2006). We study this model in the discounted setting, which is widely used in the control and reinforcement learning literatures for a variety of purposes (Daskalakis et al., 2023; Tessler et al., 2019; Huang et al., 2026; Pérolat et al., 2017; Sayin et al., 2021). Here, radically uncoupled refers to the restriction that players are not allowed to observe one another’s policies, losses, value functions, or random bits. In particular, there is no available shared randomness, communication, policy revelation, or correlation device during learning. Consequently, each player updates her policy using only her own feedback and treats the effect of the other players as part of the environment. Independent learning dynamics are attractive because they scale without the communication and synchronization overhead required by centralized coordination. For instance, in large-scale systems, repeatedly aggregating global information or coordinating agents through a central learner can be costly and or infeasible under bandwidth, latency, or privacy constraints Lian et al. (2017). Moreover, these informational restrictions also rule out many of the mechanisms used in existing results for equilibrium computation in Markov games (Bai et al., 2020; Wei et al., 2021; Jin et al., 2023), thereby motivating the study of equilibrium computation under decentralized information structures. Beyond asymptotic convergence, one typically seeks algorithms that reach an approximate equilibrium with controlled computational cost and sample complexity, for example with polynomial or quasi-polynomial dependence on the natural problem parameters. To achieve these finite-time computational guarantees, centralized or communication-based methods often rely on shared value estimates, policy information, or coordinated equilibrium-computation subroutines. In contrast, under radically uncoupled information, each player must both compute and statistically estimate her update using only her own local feedback. Therefore, the main challenge in the independent learning setting is not merely to design a convergent learning dynamic, but to obtain convergence with meaningful computational and statistical efficiency under radically uncoupled information. For these reasons, in this work we investigate the following question: Are there (quasi-)efficient, radically uncoupled learning algorithms for approximate equilibrium computation in discounted general-sum Markov games? In normal-form games, the connection between independent learning mechanisms and equilibrium computation is well understood, as independent learning reduces naturally to no-regret learning in this setting: if all players have vanishing external regret, then their average play converges to a coarse correlated equilibrium (CCE), and if all players have vanishing swap regret, their average play converges to a correlated equilibrium (CE) (Hannan, 1957; Hart and Mas-Colell, 2000; Cesa-Bianchi and Lugosi, 2006; Blum and Mansour, 2007). Moreover, it has been shown that optimistic and regularized learning dynamics yield faster self-play rates in normal-form games (Daskalakis et al., 2011; Syrgkanis et al., 2015; Daskalakis et al., 2021; Anagnostides et al., 2022; Soleymani et al., 2025). In contrast, the relationship between independent learning dynamics and equilibrium computation in Markov games remains much less understood. For two-player zero-sum Markov games there is a substantial body of work on decentralized learning, including settings with limited shared information and radically uncoupled algorithms with provable guarantees (Bai et al., 2020; Wei et al., 2021; Cai et al., 2023; Chen et al., 2024). Naturally, general-sum Markov games are expected to be more challenging, as there is no common value function or saddle-point structure. The challenge lies not only in the general-sum strategic interactions among multiple players, but also in the dynamic nature of the environment. The unilateral alternative policies may induce a different distribution over future states, and this state distribution depends jointly on the deviating player’s policy, the transition dynamics, and the policies used by the other players. Since the opponents may also change their policies over time, these comparison distributions are themselves time-varying and unknown to players. This is a central obstruction to transferring the standard normal-form no-regret argument directly to Markov games. The existing positive results for general-sum Markov games typically rely on coordination or post-processing mechanisms that are not present in the independent learning problem considered in this paper (Arslan and Yüksel, 2017; Jin et al., 2023; Song et al., 2022; Mao and Başar, 2023; Daskalakis et al., 2023). A frequently studied class of algorithms include V-learning and related sample-based algorithms (Jin et al., 2023; Song et al., 2022; Mao and Başar, 2023), which compute CCE or CE policies in decentralized MARL. The equilibrium policies produced by these methods are represented as carefully specified distributions over the learning history and require the players to sample a common index from that history during execution. Notably, the learning phase of these algorithms does not provide any online regret guarantees. Thus, while these methods are decentralized, they do not address the radically uncoupled online-regret objective considered in this paper. Being another closely related algorithm, the so-called SPoCMAR (Daskalakis et al., 2023) is a decentralized algorithm with polynomial sample and computational complexity for learning a nonstationary Markov-CCE, but the provided regret guarantees rely on the existence of common random bits during learning and for sampling the output policy, where Markov-CCE is an equilibrium with respect to the Markov policy deviations. Consequently, these works do not provide online regret guarantees for the independently played product policies during the learning process. Another closely related precursor to our work is Erez et al. (2025). Similar to our work, they study radically uncoupled learning in finite-horizon general-sum Markov games in the self-play setting. Their work, compared to ours, contains further restrictions. First, their regret bounds are obtained with respect to Markov policies, whereas our results allow non-Markov history-dependent policies. Second, their sublinear regret guarantee is obtained when agents may affect one another’s losses but not one another’s transition dynamics. In contrast, we study finite- and infinite-horizon discounted Markov games with action-dependent transition kernels and aim to develop radically uncoupled learning algorithms with online regret guarantees against non-Markov history-dependent deviations. On the other hand, there exist hardness results that demonstrate limitations in finding efficient algorithms for the MDPs and Markov games. In the single-agent case, no-regret learning in adversarially changing MDPs can be computationally intractable (Abbasi-Yadkori et al., 2013). Naturally, this intractability also arises in Markov games with adversarial opponents, where both computational and statistical barriers are known (Liu et al., 2022; Tian et al., 2021). More recently, motivated by the fact that computing Nash equilibria is PPAD-complete in normal-form games (Daskalakis et al., 2009), it has been shown that similar hardness constraints can persist in Markov games (Daskalakis et al., 2023; Foster et al., 2023). In particular, computing stationary Markov-CCEs in discounted general-sum stochastic games is PPAD-hard (Daskalakis et al., 2023). Moreover, in finite-horizon general-sum Markov games, any independent learning algorithm that achieves no regret property is also PPAD-hard (Foster et al., 2023). In contrast, we seek nonstationary policies that approximate CCE in discounted Markov games while avoiding the intractability barriers described above in the self-play setting, which complements the existing literature. Our contributions in this paper can be summarized as follows. 1. In Section 3, we first study finite-horizon general-sum Markov games under full-feedback. We introduce a layered smoothed-entropy optimistic-online-mirror-descent (OOMD) algorithm, with an increasing step-size schedule (Algorithm 1). Then, we show that this algorithm achieves an (T−3/(3H+1))O\! (T^-3/(3H+1) ) -approximate CCE with respect to history-dependent deviations after T episodes (Theorem 1). Then, when the underlying model is unknown to agents, in Subsection 3.2, under a reachability notion (Definition 7), we prove a high-probability finite-horizon CCE guarantee with the same exponential-in-horizon dependence up to the polynomial terms (Theorem 2). 2. In Section 4, we transfer the finite-horizon guarantees established in Section 3 to discounted Markov games (Theorem 3). Unlike the undiscounted case, in the discounted case our algorithms yield quasi-polynomial-time and quasi-polynomial-sample guarantees for computing inverse-polynomially accurate sparse discounted CCEs for the full-feedback and partial feedback cases for both finite-horizon and infinite-horizon Markov games (Corollaries 1 and 2). These quasi-polynomial results rely on a horizon length truncation and approximation error bounding arguments to reduce the error bound (T−3/(3H+1))O\! (T^-3/(3H+1) ) to a quasi-polynomial one. 3. In Section 5, we complement the quasi-polynomial upper bounds established in Section 4 for learning discounted-CCE with a complexity-theoretic lower bound. In particular, assuming the “ ETH for PPAD” (Babichenko et al., 2016), we show that for every fixed discount factor γ∈(0,1)∩ℚγ∈(0,1) and every polynomial support bound, there exists an inverse-polynomial accuracy level for which no polynomial-time algorithm can compute a sparse approximate CCE in finite horizon or infinite horizon discounted general-sum Markov games (Theorem 5, Corollary 3) i.e., when players learn independently in a decentralized setting, one cannot calculate approximate CCE in polynomial time. 2 Preliminaries and Notations 2.1 Notations For an integer q≥1q≥ 1, we write [q]:=1,…,q.[q]:=\1,…,q\. For a finite set X, we let Δ(X) (X) denote the probability simplex over X. For a vector x∈Δ(X)x∈ (X), x(a)x(a) denotes the probability of occurrence of action a. All logarithms are natural base unless otherwise stated. In the computational statements, every input object is represented by a finite binary string. 2.2 Undiscounted Finite-horizon Markov games Let m be a positive integer. An m-player finite-horizon Markov game is specified by the tuple G=(H,Shh=1H+1,Aii=1m,Phh=1H,ℓhii∈[m],h∈[H],s1).G= (H,\S_h\_h=1^H+1,\A_i\_i=1^m,\P_h\_h=1^H,\ _h^i\_i∈[m],h∈[H],s_1 ). We will denote by ℳ=[m]M=[m] the set of players. The components of the the Markov game are defined as follows: • Horizon length is denoted by H∈ℕ+H _+. • We denote the finite set of states at layer h by ShS_h. The initial state is deterministic and we denote the initial state by s1s_1. The layer H+1H+1 is terminal and has no actions or costs. We write :=⨆h=1H+1ShS:= _h=1^H+1S_h , and S:=||S:=|S|. • The action set of player i∈ℳi is denoted by AiA_i, which we will assume to be finite. The joint action space of all players will be denoted by A:=∏i=1mAi.A:= _i=1^mA_i. We write joint actions of the players as =(a1,…,am)∈A, a=(a_1,…,a_m)∈ A, and write −i:=(aj)j≠i∈A−i:=∏j≠iAj a_-i:=(a_j)_j≠ i∈ A_-i:= _j≠ iA_j for the action profile that excludes the action of player i. By Amax:=maxi∈[m]|Ai|,A_ := _i∈[m]|A_i|, we will denote the maximum available cardinality among all players. • For any given h∈[H]h∈[H], by Ph:Sh×A→Δ(Sh+1)P_h:S_h× A→ (S_h+1) we denote the (state) transition probability kernel of all players. The quantity Ph(s′∣s,)P_h(s s, a) represents the probability of transitioning to s′∈Sh+1s ∈ S_h+1 from s∈Shs∈ S_h when the joint action is ∈A a∈ A. • For each player i∈[m]i∈[m] and layer h∈[H]h∈[H], the cost function is ℓhi:Sh×A→[0,1]. _h^i:S_h× A→[0,1]. General (non-Markov) policies. For h∈[H]h∈[H], let ℋhH_h denote the set of histories before the layer-h action, ℋh:=S1×A×S2×A×⋯×Sh−1×A×Sh.H_h:=S_1× A× S_2× A×·s× S_h-1× A× S_h. An element of ℋhH_h is written as τh=(s1,1,s2,2,…,sh−1,h−1,sh). _h=(s_1, a_1,s_2, a_2,…,s_h-1, a_h-1,s_h). Furthermore, when needed, we let s(τh)∈Shs( _h)∈ S_h be the concluding state of the history τh∈ℋh _h _h at layer h. A non-Markov policy of player i is a sequence of maps πi=πhih=1H,πhi(⋅∣τh)∈Δ(Ai)for every τh∈ℋh.π^i=\ _h^i\_h=1^H,\; _h^i(· _h)∈ (A_i)\;for every _h _h. Let Πigen _i^gen denote the set of all such finite-horizon policies of player i, and define Πgen:=∏i=1mΠigen. ^gen:= _i=1^m _i^gen. A non-Markov product policy profile is denoted by =(π1,…,πm)∈Πgen. π=(π^1,…,π^m)∈ ^gen. In particular, for player i∈ℳi a general (non-Markov) policy πi∈Πigen _i∈ _i^gen is specified by a collection πi=(π1i,⋯,πHi)π^i=(π^i_1,·s,π^i_H), where πhi:τh→Δ(Ai)π^i_h: _h→ (A_i). Under such a profile, conditional on the history, τh _h, the players’ actions are sampled independently as ahi∼πhi(⋅∣τh),i∈[m],h∈[H].a_h^i _h^i(· _h),\;i∈[m],h∈[H]. Markov policies. A Markov policy of player i is a sequence πi=πhih=1H,πhi(⋅∣s)∈Δ(Ai)π^i=\ _h^i\_h=1^H,\; _h^i(· s)∈ (A_i) for every s∈Sh.for every s∈ S_h. Let Πimarkov _i^markov denote the set of all such finite-horizon policies of player i, and define Πmarkov:=∏i=1mΠimarkov ^markov:= _i=1^m _i^markov to denote the space of product Markov policies, where each agent i independently follows a policy in Πimarkov _i^markov for a given state. In particular, a Markov product policy ∈Πmarkov π∈ ^markov is specified by a collection =(1,⋯,H) π=( π_1,·s, π_H), where h:Sh→Δ(A1)×⋯×Δ(Am). π_h:S_h→ (A_1)×·s× (A_m). At state s∈Shs∈ S_h, it induces the product distribution h(∣s):=∏j=1mπhj(aj∣s),=(a1,…,am)∈A. π_h( a s):= _j=1^m _h^j(a_j s),\; a=(a_1,…,a_m)∈ A. For player i, write −i:=(π1,…,πi−1,πi+1,…,πm) π^-i:=(π^1,…,π^i-1,π^i+1,…,π^m) for the policy profile of all players except i. If ρiρ^i is another policy of player i, either Markov or non-Markov, we write ρi⊙−iρ^i π^-i for the profile obtained by replacing player i’s policy with ρiρ^i and leaving the opponents’ policies equal to −i π^-i. In particular, if ρiρ^i is Markov, then for s∈Shs∈ S_h, (ρi⊙−i)h(∣s):=ρhi(ai∣s)∏j≠iπhj(aj∣s).(ρ^i π^-i)_h( a s):= _h^i(a_i s) _j≠ i _h^j(a_j s). Repeated interaction. The agents interact with environment over T episodes. At the beginning of episode t∈[T]t∈[T], each player i chooses a Markov policy πti _t^i. Let t=(πt1,…,πtm) π_t=( _t^1,…, _t^m) denote the resulting product Markov profile. Each episode starts from st,1=s1s_t,1=s_1. For each h∈[H]h∈[H], player i samples at,hi∼πt,hi(⋅∣st,h),a_t,h^i _t,h^i(· s_t,h), the joint action is t,h:=(at,h1,…,at,hm), a_t,h:=(a_t,h^1,…,a_t,h^m), player i incurs cost ℓhi(st,h,t,h), _h^i(s_t,h, a_t,h), and the next state is sampled as st,h+1∼Ph(⋅∣st,h,t,h).s_t,h+1 P_h(· s_t,h, a_t,h). The feedback observed by each player after the episode depends on the feedback model defined below. Definition 1 (Full-feedback). At the end of episode t, player i observes the exact Qti(s,ai)=Qhi,t(s,ai),∀h∈[H],s∈Sh,ai∈Ai.Q_t^i(s,a_i)=Q_h^i, π_t(s,a_i),\;∀ h∈[H],\ s∈ S_h,\ a_i∈ A_i. Definition 2 (Partial feedback). At the end of episode t, player i observes only its own trajectory information (st,1,at,1i,ct,1i,st,2,at,2i,ct,2i,…,st,H,at,Hi,ct,Hi,st,H+1), (s_t,1,a_t,1^i,c_t,1^i,s_t,2,a_t,2^i,c_t,2^i,…,s_t,H,a_t,H^i,c_t,H^i,s_t,H+1 ), where ct,hi:=ℓhi(st,h,t,h)c_t,h^i:= _h^i(s_t,h, a_t,h). For a policy profile ∈Πmarkov π∈ ^markov, let ℙP π denote the distribution over trajectories induced by the policy profile π and the transition kernels Phh=1H\P_h\_h=1^H, and define VH+1i,≡0.V_H+1^i, π≡ 0. All expectations E π below are taken with respect to this trajectory distribution. For h∈[H]h∈[H], s∈Shs∈ S_h, and i∈[m]i∈[m], we define the value function Vhi,(s):=[∑r=hHℓri(sr,r)|sh=s].V_h^i, π(s):=E π [ _r=h^H _r^i(s_r, a_r)\, |\,s_h=s ]. Similarly, the state-action value is given as Qhi,(s,ai):=−i∼h−i(⋅∣s)[ℓhi(s,)+∑s′∈Sh+1Ph(s′∣s,)Vh+1i,(s′)],Q_h^i, π(s,a_i):=E_ a_-i π_h^-i(· s) [ _h^i(s, a)+ _s ∈ S_h+1P_h(s s, a)\,V_h+1^i, π(s ) ], where the opponents follow the −i π^-i. Therefore, Vhi,(s)=ai∼πhi(⋅∣s)[Qhi,(s,ai)].V_h^i, π(s)=E_a_i _h^i(· s) [Q_h^i, π(s,a_i) ]. For s1s_1, we have Vi,(s1):=V1i,(s1).V^i, π(s_1):=V_1^i, π(s_1). The induced MDP of a player. Fix an episode t, a player i, and the opponents’ policies t−i π_t^-i. Then, player i faces an induced finite-horizon MDP Mti:=(H,Shh=1H+1,Ai,Pt,hih=1H,ℓt,hih=1H,s1),M_t^i:= (H,\S_h\_h=1^H+1,A_i,\P_t,h^i\_h=1^H,\ _t,h^i\_h=1^H,s_1 ), where, for s∈Shs∈ S_h, ai∈Aia_i∈ A_i, and s′∈Sh+1s ∈ S_h+1, ℓt,hi(s,ai):=−i∼t,h−i(⋅∣s)[ℓhi(s,(ai,−i))], _t,h^i(s,a_i):=E_ a_-i π_t,h^-i(· s) [ _h^i (s,(a_i, a_-i) ) ], and Pt,hi(s′∣s,ai):=−i∼t,h−i(⋅∣s)[Ph(s′∣s,(ai,−i))].P_t,h^i(s s,a_i):=E_ a_-i π_t,h^-i(· s) [P_h (s s,(a_i, a_-i) ) ]. For a Markov policy μiμ^i in this induced MDP, define Vt,H+1i,μi≡0V_t,H+1^i,μ^i≡ 0 and, then, we have Qt,hi,μi(s,ai):=ℓt,hi(s,ai)+∑s′∈Sh+1Pt,hi(s′∣s,ai)Vt,h+1i,μi(s′),Vt,hi,μi(s):=ai∼μhi(⋅∣s)[Qt,hi,μi(s,ai)].Q_t,h^i,μ^i(s,a_i):= _t,h^i(s,a_i)+ _s ∈ S_h+1P_t,h^i(s s,a_i)\,V_t,h+1^i,μ^i(s ), V_t,h^i,μ^i(s):=E_a_i _h^i(· s) [Q_t,h^i,μ^i(s,a_i) ]. These induced-MDP quantities agree with the corresponding Markov-game quantities, Vt,hi,μi(s)=Vhi,μi⊙t−i(s),Qt,hi,μi(s,ai)=Qhi,μi⊙t−i(s,ai).V_t,h^i,μ^i(s)=V_h^i,μ^i π_t^-i(s),\;Q_t,h^i,μ^i(s,a_i)=Q_h^i,μ^i π_t^-i(s,a_i). For the actually played policy πti _t^i, we use the shorthand Vt,hi,π(s):=Vhi,πti⊙t−i(s),Qt,hi,π(s,ai):=Qhi,πti⊙t−i(s,ai),s∈Sh.V_t,h^i,π(s):=V_h^i, _t^i π^-i_t(s),\;Q_t,h^i,π(s,a_i):=Q_h^i, _t^i π^-i_t(s,a_i),\;s∈ S_h. Moreover, we drop policy-dependent indices from the value-functions’ notation whenever they are clear from the context. Distributional policies. We will also consider distributions over non-Markov general policies; we refer to such elements of Δ(Πgen) ( ^gen) as distributional policies. Playing a distributional policy P∈Δ(Πgen)P∈ ( ^gen) consists of first sampling a randomized policy ∼P, π P, and then executing the sampled policy π. For any policy ∈Πgen π∈ ^gen, let δ∈Δ(Πgen) _ π∈ ( ^gen) denote the distribution placing unit mass on π. Accordingly, the empirical distribution over the iterates 1,…,T π_1,…, π_T is Π^T:=1T∑t=1Tδt∈Δ(Πgen). _T:= 1T _t=1^T _ π_t∈ ( ^gen). More generally, if ∈Δ(Πgen) P∈ ( ^gen) is a distribution over policy profiles, we define Vi,(s1):=∼[Vi,(s1)].V^i, P(s_1):=E_ σ P [V^i, σ(s_1) ]. Then, for a deviation μi∈Πigenμ^i∈ _i^gen, we let Vi,μi⊙−i(s1):=∼[Vi,μi⊙−i(s1)].V^i,μ^i P^-i(s_1):=E_ σ P [V^i,μ^i σ^-i(s_1) ]. Definition 3 (General-policy external regret). Given product Markov policy profiles 1,…,T π_1,…, π_T, the general-policy external regret of player i is RegTgen,i:=supμi∈Πigen∑t=1T[Vi,t(s1)−Vi,μi⊙t−i(s1)].Reg^gen,i_T:= _μ^i∈ _i^gen _t=1^T [V^i, π_t(s_1)-V^i,μ^i π_t^-i(s_1) ]. Definition 4 (Coarse Correlated Equilibrium). The empirical distribution Π^T=1T∑t=1Tδt _T= 1T _t=1^T _ π_t is an ε -approximate CCE if, for every player i∈[m]i∈[m], supμi∈Πigen[Vi,Π^T(s1)−Vi,μi⊙Π^T−i(s1)]≤ε. _μ^i∈ _i^gen [V^i, _T(s_1)-V^i,μ^i _T^-i(s_1) ]≤ . 2.3 Discounted Markov games We use the same notation for finite and infinite-horizon discounted games. Let H¯∈ℕ+∪∞ H _+∪\∞\ denote the horizon. When H¯<∞ H<∞, an m-player finite-horizon discounted Markov game is specified by Gγ,H¯=(H¯,Shh=1H¯+1,Aii=1m,Phh=1H¯,ℓhii∈[m],h∈[H¯],γ,s1).G_γ, H= ( H,\S_h\_h=1 H+1,\A_i\_i=1^m,\P_h\_h=1 H,\ _h^i\_i∈[m],h∈[ H],γ,s_1 ). When H¯=∞ H=∞, we recover the discounted infinite-horizon Markov game Gγ=(S,Aii=1m,P,ℓii=1m,γ,s1)G_γ= (S,\A_i\_i=1^m,P,\ ^i\_i=1^m,γ,s_1 ) . In both cases, we will denote by ℳ=[m]M=[m] the set of players. Corresponding games are defined as follows. • For horizon H¯ H, we use the convention [H¯]=1,…,H¯,H¯<∞,ℕ+,H¯=∞.[ H]= cases\1,…, H\,& H<∞,\\ N_+,& H=∞. cases • In the finite-horizon case, the state spaces S1,…,SH¯+1S_1,…,S_ H+1 are layer-labeled, and SH¯+1S_ H+1 is terminal. In the infinite-horizon case, we have Sh=S_h=S for all h≥1.h≥ 1. The initial state is deterministic and we denote it by s1s_1. • The set AiA_i is the finite action set of player i∈ℳi . The joint action space is A:=∏i=1mAi.A:= _i=1^mA_i. We write a joint action as =(a1,…,am)∈A, a=(a_1,…,a_m)∈ A, and we write −i:=(aj)j≠i∈A−i:=∏j≠iAj a_-i:=(a_j)_j≠ i∈ A_-i:= _j≠ iA_j. • For each layer h∈[H¯]h∈[ H], the transition kernel is Ph:Sh×A→Δ(Sh+1).P_h:S_h× A→ (S_h+1). In the infinite-horizon case, this reduces to the stationary kernel P:S×A→Δ(S).P:S× A→ (S). • For each player i∈[m]i∈[m] and layer h∈[H¯]h∈[ H], the cost function is ℓhi:Sh×A→[0,1]. _h^i:S_h× A→[0,1]. In the infinite-horizon case, the cost function is ℓi:S×A→[0,1]. ^i:S× A→[0,1]. • The discount factor is γ∈(0,1).γ∈(0,1). General (non-Markov) and Markov policies. For each h≤H¯h≤ H, let ℋhH¯:=S1×A×S2×A×⋯×Sh−1×A×ShH_h H:=S_1× A× S_2× A×·s× S_h-1× A× S_h be the set of histories before the time-h action. When H¯=∞ H=∞, this definition is understood with the convention Sh=S_h=S for every h. An element of ℋhH¯H_h H is written as τh=(s1,1,s2,2,…,sh−1,h−1,sh). _h=(s_1, a_1,s_2, a_2,…,s_h-1, a_h-1,s_h). A non-Markov policy of player i over horizon H¯ H is a sequence of maps μi=μhih≤H¯,μhi(⋅∣τh)∈Δ(Ai)for every τh∈ℋhH¯.μ^i=\ _h^i\_h≤ H,\; _h^i(· _h)∈ (A_i)\;for every _h _h H. Let Πigen,H¯ _i^gen, H denote the set of such policies of player i, and define Πgen,H¯:=∏i=1mΠigen,H¯. ^gen, H:= _i=1^m _i^gen, H. For H¯=∞ H=∞, we also write Πigen,∞ _i^gen,∞ and Πgen,∞ ^gen,∞. A Markov policy of player i over horizon H¯ H is a sequence πi=πhih≤H¯,πhi(⋅∣s)∈Δ(Ai),s∈Sh.π^i=\ _h^i\_h≤ H,\; _h^i(· s)∈ (A_i),\;s∈ S_h. In the infinite-horizon case, as a special case our notion of Markov policies corresponds to non-stationary Markov policies. Let Πimarkov,H¯ _i^markov, H denote the set of such policies of player i, and define Πmarkov,H¯:=∏i=1mΠimarkov,H¯. ^markov, H:= _i=1^m _i^markov, H. For H¯=∞ H=∞, we also write Πimarkov,∞ _i^markov,∞ and Πmarkov,∞ ^markov,∞. Discounted values. For a policy profile ∈Πgen,H¯ σ∈ ^gen, H and a finite L≤H¯L≤ H, define the L-truncated discounted cost of player i by Ji,Lγ():=[∑h=1Lγh−1ℓhi(sh,h)|s1=sinit].J_i,L^γ( σ):=E σ [ _h=1^Lγ^h-1 _h^i(s_h, a_h)\, |\,s_1=s_init ]. The full discounted objective is Ji,H¯γ():=[∑h=1H¯γh−1ℓhi(sh,h)|s1],J_i, H^γ( σ):=E σ [ _h=1 Hγ^h-1 _h^i(s_h, a_h)\, |\,s_1 ], In the infinite-horizon case, we also write Jiγ():=Ji,∞γ().J_i^γ( σ):=J_i,∞^γ( σ). Since 0≤ℓhi≤10≤ _h^i≤ 1, for every profile σ, 0≤Ji,H¯γ()≤∑h=1H¯γh−1≤11−γ.0≤ J_i, H^γ( σ)≤ _h=1 Hγ^h-1≤ 11-γ. For a distribution ∈Δ(Πgen,H¯) P∈ ( ^gen, H) over policy profiles, define Ji,H¯γ():=∼[Ji,H¯γ()].J_i, H^γ( P):=E_ σ P [J_i, H^γ( σ) ]. For a unilateral deviation μi∈Πigen,H¯μ^i∈ _i^gen, H, define Ji,H¯γ(μi⊙−i):=∼[Ji,H¯γ(μi⊙−i)].J_i, H^γ(μ^i P^-i):=E_ σ P [J_i, H^γ(μ^i σ^-i) ]. Then, we define the corresponding discounted CCE and regret notions as follows. Definition 5. For a sequence of H¯ H-horizon product policy profiles ¯1,…,¯T π_1,…, π_T, the discounted general-policy regret of player i is defined as Regγ,H¯,Tgen,i:=supμi∈Πigen,H¯∑t=1T[Ji,H¯γ(¯t)−Ji,H¯γ(μi⊙¯t−i)].Reg_γ, H,T^gen,i:= _μ^i∈ _i^gen, H _t=1^T [J_i, H^γ( π_t)-J_i, H^γ(μ^i π_t^-i) ]. Definition 6. The empirical distribution Π^T _T is an ε -approximate CCE if, for every player i∈[m]i∈[m], supμi∈Πigen,H¯[Ji,H¯γ(Π^T)−Ji,H¯γ(μi⊙Π^T−i)]≤ε. _μ^i∈ _i^gen, H [J_i, H^γ( _T)-J_i, H^γ(μ^i _T^-i) ]≤ . If H¯=∞ H=∞, it is the discounted infinite-horizon CCE. 2.4 Truncated Markov Games Let L≤H¯L≤ H. For a given discounted Markov game Gγ,H¯G_γ, H, we define a corresponding L-step discounted truncation Gγ,H¯[L]G_γ, H^[L] whose one-step cost function is defined as chi(s,):=γh−1ℓhi(s,),h∈[L].c_h^i(s, a):=γ^h-1 _h^i(s, a),\;h∈[L]. The state spaces, action sets, transition kernels, and initial state of Gγ,H¯[L]G_γ, H^[L] are inherited from the original game for layers 1,…,L1,…,L. For an H¯ H-horizon policy μi=(μ1i,μ2i,…,μH¯i),μ^i=(μ^i_1,μ^i_2,…,μ^i_ H), define μi,[L]:=(μhi)h=1L.μ^i,[L]:=(μ^i_h)_h=1^L. That is, μi,[L]μ^i,[L] is the L-step policy obtained by truncating μiμ^i after stage L. We define policy L,ref π^L,ref for the layers after L, in which every player plays uniformly at every state. For an L-step product profile [L] π^[L], let ExtL([L])Ext_L( π^[L]) denote the H¯ H-horizon profile that plays [L] π^[L] during layers 1,…,L1,…,L and then plays L,ref π^L,ref afterward. Finally, define the discounted tail after layer L or truncation error by τL,H¯(γ):=∑h=L+1H¯γh−1≤γL1−γ. _L, H(γ):= _h=L+1 Hγ^h-1≤ γ^L1-γ. 3 Main Algorithm and Results for Episodic Markov Games Let G=(H,Shh=1H+1,Aii=1m,Phh=1H,ℓhii∈[m],h∈[H],s1)G= (H,\S_h\_h=1^H+1,\A_i\_i=1^m,\P_h\_h=1^H,\ _h^i\_i∈[m],h∈[H],s_1 ) be a finite-horizon Markov game. In this section, we establish the undiscounted finite-horizon regret guarantees for G that underlie our later discounted-game results. We consider undiscounted general-sum Markov games within episodic framework in the self-play setting, where the players repeatedly generate product Markov profiles and update their own policies independently. The performance criterion is regret with respect to history-dependent deviations, which, through the standard no-regret-to-CCE connection (Cesa-Bianchi and Lugosi, 2006), yields approximate CCE for the empirical distribution of play. The main obstruction, compared with normal-form games, is that the regret comparison in a Markov game is weighted by the history distribution induced by the policy deviations. A unilateral deviation of policies may change the distribution of future states, and therefore the future decision points at which the deviation is evaluated. Hence, the comparison places more weight on histories that the deviating policy visits frequently and less weight on histories that it reaches rarely. From the learner’s perspective, these history-occupancy weights are unknown and time-varying: they depend on the transition kernel, the deviation being compared against, and the opponents’ evolving policies. Thus, the analysis must control the drift of these unknown weights in addition to the online learning dynamics. We first handle this issue in the full-feedback model, and then extend the argument to the trajectory-level partial-feedback model by introducing value estimation and an exploration floor under a reachability condition. 3.1 Episodic Markov games under full-feedback In this subsection, we present the Layered Optimistic Online Mirror Descent (OOMD) algorithm for the self-play setting in game G (see Algorithm 1) and prove its regret guarantee under full-feedback. The algorithm follows an independent self-play structure: at each player–state–layer tuple (i,s,h)(i,s,h), player i performs a local policy update using the state–action value vector generated by the product Markov profile played in the previous episode. Algorithm 1 Layered Optimistic Online Mirror Descent 1: Input: Finite-horizon game G, horizon H, episode count T, base step-size η0∈ℝ _0 . 2: Define αh:=3(H−h)+13H+1,ηh:=η0T−αh,x¯i(ai):=1|Ai|,λi=1/|Ai|,ai∈Ai,h∈[H]. _h:= 3(H-h)+13H+1,\; _h:= _0T^- _h,\; x^i(a_i):= 1|A_i|, _i=1/|A_i|,\;a_i∈ A_i,h∈[H]. 3: For every i∈[m]i∈[m], h∈[H]h∈[H], and s∈Shs∈ S_h, set x~0,hi,s:=x¯i∈argminx∈Δ(Ai)Ψi(x),Q0i(s,⋅)≡0∈ℝAi. x_0,h^i,s:= x^i∈ *argmin_x∈ (A_i) _i(x),\;Q_0^i(s,·)≡ 0 ^A_i. 4: for t=1,…,Tt=1,…,T do 5: for each player i∈[m]i∈[m], layer h∈[H]h∈[H], and state s∈Shs∈ S_h do ⊳ Optimistic mirror step 6: xt,hi,s=argminx∈Δ(Ai)ηh⟨Qt−1,hi(s,⋅),x⟩+Di(x,x~t−1,hi,s).x_t,h^i,s= *argmin_x∈ (A_i) \ _h\, Q_t-1,h^i(s,·),x +D_i\! (x, x_t-1,h^i,s ) \. 7: Set the played policy at (h,s)(h,s) by πt,hi(⋅∣s)=xt,hi,s(⋅). _t,h^i(· s)=x_t,h^i,s(·). 8: Execute episode t using the t=(πt1,…,πtm). π_t=( _t^1,…, _t^m). 9: Each player i observes Qt,hi(s,ai),∀h∈[H],s∈Sh,ai∈Ai.Q_t,h^i(s,a_i),\;∀ h∈[H],\ s∈ S_h,\ a_i∈ A_i. 10: for each player i∈[m]i∈[m], layer h∈[H]h∈[H], and state s∈Shs∈ S_h do ⊳ Mirror-descent update 11: x~t,hi,s=argminx∈Δ(Ai)ηh⟨Qt,hi(s,⋅),x⟩+Di(x,x~t−1,hi,s). x_t,h^i,s= *argmin_x∈ (A_i) \ _h\, Q_t,h^i(s,·),x +D_i\! (x, x_t-1,h^i,s ) \. The full-feedback setting removes the statistical difficulty of estimating value functions from trajectories, since each player observes the exact vectors Qt,hi(s,⋅)Q^i_t,h(s,·) after every episode. The remaining challenge is therefore purely dynamical: each player’s OOMD updates must be stable enough to control the induced drift of the hidden history-occupancy weights. Algorithm 1 addresses this difficulty by combining a smoothed-entropy regularizer with an increasing layer-wise step-size schedule. Our first design choice is the smoothed entropy function as the regularizer choice. Given a smoothing parameter λi>0 _i>0, the smoothed negative-entropy regularizer over Δ(Ai) (A_i) is defined as Ψi(x):=∑a∈Ai(x(a)+λi)log(x(a)+λi),x∈Δ(Ai). _i(x):= _a∈ A_i (x(a)+ _i ) (x(a)+ _i ), x∈ (A_i). The associated Bregman divergence is Di(x,y)=∑a∈Ai(x(a)+λi)logx(a)+λiy(a)+λi,x,y∈Δ(Ai).D_i(x,y)= _a∈ A_i (x(a)+ _i ) x(a)+ _iy(a)+ _i,\;x,y∈ (A_i). Here, the idea of shift λi _i is reminiscent of the fixed-share smoothing idea used in tracking and adaptive-regret algorithms Herbster and Warmuth (1998); Cesa-Bianchi et al. (2012). To the best of our knowledge, this type of fixed-share idea, implemented through regularizers, was first proposed in Salem et al. (2024), although we use it for a different purpose. In our setting, the shift provides a bounded Bregman divergence on the full simplex and a clean Lipschitz bound, while still allowing the comparator μhi(⋅∣τh)μ^i_h(· _h) to be an arbitrary distribution in Δ(Ai) (A_i). Furthermore, under the choice λi=1/|Ai| _i=1/|A_i|, the upper bound over Di(x,y)D_i(x,y) grows only logarithmically with the action-set size. The second design choice is the increasing step-size schedule. For a given horizon H, defining αh:=3(H−h)+13H+1 _h:= 3(H-h)+13H+1, we set our learning-rate as ηh:=η0T−αh,h∈[H], _h:= _0T^- _h,\;h∈[H], given η0∈(0,1] _0∈(0,1]. Simply, our step-size schedule is designed to make the drift of unknown weights manageable. In particular, the earlier layers use smaller learning rates, and thus their policies move slowly and do not create abrupt changes over later histories. Later layers use larger learning rates, allowing the downstream parts of the game to adapt more quickly by providing them a more stable regime. In a sense, this creates a nested time-scale separation across the horizon as deep layers react faster, while earlier layers remain comparatively stable. Combined with optimism, this schedule turns the problem into a controlled collection of slowly varying weighted online learning problems. This layer-wise schedule is mathematically reminiscent of increasing learning-rate schemes used in adaptive online learning and adversarial bandit/MDP analyses Bubeck et al. (2021); Agarwal et al. (2017); Wei and Luo (2018); Lee et al. (2020), but the motivation and exact schedule here is fundamentally different. In those settings, learning rates increase across episodes to improve exploration by discounting early high-variance loss estimates and avoiding commitment to suboptimal actions. In contrast, our schedule is designed to make the drift of unknown history-occupancy weights manageable. Formally, the performance of Algorithm 1 is provided in the statement below. Theorem 1. Suppose all players run Algorithm 1. Define C∗SE:=maxi∈[m]2Hlog(|Ai|+1)η0+12mH3log(|Ai|+1)+η0H3+144η03m2H7.C_*^SE:= _i∈[m] \ 2H (|A_i|+1) _0+12mH^3 (|A_i|+1)+ _0H^3+144 _0^3m^2H^7 \. Given ϵ∈(0,1]ε∈(0,1], choose Tε:=⌈(C∗SEε)(3H+1)/3⌉.T_ := ( C_*^SE )^(3H+1)/3 . Then, after running Algorithm 1 for TεT_ episodes, for every player i∈[m]i∈[m], RegTεgen,i≤εTε.Reg^gen,i_T_ ≤ T_ . Equivalently, the empirical distribution Π^Tε _T_ is an ε -approximate CCE with respect to all history-dependent deviations. Proof Outline. We provide here an overview of the proof of Theorem 1. The full argument is deferred to Appendix B. The proof follows three main steps. First, the Markov-game regret is rewritten as a sum of local weighted regret terms. Second, the movement of the hidden weights and the movement of the Q-functions are controlled through the stability of the policy sequences. Third, the layer-wise learning-rate schedule is chosen so that all resulting terms have the same order. For a player i and a history-dependent policy μi∈Πigenμ^i∈ _i^gen, let dt,hi,μ∈Δ(ℋh)d_t,h^i,μ∈ (H_h) denote the distribution over histories at layer h, τh _h, generated by μiμ^i and the opponents’ episode-t Markov profile t−i π_t^-i. For each layer h, define the local weighted regret Ri,h(μi):=∑τh∈ℋh∑t=1Tdt,hi,μ(τh)⟨Qt,hi(s(τh),⋅),πt,hi(⋅∣s(τh))−μhi(⋅∣τh)⟩.R_i,h(μ^i):= _ _h _h _t=1^Td_t,h^i,μ( _h) Q_t,h^i(s( _h),·), _t,h^i(· s( _h))- _h^i(· _h) . The weighted value-difference decomposition, Lemma 12, shows that the regret against μiμ^i is exactly ∑t=1T[Vt,hi,π(s1)−Vt,hi,μi(s1)]=∑h=1HRi,h(μi). _t=1^T\!\! [V^i,π_t,h(s_1)\!-\!V^i,μ^i_t,h(s_1) ]\!\!=\!\! _h=1^H\!\!R_i,h(μ^i). Thus, the problem reduces to bounding Ri,h(μi)R_i,h(μ^i) for all h. The first step is the weighted optimistic-online-mirror-descent bound in Lemma 7. Applied to the learner at layer h, and then summed over histories, it leads to a bound of the form Ri,h(μi)≤Bi(1+TVi,hμ)ηh+ηhρi2∑τ∈ℋh∑t=1Tdt,hi,μ(τ)‖Qt,hi(s(τ),⋅)−Qt−1,hi(s(τ),⋅)‖∞2,R_i,h(μ^i)≤ B_i(1+TV_i,h^μ) _h+ _h _i2 _τ _h _t=1^Td_t,h^i,μ(τ) \|Q_t,h^i(s(τ),·)-Q_t-1,h^i(s(τ),·) \|_∞^2, where TVi,hμ:=∑t=1T−1‖dt+1,hi,μ−dt,hi,μ‖1.TV_i,h^μ:= _t=1^T-1 \|d_t+1,h^i,μ-d_t,h^i,μ \|_1. The first term is controlled by the bounded Bregman diameter of the smoothed-entropy regularizer. The second term is where optimism enters: the cost of learning depends on the variation of consecutive Q-functions rather than on their magnitudes. The second step controls the variation of the hidden weights. Regarding the smooth-entropy regularizer, define ρi:=1+|Ai|λi,ρ¯:=maxi∈[m]ρi, _i:=1+|A_i| _i,\; ρ:= _i∈[m] _i, and Bi:=ρilog1+λiλi.B_i:= _i 1+ _i _i. By the proximal Lipschitz property of the smoothed-entropy OOMD update given in Lemma 5, Lemma 8 shows that the one-step movement of player i’s layer-h policy satisfies maxs∈Sh‖πt+1,hi(⋅∣s)−πt,hi(⋅∣s)‖1≤3ρiHηh. _s∈ S_h \| _t+1,h^i(· s)- _t,h^i(· s) \|_1≤ 3 _iH _h. Then, Lemma 9 uses the layered structure of the game to show that the layer-h history weights depend only on policy movement in earlier layers: TVi,hμ≤3mρ¯HT∑ℓ<hηℓ.TV_i,h^μ≤ 3m ρHT _ <h _ . Since earlier layers use smaller step sizes, their movement is slow enough to keep the later-layer visitation weights stable. The third step of the proof controls the Q-variation term. Lemma 10 shows that a small change in the product Markov profile leads to a small change in Q-functions. Combining this perturbation estimate with the policy-movement bound leads to Lemma 11, namely ‖Qt,hi(s,⋅)−Qt−1,hi(s,⋅)‖∞2≤36m2ρ¯2H6ηH2(t≥2), \|Q_t,h^i(s,·)-Q_t-1,h^i(s,·) \|_∞^2≤ 36m^2 ρ^2H^6 _H^2 (t≥ 2), with the t=1t=1 round bounded separately by H2H^2. Substituting these estimates into the weighted OOMD bound yields, up to absolute constants, Ri,h(μi)≤Biηh+3mρ¯HBiηh(T∑ℓ<hηℓ)+12ηhρiH2+18ηhρim2ρ¯2H6ηH2T.R_i,h(μ^i)≤ B_i _h+ 3m ρHB_i _h (T _ <h _ )+ 12 _h _iH^2+18 _h _im^2 ρ^2H^6 _H^2T. The learning-rate schedule ηh=η0T−αh,αh=3(H−h)+13H+1, _h= _0T^- _h,\; _h= 3(H-h)+13H+1, is chosen precisely to balance these terms after summing over layers. Therefore the total regret against any μi∈Πigenμ^i∈ _i^gen is bounded by (HBiη0+3mBiρ¯H3+12η0ρiH3+18η03ρim2ρ¯2H7)Tβ, ( HB_i _0+3mB_i ρH^3+ 12 _0 _iH^3+18 _0^3 _im^2 ρ^2H^7 )T^β, where β=3H−23H+1β= 3H-23H+1. Finally, taking the supremum over μiμ^i and choosing λi=1/|Ai| _i=1/|A_i| gives RegTgen,i≤CiSETβ.Reg^gen,i_T≤ C_i^SET^β. Since β−1=−3/(3H+1)β-1=-3/(3H+1), choosing Tε:=⌈(C∗SEε)(3H+1)/3⌉,C∗SE:=maxi∈[m]CiSE,T_ := ( C_*^SE )^(3H+1)/3 ,\;C_*^SE:= _i∈[m]C_i^SE, ensures that, for every player i∈[m]i∈[m], RegTεgen,i≤εTε.Reg^gen,i_T_ ≤ T_ . The CCE guarantee then follows from the standard no-regret-to-CCE equivalence applied to the empirical distribution over the generated policy profiles. ∎ 3.2 Episodic Markov games under partial feedback In this subsection, we extend the results of Subsection 3.1 to the partial-feedback setting. The primary distinction between the full-feedback and partial-feedback settings is the restrictions on the accessibility to Q-functions. We tackle this difficulty by estimating the Q-functions as follows. First, players will maintain a small action-exploration floor throughout the play. This action-exploration floor is maintained by taking mirror descent steps over the simplex Δiζ:=x∈Δ(Ai):x(ai)≥ζ|Ai| for every ai∈Ai _i^ζ:= \x∈ (A_i):x(a_i)≥ ζ|A_i| for every a_i∈ A_i \ instead of the full simplex Δ(Ai) (A_i), where ζ∈(0,1]ζ∈(0,1]. Second, unlike the full-information case, the players update policies in blocks, which is inspired by Erez et al. (2023). This update proceeds as follows. During a block, the same product Markov profile is repeated for B independent episodes, and the realized trajectories are used to estimate the Q-functions for that block by visiting each state-action (s,a)(s,a) pair sufficiently many times. The policy is then updated using the estimated Q-functions. To ensure that every player state is reached often enough throughout the play, we impose the following reachability condition in a similar way to Erez et al. (2023); Wei et al. (2021). Definition 7 ((κ,ζ)(κ,ζ)-reachability). A finite-horizon Markov game is said to be (κ,ζ)(κ,ζ)-reachable if, for every Markov policy profile π satisfying πhi(ai∣s)≥ζ|Ai| _h^i(a_i s)≥ ζ|A_i| for all i∈[m]i∈[m], h∈[H]h∈[H], s∈Shs∈ S_h, and ai∈Aia_i∈ A_i, the induced state-occupancy probabilities satisfy Pr(sh=s)≥κ _ π(s_h=s)≥κ for all h∈[H]h∈[H] and s∈Shs∈ S_h. At block k, all players use the same product Markov profile πk _k for B independent episodes. For episode r∈[B]r∈[B] in block k, we write the realized trajectory as (s1k,r,1k,r,s2k,r,2k,r,…,sHk,r,Hk,r,sH+1k,r).(s_1^k,r, a_1^k,r,s_2^k,r, a_2^k,r,…,s_H^k,r, a_H^k,r,s_H+1^k,r). The realized tail cost of player i at layer h is denoted by Yhi,k,r:=∑τ=hHℓτi(sτk,r,τk,r).Y_h^i,k,r:= _τ=h^H _τ^i(s_τ^k,r, a_τ^k,r). By Nk,iN_k,i we denote the number of times that player i visits (s,a)∈Sh∈Ai(s,a)∈ S_h∈ A_i during the play, which can be formally written as Nk,i(s,ai):=∑r=1Bshk,r=s,ahi,k,r=ai.N_k,i(s,a_i):= _r=1^B1\s_h^k,r=s,\ a_h^i,k,r=a_i\. (1) Then, we define the empirical estimate of the Q-function of player i at block k as Q^k,hi(s,ai):=1Nk,i(s,ai)∑r=1Bshk,r=s,ahi,k,r=aiYhi,k,r,Nk,i(s,ai)>0,0,Nk,i(s,ai)=0. Q_k,h^i(s,a_i):= cases 1N_k,i(s,a_i) _r=1^B1\s_h^k,r=s,\ a_h^i,k,r=a_i\Y_h^i,k,r,&N_k,i(s,a_i)>0,\\[8.61108pt] 0,&N_k,i(s,a_i)=0. cases Our Algorithm in the partial-feedback setting, compared to Algorithm 1, differs in only two aspects: the use of a blocked estimation procedure and the replacement of exact values with their corresponding estimates; see Algorithm 2. Algorithm 2 Blocked Layered OOMD 1: Input: finite-horizon game G, horizon H, number of blocks K, block length B, exploration floor ζ∈(0,1]ζ∈(0,1], base step-size η0∈(0,1] _0∈(0,1]. 2: Define αh:=3(H−h)+13H+1,ηh:=η0K−αh,x¯i(ai):=1|Ai|,λi=1/|Ai|,ai∈Ai,h∈[H]. _h:= 3(H-h)+13H+1,\; _h:= _0K^- _h,\; x^i(a_i):= 1|A_i|, _i=1/|A_i|,\;a_i∈ A_i,h∈[H]. 3: For every i∈[m]i∈[m], h∈[H]h∈[H], and s∈Shs∈ S_h, set x~0,hi,s=x¯i∈argminx∈ΔiζΨi(x),Q^0i(s,⋅)≡0∈ℝAi. x_0,h^i,s= x^i∈ *argmin_x∈ _i^ζ _i(x),\; Q_0^i(s,·)≡ 0 ^A_i. 4: for k=1,…,Kk=1,…,K do 5: for each player i∈[m]i∈[m], layer h∈[H]h∈[H], and state s∈Shs∈ S_h do 6: xk,hi,s=argminx∈Δiζηh⟨Q^k−1,hi(s,⋅),x⟩+Di(x,x~k−1,hi,s).x_k,h^i,s= *argmin_x∈ _i^ζ \ _h Q_k-1,h^i(s,·),x +D_i (x, x_k-1,h^i,s ) \. 7: Set πk,hi(⋅∣s)=xk,hi,s(⋅) _k,h^i(· s)=x_k,h^i,s(·). 8: Execute B independent episodes using the fixed product profile πk=(πk1,…,πkm) _k=( _k^1,…, _k^m). 9: Each player i forms the trajectory estimate Q^k,hi(s,ai) Q_k,h^i(s,a_i) for all h∈[H]h∈[H], s∈Shs∈ S_h, and ai∈Aia_i∈ A_i. 10: for each player i∈[m]i∈[m], layer h∈[H]h∈[H], and state s∈Shs∈ S_h do 11: x~k,hi,s=argminx∈Δiζηh⟨Q^k,hi(s,⋅),x⟩+Di(x,x~k−1,hi,s). x_k,h^i,s= *argmin_x∈ _i^ζ \ _h Q_k,h^i(s,·),x +D_i (x, x_k-1,h^i,s ) \. For the regret guarantee of Algorithm 2, we first introduce the following: C~∗SE≤maxi∈[m]2Hlog(|Ai|+1)η0+12mH3log(|Ai|+1)+η0H3+288η03m2H7,C~∗SE:=maxi∈[m]C~iSE. C_*^SE≤ _i∈[m] \ 2H (|A_i|+1) _0+12mH^3 (|A_i|+1)+ _0H^3+288 _0^3m^2H^7 \, C_*^SE:= _i∈[m] C_i^SE. The constant above differs from the constant C∗SEC_*^SE in the full-feedback case only in the last term, which is due to the Q-function estimations that we use. The following result is the corresponding regret guarantee of Algorithm 2. Theorem 2. Suppose the underlying Markov game is (κ,ζϵ)(κ, _ε)-reachable, where ζε:=ε8H2 _ := 8H^2. Fix ε,δ∈(0,1] ,δ∈(0,1]. Choose Kε:=⌈(4C~∗SEε)(3H+1)/3⌉,Bε:=⌈8Amaxκζε(nε+uε)⌉,K_ := ( 4 C_*^SE )^(3H+1)/3 ,B_ := 8A_ κ _ (n_ +u_ ) , where Mε:=KεmAmaxS,ξε:=minε8H,ε32η0H,uε:=log4Mεδ,nε:=⌈H22ξε2uε⌉.M_ :=K_ mA_ S, _ := \ 8H, 32 _0H \,u_ := 4M_ δ,n_ := H^22 _ ^2u_ . Then, running Algorithm 2 for every player i∈[m]i∈[m], for Nε=O~(AmaxH2κε(H2ξε2+1)(C~∗SEε)(3H+1)/3)N_ = O ( A_ H^2κ ( H^2 _ ^2+1 ) ( C_*^SE )^(3H+1)/3 ) episodes results in RegNεgen,i≤εNε,Reg^gen,i_N_ ≤ N_ , with probability at least 1−δ1-δ. Consequently, the empirical distribution Π^Nε _N_ is an ε -approximate CCE. Thus, our regret guarantees for the partial-feedback implementation of Algorithm 2 inherits the same exponential dependence on the horizon length as the one we had in the full-feedback finite-horizon case, together with an additional polynomial overhead arising from exploration, and value-function estimation parts. Proof Outline. The proof follows the same stability argument as in the full-feedback case, with two additional steps. First, because the algorithm uses only partial feedback, it relies on an estimation of the exact Q-function values. The exploration floor and the (κ,ζ)(κ,ζ)-reachability ensure that, during each block, every state-action pair (s,ai)(s,a_i) is sampled often enough. Later, Lemma 14 shows that, if the block length is chosen as in Theorem 2, i.e. Bε:=⌈8Amaxκζε(nε+uε)⌉B_ := 8A_ κ _ (n_ +u_ ) , then with probability at least 1−δ1-δ, the Q-functions can be estimated uniformly with the desired precision, i.e., maxk,i,s,ai|Q^k,hi(s,ai)−Qk,hi(s,ai)|≤ξε. _k,i,s,a_i | Q_k,h^i(s,a_i)-Q^i_k,h(s,a_i) |≤ _ . Second, the imposed action floor for exploration restricts the policies played by the algorithm to Δiζε _i _ . To compare policies within Δiζε _i _ against an arbitrary history-dependent policy μiμ^i, we smooth the comparator by mixing it with the uniform distribution. Lemma 13 then shows that this comparison changes the value by at most 2ζH22ζ H^2. Thus, the error bound obtained due to the exploration is controlled by choosing ζε=ε/(8H2) _ = /(8H^2). On the good event that all Q-estimates are uniformly accurate, the proof then runs the full-feedback OOMD analysis with Q^k,hi Q_k,h^i in place of Qk,hiQ_k,h^i. Then, Proposition 2 gives the following regret bound: Reggen,iN=supμi∈Πigen1K∑k=1K[Vi,πk(s1)−Vi,μi⊙πk−i(s1)]≤C~iSEK−3/(3H+1)+2Hξ+2ζH2+8η0Hξ2K−αH. ^gen,i_N\!\!=\!\! _μ^i∈ _i^gen 1K _k=1^K [V^i, _k(s_1)\!-\!V^i,μ^i _k^-i(s_1) ]\!≤ C_i^SEK^-3/(3H+1)\!+\!2Hξ\!+\!2ζ H^2\!+\!8 _0Hξ^2K^- _H. The four terms have clear roles: the first is the finite-horizon OOMD error, the second is the error from replacing exact Q-functions by (uniform) estimates, the third is the cost of smoothing the comparator, and the last one is an additional variation term caused by using estimated Q-functions in the optimistic update. The choices of KεK_ , ξε _ , and ζε _ make these four terms at most ε/4 /4 each. Combining this deterministic regret bound with high probability estimation guarantee given in Lemma 14 proves Theorem 2. ∎ 4 Approximating Equilibrium Discounted Markov Games In this section, we extend the finite-horizon non-discounted Markov game regret guarantees from Section 3 to discounted Markov games in both finite horizon and infinite horizon cases. The argument for this extension is independent of the feedback model, and it only requires a finite-horizon regret guarantee on the truncated discounted game. With this extension, we show that the corresponding regret can be reduced to a sub-exponential bound in the discounted case. We first state this general transfer principle in Theorem 3, and then instantiate it for the full-feedback and partial-feedback algorithms in Corollaries 1 and 2 . 4.1 A transfer principle In the infinite-horizon discounted game case, a non-Markov nonstationary policy consists of infinitely many decision rules, and hence cannot be represented by a finite-sized object. Thus, a finite-output algorithm must either restrict attention to a compactly represented policy class, such as stationary policies, or approximate the discounted game by a finite-horizon truncation. It is known that, for general-sum discounted Markov games, computing stationary equilibria is already PPAD-hard (Daskalakis et al., 2023). We therefore follow the second route and work with sparse distributions over finite-horizon product-policy prefixes. In the infinite-horizon case, each such prefix is extended beyond the truncation point by a fixed reference continuation. The same formulation also covers finite-horizon discounted games: when H¯<∞ H<∞, we choose a truncation length L≤H¯L≤ H, extend the learned L-step policies only if L<H¯L< H, and the continuation is vacuous when L=H¯L= H. Ultimately, discounting is what makes this finite approximation idea possible. Since the contribution of future layers decays geometrically, controlling the first L discounted layers is sufficient to control the original discounted objective up to a tail error. This observation allows the finite-horizon regret guarantees from Section 3 to be transferred directly to discounted Markov games. Specifically, we run the finite-horizon algorithm on the L-step discounted truncated game, obtain a regret guarantee on the first L layers, and then account separately for the remaining discounted tail to approximate the equilibrium of the discounted game with horizon H¯ H. We now formalize this transfer argument as follows. Theorem 3. Let H¯∈ℕ+∪∞, H _+∪\∞\, γ∈(0,1),γ∈(0,1), and fix L≤H¯L≤ H. Suppose that a learning procedure is run on the game Gγ,H¯[L]G_γ, H^[L] for N episodes, and outputs an L-step product Markov profile at each episode, 1[L],…,N[L],\ π_1^[L],…, π_N^[L]\, where t[L]∈Πmarkov,Lfor every t∈[N]. π_t^[L]∈ ^markov,L\;for every t∈[N]. Assume that, for every player i∈[m]i∈[m], the learning procedure satisfies supνi∈Πigen,L1N∑n=1N[Ji,Lγ(n[L])−Ji,Lγ(νi⊙n[L],−i)]≤εalg. _ν^i∈ _i^gen,L 1N _n=1^N [J_i,L^γ( π_n^[L])-J_i,L^γ(ν^i π_n^[L],-i) ]≤ _alg. For each n∈[N]n∈[N], let ¯n:=ExtL(n[L]). π_n:=Ext_L( π_n^[L]). Then, for every player i∈[m]i∈[m], supμi∈Πigen,H¯1N∑n=1N[Ji,H¯γ(¯n)−Ji,H¯γ(μi⊙¯n−i)]≤εalg+τL,H¯(γ). _μ^i∈ _i^gen, H 1N _n=1^N [J_i, H^γ( π_n)-J_i, H^γ(μ^i π_n^-i) ]≤ _alg+ _L, H(γ). Equivalently, 1N∑n=1Nδ¯n 1N _n=1^N _ π_n is an (εalg+τL,H¯(γ))( _alg+ _L, H(γ))-approximate discounted CCE over horizon H¯ H. Proof Outline. The complete proof is deferred to Appendix D. To compare an extended learned policy ¯n=ExtL(n[L]) π_n=Ext_L( π_n^[L]) against an arbitrary H¯ H-horizon deviation μiμ^i, the finite-horizon algorithm only needs to compete with the first L decision rules of that deviation, μi,[L].μ^i,[L]. The formal tail bound in Lemma 15 leads to 0≤Ji,H¯γ()−Ji,Lγ([L])≤τL,H¯(γ)≤γL1−γ0≤ J_i, H^γ( σ)-J_i,L^γ( σ^[L])≤ _L, H(γ)≤ γ^L1-γ for every policy profile σ. Combining this estimate for the learned policy with the non-negativity of costs leads to the one-step comparison Ji,H¯γ(¯n)−Ji,H¯γ(μi⊙¯n−i)≤ J_i, H^γ( π_n)-J_i, H^γ(μ^i π_n^-i)≤ Ji,Lγ(n[L])−Ji,Lγ(μi,[L]⊙n[L],−i)+τL,H¯(γ), J_i,L^γ( π_n^[L])-J_i,L^γ(μ^i,[L] π_n^[L],-i)+ _L, H(γ), which is Lemma 16. Averaging this inequality over the policies produced by the finite-horizon algorithm and then using the finite-horizon regret guarantee proves the theorem.∎ The corollaries below instantiate Theorem 3 with a similar choice of truncation length. For a target accuracy ε , we choose Hεγ:=⌈log(2(1−γ)ε)log(1/γ)⌉,H_ ^γ:= ( 2(1-γ) ) (1/γ) , so that γHεγ1−γ≤ε2. γ^H_ ^γ1-γ≤ 2. Thus, for a discounted game with horizon H¯∈ℕ+∪∞ H _+∪∞, we set Lε:=minH¯,HεγL_ := \ H,H_ ^γ\ to guarantee, τLε,H¯(γ)≤ε2. _L_ , H(γ)≤ 2. We, then run the corresponding finite-horizon algorithms, Algorithms 1 and 2, on the LεL_ -step truncated discounted game Gγ,H¯[Lε]G_γ, H^[L_ ] long enough to make its average regret at most ε/2 /2. The finite-horizon regret bounds in Theorems 1 and 2 have exponents that depend on the horizon length, and thus replacing the original horizon by the effective discounted horizon LεL_ is crucial. For every fixed γ<1γ<1, Hεγ=O(log(1/ε))H_ ^γ=O( (1/ )), and hence the resulting discounted-game bounds become quasi-polynomial in 1/ε1/ , rather than exponential in the original horizon. 4.2 Full-feedback and Partial-feedback consequences Let C∗SE(L)C_*^SE(L) denote the full-feedback constant in Theorem 1 with the horizon parameter replaced by L, and set Alog:=maxi∈[m]log(|Ai|+1).A_ := _i∈[m] (|A_i|+1). Then, formally, we have the following guarantees. Corollary 1. Let H¯∈ℕ+∪∞,ε∈(0,1], H _+∪\∞\,\; ∈(0,1], and define Hεγ:=⌈log(2(1−γ)ε)log(1/γ)⌉.H_ ^γ:= \! ( 2(1-γ) ) (1/γ) . Choose Tε:=⌈(2C∗SE(Lε)ε)(3Lε+1)/3⌉,T_ := ( 2C_*^SE(L_ ) )^(3L_ +1)/3 , Lε:=minH¯,Hεγ.L_ := \ H,H_ ^γ\. Run Algorithm 1 on the LεL_ -step discounted truncation Gγ,H¯[Lε]G_γ, H^[L_ ] for TεT_ episodes. For each t∈[Tε]t∈[T_ ], let ¯t=ExtLε(t[Lε]) π_t=Ext_L_ ( π_t^[L_ ]). Then, for every player i∈[m]i∈[m], supμi∈Πigen,H¯∑t=1Tε[Ji,H¯γ(¯t)−Ji,H¯γ(μi⊙¯t−i)]≤εTε. _μ^i∈ _i^gen, H _t=1^T_ [J_i, H^γ( π_t)-J_i, H^γ(μ^i π_t^-i) ]≤ T_ . Consequently, 1Tε∑t=1Tεδ¯t 1T_ _t=1^T_ _ π_t is an ε -approximate discounted CCE over horizon H¯ H. Moreover, for every fixed γ<1γ<1, Tε≤[(Alogη0+mAlog+m2+1)minH¯,log(1/ε)7ε]O(minH¯,log(1/ε)).T_ ≤ [ ( A_ _0+mA_ +m^2+1 ) \ H, (1/ )\^7 ]^O( \ H, (1/ )\). Proof. See Appendix D.1 ∎ We now apply Theorem 3 to the partial-feedback case. By C~∗SE(L) C_*^SE(L) denote the finite-horizon constant from Theorem 2 with horizon L. For a target finite-horizon accuracy ε¯∈(0,1] ∈(0,1], horizon L, and confidence level δ∈(0,1)δ∈(0,1), choose Kε¯,L:=⌈(4C~∗SE(L)ε¯)(3L+1)/3⌉,ζε¯,L:=ε¯8L2,Bε¯,L,δ:=⌈8Amaxκζε¯,L(nε¯,L,δ+uε¯,L,δ)⌉,K_ ,L:= ( 4 C_*^SE(L) )^(3L+1)/3 ,\; _ ,L:= 8L^2,\;B_ ,L,δ\!:=\! \! 8A_ κ _ ,L (n_ ,L,δ+u_ ,L,δ )\! , where, Mε¯,L:=Kε¯,LmAmaxS,M_ ,L\!:=\!K_ ,LmA_ S, uε¯,L,δ:=log4Mε¯,Lδ,nε¯,L,δ:=⌈L22ξε¯,L2uε¯,L,δ⌉,ξε¯,L:=minε¯8L,ε¯32η0L¯.u_ ,L,δ\!:=\! 4M_ ,Lδ,\;n_ ,L,δ\!:=\! \! L^22 _ ,L^2u_ ,L,δ\! \!,\; _ ,L:= \ 8L, 32 _0 L \. Then, formally, we have the following guarantee. Corollary 2. Let H¯∈ℕ+∪∞,ε,δ∈(0,1], H _+∪\∞\,\; ,δ∈(0,1], and define Hεγ:=⌈log(2(1−γ)ε)log(1/γ)⌉.H_ ^γ:= \! ( 2(1-γ) ) (1/γ) . Set Lε:=minH¯,Hεγ,ε¯:=ε2L_ := \ H,H_ ^γ\,\; := 2 . Assume that the truncated discounted game Gγ,H¯[Lε]G_γ, H^[L_ ] is (κ,ζε¯,Lε)(κ, _ ,L_ )-reachable. Run Algorithm 2 on Gγ,H¯[Lε]G_γ, H^[L_ ] with parameters Kε¯,LεK_ ,L_ , Bε¯,Lε,δB_ ,L_ ,δ, and ζε¯,Lε _ ,L_ for Nε,H¯,δN_ , H,δ episodes. For each k∈[Kε¯,Lε],k∈[K_ ,L_ ], let π¯k:=ExtLε(πk[Lε]). π_k:=Ext_L_ ( _k^[L_ ] ). Then, with probability at least 1−δ1-δ, for every player i∈[m]i∈[m], supμi∈Πigen,H¯1Nε,H¯,δ∑k=1Kε¯,Lε∑t=1Bε,Lε,δ[Ji,H¯γ(π¯k)−Ji,H¯γ(μi⊙π¯k−i)]≤ε. _μ^i∈ _i^gen, H 1N_ , H,δ _k=1^K_ ,L_ _t=1^B_ ,L_ ,δ [J_i, H^γ( π_k)-J_i, H^γ(μ^i π_k^-i) ]≤ . Consequently, 1Nε,H¯,δ∑t=1Nε,H¯,δπ¯t 1N_ , H,δ _t=1^N_ , H,δ _ π_t is an ε -approximate discounted CCE. Moreover, for constants band:=2Alogη0+12mAlog+η0+288m2η03,C_band:= 2A_ _0+12mA_ + _0+288m^2η^3_0, ℒH¯,ε:=minH¯,log(1/ε),L_ H, := \ H, (1/ )\, and γ<1γ<1, we have Nε,H¯,δ≤[AmaxℒH¯,ε2κε(1+ℒH¯,ε4ε2+η0ℒH¯,ε3ε)×(ℒH¯,εlogbandℒH¯,ε7ε+logmAmaxSδ)][bandℒH¯,ε7ε]O(ℒH¯,ε) N_ , H,δ≤ [ A_ L_ H, ^2κ \! (1+ L_ H, ^4 ^2+ _0L_ H, ^3 \! )\!\!×\!\! (\!L_ H, \! C_bandL_ H, ^7 \!+\! \!mA_ S\!δ )\! ]\!\! [ \!C_bandL_ H, ^7\! ]^O(L_ H, ) Proof. See Appendix D.2 ∎ 5 Computational Lower Bound for Discounted Markov Games In this section, we provide computational lower bounds for the task of finding a CCE in discounted Markov games to complement the quasi-polynomial upper bounds we have found in the earlier sections. In particular, we show that under the “ ETH for PPAD”, one should not expect a polynomial-time polynomial-support algorithm for the same discounted CCE objective in general-sum discounted Markov games when players learn independently in decentralized settings. To show this, we make simple modifications on the main results of Foster et al. (2023), which achieves this result for finite-horizon undiscounted Markov games for a problem called sparse Markov CCE. Accordingly, we define a search problem that subsumes their problem as a special case. Definition 8. Fix a discount factor γ∈(0,1]γ∈(0,1] for the finite horizon case and fix a discount factor γ∈(0,1)γ∈(0,1) for the infinite horizon case . For an m-player discounted Markov game Gγ,H¯G_γ, H and parameters T∈ℕT and ε>0 >0, which may depend on the size of Gγ,H¯G_γ, H, the (T,ε)-γgen(T, )- DiscSparseMarkovCCE^gen_γ problem is the problem of finding a sequence (1),…,(T),(t)∈Πmarkov,H¯for every t∈[T], σ^(1),…, σ^(T),\; σ^(t)∈ ^markov, H\;for every t∈[T], such that the distributional policy ^T:=1T∑t=1Tδ(t)∈Δ(Πgen,H¯) σ_T:= 1T _t=1^T _ σ^(t)∈ \! ( ^gen, H ) is an ε -approximate discounted CCE of Gγ,H¯G_γ, H. Equivalently, the sequence must satisfy supμi∈Πigen,H¯∑t=1T[Jiγ((t))−Jiγ(μi⊙(t),−i)]≤εT _μ^i∈ _i^gen, H _t=1^T [J_i^γ\! ( σ^(t) )-J_i^γ\! (μ^i σ^(t),-i ) ]≤ T for every player i∈[m]i∈[m]. We call such a sequence a T-sparse discounted CCE. Definition 8 formulates the equilibrium-computation objective studied in this section as a search problem over finite sequences of product Markov policy profiles. The following proposition says that the outputs constructed from Algorithms 1 and 2 are valid solutions to this search problem. Proposition 1. Let Gγ,H¯G_γ, H be an m-player discounted Markov game, and fix ε∈(0,1] ∈(0,1]. 1. Let LεL_ and TεT_ be chosen as in Corollary 1. Run Algorithm 1 on the truncated Markov game Gγ,H¯[Lε]G_γ, H^[L_ ], and define ¯t:=ExtLε(t[Lε]),t∈[Tε]. π_t:=Ext_L_ ( π_t^[L_ ] ),\;t∈[T_ ]. Then (¯1,…,¯Tε) ( π_1,…, π_T_ ) is a solution to (Tε,ε)-γgen.(T_ , )- DiscSparseMarkovCCE_γ^gen. 2. Suppose that the reachability condition of Corollary 2 holds, and choose the parameters LεL_ , KεK_ , and BεB_ as in Corollary 2. Run Algorithm 2 on Gγ,H¯[Lε]G_γ, H^[L_ ], and define ¯k:=ExtLε(k[Lε]),k∈[Kε]. π_k:=Ext_L_ ( π_k^[L_ ] ),\;k∈[K_ ]. Let Nε:=KεBεN_ :=K_ B_ , and define the policy sequence by (k−1)Bε+r:=¯k,k∈[Kε],r∈[Bε]. σ^(k-1)B_ +r:= π_k,\;k∈[K_ ],\;r∈[B_ ]. Then, with probability 1−δ1-δ, (1,…,Nε) ( σ^1,…, σ^N_ ) is a solution to (Nε,ε)-γgen.(N_ , )- DiscSparseMarkovCCE_γ^gen. Proof. See Appendix E.1. ∎ Before proceeding, we emphasize that (T,ε)-γgen(T, )- DiscSparseMarkovCCE^gen_γ is a relaxation of the radically uncoupled learning task addressed by Algorithms 1 and 2 through discounted policy extensions. The search problem only asks for a finite sequence of product Markov policy profiles whose uniform empirical distribution is an ε -approximate discounted CCE. It does not require that this sequence be generated online by independent players; in particular, a centralized algorithm with full access to the game description is also permitted as stated in Foster et al. (2023). Therefore, any lower bound provided for this search problem, is also valid for our radically uncoupled learning problem. Next, we state the arguments that lay the foundation for our computational lower bound result. Lemma 1. Let M be an n×n× n bimatrix game. Then, there exists a corresponding 22-player Markov game FH(M)F_H(M) with a predesignated horizon-length H such that computation of the CCE of FH(M)F_H(M) implies computation of NE of M. Furthermore, this construction can be done in polynomial time. Proof. See Appendix E.3. ∎ For any given finite-horizon Markov game, by forcing the game to enter an absorbing state after the step h=Hh=H, we obtain an infinite-horizon discounted extension of it. Lemma 2. Let GHG_H be a Markov game with horizon length H. Then there exists an infinite-horizon γ-discounted Markov game G~H,γ G_H,γ such that if L~ L is an ε -approximate discounted CCE of G~H,γ G_H,γ, then there exists a list L~[H] L^[H] that is an (ε/γH−1)( /γ^H-1)-approximate CCE of GHG_H. Furthermore, this construction can be done in polynomial time. We denote this correspondence in the case of FH(M)F_H(M) by F~H,γ(M) F_H,γ(M). Proof. See Appendix E.4. ∎ We refer to Appendix E for the detailed encoding conventions. Before introducing our main result of this section, we first recall the complexity-theoretic assumption underlying our lower bound. Introduced by Papadimitriou (1994), PPAD is a widely studied complexity class for equilibrium computation in game theory. For the sake of completeness, we provide a complete statement of the so-called Exponential Time Hypothesis for PPAD. We refer to Papadimitriou (1994) and Rubinstein (2016) for further details. Definition 9 ( EndOfALine; (Daskalakis et al., 2009)). Given two binary circuits S,P,S,P, each with m-input bits and m output bits such that P(0m)=0m≠S(sm)P(0^m)=0^m =S(s^m), find an input x∈0,1mx∈\0,1\^m such that P(S(x))≠xP(S(x)) =x or S(P(x))≠x≠0mS(P(x)) =x =0^m. Assumption 1 ( ETH for PPAD; Babichenko et al. (2016)). Solving the PPAD-complete problem EndOfALine, on instances of size n~ n, requires time 2Ω(n~).2 ( n). Our hardness results rely on the following consequence of the “ ETH for PPAD”. Theorem 4 (Rubinstein (2016)). Assume ETH for PPAD. Then, there exists a universal constant ε⋆>0 _ >0 such that every algorithm that computes an ε⋆ _ -approximate Nash equilibrium of every two-player n×n× n bimatrix game requires time nlog1−o(1)n.n ^1-o(1)n. Lemma 3. There exists a countable infinite subset ⊂ℕS such that for all n∈n there exists a bimatrix game M M with the following properties: 1. Both players have n pure actions, and assuming ETH for PPAD, computing an ε⋆ _ -approximate Nash equilibrium of M M requires time nlog1−o(1)n.n ^1-o(1)n. 2. Let |M^|| M| be the size of the game M M (see Appendix E.2). There exist absolute constants qsrc,nsrc≥1q_ src,n_ src≥ 1, such that n≤|M^|≤(n+2)qsrcn≤| M|≤(n+2)^q_ src for all n≥nsrcn≥ n_ src. 3. Let γ be a discount factor. There are absolute constants AH,BH,nsize(γ),d0A_H,B_H,n_size(γ),d_0 such that whenever n≥nsize(γ)n≥ n_size(γ) and AHlog(n+2)≤H≤BHlog(n+2)A_H (n+2)\!≤ H≤\!B_H (n+2), n≤|F~H,γ(M^)|≤(n+2)d0n\!≤| F_H,γ( M)|≤\!(n+2)^d_0 holds. Proof. See Appendices E.2 and E.4. ∎ The next result is the main result of this section, which provides a computational lower bound for (NC,N−K)-γgen(N^C,N^-K)- DiscSparseMarkovCCE^gen_γ for arbitrarily large N, where N is the size of the discounted Markov game instance the search problem is concerned with (see Appendix E.2). Here, C is the support exponent and K is the accuracy exponent, which are absolute constants. Theorem 5. Fix a constant discount factor γ∈(0,1)∩ℚγ∈(0,1) and a support exponent C>0C>0. We define AH:=2(Cd0+1)cFε⋆2,BH:=AH+2,A_H:= 2(Cd_0+1)c_F _ ^2,\;B_H:=A_H+2, aγ=BHlog(1γ)a_γ=B_H ( 1γ). By M M denote the bimatrix game in Lemma 3. Under Assumption 1, there exists an accuracy exponent K=K(γ,C)≥aγ+1K=K(γ,C)≥ a_γ+1 such that, for any constructed discounted Markov game F~H,γ(M^) F_H,γ( M), n∈n , satisfying n≥nsrc,nsize(γ),n≥ n_src,n_size(γ), n−K(n+2)aγ≤ε⋆4n 2.0pt-K(n+2)^a_γ≤ _ 4, and such that there exists an even integer H with BHlog(n+2)≥H≥AHlog(n+2),B_H (n+2)≥ H≥ A_H (n+2), there exists a discounted two-player general-sum Markov game such that no polynomial-time algorithm solves (|F~H,γ(M^)|C,|F~H,γ(M^)|−K)-γgen (| F_H,γ( M)|^C,| F_H,γ( M)|^-K )- DiscSparseMarkovCCE^gen_γ. Before proceeding with the proof of Theorem 5, some remarks are in order. Theorem 5 demonstrates that with our current understanding of computational complexity, it is unlikely that there exists a polynomial time algorithm for discounted Markov games. In particular, a quasi-polynomial time algorithm (which we have constructed) is about the best one can hope for. Proof of Theorem 5. Suppose not. Take K:=aγ+1K:=a_γ+1 that violates the running hypothesis. Let M M denote the bimatrix game whose infinite-horizon discounted extension under γ admits a polynomial-time algorithm A that solves (|F~H,γ(M^)|C,|F~H,γ(M^)|−K)-γgen (| F_H,γ( M)|^C,| F_H,γ( M)|^-K )- DiscSparseMarkovCCE^gen_γ with the aforementioned properties. Running A on F~H,γ(M^) F_H,γ( M), we obtain a list L~=(1,⋯,T) L=( σ_1,·s, σ_T) such that T≤⌈|F~H,γ(M^)|C⌉,maxi∈1,2Gapiγ(L~,F~H,γ(M^))≤|F~H,γ(M^)|−K,T≤ | F_H,γ( M)|^C , _i∈\1,2\Gap_i^γ( L; F_H,γ( M))≤| F_H,γ( M)|^-K, whose restrictions to the first H-layers is denoted by LH:=L~[H]=(1[H],…,T[H])L_H:= L^[H]=( σ_1^[H],…, σ_T^[H]) that satisfies the properties in Lemma 2. In particular, it holds that maxi∈1,2GapiH(LH,FH(M^)) _i∈\1,2\Gap_i^H(L_H;F_H( M)) =γ−H+1maxi∈1,2Gapiγ(L~,F~H,γ(M^))≤|F~H,γ(M^)|−Kγ−H+1. =γ^-H+1 _i∈\1,2\Gap_i^γ( L; F_H,γ( M))≤| F_H,γ( M)|^-Kγ^-H+1. Since |F~H,γ(M^)|≥n| F_H,γ( M)|≥ n and H≤BHlog(n+2)H≤ B_H (n+2) by Lemma 3, |F~H,γ(M^)|−Kγ−(H−1) | F_H,γ( M)|^-Kγ^-(H-1) ≤n−Kγ−H ≤ n^-Kγ^-H =n−Kexp(Hlog(1/γ)) =n^-K \! (H (1/γ) ) ≤n−Kexp(BHlog(n+2)log(1/γ)) ≤ n^-K \! (B_H (n+2) (1/γ) ) =n−K(n+2)aγ≤ε⋆4. =n^-K(n+2)^a_γ≤ _ 4. Therefore LHL_H is an ε⋆/4 _ /4-approximate T-sparse CCE of FH(M^)F_H( M), against non-Markov deviations. Since T≤⌈|F~H,γ(M^)|C⌉T≤ | F_H,γ( M)|^C , |F~H,γ(M^)|≤(n+2)d0| F_H,γ( M)|≤(n+2)^d_0, and that H≥Ahlog(n+2)H≥ A_h (n+2), a straightforward inequality implies that T<exp(cFε⋆2H)T< (c_F _ ^2H), meaning that Lemma 17 is applicable. In particular, through A, one obtains an ε⋆ _ -approximate Nash equilibrium of M M in polynomial time. Note that TH≤(n+2)Cd0+1O(logn)TH≤(n+2)^Cd_0+1O( n), which can be written in polynomial time in n. Furthermore, for any given mixed strategy in M M, its Nash gap can be checked in polynomial time. Since A runs in polynomial time and |F~H,γ(M^)|≤(n+2)d0| F_H,γ( M)|≤(n+2)^d_0, all output probabilities have polynomial bit length in n. Thus enumerating the candidate pairs and outputting one with gap at most ε⋆ _ is feasible in polynomial time. Construction of FH(M^)F_H( M) and F~H,γ(M^) F_H,γ( M) takes polynomial time by Lemmas 2 and 1. In particular, we have obtained a contradiction to Theorem 4. ∎ The following corollary extends our hardness result for the finite-horizon discounted setting. Corollary 3. Fix a constant discount factor γ∈(0,1)γ∈(0,1) and a support exponent Cfh>0C_fh>0. Under Assumption 1, there exists a finite-horizon discounted Markov game and an accuracy exponent Kfh=Kfh(γ,Cfh)>0K_fh=K_fh(γ,C_fh)>0 such that no polynomial-time algorithm can solve the following problem: given a game Gγ,H¯G_γ, H of input length at most N, output a list of at most NCfhN^C_fh product Markov profiles whose H¯ H-horizon discounted CCE gap, against all history-dependent deviations, is at most N−KfhN^-K_fh. Proof. Due to equilibrium correspondence between FH(M^)F_H( M) and F~H,γ(M^) F_H,γ( M), given in Lemma 2, Theorem 5 implies that no polynomial time algorithm is feasible for a class of Markov games FH(M^)F_H( M) under some restrictions on H and n. In such a game FH(M^)F_H( M), suppose that player i has an objective function of the form Ji,H=[∑h=1HγH−1ℓhi(xh,ah)].J_i,H=E [ _h=1^Hγ^H-1 ^i_h(x_h,a_h) ]. Note that Ji,H=[∑h=1Hγh−1γH−1ℓhi(xh,ah)γh−1],J_i,H=E [ _h=1^Hγ^h-1γ^H-1 ^i_h(x_h,a_h)γ^h-1 ], and thus rewriting the cost of player i instead as ℓhiγH−1/γh−1h=1H\ ^i_hγ^H-1/γ^h-1\_h=1^H, we obtain that there is no polynomial time algorithm for a discounted Markov game. ∎ 6 Numerical Results In this section, we evaluate the independent learning dynamics under both information structures considered in the paper. First, we run Algorithm 1 with full-feedback, as in Theorem 1. Second, we run Algorithm 2 using only independently sampled partial feedbacks, as in Theorem 2. These two experiments use exactly the same four finite-horizon Markov games. Finally, we use a two-state discounted linear-quadratic zero-sum Markov game with a closed-form stationary solution as a benchmark for the discounted truncation approximation result stated in Corollary 1. 6.1 Finite-horizon episodic Markov games We consider a Markov battle-of-the-sexes chain, a routing/congestion game, a three-player public-goods game, and a transition-trap game. The transition and cost tables are given in Appendix F. Every state appearing in these games has occupancy probability at least 0.050.05 under every product Markov profile. Hence, all four games are (0.05,ζ)(0.05,ζ)-reachable for every ζ∈(0,1]ζ∈(0,1]. Letting N denote the number of executed episodes, given the episode-indexed sequence of product Markov profiles (ρn)n=1N( _n)_n=1^N, we report GapN:=maxsupμi∈Πigeni∈[m]1N∑n=1N[Vi,ρn(s1)−Vi,μi⊙ρn−i(s1)].Gap_N:= _i∈[m] _μ^i∈ _i^gen 1N _n=1^N [V^i, _n(s_1)-V^i,μ^i _n^-i(s_1) ]. For Algorithm 1, one policy update is performed per episode, so N=tN=t and ρn=πn _n= _n. For Algorithm 2, the profile πk _k is held fixed for B episodes in block k; hence N=kBN=kB and ρ(k−1),B+r=πk _(k-1),B+r= _k for r∈[B]r∈[B]. The full-feedback experiment uses T=1000T=1000, η0=0.5 _0=0.5, and evaluates the gap every 5050 episodes. The partial-feedback experiment uses K=1000,B=500,ζ=0.05,η0=0.1,K=1000,\;B=500,\;ζ=0.05,\; _0=0.1, and evaluates the gap every 5050 blocks, or equivalently in every 25,00025,000 episodes. We perform 2020 independent runs of the trajectory-feedback experiment. Figure 1 reports their mean gap, with the shaded region representing plus or minus one empirical standard deviation. In all four games, the CCE gap decreases under both feedback models. Thus, the two panels respectively support the finite-horizon conclusions of Theorems 1 and 2. (a) Algorithm 1: full-feedback. (b) Algorithm 2: partial feedback. Figure 1: Finite-horizon behavior of the independent product-policy learning dynamics on the same four Markov games. Panel (a) reports the deterministic feedback generated full-feedback. Panel (b) reports the mean over 2020 independent partial feedback runs; shaded regions show one empirical standard deviation. 6.2 Discounted linear-quadratic benchmark The final experiment studies a two-player, two-state, zero-sum discounted linear-quadratic Markov game with continuous scalar actions. The benchmark is chosen so that its infinite-horizon discounted saddle-point solution can be computed in closed form. In the simulation, we discretize the action interval while ensuring that the grid contains the closed-form saddle-point actions. Let J0⋆(s0)J_0 (s_0) denote the normalized infinite-horizon discounted saddle-point value obtained from the closed-form solution. We report ErrT′:=|1T′∑t=1T′J0(πt)−J0⋆(s0)|,Err_T := | 1T _t=1^T J_0( _t)-J_0 (s_0) |, where J0(πt)J_0( _t) is the value of the finite approximation used in the simulation. Figure 2 shows that this error decreases rapidly. Thus, while the first two experiment evaluates CCE violations directly for the episodic case, the LQ benchmark tests our approximation on a problem where the infinite-horizon value is known. This experiment uses T=1000,H=20,γ=0.90,base grid size=9,η0=1.0T=1000,\ H=20,\ γ=0.90,\ base grid size=9,\ _0=1.0. Figure 2: Discounted linear-quadratic benchmark. The plot reports the value error relative to the closed-form infinite-horizon saddle-point value. 7 Conclusion In this work, we have shown that, under the so-called “ ETH for PPAD”, there does not exist any polynomial time algorithm for computing CCE in discounted general-sum Markov games. We have complemented this hardness result with a quasi-polynomial-time algorithm for online self-play under a radically uncoupled information structure, without imposing any structural assumptions on the game. Our layered OOMD algorithm appears to be the first provably convergent algorithm in this setting with a sub-exponential convergence guarantee. Furthermore, we have shown that the layered OOMD algorithm extends to the partial-feedback setting while retaining similar convergence guarantees. Our work suggests several directions for future research. First, a gap remains between our quasi-polynomial upper bounds and the computational lower bounds established in this paper; determining the precise complexity of computing sparse CCEs in discounted Markov games remains an important open problem. Second, it would be interesting to determine whether polynomial-time radically uncoupled online-learning algorithms exist for general-sum Markov games when the considered policy classes for the players are restricted to Markov policies rather than general history-dependent policies. Finally, another direction is to characterize the boundary between radically uncoupled learning and more permissive information models. In particular, it would be interesting to investigate whether information models weaker than shared randomness also make tractable algorithms possible. 8 Acknowledgment Research was supported in part by the Army Research Office (ARO), under Grant Number W911NF-24-1-0085. References Abernethy et al. [2008] Jacob Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In Proceedings of the 21st Annual Conference on Learning Theory (COLT), pages 263–274, 2008. Anagnostides et al. [2022] Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung-Wei Lee, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics with swap regret in multiplayer games. In Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS), 2022. Bai et al. [2020] Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. In Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS), 2020. Blum and Mansour [2007] Avrim Blum and Yishay Mansour. From external to internal regret. Journal of Machine Learning Research, 8:1307–1324, 2007. Cai et al. [2024] Yang Cai, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. Near-optimal policy optimization for correlated equilibrium in general-sum Markov games. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS), 2024. Cesa-Bianchi and Lugosi [2006] Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006. Cesa-Bianchi et al. [2012] Nicolò Cesa-Bianchi, Pierre Gaillard, Gábor Lugosi, and Gilles Stoltz. Mirror descent meets fixed share (and feels no regret). In Proceedings of the 26th Conference on Neural Information Processing Systems (NeurIPS), 2012. Daskalakis et al. [2011] Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 235–254, 2011. Daskalakis et al. [2021] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS), 2021. Erez et al. [2023] Liad Erez, Tal Lancewicki, Uri Sherman, Tomer Koren, and Yishay Mansour. Regret minimization and convergence to equilibria in general-sum Markov games. In Proceedings of the 40th International Conference on Machine Learning (ICML), 2023. Erez et al. [2025] Liad Erez, Tal Lancewicki, Uri Sherman, Tomer Koren, and Yishay Mansour. Regret minimization and convergence to equilibria in general-sum Markov games. arXiv preprint arXiv:2207.14211, 2025. Hart and Mas-Colell [2000] Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5):1127–1150, 2000. Littman [1994] Michael L. Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine Learning Proceedings 1994, pages 157–163, 1994. Maheshwari et al. [2024] Chinmay Maheshwari, Manxi Wu, and Shankar Sastry. Decentralized learning in general-sum Markov games. arXiv preprint arXiv:2409.04613, 2024. Mao and Başar [2023] Weichao Mao and Tamer Başar. Provably efficient reinforcement learning in decentralized general-sum Markov games. Dynamic Games and Applications, 13(1):165–186, 2023. Mao et al. [2024] Weichao Mao, Haoran Qiu, Chen Wang, Hubertus Franke, Zbigniew Kalbarczyk, and Tamer Başar. O~(T−1) O(T^-1) convergence to (coarse) correlated equilibria in full-information general-sum Markov games. In Proceedings of the 6th Annual Learning for Dynamics and Control Conference (L4DC), 2024. Nemirovski and Yudin [1983] A. S. Nemirovski and D. B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983. Rakhlin and Sridharan [2013] Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Proceedings of the 27th Conference on Neural Information Processing Systems (NeurIPS), 2013. Shapley [1953] L. S. Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39(10):1095–1100, 1953. Song et al. [2022] Ziang Song, Song Mei, and Yu Bai. When can we learn general-sum Markov games with a large number of players sample-efficiently? In International Conference on Learning Representations (ICLR), 2022. Soleymani et al. [2025] Ashkan Soleymani, Georgios Piliouras, and Gabriele Farina. Faster rates for no-regret learning in general games via cautious optimism. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 518–529, 2025. Syrgkanis et al. [2015] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning in games. In Proceedings of the 29th Conference on Neural Information Processing Systems (NeurIPS), 2015. Yorulmaz and Başar [2025] Asrın Efe Yorulmaz and Tamer Başar. Near optimal convergence to coarse correlated equilibrium in general-sum Markov games. arXiv preprint arXiv:2511.02157, 2025. Zhang et al. [2021] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. In K. G. Vamvoudakis, Y. Wan, F. L. Lewis, and D. Cansever, editors, Handbook of Reinforcement Learning and Control, pages 321–384. Springer, 2021. Buşoniu et al. [2008] Lucian Buşoniu, Robert Babuska, and Bart De Schutter. A comprehensive survey of multi-agent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), pages 156–172, 2008. Shalev-Shwartz et al. [2016] Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. In Learning, Inference and Control of Multi-Agent Systems Workshop, (NeurIPS), 2016. Park et al. [2025] Chanwoo Park, Seungju Han, Xingzhi Guo, Asuman Ozdaglar, Kaiqing Zhang, and Joo-Kyung Kim. MAPoRL: multi-agent post-co-training for collaborative large language models with reinforcement learning. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (ACL), 2025. Wan et al. [2025] Ziyu Wan, Yunxiang Li, Xiaoyu Wen, Yan Song, Hanjing Wang, Linyi Yang, Mark Schmidt, Jun Wang, Weinan Zhang, Shuyue Hu, and Ying Wen. ReMA: learning to meta-think for LLMs with multi-agent reinforcement learning. In Proceedings of the 39th Conference on Neural Information Processing Systems (NeurIPS), 2025. Zhang et al. [2024] Hengxi Zhang, Zhendong Shi, Yuanquan Hu, Wenbo Ding, Ercan E. Kuruoglu, and Xiao-Ping Zhang. Optimizing trading strategies in quantitative markets using multi-agent reinforcement learning. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2024. Levine et al. [2017] Sergey Levine, Peter Pastor, Alex Krizhevsky, and Deirdre Quillen. Learning hand-eye coordination for robotic grasping with deep learning and large-scale data collection. The International Journal of Robotics Research, 37(4-5):421–436, 2017. Hannan [1957] James Hannan. Approximation to Bayes risk in repeated play. Contributions to the Theory of Games, 3:97–139, 1957. Abbasi-Yadkori et al. [2013] Yasin Abbasi-Yadkori, Peter L. Bartlett, Varun Kanade, Yevgeny Seldin and Csaba Szepesvari. Online learning in Markov decision processes with adversarially chosen transition probability distributions. In Proceedings of the 27th Conference on Neural Information Processing Systems (NeurIPS), 2013. Liu et al. [2022] Qinghua Liu, Yuanhao Wang and Chi Jin. Learning Markov games with adversarial opponents: efficient algorithms and fundamental limits. In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022. Foster et al. [2023] Dylan J. Foster, Noah Golowich and Sham M. Kakade. Hardness of independent learning and sparse equilibrium computation in Markov games. In Proceedings of the 40th International Conference on Machine Learning (ICML), 2023. Herbster and Warmuth [1998] Mark Herbster, and Manfred K. Warmuth. Tracking the best expert. Machine Learning, 32:151–178, 1998 Salem et al. [2024] Tareq Si Salem, Gözde Özcan, Iasonas Nikolaou, Evimaria Terzi and Stratis Ioannidis. Online submodular maximization via online convex optimization. In Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference, 2024. Tian et al. [2021] Yi Tian, Yuanhao Wang, Tiancheng Yu and Suvrit Sra. Online learning in unknown Markov games. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021. Schapire and Freund [1995] Robert E. Schapire and Yoav Freund. A decision-theoretic generalization of on-line learning and an application to boosting. In Computational Learning Theory - 2nd European Conference, EuroCOLT 1995, Proceedings, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pages 23–37. Springer Verlag, 1995. Wei et al. [2021] Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive Markov games. In Proceedings of Thirty Fourth Conference on Learning Theory (COLT), 2021. Daskalakis et al. [2023] Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The Complexity of Markov equilibrium in stochastic games. Proceedings of Thirty Sixth Conference on Learning Theory (COLT), 2023. Jin et al. [2023] Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-Learning—A simple, efficient, decentralized algorithm for multiagent reinforcement learning. Mathematics of Operations Research 49(4):2295-2322, 2023. Silver et al. [2016] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529:484–489, 2016. Brown and Sandholm [2018] Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418–424, 2018. Perolat et al. [2022] Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T. Connor, Neil Burch, Thomas Anthony, Stephen McAleer, Romuald Elie, Sarah H. Cen, Zhe Wang, Audrunas Gruslys, Aleksandra Malysheva, Mina Khan, Sherjil Ozair, Finbarr Timbers, Toby Pohlen, Tom Eccles, Mark Rowland, Marc Lanctot, Jean-Baptiste Lespiau, Bilal Piot, Shayegan Omidshafiei, Edward Lockhart, Laurent Sifre, Nathalie Beauguerlange, Remi Munos, David Silver, Satinder Singh, Demis Hassabis, and Karl Tuyls. Mastering the game of Stratego with model-free multiagent reinforcement learning. Science, 378(6623):990–996, 2022. Kramár et al. [2022] János Kramár, Tom Eccles, Ian Gemp, Andrea Tacchetti, Kevin R. McKee, Mateusz Malinowski, Thore Graepel, and Yoram Bachrach. Negotiation and honesty in artificial intelligence methods for the board game of Diplomacy. Nature Communications, 13:7214, 2022. Bakhtin et al. [2022] Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, Athul Paul Jacob, Mojtaba Komeili, Karthik Konath, Minae Kwon, Adam Lerer, Mike Lewis, Alexander H. Miller, Sasha Mitts, Adithya Renduchintala, Stephen Roller, Dirk Rowe, Weiyan Shi, Joe Spisak, Alexander Wei, David Wu, Hugh Zhang, and Markus Zijlstra. Human-level play in the game of Diplomacy by combining language models with strategic reasoning. Science, 378(6624):1067–1074, 2022. Malialis and Kudenko [2015] Kleanthis Malialis and Daniel Kudenko. Distributed response to network intrusions using multiagent reinforcement learning. Engineering Applications of Artificial Intelligence, 41:270–284, 2015. Zheng et al. [2022] Stephan Zheng, Alexander Trott, Sunil Srinivasa, David C. Parkes, and Richard Socher. The AI Economist: Taxation policy design via two-level deep multiagent reinforcement learning. Science Advances, 8(18), 2022. Daskalakis et al. [2009] Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195–259, 2009. Rubinstein [2016] Aviad Rubinstein. Settling the complexity of computing approximate two-player Nash equilibria. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 258–265, 2016. Foster and Peyton [2006] Dean P. Foster , and H. Peyton Young. Regret testing: learning to play Nash equilibrium without knowing you have an opponent. In Theoretical Economics, 1 (2006), 341–367. Cai et al. [2023] Yang Cai, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback. In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS), 2023. Chen et al. [2024] Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar, Asuman Ozdaglar, and Adam Wierman. Last-Iterate convergence of payoff-based independent learning in zero-sum stochastic games. arXiv preprint arXiv:2409.01447, 2024. Arslan and Yüksel [2017] Gürdal Arslan and Serdar Yüksel. Decentralized Q-learning for stochastic teams and games. IEEE Transactions on Automatic Control, 62(4):1545–1558, 2017. Chen et al. [2009] Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 56(3):1–57, 2009. Daskalakis et al. [2020] Constantinos Daskalakis, Dylan J. Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. In Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS), 2020. Greenwald et al. [2003] Amy Greenwald, and Keith Hall. Correlated-Q learning. In Proceedings of the 20th International Conference on Machine Learning (ICML), 2003. Hu and Wellman [2003] Junling Hu and Michael P. Wellman. Nash Q-learning for general-sum stochastic games. Journal of Machine Learning Research, 4:1039–1069, 2003. Littman [2001] Michael L. Littman. Friend-or-Foe Q-learning in general-sum games. In Proceedings of the 18th International Conference on Machine Learning (ICML), 2001. Sayin et al. [2021] Muhammed O. Sayin, Kaiqing Zhang, David S. Leslie, Tamer Başar, and Asuman Ozdaglar. Decentralized Q-learning in zero-sum Markov games. In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS), 2021. Zhang et al. [2023] Kaiqing Zhang, Sham M. Kakade, Tamer Başar, and Lin F. Yang. Model-based multi-agent reinforcement learning in zero-sum Markov games with near-optimal sample complexity. Journal of Machine Learning Research, 24(1):8286–8338, 2023. Bubeck et al. [2021] Sébastien Bubeck, Ronen Eldan, and Yin Tat Lee. Kernel-based methods for bandit convex optimization. Journal of the ACM, 68(4):1–35, 2021. Agarwal et al. [2017] Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E. Schapire. Corralling a band of bandit algorithms. In Proceedings of the 30th Conference on Learning Theory (COLT), 2017. Wei and Luo [2018] Chen-Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Proceedings of the 31st Conference on Learning Theory (COLT), 2018. Lee et al. [2020] Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei, and Mengxiao Zhang. Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs. In Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS), 2020. Mertikopoulos et al. [2019] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: going the extra (gradient) mile. In International Conference on Learning Representations (ICLR), 2019. Chen and Teboulle [1993] Gong Chen and Marc Teboulle. Convergence analysis of a proximal-like minimization algorithm using Bregman functions. SIAM Journal on Optimization, 3(3):538–543, 1993. Başar and Olsder [1998] Tamer Başar and Geert Jan Olsder. Dynamic Noncooperative Game Theory. SIAM, 1998. Tessler et al. [2019] Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and applications in continuous control. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2019. Huang et al. [2026] Shansong Huang, Virginia R. Young, and Bin Zou, Optimal investment, consumption, and insurance strategies under claim habit. Working paper, 2026. Pérolat et al. [2017] Julien Pérolat, Florian Strub, Bilal Piot, and Olivier Pietquin. Learning Nash equilibrium for general-sum Markov games from batch data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017. Zinkevich et al. [2017] Martin Zinkevich, Amy Greenwald, and Michael L. Littman. Cyclic equilibria in Markov games. In Proceedings of the 19th Conference on Neural Information Processing Systems (NeurIPS), 2005. Babichenko et al. [2016] Yakov Babichenko, Christos Papadimitriou, and Aviad Rubinstein. Can almost everybody be almost happy?. In Proceedings of the ACM Conference on Innovations in Theoretical Computer Science (ITCS), 2016. Papadimitriou [1994] Christos Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498–532, 1994. Liu et al. [2021] Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforcement learning with self-play. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021. Lian et al. [2017] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Proceedings of the 31th Conference on Neural Information Processing Systems (NeurIPS), 2017. Farina et al. [2022] Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung-Wei Lee, Christian Kroer, and Tuomas Sandholm. Near-optimal no-regret learning dynamics for general convex games. In Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS), 2022. Appendix A Related Work The connection between no-regret learning and equilibrium computation is a cornerstone of learning in games. In repeated normal-form games, if every player uses an external no-regret algorithm with regret (Tα)O(T^α), then the empirical distribution of play converges to an (Tα−1)O(T^α-1)-approximate CCE; in two-player zero-sum games this further implies convergence to the saddle-point/Nash value, while swap or internal regret yields CE in general-sum games [Hannan, 1957, Hart and Mas-Colell, 2000, Cesa-Bianchi and Lugosi, 2006, Blum and Mansour, 2007]. Classical online learning algorithms such as multiplicative weights, online mirror descent, and follow-the-regularized-leader provide the underlying no-regret guarantees in the fully adversarial setting, yielding the standard ~(T−1/2) O(T^-1/2) convergence rate to equilibrium [Schapire and Freund, 1995, Nemirovski and Yudin, 1983, Abernethy et al., 2008]. It is known that agents in the adversarial setting can be pessimistic when their learning algorithms interact with one another in self-play Farina et al. [2022]. Starting with the optimistic dynamics of Daskalakis et al. [2011] for two-player zero-sum games and continuing through the RVU framework of Syrgkanis et al. [2015], optimism and stability have emerged as central tools for leveraging this predictability. In normal-form games, optimistic variants of FTRL and OMD, together with their regularized extensions, attain convergence rates to coarse correlated and correlated equilibria that improve upon the baseline ~(T−1/2) O(T^-1/2) rate, with recent results approaching O(1/T)O(1/T) rates in general-sum normal-form games [Rakhlin and Sridharan, 2013, Daskalakis et al., 2021, Anagnostides et al., 2022, Soleymani et al., 2025]. Our work is motivated by this optimistic self-play perspective. However, extending these ideas to Markov games introduces a challenge absent from normal-form games: deviations in the joint policy profile affect not only instantaneous losses but also future state occupancies. Early learning approaches in Markov games were mostly value-based. Specifically, the convergence of Nash-Q learning [Hu and Wellman, 2003] and Friend-or-Foe Q-learning [Littman, 2001], is established only under restrictions on the games encountered during learning. Related approaches based on CE computation further developed this equilibrium-computation perspective while maintaining similar structural requirements [Greenwald et al., 2003]. A separate line of research on decentralized Q-learning with convergence guarantees for weakly acyclic stochastic teams and games also emerged, which includes stochastic team problems, but again relies on strong structural assumptions on the games [Arslan and Yüksel, 2017]. Compared to the general-sum case, the two-player zero-sum structure in Markov games has been studied more thoroughly. There exist tractable algorithms with optimism and value-iteration variants, achieve finite sample-complexity guarantees for learning approximate Nash equilibria [Bai et al., 2020, Zhang et al., 2023]. Policy-optimization methods have also been analyzed in the decentralized learning setting, including independent policy-gradient and optimistic gradient-descent/ascent approaches [Daskalakis et al., 2020, Wei et al., 2021]. Furthermore, Cai et al. [2023], Chen et al. [2024] have developed uncoupled algorithms for two-player zero-sum Markov games with bandit feedback and finite-time last-iterate guarantees, relaxing the coordination and prior-knowledge constraints used in Wei et al. [2021]. From the value-learning angle, Sayin et al. [2021] develops a radically uncoupled Q-learning algorithm for discounted zero-sum Markov games with asymptotic convergence guarantees. Even for multi-player general-sum normal-form games, Nash equilibrium computation is known to be intractable Daskalakis et al. [2009]; and thus in Markov games provably efficient algorithms in the existing literature targets either CE or CCE. For instance, in sample-based MARL literature, V-learning [Jin et al., 2023, Song et al., 2022, Mao and Başar, 2023], SPoCMAR [Daskalakis et al., 2023] and related algorithms are utilized to compute CCE/CE policies in a decentralized setting and avoid the exponential dependence on the number of agents that appears in centralized settings Bai et al. [2020], Liu et al. [2021]. Near-optimal ~(1/T) O(1/T) convergence rates for both CCE and CE obtained in the full-information setting by using either value-based or stage-based policy-optimization schemes [Cai et al., 2024, Mao et al., 2024, Yorulmaz and Başar, 2025]. These results require post-processing of the policies after the learning phase, which relies on the so-called shared randomness. In contrast to our work, their learning phases do not provide any online regret guarantees, making their operating setting simpler than ours since they allow coordination mechanisms among the players. Appendix B Convergence Analysis of Algorithm 1 B.1 Properties of smoothed entropy Lemma 4. Fix a player i∈[m]i∈[m] and a smoothing parameter λi>0 _i>0. Define the smoothed negative-entropy regularizer Ψi(x):=∑a∈Ai(x(a)+λi)log(x(a)+λi),x∈Δ(Ai). _i(x):= _a∈ A_i (x(a)+ _i ) (x(a)+ _i ), x∈ (A_i). Then, Di(x,y)=∑a∈Ai(x(a)+λi)logx(a)+λiy(a)+λi.D_i(x,y)= _a∈ A_i (x(a)+ _i ) x(a)+ _iy(a)+ _i. (2) Moreover, defining ρi:=1+|Ai|λi,ρ¯:=maxi∈[m]ρi, _i:=1+|A_i| _i,\; ρ:= _i∈[m] _i, and Bi:=ρilog1+λiλi,B_i:= _i 1+ _i _i, the following properties hold: 1. Boundedness. For all x,y∈Δ(Ai)x,y∈ (A_i), Di(x,y)≤Bi.D_i(x,y)≤ B_i. 2. Strong convexity. The function Ψi _i is 1/ρi1/ _i-strongly convex with respect to the ∥⋅∥1\|·\|_1 on Δ(Ai) (A_i). Equivalently, for all x,y∈Δ(Ai)x,y∈ (A_i), Di(x,y)≥12ρi‖x−y‖12.D_i(x,y)≥ 12 _i\|x-y\|_1^2. Proof. For each a∈Aia∈ A_i, we have ∇aΨi(x)=log(x(a)+λi)+1. _a _i(x)= (x(a)+ _i )+1. Therefore, Di(x,y) D_i(x,y) =∑a∈Ai(x(a)+λi)log(x(a)+λi)−∑a∈Ai(y(a)+λi)log(y(a)+λi) = _a∈ A_i (x(a)+ _i ) (x(a)+ _i )- _a∈ A_i (y(a)+ _i ) (y(a)+ _i ) −∑a∈Ai(log(y(a)+λi)+1)(x(a)−y(a)). - _a∈ A_i ( (y(a)+ _i)+1 ) (x(a)-y(a) ). Since x,y∈Δ(Ai)x,y∈ (A_i), we have ∑a∈Ai(x(a)−y(a))=0. _a∈ A_i (x(a)-y(a) )=0. The linear terms cancel, and we obtain (2). Next, we prove that DiD_i is a bounded function. For every a∈Aia∈ A_i, x(a)+λi≤1+λi,y(a)+λi≥λi.x(a)+ _i≤ 1+ _i,\;y(a)+ _i≥ _i. Thus, 0≤x(a)+λiy(a)+λi≤1+λiλi⟹Di(x,y)≤∑a∈Ai(x(a)+λi)log1+λiλi.0≤ x(a)+ _iy(a)+ _i≤ 1+ _i _i D_i(x,y)≤ _a∈ A_i (x(a)+ _i ) 1+ _i _i. Since ∑a∈Ai(x(a)+λi)=1+|Ai|λi=ρi, _a∈ A_i (x(a)+ _i )=1+|A_i| _i= _i, (3) DiD_i is bounded above by ρilog((1+λi)/λi)=Bi _i ((1+ _i)/ _i )=B_i. Next, note that the Hessian of Ψi _i is diagonal and given by ∇2Ψi(x)=diag(1/(x(a)+λi))a∈Ai.∇^2 _i(x)=diag (1/(x(a)+ _i) )_a∈ A_i. Thus, for any z∈ℝ|Ai|z ^|A_i|, by Cauchy–Schwarz, ‖z‖12=(∑a∈Ai|z(a)|)2≤(∑a∈Ai(x(a)+λi))(∑a∈Aiz(a)2x(a)+λi)=ρiz⊤∇2Ψi(x)z,\|z\|_1^2= ( _a∈ A_i|z(a)| )^2≤ ( _a∈ A_i(x(a)+ _i) ) ( _a∈ A_i z(a)^2x(a)+ _i )= _i\,z ∇^2 _i(x)z, where the last inequality follows from (3). Therefore, Ψi _i is 1/ρi1/ _i-strongly convex with respect to the ℓ1 _1-norm, which implies Di(x,y)≥12ρi‖x−y‖12.D_i(x,y)≥ 12 _i\|x-y\|_1^2. This completes the proof. ∎ B.2 Properties of OOMD with smoothed entropy Lemma 5. Fix player i, a base point y∈Δ(Ai)y∈ (A_i), and g,g′∈ℝAig,g ^A_i. Define Py(g):=argminx∈Δ(Ai)η⟨g,x⟩+Di(x,y).P_y(g):= *argmin_x∈ (A_i) \η g,x +D_i(x,y) \. Then ‖Py(g)−Py(g′)‖1≤ηρi‖g−g′‖∞. P_y(g)-P_y(g ) _1≤η _i g-g _∞. In particular, ‖Py(g)−y‖1≤ηρi‖g‖∞. P_y(g)-y _1≤η _i g _∞. Proof. The first claim follows from Proposition B.4 in Mertikopoulos et al. [2019]. The second claim follows by taking g′=0g =0 and observing that Py(0)=yP_y(0)=y, where PyP_y is a well-defined function. ∎ Lemma 6. Let ⊆ℝAiX ^A_i be a nonempty closed convex set, and let Ψ:→ℝ :X be a differentiable strictly convex function. Further, let D(x,y):=Ψ(x)−Ψ(y)−⟨∇Ψ(y),x−y⟩,x,y∈,D(x,y):= (x)- (y)- ∇ (y),x-y ,\;x,y , denote the associated Bregman divergence. Now, fix g∈ℝdg ^d and y∈y , and define x+:=argminx∈η⟨g,x⟩+D(x,y).x^+:= *argmin_x \η g,x +D(x,y) \. Then, for every u∈u , η⟨x+−u,g⟩≤D(u,y)−D(u,x+)−D(x+,y).η x^+-u,g ≤ D(u,y)-D(u,x^+)-D(x^+,y). Proof. The claim follows from Lemma 3.2. in Chen and Teboulle [1993]. ∎ Lemma 7. Let xt,x~t∈Δ(Ai)x_t, x_t∈ (A_i) be generated by xt=argminx∈Δ(Ai)η⟨Mt,x⟩+D(x,x~t−1),x_t= *argmin_x∈ (A_i) \η M_t,x +D(x, x_t-1) \, x~t=argminx∈Δ(A)η⟨ℓt,x⟩+D(x,x~t−1), x_t= *argmin_x∈ (A) \η _t,x +D(x, x_t-1) \, where Mt=ℓt−1M_t= _t-1 and ℓ0=0 _0=0. Suppose that the regularizer chosen for the iterations is the smoothed entropy regularizer with parameters λi,ρi=1+|Ai|λi _i, _i=1+|A_i| _i, and Bregman diameter at most B. Then, for any u∈Δ(Ai)u∈ (A_i) and any weights qt∈[0,1]q_t∈[0,1], ∑t=1Tqt⟨xt−u,ℓt⟩≤B(q1+TV(q))η+ηρi2∑t=1Tqt‖ℓt−ℓt−1‖∞2, _t=1^Tq_t x_t-u, _t ≤ B(q_1+TV(q))η+ η _i2 _t=1^Tq_t _t- _t-1 _∞^2, where we define TV(q):=∑t=1T−1|qt+1−qt|.TV(q):= _t=1^T-1|q_t+1-q_t|. Proof. Throughout the proof, we follow steps similar those in Rakhlin and Sridharan [2013], Syrgkanis et al. [2015], Erez et al. [2023]. Since x~t=argminx∈Δ(Ai)η⟨ℓt,x⟩+D(x,x~t−1), x_t= *argmin_x∈ (A_i) \η _t,x +D(x, x_t-1) \, from Lemma 6, for every u∈Δ(Ai)u∈ (A_i), ⟨x~t−u,ℓt⟩≤D(u,x~t−1)−D(u,x~t)η−D(x~t,x~t−1)η. x_t-u, _t ≤ D(u, x_t-1)-D(u, x_t)η- D( x_t, x_t-1)η. (4) Next, decompose ⟨xt−u,ℓt⟩=⟨x~t−u,ℓt⟩+⟨xt−x~t,ℓt⟩. x_t-u, _t = x_t-u, _t + x_t- x_t, _t . Substituting (4) leads to ⟨xt−u,ℓt⟩≤D(u,x~t−1)−D(u,x~t)η+⟨xt−x~t,ℓt⟩−D(x~t,x~t−1)η. x_t-u, _t ≤ D(u, x_t-1)-D(u, x_t)η+ x_t- x_t, _t - D( x_t, x_t-1)η. (5) Now split ⟨xt−x~t,ℓt⟩=⟨xt−x~t,ℓt−Mt⟩+⟨xt−x~t,Mt⟩. x_t- x_t, _t = x_t- x_t, _t-M_t + x_t- x_t,M_t . (6) Since xt=argminx∈Δ(Ai)η⟨Mt,x⟩+D(x,x~t−1),x_t= *argmin_x∈ (A_i) \η M_t,x +D(x, x_t-1) \, another application of Lemma 6, with comparator u=x~tu= x_t, yields ⟨xt−x~t,Mt⟩≤D(x~t,x~t−1)η−D(x~t,xt)η−D(xt,x~t−1)η. x_t- x_t,M_t ≤\; D( x_t, x_t-1)η- D( x_t,x_t)η- D(x_t, x_t-1)η. (7) Substituting (6) and (7) into (5) cancels out the term D(x~t,x~t−1)D( x_t, x_t-1), yielding ⟨xt−u,ℓt⟩≤D(u,x~t−1)−D(u,x~t)η+⟨xt−x~t,ℓt−Mt⟩−D(x~t,xt)η−D(xt,x~t−1)η. x_t-u, _t ≤ D(u, x_t-1)-D(u, x_t)η+ x_t- x_t, _t-M_t - D( x_t,x_t)η- D(x_t, x_t-1)η. Finally, since Bregman divergences are nonnegative, we may drop the final negative term to obtain ⟨xt−u,ℓt⟩≤D(u,x~t−1)−D(u,x~t)η+⟨xt−x~t,ℓt−Mt⟩−D(x~t,xt)η. x_t-u, _t ≤ D(u, x_t-1)-D(u, x_t)η+ x_t- x_t, _t-M_t - D( x_t,x_t)η. Due to Lemma 4, Ψi _i is 1/ρi1/ _i-strongly convex with respect to ℓ1 _1, D(x~t,xt)≥12ρi‖xt−x~t‖12.D( x_t,x_t)≥ 12 _i x_t- x_t _1^2. Therefore, by Young’s inequality, ⟨xt−x~t,ℓt−Mt⟩−D(x~t,xt)η x_t- x_t, _t-M_t - D( x_t,x_t)η ≤‖xt−x~t‖1‖ℓt−Mt‖∞−12ηρi‖xt−x~t‖12≤ηρi2‖ℓt−Mt‖∞2. ≤ x_t- x_t _1 _t-M_t _∞- 12η _i x_t- x_t _1^2≤ η _i2 _t-M_t _∞^2. Since Mt=ℓt−1M_t= _t-1, ⟨xt−u,ℓt⟩≤D(u,x~t−1)−D(u,x~t)η+ηρi2‖ℓt−ℓt−1‖∞2. x_t-u, _t ≤ D(u, x_t-1)-D(u, x_t)η+ η _i2 _t- _t-1 _∞^2. Multiplying by qtq_t and summing up yields ∑t=1Tqt⟨xt−u,ℓt⟩≤1η∑t=1Tqt(Dt−1−Dt)+ηρi2∑t=1Tqt‖ℓt−ℓt−1‖∞2, _t=1^Tq_t x_t-u, _t ≤ 1η _t=1^Tq_t(D_t-1-D_t)+ η _i2 _t=1^Tq_t _t- _t-1 _∞^2, where Dt:=D(u,x~t)D_t:=D(u, x_t). Since 0≤Dt≤B0≤ D_t≤ B, leveraging summation by parts we get, ∑t=1Tqt(Dt−1−Dt) _t=1^Tq_t(D_t-1-D_t) =q1D0−qTDT+∑t=1T−1(qt+1−qt)Dt≤Bq1+BTV(q). =q_1D_0-q_TD_T+ _t=1^T-1(q_t+1-q_t)D_t≤ Bq_1+BTV(q). This completes the proof. ∎ B.3 First order path of the played policies Lemma 8. For every player i, layer h, state s∈Shs∈ S_h, and episode t, ‖πt+1,hi(⋅∣s)−πt,hi(⋅∣s)‖1≤3ρiHηh. π^i_t+1,h(· s)-π^i_t,h(· s) _1≤ 3 _iH _h. Proof. Write xt=xt,hi,sx_t=x^i,s_t,h and x~t=x~t,hi,s x_t= x^i,s_t,h. By Lemma 5, applied with base x~t x_t and loss Qti(s,⋅)Q^i_t(s,·), ‖xt+1−x~t‖1≤ηhρi‖Qt,hi(s,⋅)‖∞≤ηhρiH. x_t+1- x_t _1≤ _h _i Q^i_t,h(s,·) _∞≤ _h _iH. Again applying Lemma 5 to compare the reference point x~t x_t and the played point xtx_t, both generated from the common base point x~t−1 x_t-1 using the losses Qti(s,⋅)Q_t^i(s,·) and Qt−1i(s,⋅)Q_t-1^i(s,·), respectively, we obtain: ‖x~t−xt‖1≤ηhρi‖Qt,hi(s,⋅)−Qt−1,hi(s,⋅)‖∞≤2ηhρiH, x_t-x_t _1≤ _h _i Q^i_t,h(s,·)-Q^i_t-1,h(s,·) _∞≤ 2 _h _iH, because both Q-functions lie in [0,H]Ai[0,H]^A_i. The triangle inequality gives ‖xt+1−xt‖1≤3ρiHηh. x_t+1-x_t _1≤ 3 _iH _h. Since xt=πt,hi(⋅∣s)x_t=π^i_t,h(· s), the claim follows. ∎ For later use, we define ψt,hi:=maxs∈Sh‖πt+1,hi(⋅∣s)−πt,hi(⋅∣s)‖1.ψ^i_t,h:= _s∈ S_h π^i_t+1,h(· s)-π^i_t,h(· s) _1. Therefore, Lemma 8 gives ψt,hi≤3ρ¯Hηh.ψ^i_t,h≤ 3 ρH _h. B.4 History occupancy variation Lemma 9. Fix a player i, a layer h, and a policy μi∈Πigen _i∈ _i^gen. Then, we have, TVhi,μ:=∑t=1T−1‖dt+1,hi,μ−dt,hi,μ‖1≤3mρ¯HT∑ℓ=1h−1ηℓ.TV^i,μ_h:= _t=1^T-1 d^i,μ_t+1,h-d^i,μ_t,h _1≤ 3m ρHT _ =1^h-1 _ . Proof. Given τℓ∈ℋℓ _ _ , ai∈Aia_i∈ A_i, −i∈A−i a_-i∈ A_-i, and s′∈Sℓ+1s ∈ S_ +1, define the next history, τℓ+1=(τℓ,ai,−i,s′)∈ℋℓ+1. _ +1= ( _ ,a_i, a_-i,s ) _ +1. For episode t, define the history transition kernel Kt,ℓi,μ:ℋℓ→Δ(ℋℓ+1)K^i,μ_t, :H_ → (H_ +1) by Kt,ℓi,μ(τℓ+1∣τℓ):=∑ai∈Ai,a−i∈A−i,s′∈Sℓ+1:τℓ+1=(τℓ,ai,−i,s′)μi(ai∣τℓ)t,ℓ−i(−i∣s(τℓ))Pℓ(s′∣s(τℓ),ai,−i),K^i,μ_t, ( _ +1 _ ):= _ subarrayca_i∈ A_i,\;a_-i∈ A_-i,\;s ∈ S_ +1:\\ _ +1= ( _ ,a_i, a_-i,s ) subarrayμ^i(a_i _ )\, π^-i_t, ( a_-i s( _ ))\,P_ (s s( _ ),a_i, a_-i), First, we demonstrate that Kt,ℓi,μK^i,μ_t, is a stochastic kernel. For every fixed τℓ∈ℋℓ _ _ , ∑τℓ+1∈ℋℓ+1Kt,ℓi,μ(τℓ+1∣τℓ) _ _ +1 _ +1K^i,μ_t, ( _ +1 _ ) =∑ai∈Ai∑−i∈A−i∑s′∈Sℓ+1μi(ai∣τℓ)t,ℓ−i(−i∣s(τℓ))Pℓ(s′∣s(τℓ),i,a−i) = _a_i∈ A_i _ a_-i∈ A_-i _s ∈ S_ +1μ^i(a_i _ ) π^-i_t, ( a_-i s( _ ))P_ (s s( _ ), a_i,a_-i) =∑ai∈Aiμi(ai∣τℓ)∑−i∈A−it,ℓ−i(−i∣s(τℓ))∑s′∈Sℓ+1Pℓ(s′∣s(τℓ),i,a−i) = _a_i∈ A_iμ^i(a_i _ ) _ a_-i∈ A_-i π^-i_t, ( a_-i s( _ )) _s ∈ S_ +1P_ (s s( _ ), a_i,a_-i) =1. =1. Now, let dt,hi,μ∈Δ(ℋh)d^i,μ_t,h∈ (H_h) denote the distribution over histories at the beginning of layer h induced by player i using μiμ^i and the opponents using t−i π^-i_t. Denoting by δs∈Δ() _s∈ (S) the probability distribution placing unit mass on s, we have dt,1i,μ=δs1,d^i,μ_t,1= _s_1, For h≥2h≥ 2, di,μt,h=δs1Ki,μt,1Ki,μt,2⋯Ki,μt,h−1.d^i,μ_t,h= _s_1K^i,μ_t,1K^i,μ_t,2·s K^i,μ_t,h-1. Here we view distributions as row vectors and kernels as row-stochastic matrices. We next compare dt+1,hi,μd^i,μ_t+1,h with dt,hi,μd^i,μ_t,h. For notational simplicity, write Kℓ:=Kt,ℓi,μ,Kℓ′:=Kt+1,ℓi,μ.K_ :=K^i,μ_t, ,\;K _ :=K^i,μ_t+1, . Then dt+1,hi,μ−dt,hi,μ d^i,μ_t+1,h-d^i,μ_t,h =δs1(K1′K2′⋯Kh−1′−K1K2⋯Kh−1) = _s_1 (K _1K _2·s K _h-1-K_1K_2·s K_h-1 ) =δs1(∑ℓ=1h−1K1⋯Kℓ−1(Kℓ′−Kℓ)Kℓ+1′⋯Kh−1′). = _s_1 ( _ =1^h-1K_1·s K_ -1(K _ -K_ )K _ +1·s K _h-1 ). Stochastic kernels are ℓ1 _1-contractions on signed measures, i.e., it holds that ‖νK‖1≤‖ν‖1 ν K _1≤ ν _1 for every signed measure ν and every stochastic kernel K. Hence ‖δs1K1⋯Kℓ−1(Kℓ′−Kℓ)Kℓ+1′⋯Kh−1′‖1 _s_1K_1·s K_ -1(K _ -K_ )K _ +1·s K _h-1 _1 ≤‖δs1K1⋯Kℓ−1(Kℓ′−Kℓ)‖1≤‖Kℓ′−Kℓ‖∞,1, ≤ _s_1K_1·s K_ -1(K _ -K_ ) _1≤ K _ -K_ _∞,1, where ‖Kℓ′−Kℓ‖∞,1:=max∑τℓ+1∈ℋℓ+1τℓ∈ℋℓ|Kℓ′(τℓ+1∣τℓ)−Kℓ(τℓ+1∣τℓ)|. K _ -K_ _∞,1:= _ _ _ _ _ +1 _ +1 |K _ ( _ +1 _ )-K_ ( _ +1 _ ) |. Therefore, ‖dt+1,hi,μ−dt,hi,μ‖1 d^i,μ_t+1,h-d^i,μ_t,h _1 ≤∑ℓ=1h−1‖δs1K1⋯Kℓ−1(Kℓ′−Kℓ)Kℓ+1′⋯Kh−1′‖1≤∑ℓ=1h−1‖Kt+1,ℓi,μ−Kt,ℓi,μ‖∞,1. ≤ _ =1^h-1 _s_1K_1·s K_ -1(K _ -K_ )K _ +1·s K _h-1 _1≤ _ =1^h-1 K^i,μ_t+1, -K^i,μ_t, _∞,1. (8) It remains to control the one-layer kernel differences ‖Kt+1,ℓi,μ−Kt,ℓi,μ‖∞,1 K^i,μ_t+1, -K^i,μ_t, _∞,1. Fix τℓ∈ℋℓ _ _ and write s=s(τℓ)s=s( _ ). Since μiμ^i and PℓP_ are the same in episodes t and t+1t+1, only the opponents’ product distribution changes. Therefore, ‖Ki,μt+1,ℓ(⋅∣τℓ)−Ki,μt,ℓ(⋅∣τℓ)‖1 K^i,μ_t+1, (· _ )-K^i,μ_t, (· _ ) _1 =∑τℓ+1∈ℋℓ+1|Kt+1,ℓi,μ(τℓ+1∣τℓ)−Kt,ℓi,μ(τℓ+1∣τℓ)| =\!\!\!\!\!\! _ _ +1 _ +1\!\!\!\!\! |K^i,μ_t+1, ( _ +1 _ )-K^i,μ_t, ( _ +1 _ ) | =∑ai∑−i∑s′μi(ai∣τℓ)Pℓ(s′∣s,ai,−i)|t+1,ℓ−i(−i∣s)−t,ℓ−i(−i∣s)| = _a_i _ a_-i _s μ^i(a_i _ )P_ (s s,a_i, a_-i) | π^-i_t+1, ( a_-i s)- π^-i_t, ( a_-i s) | =∑−i|t+1,ℓ−i(−i∣s)−t,ℓ−i(−i∣s)|∑aiμi(ai∣τℓ)∑s′Pℓ(s′∣s,ai,−i) = _ a_-i | π^-i_t+1, ( a_-i s)- π^-i_t, ( a_-i s) | _a_iμ^i(a_i _ ) _s P_ (s s,a_i, a_-i) =‖−it+1,ℓ(⋅∣s)−it,ℓ(⋅∣s)‖1≤maxs∈Sℓ‖−it+1,ℓ(⋅∣s)−it,ℓ(⋅∣s)‖1. = π^-i_t+1, (· s)- π^-i_t, (· s) _1≤ _s∈ S_ π^-i_t+1, (· s)- π^-i_t, (· s) _1. For product distributions, we have ‖t+1,ℓ−i(⋅∣s)−t,ℓ−i(⋅∣s)‖1≤∑j≠i‖πt+1,ℓj(⋅∣s)−πt,ℓj(⋅∣s)‖1. π^-i_t+1, (· s)- π^-i_t, (· s) _1≤ _j≠ i π^j_t+1, (· s)-π^j_t, (· s) _1. Since, ψt,ℓj:=maxs∈Sℓ‖πt+1,ℓj(⋅∣s)−πt,ℓj(⋅∣s)‖1,ψ^j_t, := _s∈ S_ π^j_t+1, (· s)-π^j_t, (· s) _1, it holds that ‖Kt+1,ℓi,μ−Kt,ℓi,μ‖∞,1≤∑j≠iψt,ℓj. K^i,μ_t+1, -K^i,μ_t, _∞,1≤ _j≠ iψ^j_t, . For all h>1h>1, combining this with (8) gives ‖dt+1,hi,μ−dt,hi,μ‖1≤∑ℓ=1h−1∑j≠iψt,ℓj. d^i,μ_t+1,h-d^i,μ_t,h _1≤ _ =1^h-1 _j≠ iψ^j_t, . In the special case h=1h=1, the distribution is always dt,1i,μ=δs1d^i,μ_t,1= _s_1, and hence ‖dt+1,1i,μ−dt,1i,μ‖1=0. d^i,μ_t+1,1-d^i,μ_t,1 _1=0. Finally, summing over t=1,…,T−1t=1,…,T-1 gives TVhi,μ ^i,μ_h =∑t=1T−1‖dt+1,hi,μ−dt,hi,μ‖1≤∑t=1T−1∑ℓ=1h−1∑j≠iψt,ℓj≤∑ℓ=1h−1∑j≠i3ρ¯HTηℓ≤3mρ¯HT∑ℓ=1h−1ηℓ. = _t=1^T-1 d^i,μ_t+1,h-d^i,μ_t,h _1≤ _t=1^T-1 _ =1^h-1 _j≠ iψ^j_t, ≤ _ =1^h-1 _j≠ i3 ρHT _ ≤ 3m ρHT _ =1^h-1 _ . This completes the proof. ∎ B.5 Variation bounds on the Q-values Lemma 10. Fix a player i and two Markov joint policies =(π1,…,πm),′=(π1′,…,πm′). π=(π^1,…,π^m),\; π =(π^1 ,…,π^m ). Define Δ:=∑j=1m‖πj−πj′‖∞,1, := _j=1^m π^j-π^j _∞,1, where ‖πj−πj′‖∞,1:=maxh,s‖πhj(⋅∣s)−πhj′(⋅∣s)‖1. π^j-π^j _∞,1:= _h,s π^j_h(· s)-π^j _h(· s) _1. Then, for every layer h and state s, ‖Qhi,(s,⋅)−Qhi,′(s,⋅)‖∞≤2H2Δ. Q^i, π_h(s,·)-Q^i, π _h(s,·) _∞≤ 2H^2 . Proof. Fix player i. Define Δh:=maxs‖Qhi,(s,⋅)−Qhi,′(s,⋅)‖∞. _h:= _s Q^i, π_h(s,·)-Q^i, π _h(s,·) _∞. It can be seen that, at layer H+1H+1, both value functions are zero, and hence ΔH+1=0. _H+1=0. Now, fix h≤Hh≤ H, s∈Shs∈ S_h, and ai∈Aia_i∈ A_i. Then, Qhi,(s,ai)−Qhi,′(s,ai)=−i∼h−i[ℓhi+s′Vh+1i,(s′)]−i∼h′−i[ℓhi+s′Vh+1i,′(s′)]. Q^i, π_h(s,a_i)-Q^i, π _h(s,a_i)=E_ a_-i π^-i_h [ ^i_h+E_s V^i, π_h+1(s ) ]-E_ a_-i π -i_h [ ^i_h+E_s V^i, π _h+1(s ) ]. Add and subtract −i∼h−i[ℓhi+s′Vh+1i,′(s′)].E_ a_-i π^-i_h [ ^i_h+E_s V^i, π _h+1(s ) ]. Then, |Qhi,(s,ai)−Qhi,′(s,ai)|≤−i∼h−i|s′[Vh+1i,(s′)−Vh+1i,′(s′)]|⏟future-value difference+|−i∼h−if(−i)−i∼h′−if(−i)|⏟distribution shift, |Q^i, π_h(s,a_i)-Q^i, π _h(s,a_i) |≤ E_ a_-i π^-i_h |E_s [V^i, π_h+1(s )-V^i, π _h+1(s ) ] |_future-value difference+ |E_ a_-i π^-i_hf( a_-i)-E_ a_-i π -i_hf( a_-i) |_distribution shift, where f(−i):=ℓhi(s,ai,−i)+s′Vh+1i,′(s′).f( a_-i):= ^i_h(s,a_i, a_-i)+E_s V^i, π _h+1(s ). For the future-value term, note that |Vh+1i,(s′)−Vh+1i,′(s′)| |V^i, π_h+1(s )-V^i, π _h+1(s ) | =|⟨πih+1(⋅∣s′),Qi,h+1(s′,⋅)⟩−⟨πi′h+1(⋅∣s′),Qi,′h+1(s′,⋅)⟩| = | π^i_h+1(· s ),Q^i, π_h+1(s ,·) - π^i _h+1(· s ),Q^i, π _h+1(s ,·) | ≤|⟨πih+1(⋅∣s′),Qi,h+1(s′,⋅)−Qi,′h+1(s′,⋅)⟩|+|⟨πih+1(⋅∣s′)−πi′h+1(⋅∣s′),Qi,′h+1(s′,⋅)⟩| ≤ | π^i_h+1(· s ),Q^i, π_h+1(s ,·)-Q^i, π _h+1(s ,·) |+ | π^i_h+1(· s )-π^i _h+1(· s ),Q^i, π _h+1(s ,·) | ≤Δh+1+‖πih+1(⋅∣s′)−πi′h+1(⋅∣s′)‖1‖Qi,′h+1(s′,⋅)‖∞. ≤ _h+1+ \|π^i_h+1(· s )-π^i _h+1(· s ) \|_1 \|Q^i, π _h+1(s ,·) \|_∞. Since per-layer losses lie in [0,1][0,1], the remaining loss from layer h+1h+1 to layer H is at most H−hH-h. Therefore ‖Qh+1i,′(s′,⋅)‖∞≤H−h≤H. \|Q^i, π _h+1(s ,·) \|_∞≤ H-h≤ H. Thus, |Vh+1i,(s′)−Vh+1i,′(s′)|≤Δh+1+H‖πh+1i(⋅∣s′)−πh+1i′(⋅∣s′)‖1≤Δh+1+HΔ. |V^i, π_h+1(s )-V^i, π _h+1(s ) |≤ _h+1+H \|π^i_h+1(· s )-π^i _h+1(· s ) \|_1≤ _h+1+H . Therefore, −i∼h−i|s′[Vh+1i,(s′)−Vh+1i,′(s′)]|≤Δh+1+HΔ.E_ a_-i π^-i_h |E_s [V^i, π_h+1(s )-V^i, π _h+1(s )] |≤ _h+1+H . For the distribution-shift term, since ‖f‖∞≤H\|f\|_∞≤ H, we have |−i∼h−if(−i)−i∼h′−if(−i)|≤H‖−ih(⋅∣s)−h′−i(⋅∣s)‖1. |E_ a_-i π^-i_hf( a_-i)-E_ a_-i π -i_hf( a_-i) |≤ H\, π^-i_h(· s)- π_h -i(· s) _1. Using the product-distribution inequality, ‖h−i(⋅∣s)−h′−i(⋅∣s)‖1≤∑j≠i‖πhj(⋅∣s)−πhj′(⋅∣s)‖1≤Δ. π^-i_h(· s)- π_h -i(· s) _1≤ _j≠ i π^j_h(· s)- _h^j (· s) _1≤ . Hence Δh≤Δh+1+2HΔ. _h≤ _h+1+2H . Since ΔH+1=0, _H+1=0, backward induction yields Δh≤2H(H−h+1)Δ. _h≤ 2H(H-h+1) . In particular, it holds that Δh≤2H2Δ. _h≤ 2H^2 . ∎ Lemma 11. For every player i, state s, layer h, and episode t≥2t≥ 2, ‖Qt,hi(s,⋅)−Qt−1,hi(s,⋅)‖∞2≤36m2ρ¯2H6ηH2, Q^i_t,h(s,·)-Q^i_t-1,h(s,·) _∞^2≤ 36m^2 ρ^2H^6 _H^2, and, with Q0,hi(s,⋅)=0Q^i_0,h(s,·)=0, ‖Q1,hi(s,⋅)−Q0,hi(s,⋅)‖∞2≤H2. Q^i_1,h(s,·)-Q^i_0,h(s,·) _∞^2≤ H^2. Proof. The Lemma 10 bound gives ‖Qt,hi(s,⋅)−Qt−1,hi(s,⋅)‖∞≤2H2∑j=1m‖πtj−πt−1j‖∞,1=2H2∑j=1mmaxh,s∈Sh‖πt,hj(⋅∣s)−πt−1,hj(⋅∣s)‖1. Q^i_t,h(s,·)-Q^i_t-1,h(s,·) _∞≤ 2H^2 _j=1^m π^j_t-π^j_t-1 _∞,1=2H^2 _j=1^m _h,s∈ S_h π^j_t,h(· s)-π^j_t-1,h(· s) _1. By Lemma 8 and the monotonicity η1≤⋯≤ηH _1≤·s≤ _H, it holds that ‖πtj−πt−1j‖∞,1≤3ρ¯HηH, π^j_t-π^j_t-1 _∞,1≤ 3 ρH _H, which directly implies the desired result. ∎ B.6 Weighted value-difference decomposition Lemma 12. Fix a player i, an episode t, and a policy μi∈Πigen _i∈ _i^gen. Fix the opponents’ profile t−i π^-i_t. Then, Vi,πt,1(s1)−Vi,μit,1(s1)=∑h=1H∑τh∈ℋhdi,μt,h(τh)⟨Qit,h(s(τh),⋅),πih(⋅∣s(τh))−μi,h(⋅∣τh)⟩. V^i,π_t,1(s_1)-V^i, _i_t,1(s_1)= _h=1^H _ _h _hd^i,μ_t,h( _h) Q^i_t,h(s( _h),·),π^i_h(· s( _h))- _i,h(· _h) . Proof. Let Wh(τh)W_h( _h) denote the expected continuation loss from history τh∈ℋh _h _h when player i follows the comparator μi _i from layer h onward and the opponents follow t−i π^-i_t. Thus WH+1(τH+1)=0,W_H+1( _H+1)=0, and for τh∈ℋh _h _h with current state s=s(τh)s=s( _h), Wh(τh)=∑ai∈Aiμi,h(ai∣τh)[ℓt,hi(s,ai)+∑s′∈Sh+1Pt,h(s′∣s,ai)Wh+1(τh+1)]. W_h( _h)= _a_i∈ A_i _i,h(a_i _h) [ ^i_t,h(s,a_i)+ _s ∈ S_h+1P_t,h(s s,a_i)W_h+1( _h+1) ]. where τh+1=(τh,ai,−i,s′) _h+1=( _h,a_i, a_-i,s ) denotes the next history after player i chooses aia_i, the opponents’ policies are according to t−i π^-i_t, and the next state is s′s . Then, for every history τh∈ℋh _h _h with s=s(τh)s=s( _h), we have Vt,hi,π(s)−Wh(τh) V^i,π_t,h(s)\!-\!W_h( _h) =⟨Qit,h(s,⋅),πih(⋅∣s)⟩−∑ai∈Aiμi,h(ai∣τh)[ℓit,h(s,ai)+∑s′∈Sh+1Pt,h(s′∣s,ai)Wh+1(τh+1)]. =\! Q^i_t,h(s,·),π^i_h(·\! \!s) \!-\!\!\! _a_i∈ A_i\!\! _i,h(a_i\! \! _h)\! [ ^i_t,h(s,a_i)\!+\!\!\!\!\! _s ∈ S_h+1\!\!\!\!\!P_t,h(s \!\! \!s,a_i)W_h+1( _h+1) ]. =⟨Qit,h(s,⋅),πih(⋅∣s)−μi,h(⋅∣τh)⟩ = Q^i_t,h(s,·),π^i_h(· s)- _i,h(· _h) +∑ai∈Aiμi,h(ai∣τh)∑s′∈Sh+1Pt,h(s′∣s,ai)[Vi,πit,h+1(s′)−Wh+1(τh+1)]. + _a_i∈ A_i _i,h(a_i _h) _s ∈ S_h+1P_t,h(s s,a_i) [V^i,π^i_t,h+1(s )-W_h+1( _h+1) ]. =⟨Qit,h(s(τh),⋅),πih(⋅∣s(τh))−μi,h(⋅∣τh)⟩ = Q^i_t,h(s( _h),·),π^i_h(· s( _h))- _i,h(· _h) +[Vi,πt,h+1(s(τh+1))−Wh+1(τh+1)|τh,μi,−it]. +E [V^i,π_t,h+1(s( _h+1))-W_h+1( _h+1)\, |\, _h, _i, π^-i_t ]. Now taking expectation with respect to τh∼dt,hi,μ _h d^i,μ_t,h, we get, τh∼dt,hi,μ[Vt,hi,π(s(τh))−Wh(τh)]= _ _h d^i,μ_t,h [V^i,π_t,h(s( _h))-W_h( _h) ]= ∑τh∈ℋhdi,μt,h(τh)⟨Qit,h(s(τh),⋅),πih(⋅∣s(τh))−μi,h(⋅∣τh)⟩ _ _h _hd^i,μ_t,h( _h) Q^i_t,h(s( _h),·),π^i_h(· s( _h))- _i,h(· _h) +τh+1∼dt,h+1i,μ[Vt,h+1i,π(s(τh+1))−Wh+1(τh+1)]. +E_ _h+1 d^i,μ_t,h+1 [V^i,π_t,h+1(s( _h+1))-W_h+1( _h+1) ]. Summing this identity over h=1,…,Hh=1,…,H telescopes the terms. At the initial layer, dt,1i,μ=δs1d^i,μ_t,1= _s_1, and thus τ1∼dt,1i,μ[Vt,1i,π(s(τ1))−W1(τ1)]=Vt,1i,π(s1)−Vt,1i,μi(s1).E_ _1 d^i,μ_t,1 [V^i,π_t,1(s( _1))-W_1( _1) ]=V^i,π_t,1(s_1)-V^i, _i_t,1(s_1). At layer H+1H+1, both continuation values are zero, i.e. Vt,H+1i,π≡0,WH+1≡0.V^i,π_t,H+1≡ 0,\;W_H+1≡ 0. Therefore, Vi,πt,1(s1)−Vi,μit,1(s1)=∑h=1H∑τh∈ℋhdi,μt,h(τh)⟨Qit,h(s(τh),⋅),πih(⋅∣s(τh))−μi,h(⋅∣τh)⟩. V^i,π_t,1(s_1)-V^i,μ^i_t,1(s_1)= _h=1^H _ _h _hd^i,μ_t,h( _h) Q^i_t,h(s( _h),·),π^i_h(· s( _h))- _i,h(· _h) . This completes the proof. ∎ B.7 Proof of Theorem 1 Fix a player i and an arbitrary comparator policy μi∈Πigen _i∈ _i^gen. For each layer h, define Ri,h(μi):=∑τh∈ℋh∑t=1Tdi,μt,h(τh)⟨Qit,h(s(τh),⋅),πit,h(⋅∣s(τh))−μi,h(⋅∣τh)⟩. R_i,h( _i):= _ _h _h _t=1^Td^i,μ_t,h( _h) Q^i_t,h(s( _h),·),π^i_t,h(· s( _h))- _i,h(· _h) . Now, apply Lemma 7 separately for every history τh∈ℋh _h _h, with xt=πt,hi(⋅∣s(τh)),u=μi,h(⋅∣τh),ℓt=Qt,hi(s(τh),⋅),qt=dt,hi,μ(τh),x_t=π^i_t,h(· s( _h)),\;u= _i,h(· _h),\; _t=Q^i_t,h(s( _h),·),\;q_t=d^i,μ_t,h( _h), and learning rate ηh _h. Summing over τ∈ℋhτ _h yields Ri,h(μi) R_i,h( _i) ≤Biηh∑τh∈ℋh(d1,hi,μ(τh)+∑t=1T−1|dt+1,hi,μ(τh)−dt,hi,μ(τh)|) ≤ B_i _h _ _h _h (d^i,μ_1,h( _h)+ _t=1^T-1|d^i,μ_t+1,h( _h)-d^i,μ_t,h( _h)| ) +ηhρi2∑τh∈ℋh∑t=1Tdi,μt,h(τh)‖Qit,h(s(τh),⋅)−Qit−1,h(s(τh),⋅)‖∞2. + _h _i2 _ _h _h _t=1^Td^i,μ_t,h( _h) Q^i_t,h(s( _h),·)-Q^i_t-1,h(s( _h),·) _∞^2. Since ∑τh∈ℋhd1,hi,μ(τh)=1 _ _h _hd^i,μ_1,h( _h)=1 and is the same at every episode, Lemma 11 gives Ri,h(μi)≤Bi(1+TVhi,μ)ηh+12ηhρiH2+18ηhρim2ρ¯2H6ηH2T.R_i,h( _i)≤ B_i(1+TV^i,μ_h) _h+ 12 _h _iH^2+18 _h _im^2 ρ^2H^6 _H^2T. We now sum over h. First, ∑h=1HBiηh=Biη0∑h=1HTαh≤HBiη0Tβ. _h=1^H B_i _h= B_i _0 _h=1^HT _h≤ HB_i _0T^β. Second, for h≥2h≥ 2, Lemma 9 gives BiTVhi,μηh≤3mBiρ¯HT∑ℓ=1h−1ηℓηh. B_iTV^i,μ_h _h≤ 3mB_i ρHT _ =1^h-1 _ _h. Since η1≤⋯≤ηH _1≤·s≤ _H, ∑ℓ=1h−1ηℓ≤Hηh−1. _ =1^h-1 _ ≤ H _h-1. Moreover, ηh−1ηh=T−(αh−1−αh)=T−3/(3H+1). _h-1 _h=T^-( _h-1- _h)=T^-3/(3H+1). Therefore, BiTVhi,μηh≤3mBiρ¯H2T1−3/(3H+1)=3mBiρ¯H2Tβ, B_iTV^i,μ_h _h≤ 3mB_i ρH^2T^1-3/(3H+1)=3mB_i ρH^2T^β, and hence ∑h=1HBiTVhi,μηh≤3mBiρ¯H3Tβ. _h=1^H B_iTV^i,μ_h _h≤ 3mB_i ρH^3T^β. Third, ∑h=1H12ηhρiH2≤12ρiH2⋅HηH≤12η0ρiH3Tβ, _h=1^H 12 _h _iH^2≤ 12 _iH^2· H _H≤ 12 _0 _iH^3T^β, where we used T−αH≤TβT^- _H≤ T^β for T≥1T≥ 1. Fourth, ∑h=1H18ηhρim2ρ¯2H6ηH2T _h=1^H18 _h _im^2 ρ^2H^6 _H^2T =18ρim2ρ¯2H6TηH2∑h=1Hηh≤18ρim2ρ¯2H6TηH2⋅HηH =18 _im^2 ρ^2H^6T _H^2 _h=1^H _h≤ 18 _im^2 ρ^2H^6T _H^2· H _H ≤18η03ρim2ρ¯2H7T1−3αH ≤ 18 _0^3 _im^2 ρ^2H^7T^1-3 _H ≤18η03ρim2ρ¯2H7Tβ, ≤ 18 _0^3 _im^2 ρ^2H^7T^β, where the last line follows from αH=1/(3H+1) _H=1/(3H+1), 1−3αH=3H−23H+1=β.1-3 _H= 3H-23H+1=β. Choosing λi=1|Ai|, _i= 1|A_i|, gives ρi=1+|Ai|λi=2,ρ¯=2, _i=1+|A_i| _i=2,\; ρ=2, and Bi=2log(|Ai|+1).B_i=2 (|A_i|+1). Combining all four pieces results in ∑h=1HRi,h(μi) _h=1^HR_i,h( _i) ≤(HBiη0+3mBiρ¯H3+12η0ρiH3+18η03ρim2ρ¯2H7)Tβ. ≤ ( HB_i _0+3mB_i ρH^3+ 12 _0 _iH^3+18 _0^3 _im^2 ρ^2H^7 )T^β. ≤(2Hlog(|Ai|+1)η0+12mH3log(|Ai|+1)+η0H3+144η03m2H7)Tβ. ≤ ( 2H (|A_i|+1) _0+12mH^3 (|A_i|+1)+ _0H^3+144 _0^3m^2H^7 )T^β. Define CiSE:=2Hlog(|Ai|+1)η0+12mH3log(|Ai|+1)+η0H3+144η03m2H7.C_i^SE:= 2H (|A_i|+1) _0+12mH^3 (|A_i|+1)+ _0H^3+144 _0^3m^2H^7. By Lemma 12, we have ∑t=1T(Vt,1i,π(s1)−Vt,1i,μi(s1))=∑h=1HRi,h(μi). _t=1^T (V^i,π_t,1(s_1)-V^i, _i_t,1(s_1) )= _h=1^HR_i,h( _i). The left-hand side is precisely the regret of player i with respect to the comparator policy μi _i. Since the bound on ∑t=1T(Vt,1i,π(s1)−Vt,1i,μi(s1)) _t=1^T (V^i,π_t,1(s_1)-V^i, _i_t,1(s_1) ) holds uniformly for all μi∈Πigen _i∈ _i^gen, taking the supremum over μi∈Πigen _i∈ _i^gen yields RegTgen,i=supμi∈Πigen∑t=1T(Vt,1i,π(s1)−Vt,1i,μi(s1))≤CiSETβ,β=3H−23H+1.Reg^gen,i_T= _ _i∈ _i^gen _t=1^T (V^i,π_t,1(s_1)-V^i, _i_t,1(s_1) )≤ C_i^SET^β, β= 3H-23H+1. Now we let C∗SE:=maxi∈[m]CiSE,Tε:=⌈(C∗SEε)(3H+1)/3⌉.C_*^SE:= _i∈[m]C_i^SE,\;T_ := ( C_*^SE )^(3H+1)/3 . In particular, since β−1=−3/(3H+1)β-1=-3/(3H+1), this choice ensures that, for every player i∈[m]i∈[m], RegTεgen,iTε≤CiSETε−3/(3H+1)≤C∗SETε−3/(3H+1)≤ε. Reg^gen,i_T_ T_ ≤ C_i^SET_ ^-3/(3H+1)≤ C_*^SET_ ^-3/(3H+1)≤ . Equivalently, RegTεgen,i≤εTε.Reg^gen,i_T_ ≤ T_ . The ε -CCE guarantee follows by applying the standard no-regret-to-CCE equivalence to the empirical distribution Π^Tε _T_ [Cesa-Bianchi and Lugosi, 2006]. Appendix C Convergence Analysis of Algorithm 2 C.1 Comparator smoothing Algorithm 2 plays policies in the restricted simplex Δiζ _i^ζ. We therefore first compare an arbitrary history-dependent policy with its ζ-smoothed version. For μi∈Πigenμ^i∈ _i^gen, define μhi,ζ(⋅∣τh):=(1−ζ)μhi(⋅∣τh)+ζUnif(Ai),h∈[H],τh∈ℋh. _h^i,ζ(· _h):=(1-ζ) _h^i(· _h)+ζ\,Unif(A_i), h∈[H],\ _h _h. Then μhi,ζ(⋅∣τh)∈Δiζ _h^i,ζ(· _h)∈ _i^ζ for every admissible history, and we have the following guarantee for the smoothing. Lemma 13. Fix player i, a product Markov opponent profile −i π^-i, and a history-dependent policy μi∈Πigenμ^i∈ _i^gen. Consequently, for every product Markov profile π, it holds that Vt,1i,π(s1)−Vt,1i,μi(s1)≤Vt,1i,π(s1)−Vt,1i,μi,ζ(s1)+2ζH2.V^i,π_t,1(s_1)-V^i,μ^i_t,1(s_1)≤ V^i,π_t,1(s_1)-V^i,μ^i,ζ_t,1(s_1)+2ζ H^2. Proof. For r=0,1,…,Hr=0,1,…,H, define a policy νi,rν^i,r by νhi,r(⋅∣τh):=μhi,ζ(⋅∣τh),h≤r,μhi(⋅∣τh),h>r. _h^i,r(· _h):= cases _h^i,ζ(· _h),&h≤ r,\\ _h^i(· _h),&h>r. cases Then νi,0=μiν^i,0=μ^i and νi,H=μi,ζν^i,H=μ^i,ζ. Hence Vt,1i,μi,ζ(s1)−Vt,1i,μi(s1)=∑r=1H[Vt,1i,νi,r(s1)−Vt,1i,νi,r−1(s1)]. V_t,1^i,μ^i,ζ(s_1)-V_t,1^i,μ^i(s_1)= _r=1^H [V_t,1^i,ν^i,r(s_1)-V_t,1^i,ν^i,r-1(s_1) ]. (9) The policies νi,rν^i,r and νi,r−1ν^i,r-1 agree on all layers ℓ<r <r, and their only possible difference is at layer r. For τr∈ℋr _r _r, let Qt,ri(s(τr),⋅)Q^i_t,r(s( _r),·) denote the Q-function whose aia_i-th coordinate is the expected payoff obtained by taking aia_i at τr _r, then following πiπ^i, while the opponents follow −i π^-i. Since the remaining total cost is at most H, ‖Qt,ri(s(τr),⋅)‖∞≤H.\|Q^i_t,r(s( _r),·)\|_∞≤ H. Moreover, by the definition of the smoothed policy, μri,ζ(⋅∣τr)−μri(⋅∣τr)=ζ(Unif(Ai)−μri(⋅∣τr)). _r^i,ζ(· _r)- _r^i(· _r)=ζ (Unif(A_i)- _r^i(· _r) ). Hence, ‖μri,ζ(⋅∣τr)−μri(⋅∣τr)‖1=ζ‖Unif(Ai)−μri(⋅∣τr)‖1≤2ζ. \| _r^i,ζ(· _r)- _r^i(· _r) \|_1=ζ \|Unif(A_i)- _r^i(· _r) \|_1≤ 2ζ. Thus, by Lemma 12 |Vt,1i,νi,r(s1)−Vt,1i,νi,r−1(s1)| |V_t,1^i,ν^i,r(s_1)-V_t,1^i,ν^i,r-1(s_1) | ≤∑τr∈ℋrdt,ri,νi,r−1(τr)∥Qt,r(τr,⋅)∥∞‖μri,ζ(⋅∣τr)−μri(⋅∣τr)‖1 ≤ _ _r _rd_t,r^i,ν^i,r-1( _r)\|Q_t,r( _r,·)\|_∞ \| _r^i,ζ(· _r)- _r^i(· _r) \|_1 ≤∑τr∈ℋrdt,ri,νi,r−1(τr)⋅H⋅2ζ=2ζH. ≤ _ _r _rd_t,r^i,ν^i,r-1( _r)· H· 2ζ=2ζ H. Summing over r=1,…,Hr=1,…,H by (9) we obtain |Vt,1i,μi,ζ(s1)−Vt,1i,μi(s1)|≤2ζH2. |V_t,1^i,μ^i,ζ(s_1)-V_t,1^i,μ^i(s_1) |≤ 2ζ H^2. The final claim follows by adding and subtracting Vt,1i,μi,ζ(s1)V_t,1^i,μ^i,ζ(s_1) to Vt,1i,π(s1)−Vt,1i,μi(s1)V^i,π_t,1(s_1)-V^i,μ^i_t,1(s_1). ∎ C.2 Uniform estimation of Q-values At block k, conditional on the past, the block policy πk _k is fixed and the B trajectories in that block are independent. The reachability condition, together with the action-probability floor for player i, gives a uniform lower bound on the probability of observing each state–player-i-action pair. We state the resulting estimation guarantee for the player-i Q-function estimates as follows. Lemma 14. Fix K,B∈ℕK,B , δ∈(0,1)δ∈(0,1), and ξ>0ξ>0. MK:=KmAmaxS,uK:=log4MKδ,nQ:=⌈H22ξ2uK⌉,pmin:=κζAmax.M_K:=KmA_ S,\;u_K:= 4M_Kδ,\;n_Q:= H^22ξ^2u_K ,\;p_ := κζA_ . If B≥⌈8pmin(nQ+uK)⌉,B≥ 8p_ (n_Q+u_K) , then, with probability at least 1−δ1-δ, maxk∈[K],i∈[m],h∈[H],s∈Sh,a∈Ai|Q^k,hi(s,a)−Qk,hi(s,a)|≤ξ. _ subarrayck∈[K],i∈[m],h∈[H],\\ s∈ S_h,a∈ A_i subarray | Q_k,h^i(s,a)-Q_k,h^i(s,a) |≤ξ. Proof. First, fix a tuple (k,i,h,s,ai)(k,i,h,s,a_i), with s∈Shs∈ S_h. Then, let ℱk−1F_k-1 be the sigma-field generated by all randomness before block k. Let ℙP denote the probability measure induced by Algorithm 2 and the game itself. Conditional on ℱk−1F_k-1 under ℙP, the policy πk _k is fixed and the B trajectories in block k are independent. For episode r∈[B]r∈[B], define Xr:=shk,r=s,ahi,k,r=ai,X_r:=1\s_h^k,r=s,\ a_h^i,k,r=a_i\, thus Nk,i(s,ai)=∑r=1BXrN_k,i(s,a_i)= _r=1^BX_r by (1). Then, by Definition 1 conditional on ℱk−1F_k-1, the random variables X1,…,XBX_1,…,X_B are i.i.d. Bernoulli random variables with success probability pk,i,h,s,ai:=ℙ(shk,r=s,ahi,k,r=ai∣ℱk−1).p_k,i,h,s,a_i:=P(s_h^k,r=s,a_h^i,k,r=a_i _k-1). By the reachability assumption and the action-floor condition, pk,i,h,s,ai=ℙ(shk,r=s∣ℱk−1)πk,hi(ai∣s)≥κζ|Ai|≥κζAmax=:pminp_k,i,h,s,a_i=P(s_h^k,r=s _k-1) _k,h^i(a_i s)≥κ ζ|A_i|≥ κζA_ =:p_ ℙP-almost surely. Hence, under the conditional law ℙ(⋅∣ℱk−1)P(· _k-1), Nk,i(s,ai)∼Bin(B,pk,i,h,s,ai),pk,i,h,s,ai≥pminℙ-a.s.N_k,i(s,a_i) (B,p_k,i,h,s,a_i), p_k,i,h,s,a_i≥ p_ -a.s. Since the lower-tail probability of a binomial random variable is nonincreasing in its success probability, it follows that, for every threshold n, ℙ(Nk,i(s,ai)<n∣ℱk−1)≤Pr(Bin(B,pmin)<n)P\! (N_k,i(s,a_i)<n _k-1 )≤ \! (Bin(B,p_ )<n ) ℙP-almost surely. Since Bpmin≥8(nQ+uK)Bp_ ≥ 8(n_Q+u_K), we have nQ≤Bpmin/2n_Q≤ Bp_ /2. Therefore, Chernoff’s inequality gives ℙ(Nk,i(s,ai)<nQ∣ℱk−1) \! (N_k,i(s,a_i)<n_Q _k-1 ) ≤Pr(Bin(B,pmin)<12Bpmin) ≤ \! (Bin(B,p_ )< 12Bp_ ) ≤exp(−Bpmin8)≤e−uK, ≤ \! (- Bp_ 8 )≤ e^-u_K, ℙP-almost surely. Now, let A:=Nk,i(s,ai)≥nQ.A:=\N_k,i(s,a_i)≥ n_Q\. On A, the estimator is Q^k,hi(s,ai)=1Nk,i(s,ai)∑r=1BXrYhi,k,r. Q_k,h^i(s,a_i)= 1N_k,i(s,a_i) _r=1^BX_rY_h^i,k,r. Fix a realization x1,…,xB∈0,1x_1,…,x_B∈\0,1\ with ∑r=1Bxr≥nQ _r=1^Bx_r≥ n_Q. Conditional on ℱk−1F_k-1 and on Xr=xr,r∈[B]\X_r=x_r,\ r∈[B]\, the variables Yhi,k,r:xr=1\Y_h^i,k,r:x_r=1\ are independent, since the B trajectories in block k are conditionally independent. Moreover, for each r with xr=1x_r=1, [Yhi,k,r|ℱk−1,shk,r=s,ahi,k,r=ai] \! [Y_h^i,k,r\, |\,F_k-1,\ s_h^k,r=s,\ a_h^i,k,r=a_i ] =[∑τ=hHℓτi(sτk,r,τk,r)|ℱk−1,shk,r=s,ahi,k,r=ai] =E\! [ _τ=h^H _τ^i(s_τ^k,r, a_τ^k,r)\, |\,F_k-1,\ s_h^k,r=s,\ a_h^i,k,r=a_i ] =Qk,hi(s,ai). =Q_k,h^i(s,a_i). as conditional on ℱk−1F_k-1, the policy πk _k is fixed, so the conditional expected tail cost from layer h onward is precisely the state-action value Qk,hi(s,ai)Q_k,h^i(s,a_i). Also, Yhi,k,r∈[0,H]Y_h^i,k,r∈[0,H]. Therefore, Hoeffding’s inequality gives ℙ(|1∑r=1Bxr∑r=1BxrYhi,k,r−Qk,hi(s,ai)|>ξ|ℱk−1,Xr=xr,r∈[B])≤2exp(−2nQξ2H2).P\! ( | 1 _r=1^Bx_r _r=1^Bx_rY_h^i,k,r-Q_k,h^i(s,a_i) |>ξ\, |\,F_k-1,\ X_r=x_r,\ r∈[B] )≤ 2 \! (- 2n_Qξ^2H^2 ). Averaging over all realizations x1,…,xBx_1,…,x_B with ∑r=1Bxr≥nQ _r=1^Bx_r≥ n_Q, we obtain ℙ(|Q^k,hi(s,ai)−Qk,hi(s,ai)|>ξ,A|ℱk−1)≤2exp(−2nQξ2H2)≤2e−uK.P\! ( | Q_k,h^i(s,a_i)-Q_k,h^i(s,a_i) |>ξ,\ A\, |\,F_k-1 )≤ 2 \! (- 2n_Qξ^2H^2 )≤ 2e^-u_K. Combining the bound on Ac=Nk,i(s,ai)<nQA^c=\N_k,i(s,a_i)<n_Q\ with the bound on the estimation error on A, we obtain, for the fixed tuple (k,i,h,s,ai)(k,i,h,s,a_i), ℙ(|Q^k,hi(s,ai)−Qk,hi(s,ai)|>ξ|ℱk−1) \! ( | Q_k,h^i(s,a_i)-Q_k,h^i(s,a_i) |>ξ\, |\,F_k-1 ) ≤ℙ(Ac∣ℱk−1)+ℙ(|Q^k,hi(s,ai)−Qk,hi(s,ai)|>ξ,A|ℱk−1) \! (A^c _k-1 )+P\! ( | Q_k,h^i(s,a_i)-Q_k,h^i(s,a_i) |>ξ,\ A\, |\,F_k-1 ) ≤e−uK+2e−uK=3e−uK, ≤ e^-u_K+2e^-u_K=3e^-u_K, ℙP-almost surely. Taking expectations on both sides gives the unconditional bound ℙ(|Q^k,hi(s,ai)−Qk,hi(s,ai)|>ξ)≤3e−uK.P\! ( | Q_k,h^i(s,a_i)-Q_k,h^i(s,a_i) |>ξ )≤ 3e^-u_K. Now take a union bound over all tuples (k,i,h,s,ai)withk∈[K],i∈[m],h∈[H],s∈Sh,ai∈Ai.(k,i,h,s,a_i)\;with\;k∈[K],\ i∈[m],\ h∈[H],\ s∈ S_h,a_i∈ A_i. The number of such tuples is at most MK=KmAmaxSM_K=KmA_ S. Therefore, ℙ(maxk∈[K],i∈[m],h∈[H],s∈Sh,ai∈Ai|Q^k,hi(s,ai)−Qk,hi(s,ai)|>ξ)≤3MKe−uK=3MKδ4MK≤δ. \! ( _ subarrayck∈[K],i∈[m],h∈[H],\\ s∈ S_h,\ a_i∈ A_i subarray | Q_k,h^i(s,a_i)-Q_k,h^i(s,a_i) |>ξ )≤ 3M_Ke^-u_K=3M_K δ4M_K≤δ. Equivalently, with probability at least 1−δ1-δ, maxk∈[K],i∈[m],h∈[H],s∈Sh,ai∈Ai|Q^k,hi(s,ai)−Qk,hi(s,ai)|≤ξ. _ subarrayck∈[K],i∈[m],h∈[H],\\ s∈ S_h,\ a_i∈ A_i subarray | Q_k,h^i(s,a_i)-Q_k,h^i(s,a_i) |≤ξ. This proves the result. ∎ C.3 Regret with uniformly accurate estimates We next prove a deterministic regret bound for Algorithm 2 on the event that all estimated Q-vectors are uniformly accurate. Define ℰξ:=maxk,i,h,s,ai|Q^k,hi(s,ai)−Qk,hi(s,ai)|≤ξ.E_ξ:= \ _k,i,h,s,a_i | Q_k,h^i(s,a_i)-Q_k,h^i(s,a_i) |≤ξ \. On this event, the regret analysis of the estimated-Q functions differs from the full-feedback case only through the estimation-error terms that appear. Proposition 2. Suppose Algorithm 2 is run for K blocks. On the event ℰξE_ξ, for every player i∈[m]i∈[m], supμi∈Πigen1K∑k=1K[Vk,1i,π(s1)−Vk,1i,μi(s1)]≤ _μ^i∈ _i^gen 1K _k=1^K [V^i,π_k,1(s_1)-V^i,μ^i_k,1(s_1) ]≤ C~iSEK−3/(3H+1)+2Hξ+2ζH2+8η0Hξ2K−αH, C_i^SEK^-3/(3H+1)+2Hξ+2ζ H^2+8 _0Hξ^2K^- _H, where C~iSE:=2Hlog(|Ai|+1)η0+12mH3log(|Ai|+1)+η0H3+288η03m2H7. C_i^SE:= 2H (|A_i|+1) _0+12mH^3 (|A_i|+1)+ _0H^3+288 _0^3m^2H^7. Proof. Fix player i and a comparator μi∈Πigenμ^i∈ _i^gen. Let μi,ζμ^i,ζ be its ζ-smoothed version defined as in Appendix C.1. By Lemma 13, it is enough to control the regret against μi,ζμ^i,ζ and then add 2ζH22ζ H^2 to the average regret. For block k, let dk,hi,μζ∈Δ(ℋh)d_k,h^i,μ^ζ∈ (H_h) be the history distribution at layer h generated when player i uses μi,ζμ^i,ζ and the opponents use k−i π_k^-i. Applying Lemma 12 to the block profile k π_k gives Vi,πik,1(s1)−Vi,μi,ζk,1(s1)=∑h=1H∑τh∈ℋhdk,hi,μζ(τh)⟨Qk,hi(s(τh),⋅),πk,hi(⋅∣s(τh))−μhi,ζ(⋅∣τh)⟩, V^i,π^i_k,1(s_1)-V^i,μ^i,ζ_k,1(s_1)= _h=1^H _ _h _hd_k,h^i,μ^ζ( _h) Q_k,h^i(s( _h),·), _k,h^i(· s( _h))- _h^i,ζ(· _h) , On the event ℰξE_ξ, for every history τh _h, it holds almost surely that |⟨Qk,hi(s(τh),⋅)−Q^k,hi(s(τh),⋅),πk,hi(⋅∣s(τh))−μhi,ζ(⋅∣τh)⟩|≤ξ‖πk,hi(⋅∣s(τh))−μhi,ζ(⋅∣τh)‖1≤2ξ. | Q_k,h^i(s( _h),·)- Q_k,h^i(s( _h),·), _k,h^i(· s( _h))- _h^i,ζ(· _h) |≤ξ \| _k,h^i(· s( _h))- _h^i,ζ(· _h) \|_1≤ 2ξ. Since dk,hi,μζ∈Δ(ℋh)d_k,h^i,μ^ζ∈ (H_h) has total mass one at each layer, replacing Qk,hiQ_k,h^i by Q^k,hi Q_k,h^i costs at most 2HKξ2HKξ in cumulative regret. It remains to bound the corresponding weighted regret expression with Q^k,hi Q_k,h^i in place of Qk,hiQ_k,h^i. Lemma 7 is stated for the full simplex, but its proof uses only first-order optimality over a convex decision set, the Bregman diameter bound Di≤BiD_i≤ B_i, and 1/ρi1/ _i-strong convexity of the smoothed entropy regularizer. Hence the same bound applies verbatim on the restricted simplex Δiζ _i^ζ. Applying Lemma 7 separately to every history τ∈ℋhτ _h, with xk=πk,hi(⋅∣s(τh)),u=μhi,ζ(⋅∣τh),ℓk=Q^k,hi(s(τh),⋅),qk=dk,hi,μζ(τh),Mk=Q^k−1,hi(s(τh),⋅),x_k= _k,h^i(· s( _h)), u= _h^i,ζ(· _h), _k= Q_k,h^i(s( _h),·), q_k=d_k,h^i,μ^ζ( _h), M_k= Q_k-1,h^i(s( _h),·), and summing over histories gives Ri,hest(μi,ζ)≤ R_i,h^est(μ^i,ζ)≤\; Bi(1+TVhi,μζ)ηh+ηhρi2∑τ∈ℋh∑k=1Kdk,hi,μζ(τ)‖Q^k,hi(s(τ),⋅)−Q^k−1,hi(s(τ),⋅)‖∞2, B_i(1+TV_h^i,μ^ζ) _h+ _h _i2 _τ _h _k=1^Kd_k,h^i,μ^ζ(τ) \| Q_k,h^i(s(τ),·)- Q_k-1,h^i(s(τ),·) \|_∞^2, (10) where TVhi,μζ:=∑k=1K−1‖dk+1,hi,μζ−dk,hi,μζ‖1.TV_h^i,μ^ζ:= _k=1^K-1 \|d_k+1,h^i,μ^ζ-d_k,h^i,μ^ζ \|_1. We next bound first order path of the policies generated by estimated Q-functions. The proof of Lemma 8, which is based on Lemma 5, only uses the fact that the feedback vectors lie in [0,H]Aj[0,H]^A_j. Since Q^k,hj∈[0,H]Aj Q_k,h^j∈[0,H]^A_j, repeating the same calculation, for every player j, layer h, state s∈Shs∈ S_h, and block k, we obtain ‖πk+1,hj(⋅∣s)−πk,hj(⋅∣s)‖1≤3ρjHηh≤3ρ¯Hηh. \| _k+1,h^j(· s)- _k,h^j(· s) \|_1≤ 3 _jH _h≤ 3 ρH _h. (11) Applying the Lemma 9 to the block sequence π1,…,πK _1,…, _K, and using (11), yields TVhi,μζ≤3mρ¯HK∑ℓ<hηℓ.TV_h^i,μ^ζ≤ 3m ρHK _ <h _ . We now control the variation of the estimated Q-function. For the exact values, Lemma 10 and (11) imply, for k≥2k≥ 2, ‖Qk,hi(s,⋅)−Qk−1,hi(s,⋅)‖∞ \|Q_k,h^i(s,·)-Q_k-1,h^i(s,·) \|_∞ ≤2H2∑j=1m‖πk,hj−πk−1,hj‖∞,1 ≤ 2H^2 _j=1^m\| _k,h^j- _k-1,h^j\|_∞,1 ≤2H2⋅m⋅3ρ¯HηH=6mρ¯H3ηH. ≤ 2H^2· m· 3 ρH _H=6m ρH^3 _H. On the good event ℰξE_ξ, for k≥2k≥ 2, ‖Q^k,hi(s,⋅)−Q^k−1,hi(s,⋅)‖∞ \| Q_k,h^i(s,·)- Q_k-1,h^i(s,·) \|_∞ ≤‖Qk,hi(s,⋅)−Qk−1,hi(s,⋅)‖∞+2ξ≤6mρ¯H3ηH+2ξ ≤ \|Q_k,h^i(s,·)-Q_k-1,h^i(s,·) \|_∞+2ξ≤ 6m ρH^3 _H+2ξ Then, we have ‖Q^k,hi(s,⋅)−Q^k−1,hi(s,⋅)‖∞2≤72m2ρ¯2H6ηH2+8ξ2, \| Q_k,h^i(s,·)- Q_k-1,h^i(s,·) \|_∞^2≤ 72m^2 ρ^2H^6 _H^2+8ξ^2, where the last line follows from the inequality (a+b)2≤2a2+2b2(a+b)^2≤ 2a^2+2b^2. On the first block, Q^0,hi≡0 Q_0,h^i≡ 0 and Q^1,hi∈[0,H]Ai Q_1,h^i∈[0,H]^A_i, so ‖Q^1,hi(s,⋅)−Q^0,hi(s,⋅)‖∞2≤H2. \| Q_1,h^i(s,·)- Q_0,h^i(s,·) \|_∞^2≤ H^2. Substituting these estimates into the weighted OOMD bound (10) gives, on every layer h, Ri,hest(μi,ζ)≤ R_i,h^est(μ^i,ζ)≤\; Biηh+BiTVhi,μζηh+12ηhρiH2+36ηhρim2ρ¯2H6ηH2K+4ηhρiξ2K. B_i _h+ B_iTV_h^i,μ^ζ _h+ 12 _h _iH^2+36 _h _im^2 ρ^2H^6 _H^2K+4 _h _iξ^2K. (12) We now sum over h∈[H]h∈[H], using the same bounds on the learning-rate related terms as in the proof of Theorem 1 in Appendix B. Namely, with β=(3H−2)/(3H+1)β=(3H-2)/(3H+1), ∑h=1HBiηh≤HBiη0Kβ,∑h=1HBiTVhi,μζηh≤3mBiρ¯H3Kβ,∑h=1H12ηhρiH2≤12η0ρiH3Kβ, _h=1^H B_i _h≤ HB_i _0K^β, _h=1^H B_iTV_h^i,μ^ζ _h≤ 3mB_i ρH^3K^β, _h=1^H 12 _h _iH^2≤ 12 _0 _iH^3K^β, (13) and ∑h=1H36ηhρim2ρ¯2H6ηH2K≤36η03ρim2ρ¯2H7Kβ. _h=1^H36 _h _im^2 ρ^2H^6 _H^2K≤ 36 _0^3 _im^2 ρ^2H^7K^β. (14) Then the final term in (12) satisfies ∑h=1H4ηhρiξ2K≤4η0ρiHξ2K1−αH. _h=1^H4 _h _iξ^2K≤ 4 _0 _iHξ^2K^1- _H. (15) Choosing λi=1|Ai|, _i= 1|A_i|, gives ρi=1+|Ai|λi=2,ρ¯=2, _i=1+|A_i| _i=2,\; ρ=2, and Bi=2log(|Ai|+1)B_i=2 (|A_i|+1). Then, substituting these bounds into the (13), (14), (15) yields, Ri,hest(μi,ζ)≤ R_i,h^est(μ^i,ζ)≤\; C~iSEKβ+8η0Hξ2K1−αH. C_i^SEK^β+8 _0Hξ^2K^1- _H. (16) Finally, combining (16) with the error from comparing the played policies against μi,ζμ^i,ζ, namely 2ζH2K2ζ H^2K, and the error from Q-function estimation, namely 2HKξ2HKξ, we obtain, ∑k=1K[Vk,1i,π(s1)−Vk,1i,μi(s1)]≤ _k=1^K [V_k,1^i,π(s_1)-V_k,1^i,μ^i(s_1) ]≤ C~iSEKβ+2HKξ+2ζH2K+8η0Hξ2K1−αH. C_i^SEK^β+2HKξ+2ζ H^2K+8 _0Hξ^2K^1- _H. Dividing by K and taking the supremum over μi∈Πigenμ^i∈ _i^gen proves the proposition. ∎ C.4 Proof of Theorem 2 Proof. Apply Lemma 14 with K=Kε,B=Bε,ζ=ζε,ξ=ξε.K=K_ ,\;B=B_ ,\;ζ= _ ,\;ξ= _ . By the definition of BεB_ , the event ℰξεE_ _ holds with probability at least 1−δ1-δ. On this event, Proposition 2 gives, for every player i∈[m]i∈[m], supμi∈Πigen1Kε∑k=1Kε[Vk,1i,π(s1)−Vk,1i,μi(s1)]≤ _μ^i∈ _i^gen 1K_ _k=1^K_ [V_k,1^i,π(s_1)-V_k,1^i,μ^i(s_1) ]≤ C~iSEKε−3/(3H+1)+2Hξε+2ζεH2+8η0Hξε2Kε−αH. C_i^SEK_ ^-3/(3H+1)+2H _ +2 _ H^2+8 _0H _ ^2K_ ^- _H. • By the definition of KεK_ , C~iSEKε−3/(3H+1)≤C~∗SEKε−3/(3H+1)≤ε4. C_i^SEK_ ^-3/(3H+1)≤ C_*^SEK_ ^-3/(3H+1)≤ 4. • By the definition of ξε _ , 2Hξε≤ε4.2H _ ≤ 4. • By the definition of ζε _ , 2ζεH2=ε4.2 _ H^2= 4. • Finally, since Kε−αH≤1K_ ^- _H≤ 1, ρi=2 _i=2, and ξε2≤ε/(32η0H) _ ^2≤ /(32 _0H), 8η0Hξε2Kε−αH≤8η0Hξε2≤ε4.8 _0H _ ^2K_ ^- _H≤ 8 _0H _ ^2≤ 4. Thus, with probability at least 1−δ1-δ, for every player i∈[m]i∈[m], supμi∈Πigen1Kε∑k=1Kε[Vk,1i,π(s1)−Vk,1i,μi(s1)]≤ε. _μ^i∈ _i^gen 1K_ _k=1^K_ [V_k,1^i,π(s_1)-V_k,1^i,μ^i(s_1) ]≤ . (17) It remains to translate this block-level guarantee into a guarantee over the actual trajectory episodes. By construction, during block k the algorithm plays the same product Markov policy πk _k for all BεB_ episodes in that block. Therefore 1Nε∑n=1Nε[Vni,π(s1)−Vni,μi(s1)] 1N_ _n=1^N_ [V_n^i,π(s_1)-V_n^i,μ^i(s_1) ] =1KεBε∑k=1Kε∑r=1Bε[Vk,1i,π(s1)−Vk,1i,μi(s1)]=1Kε∑k=1Kε[Vk,1i,π(s1)−Vk,1i,μi(s1)]. = 1K_ B_ _k=1^K_ _r=1^B_ [V_k,1^i,π(s_1)-V_k,1^i,μ^i(s_1) ]= 1K_ _k=1^K_ [V_k,1^i,π(s_1)-V_k,1^i,μ^i(s_1) ]. Hence the bound given in (17) holds when the average is taken over the Nε=KεBεN_ =K_ B_ actual trajectory episodes. Moreover, the empirical distribution policies over π1,…,πNε _1,…, _N_ , is identical to the empirical distribution over the block policies π1,…,πKε _1,…, _K_ , since each policy πk _k appears exactly BεB_ times. Thus, the empirical distribution over block policies is an ε -approximate CCE. Finally, the total number of episodes is Nε=KεBεN_ =K_ B_ . By the definitions of KεK_ , BεB_ , ζε _ , nεn_ , uεu_ , and using the fact ξε≤ε/(8H) _ ≤ /(8H), Nε=O~(AmaxH6κε3(C~∗SEε)(3H+1)/3),N_ = O ( A_ H^6κ ^3 ( C_*^SE )^(3H+1)/3 ), where O~(⋅) O(·) hides logarithmic factors in (m,Snt,Amax,Kε,1/δ)(m,S_nt,A_ ,K_ ,1/δ), and C~∗SE≤maxi∈[m]2Hlog(|Ai|+1)η0+12mH3log(|Ai|+1)+η0H3+288η03m2H7. C_*^SE≤ _i∈[m] \ 2H (|A_i|+1) _0+12mH^3 (|A_i|+1)+ _0H^3+288 _0^3m^2H^7 \. This completes the proof. ∎ Appendix D Proofs for the Approximation of Discounted Markov Games (Section 4) This appendix proves the truncation statements used in Section 4. Throughout this appendix, we fix the discount factor γ∈(0,1)γ∈(0,1).The argument is written once for the unified discounted model with original horizon H¯∈ℕ+∪∞ H _+∪\∞\. The case H¯<∞ H<∞ corresponds to the finite-horizon discounted games, while H¯=∞ H=∞ corresponds to the discounted infinite-horizon games. Lemma 15. For every H¯ H-horizon policy profile ∈Πgen,H¯ σ∈ ^gen, H, every L≤H¯L≤ H, and every player i∈[m]i∈[m], 0≤Ji,H¯γ()−Ji,Lγ([L])≤τL,H¯(γ)≤γL1−γ.0≤ J_i, H^γ( σ)-J_i,L^γ( σ^[L])≤ _L, H(γ)≤ γ^L1-γ. Proof. The policy profile σ and its truncation [L] σ^[L] have the same first L decision rules. Therefore they induce the same distribution over trajectories up to the beginning of layer L+1L+1. Hence, Ji,H¯γ()−Ji,Lγ([L]) J_i, H^γ( σ)-J_i,L^γ( σ^[L]) =[∑h=L+1H¯γh−1ℓhi(sh,h)|s1]. =E σ [ _h=L+1 Hγ^h-1 _h^i(s_h, a_h)\; |\;s_1 ]. The right-hand side is nonnegative. Since 0≤ℓhi≤10≤ _h^i≤ 1, we have ∑h=L+1H¯γh−1ℓhi(sh,h)≤∑h=L+1∞γh−1=γL1−γ, _h=L+1 Hγ^h-1 _h^i(s_h, a_h)≤ _h=L+1^∞γ^h-1= γ^L1-γ, which concludes the proof. ∎ Lemma 16. Let [L]∈Πmarkov,L π^[L]∈ ^markov,L, be an L-step product Markov profile, and define ¯:=ExtL([L]). π:=Ext_L( π^[L]). Then, Ji,H¯γ(¯)−Ji,H¯γ(μi⊙¯−i)≤ J_i, H^γ( π)-J_i, H^γ(μ^i π^-i)≤ Ji,Lγ([L])−Ji,Lγ(μi,[L]⊙[L],−i)+τL,H¯(γ). J_i,L^γ( π^[L])-J_i,L^γ(μ^i,[L] π^[L],-i)+ _L, H(γ). Proof. Applying Lemma 15 with =¯ π= π, we obtain Ji,H¯γ(¯)≤Ji,Lγ([L])+τL,H¯(γ). J_i, H^γ( π)≤ J_i,L^γ( π^[L])+ _L, H(γ). (18) On the other hand, the first L decision rules of μi⊙¯−iμ^i π^-i are exactly those of μi,[L]⊙[L],−iμ^i,[L] π^[L],-i. Since all costs are nonnegative, ignoring the layers after L can only decrease the term Ji,H¯γ(μi⊙¯−i)J_i, H^γ(μ^i π^-i). Therefore, Ji,H¯γ(μi⊙¯−i)≥Ji,Lγ(μi,[L]⊙[L],−i). J_i, H^γ(μ^i π^-i)≥ J_i,L^γ(μ^i,[L] π^[L],-i). (19) Then, subtracting (19) from (18) proves the claim. ∎ Proof of Theorem 3. Fix a player i∈[m]i∈[m] and a policy μi∈Πigen,H¯μ^i∈ _i^gen, H. For each output profile n[L]∈Πmarkov,L π_n^[L]∈ ^markov,L, define ¯n:=ExtL(πn[L]) π_n:=Ext_L( _n^[L]). By Lemma 16, for every n, Ji,H¯γ(¯n)−Ji,H¯γ(μi⊙¯n−i)≤ J_i, H^γ( π_n)-J_i, H^γ(μ^i π_n^-i)≤ Ji,Lγ(n[L])−Ji,Lγ(μi,[L]⊙n[L],−i)+τL,H¯(γ). J_i,L^γ( π_n^[L])-J_i,L^γ(μ^i,[L] π_n^[L],-i)+ _L, H(γ). Averaging over n=1,…,Nn=1,…,N gives 1N∑n=1N[Ji,H¯γ(¯n)−Ji,H¯γ(μi⊙¯n−i)]≤ 1N _n=1^N [J_i, H^γ( π_n)-J_i, H^γ(μ^i π_n^-i) ]≤\; 1N∑n=1N[Ji,Lγ(n[L])−Ji,Lγ(μi,[L]⊙n[L],−i)]⏟∗+τL,H¯(γ). 1N _n=1^N [J_i,L^γ( π_n^[L])-J_i,L^γ(μ^i,[L] π_n^[L],-i) ]_*+ _L, H(γ). (20) Since μi,[L]∈Πigen,Lμ^i,[L]∈ _i^gen,L, the assumed finite-horizon regret guarantee implies that the term (∗)(*) in (20) is at most εalg _alg, simultaneously for all players i∈[m]i∈[m]. The resulting bound is uniform over μiμ^i, and thus taking the supremum over Πigen,H¯ _i^gen, H proves the statement. ∎ D.1 Proofs for the full-feedback case We first note that Algorithm 1 can be applied to game Gγ,H¯[Lε]G_γ, H^[L_ ], as Gγ,H¯[Lε]G_γ, H^[L_ ] is simply an undiscounted finite-horizon Markov game with costs chi(s,a)=γh−1ℓhi(s,a)c_h^i(s,a)=γ^h-1 _h^i(s,a), and these costs remain in [0,1][0,1]. Hence Theorem 1 applies directly with the horizon parameter H replaced by LεL_ . Proof of Corollary 1. We apply Theorem 3 when Algorithm 1 runs on the truncated discounted game Gγ,H¯[Lε]G_γ, H^[L_ ]. By Theorem 1, applied with horizon LεL_ , the finite-horizon average regret on the truncated game Gγ,H¯[Lε]G_γ, H^[L_ ] is bounded by εalg=C∗SE(Lε)Tε−3/(3Lε+1). _alg=C_*^SE(L_ )T_ ^-3/(3L_ +1). The definition of TεT_ gives C∗SE(Lε)Tε−3/(3Lε+1)≤ε2.C_*^SE(L_ )T_ ^-3/(3L_ +1)≤ 2. It remains to bound the truncation error. If Lε=H¯<∞L_ = H<∞, then the truncated game Gγ,H¯[Lε]G_γ, H^[L_ ], is the same as the original game Gγ,H¯G_γ, H and τLε,H¯(γ)=0. _L_ , H(γ)=0. Otherwise, by the definition of Lε=minH¯,Hεγ,L_ = \ H,H_ ^γ\, we have Lε=HεγL_ =H_ ^γ. In that case, by Lemma 15 τLε,H¯(γ)≤γLε1−γ≤ε2, _L_ , H(γ)≤ γ^L_ 1-γ≤ 2, where the last inequality follows from the choice Hεγ=⌈log(2(1−γ)ε)log(1/γ)⌉.H_ ^γ= \! ( 2(1-γ) ) (1/γ) . Therefore, for every player i∈[m]i∈[m], Theorem 3 gives supμi∈Πigen,H¯∑t=1Tε[Ji,H¯γ(¯t)−Ji,H¯γ(μi⊙¯t−i)]≤εTε. _μ^i∈ _i^gen, H _t=1^T_ [J_i, H^γ( π_t)-J_i, H^γ(μ^i π_t^-i) ]≤ T_ . The discounted CCE conclusion in Corollary 1 follows from the standard no-regret-to-CCE equivalence [Cesa-Bianchi and Lugosi, 2006] applied to the empirical distribution of joint policies over ¯1,…,¯Tε π_1,…, π_T_ . We now justify the upper bound for the total number of episodes. Since log(1/γ)≥1−γ, (1/γ)≥ 1-γ, we have Lε≤Lγ,εH¯:=minH¯, 1+11−γlog(2(1−γ)ε),L_ ≤ L_γ, H:= \ H,\,1+ 11-γ \! ( 2(1-γ) ) \, with the convention that when H¯=∞ H=∞, Lγ,εH¯=1+11−γlog(2(1−γ)ε).L_γ, H=1+ 11-γ \! ( 2(1-γ) ). Under the choice λi=1/|Ai| _i=1/|A_i|, from Theorem 1 we have, C∗SE(L)≤(2Alogη0+12mAlog+η0+144η03m2)L7,Alog:=maxi∈[m]log(|Ai|+1).C_*^SE(L)≤ ( 2A_ _0+12mA_ + _0+144η^3_0m^2 )L^7, A_ := _i∈[m] (|A_i|+1). Substituting this estimate into the definition of TεT_ , using ⌈x⌉≤1+x x ≤ 1+x, gives, for every fixed γ<1γ<1, Tε≤[(Alogη0+mAlog+m2+1)minH¯,log(1/ε)7ε]O(minH¯,log(1/ε)).T_ ≤ [ ( A_ _0+mA_ +m^2+1 ) \ H, (1/ )\^7 ]^O( \ H, (1/ )\). This concludes the proof. ∎ D.2 Proof of the partial-feedback case Now, similar to Subsection D.1, Theorem 2 can be applied to the game Gγ,H¯[Lε]G_γ, H^[L_ ], as its scaled costs chi(s,a)=γh−1ℓhi(s,a)c_h^i(s,a)=γ^h-1 _h^i(s,a) still lie in [0,1][0,1]. Hence Theorem 2 applies directly with the horizon parameter H replaced by LεL_ and the (κ,ζε¯,L)(κ, _ ,L)-reachability condition for Gγ,H¯[Lε]G_γ, H^[L_ ]. Proof of Corollary 2. Set L=Lε,ε¯=ε2.L=L_ ,\; = 2. By assumption, the truncated discounted game Gγ,H¯[L]G_γ, H^[L] is (κ,ζε¯,L)(κ, _ ,L)-reachable. Therefore, applying Theorem 2 to Gγ,H¯[L]G_γ, H^[L] with stated parameters, we obtain that, with probability at least 1−δ1-δ, for every player i∈[m]i∈[m], supνi∈Πigen,L1Nε,H¯,δ∑k=1Kε¯,Lε∑t=1Bε,Lε,δ[Ji,Lγ(k[L])−Ji,Lγ(νi⊙k[L],−i)]≤ε¯=ε2. _ν^i∈ _i^gen,L 1N_ , H,δ _k=1^K_ ,L_ _t=1^B_ ,L_ ,δ [J_i,L^γ( π_k^[L])-J_i,L^γ(ν^i π_k^[L],-i) ]≤ = 2. By Theorem 3, the average regret of the extended block policies ¯k:=ExtL(k[L]) π_k:=Ext_L( π_k^[L]) is at most ε2+τL,H¯(γ). 2+ _L, H(γ). It remains to bound the truncation error. If Lε=H¯<∞L_ = H<∞, then the truncation is the original game and τLε,H¯(γ)=0. _L_ , H(γ)=0. Hence τL,H¯(γ)≤γL1−γ≤ε2 _L, H(γ)≤ γ^L1-γ≤ 2 by the Lemma 15. Consequently, with probability at least 1−δ1-δ, for every player i∈[m]i∈[m], Theorem 3 gives, supμi∈Πigen,H¯1Nε,H¯,δ∑k=1Kε¯,Lε∑t=1Bε,Lε,δ[Ji,H¯γ(π¯k)−Ji,H¯γ(μi⊙π¯k−i)]≤ε. _μ^i∈ _i^gen, H 1N_ , H,δ _k=1^K_ ,L_ _t=1^B_ ,L_ ,δ [J_i, H^γ( π_k)-J_i, H^γ(μ^i π_k^-i) ]≤ . The discounted CCE statement follows from the standard no-regret-to-CCE equivalence [Cesa-Bianchi and Lugosi, 2006] applied to the empirical distribution over the extended block policies. It remains to justify the upper bound on Nε,H¯,δbandN_ , H,δ^band. We have, Lε=O(ℒH¯,ε),ℒH¯,ε:=minH¯,log(1/ε),L_ =O(L_ H, ),\;L_ H, := \ H, (1/ )\, with the convention ℒ∞,ε=log(1/ε)L_∞, = (1/ ). Then, Kε¯,Lε=⌈(4C~∗SE(Lε)ε¯)(3Lε+1)/3⌉≤[bandℒH¯,ε7ε]O(ℒH¯,ε), K_ ,L_ = ( 4 C_*^SE(L_ ) )^(3L_ +1)/3 ≤ [ C_bandL_ H, ^7 ]^O(L_ H, ), (21) where, band:=2Alogη0+12mAlog+η0+288m2η03C_band:= 2A_ _0+12mA_ + _0+288m^2η^3_0 . Next, by the definitions ζε¯,L=ε¯8L2,ξε¯,L=minε¯8L,ε¯32η0L, _ ,L= 8L^2,\; _ ,L= \ 8L, 32 _0L \, we have, up to universal constants, 1ζε¯,Lε≲ℒH¯,ε2ε,Lε2ξε¯,Lε2≲ℒH¯,ε4ε2+η0ℒH¯,ε3ε. 1 _ ,L_ L_ H, ^2 , L_ ^2 _ ,L_ ^2 L_ H, ^4 ^2+ _0L_ H, ^3 . (22) Using the definitions Mε¯,L=Kε¯,LmAmaxS,uε¯,L,δ=log4Mε¯,Lδ,M_ ,L=K_ ,LmA_ S,\;u_ ,L,δ= 4M_ ,Lδ, we obtain uε¯,Lε,δ≤O(ℒH¯,εlogbandℒH¯,ε7ε+logmAmaxSδ). u_ ,L_ ,δ≤ O (L_ H, C_bandL_ H, ^7 + mA_ Sδ ). (23) Finally, substituting (22),(23) into Bε¯,Lε,δ=⌈8Amaxκζε¯,Lε(nε¯,Lε,δ+uε¯,Lε,δ)⌉,nε¯,Lε,δ=⌈Lε22ξε¯,Lε2uε¯,Lε,δ⌉,B_ ,L_ ,δ= 8A_ κ _ ,L_ (n_ ,L_ ,δ+u_ ,L_ ,δ ) ,\;n_ ,L_ ,δ= L_ ^22 _ ,L_ ^2u_ ,L_ ,δ , up to universal constants we get; Bε¯,Lε,δ≲⌈AmaxκℒH¯,ε2ε(ℒH¯,ε4ε2+η0ℒH¯,ε3ε+1)uε¯,Lε,δ⌉, B_ ,L_ ,δ A_ κ L_ H, ^2 ( L_ H, ^4 ^2+ _0L_ H, ^3 +1 )u_ ,L_ ,δ , (24) and multiplying (24) by (21), yields Nε,H¯,δ≤[AmaxℒH¯,ε2κε(1+ℒH¯,ε4ε2+η0ℒH¯,ε3ε)×(ℒH¯,εlogbandℒH¯,ε7ε+logmAmaxSδ)][bandℒH¯,ε7ε]O(ℒH¯,ε) N_ , H,δ≤ [ A_ L_ H, ^2κ \! (1+ L_ H, ^4 ^2+ _0L_ H, ^3 \! )\!\!×\!\! (\!L_ H, \! C_bandL_ H, ^7 \!+\! \!mA_ S\!δ )\! ]\!\! [ \!C_bandL_ H, ^7\! ]^O(L_ H, ) This concludes the proof. ∎ Appendix E Proofs for the Computational Lower Bounds (Section 5) For an encoded object z, we write bits(z)bits(z) for the length of its binary encoding. Rational numbers are encoded in reduced form: a rational number q∈ℚq is written as q=p/rq=p/r, where p∈ℤp , r∈ℕr , and gcd(|p|,r)=1 (|p|,r)=1. We define bits(q):=1+⌈log2(|p|+1)⌉+⌈log2(r+1)⌉.bits(q):=1+ _2(|p|+1) + _2(r+1) . E.1 Proof of Algorithms 1 and 2 solving the sparse discounted-CCE problem Proof of Proposition 1. We verify separately the policy-class requirement and the discounted CCE requirement appearing in Definition 8. First consider Algorithm 1. At every episode t, player i, layer h, and state s, the algorithm sets πt,hi,[Lε](⋅∣s)=xt,hi,s∈Δ(i) _t,h^i,[L_ ](· s)=x_t,h^i,s∈ (A_i) independently for each instance. Hence πti,[Lε]=πt,hi,[Lε]h=1Lε∈Πimarkov,Lε, _t^i,[L_ ]= \ _t,h^i,[L_ ] \_h=1^L_ ∈ _i^markov,L_ , and therefore t[Lε]=(πt1,[Lε],…,πtm,[Lε])∈Πmarkov,Lε. π_t^[L_ ]= ( _t^1,[L_ ],…, _t^m,[L_ ] )∈ ^markov,L_ . The continuation used by ExtLεExt_L_ is itself a fixed product Markov policy. Consequently, ¯t=ExtLε(t[Lε])∈Πmarkov,H¯ π_t=Ext_L_ ( π_t^[L_ ] )∈ ^markov, H for every t∈[Tε]t∈[T_ ]. Corollary 1 gives, for every player i∈[m]i∈[m], supμi∈Πigen,H¯∑t=1Tε[Ji,H¯γ(¯t)−Ji,H¯γ(μi⊙¯t−i)]≤εTε. _μ^i∈ _i^gen, H _t=1^T_ [J_i, H^γ( π_t)-J_i, H^γ (μ^i π_t^-i ) ]≤ T_ . Thus the sequence (¯1,…,¯Tε) ( π_1,…, π_T_ ) satisfies both requirements of Definition 8, and therefore solves (Tε,ε)-γgen.(T_ , )- DiscSparseMarkovCCE_γ^gen. We next consider Algorithm 2. At every block k, player i, layer h, and state s, the algorithm sets πk,hi,[Lε](⋅∣s)=xk,hi,s∈Δiζ⊆Δ(i) _k,h^i,[L_ ](· s)=x_k,h^i,s∈ _i^ζ (A_i) independently for each instance. Therefore, k[Lε]∈Πmarkov,Lε,¯k=ExtLε(k[Lε])∈Πmarkov,H¯. π_k^[L_ ]∈ ^markov,L_ ,\; π_k=Ext_L_ ( π_k^[L_ ] )∈ ^markov, H. Since the policy ¯k π_k is played throughout block k, every entry of the sequence (k−1)Bε+r:=¯k σ^(k-1)B_ +r:= π_k belongs to Πmarkov,H¯ ^markov, H. By Corollary 2, with probability at least 1−δ1-δ, for any player i∈[m]i∈[m], supμi∈Πigen,H¯∑n=1Nε[Ji,H¯γ(n)−Ji,H¯γ(μi⊙n,−i)]≤εNε. _μ^i∈ _i^gen, H _n=1^N_ [J_i, H^γ( σ^n)-J_i, H^γ (μ^i σ^n,-i ) ]≤ N_ . Hence the episode-level sequence solves (Nε,ε)-γgen(N_ , )- DiscSparseMarkovCCE_γ^gen on this event. ∎ E.2 Game size and encoding conventions For a finite-horizon Markov game GH=(H,Shh=1H+1,Aii=1m,Phh=1H,ℓhii∈[m],h∈[H],s1),G_H= (H,\S_h\_h=1^H+1,\A_i\_i=1^m,\P_h\_h=1^H,\ _h^i\_i∈[m],h∈[H],s_1 ), we define the term β(GH)β(G_H) as β(GH):=maxmaxh∈[H],s∈Sh,∈A,s′∈Sh+1bits(Ph(s′∣s,)),maxi∈[m],h∈[H],s∈Sh,∈Abits(ℓhi(s,)). β(G_H):= \ _ subarraych∈[H],s∈ S_h, a∈ A,\ s ∈ S_h+1 subarraybits (P_h(s s, a) ), _ subarrayci∈[m],h∈[H],s∈ S_h, a∈ A subarraybits ( _h^i(s, a) ) \. Thus, β(GH)β(G_H) is the largest bit length of one transition-probability entry or one loss entry. We define |GH|:=maxH,S,Amax,β(GH).|G_H|:= \H,S,A_ ,β(G_H) \. Consequently, GHG_H can be described using |GH|O(1)|G_H|^O(1) bits for fixed m. For the special case of H=1H=1, we simply denote the size of a normal-form game by |G||G| under this convention. Similarly, for a discounted infinite-horizon Markov game Gγ=(S,Aii=1m,P,ℓii=1m,γ,s1),G_γ= (S,\A_i\_i=1^m,P,\ ^i\_i=1^m,γ,s_1 ), we define the term β(Gγ)β(G_γ) as β(Gγ):=maxbits(γ),maxs∈S,∈A,s′∈Sbits(P(s′∣s,)),maxi∈[m],s∈S,∈Abits(ℓi(s,)). β(G_γ):= \bits(γ), _ subarraycs∈ S, a∈ A,s ∈ S subarraybits (P(s s, a) ), _ subarrayci∈[m],s∈ S, a∈ A subarraybits ( ^i(s, a) ) \. We then define |Gγ|:=maxS,Amax,β(Gγ).|G_γ|:= \S,A_ ,β(G_γ) \. If γ is fixed before the input is given, then bits(γ)=O(1)bits(γ)=O(1), and including bits(γ)bits(γ) in β(Gγ)β(G_γ) changes |Gγ||G_γ| only by a fixed constant factor inside the maximum. For a finite-horizon discounted Markov game Gγ,H¯G_γ, H, we use the same convention as above with the horizon parameter included: |Gγ,H¯|:=maxH¯,S,Amax,β(Gγ,H¯),|G_γ, H|:= \ H,S,A_ ,β(G_γ, H) \, and β(Gγ,H¯):=maxbits(γ),maxh∈[H¯],s∈Sh,∈A,s′∈Sh+1bits(Ph(s′∣s,)),maxi∈[m],h∈[H¯],s∈Sh,∈Abits(ℓhi(s,)). β(G_γ, H):= \bits(γ), _ subarraych∈[ H],s∈ S_h, a∈ A,\ s ∈ S_h+1 subarray\!\!\!\!\!\!bits (P_h(s s, a) ), _ subarrayci∈[m],h∈[ H],s∈ S_h, a∈ A subarray\!\!\!bits ( _h^i(s, a) ) \. Throughout Section 5, by N, we denote an upper bound on the game-size parameters. Specifically, |GH|≤N,|Gγ,H¯|≤N,|Gγ|≤N,|G_H|≤ N,\;|G_γ, H|≤ N,\;|G_γ|≤ N, for finite-horizon, finite-horizon discounted, and infinite-horizon discounted Markov games, respectively. The letter n is reserved for the number of actions per player in the corresponding games. We particularly name the M M from Lemma 3 as the source game after the bimatrix game described in Lemma 8.3 of Rubinstein [2016], which is used in the reduction underlying Theorem 4. Furthermore, we emphasize that, to remain consistent with the previous sections, we will use these games under the loss convention instead of the utility-payoff convention, since this conversion neither changes the equilibrium points nor the size of the games in view of Lemma 20 and the subsequent results. For brevity, for further details regarding the exact construction of the game, we refer to Rubinstein [2016]. E.3 The logarithmic-horizon undiscounted Markov game We use a finite-horizon Markov game construction from Foster et al. [2023]. Let M=(L1,L2)M=(L^1,L^2) be a bimatrix n×n× n game. For M, we identify a corresponding finite-horizon Markov game FH(M)F_H(M) as follows, where H≥2H≥ 2 is a fixed even (numbered) horizon length. In FH(M)F_H(M), both players share the same state and action sets. The admissible action set is [n][n] at every non-terminal layer. For odd (numbered) layers h, the state set is a singleton Sh=sh⋆S_h=\s_h \, and for even (numbered) layers h, the state set is Sh=[n]×[n]S_h=[n]×[n]. For each layer h, the state transition probability kernels Ph×[n]×[n]→Δ(Sh+1)P_h×[n]×[n]→ (S_h+1) are “deterministic” and are defined as follows. For an odd layer h, if the current state is sh⋆s_h and the players choose the joint action (a,b)∈[n]×[n](a,b)∈[n]×[n], then the next state records this joint action: Ph((a,b)∣sh⋆,(a,b))=1.P_h ((a,b) s_h ,(a,b) )=1. For an even layer h<Hh<H, the transition probability is independent of both the current state and the joint action: for every (x,y)∈[n]×[n](x,y)∈[n]×[n] and every (a,b)∈[n]×[n](a,b)∈[n]×[n], Ph(sh+1⋆∣(x,y),(a,b))=1.P_h (s_h+1 (x,y),(a,b) )=1. All other transition probabilities are zero. Furthermore, at an odd layer h, if the players choose the action profile (a,b)∈[n]×[n](a,b)∈[n]×[n], then the player i incurs cost ℓhi(sh⋆,(a,b)):=1HLi(a,b), _h^i(s_h ,(a,b)):= 1HL^i(a,b), At an even layer h<Hh<H, all costs are zero and the next state is the next odd-layer singleton sh+1⋆s_h+1 . Let H:=1,3,5,…,H−1O_H:=\1,3,5,…,H-1\ be the set of odd layers. For a given product Markov profile t π_t and odd layer h∈Hh _H, define the corresponding local mixed strategies of players as xt,h:=πt1(⋅∣sh⋆),x_t,h:=π^1_t(· s_h ), and yt,h:=πt2(⋅∣sh⋆).y_t,h:=π^2_t(· s_h ). Finally, it can be clearly seen that the described construction takes polynomial time. Lemma 17 (Lemma D.4 Foster et al. [2023]). Let M be a bimatrix game. There exists an absolute constant cF>0c_F>0, independent of any problem parameter, such that the following holds. Let H≥2H≥ 2 be even, T∈ℕ+T _+, and let FH(M)F_H(M) be the finite-horizon Markov game constructed as described in Appendix E.3. Suppose, LH=(1,…,T)L_H=( π_1,…, π_T) is an ε⋆/4 _ /4-approximate T-sparse CCE of FH(M)F_H(M), against non-Markov deviations. If T<exp(cFε⋆2H),T< (c_F _ ^2H), then there exist t∈[T]t∈[T] and h∈Hh _H such that (xt,h,yt,h)(x_t,h,y_t,h) is an ε⋆ _ -approximate Nash equilibrium of M, where HO_H is the set of odd numbered layers. E.4 Embedding into a fixed-discount game We extend the construction of FH(M)F_H(M) to the infinite-horizon setting. This enables us to establish a connection between the notion of CCE in discounted infinite-horizon Markov games and the notion of Nash equilibrium in the associated normal-form game M. For a finite-horizon Markov game GH=(H,Shh=1H+1,Aii=1m,Phh=1H,ℓhii∈[m],h∈[H],s1),G_H= (H,\S_h\_h=1^H+1,\A_i\_i=1^m,\P_h\_h=1^H,\ _h^i\_i∈[m],h∈[H],s_1 ), we define a corresponding infinite-horizon discounted Markov game G~H,γ=(S~,Aii=1m,P~,ℓ~ii=1m,γ,s1) G_H,γ=( S,\A_i\_i=1^m, P,\ ^i\_i=1^m,γ,s_1), where γ∈(0,1)∩ℚγ∈(0,1) as follows. The state space is S~:=(h,s):h∈[H],s∈Sh∪⊥, S:=\(h,s):h∈[H],\ s∈ S_h\∪\ \, where ⊥ is an absorbing state. The action sets of the players stay the same. In this configuration, we define the transition kernel of the players in G~H,γ G_H,γ as, P~(x′∣x,a)=Ph(s′∣s,a),if x=(h,s),h<H,x′=(h+1,s′),1,if x=(H,s),x′=⊥,1,if x=⊥,x′=⊥,0,otherwise. P(x x,a)= casesP_h(s s,a),&if x=(h,s),\ h<H,\ x =(h+1,s ),\\[4.0pt] 1,&if x=(H,s),\ x = ,\\[4.0pt] 1,&if x= ,\ x = ,\\[4.0pt] 0,&otherwise. cases Choose a scaling parameter α:=γH−1,α:=γ^H-1, and define the cost function of player i as ℓ~i((h,s),a):=αγ−(h−1)ℓhi(s,a)=γH−hℓhi(s,a),h∈[H], ^i((h,s),a):=αγ^-(h-1) _h^i(s,a)=γ^H-h _h^i(s,a), h∈[H], while ℓ~i(⊥,⋅):≡0 ^i( ,·):≡ 0. Moreover, as G~H,γ G_H,γ can be constructed from GHG_H in polynomial time, since it only adds one absorbing state and rescales the finitely many transition and cost entries of GHG_H. Then, we have the following result. Lemma 18. For every policy profile ∈Πmarkov σ∈ ^markov in G~H,γ G_H,γ and every player i, Jiγ(,G~γ)=αVi,[H](s1,GH).J_i^γ( σ; G_γ)=α V^i, σ^[H](s_1;G_H). Moreover, for every sparse list L~=(1,…,T) L=( σ_1,…, σ_T) where, for all t∈[T]t∈[T] σt∈Πmarkov,∞ _t∈ ^markov,∞, it holds that, if L~ L is an ε -approximate discounted CCE of G~H,γ G_H,γ, then L~[H] L^[H] is an (ε/α)( /α)-approximate CCE of GHG_H. Proof. For the first H layers, the infinite-horizon game G~H,γ G_H,γ exactly emulates GHG_H. By construction, after the layer H, the state of the players in the game G~H,γ G_H,γ permanently moves to ⊥ , where all future costs of the players are zero. Along every simulated state-action pair, i.e. ((h,sh),ah)((h,s_h),a_h), for h≤Hh≤ H, we obtain γh−1ℓ~i((h,sh),ah)=γh−1αγ−(h−1)ℓhi(sh,ah)=αℓhi(sh,ah).γ^h-1 ^i((h,s_h),a_h)=γ^h-1αγ^-(h-1) _h^i(s_h,a_h)=α _h^i(s_h,a_h). Taking the expectation of the expression above, we obtain Jiγ(,G~γ)=α[H][∑h=1Hℓhi(sh,ah)]=αVi,[H](s1,GH).J_i^γ( σ; G_γ)= σ^[H] [ _h=1^H _h^i(s_h,a_h) ]=α V^i, σ^[H](s_1;G_H). Now fix a list L~ L. Then, for any infinite-horizon deviation μi∈Πigen,∞μ^i∈ _i^gen,∞ we get the following equality 1T∑t=1T[Jiγ(t,G~γ)−Jiγ(μi⊙t−i,G~γ)]=α1T∑t=1T[Vi,t[H](s1,GH)−Vi,μi,[H]⊙t[H],−i(s1,GH)]. 1T _t=1^T [J_i^γ( σ_t; G_γ)-J_i^γ(μ^i σ_t^-i; G_γ) ]=α 1T _t=1^T [V^i, σ_t^[H](s_1;G_H)-V^i,μ^i,[H] σ_t^[H],-i(s_1;G_H) ]. (25) It can be seen that, every H-step deviation can be extended arbitrarily to infinite horizon after the absorbing layer H, and the discounted value of the players remains the same because all post-H costs are zero. Thus, taking the supremum over deviations on the LHS of (25) is equivalent to taking the supremum over H-step deviations on the right. This completes the proof. ∎ Now, we describe the expression sizes of the source game M M and its corresponding encoding F~H,γ(M^) F_H,γ( M) in the next two lemmas, Lemmas 19 and 20. Lemma 19 (Size of the source game). Let M M be the source two-player game described in Lemma 8.3 of Rubinstein [2016], and let n be the number of pure actions per player in M M. Then, there exist absolute constants qsrc,nsrc≥1q_ src,n_ src≥ 1, such that n≤|M^|≤(n+2)qsrcn≤| M|≤(n+2)^q_ src for all n≥nsrcn≥ n_ src. Proof outline. The lower bound follows immediately from the definition of |M^|| M|. For the upper bound, observe that the payoff functions of the bimatrix game constructed in Lemma 8.3 of Rubinstein [2016] consist of two types of components: a scaled bipartite polymatrix game constructed in Section 7 of Rubinstein [2016], and the payoffs of the two auxiliary Althöfer games. We first consider the polymatrix component. The bipartite polymatrix game constructed in Section 7 of Rubinstein [2016] contains number of players that is at most polynomial in n for each side of the bipartite polymatrix game. Moreover, as described in Sections 7.2–7.4 of Rubinstein [2016], each polymatrix payoff entry is computed from a number of quantities that is polynomially bounded by n. Moreover, all numerical quantities are represented at the fixed precision. Therefore, there exist an absolute constant r1r_1 and a sufficiently large absolute threshold nsrcn_ src such that every payoff entry of the bipartite polymatrix game has binary encoding length at most (n+2)r1(n+2)^r_1 whenever n≥nsrcn≥ n_ src. Then, the main payoff component is obtained by multiplying the bipartite polymatrix payoff by factors of the form λnAλ n_A or λnBλ n_B, where λ is an absolute constant and nA,nBn_A,n_B are the numbers of players on the two sides of the bipartite polymatrix game. It follows that the binary encoding length of every payoff entry arising from the scaled polymatrix component is at most (n+2)r2(n+2)^r_2 for some absolute constant r2r_2 and all n≥nsrcn≥ n_ src, after sufficiently large nsrcn_ src. We next consider the two Althöfer-game components used in Lemma 8.3 of Rubinstein [2016]. Their payoff entries belong to 0,1\0,1\, and therefore have constant binary encoding length. Since each final bimatrix payoff is the sum of one scaled polymatrix payoff and a constant number of Althöfer payoffs, there exists an absolute constant r0r_0 such that β(M^)≤(n+2)r0β( M)≤(n+2)^r_0 for all n≥nsrcn≥ n_ src, where β(M^)β( M) denotes the maximum binary encoding length of any payoff entry of M. Consequently, |M^|=maxn,β(M^)≤maxn,(n+2)r0≤(n+2)qsrc aligned | M|= \n,β( M)\≤ \n,(n+2)^r_0 \≤(n+2)^q_ src aligned for a sufficiently large absolute constant qsrc.q_ src. Finally, the payoff range of the source game need not initially be normalized to [0,1][0,1]. Since the payoffs in the construction are bounded by absolute constants, such a normalization can be carried out by an affine transformation with fixed coefficients. This changes the payoff bit complexity by at most an absolute additive amount and therefore does not affect the asserted polynomial relation for sufficiently large n. ∎ Lemma 20 (Size of the discounted embedding). Fix a rational discount factor γ∈(0,1)∩ℚγ∈(0,1) . Let qsrc≥1q_src≥ 1 be the absolute constant from Lemma 19. Define d0:=max4,qsrc+2.d_0:= \4,q_src+2\. Then, for every finite constant BH≥2B_H≥ 2, there exists an integer nsize=nsize(γ)n_size=n_size(γ) such that the following holds for every n≥nsizen≥ n_size. Let M M be the source two-player game described in Lemma 8.3 of Rubinstein [2016], with n pure actions per player, and let H≥2H≥ 2 be an even integer satisfying H≤BHlog(n+2).H≤ B_H (n+2). Let FH(M^)F_H( M) be the finite-horizon Markov game constructed according to Subsection E.3, and let F~H,γ(M^) F_H,γ( M) be the discounted game obtained from FH(M^)F_H( M) as described in Subsection E.4. Then n≤|F~H,γ(M^)|≤(n+2)d0.n≤| F_H,γ( M)|≤(n+2)^d_0. Proof. To construct F~H,γ(M^) F_H,γ( M) from M M, we first denote it in loss convention through well known conversions from payoffs to losses. By Lemma 19, the source game satisfies |M^|≤(n+2)qsrc.| M|≤(n+2)^q_src. Then, every loss entry of M M has bit length at most maxi∈1,2maxa,b∈[n]bits(Li(a,b))≤(n+2)qsrc. _i∈\1,2\ _a,b∈[n]bits(L^i(a,b))≤(n+2)^q_src. We now bound the size of F~H,γ(M^) F_H,γ( M). First, consider the state and action sets. In FH(M^)F_H( M), every odd layer is a singleton and every even layer has state set [n]×[n][n]×[n]. Hence, ∑h=1H|Sh|=H2+H2n2. _h=1^H|S_h|= H2+ H2n^2. Recall that the state space of the players in the game F~H,γ(M^) F_H,γ( M) is S~:=(h,s):h∈[H],s∈Sh∪⊥. S:=\(h,s):h∈[H],\,s∈ S_h\∪\ \. Therefore |S~|=1+H2+H2n2≤1+H(n+2)2.| S|=1+ H2+ H2n^2≤ 1+H(n+2)^2. Since H≤BHlog(n+2)H≤ B_H (n+2), we have H≤n+2H≤ n+2 whenever n≥nsizen≥ n_size. Consequently, |S~|≤1+(n+2)3≤(n+2)4. | S|≤ 1+(n+2)^3≤(n+2)^4. (26) Moreover, both players in F~H,γ(M^) F_H,γ( M) have the action set [n][n], and thus Amax=n.A_ =n. This already gives the lower bound |F~γ(M^)|=max|S~|,Amax,β(G~γ(M^)≥Amax=n.| F_γ( M)|= \| S|,A_ ,β( G_γ( M)\≥ A_ =n. It remains to bound β(F~H,γ(M^))β( F_H,γ( M)). The transition probabilities of the players in F~H,γ(M^) F_H,γ( M) are all either 00 or 11, and hence the transition entries have constant bit length. We only need to bound the loss entries. For h∈[H]h∈[H], the discounted embedding uses losses of the form ℓ~i((h,s),a)=γH−hℓhi(s,a), ^i((h,s),a)=γ^H-h ^i_h(s,a), and ℓ~i(⊥,a)=0 ^i( ,a)=0. Thus every nonzero loss entry in F~H,γ(M^) F_H,γ( M) has the form γH−h1HLi(a,b).γ^H-h 1HL^i(a,b). Since γ∈(0,1)∩ℚγ∈(0,1) is fixed, there is a constant cγ≥1c_γ≥ 1, depending only on γ, such that bits(γk)≤cγ(k+1)for all k≥0.bits(γ^k)≤ c_γ(k+1)\;for all k≥ 0. Also, bits(1H)≤O(log(H+1)).bits\! ( 1H )≤ O( (H+1)). Furthermore, there is a universal constant crat≥1c_rat≥ 1 such that, for every finite collection of rationals r1,…,rkr_1,…,r_k, bits(∏ℓ=1krℓ)≤crat(1+∑ℓ=1kbits(rℓ)).bits\! ( _ =1^kr_ )≤ c_rat (1+ _ =1^kbits(r_ ) ). Then, there exists a universal constant crat≥1c_rat≥ 1 such that every loss entry of F~H,γ(M^) F_H,γ( M) satisfies bits(γH−h2HLi(a,b)) \! (γ^H-h 2HL^i(a,b) ) ≤crat(cγ(H+1)+O(log(H+1))+bits(Li(a,b))+1) ≤ c_rat (c_γ(H+1)+O( (H+1))+bits(L^i(a,b))+1 ) ≤crat(cγ(H+1)+O(log(H+1))+(n+2)qsrc+1). ≤ c_rat (c_γ(H+1)+O( (H+1))+(n+2)^q_src+1 ). Since H≤BHlog(n+2)H≤ B_H (n+2), for sufficiently large nsizen_size we have β(F~H,γ(M^))≤(n+2)qsrc+2 β( F_H,γ( M))≤(n+2)^q_src+2 (27) for all n≥nsizen≥ n_size. Combining (26) and (27) we obtain |F~γ(M^)|≤max(n+2)4,n,(n+2)qsrc+2≤(n+2)d0, | F_γ( M)|≤ \(n+2)^4,n,(n+2)^q_src+2\≤(n+2)^d_0, where d0=max4,qsrc+2d_0= \4,q_src+2\. Together with |F~H,γ(M^)|≥n| F_H,γ( M)|≥ n, we have n≤|F~H,γ(M^)|≤(n+2)d0.n≤| F_H,γ( M)|≤(n+2)^d_0. ∎ Appendix F Details for the Numerical Experiments (Section 6) F.1 Implementation and evaluation protocol Both finite-horizon experiments use the four games specified below without any changes. The two experiments differ only in the feedback available to the players. F.2 Finite-Horizon Episodic Games Below, we list the transition and cost tables used for the finite-horizon experiments. F.2.1 Markov battle-of-the-sexes chain This is a two-player, two-action, horizon-22 game with state layers S1=0,S2=1,2,S3=3.S_1=\0\,\;S_2=\1,2\,\;S_3=\3\. At the initial state 00, the transition and costs are Joint action a Transition to (1,2)(1,2) c1(0,a)c_1(0,a) c2(0,a)c_2(0,a) (0,0)(0,0) (0.9,0.1)(0.9,0.1) 0.050.05 0.200.20 (1,1)(1,1) (0.1,0.9)(0.1,0.9) 0.200.20 0.050.05 (0,1),(1,0)(0,1),(1,0) (0.5,0.5)(0.5,0.5) 0.550.55 0.550.55 At the second layer, the game terminates deterministically. Explicitly, for s=1s=1, costs are c1(1,a) c_1(1,a) =0.15,a=(0,0),0.35,a=(1,1),0.65,a∈(0,1),(1,0),c2(1,a)=0.35,a=(0,0),0.15,a=(1,1),0.65,a∈(0,1),(1,0). = cases0.15,&a=(0,0),\\ 0.35,&a=(1,1),\\ 0.65,&a∈\(0,1),(1,0)\, cases c_2(1,a)= cases0.35,&a=(0,0),\\ 0.15,&a=(1,1),\\ 0.65,&a∈\(0,1),(1,0)\. cases For s=2s=2, c1(2,a) c_1(2,a) =0.15,a=(1,1),0.35,a=(0,0),0.65,a∈(0,1),(1,0),c2(2,a)=0.35,a=(1,1),0.15,a=(0,0),0.65,a∈(0,1),(1,0). = cases0.15,&a=(1,1),\\ 0.35,&a=(0,0),\\ 0.65,&a∈\(0,1),(1,0)\, cases c_2(2,a)= cases0.35,&a=(1,1),\\ 0.15,&a=(0,0),\\ 0.65,&a∈\(0,1),(1,0)\. cases F.2.2 Routing/congestion game This is a two-player, two-action, horizon-33 game with layers S1=0,S2=1,2,S3=3,4,S4=5.S_1=\0\,\;S_2=\1,2\,\;S_3=\3,4\,\;S_4=\5\. Actions are interpreted as route choices: 00 is an upper/fast route and 11 is a lower/safe route. Congestion occurs when both players choose the same action. At h=1h=1, let n0(a)=a1=0+a2=0n_0(a)=1\a_1=0\+1\a_2=0\ and κ(a)=a1=a2κ(a)=1\a_1=a_2\. The transition is P(1∣0,a)=0.75,n0(a)≤1,0.25,n0(a)=2,P(2∣0,a)=1−P(1∣0,a),P(1 0,a)= cases0.75,&n_0(a)≤ 1,\\ 0.25,&n_0(a)=2, cases P(2 0,a)=1-P(1 0,a), (28) with player-i cost ci(0,a)=0.10+0.45κ(a)+0.05ai.c_i(0,a)=0.10+0.45κ(a)+0.05a_i. At h=2h=2, for s∈1,2s∈\1,2\, P(3∣s,a)=0.85,s=1,κ(a)=0,0.35,s=1,κ(a)=1,0.35,s=2,κ(a)=0,0.15,s=2,κ(a)=1,P(4∣s,a)=1−P(3∣s,a),P(3 s,a)= cases0.85,&s=1,\ κ(a)=0,\\ 0.35,&s=1,\ κ(a)=1,\\ 0.35,&s=2,\ κ(a)=0,\\ 0.15,&s=2,\ κ(a)=1, cases P(4 s,a)=1-P(3 s,a), (29) with base cost 0.050.05 at state 11 and 0.200.20 at state 22: ci(s,a)=base(s)+0.50κ(a)+0.05ai=0.c_i(s,a)=base(s)+0.50κ(a)+0.051\a_i=0\. At h=3h=3, the game terminates. Costs are ci(s,a)=0.10+0.55κ(a)+pi(s,a),c_i(s,a)=0.10+0.55κ(a)+p_i(s,a), where pi(s,a)=0.10p_i(s,a)=0.10 if (s=3,ai=1)(s=3,a_i=1) or (s=4,ai=0)(s=4,a_i=0), and pi(s,a)=0p_i(s,a)=0 otherwise. F.2.3 Three-player public-goods game This game has m=3m=3, binary actions, horizon 22, and layers S1=0,S2=1,2,S3=3.S_1=\0\,\;S_2=\1,2\,\;S_3=\3\. Action 11 means contribute. Let k(a)=a1+a2+a3k(a)=a_1+a_2+a_3 be the number of contributors. At the first layer, P(1∣0,a)=0.85,k(a)≥2,0.20,k(a)<2,P(2∣0,a)=1−P(1∣0,a),P(1 0,a)= cases0.85,&k(a)≥ 2,\\ 0.20,&k(a)<2, cases P(2 0,a)=1-P(1 0,a), (30) with ci(0,a)=0.08+0.22ai+0.35max0,2−k(a)2.c_i(0,a)=0.08+0.22a_i+0.35 \0,2-k(a)\2. At the second layer, the game terminates. If s=1s=1, then ci(1,a)=0.10+0.18ai+0.08k(a)<1.c_i(1,a)=0.10+0.18a_i+0.081\k(a)<1\. (31) If s=2s=2, then ci(2,a)=0.55+0.15ai−0.10mink(a),2.c_i(2,a)=0.55+0.15a_i-0.10 \k(a),2\. (32) F.2.4 Transition-trap game This is a two-player, two-action, horizon-33 game with layers S1=0,S2=1,2,S3=3,4,S4=5.S_1=\0\,\;S_2=\1,2\,\;S_3=\3,4\,\;S_4=\5\. Action 00 is a shortcut and action 11 is safe. The shortcut gives lower immediate cost but increases the probability of entering a dangerous or trapped state. At h=1h=1, let n0(a)=a1=0+a2=0n_0(a)=1\a_1=0\+1\a_2=0\. The probability of moving to state 22 is pdanger(n0)=0.10,n0=0,0.50,n0=1,0.80,n0=2.p_danger(n_0)= cases0.10,&n_0=0,\\ 0.50,&n_0=1,\\ 0.80,&n_0=2. cases (33) The transition is P(2∣0,a)=pdanger(n0(a))P(2 0,a)=p_danger(n_0(a)), and the immediate cost is 0.050.05 for choosing action 00 and 0.130.13 for choosing action 11. At h=2h=2, from s=1s=1 the trap probability is (0.05,0.20,0.50)(0.05,0.20,0.50) for n0=0,1,2n_0=0,1,2, while from s=2s=2 it is (0.10,0.50,0.80)(0.10,0.50,0.80). The immediate cost is 0.060.06 for action 00 and 0.200.20 for action 11, with an additional 0.020.02 cost in state 22. At h=3h=3, the game terminates. In state 33, every action has cost 0.200.20. In the trap state 44, choosing shortcut action 00 costs 0.800.80, while action 11 costs 0.600.60. F.3 Discounted LQ Markov Game The discounted case is a two-player, two-state, zero-sum Markov game. The state is s∈0,1s∈\0,1\, player 0 chooses u∈[−U,U]u∈[-U,U], and player 1 chooses v∈[−U,U]v∈[-U,U]. Player 0 minimizes the raw cost gs(u,v)=r2u2−r2v2+bsuv+asu+dsv+ks,g_s(u,v)= r2u^2- r2v^2+b_suv+a_su+d_sv+k_s, (34) while player 1 minimizes −gs(u,v)-g_s(u,v). The transition is P(s′=1∣s,u,v)=ps+αsu+βsv.P(s =1 s,u,v)=p_s+ _su+ _sv. (35) For the numerical experiment, the raw zero-sum costs have been transformed by c0(s,u,v)=12+gs(u,v)2M,c1(s,u,v)=12−gs(u,v)2M.c_0(s,u,v)= 12+ g_s(u,v)2M, c_1(s,u,v)= 12- g_s(u,v)2M. (36) The parameters are s r bsb_s asa_s dsd_s ksk_s psp_s αs _s βs _s U γ M 00 1.501.50 0.350.35 1.101.10 0.900.90 −0.35-0.35 0.220.22 0.070.07 −0.055-0.055 11 0.900.90 2.402.40 11 1.501.50 −0.30-0.30 −1.05-1.05 −0.95-0.95 0.450.45 0.780.78 −0.05-0.05 0.0600.060 11 0.900.90 2.402.40 Also, our infinite-horizon benchmark can be viewed as a finite-state stochastic dynamic-game analogue of the classical two-player zero-sum LQ dynamic games studied in Başar and Olsder [1998]. F.3.1 Closed-form saddle-point solution Let VsV_s be the raw, unnormalized infinite-horizon discounted value of player 0 at state s, and define Δ:=V1−V0. :=V_1-V_0. The Bellman-Isaacs saddle-point equation is Vs=minumaxvgs(u,v)+γ[Vs′∣s,u,v].V_s= _u _v \g_s(u,v)+ [V_s s,u,v] \. Thus, [Vs′∣s,u,v] [V_s s,u,v] =(1−ps−αsu−βsv)V0+(ps+αsu+βsv)V1=V0+(ps+αsu+βsv)Δ. =(1-p_s- _su- _sv)V_0+(p_s+ _su+ _sv)V_1=V_0+(p_s+ _su+ _sv) . (37) Therefore the Bellman-Isaacs objective equals γV0+γpsΔ+ks+r2u2−r2v2+bsuv+As(Δ)u+Ds(Δ)v,γ V_0+γ p_s +k_s+ r2u^2- r2v^2+b_suv+A_s( )u+D_s( )v, (38) where As(Δ):=as+γαsΔ,Ds(Δ):=ds+γβsΔ.A_s( ):=a_s+γ _s ,\;D_s( ):=d_s+γ _s . Thus Vs=γV0+γpsΔ+ks+ϕs(Δ),V_s=γ V_0+γ p_s +k_s+ _s( ), (39) where ϕs(Δ):=minumaxvr2u2−r2v2+bsuv+As(Δ)u+Ds(Δ)v. _s( ):= _u _v \ r2u^2- r2v^2+b_suv+A_s( )u+D_s( )v \. The first-order saddle-point equations are ru+bsv+As(Δ)=0,−rv+bsu+Ds(Δ)=0.ru+b_sv+A_s( )=0, -rv+b_su+D_s( )=0. (40) Solving these gives us∗(Δ)=−rAs(Δ)+bsDs(Δ)r2+bs2,vs∗(Δ)=rDs(Δ)−bsAs(Δ)r2+bs2.u_s^*( )=- rA_s( )+b_sD_s( )r^2+b_s^2, v_s^*( )= rD_s( )-b_sA_s( )r^2+b_s^2. (41) Substituting (41) into the optimized quadratic yields ϕs(Δ)=12r(Ds(Δ)2−As(Δ)2)−2bsAs(Δ)Ds(Δ)r2+bs2. _s( )= 12 r (D_s( )^2-A_s( )^2 )-2b_sA_s( )D_s( )r^2+b_s^2. (42) Subtracting (39) for s=0s=0 from the same equation for s=1s=1 yields the scalar equation Δ=γ(p1−p0)Δ+(k1−k0)+ϕ1(Δ)−ϕ0(Δ). =γ(p_1-p_0) +(k_1-k_0)+ _1( )- _0( ). (43) Since ϕs _s is quadratic in Δ , equation (43) is a scalar quadratic. We solve this equation numerically, and select the feasible root whose saddle-point actions lie in [−U,U][-U,U], and then recovers V0=γp0Δ+k0+ϕ0(Δ)1−γ,V1=V0+Δ.V_0= γ p_0 +k_0+ _0( )1-γ,\;V_1=V_0+ . For the transformed normalized costs, the corresponding values are J0∗(s)=12+(1−γ)Vs2M,J1∗(s)=12−(1−γ)Vs2M.J_0^*(s)= 12+ (1-γ)V_s2M, J_1^*(s)= 12- (1-γ)V_s2M. (44)