%% This LaTeX-file was created by <jl> Sun Jan 27 13:08:20 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}
\theoremstyle{remark}    
\newtheorem{acknowledgement}[thm]{Acknowledgement} 

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

\begin{document}


\title{Reinforcement Learning: How to do It.}

\begin{abstract}
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 efficently
improve the policy. Approximate value function methods suffer from a lack of
theoretical performance guarentees. 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 with strong performance
guarantees given some quantifiable degree of approximation. We reduce the reinforcement
learning problem to solving two types of problems --- (1) ``How do we gain
access to states?'' (exploration) and (2) ``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. 
\end{abstract}
\maketitle

\section{Introduction}

todo:

\begin{enumerate}
\item Talk about notions of optimality given function approximation.
\item Name algorithm.
\item Fit proofs into itsy bitsy columns
\item title for big pic 
\end{enumerate}
We present a new algorithm which allows efficient approximate planning. We will
first discuss the problems with the current methods. Then we will present our
algorithm which allows near optimal 'approximate' planning. A crucial notion
is that our algorithm will be able to improve using an approximation scheme.
The approximation scheme is essentially a supervised learning problem. The quality
of the resulting policy found and the speed with which this policy is found
depend on the quality of this approximating scheme.


\section{Preliminaries}

A reinforcement learning problem is a finite Markov decision process (MDP) with
rewards which is a 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}
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 usual definition of \( J_{\pi }(s)\equiv (1-\gamma )E\{\sum _{t=0}^{\infty }\gamma ^{t}\mathcal{R}(s_{t},a_{t})|\pi ,s_{0}=s\} \),
except 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 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 asymptopic
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{The Big Pic}

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

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. 

\begin{thm}
\label{th_improve}Let \( \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} \) with the update rule
\[
\pi _{\textrm{new}}(a|s)=(1-\alpha )\pi (a|s)+\alpha \pi ^{\prime }(a|s)\]
 will guarantee the following policy improvement:
\[
\omega (\pi _{\textrm{new}})-\omega (\pi )\geq \frac{\mathbb {A}^{2}}{8R}\, .\]

\end{thm}
Hence, the greater the policy advantage the greater the guaranteed increase
in performance. 

We now address question 3, by first addressing how fast we converge to some
policy then we bound the quality of this policy. Naively, we would expect our
ability to obtain policies with large advantages to effect the speed of improvement
and the quality of the final policy. Instead of explicitly suggesting algorithms
that obtain policies with large policy advantages (which could be done using
either value function methods or direct policy search methods), we make an assumption
about the quality of this 'black box'. We assume access to an \( \varepsilon  \)-good
black box defined as:

We now 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 effect 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 such 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
an supervised learning algorithm that fits the advantages with an \( l_{1} \)-error
of \( \varepsilon  \) 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 algorithm we suggest 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  \), algorithm {*}{*}
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 })<2\varepsilon  \). 
\end{thm}
To complete the answer to question 3, we need to address the quality of the
policy found by this algorithm. 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}
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 ,\mu ) \)
does not give weight to any state where the optimal visits, then the policy
could be far from optimal. Intuitively, the maximal policy advantage with respect
to \( \pi  \) can be small even if there exist large advantages (\( A_{\pi }(s,a) \)).
The presence of large advantages, even at states not currently visited, leaves
open the possibility that \( \pi  \) is far from optimal. Exploration is necessary
to improve the policy at these unlikely states. The use of a uniform metric
will bound \( d(s|\pi ,\textrm{uniform})\geq \frac{1-\gamma }{\textrm{size of state space}} \). 

We now discuss and prove these theorems in more detail.


\section{Policy Improvement}

We now prove theorem \ref{th_improve}. First, let us examine, the policy change
for small \( \alpha  \). 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}), which is equivalent to \( E_{s\sim d(s|\pi ,\mu )}\sum _{a}\nabla \pi (a|s)A_{\pi }(s,a) \).
Therefore,
\begin{eqnarray*}
\frac{\partial \omega }{\partial \alpha }|_{\alpha =0} & = & \frac{\sum _{s,a}d(s|\pi ,\mu )(\pi ^{\prime }(a|s)-\pi (a|s))A_{\pi }(s,a)}{1-\gamma }\\
 & = & \frac{1}{1-\gamma }\sum _{s,a}d(s|\pi ,\mu )\pi ^{\prime }(a|s)A_{\pi }(s,a)
