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

\jairheading{23}{2005}{123-165}{10/03}{2/05}
\ShortHeadings{Restricted Value Iteration: Theory and
Algorithms}{Zhang \& Zhang} \firstpageno{123}

% The amssymb package provides various useful mathematical symbols
%\usepackage{amssymb}

\input{mylatexcommand.tex}

\begin{document}

\title{Restricted Value Iteration: Theory and Algorithms}

\author{\name Weihong Zhang \email wzhang@cs.wustl.edu \\
        \addr Department of Computer Science \\ Washington University,
                Saint Louis, MO 63130 USA
                \AND
 \name Nevin L. Zhang \email lzhang@cs.ust.hk \\
\addr  Department of Computer Science \\
Hong Kong University of Science \& Technology \\
Clear Water Bay Road, Kowloon, Hong Kong, CHINA
}

\maketitle

%\tableofcontents

\begin{abstract}
Value iteration is a popular algorithm for finding near optimal
policies for POMDPs.  It is inefficient due to the need to
account for the entire belief space, which necessitates the solution
of large numbers of linear programs.  In this paper, we
study value iteration restricted to belief subsets. We show
that, together with properly chosen belief subsets, restricted
value iteration yields near-optimal policies and we give a condition
for determining whether a given belief subset would bring about
savings in space and time. We also apply restricted value iteration
to two interesting classes of POMDPs, namely informative POMDPs
and near-discernible POMDPs.
\end{abstract}

%\newpage

\section{Introduction}

Partially Observable Markov Decision Processes (POMDPs) provide a
general framework for sequential decision-making tasks where the
effects of an agent's actions are nondeterministic and the states
of the world or environment are not known with certainty. Due to
the model generality, POMDPs have found a variety of potential
applications in reality \cite{Monahan82,Cass98b}. However, solving
POMDPs is computationally intractable. Extensive efforts have been
devoted to developing efficient algorithms for finding solutions
to POMDPs \cite{PR95,CLZ97,Cass98a,Hansen98,ZhangW01}.

Value iteration is a popular algorithm for solving POMDPs. Two
central concepts in value iteration are {\em belief state} and
{\em value function}. A belief state, a probability distribution
over the state space, measures the probability that the
environment is in each state. All possible belief states
constitute a {\em belief space}. A value function specifies a
payoff or cost for each belief state in the belief space. Value
iteration proceeds in an iterative fashion. Each iteration,
referred to as a {\em dynamic programming} (DP) update, computes a
new value function from the current one. When the algorithm
terminates, the final value function is used for the agent's
action selection. Value iteration is computationally expensive
because, at each iteration, it updates the current value function
over the entire belief space, which necessitates the solution of a
large number of linear programs.

One generic strategy to accelerate value iteration is to restrict
value iteration, that is, DP updates, to a subset of the belief
space. For simplicity, a subset of the belief space is referred to
as {\em belief subset}. Existing value iteration algorithms
working with belief subsets include a family of grid-based
algorithms where DP updates calculate values for a finite grid
\cite{Love91b,Ha97,ZH01}, and several (maybe anytime) algorithms
where DP updates calculate values for a growing belief subset
\cite{DKKN93,Wash97,HZ98,Hansen98,BG2000}. By restricting value
iteration into a belief subset, the complexity of value functions
is reduced and also DP updates are more efficient. These
advantages have been observed by several researchers
\cite{HF98,RG02,ZZ01a,PGT2004}.

A fundamental issue in restricted value iteration is how to select
a belief subset. The efficiency of value iteration and the quality
of its generated value functions strongly depend on the selected
belief subset. In one extreme case, if the subset is chosen to be
a singleton set, value iteration is efficient, but the quality of
value functions can be arbitrarily poor. In the other extreme
case, if the subset is the belief space, the quality of value
functions is retained, but the algorithm is inefficient. There
exists a tradeoff between the size of the belief subset and the
quality of value functions.

In this paper, we show that it is indeed possible for value
iteration to not only work with a belief subset but also retain
the quality of value functions. This is achieved by deliberately
selecting a belief subset for value iteration. Sometimes, we refer
to the algorithm working with our selected belief subset as {\em
subset value iteration}. (For distinction, {\em restricted value
iteration} refers to value iteration working with any belief
subset.) The efficiency of subset value iteration depends on the
size of the selected subset. We characterize a condition to {\em a
priori} determine whether the subset is proper \footnote{ Set $A$
is a {\em proper} subset of set $B$ if (1) $A$ is a subset of $B$,
and (2) there exists at least one element in $B$ such that it does
not belong to $A$.} with respect to the belief space for a given
POMDP. If this is the case, subset value iteration carries the
space and time advantages.

We also study two special POMDP classes, namely informative POMDPs
and near-discernible POMDPs. An informative POMDP assumes that an
agent has a good albeit imperfect idea about world states at any
time point. For an informative POMDP, there exists a natural
belief subset so that value iteration restricted to it can be more
efficient than standard value iteration \cite{ZL97}. A
near-discernible POMDP assumes that an agent has a good idea about
world states once in a while. For a near-discernible POMDP, we
propose a restricted value iteration algorithm that starts with a
small belief subset and grows it gradually. The algorithm
terminates as a proper tradeoff between size of the subset and
policy quality is found. Because of near-discernibility, the
algorithm is able to find a good tradeoff before the subset grows
too large.

The algorithms developed in this paper have been tested in a
variety of small maze problems designed to possess various
properties as desired, and a number of problems adapted from
existing research or created from our office environment. Our
results show that by exploiting problem characteristics,
restricted value iterations can solve larger POMDPs than standard
value iteration. We show how the algorithmic performances vary
with the properties of the selected belief subset for the maze
problems. These small problems facilitate exposition of the
properties of the chosen belief subsets. Meanwhile, the
experiments provide clues on which POMDP classes are amenable to
perspective algorithms.

The rest of the paper is organized as follows. In the next
section, we introduce the POMDP model and value iteration. In the
two subsequent sections, we present our subset value iteration
algorithm and analyze its theoretical properties. In particular,
in Section \ref{s:ssSelection}, we show how to select the belief
subset and how the selected subset is related to the belief space.
In Section \ref{s:ssVI}, we describe the subset value iteration
algorithm and discuss why it is able to achieve near optimality.
In Section \ref{s:informPOMDP}, we examine informative POMDPs and
show how the algorithm that exploits the informativeness is
related to the general subset value iteration \cite{ZL97}. In
Section \ref{s:discernPOMDP}, we examine near-discernible POMDPs
and develop an anytime algorithm. We empirically demonstrate that
the algorithm is able to compute value functions of high quality.
In Section \ref{s:relatedWork}, we survey related work to this
research.

\section{POMDPs and Value Iteration}
\label{s:pomdp}

This section gives a brief overview of the POMDP model and value
iteration.

\subsection{POMDPs}

A POMDP is a sequential decision model for an agent who acts in a
stochastic environment with only partial knowledge about the state
of its environment. The set of possible states of the environment
is  referred to as the {\em state space} and is denoted by $\sS$.
At each point in time, the environment is in one of the possible
states. The agent does not directly observe the state. Rather, it
receives an observation about it. We denote the set of all
possible observations as $\sZ$. After receiving the observation,
the agent chooses an action from a set $\sA$ of possible actions
and executes that action. Thereafter, the agent receives an
immediate reward   and the environment evolves stochastically into
a next state.

