%\documentstyle[jair,11pt]{article}

\documentstyle[jair,twoside,11pt]{article}
\input epsf %% at top of file

\jairheading{7}{1997}{199-230}{5/97}{11/97}
\ShortHeadings{Model Approximation for Planning under Uncertainty}
{Zhang \& Liu}
\firstpageno{199}

\title{A Model Approximation Scheme for Planning in 
	Partially Observable Stochastic Domains}



\author{\name Nevin L. Zhang  \email lzhang@cs.ust.hk \\
	\name Wenju Liu  \email wliu@cs.ust.hk  \\
	\addr  Department of Computer Science \\ 
	 Hong Kong University of Science and Technology \\
	Hong Kong, China }
	 

\begin{document}

\maketitle

\newtheorem{theo}{Theorem}
\newtheorem{cor}{Corollary}
\newtheorem{pro}{Proposition}
\newtheorem{lem}{Lemma}
\newtheorem{con}{Conjecture}


\begin{abstract}
Partially observable Markov decision processes (POMDPs) are
a natural model for planning problems where effects of actions
are nondeterministic and the state of the world is not
completely observable.
It is difficult to solve POMDPs exactly.
This paper proposes a new approximation scheme.
The basic idea is to transform a POMDP into 
another one where additional information is provided 
by an oracle. The oracle informs the
planning agent that the current state of the world is in a
certain  region.  The transformed POMDP is consequently said to be
 region observable. It is easier to solve than
the original POMDP. 
We propose to solve the transformed POMDP and use its optimal policy 
to construct an approximate policy for the original POMDP.
By controlling the amount of additional
information that the oracle provides, it is possible to find 
a proper tradeoff between computational time and approximation
quality.
In terms of algorithmic contributions,
we study in details how to exploit region observability in solving
the transformed POMDP. To facilitate the study, we also propose 
a new  exact algorithm for general POMDPs.  
The algorithm is conceptually simple and yet is significantly
more efficient than all previous exact algorithms.
 
\end{abstract}
	
\section{Introduction}
\label{sec1}

%To plan is to find a policy that will lead an agent to 
%achieve a goal with minimum cost.
%When the environment  of the agent, henceforth referred to as
%the world,  is completely observable and
%the effects of actions are deterministic, planning is reduced to 
%finding the shortest sequence of actions that will lead the  
%agent to the goal.


In a completely observable and deterministic world,
to plan is to find a sequence of actions that will lead an agent
to achieve a goal.
In real-world applications, 
the world is rarely
completely observable and effects of actions are almost always
nondeterministic.  For this reason,  a growing number of
researchers concern themselves with planning in 
partially observable stochastic 
domains (e.g., Dean \& Wellman, 1991; Cassandra {\em et al}.,  1994;
Parr \& Russell, 1995; Boutilier \& Poole, 1996).  
Partially observable Markov decision processes (POMDPs) 
can be used as a model for planning in such  domains.  In this model,
 nondeterminism in effects of actions is encoded
by transition probabilities, partial observability of 
the world by observation probabilities,
and goals and criteria for good plans  by reward functions
(see Section \ref{sec2} for details).
%This paper is concerned with how to solve a POMDP.

POMDPs are classified into {\em finite horizon} POMDPs and
{\em infinite horizon} POMDPs depending on the number of time points considered.
Infinite horizon POMDPs are usually used for planning because 
one typically does  not know beforehand the number of steps it takes to 
achieve a goal.
This paper is concerned with how to solve an infinite horizon
POMDP.


\subsection{Difficulties in Solving POMDPs}
%It is well known that infinite horizon POMDPs can be approximated by finite
%horizon POMDPs to arbitrary precision (Section \ref{sec3}).  Discussion in 
%rest of this introduction 
%is restricted to finite horizon
%POMDPs.

When the world is fully observable, a POMDP reduces
to a {\em Markov decision process} (MDP). MDPs have been studied
extensively in the dynamic-programming 
literature (e.g., Puterman, 1990; Bertsekas, 1987,
White, 1993).
Recent works have concentrated on how to  deal with 
large state spaces 
(Dean {\em et al}., 1993; Boutilier {\em et al}., 1995; Dean \& Lin, 1995).

We are concerned with the partially observable case.
This case is considerably more difficult than the fully observable case
for two related reasons.  First, when
the agent knows exactly in which state the world  currently is, 
information from the past (past observations and actions) 
is irrelevant to the current decision.  This is the 
Markov property. On the other hand,
when the agent does not fully observe
 the state of the world, past information  
becomes relevant because it can help the agent
 to better estimate the  current state of the world.
 The problem is that the number of possible states of past information 
increases exponentially with time.    



Second, in MDPs the effects of an action are fully observed at the
next time point. In POMDPs, on the other hand,
the effects of an action are not fully observed at the
next time point. 
Hence one cannot clearly tell the effects of the current action from
those of the agent's future behaviors.
To properly evaluate the effects of an action, one needs
to look into the future and 
 consider the combination of the action with each of the 
 agent's possible  behaviors in a, possibly large, number of
future steps.  The problem
is that the number of ways the agent can behave 
 is exponential in the number of future steps considered.

%Let $\delta$ be a possible future behavior.
%Let \(V(s_{\mbox{\tiny +}}, \delta)\) the be total rewards the agent
%receives in the future if the world is in state $s_{\mbox{\tiny +}}$
%at the next time point and if the agent behaves according to $\delta$.
% Viewed as a function of $s_{\mbox{\tiny +}}$,
%$V(s_{\mbox{\tiny +}}, \delta)$ will be referred to as
% a {\em future value function}.
%The second  difficulty mentioned above can be restated as that
%the number of possible future value functions
%is exponential.       

\subsection{Previous Work}
Previous methods for solving  POMDPs 
are usually classified into
exact methods and approximate methods (Lovejoy, 1991a).  
They can also
can be classified according to which  of the aforementioned two difficulties
they directly address.  
Most  previous methods
address the difficulty of
exponential number of  future behaviors
(Sondik, 1971; Sondik \& Mendelssohn,  1979; Monahan, 1982; 
Cheng, 1988; Lovejoy, 1991b; and Cassandra {\em et al}., 1994). 
They prune from consideration  behaviors that can never be optimal no matter what
the information state is
(Section \ref{sec4}).  
Other methods deal with the problem of exponential  
number of  past information states either  by aggregating them  
 (Platzman, 1977;  
White \& Schere, 1994) or by considering only a subset of them
(Lovejoy, 1992; Brafman, 1997; Hauskrecht, 1997).
They are approximation methods
in nature.
 
\subsection{Model Approximation}


In  previous approximation methods,  
approximation takes place in the process of solving a POMDP.
% approximate the solution to a POMDP and hence can be categorized
%as {\em solution approximation methods}. 
We advocate {\em model approximation methods}. 
Such a method
approximates a POMDP itself by another one that is easier to solve
and uses the solution of the latter to construct an approximate solution to
the original POMDP.

Model approximation can be in the form of a more informative
observation model, or  a more deterministic action model,
or a simpler state space, or a combination of two or all of the
three alternatives.
Cassandra {\em et al}. (1996) proposed to approximate
 POMDPs  by using MDPs. This is an example of model approximation
in the form of a more informative observation model.
There is also some work on reducing the size of the state spaces of 
 MDPs by aggregation (e.g.,   
 Bertsekas \& Castanon, 1989; Dean \& Lin, 1995; Dean \& Givan, 1997).
Such work can be conceivably extended to POMDPs, leading to
model approximation in the form of a simpler state space.
We are not aware of any model approximation schemes
in the form of a more deterministic action model.
 
 

\subsection{Our Proposal}

This paper proposes a new model approximation scheme in 
the form of a more informative observation model. 
It is a generalization of the idea of approximating POMDPs
by using MDPs.


We transform a POMDP
by assuming that, in addition to
the observations obtained by  itself,  the agent also receives
a report from an oracle who knows the true state of
the world.  The oracle does not report the true state itself. Instead,
it selects, from a predetermined 
list of candidate regions, a region that
contains the true state and reports that region.  
The transformed POMDP is said to be {\em region observable} because
 the agent knows for sure that the true state is in  the region reported by
 the oracle.


When all candidate regions are  singletons,
the oracle actually reports the true state of the world. 
The region observable POMDP reduces to an MDP.
MDPs are much easier to solve than POMDPs.  One would expect
the region observable POMDP to be solvable when all candidate regions
are small.  

In terms of approximation quality,  
the larger the candidate regions, the less
additional information the oracle provides and hence the more
accurate the
approximation.
In the extreme case when there is only one candidate region and
it consists of all possible states of the world, the oracle
provides no additional information at all. Consequently, the
region observable POMDP is identical to the original POMDP.

A method for 
determining approximation quality  will be described later
in this paper.
It allows one to make the tradeoff between
approximation quality  and computational time as follows:
 start with small candidate
regions and increase their sizes gradually until the approximation
becomes accurate enough or the region observable POMDP becomes 
untractable.  

Due to problem characteristics, 
accurate approximation can usually
be achieved with small candidate regions.
In many applications the agent 
often has a good idea about the 
state of the world (e.g., Simmons \& Koenig, 1995). 
Take   robot path planning as an example.  
Observing a landmark,
a room number for instance, would imply that the robot is 
at the proximity of that landmark.  Observing a feature about the
world, a corridor T-junction for instance, might imply the robot is 
in one of several regions. Taking history into account, the robot
might be able to determine a unique region for its current location. 
Also, an action usually moves the state of the world to 
only a few ``nearby" states. 
Thus if the robot has a good idea about the 
current state of world, it should continue to have  a good idea about
it in the next few steps. 

When the agent has a good idea about the state of the world at all times,
the oracle does not provide much additional information even with small
candidate regions and hence approximation is accurate.  Region
observable POMDPs with small candidate regions are much
easier to solve than general POMDPs.


\subsection{Organization}

We will first  show how POMDPs can be used as a model for planning
in partially observable stochastic domains 
(Section \ref{sec2}) and  give a  concise review of 
the theory of POMDPs (Sections \ref{sec3} and \ref{sec4}).
We will then
propose a new method for dynamic-programming updates,
 a key step in algorithms that
solve POMDPs via value iteration
(Section \ref{sec.incr}).
Thereafter, we will 
 formally introduce the concept of region observable
POMDPs (Section \ref{sec5}) and develop
 an algorithm
for solving region observable POMDPs (Sections \ref{sec6}, \ref{sec7}, and
\ref{sec8}). 
In   Section \ref{sec9}, we will discuss 
decision making for the original POMDPs  based on 
the solutions of their region observable approximations, 
followed by a method for determining 
 approximation quality (Section \ref{sec.qua}) and 
a method to make the tradeoff between approximation quality
and computational time (Section \ref{sec.trade}).
Finally, empirical results will be reported in Section \ref{sec10} and
conclusions will be provided in Section \ref{sec11}.


\section{Planning in Stochastic Domains and POMDPs}
\label{sec2}

To specify a planning problem, one needs to give 
a set  ${\cal S}$ of possible states
of the world, a set ${\cal O}$ of  
 possible observations, and a  set ${\cal A}$ of possible actions.  
 The sets ${\cal O}$ and ${\cal A}$ are always assumed to be finite
 in the literature,
 while the state space ${\cal S}$ can be continuous as well as finite.
 In this paper, we consider only finite state space.
 One needs also to give an observation model which describes
 the relationship between observations and the  state of the
 world, and an action model which describes  effects of actions.  
 %Furthermore, one needs
% to specify the initial state of the world and a goal state.  
%Finally, one needs to define what is
% an optimal plan.


 As a background example, consider path planning for
a robot who acts in an office environment.     Here
${\cal S}$ is
the set of all location-orientation pairs, ${\cal O}$ is the set
of possible sensor readings, and ${\cal A}$ consists of actions
\verb+move-forward+,  \verb+turn-left+,  \verb+turn-right+,  
and \verb+declare-goal+. 
%where \verb+go-east+, for instance,
%means to move one step eastward.

The current observation $o$ depends on 
the current state of the world  $s$.
Due to sensor noise, this dependency is uncertain in nature.
The observation $o$ sometimes also depends on
the action that the robot has just taken  $a_{\mbox{\small -}}$. 
The minus sign in the subscript indicates the previous time point.
In the POMDP model, the dependency of $o$ upon
$s$ and $a_{\mbox{\small -}}$ is numerically characterized by a conditional probability
$P(o|s, a_{\mbox{\small -}})$, which is usually referred to  
as the {\em observation probability}.  It is the observation model.

In a region observable POMDP, the current observation also depends
on the previous state of the world $s_{\mbox{\small -}}$.  The observation
probability for this case can be written as 
$P(o|s, a_{\mbox{\small -}}, s_{\mbox{\small -}})$.

The state $s_{\mbox{\tiny +}}$ the world will be in  
at the next time point  
depends on the current action $a$ and the current state $s$.
The plus sign in the subscript indicates the next time point.
This dependency is again uncertain
in nature due to  uncertainty in the actuator.
 In the POMDP model, the
dependency of $s_{\mbox{\tiny +}}$ upon $s$ and $a$ is numerically characterized
by a conditional probability $P(s_{\mbox{\tiny +}}|s, a)$,
which is usually referred to  as the {\em transition 
probability}.  It is the action model.

On many occasions, we need to consider the joint conditional probability
$P(s_{\mbox{\tiny +}}, o_{\mbox{\tiny +}}|s, a)$ of the next state of the world
and the next observation  given the current state  
and the current action.  It is given by

\[P(s_{\mbox{\tiny +}}, o_{\mbox{\tiny +}}|s, a)=
P(s_{\mbox{\tiny +}}|s, a)P(o_{\mbox{\tiny +}}|s_{\mbox{\tiny +}}, a,
s).\]


