\NeedsTeXFormat{LaTeX2e}
\documentclass[pdf,frames]{prosper}
% Other prosper themes
%  frames
%  blends
%  gyom
%  mancini
%  nuance gris
%  fyma
%  white cross
%  wj
%  rico

\usepackage{epsfig}
\usepackage{amsbsy}
\usepackage{rotating}
\usepackage{graphicx}
\usepackage{amsbsy}
\usepackage{epsfig}
\usepackage{natbib}

\title{Reinforcement Leanring in POMDP's via Direct Gradient Ascent}
\subtitle{ }
\author{J. Baxter \& P.L. Bartlett\\
        Australian National University\\
        ICML 2000\\
        presented by Matt Garden}
\date{27 Feb 2006}
\institution{COMP-765, McGill University}
\email{mgarden@cim.mcgill.ca}
\slideCaption{COMP-765, Baxter \& Bartlett, 2000}

\begin{document}

\maketitle

% \begin{slide}{Outline}
% \begin{itemize}
% \item Key ideas
% \item Approximating the gradient
% \item Gradient ascent
% \item Results
% \item Discussion
% \end{itemize}
% \end{slide}

\begin{slide}{In other approaches $\dots$}
\begin{itemize}
\item Previous approaches to train approximate $V(\cdot)$
\item $\forall \epsilon > 0\:\mathrm{there}\:\exists V$ such that 
\end{itemize}
\begin{eqnarray}
\mathrm{max}_i|V(i) - V^*(i)| = \epsilon \label{eqn:value-bound}\\
\eta = \eta^\ast - \frac{2\alpha\epsilon}{1 - \alpha} \label{eqn:eta-bound}
\end{eqnarray}
\noindent where $\eta =$ expected discounted reward.
\begin{itemize}
\item This is often used as the motivation for using a $V(\cdot)$-approximation technique.
\end{itemize}
\end{slide}

\begin{slide}{$\dots$ but}
\begin{itemize}
\item These approaches do not guarantee good performance in the resulting policy, $\because$
\item They minimize an $l_2 $ rather than the $l_\infty$ norm the bounds are based on.
\item Bound on performance is limited by $\epsilon$, but
\item ``smallest achievable $\epsilon$ will be very large in practice'', so
\item The bound on $\eta$ is not very helpful.
\end{itemize}
\end{slide}

\begin{slide}{$\dots$ so instead}
\begin{itemize}
\item ``What really matters is the ordering of states given by $V(\cdot)$, not the quality of the approximation.''
\item Instead of minimizing some distance from the true value function, just maximize the expected reward directly.
\item Parameterize the reward and use gradient ascent to search for the best parameters.
\end{itemize}
\end{slide}

\begin{slide}{Present approach}
\begin{itemize}
\item Parameterize the expected average reward as $\eta(\theta), \theta \in \mathbf{R}^K$
\item Compute $\nabla\eta(\theta)$ and incrementally move $\theta$ along the gradient
\item \textbf{Note}: A greedy policy based on $V(\theta)$ will not in general give a differentiable $\eta(\theta)$
\item therefore the policy must be probabilistic
\end{itemize}
\end{slide}

\begin{slide}{Contributions}
\begin{itemize}
\item \texttt{GPOMDP}: Algorithm for computing an approximation of $\nabla\eta(\theta)$
\item \texttt{CONJPOMDP}: Optimization procedure:  Choose an ``uphill'' direction and search for a local maximum.
\item \texttt{GSEARCH}: Line-search: search for a local maximum in a given direction.
\item Method doesn't require a model of transition and observation probabilities.
\end{itemize}
\end{slide}

\begin{slide}{POMDP framework}
\begin{itemize}
\item $n$ states $\mathcal{S} = \{1,..,n\}$ with rewards $r(i)$
\item $N$ actions $\mathcal{U} = \{1,..,N\}$
\item $M$ observations $\mathcal{Y} = \{1,..,M\}$ generated by $\nu_y(i) = \mathrm{Pr}(y|i)$
\item Policy $\mu_u(\theta,y) = \mathrm{Pr}(u|\theta,y)$ (randomized policy)
\item To behave optimally, input to policy must be a list of \emph{all} observations (more commonly this would be a belief, especially when iterating for $10^6$ steps).
\end{itemize}
\end{slide}

\begin{slide}{$\nabla\eta(\theta)$ and expected average reward}
\begin{itemize}
\item If $P$ is the (expected) transition matrix and $\pi$ is the stationary distribution for the Markov Chain for the problem,
\item $\eta(\theta) = \pi^T(\theta)r$ (expected average reward)
\item $\nabla\eta = \nabla\pi^Tr$ (gradient)
\item Without a model of transition and observation probabilities you can't calculate this directly.
\item Even if you could it could be intractable (you'd have to factor a large dense matrix).
\end{itemize}
\end{slide}

\begin{slide}{$\nabla\eta(\theta)$ and expected discounted reward}
\begin{itemize}
\item In this formulation optimizing the long-term average reward is the same as optimizing the expected discounted reward.
\item Let $J_\beta(\theta, i)$ be the expected discounted reward ($\infty$ horizon, discount $\beta$, starting at state $i$)
\item $J_\beta(\theta) = \left[ J_\beta(\theta,1),..,J_\beta(\theta,n)\right]$
\end{itemize}
\end{slide}

\begin{slide}{$\dots$}
\begin{itemize}
\item We can restate the gradient in terms of expected discounted reward
\item $\nabla\eta = (1-\beta)\nabla\pi^TJ_\beta + \beta\pi^T\nabla PJ_\beta$
\item This is useful since 
\subitem The second term can be estimated by wandering in the POMDP (call it $\nabla\beta\eta$)
\subitem As $\beta \to 1$ the first term goes to 0
\subitem The second term converges to the true $\nabla\eta$ in the limit $\beta \to 1$
\end{itemize}
\end{slide}

\begin{slide}{Notes about behaviour}
\begin{itemize}
\item As $\beta \to 1$ the bias in the estimate of the gradient decreases.
\item But, as $\beta \to 1$ it takes longer for the estimate to converge to within $\epsilon$ of the true gradient (variance increases).
\item So long as the mixing time of the markov chain is short, $\beta$ doesn't have to be ``too'' large, and you'll still get a good approximation.
\end{itemize}
\end{slide}

\begin{slide}{Estimating the gradient with \texttt{GPOMDP}}
\begin{itemize}
\item \texttt{GPOMDP} produces $\Delta_t$, an estimate of $\nabla_\beta\eta$ that converges exactly in the limit
\item Walk through a path in the POMDP, and update the estimated gradient by steps weighted by the reward received.
\end{itemize}
\end{slide}

\begin{slide}{\texttt{CONJPOMDP}}
\begin{enumerate}
\item Pick a direction along the expected discounted reward surface
\item Search for a local maximum in that direction (using GSEARCH)
\item Take a step in that direction, to $\theta'$ ($\theta' \gets \theta + \gamma\nabla\eta(\theta)$)
\subitem (The step size $\gamma$ is modified at each step)
\item If the gradient at $\theta'$ has flattened out to below some threshold then stop.
\end{enumerate}
\end{slide}

% \begin{slide}{}
% Maybe leave this out... this just says that as $\beta \to 1$ the first term in $\nabla\eta \to 0$
% \begin{itemize}
% \item $\nabla\eta = \mathrm{lim}_{\beta\to 1}\nabla_\beta\eta$
% \item $\nabla_\beta\eta = \pi^T\nabla P J_\beta$
% \end{itemize}
% \end{slide}
% 
% \begin{slide}{Variance/Bias tradeoff}
% \begin{equation}
% \parallel\nabla\eta(\theta) - \nabla\eta(\theta)\parallel \leq C\tau^\ast(\theta)(1-\beta)
% \end{equation}
% \noindent where $\tau^\ast(\theta)$ is the mixing time of the problem.
% \end{slide}

\begin{slide}{Results}
\begin{itemize}
\item Just a toy problem, and not compared with the performance of other methods.
\item Fig.2 shows that lower $\beta$ converges more quickly but with more bias (although still not a lot)
\item High $\beta$ takes a lot longer to converge but converges to an even better estimate.
\end{itemize}
\end{slide}

\begin{slide}{Discussion}
\begin{itemize}
\item How realistic are the assumptions about the mixing time? (i.e. what do real mixing times look like?)
\item Is it actually reasonable to keep track of \emph{all} observations as a vector?
\item How did they choose the feature vectors in the toy example?  How does this work in real problems?
\item How good is this performance compared to the approaches they criticize?
\item Would anything be gained by learning a model of transition and observation probabilities as we go?  What if it's costly to explore a path of hundreds of thousands of steps?
\end{itemize}
\end{slide}

\begin{slide}{}
\begin{itemize}
\item Would modifying $\mu$ as we go help in any way?
\item What if the problem has sink states?
\item Would you ever need random restarts of \texttt{CONJPOMDP}?
\end{itemize}
\end{slide}

\end{document}