%% This LaTeX-file was created by <jl> Fri Oct 12 22:43:26 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 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 \( \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_{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 \( \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 is: 

\emph{This isn't quite right -John}


\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 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)=\Pr _{\pi ,\textrm{MDP}}(s_{t}=s|s_{0})\Pr _{m_{0}}(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:
\[
<x,x^{\prime }>_{d_{\pi }\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} 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 =\alpha <A,f>_{d_{\pi }\pi }+O(\alpha ^{2})\, .
\end{equation}

\end{thm}
\begin{proof}
The gradient of the discounted average reward from a starting state \( s_{0} \)
chosen according to \( m_{0} \) is:
\begin{equation}
\nabla \eta (\pi )=\nabla E_{s_{0}}J_{\pi }(s_{0})
\end{equation}
 
\[
=E_{s_{0}}\nabla E_{\pi (a|s_{0})}Q_{\pi }(s_{0},a)\]
\[
=E_{s_{0}}\left[ \sum _{a}Q_{\pi }(s_{0},a)\nabla \pi (a|s_{0})+E_{\pi (a|s_{0})}\nabla Q_{\pi }(s_{0},a)\right] \]
\[
=E_{s_{0}}\left[ \sum _{a}Q_{\pi }(s_{0},a)\nabla \pi (a|s_{0})+E_{\pi (a|s_{0})}\nabla \gamma \Pr (s_{1}|s_{0},a)J(s_{1})\right] \]
\[
=E_{s_{0}}\left[ \sum _{a}Q_{\pi }(s_{0},a)\nabla \pi (a|s_{0})+E_{\pi (a|s_{0})}E_{s_{1}|s_{0}a}\gamma \nabla J(s_{1})\right] \]
\[
=\sum _{t=0}^{\infty }\gamma ^{t}E_{s_{t}}\left[ \sum _{a}Q_{\pi }(s_{t},a)\nabla \pi (a|s_{t})\right] \]
 
\begin{equation}
\label{disc-gradient}
=\frac{1}{1-\gamma }E_{s\sim d_{\pi }(s)}\left[ \sum _{a}Q_{\pi }(s,a)\nabla \pi (a|s)\right] 
\end{equation}


\emph{Note: the lack of normalizability shows up here as well with the unavoidable
\( \frac{1}{1-\gamma } \) term. -John}

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)=<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 gradient (equation \ref{disc_gradient}) can be written in the form:
\[
\frac{\partial \eta }{\partial \theta }=\frac{1}{1-\gamma }E_{s\sim d_{\pi }(s)}\left[ \sum _{a}\frac{\pi (a|s)}{\pi (a|s)}Q_{\pi }(s,a)\frac{\partial \pi (a|s)}{\partial \theta }\right] \]
\[
=\frac{1}{1-\gamma }E_{s,a\sim d_{\pi }(s),\pi (a|s)}\left[ Q_{\pi }(s,a)\frac{1}{\pi (a|s)}\frac{\partial \pi (a|s)}{\partial \theta }\right] \]
\[
=\frac{1}{1-\gamma }\left\langle \frac{\nabla \pi }{\pi },Q\right\rangle _{d\pi }\, .\]
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{\partial \log \pi (a|s)}{\partial \theta })
\end{eqnarray*}
 and so \( f=\frac{\partial \log \pi }{\partial \theta } \). 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 \( <f,Q>_{d\pi } \). 

Thus, 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{.}
As stated in the previous section, the variance in obtaining the correct sign
can be large.


\section{A Different Performance Measure}

\emph{I think our thoughts might have diverged in our previous section 5\&6.
You said you failed to see the point in the second part of the previous Thm.
5.1 (the \( |\eta -\eta ^{*}|^{2}\leq \frac{\left\langle A,A\right\rangle _{\tilde{d}\pi }}{m^{2}_{-}} \)
part). This second part, which is now in section 5.2, is the hammer for bashing
gradient methods. You made an odd comment about polynomial samples needed for
\( \omega  \), which seemed to miss the point?}

\emph{Also, I slightly changed this section (proofs, thms., etc.) and did not
assume the particular choice \( f=A \) when constructing a lower bound. This
assumption seemed a bit odd this early on.} -\emph{Sham}

As discussed in section 3, 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. 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 \( m_{0} \)), 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. \emph{Hence,
maximizing \( \omega  \) also maximizes \( \eta  \).}

The next 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 \( m_{e} \) different from \( m_{0} \) 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 \) }

