by the last step.  Consider only reachable states of the POMDP, and let   be the lowest nonzero transition probability to one of these states, the horizon, and the smallest nnnnero reward, and set = h . Then h is a lower bound on the probability of actually reaching any particular state after steps (if this probability is nonzero), in particular a state with reward .  If the reward metric is discounted, then let = (    ) h , where is the discount factor.

Now consider the infinite-horizon under a stationary policy.  This induces a Markov process, and the policy has nonzero reward if there is a nonzero probability path to a reward node, i.e., a state from which there is a positive-reward action possible. This is true if and only if there is a nonzero-probability simple path (visiting each node at most once)
to a reward node. Such a path accrues reward at least = (   ) I S I  for stationary policies.

Since stationary policies have values bounded by the time-dependent and history-dependent values for infinite-horizon POMDPs, this lower bound for the stationary value of the POMDP is also a lower bound for other policies.

Finally, note that if the value of a POMDP with non-negative rewards is  , then a
-additive approximation cannot return a positive value.  To determine whether there is a policy with reward greater than  for a given POMDP, compute   and then set   such that
, i.e., 
POMDP has positive value if and only if the approximation returns a positive value.

□
Note that this does not contradict the undecidability result of Madani et al. (1999). The problem that they proved undecidable is whether a POMDP with nonpositive rewards has a history-dependent or time-dependent value of  . We're asking whether it has value in the non-negative reward case; answering this question (even if we multiply the rewards by 1) does not answer their question.

Corollary 3.2 For POMDPs with flat representations and non-negative rewards, the PO-
MDP value problem under finite-horizon or infinite-horizon total discounted reward is additive approximable if and only if there exists a PTAS for that POMDP value problem.

Note that the corollary depends only on Facts (1) and ( ) from the proof of Theorem .1.

Thus, any optimization problem with those properties will have a -additive approximation if and only if it has a PTAS.

Proof  Let   = val a (   ), and let    be a polynomial-time  -additive approximation algorithm. First, the PTAS computes   as in Theorem  .1 and checks whether    =   . If so, it outputs .  Otherwise, given , it chooses   such that
(1)
holds. Let = (    ). (Note that (   ) is the approximation to the value of     found by running algorithm .) Then is an -approximation to i so is an -approximation to Suppose, instead, that we have a PTAS for optimal policies for this problem.  Let
(   ) be an algorithm that demonstrates this. Let   = vala(  ), and  (
5) =
Thus
". If = then = and we can stop. Else we choose an such that
, giving
(1 time computable in       (since   is the output of   (
k, and 5)), we can choose run ( T ). This gives a -additive approximation.

□