%% LyX 1.1 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{amsart}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{babel}
\usepackage{graphics}
\usepackage{amssymb}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 \theoremstyle{plain}    
 \newtheorem{cor}[thm]{Corollary} %%Delete [thm] to re-start numbering
 \theoremstyle{plain}    
 \newtheorem{lem}[thm]{Lemma} %%Delete [thm] to re-start numbering
 \theoremstyle{definition}
 \newtheorem{defn}[thm]{Definition}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{icml2002}
\usepackage{epsf}

\makeatother
\begin{document}
\twocolumn[
\icmltitle{Approximately Optimal Approximate Reinforcement Learning}

\icmlauthor{Sham Kakade}{sham@gatsby.ucl.ac.uk}
\icmladdress{Gatsby Computational Neuroscience Unit, UCL,
             London WC1N3AR, UK}
\icmlauthor{John Langford}{jcl@cs.cmu.edu}
\icmladdress{Computer Science Department, Carnegie-Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15217}
\vskip 0.3in
]


\begin{abstract}
We make a reduction of the reinforcement learning problem to solving
two types of problems --- {}``How do we gain access to states?{}''
(exploration) and {}``How do we solve a regression problem?{}''
(supervised learning). Given solutions to each of these problems,
our new algorithm: (1) is guaranteed to improve a performance metric
(2) is guaranteed to terminate in a 'small' number of timesteps and
(3) returns an {}``approximately{}'' optimal policy. The quantified
statements of (2) and (3) depend on the quality of the supervised
learning problem solution, but \emph{not} explicitly on the the size
of the state space. 
\end{abstract}

\renewcommand{\baselinestretch}{0.98} \normalsize

\section{Introduction}

In order to solve realistic reinforcement learning problems, it is
critical that approximating algorithms be used. Unfortunately, the
two standard approaches, greedy dynamic programming and policy gradient
methods, can fail to efficiently improve the policy. Approximate value
function methods suffer from a lack of theoretical performance guarantees.
We show how policy gradient techniques can require an unreasonably
large number of samples in order to determine the gradient accurately.
This is due to policy gradient method's fundamental intertwining of
{}``exploration{}'' and {}``exploitation{}''.

Drawing upon the strengths of each approach we propose a new reinforcement
learning algorithm based on two critical observations. First, we need
to improve the policy at states that are visited infrequently under
the current policy, since policy improvement at these states could
ultimately lead to large policy improvement, \emph{ie} we need to
incorporate \emph{exploration}. The second is that we must quantify
how much policy improvement is possible with an approximate scheme.
At one extreme, greedy methods show that if a large policy update
is made then the policy could significantly degrade, while at the
other extreme, for a sufficiently small change to the policy, gradient
methods guarantee performance improvement. We connect these two extremes,
to determine how much policy improvement is possible at finite step
sizes. This allows us to determine how long it takes to obtain some
'approximately' optimal policy. We then show the quality of this 'approximately'
policy is determined both by the level of approximation used and the
how 'exploratory' the start-state distribution is.

The algorithm we present overcomes the problems with both gradient
methods and greedy dynamic programming.


\section{Preliminaries}

A reinforcement learning problem is a finite Markov decision process
(MDP) with rewards. It is defined by the tuple \( (S,D,A,\mathcal{R},P) \)
where: \( S \) is finite set of states, \( D \) is the starting
state distribution, \( A \) is a finite set of actions, \( \mathcal{R} \)
is a reward function \( \mathcal{R}:S\times A\rightarrow [0,R] \),
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. \) 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 \( D \), which has a similar solution
for processes that 'mix' on a reasonable timescale \cite{Sham_colt}.
It is convenient to define a distribution over future states, with
respect to some arbitrary start-state distribution \( \mu  \), in
the following way:\begin{equation}
\label{state_dist.}
d(s|\pi ,\mu ,\gamma )\equiv (1-\gamma )\sum _{t=0}^{\infty }\gamma ^{t}\Pr (s_{t}=s|\pi ,\mu )
\end{equation}
 where \( \Pr (s_{t}=s|\pi ,\mu ) \) is the probability that the
state at time \( t \) is \( s \), under the policy \( \pi  \) and
the start-state distribution \( \mu  \). This is analogous to the
stationary distribution in the infinite time setting, since as \( \gamma \rightarrow 1 \),
\( d(s|\pi ,\mu ,\gamma ) \) tends to the stationary distribution.
For brevity, we will sometimes write this as \( d(s|\pi ) \) when
\( \gamma  \) and \( \mu  \) are clear from context. 

Let \( \delta (s) \) be the distribution over states which concentrates
all mass on state \( s \). We define the value function as the expected
reward under \( \pi (a|s)d(s|\pi ,\delta (s)) \), or\begin{equation}
\label{eq_value}
J_{\pi }(s)\equiv E_{a,s^{\prime }\sim \pi (a|s^{\prime })d(s^{\prime }|\pi ,\delta (s),\gamma )}\mathcal{R}(s^{\prime },a)
\end{equation}
 which is equivalent to the more-standard definition \( J_{\pi }(s)\equiv (1-\gamma )E\{\sum _{t=0}^{\infty }\gamma ^{t}\mathcal{R}(s_{t},a_{t})|\pi ,s_{0}=s\} \).
Note that we are using \emph{normalized} values. The state-action
value is defined as: \( Q_{\pi }(s,a)\equiv (1-\gamma )\mathcal{R}(s,a)+\gamma \sum _{s^{\prime }}p_{ss^{\prime }}^{a}J_{\pi }(s^{\prime }) \),
and the advantage is defined as \( A_{\pi }(s,a)\equiv Q_{\pi }(s,a)-J_{\pi }(s) \).
We will sometimes suppress the \( \pi  \) subscript when the policy
is clear from context. 