Now let us consider for an arbitrary \( m_{e} \) how difficult is it to improve
\( \omega  \), with the special case that \( \omega =\eta  \) when \( m_{e}=m_{0} \).
More precisely, 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. 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 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 \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 toward \( f \) if: 
\[
\left\langle Q,\tilde{f}\right\rangle _{\nu }>0\]
 , where \( \nu (s,a)=\tilde{d}_{\pi }(s)\pi (a|s) \) which is based on \( m_{e} \)
rather than on \( m_{0}(s) \).

\begin{thm}
\label{var_mu}Assume that samples \( s,a \) are drawn from \( \nu (s,a)\equiv \tilde{d}(s)\pi (a|s) \)
and assume that \( \left\langle \tilde{f},\tilde{f}\right\rangle _{\nu }=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 _{0}=\max _{s,a}\sigma (s,a) \)
and \( \sigma _{\infty }=\max _{s,a}\sigma (s,a) \). Then an unbiased estimate
of \( <A,f> \) is given by \( \hat{Q}(s,a)\tilde{f}(s,a) \) and the variance
of this estimate is bounded by:
\[
\sigma ^{2}_{0}-\left\langle A,\tilde{f}\right\rangle ^{2}_{\nu }\leq \Sigma ^{2}\leq \sigma ^{2}_{\infty }+R^{2}_{max}\, .\]
 
\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} & = & \left\langle \tilde{f}^{2}\hat{Q}^{2}\right\rangle _{\nu }-\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}_{0}\sum _{s,a}\nu (s,a)\tilde{f}^{2}(s,a)-\mu ^{2}\\
 & = & \sigma ^{2}_{0}-\mu ^{2}
\end{eqnarray*}
 where have used the unit length of \( \tilde{f} \). We can upper bound \( \sigma  \)
as follows:
\begin{eqnarray*}
\sigma ^{2} & \leq  & \sum _{s,a}\nu (s,a)\tilde{f}^{2}(Q^{2}(s,a)+\sigma ^{2}(s,a))\\
 & \leq  & (\sigma ^{2}_{\infty }+R^{2}_{max})\sum _{s,a}\nu (s,a)\tilde{f}^{2}(s,a)\\
 & = & \sigma ^{2}_{\infty }+R^{2}_{max}\, .
\end{eqnarray*}
 
\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 =\left\langle A,\tilde{f}\right\rangle _{\nu } \).
The difficulty of this is determined by how much larger the ``signal'' is
than the ``noise'', \emph{ie} the variance of the estimate of the signal.

\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}_{0}}{\left\langle A,A\right\rangle _{\nu }}-1\, .\]

\end{cor}
\begin{proof}
The \( \tilde{f} \) maximizes \( \left\langle A,\tilde{f}\right\rangle  \)
also minimizes \( \frac{\Sigma ^{2}}{\mu ^{2}} \) (subject to the normalization
constraint on \( \tilde{f} \)). This this occurs when \( \tilde{f}=\frac{A}{\sqrt{\left\langle A,A\right\rangle _{\nu }}} \)
. Substitution leads to the result.
\end{proof}
Lets consider the special case of \( \omega =\eta  \) when \( m_{e}=m_{0} \)
and \( \nu  \) is defined through \( m_{0} \). If all the large advantages
are at states that are visited infrequently then \( \left\langle A,A\right\rangle _{\nu } \)
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 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 _{\nu } \)
is small, eventhough \( \left\langle A,A\right\rangle _{\nu } \) was large
to begin with. 

Alternatively, 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. Let c 

\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
\[
\Pr (\textrm{sign}(X)=\textrm{sign}(\left\langle A,\tilde{f}\right\rangle _{\nu }))\leq \frac{\sigma ^{2}_{\infty }+R_{max}^{2}}{k\left\langle \tilde{f},A\right\rangle _{\nu }^{2}}\]

\end{cor}
\begin{proof}
Applying Chebyshev's inequality implies, \( \Pr (|X-\mu |>\mu )\leq \frac{\Sigma ^{2}}{k\mu ^{2}} \).
The result follows from theorem \ref{var_mu}. 
\end{proof}
\emph{I am a bit confused by the following Hoeffding bound. Where did the \( \sigma _{\infty } \)
go? -Sham}

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.

\emph{I disagree with this last argument (from the previous draft). The variance
of both policy gradients and our estimates look {*}equally bad{*} when \( \left\langle A,A\right\rangle _{??} \)
under their respective metric is small (needing \( \frac{n^{2}T^{2}}{A^{2}} \)samples).
The point of that \( |\eta -\eta ^{*}| \) statement is to ask how close are
we to the optima when we have a hard time estimating if \( f \) improves \( \omega  \).
For \( \eta  \), the answer is we could be very far. For \( \omega  \), the
answer is that we must be close to the optima for a good \( m_{e} \). The next
section discusses this. -Sham}


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

