%% This LaTeX-file was created by <jl> Sun Oct 21 19:17:49 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]{amsart}
\usepackage[T1]{fontenc}
\usepackage[auto]{inputenc}
\usepackage{babel}
\usepackage{graphics}

\makeatletter


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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\theoremstyle{plain}    
\newtheorem{thm}{Theorem}[section]
\numberwithin{equation}{section} %% Comment out for sequentially-numbered
\numberwithin{figure}{section} %% Comment out for sequentially-numbered
\theoremstyle{plain}    
\newtheorem{cor}[thm]{Corollary} %%Delete [thm] to re-start numbering

\makeatother

\begin{document}


\title{Incremental Reinforcement Learning}

\begin{abstract}
Gradient methods fundamentally intertwine exploration and exploitation. For
these techniques, determining if any gradient direction (in policy space) will
improve the performance of the current policy can be arbitrarily difficult.
To overcome these difficulties, an alternative performance measure which does
not suffer from variance convergence problems is proposed and analyzed. Properly
optimizing this alternative performance measure requires nonparametric techniques
and can be done in a way that never noticeably decreases the average reward. 
\end{abstract}
\maketitle

\section{Introduction}

In recent years, there has been a growing interest in direct policy-gradient
methods for approximate planning in large Markov decision problems (MDP). Direct
policy-gradient methods seek to find a good policy \( \pi  \) among some restricted
class of policies, by following the gradient of the future reward. Gradient
methods are essentially on-policy and so intertwine the fundamental exploration-exploitation
tradeoff. We argue that this entanglement could lead to highly inefficient policy
improvement and suggest how to incorporate exploration into these methods.

Earlier work has argued that undirected policies could lead to exponentially
inefficient learning \cite{whitehead91complexity}. For example, consider the
simple MDP shown in Figure \ref{fig1}A (adapted from \cite{thrun92efficient}).
Under a policy that gives equal probability to all actions, the expected time
to the goal from the left most state is \( 3(2^{n}-n-1) \), and with \( n=50 \),
the expected time to the goal is about \( 10^{15} \). Any gradient method initialized
to this policy would have to run at least this long to obtain just one accurate
estimate. The inherent problem is that in gradient methods, policy improvement
at a state is tied to the current probability of visiting that state. Importance
sampling methods have been formulated \cite{meuleau01exploration, sutton-off-policy}
but these cannot salvage the situation when there is an exponentially low probability
event with a significant contribution to the expectation of interest. 

In value function methods, this problem is seen as a lack of exploration. Active
exploration is necessary to improve the policy at states that are not visited
often in order to efficiently propagate rarely visited state value information
to commonly visited states (see \cite{kearns98nearoptimal, thrun92efficient}).
Dynamic programming also improves the policy at all states: unlikely states
will exhibit policy improvement even though this improvement might have little
impact on the average reward.

\begin{figure}
\resizebox*{0.5\textwidth}{!}{\includegraphics{figs/thrun_game.eps}} 


\caption{\label{fig1}Example 1: Two actions move agent to the left and one actions
moves agent to the right.}
\end{figure}
 

The average reward is what we ultimately seek to maximize. However, this performance
measure has the fundamental problem: it is insensitive to performance improvement
at highly unlikely states. Improvement at these states can lead to drastic policy
improvement (as in figure \ref{fig1}). We formalize this by showing that it
can be very difficult to improve a policy which has significantly sub-optimal
performance. What is meant by difficult is that estimating gradient \emph{direction}
(in policy space) when the gradient \emph{magnitude} is small can be exponentially
difficult (in the number of states). Although being close to the optima implies
the gradient has a small magnitude, a small magnitude does \emph{not} imply
being close to optima. The crucial problem is that the magnitude of the gradient
can be small at plateaus far away from the optima. 

\begin{itemize}
\item In section 2, the usual definition of the reinforcement learning problem is
stated.
\item In section 3, the problems with gradient methods are exhibited in more detail. 
\item In section 4, we discuss general incremental policy improvement. 
\item In section 6, an alternative performance measure is proposed which is sensitive
to performance improvement at unlikely states (unlike the average reward). This
alternative can in principle be improved with far fewer samples than the standard
performance measure. 
\item In section 8, we discuss why richer function approximation schemes (such as
non-parametric schemes) are necessary.
\end{itemize}

\section{Preliminaries}

First, let us state the standard formulation of a reinforcement learning problem.
A reinforcement learning problem is a finite Markov decision process (MDP) with
rewards which is a tuple \( (S,\mu ,A,R,P) \) where: \( S \) is finite set
of states, \( \mu  \) is the starting state distribution, \( A \) is a finite
set of actions, \( R \) is a reward function \( R:S\times A\rightarrow [0,R_{max}] \),
and \( P \) is the transition model in which \( p_{ij}^{a} \) is the transition
probability from state i to j under action \( a \). We only consider the more
difficult case where the goal of the agent is to find a policy that maximizes
the average reward. The agent's decision making procedure is characterized by
a stochastic policy \( \pi (a|s) \), which is the probability of taking action
\( a \) in state \( s. \) We make the assumption that \emph{every policy \( \pi  \)
is ergodic, ie} has a well-defined stationary state visitation frequency \emph{\( d_{\pi } \)}. 

Under this assumption, the \emph{average reward} is \( \sum _{s,a}d_{\pi }(s)\pi (a|s)R(s,a) \).
Although in many situations, the goal of the agent is to maximize the average
reward, we only consider the case of maximizing the \( \gamma  \) discounted
average reward. This approximation allows us to avoid mathematical difficulties
while arriving at a similar solution for processes that ``restart'' on a reasonable
timescale \cite{Sham_colt}.

We define the state-action value as 
\begin{equation}
\label{eq-Q}
Q_{\pi }(s,a)\equiv E_{\pi }\{(1-\gamma )\sum ^{\infty }_{t=0}\gamma ^{t}R(s_{t},a_{t})|s_{0}=s,a_{0}=a\}
\end{equation}
 and the value function as 