The goal of the agent is to maximize the discounted reward from the
start state distribution \( D \),\[
\eta (\pi )\equiv E_{s\sim D}\{J_{\pi }(s)\}\, .\]
A well known result is that a solution exists which simultaneously
maximizes \( J_{\pi }(s) \) for all states. 


\section{The Problems with Current Methods}

We now examine in more detail the problems with approximate value
function methods and policy gradient methods. There are three questions
to which we desire answers to:

\begin{enumerate}
\item Is there some performance measure that is guaranteed to improve at
every step?
\item How difficult is it to verify if a particular update will improve
this measure?
\item After a reasonable number of policy updates, what performance level
is obtained?
\end{enumerate}
We now argue that both greedy dynamic programming and gradient methods
give unsatisfactory answers to these questions. Note that one question
we did not ask is {}``What is the quality of the asymptotic policy?{}''.
We are only interested in policies that we can find in a reasonable
amount of time. Understanding the problems with these current methods
will give insight into our new algorithm, which addresses these three
questions. 


\subsection{The Weakness of Approximate Value Function Methods}

Approximate value function methods suffer from a paucity of theoretical
results on the performance of a policy based on the approximate values.
This leads to weak answers to all three questions.

Let us consider some function approximator \( f(s) \) with the \( l_{\infty } \)-error:\[
\varepsilon =\max _{s}|f(s)-J_{\pi }(s)|\]
where \( \pi  \) is some policy. Let \( J_{g} \) the value of a
greedy policy based on this approximation. We have the following guarantee
(see \cite{bertsekas-book}) for all states \( s \):\begin{equation}
\label{greedy_pi}
J_{g}(s)\geq J_{\pi }(s)-\frac{2\gamma \varepsilon }{1-\gamma }.
\end{equation}
In other words, the performance is guaranteed to not decrease \emph{}by
more than \( \frac{2\gamma \varepsilon }{1-\gamma } \). Question
2 is not applicable since these methods don't guarantee improvement
and a performance measure to check isn't well defined.

For approximate methods, the time required to obtain some performance
level is not well understood. At best, some asymptotic results exist
(see \cite{neuro-programming}) . In contrast, exact value function
methods have bounds showing how fast the values converge to optimal
(see \cite{bertsekas-book}). 


\subsection{The Convergence Problem for Policy Gradients}

For policy gradient techniques, question 1 has the appealing answer
that the performance measure of interest is guaranteed to improve
under gradient descent. We now address question 2 by examining the
situations in which estimating the gradient direction will be difficult.
We show that the lack of exploration in gradient methods translates
into requiring a very large number of timesteps in order to accurately
estimate the gradient \emph{direction}. 

Consider the simple MDP shown in Figure \ref{fig1} (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} \). In general, many MDPs behave in
the following manner: random actions are more likely than not to increase
the distance to the goal state. For these classes of problems (see
\cite{whitehead91complexity}), the expected time to reach the goal
state using undirected exploration, \emph{ie} random walk exploration,
is exponential in the size of the state space. Thus, any on-policy
method will have to run for at least this long before any policy improvement
can occur. In online value function methods, this problem is seen
as a lack of exploration. 


\begin{figure}
\resizebox*{0.45\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}


Any sensible estimate of the gradient without reaching the goal state
would be zero, and obtaining non-zero estimates requires exponential
time with on-policy samples. Importance sampling methods do exist
(see \cite{meuleau01exploration, sutton-off-policy}), but are not
feasible solutions. The reason is that if the agent could follow some
'off-policy' trajectory to reach the goal state in a reasonable amount
of time, the importance weights would have to be exponentially large. 

Note that a zero estimate is a rather accurate estimate of the gradient
in terms of magnitude, but this provides no information about direction.
The direction of the gradient is the crucial quantity of interest
since we must step in the {}``right{}'' direction in order to improve
our policy. Some analysis has been done studying the deviation of
gradient estimates \cite{bartlett00estimation}. However, this analysis
focused on obtaining the policy gradient accurately (within some \( \varepsilon  \)
tolerance) rather than on obtaining the correct sign. This is a crucial
difference because the magnitude of the gradient can be very small
when the policy is far from optimal.


\begin{figure}
\resizebox*{0.07\textwidth}{!}{\includegraphics{figs/twomdp.eps}} \resizebox*{0.3\textwidth}{!}{\includegraphics{figs/fig_score.eps}} \resizebox*{0.3\textwidth}{!}{\includegraphics{figs/fig_stat.eps}} 


\caption{\label{fig2} Example 2: A) See text. B) The average reward vs. time
(on a \protect\( 10^{7}\protect \) scale) of a policy under standard
gradient descent in the limit of an infinitesimally small learning
rate (initial conditions stated in text). C) The stationary probability
of state \protect\( j\protect \) in B vs. time (on a \protect\( 10^{7}\protect \)
scale). }
\end{figure}


Let us give an additional example demonstrating the problems for a
simple two state MDP as shown in Figure \ref{fig2}A, which uses the
common Gibbs table-lookup distribution, \( \tilde{\Pi }_{G}=\{\pi _{\theta }:\pi (a|s)\propto \exp (\theta _{sa})\} \).
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 \) (using \( \pi (a_{1}|i)=.8 \) and \( \pi (a_{1}|j)=.9 \)),
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}B. Figure \ref{fig2}C shows
that this problem is so severe that \( \rho (j) \) drops as low as
\( 10^{-7} \) from it's initial probability of \( .2 \). As in example
1, to obtain a nonzero estimate of the gradient it is necessary to
visit state \( j \). The situation could be even worse with a few
extra states in a chain as in figure \ref{fig1}. 

Although in the limit a good policy might be found, these results
do not bode well for the answer to question 3, which is concerned
with how fast we can get there. These results suggest that in any
reasonable number of steps, a gradient method could end up being trapped
at plateaus where estimating the gradient direction has an unreasonably
large sample complexity. The asymptotic results of standard stochastic
gradient ascent techniques show that as the number of samples go to
\( \infty  \) a local optima is found. Unfortunately, these asymptotic
results hide the sample complexity issues outlined here. Answering
question 3 is crucial to understand how well gradient methods perform,
and (to our knowledge) no such analysis exists.


