text:
\section{Related Work}
\label{sec:lts-transformation:related}

%\subsection{Incremental model-checking}

The work presented in this chapter is related to incremental model checking.
Early papers on this subject propose techniques to reuse model checking results of safety properties for a given LTS to determine whether it still satisfies the same property after some alterations~\cite{sokolsky.smolka.inc,swamy}.
This work focuses on particular models, whereas our technique deals with property preservation of transformations in general.
Large speedups are reported compared to complete rechecking, but the memory requirements are at least as high, since all states plus additional bookkeeping per state must reside in memory.
Our technique does not require such bookkeeping.
Furthermore, we do not deal with large, flat LTSs directly, but with networks and transformation rules that both consist of relatively small LTSs.
Finally, we do not recheck a property after transformation, but check bisimilarity~instead.

The work described in this chapter is also related to action refinement~\cite{GoRe01}, which provides a way to describe and study the top-down design of concurrent systems.
Action refinement allows specifying how a more concrete description of a concurrent system can be obtained from an abstract description of this system by replacing certain actions by more detailed behavior.
Action refinement deals with replacing single actions, whereas our work deals with replacing patterns that represent more involved behavior.

Saha presents an incremental algorithm for updating bisimulation relations based on changes of a graph that is related to our work, although it is used in a different context~\cite{saha.bisimulation}.
The goal of this work is efficiently maintaining a bisimulation, whereas the goal of our work essentially is to assess whether a bisimulation exists.

