\documentclass[]{beamer}
% Class options include: notes, notesonly, handout, trans,
%                        hidesubsections, shadesubsections,
%                        inrow, blue, red, grey, brown

% Theme for beamer presentation.
\usepackage{beamerthemetree} 
\usepackage{graphicx}
% Other themes include: beamerthemebars, beamerthemelined, 
% beamerthemetree, beamerthemetreebars, beamerthemesplit 

\newcommand{\tab}{\hspace*{1em}}
\newcommand{\ltab}{\hspace*{8em}}

\title{Reinforcement Learning}    % Enter your title between curly braces
\subtitle{Introduction to Artificial Intelligence}
\author{Yang Gao, Francesca Toni}  
\institute{Russel \& Norving, \emph{AI: a modern approach}, Section 21\\
Sutton \& Barto, \emph{Reinforcement Learning: An introduction}}
\date{ }

\begin{document}

% Creates title page of slide show using above information
\begin{frame}
  \titlepage
\end{frame}
 % Add notes to yourself that will be displayed when
% typeset with the notes or notesonly class options
\note{Talk for 30 minutes}
\section[Outline]{}

% Creates table of contents slide incorporating
% all \section and \subsection commands
\begin{frame}
  \tableofcontents
\end{frame}

%Section 1: First Impression on RL
\section{Big Picture of Reinforcement Learning}
\label{sec:first_sight}

\subsection{A Brief History of RL}
\begin{frame}
 \frametitle{A short history of Reinforcement Learning:}
  \begin{itemize}
  \item Proposed by the behavioural psychologists 
  \item Used to train animals (including human beings)
  \item An area of Machine Learning  
  \end{itemize}
\end{frame}
%\note[enumerate]       % Add notes to yourself that will be displayed when
%{                      % typeset with the notes or notesonly class options
%\item Note for Point 1   
%\item Note for Point 2   
%}

\subsection{Properties of RL}
 
\begin{frame}
 \frametitle{RL in a nutshell}
In each state:
 \begin{itemize}
  \item if an agent does something ``good", it gets rewards;
  \item if an agent does something ``wrong", it gets punishments;
  \item rewards and punishments are received right after the
  effect of the performed action is observed;
  \item goal: choose the best action at each state to maximise 
  the long-term rewards. 
 \end{itemize}
 \begin{figure}
 \centering
 \includegraphics[width=0.7\textwidth]{pics/flow_chart.pdf}
 \end{figure}
\end{frame}


\begin{frame}
\frametitle{Components of Reinforcement Learning}
\begin{itemize}
\item 
\textbf{State}: All information needed for choosing actions 
\item
\textbf{Action}: Available actions in each state
\item
\textbf{Dynamic of the Environment}: How the environment is changed by
the actions
\item 
\textbf{Rewards}: Criteria used to evaluate the the goodness
of performing an action in a state (typically a real number)
\end{itemize}

\end{frame}


%Section 2: MDP
\section{Mathematical Model and An Algorithm of RL}

\subsection{Motivating Example}

\begin{frame}
\frametitle{A motivating example: Maze}
\begin{columns}[c]
\column{2.5in}  % slides are 3in high by 5in wide
\begin{itemize}
\item 
A $2\times3$ grid world
\item 
A pit, an exit and some walls are known in this grid world,
but their locations are unknown
\item 
Arrive at the exit: win; fall in the pit: die; hit a wall, hurt 
\item
Goal: Get out of this maze (i.e. safely arrive at the exit) as quickly as
possible
\end{itemize}
\column{2in}
\includegraphics[width=2in,height=1.4in]{pics/basic_map.pdf}
\end{columns}
\end{frame}

\begin{frame}
\frametitle{RL components in this problem}
\begin{itemize}
\item 
\textbf{State}: The agent's current location 
\item
\textbf{Action}: \textit{LEFT, RIGHT, UP, DOWN}
\item
\textbf{Environment Dynamics}:
  \begin{itemize}
  \item
  If in the intended direction there exists a wall, no-op
  \item 
  otherwise, move one square in the intended direction
  \end{itemize}