\section{Approximately Optimal RL}

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 though policy improvement at these
unlikely states might be necessary in order for the agent to achieve
near optimal payoff. Note that in example 1, policy improvement at
state 49 will have little impact on the current performance, since
the agent hardly ever reaches state 49 anyway. However, policy improvement
at these unlikely states can ultimately lead to drastic policy improvement. 

We desire an alternative performance measure that does not down weight
advantages at unlikely states or unlikely actions. A natural candidate
for a performance measure is to weight the improvement from all states
more uniformly (rather than by \( D \)), such as \[
\omega (\pi )=E_{s\sim \mu }\{J_{\pi }(s)\}\, ,\]
 where \( \mu  \) is some 'exploratory' starting state distribution.
To this end, \textbf{\emph{we assume we have the ability to use an
arbitrary start-state distribution \( \mu  \).}} Note that for the
special case when \( \mu =D \) then \( \omega =\eta  \). 

Any optimal policy simultaneously maximizes both \( \omega  \) and
\( \eta  \). Unfortunately, the policy that maximizes \( \omega  \)
within some restricted class of policies may have poor performance
according to \( \eta  \). In general, the quality of the optima of
\( \omega  \) is related to the the quality of the optima under \( \eta  \).

Greedy policy iteration updates the policy to some \( \pi ^{\prime } \)
based on some approximate state-action values. Instead, let us consider
the following more conservative update rule: \begin{equation}
\label{pol_update}
\pi _{\textrm{new}}(a|s)=(1-\alpha )\pi (a|s)+\alpha \pi ^{\prime }(a|s)\, ,
\end{equation}
 for some \( \pi ^{\prime } \) and \( \alpha \in [0,1] \). To guarantee
improvement with \( \alpha =1 \), \( \pi ^{\prime } \) must choose
a better action at every state, or else we could suffer the penalty
shown in equation \ref{greedy_pi}. 


\subsection{Policy Improvement}

A more reasonable situation is one in which we are able to improve
the policy with some \( \alpha >0 \) using a \( \pi ^{\prime } \)
that chooses better actions at most but not all states. Let us define
the \emph{policy advantage} \( \mathbb {A}_{\pi ,\mu }(\pi ^{\prime }) \)
of some policy \( \pi ^{\prime } \) with respect to the policy \( \pi  \)
and the start-state distribution \( \mu  \) to be:\[
\mathbb {A}_{\pi ,\mu }(\pi ^{\prime })\equiv E_{s\sim d(s|\pi ,\mu )}\left[ \sum _{a}\pi ^{\prime }(a|s)A_{\pi }(s,a)\right] \, .\]
 Intuitively, this measures the expected advantage of \( \pi ^{\prime } \)
over \( \pi  \), with respect to the set of states visited under
\( \pi  \). Note that a policy found by one step of policy improvement
will maximize the policy advantage. 

The gradient of a parameterized policy is \[
\nabla \omega =\sum _{s,a}d(s|\pi ,\mu )\nabla \pi (a|s)Q_{\pi }(s,a)\, ,\]
 (see \cite{sutton99policy}). It is straightforward to show that
\( \frac{\partial \omega }{\partial \alpha }|_{\alpha =0}=\frac{1}{1-\gamma }\mathbb {A}_{\pi ,\mu } \),
so the change in \( \omega  \) is: \begin{equation}
\label{local_improve}
\Delta \omega =\frac{\alpha }{1-\gamma }\mathbb {A}_{\pi ,\mu }(\pi ^{\prime })+O(\alpha ^{2})\, .
\end{equation}
 Hence, for sufficiently small \( \alpha  \), policy improvement
can occur if the policy advantage is positive, and at the other extreme
of \( \alpha =1 \), significant degradation could occur. We now connect
these two regimes to determine how much policy improvement is possible.

\begin{thm}
\label{th_bound} Let \( \mathbb {A} \) be the policy advantage of
\( \pi ^{\prime } \) with respect to \( \pi  \) and \( \mu  \).
and let \( \varepsilon =\max _{s}|\sum _{a}\pi ^{\prime }(a|s)A_{\pi }(s,a)| \).
For the update rule \ref{pol_update} and for all \( \alpha \in [0,1] \):\[
\omega (\pi _{\textrm{new}})-\omega (\pi )\geq \frac{\alpha }{1-\gamma }(\mathbb {A}-\frac{2\alpha \gamma \varepsilon }{1-\gamma (1-\alpha )})\, .\]
 
\end{thm}
It is possible to construct a two state example showing this bound
is tight for all \( \alpha  \) though we do not provide this example
here.

The quantity \( \varepsilon  \) is the average advantage, under \( \pi ^{\prime } \),
with the largest magnitude. The first term is analogous to the first
order increase specified in equation \ref{local_improve}, and the
second term is a penalty term. Note that if \( \alpha =1 \), the
bound reduces to \[
\omega (\pi _{\textrm{new}})-\omega (\pi )\geq \frac{\mathbb {A}}{1-\gamma }-\frac{2\gamma \varepsilon }{1-\gamma }\]
 and the penalty term is identical to that of greedy dynamic programming,
where the \( \varepsilon  \) defined here is analogous to max-norm
error (see equation \ref{greedy_pi}). Thus the bound agrees with
the local information provided by the gradient and greedy penalty
when \( \alpha =1 \). 

The following corollary shows that the greater the policy advantage
the greater the guaranteed increase in performance. 