Combemale et al.~\cite{combemale.mde}, H{\"u}lsbusch et al.~\cite{Rensink2010}, and Karsai and Narayanan~\cite{narayanan.karsai.towardsverifyingmt,Karsai:2006:CMT:1785644.1785646} check semantics preservation of model transformations using either strong or weak bisimilarity.
They consider exogenous, horizontal transformations~\cite{Mens:2006:TMT:1706639.1706924}, which transform models from one language to another without changing their level of abstraction.
In contrast, our work deals with endogenous, vertical transformations, which have the same input and output language, and change the level of abstraction of models.
The approach of H{\"u}lsbusch et al.\ and our approach are transformation-dependent and input-independent~\cite{amrani.overview}, whereas the work of Combemale et al.\ and the work of Karsai and Narayanan is transformation-dependent and input-dependent.

Giese et al.\ relate input and output models when specifying a transformation and use a theorem prover to show semantic equivalence between the input and output of the transformation~\cite{Giese06towardsverified}.
A downside of this approach is that it is not completely automated and thus requires manual labor, whereas our approach is automated.
Sch{\"a}tz verifies the preservation of properties of a structural nature for model transformations~\cite{Schatz10}, also using a theorem prover.
Both techniques are transformation-dependent and model-independent, and deal with horizontal transformations.
Giese et al.\ consider exogenous transformations, and Sch{\"a}tz endogenous ones.

ext: tex

max_stars_repo_name: ljpengelen/latex-phd-thesis

max_issues_repo_name: ljpengelen/latex-phd-thesis

max_forks_repo_name: ljpengelen/latex-phd-thesis


text:
\documentclass{beamer}

\usepackage{graphicx}
\usepackage{textpos}
\usepackage{listings}
\usepackage{lstautogobble}

\usetheme{Madrid}
\useoutertheme{miniframes} % Alternatively: miniframes, infolines, split

% Setup the university's color pallette
\definecolor{UIUCorange}{RGB}{19, 41, 75} % UBC Blue (primary)
\definecolor{UIUCblue}{RGB}{232, 74, 39} % UBC Grey (secondary)

\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}

\lstdefinestyle{python}{
  backgroundcolor=\color{backcolour},
  commentstyle=\color{codegreen},
  keywordstyle=\color{magenta},
  numberstyle=\tiny\color{codegray},
  stringstyle=\color{codepurple},
  basicstyle=\ttfamily\footnotesize,
  breakatwhitespace=false,
  belowskip=-0.5em,
  breaklines=true,
  captionpos=b,
  keepspaces=true,
  numbers=left,
  numbersep=5pt,
  showspaces=false,
  showstringspaces=false,
  showtabs=false,
  tabsize=2
}

\lstset{style=python}

\AtBeginSection[]{
    \begin{frame}
        \vfill
        \centering
        \begin{beamercolorbox}[sep=8pt,center,shadow=true,rounded=true]{title}
            \usebeamerfont{title}\insertsectionhead\par%
        \end{beamercolorbox}
        \vfill
    \end{frame}
}
% Setup the university's color pallette
\definecolor{UIUCorange}{RGB}{19, 41, 75} % UBC Blue (primary)
\definecolor{UIUCblue}{RGB}{232, 74, 39} % UBC Grey (secondary)

\setbeamercolor{palette primary}{bg=UIUCorange,fg=white}
\setbeamercolor{palette secondary}{bg=UIUCblue,fg=white}
\setbeamercolor{palette tertiary}{bg=UIUCblue,fg=white}
\setbeamercolor{palette quaternary}{bg=UIUCblue,fg=white}
\setbeamercolor{structure}{fg=UIUCorange} % itemize, enumerate, etc
\setbeamercolor{section in toc}{fg=UIUCblue} % TOC sections

\setbeamercolor{subsection in head/foot}{bg=UIUCorange,fg=UIUCblue}
\setbeamercolor{subsection in head/foot}{bg=UIUCorange,fg=UIUCblue}

\usepackage[utf8]{inputenc}
\usepackage{graphicx}

%Information to be included in the title page:
\title{\textbf{Lists}}
\author{\textbf{David H Smith IV}}
\institute[\textbf{UIUC}]{\textbf{University of Illinois Urbana-Champaign}}
\date{\textbf{Tues, Thu 21 2021}}

\setbeamertemplate{title page}[default][colsep=-4bp,rounded=true]
\addtobeamertemplate{title page}{\vspace{3\baselineskip}}{}
\addtobeamertemplate{title page}{
  \begin{textblock*}{\paperwidth}(-1.0em, -1.2em)
    \includegraphics[width=\paperwidth, height=\paperheight]{imgs/uiuc.png}
  \end{textblock*}
}{}

\begin{document}

\frame{\titlepage}

\section{Reminders}

%
% Slide 1
%
\begin{frame}
  \frametitle{Reminders}
  \begin{itemize}
    \item Topic 11 participation due Friday
    \item Post reading 11 due Friday
    \item Homework 10p2 homework due Friday
    \item Quiz 3 next week
  \end{itemize}
\end{frame}

\section{Lists}

%
% Slide 2
%
\begin{frame}[fragile]
  \frametitle{Poll Question: Tracing}
  What is the value of \lstinline|x|.
  \begin{lstlisting}[language=Python, autogobble]
  x = [v+v for v in ['1', '2', '3']]
  \end{lstlisting}
  \vfill
  \begin{enumerate}[A]
    \item \lstinline|['11', '22', '33']|
    \item \lstinline|['1', '2', '3']|
    \item \lstinline|[1, 4, 9]|
    \item TypeError
  \end{enumerate}
\end{frame}

%
% Slide 2
%
\begin{frame}[fragile]
  \frametitle{List Comprehensions}
  \begin{lstlisting}[language=Python, autogobble]
  # Basic list comprehension
  [expression for value in sequence]

  # Conditional list comprehension with if
  [expresssion for value in sequence if condition]

  #Conditional list comprehension with if-else
  [expresssion if conditition else <default> for value in sequence]
  \end{lstlisting}
  \vfill
  \begin{itemize}
    \item Doesn't enable any new functionality
    \item \textit{Syntactic Sugar: } Makes code more efficient to write
  \end{itemize}
\end{frame}

%
% Slide 2
%
\begin{frame}[fragile]
  \frametitle{Poll Question: List Comprehension}
  What is the value of \lstinline|y|.
  \begin{lstlisting}[language=Python, autogobble]
  y = [c for c in 'alma mater' if c in 'aeiou']
  \end{lstlisting}
  \vfill
  \begin{enumerate}[A]
    \item \lstinline|'alma mater'|
    \item \lstinline|['alma mater']|
    \item \lstinline|'aaae'|
    \item \lstinline|['a', 'a', 'a', 'e']|
  \end{enumerate}
\end{frame}

\end{document}


text:
%%
%% This is file `askinclude-b9.tex',

%%
\chapter{Chapter B}
\expandafter\let\csname fileb9\endcsname=Y
\endinput
%%
%% End of file `askinclude-b9.tex'.

max_stars_repo_name: ho-tex/askinclude

max_issues_repo_name: ho-tex/askinclude

max_forks_repo_name: ho-tex/askinclude


text:
\part{Lecture 05: Temporal-Difference Learning}
\title[RL Lecture 05]{Lecture 05: Temporal-Difference Learning}
\date{}
\frame{\titlepage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Temporal-Difference Learning and the Previous Methods %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Temporal-Difference Learning and the Previous Methods}
Temporal-difference (TD) learning combines the previous ideas introduced in DP and MC:
\begin{itemize}
	\item From Monte Carlo (MC) methods: Learns directly from experience.
	\item From dynamic programming (DP): Updates estimates based on other learned estimates (bootstrap).
\end{itemize}
\pause
\vspace{1cm}
Hence, TD characteristics are:
\begin{itemize}
	\item Allows model-free prediction and control in unknown MDPs.
	\item Updates policy evaluation and improvement in an online fashion (i.e., not per episode) by bootstrapping.
	\item Still assumes  finite MDP problems (or problems close to that).
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Temporal-Difference Prediction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Table of Contents}
\tableofcontents
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% General TD Prediction Updates %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{General TD Prediction Updates}
Recap the every-visit MC update rule \eqref{eq:inc_impl_MC_pred_non_stat} for non-stationary problems:
\begin{equation}
	\hat{v}(x_k) \leftarrow \hat{v}(x_k) + \alpha\left[g_k - \hat{v}(x_k)\right] .
	\label{eq:MC_non_stat_up_lec05}
\end{equation}
\begin{itemize}
	\item $\alpha\in\left\{\mathbb{R}|0<\alpha<1\right\}$ is the forgetting factor / step size.
	\item $g_k$ is the \hl{target} of the incremental update rule.
	\item To execute the update \eqref{eq:MC_non_stat_up_lec05} one has to wait until the episode's termination since only then $g_k$ is available (MC requirement).
\end{itemize}\pause
\begin{block}{One-step TD / TD(0) update}
\begin{equation}
	\hat{v}(x_k) \leftarrow \hat{v}(x_k) + \alpha\left[r_{k+1}+\gamma\hat{v}(x_{k+1}) - \hat{v}(x_k)\right] .
	\label{eq:TD_zero_update}
\end{equation}
\vspace{-0.5cm}
\begin{itemize}
	\item Here, the TD target is $r_{k+1}+\gamma\hat{v}(x_{k+1})$.
	\item TD is bootstrapping: estimate $\hat{v}(x_k)$ based on $\hat{v}(x_{k+1})$.
	\item Delay time of one step and no need to wait until the episode's end.
\end{itemize}
\end{block}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Algorithmic Implementation: TD-Based Prediction %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Algorithmic Implementation: TD-Based Prediction}
\setlength{\algomargin}{0.5em}
\begin{algorithm}[H]
\SetKwInput{Input}{input}
\SetKwInput{Output}{output}
\SetKwInput{Init}{init}
\SetKwInput{Param}{parameter}
\Input{a policy $\pi$ to be evaluated}
\Output{estimate of $\bm{v}_{\mathcal{X}}^{\pi}$ (i.e., value estimates for all states				 $x\in\mathcal{X}$)}
\Init{$\hat{v}(x)\, \forall \, x\in\mathcal{X}$ arbitrary except $v_0(x)=0$ if $x$ is terminal}
 \For{$j=1,\ldots,J$ episodes}{
		Initialize $x_{0}$\;
		\For{$k=0, 1, 2 \ldots $ time steps}{
			$u_k \leftarrow$ apply action from $\pi(x_k)$\;
			Observe $x_{k+1}$ and $r_{k+1}$\;
			$\hat{v}(x_k) \leftarrow \hat{v}(x_k) + \alpha\left[r_{k+1}+\gamma\hat{v}(x_{k+1}) - \hat{v}(x_k)\right] $ \;
			Exit loop if $x_{k+1}$ is terminal\;
		}
	}
\caption{Tabular TD(0) prediction}
\label{algo:TD_zero_state_prediction_tabular}
\end{algorithm}
\begin{itemize}
	\item Note that the algorithm can be directly adapted to action-value prediction as it will be used for the later TD-based control approaches.
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TD Error %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{TD Error}
\begin{columns}[t,onlytextwidth]
\begin{column}{0.25\textwidth}
\begin{minipage}[c]{\linewidth}
	\begin{figure}
		\includegraphics[width=0.5cm]{fig/lec05/Back_Up_TD.pdf}
		\caption{Back up diagram for TD(0)}
		\label{fig:Back_up_TD0}
	\end{figure}
\end{minipage}
\end{column}
\hfill
\begin{column}{0.72\textwidth}
\begin{minipage}[c]{\linewidth}
	\begin{itemize}
		\item TD as well as MC use \hl{sample updates}.
		\item Looking ahead to a sample successor state including its value and the reward along the way to compute a backed up value estimate.
	\end{itemize}
\end{minipage}
\end{column}
\end{columns}
\vspace{0.5cm}\pause
The \hl{TD error} is:
\begin{equation}
	\delta_k = r_{k+1}+\gamma \hat{v}(x_{k+1}) - \hat{v}(x_{k}).
\end{equation}
\begin{itemize}
	\item $\delta_k$ is available at time step $k+1$.
	\item Iteratively $\delta_k$ converges towards zero.
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TD Error and its Relation to the MC Error %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{TD Error and its Relation to the MC Error }
\onslide<1->{Let's assume that the TD(0) estimate $\hat{v}(x)$ is not changing over one episode as it would be for MC prediction:
\begin{equation}
\begin{split}
\underbrace{g_k - \hat{v}(x_k)}_{\mbox{MC-error}} &= r_{k+1} + \gamma g_{k+1} - \hat{v}(x_k)	+\gamma  \hat{v}(x_{k+1})	-\gamma  \hat{v}(x_{k+1}),\\}
																									\onslide<2->{&=\delta_k + \gamma(g_{k+1} - \hat{v}(x_{k+1})),\\}
																									\onslide<3->{&=\delta_k + \gamma \delta_{k+1} + \gamma^2(g_{k+2} - \hat{v}(x_{k+2})),\\}
																									\onslide<4->{&=\delta_k + \gamma \delta_{k+1} + \gamma^2 \delta_{k+2} +\gamma^3(g_{k+3} - \hat{v}(x_{k+3})),\\}
																									\onslide<5->{&=\cdots ,\\
																									&=\sum_{i=k}^{T-1} \gamma^{i-k}\delta_i.}
\end{split}
\end{equation}
\onslide<5->{
\begin{itemize}
	\item MC error is the discounted sum of TD errors in this simplified case.
	\item If $\hat{v}(x)$ is updated during one episode (as expected in TD(0)), the above identity only holds approximately.
\end{itemize}}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Overview of the RL methods considered so far %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Overview of the RL Methods Considered so far}
\begin{figure}
	\includegraphics[width=7cm]{fig/lec05/Compare_RL_Methods_Update.pdf}
	\caption{Comparison of the RL methods considered so far with regard to the update rules (source: R. Sutton and G. Barto, Reinforcement learning: an introduction, 2018, \href{https://creativecommons.org/licenses/by-nc-nd/2.0/}{CC BY-NC-ND 2.0})}
	\label{fig:Compare_RL_Methods_Update}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Driving Home Example (1) %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Driving Home Example (1)}
\begin{table}
	\centering
		\begin{tabular}{l|M{2cm}|M{2cm}|M{2cm}}
			\onslide<1->{
			state & elapsed time  & predicted time to go & predicted total time\\
			\hline
			leaving office & 0 & 30 & 30\\
			}
			\onslide<2->reaching car, raining & 5 & 35 &40\\
			\onslide<3->exiting highway & 20 & 15 & 35\\
			\onslide<4->behind truck & 30 & 10 & 40\\
			\onslide<5->home street & 40 & 3 & 43\\
			\onslide<6->arrive home & 43 & 0 &43
		\end{tabular}
	\onslide<1->\caption{Exemplary driving home journey assuming a given policy and all numbers denote minutes (source: R. Sutton and G. Barto, Reinforcement learning: an introduction, 2018, \href{https://creativecommons.org/licenses/by-nc-nd/2.0/}{CC BY-NC-ND 2.0})}
	\label{tab:driving_home_example}
\end{table}

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Driving Home Example (2) %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Driving Home Example (2)}
\begin{figure}
	\includegraphics[width=10cm]{fig/lec05/Driving_home_example.pdf}
	\caption{Updates by MC (left) and TD (right) for $\alpha = 1$ (source: R. Sutton and G. Barto, Reinforcement learning: an introduction, 2018, \href{https://creativecommons.org/licenses/by-nc-nd/2.0/}{CC BY-NC-ND 2.0})}
	\label{fig:Driving_home_example}
\end{figure}
\begin{itemize}
	\item TD can learn before knowing the final outcome.
	\begin{itemize}
		\item TD learns after every step.
		\item MC must wait until the episode's end.
	\end{itemize}
	\item TD could learn without a final outcome.
	\begin{itemize}
		\item MC is only applicable to episodic tasks.
		\item TD can learn from incomplete sequences, i.e., in continuing tasks.
	\end{itemize}
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TD(0) Prediction Example: Forest Tree MDP (1 )%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{TD(0) Prediction Example: Forest Tree MDP (1)}
Let's reuse the forest tree MDP example with \textit{fifty-fifty policy} and discount factor $\gamma=0.8$
plus disaster probability $\alpha=0.2$:
\vspace{0.5cm}
\begin{figure}
	%\hspace*{-1.5cm}
	\includegraphics[width=9cm]{fig/lec04/Forest_Markov_Decision_Process_State_Value.pdf}
	\caption{Forest MDP with fifty-fifty-policy including state values}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TD(0) Prediction Example: Forest Tree MDP(2)%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{TD(0) Prediction Example: Forest Tree MDP (2)}
\vspace{-0.5cm}
\begin{figure}
\hspace*{-1.0cm}
	\includegraphics{fig/lec05/Forest_Tree_TD0_Prediction.pdf}
	\caption{State-value estimate of forest tree MDP using TD(0) prediction over the number of episodes being evaluated (mean and standard deviation are calculated based on 2000 independent runs)}
	\label{fig:Forest_Tree_TD0_Prediction}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TD(0) vs. MC Prediction Example: Forest Tree MDP(1)%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{TD(0) vs. MC Prediction Example: Forest Tree MDP (1)}
\vspace{-0.25cm}
\begin{figure}
\hspace*{-0.5cm}
	\includegraphics{fig/lec05/Forest_Tree_TD0_MC_RMS_Prediction_Zero_Init_500_eps.pdf}
	\caption{Averaged mean of state-value estimates of forest tree MDP using TD(0) and MC over 1000 independent runs with $\hat{v}_0(x)=0\,\forall x\in\mathcal{X}$}
	\label{fig:Forest_Tree_TD0_MC_RMS_Prediction_Zero_Init_500_eps}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TD(0) Prediction Example: Forest Tree MDP(2)%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{TD(0) vs. MC Prediction Example: Forest Tree MDP (2)}
\vspace{-0.25cm}
\begin{figure}
\hspace*{-0.5cm}
	\includegraphics{fig/lec05/Forest_Tree_TD0_MC_RMS_Prediction_Good_Init_200_eps.pdf}
	\caption{Averaged mean of state-value estimates of forest tree MDP using TD(0) and MC over 1000 independent runs with \hl{$\hat{v}_0(x)\approx v(x) \,\forall x\in\mathcal{X}$}}
	\label{fig:Forest_Tree_TD0_MC_RMS_Prediction_Good_Init_200_eps}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Convergence of TD(0)%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Convergence of TD(0)}
\vspace{-0.3cm}
\begin{theo}{Convergence of TD(0)}{converge_TD_zero}
Given a finite MDP and a fixed policy $\pi$ the state-value estimate of TD(0) converges to the true $v_\pi$
\begin{itemize}
	\item in the mean for a constant but sufficiently small step-size $\alpha$ and
	\item with probability 1 if the step-size holds the condition
	\begin{equation}
		\sum_{k=1}^{\infty}  \alpha_k = \infty \quad \mbox{and} \quad \sum_{k=1}^{\infty}  \alpha_k^2 < \infty .
		\label{eq:stoch_approx_condition}
	\end{equation}
\end{itemize}
Above $k$ is the sample index (i.e., how often the TD update was applied).
\end{theo}\pause
\begin{itemize}
	\item In particular, $\alpha_k=\frac{1}{k}$ meets the condition \eqref{eq:stoch_approx_condition}.\pause
	\item Often TD(0) converges faster than MC, but there is no guarantee (see examples above and in Barto/Sutton book).\pause
	\item TD(0) can be more sensitive to bad initializations $\hat{v}_0(x)$ compared to MC.
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Batch Training%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Batch Training}
\begin{itemize}
	\item If experience $\rightarrow\infty$ both MC and TD converge $\hat{v}(x)\rightarrow v(x)$.
	\item But how to handle limited experience, i.e., a finite set of episodes
	\begin{align*}
		&x_{1,1}, u_{1,1} , r_{2,1}, \ldots, x_{T_1,1},\\
		&x_{1,2}, u_{1,2} , r_{2,2}, \ldots, x_{T_2,2},\\
		&\hspace{2cm}\vdots\\
		&x_{1,j}, u_{1,j} , r_{2,j}, \ldots, x_{T_j,j},\\
		&\hspace{2cm}\vdots\\
		&x_{1,J}, u_{1,J} , r_{2,J}, \ldots, x_{T_J,J}.
	\end{align*}
\end{itemize}\pause
\begin{block}{Batch training}
\begin{itemize}
	\item Process all available episodes $j\in\left[1,J\right]$ repeatedly to MC and TD.
	\item If the step size $\alpha$ is sufficiently small both will converge to certain steady-state values.
\end{itemize}
\end{block}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Batch Training: AB-Example (1) %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Batch Training: AB-Example (1)}
\begin{columns}[t,onlytextwidth]
\begin{column}{0.58\textwidth}
\begin{minipage}[c]{\linewidth}
	\begin{figure}
		\includegraphics[width=4.5cm]{fig/lec05/Batch_AB_Example.pdf}
		\caption{Example environment (source: R. Sutton and G. Barto, Reinforcement learning: an introduction, 2018, \href{https://creativecommons.org/licenses/by-nc-nd/2.0/}{CC BY-NC-ND 2.0})}
		\label{fig:Batch_AB_Example}
	\end{figure}
\end{minipage}
\end{column}
\hfill
\begin{column}{0.40\textwidth}
\begin{minipage}[c]{\linewidth}
	\begin{itemize}
		\item Only two states: A, B
		\item No discounting
		\item 8 episodes of experience available (see \tabref{tab:state_reward_AB_example})
		\item What is $\hat{v}(A)$ and $\hat{v}(B)$ using batch training TD(0) and MC?
	\end{itemize}
\end{minipage}
\end{column}
\end{columns}
\vspace{0.25cm}
\begin{table}
	\centering
		\begin{tabular}{M{2cm}|M{2cm}}
			A, 0, B, 0 & B,1\\
			\hline
			B,1 & B,1\\
			\hline
			B,1	& B,1\\
			\hline
			B,1	& B,0
		\end{tabular}
	\caption{Example state-reward sequences for \figref{fig:Batch_AB_Example}}
	\label{tab:state_reward_AB_example}
\end{table}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Batch Training: AB-Example (2) %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Batch Training: AB-Example (2)}
First, recap MC and TD(0) update rules:
\begin{align*}
	\mbox{MC}: \quad &\hat{v}(x_k) \leftarrow \hat{v}(x_k) + \alpha\left[g_k - \hat{v}(x_k)\right],\\
	\mbox{TD}:	\quad&\hat{v}(x_k) \leftarrow \hat{v}(x_k) + \alpha\left[r_{k+1}+\gamma\hat{v}(x_{k+1}) - \hat{v}(x_k)\right] .
\end{align*}\pause
Then, in steady state one receives:
\begin{align*}
	\mbox{MC}: \quad &0=\alpha\left[g_k - \hat{v}(x_k)\right]=g_k - \hat{v}(x_k),\\
	\mbox{TD}:	\quad&0=\alpha\left[r_{k+1}+\gamma\hat{v}(x_{k+1}) - \hat{v}(x_k)\right] =r_{k+1}+\gamma\hat{v}(x_{k+1}) - \hat{v}(x_k).
\end{align*}\pause
Considering a batch learning sweep over $j=1,\ldots,J$ episodes:
\begin{align*}
	\mbox{MC}: \quad &0=\sum_{j=1}^J g_{k,j} - \hat{v}(x_{k,j}),\\
	\mbox{TD}:	\quad&0=\sum_{j=1}^J r_{k+1,j}+\gamma\hat{v}(x_{k+1,j}) - \hat{v}(x_{k,j}).
\end{align*}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Batch Training: AB-Example (3) %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Batch Training: AB-Example (3)}
Apply the previous equations first to state B. Since B is a terminal state, $\hat{v}(x_{k+1})=0$ and $g_{k,j}= r_{k+1,j}$ apply, i.e., the MC and TD updates are identical for B:
\begin{alignat*}{3}
	\mbox{MC}|_{x=\mbox{B}}: \quad &0=\sum_{j=1}^J g_{k,j} - \hat{v}(x_{k,j})\quad &&\Leftrightarrow \quad &&\hat{v}(\mbox{B})=\frac{1}{J}\sum_{j=1}^J g_{k,j},\\
	\mbox{TD}|_{x=\mbox{B}}:	\quad&0=\sum_{j=1}^J r_{k+1,j}- \hat{v}(x_{k,j})\quad &&\Leftrightarrow \quad &&\hat{v}(\mbox{B})=\frac{1}{J}\sum_{j=1}^J g_{k,j}.
\end{alignat*}\pause
This is the average return of the available episodes from \tabref{tab:state_reward_AB_example} , i.e., $6\times 1$ and $2\times 0$:
\begin{equation}
	\hat{v}(\mbox{B})|_{\mbox{MC}}=\hat{v}(\mbox{B})|_{\mbox{TD}}=\frac{6}{8}=0.75\, .
\end{equation}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Batch Training: AB-Example (4) %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Batch Training: AB-Example (4)}
Now consider state A assuming the steady state of batch learning process:
\begin{itemize}
	\item The instantaneous reward is always $r=0$.
	\item The TD bootstrap estimate of B is $\hat{v}(x_{k+1,j})=\hat{v}(B)=\frac{3}{4}$.
\end{itemize}\pause
\begin{align*}
	\mbox{MC}: \quad &0=\sum_{j=1}^J g_{k,j} - \hat{v}(x_{k,j})=\sum_{j=1}^J g_{k,j} - \hat{v}(A),\\
	\mbox{TD}:	\quad&0=\sum_{j=1}^J r_{k+1,j}+\gamma\hat{v}(x_{k+1,j}) - \hat{v}(x_{k,j})=\sum_{j=1}^J \gamma\hat{v}(B) - \hat{v}(A).
\end{align*}\pause
Looking at \tabref{tab:state_reward_AB_example} there is only one episode visiting state A, where the sample return is $g_{k,j}=0$. Hence, it follows:
\begin{equation*}
	\hat{v}(\mbox{A})|_{\mbox{MC}} =0, \quad \hat{v}(\mbox{A})|_{\mbox{TD}} =\gamma\hat{v}(B)=\frac{3}{4}.
\end{equation*}
Where does this mismatch between the MC and TD estimates come from?
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Certainty Equivalence %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Certainty Equivalence}
\begin{itemize}
	\item MC batch learning converges to the \hl{least squares fit} of the sampled returns:
	\begin{equation}
		\sum_{j=1}^{J}\sum_{k=1}^{T_j} \left(g_{k,j}- \hat{v}(x_{k,j})\right)^2 .
	\end{equation}\pause\vspace{-0.25cm}
	\item TD batch learning converges to the \hl{maximum likelihood estimate} such that $\left\langle\mathcal{X}, \mathcal{U}, \hat{\mathcal{P}}, \hat{\mathcal{R}}, \gamma \right\rangle$ explains the data with highest probability:
	\begin{equation}
		\begin{split}
		\hat{p}_{xx'}^u&=\frac{1}{n(x,u)}\sum_{j=1}^{J}\sum_{k=1}^{T_j} 1(X_{k+1}=x'|X_{k}=x, U_k=u),\\
		\hat{\mathcal{R}}_{x}^u&=\frac{1}{n(x,u)}\sum_{j=1}^{J}\sum_{k=1}^{T_j} 1(X_{k}=x|U_k=u) r_{k+1,j}.
	\end{split}
	\end{equation}
	\item Here, TD assumes a MDP problem structure and is absolutely certain that its model estimate describes the real world perfectly (so-called \hl{certainty equivalence}).
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Temporal-Difference On-Policy Control: Sarsa}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Table of Contents}
\tableofcontents[currentsection]
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Applying Generalized Policy Iteration (GPI) to MC Control %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Applying Generalized Policy Iteration (GPI) to TD Control}
GPI concept is directly applied to the TD framework using action values:
\begin{equation}
	\pi_0 \rightarrow \hat{q}_{\pi_0} \rightarrow \pi_1 \rightarrow \hat{q}_{\pi_1} \rightarrow \cdots \pi^* \rightarrow \hat{q}_{\pi^*} \, .
