%% This LaTeX-file was created by <jl> Sat Sep 22 22:44:59 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*{thm*}{Theorem} 
\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. Maximizing
this alternative performance measure 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 of choosing any action, 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 that it is insensitive to performance improvement
at highly unlikely states. Improvement at these states can lead to drastic policy
improvement (as in example 1). 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{enumerate}
\item In section 2, the problems with gradient methods are exhibited in more detail. 
\item In section 3, we discuss general incremental policy improvement (and consider
both gradient methods and function approximation). 
\item In section 4, we show that determining if any direction (in policy space) will
improve the average reward can be arbitrarily difficult. 
\item In section 5, we propose an alternative performance measure 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 6, we discuss how we can improve this alternative performance measure
without ever detecting a decrease in the average reward. 
\end{enumerate}

\section{Preliminaries}

Ultimately, we care about maximizing the average reward, so this seems like
the natural performance measure to use. However, before a global optima is reached
there can be regions in which it is arbitrarily difficult to improve the average
reward. 

First, let us state the standard formulation of a finite Markov decision process
(MDP) with rewards. An MDP with rewards is a tuple \( (S,s_{0},A,R,P) \) where:
\( S \) is finite set of states, \( s_{0} \) is a start state, \( 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 distribution \emph{\( d_{\pi } \)}.
Under this assumption, the \emph{average reward} is \( \eta _{\pi }\equiv \sum _{s,a}d_{\pi }(s)\pi (a|s)R(s,a) \),
the state-action value is 
\begin{equation}
\label{eq-Q}
Q_{\pi }(s,a)\equiv E_{\pi }\{\sum ^{\infty }_{t=0}(R(s_{t},a_{t})-\eta _{\pi })|s_{0}=s,a_{0}=a\}
\end{equation}
 and the value function is 
\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 \).
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{Following the Gradient }

\emph{We should consider eliminating this section. It is a distractant to the
message of the paper. Right now the paper is ``policy gradients aren't too
bad, policy gradients are bad, and here is a fix.'' It is much cleaner if we
just have: ``policy gradients are bad, and here is a fix.'' I'm skipping this
section in my pass. -John}

In this section, we trivially restrict the class of policies by excluding only
deterministic policies and consider only the Gibbs table-lookup distribution,
\( \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} \), it is straightforward
to show : 
\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 \).
\emph{aside: The proof is a bit hairy at the moment (but correct), so don't
bother wading through it too deeply. For some reason I used \( \rho (s) \)
as the stationary distribution instead of \( d(s) \). }

First, let us consider the 2-state MDP shown in Figure \ref{fig1}B, which demonstrate
the importance of this concern. In this MDP, increasing the chance of a self-loop
at \( i \) decreases the stationary probability of \( j \), which hinders
the learning to \( j \). . Under an initial policy that has the stationary
distribution \( \rho (i)=.8 \) and \( \rho (j)=.2 \), learning to state \( i \)
squelches the learning to state \( j \) and this leads to an an extremely flat
plateau of improvement at 1 average reward shown in Figure \ref{fig1}C (see
figure text). \emph{However, the optimal policy is eventually reached.} Figure
\ref{fig1}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{fig1}E shows where this occurs
and gives a clearer picture (see figure text).

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


This result suggests that using a stochastic gradient algorithm with the usual
caveats is \emph{prima facie} sufficient to find the globally optimal policy.
Unfortunately, the variance of a gradient estimate can become large, as is demonstrated
in the two state example (\emph{aside: i will make a figure showing how the
variance of the grad. estimate drops)}. This is due to the fact that, to estimate
\( \partial _{sa}\eta  \), the state \( s \) must sampled under the stationary
distribution (which could have a probability that is exponentially small in
the size of the state space). 

Let us now examine the variance in estimating the gradient more thoroughly.
First, we state a bound from \cite{bartlett00estimation} on the variance of
a gradient estimate based on single Monte Carlo run of \( N \) steps:
\begin{equation}
\label{werid_bound}
Pr(|\nabla \eta -\nabla \eta _{\textrm{MC}}|_{\infty }\geq \varepsilon )\geq \frac{Nd}{2}\exp (-s/\tau )+2sd\exp (-\varepsilon ^{2}N\frac{c}{s})
\end{equation}
where \( \nabla \eta  \) and \( \nabla \eta _{MC} \) are the true and sampled
estimates of the gradient, \( s \) is any number less than \( N \), and \( c \)
is a constant. The norm \( |\nabla \eta -\nabla \eta _{MC}|_{\infty } \) is
the largest difference in the gradient over all the parameters, \emph{ie} \( \textrm{argmax}_{\theta _{i}}|\frac{\partial \eta }{\partial \theta _{i}}-(\frac{\partial \eta }{\partial \theta _{i}})_{MC}| \).
\emph{}The important point is that the estimated direction \emph{}needs to point
within \( 90 \) degrees of the true gradient for local improvement to be guaranteed.
The bound shows that we can easily force correctness to within \( \varepsilon  \).
However, if the magnitude of the gradient is \( O(\varepsilon ) \), then an
\( \varepsilon  \) infinity error does not imply a correct direction. This
example shows that the magnitude of the gradient can be small far away from
the optima. 

