%% This LaTeX-file was created by <jl> Tue Aug 14 23:26:14 2001
%% LyX 1.0 (C) 1995-1999 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass[english]{article}
\usepackage[T1]{fontenc}
\usepackage[auto]{inputenc}
\usepackage{babel}

\makeatletter


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

\makeatother

\begin{document}


\title{The Soundness of Function Approximation (under local improvement) \\
or \\
Finding the Gradient in the Space of all Policies}


\author{\date{}Sham Kakade John Langford}

\maketitle

\section{Motivation}

Gradient algorithms guarantee improvement but they do not guarantee that the
policy we find will have a high payoff. \emph{(This guarantee can be trivially
made by virtually all incremental RL learning algorithms via the addition of
a policy evaluation step.)} We seek to find an algorithm that can not only improve
but also find a policy with a large payoff. Further, we desire the algorithm
to be able to adapt it's improvement to the amount of data it receives.


\section{Introduction}

Function approximation has gotten a bad wrap due to the fact that theoretical
guarantees are weak and policy degradation has been empirically observed. This
has lead to the recent popularity of gradient methods, where direct optimization
of a parameterized policy is possible. However, the question of how to parameterize
a policy which can return a high payoff is obscured in gradient methods (though
improvement is guaranteed regardless of what parameterization is used). In value
function methods, crudely, the answer is evident: the values must accurately
approximate the true values to obtain a near optimal policy. We now will propose
a scheme of function approximation which is sound, and allows us to directly
address the question of how to find a near optimal policy.


\subsection{What is wrong with function approximation}

The standard theoretical guarantee of approximate value functions is for the
\( l_{\infty } \) error \( \varepsilon =\max _{s}|V(s)-\tilde{V}(s)| \) (where
\( \tilde{V}(s) \) is the approximate value function) then the greedy policy
based on these values has expected discounted reward \( \eta \geq \eta ^{*}-2\gamma \varepsilon /(1-\gamma ) \)
(where \( \eta ^{*} \) is the optimal possible). This is fairly weak and trivial
guarantee, since even for large gamma, a greedy update could generate a significantly
worse policy even with an \emph{accurate} approximation. This is essentially
due to the fact that a greedy policy could be significantly different from the
current policy and the error can be compounded \( 1/(1-\gamma ) \) times. \emph{(Sham,}
\emph{perhaps it would be better to talk about normalized quantities here to
make things clearer?)} Let us enumerate the most damning criticisms of function
approximation methods, which we must address (see Baxter's intro. for most of
these criticisms):

\begin{enumerate}
\item Pretty much all existing algorithms seek to minimize an error defined under
a different norm (usually \( l_{2} \)) which does not guarantee good performance
improvement.
\item Obviously if \( \varepsilon  \) is small enough then things are fine. However,
this 'small enough' value, under the \( l_{\infty } \) norm, is essentially
saying that \emph{}we have effectively done a table lookup policy.
\end{enumerate}
Further, just because we might be able to find a good policy under our approximation
scheme does not imply that there don't exist parameters which could give a good
greedy policy. The use of the \( l_{2} \) norm is not theoretically justified
and seems to be used with the hope that it might be possible to make significant
improvement with only a crude approximation (even though the \( l_{\infty } \)
norm will generally be very large). Using the \( l_{\infty } \) is also a very
costly demand. Although non-parametric models could allow arbitrarily good FA,
this is \emph{(could be)} very costly since after a policy improvement step
we have to repeat. \emph{(incoherent sentence)} It's not that we don't desire
a good approximation but the degree of fit necessary could be costly and infeasible
(since we are just going to change the policy anyways).


\subsection{What we desire}

A meaningful theoretical guarantee must tie using a practical metric, such as
the \( l_{2} \), to performance improvement. We now suggest such a method.
The key insight in obtaining such a guarantee is that the policy update steps
must be local (ie must only slightly change the current policy). The lack of
strong results for FA seem to stem from the fact that the policy update uses
the argmax operator (and thus could make drastic changes to the policy). Our
theoretical result will be more reasonable.

The first step we must take is to choose a local update rule to analyze, since
the greedy update rule underlies the lack of performance guarantees. 