\end{equation}\pause
\begin{block}{One-step TD / TD(0) action-value update (Sarsa)}
	The TD(0) action-value update is:
		\begin{equation}
		\hat{q}(x_k, u_k) \leftarrow \hat{q}(x_k, u_k) + \alpha\left[r_{k+1}+\gamma\hat{q}(x_{k+1}, u_{k+1}) - \hat{q}(x_k, u_k)\right] .
		\label{eq:TD_zero_update_action_value}
		\end{equation}
		\hl{Sarsa}: \hl{s}tate, \hl{a}ction, \hl{r}eward, (next) \hl{s}tate, (next) \hl{a}ction evaluation
	\end{block}\pause
\begin{itemize}
	\item In contrast to MC: continuous online updates of policy evaluation and improvement.\pause
	\item On-policy approach requires exploration, e.g., by an $\varepsilon$-greedy policy:
	\begin{equation}
		\pi_i(u|x)\leftarrow\begin{cases}1-\varepsilon+\varepsilon/|\mathcal{U}|, \quad u=\tilde{u},\\ \varepsilon/|\mathcal{U}|, \quad u\neq\tilde{u}.\end{cases}
	\end{equation}
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TD-Based On-Policy Control (Sarsa) %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{TD-Based On-Policy Control (Sarsa)}
\vspace{-0.2cm}
\setlength{\algomargin}{0.5em}
\begin{algorithm}[H]
\footnotesize
\SetKwInput{Input}{input}
\SetKwInput{Output}{output}
\SetKwInput{Init}{init}
\SetKwInput{Param}{parameter}
\Param{$\varepsilon\in\left\{\mathbb{R}|0<\varepsilon<<1\right\}, \quad \alpha\in\left\{\mathbb{R}|0<\alpha<1\right\}$}
\Init{$\hat{q}(x,u)$ arbitrarily (except terminal states) $\forall \, \left\{x\in\mathcal{X}, u\in\mathcal{U}\right\}$}
\For{$j=1,2,\ldots$ episodes}{
	Initialize $x_0$\;
	Choose $u_0$ from $x_0$ using a soft policy (e.g., $\varepsilon$-greedy) derived from $\hat{q}(x,u)$\;
	$k \leftarrow 0$\;
	\Repeat{$x_k$ is terminal}{
				Take action $u_k$, observe $r_{k+1}$ and $x_{k+1}$\;
				Choose $u_{k+1}$ from $x_{k+1}$ using a soft policy derived from $\hat{q}(x,u)$\;
				$\hat{q}(x_k, u_k) \leftarrow \hat{q}(x_k, u_k) + \alpha\left[r_{k+1}+\gamma\hat{q}(x_{k+1}, u_{k+1}) - \hat{q}(x_k, u_k)\right]$\;
				$k \leftarrow k+1$\;
	}
}
\caption{TD-based on-policy control (Sarsa)}
\label{algo:Sarsa}
\end{algorithm}
Convergence properties are comparable to MC-based on-policy control:
\begin{itemize}
	\item Policy improvement theorem \theoref{theo:policy_improv_eps_greedy} holds.
	\item Greedy in the limit with infinite exploration (GLIE) from \defref{defi:GLIE} and step-size requirements in \theoref{theo:converge_TD_zero} apply.
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Sarsa Example: Windy Gridworld %%
\frame{\frametitle{Example: Sarsa with Windy Gridworld}
\begin{columns}[c,onlytextwidth]
\begin{column}{0.58\textwidth}
\begin{minipage}[t]{\linewidth}
	\begin{figure}
		\includegraphics[width=7cm]{fig/lec05/Windy_Gridworld.pdf}
		\caption{Windy gridworld environment (source: R. Sutton and G. Barto, Reinforcement learning: an introduction, 2018, \href{https://creativecommons.org/licenses/by-nc-nd/2.0/}{CC BY-NC-ND 2.0})}
		\label{fig:Windy_Gridworld}
	\end{figure}
\end{minipage}
\end{column}
\hfill
\begin{column}{0.40\textwidth}
\begin{minipage}[t]{\linewidth}
	\begin{itemize}
		\item $r=-1$ per time step
		\item No discounting
		\item South-north wind according to value below each column
		\item $\varepsilon=0.1$
		\item $\alpha=0.5$
		\item Initial $\hat{q}(x,u)=0$
	\end{itemize}
	\vspace{1cm}\pause
	\begin{itemize}
		\item What could be a possible issue when applying MC control?
	\end{itemize}
\end{minipage}
\end{column}
\end{columns}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Sarsa Example: Forest Tree MDP (1)%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Sarsa Example: Forest Tree MDP (1)}

\begin{figure}
	\hspace*{-1.0cm}
	\includegraphics[width=14cm]{fig/lec05/Forest_Tree_Sarsa_alpha_0.2.png}
	\caption{Sarsa-based control with \hl{$\alpha_{Sarsa}=0.2$} and $\varepsilon$-greedy policy with $\varepsilon=0.2$ of forest tree MDP over the number of episodes being evaluated (mean and standard deviation are calculated based on 2000 independent runs)}
	\label{fig:Sarsa_forest_tree_02}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Sarsa Example: Forest Tree MDP (2)%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Sarsa Example: Forest Tree MDP (2)}

\begin{figure}
	\hspace*{-1.0cm}
	\includegraphics[width=14cm]{fig/lec05/Forest_Tree_Sarsa_alpha_0.1.png}
	\caption{Sarsa-based control with \hl{$\alpha_{Sarsa}=0.1$} and $\varepsilon$-greedy policy with $\varepsilon=0.2$ of forest tree MDP over the number of episodes being evaluated (mean and standard deviation are calculated based on 2000 independent runs)}
	\label{fig:Sarsa_forest_tree_01}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Sarsa Example: Forest Tree MDP (3)%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Sarsa Example: Forest Tree MDP (3)}

\begin{figure}
	\hspace*{-1.0cm}
	\includegraphics[width=14cm]{fig/lec05/Forest_Tree_Sarsa_alpha_0.05.png}
	\caption{Sarsa-based control with \hl{$\alpha_{Sarsa}=0.05$} and $\varepsilon$-greedy policy with $\varepsilon=0.2$ of forest tree MDP over the number of episodes being evaluated (mean and standard deviation are calculated based on 2000 independent runs)}
	\label{fig:Sarsa_forest_tree_005}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Sarsa Example: Forest Tree MDP (4)%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Sarsa Example: Forest Tree MDP (4)}

