%% This LaTeX-file was created by <jl> Wed Oct 31 12:18:43 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\@}
%% Special footnote code from the package 'stblftnt.sty'
%% Author: Robin Fairbairns -- Last revised Dec 13 1996
\let\SF@@footnote\footnote
\def\footnote{\ifx\protect\@typeset@protect
    \expandafter\SF@@footnote
  \else
    \expandafter\SF@gobble@opt
  \fi
}
\expandafter\def\csname SF@gobble@opt \endcsname{\@ifnextchar[%]
  \SF@gobble@twobracket
  \@gobble
}
\edef\SF@gobble@opt{\noexpand\protect
  \expandafter\noexpand\csname SF@gobble@opt \endcsname}
\def\SF@gobble@twobracket[#1]#2{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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 function approximation
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 a 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 detail 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 5, 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 6, 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_{\textrm{max}}] \),
and \( P \) is the transition model in which \( p_{ij}^{a} \) is the transition
probability from state i to j under action \( a \). 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 can
not be accurate. Define a new reinforcement learning problem which is identical
to \ref{fig1} except with no reward on the goal transition. The gradient estimate
provided by any state sequence which does not visit the goal state will be identical
for both reinforcement learning problems. However, the altered reinforcement
learning problem has zero gradient and so the gradient direction returned 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).}

\emph{Sham, I don't understand the notation in this caption. What is s? What
is ``1''? -John}
\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{Conditions for 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 in the space of state-actions. 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 \( \mu  \), 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 ,s_{0}\sim \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, note that the expectation:
\[
E_{d_{\pi }\pi }xx'=\sum _{sa}d_{\pi }(s)\pi (a|s)x(s,a)x^{\prime }(s,a)\]
 can be seen as an inner product for vectors \( x \) and \( x^{\prime } \)
in the state-action space under the state-action distribution \( d_{\pi }(s)\pi (a|s) \).

\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 _{s}\sum _{a}\mu _{e}(s,a)Q_{\pi }(s,a)\]
 where \( \mu _{e} \) is some 'exploratory' starting \emph{state-action} distribution.
Note that \( \omega =\eta  \) for the special case when \( \mu _{e}=\mu (s)\pi (a|s) \).
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 it is 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 ^{2}) \) samples
when the state values are not \( \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 a \( \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
(see section \ref{sec-monte}), it is reasonable to suppose that we can calculate
a quantity \( \hat{Q}_{\pi }(s,a) \) which is a nearly unbiased estimate of
\( Q_{\pi }(s,a) \). Given that all rewards are in some interval \( [0,R_{\textrm{max}}] \),
these estimates will have some finite variance, \( \sigma (s,a)\leq \frac{R_{\textrm{max}}^{2}}{4} \).
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 ,(s_{0},a)\sim \mu _{e}}\Pr (s_{t}=s|s_{0},a)\, .\]
 Under theorem \ref{th-performance}, \( \omega  \) will improve when the policy
\( \pi  \) is perturbed toward \( f \) if \( E_{\nu }Q\tilde{f}>0 \). Here
\( \nu (s,a) \) is an arbitrary distribution over state-actions.

\emph{Sham this last statement is \_NOT\_ true right now and needs to be fixed,
either by generalizing 4.1 (preferred) or weakening the statement. I'll let
you handle it.}

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

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 \exp (-\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}
Note that if \( E_{\nu }Af \) is large then few samples are needed. In particular,
the number of samples required to achieve a fixed error rate is \( O\left( \frac{R_{\textrm{max}}^{2}}{(E_{\nu }Af)^{2}}\right)  \).
This suggests that a uniform distribution is sensible since it will allow \( E_{\nu }Af \)
to have a significant value as long as any advantage is large. The next section
formalized this need for 'exploration'. 

