Ol(s, (a1) , (w1)) = O(s, a1, w1)
B' = U 7 = 1 ( Ω) 3
(i.e., observation sequences of length no more than the finite horizon)

$R^{\prime}_{A}(s,\langle a_{1}\rangle)=R(s,a_{1})$
$${\boldsymbol{\ell}}\ {\boldsymbol{\ell}}$$
R ( ) = 0 This COM-MTDP satisfies our assumption of free communication. The POMDP assumes perfect recall, so we use the state estimator functions from Equations 5 and 6. Just as in the proof of Theorem 1, we can show that there exists a policy with expected utility greater than K for this COM-MTDP if and only if there exists one for the POMDP. The decision problem for the POMDP is known to be PSPACE-hard (Papadimitriou & Tsitsiklis, 1987),
so the COM-MTDP problem under free communication must be PSPACE-hard.

To show that the problem is in PSPACE, we take a COM-MTDP under free communication and reduce it to a single-agent POMDP. In particular, if we are given a COM-MTDP,
(S, Ag, Zg, P,  Qg, Og, Bg, R), we can construct a single-agent POMDP, (S', A', P', S', O',
R'), as follows:
S' = S'
A' = Ag Pl(s, a, s) = P(s, a, s')
C' = na 0'(s,a,ω) = Oα(s,a,ω)
R ′ (s, a) = R A (s, a)
From Theorem 2, we need to consider only the complete-communication policy for the COM-MTDP and this policy has a zero reward. Therefore, the decision problem for the COM-MTDP is simply to find a domain-level policy that produces an expected reward exceeding K .  Given full communication, the state estimator functions for the COM-MTDP (as shown in the proof of Theorem 2) reduce to Equation 10.  A policy for our POMDP
specifies an action for each and every history of observations: π ′ : U f − 1 ( l ′ ) j → A ′ . The history of observations for the single-agent POMDP corresponds to the belief states of our COM-MTDP under full communication. Therefore, we can translate a POMDP-policy, π ′ , into an equivalent domain-level policy for the COM-MTDP:

$$\pi_{A}\left(\langle\mathbf{\omega}_{0},\mathbf{\omega}_{1},\ldots,\mathbf{\omega}_{t}\rangle\right)\equiv\pi^{\prime}\left(\langle\mathbf{\omega}_{0},\mathbf{\omega}_{1},\ldots,\mathbf{\omega}_{t}\rangle\right)$$
$\left(1\,2\right)$ . 
A team following π A will perform the exact same domain-level actions as a single agent following π ′ . Thus, there exists a policy with expected utility greater than K for the COM-
MTDP if and only if there exists one for the POMDP. The decision problem for a POMDP
is known to be in PSPACE (Papadimitriou & Tsitsiklis, 1987), so the COM-MTDP problem
(under free communication) must be in PSPACE as well. □