Reconsidering the MDP in example 1, we see that although it suffers from the
initial sampling problem, it is simple in comparison to our 2-state MDP in the
sense that the true gradient is always improving the probability of the optimal
action, unlike in in the 2 state problem where the gradient initially reinforces
a sub-optimal action at state \( i \). Note that one step of policy improvement
from any policy returns an optimal policy for the MDP in example 1, but not
in the 2-state MDP. Consider the placement of a small reward at the left-most
state in example 1. This would complicate matters even further, since exploration
would be discouraged even more (just as in the 2 state-MDP). 


\section{Incremental Policy Improvement}

Gradient methods guarantee improvement due to the incremental nature of the
algorithm. Dynamic programming using function approximation has only weak theoretical
guarantees which stem from the fact that drastic changes to the policy can occur
at any step in the algorithm. Performance guarantees exist only for algorithms
which change the policy incrementally (by following a gradient or via value
function approximations). In the first subsection, general conditions under
which an incremental change to the policy will improve its performance are stated,
and the later sub-sections analyze the requirement of satisfying these conditions
for policy gradient and value function approximation techniques.


\subsection{General Conditions for Improvement}

Let's now 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. 

First, let us define the inner product for vectors in the state-action space
to be:
\[
<x,x^{\prime }>_{d\pi }=\sum _{sa}d_{\pi }(s)\pi (a|s)x(s,a)x^{\prime }(s,a)\]
 where \( d_{\pi }(s)\pi (s,a) \) is state-action distribution. This leads
to following result:

\begin{thm*}
\label{thm_avrew}Let \( A_{\pi }(s,a) \) be the advantages of any state and
action. For all \( f \), there exists an \( \epsilon  \) s.t. for all \( \alpha <\epsilon  \)
the update rule (equation \ref{fa_update}) has performance improvement:
\begin{equation}
\label{inner_prod}
\Delta \eta =\alpha <A_{\pi },f>_{d\pi }+O(\alpha ^{2})
\end{equation}
 
\end{thm*}
\begin{proof}
Specialization of \ref{th-performance}.
\end{proof}
This theorem state that to obtain improvement all we need is the much weaker
result that \( f \) must has 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{A}(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{A}>_{\nu }+O(\alpha ^{2})\, .\]


Unfortunately, we cannot directly estimate \( <f,A>_{d\pi } \), since the advantages
can't be obtained from Monte-Carlo estimates. However, we can directly estimate
\( <\tilde{A},Q>_{d\pi } \) since the state-action values can be estimated
from Monte Carlo samples. \emph{This issue has had considerable discussion in
the literature and merits more comments.}


\subsection{Gradient Methods}

In light of the last theorem, how do gradient method techniques perform? For
simplicity, let us consider the class of policies parameterized by one parameter,
\( \theta  \). The update rule under a gradient method is
\begin{eqnarray*}
\pi (a|s) & \propto  & \pi (a|s)+\frac{\partial \pi }{\partial \theta }\Delta \theta \\
 & = & \pi (a|s)(1+\Delta \theta \frac{\partial \log \pi (a|s)}{\partial \theta })
\end{eqnarray*}
 and so 
\[
f=\frac{\partial \log \pi }{\partial \theta }\]
 It follows that if \( \left\langle \partial \log \pi /\partial \theta ,Q\right\rangle _{\nu }>0 \)
then a small positive \( \Delta \theta  \) will improve the policy, otherwise
a negative \( \Delta \theta  \) will improve the policy. 

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

In the multiple parameter case, the \emph{}parameterization will choose a set
of directions, \emph{\( f_{i}=\partial \log \pi /\partial \theta _{i} \),}
and the gradient will tell us to move in the \( f_{i} \) or \( -f_{i} \) direction
with respect to each parameter \( \theta _{i} \). \emph{}In order to improve
the policy, it is crucial to obtain the correct sign of \( <\partial \log \pi /\partial \theta ,Q>_{d\pi } \)
\emph{}on average\emph{.} The next section discusses the variance issue in determining
the sign of this quantity. 


