%% This LaTeX-file was created by <jl> Thu Nov 15 00:45:55 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

\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. This
alternative performance measure has the same global optima as the average reward
and can be optimized without decreasing the average reward given a sufficiently
flexible function approximator.
\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 random policies could lead to learning that is
exponentially slow in the size of the state space \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 online 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 the gradient \emph{direction}
(in policy space) when the gradient \emph{magnitude} is small can be (at least)
exponentially difficult (in the number of states). Although being close to an
optimum implies the gradient has a small magnitude, a small magnitude does \emph{not}
imply being close to an optimum. 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. \) 

If we make the assumption that \emph{every policy \( \pi  \) is ergodic, ie}
has a well-defined stationary distribution \( p_{\textrm{stat}} \), then the
\emph{average reward} is \( \sum _{s,a}p_{\textrm{stat}}(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 from the starting state distribution \( \mu  \). 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)\}\, .\]
A solution exists which simultaneously maximizes \( J_{\pi }(s) \) for all
states, and dynamic programming finds this solution. 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?}

Before discuss the problems, a few definitions are in order. Given a fixed starting
state distribution \( \mu  \), we can define the \( \gamma  \)- discounted
future distribution of states as: 
\[
d_{\pi }(s)\equiv (1-\gamma )\sum _{t=0}^{\infty }\gamma ^{t}E_{\pi ,s_{0}\sim \mu }\Pr (s_{t}=s|s_{0})\]
 which is analogous to the stationary distribution in the infinite time setting\emph{.}
As \( \gamma \rightarrow 1 \), \( d_{\pi }(s) \) tends to the stationary distribution,
\( p_{\textrm{stat}}(s) \). 

The gradient of the discounted average reward from a starting state \( s_{0} \)
chosen according to \( \mu  \) is:
\[
\nabla \eta (\pi )=\frac{1}{1-\gamma }\sum _{s,a}d_{\pi }(s)Q_{\pi }(s,a)\nabla \pi (a|s)\]
as shown in \cite{sutton99policy}. Let us define the following distribution
on states and actions:
\[
\nu (s,a)\equiv d_{\pi }(s)\pi (s,a)\, .\]
The gradient can be re-written as:
\begin{equation}
\label{disc_gradient}
\nabla \eta (\pi )=\frac{1}{1-\gamma }E_{s,a\sim \nu }\left[ \frac{\nabla \pi }{\pi }Q_{\pi }\right] \, ,
\end{equation}
 which is a more convenient form with regards to sampling. Note that the expectation:
\[
E_{\nu }xx'=\sum _{sa}\nu (s,a)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) \),
and this view will be useful throughout this paper.

Let us consider the complexity of the most uninformed initial policy, namely
a random or \emph{undirected} policy, in MDPs where the task is to reach some
goal state as quickly as possible. Undirected policies are of interest since
they are common initializations. If a random actions are more likely to increase
the distance to the goal state rather than decreasing it, a fundamental theorem
by Whitehead  \cite{whitehead91complexity, whitehead91study}is now applicable: 

\begin{thm}
(by Whitehead) In any finite homogeneous problem solving task, the expected
time using undirected exploration (such as random walk exploration) required
to identify an optimal policy is bounded below by an expression exponential
in the depth of the state space, if the number of actions leading away from
the goal is larger than the the number of actions leading closer to the goal.
\end{thm}
\emph{Can this be stated mathematically? -John}

The proof of the theorem shows that the expected time to the goal state on the
first trial is exponential in the size of the state space. We share the belief
with Whitehead and others (\cite{thrun92efficient}) that many real-world problems
fulfill the condition that a random action is expected to worsen the situation.
As a special case of this theorem, policy gradient methods will be intractable
for these classes of problems.

More generally let us understand the situations in which estimating the gradient
direction will be difficult. In order to determine if gradient descent with
respect to the \( i \)-th parameter, \( \nabla _{i}\eta  \), will improve
the policy, it is crucial to obtain the correct sign of \( E_{\nu }Q\frac{\nabla _{i}\pi }{\pi } \).
Intuitively, we expect the difficulty of determining the sign to be proportional
to the ration of the ``noise'' \( \Sigma  \) to the ``signal'' \( \mu  \).

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 obtain samples from \( \nu (s,a) \)
and that we can calculate a quantity \( \hat{Q}_{\pi }(s,a) \) which is a nearly
unbiased estimate of \( Q_{\pi }(s,a) \).

\begin{thm}
\label{sig_noise}Assume that samples \( s,a \) are drawn from some distribution
\( \nu (s,a) \) and that \( \frac{\nabla _{i}\pi }{\pi } \)exists. 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) \).
Then the ratio of the variance, \( \Sigma  \), to the mean, \( \mu  \), of
the estimate \( \hat{Q}(s,a)\frac{\nabla _{i}\pi }{\pi } \) of \( \nabla _{i}\eta  \)
satisfies:
\[
\frac{\Sigma ^{2}}{\mu ^{2}}\geq \frac{\sigma ^{2}_{\textrm{min}}}{E_{\nu }A^{2}}-1\, .\]