\begin{figure}
	\hspace*{-1.0cm}
	\includegraphics[width=14cm]{fig/lec05/Forest_Tree_Sarsa_alpha_adapt}
	\caption{Sarsa-based control with \hl{adaptive $\alpha_{Sarsa}=\frac{1}{\sqrt{j}}$} ($j=$episode) and $\varepsilon$-greedy policy with $\varepsilon=0.2$ of forest tree MDP over the number of episodes being evaluated (mean and standard deviation are calculated based on 2000 independent runs)}
	\label{Forest_Tree_Sarsa_alpha_adapt}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Temporal-Difference Off-Policy Control: \texorpdfstring{$Q$}{Q}-Learning}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Table of Contents}
\tableofcontents[currentsection]
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Q-Learning Approach %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{$Q$-Learning Approach}
Similar to Sarsa updates, but $Q$-learning directly estimates $q^*$:
\begin{block}{$Q$-learning action-value update}
	The $Q$-learning action-value update is:
		\begin{equation}
		\hat{q}(x_k, u_k) \leftarrow \hat{q}(x_k, u_k) + \alpha\left[r_{k+1}+\gamma \max_u \hat{q}(x_{k+1}, u) - \hat{q}(x_k, u_k)\right] .
		\label{eq:Q_learning_update_action_value}
		\end{equation}
		This is an \hl{off-policy} update, since the optimal action-value function is updated independent of a given behavior policy.
	\end{block}\pause
Requirement for $Q$-learning control:
\begin{itemize}
	\item Coverage: behavior policy $b$  has nonzero probability of selecting actions that might be taken by the target policy $\pi$.
	\item Consequence: behavior policy $b$ is soft (e.g., $\varepsilon$-soft).
	\item Step-size requirements \eqref{eq:stoch_approx_condition} regarding $\alpha$ apply.
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TD-Based Off-Policy Control (Q-learning) %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{TD-Based Off-Policy Control ($Q$-Learning)}

