\documentstyle[12pt,a4paper]{article}
%\documentclass[12pt,a4paper]{article}
%
% The following macros are used to generate nice code for programs.
% See example on how to use it below
%

%%%%%%%%%%%%%%%%%%%%% program macros %%%%%%%%%%%%%%%%%
% a blank line
\def\blankline{\hbox{}}
%
% The following macro is used to generate the header.
%


\newcommand{\topic}[2]{\section{#1} \index{#2} \markright{#1}}
\newcommand{\subtopic}[2]{\subsection{#1} \index{#2}}
\newcommand{\subsubtopic}[2]{\subsubsection{#1} \index{#2}}

%
% Convention for citations is first author's last name followed by other
% authors' last initials, followed by the year.  For example, to cite the
% seventh entry in the course bibliography, you would type: \cite{BurnsL80}
% (To avoid bibliography problems, for now we redefine the \cite command.)
%

\renewcommand{\cite}[1]{[#1]}

%
% These are just to make things a little easier:
%
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\blank}{\vspace{1ex}}   % generates a blank line in the output

%
% Use these for theorems, lemmas, proofs, etc.
%
%\newtheorem{theorem}{Theorem}[chapter]
%%%
\newtheorem{theorem}{Theorem}[section]
%%%
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\hfill $\Box$}
\newenvironment{proof}{\par{\noindent \bf Proof:}}{\qed \par}
%\newenvironment{proof}{{\em Proof:}}{\hfill\rule{2mm}{2mm}}

%
% Use the following for definitions.
% \bigdef is for definitions to be set off by themselves; \smalldef is for
% definitions given in the middle of a paragraph.
%
\newenvironment{dfn}{{\vspace*{1ex} \noindent \bf Definition }}{\vspace*{1ex}}
\newcommand{\bigdef}[2]{\index{#1}\begin{dfn} {\rm #2} \end{dfn}}
\newcommand{\smalldef}[1]{\index{#1} {\em #1}}


% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}

%\usepackage[xdvi]{color}
%\color {blue}


\begin{document}
%\project{}{1}{April 2000}{Yishay Mansour}{Adi Akavia}{}{}

% **** YOUR NOTES GO HERE ****************************************************
%\topic{Reinforcement Learning - Final Project}{}
\begin{titlepage}
\title{Reinforcement Learning - Final Project}
\author{Adi Akavia}
\maketitle
\end{titlepage}


\topic {Introduction} {} In this project I've studied the article:
\emph{"Finite-Sample Convergence Rates for Q-learning and Indirect
Algorithms", by Michael Kearns and Satinder Singh}. The article
discusses the amount of experience needed for achieving a policy
with a certain level of performance guarantee by the learning
algorithms: Phased-Q-Learning (which is a variant of the familiar
Q-Learning) and the indirect algorithm (both algorithms are
explained later on); and compares the behaviour of the direct
(Phased-Q-Learning) and indirect algorithms. The article presents
a theorem but does not prove it, so the heart of my project is
presenting a proof to the theorem.


\topic{Notations}{}
\begin{itemize}
  \item {M is an MDP}
  \item {S is the set of states in M }
  \item {A is the set of actions in M }
  \item {${R^a}_M(s)$ is the return of action $a$ from state $s$.
  ${R^a}_M(s)$ is assumed to be constant in the article
  (non-stochastic returns), but this causes no loss of generality,
  since instead of assuming the reward is constant, we can take its
  expectation.}
  \item {$P^{a}_{sj}$ is the probability of reaching state $j$ by
  performing action $a$ from state $s$.}
\end{itemize}


%%% The Parallel Sampling Model
\topic {The Parallel Sampling Model}{}

The $Parallel\ Sampling\ Model$ is a model of an \emph{ideal}
exploration policy, in the sense that every state-action pair is
sampled with the same frequency. We define a subroutine called
$PS(M)$ that simulates the Parallel Sampling Model as follows: a
\emph{single} call to $PS(M)$ returns, for \emph{every}
state-action pair $(s,a)$, a random next state $s'$ distributed
according to the transition distribution $P^{a}_{sj}$. Thus a
single call to $PS(M)$ is simulating $|S| \times |A|$ transitions
in the given $MDP$, and returns $|S| \times |A|$ next states.\\ Of
course often this model is only an ideal and not an applicable
procedure; the advantage of using such a model of perfect sampling
method is that it enables us to separate the analysis of the
\emph{learning algorithms} from the quality of the policy we can
sample. Using the analysis for the ideal exploration policy we can
also bound the learning rate of any given exploration policy that
visits every state-action pair infinitely often, by approximating
the procedure $PS(M)$ with taking enough samples of the
exploration function, such that with good probability every
state-action pair is visited.


%%% The Learning Algorithms
\topic {The Learning Algorithms} {}

The article refers to two learning algorithms:
\begin{itemize}
  \item A direct algorithm called \emph{Phased-Q-Learning}, and
  \item An indirect algorithm
\end{itemize}

\subtopic {Direct Algorithm - Phased-Q-Learning} {} The
Phased-Q-Learning algorithm is similar to the Q-Learning algorithm
we've encountered in class, only it works in phases. In each phase
the algorithm makes $m_D$ calls to $PS(M)$ (where $m_D$ is
determined later by the analysis). The algorithm uses the $m_D$
samples of every state-action pair collected by the $m_D$ calls to
$PS(M)$ to update the value function as follows:
\begin{eqnarray*}
  \forall s,a: \widehat{Q}_0(s,a) &=& \widehat{v}_0(s) = 0\\
  \widehat{Q}_{l+1}(s,a) &=& {R^a}_M(s) + \gamma \frac{1}{m_D}
  \sum_{k=1}^{m_D}\widehat{v}_l({j^l}_k)\\
  &&where\ {j^l}_1,...,{j^l}_{m_D}\ are\ the\ m_D\ next\ states\
  observed\ from\ (s,a)\\
  &&on\ the\ m_D\ calls\ to\ PS(M)\ during\ the\ l^{th} phase, and\\
  &&\widehat{v}_l(s) = \max_{a \in A} \set{ \widehat{Q}(s,a) }
\end{eqnarray*}
Note that the Phased-Q-Learning algorithm requires $l_D \times
m_D$ calls to $PS(M)$, where $l_D$ is the number of performed
phases.

\subtopic {Indirect Algorithm} {} The indirect algorithm works as
follows:
\begin{itemize}
  \item {First it makes $m_I$ calls to $PS(M)$ to obtain $m_I$ next
  states for each state-action pair. Here, again, $m_I$ is determined later by the
  analysis.}

  \item {The next step of the indirect algorithm is building an
  empirical model of the transition probabilities using the
  collected samples as follows:
  ${\widehat{P}^a}_{st} = \frac{\#(s { \rightarrow_a} t)}{m_I}$,
  note that ${\widehat{P}^a}_{st}$, the transition probabilities
  in the empirical model, is an \emph{estimate} to the transition
  probability from state $s$ to state $t$ by performing action
  $a$, in the given MDP $M$.}

  \item {The third stage is iterating the $Value-Iteration$ algorithm
  (i.e. $Q_{l+1}(s,a) = {R^a}_M(s) + \gamma \sum_{t \in S}{\widehat{P}^a}_{st}\widehat{v}_l(t)$ )
  on the model we've established in the second stage of
  the algorithm for $l_I$ iterations, and returns the achieved policy.}
\end{itemize}
Note that the indirect algorithm requires $m_I$ calls to $PS(M)$.

%%% The articles Theorem
\topic {The Main Theorem - Bound on the Number of Samples} {}
  The main theorem of the article bounds the number of calls to
  the subroutine $PS(M)$, required by the learning algorithms to
  ensure with probability of at least $1-\delta$ that the achieved
  policy is an $\varepsilon$-optimal policy. The bounds stated by
  the article are:
\begin{theorem}{Main Theorem}\\
  \begin{itemize}
    \item{For an appropriate choice of the parameters $m_D$ and $l_D$,
    the total number of calls to $PS(M)$ required by the Phased-Q-Learning
    algorithm in order to ensure that, with probability at least $1-\delta$,
    the expected return of the resulting policy will be within $\varepsilon$ of the optimal policy, is:
    \begin{equation}
      O( (\frac{1}{\varepsilon^2} \cdot \ln{\frac{1}{\varepsilon}}) \cdot (\ln{\frac{|S|}{\delta}}\ +
      \ \ln\ln{\frac{1}{\varepsilon}}) )
    \end{equation}
    }

    \item{For an appropriate choice of the parameters $m_I$ and $l_I$,
    the total number of calls to $PS(M)$ required by the indirect algorithm in order
    to ensure that, with probability at least $1-\delta$, the expected return
    of the resulting policy will be within $\varepsilon$ of the optimal policy, is
    \begin{equation}
      O( (\frac{1}{\varepsilon^2}) \cdot (\ln{\frac{|S|}{\delta}}\ +
      \ \ln\ln{\frac{1}{\varepsilon}}) )
    \end{equation}
    }
  \end{itemize}
\end{theorem}

\topic {My Results} {} The article presents no proof to its
theorem, so the core of my project is providing a proof to the
theorem. The results I've accomplished depend on $|A|$ (the size
of the actions-set), but under the assumption of a constant $|A|$,
the result are the same:

\begin{itemize}
  \item{For an appropriate choice of the parameters $m_D$ and $l_D$,
  the total number of calls to $PS(M)$ required by the Phased-Q-Learning
  algorithm in order to ensure that, with probability at least $1-\delta$,
  the expected return of the resulting policy will be within $\varepsilon$ of the optimal policy, is:
  \begin{equation}
    O( (\frac{1}{\varepsilon^2} \cdot \ln{\frac{1}{\varepsilon}}) \cdot
    (\ln{(\frac{|S|\cdot |A|}{\delta})} +  \ln\ln{\frac{1}{\varepsilon}}) )\\
  \end{equation}
  }

  \item{For an appropriate choice of the parameters $m_I$ and $l_I$,
  the total number of calls to $PS(M)$ required by the indirect algorithm in order
  to ensure that, with probability at least $1-\delta$, the expected return
  of the resulting policy will be within $\varepsilon$ of the optimal policy, is
  \begin{equation}
    O( \frac{1}{\varepsilon^2} \cdot
    (\ln{(\frac{|S|\cdot |A|}{\delta})} + \ln\ln\frac{1}{\varepsilon}) )
  \end{equation}
  }
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Proof for Phased Q-Learning
\topic {Proof for Phased Q-Learning} {}
%%%%begin change
\subtopic{Notations}{}
\begin{itemize}
  \item {$Q_l$: A $(state,action)$ value function defined by\\
        $Q_{l+1}(s,a) = {{R_M}^a}(s) + \gamma \sum_{t\in
        S}{P^a}_{st}v_l(t)$, where $v_l(t) = \max_{b\in A}{\set{Q_l(t,b)}}$.\\
        Note, this is the operation of the Value-Iteration algorithm }

  \item {$\widehat{Q}_l$: A $(state,action)$ value function defined by\\
        $\widehat{Q}_{l+1}(s,a) = {{R_M}^a}(s) + \gamma
        \frac{1}{m_D}\sum_{k=1}^{m_D}\widehat{v_l}(t_k)$, where
        $\widehat{v_l}(t_k) = \max_{b\in
        A}{\set{\widehat{Q_l}(t_k,b)}}$, and $t_k$ are the $m_D$ next states
        observed from $(s,a)$ on the $m_D$ calls to $PS(M)$. Note, this is
        the operation of the phased-Q-learning algorithm }

  \item {$Q^*$ denotes, as usually, the optimal value function.}
\end{itemize}

%%% Bounding by 2 sums
\subtopic{ Bounding $\norm { \widehat{Q}_{l_D} - Q^*}$ }{} After
$l_D$ iterations, the algorithm Phased-Q-Learning returns a policy
within $\varepsilon$ of the optimal policy, if
\begin{equation}
  \norm { \widehat{Q}_{l_D} - Q^*} \leq \varepsilon
\end{equation}
(due to the definition of $Q^*$).\\
By the triangle inequality:
\begin{equation}
  \norm { \widehat{Q}_l - Q^*} \leq \norm { \widehat{Q}_l - Q_l } + \norm { Q_l - Q^* }
\end{equation}

Let's bound each of this values separately:

\begin{claim}\label{Phased-Q-Learn Chernoff}
  \begin{equation}
    \forall (s,a)\in S\times A,\ 0\leq i\leq l_D\ \\
    \Pr( \norm{ \frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_i(x_k) - \sum_{j \in S} P^{a}_{sj}\widehat{v}_i(j)
    }\geq w ) \leq 2e^{-2{m_D}{w^2}}
  \end{equation}
\end{claim}
\begin{proof}
  Note that
  \begin{itemize}
    \item {$\sum_{j \in S} P^{a}_{sj} \widehat{v}_i(j)$ is the
    expectation for the $\widehat{v}$ value of the next samples received from
    $PS(M)$ for the pair $(s,a)$ (since the samples are taken from the distribution
    $P^{a}_{sj}$); i.e. $E[\frac{1}{m_D} \sum_{k=1}^{m_D}$ $\widehat{v}_i(x_k)] =
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_i(j)$ }
    %
    \item {$\widehat{v}_k$ is bounded (since the immediate return is bounded and $\gamma<1$)}
    %
    \item {The samples are independent and identically distributed.}
  \end{itemize}

  Therefore, from \emph{Chernoff Inequality} we receive that
  $\forall w>0$
  \begin{equation}
    \forall s\in S,\ a\in A,\ 0\leq i\leq l_D\ \\
    \Pr( \norm{ \frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_i(x_k) - \sum_{j \in S} P^{a}_{sj}\widehat{v}_i(j)
    }\geq w ) \leq 2e^{-2{m_D}{w^2}}
  \end{equation}
\end{proof}

%%% Bounding the first sum
\begin{claim}{Bounding $\norm{ \widehat{Q}_l - Q_l }$:}
%\subtopic{Bounding $\norm {\widehat{Q}_l-\widetilde{Q}_l}$}{}
  \begin{itemize}
    \item{$\norm{ \widehat{Q}_l - Q_l }
        \leq \max_{(s,a)\in S\times A,\ 0\leq i\leq l}
        \set{ \norm{\frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-i}(x_k) -
        \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-i}(j) } \cdot
        \sum_{i=1}^{l}\gamma^i }$}
    \item{$\Pr( \norm{ \widehat{Q}_l - Q_l } \geq w \cdot \sum_{i=1}^l{\gamma^i} )
        \leq l \cdot |S| \cdot |A| \cdot 2e^{-2{m_D}{w^2}}$}
  \end{itemize}
\end{claim}
\begin{proof}
  First by induction let's see that:
  \begin{equation}
    \norm{ \widehat{Q}_l - Q_l } \leq \max_{(s,a)\in S\times A,\ 0\leq i\leq l}
    \set{ \norm{\frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-i}(x_k) -
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-i}(j) } \cdot
    \sum_{i=1}^{l}\gamma^i }
  \end{equation}
  Induction's Base: For $l=0$ both sides of the equation are zero, and the
  inequality holds.\\
  Induction's Step: Assume the claim for $l-1$ and prove it for $l$:
  \begin{eqnarray*}
    \norm { \widehat{Q}_l - Q_l } &=&
    \max_{(s,a) \in S \times A} \norm { \widehat{Q}_l(s,a) - Q_l(s,a) }\\
    %
    &=& \max_{(s,a) \in S \times A} \norm {
    {{R_M}^a}(s) + \gamma \frac{1}{m_D} \sum_{k=1}^{m_D}\widehat{v}_{l-1}(x_k) -
    {R_M}^a (s) - \gamma \sum_{j \in S} P^{a}_{sj} v_{l-1}(j)
    }\\
    &&where\ x_1,\ ...,\ x_{m_D}\ are\ the\ m_D\ next\ states\ observed\ from\ (s,a)
    \\&&\ on\ the\ m_D\ calls\ to\ PS(M).\\
    %
    &=& \max_{(s,a) \in S \times A} \set{ \gamma \norm {
    \frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-1}(x_k) -
    \sum_{j \in S} P^{a}_{sj} v_{l-1}(j) } }\\
    %
    &&By\ triangle\ inequality:\\
    &\leq& \max_{(s,a) \in S \times A} \{
    \gamma \norm { \frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-1}(x_k) -
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-1}(j) } +\\
    &&\gamma \norm { \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-1}(j) -
    \sum_{j \in S} P^{a}_{sj} v_{l-1}(j) } \}\\
    %
    &\leq& \max_{(s,a) \in S \times A} \set{
    \gamma \norm { \frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-1}(x_k) -
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-1}(j) }} +\\
    &&\max_{(s,a) \in S \times A} \set{
    \gamma \norm{ \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-1}(j)  -
    \sum_{j \in S} P^{a}_{sj} v_{l-1}(j) }}\\
    %
    &&By\ triangle\ inequality:\\
    &\leq& \max_{(s,a) \in S \times A} \set{
    \gamma \norm { \frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-1}(x_k) -
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-1}(j) }} +\\
    &&\max_{(s,a) \in S \times A} \set{
    \gamma \sum_{j \in S} P^{a}_{sj}
    \norm{ \widehat{v}_{l-1}(j) - v_{l-1}(j) }}\\
    %
    &\leq& \max_{(s,a) \in S \times A} \set{
    \gamma \norm { \frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-1}(x_k) -
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-1}(j) }} +\\
    &&\max_{(s,a) \in S \times A} \set{
    \gamma \norm{ \widehat{v}_{l-1} - v_{l-1} } \cdot
    \sum_{j \in S} P^{a}_{sj} }\\
    %
    &=& \max_{(s,a) \in S \times A} \set{
    \gamma \norm { \frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-1}(x_k) -
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-1}(j) }} +\\
    &&\max_{(s,a) \in S \times A} \set{
    \gamma \norm{ \widehat{v}_{l-1} - v_{l-1} } \cdot 1 }\\
    %
    &&Note\ that:\\
    &&\norm{\widehat{v}_l - v_l}
    = \max_{s \in S} \norm{\widehat{v}_l(s) - v_l(s)}
    = \max_{s \in S} \norm{\max_{a \in A}{\widehat{Q}_l(s,a)} - \max_{a \in
    A}{Q_l(s,a)}}\\
    &&\leq \max_{s \in S} \max_{a \in A} \norm{ \widehat{Q}_l(s,a) - Q_l(s,a)
    }
    \leq \max_{(s,a) \in S\times A} \norm{ \widehat{Q}_l(s,a) - Q_l(s,a) }
    = \norm { \widehat{Q}_l - Q_l }\\
    &&Therefore:\\
    %
    &\leq&
    \max_{(s,a) \in S \times A} \set{
    \gamma \norm { \frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-1}(x_k) -
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-1}(j) }} +\\
    &&\max_{(s,a) \in S \times A} \set{
    \gamma \norm{ \widehat{Q}_{l-1} - Q_{l-1} }}\\
    %
    &&By\ induction's\ assumption:\\
    &\leq& \max_{(s,a) \in S \times A} \set{
    \gamma \norm { \frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-1}(x_k) -
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-1}(j) }} +\\
    &&\max_{(s,a) \in S \times A} \set{ \gamma ( \max_{(t,b)\in S\times A,\ 0\leq i\leq l-1}
    \set{ \norm{\frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-i}(y_k) -
    \sum_{j \in S} {P^b}_{tj} \widehat{v}_{l-i}(j) } \cdot
    \sum_{i=1}^{l-1}\gamma^i } )}\\
    &&where\ y_1,\ ...,\ y_{m_D}\ are\ the\ m_D\ next\ states\ observed\ from\ (t,b)\\
    &&on\ the\ m_D\ calls\ to\ PS(M).\\
    %
    &\leq& \max_{(s,a) \in S \times A,\ o\leq i\leq l} \set{
    \gamma \norm { \frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-i}(x_k) -
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-i}(j) }} +\\
    &&\max_{(s,a)\in S\times A,\ 0\leq i\leq l}
    \set{ \norm{\frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-i}(x_k) -
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-i}(j) } \cdot
    \sum_{i=2}^{l}\gamma^i } \\
    %
    &=& \max_{(s,a)\in S\times A,\ 0\leq i\leq l}
    \set{ \norm{\frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-i}(x_k) -
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-i}(j) } \cdot
    \sum_{i=1}^{l}\gamma^i } \\
  \end{eqnarray*}

  Now, after we've accomplished the bound for $\norm{\widehat{Q}_l -
  Q_l}$, let's show that:
  \begin{equation}
    \Pr( \norm{ \widehat{Q}_l - Q_l } \geq w \cdot \sum_{i=1}^l{\gamma^i} )
    \leq l \cdot |S| \cdot |A| \cdot 2e^{-2{m_D}{w^2}}
  \end{equation}
  \begin{eqnarray*}
    \lefteqn{ \Pr( \norm{ \widehat{Q}_l - Q_l } \geq w \cdot \sum_{i=1}^l{\gamma^i}
    ) }\\
    &&By\ the\ first\ bound:\\
    &\leq& \Pr( \max_{(s,a)\in S\times A,\ 0\leq i\leq l}
    \set{ \norm{\frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-i}(x_k) -
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-i}(j) } \cdot
    \sum_{i=1}^{l}\gamma^i } \geq w \cdot \sum_{i=1}^l{\gamma^i} )\\
    %
    &=& \Pr( \max_{(s,a)\in S\times A,\ 0\leq i\leq l}
    \set{ \norm{\frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-i}(x_k) -
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-i}(j) } } \geq w )\\
    %
    &=& \Pr( \exists {(s,a)\in S\times A,\ 0\leq i\leq l}\ s.t.\
    \norm{\frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-i}(x_k) -
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-i}(j) } \geq w )\\
    %
    &\leq& \sum_{(s,a)\in S\times A,\ 0\leq i\leq l}
    \Pr( \norm{\frac{1}{m_D} \sum_{k=1}^{m_D} \widehat{v}_{l-i}(x_k) -
    \sum_{j \in S} P^{a}_{sj} \widehat{v}_{l-i}(j) } \geq w )\\
    %
    &&By\ claim\ \ref{Phased-Q-Learn Chernoff}:\\
    %
    &\leq& \sum_{(s,a)\in S\times A,\ 0\leq i\leq l}
    2e^{-2{m_D}{w^2}}\\
    %
    &=& l \cdot |S| \cdot |A| \cdot 2e^{-2{m_D}{w^2}}
  \end{eqnarray*}