\item 
\textbf{Rewards}:
  \begin{itemize}
  \item 
  normal move: -1
  \item
  hit a wall: -10
  \item 
  die: -100 
  \item 
  exit: +100
  \end{itemize}
\item
\textbf{Our Goal}: find the best route to exit
\end{itemize}
\end{frame}

\subsection{Mathematical Model of RL}
\label{subsec:mdp}
\begin{frame}
\frametitle{Markov Decision Process (MDP)}
Components of RL ($t$:current time slot, $t+1$: next time slot):
\begin{itemize}
 \item \textbf{States}: describe the environment;
 \item \textbf{Actions}: available actions for execution; 
 \item \textbf{Transition Probability}: 
 $Pr\{s_{t+1} | s_t, a_t\}$ (denoted $\mathcal{P}_{s_ts_{t+1}}^{a_t}$);
 \item \textbf{Rewards}: $E\{r_{t+1} | s_t ,  a_t,  s_{t+1}\}$
 (denoted $\mathcal{R}_{s_{t} s_{t+1}}^{a_t}$);
 \item $MDP = <S, A, T, R>$.
\end{itemize}

Why MDP?
 \begin{itemize}
  \item RL problems satisfy the \emph{Markov property}: history
independence.
 \end{itemize}
\end{frame}

\begin{frame}
\frametitle{How to find the best action}
The goal of RL:
\begin{itemize}
 \item 
 Formally: 
 in a state $s_0 \in S$, determine the best \emph{policy} $\pi$
  so as to maximise the \emph{long-term reward}  
 \item
 A \emph{policy} $\pi: S \rightarrow A$, is 
 a function from state to action. 
 $\pi(s) = a$ means choose action $a$ at state $s$
 \item
 The long-time reward of performing $a_0$ at $s_0$:
 \begin{align*}
  Q^{\pi}(s_0, a_0)
  = E_\pi\{
 \displaystyle \sum \limits_{k=0}^{\infty}\gamma^{k}r_{k+1}|
 s_0, a_0
 \}
 \end{align*}
 where $E_\pi$ denotes the expected value given that the agent
 follows policy $\pi$, and $\gamma\in[0,1]$ is the \emph{discount factor}
 indicating how 'short-sighted' the agent is:
 the smaller $\gamma$, the more short-sighted the agent.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{An example policy and its Q-value}
\begin{columns}[c]
\column{2in}
\begin{itemize}
 \item
A policy: always go right
 \item
Formally: $\pi(s)=\textit{RIGHT}$ for all $s \in S$
\begin{align*}
& Q^\pi([0,2],\textit{RIGHT})& \\
&= -10 -10 \times \gamma
-10 \times \gamma^2 \cdots &
\\
&= -10 + \gamma(-10 - 10 \gamma - 10 \gamma^2 - \cdots)
\\
&= -10 + \gamma Q^\pi([0,2],\textit{RIGHT})
\\
&= -10/(1-\gamma) &
\end{align*}
\end{itemize}
\column{2in}
\includegraphics[width=2in,height=1.4in]{pics/always_right.pdf}
\end{columns}

\end{frame}


\begin{frame}
\frametitle{Q-value in recursive form (Bellman Equation)} 
\begin{align*}
 Q^{\pi}(s_0, a_0) & = E_\pi\{
 \displaystyle \sum \limits_{k=0}^{\infty}\gamma^{k}r_{k+1}|
 s_0, a_0\}\\
 & = E_{\pi}\{r_1 + \gamma \displaystyle \sum \limits_{k=0}^\infty
 \gamma^k r_{k+2} | s_0, a_0 \}\\
 & = \displaystyle \sum \limits_{s_1 \in S} \mathcal{P}_{s_0s_1}^{a_0}
 ( \mathcal{R}_{s_0s_1}^{a_0} + \gamma \displaystyle \sum 
 \limits_{a_1 \in A} \pi(s_1, a_1) \cdot
 E_{\pi}\{\displaystyle \sum \limits_{k=0}^{\infty}\gamma^{k}r_{1+k+1}|
 s_1, a_1\}
 )\\
 & = \displaystyle \sum \limits_{s_1 \in S} \mathcal{P}_{s_0s_1}^{a_0}
 ( \mathcal{R}_{s_0s_1}^{a_0} + 
 \gamma \displaystyle \sum \limits_{a_1 \in A}
 \pi(s_1, a_1) \cdot  Q^{\pi}(s_1,a_1)
 ) 
