%% This LaTeX-file was created by <jl> Wed Jan 30 12:54:34 2002
%% LyX 1.0 (C) 1995-1999 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass[english]{amsart}
\usepackage[T1]{fontenc}
\usepackage[auto]{inputenc}
\usepackage{babel}
\usepackage{graphics}

\makeatletter


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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\theoremstyle{plain}    
\newtheorem{thm}{Theorem}[section]
\numberwithin{equation}{section} %% Comment out for sequentially-numbered
\numberwithin{figure}{section} %% Comment out for sequentially-numbered
\theoremstyle{plain}    
\newtheorem{cor}[thm]{Corollary} %%Delete [thm] to re-start numbering
\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}


\title{``Approximately'' Optimal Reinforcement Learning in Polynomial Time}

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

\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 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. We have available a companion {*}{*}tech{*}{*}
report with more detailed proofs.


\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 to obtain a non-zero estimate would require exponential time with
on-policy samples. Importance sampling methods do exist (see \cite{meuleau01exploration, sutton-off-policy}),
but would not be a feasible solution. 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 Reinforcement Learning}

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}
In ({*}{*}tech{*}{*}), we have a two state example showing this bound is tight. 

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{th_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}}) \)
Monte Carlo estimates to obtain an 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 (see {*}{*}tech report{*}{*}). 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_how_far},
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_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 dimensionality 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
losss than an \( \infty  \)-loss over the state-space, which is the appropriate
loss 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 lead 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 one could additionally decay this distribution \( \mu  \) to \( D \). 


\subsection*{Acknowledgements}

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

\bibliographystyle{plain}
\bibliography{bib.bib}



\section{Appendix: Outline of 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}