\end{proof}

%%% Bounding the second sum
\begin{claim}{Bounding $\norm {Q_l - Q^*}$:}
%\subtopic{Bounding $\norm {Q_l - Q^*}$ }{}
  \begin{equation}
    \norm {Q_l - Q^*} \leq \frac{\gamma^{l-1}}{1-\gamma} \norm{v_1 - v_0}
  \end{equation}
\end{claim}
\begin{proof}
  We saw in class that:
  \begin{equation}
    \forall l \norm { v_l - v^* }
    \leq \frac{\gamma^l}{1-\gamma} \norm{v_1 - v_0}
  \end{equation}
  so,
  \begin{eqnarray*}
    \norm {Q_l - Q^*} &=& \max_{(s,a) \in S\times A}\norm {Q_l(s,a) - Q^*(s,a)}\\
    &=& \max_{(s,a) \in S\times A}\norm { R_{M}^{a}(s) + \sum_{j \in S} P^{a}_{sj}v_{l-1}(s)
    - R_{M}^{a}(s) - \sum_{j \in S} P^{a}_{sj} v^*(s) }\\
    &\leq& \max_{(s,a) \in S\times A}\sum_{j \in S} P^{a}_{sj}
    \norm{v_{l-1}(s) - v^*(s)}\\
    &\leq&  \max_{a \in A}\sum_{j \in S} P^{a}_{sj} \norm{v_{l-1} -
    v^*}\\
    &\leq& \max_{a \in A}\sum_{j \in S} P^{a}_{sj}  \frac{\gamma^{l-1}}{1-\gamma} \norm{v_1 -
    v_0}\\
    &=& \frac{\gamma^{l-1}}{1-\gamma} \norm{v_1 - v_0} \max_{a \in A}\sum_{j \in S}
    P^{a}_{sj}\\
    &=& \frac{\gamma^{l-1}}{1-\gamma} \norm{v_1 - v_0}\\
  \end{eqnarray*}
  and the bound is received.