\begin{cor}
\label{cor_improve} Let \( R \) be the maximal possible reward and
\( \mathbb {A} \) be the policy advantage of \( \pi ^{\prime } \)
with respect to \( \pi  \) and \( \mu  \). If \( \mathbb {A}\geq 0 \),
then using \( \alpha =\frac{(1-\gamma )\mathbb {A}}{4R} \) will guarantee
the following policy improvement:\[
\omega (\pi _{\textrm{new}})-\omega (\pi )\geq \frac{\mathbb {A}^{2}}{8R}\, .\]

\end{cor}
\begin{proof}
Using the previous theorem, it is straightforward to show the change
is bounded by \( \frac{\alpha }{1-\gamma }(\mathbb {A}-\alpha \frac{2R}{1-\gamma }) \).
The corollary follows by choosing the \( \alpha  \) that maximizes
this bound.
\end{proof}

\subsection{The answer to question 3}

We address question 3 by first addressing how fast we converge to
some policy then bounding the quality of this policy. Naively, we
expect our ability to obtain policies with large advantages to affect
the speed of improvement and the quality of the final policy. Instead
of explicitly suggesting algorithms that obtain policies with large
advantages, we assume access to an algorithm that solves this problem.
Let us call this \( \varepsilon  \)-good algorithm \( BlackBox_{\varepsilon }(\pi ,\mu ) \),
which is defined as:

\begin{defn}
\( BlackBox_{\varepsilon }(\pi ,\mu ) \) is a function of a policy
\( \pi  \) and start-state distributions \( \mu  \) which returns
a policy \( \pi ^{\prime } \) such that \( \mathbb {A}_{\pi ,\mu }(\pi ^{\prime })\geq \textrm{OPT}(\mathbb {A}_{\pi ,\mu })-\varepsilon  \),
where \( \textrm{OPT}(\mathbb {A}_{\pi ,\mu })=\max _{\pi ^{\prime }}\mathbb {A}_{\pi ,\mu }(\pi ^{\prime }) \).
\end{defn}
We drop the \( \mu  \) dependence when clear. In the discussion,
we show how a supervised learning algorithm that fits the advantages
with an \( l_{1} \)-error of \( \frac{\varepsilon }{2} \) is sufficient
to construct such a \( BlackBox_{\varepsilon } \) (though direct
policy methods could also be sufficient).

The {}``breaking point{}'' of our supervised learning algorithm
is reached when it is no longer guaranteed to return a policy with
a positive policy advantage (i.e. when \( \textrm{OPT}(\mathbb {A}_{\pi ,\mu })-\varepsilon <0 \)).

For simplicity, we assume we have knowledge of \( \varepsilon  \).
A crude outline of the \emph{Conservative Policy Iteration} algorithm
is:

\begin{enumerate}
\item Call \( BlackBox_{\varepsilon }(\pi ,\mu ) \) to obtain some \( \pi ^{\prime } \)
\item Use \( O(\frac{R^{2}}{\varepsilon ^{2}}\log \frac{R^{2}}{\delta \varepsilon ^{2}}) \)
samples to obtain a Monte Carlo estimate \( \mathbb {\hat{A}} \)
of \( \mathbb {A}_{\pi ,\mu }(\pi ^{\prime }) \).
\item If \( \mathbb {\hat{A}}<\frac{2\varepsilon }{3} \), STOP and return
\( \pi  \).
\item If \( \mathbb {\hat{A}}\geq \frac{2\varepsilon }{3} \), then update
policy \( \pi  \) according to equation \ref{pol_update} using \( \frac{(1-\gamma )(\mathbb {\hat{A}}-\frac{\varepsilon }{3})}{4R} \)
and return to step 1. 
\end{enumerate}
The following theorem shows that in polynomial time, the algorithm
finds a policy \( \pi  \) that is 'close' to the break-point of the
black box. 

\begin{thm}
\label{th_steps} With probability at least \( 1-\delta  \), conservative
policy iteration will: i) improve \( \omega  \) with every policy
update, ii) cease in at most \( 72\frac{R^{2}}{\varepsilon ^{2}} \)
calls to \( BlackBox_{\varepsilon }(\pi ,\mu ) \), and iii) return
a policy \( \pi  \) such that \( \textrm{OPT}(\mathbb {A}_{\pi ,\mu })<2\varepsilon  \). 
\end{thm}
The proof is in the next section. 

To complete the answer to question 3, we need to address the quality
of the policy found by this algorithm. Note that our algorithm ceases
in an amount of time that does not depend on the start-state distribution
\( \mu  \) used though the policy \( \pi  \) that we find will depend
on \( \mu  \) since \( \textrm{OPT}(\mathbb {A}_{\pi ,\mu })<2\varepsilon  \).
If \( d(s|\mu ) \) is highly non-uniform, then a small policy advantage
will not necessarily imply that all advantages will be small. If there
are any large advantages, the policy could be far from optimal. The
following theorem quantifies this. We use standard definition of the
\( l_{\infty } \)-norm for some vector \( f(s) \), \( ||f||_{\infty }\equiv \max _{s}f(s) \).

\begin{thm}
\label{th_quality}(simple version) Assume we have some \( \pi  \)
such that \( \textrm{OPT}(\mathbb {A}_{\pi })<\varepsilon  \). Let
\( \pi ^{*} \) be an optimal policy. Then \[
\max _{s}|J_{\pi }(s)-J_{\pi _{*}}(s)|\leq \frac{\varepsilon }{(1-\gamma )}\left\Vert \frac{d(s|\pi ^{*},\mu ^{\prime })}{d(s|\pi ,\mu )}\right\Vert _{\infty }\, .\]