\end{align*}
\end{frame}

\begin{frame}
\frametitle{Find the best policy}
\begin{itemize}
 \item
 Optimal policy: 
   $\pi^* = \arg \displaystyle \max \limits_{\pi} Q^{\pi} (s,a)$  for all
$s \in  S$, $a \in A$
 \item
Optimal policies share the same Q-values:
\begin{align*}
 Q^*(s_0,a_0) & = \displaystyle \max \limits_\pi Q^\pi(s_0,a_0) \\
 & = \displaystyle \sum \limits_{s_1 \in S} \mathcal{P}_{s_0s_1}^{a_0}
 (\mathcal{R}_{s_0s_1}^{a_0} + \gamma \displaystyle \max \limits_{a_1 \in
 A} Q^*(s_1, a_1))
\end{align*}
 \end{itemize}
 
\end{frame}

\subsection{Q-Learning Algorithm}
\label{subsec:q_learning}

\begin{frame}
\frametitle{Q-Learning Algorithm}
\begin{tabular}{|p{\textwidth}|}
\hline
1\tab Initialise $Q(s,a)$ for all states $s$ and all actions $a$
arbitrarily \\
2\tab Repeat (for each episode):\\
3\tab \tab Initialise $s$\\
4\tab \tab Repeat (for each step in an episode):\\
5\tab \tab \tab Choose $a = \displaystyle \arg  \max \limits_{a \in A}
Q(s,a)$ with probability $1-\epsilon$\\
6\tab \tab \tab Perform action $a$, observe reward $r$ and next state
$s'$\\
7\tab \tab \tab $Q(s,a) \leftarrow (1-\alpha) Q(s,a) + \alpha [r + \gamma 
\max_{a'}Q(s', a')]$\\
8\tab \tab \tab $s \leftarrow s'$\\
9\tab \tab until $s$ is terminal\\
\hline

\end{tabular}
\end{frame}

\begin{frame}
\frametitle{Applying Q-Learning to The Maze Problem}
\begin{columns}[c]
\column{2in}
\begin{itemize}
 \item 
$\alpha=0.5$, $\gamma = 0.9$
 \item
All Q-values are initialised as 0
 \item<2-3>
Choose
\textit{UP}, and receive -100
 \item<3> 
update Q-value:\\
\vspace*{-20pt}
\begin{align*}
& Q([0,2],\textit{UP}) \\
& = (1-0.5) \times 0 + 
\\
&\quad 0.5 \times (-100 + 0.9\times 0)
\\
&= -50
\end{align*}
\end{itemize}
\column{2in}
\includegraphics<1>[width=2in, height=1.4in]{pics/basic_map.pdf}
\includegraphics<2>[width=2in, height=1.4in]{pics/step1.pdf}
\includegraphics<3>[width=2in, height=1.4in]{pics/step2.pdf}
\end{columns}
\end{frame}


\begin{frame}
\frametitle{Applying Q-Learning to The Maze Problem}
\begin{columns}[c]
\column{2in}
\begin{itemize}
 \item 
$\alpha=0.5$, $\gamma = 0.9$
% \item
%All Q-values are initialised as 0
\item<1-2>
Choose \textit{LEFT}, and 
receive -1
\item<2>
update Q-value:\\
\vspace*{-20pt}
\begin{align*}
& Q([0,2],\textit{LEFT}) \\
& = (1-0.5) \times 0 + 
\\
&\quad 0.5 \times (-1 + 0.9\times 0)
\\
&= -0.5
\end{align*}
\end{itemize}
\column{2in}
\includegraphics<1>[width=2in, height=1.4in]{pics/step3.pdf}
\includegraphics<2>[width=2in, height=1.4in]{pics/step4.pdf}
\end{columns}
\end{frame}

\begin{frame}
\frametitle{Applying Q-Learning to The Maze Problem}
\begin{columns}[c]
\column{2in}
\begin{itemize}
 \item 
$\alpha=0.5$, $\gamma = 0.9$
% \item
%All Q-values are initialised as 0
\item<1-2>
Choose \textit{UP}, and 
receive -10
\item<2>
update Q-value:\\
\vspace*{-20pt}
\begin{align*}
& Q([0,1],\textit{UP}) \\
& = (1-0.5) \times 0 + 
\\
&\quad 0.5 \times (-10 + 0.9\times 0)
\\
&= -5
\end{align*}
\end{itemize}
\column{2in}
\includegraphics<1>[width=2in, height=1.4in]{pics/step5.pdf}
\includegraphics<2>[width=2in, height=1.4in]{pics/step6.pdf}
\end{columns}
\end{frame}

\begin{frame}
\frametitle{Applying Q-Learning to The Maze Problem}
\begin{columns}[c]
\column{2in}
\begin{itemize}
 \item 
$\alpha=0.5$, $\gamma = 0.9$
% \item
%All Q-values are initialised as 0
\item<1-2>
Choose \textit{LEFT}, and 
receive -1
\item<2>
update Q-value:\\
\vspace*{-20pt}
\begin{align*}
& Q([0,1],\textit{LEFT}) \\
& = (1-0.5) \times 0 + 
\\
&\quad 0.5 \times (-1 + 0.9\times 0)
\\
&= -0.5
\end{align*}
\end{itemize}
\column{2in}
\includegraphics<1>[width=2in, height=1.4in]{pics/step7.pdf}
\includegraphics<2>[width=2in, height=1.4in]{pics/step8.pdf}
\end{columns}
\end{frame}

\begin{frame}
\frametitle{Applying Q-Learning to The Maze Problem}
\begin{columns}[c]
\column{2in}
\begin{itemize}
 \item 
$\alpha=0.5$, $\gamma = 0.9$
% \item
%All Q-values are initialised as 0
\item<1-2>
Choose \textit{UP}, and 
receive -1
\item<2>
update Q-value:\\
\vspace*{-20pt}
\begin{align*}
& Q([0,0],\textit{UP}) \\
& = (1-0.5) \times 0 + 
\\
&\quad 0.5 \times (-1 + 0.9\times 0)
\\
&= -0.5
\end{align*}
\end{itemize}
\column{2in}
\includegraphics<1>[width=2in, height=1.4in]{pics/step9.pdf}
\includegraphics<2>[width=2in, height=1.4in]{pics/step10.pdf}
\end{columns}
\end{frame}


\begin{frame}
\frametitle{Applying Q-Learning to The Maze Problem}
\begin{columns}[c]
\column{2in}
\begin{itemize}
 \item 
$\alpha=0.5$, $\gamma = 0.9$
% \item
%All Q-values are initialised as 0
\item<1-2>
Choose \textit{RIGHT}, and 
receive 100 
\item<2>
update Q-value:\\
\vspace*{-20pt}
\begin{align*}
& Q([0,1],\textit{RIGHT}) \\
& = (1-0.5) \times 0 + 
\\
&\quad 0.5 \times (100 + 0.9\times 0)
\\
&= 50 
\end{align*}
\end{itemize}
\column{2in}
\includegraphics<1>[width=2in, height=1.4in]{pics/step11.pdf}
\includegraphics<2>[width=2in, height=1.4in]{pics/step12.pdf}
\end{columns}
\end{frame}


\begin{frame}
\frametitle{Applying Q-Learning to The Maze Problem}
\begin{columns}[c]
\column{2in}
\begin{itemize}
 \item 
$\alpha=0.5$, $\gamma = 0.9$
 \item
The next time agent visits [0,0]
and performs \textit{UP}:
\begin{align*}
& Q([0,0],\textit{UP}) \\
& = (1-0.5) \times (-0.5) + 
\\
&\quad 0.5 \times (-1 + 0.9\times 50)
\\
&= 21.75 
\end{align*}
\end{itemize}
\column{2in}
\includegraphics<1>[width=2in, height=1.4in]{pics/second_visit1.pdf}
\includegraphics<2>[width=2in, height=1.4in]{pics/second_visit2.pdf}
\end{columns}
\end{frame}

\begin{frame}
 \frametitle{Property of Q-Learning}
 \begin{itemize}
  \item Quick learning speed: Q-Learning is able to 
  find a quite good policy after a small number of iterations.
  \item Model-free: no need to keep record of the
  learning trajectory (no need to explicitly compute the Transition
 Probability). 
  \item Guarantee to converge: 
  after visiting each state-action pairs for an infinite number
  of times,  for any $s \in S, a \in A$, $Q(s,a)$ is guaranteed
  to converge to $Q^*(s,a)$.
 \end{itemize}
\end{frame}

\begin{frame}
\frametitle{The learning parameters in Q-Learing}
\begin{itemize}
 \item $\alpha$: 
  \begin{itemize}
  \item Learning step
  \item balance between existing experiences (weight: $1-\alpha$) and new
	    observations (weight: $\alpha$)
  \end{itemize}
 \item $\gamma$: 
  \begin{itemize}
  \item Future discount
  \item balance between current reward (weight: 1) and next $N$ step's
reward (weight: $\gamma^N$)
  \end{itemize}
\item $\epsilon$:
  \begin{itemize}
  \item indicating how 'bold' the agent is
  \item balance between \emph{exploitation}  (take greedy action,
$1-\epsilon$
  chance) and \emph{exploration} (take random action, $\epsilon$ chance)
  \end{itemize}
\end{itemize}

\end{frame}


\section{Summary}

\begin{frame}
 \frametitle{Summary}
 \begin{itemize}
  \item 
  Basic idea of Reinforcement Learning (RL):
  \begin{itemize}
   \item 
   did something "good" --- reward
   \item
   did something "bad" --- punish
  \end{itemize}
  \item
  Formal model of RL --- Markov Decision Process (MDP):
  \begin{itemize}
   \item $MDP = <State,Action,TransProb,Reward>$
   \item $Q(s,a)$: 
   to valuate the value of performing action $a$ in state $s$
   \item Optimal policy: 
   \begin{itemize}
   \item
   $\pi^* = \arg \max_\pi Q^{\pi}$ \\
   \item
   $Q^{\pi^*} = Q^*$
   \end{itemize}
   \item Q-Learning algorithm
  \end{itemize}
 \end{itemize}

\end{frame}

\begin{frame}
\frametitle{What makes RL different?}
In which problems we should use RL instead of other ML techniques?
\begin{itemize}
 \item Sequential decision making: time and order really matters
 \item I know what I want, but don't know how to get it: 
       no supervisor, only rewards (goals)
 \item The agent can interact with the environment: trial and error is
	affordable
 \item Feedback is delayed: only after observing actions' consequences
\end{itemize}
\end{frame}


\section{Tutorial: The Wumpus World}
\begin{frame}
\frametitle{Tutorial: The Wumpus World}
A \emph{Wumpus World} example:
\begin{itemize}
 \item 
A $5 \times 5$ grid world
\item
The world has: 
an exit, some golds, some Wumpus and some pits. 
The agent only knows the golds' locations
\item
The agent can shoot a Wumpus next to it; 
by killing a Wumpus, the agent gets reward
\item 
When next to a Wumpus: smells \emph{stench}; \\
next to a pit: feels \emph{breeze};\\
on a gold: sees \emph{glitter}
\item 
Step into a square with a Wumpus or a pit: die;\\
hit wall: no-op
\item
Task: collects all gold and arrives the exit safely
\end{itemize}
 
\end{frame}

\begin{frame}
\frametitle{Tutorial: The Wumpus World}
\begin{itemize}
 \item 
Actions: \\
\textit{LEFT}, \textit{RIGHT}, \textit{UP}, \textit{DOWN},\\
\textit{SHOOT\_LEFT}, \textit{SHOOT\_RIGHT}, \textit{SHOOT\_UP},
\textit{SHOOT\_DOWN}, \\ 
\textit{PICK\_UP}
 \item 
Rewards: 
  \begin{itemize}
  \item 
  Normal move: -1
  \item 
  Die: -1000
  \item 
  Get a gold or kill a Wumpus: +100 
  \item 
  Missed shoot or missed pick: -50
  \item 
  Successfully exit the world: +500
  \end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{RL for Wumpus World: Understand The Learning Parameters}
\begin{itemize}
 \item 
Default parameters: 
  \begin{itemize}
  \item $\alpha = 0.1$
  \item $\gamma = 0.9$
  \item $\epsilon = 0.05 $
  \end{itemize}
 \item 
Run the following experiments to see how each parameter 
affects the learning performance  
(100 episodes for each)
  \begin{itemize}
  \item 
  Keeping the default value for $\gamma$ and $\epsilon$, compare the
  performances when $\alpha = 0, 0.1, 0.5, 1.0$
  \item 
  Keeping the default value for $\alpha$ and $\epsilon$, compare the
  performances when $\gamma= 0, 0.1, 0.5, 1.0$
  \item 
  Keeping the default value for $\alpha$ and $\gamma$, compare the
  performances when $\epsilon= 0, 0.1, 0.5, 1.0$
  \end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Domain Knowledge for The Wumpus World}
\begin{itemize}
 \item 
In certain situations, the goodness of some actions can be deduced by 
the goodness (Q-value) of other actions
 \item 
Suppose an agent steps into a square where:
  \begin{itemize}
   \item 
  In previous episodes, 
  UP, LEFT, DOWN have been performed in this square, and they are all OK;
 and
   \item 
  the agent can smell stench in this square.
  \end{itemize}
 \item 
In this situation, we can easily see that there must exist a Wumpus in the
square on the right.
 \item 
However, classical RL algorithms cannot deduce this: it still needs to 
perform RIGHT to realise that there is a Wumpus in the right square
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Add Arguments to RL}
\begin{itemize}
 \item 