\subsection{Function Approximation}

\emph{I've tried to clean up this theorem but I don't understand what you are
getting at here. Why is this here? Is this section removable? -John}

An alternative to policy gradient techniques is using function approximation
to find some \( f \) or \( \tilde{A} \) to improve the policy with. Two important
question are: ``What should we fit?'' and ``How should we do it?'' If each
\( \tilde{A}(s,a) \) has the same sign as \( A(s,a) \) then improvement will
be guaranteed. Motivated by this, let us assume that we desire \( \tilde{A} \)
to be the true advantages. The following theorem decomposes the approximation
error of some function \( f \) into two components: an action independent component
and a component due to advantages. 

\begin{thm}
Define \( \tilde{f}(s)\equiv \sum _{a}\pi (a|s)f(s,a) \), and \( \tilde{A}(s,a)\equiv f(s,a)-\tilde{f}(s) \).
Then
\[
|f-Q_{\pi }|^{2}=|\tilde{A}-A_{\pi }|^{2}+|J-\bar{f}|\, .\]
 
\end{thm}
\begin{proof}
This follows from:

\[
\begin{array}{ccc}
|f-Q|^{2} & = & |f-\bar{f}-(Q-J)-(J-\bar{f})|^{2}\\
 & = & |(\tilde{A}-A)-(J-\tilde{f})|^{2}\\
 & = & |\tilde{A}-A|^{2}+|J-\bar{f}|^{2}-2\left\langle \tilde{A},J-\bar{f}\right\rangle +2\left\langle A,J-\tilde{f}\right\rangle \\
 & = & |\tilde{A}-A|^{2}+|J-\bar{f}|^{2}
\end{array}\]
where we used the fact that \( A \) and \( \tilde{A} \) have zero expectation
values (\( \sum _{a}\tilde{A}(s,a)=0 \) for all \( s \)). 
\end{proof}
Minimizing the \( l_{2} \) error measure is equivalent to minimizing the angle
between the two vectors at hand (assuming that the vector being fit can be scaled).
If we constrain \( \tilde{f}=0 \), then the vector which minimizes the true
error with the respect to the state-action values also minimizes the true error
with respect to the advantages. However, for a finite sample size this constraint
is not necessarily appropriate. \emph{The issue of how to fit \( f \) using
baselines merits further discussion.}

\emph{ehh? -John}


\section{The Variance Trap}

Given a direction \( f \) how hard is it to determine if this direction will
improve the policy? We will now bound the signal to noise ratio of this estimate
of \( <f,Q>_{\nu } \). 

A related method is to perform a line search to determine if the policy improves.
Equation \ref{inner_prod} shows that this is essentially equivalent to checking
if \( <f,Q>_{\nu } \) is positive \emph{}for small changes to the policy. \emph{I
have to think about this a bit more.}

Under a crude sampling model, the following theorem gives a bound on the signal
to noise ratio of an estimate of \( <\tilde{A},Q>_{\nu } \).

\emph{Can we have fewer givens here? For example, perhaps can we just say what
the unbiased Monte Carlo estimates are? }

\begin{thm}
Assume that samples \( s,a \) are sampled from \( d(s)\pi (a|s) \) and that
the unbiased Monte Carlo estimates, \( \chi (s,a) \), of \( Q(s,a) \) have
variance \( \sigma ^{2}(s,a) \). Assume that \( f \) is some vector and \( \tilde{A}(s,a)\equiv f(s,a)-\sum _{a^{\prime }}\pi (a^{\prime }|s)f(s,a^{\prime }) \).
Then \( \chi (s,a)\tilde{A}(s,a) \) is an unbiased estimate of \( <\tilde{A},Q>_{\nu } \)
and the noise to signal ratio with respect to any \( f \) is bounded by:
\[
\frac{\Sigma ^{2}}{\mu ^{2}}\geq \frac{1}{\left\langle \frac{A^{2}}{Q^{2}+\sigma ^{2}}\right\rangle _{d\pi }}-1\]

\end{thm}
\begin{proof}
Since the \( \chi  \) are unbiased, the mean \( \mu  \) is:
\begin{eqnarray*}
\mu  & = & \sum _{s,a}d(s)\pi (a|s)\int dP(\chi (s,a))\chi (s,a)\tilde{A}(s,a)\\
 & = & \left\langle \tilde{A},Q\right\rangle _{d\pi }
\end{eqnarray*}
 and the variance is:
\begin{eqnarray}
\Sigma ^{2} & = & \left\langle \chi ^{2}\right\rangle -\mu ^{2}\\
 & = & \sum _{s,a}d(s)\pi (a|s)\int dP(\chi (s,a))\chi ^{2}(s,a)\tilde{A}^{2}(s,a)-\mu ^{2}\\
 & = & \sum _{s,a}d(s)\pi (a|s)\tilde{A}^{2}(Q^{2}(s,a)+\sigma ^{2}(s,a))-\mu ^{2}\, .\label{variance} 
\end{eqnarray}
giving us: 

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


Technically, \( \tilde{A} \) is constrained such that \( \sum _{a}\tilde{A}(s,a)\pi (a|s)=0 \).
However, we use the unconstrained minima of \( \Sigma ^{2}/\mu ^{2} \) to provide
a lower bound. 
\[
\frac{\partial (\sum ^{2}/\mu ^{2})}{\partial \tilde{A}_{sa}}=\frac{2d(s)\pi (a|s)\tilde{A}(s,a)(Q^{2}(s,a)+\sigma ^{2}(s,a))}{\mu ^{2}}-\frac{2\left\langle \tilde{A}^{2}(Q^{2}+\sigma ^{2})\right\rangle _{d\pi }\frac{\partial \mu }{\partial \tilde{A}_{sa}}}{\mu ^{3}}\]
 
\[
=\frac{2d(s)\pi (a|s)\tilde{A}(s,a)(Q^{2}(s,a)+\sigma ^{2}(s,a))}{\mu ^{2}}-\frac{2d(s)\pi (a|s)Q(s,a)\left\langle \tilde{A}^{2}(Q^{2}+\sigma ^{2})\right\rangle _{d\pi }}{\mu ^{3}}\]
The extrema to this equation is at \( \tilde{A}^{*}(s,a)=\frac{Q(s,a)\left\langle \tilde{A}^{2}(Q^{2}+\sigma ^{2})\right\rangle _{d\pi }}{\mu (Q^{2}(s,a))+\sigma ^{2}(s,a))} \)

\emph{I'm lost here. How do you get to the next step? -John}

\( \tilde{A}^{*}(s,a)=\frac{A(s,a)}{Q^{2}(s,a))+\sigma ^{2}(s,a)} \), and it
straightforward to check that this is the minima. 

By substitution, \( \mu (\tilde{A}^{*})=\left\langle \frac{A^{2}}{Q^{2}+\sigma ^{2}}\right\rangle _{d\pi } \).
Also, since \( \sum _{s,a}d(s)\pi (a|s)(\tilde{A}^{*})^{2}(Q^{2}(s,a))+\sigma ^{2}(s,a))=\mu (\tilde{A}^{*}) \),
it follows that :
\begin{equation}
\label{noise}
\Sigma (\tilde{A}^{*})^{2}=\mu (\tilde{A}^{*})-\mu (\tilde{A}^{*})^{2}\, .
\end{equation}
The result follows by using \( \Sigma ^{2}/\mu ^{2}\geq 1/\mu (\tilde{A}^{*})-1 \).
\end{proof}
Let us discuss why this ratio could be large. Consider a set of states \( M \)
in which the agent is almost always in, say with probability \( 1-\varepsilon  \)
(\emph{eg} states far away from the goal in example 1). If the advantages of
the states in \( M \) are small (as compared to the noise level) then these
states will have a negligible contribution to the signal to noise. Further,
if there are large advantages at states not in \( M \), then the contribution
these states have to signal to noise will be down-weighted by \( \varepsilon  \)
(\( \varepsilon  \) is exponentially small in example 1). Thus the agent will
have a hard time improving it's policy. Unfortunately, since there could be
large advantages in the states not in \( M \), the agent stands to gain a large
performance increase. 

\begin{cor}
Further, for any set of states \( M \), let \( \varepsilon  \) be the probability
of \( s\notin M \), and let \( <x>_{s\in X} \) be the conditional expectation
\( \sum _{s,a}P(s|s\in X)\pi (a|s)x(s,a) \) (where for \( s\in X \), \( p(s|s\in X)=d(s)/P(s\in X) \)).
Then: 
\[
\Sigma ^{2}/\mu ^{2}\geq \frac{1}{\varepsilon <(\frac{A}{Q})^{2}>_{s\notin M}+<(\frac{A}{\sigma })^{2}>_{s\in M}}-1\, .\]

