%% This LaTeX-file was created by <jl> Wed Oct  3 21:57:18 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

\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 a Markov decision process 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 5, we show that determining if any direction (in policy space) will
improve the average reward can be arbitrarily difficult. 
\item In section 6, an alternative performance measure is proposed which is sensitive
to performance improvement at unlikely states (unlike the average reward). We
show that improvement of this alternative performance measure can never have
an arbitrarily small signal to noise ratio. 
\item In section 7, we discuss how we can improve this alternative performance measure
without ever detecting a decrease in the average reward. 
\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 finite Markov decision process
(MDP) with rewards. An MDP with rewards is a tuple \( (S,m_{0},A,R,P) \) where:
\( S \) is finite set of states, \( m_{0} \) 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 \( T \)-step reward from
\( s_{0} \), which can be seen as an approximation scheme to maximizing the
average reward. We define the state-action value as 
\begin{equation}
\label{eq-Q}
Q_{\pi }(s,a)\equiv E_{\pi }\{\frac{1}{T}\sum ^{T}_{t=0}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:
\[
\eta (\pi )=E_{m_{0}}\{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 \( O(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 \( O(2^{-n}) \). This, implies that the expected number of steps between
visits to the goal state is \( O(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 commonly used Gibbs table-lookup distribution, \( \tilde{\Pi }_{G}=\{\pi _{\theta }:\pi (a|s)\propto \exp (\theta _{sa})\} \).
Using the notation \( \partial _{sa}\equiv \partial /\partial \theta _{sa} \),
it is straightforward to show that the gradient of the average reward is: 
\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}
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).

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 \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{Policy Gradient Behaves Poorly}

Gradient methods guarantee improvement due to the incremental nature of the
algorithm although no \emph{rate} of improvement guarantees are made. Dynamic
programming using function approximation has only 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. Under the starting
state distribution \( m_{0}(s) \), the \( T \)-step future distribution of
states is:
\[
d_{\pi }(s)\equiv \frac{1}{T}\sum _{\tau =0}^{T}\sum _{s_{0}}m(s_{0})\sum _{s}P(s_{\tau }=s|s_{0})\]
, which is analogous to the stationary distribution in the infinite time setting
(\emph{ie} as \( T\rightarrow \infty  \) then \( d_{\pi }(s) \) tends to the
stationary distribution) . Also, we define the inner product for vectors in
the state-action space as:
\[
<x,x^{\prime }>_{d\pi }=\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} Assume the definition given above for \( d_{\pi }(s) \).
Let us consider the update rule \( \pi (a|s)\leftarrow \pi (a|s)(1+\alpha f(s,a)) \)
for some vector \( f \) and some small \( \alpha  \). Let \( A \) be the
true advantages. Then the performance improvement of \( \eta  \) is: 
\begin{equation}
\label{inner_prod}
\Delta \eta =\alpha <A,f>_{d\pi }+O(\alpha ^{2})\, .
\end{equation}

\end{thm}
\begin{proof}
The exact gradient of the discounted reward from a starting state chosen according
to \( m_{0} \) is:
\begin{equation}
\label{disc_gradient}
\nabla \eta (\pi )=\sum _{s,a}d_{\pi }(s)\nabla \pi (a|s)Q_{\pi }(s,a).
\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 _{s^{\prime }a^{\prime }}=\delta _{ss^{\prime }}\pi (a|s)(\delta _{aa^{\prime }}-\pi (a^{\prime }|s)) \),
where \( \partial _{sa}\equiv \partial /\partial \theta _{sa} \). It follows
that: 
\begin{eqnarray}
\partial _{sa}\eta (\pi ) & = & \sum _{a}d(s)\pi (a|s)(\delta _{aa^{\prime }}-\pi (a^{\prime }|s))Q(s,a)\\
 & = & d_{\pi }(s)\pi (a|s)(Q_{\pi }(s,a)-<Q_{\pi }(s,a^{\prime })>_{\pi (a^{\prime }|s)})\label{partial_grad} \\
 & = & 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}=\sum _{sa}d(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 =\sum _{sa}d(s)\pi (a|s)A(s,a)(\alpha f_{sa})=<A,f>_{d\pi }\]
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 <Q,\tilde{f}>_{d\pi }+O(\alpha ^{2})\, .\]
This is important because it is difficult to estimate \( <f,A>_{d\pi } \),
since the advantages can't be obtained directly from Monte-Carlo estimates.
However, we can directly estimate \( <Q,\tilde{f}>_{d\pi } \) since the state-action
values can be estimated from Monte-Carlo samples using the empirically observed
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 update rule under a gradient method is
\begin{eqnarray*}
\pi (a|s) & \propto  & \pi (a|s)+\frac{\partial \pi }{\partial \theta }\Delta \theta \\
 & = & \pi (a|s)(1+\Delta \theta \frac{\partial \log \pi (a|s)}{\partial \theta })
\end{eqnarray*}
 and so 
\[
f=\frac{\partial \log \pi }{\partial \theta }\]
 It follows that if \( \left\langle \partial \log \pi /\partial \theta ,A\right\rangle _{d\pi }>0 \)
then a small positive \( \Delta \theta  \) will improve the policy, otherwise
a negative \( \Delta \theta  \) will improve the policy. 

Under gradient descent, \( \Delta \theta  \) will have the same sign as \( \partial \eta /\partial \theta  \).
The gradient (equation \ref{disc_gradient}) can be written in the form:
\[
\partial \eta /\partial \theta =<\partial \log \pi /\partial \theta ,Q>_{d\pi }\, .\]
 Thus we see that gradient descent is a special case of the previous result
in which the direction followed is \( \partial \log \pi /\partial \theta  \)
or \( -\partial \log \pi /\partial \theta  \) depending on the sign of \( <\partial \log \pi /\partial \theta ,Q>_{d\pi } \). 

In order to improve the policy, it is crucial to obtain the correct sign of
\( <\partial \log \pi /\partial \theta ,Q>_{d\pi } \) \emph{}on average\emph{.}
The next section discusses the variance issue in determining the sign of this
quantity. 


\section{Fixing Gradient Techniques}

\emph{TODO: Merge sections 5\&6. Merge upper and lower bounds on noise to signal.
Split off statements about \( \eta  \). }

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 reinforced MDP. Given certain assumptions \ref{sec-monte}, it is
reasonable to suppose that we can calculate a quantity \( \hat{Q}(s,a) \) which
is an unbiased estimate of the average \( T \)-step value of taking action
\( a \) in state \( s \) given policy \( \pi  \). Note that this value is
relative to the current value of the policy. Given that all rewards are finite,
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: 
\[
\forall s\, \, E_{\pi (a|s)}\tilde{f}(s,a)=0\]
 The theorem will use the notion of ``signal'' and ``noise'' where the signal
is given by: 
\[
\mu =E_{d(s)\pi (a|s)}\tilde{f}(s,a)Q(s,a)=E_{d(s)\pi (a|s)}\tilde{f}(s,a)A(s,a)\]
and the noise (variance) is given by: 
\[
\Sigma ^{2}=E_{d(s)\pi (a|s)}\tilde{f}^{2}(s,a)Q^{2}(s,a)-\mu ^{2}\, .\]
 

\begin{thm}
\label{sig_noise_lower}Assume that samples \( s,a \) are drawn from \( d(s)\pi (a|s) \).
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 _{0}=\textrm{argmin}_{s,a}\sigma (s,a) \).
Then for all vectors \( f(s,a) \) the noise to signal ratio is bounded by:
\[
\frac{\Sigma ^{2}}{\mu ^{2}}\geq \frac{\sigma ^{2}_{0}}{\left\langle A,A\right\rangle _{d\pi }}-1\]
Further, if \( \eta ^{*} \) is the optimal possible average reward and \( m_{-}=\min _{s,a}d_{\pi }(s)\pi (a|s) \),
then 
\[
|\eta -\eta ^{*}|^{2}\leq \frac{\left\langle A,A\right\rangle _{d\pi }}{m^{2}_{-}}\, .\]


\emph{Intuitively, this result states that if the advantages are small on average,
under \( d\pi  \), then the gradient will be difficult to estimate.} \emph{For
this to occur, any large advantages must be at states that are visited infrequently.
Note that this is what occurs in both of the previous examples. In the two state
MDP, at the plateau, state \( j \) is visited highly infrequently, and so \( \left\langle A,A\right\rangle _{d\pi } \)
is small (eventhough \( \left\langle A,A\right\rangle _{d\pi } \) was large
to begin with).} Unfortunately, if large advantages are present (even at unlikely
states), the agent may gain a large performance increase. 
\end{thm}
\begin{proof}
Since the \( \hat{Q} \) are unbiased, the mean \( \mu  \) is:
\begin{eqnarray*}
\mu  & = & \sum _{s,a}d(s)\pi (a|s)\int dP(\hat{Q}(s,a))\hat{Q}(s,a)\tilde{A}(s,a)\\
 & = & \left\langle \tilde{f},Q\right\rangle _{d\pi }=\left\langle \tilde{f},A\right\rangle _{d\pi }
\end{eqnarray*}
 and the variance is:
\begin{eqnarray}
\Sigma ^{2} & = & \left\langle \tilde{f}^{2}\hat{Q}^{2}\right\rangle -\mu ^{2}\\
 & = & \sum _{s,a}d(s)\pi (a|s)\int dP(\hat{Q}(s,a))\hat{Q}^{2}(s,a)\tilde{f}^{2}(s,a)-\mu ^{2}\\
 & = & \sum _{s,a}d(s)\pi (a|s)\tilde{f}^{2}(Q^{2}(s,a)+\sigma ^{2}(s,a))-\mu ^{2}\, .\label{variance} 
\end{eqnarray}
giving us: 

\[
\frac{\Sigma ^{2}}{\mu ^{2}}=\frac{\left\langle \tilde{f}^{2}(Q^{2}+\sigma ^{2})\right\rangle _{d\pi }}{\left\langle \tilde{f},A\right\rangle _{d\pi }^{2}}-1\]


Technically, \( \tilde{f} \) is constrained such that \( \sum _{a}\tilde{f}(s,a)\pi (a|s)=0 \)
(or equivalently \( \tilde{f}(s,a)\equiv f(s,a)-\sum _{a^{\prime }}\pi (a^{\prime }|s)f(s,a^{\prime })) \).
The goal is to minimize \( \frac{\Sigma ^{2}}{\mu ^{2}} \) subject to this
constraint. However, let's just minimize this quantity unconstrained since that
gives a bound. Thus:
\[
\frac{\partial (\sum ^{2}/\mu ^{2})}{\partial \tilde{f}_{sa}}=\frac{2d(s)\pi (a|s)\tilde{f}(s,a)(Q^{2}(s,a)+\sigma ^{2}(s,a))}{\mu ^{2}}-\frac{2\left\langle \tilde{f}^{2}(Q^{2}+\sigma ^{2})\right\rangle _{d\pi }\frac{\partial \mu }{\partial \tilde{f}_{sa}}}{\mu ^{3}}\]
 
\[
=\frac{2d(s)\pi (a|s)\tilde{f}(s,a)(Q^{2}(s,a)+\sigma ^{2}(s,a))}{\mu ^{2}}-\frac{2d(s)\pi (a|s)A(s,a)\left\langle \tilde{f}^{2}(Q^{2}+\sigma ^{2})\right\rangle _{d\pi }}{\mu ^{3}}\]
We can verify that \( \tilde{f}^{*}(s,a)=\frac{A(s,a)}{Q^{2}(s,a))+\sigma ^{2}(s,a)} \)
is an extrema. 