\end{thm}
\begin{proof}
Without loss of generality, we will assume that \( \frac{\nabla _{i}\pi }{\pi } \)
is normalized, \emph{ie} that \( E_{\nu }(\frac{\nabla _{i}\pi }{\pi })^{2}=1 \).
Since the \( \hat{Q} \) are unbiased, the mean \( \mu  \) of the estimate
\( \hat{Q}(s,a)\frac{\nabla _{i}\pi }{\pi } \) is also unbiased. The variance
of this estimate is:
\begin{eqnarray}
\Sigma ^{2} & = & E_{\nu }\left( \frac{\nabla _{i}\pi }{\pi }\right) ^{2}\hat{Q}^{2}-\mu ^{2}\label{variance} \\
 & = & \sum _{s,a}\nu (s,a)\int dP(\hat{Q}(s,a))\hat{Q}^{2}(s,a)\left( \frac{\nabla _{i}\pi (a|s)}{\pi (a|s)}\right) ^{2}-\mu ^{2}\\
 & = & \sum _{s,a}\nu (s,a)\left( \frac{\nabla _{i}\pi (a|s)}{\pi (a|s)}\right) ^{2}(Q^{2}(s,a)+\sigma ^{2}(s,a))-\mu ^{2}\, .
\end{eqnarray}
 We can lower bound \( \Sigma  \) as follows:
\begin{eqnarray*}
\Sigma ^{2} & \geq  & \sum _{s,a}\nu (s,a)\left( \frac{\nabla _{i}\pi (a|s)}{\pi (a|s)}\right) ^{2}\sigma ^{2}(s,a)-\mu ^{2}\\
 & \geq  & \sigma ^{2}_{\textrm{min}}\sum _{s,a}\nu (s,a)\left( \frac{\nabla _{i}\pi (a|s)}{\pi (a|s)}\right) ^{2}-\mu ^{2}\\
 & = & \sigma ^{2}_{\textrm{min}}-\mu ^{2}
\end{eqnarray*}
 where have used the unit length of \( \left( \frac{\nabla _{i}\pi (s,a)}{\pi (s,a)}\right) ^{2} \). 

Note that since \( \sum _{a}\nabla \pi (a|s)=0 \) then \( E_{\nu }\left[ Q_{\pi }\frac{\nabla _{i}\pi }{\pi }\right] =E_{\nu }\left[ A_{\pi }\frac{\nabla _{i}\pi }{\pi }\right]  \).
It follows that \( \frac{\Sigma ^{2}}{\mu ^{2}}\geq \frac{\sigma ^{2}_{\textrm{min}}}{(E_{\nu }A\frac{\nabla _{i}\pi }{\pi })^{2}}-1 \),
and so the \( \frac{\nabla _{i}\pi }{\pi } \) that maximizes \( E_{\nu }\left[ A_{\pi }\frac{\nabla _{i}\pi }{\pi }\right]  \)
also minimizes the lower bound (subject to the normalization constraint). This
occurs when \( \frac{\nabla _{i}\pi }{\pi }=\frac{A}{\sqrt{E_{\nu }A^{2}}} \).
Substitution leads to the result.
\end{proof}
Consider the case in which the large advantages are at states that are visited
infrequently, so \( E_{\nu }A^{2} \) will be small. This theorem shows provides
evidence that it may be difficult to determine if the \emph{}gradient will improve
the policy for \emph{any parameterization}. 
\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}
 

