Paper deep dive
Internal State-Based Policy Gradient Methods for Partially Observable Markov Potential Games
Wonseok Yang, Thinh T. Doan
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 93%
Last extracted: 4/2/2026, 3:21:14 AM
Summary
This paper introduces an internal state-based natural policy gradient (NPG) method for multi-agent reinforcement learning in partially observable Markov potential games (POMPGs). By leveraging a common information framework and finite-state controllers to compress observation histories, the authors achieve computational tractability and provide a non-asymptotic convergence bound to Nash equilibria, demonstrating performance improvements in partially observable environments.
Entities (5)
Relation Signals (3)
Natural Policy Gradient → solves → Partially Observable Markov Potential Games
confidence 95% · We then implement an internal state-based natural policy gradient method to find Nash equilibria of the Markov potential game.
Common Information Framework → reduces → Dec-POMDP
confidence 90% · The common information framework studied in [5] mitigates these difficulties by having agents share a subset of local observations, enabling a reduction of Dec-POMDP to a centralized MDP
Finite-State Controllers → usedin → Natural Policy Gradient
confidence 90% · the proposed method using finite-state controllers achieves consistent improvements in performance
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:This letter studies multi-agent reinforcement learning in partially observable Markov potential games. Solving this problem is challenging due to partial observability, decentralized information, and the curse of dimensionality. First, to address the first two challenges, we leverage the common information framework, which allows agents to act based on both shared and local information. Second, to ensure tractability, we study an internal state that compresses accumulated information, preventing it from growing unboundedly over time. We then implement an internal state-based natural policy gradient method to find Nash equilibria of the Markov potential game. Our main contribution is to establish a non-asymptotic convergence bound for this method. Our theoretical bound decomposes into two interpretable components: a statistical error term that also arises in standard Markov potential games, and an approximation error capturing the use of finite-state controllers. Finally, simulations across multiple partially observable environments demonstrate that the proposed method using finite-state controllers achieves consistent improvements in performance compared to the setting where only the current observation is used.
Tags
Links
- Source: https://arxiv.org/abs/2604.00433v1
- Canonical: https://arxiv.org/abs/2604.00433v1
Trouble viewing inline? Open PDF directly →
Full Text
42,401 characters extracted from source content.
Expand or collapse full text
Internal State-Based Policy Gradient Methods for Partially Observable Markov Potential Games Wonseok Yang and Thinh T. Doan This work was supported in part by the National Science Foundation (NSF) under CAREER Award 2527059 and AFOSR Grant FA9550-25-1-0247.Wonseok Yang and Thinh T. Doan are with the University of Texas at Austin, Austin, TX, 78712 USA (e-mail:wonseok.yang@utexas.edu, thinhdoan@utexas.edu) Abstract This letter studies multi-agent reinforcement learning in partially observable Markov potential games. Solving this problem is challenging due to partial observability, decentralized information, and the curse of dimensionality. First, to address the first two challenges, we leverage the common information framework, which allows agents to act based on both shared and local information. Second, to ensure tractability, we study an internal state that compresses accumulated information, preventing it from growing unboundedly over time. We then implement an internal state-based natural policy gradient method to find Nash equilibria of the Markov potential game. Our main contribution is to establish a non-asymptotic convergence bound for this method. Our theoretical bound decomposes into two interpretable components: a statistical error term that also arises in standard Markov potential games, and an approximation error capturing the use of finite-state controllers. Finally, simulations across multiple partially observable environments demonstrate that the proposed method using finite-state controllers achieves consistent improvements in performance compared to the setting where only the current observation is used. I Introduction Multi-agent systems have emerged as a powerful paradigm for tackling complex real-world tasks, with applications spanning search and rescue [1], cooperative transportation [2], and autonomous navigation [3]. Problems in these applications are naturally modeled as decentralized partially observable Markov decision processes (Dec-POMDPs), where agents compute policies from local observations. Exact solutions of Dec-POMDPs are computationally intractable due to partial observability, decentralized execution, and the exponential growth of the joint state–action space [4]. The common information framework studied in [5] mitigates these difficulties by having agents share a subset of local observations, enabling a reduction of Dec-POMDP to a centralized MDP over belief states, to which dynamic programming can be applied. This approach, however, requires the knowledge of the environment’s transition dynamics, which are difficult or impossible to obtain in many applications. This motivates the use of data-driven approaches, such as reinforcement learning (RL), where policies are learned directly from data. We study an RL framework for a structured subclass of Dec-POMDPs known as partially observable Markov potential games (POMPGs), which encompasses identical-reward team problems as a special case. In the fully observable setting, Markov potential games (MPGs) are well studied: prior work has established convergence of gradient-based dynamics to Nash equilibria (NE) [8, 9] and characterized their iteration complexity [10, 11]. Under partial observability, however, gradient-based methods remain largely unexplored. While the common information approach can reduce a POMPG to a belief-based MPG [12], the resulting belief space is continuous and uncountable even for finite state spaces [13], rendering direct optimization intractable. Addressing this challenge requires efficient belief representations to design tractable gradient algorithms. To this end, we develop a tractable policy gradient method for POMPGs that can scale to large multi-agent systems. Our approach builds on recent single-agent work [14, 15], where internal state representations compress observation histories to enable policy learning from finite memories. Extending this idea to multi-agent systems is non-trivial due to the decentralized structure; we therefore integrate the common information framework with finite internal state representations to yield a principled and tractable RL approach for POMPGs. Main Contributions. We study internal state-based POMPGs, a structured subclass of POMGs in which each agent maintains finite internal states to compress its shared information history and local memory. By restricting policies to finite-state controllers, we prevent unbounded growth of common information and local memory, achieving computational tractability at the cost of exact optimality. Our focus is to develop a variant of the natural policy gradient (NPG) algorithm to optimize over the class of internal state-based policies, and provide theoretical guarantees on its performance in converging to a Nash equilibrium of the POMPG. Specifically, we establish a performance bound comprising an iteration complexity of (1/T)O(1/ T), where T is the number of iteration, and an approximation error term arising from the use of finite-state controllers. Finally, we validate our theoretical findings through experiments across multiple RL environments, demonstrating the effectiveness of the proposed approach. I Problem Formulation I-A POMPGs with information sharing We consider a partially observable Markov games (POMG) modeled as a tuple =,i,i,P,Ωi,riG=\\,X,\Y_i\,\U_i\,P,\ _i\,\r_i\\, where i∈=1,⋯,ni =\1,·s,n\ and n is the number of agents. In this model, X is a finite set of states, and i,iY_i,U_i denote a finite set of observations and actions at agent i, respectively. Let =1×⋯nU=U_1×·sU_n be the set of joint actions. Then, P:×→ΔP:X×U→ is a state transition probability matrix, where Δ is a distribution over X. Finally, Ωi:→Δi _i:X→ _i is a local probabilistic observation model and ri:×→ℝr_i:X×U denotes the local reward function at agent i. Let ℋiH_i be the local information set available to agent i and ℋ=∪iℋiH= _iH_i. A joint policy π=(μi1,μi2,⋯)π=(\ _i^1\,\ _i^2\,·s) is a sequence of mappings, where μik:ℋik→Δi _i^k:H_i^k→ _U_i specifies the actions of agent i at time k. Given a joint policy π and an initial information h0h^0, let ViπV_i^π be the discounted value function of agent i corresponding to β∈(0,1)β∈(0,1) Viπ(h0)=τ∼h0,T,Ωπ[∑k=0∞βkri(xk,uk)|Hi0=h0],V_i^π(h^0)=E_τ _h^0,T, ^π [ _k=0^∞β^kr_i(x^k,u^k)\,|\,H_i^0=h^0 ],\\ (1) and Ji(π)=h0∼ζ[Viπ(h0)]J_i(π)=E_h^0 ζ [V_i^π(h^0) ] under some initial distribution ζ. In the sequel, we write π=(πi,π−i)π=( _i, _-i), where π−i _-i denotes the collection of agents’ policies but agent i’s. Given π−i _-i, each agent i seeks a policy πi⋆π _i that maximizes its function Ji(πi,π−i)J_i( _i, _-i). In this setting, a common objective is to search for a Nash equilibrium (NE) π∗=(π1∗,⋯,πn∗)π^*=( _1^*,·s, _n^*) satisfying Ji(πi∗,π−i∗)≥Ji(πi,π−i∗),∀πi,i∈.J_i( _i^*, _-i^*)≥ J_i( _i, _-i^*), ∀ _i,\;i . At an NE, no agent has a unilateral incentive to deviate from its equilibrium, provided that all other agents play at their NEs. In this paper, we will focus on a subclass of POMG, namely, partially observable Markov potential games (POMPG). In this setting, there exists a potential function ϕ:×i×−i→ℝφ:X×U_i×U_-i such that the following equality holds for any agent i, and any pair of policies (πi′,π−i)(π _i, _-i) and (πi,π−i)( _i, _-i): Ji(πi′,πi)−Ji(πi,πi)=Φ(πi′,πi)−Φ(πi,πi),J_i(π _i, _i)-J_i( _i, _i)= (π _i, _i)- ( _i, _i), (2) where the global potential function Φ is defined as Φ(π)≔[∑k=0∞βkϕ(xk,uk)|H0=h0]. (π) [ _k=0^∞β^kφ (x^k,u^k )\, |\,H^0=h^0 ]. (3) with ϕmin≤ϕ(x,u)≤ϕmax _ ≤φ(x,u)≤ _ for all (x,u)∈×(x,u) ×U. Finding an NE in the decentralized partially observable MDP (Dec-POMDP) setting is generally challenging and intractable, owing to each agent’s partial and decentralized access to the global environment state. To address this, we adopt the common information sharing framework of [5], which transforms the Dec-POMDP into a centralized MDP. In this framework, each agent shares a portion of its local observations to a common memory accessible by all agents, and each agent then determines its NE policy using both the shared common information and its own local observation. We present this idea as follows. Let mik∈ℳim_i^k _i be the local memory at time k at agent i, i.e., mik⊂yi0,⋯yik−1,ui0,⋯,uik−1m_i^k⊂\y_i^0,·s y_i^k-1,u_i^0,·s,u_i^k-1\. The shared memory ck∈kc_k ^k aggregates observations and actions broadcast by all agents,e.g., ck⊂y0,⋯,yk−1,u0,⋯,uk−1c^k⊂\y^0,·s,y^k-1,u^0,·s,u^k-1\. At time k, each agent obtains local observation yiky_i^k and selects action uiku_i^k based on its available information hik=(yik,mik,ck)h_i^k=(y_i^k,m_i^k,c^k). It then transmits a portion zik⊂mik,yik,uikz_i^k⊂\m_i^k,y_i^k,u_i^k\ to update the shared memory ckc^k. As established in [5], the common information approach reduces the Dec-POMDP to a standard POMDP, which can in turn be solved by reformulating it as an equivalent MDP over the belief state space — the space of probability distributions over X. However, this approach faces two fundamental challenges: (1) the belief state space is uncountable even when X is finite; and (2) computing belief states requires to store the entire history of agents’ observations and the knowledge of the transition kernel P, i.e., a full model of the environment. We address both challenges by introducing finite internal states and implementable approximation to the belief states. Building on this, we will develop a reinforcement learning algorithm in which each agent learns a finite-state NE policy directly from its local observations, without requiring knowledge of P. I-B Finite Internal State-Based Policies We introduce the finite internal state representation for both shared information and local observations at the agents. Let W be a finite set and wk∈w^k represent a compression of the shared information history up to time k. The shared internal state is updated as wk+1=φ(wk,zk,uk)w^k+1= (w^k,z^k,u^k) for some chosen function φ:×→ :W×Z×U . Similarly, we denote by ℒiL_i a finite set and lik∈ℒil_i^k _i a compression of the local memory at time k. The local compressed memory lil_i is updated as łik+1=χi(lik,yik,uik,zik), _i^k+1= _i(l_i^k,y_i^k,u_i^k,z_i^k), where ξi:ℒi×Yi×Ui×i→ℒi _i:L_i× Y_i× U_i×Z_i _i is a prior chosen function. Examples of these functions include a finite window of past observation–action histories and feature representations produced by recurrent neural network (RNN)–based models [17]. Given the internal state-based system, we will consider the class of finite-state controllers (FSC), denoted as Πi _i, where each agent takes action uiku_i^k based on the shared internal state wkw^k, the local internal state likl_i^k, and the local observation yiky_i^k. The objective of the agents is to search a NE policy over Π=Π1×…Πn = _1×… _n, i.e., they seek a π⋆∈Ππ ∈ satisfying Ji(πi∗,π−i∗)≥Ji(πi,π−i∗),∀πi∈Πi,i∈.J_i( _i^*, _-i^*)≥ J_i( _i, _-i^*), ∀ _i∈ _i,\;i . (4) I Internal State Natural Policy Gradient We propose an internal state-based natural policy gradient (NPG) method to find the finite-state NE policy of the POMPG defined in (4). The NPG is a gradient-based algorithm that updates policy parameters while accounting for the geometry of the policy distribution space rather than the Euclidean geometry of the parameter space [18]. Let each policy πi _i parameterized by θi∈ℝ|h^i||ui| _i ^| h_i||u_i| and our focus is to study the tabular softmax policies defined as πθi(ui|h^i)=exp(θh^i,ui)∑ui′exp(θh^i,ui′)⋅ _ _i(u_i| h_i)= ( _ h_i,u_i) _u _i ( _ h_i,u _i)· Let (w0,l0,y0)∼ξ∈Δ×ℒ×(w^0,l^0,y^0) ξ∈ _W×L×Y denote initial approximate information. The initial information available to agent i is (w0,li0,yi0)(w^0,l_i^0,y_i^0), whose distribution is marginal ξi∈Δ×ℒi×i _i∈ _W×L_i×Y_i. Further, we define the discounted visitation distribution conditioned on (w0,li0,yi0)(w^0,l_i^0,y_i^0) under policy π as d(w0,li0,yi0)π(w,l,y) d_(w^0,l_i^0,y_i^0)^π(w,l,y) =(1−β)∑k=0∞βkPrπ(Wk=w,Lik=li,Yik=yi|w0,li0,yi0) =(1-β) _k=0^∞β^kPr^π(W^k=w,L_i^k=l_i,Y_i^k=y_i|w^0,l_i^0,y_i^0) for any policy π and (w,l,y)(w,l,y). Also, let the marginal discounted visitation distribution over information available to agent i be d(w0,li0,yi0)π(w,li,yi)=∑l−i0,y−i0d(w0,li0,yi0)π(w,l,y)d_(w^0,l_i^0,y_i^0)^π(w,l_i,y_i)= _l_-i^0,y_-i^0d_(w^0,l_i^0,y_i^0)^π(w,l,y). For ξi _i, let dξiπ(w,li,yi)=(w0,li0,yi0)∼ξi[d(w0,li0,yi0)π(w,li,yi)]d_ _i^π(w,l_i,y_i)=E_(w^0,l_i^0,y_i^0) _i [d_(w^0,l_i^0,y_i^0)^π(w,l_i,y_i) ]. For notational convenience, let h^i=(w,li,yi) h_i=(w,l_i,y_i) and h^=(w,l,y) h=(w,l,y). The NPG algorithm updates the policy parameter as θit+1=θit+ηFi(θit)†∇θiJi(πθt), _i^t+1= _i^t+η\,F_i( _i^t) _ _iJ_i( _θ^t), (5) where Fi(θit)F_i( _i^t) is the Fisher information matrix Fi(θit)=h^i∼dξiπ,ui∼πθit[∇θilogπθit(ui|h^i)∇θi⊤logπθit(ui|h^i)] -2.84544ptF_i( _i^t)=E_ h_i d_ _i^π,u_i _ _i^t [ _ _i _ _i^t(u_i| h_i) _ _i _ _i^t(u_i| h_i) ] and Fi(θ)†F_i(θ) denote its Moore-Penrose inverse, respectively. Under softmax parameterization, the NPG algorithm updates the parameter θh^i,ui _ h_i,u_i and the policy πi _i as θh^i,uit+1=θh^i,uit+η1−βAiπt(h^i,ui),πit+1(ui|h^i)=πit(ui|h^i)exp(ηAiπt(h^i,ui)1−β)/git(h^i), aligned _ h_i,u_i^t+1&= _ h_i,u_i^t+ η1-β\,A_i^π^t( h_i,u_i),\\ _i^t+1(u_i| h_i)&= _i^t(u_i| h_i) ( η A_i^π^t( h_i,u_i)1-β ) /g_i^t( h_i), aligned (6) where git(h^i)=∑uiπit(ui|h^i)exp(ηAiπt(h^i,ui)/(1−β))g_i^t( h_i)= _u_i _i^t(u_i| h_i) (η A_i^π^t( h_i,u_i)/(1-β) ) is a normalized constant [10]. For each iteration, all agents update their own policy πi _i at the same time, and this algorithm requires the access to AiπtA_i^π^t for synchronous update. The advantage function can be obtained through Monte-Carlo or TD-learning, but we assume that we know the exact advantage function. Details of the NPG algorithm is described in Algorithm 1. 1 Input: Initial policy π0π^0 and learning rate η 2 for t=0t=0 to T−1T-1 do 3 All agents simultaneously: 4 Update policy using (6) 5 6 end Output: Optimized policy πTπ^T Algorithm 1 Internal State NPG Algorithm IV Main Results We present our main theoretical result in Theorem 1, where we provide an upper bound to characterize the convergence properties of the proposed internal state NPG method. Let b(⋅|c)b(·|c) and b(⋅|w)b(·|w) be the belief states defined over (x,y,m)(x,y,m) conditioned on the common information and shared internal state, respectively. In addition, let dbd_b be the total variation distance between these two distributions db d_b =maxw∥b(⋅|c)−b(⋅|w)∥TV. = _w\|b(·\,|\,c)-b(·\,|\,w)\|_TV. (7) Our theoretical bound will depend on this TV distance as the agents can only have access to the shared internal state. For our result, we will assume that infπminiminh^idξiπ(h^i)>0 _π _i _ h_id_ _i^π( h_i)>0, which basically guarantees sufficient exploration of the initial policies ρi _i and has been used extensively in the literature [18]. Finally, we define the NE-gap of agent i as NE-gapi(π)=supπi′Ji(πi′,π−i)−Ji(πi,π−i),NE-gap_i(π)= _π _iJ_i(π _i, _-i)-J_i( _i, _-i), and NE-gap as NE-gap(π)=maxiNE-gapi(π)NE-gap(π)= _iNE-gap_i(π). Theorem 1 Let η=(1−β)2/(2nϕmax)η=(1-β)^2/ (2n _ ). Then the policies πt\π^t\ generated by Algorithm 1 satisfy 1T∑t=0T−1NE-gap(πt)≤(naT)+εFSC, 1T _t=0^T-1\,NE-gap(π^t) ( naT )+ _FSC, (8) where εFSC _FSC =22ϕmax1−β(db2+3Mna(1−β)db), = 2 2 _ 1-β (d_b^2+ 3Mna(1-β)\,d_b ), a a =minh^i∑ui∗πi(ui∗|h^i),ui∗=argmaxuiQiπt(h^i,ui). = _ h_i _u_i^* _i(u_i^*\,| h_i),\,\,u_i^*= _u_iQ_i^π^t( h_i,u_i). Remark 1: The proposed algorithm exhibits performance bound on the averaged NE gap consisting of (1/T)O(1/ T) term and the additional error term. If the state becomes fully observable, then the proposed performance bound can be reduced to (1/T)O(1/ T), which aligns with the result of [10]. Furthermore, the performance bound with n=1n=1 includes (1/T)O(1/ T), analogous to the bound in [14]. The theorem further indicates that the presence of partial observability and use of FSC induces εFSC _FSC which quantifies the difference in estimation of state between common information and internal state that approximates the common information. This implies that expressive internal-state representation reduces this gap, leading to improve the performance. The performance bound depends on the 1/a1/ a that can be possible to become large, as similar to MPGs setting. A small value of a represents the case where the policy far from the NE has difficulty in updating due to the small gradient. This happens when the initial policy is uniform initialization with the large size of the internal state. IV-A Proof of Theorem 1 We next present the analysis to derive the result in Theorem 1. We first present the following intermediate results that are necessary for our analysis. For convenience, we present their proofs in the Appendix. Lemma 1 Given two policies π′,π ,π we have Φ(π′)−Φ(π) (π )- (π) ≤11−βh^i,u[Aϕπ(h^i,u)] ≤ 11-β\,E_ h_i,u [A_φ^π( h_i,u) ] (9) +2ϕmax1−βh^i,u[∥b(⋅|c)−b(⋅|w)∥TV], + 2 _ 1-β\,E_ h_i,u [\,\|b(·\,|\,c)-b(·\,|\,w)\|_TV\, ], where (h^i,u)∼(dξiπ′⊗π′)(⋅)( h_i,u) (d_ _i^π π )(·) are sampled from the marginal state-action distribution induced by policy π′π , and (dξiπ′⊗π′)(h^i,u)=∑l−i,y−idξiπ′(h^)π′(u|h^)(d_ _i^π π )( h_i,u)= _l_-i,y_-id_ _i^π ( h)π (u| h). Remark 1 Lemma 11, a variant of the well-known performance difference lemma in MDP, consists of two terms: one associated with the advantage function and the other capturing the error induced by partial observability and the use of finite-state controllers. In fully observable settings, the latter term vanishes, and the result reduces to the standard performance difference bound for fully observable MPG. In contrast, for internal state–based POMPG, this additional term influences resulting finite-time convergence bounds. Lemma 2 For any π, we have NE-GAP(π)≤11−βmaximaxh^i,uiAiπ(h^i,ui)+2dbϕmax1−β⋅NE-GAP(π)≤ 11-β\, _i\, _ h_i,u_iA_i^π( h_i,u_i)+ 2d_b _ 1-β· (10) Lemma 3 The sequence πt\π^t\ generated by (6) satisfies 11−βh^i,u[Aϕπt(h^i,u)] 11-β\,E_ h_i,u [A_φ^π^t( h_i,u) ] (11) ≥κ∑ρidξiπt+1(h^i)∑j=1nKL(πit+1(⋅|h^j)∥πit(⋅|h^j)) ≥κ _ _id_ _i^π^t+1( h_i)\, _j=1^nKL ( _i^t+1(·\,|\, h_j)\,\|\, _i^t(·\,|\, h_j) ) +1η∑ρidξiπt+1(h^i)∑i=1nlog(git(h^i)), + 1η\, _ _id_ _i^π^t+1( h_i)\, _i=1^n\, (g_i^t( h_i) ), where κ=1η−2nϕmax(1−β)2⋅κ= 1η- 2n _ (1-β)^2· Lemma 4 The sequence πt\π^t\ generated by (6) satisfies ∑h^idξiπt+1(h^i)∑i=1nlog(git(h^i)) _ h_id_ _i^π^t+1( h_i)\, _i=1^n (g_i^t( h_i) ) (12) ≥aη23M(NE-gap(πt)−2dbϕmax1−β)2, ≥ aη^23M\, (NE-gap(π^t)- 2d_b _max1-β )^2, where M=supπmaxh^i1dξiπ(h^i)M= _π _ h_i 1d_ _i^π( h_i). Proof of Theorem 1: Using (9)–(12) with η=(1−β)22nϕmaxη= (1-β)^22n _ yields Φ(πt+1)−Φ(πt)+2dbϕmax1−β (π^t+1)- (π^t)+ 2d_b _ 1-β ≥aη3M(NE-gap(πt)−2dbϕmax1−β)2, ≥ aη3M\, (NE-gap(π^t)- 2d_b _max1-β )^2, which when summing up over t gives 1T∑t=0T−1(NE-gap(πt)−2dbϕmax1−β)2 1T _t=0^T-1 (NE-gap(π^t)- 2d_b _max1-β )^2 ≤3MaηT((Φ(πT)−Φ(π0))+2dbTϕmax1−β) ≤ 3Maη T ( ( (π^T)- (π^0) )+ 2d_bT _ 1-β ) ≤3Mϕmaxa(1−β)ηT+6dbMϕmaxa(1−β)η⋅ ≤ 3M _ a(1-β)η T+ 6d_bM _ a(1-β)η· By using the relation λ12≤2λ22+2(λ1−λ2)2 _1^2≤ 2 _2^2+2( _1- _2)^2, where λ1=NE-gap(πt) _1=NE-gap(π^t) and λ2=2dbϕmax1−β _2= 2d_b _max1-β, we obtain NE-gap(πt)2≤8db2ϕmax2(1−β)2+2(NE-gap(πt)−2dbϕmax1−β)2, -gap(π^t)^2≤ 8d_b^2 _ ^2(1-β)^2+2 (NE-gap(π^t)- 2d_b _max1-β )^2, which when summing over t and using the relation above gives 1T∑t=0T−1NE-gap(πt)2 1T _t=0^T-1\,NE-gap(π^t)^2 ≤8db2ϕmax2(1−β)2+2(3Mϕmaxa(1−β)ηT+6dbMϕmaxa(1−β)η) ≤ 8d_b^2 _ ^2(1-β)^2+2 ( 3M _ a(1-β)η T+ 6d_bM _ a(1-β)η ) =(12Mnϕmax2a(1−β)3)1T+8ϕmax2(1−β)2(db2+Mna(1−β)db). = ( 12Mn _ ^2a(1-β)^3 ) 1T+ 8 _ ^2(1-β)^2 (d_b^2+ Mna(1-β)d_b ). Applying the Jensen’s inequality to the preceding relation immediately gives Eq. (8). This concludes our proof. V Simulation Figure 1: Learning curve of ITRPO for MATiger and MABC Figure 2: One run of the learned policy on LBF environment We evaluate the proposed NPG algorithm on partially observable common-reward games across three environments from the POSGGym benchmark [19]: Multi-Agent Tiger (MATiger), Multi-Access Broadcast Channel (MABC), and Level-Based Foraging (LBF). In MATiger, two agents face two doors concealing a tiger and a treasure, respectively. At each step, each agent independently chooses to open the left door, open the right door, or listen. Opening the treasure door yields a reward of +10, opening the tiger door incurs a penalty of -100, and listening yields -1. Agents receive noisy observations of the tiger’s location and the doors opened, with the objective of maximizing cumulative team reward over a 10-step episode. In MABC, two nodes share a communication channel that supports only one successful transmission at a time. Each node independently chooses to transmit or remain idle, receiving a reward of 11 if exactly one node transmits and 0 otherwise, along with noisy collision observations. Agents share the objective of maximizing channel throughput over a 1010-step episode. In LBF, two agents navigate a 4×44× 4 grid world containing one food item, with each agent’s observation limited to a sight range of 1. Agents may move within the grid or execute a lift action to collect adjacent food, upon which a reward is received and the episode terminates. The maximum episode length is set to 50. In our experiments, neural network (N)-based policy and value function are used for implementability. We use independent Trust Region Policy Optimization (ITRPO) [20] with parameter sharing, which is a variant of NPG. The finite window of memory is selected as the internal state representation, and the finite-memory policy is used for finite-state controller. In addition, we set the local internal state at time t as lit=(yit−tw:t−1,uit−tw:t−1)l_i^t=(y_i^t-t_w:t-1,u_i^t-t_w:t-1) and the shared internal state as wt=y−it−tw:t−1w^t=y_-i^t-t_w:t-1, where twt_w is the length of memory. We let tw=2t_w=2 for all experiments. Main Observations. The simulation results yield several key insights. As shown in Figure 1, the finite-memory policy consistently achieves higher returns than the reactive policy across both MATiger and MABC environments. Notably, the reactive policy fails to learn in MABC, underscoring that memory is essential for effective decision-making under partial observability. Figure 2 further illustrates that the finite-memory policy learned in the LBF environment produces coordinated agent behavior—agents align their movements and successfully complete the task—demonstrating that internal states naturally facilitate structured cooperation. Beyond performance improvements, these results reveal that internal state representations serve as a structural mechanism that implicitly approximates belief states without requiring explicit belief updates, thereby enabling tractable learning. The learning curves exhibit consistent improvement before saturating at large iteration counts, in agreement with the convergence properties established in Theorem 1. Finally, the performance gap between the finite-memory and reactive policies reflects the approximation error introduced by finite-state controllers, suggesting that richer internal state representations could further reduce this gap. VI Appendix VI-A Proof of Lemma 1 Let Vϕπ(h^i0)=π′[∑k=0∞βkϕ(xk,uk)|h^i0]V_φ^π( h_i^0)=E^π [ _k=0^∞β^kφ(x^k,u^k)| h_i^0 ]. The performance difference can be expressed as Vϕπ′(h^i0)−Vϕπ(h^i0) V_φ^π ( h_i^0)-V_φ^π( h_i^0) (13) =π′[∑k=0∞βk(ϕ(xk,uk)+βVϕ0π(sk+1,h^ik+1) =E^π [ _k=0^∞β^k (φ(x^k,u^k)+β V_ _0^π(s^k+1, h_i^k+1) −Vϕπ(h^ik))|h^i0] -V_φ^π( h_i^k) )| h_i^0 ] +βπ′[∑k=0∞βk(Vϕπ(h^ik+1)−Vϕ0π(sk+1,h^ik+1))|h^i0], + ^π [ _k=0^∞β^k (V_φ^π( h_i^k+1)-V_ _0^π(s^k+1, h_i^k+1) )| h_i^0 ], where Vϕ0π(s0,h^i0)=π′[∑k=0∞βkϕ(xk,uk)|s0,h^i0],V_ _0^π(s^0, h_i^0)=E^π [ _k=0^∞β^kφ(x^k,u^k)|s^0, h_i^0 ], and sk=(xk,yk,mk).s^k=(x^k,y^k,m^k). Applying the law of total expectation to the first term in (13), we obtain π′[ϕ(xk,uk)+βVϕ0π(sk+1,h^ik+1)−Vϕπ(h^ik)|h^i0] ^π [φ(x^k,u^k)+β V_ _0^π(s^k+1, h_i^k+1)-V_φ^π( h_i^k)| h_i^0 ] (14) =π′[π′[ϕ(xk,uk)+βVϕ0π(sk+1,h^ik+1)|ck,hk] =E^π [E^π [φ(x^k,u^k)+β V_ _0^π(s^k+1, h_i^k+1)|c^k,h^k ] −Vϕπ(h^ik)|h^i0]. -V_φ^π( h_i^k)| h_i^0 ]. Rewrite the conditional expectation in (14) with dbk=∥b(⋅|ck)−b(⋅|wk)∥TVd_b^k=\|b(·\,|\,c^k)-b(·\,|\,w^k)\|_TV and Qϕ0π(⋅)≤ϕmax/(1−β)Q_ _0^π(·)≤ _ /(1-β) where Qϕ0π(s0,h^i0,u0)=π′[∑k=0∞βkϕ(xk,uk)|s0,h^i0,u0]Q_ _0^π(s^0, h_i^0,u^0)=E^π [ _k=0^∞β^kφ(x^k,u^k)|s^0, h_i^0,u^0 ], then we obtain π′[ϕ(xk,uk)+βVϕ0π(sk+1,h^ik+1)|ck,h^k] ^π [φ(x^k,u^k)+β V_ _0^π(s^k+1, h_i^k+1)|c^k, h^k ] (15) =∑sk,ukb(sk|ck)π′(uk|h^k)Qϕ0π(sk,h^ik,uk) = _s^k,u^kb(s^k|c^k)\,π (u^k| h^k)\,Q_ _0^π(s^k, h_i^k,u^k) =∑sk,uk(b(sk|ck)−b(sk|wk))π′(uk|h^k)Qϕ0π(sk,h^ik,uk) = _s^k,u^k (b(s^k|c^k)-b(s^k|w^k) )π (u^k| h^k)Q_ _0^π(s^k, h_i^k,u^k) +∑ukπ′(uk|h^k)Qϕπ(h^ik,uk). + _u^kπ (u^k| h^k)\,Q_φ^π( h_i^k,u^k). ≤ϕmax1−βdbk+Qϕπ(h^ik,uk). ≤ _ 1-β\,d_b^k+Q_φ^π( h_i^k,u^k). Substituting (15) into (14), we obtain the first term in (13) as ∑k=0∞βkπ′[π′[ϕ(sk,uk)+βVϕ0π(sk+1,h^ik+1)|ck,h^k] _k=0^∞β^k\,E^π [E^π [φ(s^k,u^k)+β V_ _0^π(s^k+1, h_i^k+1) |c^k, h^k ] (16) −Vϕπ(h^ik)|h^i0] -V_φ^π( h_i^k) | h_i^0 ] ≤∑k=0∞βkπ′[ϕmax1−βdbk+Qϕπ(h^ik,uk)−Vϕπ(h^ik)|h^i0] ≤ _k=0^∞β^k\,E^π [ _ 1-βd_b^k+Q_φ^π( h_i^k,u^k)-V_φ^π( h_i^k)\, |\, h_i^0 ] =π′[∑k=0∞βkAϕπ(h^ik,uk)|h^i0]+ϕmax1−βπ′[∑k=0∞βkdbk|h^i0]. =E^π [ _k=0^∞β^kA_φ^π( h_i^k,u^k)| h_i^0 ]+ _ 1-βE^π [ _k=0^∞β^kd_b^k| h_i^0 ]. A similar argument can be applied to the second term, yielding βπ′[∑k=0∞βk(Vϕπ(h^ik+1)−Vϕ0π(sk+1,h^ik+1))|h^i0] ^π [ _k=0^∞β^k (V_φ^π( h_i^k+1)-V_ _0^π(s^k+1, h_i^k+1) )| h_i^0 ] (17) ≤ϕmax1−βπ′[∑k=0∞βkdbk|h^i0]. ≤ _ 1-β\,E^π [ _k=0^∞β^kd_b^k| h_i^0 ]. Combining the above bounds, we obtain Vϕπ′(h^i0)−Vϕπ(h^i0) V_φ^π ( h_i^0)-V_φ^π( h_i^0) (18) ≤π′[∑k=0∞βkAϕπ(h^ik,uk)|h^i0]+2ϕmax1−βπ′[∑k=0∞βkdbk|h^i0]. ^π [ _k=0^∞β^kA_φ^π( h_i^k,u^k)| h_i^0 ]+ 2 _ 1-β\,E^π [ _k=0^∞β^kd_b^k| h_i^0 ]. Considering ξi _i, (18) becomes (9). This completes the proof. VI-B Proof of Lemma 2 Consider two policies π′=(πi′,π−i)π =(π _i, _-i) and π=(πi,π−i)π=( _i, _-i). Using the definition of NE-gap, (2) and (18), we obtain (10). This concludes the proof. VI-C Proof of Lemma 3 Define mixed policy as π~−i(u−i|h^−i)=∏j=1i−1πjt+1(uj|h^j)∏j=i+1nπjt(uj|h^j), π_-i(u_-i| h_-i)= _j=1^i-1 _j^t+1(u_j| h_j) _j=i+1^n _j^t(u_j| h_j), and corresponding local advantage function as A~i,ϕt(h^i,ui)=∑u−iπ~−i(u−i|h^−i)Aϕt(h^i,ui) A_i,φ^t( h_i,u_i)= _u_-i π_-i(u_-i| h_-i)A_φ^t( h_i,u_i). The following term is obtained as h^i,u[Aϕπt(h^i,u)] _ h_i,u [A_φ^π^t( h_i,u) ] (19) =∑h^idξt+1(h^i)∑i=1n∑ui(πit+1(ui|h^i)−πit(ui|h^i))A~i,ϕπt(h^i,ui), = _ h_id_ξ^t+1( h_i)\, _i=1^n _u_i ( _i^t+1(u_i| h_i)- _i^t(u_i| h_i) ) A_i,φ^π^t( h_i,u_i), due to πt+1−πt=∑i=1n(πit+1−πit)(∏j<iπjt+1)(∏j>iπjt)π^t+1-π^t= _i=1^n( _i^t+1- _i^t)\,( _j<i _j^t+1)\,( _j>i _j^t), and the definition of A~i,ϕπt(h^i,ui) A_i,φ^π^t( h_i,u_i). (19) can be rewritten as ∑ui(πit+1(ui|h^i)−πit(ui|h^i))A~i,ϕπt(h^i,ui) _u_i ( _i^t+1(u_i| h_i)- _i^t(u_i| h_i) ) A_i,φ^π^t( h_i,u_i) (20) =∑uiπit+1(ui|h^i)Ai,ϕπt(h^i,ui) = _u_i _i^t+1(u_i| h_i)A_i,φ^π^t( h_i,u_i) +∑ui(πit+1(ui|h^i)−πit(ui|h^i))(A~i,ϕπt(h^i,ui)−Ai,ϕπt(h^i,ui)). + _u_i ( _i^t+1(u_i| h_i)- _i^t(u_i| h_i) ) ( A_i,φ^π^t( h_i,u_i)-A_i,φ^π^t( h_i,u_i) ). Using the definition of KL divergence and NPG update, the first term in (20) becomes ∑uiπit+1(ui|h^i)Ai,ϕπt(h^i,ui) _u_i _i^t+1(u_i| h_i)A_i,φ^π^t( h_i,u_i) (21) =1−βη(KL(πit+1(⋅|h^i)||πit(⋅|h^i))+log(Git(w,li,yi))). = 1-βη (KL ( _i^t+1(·| h_i)\,||\, _i^t(·| h_i) )+ (G_i^t(w,l_i,y_i) ) ). The difference in advantage functions in (20) is bounded as |A~i,ϕπt(h^i,ui)−Ai,ϕπt(h^i,ui)| | A_i,φ^π^t( h_i,u_i)-A_i,φ^π^t( h_i,u_i) | (22) ≤ϕmax1−β∑j=1n∥πjt+1(⋅|h^j)−πjt(⋅|h^j)∥1. ≤ _ 1-β\, _j=1^n \| _j^t+1(·| h_j)- _j^t(·| h_j) \|_1. Substituting (22) into (20) and using the Pinsker’s inequality, we obtain ∑ui(πit+1(ui|h^i)−πit(ui|h^i))(A~i,ϕπt(h^i,ui)−Ai,ϕπt(h^i,ui)) _u_i ( _i^t+1(u_i| h_i)- _i^t(u_i| h_i) ) ( A_i,φ^π^t( h_i,u_i)-A_i,φ^π^t( h_i,u_i) ) (23) ≤2nϕmax1−β∑j=1nKL(πit+1(⋅|h^j)∥πit(⋅|h^j)), ≤ 2n _ 1-β _j=1^nKL ( _i^t+1(·| h_j)\,\|\, _i^t(·| h_j) ), and this completes the proof. VI-D Proof of Lemma 4 Let ui∗=argmaxuiQiπ(h^i,ui)∈i∗u_i^*= _u_iQ_i^π( h_i,u_i) _i^*, and ui−∗∈i ∗u_i^-* _i\, \,U_i^*. Git(h^i)G_i^t( h_i) can be decomposed into the term with respect to ui∗u_i^* and ui−∗u_i^-* as Git(h^i) G_i^t( h_i) =∑ui∗πit(ui|h^i)exp(ηmaxuiAiπt(h^i,ui)1−β) = _u_i^* _i^t(u_i| h_i) ( η _u_iA_i^π^t( h_i,u_i)1-β ) +∑ui−∗πit(ui|h^i)exp(ηAiπt(h^i,ui)1−β). + _u_i^-* _i^t(u_i| h_i) ( η A_i^π^t( h_i,u_i)1-β ). Applying Taylor’s expansion, we obtain the bound as Git(h^i,ui) G_i^t( h_i,u_i) ≥1+12∑ui∗πit(ui|h^i)(ηmaxuiAiπt(h^i,ui)1−β)2 ≥ 1+ 12\, _u_i^* _i^t(u_i| h_i) ( η _u_iA_i^π^t( h_i,u_i)1-β )^2 ≥1+a2(ηmaxuiAiπt(h^i,ui)1−β)2. ≥ 1+ a2\, ( η _u_iA_i^π^t( h_i,u_i)1-β )^2. For η≤(1−β)2η≤(1-β)^2, we have a2(ηmaxuiAiπt(h^i,ui)1−β)2≤12 a2\, ( η _u_iA_i^π^t( h_i,u_i)1-β )^2≤ 12, and use the inequality log(1+λ3)≥23λ3 (1+ _3)≥ 23 _3 for 0≤λ3≤120≤ _3≤ 12, then the bound can be rewritten as log(Git(h^i,ui))≥a3(ηmaxuiAiπt(h^i,ui)1−β)2. (G_i^t( h_i,u_i) )≥ a3\, ( η _u_iA_i^π^t( h_i,u_i)1-β )^2. (24) Using (24) and the definition of M, we obtain the bound of ∑h^idξπt+1(h^i)∑i=1nlog(Git(h^i)) _ h_id_ξ^π^t+1( h_i) _i=1^n (G_i^t( h_i) ) as (12). This concludes the proof. References [1] M. Lyu, Y. Zhao, C. Huang, and H. Huang, “Unmanned aerial vehicles for search and rescue: A survey”, Remote Sens, vol. 15, no. 13, Jun, 2023. [2] B. Pandit, A. Gupta, M. S. Gadde, A Johnson, A. K. Shrestha, H. Duan, J. Dao, and A. Fern, ”Learning Decentralized Multi-Biped Control for Payload Transport”, 2024, arXiv:2406.17279. [3] J. J. Choi, J. J. Aloor, J. Li, M. G. Mendoza, H. Balakrishnan, and C. J. Tomlin, ”Resolving Conflicting Constraints in Multi-Agent Reinforcement Learning with Layered Safety”, 2025, arXiv preprint arXiv:2505.02293. [4] M. J. Kochenderfer, T. A. Wheeler, and K. H. Wray, ”Algorithms for Decision Making”, MA, USA: MIT Press, 2022. [5] A. Nayyar, A. Mahajan, and D. Teneketzis, ”Decentralized Stochastic Control with Partial History Sharing: A Common Information Approach”, IEEE Trans. Autom. Control, vol. 58, no. 7, p. 1644-1658, Jul. 2013. [6] Q. Liu, C. Szepesvari and C. Jin, ”Sample-Efficient Reinforcement Learning of Partially Observable Markov Games”, in Proc. Adv. Neural Inf. Process. Syst. (NeurIPS), 2022. [7] X. Liu and K. Zhang, ”Partially Observable Multi-agent RL with (Quasi-)Efficiency: The Blessing of Information Sharing”, in Proc. Int. Conf. Mach. Learn. (ICML), 2023. [8] S. Leonardos, W. Overman, I. Panageas, and G. Piliouras, ”Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games”, 2021, ,arXiv:2106.01969. [9] R. Zhang, Z. Ren, and N. Li, ”Gradient play in stochastic games: stationary points, convergence, and sample complexity”, IEEE Trans. Autom. Control, vol. 69, no. 10, p. 6499–6514, Oct. 2024. [10] R. Zhang, J. Mei, B, Dai, D. Schuurmans and N. Li, ”On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Games”, in Proc. Adv. Neural Inf. Process. Syst. (NeurIPS), 2022. [11] Y. Sun, T. Liu, R. Zhou, P. R. Kumar, and S. Shahrampour, ”Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games”, in Proc. Adv. Neural Inf. Process. Syst. (NeurIPS), 2023. [12] K. Horak and B. Bosansky, ”Solving Partially Observable Stochastic Games with Public Observations”, in Proc. AAAI Conf. Artif. Intell. (AAAI), vol. 33, no. 1, p. 3410–3417, 2019. [13] S. Seuken and S. Zilberstein, “Memory-Bounded Dynamic Programming for DEC-POMDPs”, in Proc. Int. Joint Conf. Artif. Intell. (IJCAI), 2007. [14] S. Cayci, N. He, and R. Srikant, “Finite-time analysis of natural actor-critic for POMDPs”, SIAM J. Math. Data Sci., vol. 6, no. 4, p. 869–896, 2024. [15] W. Mao, K. Zhang, Z. Yang, and T. Başar, ”Decentralized Learning of Finite-Memory Policies in Dec-POMDPs”, in Proc. IFAC World Congr.,2023 [16] S. Kakade, ”A Natural Policy Gradient”, in Proc. Adv. Neural Inf. Process. Syst. (NeurIPS), 2001. [17] S. Cayci and A. Eryilmaz, ”Recurrent Natural Policy Gradient for POMDPs”, 2024, arXiv preprint arXiv:2405.18221. [18] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan, ”On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift”, J. Mach. Learn. Res., vol. 22, no. 98, p. 1–76, 2021. [19] J. Schwartz, R. Newbury, D. Kulic, and H. Kurniawati, ”POSGGym: a library for decision-theoretic planning and learning in partially observable, multi-agent environments”, Auton. Agents Multi-Agent Syst., vol. 39, no. 35, 2025. [20] J. Schulman, S. Levine, P. Moritz, M. Jordan, and P. Abbeel, ”Trust Region Policy Optimization”, in Proc. Int. Conf. Mach. Learn. (ICML), 2015.