\end{eqnarray*}
since \( \sum _{a}\pi (a|s)A_{\pi }(s,a)=0 \). 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.

The following lemma will be useful throughout:

\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}
The following theorem bounds the policy change for all \( \alpha  \).

\begin{thm}
\label{how_far_go}Let \( \mathbb {A} \) be the policy advantage of \( \pi ^{\prime } \)
with respect to the policy \( \pi  \) and the distribution \( \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}
Before we state the proof, let us examine this result. The quantity \( \varepsilon  \)
is the largest average advantage, under \( \pi ^{\prime } \). 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 \( \gamma =0 \) then there
is no penalty, so using \( \alpha =1 \) will not result in policy degradation.
Also 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 (see
equation \ref{greedy_pi}). 

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 expectated advatage 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}
Appendix {*}{*} gives an example showing this bound is tight for all \( \alpha  \). 

\begin{cor}
\label{cor_how_far}Under the assumptions in the previous theorem and that \( R \)
is the maximum possible reward, then
\[
\omega (\pi _{\textrm{new}})-\omega (\pi )\geq \frac{\alpha }{1-\gamma }(\mathbb {A}-\alpha \frac{2R}{1-\gamma })\, .\]
 
\end{cor}
\begin{proof}
The bound is a straightforward result of the previous theorem, using the fact
that \( \varepsilon  \) is bounded by \( R \). 
\end{proof}
Theorem 1 follows by choosing the \( \alpha  \) that maximizes the lower bound
in this corollary.