The previous section suggested that if \( <A,A>_{\nu } \) 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} \( m_{e} \))
being used. The important question we now address is how difficult is it to
determine if \( f \) improves a sub-optimal policy. 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  \). 

First, let us provide a theorem as to how far the policy is from optimal in
terms of how large \( \left\langle A,A\right\rangle _{\nu } \) is.

\begin{thm}
Let \( J^{*}(s) \) be the optimal reward starting from state \( s \) and let
\( \nu _{0}=\min _{s,a}\nu (s,a) \) for some state-action distribution \( \nu  \).
Then 
\begin{equation}
\label{sub_optimal}
|J(s)-J^{*}(s)|\leq \sqrt{T\frac{\left\langle A,A\right\rangle _{\nu }}{\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 } \).
By induction, we can do this at most for \( T \) steps, and so \( |J(s)-J^{*}(s)|<TA_{\infty } \)
(\emph{this is proved in some book)}. The largest possible \( A_{\infty } \)
is when \( <A,A>_{\nu }=\nu _{0}A_{\infty }^{2} \). \emph{I'll construct an
example to show this bound is tight in the appendix.}
\end{proof}
Note that this implies for any distribution \( m \) and for \( \omega (\pi )=E_{m}\{J_{\pi }(s)\} \),
\begin{equation}
\label{sub_optimal_2}
|\omega -\omega ^{*}|\leq \sqrt{T\frac{\left\langle A,A\right\rangle _{\nu }}{\nu _{0}}}
\end{equation}
 where \( \nu  \) is arbitrary (not necessarily based on \( m \)).

