%% This LaTeX-file was created by <jl> Thu Sep 19 13:21:07 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[landscape,dvips]{slides}
\usepackage[T1]{fontenc}
\pagestyle{empty}
\usepackage{color}
\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}
}
\newcommand{\lyxnewoverlay}[1]{
   \lyxendslide{.}
   \setcounter{slidetype}{2}
   \begin{overlay}
}
\newcommand{\lyxinvisible}[1]{
   \invisible
}

\makeatother

\begin{document}


\lyxnewslide{aona}

{\par\centering Metric-\( E^{3} \)\par}

{\par\centering John Langford\par}

{\par\centering (With Sham Kakade and Michael Kearns)\par}


\lyxnewslide{adfadf}

{\par\centering The goal: solving reinforcement learning in a large state space\par}

Solve: find a near-optimal policy

Reinforcement learning: On a Markov Decision Process

Large state space: continuous or merely large discrete

\vspace{0.3cm}
{\par\centering \includegraphics{maze.eps} \par}
\vspace{0.3cm}


\lyxnewslide{adfa}

{\par\centering Markov Decision Process\par}

Spaces:

\begin{enumerate}
\item states, \textcolor{green}{\( S \)} 
\item actions, \textcolor{green}{\( A \) }
\end{enumerate}
Dynamics:

\begin{enumerate}
\item Given \textcolor{green}{\( s\in S \)}, reward=\textcolor{green}{\( R(s) \)}
\item Given \textcolor{green}{\( s\in S \)} and \textcolor{green}{\( a\in A \)},
next state \textcolor{green}{\( s'\in S \)} drawn from \textcolor{green}{\( P(s'|a,s) \)}
for some \textcolor{green}{\( P \)}
\end{enumerate}

\lyxnewslide{adfa}

{\par\centering Solving\par}

Efficiently find a policy \textcolor{green}{\( \pi :S\rightarrow A \)} to maximize
expected reward in the next \textcolor{green}{\( T \)} steps.


\lyxnewslide{afaf}

{\par\centering NOT Solving\par}

\begin{itemize}
\item ``Policy Gradient'' is not a solution (no guarantee of near optimality)
\end{itemize}

\lyxinvisible{}

\begin{itemize}
\item ``Policy iteration'' is not a solution (no guarantee of near optimality)
\item Q-learning is not a solution (\emph{far} to slow)
\item Dynamic programming is not a solution (requires model)
\end{itemize}

\lyxnewoverlay{adf}

{\par\centering NOT Solving\par}

\begin{itemize}
\item ``Policy Gradient'' is not a solution (no guarantee of near optimality)
\item ``Policy iteration'' is not a solution (no guarantee of near optimality)
\end{itemize}

\lyxinvisible{}

\begin{itemize}
\item Q-learning is not a solution (\emph{far} to slow)
\item Dynamic programming is not a solution (requires model)
\end{itemize}

\lyxnewoverlay{adf}

{\par\centering NOT Solving\par}

\begin{itemize}
\item ``Policy Gradient'' is not a solution (no guarantee of near optimality)
\item ``Policy iteration'' is not a solution (no guarantee of near optimality)
\item Q-learning is not a solution (\emph{far} to slow)
\end{itemize}

\lyxinvisible{}

\begin{itemize}
\item Dynamic programming is not a solution (requires model)
\end{itemize}

\lyxnewoverlay{adf}

{\par\centering NOT Solving\par}

\begin{itemize}
\item ``Policy Gradient'' is not a solution (no guarantee of near optimality)
\item ``Policy iteration'' is not a solution (no guarantee of near optimality)
\item Q-learning is not a solution (\emph{far} to slow)
\item Dynamic programming is not a solution (requires model)
\end{itemize}

\lyxnewslide{adfadf}

{\par\centering Solution Methods\par}

\begin{itemize}
\item \( E^{3} \) (Explicit-Explore-or-Exploit) Running time \textcolor{green}{\( P(|S|) \)}.
(KS 1998)
\end{itemize}

\lyxinvisible{}

\begin{itemize}
\item Factored-\( E^{3} \), Running time \textcolor{green}{\( P(|L|) \)}, \textcolor{green}{\( L \)}
= \# of parameters (KK 1999)
\item \( RMAX \) (generalization \& simplification) (BT 2001)
\end{itemize}

\lyxnewoverlay{adfa}

{\par\centering Solution Methods\par}