By substitution, \( \mu (\tilde{f}^{*})=\left\langle \frac{A^{2}}{Q^{2}+\sigma ^{2}}\right\rangle _{d\pi } \).
Also, since \( \sum _{s,a}d(s)\pi (a|s)(\tilde{f}^{*})^{2}(Q^{2}(s,a))+\sigma ^{2}(s,a))=\mu (\tilde{f}^{*}) \),
it follows that :
\begin{equation}
\label{noise}
\Sigma (\tilde{f}^{*})^{2}=\mu (\tilde{f}^{*})-\mu (\tilde{f}^{*})^{2}\, .
\end{equation}
Using \( \Sigma ^{2}/\mu ^{2}\geq 1/\mu (\tilde{f}^{*})-1 \), it follows that
\[
\frac{\Sigma ^{2}}{\mu ^{2}}\geq \frac{1}{\left\langle \frac{A^{2}}{Q^{2}+\sigma ^{2}}\right\rangle _{d\pi }}-1\, .\]
 Our result follows from using the definition of \( \sigma _{0} \).

\emph{The second part of the proof is easy. }

\emph{I'm not sure what the point of the second part is, but maybe seperate
and fill in -John}
\end{proof}
We view this variance trap as problem of exploration. The agent must have access
to a state to improve the policy at that state and the performance measure being
used must be sensitive to improvements at those states.