\end{thm}
The proof is provided later in the paper. This bound elucidates the
problem of using the given start-state distribution, \( D \), instead
of a more uniform distribution. The reason is that if \( d(s|\pi ,D) \)
does not give weight to any state where the optimal visits, then the
policy could be far from optimal. The factor of \( \left\Vert \frac{d(s|\pi ^{*},\mu ^{\prime })}{d(s|\pi ,\mu )}\right\Vert _{\infty } \)
represents a mis-match between the distribution of states of the current
policy and that of the optimal policy. Intuitively, weight must be
given to all states that the optimal could visit. The use of a uniform
metric will bound \( d(s|\pi ,\textrm{uniform})\geq \frac{1-\gamma }{\textrm{size of state space}} \).
Essentially, exploration is necessary to improve the policy at these
unlikely states.

We now discuss and prove these theorems in more detail.


\section{Conservative Policy Iteration}

After our black box returns some policy \( \pi ^{\prime } \), we
must address how to update the policy. If we knew the policy advantage
of this policy was \( \mathbb {A} \) and if \( \mathbb {A}>0 \),
then we could use \( \alpha =\frac{(1-\gamma )\mathbb {A}}{4R} \).

Let us address how many samples are required to accurately determine
\( \mathbb {A}_{\pi }(\pi ^{\prime }) \). We must specify a sampling
model to estimate the policy advantage. It is straightforward to show
that the policy advantage can be written as \( \mathbb {A}_{\pi ,\mu }(\pi ^{\prime })=E_{s\sim d(s|\pi ,\mu )}\left[ \sum _{a}(\pi ^{\prime }(a|s)-\pi (a|s))Q(s,a)\right]  \)
which is a more convenient form since we can directly estimate the
state-action values. 

Each sample required will consist of a sample \( s \) from from \( d(s|\pi ,\mu ) \),
an \( a \) from the uniform distribution, and a nearly unbiased estimate
\( \hat{Q}(s,a) \) of \( Q_{\pi }(s,a) \). Then, we can use Monte
Carlo integration in order to estimate the value of \( \mathbb {A}_{\pi ,\mu }(\pi ^{\prime }) \).
Given certain assumptions, it is reasonable to suppose that we can
obtain these samples in an on-policy manner, using a sample from \( \mu  \)
and \( O(\frac{1}{1-\gamma }) \) transitions in our MDP. This can
be done by first drawing a state \( s \) from \( d(s|\pi ,\mu ) \),
which can be done by acting in the MDP. Then we choose an action \( a \)
from the uniform distribution and obtain an estimate \( \hat{Q}(s,a) \)
of the \( Q(s,a) \) value, by acting according to the policy for
\( O(\frac{1}{1-\gamma }) \) steps. We use importance sampling with
a uniform proposal distribution over the actions to estimate the policy
advantage. We do not use \( \pi  \) or \( \pi ^{\prime } \) as the
importance distribution, since if either of these are deterministic
the importance weights may be large. The estimate of the policy advantage
from the \( i \)-th sample will be \( x_{i}=n_{a}\hat{Q}_{i}(s,a)(\pi ^{\prime }(a|s)-\pi (a|s)) \)
where \( n_{a} \) is the number of actions. 

How many samples are required? Since \( \hat{Q}_{i}\in [0,R] \),
our samples satisfy \( x_{i}\in [-n_{a}R,n_{a}R] \). Using Hoeffding's
inequality for \( k \) independent identical random variables, we
have: \begin{equation}
\label{hoeffding}
\Pr \left( |\mathbb {A}-\mathbb {\hat{A}}|>\delta \right) \leq 2e^{-\frac{k\delta ^{2}}{2n_{a}^{2}R^{2}}}\, ,
\end{equation}
 where \( \mathbb {\hat{A}}=\frac{1}{k}\sum _{i=1}^{k}x_{i} \). Hence,
the number of samples required to obtain a \( \delta  \) accurate
sample with a fixed error rate is \( O\left( \frac{n_{a}^{2}R^{2}}{\delta ^{2}}\right)  \).
Consequently, if the policy advantage is large then few samples will
be needed. 

Now the proof of the conservative policy iteration algorithm is straightforward:

\begin{proof}
There are three statements, that must all hold with probability \( 1-\delta  \),
--- \( \omega  \) improves at every step, the algorithms ceases in
\( \frac{72R^{2}}{\varepsilon ^{2}} \) iterations, and the policy
found has maximal policy advantage less than \( 2\varepsilon  \).
Let us assume that every time we make a Monte-Carlo estimate of the
policy advantage, our estimate \( \mathbb {\hat{A}} \) of the policy
advantage satisfies \( |\mathbb {A}-\mathbb {\hat{A}}|<\frac{\varepsilon }{3} \).
We estimate the probability this assumption fails later.

The assumption implies that if we observe \( \mathbb {\hat{A}}\geq \frac{2\varepsilon }{3} \),
then \( \mathbb {A}\geq \frac{\varepsilon }{3} \). By corollary \ref{cor_improve},
step 4 will guarantee improvement of \( \frac{\left( \mathbb {\hat{A}}-\frac{\varepsilon }{3}\right) ^{2}}{8R}\geq \frac{\varepsilon ^{2}}{72R} \)
using \( \alpha =\frac{(1-\gamma )(\mathbb {\hat{A}}-\frac{\varepsilon }{3})}{4R} \).
Since \( 0\leq \omega \leq R \), there are at most \( \frac{72R^{2}}{\varepsilon ^{2}} \)
steps before \( \omega  \) becomes larger than \( R \), so the algorithm
must cease in this time. Our algorithm ceases and returns \( \pi  \)
when we observe that the policy advantage of some \( \pi ^{\prime } \)
satisfies \( \mathbb {\hat{A}}_{\pi }(\pi ^{\prime })<\frac{2\varepsilon }{3} \)
which implies \( \mathbb {A}_{\pi }(\pi ^{\prime })<\varepsilon  \).
By definition of the black box, it follows that \( \textrm{OPT}(\mathbb {A}_{\pi })<2\varepsilon  \). 

