{'fraction_non_alphanumeric': 0.04220449601160261, 'fraction_numerical': 0.012849891225525743, 'mean_word_length': 4.259496567505721, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Common Information based Approximate State Representations in Multi-Agent Reinforcement Learning

Due to information asymmetry, finding optimal policies for Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) is hard with the complexity growing doubly exponentially in the horizon length. The challenge increases greatly in the multi-agent reinforcement learning (MARL) setting where the transition probabilities, observation kernel, and reward function are unknown. Here, we develop a general compression framework with approximate common and private state representations, based on which decentralized policies can be constructed. We derive the optimality gap of executing dynamic programming (DP) with the approximate states in terms of the approximation error parameters and the remaining time steps. When the compression is exact (no error), the resulting DP is equivalent to the one in existing work. Our general framework generalizes a number of methods proposed in the literature. The results shed light on designing practically useful deep-MARL network structures under the"centralized learning distributed execution"scheme.


INTRODUCTION
Finding optimal policies for Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) is hard due to information asymmetry, which refers to the mismatch in the set of information each agent has in a multi-agent environment. In fact, a finite-horizon Dec-POMDP with more than one agent is NEXP-complete [Bernstein et al., 2002], implying a doubly exponential complexity growth in the horizon length. In decentralized control theory, theoretical solutions have been proposed to find the optimal control laws for Dec-POMDPs. Notably among them is the common information (CI) approach [Nayyar et al., 2013], a framework that decomposes the decision of a full policy into the decision of a "prescription policy" from the CI known by all the agents, and the "prescription" itself which is a full characterization of how the agents should act based on any realization of their own private information (PI). This approach effectively transforms the decentralized model back to a centralized one from the view of a fictitious "coordinator" who only observes the CI, and permits a coordinator level sequential decomposition using a belief state a'la POMDPs [Kumar and Varaiya, 2015].
The challenge increases greatly in the multi-agent reinforcement learning (MARL) setting where the model -transition probabilities, observation kernel, and reward function -is unknown. When the agents learn concurrently, information asymmetry causes another issue called the "non-stationarity issue," since the effective environment observed by each agent is time-varying as the other agents learn and update their policies. The issue can be alleviated in principle by the "centralized learning and distributed execution" scheme [Dibangoye and Buffet, 2018] as the learning is from the coordinator's viewpoint; indeed, if agents only update their policies using CI, they can perfectly track others' policies. However, there is still a big gap in applying the CI approach to the MARL setting. First, the Bayesian updates of the belief state in the CI approach require the knowledge of the model, which are not available in the MARL setting. Moreover, the linear growth of length of private histories leads to the doubly exponential growth of the space of prescriptions in time, which is explosively large even for toy-size environments and forbids any practical explorations in such space. One natural question is whether we can restrict attention to some policies (and prescriptions) that take some state variable as inputs without losing much performance, where the state variables encapsulate the crucial information relevant to future decisions in a time-invariant domain, and where the representations (ways of encapsulation) can be learned without the knowledge of the model.
In this paper, we formulate good approximate common and private state representations for learning close-to-optimal policies in unknown finite-horizon Dec-POMDPs, where each agent receives its own private information plus a common observation. The agents also share the same commonly observed rewards; however, they may not know each others' actions. We propose conditions in Definition 3 for an approximate sufficient private state (ASPS), which compresses an agent's private information, i.e., its action observation history (AOH), and conditions in Definition 5 for an approximate sufficient common state (ASCS), which compresses the fictitious coordinator's AOH, with the actions being ASPS-based prescriptions and the observations being common observations. Critically, using Theorem 4 and Theorem 6, in Theorem 7 we derive the optimality gap in terms of the error parameters of our compression and the remaining time steps, between the values of two dynamic programmings (DPs): one in Algorithm 1 for the optimal policy using the CI approach without compression, with states being the complete coordinator's AOHs and actions being the prescriptions from Nayyar et al. [2013]; and the other in Algorithm 3 using our framework with states being any valid 1 ASCSs and the actions being ASPS-based prescriptions for valid ASPS. Our framework generalizes a number of results in the literature: first, it extends the approximate information state (AIS) framework [Subramanian and Mahajan, 2019, Subramanian et al., 2020 to the multiagent setting; second, it extends the CI approach [Nayyar et al., 2013] and the follow-up sufficient private information (SPI) framework that compresses the private states [Tavafoghi et al., 2021], to their general approximate state representation counterpart; third, it generalizes the work by Mao et al. [2020] to include non-injective compressions and a general approximate common state representation. Our results can provide guidance on designing Deep Learning (DL) structures to learn the (compressed) state representations and the optimal policies (using learned representations) under the centralized learning distributed execution scheme, which applies to practical offline or online MARL settings.
Related Work. The problem of state representation is well studied in the single-agent POMDP case. Stochastic control theory details the conditions an information state (IS) needs to satisfy so that it acts as the Markov state in an equivalent MDP so one may only consider IS-based policies without loss of generality [Mahajan and Mannan, 2016]; the belief state is an example of such IS [Kumar and Varaiya, 2015]. Subramanian et al. [2020] extends the idea to an approximate information state (AIS), where the IS conditions hold approximately; importantly, the optimality gap of running DP with any valid AIS is quantified. Based on their AIS scheme, they propose a DL framework that learns the AIS representation without knowing the model. Recent work on Deep Bisimulation for Control (DBC) [Zhang et al., 2021b] in the DL literature uses similar ideas: they train an encoder to predict well the instantaneous rewards and transitions, and use the encoder output to train the policies. The encoder is an encapsulation or a compression. The optimality gap established is similar to the result of the infinite horizon case in Subramanian and Mahajan [2019]. There are more representation learning schemes not requiring model knowledge in the DL or RL literature, e.g. Ha and Schmidhuber [2019], with the bulk without theoretical guidance or guarantees.
In the multi-agent context, Nayyar et al. [2013] propose a belief IS for the coordinator using the CI approach, without compressing agents' private information. Tavafoghi et al. [2018] further compress private histories to sufficient private information (SPI) so that the corresponding spaces of the belief IS and prescriptions are time-invariant. They identify conditions such that restricting attention to SPI-based policies is without loss of optimality. However, not only do they consider a control setting where the model is required, but also only present compression of the common history to a belief state, which is a narrow class of compression schemes. Nevertheless, this work will be a starting point of our work. Mao et al. [2020] consider an information state embedding that injectively maps agents' histories to representations in a fixed domain, and quantify the effect of the embedding on the value function like Subramanian and Mahajan [2019]. However, their requirement that the mapping is injective is impractical for two reasons: one, an injective mapping does not reduce the policy complexity; and two, real world applications often demand non-injective encapsulationse.g., tiger [Kaelbling et al., 1998] where one IS is the number of right observations minus the number of left observations, which is non-injective. Moreover, they also compress the common state to a belief state, but it is unclear how this can be done in practice without model information.
Another line of work in deep-MARL literature also applies the notion of CI (also known as the common knowledge) to solving MARL problems [Schroeder de Witt et al., 2019, Lerer et al., 2019, Sokota et al., 2021. They search for optimal policies for a Dec-POMDP when the model is known, while we consider designing sample efficient and lower regret learning algorithms in an offline or online MARL setting for an unknown model. Moreover, many of them involve heuristic or approximation methods without knowing the potential loss from the approximations or apply a variety of machine learning schemes without a theoretical basis or understanding.

PRELIMINARIES
Notation. Let ∆(X ) denote the set of distributions on the space X , and Ω(X) denote the space where the variable X takes values. Superscripts are used as the agent index and subscripts as the time index. The notation X c:d a:b denotes the tuple (X c a , . . . , X d a , . . . , X c b , . . . , X d b ). In some cases superscripts or subscripts are omitted, and if so the meaning will be clarified. Capital letters are used for random variables while lower case letters are for their realizations. For random variables X with a realization x, we use the short hand notation P(·|x) P(·|X = x) and E[·|x] E[·|X = x]. If a random variable appears without realization in a place other than the operand of E, then it means the related equation should hold for any Borel measurable subset in its domain.

Dec-POMDP Model
Suppose there are N agents in the system. We consider the Dec-POMDP model, i.e., a tuple (S, A, P T , R, O, P O , T, P I ) where the quantities are: S is the state space; A = A 1 × · · · × A N is the joint action space whose elements are joint actions A = (A 1 , . . . , A N ); P T : S × A → ∆(S) is the transition kernel mapping a current state and a joint action to a distribution of new states P T : S × A → ∆(S); R : S × A → ∆(R) is the reward function mapping a current state and a joint action to a probability distribution on the reals; O = O 0 × O 1 × · · · × O N is the joint observation space whose elements are joint observations O = (O 0 , O 1 , . . . , O N ), where O 0 is commonly observed but O n is only observed by agent n; P T : S → ∆(O) is the observation kernel mapping a current state to a distribution of joint observations; T is the time horizon; P I ∈ ∆(S) is the initial state distribution. In comparison to the standard Dec-POMDP model [Oliehoek and Amato, 2016], we have an additional common observation (including the reward), and our observations depend only on the current state.
We assume S, A, O, and T are finite and known in advance, while P T , R, P O , and P I are unknown in the MARL setting. Further, agents have perfect recall. At time t, agent n observes (O 0 t , O n t ) generated from P O (S t ), then uses the policy A n t = g n t (O 0 1:t , g 1:t−1 , H n t ) to select its action, where g s = g 1:N s and H n t = (A n 1:t−1 , O n 1:t ) is agent n's private history and known as its AOH. The agents receive a reward R t R(S t , A t ) sampled from R(S t , A t ), and the next state S t+1 is generated from P T (S t , A t ). The goal is to find a policy g = g 1:T to maximize the common cumulative reward where the expectation is taken over the measure generated by policy g applied to model (P T , R, P O , P I ).

AIS Framework
In the single-agent POMDP setting, the spaces A and O are not product spaces, and at time t the agent's policy is of the form g t : Ω(H t ) → Ω(A t ), where H t = (A 1:t−1 , O 1:t ) is the agent's AOH. Note the policy space grows exponentially in t as the length of H t grows linearly in t. Subramanian and Mahajan [2019] give conditions of a representation encapsulating the information in H t that is approximately sufficient for decision purposes into a time-invariant space.
Definition 1: An (ǫ, δ)-approximate information state Z t is the output of a function Z t = ϑ t (H t ) that satisfies the following properties: AIS3) It suffices for approximately predicting the observation, i.e., ∀ h t , a t , we have K(P(O t+1 |h t , a t ), P(O t+1 | z t , a t )) ≤ δ , where K(·, ·) is a distance between two distributions 2 .
The value function at t obtained from Bellman equations with Z's as states falls behind the optimal value function at the most by an expression linear in T − t, ǫ, and δ [Subramanian and Mahajan, 2019]. When ǫ = δ = 0, the expression is 0, and the AIS Z degenerates to an IS Z.
In Subramanian and Mahajan [2019], a DL framework is provided to find an "approximate mapping" ϑ t (·) for any given POMDP model. The idea is to interpret the quantities in the LHS of (AIS2) and (AIS3) as driving the learning loss in DL, and let existing DL optimization algorithms find good mappings. The resulting AIS can then be used as the state in common policy approximation methods to find a near-optimal policy.

DP with No Compression
In a DecPOMDP, the action decision for agent n at time t, A n t = g n t (O 0 1:t , g 1:t−1 , H n t ), can be split into two steps. In the first step, based on past common observations and policies (O 0 1:t , g 1:t−1 ) (using perfect recall), the agent decides g n t and hence Γ n t (·) g n t (O 0 1:t , g 1:t−1 , ·); then in the second step, it simply applies Γ n t to H n t to obtain the action A n t = Γ n t (H n t ). The function Γ n t is called the prescription (function), since it prescribes what the agent should do based on any possible realization of its private information.
This decomposition technique is called the CI approach [Nayyar et al., 2013]. Note that the actual decision is carried out in the first step and solely upon CI (perfect recall makes policy common knowledge). One may then imagine there is a fictitious coordinator, labelled agent 0. At time t, the coordinator's policy is of the form d t : ; then it sends Γ t to every agent, and agent n selects A n t = Γ n t (H n t ). It is shown that this decomposition is without loss of generality (so without loss of optimality too). The coordinator observes common observation O 0 t and chooses action Γ t ; hence, H 0 t can be seen as the coordinator's AOH and will be called the full common state (FCS), while H n t will be referred to as the full private state (FPS) of agent n. From the perspective of the coordinator, the problem is now a centralized POMDP, and the goal is to find a policy d = d 1:T that maximizes the expected cumulative reward. This permits a sequential decomposition with FCS as the state and an FPS-based prescription (meaning the prescription takes FPS as its input) as the action, which is presented in Algorithm 1.

Algorithm 1 Dynamic Programming with FCSs and FPS-based Prescriptions
In practice, the coordinator is virtual and the computation of the coordinator is carried out in all agents -this is viable since the coordinator's computation only requires CI, which every agent has access to. Note the update of the state is done by direct concatenation of the incoming Γ t and O 0 t+1 .

DP with BCS
Nayyar et al. [2013] further compresses the FCS to the belief common state (BCS) Π t = P(S t , H 1:N t |H 0 t ), which is the conditional distribution on the state and the FPSs given the FCS.
It is shown that restricting attention to coordinator's policy of the form .
is without loss of optimality. The DP presented thus uses this BCS as the state and an FPS-based prescription as the action -see Appendix A.2.
There are two problems with this approach when applied to the MARL setting. First, the BCS is updated via a Bayesian update using P T and P O , which requires model knowledge. Second, the growing length of H 1:N t makes the spaces of Π t and Γ t explosively large and impossible to explore. However, at a conceptual level we can apply the AIS framework to the centralized POMDP of the coordinator 3 ; the underlying decentralized information structure coupled with increasing domain of private information makes practical implementations of this scheme challenging.

DP with BCS and SPI
To alleviate the aforementioned dimensionality issue, Tavafoghi et al. [2018] further compresses the FPS to a representation called the sufficient private information (SPI) lying in a time-invariant domain. They identify a set of conditions for the compression so that the SPI is sufficient for decision making purposes.
It is shown that restricting attention to coordinator's policy of the form d ∼ t : Ω(Π ∼ t ) → Ω(Λ t ) is without loss of optimality. The resulting DP uses the BCS as the state and SPI-based prescription as the action -see Appendix A.3. Note that the compression actually leads to an action compression for the coordinator -from FPS-based prescriptions to SPI-based prescriptions -which has no loss in performance.
With Π ∼ t , Z 1:N t , and Λ t all lying in time-invariant spaces, the complexity no longer grows with time. However, it is unclear how to find mappings satisfying Definition 2 and update the BCSs in an MARL setting. Further, the solution focuses on a decentralized setting wherein the (lossless) compression functions are consistent (common knowledge), and the performance assessments and predictions are based only on the information of any particular agent. Ensuring these properties in the RL context would require significant communication, particularly during training.

APPROXIMATE STATE REPRESENTATIONS
We seek to extend the idea of identifying representations sufficient for approximately optimal decision making from Section 2.2 to the multi-agent setting, and develop a general compression framework for common states and private states (hence also prescriptions) whose mappings can be learned from samples obtained by interacting with the environment alone.
In this section, we propose our general states representation framework for approximate planning and control in partially observable MARL problems. We start by compressing private histories to ASPS; for the coordinator, this induces an action compression from FPS-based prescriptions to ASPS-based prescriptions. Then based on this compression, the common history is further compressed to ASCS.
The framework we develop will be consistent with the philosophy of recent empirical MARL work wherein there is a centralized agent called the supervisor. The supervisor observes all the quantities and develops good compression of private information and common information that the coordinator can use to produce close-to-optimal prescriptions (using the compressed common information), which can be implemented by the agents using just their own compressed private information. We detail the supervisor in Section 4.1 but point out here that it has the knowledge of H 0:N t for all t ∈ [T ]. Note that this viewpoint is consistent with the "centralized training with distributed execution" setting of the empirical MARL work.

Compressing Private States
This definition induces the ASPS-based prescription, which is a mapping λ t : ) in a component-wise manner. One can run a DP with FCSs as states and ASPS-based prescriptions as actions -see Algorithm 2.

