out of the engineering tradition (see, for example, Tsitsiklis and Van Roy's (1996) article on feature-based methods) which depends on empirical evidence to evaluate algorithms. While there are obvious drawbacks to this approach, our work argues that this may be the most appropriate way to verify the quality of an approximation algorithm, at least if one wants to do so in reasonable time.

The same problems that plague approximation algorithms for uncompressed representations carry over to the succinct representations, and the compression introduces additional complexity. For example, if there is no computable approximation of the optimal policy in the uncompressed case, then compression will not change this. However, it is easy to find the optimal policy for an infinite-horizon fully observable MDP (Bellman, 1957), yet EXP-
hard (provably harder than polynomial time) to find approximately optimal policies (in time measured in the size of the input) if the input is represented succinctly (see Section 5).

Note that there are two interpretations to finding an approximation: finding a policy with value close to that of the optimal policy, or simply calculating a value that is close to the optimal value. If we can do the former and can evaluate policies, then we can certainly do the latter. Therefore, we sometimes show that the latter cannot be done, or cannot be done in time polynomial in the size of the input (unless something unlikely is true).

The complexity class PSPACE consists of those languages recognizable by a Turing machine that uses only  ( ) memory for some polynomial  , where is the size of the input. Because each time step uses at most one unit of memory, P
P SPA CE,though we do not know whether that is a proper inclusion or an equality. Because, given a limit on the amount of memory used, there are only exponentially many configurations of that to memory possible with a fixed finite alphabet, PSPACE
EXP. It is not known whether this is a proper inclusion or an equality either, although it is known that P = EXP. Thus, a PSPACE-hardness result says that the problem is apparently not tractable, but an EXP- hardness result says that the problem is certainly not tractable.

Researchers also consider problems that are P-complete (under logspace or other highly restricted reductions). For example, the policy existence problem for infinite-horizon MDPs is P-complete (Papadimitriou & Tsitsiklis, 1987). This is useful information, because it is generally thought that P-complete problems are not susceptible to significant speed-up via parallelization. (For a more thorough discussion of P-completeness, see Greenlaw, Hoover,
& Ruzzo, 1995.)
PSPACE, so P = PSPACE would imply P = NP. Thus, We also know that NP
any argument or belief that P = NP implies that P = PSPACE. (For elaborations of this complexity theory primer, see any complexity theory text, such as Papadimitriou, 1994.)
In this paper, we show that there is a necessary trade-off between running time guarantees and performance guarantees for any general POMDP approximation algorithm uless P = NP or P = PSPACE. (Table 1 gives an overview of our results.) Note that (assuming P = NP or P = PSPACE) this tells us that there is no algorithm that runs in time polynomial in the size of the representation of the POMDP that finds a policy that is close to optimal for every instance. It does not say that fast algorithms will produce far-from-optimal values for all POMDPs; there are many instances where the algorithms already in use or being developed will be both fast and close. We simply can't guarantee that the algorithms will always find a close-to-optimal policy quickly.