\emph{I don't understand or agree with the comments that were previously here.
The previous statement 'polynomial in all the parameters' was very weak, since
the scalar \( A \) was one of the parameters (which wasn't defined).} \textbf{\emph{}}\emph{One
of these parameters cannot be A, since A could scale with \( n \) (as in example
1). Policy gradients might converge 'slower' (it's a tricky argument to make
at this point) but at least we are improving what we are interested in. It is
a bit rude at this point to say that this different quantity is easy to improve,
since, after all, it isn't the quantity we are interested in. The next section
formalizes a criticism. -Sham}

\emph{I don't see why \( A \) is a scalar. It looks like a vector to me. I
think it is worth pointing out that the number of samples behaves well as a
function of \( \frac{1}{E_{\nu }Af} \) and \( R_{\textrm{max}} \). See if
the current statement is sensible. -John}


\subsection{Why is exploration necessary?}

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?''

We measure the degree of sub-optimality by: 
\[
\varepsilon =\max _{s}|J(s)-J^{*}(s)|\]
which is the standard \( \infty  \)-measure used in dynamic programming (see
\cite{bertsekas-book}). It follows that \( |\eta -\eta ^{*}|\leq \varepsilon  \).
Clearly, increasing an average of \( J(s) \), under a distribution that has
nonzero weight for every state, will eventually decrease this measure , and
force the policy to be at least \( \varepsilon  \) close to optimal. 

The following theorem addresses the difficulty of improving \( \omega  \) for
an \( \varepsilon  \) sub-optimal policy. Let \( \theta  \) be the angle between
the vectors \( A \) and \( f \) in state action space. Then the inner product
satisfies \( E_{\nu }Af=\sqrt{(E_{\nu }A^{2})(E_{\nu }f^{2})}\cos \theta  \).

\begin{thm}
\label{thm_samp_opt}Let \( \cos \theta =\frac{E_{\nu }Af}{\sqrt{(E_{\nu }A^{2})(E_{\nu }f^{2})}} \),
\( \varepsilon =\max _{s}|J(s)-J^{*}(s)| \), and \( \nu _{0}=\min _{s,a}\nu (s,a) \).
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) \) satisfies:
\[
\Pr (\textrm{sign}(X)=\textrm{sign}(E_{\nu }Af))\leq \exp (-k\varepsilon ^{2}\nu _{0}\frac{2(1-\gamma )^{2}\cos ^{2}\theta }{R_{\textrm{max}}^{2}})\]

\end{thm}
\begin{proof}
First, let us bound \( \varepsilon  \) in terms of how large \( E_{\nu }A^{2} \)
is. Let \( A_{\infty }=\max _{s,a}A(s,a) \). By definition of the advantages,
if we deviate from the current policy at any state \( s \) by taking action
\( a \), we gain, on average, \( A(s,a) \) future reward. The change in \( J_{\pi }(s) \)
when we switch to any new policy \( \pi ^{\prime } \) is \( E_{\mu _{e},\pi ^{\prime }}(\sum _{t}\gamma ^{t}A(s_{t},a_{t})) \),
since the new policy deviates from the old at every time step. Each term in
this sum is at most \( A_{\infty } \), so for any policy \( J_{\pi ^{\prime }}(s)-J_{\pi }(s)\leq \frac{A_{\infty }}{1-\gamma } \).
Hence, 
\begin{equation}
\label{max_improve}
\varepsilon \leq \frac{A_{\infty }}{1-\gamma }\, .
\end{equation}
The largest possible \( A_{\infty } \) for a given \( E_{\nu }A^{2} \) satisfies
\( E_{\nu }A^{2}=\nu _{0}A_{\infty }^{2} \), so \( A_{\infty }\leq \sqrt{\frac{E_{\nu }A^{2}}{\nu _{0}}} \)
and
\begin{equation}
\label{sub_optimal}
\varepsilon \leq \frac{1}{1-\gamma }\sqrt{\frac{E_{\nu }A^{2}}{\nu _{0}}}\, .
\end{equation}
 By definition of \( \theta  \), \( (E_{\nu }Af)^{2}=E_{v}(A^{2})E_{\nu }(f^{2})\cos ^{2}\theta \geq (1-\gamma )^{2}\nu _{0}\varepsilon ^{2}\cos ^{2}\theta  \).
(for normalized \( f \)), and the result follows using corollary \ref{sample_size}.
\end{proof}
Thus, when the policy is \( \varepsilon  \)-near optimal, we need at most \( O\left( \frac{1}{\varepsilon ^{2}\nu _{0}}\right)  \)
samples to estimate the gradient. If we use a \( \mu _{e} \) that implies a
uniform state-action distribution, then we need at most \( O\left( \frac{n}{\varepsilon ^{2}}\right)  \)
(where \( n \) is the number of state-actions). 

The same cannot be said for policy gradients since \( \nu _{0} \) can be arbitrarily
small, implying that arbitrarily many samples might be necessary. Essentially,
\( \varepsilon  \) can be large which implies that there must be large advantages
(by equation \ref{max_improve}), but the large advantages could be hidden from
the agent \emph{}in the sense that \emph{}\( E_{\nu }(A^{2}) \) can be small
due to the skewed state action distribution. Thus, for large \( \varepsilon  \),
the signal to noise could be large (by corollary \ref{sig_noise}) implying
many more samples are necessary.