To obtain an error probability of less than \( \delta  \), we must
obtain enough samples such that \( |\mathbb {A}-\mathbb {\hat{A}}|<\frac{\varepsilon }{3} \)
for every loop of the algorithm, and there are at most \( \frac{72R^{2}}{\varepsilon ^{2}} \)
loops. By the union bound and inequality \ref{hoeffding}, we have
\( \frac{72R^{2}}{\varepsilon ^{2}}2e^{-\frac{k\varepsilon ^{2}}{2n_{a}^{2}R^{2}}}<\delta  \),
and so when \( O\left( \frac{R^{2}}{\varepsilon ^{2}}\log \frac{R^{2}}{\delta \varepsilon ^{2}}\right)  \)
samples are used, the probability of failure is less than \( \delta  \).
\end{proof}

\section{How Good is The Policy Found?}

The speed with which our algorithm ceases does not depend on the
start-state distribution used. However, we now show that the quality
of the resulting policy could strongly depend on this distribution.

The following lemma will be useful:

\begin{lem}
\label{lem-advantage}For any policy \( \tilde{\pi } \) and start-state
distribution \( \mu  \), \[
\omega _{\tilde{\pi }}(s)-\omega _{\pi }(s)=\frac{1}{1-\gamma }E_{s,a\sim d(s|\tilde{\pi },\mu )\tilde{\pi }}\{A_{\pi }(s,a)\}\]

\end{lem}
\begin{proof}
Let \( d_{t}(s) \) be probability that the state at time \( t \)
is \( s \) while following \( \tilde{\pi } \) under the start-state
distribution \( \mu  \). We have \begin{eqnarray*}
 &  & \omega (\tilde{\pi })\\
 & = & (1-\gamma )\sum _{t=0}^{\infty }\gamma ^{t}E_{s,a\sim d_{t}\tilde{\pi }}\{\mathcal{R}(s,a)\}\\
 & = & \sum _{t=0}^{\infty }\gamma ^{t}E_{s,a\sim d_{t}\tilde{\pi }}\{(1-\gamma )\mathcal{R}(s,a)-J_{\pi }(s)+J_{\pi }(s)\}\\
 & = & E_{s\sim d_{0}}\{J_{\pi }(s)\}\\
 &  & +\sum _{t=0}^{\infty }\gamma ^{t}E_{s',s,a\sim d_{t+1}d_{t}\tilde{\pi }}\{(1-\gamma )\mathcal{R}(s,a)+\gamma J_{\pi }(s')-J_{\pi }(s)\}\\
 & = & \omega (\pi )+\sum _{t=0}^{\infty }\gamma ^{t}E_{s,a\sim d_{t}\tilde{\pi }}\{A_{\pi }(s,a)\}\\
 & = & \omega (\pi )+\frac{1}{1-\gamma }E_{s,a\sim d(s|\tilde{\pi },\delta (s))\tilde{\pi }}\{A_{\pi }(s,a)\}\, .
\end{eqnarray*}
 
\end{proof}
This lemma elucidates a a fundamental \emph{measure mismatch} in reinforcement
learning, which we now analyse. The performance measure of interest,
\( \eta (\pi ) \) (defined with respect to start-state distribution
\( D \)), changes in proportion the policy advantage \( \mathbb {A}_{\pi ,D}(\pi ^{\prime }) \)
for small \( \alpha  \) when using our update rule (see equation
\ref{local_improve}). A resulting improvement of \( \frac{\mathbb {A}^{2}}{8R} \)
can be guaranteed if \( \mathbb {A}\geq 0 \). Recall that the policy
advantage is just the expected advantage under the distribution \( d(s|\pi ,D)\pi ^{\prime }(a|s) \).
However, the difference between \( \eta  \) and \( \eta ^{*} \)
is the average advantage under \( d(s|\pi ^{*},D)\pi ^{*}(a|s) \),
where \( \pi ^{*} \) is an optimal policy. Thus, if \( \mathbb {A}_{\pi ,D}(\pi ^{\prime }) \)
is small and \( D \) is highly non-uniform, this will not imply that
\( \eta  \) is close to optimal. For example, there could still be
some large advantages where \( d(s|\pi ,D) \) is small and \( d(s|\pi ^{*},D) \)
is large. Also, with \( \mathbb {A}_{\pi ,D}(\pi ^{\prime }) \) small,
little improvement is guaranteed and even detecting if the policy
advantage is positive (\( \mathbb {A}_{\pi ,D}(\pi ^{\prime })\geq 0 \))
will have large sample complexity. Intuitively, this is the situation
where large advantages are at states with low probabilities of being
visited under the current policy (as in examples 1 and 2).

We now quantify how far from optimal the resulting policy is using
some start-state distribution \( \mu  \).

\begin{thm}
\label{th_high_quality}Assume we have some \( \pi  \) such that \( \textrm{OPT}(\mathbb {A}_{\pi ,\mu })<\varepsilon  \).
For any policy \( \tilde{\pi } \) and for any \( \mu ^{\prime } \),
\begin{eqnarray*}
\omega _{\mu ^{\prime }}(\tilde{\pi })-\omega _{\mu ^{\prime }}(\pi )\leq \frac{\varepsilon }{(1-\gamma )}\left\Vert \frac{d(s|\tilde{\pi },\mu ^{\prime })}{d(s|\pi ,\mu )}\right\Vert _{\infty } &  & \\
\leq \frac{\varepsilon }{(1-\gamma )^{2}}\left\Vert \frac{d(s|\tilde{\pi },\mu ^{\prime })}{\mu }\right\Vert _{\infty }\, . &  & 
\end{eqnarray*}