\section{FA}

Let us now consider the case where have some approximate advantages \( \tilde{A} \)
(\( \tilde{A} \) denotes a vector in state-action space), or if we have found
some approximate state-action value \( \tilde{Q} \) then the approximate advantage
is \( \tilde{A}(s,a)=\tilde{Q}(s,a)-<\tilde{Q}(s,a^{\prime })>_{\pi (s,a^{\prime })} \).
Naively, we would like \( \tilde{A} \) to reflect the true advantages, \( A \),
for the policy to improve significantly. Let's now consider the local update
rule:
\begin{equation}
\label{fa_update}
\pi _{s}(a)\leftarrow \pi _{s}(a)\exp (\alpha \tilde{A}(s,a))
\end{equation}
Intuitively, we increase the chance of doing actions with high advantages the
fastest. Note that for an infinite \( \alpha  \) we end up with a greedy policy,
\emph{ie} one that would result from a greedy policy improvement step.

\textbf{(Side note:} This is exactly the simplest rule we were considering before
for policy improvement. Also, under the natural gradient, this is exactly what
the gradient update would give for small \( \alpha  \), where \( \tilde{A} \)
is the advantage fit from the compatible policy. In essence, a gradient method's
performance is tied to how good its compatible \( \tilde{A} \) is. Gradient
methods do not address how to choose a parameterized policy, which induces a
parameterized \( \tilde{A} \), that can give a good approximation of \( A \).)

Function approximation directly addresses the question of how to find a good
state-action value function \( \tilde{Q} \) or advantage \( \tilde{A} \).
However, the theoretical guarantees for function approximation are weak. \emph{(You
use ``clearly'' too often. Clarity should not need to be asserted.)} A line
search over \( \alpha  \) will guarantee a non-decrease in performance, and
an infinite \( \alpha  \) will return a policy that is equivalent to what greedy
policy improvement would return. However, the question we now seek to address
is how to fit \( \tilde{A} \) such that we get significant improvement. 

First, let us define the inner product for vectors in state-action space to
be:
\[
<x,x^{\prime }>_{\nu }=\sum _{sa}\nu (s,a)x(s,a)x^{\prime }(s,a)\]
 and we will define \( \nu (s,a)=\rho (s)\pi _{s}(a) \) (\emph{ie} the observed
\emph{(Observed, or real state action distribution?)} state-action distribution).
This leads to following result:

\begin{description}
\item [Theorem{*}]Let us consider the update rule  specified in equation \ref{fa_update}
for some \( \tilde{A} \) and some small \( \alpha  \). Let \( A \) be the
true advantages. Then the performance improvement we get is: 
\begin{equation}
\label{inner_prod}
\Delta \tilde{\eta }=\alpha <A,\tilde{A}>_{\nu }+O(\alpha ^{2})\, .
\end{equation}

\end{description}
\emph{Thus, to obtain improvement all we need is the much weaker result that
\( \tilde{A} \) must have a positive inner product with \( A \)} (as opposed
to strong and intractable conditions with the \( l_{\infty } \) norm).

\textbf{Proof} First, let us consider the table-lookup Gibbs distribution, \( \tilde{\Pi }_{G}=\{\pi _{\theta }:\pi (s,a)\propto \exp (\theta _{sa})\} \).
The exact gradient of the average reward (for any parameterized policy) is:
\begin{equation}
\label{av_gradient}
\nabla \eta ^{\pi }=\sum _{s,a}\rho ^{\pi }(s)\nabla \pi (s,a)Q^{\pi }(s,a).
\end{equation}
 