\begin{equation}
\label{eq-value}
J_{\pi }(s)\equiv E_{\pi (a^{\prime }|s)}\{Q_{\pi }(s,a^{\prime })\}
\end{equation}
, where and \( s_{t} \) and \( a_{t} \) are the state and action at time \( t \).
Thus, the goal of the agent is to maximize the discounted average reward:
\[
\eta (\pi )=E_{\mu }\{J_{\pi }(s)\}\, .\]
One last definition is required. The advantage is defined by: 
\begin{equation}
\label{eq-advantage}
A_{\pi }(s,a)\equiv Q_{\pi }(s,a)-J_{\pi }(s)\, .
\end{equation}
We will sometimes suppress the \( \pi  \) subscript when the policy is clear
from context. 


\section{What is Wrong with Policy Gradients?}

Let us consider the family of problems shown in figure \ref{fig1} where an
agent needs to reach some goal state. Policy gradient techniques will perform
very poorly on these problems. 

\begin{thm}
\label{th-inefficient}(Policy gradient is inefficient) There exist reinforcement
learning problems with \( n=|S| \) states which require an expected \( \Omega (2^{n}) \)
state transitions in order to accurately estimate the gradient direction. 
\end{thm}
\begin{proof}
Consider the family of \( n \) state problems given in example \ref{fig1}
with table lookup policy placing equal probability on every action. The stationary
distribution under this policy will satisfy: 
\[
\Pr (\textrm{state }i|i+1)=\frac{2}{3}\]
\[
\Pr (\textrm{state }i+1|i)=\frac{1}{3}\]
\[
\Pr (\textrm{state }i|i+1)\Pr (\textrm{state }i+1)\]
\[
=\Pr (\textrm{state }i+1|i)\Pr (\textrm{state }i)\]
 
\[
\Rightarrow \Pr (\textrm{state }i)=\frac{\Pr (\textrm{state }i+1)}{2}\]
In particular, this implies that the stationary probability of the goal state
will be \( \Theta (2^{-n}) \). This, implies that the expected number of steps
between visits to the goal state is \( \Theta (2^{n}) \). All that remains
is showing that a gradient estimate which does not visit the goal state will
not be accurate. This can be done by noticing that the gradient estimate provided
by any state sequence which does not visit the goal state will be identical
to reinforcement learning where the goal transition reward is removed. This
altered reinforcement learning problem has zero gradient and so the gradient
direction must be arbitrary.
\end{proof}
Since Figure \ref{fig1} is a very simple reinforcement learning problem, it
is easy to imagine that many more complex problems have this simple problem
embedded within the larger problem. 
\begin{figure}
\resizebox*{0.1\textwidth}{!}{\includegraphics{figs/twomdp.eps}} \resizebox*{0.4\textwidth}{!}{\includegraphics{figs/fig_2score.eps}} \resizebox*{0.4\textwidth}{!}{\includegraphics{figs/fig_2phase.eps}} 


\caption{\label{fig2} Example 2: A) See text. B top) The average reward vs. time (on
a \protect\( 10^{7}\protect \) scale) of a policy under standard gradient descent
using the sigmoidal policy parameterization (\protect\( \pi (1;s,\theta _{i})\propto \exp (\theta _{i})/(1+\exp (\theta _{i}))\protect \),
with the initial conditions \protect\( \pi (i,1)=.8\protect \) and \protect\( \pi (j,1)=.1\protect \).
B bottom) The average reward vs. time (unscaled) under standard gradient descent
(solid line) and natural gradient descent (dashed line) for an early window
of the above plot. D) Phase space plot for  the standard gradient case (the
solid line) and the natural gradient case (dashed line).}
\end{figure}
 

The situation is more generic and worse than theorem \ref{th-inefficient} might
indicate. Let us give an additional example in which the situation is dire even
for a two state example as shown in Figure \ref{fig2}B. Our example will use
the common Gibbs table-lookup distribution, \( \tilde{\Pi }_{G}=\{\pi _{\theta }:\pi (a|s)\propto \exp (\theta _{sa})\} \).
The gradient of the discounted average reward (as shown later) is: 

\begin{equation}
\label{partial_grad}
\partial _{sa}\eta (\pi )=\frac{1}{1-\gamma }d_{\pi }(s)\pi (a|s)A_{\pi }(s,a)
\end{equation}
Increasing the chance of a self-loop at \( i \) decreases the stationary probability
of \( j \), which hinders the learning at state \( j \). Under an initial
policy that has the stationary distribution \( \rho (i)=.8 \) and \( \rho (j)=.2 \),
learning at state \( i \) reduces the learning at state \( j \) leading to
an an extremely flat plateau of improvement at 1 average reward shown in Figure
\ref{fig2}C (see figure text). Figure \ref{fig2}D shows that this problem
is so severe that \( \rho (j) \) drops as low as \( 10^{-7} \) from it's initial
probability of \( .2 \), which makes sampling the gradient difficult. Figure
\ref{fig2}E shows where this occurs and gives a clearer picture (see figure
text).

\emph{Sham, fill in the missing figures. -John}

One question immediately arises: are we suffering from numerical error problems?
The answer is no, as can be shown by a careful (and somewhat hairy) analysis
of reinforcement learning with the Gibbs distribution. The analysis is given
in section \ref{sec-gibbs_works}.

This example is remarkably discouraging for policy gradient approaches. We can
easily make it even worse by using a few extra states in a chain as in figure
\ref{fig1}.


\section{Incremental Improvement}

Gradient methods guarantee improvement due partially to the incremental nature
of the algorithm although no \emph{rate} of improvement guarantees are made.
In contrast, dynamic programming with function approximation has only very weak
performance guarantees (in terms of the worst case error) primarily due to the
possibility of drastic policy changes. Before we analyze the problems with gradient
methods, we first state the general conditions for incremental policy improvement.

Let's consider the incremental update rule:
\begin{equation}
\label{fa_update}
\pi (a|s)\propto \pi (a|s)(1+\alpha f(s,a))
\end{equation}
where \( f \) is some vector. Note that this update rule is to first order
equal to the update rule \( \pi (a|s)\propto \pi (a|s)\exp (\alpha f(s,a)) \),
which enforces positivity. Also note that using an infinite \( \alpha  \) returns
a greedy policy based on \( f \). If \( f \) is equal to the true advantages
\( A \), then the probability of actions with highest advantages increase the
fastest. 