\setlength{\algomargin}{0.5em}
\begin{algorithm}[H]
\footnotesize
\SetKwInput{Input}{input}
\SetKwInput{Output}{output}
\SetKwInput{Init}{init}
\SetKwInput{Param}{parameter}
\Param{$\varepsilon\in\left\{\mathbb{R}|0<\varepsilon<<1\right\}, \quad \alpha\in\left\{\mathbb{R}|0<\alpha<1\right\}$}
\Init{$\hat{q}(x,u)$ arbitrarily (except terminal states) $\forall \, \left\{x\in\mathcal{X}, u\in\mathcal{U}\right\}$}
\For{$j=1,2,\ldots$ episodes}{
	Initialize $x_0$\;
	$k \leftarrow 0$\;
	\Repeat{$x_k$ is terminal}{
				Choose $u_k$ from $x_k$ using a soft policy  derived from $\hat{q}(x,u)$\;
				Take action $u_k$, observe $r_{k+1}$ and $x_{k+1}$\;
				$\hat{q}(x_k, u_k) \leftarrow \hat{q}(x_k, u_k) + \alpha\left[r_{k+1}+\gamma \max_{u} \hat{q}(x_{k+1}, u) - \hat{q}(x_k, u_k)\right]$\;
				$k \leftarrow k+1$\;
	}
}
\caption{TD-based off-policy control ($Q$-learning)}
\label{algo:Q_learning}
\end{algorithm}
\vspace{0.5cm}
\begin{itemize}
	\item Even simpler compared to Sarsa implementation in \algoref{algo:Sarsa}.
	\item As discussed with MC-based off-policy control: avoidance of the exploration-optimality trade-off for on-policy methods.
	\item No importance sampling required as for off-policy MC-based control.
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Q-Learning Control Example: Cliff Walking %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{$Q$-Learning Control Example: Cliff Walking}
\begin{columns}[c,onlytextwidth]
\begin{column}{0.58\textwidth}
\begin{minipage}[t]{\linewidth}
	\begin{figure}
		\includegraphics[width=5.5cm]{fig/lec05/Cliff_Walking.pdf}
		\caption{Cliff walking environment (source: R. Sutton and G. Barto, Reinforcement learning: an introduction, 2018, \href{https://creativecommons.org/licenses/by-nc-nd/2.0/}{CC BY-NC-ND 2.0})}
		\label{fig:Cliff_Walking}
	\end{figure}
\end{minipage}
\end{column}
\hfill
\begin{column}{0.40\textwidth}
\begin{minipage}[t]{\linewidth}
	\begin{itemize}
		\item $r=-1$ per time step
		\item Large penalty if you fall off the cliff
		\item No discounting
		\item $\varepsilon=0.1$
	\end{itemize}
	\vspace{1cm}\pause
	\begin{itemize}
		\item Why is Sarsa better in this example?
		\item And what policy's performance is shown here in particular?
	\end{itemize}
\end{minipage}
\end{column}
\end{columns}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Expected Sarsa}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Table of Contents}
\tableofcontents[currentsection]
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Q-Learning Approach %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Expected Sarsa: A Hybrid Approach}
\begin{block}{Expected Sarsa action-value update}
	The expected Sarsa action-value update is:
		\small
		\begin{equation}
		\begin{split}
		\hat{q}(x_k, u_k) &\leftarrow \hat{q}(x_k, u_k) + \alpha\left[r_{k+1}+\gamma \El{\hat{q}(x_{k+1}, u_{k+1})|x_{k+1}}{\pi} - \hat{q}(x_k, u_k)\right] ,\\
											&\leftarrow \hat{q}(x_k, u_k) + \alpha\left[r_{k+1}+\gamma \sum_{u} \pi(u|x_{k+1}) \hat{q}(x_{k+1}, u) - \hat{q}(x_k, u_k)\right].
		\end{split}
		\label{eq:Expected_Sarsa_update_action_value}
		\end{equation}
		\normalsize
		This is an \hl{off or on-policy} update, depending on whether the action leading to $x_{k+1}$ was taken from the target or a varying behavior policy.
	\end{block}
\pause
\begin{itemize}
	\item Moves deterministically in the same direction as Sarsa moves in expectation (accordingly, it is called expected Sarsa). \pause
	\item Computationally more complex than Sarsa but reduces variance due to random selection of $u_{k+1}$. \pause
	\item If $\pi$ is greedy and $b$ is an exploratory behavior policy, then expected Sarsa is exactly $Q$-learning (generalization).
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Back-up Diagrams for TD-Based Control Approaches %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Back-up Diagrams for TD-Based Control Approaches}
\begin{minipage}[t]{0.32\linewidth}
	\begin{figure}
		\includegraphics[height=3.0cm]{fig/lec05/Back_Up_Sarsa.pdf}
		\caption{Sarsa}
	\end{figure}
\end{minipage}
\hfill
\begin{minipage}[t]{0.32\linewidth}
	\begin{figure}
		\includegraphics[height=3.0cm]{fig/lec05/Back_Up_Q_learning.pdf}
		\caption{Q-learning}
	\end{figure}
\end{minipage}
\hfill
\begin{minipage}[t]{0.32\linewidth}
	\begin{figure}
		\includegraphics[height=3.0cm]{fig/lec05/Back_Up_Expected_Sarsa.pdf}
		\caption{Expected Sarsa}
	\end{figure}
\end{minipage}
\begin{itemize}
	\item Commonalities:
	\begin{itemize}
		\item Use sample updates based on a one step look ahead evaluation.
		\item Improve estimates based on other estimates (bootstrap).
	\end{itemize}\pause
	\item Distinctions:
	\begin{itemize}
		\item Sarsa updates based on specific state-action transitions.
		\item $Q$-learning updates the optimal policy estimate $q^*$
		\item Expected Sarsa updates considering the expected transitions.
	\end{itemize}
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Comparison Based on Cliff-Walking Example %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Comparison Based on Cliff-Walking Example}
\vspace{-0.2cm}
\begin{figure}
	\hspace*{-1.0cm}
	\includegraphics[width=9cm]{fig/lec05/Cliff_Walking_Extended.pdf}
	\caption{All algorithms used an $\varepsilon$-greedy policy with $\varepsilon = 0.1$. Asymptotic performance is an average over 100,000 episodes whereas interim performance is an average over the first 100 episodes. These data are averages of over 50,000 and 10 runs for the interim and asymptotic cases respectively (source: R. Sutton and G. Barto, Reinforcement learning: an introduction, 2018, \href{https://creativecommons.org/licenses/by-nc-nd/2.0/}{CC BY-NC-ND 2.0})}
	\label{Cliff_Walking_Extended}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Maximization Bias and Double Learning}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Table of Contents}
\tableofcontents[currentsection]
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Maximization Bias %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Maximization Bias}
All control algorithms discussed so far \hl{involve maximization operations}:
\begin{itemize}
	\item $Q$-learning: target policy is greedy and directly uses $\max$ operator for action-value updates.
	\item Sarsa: typically uses an $\varepsilon$-greedy framework, which also involves $\max$ updates during policy improvement.
\end{itemize}\pause
This can lead to a significant \hl{positive bias}:
\begin{itemize}
	\item Maximization over sampled values is used implicitly as an estimate of the maximum value.
	\item This issue is called \hl{maximization bias}.
\end{itemize}\pause
Small example:
\begin{itemize}
	\item Consider a single state $x$ with multiple possible actions $u$.
	\item The true action values are all $q(x,u)=0$ .
	\item The sampled estimates $\hat{q}(x,u)$ are uncertain, i.e., randomly distributed. Some samples are above and below zero.
	\item Consequence: The maximum of the estimate is positive.
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Double Learning Approach %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Double Learning Approach}

Split the learning process:
\begin{itemize}
	\item Divide sampled experience into two sets.
	\item Use sets to estimate independent estimates $\hat{q}_1(x,u)$ and $\hat{q}_2(x,u)$.