Algorithm 2 Dynamic Programming with FCSs and ASPS-based Prescriptions
The compression is characterized by functions ϑ 1:N t . These functions also relate Ω(Γ t ) and Ω( Λ t ) as ASPS-based prescriptions are a strict subset of FPS-based prescritions; this detail will be explained in Section 4.2. For now we note that here the conditions we set for the action compression from Ω(Γ t ) to Ω( Λ t ) are on the private states instead of defining an encapsulation directly on the actions (i.e., prescriptions); moreover, the compression may depend on the common state h 0 t as well. Hence, this falls outside of the action compression scheme studied in Subramanian et al. [2020]. We bound the error between the value functions obtained from Algorithm 2 and the optimal value functions obtained from Algorithm 1 in the following theorem proved in Section 4.2. Theorem 4: Assume the reward function R is uniformly bounded byR. For any h 0 wheret = T − t.

Compressing Common States
While restricting attention to ASPS-based prescriptions, we further compress the common history to an approximate representation by applying the state compression result of Subramanian and Mahajan [2019].
Definition 5: An (ǫ c , δ c )-approximate sufficient common state (ASCS) Z 0 t is the output of a function Z 0 t = ϑ 0 t (H 0 t ) satisfying the properties: (ASCS1) It evolves in a recursive manner, that is, In our proposed representation framework, agents compress the CI and PI to ASCS Z 0 t and ASPS Z 1:N t , which can be updated recursively using the incoming CI and PI. Agents use the same policy d * t : Ω( Z 0 t ) → Ω( Λ t ) to decide the ASPS-based prescription Λ t from Z 0 t , then they apply Λ t to their own ASPS Z n t to obtain the action A n t . Approximately optimal policies then result from the DP with ASCSs as states and ASPS-based prescriptions as actions -see Algorithm 3.