\end{cor}
\begin{proof}
Assume \( \tilde{A}^{*}(s,a)=\frac{A(s,a)}{Q^{2}(s,a))+\sigma ^{2}(s,a)} \),
as before. Using \( \tilde{A}^{*}(s,a)\leq \frac{A(s,a)}{\sigma ^{2}(s,a)} \)
and \( \tilde{A}^{*}(s,a)\leq \frac{A(s,a)}{Q^{2}(s,a))} \), 
\begin{eqnarray*}
\mu (\tilde{A}^{*}) & = & \sum _{s\notin M,a}\nu (s,a)A^{*}(s,a)A(s,a)+\sum _{s\in M,a}\nu (s,a)A^{*}(s,a)A(s,a)\\
 & \leq  & \sum _{s\notin M,a}\nu (s,a)\frac{A^{2}(s,a)}{Q^{2}(s,a)}+\sum _{s\in M,a}\nu (s,a)\frac{A^{2}(s,a)}{\sigma ^{2}(s,a)}\\
 & = & \varepsilon \sum _{s,a}P(s|s\notin M)\pi (a|s)\frac{A^{2}(s,a)}{Q^{2}(s,a)}+(1-\varepsilon )\sum _{s,a}P(s|s\in M)\pi (a|s)\frac{A^{2}(s,a)}{\sigma ^{2}(s,a)}\\
 & \geq  & \varepsilon <(\frac{A}{Q})^{2}>_{s\notin M}+<(\frac{A}{\sigma })^{2}>_{s\in M}\, .
\end{eqnarray*}
 The result follows from \ref{noise}.
\end{proof}
\emph{For certain polices and MDPs, this lower bound can be arbitrarily large
(as in the 2-state MDP) and can be exponentially small with respect to the size
of the state space (as in example 1). Since this result holds for all \( f \),
then there does not exist any} \emph{class of parameterized policies for which
the gradient can be estimated with low a signal to noise ratio for these aforementioned
cases, since the inner product being positive determines being correct to within
90 degrees.} Contrast this to bound \ref{werid_bound}. It should be straight
forward to show that this signal to noise ratio scales exponentially in example
1.

We view this variance trap as problem of exploration. The agent must have access
to a state to improve the policy at that state and the performance measure being
used must be sensitive to improvements at those states.


\section{A Different Performance Measure}

We desire a performance measure that can never have an arbitrarily high signal
to noise ratio when there is a potential for large performance increase (\emph{ie}
when there are large advantages at some states). This alternative performance
measure cannot down weight advantages at unlikely states. \emph{}