\section{A Different Performance Measure}

We desire a performance measure that can never have an arbitrarily high signal
to noise ratio when there is a potential for large performance increase (\emph{ie}
when there are large advantages at some states). This alternative performance
measure cannot down weight advantages at unlikely states or unlikely actions.
The performance measure we choose will \emph{require} access to an exploration
policy which can achieve a ``uniform'' distribution over states. This requirement
is both nontrivial and feasible.

A natural candidate for a performance measure is to weight the improvement from
all states and all actions more uniformly, such as 
\[
\omega (\pi )=\sum _{s}m_{e}(s,a)Q_{\pi }(s).\]
 where \( m_{e} \) is some 'exploratory' starting \emph{state-action} distribution.
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. Note that the policy that maximizes \( \omega  \)
also simultaneously maximizes the future reward from every state (hence, \( \eta  \)
is also maximized).

Now let us analyze the improvement conditions for this new performance measure
and its signal to noise properties. The analogous discounted future distribution
of states is:
\[
\tilde{d}_{\pi }(s)\equiv \frac{1}{T}\sum _{\tau =0}^{T}\sum _{s_{0},a_{0}}m_{e}(s_{0},a_{0})\sum _{s}P(s_{\tau }=s|s_{0},a_{0})\, .\]
 Under theorem \ref{th-performance}, \( \omega  \) will improve when the policy