\end{itemize}\pause
\vspace{0.5cm}
Assign specific tasks to each estimate:
\begin{itemize}
	\item Estimate the maximizing action:
	\begin{equation}
		 u^*=\argmax_u \hat{q}_1(x,u) .
	\end{equation}\pause
	\item Estimate corresponding action value:
	\begin{equation}
		q(x,u^*) \approx \hat{q}_2(x,u^*)= \hat{q}_2(x,\argmax_u \hat{q}_1(x,u)) .
	\end{equation}\pause
	\item Doubles memory requirements, but amount of computation per step remains the same.
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Double Q-Learning Algorithm %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Double $Q$-Learning Algorithm}
\vspace{0.1cm}
\setlength{\algomargin}{0.5em}
\begin{algorithm}[H]
\footnotesize
\SetKwInput{Input}{input}
\SetKwInput{Output}{output}
\SetKwInput{Init}{init}
\SetKwInput{Param}{parameter}
\Param{$\varepsilon\in\left\{\mathbb{R}|0<\varepsilon<<1\right\}, \quad \alpha\in\left\{\mathbb{R}|0<\alpha<1\right\}$}
\Init{$\hat{q}_1(x,u),\,\hat{q}_2(x,u)$ arbitrarily (except terminal states) $\forall \, \left\{x\in\mathcal{X}, u\in\mathcal{U}\right\}$}
\For{$j=1,2,\ldots$ episodes}{
	Initialize $x_0$\;
	$k \leftarrow 0$\;
	\Repeat{$x_k$ is terminal}{
				Choose $u_k$ from $x_k$ using the policy $\varepsilon$-greedy based on $\hat{q}_1(x,u)+\hat{q}_2(x,u)$\;
				Take action $u_k$, observe $r_{k+1}$ and $x_{k+1}$\;
				\eIf{$n\sim \mathcal{N}(\mu=0, \sigma)>0$}{
				$\hat{q}_1(x_k, u_k) \leftarrow \hat{q}_1(x_k, u_k) + \alpha\left[r_{k+1}+\gamma \hat{q}_2(x_{k+1}, \argmax_u \hat{q}_1(x_{k+1},u)) - \hat{q}_1(x_k, u_k)\right]$\;}
				{$\hat{q}_2(x_k, u_k) \leftarrow \hat{q}_2(x_k, u_k) + \alpha\left[r_{k+1}+\gamma \hat{q}_1(x_{k+1}, \argmax_u \hat{q}_2(x_{k+1},u)) - \hat{q}_2(x_k, u_k)\right]$\;}

				$k \leftarrow k+1$\;
	}
}
\caption{TD-based off-policy control with double learning}
\label{algo:double_Q_learning}
\end{algorithm}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Maximization Bias Example %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{Maximization Bias Example}
\vspace{-0.2cm}
\begin{figure}
	\hspace*{-1.0cm}
	\includegraphics[width=9cm]{fig/lec05/Double_Learning_Example.pdf}
	\caption{Comparison of $Q$-learning and double $Q$-learning on a simple episodic MDP. $Q$-learning initially learns to take the left action much more often than the right action, and always takes it significantly more often than the $5 \%$ minimum probability enforced by $\varepsilon$-greedy action selection with $\varepsilon= 0.1$. In contrast, double $Q$-learning is essentially unaffected by maximization bias. These data are averaged over 10,000 runs. The initial action-value estimates were zero. (source: R. Sutton and G. Barto, Reinforcement learning: an introduction, 2018, \href{https://creativecommons.org/licenses/by-nc-nd/2.0/}{CC BY-NC-ND 2.0})}
	\label{Double_Learning_Example}
\end{figure}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Summary %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Summary: What You've Learned Today}
\begin{itemize}
	\item TD unites two key characteristics from DP and MC:
	\begin{itemize}
		\item From MC: Sample-based updates (i.e., operating in unknown MDPs).
		\item From DP: Update estimates based on other estimates (bootstrapping).
	\end{itemize}\pause
	\item TD allows certain simplifications and improvements compared to MC:
	\begin{itemize}
		\item Updates are available after each step and not after each episode.\pause
		\item Off-policy learning comes without importance sampling.\pause
		\item Exploits MDP formalism by maximum likelihood estimates. \pause
		\item Hence, TD prediction and control exhibit a high applicability for many problems.\pause
	\end{itemize}
	\item Batch training can be used when only limited experience is available, i.e., the available samples are re-processed again and again.\pause
	\item Greedy policy improvements can lead to maximization biases and, therefore, slow down the learning process. \pause
	\item TD requires careful tuning of learning parameters:
	\begin{itemize}
		\item Step size $\alpha$: how to tune convergence rate vs. uncertainty / accuracy?
		\item Exploration vs. exploitation: how to visit all state-action pairs?
	\end{itemize}
\end{itemize}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Final Slide %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame{\frametitle{The End for Today}
\vspace{-0.25cm}
\begin{figure}
\hspace*{-0.5cm}
\includegraphics[width=10cm]{fig/lec05/Dilbert.png}
\end{figure}
\vspace{1cm}
\centering
Thanks for your attention and have a nice week!
}


text:
\documentclass[a4paper]{article}
\input{head}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\newcommand{\algrule}[1][.2pt]{\par\vskip.5\baselineskip\hrule height #1\par\vskip.5\baselineskip}
\begin{document}

%-------------------------------
%	TITLE SECTION
%-------------------------------

\title{\textbf{COL351 : Analysis and Design of Algorithm \\ Assignment 2 }}
\author{Gaurav Jain (2019CS10349) \& T Abishek (2019CS10407)}
\date{}
%-------------------------------
%	CONTENTS
%-------------------------------

\maketitle

\section{Algorithms Design book}

Algorithm to partition the chapters into 3 sets $S_1$, $S_2$, $S_3$, so that maximum sum of each set in minimised.

\textbf{Observation:}\\
To minimize the objective, we can find the minimum of every possibility of a chapter being assigned to all 3 sets. We can achieve this by dynamic programming.

\textbf{Algorithm:}

    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Minimisation}\label{alg:ts}
    \begin{algorithmic}[1]
    \Procedure{DP}{a,b,c,i, P, M}\Comment{a,b,c: sum of questions given to Alice, Bob and Charlie}
    \If {M[a][b][c][i] $\neq$ -1}
        \State \Return M[a][b][c][i]
    \EndIf
    \State M[a][b][c][i] = min(DP(a+P[i],b,c,i+1), DP(a,b+P[i],c,i+1), DP(a,b,c+P[i], i+1))
    \State \Return M[a][b][c][i]
    \EndProcedure

    \Procedure{Start}{P, n}
    \State n $\gets$ no. of chapters
    \State P $\gets$ P is array where P[i] is no. of questions in chapter i( 1 to n)
    \State M $\gets$ M is matrix which is used to store computed totals in DP (initially -1)
    \For{i from 0 to $n^2$}
        \For{j from 0 to $n^2$}
            \For {k from 0 to $n^2$}
                \State M[i][j][k][n] = max(i,j,k)
    \EndFor
    \EndFor
    \EndFor
    \State \Return DP(0,0,0,1,P,M)
    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}

    \textbf{Runtime Analysis:}\\
    This is dynamic programming problem, and in the worst case, all the elements of the matrix M will have to be filled to the final answer we are looking for. Dimensions a, b and c can be maximum $n^2$, because each chapter has a maximum of n questions and there are n chapters, so the maximum no. of questions is $n^2$, and thus each person can be assigned a maximum of $n^2$ questions. Dimension i can be maximum n, as there are only n chapters. So, no. of elements in M is $(n^2)^3*n = n^7$, So, the Time Complexity is O($n^7$).

    \textbf{Correctness of Algorithm:}\\
    The correctness of the algorithm can be proved using induction.

    \textit{Base Case:}\\
    When all chapters are assigned i.e. $i=n$ in procedure DP, the max value of a,b and c is max(i,j,k) which is the optimal solution.

    \textit{Induction Hypothesis:}\\
    For all $n \geq j > i$ the algorithm provides the optimal solution using chapters $P[1],P[2],...,P[j]$.

    \textit{Induction Step:}\\
    The $i^{th}$ chapter can be assigned to any of the three sets a, b or c. Thus, the optimal solution is the minimum of the three subproblems generated by including questions of chapter $i$ to the any one of the three sets.

    By induction, the proof for all chapters. Hence, the algorithm gives an optimal solution to the problem.

    \hfill\qedsymbol

\newpage
\section{Course Planner}
\begin{enumerate}[1.]
\item Algorithm to find an order for taking the courses so that a student is able to take all the courses with the prerequisite criteria being satisfied.

    \textbf{Representation:}

    All courses are represented as vertices in a directed graph, with the in-edges of every vertex being the prerequisites.

    \textbf{Observation:}
    The order is required in such a way that all the prerequisites of a course is done before it, i.e, in the required order, all the edges go from left to right and there exists no edge from right to left. This is the same as the aim of topological sorting which can be achieved with a small modification to DFS.

    \textbf{Algorithm:}

    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Topological sorting}\label{alg:ts}
    \begin{algorithmic}[1]
    \Procedure{Topsort}{Graph $G$, $S$, Node $x$, visited}
    %\State $distance \gets$ array of size $|V|$
    \State visited[x] = grey
    \For{each vertex $v$ in $N(x)$} %\Comment{Changing edge weights}
        \If{$visited[v] = white$}
            \State Topsort(G, S, v, visited)
        \EndIf
        \If{$visited[v] = grey$}
            \State \Return Error: Not Possible
        \EndIf

    \EndFor
    \State S.insertFront(x)
    \State visited[x] = black

    \EndProcedure

    \Procedure{Initial}{Graph $G$}
    \State visited $\gets$ array of size of number of vertices(initially white)
    \State S $\gets$ order of taking courses(initially empty)
    \For{each vertex $v$ in G}
        \If{$visited[v] = white$}
            \State Topsort(G, S, v, visited)
        \EndIf
    \EndFor
    \State \Return S
    \EndProcedure
    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}

    \textbf{Runtime Analysis:}\\
    As discussed in class, the runtime complexity of topological sort is equivalent to DFS, i.e, O(m+n).

    \textbf{Correctness of Algorithm:}\\
    There can be no cycles in the graph that we are given so the given graph is a DAG and as discussed in class, topological sort guarantees a order of vertices in case of DAG where edges only go from left to right and not the other way. If we follow this order, it would satisfy the requirement that all courses have to be done only after their prerequisites are completed, as the source of edges represent the destination's prerequisites.

    \hfill\qedsymbol

\newpage
\item Algorithm to find the minimum number of semesters needed to complete
all n courses.

\textbf{Algorithm:}

    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Minimum no. of semesters}\label{alg:ms}
    \begin{algorithmic}[1]
    \Procedure{Minimum\_semester}{Graph G}
    %\State $distance \gets$ array of size $|V|$
    \State $D \gets$ array of buckets where vertices are arranged by their degree
    \State count = 0
    \While{G $\neq$ EMPTY}
        \If{D[0] = EMPTY}
            \State \Return Error: No order possible
        \EndIf
        \For{$v \in D$ with $deg(v) = 0$}
            \State \textsc{RemoveVertex}($G,v$)
        \EndFor
        \State count = count + 1

    \EndWhile
    \State \Return count

    \EndProcedure

    \Procedure{RemoveVertex}{$G,v$}\Comment{Reduces degrees of vertices connected to $v$}
    \State Mark $v$ \Comment{$v$ is removed from invitees list}
    \State $D[deg(v)].\textsc{remove}(v)$
    \For{$j$ from $1$ to $deg(v)$}
    \State $u \gets adj(v)(j)$
    \If{$u$ is marked}
    \State \textbf{continue}
    \EndIf
    %\State Delete $v$ from $adj(u)$
    \State $deg(u) \gets deg(u)-1$
    \State $D[deg(u)+1].\textsc{remove}(u)$
    \State $D[deg(u)].\textsc{insert}(u)$
    \EndFor
    \EndProcedure
    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}

    \textbf{Runtime Analysis:}\\
    The graph is stored in adjacency list as a HashMap mapping each vertex to an unordered set of connected vertices. The time taken to make the graph is $O(m)$.
    Degree of all vertices is also stored separately as a HashMap to give $O(1)$ access to degrees of each vertex and updated accordingly.

    The degree of all the vertices is then sorted using bucket sort with each bucket being an unordered set(Hash) of vertices which allows us to insert and remove in  $O(1)$ time. The buckets themselves are stored as an array of buckets of size N, with the index of the bucket representing the degree of the vertices stored in them. The initial sorting takes $O(m)$ as it is done through a single pass.

    The inner FOR loop inside the WHILE loop in the Select procedure, is also run only $O(n)$ times as each iteration, a vertex is removed, and the maximum no. of vertices that can be removed is n.

    Since the number of edges are $m$ so the procedure \textsc{RemoveVertex}'s FOR loop runs atmost $2*m$  over all the calls as the procedure is called for each vertex only once, and the for loop is run degree(v) times. Sum of the degrees of all the vertices is $2*m$. So the overall running time of the algorithm is $O(m+n)$.
    Since $m \leq n^2$ so the time complexity is $O(n^2)$.

    \textbf{Correctness of Algorithm:}\\
    Claim: Let P be an array of sets, where P[i] = set of courses done by semester i. Let P' be the array representing the optimal(minimum) order of courses and let P be the array representing the above algorithm. Claim is P'[i] $\subseteq$ P[i] for all i.

    Proof: Proof by induction on i

    Base Case: i = 1\\
    When i=1, the algorithm picks all the courses that don't have any prerequisites and the optimal order can't pick more courses than the given algorithm as there are no more courses left that can be taken.

    Induction Hypothesis:\\
    P'[j] $\subseteq$ P[j] for all j $<=$ i-1

    Induction Step:\\
    for i, as P'[i-1] $\subseteq$ P[i-1], the courses that can be done in the ith semester (all prerequisites cleared) by our algorithm must be at least the same as the optimal algorithm. And as our algorithm picks all the eligible courses again, the optimal algorithm can't pick more courses than the given algorithm. Thus, P'[i] $\subseteq$ P[i].

    Therefore, the claim is proved, and the algorithm provides the optimal way to finish the courses in minimum no. of semesters.

    {\hfill\qedsymbol}