\begin{description}
\item [Assumption]\emph{The assumption we make in this paper is that the agent has
access to a simulator that can place the agent in any state.}
\end{description}
A natural candidate for a performance measure is to weight the improvement from
all states more uniformly, such as 
\[
\omega \equiv \sum _{s}m(s)*(\textrm{future reward from state }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. Note that the policy that maximizes \( \omega  \)
also simultaneously maximizes the future reward from every state.

The problem with directly using this measure as stated is that the sum future
reward from any state \( s \) is infinite. The dynamic programming formulation
for the undiscounted, infinite horizon scenario is to solve the following, slightly
modified, Bellman equations:
\[
J^{*}(s)=\max _{a}(r(s,a)-\eta ^{*}+\sum _{s^{\prime }}p(s^{\prime }|s,a)J^{*}(s^{\prime }))\]
 for both \( J^{*} \) and \( \eta ^{*} \). The optimal policy is then \( \pi ^{*}(a|s)=\textrm{argmax}_{a}(r(s,a)-\eta (\pi )+\sum _{s^{\prime }}p(s^{\prime }|s,a)J^{*}(s^{\prime })) \).
Note that if \( J^{*}(s) \) is a solution then so is \( J^{*}(s) \) plus a
constant, and so there is a whole family of solutions. The differential value
functions defined by \( J_{\pi }(s)\equiv E_{\pi }\{\sum ^{\infty }_{t=0}(R(s_{t})-\eta _{\pi })|s_{0}=s\} \),
for the policy \( \pi ^{*} \), are one such solution. A common alternative
is to define the value functions by the reward received until a certain recurrent
state (so \( J_{\pi }(s)\leftarrow J_{\pi }(s)-J_{\pi }(s_{\textrm{recurrent}}) \)).
All these suggestions satisfy the consistency condition \( J_{\pi }(s)=r(s,a)-c+\sum _{s^{\prime }}p(s^{\prime }|s,a)J_{\pi }(s^{\prime }) \)
for some constant \( c \).

The problem is that we cannot use the performance measure \( \omega \equiv \sum _{s}m(s)J_{\pi }(s) \)
for any of these suggestions. \emph{The reason is that \( J^{*} \) is not maximized
when the undiscounted, infinite horizon Bellman equations are solved, unlike
in the finite horizon or discounted case.} Intuitively, the \( J^{*}(s) \)
is the transient after an infinite amount of reward has been subtracted away
( \emph{}\( J_{\pi }(s)=E_{\pi }\{\sum ^{\infty }_{t=0}(R(s_{t})-\eta _{\pi })|s_{0}=s\}\approx E_{\pi }\{\sum ^{\infty }_{t=0}R(s_{t})|s_{0}=s\}-\infty \eta ^{*} \).
It is \( \eta ^{*} \) that is being maximized not these differential value
functions. \textbf{aside: This is an important point that we {*}cannot{*} define
an 'exact' alternative performance measure \( \omega  \) in the undiscounted,
infinite horizon case. My previous draft was incorrect in suggesting that the
recurrent state formulation would work! I have not thought through all the implications
of this yet. }

To overcome these difficulties, we no longer considering maximizing the undiscounted,
future reward, but an approximation to it. There are two sensible alternatives,
using the \( T \)-step future reward or using \( \gamma  \) discounted reward,
either of which is acceptable. For computational and notational convenience,
we only consider the discounted formulation. 

\emph{aside: In the \( T \)-step scenario, we have to not only consider the
\( T \)-step future reward, but also have to the \( T-1,T-2,\ldots 1 \)-step
future rewards. For instance, just look at \( \nabla J_{T}(s_{0})=\sum _{t=1}^{T}\sum _{s}P(s_{t}=s|s_{0})\nabla \pi (a|s)Q_{T-t}(s) \),
where \( Q_{T-t} \) is the reward for the next \( T-t \) steps. Nothing is
wrong with this, but the inner-product condition is not as clean due to an additional
sum over 1 to \( T \). }

We now consider the following performance measure:
\[
\omega (\pi )=(1-\gamma )\sum _{s}m(s)J_{\gamma }(s)\]
 \emph{Maximizing this performance measure is equivalent to maximizing the discounted
reward from starting states chosen under the distribution \( m(s) \) (which
could be uniform).} Unlike in the undiscounted, infinite horizon setting, the
\( J_{\pi }(s) \) can be \emph{simultaneously maximized} when the corresponding
Bellman equations, \( J_{\gamma }(s)=\max _{a}(r(s,a)+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)J_{\gamma }(s^{\prime })) \),
are solved. 

Note that if \( m(s) \) is equal to the stationary distribution of \( \pi  \)
then \( \omega (\pi ) \) will be equal to the average reward of \( \pi  \)
(of course \( m(s) \) is constant where as \( d_{\pi }(s) \) is a function
of the policy). More formally (as shown in \cite{singh94learning}):
\[
\eta (\pi )=(1-\gamma )\sum d_{\pi }(s)J_{\pi }(s)\, .\]
 This follows from using the consistency condition (\( J=r+\gamma PJ) \):
\begin{eqnarray*}
\sum _{s}d_{\pi }(s)J(s) & = & \sum _{s}d_{\pi }(s)r+\gamma \sum _{s,s^{\prime }}d_{\pi }(s)P_{s\rightarrow s^{\prime }}J(s^{\prime })\\
 & = & \eta +\gamma \sum _{s^{\prime }}d_{\pi }(s^{\prime })J(s^{\prime })
\end{eqnarray*}
where we have also used the stationarity of \( d(s) \). Collecting terms proves
the previous statement. 

Now let us analyze the improvement conditions for this new performance measure
and its signal to noise properties. Given a start state \( s_{0} \), let us
define the discounted future distribution of states as:
\[
d_{\pi }(s|s_{0})\equiv (1-\gamma )\sum _{\tau =0}^{\infty }\sum _{s}\gamma ^{\tau }P(s_{\tau }=s|s_{0})\, .\]
 This definition is analogous to the stationary distribution in the undiscounted
setting. Since the starting state is chosen according to \( m(s) \), the following
definition will be useful:
\[
\tilde{m}(s)\equiv \sum _{s^{\prime }}d_{\gamma }(s|s^{\prime })m(s^{\prime })\, .\]


\begin{thm}
\label{th-performance} Assume the definition given above for \( \tilde{m}(s) \).
Let us consider the update rule \( \pi _{s}(a)\leftarrow \pi _{s}(a)(1+\alpha f(s,a)) \)
for some vector \( f \) and some small \( \alpha  \). Let \( A \) be the
true advantages. Then the performance improvement of \( \omega  \) is: 
\begin{equation}
\label{inner_prod}
\Delta \omega =\alpha <A,f>_{\tilde{m}\pi }+O(\alpha ^{2})\, .
\end{equation}

\end{thm}
\begin{proof}
The proof is similar to that of theorem 2.1. The gradient of \( J_{\gamma }(s_{0}) \)
is 
\begin{eqnarray}
(1-\gamma )\nabla J_{\gamma }(s_{0}) & =(1-\gamma ) & \sum _{\tau =0}^{\infty }\sum _{s}\gamma ^{\tau }P(s_{\tau }=s|s_{o})\sum _{a}\nabla \pi (a|s)Q_{\gamma }(s,a)\\
 & = & \sum _{s}d_{\gamma }(s|s_{0})\sum _{a}\nabla \pi (a|s)Q_{\gamma }(s,a)\label{disc_grad} 
\end{eqnarray}
Let us consider the table-lookup Gibbs distribution, \( \tilde{\Pi }_{G}=\{\pi _{\theta }:\pi (a|s)\propto \exp (\theta _{sa})\} \).
This gradient is then:
\[
(1-\gamma )\partial _{sa}J_{\gamma }(s_{0})=d_{\gamma }(s|s_{0})\pi (a|s)A_{\gamma }(s,a)\]
where \( A_{\gamma }(s,a)\equiv Q_{\gamma }(s,a)-J_{\gamma }(s) \) and \( \partial _{sa}\equiv \partial /\partial \theta _{sa} \).
It follows that the gradient of \( \omega  \) is :
\begin{eqnarray}
\partial _{sa}\omega (\pi ) & = & (1-\gamma )\sum _{s^{\prime }}m(s^{\prime })\partial _{sa}J_{\gamma }(s^{\prime })\\
 & = & \sum _{s^{\prime }}m(s^{\prime })d_{\gamma }(s|s^{\prime })\pi (a|s)A_{\gamma }(s,a)\\
 & = & \tilde{m}(s)\pi (a|s)A_{\gamma }(s,a).
\end{eqnarray}
 Similar arguments as before lead to the result.
\end{proof}
The following theorem shows that there exists a direction in which improvement
of \( \omega  \) can always be detected \emph{(with a policy independent bound)},
unless the policy has performance close to the globally optimal policy (with
the caveat that we never let the policy become arbitrarily deterministic).

\begin{thm}
Assume that samples \( s,a \) are sampled from \( \tilde{m}(s)\pi (a|s) \)
and that the unbiased Monte Carlo estimates, \( \chi (s,a) \), of \( Q(s,a) \)
have variance \( \sigma ^{2}(s,a) \). Assume that \( \max _{s,a}\sigma (s,a)=\sigma _{\infty } \),
\( \max _{s,a}|A(s,a)|=A_{\infty } \), \( \min _{s,a}\pi (a|s)=\pi _{0} \),
and \( \min _{s}m(s)=m_{0} \). Let the improvement direction \( f \) be the
true advantages \( A \). Then the estimate \( \chi (s,a)\tilde{A}(s,a) \)
of \( <\tilde{A},Q>_{\tilde{m}\pi } \) will have the following bounded noise
to signal ratio:
\[
\sigma ^{2}/\mu ^{2}\leq \frac{\sigma ^{2}_{\infty }}{(1-\gamma )\pi _{0}m_{0}A^{2}_{\infty }}\, .\]
 Further, the if \( \eta ^{*} \) is the optimal possible average reward, then
\( |\eta -\eta ^{*}|\leq A_{\infty }/(1-\gamma ) \).
\end{thm}
Note that for the uniform distribution for \( m(s) \) that \( m_{0}=1/(\#\textrm{ of states}) \),
whereas in the previous bound \( \varepsilon  \) could be exponentially small
(in terms of the size of the state space). \emph{aside: Also, although this
bound uses \( \pi _{0} \) (the lowest action probability of the} current \emph{policy),
this could be avoided by using a starting state-action distribution, \( m(s,a) \),
rather than just a starting-state distribution \( m(s) \).} \emph{I'll change
this later, not sure why I didn't use m(s,a) to start with.}

\begin{proof}
Using \( f=A \), the mean is
\[
\mu =\sum _{s,a}\tilde{m}(s)\pi (a|s)A^{2}(s,a)\]
 and using equation \ref{variance}, the variance of an estimate can be bounded
by
\begin{eqnarray*}
\sigma ^{2} & \leq  & \sum _{s,a}\tilde{m}(s)\pi (a|s)\sigma ^{2}(s,a)A^{2}(s,a)\\
 & \leq  & \sigma ^{2}_{\infty }\sum _{s,a}\tilde{m}(s)\pi (a|s)A^{2}(s,a)\\
 & = & \sigma ^{2}_{\infty }\mu \, .
\end{eqnarray*}
 Thus,
\[
\sigma ^{2}/\mu ^{2}\leq \sigma ^{2}_{\infty }/\mu \, .\]
 Using the definition of \( d_{\gamma } \), \( d(s|s_{0})\geq (1-\gamma ) \)
so \( \tilde{m}(s)\geq d_{\gamma }(s|s)m(s)\geq (1-\gamma )m_{0} \). Also,
let \( s_{\infty } \) be the state with the largest advantage. It follows that:
\begin{eqnarray*}
\mu  & = & \sum _{s,a}\tilde{m}(s)\pi (a|s)A^{2}(s,a)\\
 & \geq  & \tilde{m}(s_{\infty })\pi (s_{\infty },a)A^{2}(s_{\infty },a)\\
 & \geq  & (1-\gamma )\pi _{0}m_{0}A^{2}_{\infty }\, .
\end{eqnarray*}
 It is straightforward to show if the maximum advantage is \( A_{\infty } \)
then the optimal payoff can be no greater then \( A_{\infty }/(1-\gamma ) \)
than the current policy (this proof is omitted for now). 
\end{proof}

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

An important question raised by this analysis is if we try improve \( \omega  \)
could the actual average reward decrease\emph{, which is what we wanted to maximize
in the first place!} Note that policy iteration simultaneously improves both
these measures on any policy improvement step because the future reward from
every state is increased (with the caveat that the \( \gamma  \) must be large
enough). In general, an improvement of \( \omega  \) could decrease \( \eta  \).
Of course if both \( <Q,f>_{\tilde{m}\pi } \) and \( <Q,f>_{d\pi } \) are
positive then both performance measures improve.

We could force the \( l_{2} \) error \( <\tilde{A}-A,\tilde{A}-A>_{\tilde{m}\pi } \)
to be sufficiently small such that \( <\tilde{A}-A,\tilde{A}-A>_{d\pi } \)
is small as well (this is analogous to a supervised learning problem where we
fit under one distribution and test under another). It should be straight forward
to show that if the error \( <\tilde{A}-A,\tilde{A}-A>_{\tilde{m}\pi } \) is
always smaller than some reasonable\emph{, policy-independent} constant then
either we can detect improvement of \( \omega  \) with a line search \emph{or}
if cannot detect improvement, then the policy is close to optimal. Unfortunately,
we  will not be able to say the same for \( \eta  \) if \( <\tilde{A}-A,\tilde{A}-A>_{d\pi } \)
is smaller than some \emph{policy-independent} constant. The problem is that
\( <\tilde{A}-A,\tilde{A}-A>_{d\pi } \) could be small due to the agent not
visiting states with large advantages. This is essentially the signal to noise
argument revisited. 

The punchline is that we can fit the \( \tilde{A} \) good enough under \( \omega  \),
such that either: 1) \( \omega  \) increases or 2) if we cannot detect improvement
of \( \omega  \), then the policy must have near optimal performance. \emph{Further,
while this is being done, we can also ensure that we never detect (with some
certainty) a decrease in the average reward.} Thus, when doing line searches
we have to check that \emph{both} \( \omega  \) and \( \eta  \) are increasing
or at least non-decreasing (where the noise determines the quality of our checks).
For instance, in example 1, the policy could improve close to the goal state
which would increase \( \omega  \) (and we could detect this increase!). However,
the improvement to the average reward would be undetectable when the policy
is changed at these highly unlikely states. Eventually (when the states close
to goal have a good policy), the states visited with reasonable probability
under the stationary distribution will have large advantages, and then improvement
will be seen in both performance measures.

\textbf{aside: You asked me for an example in which \( \omega  \) could increase
but \( \eta  \) could decrease. Here is an} \textbf{\emph{outline}} \textbf{of
one using an MDP similar to that of example 1 (where the agent could collect
rewards along the way to state 50). Consider that at state 49 we learn some
action to get considerably more reward. However, say at state 35 we don't fit
things good enough and we get a slight decrease in the reward from this state.
Under \( \omega  \), the increase at state 49 is offset by the decrease at
state 35. However, under \( d_{\pi } \), the agent visits 35 much more often
than 49, so the agents average reward could decrease.} \textbf{\emph{On the
bright side, although the true average reward might drop, we certainly won't
be able to detect this drop, since both states are visited so infrequently.}}
\textbf{Obviously, if we fit everything perfectly these are not concerns. Realistically,
what we desire is that if there are some large advantages at states visited
by the agent with reasonable stationary probability, then we should fit these
advantages good enough such that \( \eta  \) also improves in addition to \( \omega  \).
Does that make sense?}

\bibliographystyle{plain}
\bibliography{bib}


\end{document}
