\batchmode

\input epsf

\documentstyle[jair,twoside,11pt,theapa]{article}
\makeatletter

\jairheading{14}{2001}{29-51}{6/00}{2/01}
\ShortHeadings{Speeding Up Value Iteration in POMDPS}
{Zhang \& Zhang}
\firstpageno{29}




























\newtheorem {defi}{Definition}

\newtheorem {theo}{Theorem}

\newtheorem {cor}{Corollary}

\newtheorem {pro}{Proposition}

\newtheorem {lem}{Lemma}

\newtheorem {con}{Conjecture}

\newcommand {\cs}{\bigoplus}

\newcommand {\la}{\leftarrow}

\newcommand {\al}{\alpha}

\newcommand {\bt}{\beta}

\newcommand {\ns}{s'}

\newcommand {\no}{z}

\newcommand {\na}{a_{\mbox{\tiny +}}}

\newcommand {\pa}{a_{\mbox{\small -}}}

\newcommand {\sS}{{\cal S}}

\newcommand {\sM}{{\cal M}}

\newcommand {\sZ}{{\cal Z}}

\newcommand {\sA}{{\cal A}}

\newcommand {\sV}{{\cal V}}

\newcommand {\sB}{{\cal B}}

\newcommand {\sU}{{\cal U}}

\newcommand {\sW}{{\cal W}}

\newcommand {\pr}{P(\no, \ns|s, a)}

\makeatother
\newenvironment{tex2html_wrap}{}{}
\newwrite\lthtmlwrite
\def\lthtmltypeout#1{{\let\protect\string\immediate\write\lthtmlwrite{#1}}}%
\newbox\sizebox
\begin{document}
\pagestyle{empty}
\stepcounter{section}
\stepcounter{section}
\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal S}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline992: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal Z}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline994: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal A}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline996: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal B}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1036: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1042: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^{\pi}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1044: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^{\pi}(b)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1048: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\label{vpib}
V^{\pi}(b)=E_{\pi, b}[\sum_{t=0}^{\infty}\lambda ^tr_t],
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$r_t$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1052: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\lambda$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1056: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$0{\leq}\lambda{<}1$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1058: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pi^*$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1060: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^{\pi^*}(b){\geq}V^{\pi}(b)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1062: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^*$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1068: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1070: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{displaymath}V^{\pi}(b) + \epsilon \geq V^{*}(b) \hspace{0.4cm} 
        \forall b \in {\cal B}.\end{displaymath}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$b^a_{z}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1082: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$b^a_{z}(s')$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1086: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\label{b+}
   b^a_{z}(s') =\frac{\sum_{s} P(z, s'|s, a)b(s)}
        {P(\no|b, a)},
   \end{eqnarray}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$P(z , \ns|s, a){=}P(\no|s', a)P(\ns|s, a)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1088: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$P(\no|b, a){=}\sum_{s, s'}P(z , \ns|s, a) b(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1090: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{eqnarray}\label{vi}
TV(b) = \max_a[r(b, a) + \lambda \sum_{z}
                P(\no|b, a)V(b_{z}^a)]  \hspace{0.4cm}  \forall b \in {\cal B} 
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$r(b, a)=\sum_sr(s, a)b(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1104: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{eqnarray}% latex2html id marker 124
\label{v-improve}
\pi(b) = \arg \mbox{ }\max_a[r(b, a) + \lambda \sum_{z}
                P(\no|b, a)V(b_{z}^a)] \hspace{0.4cm}  \forall b \in {\cal B}.
\end{eqnarray}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V_0$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1118: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{eqnarray*}V_{n} = TV_{n-1}.
 \end{eqnarray*}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V_n$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1120: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\max_b|V_{n}(b)-V_{n-1}(b)|$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1126: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\epsilon(1-\lambda)/2\lambda$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1128: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$|\sS|$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1136: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\alpha$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1138: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\beta$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1140: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal V}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1142: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal U}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1144: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{displaymath}f(b) =\max_{\alpha \in {\cal V}} \alpha{\cdot}b \hspace{0.4cm} \forall b
                \in {\cal B},\end{displaymath}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\alpha{\cdot}b$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1154: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\alpha{\cdot}b{=}\sum_s\alpha(s)b(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1160: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal V}(b)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1166: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$R(\alpha,{\cal V})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1174: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\overline{R}(\alpha,{\cal V})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1176: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{eqnarray*}R(\alpha,{\cal V})= \{b\in{\cal B}|\alpha{\cdot}b>\alpha'{\cdot}b, \ \forall
\alpha'\in{{\cal V}\backslash \{\alpha\} } \}
\\ 
\overline{R}(\alpha,{\cal V})= \{b\in{\cal B}|\alpha{\cdot}b\ge\alpha'{\cdot}b, \
\forall
\alpha'\in{{\cal V}\backslash \{\alpha\} } \}
\end{eqnarray*}
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{center}
\makebox{
        \epsfxsize=6cm
        \epsffile{represent.ps}
}
\end{center}

\label{represent}
\end{figure}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\alpha_1$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1194: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\alpha_2$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1196: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\alpha_3$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1198: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\alpha_4$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1200: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\alpha_i{\cdot}b$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1202: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$T{\cal V}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1230: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\max_b|{\cal U}(b) - {\cal V}(b)|$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1240: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{tabbing}
xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=  \kill
 \> $\verb+VI+({\cal V}, \epsilon)$: \\ 
\>1. \> $\delta \leftarrow\epsilon(1-\lambda)/2\lambda$. \\ 
\>2. \> {\bf do} \{  \\ 
\>3. \>\>  ${\cal U} \leftarrow \mbox{\verb+DP-UPDATE+}({\cal V})$. \\ 
\>4.   \> \> $r \leftarrow \max_b|{\cal U}(b) - {\cal V}(b)|$;  \\ 
\>5.\>\>  {\bf if } ($r> \delta$)      ${\cal V} \leftarrow {\cal U}$. \\ 
\>6. \> \} {\bf while} ( $r > \delta$).  \\ 
\>7.\> {\bf return} ${\cal U}$.
\end{tabbing}

\label{vi.algo}
\end{figure}
}

\stepcounter{section}
\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$b^z_a$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1268: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\beta_{a, z}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1276: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\beta_a$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1280: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{eqnarray*}\beta_a(s)= r(s,a)+\gamma
        \sum\limits_{z,s'}P(s', z|s,a)\beta_{a,z}(s'), \forall s\in{\cal S}.
\label{e:beta-a}
\end{eqnarray*}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\verb+backup+(b,{\cal V})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1286: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\verb+backup+(b,{\cal V})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1288: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\verb+backup+(b,{\cal V})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1296: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\verb+backup+(b,{\cal V})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1304: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\verb+backup+(b',{\cal V})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1306: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}[t] 
\begin{tabbing}
xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=  \kill
 \> $\verb+VI1+({\cal V}, \epsilon)$: \\ 
\>1. \> $\delta \leftarrow\epsilon(1-\lambda)/2\lambda$. \\ 
\>2. \> {\bf do} \{  \\ 
\>3. \>\>  ${\cal U} \leftarrow \mbox{\verb+DP-UPDATE+}({\cal V})$. \\ 
\>4.   \> \> $r \leftarrow \max_b|{\cal U}(b) - {\cal V}(b)|$;  \\ 
\>5.\>\>  {\bf if } ($r> \delta$)      ${\cal V} \leftarrow$ 
			{\tt POINT-BASED-VI}$({\cal U}, \delta)$. \\ 
\>6. \> \} {\bf while} ( $r > \delta$).  \\ 
\>7.\> {\bf return} ${\cal U}$.
\end{tabbing}

\begin{tabbing}
xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=  \kill
 \> \verb+POINT-BASED-VI+$({\cal U}, \delta)$: \\ 
\>1. \>   {\bf do}  \{  \\ 
\>2.   \>\>     ${\cal V} \leftarrow {\cal U}$. \\  
\>3.\>\>  	${\cal U}$ $\leftarrow $ {\tt POINT-BASED-DPU}$({\cal V})$\\  
\>4.\>  \} {\bf while} ({\tt STOP}$({\cal U}, {\cal V}, \delta)$= false). \\ 
\>5.\> {\bf return} ${\cal V}$.
\end{tabbing}



\label{vi1}
\end{figure}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{figure}[t]
\begin{center}
\makebox{
        \epsfxsize=12cm
        \epsffile{idea.ps}
        \epsfxsize=2cm
}
\end{center}

\label{idea}
\end{figure}
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V{\leq}U$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1358: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V(b){\leq}U(b)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1360: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V{\leq}TV$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1366: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{lem}The operator $T$ is isotone in the sense that 
for any two value functions $V$ and $U$, $V{\leq}U$ implies
$TV{\leq}TU$. $\Box$
\end{lem}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V{\leq}TV{\leq}V^*$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1394: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$V^*(b)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1398: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{lem}% latex2html id marker 273
\label{ui.property}
Consider two value functions $V$ and $U$.
If $V$ is  uniformly improvable and
$V{\leq}U{\leq}TV$, then $U$ is also uniformly improvable.
\end{lem}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$TV{\leq}TU$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1416: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$U{\leq}TV$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1418: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$U{\leq}TU$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1420: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\Box$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1424: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{cor}% latex2html id marker 283
\label{ui.cor}
If value function $V$ is uniformly improvable, so
is $TV$. $\Box$ 
\end{cor}
}

\stepcounter{section}
\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\tt w}(\alpha)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1438: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\tt backUpWitnessPoints}({\cal V})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1440: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal U} \leftarrow \emptyset$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1442: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\beta \in {\cal V}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1444: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\alpha \leftarrow {\tt backup}({\tt w}(\beta), {\cal V})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1446: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\alpha \notin {\cal U}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1448: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\tt w}(\alpha)  \leftarrow  {\tt w}(\beta) $}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1450: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal U} \leftarrow {\cal U} 		
			\cup \{\alpha\}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1452: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\tt w}(\beta)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1458: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal U}(b){<}{\cal V}(b)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1478: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal U}(b){<}\beta{\cdot}b$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1484: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\tt backUpLPPoints}({\cal U}, {\cal V})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1492: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$b \leftarrow {\tt dominanceCheck}(\beta, {\cal U})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1496: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$b \neq {\tt NULL}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1498: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\alpha \leftarrow {\tt backup}(b, {\cal V})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1500: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\tt w}(\alpha)  \leftarrow b $}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1502: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\alpha{\cdot}b{=}T{\cal V}(b)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1536: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$T{\cal V}(b){\geq}{\cal V}(b)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1540: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal V}(b){\geq}\beta{\cdot}b$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1542: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\beta{\cdot}b{>}{\cal U}(b)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1544: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\alpha{\cdot}b{>}{\cal U}(b)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1546: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal U}(b){\geq}\beta{\cdot}b$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1560: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\tt dominanceCheck}(\beta, {\cal U})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1572: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\alpha(s){\geq}\beta(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1580: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\tt LP}(\beta, {\cal U})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1586: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$(\beta, {\cal U})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1592: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\sum_s\beta(s)b(s) \geq x{+}
				\sum_s\alpha(s){\cdot}b(b)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1602: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\alpha{\in}{\cal U}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1604: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\sum_sb(s) = 1$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1606: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$b(s) \geq 0$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1608: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$({\cal V})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1612: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal U} \leftarrow {\tt backUpWitnessPoints}({\cal V})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1614: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$|\sV|$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1620: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$|T\sV|$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1622: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$|T\sV|{+}|\sV|$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1624: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$|T\sV|+1$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1626: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$|\sU|{+}|\sV|$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1636: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{displaymath}\max_{\alpha \in {\cal U}}|{\cal U}({\tt w}(\alpha)) - {\cal V}({\tt w}(\alpha))| \leq \delta_1\delta.\end{displaymath}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\delta_1\delta$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1644: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\delta$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1646: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\delta_1$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1648: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\sV_n$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1652: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal V}'_n$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1654: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{lem}% latex2html id marker 375
