Note that all policies have expected reward of either 1 or . Immediately we get the nonapproximability result for POMDPs, even if all tra ectories have non-negative performance.

1. An optimal stationary policy for POMDPs with non-negative Theorem 4.2  Let rewards is  -approximable if and only if P = NP.

Proof  The stationary value of a POMDP can be calculated in polynomial time by a binary search using an oracle for the stationary policy existence problem for POMDPs.

The number of bits to be calculated is polynomial in the size of nowing the value, we can try to fix an action for an observation. If the modified POMDP still achieves the value calculated before, we can continue with the next observation, until a stationary policy is found which has the optimal performance. This algorithm runs in polynomial time with an oracle solving the stationary policy existence problem for POMDPs. Since the oracle is in NP, by Theorem 4.1, the algorithm runs in polynomial time if P = NP.

Now, assume that - is a polynomial-time algorithm that -approximates the optimal 1. We show that this implies that P = NP by stationary policy for some   with showing how to solve the NP-complete problem 3SAT. As in the proof of Theorem 4.1, given an instance of 3SAT, we construct a POMDP (). The only change to the reward function of the POMDP constructed in the proof of Theorem 4.1 is to make it a POMDP with positive performances. Now reward 1 is obtained if state    is reached, and reward
__
() has value Assume that policy is the output of the -approximation algorithm If is satisfiable, 1. Because the performance of every policy for then perf(  ( )  )
(1
) = =
( ) is either 1 if is not satisfiable, or - if is satisfiable, it follows that has performance 1 if and only if is satisfiable. So, in order to decide 3SAT, we can construct ( ), run the approximation algorithm on it, take its output and calculate perf(  ( ) ). That output shows whether   is in 3SAT. All these steps are polynomialtime bounded computations. It follows that 3SAT is in P, and hence P = NP.

□
Of course, the same nonapproximability result holds for POMDPs with positive and ngative rewards. Corollary 4.3  Let 1. Any optimal stationary policy for POMDPs is -approximable if and only if P = NP.

Using the same proof technique as above, we can show that the value is nonapproximable, too.

Corollary 4.4  Let only if P = NP.

1. The stationary value for POMDPs is -approximable if and A similar argument can be used to show that a policy with performance at least the average of all performances for a POMDP cannot be computed in polynomial time, unless P = NP. Note that in the proof of Theorem 4.1, the only performance greater than or equal to the average of all performances is that of an optimal policy.