Although we ultimately seek to improve \( \eta  \), the appropriate performance
measure to use is one which weights \( J(s) \) more uniformly. This stems from
the fact that if \( |J(s)-J^{*}(s)| \) is large for just one state, then all
other states stand to gain significant improvement. Intuitively, using \( \omega  \)
is analogous to an incremental version of policy iteration.


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

What has been lost by improving \( \omega  \) instead of \( \eta  \)? Our
real goal \emph{is} improving \( \eta  \). Note that the endpoint of improving
\( \omega  \) will be a policy which is optimal for criteria \( \eta  \).
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 a \( f \) which
improves the policy under the the distribution \( d_{\pi }(s) \) yet \( -f \)
improves the policy under \( \tilde{d}_{\pi }(s) \). Such \( f \) can exist
when the initial distributions \( \mu  \) and \( \mu _{e} \) differ significantly.
For these \( f \), optimizing according to \( \omega  \) will decrease \( \eta  \).
There \emph{always} exist \( f(s,a) \) for which optimizing \( \omega (\pi ) \)
improves \( \eta (\pi ) \): consider \( 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. This is why we considered \( \omega  \)
to begin with. Let \( \nu  \) be the distributions implied by \( \mu  \),
\emph{ie} \( d_{\pi }\pi  \). The problematic cases for improving \( f \)
are when \( E_{\nu }(A^{2}) \) is small. The number of samples required to
determine if \( f \) improves is \( O\left( \frac{1}{(E_{\nu }Af)^{2}}\right)  \).
Using the angle between \( A \) and \( f \) determined by \( \nu  \), the
number of samples required is \( O\left( \frac{1}{\cos ^{2}\theta E_{\nu }A^{2}}\right)  \).
Thus, if \( E_{\nu }(A^{2}) \) is not extremely small then it is possible to
determine if \( f \) or \( -f \) improves \( \eta  \).

We now focus on the important \( \cos \theta  \) dependence, and show how it
is possible to improve both \( \omega  \) and \( \eta  \) in nonproblematic
case.


\section{Policy Improvement}

The question now is how to choose an \( f \) to improve the policy. An obvious
method is to chose some \( f \) randomly and try to improve the policy the
policy with it. The infamous 'curse of dimensionality' harms this approach in
general. Recall from theorem \ref{thm_samp_opt} that \( O\left( \frac{1}{\varepsilon ^{2}\cos ^{2}\theta }\right)  \)
samples allow us to determine the improvement direction. The problem is that
a random \( f \) will have exponentially small overlap in the size of the state-action
space with the vector \( A \). Thus, \( \cos \theta  \) will be exponentially
small and many samples might be necessary. 

\emph{This last statement seems false. Assume that you have a normalized vector
\( x \) and pick another random normalized vector \( x' \). \( Exx'=\Theta \left( \frac{1}{\sqrt{n}}\right)  \).
-John}

There are two alternatives to improve the policy, which we know discuss. There
is the brute force method of just optimizing \( \omega  \). The second and
more powerful method is to use function approximation to find an \( f \) that
is aligned with \( A \). 


\subsection{The Brute Force Method}

We could just try to use a gradient method to improve \( \omega  \) with some
parameterized class of policies \( \Pi _{\theta } \). There are two problems
with doing this. The first is that the parameterized class of polices must be
tailored such that \( f \) always overlaps with \( A \). In many problems,
such information might not be available. The second and more serious problem
is that \( \Pi _{\theta } \) might not be a rich enough set such that a near-optimal
policy is contained, so when \( \theta  \) converges to a local optimum \( \eta  \)
might still be small. In order to achieve near-optimal performance, the ``size''
of the set \( \Pi _{\theta } \) must be increased. For instance, if the class
is parameterized by a neural network and \( \theta  \) converges to point where
\( \eta  \) is insufficiently small, more hidden units must be added.

The advantage of this method is that a compact representation of the policy
can be kept.

\emph{I think this quite a big concern. With the function approximation methods,
what we might get is string of horrendously complicated policies. Just sampling
from one of these policies might be tricky. -s}


\subsection{Function approximation and the need for exploration}

In general, we might not have the information necessary to construct a good
class \( \Pi _{\theta } \), and so the improvement direction must be learned
from the data. The function approximation strategy is then to align \( f \)
with \( A \). This strategy has some powerful advantages, since we can now
attempt to jointly increase \( \omega  \) and \( \eta  \). \emph{Actually,
I think all the above strategies can be tuned to do that as well -John} First,
let us analyze the conditions for improvement in terms of the generalization
error.

In practice, the \( l_{2} \)-error of \( f \)'s approximation to \( A \)
is a convenient error to minimize. The following theorem gives conditions for
improvement based on the \( \varepsilon  \) sub-optimality and the true \( l_{2} \)-error.

\emph{This theorem statement feels wrong to me. We can let \( \forall s:\,\,J(s)=J^{*}(s) \),
and then \( E_{\nu }Af=0 \), breaking the theorem. -John}

\begin{thm}
Let \( \varepsilon >\max _{s}|J(s)-J^{*}(s)| \) and \( \nu _{0}=\min _{s,a}\nu (s,a) \).
If
\[
E_{\nu }(f-A)^{2}<\nu _{0}\varepsilon ^{2}(1-\gamma )^{2}\]
 then \( E_{v}Af>0 \).
\end{thm}
\begin{proof}
Since \( E_{\nu }(f-A)^{2}=E_{\nu }A^{2}-E_{\nu }fA+E_{\nu }f^{2} \), then
\( E_{\nu }fA\geq E_{\nu }A^{2}-E_{\nu }(f-A)^{2} \). Hence, if 
\begin{equation}
\label{l2_improve}
E_{\nu }A^{2}>E_{\nu }(f-A)^{2}
\end{equation}
, then \( E_{v}Af>0 \). By equation \ref{sub_optimal}, 
\[
E_{\nu }A^{2}\geq \nu _{0}\varepsilon ^{2}(1-\gamma )^{2}\]
 and our result follows.
\end{proof}
Note the \( \nu _{0} \) dependence which suggests that exploration is also
necessary for function approximation. If \( \nu _{0} \) is uniform, then a
polynomial small error, \( \frac{\varepsilon ^{2}(1-\gamma )^{2}}{n} \), is
required to improve \( \omega  \). Unfortunately, if \( \nu  \) is based on
the current policy, then \( \nu _{0} \) could be exponentially small, which
implies that an exponentially small generalization error might be required to
improve \( \eta  \). Not surprisingly, the exploration problem is also persists
for the function approximation case with \( \eta  \).

Let \( \nu  \) and \( \tilde{\nu } \) be the distributions implied by \( \mu  \)
and \( \mu _{e} \) respectively. Again, the problematic case for improving
\( \eta  \) is if \( E_{\nu }A^{2} \) is small. However, if we are not in
this case we might desire to improve both measures with a reasonable error.
Consider 
\[
E_{\tilde{\nu }}(f-A)^{2}+E_{\nu }(f-A)^{2}\leq \tilde{\nu }_{0}\varepsilon ^{2}(1-\gamma )^{2}\]
 so that the error under both error metrics is \( \tilde{\nu }_{0}\varepsilon ^{2}(1-\gamma )^{2} \)
small. Note that \( E_{\nu }A^{2}>\tilde{\nu }_{0}\varepsilon ^{2}(1-\gamma )^{2} \)
implies \( \eta  \) will also improve by equation \ref{l2_improve}. If \( \nu _{0} \)
is uniform and the policy is \( \varepsilon  \) sub-optimal, then in addition
to improving \( \omega  \) with polynomially small error, \( \eta  \) will
also improve if \( E_{\nu }A^{2} \) is not \( \frac{\varepsilon ^{2}(1-\gamma )^{2}}{n} \)
small. Thus, in principle, we have lost very little by improving \( \omega  \).

These results pose the function approximation problem as a supervised learning
problem with reasonable requirements. There are two concerns. We need a supervised
learning method sophisticated enough to meet these desired goals of a polynomially
small generalization error. The other concern is that the representation of
the policy can become arbitrarily complicated, since it is the product of all
previous \( f \)'s. In the discussion, we suggest methods to tackle both of
these difficulties.


\subsection{What have we gained in the incremental framework?}

\emph{Again, the theoretical analysis is not done yet. -s}

OUTLINE: Bounds exist for doing dynamic programming with function approximation,
where the algorithm is just to use the greedy update rules specified in DP with
approximate value functions. These bounds state how close the final policy is
to optimal in terms of the \( \infty  \)-error. Since we are constructing approximate
value functions, the question arises as to why we don't just run DP with these
approximate value functions? What have we gained by using incremental improvement?
I have not worked it through yet, but I think we gain a factor of \( 1-\gamma  \).
In DP with approximation, the closeness of the final policy to optimal is the
\( \infty  \)-error {*}compounded{*} \( \frac{1}{1-\gamma } \) times. I think
in our incremental framework, the final policy is as close to optimal by just
the \( \infty  \)-error, which is the best we could hope for. I haven't finished
working it out yet.


\section{Discussion}

\begin{enumerate}
\item discuss sensible supervised learning methods.
\item how to represent compact policies?
\item discuss why the assumption that we have access to an exploration policy is reasonable.
\end{enumerate}
\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}
