Paper deep dive
Nash Approximation Gap in Truncated Infinite-horizon Partially Observable Markov Games
Lan Sang, Chinmay Maheshwari
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 94%
Last extracted: 4/10/2026, 1:59:04 AM
Summary
The paper introduces a finite-memory truncation framework to approximate infinite-horizon Partially Observable Markov Games (POMGs). By restricting agents to condition decisions on finite windows of common and private information, the authors transform intractable infinite-horizon POMGs into finite-state, finite-action Markov games. Under specific filter stability (forgetting) conditions, they prove that any Nash equilibrium of the truncated game serves as an ε-Nash equilibrium of the original POMG, with the approximation gap vanishing as the truncation length increases.
Entities (4)
Relation Signals (2)
Finite-memory truncation → approximates → Partially Observable Markov Games
confidence 95% · We propose a finite-memory truncation framework that approximates infinite-horizon POMGs by a finite-state, finite-action Markov game
Nash Equilibrium → isapproximatesolutionfor → Partially Observable Markov Games
confidence 90% · any Nash equilibrium of the truncated game is an ε-Nash equilibrium of the original POMG
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Partially Observable Markov Games (POMGs) provide a general framework for modeling multi-agent sequential decision-making under asymmetric information. A common approach is to reformulate a POMG as a fully observable Markov game over belief states, where the state is the conditional distribution of the system state and agents' private information given common information, and actions correspond to mappings (prescriptions) from private information to actions. However, this reformulation is intractable in infinite-horizon settings, as both the belief state and action spaces grow with the accumulation of information over time. We propose a finite-memory truncation framework that approximates infinite-horizon POMGs by a finite-state, finite-action Markov game, where agents condition decisions only on finite windows of common and private information. Under suitable filter stability (forgetting) conditions, we show that any Nash equilibrium of the truncated game is an $\varepsilon$-Nash equilibrium of the original POMG, where $\varepsilon \to 0$ as the truncation length increases.
Tags
Links
- Source: https://arxiv.org/abs/2604.05131v1
- Canonical: https://arxiv.org/abs/2604.05131v1
Trouble viewing inline? Open PDF directly →
Full Text
66,835 characters extracted from source content.
Expand or collapse full text
Nash Approximation Gap in Truncated Infinite-horizon Partially Observable Markov Games Lan Sang and Chinmay Maheshwari L. Sang is with Applied Mathematics and Statistics at Johns Hopkins University, Baltimore, MD, USA lsang3@jh.eduC. Maheshwari is with the Department of Electrical and Computer Engineering, Johns Hopkins University, Baltimore, MD, USA chinmay_maheshwari@jhu.edu Abstract Partially Observable Markov Games (POMGs) provide a general framework for modeling multi-agent sequential decision-making under asymmetric information. A common approach is to reformulate a POMG as a fully observable Markov game over belief states, where the state is the conditional distribution of the system state and agents’ private information given common information, and actions correspond to mappings (prescriptions) from private information to actions. However, this reformulation is intractable in infinite-horizon settings, as both the belief state and action spaces grow with the accumulation of information over time. We propose a finite-memory truncation framework that approximates infinite-horizon POMGs by a finite-state, finite-action Markov game, where agents condition decisions only on finite windows of common and private information. Under suitable filter stability (forgetting) conditions, we show that any Nash equilibrium of the truncated game is an ε -Nash equilibrium of the original POMG, where ε→0 → 0 as the truncation length increases. I Introduction Partially Observable Markov Games (POMGs) model sequential decision-making with strategic interactions under asymmetric information, where each agent has access to only partial and possibly private observations of the underlying state. A central difficulty in such games is that agents must form decisions based on their information histories, which differ across players and evolve over time. This leads to heterogeneous beliefs about the underlying state, making the computation of equilibria challenging [10, 15, 5, 16]. A major conceptual advance in addressing asymmetric information in dynamic games is the common-information framework of [15], which reformulates a POMG as a fully observable Markov game over belief states. In this representation, the state is the conditional distribution of the system state and all agents’ private information given the common information, and actions correspond to prescriptions, i.e., mappings from private information to actions. While this reduction provides a powerful structural characterization of equilibria, it introduces two key challenges. First, the resulting belief state space is typically uncountable. Second, the action space—consisting of prescription functions—grows over time as private information accumulates. Together, these aspects render equilibrium computation challenging, specially in infinite horizon games. This motivates the central question in this paper: Can one construct a finite-state, finite-action Markov game approximation of an infinite-horizon POMG, and quantify the approximation error in terms of Nash approximation gap? In this work, we answer this question affirmatively. We introduce a truncated POMG framework, which induces a finite-state, finite-action Markov game by restricting policies to depend only on finite windows of common and private information. In particular, the state is given by a finite window of common information, and actions correspond to prescriptions that map finite windows of private information to actions. Moreover, we identify suitable forgetting conditions (Assumptions 3–4) under which we show that any Nash equilibrium of the truncated game is an approximate Nash equilibrium of the original POMG, with an approximation gap that decays with the truncation length (Theorem 1). Our analysis proceeds in two steps. First, we show that the gap between the optimal response of any player under the truncated policy class and the original policy class decays as the truncation length increases (Lemma 3). Second, we show that the gap between the value achieved in the truncated game and the original game also vanishes with increasing truncation length (Lemma 4). I-A Related Works Our work builds on and extends recent approaches for handling asymmetric information in POMGs, particularly those based on information compression and finite-memory representations. A closely related line of work is [10], which studies compression of common information in finite-horizon POMGs. While their framework provides a principled way to reduce the effective state space, it does not address compression of private information. This distinction is critical in infinite-horizon settings, where both common and private information grow over time and must be controlled to obtain a finite-state, finite-action representation. Moreover, their approximation guarantees rely on the notion of γ-observability [4], which enforces that observations remain sufficiently informative about the underlying state. In contrast, our approach is based on forgetting conditions (Assumptions 3–4), which ensure stability of the filtering process by requiring that the influence of past information decays over time. As discussed in [14], these assumptions capture fundamentally different mechanisms for filter stability. Another closely related work is [6], which proposes a general compression framework for both common and private information in POMGs. However, their approximation error scales with the time horizon, which limits the applicability of their results in infinite-horizon settings considered in this paper. Our approach is also inspired by a growing body of work on finite-memory truncation in single-agent partially observable systems [7, 8, 2]. These works show that restricting policies to depend on finite windows of past observations can yield near-optimal performance while significantly improving tractability. This line of work is closely connected to the filtering literature for hidden Markov models, where stability and forgetting properties ensure that recent observations suffice to approximate the belief state [9, 3]. Building on these ideas, recent works [14, 4, 2] establish that truncated representations can support efficient planning and learning. However, extending these ideas to multi-agent settings introduces additional challenges due to asymmetric information. In POMGs, agents must form beliefs not only over the underlying state but also over the private information of other agents, which grows over time. As a result, truncation must simultaneously control both common and private information across agents, which is not addressed in existing single-agent frameworks. Finally, our work contributes to the broader literature on information compression and approximation in partially observable systems [17, 6, 10, 11, 13, 1]. Within this literature, our main contribution is to provide a finite-state, finite-action Markov game approximation for infinite-horizon POMGs, together with explicit approximation guarantees that decay with the truncation length. I Preliminaries I-A Partially Observable Markov Game Consider an infinite-horizon discounted Partially Observable Markov Game (POMG) G1 G_1, denoted by the tuple G1=⟨ℐ,,,,r,,ℰ,ρ0⟩ G_1= ,S,A,T,r,O,E, _0 . Here, ℐI is the finite set of players; S is the finite set of states; =×i∈ℐiA=×_i A_i is the finite set of joint actions available to all players; iA_i is the finite set of actions of player i; ri:×→ℝr_i:S×A is the one-stage utility function of player i∈ℐi , such that maxi∈ℐ,s∈,a∈|ri(s,a)|≤r¯ _i ,s ,a |r_i(s,a)|≤ r for some r¯>0 r>0; =((s′|s,a))s,s′∈,a∈T=(T(s |s,a))_s,s ,a is the transition kernel such that (s′|s,a)T(s |s,a) denotes the probability of transitioning to state s′s given the current state set to be s and the joint action to be a; :=×i∈ℐiO:=×_i O_i denote the finite set of joint observation space of all players where iO_i is the observation space of player i; ℰ=(ℰ(o|s))o∈,s∈E=(E(o|s))_o ,s is the emission kernel where ℰ(o|s)E(o|s) denotes the probability of observing o∈o given that the current state is s∈s ; and ρ0∈Δ() _0∈ (S) is the initial distribution of states. The interaction between players proceeds in discrete stages indexed by t∈ℕt . The initial state s0∼ρ0s_0 _0. At any time t∈ℕ,t , let sts_t be the state and ot=(oi,t)o_t=(o_i,t) be the joint observation. Due to partial observability, the state sts_t is not accessible to the players. Instead, each player i takes an action ai,ta_i,t using the information locally available to it by time t, denoted by i,t⊆ℋtI_i,t _t, where ℋt=o0,a0,o1,a1,…,at−1,otH_t=\o_0,a_0,o_1,a_1,...,a_t-1,o_t\ is the entire history of information. The heterogneity in the information available to each player makes it an asymmetric information game. Based the the resulting joint action at=(ai,t)i∈ℐ,a_t=(a_i,t)_i , the state transitions to the new state st+1∼(⋅|st,at)s_t+1 (·|s_t,a_t). Additionally, at time t, each player i receives a reward ri(st,at)r_i(s_t,a_t). The information set i,tI_i,t is comprised of a tuple (t,i,t)(c_t,p_i,t), where t⊆ℋtc_t _t is the common information available to all players and i,t⊆ℋtp_i,t _t denotes the private information available to player i at time t. Let tC_t and i,tP_i,t denote the set of all possible common information and private information available to player i at time t, respectively. Furthermore, we define :=⋃t≥0tC:= _t≥ 0C_t, i:=⋃t≥0i,tP_i:= _t≥ 0P_i,t, and :=∏i∈ℐiP:= _i P_i. At every time step t∈ℕt and every i∈ℐi , the action ai,ta_i,t is sampled using a stationary strategy πi:×i→Δ(i) _i:C×P_i→ (A_i). Let π:=(πi)i∈ℐπ:=( _i)_i denote the joint strategy profile. Let Π=×i∈ℐΠi =×_i _i be the set of joint strategy, where Πi _i is the set of strategy of player i∈ℐi . In what follows, we make the following standard assumption about the evolution of common information and private information [15, 10]. Assumption 1 (Structure of History Updates) The evolution of information states is governed by time-homogeneous update kernels. Specifically: 1. Common History Update: The common history evolves recursively as t+1=(t,ct+1+)c_t+1=(c_t,c^+_t+1), where ct+1+⊆ℋt+1c^+_t+1 _t+1 denotes the increment in common information and is drawn from a time-homogeneous kernel: ct+1+∼ζ(t,at,ot+1),∀t∈ℕ.c^+_t+1 ζ(p_t,a_t,o_t+1), ∀\ t . (1) 2. Private History Update: Similarly, for each agent i∈ℐi , the private history evolves as i,t+1=(i,t,pi,t+1+)p_i,t+1=(p_i,t,p^+_i,t+1), where pi,t+1+⊆ℋt+1p^+_i,t+1 _t+1 denotes the increment in private information of player i and is drawn from a time-homogeneous kernel: pi,t+1+∼ξi(i,t,ai,t,oi,t+1).p^+_i,t+1 _i(p_i,t,a_i,t,o_i,t+1). (2) Assumption 1-(1) posits that the increment in common information is based on current private information of players, current joint action and joint observation. Meanwhile, Assumption 1-(2) posits that the increment in private information with time is based only on local action and observation of players. Remark 1 Assumption 1 is different from [15, Assumption 1] for three reasons. First, in (1)-(2), we consider stochastic update unlike [15] who consider deterministic update. Second, as we are working in infinite horizon game, we restrict the the increment updates in (1)-(2) to be governed by time-homogeneous stochastic kernels instead of deterministic maps for both the common and private histories. Finally, as per (2), we allow private information to be non-decreasing with time, which is a realistic assumption for many real world implementation where private information is not forgotten. Such representation of private information update will enable us to study finite-memory policies (to be discussed in next section). Given a joint strategy π∈Ππ∈ , player i aims to maximize the expected infinite-horizon discounted value defined by Vi(π):=π[∑t=0∞δtri(st,at)],V_i(π):=E^π [ _t=0^∞δ^tr_i(s_t,a_t) ], (3) where δ∈[0,1)δ∈[0,1) is the discount factor, s0∼ρ0s_0 _0 and for every t∈ℕt , ai,t∼πi(t,i,t)a_i,t _i(c_t,p_i,t) and st+1∼(⋅|st,at)s_t+1 (·|s_t,a_t). Nash equilibrium is a natural solution concept used to study the interaction between agents with heterogeneous preferences. Definition 1 For any ϵ≥0ε≥ 0, a joint strategy π⋆=(πi⋆)i∈ℐ∈Ππ =( _i )_i ∈ is an ϵε-Nash equilibrium if, for every i∈ℐ,i , πi∈Πi, _i∈ _i, Vi(πi⋆,π−i⋆)≥Vi(πi,π−i⋆)−ϵ.V_i( _i , _-i )\ ≥\ V_i( _i, _-i )-ε. One of the main challenges with the setup of POMG defined here is that of asymmetric information among players. This makes it challenging to computationally characterize Nash equilibrium [15]. To overcome this challenge, [15] gave a construction of symmetric information game, which is described next. I-B Reformulating POMG with Symmetric Information We reformulate the original game G1 G_1 as an equivalent game G2 G_2 played by virtual players who make their strategies condition only on the common history. In G1 G_1, player i uses a stationary strategy πi:×i→Δ(i) _i:C×P_i→ (A_i). Following [15], in G2 G_2, we separate this decision into two steps: 1. Virtual player i selects a prescription based on the common history tc_t. Formally, let the prescription space be Γi:=γi:i→i _i:=\ _i:P_i _i\. 2. The prescription is then applied to the realized private information: ai,t=γi,t(i,t)a_i,t= _i,t(p_i,t). A behavioral strategy of virtual player i, denoted by χi∈i _i _i, maps each common history ∈c to a distribution over deterministic prescriptions, i.e., χi(⋅∣)∈Δ(Γi) _i(· )∈ ( _i). At time t, the virtual player samples γi,t∼χi(⋅∣t) _i,t _i(· _t). We define the joint prescription at time t as γt:=(γi,t)i∈ℐ _t:=( _i,t)_i , and the prescription history up to time t as γ1:t:=(γ1,…,γt) _1:t:=( _1,…, _t). The hidden state, observation, and history update processes then evolve exactly as in G1 G_1. For any player i, define the discounted value in G2 G_2 by111For the sake of concise notation, we are using the same notation of value function in (3) and (4), even though the policies are different in two games. Vi(χ):=χ[∑k=0∞δkri(sk,ak)],V_i(χ)\;:=\;E^χ\! [ _k=0^∞δ^\,k\,r_i(s_k,a_k) ], (4) where s0∼ρ0s_0 _0 and for every k∈ℕk , ai,k=γi,k(i,k),γi,k∼χi(⋅|k)a_i,k= _i,k(p_i,k), _i,k _i(·|c_k) and sk+1∼(⋅|sk,ak)s_k+1 (·|s_k,a_k). Next, we introduce a structural result that establishes equivalence between G1 G_1 and G2 G_2. Proposition 1 (Correspondence between G1 G_1 and G2 G_2) Suppose that Assumption 1 holds. Then, (1) For any strategy χ∈χ (in G2 G_2), there exists a strategy πχ∈Ππ^χ∈ (in G1 G_1) such that the state and action trajectory distribution generated by χ and πχπ^χ is the same. Moreover, if χ is a Nash equilibrium in G2 G_2 then πχπ^χ is a Nash equilibrium for G1 G_1. (2) For any strategy π∈Ππ∈ (in G1 G_1), there exists a strategy χπ∈χ^π (in G2 G_2) such that the state and action trajectory distribution generated by π and χπχ^π is the same. Furthermore, if π is a Nash equilibrium in G1 G_1 then χπχ^π is a Nash equilibrium for G2 G_2. Proposition 1 shows that we can study any of the game G1 G_1 or G2 G_2 and then using the correspondence given here provide guarantees about other game. In what follows, we focus attention on study G2 G_2 as it ensures symmetric information game. I-C Belief State Representation of POMG In this section, we introduce the concept of belief state that acts as a sufficient statistic for converting POMG into a Markov game. We define two useful notions of belief-state which are posterior over the underlying state and private information given the history. First we define, public belief state, which is the posterior over the current state and private information given the common information. More formally, the public belief state at time t,222Note that under Assumption 2 the belief states are independent of the strategy. denoted by βt _t, is defined as βt(s,∣t):=ℙχ(st=s,t=∣t). _t(s,p _t):=P^χ (s_t=s,p_t=p _t ). (5) Next, we define player specific private belief state which for any player i∈ℐi is defined to be the posterior over the current state and private information of other players given the common information and its own private information. More formally, the private belief state of player i, at time t, denoted by φi,t _i,t, is defined as φi,t(s,−i∣t,i,t):=ℙχ(st=s,−i,t=−i|t,i,t). _i,t(s,p_-i _t,p_i,t)\;:=\;P^χ\! (s_t=s,p_-i,t=p_-i\, |\,c_t,\ p_i,t ). (6) Next, we introduce another structural assumption, which is same as [15, Assumption 2], which together with Assumption 1 would enable construction of a Markov state for POMG (to be discussed next). Assumption 2 (Strategy Independence of Beliefs) Consider any two joint strategies χ,χ~∈χ, χ . Let tc_t be a realization of common information at time t that has non-zero probability under both χ and χ~ χ. Then, for all (s,)∈×t(s,p) ×P_t, ℙχ(st=s,t=p∣t=ct)=ℙχ~(st=s,t=p∣t=ct).P^χ(s_t=s,p_t=p _t=c_t)=P χ(s_t=s,p_t=p _t=c_t). (7) Assumption 2 posits that the common information based posterior distribution on state and private information is strategy-independent. Example 1 Consider a POMG where the system state admits the decomposition s=(s0,(si)i∈ℐ)s=(s^0,(s_i)_i ), with s0s^0 being a global state and sis_i a local state private to player i∈ℐi . Given the current state s and the joint action a, the global and local states transitions to (s¯0,(s¯i)i∈ℐ)∼(⋅|s,a)( s^0,( s_i)_i ) (·|s,a). The emission kernel is such that at any time t, the observation made player i is oi,t=(st0,si,t,at−1)o_i,t=(s_t^0,s_i,t,a_t-1). Consequently, the common and private information available to players is such that ct+:=(st0,at−1)c^+_t:=(s_t^0,a_t-1) and pi,t+:=(si,t)p^+_i,t:=(s_i,t). Similar to [15], it can be shown that this example satisfies Assumption 1-2. Next, we introduce the following structural result that provides the evolution of the belief states. Lemma 1 (Fixed Bayesian filtering maps) Suppose Assumptions 1-2 hold. Let χ∈χ be any arbitrary strategy. At any time t, let tc_t be a realization of common information, tp_t be a realization of private information, γt _t be a realization of prescription, ct+1+c^+_t+1 be a relization of common information increment, pt+1+p^+_t+1 be a relaization of private information increment, βt _t be a relization of belief state, and φi,ti∈ℐ\ _i,t\_i be a realization of private belief state for players. Then, the evolution of belief states β,φii∈ℐβ,\ _i\_i is described as follows βt+1 _t+1 =ℱ(βt,ct+1+), =F( _t,c^+_t+1), (8) φi,t+1 _i,t+1 =ℱi(φi,t,ct+1+,pi,t+1+), =F_i( _i,t,c^+_t+1,p^+_i,t+1), (9) where ℱF and ℱii∈ℐ\F_i\_i (termed as Bayesian filtering maps) are fixed mappings (formally defined in the proof). Using Lemma 1, it can be shown that the evolution of public belief state is a controlled Markov process. Lemma 2 (Markov Property of Belief in G2G_2) The public belief βt _t evolves as a Markov process driven by the joint prescription γt _t. Specifically, the update dynamics satisfy: ℙ(βt+1∣t,β1:t,γ1:t)=ℙ(βt+1∣βt,γt).P\! ( _t+1 _t, _1:t, _1:t )\;=\;P\! ( _t+1 _t, _t ). (10) While the public belief state yields a valid Markov representation of the original POMG, the state space of the Markov game is uncountable even when state, action and observation spaces are finite. Furthermore, the unbounded growth of the history spaces (t,t)(c_t,p_t) renders exact computation intractable over an infinite horizon. To overcome this challenge, we introduce a finite memory truncation that approximates the full history using only the most recent ℓ increments. I Approximating Nash Equilibrium Using Trucated Game In this section, we introduce the framework of trucated game that will be used to study the impact of finite memory based policies. Before introducing it, we discuss a new form of Markov state for POMG which is different from the belief based representation discussed in previous section. I-A Finite-Memory based Representation of Belief Updates Here, we introduce a finite-memory window based representation of Markov state for G2 G_2. Definition 2 (Truncated common and private information) Fix a truncation length ℓ∈ℕ . At any time t, we denote the truncated common information by ~t=ℓ(t) c_t=G_ (c_t), where ℓ(t):=(ct−ℓ+1+,…,ct+)ift≥ℓ;(c1+,…,ct+)otherwise.G_ (c_t):= cases(c^+_t- +1,…,c^+_t)&if\ t≥ ;\\ (c^+_1,…,c^+_t)&otherwise. cases (11) We denote the set of truncated common information by ~ C. Similarly, we define the truncated private history by ~i,t=ℓi(i,t) p_i,t=G_ ^i(p_i,t), where ℓi(i,t):=(pi,t−ℓ+1+,…,pi,t+)ift≥ℓ;(pi,1+,…,pi,t+)otherwise.G_ ^i(p_i,t):= cases(p^+_i,t- +1,…,p^+_i,t)&if\ t≥ ;\\ (p^+_i,1,…,p^+_i,t)&otherwise. cases (12) We denote the set of truncated common information by ~i P_i. Under Assumption 1, the common history evolves recursively as t+1=(t,ct+1+)c_t+1=(c_t,c^+_t+1). Therefore, the truncated common information ~t c_t updates as ~t+1=ℓ([~t,ct+1+]), c_t+1=G_ \! ([ c_t,\,c^+_t+1] ), where [~t,ct+1+][ c_t,\,c^+_t+1] denotes appending the new increment to ~t c_t. To account for the influence of the common history before the window, we introduce an auxiliary probability measure at the window start, following finite window belief-MDP reduction in [7]. At any time t, given a realization of t−ℓ,c_t- , define μt _t as follows μt:=βt−ℓ(⋅∣t−ℓ),ift≥ℓ;ρ0,ift<ℓ. _t\;:=\; cases _t- (\,· _t- \,),&if\ t≥ ;\\ _0,&if~t< . cases (13) The pair (μt,~t)( _t, c_t) can be used as an exact coordinate representation of the current belief, since βt _t is obtained by composing ℓ Bayesian updates starting from μt _t along the window ~t c_t. Given μt _t and finite window of common information increment ~t=(ct−ℓ+1+,…,ct+) c_t=(c^+_t- +1,…,c^+_t), the current public belief can be obtained through Lemma 1. That is, βt _t =ℱ(βt−1,ct+)=ℱ(ℱ(βt−2,ct−1+),ct+) =F( _t-1,c^+_t)=F (F( _t-2,c^+_t-1),c^+_t ) (14) =⋯=ℱ(ℓ)(βt−ℓ,~t)=ℱ(ℓ)(μt,~t). =·s=F^( )( _t- , c_t)=F^( )( _t, c_t). Equation (14) shows that the public belief βt _t depends on (μt,~t)( _t, c_t). Hence, any strategy or value function expressed in terms of the belief state βt _t can be equivalently expressed using the fully observed coordinates (μt,~t)( _t, c_t). Analogously, for each player i, we introduce a private predictor νi,t∈Δ(×−i) _i,t∈ (S×P_-i) at the start of the window: νi,t:=φi,t−ℓ(⋅∣t−ℓ,i,t−ℓ),t≥ℓ,φi,0(⋅∣0,i,0),t<ℓ, _i,t:= cases _i,t- (· _t- ,p_i,t- ),&t≥ ,\\[4.30554pt] _i,0(· _0,p_i,0),&t< , cases (15) where φi,0 _i,0 denotes the initial private belief induced by the prior ρ0 _0. By Lemma 1, the exact private belief can then be compactly expressed via the ℓ -step filtering map as φi,t(⋅∣t,i,t)=ℱi(ℓ)(νi,t,~t,~i,t). _i,t(· _t,p_i,t)=F_i^( )\! ( _i,t, c_t, p_i,t ). (16) I-B Constructing Truncated Game In this subsection, we introduce the notion of ℓ− -length truncated game, denoted by Gℓ, G_ , that would be crucial for subsequent exposition. The truncated game is a finite state, finite action Markov game. The state space of this game is ~=(+)ℓ C=(C^+) . The action space of player i is defined as Γiℓ:=γiℓ:~i→i. _i \;:=\; \ _i : P_i _i \. For any truncated private history profile ~=(~i)i∈ℐ∈~:=∏i∈ℐ~i p=( p_i)_i ∈ P:= _i P_i and any joint prescription γℓ=(γiℓ)i∈ℐ∈Γℓ:=∏i∈ℐΓiℓγ =( _i )_i ∈ := _i _i , we define the induced joint action by the componentwise evaluation γℓ(~):=(γi(~i))i∈ℐ∈.γ ( p)\;:=\; ( _i( p_i) )_i . The strategy for player i in Gℓ G_ , denoted by χiℓ∈iℓ _i _i with χiℓ:~→Δ(Γiℓ) _i : C→ ( _i ), maps the current window state to a distribution over finite-memory prescriptions. To define the state transition and stage reward function, we consider an arbitrary distribution μ¯∈Δ(×) μ∈ (S×P). Assuming μ¯ μ as the prior distribution, we define posterior belief on state and private information after observing ~∈~ c∈ C as follows βℓ(⋅∣~):=ℱ(ℓ)(μ¯,~).β (· c)\;:=\;F^( )( μ, c). (17) Because the prescription γℓγ acts only on the truncated private history profile ~=ℓ() p=G_ (p), the induced truncated belief on ×~S× P is defined as the pushforward of βℓ(⋅∣~)β (· c) through the mapping ×∋(s,)↦ϕ(s,):=(s,ℓ())∈×~S×P (s,p) φ(s,p):= (s,G_ (p) ) × P. Define β~ℓ(⋅∣~):=ϕ#βℓ(⋅∣~) β (· c):= _\#β (· c), which evaluates explicitly to: β~ℓ(s,~∣~)=∑:ℓ()=~βℓ(s,∣~). β (s, p c)= _p:\,G_ (p)= pβ (s,p c). (18) Based on the truncated belief β~ℓ(⋅∣~) β (· c), we define the stage reward in Gℓ G_ : riℓ(~,γℓ):=∑s∈∑~∈~β~ℓ(s,~∣~)ri(s,γℓ(~)),r_i ( c,γ )\;:=\; _s _ p∈ P β (s, p c)\,r_i\! (s,γ ( p) ), (19) Next, we define Wσγℓ:×~→Δ(+)W_σ^γ :S× P→ (C^+) as Wσγℓ(c+∣s,~) W_σ^γ (c^+ s, p) :=∑s′∈,o∈(s′∣s,γℓ(~))ℰ(o∣s′) = _s ,\,o T\! (s s,γ ( p) )E\! (o s ) (20) ⋅ζ(c+∣~,γℓ(~),o). ·ζ\! (c^+ p,γ ( p),o ). Using this notation, the distribution of common information increment can be obtained as follows σℓ(c+∣~,γℓ)=∑s∈,~∈~Wσγℓ(c+∣s,~)β~ℓ(s,~∣~).σ (c^+ c,γ )= _s ,\, p∈ PW_σ^γ (c^+ s, p)\, β (s, p c). (21) Finally, the next window state ~′ c updates deterministically via the mapping ψ~(c+):=ℓ([~,c+]) _ c(c^+):=G_ \! ([ c,\,c^+] ). Therefore, the transition kernel of the truncated game Gℓ G_ is defined as the pushforward of the increment distribution σℓ(⋅∣~,γℓ)σ (· c,γ ) through ψ~ _ c. Define ~(⋅∣~,γℓ):=(ψ~)#σℓ(⋅∣~,γℓ) T(· c,γ ):=( _ c)_\#σ (· c,γ ), which evaluates explicitly to: ~(~′∣~,γℓ)=∑c+:ℓ([~,c+])=~′σℓ(c+∣~,γℓ). T( c c,γ )= _c^+:\,G_ ([ c,\,c^+])= c σ (c^+ c,γ ). (22) For any player i and any truncated superstate ~ c, define the value in Gℓ G_ by V~i(χℓ):=χℓ[∑k=0∞δkriℓ(~k,γkℓ)]. V_i(χ )\;:=\;E^χ \! [ _k=0^∞δ^\,k\,r _i( c_k,γ _k) ]. (23) where χℓE^χ denotes the expectation with respect to the information induced by χℓχ and the truncated game dynamics. I-C Nash Approximation Gap due to Truncation As we used an arbitrary μ¯ μ to characterize the Markov game Gℓ, G_ , this would inevitably result in error between the trajectories generated under Gℓ G_ and G2 G_2. Therefore, in this subsection, we quantify the error resulting due to this truncation. To study the error quantification, we introduce following assumptions: Assumption 3 (Uniform filter stability) There exists a nonincreasing function f:ℕ→ℝ+f:N _+ with f(ℓ)→0f( )→ 0 as ℓ→∞ →∞ such that for any ℓ∈ℕ , for any reachable window realization ~∈~ c∈ C, and for any pair of predictors μ,μ′∈Δ(×)μ,μ ∈ (S×P), ‖ℱ(ℓ)(μ,~)−ℱ(ℓ)(μ′,~)‖TV≤f(ℓ)‖μ−μ′‖TV. \|F^( )(μ, c)-F^( )(μ , c) \|_TV\;≤\;f( )\, \|μ-μ \|_TV. (24) This assumption characterizes the “forgetting property” of the filtering process: it guarantees that the influence of the initial predictor μ on the posterior belief decays uniformly as the observation window expands. In other words, the public belief asymptotically becomes independent of the initial belief on the past. Next, we introduce similar assumption that ensures that the private belief asymptotically becomes independent of initial belief on the past: Assumption 4 (Uniform private filter stability) For each virtual player i∈ℐi , there exists a nonincreasing function fi:ℕ→ℝ+f_i:N _+ satisfying limℓ→∞fi(ℓ)=0 _ →∞f_i( )=0, such that for any truncation length ℓ∈ℕ , any reachable truncated history (~,~i)∈~×~i( c, p_i)∈ C× P_i, and any two predictor distributions ν,ν′∈Δ(×−i)ν,ν ∈ (S×P_-i), the truncated private filter ℱi(ℓ)F_i^( ) satisfies ‖ℱi(ℓ)(ν,~,~i)−ℱi(ℓ)(ν′,~,~i)‖TV≤fi(ℓ). \|F_i^( )(ν, c, p_i)-F_i^( )(ν , c, p_i) \|_TV\;≤\;f_i( ). (25) Remark 2 Consider the setting given in Example 1. If the Dobrushin coefficient of the transition kernel T, defined as follows δ():=infs,s′,a∑s′∈Smin((s′∣s,a),(s′∣s′,a)),δ(T):= _s,s ,a _s ∈ S \! (T(s s,a),T(s s ,a) ), (26) is less than 11 then Assumptions 3-4 are satisfied. Next, we leverage Assumptions 3-4 to obtain a relation between Nash equilibrium of Gℓ G_ and G2 G_2 in terms of the truncation length ℓ . Towards that goal, we first introduce the notion of lifted strategy to relate strategy profile in truncated game with that of G2 G_2. Definition 3 (Lifted Strategy) For any truncated strategy profile χℓ∈ℓχ , define its lifted strategy profile L(χℓ)∈L(χ ) as follows (L(χℓ))():=χℓ(ℓ())∀∈. (L(χ ) )(c)\;:=\;χ \! (G_ (c) ) . Moreover, for any opponent strategy profile χ−i∈−i _-i _-i, let iFMRS:=L(χiℓ):χiℓ∈iℓ⊆iX_i^FMRS:=\\,L( _i ):\; _i _i \,\ _i denote the finite-memory restricted strategy set, which is set of all lifted strategies from truncated game. We are now ready to state the main result, which shows that lifting a Markov Nash equilibrium of Gℓ G_ yields an ϵε-Nash equilibrium of the original prescription game G2 G_2. Theorem 1 (ϵε-Nash equilibrium approximation) Suppose that Assumptions 1-4 hold. Let χ∗,ℓ∈ℓχ^*, be a Markov Nash equilibrium of the truncated game Gℓ G_ . Define the lifted strategy profile in G2 G_2 by χ∗:=L(χ∗,ℓ).χ^*:=L(χ^*, ). Then χ∗χ^* is an ϵ(ℓ)ε( )-Nash equilibrium of G2 G_2, i.e., for all players i, and all unilateral deviations χi∈i _i _i, Vi(χi,χ−i∗)≤Vi(χ∗)+ϵ(ℓ),V_i( _i,χ^*_-i)\;≤\;V_i(χ^*)+ε( ), (27) where ϵ(ℓ):=2ξ(ℓ)+κ(ℓ)ε( ):=2ξ( )+κ( ) with ξ(ℓ):=2f(ℓ)r¯(1−δ)2ξ( ):= 2f( )\, r(1-δ)^2 and κ(ℓ):=maxi∈ℐ4fi(ℓ)r¯(1−δ)2κ( ):= _i 4f_i( ) r(1-δ)^2. The proof of Theorem 1 relies on two intermediate results stated below. The first result quantifies the gap between player i’s optimal value function (in G2 G_2), evaluated over iX_i and over the finite-memory restricted set iFMRSX_i^FMRS, for any fixed opponent strategy χ−i∈−i _-i _-i; this gap vanishes as the truncation length increases. Lemma 3 Suppose that Assumptions 1, 2, and 4 hold. For any i∈ℐ,i , χ−i∈−i _-i _-i, we have supχi∈iVi(χi,χ−i)−supχi∈iFMRSVi(χi,χ−i)≤κi(ℓ), _ _i _iV_i( _i, _-i)\;-\; _ _i _i^FMRSV_i( _i, _-i)\;≤\; _i( ), where κi(ℓ)=4fi(ℓ)r¯(1−δ)2. _i( )= 4f_i( ) r(1-δ)^2. The second result quantifies the gap between the value function of any player in Gℓ G_ and G2 G_2 (corresponding to lifted strategy), which vanishes as the truncation length increase. Lemma 4 Suppose that Assumptions 1-3 hold. Fix any player i and any strategy profile χℓ∈ℓχ in the truncated game Gℓ G_ . Then, |Vi(L(χℓ))−V~i(χℓ)|≤ξi(ℓ), |V_i(L(χ ))- V_i(χ ) |\;≤\; _i( ), (28) where ξ(ℓ):=2f(ℓ)r¯(1−δ)2ξ( ):= 2f( )\, r(1-δ)^2. I-D Proofs. Proof of Theorem 1 Fix arbitrary player i∈ℐi and an arbitrary χi∈i _i _i. We note that Vi(χi,χ−i∗)≤supχi∈iVi(χi,χ−i∗) V_i( _i,χ^*_-i)\;≤\; _ _i _iV_i( _i,χ^*_-i) ≤supχ^i∈iFMRSVi(χ^i,χ−i∗)+κi(ℓ), ≤ _ χ_i _i^FMRSV_i( χ_i,χ^*_-i)+ _i( ), where second inequality is due Lemma 3. Thus, there exists a χ^i∈iFMRS χ_i _i^FMRS such that Vi(χi,χ−i∗)≤Vi(χ^i,χ−i∗)+κi(ℓ). V_i( _i,χ^*_-i)\;≤\;V_i( χ_i,χ^*_-i)+ _i( ). (29) Next, we note that, using definition of iFMRSX_i^FMRS, there exists χ^iℓ∈iℓ χ_i _i such that χ^i=L(χ^iℓ) χ_i=L( χ_i ). Thus, L(χ^iℓ,χ−i∗,ℓ)=(χ^i,χ−i∗)L( χ_i , _-i^*, )=( χ_i,χ^*_-i). Consequently, we note that Vi(χ^i,χ−i∗)=Vi(L(χ^iℓ,χ−i∗,ℓ)) V_i( χ_i,χ^*_-i)=V_i(L( χ_i , _-i^*, )) ≤V~i(χ^iℓ,χ−i∗,ℓ)+ξ(ℓ)≤V~i(χ∗,ℓ)+ξ(ℓ), ≤ V_i( χ_i , _-i^*, )+ξ( )≤ V_i(χ^*, )+ξ( ), (30) where the first inequality is due to Lemma 4 and the second inequality is due to the fact that χ∗,ℓχ^*, is a Nash equilibrium in Gℓ G_ . Furthermore, from the statement of Theorem 1, we know that L(χ∗,ℓ)=χ∗L(χ , )=χ . Thus, using Lemma 4, we obtain V~i(χ∗,ℓ)≤Vi(L(χ∗,ℓ))+ξ(ℓ)=Vi(χ∗)+ξ(ℓ) V_i(χ^*, )≤ V_i(L(χ^*, ))+ξ( )=V_i(χ^*)+ξ( ) (31) Combining (29)–(31) we obtain Vi(χi,χ−i∗)≤Vi(χ∗)+2ξ(ℓ)+κi(ℓ).V_i( _i,χ^*_-i)\;≤\;V_i(χ^*)+2ξ( )+ _i( ). This completes the proof. Proof of Lemma 3 Fix any arbitrary time t≥0t≥ 0, any opponent strategy profile χ−i∈−i _-i _-i, and any common history realization t∈tc_t _t that is reachable under (χi′,χ−i)( _i , _-i) for any χi′∈i _i _i. Let χi⋆∈i _i _i denote an optimal response to χ−i _-i. Recall from (16) that the exact private posterior admits the ℓ -step representation φi,t(⋅∣t,i,t)=ℱi(ℓ)(νi,t,~t,~i,t) _i,t(· _t,p_i,t)=F_i^( )( _i,t, c_t, p_i,t), initialized by the history dependent predictor νi,t _i,t (defined in (15)). We now introduce an arbitrary reference predictor ν¯i∈Δ(×−i) ν_i∈ (S×P_-i) and define the corresponding reference truncated posterior as: φi,tℓ(⋅∣~t,~i,t):=ℱi(ℓ)(ν¯i,~t,~i,t). _i,t^\, (· c_t, p_i,t)\;:=\;F_i^( )\! ( ν_i, c_t, p_i,t ). (32) Then, Assumption 4 implies: ∥φi,t(⋅∣t,i,t)−φi,tℓ(⋅∣~t,~i,t)∥TV \| _i,t(· _t,p_i,t)- _i,t^\, (· c_t, p_i,t) \|_TV ≤fi(ℓ). ≤ f_i( ). (33) For any time t≥0t≥ 0, any y∈×−iy ×P_-i, and any action ai∈ia_i _i, we first define the expected future return conditioned on the full state realization as: Jt(y,ai) J_t(y,a_i) :=χi⋆,χ−i[∑k=t∞δk−tri(sk,ak)|(st,−i,t)=y,ai,t=ai]. =E _i , _-i\! [ _k=t^∞δ^k-t\,r_i(s_k,a_k)\; |\; aligned &(s_t,p_-i,t)=y,\\ &a_i,t=a_i aligned ]. (34) Subsequently, we define the exact and the truncated reference Q-values by explicitly taking the expectation of Jt(y,ai)J_t(y,a_i) over their respective private posteriors: Qt(t,i,t,ai) Q_t(c_t,p_i,t,a_i) =yt∼φi,t(⋅∣t,i,t)[Jt(yt,ai)], =E_y_t _i,t(· _t,p_i,t)\! [J_t(y_t,a_i) ], (35) Qtℓ(~t,~i,t,ai) Q_t ( c_t, p_i,t,a_i) =yt∼φi,tℓ(⋅∣~t,~i,t)[Jt(yt,ai)]. =E_y_t _i,t (· c_t, p_i,t)\! [J_t(y_t,a_i) ]. (36) Using the uniform bound ‖Jt(⋅,ai)‖∞≤r¯1−δ\|J_t(·,a_i)\|_∞≤ r1-δ and (33), for any fixed action ai∈ia_i _i, the approximation error of the Q-value is bounded by: |Qt(t,i,t,ai)−Qtℓ(~t,~i,t,ai)| |Q_t(c_t,p_i,t,a_i)-Q_t^\, ( c_t, p_i,t,a_i) | ≤ 2∥Jt(⋅,ai)∥∞∥φi,t(⋅∣t,i,t)−φi,tℓ(⋅∣~t,~i,t)∥TV \;≤\;2\|J_t(·,a_i)\|_∞ \| _i,t(· _t,p_i,t)- _i,t^\, (· c_t, p_i,t) \|_TV ≤2r¯1−δfi(ℓ). ≤ 2 r1-δf_i( ). (37) Let a⋆(t,i,t)∈argmaxaiQt(t,i,t,ai)a (c_t,p_i,t)∈ _a_iQ_t(c_t,p_i,t,a_i) and let a^(~t,~i,t)∈argmaxaiQtℓ(~t,~i,t,ai) a( c_t, p_i,t)∈ _a_iQ_t^\, ( c_t, p_i,t,a_i). Next, we note that maxaiQt(t,i,t,ai)=Qt(t,i,t,a⋆(t,i,t)) _a_iQ_t(c_t,p_i,t,a_i)=Q_t (c_t,p_i,t,a (c_t,p_i,t) ) ≤(I-D)Qtℓ(~t,~i,t,a⋆(t,i,t))+2r¯1−δfi(ℓ) eq:Qt_TV_bound_phi≤Q_t^\, ( c_t, p_i,t,a (c_t,p_i,t) )+ 2 r1-δf_i( ) ≤Qtℓ(~t,~i,t,a^(~t,~i,t))+2r¯1−δfi(ℓ) ≤Q_t^\, ( c_t, p_i,t, a( c_t, p_i,t) )+ 2 r1-δf_i( ) ≤(I-D)Qt(t,i,t,a^(~t,~i,t))+4r¯1−δfi(ℓ), eq:Qt_TV_bound_phi≤Q_t (c_t,p_i,t, a( c_t, p_i,t) )+ 4 r1-δf_i( ), (38) where the second inequality is due to the property of a^(~t,~i,t) a( c_t, p_i,t). Finally, define γ^i∈Γiℓ γ_i∈ _i such that γ^i(~i,t):=a^(~t,~i,t) γ_i( p_i,t):= a( c_t, p_i,t) for all ~i,t∈~i p_i,t∈ P_i. We then construct the truncated behavioral strategy χ^iℓ:~→Δ(Γiℓ) χ_i : C→ ( _i ) in Gℓ G_ by setting χ^iℓ(⋅∣~t):=γ^i χ_i (· c_t):=1_ γ_i, where 1 denotes the Dirac measure. Let χ^i:=L(χ^iℓ)∈iℓ χ_i:=L( χ_i ) _i denote its lifted strategy. For each t≥0t≥ 0, define a hybrid strategy χi(t) _i^(t) such that player i follows χ^i χ_i for the first t stages 0,1,…,t−10,1,…,t-1, and then follows χi⋆ _i from stage t onward. In particular, χi(0)=χi⋆ _i^(0)= _i , and when t→∞t→∞, the strategy χi(t) _i^(t) converges to χ^i χ_i. Therefore, the state transitions and reward distributions perfectly coincide for all steps k<tk<t under the two profiles. By isolating the discounted reward from step t onward, and conditioning on the realized history (t,i,t)(c_t,p_i,t), the law of total expectation yields the following future return: χi(t),χ−i[∑k=t∞δk−tri(sk,ak)|t,i,t]=ai∼χi⋆[Qt(t,i,t,ai)]≤maxai∈iQt(t,i,t,ai), split&E _i^(t), _-i\! [ _k=t^∞δ^k-tr_i(s_k,a_k)\; |\;c_t,p_i,t ]\\ &=E_a_i _i \! [Q_t(c_t,p_i,t,a_i) ]≤ _a_i _iQ_t(c_t,p_i,t,a_i), split (39) and χi(t+1),χ−i[∑k=t∞δk−tri(sk,ak)|t,i,t]=Qt(t,i,t,a^(~t,~i,t)). splitE _i^(t+1), _-i\! [ _k=t^∞δ^k-tr_i(s_k,a_k)\; |\;c_t,p_i,t ]\\ =Q_t (c_t,p_i,t, a( c_t, p_i,t) ). split (40) Since χi(t) _i^(t) and χi(t+1) _i^(t+1) coincide over the first t stages, the cumulative discounted rewards collected before time t are identical under the two profiles and therefore cancel in the difference. Moreover, the two profiles induce the same distribution of (t,i,t)(c_t,p_i,t) under the fixed initial distribution ρ0 _0. Applying (39) and (40), we obtain the single stage deviation gap: Vi(χi(t),χ−i)−Vi(χi(t+1),χ−i)=δtχi(t),χ−i[χi(t),χ−i[∑k=t∞δk−tri(sk,sk)|t,i,t]−δtχi(t+1),χ−i[∑k=t∞δk−tri(sk,ak)|t,i,t]]≤δtχi(t),χ−i[χi(t),χ−i[maxai∈iQt(t,i,t,ai)−Qt(t,i,t,a^(~t,~i,t))]]. split&V_i( _i^(t), _-i)-V_i( _i^(t+1), _-i)\\ &=δ^t\,E _i^(t), _-i [E _i^(t), _-i\! [ _k=t^∞δ^k-tr_i(s_k,s_k)\; |\;c_t,p_i,t ]\\ & -δ^tE _i^(t+1), _-i\! [ _k=t^∞δ^k-tr_i(s_k,a_k)\; |\;c_t,p_i,t ] ]\\ &≤δ^t\,E _i^(t), _-i [E _i^(t), _-i\! [ _a_i _iQ_t(c_t,p_i,t,a_i)\\ & -Q_t (c_t,p_i,t, a( c_t, p_i,t) )\; ] ]. split (41) Applying the uniform bound established in (38) to the term inside the expectation yields Vi(χi(t),χ−i)−Vi(χi(t+1),χ−i)≤δt⋅4r¯1−δfi(ℓ).V_i( _i^(t), _-i)-V_i( _i^(t+1), _-i)\;≤\;δ^t· 4 r1-δ\,f_i( ). Then telescoping over t=0,1,…,T−1t=0,1,…,T-1 gives Vi(χi(0),χ−i)−Vi(χi(T),χ−i) V_i( _i^(0), _-i)-V_i( _i^(T), _-i) (42) =∑t=0T−1(Vi(χi(t),χ−i)−Vi(χi(t+1),χ−i)). = _t=0^T-1 (V_i( _i^(t), _-i)-V_i( _i^(t+1), _-i) ). and hence Vi(χi⋆,χ−i)−Vi(χi(T),χ−i)≤∑t=0T−1δt⋅4r¯1−δfi(ℓ).V_i( _i , _-i)-V_i( _i^(T), _-i)\;≤\; _t=0^T-1δ^t· 4 r1-δf_i( ). By taking the limit as T→∞T→∞, which implies χi(T)→χ^i _i^(T)→ χ_i, and applying the geometric series limit ∑t=0∞δt=(1−δ)−1 _t=0^∞δ^t=(1-δ)^-1, we obtain Vi(χi⋆,χ−i)≤Vi(χ^i,χ−i)+4r¯(1−δ)2fi(ℓ).V_i( _i , _-i)\;≤\;V_i( χ_i, _-i)+ 4 r(1-δ)^2\,f_i( ). (43) Since the lifted strategy χ^i=L(χ^iℓ)∈iFMRS χ_i=L( χ_i ) _i^FMRS, and χi⋆ _i is an optimal response in strategy space iX_i, we obtain: supχi∈iVi(χi,χ−i)−supχi∈iFMRSVi(χi,χ−i)≤4r¯(1−δ)2fi(ℓ). _ _i _iV_i( _i, _-i)- _ _i _i^FMRSV_i( _i, _-i)\;≤\; 4 r(1-δ)^2\,f_i( ). This completes the proof. Proof of Lemma 4 Fix any arbitrary time t≥0t≥ 0, any reachable common history realization t∈c_t under χℓχ , and let ~t=ℓ(t) c_t=G_ (c_t) be its corresponding window state. By the definition of the truncated belief in (17), applying the uniform forgetting property from Assumption 3 directly yields the approximation bound: ∥βt(⋅∣t)−βtℓ(⋅∣~t)∥TV≤f(ℓ)∥μt−μ¯∥TV≤f(ℓ), \| _t(· _t)- _t (· c_t) \|_TV\;≤\;f( ) \| _t- μ \|_TV\;≤\;f( ), (44) where the final inequality follows since the total variation distance between any two probability measures is trivially bounded by 11. Since the induced beliefs are defined as pushforwards through the mapping ϕφ (i.e., β~t=ϕ#βt β_t= _\# _t and β~tℓ=ϕ#βtℓ β_t = _\# _t ), the nonexpansiveness of the TV distance (Lemma 5) yields ∥β~t(⋅∣t)−β~tℓ(⋅∣~t)∥TV≤∥βt(⋅∣t)−βtℓ(⋅∣~t)∥TV≤f(ℓ).\| β_t(· _t)- β_t (· c_t)\|_TV≤\| _t(· _t)- _t (· c_t)\|_TV≤ f( ). (45) Recall the truncated stage reward definition in (19) riℓ(~t,γℓ)=∑s∈∑~∈~β~tℓ(s,~∣~t)ri(s,γℓ(~)),r_i ( c_t,γ )\;=\; _s _ p∈ P β_t (s, p c_t)\,r_i\! (s,γ ( p) ), Define the corresponding conditional expected reward in G2 G_2 at tc_t under the same prescription: ri(t,γℓ):=∑s∈∑~∈~β~t(s,~∣t)ri(s,γℓ(~)),r_i(c_t,γ ):= _s _ p∈ P β_t(s, p _t)\,r_i\! (s,γ ( p) ), where β~t(⋅∣t) β_t(· _t) denotes the induced belief on (st,~t)(s_t, p_t) under tc_t. Using |ri|≤r¯|r_i|≤ r and the TV inequality |μ[g]−ν[g]|≤2‖g‖∞‖μ−ν‖TV|E_μ[g]-E_ν[g]|≤ 2\|g\|_∞\|μ-ν\|_TV, together with (45), we obtain |riℓ(~t,γℓ)−ri(t,γℓ)| |r_i ( c_t,γ )-r_i(c_t,γ ) | ≤2r¯∥β~tℓ(⋅∣~t)−β~t(⋅∣t)∥TV ≤ 2 r\, \| β_t (· c_t)- β_t(· _t) \|_TV (46) ≤2f(ℓ)r¯. ≤ 2f( ) r. Similarly, because both the exact and truncated increment laws are generated by applying the identical Markov kernel WσγℓW_σ^γ (defined in (20)) to their respective induced beliefs, they can be compactly expressed as operator applications: σ(⋅∣t,γℓ)=Wσγℓβ~t(⋅∣t)σ(· _t,γ )=W_σ^γ β_t(· _t) and σℓ(⋅∣~t,γℓ)=Wσγℓβ~tℓ(⋅∣~t)σ (· c_t,γ )=W_σ^γ β_t (· c_t). Consequently, applying the nonexpansiveness of the TV distance immediately yields the error bound: ∥σℓ(⋅∣~t,γℓ)−σ(⋅∣t,γℓ)∥TV \|σ (· c_t,γ )-σ(· _t,γ ) \|_TV (47) =∥Wσγℓβ~tℓ(⋅∣~t)−Wσγℓβ~t(⋅∣t)∥TV = \|W_σ^γ β_t (· c_t)-W_σ^γ β_t(· _t) \|_TV ≤‖β~(~t)−β(t)‖TV≤f(ℓ). ≤ \| β( c_t)-β(c_t) \|_TV≤ f( ). Recall from (22) that the induced transition kernel is the pushforward ~(⋅∣~t,γℓ)=(ψ~t)#σℓ(⋅∣~t,γℓ) T(· c_t,γ )=( _ c_t)_\#σ (· c_t,γ ). Analogously, the exact transition kernel mapped to the window space shares the identical pushforward structure: (⋅∣t,γℓ):=(ψ~t)#σ(⋅∣t,γℓ)T(· _t,γ ):=( _ c_t)_\#σ(· _t,γ ). Since both transition kernels are pushforwards through the same deterministic map ψ~t _ c_t, applying the nonexpansiveness of the TV distance along with the increment bound (47) yields: ∥~(⋅∣~t,γℓ)−(⋅∣t,γℓ)∥TV≤∥σℓ(⋅∣~t,γℓ)−σ(⋅∣t,γℓ)∥TV≤f(ℓ). split \| T(· c_t,γ )-T(· _t,γ ) \|_TV\\ ≤ \|σ (· c_t,γ )-σ(· _t,γ ) \|_TV≤ f( ). split (48) To establish the connection between the transition kernels and the values, we introduce the state values in G2 G_2 and Gℓ G_ . For any time t≥0t≥ 0, any common history ∈tc _t, and its corresponding truncated window ~=ℓ() c=G_ (c), we define: Vi,t(;χ):=χ[∑k=0∞δkri(st+k,at+k)|t=],V_i,t(c;χ):=E^χ [ _k=0^∞δ^kr_i(s_t+k,a_t+k) |c_t=c ], (49) V~i,t(~;χℓ):=χℓ[∑k=0∞δkriℓ(~t+k,γt+kℓ)|~t=~]. V_i,t( c;χ ):=E^χ [ _k=0^∞δ^kr_i ( c_t+k, _t+k ) | c_t= c ]. (50) Define the worst-case value gap Δ(ℓ):=suptsup∈t|V~i,t(~;χℓ)−Vi,t(;χ)|. ( ):= _t _c _t | V_i,t( c;χ )-V_i,t(c;χ) |. Since the original values Vi(χ)V_i(χ) and V~i(χℓ) V_i(χ ) are essentially the state value from t=0t=0, taking the supremum over all possible histories guarantees that |V~i(χℓ)−Vi(χ)|≤Δ(ℓ). | V_i(χ )-V_i(χ) |≤ ( ). Using the Bellman equations in G2 G_2 and Gℓ G_ and the lift χ(t)=χℓ(~t)χ(c_t)=χ ( c_t), for any fixed (t,~t)(c_t, c_t) and any realized prescription Γt=γℓ _t=γ , Vi,t(t;χ) V_i,t(c_t;χ) =γℓ∼χ(t)[ri(t,γℓ)+δVi,t(t+1;χ)], =E_\,γ χ(c_t)\! [r_i(c_t,γ )+δ V_i,t(c_t+1;χ) ], V~i,t(~t;χℓ) V_i,t( c_t;χ ) =γℓ∼χℓ(~t)[riℓ(~t,γℓ)+δV~i,t(~t+1;χℓ)]. =E_\,γ χ ( c_t)\! [r_i ( c_t,γ )+δ V_i,t( c_t+1;χ ) ]. Then the worst-case value gap can be written as: |V~i,t(~t;χℓ)−Vi,t(t;χ)|≤|riℓ(~t,γℓ)−ri(t,γℓ)|⏟Term A+δ|∑~′(~′∣t,γℓ)(V~i(~′;χℓ)−Vi(t+1;χ))|⏟Term B+δ|∑~′(~(~′∣~t,γℓ)−(~′∣t,γℓ))V~i(~′;χℓ)|⏟Term C. split | V_i,t( c_t;χ )-V_i,t(c_t;χ) |≤ |r_i ( c_t,γ )-r_i(c_t,γ ) |_Term A\\ +δ | _ c T( c _t,γ ) ( V_i( c ;χ )-V_i(c_t+1;χ) ) |_Term B\\ +δ | _ c ( T( c c_t,γ )-T( c _t,γ ) ) V_i( c ;χ ) |_Term C. split (51) Term A is bounded by (46) so that A≤2f(ℓ)r¯A≤ 2f( ) r. For term B, since ∑~′(~′∣t,γℓ)=1 _ c T( c _t,γ )=1 and by definition of Δ(ℓ) ( ), B≤∑~′(~′∣t,γℓ)|V~i(~′;χℓ)−Vi(t+1;χ)|≤Δ(ℓ).B≤ _ c T( c _t,γ )\, | V_i( c ;χ )-V_i(c_t+1;χ) |≤ ( ). For term C, using |ri|≤r¯|r_i|≤ r implies ‖V~i(⋅;χℓ)‖∞≤r¯/(1−δ)\| V_i(·;χ )\|_∞≤ r/(1-δ). Applying the TV inequality and (48) yields C C ≤2∥V~i(⋅;χℓ)∥∞∥~(⋅∣~t,γℓ)−(⋅∣t,γℓ)∥TV ≤2 \| V_i(·;χ ) \|_∞\, \| T(· c_t,γ )-T(· _t,γ ) \|_TV ≤2r¯1−δf(ℓ). ≤ 2 r1-δ\,f( ). Plugging the three bounds into (51) and taking supremum over tc_t yields Δ(ℓ)≤2f(ℓ)r¯+δΔ(ℓ)+δ⋅2r¯1−δf(ℓ). ( )≤ 2f( ) r+δ\, ( )+δ· 2 r1-δf( ). Rearranging, (1−δ)Δ(ℓ)≤2f(ℓ)r¯+2δr¯1−δf(ℓ),(1-δ) ( )≤ 2f( ) r+ 2δ r1-δf( ), and hence |V~i(χℓ)−Vi(χ)|≤Δ(ℓ)≤2f(ℓ)r¯1−δ+2δf(ℓ)r¯(1−δ)2=2f(ℓ)r¯(1−δ)2. | V_i(χ )-V_i(χ) |≤ ( )≤ 2f( ) r1-δ+ 2δ f( ) r(1-δ)^2= 2f( ) r(1-δ)^2. IV Conclusion We develop a finite-state, finite-action Markov game approximation of a POMG via truncation of agents’ information histories. Under suitable filter stability conditions, we establish that any equilibrium of the truncated game induces an ε -Nash equilibrium of the original POMG, with ε→0 → 0 as the truncation length increases. This framework opens the door to tractable planning and learning algorithms in infinite-horizon games, including extensions with heterogeneous memory lengths across agents, capturing realistic settings where agents operate with differing informational capacities. Lemma 5 (TV distance nonexpansiveness [12, p. 31]) Let ,X,Y be measurable spaces, and let W(⋅∣x)∈Δ()W(· x)∈ (Y), x∈x . For any p∈Δ()p∈ (X), define the output distribution Wp∈Δ()Wp∈ (Y) by (Wp)(y):=∫W(y∣x)p(x)x,y∈.(Wp)(y):= _XW(y x)\,p(x)dx, y . Then for any p,q∈Δ()p,q∈ (X), ‖Wp−Wq‖TV≤‖p−q‖TV.\|Wp-Wq\|_TV\;≤\;\|p-q\|_TV. References [1] A. Altabaa and Z. Yang (2024) On the role of information structure in reinforcement learning for partially-observable sequential teams and games. Advances in Neural Information Processing Systems 37, p. 6648–6710. Cited by: §I-A. [2] A. Anjarlekar, R. Etesami, and R. Srikant (2025) Scalable policy-based rl algorithms for pomdps. arXiv preprint arXiv:2510.06540. Cited by: §I-A. [3] R. Douc, G. Fort, E. Moulines, and P. Priouret (2009) Forgetting the initial distribution for hidden markov models. Stochastic processes and their applications 119 (4), p. 1235–1256. Cited by: §I-A. [4] 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: §I-A, §I-A. [5] A. Gupta, A. Nayyar, C. Langbort, and T. Basar (2014) Common information based markov perfect equilibria for linear-gaussian games with asymmetric information. SIAM Journal on Control and Optimization 52 (5), p. 3228–3260. Cited by: §I. [6] H. Kao and V. Subramanian (2022) Common information based approximate state representations in multi-agent reinforcement learning. In International Conference on Artificial Intelligence and Statistics, p. 6947–6967. Cited by: §I-A, §I-A. [7] 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: §I-A, §I-A. [8] 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: §I-A. [9] F. Le Gland and N. Oudjane (2004) Stability and uniform approximation of nonlinear filters using the hilbert metric and application to particle filters. The Annals of Applied Probability 14 (1), p. 144–187. Cited by: §I-A. [10] 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: §I-A, §I-A, §I, §I-A. [11] X. Liu and K. Zhang (2026) Partially observable multiagent reinforcement learning with information sharing. SIAM Journal on Control and Optimization 64 (2), p. 673–697. Cited by: §I-A. [12] A. Makur (2019) Information contraction and decomposition. Ph.D. Thesis, Massachusetts Institute of Technology. Cited by: Lemma 5. [13] W. Mao, K. Zhang, E. Miehling, and T. Başar (2020) Information state embedding in partially observable cooperative multi-agent reinforcement learning. In 2020 59th IEEE Conference on Decision and Control (CDC), p. 6124–6131. Cited by: §I-A. [14] C. McDonald and S. Yüksel (2020) Exponential filter stability via dobrushin’s coefficient. Cited by: §I-A, §I-A. [15] A. Nayyar, A. Gupta, C. Langbort, and T. Başar (2013) Common information based markov perfect equilibria for stochastic games with asymmetric information: finite games. IEEE Transactions on Automatic Control 59 (3), p. 555–570. Cited by: §I, §I, §I-A, §I-A, §I-B, §I-C, Example 1, Remark 1. [16] Y. Ouyang, H. Tavafoghi, and D. Teneketzis (2016) Dynamic games with asymmetric information: common information based perfect bayesian equilibria and sequential decomposition. IEEE Transactions on Automatic Control 62 (1), p. 222–237. Cited by: §I. [17] J. Subramanian, A. Sinha, R. Seraj, and A. Mahajan (2022) Approximate information state for approximate planning and reinforcement learning in partially observed systems. Journal of Machine Learning Research 23 (12), p. 1–83. Cited by: §I-A.