Mathematically, a POMDP is specified by: three sets $\sS$, $\sZ$,
and $\sA$; a {\em reward function} $r(s,a)$ for $s$ in $\sS$ and
$a$ in $\sA$; a {\em transition probability function} $P(s'|s,
a)$; and an {\em observation probability function} $P(z|s', a)$
for $z$ in $\sZ$ and $\ns$ in $\sS$. The reward function
characterizes the dependency of the immediate reward on the
current state $s$ and the current action $a$. The transition
probability characterizes the dependency of the next state $s'$ on
the current state $s$ and the current action $a$. The observation
probability characterizes the dependency of the observation $z$ at
the next time point on the next state $s'$ and the current action
$a$.

\subsection{Policies and Value Functions}

Since the current observation does not necessarily fully reveal
the identity of the current state, the agent needs to consider
all previous observations and  actions  when choosing an action.
Information about the current state contained in the current
observation, previous observations,  and  previous actions can be
summarized by a probability distribution over the state space
\cite{Ast65}. The probability distribution is sometimes called a
{\em belief state} and denoted by $b$. For any possible state $s$,
$b(s)$ is the probability that the current state is $s$. The set
of all possible belief states is called the {\em belief space}. We
denote it by $\sB$.

A {\em policy} prescribes an action for  each possible belief
state. In other words, it is a mapping from $\sB$ to $\sA$.
Associated with a policy $\pi$ is its {\em value function}
$V^{\pi}$. For each belief state $b$, $V^{\pi}(b)$ is the expected
total discounted reward that the agent receives by following the
policy starting from  $b$, i.e., $V^{\pi}(b)=E_{\pi,
b}[\sum_{t=0}^{\infty}\lam ^tr_t]$ where $r_t$ is the reward
received at time $t$ and $\lam$ ($0{\leq}\lam{<}1$) is the {\em
discount factor}. It is known that there exists a policy $\pi^*$
such that $V^{\pi^*}(b){\geq}V^{\pi}(b)$ for any other policy
$\pi$ and any belief state $b$ \cite{P94}. Such a policy is called
an {\em optimal policy}. The value function of an optimal policy
is called the {\em optimal value function}. We denote it by $V^*$.
For any positive number $\epsilon$, a policy $\pi$ is {\em
$\epsilon$-optimal} if $V^{\pi}(b)+\epsilon\geq V^\ast(b)$ for any
$b$ in $\sB$.

\subsection{Value Iteration}
\label{ss:ssectionVI}

To explain value iteration, we need to consider how the belief
state evolves over time. Let $b$ be the current belief state.  The
belief state at the next point in time is determined by the
current belief state, the current action $a$, the next observation
$\no$. We denote it by $\tau(b,a,z)$. For any state $s'$,
$\tau(b,a,z)$ is given by
\begin{eqnarray}
\label{e:beliefUpdate}
\tau(b,a,z)(\ns) =\frac{\sum_{s} P(\no, s'|s, a)b(s)}{P(\no|b, a)},
\end{eqnarray}

\noindent where $\pr{=}P(\no|\ns, a)P(\ns|s, a)$ and
$P(\no|b, a){=}\sum_{s, \ns}\pr b(s)$ is the renormalization
constant. As the notation suggests, the constant can also be
interpreted as the probability of observing $\no$ after taking
action $a$ in belief state $b$.

With the concept of belief state, a POMDP model can be
transformed into a {\em belief space MDP} as follows.
\begin{itemize}
\item
The state space is $\sB$ and the action space is $\sA$.
\item
Given a belief state $b$ and an action $a$, the transition model
specifies the transition probability as follows.
\begin{eqnarray*}
P(b'|b,a)=\left\{
        \begin{array}{ll}
        P(z|b,a) & \mbox{if $b'=\tau(b,a,z)$ for some $z$,} \\
        0        & \mbox{otherwise.}
        \end{array}
\right .
\label{e:beliefTransition}
\end{eqnarray*}

\item
Given a belief state $b$ and action $a$, the reward model
specifies immediate reward $r(b,a)$ as
$r(b,a) = \sum_{s\in\sS}b(s)r(s,a)$.
\end{itemize}

Due to this reformulation, the task of solving a POMDP can be
accomplished by solving the reformulated MDP. It has been proven
that the reformulated MDP has a stationary optimal policy, which
can be found by stochastic dynamic programming
\cite{Bellman57,P94}.

Value iteration is a dynamic programming algorithm for finding
$\epsilon$-optimal policies for an MDP. It starts with an initial
value function $V_0$ and iterates using the following formula:
\begin{eqnarray}
\label{e:standardDPUpdate}
V_{n+1}(b) = \max_a[r(b, a) + \lam \sum_{\no}
   P(\no|b, a)V_n(\tau(b,a,z) )] \ \  \forall b \in {\sB}
\end{eqnarray}
where $V_n$ is referred to as the $n$th-{\em{}step value
function}. It is known that $V_n$ geometrically converges to $V^*$
as $n$ goes to infinity.

For a given value function $V$, a policy $\pi$ is  said to be
{\em $V$-improving} if
\begin{eqnarray}
\label{e:v-improve}
\pi(b) = \arg\max_a[r(b, a) + \lam \sum_{\no}
    P(\no|b, a)V(\tau(b,a,z))] \hspace{0.4cm}  \forall b \in\sB.
\end{eqnarray}

The following theorem tells one when to terminate value iteration
given a precision requirement $\epsilon$ \cite{P94}. The stopping
criterion depends on the quantity
$\max_{b\in\sB}|V_n(b)-V_{n-1}(b)|$, which is the maximum
difference between $V_n$ and $V_{n-1}$ over the belief space. The
quantity is often called {\em Bellman residual} between $V_n$ and
$V_{n-1}$ \cite{P94}.
\begin{theo}
\label{th:viStop}
If $\max_b|V_{n}(b)-V_{n-1}(b)|\le{\epsilon(1-\lam)}/(2\lam)$,
then the $V_{n-1}$-improving policy is $\epsilon$-optimal.
\end{theo}

Since there are infinitely many  belief states, value functions
cannot be explicitly represented. Fortunately, value functions
that one encounters in the process of value iteration admit
implicit finite representations \cite{Sondik71}.

\subsection{Technical and Notational Considerations}

For convenience, we view  functions over the  state space as
vectors of size $|\sS|$. We  use lower case Greek letters $\al$
and $\bt$ to refer to vectors and script letters $\sV$ and $\sU$
to refer to sets of vectors. In contrast, the upper case letters
$V$ and $U$ always refer to value functions, that is functions
over the belief space $\sB$.

A set $\sV$ of vectors {\em induces} a piecewise linear convex
value function (say $f$) as follows: $f(b) =\max_{\alpha \in \sV}
\al{\cdot}b$ for any $b$ in $\sB$ where $\al{\cdot}b$ is the inner
product of $\al$ and $b$. For convenience, we shall abuse notation
and use $\sV$ to denote both a set of vectors and the value
function induced by the set. Under this convention, the quantity
$f(b)$ can be written as $\sV(b)$.

A vector in a set is {\em useless} if its removal does not affect
the function that the set induces. It is {\em useful} otherwise. A
set of vectors is {\em minimal} if it contains no useless vectors.
Let $\al$ be a vector in set $\sV$. It is known that $\al$ is
useful if and only if there is at least one belief state $b$ such
that $ \alpha{\cdot}b>\alpha'{\cdot}b, \ \forall
\alpha'\in{{\sV}\backslash \{\alpha\} }$. Such a belief state is
called a {\em witness point} of $\al$ because it testifies to the
fact that $\al$ is useful \cite{KLC98}. To determine the
usefulness of a vector in a set, it is sufficient to solve one
linear program. To compute a minimal set for a given set $\sV$ of
vectors, it is sufficient to solve $|\sV|$ linear programs. The
procedure of computing a minimal set for a given set of vectors is
often referred to as {\em pruning} a set.

\subsection{Finite Representation of Value Functions and Value Iteration}

A value function $V$ is {\em represented} by a set of vectors if
it equals the value function induced by the set. When a value
function is representable by a finite set of vectors, there is a
unique minimal set that represents the function \cite{LCK95b}.

Sondik (1971) has shown that if a value function is representable
by a finite set of vectors, then so are the subsequent value
functions derived by DP updates. The process of obtaining the
minimal representation for $V_{n+1}$ from the minimal
representation of $\sV_n$ is usually referred to as {\em dynamic
programming (DP) update}.

In practice, value iteration for POMDPs is not carried out
directly in terms of value functions themselves. Rather,
it is carried out in terms of sets of vectors that represent
the value functions. One begins with an initial set of vectors
$\sV_0$ (often set to a zero-vector). At each iteration, one
performs a DP update on the previous minimal set $\sV_n$ of
vectors and obtains a new minimal set $\sV_{n+1}$ of vectors.
One continues until the Bellman residual $\max_b|\sV_{n+1}(b) -
\sV_n(b)|$, which is determined by solving a sequence of
linear programs, falls below a threshold.

\section{Belief Subset Selection}
\label{s:ssSelection}

In this section, we show how to select a belief subset for value
iteration. We describe a condition determining whether the
selected subset is proper w.r.t.\ the belief space. In addition,
we discuss the minimal representation of value functions w.r.t.\
the selected subset. In the next section, we develop the subset
value iteration algorithm and show why it is able to achieve near
optimality.

\subsection{Subset Selection}

Our belief subset selection rests on belief updating. Let the
agent's current belief be $b$. Its next belief state is
$\tau(b,a,z)$ if it performs action $a$ and receives observation
$z$. If we vary the belief state $b$ in the belief space $\sB$, we
obtain a set $\{ \tau(b,a,z) | b\in\sB\}$. Abusing our notation,
we denote this set by $\tsimplex$. In words, no matter which
belief state the agent starts with, if it receives $z$ after
performing $a$, its next belief state must be in $\tsimplex$.

The union $\cup_{a,z}\tsimplex$ takes into account the sets of
belief states for all possible combinations of actions and
observations. It contains all the belief states that the agent can
encounter. In other words, the agent's belief state at any time
point must belong to this set regardless of its initial belief
state, performed actions and received observations. We denote the
set by $\tspace$ or simply $\tsimspace$. It is a {\em closed} set
in the sense that no action can lead the agent to belief states
outside $\tsimspace$ if the agent starts with a belief state in
it. Furthermore, any belief subset between the set $\tsimspace$
and the belief space $\sB$ is closed.
\begin{lem}
\label{l:closedSSpace}
The set $\tsimspace$ is closed. Moreover, if $\tsimspace\subseteq
{\sB}'\subseteq\sB$, ${\sB}'$ is closed.
\end{lem}
As is apparent, the set $\tsimspace$ is a subset of the belief
space $\sB$. Its definition is an application of reachability
analysis \cite{BBG98,DKKN93}. Under the terminology in
reachability analysis, the subset $\tsimplex$ comprises the
one-step reachable belief states if the agent performs action $a$
and receives observation $z$, while the subset $\tsimspace$
comprises the one-step reachable belief states regardless of
performed actions and received observations. Although the belief
subset $\tsimspace$ is the set of one-step reachable belief
states, an appealing property, to be shown in the next subsection,
is that  value iteration working with it can preserve the quality
of the generated value functions.

\subsection{Subset Representation}
\label{ss:representation}

Subset representation addresses how to represent the subsets
$\tsimplex$ and $\tsimspace$. For this, we introduce the concept
of belief simplex.
\begin{defi}
Let $B=\{b_1,b_2, ...,b_k\}$ be a set of belief states. A {\em
belief simplex $\Psi$ generated by $B$} is the set of belief
states $\{ \sum^k_{i=1}\lam_ib_i | \lam_i\ge 0 \mbox{ and }
\sum^k_{i=1}\lam_i=1.0 \}$. \label{d:simplex}
\end{defi}
\noindent The set $B$ is said to be a {\em basis} of the belief
simplex $\Psi$. From the definition, the belief simplex (or simply
{\em simplex}) is the set of convex combinations of the belief
states in the basis. Following the standard terms in linear
algebra, we can also talk about the {\em minimum basis} of a
simplex. For convenience, we use notation $B_{\Psi}$ to denote a
basis of a given simplex $\Psi$. Additionally, the simplex with
the basis $\{b_1,b_2,\cdots,b_k\}$ is denoted by
$\Psi(b_1,b_2,\cdots,b_k)$.

Our result is that for any $a$ and $z$, the subset $\tsimplex$ is
a simplex. The intuition follows. Let the number of states in a
POMDP be $n$. For each $i\in\{1,2,\ldots,n\}$, $b_i$ is a unit
vector, i.e., $b_i(s)$ equals 1.0 for $s=i$ and 0.0 otherwise. For
belief state $b_i$, if $P(z|b_i,a)>0$, $\tau(b_i,a,z)$ is a belief
state in $\tsimplex$; if $P(z|b_i,a)=0$, by the belief update
equation $\tau(b_i,a,z)$ is undefined. In the belief space $\sB$,
it is trivial to note that any belief state can be represented as
a convex combination of belief states in $\{b_1,b_2,\cdots,b_n\}$.
Correspondingly, in the belief subset $\tsimplex$, any belief
state can be represented as a convex combination of belief states
in $\{\tau(b_i,a,z)|P(z|b_i,a)>0\}$. Hence,
$\{\tau(b_i,a,z)|P(z|b_i,a)>0\}$ is a basis of $\tsimplex$. For
convenience, we denote such a basis by $B_\tsimplex$.
\begin{theo}
\label{th:sspace}
For any pair $[a,z]$, the subset $\tsimplex$ is a simplex.
\end{theo}
\noindent {\bf Proof:} See Appendix \ref{s:app.proofs}. \qed

By the above theorem, the subset $\tsimspace$ is a union of
simplices. Although the subset $\tsimspace$ is not linearly
representable in its own, it is the union of linearly
representable sets. Later in the section, this property is crucial
to and will be exploited in finding the minimal representing sets
of value functions w.r.t.\ the belief subset $\tsimspace$.

To concretize the ideas on subset representation, we give a POMDP
example and visualize the simplices for actions and observations.
Before presenting the example, we mention that we shall use it for
additional purposes later on in this paper. First, we shall use it
to show the difference between two conditions determining whether
the subset $\tsimspace$ is a proper subset of the belief space.
Second, we shall use it to demonstrate the fundamental differences
between two restricted value iteration algorithms.

\noindent {\bf Example} The POMDP has three states
$\{s_1,s_2,s_3\}$, two actions $\{a_1,a_2\}$ and two observations
$\{z_1,z_2\}$. We define the transition and observation model for
action $a_1$. These models for $a_2$ can be defined similarly. To
shorten notations, we use $p_{ij}$ to denote the transition
probability $P(s_j|s_i,a_1)$ and $q_{ij}$ to denote the
observation probability $P(z_j|s_i,a_1)$. We assume that (1) for
any state $s_i$, the probability $p_{i1}$ is equal to $p_{i2}$,
i.e., $p_{i1}=p_{i2}$; (2) at each state $s_i$, observations $z_1$
and $z_2$ are received with the same probability, i.e.,
$q_{i1}=q_{i2}=0.5$ for each $i$; and (3) $p_{11}>p_{21}>p_{31}$.
Under these assumptions, the matrix
\begin{eqnarray}
P_{a_1z_1} = \left( \begin{tabular}{ccc}

$0.5p_{11}$      & $0.5p_{21}$      & $0.5p_{31}$ \\
$0.5p_{11}$      & $0.5p_{21}$      & $0.5p_{31}$ \\
$0.5(1-2p_{11})$ & $0.5(1-2p_{21})$ & $0.5(1-2p_{31})$

\end{tabular} \right). \label{e:Paz}
\end{eqnarray}
\noindent Because of the first assumption, the first two rows of
the matrix are the same. In the third row, the probability
$p_{i3}$ is replaced with $1-p_{i1}-p_{i2}$, i.e., $1-2p_{i1}$.

We compute the basis of the belief subset $\tau(\sB,a_1,z_1)$. Let
the basis of the belief space $\sB$ be the set $\{{(1.0,0,0)}^T,$
${(0,1.0,0)}^T,$ ${(0,0,1.0)}^T \}$. (For a matrix or vector $A$,
$A^T$ denotes its transpose.) For action $a_1$ and observation
$z_1$, the next belief states, denoted by $A_i$s, are:
\begin{eqnarray}
\begin{tabular}{ll}
$A_1$ & $=\tau({(1.0,0,0)}^T,a_1,z_1) =
{(p_{11},p_{11},1.0-2p_{11})}^T $
\\
$A_2$ & $=\tau({(0,1.0,0)}^T,a_1,z_1) =
{(p_{21},p_{21},1.0-2p_{21})}^T$
\\
$A_3$ & $=\tau({(0,0,1.0)}^T,a_1,z_1) = {(p_{31},p_{31},
1.0-2p_{31}) }^T$
\end{tabular}\label{e:nextBeliefs}
\end{eqnarray}

\noindent Interestingly, it can be shown that $A_2$ is a convex
combination of $A_1$ and $A_3$. In fact, in can be verified that
\begin{eqnarray*}
\tau({(0,1.0,0)}^T,a_1,z_1)=\lam_1\tau({(1.0,0,0)}^T,a_1,z_1)
+\lam_2\tau({(0,0,1.0)}^T,a_1,z_1)
\end{eqnarray*} where
$\lam_1=\frac{p_{21}-p_{31}}{p_{11}-p_{31}}$ and
$\lam_2=\frac{p_{11}-p_{21}}{p_{11}-p_{31}}$. Thus
$\lam_1+\lam_2=1.0$. Our third assumption ensures that $\lam_1$
and $\lam_2$ are greater than 0.0. Because $A_2$ is a convex
combination of $A_1$ and $A_3$, the three belief states $A_1$ to
$A_3$ lie in the same straight line.

Figure \ref{f:visualSimplex} visualizes the belief space $\sB$ in
the left and the simplex $\tau(\sB,a_1,z_1)$ in the right. The
right chart is based on these parameters: $p_{11}=0.5$,
$p_{21}=0.4$ and $p_{31}=0.1$. The belief states $A_i$s are the
following: $A_1={(0.5,0.5,0.0)}^T$, $A_2={(0.4,0.4,0.2)}^T$ and
$A_3={(0.1,0.1,0.8)}^T$. We see that the belief space is a
triangle area and the belief simplex is a line segment in that
area. In the next subsection, we shall return to this point and
show why.

\begin{figure}[htb]
\begin{center}
\makebox{
        \epsfxsize=8.5cm
        \epsffile{fig/visualSimplex.eps}
}
\end{center}
\caption{A graphical representation of belief space and belief
simplex. See text for explanations.} \label{f:visualSimplex}
\end{figure}

To show the belief subset $\tsimspace$, we continue to define the
transition and the observation models for action
$a_2$.\footnote{Other components of the POMDP do not affect our
discussions here and are omitted for convenience.} We may follow
the three assumptions for $a_1$ to define these models for $a_2$,
but give a different set of transition probabilities so that $a_2$
differs from $a_1$.

By the second assumption that observation $z_1$ and $z_2$ are
received with the same probability, the matrix $P_{a_i,z_1}$ is
identical to $P_{a_i,z_2}$ for $i\in\{1,2\}$. So, the simplex
$\tau(\sB,a_i,z_1)$ is identical to $\tau(\sB,a_i,z_2)$ for each
$i$. As such, the subset $\tsimspace$ consists of two line
segments in the entire belief space. \qed

\subsection{Belief Subset and Belief Space}
\label{ss:beliefSubset}

We discuss the relationship between the set $\tsimspace$ and the
belief space $\sB$. Since the set $\tsimspace$ is a union of
simplices, it helps to show how each simplex $\tsimplex$ is
related to the belief space $\sB$. For an action $a$ and
observation $z$, it turns out that a matrix derived from the
transition and observation models plays a central role in
determining the simplex. Such a matrix, denoted by $P_{az}$, is of
dimension $|\sS|\times|\sS|$ and its entry at $(s,\ns)$ is the
joint probability $P(\ns,z|s,a)$, i.e.,
\begin{eqnarray*}
P_{az} =
\left(
\begin{tabular}{cccc}
$P(s'_1,z|s_1,a)$ & $P(s'_1,z|s_2,a)$ & $\cdots$  & $P(s'_1,z|s_n,a)$ \\
$P(s'_2,z|s_1,a)$ & $P(s'_2,z|s_2,a)$ & $\cdots$  & $P(s'_2,z|s_n,a)$ \\
$\cdots$ & $\cdots$ & $\cdots$ & $\cdots$ \\
$P(s'_n,z|s_1,a)$ & $P(s'_n,z|s_2,a)$ & $\cdots$ & $P(s'_n,z|s_n,a)$
\end{tabular}
\right).
\end{eqnarray*}
The matrix can be used to relate the next belief $\tau(b,a,z)$ and
the current $b$. If $b$ and $\tau(b,a,z)$ are viewed in column
vector form, the belief update Equation (\ref{e:beliefUpdate}) can
be rewritten as $\tau(b,a,z)=\frac{1}{p(z|b,a)}P_{az}b$. Hence,
$\tau(b,a,z)$ is a transformation of $b$ and the matrix $P_{az}$
is called the {\em transformational matrix}. The following lemma
characterizes a condition under which the simplex $\tsimplex$ is
the same as the belief space $\sB$.
\begin{lem}
\label{l:tsimplexandB} For any $[a,z]$, there exists a bijection
between the simplex $\tsimplex$ and the space $\sB$ if the matrix
$P_{az}$ is invertible \footnote{A matrix is invertible if its
determinant is non-zero. It is degenerate otherwise.}.
\end{lem}
This can be seen from the fact
$\tau(b,a,z)=\frac{1}{p(z|b,a)}P_{az}b$ and $\tsimplex$ is the set
of the transformed belief states from the belief space.
Consequently, the simplex $\tsimplex$ is a {\em proper} subset of
$\sB$ if the matrix $P_{az}$ is degenerate. We note that the
matrix $P_{az}$ is degenerate if there exists a state $\ns$ such
that $P(z|\ns,a)=0.0$, i.e., there is a state such that the agent
can never receive the observation $z$ (if action $a$ is
performed). This is because all the entries in the row
corresponding to $\ns$ are 0.0 in the matrix. In this case, by the
lemma, the set $\tsimplex$ must be a proper subset of the belief
space $\sB$.
\begin{cor}
\label{cor:informativeSimplex}
If there is a state $s$ such that $P(z|s,a)=0.0$, the set
$\tsimplex$ is a proper subset of the belief space $\sB$.
\end{cor}
However, that $\tsimplex$ is a proper subset does not necessarily
imply that there exists a state $s$ such that $P(z|s,a)=0.0$.
Consequently, to determine if a belief simplex is proper, the
above corollary provides a sufficient condition; in contrast,
Lemma \ref{l:tsimplexandB} provides a sufficient and necessary
condition. This will be illustrated by continuing our discussions
on the POMDP example.

\

\noindent {\bf Example (Continued)} We consider the simplex
$\tau(\sB,a_1,z_1)$. By the second assumption, $z_1$ can be
observed at any state. So, there does not exist a state $s$ such
that $P(z_1|s,a_1)=0.0$. On the other hand, the matrix
$P_{a_1z_1}$ is degenerate because it has the same two rows. By
Lemma \ref{l:tsimplexandB}, the simplex $\tau(\sB,a_1,z_1)$ is a
proper set of the belief space. In fact, as seen in Figure
\ref{f:visualSimplex}, it is a line segment, which can be viewed
as a degenerate belief space. \qed

We proceed to discover the relationship between the belief set
$\tau(\sB,a,z)$ and the belief space $\sB$. Since $\tau(\sB,a,z)$
is the union of the simplices $\tsimplex$, it is a proper subset
of the belief space if so is each simplex. In turn, this requires
that each transformational matrix is degenerate.
\begin{theo}
\label{th:tspaceandB} The subset $\tsimspace$ is a proper subset
of belief space $\sB$ only if the transformational matrices for
all actions and observations are degenerate.
\end{theo}

\subsection{Subset Value Functions}

We discuss value functions whose domains are belief subset
$\tsimplex$ or $\tsimspace$. For simplicity, we refer to them as
{\em subset value functions}. The problem we will examine is,
given a set of vectors representing a subset value function, how
to compute a minimal set w.r.t.\ a belief subset. We first
consider the case where the subset is a simplex.

In order to calculate a minimal set of vectors, one needs to
determine the usefulness of a vector in a set w.r.t.\ the simplex.
Let $\beta$ be a vector in set $\sV$ and the simplex be
$\tsimplex$. The vector $\beta$ is useful w.r.t.\ $\tsimplex$ if
and only if there is a belief state $b$ in the simplex such that
$\beta\cdot{b}\ge\alpha\cdot{b}+x$ where $x$ is a sufficiently
small positive number and $\alpha$ is a vector in the set
$\sV{-}\{\beta\}$. Moreover, if such a belief state $b$ exists,
since it is in the simplex, $b$ must be representable by the
belief states in the basis $B_\tsimplex$, i.e.,
$b=\sum_i\lam_i\tau(b_i,a,z)$. If we replace $b$ by
$\sum_i\lam_i\tau(b_i,a,z)$ in $\beta\cdot{b}\ge\alpha\cdot{b}+x$,
the condition of determining  $\beta$'s usefulness is equivalent
to this: whether there exists a series of nonnegative numbers
$\lam_i$s such that for any vector $\alpha$ in $\sV$,
\begin{eqnarray*}
\beta\cdot\sum_i\lam_i\tau(b_i,a,z)\ge
\alpha\cdot\sum_i\lam_i\tau(b_i,a,z)+x.
\end{eqnarray*}
Rewriting the above inequality, we have
\begin{eqnarray}
\label{e:tsLP}
\sum_i\left[ \beta\cdot\tau(b_i,a,z)  \right] \lam_i\ge
\sum_i\left[ \alpha\cdot\tau(b_i,a,z)   \right] \lam_i+x.
\end{eqnarray}

To determine $\beta$'s usefulness, the procedure
$\verb+simplexLP+$ in Table \ref{t:simplexPrune} is used. When the
optimality of the linear program is reached, one checks its
objective $x$. If it is positive, there exists a belief state in
belief simplex $\tsimplex$ such that at this belief state $\beta$
dominates other vectors. The belief state is a witness point of
$\beta$. It is represented as $\sum_i\lam_i\tau(b_i,a,z)$ where
$\lam_i$s are the solutions (values of variables) of the linear
program. In this case, the belief state
$\sum_i\lam_i\tau(b_i,a,z)$ is returned. For other cases, no
belief state is returned and $\beta$ is a useless vector.

\begin{table}[htb]
\begin{center}
   \begin{tabbing}
    xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=  \kill
    \>$\verb+simplexLP+(\beta, \sV, B_\tsimplex)$: \\
    \>1.\>  Variables: $x$, $\lam_i$ for each $i$ \\
    \>2.\>       Maximize: $x$. \\
    \>3. \>      Constraints:             \\
    \>4.\> \>
$\sum_i\left[ \beta\cdot\tau(b_i,a,z)  \right] \lam_i\ge
\sum_i\left[ \alpha\cdot\tau(b_i,a,z)   \right] \lam_i+x
$ for $\forall\alpha\in\ \sV-\{\beta\}$ \\
    \>\>\>\> and for each $i$, $\tau(b_i,a,z)\in{B_\tsimplex}$ \\
    \>5. \>\>     $\sum_i\lam_i = 1$, $\lam_i\geq 0$ for $i$.
\> \ \ \\
\> \ \ \\
    \> $\verb+simplexPrune+(\sV, B_\tsimplex )$: \\
    \> 1.\> $\sU\la\sV,\ \sV\la\emptyset$ \\
    \> 2.\> {\bf For} each $\beta$ in $\sU$ \\
    \> 3.\>\> $b\la\verb+simplexLP+(\beta,\sU,B_\tsimplex )$ \\
    \> 4.\>\> {\bf If} $b\not=\verb+null+$ \\
    \> 5.\>\>\> $\sV\la\sV\cup\{\beta\}$ \\
    \> 6.\> {\bf Return} $\sV$
\end{tabbing}
\end{center}
\caption{The procedure to compute the minimal set of vectors over
a simplex} \label{t:simplexPrune}
\end{table}

To determine a vector's usefulness in a given set, one linear
program needs to be solved. If a vector is useless, its removal
does not change the value function that the set induces.
Therefore, to compute a minimal set for a given set $\sV$ w.r.t.\
a simplex, one needs to solve $|\sV|$ linear programs.

This procedure is implemented in $\verb+simplexPrune+$ of Table
\ref{t:simplexPrune}. Its input has two arguments: a set of
vectors $\sV$ \footnote{For simplicity, we assume that the set
$\sV$ does not contain duplicate vectors. Duplicates can be
removed by a simple componentwise check.} and a basis of the
simplex $B_\tsimplex$. A set $\sU$ is initialized to be the set
$\sV$ and the set $\sV$ to be empty at line 1. Useful vectors are
added to the set $\sV$ in the sequel. For each vector in set
$\sU$, at line 3 the procedure $\verb+simplexLP+$ is called to
determine its uselessness. If it returns a belief state, the
vector is added to the set $\sV$ at line 5. Eventually, the set
$\sV$ becomes the minimal representation of $\sU$ w.r.t.\ simplex
$\tsimplex$.

\

To compute a minimal set of vectors w.r.t.\ the subset
$\tsimspace$, one needs to determine a vector's usefulness w.r.t.\
the subset. In turn, one needs to determine its usefulness w.r.t.\
each simplex. Again, let the set be $\sV$ and the vector be
$\beta$. If $\beta$ is useful w.r.t.\ a simplex, it must be useful
w.r.t.\ the subset. However, if it is useless w.r.t.\ a simplex,
it may be useful w.r.t.\ another simplex. Hence, for a simplex, if
$\beta$ has been identified as useful, there is no need to check
it again for subsequent simplices. After all the simplices have
been examined, if $\beta$ is useless w.r.t.\ all simplices, it is
useless w.r.t.\ the subset. By removing all useless vectors
w.r.t.\ the subset, one obtains the minimal set.

\section{Subset Value Iteration}
\label{s:ssVI}

In this section, we first describe the value iteration algorithm
in belief subset $\tsimspace$. We then show that the algorithm
is able to achieve near optimality. Finally, we analyze its
complexity and report empirical studies.

\subsection{Belief Subset MDP}

Because the subset $\tsimspace$ is closed, we are able to define a
so-called {\em belief subset MDP} (or simply {\em subset MDP}).
Its state space is the chosen subset $\tsimspace$ and other
components are the same as those in the MDP transformed from the
original POMDP (Section \ref{ss:ssectionVI}). The only difference
between the two MDPs lies in their state spaces: the state space
of the belief subset MDP is a subset of the state space of the
belief space MDP.

\subsection{Subset DP Updates}
\label{ss:ssDPUpdate}

By MDP theory, the subset MDP admits the following DP update
equation where $V^\tsimspace_n$ represents its $n$th-step
value function.
\begin{eqnarray}
V^\tsimspace_{n+1}(b) = \max_a \{ r(b,a) +\lam\sum_z P(z|b,a)
    V^\tsimspace_n(\tau(b,a,z)) \}
\ \ \forall b\in\tsimspace.
\label{e:dpuSSpace}
\end{eqnarray}
Following the equation, an implicit DP update computes the
minimal set $\sV^\tsimspace_{n+1}$ representing value function
$V^\tsimspace_{n+1}$ from $\sV^\tsimspace_n$ representing
$V^\tsimspace_n$. Note that the domains of value functions
are belief subset $\tsimspace$. For simplicity, such a step
is called {\em subset DP update}.

Implicit subset DP updates can be carried out as standard DP
updates. Here, we present a two-pass algorithm due to its
conceptual simplicity \cite{Monahan82}. It constructs the next set
of vectors in two steps -- an enumeration step enumerating all
possible vectors and a reduction step removing useless vectors. In
the following, we focus on the enumeration step. For the reduction
step, since the usefulness of a vector is w.r.t.\ the subset
$\tsimspace$, the techniques in the preceding section can be used.

Given a set $\sV^\tsimspace_n$, a vector in the representing set
of $V^\tsimspace_{n+1}$ can be defined by a pair of action and a
mapping from the set $\sZ$ of observations to the set
$\sV^\tsimspace_n$. To be precise, for an action $a$ and a mapping
$\delta$, a vector, denoted by $\beta_{a,\delta}$, is defined as
follows \footnote{ The procedure of defining a vector actually
constructs an $(n{+}1)$th-step policy tree. (See, e.g., Zhang and
Liu 1997, for details.) }. For each $s\in\sS$,
\begin{eqnarray}
\beta_{a,\delta}(s)=r(s,a)+\lam\sum_z\sum_\ns
P(\ns|s,a)P(z|\ns,a)\delta_z(\ns)
\label{e:beta-tspace}
\end{eqnarray}
where $\delta_z$ is the mapped vector for observation $z$.

If we enumerate all possible combinations of actions and
mappings above, we can define various vectors. These
vectors form a set
\begin{eqnarray}
\label{e:beta-set-subset}
\{\beta_{a,\delta}|
a\in\sA, \delta:\sZ\to\sV^\tsimspace_n
    \ \&\ \forall z,\delta_z\in\sV^\tsimspace_n\}.
\end{eqnarray}
The set is denoted by $\sV^\tsimspace_{n+1}$. By MDP theory,
it represents the value function $V^\tsimspace_{n+1}$ if
the set $\sV^\tsimspace_n$ represents $V^\tsimspace_n$.
\begin{lem}
The set $\sV^\tsimspace_{n+1}$ represents value function
$V^\tsimspace_{n+1}$ if $\sV^\tsimspace_n$ represents
$V^\tsimspace_n$.
\label{l:sameSubspaceVF}
\end{lem}

\

The above DP update works in a {\em collective} fashion in that it
directly computes value functions over $\tsimspace$. An
alternative way to conduct DP updates is to compute value
functions for individual simplices one by one. The rationale is
that, by letting a DP update work with the finer-grained belief
subsets, it could be more efficient than its collective version. A
DP update in an individual fashion constructs a collection
$\{\sV^\tsimplex_{n+1}\}$ of vector sets from a given collection
$\{\sV^\tsimplex_n|a\in\sA,z\in\sZ\}$ where each $\sV^\tsimplex_n$
represents $V^\tsimspace_n$ in the simplex $\tsimplex$. We
consider how to construct a set $\sV^{\tau(\sB,\na,\nz)}_{n+1}$
for one simplex $\tau(\sB,\na,\nz)$.

Likewise, a vector $\beta_{a,\delta}$ in
$\sV^{\tau(\sB,\na,\nz)}_{n+1}$ can be defined by an action $a$
and a mapping $\delta$. The fact that $\tau(b,a,z)$ must be in
$\tau(\sB,a,z)$ for any $b$ implies that for any $z$, $\delta_z$
can be restricted to a vector in the set $\sV^{\tau(\sB,a,z)}_n$.
By altering actions and mappings, one obtains the following set:
\begin{eqnarray}
\label{e:beta-set-simplex}
\{\beta_{a,\delta}|
a\in\sA, \ \ \ \delta: \sZ\to\cup_{a,z}
      \sV^{\tau(\sB,a,z)}_n,
    \ \&\ \forall z,\delta_z\in\sV^{\tau(\sB,a,z)}_n\}.
\end{eqnarray}
It differs from (\ref{e:beta-tspace}) in that for an observation
$z$, the mapped vector by $\delta$ is restricted to the set
$\sV^{\tau(\sB,a,z)}_n$. The above set is denoted by
$\sV^{\tau(\sB,\na,\nz)}_{n+1}$. To obtain its minimal
representation, one removes useless vectors from the set w.r.t.\
the simplex $\tau(\sB,\na,\nz)$. The value function that the set
$\sV^{\tau(\sB,\na,\nz)}_{n+1}$ induces is equal to the value
function $V^{\tau(\sB)}_n$ in the belief simplex
$\tau(\sB,\na,\nz)$.
\begin{lem}
For any action $a$ and observation $z$, each set
$\sV^\tsimplex_{n+1}$ represents the same value function
$V^\tsimspace_{n+1}$ in the simplex $\tau(\sB,a,z)$ if each
$\sV^\tsimplex_n$ represents $V^\tsimspace_n$ in the same
simplex.
\label{l:sameSimplexVF}
\end{lem}

Although subset DP updates can be carried out either collectively
or individually, they are essentially equivalent in terms of value
functions induced.
\begin{theo}
\label{th:subspaceSimplexDPVF}
Let $\sU=\cup_{a,z}\sV^\tsimplex_{n+1}$. For any $b\in\tsimspace$,
$\sU(b)=\sV^\tsimspace_{n+1}(b)$.
\end{theo}

It is worthwhile to note that for two pairs of actions and
observations, the simplices $\tau(\sB,a_1,z_1)$ and
$\tau(\sB,a_2,z_2)$ might not be disjoint. A few remarks are in
order for this case. First, by Theorem \ref{l:sameSimplexVF}, for
any $b$ in the intersection of the simplices,
$\sV^{\tau(\sB,a_1,z_1)}_{n+1}(b)=\sV^{\tau(\sB,a_2,z_2)}_{
n+1}(b)$. This is because both sets represent $V^\tsimspace_{n+1}$
in $\tau(\sB)$. Second, if a subset DP update is carried out
individually, it may generate more vectors than its collective
version. This is because the two sets
$\sV^{\tau(\sB,a_1,z_1)}_{n+1}$ and
$\sV^{\tau(\sB,a_2,z_2)}_{n+1}$ may contain duplicate vectors.

Finally, we note that to achieve computational savings,
sophisticated algorithms for standard DP updates can be applied to
subset DP updates. Let us take incremental pruning, one of the
most efficient algorithms, as an example \cite{CLZ97,ZL97}. In
standard incremental pruning, all the pruning operations are
w.r.t.\ the belief space; however, when it is used in subset DP
updates, all the pruning operations are w.r.t.\ the belief
subsets.

\subsection{Analysis}
\label{ss:analysis}

We analyze several theoretical properties of the subset value
iteration algorithm. Our main results include: value functions
generated by subset value iteration are equivalent to those by
standard value iteration in some sense; to achieve near
optimality, value iteration needs to account for at least the
belief subset $\tau(\sB)$; the value function generated by subset
value iteration can be used for near optimal decision-making in
the entire belief space if the algorithm is appropriately
terminated.

\subsubsection{Belief Subset, Value Functions and Value Iterations}

Subset value iteration generates a series $\{V^\tsimspace_n\}$ of
value functions. If its initial value function $V^\tsimspace_0$
is the same as the initial $V_0$ of standard value iteration
in $\tsimspace$, subset value iteration generates the same series
of value functions as standard value iteration in $\tsimspace$.
\begin{theo}
\label{th:subspaceDPVF}
If $V^\tsimspace_0(b)=V_0(b)$ for any $b$ in $\tsimspace$,
then $V^\tsimspace_n(b)=V_n(b)$ for any $n$ and any $b$ in
$\tsimspace$.
\end{theo}

\noindent {\bf Proof:} We first consider one DP update computing
value function $V_{n+1}$ from the current $V_n$ by DP Equation
(\ref{e:standardDPUpdate}). In its right hand side, since
$\tau(b,a,z)$ must belong to the subset $\tsimspace$, the notation
$V_n(\tau(.,.,.))$ can be interpreted as a value function over
subset $\tsimspace$ rather than belief space $\sB$. Comparing DP
Equation (\ref{e:standardDPUpdate}) for the belief space $\sB$ and
Equation (\ref{e:dpuSSpace}) for belief subset $\tau(\sB)$, we see
that $V_{n+1}$ and $V^{\tau(\sB)}_{n+1}$ represent the same value
function in $\tau(\sB)$ if so do $V_n$ and $V^{\tau(\sB)}_n$.

The theorem is true for $n=0$ by the given condition. It  is true
for $n>0$ by induction. \qed

More interestingly, the value function $V^\tsimspace_n$ at step
$n$ can be used to derive the value function $V_{n+1}$ in standard
value iteration. To see why, we first note that a subset value
function $V^\tsimspace$ can be used to define a value function
(say $V$) by one-step lookahead operation as follows:
\begin{eqnarray}
\label{e:ssOptiVF}
V(b) = \max_a \{ r(b,a) + \lambda \sum_z P(z|b,a)
        V^\tsimspace(\tau(b,a,z)) \}
        \ \ \forall\ \ b\in\sB.
\end{eqnarray}
The so-defined $V$ is called $V^\tsimspace$-{\em improving} {\em
value function}. Second, comparing Equations (\ref{e:ssOptiVF})
and (\ref{e:standardDPUpdate}), we see that the
$V^\tsimspace_n$-improving value function is actually $V_{n+1}$ if
$V^\tsimspace_n$ is equal to $V_n$ in $\tsimspace$.

Consequently, although subset value iteration works with
$\tsimspace$, value functions generated in standard value
iteration can be derived. In this sense, we say $\tsimspace$ is a
{\em sufficient} belief subset since it enables subset value
iteration to preserve standard value functions without ``loss''.

Since subset value iteration retains the quality of value
functions, it can be regarded as an {\em exact} algorithm. One
interesting question is, if value iteration intends to retain
quality, can it work with a proper subset of $\tau(\sB)$? In
general, the answer is no. The reason follows. To compute
$V_{n+1}$, one needs to keep values $V^{\tau(\sB)}_n$ for belief
states in $\tau(\sB)$. Otherwise, if one accounts for a proper
subset $\sB'$ of $\tau(\sB)$, it can be proven that there exists a
belief state $b$ in $\sB$, an action $a$ and an observation $z$
such that $\tau(b,a,z)$ does not belong to $\sB'$. It's known that
the value update of $V_{n+1}(b)$ depends on the values for all
possible next belief states. Due to the unavailability of
$V^{\tau(\sB)}_n(\tau(b,a,z))$, the value $V_{n+1}(b)$ cannot be
calculated exactly. Consequently, if value iteration works with a
proper subset of $\tau(\sB)$, it cannot be exact. In other words,
it should be an {\em approximate} algorithm. To make it be exact,
value iteration needs consider at least $\tau(\sB)$. In this
sense, the subset $\tau(\sB)$ is said to be a {\em minimal}
sufficient set.

Informally we use Figure \ref{f:ssSubset} to illustrate the
relationship between belief subsets and value iteration. In the
figure, circles represent belief sets. The minimum belief subset
for value iteration to retain quality is $\tsimspace$, while the
maximum subset is the belief space $\sB$ itself. If value
iteration works with belief subset $\sB'$ (denoted by dashed
circles) between $\tsimspace$ and $\sB$, its quality is also
retained. However, if it works with a proper belief subset of
$\tsimspace$, in general it is unable to retain the quality of
value functions.

\begin{figure}[htb]
\begin{center}
\makebox{
        \epsfxsize=6cm
        \epsffile{fig/venn.eps}
}
\end{center}
\caption{The relationship between belief subsets and value
iteration} \label{f:ssSubset}
\end{figure}


\subsubsection{Stopping criterion and decision making}
\label{sss:stopping}

Subset value iteration starts with an initial value function. As
it continues, the Bellman residual $\max_{b\in\tsimspace}|
V^\tsimspace_n(b)-V^\tsimspace_{n-1}(b)|$, the maximum difference
between two value functions over the subset $\tsimspace$, must
become smaller. By MDP theory, if the quantity falls below
$\epsilon(1-\lam)/(2\lam)$, the value function
$\sV^\tsimspace_{n-1}$ is $\epsilon$-optimal w.r.t.\ the subset
MDP. In the following, we show that the $\epsilon$-optimality can
be extended to the entire belief space by appropriately
terminating the subset value iteration algorithm.

Let the output value function be $V^\tsimspace_{n-1}$. It can be
used to define a policy for any belief state in $\sB$ as in
Equation (\ref{e:v-improve}) where $V$ is replaced by
$V^\tsimspace_{n-1}$. The policy $\pi$ is said to be
$V^\tsimspace_{n-1}$-{\em improving}. Note that the policy
prescribes an action for any belief state in the belief space. The
following theorem tells one when to terminate subset value
iteration such that the $V^\tsimspace_{n-1}$-{\em improving}
policy is $\epsilon$-optimal over the belief space.
\begin{theo}
\label{th:strictThreshold}
If $\max_{b\in\tau(\sB)}|V^{\tau(\sB)}_{n}(b)-V^{\tau(\sB)}_{n-1}(b)|
\le {\epsilon(1-\lam)}/{(2{\lam}^2|\sZ|)}$,
then the $V^{\tau(\sB)}_{n-1}$-improving policy is $\epsilon$-optimal
over the entire belief space $\sB$.
\end{theo}

\noindent {\bf Proof: } See Appendix \ref{s:app.proofs}. \qed

This theorem is important for two reasons. First, although subset
value iteration outputs a subset value function,
$\epsilon$-optimal value functions over the entire space can be
induced by one-step lookahead operation. Second, it implies that
the $V^\tsimspace_{n-1}$-improving policy is $\epsilon$-optimal if
the condition is met. We know that $\tsimspace$ consists of all
possible belief states the agent encounters after the initial
belief state. However, we have no assumption about the initial
belief state. It may or may not belong to this set. The theorem
means that the agent is still able to select a near optimal action
for an initial belief state even if it is not in the subset. In
fact, the agent can always select near optimal action for any
belief state in the entire belief space.

Finally, we note that to guarantee the $\epsilon$-optimality, when
compared with the condition in Theorem \ref{th:viStop}, subset
value iteration uses a more restrictive condition. For
convenience, it is sometimes called a {\em strict stopping
criterion}. In contrast, the condition in standard value iteration
is called a {\em loose stopping criterion}.

\subsection{Complexity}

To put in use for a POMDP, the subset value iteration algorithm
would take two steps: determining if the algorithm can bring about
savings in time and then running the subset value iteration if it
can. The first step needs to compute $|\sA||\sZ|$ determinants
$|P_{az}|$. Since the complexity of computing $|P_{az}|$ is
${|\sS|}^3$, the first step has the complexity of
$O(|\sA||\sZ|{|\sS|}^3)$. This is the polynomial part of the
complexity of subset value iteration. The second step is much
harder than the first step. It is known that finding the optimal
policy for even a simplified finite horizon POMDP is
PSPACE-complete \cite{PT87,BRS96,LGM98}. Recently, it has been
proven that finding the optimal policy for an infinite-horizon
POMDP is incomputable \cite{MHC99}.

We compare the subset value iteration with standard value
iteration. Standard DP updates improve values for the space $\sB$,
while subset DP updates improve values for the subset
$\tsimspace$. If the initial set $\sV^\tsimspace_0$ is equal to
the initial set $\sV_0$ in standard value iteration, because
$\tsimspace$ is a subset of $\sB$, the vectors in
$\sV^\tsimspace_1$ must be in $\sV_1$, and $\sV^\tsimspace_1$ is a
subset of $\sV_1$. Inductively, $\sV^\tsimspace_n$ is a subset of
$\sV_n$ for any $n$. This analysis suggests two advantages of
subset value iteration if the subset $\tsimspace$ is a proper
subset of the belief space $\sB$. First, fewer vectors are needed
to represent a value function over a belief subset. This is the
representational advantage in space. For $\sV_{n+1}$, its size can
be as large as $|\sA|{|\sV_n|}^{|\sZ|}$. For
$\sV^\tsimspace_{n+1}$, its size can be as large as
$|\sA|{|\sV^\tsimspace_n|}^{|\sZ|}$. Clearly, subset DP update
generates fewer vectors. Second, fewer vectors means lesser degree
of time complexity since computing vectors needs to solve linear
programs. This is the computational advantage in time.

However, the advantages strongly depend upon the size of the
subset $\tsimspace$. If each simplex $\tsimplex$ is the same as
the belief space $\sB$ and DP updates are conducted in an
individual fashion, subset DP updates could be $|\sA||\sZ|$ times
slower than standard DP updates. This is the worst case
complexity. Fortunately, by discussions in the previous section
(Theorem \ref{th:tspaceandB}), we know that given a POMDP we are
able to determine whether the selected subset $\tau(\sB)$ is a
proper subset of the belief space before solving it.

Although Theorem \ref{th:tspaceandB} gives a condition to
determine when the subset value iteration is more efficient than
standard value iteration for a POMDP, it does not answer the
question that how much savings the algorithm can bring about,
which turns out to be a very difficult problem in theoretical
analysis. The difficulty lies in not only the size of the set
$\tau(\sB)$ but also the vectors representing the step and the
optimal value functions. Let us assume that $\tau(\sB)$ is a
proper subset of the belief space. We can imagine at least two
cases. In one case, if at each iteration the step value function
has very few useful vectors in the subset $\tau(\sB)$, the subset
value iteration can be very efficient. In the other case, if at
each iteration the step value function has all useful vectors in
the subset $\tau(\sB)$, subset value iteration has the same
complexity as standard value iteration in an asymptotic sense. In
general, given a POMDP, it is difficult to predict how these
vectors scatter around the belief subsets and the belief space.
Consequently, it is hard to predict how much saving the subset
value iteration algorithm can bring about for a POMDP without
solving it.


\subsection{Empirical Studies}
\label{ss:ssVIExp}

We present our empirical results on two variants of a designed
maze problem and the problems in a standard test-bed in this
subsection. Some common settings to all experiments in the paper
are as follows. The experiments are conducted on an UltraSparc II
machine with dual CPUs and 256MB of RAM. Our codes are written in
C and executed under a UNIX operating system Sola 2.6. When
solving linear programs, we use a commercial package CPLEX V6.0.
The discount factor is set at $0.95$ and round-off precision is
set at $10^{-6}$. When not stated otherwise, the quality
requirement $\epsilon$ is set to 0.01. We use incremental pruning
to compute representing sets of value functions over the belief
space or belief subsets.

We compare the performances of subset and standard value
iteration. For simplicity, we denote them respectively by
$\verb+ssVI+$ and $\verb+VI+$. At each iteration, we compare
$\verb+VI+$ and $\verb+ssVI+$ in two measures: sizes of sets
representing value functions and total time of DP updates.

\subsubsection{The Maze Problem}
\label{ss:ssVIMaze}

The maze problem is specified in Figure \ref{f:ssMaze}. There are
10 locations and the goal is location 9. A robot agent can execute
four ``move'' actions to change its position, optionally a
``look'' action to observe its surroundings and a ``declare''
action to announce its success of goal-attainment. The ``move''
actions can achieve their intended effects with probability 0.8,
but might have no effects with probability 0.1 (the agent's
position remains unchanged) or lead to overshooting with
probability 0.1. Moving against maze walls leaves the agent at its
original location. Other actions do not change the agent's
position. At each time point, the robot receives a ``null''
observation giving no useful information at all, or reads four
sensors so as to reason about its current position. Each sensor
informs the robot whether there is a wall or nothing along a
direction. In the figure thick lines stand for walls and thin
lines for nothing (open). For instance, if the agent is at
location 2, ideally a string ``owow'' (in the order of East,
South, West and North) is received. Specific parameters will be
instantiated in relevant empirical analysis. The robot is required
to maximize the infinite discounted sum of rewards.

\begin{figure}[htb]
\begin{center}
\makebox{
        \epsfxsize=5cm
        \epsffile{results/ssvi/inform/maze.xfig.eps}
}
\end{center}
\caption{A maze problem}
\label{f:ssMaze}
\end{figure}

Two variants of the above maze are designed to test $\verb+ssVI+$
and $\verb+VI+$. They are denoted by $\verb+maze1+$ and
$\verb+maze2+$. For $\verb+maze1+$, $\verb+ssVI+$ is more
efficient; for $\verb+maze2+$, $\verb+ssVI+$ is less efficient.

\

\noindent {\bf Case I: $\tsimspace\subset\sB$}

The $\verb+maze1+$ problem has a state space of 10 locations, an
action space of size 5 (four ``move'' and one $\verb+declare+$)
and an observation space of size 6 (strings of four letters). An
ideal string is received with certainty after any action is
performed. When the agent declares goal at location 9, it receives
a reward of 1 unit; if it does so at location 10, it receives a
reward of $-1$. Other combinations of actions and observations
lead to no reward.

We collect the results in Figure \ref{f:ssMazeExp}. The first
chart in the figure depicts the total time of DP updates in
log-scale for $\verb+VI+$ with the loose stopping criterion and
$\verb+ssVI+$ with the strict one (Section \ref{sss:stopping}). To
compute a 0.01-optimal value function, $\verb+VI+$ took 20,000
seconds after 162 iterations while $\verb+ssVI+$ with strict
stopping criterion took 900 seconds after 197 iterations. We note
that $\verb+ssVI+$ needs more iterations but it still takes much
less time. The performance difference is big. Moreover, more
iterations means that the value function generated by
$\verb+ssVI+$ is closer to optimality.

\begin{figure}[htb]
\begin{center}
\begin{tabular}{ll}
\makebox{
        \epsfxsize=6.5cm
        \epsffile{results/ssvi/inform/logtime.eps}
}
&
\makebox{
        \epsfxsize=6.5cm
        \epsffile{results/ssvi/inform/logsize.eps}
}
\end{tabular}
\end{center}
\caption{Comparative studies for {\tt VI} and {\tt ssVI} on Maze1}
\label{f:ssMazeExp}
\end{figure}

This is not a surprising result if we take a look at the matrix
$P_{az}$ for an action $a$ and observation $z$. We know that the
matrix impacts the size of the simplex $\tsimplex$. The dimension
of the matrix is $10\times{10}$. The entry of $P_{az}$ at $(i,j)$
is the product of the transition probability $P(s_j|s_i,a)$ and
observation probability $P(z|s_j,a)$. Let us assume that the
observation be $\verb+owow+$. Hence, the possible locations may be
2 or 5. Regardless of actions executed, only entries in row 2 and
5 of $P_{az}$ can be non-zero. Therefore, the matrix is highly
sparse and non-invertible and the simplex $\tsimplex$ is much
smaller than $\sB$. This analysis holds similarly for other
combinations of actions and observations. Hence, $\verb+ssVI+$
accounts for only a small portion of the belief space. This
explains why $\verb+ssVI+$ is more efficient than $\verb+VI+$. In
addition, we expect that the sets generated by $\verb+ssVI+$ are
much smaller than those by $\verb+VI+$.

This is confirmed in the second chart of the figure. It depicts
the sizes of the sets representing the value functions generated
by $\verb+ssVI+$ and $\verb+VI+$ at each iteration. When counting
the size of $\sV^\tsimspace_n$, we collect the sum of the sizes of
representing sets over $|\sA||\sZ|$ simplices. We note that at the
same iteration $\verb+VI+$ always generates much more vectors than
$\verb+ssVI+$. The sizes at both curves increase sharply at first
iterations and then stabilize. The size for $\verb+VI+$ reaches
its peak of 2466 at iteration 11 and the maximum size for
$\verb+ssVI+$ is 139 at iteration 10. This size in $\verb+VI+$ is
about 20 times many as that in $\verb+ssVI+$. This is a magnitude
consistent with the performance difference. After the sizes
stabilize, the sizes of the sets generated by $\verb+VI+$ are
around 130 and they are around 50 in $\verb+ssVI+$.

\

\noindent {\bf Case II: $\tsimspace=\sB$}

The problem $\verb+maze2+$ is designed to show
that $\verb+ssVI+$ could be less efficient than $\verb+VI+$
when the selected belief subset $\tsimspace$ is equal to the belief
space $\sB$. The problem has a state space of 10 locations,
an action space of size 6 (four moves, one $\verb+stay+$
and one $\verb+declare+$) and an observation space of size
7 (6 strings and a $\verb+null+$ telling nothing). The action
$\verb+stay+$ does not change the agent's position.
$\verb+maze2+$ has more complications on the observation
model. Due to hardware limitations, after a move action,
with a probability of 0.1, the agent receives a wrong report
where the string $\verb+owow+$ is collected as $\verb+owww+$ and
$\verb+woww+$ as $\verb+wowo+$. If the $\verb+declare+$ action
is executed, the agent always receives a $\verb+null+$
observation. In addition, if the agent executes $\verb+stay+$,
it receives either a $\verb+null+$ observation with probability
0.9 or the ideal string about the surrounding locations with
probability 0.1.

The reward model is accordingly changed to reflect new design
considerations. We assume that the agent needs to pay for its
information about states. For this purpose, if the agent executes
$\verb+stay+$, it really does nothing and thus yields no cost
(i.e., {\em negative reward}). In contrast, the ``move'' actions
always cause a cost of 2. Depending on the locations at which it
executes $\verb+declare+$, it receives rewards or costs: if the
location is state 9, it receives a reward of 1; if state 10, it
receives a cost of 1; otherwise, it leads to no rewards. The
$\verb+stay+$ action is attractive in that it yields no cost but
it leads to an useful observation about states with a small
likelihood.

The empirical results are collected in Figure \ref{f:ssNoisyMaze}.
First, we note both $\verb+VI+$ and $\verb+ssVI+$ are able to run
only 11 iterations within a reasonable time limit (8 hours). The
first chart in the figure presents the time costs along
iterations. To run 11 iterations, $\verb+ssVI+$ takes 53,000
seconds while $\verb+VI+$ takes around 30,900 seconds. Therefore,
$\verb+ssVI+$ is slower than $\verb+VI+$ for this problem.
However, the magnitude of performance difference is not big. To
explain this, let us consider the matrix $P_{az}$ for action
$\verb+stay+$ and observation $\verb+null+$. The transition matrix
is an identity and each state can lead to the $\verb+null+$
observation with probability of 0.9 if $\verb+stay+$ is executed.
Therefore, the matrix $P_{az}$ is invertible and the simplex
$\tsimplex$ is the same as the belief space $\sB$. Because
$\verb+ssVI+$ needs to account for additional simplices for other
combinations of actions and observations, $\verb+ssVI+$ must be
less efficient than $\verb+VI+$. This explains the performance
difference in time between $\verb+ssVI+$ and $\verb+VI+$.

\begin{figure}[htb]
\begin{center}
\begin{tabular}{ll}
\makebox{
        \epsfxsize=6.5cm
        \epsffile{results/ssvi/noninform/logtime.eps}
} &\makebox{
        \epsfxsize=6.5cm
        \epsffile{results/ssvi/noninform/logsize.eps}
}
\end{tabular}
\end{center}
\caption{Comparative studies for {\tt VI} and {\tt ssVI} on maze2}
\label{f:ssNoisyMaze}
\end{figure}

It is also anticipated that $\verb+ssVI+$ should generate more
vectors than $\verb+VI+$ at the same iteration because the size of
$\sV^\tsimspace_n$ is defined to be sum of the individual sets in
it. This is confirmed and demonstrated in the second chart of
Figure \ref{f:ssNoisyMaze}. The curve for $\verb+ssVI+$ is always
on the upper side of that for $\verb+VI+$. For the 11th iteration,
$\verb+ssVI+$ generates 3,300 vectors and $\verb+VI+$ generates
around 1,700 vectors.

\subsubsection{More Experiments on the Test-Bed}
\label{ss:testBed}

To validate the performance of the subset value iteration over
different problem domains, we collected the results of the
algorithm on the standard test-bed maintained by Tony Cassandra
\footnote{See the URL
 \verb+http://pomdp.org/pomdp/examples/index.shtml+}. In
the literature, the eight problems are commonly referred to as
4x3CO, Cheese, 4x4, Part Painting, Tiger, Shuttle, Network, and
Aircraft. Table \ref{t:ssVIMoreExp} presents detailed statistics
for these problems. In the table, Rows 2--4 give the sizes of
problem parameters, namely the number of states, observations and
actions. Row 5 and 6 show the CPU seconds for the standard and
subset value iteration algorithms to compute the 0.01-optimal
policy for each problem. Row 7 shows the number of the vectors
representing the 0.01-optimal value function in standard value
iteration. In our experiments, we implemented the subset value
iteration in the individual fashion. In Row 8, an entry takes the
form $\cdot/\cdot$, denoting the total number of vectors over all
$|\sA|\cdot|\sZ|$ simplices and the maximum number of vectors
among these simplices when the subset value iteration terminates.
The last row shows whether the belief subset $\tau(\sB)$ is a
proper subset of the belief space.

\begin{table}
\begin{tabular}{|c||r|r|r|r|r|r|r|r|} \hline
     & 4x3CO   &  Cheese & 4x4 & Paint & Tiger  & Shuttle & Network &
     Aircraft
\\ \hline \hline
$|\sS|$ & 11 & 11 & 16 & 4 & 2 & 8 & 7 & 12 \\ \hline $|\sZ|$ & 4
& 4  & 2 & 4 & 2 & 2 & 2 & 5 \\
\hline $|\sA|$ & 11 & 7 & 4 & 2 & 3 & 3 & 4 & 6 \\ \hline \hline
VI(Time) &  3.52   & 14.06 & 27.47 & 38.75 & 82.40  & 6130.69 &
13283.15 & 1723193.34
\\ \hline
ssVI(Time) & 63.28   & 85.44 & 85.44 & 85.20 & 145.21 & 1437.32 &
2810.21  & 425786.49
\\ \hline
VI($\#$) &  4   & 14 & 20 & 9 & 9      & 208 & 491 & 2071
\\ \hline
ssVI($\#$) & 43/1   & 32/2 & 42/10 & 22/9 & 22/9  & 98/45 & 201/50
& 3236/428
\\ \hline
subspace & yes & yes &  yes     & no   & no     & yes     & yes &
yes \\ \hline
\end{tabular}
\caption{Comparative studies for {\tt ssVI} and {\tt VI} on the
standard test-bed} \label{t:ssVIMoreExp}
\end{table}

In discussing the performances of the subset value iteration
algorithm, we categorize the tested problems into three classes.
In the first class, the subset $\tau(\sB)$ is actually the same as
the belief space. Subset value iteration must be less efficient
than standard value iteration. The reason is as follows: there
exists at least one belief simplex such that value iteration over
it has the same complexity as standard value iteration; moreover,
subset value iteration needs to account for other simplices.
Example problems are tiger and paint. Let us take the paint
problem as an instance. Our results show that there are two
simplices are the same as the belief space. The 0.01-optimal value
functions over them are represented by 9 vectors, each of which
has the same number of vectors representing the 0.01-optimal value
function over the entire belief space. In the second class of the
tested problems, the set $\tau(\sB)$ is a proper subset of the
belief space, and meanwhile the numbers of the vectors
representing value functions over the belief space and individual
simplices are very small. Subset value iteration may not be so
efficient as standard value iteration because of the overhead of
accounting for a large number of simplices. Example problems
include 4X3CO, cheese and 4X4. Let us take 4X3CO as an instance.
The 0.01-optimal value function over the entire belief space is
represented by only 4 vectors, whereas the 0.01-optimal value
function over each simplex is represented by only 1 vector. Since
the subset value iteration has to account for 44 simplices, subset
value iteration is less efficient than standard value iteration.
In the third class of tested problems, the set $\tau(\sB)$ is a
proper subset of the belief space, and meanwhile the numbers of
the vectors representing value functions over the belief space are
moderately large. The subset value iteration algorithm is more
efficient than the standard value iteration algorithm. Examples
include shuttle, network and aircraft. Let us take network as an
instance. The 0.01-optimal value function in the belief space is
represented by 491 vectors, whereas the 0.01-optimal value
function in $\tau(\sB)$ is represented by less than 201 vectors
(note that there are duplicates across belief simplices). The
maximum size of the representing sets over all simplices is 50. In
this case, we expect that the savings brought by the subset value
iteration outweighs the overhead of accounting for the simplices.
The result shows that subset value iteration is about 5 times
faster than standard value iteration.

Combining these results with those on the maze problem, we see
that the computational savings brought by the subset value
iteration vary with different problem domains. Theorem
\ref{th:tspaceandB} can be used to determine whether subset value
iteration can bring about computational savings for a POMDP. In
the event that the belief set $\tau(\sB)$ is a proper subset of
the belief space, the magnitude of the savings needs to be
determined through empirical evaluation.

\section{Informative POMDPs}
\label{s:informPOMDP}

In this section, we study a special POMDP class, namely
informative POMDPs. For this POMDP class, there are natural belief
subsets for value iteration to work with. We will show how to
formally define these subsets. As the value iteration over these
belief subsets has been described \cite{ZL97}, our focus is to
compare the algorithm with the general subset value iteration
developed in the previous section.

\subsection{Motivation}

As noted by some authors, in reality an agent often has a good,
although imperfect, idea about its locations \cite{RG02}. For
instance, mobile robots and other real world systems have local
uncertainty, but rarely encounter global uncertainty. Let us
exemplify this using the maze in Figure \ref{f:ssMaze}. Suppose
that at each time point an agent receives a string of four letters
with certainty. In total, there are 6 observations, $\verb+owww+$,
$\verb+owow+$, $\verb+owoo+$, $\verb+wwow+$, $\verb+wowo+$ and
$\verb+woww+$ regardless of executed actions. If we enumerate all
possible observations and the set of locations at which the agent
receives such observations, we end up with the following table.
\begin{center}
\begin{tabular}{|c|c|c|c|} \hline
observations & states & observations & states \\
\hline
$\verb+owww+$ & \{1 \} & $\verb+owow+$ & \{ 2, 5\} \\
$\verb+owoo+$ & \{ 3,4 \} &  $\verb+wwow+$ & \{ 6 \} \\
$\verb+wowo+$ & \{ 7,8\} & $\verb+woww+$ & \{ 9,10 \} \\ \hline
\end{tabular}
\end{center}
\noindent On the other hand, the strings can be used to infer the
agent's locations. For instance, if a string $\verb+owoo+$ is
received, the world must be at location 3 or 4. Hence, the
observation $\verb+owoo+$ restricts the world into a small range
of world states. In fact, any observation can restrict the world
into at most two states although the world has ten. For this
reason, the POMDP is said to be {\em informative}.

In general, an agent perceives the world via observations.
Starting from any state, if the agent executes an action $a$ and
receives an observation $z$, the world states can be categorized
into two classes by the observation model: states the agent can be
in and states it cannot. Formally, the former is $\{s|
s\in\sS\mbox{ and } P(z|s,a)>0\}$. The set is denoted by
$\sS^{az}$. We use the set to define the informativeness. An
$[a,z]$ pair is said to be {\em informative} if the size
$|\sS^{az}|$ is much smaller than $|\sS|$. An observation $z$ is
{\em informative} if $[a,z]$ is informative for every action $a$
giving rise to $z$. A POMDP is {\em informative} if all
observations are informative.

In informative POMDPs, since any observation restricts the world
into a small set of states, the agent knows that the world cannot
be in the state outside this small set. In other words, for those
states outside the set, the agent has zero beliefs. Consequently,
an observation can also restrict belief states into a belief
subset.

\subsection{Belief Subset Selection}
\label{ss:BSS}

For informative POMDPs, we can select belief subset $\tsimspace$
as before. Combining the informativeness assumption and Corollary
\ref{cor:informativeSimplex}, we know that $\tsimspace$ is a
proper subset of the belief space. So, value iteration over
$\tsimspace$ carries the space and time savings. In this section,
we choose an alternative belief subset for value iteration.
Compared against the subset $\tsimspace$, the subset that we
choose yields several advantages. First, it is conceptually simple
and geometrically intuitive. Second, it facilitates employing the
low dimensional representation of vectors. Third, it may lead to
additional savings in time if the observation models of a POMDP
are independent of actions. The latter two advantages will be
shown later.

To define the belief subset (say $\psimspace$), we first define a
subset $\psimplex$ for an action and observation pair. Then, the
belief subset $\psimspace$ is formed by taking the union of
$\psimplex$ over all action and observation pairs. To be specific,
\begin{eqnarray}
\psimplex = \{ b| \sum_{s\in\sS^{az}}b(s)=1.0, \ \forall s\in
\sS^{az}, b(s)\ge 0 \} \label{e:unitSSpace}
\end{eqnarray}
and \vspace{-0.5cm}\begin{eqnarray*}
\psimspace=\cup_{a,z}\psimplex.
\end{eqnarray*}
It is trivial to see that $\psimplex$ is a belief simplex. It can
be proven that for any belief state $b$, $\tau(b,a,z)$ must be in
$\psimplex$. Therefore, $\tau(\sB,a,z)$ is a subset of
$\psimplex$. Consequently, $\tsimspace$ is a subset of
$\psimspace$. This is summarized in the lemma below. The lemma is
useful when we discuss the value iteration algorithm working with
the belief subset $\psimspace$.
\begin{lem}
\label{l:tp-subspaces} For a POMDP,
$\tsimspace\subseteq\psimspace$.
\end{lem}

It is of interest to compare the $\tau$-simplex and $\phi$-simplex
for a pair of $a$ and $z$. Although both simplices are generated
by a list of belief states, $\phi$-simplex has more intuitive
geometric meaning. Each belief state in the basis of $\psimplex$
is a unit vector, i.e., it has probability mass on one state.
Therefore, the belief state in the basis must be a boundary point
of the belief space. In contrast, a belief state in the basis of a
$\tau$-simplex can be an interior point. See Figure
\ref{f:visualSimplex} for an example, where $A_2$, $A_3$ are
interior points and $A_1$ is a boundary point of the belief space.

\subsection{Value Iteration over $\psimspace$}

From the theoretical perspective, the feasibility of conducting
value iteration in $\psimspace$ is justified by Lemma
\ref{l:closedSSpace}. Combined with Lemma \ref{l:tp-subspaces},
the subset $\psimspace$ is a closed set. Hence, the MDP theory is
applicable to defining the DP update equation. By our discussions
on the relationship and value iteration in Section
\ref{ss:analysis}, value iteration working with $\psimspace$
retains the quality of value functions.

We further exploit the informative feature in value iteration over
$\psimspace$. We briefly outline the subset value iteration
algorithm and refer the readers to a  detailed description
\cite{ZL97}. The basic idea is to reduce the dimensions of vectors
in representing sets of value functions. Note that for any pair
$[a,z]$, since the beliefs in states outside $\sS^{az}$ are zero,
a vector in the representing set of a value function over the
simplex $\psimplex$ needs only $|\sS^{az}|$ components.  In an
individual fashion, a DP update over $\psimspace$ computes a
collection $\{\sV^\psimplex_{n+1}\}$ from a collection
$\{\sV^\psimplex_n\}$ where $\sV^\psimplex_n$ is the $n$th-step
value function and the vectors in it have $|\sS^{az}|$ dimensions.
The procedure of conducting a DP update is parallel to that in
Section \ref{ss:ssDPUpdate} except that $\tsimplex$ is replaced by
$\psimplex$. In the enumeration step, when building a vector
$\beta$ in a belief simplex $\phi(\sB,\na,\nz)$ using Equation
(\ref{e:beta-set-simplex}), we need only define its components
corresponding to the set $\sS^{\na\nz}$. In the reduction step,
for each constructed set $\sV^{\phi(\sB,\na,\nz)}_{n+1}$, a
pruning procedure is called to remove useless vectors to obtain
the minimal representation of the set. Note that the lower
dimension feature is also used to cut down the number of variables
in setting up linear programs.

Interestingly, DP updates over $\psimspace$ account for a larger
subset than those over $\tsimspace$. Hopefully, since DP updates
over $\psimspace$ explicitly employ the economy of representation,
they could be more efficient. In addition, DP updates over
$\psimspace$ have another advantage in the event that the
observation models of a POMDP are independent of actions, i.e.,
the probabilities $P(z|s,a)$ being independent of $a$. Hence,
given an observation $z$, the simplices $\phi(\sB,a,z)$ are the
same for all actions. Therefore, DP updates over $\psimspace$ only
account for $|\sZ|$ $\phi$-simplices. However, DP updates over
$\tsimspace$ usually need to account for $|\sA||\sZ|$
$\tau$-simplices because an observation determines different
$\tau$-simplices when combined with different actions.

\subsection{Empirical Studies}
\label{ss:infoVIExp}

We have conducted experiments to compare $\verb+VI+$,
$\verb+ssVI+$ and $\verb+infoVI+$, which refers to value iteration
exploiting the low-dimension feature. The experiments on
$\verb+maze1+$ (defined in Section \ref{ss:ssVIExp}) can be found
elsewhere \cite{ZZ01c,ZhangW01}. The results, together with
existing results \cite{ZL97}, showed that value iteration over
$\phi(\sB)$ can be significantly more efficient than standard
value iteration. For reference, we mention that it is feasible to
integrate a point-based technique and value iteration over
$\psimspace$ in order to take advantage of both reducing the
iteration number and accelerating the iterative steps
\cite{ZZ01a}. To demonstrate this, we include results on a
96-state POMDP in Appendix \ref{s:app.infoPOMDPs}.

\subsection{Restricted Value Iteration and Dimension Reduction}

We compare the value iteration algorithms in this and the previous
section. Through the comparison, we would like to emphasize that
working with belief subsets does not imply working with
low-dimensional vectors.

Although both algorithms work with belief subsets, the mechanisms
exploited to achieve the computational gains are different. The
general value iteration works with the belief subset $\tsimspace$
but the dimension of representing vectors is the same as the
number of states, whereas value iteration over $\psimspace$ works
with a superset of $\tsimspace$ but the dimension of the vectors
is smaller than the number of the states. To facilitate
demonstrating how a reduced belief set and the low-dimensional
representation respectively contribute to the computational gains,
we experimented with a carefully designed maze problem that is
amenable to both algorithms. However, it is worth pointing out
that working with a reduced belief set does not mean that the
vectors can be represented in low dimensions. We illustrate this
point by continuing our discussions of the example in Section
\ref{ss:beliefSubset}. Such an example shows that the primary
advantage of value iteration over $\tsimspace$ stems from the size
of the chosen belief subset rather than dimension reduction of the
representing vectors.

\

\noindent {\bf Example (Continued)} For the POMDP example
presented in Section \ref{ss:representation}, the subset
$\tsimspace$ consists of only two line segments in the entire
belief space. Clearly value iteration over $\tsimspace$ is more
efficient than standard value iteration. However, if one runs
value iteration over $\psimspace$ on this POMDP anyhow, the
algorithm is less efficient than the standard value iteration
algorithm. This follows from (1) the set $\sS^{a_iz_j}$ is equal
to the set of states $\sS$ for any action $a_i$ and observation
$z_j$ by the second assumption, and (2) each $\phi$-simplex is
actually the same as the belief space by the definition in
Equation (\ref{e:unitSSpace}). To solve this POMDP, the susbet
value iteration algorithm is definitely a better choice than the
value iteration algorithm for informative POMDPs. \qed

\section{Near-Discernible POMDPs}
\label{s:discernPOMDP}

In this section, we study near-discernible POMDPs. For this POMDP
class, we develop an anytime value iteration algorithm working
with growing belief subsets.

\subsection{Motivation}

A discernible POMDP assumes that once in a while the uncertainty
about world states vanishes if a particular action is executed and
the observations pertain to the action fully reveal the identities
of the world \cite{Hansen98}. Our research on near-discernible
POMDPs was motivated by two aspects. One of them arises from the
origin of applying POMDP as a framework for planning under
uncertainty. To achieve a goal location, an agent has to not only
change its positions by performing goal-achieving actions but also
reason about its surroundings by performing information-gathering
actions. However, at one time point the agent cannot
simultaneously move its positions and observe its environments.
For instance, if an information-gathering action is performed, the
agent cannot move its positions meanwhile. The other aspect
motivating the concept of near-discernibility arises from existing
research in the community. Near-discernible POMDPs generalize
discernible POMDPs in that even when an information-gathering
action is performed, the agent can get a rough, rather than exact,
idea about world states and uncertainty vanishes in some sense.

We revise the maze problem to fix ideas on the first motivation.
The action space consists of six actions: four ``moving'' actions,
$\verb+look+$ and $\verb+declare+$. If move actions or
$\verb+declare+$ are performed, an observation $\verb+null+$ is
received and the agent gets no information at all. If
$\verb+look+$ is performed, an ideal string is received and the
agent gets imperfect information since different locations might
yield the same string. On one hand, to achieve the goal location,
the agent has to change its positions. On the other hand, to
declare goal attainment with confidence, it has to perform
$\verb+look+$ and reason about the environment. Arbitrarily
declaring goal attainment leads to a penalty. Consequently, at a
time point the agent faces the problem of choosing a move or
$\verb+look+$.

We note that the subset value iteration algorithm usually yields
no computational advantage for near-discernible POMDPs. We give an
example in which the subset $\tau(\sB)$ is the same as the belief
space $\sB$ under some assumptions. Suppose the maze is a square
grid. Locations are numbered such that at each row the indices of
the locations increase from left to right. We assume that a move
action achieves its intended effects with a high likelihood, but
may have no effect (i.e., the agent's location remains unchanged)
or may lead to overshooting with a small probability. Under these
assumptions, the transition matrix for action $\verb+east+$ is
upper-triangular and invertible. If at each location $\verb+null+$
is received with a positive probability after a move, the
transformational matrix $P_{\verb+east+,\verb+null+}$ is
invertible. By Theorem \ref{th:tspaceandB}, the belief subset
$\tau(\sB,\verb+east+,\verb+null+)$ is equal to the belief space
$\sB$.

Our solution to near-discernible POMDPs rests on the intuition
that the agent needs to interleave goal-achieving actions and
information-gathering actions. A typical sequence of executed
actions should consist of several goal-achieving actions and an
information-gathering action. The difficulty is how frequently the
agent should execute an information-gathering action. In this
section, we consider the action and observation sequences
containing more goal-achieving actions incrementally. We show that
such sequences can be used to determine belief simplices. As more
sequences are added, the union of the belief simplices grows. In
the following, we give some technical preparations and then
describe the algorithm designed for near-discernible POMDPs. In
order to put our discussions under a general context, we shall use
{\em information-rich} and {\em information-poor} actions instead
of information-gathering and goal-achieving actions respectively.


\subsection{Histories, Belief Subsets and Value Functions}

A history is a sequence of ordered pairs of actions and
observations. We usually denote a history by $h$. The number of
pairs of actions and observations is referred to as {\em the
length of a history}. A history of length $l$ is denoted by
$[a_1,z_1,\cdots,a_l,z_l]$. If an agent's initial belief state is
$b$ and a history $h$ of length $l$ is realized, its belief state
can be updated at each time step. The notation $\tau(b,h)$ denotes
the belief at the time point $l$. The set $\tau(\sB,h)$ is defined
to be $\cup_{b\in\sB}\tau(b,h)$, consisting of all possible belief
states that the agent can be in at step $l$ if it starts with any
belief and history $h$ is realized. Note that if $h$ is of length
1(say $h=[a,z]$), $\tau(\sB,h)$ degenerates to our previous
notation $\tau(\sB,a,z)$.
\begin{lem}
\label{l:historySimplex}
For any history $h$, the belief subset $\tau(\sB,h)$ is a simplex.
\end{lem}

A set of histories is usually denoted by $\sH$. The belief subset
$\tau(\sB,\sH)$ denotes the union of simplices for all histories
in the set $\sH$, i.e., $\cup_{h\in\sH}\tau(\sB,h)$. Value
functions over the simplex $\tau(\sB,h)$ and belief subset
$\tau(\sB,\sH)$ are referred to as $V^{\tau(\sB,h)}$ and
$V^{\tau(\sB,\sH)}$ respectively. Given a set $\sV^{\tau(\sB,h)}$
representing value function $V^{\tau(\sB,h)}$, the procedure
$\verb+simplexPrune+(\sV,B_{\tau(\sB,h)})$ in Table
\ref{t:simplexPrune} computes the minimal representation of
$\sV^{\tau(\sB,h)}$. In the context of history, the occurrences of
the basis $B_\tsimplex$ should be replaced by $B_{\tau(\sB,h)}$.

\subsection{Space Progressive Value Iteration}

We describe the space progressive value iteration (SPVI)
algorithm. As an anytime algorithm, SPVI begins with a belief
subset and gradually grows it. When a certain stopping criterion
is met, SPVI terminates and returns a set of vectors for the
agent's decision making.

\subsubsection{Algorithmic structure}

SPVI interleaves value iteration (computing a value function for a
belief subset) and subset expansion (expanding the current belief
subset to a larger one). The belief subsets in SPVI are introduced
by sets of histories. Subset expansion is achieved through
incorporating more histories. For convenience, the set of
histories determining the $i$-th belief subset is denoted by
$\sH_i$. The belief subset determined by $\sH_i$ is
$\tau(\sB,\sH_i)$. The value function constructed by SPVI for
$\sH_i$ is $\sV^{\tau(\sB,\sH_i)}$.

The pseudo-code in Table \ref{t:spvi} implements SPVI. A set of
histories $\sH_0$ (and therefore the belief subset
$\tau(\sB,\sH_0)$), a value function $\sV^{\tau(\sB,\sH_0)}$ and
the quality precision $\eta$ are initialized at line 1. This step
can be regarded as the 0th-step expansion of belief subset. Note
that we set the initial value function to be the minimum reward
for all pairs of actions and states. (This is for the convergence
issue discussed later.) Value iteration over the current subset
$\tau(\sB,\sH_i)$ is conducted at line 3, and the belief subset is
expanded to the subset $\tau(\sB,\sH_{i+1})$ through constructing
a superset $\sH_{i+1}$ of the current set $\sH_i$ at line 4. Value
function $\sV^{\tau(\sB,\sH_i)}$ for the current belief subset is
set to be the initial value function for the next subset at line
5. If the stopping condition is not satisfied at line 7, SPVI goes
to the next iteration; otherwise, it terminates and returns the
latest value function $\sV^{\tau(\sB,\sH_{i-1})}$.
\begin{table}[htb]
\begin{tabbing}
xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=  \kill
\> $\verb+SPVI+$: \\
\> 1.\> $i\la{0}$, initialize $\sH_0$,
$\sV^{\tau(\sB,\sH_0)}\la\min_{s\in\sS,a\in\sA}{r(s,a)}$,
        $\eta\la\epsilon(1-\lambda)/2\lambda$\\
\> 2.\> {\bf Do} \\
\> 3.\>\> $\sV^{\tau(\sB,\sH_i)}\la\verb+subsetVI+
             (\sV^{\tau(\sB,\sH_i)},\sH_i,\eta)$ \\
\> 4.\>\> $<\sH_{i+1},\tau(\sB,\sH_{i+1})>\la\verb+expandSubset+
        (\sV^{\tau(\sB,\sH_i)}, \sH_i)$ \\
\> 5.\>\> $\sV^{\tau(\sB,\sH_{i+1})}\la\sV^{\tau(\sB,\sH_i)}$ \\
\> 6.\>\> $i\la{i+1}$ \\
\> 7.\> {\bf Until}\ (stopping condition is met) \\
\> 8.\> {\bf Return} $\sV^{\tau(\sB,\sH_{i-1})}$
\end{tabbing}

\begin{tabbing}
xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=  \kill
\> $\verb+subsetVI+(\sV,\sH,\eta)$: \\
\> 1.\> $j\la{0}, \sU_0\la\sV$ \\
\> 2.\> {\bf Do} \\
\> 3.\>\> $\sU_{j+1}\la\verb+subsetDPUpdate+
        (\sU_j,\tau(\sB,\sH))$ \\
\> 4.\>\> $\sU_{j+1}\la\sU_{j+1}\cup\sU_j$ \\
\> 5.\>\> $j\la{j+1}$ \\
\> 6.\> {\bf While} $(\ \max_{b\in\tau(\sB,\sH)}
    |\sU_j(b)-\sU_{j-1}(b)|\le\eta\ )$   \\
\> 7.\> {\bf Return} $\sU_{j-1}$
\end{tabbing}

\begin{tabbing}
xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=  \kill
\> $\verb+expandSubset+(\sV, \sH)$ \\
\> 1. \> $\nH\la\sH$ \\
\> 2.\>  {\bf For} each $\beta$ in the set $\sV$ \\
\> 3.\>\> {\bf If} $\beta$.history is maximal in $\sH$ {\bf and }
    $\beta$.action is information-poor \\
\> 4. \>\>\> {\bf For} each $[a,z]$ in $\sA_{IP}\times\sZ_{IP}$ \\
\> 5. \>\>\>\>\> $\nH\la\nH\cup\{[h,a,z]\}$ \\
\> 6.\> {\bf Return} $<\nH,\tau(\sB,\nH)>$
\end{tabbing}
\caption{Space progressive value iteration (SPVI)}
\label{t:spvi}
\end{table}

To ensure the efficiency of SPVI, its initial belief subset should
be chosen to be small. To this end, we set $\sH_0$ to be $\{[a,z]
\mid a\in\sA_{IR},z\in\sZ_{IR}\}$ where $\sA_{IR}$ is the set of
information-rich actions and $\sZ_{IR}$ is the set of observations
led to by those actions. The subset $\tau(\sB,\sH_0)$ is small due
to the discernability  property.

In the sequel, we discuss value iteration in a belief subset,
subset expansion and the stopping criterion in detail.

\subsubsection{Value iteration in a belief subset}

Given a set $\sV$ of vectors, a set $\sH$ of histories and a
precision threshold $\eta$, value iteration computes an improved
value function over the belief subset $\tau(\sB,\sH)$. This is
accomplished by conducting a sequence of DP updates. In the
following, we discuss implicit DP updates, the convergence issue
and the stopping criterion in the value iteration step.

An implicit DP update computes a new value function from the
current one for belief subset $\tau(\sB,\sH)$. Let $\sU_j$
($\sU_0=\sV$) denote the $j$-step value function. Thus, a DP
update computes value function $\sU_{j+1}$ from $\sU_j$. The
procedure of computing $\sU_{j+1}$ from $\sU_j$ is parallel to the
collective DP update in Section \ref{s:ssVI}. In particular, when
defining a vector $\beta_{a,\delta}$ given an action $a$ and a
mapping $\delta$ in Equation (\ref{e:beta-set-subset}), the
occurrences of $\sV^{\tau(\sB)}_n$ are replaced by $\sU_j$. By
enumerating actions and mappings, all defined vectors form the set
$\sU_{j+1}$. Its minimal representation is obtained by removing
useless vectors w.r.t.\ the subset $\tau(\sB,\sH)$.

The convergence issue arises because the subset $\tau(\sB,\sH)$
may not be a closed set. To guarantee the convergence of value
iteration, we set $\sU_{j+1}$ to be the union of set $\sU_{j+1}$
and $\sU_j$ after a DP update. Together with the fact that the
initial value function is set to be the minimum reward for all
actions and states, the sequence $\{\sU_j\}$ monotonically
increases in terms of induced value functions. On the other hand,
the value functions in the sequence are upper bounded by the
optimal value function. Consequently, value iteration in
$\tau(\sB,\sH)$ must converge. As a result, the Bellman residual
between value functions,
$\max_{b\in\tau(\sB,\sH)}|\sU_{j+1}(b)-\sU_j(b)|$, becomes smaller
in $\tau(\sB,\sH)$ as value iteration continues. When the residual
falls below the threshold $\eta$, value iteration terminates.

The value iteration step is implemented as the procedure
$\verb+subsetVI+$ in Table \ref{t:spvi}. Given a set $\sV$ of
vectors, a set $\sH$ of histories and a threshold $\eta$, the
procedure computes an improved value function for belief subset
$\tau(\sB,\sH)$. Value function $\sU_0$ is set to be the input set
$\sV$ at line 1. The new value function $\sU_{j+1}$ is computed by
a DP update at line 3. To guarantee convergence, $\sU_{j+1}$ to
set to be the union of $\sU_j$ and $\sU_{j+1}$ at line 4. The
stopping criterion is tested at line 6. If it is met, the latest
value function $\sU_{j-1}$ is returned.

\subsubsection{Subset expansion}
\label{sss:expansion}

Given a set $\sV$ of vectors and a set $\sH$ of histories, the
subset expansion step expands the belief subset $\tau(\sB,\sH)$ to
a larger one. This is achieved by generating a superset $\sH'$ of
$\sH$. The new belief subset $\tau(\sB,\nH)$ is thus a superset of
$\tau(\sB,\sH)$. Hence, the key in subset expansion is how to
generate a history set $\nH$. In the following, we propose two
approaches to generating the history set using our intuition for
near-discernible POMDPs. Both approaches generate new histories by
exploiting the vectors in $\sV$. We begin with an analysis of the
vectors in the set $\sV$ and show how to use them to generate
histories.

Let $\beta$ be a vector in the set $\sV$. Remember that $\beta$ is
defined by a pair of action $a$ and mapping $\delta$. For
convenience, such an action is said to be the {\em associated
action of $\beta$}. In addition, if $\beta$ is useful in the set
$\sV$ w.r.t.\ the belief subset $\tau(\sB,\sH)$, there must exist
a history $h$ in $\sH$ such that $\beta$ is useful w.r.t.\ the
belief simplex $\tau(\sB,h)$. The history $h$ is said to be the
{\em associated history of $\beta$}. The associated history of a
vector can be used to generate new histories by {\em extending the
history}, i.e., appending the pairs of informative-poor actions
and observations to the history. Let $\sA_{IP}$ be the set of the
information-poor actions and $\sZ_{IP}$ be the set of the
observations led to by those actions. Extending history $h$
results in a set $\{[h,a,z]|a\in{\sA_{IP}},z\in{\sZ_{IP}}\}$. The
set contains $|\sA_{IP}||\sZ_{IP}|$ histories. Each history in the
set is called an {\em extension of history $h$}.

To generate $\nH$ from the set $\sH$ and the set $\sV$, one
generic approach works as follows. Each vector $\beta$ in the set
$\sV$ is examined. If its associated history is long and the
associated action is information-poor, we produce all extensions
of its associated history. An extension is added to $\nH$ if it is
not in $\nH$. (The reason is that the associated action of a
vector should be information-rich if its associated history is
sufficiently long.) To ensure that $\nH$ is a superset of $\sH$,
we set $\nH$ to be $\sH$ in the beginning. Apparently, this
approach to generating histories suffers from the exponential
increase of the size $|\nH|$ in $|\sA_{IP}|$ and $|\sZ_{IP}|$. In
the worst case where all the vectors in $\sV$ are associated with
information-poor actions, the size $|\nH|$ is
$|\sH||\sA_{IP}||\sZ_{IP}|$. Consequently, after the $i$-step
subset expansion, $|\sH_{i+1}|$ can be as large as
$|\sA_{IR}||\sZ_{IR}|{(|\sA_{IP}||\sZ_{IP}|)}^i$ where
$|\sA_{IR}||\sZ_{IR}|$ is the size of initial history set.

To alleviate this problem, we use a heuristic approach to
generating $\nH$ in hope that the size $\nH$ increases moderately.
The above exhaustive approach extends the histories associated
with the vectors prescribing informative-poor actions. The
heuristic approach does not extend all such histories. Instead it
extends only {\em maximal histories} in the set $\sH$. (A history
is said to be maximal in a set if none of its extensions is in the
set.) This is the only change made from the above approach. As
indicated in the experiments, this restriction can effectively cut
down the size of the history sets. Nonetheless, the heuristic
approach shares the same worst-case complexity with the exhaustive
approach.

The subset expansion step is implemented as the procedure
$\verb+subsetExpansion+$ in Table \ref{t:spvi}. Given a set $\sV$
of vectors and a set $\sH$ of histories, it computes
an expanded set $\nH$ and an expanded belief subset $\tau(\sB,\nH)$.
The set $\nH$ is initialized to be $\sH$ at line 1. For each vector
$\beta$ in $\sV$ at line 2, if its associated history is maximal
in $\sH$ and its action is information-poor (line 3), all the
extensions of its associated history are added to $\nH$ (line 5).
The expanded set $\nH$ and also the expanded belief subset
$\tau(\sB,\nH)$ are returned at line 6.

\subsubsection{Stopping criterion and Decision-Making}

As an anytime algorithm, SPVI can be terminated if a hard deadline
is reached. Another stopping criterion of interest can be set as
follows. Given a sufficiently large amount of time, SPVI would
account for as many histories as possible. If a (near) optimal
policy of the POMDP requires that information-rich actions be
executed after a sequence of information-poor actions, SPVI should
be able to compute a value function for the belief subset, which
consists of all possible belief states that the agent encounters
if it is guided by such a policy. After sufficiently many
expansions of history sets and hence belief subsets, any vector
associated with a maximal history prescribes an information-rich
action. If all the vectors in the representing set prescribe
information-rich actions, SPVI terminates. If a (near) optimal
policy has the desired structure in its sequence of actions, the
output value function should be near optimal in the final belief
subset.

When SPVI terminates, the value function $\sV^{\tau(\sB,\sH_{i-1})}$
can be used for decision making. Similarly to Equation
(\ref{e:v-improve}), a $\sV^{\tau(\sB,\sH_{i-1})}$-improving policy
can be defined over the belief space.

\subsubsection{Efficiency of SPVI}

The efficiency of SPVI depends on the selected belief subsets. If
these belief subsets are close to the belief space in size, SPVI
must be inefficient. Fortunately, our approach for belief subset
expansion ensures that the initial belief subset is small and the
subsequent subsets grow slowly. First, since $\sH_0$ is the set of
the pairs of information-rich actions and observations, the
initial belief $\tau(\sB,\sH_0)$ is relatively small. Second, the
subsequent belief subsets $\tau(\sB,\sH_i)$ do not grow too
quickly. The reason follows. In extending a history, the
information-poor pairs are added to its end. Hence, the first
action and observation pair of the histories in a set $\sH_i$ must
be information-rich. Therefore, for a history $h$ in the set
$\sH_i$, $\tau(\sB,h)$ is small in size. Meanwhile, due to the
heuristic for generating history sets, the sizes $|\sH_i|$ would
not increase too fast. These characteristics make SPVI efficient
when compared with the standard value iteration algorithm.

Although the above analysis is empirically confirmed in our
experiments below, it is worthy to mention that in the worst case
the number of belief simplices grows exponentially in the number
of $|\sA_{IP}||\sZ_{IP}|$.  Since a history determines a belief
simplex, in the worst case the number of the belief simplices
after the $i$-step subset expansion is the same as the number of
histories, i.e., $|\sA_{IR}||\sZ_{IR}|{(|\sA_{IP}||\sZ_{IP}|)}^i$
(see the third paragraph of Section \ref{sss:expansion}).

\subsection{Empirical Results}

Since SPVI works in an anytime manner, our primary interest is to
demonstrate how the quality of the generated value functions
varies with the time cost. However, the availability of optimal
solutions strongly depends on the ``tractability'' of the
problems. If a near optimality is available, we compare it
directly with the value function generated by SPVI by simulations.
Otherwise, we simply compare value functions from SPVI against
those from an approximate algorithm QMDP \cite{LCK95b,Ha00}.
Although the comparison is not strict in a formal sense, it can
provide clues about the quality of value functions.

We report our results on two variants of the base maze problem and
an office navigation problem. In one variant, SPVI terminated
after a finite number of iterations and the output value function
is near optimal; in the other variant, SPVI can quickly find a
high-quality value function as time goes by \cite{ZZ01b,ZhangW01}.
In the rest of this section, we report our results on the office
navigation problem.

The environment is modeled after the floor plan of the authors'
home department. The layout is shown in Figure
\ref{f:disn-office}. There are 35 states: 34 locations plus one
terminal state. The action space is of size 6 (four $\verb+move+$,
one $\verb+look+$ and one $\verb+beep+$ replacing $\verb+declare+$
in the maze problem). Any action except $\verb+look+$ leads to a
$\verb+null+$ observation. To introduce other observations, we
note that in the figure, black bars represents doors and grey bars
represent walls with display boards. The $\verb+look+$ action
yields observation of strings of four letters for a location
indicating, for each of the four directions, where there is a door
(d), an empty wall (w), a wall with a display board (b), or
nothing (o). In total, there are 22 different strings. Hence, plus
the $\verb+null+$ observation, the observation space is of size
23. Transition probabilities for moves are specified identically
as in the maze problem. Neither $\verb+look+$ nor $\verb+beep+$
changes the states of the environment. At each location,
$\verb+look+$ produces the ideal string for that location with
probability 0.75. With probability 0.05, it produces the
$\verb+null+$ observation. Also with probability 0.05, it produces
a string that is ideal for some other location and that differs
from the ideal string for the current location by only 1
character. The robot receives a reward of 50 when beeping at
location 22 and a reward of -10 when beeping at any other location
(we don't want the robot to make a lot of noise). The
$\verb+move+$ actions bring about a reward of -2 if they lead the
robot to bumping into walls or doors. They have no rewards
otherwise. The reward for the $\verb+look+$ action is always -1.
The robot needs to get to location 22 and beep so that someone in
the main office can come out and hand the robot some mail.

\begin{figure}[htb]
\begin{center}
\makebox{
        \epsfxsize=10cm
        \epsffile{results/disnvi/office.n/office.xfig.eps}
}
\end{center}
\caption{HKUST-CSD office environment} \label{f:disn-office}
\end{figure}

We conduct simulations about the generated value functions because
no existing exact algorithm can find the near optimal value
function. The simulation consists of 1000 trials. Each trial
starts from a random initial belief state and is allowed to run up
to 100 steps. The average reward across all the trials is used as
a measurement of the quality of policies derived by value
functions.

Figure \ref{f:csdOffice-spvi} presents the results about the
quality against time costs. We see that SPVI found a policy whose
average reward is 19.6 in about 80,000 seconds. SPVI was manually
terminated after running about 24 hours. It is found that the
algorithm conducted three steps of subset expansion. By our data,
after the first and second expansion steps, both rewards by
simulation are 18.4. This is not far from 19.6 obtained after the
third expansion step although it is difficult to say how close
those polices are to the optimal. Compared with the solutions
generated by QMDP, the policies generated by SPVI are clearly
better.
\begin{figure}[htb]
\begin{center}
\makebox{
        \epsfxsize=7cm
        \epsffile{results/disnvi/office.n/logtime.eps}
}
\end{center}
\caption{Performance of SPVI on office navigation problem}
\label{f:csdOffice-spvi}
\end{figure}

For reference, Table \ref{t:hkust-csd-SPVI} gives detailed
statistics on the number of the histories, iterations and vectors
after each subset expansion. A note is about the number of
iterations in the third column: when conducting value iteration
over subsets, we also use the point-based improvements
\cite{ZhangW01}. In the column, the number of point-based steps
are excluded. The fourth column about the number of vectors
provides some idea of why SPVI takes long time for this problem.
This is because it generates a great number of vectors. After the
third expansion, it uses 7,225 vectors to represent a value
function over the belief subset.
\begin{table}[htb]
\begin{center}
\begin{tabular}{|c||c|c|c|c|r|} \hline\hline
$i$-step expansion &  histories\# & iterations\# & vectors\# &
rewards & time  \\ \hline
0 & 53 & 4  & 464   & 18.44 & 163 \\
1 & 86 & 6  & 5178  & 18.44 & 16157 \\
2 & 131 & 7 & 7225  & 19.65 & 78183 \\ \hline
\end{tabular}
\end{center}
\caption{Statistics on HKUST-CSD environment for SPVI}
\label{t:hkust-csd-SPVI}
\end{table}


\section{Related Work}
\label{s:relatedWork}

In this paper, we propose restricted value iteration algorithms to
accelerate value iteration for POMDPs. Two basic ideas behind
restricted value iterations are (1) reducing the complexity of DP
updates and (2) reducing the complexity of value functions. In
this section, we discuss related work under these two categories.
In addition, we give an overview on special POMDPs in the
literature and the algorithms exploiting their problem
characteristics.

\subsection{Reducing the Complexity of DP Updates}

In a broad sense, approaches reducing the complexity of DP
updates can be roughly categorized into two classes: approaches
conducting value updates over a (stationary) belief subset and
approaches conducting value updates over a growing subset,
although the boundary between these two classes is ambiguous
in some cases.

The first class includes a family of grid-based algorithms,
algorithms based on reachability analysis, algorithms using
state-space decomposition and others. Grid-based algorithms update
values for a finite grid and extrapolate values for non-grid
belief states \cite{Love91b,Ha97,ZH01}. However, to guarantee
optimality, the grid size is often exponential in the dimension of
the state space. To tackle POMDPs with large state spaces,
reachability analysis is a generally applicable technique. If an
agent is informed of its initial belief, all belief states it can
encounter form a finite set in case of a finite decision horizon.
These belief states can be structured in a decision tree or AND/OR
tree \cite{Wash97,HZ98,Hansen98,BG2000}. Although sometimes near
optimality can be achieved at the initial belief state
\cite{Hansen98}, the algorithms in the cited articles cannot be
applied to the case with unknown initial belief. State-space
decomposition is an effective way to alleviate the curse of
dimensionality. This approach has been successfully applied to
MDPs \cite{DL95,DGK98,Parr98,KP2000}. Typically, to solve an MDP,
one solves a number of small MDPs and uses their solutions to
approximate that of the original MDP. However, the state-space
decomposition approach cannot directly generalize to the POMDP
context because of the inherent difficulty incurred by the
continuum of the belief space.

Our theory and algorithms on restricted value iteration have
significant differences from the above approaches. Through a well
chosen belief subset, restricted value iterations can achieve
convergence and optimality. It differs from grid-based algorithms
in that it computes vector-based representations of value
functions. Despite this difference, it is possible that grid-based
algorithms can benefit from our theory on belief subset selection.
This possibility is yet to be investigated. For instance, while
choosing grid points, one should choose those within the belief
subset $\tsimspace$. The reason follows. Since the belief states
outside the set are never reachable, their values do not directly
contribute to value updates for beliefs in the grid. With regard
to the differences between the aforementioned algorithms and ours,
our approach has no assumption about an agent's initial belief,
although the belief subset is chosen via reachability analysis.
Our algorithm differs from the decomposition techniques in that it
solves a reformulated MDP instead of a set of small MDPs.

Approaches conducting value updates for a growing belief subset
include real-time dynamic programming (RTDP) in the POMDP context
\cite{BBS95,GB98}, a synthetic projection algorithm \cite{DB90}
and the envelope algorithm for Plexus planner in the MDP context
\cite{DKKN93}. Naturally, they run as anytime algorithms. In RTDP,
value updates are carried out for a belief subset, which grows as
an agent explores the belief space. The main difference between
SPVI and the above algorithms is how they expand the belief/state
subset and how they choose beliefs/states for value updates. For
subset expansion, SPVI adds more belief simplices, which often
contains an infinite number of belief states, while the above
algorithms mostly add a finite number of belief states. (It is
also noted that reachability analysis is used in these
expansions.) For value updates, SPVI improves values for the
entire belief subset, while the above algorithms typically select
a limited number of beliefs or states in the current subset.

\subsection{Reducing the Complexity of Value Functions}

Another idea behind restricted value iteration is concerned with
the representational complexity of value functions. Intuitively,
the representing set of a value function over a belief subset
contains fewer vectors than that of the same value function over
the belief space. This fact has been observed \cite{BP96,HF98},
where POMDPs are represented compactly. When states are depicted
by a set of variables, they are classified into observable
variables and hidden variables. It is also noted that some belief
states cannot be reached for certain combinations of observable
variables and hidden variables.  This fact has been exploited in
approximating the solution to a medical treatment example
\cite{HF98}. Recent work along this thread includes a state-space
compression technique exploiting the representational advantage
\cite{PB02}, and a technique of Principle Component Analysis (PCA)
aiming at reducing the complexity of value functions \cite{RG02}.
However, it is unclear whether it is feasible to combine
state-space compression with subset value iteration before we know
how to conduct value iteration over a belief space induced by a
compressed state space.

\subsection{Solving Special POMDPs}

Since solving a POMDP generally is computationally intractable, it
is advisable to study POMDPs with special characteristics. The
hope is that these characteristics may be exploited to find their
near optimal solutions more efficiently. Special POMDPs examined
in the literature include regional-observable POMDPs \cite{ZL97},
memory-resetting and discernible POMDPs \cite{Hansen98}, even-odd
POMDPs \cite{ZD00} and generalized near-discernible POMDPs
\cite{ZhangW01}. Interestingly, these POMDPs assume the existence
of informative actions or observations such that somehow an agent
is able to get more information about the world. In the following,
we briefly discuss the assumptions behind informative POMDPs and
near-discernible POMDPs and review existing work closely related
to them. Before concluding this subsection, we also mentioned a
couple of extensions to our current work.

An informative POMDP assumes that any observation restricts the
world into a small set of states. This assumption is validated by
a few problem instances with compact representations of state
space. In the literature, some POMDP examples are actually
informative POMDPs. One example is the {\em slotted Aloha}
protocol problem \cite{BG95,Cass98a}, where the state of the
system consists of the number of backlogged messages and the
channel status. The channel status is observable and its possible
assignments form the observation space. However, the system has no
access to the number of backlogged messages. If the maximum number
of backlogged messages is set to $m$ and there are $n$ possible
values for the channel status, the number of states is $m\cdot n$.
A particular assignment of channel status will restrict the system
into $m$ states out of $m\cdot n$. A similar problem
characteristic also exists in a non-stationary environment model
proposed for reinforcement learning \cite{CYZ99}.

A regional observable POMDP assumes that at any point in time an
agent is restricted to a handful of world states \cite{ZL97}. The
assumption leads to a value iteration algorithm that works with a
belief subset and also exploits the low dimensional representation
of vectors. We used the algorithm to solve informative POMDPs.
However, we would like to discuss  several differences. First,
conceptually the assumptions are different for the two POMDP
classes. In regional observable POMDPs, when the agent is
restricted to a set of states (i.e., a {\em region}), the states
in such a set are geometrically neighboring ones. However, in
informative POMDPs, when the agent is restricted to a set of
states, the states in a set are obtained by formally analyzing the
observation model of the POMDP. It is possible that the states in
the set are spatially distant from one another. Second, the
algorithms for the two POMDP classes work in a quite different
way. To ease presentation, we use $\verb+infoVI+$ and
$\verb+roVI+$ to respectively denote our value iteration for
informative POMDPs and that for regional observation POMDPs. In
$\verb+infoVI+$, the number of state sets is the product of the
number of actions and the number of observations, while in
$\verb+roVI+$, the number of regions is subjectively chosen. In
addition, the observations in $\verb+roVI+$ are {\em augmented}.
An {\em augmented observation} consists of an original observation
and a specific region. So, the number of augmented observations is
the product of the number of original observations and the number
of regions. Hence, $\verb+roVI+$ has to account for many more
observations than $\verb+infoVI+$. This fact is useful when
comparing the efficiency of $\verb+infoVI+$ and $\verb+roVI+$.
Imagine what happens if $\verb+roVI+$ works with the region
system, which consists of the state sets defined by
$\verb+infoVI+$, for an informative POMDP. Because $\verb+infoVI+$
accounts for fewer observations than $\verb+roVI+$, it should be
more efficient. Finally, the quality of the value function
returned by $\verb+infoVI+$ is guaranteed for the entire belief
space when it terminates with the strict stopping criterion.
However, the quality of the value function by $\verb+roVI+$ in its
original description is problematic even for the considered belief
subset.

The other POMDP class examined in this paper is near-discernible
POMDPs. A near discernible POMDP assumes that the actions are
classified into information-rich ones and information-poor ones.
The assumption is reasonable in several realistic domains. The
first domain is the path planning problems \cite{Cass98a}. The
actions are categorized into goal-achieving and
information-gathering ones, as discussed earlier. Another
application domain is machine maintenance problems
\cite{SS73,Hansen98}, where an agent usually can execute the
following set of actions: manufacture, examine, inspect and
replace. Among these actions, ``inspect'' is information-rich and
the remaining three actions are information-poor.

A near discernible POMDP is a generalization of a memory-resetting
(discernible) POMDP, which assumes that there exists actions
resetting the world to an unique state. If such actions are
performed, the agent knows that the world must be in a definite
state. If the initial belief state is known and an optimal policy
must execute one of such actions periodically, the number of
belief states that the agent visits is finite. Accordingly, DP
updates over a finite set of beliefs are much cheaper. However,
after the discernibility assumption is relaxed, the agent may
visit an infinite number of states and DP updates become more
expensive. We therefore developed an anytime algorithm seeking a
tradeoff between the solution quality and the size of the belief
subset.

We also experimented with one extension of using SPVI to
approximate the solutions of more general POMDPs \cite{ZhangW01}.
The approximation scheme employs a thresholding technique. Given a
POMDP and a threshold, a POMDP can be transformed to a new one,
which differs from the original one in the observation model. The
observation model in the transformed POMDP is obtained by ignoring
the probabilities (in the original model) less than the threshold
\footnote{To complete the definition of the approximate
observation model, one needs to re-normalize model parameters such
that for an action and a state, the probabilities for all
observations sum up to 1.0.}. If the transformed POMDP is near
discernible, its solution can be found by SPVI and be used to
approximate that of the original POMDP. We have designed another
maze problem that has no informative action/observation pair and
therefore is expected to be not amenable to SPVI \cite{ZhangW01}.
However, the transformed POMDP is amenable to SPVI. The
experiments show that SPVI can quickly find a high quality
solution for the transformed POMDP. In another case, if the
transformed POMDP is informative, the algorithm exploiting low
dimensional representations for informative POMDPs can be applied.

\section{Conclusions}
\label{s:conclusions}

In this paper, we studied value iterations working with belief
subset. We applied reachability analysis to select a particular
subset. The subset is (1){\em closed} in that no actions can lead
the agent to belief states outside it; (2){\em sufficient} in that
value function defined over it can be extended into the belief
space; and (3){\em minimal} in that value iteration needs to
consider at least the subset if it intends to achieve the quality
of value functions. That the subset is closed enables one to
formulate a subset MDP. We addressed the issues of representing
the subset and pruning a set of vectors w.r.t.\ the subset. We
then described the subset value iteration algorithm. For a given
POMDP, whether the subset is proper can be determined {\em a
priori}. If this is the case, subset value iteration carries the
advantages of representation in space and efficiency in time. We
also studied informative POMDPs and near-discernible POMDPs. For
informative POMDPs, there are natural belief subsets for value
iteration to work with. For near-discernible POMDPs, we developed
an anytime value iteration algorithm seeking a tradeoff between
the policy quality and the size of belief subsets.

\acks{Research was partially supported by Hong Kong Research
Grants Council under grant HKUST6088 / 01E. The authors thank Tony
Cassandra and Eric Hansen for sharing with us their programs. The
first author would like to thank Eric Hansen for in-depth
discussions on belief subset selection and low dimensional
representation, and Judy Goldsmith for valuable comments on an
earlier writeup of the ideas in this paper. We are also grateful
for the three anonymous reviewers who provided insightful comments
and suggestions on this paper.}

\appendix

\section{Proofs}
\label{s:app.proofs}

\setcounter{theo}{1}

\begin{theo}
%\label{th:sspace}
For any pair $[a,z]$, the subset $\tsimplex$ is a simplex.
\end{theo}

\noindent {\bf Proof:} Suppose $b_i$ is a belief state such that
$b_i(s)=1.0$ for $s=s_i$ and 0 otherwise. It can be seen that
$\{b_1,b_2,\cdots,b_n\}$ is a basis of belief space $\sB$. Each
belief state $b(=(b(s_1),b(s_2),\cdots,b(s_n))$ can be represented
as $\sum^n_{i=1}b(s_i)b_i$.

Let $k$ be the cardinality of the set $\{\tau(b_i,a,z)|P(z|b_i,a)>0\}$.
Without loss of generality, we enumerate the set as
$\{\tau(b_1,a,z)$, $\cdots$, $\tau(b_k,a,z)\}$.
It suffices to show that $\tsimplex=$
$\Psi(\tau(b_1,a,z),\tau(b_2,a,z),\cdots,\tau(b_k,a,z))$. To prove
it, we prove:

(1) $\tsimplex\subseteq$$\Psi(\tau(b_1,a,z),
\tau(b_2,a,z),\cdots,\tau(b_k,a,z))$ and

(2) $\Psi(\tau(b_1,a,z),\tau(b_2,a,z),\cdots,\tau(b_k,a,z))
\subseteq\tsimplex$.

\

First, we prove (1). It suffices to show that any belief state
$b'$ in $\tsimplex$ must belong to the simplex $\Psi$. Since $b'$
is in $\tsimplex$, there must exist a belief state $b$ in $\sB$
such that $b'=\tau(b,a,z)$. We define a few constants as follows.
\begin{itemize}
\item For any $i\in\{1,\cdots,k\}$, $C_{b_i}$ is the probability
of observing $z$ when action $a$ is executed in belief state
$b_i$. Formally, $C_{b_i}=\sum_{\ns,s}P(z|\ns,a)P(\ns|s,a)b_i(s)$.
\item $C_b$ is the probability of observing $z$  when action $a$
is performed in $b$. Formally,
$C_b=\sum_{\ns,s}P(z|\ns,a)P(\ns|s,a)b(s)$. \item For any
$i\in\{1,\cdots,k\}$, define $\lam_i=C_{b_i}/C_b$.
\end{itemize}
Given these constants, we are going to prove
$b'=\sum_i\lam_i\tau(b_i,a,z)$. If this is true, i.e., $b'$ can be
represented as a convex combination of the vectors in the basis,
(1) is proven.

We start from $b'=\tau(b,a,z)$.  If $\tau(b,a,z)$ is replaced by
its definition, for a state $\ns$,
\begin{eqnarray*}
b'(\ns) = \frac{1}{C_b}\sum_s P(z|\ns,a)P(\ns|s,a)b(s)
\end{eqnarray*}
By the definition of belief state $b_i$, we can rewrite the above
equation as
\begin{eqnarray*}
b'(\ns) = \frac{1}{C_b}\sum_s\sum_{i\in\{1,\cdots,k\}}
    P(z|\ns,a)P(\ns|s,a)b_i(s).
\end{eqnarray*}
Trivially,
\begin{eqnarray*}
b'(\ns)=\frac{1}{C_b}\sum_s C_{b_i}
        \frac{\dstyle\sum_iP(z|\ns,a)P(\ns|s,a)b_i(s)}
                {\dstyle C_{b_i}}.
\end{eqnarray*}
By the definition of $\tau(b_i,a,z)$, rewriting the above
equation, we have
\begin{eqnarray*}
b'(\ns)=\sum_i(\frac{C_{b_i}}{C_b})\tau(b_i,a,z)(\ns) .
\end{eqnarray*}
By the definition of $\lam_i$, the above equation yields
\begin{eqnarray*}
b'(\ns)=\sum_i \lam_i\tau(b_i,a,z)(\ns).
\end{eqnarray*}
If $b'$ and $\tau(b_i,a,z)$ are regarded as column vectors, the
above equation means
\begin{eqnarray*}
b' = \sum_i\lam_i\tau(b_i,a,z).
\end{eqnarray*}
Therefore, we prove that if there is a belief state $b$ such that
$b'=\tau(b,a,z)$, $b'$ can be represented as a convex combination
of the vectors in the basis. This means $b'$ must be in the
simplex $\Psi$.

\

To prove (2), we prove that any belief state $b'$ in the simplex
$\Psi$ must be in the subset $\tsimplex$. It suffices to show that
there exists a belief state $b$ in $\sB$ such that $b'=\tau(b,a,z)$.

Since $b'$ is in $\Psi$,
there must exist a set of nonnegative $\lam_i$s such that
$b'=\sum^k_{i=1}\lam_i\tau(b_i,a,z)$. If we replace
$\tau(b_i,a,z)$ by its definition, then: for a state $\ns$,
\begin{eqnarray*}
b'(\ns) = \sum_i \lam_i \frac{\sum_sP(z|\ns,a)P(\ns|s,a)b_i(s)}
    {\sum_{\ns, s}P(z|\ns,a)P(\ns|s,a)b_i(s)}.
\end{eqnarray*}
If we denote $\sum_{\ns, s}P(z|\ns,a)P(\ns|s,a)b_i(s)$ by a
constant $C_{b_i}$, then
\begin{eqnarray*}
b'(\ns)=\sum_i\sum_sP(z|\ns,a)P(\ns|s,a)b_i(s)\frac{\lam_i}{C_{b_i}}.
\end{eqnarray*}
Exchanging the summation order of $i$ and $s$ and making use of
the definition of $b_s(i)$, we have
\begin{eqnarray*}
b'(\ns)=\sum_s\frac{\lam_s}{C_{b_s}}P(z|\ns,a)P(\ns|s,a).
\end{eqnarray*}
We define a belief state $b$ as follows: for any $s$,
\begin{eqnarray*}
b(s)=\frac{\dstyle {\lam_s}/{C_{b_s}}}
    {\dstyle \sum_s{\lam_s}/{C_{b_s}}}.
\end{eqnarray*}
It can be seen that
\begin{eqnarray*}
b'(\ns)=\frac{ \sum_sP(z|\ns,a)P(\ns|s,a)b(s)}
      { \sum_{\ns,s} P(z|\ns,a)P(\ns|s,a)b(s) }.
\end{eqnarray*}
Therefore, we proved that for any $b'$ in $\Psi$ there exists a
belief state  $b$ such that $b'=\tau(b,a,z)$. Consequently,
$b'\in\tsimplex$. \qed

\setcounter{theo}{5}

\begin{theo}
%\label{th:strictThreshold}
If $\max_{b\in\tau(\sB)}|V^{\tau(\sB)}_{n}(b)-V^{\tau(\sB)}_{n-1}(b)|
\le {\epsilon(1-\lam)}/{(2{\lam}^2|\sZ|)}$, then the
$V^{\tau(\sB)}_{n-1}$-improving policy is $\epsilon$-optimal
over the entire belief space $\sB$.
\end{theo}

\noindent {\bf Proof:} It suffices to show
$\max_{b\in\sB}|V_{n+1}(b)-V_n(b)|\le\epsilon(1-\lam)/(2\lam)$.
For any $b\in\sB$,
$$
\begin{array}{llr}
 &|V_{n+1}(b)-V_n(b)| & \\
=&|\max_a\{r(b,a){+}\lam\sum_z V^\tsimplex_n(\tau(b,a,z))\}
{-}\max_a\{r(b,a){+}\lam\sum_zV^\tsimplex_{n-1}(\tau(b,a,z) )\}|
 & (1)\\
\le&
|r(b,a^\ast)+\lam\sum_zV^{\tau(\sB,a^\ast,z)}_n(\tau(b,a^\ast,z))
  -r(b,a^\ast)-\lam\sum_zV^{\tau(\sB,a^\ast,z)}_{n-1}(\tau(b,a^\ast,z))|
& (2)\\
\le & |\lam\sum_z(V^{\tau(\sB,a^\ast,z)}_n(\tau(b,a^\ast,z))
    -V^{\tau(\sB,a^\ast,z)}_{n-1}(\tau(b,a^\ast,z)))|
& (3) \\
\le&\lam|\sZ|\max_z|V^{\tau(\sB,a^\ast,z)}_n(\tau(b,a^\ast,z))
    -V^{\tau(\sB,a^\ast,z)}_{n-1}(\tau(b,a^\ast,z))|
& (4) \\
\le & \lam|\sZ|\epsilon(1-\lam)/(2\lam^2|\sZ|)
& (5) \\
\le & \epsilon(1-\lam)/(2\lam) & (6)
\end{array}
$$
\noindent where
\begin{itemize}
\item At Step (1), value functions are replaced by their
definitions; \item At Step (2), $a^\ast$ is the
$V^\tsimspace_n$-improving action for $b$ but it is not
necessarily $V^\tsimspace_{n-1}$-improving; \item At Step (5), the
given condition is used; \item Other steps are trivial.   \qed
\end{itemize}


\section{Informative POMDPs: An Elevator Problem}
\label{s:app.infoPOMDPs}

This appendix describes a 96-state informative POMDP and empirical
results of value iteration over $\psimspace$. The problem is
adapted from existing research \cite{CYZ99}. Our purpose is to
show that restricted value iteration is able to solve larger
POMDPs than standard value iteration.

\subsection*{Problem Formulation}

An elevator operates in a two-floor residential building. There
are three patterns on the passengers' arrival: high arrival rate
in the first floor and low in the second floor; low arrival rate
in the first floor and high in the second floor; equal arrival
rates. As time varies from the morning to  the night in a day,
these patterns change according to a probability distribution. To
keep track of the pick-up and drop-off requests, the elevator sets
up four buttons in its control panel: two buttons record the
pick-up and drop-off requests for the first floor, two other
buttons keep the same information for the second floor. The
elevator is also aware of which floor it is on. In order to
fulfill the requests at a floor, the elevator first moves upwards
or downwards so that it reaches the floor; then, the elevator
stays at the floor until the passengers finish entering or
exiting. The objective of the elevator is to minimize certain
penalty or cost in the long run.

The problem can be formulated into a POMDP framework. A state
consists of six components: the arrival pattern, the pick-up
requests for two floors, the drop-off requests for two floors and
the elevator's position. We use six variables to denote the
components respectively. A state is an assignment to all the
variables. The arrival pattern takes on three possible values for
three different patterns. If there are passengers waiting in the
lobby of the first floor, the pick-up request is set; otherwise,
it is unset. If there are passengers in the elevator intending to
get off at the first floor, the drop-off request for the first
floor is set; otherwise, it is unset. Similarly, for the second
floor, the variables for the pick-up/drop-off requests can be set
accordingly. If the elevator is at the first floor, its position
is set to first; for the second floor, its position is set to
second. The number of states is $3*2*2*2*2*2=96$. Each observation
has five components; it has the same components as a state except
the arrival pattern. There are as many as $2*2*2*2*2=32$
observations. The elevator may execute one of three actions,
namely $\verb+go.up+$, $\verb+go.down+$
 and $\verb+stay+$. The restriction is, when it is
at the first floor, it cannot perform $\verb+go.down+$;
 when it is at the second floor, the action
$\verb+go.up+$ cannot be performed.

The uncertainty stems from the probabilities of the changes of the
arrival patterns. When the elevator executes $\verb+go.up+$, each
component evolves as follows. The arrival pattern changes
according to a predetermined probability distribution. The
components for pick-up/drop-off requests remain. The position
changes from first to second. The effects of the action
$\verb+go.down+$ can be described similarly. When the elevator
performs the action $\verb+stay+$, the arrival pattern changes
similarly. All the requests at the floor are fulfilled and the
corresponding variables are reset. For instance, if a passenger
would like to get off at the first floor, when the elevator at the
first floor performs stay, the passenger is able to get off. We
say that the elevator fulfills the drop-off requests for the first
floor. For another instance, if passengers like to enter the
elevator at the second floor, they can do so only when the
elevator performs action $\verb+stay+$ at the second floor. We say
the pickup request at the second floor is fulfilled in this case.
It is also allowable for the elevator to fulfill two requests at
one time point. For example, if there are both pick-up and
drop-off requests at the first floor, when the elevator performs
action $\verb+stay+$, the passengers can enter and exit within one
time point. We say it fulfills two requests. Note that only when
an action $\verb+stay+$ is performed, the elevator can fulfill its
request. Since the variable of arrival pattern changes at any time
moment, the elevator changes its states probabilistically after
performing any action.

The elevator is informed of partial knowledge of its state
transition. After the elevator performs an action, it knows the
changes of components of its states: variables pick-up and
drop-off for each floor and its position. However, since it does
not know the arrival pattern and it is a component of the state,
the observations cannot reveal the identities of the states. This
is the partial observability. However, since there are only three
possible arrival patterns, each observation reveals that the
elevator must be in only three possible states. Therefore, the
POMDP is informative.

The performance of the elevator can be measured in different ways
for diverse applications. We define a measure to minimize the
unsatisfactory degree of the service the elevator provides. We
encode this in our reward model. At any time point, the elevator
serves one of four requests: pick-up requests at the first/second
floor, drop-off requests at the first/second floor. After
performing an action, if any of these 4 requests is unfulfilled,
the elevator receives a penalty of 0.25. For instance, if the
elevator un-fulfills either the pick-up or drop-off request(if
they are set) at the first floor, it receives a penalty of
$0.25*2= 0.5$. The objective of the elevator is to minimize total
discounted penalty in a long run.

For convenience, we use A.$i$ to denote arrival patterns for
$i=1,2,3$. In our experiments, the transition probabilities are
set as in the following table. Basically, each pattern remains
fixed with probability 0.90 and changes to another with 0.05.
\begin{center}
\begin{tabular}{|c|ccc|}
    \hline
   & A.$1$   & A.$2$   & A.$3$  \\ \hline
A.$1$ & 0.90 & 0.05 & 0.05 \\
A.$2$ & 0.05 & 0.90 & 0.05 \\
A.$3$ & 0.05 & 0.05 & 0.90  \\ \hline
\end{tabular}
\end{center}

\subsection*{Empirical Studies}

We collect the time costs and the actual number of vectors
generated at each iteration of algorithms $\verb+VI+$,
$\verb+ssVI+$, $\verb+infoVI+$ and $\verb+infoVIPB+$ referring to
$\verb+infoVI+$ integrated with a point-based procedure
\cite{ZhangW01}. The results are presented in Figure
\ref{f:elevatorExp}.

The first chart in the figure shows the time costs against the
iterations. The algorithms are set to compute a 0.1-optimal value
function. For $\verb+infoVIPB+$, we exclude the iterations for
point-based improvements. Overall, we see that $\verb+VI+$ and
$\verb+ssVI+$ by no means can solve the problem, $\verb+infoVI+$
is likely to solve it given sufficient time and $\verb+infoVIPB+$
is able to solve it easily. When $\verb+infoVIPB+$ runs, it uses
the loose stopping criterion. This is because if the strict one is
used, the threshold is close to the round-off precision parameter.

For the first seven iterations, $\verb+ssVI+$ takes 190,000
seconds, $\verb+infoVI+$ only 32 seconds. The performance
difference is drastic. As $\verb+infoVI+$ proceeds, it takes about
1,100 seconds for one iteration. It is evident that
$\verb+infoVI+$ is able to compute a near optimal value function
if given sufficient time. When the point-based technique is
integrated, $\verb+infoVIPB+$ is able to terminate in 94 seconds
after five steps of DP updates over $\psimspace$. Since most of
these algorithms cannot terminate within a reasonable time limit,
we compare the data on the 6th iteration among them. This is the
last iteration we are able to gather statistics for $\verb+VI+$.
For this iteration, $\verb+VI+$ takes 76,000 seconds,
$\verb+ssVI+$ 6,000 seconds, $\verb+infoVIPB+$ only 8 seconds.

\begin{figure}
\begin{center}
\begin{tabular}{ll}
\makebox{
        \epsfxsize=6.5cm
        \epsffile{results/regionvi/elevator/logtime.eps}
}
&\makebox{
        \epsfxsize=6.5cm
        \epsffile{results/regionvi/elevator/logsize.eps}
}
\end{tabular}
\end{center}
\caption{Performance of {\tt VI}, {\tt ssVI}, {\tt infoVI} and
{\tt infoVIPB} on Elevator} \label{f:elevatorExp}
\end{figure}

The second chart in Figure \ref{f:elevatorExp} depicts the number
of vectors generated at each iteration for the tested algorithms.
For $\verb+ssVI+$, we collect the sum of the numbers of vectors
representing value functions over $|\sA|\cdot|\sZ|$
$\tau$-simplices. For $\verb+infoVI+$ and $\verb+infoVIPB+$, we
collect the sum of the numbers of representing vectors for $|\sZ|$
$\phi$-simplices. This is because for this problem the observation
models are independent of the actions.

From the chart, we see that $\verb+VI+$ generates significantly
more vectors than $\verb+ssVI+$ and $\verb+infoVI+$. In our
experiments, after $\verb+infoVIPB+$ terminates, it produces 1,132
vectors. For the same reason as above, we compare the numbers of
the vectors after the 6th iterations for these algorithms. After
the iteration, $\verb+VI+$ generates 12,000 vectors. For
$\verb+ssVI+$ and $\verb+infoVI+$, this number is 252 and 136
respectively. As DP updates proceed, it is conceivable that the
number of vectors generated by $\verb+VI+$ will increase sharply
and hence the DP updates are extremely inefficient. For
$\verb+infoVIPB+$, since the final number of generated vectors are
rather small, together with the fact that point-based improvement
effectively reduces the number of iterations over the
$\psimspace$, it is possible to compute a near optimal value
function within a rather small time limit as it turns out.

\bibliographystyle{theapa}
\bibliography{zhang05}

\end{document}