Algorithm 3 Dynamic Programming with ASCSs and ASPS-based Prescriptions
From Algorithm 2 to Algorithm 3, only the states are further compressed, so a gap result bounding the difference between the two DPs holds, similar to the result in Subramanian and Mahajan [2019]. See Appendix C for details. Theorem 6: Assume the reward function R is uniformly bounded byR. For any h 0 t ∈ Ω(H 0 t ) and λ ∈ Ω( Λ t ), witht = T − t, we have

Main Result
Our main result bounds the optimality gap of value functions obtained from performing DP with the general common and private representations satisfying the conditions in Definition 3 and Definition 5 as in Algorithm 3, in comparison to the optimal value functions computed from Algorithm 1. Theorem 7: Assume the reward function R is uniformly bounded byR. For any h 0 wheret = T − t.
We observe that the action compression induced by private state compression leads to a gap quadratic in remaining timet = T − t (Theorem 4), and common state compression causes a gap linear in remaining time. Also, note that the gap decreases to 0 as (ǫ c , δ c , ǫ p , δ p ) go to 0. Having developed this result, the remaining questions for learning using the sample data from the environment are: how to learn the compression mappings ϑ 0:N 1:T with small error; and how to learn good policies with the compressed representations. See Appendix E for a proposed scheme to answer both these questions using DL methods.