Let us give an additional example demonstrating the problems for a simple two
state MDP 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{Optimizing a Different Performance Measure}

The fundamental problem with policy gradients is that \( \eta  \), which is
what we ultimately seek to optimize, is insensitive to policy improvement at
unlikely states. As shown in theorem \ref{sig_noise}, the gradient will be
difficult to estimate in these cases where the advantages are hidden to the
agent. However, policy improvement at these unlikely states might be necessary
in order for the agent to achieve near 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 for the special case when \( \mu _{e}=\mu (s)\pi (a|s) \) then \( \omega =\eta  \).
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. 

\textbf{\emph{Note to self: say more about why \( \omega  \) is sensible.}}

Since the policy that maximizes \( \omega  \) also simultaneously maximizes
the future reward from every state, then \emph{}maximizing \( \omega  \) also
maximizes \( \eta  \). However, the problem with using a restricted class of
parameterized policies, \( \Pi _{\theta } \), is that a policy which optimizes
\( \omega  \) does not necessarily have high return on \( \eta  \). In order
to exploit the benefits of exploration, the class of policies we consider must
allow us to improve the policy in different areas without ultimately preventing
us from improving \( \eta  \).

The subsections are outlined as follows:

\begin{itemize}
\item in 4.1, we state general conditions for policy improvement.
\item in 4.2, we bound the sample size necessary to improve \( \omega  \) and argue
why using an exploratory distribution \( \mu _{e} \) is important
\item in 4.3, we discuss the implications of improving \( \omega  \) rather than
\( \eta  \)
\end{itemize}

\subsection{Incremental improvement}

For now, let us consider general conditions for improvement without regards
to any restricted class of policies. Consider the incremental update rule:
\begin{equation}
\label{fa_update}
\pi (a|s)\leftarrow \pi (a|s)+\alpha f(s,a)
\end{equation}
where \( f \) is some vector in the space of state-actions. We later address
how to choose an \( f \) at each point in time. Note that this update rule
is to first order equal to the update rule \( \pi (a|s)\propto \pi (a|s)\exp \left( \alpha \frac{f(s,a)}{\pi (s,a)}\right)  \),
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 activ jons with largest advantages
increases the fastest in a ratio sense. 

The relevant \( \gamma  \)- discounted future distribution of states is: 
\[
d_{e}(s)\equiv (1-\gamma )\sum _{t=0}^{\infty }\gamma ^{t}E_{\pi ,s_{0}a_{0}\sim \mu _{e}}\Pr (s_{t}=s|s_{0},a_{0})\]
where the starting state-action distribution is \( \mu _{e} \).

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

\end{thm}
Before we provide the proof, let us compare this to the gradient update rule.
Note that the update rule for a gradient method is:
\[
\pi (a|s)\leftarrow \pi (a|s)+\frac{\partial \pi }{\partial \theta }\Delta \theta \]
and so \( f=\frac{\partial \pi }{\partial \theta } \). To first order, the
performance change specified by the gradient, equation \ref{disc_gradient},
is identical to the previous theorem. 

\begin{proof}
For small enough \( \alpha  \) to ensure positivity, the normalized policy
is
\[
\pi _{\alpha }(a|s)=\frac{\pi (a|s)+\alpha f(s,a)}{1+\alpha \sum _{a^{\prime }}\pi (a^{\prime }|s)f(s,a^{\prime })}\, ,\]
 and so
