\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{
      \hbox to 5.78in { {#1} \hfill #2 }
      \vspace{4mm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{2mm}
      \hbox to 5.78in { {\em #3 \hfill #4} }
    }
  }
  \end{center}
  \vspace*{4mm}
}
\DeclareMathOperator*{\argmax}{argmax}
\newcommand{\lecture}[5]{\handout{#1}{#2}{#3}{#4}{#5}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

% 1-inch margins, from fullpage.sty by H.Partl, Version 2, Dec. 15, 1988.
\topmargin 0pt
\advance \topmargin by -\headheight
\advance \topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in
\textwidth 6.5in

\parindent 0in
\parskip 1.5ex
%\renewcommand{\baselinestretch}{1.25}

\begin{document}

\lecture{ACRL (16-899C, S09)}
{Lecture \#15 (March 12, 2009)}{Lecturer: Drew Bagnell}
{Scribe: Andrew Maas}{POMDPs Continued and Function Approximation Strategies}

\section{Introduction}
We will continue our discussion of POMDPs and some basic strategies
for solving them. After reviewing some of the POMDP basics we will
move into a more detailed discussion on methods for approximating
value funcitons.

\section{POMDP Review}
\begin{itemize}
\item
Last time we discussed the basic structure of POMDPs. 
\item
A fundamental
strategy is to convert the POMDP to an Information-State(I-State)
MDP. There are several simple I-states which are not practical. One we
discussed which is practical is the belief I-state. The belief I-state
is a distribution over states condintioned on the history. 
\item
We can solve all adaptive control problems optimally! Given our
unknown parameters $\theta$, we augment our state to include $\theta$.
$\theta$ has no dynamics so $\theta_t = \theta_{t+1}$. We then solve
the I-state MDP over the belief state which includes $\theta$ (our
augmented state).
\item
We can ``solve'' all POMDPs using various algorithms:
\begin{itemize}
  \item
    Discretize the I-state annd use value iteration. Because the
    dimension of the I-state is approximately equal to the number of
    states, this algorithm is exponential in the number of states. It is
    also $O(T)$, where $T$ is the total time.
  \item
    Policy iteration over trees describing policies. This is
    $O(exp(T))$ in the worst case, though it might be better in
    practice.
  \item
    We can solve a special case: Linear Quadratic Gaussian (LQG). 
  \item
    Bar-Shalom paper/method is interesting. You should take a look at it.
    
\end{itemize}
\end{itemize}

\section{Approximate Strategies: Receeding Horizon Control}
Making a policy is too much work. We move now to talking about various
methods for side-stepping building a complete policy.

We can use the ``poor man's policy'' where we re-plan at
every timestep to choose our action. Receeding Horizon Control is an
extension of this approach where we plan for only a short window, and
then execute the planned action before replanning. This approach is
used in chess and ZMP preview controllers.

Here are some other strategies we can use which will allow us to avoid
building a complete policy:
\begin{enumerate}
  \item
    Do certainty equivalence even though it's wrong. This allows for
    ``passive'' active learning, where we learn new things because our
    assumption makes us take incorrect actions.
  \item
    Compute the current belief state and select the action which
    maximizeds the one-step reward: $\argmax_a \sum_s b(s)r(s,a) + 
    \tilde{v}(b')$ where $\tilde{v}(b') = \sum_{s'} v(s')b'(s')$
    and $b'$ is the belief in the subsequent timestep.

    This algorithm only explores if it will help you right now.  This
    doesn't really seek to resolve uncertainty. The resulting value
    approximation is optimistic about the true value, it is always $\geq v(b)$
  \item
    Another optimistic approach is to assume that all uncertainty will
    resolve in your favor. This is the approach used by the D*
    algorithm. At every step will either learn something, or assume
    the best thing happened. This approach is very good at compressing
    the belief state (reducing apparent uncertainty)
  \item
    Alternatively we could assume that all uncertainty resolve against
    us. This produces a pessimistic estimate, in which our estimated
    values are always $\leq v(b)$
  \item
    Another pessimistic policy is to assume the policy $\pi$ is fixed
    at the next timestep. We can then do one step lookahead to choose
    an action. Thus we choose $\argmax_a \sum_s b(s)r(s,a) + 
    \sum_{s'} b(s')v^{\pi}(s')$ where $v^{\pi}$ is the value function
    under the policy which we assume is fixed. Bar-Shalom paper is
    a special case of this approach where the value estimate is
    quadratic.

    An extension to the above approach is to optimize over $\pi$ while
    doing the above. For example, we might take the max over multiple
    $\pi$s, or tweak $\pi$ for a particular $b$
  \item
    We can also push back thee horizon (e.g. 2-step lookahead). This
    is exponential in the number of lookahead steps.
\end{enumerate}
\section{Value Function Approximation}
Now we want to build up a policy instead of doing receeding horizon control.
\begin{itemize}
\item
  Sum of linear basis functions (future discussion)
\item
  DDP. Lots of dimensions. Very local.
\item
  Grid-based. There are quite a few options such as: adaptive
  resolution, random grids, etc. Grids in general have dimensionality
  issues.
\end{itemize}
\end{document}
