%% This LaTeX-file was created by <jl> Thu Feb 14 18:30:09 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{article}
\usepackage[T1]{fontenc}

\makeatletter


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

\makeatother

\begin{document}

\begin{enumerate}
\item The RL problem
\item Formalization

\begin{enumerate}
\item Discrete, deterministic
\item Markov Decision process
\item POMDP
\end{enumerate}
\item Solution criteria

\begin{enumerate}
\item maximum average reward: often mathematically painful

\begin{enumerate}
\item average reward is independent of state.
\item average reward is (generall) independent of a one step policy iteration. \( \Rightarrow  \)
measure ``transients''
\end{enumerate}
\item maximum \( \gamma  \)-discounted reward: sometimes hides things.
\end{enumerate}
\item Useful quantities

\begin{enumerate}
\item State distribution at time \( t=d_{t}(s) \).
\item Asymptotic state distribution \( d(s) \).
\item disounted state distribution \( d(s|\gamma ,\pi ,d_{0})=(1-\gamma )\sum _{\gamma =0}^{\infty }\gamma ^{t}d_{t}(s) \)
\item Average reward \( \eta =E_{a,s\sim \pi (a|s)d(s)}R(s,a) \).
\item Discounted reward \( \eta _{\gamma }=E_{a,s\sim \pi (a|s)d(s|\gamma ,\pi ,d_{0})}R(s,a) \)
\item Expected reward given a state, \( J(s)=E_{a,s\sim \pi (a|s)d(s|\gamma ,\pi ,\delta (s))}R(s,a) \)
\item Expected reward given a state action, \( Q(s,a)=R(s,a)+\gamma E_{a,s\sim \pi (a|s)d(s|\gamma ,\pi ,\delta (s,a))}R(s,a) \)
\item Advantage: \( A(s,a)=Q(s,a)-J(s) \)
\end{enumerate}
\item Deterministic results

\begin{enumerate}
\item Exploration required
\item All states reachable from all others \( \Rightarrow  \) exploration = \( \Theta (VE) \)
for exact solution. (http://www.cc.gatech.edu/fac/Sven.Koenig/papers/aaai93.ps.gz) 
\end{enumerate}
\item MDP results

\begin{enumerate}
\item Exploration required
\item ``mixing time'' = \( n \) (really state visitation frequency of \( n \))
\( \Rightarrow  \) \( \exists c:\,\,O(n^{c}) \) algorithm, \( E^{3} \), for
near optimal solution. (http://www.cis.upenn.edu/\~{}mkearns/papers/reinforcement.ps)

\begin{enumerate}
\item Lower bound mixing
\item \( \frac{1}{1-\gamma }\geq n\Rightarrow  \) solutions are similar (http://www.gatsby.ucl.ac.uk/\~{}sham/papers/discounting.ps.gz)
\end{enumerate}
\end{enumerate}
\item POMDP results: strong intractibility
\item Exact RL algorithms

\begin{enumerate}
\item Dyamic programming
\item Q-learning: Learn optimal policy independent of exploration policy
\end{enumerate}
\item Previous Approximate RL algorithms

\begin{enumerate}
\item Greedy Dynamic Programming: Not guaranteed to improve.
\item Policy Gradient: Guaranteed to improve, but very slow.
\end{enumerate}
\item Conservative Policy iteration

\begin{enumerate}
\item RL reduced to Supervised learning + exploration
\item Guaranteed to improve by finite steps \( \Rightarrow  \) guaranteed to terminate
\item ``broad'' \( d_{0}(s)\Rightarrow  \) near optimal
\end{enumerate}
\end{enumerate}
\end{document}