This bound elucidates the problems with using \( m_{0} \) as the starting distribution.
Let us consider the case in which \( \left\langle A,A\right\rangle _{\nu } \)
is small, so estimating if \( f \) or \( -f \) improves the policy will be
difficult, by corollary \ref{sig_noise}. For this \( m_{0} \), the induced
state-action distribution can have a small \( \nu _{0} \), so \( \left\langle A,A\right\rangle _{\nu }/\nu _{0} \)
could be large (even if \( \left\langle A,A\right\rangle _{\nu } \) 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 those important states (making
improvement difficult), but the presence of large advantages leaves open the
possibility that the policy is significantly sub-optimal. 

Instead, let us consider an \( m_{e} \) that does not allow \( \nu _{0} \)
to be extremely small. This will force each \( J(s) \) to be close to optimal
if \( \left\langle A,A\right\rangle _{\nu } \) is small. An additional desired
property is that the number of samples needed to improve the performance measure
must be small. The number of samples must depend on the direction \( f \) being
followed, and there are clearly high variance choices (those that ``alias''
states). \emph{However, the following theorem states that there exist \( f \)
such that local improvement can be evaluated with \( O(1/\varepsilon ) \) samples
when the policy could be at most \( O(1/\sqrt{\varepsilon }) \) away from optimal.}
Note that this local improvement of \( J(s) \) is with respect to \( m_{e} \).

\begin{cor}
\label{improvement} Under the assumptions and sampling model of theorem \ref{var_mu},
we construct the estimate \( X=\frac{1}{k}\sum _{i=1}^{k}\hat{Q}(s,a)\tilde{f}(s,a) \).
Then if \( \left\langle A,A\right\rangle _{\nu }\leq \varepsilon  \) then
\[
|J(s)-J^{*}(s)|\leq \sqrt{\frac{T\varepsilon }{\nu _{0}}}\]
else there exist \( \tilde{f} \), namely those with \( \left\langle \tilde{f},A\right\rangle ^{2}_{\nu }>\varepsilon  \),
such that

\[
\Pr (\textrm{sign}(X)=\textrm{sign}(\left\langle A,\tilde{f}\right\rangle _{\nu }))\leq \frac{\sigma ^{2}_{\infty }+R_{max}^{2}}{k\varepsilon }\, .\]

\end{cor}
\begin{proof}
If \( \left\langle A,A\right\rangle \leq \varepsilon  \), the second condition
follows from theorem \ref{sub_optimal}. Else if \( \left\langle A,A\right\rangle _{\nu }>\varepsilon  \),
then for \( \tilde{f}=A/\sqrt{\left\langle A,A\right\rangle _{\nu }} \) , \( \left\langle \tilde{f},A\right\rangle _{\nu }^{2}=\left\langle A,A\right\rangle _{\nu }>\varepsilon  \),
so \emph{}such \( \tilde{f} \) exist. Using \( \left\langle \tilde{f},A\right\rangle _{\nu }^{2}>\varepsilon  \)
with corollary \ref{sample_size}, the second case follows. 
\end{proof}
Thus if we use an \( m_{e} \) such that \( \nu _{0} \) is not too small, then
each \( J(s) \) will be \( \sqrt{\frac{T\varepsilon }{\nu _{0}}} \) near-optimal,
when \( \left\langle A,A\right\rangle _{\nu }\leq \varepsilon  \). By equation
\ref{sub_optimal_2}, it follows that \( \eta  \) will also be \( \sqrt{\frac{T\varepsilon }{\nu _{0}}} \)
near-optimal. If we not guaranteed to be this close to optimal, then there exists
a set of directions such that determining if one of these directions improves
\( J(s) \) (under \( m_{e} \)) needs at most \( O(1/\varepsilon ) \) samples.
\emph{The same cannot be said of policy gradients when the policy is significantly
sub-optimal where high variance estimates could occur for a significantly sub-optimal
policy.} 


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

\emph{I weakened this section to essentially state that, in principle, it is
possible to 'mostly' improve \( \eta  \) when \( \omega  \) improves. We can
discuss how in the next section. -Sham}

The previous section suggested that as long as \( \eta  \) is not guaranteed
to be \( \sqrt{\frac{T\varepsilon }{\nu _{0}}} \)-near optimal, then there
is the possibility of improving the value functions on average, under \( m_{e} \),
with \( O(1/\varepsilon  \)) samples. This hinges on finding directions such
that \( \left\langle \tilde{f},A\right\rangle _{\nu }^{2}>\varepsilon  \) when
\( \left\langle A,A\right\rangle _{\nu }>\varepsilon  \). Clearly, the direction
\( \tilde{f}\propto A \) and \( \tilde{f}\propto -A \) satisfy this criterion.
In the next section, we discuss how to find such \( \tilde{f} \). Before this,
we will address the important issue of what have lost in improving \( \omega  \)
instead of \( \eta  \), which is what we wanted to maximize to begin with.
\emph{Although, at the end-point of the optimization procedure, we will have
found a policy with return close to \( \eta ^{*} \), an important question
is can \( \eta  \) decrease along the way until we find 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 starting
from \( m_{e} \) and \( f(s,a)=-A(s,a) \) on all other states. This will force
\( \left\langle f,A\right\rangle _{\nu }>0 \) for the \( \nu  \) implied by
\( m_{e} \). However, if the state distribution from \( m_{0} \) has high
probability at states where \( f(s,a)=-A(s,a) \) then \( \eta  \) can decrease.
Thus, although ultimately the policy will be near-optimal, improvement of \( \omega  \)
will not always imply improvement of \( \eta  \). 

However, 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 the estimation problem
of finding \( f(s,a)=A(s,a) \) everywhere is infeasable, which we discuss later. 

In general, forcing \( \eta  \) to improve at every step is impractical , since
determining if any \( f \) or \( -f \) improves the policy can be arbitrarily
difficult for a policy with payoff far from optimal. These difficult cases are
when the agent rarely visits states with large advantages, so the reward surface
is at a plateau. \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.

Let \( \nu  \) and \( \tilde{\nu } \) be the distributions implied by \( m_{0} \)
and \( m_{e} \) respectively and let us consider the case in which we are not
guaranteed to be \( \sqrt{\frac{T\varepsilon }{\nu _{0}}} \)-close to the optimal
policy, \emph{ie} \( \left\langle A,A\right\rangle _{\tilde{v}}\leq \varepsilon  \).
Corollary \ref{improvement} states that either we can determine if \( \tilde{f} \)
or \( -\tilde{f} \) improves \( \omega  \) with \( O(1/\varepsilon  \)) samples,
for normalized \( \tilde{f} \) with \( \left\langle \tilde{f},A\right\rangle _{\tilde{v}}^{2}>\varepsilon  \).
As far as \( \eta  \) is concerned, let us consider the case in which the agent
also visits states with large advantages under \( m_{0} \), \emph{ie} \( \left\langle A,A\right\rangle _{\nu }>\varepsilon  \)
(\emph{ie} the non-problematic case). Then there exist normalized \( \tilde{f} \)
such that \( \left\langle \tilde{f},A\right\rangle _{\nu }^{2}>\varepsilon  \)
(for instance \( \tilde{f}=A/\sqrt{\left\langle A,A\right\rangle _{\nu }} \))
such that we detect improvement with \( O(1/\varepsilon ) \) samples. Further,
there are \( \tilde{f} \) that satisfy \emph{both} of these conditions, \( \left\langle \tilde{f},A\right\rangle _{\nu }^{2}>\varepsilon  \)
and \( \left\langle \tilde{f},A\right\rangle _{\tilde{v}}^{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 \( m_{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. We
now discuss how to find these good directions \( f \).


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

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. 

\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.

\end{document}