We describe the domain knowledge by \emph{Arguments}:
logic sentences describing which actions are 
recommended and/or discouraged.
 \item 
The argument for the example domain knowledge above:
\\
\ltab \textbf{IF} \\ 
\ltab left \hspace*{2em} OK \\
\ltab up \hspace*{2.3em} OK \\
\ltab down \hspace*{1.2em} OK \\
\ltab stench \hspace*{0.8em} TRUE \\
\ltab \textbf{THEN}\\
\ltab + \hspace*{2.7em} SHOOT\_RIGHT \\
\ltab $-$ \hspace*{2.7em} RIGHT \\
\ltab \textbf{DONE}
\end{itemize}
\end{frame}

\iffalse

\section{Simple slide with three points shown in succession}



\begin{frame}

  \frametitle{Simple slide with three points shown in succession}   %
Insert frame title between curly braces



  \begin{itemize}

  \item<1-> Point 1 (Click ``Next Page'' to see Point 2) % Use Next

Page to go to Point 2

  \item<2-> Point 2  % Use Next Page to go to Point 3

  \item<3-> Point 3

  \end{itemize}

\end{frame}

\note{Speak clearly}  % Add notes to yourself that will be displayed when

                      % typeset with the notes or notesonly class options





\section{Slide with two columns: items and a graphic}



\begin{frame}

  \frametitle{Slide with two columns: items and a graphic}   % Insert frame
title between curly braces

  \begin{columns}[c]

  \column{2in}  % slides are 3in high by 5in wide

  \begin{itemize}

  \item<1-> First item

  \item<2-> Second item

  \item<3-> ...

  \end{itemize}

  \column{2in}

  \framebox{Insert graphic here % e.g.
\includegraphics[height=2.65in]{graphic}

  }

  \end{columns}

\end{frame}

\note{The end}       % Add notes to yourself that will be displayed when

		     % typeset with the notes or notesonly class options



\fi

\end{document}