\newpage

\item Algorithm to compute the set of all those course pairs whose prerequisites and ancestors don't intersect.

\textbf{Algorithm:}

    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Set of no intersection}\label{alg:ms}
    \begin{algorithmic}[1]
    \Procedure{Non\_intersection}{Graph G}
    %\State $distance \gets$ array of size $|V|$
    \State $D \gets$ array of buckets where $D[i]$ is a bucket with nodes of $i$ indegree
    \State $Root$ $\gets$ boolean array for each node mapping that node to its ancestor with degree 0
    \State $Removed \gets$ the nodes removed from the graph(initially empty)
    \State $P \gets$ the required set (initially empty)
    \While{G $\neq$ EMPTY}
        \If{D[0] = EMPTY}
            \State \Return Error: No order possible
        \EndIf
        \For{$v \in D$ with $deg(v) = 0$}
            \State \textsc{RemoveVertex}($G,v$)
            \For{$t$ in Removed}
                \If{\textsc{Check(v,t)}}
                    \State P.add(v,t)
                    \State P.add(t,v)
                \EndIf
            \EndFor
            \State Removed.add(v)
        \EndFor

    \EndWhile
    \State \Return $P$

    \EndProcedure
    \algrule
    \Procedure{RemoveVertex}{$G,v$}\Comment{Reduces degrees of vertices connected to $v$}

    \State $D[deg(v)].\textsc{remove}(v)$
    \For{$j$ from $1$ to $deg(v)$}
    \State $u \gets adj(v)(j)$
    \If{$u$ is marked}
    \State \textbf{continue}
    \EndIf
    %\State Delete $v$ from $adj(u)$
    \State $deg(u) \gets deg(u)-1$
    \State $D[deg(u)+1].\textsc{remove}(u)$
    \State $D[deg(u)].\textsc{insert}(u)$
    \For{$i$ from $0$ to $size(Root(u))$}
        \If{Root(v)[i]}
        Root(u)[i] = True
        \EndIf
    \EndFor
    \EndFor
    \EndProcedure
    \algrule
    \Procedure{Check}{$v, u$}\Comment{Checks whether the 2 nodes don't have any common ancestors}
    \For{$i$ from $0$ to $size(Root(u))$}
        \If{Root(u)[i] and Root(y)[i]}
            \State \Return False
        \EndIf
    \EndFor
    \State \Return True
    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}

    \textbf{Runtime Analysis:}\\
    The subroutine \textsc{RemoveVertex} can take $O(n)$ time and the subroutine \textsc{Check} can also take $O(n)$ time for each vertex. The size of $Removed$ array can grow upto $O(n)$ and thus, for each vertex we may end up checking for all elements present in $Removed$ in $O(n^2)$ time.\\
    Thus, the total time complexity of the algorithm is $O(n^3)$. The space complexity can be $O(n^2)$ when all nodes are independent.

    \textbf{Correctness of Algorithm:}\\
    We can prove the correctness of the algorithm by contradiction by assuming that there exists a pair of vertices which is not selected by the algorithm.
    Suppose the pair is $(u,v)$ and at some stage of the algorithm, degree of $u$ is 0 (as ancestors of $u$ is finite). So, at this stage $u$ is added to the $Removed$ array. Consider the stage at which degree of $v$ becomes 0.\\ Without loss of generality, assume that $u$ is added to $Removed$ first compared to $v$. Thus, the procedure \textsc{Check} will be called using $(u,v)$. So, this pair will be checked and added to $P$ if there is no common ancestor between them. This is a contradiction as we assumed that the algorithm will not find $(u,v)$.

    {\hfill\qedsymbol}

