Paper deep dive
Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics
Philip Jordan, Maryam Kamgarpour
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 7/8/2026, 10:53:05 AM
Summary
The paper proposes an independent learning algorithm for finding approximate Nash equilibria in partially observable Markov games (POMGs) with decoupled state dynamics and a potential structure. By assuming filter stability, the authors approximate the POMG with a finite-window superstate Markov game that preserves a near-potential structure, enabling communication-free, independent learning with quasi-polynomial sample and computational complexity.
Entities (8)
Relation Signals (5)
Independent Learning Algorithm → convergesto → Nash Equilibrium
confidence 95% · present an independent learning algorithm in which players, observing only their own actions and observations and without communication, jointly converge to an approximate Nash equilibrium.
Independent Learning Algorithm → achieves → Quasi-polynomial Complexity
confidence 93% · leading to quasi-polynomial sample and computational complexity for independent Nash equilibrium learning in the underlying POMG.
Decoupled Dynamics → issubclassof → Partially Observable Markov Games
confidence 92% · We focus on a subclass of POMGs with independent state transitions, where agents remain coupled through their rewards
Filter Stability Assumption → enablesapproximationof → Superstate Markov Game
confidence 90% · Under a filter stability assumption, we show that policies based on finite history windows provide sufficient approximation guarantees. This enables us to approximate the POMG by a surrogate Markov game that is near-potential
Markov Potential Games → enablesconvergenceof → Independent Learning Algorithm
confidence 88% · assume that the underlying fully observed Markov game is a Markov potential game. For this class, we present an independent learning algorithm
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study Nash equilibrium learning in partially observable Markov games (POMGs), a multi-agent reinforcement learning framework in which agents cannot fully observe the underlying state. Prior work in this setting relies on centralization or information sharing, and suffers from sample and computational complexity that scales exponentially in the number of players. We focus on a subclass of POMGs with independent state transitions, where agents remain coupled through their rewards, and assume that the underlying fully observed Markov game is a Markov potential game. For this class, we present an independent learning algorithm in which players, observing only their own actions and observations and without communication, jointly converge to an approximate Nash equilibrium. Due to partial observability, optimal policies may in general depend on the full action-observation history. Under a filter stability assumption, we show that policies based on finite history windows provide sufficient approximation guarantees. This enables us to approximate the POMG by a surrogate Markov game that is near-potential, leading to quasi-polynomial sample and computational complexity for independent Nash equilibrium learning in the underlying POMG.
Tags
Links
- Source: https://arxiv.org/abs/2605.06377v1
- Canonical: https://arxiv.org/abs/2605.06377v1
Trouble viewing inline? Open PDF directly →
Full Text
108,013 characters extracted from source content.
Expand or collapse full text
Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics Philip Jordan SYCAMORE, EPFL philip.jordan@epfl.ch &Maryam Kamgarpour SYCAMORE, EPFL maryam.kamgarpour@epfl.ch Abstract We study Nash equilibrium learning in partially observable Markov games (POMGs), a multi-agent reinforcement learning framework in which agents cannot fully observe the underlying state. Prior work in this setting relies on centralization or information sharing, and suffers from sample and computational complexity that scales exponentially in the number of players. We focus on a subclass of POMGs with independent state transitions, where agents remain coupled through their rewards, and assume that the underlying fully observed Markov game is a Markov potential game. For this class, we present an independent learning algorithm in which players, observing only their own actions and observations and without communication, jointly converge to an approximate Nash equilibrium. Due to partial observability, optimal policies may in general depend on the full action-observation history. Under a filter stability assumption, we show that policies based on finite history windows provide sufficient approximation guarantees. This enables us to approximate the POMG by a surrogate Markov game that is near-potential, leading to quasi-polynomial sample and computational complexity for independent Nash equilibrium learning in the underlying POMG. 1 Introduction Markov games have become the standard framework for modeling multi-agent reinforcement learning. In this framework, agents are typically assumed to have full access to the underlying state of the environment. However, in many practical settings, such as autonomous driving [27, 6], multi-robot control under sensor noise [27, 43], or strategic interactions in games of imperfect information [44], this assumption is violated due to noisy or partial state information. Partially observable Markov games (POMGs) extend the Markov game model by allowing each agent to receive only limited or noisy observations of the true state. Developing principled multi-agent learning methods for such partially observable settings remains a central challenge. Despite the broad applicability of POMGs, our understanding of their tractability, as well as the design of efficient algorithms with provable guarantees, remains limited. In contrast, in the single-agent setting of partially observable Markov decision processes (POMDPs), it is known that optimal policies may in general depend on the entire action-observation history [40], leading to computational intractability of the planning problem even for a single agent [39], as well as exponential statistical complexity for learning near-optimal policies [26]. However, these hardness results are worst-case in nature, and recent advances paint a clearer picture of rich POMDP subclasses that admit (quasi-) efficient learning and planning [19, 30]. These developments motivate investigating whether similar progress can be achieved in the multi-agent setting. Tractability under partial observability. Since the main challenge in POMDPs arises from the dependence of optimal policies on the full action-observation history, a large body of work studies structural conditions under which finite-window approximations become effective. One line of work achieves this by imposing richness conditions on the observations. In particular, the α-weakly revealing condition of [30] yields polynomial sample complexity, disregarding computational aspects. The related notion of γ-observability enables planning and learning algorithms with quasi-polynomial computational and sample complexity via intricate policy cover constructions [18, 19]. Furthermore, [18] shows that under this condition, and standard complexity-theoretic assumptions, polynomial-time algorithms are ruled out. Another family of positive algorithmic results is based on a filter stability assumption, under which the posterior distribution over states given the action-observation history converges exponentially fast, regardless of the initial prior. This enables practical finite-window approximations and has led to provable learning algorithms closer to those used in practice, including Q-learning [23], gradient methods [9], and temporal difference learning [4], that achieve quasi-polynomial computational and sample complexity [9, 4, 22]. These positive results in the single-agent setting raise the question of whether similar assumptions can enable provable methods for multi-agent learning under partial observability. While a large body of practical work proposes algorithms for POMGs [15, 38, 29, 33], only few provide theoretical guarantees. From a statistical perspective, [31] extends a sample-efficient POMDP approach [30] to POMGs under an α-weakly revealing condition, by replacing the policy optimization oracle used in [30] with an oracle for equilibrium computation. This leaves open the possibility of developing methods that are both statistically and computationally efficient. Achieving computationally efficient guarantees in the multi-agent setting is challenging even under full observability. In particular, Nash equilibrium computation is intractable in general Markov games, and already PPAD-hard for normal-form games [11]. As a result, much of the literature focuses on structured subclasses, among which Markov potential games are particularly well studied [34, 41]. In this setting, several independent learning algorithms have been shown to converge provably to Nash equilibria without requiring centralized coordination and scaling to large numbers of players [28, 14, 35]. Partially observable games with a common reward structure, captured by decentralized POMDPs (Dec-POMDPs) [8], form an important subclass of partially observable Markov potential games. A common approach in this setting is to assume that agents share information, effectively reducing the problem to a centralized decision process [13, 12, 36]. More recently, [32] establishes quasi-polynomial-time Nash equilibrium learning under γ-observability in cooperative POMGs by leveraging information sharing. However, this comes at the cost of an exponential dependence on the number of players, the so-called curse of multi-agency. Moreover, their results suggest that observability assumptions sufficient in the single-agent setting do not directly extend to decentralized multi-agent settings, where agents may form inconsistent beliefs due to differing local observations. Decoupled dynamics. Motivated by these challenges, we aim to design a communication-free independent learning algorithm that avoids the curse of multi-agency. To this end, we impose an additional structural assumption: while agents remain coupled through the reward function, their state dynamics are decoupled. Such models arise naturally in applications including wireless networks [3, 2], smart energy grids [16], autonomous driving, and multi-robot control [43]; see Appendix B for detailed illustrations. Decoupled dynamics have also been studied in the Markov game literature [47, 17] and their partially observable extension defines a rich subclass of POMGs. Contributions. In this work, we study POMGs with decoupled dynamics and potential structure under a filter stability assumption. Our approach builds on recent advances in approximating POMDPs by finite-state MDPs based on finite observation-action windows [23, 18, 9, 4, 22]. Extending this idea to the multi-agent setting, we approximate a decoupled POMG P by a Markov game mG^m defined over m-step history windows, termed superstate Markov game. We then establish the following: 1. We show that approximate Nash equilibria of the Markov game mG^m induce approximate Nash equilibria of the original POMG with explicit error bounds (Proposition 3.2). 2. Based on decoupledness of transition dynamics, we establish that the superstate Markov game mG^m admits a Markov near-potential structure [20, 21] (Proposition 3.2). 3. Building on recent independent learning methods for Markov potential games [47], we propose an independent learning algorithm for the superstate Markov game mG^m based on finite-window model estimation and soft policy iteration (see Algorithm 1). 4. We prove that the proposed algorithm converges to an ϵε-approximate Nash equilibrium of the underlying POMG with quasi-polynomial computational and sample complexity. In particular, the complexity does not scale exponentially with the number of players (see Theorem 1). The remainder of the paper is organized as follows. In Section 2, we introduce the formal problem setting. Section 3 develops the structural properties of the superstate Markov game. Building on these insights, Section 4 presents our independent learning algorithm, and Section 5 establishes its convergence guarantees. We conclude in Section 6. 2 Problem setting Let ℕ≔1,2,…N \1,2,… \ and ℕ0≔ℕ∪0N_0 ∪ \0 \. For n∈ℕn , let [n]≔1,2,…,n[n] \1,2,…,n \ and [n]0≔[n]∪0[n]_0 [n]∪ \0 \. For a,b∈ℕa,b with a≤ba≤ b, let [a,b]≔a,a+1,…,b−1,b[a,b] \a,a+1,…,b-1,b \. POMG. We consider N-player tabular finite-horizon partially observable Markov games in which transition and observation kernels are independent across players, but rewards are coupled. Formally, a POMG within this class is defined as a tuple =(,H,,,,r,ℙ,,μ)P=(N,H,S,A,O,r,P,O,μ) with players ≔[N]N [N], horizon H∈ℕH , finite state space ≔1×⋯×NS _1×…×S_N, finite action space =1×⋯×NA=A_1×…×A_N, and finite observation space ≔1×⋯×NO _1×…×O_N. Player i’s reward function at step h∈[H]h∈[H] is defined as ri,h:×→[0,1]r_i,h:S×A→[0,1]. State transition probabilities are given by ℙ=(ℙi,h)i∈,h∈[H]P= (P_i,h )_i ,h∈[H] with each player’s transition ℙi,h(⋅∣si,h,ai,h)∈Δ(i)P_i,h(· s_i,h,a_i,h)∈ (S_i) for si,h∈is_i,h _i, ai∈ia_i _i, and observation probabilities are given by =(i,h)i∈,h∈[H]O= (O_i,h )_i ,h∈[H] with i,h(⋅∣si,h)∈Δ(i)O_i,h(· s_i,h)∈ (O_i) for each i∈i . Observe that rewards are coupled through the dependence on joint states and actions, whereas state transitions and observations factor across players, as detailed below. At step h∈[H]h∈[H], when in state sh∈s_h , joint observation oh∈o_h is emitted with probability h(oh∣sh)=∏i∈i,h(oi,h∣si,h)O_h(o_h s_h)= _i O_i,h(o_i,h s_i,h), reflecting the decoupled observation structure, and each player i∈i observes its component oi,ho_i,h. Then, player i chooses an action ai,h∈ia_i,h _i and receives reward ri,h(sh,ah)r_i,h(s_h,a_h). Next, the unobserved state transitions to sh+1∈s_h+1 with probability ℙh(sh+1∣sh,ah)=∏i∈ℙi,h(si,h+1∣si,h,ai,h)P_h(s_h+1 s_h,a_h)= _i P_i,h(s_i,h+1 s_i,h,a_i,h), reflecting the decoupled transition structure. The initial state is drawn from the product distribution μ∈Δ()μ∈ (S), i.e., μ(s1)=∏i∈μi(s1,i)μ(s_1)= _i _i(s_1,i). Histories and policies. For each player i∈i and h∈ℕh , let ℋih≔(i×i)hH_i^h (A_i×O_i)^h be the set of h-step action-observation histories, and let ℋi0H_i^0 denote the empty history. Let ℋi≤h≔⋃h′∈[h]0ℋih′H_i^≤ h _h ∈[h]_0H_i^h . Let τi∈ℋih _i _i^h be a history written as τi=(ai,h′,oi,h′)h′=1h _i=(a_i,h ,o_i,h )_h =1^h. For k,l∈ℕk,l with k≤lk≤ l, we define the sub-history τi,k:l=(ai,h′,oi,h′)h′∈[k,l]∩[1,h] _i,k:l=(a_i,h ,o_i,h )_h ∈[k,l]∩[1,h]. In particular, τi,1:h=τi _i,1:h= _i. We denote by |τi|=h| _i|=h the length of τi _i. For each player i∈i , we define the class of history-dependent policies as ΠiH≔πi=(πi,h)h∈[H]∣πi,h:ℋih−1→Δ(i) for all h∈[H]. _i^H \ _i=( _i,h)_h∈[H] _i,h:H_i^h-1→ (A_i) for all h∈[H] \. We consider localized product policies π=(π1,…,πN)∈Π1H×⋯×ΠNHπ=( _1,…, _N)∈ _1^H×…× _N^H, meaning that at step h, given local histories τ=(τ1,…,τN)∈ℋh−1τ=( _1,…, _N) ^h-1, joint action a=(a1,…,aN)∈a=(a_1,…,a_N) is chosen by π∈ΠHπ∈ ^H with probability πh(a∣τ)=∏i∈πi,h(ai∣τi) _h(a τ)= _i _i,h(a_i _i). Moreover, for any joint policy π∈ΠHπ∈ ^H, we define for each i∈i the value function Vi(π)≔π,s1∼μ[∑h=1Hri,h(sh,ah)], V_i(π) _π,\,s_1 μ [ _h=1^Hr_i,h(s_h,a_h) ], (1) where the expectation is taken over the distribution of trajectories induced by the POMG P under the joint policy π, including the randomness from state transitions and observation emissions. Nash equilibria. Let ϵ>0ε>0. A joint policy π∈ΠHπ∈ ^H is called an ϵε-approximate Nash equilibrium if for all players i∈i and all πi′∈ΠiHπ _i∈ _i^H, it holds that Vi(π)≥Vi(πi′,π−i)−ϵV_i(π)≥ V_i(π _i, _-i)-ε. When ϵ=0ε=0, we call π a Nash equilibrium. Our objective in this paper is to provide an algorithm for learning ϵε-approximate Nash equilibria. Potential structure. The hardness of Nash equilibrium computation in the general-sum regime [11] motivates us to focus on a tractable subclass such as potential games. For i∈i , let Πi≔πi=(πi,h)h=1H∣πi,h:→Δ(i) _i \ _i=( _i,h)_h=1^H _i,h:S→ (A_i)\, and let Π≔Π1×⋯×ΠN _1×…× _N denote the set of Markov product policies. For π∈Ππ∈ , define the value function Vi(π)≔π,s1∼μ[∑h=1Hri,h(sh,ah)]V_i(π) _π,\,s_1 μ[ _h=1^Hr_i,h(s_h,a_h)]. Assumption 1. There exists a function Φ:Π→ℝ : such that for all i∈i , π∈Ππ∈ , and πi′∈Πi _i ∈ _i, Vi(π)−Vi(πi′,π−i)=Φ(π)−Φ(πi′,π−i). V_i(π)-V_i( _i , _-i)= (π)- ( _i , _-i). Assumption 1 represents the standard definition of Markov potential games and thus underlies a large body of work, see [28, 46] and others. Notably, in the decoupled setting considered here, this assumption is particularly simple to verify: it is equivalent to requiring that, at each state, the induced static (stage) game is a potential game [47]. Assumption 1 is satisfied in the fully cooperative case r1=⋯=rNr_1=…=r_N, as well as in practical settings such as demand-response markets [37], and other mixed cooperative/competitive scenarios for which [37] provides several sufficient conditions. Before turning to the main objective of Nash equilibrium learning, the next section first establishes structural properties of the considered games which will then guide our algorithm design in Section 4. 3 Approximating POMGs via Markov near-potential games In this section, we show that any decoupled POMG can be approximated by a Markov game, which we term the superstate Markov game, obtained via a finite-window approximation based on truncated histories. This extends related approaches from the single-agent setting [23, 18, 9] to the multi-agent case. We establish that the resulting superstate Markov game approximately preserves Nash equilibria of the original POMG (Proposition 3.2) and admits a near-potential structure (Proposition 3.2). These properties provide a key insight enabling us to lift techniques from Markov potential games to the partially observable case and will play a central role in the analysis of our algorithm in Section 4. Superstate Markov game. The superstate Markov game mG^m has state space ℋ≤mH^≤ m and action space A. Concretely, at step h, the state is given by w=(wi)i∈w=(w_i)_i , where we use the notation wi=(ai,h−m,oi,h−m,…,ai,h−1,oi,h−1)∈ℋimin(h−1,m)w_i=(a_i,h-m,o_i,h-m,…,a_i,h-1,o_i,h-1) _i (h-1,m) for the most recent m-step local history of player i. To define the transition dynamics of the superstate Markov game, we introduce a belief over latent states induced by truncated histories. Since truncated histories do not, in general, determine the posterior distribution of the underlying state, for each player i∈i and step h∈[H]h∈[H], we define the belief bi,hm(si∣wi)b^m_i,h(s_i w_i) as the probability that player i is in state sis_i at step h after observing the window wiw_i, starting from the initial distribution111Instead of μi _i, one could use an arbitrary prior over iS_i. μi _i. Formally, this is obtained by marginalizing over all local state trajectories consistent with wiw_i, bi,hm(si∣wi) b^m_i,h(s_i w_i) =1Zi(wi)∑si1,…,sim∈iμi(si1)[∏k=1m−1ℙi,h−m+k−1(sik+1∣sik,ai,h−m+k−1) = 1Z_i(w_i) _s^1_i,…,s^m_i _i _i(s^1_i) [ _k=1^m-1P_i,\,h-m+k-1(s^k+1_i s^k_i,a_i,h-m+k-1) i,h−m+k−1(oi,h−m+k−1∣sik)]⋅ℙi,h−1(si∣sim,ai,h−1)i,h−1(oi,h−1∣sim), _i,\,h-m+k-1(o_i,h-m+k-1 s^k_i) ]·P_i,\,h-1(s_i s^m_i,a_i,h-1)\;O_i,\,h-1(o_i,h-1 s^m_i), where the normalization factor Zi(wi)Z_i(w_i) is the sum over si∈is_i _i of the unnormalized probabilities of reaching sis_i. Intuitively, this expression averages over all latent state sequences that could have generated the observed window wiw_i, each weighted by its likelihood under the model. For h∈[H]h∈[H], w,w′∈ℋ≤mw,w ^≤ m, a∈a , and o∈o with |w′|=n|w |=n and w′=(w∘(a,o))n−m+2:n+1w =(w (a,o))_n-m+2:n+1, ℙhm(w′∣w,a)≔∑s∈h(o∣s)∏i∈bi,hm(si∣wi). _h^m(w w,a)\; \; _s O_h(o s) _i b^m_i,h(s_i w_i). (2) Otherwise, if w′w cannot be obtained by concatenating w with any action-observation pair, we set ℙhm(w′∣w,a)=0P_h^m(w w,a)=0. Similarly, we define rewards ri,hm(w,a)≔∑s∈ri,h(s,a)∏j∈bj,hm(sj∣wj)r_i,h^m(w,a) _s r_i,h(s,a) _j b^m_j,h(s_j w_j). Moreover, for policy π∈Πmπ∈ ^m, its value in mG^m is defined as Vim(π)≔π,s1∼μ[∑h=1Hri,hm(wh,ah)] V^m_i(π) _π,\,s_1 μ [ _h=1^Hr^m_i,h(w_h,a_h) ] where the expectation is taken over the randomness of the policy and the superstate transitions ℙmP^m. By construction, mG^m is a Markov game with a finite state space. Moreover, due to the decoupled structure of the underlying dynamics and observations, its transition kernel factorizes across players. Importantly, mG^m is a conceptual object used for analysis: it is defined via a finite-window truncation of histories, which does not correspond to the true evolution of observations in the POMG. In particular, trajectories are generated by the underlying POMG, where observations depend on the full history, and therefore do not follow the superstate transition kernel ℙmP^m. We note that for m=Hm=H, we obtain a Markov game with state space corresponding to the full action-observation histories. This model is equivalent to the POMG in the sense that any joint policy over histories induces the same trajectory distribution and value in both models. 3.1 Finite-window policies and filter stability Having defined the superstate Markov game mG^m, we aim to establish that its Nash equilibria over finite-window policies correspond to approximate Nash equilibria of the original POMG. Such a guarantee would justify using mG^m as a surrogate game in the analysis of learning algorithms. In order to argue about finite-window Nash equilibria, we first introduce the respective policy class. Finite-window policies. For any m∈[H]m∈[H], and each player i∈i , let Πim≔πi=(πi,h)h∈[H]∣πi,h:ℋimin(h−1,m)→Δ(i) for all h∈[H]. _i^m \ _i=( _i,h)_h∈[H] _i,h:H_i (h-1,m)→ (A_i) for all h∈[H] \. We further define joint finite-window policies given by product policies π=(π1,…,πN)∈Π1m×⋯×ΠNmπ=( _1,…, _N)∈ _1^m×…× _N^m, meaning that at step h, given local histories τ=(τ1,…,τN)∈ℋh−1τ=( _1,…, _N) ^h-1, a∈a is chosen with probability π′(a∣τh−m:h−1)=∏i∈πi′(ai∣τi,h−m:h−1)π (a _h-m\,:\,h-1)= _i π _i(a_i _i,h-m\,:\,h-1). We note that Πm ^m can be seen as a subclass of ΠH ^H by associating to each π∈Πmπ∈ ^m its extension to ΠH ^H that depends only on the most recent m steps of history. Thus, for i∈i and π∈Πmπ∈ ^m, the value Vi(π)V_i(π) is defined as in (1). Without further assumptions, relevant information about the state may reside arbitrarily far in the past, and it is not clear whether finite-window approximation can yield meaningful guarantees. We therefore introduce a standard condition that ensures sufficient decay of past information. Filter stability. Filter stability formalizes the idea that the influence of initial beliefs decays exponentially over time, and has been studied in prior work on hidden Markov models [42] and POMDPs [23, 4]. For h∈[H]h∈[H], and joint history τ∈ℋhτ ^h, we let bh(⋅∣τ)∈Δ()b_h(· τ)∈ (S) denote the posterior distribution over joint states S. For ν,ν′∈Δ()ν,ν ∈ (S), define the total variation distance ‖ν−ν′‖TV≔12∑s∈|ν(s)−ν′(s)|\|ν-ν \|_TV 12 _s |ν(s)-ν (s)|. Assumption 2. There exists ρ>0ρ>0 such that for all h∈[H]h∈[H], τ,τ′∈ℋhτ,τ ^h, a∈a , and o∈o , ∥bh(⋅∣τ∘(a,o))−bh(⋅∣τ′∘(a,o))∥TV≤(1−ρ)∥bh(⋅∣τ)−bh(⋅∣τ′)∥TV b_h(· τ (a,o))-b_h(· τ (a,o)) _TV≤(1-ρ) b_h(· τ)-b_h(· τ ) _TV where ∘ denotes concatenation. Filter stability requires (a) state transitions to be sufficiently mixing, and (b) observations to be sufficiently noisy. We refer to [24] for a sufficient condition that formalizes these requirements in terms of Dobrushin coefficients of the transition and observation kernel. 3.2 Finite-window Nash equilibrium approximation and near-potential structure Based on the filter stability assumption above, we aim to show that Nash equilibria of the superstate Markov game over the finite-window policy class Πm ^m correspond to approximate Nash equilibria of the POMG over the full-history class ΠH ^H. This approximation result will allow us to analyze equilibria in the tractable superstate setting while retaining guarantees for the original POMG. In addition, we establish that the superstate Markov game admits a near-potential structure, which will enable us to prove convergence of our learning algorithm. For the single-agent case, it is known that under filter stability, the optimal value of a superstate MDP approximates the optimal value of the corresponding POMDP, see Theorem 2 of [4]. We extend this guarantee to the multi-agent setting by establishing value approximation results for joint policies, as well as for best-response values. Notably, this result, as well as Proposition 3.2 below, hold for general POMGs and do not rely on the decoupled dynamics assumption. restatablelemmavalueapproxlemma Let π∈Πmπ∈ ^m and π′∈ΠHπ ∈ ^H such that for all h≥mh≥ m and all w∈ℋmw ^m, τ∈ℋhτ ^h with w=τh−m+1:hw= _h-m+1:h, it holds that πh(⋅∣w)=πh′(⋅∣τ) _h(· w)=π _h(· τ). Let ϵρm≔4H2(1−ρ)m. ε^m_ρ 4H^2(1-ρ)^m. (3) Under Assumption 2, for any i∈i , we have |Vim(π)−Vi(π′)|≤ϵρm. |V^m_i(π)-V_i(π ) |≤ε^m_ρ. Moreover, for π and π′π as above, it holds that |maxπ^i∈ΠimVim(π^i,π−i)−maxπ^i′∈ΠiHVi(π^i′,π−i)|≤ϵρm. | _ π_i∈ ^m_iV^m_i( π_i, _-i)- _ π_i ∈ ^H_iV_i( π_i , _-i) |≤ε^m_ρ. We are then able to connect equilibria of the superstate Markov game to those of the original POMG. restatablepropositionapproxneprop Let ϵ>0ε>0, and let π∈Πmπ∈ ^m be an ϵε-approximate Nash equilibrium of the superstate Markov game mG^m. Under Assumption 2, π is an (ϵ+2ϵρm)(ε+2ε^m_ρ)-approximate Nash equilibrium of P. The proofs of Lemma 3.2 and Proposition 3.2 are provided in Appendix C. The following result shows that mG^m inherits a near-potential structure [20], suggesting that efficient learning in the superstate Markov game is possible. restatablepropositionalphapotentialprop Under Assumption 1, there exists a function Ψ:Πm→ℝ : ^m such that for all π∈Πmπ∈ ^m, i∈i , and πi′∈Πim _i ∈ ^m_i, and ϵρm _ρ^m as in (3), we have |(Vim(π)−Vim(πi′,π−i))−(Ψ(π)−Ψ(πi′,π−i))|≤2ϵρm. | (V^m_i(π)-V^m_i( _i , _-i) )- ( (π)- ( _i , _-i) ) |≤ 2ε^m_ρ. The proof is deferred to Appendix C. At a high level, the decoupled structure allows state visitation distributions to factor across players, enabling the construction of a potential function for the POMG, which then transfers approximately to the finite-window setting. Building upon these structural properties, we now turn to the question of learning in POMGs. 4 Independent Nash equilibrium learning algorithm In this section, we design a learning algorithm for decoupled POMGs with potential structure. We begin by stating the learning objective and protocol, then we outline our approach. Learning Objective. Given ϵ>0ε>0, our objective is to efficiently learn a finite-window policy π∈Πmπ∈ ^m such that π is an ϵε-approximate Nash equilibrium of the POMG, that is, for all i∈i and all deviations with full history dependence πi′∈ΠiHπ _i∈ _i^H, it holds that Vi(π)≥Vi(πi′,π−i)−ϵV_i(π)≥ V_i(π _i, _-i)-ε. Independent learning protocol. We consider an independent learning setting [45, 10, 14] in which players interact with the game over a fixed number of episodes. Within each episode, every player follows a fixed policy πi∈Πm _i∈ ^m, observes only its own sequence of actions, observations, and rewards, and then updates its policy individually. Players do not observe other agents’ actions, observations, rewards, or policies. Moreover, no information is shared among players or with any central entity. We do assume, however, that all players agree in advance to follow the same algorithm, which places the resulting dynamics in the self-play regime [7]. Our algorithm (Algorithm 1) closely follows the method of [47] for fully observable Markov games, applied to the superstate game. The main challenges arise in the analysis, which we outline in the proof overviews in Section 5. Algorithm 1 Learning Finite-Window Policy in POMG (at player i) 1: Input: iteration number K, episode number T, window length m, stepsizes η(k)η^(k) for k∈[K]k∈[K]. 2: Initialize πi,h(0)=1/|i| _i,h^(0)=1/|A_i| for all h∈[H]h∈[H]. 3: for k=0,1,…,K−1k=0,1,…,K-1 do 4: Collect trajectory τi=((ai,h(t),oi,h(t),ri,h(t))h=1H)t=1T _i=((a^(t)_i,h,o^(t)_i,h,r_i,h^(t))_h=1^H)_t=1^T by following πiϵ,(k)≔ϵ(i)+(1−ϵ)πi(k) _i^ε,(k) (A_i)+(1-ε) _i^(k), i.e., ai,h(t)∼(i)a^(t)_i,h (A_i) w.p. ϵε and ai,h(t)∼πi,h(k)(⋅∣wi,h(t))a^(t)_i,h _i,h^(k)(· w_i,h^(t)) otherwise, for all h∈[H]h∈[H] and t∈[T]t∈[T]. 5: Estimate ℙ^i,hm P^m_i,h and r^im,π−i(k) r^m,π^(k)_-i_i based on empirical frequencies (see Appendix D for details). 6: Let Q^i,H+1(k)(wi,ai)≔0 Q^(k)_i,H+1(w_i,a_i) 0 for all wi∈ℋi≤m,ai∈iw_i ^≤ m_i,a_i _i. 7: for h=H,…,1h=H,…,1 do 8: for wi∈ℋi≤m,ai∈iw_i ^≤ m_i,a_i _i do 9: Q^i,h(k)(wi,ai)≔r^i,hm,π−i(wi,ai)+∑wi′,ai′ℙ^i,hm(wi′∣wi,ai)πi,h+1(k)(ai′∣wi′)Q^i,h+1(k)(wi′,ai′) Q^(k)_i,h(w_i,a_i) -1.0pt -1.0pt r_i,h^m, _-i(w_i,a_i)+ _w_i ,a_i -2.0pt P_i,h^m(w_i w_i,a_i)π^(k)_i,h+1(a_i w_i ) Q^(k)_i,h+1(w_i ,a _i). 10: πi,h(k+1)(ai∣wi)≔(1−η(k))πi,h(k)(ai∣wi)+η(k)ai∈argmaxai′Q^i,h(k)(wi,ai′) _i,h^(k+1)(a_i w_i) -1.0pt -1.0pt(1-η^(k)) _i,h^(k)(a_i w_i)+η^(k)1 \a_i∈ _a_i Q^(k)_i,h(w_i,a_i ) \. 11: end for 12: end for 13: end for 4.1 Independent soft policy iteration A key challenge in independent learning in Markov games, even under decoupled transitions, is that each player’s value function depends on the joint policy of all players through the coupled rewards. However, when fixing any π−i _-i in the superstate Markov game mG^m, player i faces an MDP ℳπ−iM _-i with state space iS_i, action space iA_i, transition kernel ℙimP_i^m as defined in (2), and reward ri,hm,π−i(wi,ai) r_i,h^m, _-i(w_i,a_i) ≔w−i∼d−i,hm,π,a−i∼π−i(⋅∣w−i)[ri,hm(wi,w−i,ai,a−i)], _w_-i d^m,π_-i,h,a_-i _-i(· w_-i) [r_i,h^m(w_i,w_-i,a_i,a_-i) ], where di,hm,π(wi,h)≔Pπ(wi,h=wi)d^m,π_i,h(w_i,h) P_π(w_i,h=w_i), and d−i,hm,π(w−i,h)≔∏j∈∖idj,hm,π(wj)d^m,π_-i,h(w_-i,h) _j \i\d^m,π_j,h(w_j). Note that here PπP_π is taken over the randomness of policy π and transition kernel ℙmP^m. We further denote the Q-function of ℳπ−iM _-i by Q¯i,hm,π:ℋi≤m×i→ℝ Q^m,π_i,h:H_i^≤ m×A_i . Observe that if a policy π⋆∈Πmπ ∈ ^m is such that for all i∈i , πi⋆π _i achieves the optimal value in ℳπ−i⋆M^π _-i, then π⋆π is a Nash equilibrium of mG^m. This motivates having each player perform policy iteration with respect to Q¯i,hm,π Q^m,π_i,h in the hope of converging to a joint policy that satisfies this playerwise optimality in ℳπ−iM _-i. However, in a game setting, such simultaneous updates may lead to cyclic patterns that fail to converge [48]. In contrast, the smoothed version with appropriately chosen stepsize 0<η(k)<10<η^(k)<1, as implemented in Line 10 of Algorithm 1, has been shown to converge to an approximate Nash equilibrium in Markov potential games [47]. It remains to describe how to obtain Q¯i,hm,π(k) Q^m,π^(k)_i,h. As the Q-function of an MDP, namely ℳπ−i(k)M^π^(k)_-i, Q¯i,hm,π(k) Q^m,π^(k)_i,h satisfies the Bellman expectation equation, which allows us to compute an estimate Q^i,h(k) Q^(k)_i,h via backward iteration (see Line 9 of Algorithm 1). This computation relies on having estimates ℙ^im P_i^m and r^i,hm,π−i(k) r_i,h^m,π^(k)_-i of the transition kernel of ℳπ−i(k) M _-i^(k). We next describe how to obtain these estimates for the superstate game from interaction with the POMG at each iteration. 4.2 Sampling & model estimation As we do not assume access to transition kernels or a generative model, players sample action-observation sequences over T episodes by simultaneously interacting with the POMG and receiving their respective observations and rewards. At iteration k and step h, in order to ensure exploration of actions, player i∈i takes an action uniformly at random with probability ϵε, and otherwise follows its current policy πi,h(k) _i,h^(k). Based on the observed sequences τi=ai,h(t),oi,h(t),ri,h(t)h=1Ht=1T _i=\\a_i,h^(t),o_i,h^(t),r_i,h^(t)\_h=1^H\_t=1^T, we apply standard model estimation techniques inspired by single-agent methods [5, 25] as detailed below. Transition estimation. For each player i∈i , we estimate the superstate transition probabilities ℙim(⋅∣wi,ai)P_i^m(· w_i,a_i) by empirical frequencies of m-step window transitions. Concretely, for each pair (wi,ai)∈ℋi≤m×i(w_i,a_i) _i^≤ m×A_i, we collect all time steps at which the m-step history window equals wiw_i and action aia_i is played, and record the resulting next window wi′∈ℋi≤mw_i _i^≤ m. The estimate ℙ^im(wi′∣wi,ai) P_i^m(w_i w_i,a_i) is given by the relative frequency of observing wi′w_i among these occurrences. If a pair (wi,ai)(w_i,a_i) is not observed, the estimate is set to 0. Reward estimation. Similarly, we estimate the reward function ri,hm,π−i(k)r_i,h^m,π^(k)_-i of ℳπ−i(k) M _-i^(k) by empirical averaging. For each (wi,ai)∈ℋi≤m×i (w_i,a_i) _i^≤ m×A_i, we average the rewards observed at time steps where the history window equals wiw_i and action aia_i is taken. If (wi,ai)(w_i,a_i) is not observed, the estimate is set to 0. For formal definitions of the estimates ℙ^im P_i^m and r^i,hm,π−i(k) r_i,h^m,π^(k)_-i, we refer to Appendix D. A key challenge towards establishing guarantees for Algorithm 1 lies in deriving confidence bounds for this sampling procedure. We provide further insight on this in the proof overview of Lemma 3 in the next section. 5 Convergence to Nash equilibrium In this section, we present our main result, Theorem 1, which provides the convergence guarantee for Algorithm 1 towards an approximate Nash equilibrium. Our analysis relies on establishing confidence bounds for the estimated superstate model ℙ^im P_i^m and r^i,hm,π−i r_i,h^m, _-i (see Lemma 3 below). This in turn requires that all m-step history windows are well explored. A sufficient condition is that, at each superstate, all actions are selected and all observations are realized with probabilities bounded away from zero. For actions, this is ensured by the ϵε-greedy exploration strategy in Line 4 of Algorithm 1. For observations, we impose the following assumption. Assumption 3. There exists β>0β>0 such that for all i∈i , si∈is_i _i and oi∈io_i _i, i(oi∣si)≥βO_i(o_i s_i)≥β. We note that Assumption 3 can be enforced, for example, by having each player inject a small amount of uniform noise into its observations, ensuring that every observation occurs with probability bounded away from zero. Next, based on this assumption, we state the estimation confidence bounds. restatable lemmaestproblemma Let Assumptions 2 and 3 hold, and let π∈Πmπ∈ ^m. Suppose each player i∈i collects a trajectory according to Line 4 in Algorithm 1, and estimates ℙ^im P^m_i and r^im,π−i r^m, _-i_i according to (6) and (7), respectively. Let i∈i , h∈[H]h∈[H], ai∈ia_i _i, and wi,wi′∈ℋi≤mw_i,w_i _i^≤ m. Then for any 0<ϵ≤10<ε≤ 1, it holds that P(|ℙi,hm(wi′∣wi,ai)−ℙ^i,hm(wi′∣wi,ai)|≥ϵ+(1−ρ)m) P (|P^m_i,h(w_i w_i,a_i)- P_i,h^m(w_i w_i,a_i)|≥ε+(1-ρ)^m ) ≤4exp(−ϵ2m+2β2mT32|i|2m), ≤ 4 (- ε^2m+2β^2mT32|A_i|^2m ), P(|ri,hm,π−i(wi,ai)−r^i,hm,π−i(wi,ai)|≥4NHϵ+N2H(1−ρ)m) P (|r_i,h^m, _-i(w_i,a_i)- r_i,h^m, _-i(w_i,a_i)|≥ 4NHε+N^2H(1-ρ)^m ) ≤4exp(−ϵ2m+2β2mT32|i|2m). ≤ 4 (- ε^2m+2β^2mT32|A_i|^2m ). Proof overview. The main challenge we face is a mismatch between superstate Markov game and the underlying POMG process: action-observation sequences are collected from the POMG kernel with full history dependence ℙHP^H, rather than the superstate Markov game kernel ℙmP^m. While this issue arises already in POMDPs [9, 4, 22], it is compounded in the game setting since rewards depend on other agents’ superstates. We handle this by decomposing the estimation error of ℙ^i,hm P_i,h^m and r^i,hm,π−i r_i,h^m, _-i into a statistical term arising from randomness of the policy and environment, and a bias term due to the finite-window approximation (Lemma 3). The first term is controlled by a concentration argument across the independently sampled episodes, while the bias term is bounded under Assumption 2 by analyzing how mismatch propagates through other agents’ states (Lemma 5). Compared to the corresponding result for Markov games (see [47], Lemma 4), we highlight the additional bias terms (1−ρ)m(1-ρ)^m and N2H(1−ρ)mN^2H(1-ρ)^m in the above bounds, that stem from the superstate approximation error. For the full proof of Lemma 3 and its supporting results, we refer to Appendix E. It is standard for sample-based single- and multi-agent reinforcement learning methods to require certain assumptions on the state visitation distribution [1, 28, 14]. As in the Markov game case (Assumption 1 in [47]), we impose the following condition ensuring sufficient exploration. Assumption 4. There exists α>0α>0 such that for any policy π∈Πmπ∈ ^m, and for all i∈i , h∈[H]h∈[H], and si∈is_i _i, we have di,hπ(si)≥αd^π_i,h(s_i)≥α. Next, we state our guarantee for Algorithm 1 in learning an approximate Nash equilibrium. Theorem 1. Let Assumptions 1, 2, 3, and 4 hold. For ϵ>0ε>0, δ>0δ>0, suppose each player i∈i runs Algorithm 1 simultaneously with stepsizes η(k)=Θ(1/N2H3k)η^(k)= (1/ N^2H^3k), and m≥c1⋅ρ−1log(NHAOαβϵ),T≥c2⋅A2m+2H6O2N2αβ2mϵ2m+2log(1/δ),K≥c3⋅H5N4A2α2ϵ2, m≥ c_1·ρ^-1 ( NHAOαβε ), T≥ c_2· A^2m+2H^6O^2N^2αβ^2mε^2m+2 (1/δ), K≥ c_3· H^5N^4A^2α^2ε^2, where c1,c2,c3∈ℕc_1,c_2,c_3 are constants independent of the problem parameters, and A≔maxi∈|i|A _i |A_i|, O≔maxi∈|i|O _i |O_i|. Then, with probability 1−δ1-δ, there exists k∈[K]k∈[K] such that the joint policy π(k)π^(k) is an ϵε-approximate Nash equilibrium of the POMG P. The sample and computational complexity of Algorithm 1 are at most ((NHAOβαϵ)(ρ−1log(A/(βϵ)))log(1/δ)). ( ( NHAOβαε )^O(ρ^-1 (A/(βε))) (1/δ) ). (4) Proof overview. Although the superstate game need not admit an exact potential, it satisfies a near-potential property (Proposition 3.2). This ensures that each iteration of soft policy iteration yields an approximate improvement, up to an error on the order of H2(1−ρ)mH^2(1-ρ)^m (Lemma 7). Choosing m appropriately controls the accumulated error and yields convergence. For the full proof, we refer to Appendix E. (Quasi-)efficiency. We highlight that the sample and computational complexity (4) is quasi-polynomial, and in particular does not scale exponentially in the number of players N. Thus, in our decoupled potential game setting, Algorithm 1 breaks the curse of multi-agency. Window size tradeoff. The choice of the window size m induces a tradeoff between approximation accuracy and statistical efficiency. Larger values of m reduce the approximation error of the value in the superstate Markov game relative to the respective value in the original POMG (see Propositions 3.2 and 3.2), but increase the sampling complexity required to accurately estimate the superstate model (see Lemma 3). Choosing m on a logarithmic scale as in Theorem 1 balances these effects. Comparison with prior work. Compared to [31], our framework relies on a different structural assumption, filter stability rather than observability, and focuses on decoupled dynamics with potential structure. This restriction enables an independent learning approach that does not rely on computationally intractable oracles. In contrast to [32], our setting does not require information sharing. Moreover, unlike [31, 32] our method does not suffer from the curse of multi-agency. 6 Conclusion We studied Nash equilibrium learning in partially observable Markov games under decoupled dynamics and potential structure. We proposed an independent learning algorithm that converges to an approximate Nash equilibrium with quasi-polynomial sample and computational complexity. Our analysis is based on a superstate Markov game representation, which we show approximately preserves equilibria and admits a near-potential structure. Limitations and future work. The setting of POMGs with decoupled dynamics and potential structure forms a rich but still restricted subclass of POMGs. Understanding the boundary between tractable and intractable regimes remains an important direction for future work. Another limitation is Assumption 4, which restricts transition dynamics to guarantee exploration of superstates; relaxing this to weaker distribution mismatch conditions, as in [1, 14], is an interesting direction. To the best of our knowledge, this is the first work on provable independent learning in POMGs. Our results open up new possibilities for independent learning in partially observable multi-agent systems and provide a starting point for further extensions to other game classes, such as two-player zero-sum games, and to broader equilibrium notions, including coarse correlated equilibria in general-sum games. References [1] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan (2021) On the theory of policy gradient methods: optimality, approximation, and distribution shift. Journal of Machine Learning Research 22 (98), p. 1–76. Cited by: §5, §6. [2] E. Altman, K. Avrachenkov, I. Menache, G. Miller, B. J. Prabhu, and A. Shwartz (2009) Dynamic discrete power control in cellular networks. IEEE Transactions on Automatic Control 54 (10), p. 2328–2340. Cited by: §B.1, §1. [3] E. Altman, K. Avratchenkov, N. Bonneau, M. Debbah, R. El-Azouzi, and D. S. Menasché (2007) Constrained stochastic games in wireless networks. In IEEE GLOBECOM 2007-IEEE Global Telecommunications Conference, p. 315–320. Cited by: §B.1, §1. [4] A. Anjarlekar, S. R. Etesami, and R. Srikant (2025) Scalable policy-based RL algorithms for POMDPs. Advances in Neural Information Processing Systems. Cited by: §C.1, §1, §1, §3.1, §3.2, §5. [5] M. G. Azar, R. Munos, and H. Kappen (2012) On the sample complexity of reinforcement learning with a generative model. In International Conference on Machine Learning, Cited by: §4.2. [6] H. Bai, S. Cai, N. Ye, D. Hsu, and W. S. Lee (2015) Intention-aware online POMDP planning for autonomous driving in a crowd. In International Conference on Robotics and Automation, p. 454–460. Cited by: §1. [7] Y. Bai and C. Jin (2020) Provable self-play algorithms for competitive reinforcement learning. In International Conference on Machine Learning, p. 551–560. Cited by: §4. [8] D. S. Bernstein, R. Givan, N. Immerman, and S. Zilberstein (2002) The complexity of decentralized control of Markov decision processes. Mathematics of operations research 27 (4), p. 819–840. Cited by: §1. [9] S. Cayci, N. He, and R. Srikant (2024) Finite-time analysis of natural actor-critic for POMDPs. SIAM Journal on Mathematics of Data Science 6 (4), p. 869–896. Cited by: §1, §1, §3, §5. [10] C. Daskalakis, D. J. Foster, and N. Golowich (2020) Independent policy gradient methods for competitive reinforcement learning. Advances in Neural Information Processing Systems. Cited by: §4. [11] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou (2009) The complexity of computing a Nash equilibrium. Communications of the ACM 52 (2), p. 89–97. Cited by: §1, §2. [12] J. Dibangoye and O. Buffet (2018) Learning to act in decentralized partially observable MDPs. In International Conference on Machine Learning, p. 1233–1242. Cited by: §1. [13] J. S. Dibangoye, C. Amato, O. Buffet, and F. Charpillet (2016) Optimally solving Dec-POMDPs as continuous-state MDPs. Journal of Artificial Intelligence Research 55, p. 443–497. Cited by: §1. [14] D. Ding, C. Wei, K. Zhang, and M. Jovanovic (2022) Independent policy gradient for large-scale Markov potential games: sharper rates, function approximation, and game-agnostic convergence. In International Conference on Machine Learning, p. 5166–5220. Cited by: §1, §4, §5, §6. [15] R. Emery-Montemerlo, G. Gordon, J. Schneider, and S. Thrun (2004) Approximate solutions for partially observable stochastic games with common payoffs. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, 2004. AAMAS 2004., p. 136–143. Cited by: §1. [16] S. R. Etesami, W. Saad, N. B. Mandayam, and H. V. Poor (2018) Stochastic games for the smart grid energy management with prospect prosumers. IEEE Transactions on Automatic Control 63 (8), p. 2327–2342. Cited by: §B.1, §1. [17] S. R. Etesami (2024) Learning stationary nash equilibrium policies in n-player stochastic games with independent chains. SIAM Journal on Control and Optimization 62 (2), p. 799–825. Cited by: §1. [18] N. Golowich, A. Moitra, and D. Rohatgi (2022) Learning in observable POMDPs, without computationally intractable oracles. Advances in Neural Information Processing Systems. Cited by: §1, §1, §3. [19] N. Golowich, A. Moitra, and D. Rohatgi (2023) Planning and learning in partially observable systems via filter stability. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, p. 349–362. Cited by: §1, §1. [20] X. Guo, X. Li, C. Maheshwari, S. Sastry, and M. Wu (2025) Markov α-potential games. IEEE Transactions on Automatic Control. Cited by: item 2, §3.2. [21] X. Guo, X. Li, and Y. Zhang (2025) An α-potential game framework for N-player dynamic games. SIAM Journal on Control and Optimization 63 (4), p. 2964–3005. Cited by: item 2. [22] P. Jordan and M. Kamgarpour (2026) Model-based learning of near-optimal finite-window policies in POMDPs. arXiv preprint arXiv:2604.01024. Cited by: §1, §1, §5. [23] A. D. Kara and S. Yüksel (2023) Convergence of finite memory Q-learning for POMDPs and near optimality of learned policies under filter stability. Mathematics of Operations Research 48 (4), p. 2066–2093. Cited by: §1, §1, §3.1, §3. [24] A. Kara and S. Yuksel (2022) Near optimality of finite memory feedback policies in partially observed Markov decision processes. Journal of Machine Learning Research 23 (11), p. 1–46. Cited by: §3.1. [25] M. Kearns and S. Singh (2002) Near-optimal reinforcement learning in polynomial time. Machine learning 49 (2), p. 209–232. Cited by: §4.2. [26] A. Krishnamurthy, A. Agarwal, and J. Langford (2016) PAC reinforcement learning with rich observations. Advances in Neural Information Processing Systems. Cited by: §1. [27] M. Lauri, D. Hsu, and J. Pajarinen (2022) Partially observable Markov decision processes in robotics: a survey. IEEE Transactions on Robotics 39 (1), p. 21–40. Cited by: §1. [28] S. Leonardos, W. Overman, I. Panageas, and G. Piliouras (2022) Global convergence of multi-agent policy gradient in Markov potential games. In International Conference on Learning Representations, Cited by: §1, §2, §5. [29] A. Lerer, H. Hu, J. Foerster, and N. Brown (2020) Improving policies via search in cooperative partially observable games. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34, p. 7187–7194. Cited by: §1. [30] Q. Liu, A. Chung, C. Szepesvári, and C. Jin (2022) When is partially observable reinforcement learning not scary?. In Conference on Learning Theory, p. 5175–5220. Cited by: §1, §1, §1. [31] Q. Liu, C. Szepesvári, and C. Jin (2022) Sample-efficient reinforcement learning of partially observable Markov games. Advances in Neural Information Processing Systems. Cited by: §1, §5. [32] X. Liu and K. Zhang (2023) Partially observable multi-agent rl with (quasi-) efficiency: the blessing of information sharing. In International Conference on Machine Learning, p. 22370–22419. Cited by: §1, §5. [33] R. Lu, Y. Zhu, and D. Zhao (2025) Divergence-regularized discounted aggregation: equilibrium finding in multiplayer partially observable stochastic games. In The Thirteenth International Conference on Learning Representations, Cited by: §1. [34] S. V. Macua, J. Zazo, and S. Zazo (2018) Learning parametric closed-loop policies for Markov potential games. In International Conference on Learning Representations, Cited by: §1. [35] C. Maheshwari, M. Wu, D. Pai, and S. Sastry (2025) Independent and decentralized learning in Markov potential games. IEEE Transactions on Automatic Control. Cited by: §1. [36] W. Mao, K. Zhang, Z. Yang, and T. Başar (2023) Decentralized learning of finite-memory policies in Dec-POMDPs. IFAC-PapersOnLine 56 (2), p. 2601–2607. Cited by: §1. [37] D. Narasimha, K. Lee, D. Kalathil, and S. Shakkottai (2022) Multi-agent learning via Markov potential games in marketplaces for distributed energy resources. In 2022 IEEE 61st Conference on Decision and Control (CDC), p. 6350–6357. Cited by: §2. [38] S. Omidshafiei, J. Pazis, C. Amato, J. P. How, and J. Vian (2017) Deep decentralized multi-task multi-agent reinforcement learning under partial observability. In International Conference on Machine Learning, p. 2681–2690. Cited by: §1. [39] C. H. Papadimitriou and J. N. Tsitsiklis (1987) The complexity of Markov decision processes. Mathematics of Operations Research 12 (3), p. 441–450. Cited by: §1. [40] M. L. Puterman (1994) Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, Inc.. Cited by: §1. [41] Z. Song, S. Mei, and Y. Bai (2022) When can we learn general-sum Markov games with a large number of players sample-efficiently?. In International Conference on Learning Representations, Cited by: §1. [42] R. van Handel (2008) Hidden Markov models. Unpublished lecture notes. Cited by: §3.1. [43] Y. Xiao, W. Tan, J. Hoffman, T. Xia, and C. Amato (2025) Asynchronous multi-agent deep reinforcement learning under partial observability. The International Journal of Robotics Research 44 (8), p. 1257–1286. Cited by: §B.1, §1, §1. [44] J. Yao, Z. Zhang, L. Xia, J. Yang, and Q. Zhao (2020) Solving imperfect information Poker games using Monte Carlo search and POMDP models. In 2020 IEEE 9th Data Driven Control and Learning Systems Conference (DDCLS), p. 1060–1065. Cited by: §1. [45] K. Zhang, Z. Yang, and T. Başar (2021) Multi-agent reinforcement learning: a selective overview of theories and algorithms. Handbook of reinforcement learning and control, p. 321–384. Cited by: §4. [46] R. Zhang, J. Mei, B. Dai, D. Schuurmans, and N. Li (2022) On the global convergence rates of decentralized softmax gradient play in Markov potential games. Advances in Neural Information Processing Systems. Cited by: §2. [47] R. Zhang, Y. Zhang, R. Konda, B. Ferguson, J. Marden, and N. Li (2023) Markov games with decoupled dynamics: price of anarchy and sample complexity. In 2023 62nd IEEE Conference on Decision and Control (CDC), p. 8100–8107. Cited by: 1st item, 1st item, 1st item, 2nd item, §E.1, item 3, §1, §2, §4, §4.1, §5, §5. [48] M. Zinkevich, A. Greenwald, and M. Littman (2005) Cyclic equilibria in Markov games. Advances in Neural Information Processing Systems. Cited by: §4.1. Supplementary Material Table of Contents Appendix A Overview of Notation Table 1 gives an overview of the notation used throughout this paper. All notations are introduced before their first use as well. Table 1: Overview of notation Symbol Description POMG =(,H,,,,r,ℙ,,μ)P=(N,H,S,A,O,r,P,O,μ) the partially observable Markov game =[N]N=[N] set of N players H planning horizon =∏iS= _iS_i joint state space =∏iA= _iA_i joint action space; A≔maxi|i|A _i|A_i| =∏iO= _iO_i joint observation space; O≔maxi|i|O _i|O_i| ri,h:×→[0,1]r_i,h:S×A→[0,1] reward function for player i at step h ℙi,h(⋅∣si,ai)P_i,h(· s_i,a_i) transition kernel for player i at step h i,h(⋅∣si)O_i,h(· s_i) observation kernel for player i at step h μ=∏iμiμ= _i _i initial state distribution over S Histories and Policies ℋih=(i×i)hH_i^h=(A_i×O_i)^h set of h-step local histories for player i ℋi≤hH_i^≤ h ⋃h′=0hℋih′ _h =0^hH_i^h τi=(ai,h′,oi,h′)h′=1h _i=(a_i,h ,o_i,h )_h =1^h local history of length |τi|=h| _i|=h; ∘ denotes concatenation τi,k:l _i,k:l sub-history from step k to step l (inclusive) Πim _i^m m-step finite-window policies for player i Vi(π)V_i(π) value of player i under joint policy π in P Superstate Markov Game mG^m wi∈ℋi≤mw_i _i^≤ m local superstate (truncated history window) of player i bi,hm(si∣wi)b_i,h^m(s_i w_i) player i’s belief over iS_i induced by window wiw_i at step h bi,h(si∣τi)b_i,h(s_i _i) player i’s belief over iS_i given full history τi _i ℙhm(w′∣w,a)P_h^m(w w,a) superstate transition kernel of mG^m ri,hm(w,a)r_i,h^m(w,a) reward of player i in mG^m Vim(π)V_i^m(π) value of player i under π in mG^m Q¯i,hm,π(wi,ai) Q_i,h^m,π(w_i,a_i) marginalized Q-function in mG^m under policy π di,hm,π(wi)d_i,h^m,π(w_i) superstate visitation distribution at step h under π Potential Structure λi,hπi(si,ai) _i,h _i(s_i,a_i) state-action occupancy measure of player i Φ:Π→ℝ : potential function of the underlying Markov game ϕh:×→ℝ _h:S×A stage-wise potential function at step h Ψ:Πm→ℝ : ^m near-potential function for mG^m (see Proposition 3.2) Assumptions and Key Parameters ρ>0ρ>0 filter stability contraction factor (see Assumption 2) β>0β>0 minimum observation probability (see Assumption 3) α>0α>0 minimum state visitation probability (see Assumption 4) ϵρm≔4H2(1−ρ)m _ρ^m 4H^2(1-ρ)^m finite-window approximation error (see Lemma 3.2) Algorithm 1 T number of episodes per iteration K number of iterations η(k)η^(k) stepsize at iteration k ℙ^i,hm,r^i,hm,π−i P_i,h^m,\ r_i,h^m, _-i empirical estimates of superstate transitions and rewards Q^i,h(k) Q_i,h^(k) estimated Q-function at iteration k Appendix B Discussion of decoupled dynamics assumption B.1 Illustrative examples We provide several representative application domains in which the assumption of decoupled transition dynamics arises naturally, while interactions are captured through the reward structure. Wireless networks. Consider a wireless communication network in which N users aim to transmit packets over a shared channel. Each user maintains a local queue of packets and, at each time step, selects a transmission power level. The local state corresponds to the queue length, which evolves based on the transmission success and exogenous packet arrivals. Crucially, under standard modeling assumptions, the queue dynamics depend only on the user’s own state and action, and are thus conditionally independent across users. In contrast, rewards depend on the joint action profile: simultaneous high-power transmissions lead to increased interference and congestion, reducing transmission success probabilities. This induces a coupling in the reward function, often leading to a (statewise) congestion (and thus potential) structure. Such models have been studied in the networking literature (see, e.g., [3, 2]). In practice, the queue length may only be partially observed due to delays, noise, or aggregation effects, leading naturally to a partially observable setting. Distributed energy markets. In distributed energy systems [16], multiple prosumers (e.g., households equipped with photovoltaic panels and storage) interact through a shared energy market. Each prosumer’s local state is given by its battery level, which evolves according to locally generated and consumed energy, as well as charging and discharging decisions. Assuming participants are geographically separated with independent local conditions, these state dynamics may be modelled as decoupled across agents. However, the reward, typically representing negative energy cost, depends on the aggregate supply and demand in the market, and hence on the joint actions of all agents. This induces strategic coupling through prices or clearing mechanisms, while maintaining independent state evolution. Multi-robot systems. Decoupled transition dynamics also naturally arise in multi-robot systems and autonomous driving. Each agent (robot or vehicle) evolves according to its own local dynamics, which depend primarily on its state and control inputs. Coupling between agents typically enters through the reward function, which encodes coordination objectives such as collision avoidance, or task allocation. In many practical settings, agents have only partial observations of the local state due to limited sensing. For instance, [43] implements reinforcement learning methods under partial observability in real-world multi-robot tasks. Here, agents learn localized policies based on their individual state observations. Appendix C Proofs for Section 3 In this section, we provide the proofs for our structural results on POMGs presented in Section 3. C.1 Finite window approximation results In this subsection, we establish several approximation results under filter stability that lead us towards proving Proposition 3.2. First, we show that beliefs formed from joint histories corresponding to the same superstate must be close to each other in terms of total variation distance. Lemma 1. For m,h,h′∈ℕm,h,h with h,h′≥mh,h ≥ m, let τ∈ℋh,τ′∈ℋh′τ ^h,τ ^h such that τh−m+1:h=τh−m+1:h′ _h-m+1:h=τ _h-m+1:h. Then, under Assumption 2, we have ∥bh(⋅∣τ)−bh′(⋅∣τ′)∥TV≤(1−ρ)m. b_h(· τ)-b_h (· τ ) _TV≤(1-ρ)^m. Proof. Since the POMG can be viewed as an POMDP with action space A and observation space O, the result follows equivalently to the respective single-agent result, see Lemma 1 in [4]. At each of the m steps, beliefs are contracted by a (1−ρ)(1-ρ)-factor, and hence the desired bound follows. ∎ Next, we bound the error in terms of superstate rewards and transition kernels resulting from finite-window approximation. Recall that ∘ denotes concatenation of histories. Lemma 2. Let h≥mh≥ m and w∈ℋmw ^m, τ∈ℋhτ ^h with w=τh−m+1:hw= _h-m+1:h. Then, for any i∈i , h∈[H]h∈[H], and a∈a , |ri,hm(w,a)−ri,hH(τ,a)| |r^m_i,h(w,a)-r^H_i,h(τ,a) | ≤2(1−ρ)m, ≤ 2(1-ρ)^m, ∑o∈|ℙhm(w2:m∘(a,o)∣w,a)−ℙhH(τh−m+1:h∘(a,o)∣τ,a)| _o |P^m_h(w_2:m (a,o) w,a)-P^H_h( _h-m+1:h (a,o) τ,a) | ≤2(1−ρ)m. ≤ 2(1-ρ)^m. Proof. For the first bound, note that |ri,hm(w,a)−ri,hH(τ,a)|≤∑s∈ri,h(s,a)|bhm(s∣w)−bh(s∣τ)|≤2(1−ρ)m |r^m_i,h(w,a)-r^H_i,h(τ,a) |≤ _s r_i,h(s,a) |b^m_h(s w)-b_h(s τ) |≤ 2(1-ρ)^m where in the last step we have used Lemma 1 and the fact that rewards are bounded by 11. For the second bound, denoting wo′≔w2:m∘(a,o)w _o w_2:m (a,o) and τo′≔τ∘(a,o)τ _o τ (a,o), we have ∑o∈|ℙhm(wo′∣w,a)−ℙhH(τo′∣τ,a)| _o |P^m_h(w _o w,a)-P^H_h(τ _o τ,a) | =∑o∈∑s,s′∈h+1(o∣s′)ℙh(s′∣s,a)|bhm(s∣w)−bh(s∣τ)| = _o _s,s O_h+1(o s )P_h(s s,a) |b^m_h(s w)-b_h(s τ) | ≤∑s∈|bhm(s∣w)−bh(s∣τ)|∑o∈∑s′∈h+1(o∣s′)ℙh(s′∣s,a) ≤ _s |b^m_h(s w)-b_h(s τ) | _o _s O_h+1(o s )P_h(s s,a) ≤2(1−ρ)m. ≤ 2(1-ρ)^m. ∎ Using the above bound, we obtain the following approximation result for value functions and best responses, restated here for convenience. * Proof. The proof of the first bound proceeds by showing a stronger inequality by backward induction on h. For this, we define for any w∈ℋ≤mw ^≤ m and τ∈ℋh−1τ ^h-1 the step h value functions Vi,h(π;τ) V_i,h(π;τ) ≔π,s1∼μ[∑h′=hHri,h′m(sh′,ah′)∣(a1,o1,…,ah−1,oh−1)=τ] _π,\,s_1 μ [ _h =h^Hr^m_i,h (s_h ,a_h ) (a_1,o_1,…,a_h-1,o_h-1)=τ ] Vi,hm(π;w) V^m_i,h(π;w) ≔π,s1∼μ[∑h′=hHri,h′m(wh′,ah′)∣wh−1=w]. _π,\,s_1 μ [ _h =h^Hr^m_i,h (w_h ,a_h ) w_h-1=w ]. The inequality we aim to show for all h∈[H]h∈[H] is |Vi,hm(π;w)−Vi,h(π;τ)|≤4(1−ρ)mH(H+1−h). |V^m_i,h(π;w)-V_i,h(π;τ) |≤ 4(1-ρ)^mH(H+1-h). (5) For H+1H+1, (5) trivially holds. Suppose (5) holds for some h∈[H]h∈[H]. The Bellman expectation equations are given by Vi,hm(π;w) V^m_i,h(π;w) =∑a∈πh(a∣w)[ri,hm(w,a)+∑o∈ℙhm(w2:m∘(a,o)∣w,a)Vi,h+1m(π;w2:m∘(a,o))], = _a _h(a w) [r^m_i,h(w,a)+ _o P^m_h(w_2:m (a,o) w,a)V^m_i,h+1(π;w_2:m (a,o)) ], Vi,h(π′;τ) V_i,h(π ;τ) =∑a∈πh′(a∣τ)[ri,hH(τ,a)+∑o∈ℙhH(τ∘(a,o)∣τ,a)Vi,h+1(π′;τ∘(a,o))]. = _a π _h(a τ) [r^H_i,h(τ,a)+ _o P^H_h(τ (a,o) τ,a)V_i,h+1(π ;τ (a,o)) ]. Hence, we can write the difference as |Vi,hm(π;w)−Vi,h(π′;τ)| |V^m_i,h(π;w)-V_i,h(π ;τ) | ≤∑a∈πh(a∣w)[|ri,hm(w,a)−ri,hH(τ,a)| ≤ _a _h(a w) [ |r^m_i,h(w,a)-r^H_i,h(τ,a) | +∑o∈ℙhm(w2:m∘(a,o)∣w,a)[Vi,h+1m(π;w2:m∘(a,o))−Vi,h+1(π′;τ∘(a,o))] + _o P^m_h(w_2:m (a,o) w,a) [V^m_i,h+1(π;w_2:m (a,o))-V_i,h+1(π ;τ (a,o)) ] +∑o∈[ℙhm(w2:m∘(a,o)∣w,a)−ℙhH(τ∘(a,o)∣τ,a)]Vi,h+1(π′;τ∘(a,o))] + _o [P^m_h(w_2:m (a,o) w,a)-P^H_h(τ (a,o) τ,a) ]V_i,h+1(π ;τ (a,o)) ] ≤(a)∑a∈πh(a∣w)[2(1−ρ)m+maxo∈|Vi,h+1m(π;w2:m∘(a,o))−Vi,h+1(π′;τ∘(a,o))|+2(1−ρ)mH] (a)≤ _a _h(a w) [2(1-ρ)^m+ _o |V^m_i,h+1(π;w_2:m (a,o))-V_i,h+1(π ;τ (a,o)) |+2(1-ρ)^mH ] ≤4H(1−ρ)m+maxa∈,o∈|Vi,h+1m(π;w2:m∘(a,o))−Vi,h+1(π′;τ∘(a,o))| ≤ 4H(1-ρ)^m+ _a ,o |V^m_i,h+1(π;w_2:m (a,o))-V_i,h+1(π ;τ (a,o)) | ≤(b)4H(1−ρ)m+4(1−ρ)mH(H−h) (b)≤4H(1-ρ)^m+4(1-ρ)^mH(H-h) ≤4(1−ρ)mH(H+1−h) ≤ 4(1-ρ)^mH(H+1-h) where in (a) we use Lemma 2, and in (b) we apply the induction hypothesis. To show the second bound, define the best response functions for any i∈i , h∈[H]h∈[H], w∈ℋ≤mw ^≤ m, and τ∈ℋh−1τ ^h-1, Vi,hm,†(π−i;w) V_i,h^m, ( _-i;w) ≔maxπ^i∈ΠimVi,hm(π^i,π−i;w), _ π_i∈ ^m_iV^m_i,h( π_i, _-i;w), Vi,h†(π−i′;τ) V _i,h(π _-i;τ) ≔maxπ^i′∈ΠiHVi,h(π^i′,π−i;τ). _ π_i ∈ ^H_iV_i,h( π_i , _-i;τ). By Bellman optimality, we have Vi,hm,†(π−i;w)=maxai∈i∑a−i∈−iπ−i(a−i∣w−i)[ri,hm(w,ai,a−i) V_i,h^m, ( _-i;w)= _a_i _i _a_-i _-i _-i(a_-i w_-i) [r^m_i,h(w,a_i,a_-i) +∑o∈ℙhm(w2:m∘(ai,a−i,o)∣w,ai,a−i)Vi,h+1m,†(π−i;w2:m∘(ai,a−i,o))], + _o P^m_h(w_2:m (a_i,a_-i,o) w,a_i,a_-i)V_i,h+1^m, ( _-i;w_2:m (a_i,a_-i,o)) ], Vi,h†(π−i′;τ)=maxai∈i∑a−i∈−iπ−i′(a−i∣τ−i)[ri,hH(τ,ai,a−i) V_i,h (π _-i;τ)= _a_i _i _a_-i _-iπ _-i(a_-i _-i) [r^H_i,h(τ,a_i,a_-i) +∑o∈ℙhH(τ∘(ai,a−i,o)∣τ,ai,a−i)Vi,h+1†(π−i′;τ∘(ai,a−i,o))]. + _o P^H_h(τ (a_i,a_-i,o) τ,a_i,a_-i)V_i,h+1 (π _-i;τ (a_i,a_-i,o)) ]. Therefore, using the same steps as above, we can decompose the difference as above and apply Lemma 2 to obtain |Vi,hm,†(π−i;w)−Vi,h†(π−i′;τ)| |V_i,h^m, ( _-i;w)-V_i,h (π _-i;τ) | ≤maxai∈i∑a−i∈−iπ−i(a−i∣w−i)[4H(1−ρ)m ≤ _a_i _i _a_-i _-i _-i(a_-i w_-i) [4H(1-ρ)^m +maxo∈|Vi,h+1m,†(π−i;w2:m∘(ai,a−i,o))−Vi,h+1†(π−i′;τ∘(ai,a−i,o))|] + _o |V_i,h+1^m, ( _-i;w_2:m (a_i,a_-i,o))-V_i,h+1 (π _-i;τ (a_i,a_-i,o)) | ] ≤4H(1−ρ)m+maxa∈,o∈|Vi,h+1m,†(π−i;w2:m∘(ai,a−i,o))−Vi,h+1†(π−i′;τ∘(ai,a−i,o))|. ≤ 4H(1-ρ)^m+ _a ,o |V_i,h+1^m, ( _-i;w_2:m (a_i,a_-i,o))-V_i,h+1 (π _-i;τ (a_i,a_-i,o)) |. Then, by an induction argument over h similar to above, we can show that for any h∈[H]h∈[H], |Vi,hm,†(π−i;w)−Vi,h†(π−i′;τ)|≤4(1−ρ)mH(H+1−h), |V_i,h^m, ( _-i;w)-V_i,h (π _-i;τ) |≤ 4(1-ρ)^mH(H+1-h), which implies the desired bound. ∎ C.2 Nash equilibrium approximation As a direct application of Lemma 3.2, we obtain the following approximation guarantee for Nash equilibria for m-step history-dependent policies. * Proof. With best response function defined as in the proof of Lemma 3.2, we have Vi†(π−i)−Vi(π) V _i( _-i)-V_i(π) ≤[Vi†(π−i)−Vim,†(π−i)]+[Vim,†(π−i)−Vim(π)]+[Vim(π)−Vi(π)] ≤ [V _i( _-i)-V_i^m, ( _-i) ]+ [V_i^m, ( _-i)-V_i^m(π) ]+ [V_i^m(π)-V_i(π) ] ≤(a)|Vi†(π−i)−Vim,†(π−i)|+ϵ+|Vim(π)−Vi(π)| (a)≤ |V _i( _-i)-V_i^m, ( _-i) |+ε+ |V_i^m(π)-V_i(π) | ≤(b)ϵ+2ϵρm (b)≤ε+2ε^m_ρ where (a) is due to π being an ϵε-approximate Nash equilibrium, and (b) follows from the two respective bounds in Lemma 3.2. ∎ C.3 Near-potential structure Having shown our Nash equilibrium approximation guarantee, we next establish near-potential structure of the superstate Markov game mG^m. * Proof. The proof is divided into two parts. First, using decoupledness of transitions, we show that under Assumption 1 on the underlying latent state Markov game, there exists an exact potential function for the POMG. As a second step, based on this, we then prove the (2ϵρm)(2 _ρ^m)-approximate potential structure for the superstate Markov game. • POMG is potential: For any πi∈Πim _i∈ ^m_i and h∈[H]h∈[H], let λi,hπi∈Δ(i×i)λ _i_i,h∈ (S_i×A_i) denote the induced playerwise state-action visitation probability at step h, defined as λi,hπi(si,ai)≔Pπi(si,h=si,ai,h=ai) _i,h _i(s_i,a_i) P_ _i (s_i,h=s_i,a_i,h=a_i ) where PπiP_ _i refers to the distribution over player i’s (unobserved) state trajectories when following πi _i in the underlying POMG. By Assumption 1, the underlying Markov game is a potential game. Due to decoupledness of transitions, it is known that the Markov game is statewise potential [47], i.e., there exist ϕh:×→ℝ _h:S×A for each h∈[H]h∈[H] such that for all i∈i , h∈[H]h∈[H], s∈s , si′∈is_i _i, a∈a , and ai′∈ia_i _i, we have ri,h(si,h′,s−i,h,ai,h′,a−i,h)−ri,h(si,h,s−i,h,ai,h,a−i,h) r_i,h(s_i,h ,s_-i,h,a_i,h ,a_-i,h)-r_i,h(s_i,h,s_-i,h,a_i,h,a_-i,h) =ϕh(si,h′,s−i,h,ai,h′,a−i,h)−ϕh(si,h,s−i,h,ai,h,a−i,h). = _h(s_i,h ,s_-i,h,a_i,h ,a_-i,h)- _h(s_i,h,s_-i,h,a_i,h,a_-i,h). Define the function Φ:Πm→ℝ : ^m as Φ(π)≔π[∑h=1Hϕh(sh,ah)], (π) _π [ _h=1^H _h(s_h,a_h) ], and further define for any π−i∈Π−i _-i∈ _-i, ri,hπ−i(si,ai) r_i,h _-i(s_i,a_i) ≔∑s−i,a−iri,h(si,s−i,ai,a−i)∏j∈∖iλj,hπj(sj,aj), _s_-i,a_-ir_i,h(s_i,s_-i,a_i,a_-i) _j \i \ _j,h _j(s_j,a_j), ϕhπ−i(si,ai) _h _-i(s_i,a_i) ≔∑s−i,a−iϕh(si,s−i,ai,a−i)∏j∈∖iλj,hπj(sj,aj). _s_-i,a_-i _h(s_i,s_-i,a_i,a_-i) _j \i \ _j,h _j(s_j,a_j). Then, we can write Vi(π)−Vi(πi′,π−i) V_i(π)-V_i( _i , _-i) =(a)∑h∈[H]ri,h⊤(×j∈λj,hπj)−∑h∈[H]ri,h⊤(λi,hπi′×(×j∈∖iλj,hπj)) (a)= _h∈[H]r _i,h ( _j _j,h _j )- _h∈[H]r _i,h ( _i,h _i × ( _j \i \ _j,h _j ) ) =∑h∈[H](ri,hπ−i)⊤λi,hπi−(ri,hπ−i)⊤λi,hπi′ = _h∈[H] (r_i,h _-i ) _i,h _i- (r_i,h _-i ) _i,h _i =(b)12∑h∈[H]∑si,si′,ai,ai′(λi,hπi(si,ai)λi,hπi′(si′,ai′)−λi,hπi(si′,ai′)λi,hπi′(si,ai))(ri,hπ−i(si,ai)−ri,hπ−i(si′,ai′)) (b)= 12 _h∈[H] _s_i,s_i ,a_i,a_i ( _i,h _i(s_i,a_i) _i,h _i (s_i ,a_i )- _i,h _i(s _i,a _i) _i,h _i (s_i,a_i) ) (r _-i_i,h(s_i,a_i)-r _-i_i,h(s _i,a _i) ) =12∑h∈[H]∑si,si′,ai,ai′(λi,hπi(si,ai)λi,hπi′(si′,ai′)−λi,hπi(si′,ai′)λi,hπi′(si,ai))(ϕhπ−i(si,ai)−ϕhπ−i(si′,ai′)) = 12 _h∈[H] _s_i,s_i ,a_i,a_i ( _i,h _i(s_i,a_i) _i,h _i (s_i ,a_i )- _i,h _i(s _i,a _i) _i,h _i (s_i,a_i) ) ( _h _-i(s_i,a_i)- _h _-i(s _i,a _i) ) =∑h∈[H](ϕhπ−i)⊤λi,hπi−(ϕhπ−i)⊤λi,hπi′ \,= _h∈[H] ( _h _-i ) _i,h _i- ( _h _-i ) _i,h _i =∑h∈[H]ϕh⊤(×j∈λj,hπj)−ϕh⊤(λi,hπi′×(×j∈∖iλj,hπj)) \,= _h∈[H] _h ( _j _j,h _j )- _h ( _i,h _i × ( _j \i \ _j,h _j ) ) =Φ(π)−Φ(πi′,π−i) = (π)- ( _i , _-i) where (a) uses linearity of the value functions in the state-action occupancy, and (b) uses the identity proven in Lemma 3. This proves that the belief state Markov game is a Markov potential game with potential function Φ . • Superstate Markov game is near-potential: For any π∈Πmπ∈ ^m, i∈i , and πi′∈Πim _i ∈ ^m_i, (Vim(π)−Vim(πi′,π−i)) (V_i^m(π)-V_i^m( _i , _-i) ) −(Φ(π)−Φ(πi′,π−i)) - ( (π)- ( _i , _-i) ) =(Vim(π)−Vi(π))+(Vi(πi′,π−i)−Vim(πi′,π−i))⏟(a) = (V_i^m(π)-V_i(π) )+ (V_i( _i , _-i)-V_i^m( _i , _-i) )_(a) +(Vi(π)−Vi(πi′,π−i))−(Φ(π)−Φ(πi′,π−i))⏟(b). + (V_i(π)-V_i( _i , _-i) )- ( (π)- ( _i , _-i) )_(b). Note that since Φ is a potential function of the belief state Markov game, we have (b)=0(b)=0. Moreover, using Lemma 3.2, we bound |(a)|≤2ϵρm |(a) |≤ 2ε^m_ρ, which concludes the proof. ∎ C.4 Auxiliary lemma In the above proof of Proposition 3.2, we invoked the following algebraic identity, which expresses the difference of two linear forms over distributions as a symmetric pairwise sum. Here we provide its proof. Lemma 3. For k∈ℕk and ℐ=1,…,kI=\1,…,k\, let p,q∈Δ(ℐ)p,q∈ (I), and let x:ℐ→ℝx:I be arbitrary. Then ∑i∈ℐp(i)x(i)−∑i∈ℐq(i)x(i)=12∑i,j∈ℐ(p(i)q(j)−p(j)q(i))(x(i)−x(j)). _i p(i)x(i)- _i q(i)x(i)= 12 _i,j (p(i)q(j)-p(j)q(i) )\, (x(i)-x(j) ). Proof. Expanding the right-hand side yields 12∑i,jp(i)q(j)x(i)−12∑i,jp(i)q(j)x(j)−12∑i,jp(j)q(i)x(i)+12∑i,jp(j)q(i)x(j). 12 _i,jp(i)q(j)x(i)- 12 _i,jp(i)q(j)x(j)- 12 _i,jp(j)q(i)x(i)+ 12 _i,jp(j)q(i)x(j). We first group terms according to whether they multiply x(i)x(i) or x(j)x(j): ∑i,j12(p(i)q(j)−p(j)q(i))x(i)+∑i,j12(p(j)q(i)−p(i)q(j))x(j). _i,j 12 (p(i)q(j)-p(j)q(i) )x(i)+ _i,j 12 (p(j)q(i)-p(i)q(j) )x(j). For the first sum, fixing i and summing over j yields ∑j12(p(i)q(j)−p(j)q(i))=12(p(i)∑jq(j)−q(i)∑jp(j))=12(p(i)−q(i)), _j 12 (p(i)q(j)-p(j)q(i) )= 12 (p(i) _jq(j)-q(i) _jp(j) )= 12 (p(i)-q(i) ), where we used ∑jp(j)=∑jq(j)=1 _jp(j)= _jq(j)=1. Hence ∑i,j12(p(i)q(j)−p(j)q(i))x(i)=∑i12(p(i)−q(i))x(i). _i,j 12 (p(i)q(j)-p(j)q(i) )x(i)= _i 12 (p(i)-q(i) )x(i). Applying the same argument to the second sum (with indices relabeled) gives ∑i,j12(p(j)q(i)−p(i)q(j))x(j)=∑i12(q(i)−p(i))x(i). _i,j 12 (p(j)q(i)-p(i)q(j) )x(j)= _i 12 (q(i)-p(i) )x(i). Combining the two expressions and canceling terms yields ∑i(p(i)−q(i))x(i)=∑ip(i)x(i)−∑iq(i)x(i), _i(p(i)-q(i))x(i)= _ip(i)x(i)- _iq(i)x(i), which completes the proof. ∎ Appendix D Algorithm details Below, we provide further details omitted in the main part by formally specifying how to compute empirical frequencies for estimating superstate transition probabilities and rewards based on the sampled action-observation sequences. Denote by τi(t)=(ai,h(t),oi,h(t),ri,h(t))h=1Hτ^(t)_i=(a^(t)_i,h,o^(t)_i,h,r_i,h^(t))_h=1^H for t∈[T]t∈[T] the t-th sequence sampled at some iteration k∈[K]k∈[K] of Algorithm 1 when players follow the joint policy π(k)∈Πmπ^(k)∈ ^m. Transition probabilities. At each player i∈i , at step h∈[H]h∈[H], and for all wi,wi′∈ℋi≤mw_i,w_i _i^≤ m and ai∈ia_i _i, take the empirical average of transitions from wiw_i to wi′w_i , that is, ℙ^i,hm(wi′∣wi,ai)≔∑t=1Tτi,h−|wi′|+2:h+1(t)=wi′∧τi,h−|wi|+1:h(t)=wi∧ai,h(t)=ai∑t=1Tτi,h−|wi|+1:h(t)=wi∧ai,h(t)=ai, if ∑t=1Tτh−|wi|+1:h(t)=wi∧ai,h(t)=ai≥1 and |wi′|=min(m,|wi|+1),0,otherwise. P_i,h^m(w_i w_i,a_i) cases _t=1^T1\τ^(t)_i,h-|w_i |+2\,:\,h+1=w_i \; \;τ^(t)_i,h-|w_i|+1\,:\,h=w_i\; \;a^(t)_i,h=a_i\ _t=1^T1\τ^(t)_i,h-|w_i|+1\,:\,h=w_i a_i,h^(t)=a_i\,\\[14.0pt] if _t=1^T1\τ^(t)_h-|w_i|+1\,:\,h=w_i a_i,h^(t)=a_i\≥ 1 and |w_i |= (m,|w_i|+1),\\[16.0pt] 0,\;otherwise. cases (6) Rewards. Similarly, at each player i∈i , at step h∈[H]h∈[H], and for all wi∈ℋi≤mw_i _i^≤ m and ai∈ia_i _i, set r^i,hm,π−i(k)(wi,ai)≔∑t=1Tri,h(t)⋅τi,h−|wi|+1:h(t)=wi∧ai,h(t)=ai∑t=1Tτh−|wi|+1:h(t)=wi∧ai,h(t)=ai, if ∑t=1Tτi,h−|wi|+1:h(t)=wi∧ai,h(t)=ai≥1,0,otherwise. r_i,h^m,π^(k)_-i(w_i,a_i) cases _t=1^Tr_i,h^(t)·1\τ^(t)_i,h-|w_i|+1\,:\,h=w_i\; \;a^(t)_i,h=a_i\ _t=1^T1\τ^(t)_h-|w_i|+1\,:\,h=w_i\; \;a^(t)_i,h=a_i\,\\[14.0pt] if _t=1^T1\τ^(t)_i,h-|w_i|+1\,:\,h=w_i\; \;a^(t)_i,h=a_i\≥ 1,\\[12.0pt] 0,\;otherwise. cases (7) Appendix E Proofs for Section 5 In this section, we provide the proof our main result, Theorem 1, on the convergence of Algorithm 1 to an ϵε-approximate Nash equilibrium. E.1 Model estimation guarantees We begin by deriving confidence bounds for the transition and reward estimates computed at each iteration of Algorithm 1. Note that these differ from the Markov game case, since we additionally need to account for the bias introduced by the superstate Markov game approximation. * Proof. We divide the proof into two parts for proving each of the two bounds. • Bound for estimation of transitions: For some πi∈ΠiH _i∈ _i^H, let ℙ~i,hπi(⋅∣wi,ai)∈Δ(ℋi≤m) P _i_i,h(· w_i,a_i)∈ (H_i^≤ m) denote the distribution over m-step windows observed at step h marginalized over the full history, i.e., ℙ~i,hπi(wi′∣wi,ai)≔∑τi=(ai,1,oi,1,…,ai,h+1,oi,h+1)∈ℋih+1Pπi(i,h=τi) P _i_i,h(w_i w_i,a_i) _ _i=(a_i,1,o_i,1,…,a_i,h+1,o_i,h+1) _i^h+1P_ _i (T_i,h= _i ) ⋅τi,h−m+2:h+1=wi′∧τi,h−m+1:h=wi∧ai,h+1=ai 110.00017pt·1 \ _i,h-m+2:h+1=w_i _i,h-m+1:h=w_i a_i,h+1=a_i \ where Pπi(i,h=τi)P_ _i (T_i,h= _i ) is the probability that the random history i,hT_i,h, induced by the POMG dynamics and policy πi _i, is equal to τi _i at step h for player i. Note that [ℙ^i,hm(wi′∣wi,ai)]=ℙ~i,hπiϵ(wi′∣wi,ai), [ P_i,h^m(w_i w_i,a_i) ]= P^π^ε_i_i,h(w_i w_i,a_i), where πiϵπ^ε_i is the ϵε-greedy policy from which we sample in Line 4 of Algorithm 1. Since we sample T independent trajectories, ℙ^i,hm(wi′∣wi,ai) P_i,h^m(w_i w_i,a_i) is a sum of T independent estimators of ℙ^i,hm(wi′∣wi,ai) P_i,h^m(w_i w_i,a_i). Therefore, as shown by Lemma 4 in [47], for any 0<ϵ≤10<ε≤ 1, we have P(|ℙ~i,hπiϵ(wi′∣wi,ai)−ℙ^i,hm(wi′∣wi,ai)|≥ϵ)≤4exp(−ϵ2m+2β2mT32Ai2m). P ( | P^π^ε_i_i,h(w_i w_i,a_i)- P_i,h^m(w_i w_i,a_i) |≥ε )≤ 4 (- ε^2m+2β^2mT32A_i^2m ). In [47], to get above bound, a lower bound of c>0c>0 on state visitation probabilities is assumed. In our case, due to Assumption 3 and the fact that we sample trajectories in a ϵε-greedy manner, at any step h∈[H]h∈[H], any m-step window is visited with probability at least ((βϵ)/Ai)m ((βε)/A_i )^m, which then yields the above bound. Moreover, by Lemma 2, we have the deterministic bound |ℙ~i,hπiϵ(wi′∣wi,ai)−ℙi,hm(wi′∣wi,ai)|≤2(1−ρ)m | P _i^ε_i,h(w_i w_i,a_i)-P^m_i,h(w_i w_i,a_i) |≤ 2(1-ρ)^m which together with the above concludes the proof of the first bound. • Bound for reward estimation: Similar to above, we define r~i,hπ(wi,ai)≔∑τi=(ai,1,oi,1,…,ai,h,oi,h)∈ℋihPπ(i,h=τi) r_i,h^π(w_i,a_i) _ _i=(a_i,1,o_i,1,…,a_i,h,o_i,h) ^h_iP_π (T_i,h= _i ) ⋅τi,h−m+1:h=wi∧ai,h+1=airi,hH,π−i(τi,ai), ·1 \ _i,h-m+1:h=w_i a_i,h+1=a_i \\,r_i,h^H, _-i( _i,a_i), such that we have [r^i,hm,π−i(wi,ai)]=r~i,hπϵ(wi,ai), [ r_i,h^m, _-i(w_i,a_i) ]= r_i,h^π^ε(w_i,a_i), Similar as for transition probabilities, we obtain from Lemma 4 of [47] the bound P(|r~i,hπϵ(wi,ai)−r^i,hm,π−i(wi,ai)|≥ϵ)≤4exp(−ϵ2m+2β2mT32Ai2m). P ( | r_i,h^π^ε(w_i,a_i)- r_i,h^m, _-i(w_i,a_i) |≥ε )≤ 4 (- ε^2m+2β^2mT32A_i^2m ). Moreover, we decompose the bias as follows |r~i,hπϵ(wi,ai)−ri,hm,π−i(wi,ai)| | r_i,h^π^ε(w_i,a_i)-r_i,h^m, _-i(w_i,a_i) | ≤|r~i,hπϵ(wi,ai)−r~i,hπ(wi,ai)|⏟(a)+|r~i,hπ(wi,ai)−ri,hm,π−i(wi,ai)|⏟(b). ≤ | r_i,h^π^ε(w_i,a_i)- r_i,h^π(w_i,a_i) |_(a)+ | r_i,h^π(w_i,a_i)-r_i,h^m, _-i(w_i,a_i) |_(b). Using Lemma 5 below, for the second term, we obtain (b) (b) ≤|r~i,hπ(wi,ai)−ri,hm,π−i(wi,ai)| ≤ | r_i,h^π(w_i,a_i)-r_i,h^m, _-i(w_i,a_i) | ≤∑τi=(ai,1,oi,1,…,ai,h,oi,h)∈ℋihP(i,h=τi)τi,h−m+1:h=wi∧ai,h+1=ai ≤ _ _i=(a_i,1,o_i,1,…,a_i,h,o_i,h) ^h_iP (T_i,h= _i )1 \ _i,h-m+1:h=w_i a_i,h+1=a_i \ ⋅|ri,hH,π−i(τi,ai)−ri,hm,π−i(wi,ai)| 200.0003pt· |r_i,h^H, _-i( _i,a_i)-r_i,h^m, _-i(w_i,a_i) | ≲N2H(1−ρ)m, N^2H(1-ρ)^m, and the first term is bounded by Lemma 4, (a)≤4H(N−1)ϵ. (a)≤ 4H(N-1)ε. Together with our probabilistic bound on |r~i,hπ(wi,ai)−r^i,hm,π−i(wi,ai)|| r_i,h^π(w_i,a_i)- r_i,h^m, _-i(w_i,a_i)|, this concludes the proof. ∎ Lemma 4. Let π∈Πmπ∈ ^m, and for ϵ>0ε>0 define πϵ∈Πmπ^ε∈ ^m such that πiϵ(ai∣wi)≔ϵAi+(1−ϵ)πi(ai∣wi). _i^ε(a_i w_i) εA_i+(1-ε) _i(a_i w_i). Let also ri,hm,π(wi,ai)≔w−i∼d−i,hm,π,a−i∼π−i(⋅∣w−i)[ri,hm(wi,w−i,ai,a−i)]. r_i,h^m,π(w_i,a_i) _w_-i d^m,π_-i,h,\,a_-i _-i(· w_-i) [r_i,h^m(w_i,w_-i,a_i,a_-i) ]. Assume ri,hm∈[0,1]r_i,h^m∈[0,1]. Then, for any wi∈ℋi≤mw_i _i^≤ m and ai∈ia_i _i, |ri,hm,π(wi,ai)−ri,hm,πϵ(wi,ai)|≤4H(N−1)ϵ. |r_i,h^m,π(w_i,a_i)-r_i,h^m,π^ε(w_i,a_i) |≤ 4H(N-1)ε. Proof. Fix wi,aiw_i,a_i. We write |ri,hm,π(wi,ai)−ri,hm,πϵ(wi,ai)| |r_i,h^m,π(w_i,a_i)-r_i,h^m,π^ε(w_i,a_i) | =|w−i∼d−i,hm,πa−i∼π−i(⋅∣w−i)[ri,hm(wi,w−i,ai,a−i)]−w−i∼d−i,hm,πϵa−i∼π−iϵ(⋅∣w−i)[ri,hm(wi,w−i,ai,a−i)]| = |E_ subarraycw_-i d^m,π_-i,h\\ a_-i _-i(· w_-i) subarray [r_i,h^m(w_i,w_-i,a_i,a_-i) ]-E_ subarraycw_-i d^m,π^ε_-i,h\\ a_-i π^ε_-i(· w_-i) subarray [r_i,h^m(w_i,w_-i,a_i,a_-i) ] | ≤|w−i∼d−i,hm,πa−i∼π−i(⋅∣w−i)[ri,hm(wi,w−i,ai,a−i)]−w−i∼d−i,hm,πa−i∼π−iϵ(⋅∣w−i)[ri,hm(wi,w−i,ai,a−i)]|⏟(a) ≤ |E_ subarraycw_-i d^m,π_-i,h\\ a_-i _-i(· w_-i) subarray [r_i,h^m(w_i,w_-i,a_i,a_-i) ]-E_ subarraycw_-i d^m,π_-i,h\\ a_-i π^ε_-i(· w_-i) subarray [r_i,h^m(w_i,w_-i,a_i,a_-i) ] |_(a) +|w−i∼d−i,hm,πa−i∼π−iϵ(⋅∣w−i)[ri,hm(wi,w−i,ai,a−i)]−w−i∼d−i,hm,πϵa−i∼π−iϵ(⋅∣w−i)[ri,hm(wi,w−i,ai,a−i)]|⏟(b). + |E_ subarraycw_-i d^m,π_-i,h\\ a_-i π^ε_-i(· w_-i) subarray [r_i,h^m(w_i,w_-i,a_i,a_-i) ]-E_ subarraycw_-i d^m,π^ε_-i,h\\ a_-i π^ε_-i(· w_-i) subarray [r_i,h^m(w_i,w_-i,a_i,a_-i) ] |_(b). For term (a)(a), since ri,hm∈[0,1]r_i,h^m∈[0,1], for any fixed w−iw_-i, |a−i∼π−i(⋅∣w−i)[ri,hm(wi,w−i,ai,a−i)]−a−i∼π−iϵ(⋅∣w−i)[ri,hm(wi,w−i,ai,a−i)]| |E_a_-i _-i(· w_-i)[r_i,h^m(w_i,w_-i,a_i,a_-i)]-E_a_-i π^ε_-i(· w_-i)[r_i,h^m(w_i,w_-i,a_i,a_-i)] | ≤2∥π−i(⋅∣w−i)−π−iϵ(⋅∣w−i)∥TV ≤ 2\| _-i(· w_-i)-π^ε_-i(· w_-i)\|_TV ≤2(N−1)ϵ, ≤ 2(N-1)ε, and hence (a)≤2(N−1)ϵ(a)≤ 2(N-1)ε. For the second term, we have (b)≤‖d−i,hm,π−d−i,hm,πϵ‖TV(b)≤\|d^m,π_-i,h-d^m,π^ε_-i,h\|_TV. By decoupledness of dynamics, d−i,hm,πd^m,π_-i,h factorizes across players, and hence by induction on h∈[H]h∈[H] similar to the proof of Lemma 3.2, we obtain a bound of (b)≤2∑j∈∖i‖dj,hm,π−dj,hm,πϵ‖TV≤2H(N−1)ϵ. (b)≤ 2 _j \i\\|d^m,π_j,h-d^m,π^ε_j,h\|_TV≤ 2H(N-1)ε. Combining the bounds on (a)(a) and (b)(b) gives the claimed inequality. ∎ Lemma 5. Suppose Assumptions 2 and 3 hold. Let π∈Πmπ∈ ^m, and for any i∈i , h∈[H]h∈[H], wi∈ℋi≤mw_i _i^≤ m, τi∈ℋih−1 _i _i^h-1, and ai∈ia_i _i, recall that marginal rewards are defined as ri,hm,π−i(wi,ai) r_i,h^m, _-i(w_i,a_i) ≔w−i∼d−i,hm,π,a−i∼π−i(⋅∣w−i)[ri,hm(wi,w−i,ai,a−i)], _w_-i d^m,π_-i,h,a_-i _-i(· w_-i) [r_i,h^m(w_i,w_-i,a_i,a_-i) ], ri,hH,π−i(τi,ai) r_i,h^H, _-i( _i,a_i) ≔τ−i∼d−i,hH,π,a−i∼π−i(⋅∣τ−i)[ri,hH(τi,τ−i,ai,a−i)]. _ _-i d^H,π_-i,h,a_-i _-i(· _-i) [r_i,h^H( _i, _-i,a_i,a_-i) ]. Then, for any wi∈ℋi≤mw_i _i^≤ m and τi∈ℋiH _i _i^H with τi,h−m+1:h=wi _i,h-m+1:h=w_i, it holds that |ri,hm,π−i(wi,ai)−ri,hH,π−i(τi,ai)|≲N2H(1−ρ)m. |r_i,h^m, _-i(w_i,a_i)-r_i,h^H, _-i( _i,a_i) | N^2H(1-ρ)^m. Proof. Let h∈[H]h∈[H]. We decompose the difference as follows, |ri,hm,π−i(wi,ai)−ri,hH,π−i(τi,ai)| |r_i,h^m, _-i(w_i,a_i)-r_i,h^H, _-i( _i,a_i) | =|∑w−i∈ℋ−i≤m,a−i∈−id−i,hm,π(w−i)⋅π−i(a−i∣w−i)⋅ri,hm(wi,w−i,ai,a−i) = _w_-i _-i^≤ m,a_-i _-id^m,π_-i,h(w_-i)· _-i(a_-i w_-i)· r_i,h^m(w_i,w_-i,a_i,a_-i) −∑τ−i∈ℋ−iH,a−i∈−id−i,hH,π(τ−i)⋅π−i(a−i∣τ−i)⋅ri,hH(τi,τ−i,ai,a−i)| - _ _-i _-i^H,a_-i _-id^H,π_-i,h( _-i)· _-i(a_-i _-i)· r_i,h^H( _i, _-i,a_i,a_-i) ≤(a)|∑w−i∈ℋ−i≤m,a−i∈−id−i,hm,π(w−i)⋅π−i(a−i∣w−i)⋅ri,hm(wi,w−i,ai,a−i) (a)≤ _w_-i _-i^≤ m,a_-i _-id^m,π_-i,h(w_-i)· _-i(a_-i w_-i)· r_i,h^m(w_i,w_-i,a_i,a_-i) −∑τ−i∈ℋ−iH,a−i∈−id−i,hH,π(τ−i)⋅π−i(a−i∣τ−i)⋅ri,hm(τi,h−m+1:h,τ−i,h−m+1:h,ai,a−i)| - _ _-i _-i^H,a_-i _-id^H,π_-i,h( _-i)· _-i(a_-i _-i)· r_i,h^m( _i,h-m+1:h, _-i,h-m+1:h,a_i,a_-i) +2N(1−ρ)m +2N(1-ρ)^m ≤(b)∑w−i∈ℋ−i≤m|d−i,hm,π(w−i)−∑τ−i,1:h−m∈ℋ−iHd−i,hH,π(τ−i,1:h−m∘w−i)|+2N(1−ρ)m (b)≤ _w_-i _-i^≤ m |d^m,π_-i,h(w_-i)- _ _-i,1:h-m _-i^Hd^H,π_-i,h( _-i,1:h-m w_-i) |+2N(1-ρ)^m ≤(c)∑j∈∖i∑wj∈ℋj≤m|dj,hm,π(wj)−∑τj,1:h−m∈ℋjHdj,hH,π(τj,1:h−m∘wj)|+2N(1−ρ)m (c)≤ _j \i\ _w_j _j^≤ m |d^m,π_j,h(w_j)- _ _j,1:h-m _j^Hd^H,π_j,h( _j,1:h-m w_j) |+2N(1-ρ)^m ≤(d)N⋅HN(1−ρ)m+2N(1−ρ)m, (d)≤N· HN(1-ρ)^m+2N(1-ρ)^m, where • (a) uses the reward approximation bound from Lemma 2, • (b) is by boundedness of rewards and rearraging the summations, • (c) holds since by decoupledness of state transitions, we can factor state visitation distributions over players, and • (d) follows from bounding the error in state visitation distributions induced by ℙimP^m_i vs. ℙiHP^H_i inductively over the H steps (similar to the proofs in Lemma 3.2), and using the transition probability approximation bound from Lemma 2. ∎ Next, we provide an approximation bound for the Q function obtained from backward dynamic programming in terms of reward and transition probability estimation errors. Lemma 6. Suppose the bounds on transition and reward estimates from Lemma 3 hold, namely, we have |ℙi,hm(wi′∣wi,ai)−ℙ^i,hm(wi′∣wi,ai)| |P^m_i,h(w_i w_i,a_i)- P_i,h^m(w_i w_i,a_i) | ≤ϵ+(1−ρ)m≕ϵr, ≤ε+(1-ρ)^m _r, |ri,hm,π−i(wi,ai)−r^i,hm,π−i(wi,ai)| |r_i,h^m, _-i(w_i,a_i)- r_i,h^m, _-i(w_i,a_i) | ≤4NHϵ+N2H(1−ρ)m≕ϵℙ. ≤ 4NHε+N^2H(1-ρ)^m _P. Then, for all i∈i , h∈[H]h∈[H], k∈[K]k∈[K], wi∈ℋi≤mw_i _i^≤ m, and ai∈ia_i _i, it holds that |Q^i,hm,π(wi,ai)−Q¯i,hm,π(wi,ai)|≲H3N⋅|i|⋅|i|⋅(ϵN+(1−ρ)m). | Q^m,π_i,h(w_i,a_i)- Q_i,h^m,π(w_i,a_i) |\, \,H^3N·|A_i|·|O_i|· (ε N+(1-ρ)^m ). Proof. The proof proceeds by showing a stronger inequality by backward induction on h, namely that |Q^i,hm,π(wi,ai)−Q¯i,hm,π(wi,ai)|≤ϵr(H+1−h)+ϵℙH(H+1−h)⋅|i|⋅|i|. | Q^m,π_i,h(w_i,a_i)- Q_i,h^m,π(w_i,a_i) |≤ _r(H+1-h)+ _PH(H+1-h)·|A_i|·|O_i|. (8) For H+1H+1, (8) trivially holds. Suppose (8) holds for some h∈[H]h∈[H]. We can write the error as |(Q^i,hm,π−Q¯i,hm,π)(wi,ai)| | ( Q^m,π_i,h- Q_i,h^m,π )(w_i,a_i) | ≤|(r^i,hm,π−i−ri,hm,π−i)(wi,ai)| ≤ | ( r_i,h^m, _-i-r_i,h^m, _-i )(w_i,a_i) | +∑wi′,ai′ℙi,h(wi′∣wi,ai)⋅πi,h+1(ai′∣wi′)⋅(Q^i,h+1m,π−Q¯i,h+1m,π)(wi′,ai′) + _w_i ,a_i P_i,h(w_i w_i,a_i)· _i,h+1(a_i w_i )· ( Q^m,π_i,h+1- Q_i,h+1^m,π )(w_i ,a_i ) +∑wi′,ai′(ℙ^i,h−ℙi,h)(wi′∣wi,ai)⋅πi,h+1(ai′∣wi′)⋅Q^i,h+1m,π(wi′,ai′) + _w_i ,a_i ( P_i,h-P_i,h )(w_i w_i,a_i)· _i,h+1(a_i w_i )· Q^m,π_i,h+1(w_i ,a_i ) ≤(a)ϵr+‖Q^i,h+1m,π−Q¯i,h+1m,π‖∞+ϵℙH⋅|i|⋅|i| (a)≤ _r+ Q^m,π_i,h+1- Q_i,h+1^m,π _∞+ _PH·|A_i|·|O_i| ≤(b)ϵr+(ϵr(H−h)+ϵℙH(H−h)⋅|i|⋅|i|)+ϵℙH⋅|i|⋅|i| (b)≤ _r+ ( _r(H-h)+ _PH(H-h)·|A_i|·|O_i| )+ _PH·|A_i|·|O_i| ≤ϵr(H+1−h)+ϵℙH(H+1−h)⋅|i|⋅|i| ≤ _r(H+1-h)+ _PH(H+1-h)·|A_i|·|O_i| For (a) we use the fact that for most m-step windows, the transition probability error is 0. Namely, for all wi′∈ℋi≤mw_i _i^≤ m for which the first m−1m-1 actions and observation do not coincide with the last m−1m-1 actions and observations of wiw_i, we have ℙ^i,h(wi′∣wi,ai)=ℙi,h(wi′∣wi,ai)=0 P_i,h(w_i w_i,a_i)=P_i,h(w_i w_i,a_i)=0. This observation is crucial, as it saves us an factor exponential in m one would obtain from summing over the entire space ℋi≤mH_i^≤ m. In (b) we apply the induction hypothesis. The final bound follows after plugging in ϵr _r and ϵℙ _P. ∎ Lemma 7. Suppose for some 0<ϵ≤10<ε≤ 1 and for all i∈i , h∈[H]h∈[H], and k∈[K]k∈[K], our Q-function estimates satisfies |Q^i,hm,π(k)(wi,ai)−Qi,hm,π(k)(wi,ai)|≲H3N⋅|i|⋅|i|⋅(ϵN+(1−ρ)m)≔ϵQ. | Q^m,π^(k)_i,h(w_i,a_i)-Q_i,h^m,π^(k)(w_i,a_i) |\, \,H^3N·|A_i|·|O_i|· (ε N+(1-ρ)^m ) _Q. Then, choosing stepsize η(k)=14N2H3kη^(k)= 1 4N^2H^3k, there exists k∈[K]k∈[K] such that for all i∈i , maxπi′∈ΠimV(πi′,π−i(k))−V(π(k))≲N2H3(HN+log(K))αK+NHϵQα+NHϵρmKα. _ _i ∈ _i^mV( _i , _-i^(k))-V(π^(k)) N^2H^3 (HN+ (K) )α K+ NH _Qα+ NH _ρ^m Kα. (9) Proof. Fix some k∈[K]k∈[K] and define for each i∈i the joint policy π~i:=(π1(k),…,πi−1(k),πi(k+1),…,πN(k+1))∈Πm. π^i:=( _1^(k),…, _i-1^(k), _i^(k+1),…, _N^(k+1))∈ ^m. Based on the marginalized Q-function, we further define the advantage functions in mG^m and in the Markov game underlying P, respectively. For any i∈i , h∈[H]h∈[H], π∈Πmπ∈ ^m, wi∈ℋi≤mw_i _i^≤ m, si∈is_i _i, and ai∈ia_i _i, let Ai,hm,π(wi,ai) A^m,π_i,h(w_i,a_i) ≔Q¯i,hm,π(wi,ai)−∑ai′∈iπi,h(ai′∣wi)Q¯i,hm,π(wi,ai′), Q^m,π_i,h(w_i,a_i)- _a_i _i _i,h(a_i w_i) Q^m,π_i,h(w_i,a _i), Ai,hπ(si,ai) A_i,h^π(s_i,a_i) ≔Q¯i,hπ(si,ai)−∑ai′∈iπi,h(ai′∣si)Q¯i,hπ(si,ai′). Q^π_i,h(s_i,a_i)- _a_i _i _i,h(a_i s_i) Q^π_i,h(s_i,a _i). Then, since by Proposition 3.2, the superstate game mG^m is a Markov 2ϵρm2 _ρ^m-potential game, we can decompose Ψ(π(k+1))−Ψ(π(k)) (π^(k+1))- (π^(k)) (10) =∑i=1NΨ(π~i)−Ψ(π~i+1) = _i=1^N ( π^i)- ( π^i+1) (11) ≥−2Nϵρm+∑i=1NVim(π~i)−Vim(π~i+1) ≥-2N _ρ^m+ _i=1^NV^m_i( π^i)-V^m_i( π^i+1) (12) =(a)−2Nϵρm+∑i=1N∑h=1H∑wi,aidi,hm,π~i(wi)(πi(k+1)(ai∣wi)−πi(k)(ai∣wi))Qiπ~i+1(wi,ai) (a)=-2N _ρ^m+ _i=1^N _h=1^H _w_i,a_id^m, π^i_i,h(w_i)\, (π^(k+1)_i(a_i w_i)-π^(k)_i(a_i w_i) )\,Q π^i+1_i(w_i,a_i) (13) ≥(b)η(k)∑i=1N∑h=1H∑widi,hm,π~i(wi)maxaiAi,hm,π(k)(wi,ai)−2η(k)NHϵQ−4N2H3(η(k))2−2Nϵρm (b)≥η^(k) _i=1^N _h=1^H _w_id^m, π^i_i,h(w_i)\, _a_iA^m,π^(k)_i,h(w_i,a_i)-2η^(k)NH _Q-4N^2H^3(η^(k))^2-2N _ρ^m (14) ≥(c)η(k)α∑i=1N∑h=1H∑wimaxaiAi,hm,π(k)(wi,ai)−2η(k)NHϵQ−4N2H3(η(k))2−4NHϵρm (c)≥η^(k)α _i=1^N _h=1^H _w_i _a_iA^m,π^(k)_i,h(w_i,a_i)-2η^(k)NH _Q-4N^2H^3(η^(k))^2-4NH _ρ^m (15) ≥(d)η(k)α∑i=1N(maxπi′∈ΠimV(πi′,π−i(k))−V(π(k)))−2η(k)NHϵQ−4N2H3(η(k))2−4NHϵρm (d)≥η^(k)α _i=1^N ( _ _i ∈ _i^mV( _i , _-i^(k))-V(π^(k)) )-2η^(k)NH _Q-4N^2H^3(η^(k))^2-4NH _ρ^m (16) where (a) is by the performance difference lemma (see Lemma 6 of [47]), and (b) follows similar as in [47], and (d) is by Lemma 8 of [47]. Step (c) requires further justification: We can show along the lines of the proof of Lemma 3.2 that for any π∈Πmπ∈ ^m and i∈i , h∈[H]h∈[H], we have |∑wi∈ℋi≤mdi,hm,π~i(wi)maxaiAi,hm,π(k)(wi,ai)−∑si∈idi,hπ~i(si)maxaiAi,hπ(k)(si,ai)| | _w_i _i^≤ md^m, π^i_i,h(w_i)\, _a_iA^m,π^(k)_i,h(w_i,a_i)- _s_i _id π^i_i,h(s_i)\, _a_iA^π^(k)_i,h(s_i,a_i) | ≤ϵρm, and ≤ _ρ^m,\; and (17) |maxwi∈ℋi≤m,ai∈iAi,hm,π(wi,ai)−maxsi∈i,ai∈iAi,hπ(si,ai)| | _w_i _i^≤ m,a_i _iA^m,π_i,h(w_i,a_i)- _s_i _i,a_i _iA^π_i,h(s_i,a_i) | ≤ϵρm. ≤ _ρ^m. (18) Therefore, we have ∑wi∈ℋi≤mdi,hm,π~i(wi)maxaiAi,hm,π(k)(wi,ai) _w_i _i^≤ md^m, π^i_i,h(w_i)\, _a_iA^m,π^(k)_i,h(w_i,a_i) ≥−ϵρm+∑si∈idi,hπ~i(si)maxaiAi,hπ(k)(si,ai) ≥- _ρ^m+ _s_i _id π^i_i,h(s_i)\, _a_iA^π^(k)_i,h(s_i,a_i) ≥−ϵρm+α⋅maxsi,aiAi,hπ(k)(si,ai) ≥- _ρ^m+α· _s_i,a_iA^π^(k)_i,h(s_i,a_i) ≥−2ϵρm+α⋅maxwi,aiAi,hm,π(k)(wi,ai) ≥-2 _ρ^m+α· _w_i,a_iA^m,π^(k)_i,h(w_i,a_i) where the first inequality is by (17), the second is by Assumption 4, and the third is by (18) and due to 0≤α≤10≤α≤ 1. The final bound (9) follows from a telescoping argument applied to (10), the fact that Ψ(π)≤HN (π)≤ HN for all π∈Πmπ∈ ^m, and our choice of stepsize. ∎ Proof of Theorem 1. By Lemma 7, there exists k∈[K]k∈[K] such that for all i∈i , maxπi′∈ΠimV(πi′,π−i(k))−V(π(k))≲N2H3(HN+log(K))αK⏟(a)+NHϵQα⏟(b)+NHϵρmKα⏟(c). _ _i ∈ _i^mV( _i , _-i^(k))-V(π^(k)) N^2H^3 (HN+ (K) )α K_(a)+ NH _Qα_(b)+ NH _ρ^m Kα_(c). We next show that for appropriately chosen iteration number K, trajectory length T, and window size m, the terms (a), (b), and (c) are all upper bounded by ϵ/3ε/3. With our choices of T≳A2m+2O2N2H6α2β2mϵ2m+2log(1/δ)T A^2m+2O^2N^2H^6α^2β^2mε^2m+2 (1/δ) and m≳ρ−1log(HAONβαϵ)m ρ^-1 ( HAONβαε ), applying Lemma 3 and Lemma 6, yields that with probability at least 1−δ1-δ, we have ϵQ≲ϵαNH _Q εαNH and hence (b)≲ϵ/3(b) ε/3. Moreover, by choosing K≳N4H5α2ϵ2K N^4H^5α^2ε^2, we ensure that both (a)≲ϵ/3(a) ε/3, as well as (c)≲ϵ/3(c) ε/3. The overall sample complexity of Algorithm 1 is given by TK=(A2O2N6H11α4ϵ2(Aβϵ)2mlog(1/δ)). TK=O ( A^2O^2N^6H^11α^4ε^2 ( Aβε )^2m (1/δ) ). Moreover, we have (Aβϵ)2m=exp(2ρlogAβϵ⋅log(HAONβαϵ))=(HAONβαϵ)2ρlog(A/(βϵ)), ( Aβε )^2m= \! ( 2ρ Aβε· \! ( HAONβαε ) )= ( HAONβαε ) 2ρ (A/(βε)), from which we can conclude the bound TK=(A2O2N6H11α4ϵ2(HAONβαϵ)2ρlog(A/(βϵ))log(1/δ)). TK=O ( A^2O^2N^6H^11α^4ε^2 ( HAONβαε ) 2ρ (A/(βε)) (1/δ) ). ∎