
## 5. Mdp S

Calculating the finite-horizon performance of stationary policies is in GapL (Mundhenk
), whi is a subclass of the class of polynomial time computable functions. The et al.,
stationary policy existence problem for MDPs is shown to be P-hard by Papadimitriou and Tsitsiklis (1986), from which it follows that finding an optimal stationary policy for MDPs is P-hard. So it is not surprising that approximating the optimal policy is also P-hard. We include the following theorem because it allows us to present one aspect of the reduction used in the proof of Theorem 5. in isolation.

Theorem 5.1  The problem of  -additive approximating the optimal stationary policy for MDPs is P-hard.

The proof shows this for the case of non-negative rewards; the unrestricted case follows immediately. By Proposition . , this shows that finding a multiplicative approximation scheme for this problem is also P-hard.

Proof  Consider the P-complete problem CVP: given a Boolean circuit    and input  , is
( ) = 1? A Boolean circuit and its input can be seen as a directed acyclic graph. Each node represents a gate, and every gate has one of the types AND, OR, NOT,   or 1. The gates of type or 1 are the input gates, which represent the bits of the fixed input to the circuit. Input gates have indegree  . All NOT gates have indegree 1, and all AND and OR
gates have indegree . There is one gate having outdegree . This gate is called the output gate, from which the result of the computation of circuit —on input —can be read.

From such a circuit   , an MDP
can be constructed as follows. Because the basic idea of the construction is very similar to one shown in (Papadimitriou & Tsitsiklis, 1986),
we leave out technical details. As an initial simplifying assumption, assume that the circuit has no NOT gates. Each gate of the circuit becomes a state of the MDP. The start state is is the output gate. Reverse all edges of the circuit. Hence, a transition in leads from a to one of its predecessors. A transition from an OR gate depends on the action gate in and is deterministic. On action   its left predecessor is reached, and on action 1 its right predecessor is reached. A transition from an AND gate is probabilistic and does not depend on the action. With probability - the left predecessor is reaed, and with probability –
the right predecessor is reached.

Continue considering a circuit without NOT gates. If an input gate with value 1 is reached, a large positive reward is gained, and if an input gate with value is reached, no reward is gained, which makes the total expected reward noticeably smaller than otherwise.

If ( ) = 1, then the actions can be chosen at the OR gates so that every tra ectory reaches an input gate with value 1; if this condition holds, then it must be that   (  ) = 1. Hence, the MDP has a large positive value if and only if   (  ) = 1.

If the circuit has NOT gates, we need to remember the parity of the number of NOT
gates on each tra ectory. If the parity is even, everything goes as described above. If the parity is odd, then the role of AND and OR gates is switched, and the role of   and 1 gates is switched. If a NOT gate is reached, the parity bit is   ipped. For every gate in the circuit, we now take two MDP states: one for even and one for odd parity. Hence, if is the set of gates in , the MDP has states 1 . The state transition function is