\documentclass[11pt,twoside]{article}

\usepackage{latexsym} %fullpage}

\usepackage{apacite}
\usepackage{epsfig}
\usepackage{xspace}
\usepackage{pictex}
\usepackage{jair}    

\newcommand{\polytime}{po\-ly\-nomial-time\xspace}


\usepackage[dvips]{rotating}
 
%\input{nap-defis}

%\textheight 247mm
%\advance\textheight by -\footskip
%     
%\oddsidemargin 0pt
%\evensidemargin \oddsidemargin
%\marginparwidth 0pt
%     
%\textwidth 160mm
%\advance\textwidth by 0.375in
%%          
%% For users of A4 paper: The above values are suited for american 8.5x11in
%% paper. If your output driver performs a conversion for A4 paper, keep
%% those values. If your output driver conforms to the TeX standard (1in/1in),
%% then you should add the following commands to center the text on A4 paper:
%     
%\advance\hoffset by -5mm  % A4 is narrower.
%\advance\hoffset by -0.05in 
%\advance\voffset by  8mm  % A4 is taller.
%     
%\setlength{\itemsep}{-\parsep}
%\setlength{\itemsep}{0pt}
%\renewcommand{\topfraction}{.9}
%\renewcommand{\textfraction}{.1}
%\setlength{\parskip}{\smallskipamount}

%%%%%%%%%%%     Definitions and Theorems
\newtheorem{theorem}{Theorem}[section]
\newtheorem{defi}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{coro}[theorem]{Corollary}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}{Claim}
\newcommand{\qedsyb}{\ensuremath{\Box}}
\newcommand{\qed}{\hspace*{\fill} \qedsyb}
\newenvironment{proof}{\noindent{\bf Proof }}{\qed \vskip 1ex} 
\newenvironment{proofofclaim}{\noindent{\bf Proof }}{\qedsyb \vskip 1ex}
\newtheorem{fact}[theorem]{Fact}

%%%%%%%%%%%     Special symbols

\newcommand{\fptred}{\leq^{fpt}_m}
\newcommand{\poly}{{\it poly}}