Comparisons to Existing Schemes
Nayyar et al. [2013] and Tavafoghi et al. [2018] provide lossless (performance-wise) compression. We refer to ASPS and its corresponding conditions with ǫ p = δ p = 0 as SPS; similarly, we refer to ASCS and its corresponding conditions with ǫ c = δ c = 0 as SCS. Missing proofs in this subsection are in Appendix D.
Relation to Nayyar et al. [2013]. The private history is not compressed in Nayyar et al. [2013], so it is clearly a special case of SPS. The BCS proposed in Nayyar et al. [2013] is a special case of SCS as well.

Restricting to SPS, their BCS
is a special case of SCS as well, so a result identical to Proposition 8 holds with FPS changed to SPS. Mao et al. [2020]. Their private state embedding does not require a recursive update (ASPS1), but demands injective functions ϑ 1:N t . With this additional assumption they show linearity of the optimality gap in remaining time. For the common state, the BCS they consider is a special case of our SCS, just as the BCS of Tavafoghi et al. [2018].

OPTIMALITY GAP ANALYSIS
In this section, we outline the optimality gaps introduced in Section 3; details are in Appendix B.

Supervisor's Functions
For better exposition, we introduce another set of Q/V functions from an omniscient supervisor's perspective, for the original decision problem. The supervisor can access the union of the information of all agents: at time t the supervisor knows H 0:N t . In contrast, coordinator's information is the intersection of the information of all agents: H 0 t . The supervisor, however, only observes what is happening, lets the coordinator decide all the policies and prescriptions, and implements the coordinator's policies. Let d * 1:T be a coordinator's optimal policy solved using Algorithm 1, Then the Q/V functions defined in Algorithm 1 can be rewritten as The supervisor's Q/V functions use similar concepts, but with supervisor's states and coordinator's policies.
Then the coordinator's Q/V functions can be expressed as the expectation of supervisor's Q/V functions taken over the conditional distribution on FPSs given the FCS:

Proof of Theorem 4
We first determine the relationship between the space of FPS-based prescriptions Ω(Γ t ) and the space of ASPS-based prescriptions Ω( Λ t ). Consider a fixed h 0 t . Since the compression mappings A λ t ∈ Ω( Λ t ) can thus be thought of as a special element of Ω(Γ t ) that prescribes the same action for all the FPSs h 1:N t 's mapped to the same ASPS z 1:N t . Hence, we can construct an injective extension mapping from Ω( Λ t ) to Ω(Γ t ) in this sense.

Definition 12: For any
) (hence ψ t implicitly depends on ϑ t ), then choose the action according to λ t ( z 1:N t ). That is, Given the compression ϑ 1:N t , ψ t is well-defined. Under this circumstance and with an abuse of notation, γ t = ψ t ( λ t , h 0 t ) will be written as γ λt,h 0 t when the considered compression is clear from the context and will be referred to as the γ t extended from λ t under h 0 t .
The following proposition says that for any FCS one can find an ASPS-based prescription whose extension nearly achieves the same Q-value as an optimal prescription, up to a gap linear in the remaining timet. This implies that it nearly suffices to consider the class of prescriptions extended from ASPS-based prescriptions for DP purposes. Proposition 13: Assume the reward function R is uniformly bounded byR. For any h 0 which leads to Before proving this critical proposition we need a few intermediate results. The first key lemma says that with the same supervisor's state, the supervisor's Q-values for two different prescriptions will be the same as long as they prescribe the same action for the given private information.
Lemma 14: For any h 0 t ∈ Ω(H 0 t ) and h ∈ Ω(H 1:N t ), let γ 1 , γ 2 ∈ Ω(Γ t ) be two prescriptions that choose the same action on h, i.e. γ 1 (h) = γ 2 (h) = a; then Next we show that the supervisor's Q-values will be nearly the same for two different FPSs that map to the same ASPS and a prescription that prescribes the same action on these two FPSs.
Lemma 15: Assume R is uniformly bounded byR. For any h 0 t ∈ Ω(H 0 t ), let h 1 , h 2 ∈ Ω(H 1:N t ) be two FPSs under h 0 t that map to the same ASPS z ∈ Ω( Z 1:N t ), i.e. z = ϑ 1:N t (h 0 t , h 1 ) = ϑ 1:N t (h 0 t , h 2 ), and let γ ∈ Ω(Γ t ) be a prescription that chooses the same action on these two FPSs γ(h 1 ) = γ(h 2 ) = a. Then Using the above two lemmas, we show that the supervisor's V function will differ little for two supervisor's states with the same compression of private states. Corollary 16: Assume R is uniformly bounded byR. For any h 0 , and let γ * ∈ argmax γ Q t (h 0 t , γ) be an optimal prescription. Then Proof of Proposition 13: Given an optimal prescription γ * ∈ argmax γ Q t (h 0 t , γ), we will specifically construct a λ ∈ Ω( Λ t ) that serves for the claim. For each z ∈ Ω( Z 1:N t ), define to be the class of h's in Ω(H 1:N t ) that are compressed to z under the considered compression ϑ 1:N t . By the Axiom of Choice, for each z ∈ Ω( Z 1:N t ) there exists a representative of the class H z coming from arbitrary choice function, which we denote ash z . We then construct the λ by λ( z) = γ * (h z ); the corresponding extension in Ω(Γ t ) will be that is, the prescription first compresses the input FPS and finds the representative of the corresponding compression class, then it mimics what the optimal prescription would have done with the representative. For any h ∈ Ω(H 1:N t ), we have as the first term is bounded by (T −t)(ǫ p +TRδ p )/2+ǫ p /2 due to Corollary 16, the second term is 0 due to Lemma 14, and the third term is bounded by (T − t)(ǫ p + TRδ p )/2 + ǫ p /2 due to Lemma 15.
If it happens to be the case that h =h ϑ 1:N t (h 0 t ,h) , i.e. h is the representative, then the original term Taking the conditional expectation on h given h 0 t gives the claim.
Proof of Theorem 4: There are three main quantities: V t (h 0 t ) is the value obtained from executing optimal FPS-based prescriptions to the end, max λ∈Ω( Λt) Q t (h 0 t , γ λ,h 0 t ) is from executing the optimal ASPS-based prescription for step t and then optimal FPS-based prescriptions afterwards to the end, and V t (h 0 t ) is from executing optimal ASPS-based prescriptions to the end. Proposition 13 establishes that restricting to ASPS-based prescriptions in one step incurs a gap (between V t (h 0 t ) and max λ∈Ω( Λt) Q t (h 0 t , γ λ,h 0 t )) linear in T − t. Using an induction argument to accumulate this gap in every step from T back to t yields the gap (between V t (h 0 t ) and V t (h 0 t )) to be quadratic in T − t. See Appendix B for detailed derivations.

