\documentclass[11pt]{article}
\usepackage{jair,theapa,psfig,epsfig,latexsym}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Claim}
\newtheorem{fact}{Fact}
\newtheorem{definition}{Definition}
\newtheorem{assumption}{Assumption}
\newtheorem{observation}{Observation}
\newtheorem{example}{Example}
\newcommand{\qed}{\rule{7pt}{7pt}}
\newcommand{\real}{\hbox{\it I\hskip -2pt R}}

\newcommand{\necpos}[1]{[\langle #1 \rangle]}
\newcommand{\proof}[1]{\medskip \noindent {\bf Proof} \mbox{\vspace{0.2cm}} #1 \mbox{\vspace
{0.2cm}} $\Box$ \medskip}
\newcommand{\commentout}[1]{}
\newcommand{\mynote}[1]{\begin{center}\fbox{\parbox{5in}{#1}}\end{center}}
\newcommand{\card}[1]{|#1|}
\newcommand{\next}{\mbox{next}}
\newcommand{\action}{\mbox{action}}
 

\jairheading{13}{2000}{33--94}{9/99}{8/00}
\ShortHeadings{Value-Function Approximations for POMDPs}{Hauskrecht}
\firstpageno{33}

% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
\begin{document}
\title{Value-Function Approximations for Partially Observable Markov
Decision Processes} 
\author {\name Milos Hauskrecht \email{milos@cs.brown.edu} \\
\addr{Computer Science Department, Brown University\\
Box 1910, Brown University, Providence, RI 02912, USA} 
%%% \email{milos@cs.brown.edu}
         }


\maketitle 
\medskip
\medskip

%%%%% ABSTRACT %%%%%%%%

\begin{abstract}

Partially observable Markov decision processes (POMDPs)
provide an elegant mathematical framework for modeling complex decision and planning problems in stochastic domains in which states of the
system are observable only indirectly, via a set of imperfect or
noisy observations. The modeling advantage of POMDPs, however, comes at a price --- exact methods for solving them are computationally very
expensive and thus applicable in practice only to very simple problems.
We focus on efficient approximation (heuristic) methods
that attempt to alleviate the computational problem and trade off accuracy
for speed. We have two objectives here. First, we survey various
approximation methods, analyze their properties and relations and provide
some new insights into their differences. Second, we present a number of new
approximation methods and novel refinements of existing techniques. The
theoretical results are supported by experiments on a problem from the
agent navigation domain.     

\end{abstract}


%%%%%%% INTRODUCTION %%%%%%%%

\section{Introduction}

Making decisions in dynamic environments requires careful evaluation of the
cost and benefits not only of the immediate
action but also of choices we may have in the future. This
evaluation becomes harder when the effects of actions are stochastic, so
that we must pursue and evaluate
many possible outcomes in parallel. Typically, the problem becomes more
complex the further we look into the future. The situation becomes even worse
when the outcomes we can observe are imperfect or
unreliable indicators of the underlying process and special actions are
needed to obtain more reliable information. Unfortunately, many real-world
decision problems fall into this category.

Consider, for example, a problem of patient management. The patient comes
to the hospital with an initial set of complaints. Only rarely
do these allow the physician (decision-maker) to diagnose the underlying disease with
certainty, so that a number of disease options generally remain open after the initial
evaluation. The physician has multiple choices in managing the patient. 
He/she
can choose to do nothing (wait and see), order additional tests 
and learn more about the patient state and disease, 
or proceed to a more radical treatment (e.g. surgery). 
Making the right decision is not an easy task. The disease the patient
suffers can progress over time and may 
become worse if the window of opportunity for a particular effective treatment is missed. On the other hand, selection of the wrong treatment may make the patient's condition worse,
or may prevent applying the correct treatment
later. The result of the treatment is typically non-deterministic and more
outcomes are possible. In addition, both treatment and investigative
choices come with different costs.  Thus, in a course of patient management,
the decision-maker must carefully evaluate the costs and benefits of both
current and future choices, as well as their interaction and ordering. 
Other decision problems with similar characteristics --- complex temporal cost-benefit
tradeoffs, stochasticity, and partial observability of the underlying
controlled process --- include robot navigation, target tracking,
machine mantainance and replacement, and the like.  

%%% , two sources of 
%%% uncertainty the decision-maker should tackle: action-outcome
%%% uncertainty in which we try to optimize our 
%%% decisions with regard to the about include in robot
%%% navigation, Robot navigation, target tracking, maintainance and
%%% replacement are typical examples. 


Sequential decision problems can be modeled as {\em Markov decision
processes (MDP}s{\em)} \cite{Bellman57,Howard60,Puterman94,BDH:jair99} and
their extensions. The model of choice for problems similar to patient
management 
%%% in stochastic, partially observable domains 
is the {\em partially observable Markov decision process (POMDP)}
\cite{Drake62,Astrom65,Sondik:thesis,Lovejoy:survey}. The POMDP 
%%% allows us to 
represents two sources of uncertainty: stochasticity of %%%  behavior of
the underlying controlled process (e.g. disease dynamics in the patient
management problem), and imperfect observability of its states via a set of noisy
observations (e.g. symptoms, findings, results of tests). In addition, it
lets us model in a uniform way 
both control and information-gathering (investigative) actions, as well as
their effects and cost-benefit trade-offs.
Partial observability and
the ability to model and reason with information-gathering actions are the main features that
distinguish the POMDP from the widely known {\em fully observable Markov
decision process} \cite{Bellman57,Howard60}.

Although useful from the modeling perspective, POMDPs have the disadvantage
of being hard to solve \cite{Papadimitriou87,Littman:thesis,Mundhenk:TR97,Madani:aaai99}, and optimal or 
$\epsilon$-optimal solutions can be obtained in practice only for problems
of low complexity. A challenging goal in this research area is to 
exploit additional structural properties of the domain and/or
suitable approximations (heuristics) that can be used to
obtain good solutions more efficiently. 

We focus here on heuristic approximation methods, in particular
approximations based on value functions. Important research issues in
this area are the design of new and efficient algorithms, as well as 
a better understanding of the existing techniques and their relations,
advantages and disadvantages. In this paper we address both of these
issues. First, we survey various value-function approximations, analyze
their properties and relations and provide some insights into their
differences. Second, we present a number of new methods and novel
refinements of existing techniques. 
%%% like the fast informed bound method, or
%%% adaptive grid refinement strategies. 
The theoretical results and findings are also supported empirically
on a problem from the agent navigation domain.  


%%%%%%%%%%%% POMDP %%%%%%%%%%%%

\section{Partially Observable Markov Decision Processes}

A {\em partially observable Markov decision process (POMDP)} describes a
stochastic control process with partially observable (hidden)
states. Formally, it corresponds to a tuple $(S, A, \Theta, T, O, R)$ where
$S$ is a set of states, $A$ is a set of actions,  $\Theta$ is a set
of observations, $T: S \times A \times S \rightarrow [0, 1]$ is a set of
transition probabilities that describe the dynamic behavior of the modeled
environment, $O: S \times A \times \Theta \rightarrow [0, 1]$ is a set of
observation probabilities that describe the relationships among
observations, states and actions,  and $R: S \times A \times S \rightarrow
\real$ denotes a reward model that assigns rewards to state transitions
and models payoffs associated with such transitions. 
%%% (the alternative model can include costs).  
In some instances the definition of a POMDP also includes an {\em a priori}
probability distribution over the set of initial states $S$.

\subsection{Objective Function}

Given a POMDP, the goal is to construct a {\em control policy} that maximizes
an {\em objective (value) function}. The objective function combines
partial (stepwise) rewards over multiple steps using various kinds of decision
models. Typically, the models are cumulative and based on
expectations. Two models are frequently used in practice:
\begin{itemize} 
\item a {\em finite-horizon} model in which we maximize  $E(\sum_{t=0}^{T}
r_t)$, where $r_t$ is a reward obtained at time $t$.
\item an {\em infinite-horizon discounted} model in which we maximize 
$E(\sum_{t=0}^{\infty} \gamma ^t r_t)$, where $0< \gamma < 1$ is a
discount factor.
\end{itemize}
Note that POMDPs and cumulative decision models provide a rich
language for modeling various control objectives. For example, one can easily
model goal-achievement tasks (a specific goal must be reached) by giving
a large reward for a transition to that state and zero or smaller rewards
for other transitions.  

In this paper we focus primarily on discounted infinite-horizon
model. However, the results can be easily applied also to the
finite-horizon case. 


\subsection{Information State}

\begin{figure}
\begin{center}
\mbox{ \epsfxsize 0.5\textwidth \epsffile{./FIGURE/inf-diag.ps}}
\caption{Part of the influence diagram describing a POMDP
model. Rectangles correspond to decision nodes (actions), circles to random
variables (states) and diamonds to reward nodes. Links represent the
dependencies among the components. $s_t, a_t, o_t$ and $r_t$ denote 
state, action, observation and reward at time $t$. Note that an action at
time $t$ depends only on past observations and actions, not on states.}
\label{fig:POMDP-influence-diagram}
\end{center}
\end{figure}

In a POMDP the process states are hidden
and we cannot observe them while making a decision about the next action. Thus,
our action choices %% (and subsequently the policy) 
are based only on the information available to us or on quantities derived
from that information.  This is 
illustrated in the influence diagram in Figure
\ref{fig:POMDP-influence-diagram}, where the action at 
time $t$ depends only on previous observations and actions, not
on states. Quantities summarizing  all information are called {\em information
states}. {\em Complete information states} represent a trivial case. 


%%% In the simplest case, an information state corresponds to the
%%% complete history of actions and observations, or the {\em complete
%%% information state}.  

{\definition {(Complete information state). The complete
information state at time $t$ (denoted $I^{C}_t$) consists of:
\begin{itemize}
\item a prior belief $b_0$ on states in $S$ at time $0;$
\item a complete history of actions and observations 
$\{o_{0},a_{0},o_{1}, a_{1}, \cdots, o_{t-1}, a_{t-1}, o_{t}\}$ starting from time $t=0$.
\end{itemize}
}}

A sequence of information states defines a controlled Markov process that
we call an {\em information-state Markov decision process}
or {\em information-state MDP}. 
The policy for the information-state MDP is defined in terms of a control function
$\mu: {\cal I} \rightarrow A$ mapping information state space  to
actions.
The new information state ($I_t$) is a deterministic
function of the previous state ($I_{t-1}$), the last action ($a_{t-1}$) and the new
observation ($o_t$):
$$I_{t} = \tau(I_{t-1}, o_{t}, a_{t-1}).$$
%% where $I_{t}$ and $I_{t-1}$ denote the new and the previous information states and 
$\tau: {\cal I} \times \Theta \times A \rightarrow {\cal I}$ is the {\em
update function}  mapping the information state space, observations and
actions back to the information space.{\footnote {In this paper, $\tau$ denotes the generic update
function. Thus we use the same symbol even if the information state space is different.}}
It is easy to see that one can always convert the original 
POMDP into the information-state MDP by using complete information
states. The relation between the components of the two models and a sketch
of a reduction of a POMDP to an information-state 
MDP,  are shown in Figure \ref{fig:POMDP-influence-information}. 

\begin{figure}
\begin{center}
\mbox{ \epsfxsize 0.8\textwidth \epsffile{./FIGURE/inf-info.ps}}
\caption{Influence diagram for a POMDP with information states and
corresponding information-state MDP. Information states ($I_t$ and
$I_{t+1}$) are represented by double-circled nodes. An action choice (rectangle)
depends only on the current information state.} 
\label{fig:POMDP-influence-information}
\end{center}
\end{figure}


\subsection{Bellman Equations for POMDPs}

An information-state MDP for the infinite-horizon discounted case is like a
fully-observable MDP and satisfies the standard fixed-point (Bellman) equation:
\begin{equation}
V^{*}(I) = \max_{a \in A} \left \{\rho(I, a)+ \gamma \sum_{I'}
P(I'|I,a)V^{*}(I') \right \}. \label{eq:POMDP-n-step-to-go-complete-IF}
\end{equation}
Here, $V^{*}(I)$ denotes the optimal value function maximizing
$E(\sum_{t=0}^{\infty} \gamma ^t r_t)$ for state $I$. 
$\rho(I, a)$ is the expected one-step reward and equals
$$ \rho(I, a) = \sum_{s \in S} \rho(s,a) P(s|I) = \sum_{s
\in S} \sum_{s' \in S} R(s, a, s')P(s'|s,a) P(s|I).$$
$\rho(s,a)$ denotes an expected one-step reward for state $s$ and action $a$.

Since the next information state $I'=\tau(I, o, a)$ is a deterministic
function of the previous information state $I$, action $a$, and the
observation $o$, the Equation
\ref{eq:POMDP-n-step-to-go-complete-IF} can be 
rewritten more compactly by summing over all possible observations $\Theta$: 
\begin{equation}
V^{*}(I) =  \max_{a \in A}  \left \{ \sum_{s \in S} \rho(s,a)P(s|I) +
\gamma \sum_{o \in \Theta} P(o| I, a) V^{*}(\tau(I, o, a))  \right \}. \label{eq:POMDP-n-step-to-go-IF}
\end{equation}
%%% where $\Theta$ is the set of all possible observations. 
The optimal policy
(control function) $\mu^{*}: {\cal I} \rightarrow A$ selects the
value-maximizing action  
\begin{equation}
\mu^{*}(I)= \arg\max_{a \in A} \left \{\sum_{s \in S}
\rho(s,a)P(s|I) + \gamma \sum_{o \in \Theta} P(o|I,a) V^{*}(\tau(I, o,
a)) \right \}. \label{eq:POMDP-n-step-to-go-control}  
\end{equation}

The value and control functions can be also expressed in terms of
{\em action-value functions (Q-functions)}
\begin{eqnarray}
V^{*}(I) = \max_{a \in A} Q^{*}(I,a) \mbox{ \hspace{1.5cm} } \mu^{*}(I)=
 \arg\max_{a \in A} Q^{*}(I,a), \nonumber \\
Q^{*}(I,a)= \sum_{s \in S}
\rho(s,a)P(s|I) + \gamma \sum_{o \in \Theta} P(o|I,a) V^{*}(\tau(I, o,
a)).\label{eq:V-Q-relation}
\end{eqnarray}
A {\em Q}-function corresponds to the expected reward for chosing a fixed action ($a$)
in the first step and acting optimally afterwards. 


\subsubsection{Sufficient Statistics}

To derive Equations
\ref{eq:POMDP-n-step-to-go-complete-IF}---\ref{eq:POMDP-n-step-to-go-control}
we implicitly used complete information states. However, as remarked earlier,
the information available to the decision-maker can be also summarized by
other quantities. We call them
{\em sufficient information states}. Such states must preserve the necessary
information content and also the Markov property of the information-state
decision process. 


{\definition {(Sufficient information state process).  Let ${\cal I}$ be an
information state space and $\tau:{\cal I} \times A \times \Theta
\rightarrow {\cal I}$ be an update function defining an information process
$I_t= \tau(I_{t-1}, a_{t-1}, o_t)$. The process is sufficient with regard to the optimal
control when, for any time step $t$, it satisfies 
$$P(s_{t}|I_{t}) = P(s_{t}|I^{C}_{t})$$
$$P(o_{t}|I_{t-1}, a_{t-1}) = P(o_{t}|I^{C}_{t-1}, a_{t-1}),$$
where $I^{C}_{t}$ and $I^{C}_{t-1}$ are complete information states. }} 
\medskip

It is easy to see that Equations \ref{eq:POMDP-n-step-to-go-complete-IF}
--- \ref{eq:POMDP-n-step-to-go-control} 
for complete information states must hold also for sufficient
information states. 
%% Thus, the optimal value function and optimal policy can
%% also be expressed in terms of the sufficient statistics. 
The key benefit of sufficient statistics is that they are often easier to 
manipulate and store, since unlike complete
histories, they may not expand with time. For example, in the standard POMDP model it is sufficient to
work with belief states that assign probabilities to every possible process state \cite{Astrom65}.{\footnote {Models in which belief states are not sufficient include
POMDPs with observation and action channel lags (see Hauskrecht \citeyear{Hauskrecht:thesis}).}}
In this case the Bellman equation reduces to:
\begin{equation} 
V(b) =  \max_{a \in A} \left \{\sum_{s \in S} \rho(s,a) b(s) + \gamma \sum_{o \in
\Theta} \sum_{s \in S} P(o| s, a) b(s) V(\tau(b, o,
a)) \right \}, \label{eq:POMDP-inf-belief} 
\end{equation}
where the next-step belief state $b'$ is
%%% update for a belief space 
$$b'(s) = \tau(b, o, a)(s) = \beta P(o|s,a) \sum_{s' \in S} P(s|a,s')b(s').$$ 
$\beta = 1/P(o|b,a)$ is a normalizing constant. This defines a {\em
belief-state MDP} which is a special case of a
continuous-state MDP. Belief-state MDPs are also the primary focus of our
investigation in this paper. 


\subsubsection{Value-Function Mappings and their Properties} \label{sec:POMDP-H-mapping}

The Bellman equation \ref{eq:POMDP-n-step-to-go-IF} for the
belief-state MDP can be also rewritten in the value-function mapping
form. Let ${\cal V}$ be a space of real-valued
bounded functions $V: {\cal I} \rightarrow \real$  defined on the
belief information space ${\cal I}$, and let $h: {\cal I} \times A \times B
\rightarrow \real$ be defined as 
$$h(b,a,V) = \sum_{s \in S} \rho(s,a)b(s) + \gamma \sum_{o \in
\Theta} \sum_{s \in S} P(o|s,a)b(s) V(\tau(b, o, a)).$$ 
Now by defining the value function mapping $H:{\cal V} \rightarrow
{\cal V}$ as 
$(HV)(b)= \max_{a \in A} h(b,a,V)$, 
the Bellman equation \ref{eq:POMDP-n-step-to-go-IF} for all information
states can be written as $V^{*} = H V^{*}.$
It is well known that $H$ (for MDPs) is an isotone mapping and that it is
a contraction under the supremum norm (see \cite{Heyman84,Puterman94}).

{\definition {The mapping $H$ is isotone, if $V, U \in {\cal V}$ and $V
\leq U$ implies $HV \leq HU$.}}

{\definition {Let $\|.\|$ be a supremum norm. The mapping $H$ is a
contraction under the supremum norm, if for all $V, U \in {\cal V}$,
$\|HV-HU\| \leq \beta \|V-U\|$ holds for some $0 \leq \beta < 1$.}}

%%% The proofs of these properties can be
%%% found in the Appendix. %%% ~\ref{sec:appendix:theorems-proofs}. 

%%% {\theorem {(Isotonicity of H mapping). $H$  mapping for $\gamma \geq 0$ is
%%% isotone. That is, for any two functions $U,V$ satisfying $U \leq V$, 
%%% $HU \leq HV$ holds. \label{proof:H-isotonicity} }}

%%% {\theorem  \label{proof:H-contraction} {(Contraction property).  H
%%%% with a discount factor $0 \leq \gamma < 1$ is a contraction
%%% under the supremum norm.}} 


\subsection{Value Iteration}

The optimal value function (Equation \ref{eq:POMDP-n-step-to-go-IF}) or its
approximation can be computed using {\em dynamic programming} techniques. The
simplest approach is the {\em value iteration} \cite{Bellman57}
shown in Figure \ref{fig:VI-algorithm}.  
\begin{figure}
\begin{center}
\begin{tabbing}
{\bf Valu}\= {\bf e iteration ($POMDP$, $\epsilon$)}\\
\>{\bf initialize } $V$ for all $b \in {\cal I}$;\\
\>{\bf repeat} \= \\
\>       \> $V' \leftarrow V$;\\
\>       \> update $V \leftarrow H V'$ for all $b \in {\cal I}$;\\
\>{\bf until } $ \sup_{b} \mid V(b) - V'(b) \mid \leq \epsilon$ \\ %% \frac{\delta (1- \gamma)}{\gamma}$ \\
\>{\bf return } V; \\
\end{tabbing}
\caption{Value iteration procedure.}
\label{fig:VI-algorithm}
\end{center}
\end{figure}
In this case, the optimal value function $V^{*}$ can be determined in the
limit by performing a sequence of value-iteration steps $V_{i}=HV_{i-1}$, where
$V_i$ is the $i$th approximation of the value function ($i$th value
function).{\footnote { We note that the same update $V_{i}=HV_{i-1}$ can
be applied to solve the finite-horizon problem in a standard way. The
difference is that $V_{i}$ now stands for the $i$-steps-to-go value
function and $V_{0}$ represents the value function (rewards) for end states.}}
 The sequence of estimates converges to the unique fixed-point solution
which is the direct consequence of Banach's theorem for contraction mappings
(see, for example, Puterman \citeyear{Puterman94}). 

In practice, we stop the iteration well before it reaches the limit
solution. The stopping criterion we use in our algorithm (Figure
\ref{fig:VI-algorithm}) examines the maximum difference between value functions obtained
in two consecutive steps --- the so-called Bellman error
\cite{Puterman94,Littman:thesis}. The algorithm stops when this quantity
falls below the threshold $\epsilon$.  
The accuracy of the approximate solution ($i$th value function) with regard
to $V^{*}$ can be expressed in terms of the Bellman error $\epsilon$. 

{\theorem \label{thm:BelRes-V} {Let $\epsilon = \sup_{b}|V_{i}(b) - V_{i-1}(b)| =
\|V_i-V_{i-1}\|$ be the magnitude of the Bellman error. Then $\|V_{i} - V^{*}\|
\leq \frac{\gamma \epsilon}{1 - \gamma}$ and $\|V_{i-1} - V^{*}\| \leq
\frac{\epsilon}{1 - \gamma}$  hold.}} 

\medskip

Then, to obtain the approximation of $V^{*}$ with precision
$\delta$ the Bellman error should fall below  $\frac{\delta (1-
\gamma)}{\gamma}$.  

\subsubsection{Piecewise Linear and Convex Approximations of the Value
Function}
 
The major difficulty in applying the value iteration (or dynamic programming)
to belief-state MDPs is that the belief space is
infinite and we need to compute an update $V_{i}=HV_{i-1}$ for all of it. 
%%% For example, in a belief-state MDP we face a continuous belief space. 
This poses the following threats: the value
function for the $i$th step may not be representable by finite
means and/or computable in a finite number of steps. 

To address this problem Sondik \cite{Sondik:thesis,Smallwood73} showed that
one can guarantee the computability of the $i$th value function as well as
its finite description for a belief-state MDP by 
considering only piecewise 
linear and convex representations of value function estimates (see Figure
\ref{fig:POMDP-pcl-convex}). In particular, Sondik showed that for a
piecewise linear and convex representation of $V_{i-1}$, $V_i= HV_{i-1}$ is
computable and remains piecewise linear and convex.  

\begin{figure}
\begin{center}
\mbox{ \epsfxsize 0.5\textwidth \epsffile{./FIGURE/pcl-convex.eps}}
\caption{A piecewise linear and convex function for a
POMDP with two process states $\{s_{1}, s_{2}\}$. Note that $b(s_{1}) = 1 -
b(s_{2})$ holds for any belief state.}
\label{fig:POMDP-pcl-convex}
\end{center}
\end{figure}

{\theorem {(Piecewise linear and convex functions). \label{thm:pclc-functions}
Let $V_{0}$ be
an initial value function that is piecewise linear and convex. Then the $i$th value
function obtained after a finite number of update steps for a belief-state
MDP is also finite, piecewise linear and convex, and is equal to:
$$V_{i}(b)=\max_{\alpha_{i} \in \Gamma_{i}} \sum_{s \in S} b(s)\alpha_{i}(s),$$
where $b$ and $\alpha_{i}$ are vectors of size
$|S|$ and $\Gamma_{i}$ is a finite set of vectors (linear functions) $\alpha_{i}$. }}

\medskip

The key part of the proof 
%%% (the full proof is given in the Appendix) 
is that we can express the
update for the $i$th value function in terms of linear functions $\Gamma_{i-1}$
defining $V_{i-1}$:
\begin{equation}
V_{i}(b) = \max_{a \in A} \left \{ \sum_{s \in S} \rho(s, a)b(s) +
\gamma \sum_{o \in \Theta}  \max_{\alpha_{i-1} \in \Gamma_{i-1}}
\sum_{s' \in S} \left [\sum_{s \in S} P(s',o|s,a) b(s) \right ]
\alpha_{i-1}(s') \right \}.
\end{equation}
This leads to a piecewise linear and convex value function $V_{i}$
that can be represented by a finite set of linear functions
$\alpha_{i}$, one linear function for every combination of actions and
 permutations of $\alpha_{i-1}$ vectors of size $|\Theta|$. Let 
$W = (a, \{o_1,\alpha_{i-1}^{j_1}\}, \{o_2,\alpha_{i-1}^{j_2}\}, \cdots
\{o_{|\Theta|},\alpha_{i-1}^{j_{|\Theta|}}\})$ be such a combination. Then the
linear function corresponding to it is defined as
\begin{equation}
\alpha_{i}^{W}(s) = \rho(s, a) + \gamma \sum_{o \in \Theta} \sum_{s' \in
S} P(s',o|s,a) \alpha^{j_{o}}_{i-1}(s'). \label{eq:linear-function-struct}
\end{equation} 

Theorem~\ref{thm:pclc-functions} is the basis of the
dynamic programming algorithm for finding the optimal solution for the
finite-horizon models and the value-iteration algorithm for finding
near-optimal approximations of $V^{*}$ for the discounted, infinite-horizon
model.  Note, however, that this result does not imply piecewise linearity
of the optimal (fixed-point) solution $V^{*}$. 


\subsubsection{Algorithms for Computing Value-Function Updates}
\label{sec:POMDP-exact-updates} 

\medskip

The key part of the value-iteration algorithm is the computation of
value-function updates $V_{i}=HV_{i-1}$. Assume an $i$th value function
$V_{i}$ that is 
represented by a finite number of linear segments ($\alpha$ vectors). The
total number of all its possible linear functions is 
$|A||\Gamma_{i-1}|^{|\Theta|}$ (one for every combination of actions
and permutations of $\alpha_{i-1}$ vectors of size $|\Theta|$) and they can
be enumerated in $O(\card{A}\card{S}^{2}\card{\Gamma_{i-1}}^{\card{\Theta}})$ time. 
However, the complete set of linear functions is rarely
needed: some of the linear functions are dominated by others
and their omission does not change the resulting 
piecewise linear and convex function. This is illustrated in Figure
\ref{fig:POMDP-pcl-redundant}. 
\begin{figure}
\begin{center}
\mbox{ \epsfxsize 0.5\textwidth \epsffile{./FIGURE/pcl-redundant.eps}}
\caption{Redundant linear function. The function does not dominate in any of
the regions of the belief space and can be excluded. }
\label{fig:POMDP-pcl-redundant}
\end{center}
\end{figure}

A linear function that can be eliminated without changing 
the resulting value function solution is called {\em
redundant}. Conversely, a linear function that singlehandedly achieves
the optimal value for at least one point of the belief space is called 
{\em useful}.{\footnote {In defining redundant and useful
linear functions we assume that there are no linear function duplicates,
i.e. only one copy of the same linear function is kept in the set
$\Gamma_{i}$.}}  

For the sake of computational efficiency it is important to make the size
of the linear function set as small as possible (keep only useful linear
functions) over value-iteration steps. 
There are two main approaches for computing useful
linear functions. 
%% Unfortunately, the problem cannot be solved 
%%% efficiently with regard to
%%% $|S|,|A|,|\Theta|,|\Gamma_{i-1}|,|\Gamma_{i}|$. This was shown in 
%%% \cite{Littman95c}, who proved that the problem can be solved efficiently
%%% only when $RP=NP$.  
The first approach is based
on a generate-and-test paradigm and is due to Sondik
\citeyear{Sondik:thesis} and 
Monahan \citeyear{Monahan82}. The idea here is to enumerate all possible
linear functions first, then test the usefulness of linear functions in the
set and prune all redundant vectors. Recent
extensions of the method interleave the generate and test stages and do early
pruning on a set of partially constructed linear functions \cite{Zhang97,Cassandra:uai97,Zhang:uai98}. 
%%% The methods for
%%% early pruning of linear functions for a single action were developed by
%%% Zhang and 
%%% \cite{Zhang96} and studied in \cite{Cassandra:uai97,Zhang:uai98}. 
%%% The idea for early pruning of linear functions across different actions was
%%%% described in \cite{Hauskrecht:thesis}.  

The second approach builds on Sondik's idea of computing a useful
linear function for a single belief state \cite{Sondik:thesis,Smallwood73},
which can be done efficiently. The key 
problem here is to locate all belief points that seed useful linear functions
and different methods address this problem differently. Methods that
implement this idea are Sondik's one- and two-pass algorithms
\cite{Sondik:thesis},
%%%  (see also \cite{Cassandra:thesis}), 
Cheng's methods
\cite{Cheng:thesis}, and the Witness algorithm
\cite{Kaelbling:aij,Littman:thesis,Cassandra:thesis}. 



\subsubsection{Limitations and Complexity}

The major difficulty in solving a belief-state MDP
is that the complexity of a piecewise linear and convex function can
grow extremely fast with the number of update steps. More specifically, the size of a linear function set
defining the function can grow exponentially (in the number of
observations) during a single update step. Then, assuming that the initial
value function is linear, the number of linear
functions defining the $i$th value function is $O(|A|^{|\Theta|^{i-1}})$.

The potential growth of the size of the linear function set is
not the only bad news. As remarked earlier, a piecewise linear convex value
function is usually less complex than the worst case because many linear functions can be pruned away
during updates. However, it turned out that the task of identifying
all useful linear functions is computationally intractable as well
\cite{Littman:thesis}. This means that one faces not only the
potential super-exponential growth of the number of useful linear functions,
but also inefficiencies related to the identification of such vectors. This is
a significant drawback that makes the exact methods applicable only to
relatively simple problems.

The above analysis suggests that solving a POMDP problem is an
intrinsically hard task. Indeed, finding the optimal
solution for the finite-horizon problem is PSPACE-hard
\cite{Papadimitriou87}. Finding the optimal
solution for the discounted infinite-horizon criterion is even harder. The
corresponding decision problem has been shown to be undecidable
\cite{Madani:aaai99}, and thus the optimal solution may not
be computable.  


\subsubsection{Structural Refinements of the Basic Algorithm}

The standard POMDP model uses a flat state space and full transition and
reward matrices. However, in practice, problems often exhibit more  
structure and can be represented more compactly, for example, using graphical
models \cite{Pearl88,Lauritzen96}, most often
dynamic belief networks \cite{Dean:2TBF,Kjaerulff92} or dynamic
influence diagrams \cite{Howard84,Tatman90}.{\footnote {See
the survey by Boutilier, Dean and Hanks \citeyear{BDH:jair99} for different
ways to represent structured MDPs.}} There are many ways to take advantage of the problem structure 
to modify and improve exact algorithms.    
For example, a refinement of the basic Monahan algorithm to 
compact transition and reward models has been studied by Boutilier and Poole
\citeyear{Boutilier:aaai96}. 
A hybrid framework that combines MDP-POMDP
problem-solving techniques to take advantage of perfectly and
partially observable components of the model and the subsequent value function
decomposition was proposed by Hauskrecht
\citeyear{Hauskrecht:thesis,Hauskrecht:DX-98,Hauskrecht:AIMJ-00}.   
A similar approach with perfect information about a region (subset of
 states) containing the actual underlying state was discussed by Zhang and Liu
 \citeyear{Zhang:uai97-region,Zhang97}. Finally, Casta\~{n}on \citeyear{Castanon97} and Yost
 \citeyear{Yost:thesis} explore techniques for solving  large POMDPs that
 consist of a set of  smaller, resource-coupled but otherwise independent
 POMDPs.  


\subsection{Extracting Control Strategy \label{POMDP:control-strategy}}

Value iteration allow us to compute an $i$th approximation of the value function
$V_i$. However, our ulimate goal is to find the optimal control strategy
$\mu^{*}:{\cal I} \rightarrow A$ or its close approximation. Thus our focus here
is on the problem of extraction of control strategies from the results of value iteration. 

\subsubsection{Lookahead Design}

The simplest way to define the control function $\mu:{\cal I} \rightarrow A$  
from the value function $V_i$ is via greedy one-step lookahead: 
$$\mu(b) =  \arg\max_{a \in A} \left \{ \sum_{s \in S} \rho(s, a)b(s)
+ \gamma \sum_{o \in \Theta} P(o|b, a) V_i(\tau(b, o, a)) \right \}.$$

As $V_i$ represents only the $i$th approximation of the optimal value
function, the question arises how good the resulting
controller really is.{\footnote {Note that the control action extracted
via lookahead from $V_i$ is optimal for $(i+1)$ steps-to-go and the
finite-horizon model. The main difference here is that $V_i$ is the optimal
value function for $i$ steps to go.}} The following theorem
\cite{Puterman94,Williams-Baird:94,Littman:thesis} relates the accuracy of
the (lookahead) controller and the Bellman error.  

{\theorem \label{thm:BelRes-LA} {Let $\epsilon = \|V_i-V_{i-1}\|$ be the
magnitude of the Bellman error. Let $V^{LA}_i$ be the expected reward for
the lookahead controller designed for $V_i$. Then $\|V_i^{LA}-V^{*}\| \leq
\frac{2 \epsilon \gamma}{1- \gamma}$.}} 

\medskip

The bound can be used to construct the value-iteration routine that yields
a lookahead strategy with a minimum required precision. The result can be
also extended to the $k$-step lookahead design in a straightforward way; with $k$
steps, the error bound becomes $\|V_i^{LA(k)}-V^{*}\| \leq \frac{2 \epsilon
\gamma^{k}}{(1- \gamma)}$. 

\subsubsection{Direct Design}

To extract the control action via lookahead essentially requires
computing one full update. Obviously, this can lead to unwanted delays in
reaction times. In general, we can speed up the response by remembering
and using additional information. In particular, every linear function defining $V_i$
is associated with the choice of action (see Equation
\ref{eq:linear-function-struct}). The action is a byproduct of methods for
computing linear functions and no extra computation is required to find
it. Then the action corresponding to the best
linear function can be selected directly for any belief
state. The idea is illustrated in Figure~\ref{fig:policy-pcl}.  
%%% This is the easiest way to represent the
%%% resulting control policy.  

\begin{figure}
\epsfxsize 0.5\textwidth
\begin{center}
   \mbox{ \epsffile{./FIGURE/policy-pcl.eps}}
\end{center} 
\caption{Direct control design. Every linear function defining
$V_i$ is associated with an action. The action is selected if its linear
function (or Q-function) is maximal.}
\label{fig:policy-pcl}
\end{figure}

The bound on the accuracy of the direct controller for the infinite-horizon
case can be once again derived in terms of the magnitude of the Bellman error. 

{\theorem {Let $\epsilon = \|V_i-V_{i-1}\|$ be the magnitude of the Bellman error. Let
$V^{DR}_i$ be an expected reward for the direct controller designed for
$V_i$. Then $\|V_i^{DR}-V^{*}\| \leq \frac{2 \epsilon}{1- \gamma}$.}}

\medskip

The direct action choice is closely related to the notion of action-value
function (or Q-function). Analogously to Equation \ref{eq:V-Q-relation}, the
$i$th Q-function satisfies
$$V_i(b) = \max_{a \in A} Q_i(b,a),$$
$$Q_i(b,a) = R(b,a) + \gamma \sum_{o \in \Theta}
P(o|b,a)V_{i-1}(\tau(b,a,o)).$$
From this perspective, the direct strategy selects the
action with the best (maximum) Q-function for a given belief state.{\footnote
{Williams and Baird \citeyear{Williams-Baird:94} also give results relating the
accuracy of the direct Q-function controller to
the Bellman error of Q-functions.}} 


\subsubsection{Finite-State Machine Design \label{sec:FSM-control-design}}

A more complex refinement of the above technique is to remember, for every
linear function in $V_i$,  not only the action choice but also the choice
of a linear function for the previous step and to do this for all observations (see
Equation \ref{eq:linear-function-struct}). As the same
idea can be applied recursively to the linear functions for all previous steps, we
can obtain a relatively complex dependency structure relating linear
functions in $V_i, V_{i-1}, \cdots V_0$, observations and actions that itself represents a control strategy \cite{Kaelbling:aij}. 

To see this, we model the structure in graphical terms (Figure
\ref{fig:FSM-policy-init}).
%%%%%% FIGURE %%%%%%%% 
\begin{figure}
\begin{center}
\mbox{ \epsfxsize 0.6\textwidth \epsffile{./FIGURE/FSM-policy-init.eps}}
\caption{A policy graph (finite-state machine) obtained after
two value iteration steps. Nodes correspond to linear functions (or states of the
finite-state machine) and links to dependencies between linear functions
(transitions between states). Every linear function (node) is associated
with an action. 
To ensure that the policy can be also applied to the infinite-horizon
problem, we add  a cycle to the last state (dashed line).}  
\label{fig:FSM-policy-init}
\end{center}
\end{figure}
%%%%%% END FIGURE %%%%%%%%%
Here different nodes represent linear
functions, actions associated with nodes correspond to optimizing actions,
links emanating from nodes correspond to different observations, and
successor nodes correspond to linear functions paired with observations. 
%%% \begin{figure}
%%% \begin{center}
%% \mbox{\psfig{figure=./FIGURE/app-fpol.ps}}
%% \caption{********** use new figure here that is more complex*****. } 
%%% \label{fig:policy-graph}
%%% \end{center}
%%%% \end{figure}
Such graphs are also called {\em policy graphs}
\cite{Kaelbling:aij,Littman:thesis,Cassandra:thesis}. One interpretation of
the dependency structure is that it represents a collection of 
finite-state machines (FSMs) with many possible initial states
that implement a POMDP controller: nodes correspond to states of
the controller, actions to controls (outputs), and links to
transitions conditioned on inputs (observations). 
The start state of the FSM controller is chosen greedily by selecting the
linear function (controller state) optimizing the value of an initial
belief state. 

The advantage of the finite-state machine representation of the
strategy is that for the first $i$ steps it works with observations
directly; belief-state updates are not needed. This contrasts with the
other two policy models (lookahead and direct models), which must keep
track of the current belief state and update it over time in order to
extract appropriate control. 
The drawback of the approach is that the FSM controller is limited to $i$
steps that correspond to the number of value iteration steps
performed. However, in the infinite-horizon model the controller is
expected to run for an infinite number of steps. One way to remedy this
deficiency is to extend the FSM structure and to create cycles 
that let us visit controller states repeatedly. For example, adding
a cycle transition to the end state of the FSM controller in
Figure \ref{fig:FSM-policy-init} (dashed line) ensures that the controller is
also applicable to the infinite-horizon problem. 


\subsection{Policy Iteration \label{sec:policy-iteration}}

An alternative method for finding the solution for the discounted
infinite-horizon problem is {\em policy iteration} \cite{Howard60,Sondik78}. Policy
iteration searches the policy space and gradually improves the current 
control policy for one or more belief states.  The method consists of two
steps performed iteratively: 
\begin{itemize}
\item {\it policy evaluation}: computes expected value for the current
policy;
\item {\it policy improvement}: improves the current policy.
\end{itemize}

As we saw in Section
\ref{POMDP:control-strategy}, there are many ways to represent a control
policy for a POMDP. Here we restrict attention to a finite-state machine model
in which observations correspond to inputs and actions to outputs
\cite{Platzman80,Hansen:uai98,Kaelbling:aij}.{\footnote {A
policy-iteration algorithm in which policies are defined over the regions
of the belief space was described first by Sondik \citeyear{Sondik78}.}} 

\subsubsection{Finite-State Machine Controller \label{sec:FSM:definition}}


A finite-state machine (FSM) controller $C=(M, \Theta, A, \phi, \eta,
\psi)$ for a POMDP is described by a set of memory states $M$ of the
controller, a set of observations (inputs) $\Theta$, a set of actions 
(outputs) $A$, a transition function $\phi: M \times \Theta
\rightarrow M$ mapping states of the FSM to next memory states given the
observation, and an output function $\eta: M \rightarrow A$ 
mapping memory states to actions. A function $\psi: {\cal I}_0 \rightarrow
M$ selects the initial memory state given the initial information
state. The initial information state corresponds either to a prior
or a posterior belief state at time $t_0$ depending on the availability of an
initial observation. 

\subsubsection{Policy Evaluation \label{sec:policy:evaluation}}

The first step of the policy iteration is policy evaluation. The most
important property of the FSM model is that the value function for 
a specific FSM strategy can be computed efficiently in the number of
controller states $M$. The key to efficient computability
is the fact that the value function for executing an FSM strategy from some
memory state $x$ is linear \cite{Platzman80}.{\footnote 
{The idea of linearity and efficient computability of the value functions
for a fixed FSM-based strategy has been addressed recently in different
contexts by a number of researchers
\cite{Littman:thesis,Cassandra:thesis,Hauskrecht:thesis,Hansen:uai98,Kaelbling:aij}.
However, the origins of the idea can be traced to the earlier work
by Platzman \citeyear{Platzman80}.}}

{\theorem \label{thm:fixed-linear} {Let $C$ be a finite-state machine
controller with a set of memory states $M$. The value function for
applying $C$ from a memory state $x \in M$, $V^{C}(x,b)$, is linear. Value
functions for all $x \in M$ can be found by solving a system of linear
equations with $|S||M|$ variables. }}  

\medskip

We illustrate the main idea by an example. Assume an FSM controller
with four memory states $\{x_1,x_2, x_3, x_4\}$, as in Figure
\ref{fig:FSM-policy-example-dupl}, and a stochastic process with two hidden
states $S=\{s_{1}, s_{2} \}$. 
\begin{figure}
\begin{center}
\mbox{ \epsfxsize 0.6\textwidth \epsffile{./FIGURE/FSM-pol-ex.eps}}
\caption{An example of a four-state FSM policy. Nodes 
represent states, links transitions between states (conditioned on
observations). Every memory state has an associated control action
(output).} 
\label{fig:FSM-policy-example-dupl}
\end{center}
\end{figure}
The value of the policy for an augmented state space $S \times M$
satisfies a system of linear equations 
\begin{eqnarray*}
V(x_{1}, s_{1}) & = & \rho(s_1,\eta(x_{1})) + \gamma \sum_{o \in \Theta}
\sum_{s \in S} P(o,s|s_{1}, \eta(x_{1})) V(\phi(x_{1},o),s) \\
V(x_{1}, s_{2}) & = & \rho(s_2,\eta(x_{1})) + \gamma \sum_{o \in \Theta}
\sum_{s \in S} P(o,s|s_{2}, \eta(x_{1})) V(\phi(x_{1},o),s) \\
% ******** x2 **************
V(x_{2}, s_{1}) & = & \rho(s_1,\eta(x_{2})) + \gamma \sum_{o \in \Theta}
\sum_{s \in S} P(o,s|s_{1}, \eta(x_{2})) V(\phi(x_{2},o),s) \\
% V(x_{2}, s_{2}) & = & \rho(s_2,\eta(x_{2})) + \gamma \sum_{o \in \Theta}
% \sum_{s \in S} P(o,s|s_{2}, \eta(x_{2})) V(\phi(x_{2},o),s)\\
& \cdots & \\
%%% V(x_{4}, s_{1}) & =&  \rho(s_1,\eta(x_{4})) + \gamma \sum_{o \in
%%% \Theta} 
%%% \sum_{s \in S} P(o,s|s_{1}, \eta(x_{4})) V(\phi(x_{4},o),s) \\
V(x_{4}, s_{2}) & = & \rho(s_2,\eta(x_{4})) + \gamma \sum_{o \in \Theta}
\sum_{s \in S} P(o,s|s_{2}, \eta(x_{4})) V(\phi(x_{4},o),s),
\end{eqnarray*}
where $\eta(x)$ is the action executed in $x$ and $\phi(x,o)$
is the state to which one transits  after seeing an input (observation)
$o$. Assuming we start the policy from the memory state $x_1$, the value of the
policy is: 
$$V^{C}(x_1,b) = \sum_{s \in S} V(x_1,s)b(s).$$
Thus the value function is linear and can be computed efficiently by
solving a system of linear equations. 

Since in general the FSM controller can start from any memory state,  
we can always choose the initial memory state greedily, maximizing
the expected value of the result. In such a case the optimal choice
function $\psi$ is defined as:
$$\psi(b) = \arg\max_{x \in M} V^{C}(x, b),$$
and the value for the FSM policy C and belief state $b$ is:
$$V^{C}(b) = \max_{x \in M} V^{C}(x, b) = V^{C}(\psi(b), b).$$
Note that the resulting value function for the strategy $C$ is piecewise
linear and convex and represents expected rewards for following $C$. Since
no strategy can perform better that the optimal strategy, $V^{C} \leq V^{*}$
must hold. 


\subsubsection{Policy Improvement}

%% Thus, in this case, the policy iteration searches
%%% the space  of finite-state controllers. 

The policy-iteration method, searching the space of controllers,  starts from
an arbitrary initial policy and improves it gradually by refining its
finite-state machine (FSM) description. In particular, one keeps modifying
the structure of the controller by adding or removing controller states
(memory) and transitions. Let $C$ and $C'$ be an old and a new FSM
controller. In the improvement step we must satisfy 
$$V^{C'}(b) \geq V^{C}(b) \mbox{ for all } b \in {\cal I};$$
$$ \exists b \in {\cal I}  \mbox{ such that } V^{C'}(b) > V^{C}(b).$$
To guarantee the improvement, Hansen \citeyear{Hansen:NIPS97,Hansen:uai98}
proposed a policy-iteration algorithm that relies on exact value function
updates to obtain a new improved policy structure.{\footnote {A policy-iteration algorithm that exploits exact
value function updates but works with policies defined over the belief
space was used earlier by Sondik \citeyear{Sondik78}.}} The basic idea
of the improvement is based on the observation that one can switch back and
forth between the FSM policy description and the piecewise-linear and convex 
representation of a value function. In particular:
\begin{itemize}
\item the value function for
an FSM policy is piecewise-linear and convex and every linear function
describing it corresponds to a memory state of a controller;
\item
%%  the update of a piecewise linear and convex value function leads to a
%% new piecewise-linear and convex value function, and 
individual linear functions
comprising the new value function after an update can be viewed as new memory states of an FSM policy, as described in Section \ref{sec:FSM-control-design}.  
\end{itemize}
This allows us to improve the policy by adding new memory states
corresponding to linear functions of the new value function obtained after
the exact update. The technique can be refined by removing
some of the linear functions (memory states) whenever they are
fully dominated by one of the other linear functions.  


\subsection{Forward (Decision Tree) Methods}

%%%% \mynote{Add Satia and Lave}

The methods discussed so far assume no prior knowledge
of the initial belief state and treat all belief states as equally
likely. However, if the initial state is known and fixed, methods can often
be modified to take advantage of this fact. For example, for 
the finite-horizon problem, only a finite number of belief states can be
reached from a given initial state. In this case it is very often easier to
enumerate all possible histories (sequences of actions and observations)
and represent the problem using stochastic decision trees \cite{Raiffa70}.
An example of a two-step decision tree is shown in Figure
~\ref{fig:d-2tree}. 

The algorithm for solving the stochastic decision tree basically
mimics value-function updates, but is restricted only to situations that
can be reached from the initial belief state. The key difficulty here is that the
number of all possible trajectories grows exponentially with the horizon of
interest.  

\subsubsection{Combining Dynamic-Programming and Decision-Tree
Techniques}

\begin{figure}
\epsfxsize 0.35\textwidth
\begin{center}
   \mbox{ \epsffile{./FIGURE/d2-tree-new-2.ps}}
\end{center} 
\caption{A two-step decision tree. Rectangles correspond to
the decision nodes (moves of the decision-maker) and circles to chance nodes
(moves of the environment). Black rectangles represent leaves of the
tree. The reward for a specific path is associated with every leaf of the
tree. Decision nodes are associated with information states obtained by
following action and observation choices along the path from the root
of the tree. For example, $b_{1,1}$ is a belief state obtained by
performing action $a_1$ from the initial belief state $b$ and observing
observation $o_1$.}
\label{fig:d-2tree}
\end{figure}

To solve a POMDP for a fixed initial belief state,  we can apply
two strategies: one constructs
the decision tree first and then solves it, the other solves the
problem in a backward fashion via dynamic programming. Unfortunately, both
these techniques are inefficient, one suffering from exponential
growth in the decision tree size, the other from super-exponential growth in
the value function complexity. However, the two techniques can be combined
in a way that at least partially eliminates their disadvantages. The idea is
based on the fact that the two techniques work on the solution from two
different sides (one forward and the other backward) and the complexity
for each of them worsens gradually. Then the  solution is to compute the complete
$k$th value function using dynamic programming (value iteration) and
cover the remaining steps by forward decision-tree expansion.

Various modifications of the above idea are possible. For example, one can
often replace exact dynamic programming with two more efficient approximations
providing upper and lower bounds of the value function. Then the decision
tree must be expanded only when the bounds are not sufficient to determine
the optimal action choice. A number of search techniques
developed in the AI literature \cite{Korf85} combined with
branch-and-bound pruning \cite{Satia73} can be applied to
this type of problem. Several 
researchers have experimented with them to solve POMDPs
\cite{Washington96,Hauskrecht:thesis,Hansen:uai98}. Other methods
applicable to this problem are based on Monte-Carlo sampling \cite{Kearns:ijcai99,McAllester:uai99} and real-time
dynamic programming \cite{Barto95,Dearden:aij97,Bonet:icml98}. 

%%% real-time dynamic programming (see
%%%  \cite{Barto95}) and methods for searching stochastic decision
%%% trees combined with branch and bound pruning \cite{Korf85}
%%% \cite{Hauskrecht97-TR} \cite{Washington96} 
%%% Hansen explores the combination of \cite{Hansen:uai98} can be
%%% applied.      


\subsubsection{Classical Planning Framework}

POMDP problems with fixed initial belief states and their solutions are
closely related to work in classical planning and its extensions to handle
stochastic and partially observable domains, particularly the work on BURIDAN and
C-BURIDAN planners \cite{Kushmerick:BURIDAN,Draper:C-BURIDAN}. The
objective of these planners is to maximize the probability of reaching some
goal state. However,
this task is similar to the discounted reward task in terms of 
complexity, since a discounted reward model can be converted into a
goal-achievement model by introducing an absorbing state \cite{Condon92}. 



%%%%%%%% APPROXIMATIONS %%%%%%%%%%%%

\section{Heuristic Approximations}

The key obstacle to wider application of the POMDP framework is the
computational complexity of POMDP problems. In particular, finding the
optimal solution for the finite-horizon case is
PSPACE-hard \cite{Papadimitriou87} and the discounted infinite-horizon case
may not even be computable \cite{Madani:aaai99}. 
One approach to such  problems is to approximate the solution to some
$\epsilon$-precision. Unfortunately, even this remains intractable
and in general POMDPs cannot be approximated efficiently
\cite{Burago96,Lusena98,Madani:aaai99}. This is also the reason why only
very simple problems can be solved optimally or
near-optimally in practice.   

To alleviate the complexity problem, research in the POMDP area has
focused on various heuristic methods (or approximations without the error
parameter) that are more efficient.{\footnote {The quality of a heuristic
approximation can be tested 
using the Bellman error, which requires one exact update step. However,
heuristic methods per se  do not contain a precision parameter.}}   
Heuristic methods are also our focus here. Thus, when referring to
approximations, we mean heuristics, unless specifically stated otherwise.   
%%% We refer to such approximations also heuristics. The hope in applying such
%% approximations is that they perform well in practice and lead to a
%%% reasonably good solution.

The many approximation methods and their combinations
can be divided into two often very closely related classes: {\em
value-function approximations} and {\em policy approximations}. 

\subsection{Value-Function Approximations}

The main idea of the value-function approximation approach is to approximate
the optimal value function $V:{\cal I} \rightarrow \real$ with a
function $\widehat{V}:{\cal I}
\rightarrow \real$ defined over the same information space. 
Typically, the new function is of lower complexity (recall that the 
optimal or near-optimal value function may consist of a large set of
linear functions) and is easier to compute than the exact
solution. Approximations can be often formulated as dynamic programming
problems and can be expressed in terms of approximate value-function
updates $\widehat{H}$. 
Thus, to understand the differences and advantages of various
approximations and exact methods, it is often sufficient to analyze and
compare their update rules. 
%%% each method implements. 
%%%{\footnote {We note that approximate
%%% updates can be applied in a straightforward way to solve finite-horizon
%%% problems, via dynamic programming.}} 


\subsubsection{Value-Function Bounds}

Although heuristic approximations have no guaranteed precision,
in many cases we are able to say whether they overestimate or underestimate
the optimal value function. The information on bounds can be used in
multiple ways. For example, upper- and lower-bounds can
help in narrowing the range of the optimal value function, elimination of
some of the suboptimal actions and subsequent speed-ups of exact
methods. Alternatively, one can use knowledge of both 
value-function bounds to determine the accuracy of a controller generated
based on one of the bounds (see Section \ref{sec:approx-control}). Also, in
some instances, a lower bound alone is 
sufficient to guarantee the control choice that always achieves an expected
reward at least as high as the one given by that bound (Section \ref{sec:minimum-exp-reward}). 

The bound property of different methods can be determined by examining the
updates and their bound relations. 

{\definition {(Upper bound). Let $H$ be the exact value-function mapping and
$\widehat{H}$ its approximation. We say that $\widehat{H}$ upper-bounds
$H$ for some $V$ when $(\widehat{H}V)(b) \geq (HV)(b)$ holds for every $b
\in {\cal I}$.
}}

\medskip

An analogous definition can be constructed for the lower bound.


\subsubsection{Convergence of Approximate Value Iteration}

Let $\widehat{H}$ be a value-function mapping representing an approximate
update. Then the approximate value iteration computes the $i$th value
function as $\widehat{V}_{i}= \widehat{H} \widehat{V}_{i-1}$. The fixed-point solution $\widehat{V^{*}} = \widehat{H}\widehat{V}^{*}$ or its
close approximation would then represent the intended output of the
approximation routine. The main problem with the iteration
method is that in general it can converge to unique or multiple
solutions, diverge, or oscillate, depending on $\widehat{H}$ and the initial
function $\widehat{V}_0$. Therefore, unique convergence cannot
be guaranteed for an arbitrary mapping $\widehat{H}$ and the convergence
of a specific approximation method must be proved.    


{\definition {(Convergence of $\widehat{H}$). The value iteration with
$\widehat{H}$ converges for a value function $V_{0}$ when $\lim_{n \rightarrow \infty}
(\widehat{H}^{n}V_{0})$ exists. %%% and is bounded ($|a| < \infty$).
}} 

{\definition {(Unique convergence of $\widehat{H}$). The value iteration
converges uniquely for ${\cal V}$ when for every $V \in {\cal V}$, 
$\lim_{n \rightarrow \infty} (\widehat{H}^{n}V)$ exists and for all pairs
$V, U \in {\cal V}$, $\lim_{n\rightarrow \infty} (\widehat{H}^{n}V) =
\lim_{n\rightarrow \infty} (\widehat{H}^{n}U)$. }}  

\medskip

A sufficient condition for the unique convergence is to show that
$\widehat{H}$ be a contraction. The contraction and the bound properties of
$\widehat{H}$ can be combined, under additional conditions, to show the
convergence of the iterative approximation method to the bound. To address
this issue we present a theorem comparing fixed-point solutions of two
value-function mappings.  

{\theorem \label{thm:convergence-to-bound}
{Let $H_1$ and $H_2$ be two value-function
mappings defined on ${\cal V}_1$ and ${\cal V}_2$ such that 
\begin{enumerate}
\item $H_1$, $H_2$ are contractions with fixed points $V_{1}^{*}$,
$V_{2}^{*}$;
\item $V^{*}_1 \in {\cal V}_2$ and $H_2 V_{1}^{*} \geq H_1 V_{1}^{*}= V_{1}^{*}$;
\item $H_2$ is an isotone mapping.
\end{enumerate}
Then $V^{*}_2 \geq V_{1}^{*}$ holds.}}

\medskip

Note that this theorem does not require that ${\cal V}_1$ and ${\cal V}_2$
cover the same space of value functions. For example, ${\cal V}_2$ can cover
all possible value functions of a belief-state MDP, while ${\cal V}_1$ can be
restricted to a space of piecewise linear and convex value functions. This
gives us some flexibility in the design of iterative approximation algorithms 
for computing value-function bounds. An analogous theorem also holds for the
lower bound. 


\subsubsection{Control} \label{sec:approx-control}

Once the approximation of the value-function is available, it can be used 
to generate a control strategy. In general, control solutions correspond to options
presented in Section \ref{POMDP:control-strategy} and include lookahead, direct
(Q-function) and finite-state machine designs.

A drawback of control strategies based on heuristic approximations is
that they have no precision guarantee. One way to find the accuracy of such
strategies is to do one exact update of the value function approximation and adopt
the result of Theorems \ref{thm:BelRes-V} and \ref{thm:BelRes-LA} for the
Bellman error. An alternative solution
to this problem is to bound the accuracy of such controllers using the
upper- and the lower-bound approximations of the optimal value function. 
To illustrate this approach, we present and prove (in the Appendix) the
following theorem that relates the quality of bounds to the quality of a 
lookahead controller.   

{\theorem \label{thm:bound-accuracy} {Let $\widehat{V}_U$ and $\widehat{V}_L$ be upper and lower
bounds of the optimal value function for the discounted infinite-horizon
problem. Let $\epsilon = \sup_{b}|\widehat{V}_U(b)-\widehat{V}_L(b)| =
\|\widehat{V}_U - \widehat{V}_L\|$ be the maximum bound difference. Then the expected 
reward for a lookahead controller $\widehat{V}^{LA}$, constructed for
either $\widehat{V}_U$ or $\widehat{V}_L$, satisfies $\|\widehat{V}^{LA} -
V^{*}\| \leq \frac{\epsilon (2 - \gamma)}{(1-\gamma)}$.}}

\medskip

\subsection{Policy Approximation \label{sec:policy-approx}}

%%% **** controller what action to choose and where to go

An alternative to value-function approximation is policy approximation. As
shown earlier,  a strategy (controller) for a POMDP can be represented using
a finite-state machine (FSM) model. The policy iteration searches  the
space of all possible policies (FSMs) for the optimal or near-optimal
solution. This space is usually enormous, which is the bottleneck of the
method. Thus, instead of searching the complete policy space, we can
restrict our attention only to its subspace that we believe to contain the
optimal solution or a good approximation. Memoryless policies
\cite{Platzman:thesis,White94,Littman94,Singh94},  
policies based on truncated histories \cite{Platzman:thesis,White94,McCallum:ml95}, or finite-state controllers with a fixed number of memory states
\cite{Platzman80,Hauskrecht:thesis,Hansen:NIPS97,Hansen:uai98} are all
examples of a policy-space restriction.  
In the following we consider only the finite-state machine model (see
Section \ref{sec:FSM:definition}), which is quite
general; other models can be viewed as its special cases. 

States of an FSM policy model represent the memory of the controller and,
in general, summarize information about past activities and
observations. Thus, they are best viewed as approximations of the
information states, or as {\em feature states}. The transition model of the
controller ($\phi$) then approximates the update 
function of the information-state MDP ($\tau$) and the output function of
an FSM ($\eta$) approximates the control function ($\mu$) mapping
information states to actions. The important property of the model, as
shown Section \ref{sec:policy:evaluation}, is that the value function for
a fixed controller and fixed initial memory state can be obtained
efficiently by solving a system of linear equations \cite{Platzman80}. 

To apply the policy approximation approach we first need to decide (1) how to
restrict a space of policies and (2) how to judge
the policy quality. 

% How to restrict the space of policies? What is the best policy?  

%% How to restrict the space of policies?
A restriction frequently used is to consider only controllers with a fixed
number of states, say $k$. Other structural restrictions further narrowing
the space of policies can restrict either the output function (choice of
actions at different controller states), or the transitions between
the current and next states. In general, any heuristic or domain-related
insight may help in selecting the right biases. 

%%% the size of the policy space with $|F|^{|A|}|F|^{2 \Theta}$

% What is the best policy?  
Two different policies can yield value functions that are
better in different regions of the belief space. Thus, in order to
decide which policy is the best, we need to define the importance of
different regions and their combinations. There are multiple solutions to
this. 
For example, Platzman \citeyear{Platzman80} considers the worst-case
measure and 
optimizes the worst (minimal) value for all initial belief states. 
Let ${\cal C}$ be a space of FSM controllers satisfying given
restrictions. Then the quality of a policy under the worst case measure
is:
$$\max_{C \in {\cal C}} \min_{b \in {\cal I}} \max_{x \in M_C} V^{C}(x,b).$$
Another option is to consider a distribution over all initial belief states
and maximize the expectation of their value function values. 
%%% for all
%%% possible initial belief states and their prior distribution. For example,
%%% the quality of a controller for uniformly distributed initial belief states
%%% can be measured as: 
%%% $$\max_{C \in {\cal C}} \int_{{\cal I}} \max_{x \in M_C} V^{C}(x,b) db.$$
However, the most common objective is to choose the policy that leads to
the best value for a single initial belief state $b_0$:
$$\max_{C \in {\cal C}} \max_{x \in M_C} V^{C}(x,b_0).$$ 
Finding the optimal policy for this case reduces to 
a combinatorial optimization problem. Unfortunately, for all but trivial
cases, even this problem is computationally intractable. For example, the
problem of finding the optimal policy for a memoryless case (only current
observations are considered) is NP-hard \cite{Littman94}. Thus, various
heuristics are typically applied to alleviate this difficulty \cite{Littman94}.

\subsubsection{Randomized Policies}

By restricting the space of policies we simplify the policy optimization
problem. On the other hand, we simultaneously give up an opportunity to
find the best optimal policy, replacing it with the best restricted policy. 
Up to this point, we have considered only deterministic policies with a
fixed number of internal controller states, that is, 
policies with deterministic output and transition functions. However,
finding the best deterministic policy is not always the best option: 
{\em randomized policies}, with randomized output and transition functions,
usually lead to the far better performance. The application of randomized (or stochastic)
policies to POMDPs was introduced by Platzman \citeyear{Platzman80}. 
%%%% and has also been studied recently by researchers in AI \cite{Singh94}.
Essentially, any deterministic
policy can be represented as a randomized policy with a single action and
transition, so that the best randomized policy is no worse than the best
deterministic policy. The difference in control performance of two policies shows up most often in cases when the 
number of states of the controller is relatively small compared to that in the
optimal strategy. 

The advantage of stochastic policies is that their space is
larger and parameters of the policy are continuous. Therefore the problem of
finding the optimal stochastic policy becomes a non-linear optimization problem
and a variety of optimization methods can be applied to solve it. An
example is the gradient-based approach (see Meuleau et
al., 1999). %%%%  \citeyear{Meuleau:uai99}). 

%%%%%%% VALUE-FUNCTION APPROXIMATIONS  %%%%%%%

\section{Value-Function Approximation Methods} \label{POMDP-APPROX}


In this section we discuss in more depth value-function
approximation methods. We focus on approximations with belief information
space.{\footnote {Alternative value-function approximations may work with
complete histories of past actions and observations. Approximation methods
used by White and Scherer \citeyear{White94} are an example.}}
We survey known techniques, but
also include a number of new methods and modifications of existing
methods. Figure \ref{fig:val-approx} summarizes the methods covered. 
\begin{figure}
\begin{center}
\mbox{\epsfxsize 0.86\textwidth
\epsffile{./FIGURE/value-approx.ps}}
%% \psfig{figure=./FIGURE/value-approx.ps}}
\caption{Value-function approximation methods.} 
\label{fig:val-approx}
\end{center}
\end{figure}
We describe the methods by means of 
update rules they implement, which simplifies their analysis and
theoretical  comparison. We focus on the following properties: the
complexity of the dynamic-programming (value-iteration) updates; the complexity
of value functions each method uses; the ability of methods to bound the exact
update; the convergence of value iteration with approximate update rules;
and the control performance of related controllers.  The results of the
theoretical analysis are illustrated empirically on a problem from the 
agent-navigation domain. In addition, we use the agent navigation problem
to illustrate and give some intuitions on other characteristics of
methods with no theoretical underpinning. Thus, these results should
not be generalized to other problems or used to rank different
methods.  

\subsubsection*{Agent-Navigation Problem}

Maze20 is a maze-navigation problem with 20 states, six
actions and eight observations. The maze (Figure \ref{fig:maze20}) consists of
20 partially connected rooms (states) in which a robot operates and
collects rewards. The robot can move in four directions (north, south, east
and west) and can check for the presence of walls using its
sensors. But, neither ``move'' actions nor sensor inputs are perfect, so
that the
robot can end up moving in unintended directions. The robot moves in an
unintended direction with probability of 0.3 (0.15 for each of the
neighboring directions). A move into the wall keeps the robot in the same
position. Investigative actions help the robot to navigate by activating
sensor inputs. Two such investigative actions allow the robot to
check inputs (presence of a wall) in the north-south and east-west
directions. Sensor accuracy in detecting walls is 0.75 for 
a two-wall case (e.g. both north and south wall), 0.8 for a one-wall case
(north or south) and 0.89 for a no-wall case, with smaller probabilities
for wrong perceptions. 
\begin{figure}
\begin{center}
\mbox{ \epsfxsize 0.5\textwidth \epsffile{./FIGURE/maze20.ps}}
\caption{Test example. The maze navigation problem: Maze20.}
\label{fig:maze20}
\end{center}
\end{figure}

The control objective is to maximize the expected discounted rewards with a
discount factor of 0.9. A small reward is given for every action not
leading to bumping into the wall (4 points for a move and 2 points for an
investigative action), and one large reward (150 points) is given for
achieving the special target room (indicated by the circle in the figure) and
recognizing it by performing one of the move actions. After doing that and
collecting the reward, the robot is placed at random in a new start
position. 

Although the Maze20 problem is of only moderate complexity with regard to the
size of state, action and observation spaces, its exact solution is
beyond the reach of current exact methods. The exact methods tried on the
problem include the Witness algorithm \cite{Kaelbling:aij}, the
incremental pruning algorithm \cite{Cassandra:uai97}{\footnote{Many thanks to
Anthony Cassandra for running these algorithms.}} and policy iteration
with an FSM model \cite{Hansen:uai98}. The main obstacle preventing these
algorithms from obtaining the optimal or close-to-optimal solution was the
complexity of the value function (the number of linear functions needed to
describe it) and subsequent running times and memory problems.


%%%%%% MDP-approx %%%%%%%

% *************** MDP- approximation *****************

\subsection{Approximations with Fully Observable MDP}
\label{sec:MDP-based-approximation} 


%%% performance scores: MDP-lookahead 38.24, QMDP-direct 38.11, QMDP 53.84

Perhaps the simplest way to approximate the value function for a POMDP is
to assume that states of the process are fully observable
\cite{Astrom65,Lovejoy:bounds93}. In that case the optimal value function
$V^{*}$ for a POMDP can be approximated as:
\begin{equation}
\widehat{V}(b)= \sum_{s \in S} b(s)V^{*}_{MDP}(s), \label{eq:MDP-approx-basic}
\end{equation}
where $V^{*}_{MDP}(s)$ is the optimal value function for state $s$ for the
fully observable version of the process. We refer to this approximation as
to the {\em MDP approximation}. The 
idea of the approximation is illustrated in Figure 
\ref{fig:POMDP-MDP-approximation}a. The resulting value function is linear 
and is fully defined by values at extreme points of the belief
simplex. These correspond to the optimal values for the fully
observable case.  
\begin{figure*}[t]

%%% alternative \epsffile{./FIGURE/FOMDP-merged.eps}
\epsfxsize 0.55\textwidth
\begin{center}
   \mbox{  \epsfxsize 0.45\textwidth
          \epsffile{./FIGURE/MDP-approx.eps}
          \hspace*{5mm} 
          \epsfxsize 0.50\textwidth
          \epsffile{./FIGURE/QMDP-approx.eps}
}
\end{center}
\caption{Approximations based on the fully observable version of a two
state POMDP (with states $s_1,s_2$): 
(a) the MDP approximation; (b) the QMDP approximation. Values at extreme
points of the belief space are solutions of the fully observable MDP.} 
\label{fig:POMDP-MDP-approximation}
\end{figure*}
The main advantage of the approximation is that the fully observable MDP
(FOMDP) can be solved efficiently for both the finite-horizon problem and
discounted infinite-horizon problems.{\footnote {The solution for the
finite-state fully observable MDP and discounted infinite-horizon criterion
can be found efficiently by formulating an equivalent linear programming task
\cite{Bertsekas95}}} The update step for the (fully observable) MDP is: 
$$V^{MDP}_{i+1}(s) = \max_a \left \{ \rho(s,a)+\gamma \sum_{s' \in
S}P(s'|s,a)V^{MDP}_{i}(s')\right \}.$$


\subsubsection{MDP Approximation}


The
MDP-approximation approach (Equation \ref{eq:MDP-approx-basic}) can be also
described in terms of value-function updates for the 
belief-space MDP. Although this step is strictly speaking redundant 
here, it simplifies the analysis and comparison of this approach to other
approximations. 

Let $\widehat{V}_{i}$ be a linear value function described by a vector
$\alpha_{i}^{MDP}$ corresponding to values of $V_{i}^{MDP}(s')$ for all
states $s' \in S$. Then the $(i+1)$th value function
$\widehat{V}_{i+1}$ is  
\begin{eqnarray*}
\widehat{V}_{i+1}(b)  & = &
\sum_{s \in S} b(s)\max_{a \in A} \left [ \rho(s,a) + \gamma \sum_{s' \in
S} P(s'|s,a) \alpha_{i}^{MDP}(s') \right ]\\
& = & (H_{MDP}\widehat{V}_{i})(b).
\end{eqnarray*}
$\widehat{V}_{i+1}$ is described by a linear function with components
$$ \alpha_{i+1}^{MDP}(s) = V^{MDP}_{i+1}(s)= \max_a \left \{\rho(s,a) + \gamma \sum_{s
\in S} P(s'|s,a) \alpha_{i}^{MDP}(s') \right \}. $$
The MDP-based rule $H_{MDP}$ can be also rewritten in a more general form
that starts from an arbitrary piecewise linear and convex value function
$V_{i}$, represented by a set of linear functions $\Gamma_{i}$:
\begin{eqnarray*}
\widehat{V}_{i+1}(b)  & = &
\sum_{s \in S} b(s)\max_{a \in A} \left \{ \rho(s,a) + \gamma \sum_{s' \in
S} P(s'|s,a) \max_{\alpha_{i} \in \Gamma_{i}} \alpha_{i}(s') \right \}.
\end{eqnarray*}

The application of the $H_{MDP}$ mapping always leads to a linear value
function. The update is easy to compute and takes
$O(|A||S|^{2}+ |\Gamma_{i}||S|)$ time. This reduces to $O(|A||S|^{2})$ time
when only MDP-based updates are strung together. As remarked earlier,
the optimal solution for the infinite-horizon, discounted problem can be
solved efficiently via linear programming. 

The update for the MDP approximation upper-bounds the exact update, that
is, $H \widehat{V}_{i} \leq H_{MDP} \widehat{V}_{i}$.  We show this
property later in Theorem~\ref{thm:upper-bounds}, which covers more
cases. The intuition is that we cannot get a better solution with less
information, and thus the fully observable MDP must upper-bound the partially
observable case.

%% In addition, $H_{MDP}$ is an isotone
%% contraction (follows directly from properties of perfectly observable
%%% MDPs). Thus,  it leads to the unique fixed-point solution
%%% $\widehat{V}^{*} = H_{MDP} \widehat{V}^{*} \geq V^{*}$.

%%% {\theorem {(Upper bound property of the MDP-based update rule) Let
%%% $\widehat{V}_{i}$ be a piecewise linear and value function described by
%%% a set 
%%% of linear vecors $\Gamma_{i}$. Then it holds that $H \widehat{V}_{i} \leq
%%% H_{MDP}\widehat{V}_{i}$.}} \medskip


\subsubsection{Approximation with Q-Functions (QMDP)}

A variant of the approximation based on the fully observable MDP uses
Q-functions \cite{Littman:icml95}: 
$$\widehat{V}(b) = \max_{a \in A} \sum_{s \in S} b(s)Q^{*}_{MDP}(s,a),$$ 
where 
$$Q^{*}_{MDP}(s,a) = \rho(s,a) + \gamma \sum_{s' \in S}P(s'|s,a)
 V^{*}_{MDP}(s')$$
is the optimal action-value function (Q-function) for the fully observable
 MDP. 
The QMDP approximation $\widehat{V}$ is piecewise linear and convex with
$|A|$ linear functions, each corresponding to one action (Figure
 \ref{fig:POMDP-MDP-approximation}b).   
The QMDP update rule (for the belief state MDP) for $\widehat{V}_{i}$ with
linear functions $\alpha_{i}^{k} \in \Gamma_{i}$ is: 
\begin{eqnarray*}
\widehat{V}_{i+1}(b)  & = &
\max_{a \in A} \sum_{s \in S} b(s) \left [\rho(s,a) + \gamma \sum_{s' \in
 S} P(s'|s,a) \max_{\alpha_{i} \in \Gamma_{i}} \alpha_{i}(s') \right
]\\
& = & (H_{QMDP}\widehat{V}_{i})(b).
\end{eqnarray*}

$H_{QMDP}$ generates a value function with $|A|$ linear
functions. The time complexity of the update is the same as for the
MDP-approximation case -- 
$O(|A||S|^{2}+ |\Gamma_{i}||S|)$, which reduces to $O(|A||S|^{2})$ time when
only $\mbox{QMDP}$ updates are used. $H_{QMDP}$ is a contraction mapping 
and its fixed-point solution can be found by solving the corresponding
fully observable MDP. 

The QMDP update upper-bounds the exact update. The bound is
tighter than the MDP update; that is, $H\widehat{V}_{i} \leq
H_{QMDP}\widehat{V}_{i} \leq H_{MDP}\widehat{V}_{i}$, as we prove later in 
Theorem~\ref{thm:upper-bounds}. The same inequalities hold for both
fixed-point solutions (through Theorem \ref{thm:convergence-to-bound}). 


To illustrate the difference in the
quality of bounds for the MDP approximation and the QMDP method, we use our
Maze20 navigation problem. To measure the quality of a bound we use the
mean of value-function values. Since all belief states are equally important
we assume that they are uniformly distributed. 
We approximate this measure using the average of values for a fixed set of $N=2000$
belief points. The points in the set were selected uniformly at random at
the beginning. Once the set was chosen, it was fixed and remained the same
for all tests (here and later).   
Figure \ref{fig:MDP-app-bound} shows the results of the experiment; we include also
results for the fast informed bound method that is presented in the next
section.{\footnote {The confidence interval limits for probability level
0.95 range in $\pm (0.45,0.62)$ from their
respective average scores and this holds for all bound
experiments in the paper. As these are relatively small we do not include
them in our graphs.}} Figure 
\ref{fig:MDP-app-bound} 
also shows the running times of the methods. The methods were implemented
in Common Lisp and run on Sun Ultra 1 workstation.

\begin{figure}
\epsfxsize 0.45\textwidth
\begin{center}
   \mbox{ \epsfxsize 0.45\textwidth \epsffile{./FIGURE/MDP-bounds.eps}
   \hspace*{10mm}
   \epsfxsize 0.45\textwidth \epsffile{./FIGURE/MDP-times.eps}}
\end{center}
\caption{Comparison of the MDP, QMDP and fast informed bound
   approximations: bound quality (left);  running times (right). The
   bound-quality score is the average value of the approximation for the
   set of 2000 belief points (chosen uniformly at random). As the methods upper-bound the optimal
   value function, we flip the bound-quality graph so that longer bars
   indicate better approximations.} 
\label{fig:MDP-app-bound}
\end{figure}


\subsubsection{Control}

%%%% performance scores: MDP-lookahead 38.24, QMDP-direct 38.11, QMDP 53.84

The MDP and the QMDP value-function approximations can be used
to construct controllers based on one-step lookahead. In addition, the QMDP
approximation is also suitable for the direct control strategy, which selects
an action corresponding to the best (highest value) Q-function. Thus,
the method is a special case of the Q-function approach discussed in Section
\ref{sec:approx-control}.{\footnote {As pointed out by Littman et
al. \citeyear{Littman:icml95}, in some
instances, the direct QMDP controller never selects investigative actions,
that is, actions that try to gain more information about the underlying
process state. Note, however, that this observation is not true in general and
the QMDP-based controller with direct action selection may select
investigative actions, even though in the 
fully observable version of the problem investigative actions are never
chosen. }}   
The advantage of the direct QMDP method is that it is faster than both
lookahead designs. On other the hand, lookahead tends to improve the 
control performance. This is shown in Figure \ref {fig:MDP-approx-control},
which compares the control performance of different controllers on
the Maze20 problem. 

The quality of a policy $\widehat{\pi}$, with no preference
towards a particular initial belief state, can be measured by the mean of
value-function values for $\widehat{\pi}$ and uniformly distributed
initial belief states. We approximate this measure using the average of
discounted rewards for 2000 control trajectories obtained for the fixed set
of $N=2000$ initial belief states (selected uniformly at random at the
beginning). 
The trajectories were obtained through simulation and were 60 steps long.{\footnote {The length of the trajectories (60 steps)
for the Maze20 problem was chosen to ensure that our estimates of
(discounted) cumulative 
rewards are not far from the actual rewards for an infinite number of
steps.}} 

To validate the comparison along the averaged performance scores, we must
show that these scores are not the result of 
randomness and that methods are indeed statistically significantly
different. To do this we rely on pairwise significance tests.{\footnote {An
alternative way to compare two methods is to compute confidence limits for
their scores and inspect their overlaps. However, in this case, the ability to distinguish two
methods can be reduced due to fluctuations of scores for different
initializations. For Maze20, confidence interval limits for probability
level 0.95 range in $\pm (1.8,2.3)$ from their respective average
scores. This covers all control experiments here and later. Pairwise tests eliminate the
dependency by examining the differences of individual values and thus improve
the discriminative power.}}    
%%% {\footnote
%%% {During the test we ensured that all controllers started from the same
%%% (hidden) position (and, of course, the 
%%% same fixed set of initial points.}} 
To summarize the obtained results, the score
differences of 1.54, 2.09 and 2.86 between any two methods (here and also
later in the paper) are sufficient to reject the method with a lower score
being the better performer at significance levels 0.05, 0.01 and 0.001
respectively.{\footnote {The critical score differences listed cover the
worst case combination. Thus, there may be some pairs for which the smaller
difference would suffice.}} Error-bars in Figure
\ref{fig:MDP-approx-control} reflect the critical score difference for the 
significance level 0.05.  


Figure \ref{fig:MDP-approx-control} also shows the
average reaction times for different controllers during these
experiments. The results show the clear dominance of the direct QMDP
controller, which need not do a lookahead in order to extract an
action, compared to the other two MDP-based controllers.   
\begin{figure*}[t]
\epsfxsize 0.45\textwidth
\begin{center}
   \mbox{ \epsfxsize 0.45\textwidth \epsffile{./FIGURE/MDP-control.eps} 
          \hspace*{10mm}
          \epsfxsize 0.45\textwidth \epsffile{./FIGURE/MDP-response.eps}}
\end{center}
\caption{Comparison of control performance of the MDP, QMDP and fast
          informed bound methods: quality of control (left); reaction times
          (right). The quality-of-control score is the
average of discounted  rewards for 2000 control trajectories obtained for the
fixed set of 2000 initial belief states (selected uniformly at
          random). Error-bars show the critical score difference value
          (1.54) at which any two methods become statistically 
          different at significance level 0.05.}
\label{fig:MDP-approx-control}
\end{figure*}


% ******************* Fast informed bound ********************************

\subsection{Fast Informed Bound Method} \label{fast-informed-bound}

%%% bound scores
%%% performance scores: MDP-lookahead 38.24, QMDP-direct 38.11, QMDP
%%% 53.84, fast-informed-lookahead 41.64 fast-informed 54.73

Both the MDP and the QMDP approaches ignore partial observability and use
the fully
observable MDP as a surrogate. To improve these approximations and account
(at least to some degree) for partial observability we propose a new method
-- {\em the fast informed bound method}.    
%% \cite{Hauskrecht97b} 
%% \cite{Hauskrecht97-TR}.  
% The method uses a newly designed update rule that upper bounds the exact
% update rule similarly to the MDP-based method.  
Let $\widehat{V}_{i}$  be a piecewise linear and convex value function
represented by a set of linear functions $\Gamma_{i}$. The new update is
defined as  
\begin{eqnarray*}
\widehat{V}_{i+1}(b) & = & \max_{a \in A} \left \{ \sum_{s \in S}
\rho(s, a)b(s) + \gamma \sum_{o \in \Theta} \sum_{s \in S}
\max_{\alpha_{i} \in \Gamma_{i}}  \sum_{s' \in S} P(s',o|s,a) b(s)
\alpha_{i}(s') \right \}\\
& = & \max_{a \in A} \left \{\sum_{s \in S}b(s)\left [\rho(s, a) +
\gamma \sum_{o \in \Theta} \max_{\alpha_{i} \in \Gamma_{i}} \sum_{s' \in
S}  P(s',o|s,a) \alpha_{i}(s')\right ] \right \} \\
& = & (H_{FIB} \widehat{V}_{i})(b).
\end{eqnarray*}

The fast informed bound update can be obtained from the exact update
by the following derivation:
\begin{eqnarray*}
(H\widehat{V}_{i})(b) & = & \max_{a \in A} \left \{ \sum_{s \in S} \rho(s, a)b(s) + \gamma
\sum_{o \in \Theta}  \max_{\alpha_{i} \in \Gamma_{i}} \sum_{s' \in S}
\sum_{s \in S} P(s',o|s,a) b(s) \alpha_{i}(s') \right \}\\
& \leq & \max_{a \in A} \left \{ \sum_{s \in S} \rho(s, a)b(s) +  \gamma \sum_{o
 \in \Theta} \sum_{s \in S} \max_{\alpha_{i} \in \Gamma_{i}}  \sum_{s'
 \in S}  P(s',o|s,a) b(s) \alpha_{i}(s') \right \}\\
& = & \max_{a \in A} \sum_{s \in S} b(s)\left [ \rho(s, a) + \gamma
 \sum_{o \in \Theta} \max_{\alpha_{i} \in \Gamma_{i}}  \sum_{s' \in S}
 P(s',o|s,a)  \alpha_{i}(s')\right ]\\
& = &  \max_{a \in A} \sum_{s \in S} b(s) \alpha_{i+1}^{a}(s)\\
& = & (H_{FIB}\widehat{V}_{i})(b).
\end{eqnarray*}

The value function
$\widehat{V}_{i+1} = H_{FIB} \widehat{V}_{i}$ one obtains
after an update is piecewise linear and convex and consists of at most
$|A|$ different linear functions, each corresponding to one action 
$$ \alpha_{i+1}^{a}(s) = \rho(s, a) + \gamma \sum_{o \in \Theta}
\max_{\alpha_{i} \in \Gamma_{i}}  \sum_{s' \in S} P(s',o|s,a)
\alpha_{i}(s').$$ 
The $H_{FIB}$ update is efficient and can be computed in
$O(\card{A}\card{S}^{2}\card{\Theta}\card{\Gamma_{i}})$ time. As the   
method always outputs $|A|$ linear functions, the computation can be done in $ O(\card{A}^{2}\card{S}^{2}\card{\Theta})$ time, when many
$H_{FIB}$ updates are strung together. 
This is a significant complexity reduction compared to the exact approach:
the latter can lead 
to a function consisting of $|A||\Gamma_{i}|^{|\Theta|}$ linear
functions, which is exponential in the number of observations and in the
worst case takes $O(\card{A}\card{S}^{2}\card{\Gamma_{i}}^{\card{\Theta}})$
time. 

As $H_{FIB}$ updates are of polynomial complexity one can find the
approximation for the finite-horizon case efficiently. The open issue
remains the problem of finding the solution for the infinite-horizon
discounted case and its complexity. 
%%% the $H_{FIB}$ is an isotone contraction. Thus, there is a unique
%%% fixed-point solution for the discounted infinite-horizon problem. 
%%% The open question is the computational complexity of finding it. 
To address it we establish the following theorem. 

{\theorem \label{thm:FIB-fixed-point} {A solution for the
fast informed bound approximation can be found by solving an
MDP with $|S||A||\Theta|$ states, $|A|$ actions and the same discount
factor $\gamma$.}}

\medskip

The full proof of the theorem is deferred to the Appendix. The key part of
the proof is the construction of an equivalent MDP with $|S||A||\Theta|$ states
representing $H_{FIB}$ updates. Since a finite-state MDP can be solved
through linear program conversion, the fixed-point solution for the
fast informed bound update is computable efficiently. 

%%% \ref{proof:H-contraction} and Theorem \ref{proof:H-isotonicity} and are


\subsubsection{Fast Informed Bound versus Fully-Observable MDP Approximations}

The fast informed update upper-bounds the exact update and is tighter than
both the MDP and the QMDP approximation updates. 

{\theorem \label{thm:upper-bounds}
{Let $\widehat{V}_{i}$ corresponds to a piecewise linear convex
value function defined by $\Gamma_{i}$ linear functions. Then $H\widehat{V}_{i} \leq H_{FIB}\widehat{V}_{i} \leq H_{QMDP}\widehat{V}_{i}
\leq H_{MDP}\widehat{V}_{i}.$
}}

\medskip

The key trick in deriving the above result is to swap max and sum
operators (the proof is in the Appendix) and thus obtain both to the
upper-bound inequalities and the subsequent reduction in the complexity of
update rules compared to the exact update. 
This is also shown in Figure \ref{fig:approx-relations}. The UMDP
approximation, also included in Figure  \ref{fig:approx-relations}, is
discussed later in Section \ref{sec:UMDP}.
\begin{figure*}
\begin{center}
   \epsfxsize 0.65\textwidth \epsffile{./FIGURE/approx-rel.eps}
\end{center}
\caption{Relations between the exact update and the UMDP, the fast informed
bound, the QMDP and the MDP updates. }
\label{fig:approx-relations}
\end{figure*}
Thus, the difference among the methods boils down to simple
mathematical manipulations. Note that the same inequality relations as
derived for updates hold also for their fixed-point solutions (through
Theorem \ref{thm:convergence-to-bound}).  

Figure \ref{fig:MDP-app-bound}a illustrates the improvement of the bound
over MDP-based approximations on the Maze20 problem. Note, however, that
this improvement is paid for by the increased running-time complexity
(Figure \ref{fig:MDP-app-bound}b). 



\subsubsection{Control}

The fast informed bound always outputs a piecewise linear and convex
function, with one linear function per action. This allows us to build a
POMDP controller that selects an action associated with
the best (highest value) linear function directly. Figure \ref{fig:MDP-approx-control}
compares the control performance of the direct and the lookahead
controllers to the MDP and the QMDP controllers. We see that the fast
informed bound leads not only to tighter bounds but also to improved
control on average. However, we stress that currently there is no theoretical
underpinning for this observation and thus it may not be true for all
belief states and any problem. 

\subsubsection{Extensions of the Fast Informed Bound Method}

The main idea of the fast informed bound method is to select the best 
linear function for every observation and every current state separately. This
differs from the exact update where we seek a linear function that 
gives the best result for every observation and the combination of all 
states. However, we observe that there is a great deal of middle
ground between these two extremes. Indeed, one can design an update
rule that chooses optimal (maximal) linear functions for disjoint sets of
states separately.  To illustrate this idea, assume a partitioning ${\cal
S} = \{S_{1}, S_{2}, \cdots, S_{m} \}$ of the state space $S$. The
new update for ${\cal S}$ is:  
 
\begin{eqnarray*}
\widehat{V}_{i+1}(b)  =  \max_{a \in A} \left \{ \sum_{s \in S} \rho(s,
a)b(s) \right .  & + &  \gamma \sum_{o \in \Theta} \left [ \max_{\alpha_{i} \in
\Gamma_{i}} \sum_{s \in S_{1}}  \sum_{s' \in S} P(s',o|s,a) b(s)
\alpha_{i}(s') + \right . \\
&  & \mbox{\hspace{1cm}} \max_{\alpha_{i} \in \Gamma_{i}}  \sum_{s \in S_{2}} \sum_{s' \in
S} P(s',o|s,a) b(s) \alpha_{i}(s') + \cdots + \\ 
&   & \mbox{\hspace{1cm}} \left . \left . \max_{\alpha_{i} \in \Gamma_{i}} \sum_{s \in S_{m}}
\sum_{s' \in S} P(s',o|s,a) b(s) \alpha_{i}(s') \right ] \right \}
\end{eqnarray*} 

%%% A case in which we use a single partition is equal to the exact update. The
%%% other extreme, with one partition per state, corresponds to the fast
%%% informed bound update. 
It is easy to see that the update upper-bounds the
exact update.  Exploration of this approach and various partitioning
heuristics remains an interesting open research issue.   


%%%%%%%%%%%% UMDP %%%%%%%%%%%%%%%%%%%%%

\subsection{Approximation with Unobservable MDP \label{sec:UMDP}}

The MDP-approximation assumes full observability of POMDP states
to obtain simpler and more efficient updates. The other extreme is to
discard all observations available to the decision maker. 
An MDP with no observations is called {\em unobservable MDP
(UMDP)} and one may choose its value-function solution as an
alternative approximation. 
\commentout{
%%%% od that assumes is to
%%%% consider a decision process in which observations are always ignored. 
%%%% Another approximation of the optimal value function can be found
%%%% by solving a corresponding {\em unobservable MDP (UMDP)}. Basically, in an
unobservable MDP all states are hidden and there no observations are
available to the decision-maker. 
Thus, one must act blindly in order to
control the system. {\footnote {We call a policy applicable to an unobservable MDP
a {\em blind policy}. A blind policy can be modeled as an FSM that does not branch
on observations and thus the sequence of actions it outputs is independent of inputs.}}  
%%% The value function corresponding to the fixed blind policy (with a single
%%% initial state) is linear and lower-bounds the optimal partially observable
%%% value function (a blind policy is a special case of a fixed policy). 
}
\commentout{
%% {\definition {(Blind control policy) Let $\pi = \{ \mu_{1}, \mu_{2},
%%% \cdots, \mu_{i}, \cdots \}$ be a control policy with control functions
%% $\mu_{i}: {\cal I} \rightarrow A$. The policy is called {\em blind} when control functions
%%% $\mu_{i} \in \pi$ map all information states to a single control action,
%% that is all $\mu_{i}$ are of the form $\mu_{i}: {\cal I} \rightarrow
%%% \{a_{i}\}$ with $a_{i} \in A$ denoting a single action. }} 
\medskip}

To find the solution for the unobservable MDP, we derive the
corresponding update rule, $H_{UMDP}$, similarly to the update for the
 partially observable case. $H_{UMDP}$ preserves piecewise linearity and
convexity of the value function and is a contraction. 
%%% Thus, the $i$th value function
%%% for the unobservable case (obtained after $i$ value updates) is piecewise linear
%%% and convex. 
%%% The optimal unobservable value function is the fixed point of
%%% $H_{UMDP}$.  
The update equals:
\begin{eqnarray*}
\widehat{V}_{i+1}(b) & = & \max_{a \in A} \left \{\sum_{s \in S} \rho(s,
a)b(s) +  \gamma \max_{\alpha_{i} \in \Gamma_{i}} \sum_{s \in S}
\sum_{s' \in S} P(s'|s,a) b(s) \alpha_{i}(s') \right \}\\
&  = & (H_{UMDP}\widehat{V}_{i})(b), 
\end{eqnarray*}
where $\Gamma_{i}$ is a set of linear functions describing $\widehat{V}_{i}$. 
$\widehat{V}_{i+1}$ remains piecewise linear and convex and it consists of
at most $|\Gamma_{i}||A|$ linear functions. This is in 
contrast  to the exact update, where the number of possible vectors in the
next step can grow exponentially in the number of observations
and leads to $|A||\Gamma_{i}|^{|\Theta|}$ possible vectors. The
time complexity of the update is $O(\card{A} \card{S}^{2}
\card{\Gamma_{i}})$. Thus, starting from $\widehat{V}_0$ with one linear
function, the running-time complexity for $k$ updates is bounded by
$O(\card{A}^{k} \card{S}^{2})$. The problem of finding the
optimal solution for the unobservable MDP remains intractable: the
finite-horizon case is NP-hard\cite{Burago96}, and the discounted
infinite-horizon case is undecidable \cite{Madani:aaai99}. Thus, it is
usually not very useful approximation.

The update $H_{UMDP}$ lower-bounds the exact update, an intuitive  
result reflecting the fact that one cannot do better with less
information. 
%%% that follows from the lower-bound property of fixed
%%% policies. 
To provide some insight into how the two updates are related,
we do the following derivation, which also proves the bound property in an
elegant way:
\begin{eqnarray*}
(H\widehat{V}_{i})(b) & = & \max_{a \in A} \left \{ \sum_{s \in S} \rho(s, a)b(s) +
\gamma \sum_{o \in \Theta}  \max_{\alpha_{i} \in \Gamma_{i}}
\sum_{s' \in S} \sum_{s \in S} P(s',o|s,a) b(s) \alpha_{i}(s') \right \}\\ 
& \geq & \max_{a \in A} \left \{ \sum_{s \in S} \rho(s, a)b(s) +  \gamma
\max_{\alpha_{i} \in \Gamma_{i}} \sum_{o \in \Theta}
\sum_{s \in S} \sum_{s' \in S} P(s',o|s,a) b(s) \alpha_{i}(s')\right \} \\
& = & \max_{a \in A} \left \{ \sum_{s \in S} \rho(s, a)b(s) +  \gamma
\max_{\alpha_{i} \in \Gamma_{i}} \sum_{s \in S} \sum_{s' \in S}
P(s'|s,a) b(s) \alpha_{i}(s') \right \}\\ 
& = & (H_{UMDP}\widehat{V}_{i})(b).\\
\end{eqnarray*}
We see that the difference between the exact and UMDP updates is that the
max and the sum over next-step observations are exchanged. This causes the
choice of $\alpha$ vectors in $H_{UMDP}$ to become independent
of the observations. Once the sum and max operations are exchanged, the
observations can be marginalized out. Recall that the idea of swaps leads to a number
of approximation updates; see Figure \ref{fig:approx-relations} for their summary. 

%%%%%%%%% fixed policy %%%%%%%%%


\subsection{Fixed-Strategy Approximations \label{sec:fixed-policies}}

%%% \mynote{The idea here is that we can go from an FSM policy to value
%%% functions. In the exact methods we went from the value function - updates
%%% to FSM policy. This is the other direction. } 

A finite-state machine (FSM)  model is used primarily to define a control
strategy. Such a strategy does not require belief state updates 
since it directly maps sequences of observations to sequences of
actions. The value function of an FSM strategy is piecewise
linear and convex and can be found efficiently in the number of memory
states (Section \ref{sec:FSM:definition}). While in the policy
iteration and policy approximation contexts the value function for a specific
strategy is used to quantify
the goodness of the policy in the first place, the value function alone can
be also used as a substitute for the optimal value function. 
In this case, the value function (defined over the belief space) equals
$$V^{C}(b) = \max_{x \in M} V^{C}(x,b),$$
where $V^{C}(x,b)=\sum_{s \in S}V^{C}(x,s)b(s)$ is obtained by solving a set
of $|S||M|$ linear equations (Section \ref{sec:policy:evaluation}). 
As remarked earlier, the value for the fixed strategy lower-bounds the
optimal value function, that is $V^{C} \leq V^{*}$. 

To simplify the comparison of the fixed-strategy approximation to other
approximations, we can rewrite its solution also in terms of fixed-strategy updates 
\begin{eqnarray*}
\widehat{V}_{i+1}(b) & = & \max_{x \in M} \left \{\sum_{s \in S} \rho(s,\eta(x)
)b(s) +  \gamma \sum_{o \in \Theta} \sum_{s \in S} \sum_{s' \in S}
P(o,s'|s,\eta(x)) b(s) \alpha_{i}(\phi(x,o),s') \right \},\\
& = & \max_{x \in M} \left \{\sum_{s \in S} b(s) \left [\rho(s,\eta(x)
) + \gamma \sum_{o \in \Theta}  \sum_{s' \in S} P(o,s'|s,\eta(x))
\alpha_{i}(\phi(x,o),s') \right ] \right \}\\
& = & (H_{FSM}\widehat{V}_{i})(b). 
\end{eqnarray*}
The value function $\widehat{V}_i$ is piecewise linear and convex and
consists of $|M|$ linear functions $\alpha_{i}(x,.)$. For the
infinite-horizon discounted case $\alpha_i(x,s)$ 
represents the $i$th approximation of $V^{C}(x,s)$. Note that the update
can be applied to the finite-horizon case in a straightforward way. 


\subsubsection{Quality of Control}

Assume we have an FSM strategy and would like to 
use it as a substitute for the optimal control policy. There are three
different ways in which we can use it to extract the control. The first
is to simply execute the strategy represented by the FSM. 
%%% . We select the start state by
%%% examining linear functions corresponding to each possible start state and
%%% execute the strategy
There is no need to update belief states in this
case. The second possibility is to choose linear functions corresponding to
different memory states and their associated actions repeatedly in every 
step. We refer to such a controller as a {\em direct} (DR)
controller. This approach requires updating of belief states in every
step. On the other hand its control performance is no worse than that of
the FSM control. The final strategy  
discards all the information about actions and extracts the policy by using
the value function $\widehat{V}(b)$ and one-step lookahead. This method (LA)
requires both belief state updates and lookaheads and leads to the worst
reactive time. Like DR, however, this strategy is guaranteed to be no 
worse than the FSM controller. The following theorem relates the
performances of the three controllers.  

{\theorem  \label{thm:FSM-controller-improvement}
{Let $C_{FSM}$ be an FSM controller. Let $C_{DR}$ and $C_{LA}$ be the
direct and the one-step-lookahead controllers constructed based on $C_{FSM}$. Then
$V^{C_{FSM}}(b) \leq V^{C_{DR}}(b)$ and $V^{C_{FSM}}(b) \leq
V^{C_{LA}}(b)$ hold for all belief states $b \in {\cal I}$.}}

\medskip

Though we can prove that both the direct controller and the
lookahead controller are always better than the underlying FSM controller
(see Appendix for the full proof of the theorem), we
cannot show the similar property between the first two controllers for all initial
belief states. However, the lookahead approach typically tends to dominate,
reflecting the usual trade-off between control quality and response time.
We illustrate this trade-off on our running Maze20 example and a collection
of $|A|$ one-action policies, each generating a sequence of the same action. 
%%% shown in Figure \ref{fig:simple-blind-policy}. 
%%% \begin{figure*}[t]
%%% \epsfxsize 0.45\textwidth
%%% \begin{center}
%%%   \mbox{ \epsfxsize 0.45\textwidth \epsffile{./FIGURE/FSM-simple-blind.eps}}
%%%% \end{center}
%%% \caption{A set of independent, one-action policies. Every policy produces
%%% a sequence of the same actions.}
%%% \label{fig:simple-blind-policy}
%%%% \end{figure*}
Control quality and response 
time results are shown in Figure \ref{fig:fixed-policy-comparison}. We see 
that the controller based on the FSM is the fastest of the three, but it is also the worst in terms of control quality. On
the other hand, the direct controller is slower (it needs to
update belief states in every step) but delivers better
control. Finally, the lookahead controller is the slowest and has
the best control performance. 
\begin{figure*}
% \mbox{ \vspace{1.5cm} }
\epsfxsize 0.45\textwidth
\begin{center}
   \mbox{ \epsfxsize 0.45\textwidth \epsffile{./FIGURE/FSM-control.eps}
   \hspace*{10mm}
   \epsfxsize 0.48\textwidth \epsffile{./FIGURE/FSM-response.eps}} 
\end{center}
\caption{Comparison of three different controllers (FSM, DR and LA) for
the Maze20 problem and a collection of one-action policies: control
quality (left) and response time (right). Error-bars in the control
performance graph indicate the critical score
difference at which any two methods become statistically different at
significance level 0.05.}
\label{fig:fixed-policy-comparison}
\end{figure*}


\subsubsection{Selecting the FSM Model}

The quality of a fixed-strategy approximation depends strongly on the FSM
model used. The model can be provided a priori or constructed automatically. 
Techniques for automatic construction of FSM policies correspond
to a search problem in which either the complete or a restricted space of
policies is examined to find the optimal or the near-optimal policy for such a
space. The search process is equivalent to policy approximations or 
policy-iteration techniques discussed earlier in Sections
\ref{sec:policy-iteration} and \ref{sec:policy-approx}. 


\subsection{Grid-Based Approximations with Value Interpolation-Extrapolation} \label{sec:grid-based-interpolation-extrapolation}

\commentout{Add Q-value approximations - this leads to the better bound or
direct controller for all methods}

A value function over a continuous belief space can be approximated
by a finite set of grid points $G$ and an {\em interpolation-extrapolation
rule} that estimates the value of an arbitrary point of the belief space by
relying only on the points of the grid and their associated values. 

%%% The main advantage of such a model is that it can be
%% updated easily by computing new values only for a finite 
%%% set of grid points.  

{\definition {(Interpolation-extrapolation rule) Let $f: {\cal I}
\rightarrow \real $ be a real-valued function defined over the
information space ${\cal I}$, $G = \{b_{1}^{G}, b_{2}^{G}, \cdots b_{k}^{G}\}$ be a set of grid
points and $\Psi^{G} = \{(b_{1}^{G}, f(b_{1}^{G})), (b_{2}^{G},
f(b_{2}^{G})), \cdots, (b_{k}^{G}, f(b_{k}^{G})) \}$ be a set of
point-value pairs. A function $R_{G}: {\cal I} \times ({\cal I} \times \real)^{|G|} \rightarrow
\real$ that estimates $f$ at any point of the
information space ${\cal I}$ using only values associated with
grid points is called an interpolation-extrapolation rule.}}
\medskip

The main advantage of an interpolation-extrapolation model in estimating
the true value function is that it requires us to compute value updates  only for a finite set of
grid points $G$.
Let $\widehat{V}_{i}$ be the approximation of the $i$th value
function. Then the approximation for the $(i+1)$th value function $\widehat{V}_{i+1}$ 
can be obtained as
$$\widehat{V}_{i+1}(b)= R_{G}(b, \Psi_{i+1}^{G}),$$
where values associated with every grid point $b_{j}^{G} \in G$ (and
included in $\Psi_{i+1}^{G}$) are:
\begin{equation}
\varphi_{i+1}(b_{j}^{G}) = (H\widehat{V}_{i})(b_{j}^{G}) = \max_{a \in A}
\left  \{
\rho(b, a) + \gamma \sum_{o \in \Theta} P(o| b, a)
\widehat{V}_{i}(\tau(b_{j}^{G}, o, a)) \right \}. \label{eq:grid-update-general}
\end{equation} 

The grid-based update can also be described in terms of a
value-function mapping $H_{G}$: $\widehat{V}_{i+1} = H_{G}
\widehat{V}_{i}$. The complexity of such an update is 
$O(\card{G}\card{A}\card{S}^{2}\card{\Theta}C_{\mbox{Eval}}(R_{G},
\card{G}))$ 
where $C_{\mbox{Eval}}(R_{G},\card{G})$ is the computational cost of evaluating
the interpolation-extrapolation rule $R_{G}$ for $\card{G}$ grid
points. We show later (Section \ref{sec:conversion-to-grid-MDP}), that in
some instances, the need to evaluate the interpolation-extrapolation rule
in every step can be eliminated.   

\subsubsection{A Family of Convex Rules}

The number of all possible interpolation-extrapolation rules is
enormous. We focus on a set of {\em convex rules} that
is a relatively small but very important subset of
interpolation-extrapolation rules.{\footnote {We note that convex rules
used in our work are a special case of averagers introduced by Gordon
\citeyear{Gordon95}. The difference is minor; the definition of an averager
includes a constant (independent of grid points and their values) that
is added to the convex combination. }}  

{\definition \label{def:convex-rule} {(Convex rule) Let $f$ be some
function defined over the  
space ${\cal I}$, $G=\{b_{1}^{G}, b_{2}^{G}, \cdots b_{k}^{G}\}$ be a set of grid
points, and  $\Psi^{G} = \{(b_{1}^{G}, f(b_{1}^{G})), (b_{2}^{G},
f(b_{2}^{G})), \cdots, (b_{k}^{G}, f(b_{k}^{G})) \}$ be a set of
point-value pairs. The rule $R_{G}$ for estimating $f$ using $\Psi^{G}$ 
%% values $f(b_{1}^{G}), f(b_{2}^{G}), \cdots f(b_{k}^{G})$ 
is called convex when for every $b \in {\cal I}$, the value
$\widehat{f}(b)$ is: 
$$\widehat{f}(b) = R_{G}(b, \Psi^{G})=  \sum_{j=1}^{|G|}
\lambda_{j}^{b} f(b_{j}),$$ such that $0
\leq \lambda_{j}^{b} 
\leq 1$ for every $j= 1, \cdots, |G|$,  and $\sum_{j=1}^{|G|} \lambda_{j}^{b} = 1$.}}
\medskip

The key property of convex rules is that their corresponding grid-based
update $H_{G}$ is a contraction in the max norm \cite{Gordon95}. Thus, the
approximate value iteration based on $H_G$ converges to the unique
fixed-point solution. In addition, $H_G$ based on convex rules is isotone.  

\subsubsection{Examples of Convex Rules}

The family of convex rules includes approaches that are very commonly used in practice, like
{\em nearest neighbor, kernel regression}, {\em linear point
interpolations} and many others.     

Take, for example, the {\em nearest-neighbor} approach. The function for a
belief point $b$ is
estimated using the value at the grid point closest to it in terms of some
distance metric $M$ defined over the belief space. Then, for any 
point $b$, there is exactly one nonzero parameter $\lambda_{j}^{b} = 1$
such that $\parallel b - b_{j}^{G} \parallel_{M} \leq \parallel b - b_{i}^{G}
\parallel_{M}$
holds for all $i = 1,2, \cdots, k$.
All other $\lambda$s are zero. 
%% That is:
%% $$ \widehat{f}(b)= R_{G}(b, \Psi^{G}) = f(b_{j}^{G}),$$
% where $\parallel b - b_{j}^{G} \parallel_{M} \leq \parallel b - b_{i}^{G}
% \parallel_{M}$
% holds for all $i = 1,2, \cdots, k$. $M$ represents a distance metric
% defined on the information space. 
Assuming the Euclidean distance metric, the nearest-neighbor approach leads to
a piecewise constant approximation,  in which regions with equal values
correspond to regions with a common nearest grid point.

The nearest neighbor estimates the function value by taking into an
account only one grid point and its value. {\em Kernel regression}
expands upon this by using more grid points. It adds up and weights their
contributions (values) according to their distance from the target point. 
%%% Here
%%% $\lambda$s represent the weights associated with different grid points.
%% The approximate function $\widehat{f}(b)$ for state $b$ and Gaussian kernels is
%% \vspace{-0.2cm}
%% $$ \widehat{f}(b)= R_{G}(b, \Psi^{G}) = \sum_{j=1}^{k} \lambda_{j}^{b} f(b_{j}^{G}).$$
%% such that
For example, assuming Gaussian kernels, the weight for a grid point
$b_j^{G}$ is 
$$\lambda_{j}^{b} = \beta \exp^{- \parallel b - b_{j}^{G} \parallel^{2}_{M} / 2\sigma^{2} },$$
where $\beta$ is a normalizing constant ensuring that 
$\sum_{j=1}^{|G|}\lambda_{j}^{b}=1$
%%%$$ \beta = \sum_{j=1}^{k} \exp^{- \parallel b - b_{j}^{G}
%%%\parallel^{2}_{M} / 2\sigma^{2} },$$ 
and $\sigma$ is a parameter that flattens or narrows weight
functions. For the Euclidean metric, the above kernel-regression rule
leads to a smooth approximation of the function. 
%% , unlike the nearest neighbor rule, which allows discontinuities. 

{\em Linear point interpolations} are a subclass of convex rules that
in
addition to constraints in Definition~\ref{def:convex-rule} satisfy
%%% also a constraint that explicitly 
%%% relates a point $b$ and its $\lambda$ coefficients
$$ b = \sum_{j=1}^{|G|} \lambda^{b}_{j} b_{j}^{G}. $$
That is, a belief point $b$ is a convex combination of grid points and
the $\lambda$s are the corresponding coefficients. 
Because the optimal value function for the POMDP is convex, the new
constraint is sufficient to prove the upper-bound property of the
approximation. In general, there can be many different linear
point-interpolations for a given grid. A challenging problem here is to
find the rule with the best approximation. We discuss these issues in
Section~\ref{sec:new-interpolation-rule}.   


\subsubsection{Conversion to a Grid-Based MDP \label{sec:conversion-to-grid-MDP}}

Assume that we would like to find the approximation of the value function
using our grid-based convex rule and grid-based update
(Equation~\ref{eq:grid-update-general}).  
We can view this process also as a process of finding a sequence of values
$\varphi_{1}(b^{G}_j), \varphi_{2}(b^{G}_j), \cdots, 
\varphi_{i}(b^{G}_j), \cdots$ for all grid-points $b^{G}_j \in G$. We show that in
some instances the sequence of values can be 
computed without applying an interpolation-extrapolation rule in
every step. In such cases, the problem can be converted into a fully
observable MDP with states corresponding to grid-points $G$.{\footnote {We
note that a similar result has been also proved independently by Gordon
\citeyear{Gordon95}.}} We call this MDP a {\em grid-based MDP}. 


{\theorem \label{thm:grid-based-conversion}
{Let $G$ be a finite set of grid points and $R_{G}$ be a convex
rule such that parameters $\lambda_{j}^{b}$ are fixed. Then the values of
$\varphi(b^{G}_{j})$ for all $b^{G}_{j} \in G$ can be found by solving a
fully observable MDP with $|G|$ states and the same discount factor $\gamma$.}}

\medskip
\proof{
%%% The main idea is to convert the problem of a grid-based update to an
%%% MDP update.  
For any grid point $b_{j}^{G}$ we can write:

\begin{eqnarray*}
\varphi_{i+1}(b_{j}^{G}) & = & \max_{a \in A} \left \{\rho(b_{j}^{G},a) +
\gamma \sum_{o \in \Theta} P(o|b_{j}^{G},a)
\widehat{V}_{i}^{G}(\tau(b_{j}^{G},a,o)) \right \}\\ 
& = & \max_{a \in A} \left \{ \rho(b_{j}^{G},a) + \gamma \sum_{o \in \Theta}
P(o|b_{j}^{G},a) \left [ \sum_{k=1}^{|G|}\lambda^{o,a}_{j,k}
\varphi_{i}(b_{k}^{G})\right ] \right \}\\
& = &\max_{a \in A} \left \{ \left [ \rho(b_{j}^{G},a) \right ] + \gamma
\sum_{k=1}^{|G|} 
\varphi_{i}^{G}(b_{k}^{G}) \left [ \sum_{o \in \Theta}
P(o|b_{j}^{G},a)\lambda^{o,a}_{j,k} \right ] \right \}\\ 
\end{eqnarray*}

Now denoting $[\sum_{o \in
\Theta} P(o|b_{j},a)^{G}\lambda^{o,a}_{j,k}]$ as
$P(b_{k}^{G}|b_{j}^{G},a)$, we can construct a fully observable MDP
problem with states corresponding to grid points $G$ and the same discount
factor $\gamma$. The update step equals:  

$$ \varphi_{i+1}(b_{j}^{G}) = \max_{a \in A} \left \{ \rho(b_{j}^{G},a) +
\gamma \sum_{k=1}^{|G|}
P(b_{k}^{G}|b_{j}^{G},a)\varphi_{i}^{G}(b_{k}^{G}) \right \}.$$

The prerequisite $0 \leq \lambda_{j}^{b} \leq 1$ for every $j= 1, \cdots, |G|$
and $\sum_{j=1}^{|G|} \lambda_{j}^{b} = 1$ guarantees that
$P(b_{k}^{G}|b_{j}^{G},a)$ can be interpreted as true probabilities. 
Thus, one can compute values $\varphi(b_{j}^{G})$ by solving the
equivalent fully-observable MDP. 
} %%% end of proof


\subsubsection{Solving Grid-Based Approximations}

The idea of converting a grid-based approximation into a
grid-based MDP is a basis of our simple but very powerful approximation
algorithm.  
Briefly, the key here is to find the parameters (transition probabilities and
rewards) of a new MDP model and then solve it. This process is relatively easy
if the parameters $\lambda$ used to interpolate-extrapolate the
value of a  non-grid point are fixed (the assumption of Theorem~\ref{thm:grid-based-conversion}). In
such a case, we can determine parameters of the new MDP efficiently in
one step, for any grid set $G$. The nearest neighbor or the kernel
regression are examples of rules with this property. Note that this leads to polynomial-time
algorithms for finding values for all grid points (recall that an MDP can
be solved efficiently for both finite and discounted, infinite-horizon
criteria). 

The problem in solving grid-based approximation arises only when the parameters
$\lambda$ used in the interpolation-extrapolation are not fixed 
and are subject to the optimization itself. This happens, for example,  when
there are multiple ways of interpolating a value at some point of
the belief space and we would like to find the best interpolation (leading to
the best values) for all grid points in $G$. 
In such a case, the corresponding ``optimal'' grid-based MDP cannot be found
in a single step and iterative approximation, solving a sequence of
grid-based MDPs, is usually needed. The worst-case complexity of this
problem remains an open question.
%%% {\footnote{We suspect the problem becomes
%%% NP-hard if an arbitrary set of grid points is used.}}


\subsubsection{Constructing Grids \label{sec:contruct-grid}}

%%% \mynote{may be include a picture of a regular grid for 3-dimensions and
%%% tri angulation}

An issue we have not touched on so far is the selection of grids. There are
multiple ways to select grids. We divide them into two classes -- regular
and non-regular grids. 

Regular grids \cite{Lovejoy:bounds91} partition the belief space
evenly into equal-size regions.{\footnote {
Regular grids used by Lovejoy \citeyear{Lovejoy:bounds91} are based on
Freudenthal triangulation \cite{Eaves84}.  Essentially, this is the same
idea as used to 
partition evenly the n-dimensional subspace of $\real^{n}$. In fact,
an affine transform allows us to map isomorphically grid
points in the belief space to grid points in the $n$-dimensional space
\cite{Lovejoy:bounds91}.}} The main advantage of regular grids
is the simplicity with which we can locate grid points in the neighborhood of
any belief point.  The disadvantage of regular grids is that they are restricted to a
specific number of points, and any increase in grid resolution is
paid for in an exponential increase in the grid 
size.  For example, a sequence of regular grids for a 20-dimensional belief
space (corresponds to a POMDP with 20 states) consists of 20, 210, 1540,
8855, 42504, $\cdots$ grid points.{\footnote {The number of points in the
regular grid sequence is given by \cite{Lovejoy:bounds91}: 
$$|G|= \frac{(M + |S| - 1)!}{M! (|S|-1)!},$$
where $M = 1,2, \cdots$ is a grid refinement parameter. }} This prevents
one from using the method with higher grid resolutions for problems with
larger state spaces.

Non-regular grids are unrestricted and thus provide
for more flexibility when grid resolution must be increased
adaptively. On the other hand, due to irregularities, methods for locating
grid points adjacent to an arbitrary belief point are usually more complex
when compared to regular grids. 


% ************************************
\subsubsection{Linear Point Interpolation}

\commentout{
The fact that the optimal value function is convex for a belief-state
MDPs can be used to show that the approximation based on linear
point interpolation always upper-bounds the exact update \cite{Lovejoy:bounds91,Lovejoy:bounds93}). Neither kernel
regression nor nearest neighbor can guarantee us any bound.
}     

The fact that the optimal value function $V^{*}$ is convex for a belief-state
MDPs can be used to show that the approximation based on linear
point interpolation always upper-bounds the exact solution
\cite{Lovejoy:bounds91,Lovejoy:bounds93}. Neither kernel
regression nor nearest neighbor can guarantee us any bound.

{\theorem \label{thm:interpolation-bound} {(Upper bound property of a
grid-based point interpolation update). Let $\widehat{V}_{i}$ be a convex value function. Then $H\widehat{V}_{i} \leq H_{G}\widehat{V}_{i}$.}} 
\medskip

%%% added
The upper-bound property of $H_{G}$ update for convex value functions follows
directly from Jensen's inequality. The convergence to an upper-bound follows
from Theorem \ref{thm:convergence-to-bound}. 

Note that the point-interpolation update imposes an additional constraint
on the choice of grid points.  In particular, it is easy to see that any valid
grid must also include extreme points of the belief 
simplex (extreme points correspond to $(1, 0, 0, \cdots), (0, 1, 0,
\cdots)$, etc.). Without extreme points one would  be unable to cover the
whole belief space via interpolation. Nearest neighbor and kernel regression
impose no restrictions on the grid.  

\subsubsection{Finding the best interpolation
\label{sec:new-interpolation-rule} }

In a general, there are multiple ways to interpolate a point of a
belief space. Our objective is to find 
the best interpolation, that is, the one that leads to the tightest
upper bound of the optimal value function. 

Let $b$ be a belief point and $\{(b_j,f(b_j))|b_j \in
G\}$ a set of grid-value pairs. Then the best interpolation for point $b$ is:
$$ \widehat{f}(b) = \min_{{\overline{\lambda}}} \sum_{j=1}^{|G|}\lambda_j f(b_j)$$
subject to $0 \leq \lambda_{j} \leq 1$ for all $j= 1, \cdots, |G|$,
$\sum_{j=1}^{|G|} \lambda_{j} = 1$, and $b=\sum_{j=1}^{|G|} \lambda_{j}
b_{j}^{G}$.

This is a linear optimization problem. Although it can be solved in
polynomial time (using linear programming techniques), the
computational cost of doing this is still relatively large, especially
considering the fact that the optimization must be repeated many times. To
alleviate this problem we seek more efficient ways of finding the
interpolation, sacrificing the optimality. 

One way to find a (suboptimal) interpolation quickly is to apply regular grids
proposed by Lovejoy \citeyear{Lovejoy:bounds91}. In this case the value at
a belief point is approximated using the convex combination of grid points
closest to it. The approximation leads to
piecewise linear and convex value functions. As all interpolations are
fixed here, the problem of finding the approximation can be converted into
an equivalent grid-based MDP and solved as a finite-state MDP. However, as 
pointed  in the previous section, the regular grids must use a specific 
number of grid points and any increase in the resolution of a grid is paid for
by an exponential increase in the grid size. This feature makes the method
less attractive when we have a problem with a large state space and we need
to achieve
high grid resolution.{\footnote {One solution to this
problem may be to use adaptive regular grids in which grid resolution is
increased only in some parts of the belief space. We leave this
idea for future work.}}  

In the present work we focus on non-regular (or arbitrary) grids. We propose 
an interpolation approach that searches a limited space of interpolations 
and is guaranteed to run in time linear in the size of the grid. The
idea of the approach is to interpolate a point $b$ of a belief space of 
dimension $|S|$ with a set of grid points that
consists of an arbitrary grid point $b' \in G$ and $|S|-1$ extreme points
of the belief simplex.  The coefficients of this interpolation can be found
efficiently and we search for the best such interpolation.  
Let $b' \in G$ be a grid point defining one such interpolation. Then the
value at point $b$ satisfies 
$$\widehat{V}_{i}(b) = \min_{b' \in G} \widehat{V}_i^{b'}(b),$$
where  $\widehat{V}_i^{b'}$ is the value of the interpolation for the grid
point $b'$. Figure 
\ref{fig:POMDP-point-interpolation-saw} illustrates the resulting
approximation. The function is characterized by its ``sawtooth'' shape, which
is influenced by the choice of the interpolating set.  

\begin{figure}
\epsfxsize 0.55\textwidth
\begin{center}
   \epsffile{./FIGURE/grid-saw-new.eps}
\end{center}
%%% \mbox{\psfig{figure=./FIGURE/grid-saw-new.eps}}
\caption{Value-function approximation based on the linear-time
interpolation approach (a two-dimensional case). Interpolating sets are
restricted to a single internal point of the belief space. }  
\label{fig:POMDP-point-interpolation-saw}
\end{figure}

To find the best value-function solution or its close approximation we can
apply a value iteration procedure in which we search for the best
interpolation after every update step. The drawback of this approach is
that interpolations may remain unchanged for many update steps, thus
slowing down the solution process. An alternative
approach is to solve 
a sequence of grid-based MDPs instead.  
%%% gradually converges to the desired solution. 
In particular, at every stage
we find the best (minimum value) interpolations for all belief points
reachable from grid points in one step, fix coefficients of these
interpolations ($\lambda$s), construct a grid-based MDP and solve it
(exactly or approximately). This
process is repeated until no further improvement (or no improvement larger
than some threshold) is seen in values at different grid points. 
%%%%%%% 
\commentout{
The following theorem (proved in the Appendix) summarizes the convergence
result, which holds for any point interpolation method. 

{\theorem {Let $G$ be a set of grid points including extreme points
of the belief simplex and $R_G$ a point interpolation rule. The sequence of
grid-based MDPs that optimize interpolation coefficients 
($\lambda_{i,j}^{a,o}$) locally after every step converges to the
interpolation with the best (minimum) value function. }} 

\medskip
} %%% end commentout

\subsubsection{Improving Grids Adaptively}

The quality of an approximation (bound) depends strongly on the points used in the
grid. Our objective is to provide a good approximation
with the smallest possible set of grid points.  However, this task is
impossible to achieve, since it cannot be known in advance (before solving)
what belief points to pick. A way to address this problem is to build grids
incrementally, starting from a small set of grid points and adding others
adaptively, but only in places with a greater chance of improvement. 
The key part of this approach is a heuristic for choosing grid points
to be added next.  

One heuristic method we have developed attempts to maximize improvements in bound
values via stochastic simulations. The method builds on the fact that 
every interpolation grid must also include extreme points
(otherwise we cannot cover the entire belief space). As extreme points and
their values affect the other grid points, we try to improve 
their values in the first place. In general, a value at any grid
point $b$ improves more the more precise values are used for its successor
belief points, that is, belief states that correspond to $\tau(b,a^{*},o)$
for a choice of observation $o$. $a^{*}$ is the current optimal action
choice for $b$. Incorporating such points
into the grid then makes a larger improvement in 
the value at the initial grid point $b$ more likely. Assuming that our
initial point is an extreme point, we have a heuristic that tends to
improve a value for 
that point. Naturally, one can proceed further with 
this selection by incorporating the successor points for the first-level
successors into the grid as well, and so forth.  

To capture this idea, we generate new grid points via simulation,
starting from one of the extremes of the belief simplex and continuing until
a belief point not currently in the grid is reached. An algorithm that
implements the bound improvement heuristic and expands the current grid $G$ with a set of $|S|$
new grid points while relying on the current value-function approximation
$\widehat{V}^{G}$ is shown in Figure \ref{fig:adaptive-algorithm}.
%%% \newpage  
\begin{figure}
\begin{center}
\begin{tabbing}
{\bf gene}\={\bf rate new grid points $(G, \widehat{V}^{G}$)}\\
\> {\bf set} \= $G_{new} = \{\}$\\
\> {\bf for} \> all extreme points $b$ do\\
\>           \> {\bf repe}\={\bf at} until $b \notin G \cup G_{new}$\\
\>           \>           \> {\bf set} $a^{*}=\arg\max_{a} \left \{ \rho(b, a) +
\gamma \sum_{o \in \Theta} P(o| b, a) \widehat{V}^{G}(\tau(b,a,o)) \right \}$ \\
\>           \>           \> {\bf select} observation $o$ according to $P(o|b,a^{*})$\\ 
\>           \>           \> {\bf update} $b = \tau(b,a^{*},o)$\\
\>           \>{\bf add} $b$ into $G_{new}$\\
\> {\bf return} $G_{new}$\\
\end{tabbing}
\caption{Procedure for generating additional grid points based on our bound
improvement heuristic. \newline}
\label{fig:adaptive-algorithm}
\end{center}
\end{figure}

Figure \ref{fig:grid-ie-bound} illustrates the performance (bound quality) of
our adaptive grid method on the Maze20 problem. Here we use the combination of
adaptive grids with our linear-time interpolation approach. 
\begin{figure*}[t]
\epsfxsize 0.7\textwidth
\begin{center}
   \epsffile{./FIGURE/GMDP-bounds.eps}
\end{center}
\caption{Improvement in the upper bound quality for grid-based
point-interpolations based on the 
adaptive-grid method. The method is compared to randomly refined
grid and the regular grid with 210 points. Other 
upper-bound approximations (the MDP, QMDP and fast informed bound methods)
are included for comparison.}
\label{fig:grid-ie-bound}
\end{figure*}
The method gradually expands the grid in 40 point
increments up to 400 grid points. Figure \ref{fig:grid-ie-bound} also
shows the performance  of the random-grid method in which new points of the
grid are selected iniformly at random (results for 40 grid point increments are
shown). In addition, the figure gives results for the regular grid
interpolation (based on Lovejoy \citeyear{Lovejoy:bounds91}) with 210 belief points and
other upper-bound methods: the MDP, the QMDP and the fast informed bound
approximations.  

We see a dramatic improvement in the quality of the bound for the adaptive
method. In contrast to this, the uniformly sampled grid (random-grid
approach) hardly changes the bound. There are two reasons for this:
(1) uniformly sampled grid points are more likely 
to be concentrated in the center of the belief simplex; (2) the transition matrix
for the Maze20 problem is relatively sparse, the belief points one obtains from
the extreme points in one step are on the boundary of the simplex. Since
grid points in the center of the simplex are never used to interpolate
belief states reachable from extremes in one step they cannot improve
values at extremes and the bound does not change.  

One drawback of the adaptive method is its running time (for every grid
size we need to solve a sequence of grid-based MDPs). Figure
\ref{fig:grid-ie-times} compares running times of different methods on the
Maze20 problem. As grid-expansion of the adaptive method depends on
the value function obtained for previous steps, we plot its cumulative
running times. We see a relatively large
increase in running time, especially for larger grid sizes, reflecting
the trade-off between the bound quality and running time. However,
we note that the adaptive-grid method performs quite well in the initial
few steps, and with only 80 grid points outperforms the regular grid (with
210 points) in bound quality.
%%% In contrast to the
%%% adaptive grid method, the running time for the regular grid is much better,
%%% as it requires to solve only a single grid-based MDP. 
\begin{figure*}[t]
\begin{center}
\vspace*{3mm}
\epsfxsize 0.65\textwidth \epsffile{./FIGURE/GMDP-times.eps}
%%%    \epsfxsize 0.5\textwidth \epsffile{./FIGURE/GMDP-times.eps}
%%   \hspace*{10mm}
%%  \epsfxsize 0.5\textwidth \epsffile{./FIGURE/GMDP-times.eps}}
\end{center}
\caption{Running times of grid-based point-interpolation methods. Methods
tested include the adaptive grid, the random grid, and the regular grid
with 210 grid points.    
Running times for the adaptive-grid are cumulative, reflecting the
dependencies of higher grid resolutions on the lower-level resolutions. 
The running time results for the MDP, QMDP, and fast informed bound
approximations are shown for comparison.} 
\label{fig:grid-ie-times}
\end{figure*}

Finally, we note that other heuristic approaches to constructing adaptive
grids for point interpolation are possible. For example, a
different approach that refines the grid by examining differences in values at
current grid points has recently been proposed by Brafman
\citeyear{Brafman:aaai97}.  

\subsubsection{Control \label{sec:grid-based-control}}

Value functions obtained for different grid-based methods define a variety
of controllers. Figure \ref{fig:grid-ie-control} compares the performances
\begin{figure}[t]
\epsfxsize 0.7\textwidth
\begin{center}
   \epsffile{./FIGURE/GMDP-control-70.eps}
\end{center}
\caption{Control performance of lookahead controllers based on grid-based
point interpolation and nearest neighbor methods and varying grid
sizes. The results are compared to the MDP, the QMDP and the fast informed
bound controllers. }
\label{fig:grid-ie-control}
\end{figure}
of lookahead controllers based on the point-interpolation 
and  nearest-neighbor methods. We run two versions of both 
approaches, one with the adaptive grid, the other with the random grid, and
we show results obtained for 40, 200 and 400 grid points. In addition, we
compare their performances to the interpolation with regular grids
(with 210 grid points), the MDP, the QMDP and the fast informed bound
approaches. 

Overall, the performance of the interpolation-extrapolation techniques we
tested on the Maze20 problem was a bit disappointing. In particular, better
scores were achieved by the simpler QMDP and fast informed bound
methods. We see that, although heuristics improved the bound quality
of approximations, they did not lead to the similar improvement over the
QMDP and the fast informed bound methods in terms of control.
This result shows that a bad bound (in terms of absolute values) does not
always imply bad control performance.  
The main reason for this is that the control performance is influenced
mostly by relative rather than absolute value-function values (or, in other
words, by the shape of the function). All interpolation-extrapolation
techniques we use (except regular grid interpolation) approximate
the value function 
with functions that are not piecewise linear and convex; the interpolations
are based on the linear-time interpolation 
technique with a sawtooth-shaped function, and the nearest-neighbor leads
to a piecewise-constant function. This does not
allow them to match the shape of the optimal function correctly. The other factor that affects the performance
is a large sensitivity of methods to the selection of grid points,
as documented, for example, by the comparison of heuristic and random grids. 

In the above tests we focused on lookahead controllers only. However, 
an alternative way to define a controller for grid-based 
interpolation-extrapolation methods is to use Q-function approximations
instead of value functions, and either direct or lookahead designs.{\footnote {This is similar to the QMDP method, which allows both
lookahead and greedy designs. In fact, QMDP can be viewed as a special case
of the grid-based method with Q-function approximations, where grid points
correspond to extremes of the belief simplex.}} 
Q-function approximations can be found by solving the same grid-based MDP, and
by keeping values (functions) for different actions separate at the
end.  


%%%% CURVE FITTING %%%%%%

\subsection{Approximations of Value Functions Using Curve Fitting
(Least-Squares Fit)} \label{sec:least-squares-fit} 

An alternative way to approximate a function over a continuous space is to use
curve-fitting techniques. This approach relies on a predefined parametric model
of the value function and a set of values associated with a finite set of
(grid) belief points $G$. 
The approach is similar to interpolation-extrapolation techniques in that it relies
on a set of belief-value pairs. The difference is
that the curve fitting, instead of remembering all belief-value pairs, tries to summarize
them in terms of a given parametric function model. 
The strategy seeks the best possible match between model
parameters and observed point values.
The best match can be defined using
various criteria, most often the least-squares fit criterion, where the objective
is to minimize  
$$Error(f) = \frac{1}{2} \sum_{j} \left [ y_{j} - f(b_{j})\right ]^{2}.$$
Here $b_{j}$ and $y_{j}$ correspond to the belief point and its associated
value. The index $j$ ranges over all points of the sample set $G$. 
 

\subsubsection{Combining Dynamic Programming and Least-Squares Fit}

The least-squares approximation of a function can be used to construct a
dynamic-programming algorithm with an update step: $\widehat{V}_{i+1} =
H_{LSF} \widehat{V}_{i}$. The approach has two steps. First, we
obtain new values for a set of sample points $G$:
$$ \varphi_{i+1}(b) = (H\widehat{V}_{i})(b) = \max_{a \in A} \left \{ \sum_{s \in S} \rho(s, a)b(s)
+ \gamma \sum_{o \in \Theta} \sum_{s \in S} P(o|s, a) b(s)
\widehat{V}_{i}(\tau(b,a,o)) \right \}.$$ 
Second, we fit the parameters of the value-function model
$\widehat{V}_{i+1}$ using new sample-value pairs and the square-error
cost function. The complexity of the update is
$O(\card{G}\card{A}\card{S}^{2}\card{\Theta} C_{\mbox{Eval}}(\widehat{V}_{i})
+ C_{\mbox{Fit}}(\widehat{V}_{i+1},\card{G}))$ time, where $C_{\mbox{Eval}}(\widehat{V}_{i})$ is
the computational cost of evaluating $\widehat{V}_{i}$ and
$C_{\mbox{Fit}}(\widehat{V}_{i+1},\card{G})$ is the cost of
fitting parameters of $\widehat{V}_{i+1}$ to $\card{G}$ belief-value pairs.
 
The advantage of the approximation based on the least-squares fit is that it
requires us to compute updates only for the finite set of belief states. 
The drawback of the approach is that, when combined
with the value-iteration method, it can lead to instability and/or 
divergence. This has been shown for MDPs by several researchers
\cite{Bertsekas94,Boyan:NIPS95,Baird95,Tsitsiklis96}. 
%%% In addition, the method is very
%%% sensitive to the selection of the grid points used in updates and to the
%%% initial value function $\widehat{V}_0$.  


\subsubsection{On-line Version of the Least-Squares Fit}

The problem of finding a set of parameters with the best fit can be
solved by any available optimization procedure. This includes
the on-line (or instance-based) version of the gradient descent method,
which corresponds to the well-known delta rule \cite{Rumelhart86}. 
%% The delta rule
%% allows for the gradual adjustment of the function parameters for every new
%%% sample seen. 

Let $f$ denote a parametric value function over the belief space with
adjustable weights $\overline{w} = \{w_{1}, w_{2}, \cdots, w_{k} \}$. Then
the on-line update for a weight $w_{i}$ is computed as: 
$$w_{i} \leftarrow w_{i} - \alpha_{i} (f(b_{j})- y_{j}) \frac{\partial
f}{\partial w_{i}}|_{b_{j}},$$ 
where $\alpha_{i}$ is a learning constant, and $b_{j}$ and $y_{j}$ are the last-seen point and its value. Note that the gradient descent method
requires the function to be differentiable with regard to adjustable
weights. 
%%% Therefore one needs to use a suitable model and this also in the case
%%% when  the optimal value function is
%%% nondifferentiable (for example piecewise linear). 

To solve the discounted infinite-horizon problem, the stochastic (on-line)
version of a least-squares fit can be combined with either parallel
(synchronous) or incremental (Gauss-Seidel) point updates. In the first
case, the value function from the previous step is 
fixed and a new value function is computed from scratch using a set of
belief point samples and their values computed through one-step expansion. Once
the parameters are stabilized (by attenuating learning rates), the newly
acquired function is fixed, and the process proceeds with another
iteration. In the incremental version, a single value-function model is at the same time updated and used to compute
new values at sampled points. Littman et al. \citeyear{Littman:icml95} and
Parr and Russell \citeyear{Parr95} implement this approach using asynchronous
reinforcement learning backups in which sample points to be updated next 
are obtained via stochastic simulation. We stress that all versions are subject
to the threat of instability and divergence, as remarked above. 

\subsubsection{Parametric Function Models}
\label{sec:least-square-function-models} 

To apply the least-squares approach we must first select an appropriate value
function model. Examples of simple convex functions are linear
or quadratic functions, %%%% usually corresponds to linear $\widehat{V}$, linear $\widehat{Q}$
%%% \cite{Littman:icml95}, or a quadratic function, 
but more complex models are possible as well. 

%%% The only restriction is that
%% if we use the on-line version of the method we need a
%%% model that is differentiable.  

One interesting and relatively simple approach is based on the
least-squares approximation of linear action-value functions (Q-functions)
\cite{Littman:icml95}. Here the value function $\widehat{V}_{i+1}$ is
approximated as a piecewise linear and convex combination of
$\widehat{Q}_{i+1}$ functions: 
$$\widehat{V}_{i+1}(b) = \max_{a \in A} \widehat{Q}_{i+1}(b,a),$$
where $\widehat{Q}_{i+1}(b,a)$ is the least-squares fit of a linear function
for a set of sample points $G$. Values at points in $G$ 
are obtained as
$$\varphi^{a}_{i+1}(b) = \rho(b,a) + \gamma \sum_{o \in \Theta} P(o|b,a) \widehat{V}_{i}(\tau(b,o,a)).$$
The method leads to an approximation with $|A|$ linear functions and the coefficients of these functions can be
found efficiently by solving a set of linear equations. Recall that other
two approximations (the QMDP and the fast informed bound approximations) also work with $|A|$ linear
functions. The main differences between the methods are that the QMDP and
fast informed bound methods update linear functions directly, and they
guarantee upper bounds and unique convergence. 
%%% while Q-function least-squares relies on updates
%%% performed at some number of sample points, and neither bound nor
%%% convergence properties are guaranteed.  
 
A more sophisticated parametric model of a convex function is the {\em softmax
model} \cite{Parr95}:
$$\widehat{V}(b) = \left [\sum_{\alpha \in \Gamma} \left [\sum_{s \in S} \alpha(s) b(s)\right ]^{k} \right ]^{\frac{1}{k}},$$
where $\Gamma$ is the set of linear functions $\alpha$ with
adaptive parameters to fit and $k$ is a ``temperature'' parameter that
provides a better fit to the underlying piecewise linear convex function
for larger values. The function represents a soft approximation of a
piecewise linear convex function, with the parameter $k$ smoothing the approximation.  

\subsubsection{Control}

%%%% \mynote{Example: Q-least square (lookahead and direct) + 2 alpha models}

We tested the control performance of the least-squares approach on the linear
Q-function model \cite{Littman:icml95} and the softmax
model \cite{Parr95}. For the softmax model we varied the number of linear
functions, trying cases with 10 and 15 linear functions respectively. 
In the first set of experiments we used parallel (synchronous) updates and
samples at a fixed set of 100 belief points.  We applied stochastic
gradient descent techniques to find the best fit in both cases. We tested
the control performance for value-function approximations obtained after
10, 20 and 30 updates, starting from the QMDP solution. In the second set
of experiments, we applied the incremental stochastic update scheme with
Gauss-Seidel-style updates. The 
results for this method were acquired after every grid point was updated
150 times, with learning rates decreasing linearly in the range between
$0.2$ and $0.001$. Again we started from the QMDP solution.
The results for lookahead controllers are summarized in
Figure \ref{fig:LSF-control}, which also shows the control performance of the
direct Q-function controller and, for comparison, the results for the QMDP
method.   
\begin{figure*}[t]
%%% \epsfxsize 0.45\textwidth
\begin{center}
   \mbox{ \epsfxsize 0.65\textwidth \epsffile{./FIGURE/LSF-control.eps}}
\end{center}
\caption{Control performance of least-squares fit methods. Models tested include:
linear Q-function model (with both direct and lookahead control) and   
softmax models with 10 and 15 linear functions (lookahead control
only). Value functions obtained after 10, 20 and 30 synchronous updates and
value functions obtained through the incremental stochastic update scheme
are used to define different controllers. For comparison, we also include
results for two QMDP controllers.} \label{fig:LSF-control} 
\end{figure*}

The linear-Q function model performed very well and the results for the 
lookahead design were better than the results for the QMDP
method. The difference was quite apparent for direct approaches. In 
general, the good performance of the method can be 
attributed to the choice of a function model that let us match the
shape of the 
optimal value function reasonably well.
In contrast, the softmax models (with 10 and 15 linear functions) did
not perform as expected. This is probably because
in the softmax model all linear functions are updated for every sample
point. This leads to situations in which multiple linear functions try to
track a belief point during its update. Under these circumstances it is hard
to capture the structure of the optimal value function accurately. 
The other negative feature is that the effects of on-line changes of all
linear functions are added in the softmax approximation, and thus could
 bias incremental update schemes. In the ideal
case, we would like to identify one vector $\alpha$ responsible for a specific
belief point and update (modify) only that vector. 
The linear Q-function approach avoids this 
problem by always updating only a single linear function (corresponding to
an action).  


%%%%%%%%%% grid-Sondik %%%%%%%%%%

\subsection{Grid-Based Approximations with Linear Function Updates
%% linear-function method %%%% (grid-based Sondik's method)
\label{sec:grid-based-Sondiks-method}}


%%% \mynote{Think about: add also results on standard grid-based method but
%%% with incremental updates}
 
An alternative grid-based approximation method can be constructed
by applying Sondik's approach for computing derivatives (linear functions)
to points of the grid \cite{Lovejoy:bounds91,Lovejoy:bounds93}.
Let $\widehat{V}_{i}$ be a piecewise linear convex function described
by a set of linear functions $\Gamma_{i}$. Then a new linear function for
a belief point $b$ and an action $a$ can be computed efficiently as
\cite{Smallwood73,Littman:thesis}   
\begin{equation}
\alpha_{i+1}^{b,a}(s) = \rho(s, a)+ \gamma \sum_{o \in \Theta} \sum_{s' \in S} P(s',o|s,a) \alpha^{\iota(b,a,o)}_{i}(s'),
\end{equation}
\normalsize
where $\iota(b,a,o)$ indexes a linear function $\alpha_{i}$ in a set of
linear functions $\Gamma_{i}$ (defining $\widehat{V}_{i}$) that maximizes
the expression
$$\sum_{s' \in S} \left [\sum_{s \in S} P(s',o|s,a) b(s) \right ] \alpha_{i}(s')$$
for a fixed combination of $b, a, o$.
The optimizing function for $b$ is then acquired by
choosing the vector with the best overall value from all action
vectors. That is, assuming $\Gamma_{i+1}^{b}$ is a set of all candidate
linear functions, the resulting functions satisfies
$$ \alpha_{i+1}^{b,*} = \arg\max_{\alpha_{i+1}^{b} \in
\Gamma_{i+1}^{b}} \sum_{s \in S} \alpha_{i+1}^{b}(s) b(s).$$ 

% Note that there is a problem of ties not addressed here 

A collection of linear functions obtained for a set of belief points can be
combined into a piecewise linear and convex value function. This is the idea
behind a number of exact algorithms (see
Section~\ref{sec:POMDP-exact-updates}). However, in the exact case, a set
of points that cover all linear functions defining the new
value function must be located first, which is a hard task in itself. 
In contrast, the approximation method uses an incomplete 
set of belief points that are fixed or at least easy to locate, for example
via random or heuristic selection. We use $H_{GL}$ to denote the
value-function mapping for the grid approach. 

The advantage of the grid-based method is that it leads to more efficient
updates. The time complexity of the update is polynomial and equals 
$O(\card{G}\card{A}\card{S}^{2}\card{\Theta})$. It yields a set of
$\card{G}$ linear functions, compared to $|A||\Gamma_{i}|^{|\Theta|}$
possible functions for the exact update. 

Since the set of grid-points is incomplete, the resulting approximation
lower-bounds the value function one would obtain by performing the exact
update \cite{Lovejoy:bounds91}.   

{\theorem \label{thm:linear-function-bound} {(Lower-bound property of the
grid-based linear function update). Let $\widehat{V}_{i}$ be a piecewise linear value
function and $G$ a set of grid points used to compute linear
function updates. Then $H_{GL} \widehat{V}_{i} \leq H
\widehat{V}_{i}$.}}

\medskip

\subsubsection{Incremental Linear-Function Approach}

The drawback of the grid-based linear function method is that
$H_{GL}$ is not a contraction for the discounted infinite-horizon
case, and therefore the value 
iteration method based on the mapping may not converge \cite{Lovejoy:bounds91}. To remedy this problem, we propose an
incremental version of the grid-based linear function method.  The idea of
this refinement is to prevent instability by gradually improving the
piecewise linear and convex lower bound of the value function. 

Assume that $\widehat{V}_{i} \leq V^{*}$ is a convex piecewise linear
lower bound of the optimal value function defined by a linear function
set $\Gamma_{i}$, and let $\alpha_b$ be a linear function for a point $b$
that is computed from $\widehat{V}_{i}$ using Sondik's method. 
Then one can construct a new
improved value function $\widehat{V}_{i+1} \geq \widehat{V}_{i}$ by simply
adding the new linear function $\alpha^{b}$ into $\Gamma_{i}$. That is: 
$\Gamma_{i+1} = \Gamma_{i} \cup \alpha_b$.
The idea of the incremental update, illustrated in Figure
\ref{fig:POMDP-lower-bound}, 
%%%%% figure
\begin{figure*}
%%% \mbox{\psfig{figure=./FIGURE/grid-sondik.eps}}
\epsfxsize 0.55\textwidth
\begin{center}
   \epsffile{./FIGURE/GS-new-function.eps}
\end{center}
\caption{An incremental version of the grid-based linear function method. The
piecewise linear lower bound is improved by a new linear function computed for a belief
point $b$ using Sondik's method.} 
\label{fig:POMDP-lower-bound}
\end{figure*}
%%%% end figure
is similar to incremental methods used by
Cheng \citeyear{Cheng:thesis} and Lovejoy \citeyear{Lovejoy:bounds93}. The method can be 
extended to handle a set of grid points $G$ in a straightforward way. 
%% However, it is advantageous to perform updates of grid points
%% one by one, as this leads to a much faster Gauss-Seidel approach. 
Note also
that after adding one or more new linear functions to $\Gamma_{i}$, some of
the previous linear functions may become redundant and can be removed from
the value function. Techniques for redundancy checking are the same as
are applied in the exact approaches \cite{Monahan82,Eagle84}.  


The incremental refinement is stable and converges for a fixed set of
grid points. The price paid for this feature is that the linear
function set $\Gamma_{i}$ can grow in size over the iteration
steps. Although the growth is at most linear in the number of iterations,
compared to the potentially exponential growth of exact methods, 
the linear function set describing the piecewise linear
approximation can become huge. %%% and possibly approach the complexity of
%%% value functions for exact methods. 
Thus, in practice we usually stop
incremental updates well before the method converges. The question that
remains open is the complexity (hardness) of the problem of finding the
fixed-point solution for a fixed set of grid points $G$.   

Figure \ref{fig:grid-Sondik-si} illustrates some of the trade-offs involved
in applying incremental updates compared to the standard fixed-grid
approach on the Maze20 problem. We use the same grid of 40 points for both
techniques and the same initial value function. Results for 1-10 update
cycles are shown. 
\begin{figure}[t]
%%%% \epsfxsize 0.45\textwidth
%%% \begin{center}
   \epsfxsize 0.47\textwidth  \epsffile{./FIGURE/G-Sondik-si-bounds.eps}
  \hspace*{10mm}
 \epsfxsize 0.45\textwidth
  \epsffile{./FIGURE/G-Sondik-si-times.eps}  
%%%% \end{center}
\caption{Bound quality and running times of the standard and incremental
  version of the grid-based linear-function method for the fixed 40-point
  grid. Cumulative running  times (including all previous update cycles)
  are shown for both methods. Running times of the QMDP and the fast
  informed bound methods are included for comparison.}  
\label{fig:grid-Sondik-si}
\end{figure}
We see that the incremental method has longer running times than the
standard method, since the number of linear functions can
grow after every update. 
%%% In contrast to this, the complexity of the update
%%% for the standard method is constant as the number of linear functions
%%% for every point of the grid does not grow.
On the other hand, the bound
quality of the incremental method improves more rapidly and it can never
become worse after more update steps.


\subsubsection{Minimum Expected Reward \label{sec:minimum-exp-reward}}

The incremental method improves the lower bound of the value
function. The value function, say $\widehat{V}_i$, can be used to create a
controller (with either the lookahead or direct-action choice). In the
general case, we cannot say anything about the performance 
quality of such controllers with regard to $\widehat{V}_i$. However, under certain
conditions the performance of both controllers is guaranteed never to fall 
below $\widehat{V}_i$. The following theorem (proved in the Appendix)
establishes these conditions.  

{\theorem \label{thm:value-control-rel} 
{Let $\widehat{V}_i$ be a value function obtained via the incremental
linear function method, starting from $\widehat{V}_{0}$, which corresponds
to some fixed strategy $C_{0}$. Let $C_{LA,i}$ and $C_{DR,i}$ be two controllers based on
$\widehat{V}_{i}$: the lookahead controller and the direct action
controller, and $V^{C_{LA,i}}$, $V^{C_{DR,i}}$ be their respective value
functions. Then $\widehat{V}_i \leq V^{C_{LA,i}}$ and $\widehat{V}_i \leq
V^{C_{DR,i}}$ hold. }} 

\medskip

We note that the same property holds for the incremental version of exact
value iteration.  That is, both the lookahead and the direct controllers
perform no worse than $V_{i}$ obtained after $i$ incremental updates from
some $V_{0}$ corresponding to a FSM controller $C_{0}$. 

\subsubsection{Selecting Grid Points} \label{sec:linear-vector-heuristic}

The incremental version of the grid-based linear-function approximation
is flexible and works for an arbitrary grid.\footnote{There is no
restriction on the grid points that must be included in the grid, such 
as was required for example in the linear point-interpolation scheme, which
had to use all extreme points of the belief simplex.}
Moreover, the grid need not be fixed and can be changed
on line. Thus, the problem of finding grids reduces to the
problem of selecting belief points to be updated next. One can
apply various strategies to do this. For example, one can use a fixed set of grid
points and update them repeatedly, or one can select belief points on line
using various heuristics.  

The incremental linear function method guarantees that the value function is
always improved (all linear functions from previous steps are kept unless
found to be redundant). The quality of a new linear function (to
be added next) depends strongly on the quality 
of linear functions obtained in previous steps. Therefore, our objective
is to select and order points with better chances of larger improvement. To
do this we have designed two heuristic strategies for 
selecting and ordering belief points. 

%%% With an objective to speed up the improvement of the value-function
%%% bound, we have 
%%% designed and implemented two relatively simple heuristic strategies that 
%%% try to optimize updates of a bound value function.  

The first strategy attempts to optimize updates at extreme points of the
belief simplex by ordering them heuristically. The idea of the heuristic is
based on the fact that states with higher expected rewards  (e.g. some designated goal
states) backpropagate their effects (rewards) locally. Therefore, it is desirable
that states in the neighborhood of the highest reward state be
updated first, and the distant ones later. We apply this idea to order
extreme points of the belief simplex, relying on the current estimate of
the value function
to identify the highest expected reward states and on a POMDP
model to determine the neighbor states. 
 
The second strategy is based on the idea of stochastic simulation. 
%%% and its combination with the first heuristics.
%%% , similar to
%%% the one we apply in the upper bound techniques. 
The strategy generates a sequence of belief points more likely to be
reached from some (fixed) initial belief point. The points
of the sequence are then used in reverse order to generate updates. 
%%% to update the current value function. 
The intent of this heuristic is to ``maximize'' the improvement of the value
function at the initial fixed point. To run this heuristic, we need to find
an initial belief point or a set of initial belief points. To
address this problem, we use the first heuristic that allows us to order
the extreme points of the belief simplex. These points are then used as
initial beliefs for the simulation part. Thus, we have a two-tier strategy:
the top-level strategy orders extremes of the belief simplex, and the lower-level
strategy applies stochastic simulation to generate a sequence of belief
states more likely reachable from a specific extreme point.  

We tested the order heuristics and the two-tier heuristics on
our Maze20 problem, and compared them also to two simple point
selection strategies: the fixed-grid strategy, in which a set of 40 grid
points was updated repeatedly, and the random-grid strategy, in which
points were always chosen uniformly at random. Figure \ref{fig:grid-Sondik-heuristics}
\begin{figure*}[t]
%%%% \epsfxsize 0.7\textwidth
\begin{center}
%%%   \epsfxsize 0.5\textwidth  \epsffile{./FIGURE/G-Sondik-times.eps}
\vspace*{3mm}
 \epsfxsize 0.65\textwidth  \epsffile{./FIGURE/G-Sondik-heuristics-bounds.eps} 
\end{center}
\caption{Improvements in the bound quality for the incremental
linear-function method and four different grid-selection heuristics. Each
cycle includes 40 grid-point updates. }
\label{fig:grid-Sondik-heuristics}
\end{figure*}
shows the bound quality of the methods for 10 update cycles (each cycle
consists of 40 grid point updates) on
the Maze20 problem. We see that the differences in the 
quality of value-function approximations for different strategies (even the
very simple ones) are relatively small. We note that we observed
similar results also for other problems, not just Maze20. 

The relatively small improvement of our heuristics can be
explained by the fact that every new linear function influences a larger portion
of the belief space and thus the method should be less sensitive to a
choice of a specific point.{\footnote {The small sensitivity of the
incremental method to the selection of grid points would suggest that one
could, in many instances, replace exact updates with simpler point
selection strategies. This could increase the speed of exact value-iteration methods (at least in their initial stages), which suffer from
inefficiencies associated with locating a complete set of grid
points to be updated in every step. However, this issue needs to be investigated.}} 
However, another plausible explanation is that our heuristics were not very
good and more accurate heuristics or combinations of heuristics
could be constructed. Efficient strategies for locating grid
points used in some of the exact methods, e.g. the Witness algorithm
\cite{Kaelbling:aij} or Cheng's methods \cite{Cheng:thesis} can potentially
be applied to this problem. This remains an open area of research. 
 

\subsubsection{Control}

%%%% control and heuristics (LA)
%%%% direct control (how good it is)
%%%% the usage of the 

The grid-based linear-function approach leads to a piecewise linear and convex
approximation. Every linear function comes with a natural action choice
that lets us choose the action greedily. Thus we can run both
the lookahead and the direct controllers. 
Figure \ref{fig:grid-Sondik-control}
\begin{figure}
%%% \epsfxsize 0.65\textwidth
\begin{center}
%%%   \epsfxsize 0.5\textwidth
%%%   \epsffile{./FIGURE/G-Sondik-40-times.eps} 
%%%% \mbox{\vspace*{8mm}}
  \epsfxsize 0.65\textwidth  \epsffile{./FIGURE/G-Sondik-si-control.eps}   
\end{center}
\caption{Control performance of four different controllers based on
grid-based linear function updates after 1, 5
and 10 update cycles for the same 40-point grid. Controllers 
represent combinations of two update strategies (standard and incremental)
and two action-extraction techniques 
(direct and lookahead). Running times for the two update strategies were
presented in Figure \ref{fig:grid-Sondik-si}. For comparison we include
also performances of the QMDP and the fast informed bound methods (with
both direct and lookahead designs). }
\label{fig:grid-Sondik-control}
\end{figure}
compares the performance of four 
different controllers for the fixed grid of 40 points, combining standard
and incremental updates with lookahead and direct greedy 
control after 1, 5 and 10 update cycles. The results (see also Figure \ref{fig:grid-Sondik-si}) illustrate the
trade-offs between the computational time of 
obtaining the solution and its quality. We see that the incremental
approach and the lookahead controller design tend to improve the control
performance. The prices paid are worse running and reaction times,
respectively. 
%%% We note that direct methods are not bad -
%%% suggesting the lookahead is not a big 
%%% issue here

\begin{figure*}[h]
%%% \epsfxsize 0.65\textwidth
\begin{center}
%%%   \epsfxsize 0.5\textwidth  \epsffile{./FIGURE/G-Sondik-htimes.eps}
%%%   \hspace*{10mm}
 \epsfxsize 0.65\textwidth  \epsffile{./FIGURE/G-Sondik-heuristics-control.eps}  
\end{center}
\caption{Control performances of lookahead controllers based on
  the incremental linear-function approach and different point-selection
  heuristics after 1, 5 and 10 improvement cycles. For comparison, scores
  for the QMDP and the fast informed bound approximations are shown as well.}
\label{fig:grid-Sondik-hcontrol}
\end{figure*}

Figure \ref{fig:grid-Sondik-hcontrol} illustrates the effect of point
selection heuristics on control. We compare the results for lookahead
control only, using approximations obtained after 1, 5 and 10 improvement cycles (each cycle consists of 40 grid point updates). The test results show that, as for the bound
quality, there are no big differences among various heuristics, suggesting
a small sensitivity of control to the selection of grid points. 


\subsection{Summary of Value-Function Approximations}

%%% \mynote{Mention truncated history}
Heuristic value-function approximations methods allow us to replace
hard-to-compute exact methods and trade off solution quality for
speed. There are numerous methods we can employ, each with different
properties and different trade-offs of quality versus 
speed. Tables~\ref{tab:methods-properties} and \ref{tab:methods-complexity}
summarize main theoretical properties of the approximation methods covered
in this paper. The majority of these methods are of polynomial 
complexity or at least have efficient (polynomial) Bellman updates. This
makes them good candidates for more complex POMDP problems that are out of
reach of exact methods. 

All of the methods are heuristic approximations in that they do not
give solutions of a guaranteed precision. Despite this fact we proved that
solutions of some of the methods are no worse than others 
in terms of value function quality (see Figure
\ref{fig:approx-relations}). This was one of the main contributions of the
paper. However, there are currently minimal
theoretical results relating these methods in terms of control
performance; the exception are some results for FSM-controllers and
FSM-based approximations. The key observation here is that for the quality of
control (lookahead control) it is more important to approximate the shape
(derivatives) of the value function correctly. This is also illustrated
empirically on grid-based interpolation-extrapolation methods in Section
\ref{sec:grid-based-control} that are based on non-convex value
functions. The main challenges here are to find ways of analyzing and comparing
control performance of different approximations also theoretically
and to identify classes of POMDPs for which certain methods dominate the
others.  

Finally, we note that the list of methods is not complete and other
value-function approximation methods or the refinements of existing methods
are possible. For example, White and Scherer \citeyear{White94} investigate
methods based on truncated histories that lead to upper and lower bound
estimates of the value function for complete information states (complete
histories). Also, additional restrictions on some of the methods can change the
properties of a more generic method. For example, it is possible that under
additional assumptions we will be able to ensure convergence of the
least-squares fit approximation.  

\begin{table}
\begin{center}
\small
\begin{tabular}{|l||l|l|l|} \hline
Method & Bound & Isotonicity & Contraction \\ \hline \hline
MDP approximation & upper & $\surd$ & $\surd$ \\ \hline
QMDP approximation & upper & $\surd$  & $\surd$ \\ \hline
Fast informed bound & upper & $\surd$ & $\surd$\\ \hline
UMDP approximation & lower & $\surd$ & $\surd$\\ \hline
Fixed-strategy method & lower & $\surd$ & $\surd$ \\ \hline
Grid-based interpolation-extrapolation & -  & -  & - \\ \hline
\mbox{ \hspace{0.4cm}}Nearest neighbor & -  & $\surd$  & $\surd$\\ \hline
\mbox{ \hspace{0.4cm}}Kernel regression & - & $\surd$ & $\surd$\\ \hline
\mbox{ \hspace{0.4cm}}Linear point interpolation & upper & $\surd$ &
$\surd$ \\ \hline
Curve-fitting (least-squares fit) & -  & - & -  \\ \hline
\mbox{ \hspace{0.4cm}} linear Q-function & -  & - & - \\ \hline
Grid-based linear function method & lower & - & - \\ \hline % this was added
\mbox{ \hspace{0.4cm}}Incremental version (start from a lower bound) &
lower & $\surd$ & - *\\ \hline
\end{tabular}
\normalsize
\caption{Properties of different value-function approximation methods:
bound property, isotonicity and contraction property of the underlying
mappings for $0 \leq \gamma < 1$. (*) Although incremental version of the
grid-based linear-function method is not a contraction it always converges.}  
\label{tab:methods-properties}
\end{center}
\end{table}


\begin{table}
\begin{center}
\small
\begin{tabular}{|l||l|r|} \hline
Method & Finite-horizon & Discounted infinite-horizon\\ \hline \hline
%%% &    &  infinite-horizon \\ \hline \hline
MDP approximation & P & P \\ \hline
QMDP approximation & P & P  \\ \hline
Fast informed bound & P & P \\ \hline
UMDP approximation & NP-hard & undecidable \\ \hline
Fixed-strategy method & P & P \\ \hline
%%%% restricted policy space & ?? & NP-hard \\ \hline
Grid-based interpolation-extrapolation & varies & NA \\ \hline
\mbox{ \hspace{0.4cm}}Nearest neighbor & P & P  \\ \hline
\mbox{ \hspace{0.4cm}}Kernel regression & P & P \\ \hline
\mbox{ \hspace{0.4cm}}Linear point interpolation & P & varies  \\
\hline 
\mbox{ \hspace{1cm}} Fixed interpolation & P & P \\ \hline
\mbox{ \hspace{1cm}} Best interpolation & P & ? \\ \hline
Curve-fitting (least-squares fit) & varies & NA \\ \hline
\mbox{ \hspace{0.4cm}} linear Q-function & P & NA \\ \hline
Grid-based linear function method & P & NA\\ \hline % this was added
\mbox{ \hspace{0.4cm}}Incremental version & NA & ? \\ \hline
\end{tabular}
\normalsize
\caption{Complexity of value-function approximation methods for
finite-horizon problem and discounted infinite-horizon problem. The
objective for the discounted infinite-horizon case is to find the corresponding
fixed-point solution. The complexity results take into account, in addition to components of
POMDPs, also all other approximation specific 
parameters, e.g., the size of the grid $G$ in grid-based methods. ?
indicates open instances and NA methods that are not 
applicable to one of the problems (e.g. because of possible divergence).} 
\label{tab:methods-complexity}
\end{center}
\end{table}


%%%%%%%%% CONCLUSION %%%%%%%


\section{Conclusions}

POMDPs offers an elegant mathematical framework for representing decision
processes in stochastic partially observable domains. Despite their modeling
advantages, however, POMDP problems are hard to solve exactly. Thus, the
complexity of problem solving-procedures becomes the key aspect in the
sucessful application of the model to real-world problems, even at the
expense of the optimality. As recent complexity results for the
approximability of POMDP problems are not encouraging
\cite{Lusena98,Madani:aaai99}, we focus on heuristic approximations, in
particular approximations of value functions.   
%%% remain one of the only solution we have in our arsenal.   

\subsection{Contributions}

%% survey and analysis + new methods
% The objective of the paper was twofold: as a survey with a
The paper surveys new and known value-function approximation methods for
solving POMDPs. We focus primarily on the theoretical analysis and
comparison of the methods, with findings and results supported
experimentally on a problem of moderate size from the agent navigation 
domain. We analyze the methods from different perspectives: their
computational complexity, capability to bound the optimal value
function, convergence properties of iterative implementations, and the
quality of derived controllers. The analysis includes new
theoretical results, deriving the properties of individual approximations,
and their relations to exact methods.        
In general, the relations between and
trade-offs among different methods are not well understood. We provide some new insights on
these issues by analyzing their corresponding updates. For example, we
showed that the differences among the exact, the MDP, the QMDP,
the fast-informed bound, and the UMDP methods boil down to simple mathematical
manipulations and their subsequent effect on the value-function
approximation. This allowed us to determine relations among different
methods in terms of quality of their respective value functions which is one
of the main results of the paper.

We also presented a number of new methods and
heuristic refinements of some existing techniques. The primary 
contributions in this area include the fast-informed
bound, grid-based point interpolation methods (including adaptive grid
approaches based on stochastic sampling), and the incremental linear-function method. We
also showed that in some instances the solutions 
can be obtained more  efficiently by converting the original approximation
into an equivalent finite-state MDP. For example, grid-based approximations
with convex rules can be often solved via conversion into a grid-based
MDP (in which grid points correspond to new states), leading to the
polynomial-complexity algorithm for both the finite and the discounted
infinite-horizon cases (Section \ref{sec:conversion-to-grid-MDP}). This
result 
%%% is not obvious and 
can dramatically improve the run-time
performance of the grid-based approaches. A similar conversion to the
equivalent finite-state MDP, allowing a polynomial-time solution for the
discounted infinite-horizon problem, was shown for the fast informed bound
method (Section \ref{fast-informed-bound}).  


\subsection{Challenges and Future Directions}

%%% Other methods and theoretical results


Work on POMDPs and their approximations is far from 
complete. Some complexity results remain open, in particular, the complexity of the
grid-based approach seeking the best interpolation, or the complexity of
finding the fixed-point solution for the incremental version of the
grid-based linear-function method. Another interesting issue that needs
more investigation is the convergence of value iteration with least-squares
approximation. Although the method can be unstable in the general case, it
is possible that under certain restrictions it will converge.

\commentout{
New approximation methods or
improvements of the existing  techniques are possible. A promising direction 
in this regard is a class of policy-approximation methods \cite{Platzman80}
(see Sections \ref{sec:policy-approx} and \ref{sec:fixed-policies}), that
has recently become the focus of attention of many researchers, both in planning and
reinforcement learning
\cite{Singh94,Littman94,McCallum:ml95,Hauskrecht:thesis,Hansen:uai98,Loch:icml98,Baird:NIPS98,Meuleau:uai99}.
The key advantage of the approach is that the value for a specific
policy (controller) can be evaluated efficiently. 
%%% say that we do not have the connection between the value funcIn contrast, the value 
%% function approximations do novalue
%%% function approximations suffer
%%%%  possibly new paper by Sutton    

}
 
%%% \subsubsection{Lack of Empirical studies}

In the paper we use a single POMDP problem (Maze20) only to
support theoretical findings or to illustrate some
intuitions. Therefore, the results not supported theoretically
(related mostly to control) cannot be generalized and used to rank different methods, since their
performance may vary on other problems. In general, the area of POMDPs and
POMDP approximations suffers from a shortage of larger-scale experimental
work with multiple problems of different complexities and a broad range of
methods.   
Experimental work is especially needed to study and compare
different methods with regard to control quality. The main reason for
this is that there are only few theoretical results relating the control
performance. These studies should help focus
theoretical exploration by discovering interesting cases and possibly
identifying classes of problems for which certain approximations are more or
less suitable. Our preliminary experimental results show that there are
significant differences in control performance among different methods and
that not all of them may be suitable to approximate the control
policies. For example, the grid-based nearest-neighbor approach with
piecewise-constant approximation is typically inferior to and outperformed by
other simpler (and more efficient) value-function methods. 

The present work focused on heuristic approximation methods. We investigated
general (flat) POMDPs and did not take advantage of any additional
structural refinements. However, real-world problems usually offer more
structure that can be exploited to devise new algorithms and
perhaps lead to further speed-ups. It is also possible that some of the restricted
versions of POMDPs (with additional structural assumptions) can be solved or
approximated efficiently, even though the general
complexity results for POMDPs or their $\epsilon$-approximations are not
very encouraging \cite{Papadimitriou87,Littman:thesis,Mundhenk:TR97,Lusena98,Madani:aaai99}. A challenge here is
to identify models that allow efficient solutions and are at the same time
interesting enough from the point of application.  

Finally, a number of interesting issues arise when we move to problems
with large state, action, and observation spaces. Here, the complexity of
not only value-function updates but also belief state updates becomes an issue. In general, partial
observability of hidden process states does not allow us to factor
and decompose belief states (and their updates), even 
when transitions have a great deal of structure and can be represented very
compactly. Promising directions to deal with these issues include various Monte-Carlo
approaches \cite{isard-blake:vision96,Kanazawa:uai95,Doucet98,Kearns:ijcai99}), 
methods for approximating belief states via decomposition
\cite{Boyen:uai98,Boyen:aaai99}, or a combination of the two approaches
\cite{McAllester:uai99}.  


%%%%%% ACKNOWLEDGEMENT

\section*{Acknowledgements}

Anthony Cassandra, Thomas Dean, Leslie Kaelbling,
William Long, Peter Szolovits and anonymous reviewers provided valuable
feedback and comments on this work. This research was supported by grant
RO1 LM 04493 and grant 1T15LM07092 from the National Library of Medicine,
by DOD Advanced Research Project Agency  (ARPA) under contract number
N66001-95-M-1089 and DARPA/Rome Labs Planning Initiative grant
F30602-95-1-0020.  



%%%%%%%% APPENDIX %%%%%%%%%%%% 
\appendix

\section{Theorems and proofs} \label{sec:appendix:theorems-proofs}

\subsection{Convergence to the Bound}

\vspace{-0.4cm}
\setcounter{theorem}{\ref{thm:convergence-to-bound}}
\addtocounter{theorem}{-1}
{\theorem 
{Let $H_1$ and $H_2$ be two value-function
mappings defined on ${\cal V}_1$ and ${\cal V}_2$ s.t. \vspace{-0.2cm} 
\begin{enumerate}
\item $H_1$, $H_2$ are contractions with fixed points $V_{1}^{*}$,
$V_{2}^{*}$;
\item $V^{*}_1 \in {\cal V}_2$ and $H_2 V_{1}^{*} \geq H_1 V_{1}^{*} = V_{1}^{*}$;
\item $H_2$ is an isotone mapping.
\end{enumerate}
\vspace{-0.2cm}Then $V^{*}_2 \geq V_{1}^{*}$ holds.}}

\proof{By applying $H_2$ to condition 2 and expanding the result with
condition 2 again we get:
$ H^{2}_2 V^{*}_1 \geq H_2 V^{*}_1 \geq H_1 V^{*}_1 = V^{*}_1$. 
Repeating this we get in the limit $V^{*}_2 \geq \cdots \geq H_2^{n}V^{*}_1 \geq \cdots
H^{2}_2 V^{*}_1 \geq H_2 V^{*}_1 \geq H_1 V^{*}_1 =V^{*}_1$, which proves the
result.}
 
\subsection{Accuracy of a Lookahead Controller Based on Bounds}

\setcounter{theorem}{\ref{thm:bound-accuracy}}
\addtocounter{theorem}{-1}
% \setcounter{theorem}{7}
{\theorem {Let $\widehat{V}_U$ and $\widehat{V}_L$ be upper and lower
bounds of the optimal value function for the discounted infinite-horizon
problem. Let $\epsilon = \sup_{b}|\widehat{V}_U(b)-\widehat{V}_L(b)| =
\|\widehat{V}_U - \widehat{V}_L\|$ be the maximum bound difference. Then the expected 
reward for a lookahead controller $\widehat{V}^{LA}$, constructed for
either $\widehat{V}_U$ or $\widehat{V}_L$, satisfies $\|\widehat{V}^{LA} -
V^{*}\| \leq \frac{\epsilon (2 - \gamma)}{(1-\gamma)}$.}}

\proof{Let $\widehat{V}$ denotes either an upper or lower bound approximation of
$V^{*}$ and $H^{LA}$ be the value function mapping corresponding to the
lookahead policy for $\widehat{V}$. Note, that since the lookahead policy always optimizes its actions
with regard to $\widehat{V}$, $H \widehat{V} = H^{LA} \widehat{V}$ must hold. 

\noindent The error of $\widehat{V}^{LA}$ can be bounded using the triangle
inequality
$$\|\widehat{V}^{LA} - V^{*}\| \leq \|\widehat{V}^{LA} - \widehat{V}\| +
\|\widehat{V} - V^{*}\|.$$

\noindent The first component satisfies:
\begin{eqnarray*}
\|\widehat{V}^{LA} - \widehat{V}\| & = & \|H^{LA} \widehat{V}^{LA} -
\widehat{V} \|\\
 & \leq & \|H^{LA} \widehat{V}^{LA} - H \widehat{V}\| + \|H \widehat{V} - \widehat{V}\| \\
 & = &  \|H^{LA} \widehat{V}^{LA} - H^{LA} \widehat{V}\| + \|H \widehat{V} - \widehat{V}\| \\
 & \leq & \gamma \|\widehat{V}^{LA} - \widehat{V}\| + \epsilon
\end{eqnarray*}
The inequality:
$\|H \widehat{V} - \widehat{V}\| \leq \epsilon$ follows from the
isotonicity of $H$ and the fact that $\widehat{V}$ is either an upper or a
lower bound. Rearranging the inequalities, we obtain:
$\|\widehat{V}^{LA} - \widehat{V}\| = \frac{\epsilon}{(1-\gamma)}$. 

\noindent The bound on the second term $\|\widehat{V} - V^{*}\| \leq
\epsilon$ is trivial. 

Therefore,
$\|\widehat{V}^{LA} - V^{*}\| \leq \epsilon[\frac{1}{(1-\gamma)} + 1] =
\epsilon\frac{(2 - \gamma)}{(1-\gamma)}$. 
} %%% end proof


\subsection{MDP, QMDP and the Fast Informed Bounds}

\setcounter{theorem}{\ref{thm:FIB-fixed-point}}
\addtocounter{theorem}{-1}
% \setcounter{theorem}{8}
{\theorem {A solution for the
fast informed bound approximation can be found by solving an
MDP with $|S||A||\Theta|$ states, $|A|$ actions and the same discount
factor $\gamma$.}}

\proof{
%%% The proof is based on the conversion of the problem to an
%%% equivalent MDP with $|S||A||\Theta|$ states.
Let $\alpha^{a}_i$ be a linear function for action $a$ defining
$\widehat{V}_i$. Let $\alpha_i(s,a)$ denote parameters of the
function. The parameters of $\widehat{V}_{i+1}$ satisfy:
$$\alpha_{i+1}(s,a) = \rho(s,a)+\gamma \sum_{o
\in \Theta} \max_{a' \in A} \sum_{s' \in S} P(s',o|s,a)\alpha_{i}(s',a').$$
Let 
$$\alpha_{i+1}(s,a,o) = \max_{a' \in A} \sum_{s'
\in S} P(s',o|s,a)\alpha_{i}(s',a').$$
Now, we can rewrite $\alpha_{i+1}(s,a,o)$ for every $s,a,o$ as:
\begin{eqnarray*}
\alpha_{i+1}(s,a,o) & = & \max_{a' \in A} \left \{ \sum_{s' \in S} P(s',o|s,a) \left [
\rho(s',a')+\gamma \sum_{o' \in \Theta} \alpha_{i}(s',a',o') \right ]
\right \}\\
& = & \max_{a' \in A} \left \{ \left [ \sum_{s' \in S} P(s',o|s,a)
\rho(s',a') \right ] + \gamma
\left [ \sum_{o' \in \Theta} \sum_{s' \in S} P(s',o|s,a) \alpha_{i}(s',a',o')
\right ] \right \}
\end{eqnarray*} 
 
These equations define an MDP with state space $S \times A
\times \Theta$, action space $A$ and discount 
factor $\gamma$. Thus, a solution for the fast informed bound update can be
found by solving an equivalent finite-state MDP. 
%% As the 
%% new MDP can be solved efficiently (as a linear program) we can
%% find all linear functions $\alpha^{a}$ efficiently in polynomial time. 
}  %%% end proof

\setcounter{theorem}{\ref{thm:upper-bounds}}
\addtocounter{theorem}{-1}
% \setcounter{theorem}{9}
{\theorem 
{Let $\widehat{V}_{i}$ corresponds to a piecewise linear convex
value function defined by $\Gamma_{i}$ linear functions. Then $H\widehat{V}_{i} \leq H_{FIB}\widehat{V}_{i} \leq H_{QMDP}\widehat{V}_{i}
\leq H_{MDP}\widehat{V}_{i}.$
}}

\medskip \noindent {\bf Proof} \mbox{\vspace{0.2cm}}
%%% The idea of the proof is to gradually swap max and sum
%%% operators in the exact update 
\begin{eqnarray*}
& \mbox{ } & \max_{a \in A} \left \{ \sum_{s \in S} \rho(s, a)b(s) + \gamma
\sum_{o \in \Theta}  \max_{\alpha_{i} \in \Gamma_{i}} \sum_{s' \in S}
\sum_{s \in S} P(s',o|s,a) b(s) \alpha_{i}(s') \right \}\\
& = & (HV_{i})(b) \\
& \leq & \max_{a \in A} \sum_{s \in S}
b(s)\left [ \rho(s, a) + \gamma \sum_{o \in \Theta}
\max_{\alpha_{i} \in \Gamma_{i}}  \sum_{s' \in S} P(s',o|s,a)
\alpha_{i}(s')\right ]\\
& = & (H_{FIB}V_{i})(b)\\
& \leq & \max_{a \in A} \sum_{s \in S} b(s)\left [\rho(s, a) + \gamma  \sum_{s'
\in S} P(s'|s,a) \max_{\alpha_{i} \in \Gamma_{i}}  \alpha_{i}(s') \right]\\ 
& = & (H_{QMDP}\widehat{V}_{i})(b)\\
& \leq & \sum_{s \in S} b(s)\max_{a \in A} \left [\rho(s, a) + \gamma  \sum_{s'
\in S} P(s'|s,a) \max_{\alpha_{i} \in \Gamma_{i}}
\alpha_{i}(s')\right ]\\
& = &  (H_{MDP} \widehat{V}_{i})(b) \mbox{\hspace{0.5cm}} \Box
\end{eqnarray*}



\subsection{Fixed-Strategy Approximations}

\setcounter{theorem}{\ref{thm:FSM-controller-improvement}}
\addtocounter{theorem}{-1}
{\theorem 
{Let $C_{FSM}$ be an FSM controller. Let $C_{DR}$ and $C_{LA}$ be the
direct and the one-step-lookahead controllers constructed based on $C_{FSM}$. Then
$V^{C_{FSM}}(b) \leq V^{C_{DR}}(b)$ and $V^{C_{FSM}}(b) \leq
V^{C_{LA}}(b)$ hold for all belief states $b \in {\cal I}$.}}

\setcounter{equation}{0}

\proof{The value function for the FSM controller $C_{FSM}$ satisfies:
$$V^{C_{FSM}}(b) = \max_{x \in M} V(x,b) = V(\psi(b),b)$$
where 
$$V(x,b) = \rho(b,\eta(x)) + \gamma \sum_{o \in \Theta}
P(o|b,\eta(x)) V(\phi(x,o), \tau(b,\eta(x),o)).$$

The direct controller $C_{DR}$ selects the action greedily in every step,
that is, it always chooses according to $\psi(b) = \arg\max_{x \in M}
V(x,b)$. The lookahead controller $C_{LA}$ selects the action based on
$V(x,b)$ one step away:  
$$\eta^{LA} (b) = \arg\max_{a \in A} \left [\rho(b,a) + \gamma \sum_{o \in \Theta}
P(o|b,a) \max_{x' \in M} V(x', \tau(b,a,o)) \right ].$$

By expanding the value function for $C_{FSM}$ for one step we get:
\begin{eqnarray}
\lefteqn{V^{C_{FSM}}(b) = \max_{x \in M} V(x,b)} \nonumber \\
& = &  \max_{x \in M} \left [ \rho(b,\eta(x)) + \gamma \sum_{o \in \Theta}
P(o|b,\eta(x)) V(\phi(x,o), \tau(b,\eta(x),o)) \right ]
\label{C:step1} \\
& = & \rho(b,\eta(\psi(b))) + \gamma \sum_{o \in \Theta}
P(o|b,\eta(\psi(b))) V(\phi(x,o), \tau(b,\eta(\psi(b)),o)) \nonumber\\
& \leq & \rho(b,\eta(\psi(b))) + \gamma \sum_{o \in \Theta}
P(o|b,\eta(\psi(b))) \max_{x' \in M} V(x',
\tau(b,\eta(\psi(b)),o)) \label{C:step2}\\
& \leq & \max_{a \in A} \left [ \rho(b,a) + \gamma \sum_{o \in \Theta}
P(o|b,a) \max_{x' \in M} V(x', \tau(b,a,o)) \right ] \nonumber \\
& = &  \rho(b,\eta^{LA}(b)) + \gamma \sum_{o \in \Theta}
P(o|b,\eta^{LA}(b)) \max_{x' \in M} V(x', \tau(b,\eta^{LA}(b),o))  \label{C:step3}
\end{eqnarray}
Iteratively expanding $\max_{x' \in M} V(x,.)$ in \ref{C:step2} and
\ref{C:step3} with expression \ref{C:step1} and substituing improved
(higher value) expressions \ref{C:step2} and \ref{C:step3} back we obtain
value functions for both the direct and the lookahead controllers.
(Expansions of \ref{C:step2} lead to the value for the direct controller
and expansions of \ref{C:step3} to the value for the lookahead controller.)
Thus $V^{C_{FSM}} \leq V^{C_{DR}}$ and $V^{C_{FSM}} \leq V^{C_{LA}}$ must
hold. 
Note, however, that action choices $\psi(b)$ and $\psi^{LA}(b)$ in
expressions \ref{C:step2} and \ref{C:step3} can be
different leading to different next step belief states and subsequently to
different expansion sequences. Therefore, the above result does not imply
that $V^{DR}(b) \leq V^{LA}(b)$ for all $b \in {\cal I}$. 
} %%% end of proof


\commentout{
\subsection{Grid-based Interpolation-Extrapolation Methods}

{\theorem {Let $G$ be a set of grid points including extreme points
of the belief simplex and $R_G$ a point interpolation rule. The sequence of
grid-based MDPs that optimize interpolation coefficients 
($\lambda_{i,j}^{a,o}$) locally after every step converges to the
interpolation with the best (minimum) value function. }} 

\medskip

\proof{
First we prove that whenever there is a difference in value functions for the
optimal (best interpolation) and the current interpolation there exists a local
interpolation improvement. 

Let $H_g$ be a
mapping corresponding to the current choice of interpolation coefficients
($\lambda_{i,j}^{a,o}$) and $V_g^{*}$ its fixed point solution. Let
$H_{g^{*}}$ be an interpolation leading to the optimal value and 
$V_{g^{*}}^{*}$ its fixed point solution. For any grid point $b_j \in G$
the value function of the optimal interpolation satisfies
$V_{g^{*}}^{*}(b_j) \leq V_g^{*}(b_j)$.
 
Assume (for the purpose of contradiction) that the solution based on the
current interpolation $H_g$ is suboptimal (in at least one grid point) and
that no local improvement is possible. Let $\delta = \max_{j=1, \cdots, |G|}
\left [V_g^{*}(b_j) - V_{g^{*}}^{*}(b_j)\right ]$ and $k=\arg\max_{j=1,
\cdots, |G|} \left [V_g^{*}(b_j) - V_{g^{*}}^{*}(b_j)\right ]$. $V_g^{*}$
is the fixed point solution for the suboptimal interpolation, thus $\delta > 0$
must hold. As the optimal interpolation update $H_{g^{*}}$ is an isotone
contraction with the discount factor $\gamma$, 
$$(H_{g^{*}} V_g^{*})(b_k)- (H_{g^{*}}V_{g^{*}}^{*})(b_k) = V_g^{*}(b_k) -
(H_{g^{*}}V_{g^{*}}^{*})(b_k) \leq \gamma \delta.$$
This is a contradiction, as the interpolation based on $H_{g}^{*}$
gives an example of a local improvement (of $(1-\gamma)\delta$) for the
grid point $b_k$. 

Now we show that the sequence of grid-based MDPs based on local
improvements defines a contraction mapping under the supremum norm over
their respective value functions. Let $H^{M}$ be the value function
mapping that always maps a fixed-point (value-function) solution
$V_{g}^{*}$ for a grid-based MDP based on the current interpolation to the
new fixed point solution $V_{g'}^{*}$ corresponding to the best local
interpolation improvement. 
We use $H_{g'}$ to denote the value-function mapping corresponding to the
new (improved) interpolation based on $V_g^{*}$.
Then
\begin{eqnarray*} 
\|H^{M} V_{g^{*}}^{*} - H^{M} V_{g}^{*}\| = \|V_{g^{*}}^{*} - V_{g'}^{*} \|
\leq \| V_{g^{*}}^{*} - H_{g'}V_g^{*}\| \leq \\
\leq \|V_{g^{*}}^{*} - H_{g^{*}}V_g^{*}\| = \|H_{g^{*}}V_{g^{*}}^{*} -
H_{g^{*}}V_g^{*}\| \leq \gamma \|V_{g^{*}}^{*} - V_g^{*}\|
\end{eqnarray*}
The first inequality follows from the isotonicity of $H_{g'}$ and the
second from the fact that $H_{g'}$ represents the best local improvement of
$V_g^{*}$. Thus, $H^{M}$ is contraction mapping and applying the Banach theorem
the sequence of grid-based improvements converges to the optimal (minimal)
grid-based MDP.  
}

} %%% end commentout



\subsection{Grid-Based Linear-Function Method}

\commentout{
%%% \setcounter{theorem}{\ref{thm:linear-function-bound}}
\setcounter{theorem}{14}
{\theorem {(Lower bound property of the grid-based linear-function
update \cite{Lovejoy:bounds91}).  Let $\widehat{V}_{i}$ be a piecewise linear value
function and $G$ a set of grid points used to compute linear
function updates. Then $H_{GL} \widehat{V}_{i} \leq H
\widehat{V}_{i}$.}}
\medskip

\proof{The proof is based on the completeness argument. Let
$\Gamma^{G}_{i+1}$ be a set of optimizing linear functions 
computed for a grid set $G$ and $\Gamma_{i+1}$ a set of linear functions
for the exact update. Since a set of grid points $G$ may be incomplete,
$\Gamma^{G}_{i+1} \subseteq \Gamma_{i+1}$ must hold. Therefore
$$(H_{GL} \widehat{V}_{i})(b) = \max_{\alpha \in \Gamma^{G}_{i+1}} \sum_{s
\in S} \alpha(s)b(s) \leq \max_{\alpha \in \Gamma_{i+1}} \sum_{s
\in S} \alpha(s)b(s) = (H \widehat{V}_{i})(b).$$
} % end of proof
} %%%% end commentout

\setcounter{theorem}{\ref{thm:value-control-rel}}
\addtocounter{theorem}{-1}
%% \setcounter{theorem}{15}
{\theorem
{Let $\widehat{V}_i$ be a value function obtained via the incremental
linear function method, starting from $\widehat{V}_{0}$, which corresponds
to some fixed strategy $C_{0}$. Let $C_{LA,i}$ and $C_{DR,i}$ be two
controllers based on 
$\widehat{V}_{i}$: the lookahead controller and the direct action
controller, and $V^{C_{LA,i}}$, $V^{C_{DR,i}}$ be their respective value
functions. Then $\widehat{V}_i \leq V^{C_{LA,i}}$ and $\widehat{V}_i \leq
V^{C_{DR,i}}$ hold. }}

\proof{
By initializing the method with a value function for some FSM controller
$C_0$, the incremental updates can be interpreted as additions of new
states to the FSM controller (a new linear function corresponds to a new
state of the FSM). Let $C_i$ be a controller after step $i$. Then
$V^{C_{FSM,i}} = \widehat{V}_{i}$ holds 
and the inequalities follow from Theorem
\ref{thm:FSM-controller-improvement}.} 


\bibliographystyle{theapa}
\bibliography{refs}

\end{document}  