\[
\frac{\partial \pi _{\alpha }(a|s)}{\partial \alpha }|_{\alpha =0}=\pi (a|s)(f(s,a)-\sum _{a^{\prime }}\pi (a^{\prime }|s)f(s,a^{\prime })\, .\]
Since the probabilities are normalized \( \sum _{a}\nabla \pi (a|s)=0 \) and
so \( \sum _{a}Q(s,a)\nabla \pi (a|s)=\sum _{a}(A(s,a)+J(s))\nabla \pi (a|s)=\sum _{a}A(s,a)\nabla \pi (a|s) \).
Hence, 
\[
\nabla \eta (\pi )=\frac{1}{1-\gamma }E_{s,a\sim \nu }\left[ \frac{\nabla \pi }{\pi }Q_{\pi }\right] =\frac{1}{1-\gamma }E_{\nu }A\frac{\nabla \pi }{\pi }\]
It follows that, to first order in \( \alpha  \),
\begin{eqnarray*}
\Delta \eta  & = & \alpha \frac{\partial \eta }{\partial \alpha }|_{\alpha =0}\\
 & = & \frac{\alpha }{1-\gamma }\sum _{s,a}d_{\pi }(s)\pi (a|s)A(s,a)\frac{\pi (a|s)(f(s,a)-\sum _{a^{\prime }}\pi (a^{\prime }|s)f(s,a^{\prime }))}{\pi (a|s)}\\
 & = & \frac{\alpha }{1-\gamma }\sum _{s,a}d_{\pi }(s)\pi (a|s)A(s,a)f(s,a)-(\sum _{s,a}d_{\pi }(s)\pi (a|s)A(s,a))(\sum _{a^{\prime }}\pi (a^{\prime }|s)f(s,a^{\prime }))\\
 & = & \frac{\alpha }{1-\gamma }\sum _{s,a}\nu (s,a)A(s,a)f(s,a)
\end{eqnarray*}
 where we have used \( \sum _{a}\pi (a|s)A(s,a)=0 \).
\end{proof}
Thus, to improve the policy it is only necessary that \( f \) must have a positive
inner product with \( A \). {*}Perhaps make a statement here comparing this
to greedy dynamic programming{*}. \emph{}

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:
\[
\Delta \omega =\alpha E_{\nu }Q\tilde{f}+O(\alpha ^{2})\, .\]
This form is convenient since we can directly estimate \( E_{d\pi }Q\tilde{f} \)
using Monte-Carlo estimates of the state-action values. We now address how many
samples are required to improve a sub-optimal policy.


\subsection{The difficulty of improving a sub-optimal policy}

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) \)
for some sub-optimal policy. More precisely, given an \( f \) how many samples
are sufficient to determine if the direction \( f \) or \( -f \) will improve
the policy? We again consider the sampling model used in theorem \ref{sig_noise}.

In order to do this, we must determine, with some certainty, the sign of \( E_{\nu }Q\tilde{f} \),
where


\[
\tilde{f}(s,a)\equiv f(s,a)-\sum _{a^{\prime }}\pi (a^{\prime }|s)f(s,a^{\prime })\]
Note that this constrained direction has the property that for all states \( s \),
\( E_{\pi (a|s)}\tilde{f}(s,a)=0 \). 

In the following theorem, \( \theta  \) is the angle between the vectors \( A \)
and \( f \) in the state action space. The inner product then satisfies \( E_{\nu }Af=\sqrt{(E_{\nu }A^{2})(E_{\nu }f^{2})}\cos \theta  \). 

\begin{thm}
\label{sample_size}Let \( \cos \theta =\frac{E_{\nu }Af}{\sqrt{(E_{\nu }A^{2})(E_{\nu }f^{2})}} \)
and assume \( f \) is a vector in the state-action space. Under the assumptions
and sampling model of theorem \ref{sig_noise}, then given \( k \) independent
samples, the estimate \( X=\frac{1}{k}\sum _{i=1}^{k}\hat{Q}(s,a)\tilde{f}(s,a) \)
has the
\[
\Pr (\textrm{sign}(X)\neq \textrm{sign}(E_{\nu }Af))\leq \exp (-\frac{2k(E_{\nu }A)^{2}\cos ^{2}\theta }{5R_{\textrm{max}}^{2}})\]

