Hence, it has at most 6 arguments and can be described by a small table. This holds for all uents of s. Finally, the function c for s ust copies the value of f. into f. Hence, we can construct a MDP in  TBN representation similar to the MDP in the proof from of Theorem 5.1. Next, we specify the rewards of this MDP. The reward is   Isl+k+1 if any action is taken on a state representing an input gate with value 1 and parity –, or with value and parity 1. Otherwise, the reward equals . This reward function can be represented outputs the  th bit of the reward obtained in state by by the on action . (Since it requires | S | k bits to represent the reward, can be represented using only + + 1 bits.)
If ( ) = 1, then there is a choice of actions for each state that gives reward    Isl+k+i  on every tra ectory, similar to the proof of Theorem 5.1. However, if   (  ) =  , any policy has at least one tra ectory that receives a reward. Now, there are at most Isl tra ectories, between possible values.  As and therefore there is a gap of at least   ISI+k+!    ISI
above, we conclude that any -additive approximation to the factored MDP problem gives a decision algorithm for the succinct circuit value problem. Therefore, the lower bound of EXP-hardness for the factored MDP value problem holds for this approximation problem as well.

The following structured representation is more general than the representations more common to the AI/planning community. We say that an MDP has a succinct representation, or is a succinct MDP, if there are Boolean circuits     and 
' ) produces the  th bit of the transition probability  (
reward (    ). Similar to the proof of Theorem 5. , we can also prove nonapproximability of MDP values for succinctly represented MDPs.

Theorem 5.3  The problem of  -additive approximating the optimal stationary policy for a succinctly represented MDP is EXP-hard.

## 6.  Non-Approximability For Infinite-Horizon Pomdps

The discounted value of an infinite-horizon POMDP is the maximum total discounted performance. When we discuss the policy existence problem or the average case performance in the infinite horizon, it is necessary to specify the reward criterion. We generalize the value function as follows.

The
-value vala. 8 (  ) of    is   's maximal  -performance under any policy of type   , i.e. val α,β(   ) = max πε  α perf β( Note that a time-dependent or history-dependent infinite-horizon policy for a POMDP is not necessarily finitely representable. For fully-observable MDPs, it turned out (see e.g. Puterman, 1994) that the discounted or average value is the performance of a stationary policy.

This means that no history-dependent policy performs better than the best stationary one.

As an important consequence, an optimal policy is finitely representable. For POMDPs, this does not hold. Madani et al. (1999) showed that the time-dependent infinite-horizon policy-existence problem for POMDPs is not decidable under average performance or under total discounted performance. In contrast, we show that the same problem for stationary policies is NP-complete.