Corollary 4.5 The following are equivalent.

1. There exists a polynomial-time algorithm that for a given POMDP    computes a stationary policy under which has performance greater than or equal to the average

stationary performance of 2. P = NP.
Thus, even calculating a policy whose performance is above average is likely to be infeasible.

We now turn to time-dependent policies. The time-dependent policy existence problem for POMDPs is known to be NP-complete, as is the stationary one. Theorem 4.6 (Mundhenk et al., 2000) The time-dependent policy existence problem for unobservable MDPs is NP-complete.

Papadimitriou and Tsitsiklis (1987) proved a theorem similar to Theorem 4.6.  Their MDPs had only non-positive rewards, and their formulation of the decision problem was whether there is a policy with performance . The proof by Mundhenk et al.,
, like theirs, uses a reduction from 3SAT. We modify this reduction to show that an optimal time-dependent policy is hard to approximate even for unobservable MDPs.

Theorem 4.7 Let 1. Any optimal time-dependent policy for unobservable MDPs with non-negative rewards is  -approximable if and only if P = NP.

Proof  We give a reduction from 3SAT with the following properties.  For a formula with    clauses we show how to construct an unobservable MDP
stisfiable, and with value (1 ) if is not satisfiable. Therefore, an  -approximation could be used to distinguish between satisfiable and unsatisfiable formulas in polynomial time.

For formula   , we first show how to construct an unobservable    (  ) from which will be constructed.  (The formal presentation appears in Appendix B.)     (  ) simulates the following strategy.  At the first step, one of the    clauses is chosen uniformly at random with probability =. At step +1, the assignment of variable is determined. Because the process is unobservable, it is guaranteed that each variable gets the same assignment in all clauses, because its value is determined in the same step. If a clause is satisfied by this assignment, a final state will be reached. If not, an error state will be reached.

Now, construct m² of           such that the initial state of reward 1 is gained if the final state of m 2 is reached. The error states of all the m is are identified as a unique sink state To illustrate the construction, in Figure 1 we give an example POMDP consisting of a chain of 4 copies of    (  ) obtained for the formula    = (
The dashed arrows indicate a transition with probability –. The dotted (resp. solid) arrows are probability 1 transitions on action   (resp. 1). The actions correspond to assignments to the variables.

If is satisfiable, then a time-dependent policy simulating      repetitions of any satisfying assignment has performance 1. If is not satisfiable, then under any assignment at