\end{thm}
\begin{proof}
The variance is: 
\begin{eqnarray*}
\Sigma ^{2} & = & E_{\nu }((\tilde{f}\hat{Q})^{2})-\mu ^{2}\\
 & \leq  & E_{\nu }(\tilde{f}^{2})E_{\nu }(\hat{Q}^{2})
\end{eqnarray*}
We can upper bound \( E_{\nu }\hat{Q}^{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)\leq R_{\textrm{max}} \).
This implies that the maximum variance for any state-action is \( \frac{R_{\textrm{max}}^{2}}{4} \).
Therefore, \( E_{\nu }(\hat{Q}^{2})=\sigma (s,a)^{2}+Q(s,a)^{2}\leq \frac{5R_{\textrm{max}}^{2}}{4} \)
and so:
\[
\Sigma ^{2}\leq E_{\nu }(\tilde{f}^{2})\frac{5R_{\textrm{max}}^{2}}{4}\, .\]


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}}{5R_{\textrm{max}}^{2}}}\]
setting \( \epsilon =EX=E_{\nu }Af=\sqrt{(E_{\nu }A^{2})(E_{\nu }f^{2})}\cos \theta  \)
gives the \( \Pr \left( |E_{\nu }Af-\frac{1}{k}\sum _{i}X_{i}|>E_{\nu }Af\right)  \)
and the result follows.
\end{proof}
Note that if \( E_{\nu }A^{2} \) 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 }A^{2}\cos ^{2}\theta }\right)  \).
This suggests that a uniform distribution is sensible since it allows \( E_{\nu }A^{2} \)
to have a significant value as long as any advantage is large. A uniform distribution
in \( \nu  \) may be difficult to achieve by controlling \( \mu _{e} \). 

Note that 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 since \( E_{\nu }A^{2} \) is
small. 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}). Under this definition, \( \eta  \) could be at most
\( \varepsilon  \)-far from \( \eta ^{*} \) in a worst case scenario. 

The following theorem states how far from optimal a given policy is in terms
of the largest advantage.

\begin{thm}
Let \( \varepsilon =\max _{s}|J(s)-J^{*}(s)| \) and \( A_{\infty }=\max _{s,a}A(s,a) \).
Then
\begin{equation}
\label{max_improve}
\varepsilon \leq A_{\infty }\, .
\end{equation}

