A polynomial-time algorithm computing such a nearly optimal policy is called an  -
approximation (for            1), where indicates the quality of the approximation in the following way. Let be a polynomial-time algorithm which for every POMDP computes an   -policy   (   ). Notice that perf(     (   ))    vala(   ) for every    . The algorithm is called an -approximation if for every POMDP

$$\left|{\frac{\operatorname{val}_{\alpha}{\bigl(}\quad{\bigr)}\quad p e r f{\bigl(}\quad{\bigl(}\quad{\bigr)}{\bigr)}}{\operatorname{val}_{\alpha}{\bigl(}\quad{\bigr)}}}\right|$$

(See, e.g., Papadimitriou, 1994 for more detailed definitions.) Approximability distinguishes NP-complete problems: There are problems which are  -approximable for all   , for certain  , or for no   (unless P = NP). Note that this definition of  -approximation requires that val a (  )    . If a policy with positive performance exists, than every approximation algorithm yields such a policy, because a policy with performance or smaller cannot approximate a policy with positive performance. Hence, any approximation straightforwardly solves the decision problem.

An approximation seme yields an  -approximation for arbitrary
. If there is a polynomial-time algorithm that on input POMDP and and autputs an -approximation of the value, in time polynomial in the size of then we say the problem has a Polynomial-
Time Approximation Scheme (PTAS). If the algorithm runs in time polynomial in the size and = , the scheme is a Fully Polynomial-Time Approximation Scheme (FPTAS). All of of the PTASs constructed here are FPTASs; we state the theorems in terms of PTASs because that gives stronger results in some cases, and because we do not explicitly analyze the complexity in terms of –.

If there is a polynomial-time algorithm that outputs an approximation, to the value
, then we say that the problem has a -additive
( = vala(  )) with of approximation algorithm.

In the context of POMDPs, existence of a  -additive approximation algorithm and a PTAS are often equivalent. This might seem surprising to readers who are more familiar with reward criteria that have fixed upper and lower bounds on the performance of a solution, for example, the probability of reaching a goal state. In these cases, the fixed bounds on performance will give different results. However, we are addressing the case where there is no a priori upper bound on the performance of policies, even though there are computable upper bounds on the performance of a policy for each instance.

Theorem 3.1 For POMDPs with non-negative rewards and flat representations under finite-horizon total or total discounted, and infinite-horizon total discounted reward metrics, if there exists a -additive approximation, then we can determine in polynomial time whether there is a policy with performance greater than 0.

The Proof  The theorem follows from two facts: (1) given a POMDP
with value   , we can construct another POMDP       with value        ust by multiplying all rewards in the former POMDP by  ¡ ( ) under these reward metrics we can find a lower bound on    if it is not The computation of the lower bound, an the value of depends on the reward metric.

Because there are no negative rewards, in order for the expected reward to be positive in the finite-horizon case, an action with positive reward must be taken with nonzero probability