CONCLUSION
In this paper, we developed a general approximate state representation framework for MARL problems in a Dec-POMDP setting. We bounded the optimality gap in terms of the approximation error parameters and the number of remaining time steps. The theory provides guidance on designing deep-MARL algorithms, which has great potential in practical uses. Future directions include: exploring DL methods for applications using our framework, designing a representation for prescriptions, designing fully decentralized MARL schemes by adding communication, and extensions to general-sum games.

A.1 More Related Work
In Kara and Yuksel [2020] consider a special type of AIS -the N -memory, which contains the information from the last N steps. Here, the compression function is fixed but in contrast to Subramanian et al. [2020], the approximation error given each history need not be uniform. When the model is known, they provide conditions that bound the regret of N -memory policies (policies that depend on N -memory), and an algorithm that finds optimal policies within this class. The first algorithm to learn the optimal policies of POMDPs with sub-linear regret in an online setting is proposed in Jafarnia-Jahromi et al. [2021]. Using a posterior sampling-based scheme, the algorithm maintains the posterior distribution on the unknown parameters of the considered POMDP, and adopts the optimal policy with respect to a set of parameters sampled from the distribution in each episode. The posterior update in the algorithm, however, heavily relies on the knowledge of the observation kernel, which is usually unknown in RL settings.
State representation for control is studied extensively in the literature [Lesort et al., 2018]. Early work on predictive state representation (PSR) of POMDPs [Littman et al., 2001] only focuses on the encapsulation of the histories and does not explore its system prediction ability. The bisimulation relation clusters MDP states with similar rewards and transitions, and a bisimulation metric convexly combines the errors of the rewards and the transitions between two states [Ferns et al., 2011]. The difference of the value functions of two states can be upper-bounded by the metric. The causal state representation [Zhang et al., 2021a] for POMDPs clusters the histories in the space of AOHs that will produce the same future dynamics. Using the observation history as the state, the considered POMDP can be transformed into an MDP, so that the results from the bisimulation literature can be applied.