\( \pi  \) is perturbed towards \( f \) if: 
\[
\left\langle A,f\right\rangle _{\tilde{d}\pi }>0\]
 , where, crucially, the metric uses \( \tilde{d}_{\pi }(s) \) instead of \( d_{\pi }(s) \).

The following theorem shows that there exists a direction in which improvement
of \( \omega  \) can always be detected (with a policy independent bound),
unless the policy has performance close to the globally optimal policy.

\begin{thm}
Assume that samples \( s,a \) are sampled from \( \tilde{d}(s)\pi (a|s) \)
and that the unbiased Monte Carlo estimates \( \hat{Q}(s,a) \) of \( Q(s,a) \)
have variance \( \sigma ^{2}(s,a) \). Let \( \sigma _{\infty }=\max _{s,a}\sigma (s,a) \).
If the improvement direction \( f \) is the true advantages \( A \), then
the noise to signal ratio is bounded by: 

\[
\Sigma ^{2}/\mu ^{2}\leq \frac{\sigma ^{2}_{\infty }}{\left\langle A,A\right\rangle _{\tilde{d}\pi }}\, .\]
 Further, the if \( \eta ^{*} \) is the optimal possible average reward and
\( m_{-}=\min _{s,a}m_{e}(s,a) \), then 
\[
|\eta -\eta ^{*}|^{2}\leq \frac{\left\langle A,A\right\rangle _{\tilde{d}\pi }}{m^{2}_{-}}\, .\]