\end{enumerate}
\newpage
\section{Forex Trading}
\begin{enumerate}[1.]
    \item Algorithm to verify whether or not there exists a cycle such that exchanging money over this cycle results in positive gain.

    \textbf{Observation:}

    A number $x$ is strictly larger than $1$ if and only if $log(1/x) > 0$.

    \begin{center}
        So, if we want ${R[i_1,i_2]R[i_2,i_3]...R[i_{k-1},i_k]R[i_k,i_1] > 1}$

        Then ${log(1/R[i_1,i_2]R[i_2,i_3]...R[i_{k-1},i_k]R[i_k,i_1]) < 0}$

        $\implies log(1/R[i_1,i_2]) + log(1/R[i_2,i_3]) + ..... + log(1/R[i_{k-1},i_k] + log(1/R[i_k,i_1]) < 0$

        $\implies R'[i_1,i_2] + R'[i_2,i_3] + ..... + R'[i_{k-1},i_k] + R'[i_k,i_1] < 0$
    \end{center}
    Since this problem is related to forex trading where it is suitable to assume that every currency is exchangeable with any other currency either directly or indirectly so it is assumed that the graph generated by the currency exchange is connected.  \\
    Thus, the problem can be reduced to finding a negative weight cycle in a (connected) graph where weight of edges is given by
    \begin{center}
        $R'[i_p,i_{p+1}] = log(1/R[i_p,i_{p+1}])$
    \end{center}
    A negative weight cycle can be detected easily in a (connected) graph using Bellman-Ford Algorithm.

    \textbf{Algorithm:}

    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Negative Cycle Detection Algorithm}\label{alg:dc}
    \begin{algorithmic}[1]

    \Procedure{NegativeCycleDetect}{Graph $G$, $S$}

    \State $distance \gets$ array of size $|V|$
    \For{$i=0$ to $m-1$} \Comment{Changing edge weights}
        \State $R'(e_i) \gets log(1/R(e_i))$
    \EndFor

    \For{each vertex $v$ in $G$}
    \State $distance[v] \gets \infty$
    \EndFor

    \State $distance[S] \gets 0$

    \For{$i=0$ to $n-1$}
        \For{each edge $(u,v)$ in $G$}
            \If{$distance[u]+R'[u,v] < distance[v]$}
            \State $distance[v] \gets distance[u]+R'[u,v]$
            \EndIf
        \EndFor
    \EndFor

    \For{each edge $(u,v)$ in $G$}
        \If{$distance[u]+R'[u,v] < distance[v]$}
        \State\Return True
        \EndIf
    \EndFor

    \State\Return False

    \EndProcedure

    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}

    \textbf{Runtime Analysis:}\\
    Edge weights are changed in $O(m)$ time. After changing the edge weights, the rest part of the algorithm is identical to the standard Bellman-Ford Algorithm which has time complexity $O(mn)$ and space complexity $O(n)$.\\
    Thus, the total time complexity is $O(mn)$ and space complexity is $O(n)$.

    \textbf{Correctness of Algorithm:}\\
    The conversion of edge weights is explained in the observation section above and this conversion leads to a standard problem of shortest paths- Bellman-Ford Algorithm. The correctness of Bellman-Ford Algorithm is discussed in the lectures of the course. Thus, by reducing the problem to another problem, the algorithm is designed to find the solution of the problem.

    \hfill\qedsymbol
    \newpage
 %-------------------------------------------------------------------------%
    \item Algorithm to print out such a cyclic sequence defined in part 1, if it exists.

    \textbf{Algorithm:}

    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Print Negative Cycle Algorithm}\label{alg:pfc}
    \begin{algorithmic}[1]
    \Procedure{PrintNegativeCycle}{Graph $G$, $S$}
    \State $distance \gets$ array of size $n$
    \State $parent \gets$ array of size $n$
    \For{$i=0$ to $m-1$} \Comment{Changing edge weights}
        \State $R'(e_i) \gets log(1/R(e_i))$
    \EndFor

    \For{each vertex $v$ in $G$}
    \State $distance[v] \gets \infty$
    \EndFor

    \State $distance[S] \gets 0$

    \For{$i=0$ to $n-1$}
        \For{each edge $(u,v)$ in $G$}
            \If{$distance[u]+R'[u,v] < distance[v]$}
            \State $distance[v] \gets distance[u]+R'[u,v]$
            \State $parent[v] \gets u$
            \EndIf
        \EndFor
    \EndFor
    \algrule
    \State $cycle \gets$ sequence of nodes containing a cycle

    \For{each edge $(u,v)$ in $G$}
        \If{$distance[u]+R'[u,v] < distance[v]$} \Comment{Cycle detected}
        \State $p \gets v$
        \For{$i = 0$ to $n-1$}
            \State $p \gets parent[p]$
        \EndFor

        \State Add $p$ to $cycle$
        \While{$i$ is not $p$}
            \State Add $i$ to $cycle$
            \State $i \gets parent[i]$
        \EndWhile

        \State \Return $cycle$
        \EndIf
    \EndFor

    \State\Return False

    \EndProcedure

    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}

    \textbf{Runtime Analysis:}\\
    The time complexity of this algorithm is same as the previous one because in this algorithm, we only add a $parent$ array to store the previous element of a node in the shortest path tree.\\
    Thus, the space complexity is $O(n)$ and the time complexity is $O(mn)$.

    \textbf{Correctness of Algorithm:}\\
    Printing negative cycle in a graph is a standard problem based on the Bellman-Ford algorithm. Similar to the previous algorithm, we stop when an update is possible in the $n^{th}$ iteration and using the $parent$ array, we backtrack to reach the starting point. The correctness of this algorithm is strongly related to the previous one which is based on Bellman-Ford algorithm and its correctness is discussed in the lectures.

    \hfill\qedsymbol
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{Coin Change}
\begin{enumerate}[1.]
    \item Algorithm to count the number of ways to make change for Rs. $n$,
    given an infinite amount of coins/notes of denominations $d[1],...,d[k]$.

    \textbf{Recurrence Relation:}

    Let $C(n,m)$ represent the number of ways to make change for Rs. $n$ using coins of denomination $d[1],...,d[m]$.

    The solution of $C(n,m)$ can be partitioned into two parts:
    \begin{itemize}
        \item Solution containing at least one coin of denomination $d[m]$. The subproblem here is to count number of ways to make change of Rs. $n-d[m]$ using $d[1],...,d[m]$ i.e. $C(n-d[m],m)$.
        \item Solution containing no coins of denomination $d[m]$. The subproblem here is to count number of ways to make change of Rs. $n$ using $d[1],...,d[m-1]$ i.e. $C(n,m-1)$.
    \end{itemize}
    Thus, the recurrence relation is formulated as:
    \begin{equation}
        C(n,m) = C(n,m-1) + C(n-d[m],m)
    \end{equation}
    with the base cases:
    \begin{itemize}
        \item $C(n,m) = 1$ when $n=0$ (No coin change)
        \item $C(n,m) = 0$ when $n<0$ (Negative money)
        \item $C(n,m) = 0$ when $n>0$ and $m\leq0$ (No coin left)
    \end{itemize}

    \textbf{Algorithm:}

    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Coin Change Algorithm}\label{alg:cc}
    \begin{algorithmic}[1]
    \Procedure{CoinChange}{$n$, set of coins $d[1],d[2],...,d[k]$}
    \State $count \to$ 2D array of size $(n+1) \times k$
    \For{$i=0$ to $n$}
    \For{$j=1$ to $k$}
    \If{$i=0$}
        $count(i,j) \gets 1$
    \ElsIf{$j=0$}
        \If{$i\mod d[j] = 0$} $count(i,j) \gets 1$
        \Else{}
        $count(i,j) \gets 0$
        \EndIf
    \ElsIf{$d[j]>i$} $count(i,j) \gets count(i,j-1)$
    \Else{} $count(i,j) \gets count(i,j-1)+count(i-d[j],j)$
    \EndIf
    \EndFor
    \EndFor
    \State \Return $count(n,k)$
    \EndProcedure
    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}

    \textbf{Runtime Analysis:}

    Like other dynamic programming problems, this algorithm fills the complete 2D array $count$ in a single pass. So, the time complexity as well as space complexity is $O(nk)$.

    \textbf{Correctness of Algorithm:} Proof by Induction on $i$

    \textit{Base Case:}\\
    There are three base cases:
    \begin{itemize}
        \item When no amount is left to make change. In this case, there is only 1 way to make change.
        \item When the amount is negative, there is no way to make change. Thus, $C(n,m) = 0$ is 0 in this case.
        \item When there is some amount left but no coins are left to make change. Thus, in this case, number of ways to make change is 0.
    \end{itemize}

    \textit{Induction Hypothesis:}\\ The algorithm gives the correct count of the number of ways to make change for all values of Rs. $p < i$ using coins of denominations $d[1], d[2],...,d[j]$ and number of ways to make change of Rs. $i$ using coins of denomination $d[1],d[2],...,d[q]$ for all $q<j$.

    \textit{Induction Step:}\\
    To calculate the number of ways to make change of Rs. $i$ using coins of denomination $d[1],d[2],...,d[j]$. We can either include the coin of denomination $d[j]$ or exclude it.\\
    By induction hypothesis, we have the number of ways to make change of Rs. $i$ using $d[1],d[2],...,d[j-1]$. We also have the number of ways to make change of Rs. $i-d[j]$ using coins of denomination $d[1],d[2],...,d[j]$.\\
    Thus, the total number of ways is calculated by using these two subproblems solutions.
    \hfill\qedsymbol

%----------------------------------------------------------------------%
    \newpage
    \item Algorithm to find a change of Rs. $n$ using the minimum number of coins.

    \textbf{Recurrence Relation:}

    Let $C(n)$ represent the minimum number of coins required to make change for Rs. $n$ using coins of denomination $d[1],...,d[m]$.

    $C(n)$ is minimum of the subproblems generated by using one coin of $d[j]$ denomination. The recurrence relation is formulated as:
    \begin{equation}
        C(n) = min(C(n) , 1+C(n-d[j]))~\forall j \in [1,m]
    \end{equation}
    with the base case:
    $C(n) = 0$ when $n=0$ (No coin change)

    \textbf{Algorithm:}

    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Min Coin Change Algorithm}\label{alg:mc}
    \begin{algorithmic}[1]
    \Procedure{MinCoinChange}{$n$, set of coins $d[1],d[2],...,d[k]$}
    \State $count \to$ array of size $n+1$
    \State $previous \to$ array of size $n+1$
    \State $count[0] = 0$
    \State $previous[0] = Null$
    \For{$i=1$ to $n$}
        \State $minimum \gets \infty$
        \State $minprevious \gets Null$
        \For{$j=1$ to $k$}
            \If{$i \geq d[j]$}
                \State $minimum \gets min(minimum,1+count[i-d[j]])$
                \State $minprevious \gets i-d[j]$
            \EndIf
        \EndFor
        \State $count[i] \gets minimum$
        \State $previous[i] \gets minprevious$
    \EndFor
    \State $change \to$ list of coins required
    \State $x \gets n$
    \While{$previous[x] \neq Null$}
        \State $change.append(x-previous[x])$
        \State $x \gets previous[x]$
    \EndWhile
    \State \Return $change$
    \EndProcedure
    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}

    \textbf{Runtime Analysis:}

    Like other dynamic programming problems, this algorithm fills the complete array $count$ in a single pass. There are two nested for loops which run $n$ and $k$ times respectively. So, the time complexity is $O(nk)$. The space complexity is $O(n)$ to store the $previous$ array.

    \textbf{Correctness of Algorithm:} Proof by Induction on $i$

    \textit{Base Case:} $i=0$\\ When $i=0$ the number of coins required to make change is zero. The algorithm is initialized with $count[i]=0$ when $i=0$. So, base case holds.

    \textit{Induction Hypothesis:}\\ The algorithm gives the correct count of the minimum number of coins required to make change for all values of Rs. $j < i$.

    \textit{Induction Step:}\\
    Consider the $i^{th}$ iteration of the outer for loop, the algorithm finds the minimum coins required to make change for Rs. $i$ by using a coin of denomination of $d[j]$ and breaking the problem into various subproblems.\\
    By induction hypothesis, the solution given by the algorithm of these subproblems is optimal and thus, we only need to add one coin of denomination $d[j]$ (which gives the minimum) to the coin sequence.

    \hfill\qedsymbol

\end{enumerate}
%------------------------------------------------

\end{document}


text:
\documentclass[../document.tex]{subfiles}

\begin{document}

\section*{Choice-of-lifecycle Model}
\addcontentsline{toc}{section}{Choice-of-lifecycle Model}
Our choice of lifecycle is the Agile model, or specifically the Scrum model as it is outlined below. In the report, the choice of lifecycle model will be included with the preliminary study.

\subsection*{The Scrum model}
\addcontentsline{toc}{subsection}{The Scrum model}
The Agile Manifesto and its twelve principles defines a new approach to software development that strongly contrasts with the previous Waterfall model. While the Waterfall model focuses on producing extensive documentation before implementation, an agile development process places the main focus on customer collaboration, presenting working software early, and responding to changes in the product requirements.

The Scrum model is a framework for software development that closely adheres to the Agile Manifesto. It is an incremental approach in that it develops the product through so-called sprints. A sprint is a phase of implementation that can last from 7 to 30 days. The input to each sprint is the product backlog, which is a list of all product requirements to be implemented ordered by priority. The sprint phase begins with a sprint meeting in which requirements are selected from the backlog to form a sprint backlog. The sprint backlog is the set of requirements that should be implemented during the sprint phase. During the sprint, the development team starts each day with a scrum meeting. Here, each team member presents what was done yesterday, what should be done today, and if there are any difficulties. The sprint ends with an end meeting in which the work progress is evaluated, and a demo of the new product increment is presented to the stakeholders.

In our initial project phase, we do not follow the Scrum model strictly. The initial phase is more concerned with documenting product requirements. This work would benefit from a close collaboration with the customer, making us choose our own agile model of work. In addition to having regular customer meetings, we opened up all our product documentation to the customer. The customer was prompted by email to review new versions of documents so that he could provide feedback outside meeting hours.

During the implementation phases, the Scrum model will be much more central. Here we will apply it to have a backlog, scrum meetings, and sprints.

\end{document}