% Multi criteria RL in Average cost games
% Shie Mannor
% Submitted: Aug/02
% Revised: Aug/03, Dec/03.

\documentclass[twoside,11pt]{article}

\usepackage{jmlr2e}
\usepackage[usenames,dvipsnames]{color}
\newcommand{\Exp}{{\rm I\hspace{-0.7mm}E}}
%\documentclass[12pt]{article}
\usepackage{epsf}

\jmlrheading{5}{2004}{325-360}{8/02; Revised 12/03}{4/04}{Shie Mannor and Nahum Shimkin}
\ShortHeadings{Multi-Criterion Reinforcement Learning}{Mannor and Shimkin}
\firstpageno{325}

\newcommand{\Red}{\color{red}}
\newcommand{\Blue}{\color{blue}}
\newcommand{\Green}{\color{green}}
\newcommand{\Black}{\color{black}}
\newcommand{\Magenta}{\color{Magenta}}
\newcommand{\bt}{\mbox{\boldmath $\theta$}}


%toggle red/all black version
\renewcommand{\Red}{}


\begin{document}

\title{A Geometric Approach to \\ Multi-Criterion Reinforcement Learning}

\author{\name Shie Mannor  \email shie@mit.edu \\
       \addr Laboratory for Information and Decision Systems\\
       Massachusetts Institute of Technology \\
       Cambridge, MA 02139, USA
       \AND
       \name Nahum Shimkin  \email shimkin@ee.technion.ac.il \\
       \addr Department of Electrical Engineering\\
       Technion, Israel Institute of Technology \\
       Haifa 32000, Israel}

\editor{Sridhar Mahadevan}

\maketitle


%\end{titlepage}
%\setlength{\textwidth}{6in} \setlength{\textheight}{9in}
%\setlength{\topmargin}{-0.5in} \setlength{\oddsidemargin}{.25in}

%\begin{document}


%\renewcommand{\cite}{\shortciteA}


\newcommand{\uu}{\underline}
\newcommand{\oo}{\overline}

\newcommand{\reals}{{\rm I\!R}}
\newcommand{\PP}{{\rm I\!P}}
\newcommand{\NN}{{\rm I\!\!N}}
\newcommand{\ZZ}{{ /\!\!Z}}

\newcommand{\Ball}{{\rm I\!B}}

\newcommand{\cI}{{\cal I}}
\newcommand{\cT}{{\cal T}}
\newcommand{\cJ}{{\cal J}}
\newcommand{\cF}{{\cal F}}
\newcommand{\cU}{{\cal U}}
\newcommand{\cH}{{\cal H}}
\newcommand{\cN}{{\cal N}}