\end{thm}
Note that for the uniform distribution \( m_{-}=1/(\#\textrm{ of states}) \),
whereas in the theorem \ref{sig_noise_lower}, the related term could be arbitrarily
smaller, depending on the policy. Similar to the previous result, the noise
to signal ratio could be high if \( \left\langle A,A\right\rangle _{\tilde{d}\pi } \)
is small. \emph{However, small \( \left\langle A,A\right\rangle _{\tilde{d}\pi } \)
forces the policy to have close to optimal performance, unlike the previous
situation for small \( \left\langle A,A\right\rangle _{\tilde{d}\pi } \).}

\begin{proof}
Using \( f=A \), the mean is
\[
\mu =\sum _{s,a}\tilde{d}(s)\pi (a|s)A^{2}(s,a)\]
 and using equation \ref{variance}, the variance of an estimate can be bounded
by
\begin{eqnarray}
\sigma ^{2} & \leq  & \sum _{s,a}\tilde{d}(s)\pi (a|s)\sigma ^{2}(s,a)A^{2}(s,a)\\
 & \leq  & \sigma ^{2}_{\infty }\sum _{s,a}\tilde{d}(s)\pi (a|s)A^{2}(s,a)\\
 & = & \sigma ^{2}_{\infty }\left\langle A,A\right\rangle _{\tilde{d}\pi }\, .\label{var_bound} 
\end{eqnarray}
 The first result follows using \( \sigma ^{2}/\mu ^{2}\leq \sigma ^{2}_{\infty }/\mu ^{2} \).
 

\emph{outline:} The second part follows by bounding \( A_{\infty } \) (the
largest advantage). Then it is straightforward to show if the maximum advantage
is \( A_{\infty } \) then the optimal payoff can be no greater then \( A_{\infty }T \)
over the current policy. 
\end{proof}
What does this imply about the number of samples \( \hat{Q}(s,a) \)? Consequently,
the variance will decrease like \( \frac{1}{k} \) where \( k \) is the number
of samples. Let \( X=\frac{1}{k}\sum _{i=1}^{k}\hat{Q}(s,a)\tilde{f}(s,a) \).
Applying Chebyshev's inequality implies: 
\[
\Pr (|X-\mu |>\mu )\leq \frac{\sigma ^{2}_{\infty }}{k\left\langle A,A\right\rangle _{\tilde{d}\pi }}\]
 We can do better than Chebyshev's inequality using the independence of the
\( \hat{Q}(s,a) \). In particular, assume that \( Q(s,a)\in [0,R_{\textrm{max}}] \).
Then, the Hoeffding bound states: 
\[
\Pr (|X-\mu |>\mu )\leq e^{-\frac{k\mu ^{2}}{R_{\textrm{max}}^{2}}}\]
In either case, we know that an advantage of size \( A \) will imply a bias
of size at least \( \mu =\frac{A}{nT} \). Here \( n \) is the number of state-actions,
\( T \) is the number of timesteps, and we are assuming a uniform distribution.
This will, in turn, imply that at most \( k=\frac{n^{2}T^{2}}{A^{2}} \) samples
are required in order to estimate the ``right'' direction with high confidence.
This quantity is polynomial in all parameters and so (in general) convergences
far faster than policy gradient estimates.


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

For an arbitrary \( f \), optimizing \( \omega (\pi ) \) can have disastrous
effects on the average reward, \( \eta _{\pi } \). To see this consider a one
parameter function \( f(s,a) \) for which \( f(s,a)=A(s,a) \) on all states
commonly visited under \( d(s)\pi (a|s) \) and \( f(s,a)=-A(s,a) \) on all
other states. The advantages can be essentially independent which implies that
given sufficient ``other states'', optimization according to \( \omega (\pi ) \)
will be directly opposed to opimization of \( \eta _{\pi } \). Therefore, optimizing
according to \( \omega (\pi ) \) for arbitrary \( f \) is dangerous.

There exists \( f(s,a) \) for which optimizing \( \omega (\pi ) \) always
agrees with optimizing \( \eta _{\pi } \). To see this, simply make \( f(s,a)=A(s,a) \)
everywhere. Then, optimization under any distribution over state-actions will
always be in the same direction. Of course, in practice we will not use \( f(s,a)=A(s,a) \).

Intuitively, when optimizing according to \( \omega (\pi ) \), we need a family
of \( f \) which is sufficiently adaptive that optimization on the set of frequently
visited states (under \( d(s)\pi (a|s) \)) is (mostly) orthogonal to optimization
under the uniform state distribution given by \( \omega (\pi ) \). Since the
goal state distribution is unknown in advance, this strongly suggests that nonparametric
function approximation techniques should be applied. The next theorem essentially
states that a reasonable notion of sufficiently adaptive function approximation
will work. 

Let us first consider the signal to noise under a general state-action distribution
\( \nu (s,a) \). The previous condition only considered the case where \( f=A \).
Now we consider the case when \( f \) is \( \varepsilon  \) close to \( \tilde{A} \). 

\emph{This theorem sort of bothers me, but I'm not certain why. Maybe it's because
there are more general families of \( f \) which will work. Why does variance
go to \( \infty  \) when \( \varepsilon  \) goes to 0? -John}

\begin{thm}
Assume that samples \( s,a \) are sampled from \( \tilde{d}(s)\pi (a|s) \)
and that the unbiased Monte Carlo estimates of \( Q(s,a) \) have variance \( \sigma ^{2}(s,a) \).
Let \( \sigma _{\infty }=\max _{s,a}\sigma (s,a) \). If \( \left\langle f-A,f-A\right\rangle _{\nu }<\varepsilon ^{2} \)
and \( \left\langle A,A\right\rangle _{_{\nu }}>2\varepsilon ^{2} \), then:
\[
\frac{\Sigma ^{2}}{\mu ^{2}}\leq \frac{2\sigma ^{2}_{\infty }}{\varepsilon ^{2}}\, .\]

\end{thm}
\begin{proof}
Using equation \ref{var_bound}, we have:
\[
\frac{\Sigma ^{2}}{\mu ^{2}}\leq \frac{\sigma ^{2}_{\infty }\left\langle A,A\right\rangle _{\nu }}{\left\langle A,f\right\rangle _{\nu }}\, .\]
Since \( \left\langle f-A,f-A\right\rangle _{\nu }<\varepsilon ^{2} \) and
\( \left\langle A,A\right\rangle _{_{\nu }}>2\varepsilon ^{2} \), then \( \left\langle A,f\right\rangle _{\nu }>\varepsilon ^{2} \).
The result follows from combining inequalities.
\end{proof}
Intuitively, as long as \( \left\langle A,A\right\rangle _{\nu } \) is large,
then any \( f \) that is \( \varepsilon  \)-close to \( A \) will have a
\( 1/\varepsilon ^{2} \) bound on its noise to signal ratio. 

Now, let us consider the consequences for improvement under both performance
measures. Consider \( f \) satisfying: 
\begin{equation}
\label{eps_close}
\left\langle f-A,f-A\right\rangle _{\tilde{d}\pi }+\left\langle f-A,f-A\right\rangle _{d\pi }\leq \varepsilon ^{2}
\end{equation}
 , which is the set of vectors that is \( \varepsilon  \)-close to \( A \)
under both \( \tilde{d}\pi  \) and \( d\pi  \). For these vectors, we will
either be able to detect improvement of \( \omega  \) or the policy has near
optimal performance. Further, we will either be able to detect an increase of
\( \eta  \) or we are in the situation where the signal to noise ratio is small
(and so improving \( \eta  \) was hard anyways). More precisely, for the \( \varepsilon  \)-close
\( f \),:

\begin{enumerate}
\item If \( |A|_{\tilde{d}\pi }>2\varepsilon  \), then \( f \) will improve \( \omega  \)
and detection of this improvement is feasible (\( \Sigma /\mu \leq \frac{\sigma _{\infty }}{\varepsilon } \)).
Else if \( |A|_{\tilde{d}\pi }\leq 2\varepsilon  \), then although detection
of improvement is not feasible, the policy is close to optimal (\( |\eta -\eta ^{*}|\leq \frac{2\varepsilon }{(1-\gamma )m_{-}} \)).
\item If \( |A|_{d\pi }>2\varepsilon  \), then \( f \) will improve \( \eta  \)
and detection of this improvement is feasible (\( \Sigma /\mu \leq \frac{\sigma _{\infty }}{\varepsilon } \)).
Else if \( |A|_{d\pi }\leq 2\varepsilon  \), then detection could be difficult
(since \( \Sigma /\mu \leq \frac{\sigma _{0}}{2\varepsilon }-1 \) by theorem
\ref{sig_noise_lower}).
\end{enumerate}
The big picture is that we have lost very little by improving \( \omega  \).
The only case where \( \eta  \) might decrease when \( \omega  \) improves
is when \( |A|_{d\pi } \) is small. However, by theorem \ref{sig_noise_lower},
this was the case where it is difficult to improve \( \eta  \) anyways due
to the high variance, so improvement was an unreasonable expectation. The flip
side is that we will not be able to detect a decrease of \( \eta  \) , for
small changes to the policy (in essence, \emph{}this is the 'plateau' case).
However, what we have gained is that we can always improve \( \omega  \) until
the policy is close to optimal (and \( \eta  \) along the way, when feasible).

Note that for a fixed architecture, it will not necessarily be possible to satisfy
equation \ref{eps_close}. Thus, we need to consider function approximation
schemes that are are rich enough to satisfy this quantity. Intuitively, we hope
that policy improvement at unlikely states does not clash with improvement at
likely states (when feasible, as discussed above). Further, we seek to eventually
find the optimal policy. \emph{This leads into non-parametric schemes!}

\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})\} \).
The exact gradient of the average reward is:
\begin{equation}
\label{av_gradient}
\nabla \eta (\pi )=\sum _{s,a}d_{\pi }(s)\nabla \pi (a|s)Q_{\pi }(s,a)
\end{equation}
 (see \cite{sutton99policy, marbach98simulation-based}). Using the notation