\end{proof}


%%% combining the 2 bounds
\subtopic{Putting It All Together}{}

We've received:
\begin{equation}
  \norm { \widehat{Q}_l - Q^*} \leq \norm { \widehat{Q}_l - Q_l } + \norm { Q_l - Q^* }
\end{equation}
where
\begin{itemize}
  \item
    For any $w>0$:
    $\Pr( \norm{\widehat{Q}_l - Q_l} \geq w \cdot \sum_{i=1}^l{\gamma^i} )
    \leq l \cdot |S| \cdot |A| \cdot 2e^{-2{m_D}{w^2}}$
  \item
    $\norm {Q_l - Q^*} \leq \frac{\gamma^{l-1}}{1-\gamma} \norm{v_1 -
    v_0}$
\end{itemize}

\emph{Hence we can sum up all of the above by:}
%%%The important result from all the above:
\emph{
\begin{eqnarray*}
  \lefteqn{ \Pr( \norm{\widehat{Q}_l - Q^*} \geq
  w \cdot \sum_{i=1}^l{\gamma^i} + \frac{\gamma^{l-1}}{1-\gamma} \norm{v_1 - v_0}
  ) }\\
  %
  &\leq& \Pr( \norm{\widehat{Q}_l - Q_l} + \norm{Q_l - Q^*} \geq
  w \cdot \sum_{i=1}^l{\gamma^i} + \frac{\gamma^{l-1}}{1-\gamma} \norm{v_1 - v_0} )\\
  %
  &\leq& \Pr( \norm{\widehat{Q}_l - Q_l} +  \frac{\gamma^{l-1}}{1-\gamma} \norm{v_1 - v_0} \geq
  w \cdot \sum_{i=1}^l{\gamma^i} + \frac{\gamma^{l-1}}{1-\gamma} \norm{v_1 - v_0} )\\
  %
  &\leq& \Pr( \norm{\widehat{Q}_l - Q_l} \geq w \cdot \sum_{i=1}^l{\gamma^i}
  )\\
  %
  &\leq& l \cdot |S| \cdot |A| \cdot 2e^{-2{m_D}{w^2}}\\
\end{eqnarray*}
}