\end{thm}
\begin{proof}
The optimal policy advantage is \( \textrm{OPT}(\mathbb {A}_{\pi ,\mu })=\sum _{s}d(s|\pi ,\mu )\max _{a}A_{\pi }(s,a) \).
Therefore, \begin{eqnarray*}
\varepsilon  & > & \sum _{s}\frac{d(s|\pi ,\mu )}{d(s|\tilde{\pi },\mu ^{\prime })}d(s|\tilde{\pi },\mu ^{\prime })\max _{a}A_{\pi }(s,a)\\
 & \geq  & \min _{s}\left( \frac{d(s|\pi ,\mu )}{d(s|\tilde{\pi },\mu ^{\prime })}\right) \sum _{s}d(s|\tilde{\pi },\mu ^{\prime })\max _{a}A_{\pi }(s,a)\\
 & \geq  & \left\Vert \frac{d(s|\tilde{\pi },\mu ^{\prime })}{d(s|\pi ,\mu )}\right\Vert _{\infty }^{-1}\sum _{s,a}d(s|\tilde{\pi },\mu ^{\prime })\tilde{\pi }(a|s)A_{\pi }(s,a)\\
 & = & (1-\gamma )\left\Vert \frac{d(s|\tilde{\pi },\mu ^{\prime })}{d(s|\pi ,\mu )}\right\Vert _{\infty }^{-1}(\omega _{\mu ^{\prime }}(\tilde{\pi })-\omega _{\mu ^{\prime }}(\pi ))
\end{eqnarray*}
where the last step follows from lemma \ref{lem-advantage}. The second
inequality is due to \( \min _{s}d(s|\pi ,\mu )\leq (1-\gamma )\min _{s}\mu (s) \).
\end{proof}
Note that \( \left\Vert \frac{d(s|\pi ^{*},\mu ^{\prime })}{\mu }\right\Vert _{\infty } \)
is a measure of the mismatch in using \( \mu  \) rather than the
start-state distribution of an optimal policy. The interpretation
of each factor of \( \frac{1}{1-\gamma } \) is important. In particular,
one factor of \( \frac{1}{1-\gamma } \) is due to the fact that policy
is \( \frac{1}{1-\gamma } \) times the average advantage (under \( d(s|\pi ^{*}) \))
away from optimal and another factor of \( \frac{1}{1-\gamma } \)
is due to the inherent un-uniformity of \( d(s|\pi ,\mu ) \). 


\section{Discussion}

We have provided an algorithm that finds an {}``approximately{}''
optimal solution that is polynomial in the approximation parameter
\( \varepsilon  \), but not in the size of the state space. We discuss
the difficulty of constructing our \( BlackBox \) function and also
make a few other points. 


\subsection{The Black Box Algorithm}

The ability to find a policy with a large policy advantage can be
stated as a supervised learning problem, though we do not specify
the sample complexity of this supervised learning problem. Let us
consider the loss given by:\[
E_{s\sim d(s|\pi ,\mu )}\max _{a}|A_{\pi }(s,a)-f_{\pi }(s,a)|\, .\]
This loss is an \emph{average} loss over the state space (though it
is an \( \infty  \)-loss over actions). It is in general much more
tractable to deal with an average loss than an \( \infty  \)-loss
over the state-space. In general, it is the \( \infty  \)-loss that
is the relevant measure for greedy dynamic programming (see equation
\ref{greedy_pi} and \cite{neuro-programming}).

It is straightforward to see that if we can keep this error below
\( \varepsilon  \), then we can construct an \( 2\varepsilon  \)-good
black box by choosing \( \pi ^{\prime }(a|s) \) to be nonzero only
for actions in \( \textrm{argmax}_{a}f(s,a) \). Thus, the difficulty
of constructing an \( 2\varepsilon  \)-good black box is at most
as difficult as solving a regression problem with \( \varepsilon  \)
loss. 

Direct policy search methods could also be used to construct this
\( BlackBox \). Equation \ref{hoeffding} states that the sample
complexity of determining the policy advantage to \( \delta  \) accuracy
is \( O\left( \frac{n_{a}^{2}R^{2}}{\delta ^{2}}\right)  \), which
is related to the sample complexity of searching a set of polices
to obtain one with the largest policy advantage. 


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

Eventhough we ultimately seek to have good performance measure under
\( \eta  \) (which is under \( D \)), we show that it is important
to improve the policy under a somewhat uniform measure. An interesting
question is {}``Can we improve the policy according to both \( \eta  \)
and \( \omega  \) (which is under \( \mu  \)) at each update?{}''
In general the answer is {}``no{}'', but consider improving the
performance under \( \tilde{\mu }=(1-\beta )\mu +\beta D \) instead
of just \( \mu  \). This metric only slightly changes the quality
of the asymptotic policy. However, by giving weight to \( D \), the
possibility of improving \( \eta  \) is allowed if the optimal policy
has large advantages under \( D \). Essentially if \( \textrm{OPT}(\mathbb {A}_{\pi ,D}) \)
is large (greater than \( \frac{\varepsilon }{\beta } \)) , then
finding a policy with large policy advantage with respect to \( \tilde{\mu } \),
will also find a policy with large policy advantage under \( D \).
Joint improvement will be possible for this case, with an appropriate
setting of \( \alpha  \). 

The only situation where joint improvement with \( \eta  \) is not
possible is when \( \textrm{OPT}(\mathbb {A}_{\pi ,D}) \) is small.
However, this is just the usual problematic case where, under \( D \),
the large advantages are inaccessible.


\subsection{Prior Knowledge}

A very interesting suggestion of how to chose \( \mu  \), is to use
prior knowledge of which states an optimal policy tends to visit or
where any good policy tends to visit. The bounds we have presented
show directly the importance of ensuring the agent starts in states
where the optimal tends to visit. 


\subsection{Practical Variants}

The algorithms we have suggested leads to a variety of practical variants.
The most pragmatic for doing greedy dynamic programming is to fit
the value functions under a more uniform metric and to use a line
search over \( \alpha  \) with the greedy policy, rather than using
the greedy \( \alpha =1 \). Further tricks must be done to ensure
a compact representation of the policy. The most pragmatic variant
for using gradient methods is to use a more uniform start state distribution,
and then decay the distribution \( \mu  \) to \( D \). 