\newcommand{\red}[2]{\leq_{#1}^{#2}}
\newcommand{\redp}[1]{\red{#1}{p}}
\newcommand{\redT}[1]{\red{#1}{T}}
\newcommand{\mred}{\redp{m}}
\newcommand{\npmred}{\red{m}{np}}
\newcommand{\qlred}{\red{m}{QL}}
%\newcommand{\qed}{\hspace*{\fill} $\Box$}
\newcommand{\qedd}{\hspace*{2ex} $\Box$}
\newcommand{\mi}{\mbox{-}}
\newcommand{\cA}{{\cal A}}
\newcommand{\cC}{{\cal C}}
\newcommand{\cN}{{\cal N}}
\newcommand{\cR}{{\cal R}}
\newcommand{\reals}{\mathbf{R}}
\newcommand{\integers}{\mathbf{I}}
\newcommand{\cS}{{\cal S}}
\newcommand{\cO}{{\cal O}}

\newcommand{\nat}{\mathbf{N}}
\newcommand{\natn}{\mathbf{N_0}}

\newcommand{\code}[1]{\langle #1\rangle}
\newcommand{\tuple}[1]{\code{#1}}
\newcommand{\pair}[1]{\langle #1 \rangle}


%%%%%%%%%%  Complexity classes

\newcommand{\classfont}{\rm }
\newcommand{\p}{{\classfont P}}
\newcommand{\FP}{{\classfont FP}}
\newcommand{\np}{{\classfont NP}}
\newcommand{\NP}{{\classfont NP}}
\newcommand{\GapP}{{\classfont GapP}}
\newcommand{\PP}{{\classfont PP}}
\newcommand{\PH}{{\classfont PH}}
\newcommand{\logspace}{{\classfont L}}
\newcommand{\NL}{{\classfont NL}}
\newcommand{\sharpL}{{\classfont \#L}}
\newcommand{\sharpP}{{\classfont \#P}}
\newcommand{\GapL}{{\classfont GapL}}
\newcommand{\PL}{{\classfont PL}}
\newcommand{\MAXNP}{{\classfont MAXNP}}
\newcommand{\E}{{\classfont E}}
\newcommand{\NE}{{\classfont NE}}
\newcommand{\EXP}{{\classfont EXP}}
\newcommand{\NEXP}{{\classfont NEXP}}
\newcommand{\R}{{\classfont R}}
\newcommand{\NR}{{\classfont NR}}
\newcommand{\fp}{{\classfont FP}}
\newcommand{\NC}{{\classfont NC}}
\newcommand{\NNC}{{\classfont NNC}}
\newcommand{\SPACE}{{\classfont SPACE}}
\newcommand{\PSPACE}{{\classfont PSPACE}}
\newcommand{\PPSPACE}{{\classfont PPSPACE}}
\newcommand{\sharpPSPACE}{{\classfont \#PSPACE}}
\newcommand{\FPSPACE}{{\classfont FPSPACE}}
\newcommand{\NPSPACE}{{\classfont NPSPACE}}
\newcommand{\EXPSPACE}{{\classfont EXPSPACE}}
\newcommand{\EXPTIME}{{\classfont EXPTIME}}
\newcommand{\TIME}{{\classfont DTIME}}
\newcommand{\Time}{{\classfont DTIME}}
\newcommand{\NTIME}{{\classfont NTIME}}
\newcommand{\ntime}{{\classfont NTIME}}
\newcommand{\NONDETTIME}{{\classfont NONDET\mbox{-}TIME}}
\newcommand{\Pohelp}{\p_{1{\classfont\mbox{-}help}}}
\newcommand{\gc}{{\classfont GC}}
\newcommand{\logsnp}{{\classfont LOGSNP}}
\newcommand{\lognp}{{\classfont LOGNP}}
\newcommand{\maxNP}{\mbox{\classfont MAXNP}}
\newcommand{\maxSNP}{\mbox{\classfont MAXSNP}}
\newcommand{\SBH}{{\classfont SBH}}
\newcommand{\ora}[1]{$^{{#1}}$}          
\newcommand{\NPPP}{\NP\ora{\PP}}
\newcommand{\ABPP}{{\classfont ABPP}}
\newcommand{\IP}{{\classfont IP}}
\newcommand{\fpt}{{\classfont FPT}}
\newcommand{\qnp}[2]{{\classfont N}^{#1}\!\p_{#2}}
\newcommand{\FPT}{{\classfont FPT}}
\newcommand{\GC}{{\classfont GC}}
\newcommand{\sGC}{{\classfont sGC}}
\newcommand{\pGC}{{\classfont pGC}}

\newcommand{\co}{{\classfont co}}

\newcommand{\tally}{{\classfont TALLY}}
\newcommand{\TALLY}{{\classfont TALLY}}

\newcommand{\peqnp}{\p\mathrel{=?}\NP}


%%%%%%%%%  Languages

\newcommand{\langfont}{\sc}       % Use inside \mbox-es
\newcommand{\scriptlangfont}{\rm} % Use in sub- or superscripts

\newcommand{\Dtime}{\TIME}
\newcommand{\Ntime}{\NTIME}
\newcommand{\SAT}{\mbox{\langfont Sat}}
\newcommand{\MAJSAT}{\mbox{\langfont Majsat}}
\newcommand{\THREESAT}{\mbox{\langfont 3Sat}}
\newcommand{\sTHREESAT}{s\mbox{\langfont 3Sat}}
\newcommand{\HAMCIRCUIT}{\mbox{\langfont Hamiltonian-circuit}}
\newcommand{\CSAT}{\mbox{\langfont Csat}}
\newcommand{\QBF}{\mbox{\langfont Qsat}}
\newcommand{\SSAT}{\mbox{\langfont Ssat}}
\newcommand{\wcs}{\mbox{\langfont Wcs}}
\newcommand{\circsat}[1]{\mbox{\langfont CSat$(#1)$}}
\newcommand{\shortsat}[1]{\mbox{\langfont ShortSat$(#1)$}}
\newcommand{\shortsatord}[1]%
{\mbox{\langfont ShortSat$_{\scriptlangfont ord}(#1)$}}
\newcommand{\vc}[1]{\mbox{\langfont Vertex\mbox{-}Cover$(#1)$}}
\newcommand{\unarygen}{\mbox{\langfont UnaryGen}}
\newcommand{\unarygenord}{\mbox{\langfont UnaryGen$_{\scriptlangfont ord}$}}
\newcommand{\pcircsat}{\circsat{*}}
\newcommand{\pshortsat}{\shortsat{*}}
\newcommand{\pshortsatord}{\shortsatord{*}}
\newcommand{\sfsat}[1]{\mbox{\langfont SF-Sat$(#1)$}}
\newcommand{\sfthreecol}[1]{\mbox{\langfont SF-3Col$(#1)$}}
\newcommand{\sfhamcycle}[1]{\mbox{\langfont SF-Ham$(#1)$}}
\newcommand{\SATk}{\mbox{\langfont Sat$_k$}}
\newcommand{\MAXTHREESAT}{\mbox{\langfont Max3Sat}}
\newcommand{\MAXQSAT}{\mbox{\langfont MaxQ3Sat}}

\newcommand{\OPT}{\mbox{\langfont Opt}}


\newcommand{\plural}[1]{{#1}s\xspace}

\newcommand{\MDP}{MDP\xspace}
\newcommand{\MDPs}{\plural{\MDP}}
\newcommand{\POMDP}{PO\-MDP\xspace}
\newcommand{\POMDPs}{\plural{\POMDP}}
\newcommand{\UMDP}{UMDP\xspace}
\newcommand{\UMDPs}{\plural{\UMDP}}

\newcommand{\sMDP}{sMDP\xspace}
\newcommand{\slMDP}{compressed\xspace\MDP}

%\newcommand{\MDPP}{\mbox{\langfont Mdpp}}
%\newcommand{\sMDPP}{s\mbox{\langfont Mdpp}}
%\newcommand{\slMDPP}{s_{\log}\mbox{\langfont Mdpp}}
%\newcommand{\dpMDPP}{dpo\mbox{\langfont Mdpp}}
%\newcommand{\dpoMDPP}{dpo\mbox{\langfont Mdpp}}
%\newcommand{\sdpMDPP}{dpo\mbox{\langfont Mdpp}}
\newcommand{\CVP}{\mbox{\langfont Cvp}}
\newcommand{\sCVP}{s\mbox{\langfont Cvp}}
\newcommand{\REACH}{\mbox{\langfont Reachability}}

\newcommand{\lneg}{\neg}

%%%%%%%%%%  Environment for programs %%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\For}{{\bf for\ }}
\newcommand{\To}{{\bf to\ }}
\newcommand{\Do}{{\bf do\ }}
\newcommand{\Begin}{{\bf begin\ }}
\newcommand{\End}{{\bf end\ }}
\newcommand{\If}{{\bf if\ }}
\newcommand{\Then}{{\bf then\ }}
\newcommand{\Else}{{\bf else\ }}
\newcommand{\While}{{\bf while\ }}
\newcommand{\Repeat}{{\bf repeat\ }}
\newcommand{\Until}{{\bf until\ }}
%\newcommand{\And}{{\bf and\ }}
\newcommand{\Or}{{\bf or\ }}
\newcommand{\Input}{{\bf input\ }}
\newcommand{\Output}{{\bf output\ }}
\newcommand{\Halt}{{\bf halt\ }}
\newcommand{\Return}{{\bf return\ }}
\newcommand{\Guess}{{\bf guess\ }}
\newcommand{\Accept}{{\it accept\ }}
\newcommand{\Reject}{{\it reject\ }}
\newcommand{\Space}[1]{\mbox{}\hspace{#1ex}}

\newcounter{einrueck}
\newcommand{\einrueckstart}{\setcounter{einrueck}{0}}
\newcommand{\spa}{\Space{\theeinrueck}}
\newcommand{\vor}{\addtocounter{einrueck}{2}
\spa}
\newcommand{\rueck}{\addtocounter{einrueck}{-2}
\spa}
\newcommand{\rueckk}{\addtocounter{einrueck}{-4}}
\newcommand{\vors}[1]{\addtocounter{einrueck}{#1}}
\newcommand{\ruecks}[1]{\addtocounter{einrueck}{-#1}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\newcommand{\perf}{{\rm perf}}
\newcommand{\perf}{\mathit{perf}}
\newcommand{\perfs}{\perf\!_s}
\newcommand{\perfl}{\perf\!_l}
\newcommand{\perff}{\perf\!_f}

\newcommand{\ave}{{\rm ave}}
\newcommand{\prob}{{\rm prob}}
\newcommand{\rew}{r}
\newcommand{\val}{{\rm val}}
\newcommand{\rewa}{{\rm rew}}
\newcommand{\med}{{\rm med}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% formating %%%%  CDL 8/4/1998
%%%%%%%%%%%%%%%%%
\newcommand{\fofbox}[1]{\mbox{\makebox[3.8em][c]{$#1$}}} %cdl 8/4/1998


%%  POMDP states
\newcommand{\statesfont}[1]{\mathsf{#1}}
\newcommand{\send}{s_{\mathit{end}}}
\newcommand{\true}{\statesfont{t}}
\newcommand{\false}{\statesfont{f}}

\newcommand{\linie}{\mbox{}\hrulefill\mbox{}}
\newcommand{\mdpsfont}[1]{#1}
\newcommand{\mA}{\mdpsfont{A}}
\newcommand{\mC}{\mdpsfont{C}}
\newcommand{\mM}{\mdpsfont{M}}
\title{Nonapproximability Results for \\Partially Observable 
Markov Decision Processes}
%\title{Most Markov Decision Process Problems Aren't Approximable}

%%%\jairheading{14}{2001}{53-83}{12/99}{3/01}

\jairheading{14}{2001}{83-113}{12/99}{3/01}

\ShortHeadings{Nonapproximability Results for POMDPs}{Lusena, Goldsmith, \& Mundhenk}
\firstpageno{83}

\author{%
%\hspace{.15in}
\name{Christopher Lusena}
\email{lusena@cs.engr.uky.edu}\\
\addr{University of Kentucky\\ Dept.~of Computer Science, Lexington KY 40506-0046}
\AND
\name{Judy Goldsmith}
\email{goldsmit@cs.engr.uky.edu} \\
\addr{University of Kentucky \\Dept.~of Computer Science, Lexington KY 40506-0046}
\AND
\name{Martin Mundhenk}
\email{mundhenk@ti.uni-trier.de}\\
\addr{%
Universit\"at Trier\\ FB IV -- Informatik, D-54286 Trier, Germany}
}

\begin{document}

\maketitle

\begin{abstract}
We show that for several variations of partially observable 
Markov decision processes,
poly\-nomial-time algorithms for finding control policies 
are unlikely to or simply don't have guarantees of finding policies within
a constant factor or a constant summand of optimal.  
Here ``unlikely'' means  ``unless some complexity classes collapse,'' 
where the collapses considered are $\p=\NP$, $\p=\PSPACE$, or $\p=\EXP$.  
Until or unless these collapses are shown to hold, 
any control-policy designer must choose
between such performance guarantees and efficient computation.
\end{abstract}

%\input{nap-intro}

\section{Introduction}\label{intro}

Life is uncertain;  real-world applications
of artificial intelligence contain many uncertainties.  In
this work,  we show that uncertainty breeds uncertainty:
In a controlled stochastic system with uncertainty (as modeled
by a partially observable Markov decision process, for example),
plans can be obtained efficiently or with quality guarantees, but rarely both.

Planning over stochastic domains with uncertainty is
hard (in some cases PSPACE-hard or even 
undecidable, \citeNP<see>{PapaTsitsi:mor:87,madani:aaai:99}).  Given that
it is hard to find an optimal plan or policy, it is natural to
try to find one that is ``good enough".  In the best of
all possible worlds, this would mean having an algorithm
that is guaranteed to be fast and to produce a policy that
is reasonably close to the optimal policy.
Unfortunately, we show here that such an
algorithm is unlikely or, in some cases, impossible.
The implication for algorithm development is that developers
should not waste time working toward both guarantees at once.

The particular mathematical models we concentrate on in
this paper are \emph{Markov decision processes (\MDPs)} and \emph{partially
observable Markov decision processes (\POMDPs)}.
We consider both the straightforward representations of
\MDPs and \POMDPs, and succinct representations, since the
complexity of finding policies is measured not in terms of
the size of the system, but in terms of the size of the \emph{representation}
of the system.

There has been a significant body of work on heuristics
for succinctly represented \MDPs (see \citeNP{BDH:jair:99,blythe:AIM:99}
for surveys).  Some of this work grows out of the engineering
tradition (see, for example, 
\citeauthor{tsitsi:ml:96}'s \citeyear{tsitsi:ml:96}
%Tsitsiklis and Van Roy's
article on feature-based methods) %~\cite{tsitsi:ml:96}), 
which depends on empirical evidence to evaluate algorithms.
While there are obvious drawbacks to this approach, our work
argues that this may be the most appropriate way to verify the
quality of an approximation algorithm, at least if one wants to
do so in reasonable time.

The same problems that plague approximation algorithms for
uncompressed representations carry over to the succinct 
representations, and the compression introduces additional
complexity.  For example, if there is no computable approximation
of the optimal policy in the uncompressed case, then compression
will not change this.  However, it is easy to find the optimal
policy for an infinite-horizon fully observable 
\MDP~\cite{Bellman:book}, yet EXP-hard
(provably harder than polynomial time)
to find approximately optimal policies (in time measured in the
size of the input) if the input is represented succinctly
(see Section~\ref{sec:MDP}).


Note that there are two interpretations to finding an approximation:
finding a policy with value close to that of the optimal policy,
or simply calculating a \emph{value} that is close to the
optimal value.  If we can do the former and can evaluate
policies, then we can certainly do the latter.  Therefore,
we sometimes show that the latter cannot be done, or cannot
be done in time polynomial in the size of the input (unless
something unlikely is true).


The complexity class PSPACE consists of those languages
recognizable by a Turing machine that uses only $p(n)$ memory
for some polynomial $p$, where $n$ is the size of the input.
Because each time step uses at most one unit of memory, 
$\p\subseteq \PSPACE$, though we do not know whether that
is a proper inclusion or an equality.   Because, given a
limit on the amount of memory used, there are only exponentially
many configurations of that memory possible with a fixed finite
alphabet, $\PSPACE\subseteq \EXP$.  It is not known whether
this is a proper inclusion or an equality either, although it is
known that $\p\neq \EXP$.  Thus, a \PSPACE-hardness result
says that the problem is apparently not tractable, but an
\EXP-hardness result says that the problem is certainly
not tractable.

Researchers also consider problems that are \p-complete (under
logspace or other highly restricted reductions).  For example,
the policy existence problem for infinite-horizon MDPs is
P-complete~\cite{PapaTsitsi:mor:87}.  This is useful information,
because it is generally thought that P-complete problems are
not susceptible to significant speed-up via parallelization.
(For a more thorough discussion of P-completeness, 
see \citeNP{greenlaw:p-complete}.)

We also know that $\NP\subseteq \PSPACE$, so $\p=\PSPACE$
would imply $\p=\NP$.  Thus, any argument or belief that
$\p\neq \NP$ implies that $\p\neq\PSPACE$.
(For elaborations of this complexity theory primer, see
any complexity theory text, such as \citeNP{Papa:complbook}.)

In this paper, we show that there is a necessary trade-off
between running time guarantees and performance guarantees
for any general \POMDP approximation algorithm --- unless
$\p=\NP$ or $\p=\PSPACE$.
(Table~\ref{FOevalresults_table} gives an overview of our results.)
%
%
\begin{table}[t]
\begin{center}

\noindent
\begin{tabular}{|cccc|c|}
\hline
\multicolumn{3}{|c}{\mbox{}\hspace{2mm}{\bf policy }\hspace{4mm}  {\bf representation}\hspace{4mm}
   {\bf horizon}}
 & {\bf problem} &
 {\bf complexity}
\\ \hline

\multicolumn{2}{@{}l}{\quad Partial observability}\\
\hline

stationary & -- & $n$ & $\varepsilon$-app. & not unless \p=\NP \\
stationary & -- & $n$ & above-avg.~value & not unless \p=\NP \\
time-dependent & -- & $n$ &  $\varepsilon$-app. & not unless \p=\NP \\
history-dependent & -- & $n$ &  $\varepsilon$-app. &not unless  \p=\PSPACE \\
stationary & -- & $\infty$ & $\varepsilon$-app. & not unless \p=\NP \\
time-dependent & -- & $\infty$ & $\varepsilon$-app. & uncomputable \\ 
               &    &          &                    & \cite{madani:aaai:99}\\


\hline
\multicolumn{2}{@{}l}{\quad Unobservability}\\
\hline

time-dependent & -- & $n$ &  $\varepsilon$-app. & not unless \p=\NP \\

\hline
\multicolumn{2}{@{}l}{\quad Full observability}\\
\hline

stationary & -- & $n$ & $k$-additive app. & \p -hard \\
stationary & 2TBN & $n$  & $k$-additive app. & \EXP-hard \\

\hline
\end{tabular}
\end{center}
\vspace{-2ex}

\caption{Hardness for partially  and fully observable
\MDPs}\label{FOevalresults_table}
\end{table}
%
%
Note that (assuming $\p\neq \NP$ or $\p\neq\PSPACE$) this tells us that there
is no algorithm that runs in time polynomial in the size of
the representation of the \POMDP that finds a policy that
is close to optimal \emph{for every instance}.  It does not
say that fast algorithms will produce far-from-optimal
values for all POMDPs;
%no fast algorithm will ever be close on any input;
there are many instances where the algorithms already in use
or being developed will be both fast and close.  We simply
can't guarantee that the algorithms will \emph{always} find a
close-to-optimal policy quickly.

\subsection{Heuristics and Approximations}

The state of the art with respect to \POMDP policy-finding
algorithms is that there are three types of algorithms in
use or under investigation:  exact algorithms, approximations,
and heuristics.  Exact algorithms attempt to find exact solutions.
In the finite-horizon cases, they run in worst-case time at least exponential in
the size of the \POMDP and the horizon (assuming a straightforward
representation of the \POMDP).  In the infinite horizon, they
do not necessarily halt, but can be stopped when the policy is
within $\varepsilon$ of optimal (a checkable condition).
Approximation algorithms construct approximations to what the
exact algorithms find.  (Examples of this include 
grid-based methods,~\citeNP{hauskrecht:PhD:97,lovejoy:grid:91,white:91}.)
Heuristics come in two flavors:  those that construct or find actual
policies that can be evaluated, and those that specify a means of
choosing an action (for example, ``most likely state"), which do
not yield policies that can be evaluated using the standard,
linear algebra-based methods.

The best current exact algorithm is incremental pruning (IP) with point-based
improvement \cite{zhang:uai:99}.  Littman's analysis of the witness 
algorithm~\cite{Litt:UAI:95,CKL:witness:95} still applies:  This algorithm
requires exponential time in the worst case.
The underlying theory of these algorithms (Witness, IP, etc.)
for infinite-horizon cases depends on Bellman's and Sondik's
work on value iteration for 
\MDPs and \POMDPs~\cite{Bellman:book,sondik:PhD:71,SmallSon:73}.


The best known family of approximation algorithms is known as grid
methods.  The basic idea is to use a finite grid of points in
the belief space (the space of all probability distributions
over the states of the \POMDP\ --- this is the underlying space
for the algorithms mentioned above) to define
a policy.  Once the grid points are chosen, all of these algorithms
use value iteration on the points to obtain a policy for those
belief states, then interpolate to the whole belief space.
The difference in the algorithms lies in the choice of grid
points.  (An excellent survey appears in~\citeNP{hauskrecht:PhD:97}.)
%%XXXSEE IF THIS HAS APPEARED IN ARCHIVAL JOURNALS.
%%XXX not like. I think it might be divided up into 2 or 
%% three different pieces --Chris
These algorithms are called approximation algorithms because they
approximate the process of value iteration, which the
exact algorithms algorithms carry out exactly.

Heuristics that do not yield easily evaluated policies are surveyed
in~\cite{cassandra:PhD:98}.  These are often very easy to implement,
and include techniques such as ``most likely state'' (choosing a
state with the highest probability from the belief state, and acting
as if the system were fully observable), and minimum entropy (choosing
the action that gives the most information about the current state).
Others depend on ``voting,'' where several heuristics or options are combined.

There are heuristics based on finite histories or other
uses of finite amounts of memory within the 
algorithm~\cite{sondik:PhD:71,platzman:PhD:77,hansen:PhD:98,hansen:uai:98,brain:99,meuleau:uai:99,meuleau1:uai:99,peshkin:ml:99,hansen:aips:00,kim:aips:00}.
None of these comes with proofs of closeness, except for some of
Hansen's work.  For the rest, the trade-off has been made between 
fast searching through policy space and guarantees.

\subsection{Structure of This Paper}

In Section~\ref{sec:defns}, we give formal definitions of \MDPs and \POMDPs
and policies;
two-phase temporal Bayes nets (2TBNs) are defined in Section~\ref{sec:MDP}.
In Section~\ref{sec:approx}, we define 
$\varepsilon$-approximations and additive approximations, and show a
relationship between the two types of approximability for \MDPs and \POMDPs.

We separate the complexity results for finite-horizon policy approximation
from those for infinite-horizon policies.  Section~\ref{sec:fin} contains
nonapproximability results for finite-horizon \POMDP policies;  
Section~\ref{sec:inf} contains nonapproximability for infinite-horizon
\POMDP policies.  %While it is easier to find optimal \MDP policies than
%\POMDP policies, 
Although it is relatively easy to find optimal MDP policies,
we consider approximating \MDP policies in Section~\ref{sec:MDP},
since the succinctly represented case, at least, is provably hard to
approximate.

Some of the more technical proofs are included in appendices
in order to make the
body of the paper more readable.  However, some proofs from other papers
are sketched in the body of the paper in order to motivate both the results
and the proofs newly presented here.



\section{Definitions}\label{sec:defns}

Note that \MDPs are in fact special cases of \POMDPs.  The complexity
of finding and approximating optimal policies depends on the
observability of the system, so our results are segregated
by observability.  However, one set of definitions suffices.

\subsection{Partially Observable Markov Decision Processes}

A partially observable Markov decision process (\POMDP) describes a 
controlled stochastic system
by its states and the consequences of actions on the system.
It is denoted as a tuple $M=(\cS,s_0,\cA,\cO,t,o,r)$, where
\begin{itemize}
\item
$\cS$, $\cA$ and $\cO$ are finite sets of \emph{states},
\emph{actions} and \emph{observations};
\item
$s_0\in\cS$ is the \emph{initial state};
\item
$t:\cS\times\cA\times\cS\rightarrow [0,1]$
is the \emph{state transition function},
where $t(s,a,s')$ is the probability that
state $s'$ is reached from state $s$ on action $a$
(for every $s\in\cS$ and $a\in\cA$;
either $\Sigma_{s'\in\cS}t(s,a,s')=1$, if action $a$
can be applied on state $s$, 
or $\Sigma_{s'\in\cS}t(s,a,s')=0$);
\item
$o:\cS\rightarrow \cO$ is the \emph{observation function},
where $o(s)$ is the observation made in state $s$,\footnote{Note
that making observations probabilistically does not
add any power to \MDPs. 
Any probabilistically observable \MDP can be turned
into one with deterministic observations
with only a polynomial increase in its size.}
\item
$r:\cS\times\cA\rightarrow {\bf Q}$ is the \emph{reward function},
where $r(s,a)$ is the reward gained by taking action $a$
in state $s$.
\end{itemize}

If states and observations are identical,
i.e.~$\cO=\cS$ and $o$ is the identity function (or a bijection),
then the \MDP is called \emph{fully observable}.
Another special case is \emph{unobservable \MDPs},
where the set of observations contains only one element,
i.e.~in every state the same observation is made,
and therefore the observation function is constant.

Normally, MDPs are represented by $\cS\times\cS$ 
tables, one for each action.  However, we will
also discuss more succinct representations: in particular,
{\em two-phase temporal Bayes nets\/} (2TBNS).  These will
be defined in Section~\ref{sec:MDP}.

\subsection{Policies and Performances}

A policy describes how to act depending on observations.
We distinguish three types of policies.
\begin{itemize}
\item
A \emph{stationary policy} $\pi_s$ (for $M$)
is a function $\pi_s:\cO\rightarrow\cA$,
mapping each observation to an action.
\item
A \emph{time-dependent policy} $\pi_t$ 
is a function $\pi_t:\cO\times\nat \rightarrow\cA$,
mapping each pair $\langle$observation, time$\rangle$  to an action. 
\item
A \emph{history-dependent policy} $\pi_h$ 
is a function $\pi_h: \cO^*\rightarrow\cA$,
mapping each finite sequence of observations to an action. 
\end{itemize}

Notice that, for an unobservable \MDP, a history-dependent
policy is equivalent to a time-depend\-ent one.  %Thus, our
%theorems do not address the case of history-dependent policies
%for unobservable \MDPs.

Recent algorithmic development has included consideration of
finite memory policies as well \fullcite{hansen:uai:98,hansen:PhD:98,brain:99,%
meuleau:uai:99,meuleau1:uai:99,peshkin:ml:99,hansen:aips:00,kim:aips:00}.
These are policies that are allowed some finite amount of memory;
sufficient allowances would enable such a policy to simulate a
full history-dependent policy over a finite horizon, 
or perhaps a time-dependent policy,
or to use less memory more judiciously.  One variant of finite memory
policies, which we call \emph{free finite memory policies,}
fixes the amount of memory \emph{a priori}.

More formally, a free finite memory policy with the finite set 
${\cal M}$ of memory states for \POMDP
$M=(\cS,\cA,\cO,t,o,r)$
is a function
% A \emph{finite memory policy}  $\pi_f$
 $\pi_f: \cO\times{\cal M}\rightarrow\cA\times {\cal M}$,
mapping each $\langle$observation, memory state$\rangle$ pair  to
a pair $\langle$action, memory state$\rangle$.
The set of memory states ${\cal M}$
can be seen as a finite ``scratch" memory.

Free finite memory policies can also simulate stationary
policies; all hardness results for stationary policies apply to
free finite memory policies as well.   Because one can consider
a free finite memory policy to be a stationary policy over the
state space $\cS \times{\cal M}$, \emph{all upper bounds (complexity class
membership results) for stationary policies hold 
for free finite memory policies as well.}  The
advantages of free finite memory policies appear in the constants
of the algorithms, and in special, probably large, subclasses of POMDPs,
where a finite amount of memory suffices for an optimal policy.
The maze instances such as McCallum's maze~\cite{mccallum:perc:93,Litt:94} 
are such examples:  McCallum's maze requires only 1 bit of memory to find an
optimal policy.


Let $M=(\cS,s_0,\cA,\cO,t,o,r)$ be a \POMDP.


A \emph{trajectory $\theta$ of length $m$ for $M$} is a sequence of states
$\theta=\sigma_0,\sigma_1,\sigma_2,\ldots,\sigma_m$ 
($m\geq 0$, $\sigma_i\in\cS$) which starts with the initial state of
$M$, i.e.~$\sigma_0=s_0$.
We use 
$T_k(s)$ to denote the set of length-$k$ trajectories
which end in state $s$.

The expected reward obtained in state $s$ after exactly $k$ steps
under policy $\pi$ is
the reward obtained in $s$ by taking the action specified by $\pi$,
weighted by the probability that $s$ is actually reached after $k$ steps,
\begin{itemize}
\item $\rew(s,k,\pi) = r(s,\pi(o(s)))\cdot 
         \sum\limits_{(\sigma_0,\ldots,\sigma_k)\in T_k(s)}
           \prod_{i=1}^{k} t(\sigma_{i-1},\pi(o(\sigma_{i-1})),\sigma_{i})$,
      if $\pi$ is a stationary policy,
\item $\rew(s,k,\pi) = r(s,\pi(o(s),k))\cdot 
         \sum\limits_{(\sigma_0,\ldots,\sigma_k)\in T_k(s)}
           \prod_{i=1}^{k} t(\sigma_{i-1},\pi(o(\sigma_{i-1}),i-1),\sigma_{i})$,
      if $\pi$ is a time-dependent policy, and
\item $\rew(s,k,\pi)=\sum\limits_{(\sigma_0,\ldots,\sigma_k)\in T_k(s)}
          r(s,\pi(o(\sigma_0)\cdots o(\sigma_k))) \cdot
           \prod_{i=1}^{k} 
            t(\sigma_{i-1},\pi(o(\sigma_0)\cdots o(\sigma_{i-1})),\sigma_{i})$,
      if $\pi$ is a history-dependent policy.
\end{itemize}


A \POMDP may behave differently under optimal policies for each type
of policy.  
The quality of a policy is determined by its \emph{performance},
i.e.~by the expected rewards accrued by it.
We distinguish between 
different performance metrics for
POMDPs that run for a finite number of steps
and those that run indefinitely.

\begin{itemize}
\item
The \emph{finite-horizon performance of a policy $\pi$} for \POMDP $M$
is the expected sum of rewards received during the first $|M|$ steps
by following the policy $\pi$,
i.e., $\perff(M,\pi) = \sum_{i=0}^{|M|-1}\sum_{s\in\cS}\rew(s,i,\pi)$.
(Other work assumes that the horizon is $\mathit{poly}(|M|)$, instead of
$|M|$. This does not change the complexity of any of our problems.)
\item 
The infinite-horizon \emph{total discounted performance} gives 
rewards obtained
earlier in the process a higher weight than those obtained later.
For $0 < \beta < 1$,
the total $\beta$-discounted reward is defined as
$\perf_{td}^{\beta}(M,\pi)=\sum_{i=0}^{\infty}\sum_{s\in{\cal S}}
   \beta^i \cdot \rew(s,i,\pi)$.
\item
The infinite-horizon \emph{average performance} is 
the limit of all rewards obtained within
%the first 
$n$ steps divided by $n$, for $n$ going to infinity:%
\footnote{If this limit is not defined, the performance is defined as
a $\liminf$.}
$\perf_{av}(M,\pi)=\lim_{n\rightarrow\infty}\frac{1}{n}\perff(M,n,\pi)$.
\end{itemize} 

Let $\perf$ be any  of these performance metrics, and
let $\alpha$ be any policy type, either stationary, 
time-dependent, or history-dependent.
The \emph{$\alpha$-value} $\val_{\alpha}(M)$ of $M$ 
(under the metric chosen) 
is the maximal performance of any policy $\pi$
of type $\alpha$ for $M$,
i.e.~$\val_{\alpha}(M)=\max_{\pi\in\Pi_{\alpha}}\perf(M,\pi)$,
where $\Pi_{\alpha}$ is the set of all $\alpha$ policies.
%We also write $\val_{\alpha}(M,k)$ for the finite-horizon
%$\alpha$-value of $M$ with horizon $k$.

%
%The \emph{$\alpha,\beta$-value} $\val_{\alpha,\beta}(M)$ of $M$ is
%$M$'s maximal $\beta$-performance under any policy $\pi$
%of type $\alpha$,
%i.e.~$\val_{\alpha,\beta}(M)=\max_{\pi\in\Pi_{\alpha}}\perf_{\beta}(M,\pi)$,
%where $\Pi_{\alpha}$ is the set of all $\alpha$ policies.

{F}or simplicity, we assume that the size $|M|$
of a \POMDP $M$ is determined by the size $n$ of its state space.
We assume that there are no more actions than states,
and that each state transition probability is given as a binary fraction
with $n$ bits and each reward is an integer of at most $n$ bits.
This is no real restriction, since adding unreachable ``dummy'' states 
allows one to use more bits for transition probabilities and rewards.
Also, it is straightforward to transform a \POMDP $M$ with non-integer
rewards to $M'$ with integer rewards such that 
$\val_{\alpha}(M,k) = c \cdot \val_{\alpha}(M',k)$ for some constant $c$
depending only on %the transformation, rather than the instance $(M,k)$.
$(M,k)$ and not on $\val_{\alpha}(M,k)$.

We consider
problem instances that are represented in a straightforward way.
A \POMDP with $n$ states is represented by a set of
$n\times n$ tables for
the transition function (one table for each action) 
and a similar table for the reward function and for the observation function.
We assume that the number of actions
and the number of bits needed to store 
each transition probability or reward
does not exceed $n$,
so such a representation requires $O(n^4)$ bits.
(This can be modified to allow $n^k$ bits 
without changing the complexity results.)
In the same way,
stationary policies can be encoded as
lists with $n$ entries, and time-dependent
policies for horizon $n$ as $n\times n$ tables.

For each type of \POMDP, each type of policy, and each type of performance
%we consider the \emph{value problem} and the \emph{policy existence problem}.
metric the \emph{value problem} is,
\begin{description}
\item[given]
 a \POMDP, 
a performance metric (finite-horizon, total discounted, or average
performance),
and a policy type (stationary, time-dependent, or history-dependent),
\item[calculate]
 the value of the best policy of the
specified type under the given performance metric.
%of the optimal policy of that type for it.
\end{description}
The \emph{policy existence problem} is,
\begin{description}
\item[given]
a \POMDP, a performance metric, and a policy type,
\item[decide]
whether the value of the best policy of the
specified type under the given performance metric
is greater $0$.
\end{description}




\section{Approximability}\label{sec:approx}
In previous 
work~\cite{PapaTsitsi:86,PapaTsitsi:mor:87,MGA:MFCS:97,encyclo,madani:aaai:99},
it was shown 
that the policy existence problem 
is computationally intractable for most variations of POMDPs, or even
undecidable for some infinite-horizon cases.
For example, we showed that the stationary policy existence
problems for POMDPs with or without negative rewards
are \NP-complete.  
Computing an optimal policy is at least
as hard as deciding the existence problem.
Instead of asking for an optimal policy, we might wish to compute
a policy that is guaranteed to have a value
that is at least a large fraction of the optimal value.

A \polytime algorithm computing such a nearly optimal policy
is called an $\varepsilon$-approx\-i\-ma\-tion (for $0\leq \varepsilon<1$),
where $\varepsilon$ indicates the quality of the approximation
in the following way.
Let $A$ be a \polytime algorithm which for
every \POMDP $M$ computes an $\alpha$-policy $A(M)$.
Notice that $\perf(M,A(M))\leq \val_{\alpha}(M)$ for every $M$.
The algorithm $A$ is called an \emph{$\varepsilon$-approximation}
if for every \POMDP $M$, 
$$
\left|\frac{\val_{\alpha}(M)-\perf(M,A(M))}{\val_{\alpha}(M)}\right|
\leq\varepsilon\ .
$$

%\noindent
(See, e.g., \citeNP{Papa:complbook} for more detailed definitions.)
Approximability distinguishes $\NP$-complete problems:
There are problems which are $\varepsilon$-approximable
for all $\varepsilon$, for certain $\varepsilon$, 
or for no $\varepsilon$ (unless $\p=\NP$). 
Note that this definition 
of $\varepsilon$-approximation requires that $\val_{\alpha}(M)\geq 0$.
If a policy with positive performance exists,
than every approximation algorithm yields such a policy,
because a policy with performance $0$ or smaller
cannot approximate a policy with positive performance.
Hence, any approximation straightforwardly solves the decision problem.


An approximation scheme yields an $\varepsilon$-approximation
for arbitrary $\varepsilon>0$.
If there is a \polytime algorithm that on
 input \POMDP $M$ and $\varepsilon$ outputs an $\varepsilon$-approximation
of the value, in time polynomial in the size of $M$ 
%and $\frac{1}{\varepsilon}$, 
then we say the problem has a
\emph{Polynomial-Time Approximation Scheme (PTAS)}.
If the algorithm runs in time polynomial in the size of $M$
and $\frac{1}{\varepsilon}$, the scheme is a \emph{Fully Polynomial-Time
Approximation Scheme (FPTAS)}.  All 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 $\frac{1}{\varepsilon}$.


If there is a \polytime algorithm that
 outputs an approximation, $v$, to the value $\mu$
of $M$ ($\mu= \val_\alpha(M)$) 
with $\mu\geq v\geq \mu-k$, then we
say that the problem has a 
{\em $k$-additive approximation algorithm.\/}

  
In the context of POMDPs, 
existence of a $k$-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 {\em a priori\/} upper bound on the performance 
of policies, even though there 
are computable upper bounds on the performance of a policy for each
{\em instance.}

%XXX discuss how these approximations differ from typical goal
% oriented probability of success approximations. AS per Ref \#3' s comment.

\begin{theorem}\label{lusena1} 
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 $k$-additive approximation, then we can determine
in polynomial time
whether there is a policy with performance greater than 0.
\end{theorem}

\begin{proof} The theorem follows from two facts: (1) given 
a \POMDP $M$ with value $\mu$, we can construct
another \POMDP $\theta M$ with value $\theta\cdot\mu$ just by
multiplying all rewards in the former \POMDP by $\theta$; (2)
under these reward metrics we can find a lower bound on
$\mu$ if it is not 0.

The computation of the lower bound, $\delta$, on the value of $\mu$ 
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
by the last step.  Consider only reachable states of the POMDP, and let 
$\nu$ be the lowest nonzero transition probability to one of these
states, $h$ the horizon,
and $\zeta$ the smallest nonzero reward, and set $\delta=\nu^h\zeta$.
Then $\nu^h$ is a lower bound on the probability of actually reaching
any particular state after $h$ steps (if this probability is
nonzero), in particular a state with reward
$\zeta$. If the reward metric is discounted, then let 
$\delta=(\gamma\nu)^h\zeta$, where $\gamma\in (0,1]$ 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 {\em simple\/} path (visiting each node at most
once) to a reward node. Such a path accrues reward at least
$\delta=(\gamma\nu)^{|S|}\zeta$ for stationary policies. %, where
%$\gamma$ is the discount factor. 

Since stationary policies have values bounded by the time-dependent and
history-depend\-ent 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 0, then a $k$-additive approximation cannot return a
positive value.
To determine whether there is a policy with reward greater than
0 for a given POMDP, 
compute $\delta$ and then set $\theta$ such that $\theta\delta-k>0$,
i.e., $\theta>\frac{k}{\delta}$, and run the $k$-additive approximation
algorithm on $\theta M$. The POMDP has positive value if and only if 
the approximation returns a positive value.
\end{proof}

Note that this does not contradict the undecidability result
of \citeA{madani:aaai:99}.  The problem
that they proved undecidable is whether a \POMDP with nonpositive
rewards has a history-dependent or time-dependent value of 0.
We're asking whether it has value $>$ 0 in the non-negative
reward case;  answering this question (even if we multiply the
rewards by $-1$) does not answer their question.


\begin{coro}\label{additiveIFFPTAS} 
For \POMDPs
with flat representations and non-negative rewards,
the \POMDP value problem under finite-horizon or infinite-horizon
total discounted reward is $k$-additive approximable
if and only if there exists a %\polytime approximation
%scheme (a 
PTAS for that \POMDP  value problem.
\end{coro}

Note that the corollary depends only on Facts (1) and (2) from the
proof of Theorem~\ref{lusena1}.  Thus, any optimization problem with
those properties will have a $k$-additive approximation if and only
if it has a PTAS.

\begin{proof}
Let $\mu=\val_\alpha(M)$, and
let $A$ be a \polytime $k$-additive approximation algorithm.
First, the PTAS computes $\delta$ as in Theorem~\ref{lusena1} and
checks whether $\mu = 0$.  If so, it outputs $0$.
Otherwise, given $\varepsilon$, it chooses $\theta$ such that 
$\theta>\frac{k}{\varepsilon\delta}\geq \frac{k}{\varepsilon\mu}$, 
and thus
$\theta\mu -k>(1-\varepsilon)\theta \mu$ holds.
Let $v = A(\theta M)$. 
(Note that $A(M)$ is the approximation to the value
of $M$ found by running algorithm $A$.)
Then $v$ is an $\varepsilon$-approximation to $\theta\mu$, so 
$\frac{v}{\theta}$
is an $\varepsilon$-approximation to $\mu$. 

Suppose, instead, that we have a PTAS for optimal policies
for this problem.
Let $A(M,\varepsilon)$ be an algorithm that demonstrates this.
Let $\mu=\val_\alpha(M)$, and $A(M,0.5)=v$. Thus $\mu\geq v\geq 
\frac{\mu}{2}$. 
If $\mu=0$ then $v=0$ and we can stop.
Else we choose an  
$\varepsilon$ such that
$(1-\varepsilon)\mu\geq\mu-k$, giving
$\varepsilon \leq \frac{k}{\mu}$.
Since $\frac{k}{2v}\leq\frac{k}{\mu}$, and $\frac{k}{2v}$ is polynomial size
and is \polytime computable in $|M|$
(since $v$ is the output of $A(M,0.5)$), 
we can choose $\varepsilon<\frac{k}{2v}$, and run $A(M,\varepsilon)$.
This gives a $k$-additive approximation.
\end{proof}

A problem that is not $\varepsilon$-approximable for some $\varepsilon$
cannot have a PTAS.  Therefore, any multiplicative nonapproximability
result yields an additive nonapproximability result.  However, an
additive nonapproximability result only shows that there is no PTAS, 
although there might
be an $\varepsilon$-approximation for some fixed $\varepsilon$.







\section{Non-Approximability for Finite-Horizon \POMDPs}\label{sec:fin}

This section focuses on finite-horizon policies.  Because that
is consistent throughout the section, we do not explicitly mention
it in each theorem.  However, as Section~\ref{sec:inf} shows, there
are significant computational differences between finite- and 
infinite-horizon calculations.

The policy existence problem for
\POMDPs with negative and non-negative rewards is not suited for
$\varepsilon$-approximation.
If a policy with positive performance exists,
then every approximation algorithm yields such a policy,
because a policy with performance $0$ or smaller 
cannot approximate a policy with positive performance.
Hence, the decision problem 
is straightforwardly solved by
any $\varepsilon$-approximation. 
Therefore, we concentrate on \POMDPs with non-negative rewards.
Results for \POMDPs with unrestricted rewards are
stated as corollaries.
Consider an $\varepsilon$-approximation algorithm $A$
that, on input a \POMDP $M$ with non-negative rewards,
outputs a policy $\pi_{\alpha}^{M}$ of type $\alpha$.
Then it holds that 
$$
\perf(M,\pi_{\alpha}^{M}) \geq
(1-\varepsilon)\cdot \val_{\alpha}(M).
$$

We first consider the question
of whether an optimal stationary policy
can be $\varepsilon$-approx\-i\-ma\-ted
for \POMDPs with non-negative rewards.
It is known~\cite{Litt:94,encyclo} that the related decision problem
is $\NP$-complete.
We include a sketch of that proof here, since later proofs build on it.
The formal details can be found in Appendix~\ref{stat-reduct}.

\begin{theorem}\cite{Litt:94,encyclo}\label{sfpMDPPp_NP-complete}
The stationary policy existence problem for \POMDPs
with non-negative rewards is $\NP$-complete.
\end{theorem}
 
\begin{proof}
Membership in $\NP$ is straightforward,
because a policy can be guessed
and evaluated in polynomial time.
To show $\NP$-hardness,
we reduce the $\NP$-complete satisfiability problem
$\THREESAT$ to it.
Let $\phi(x_1,\ldots,x_n)$ be such a formula
with variables $x_1,\ldots,x_n$
and clauses $C_1,\ldots,C_m$,
where clause $C_j=(l_{v(1,j)}\vee l_{v(2,j)} \vee l_{v(3,j)})$
for $l_i\in\{x_i,\lneg x_i\}$.
We say that variable $x_i$
\emph{appears in $C_j$ with signum $0$ (resp.~$1$)}
if $\lneg x_i$ (resp.~$x_i$) is a literal in $C_j$.
Without loss of generality, we assume that every variable
 appears at most once in each clause.
The idea is to construct a \POMDP $M(\phi)$ having
one state for each appearance of a variable in a clause.
The set of observations is the set of variables.
Each action corresponds to an assignment of
a value to a variable.
The transition function is deterministic.
The process starts with the first variable
in the first clause.
If the action chosen in a certain state
satisfies the corresponding literal,
the process proceeds to the first variable
of the next clause, or with reward 1 to a final sink state $T$ if all
clauses were considered.
If the action does not satisfy the literal, the process proceeds to the next
variable of the clause, or with reward 0 to a sink state $F$.
A sink state will never be left.
The partition of the state space into observation classes
guarantees that the same assignment is made
for every appearance of the same variable.
Therefore, the value of $M(\phi)$ equals $1$
iff $\phi$ is satisfiable. 
The formal reduction is in Appendix~\ref{stat-reduct}.
\end{proof}
 

Note that all policies have expected reward of either 1 or 0.
Immediately we get the nonapproximability result
for \POMDPs, even if all trajectories have non-negative performance.


\begin{theorem}\label{sfpMDPP_nonapprox}
Let $0\leq \varepsilon < 1$.
An optimal stationary policy for \POMDPs 
with non-negative rewards
is $\varepsilon$-appro\-xi\-mable 
if and only if $\p=\NP$.
\end{theorem}

\begin{proof} 
The stationary value of a \POMDP can be calculated
in polynomial time by a binary search 
using an oracle for the
stationary policy existence problem for \POMDPs.
The number of bits to be calculated is polynomial in the size of $M$.
Knowing the value, we can try 
to fix an action for an observation.
If the modified \POMDP still achieves the value
calculated before, we can continue with the next observation,
until a stationary policy is found which has the optimal
performance.
This algorithm runs in polynomial time
with an oracle solving the
stationary policy existence problem for \POMDPs.
Since the oracle is in NP, by
Theorem~\ref{sfpMDPPp_NP-complete},
the algorithm runs in polynomial time if $\p=\NP$.

Now, assume that $A$ is a polynomial-time
algorithm that $\varepsilon$-approximates the optimal stationary policy
for some $\varepsilon$ with $0\leq \varepsilon < 1$.
We show that this implies that $\p=\NP$
by showing how to solve the \NP-complete problem \THREESAT.
As in the proof of Theorem~\ref{sfpMDPPp_NP-complete},
given an instance $\phi$ of \THREESAT,
we construct a \POMDP $\mM(\phi)$.
The only change to the reward function of the \POMDP constructed in 
the proof of Theorem~\ref{sfpMDPPp_NP-complete}
is to make it a \POMDP with positive performances.
Now reward $1$ is obtained if state $F$ is reached, 
and reward $\lceil \frac{2}{1-\varepsilon}\rceil$ is obtained
if state $T$ is reached.
Hence $\phi$ is satisfiable if and only if
$\mM(\phi)$ has value $\lceil \frac{2}{1-\varepsilon}\rceil$.

Assume that policy $\pi$ is the output of
the $\varepsilon$-approximation algorithm $A$.
If $\phi$ is satisfiable, then 
$\perf(\mM(\phi),\pi)
    \geq  (1-\varepsilon)\cdot \frac{2}{1-\varepsilon}
      =   2
      > 1  $.
Because the performance of every policy for $\mM(\phi)$ 
is either $1$ if $\phi$ is not satisfiable,
or $\lceil \frac{2}{1-\varepsilon}\rceil$ if $\phi$ is satisfiable,
it follows that $\pi$ has performance 
$>1$ if and only if $\phi$ is satisfiable.
So, in order to decide $\phi\in\THREESAT$,
we can construct $\mM(\phi)$, run 
the approximation algorithm $A$ on it,
take its output $\pi$ and calculate $\perf(\mM(\phi),\pi)$.
That output shows
whether $\phi$ is in $\THREESAT$.
All these steps are polynomial-time bounded computations.
It follows that $\THREESAT$ is in \p,
and hence $\p=\NP$.
\end{proof}

Of course, the same nonapprox\-i\-ma\-bil\-ity result
holds for \POMDPs with positive and negative rewards.

\begin{coro}
Let $0 \leq \varepsilon < 1$.
Any optimal stationary policy for \POMDPs 
is $\varepsilon$-appro\-xi\-mable 
if and only if $\p=\NP$.
\end{coro}

Using the same proof technique as above,
we can show that the value is nonapproxi\-mable, too.

\begin{coro}
Let $0 \leq \varepsilon < 1$.
The stationary value  for \POMDPs
is $\varepsilon$-appro\-xi\-mable 
if and only if $\p=\NP$.
\end{coro}


A similar argument can be used 
to show that a policy with performance
at least the average of all performances for a \POMDP 
cannot be computed in polynomial time, unless $\p=\NP$.
Note that in the proof of
Theorem~\ref{sfpMDPPp_NP-complete}, 
the only performance greater than or equal to the average
of all performances is that of an optimal policy.
%If the average is greater than 0, then the only policies
%with performance greater than \emph{or equal to} the
%average are optimal policies.

\begin{coro}
The following are equivalent.
\begin{enumerate}
\item
There exists a polynomial-time algorithm that 
for a given \POMDP $M$ computes a stationary policy
under which $M$ has performance greater than or equal to
the average stationary performance of $M$.
\item
$\p=\NP$.
\end{enumerate}
\end{coro}
Thus, even calculating a policy whose performance is
above average is likely to be
infeasible.  %except, perhaps, in Lake Woebegone.

We now turn to time-dependent policies.
The time-dependent policy existence problem for \POMDPs
is known to be $\NP$-complete, as is the stationary one.

\begin{theorem}\cite{encyclo}\label{time-exi-NPcomplete}
The time-dependent policy existence problem
for unobservable \MDPs
is $\NP$-com\-plete.
\end{theorem}

\citeA{PapaTsitsi:mor:87} proved a
theorem similar to Theorem~\ref{time-exi-NPcomplete}.
Their \MDPs had only non-positive rewards, and their formulation of
the decision problem was whether there is a policy
with performance 0.  
The proof by~\citeNP{encyclo}, like theirs, uses a reduction
%Our result can be proven by
%a proof very similar to theirs, using a reduction
{from} $\THREESAT$.
We modify this reduction to show that
an optimal time-dependent policy is hard to approximate even for
unobservable \MDPs.

\begin{theorem}\label{tfpMDPP_nonapprox}
Let $0 \leq \varepsilon < 1$.
Any optimal time-dependent policy for
unobservable \MDPs with non-negative rewards
is $\varepsilon$-appro\-xi\-mable 
if and only if $\p=\NP$.
\end{theorem}


\begin{proof}
We give a reduction from $\THREESAT$ 
%(Given a 3CNF formula, what is the maximum number of
%simultaneously satisfiable clauses?)
with the following properties.
For a formula $\phi$ with $m$ clauses we show how to construct an
unobservable \MDP $M_{\varepsilon}(\phi)$ with value
$1$ if $\phi$ is satisfiable,
and with value $<(1-\varepsilon)$ if $\phi$ is not satisfiable.
Therefore, an $\varepsilon$-approximation could be used to
distinguish between satisfiable and unsatisfiable formulas
in polynomial time.

For formula $\phi$, we first show how
to construct an unobservable $M(\phi)$
from which $M_{\varepsilon}(\phi)$ will be constructed.
(The formal presentation appears in Appendix~\ref{time-reduct}.)
$M(\phi)$ simulates the following strategy.
At the first step, one of the $m$ clauses is chosen uniformly at random
with probability $\frac{1}{m}$.
At step $i+1$, the assignment of variable $i$
is determined.
Because the process is unobservable,
it is guaranteed that each variable gets
the same assignment in all clauses,
because its value is determined in the same step.
If a clause is satisfied by this assignment, 
a final state will be reached.
If not, an error state will be reached.

Now, construct $M_{\varepsilon}(\phi)$ 
from $m^2$ copies $M_1,\ldots,M_{m^2}$ of $M_{\phi}$,
such that the initial state of $M_{\varepsilon}(\phi)$ 
is the initial state of $M_1$,
the initial state of $M_{i+1}$ is the final state $T$ 
of $M_i$, 
and reward $1$ is gained if the final state of $M_{m^2}$ is reached.
The error states of all the $M_i$s are identified as a unique sink state $F$.

To illustrate the construction, in Figure~\ref{fig2} we give
an example \POMDP consisting of
a chain of $4$ copies of $M(\phi)$ obtained for the
formula $\phi=(\neg x_1\vee x_3\vee x_4) \wedge (x_1\vee\neg x_2\vee x_4)$.
% The meaning of the arrows are as in Figure~\ref{fig1}.
The dashed arrows indicate
a transition with probability $\frac{1}{2}$.
The dotted (resp.~solid) 
arrows are probability 1 transitions on action $0$ (resp.~$1$).
The actions correspond to assignments to the variables.

\begin{figure}
\begin{center}
\input{nap-timedep.pstex_t}
\end{center}
\caption{An example unobservable \MDP for 
$\phi=(\neg x_1\vee x_3\vee x_4) \wedge (x_1\vee\neg x_2\vee x_4)$}\label{fig2}
\end{figure}

If $\phi$ is satisfiable,
then a time-dependent policy simulating $m^2$ repetitions of
any satisfying assignment has performance $1$.
If $\phi$ is not satisfiable, then under any assignment
at least one of the $m$ clauses of $\phi$ is not satisfied.
Hence, the probability that under any time-dependent policy
the final state $T$ of $M(\phi)$ is reached is at most $1-\frac{1}{m}$.
Consequently, the probability that the final state
of $M_{\varepsilon}(\phi)$ is reached is at most
$(1-\frac{1}{m})^{m^2}\leq e^{-m}$.
This probability equals the expected reward.
Since for large enough $m$ it holds that $e^{-m}<(1-\varepsilon)$,
the theorem follows.
\end{proof}
 
Note that the time-dependent policy existence problem
for \POMDPs with non-negative rewards is $\NL$-complete~\cite{encyclo}.
The class $\NL$ consists of those languages recognizable
by nondeterministic Turing machines that use a read-only input tape
and additional read-write tapes with $O(\log n)$ tape cells.
It is known that $\NL\subseteq \p$
and that $\NL$ is properly contained in $\PSPACE$.
Unlike the case of stationary policies,
approximability of time-dependent policies is harder
than the policy existence problem (unless $\NL=\NP$).

Unobservability is a special case of partial observability.
Hence, we get the same nonapproximability result
for \POMDPs,  even for unrestricted rewards.

\begin{coro}\label{tfpMDPP_nonapprox_coro}
Let $0 \leq \varepsilon < 1$.
Any optimal time-dependent policy
for \POMDPs 
is $\varepsilon$-appro\-xi\-mable 
if and only if $\p=\NP$.
\end{coro}

\begin{coro}
Let $0 \leq \varepsilon < 1$.
The time-dependent value of \POMDPs 
is $\varepsilon$-appro\-xi\-mable 
if and only if $\p=\NP$.
\end{coro}


Note that the proof of Theorem~\ref{tfpMDPP_nonapprox}
assumed a total expected reward criterion.  The discounted
reward criterion is also useful in the finite horizon. 
To show the result for a discounted reward criterion, 
we only need to change the reward in the proof of 
Theorem~\ref{tfpMDPP_nonapprox} as follows:
Multiply the final reward by
$\beta^{-m^2(n+1)}$, where $\beta$ is the discount factor,
$m$ the number of clauses, and $n$ the number of variables of the
formula $\phi$.


%Papadimitriou and Tsitsiklis~
\citeA{PapaTsitsi:mor:87}
proved that a problem very similar to
history-dependent policy existence is $\PSPACE$-complete.

\begin{theorem}\cite{PapaTsitsi:mor:87,encyclo}\label{histdep-PSPACE}
The history-dependent policy existence problem for \POMDPs 
is $\PSPACE$-com\-plete.
\end{theorem} 

To describe a
horizon $n$ history-dependent policy for a \POMDP 
with $c$ observations explicitly takes space $\sum_{i=1}^n c^i$.
(We do not address the case of succinctly represented
policies for \POMDPs here.  For an analysis of their complexity,
see~\citeNP{Mund:tract-hist}.)
If $c>1$, this is exponential space.
Therefore, we cannot expect that a \polytime algorithm
outputs a history-dependent policy,
and we restrict consideration to \polytime algorithms
that approximate the history-dependent \emph{value} 
--- the optimal performance under any history-dependent policy ---
of a \POMDP.
%Burago et al.~
\citeA{BRS:tcs:96}
considered the class of \POMDPs with a bound
of $q$ on the number of states corresponding to an observation,
where the rewards corresponded to the probability of reaching
a fixed set of goal states (and thus were bounded by 1).
They showed that for any fixed $q$, 
the optimal history-dependent policies
for \POMDPs in this class can be approximated to within an
additive constant $k$.
We showed in Proposition~\ref{additiveIFFPTAS}
that \POMDP history-dependent discounted or total-reward
value problems that can be approximated to within an
additive constant $k$ have \polytime
approximation schemes (Proposition~\ref{additiveIFFPTAS}),
\emph{as long as there are no a priori bounds on either the number of 
states per observation or the rewards}.

Notice, however, that
Theorem~\ref{HistoryPOMDP-not-mult-approx-PSPACE}
does not give us information about the classes of
\POMDPs that %Burago et al.~
\citeA{BRS:tcs:96} considered:  Because of the
restrictions associated with the parameter $q$, our hardness
results do not contradict their result.

Finally, we show that the history-dependent value of \POMDPs
with non-negative rewards
is not $\varepsilon$-approximable under total
expected or discounted rewards, unless $\p=\PSPACE$.
Consequently, the value has no PTAS or $k$-additive approximation under 
the same assumption.

The history-dependent policy existence problem
for \POMDPs with non-negative rewards is $\NL$-complete~\cite{encyclo}.
Hence, because $\NL$ is a proper subclass of $\PSPACE$,
approximability of the history-dependent value is
\emph{strictly} harder than the policy existence problem.


\begin{theorem}\label{HistoryPOMDP-not-mult-approx-PSPACE} 
Let $0 \leq \varepsilon < 1$.
The history-dependent value of \POMDPs with non-negative rewards
is $\varepsilon$-approximable 
if and only if $\p=\PSPACE$.
\end{theorem} 

\begin{proof}
The history-dependent value of a \POMDP $M$ can be calculated
using binary search over the history-dependent policy
existence problem.
The number of bits to be calculated is polynomial in the size of $M$.
Therefore, by Theorem~\ref{histdep-PSPACE},
this calculation can be performed in polynomial time
using a $\PSPACE$ oracle.
If $\p=\PSPACE$, it follows that the history-dependent value of a
\POMDP $M$
can be \emph{exactly} calculated in polynomial time.

The set $\QBF$ of true quantified Boolean formulae is 
one of the standard $\PSPACE$ complete sets.
To conclude $\p=\PSPACE$ from an $\varepsilon$-approximation
of the history-dependent value problem,
we use a transformation of
instances of $\QBF$ to \POMDPs
similar to the proof of
Theorem~\ref{histdep-PSPACE} in~\cite{Mund:habil}.
%% This transformation is given in Appendix~\ref{histdep-PSPACE-proof}.

The set $\QBF$ can be interpreted as a two-player game:
Player 1 sets the existentially quantified variables,
and player 2 sets the universally quantified variables.
Player 1 wins if the alternating choices determine
a satisfying assignment to the formula,
and player 2 wins if the determined assignment is not satisfying.
A formula is in $\QBF$ if and only if player 1 has a 
winning strategy.
This means player 1 has a response to every choice
of player 2, so that in the end the formula will be satisfied.

\newlength{\rhoehe}
\settoheight{\rhoehe}{\sffamily \slshape R}
% \newcommand{\random}{\begin{turn}{180}\raisebox{-\rhoehe}{\sffamily R}\end{turn}}
\newcommand{\random}{\mbox{\sffamily \slshape R}}

The version where player 2 makes random choices 
and player 1's goal is to win with probability $>\frac{1}{2}$
corresponds to $\SSAT$ (\emph{stochastic satisfiability}),
which is also $\PSPACE$ complete.
The instances of $\SSAT$ are formulas
which are quantified alternatingly with existential quantifiers
$\exists$ and random quantifiers $\random$. %$R$.
The meaning of the random quantifier $\random$ is that 
an assignment to the respective variable is chosen 
uniformly at random from $\{0,1\}$.
A stochastic Boolean formula 
$$
\Phi=\exists x_1 \random x_2 \exists x_3 \random x_4 \ldots \phi
$$
is in $\SSAT$ if and only if

\centerline{
there exists $b_1$ 
  for random $b_2$ exists $b_3$ for random $b_4$ \ldots 
     $Prob[\phi(b_1,\ldots,b_n)\mbox{ is true}] > \frac{1}{2}$.
}
\vspace{1ex}

If $\Phi$ has $r$ random quantifiers,
then the strategy of player 1 determines a 
set of $2^r$ assignments to $\phi$.
The term ``$Prob[\phi(b_1,\ldots,b_n)\mbox{ is true}] > \frac{1}{2}$''
means that more than $2^{r-1}$ of these $2^r$ assignments
satisfy $\phi$.

\newcommand{\mmhat}{\widehat}

{From} the proof of $\IP=\PSPACE$ by %Shamir~
\citeA{Shamir:1992:IP}
it follows that for every $\PSPACE$ set $A$ and constant $c\geq 1$ there
is a \polytime reduction $f$ from $A$ to $\SSAT$ such that for
every instance $x$ and formula 
$f(x)=\exists x_1 \random x_2 \ldots \phi_x$
the following holds.
\begin{itemize}
\item If $x\in A$, then %% \\\mbox{} \ \  
   $\exists b_1 \mbox{ for random } b_2 \ldots 
                 Prob[\phi_x(b_1,\ldots,b_n)\mbox{ is true}] > (1-2^{-c})$, 
and
\item if $x\not\in A$, then 
   $\forall b_1 \mbox{ for random } b_2 \ldots 
                 Prob[\phi_x(b_1,\ldots,b_n)\mbox{ is true}] < 2^{-c}$.
\end{itemize}
This means that player 1 either has a strategy
under which she wins with very high probability,
or the probability of winning (under any strategy) is very small.
We show how to transform a stochastic Boolean formula $\Phi$
into a \POMDP with a large history-dependent value
if player 1 has a winning strategy,
and a much smaller value if player 2 wins.

{F}or an instance $\Phi=\exists x_1 \random x_2 \ldots \phi$ of $\SSAT$, 
where $\Phi$ is a % 3CNF 
formula with $n$ variables $x_1,\ldots,x_n$, 
we construct a \POMDP $\mM(\Phi)$ as follows.
The role of player 1 is taken by the controller of the process.
A strategy of player 1 determines a policy of the controller,
and vice versa.
Player 2 appears as probabilistic transitions in the process.
The process $\mM(\Phi)$ has three stages.
The first stage consists of one step.
The process chooses uniformly at random one of the variables 
and an assignment to it,
and stores the variable and the assignment.
More formally, from the initial state $s_0$,
one of the states ``$x_i=b$'' ($1\leq i\leq n$, $b\in\{0,1\}$)
is reached, each with probability $1/(2n)$.
\begin{figure}[ht]
\begin{center}
\input{stage1.pstex_t}
\end{center}
\caption{The first stage of $\mM(\Phi)$.}\label{fig-stage1}
\end{figure}
%The partial observability of the process
%is made use of in the way, that it becomes unobservable
It is not observable
which variable assignment was stored by the process.
However, whenever that variable appears later, %the assignment to which
%is stored by the process,
the process checks that the initially fixed assignment
is chosen again.
If the policy gives a different assignment during
the second stage,
the process halts with reward $0$.  (There is a deterministic
transition to a final state which we refer to as $s_{end}$, or less
formally, the \emph{dead end} state.)
If such an inconsistency occurs during the third stage,
the process halts with reward $0$
and notices that the policy \emph{cheats}.  (There is a deterministic
transition to a sink state which we refer to as $s_{cheat}$, or
less formally as \emph{the penalty box} because the player sent there
cannot re-enter the game later.)
If eventually the whole formula is passed, 
either reward $2$ or reward $0$ 
is obtained dependent on whether the formula was satisfied or not.
The first stage is sketched in Figure~\ref{fig-stage1}.
In this and the following figures,
dashed arrows represent random
transitions (all of equal probability, irregardless
of the action chosen),  solid arrows represent 
deterministic transitions corresponding to the action $1$
(True), and dotted arrows represent deterministic transitions
corresponding to the action $0$ (False).

The second stage starts in each of the states ``$x_i=b$''
and has $n$ steps, during which an assignment
to the variables $x_1, x_2,\ldots,x_n$ is fixed.
Let $\mA_{c,b}$ denote the part of the process' second stage
during which it is assumed that value $b$ is assigned to variable $x_c$.
If a variable $x_i$ is existentially quantified,
then the assignment is the action in $\{0,1\}$ chosen by the policy.
If a variable $x_i$ is randomly quantified,
then the assignment is chosen uniformly at random by the process,
independent of the action of the policy.
In the second stage, it is observable
which assignment was made to every variable.
If the variable assignment from the first stage
does not coincide with the assignment made to that
variable during the second stage, the trajectory
on which that happens ends in the dead end state that yields reward $0$.
\begin{figure}[ht]
\begin{center}
\input{stage2.pstex_t}
\end{center}
\caption{The second stage of $\mM(\Phi)$: 
$\mA_{3,0}$ for the quantifier prefix 
$\random x_1 \exists x_2 \random x_3 \exists x_4$.}\label{fig-stage2}
\end{figure}
Let $r$ be the number of random quantifiers of $\Phi$.
Every strategy of player 1 determines $2^r$ assignments.
Every assignment $(x_1=b_1,\ldots,x_n=b_n)$ induces
$2n$ trajectories:
$n$ have the form
$$
s_0, x_i\!\!=\!\!b_i, [x_1,b_1],\ldots,[x_i,b_i],\ldots,[x_n,b_n]
$$
(for $i=1,2,\ldots,n$) that pass stage 2 without 
reaching the dead end state and continue with the
first state of the third stage,
and $n$ that dead-end in stage 2.
%Also, the assignment induces $n$ trajectories
The latter $n$ trajectories that do not reach stage 3 are of the form
$$
s_0, x_i\!\!=\!\!b_i, [x_1,b_1],\ldots,[x_i,1-b_i], \send
$$
(for $i=1,2,\ldots,n$). % that do not reach stage 3.
Accordingly,
$M(\Phi)$ has $n\cdot 2^r$ trajectories that reach the third stage.
The structure of stage 2 is sketched for $x_3=0$ in Figure~\ref{fig-stage2}.

The third stage
checks whether $\phi$ is satisfied 
by that trajectory's assignment.
The process passes sequentially through the whole formula
%and asks the controller one literal after the other 
%in each clause after the other
checking each literal in each clause
for an assignment to the respective variable.\footnote{%
We can also regard the interaction between the
process and the policy as an interactive proof system,
where the policy presents a proof and the process
checks its correctness.}
%It must be excluded that the policy cheats,
The case of a \emph{cheating policy},
i.e., one that answers during the third stage with another
assignment than fixed during the second stage,
must be ``punished''.
Whenever the variable corresponding to the initial,
stored assignment appears 
the process checks that the stored assignment
is consistent with the current assignment.
If eventually the whole formula passes the checking,
either reward $2$ or reward $0$
is obtained, depending on whether the formula 
was satisfied and the policy was not cheating, or not.
Let $\mC_{c,b}$ be that instance of the third stage
where it is checked whether $x_c$ always gets assignment $b$.
It is essentially the same deterministic process as defined in
the proof of Theorem~\ref{sfpMDPPp_NP-complete},
but whenever an assignment to a literal containing $x_c$
is asked for, 
if $x_c$ does not get assignment $b$
the process goes to state $s_{\mathit{cheat}}$.
Otherwise, the process goes to state $\send$.
If the assignment chosen by the policy satisfied the formula,
reward $2$ is obtained;
otherwise the reward is $0$.

The overall structure of $\mM(\Phi)$ is
sketched in Figure~\ref{fig-allstages}.
Note that the dashed arrows represent random
transitions (all of equal probability, irregardless
of the action chosen),  solid arrows represent
deterministic transitions corresponding to the action
True, dotted arrows represent deterministic transitions
corresponding to the action False, and dot-dash arrows
represent transitions that are forced, whatever the choice
of action.


\begin{figure}[ht]
\centering
\input{allstages.pstex_t}

\caption{A sketch of $\mM(\Phi)$.}
\label{fig-allstages}
\end{figure}


Consider a formula $\Phi\in\SSAT$ with
variables $x_1,x_2,\ldots,x_n$ and $r$ random quantifiers, and
consider $\mM(\Phi)$.
Because the third stage is deterministic,
the process has $2n\cdot 2^r$ trajectories,
$n\cdot 2^r$ of which reach stage 3.
Now, assume that $\pi$ is a policy,
which is \emph{consistent}
with the observations from the $n$ steps
during the second stage,
i.e., whenever it is ``asked'' to give an assignment
to a variable (during the third stage), 
it does so according to the observations
during the second stage
and therefore it assigns the same value to every appearance
of a variable in $\mC_{k,a}$.
Because $\Phi\in\SSAT$, 
a fraction of more than $1-2^{-c}$ of the trajectories that reach stage 3
correspond to a satisfying assignment
and are continued under this policy $\pi$ 
to state $\send$ where they receive reward 2.
Hence, the history-dependent value of $\mM(\Phi)$ 
is $>\frac{1}{2}\cdot(1-2^{-c})\cdot 2 = 1-2^{-c}$.

For $\Phi\not\in\SSAT$,
an inconsistent (or \emph{cheating}) policy on $M(\Phi)$ 
may have performance greater than $1-2^{-c}$.
Therefore, we have to perform a probability amplification
as in the proof of Theorem~\ref{tfpMDPP_nonapprox}
that punishes cheating.
We construct $M_k(\Phi)$ 
from $k$ copies $M_1,\ldots,M_{k}$ of $M(\Phi)$
(the exact value of $k$ will be determined later),
such that the initial state of $M_k(\Phi)$ 
is the initial state of $M_1$, and
the initial state of $M_{i+1}$ is the final state $\send$ 
of $M_i$.
If in some repetition a trajectory is caught cheating,
then it is sent to the ``penalty box'' and is not continued in the following
repetitions. 
Hence, it cannot collect any more rewards.
More formally,
the states $s_{\mathit{cheat}}$ of all the $M_i$s are identified 
as a unique sink state of $M_k(\Phi)$.

If $\Phi\in\SSAT$,
then in each round (or repetition),
expected rewards $>1-2^{-c}$ can be collected,
and hence the value of $M_k(\Phi)$ 
is $>k\cdot(1-2^{-c})$.

Consider a formula $\Phi\not\in\SSAT$.
Then a non-cheating policy for $M_k(\Phi)$ 
has performance less than $k\cdot 2^{-c}$.
Cheating policies may have better performances.
We claim that for all $k$, the value of $M_k(\Phi)$ 
is at most $k\cdot 2^{-c} + 2n$.
The proof is an induction on $k$.
Consider $M_1(\Phi)$, which has the same value as $M(\Phi)$.
Hence, the value of $M_1(\Phi)$ is at most $1$.
As an inductive hypothesis, let us assume that 
$M_k(\Phi)$ has value at most 
$k\cdot 2^{-c} + 2n$.
In the inductive step, we consider $M_{k+1}(\Phi)$,
i.e. $M(\Phi)$ followed by $M_k(\Phi)$.
Assume that a policy $\pi_j$ cheats on $j$ of the $2^r$ assignments.
{From} the $n$ trajectories that correspond to an assignment,
at least $1$ is trapped for cheating under a cheating 
policy, and at most $n-1$ may obtain reward $2$.  
Then the reward obtained in the first round is at most
$2^{-c} + 2\cdot\frac{j\cdot(n-1)}{2n\cdot 2^r}$,
and the rewards obtained in the following rounds are
multiplied by $1-\frac{j}{2n\cdot 2^r}$,
because a fraction of $\frac{j}{2n\cdot 2^r}$ of the trajectories
are sent to the penalty box.
Using the induction hypothesis, we obtain the following
upper bound for the performance of $M_{k+1}(\Phi)$ under $\pi_j$ 
for an arbitrary $j$.
\begin{eqnarray*}
\perff(M_{k+1}(\Phi),\pi_j) & \leq & 
\bigg(2^{-c} + \frac{j\cdot(n-1)}{n\cdot 2^r}\bigg) 
      + \bigg(1-\frac{j}{2n\cdot 2^r}\bigg) \cdot \val(M_{k}(\Phi)) \\
&\leq& 
\bigg(2^{-c} + \frac{j\cdot(n-1)}{n\cdot 2^r}\bigg) 
      + \bigg(1-\frac{j}{2n\cdot 2^r}\bigg)
 \cdot \bigg(k\cdot 2^{-c} + 2n \bigg)\\
&=&
(k+1)\cdot 2^{-c}+ 2n - \frac{j}{2^r}\cdot
             \bigg(\frac{1}{n}+\frac{k\cdot 2^{-c}}{2n}\bigg) \\
&\leq&
(k+1)\cdot 2^{-c} + 2n
\end{eqnarray*}
This completes the induction step.
Hence, we proved that,
for $\Phi\not\in\SSAT$ and for every $k$,
the value of $M_k(\Phi)$ is 
at most $k\cdot 2^{-c} + 2n$.

Eventually, we have to fix the constants.
We choose $c$ such that $2^c>\frac{\varepsilon-2}{\varepsilon-1}$.
This guarantees that $$(1-\varepsilon)\cdot(1-2^{-c}) - 2^{-c}>0 .$$
Next, we choose $k$ such that
$$
2n < k\cdot((1-\varepsilon)\cdot(1-2^{-c})-2^{-c}) .
$$
Let $\mmhat{\mM(\Phi)}$ 
be the \POMDP that consists of $k$ repetitions of $M(\Phi)$
as described above.
Because $k$ is linear in the number, $n$, of variables of $\Phi$
and hence linear in the length %$|\Phi|$ 
of $\Phi$,
$\Phi$ can be transformed to $\mmhat{\mM(\Phi)}$ in polynomial time.
The above estimates guarantee that
$$
\mbox{value of $\mmhat{M(\Phi)}$ for $\Phi\not\in\SSAT$}
\ \ \leq \ \  k\cdot 2^{-c} + 2n 
\ \ < \ \  (1-\varepsilon)\cdot k\cdot (1-2^{-c}) \ .
$$
The right-hand side of this inequality is a lower
bound for an $\varepsilon$-approximation of the
value of $\mmhat{\mM(\Phi)}$ for $\Phi\in\SSAT$.
Hence,
\begin{itemize}
\item
if $\Phi\in\SSAT$, then $\mmhat{\mM(\Phi)}$ has value 
  $\geq k\cdot(1-2^{-c})$, and
\item if $\Phi\not\in\SSAT$, 
            then $\mmhat{\mM(\Phi)}$ has value 
                       $<(1-\varepsilon)\cdot k\cdot (1-2^{-c})$.
\end{itemize}
Hence, a \polytime $\varepsilon$-approximation
of the value of $\mmhat{\mM(\Phi)}$ shows whether
$\Phi$ is in \SSAT.

Concluding, let $A$ be any set in \PSPACE.
There exists a \polytime function $f$ which maps every instance
$x$ of $A$ to a bounded error stochastic formula 
$f(x)=\Phi_x$ with error $2^{-c}$ and reduces $A$ to \SSAT.
Transform $\Phi_x$ into the \POMDP $\mmhat{\mM(\Phi_x)}$.
Using the $\varepsilon$-approximate value of $\mmhat{\mM(\Phi_x)}$,
one can answer ``$\Phi_x\in\SSAT$?" and hence $x\in A$ in polynomial time.
This shows that $A$ is in $\p$, and consequently $\p=\PSPACE$.
\end{proof}



\begin{coro}
Let $0 \leq  \varepsilon < 1$.
The history-dependent value of \POMDPs 
with general rewards is $\varepsilon$-approximable 
if and only if $\p=\PSPACE$.
\end{coro} 

\newcommand{\AND}{\mbox{\sc AND}}
\newcommand{\OR}{\mbox{\sc OR}}
\newcommand{\NOT}{\mbox{\sc NOT}}
\newcommand{\INPUT}{\mbox{\sc INPUT}}
\newcommand{\noteq}{\not=}


\section{\MDPs}\label{sec:MDP}

Calculating the finite-horizon performance of 
stationary policies is in $\GapL$~\cite{encyclo},
which is a subclass of the class of polynomial time computable functions.
The stationary policy existence problem for \MDPs 
is shown to be $\p$-hard by %Papadimitriou and Tsitsiklis in~
\citeA{PapaTsitsi:86}, 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~\ref{thm:exp-hard-approx} in isolation.

\begin{theorem}\label{thm:approx-MDP}
The problem of $k$-additive approximating the optimal stationary policy
for \MDPs is $\p$-hard.
\end{theorem}

The proof shows this for the case of non-negative rewards;  the
unrestricted case follows immediately.  By Proposition~\ref{additiveIFFPTAS},
this shows that finding a multiplicative approximation
scheme for this problem is also $\p$-hard.

\begin{proof}
Consider the $\p$-complete problem $\CVP$:
given a Boolean circuit $C$ and input $x$, is $C(x)=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, $0$ or $1$.
The gates of type $0$ or $1$ are the input gates, which
represent the bits of the fixed input $x$ to the circuit.
Input gates have indegree $0$.
All NOT gates have indegree $1$, 
and all AND and OR gates have indegree $2$.
There is one gate having outdegree $0$.
This gate is called the output gate, from which
the result of the computation of circuit $C$ on input $x$ can be read.

From such a circuit $C$,
an \MDP $M$ can be constructed as follows.
Because the basic idea of the construction is very similar 
to one shown in~\cite{PapaTsitsi:86}, 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 the output gate.
Reverse all edges of the circuit.
Hence, a transition in $M$ leads from a gate in $C$ to
one of its predecessors.
A transition from an OR gate depends on the action and is deterministic.
On action $0$ 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 $\frac{1}{2}$ the left predecessor is reached,
and with probability $\frac{1}{2}$ 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 $0$ is reached, no reward
is gained, which makes the total expected reward noticeably smaller
than otherwise.
If $C(x)=1$, then the actions can be chosen at the OR gates
so that every trajectory reaches an input gate with value $1$;
if this condition holds, then it must be that $C(x)=1$.
Hence, the \MDP has a large positive value if and only if $C(x)=1$.

If the circuit has NOT gates, we need to remember the parity of
the number of NOT gates on each trajectory.
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 $0$ and $1$ gates is switched.
If a NOT gate is reached, the parity bit is flipped.
For every gate in the circuit, we now take two \MDP states:
one for even and one for odd parity.
Hence, if $G$ is the set of gates in $C$,
the \MDP has states $G\times\{0,1\}$.
The state transition function is
\vspace{2ex}

\noindent
$
\begin{array}{lcl}
t((s,p),a,(s',p')) & = & \left\{\begin{tabular}{lp{0.6\textwidth}}
1, & if ($s$ is an OR gate and $p=0$) or ($s$ is an AND gate and $p=1$),
      $p=p'$, and $s'$ is predecessor $a$ of $s$; \\
$\frac{1}{2}$, & if ($s$ is an OR gate and $p=1$) or ($s$ is an AND gate and $p=0$),
      $p=p'$, and $s'$ is predecessor $0$ of $s$; \\
$\frac{1}{2}$, & if ($s$ is an OR gate and $p=1$) or ($s$ is an AND gate and $p=0$),
      $p=p'$, and $s'$ is predecessor $1$ of $s$; \\
1, & if $s$ is a NOT gate and $s'$ is a predecessor of $s$ and $p'=1-p$; \\
1, & if $s$ is an input gate or the sink state, and $s'$ is the sink state.\\
\end{tabular}\right.

\end{array}
$
\vspace{2ex}

Now we have to specify the reward function.
If an input gate with value $1$ is encountered on a trajectory
where the parity of NOT gates is even,
then reward $2^{|C|+k+1}$ is obtained, 
where $|C|$ is the size of circuit $C$.
The same reward is obtained if an  
input gate with value $0$ is encountered on a trajectory
where the parity of NOT gates is odd.
All other trajectories obtain reward $0$.


Thus each trajectory receives reward either $0$ or $2^{|C|+k+1}$.
There are at most $2^{|C|}$ trajectories for each policy.
If a policy chooses the correct values for all the gates in order
to prove that $C(x)=1$, in other words if $C(x)=1$,
then the expected value of an optimal policy is $2^{|C|+k+1}$.
Otherwise, the expected value is at least $2^{|C|+k+1}/2^{|C|} \geq 2k$
lower than $2^{|C|+k+1}$, i.e., at most $2^{|C|+k+1} -2k$.

Thus, if an approximation algorithm is within an additive constant
$k$ of the optimal policy, it will either give a value 
$\geq 2^{|C|+k+1} -k$ or $< 2^{|C|+k+1} - k$.  By inspection of
the output, one can immediately determine whether $C(x)=1$.
Thus, any $k$-additive approximation for this problem must take at
least polynomial time.

In Figure~\ref{fig-circ-mdp},
an example circuit and the \MDP to which it is transformed are given.
Every gate of the circuit is transformed to two states
of the \MDP: one copy for \emph{even} parity of NOT gates passed on that 
trajectory (indicated by a thin outline of the state)
and one copy for \emph{odd} parity of NOT gates passed on that 
trajectory (indicated by a thick outline of the state).
A solid arrow indicates the outcome of action ``choose the left
predecessor'',
and a dashed arrow indicates the outcome of action ``choose the right 
predecessor''.
Dotted arrows indicate a transition with probability $\frac{1}{2}$ 
on any action.
The circuit in Figure~\ref{fig-circ-mdp} has value $1$.
The policy, which chooses the right predecessor in the starting
state, yields trajectories which all end in an input gate with value
$1$
and which therefore obtains the optimal value.
\end{proof}


\newcommand{\simpleskbild}{
\beginpicture
\setcoordinatesystem units <0.8mm, 0.8mm>
%                  Breite,         Hoehe
\setplotarea x from 20 to 90, y from 15 to 70

\arrow <2mm> [0.375,0.75] from 50 60 to 50 65

\put{$\lor$}[b] at 50 56
\circulararc 180 degrees from 55 55 center at 50 55
\plot 45 55 55 55 /

\arrow <2mm> [0.375,0.75] from 30 45 to 48 55
\arrow <2mm> [0.375,0.75] from 70 45 to 52 55

\put{$\land$}[b] at 30 41
\circulararc 180 degrees from 35 40 center at 30 40
\plot 25 40 35 40 /

\arrow <2mm> [0.375,0.75] from 30 30 to 28 40
\arrow <2mm> [0.375,0.75] from 70 30 to 32 40

\put{$\lneg$}[b] at 70 41
\circulararc 180 degrees from 75 40 center at 70 40
\plot 65 40 75 40 /

\arrow <2mm> [0.375,0.75] from 70 30 to 70 40

\put{$\land$}[b] at 30 26
\circulararc 180 degrees from 35 25 center at 30 25
\plot 25 25 35 25 /

\put{$\lor$}[b] at 70 26
\circulararc 180 degrees from 75 25 center at 70 25
\plot 65 25 75 25 /

\arrow <2mm> [0.375,0.75] from 28 15 to 28 25
\put{$1$}[b] at 28 10

\arrow <2mm> [0.375,0.75] from 50 15 to 32 25
\arrow <2mm> [0.375,0.75] from 50 15 to 68 25
\put{$0$}[b] at 50 10

\arrow <2mm> [0.375,0.75] from 72 15 to 72 25
\put{$0$}[b] at 72 10

\endpicture}


\begin{figure}
\begin{tabular}{@{}c@{}c@{}}
\simpleskbild &
\input{nap-mdp-traj.pstex_t}
\end{tabular}
\caption{A circuit, the \MDP it is reduced to, and the trajectories
according to an optimal policy for the \MDP}\label{fig-circ-mdp}
\end{figure}


There have been several recent approximation algorithms introduced for
structured \MDPs, many of which are surveyed in~\cite{BDH:jair:99}.
More recent work includes a variant of policy iteration 
by % Koller and Parr~
\citeA{koller:uai:00} and heuristic search in
the space of finite controllers by %Hansen and Feng and
%by Kim, et al.~
\citeA{hansen:aips:00} and \citeA{kim:aips:00}.
While these algorithms are often highly effective in reducing the
asymptotic complexity and actual run times of policy construction,
they all run in time exponential in the size of the structured representation,
or offer only weak performance guarantees.
We show that exponential 
asymptotic complexity is necessary for any algorithm scheme
that produces $\varepsilon$-approximations for all $\varepsilon$.
For this, we consider \MDPs represented by 2TBNs~\cite{BDG:ijcai:95}.
%%%XXXXXX THIS NEEDS A BETTER REFERENCE!!!
Until now, we have described the state transition function for MDPs
by a function $t(s,a,s')$ that computes the probability of reaching
state $s'$ from state $s$ under action $a$.  We assumed that the
transition function was represented explicitly.
%Whereas for {\MDP}s we used up to now a state transition function
%which gives the probability $t(s,a,s')$ that we reach state $s'$
%from state $s$ within one step on action $a$,
A \emph{two-phase temporal Bayes net} (2TBN)
is a succinct representation of an \MDP or \POMDP.
Each state of the system is described by a vector of values
called \emph{fluents}.  
(Note that if each of $n$ fluents is two-valued,
 then the system has $2^n$ states.)
Actions are described by the effect they have on each fluent
by means of two data structures. % a dependency graph and a
They are a dependency graph and a set of functions encoded
as conditional probability tables, decision trees, arithmetic 
decision diagrams, or in some other data structure.

The dependency graph is a directed acyclic graph with nodes
partitioned into two sets $\{v_1,\ldots,v_n\}$ and $\{v_1',\ldots,v_n'\}$.
The first set of nodes represents the state
at time $t$, the second at time $t+1$.
The edges are from the first set of nodes to the second (asynchronous)
or within the second set (synchronous).  The value of the
$k^{th}$ fluent at time $t+1$ under action $a$ depends probabilistically on the
values of the predecessors of $v_k'$ in this graph.  
(Note that the synchronous edges must form a directed, acyclic graph
in order for the dependencies to be evaluated.)
The
probabilities are spelled out, for each action, in the corresponding
data structure for $v_k'$ and $a$.
We will indicate that (stochastic) function by $f_k$.

We make no assumptions about the structure of rewards for 2TBNs.
In fact, the final 2TBN constructed in the proof of 
Theorem~\ref{thm:exp-hard-approx} has very large rewards which
are computed implicitly;  in time polynomial in the size of the
2TBN, one can explicitly compute any individual \emph{bit} of the reward.
This has the effect of making the potential {\em value\/} of the 2TBN too
large to write down with polynomially many bits.

\begin{theorem}\label{thm:exp-hard-approx}
The problem of $k$-additive approximating any optimal stationary
policy for an \MDP in 2TBN-representation is \EXP-hard.
\end{theorem}

\begin{proof}
The general strategy is similar to the proof
of Theorem~\ref{thm:approx-MDP}.
We give a reduction from the \EXP-complete 
succinct circuit value problem to the
problem for \MDPs in 2TBN-representation.
An instance of the succinct circuit value problem is
a Boolean circuit $S$ that describes a circuit $C$ and an input $x$,
i.e.~$S$ describes an instance of the ``flat'' circuit value problem.
We can assume that in $C$, each gate is a predecessor to
at most two other gates.%
\footnote{If this is not the case, and $d$ is the maximum out-degree
of a gate, we can replace the circuit by one with maximum out-degree 2
and size at most $\log d$ larger.  Since $d\leq |C|$,
such a substitution will not affect the asymptotic complexity of
any of our algorithms.}
Then every gate in $C$ has four neighbors,
two of which output the input to $C$, and two of which
get the output of $C$ as input (if there are fewer neighbors,
the missing neighbors are set to a fictitious gate 0).
Consider a gate $i$ of $C$.
Say that the output of neighbors $0$ and $1$ is the input to gate $i$,
and the output of gate $i$ is input to neighbors $2$ and $3$.
Now, the circuit $S$ on input $(i,k)$ 
outputs $(j,s)$, where gate $j$ is the $k^{th}$ neighbor
of gate $i$, and $s$ encodes the type of gate $i$
(AND, OR, NOT, 0, and 1).
The idea is to construct from $C$ an \MDP $M$ as in the proof
of Theorem~\ref{thm:approx-MDP}.
However, we do it succinctly.
Hence, we construct from $S$ a 2TBN-representation of an \MDP $M(S)$.
The actions of $M(S)$ are $0$ and $1$, for
choosing neighbor $0$ of the current state-gate, or respectively, 
neighbor $1$.
The states of $M(S)$ are tuples $(i,p,t,r)$ where
$i$ is a gate of $C$, $p$ is the parity bit
--- as in the proof of Theorem~\ref{thm:approx-MDP},
$t$ is the type of gate $i$,
and $r$ is used for a random bit.
Every gate number $i$ is given in binary using --- say --- $l$ bits.
Then, the 2TBN has $l+3$ fluents $i_1,i_2,\ldots,i_{l},p,t,r$.
Let $f_1,f_2,\ldots,f_l,f_p,f_t,f_r$ 
be the stochastic functions that calculate
$i_1',i_2',\ldots,i_{l}',p',t',r'$.
The simplest is $f_r$ for the fluent $r'$
that is used as random bit if from state $i=i_1\cdots i_l$ 
the next state is chosen uniformly at random from
one of the two predecessors of gate $i$ in $C$.
This happens
if the type $t$ of gate $i$ is AND and the parity $p$ is $0$,
or if $t$ is OR and $p$ is $1$.
In these cases, $r'$ determines its value $0$ or $1$ by flipping a coin.
Otherwise, $r'$ equals $1$.
Notice that $r'$ is independent of the action.

%% \begin{center}
%% {\renewcommand{\arraystretch}{1.2}
%% \begin{tabular}{cc|c}
%% $p$ & $t$ & $Prob[f_{r'}(p,t)=1]$ \\ \hline
%% $0$ & AND & $\frac{1}{2}$ \\
%% $1$ & OR  & $\frac{1}{2}$ \\
%% \multicolumn{2}{c|}{otherwise} & 1
%% \end{tabular}
%% }
%% \end{center}

The functions $f_c$ for the fluents $v_c'$
determine the bits of the next states.
If $t$ is an AND and the parity $p$ is even,
then ``randomly'' a predecessor of gate $i$ is chosen.
``Randomly'' means here that the random bit $r'$ 
determines whether predecessor $0$ or predecessor $1$ is chosen.
Hence, $v_c'$ is the $c^{th}$ bit of $j$,
where $(j,s)$ is the output of $S$ on input $(i,r')$.
Accordingly, $t'=s$ is the type of the chosen gate,
and $p'=p$ remains unchanged.
The same happens if $t$ is an OR and the parity $p$ is odd.
If $t$ is a NOT,
there is only one predecessor of $i$, and 
that one must be chosen for $i'$ and $t'$.
The parity bit $p'$ is flipped to $1-p$.
If $t$ is an OR and the parity $p$ is even,
then on action $a\in\{0,1\}$, the predecessor $a$ of gate $i$ is chosen.
Hence, $v_c'$ is the $c^{th}$ bit of $j$,
where $(j,s)$ is the output of $S$ on input $(i,a)$.
Accordingly, $t'=s$ and $p'=p$.
The same happens if $t$ is an AND and the parity $p$ is odd.
Hence, the function $f_c$ can be calculated as follows.

\begin{quote}
\Input $i,p,t,r',a$ \\  
\If ($t=\mathrm{OR}$ and $p=0$) or ($t=\mathrm{AND}$ and $p=1$) \\ \vor
\Then calculate $S(i,a)=(j,s)$; \\ \rueck
\Else \If ($t=\mathrm{OR}$ and $p=1$) or ($t=\mathrm{AND}$ and $p=0$) \\ \vor
\Then calculate $S(i,r')=(j,s)$ \\ \rueck
\Else \If $t=\mathrm{NOT}$ \\ \vor
\Then calculate $S(i,0)=(j,s)$ \\ \rueck
\Else $j=\mathbf{0}$ \\
\Output the $c^{th}$ bit of $j$
\end{quote}

The state $\mathbf{0}$ is a sink state which is reached from
the input gates within one step and which is never left.
The type $t'$ of the next state or gate is calculated accordingly.

One can also simulate the circuit $S$ for function $f_k$
in the above algorithm by a 2TBN.
Note that, in general, circuits can have more than one output.
We consider this more general model here.

\begin{claim}
Every Boolean circuit can be simulated by a 2TBN,
to which it can be transformed in polynomial time. 
\end{claim}

\begin{proofofclaim}
We sketch the construction idea.
Let $R$ be a circuit with $n$ input gates 
and $n'$ output gates.
The outcome of the circuit on any input $b_1,\ldots,b_{n}$
is usually calculated as follows.
At first, calculate the outcome of all gates that get input only 
from input gates.
Next, calculate the outcome of all gates that get their inputs only
from those gates whose outcome is already calculated, and so on.
This yields an enumeration of the gates of a circuit in topological
order, i.e., such
that the outcome of a gate can be calculated when all
the outcomes of gates with a smaller index are already calculated.
We assume that the gates are enumerated
in this way, and that $g_1,\ldots,g_n$ are the input gates,
and that $g_l,\ldots,g_s$ are the other gates, where
the smallest index of a gate which is
neither an output nor an input gate equals $l=\max(n,n')+1$.

Now, we define a 2TBN $T$ simulating $R$ as follows.
$T$ has a fluent for every gate of $R$,
say fluents $v_1,\ldots,v_s$.
The basic idea is that fluents $v_1,\ldots,v_n$ represent
the input gates of $R$.
In one time step, values are propagated from the
input nodes $v_1,\ldots,v_n$ through all gate nodes
$v'_l,\ldots,v'_s$, and the outputs copied to $v'_1,\ldots,v'_{n'}$.
%and after one step in time the fluents 
%$v_l',\ldots,v_s'$ represent the other gates of $R$,
%and the values of the output gates of $R$ are eventually
%copied to the fluents $v_1',\ldots,v_{n'}'$.
The dependency graph has the following edges
according to the ``wires'' of the circuit $R$.
If an input gate $g_i$ ($1\leq i\leq n$) outputs an input to gate $g_j$,
then we get an edge from $v_i$ to $v_j'$.
If the output of a non-input gate $g_i$ ($n < i < s$)
is input to gate $g_j$, then we get an edge from $v_i'$ to $v_j'$.
Finally, the nodes $v_1',\ldots,v_{n'}'$ stand for the value bits.
If gate $g_j$ produces the $i$th output bit, then
there is an edge from $v_j'$ to $v_i'$.
Because the circuit $R$ has no loop, the graph
is loop-free, too.

\newcommand{\skbild}{\beginpicture
\setcoordinatesystem units <1mm, 1mm>
%                  Breite,         Hoehe
\setplotarea x from 0 to 110, y from 0 to 60

%% \put{$\ddot{u}$}[b] at 40 51
\arrow <2mm> [0.375,0.75] from 40 45 to 40 50
\put{output}[b] at 40 55
\put{gate 1}[b] at 40 51
\put{$\land$}[b] at 40 41
\circulararc 180 degrees from 45 40 center at 40 40
\put{$7$}[b] at 47 40
\plot 35 40 45 40 /

%% \put{$s$}[b] at 80 51
\arrow <2mm> [0.375,0.75] from 80 45 to 80 50
\put{output}[b] at 80 55
\put{gate 2}[b] at 80 51
\put{$\lor$}[b] at 80 41
\circulararc 180 degrees from 85 40 center at 80 40
\put{$8$}[b] at 87 40
\plot 75 40 85 40 /


\arrow <2mm> [0.375,0.75] from 65 30 to 78 40
\put{$\land$}[b] at 65 26
\circulararc 180 degrees from 70 25 center at 65 25
\put{$5$}[b] at 72 25
\plot 60 25 70 25 /

\arrow <2mm> [0.375,0.75] from 95 30 to 82 40
\put{$\land$}[b] at 95 26
\circulararc 180 degrees from 100 25 center at 95 25
\put{$6$}[b] at 102 25
\plot 90 25 100 25 /

\arrow <2mm> [0.375,0.75] from 65 20 to 63 25
\put{$\lneg$}[b] at 65 16
\circulararc 180 degrees from 70 15 center at 65 15
\put{$3$}[b] at 72 15
\plot 60 15 70 15 /

\arrow <2mm> [0.375,0.75] from 95 20 to 97 25
\put{$\lneg$}[b] at 95 16
\circulararc 180 degrees from 100 15 center at 95 15
\put{$4$}[b] at 102 15
\plot 90 15 100 15 /


\plot 50 3 50 5 38 5 /
\arrow <2mm> [0.375,0.75] from 38 5 to 38 40
\plot 50 5 50 7 /
\circulararc 180 degrees from 50 7 center at 50 8
\plot 50 9 50 10 /
\plot 50 10 75 10 /
\arrow <2mm> [0.375,0.75] from 65 10 to 65 15
%% \arrow <2mm> [0.375,0.75] from 75 10 to 93 25
\arrow <2mm> [0.375,0.75] from 79 12 to 93 25
\circulararc 180 degrees from 75 10 center at 77 11

\put{input}[b] at 50 -1
\put{gate 1}[b] at 50 -4

%\plot 80 5 80 8 42 8 /
\plot 80 3 80 8 42 8 /
\arrow <2mm> [0.375,0.75] from 42 8 to 42 40
\plot 80 8 95 8 /
\arrow <2mm> [0.375,0.75] from 95 8 to 95 15
\arrow <2mm> [0.375,0.75] from 80 8 to 67 25

%\put{$3$}[b] at 87 0
%\circulararc 180 degrees from 85 0 center at 80 0
%\put{$0/1$}[b] at 80 0
%\plot 85 0 75 0 /

\put{input}[b] at 80 -1
\put{gate 2}[b] at 80 -4

\endpicture
}  % end of \skbild

\newcommand{\funktionstabellen}{%
\put(5000,-1200){
$f_1: \begin{array}{c|c}
       v_8' & {Prob}[v_1'=1]) \\ \hline
        0  & 0 \\
        1  & 1 \\
         \end{array}$
}

\put(5000,-2500){
$f_3: \begin{array}{c|c}
        v_1 & {Prob}[v_3'=1] \\ \hline
         0   & 1 \\
         1   & 0 \\
         \end{array}$
}

\put(5000,-3800){
$f_5: \begin{array}{cc|c}
        v_2 & v_3' & {Prob}[v_5'=1] \\ \hline
         0   & 0 & 0 \\
         0   & 1 & 0 \\
         1   & 0 & 0 \\
         1   & 1 & 1 \\
         \end{array}$
}


\put(5000,-5500){
$f_8: \begin{array}{cc|c}
      v_5' & v_6' & {Prob}[v_8'=1] \\ \hline
       0  &  0  & 0 \\
       0  &  1  & 1 \\
       1  &  0  & 1 \\
       1  &  1  & 1 \\
         \end{array}$
}

}

\begin{figure}

\skbild
\mbox{}\vspace{4ex}\mbox{}

\mbox{}\hspace{1cm}
%\input{nap-2tbn-fixed.pstex_t}
\input{nap-2tbn.pstex_t}

\vspace{4ex}

\caption{A Boolean circuit which outputs the binary sum of its input bits,
and a 2TBN representing the circuit. Only functions
$f_1$ (the identity function), 
$f_3$ (simulating a NOT gate),
$f_5$ (simulating an AND gate), and
$f_8$ (simulating an OR gate)
are described).}
\label{fig-halbaddierer}
\end{figure}


The functions associated to the nodes $v_1',\ldots,v_{s}'$
depend on the functions calculated by the
respective gate and are as follows.
Each of the value nodes $v_i'$ for $i=1,2,\ldots,n'$,
which stands for the input bits,
has exactly one predecessor, whose value is copied into $v_i'$.
Hence, $f_i$ is the one-place identity function, 
$f_i(x)=x$ with probability $1$, for $i=1,2,\ldots,n'$.
Now we consider the nodes which come from internal gates of the circuit.
If $g_i$ is an AND gate,
then $f_i(x,y)= x\wedge y$, where $x$ and $y$ are the predecessors
of gate $g_i$.
If $g_i$ is an OR gate, then $f_i(x,y)= x\vee y$,
and if $g_i$ is a NOT gate, then $f_i(x)= \neg x$,
all with probability $1$.

By this construction, it follows that 
the 2TBN $T$ simulates the Boolean circuit $R$.
Notice that the number of fluents of $T$ is at most the
double of the number of gates of $R$.
The transformation from $R$ to $T$ can be performed in polynomial time.
\end{proofofclaim}

An example of a Boolean circuit and the 2TBN
to which it is transformed as described above
is given in Figure~\ref{fig-halbaddierer}.

Now, we can construct from the circuit $S$ 
that is a succinct representation of a circuit $C$
a 2TBN $T_S$ with fluents $i_1,i_2,\ldots,i_{l},p,t,r$ as
already defined, plus additional fluents for the gates of $S$,
using the technique from the above Claim.
Taking the action $a$, the parity $p$, the gate type $t$
and the random bit $r'$ into account,
we can construct $T_S$ ---
according to the description of function $f_c$ above ---
so that fluent $v_{j_c}'$
contains the bit described by 
the function $f_c(i_1,i_2,\ldots,i_{l},p,t,r)$ above.
Notice that the function $f_{j_c}$ for $v_{j_c}'$
is dependent only on the predecessors of
the gate of $S$ represented by $v_{j_c}'$,
the fluents $p,t,r',$ and the action $a$.
Hence, it has at most $6$ arguments and can be described by a small table.
This holds for all fluents of $T_S$.
Finally, the function $f_c$ for $T_S$ 
just copies the value of $v_{j_c}'$ into $v_c'$.
Hence, from $S$ we can construct a 
\MDP in 2TBN representation similar to the \MDP in the
proof of Theorem~\ref{thm:approx-MDP}.
Next, we specify the rewards of this \MDP.
The reward is $2^{2^{|S|+k+1}}$
if any action is taken on 
a state representing an input gate with value $1$ and parity $0$,
or with value $0$ and parity $1$.
Otherwise, the reward equals $0$.
This reward function can be represented by a circuit,
which on binary input $i,a,b$ outputs the $b^{th}$ bit
of the reward obtained in state $i$ on action $a$.
(Since it requires ${2^{|S|+k+1}}$
bits to represent the reward, $b$ can be represented using only 
$|S|+k+1$ bits.)

If $C(x)=1$, then there is a choice of actions for each state
that gives
reward $2^{2^{|S|+k+1}}$ on every trajectory, similar to the
proof of Theorem~\ref{thm:approx-MDP}.
However, if $C(x)=0$, any policy has at least one trajectory that
receives a 0 reward.
Now, there are at most $2^{2^{|S|}}$ trajectories,
and therefore there is a gap of 
at least $2^{2^{|S|+k+1}}/2^{2^{|S|}}\geq 2k$
between possible values.  
As above, we conclude that any $k$-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.
\end{proof}

%According to Theorem~\ref{additiveIFFPTAS},
%we obtain the following Corollary to Theorem~\ref{thm:exp-hard-approx}.
%
%\begin{coro}
%Any approximation scheme for the factored \MDP
%value problem requires time exponential in the size of the input.
%\end{coro}
%
%A 2TBN-representation for an \MDP can be polynomial-transformed
%to a representation 
%by probabilistic STRIPs operators (PSOs) and vice versa~\cite{Litt:97}.
%Thus, any upper bound and any lower bound 
%on the complexity of \MDP problems represented
%by 2TBNs translates immediately to a respective bound on the complexity
%of PSOs.
%
The following structured representation is more general than 
the representations more
common to the AI/planning community.  We say that an \MDP has a 
\emph{succinct representation}, or is a succinct \MDP, if there are
Boolean circuits $C_t$ and $C_r$ such that $C_t(s,a,s',i)$ produces 
the $i$th bit of the transition probability $t(s,a,s')$ and $C_r(s,a,i)$ 
produces the $i$th bit of the reward $r(s,a)$.
Similar to the proof of Theorem~\ref{thm:exp-hard-approx},
we can also prove nonapproximability of \MDP values 
for succinctly represented \MDPs.

\begin{theorem}
The problem of $k$-additive approximating the optimal stationary
policy for a succinctly represented \MDP is \EXP-hard.
\end{theorem}


\section{Non-Approximability for Infinite-Horizon POMDPs}\label{sec:inf}

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 \emph{$\alpha,\beta$-value} $\val_{\alpha,\beta}(M)$ of $M$ is
$M$'s maximal $\beta$-performance under any policy $\pi$
of type $\alpha$,
i.e.~$\val_{\alpha,\beta}(M)=\max_{\pi\in\Pi_{\alpha}}\perf_{\beta}(M,\pi)$.

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.~\citeNP{Puterman:book})
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, Hanks, and Condon~
\citeA{madani:aaai:99} 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.

\begin{theorem}
The stationary infinite-horizon policy-existence problem for POMDPs
under total discounted or average performance is $\NP$-complete.
\end{theorem}

The hardness proof is essentially the same 
as for Theorem~\ref{sfpMDPPp_NP-complete}.
Note that in that construction,
every stationary policy obtains reward $1$ for at most one step,
namely when sink state $T$ is reached, meaning that the formula is satisfied.
All other steps yield reward $0$.
Therefore, for this construction,
the total discounted value is greater than $0$
if and only if the finite-horizon value is so. 
To make the construction work for average value,
we have to modify it such that
once the sink state $T$ is reached, every subsequent action
brings reward $1$.
%every action performed in the sink state $T$ obtains reward $1$.
Therefore, the average value equals $1$ if the formula is satisfiable,
and it equals $0$ if it is unsatisfiable.
Hence, both the problems are $\NP$-hard.

Containment in $\NP$ for the total discounted performance
follows from the guess-and-check approach:
Guess a stationary policy, calculate its performance
and accept if and only if the performance is positive.
The total discounted and the average performance 
can both be calculated in polynomial time.


In the same way, the techniques proving nonapproxima\-bility results
for the stationary policy in the finite horizon case 
(Corollary~\ref{sfpMDPP_nonapprox})
can be modified to obtain nonapproxima\-bility results
for infinite horizons.

\begin{theorem}
The stationary infinite-horizon value of {\POMDP}s
under total discounted or average performance
can be $\varepsilon$-appro\-xi\-mated  
if and only if \mbox{$\p=\NP$}. 
\end{theorem}

The infinite-horizon time-dependent policy-existence problems
are undecidable~\cite{madani:aaai:99}.
We show that no computable function can even approximate optimal policies.

\begin{theorem} 
The time-dependent infinite-horizon value of unobservable POMDPs   
under average performance 
cannot be $\varepsilon$-appro\-xi\-mated.
\end{theorem} 
 

The proof follows from the proof by %Madani et al.~
\citeA{madani:aaai:99}
showing the uncomputability of the time-dependent value.
In %Madani et al.~
\citeA{madani:aaai:99},
from a given Turing machine $T$ an unobservable POMDP is constructed
having the following properties for arbitrary $\delta>0$.
(1) If $T$ halts on empty input,
then there is exactly one time-dependent infinite-horizon policy
with performance $\geq 1-\delta$, 
(2) all other time-dependent policies have performance $\leq \delta$,
and (3) the average value is between $0$ and $1$.
This reduces the undecidable problem of whether a Turing machine halts on
empty input to the time-dependent infinite-horizon policy existence problem
for unobservable POMDPs under average performance.
Actually, assuming that the value of the unobservable POMDP 
were $\varepsilon$-approximable,
we could choose $\delta$ in a way that even the approximation
enables us to decide whether $T$ halts on empty input.
Since this is undecidable, an $\varepsilon$-approximation is impossible.

\begin{coro}
The time-dependent and history-dependent 
infinite-horizon value of {\POMDP}s    
under average performance  
cannot be $\varepsilon$-appro\-xi\-mated.
\end{coro}


\section*{Acknowledgements}
This work was supported 
in part by NSF grant CCR-9315354 and CCR-9610348 (Lusena and Goldsmith),
and by Deutscher Akademischer Austauschdienst (DAAD) grant 315/PPP/ g\"u-ab
(Mundhenk).
The third author performed part of the work at Dartmouth College.

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


\appendix\label{app:stat-reduct}
\section{Proof of Theorem~\ref{sfpMDPPp_NP-complete}}\label{stat-reduct}

We present the reduction from~\cite{encyclo}.
Let $\phi(x_1,\ldots,x_n)$ be an instance of $\THREESAT$
with variables $x_1,\ldots,x_n$
and clauses $C_1,\ldots,C_m$,
where clause $C_j=(l_{v(1,j)}\vee l_{v(2,j)} \vee l_{v(3,j)})$
for $l_i\in\{x_i,\lneg x_i\}$.
We say that variable $x_i$
{\em appears in $C_j$ with signum $0$ (resp.~$1$)}
if $\lneg x_i$ (resp.~$x_i$) is a literal in $C_j$.

{From} $\phi$,we construct a
\POMDP\ $M(\phi)=(\cS,s_0,\cA,\cO,t,o,r)$ with

\noindent
$
\begin{array}{cclcclccl}
\cS & = & \multicolumn{7}{l}{\{(i,j)\mid
          1\leq i\leq n, 1\leq j\leq m\}\cup\{F,T\}} \\
s_0 & = & (v(1,1),1),  \hspace{4ex}&
\cA & = & \{0,1\}, \hspace{4ex}&
\cO & = & \{x_1,\ldots,x_n,F,T\}
\end{array}
$
 
\noindent
$
\begin{array}{ccll}
t(s,a,s') & = & \multicolumn{2}{l}{\left\{ \begin{array}{ll}
1, & \mbox{ if } s=(v(i,j),j), s'=(v(1,j+1),j+1), j<m, 1\leq i\leq 3,\\
   &  \hspace{18ex} \mbox{and $x_{v(i,j)}$ appears in $C_j$ with signum $a$}\\
1, & \mbox{ if } s=(v(i,m),m), s'=T, 1\leq i\leq 3, \\
   &  \hspace{18ex} \mbox{and $x_{v(i,m)}$ appears in $C_m$ with signum $a$}\\
1, & \mbox{ if } s=(v(i,j),j), s'=(v(i+1,j),j), 1\leq i<3, \\
   &  \hspace{18ex}\mbox{and $x_{v(i,j)}$ appears in $C_j$ with signum $1-a$}\\
1, & \mbox{ if } s=(v(3,j),j), s'=F, \\
   &  \hspace{18ex}\mbox{and $x_{v(3,j)}$ appears in $C_j$ with signum $1-a$}\\
1, & \mbox{ if } s=s'=F \mbox{ or } s=s'=T \\
0, & \mbox{ otherwise}
\end{array} \right. }\\[4ex]
%\end{array}
%$
%
%$
%\begin{array}{ccl}
r(s,a) & = & \left\{ \begin{array}{ll}
1, & \mbox{ if } t(s,a,T)=1, s\not=T \\
0, & \mbox{ otherwise }\\
\end{array} \right.
,\hspace{4ex} &
\begin{array}{ccl}
o(s) & = & \left\{ \begin{array}{ll}
x_i, & \mbox{ if } s=(i,j)\\
T, & \mbox{ if } s=T \\
F, & \mbox{ if } s=F \ \ .\\
\end{array} \right. \end{array} \\[4ex]
\end{array}
$
 
Note that all transitions in $M(\phi)$ are deterministic,
and every trajectory has value $0$ or $1$.
There is a correspondence between
policies for $M(\phi)$ and assignments of values to the variables of $\phi$,
such that policies under which $M(\phi)$ has value $1$
correspond to satisfying assignments for $\phi$, and vice versa.


\section{Proof of Theorem~\ref{time-exi-NPcomplete}}\label{time-reduct}
 
Again, we present the reduction from~\cite{encyclo}.
Let $\phi$ be a formula with $n$ variables $x_1,\ldots,x_n$
and $m$ clauses $C_1,\ldots,C_m$.
%We say that $x_i$ appears in $C_j$ with signum $1$
%if $x_i\in C_j$, and with signum $0$ if $\neg x_i\in C_j$.
This time, we define the unobservable MDP $M(\phi)=(\cS,s_0,\cA,t,r)$ where
 
\noindent
\begin{eqnarray*}
\fofbox\cS  &=&  \{(i,j)\mid 1\leq i\leq n, 1\leq j\leq m\} 
           \cup\{sat_{i}\mid 1\leq i\leq n\} \cup \{s_0,T,F\} \\
\fofbox\cA  &= & \{0,1\}\\ 
\fofbox{t(s,a,s')}& = & \left\{ \begin{array}{ll}
\frac{1}{m}, & \mbox{ if } s=s_0, s'=(1,j), 1\leq j\leq m \\
1, & \mbox{ if } s=(i,j), s'=sat_{i+1}, i<n,
        \mbox{ $x_i$ appears in $C_j$ with signum $a$}\\

1, & \mbox{ if } s=(i,j), s'=(i+1,j), i<n, \\ 
   & \qquad     \mbox{ $x_i$ does not appear in $C_j$ with signum $a$}\\
1, & \mbox{ if } s=(n,j), s'=T,
        \mbox{ $x_n$ appears in $C_j$ with signum $a$}\\
1, & \mbox{ if } s=(n,j), s'=F,
        \mbox{ $x_n$ does not appear in $C_j$ with signum $a$}\\
1, & \mbox{ if } s=sat_i, s'=sat_{i+1}, i<n\\
1, & \mbox{ if } s=sat_n, s'=T\\
1, & \mbox{ if } s=s'=F \mbox{ or } s=s'=T, a=0 \mbox{ or } a=1\\
0, & \mbox{ otherwise}
\end{array} \right. \\
\fofbox{r(s,a)} & =&  \left\{ \begin{array}{ll}
m, & \mbox{ if } s\not=T \mbox{ and } t(s,a,T)>0 \\
0, & \mbox{ otherwise\ .}
\end{array} \right.
\end{eqnarray*}


\bibliography{Marko2}
%\bibliographystyle{plain}
\bibliographystyle{apacite}

\end{document}