%%%finding m_D l_d and the no. of calls to PS(M)
\subtopic{Finding the Constants $m_D$ and $l_D$}{}

For parameters $w,\ m_D\ and\ l_D$ s.t.:
\begin{enumerate}
  \item
    $\varepsilon = w \cdot \sum_{i=1}^{l_D}{\gamma^i} + \frac{\gamma^{l_D-1}}{1-\gamma} \norm{v_1 -
    v_0}$

  \item
    $\delta =  {l_D} \cdot |S| \cdot |A| \cdot 2e^{- 2 {m_D} {w^2}}$
\end{enumerate}
we get, by the above result, that with probability at least
$1-\delta$ we have reached an $\varepsilon-optimal$ policy i.e.:
$\Pr( \norm {\widehat{Q}_{l_D} - Q^*} < \varepsilon ) >
1-\delta$\\ So, let's find such parameters $w,\ m_D\ and\ l_D$.
Note that $m_D$ and $l_D$ must be natural numbers, but it suffices
to constrain them to a \emph{real} value, since taking an upper
value won't change the asymptotic complexity.

>From (1) we get:
\begin{eqnarray*}
  w &=& \frac{ \varepsilon - \frac{\gamma^{l_D-1}}{1-\gamma} \norm{v_1 -
  v_0} }{ \sum_{i=1}^{l_D}{\gamma^i} }\\
  &=& \frac{ \varepsilon - \frac{\gamma^{l_D-1}}{1-\gamma} \norm{v_1 -
  v_0} }{ \frac{\gamma-\gamma^{{l_D}+1}}{1-\gamma} }\\
  &=& \frac{ (1-\gamma) \cdot (\varepsilon - \frac{\gamma^{l_D-1}}{1-\gamma} \norm{v_1 -
  v_0}) }{ \gamma-\gamma^{{l_D}+1} }\\
  &=& \frac{ (1-\gamma)\varepsilon - (\gamma^{l_D-1}\norm{v_1- v_0}) }{ \gamma-\gamma^{{l_D}+1} }\\
\end{eqnarray*}
In order to use Chernoff, we must have $w>0$,
\begin{eqnarray*}
  w>0 &\Leftrightarrow& \frac{ (1-\gamma)\varepsilon - \gamma^{l_D-1}\norm{v_1- v_0})
  }{\gamma-\gamma^{{l_D}+1} }>0\\
  &\Leftrightarrow& (1-\gamma)\varepsilon - \gamma^{l_D-1}\norm{v_1-
  v_0}) > 0\ \ (\gamma-\gamma^{l_D}>0\ since\ 0<\gamma<1) \\
  &\Leftrightarrow& (1-\gamma)\varepsilon > \gamma^{l_D-1}\norm{v_1-
  v_0}\\
  &\Leftrightarrow& \frac{ (1-\gamma)\varepsilon }{ \norm{v_1-
  v_0} } > \gamma^{l_D-1}\\
  &\Leftrightarrow& \ln{(\frac{ (1-\gamma)\varepsilon }{ \norm{v_1-
  v_0} })} > {(l_D-1)} \cdot \ln\gamma\\
  &\Leftrightarrow& {l_D} > \frac{ \ln{(\frac{ (1-\gamma)\varepsilon }{ \norm{v_1-
  v_0} })} }{ \ln\gamma } + 1\  \   (since\ \ln\gamma<0)\\
  &\Leftrightarrow& {l_D} > log_{\gamma}{(\frac{ (1-\gamma)\varepsilon }{ \norm{v_1-
  v_0} })} + 1\\
\end{eqnarray*}

And we get the constraint:
\emph{
  \begin{equation}
    l_D > log_{\gamma}{(\frac{ (1-\gamma)\varepsilon }{ \norm{v_1-
    v_0} })} + 1\\
  \end{equation}
} This constraint is fulfilled by setting $l_D =
log_{\gamma}{(\frac{ (1-\gamma)\varepsilon }{ \norm{v_1-
  v_0} })} + f$, for \emph{any} $f>1$, and in particular,
for $f = log_{\gamma}{2}$ ($log_{\gamma}{2}>1$ since
$0<\gamma<1$), we get: \emph{
\begin{equation}\label{l_D}
    l_D = {\log_{\gamma}}{\frac{ (1-\gamma)\varepsilon }{ \norm{v_1-
    v_0} }} + \log_{\gamma}{2}
    = {\log_\gamma}{\frac{ 2(1-\gamma)\varepsilon }{ \norm{v_1-
    v_0} }}
  \end{equation}
}

>From (2) we get:
\begin{equation}
  \ln\delta = \ln{(l_D\cdot |S|\cdot |A|\cdot 2)} - 2 {m_D}
  {w^2}\ln{e} = \ln{(2 l_D |S|\cdot |A|)} - 2 {m_D}{w^2}
\end{equation}
Hence:
\begin{equation}
  m_D = \frac{ \ln{(2 l_D |S| \cdot |A|)} - \ln\delta } { 2{w^2} }
  = \frac{ \ln{(\frac{2 l_D |S| \cdot |A|}{\delta})} } { 2{w^2}
  }
\end{equation}