\begin{itemize}
\item \( E^{3} \) (Explicit-Explore-or-Exploit) Running time \textcolor{green}{\( P(|S|) \)}ish.
(KS 1998)
\item Factored-\( E^{3} \), Running time \textcolor{green}{\( P(|L|) \)}, \textcolor{green}{\( L \)}
= \# of parameters (KK 1999)
\end{itemize}

\lyxinvisible{}

\begin{itemize}
\item \( RMAX \) (generalization \& simplification) (BT 2001)
\end{itemize}

\lyxnewoverlay{adfa}

{\par\centering Solving\par}

\begin{itemize}
\item \( E^{3} \) (Explicit-Explore-or-Exploit) Running time \textcolor{green}{\( P(|S|) \)}ish.
(KS 1998)
\item Factored-\( E^{3} \), Running time \textcolor{green}{\( P(|L|) \)}, \textcolor{green}{\( L \)}
= \# of parameters (KK 1999)
\item \( RMAX \) (\( E^{3} \) generalization \& simplification) (BT 2001)
\end{itemize}

\lyxnewslide{ada}

How can we make Reinforcement learning work in \emph{large} state spaces?


\lyxnewslide{adfa}

{\par\centering You Can't\par}

Theorem: There exists a set of problems requiring \textcolor{green}{\( O\left( \frac{|S||A|T\ln \frac{1}{\delta }}{\epsilon }\right)  \)}
time to solve for any algorithm. 


\lyxnewslide{adfa}

{\par\centering You Can\par}

People do it all the time. 


\lyxnewslide{adfad}

{\par\centering Reconciliation\par}


\lyxinvisible{}

Lower bound \( \Rightarrow  \) additional assumption necessary

Why can people succeed?

The world has structure. 


\lyxnewoverlay{adf}

{\par\centering Reconciliation\par}

Lower bound \( \Rightarrow  \) additional assumption necessary


\lyxinvisible{}

Why can people succeed?

The world has structure. 


\lyxnewoverlay{adf}

{\par\centering Reconciliation\par}

Lower bound \( \Rightarrow  \) additional assumption necessary

Why can people succeed?


\lyxinvisible{}

The world has structure. 


\lyxnewoverlay{adf}

{\par\centering Reconciliation\par}

Lower bound \( \Rightarrow  \) additional assumption necessary

Why can people succeed?

The world has structure. 


\lyxnewslide{adaf}

{\par\centering The Metric-\( E^{3} \) detective story\par}

\begin{enumerate}
\item Approaches which fail.
\item Our structure.
\item The algorithm.
\item The analysis.
\end{enumerate}

\lyxnewslide{adfa}

{\par\centering A dead end (commonly used)\par}

\begin{enumerate}
\item (metric \( \Rightarrow  \)) Aggregate states into superstates.
\item Derive (somehow) dynamics between the superstates.
\item Reinforcement Learn on the superstates.
\end{enumerate}
Problem: dynamics CANNOT be markovian. 

\vspace{0.3cm}
{\par\centering \includegraphics{paper/instability.eps} \par}
\vspace{0.3cm}


\lyxnewslide{adfa}

{\par\centering An elegant dead end (DG 1997)\par}

\begin{enumerate}
\item dynamics \( \Rightarrow  \) aggregate states into superstates
\item Reinforcement Learn on superstates
\end{enumerate}
Problem: in a real world, dynamics \( \Rightarrow  \) no simplification. 


\lyxnewslide{adfa}

{\par\centering Our structure\par}

\begin{enumerate}
\item Use metric
\item Assume \textcolor{red}{local modeling}
\item Assume \textcolor{red}{approximate planning}
\end{enumerate}
assumption \( = \) difficulty abstraction 


\lyxnewslide{adfa}

{\par\centering Metric\par}

Not an assumption---a metric always exists.

Motivation:

\begin{enumerate}
\item Fundamental structure.
\item Intuitive.
\item Appears related to human RL ability. 
\end{enumerate}
\textcolor{green}{\( d((s,a),(s',a'))\geq 0 \)} and \textcolor{green}{\( d((s',a'),(s,a))=d((s,a),(s',a')) \)} 

Note: triangle inequality unnecessary


\lyxnewslide{ad}

{\par\centering \textcolor{red}{Local Model}\par}

GIVEN: sufficient ``nearby'' experience

ASSUME: ability to model local dynamics

\textcolor{green}{\( \forall \textrm{nearby}\, s,a\, \, \exists \hat{P}:\, \, \sum _{s'}|\hat{P}(s'|s,a)-P(s'|s,a)|\leq \alpha  \)}

Motivation: lower bound \( \Rightarrow  \) model generalization necessary


\lyxnewslide{adfa}

{\par\centering \textcolor{red}{Approximate Plan}\par}

GIVEN: model + Reward structure

ASSUME: ability to find near-optimal policy, \textcolor{green}{\( \pi  \)}.

\textcolor{green}{\( V_{M}(\pi )\geq V_{M}(\pi ^{*})-\beta  \)}

\textcolor{green}{\( V_{M}(\pi ) \)} = value of policy \textcolor{green}{\( \pi  \)}
in model \textcolor{green}{\( M \)}. 

Motivation: 

\begin{enumerate}
\item Approximate planning algorithms exist (KL 2002, KMN 1999)
\item planning time lower bound \( \Rightarrow  \) generalization necessary 
\end{enumerate}

\lyxnewslide{adfa}

{\par\centering Algorithm\par}

\begin{enumerate}
\item Move randomly until ``known state'' (\textcolor{red}{local model})
\item \textcolor{red}{Approximate Plan} to:

\begin{enumerate}
\item escape (\textcolor{green}{\( M= \)} \textcolor{red}{known world}, \textcolor{green}{\( R=1 \)}
in unknown states)
\item exploit (\textcolor{green}{\( M= \)} \textcolor{red}{known world}, \textcolor{green}{\( R=0 \)}
in unknown states)
\end{enumerate}
\item If \textcolor{green}{\( V_{\textrm{escape}}(\pi _{\textrm{escape}})>\epsilon  \)},
then use \textcolor{green}{\( \pi _{\textrm{escape}} \)}
\item otherwise, return \textcolor{green}{\( \pi _{\textrm{exploit}} \)}. 
\end{enumerate}

\lyxnewslide{adf}

{\par\centering Analysis I\par}

Theorem: (correctness) \textcolor{green}{\( Pr(\textrm{bad output policy})\leq \delta  \)}

bad output policy = \textcolor{green}{\( V_{M}(\pi ,s)<V_{M}(\pi ^{*},s)-\epsilon -2\beta -2\alpha T \)}

\textcolor{green}{\( T \)} = horizon time

\textcolor{green}{\( \beta  \)} = \textcolor{red}{approximate plan} error

\textcolor{green}{\( \alpha  \)} = \textcolor{red}{local model} error

\textcolor{green}{\( \epsilon  \)} = nearness-to-optimal


\lyxnewslide{adfa}

{\par\centering Analysis II\par}

Theorem: (speed) \textcolor{green}{\( Pr(\textrm{bad sample complexity})\leq \delta  \)}

\textcolor{green}{\( N(\alpha ) \)} = covering number.

\textcolor{green}{\( m \)} = enough experience for \textcolor{red}{local model}.

\textcolor{green}{\( \textrm{bad sample complexity }>\frac{TmN(\alpha )}{\epsilon -\alpha T}\ln \frac{1}{\delta }+mN(\alpha ) \)}


\lyxnewslide{adaf}

{\par\centering Analysis III\par}

Let \textcolor{green}{\( k \)} = sample complexity.

Theorem: (running time) 

{\par\centering \textcolor{green}{run time \( \leq \frac{k(k-1)}{2}t_{\textrm{metric}}+2k(t_{\textrm{plan}}+c_{\textrm{gen}}t_{\textrm{model}})+O(k) \)}\par}

\textcolor{green}{\( t_{\textrm{metric}} \)} = execution time of metric

\textcolor{green}{\( t_{\textrm{plan}} \)} = execution time of \textcolor{red}{approximate
plan}

\textcolor{green}{\( t_{\textrm{model}} \)} = execution time of \textcolor{red}{local
model}

\textcolor{green}{\( c_{\textrm{gen}} \)} = number of calls to \textcolor{red}{local
model} per \textcolor{red}{approximate plan}


\lyxnewslide{afda}

{\par\centering Example\par}

a)\includegraphics{paper/cover.eps} b)\includegraphics{paper/metric_cover_2.eps} 

a) cover with Line-of-sight metric. 

b) cover with Line-of-sight + max distance metric.


\lyxnewslide{adfa}

{\par\centering Conclusion\par}

\begin{enumerate}
\item We (finally) have math to validate intuitive answer.
\item Don't aggregate. Instead, locally model.
\item RL is closer to viable. 
\end{enumerate}

\lyxnewslide{adfa}

{\par\centering Important undone work\par}

\begin{enumerate}
\item write a program, see it work 

\begin{enumerate}
\item caveat: parti-game
\item caveat: robot path planning
\end{enumerate}
\item Very few algorithms for local modeling exist.
\item Measurement of modeling failure very important.
\end{enumerate}
\end{document}