Knowledge about the initial state, if available,
is represented 
as a probability distribution $P_0$ over ${\cal S}$.
When the agent knows the initial state with certainty, $P_0$ is $1$ at 
the initial state and $0$ everywhere else.
The planning goal is encoded by a {\em reward function} such as the following:
\begin{eqnarray*}
r(s, a) = \left\{ 
			\begin{array}{ll}
			1 & \mbox{if $a{=}$\verb+declare-goal+ and
					   $s{=}$\verb+goal+,} \\
			0 & \mbox{otherwise.} 
			\end{array}
			\right .
\end{eqnarray*}
The preference for short plans is encoded by discounting future
rewards with respect to the current reward (see the next section).

In summary, a POMDP consists of a set   of possible states of the
world, a set   of possible observations, a set of  
possible actions, a observation probability, a transition probability, and
a reward function. An MDP has the same ingredients as    
an POMDP except that it has no observation probability. This is
because the state of the world is completely observed in an MDP.


\section{Basics of POMDPs}
\label{sec3}

This section reviews several concepts and results related to POMDPs.

\subsection{Belief States}
\label{sec2.2}


In a POMDP, an agent chooses and executes an action at each time point.
The choice is  made based on information from the past
(past observations and past actions) and the current observation. The 
amount of memory required to store
past observations and actions increases linearly with time.
This makes it difficult to maintain past information
after a long period of  time.

The standard way to overcome this difficulty
is to maintain, instead of past information,
the agent's {\em belief state} ---
the probability distribution 
$P(s_t|o_t, a_{t-1}, o_{t-1}, \ldots, a_1, o_1, P_0)$
of the current state $s_t$ of the world
given past information and the current observation.  
It is well known that the belief state is a {\em sufficient statistic} in
the sense that it captures all the information contained in past
information and the current observation that is useful 
for action selection. 
Hence the agent can base
its decision solely on the belief state.

Compared with maintaining past information, maintaining the belief state  is desirable
because the number of possible states of the world is 
 finite.  One needs only to maintain a fixed and finite number
of probability values\footnote{Storing these values exactly could
require unbounded precision.  Approximations are implicitly being made due
to the fact that machine precision is bounded.}.

The initial belief state is $P_0$.  One question is how the agent should
update its belief state as time goes by. 
Following Littman (1994), we use $b$ to denote a belief state.
For any state $s$, $b(s)$ is the probability that
the world is in state $s$.
The set of all possible belief states will be denoted by ${\cal B}$.

Suppose  $b$ is the current belief state, and 
$a$ is the current  action.  
If the observation $o_{\mbox{\tiny +}}$ is obtained at the next time point,
then the agent should update its belief state from $b$ to 
a new belief state $b_{\mbox{\tiny +}}$ given by
\begin{eqnarray}
\label{belief.rec}
b_{\mbox{\tiny +}}(s_{\mbox{\tiny +}}) = k
	\sum_{s} 
	P(s_{\mbox{\tiny +}},o_{\mbox{\tiny +}}|s, a)b(s),
\end{eqnarray}

\noindent where $k{=}1/\sum_{s, s_{\mbox{\tiny +}}} 
	P(s_{\mbox{\tiny +}},o_{\mbox{\tiny +}}|s, a)b(s)$
is the 
normalization constant (e.g., Littman, 1994).
%To signify the dependence of $b_{\mbox{\tiny +}}$
%upon $b$, $a$, and $o_{\mbox{\tiny +}}$, we shall sometimes write
%it as $b_{\mbox{\tiny +}}(.|b, a, o_{\mbox{\tiny +}})$.


\subsection{POMDPs as  MDPs}

For any belief state $b$ and any action $a$, define
\begin{eqnarray} 
\label{eq2.5}  
r(b, a)=\sum_{s}b(s)r(s, a).
\end{eqnarray}
 
\noindent It is the expected immediate reward for taking action $a$ in belief
state $b$.
 
 
For any belief state $b$, any action $a$, and any observation
$o_{\mbox{\tiny +}}$, define
\begin{eqnarray} 
\label{eq.btransition}   
P(o_{\mbox{\tiny +}}|b, a) = \sum_{s, s_{\mbox{\tiny +}}}
		P(s_{\mbox{\tiny +}}, o_{\mbox{\tiny +}}|s, a)b(s).
\end{eqnarray}
 
\noindent It is the probability of observing $o_{\mbox{\tiny +}}$ at the
next time point given that the current belief state is $b$ and the current action
is $a$. 
Let $b_{\mbox{\tiny +}}$ be the belief state given
by  equation (\ref{belief.rec}).
$P(o_{\mbox{\tiny +}}|b, a)$
 can also be understood as the probability of the next belief state
being $b_{\mbox{\tiny +}}$ given that the current action is
$a$ and the current belief state is $b$.
 
 
A POMDP over world state space ${\cal S}$ can be viewed as an MDP
over the belief state space ${\cal B}$. The 
the reward function and the transition probability of the 
MDP are given by Equations
(\ref{eq2.5}) and (\ref{eq.btransition}) respectively.


\subsection{Optimal Policies}
\label{sec2.3}

At each time point, the agent consults its belief state and chooses an action.
A {\em policy} $\pi$ 
 prescribes an action  for each possible belief
state. Formally it 
is a mapping from  ${\cal B}$ to  ${\cal A}$.
For each belief state $b$,
$\pi(b)$ is the action prescribed by $\pi$ for $b$.


Suppose $b_0$ is the current belief state.  
If an agent follows a policy $\pi$, then its current action is
$\pi(b_0)$ and the immediate reward is $r_0(b, \pi(b_0))$;
with probability $P(o_{\mbox{\tiny +}}|b_{0}, \pi(b_{0}))$, 
the agent's next belief state $b_1$ will be as 
given by Equation (\ref{belief.rec}),
the next action will be $\pi(b_1)$, and the next reward will be
$r_1(b_1, \pi(b_1))$; and so on and so forth.
The quality of a policy is measured by the expected discounted rewards it
garners. 
Formally the {\em value function} of a policy $\pi$ is defined for
each belief state $b_0$ to be the following expectation:
\begin{eqnarray}
\label{eq.vpi}
V^{\pi}(b_0)=E_{b_0}[\sum_{i=0}^{\infty}\gamma^ir_i(b_i, \pi(b_i))], 
\end{eqnarray}

\noindent where $0{\leq}\gamma{<}1$ is the {\em discount factor}.


A policy $\pi_1$  {\em dominates} another policy
$\pi_2$ if for each belief state $b{\in}{\cal B}$
\begin{eqnarray}
\label{eq.opt}
V^{\pi_1}(b) \geq V^{\pi_2}(b).
\end{eqnarray}

\noindent Domination is a partial ordering
among policies.  It is well known that there exists a 
policy  that dominates all other policies
(e.g., Puterman, 1990).  Such a policy
is called an {\em optimal policy}.
The value function of an optimal policy is called
the {\em optimal value function} and  is
denoted by $V^*$. 




\subsection{Value Iteration}
\label{sec2.4}

     

Value iteration is a standard way for solving infinite horizon  MDPs 
(Bellman, 1957).  
It begins with an arbitrary initial  function 
$V^*_0(b)$ and improves it iteratively by using the following equation
\begin{eqnarray}
\label{valueIteration}
V^*_t(b) = max_a [r(b, a) +
			\gamma\sum_{o_{\mbox{\tiny +}}}
			P(o_{\mbox{\tiny +}}|b, a)
			V^*_{t-1}(b_{\mbox{\tiny +}})],
\end{eqnarray}       
where $b_{\mbox{\tiny +}}$ is the belief state given
by equation (\ref{belief.rec}).
 If $V^*_0{=}0$, then
$V^*_t$ is  called the {\em $t$-step optimal value function}.
For any belief state $b$, $V^*_t(b)$ is the optimal expected
reward the agent can get in $t$ steps starting from $b$.


	   
The following theorem (Puterman, 1990, page 361)
 tells one when to terminate value iteration and how
to construct a ``good enough" policy.

\begin{theo} 
\label{theo.residual}
Let $\pi$ the policy given by
\begin{eqnarray}
\label{policy}
\pi(b) = arg \hspace{0.1cm}max_a [r(b, a) +
			\gamma\sum_{o_{\mbox{\tiny +}}}
			P(o_{\mbox{\tiny +}}|b, a)
			V^*_{t}(b_{\mbox{\tiny +}})]. 
\end{eqnarray} 
\noindent 
If
$max_{b{\in}{\cal B}} |V^*_t(b)-V^*_{t-1}(b)| \leq \epsilon$, 
then
\begin{eqnarray}
max_{b{\in}{\cal B}} |V^{\pi}(b)-V^*(b)| \leq 
		\frac{2{\epsilon}\gamma}{1-\gamma}.  \Box 
\end{eqnarray}
\end{theo} 

The quantity $max_{b{\in}{\cal B}} |V^*_t(b)-V^*_{t-1}(b)|$ is sometimes
called the {\em Bellman residual} and the
 policy $\pi$ is called the {\em greedy policy} based on
$V^*_{t}$.


Algorithms for POMDPs are classified into
{\em exact} or {\em approximation} algorithms depending on whether
they compute the  $t$-step optimal value function $V^*_t$ exactly
(Lovejoy, 1991a).
In the next two sections, we discuss the theoretical foundations of
exact algorithms  
and develop a new exact algorithm.
Thereafter, we propose a new approximation algorithm. 
			      
\section{Piecewise Linearity and Implicit Value Iteration}
\label{sec4}

Since  the belief space is continuous,
exact value iteration
cannot be carried out explicitly.  Fortunately, it can be carried out 
implicitly due to the piecewise linearity of the $t$-step
optimal value functions.  To 
explain piecewise linearity, we need the concept of 
policy trees. 


\subsection{Policy Trees}
\label{sec3.1}


\begin{figure}[t]
\begin{center}
\makebox{
	\epsfxsize=8cm
	\epsffile{ptree.ps}
}
\end{center}
\caption{A 3-step policy tree. }
\label{ptree}
\end{figure}



A {\em $t$-step policy tree} $p_t$ (Littman, 1994) prescribes 
an action for the current time point and an action  
for each possible information scenario $(o_1, \ldots,  o_i, a_0, \ldots, a_{i-1})$
at each of the next $t{-}1$ time points $i$.  
 Figure 
\ref{ptree} shows a 3-step policy tree.  
The tree reads as follows. \verb+Move-forward+ at the current time point.
 At the next time point,  if $o_1{=}0$ is observed then \verb+turn-left+.
Thereafter if $o_2{=}0$ is observed  then \verb+turn-left+ again; 
else if $o_2{=}1$ is observed then \verb+declare-goal+; else   
if $o_2{=}2$ is observed then \verb+move-forward+.
  And so on and so forth. To relate back to the introduction,
a $t$-step policy tree prescribes a way  the agent 
might  behave at the
current and the next $t{-}1$ time points.


When $t{>}1$, the subtree rooted at the $o_1$ node will be called a
{\em $o$-rooted $t{-}1$-step policy tree}, and will be
denoted by $\delta^{t-1}$.  It is a mapping from 
the set of possible observations ${\cal O}$
to the set of all possible $t{-}1$-step policy trees;  it prescribes
a $t{-}1$ step policy tree $\delta^{t-1}(o)$ for each possible
observation $o$.  In our example,  $\delta^2(o_1{=}0)$ is the $2$-step 
policy tree rooted at the uppermost $a_1$ node.


When $t{>}1$,  
a $t$-step policy tree $p_t$ has two components: an
action $a$ for the current time point and an $o$-rooted
$t{-}1$-step policy tree $\delta^{t-1}$ for the next $t{-}1$
time points.  
For this reason,
we shall sometimes write $p_t$ as a pair $(a, \delta^{t-1})$ and
call $a$ the {\em first action} of $p_t$.


By altering the actions on the edges out of the $a$-nodes,
one obtains different $t$-step policy trees.  The set of
all possible $t$-step policy trees will be denoted
by ${\cal P}_t$.  
A $1$-step policy tree is simply an action, and hence  ${\cal P}_1$ is 
the same as the set of possible actions ${\cal A}$.



\subsection{State Value Functions of  Policy Trees}
\label{sec3.2}

For any state $s$ and any $t$-step policy tree $p_t{=}(a, \delta^{t-1})$,                
recursively define

\begin{eqnarray}
\label{rec1}
V_{p_t}(s) = r(s, a) + \gamma \sum_{o_{\mbox{\tiny +}}}\sum_{s_{\mbox{\tiny +}}}
		V_{\delta^{t-1}(o_{\mbox{\tiny +}})}(s_{\mbox{\tiny +}})
		P(s_{\mbox{\tiny +}}, o_{\mbox{\tiny +}}|s, a),
\end{eqnarray}

\noindent where the second term is to be 
understood as $0$ when $t{=}1$.
It  is the expected discounted total reward the agent receives
at the current time and
during the next $t{-}1$ time points if the world is currently 
in state $s$ and
the agent behaves according to the policy tree $p_t$. 
We call $V_{p_t}$ 
the {\em state value function} of the $t$-step policy tree $p_t$.


Without mentioning the policy tree,
we shall sometimes call
$V_{p_t}$ a {\em $t$-step state value function}. 
The collection of all $t$-step state value functions
will be denoted by ${\cal V}_t$, i.e.
\[{\cal V}_t = \{V_{p_t}|p_t{\in}{\cal P}_t\}.\]
\noindent For convenience, we let ${\cal V}_0$ consist of one single
function of $s$ that is zero for all $s$.

\subsection{State Space Functions and Belief Space Functions}

It is worthwhile to point out that
a $t$-step state value function is a {\em state space function}, i.e.
a function over the state space ${\cal S}$, while
the $t$-step optimal value function is  a 
{\em belief space function}, i.e. a function over the belief space
${\cal B}$.
We  often use notations such as $\alpha$ or $\beta$ to refer
to state space functions.
A state space function $\alpha(s)$ {\em induces} a belief space function through
\[\alpha(b) = \sum_{s}\alpha(s)b(s).\]
\noindent 
Regarding $b$ as a vector with one component
$b(s)$ for each $s$, the induced belief space function is a {\em linear}  
combination of 
the components of $b$.  For convenience, we simply say that
$\alpha(b)$ is  {\em linear} in $b$.

A collection ${\cal V}$ of state space functions {\em induces} a belief space function
through
\begin{eqnarray}
\label{induced.bf}
{\cal V}(b) = max_{\alpha{\in}{\cal V}}\alpha(b).
\end{eqnarray}
\noindent 
Note that we are using ${\cal V}$ to denote both a set of 
state space functions and the belief space function it induces.
When ${\cal V}$ is empty, ${\cal V}(b)$ is  $0$ by definition.

The induced belief space function ${\cal V}(b)$ is {\em piecewise linear} in
$b$ in the sense that,
for each $\alpha{\in}{\cal V}$,  
it equals $\alpha(b)$  in  the region
$\{b|\alpha(b){\geq}\beta(b) \mbox{ for any other }  \beta{\in}{\cal V}\}$
of the belief space ${\cal B}$ and hence is linear in $b$ in that region.



\subsection{Piecewise Linearity of  Optimal Value Functions}

The following theorem 
was first proved by Sondik (1971).  It first appeared in its present 
form in Littman (1994).

\begin{theo} ({\bf Piecewise Linearity}) 
\label{theo.piece}
The $t$-step optimal value function $V^*_t$ is the
same as the belief space function induced by  the collection of
all $t$-step state value functions ${\cal V}_t$, i.e. for 
any belief state $b$
\[V^*_t(b)={\cal V}_t(b).  \Box \]
\end{theo}
The theorem is true for  the following reasons.
$V^*_t(b)$ is the reward the agent receives if  it behaves optimally and
for any policy tree $p_t$, $V_{p_t}(b)$ is the reward the agent
gets if it behaves according to $p_t$. Because one of the policy trees
must be optimal, $V^*_t(b)=max_{p_t}V_{p_t}(b){=}{\cal V}_t(b)$.
Due to this theorem, we  say that the collection  
${\cal V}_t$ of 
state value functions is
 {\em representation} of $V^*_t$.





\subsection{Parsimonious Representations}



The size of ${\cal V}_t$ increases
exponentially with $t$.  As a matter of fact, 
 the total number of $t$-step policy trees 
 (Cassandra,  1994) is:

\[|{\cal P}_t|=|{\cal A}|^{\frac{|{\cal O}|^t-{1}}{|{\cal O}|-{1}}}.\]

\noindent There are potentially the same number of 
$t$-step state value functions.  
Fortunately, many of the state value functions  
 can be pruned without affecting the induced
belief space function. 
Let us make this property more explicit.


Let ${\cal W}$ and ${\cal X}$ be two sets of  state space functions.
We say that ${\cal W}$ {\em covers} ${\cal X}$ 
if  it induces
the same belief space function as ${\cal X}$ does, i.e. if

\[{\cal W}(b)={\cal X}(b)\]
for any belief state $b$.
We say that ${\cal W}$ {\em parsimoniously covers} ${\cal X}$ if
${\cal W}$ covers ${\cal X}$ and none of its proper subsets do.
When ${\cal W}$ covers or parsimoniously covers ${\cal X}$,
we refer to ${\cal W}$ as a {\em covering} or a
{\em parsimonious covering} of ${\cal X}$.





\begin{theo}
\label{uniqueness}
All parsimonious coverings of a set of state space functions
consist of the same number of state space functions.
$\Box$
\end{theo}
The theorem has been known for sometime (e.g., Littman, 1994).
Due to this theorem, one can also define 
a parsimonious covering as a covering that contains
the minimum number of state space functions.

A parsimonious covering $\hat{\cal V}_t$ of ${\cal V}_t$
is also a  representation
of $V^*_t$ in the sense that  $\hat{\cal V}_t(b)=V^*_t(b)$ for
any belief state $b$.  This representation is parsimonious because
it consists of the fewest number of state space 
functions among all the representations of $V^*_t$.

 

\subsection{Dynamic-Programming Updates}
\label{sec.updating}

The question now is how to obtain a parsimonious covering
of ${\cal V}_t$.
As will be shown in the next section,
it is possible to obtain a parsimonious covering
of ${\cal V}_t$ by starting from a parsimonious covering of
${\cal V}_{t-1}$.
The process
of computing a parsimonious covering of ${\cal V}_t$ from
a parsimonious covering  of ${\cal V}_{t-1}$ is called
{\em dynamic-programming updates} (Littman {\em et al}., 1995).
It is a key step in algorithms that solve POMDPs via value iteration. 




Previous  algorithms for dynamic-programming updates  include
the enumeration and pruning
algorithms by Monahan (1992), Eagle (1984), and
Lark (White, 1991), 
the one-pass algorithm by Sondik (1971), the linear support 
and relaxed region algorithms
by Cheng (1988), and the witness algorithm by Cassandra {\em et al}.
 (1994) and Littman (1994).  The witness algorithm has been 
empirically proved to
be the most efficient among all those algorithms (Littman {\em et al}., 1995).

\subsection{Implicit Value Iteration}

The  procedure \verb+solvePOMDP+ shown in Figure
\ref{solvepomdp} carries out value iteration implicitly:
instead inductively computing the $t$-step optimal value function
$V^*_t$ itself, it computes
 a parsimonious covering of ${\cal V}_t$ --- a set of
state space functions that represents $V^*_t$.
In the procedure, the subroutine \verb+update+$(\hat{\cal V}_{t-1})$
  takes a parsimonious covering $\hat{\cal V}_{t-1}$ 
of ${\cal V}_{t-1}$ and returns a parsimonious covering
$\hat{\cal V}_t$ of
${\cal V}_t$.  It can be implemented
using any of the  algorithms mentioned in the previous subsection.  
The subroutine \verb+stop+$(\hat{\cal V}_{t}, \hat{\cal V}_{t-1}, \epsilon)$ 
 determines whether the Bellman residual has
fallen below the threshold $\epsilon$ from the
parsimonious coverings $\hat{\cal V}_{t-1}$ and  $\hat{\cal V}_{t}$
of ${\cal V}_{t-1}$ and ${\cal V}_t$. 
 See Littman (1994) for an implementation of this subroutine.

   

\begin{figure}
\begin{quote}
\begin{quote}
\begin{quote}
\begin{quote}
------------------------------------------------------------------
\\

  Procedure \verb+solvePOMDP+$({\cal M},\epsilon)$:
	 \begin{itemize}
       \item Input: ${\cal M}$ --- A  POMDP, \\
		\verb+      + $\epsilon$ --- A positive number.
       \item  Output:  A set of state space functions.
	\end{itemize}

	\begin{enumerate}
	\item  $t \leftarrow 0$,  $\hat{\cal V}_0 \leftarrow \{0\}$.

	\item {\bf Do}
		\begin{itemize}
		\item $t{=}t{+}1$.
		\item 
			\(\hat{\cal V}_t \leftarrow 
		\verb+update+(\hat{\cal V}_{t-1}).\)

		\end{itemize}


		{\bf while}
		\verb+stop+$(\hat{\cal V}_{t}, \hat{\cal V}_{t-1},
				\epsilon)$
				= \verb+no+.

	\item Return $\hat{\cal V}_{t}$.
	\end{enumerate}
\ \\
------------------------------------------------------------------
\end{quote}
\end{quote}
\end{quote}
\end{quote}
\caption{Implicit value iteration.}
\label{solvepomdp}
\end{figure}

Procedure \verb+solvePOMDP+ terminates when the
Bellam residual falls below the threshold $\epsilon$ and
return a set  of state space functions.
The set $\hat{\cal V}_t$ of state space functions returned
represents the $t$-step optimal value function $V^*_t$.  
It is the solution to the input POMDP.  
The planning agent keeps $\hat{\cal V}_t$ in its memory.
 When it needs to make a decision, the agent consults
its belief state $b$ and chooses an action using 
 (\ref{policy}) with $V^*_t(b_{\mbox{\tiny +}})$ replaced
by $\hat{\cal V}_t(b_{\mbox{\tiny +}})$.  

\section{A New Algorithm for Dynamic-Programming Updates}
\label{sec.incr}


This section proposes a new algorithm
for dynamic-programming updates.
There are four subsections. In the first three subsections,
we show that a parsimonious covering of ${\cal V}_t$ can
be obtained by starting from a parsimonious covering of ${\cal V}_{t-1}$ and,
while doing so, introduce  concepts and results
that are necessary for the development of the new algorithm.

\subsection{Relationship Between ${\cal V}_{t-1}$ and ${\cal V}_t$}

Suppose  ${\cal W}$ and
${\cal X}$ are two sets of state space functions.
The {\em cross sum} ${\cal W}{\bigoplus}{\cal X}$ of ${\cal W}$
and ${\cal X}$ is
the following set of state space functions:
\[{\cal W}{\bigoplus}{\cal X}=\{\alpha{+}\beta|\alpha{\in}{\cal W},
\beta{\in}{\cal X}\}.\]
It is evident that the cross sum  operation is commutative and
associative.
Consequently, we can talk about the cross sum $\bigoplus_{i=0}^N{\cal W}_i$
of a list of sets ${\cal W}_0$, \ldots, ${\cal W}_N$ of
state space functions.

For any action $a$ and any observation $o_{\mbox{\tiny +}}$,
define
\begin{eqnarray}
\label{qao+}
{\cal Q}_{a, o_{\mbox{\tiny +}}}
  &=& \{\gamma\sum_{s_{\mbox{\tiny +}}}\alpha(s_{\mbox{\tiny +}})
	P(s_{\mbox{\tiny +}}, o_{\mbox{\tiny +}}|s, a) |
	\alpha{\in} {\cal V}_{t-1}\}.
\end{eqnarray}
Note that since
$a$ and  $o_{\mbox{\tiny +}}$ are given,  each member
$\gamma\sum_{s_{\mbox{\tiny +}}}\alpha(s_{\mbox{\tiny +}})
	P(s_{\mbox{\tiny +}}, o_{\mbox{\tiny +}}|s, a)$
of the above set  is a function of $s$, in other words, a
 state space function.
 Hence ${\cal Q}_{a, o_{\mbox{\tiny +}}}$ is a set of
 state space functions.
Let $0$, $1$, \ldots, $N$ be an enumeration of all possible values of
$o_{\mbox{\tiny +}}$. We use ${\bigoplus}_{o_{\mbox{\tiny +}}}
{\cal Q}_{a, o_{\mbox{\tiny +}}}$ to denote the cross sum
$\bigoplus_{i=0}^N{\cal Q}_{a, i}$.
 

\begin{pro}
\label{pro.vtvt-1}
\( {\cal V}_t  =\cup_a[\{r(s,a)\}{\bigoplus}({\bigoplus}_{o_{\mbox{\tiny +}}}
{\cal Q}_{a, o_{\mbox{\tiny +}}})]. \) 
\end{pro}

\noindent
{\bf Proof}:
By the definition of the set ${\cal V}_t$ and Equation (\ref{rec1}),
a state space function $\alpha$ is in ${\cal V}_t$ if and only if
there exist action $a$ and  $\beta_{o_{\mbox{\tiny +}}} \in
{\cal V}_{t-1}$ for each ${o_{\mbox{\tiny +}}} \in {\cal O}$ such that

\[\alpha(s) = r(s, a) +  \sum_{o_{\mbox{\tiny +}}} \gamma \sum_{s_{\mbox{\tiny +}}}
		\beta_{o_{\mbox{\tiny +}}}(s_{\mbox{\tiny +}})
		P(s_{\mbox{\tiny +}}, o_{\mbox{\tiny +}}|s, a). \]
The proposition follows. $\Box$


\subsection{Properties of Coverings}


\begin{lem}
\label{transitive1}
Suppose ${\cal W}$, ${\cal X}$, and ${\cal Y}$ are  
three sets of state space functions.
  If ${\cal W}$ 
parsimoniously covers
 ${\cal X}$ and ${\cal X}$ covers
${\cal Y}$, then ${\cal W}$  parsimoniously
 covers
of ${\cal Y}$.  $\Box$
\end{lem}


%Hence one can talk about the cross sum of
%more than two sets of state space functions.
\begin{lem}
\label{incremental1}
Let ${\cal W}$, ${\cal W}'$, ${\cal X}$, and ${\cal X}'$
be four sets of state space functions.
If ${\cal W}'$ covers ${\cal W}$ and  ${\cal X}'$ 
covers  ${\cal X}$, then
\begin{enumerate}
\item ${\cal W}'{\bigoplus}{\cal X}'$ covers
${\cal W}{\bigoplus}{\cal X}$.

\item ${\cal W}'{\cup}{\cal X}'$
covers
${\cal W}{\cup}{\cal X}$.$\Box$
\end{enumerate}
\end{lem}



\subsection{Coverings of ${\cal V}_t$ from
Parsimonious  Coverings of ${\cal V}_{t-1}$}


Let $\hat{\cal V}_{t-1}$ be a parsimonious covering
 of ${\cal V}_{t-1}$.
For any action $a$ and any observation $o_{\mbox{\tiny +}}$,
define 
\begin{eqnarray*}
\label{qao.hat}
{\cal Q}'_{a, o_{\mbox{\tiny +}}} 
  &=& \{\gamma\sum_{s_{\mbox{\tiny +}}}\alpha(s_{\mbox{\tiny +}})
	P(s_{\mbox{\tiny +}}, o_{\mbox{\tiny +}}|s, a) | 
	\alpha{\in} \hat{\cal V}_{t-1}\}.
\end{eqnarray*}        
Note that the definition of
${\cal Q}'_{a, o_{\mbox{\tiny +}}}$ is the same as
that of ${\cal Q}_{a, o_{\mbox{\tiny +}}}$ except that 
${\cal V}_{t-1}$ is replaced by $\hat{\cal V}_{t-1}$.
Also define
\[ {\cal V}'_t  =\cup_a[\{r(s,a)\}{\bigoplus}({\bigoplus}_{o_{\mbox{\tiny +}}}
{\cal Q}'_{a, o_{\mbox{\tiny +}}} )].\]

\begin{pro}
\label{theo.incr}
The set ${\cal V}'_t$ covers  ${\cal V}_t$.
\end{pro}

Formal proof of this proposition  is given in 
Appendix A. 
Informally, the fact that 
 $\hat{\cal V}_{t-1}$ covers ${\cal V}_{t-1}$ implies that
  ${\cal Q}'_{a, o_{\mbox{\tiny +}}}$
covers  ${\cal Q}_{a, o_{\mbox{\tiny +}}}$, which 
in turn implies that 
${\cal V}'_t$ covers  ${\cal V}_t$ due to 
 Proposition \ref{pro.vtvt-1} and
 Lemma \ref{incremental1}.





According to Proposition \ref{theo.incr} and   Lemma \ref{transitive1},
  one can obtain a parsimonious covering of ${\cal V}_t$
by finding a parsimonious
covering of ${\cal V}'_t$ and ${\cal V}'_t$ is defined in terms of 
a parsimonious covering $\hat{\cal V}_{t-1}$
of ${\cal V}_{t-1}$. 
This is why we said that a parsimonious covering of ${\cal V}_t$
can be obtained by starting from a parsimonious covering
of ${\cal V}_{t-1}$.

  

 Monahan's exhaustive method finds a parsimonious covering
of ${\cal V}'_t$ by
 enumerating all the state space functions  in ${\cal V}'_t$
one by one and  detecting
those that  can be pruned by solving linear programs.
 Lark's algorithm  works
in a similar fashion except that its linear programs have fewer constraints.
Since ${\cal V}'_t$ 
consists of $|{\cal A}||\hat{\cal V}_{t-1}|^{|{\cal O}|}$ state space functions,
enumerating them one by one  is very expensive.
Other algorithms  (Sondik, 1971; Cheng, 1988; Littman, 1994)
avoid this difficulty by exploiting the structures of ${\cal V}'_t$.




\subsection{A New Algorithm for Dynamic-Programming Updates}
\label{sec.new}

 Let \verb+purge+$({\cal W})$ be a subroutine that takes a set ${\cal W}$ of
state space functions and returns a parsimonious covering of ${\cal W}$.
An implementation of \verb+purge+ can be found in the appendix.

Let  ${\cal W}_0$, \ldots, ${\cal W}_N$ be 
sets of state space functions.
Consider the  procedure \verb+incrPruning+ shown in Figure \ref{ip}. 
Let $n$ be a  number between $0$ and $N$.
Using  Lemmas \ref{transitive1} and
\ref{incremental1},
one can easily show by induction
that, at the end of the $n$th pass through the for-loop,
the set ${\cal W}$
 is a parsimonious covering of
$\bigoplus_{i=0}^n{\cal W}_{i}$.
Consequently, the procedures returns a parsimonious covering of
$\bigoplus_{i=0}^N{\cal W}_{i}$.
The procedure is named {\em incremental pruning} because pruning
takes place after each cross sum.


 

Let $0$, $1$, \ldots, $N$ be an enumeration
of all the possible observations, i.e. possible instantiations of 
$o_{\mbox{\tiny +}}$.
For any action $a$,
suppose the sets
${\cal Q}'_{a, 0}$, ${\cal Q}'_{a, 1}$,
\ldots, and   ${\cal Q}'_{a, N}$ have been computed.
Applying \verb+incrPruning+ to those sets, we  get
a parsimonious covering of  
$\bigoplus_{i=0}^N{\cal Q}'_{a, i}$.
Denote it by ${\cal W}_a$.
According to Lemma \ref{incremental1}, 
$\cup_a[\{r(s,a)\}{\bigoplus}{\cal W}_{a}]$ covers ${\cal V}'_t$. 
Due to  Lemma \ref{transitive1}, this fact implies that
a parsimonious covering of $\cup_a[\{r(s,a)\}{\bigoplus}{\cal W}_{a}]$
is also a parsimonious covering of
${\cal V}'_t$ and hence of  ${\cal V}_t$.
Thus, a parsimonious covering of ${\cal V}_t$ can be found from
a parsimonious covering of ${\cal V}_{t-1}$ using the procedure
\verb+update+ shown in Figure \ref{ip}.

\begin{figure}
\begin{quote}
\begin{quote}
\begin{quote}
---------------------------------------------------------------------
\\

Procedure \verb+incrPruning+$(\{{\cal W}_{0},{\cal W}_{1}, 
	\ldots,  {\cal W}_{N}\})$:
  \begin{enumerate}
\item ${\cal W}{\leftarrow}{\cal W}_{0}$.
\item {\bf For} $i=1$ to $N$,

	\[{\cal W} \leftarrow
		\verb+purge+({\cal W}{\bigoplus}{\cal W}_{i}).\]


\item Return ${\cal W}$.
\end{enumerate}
\end{quote}\end{quote}\end{quote}
\begin{quote}
\begin{quote}
\begin{quote}

	Procedure \verb+update+$(\hat{\cal V}_{t-1})$: 
	\begin{itemize}
	\item Input: $\hat{\cal V}_{t-1}$ --- a parsimonious covering of ${\cal V}_{t-1}$.
	\item Input: a parsimonious covering of ${\cal V}_{t}$. 
	 \end{itemize}

	\begin{enumerate}
	\item {\bf For} each $a{\in}{\cal A}$,
		\begin{enumerate}
		\item Compute the sets 
			${\cal Q}'_{a, 0}$, ${\cal Q}'_{a, 1}$,
\ldots, and   ${\cal Q}'_{a, N}$.
	\item ${\cal W}_a \leftarrow 
		\verb+incrPruning+(\{ 
{\cal Q}'_{a, 0},{\cal Q}'_{a, 1}, \ldots,  {\cal Q}'_{a, N}\})$. 
	
		\end{enumerate}

	\item Return $\verb+purge+(\cup_a[\{r(s,a)\}{\bigoplus}{\cal W}_{a}])$. 
	\end{enumerate}

---------------------------------------------------------------------

\end{quote}
\end{quote}
\end{quote}

\caption{Incremental pruning and  dynamic-programming updates.}
\label{ip}
\end{figure}


We also use the  term {\em incremental pruning} to refer to the above
algorithm for dynamic-programming updates.
It has been shown elsewhere (Cassandra {\em et al}., 1977) 
that incremental pruning has the same 
asymptotic complexity as the witness algorithm 
and empirically it  significantly 
outperforms the latter.



	
\section{Region-Based Model Approximation}
\label{sec5}


We have so far been  concerned with   exact algorithms.
Experiments with incremental pruning,
presently the most efficient exact algorithm, have revealed
that it can solve only small POMDPs (Cassandra {\em et al}., 1997).
One needs to resort to approximation  
in order to solve large real-world problems.


Most previous approximation methods solve a POMDP directly; they
approximate the $t$-step optimal value function of the POMDP.
In the rest of this paper, we develop a new 
method that  approximates a POMDP itself by another
that has a more informative observation model and
is hence easier to solve.
The latter POMDP is solved and its solution is used to
construct a solution to the original POMDP.





\subsection{The Basic Idea}

We make the following assumption about problem characteristics.
in a POMDP ${\cal M}$, even though an  agent  does not know the  true
state of the world,  it   often 
has a good idea about the state.  Justifications for this assumption 
were given in the introduction and empirical evidence is presented by 
Simmons \& Koenig (1995).

Consider another POMDP ${\cal M}'$ that is the same as
${\cal M}$ except that in addition to the observation made by
itself, the agent
 also receives a report from 
an oracle who knows the true state of the world.
The oracle does not report the true state itself. Instead 
it selects, from a predetermined list of candidate regions, a
region that contains the true state and
reports that region.

					     

More information is available to the agent in 
${\cal M}'$ than in ${\cal M}$; additional information is provided by the 
oracle.  
Since  in ${\cal M}$ the agent already has
a good idea about the true state of the world,  
the oracle might not provide much
additional information even when the candidate
regions are small.  Consequently, 
${\cal M}'$ could be  a good approximation
of ${\cal M}$.  

In ${\cal M}'$, the agent knows for sure that the true state of
the world is in the region reported by the oracle.   
For this reason, we say  that it
is {\em region observable}.  
The region observable POMDP     ${\cal M}'$ can be much easier to solve than
${\cal M}$ when the candidate regions are small.
For example, if the oracle is allowed to report only singleton regions,
then it actually reports the true state of the world and
hence  ${\cal M}'$ is
an MDP.  MDPs are much easier to solve than POMDPs. 
One would expect the region observable POMDP ${\cal M}'$ to be solvable
when the candidate regions are small.


\subsection{Spectrum of Approximations}

If the  region reported by the oracle is always the set of
all possible states, then no additional information is provided,  because
the report that 
the true state of the world is one of the possible states
has no information content.
In this case, ${\cal M}'$  
has the same solution as
${\cal M}$ and solving ${\cal M}'$ is equivalent to
solving ${\cal M}$ directly.
This is one extreme of the spectrum.


 At the other extreme, if all the candidate regions are singletons, 
the oracle reports the true state of the world.
Maximum amount of additional information is provided and
${\cal M}'$ is actually an MDP. The MDP
might not be a good approximation  of ${\cal M}$ but it is 
much easier to solve than  ${\cal M}$.


Previous methods for solving a POMDP  either solve it directly or 
to approximate it by using a MDP.  
By allowing the oracle to report regions that are neither
singletons nor the set of all possible states, this paper opens up the possibility of
exploring the spectrum between those two extremes.
One way to explore the spectrum is to start with singleton candidate                                 
regions and increase their sizes gradually. Approximation quality
and computational time both increase as one goes along.  
One stops when the approximation is accurate enough or the
region observable POMDP becomes intractable. A method
for determining approximation quality will be described later.
				 \ \\

We now set out to make these ideas more concrete by starting with
the concept of region systems.

\subsection{Region Systems}



A {\em region} is simply 
a subset of states of the world.
A {\em region system} is a collection of regions such that
no region is a subset of another region in the  collection
and the union of all regions equals the set of all possible states
of the world.  
We use
$R$ to denote a region and ${\cal R}$ to denote a region
system.

Region systems are  used to restrict the regions that
the oracle can choose to report. 
The choice of a region system
 determines the computational complexity of the region observable
POMDP ${\cal M}'$ 
and approximation quality.
How to choose regions so as to make proper tradeoff
between computational time and approximation quality 
is an open research issue. Here is a preliminary
 approach.  
The idea   is to create 
a region for each state  by including its ``nearby" states.
  We say
a state $s'$ is {\em ideally reachable in one step} from another
state $s$ if
after executing a certain action in state $s$,
 the probability of the world ending up in  state $s'$       is the highest.     
A state $s_k$ is {\em ideally reachable in $k$ steps} from another state
$s_0$ if there are state $s_1$, \ldots, $s_{k-1}$ such that
$s_{i+1}$ is ideally reachable from $s_i$ in one step for all $0{\leq}i{\leq}k{-}1$.
Any state is ideally reachable from itself in 0 step.

For any non-negative integer $k$,
the {\em radius-$k$ region centered at a state  $s$} is the set of states
that are ideally reachable from $s$ in $k$ or less steps.  
A {\em radius-$k$ region system} is the one obtained by creating a
radius-$k$ region for each state and then removing, one after another, regions that
are subsets of others.

When $k$ is 0, the radius-$k$ region system consists of singleton regions.
On the other hand, if  each state is
reachable from any other state in $k$ or less steps, there is only one region
in the radius-$k$ region system --- the set of all possible states.



\subsection{Region Observable POMDPs}

Given a region system ${\cal R}$ and 
a POMDP ${\cal M}$,  we construct a region observable POMDP
${\cal M}'$  by assuming that
at each time point the agent not only obtains an observation by itself
but also receives a report from 
an oracle who knows the true state of the world.
The oracle does not report the true state itself. Instead 
it chooses from ${\cal R}$ one region  that contains the true state
and reports that region. 

The amount of additional information provided by the oracle
depends not only on the
region system used but also on the way the oracle chooses
regions.
For example,  if the oracle always reports the region centered
at the true state, then it implicitly reports the true state itself.


In order to provide as little additional information as possible, the oracle
should consider what the agent already knows.  
However, it cannot take the entire history of past
actions and observations into account because
if it did, ${\cal M}'$ would not be a POMDP.
The current observation would depend on the entire history.
%The best he can do is to estimate what the agent knows based
%on the current observation and the previous true state of the
%world.


For any non-negative state space function $f(s)$  and any region $R$,
we call the quantity $supp(f, R)$${=}$
$\sum_{s{\in}R}f(s)/\sum_{s{\in}{\cal S}}f(s)$ the
{\em degree of support} of $f$ by  $R$.
Note that when $f$ is a probability distribution, the denominator
is 1.
If $R$  supports $f$ to degree 1,
we say that
$R$ {\em fully supports} $f$.

We suggest the following region-selection rule for the oracle.
Let $s_{\mbox{\tiny -}}$
be the previous true state of the world, $a_{\mbox{\tiny -}}$ be the
previous action, and $o$ be the current observation.  
The oracle should choose, 
among all the regions  in ${\cal R}$ that contain the true state
of the world,
one
that supports the function $P(s, o|s_{\mbox{\tiny -}}, a_{\mbox{\tiny -}})$
of $s$ to the maximum degree.  Where there is more than one such regions, 
choose the one that comes first in a predetermined ordering
among the regions.


Here are some arguments in support of the rule.
If the previous world state
 $s_{\mbox{\tiny -}}$ were known to the agent, then its current
belief state $b(s)$, a function of s,  would be proportional to 
$P(s, o|s_{\mbox{\tiny -}}, a_{\mbox{\tiny -}})$.
In this case, the rule minimizes additional information in the sense that
the region reported  supports the current belief state to the maximum degree.  
If the previous world state is known to be around $s_{\mbox{\tiny -}}$,
the same is roughly true.
Also if the current observation is informative enough, 
being a landmark for instance, to ensure that
the world state is in a certain region, then the region chosen 
using the 
rule fully supports the current belief state.  In such a case, no
additional information is provided.
Despite those arguments,
we do not claim that the rule described above is optimal.  
Finding a rule that minimizes additional information is still an open
problem.


The probability $P(R|s, o, s_{\mbox{\tiny -}}, a_{\mbox{\tiny -}})$
 of a region $R$ being chosen under the above scheme is given by 
\begin{eqnarray*}
P(R|s, o, s_{\mbox{\tiny -}}, a_{\mbox{\tiny -}})
 = \left\{  \begin{array}{ll}
	1 & \mbox{ if $R$ is the first region s.t.
		 $s{\in}R$ and  for
		any other region $R'$} \\
	  & \mbox{$\sum_{s'{\in}R}P(s', o|s_{\mbox{\tiny -}}, 
	  a_{\mbox{\tiny -}}){\geq}\sum_{s'{\in}R'}P(s', o|s_{\mbox{\tiny -}}, a_{\mbox{\tiny -}})$} \\
	0 & \mbox{ otherwise. }
	\end{array}
\right .
\end{eqnarray*}




The region observable POMDP ${\cal M}'$ 
differs from the original POMDP ${\cal M}$ only in
terms of observation; in addition to the observation 
$o$ made by itself,
the agent also receives a report $R$ from the oracle.
We shall denote an observation in ${\cal M}'$ by
$z$ and write 
$z{=}(o, R)$.  
The observation model of ${\cal M}'$ is given by
\[P(z|s, a_{\mbox{\tiny -}}, s_{\mbox{\tiny -}}) = 
P(o, R|s, a_{\mbox{\tiny -}}, s_{\mbox{\tiny -}}) = 
P(o|s, a_{\mbox{\tiny -}})
P(R|s, o, s_{\mbox{\tiny -}}, a_{\mbox{\tiny -}}). \]
The joint conditional probability
$P(s_{\mbox{\tiny +}}, z_{\mbox{\tiny +}}|s, a)$ of the 
next state $s_{\mbox{\tiny +}}$ of the world
and the next observation $z_{\mbox{\tiny +}}$
  given the current state $s$ 
and the current action $a$ is 

\[P(s_{\mbox{\tiny +}}, z_{\mbox{\tiny +}}|s, a)=
P(s_{\mbox{\tiny +}}|s, a)P(z_{\mbox{\tiny +}}|s_{\mbox{\tiny +}}, a,
s).\]



\section{Solving Region Observable POMDPs}
\label{sec6}

In principle, the  region observable POMDP ${\cal M}'$ can be solved 
in the same way as general POMDPs  using 
the procedure \verb+solvePOMDP+.
  It is not advisable to do so, however, since 
\verb+solvePOMDP+
 does not automatically exploit region observability.
This  section and the next two sections
develop an algorithm  for solving ${\cal M}'$ that  takes advantage of region 
observability.



\subsection{Restricted Value Iteration}

For any region $R$, let ${\cal B}_R$ be the set of belief
states that are fully supported by $R$.
Let ${\cal R}$ be the region system underlying
the region observable POMDP ${\cal M}'$.
Define ${\cal B}_{\cal R}
=\cup_{R \in {\cal R}}{\cal B}_R$.





It is easy to see that, in ${\cal M}'$,
 no matter what the current belief state $b$ is, the
next belief state $b_{\mbox{\tiny +}}$ must be in  ${\cal B}_{\cal R}$.
We assume that  the initial belief state is  in 
${\cal B}_{\cal R}$.  Then all possible belief states the agent might 
encounter are in  ${\cal B}_{\cal R}$.  This implies 
that  policies for ${\cal M}'$  need only be defined
over ${\cal B}_{\cal R}$ and value iteration for ${\cal M}'$
can be restricted to the subset  ${\cal B}_{\cal R}$ of  ${\cal B}$.    

We  restrict value iteration for ${\cal M}'$ to
${\cal B}_{\cal R}$ for the sake of efficiency.
Doing so implies that 
the $t$-step optimal value function of ${\cal M}'$, denoted by
$U^*_t$, 
is defined only over ${\cal B}_{\cal R}$ and the Bellman residual  is now
$max_{b \in {\cal B}_{\cal R}}|U^{*}_t(b)-U^{*}_{t-1}(b)|$.
To avoid confusion, we  call it the {\em restricted
Bellman residual} and call $U^*_t$ the {\em restricted $t$-step optimal
value function}.


Since ${\cal B}_{\cal R}$ is continuous,
 restricted value iteration cannot be 
carried out implicitly.  The next subsection
shows how it can be carried implicitly.


 
\subsection{Implicit Restricted Value Iteration}

Let ${\cal W}$ and ${\cal X}$ be two sets of state space functions
and let $R$ be a region.
We say that ${\cal W}$   {\em covers
 ${\cal X}$ in region $R$}
if, for any $b{\in}{\cal B}_R$,  
\begin{eqnarray*}
\label{eq.regional}
{\cal W}(b)= {\cal X}(b).
 \end{eqnarray*}
We say that ${\cal W}$   {\em parsimoniously covers
 ${\cal X}$ in region $R$} if ${\cal W}$ covers ${\cal X}$ in
region $R$ and none of its proper subsets do.
When ${\cal W}$ covers or parsimoniously covers ${\cal X}$ in
a region, we refer to ${\cal W}$ as a {\em regional covering}
or a {\em parsimonious regional covering} of ${\cal X}$.


Let ${\cal U}_t$ be the set of all $t$-step state value functions
of ${\cal M}'$.  According to Theorem \ref{theo.piece}, 
	\[U^*_t(b) = {\cal U}_t(b)\]
for any belief state $b{\in}{\cal B}_{\cal R}$.  

For  each region $R$, suppose $\hat{\cal U}_{t, R}$
is a set of state space functions
 that
parsimoniously covers   ${\cal U}_t$ in region $R$.
Then the collection   $\{\hat{\cal U}_{t, R}|R{\in}{\cal R}\}$
is a {\em representation} of $U^*_t$ in the sense
that for any $b{\in}{\cal B}_{\cal R}$, 
\begin{eqnarray}
\label{local.rep}
U^*_t(b)=\hat{\cal U}_{t, R_b}(b),
\end{eqnarray}
where $R_b$ is such that $b{\in}{\cal B}_R$, i.e.
such that $R_b$  fully supports $b$.


As will be shown in the next section, parsimonious regional
coverings of ${\cal U}_t$ can be obtained from
parsimonious regional coverings of ${\cal U}_{t-1}$.
Let \verb+ROPOMDPupdate+$(R, \hat{\cal U}_{t-1, R_{\mbox{\tiny +}}}
|R_{\mbox{\tiny +}}{\in}{\cal R}\})$ 
be a procedure that takes a region $R$ and parsimonious regional covering
$\{\hat{\cal U}_{t-1, R_{\mbox{\tiny +}}}|
R_{\mbox{\tiny +}}{\in}{\cal R}\}$ of ${\cal U}_{t-1}$ and returns
a set of state space functions that parsimoniously
covers ${\cal U}_t$ in region $R$ \footnote{The string
``ROPOMDP"  in
\verb+ROPOMDPupdate+ stands for region-observable POMDP.}.
Let \verb+ROPOMDPstop+ be a procedure that determines, 
from parsimonious regional coverings of ${\cal U}_{t-1}$ and 
  ${\cal U}_t$, whether the
restricted Bellman residual has fallen below a predetermined
threshold.  


The  procedure \verb+solveROPOMDP+ shown in Figure
\ref{solveROPOMDP} carries out restricted value iteration implicitly:
instead inductively computing the restricted $t$-step optimal value function
$U^*_t$ itself, it computes
 parsimonious regional coverings of ${\cal U}_t$.
In other words, it computes  sets of
state space functions that represent $U^*_t$ in the
sense of (\ref{local.rep}).

\begin{figure}
 \begin{quote}
 \begin{quote}
---------------------------------------------------------------------------------
\\

  Procedure \verb+solveROPOMDP+$({\cal M}',\epsilon)$
	\begin{itemize}
       \item Input: ${\cal M}'$ --- A region observable POMDP, \\
		\verb+      + $\epsilon$ --- A positive number.
       \item  Output:  A list of sets of state space functions.
	\end{itemize}

	\begin{enumerate}
	\item $t{\leftarrow}0$.
	\item 
  {\bf For} $R{\in}{\cal R}$,  
		 $\hat{\cal U}_{0, R} \leftarrow \{0\}$.
		
	\item {\bf Do}
		\begin{itemize}
		\item $t \leftarrow t{+}1$.                
		\item {\bf For} each $R{\in}{\cal R}$,
			\[\hat{\cal U}_{t, R}  \leftarrow 
		\verb+ROPOMDPupdate+(R, \{\hat{\cal U}_{t-1, R_{\mbox{\tiny +}}}
			|R_{\mbox{\tiny +}}{\in}{\cal R}\}).\]
		\end{itemize}


		{\bf while}
		\verb+ROPOMDPstop+$(\{\hat{\cal U}_{t, R} |R{\in}{\cal R}\}, 
				\{\hat{\cal U}_{t-1, R_{\mbox{\tiny +}}}|
				R_{\mbox{\tiny +}}{\in}{\cal R}\}, 
				\epsilon)$ 
				= \verb+no+.

	\item Return $\{\hat{\cal U}_{t, R} |R{\in}{\cal R}\}$.
	\end{enumerate}

---------------------------------------------------------------------------------

\end{quote}\end{quote}
\caption{Implicit restricted value iteration for region-observable POMDPs.}
\label{solveROPOMDP}
\end{figure}

Let $\pi'$  be the greedy policy for ${\cal M}'$  based on ${U}^{*}_t$.
For any $b{\in}{\cal B}_{\cal R}$,
$\pi'(b)$  is defined by Equation (\ref{policy}) with $o_{\mbox{\tiny +}}$
replaced by $z_{\mbox{\tiny +}}{=}
(o_{\mbox{\tiny +}},R_{\mbox{\tiny +}})$ and $V^*_t$ replaced by
$U^*_t$.
Since the list $\{\hat{\cal U}_{t, R} |R{\in}{\cal R}\}$
of sets of state space functions returned by \verb+solveROPOMDP+ 
represents $U^*_t$ in the sense of (\ref{local.rep}),
we have that for any $b{\in}{\cal B}_{\cal R}$
\begin{eqnarray}
\label{policy1}
\pi'(b) = arg \hspace{0.1cm}max_a [r(b, a) +
			\gamma\sum_{o_{\mbox{\tiny +}}, R_{\mbox{\tiny +}}}
			P((o_{\mbox{\tiny +}}, R_{\mbox{\tiny +}})|b, a)
		  \hat{\cal U}_{t, R_{\mbox{\tiny +}}}(b_{\mbox{\tiny +}})].
\end{eqnarray}
%where the summation is taken over all possible
%observations $z_{\mbox{\tiny +}}{=}(o_{\mbox{\tiny +}},R_{\mbox{\tiny +}})$
%of ${\cal M}'$ and $b_{\mbox{\tiny +}}$ is 
%the  belief state  for the case
% when $z_{\mbox{\tiny +}}{=}(o_{\mbox{\tiny +}},R_{\mbox{\tiny +}})$
%is observed after taking action $a$ from belief state
%$b$.

The next two sections show how to implement the procedures 
\verb+ROPOMDPupdate+ and \verb+ROPOMDPstop+.


 
\section{Dynamic-Programming Updates for Region Observable POMDPs}
\label{sec7}

This section shows how the incremental pruning algorithm
developed in Section \ref{sec.incr} can be adapted to compute 
parsimonious regional 
 coverings of ${\cal U}_t$ from parsimonious
regional coverings of
${\cal U}_{t-1}$.

		       

\subsection{Properties of Regional Coverings}



\begin{lem}
\label{transitive}
Let $R$ be a region and let ${\cal W}$, ${\cal X}$, and 
${\cal Y}$ be three sets of
state space functions.  If ${\cal W}$  parsimoniously covers ${\cal X}$
 in region $R$ and ${\cal X}$  covers 
${\cal Y}$ in region $R$, then ${\cal W}$ parsimoniously  
covers ${\cal Y}$ in region $R$.  $\Box$
\end{lem}



\begin{lem}
\label{incremental}
Let $R$ be a region and let  ${\cal W}$, ${\cal W}'$, ${\cal X}$, and
${\cal X}'$ be four sets of state space functions.
If ${\cal W}'$ and ${\cal X}'$  respectively cover 
${\cal W}$ and ${\cal X}$   in region $R$, then
\begin{enumerate}
\item ${\cal W}'{\bigoplus}{\cal X}'$ 
covers
${\cal W}{\bigoplus}{\cal X}$ in region $R$.
\item
${\cal W}'{\cup}{\cal X}'$ 
covers
${\cal W}{\cup}{\cal X}$ in region $R$.  $\Box$
\end{enumerate}
\end{lem}




\subsection{Regional Coverings of ${\cal U}_t$ from Parsimonious
Regional Coverings of
	${\cal U}_{t-1}$}

From parsimonious regional coverings  
$\hat{\cal U}_{t-1, R_{\mbox{\tiny +}}}$ 
($R_{\mbox{\tiny +}}{\in}{\cal R}$) of ${\cal U}_{t-1}$, 
this subsection constructs, for each region $R{\in}{\cal R}$,
a set ${\cal U}_{t, R}$ of state space functions and shows that
it covers  ${\cal U}_t$ in region $R$.


For  any action
$a$ and any observation  $z_{\mbox{\tiny +}}{=}
(o_{\mbox{\tiny +}}, R_{\mbox{\tiny +}})$ of ${\cal M}'$, 
 let ${\cal Q}_{a, z_{\mbox{\tiny +}}, R}$ be the set of all
 state space functions $\beta$
 that are of the following form:
\begin{eqnarray}
\label{vazHat}
\beta(s) = \left\{
		\begin{array}{ll} 
		\gamma\sum_{s_{\mbox{\tiny +}}}\alpha(s_{\mbox{\tiny +}})
	P(s_{\mbox{\tiny +}}, z_{\mbox{\tiny +}}|s, a) &
			\mbox{ if $s{\in}R$ } \\
		0  & \mbox{otherwise.}
		\end{array}
	\right .  
\end{eqnarray}
where  $\alpha \in \hat{\cal U}_{t-1, R_{\mbox{\tiny +}}}$.
Define
\begin{eqnarray*}
	{\cal U}_{t, R} &=& \cup_a[\{r(s, a)\}{\bigoplus}(
		{\bigoplus}_{z_{\mbox{\tiny +}}}
	{\cal Q}_{a, z_{\mbox{\tiny +}}, R})].
\end{eqnarray*} 


\begin{pro}
\label{coveringUt}
The set ${\cal U}_{t, R}$ covers  ${\cal U}_t$ in region $R$.
\end{pro}

Formal proof of this proposition can be found in
Appendix A.  
Informally, the fact that 
$\hat{\cal U}_{t-1, R_{\mbox{\tiny +}}}$ covers
${\cal U}_{t-1}$ in region $R_{\mbox{\tiny +}}$ implies
that 
${\cal Q}_{a, z_{\mbox{\tiny +}}, R}$ covers
${\cal Q}_{a, z_{\mbox{\tiny +}}}$ in region $R$,
 where ${\cal Q}_{a, z_{\mbox{\tiny +}}}$ is given by
 (\ref{qao+}) with $o_{\mbox{\tiny +}}$ and ${\cal V}_{t-1}$ replaced by
$z_{\mbox{\tiny +}}$ and ${\cal U}_{t-1}$.
This fact in turn implies that 
 ${\cal U}_{t, R}$ covers  ${\cal U}_t$ in region $R$ because of
Proposition \ref{pro.vtvt-1} and Lemma \ref{incremental}.

\subsection{Possible Observations at the Next Time Point}
In the definition of ${\cal U}_{t, R}$, the cross sum is taken over
all possible observations.  
This subsection shows that some of the possible observations
can be skipped.

For any action $a$ and any region $R$,
define
\[Z_{a, R} = \{ z_{\mbox{\tiny +}} | \sum_{s_{\mbox{\tiny +}}}
			 P(s_{\mbox{\tiny +}}, z_{\mbox{\tiny +}}|s, a) > 0 
	\mbox{ for some $s{\in}R$ } \}.\]
It is the set of  observations that the agent can possibly
receive at the next time point
given that the current state of the world lies in region $R$ and the current
action is $a$.
There are many observations outside this set.  As a matter
of fact, an observation $z_{\mbox{\tiny +}}{=}(o_{\mbox{\tiny +}}, 
R_{\mbox{\tiny +}})$ is not in the set if it is not possible to reach
region $R_{\mbox{\tiny +}}$ from region $R$ in one step.

\begin{figure}[t]
\begin{quote}
------------------------------------------------------------------------------------------------------
\\

	Procedure \verb+ROPOMDPupdate+$(R, \hat{\cal U}_{t-1, R_{\mbox{\tiny +}}}
	|R_{\mbox{\tiny +}}{\in}{\cal R}\})$:
	\begin{itemize}
    \item Inputs: $R$ --- A region, and  for any region $R_{\mbox{\tiny +}}$, \\
	    \verb+      +            $\hat{\cal U}_{t-1, R_{\mbox{\tiny +}}}$
				parsimoniously covers
				${\cal U}_{t-1}$ in region $R_{\mbox{\tiny +}}$.
	\item Output:  A  set of state space functions
		that parsimoniously covers
		  ${\cal U}_t$ in region $R$.
	\end{itemize}
	\begin{enumerate}
	\item {\bf For} each action $a$,
		\begin{enumerate}
		\item Compute the set ${\cal Z}_{a, R}$
		and enumerate its members as $0, 1, \ldots, M$.
		\item {\bf For} $i{=}0$ to $M$,  compute the set
		${\cal Q}_{a, i, R}$.


		\item \({\cal W}_a{\leftarrow}\verb+restrictedIncrPruning+(
		\{{\cal Q}_{a, 0, R}, {\cal Q}_{a, 1, R}, \ldots,
		{\cal Q}_{a, M, R}\}, R). \)

		\end{enumerate}
	\item Return \verb+purge+(${\cup}_a[\{r(s, a)\}\bigoplus{\cal W}_a], R$).
	\end{enumerate}
\end{quote}
\begin{quote}
	Subroutine \verb+restrictedIncrPruning+$(\{{\cal W}_0,
	{\cal W}_1, \ldots, {\cal W}_M\}, R)$:
	\begin{enumerate}
	\item Let ${\cal W}{\leftarrow}{\cal W}_0$.
	\item {\bf For} $i{=}1$ to $M$,
			\[{\cal W}{\leftarrow}
			\verb+purge+({\cal W}{\bigoplus}
			{\cal W}_i, R). \]
	\item Return ${\cal W}$.
	\end{enumerate}
------------------------------------------------------------------------------------------------------

\end{quote}
\caption{Dynamic-programming updates for region observable POMDPs.}
 \label{ROPOMDPupdate}
\end{figure}



For any $z_{\mbox{\tiny +}}{=}(o_{\mbox{\tiny +}}, R_{\mbox{\tiny +}})$,
if $z_{\mbox{\tiny +}}{\notin}Z_{a, R}$, 
then $\sum_{s_{\mbox{\tiny +}}} P(s_{\mbox{\tiny +}}, z_{\mbox{\tiny +}}|s, a)=0$
for all $s{\in}R$. In such a case,
${\cal Q}_{a, z_{\mbox{\tiny +}}, R}=\{0\}$
according to (\ref{vazHat}).
Since, $\{0\}{\bigoplus}{\cal W}{=}{\cal W}$ for any set 
${\cal W}$ of state space functions, we have
\begin{eqnarray*}
	{\cal U}_{t, R} &=& \cup_a[\{r(s, a)\}{\bigoplus}(
		{\bigoplus}_{z_{\mbox{\tiny +}} \in
		Z_{a, R}}
	{\cal Q}_{a, z_{\mbox{\tiny +}}, R})].
\end{eqnarray*}




 

\subsection{Parsimonious Regional Covering of ${\cal U}_t$}

Proposition \ref{coveringUt} and Lemma \ref{transitive} imply
that, for any region $R$, a set of state space functions parsimoniously
covers ${\cal U}_t$ in region $R$ if and only if it 
parsimoniously covering ${\cal U}_{t, R}$ in region $R$.
According to  Lemmas \ref{transitive}
and \ref{incremental},
a set of state space functions that parsimoniously
covers ${\cal U}_{t, R}$ in region $R$
can be found using the procedure \verb+ROPOMDPupdate+ shown in
Figure \ref{ROPOMDPupdate} (c.f. Section \ref{sec.new}).
In the procedure, the subroutine
 \verb+purge+$({\cal W}, R)$  takes
a set ${\cal W}$ of state space functions and region $R$, and returns
a set of state space functions that
 parsimoniously  covers ${\cal W}$ in region $R$.
An implementation of this subroutine can be found in Appendix B.










\section{The Stopping Condition}
\label{sec8}


This section shows how 
to determine whether the restricted Bellman residual 
has fallen below a predetermined threshold
$\epsilon$  from   regional coverings  of ${\cal U}_t$ and ${\cal U}_{t-1}$.
For any region $R$, let $\hat{\cal U}_{t, R}$ and 
$\hat{\cal U}_{t-1, R}$ be 
 two sets of state space functions that respectively
 cover ${\cal U}_t$ and ${\cal U}_{t-1}$ in region $R$. 
By the definition of regional coverings, we have                                


\begin{figure}[t] 
\begin{quote}
\begin{quote}
---------------------------------------------------------------------------------
\\

	Procedure \verb+ROPOMDPstop+$(\{\hat{\cal U}_{t, R}|R{\in}{\cal R}\}, 
				\{\hat{\cal U}_{t-1, R}|R{\in}{\cal R}\}, 
				\epsilon)$
	\begin{itemize}
	\item Inputs: $\epsilon$ --- A positive number, and for any region $R$ \\
		\verb+      +$\hat{\cal U}_{t, R}$ 
			covers ${\cal U}_t$ in region $R$, and \\
		\verb+      +$\hat{\cal U}_{t-1, R}$ covers
			${\cal U}_{t-1}$ in region $R$.
			
	\item Outputs: \verb+yes+ --- If the restricted Bellman residual 
					$\leq \epsilon$, \\
		\verb+        +\verb+no+ --- Otherwise.
	\end{itemize}
	\begin{enumerate}
	\item {\bf For} each region $R$,
		\begin{enumerate}
		\item flag $\leftarrow$ \verb+yes+.
		\item {\bf For} each $\alpha{\in}\hat{\cal U}_{t-1, R}$,        
	\[\mbox{flag $\leftarrow$ \verb+no+  if \verb+dominate+}(\alpha, 
			\hat{\cal U}_{t, R},
			R, \epsilon) \neq \verb+nil+.\]
		\item {\bf For} each $\alpha{\in}\hat{\cal U}_{t, R}$,        
	\[\mbox{flag $\leftarrow$ \verb+no+  if \verb+dominate+}(\alpha, 
			\hat{\cal U}_{t-1, R},
			R, \epsilon) \neq \verb+nil+.\]
				
		\item Return \verb+no+ if flag = \verb+no+.
		\end{enumerate}
	\item Return \verb+yes+.
	\end{enumerate}
---------------------------------------------------------------------------------


\end{quote}
\end{quote}



\caption{Procedure for determining whether the restricted Bellman residual has
  fallen below a threshold. }
\label{stop}
\end{figure}

\begin{lem}
\label{edominate}
The restricted Bellman residual is  no larger than $\epsilon$ if and only if
for any  region $R$ and any belief state $b{\in}{\cal B}_R$,
\begin{enumerate}
\item For any   $\alpha{\in}\hat{\cal U}_{t, R}$,
	\[\alpha(b) \leq \hat{\cal U}_{t-1, R}(b){+}\epsilon, \mbox{   and}\] 
\item For any   $\alpha{\in}\hat{\cal U}_{t-1, R}$,
	\[\alpha(b) \leq \hat{\cal U}_{t, R}(b){+}\epsilon. \Box\]
\end{enumerate}
 \end{lem}


Let \verb+dominate+$(\alpha, {\cal W}, R, \epsilon)$ be a procedure that returns
a belief state $b$ in ${\cal B}_R$  such that
\(\alpha(b)>{\cal W}(b){+}\epsilon\). 
If such a belief state does not exist, it  returns
 \verb+nil+. An implementation of this procedure
can be found in Appendix B.  The  procedure \verb+ROPOMDPupdate+
shown in Figure \ref{stop} returns
\verb+yes+ if the restricted Bellman residual has fallen below $\epsilon$ and
\verb+no+ otherwise.

A couple of notes are in order.  First, 
when the reward function $r(s, a)$ is non-negative, $U^*_t$ increases
with $t$. In this case, the restricted Bellman residual becomes
$max_{b{\in}{\cal B}_{\cal R}}(U^*_t(b){-}U^*_{t-1}(b))$.  Consequently,
step (c) can be skipped.
Second, when $r(s, a)$ takes negative values for some $s$ and some $a$,
a constant can be added to it so that it becomes non-negative.
Adding a constant to $r(s, a)$ does not affect the optimal
policy.  However, it makes it easier to determine whether the
restricted Bellman residual has fallen below a threshold.


\section{Decision Making for the Original POMDP}
\label{sec9}

Suppose we have solved the region observable POMDP ${\cal M}'$.
The next step is to construct a policy $\pi$ for
the original POMDP ${\cal M}$ based on the solution for ${\cal M}'$. 


Even though it is our assumption that in the original POMDP ${\cal M}$
the agent has a good idea
about the state of the world at all times, there is no guarantee
that its belief state are  always  in ${\cal B}_{\cal R}$.
There is no oracle in ${\cal M}$.
A policy should prescribe actions
 for belief states in
${\cal B}_{\cal R}$ as well as for belief states outside
${\cal B}_{\cal R}$.  
One issue here is that the policy $\pi'$ 
for ${\cal M}'$ is defined only for belief states in
${\cal B}_{\cal R}$.   Fortunately,
 $\pi'$  can be naturally extended to the entire belief space by    
 ignoring the constraint $b{\in}{\cal B}_{\cal R}$ in    
Equation (\ref{policy1}).
We hence define a policy $\pi$ for ${\cal M}$  
as follows: for any $b{\in}{\cal B}$, 
\begin{eqnarray}
\label{policy2}
\pi(b) = arg \hspace{0.1cm}max_a [r(b, a) +
			\gamma\sum_{o_{\mbox{\tiny +}}, R_{\mbox{\tiny +}}}
			P((o_{\mbox{\tiny +}}, R_{\mbox{\tiny +}})|b, a)
		  \hat{\cal U}_{t, R_{\mbox{\tiny +}}}(b_{\mbox{\tiny +}})].
\end{eqnarray} 



Let $k$ be the radius of the region system underlying
${\cal M}'$.  The policy $\pi$   given above will be
referred to as the {\em radius-k approximate policy} for
${\cal M}$.  The entire process of obtaining this policy, including the
construction and solving  of the region observable POMDP ${\cal M}'$,
will be referred to as {\em region-based approximation}.

It is worthwhile to compare this equation with Equation (\ref{policy}).
In Equation (\ref{policy}), there are two terms on the right hand
side.  The first term is the immediate reward for taking action
$a$ and the second term is the discounted future reward  the
agent can expect to receive if it behaves optimally.  
Their sum is the total expected reward for taking action $a$.
The action with the 
highest total reward is chosen.

The second term is difficult to obtain.
In essence, Equation (\ref{policy2}) 
approximates  the second term   using
the optimal expected future reward   the agent can receive with
the help of the oracle, which  is easier to compute.

It should be emphasized that the presence of the oracle is  assumed
only in the process of computing the radius-k approximate policy.
The oracle is not present when executing the policy.


\section{Quality of Approximation and Simulation}
\label{sec.qua}
In general, the quality of an approximate policy $\pi$ is measured
by the distance between 
its  value function $V^{\pi}(b)$ and the optimal value function $V^*(b)$. 
This measurement does not consider what an agent might
know about the initial state of the world. As such, it is not
appropriate for a policy obtained   through region-based 
approximation.
One cannot  expect such  a policy 
to be of good quality if an agent is very uncertain about the
initial state of the world because it is obtained under the
assumption that an agent has a good idea about the state of
the world at all times. 

This section describes a scheme for
determining the quality of an approximate policy in cases where
an agent knows the initial state of the world with certainty.
The scheme can be generalized to cases where there is a small
amount of uncertainty about the initial state; for example, cases
where the initial state is known to be in some small region.

An agent might need to reach a goal from different initial
states at different times. Let $P(s)$ be the frequency it will
start from state $s$\footnote{
This is not to be confused with the initial belief state $P_0$, which
represents the agent's knowledge about the ninitial state at a
particular trial.}.
 The quality of an approximate policy $\pi$ can be measured by
 $\sum_s|V^*(s)-V^{\pi}(s)|P(s)$, where 
 $V^*(s)$ and $V^{\pi}(s)$ denote the rewards
 the agent can expect to receive starting from state $s$
 if it behaves optimally or according to $\pi$ respectively.
 
 
By definition $V^*(s){\geq}V^{\pi}(s)$ for all $s$. 
Let $U^{*}$ be the
optimal value function of the region observable POMDP ${\cal M}'$.
Since more information 
is available to the agent in ${\cal M}'$, $U^{*}(s){\geq}V^*(s)$
for all $s$.  Therefore, 
$\sum_s[U^{*}(s)-V^{\pi}(s)]P(s)$ is an upper
bound on  $\sum_s[V^*(s)-V^{\pi}(s)]P(s)$.

Let $\pi'$ be the policy for
${\cal M}'$ given by (\ref{policy1}).  When the restricted  Bellman
residual is small, $\pi'$ is close to optimal for ${\cal M}'$ and
the value function $V^{\pi'}$ of $\pi'$ is close to $U^{*}$.
Consequently,
$\sum_s[V^{\pi'}(s)-V^{\pi}(s)]P(s)$ is an upper
bound on  $\sum_s[V^*(s)-V^{\pi}(s)]P(s)$ when the  restricted
Bellman
residual is small enough.


One way to estimate the quantity $\sum_s[V^{\pi'}(s)-V^{\pi}(s)]P(s)$
is to conduct a large number of simulation trials.  
In each trial,  an initial state 
is randomly generated according to $P(s)$. The agent is informed  of the initial  
state. Simulation takes place in both ${\cal M}$ and ${\cal M}'$.
In ${\cal M}$, the agent chooses, at each step, an action  using $\pi$ 
based on 
its current belief state.  The action is passed to
a simulator which randomly generates the next state of the world
and the next observation according to the transition 
and observation probabilities. The observation (but not the state) is passed to  
the agent, who updates its belief state and chooses the next
action.   And so on and so forth. The trial terminates when
the agent chooses the action \verb+declare-goal+ or a maximum number 
of steps is reached. 
Simulation in ${\cal M}'$ takes place in a similar manner except  that the observations
and the observation probabilities are different and
actions are chosen using $\pi'$.

If the goal is correctly declared at the end of a trial, the
agent receives a reward in the amount $\gamma^n$, where $n$ is
the number of steps.  Otherwise, the agent receive no reward.
The quantity
$\sum_s[V^{\pi'}(s)-V^{\pi}(s)]P(s)$ 
can be estimated using the
difference between the average reward received in the trials for
${\cal M}'$ and the average reward received in the trials for ${\cal M}$.


\section{Tradeoff Between Quality and Complexity}
\label{sec.trade}
Intuitively, the larger the radius of the region system, the less 
the amount of additional information the oracle provides.
Hence the closer  ${\cal M}'$ is to ${\cal M}$ and the narrower
the gap between $\sum_sV^{\pi'}(s)P(s)$ and $\sum_sV^{\pi}(s)P(s)$.
Although we have not theoretically proved this, empirical
results (see the next section) do suggest that
$\sum_sV^{\pi}(s)P(s)$ increases with the radius of the region system
while $\sum_sV^{\pi'}(s)P(s)$ decreases with it.  In the extreme case when
there is one region in the region system that contains all
the possible states of the world, ${\cal M}$ and ${\cal M}'$
are identical and hence so are   
$\sum_sV^{\pi'}(s)P(s)$ and $\sum_sV^{\pi}(s)P(s)$.

These discussions lead to the following   
scheme for making the tradeoff between complexity and
quality:  Start with the radius-0 region system and increase
the radius gradually until the quantity 
$\sum_s[V^{\pi'}(s)-V_{\pi}(s)]P(s)$
becomes sufficiently small 
or the region observable POMDP ${\cal M}'$ becomes untractable. 



\section{Simulation Experiments}
\label{sec10}

Simulation experiments have been carried out to show that
(1) approximation quality  increases  with radius of region
system and (2) where there is not much uncertainty, a POMDP
can be accurately approximated by a region-observable POMDP
that can be solved exactly.  This section reports on the
experiments.

\subsection{Synthetic Office Environments}


Our experiments were conducted using
two   synthetic office environments borrowed from Cassandra {\em et al}. 
(1996) with some minor modifications.
Layouts of the environments are shown in Figure \ref{office}, where squares
represent locations. 
Each location is represented as four states in the POMDP model, one 
for each orientation. The dark locations are rooms connected
to corridors by doorways.


\begin{figure}[t]
\begin{center}
\makebox{
	\epsfxsize=4cm
	\epsffile{enA.ps}
 }
\makebox{
	\epsfxsize=6cm
	\epsffile{enB.ps}
}
\end{center}
\begin{center}
{\bf Transition Probabilities}  \\ 
\  \\

 \begin{tabular}{|l|l|l|} \hline
 Action & Standard outcomes & Noisy outcomes \\ \hline
\verb+move-forward+ & N (0.11), F (0.88), F-F (0.01) &
                 N (0.2), F (0.7), F-F (0.1)\\
\verb+turn-left+ & N (0.05), L (0.9), L-L (0.05) &
                N (0.15), L (0.7), L-L (0.15)\\
\verb+turn-right+ & N (0.05), R (0.9), R-R (0.05) &
         N (0.15), R (0.7), R-R (0.15)  \\
\verb+declare-goal+ & N (1.0) & N (1.0) \\ \hline
\end{tabular}
\end{center}
\ \\

\begin{center}
{\bf Observation Probabilities} \\
\ \\

\begin{tabular}{|c|p{6cm}|p{6cm}|} \hline
Actual case & Standard observations & Noisy observations \\ \hline
\verb+wall+ & \verb+wall+ (0.90), \verb+open+ (0.04),
                \verb+doorway+ (0.04), \verb+undetermined+ (0.02)
                & \verb+wall+ (0.70), \verb+open+ (0.19),
                \verb+doorway+ (0.09), \verb+undetermined+ (0.02)
                \\              \hline
\verb+open+ & \verb+wall+ (0.02), \verb+open+ (0.90),
                \verb+doorway+ (0.06), \verb+undetermined+ (0.02)
                & \verb+wall+ (0.19), \verb+open+ (0.70),
                \verb+doorway+ (0.09), \verb+undetermined+ (0.02)
                \\              \hline
\verb+doorway+ & \verb+wall+ (0.15), \verb+open+ (0.15),
                \verb+doorway+ (0.69), \verb+undetermined+ (0.01)
                & \verb+wall+ (0.15), \verb+open+ (0.15),
                \verb+doorway+ (0.69), \verb+undetermined+ (0.01)
                \\              \hline
\end{tabular}
\end{center}

\caption{Synthetic Office Environments. }
\label{office}
\end{figure}


In each environment, a robot needs to reach the goal location with
the correct orientation.  At each step,  the robot can 
execute one of the following actions:
\verb+move-forward+, \verb+turn-left+, \verb+turn-right+, and
\verb+declare-goal+.  The two sets of action models given in
Figure \ref{office} were used in our experiments.
For the action \verb+move-forward+,
the term F-F (0.01) means that with probability 0.01 the robot
actually moves two steps forward.  
The other terms are to be
interpreted similarly. 
If an outcome cannot occur in a certain state of the world,
then the robot is left in the last state before the
impossible outcome. 
%Two sets of outcomes,
%standard and noisy,  were used in the experiments so that
%we can see the effects of increasing noise.

In each state, the robot is able to perceive in each of three
nominal directions (front, left, and right) whether there is
a \verb+doorway+, \verb+wall+, \verb+open+, or it is
\verb+undetermined+.  The  two sets of observation models
shown in Figure \ref{office} were used in our experiments.



\subsection{Complexity of Solving the POMDPs}

%The sizes of the POMDPs for 
%the two environments are given in the following table.
%
%\begin{center}
%\begin{tabular}{|p{1cm}|p{1.5cm}|p{1.8cm}|p{1.5cm}|} \hline
%       Environ -ment & Number of states & Number of observations & 
%                       Number of actions \\ \hline \hline
%       A       &  280 & 64 & 4 \\
%       B       & 200 & 64 & 4 \\ \hline
%\end{tabular}
%\end{center}

One of the POMDPs has 280 possible states while the other has
200.  They both have 64 possible observations and 4 possible actions.
 Since  the largest
POMDPs that researchers have been able to solve  exactly so far
 have less than 20
states and 15 observations,  it is safe to say no 
existing exact algorithms can solve those two POMDPs.

 We
were  able to solve the radius-0 and radius-1 approximations 
(region observable POMDPs) of 
the two POMDPs on a SUN SPARC20 computer.  The threshold for
the  Bellman residual was set at 0.001 and the
discount factor at 0.99.
 The amounts of time  it took in  CPU seconds
  are collected in the following table.
\\


\begin{center}
\begin{tabular}{ccccc} \hline
Environment & \multicolumn{2}{c}{Standard models} & \multicolumn{2}{c}{Noisy  models}  \\ \cline{2-5}
	    & Radius-0 & Radius-1 & Radius-0 & Radius-1 \\ \hline 
A           & 1.26 & 3373& 1.35 & 5984\\ 
B           &  0.61& 2437& 0.72 & 3952 \\ \hline
\end{tabular}
\end{center}
\ \\


\noindent
We see that the radius-1 approximations took much longer time to solve
than the radius-0 approximations. 
Also notice that the region observable POMDPs with noisy action and observation
models took more time to solve that 
those with the standard  models.
This suggests that the more nondeterministic the  actions
and the less informative the observations, the more difficult it is to solve
a POMDP.

We were unable to solve the radius-2 approximations. 
Other approximation techniques  need to be incorporated in order
to solve the  approximations based on region systems with radius larger
than or equal to 2. 


\subsection{Approximation Quality  for Standard Models}

To determine the quality of the radius-0 and radius-1 
approximate policies  for the POMDPs with
standard action and observation models, 1000
simulation trials were conducted using the scheme described
in Section \ref{sec.qua}. It was assumed that
the agent is equally likely to start from any state.
Average rewards obtained in the original POMDPs
${\cal M}$ (i.e. without the help of the oracle)
and in the corresponding region-observable
POMDPs ${\cal M}'$  (i.e.  with the help of the oracle)
are shown in the following table. \\


\begin{center}
\begin{tabular} {ccccc} \hline
		 &  \multicolumn{2}{c}{Environment A} &
			 \multicolumn{2}{c}{Environment B}  \\ \cline{2-3} \cline{4-5}
		 & radius-0 & radius-1 & radius-0 & radius-1 \\ \hline
Average reward in ${\cal M}$ & 0.806535&   0.815695   & 0.866118 & 0.868533 \\  
Average reward in ${\cal M}'$ &0.827788&   0.818534   & 0.883271 & 0.876356 \\  
Difference &                  0.021253  & 0.002839   & 0.017153 & 0.007823\\ \hline
\end{tabular}
\end{center}
\ \\


We see that, when the radius-0 policies were used, 
the differences  between the rewards obtained in ${\cal M}$ and those
obtained in 
${\cal M}'$  are very small in both environments. This indicates that
the radius-0 region observable POMDPs (i.e. MDPs)  are accurate
approximations of the original POMDPs.  The radius-0 approximate
policies are close to optimal for the original POMDPs.  
When the radius-1 policies were used, the differences
are even smaller; the rewards obtained in ${\cal M}$ and 
those obtained in ${\cal M}'$
are essentially the same.


Consider the rewards obtained in the original POMDPs.
We see that they are larger when radius-1 policies were used than when
radius-0 policies were used.
This supports our claim that  approximation quality 
increases with  radius of region system.


There is a another fact worth mentioning.
The differences between rewards obtained in ${\cal M}$ 
and those obtained in ${\cal M}'$ are larger in Environment B  than in Environment
A.  This is because Environment B is more symmetric and
consequently observations are less effective in disambiguating
uncertainty in the agent's belief about the state of the world.


\subsection{Approximation Quality for Noisy Models}

One thousand trials were also conducted for the POMDPs
 with noisy action and observation models.
Results are shown in the following table.
\\

\begin{center}
\begin{tabular} {ccccc} \hline
		 &  \multicolumn{2}{c}{Environment A} &
			 \multicolumn{2}{c}{Environment B}  \\ \cline{2-3} \cline{4-5}
		 & radius-0 & radius-1 & radius-0 & radius-1 \\ \hline
Average reward in ${\cal M}$ & 0.596670& 0.634934    & 0.445653   & 0.565099 \\  
Average reward in ${\cal M}'$ &0.812898&   0.722441   & 0.871903 & 0.818365 \\  
Difference &                  0.214228  & 0.087507   & 0.426250 & 0.253266\\ \hline
\end{tabular}
\end{center}

  \ \\



We see that   the differences  between rewards obtained in 
${\cal M}$ and rewards obtained  in ${\cal M}'$  
are significantly smaller when the radius-1 policies
were used than when the radius-0 policies were used. 
This is the case
 especially in
Environment A.  
Also the rewards obtained in ${\cal M}$ are larger
 when the radius-1 policies
were used than when the radius-0 policies were used. 
Those again support our claim that approximation quality 
increases with radius of region system.


As far as absolute  approximation quality is concerned, 
the radius-0 POMDPs (i.e. MDPs) are obviously very poor approximations
of the original POMDPs; when
the radius-0 policies were used, the rewards obtained
in ${\cal M}$ are significantly smaller than the rewards obtained
in ${\cal M}'$.
 For Environment A, the radius-1 approximation
is fairly accurate.  However, the radius-1 approximation
remains poor for Environment B.  The radius of region
system needs to be increased.


Tracing through the trials step by step, we  observed some interesting
facts.  In Environment B, the agent, under the
guidance of the radius-1 approximate policy,
 was able to quickly get to the neighborhood of the goal even
when starting from far way.
The fact that the Environment around the goal
is highly symmetric was the cause of the  poor performance.
Often the agent was not able to determine whether it was
at the goal location (room), or in the opposite room,
or in the left most room, or in the room to the right of 
the goal location.  The performance would be close
to optimal if the goal location had some distinct features.

In Environment A, the agent, again under the guidance of
the radius-1 approximate policy, was able to reach and declare
the goal successfully once it got to the neighborhood.
However, it often took many unnecessarily steps before
reaching the neighborhood due to uncertainty in the
effects of the turning actions.
For example,
when the agent reached the  lower left corner from above,
it was facing downward. The agent executed the action \verb+turn_left+.
Fifteen percent of the time, it ended up facing upward instead of
to the right.  The agent then
decided to \verb+move-forward+, thinking that it was approaching
the goal.  But it was actually moving upward and did not realize
this until a few steps later.  The agent would perform
much better if there were informative landmarks around the corners.


\section*{Appendix A: Proofs
of Propositions \ref{theo.incr} and 
\ref{coveringUt}}

\begin{lem}
\label{covering.def1}
Suppose ${\cal W}$ and ${\cal X}$ are two sets of state space functions.
If ${\cal W}$ covers
${\cal X}$, then for any non-negative   function $f(s)$,
\[max_{\alpha{\in}{\cal W}}\sum_s\alpha(s)f(s) =
max_{\beta{\in}{\cal X}}\sum_s\beta(s)f(s). \Box\]
\end{lem}

\noindent {\bf Proof of Proposition \ref{theo.incr}:}
Because of Proposition \ref{pro.vtvt-1} and
 Lemma \ref{incremental1}, it suffices to show
 that ${\cal Q}'_{a, o_{\mbox{\tiny +}}}$
covers  ${\cal Q}_{a, o_{\mbox{\tiny +}}}$.
By the definition of ${\cal Q}_{a, o_{\mbox{\tiny +}}}$ and
Equation (\ref{induced.bf}), we have, for
 any belief state $b$, that
\begin{eqnarray}
{\cal Q}_{a, o_{\mbox{\tiny +}}}(b) & = &
  max_{\alpha{\in}{\cal V}_{t-1}}\sum_s [\gamma
  \sum_{s_{\mbox{\tiny +}}}\alpha(s_{\mbox{\tiny +}})
        P(s_{\mbox{\tiny +}}, o_{\mbox{\tiny +}}|s, a)]b(s)  \nonumber \\
  &=& \gamma \verb+ + max_{\alpha{\in}{\cal V}_{t-1}}
  \sum_{s_{\mbox{\tiny +}}}\alpha(s_{\mbox{\tiny +}})
        [\sum_sb(s)P(s_{\mbox{\tiny +}}, o_{\mbox{\tiny +}}|s, a)]
        \nonumber
\end{eqnarray}
  Since $\hat{\cal V}_{t-1}$ covers ${\cal V}_{t-1}$ and
the term within the square brackets
is a non-negative function of $s_{\mbox{\tiny +}}$,
by Lemma \ref{covering.def1} we have

 \begin{eqnarray}
{\cal Q}_{a, o_{\mbox{\tiny +}}}(b)
 &=& \gamma \verb+ + max_{\alpha{\in}\hat{\cal V}_{t-1}}
  \sum_{s_{\mbox{\tiny +}}}\alpha(s_{\mbox{\tiny +}})
        [\sum_sb(s)P(s_{\mbox{\tiny +}}, o_{\mbox{\tiny +}}|s, a)]
         \nonumber \\
  &=& max_{\alpha{\in}\hat{\cal V}_{t-1}}\sum_s [\gamma
  \sum_{s_{\mbox{\tiny +}}}\alpha(s_{\mbox{\tiny +}})
        P(s_{\mbox{\tiny +}}, o_{\mbox{\tiny +}}|s, a)]b(s)   \nonumber \\
 &=&
  {\cal Q}'_{a, o_{\mbox{\tiny +}}}(b), \nonumber
\end{eqnarray}
where the last equation is
due to the definition of ${\cal Q}'_{a, o_{\mbox{\tiny +}}}$ and
Equation (\ref{induced.bf}).
So, ${\cal Q}'_{a, o_{\mbox{\tiny +}}}$
does  cover  ${\cal Q}_{a, o_{\mbox{\tiny +}}}$.
The proposition is proved.
$\Box$


 
\begin{lem}
\label{s+z+sa}
For any observation $z_{\mbox{\tiny +}}{=}(o_{\mbox{\tiny +}},
R_{\mbox{\tiny +}})$ of the region observable POMDP ${\cal M}'$,
        \[P(s_{\mbox{\tiny +}}, z_{\mbox{\tiny +}}|s, a)=0,\]
for any
 $s_{\mbox{\tiny +}}{\notin}R_{\mbox{\tiny +}}$. $\Box$
\end{lem}
Informally, this lemma says that the true state of the world
must be in the region reported by the oracle.
            
\begin{lem}
\label{rcovering.def}
Let ${\cal W}$ and ${\cal X}$ be two sets of state space functions
and $R$ be a region.
If ${\cal W}$ covers
${\cal X}$ in region $R$, then for  non-negative function $f(s)$ that
is $0$ when $s{\notin}R$, we have 
 \[max_{\alpha{\in}{\cal W}}\sum_s\alpha(s)f(s) =
max_{\beta{\in}{\cal X}}\sum_s\beta(s)f(s). \Box \]
\end{lem}

\noindent {\bf Proof of Proposition \ref{coveringUt}}:
Because of 
Proposition \ref{pro.vtvt-1} and Lemma \ref{incremental},
it suffices to show that
${\cal Q}_{a, z_{\mbox{\tiny +}}, R}$ covers
${\cal Q}_{a, z_{\mbox{\tiny +}}}$ in region $R$,
where ${\cal Q}_{a, z_{\mbox{\tiny +}}}$ is given by
 (\ref{qao+}) with $o_{\mbox{\tiny +}}$ and ${\cal V}_{t-1}$ replaced by
$z_{\mbox{\tiny +}}$ and ${\cal U}_{t-1}$.

Let $b$ be any belief state in ${\cal B}_R$.
 Similar to  the proof of Theorem \ref{theo.incr}, we
have
\begin{eqnarray}
{\cal Q}_{a, z_{\mbox{\tiny +}}}(b)
 & = &
   \gamma \verb+ + max_{\alpha{\in}{\cal U}_{t-1}}
  \sum_{s_{\mbox{\tiny +}}}\alpha(s_{\mbox{\tiny +}})
        [\sum_sb(s)P(s_{\mbox{\tiny +}}, z_{\mbox{\tiny +}}|s, a)]
        \nonumber \\
 &=& \gamma \verb+ + max_{\alpha{\in}\hat{\cal U}_{t-1,
        R_{\mbox{\tiny +}}}}
  \sum_{s_{\mbox{\tiny +}}}\alpha(s_{\mbox{\tiny +}})
        [\sum_sb(s)P(s_{\mbox{\tiny +}}, z_{\mbox{\tiny +}}|s, a)]
        \nonumber \\
 &=&  max_{\alpha{\in}\hat{\cal U}_{t-1, R_{\mbox{\tiny +}}}}
  \sum_{s{\in}R}[\gamma \sum_{s_{\mbox{\tiny +}}}\alpha(s_{\mbox{\tiny +}})
        P(s_{\mbox{\tiny +}}, z_{\mbox{\tiny +}}|s, a)]b(s)
        \nonumber \\
&=& max_{\beta{\in} {\cal Q}_{a, z_{\mbox{\tiny +}}, R}}
         \sum_s\beta(s)b(s) \nonumber \\
&=& {\cal Q}_{a, z_{\mbox{\tiny +}}, R}(b), \nonumber
\end{eqnarray}
where the second equation is true because of the fact that
$\hat{\cal U}_{t-1, R_{\mbox{\tiny +}}}$  covers
 ${\cal U}_{t-1}$ in region $R_{\mbox{\tiny +}}$ and of
Lemma \ref{rcovering.def}.  The term within the square brackets
is a non-negative function of $s_{\mbox{\tiny +}}$ and it is $0$ when
$s_{\mbox{\tiny +}}{\notin}R_{\mbox{\tiny +}}$ because
of Lemma \ref{s+z+sa}.
The fourth equation is true because that
$b(s){=}0$ when $s{\notin}R$.
The proposition is proved.
$\Box$



\section*{Appendix B: Domination and  Pruning}

This appendix describes  implementation of 
the procedures \verb+dominate+$(\alpha, {\cal W}, R, \epsilon)$,
 \verb+purge+$({\cal W}, R)$, and \verb+purge+$({\cal W})$.
  They were not given in the main text
because they are minor adaptations of existing algorithms.

The procedure  \verb+dominate+$(\alpha, {\cal W}, R, \epsilon)$ takes,
 as inputs, a state space function $\alpha$, 
a set of state space functions ${\cal W}$,
a region $R$, and a nonnegative number $\epsilon$.
It returns
 a belief state $b$ in ${\cal B}_R$ 
such that $\alpha(b){>}{\cal W}(b){+}\epsilon$.
 If such a belief state does not  
exist, it  returns \verb+nil+. 
It can be implemented as follows.
        \begin{quote}
        Procedure \verb+dominate+$(\alpha, {\cal W}, R, \epsilon)$
        \begin{itemize}
        \item Inputs: 
                $\alpha$ --- A state space function,\\
	       \verb+      +	 ${\cal W}$ --- A set of state space functions, \\
               \verb+      + $R$ --- A region, $\epsilon$ --- A nonnegative number.
        \item Output:  A belief state in ${\cal B}_R$ or \verb+nil+.
        \end{itemize}

        \begin{enumerate}
        \item {\bf If} ${\cal W}{=}\emptyset$, return an arbitrary
                belief state in ${\cal B}_R$.

        \item Solve the following linear program:
                \begin{quote}
                \vspace{-0.5cm}
                \item Variables: $x$, $b(s)$ for each $s{\in}R$.        
                \item Maximize: $x$
                \item Constraints: 
                        \begin{eqnarray*}
                        &&\sum_{s{\in}R}\alpha(s)b(s) \geq x  +
                                \sum_{s{\in}R}\beta(s)b(s) \mbox{ for all }
                                        \beta{\in}{\cal W},  \\
                        &&\sum_{s{\in}R}b(s) = 1 \\
                        &&b(s) \geq 0 \mbox{ for all } s{\in}R.
                        \end{eqnarray*}
                \end{quote}

        \item {\bf If} $x{\leq}\epsilon$, return \verb+nil+,
		 {\bf else} return $b$.


        \end{enumerate}

        \end{quote}


The procedure \verb+purge+$({\cal W}, R)$ takes a set of state space functions
${\cal W}$ and a region $R$ and returns 
a set of state space functions that parsimoniously covers
${\cal W}$ in region $R$.
To implement it, we need two subroutines.

A state space function $\alpha$ {\em pointwise dominates} another
state space function $\beta$ in a region $R$ if 
$\alpha(s){\geq}\beta(s)$ for all $s{\in}R$.  
The subroutine \verb+pointwisePurge+$({\cal W}, R)$ 
returns a minimal subset ${\cal W}'$ of ${\cal W}$ 
such that each state space function in ${\cal W}$ is pointwise dominated 
in the region $R$ by
at least one state space function in ${\cal W}'$.
Implementation of this subroutine is straightforward.


The subroutine \verb+best+$(b, {\cal W}, R)$ returns
a state space function $\alpha$ in ${\cal W}$ such that
$\sum_{s{\in}R}b(s)\alpha(s) \geq \sum_{s{\in}R}b(s)\beta(s)$
for any other state space function $\beta$ in ${\cal W}$.
Implementation of the subroutine is straightforward
except for the issue of tie breaking. If the ties are not
broken properly, 
\verb+purge+$({\cal W}, R)$ 
might return a regional covering   of ${\cal W}$ that is not parsimonious.
A correct way to break ties is as follows:  Fix an ordering
among states in $R$. This induces a lexicographic ordering among
all state space functions.  Among
the tied state space functions, chose the one that is the largest under the
lexicographic ordering (Littman, 1994). 




The following
implementation of \verb+purge+ is based on Lark's algorithm (White, 1991).  


        \begin{quote}
        Procedure \verb+purge+$({\cal W}, R)$ \\
        \begin{itemize}
        \vspace{-0.5cm}

        \item Inputs: ${\cal W}$ --- A set of state space functions, \\
                \hspace{8.5cm} \verb+      + $R$ --- A region.

        \item Output:  A set of state space functions that
		parsimoniously covers ${\cal W}$ in region $R$.


        \end{itemize}
        \noindent
        \begin{enumerate}
        \item ${\cal W}{\leftarrow}\verb+pointwisePurge+({\cal W}, R)$. 
        \item ${\cal X}{\leftarrow}\emptyset$.

        \item {\bf While} ${\cal W}{\neq}\emptyset$,
                \begin{enumerate}
                \item Pick a state space function $\alpha$ from ${\cal W}$.
                \item $b{\leftarrow}\verb+dominate+(\alpha, {\cal X}, R, 0)$.
                \item {\bf If} $b=$\verb+nil+, remove $\alpha$ from
                        ${\cal W}$.
                \item {\bf Else} remove \verb+best+($b, {\cal W}, R$)
                        from ${\cal W}$ and add it to ${\cal X}$.
                \end{enumerate}
        \item Return ${\cal X}$.
        \end{enumerate}
        
        \end{quote}

Finally, the procedure \verb+purge+$({\cal W})$ takes a set of state space
functions ${\cal W}$ and returns a parsimonious covering of ${\cal W}$.
It can be  implemented simply as follows.

  \begin{quote}
        Procedure \verb+purge+$({\cal W})$:
	 \begin{itemize}
	\item  \verb+purge+$({\cal W}, {\cal S})$.
	\end{itemize}
  \end{quote}
Here, ${\cal S}$ is the set of all possible states of the world.

\subsection*{References}

\begin{description}

\item    Bellman, R. (1957). 
	{\em Dynamic Programming}. Princeton University Press.

\item Bertsekas, D. P. (1987).
        {\em Dynamic Programming: Deterministic and Stochastic Models}.
        Prentice-Hall.




\item Bertsekas, D. P.,  \&  Castanon, D. C. (1989). Adaptive Aggregation 
	for Infinite Horizon Dynamic Programming. {\em IEEE trans. on auto.
	control}, vol 34, No  6.

\item Boutilier, C.,  Dearden, R., \&  Goldszmidt, M. (1995).
	Exploiting structures in policy construction.
 	In	{\em Proceedings of  IJCAI-95},  1104-1111.
\item
        Boutilier, C., \& Poole, D. (1996).  Computing optimal
        policies for partially observable decision processes using
        compact representations.  In      {\em Proceedings of
		 AAAI-96},  1168-1175.




\item
        Brafman, R. I. (1997). A heuristic variable grid solution method for
        POMDPs.  In      {\em Proceedings of AAAI-97},  727-733. 

\item
Cassandra, A. R. (1994). Optimal polices for partially observable Markov
        decision processes. TR CS-94-14, Department of Computer Science,
        Brown University, Providence, Rhode Island 02912, USA.



\item Cassandra, A. R.,  Kaelbling, L. P., \& Littman, M. L. (1994).
	Acting optimally in partially observable stochastic domains.
 	 In      {\em Proceedings of	AAAI-94}, 1023-1028.

 

\item 
Cassandra, A. R.,  Kaelbling, L. P., \& Kurien, J. (1996).  
	Acting under uncertainty: Discrete Bayesian models for mobile-robot
	navigation. 
	 In      {\em Proceedings of IEEE/Robotics Society of Japan Conference on Intelligent
	Robotics and Systems (IROS-96)}.




\item
        Cassandra, A. R., Littman, M. L., \& Zhang, N. L. (1997).
        Incremental pruning: A simple, fast, exact method for
        partially observable Markov decision processes. 
           In      {\em Proceedings  of Thirteenth Conference
        on Uncertainty in Artificial Intelligence},
         54-61.

\item Cheng, H. T. (1988). Algorithms for partially observable Markov
	decision processes. PhD thesis, University of British Columbia,
	Vancouver, BC, Canada.


\item
        Dean, T. L., Givan, R., \& Leach, S. (1997).
		 Model reduction techniques for
        computing approximately optimal solution for Markov decision 
	processes.
	 In      {\em Proceedings of the Thirteenth Conference
        on Uncertainty in Artificial Intelligence},
        124-131.

\item	Dean, T. L., Kaelbling, L. P.,  Kirman, J., \& 
                Nicholson A. (1993).
        Planning with deadlines in stochastic domains.
		 In      {\em Proceedings of AAAI-93},
         574-579.

\item
        Dean T. L., \&  Lin, S. H. (1995). Decomposition techniques for
        planning in stochastic domains. 
         TR CS-95-10, Department of Computer Science,
        Brown University, Providence, Rhode Island 02912, USA.





\item  Dean, T. L.,   \& Wellman, M. P. (1991). {\em
	Planning and Control}. Morgan Kaufmann.


\item 
	Eagle, J. N. (1984). The optimal search for a moving target
	when the search path is constrained. {\em Operations Research},
	32(5),  1107-1115.  

\item
        Hauskrecht, M. (1997). Incremental methods for computing bounds
        in partially observable Markov decision processes.
          In      {\em Proceedings of AAAI-97},  734-739.


\item{} Littman, M. L. (1994). The witness algorithm: Solving
	 partially observable Markov
	decision processes. TR CS-94-40, Department of Computer Science,
	Brown University, Providence, Rhode Island 02912, USA.


\item
	 Littman, M. L.,  Cassandra, A. R., \& Kaelbling, L. P. (1995).
	Efficient dynamic-programming updates in partially observable
	Markov decision processes. 
	TR CS-95-19, Department of Computer Science,
	Brown University, Providence, Rhode Island 02912, USA.

\item   Lovejoy, W. S. (1991a). A survey of algorithmic methods for solving
	partially observable Markov decision processes. {\em Annals of Operations
	Research}, 28 (1),  47-65.


\item          Lovejoy, W. S. (1991b). Computationally
	feasible bounds for partially observed Markov
	decision processes. {\em Operations Research},
		39 (1),  162-175.



\item  Monahan, G. E. (1982). A survey of partially observable Markov decision processes: theory,
	models, and algorithms. {\em Management Science}, 28 (1),  1-16.



\item Parr, R., \& Russell, S. (1995). 
	Approximating optimal polices for partially
	observable stochastic domains.  
		 In      {\em Proceedings of  IJCAI-95},
	 1088-1094.


\item Platzman, L. K. (1977). Finite-memory estimation and
	control of finite probabilistic systems.
	Ph.D. Thesis, Department of Electrical Engineering and
	Computer Science, Massachusetts Institute of Technology.


\item Puterman, M. L. (1990). Markov decision processes. 
	In D. P. Heyman and M. J. Sobel (eds.), {\em  Handbooks in OR \& MS.},
	Elsevier Science Publishers,
	 Vol. 2, 331-434.


\item  Sondik, E. J. (1971). The optimal control of partially observable
	Markov processes. PhD thesis, Stanford University, Stanford,
	California, USA.


\item Sondik, E. J., \& Mendelssohn, R. (1979). 
	Information seeking in Markov decision processes,
	Southwest Fisheries Center  Administrative Report
	H-79-13, National Marine Fisheries Service,
	Honolulu, Hawaii.

 
\item 
	White III, C. C. (1991). Partially observed Markov decision processes: 
	A survey.  {\em Annals of Operations Research}, 32. 


\item White, D. J. (1993).
        {\em Markov Decision Processes}.
        John Wiley \& Sons.

\item  White III, C. C., \&   Scherer, W. T., (1994).
	Finite-memory suboptimal design  for partially observed Markov
	decision processes.
	{\em Operations Research}, 42(3),  440-455.


\end{description}


\end{document}