\( \partial _{sa}\equiv \partial /\partial \theta _{sa} \), we get: 
\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}


Before we address variance issues, we address the important question as to whether
or not the the optimal policy will be found by following the gradient. 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}

\emph{The exact process of how a monte carlo estimate can be formed isn't well
spelled out. This is a first attempt. -John}

In order to determine which direction is the ``right'' direction, we need
to know how to estimate this right direction. This is a surprisingly subtle
problem in the undiscounted average reward case. 

The problem of estimating the average reward given a policy and a reinforced
MDP is similar to the problem of Monte-Carlo integration of an unknown function
with an unknown mixing time. This problem is typically solvable under very general
conditions. Let \( \hat{p}_{s} \) be the observed portion of the time the system
enters the state \( s \) after \( T \) steps and \( p_{s} \) be the expected
number of times the system enters the state \( s \).

The following condition is a statement that every empirically observed state
frequency converges to the exact state frequency at a reasonable rate.
\[
\forall s\, \, \forall \epsilon \, \, \exists T'\, \, \Pr _{\textrm{T step Markov Process}}(|\hat{p}_{s}-p_{s}|\geq \epsilon )\leq e^{-\epsilon ^{2}\frac{T}{T'}}\]


For a finite state space, this condition implies uniform convergence (over all
states simultaneously) at a rate dependent on the size of the state space. This
is a very general condition - even finite deterministic systems have a \( T' \).
Given a reasonable convergence rate (which is a stronger assumption than the
ergodicity assumption) and finite reward values, it is possible to estimate
the average reward \( \eta _{\pi } \) of the policy to some finite precision
in a finite amount of time. Let \( \hat{\eta }_{\pi } \) be the observed average
reward. 

Intuitively, if we run the Markov process for a time long compared to the convergence
time \( T' \), we will obtain an estimate \( \hat{Q}(s,a) \) which consists
of two components, an average reward plus a transient. By subtracting the average
reward, we can gain an (approximately unbiased) estimate of the transient.


\section{Have we thrown the baby out with the bath water?}

\emph{aside: The gist of this section is that following \( \omega  \) does
not hurt us with respect to \( \eta  \), except when we are at a 'plateau'.
For this case, we are screwed anyways with regards to \( \eta  \), so no big
deal.}

\textbf{\emph{aside: It should be easy to come up with a case (as specified
above in point 2) where \( \eta  \) will decrease.}}

\end{document}