\end{thm}
\begin{proof}
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 
\[
J_{\pi ^{\prime }}(s)-J_{\pi }(s)=(1-\gamma )E_{a\sim \pi ^{\prime },s_{t}\sim P(s_{t}|s_{o}=s)}(\sum _{t}\gamma ^{t}A_{\pi }(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 A_{\infty } \).
The result follows from the special case when \( \pi ^{\prime } \) is optimal. 
\end{proof}
This bound is tight and is the best one could hope for some \( A_{\infty } \).
As a lower bound, consider the case in which one state-action pair has a large
advantage. The agent stands to gain that advantage by taking that action and
can do so forever if the action returns the agent to the same state. 

Let us consider for a given \( E_{\nu }A^{2} \), how large \( A_{\infty } \)
could be. Let \( (s^{\prime },a^{\prime }) \) be the state-action pair with
the largest advantage, so \( E_{\nu }A^{2}\geq \nu (s^{\prime },a^{\prime })A_{\infty }^{2}\geq \nu _{0}A_{\infty }^{2} \).
Hence, 
\[
A_{\infty }\leq \sqrt{\frac{E_{\nu }A^{2}}{\nu _{0}}}\]
 , where the bound is tight for the worst case scenario of \( 0 \) advantages
everywhere except for the state with lowest probability. In practice, the reinforcement
learning problem is (hopefully) not this difficult.

The importance of using exploration is that \( E_{\nu _{e}}A^{2} \) will be
small only when all advantages are small, where \( \nu _{e} \) is the distribution
implied by the exploratory distribution \( \mu _{e} \). Using the worst case
bounds, 
\begin{equation}
\label{worst_case}
E_{\nu }A^{2}\leq \nu _{0}\varepsilon ^{2}(1-\gamma )^{2}\, .
\end{equation}
 The number of sample required to improve \( \omega  \) is \( O(\frac{R_{\textrm{max}}^{2}}{E_{\nu }A^{2}}) \),
neglecting the \( \theta  \) dependence. Hence, in the worst case scenario,
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). In contrast, for the on-policy
\( \nu  \), \( E_{\nu }A^{2} \) can be exponentially small for the same policy,
thus requiring many more samples to improve the policy. 

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. 


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

What has been lost by improving \( \omega  \) instead of \( \eta  \)? Our
real goal is \emph{}improving \( \eta  \). Note that the end point 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. The problematic cases for improving \( f \) are when \( E_{\nu }(A^{2}) \)
is small, where \( \nu  \) is the 'on-policy' distributions. However, if \( E_{\nu }(A^{2}) \)
is not 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 non-problematic
case.


\section{Policy Improvement (\textbf{incomplete)}}

The question now is how to choose an \( f \) to improve the policy. There are
two alternatives to improve the policy, which we now discuss. There is the brute
force method of just choosing different \( f \), possibly at random, to optimize
\( \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.


\subsection{Function approximation and the need for exploration}

We now pose the policy improvement issue as a supervised learning problem with
reasonable requirements. The function approximation strategy is to align \( f \)
with \( A \), and then use this \( f \) in an incremental update rule. 

In practice, the \( l_{2} \)-error of \( f \)'s approximation to \( A \)
is a convenient error to minimize. Consider the case in which the advantages
are fit such that 
\[
E_{\nu }(f-A)^{2}\leq \delta \, .\]
 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} \). Therefore, if 
\[
E_{\nu }A^{2}>\delta \]
then \( E_{v}Af>0 \). This suggests the following incremental algorithm.

\begin{enumerate}
\item Fit the advantages with mean squared error no more than \( \delta  \).
\item Perform a line search with the following update rule:
\[
\pi (a|s)\leftarrow \pi (a|s)(1+\alpha f(s,a))\]

\item Terminate if no the \( \omega  \) does not increase.
\end{enumerate}
Note that the previous algorithm will return a policy with the property that
\( E_{\nu }A^{2}<\delta  \). In the worst case situation, the \( \varepsilon  \)
degree of sub-optimality is given by equation \ref{worst_case}, which implies
\( \nu _{0}\varepsilon ^{2}(1-\gamma )^{2}<\delta  \) or
\[
\varepsilon <\sqrt{\frac{\delta }{\nu _{0}(1-\gamma )^{2}}}\]
 Therefore, in the worst case, if \( \nu  \) is uniform, then a polynomially
small \( \delta  \) is required to be \( \varepsilon  \) close to optimal.
Unfortunately, if \( \nu  \) is based on the current policy, then \( \nu _{0} \)
could be exponentially small, which implies that an exponentially small generalization
error is necessary to be \( \varepsilon  \) close to optimal. Not surprisingly,
we see that exploration is also necessary for function approximation.

\textbf{Need to mention non-param. function approximation is necessary to achieve
condition 1.}

If we desire both \( \omega  \) and \( \eta  \) to improve most of the time,
let us consider a slightly different error measure. Let \( \nu  \) and \( \tilde{\nu } \)
be the distributions implied by \( \mu  \) and \( \mu _{e} \) respectively.
Consider 
\[
E_{\tilde{\nu }}(f-A)^{2}+E_{\nu }(f-A)^{2}\leq \delta \]
 so that the error under both error metrics is \( \delta  \) small. \textbf{Need
to say more about joint improvement.}


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