%% This LaTeX-file was created by <jl> Sun May 12 14:38:41 2002
%% LyX 1.0 (C) 1995-1999 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass[dvips]{slides}
\usepackage[T1]{fontenc}
\usepackage{geometry}
\geometry{verbose,landscape}
\usepackage{amsmath}
\pagestyle{empty}
\usepackage{graphics}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\newcounter{slidetype}
\setcounter{slidetype}{0}
\newif\ifLyXsNoCenter
\LyXsNoCenterfalse
\newcommand{\noslidecentering}{
   \LyXsNoCentertrue%
}
\newcommand{\slidecentering}{
   \LyXsNoCenterfalse%
}
\newcommand{\lyxendslide}[1]{
   \ifLyXsNoCenter%
        \vfill%
   \fi%
   \ifcase \value{slidetype}%
        \or % no action for 0
        \end{slide} \or%
        \end{overlay} \or%
        \end{note}%
   \fi%
   \setcounter{slidetype}{0}
	\visible
}
\AtEndDocument{\lyxendslide{.}}
\newcommand{\lyxnewslide}[1]{
   \lyxendslide{.}
   \setcounter{slidetype}{1}
   \begin{slide}
}

\makeatother

\begin{document}


\lyxnewslide{ad}

{\par\centering Approximately Optimal Approximate Reinforcement Learning\par}

{\par\centering Sham Kakade and John Langford\par}

{\par\centering @ ICML 2002\par}


\lyxnewslide{adfa}

{\par\centering The Goal: Reinforcement Learning on LARGE state spaces\par}

What algorithms work?


\lyxnewslide{afa}

{\par\centering Current Methods\par}

\begin{enumerate}
\item Approximate value functions
\item Policy Gradient 
\end{enumerate}

\lyxnewslide{afa}

{\par\centering Questions\par}

\begin{enumerate}
\item Will the policy always improve?
\item Will the program halt?
\item Will the final policy be near-optimal?
\end{enumerate}

\lyxnewslide{afaf}

{\par\centering Approximate Value function \par}

\begin{enumerate}
\item Approximate state-action values. 
\item Derive policy from approximate values.
\end{enumerate}
\( \max _{s}|V(s)-\hat{V}(s)|\leq \epsilon \textrm{ }\,\,\Rightarrow  \) each
iteration doesn't \emph{lose} much


\lyxnewslide{afaf}

{\par\centering Policy Iteration\par}

Let \( \gamma  \) = discount factor.

Let \( \epsilon =\max _{s}|V(s)-\hat{V}(s)| \) = approximation error

Theorem: The average reward of the next policy is no more than \( O(\frac{\epsilon \gamma }{1-\gamma }) \)
worse

Note: some guarantees on (near) optimality exist.


\lyxnewslide{adfaaf}

{\par\centering Policy Gradient\par}

\( \eta (\pi )= \) average reward

Evaluate \( \frac{\partial \eta (\pi )}{\partial w} \) and optimize

Fundamentally: intertwine explore and exploit


\lyxnewslide{adf}

{\par\centering Directed exploration required\par}

\vspace{0.3cm}
{\par\centering \resizebox*{0.95\columnwidth}{!}{\includegraphics{paper/figs/thrun_game.eps}} \par}


\lyxnewslide{afdfa}

{\par\centering Policy Gradient Theorems\par}

Theorem: The policy always improves with infinitesimally small steps.

Theorem: The gradient \emph{magnitude} can be estimated quickly.

Theorem: The gradient \emph{direction} can not always be estimated quickly,
even far from the optima.


\lyxnewslide{adf}

{\par\centering Next\par}

\begin{enumerate}
\item RL terminology
\item Conservative Policy Iteration
\item Theorems
\end{enumerate}

\lyxnewslide{adfa}

{\par\centering Terminology\par}

\begin{enumerate}
\item \( \mu (s) \) = start state distribution
\item \( R(s,a) \) = reward recieved for action \( a \) in state \( s \)
\item \( V_{\pi }(s)=(1-\gamma )E\sum _{t=0}^{\infty }\gamma ^{t}R(s_{t},a_{t}) \)
= expected reward from state \( s \)
\item \( Q_{\pi }(s,a)=(1-\gamma )R(s,a)+\gamma E_{s',a\sim P(s';s,a)\pi (a|s)}V_{\pi }(s') \)
= expected reward from state \( s \) and action \( a \)
\item \( A_{\pi }(s,a)=Q_{\pi }(s,a)-V_{\pi }(s) \) = advantage of taking one action
over another
\end{enumerate}

\lyxnewslide{adf}

{\par\centering Consider update rules\par}


\[
\pi _{\textrm{new}}\leftarrow \alpha \pi '+(1-\alpha )\pi \]


\( \alpha \rightarrow 0 \) = policy gradient

\( \alpha =1 \) = policy iteration


\lyxnewslide{adfad}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\includegraphics{alpha.eps}} \par}
\vspace{0.3cm}