%\renewcommand{\theequation}{\thesection.\arabic{equation}}
%\newcommand{\mysection}[1]{\section{#1}\setcounter{equation}{0}}
% \newcommand{\mysection}[1]{\section{#1}\setcounter{equation}{0}
%                       \setcounter{figure}{0}}

%ABBREVIATIONS
\newcommand{\req}[1]{(\ref{#1})}
\newcommand{\dfn}{\stackrel{\triangle}{=}}
\newcommand{\bydef}{\stackrel{\bigtriangleup}{=}}
\newcommand{\limsupn}{\limsup_{n \rightarrow \infty}}
\newcommand{\liminfn}{\liminf_{n \rightarrow \infty}}
\newcommand{\liminft}{\liminf_{t \rightarrow \infty}}
\newcommand{\limsupt}{\limsup_{t \rightarrow \infty}}
\newcommand{\val}{{\rm v }}
\newcommand{\co}{{\rm co }}
\newcommand{\ri}{{\rm ri }}
\newcommand{\limn}{\lim_{n \rightarrow \infty}}
\newcommand{\R}[1]{\reals^{#1}}
\newcommand{\m}[1]{\mathcal{#1}}

%COMMANDS
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bea}{\begin{eqnarray}}
\newcommand{\eea}{\end{eqnarray}}
\newcommand{\beaa}{\begin{eqnarray*}}
\newcommand{\eeaa}{\end{eqnarray*}}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\db}{\hspace*{\fill}{\zapf o}}
\newcommand{\cpn}[1]{\caption{\myfont #1}}
\newcommand{\bpn}{\begin{proposition}\twlsf}
\newcommand{\epn}{\db\end{proposition}}
\newcommand{\bdm}{\begin{displaymath}}
\newcommand{\edm}{\end{displaymath}}

\newcommand{\supp}{\rm{supp}}
\newcommand{\op}[1]{\mbox{op}_{#1}}
\newcommand{\qed}{\hfill$\rule{2mm}{3mm}$}
\newcommand{\argmax}{\mathop{\mbox{argmax}}}
\newcommand{\argmin}{\mathop{\mbox{argmin}}}

%ENVIRONMENTS
\newtheorem{assumption}{Assumption}

%VARIOUS NOTATIONS

\newcommand{\boldone}{\mbox{\bf 1}}
\newcommand{\Ga}{\Gamma}
\newcommand{\GA}{\Gamma}
\newcommand{\La}{\Lambda}
\newcommand{\LA}{\Lambda}
\newcommand{\la}{\lambda}
\newcommand{\eps}{\epsilon}
\newcommand{\rate}{\frac{1}{n}\log}
\newcommand{\Rd}{\reals^d}
\newcommand{\DU}{\Delta(\cU)}
\newcommand{\bX}{\oo{X}}
\newcommand{\lip}{\langle}
\newcommand{\rip}{\rangle}
\newcommand{\rome}{\mbox{\rm e}}
\newcommand{\Pone}{P^1}
\newcommand{\Ptwo}{P^2}

\def\SM#1{{\bf #1}}
\def\Old#1{OLD: {\tt #1}}
% \renewcommand{\cite}{\citeA}



\begin{abstract}
We consider the problem of reinforcement learning in a controlled
Markov environment with multiple objective functions of the
long-term average reward type. The environment is initially
unknown, and furthermore may be affected by the actions of other
agents, actions that are observed but cannot be predicted
beforehand. We capture this situation using a stochastic game
model, where the learning agent is facing an adversary whose
policy is arbitrary and unknown, and where the reward function is
vector-valued. State recurrence conditions are imposed throughout.
In our basic problem formulation, a desired target set is
specified in the vector reward space, and the objective of the
learning agent is to {\em approach} the target set, in the sense
that the long-term average reward vector will belong to this set.
We devise appropriate learning algorithms, that essentially use
multiple reinforcement learning algorithms for the standard scalar
reward problem, which are combined using the geometric insight
from the theory of approachability for vector-valued stochastic
games. We then address the more general and optimization-related
problem, where a nested class of possible target sets is
prescribed, and the goal of the learning agent is to approach the
smallest possible target set (which will generally depend on the
unknown system parameters). A particular case which falls into
this framework is that of stochastic games with average reward
constraints, and further specialization provides a reinforcement
learning algorithm for constrained Markov decision processes. Some
basic examples are provided to illustrate these results.
\end{abstract}

%\thispagestyle{empty}

%\setcounter{page}{1}

\section{Introduction}


% Overview

Agents that operate in the real world often need to consider
several performance criteria simultaneously.
In this paper we address the problem of RL (Reinforcement Learning) in
a dynamic environment, where the controlling agent's goals are
formulated in terms of multiple objective functions, each one corresponding
to a long-term average reward functional.
Furthermore, we deviate from the strictly Markovian environment
model by allowing the presence of additional agents whose
policies may be arbitrary.
Our goal then is to formulate performance objectives that are
meaningful in such a setting, and develop learning algorithms that
attain these objectives.

% Multi criterion - the concept

Multi-criterion decision making is a well established research
area with a wide range of solution concepts and methods \citep[for an
overview see, for example,][]{Steuer86,EhrgottGandibleux02}.
Most basic to multi-criterion optimization is the concept of
efficient (or Pareto optimal) solutions, namely those solutions
that cannot be improved upon in all coordinates (with strict improvement
is at least one coordinate) by another solution.
Unfortunately efficient solutions are essentially non-unique, and various
methods have been developed to single out one ``optimal" solution" --- for
example, by forming appropriate scalar combinations of the different
objective functions. Another formulation of multi-criterion optimization
which leads to a well-defined solution is the constrained optimization
problem,  where one criterion is optimized
subject to explicit constraints on the others.
In the context of Markov decision problems (MDPs), several papers
have developed dynamic programming algorithms to compute efficient
solutions \citep[see][]{White82,Henig83,CMM90},
while constrained MDPs have received more extensive attention
--- see \cite{Alt99} and references therein.
Constrained Stochastic Games were considered by \cite{Shimkin94} and
\cite{AltmanShwartz00}.
Learning schemes for constrained MDPs were
devised by \cite{PNR99}, based on the theory of stochastic
learning automata. A Q-learning approach to constrained MDPs was
considered by \cite{KSZ98}.
% Pareto dominance \citep[in the games context see][]{GhosePrasad89}.
% In the more general context of control see
% \cite{Salukvadze79} and \cite{LWYY02}.

% Target sets

In the present paper, we shall use the notion of a {\em target set}
as the basic concept which specifies the controller's goals with respect
to its multiple objective functions.
This set specifies the range in which
the vector of objective functions is required to reside.
More precisely, since each objective function is in the form of a
long-range average reward, the controller's objective is to ensure
that the average-reward vector converges to the given target set.
Note that in its basic form the target set concept does not correspond
to an optimization problem but rather to constraint satisfaction.
However, the optimization aspect may be added by looking for target sets
that are minimal in some sense; indeed, we will employ this
approach in the latter part of the paper to obtain a learning algorithm
for constrained stochastic games (and, in particular, constrained MDPs).

% importance and relevance of target sets

As the target set concept is basic to our problem formulation, it
is worth taking some time to highlight its relevance and utility
in dynamic decision problems. In various engineering applications,
performance requirements are given in the form of bounds on
variables of interest, that need to hold under varying system
conditions (parameters) and external disturbances. A temperature
regulator, for example, may be required to keep the temperature
with a certain range (say $\pm 1^o$C) of the nominal operating
point. The corresponding target set is then simply the interval
$[\underline{T},\overline{T}]$.  In communication networks which
provide quality of service (QoS) guarantees, such as certain
service classes of ATM networks, a user may be given guarantees in
terms of a Minimal Cell Rate (MCR), which lower bounds the
available bandwidth, and a Cell Loss Ratio (CLR) that upper bounds
the allowed fraction of lost cells \citep[e.g.,][]{ATM}. The
controller's goal is to keep ${\rm BW}\geq{\rm MCR}$ and ${\rm
LR}\leq{\rm CLR}_0$, where ${\rm BW}$ is the available bandwidth
and ${\rm LR}$ is the fraction of lost cells. This translates to a
target set $T$ of the form $T=[{\rm MCR},\infty)\times [0,{\rm
CLR}]$, which resides in the two-dimensional objective space
$\reals^2$. A more elaborate service guarantee may ensure a
certain loss ratio up to a given cell rate, and allow for a higher
one when the cell rate is higher; the corresponding target set can
still be easily constructed in $\reals^2$, although it will no
longer be rectangular due to the coupling between the two
criterions. We note that regulating mechanisms are equally
prevalent in biological systems, where such quantities as
temperature, pressure and concentration need to be maintained
within certain bounds.

We observe, in passing, that goal setting and their attainment
play a central role in prominent descriptive models of human
decision making. Simon`s theory of {\em satisfying} decisions
suggests that actual decision makers are rarely optimizers, but
rather accept ``good enough" alternatives that meet previously
determined aspiration levels \citep{Simon96}. Kahaneman and
Tversky`s prospect theory \citep{Kahaneman79} evaluates gain or
loss relative to a preset reference point, which can also be
interpreted as an aspiration level for the decision maker.

%NN
A second challenging ingredient in our problem formulation is that of
the arbitrarily varying environment.
The decision problem is considered from the
viewpoint of a particular controlling agent, whose environment may be
affected by other, noncooperative, agents. We make no assumptions
regarding the choices of these other agents, and allow them to
choose their actions arbitrarily.
Such agents may also represent non-stationary moves of Nature,
or account for non-Markovian dynamics over a partially-observed
state.
For modelling simplicity we collect all the additional agents as a
single one, the {\em adversary}, whose actions may affect both the
state transitions and obtained rewards. The model then reduces to
a two-person stochastic game with vector-valued rewards. The
adversary is free to choose its actions according to any control
policy, subject only to causality limitations (both agents are assumed
to fully observe the state and action sequences).
Accordingly, we shall require that the controlling agent will
achieve the required goal (convergence of the average reward vector
to the target set) {\em for any policy of the adversary}.
% In the special case
% where the adversary is trivialized, the model reduces to a Markov Decision
% Process (MDP) with vector rewards.

%%NN
The proposed problem formulation is inspired by the theory of
approachability, introduced by \cite{B56} in the context of
repeated matrix games with vector payoffs. This theory provides
geometric conditions, and matching control policies, for a set in
the reward space to be {\em approachable} by a player, in the
sense that the average reward vector approaches this target set
for any policy of the adversary. Essentially, Blackwell
approaching strategies are based on reviewing the current average
reward vector, and whenever it is outside the target set, the
reward is ``steered" in the direction of the target set. More
precisely, the controlling agent computes the direction of closest
distance from  current reward vector to the target set, and plays
his maximin policy in the matrix game obtained by projecting the
vector-valued reward function along this direction. Among its many
extensions and applications, approachability theory has been
extended to stochastic (Markov) games by \cite{SS93} under
appropriate state recurrence conditions; these conditions are
enforced throughout the present paper. The relevant results are
reviewed in Section~\ref{sec:Appsurvey} and some new results
are provided in Section~\ref{sub:appfinitedirs}. In this paper we add
the learning aspect, and consider the problem of learning
approaching policies on-line.
% , using Reinforcement Learning (RL).
Accordingly, we refer below to the controlling
agent as the {\em learning} agent.

%%NN
It will be useful at this point to illustrate some of the
geometric ideas behind Blackwell`s approaching policies via a
simple example. Note that this example is strictly illustrative.
{\Red
Consider first a scalar temperature regulation problem,
where the performance objective of interest is to regulate the
{\em long-term average} temperature, and guarantee that it is in
some prescribed interval $[\underline{T},\overline{T}]$. The
agent may activate a cooler or a heater at will, although when
activated it must remain so for a certain period of time.
When the cooler is activated the temperature drops to a range
$[a,b]$, with $b<\underline{T}$, and when the heater is
on the temperature reaches a range $[c,d]$, with $c>\overline{T}$.
The precise temperature reached in the allocated range varies
due to environmental influence.
Given this uncertainty, the simplest way to regulate the average
temperature would be to keep note of the current average temperature
(over the time interval between the initial and present time),
and then activate the cooler whenever the current average
increases above $\overline{T}$, and the heater whenever
it decreases below $\underline{T}$:
see Figure~\ref{fig:tempraturegraph} for an illustration.
In between these levels, any (reasonable) activation rule may be used.
It should be noted that the proposed policy is not stationary in the
usual sense, since it depends on the current {\em average} temperature,
which is not part of a standard definition of a state for this system.
We also note the similarity with the common "bang-bang"
(or threshold) feedback policy for temperature regulation: the
goal there is of course to regulate the {\em instantaneous} temperature,
which is accordingly used as the feedback variable.
It is not possible (due to the assumed relationships between the temperature intervals)
to maintain the instantaneous temperature in the specified interval.
}

\begin{figure}[h]
%\vskip -0.2in
\setlength{\epsfxsize}{3.25in}
\centerline{\epsfbox{tempraturegraph.eps}} \vskip 0.2in
\caption{The single dimensional temperature regulation example. If the
temperature is higher than $\overline{T}$ the control policy is to
cool, and if the temperature is lower than $\underline{T}$ the
control policy is to heat.} \label{fig:tempraturegraph}
\end{figure}

%%NN
This one-dimensional example already contains one of the key
elements of the approaching policies. Namely, the average reward
vector is ``steered" in the direction of the target set by using
direction dependent sub-policies. While each sub-policy may itself
be stationary, the overall approaching policy is not. Except for
the special case when the adversary is trivial (so that the model
reduces to a single-controller one), the use of such non-stationary
policies is essential, in the sense that target sets that are
approachable with general polices need not be so with stationary
policies.

%NN
Consider next a multi-objective version of the temperature
regulation problem. The controller's first objective, as before,
is to maintain the average temperature in a certain range. One can
consider other criteria of interest such as the
average humidity, frequency of switching between policies, average
energy consumption and so on. This problem may be characterized as
a multi-criterion problem, in which the objective of the
controller is to have the average reward in some target set.
Suppose that the additional variable of interest is the average
humidity. In a controlled environment such as a greenhouse, the
allowed level of humidity depends on the temperature. An
illustrative target set is shown in Figure
\ref{fig:temperaturegraphcombined}. A steering policy now relies
on more elaborated geometry. In place of the two directions
(left/right) of the one-dimensional case, we now face a continuous
range of possible directions, each associated with a possibly different
steering policy. For the purpose of the proposed learning
algorithm, it will be useful to consider only a finite number of
steering directions (and associated policies). We will show that
this can always be done, with negligible effect on the attainable
performance.

\begin{figure}[h]
%\vskip 0.2in
\begin{center}
\centerline{\epsfxsize=2.5in\epsfbox{temperaturegraphcombined.eps}}
\caption{The two dimensional temperature-humidity example.
The steering directions, which point to the closest point in the
set, are denoted by arrows.} \label{fig:temperaturegraphcombined}
\end{center}
\end{figure}


The analytical basis for this work relies on three elements:
the theory of approachability for vector-valued dynamic games;
RL algorithms for (scalar) average reward problems;
and stochastic game models.
As approachability was already introduced above, we next briefly
address the other two topics.

%RL in general and for scalar average cost systems
Reinforcement Learning has emerged in the last decade as a
unifying discipline for learning and adaptive control.
Comprehensive overviews may be found in \cite{NDP,SB98}, and \cite{KLM96}.
It should be mentioned that reinforcement learning has come
to encompass a wide range of learning methods, which surpasses
the restricted sense of adapting actions directly in response
to a (scalar) reinforcement signal; our method belongs in this
wider class.
RL for average reward Markov Decision Processes (MDPs) was
suggested by \cite{Sch93} and \cite{Mah96} and later analyzed in
\cite{ABB01}. The analysis for the average reward criterion is
considerably more difficult than the discounted case, as the
dynamic programming operator is no longer a contraction. Several
methods exist for average reward RL, including Q-learning
\citep{ABB01}, the $E^3$ algorithm \citep{KS98}, and actor-critic
schemes \citep{SB98}.
RL for multi-objective problems was considered, to
the best of our knowledge, only by \cite{KSZ98}. This paper
considers discounted constrained MDPs, that is, the objective is
to find a maximizing policy for the discounted reward problem,
given that some additional discounted constraints are satisfied.
The algorithm of \cite{KSZ98} searches for the best {\em
deterministic} policy. In general, however, the optimal policy for
constrained MDPs is not deterministic \citep[e.g.,][]{Alt99}.

%Stochastic games and AI
Stochastic Games (SGs) present a flexible model of dynamic conflict
situations, with extensive theory and various applications in
economics, operations research, and more. For recent overviews see
\cite{FV96} and \cite{Mertens02}. In particular, existence of a
state-independent value and stationary optimal policies is
established for average-reward stochastic games under appropriate
recurrence conditions, which are assumed in this paper. Stochastic
games provide a natural generalization of the single-controller
Markov decision problem to the multi-agent setting, and are highly
relevant to various RL applications, starting with board games.
The naive learning approach ignores possible non-stationarity of
the opponent and simply applies standard RL algorithms as used for
MDPs. This approach has shown some notable success
\citep{BTW98}, but provides no performance guarantees.
{\Red The seminal work of \cite{Tes94} is a notable example of
an algorithm that learns under the assumption that the
opponent play is stationary and adversarial, but provides no performance
guarantees.}
Learning algorithms for zero-sum stochastic games with discounted rewards
have been introduced by \cite{L94} and shown to converge to the
max-min optimal policies \citep{LS99}.
Corresponding algorithms
for the average reward problem have emerged only recently, and
include model-based learning \citep{BrafTen02}, and Q-learning
\citep{MS02Qlrn}.

Our main results are as follows.
We present two learning algorithms for approaching a prescribed target set.
The first (Multiple Directions Reinforcement Learning) algorithm is based
on discretizing the set of possible
steering directions, using a (dense) grid of direction vectors,
and maintaining a learning algorithm for the stochastic games
induced by each grid direction;
the (scalar) reward function for each game is obtained by projecting
the vector reward function on the corresponding direction.
% Whenever the learning agent wishes to steer in a certain direction
% it steers in a close direction instead.
The second (Current Direction Reinforcement Learning) algorithm focuses on
a single direction at a time, which is frozen for a long enough period
so that both learning and steering  are assured.
% Once a required steering direction is determined,
% it is maintained for a long enough period so that the required
% average reward relative to this direction is indeed achieved.
Both algorithms are efficient, in the sense that they approach
(to required accuracy) any target set that is
approachable by steering policies when the model is known.

Equipped with the two basic algorithms, we consider the important
extension to variable target sets.
Here the target set to be approached is not fixed {\em a-priori}.
Indeed, the target set of interest may depend on the
model parameters, which are initially unknown.
Our starting point here will be a {\em nested} family of target sets,
with the goal of the learning agent naturally defined as approaching the
smallest possible set in this family (note that approaching a smaller
set automatically implies that any larger set in the nested family is
also approached). We present a suitable learning algorithm which
combines the basic algorithms with an on-line estimate
of the minimally approachable target set.
We will then show that this framework can be specialized to
give a solution to the important problems of constrained SGs and MDPs.

We shall also briefly consider an alternative algorithm for
approaching a (fixed) target set, which is based on the
adversarial multi-armed bandit problem \citep[e.g.,][]{ACFS02}.
This algorithm is suitable for the case where there is only a
small set of sub-strategies that the controlling agent may
alternate between. The idea here is to treat each of the possible
strategies as an arm, and make sure that after enough rounds the
reward is as high as that of the best arm (policy). Again, we show
that the algorithm attains the same performance as in the known
model case.

The paper is organized as follows. In Section~\ref{sec:stochastic
games} we describe the stochastic game model and formulate the
control objective. In Section~\ref{sec:preliminaries} we recall basic results from approachability theory,
and prove that it suffices to use finitely many steering directions in order to approach a target
set with a given precision. We also discuss RL for scalar-valued SGs
and define two notions of optimality that will be used in the
sequel. The next two sections
% Section~\ref{sec:MCRL}, \ref{sec:CDRL}
describe the Multiple Directions RL algorithm
and the Current Direction RL algorithm, while the bandit-based
algorithm is described in Section~\ref{sec:small}.
The extension to variable target sets
is discussed in Section~\ref{sec:unknown target}, which also
discusses constrained problems.
In Section~\ref{sec:MDPs} we briefly discuss the specialization of
the previous results to (single-controller) MDPs with
multiple objectives.
Two examples are described in Section~\ref{sec:illus},
followed by concluding remarks.
% drawn in Section~\ref{sec:conclusion}.
An appendix contains a refined algorithm and its convergence
proof.

%++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\section{Multi-Criterion Stochastic Games}
\label{sec:stochastic games}

In this section we present the multi-criterion SG model.
We describe the learning agent's objective and define a related
scalar projected games which will be useful in the sequel.

\subsection{Model Definition}
We consider a two-person average reward SG,
with a vector-valued reward function. We refer to the players as
P1 (the learning agent) and P2 (the arbitrary adversary). The game
is defined by the following elements:
%\vspace{-0.3cm}
\begin{enumerate}
\item $\m{S}$, a finite state space.
\item $\m{A}$ and $\m{B}$, finite sets of actions
for P1 and P2, respectively. To streamline our notation
it is assumed that P1 and P2 have the same action sets available in each state.
\item $P=P(s'|s,a,b)$, the state transition function.
\item $m:\m{S}\times \m{A}\times \m{B} \to \R{k}$, a vector-valued
reward function.
\end{enumerate}
At each time epoch $n\geq 0$, both players observe the current
state $s_n$, and then P1 and P2 simultaneously choose actions
$a_n$ and $b_n$, respectively. As a result P1 receives the reward
vector $m_n=m(s_n,a_n,b_n)$ and the next state is determined
according to the transition probability $P(\cdot|s_n,a_n,b_n)$.
More generally, we allow the actual reward $m_n$ to be random, in
which case $m(s_n,a_n,b_n)$ denotes its mean and we assume the
reward is bounded.\footnote{{\Red Bounded reward is required
essentially only for the SPRL algorithm from Section
\ref{sec:small}. This assumption can be relaxed for the algorithms
of Sections \ref{sec:CDRL},\ref{sec:MCRL}, and \ref{sec:unknown
target} to requiring bounded second moments. The result in the
appendix is also proved using the weaker assumption of bounded second moment.}}
We further assume
that both players observe the previous rewards and actions
(however, in some of the learning algorithms below, the assumption
that P1 observes P2's action may be relaxed). A policy $\pi\in
\Pi$ for P1 is a mapping which assigns to each possible observed
history a mixed action in $\Delta(\m{A})$, namely a probability
vector over P1's action set $\m{A}$. A policy $\sigma\in \Sigma$
for P2 is defined similarly. A policy of either player is called
{\em stationary} if the mixed action it prescribes depends only on
the current state $s_n$. The set of stationary policies of P1 is
denoted by $F$, and that of P2 by $G$. Let $ \hat{m}_n$ denote the
average reward by time $n$:
$$
\hat{m}_n\bydef \frac{1}{n} \sum_{\tau=0}^{n-1} m_\tau \,.
$$
Note that we do not define a reward for P2. Since we
allow P2 to use an arbitrary policy, such reward function,
even if it exists, is irrelevant to our formulation.

The following recurrence assumption will be employed. Let state
$s^*$ denote a specific reference state to which a return is
guaranteed. We define the renewal time of state $s^*$ as
\be
\label{eq:taudef} \tau \bydef \min\{ n > 0 : s_n = s^* \} \,.
\ee

%\renewcommand{\theassumption}{A-\arabic{assumption}}
\begin{assumption}[Recurrence]
\label{ass:stabgames} There exist a state $s^*\in \m{S}$ and a
finite constant $N$ such that
$$
\Exp^s_{\pi,\sigma} (\tau ^2) < N \quad \mbox{\rm for all $\pi \in
\Pi$, $\sigma \in \Sigma$ and $s \in \m{S}$,}
$$
where $\Exp^s_{\pi\sigma}$ is the expectation operator when starting
from state $s_0=s$ with policies $\pi$ and $\sigma$ for P1
and P2, respectively.
\end{assumption}
For finite state and action spaces this assumption is satisfied if state
$s^*$ is accessible from all other states under any pair of
stationary deterministic policies \citep{SS93}. We note that Assumption \ref{ass:stabgames} holds
if the game is irreducible \citep[as defined in][]{HoffmanKarp66} or ergodic \citep[as defined in][]{KS98}.

\begin{remark}
\label{rem:reachablity}
Assumption \ref{ass:stabgames} may be relaxed in a similar manner to
\cite{MS00c}. There, it is assumed that state $s^*$ is {\em reachable}, that
is, either player has a policy that guarantees a return to $s^*$.
The approachability result that is obtained under this related assumption is
somewhat more complicated, and we adhere here to Assumption \ref{ass:stabgames}
for simplicity.
\end{remark}

\begin{remark}
\label{rem:norecurrence}
In the absence of any recurrence conditions, tight approachability conditions
and corresponding policies are extremely hard to obtain. This may be
attributed to the dependence of the minimax value of such games (with scalar
reward) on the initial state. Still, non-tight sufficient conditions and
corresponding learning algorithms may be obtained by requiring the approachability
conditions below to hold for all initial states. Again, we shall not
pursue this direction here.
\end{remark}




\subsection{P1's Objective}

P1's task is to approach a target set $T$, namely to
ensure convergence of the average reward vector to this set
irrespectively of P2's actions. Formally, let
$T\subset\R{k}$ denote the target set. In the following, $d$ is
the Euclidean distance in $\R{k}$. The set-to-point
distance between a point $x$ and a set $T$ is
$d(x,T) \bydef \inf_{y\in T} d(x,y)$.
{\Red We let $P_{\pi,\sigma}^s$ denote the
probability measure on the states and rewards sequences
when P1 plays the policy $\pi$, P2 plays policy $\sigma$, and
the initial state is $s$.}
\begin{definition}
A policy $\pi^*$ of P1 {\em approaches} a set $T\subset\R{k}$ (from initial state $s$)
if
$$
\lim_{n\to \infty} d(\hat{m}_n,T) = 0 \quad \mbox{\rm{$P_{\pi^*,\sigma}^s$-{a.s.},
for every $\sigma \in \Sigma$}}\,.
$$
A policy $\sigma^* \in \Sigma$
of P2 {\em excludes} a set $T$
(from initial state $s$) if for some $\delta>0$,
$$
\liminfn d(\hat{m}_n,T) > \delta \quad
\mbox{\rm{$P_{\pi,\sigma^*}^s$-{a.s.} for every $\pi \in \Pi$}}\,,
$$
{\Red where a.s. stands for almost surely.}
\end{definition}
The policy $\pi^*$ ($\sigma^*$) will be called an
approaching (excluding) policy for P1 (P2). A set is approachable if there exists
an approaching policy from all states. Noting that approaching a set and
its topological closure are the same, we shall henceforth suppose that the set
$T$ is closed.

\begin{remark}
The original definition of approachability by \cite{B56} required
uniformity of convergence with respect to P2's policy. Some of our
results do hold uniformly with respect to P2's policy and some
do not. Specifically, the rate of convergence in the algorithms
described in Sections \ref{sec:CDRL} and \ref{sec:small} is
uniform with respect to P2's policy. The convergence rate of the
algorithm described in Section~\ref{sec:MCRL} is not uniform
unless further assumptions are made. The issue of uniformity of
convergence was not pursued here.
\end{remark}

\begin{remark}
{\Red While the main focus in this paper is on  the long-term average criterion,
the target set concept does allow some consideration of instantaneous quantities.
For example, recall the temperature regulation problems presented in the Introduction.
Suppose that the instantaneous temperature ({\em in addition} to its average) is required to stay in some different
range $[T_{\min},T_{\max}]$. We can add a component to the reward vector,
which indicates deviation from the required range: i.e., it takes the value '1' if the
instantaneous temperature is outside this range, and '0' otherwise.
We can now define the target set so that the long-term average of this component
is required to approach 0, thereby assuring that the temperature stays in the required
range save for  a negligible fraction of times.
Thus, both instantaneous quantities and their time averages can be considered
in a unified framework.
}
\end{remark}

\subsection{The Projected Scalar Game}
Let $u$ be a unit vector in the reward space $\R{k}$. We often
consider the {\em projected game in direction $u$} as the zero-sum
stochastic game with the same dynamic as above, and {\em scalar}
rewards  $r_n \bydef m_n \cdot u$. Here ``$\cdot$'' stands for the
standard inner product in $\R{k}$. Denote this game by
$\Gamma_s(u)$, where $s$ is the initial state. The scalar
stochastic game $\Gamma_s(u)$, has a {\em value}, denoted $\val
\Gamma_s(u)$, if \bea \label{eq:valueexistance} \val \Gamma_s (u)
& = & \sup_{\pi} \inf_{\sigma} \liminfn \Exp^s_{\pi\sigma} (\hat{m}_n
\cdot u) \nonumber\\ & = & \inf_{\sigma} \sup_{\pi} \limsupn
\Exp^s_{\pi\sigma} (\hat{m}_n \cdot u) \,. \eea
The value is known to exist for any game with finite state and action spaces \citep{MN81}.
Furthermore, under Assumption
\ref{ass:stabgames} the value is independent of the initial state
and can be achieved in stationary policies \citep{FV96}. We
henceforth simply write $\Gamma(u)$ for the average reward zero-sum game which reward is
$r_n=m_n \cdot u$, and denote its value by $\val\Gamma(u)$.


\section{Preliminaries}
\label{sec:preliminaries}


In this section we recall the basic results of approachability
theory for SGs. In Subsection~\ref{sub:appfinitedirs} we extend
approachability theory by considering approximate approachability. A target set is
said to be {\em approximately approachable} if for every $\eps>0$ there exists
a policy such that the distance between the average vector-valued reward
vector and the target set is asymptotically less than $\eps$.
We prove that it suffices to consider finitely many steering directions
in order to approximately approach a target set.
We discuss relevant types of optimality of RL
algorithms in scalar games in Subsection~\ref{sub:RLscalar}.


\subsection{Approachability for Stochastic Games}
\label{sec:Appsurvey}

We recall the basic results from \cite{SS93} regarding
approachability for known stochastic games, which generalize
Blackwell`s conditions for repeated matrix games. Let
$$
\phi(\pi,\sigma) \bydef \frac{\Exp^{s^*}_{\pi,\sigma} (
\sum_{n=0}^{\tau-1} m_n )}{\Exp^{s^*}_{\pi,\sigma} (\tau)}
$$
denote the {\em average per-cycle} reward vector, which is the expected
total reward over the cycle that starts and ends in the reference
state, divided by the expected duration of that cycle. For any $x
\not\in T$, denote by $C_x$ a closest point in $T$ to $x$, and let
$u_x$ be the unit vector in the direction of $C_x - x$, which
points from $x$ to the goal set $T$.
The following theorem requires,
geometrically, that there exists a policy $\pi(x)$ such that the
set of all possible (vector-valued) expected rewards is on the other side of
the hyperplane supported by $C_x$ in direction $u_x$. See Figure~\ref{fig:approahcillustrate} for an illustration, the polygon
represents the set of all possible rewards when $\pi(x)$ is used.

\begin{theorem}{\em \citep{SS93}}
\label{thm:BLCKWLLclassic} Let Assumption \ref{ass:stabgames}
hold. Suppose that for every point $x\not\in T$ there exists a
policy $\pi (x)$ such that
\be \label{eq:B condition}
\left(\phi(\pi(x),\sigma) - C_x\right) \cdot u_x \ge 0\,, \quad
\forall \sigma \in \Sigma \,. \ee
Then $T$ is approachable by P1.
An approaching policy is given as follows: If $s_n=s^*$ and  $\hat{m}_n \not\in T$,
play $\pi(\hat{m}_n)$ until the next visit to state $s^*$;
otherwise, play arbitrarily until the next return to $s^*$.
\end{theorem}

\begin{figure}[h]
\centerline{\psfig{file=fig3t2.eps,width=.6\textwidth}}
\caption{An illustration of the approachability condition. The
location of the current average reward is $x$. The closest point
to $x$ in the target set is $C_x$. The polygon represents the set
of all possible expected reward when $\pi(x)$ is played. It can be
observed that $\pi(x)$ ensures that P1's reward will be on the
other side of the hyperplane perpendicular to the line segment
between $C_x$ and $x$.} \label{fig:approahcillustrate}
\end{figure}


Intuitively, the condition in Equation~\req{eq:B condition} means that P1
can ensure, irrespectively of P2's policy, that the average
per-cycle reward will be on the other side (relative to $x$) of
the hyperplane that passes through $C_x$ and is perpendicular to the line segment that
points from  $x$ to $C_x$.  Note that this hyperplane actually
separates $T$ and $x$ when $T$ is convex. We shall refer to the
direction $u_x$ as the {\em steering direction} from point $x$,
and to the policy $\pi(x)$ as the {\em directional steering policy} from $x$.
The approaching policy uses the following rule: between successive
visits to the reference state, a fixed (possibly stationary)
policy is used. When in the reference state, the current average
reward vector $\hat{m}_n$ is inspected. If this vector is not in
$T$, then the steering policy that satisfies Equation~\req{eq:B condition}
with $x=\hat{m}_n$ is selected for the next cycle. As a
consequence the average reward is ``steered" towards $T$, and
eventually converges to it.

Recalling the definition of the projected game in direction $u$
and its value $\val\Gamma(u)$, the condition in Equation~\req{eq:B
condition} may be equivalently stated as $\val\Gamma(u_x) \ge C_x
\cdot u_x$. Furthermore, the policy $\pi(x)$ can always be chosen
as the stationary policy which is optimal for P1 in the projected game
$\Gamma(u_x)$. In particular, the directional steering policy $\pi(x)$
depends only on the corresponding steering direction $u_x$.

For {\em convex} target sets, the condition of the last theorem
turns out to be both sufficient and necessary. Moreover, this
condition may be expressed in a simpler form, which may be
considered as a generalization of the minimax theorem for scalar
games \citep{B56}. Given a stationary policy
$g \in G$ for P2, let $\Phi(F,g) \bydef \co (\{\phi(f,g)\}_{f\in
F} )$, where  $\co$ is the convex hull operator.
The Euclidean unit sphere in $\R{k}$ is denoted by $\Ball^k$.
\begin{theorem}{\em \citep{SS93}}
\label{thm:convexapproachability} Let Assumption
\ref{ass:stabgames} hold. Let $T$ be a closed convex set in
$\R{k}$.
\begin{enumerate}
\item[(i)] $T$ is approachable if and only if  $\Phi(F,g) \cap T \ne \emptyset$ for every
stationary policy $g\in G$.
\item[(ii)] If $T$ is not approachable then it is excludable by P2.
In fact, any stationary policy $g$ that violates (i) is an
excluding policy.
\item[(iii)] $T$ is approachable if and only if $\val\Gamma(u) \ge \inf_{m\in T} u \cdot m$
for every $u\in \Ball^k$.
\end{enumerate}
\end{theorem}

\subsection{Approachability with a Finite Set of Steering Directions}
\label{sub:appfinitedirs}

Standard approaching policies, as outlined above, may involve an
infinite number of steering directions. The corresponding set of
directional steering policies may turn out to be infinite as well.
For the purpose of our learning scheme, we shall require an
approaching policy which relies on a {\em finite} set of steering
directions and policies.
{\Red In this section we establish appropriate extensions of the results surveyed
above. We prove that using a finitely many steering directions to approach
a target set can indeed be done, possibly requiring to slightly expand the target
set.} Specifically, we establish that if the condition in Equation~\req{eq:B
condition} is satisfied for the set $T$, then for any $\eps>0$
there exists a finite partition $\{U_1,U_2,\dots,U_J\}$ of the
unit sphere $\Ball^k$, and a corresponding set
$\{\pi_1,\pi_2,\dots,\pi_J\}$ of policies for P1, such that the
required separation condition in Equation~\req{eq:B condition} may be
satisfied within $\eps$ precision for any $u\in U_j$ by using the
policy $\pi_j$. In the following, let $M$ be an upper bound on the
magnitude of the expected one-stage reward vector, so that
$\|m(s,a,b)\| < M$ for all $(s,a,b)$ ($\|\cdot\|$ denotes the
Euclidean norm).
\begin{proposition}
\label{prop:finite_directions} Let Assumption \ref{ass:stabgames}
hold and suppose that the target set $T\subset \R{k}$ satisfies
the condition in Equation~\req{eq:B condition}.  Fix $\epsilon>0$. Let
$U=\{u_1,u_2,\dots,u_J\}$ be a set of unit vectors which are the
centers of open balls of radius $\epsilon/2M$ that cover the unit
sphere $\Ball^k$. Let $\pi_j$ be the (stationary)
policy which is optimal in the projected game $\Gamma(u_j)$. Then
for any $x\not\in T$, if the unit vector $u_x$ is closest to $u_j$
in $U$, then
\be \label{eq:eps_cond} \left(\phi(\pi_j,\sigma) -
C_x\right) \cdot u_x \ge - \eps\,, \quad \forall \sigma \in \Sigma
\,. \ee The cardinality $J$ may be chosen so that $J\leq
C(2M/\epsilon)^k$, where $C$ is a constant that depends only on the
dimension $k$.
\end{proposition}
\proof
Let $U=\{u_1,\dots ,u_J\}$ be the prescribed set of unit
vectors. A standard sphere packing argument shows that $J$ need not
be larger than the stated upper bound \citep[see, e.g.,][]{AntBar99}. Let $\pi_j$ be an
optimal policy for the projected game $\Gamma(u_j)$. By
assumption, Equation~\req{eq:B condition} holds for any $x\not\in T$ and
associated unit vector $u_x$. Let $u_j$ be the closest vector to
$u_x$ in $U$. Rewriting Equation~\req{eq:B condition} we have that
\begin{eqnarray*}
u_x \cdot C_x & \le & \inf_\sigma \left\{ \phi(\pi(x),\sigma) \cdot u_x \right\}\\
& \le & \sup_\pi \inf_\sigma \left\{\phi(\pi,\sigma) \cdot u_x \right\}\\
& = & \sup_\pi \inf_\sigma \left\{\phi(\pi,\sigma) \cdot \left(u_j
+ (u_x -u_j)\right)\right\} \,.
\end{eqnarray*}
By construction, $\| u_j - u_x\| < \eps/2M$ so that for every pair
$\sigma \in \Sigma$ and $\pi \in \Pi$ we have that
$\| \phi(\pi,\sigma) \cdot (u_i - u_x )\| \le \eps/2 $.
\begin{eqnarray*}
u_x \cdot C_x & \le & \sup_\pi \inf_\sigma \left\{\phi(\pi,\sigma)
\cdot u_j \right\} +
\eps/2 \\
& = & \inf_\sigma \left\{\phi(\pi_j,\sigma) \cdot u_j \right\} + \eps/2 \\
& \le & \inf_\sigma \left\{\phi(\pi_j,\sigma) \cdot u_x \right\} +
\eps \,.
\end{eqnarray*}
The optimality of $\pi_j$ in $\Gamma(u_j)$ was used in the first
equality and the bound on $\|u_j-u_x\|$ was used again in the last
inequality. \qed

{\Red
For a set $T\subset \R{k}$ we define its $\eps$-expansion, $T^\eps$, as
$T^\eps \bydef \{x\in \R{k}: d(x,T)\le \eps\}$.}
It is now easy to verify that Equation~\req{eq:eps_cond} suffices for
approaching $T^\eps$, which leads to the following result.
\begin{theorem}
\label{thm:Blackwellfinite}
Let Assumption \ref{ass:stabgames} hold and suppose that $T$ satisfies
Equation~\req{eq:B condition}. For any $\eps>0$
let $\{u_1,\dots,u_J\}$ be the unit
vectors in Proposition \ref{prop:finite_directions}, with corresponding directional steering polices
$\{\pi_1,\pi_2,\dots,\pi_J\}$. Then the following policy
approaches $T^\epsilon$, the $\eps$-expansion of $T$: If $s_n=s^*$
and  $\hat{m}_n \not\in T^\epsilon$, then choose $j$ so that
$u_{\hat{m}_n}$ is closest to $u_j$ (in Euclidean norm) and play
$\pi_j$ until the next visit to state $s^*$; otherwise, play
arbitrarily.
\end{theorem}
\proof We aim to show that the stated policy satisfies the
requirements of Theorem \ref{thm:BLCKWLLclassic} with respect to
$T^\eps$. That is, for every $x\not\in T^\eps$ the policy $\pi_j$
which is optimal for the $u_j$ which is closest to $x$ satisfies
\be \label{eq:bcondinproof} \left(\phi(\pi_j,\sigma) -
C^\eps_x\right) \cdot u^\eps_x \ge 0\,, \quad \forall \sigma \in
\Sigma \,, \ee where $C^\eps_x$ is the closest point in $T^\eps$
to $x$ and $u^\eps_x$ is the unit vector from $x$ to $C^\eps_x$.
We first claim that $C_x = C_x^\eps + \eps u_x^\eps$, and hence
$u_x = u_x^\eps$. Indeed, if this is not true then there is a
point $z$ in $T$ such that $d(z,x)<d(C_x^\eps + \eps
u_x^\eps,x)=d(C^\eps_x,x)+\eps$. Let $u'$ denote the unit vector
from $x$ to $z$, we have that $z^\eps=z-\eps u'$ is in $T^\eps$.
It follows that $d(z^\eps,x)=d(z,x)-\eps$, combining this with the
above, we get that $d(z^\eps,x)<d(C^\eps_x,x)$ which
contradicts the assumption that $C^\eps_x$ is a closest point to
$x$ in $T^\eps$.

Next, observe that by Proposition \ref{prop:finite_directions} we have
that
$$
\left(\phi(\pi_j,\sigma) - C_x\right) \cdot u_x \ge -\eps  \,,
\quad \forall \sigma \in \Sigma \,,
$$
but since $C_x = C_x^\eps + \eps u_x^\eps$ and $u_x = u_x^\eps$,
\req{eq:bcondinproof} follows. \qed


\begin{remark} It follows immediately from the last theorem that the set
$T$ itself (rather than its $\eps$-expansion) is approachable
with a finite number of steering directions if $T^{-\eps}$, the
$\eps$ shrinkage of $T$ satisfies Equation~\req{eq:B condition}.
Equivalently, $T$ is required to satisfy Equation~\req{eq:B condition} with
the 0 on the right-hand side replaced by $\eps$.
\end{remark}

For convex target sets the sufficient condition Equation~\req{eq:B condition}
for approachability is also necessary. This implies that every $\epsilon$-expansion
is approachable using a finite number of directions as per Theorem \ref{thm:Blackwellfinite}. The following
corollary is an immediate result of the above theorem and Theorem \ref{thm:convexapproachability}.
\begin{corollary}
\label{cor:convex iff} Let Assumption \ref{ass:stabgames} hold. A
convex target set $T$ is approachable if and only if for every $\epsilon>0$
the set $T^\epsilon$ can be approached by
considering a finite number of directions as in Theorem
\ref{thm:Blackwellfinite}.
\end{corollary}

\subsection{Reinforcement Learning in Scalar Games}
\label{sub:RLscalar}

In this subsection we review RL for zero-sum stochastic games with
scalar rewards. We define two notions of approximate optimality in
these games that will be useful in the sequel. The first type of
optimality is optimality of the expected reward in finite time and
the second type is asymptotic optimality of the learned policy.
In both cases, the reference level for optimal performance is
the value of the game. The first type of optimality requires that the average
reward is not much less than the value of the game. The second
type of optimality requires that the learned policy
asymptotically achieves an expected reward which is not much worse
than the value of the game. We note that a more ambitious goal may be to
consider the Bayes envelope as in \cite{MS03MOR} instead of the
value, but this is not pursued here.

Consider a scalar zero-sum stochastic game.
Denote the scalar reward at time $n$ by $r_n$ and the value by
$\val$ (which is defined as in Equation~\req{eq:valueexistance}). Similarly to the vector-valued case, $\hat{r}_n$ denotes
the average reward by time $n$. Our first notion of optimality is
in expectation, after finitely many epochs.
\begin{definition}
\label{def:epsoptexpect} A learning algorithm $\pi$ is {\em
$\eps$-optimal in expectation} from state $s$ if
there exists a deterministic finite
time $N(\eps)$ such that the expected average reward by time
$N(\eps)$ satisfies
\be \label{eq:Episigmaepsoptimal}
\Exp_{\pi,\sigma}^s \hat{r}_{N(\eps)} \ge \val -\epsilon \,, \ee for
every policy $\sigma$ of P2.
\end{definition}

There are several algorithms that are $\eps$-optimal in
expectation. For example, by carefully choosing the parameters of
the R--MAX algorithm of \cite{BrafTen02} the optimality
requirement in Equation~\req{eq:Episigmaepsoptimal} is satisfied. Indeed,
\cite{BrafTen02} suggested a model-based learning policy $\pi$ of
P1 that satisfies that for every $\eps,\delta >0$ there exists a
time $N(\eps,\delta)$ such that the
expected average reward satisfies at time $N(\eps,\delta)$ with
probability at least $1-\delta$
$$
\Exp_{\pi,\sigma} \hat{r}_{N(\eps,\delta)} \ge \val -\epsilon \,,
$$
for every policy $\sigma$ of P2.
By proper choice of parameters, the R--MAX algorithm yields an $\eps$-optimal in expectation algorithm.
This can be done by running the R--MAX algorithm with
$\eps' = \eps/2$ and $\delta' = \eps/2M$, where $M$ is a bound on the
expected immediate reward.
Another algorithm that is $\eps$-optimal in expectation is
the Q-learning algorithm of \cite{MS02Qlrn}. An additional assumption that is required there is
that P2 plays every action infinitely often  \citep[the analysis follows][]{KS99}.


The next definition concerns the optimality of the learned
policy and is of asymptotic nature.
It implies that the learned policy of P1 is almost optimal in the limit.
Formally, a policy of P1 is a mapping from all possible histories to
the set of mixed actions of P1.
Let $\pi_n$ denote the policy of P1 from time $n$ onwards
(in the definition below this policy depends on the entire history up to time $n$, and the time
axis is moved back $n$ steps so that $\pi_n$ starts at $t=0$).
\begin{definition}
A learning policy $\pi$ of P1 is {\em  asymptotically $\eps$-optimal}
in a scalar game if, for every policy
$\sigma$ of P2,
$\pi_n$ satisfies
 \be
\label{eq:epsoptdef} \liminfn \frac{\Exp^{s^*}_{\pi_n,\sigma}
\sum_{t=0}^{\tau-1} r_t}{\Exp^{s^*}_{\pi_n,\sigma} \tau} \ge \val
-\epsilon \quad \mbox{$P_{\pi,\sigma}$-a.s.}
\ee
The renewal time $\tau$ is as defined in Equation~\req{eq:taudef}.
\end{definition}
It should be noted that the requirement in Equation~\req{eq:epsoptdef} is on the
policy $\pi_n$ and not on the actual reward obtained.
Intuitively, the condition means that after enough time P1 cannot
be surprised anymore, namely no policy of P2 can decrease his (per cycle)
payoff below the value of the game.

RL for average reward zero-sum stochastic games was devised
along similar lines as RL for average reward Markov decision processes.
A Q-learning based algorithm which combines the ideas of
\cite{L94,LS99} with those of \cite{ABB01} was devised by \cite{MS02Qlrn}. An
additional assumption that was needed for the convergence analysis there is that all
actions of both players are used infinitely often in order to satisfy Equation~\req{eq:epsoptdef}.
A model-based algorithm that is $\eps$-optimal asymptotically can be suggested.
By assuming that all actions are played infinitely often a model of the stochastic game may
be calculated and an $\eps$-optimal policy played,
similarly to the R-MAX algorithm of \cite{BrafTen02}.
It should be noted that P2 may refrain from playing certain actions. Consequently, P1 may
never observe these actions and never learn the exact model of the
game. This implies that unless we impose some restrictions on P2's
policy, the policy learned by P1 may be suboptimal. However,
P1 can only benefit if P2 does not play certain actions, since in
that case P2's play is constrained. The topic of learning to play optimally in
SGs when no restrictions are made on P2 calls for further study.


In the special case of MDPs there are several algorithms that are
$\eps$-optimal in expectation \citep[e.g.,][]{KS98,KS99}.
Algorithms that are asymptotically optimal include $\eps$-greedy
Q-learning \citep{SingJaakkolaLittmanSzepe00} and actor-critic \citep{KonTsi01}.

\section{The Multiple Directions Algorithm}
\label{sec:MCRL}

In this section we introduce and prove the convergence of the MDRL
(Multiple-Directions Reinforcement Learning) algorithm.
We consider the model of Section~\ref{sec:stochastic games}, but
here we assume that P1, the learning agent, does not know the
model parameters, namely the state transition probabilities and
reward functions. A policy of P1 that does not rely on prior knowledge
of these parameters will be referred to as a {\em learning}
policy.

The proposed learning algorithm relies on the construction of the
previous section of approaching policies with a finite number of
steering directions. The main idea is to apply a (scalar) learning
algorithm for each of the projected games $\Gamma(u_j)$
corresponding to these directions. Recall that each such game is a
standard zero-sum stochastic game with average reward. The
required learning algorithm for game $\Gamma(u)$ should secure an
average reward that is not less than the value $\val\Gamma(u)$ of
that game.


We now describe the MDRL algorithm that approximately approaches any
target set $T$ that satisfies Equation~\req{eq:B condition}. The parameters
of the algorithm are $\epsilon$ and $M$, where $\eps$ is the
approximation level and $M$ is a known bound on the norm of the
expected reward per step. The goal of the algorithm is to approach
$T^\epsilon$, the $\eps$ expansion of $T$. There are $J$ learning
algorithms that are run in parallel, denoted by $\pi_1,\ldots
\pi_J$.
Each of the $J$ algorithms is responsible for learning to steer the reward
in a different direction. Each of the $J$ algorithms is assumed to be
an asymptotically $\eps/2$-optimal learning algorithm.
The MDRL is described in Figure~\ref{fig:MCRL} and is
given here as a meta-algorithm (the scalar RL algorithms $\pi_i$
are not specified).

The algorithm is based on the idea of changing
the control policy on arrivals to the reference state $s^*$.
When arriving to $s^*$, the learning agent checks if the average
reward vector is outside the set $T^\eps$. In that case, it
switches to an appropriate policy that is intended to ``steer" the
average reward vector towards the target set. The steering policy
($\pi_j$) is chosen so that the steered direction ($u_j$) is close to the
exact direction towards $T$. The intuition behind the algorithm and
the proof is that instead of steering in the current direction into $T$, a
``close'' direction, quantized out of a finite set is used. By employing the same quantized
directions often enough, the decision maker eventually learns how to steer in those
directions. Once the steering policy in each of the quantized directions
is learned, the decision maker can almost steer in the desired direction at
every return to $s^*$, by choosing a close enough quantized steering
direction.

% insert it in figure like manner
\begin{figure}[h]
\begin{center}
\begin{tabular}{|p{14cm}|}
\hline
Input: Target set $T$; desired approximation level $\eps$; a bound $M$ on the
expected \\ \quad\quad\quad one step reward; a recurrent state $s^*$. \\
\hline 0. Divide the unit vector ball $\Ball^k$ as in Proposition
\ref{prop:finite_directions} for approaching the $\eps/2$ \\\quad expansion
of $T$. Let $u_1,\ldots u_J$ be the chosen directions there ($J= C(4M/\eps)^k$). \\\quad Initialize
$J$ different $\eps/2$-optimal asymptotically scalar algorithms, $\pi_1,\ldots,\pi_J$. \\\quad Set $n=0$.\\
1. If $s_n \ne s^*$ play arbitrarily until $s_n=s^*$.\\
2. ($s_n = s^*$) If $\hat{m}_n \in T^\eps$ goto step 1.
Else let $i= \arg\min_{1\le i\le J} \|u_i - u_{\hat{m}_n}\|_2$. \\
3. While $s_n \ne s^*$ play according to $\pi_i$, the reward
$\pi_i$ receives
is $u_i \cdot m_n$. \\
4. When $s_n =s^*$ goto step 2.\\
\hline
\end{tabular}
\end{center}
\caption{The MDRL algorithm.} \label{fig:MCRL}
\end{figure}

\begin{theorem}
\label{th:main} Suppose that Assumption \ref{ass:stabgames} holds
and that the target set satisfies Equation~\req{eq:B condition}.
Then the MDRL algorithm approaches $T^\epsilon$.
\end{theorem}
\proof Using the construction of Theorem \ref{thm:Blackwellfinite}
there are finitely many directions $u_1,\ldots , u_J$ that
induce $J$ projected SGs. At every return to state $s^*$, one of the
$J$ projected games is played and algorithm $\pi_i$ is run.
If the i-th game is not played infinitely often
then there exists $\tau_i$ after which the $i$-th algorithm is
not played. Let $\tau^1$ be
the maximum of all the times $\tau_i$ for $i$-s that were
played finitely often.
Let $\m{I}\subseteq\{1,\ldots,J\}$ be the
indices of algorithms that are played infinitely often. Since
each $\pi_i$ is eventually almost optimal it follows that after
some finite time $\tau'(\epsilon/2)_i$ each of the algorithms almost
achieves the maximal reward, that is for $t> \tau'(\epsilon/2)_i$
\req{eq:epsoptdef} holds with $\eps/2$ instead of $\eps$.
Let $\tau^2 = \max_{i \in \m{I}}
\tau'(\epsilon/2)_i$.
Let $\tau^3 = \max\{\tau^1,\tau^2\}$. From time $\tau^3$
onward P1's play is $\epsilon/2$ optimal. Thus, we can apply Theorem
\ref{thm:Blackwellfinite} so that $T^\eps$ is approached starting from $\tau^3$.
Fix $\delta > 0$.
Let $\tau^4$ be a large enough time such that the effect of the
first $\tau^3$ time epochs is not more $\delta$ in norm, i.e.,
$|\frac{1}{\tau^4} \sum_{n =0}^{\tau^3-1} m_n | < \delta$.
Since $\delta$ is arbitrary, by Theorem
\ref{thm:Blackwellfinite} the result follows.
 \qed

\begin{remark}
In the algorithm below, when $\pi_j$ is not played,
its learning pauses and the process history during that time is
ignored. Note however that some ``off-policy" algorithms (such as
Q-learning) can learn the optimal policy even while playing a
different policy. In that case, a more efficient version of the
MDRL may be suggested, in which learning is performed by all learning
policies $\pi_j$ continuously and concurrently.
\end{remark}

\section{The Current Direction Learning Algorithm}
\label{sec:CDRL}

In this section we introduce and prove the convergence of the
CDRL (Current Direction Reinforcement Learning) algorithm.
P1's goal is the same as in Section~\ref{sec:MCRL} - to approach a given target set $T$.
P1 does not know the model parameters and aims to ensure
the convergence of the average reward vector to this set
irrespectively of P2's actions.

Instead of using several fixed steering directions while employing a scalar learning algorithm
for each of these directions separately, a single learning algorithm
is used with the reward function changing over time.
The idea is to learn to play a scalar game whose reward is
the projected average reward on the direction towards the target set.
Once a direction is fixed, the policy is to steer in that direction
towards the target set for a while.
After a long enough time, the direction is replaced by the new steering direction
into the target set, and a new scalar learning algorithm is initiated.

We now describe the CDRL algorithm for approaching any
target set $T$ that satisfies Equation~\req{eq:B condition}.
The CDRL is described in Figure~\ref{fig:CDRL} and is
given here as a meta-algorithm. The algorithm is based on the idea of changing
the control policy after a long enough time.
Whenever a switch occurs the new policy is intended to ``steer'' the
average reward vector towards the target set.

% insert it in figure like manner
\begin{figure}[h]
\begin{center}
\begin{tabular}{|p{14cm}|}
\hline
Input: Target set $T$; Required precision $\eps$; $\eps$-optimal learning algorithm;\\
\quad \quad \quad $N(\eps)$ from Definition \ref{def:epsoptexpect}.\\
\hline 0. Set $\hat{m}_0$ arbitrarily; $n=0$.\\
1. Repeat forever:\\
2. \quad If $\hat{m}_n \in T^\eps$ play arbitrarily for $N(\eps)$ steps; $n:=n+N(\eps)$. \\
3. \quad Else let $u= u_{\hat{m}_n}$.\\
4. \quad Play an $\eps$-optimal in expectation learning algorithm with reward
at time $n$\\ \quad \quad\, given by $r_n=u \cdot m_n$ and parameter $\eps$.
Play the algorithm for $N(\eps)$ time\\\quad \quad\, epochs; $n:=n+N(\eps)$.\\
\hline
\end{tabular}
\end{center}
\caption{The CDRL algorithm.} \label{fig:CDRL}
\end{figure}

\begin{theorem}
\label{th:CDRL} Fix $\eps>0$. Suppose that for every $u\in \Ball ^k$ there exists an
$\eps$-optimal in expectation algorithm for each projected SG, $\Gamma(u)$.
Assume that the target set satisfies Equation~\req{eq:B condition}.
Then $T^\eps$ is approached using the CDRL algorithm.
\end{theorem}
\proof (outline)
The proof follows similarly to the more general Theorem \ref{th:modCDRL} that is provided in the appendix.
Consider the time epochs $\tau_i = iN(\eps)$, $i=1,2,\ldots$. If $\hat{m}_{\tau_i} \not\in T^\eps$ it follows that
$$
\Exp \left ( \Big(\frac{1}{N(\eps)} \sum_{n=\tau_i}^{\tau_{i+1}-1} (m_n - C_{\hat{m}_{\tau_i}} ) \Big) \cdot u_{\hat{m}_{\tau_{i}}} \Big| F_{\tau_i} \right )\ge -\eps \,,
$$
where $F_t$ is the sigma algebra generated until time $t$.
Consequently,
$$
\Exp \left ( \Big(\frac{1}{N(\eps)} \sum_{n=\tau_i}^{\tau_{i+1}-1} (m_n - C^\eps_{\hat{m}_{\tau_i}}) \Big) \cdot u_{\hat{m}_{\tau_{i}}} \Big| F_{\tau_i} \right )\ge 0 \,,
$$
where $C^\eps_x$ is the closest point to $x$ in $T^\eps$.
A similar argument to that of Theorem \ref{th:modCDRL} can be used to show that
$d(\hat{m}_{\tau_i},T^\eps) \to 0$ (a.s.).
The result for all $t$ follows by the boundedness of the immediate reward.
\qed

\begin{remark}
\label{rem:genofCDRL}
The CDRL algorithm was described above in extreme generality. There are several
possible refinements and improvements which depend on the specific scalar algorithm used and on
the domain of the problem. Specifically, knowledge is not assumed
to be preserved from one activation of the scalar algorithm to the other.
One may be interested to transfer knowledge between activations.
This is especially natural for model-based algorithm in the spirit of  \cite{BrafTen02},
where estimation of the model is performed.
\end{remark}

\begin{remark}
A variant of the CDRL algorithm in which the precision level $\eps$ is decreased with
time is described in the Appendix. It is shown there that $\eps$ can be slowly reduced to 0
so that the target set $T$ itself, rather than its $\eps$-expansion, is approached.
\end{remark}

\section{Policy Mixing}
\label{sec:small}

Up to now we did not impose any restrictions on the directional steering policies that P1 can employ.
Suppose now that P1 may choose between a finite and given set of policies
$\pi_1,\ldots,\pi_J$. For simplicity we may restrict the policy changes to occur in
renewal epochs to some reference state $s^*$.
To motivate this problem, one may consider an agent who has a few pre-programmed control policies.
These policies may have been found useful for different tasks in this environment or are
just intelligent guesses of reasonable policies. The agent wants to mix
the policies in such a way so that the target set is approached.
The idea is to mix between the prescribed policies so that when steering in
a direction $u$ the best policy among the $J$ available policies is used.
To choose the best such policy, a Multi-Armed Bandit (MAB) algorithm is employed.
We describe an algorithm in the spirit of CDRL which
we call SPRL (Specified Policies Reinforcement Learning).

If P1 knew the model parameters, P1 could choose the policy that
is best in Equation~\req{eq:B condition} in the current steering direction
(out of the set of given policies).
In that case it follows from Theorem \ref{thm:BLCKWLLclassic} that
the set $T$ is approachable if for every point $x\not\in T$ there exists a
policy $\pi_i$, $1\le i \le J$, such that
\be
\label{eq:approachabiliywithJ}
\left(\phi(\pi_i,\sigma) - C_x\right) \cdot u_x \ge 0\,, \quad
\forall \sigma \in \Sigma \,.
\ee
In that case we say that $T$ is approachable with $\pi_1,\ldots ,\pi_J$.

We set out to show that if $T$ is approachable with $\pi_1,\ldots ,\pi_J$ when the
model is known then it is approachable with $\pi_1,\ldots ,\pi_J$ when
the model is unknown.
{\Red The following algorithm
resembles the CDRL algorithm in that every once in a while P1 changes the steering
direction to best approach $T$.
In order to steer in the current direction}
we use appropriate algorithms for the adversarial MAB problem, such as the Exp3.1 algorithm of \cite{ACFS02},
as a policy selection mechanism.
Recall that in the adversarial MAB problem a decision
maker is repeatedly required to decide between $J$ arms. When choosing arm $i$
at time epoch $n$ a reward of $r_n^i$ is obtained. The decision maker tries to make sure that its cumulative
reward is close to the one obtained at the best arm.
We assume that a MAB arm selection algorithm, $\pi$, is defined by the following operations:
\begin{enumerate}
\item $Init_{\mbox{MAB}}(J)$ - Initialize the parameters of MAB with $J$ arms.
\item $GetArm_{\mbox{MAB}} ()$ - Returns the arm $a$ that MAB wants to sample next.
\item $Update_{\mbox{MAB}} (i, r)$ - Informs MAB the latest reward $r$ of arm $i$.
\end{enumerate}
The dynamics of every algorithm for the MAB problem are described as follows. First, each
MAB algorithm is initialized. At every time epoch $n$, $GetArm_{\mbox{MAB}}$ is
used for picking an arm $i_n$ and a reward $r_n = r_n^{i_n}$ is
obtained. $Update_{\mbox{MAB}} (i_n, r_n)$ is used to update the
algorithm with the knowledge of the obtained reward.
In the adversarial MAB formulation, there are two
players - P1 and P2. P1 chooses which arm to play and simultaneously
(not knowing P1's choice)
P2 chooses how much reward to give to P1 for every possible
choice of P1. The basic requirement from a MAB algorithm is that for
every $\eps>0$ there exists $N(\eps)$ such that
\be \label{eq:MABcondition} \Exp_{\pi,\sigma}\frac{1}{N(\eps)} \sum_{n=0}^{N(\eps)-1} r_n \ge \max_{1\le j \le J}
\sum_{n=0}^{N(\eps)-1} r_n^j -\eps \quad \,\mbox{for
every policy $\sigma$ of P2,} \,
\ee
where the expectation is taken over both player's policies, as the resulting
policy (for both players) may be stochastic.
Equation~(\ref{eq:MABcondition}) means that the expected average reward by time
$N(\eps)$ is almost as high as the average reward that would have been obtained
if P1 would have known the reward of each arm in advance.
Note that it is assumed that
P2 decides on P1's reward for every action (arm) chosen at every time epoch. The
Exp3.1 algorithm satisfies Equation~\req{eq:MABcondition}. Moreover, $N(\eps)$
depends only on  $\eps$, $J$  and a bound on the immediate reward.


To state the SPRL algorithm we shall require the concept of {\em $\eps$-mixing time} \citep[see][]{BrafTen02}.
The $\eps$-mixing time $K$ is a (large enough) number so that for every $1\le i \le J$, every policy $\sigma$ of P2,
and every initial state $s$,
$$
\Exp^s_{\pi_i,\sigma} \frac{1}{K} \sum_{n=0}^{K-1} r_n \ge
\inf_{\sigma'} \frac{ \Exp^{s^*}_{\pi_i,\sigma'} \sum_{t=0}^{\tau-1} r_t}{\Exp^{s^*}_{\pi_i,\sigma'} \tau} -\eps \,,
$$
where $\tau$ is the stopping time defined in Equation~\req{eq:taudef}.
Having an $\eps$-mixing time implies that the expected reward starting from
any initial state is at least as high (up to $\eps$) as the worst case average
reward starting from $s^*$.
It follows by Lemma 3.4 from \cite{SS93} that when
Assumption \ref{ass:stabgames} holds then there exists $K_0$
such that the expected return time to $s^*$ from every state and every pair of
policies is bounded by some $K_0$. By choosing $K \ge K_0 M /\eps$
the above condition is satisfied ($M$ is a bound on the expected one stage reward).
The basic requirement of the SPRL algorithm is that $K$, or an upper bound on it, is provided.

% insert it in figure like manner
\begin{figure}[h]
\begin{center}
\begin{tabular}{|p{14cm}|}
\hline Input: Required precision $\eps$; set of policies $\pi_1,\ldots,\pi_J$; $\eps/2$-mixing
time $K$;\\ \quad\quad\quad a recurrent state $s^*$. \\
\hline
0. $n=0$; play arbitrarily until $s_n=s^*$.\\
1. Repeat forever \\
2. \quad If $\hat{m}_n \in T^\eps$ play arbitrarily for $K$ steps. \\
3. \quad Else let $u= u_{\hat{m}_n}$. \\
4. \quad $Init_{MAB}(J)$. \\
5. \quad Repeat $N(\eps/2)$ times: \\
6. \quad \quad $i= GetArm_{MAB}$. \\
7. \quad \quad Play $\pi_i$ for $K$ epochs, let the total reward over the $K$
epochs be $m_{tot}$,\\\quad\quad \,\,\,\,\, set $r = m_{tot} \cdot u$; $n:=n+N(\eps/2)$.\\
8. \quad \quad $Update_{MAB}(i,r)$. \\
\hline
\end{tabular}
\end{center}
\caption{The SPRL algorithm - switching between a given small set of policies.} \label{fig:MCRLknown}
\end{figure}

\begin{theorem}
\label{th:SPRL}
Suppose that $T$ is approachable with $\pi_1,\ldots \pi_J$ when the model is known. Then
the SPRL algorithm described in Figure~\ref{fig:MCRLknown} approaches
$T^\eps$.
\end{theorem}
\proof
The proof is based on showing that by using the SPRL algorithm
Equation~\req{eq:B condition} holds for the expanded target set $T^\eps$. Consider the reward in the epochs
$\tau_i = i K N \ (i=1,2,\ldots)$, for $N=N(\eps/2)$. We claim that the vector valued reward at those
points satisfies Blackwell`s condition.
By using the SPRL algorithm it follows that either $\hat{m}_{\tau_i} \in T^\eps$ or that
\be
\label{eq:epsexpansionagain}
\Exp \left(\Big(\frac{\sum_{n=\tau_i}^{\tau_{i+1}-1} m_n}{KN}  - C_{\hat{m}_{\tau_{i}}}\Big)
\cdot u_{\hat{m}_{\tau_{i}}} \Big| F_{\tau_i} \right )\ge -\eps
\quad \mbox{a.s.} \,,
\ee
where $C_{\hat{m}_{\tau_{i}}}$ is the closest point to $\hat{m}_{\tau_{i}}$ in $T$ and
$F_n$ is the sigma algebra up to time $n$.
Fix $i$ and let $r_n \bydef (m_n - C_{\hat{m}_{\tau_{i}}} )\cdot u_{\hat{m}_{\tau_{i}}}$ for
$\tau_i \le n\le \tau_{i+1}-1$.
By our choice of playing an $\eps/2$ MAB algorithm it follows that
\begin{eqnarray}
\Exp^{s_{\tau_i}}_{\pi,\sigma} \left(\frac{1}{KN} \sum_{n=\tau_i}^{\tau_{i+1}-1} r_n \right)=
\Exp^{s_{\tau_i}}_{\pi,\sigma} \left(\frac{1}{N} \sum_{\ell=0}^{N-1} \frac{1}{K} \sum_{n=\tau_i + \ell K}^{\tau_i + (\ell+1) K -1} r_n \right)\nonumber\\
\ge \max_{1\le j \le J}
\frac{1}{N} \sum_{\ell=0}^{N-1} \frac{1}{K} \Exp^{s_{\tau_i + \ell K}}_{\pi_j,\sigma}
\left( \sum_{n=\tau_i + \ell K}^{\tau_i + (\ell+1) K -1} r_n \right) - \eps/2 \,.
\label{eq:Ebandits}
\end{eqnarray}
Since $K$ is an $\eps/2$-mixing time we have that for every $1\le j \le J$ and $1\le \ell < N$,
$$
\Exp^{s_{\tau_i + \ell K}}_{\pi_j,\sigma} \frac{1}{K} \sum_{n=\tau_i+\ell K}^{\tau_{i}+(\ell+1)K-1} r_n
\ge
\inf_{\sigma'} \frac{ \Exp^{s^*}_{\pi_j,\sigma'} \sum_{t=0}^{\tau-1} r_t}{\Exp^{s^*}_{\pi_i,\sigma'} \tau} -\eps/2 \,.
$$
Since this holds for every $1\le j \le J$, we substitute this in Equation~\req{eq:Ebandits} to obtain
$$
\Exp^{s_{\tau_i}}_{\pi,\sigma} \left(\frac{1}{KN} \sum_{n=\tau_i}^{\tau_{i+1}-1} r_n \right) \ge
\max_{1\le j \le J}
\inf_{\sigma'} \frac{ \Exp^{s^*}_{\pi_j,\sigma'} \sum_{t=0}^{\tau-1} r_t}{\Exp^{s^*}_{\pi_i,\sigma'} \tau} -\eps \,.
$$
Using the definitions of $r_n$ and $C_{\hat{m}_{\tau_{i}}}$, Equation~\req{eq:epsexpansionagain} follows.
The rest of the proof follows almost exactly as Theorem \ref{th:CDRL}
and is therefore omitted. \qed

Several comments are in order.
\begin{remark}
We note that even if $\pi_i$ are learning policies rather than a-priori fixed
ones the algorithm still works. The only thing that matters in this case is that
the strategies converge after some finite stochastic time. This suggests the following algorithm.
Learn the optimal policy for several directions, and use the SPRL algorithm
for mixing the learned strategies.
\end{remark}
\begin{remark}
It is possible to obtain Theorem \ref{th:SPRL} with $\eps=0$. This can be done
by a limiting procedure similar to Theorem \ref{th:modCDRL}
with the additional complication that both the $\eps$-mixing time and the time required
by the MAB algorithm increase. It can be shown that for certain MAB algorithms
$N(\eps) \sim \frac{1}{\eps^2}$ and
that the behavior of the mixing time as a function of $\eps$ is $K(\eps) \sim \frac{1}{\eps}$.
The total time is approximately $O(\frac{1}{\eps^3})$, and the technique of Theorem \ref{th:modCDRL}
may be employed.
\end{remark}

\section{On-line Selection of Target Sets}
\label{sec:unknown target}

In many problems of interest the target set that we wish to approach
may itself depend on the unknown model parameters, so that it cannot
be explicitly prescribed {\em a-priori} to the learning agent.
The simplest and most common instance of this situation is the simple
maximization of a scalar objective function: this corresponds to a target
set of the form $[a,\infty)$, with $a$ required to be as large as possible.
We generalize this situation to the multi-objective case by considering
a {\em nested} family of possible target sets,
and assume that the agent's task it to approach the minimal
target set, namely the smallest possible one for the actual model at hand.
The major difficulty in applying the steering approach now is that the
required steering direction is not known, as it may be different
for each set in the given family.
We address this difficulty by maintaining an estimate of the smallest
set that can be approached, which is used as a target for steering,
and updating this estimate according to observations.
In the latter part of this section we apply these results to
solve the problem of learning optimal policies in constrained stochastic games.
Throughout this section we assume that all target sets are convex.

\subsection{Nested Target Sets}
\label{sub:nested}

Consider an increasing class of convex sets $\{T_\alpha\}_{\alpha \in
\m{L}}$, indexed by the ordered set of indices $\m{L}$ such that
$\alpha < \beta$ implies $T_\alpha \subseteq T_\beta$.  For
simplicity, we may consider $\m{L} = \reals$ and assume that
$\{T_\alpha\}$ is continuous.\footnote{Continuity here is induced by
the metric, implying that the distance between sets is small when the
indices are close. Formally, we require that if $\alpha_k \to \alpha$
then $\sup_{x \in T_\alpha \cup T_{\alpha_k}}
\inf_{y \in T_\alpha \cap T_{\alpha_k}} d(x,y) \to 0$.
}
The objective is to approach the smallest possible set in this class, that is to
approach the smallest possible $T_\alpha$.
Recall that the third part of Theorem \ref{thm:convexapproachability} claims
that a convex target set is approachable if and only if
for every $u\in \Ball^k$, $\val\Gamma(u) \ge \inf_{m\in T} u \cdot m$.
{\Red
Consider a direction $u$, and let $\val(u)=\val\Gamma(u)$ denote the
value of the game in this direction. Let
$\alpha(u,\val(u))$ denote the smallest (or infimal) value $\alpha$ for which
$\val(u) \geq \inf_{m\in T_\alpha} u\cdot m$. (Note that
we define $\alpha(u,\val(u))$ for any value $\val(u)$,
since below we shall use an estimate to $\val\Gamma(u)$ rather
than the exact value). Then, according to Theorem \ref{thm:convexapproachability}
the set $T_\alpha$ may be approachable only if
$\alpha\geq \alpha(u,\val\Gamma(\alpha))$, and the smallest
approachable set is
}
$$
T^*=\bigcap_{u \in \Ball^k} T_{\alpha(u,\val \Gamma(u))} = T_{\alpha^*} \,,
$$
where $\alpha^* = \sup_{u \in \Ball} \alpha(u,\val \Gamma(u))$.
{\Red See Figure~\ref{fig:nested} for a geometric illustration of
the problem.}

\begin{figure}[h]
  \begin{center}
    \psfig{file=nested2.eps,width=.8\textwidth}
    \caption{\label{fig:nested} {\Red A two dimensional Illustration of nested sets.
    In the illustration $\alpha_1 < \alpha_2< \alpha_3$ so that
    $T_{\alpha_1} \subset T_{\alpha_2} \subset T_{\alpha_3}$. For
    the direction $u$ the value of the projected game $\Gamma(u)$
    is such that $\alpha(u,\val\Gamma(u)) = \alpha_2$. As a result
    a target $T_\alpha$ set may be approachable if $\alpha \ge
    \alpha_2$. In this case $T_{\alpha_3}$ may be approachable, but
    $T_{\alpha_1}$ is not approachable.
    }}
    \end{center}
\end{figure}



We now suggest a modification of the MDRL algorithm for
approximately approaching $T^*$. Recall that the MDRL algorithm is
based on switching between a grid of $J$ steering directions
$u_1,\ldots,u_J$. For each direction $u_j$ an asymptotically $\eps$-optimal learning algorithm
$\pi_j$ is applied. In the
original MDRL algorithm some directions may be encountered
finitely many times so that the learned directional steering policy may be
suboptimal. Since $T$ is not prescribed and should be estimated
on-line, we will impose exploration in each of the $J$ steering
directions. Fix a direction $u_j$. Let $\tilde{\val}(u_j)_n$ be
the estimate by time $n$ of $\val\Gamma(u_j)$. We require that the
estimate is not too pessimistic. That is,
\be \label{eq:tildev}
\liminfn \tilde{\val}(u_j)_n \ge \val\Gamma(u_j) - \eps \quad
P_{\pi_j,\sigma}-\mbox{a.s}\,, \ee
where $\pi_j$ is the learning policy when steering in direction $u_j$,
$\sigma$ is P2's policy, and Equation~\req{eq:tildev} holds for
all $\sigma$. We also require that for every $\pi_j$, \be
\label{eq:tildevlimexist} \lim_{n \to \infty} \tilde{\val}(u_j)_n
\quad\mbox{exists } P_{\pi_j,\sigma}-\mbox{a.s.}  \ee This
requirement is not essential, but simplifies the analysis
and is fulfilled by all the learning algorithms we are aware of.
We also assume that the estimate of the value is not too
optimistic and matches P2's policy in the following sense: \be
\label{eq:tildevandpolicy} \liminfn \left(
\frac{\Exp^{s^*}_{\pi_n,\sigma} \sum_{t=0}^{\tau-1}
r_t}{\Exp^{s^*}_{\pi_n,\sigma} \tau} - \tilde{\val}(u_j)_n \right)
\ge -\epsilon \quad \mbox{$P_{\pi_j,\sigma}$-a.s} \,, \ee for
every policy $\sigma$ of P2 ($\tau$ is the renewal time from
Equation~\req{eq:taudef}). Intuitively, Equation~\req{eq:tildevandpolicy} means that
P1's policy guarantees an expected reward which is not much
worse than the estimated value $\tilde{\val}(u_j)_n$. Without
Equation~\req{eq:tildevandpolicy}, the target set may not be estimated
correctly, and the steering direction may be wrong. All three
assumptions Equation~\req{eq:tildev}-\req{eq:tildevandpolicy} are satisfied
by Q-learning for average reward games of \cite{MS02Qlrn} under
mild additional assumptions on P2's play (the assumption there was
that every action is either played a non vanishing fraction
of the times or finitely many times, but the fraction of times
may not alternate between 0 and something bigger than 0).
The above requirements may also be seen to be satisfied by model-based
learning algorithms under the assumption that all actions by P2
are played infinitely often. We note that $\tilde{\val}(u_j)_n$ in
Equation~\req{eq:tildev} may be larger than the true value
$\val\Gamma(u_j)$. The reason for that is that $\tilde{\val}(u_j)$
is an estimate which is based on the observations. If P2 refrains
from playing certain actions (which are worst-case in
$\Gamma(u_j)$) then P1 cannot, and need not, take these action
into consideration.

In Figure~\ref{fig:MCRLpres} we describe a modified
version of the MDRL algorithm.
Essentially we add to the MDRL algorithm a small probability of
exploration on each return to the reference state $s^*$.
Exploration is made uniformly over the $J$ available directions.
For each direction $u_i$ (all directions are
chosen comparatively often due to the exploration) an index is
maintained for the value of the projected game. This index
represents the current estimate of $\alpha(u,\val \Gamma(u))$. The
goal is to approach an ``almost" minimal set.
The steps of the algorithm are very similar to the MDRL algorithm
from Figure~\ref{fig:MCRL}. The differences are the persistent exploration that
is performed continually (step 2 of the algorithm) and the fact that
the estimated target set replaces the true (unknown) target set. Exploration
is made when either $\hat{m}_n$ is inside the estimated target set (and therefore the decision
maker does not need to steer in any direction),
or with some small probability when returning to $s^*$.
The latter exploration is needed in order to guarantee that
the estimate of the target set is eventually consistent.
The estimate of the target set is based on estimating the index
that each of the $J$ projected games and taking the maximal index
to be the current estimate of the index of the target set.
We wish to approach the set $T_\alpha$ with minimal index that
is approachable.
The estimate of the index by time $n$ is denoted by
$indmax_n$ and equals
$$indmax_n \bydef \max_{1\le i\le J}
\alpha(u_i,\tilde{\val}(u_i)_n).$$
{\Red
We take the maximal index (over the $J$ available directions), because if
$\alpha <\alpha(u_i,\tilde{\val}(u_i)_n)$ for some $i$ it
implies that, according to the current estimate, $T_\alpha$ is not approachable for
$\alpha <\alpha(u_i,\tilde{\val}(u_i)_n)$.
}
The estimate of the target set
by time $n$ is
\be
\label{eq:tildeT} \tilde{T}_n =  T_{indmax_n}
\,. \ee

For every $\eps>0$ define the maximal index $indmax(\eps) \bydef \max_{1\le i\le J}
\alpha(u_i,\val\Gamma(u_i)-\eps)$. The target set P1 tries to
approach is $T_{indmax(\eps)}$. The modified MDRL
algorithm from Figure~\ref{fig:MCRLpres} approaches
the set $T_{indmax(\eps)}^\eps$, which is the $\eps$-expansion of
$T_{indmax(\eps)}$.

\begin{figure}[h]
\begin{center}
\begin{tabular}{|p{14cm}|}
\hline
Input: Desired approximation level $\eps$; a set class $\{T_\alpha\}_{\alpha\in \m{L}}$; a bound $M$ on the \\
\quad \quad \quad expected one step reward; a bound $N$ on the expected renewal time to $s^*$.\\
\hline 0. Divide the unit vector ball $\Ball^k$ as in Proposition
\ref{prop:finite_directions} for approaching the $\eps/3$ \\
\quad expansion
of any target set. Let $U=u_1,\ldots, u_J$ be the chosen directions. \\\quad Initialize
$J$ different asymptotically $\eps/3$-optimal scalar algorithms, $\pi_1,\ldots,\pi_J$ \\
\quad that satisfy Equation~\req{eq:tildevandpolicy}. \\
1. Choose a random direction $u_i \in U$ and play $\pi_i$ until $s_n=s^*$.\\
2. ($s_n = s^*$) If $\hat{m}_n \in \tilde{T}_n$ goto step 1. \\
\quad \quad Else with probability $\delta = \eps/(3MN)$ goto 1.\\
3. Let $u = \frac{\hat{m}_n - C(\tilde{T}_n,\hat{m}_n)}{\|\hat{m}_n - C(\tilde{T}_n)\|}$. ($C(T,x)$ denotes
the closest point in $T$ to $x$.) \\
4. Let $i = \argmin_{1\le i \le J} \|u-u_i\|$.\\
5. While $s_n \ne s^*$ play according to $\pi_i$, the reward
$\pi_i$ receives is $u_i \cdot m_n$. \\
6. When $s_n =s^*$ goto step 2.\\
\hline
\end{tabular}
\end{center}
\caption{The modified MDRL for unprescribed target sets.} \label{fig:MCRLpres}
\end{figure}

The following Theorem claims that $T^{\eps}_{indmax(\eps)}$ is approached using the
modified MDRL. Since we assume that the class $\{T_\alpha\}$ is continuous in $\alpha$,
by taking $\eps$ small enough we can practically get as close as we wish to $T$.

\begin{theorem}
\label{th:MDRLUnspecified}
Suppose that Assumption \ref{ass:stabgames} holds
and that the target set satisfies Equation~\req{eq:B condition}.
Further assume that each scalar learning algorithm satisfies
Eqs.~\req{eq:tildev}, \req{eq:tildevlimexist}, and \req{eq:tildevandpolicy}, where
Equation~\req{eq:tildev} and Equation~\req{eq:tildevandpolicy} are satisfied with $\eps/3$ instead of $\eps$.
Then $T^{\eps}_{indmax(\eps)}$ is approached
using the modified MDRL algorithm from Figure~\ref{fig:MCRLpres}.
\end{theorem}
\proof (outline)
Exploration is persistent in all directions.
By the definition of the algorithm, exploration cannot cause more that
$\eps/3$ drift away from the target set.
Since each algorithm
satisfies Equation~\req{eq:tildevandpolicy} and since the estimate $\tilde{\val}(u_j)_n$
converges to a limit by Equation~\req{eq:tildevlimexist} it follows that
from some (random) time on P2's expected reward when steering in direction $j$ is
up to $\eps/3$ as high as $\lim_{n\to\infty}\tilde{\val}(u_j)_n$.
By Equation~\req{eq:tildev} and Equation~\req{eq:tildevlimexist} the limit of
$\tilde{\val}(u_j)_n$ is not less than $\val\Gamma(u_j) -\eps/3 $.
It follows that from some (random) time on the estimate
of $\tilde{T}_n$ almost does not change
(more specifically, we assume that Equation~\req{eq:tildevlimexist} holds so that
$\tilde{\val}(u_j)_n$ converges. From some
random time on, all the $J$ estimates $\tilde{\val}(u_j)_n$ converge.
By the continuity of $T_\alpha$ in $\alpha$, it follows that
the set $\tilde{T}_n$ converges to some, random, $\tilde{T}_\infty$).
After that time - the same analysis as in Theorem \ref{th:main} may be performed. \qed

There is a special case in which there is no need to perform the exploration for estimating
$\tilde{v}(u_i)_n$. This is the case where the sets in the target set class are balls around
a target point.
Namely, if there is some point $x_0$ such that for every $\alpha$ in $\m{L}$ there is a number $\gamma$ such
that $T_\alpha$ is a ball with radius $\gamma$ around $x_0$.
The steering directions is always towards $x_0$ and is the same for all the candidate target sets.
Consequently, the MDRL algorithm does not require any changes, and exploration is not required.

\subsection{Constrained Stochastic Games}
A specific case of interest is the case of constrained optimization which has been extensively explored
for MDPs \citep[see][and references therein]{Alt99}.
In this setup the decision maker obtains in every time step both reward and additional
variables.
The objective of the decision maker is to maximize its average reward $\hat{r}_n$ given
that some additional average variables $\hat{c}_n^1,\ldots ,\hat{c}_n^k$
satisfy the constraints $\hat{c}_n^i \le \bar{c}^i, i=1,\ldots,k$.
The policy of P2 remains unconstrained and arbitrary.
The immediate reward vector in this game is comprised of one coordinate which is the actual scalar reward
and the remaining $k$ coordinates that are the constraints.
The maximization of the reward is performed on a sample path,
so the average reward should be optimal almost surely.
For zero-sum stochastic games where P1 tries to maximize the average reward subject to the constraints
it was shown by \cite{Shimkin94} that under Assumption \ref{ass:stabgames}, and provided
that the constraints can be
satisfied by some policy, there exists a value $\val$. This implies that P1 can guarantee that
$\liminf_{n\to \infty} \hat{r}_n \ge \val$
and $\limsupn \hat{c}_n\le \bar{c}$ (with the last inequality a vector inequality) almost surely.
It was also shown there that P1 cannot guarantee a reward higher than $\val$ while
satisfying the constraints.

We now show that the constrained optimization problem may be solved by the framework of the nested
target sets.
Let the candidate set class $\{T_\alpha\}$
be defined in the reward-constraints space:
$$
T_\alpha = \{(r,c^1\ldots,c^k): r\ge -\alpha, c^1 \le \bar{c}^1,\ldots, c^k \le \bar{c}^k\} \subseteq \R{k+1} \,.
$$
The $\alpha$ belongs to the index set $\m{L}=\reals$.
It obviously holds that if $\alpha<\beta$ then $T_\alpha \subset T_\beta$
and that $T_\alpha$ is convex for all $\alpha$. Continuity of the class $\{T_\alpha\}$ holds
as well.
Using the MDRL algorithm with
persistent exploration we can find the minimal set to be approached.
Since we only use a finite grid of directions as in the MDRL algorithm,
the guaranteed reward is $\val - \eps$, with constrains satisfied up to $\eps$.
But since $\eps$ is arbitrary we can effectively get as close as we want to the value.
We summarize the results in the following proposition.
\begin{proposition}
Assume that some policy satisfies $\limsupn \hat{c}_n \le \bar{c}$.
Suppose that the modified MDRL algorithm is used for finding the optimal
policy in a constrained SG, and that the assumptions of
Theorem \ref{th:MDRLUnspecified} are satisfied. Then
$\liminfn \hat{r}_n \ge \val-\eps$ and $\limsupn \hat{c}_n \le \bar{c}+\eps e$ where the
last inequality is in vector notations, and $e$ is a vector of ones.
\end{proposition}

We now describe more explicitly the estimation of the target set
for the constrained optimization problem. We denote the first coordinate of a unit
vector in $\Ball^{k+1}$ by $u^r$ and the rest
of the $k$ coordinates by $u^c$.
Suppose that at time $n$ we are given an estimate $indmax_n$ of the value $\val$.
By the geometry of the problem it follows that for any point
$(r,c)$, the closest point in $\tilde{T}_{n}$ is
$(r',c_1',c_2',\ldots,c_k')$
where $r' = \max\{r,indmax_n\}$ and $c_i' = \min\{c_i,\overline{c}_i\}$.
{\Red Because of the special structure of the target set and its
convexity,} the set of directions which may possibly be
steering directions (in the $k+1$ unit ball) is given by
\be
\label{eq:possteer}
SD=\{(u^r,c^1,\ldots ,c^k)\in \Ball^{k+1} : u^r \ge 0 , c^1 \le 0 ,\ldots, c^k \le 0\} .
\ee
To observe that this is the set of possible steering directions, we first note that $u^r \ge 0$
since there is no point in trying to reduce the reward.
Indeed, it is easily seen that
otherwise $\inf_{m\in T_\alpha} u \cdot m =-\infty$ for all $\alpha$,
so that $\alpha(u,\val(u)) = -\infty$.
Second,
if a constraint is satisfied then the steering direction will
not attempt to violate it.
It therefore suffices to consider steering directions, $u_1,\ldots,u_J$, that belong to
$SD$. We now show how to estimate the index of the target set given
current estimates of the value for each of the projected games.
\begin{proposition}
Given directions $u_1,\ldots,u_J$ and estimates $\tilde{\val}(u_j)$, $1\le j\le J$, the estimated
index of the target set $\tilde{T}_n$ is given by
$$
indmax_n = - \min_{1\le j \le J, u^r_j >0} \frac{\tilde{\val}(u_j)_n - u_j^c \cdot (\bar{c}^1,\ldots, \bar{c}^k)}{u_j^r} \,,
$$
\end{proposition}
\proof
By the geometry of the problem
each direction $u_j$ and corresponding estimate of the value $\tilde{\val}(u_j)$ define a ``half space''
which must intersect with the estimated target set (by Theorem \ref{thm:convexapproachability}).
This half space is given by: $\{(r,c) \in \reals\times \reals^k: (r,c)\cdot (u_j^r,u_j^c) \ge\tilde{\val}(u_j)\}$.
The target set is of the form $\{(r,c): r\ge r_{max}(u), c\le \bar{c} \}$,
where $r_{max}(u)$ the maximal scalar reward which can be achieved by a specific steering direction $u$ while satisfying
the constraints, {\Red for an illustration see Figure~\ref{fig:constillust}.} It follows that $r_{max}$ is in fact the index $\alpha$ in the construction of the candidate target set
class. Since $u_r \ge 0$ and $u_c \le 0$ it follows that
$$
(u^r,u^c) \cdot (r_{max}(u),\bar{c}^1,\ldots ,\bar{c}^k) = \tilde{\val}(u) \,,
$$
so that (assuming $u^r \ne 0$)
$$
r_{max}(u) = \frac{\tilde{\val}(u)- u^c \cdot (\bar{c}^1,\ldots, \bar{c}^k)}{u^r} \,.
$$
Overall, the maximal reward that can be achieved is
\be
\label{eq:ramaxest}
r_{max}= \inf_{\{u \in \Ball^{k+1}: u^r>0, u^c\le 0\}} r_{max}(u) \,.
\ee
The result follows by considering finitely many directions and recalling that
the index is minus $r_{max}$. \qed

\begin{figure}[h]
  \begin{center}
    \psfig{file=const2.eps,width=.6\textwidth}
    \caption{\label{fig:constillust} {\Red A two dimensional Illustration of finding the value for a constrained game.
    The $x$ axis is the reward and the $y$ axis is the constraint. The value of the game projected
    on direction $u$ is $\val\Gamma(u)$ which implies that the achievable reward is at most
    $r_2$, and possibly less.
    An average reward of $r_1$ is not achievable since the set
    $\{(r,c): r\ge r_1, c\le\overline{c}\}$ does not satisfy Theorem
    \ref{thm:BLCKWLLclassic} for the direction $u$.
    }
    }
    \end{center}
\end{figure}


The last two propositions imply that we can solve
constrained SGs, and in particular, constrained MDPs.
To the best of our knowledge this is
the first RL algorithm that solves constrained SGs.
Regarding constrained MDPs, we note that one can envision a model-based algorithm
\citep[in the spirit of the $E^3$ algorithm of][]{KS98}, however
such an algorithm would work only for small problems.
Our algorithm may be applied in a model-free setup, as long as underlying
model-free scalar RL algorithms can be used.
We also comment that the Q-learning style algorithm of \cite{KSZ98} searches for
the optimal deterministic policy, while the optimal one may
be stochastic.
An example for the solution of constrained MDPs is provided
in Section~\ref{sub:constrainedMDP}.


\begin{remark}
\label{rem:gentargetsets}
For general target sets it is possible to devise a similar algorithm to the above where
the target set is estimated on-line. For example, one can estimate the game parameters and
derive a candidate for the target set based on that estimate. We note that
as long as the estimate is consistent (i.e., the final estimate is the actual
set to be approached) then schemes which are based on MDRL or CDRL will approach the target set.
For example, one may consider approaching the convex Bayes envelope \citep{MS03MOR} to
arrive at a optimal on-line algorithm for stochastic games.
For convex sets there is a particularly interesting possibility
of learning the support function \citep{R70}. Recall that a convex set $T$ can be
written as
$$
T = \bigcap_{u\in \Ball^k} \{x: u\cdot x \ge f_T(u)\} \,,
$$
{\Red
where the function $f_T(u):\Ball^k \to \reals$ is  the {\em support function} of $T$, which is
defined as $f_T(u) \bydef \inf_{y\in T} u\cdot y$. }
The steering direction can be characterized as the maximizer of $f_T(u)-u \cdot x$
\citep{M02phd}. Now, if $f_T(u)$ can be learned somehow then instead of the true
unknown steering direction an approximate steering direction which the maximizer
of the $\tilde{f}_T(u)-u \cdot x$, where $\tilde{f}_T$ is the estimate of $f_T$, can be used.
This approach may prove useful when the support function has a simple representation.
\end{remark}


%++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

\section{Multi-Criterion MDPs}
\label{sec:MDPs} In this section we briefly discuss multi-criterion
MDPs. These models may be regarded as a special
case of the stochastic game model that was considered so far, with
P2 eliminated from the problem. We shall thus only outline the
main distinctive features of the MDP case.

Both the MDRL algorithm from Section~\ref{sec:MCRL} and
the CDRL algorithm from Section~\ref{sec:CDRL} remain essentially the same.
Their constituent scalar learning algorithms are now learning
algorithms for average-reward MDPs. These
algorithms are generally simpler than algorithms for the game problem. Examples of
optimal or $\epsilon$-optimal algorithms are Q-Learning with
persistent exploration \citep{NDP}, actor-critic schemes
\citep{SB98}, the $E^3$ algorithm
\citep{KS98}, and others.
Additionally, it should be noted that the
steering policies learned and used within the MDRL algorithm may now be {\em
deterministic} stationary policies, which simplifies the
implementation of this algorithm.

Working with a finite number of specified policies as in Section~\ref{sec:small} is particularly simple.
In this case all that P1 needs to do is to estimate the average reward vector that each policy
yields. P1 can attain every point in the convex hull of the average per policy
reward vectors by mixing the strategies appropriately.
In the absence of an adversary, the problem of approaching a set
in a known model becomes much simpler. In this case, if a set is approachable
then it may be approached using a stationary (possibly mixed)
policy. Indeed, any point in the feasible set of state-action
frequencies may be achieved by such a stationary policy
\citep{Derman70}. Thus, alternative learning schemes that do not rely on
the steering approach may be
applicable to this problem.

%++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


\section{Examples}
\label{sec:illus}

Two brief examples will be used to illustrate the above
framework and algorithms.
In Subsection~\ref{sub:temphumidity} we show what sample paths of
the MDRL algorithm look like for the two dimensional temperature-humidity
problem from the introduction. In Subsection~\ref{sub:constrainedMDP}
we solve on-line a queuing problem which is modelled as a constrained MDP.

\subsection{The Two-Dimensional Temperature-Humidity Problem}
\label{sub:temphumidity}
Recall the humidity-temperature example from the introduction.
Suppose that the system is modelled in such
a way that first P1 chooses a temperature-humidity curve by, say,
deciding if to activate heater/cooler or humidifier/dehumidifier  a-priori.
Then Nature (modelled as P2) chooses the exact location on the
temperature-humidity curve by choosing the weather that
affect the conditions in the greenhouse.
Essentially, P1 chooses the set where the immediate rewards lie in and
P2 chooses the exact location of the reward in that set.
In Figure~\ref{fig:I}(a) we show the
target set $T$ and three different temperature-humidity curves (these
curves are representative curves).
Geometrically, P1 chooses the curves where the reward belongs to (each defined by a certain policy
of P1 - $f_0,f_1,f_2$), and P2 chooses the exact location. Additional zero mean with unit variance
noise was added to each reward entry. It so happens that there is no
stationary policy for P1 which guarantees that the average
reward is in $T$, regardless of P2's actions. We implemented an MDRL algorithm with a
``dense'' grid of only nine directions. In each direction a
version of Littman`s Q-learning \citep{L94}, adapted for average
cost games, was used \citep{MS02Qlrn}. P2's policy was
adversarial, and it tried to get the average reward away from the
target set. Three sample paths of the average reward for 100,000
epochs that were generated by the MDRL algorithm are shown in
Figure~\ref{fig:I}(b). Each sample path starts at 'S' and finishes
at 'E'. It can be seen that the learning algorithm pushes towards
the target set so that the path is mostly on the edge of the
target set. Note that in this example a small number of directions
was quite enough for approaching the target set. Since the
convergence was so fast it made no sense to use the
CDRL algorithm, though we would expect it to work well in this case.

\begin{figure}[h]
  \begin{center}
    \begin{tabular}{cc}
    \psfig{file=probdynamics3.eps,width=0.5\textwidth} &
    \psfig{file=3pathstake2.eps,width=0.5\textwidth}
    \end{tabular}
    \caption{{\bf (a)} Greenhouse problem dynamics. {\bf (b)} Three sample paths from 'S' to 'E'.}
    \label{fig:I}
    \end{center}
\end{figure}

\subsection{Constrained Optimization of a Queue}
\label{sub:constrainedMDP}

In this section we consider the model of a queue with varying service rate.
Suppose that there is a queue of buffer length $L$. Messages arrive to the queue at
a rate of $\mu$. P1 controls the service rate which means that if the queue
is not empty then a message leaves the queue with probability $a_n$.
The state of the system is the number of messages in the queue $\m{S} = \{0,1,2,\ldots,L\}$.
The state transition probability satisfies

$$
\nonumber
P(s_{n+1}|s_n,a) =    \left\{ \begin{array}{ll}
        (1-\mu)a & \mbox{if } L\ge s_n \ge 1 \mbox{ and } s_{n+1}=s_n -1, \\
        \mu a +(1-\mu)(1-a) & \mbox{if } L> s_n \ge 1 \mbox{ and } s_{n+1}=s_n,\\
        \mu +(1-\mu)(1-a) &  \mbox{if } s_{n+1}=s_n=L,\\
        \mu (1- a) & L-1 \ge \mbox{if } s_n \ge 0 \mbox{ and } s_{n+1}=s_n+1,\\
        1-\mu (1-a) & \mbox{if } s_{n+1}=s_n =0, \\
        0 & \mbox{otherwise}.\nonumber\\
        \end{array}
        \right.
$$
The reward of P1 is a function of the number of vacant places in the queue. For simplicity
we assumed that $r_n = c (L-s_n)$ where $c$ is a positive constant.
P1's objective is to maximize the reward it obtains. This
is equivalent to minimizing the average queue length. P1 may affect the state transitions through
change of the service rate $a_n \in \{a_L,a_H\}$. The service constraint of P1 is to have
the average service rate $\hat{a}_n$ lower than some pre-specified constant $c_0$.
The optimization problem we have is
\beaa
& & \max \hat{r}_n \\
& & \mbox{ s.t. } \hat{a}_n \le c_0 \,.
\eeaa
Note that the maximum should be attained per sample path and may be achieved by a
stationary policy \citep[e.g.,][]{Alt99}. Moreover,
it can be shown that there exists an optimal policy with at most one randomization.
We used the modified MDRL algorithm for solving the above problem for different
values of $c_0$. The parameters of the problems were $\mu= 0.5$, $L=9$, $c=0.5$, $\delta=0.01$ (exploration rate
in stage 2 of the modified MDRL algorithm from Figure~\ref{fig:MCRLpres}),
$a_L=0.5$, $a_H=0.8$,
and the number of steering directions was 10.
For three values of $c_0$ we show in Figures
\ref{fig:queue075}-\ref{fig:queue055} the sample path (average reward and average constraint)
on the left side and the estimation of $r_{max}$ over time as per Equation~\req{eq:ramaxest} on the right side.
The final estimate of the target set is also drawn
for each sample path. The average vector-valued reward typically  converges to the corner of the target set
and pretty much stays there with random fluctuations caused by the exploration.
The estimation of $r_{max}$ is quite stable and tends to converge.
As expected, the reward increases as the constraint becomes less stringent.

\begin{figure}[t!]
\begin{center}
\begin{tabular}{cc}
\epsfig{file=queue075.eps,width=0.45\textwidth,height=0.45\textwidth} &
\epsfig{file=queue075rmax.eps,width=0.45\textwidth,height=0.45\textwidth}
\end{tabular}
\end{center}
\caption{A sample path (a) and $r_{max}$ estimation (b) for a run
of the modified MDRL for the constrained queue problem, $c_0 = 0.75$. Note that
$r_{max}$ converged to $4.02$.}
\label{fig:queue075}
\end{figure}

\begin{figure}[t!]
\begin{center}
\begin{tabular}{cc}
\epsfig{file=queue065.eps,width=0.45\textwidth,height=0.45\textwidth}&
\epsfig{file=queue065rmax.eps,width=0.45\textwidth,height=0.45\textwidth}
\end{tabular}
\end{center}
\caption{A sample path (a) and $r_{max}$ estimation (b) for a run
of the modified MDRL for the constrained queue problem, $c_0 = 0.65$.
Note that $r_{max}$ converged to $3.92$.}
\label{fig:queue065}
\end{figure}

\begin{figure}[t!]
\begin{center}
\begin{tabular}{cc}
\epsfig{file=queue055.eps,width=0.45\textwidth,height=0.45\textwidth}&
\epsfig{file=queue055rmax.eps,width=0.45\textwidth,height=0.45\textwidth}
\end{tabular}
\end{center}
\caption{A sample path (a) and $r_{max}$ estimation (b) for a run
of the modified MDRL for the constrained queue problem, $c_0 = 0.55$.
Note that $r_{max}$ converged to $3.45$.}
\label{fig:queue055}
\end{figure}


\section{Conclusion}
\label{sec:conclusion}

%what we've done
We have presented learning algorithms that address the problem
of multi-objective decision making in a dynamic environment,
which may contain arbitrarily varying elements,
focusing on the long-term average reward vector.
The proposed algorithms learn to approach a
prescribed target set in multi-dimensional performance space,
provided this set satisfies a certain geometric condition
with respect to the dynamic game model. For
convex sets, this sufficient condition is also necessary.
The algorithms we suggested
essentially rely on the theory of approachability for stochastic
games, and are based on the idea of steering the average reward
vector towards the target set. We then extended the algorithms
to the case of a target set which is not prescribed but rather may
depend on the parameters of the game.
This was done by requiring an order relation between candidate target sets or
by assuming that the set can be learned consistently.
Specifically, we showed that optimal learning policies in
constrained MDPs and constrained games may be learned using the
proposed schemes.
It should be noted that the proposed schemes are in fact algorithmic
frameworks, or {\em meta-algorithms}, in which one can plug-in different
scalar learning algorithms, provided they satisfy the required
convergence properties. All results are developed under the single-state
recurrence assumption (Assumption \ref{ass:stabgames}), with possible relaxations
outlined in Remarks \ref{rem:reachablity} and \ref{rem:norecurrence}.

Several issues call for further study.
{\Red First, the algorithmic framework we presented can undoubtedly
be improved in terms of convergence speed and memory complexity.
For example, a reduction of the number of steering directions used in the MDRL
algorithm is of practical interest for both convergence speed (less things
to learn) and memory requirement (less policies to store in memory).}
In some cases, especially when the requirements embodied by the target set $T$
are not stringent, this number may be quite small compared to the
conservative estimate used above. A possible refinement of the MDRL
algorithm is to eliminate directions that are not
required, perhaps doing so on-line.
Second, specific algorithms may be devised for the special problems of
constrained MDPs and constrained SGs which are simpler and
with improved convergence rates.
Third, the performance criteria considered here were solely based
on the long-term average reward. It should be of practical interest to
extend this framework to an appropriately windowed or discounted criterion,
that gives more emphasis to {\em recent} rewards.
Finally, it should be challenging to apply the proposed framework and
algorithms to realistic learning problems.
An interesting application class is related to communication networks,
with their multiple QoS requirements and averaged performance
criteria.
% implementation of multi-criterion learning for communication (routing) systems
% in the spirit of \cite{Brown01} may be useful.
We note that the
average reward is the criterion of interest is such applications,
and that the high rate of data makes our algorithms particularly useful
\cite[see][]{Brown01}.
Such applications would undoubtedly require further attention to
issues of computational complexity and convergence rates.

\section*{Acknowledgments}
This research was
supported by the fund for the promotion of research at the
Technion.
We are indebted to three anonymous referees for thoughtful remarks
and for significantly improving the presentation of this work.
S.M.~would like to thank Yishay Mansour, Eyal Even-Dar, and Ishai
Menache for helpful discussions.

\appendix
\section{}

In this appendix we discuss a generalization of the CDRL algorithm and prove that
it approaches $T$ rather than the $\eps$ expansion of $T$.
Recall that in the CDRL algorithm (see Figure~\ref{fig:CDRL}) an accuracy
parameter $\eps$ was provided. The algorithm progressed in blocks where
in each block a direction is
fixed for a duration of $N(\eps)$. In this $N(\eps)$ duration the vector-valued
reward is steered towards the target set $T$ using an
 $\eps$-optimal in expectation learning algorithm.
The following algorithm is a modification of the CDRL algorithm
where we slowly take $\eps$ to 0.
As before, we denote by $N(\eps)$ the time
required for the learning algorithm to achieve an $\eps$ optimal reward in expectation
(see Definition \ref{def:epsoptexpect}).

% insert it in figure like manner
\begin{figure}[h]
\begin{center}
\begin{tabular}{|p{14cm}|}
\hline
Input: Target set $T$; $\eps$-optimal learning algorithm with polynomial dependency $N$.\\
\hline 0. Set $\hat{m}_0$ arbitrarily; $i=1$; $n=0$.\\
1. Repeat forever:\\
2. \quad Set $\eps_i=\frac{1}{i}$. \\
3. \quad If $\hat{m}_n \in T$ play arbitrarily for $N(\eps_i)$ steps; $n:=n+N(\eps_i)$. \\
4. \quad Else let $u_i= u_{\hat{m}_n}$.\\
5. \quad Play an $\eps_i$-optimal in expectation learning algorithm with reward
at time $n$\\ \quad \quad\, given by $r_n=u_i \cdot m_n$ and parameter $\eps_i$.
Play the algorithm for $N(\eps_i)$ time\\\quad \quad\, epochs; $n:=n+N(\eps_i)$.\\
6. \quad Set $i=i+1$.\\
\hline
\end{tabular}
\end{center}
\caption{The modified CDRL algorithm.} \label{fig:modCDRL}
\end{figure}

\begin{theorem}
\label{th:modCDRL} Suppose that for every $\eps>0$ there exists an $\eps$-optimal in
expectation algorithm for each projected SG.
Suppose further that $N(\eps)$ has polynomial dependence in $1/\eps$, and assume that
the target set satisfies Equation~\req{eq:B condition}.
Then $T$ is approached using the modified CDRL algorithm.
\end{theorem}
\proof
We note that we cannot use Theorem \ref{thm:BLCKWLLclassic} or any of its extensions from \cite{MS00c} since
a stopping time (in which steering strategies are switched) which is uniformly bounded
is not provided. We therefore use a direct argument.
It suffices to prove that $T^\eta$ is approached for
every $\eta>0$ \citep{MS00c}. Fix $\eta >0$.\\
Let $\tau_0=0$ and define $\tau_i = \tau_{i-1} +N(\eps_i)$ for $i>0$.
Let the polynomial dependence of the execution time of each stage of the algorithm
be denoted by $N(\eps_i) = C i^\ell$.
It follows that $\tau_i = C \sum_{j=1}^i j^\ell = O (i^{\ell+1})$. \\
By the definition of the algorithm either $\hat{m}_{\tau_i} \in T^\eta$ or each algorithm produces
an average reward which is higher
than the value of the projected game (minus $\eps$).
This implies that the expected progress in direction $u_i$ is positive:
\be
\label{eq:negativity}
\frac{\Exp (\sum_{t=\tau_i}^{\tau_{i+1}-1} m_t \,| F_{\tau_i})}{\tau_{i+1}-\tau_i} \cdot u_i \ge \val\Gamma(u_i) - \eps_i \,,
\ee
where $F_t$ is the sigma algebra generated by all observations up to time $t$.
Let $i$ be large enough so that $\eps_i < \eta$.
Let $d_i$ denote the distance from $\hat{m}_{\tau_i}$ to $T^\eta$,
i.e., $d_i=d(\hat{m}_{\tau_i},T^\eta)$.
We begin by showing that $d_i \to 0$ almost surely, and then show that $d(\hat{m}_n,T^\eta) \to 0$
for all $n$.

Consider the square of the distance, $d^2_i$. Let $y_i$ denote the closest point
in $T^\eta$ to $\hat{m}_{\tau_{i}}$, for an illustration see Figure~\ref{fig:appillust}.
Equation~\req{eq:negativity} implies that for $i$ large enough (so that $\eps_i < \eta$),
\be
\label{eq:negativity2}
\Exp \Big(\frac{(\sum_{t=\tau_i}^{\tau_{i+1}-1} m_t \,| F_{\tau_i})}{\tau_{i+1}-\tau_i} - y_i\Big) \cdot u_i \ge 0 .
\ee

\begin{figure}[h]
  \begin{center}
    \psfig{file=app2t2.eps,width=0.7\textwidth}
    \caption{\label{fig:appillust} {\Red Illustration of one step of the algorithm. The closest point in $T$ to
    $\hat{m}_{\tau_i}$ is $y_i$ and similarly the closest point to $\hat{m}_{\tau_{i+1}}$ is $y_{i+1}$.
    Between ``switching times'' the reward obtained by P1 lies on the other side of the hyperplane
    perpendicular to the segment $(y_i,\hat{m}_{\tau_i})$.}
    }
    \end{center}
\end{figure}


It follows that
\bea
\label{eq:appbasic}
\Exp (d ^2_{i+1}|F_{\tau_i}) &  = & \Exp (\|\hat{m}_{\tau_{i+1}}-y_{i+1}\|^2_2 \,| F_{\tau_i})\nonumber\\
& \le & \Exp (\|\hat{m}_{\tau_{i+1}}-y_i\|^2_2 \,| F_{\tau_i})
\nonumber\\
& = &
\Exp (\|\hat{m}_{\tau_{i+1}}-\hat{m}_{\tau_{i}} + \hat{m}_{\tau_{i}} -y_i\|^2_2 \,| F_{\tau_i}) 
 \nonumber\\
& = & \|\hat{m}_{\tau_{i}}-y_i\|^2_2 + \Exp(\|\hat{m}_{\tau_{i+1}}-\hat{m}_{\tau_{i}}\|^2_2 \,| F_{\tau_i}) + \nonumber\\
& & \quad \quad \quad \quad \quad \quad \quad \quad \Exp (2(\hat{m}_{\tau_{i}}-y_i) \cdot (\hat{m}_{\tau_{i+1}}- \hat{m}_{\tau_{i}}) \,| F_{\tau_i}),
\eea
where the last equality is just the result of simple algebraic manipulation.
The first element in Equation~(\ref{eq:appbasic}) is simply $d_i^2$.
To bound the second element in Equation~(\ref{eq:appbasic}) note that
\begin{eqnarray*}
\Big\|\hat{m}_{\tau_{i+1}} - \hat{m}_{\tau_i}\Big\|_2^2
& = & \Big\| \frac{1}{\tau_{i+1}} \sum_{t=\tau_i}^{\tau_{i+1}-1} m_t
+ (\frac{1}{\tau_{i+1}} - \frac{1}{\tau_i}) \sum_{t=0}^{\tau_i-1} m_t \Big\|_2^2 \\
& \le & \frac{C_1}{(i+1)^{2\ell+2}} \Big\|\sum_{t=\tau_i}^{\tau_{i+1}-1} m_t \Big\|_2^2 +
C_2 \Big(\frac{i^{\ell +1} - (i+1)^{\ell +1}}{(i+1)^{\ell+1}i^{\ell+1}} i^{\ell+1}\Big)^2 \Big\|\hat{m}_{\tau_i} \Big\|_2^2 \\
& \le & C_3 \frac{1}{i^2} \Big(\frac{1}{\tau_{i+1} - \tau_i}\Big)^2 \Big\|\sum_{t=\tau_i}^{\tau_{i+1}-1} m_t\Big\|_2^2
 + C_4 \frac{1}{i^2} \Big\| \hat{m}_{\tau_i} \Big\|_2^2,
\end{eqnarray*}
where we used the fact that $\|a+b\|_2^2 \le 2\|a\|_2^2 + 2\|b\|_2^2$ for the first inequality and
$C_1,C_2,C_3,C_4$ are constants independents of $i$.
Taking the expectation conditioned on $F_{\tau_i}$
we can bound $\Exp(\|\hat{m}_{\tau_{i+1}}-\hat{m}_{\tau_{i}}\|_2^2 \,| F_{\tau_i})$ by
$\frac{C}{i^2}$. Note that the second term is deterministic (conditioned
on $F_{\tau_i}$ and vanishes from some point on.

The third element of Equation(\ref{eq:appbasic}) is more tricky. Since
\begin{eqnarray*}
\hat{m}_{\tau_{i+1}}-\hat{m}_{\tau_{i}} & = &
\frac{1}{\tau_{i+1}} \sum_{t=0}^{\tau_{i+1}-1} m_t - \frac{1}{\tau_{i}} \sum_{t=0}^{\tau_{i}-1} m_t \\
& = &
(\frac{1}{\tau_{i+1}} - \frac{1}{\tau_{i}} ) \sum_{t=0}^{\tau_i-1} m_t
+ \frac{1}{\tau_{i+1}} \sum_{t=\tau_i}^{\tau_{i+1}-1} m_t \\
& = & \frac{\tau_i - \tau_{i+1}}{\tau_{i+1}} \hat{m}_{\tau_i} + \frac{1}{\tau_{i+1}}\sum_{t=\tau_i}^{\tau_{i+1}-1} m_t,
\end{eqnarray*}
we have that
\begin{eqnarray*}
(\hat{m}_{\tau_{i}}-y_i)\cdot (\hat{m}_{\tau_{i+1}}-\hat{m}_{\tau_{i}}) & = &
(\hat{m}_{\tau_{i}}-y_i) \cdot (\hat{m}_{\tau_{i+1}}-\frac{\tau_i -\tau_{i+1}}{\tau_{i+1}} y_i+
\frac{\tau_i -\tau_{i+1}}{\tau_{i+1}}y_i- \hat{m}_{\tau_{i}}) \\
& = & (\hat{m}_{\tau_{i}}-y_i) \cdot \Big(\frac{\tau_i - \tau_{i+1}}{\tau_{i+1}} \hat{m}_{\tau_i} -\frac{\tau_i -\tau_{i+1}}{\tau_{i+1}} y_i+
\\ & & \hspace{4cm}
\frac{\tau_i -\tau_{i+1}}{\tau_{i+1}}y_i + \frac{1}{\tau_{i+1}}\sum_{t=\tau_i}^{\tau_{i+1}-1} m_t\Big) \\
& = & \frac{\tau_i - \tau_{i+1}}{\tau_{i+1}} (\hat{m}_{\tau_{i}}-y_i) \cdot (\hat{m}_{\tau_{i}} - y_i) \\
& & + \frac{\tau_i - \tau_{i+1}}{\tau_{i+1}} (\hat{m}_{\tau_{i}}-y_i) \cdot
(\frac{1}{\tau_{i+1}-\tau_i}\sum_{t=\tau_i}^{\tau_{i+1}-1} m_t -y_i).
\end{eqnarray*}
%\frac{(\hat{m}_{\tau_{i}}-y_i,\hat{m}_{\tau_{i+1}}-y_i)}{i+1}+
%\frac{(\hat{m}_{\tau_{i}}-y_i,y_i-\hat{m}_{\tau_{i}})}{i+1} \nonumber
%\eea
Since $\tau_i = C i^{\ell+1}$ the fraction $\frac{\tau_{i+1} - \tau_i}{\tau_{i+1}}= O(1/i)$.
The first term is therefore approximately $- d_i^2 \frac{C}{i}$.
We get the following inequality:
\be
\label{eq:basic condition}
\Exp (d^2_{i+1}|F_{\tau_i})  \le (1-\frac{C'}{i}) d^2_i + \frac{C''}{i^2} + C''' \Exp
\left(2\frac{(\hat{m}_{\tau_{i}}-y_i)\cdot (\sum_{t=\tau_i}^{\tau_{i+1}-1} m_t-y_i)}{i+1} \,\Big| F_{\tau_i}\right) \,,
\ee
where $C'$, $C''$, and $C'''$ are positive constants.
Now according to Equation~\req{eq:negativity2} the last term in
\req{eq:basic condition} is negative in expectation. We therefore have that
$\Exp (d^2_{i+1}|F_{\tau_i})  \le (1-\frac{C_1}{i}) d^2_i + \frac{C_2}{i^2}$.
Using Lemma \ref{le:martingale difference} we have that
$d^2_{i} \to 0$ almost surely.
To conclude the proof one should show that
$d(\hat{m}_n,T^\eta)\to 0$ for all $n$.
Let $i$ denote the maximal $\tau_i$ smaller than
$n$. By the triangle inequality,
$$
d(\hat{m}_n,T^\eta) \le d(\hat{m}_{\tau_i},T^\eta) + \|\hat{m}_{\tau_i} - \hat{m}_n\|_2 \,.
$$
The first term converges to 0 by the above. To bound the second term note that
\begin{eqnarray}
\label{eq:restoft}
\|\hat{m}_{\tau_i} - \hat{m}_n\|_2 & = & \Big\|\frac{1}{n}\sum_{t=0}^{n-1} m_t - \frac{1}{\tau_i} \sum_{t=0}^{\tau_i-1} m_t \Big\|_2 \nonumber\\
 & = & \Big\| \frac{1}{n} \sum_{t=\tau_i}^{n-1} m_t + \frac{\tau_i-n}{n \tau_i} \sum_{t=0}^{\tau_i-1} m_t \Big\|_2 \nonumber\\
 & \le & \frac{1}{n}\Big\|\sum_{t=\tau_i }^{n-1} m_t \Big\|_2 + \frac{n-\tau_i}{n \tau_i} \Big\|\sum_{t=0}^{\tau_i-1} m_t \Big\|_2\nonumber\\
  & = & \frac{n-\tau_i}{n}\frac{1}{n-\tau_i}\Big\|\sum_{t=\tau_i}^{n-1} m_t \Big\|_2 +
  \frac{n-\tau_i}{n} \frac{1}{\tau_i} \Big\|\sum_{t=0}^{\tau_i-1} m_t \Big\|_2 \,,
\end{eqnarray}
where the inequality is due to the triangle inequality.
By our construction of $\tau_i$ it follows that $\lim_{n\to \infty} \frac{n-\tau_i}{n} = 0$.
Since the random vector reward $m_t$ has finite expectation and bounded second moment (uniformly
in $t$, since there are finitely many states and actions)
it follows that $\frac{1}{\tau_i} \|\sum_{t=0}^{\tau_i-1} m_t \|_2$ is asymptotically contained in some ball
of finite radius with probability one.\footnote{To see that, take the centralized version of that random variable which
converges to 0, almost surely by an appropriate version of the strong law of large numbers.
Note that the center may not converge, but is guaranteed to be in some bounded region.}
Consequently, the second term in Equation~\req{eq:restoft} converges to 0 almost surely.
The first term in Equation~\req{eq:restoft} converges to 0 as well by a standard probabilistic argument.\footnote{The result follows by Chebyshev's inequality on the centralized version of
$\sum_{t=\tau_i }^{n-1} m_t$ and the Borel-Cantelli Lemma, noticing that
$\sum_{t=\tau_i }^{n-1} m_t$ is multiplied by a deterministic series that converges to 0.}
\qed

\begin{lemma} \label{le:martingale difference}
Assume $e_t$ is a non-negative random variable, measurable
according to the sigma algebra $F_t$ ($F_t \subset F_{t+1}$) and that
\be
\label{martingale difference eq}
\Exp(e_{t+1}|F_t) \le (1-d_{t})e_{t} + c d_{t}^2.
\ee
Further assume that $\sum_{t=1}^{\infty}d_{t} = \infty$, $d_t \ge 0$,  and that $d_{t}\to 0$.
Then $e_{t}\to 0 $ P-a.s.
\end{lemma}

\proof First note that by taking the expectation of
Equation~\req{martingale difference eq} we get
\[
\Exp e_{t+1} \le (1-d_{t}) \Exp e_{t} + c d_{t}^2.
\]
According to \citet[page 117]{NDP} it follows that $\Exp e_t\to 0$.
Since $e_t$ is non-negative it suffices to show that $e_t$ converges.
Fix $\epsilon > 0$, let
\[
V^{\epsilon}_t \bydef \max\{\epsilon , e_t\}.
\]
Since $d _t \to 0$ there exists $T(\epsilon )$ such that
$c d _t < \epsilon$ for $t>T$. Restrict attention to $t> T(\eps)$.
If $e_t < \epsilon$ then
$$
\Exp(V^{\epsilon}_{t+1}|F_t) \le (1-d_{t}) \epsilon + c d_{t}^2  \le \epsilon \le V^{\epsilon}_t.
$$
If $e_t > \epsilon$ we have
$$
\Exp(V^{\epsilon}_{t+1}|F_t)  \le (1-d_{t})e_t + d_{t} e_t \le   V^{\epsilon}_t .
$$
$V^{\epsilon}_t$ is a super-martingale, by a standard convergence argument
we get $V^{\epsilon}_t \to V^{\epsilon}_\infty$.

By definition  $V^{\epsilon}_t \ge \epsilon $ and therefore $ \Exp V^\eps_t \ge \eps$.
Since $\Exp \left[\max(X,Y)\right] \le \Exp X + \Exp Y$ it follows that $\Exp V^{\epsilon}_t \le \Exp e_t + \eps$.
So that $\Exp V^{\epsilon}_\infty = \eps$.
Now we have a positive random variable, with expectation $\eps$
which is not smaller than $\eps$ with probability 1. It follows that
$V^\eps_\infty = \eps$.

To summarize, we have shown that for every $\eps>0$ with probability 1,
$$
\limsup_{t\to \infty} e_t \le \limsup_{t\to \infty} V^\eps_t = \lim_{t\to \infty} V^\eps_t = \eps \,.
$$
Since $\eps$ is arbitrary and $e_t$ non-negative it follows that $e_t \to 0$ almost surely.
\qed

\bibliography{phd}
%\bibliographystyle{alpha}

\end{document}               % End of document.