By substituting with the $w$ received from (1), we get:
\begin{eqnarray*}
  m_D &=& \frac{ \ln{(\frac{2 l_D |S| \cdot |A|}{\delta})} } { 2{w^2}
  }\\
  &=& \frac{ \ln{(\frac{2 l_D |S| \cdot |A|}{\delta})} }
  { 2{{( \frac{ (1-\gamma)\varepsilon - \gamma^{l_D-1}\norm{v_1- v_0}) }{
    \gamma-\gamma^{l_D+1} } )}^2} }\\
  %
  &=& \frac{ {(\gamma-\gamma^{l_D+1})}^2 \cdot \ln{(\frac{2 l_D |S| \cdot |A|}{\delta})} }
  { 2 {( (1-\gamma)\varepsilon - \gamma^{l_D-1}\norm{v_1- v_0} )}^2 }\\
  %
  && Substitution\ l_D\ with\ the\ value\ we've\ received\ in\ \ref{l_D}:\\
  %
  &=& \frac
  { {(\gamma-\gamma^{ {\log_\gamma}{(\frac{ 2(1-\gamma)\varepsilon }{ \norm{v_1-
    v_0} })}+1 })}^2 \cdot
    \ln {(\frac{2 {\log_\gamma}{(\frac{ 2(1-\gamma)\varepsilon }{ \norm{v_1-
    v_0} })} |S| \cdot |A|}{\delta})} }
  { 2 {( (1-\gamma)\varepsilon - \gamma^{ {\log_\gamma}{(\frac{ 2(1-\gamma)\varepsilon }{ \norm{v_1-
    v_0} })} -1 }\norm{v_1- v_0} )}^2 }\\
  %
  &&Note\ \gamma^{l_D} = \gamma^{{\log_\gamma}{(\frac{ 2(1-\gamma)\varepsilon }{ \norm{v_1-
    v_0} })}} = \frac{2(1-\gamma)\varepsilon}{\norm{v_1- v_0}
    }\\
  %
  &=& \frac{ {(\gamma - \gamma \cdot \frac{2(1-\gamma)\varepsilon}{\norm{v_1- v_0}})}^2
  \cdot \ln{(\frac{2 {\log_\gamma}{(\frac{ 2(1-\gamma)\varepsilon }{ \norm{v_1-
    v_0} })} |S| \cdot |A|}{\delta})} }
  { 2 {( (1-\gamma)\varepsilon - \gamma^{-1} \cdot
  \frac{2(1-\gamma)\varepsilon}{\norm{v_1- v_0}} \norm{v_1- v_0} )}^2 }\\
  %
  &=& \frac{ {(\gamma - \gamma \cdot \frac{2(1-\gamma)\varepsilon}{\norm{v_1- v_0}})}^2
  \cdot \ln{(\frac{2|S| \cdot |A| \cdot {\log_\gamma}{\frac{ 2(1-\gamma)\varepsilon }{ \norm{v_1-
    v_0} }} }{\delta})} }
  { 2 {((1-\gamma)\varepsilon - 2\gamma^{-1}(1-\gamma)\varepsilon)} }\\
  %
  &=& \gamma \cdot \frac{ {(1 - \frac{2(1-\gamma)\varepsilon}{\norm{v_1- v_0}})}^2
  \cdot \ln{(\frac{2|S| \cdot |A| \cdot {\log_\gamma}{(\frac{ 2(1-\gamma)\varepsilon }{ \norm{v_1-
    v_0} })} }{\delta})} }
  { 2 {(1-\gamma)}^2 \varepsilon^2 {(1-\gamma^{-1})}^2 }\\
  %
  &=& \gamma^3 \cdot \frac{ {(1 - \frac{2(1-\gamma)\varepsilon}{\norm{v_1- v_0}})}^2
  \cdot \ln{(\frac{2|S| \cdot |A| \cdot {\log_\gamma}{(\frac{ 2(1-\gamma)\varepsilon }{ \norm{v_1-
    v_0} })} }{\delta})} }
  { 2 {(1-\gamma)}^4 \varepsilon^2 }\\
\end{eqnarray*}

Now, let's bound the number of calls to $PS(M)$ i.e. let's bound
$m_D \times l_D$:
\begin{eqnarray*}
  l_D \times m_D
  &=& [{\log_\gamma}{(\frac{ 2(1-\gamma)\varepsilon }{ \norm{v_1-
    v_0} })}] \times
  [ \frac{ {\gamma^3 \cdot (1 - \frac{2(1-\gamma)\varepsilon}{\norm{v_1- v_0}})}^2
  \cdot \ln{(\frac{2|S| \cdot |A| \cdot {\log_\gamma}{(\frac{ 2(1-\gamma)\varepsilon }{ \norm{v_1-
    v_0} })} }{\delta})} }
  { 2 {(1-\gamma)}^4 \varepsilon^2 }] \\
  %
  &=& O( [{\log_\gamma}{\varepsilon}] \times
  [ \frac{ {(1 - \varepsilon)}^2
  \cdot \ln{(\frac{|S| \cdot |A| \cdot {\log_\gamma}\varepsilon }{ \delta })} }
  { \varepsilon^2 } ] )\\
  %
  &=& O( [\frac{\ln\varepsilon}{\ln\gamma}] \times
  [ \frac{ {(1 - \varepsilon)}^2 \cdot \ln{(\frac{|S| \cdot |A| \cdot \frac{\ln\varepsilon}{\ln\gamma} }{ \delta })} }
  { \varepsilon^2 } ] )\\
  %
  &&Since\ \ln\gamma<0:\\
  &=& O( [ \ln{\frac{1}{\varepsilon}} ] \times
  [ \frac{ {(1 - \varepsilon)}^2 \cdot \ln{(\frac{ |S| \cdot |A| \cdot \ln{\frac{1}{\varepsilon}} }{ \delta
  })} }{ \varepsilon^2 } ] )\\
  %
  &&w.l.g\ we\ can\ assume\ that\ \varepsilon<1,\ and\ hence:\\
  &=& O( [ \ln{\frac{1}{\varepsilon}} ] \times
  [ \frac{ \ln{(\frac{|S| \cdot |A| \cdot \ln{\frac{1}{\varepsilon}} }{ \delta })} }
  { \varepsilon^2 } ] )\\
  %
  &=& O( [ \ln{\frac{1}{\varepsilon}} ] \times
  [ \frac{1}{\varepsilon^2} \cdot
  ( \ln{(\frac{|S| \cdot |A|}{\delta})} +  \ln\ln{\frac{1}{\varepsilon}} ) ] )\\
  %
  &=& O( \frac{1}{\varepsilon^2} \cdot \ln{(\frac{|S|\cdot |A|}{\delta})} \cdot
  \ln{\frac{1}{\varepsilon}} +
  \frac{1}{\varepsilon^2} \cdot \ln{\frac{1}{\varepsilon}} \cdot \ln\ln{\frac{1}{\varepsilon}} )\\
\end{eqnarray*}

So the number of calls to $PS(M)$ that insures with probability at
least $1-\delta$ that the received policy in the
$Phased-Q-Learning$ algorithm is within $\varepsilon$ distance
from the optimal policy is $O( \frac{1}{\varepsilon^2} \cdot
\ln{\frac{|S|\cdot |A|}{\delta}} \cdot
  \ln{\frac{1}{\varepsilon}} +
  \frac{1}{\varepsilon^2} \cdot \ln{\frac{1}{\varepsilon}} \cdot \ln\ln{\frac{1}{\varepsilon}} )$ \\

\qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Proof for Indirect Algorithm
\topic {Proof for The Indirect Algorithm} {}