A.2 DP with BCS
Algorithm 4 Dynamic Programming with BCSs and FPS-based Prescriptions . Q t (π t , γ t )

A.3 DP with BCS and SPI
Algorithm 5 Dynamic Programming with BCSs and SPI-based Prescriptions B Omitted Analysis in Section 4.2 The following lemma shows that given the FPS, the actions the chosen prescription chooses for other FPSs does not affect the next step statistics.
Lemma 17: Let h 0 Proof: We will omit specifying the original random variables when their realizations are given in the proof.
Proof of Lemma 15: We preceed the proof by mathematical induction. The instantaneous part and the base case t = T follow trivially from (ASPS2) For the continuation part, we have and the same equality holds for h 2 . Therefore, For the first two terms, we have 1 , 2 ≤ 2 V t+1 ∞ · δ p /8 ≤ TRδ p /4 by (ASPS3). Note that the above equation follows if K(·, ·) is the total variation distance. If it is instead the Wasserstein metric, then the total variation distance will still be bounded by δ p min x,y∈Ω(O 0:N t+1 ),x =y x − y ; we can redefine this value as δ p so that the total variation distance is still bounded by δ p . = (T − t − 1)(ǫ p + TRδ p )/2 + ǫ p /2. Combining the three terms plus the instantaneous part, it follows that Q S by symmetry C Omitted Analysis in Section 3.2 Proposition 18: Assume the reward function R is uniformly bounded byR. Let h 0 1 , h 0 2 ∈ Ω(H 0 t ) be two FCSs. If z 0 = ϑ 0 t (h 0 1 ) = ϑ 0 t (h 0 2 ), then for any λ ∈ Ω( Λ t ), Proof: We proceed the proof again by mathematical induction. The instantaneous part as well as the base case t = T trivially follow from (ASCS2) ( (ASCS2)) For the continuation part in the induction step, we have For the first two terms, we have 1 , 2 ≤ 2 V t+1 ∞ · δ c /2 ≤ TRδ c by (ASCS3).
The last term can thus be bounded by 3 ≤