\subsection*{Acknowledgments}

We give many thanks to Peter Dayan for suggestions on what constitutes
efficient learning.

\bibliographystyle{plain}
\bibliography{bib}



\section{Appendix: Proof of Theorem\ref{th_bound}}

The intuition for the proof is that \( \alpha  \) determines the
probability of choosing a 'deviant' action from \( \pi ^{\prime } \).
If the current state distribution is \( d(s|\pi ,\mu ) \) when an
action from \( \pi ^{\prime } \) is chosen, then the performance
change from this deviant action will be proportional to the policy
advantage. The first deviant action will be chosen when the state
distribution is approximately \( d(s|\pi ,\mu ) \), and in the worst
case scenario, all following deviant actions could be chosen when
the state distribution is arbitrarily different. The penalty for the
approximation in the former and the worst-case situation in the latter
will be approximately \( \varepsilon  \). 

\begin{proof}
The expected advantage with respect to \( \pi _{\textrm{new}} \)
is,\begin{eqnarray*}
 &  & E_{a\sim \pi _{\textrm{new}}(a|s)}\{A_{\pi }(s,a)\}\\
 & = & \sum _{a}((1-\alpha )\pi (a|s)+\alpha \pi ^{\prime }(a|s))A_{\pi }(s,a)\\
 & = & \alpha \sum \pi ^{\prime }(a|s)A_{\pi }(s,a)\\
 & = & \alpha E_{a\sim \pi ^{\prime }(a|s)}\{A_{\pi }(s,a)\}\, .
\end{eqnarray*}
 For any timestep, the probability that we choose an action according
to \( \pi ^{\prime } \) is \( \alpha  \). Let \( c_{t} \) be the
random variable indicating the number of actions chosen from \( \pi ^{\prime } \)
before time \( t \). In particular, while no action has been chosen
from \( \pi ^{\prime } \) we have \( c_{t}=0 \) and after one action
has been chosen \( c_{t}=1 \). Hence, \( \Pr (c_{t}=0)=(1-\alpha )^{t} \)
and \( \Pr (c_{t}\geq 1)=1-(1-\alpha )^{t} \). For any \( \pi ^{\prime } \),
let \( d_{t}(s|\pi ^{\prime }) \) be the probability that the state
at time \( t \) is \( s \) while following \( \pi ^{\prime } \)
under the start-state distribution \( \mu  \). It follows that for
all timesteps \( t \):\begin{eqnarray*}
 &  & E_{a,s\sim \pi _{\textrm{new}}(a|s)d_{t}(s|\pi _{\textrm{new}})}A_{\pi }(s,a)\\
 & = & \alpha E_{a,s\sim \pi ^{\prime }(a|s)d_{t}(s|\pi _{\textrm{new}})}A_{\pi }(s,a)\\
 & = & \alpha \Pr (c_{t}=0)E_{a,s\sim \pi ^{\prime }(a|s)d_{t}(s|\pi _{\textrm{new}},c_{t}=0)}A_{\pi }(s,a)\\
 &  & +\alpha \Pr (c_{t}\geq 1)E_{a,s\sim \pi ^{\prime }(a|s)d_{t}(s|\pi _{\textrm{new}},c_{t}\geq 1)}A_{\pi }(s,a)\\
 & \geq  & \alpha (1-\Pr (c_{t}\geq 1))E_{a,s\sim \pi ^{\prime }(a|s)d_{t}(s|\pi _{\textrm{new}},c_{t}=0)}A_{\pi }(s,a)\\
 &  & -\alpha \Pr (c_{t}\geq 1)\varepsilon \\
 & \geq  & \alpha E_{a,s\sim \pi ^{\prime }(a|s)d_{t}(s|\pi _{\textrm{new}},c_{t}=0)}A_{\pi }(s,a)-2\alpha \Pr (c_{t}\geq 1)\varepsilon \\
 & = & \alpha E_{a,s\sim \pi ^{\prime }(a|s)d_{t}(s|\pi )}A_{\pi }(s,a)-2\alpha (1-(1-\alpha )^{t})\varepsilon 
\end{eqnarray*}
 where we have used the definition of \( \varepsilon  \) and \( d_{t}(s|\pi _{\textrm{new}},c_{t}=0)=d_{t}(s|\pi ) \). 

By substitution and lemma \ref{lem-advantage}, we have:\begin{eqnarray*}
 &  & \omega (\pi _{\textrm{new}})-\omega (\pi )\\
 & = & \frac{1}{1-\gamma }E_{a,s\sim \pi _{\textrm{new}}(a|s)d(s|\pi _{\textrm{new}})}A_{\pi }(s,a)\\
 & = & \sum _{t=0}^{\infty }\gamma ^{t}E_{a,s\sim \pi _{\textrm{new}}(a|s)d_{t}(s|\pi _{\textrm{new}})}\{A_{\pi }(s,a)\}\\
 & \geq  & \sum _{t=0}^{\infty }\gamma ^{t}(\alpha \sum _{s,a}d_{t}(s|\pi )\pi ^{\prime }(a|s)A_{\pi }(s,a)-2\alpha (1-(1-\alpha )^{t})\varepsilon )\\
 & = & \frac{\alpha }{(1-\gamma )}E_{a,s\sim \pi ^{\prime }(a|s)d(s|\pi )}A_{\pi }(s,a)-2\alpha \varepsilon \sum _{t=0}^{\infty }\gamma ^{t}(1-(1-\alpha )^{t})\\
 & = & \alpha \frac{\mathbb {A}_{\pi }(\pi ^{\prime })}{(1-\gamma )}-2\alpha \varepsilon (\frac{1}{1-\gamma }-\frac{1}{1-\gamma (1-\alpha )})\, .
\end{eqnarray*}
 The result follows from simple algebra.\end{proof}

\end{document}