Before we state the theorem, a few definitions are in order. Given a fixed starting
state distribution \( m_{0}(s_{0}) \), a fixed policy, \( \pi (a|s) \), and
a fixed Markov decision process, we can define the distribution at timestep
\( t \) as: 
\[
d_{\pi ,t}(s)=E_{\pi ,\mu }\Pr (s_{t}=s|s_{0})\]
We are most concerned with the \( \gamma  \) discounted average distribution:
\[
d_{\pi }(s)\equiv (1-\gamma )\sum _{t=0}^{\infty }\gamma ^{t}d_{\pi ,t}(s)\]
, which is analogous to the stationary distribution in the infinite time setting
(\emph{ie} as \( \gamma \rightarrow 1 \) then \( d_{\pi }(s) \) tends to the
stationary distribution) Also, we define the inner product for vectors in the
state-action space as:
\[
E_{d_{\pi }\pi }xx'=\sum _{sa}d_{\pi }(s)\pi (a|s)x(s,a)x^{\prime }(s,a)\]
 where \( d_{\pi }(s)\pi (a|s) \) is the state-action distribution.. 

\begin{thm}
\label{th-performance} Let \( A \) be the true advantages. If the update rule
is \( \pi (a|s)\leftarrow \pi (a|s)(1+\alpha f(s,a)) \) , then the performance
improvement of \( \eta  \) is: 
\begin{equation}
\label{inner_prod}
\Delta \eta =\frac{\alpha }{1-\gamma }E_{d_{\pi }\pi }Af+O(\alpha ^{2})\, .
\end{equation}

\end{thm}
\begin{proof}
As shown in \cite{sutton99policy}, the gradient of the discounted average reward
from a starting state \( s_{0} \) chosen according to \( \mu  \) is:
\begin{equation}
\label{disc-gradient}
\nabla \eta (\pi )=\frac{1}{1-\gamma }E_{s\sim d_{\pi }(s)}\left[ \sum _{a}Q_{\pi }(s,a)\nabla \pi (a|s)\right] 
\end{equation}
Let us consider the table-lookup Gibbs distribution, \( \tilde{\Pi }_{G}=\{\pi _{\theta }:\pi (a|s)\propto \exp (\theta _{sa})\} \).
Note that \( \partial _{sa}\pi (a^{\prime }|s^{\prime })=\delta _{s^{\prime }s}\pi (a|s)(\delta _{a^{\prime }a}-\pi (a^{\prime }|s)) \),
where \( \partial _{sa}\equiv \partial /\partial \theta _{sa} \). It follows
that: 
\begin{eqnarray}
\partial _{sa}\eta (\pi ) & = & \frac{1}{1-\gamma }d_{\pi }(s)\left[ \sum _{a}Q_{\pi }(s,a)\pi (a|s)(\delta _{aa^{\prime }}-\pi (a^{\prime }|s))\right] \\
 & = & \frac{1}{1-\gamma }d_{\pi }(s)\pi (a|s)\left[ Q_{\pi }(s,a)-E_{\pi (a^{\prime }|s)}Q_{\pi }(s,a^{\prime })\right] \label{partial_grad} \\
 & = & \frac{1}{1-\gamma }d_{\pi }(s)\pi (a|s)A_{\pi }(s,a)\, .
\end{eqnarray}
 For some change \( \Delta \theta _{sa} \) to the parameters, the update rule
is:
\[
\pi (a|s,\theta _{t+1})\leftarrow \pi (a|s,\theta _{t})\exp (\Delta \theta _{sa})\]
, the resulting change to the performance is \( \Delta \eta =\sum _{sa}\partial _{sa}\eta \Delta \theta _{sa}=\frac{1}{1-\gamma }\sum _{sa}d_{\pi }(s)\pi (a|s)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 =\frac{1}{1-\gamma }\sum _{sa}d_{\pi }(s)\pi (a|s)A(s,a)\alpha f(s,a)=\frac{\alpha }{1-\gamma }E_{d\pi }Af\]
to first order.
\end{proof}
This theorem states that to obtain improvement all we need is the much weaker
result that \( f \) must have a positive inner product with \( A \) \emph{}(as
opposed to strong and intractable conditions using the \( l_{\infty } \) norm).

Note that this theorem implies that if we define \( \tilde{f}(s,a)\equiv f(s,a)-\sum _{a^{\prime }}\pi (a^{\prime }|s)f(s,a^{\prime }) \)
then we get:
\[
\Delta \eta =\alpha E_{d\pi }Q\tilde{f}+O(\alpha ^{2})\, .\]
This is important because it is difficult to estimate \( E_{d\pi }fA \), since
the advantages can't be obtained directly from Monte-Carlo estimates. However,
we can directly estimate \( E_{d\pi }Q\tilde{f} \) since the state-action values
can be estimated from Monte-Carlo samples using the empirically observed discounted
average reward.

Let us relate the previous theorem to policy gradient methods. For simplicity,
let us consider the class of policies parameterized by one parameter, \( \theta  \).
The gradient (equation \ref{disc_gradient}) can be written in the form:
\begin{eqnarray*}
\frac{\partial \eta }{\partial \theta } & = & \frac{1}{1-\gamma }E_{d\pi }\left[ Q_{\pi }(s,a)\frac{1}{\pi (a|s)}\frac{\partial \pi (a|s)}{\partial \theta }\right] \\
 & = & \frac{1}{1-\gamma }E_{d\pi }\frac{\nabla \pi }{\pi }Q\, .
\end{eqnarray*}
The update rule is
\begin{eqnarray*}
\pi (a|s) & \propto  & \pi (a|s)+\frac{\partial \pi }{\partial \theta }\Delta \theta \\
 & = & \pi (a|s)(1+\Delta \theta \frac{1}{\pi (a|s)}\frac{\partial \pi (a|s)}{\partial \theta })
\end{eqnarray*}
 and so \( f=\frac{1}{\pi }\frac{\partial \pi }{\partial \theta } \). Thus
we see that gradient descent is a special case of the previous result in which
the direction followed is \( \frac{1}{\pi }\frac{\partial \pi }{\partial \theta } \)
or \( -\frac{1}{\pi }\frac{\partial \pi }{\partial \theta } \) depending on
the sign of \( E_{d\pi }fQ \). 

In order to improve the policy, it is \emph{crucial} to obtain the correct sign
of \( E_{d\pi }\frac{1}{\pi }\frac{\partial \pi }{\partial \theta }Q \)\emph{.}
As stated in the previous section, the variance in obtaining the correct sign
can be large.


\section{A Different Performance Measure}

In this section, we show that the performance measure \( \eta  \) is fundamentally
inadequate. As discussed in section 3, the performance measure being used must
be sensitive to improvements at unlikely states, where policy improvement might
be necessary in order for the agent to achieve optimal payoff.

We desire an alternative performance measure that does not down weight advantages
at unlikely states or unlikely actions. The performance measure we choose will
\emph{require} access to an exploration policy or simulator which can achieve
a more ``uniform'' distribution over states. A natural candidate for a performance
measure is to weight the improvement from all states and all actions more uniformly
(rather than by \( \mu  \)), such as 
\[
\omega (\pi )=\sum _{a}\sum _{s}\mu _{e}(s,a)J_{\pi }(s).\]
 where \( \mu _{e} \) is some 'exploratory' starting \emph{state-action} distribution.
Note that \( \omega =\eta  \) for the special case when \( \mu _{e}=\mu  \).
Under this performance measure, even if a state is not visited often (like the
right most states in example 1), importance will be given to improving the future
reward from this unlikely state. Since the policy that maximizes \( \omega  \)
also simultaneously maximizes the future reward from every state, then \emph{}maximizing
\( \omega  \) also maximizes \( \eta  \).

Now let us consider for an arbitrary \( \mu _{e} \) how difficult is it to
improve \( \omega  \) using a direction given to us by some vector \( f(s,a) \).
As discussed in the last section, the choice of parameterization implicitly
defines the vector \( f(s,a) \). In the following subsections, we show that
there exists a vector \( f(s,a) \) for which determining if \( f \) or \( -f \)
will improve the average state values takes \( O(1/\varepsilon ) \) samples
when the state values are not \( O(\sqrt{\varepsilon }) \) near optimal. The
same statement cannot be made for policy gradients of \( \eta  \). The subsections
are outlined as follows:

\begin{itemize}
\item in 5.1, we bound the sample size necessary to improve \( \omega  \)
\item in 5.2, we argue why using \( \mu _{e} \) different from \( \mu  \) is important
\item in 5.3, we discuss the implications of improving \( \omega  \) rather than
\( \eta  \)
\end{itemize}

\subsection{The Difficulty of Improving \protect\( \omega \protect \) }

Given a direction \( f \) how hard is it to determine if this direction will
improve the policy? We must first consider how information about the direction
of \( f \) can be found. Fundamentally, the only process available to us is
running the MDP of the reinforcement learning problem. Given certain assumptions
\ref{sec-monte}, it is reasonable to suppose that we can calculate a quantity
\( \hat{Q}(s,a) \) which is a nearly unbiased estimate of \( Q(s,a) \). Note
that this value is relative to the current value of the policy. Given that all
rewards are in some interval \( [0,R_{max}] \), these estimates will have some
finite variance, \( \sigma (s,a) \). Our goal is now to prove a statement about
the number of samples required in order to estimate if a particular direction
in state-action space given by \( f(s,a) \) is in fact the ``right'' direction.
In order to do this properly, we must first define a constrained \( f \): 
\[
\tilde{f}(s,a)\equiv f(s,a)-\sum _{a^{\prime }}\pi (a^{\prime }|s)f(s,a^{\prime })\]
With this definition, we have the property that for all states \( s \), \( E_{\pi (a|s)}\tilde{f}(s,a)=0 \).
Without loss of generality we also assume that \( \tilde{f} \) is of unit length,
\emph{ie} \( \left\langle \tilde{f},\tilde{f}\right\rangle =1 \). Also, let
us define the analogous discounted future distribution of states as:
\[
\tilde{d}_{\pi }(s)\equiv (1-\gamma )\sum _{t=0}^{\infty }\gamma ^{t}E_{\pi ,\mu _{e}(s_{0})}\Pr (s_{t}=s|s_{0})\, .\]
 Under theorem \ref{th-performance}, \( \omega  \) will improve when the policy
\( \pi  \) is perturbed toward \( f \) if \( E_{\nu }Q,\tilde{f}>0 \) , where
\( \nu (s,a) \) is an arbitrary distribution over state-action choices. For
example, this distribution might be derived from \( \mu _{e}(s) \).

\begin{thm}
\label{var_mu}Assume that samples \( s,a \) are drawn from some distribution
\( \nu (s,a) \) and that \( E_{\nu }\bar{f}^{2}=1 \). For each sample, we
are given an unbiased estimate \( \hat{Q}(s,a) \), of \( Q(s,a) \) with variance
\( \sigma ^{2}(s,a) \). Let \( \sigma _{\textrm{min}}=\min _{s,a}\sigma (s,a) \)
and assume all rewards satisfy \( R\in [0,R_{\textrm{max}}] \). Then the estimate
\( \hat{Q}(s,a)\tilde{f}(s,a) \) of \( E_{\nu }Af \) has variance bounded
by:
\[
\sigma ^{2}_{\textrm{min}}-(E_{\nu }A\tilde{f})^{2}\leq \Sigma ^{2}\leq \frac{R_{\textrm{max}}^{2}}{4}\, .\]
 
\end{thm}
\begin{proof}
Since the \( \hat{Q} \) are unbiased, the mean \( \mu  \) of the estimate
\( \hat{Q}(s,a)\tilde{f}(s,a) \) is also unbiased. The variance of this estimate
is:
\begin{eqnarray}
\Sigma ^{2} & = & E_{\nu }\tilde{f}^{2}\hat{Q}^{2}-\mu ^{2}\\
 & = & \sum _{s,a}\nu (s,a)\int dP(\hat{Q}(s,a))\hat{Q}^{2}(s,a)\tilde{f}^{2}(s,a)-\mu ^{2}\\
 & = & \sum _{s,a}\nu (s,a)\tilde{f}^{2}(Q^{2}(s,a)+\sigma ^{2}(s,a))-\mu ^{2}\, .\label{variance} 
\end{eqnarray}
 We can lower bound \( \sigma  \) as follows:
\begin{eqnarray*}
\Sigma ^{2} & \geq  & \sum _{s,a}\nu (s,a)\tilde{f}^{2}\sigma ^{2}(s,a)-\mu ^{2}\\
 & \geq  & \sigma ^{2}_{\textrm{min}}\sum _{s,a}\nu (s,a)\tilde{f}^{2}(s,a)-\mu ^{2}\\
 & = & \sigma ^{2}_{\textrm{min}}-\mu ^{2}
\end{eqnarray*}
 where have used the unit length of \( \tilde{f} \). We can upper bound \( \Sigma ^{2} \)
by noting that each sample \( \hat{Q}(s,a) \) is drawn from the interval \( [0,R_{\textrm{max}}] \)
and \( E\hat{Q}(s,a)=Q(s,a) \). This implies that the maximum variance for
any state-action is \( \frac{R_{\textrm{max}}^{2}}{4} \). Therefore, the expected
variance is bounded by \( \frac{R_{\textrm{max}}^{2}}{4} \).
\end{proof}
In order to determine if the direction \( f \) will improve the policy, we
have to determine with some certainty the correct sign of the mean \( \mu =E_{\nu }A\tilde{f} \).
The difficulty of this is determined by how much larger the ``signal'' \( \mu  \)
is than the ``noise'' \( \Sigma  \). If the ratio \( \Sigma /\mu  \) is
large, then determining the sign \( E_{\nu }A\bar{f} \) will require many samples. 

\begin{cor}
\label{sig_noise}Under the assumptions and sampling model of theorem \ref{var_mu},
then for any \( f \), the noise to signal is bounded by
\[
\frac{\Sigma ^{2}}{\mu ^{2}}\geq \frac{\sigma ^{2}_{\textrm{min}}}{E_{\nu }A^{2}}-1\, .\]

\end{cor}
\begin{proof}
The \( \tilde{f} \) that maximizes \( E_{\nu }A\tilde{f} \) also minimizes
the lower bound on \( \Sigma ^{2} \) (subject to the normalization constraint
on \( \tilde{f} \)). This occurs when \( \tilde{f}=\frac{A}{\sqrt{E_{\nu }A^{2}}} \)
. Substitution leads to the result.
\end{proof}
Lets consider the special case of \( \omega =\eta  \) when \( \mu _{e}=\mu  \).
If all the large advantages are at states that are visited infrequently then
\( E_{\nu }A^{2} \) will be small. The corollary shows that it is difficult
to determine if any direction will improve the policy. Note that this is what
occurs in the examples of the previous section. In the two state example, at
the plateau, state \( j \) is visited highly infrequently, and so \( E_{\nu }A^{2} \)
is small, eventhough \( E_{\nu }A^{2} \) was large to begin with. 


\subsection{Why is \protect\( \omega \protect \) better?}

Let us bound the number of samples \( \hat{Q}(s,a) \) needed to determine if
\( f \) will improve. The variance will decrease like \( \frac{1}{k} \) where
\( k \) is the number of samples. 

\begin{cor}
\label{sample_size}Under the assumptions and sampling model of theorem \ref{var_mu},
then the estimate \( X=\frac{1}{k}\sum _{i=1}^{k}\hat{Q}(s,a)\tilde{f}(s,a) \)
has the
\[
\Pr (\textrm{sign}(X)=\textrm{sign}(E_{\nu }Af))\leq e^{-\frac{2k(E_{\nu }Af)^{2}}{R_{\textrm{max}}^{2}}}\]

\end{cor}
\begin{proof}
Hoeffding's inequality for \( k \) independent identical random variables,
\( X\in [0,R_{\textrm{max}}] \) states: 
\[
\Pr \left( EX-\frac{1}{k}\sum _{i}X_{i}>\epsilon \right) \leq e^{-\frac{2k\epsilon ^{2}}{R_{\textrm{max}}^{2}}}\]
setting \( \epsilon =EX=E_{\nu }Af \) gives the result.
\end{proof}
We know that an advantage of size \( A \) will imply a bias of size at least
\( \mu =(1-\gamma )\frac{A}{n} \). Here \( n \) is the number of state-actions
and we are assuming a uniform distribution over state-actions. This will, in
turn, imply that at most \( k=\frac{n^{2}}{A^{2}(1-\gamma )^{2}} \) samples
are required in order to estimate the ``right'' direction with high confidence.
This quantity is polynomial in all parameters and so given that a significant
advantage exists anywhere, it convergences far faster than policy gradient estimates. 

As suggested by corollary \ref{sig_noise}, if \( E_{\nu }A^{2} \) is small
then determining if any \( f \) will improve the policy will be difficult.
If the policy has near optimal performance, then all the advantages are small
and we expect improvement to be difficult regardless of the performance measure
(\emph{ie} \( \mu _{e} \)) being used. This is the common situation that close
to a maxima it is difficult to determine if any direction will improve the function
due to local flatness. The ideal situation is that the estimates only have high
variance when the policy has near optimal performance. Unfortunately, as demonstrated
by our two examples, this is not the case for \( \eta  \). The important question
we now address is ``How difficult is it to determine if \( f \) improves a
sub-optimal policy?''

First, let us provide a theorem as to how far the policy is from optimal in
terms of how large \( E_{\nu }A^{2} \) is.

\begin{thm}
\label{th-constraint} Let \( J^{*}(s) \) be the maximum value of \( J(s) \),
\( \nu _{0}=\min _{s,a}\nu (s,a) \), and \( A_{\infty }=\max _{s,a}A(s,a) \).
Then 
\begin{equation}
\label{sub_optimal}
|J(s)-J^{*}(s)|\leq \frac{A_{\infty }}{1-\gamma }\leq \frac{1}{1-\gamma }\sqrt{\frac{E_{\nu }A^{2}}{\nu _{0}}}\, .
\end{equation}

\end{thm}
\begin{proof}
Let \( A_{\infty }=\max _{s,a}A(s,a) \). By definition of the advantages, if
we deviate from the current policy at any step we can gain at most \( A_{\infty } \)
future reward. We can deviate at every steps, and by induction, \( |J(s)-J^{*}(s)|<A_{\infty }/(1-\gamma ) \)
(\emph{Cite book, or prove it. -John)}. The largest possible \( A_{\infty } \)
for a given \( E_{\nu }A^{2} \) satisfies \( E_{\nu }A^{2}=\nu _{0}A_{\infty }^{2} \). 
\end{proof}
Note that this implies for any distribution \( \mu  \) and for \( \omega (\pi )=E_{\mu }\{J_{\pi }(s)\} \),
\begin{equation}
\label{sub_optimal_2}
(\omega -\omega ^{*})^{2}\leq \frac{E_{\nu }A^{2}}{\nu _{0}(1-\gamma )^{2}}
\end{equation}
 where \( \nu  \) is arbitrary (not necessarily related to \( \mu  \)).

This bound elucidates the problems with using \( \mu  \) as the starting distribution.
Let us consider the case in which \( E_{\nu }A^{2} \) is small, so determining
if \( f \) or \( -f \) improves the policy will be difficult. If \( \nu _{0} \)
is small, then \( A_{\infty } \) could be large even if \( E_{\nu }A^{2} \)
is small. Thus, \( \eta  \) could be far from \( \eta ^{*} \), since each
\( J(s) \) is significantly sub-optimal. Essentially, the large advantages
are hidden to the agent due to the low probability of visiting the state-actions
with large advantages. This makes policy improvement difficult regardless of
the choice of \( f \). Unfortunately, the presence of large advantages leaves
open the possibility that the policy is significantly sub-optimal. 

Instead, let us consider a \( \mu _{e} \) that does not allow \( \nu _{0} \)
to be extremely small. This will force each \( J(s) \) to be close to optimal
if \( E_{\nu }A^{2} \) is small. The number of samples must depend on the direction
\( f \) being followed, and there are directions for which determining whether
\( f \) or \( -f \) improves the policy has high variance. For example, directions
which ``alias'' important distinctions between the states can have high variance. 

In summary, for a near uniform \( \mu _{e} \), we know that the distance from
optimal is constrained to satisfy theorem \ref{th-constraint}, and if we are
far from optimal there exists a direction \( f(s,a) \) which can be confirmed
as ``good'' with \( k=O\left( \frac{R_{\textrm{max}}^{2}}{(E_{\nu }Af)^{2}}\right)  \)
samples.


\subsection{What about \protect\( \eta \protect \)?}

\emph{I weakened this section to essentially state that, in principle, it is
possible to 'usually' improve \( \eta  \) when \( \omega  \) improves. -Sham}

What has been lost by improving \( \omega  \) instead of \( \eta  \)? Our
real goal \emph{is} improving \( \eta  \). \emph{}An important question is:
``Can \( \eta  \) decrease as we search for this near-optimal policy?'' In
general, the answer is ``yes'' because we are only guaranteed to increase
\( \omega  \). To see this, consider \( f(s,a)=A(s,a) \) on all states visited
often under \( d_{\pi }(s) \) and \( f(s,a)=-A(s,a) \) on all other states.
This will force \( E_{\nu }fA>0 \) under the exploitation policy. However,
if the state distribution from \( \mu _{e} \) has high probability at states
where \( f(s,a)=-A(s,a) \) then \( \eta  \) can decrease when we optimize
according to \( \omega  \). For a sufficiently flexible space of \( f(s,a) \),
the ultimate policy will be near-optimal, but increasing \( \omega  \) does
not always imply \( \eta  \) improves. There \emph{do} exist \( f(s,a) \)
for which optimizing \( \omega (\pi ) \) always improves \( \eta (\pi ) \).
To see this, simply make \( f(s,a)=A(s,a) \) everywhere. 

In general, determining if any \( f \) or \( -f \) improves \( \eta  \) at
every step is impractical, as shown previously. \emph{This is why we considered
\( \omega  \) to begin with.} However, for all other cases we would like to
determine if \( f \) improves both \( \omega  \) and \( \eta  \) with \( O(1/\varepsilon ) \)
samples, if the policy is not \( O(\sqrt{\varepsilon }) \) near optimal. 

\emph{I'm losing the thread again here. The word 'oracle' confuses me and I
think you work with strange ``derived'' distributions. I'll let you go through
it again and see if you can make sense of it. -John}

Let \( \nu  \) and \( \tilde{\nu } \) be the distributions implied by \( \mu  \)
and \( \mu _{e} \) respectively and let us consider the case in which we are
not guaranteed to be \( \frac{1}{1-\gamma }\sqrt{\frac{\varepsilon }{\nu _{0}}} \)
near optimal policy. Theorem \ref{improvement} states that there exists an
oracle such that \( \omega  \) can be improved with \( O(1/\varepsilon  \))
samples. As far as \( \eta  \) is concerned, let us consider the non-problematic
case in which the agent also visits states with large advantages under \( \mu  \),
\emph{ie} \( E_{\nu }A^{2}>\varepsilon  \). Also by theorem \ref{improvement},
there exist a different oracle such that improvement of \( \eta  \) requires
\( O(1/\varepsilon ) \) samples. Further, there are \( \tilde{f} \) that jointly
satisfy the conditions of each oracle, \( (E_{\nu }\tilde{f}A)^{2}>\varepsilon  \)
and \( (E_{\tilde{v}}\tilde{f}A)^{2}>\varepsilon  \) (when not in the problematic
case for \( \eta  \)). For instance, \( \tilde{f}\propto A \) or any \( \tilde{f} \)
sufficiently parallel will satisfy both of these conditions. For these \( \tilde{f} \),
then we can determine if both \( \eta  \) and \( \omega  \) will improve with
\( O(1/\varepsilon ) \) samples. 

The big picture is that we have lost very little by improving \( \omega  \),
if we can find these good directions \( f \). First, we can improve \( J(s) \)
on average, under \( \mu _{e} \), with \( O(1/\varepsilon ) \) samples until
\( \eta  \) is guaranteed to be near-optimal. Second, also with \( O(1/\varepsilon ) \)
samples, we can determine if \( \eta  \) will improve as well, in the non-problematic
cases. Thus all that we have lost in principle is that improvement might not
be possible for \( \eta  \) when the advantages are at unlikely states, which
is unavoidable if we will only collect \( O(1/\varepsilon ) \) samples. However,
remember that optimizing \( \omega  \) will also ultimately optimize \( \eta  \).
We now discuss how to find these good directions \( f \).


\section{The Need for Non-Parametric Function Approximation }

There is no reason to believe that a ``good'' choice of the vector \( f(s,a) \)
can be made without significant prior knowledge about the form of the reinforcement
learning problem. Given some number of samples drawn from \( \nu (s,a) \),
we can test the value of a particular vector \( f(s,a) \). The vector \( f \)
or \( -f \) may satisfy: \( E_{\nu }fA>\epsilon  \), in which case we can
improve the policy with high probability. Or, it may be that the expectation
is to small and we will be unable to determine whether or not the \( f \) is
a beneficial perturbation given the (necessarily finite) samples from \( \nu (s,a) \).
This last case is by far the most common, and so it is necessary that we test
many different \( f \) with the same set of samples from \( \nu (s,a) \).
This necessity creates the possibility of overfitting: we might find an \( f \)
which works \emph{only} on our sample set and not on future draws from \( \nu (s,a) \).

There are two approaches to avoiding overfitting. One is to work with a finitely
parameterized set \( F \) of vectors \( f(s,a) \), and then simply use enough
samples from \( \nu (s,a) \) that we can guarantee (via VC bounds or other
approaches) that the empirical estimate of \( E_{\nu }fA \) must be strongly
related to the actual value of \( E_{\nu }fA \). The disadvantage of this approach
is that it might not work. In particular, it is unclear (without extra prior
knowledge) that we can guarantee there exists \( f\in F \) with a large dot
product (\( E_{\nu }fA \)). This is exactly what we wish to avoid by shifting
from optimizing \( \eta  \) to \( \omega  \). 

The other approach is ``non-parametric'' which is a great misnomer. In a non-parametric
approach the number of parameters grows with the number of samples, but always
remains small enough that we can guarantee that the empirical estimate of \( E_{\nu }fA \)
remains close to its real value. This is the approach that we advocate here:
choose an \( f(s,a) \) by sampling from \( \nu (s,a) \) and testing until
an \( f(s,a) \) is found which improves \( \omega  \) with high probability.
In the process of discovering \( f(s,a) \), increase the space of functions
as more samples are acquired. We can \emph{always} check to see if a ``good''
\( f(s,a) \) has been learned by simply acquiring a few extra independent samples
from \( \nu (s,a) \) and testing to see that \( f(s,a) \) behaves well on
the extra samples. If the test fails, then we have more samples from which to
learn a new \( f \). 

Our suggested technique then does the following:

\begin{enumerate}
\item Sample \( k \) samples from \( \nu (s,a) \) and calculate \( \hat{Q}(s,a) \)
for each sample.
\item Find an \( f(s,a)\in F(k) \) for which the empirical estimate of \( \frac{1}{k}\sum _{i=1}^{k}\bar{f}(s,a)Q(s,a) \)
is largest.
\item Verify that \( f(s,a) \) does well with \( l \) new independent samples drawn
from \( \nu (s,a) \) (or other sample complexity approaches if applicable).
If no, then go to step \( 2 \) with an extra \( l \) samples.
\item Alter the policy by \( \pi (a|s)\propto \pi (a|s)+\alpha f(s,a) \) and go to
step \( 1 \).
\end{enumerate}
This approach will always result in improvement according to the metric \( \omega  \)
and so it will always result in improvement given that significant advantages
exist. 

Another advantage of the nonparametric approach is that we can avoid trading
off between improvement of \( \omega  \) and improvement of \( \eta  \). Samples
from \( \eta  \) are easier to acquire so we could easily acquire an addition
\( k \) samples from \( \eta  \) and then find the optimal \( f \) for the
empirical distribution which is a mix of the \( \nu (s,a) \) and \( d_{\pi }(s)\pi (a|s) \).
If the choice of \( f \) makes optimization on the \( d_{\pi }(s)\pi (a|s) \)
samples essentially orthogonal to optimization on the \( \nu (s,a) \) samples,
then we expect that \( f(s,a) \) will almost never decrease the value \( \eta  \).

\emph{(I don't quite know know how to work this into the story line. -John)}

One other 

A ``good'' set of \( f \) directions might satisfy the following criterion:
\begin{equation}
\label{eps_close}
E_{\tilde{d}\pi }(f-A)^{2}+E_{d\pi }(f-A)^{2}\leq \varepsilon ^{2}\, .
\end{equation}
 These \( f \) will always improve \( \omega  \) when not \( O(\sqrt{\varepsilon }) \)
near optimal. Further, these \( f \) can simultaneously improve \( \eta  \)
unless the policy is near optimal.

\bibliographystyle{plain}
\bibliography{bib}



\section{Appendix}

\label{sec-gibbs_works} The goal of this section is constructing a proof that
policy gradient will \emph{eventually} work on a Gibbs table lookup distribution.
Note that the time scale of ``eventually'' can be remarkably long.

The Gibbs table-lookup distribution is \( \tilde{\Pi }_{G}=\{\pi _{\theta }:\pi (a|s)\propto \exp (\theta _{sa})\} \).
Using the notation \( \partial _{sa}\equiv \partial /\partial \theta _{sa} \),
\begin{equation}
\label{partial_grad}
\partial _{sa}\eta (\pi )=d_{\pi }(s)\pi (a|s)(Q_{\pi }(s,a)-J_{\pi }(s))=d_{\pi }(s)\pi (a|s)A_{\pi }(s,a)
\end{equation}
Note that for any deterministic policy (\emph{ie} \( \forall s\, \exists a\textrm{ s}.\textrm{t}.\textrm{ }\theta _{sa}=\infty  \))
the gradient is zero. Since the gradient is 0 at all points at infinity, this
suggests the dismal possibility that the gradient descent could lead to arbitrary
deterministic policy. It is straight forward to show that if the stationary
distribution, of the asymptotic policy, is nonzero for all states then this
asymptotic policy is optimal. However, the non-trivial question is can \( \partial _{sa}\eta _{\pi } \)
tend to \( 0 \) due to \( d(s) \) tending to \( 0 \) in a manner such that
such that the optimal policy is not achieved. Note that the gradient \( \partial _{sa}\eta (\pi ) \)
is zero if either the advantage is zero or if \( d(s) \) is zero. The following
theorem states that this can never occur, and the key to proof is dealing with
this case (where learning to one state could stop due to a vanishing stationary
probability). We only consider the infinitesimal learning rate case where \( \theta _{t}=\theta _{0}+\int _{0}^{t}\nabla \eta ^{\pi _{t}}dt \). 

\begin{thm}
Assume that \( \pi _{\infty } \) is the single limiting policy corresponding
to \( \lim _{t\rightarrow \infty }\theta _{t} \). Then \( \pi _{\infty } \)
is globally optimal. 
\end{thm}
\begin{proof}
Let \emph{}\( S^{*}=\{s|\exists \pi \textrm{ s}.\textrm{t}.\textrm{ }\rho _{\pi }(s)\neq 0\} \).
Our proof that \( \pi _{\infty } \) globally maximizes the average reward consists
of showing that for all \( s\in S^{*} \), \( J^{\pi _{\infty }}(s)=\max _{a}Q^{\pi _{\infty }}(s,a) \)\emph{,
ie} \( \pi _{\infty } \) partially satisfies the Bellman equations. When clear,
the subscript on \( \pi _{t} \) is dropped, \emph{eg} \( \rho ^{\pi _{\infty }}=\rho ^{\infty } \).
Assume for now that as \( t\rightarrow \infty  \) then for all \( s\in S^{*} \)
and actions \( a \) either \( \pi _{t}(a|s)\rightarrow 0 \) or \( A^{t}(s,a)\rightarrow 0 \).
For all \( \tilde{a}\in \textrm{argmax}_{a}Q^{\pi _{\infty }}(s,a) \), \( \partial _{sa}\eta ^{t} \)
is positive for sufficiently large \( t \), so \( \pi _{\infty }(a|s)\neq 0 \)
and \( A^{\infty }(s,a)=0 \). Therefore, \( \pi _{\infty } \) satisfies the
Bellman equations for \( s\in S^{*} \). It follows that if \( \tilde{a}\notin \textrm{argmax}_{a}Q^{\pi _{\infty }}(s,a) \)
then \( \pi _{\infty }(\tilde{a},s)=0 \), and so if \( t \) is sufficiently
large \( \partial _{s\tilde{a}}\eta ^{t}<0 \), else there must exist a partial
extrema for some \( \tilde{t}\geq t \). 

It is straightforward to show that \( \lim _{t\rightarrow \infty }\partial _{sa}\eta ^{t}=0 \),
and so as \( t\rightarrow \infty  \) either \( \rho ^{t}\rightarrow 0 \),
\( \pi _{t}(a|s)\rightarrow 0 \), or \( A^{t}(s,a)\rightarrow 0 \). We now
show that even if if \( \rho ^{\infty }\neq 0 \), then \( \pi _{\infty }(a|s)=0 \)
or \( A^{\infty }(s,a)=0 \), which completes the proof. Assume that for some
\( s \) that \( \rho ^{\infty }(s)=0 \). By stationarity, \( \rho ^{t}(s)=\sum _{s_{0}}P(s_{\tau }=s|s_{0})\rho ^{t}(s_{0}) \),
and so for any trajectory \( s_{0},a_{0},s_{1},a_{1}\ldots s \), \( \rho ^{t}(s)\geq \rho ^{t}(s_{0})p_{s_{0}s_{1}}^{a_{0}}\pi _{t}(a_{0}|s_{0})\ldots p_{s_{\tau -1}s}^{a_{\tau -1}}\pi _{t}(a_{\tau -1}|s_{\tau -1}) \).
For every \( \tau  \)-length trajectory with \( p_{s_{i}s_{i+1}}^{a_{i}}\neq 0 \)
and \( \rho ^{\infty }(s_{0})\neq 0 \), there must exist at least one \( s_{i},a_{i} \)
such that \( \pi _{\infty }(a_{i}|s_{i})=0 \), else \( \rho ^{\infty }(s)\neq 0 \)
or \( s\notin S^{*} \). It can be shown that there exist some \( \tilde{s} \),
\( \tilde{a} \) and positive constant \( \tilde{\alpha } \) such that \( \forall t\, \rho ^{t}(s)\geq \tilde{\alpha }\rho ^{t}(\tilde{s})\pi _{t}(\tilde{a}|\tilde{s}) \),
\( \rho ^{\infty }(\tilde{s})\neq 0 \), and \( \pi _{\infty }(\tilde{a}|\tilde{s})=0 \)
(using a trajectory such that \( \pi _{\infty }(a_{i}|s_{i})=0 \) only for
\( i=0 \)). Assume that \( \pi _{\infty }(s)\neq 0 \) and \( A^{\infty }(s)\neq 0 \)
(else the conjecture is true), then it follows from equation \ref{partial_grad}
and the previous inequality that for each \( a \), \( \vert \int _{0}^{\infty }\partial _{sa}\eta ^{t}dt\vert \geq \alpha \vert \int _{0}^{\infty }\partial _{\tilde{s}\tilde{a}}\eta ^{t}dt\vert  \)
for some positive constant \( \alpha  \). However, \( \pi _{\infty }(\tilde{s})=0 \)
forces \( \vert \int _{0}^{\infty }\partial _{\tilde{s}\tilde{a}}\eta ^{t}dt\vert  \)
to be \( \infty  \), and so \( \vert \int _{0}^{\infty }\partial _{sa}\eta ^{t}dt\vert  \)
is \( \infty  \), contradicting \( \pi _{\infty }(s)\neq 0 \) and \( A^{\infty }(s)\neq 0 \).
\end{proof}

\section{How to Monte Carlo}

\label{sec-monte}

In order to determine which direction is the ``right'' direction, we need
to know how to estimate this right direction. This is a subtle problem when
you must (in general) sample from the underlying reinforced MDP forever in order
to acquire an unbiased estimate of the discounted future reward, \( \hat{Q}(s,a) \).

Intuitively, if we run the Markov process for a time long compared to the discount
\( \gamma  \), we will obtain an estimate \( \hat{Q}(s,a) \) which is ``nearly''
unbiased, simply due to the fact that the contribution to the reward from future
actions will necessarily be small.

\end{document}