\subtopic{Notations}{}
\begin{itemize}
  \item {${\widehat{P}^a}_{sj}$ is the \emph{estimation} of the transition probability from states $s$ to $j$ by action
  $a$, calculated by the $Indirect Algorithm$: ${\widehat{P}^a}_{sj} =
  \frac{\#(s{\rightarrow_a}j)}{m_I}$. }

  \item {${Q_l}(s,a)$ is the value of state $s$ and action $a$
  received from $l$ iterations of the $VI$ algorithm, using the
  real transition probabilities ($P^{a}_{sj}$).}

  \item { ${\widehat{Q}_l}(s,a)$ is the value of state $s$ and action $a$
  received from $l$ iterations of the $VI$ algorithm, using the
  ${\widehat{P}^a}_{sj}$ estimation of the transition probabilities. }
\end{itemize}

\begin{claim}{}\label{claim_1}
  For any $w>0,\ (s,a)\in S\times A$
  \begin{equation}
    \Pr( \norm{\sum_{j\in S}{\widehat{P}^a}_{sj}v_k(j) -
    \sum_{j\in S}P^{a}_{sj}v_k(j)} \geq w )
    \leq 2e^{-2\cdot m_I\cdot w^2}
  \end{equation}
\end{claim}
\begin{proof}
  The samples are independent and identically distributed; they
  are bounded since the immediate return is bounded and
  $\gamma<1$; and:
  \begin{eqnarray*}
    E[\sum_{j\in S}{\widehat{P}^a}_{sj} \cdot v_k(j)]
    &=& \sum_{j\in S} E[{\widehat{P}^a}_{sj} \cdot v_k(j)]\\
    &=& \sum_{j\in S} E[\frac{\#(s{\rightarrow_a}j)}{m_I}] \cdot
    v_k(j)\\
    &=& \sum_{j\in S} P^{a}_{sj}\cdot v_k(j)\\
  \end{eqnarray*}
  therefore, by Chernoff-inequality, the claim holds:
  \begin{eqnarray*}
    \lefteqn{ \Pr( \norm{\sum_{j\in S}{\widehat{P}^a}_{sj} \cdot v_k(j) -
    \sum_{j\in S} P^{a}_{sj} \cdot v_k(j)} \geq w ) }\\
    &=& \Pr( \norm{\sum_{j\in S}{\widehat{P}^a}_{sj} \cdot v_k(j) -
    E[\sum_{j\in S}{\widehat{P}^a}_{sj} \cdot v_k(j)]} \geq w
    )
    \leq 2e^{-2\cdot m_I\cdot w^2}
  \end{eqnarray*}
\end{proof}

\begin{claim}{Bounding $\norm{ \widehat{v}_l - v_l }$:}\label{claim_2}
\begin{enumerate}
  \item
    $\norm{\widehat{v}_l - v_l} \leq \norm { \widehat{Q}_l - Q_l
    }$
  \item
    $\sum_{j \in S} {\widehat{P}^a}_{sj} = 1$
  \item
    $\norm{\widehat{v}_l - v_l}
    \leq \max_{s\in S,\ a\in A,\ 0\leq k\leq l}
    { \norm{ \sum_{j\in S}{\widehat{P}^a}_{sj}v_k(j)
    - \sum_{j\in S}P^{a}_{sj}v_k(j) } } \cdot
    \sum_{i=1}^l{\gamma^i}$
\end{enumerate}
\end{claim}

\begin{proof}
\begin{itemize}
  \item {
  First, let's see that $\norm{\widehat{v}_l - v_l} \leq \norm { \widehat{Q}_l - Q_l
  }$:
  \begin{eqnarray*}
    \norm{\widehat{v}_l - v_l}
    &=& \max_{s \in S} \norm{\widehat{v}_l(s) - v_l(s)}\\
    &=& \max_{s \in S} \norm{\max_{a \in A}{\widehat{Q}_l(s,a)} - \max_{a \in
    A}{Q_l(s,a)}}\\
    &\leq& \max_{s \in S} \max_{a \in A} \norm{ \widehat{Q}_l(s,a) - Q_l(s,a)
    }\\
    &\leq& \max_{(s,a) \in S\times A} \norm{ \widehat{Q}_l(s,a) - Q_l(s,a) }\\
    &=& \norm { \widehat{Q}_l - Q_l }\\
  \end{eqnarray*}
  }
%
  \item {
  Secondly, $\sum_{j \in S} {\widehat{P}^a}_{sj} = 1$, since:
  \begin{eqnarray*}
    \sum_{j \in S}{\widehat{P}^a}_{sj}
    &=& \sum_{j \in S}\frac{\#(s{\rightarrow_a}j)}{m_I}\\
    &=& \frac{1}{m_I} \sum_{j \in S}\#(s{\rightarrow_a}j)\\
    &=& \frac{1}{m_I} \cdot m_I\    \   (on\ \emph{each}\ sampling\ there's\ some\ returned\ state\ j)\\
    &=& 1\\
  \end{eqnarray*}
  }
%
  \item {
  Thirdly, let's prove the bound for $\norm{ \widehat{v}_l - v_l }$ by
  induction:\\
  For $l=0$, $\norm{\widehat{v}_0 - v_0} = 0$ and the bound
  holds.\\
  Let assume the bound holds for $l-1$, and prove it for $l$:
  \begin{eqnarray*}
    \norm{\widehat{v}_l - v_l}
    &\leq& \norm { \widehat{Q}_l - Q_l }\\
    %
    &=& \max_{(s,a) \in S\times A}\set{ \norm { {R_M}^a(s) + \gamma \sum_{j \in S}{
    {\widehat{P}^a}_{sj}\widehat{v}_{l-1}(j)} - {R_M}^a(s) - \gamma \sum_{j \in S}{
    P^{a}_{sj}v_{l-1}(j)} } }\\
    %
    &\leq& \max_{(s,a) \in S\times A} \{
    \gamma \norm{ \sum_{j \in S} {\widehat{P}^a}_{sj}\widehat{v}_{l-1}(j) -
    \sum_{j \in S} {\widehat{P}^a}_{sj}v_{l-1}(j) } +\\
    &&\gamma \norm{ \sum_{j \in S} {\widehat{P}^a}_{sj}v_{l-1}(j) -
    \sum_{j \in S} {P}^a_{sj}v_{l-1}(j) } \}\\
    %
    &\leq& \max_{(s,a) \in S\times A} \{
    \gamma \sum_{j \in S} {\widehat{P}^a}_{sj} \norm{\widehat{v}_{l-1}(j)
    - v_{l-1}(j)} +\\
    &&\gamma \norm{ \sum_{j \in S} {\widehat{P}^a}_{sj}v_{l-1}(j) -
    \sum_{j \in S} {P}^a_{sj}v_{l-1}(j) } \}\\
    %
    &\leq& \max_{(s,a) \in S\times A} \set{
    \gamma \sum_{j \in S} {\widehat{P}^a}_{sj} \norm{\widehat{v}_{l-1}
    - v_{l-1}} +
    \gamma \norm{ \sum_{j \in S} {\widehat{P}^a}_{sj}v_{l-1}(j) -
    \sum_{j \in S} {P}^a_{sj}v_{l-1}(j) } }\\
    %
    &\leq& \max_{(s,a) \in S\times A} \set{
    \gamma \norm{\widehat{v}_{l-1} - v_{l-1}} \sum_{j \in S} {\widehat{P}^a}_{sj} +
    \gamma \norm{ \sum_{j \in S} {\widehat{P}^a}_{sj}v_{l-1}(j) -
    \sum_{j \in S} {P}^a_{sj}v_{l-1}(j) } }\\
    %
    &=& \max_{(s,a) \in S\times A} \set{
    \gamma \norm{\widehat{v}_{l-1} - v_{l-1}} +
    \gamma \norm{ \sum_{j \in S} {\widehat{P}^a}_{sj}v_{l-1}(j) -
    \sum_{j \in S} {P}^a_{sj}v_{l-1}(j) } }\\
    %
    &&By\ induction's\ assumption:\\
    &\leq& \max_{(s,a) \in S\times A} \{
    \gamma
        \max_{(t, b)\in S\times A,\ 0\leq k\leq l} \set{
        { \norm{ \sum_{j\in S}{\widehat{P}^b}_{tj}v_k(j)
        - \sum_{j\in S}{P^b}_{tj}v_k(j) } } \cdot
        \sum_{i=1}^{l-1}{\gamma^i} } +\\
    && \gamma \norm{ \sum_{j \in S} {\widehat{P}^a}_{sj}v_{l-1}(j) -
        \sum_{j \in S} {P}^a_{sj}v_{l-1}(j)} \}\\
    %
    &\leq& \max_{(s,a) \in S\times A} \{
    \gamma
        \max_{(t, b)\in S\times A,\ 0\leq k\leq l} \set{
        { \norm{ \sum_{j\in S}{\widehat{P}^b}_{tj}v_k(j)
        - \sum_{j\in S}{P^b}_{tj}v_k(j) } } \cdot
        \sum_{i=1}^{l-1}{\gamma^i} } +\\
    &&\gamma
        \max_{(t, b)\in S\times A,\ 0\leq k\leq l-1} \set{
        { \norm{ \sum_{j \in S} {\widehat{P}^b}_{tj}v_k(j) -
        \sum_{j \in S} {P}^b_{tj}v_k(j) } }
        } \}\\
    %
    &=& \gamma \max_{(t, b)\in S\times A,\ 0\leq k\leq l}
    { \norm{ \sum_{j\in S}{\widehat{P}^b}_{tj}v_k(j)
    - \sum_{j\in S}{P^b}_{tj}v_k(j) } } \cdot
    \sum_{i=1}^{l-1}{\gamma^i} +\\
    &&\gamma \max_{(t, b)\in S\times A,\ 0\leq k\leq l-1}
    { \norm{ \sum_{j \in S} {\widehat{P}^b}_{tj}v_k(j) -
    \sum_{j \in S} {P}^b_{tj}v_k(j) } }\\
    %
    &=& \max_{(t, b)\in S\times A,\ 0\leq k\leq l}
    { \norm{ \sum_{j\in S}{\widehat{P}^b}_{tj}v_k(j)
    - \sum_{j\in S}{P^b}_{tj}v_k(j) } } \cdot
    \sum_{i=2}^l{\gamma^i} +\\
    &&\gamma \max_{(t, b)\in S\times A,\ 0\leq k\leq l}
    { \norm{ \sum_{j \in S} {\widehat{P}^b}_{tj}v_k(j) -
    \sum_{j \in S} {P}^b_{tj}v_k(j) } }\\
    %
    &\leq& \max_{(t, b)\in S\times A,\ 0\leq k\leq l}
    { \norm{ \sum_{j\in S}{\widehat{P}^b}_{tj}v_k(j)
    - \sum_{j\in S}{P^b}_{tj}v_k(j) } } \cdot
    \sum_{i=1}^l{\gamma^i}\\
  \end{eqnarray*}
  }
\end{itemize}
\end{proof}


\begin{claim}{}\label{claim_3}
  As a conclusion from claims \ref{claim_1} and \ref{claim_2}
  we get that for every $w>0$:
  \begin{equation}
    \Pr( \norm{\widehat{v}_l - v_l} \geq w ) \leq
    l\cdot |S|\cdot |A|\cdot 2e^{-2m_I({\frac{w(1-\gamma)}{\gamma(1-\gamma^l)}})^2}
  \end{equation}
\end{claim}
\begin{proof}
  \begin{eqnarray*}
    \lefteqn{ \Pr( \norm{\widehat{v}_l - v_l} \geq w )
    %
    \leq \Pr( \max_{(s, a)\in S\times A,\ 0\leq k\leq l}
    { \norm{ \sum_{j\in S}{\widehat{P}^a}_{sj}v_k(j)
    - \sum_{j\in S}P^{a}_{sj}v_k(j) } } \cdot
    \sum_{i=1}^l{\gamma^i}
    \geq w )}\\
    %
    &=& \Pr( \exists {(s, a)\in S\times A,\ 0\leq k\leq l}
    { \norm{ \sum_{j\in S}{\widehat{P}^a}_{sj}v_k(j)
    - \sum_{j\in S}P^{a}_{sj}v_k(j) } } \cdot
    \sum_{i=1}^l{\gamma^i}
    \geq w )\\
    %
    &\leq& \sum_{(s, a)\in S\times A,\ 0\leq k\leq l}
    \Pr( \norm{ \sum_{j\in S}{\widehat{P}^a}_{sj}v_k(j)
    - \sum_{j\in S}P^{a}_{sj}v_k(j) } \cdot
    \sum_{i=1}^l{\gamma^i}
    \geq w )\\
    %
    &=& \sum_{(s, a)\in S\times A,\ 0\leq k\leq l}
    \Pr( \norm{ \sum_{j\in S}{\widehat{P}^a}_{sj}v_k(j)
    - \sum_{j\in S}P^{a}_{sj}v_k(j) }
    \geq \frac{w}{\sum_{i=1}^l{\gamma^i}} )\\
    %
    &&By\ \ref{claim_1}:\\
    &\leq& \sum_{(s, a)\in S\times A,\ 0\leq k\leq l}
    2e^{-2\cdot m_I\cdot({\frac{w}{\sum_{i=1}^l{\gamma^i}}})^2}\\
    %
    &=& l\cdot |S|\cdot |A|\cdot 2e^{-2\cdot m_I\cdot
    ({\frac{w}{\frac{\gamma-\gamma^{l+1}}{1-\gamma}}})^2}\\
    %
    &=& l\cdot |S|\cdot |A|\cdot 2e^{-2\cdot m_I\cdot
    ({\frac{(1-\gamma)w}{\gamma(1-\gamma^l)}})^2}\\
  \end{eqnarray*}
\end{proof}

\begin{claim}{}\label{claim_4}
  As we've seen in class:
  \begin{equation}
    \norm{v_l - v^*} \leq \frac{\gamma^l}{1-\gamma}
  \end{equation}
\end{claim}

\begin{claim}{}
  For every $l > \frac{\ln{\varepsilon(1-\gamma)}}{\ln\gamma}$,
  \begin{equation}
    \Pr( \norm{\widehat{v}_l-v^*} \geq \varepsilon ) \leq
    l\cdot\ |S|\cdot |A|\cdot
    2e^{-2\cdot m_I\cdot {(\frac{(1-\gamma)(\varepsilon
    \frac{\gamma^l}{1-\gamma})}{\gamma(1-\gamma^l)})}^2}
  \end{equation}
\end{claim}
\begin{proof}
  \begin{eqnarray*}
    \Pr( \norm{\widehat{v}_l-v^*} \geq \varepsilon)
    &\leq& \Pr( \norm{\widehat{v}_l - v_l} + \norm{v_l - v^*} \geq
    \varepsilon)\\
    &\leq& \Pr( \norm{\widehat{v}_l - v_l} +  \frac{\gamma^l}{1-\gamma} \geq
    \varepsilon)\\
    &=& \Pr( \norm{\widehat{v}_l - v_l} \geq \varepsilon - \frac{\gamma^l}{1-\gamma}
    )\\
    &&as\ long\ as:\ \varepsilon - \frac{\gamma^l}{1-\gamma} > 0:\\
    &\leq& l\cdot\ |S|\cdot |A|\cdot
    2e^{-2\cdot m_I\cdot {(\frac{(1-\gamma)(\varepsilon -
    \frac{\gamma^l}{1-\gamma})}{\gamma(1-\gamma^l)})}^2}\\
  \end{eqnarray*}

  Let's see when does $\varepsilon - \frac{\gamma^l}{1-\gamma} >
  0$:
  \begin{eqnarray*}
    \varepsilon - \frac{\gamma^l}{1-\gamma} > 0
    &\Leftrightarrow& \varepsilon \cdot{(1-\gamma)} > \gamma^l\\
    &\Leftrightarrow& \ln{( \varepsilon \cdot{(1-\gamma)} )} > l
    \cdot\ln{\gamma}\\
    &\Leftrightarrow& l > \frac {\ln{( \varepsilon \cdot{(1-\gamma)}
    )}}{\ln\gamma}\\
    &&(Since\ \ln\gamma < 1\ due\ to\ the\ fact\ that\ 0<\gamma<1)
  \end{eqnarray*}
  And this is the claim's assumption, so the proof is complete.
\end{proof}


\subtopic{Bounding the Number of Calls to $PS(M)$}{}

We've seen: \\ For every
$l_I>\frac{\ln{\varepsilon(1-\gamma)}}{\ln\gamma}$,
\begin{equation}
  \Pr( \norm{\widehat{v}_{l_I}-v^*} \geq \varepsilon) \leq
  l_I\cdot\ |S|\cdot |A|\cdot
  2e^{-2\cdot m_I\cdot {\frac{(1-\gamma)(\varepsilon -
  \frac{\gamma^{l_I}}{1-\gamma})}{\gamma(1-\gamma^{l_I})}}^2}
\end{equation}

Let's find $m_I$ and $l_I$ such that
\begin{equation}
  \Pr( \norm{\widehat{v}_{l_I}-v^*} \geq \varepsilon) \leq \delta
\end{equation}
By the previous claims, it suffices to find $m_I$ and $l_I$ s.t.:
\begin{enumerate}
  \item $l_I > \frac{\ln{(\varepsilon(1-\gamma))}}{\ln\gamma}$

  \item $\delta = l_I\cdot\ |S|\cdot |A|\cdot 2e^{-2\cdot m_I\cdot
  ({\frac{ (1-\gamma) (\varepsilon - \frac{\gamma^{l_I}}{1-\gamma}) }
  { \gamma (1-\gamma^{l_I}) } })^2}$
\end{enumerate}

Note that $log_{\gamma}{2} > 0$ (since $0<\gamma<1$). Then we can
set (taking upper value if necessary):
\begin{eqnarray*}\label{l_I}
  l_I &=& \frac{\ln{(\varepsilon(1-\gamma))}}{\ln\gamma} +
  {log_\gamma}{2}\\
  &=& \log_{\gamma}{(\varepsilon(1-\gamma))} +
  log_{\gamma}{2}\\
  &=& \log_\gamma(2\varepsilon(1-\gamma))
\end{eqnarray*}

The number of calls to $PS(M)$ is $m_I$:
\begin{eqnarray*}
  &&From\ the\ second\ constraint\ we\ get:\\
  m_I &=& (\ln{(2\cdot {l_I}\cdot |S|\cdot |A|)} - \ln\delta) \cdot
  \frac{ \gamma^2 {(1-\gamma^{l_I})}^2 }
  { 2 {(1-\gamma)}^2 {(\varepsilon - \frac{\gamma^{l_I}}{1-\gamma})}^2 }\\
  %
  &=& (\ln{(2\cdot \log_{\gamma}{(2\varepsilon(1-\gamma))}
  \cdot |S|\cdot |A|)} - \ln\delta) \cdot
  \frac{ \gamma^2 {(1-\gamma^{l_I})}^2 }
  { 2 {(1-\gamma)}^2 {(\varepsilon - \frac{\gamma^{l_I}}{1-\gamma})}^2 }\\
  %
  &=& \ln{(\frac{2\cdot \log_{\gamma}{(2\varepsilon(1-\gamma))}
  \cdot |S|\cdot |A|}{\delta})} \cdot
  \frac{ \gamma^2 }{ 2{(1-\gamma)}^2 } \cdot
  {(\frac{ 1-\gamma^{l_I} }{ \varepsilon - \frac{\gamma^{l_I}}{1-\gamma}
  })}^2\\
  %
  &&By\ substituting\ l_I\ with\ the\ expression\ we've\ received\ for\ l_I:\\
  &=& \ln{(\frac{2\cdot \log_{\gamma}{(2\varepsilon(1-\gamma))}
  \cdot |S|\cdot |A|}{\delta})} \cdot
  \frac{ \gamma^2 }{ 2{(1-\gamma)}^2 } \cdot
  {(\frac{ 1-\gamma^{\log_\gamma(2\varepsilon(1-\gamma))} }
  { \varepsilon - \frac{\gamma^{\log_\gamma(2\varepsilon(1-\gamma))}}{1-\gamma}
  })}^2\\
  %
  &=& \ln{(\frac{2\cdot \log_{\gamma}{(2\varepsilon(1-\gamma))}
  \cdot |S|\cdot |A|}{\delta})} \cdot
  \frac{ \gamma^2 }{ 2{(1-\gamma)}^2 } \cdot
  \frac{ {(1-(2\varepsilon(1-\gamma)))}^2 }
  { {(\varepsilon - \frac{(2\varepsilon(1-\gamma))}{1-\gamma})}^2
  }\\
  %
  &=& \ln{(\frac{2\cdot \log_{\gamma}{(2\varepsilon(1-\gamma))}
  \cdot |S|\cdot |A|}{\delta})} \cdot
  \frac{ \gamma^2 }{ 2{(1-\gamma)}^2 } \cdot
  \frac{ {(1-(2\varepsilon(1-\gamma)))}^2 }
  { \varepsilon^2 {(1 - \frac{(2(1-\gamma))}{1-\gamma})}^2 }\\
  %
  &=& \ln{(\frac{2\cdot \log_{\gamma}{(2\varepsilon(1-\gamma))}
  \cdot |S|\cdot |A|}{\delta})} \cdot
  \frac{ \gamma^2 }{ 2{(1-\gamma)}^2 } \cdot
  \frac{ {(1-(2\varepsilon(1-\gamma)))}^2 }
  { \varepsilon^2 {(1 - 2)}^2 }\\
  %
  &=& \ln{(\frac{2\cdot \log_{\gamma}{(2\varepsilon(1-\gamma))}
  \cdot |S|\cdot |A|}{\delta})} \cdot
  \frac{ \gamma^2 }{ 2{(1-\gamma)}^2 } \cdot
  \frac{ {(1-(2\varepsilon(1-\gamma)))}^2 }{ \varepsilon^2 }\\
%
  &=& O( (\ln{\frac{\log_{\gamma}{\varepsilon}
  \cdot |S|\cdot |A|}{\delta}}) \cdot (\frac{1}{\varepsilon^2}) \cdot {(1-2\varepsilon(1-\gamma))}^2 )\\
%
  &&Since\ we're\ interested\ in\ asymptotic\ measure\ (as\ \varepsilon\ and\ \delta\ go\ to\ zero),\\
  &&we\ can\ assume\ that\ \varepsilon<2(1-\gamma)\ (because\ it's\ true\ for\ \varepsilon\ small\ enough),\\
  &&therefore:\\
  &=& O( (\ln{\frac{\log_{\gamma}{\varepsilon}
  \cdot |S|\cdot |A|}{\delta}}) \cdot (\frac{1}{\varepsilon^2}) )\\
  %
  &&Since\ \ln\gamma<0,\ we\ have:\ log_\gamma\varepsilon = \frac{\ln\varepsilon}{\ln\gamma}
  = O(\ln\frac{1}{\varepsilon}),\ therefore:\\
  %
  &=& O( \ln{(\frac{\ln\frac{1}{\varepsilon}\cdot |S|\cdot |A|}{\delta})}
  \cdot (\frac{1}{\varepsilon^2}) )\\
  %
  &=& O( (\ln{(\frac{|S|\cdot |A|}{\delta})} +
  \ln\ln\frac{1}{\varepsilon})
  \cdot (\frac{1}{\varepsilon^2}) )\\
  %
  &=& O( \frac{1}{\varepsilon^2} \cdot \ln{(\frac{|S|\cdot |A|}{\delta})} +
  \frac{1}{\varepsilon^2} \cdot \ln\ln\frac{1}{\varepsilon} )
\end{eqnarray*}
Here, again, $m_I$ and $l_I$ must be natural numbers, but taking
their upper value won't change the asymptotic complexity, so, the
number of calls to $PS(M)$ by the indirect algorithm is:\\
$O(\frac{1}{\varepsilon^2} \cdot \ln{(\frac{|S|\cdot
|A|}{\delta})} + \frac{1}{\varepsilon^2} \cdot
\ln\ln\frac{1}{\varepsilon} )$\\


%%%
\topic {Conclusions}{} We saw that both Phased-Q-Learning and the
indirect algorithm enjoy a rather rapid convergence to the optimal
policy as a function of the number of observed transitions. Both
have roughly the same sampling complexity, with a slight advantage
to the indirect algorithm. This advantage is rather surprising
since this sampling complexity is not enough to enable the
\emph{construction} of a good model of the given MDP.

\end{document}