Let \( \delta _{ss^{'}} \) be the Kronecker delta which is \( 1 \) when \( s=s' \)
and \( 0 \) otherwise.

Using the notation \( \partial _{sa}\equiv \partial /\partial \theta _{sa} \),
it is straightforward to show for \( \tilde{\Pi }_{G} \), since \( \partial _{sa}\pi (s^{'},a^{'})=\delta _{ss^{\prime }}\pi (s,a)(\delta _{aa^{\prime }}-\pi (s,a^{\prime })) \):
\begin{eqnarray}
\partial _{sa}\eta ^{\pi } & = & \sum _{a}\rho (s)\pi (s,a)(\delta _{aa^{\prime }}-\pi (s,a^{\prime }))Q(s,a)\\
 & = & \rho ^{\pi }(s)\pi (s,a)(Q^{\pi }(s,a)-<\tilde{Q}(s,a^{\prime })>_{\pi (s,a^{\prime })})\label{partial_grad} \\
 & = & \rho ^{\pi }(s)\pi (s,a)A^{\pi }(s,a)
\end{eqnarray}
 . For some change \( \Delta \theta _{sa} \) to the parameters, the update
rule is:
\[
\pi _{s}(a,\theta _{t+1})\leftarrow \pi _{s}(a;\theta _{t})\exp (\Delta \theta _{sa})\]
, the resulting change to the performance is \( \Delta \eta =\sum _{sa}\partial _{sa}\eta \Delta \theta _{sa}=\sum _{sa}\rho (s)\pi _{s}(a)A(s,a)\Delta \theta _{sa} \)
(for small \( \Delta \theta  \)).

The update rule for the table-lookup Gibbs is exactly the same as that used
in equation \ref{fa_update}, so we evaluate the change to the performance 
\[
\Delta \eta =\sum _{sa}\rho (s)\pi _{s}(a)A(s,a)(\alpha \tilde{A}_{sa})=<A,\tilde{A}>_{\nu }\]
. \textbf{q.e.d.}


\section{Issues}

In essence, this method can be seen as trying to find the gradient over the
space of \emph{all} policies.

Neglecting the scale of \( \tilde{A} \) it is clear that the largest local
improvement is when \( \tilde{A} \) is aligned with \( A \). This is precisely
what the \( l_{2} \) norm is trying to fit (the \( l_{2} \) error is \( <A-\tilde{A},A-\tilde{A}>_{\nu } \)).
However, this scale is the real problem!!! Or put another way, what determines
the best direction? It is the one which can be followed the furthest in a line
search. We would like to find the \( \tilde{A} \) that allows the largest improvement
after a line search is done. However, trying to analyse this involves looking
at the curvature. Ack! I have been trying to do this with little success. Essentially
it is the \( O(\alpha ^{2}) \) term in equation \ref{inner_prod} that determines
what will be the best fit! As it stands, we want an infinite \( \tilde{A} \)
must be prevented.

Another way to look at the whole argument (perhaps simpler) is let us just start
with the set of parameterized policy \( \{\pi _{\theta }:\pi (s,a)\propto \exp (\theta _{sa})\} \).
The gradient is \( \partial _{sa}\eta =\rho (s)\pi (s,a)A(s,a) \). If we change
the parameters by \( \Delta \theta _{sa} \), then the resulting performance
change will be \( \Delta \eta =<A,\Delta \theta >_{\nu } \) (for small \( \Delta \theta  \)).
Now, if we constrain \( <\Delta \theta ,\Delta \theta >_{\nu } \) to be constant
(\( ie \) ignore the magnitude of this vector), then the \( l_{2} \) norm
is fine to use. However, this essentially boils down to the question of what
the best direction is (out of all of those that improve).


\section{Regardless}

The last argument essentially shows that we have a method to find the gradient
over the space of all policies (it's actually the natural gradient that we are
finding due to update rule of equation \ref{fa_update}). As with all gradient
methods, there is an issue as to how to actually find the precise direction
to travel in (which I don't have good answer). With non-parametric methods,
this method can try to find this gradient regardless of how much data is observed
(with more data giving a more accurate gradient). This is an interesting way
of looking at things, \emph{ie} that we are trying to generalize from the observed
data to find the gradient over the space of all policies. Thus we shouldn't
need to worry about local minima issues if asymptotically we collect more data
between gradient updates. I have not though about how to combine these ideas
with conjugate ideas (which could address this issue of which direction to do
a line search in).

Also, up till now I have assumed that the performance measure we are interested
in is the average reward. However, the stationary distribution seems to be the
wrong distribution and could get us trapped. A more uniform distribution is
necessary, but the results here still hold under a different distribution.

\end{document}