\label{lem.start}
Let $m{=}\min_{s, a}r(s, a)$, $c=m/(1-\lambda)$, and $\alpha_c$ be the vector whose
components are all $c$. Then the singleton set $\{\alpha_c\}$ is uniformly improvable.  
\end{lem}
}

{\newpage
\clearpage
\samepage \begin{eqnarray*}TV(b) &=& \max_a[r(b, a) + \lambda \sum_{z}
                P(\no|b, a)V(b_{z}^a)]  \\ 
	&=& \max_a[r(b, a) + \lambda \sum_{z}
                P(\no|b, a)c]  \\ 
	&=& \max_a[r(b, a) + \lambda m/(1-\lambda)]  \\ 
	&\geq& m + \lambda m/( 1-\lambda)  \\ 
	&=&  m/( 1-\lambda) = V(b).	
\end{eqnarray*}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\max_b({\cal U}(b){-}{\cal V}(b))$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1698: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$(\alpha, {\cal V})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1702: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$|{\cal Z}|$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1710: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$|\sA|$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1712: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$10^{-6}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1722: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$T'{\cal V}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1726: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal V}(b){\leq}T'{\cal V}(b){\leq}T{\cal V}(b)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1732: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\cal V} \cup {\cal U}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1744: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{section}
\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\delta=\epsilon(1-\lambda)/2\lambda$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1760: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\delta/2$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1762: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$|{\cal A}|$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1776: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
\stepcounter{section}
\stepcounter{section}

\end{document}