\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 ) \)
and a nearly unbiased estimate \( \hat{Q}(s,a) \) of \( Q_{\pi }(s,a) \) for
some \( a \). Given certain assumptions (see section \ref{sec-monte}), it
is reasonable to suppose that we can obtain these samples in an on-policy manner,
in using a sample from \( \mu  \) and \( O(\frac{1}{1-\gamma }) \) transitions
in our MDP (see {*}tech report{*}). Then, we can use monte carlo integration
in order to estimate the value of \( \mathbb {A}_{\pi ,\mu }(\pi ^{\prime }) \).
This can be done by first drawing a state \( s \) from \( d(s|\pi ,\mu ) \)
Then, we can use importance sampling with a uniform proposal distribution over
the actions to choose an action \( a \). 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}}|>\epsilon \right) \leq 2e^{-\frac{k\epsilon ^{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 achieve a fixed error rate is \( O\left( \frac{n_{a}^{2}R^{2}}{\mathbb {A}^{2}}\right)  \)
and the number of MDP transitions required is \( O\left( \frac{n_{a}^{2}R^{2}}{\mathbb {A}^{2}}\frac{1+\ln \frac{R}{\mathbb {A}}}{1-\gamma }\right)  \).
Consequently, if the policy advantage is large then few samples will be needed. 

Now the proof of 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 the 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 reason is due to 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 \( 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,
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 intuitively
due to the fact that approximation errors can be incurred over \( \frac{1}{1-\gamma } \)
timesteps and another factor of \( \frac{1}{1-\gamma } \) is due to the inherent
ununiformity of \( d(s|\pi ^{*},\mu ') \). 


\section{Discussion}

We have made the first guarentees for doing reinforcment learning in the approximate
regime.


\subsection{The Black Box Algorithm}

The ability to find a policy with a large policy advantage can be stated as
a supervised learning problem. Essentially, we must estimate the \emph{differences}
between the the advantages of actions at a particular state well (in expectation).
Our notion of loss is given by:
\[
E_{s\sim d(s|\pi ,\mu )}\max _{a}|A_{\pi }(s,a)-f_{\pi }(s,a)|\]
It is straightforward to see that if we can keep this error below \( \varepsilon  \),
then we can construct an \( \frac{\varepsilon }{2} \)-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 \( \frac{\varepsilon }{2} \)-good black
box is at most as difficult as solving a regression problem with an \( l_{1} \)error
of \( \varepsilon  \) over the maximum advantage error in each state.

advantage difference error for each state. It is possible to turn this into
an exact \( l_{1} \) error by introducing a factor of \( n_{a} \), the number
of actions.


\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  \))?'' Consider improving the perfomance 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 \( \beta \varepsilon  \)) , then finding a policy with
large policy advantage with respect to \( \tilde{\mu } \), will also find a
policy with large policy advantage under \( D \). Then joint improvement will
be possible for this case (though we don't discuss all the detials here). 

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


\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 any good policy). \emph{etc.
etc. etc.}

\begin{acknowledgement}
We give Peter Dayan many thanks for suggestions on what constitutes efficient
learning.
\end{acknowledgement}

\section{Appendix B: Examples}

The example for theorem \ref{how_far_away} is easy.

\emph{FIG: I didn't have the time to make the fig, but I'll describe it.} There
are two states, \( i \) and \( j \), and two actions, \( 1 \) and \( 2 \),
at each state. At state \( i \), action \( 1 \): \( R(i,1)=0 \) and transition
is \( i\rightarrow i \) and action 2: \( R(i,2)=R \) and transition is \( i\rightarrow j \).
At state \( j \), action 1: \( R(j,1)=0 \) and transition is \( j\rightarrow j \)
and action 2: \( R(j,2)=-R \) and transition is \( j\rightarrow j \). So only
one action (1 at state \( i \)) can move the agent from one state to another.
\emph{-Sham}

We now show the bound in theorem \ref{how_far_go} is tight. Consider the MDP
shown in the figure. Let the start state be \( i \). Let \( \pi (1|i)=1 \)
and \( \pi (1|j)=1 \), so \( d(i|\pi )=1 \). The advantage are then \( A(i,1)=0 \),
\( A(i,2)=(1-\gamma )R \), \( A(j,1)=0 \), and \( A(j,2)=-(1-\gamma )R \).
Let us choose \( \pi ^{\prime } \) such that \( \pi ^{\prime }(2|i)=1 \) and
\( \pi ^{\prime }(2|j)=1 \), so: 
\begin{eqnarray*}
\Pi _{\pi }(\pi ^{\prime }) & = & E_{s\sim d(s|\pi ,\mu _{e})}\{\sum _{a}\pi ^{\prime }(a|s)A_{\pi }(s,a)\}\\
 & = & 1*(1-\gamma )R+0*(-(1-\gamma )R)\\
 & = & (1-\gamma )R\, ,
\end{eqnarray*}
 so policy improvement is possible with \( \pi ^{\prime } \) since the policy
advantage is positive. It is clear that \( \omega (\pi )=0 \) and \( \varepsilon =(1-\gamma )R \). 

Now let us compute \( \omega (\pi _{\textrm{new}}) \). If the agent is at state
1, the immediate reward it receives is, on average, 

\( \alpha R \) and if the agent is at state 2, the immediate reward is \( -\alpha R \)
(based on \( \pi _{\textrm{new}} \)). It follows that 
\begin{eqnarray*}
\omega (\pi _{\textrm{new}})-\omega (\pi ) & = & (1-\gamma )\sum _{t=0}^{\infty }\gamma ^{t}r_{t}-0\\
 & = & \alpha (1-\gamma )\sum _{t=0}^{\infty }\gamma ^{t}(P(s_{t}=i|t)R-P(s_{t}=j|t)R)\\
 & = & \alpha (1-\gamma )R\sum _{t=0}^{\infty }\gamma ^{t}(1-2P(j|t))\\
 & = & \alpha (1-\gamma )R\sum _{t=0}^{\infty }\gamma ^{t}(1-2(1-(1-\alpha )^{t}))\\
 & = & \alpha (1-\gamma )R\sum _{t=0}^{\infty }\gamma ^{t}-2\alpha (1-\gamma )R\sum _{t=0}^{\infty }\gamma ^{t}(1-(1-\alpha )^{t})\\
 & = & \alpha R-2\gamma R\frac{\alpha ^{2}}{1-\gamma (1-\alpha )}\\
 & = & \alpha \frac{\Pi }{1-\gamma }-\frac{\alpha ^{2}}{1-\gamma (1-\alpha )}\frac{2\gamma \varepsilon }{1-\gamma }\, .
\end{eqnarray*}
Hence, the bound is tight. Note that the we can improve by at least\( \frac{\Pi ^{2}}{8R}=\frac{(1-\gamma )^{2}R}{8} \),
with \( \alpha =\frac{(1-\gamma )\Pi }{4R}=\frac{(1-\gamma )^{2}}{4} \).

\end{document}