\lyxnewslide{adfa}

{\par\centering The idea\par}

\begin{enumerate}
\item Use uniform state distribution \( \mu  \) \( \Rightarrow  \) avoid exploration
problems
\item Use finite \( \alpha >0 \).
\item \( l_{1} \) metric instead of \( l_{\infty } \) metric
\end{enumerate}

\lyxnewslide{asdfd}

{\par\centering Definitions\par}


\[
d_{\pi ,\mu }(s)\equiv \Pr _{\pi ,\mu ,\textrm{world}}(s)\textrm{ }=\textrm{ natural metric on states}\]
 
\[
\mathcal {A}_{\pi ,\mu }(\pi ')\equiv E_{s\sim d_{\pi ,\mu }(s)}E_{a\sim \pi '(a;s)}A(s,a)=\textrm{ policy advantage}\]


As \( \alpha \rightarrow 0 \), 
\[
\eta _{\mu }(\pi _{\textrm{new}})-\eta _{\mu }(\pi )\propto \mathcal {A}_{\pi ,\mu }(\pi ')\]



\lyxnewslide{adf}

{\par\centering Ingredient: Supervised Learning\par}

Input space: \( s,a \)

Output space: \( Q(s,a) \)

Input distribution: \( d_{\pi ,\mu }(s),\pi (a|s) \)

Output distribution: \( \hat{Q}(s,a) \) s.t. \( E\hat{Q}(s,a)=Q(s,a) \)

Use greedy evaluation for new policy, \( \pi ' \).


\lyxnewslide{dafd}

{\par\centering Conservative Policy Iteration\par}

Let \( G_{\mu }(\pi )= \) regression algorithm finding \( \pi ' \) with large
policy advantage.

\begin{enumerate}
\item \( \pi '=G_{\mu }(\pi ) \) 
\item if \( \mathcal {A}_{\pi ,\mu }(\pi ')>\epsilon  \) 

\begin{enumerate}
\item then \( \pi \leftarrow \alpha \pi '+(1-\alpha )\pi  \), goto 1
\item else output \( \pi  \)
\end{enumerate}
\end{enumerate}

\lyxnewslide{adfa}

{\par\centering Analysis\par}

Theorem: (progress) The policy always improves:


\[
\eta _{\mu }(\pi _{\textrm{new}})-\eta _{\mu }(\pi )\geq \frac{\alpha }{1-\gamma }\left( \mathcal {A}_{\pi ,\mu }(\pi ')-\frac{2\alpha \gamma \epsilon }{1-\gamma (1-\alpha )}\right) \]



\lyxnewslide{adfd}

Theorem: (termination) CPI halts in \( O\left( R^{2}/\epsilon ^{2}\right)  \)
iterations.

Proof: Take derivative w.r.t. \( \alpha  \), find extrema, 

\( \Rightarrow \eta _{\mu }(\pi _{\textrm{new}})-\eta _{\mu }(\pi )\geq \frac{\mathcal {A}_{\pi ,\mu }(\pi ')^{2}}{8R} \)


\lyxnewslide{dfd}

Theorem: (optimality) The output policy satisfies: 
\[
\eta _{D}(\pi ^{*})-\eta _{D}(\pi )\leq \frac{\epsilon }{1-\gamma }\max _{s}\frac{d_{\pi ^{*},D}(s)}{d_{\pi ,\mu }(s)}\]
 
\[
\leq \frac{\epsilon }{(1-\gamma )^{2}}\max _{s}\frac{d_{\pi ^{*},D}(s)}{\mu (s)}\]


Note: back to \( l_{\infty } \) norm.

Prior information \( \rightarrow  \) tune \( \mu (s) \)


\lyxnewslide{adf}

{\par\centering Needed\par}

\begin{enumerate}
\item (progress) Supervised learning (regression) algorithm
\item (progress \& termination) Evaluation of Policy advantage
\item (optimality) \( \mu  \) restart distribution
\end{enumerate}

\lyxnewslide{adfa}

{\par\centering Conclusion\par}

RL = supervised learning + restart distribution


\lyxnewslide{da}

{\par\centering Work in progress\par}

\begin{enumerate}
\item Algorithms for directed exploration 

\begin{enumerate}
\item finite, MDP: solved (\( E^{3} \) + Sven/Thrun/Simmons)
\item Large/infinite MDP: unsolved
\end{enumerate}
\item Approximate model building
\item Experimental validation
\end{enumerate}
\end{document}
