We would like to thank Daphne  oller and several anonymous referees for catching errors in earlier versions of this paper.

## Appendix A. Proof Of Theorem 4.1

We the reduction from (Mundhenk et al.,       ). Let   (
n) be an instance of 3SAT with variables v j ) for j = j = j = j . We say that variable j appears in j with signum (resp. 1) if i (resp.   is a literal in   j.

From    we construct a POMDP    (  ) = (

$$\begin{array}{l l l l l}{\mathbf{P}}&{\mathbf{\Phi}}&{\mathbf{\Phi}}&{\mathbf{\Phi}}&{\mathbf{\Phi}}\\ {\mathbf{\Phi}}&{\mathbf{\Phi}}&{\mathbf{\Phi}}&{\mathbf{\Phi}}&{\mathbf{\Phi}}\end{array}$$
) 1 = ( (1 1) 1) 1 ) ) ' = ( (1 +1) +1) if = ( ( ( 1 1 and v i,j appears in j with signum if )  ) '=   1 = ( ( 1 and vi,m appears in m with signum if = ( ( ) ) ' = ( ( +1 ) ) 1 1 and  v i,j  appears in  j with signum 1 if = ( ( 1 ) ) ' = and  if = ' = 1 or = ' = other wise l ( if . = 1 if ( ) = 1 l if ( ) ) l other wise if = l
Note that all transitions in   (  ) are deterministic, and every tra ectory has value   or 1. There is a correspondence between policies for   ( ) and assignments of values to the variables of  , such that policies under which   (  ) has value 1 correspond to satisfying assignments for and vice versa.

## Appendix B. Proof Of Theorem 4.6

Again, we present the reduction from (Mundhenk et al.,      ). Let    be a formula with n and    clauses m. This time, we define the unobservable MDP
variables
( ) = (
) where

$$\begin{array}{l l l l l}{{=}}&{{}}&{{(}}&{{)}}&{{1}}&{{}}\\ {{=}}&{{}}&{{}}&{{1}}\end{array}$$

i 1