% This is LLNCS.DEM the demonstration file of
% the LaTeX macro package from Springer-Verlag
% for Lecture Notes in Computer Science,
% version 2.3 for LaTeX2e
%
\documentclass{llncs}
%
\usepackage{times}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{amssymb,amsmath}
\usepackage{nopageno}

\usepackage{graphicx} % more modern
%\usepackage{epsfig} % less modern
\usepackage{subfigure}

\hyphenation{Litt-man}

%\newtheorem{theorem}{Theorem}
%\newtheorem{proposition}{Proposition}
%\newtheorem{corollary}{Corollary}
%\newtheorem{definition}{Definition}
%\newtheorem{lemma}{Lemma}

\def\argmax{\mathop{\rm argmax}}
\def\argmin{\mathop{\rm argmin}}
\newcommand{\cala}{\mathcal{A}}
\newcommand{\bolda}{\mathbf{A}}
\newcommand{\bolds}{\mathbf{S}}
\newcommand{\boldc}{\mathbf{C}}
\newcommand{\boldp}{\mathbf{P}}
\newcommand{\bolde}{\mathcal{E}}
\newcommand{\boldpi}{\boldsymbol{\pi}}
\newcommand{\cals}{\mathcal{S}}
\newcommand{\calp}{\mathcal{P}}
\newcommand{\calv}{\mathcal{V}}
\newcommand{\calc}{\mathcal{C}}
\newcommand{\calt}{\mathcal{T}}
\newcommand{\calg}{\mathcal{G}}
\newcommand{\cale}{\mathcal{E}}
\newcommand{\calh}{\mathcal{H}}
\newcommand{\calb}{\mathcal{B}}
\newcommand{\calr}{\mathcal{R}}
\newcommand{\cald}{\mathcal{D}}
\newcommand{\calgbold}{\mathcal{\mathbf{G}}}
\newcommand{\boldalpha}{\mathbf{\alpha}}
\newcommand{\vecs}{\vec{s}}
\newcommand{\veca}{\vec{a}}
\newcommand{\vecb}{\vec{b}}
\newcommand{\veck}{\vec{k}}
\newcommand{\vece}{\vec{e}}
\newcommand{\vecx}{\vec{x}}
\newcommand{\vecz}{\vec{z}}
\newcommand{\vecy}{\vec{y}}
\newcommand{\hatQ}{\hat{Q}}
%\newcommand{\starQ}{\overset{*}{Q}}
%\newcommand{\starpi}{\overset{*}{\pi}}
\newcommand{\starQ}{\accentset{\star}{Q}}
\newcommand{\starpi}{\accentset{\star}{\pi}}
\renewcommand{\vec}{\mathbf}
\renewcommand\arraystretch{1.2}

%
\begin{document}
%
\frontmatter          % for the preliminaries
%
\pagestyle{headings}  % switches on printing of running heads
\addtocmark{Hamiltonian Mechanics} % additional mark in the TOC
%
%
\mainmatter              % start of the contributions
%
\title{Anytime Self-play Learning to Satisfy Functional
Optimality Criteria}
%
\titlerunning{Anytime Self-play Learning}  % abbreviated title (for running head)
%                                     also used for the TOC unless
%                                     \toctitle is used
%
\author{Andriy Burkov \and Brahim Chaib-draa}
%
\authorrunning{Ivar Ekeland and Brahim Chaib-draa}   % abbreviated author list (for running head)
%
%%%% list of authors for the TOC (use if author list has to be modified)
\tocauthor{Ivar Ekeland, Brahim Chaib-draa}
%
\institute{Laval University, Quebec QC , Canada,\\
\email{burkov@damas.ift.ulaval.ca},\\ WWW home page:
\texttt{http://www.damas.ift.ulaval.ca}}

\maketitle              % typeset the title of the contribution

\begin{abstract}
We present an anytime multiagent learning approach to satisfy any
given optimality criterion in repeated game self-play. Our approach
is opposed to classical learning approaches for repeated games:
namely, learning of equilibrium, Pareto-efficient learning, and
their variants. The comparison is given from a practical (or
engineering) standpoint, i.e., from a point of view of a multiagent
system designer whose goal is to maximize the system's overall
performance according to a given optimality criterion. Extensive
experiments in a wide variety of repeated games demonstrate the
efficacy of our approach.
\end{abstract}
%
\section{Introduction}
Until now, the main body of the state-of-the-art multiagent learning
(MAL) research~\cite{bowling-veloso:2002} has been focused on
finding a learning rule possessing specific properties. For example,
when adopted by all agents of a multiagent system (MAS), such rule
could bring to each agent an accumulated reward, ``optimal'' in a
certain sense. I.e., a learning rule were considered to be good if
the rewards accumulated by the agents (also called ``players'') were
close to some values satisfying a certain criterion of
optimality\footnote{As a matter of fact, the terms ``optimal'' and
``optimality'' are not always appropriate in MAS. Indeed, there are
often multiple entities (agents) having different interests in a
MAS. In the classical game theoretical literature such terms as
``Pareto efficiency'' or ``equilibrium'' are used in place of
``optimality''. Nevertheless, we will use these terms to unify and
simplify the presentation.}. Two most widely used optimality
criteria in the context of learning in repeated games are: closeness
of the value accumulated by each player to the value of (a) a Nash
equilibrium and (b) a Pareto-efficient joint strategy (which need
not be an equilibrium).

The scenario where all agents use the same algorithm is called
``self-play''. Most of the existing multiagent learning rules assume
self-play~\cite{claus-boutilier:1998,bowling-veloso:2002,hu-wellman:2003,banerjee2004pbr}.
An important reason for that is because ``self-play'' multiagent
systems (SPMAS) are of a great practical interest. Indeed, given an
algorithm capable of achieving a utility satisfying a given
optimality criterion in self-play, an engineer can create a number
of identical agents (in the case of software agents, one can just
make as many copies of one agent as required) put these agents into
a given environment and let them converge.

However, in an arbitrary repeated game, the values corresponding to
different optimality criteria can vary substantially from one
criterion to another. So, when the game being played is unknown, it
is usually hard to chose the best learning rule. Another problem,
when using algorithms satisfying such optimality criteria as (a) or
(b) listed above, is that, from a practical point of view, neither
of those criteria can be satisfactory for all SPMAS. Let us clarify
this claim.

Let suppose we are an engineer that receives from a client a problem
that needs to be solved by a number of identical agents. (We will
call this problem ``the environment'' and this environment is
supposed to be unknown in terms of players' rewards for different
actions.) The agents (if embodied) are provided by the client, but
we are free to decide about the algorithms used by the agents to
solve the problem. The client expects the good solution to satisfy a
certain quantitative criterion based on the values accumulated by
the agents. For example, this criterion can require that the
solution maximize a given algebraic function of player's accumulated
rewards. In this case, which of the existing MAL algorithms and
their corresponding optimality criteria will we choose?

One solution would be to run each algorithm on the given problem,
observe the results, and pick the best. However, such an approach
can be time and ressource expensive, and does not guarantee
optimality. Another approach is to use a learning algorithm capable
of solving problems in SPMAS in a way to directly satisfy functional
criteria.

%It makes sense to use such criteria in many practical tasks
%involving multiple identical agents working together. For example,
%suppose that our agents are robots that gather soil samples (of
%different volumes and values) on an unknown and distant planet.
%Since the robots have a limited carrying capacity, the client's
%preference could be to distribute samples among robots so as to
%maximize the overall value of samples collected by all robots (i.e.,
%\emph{sum} of the robots' values). On the other hand, if our robots
%are searching for diamonds, the client's preference could be to find
%and deliver the biggest diamond (or a certain set of bigger
%diamonds), probably at the cost of leaving a number of smaller
%diamonds, or even a number of robots, on the planet (i.e.,
%\emph{max} of the robots' values). Finally, the client could want
%the robots to consume the fuel so as to keep all robots capable of
%working together as long as possible. In this case, he can prefer
%the \emph{product} of values (taking into account the consumption of
%fuel) to be maximized\footnote{The product generally permits a more
%uniform distribution of gains (or losses) among multiple
%agents~\cite{nashjr1950bp}.}.

These functional criteria are opposed to such criteria as
(a)~and~(b), which we call ``relational'', meaning that they are
defined by taking into account relations between the values
accumulated by each individual agent. In this case, the absolute
values themselves \emph{are secondary}. For example, a
joint-strategy of multiple players is said to be a Nash equilibrium
(criterion a) if the expected reward of \emph{each player} is
maximized given that \emph{the other players} have their strategies
fixed. In a similar manner, a joint-strategy is said to be
Pareto-efficient (criterion b) if by changing this strategy so as to
increase the expected value of \emph{any subset of players}, there
will necessarily be \emph{a player out of this subset} whose value
decreases. The same reasoning is applicable
%to a Pareto-efficient
%Nash equilibrium and
to a number of other relational optimality criteria (for example,
correlated equilibrium~\cite{greenwald2003cql}).

In this paper, we propose an approach to multiagent learning in
repeated game self-play when the goal is to satisfy a given
functional optimality criterion. We show that in such a setting our
learning algorithm, called \emph{Anytime Self-play Learner}, is (i)
a better choice than a whole family of equilibrium and
Pareto-efficient strategy learning algorithms, and (ii) anytime,
i.e., the quality of solution increases gradually with the number of
repeated game plays; thus the learning process terminated at an
arbitrary moment still results in a reasonably good agents'
behavior.

\section{Formal notions}
For simplicity of exposition, our presentation will be given for
two-player repeated game case. Extensions to an $n$-player setting
(for an arbitrary $n>2$) as well as to the multistate problems are
also possible but omitted due to space limits.
%as well as to the multistate problems are discussed in
%Section \ref{discussions}.

\subsection{Matrix games and their solutions}
A finite repeated two-player general-sum matrix game~$\Gamma$
(henceforth, a repeated game) consists of a set $P$ of two players,
$p$ and $q$, with $(p,q)\in \{(1,2),(2,1)\}$. Player $p$ has a
finite number $M^p \in \mathbb{N}^+$ of actions it can choose from.
The game is played iteratively. At iteration $i=1,2,\ldots$, each
player $p$ chooses an action $a^p_i \leq M^p$ and the vector
$\veca_i = (a^p_i,a^q_i) \in A$ gives a \emph{joint action}. $A$ is
called the joint action space of players. For each player $p$ there
is a $M^p$-by-$M^q$ matrix $R^p$ defining the real-valued reward of
that player after playing a joint action $\veca_i$.

To choose an action from $M^p$ at any iteration, each player uses
its \emph{strategy}. A strategy can be viewed as a function mapping
the player $p$'s current internal states into actions. A player's
strategy can be \emph{stationary} or \emph{non-stationary}. Let
$\pi^p_i$ denote the rule, following to which player $p$ chooses its
action at iteration $i$. Then, $p$'s strategy $\pi^p$ is called
stationary if $\pi^p_i=\pi^p_0$, $\forall i$. This means that $p$'s
strategy does not depend on current iteration, or, in other words,
that it cannot change with time. Otherwise the strategy is called
non-stationary.

A strategy profile $\boldpi = (\pi^p,\pi^q)$ is a joint strategy of
players. To compare strategies and strategy profiles between them
one can assign a metric to a strategy. We are using the expected
limit of the means (ELM) metric. ELM assigns a unique value to an
expected sequence of rewards that is obtained by a player following
a given strategy profile $\boldpi$ in an infinite sequence of
iterations:
\begin{equation}
\label{limitOfTheMeans} u^p(\boldpi) =
E_{\boldpi}\left[\lim_{T\rightarrow\infty}\frac{1}{T}\sum_{i=1}^{T}R^p(\boldpi_i)\right]
\end{equation}
In the above equation, $u^p(\boldpi)$ is the ELM value of strategy
$\boldpi$. $R^p(\boldpi_i)$ denotes the expected immediate reward
obtained by player $p$ at iteration $i$ if both players follow the
strategy~$\boldpi$ at that iteration.

Nash equilibrium is a strategy profile
$\hat{\boldpi}=(\hat{\pi}^p,\hat{\pi}^q)$ such that the following
condition holds:
\begin{equation}
\label{nashConditions}
\begin{split}
u^p(\pi^p,\hat{\pi}^q) \leq u^p(\boldpi) \mbox{ and }
u^q(\hat{\pi}^p,\pi^q) \leq u^q(\boldpi), \forall
\pi^q\neq\hat{\pi}^q, \pi^p\neq\hat{\pi}^p
\end{split}
\end{equation}

%Let $\hat{\Pi}(\Gamma)$ denote the set containing all Nash
%equilibria of the repeated game $\Gamma$. (It is
%known~\cite{nash:1950} that for any $\Gamma$,
%$\hat{\Pi}(\Gamma)\neq\varnothing$). A Pareto-efficient Nash
%equilibrium is a Nash equilibrium
%$\tilde{\boldpi}\in\hat{\Pi}(\Gamma)$ such that $\forall
%\boldpi'\neq\tilde{\boldpi}$, at least one of the following two
%conditions holds:
%\begin{equation}
%\label{nashParetoConditions}
%\begin{split}
%u^p(\boldpi') < u^p(\tilde{\boldpi})\mbox{~~or~~} u^q(\boldpi') <
%u^q(\tilde{\boldpi})
%\end{split}
%\end{equation}

Let $M(\Gamma)$ denote the set of all strategy profiles of
game~$\Gamma$. A Pareto-efficient solution of $\Gamma$ is a strategy
profile $\bar{\boldpi}\in M(\Gamma)$ such that the following
condition holds:
\begin{equation}
\label{paretoConditions}
\begin{split}
u^p(\boldpi') < u^p(\bar{\boldpi}) \mbox{~~or~~} u^q(\boldpi') <
u^q(\bar{\boldpi}), \forall \boldpi'\neq\bar{\boldpi}
\end{split}
\end{equation}

\subsection{Optimality criteria}
The equations (\ref{nashConditions}--\ref{paretoConditions}) define
two relational optimality criteria discussed in the previous
section. And as we claimed above, there are tasks where a use of
relational criteria is not justified from a practical standpoint. In
such environments, we would prefer agents to learn (and to use
thereafter) strategies maximizing some mathematical function of
their utility. This, functional, optimality criterion, depending on
the task, can be based on such functions as \emph{max}, \emph{sum},
\emph{product} or any other desirable function of players'
individual utilities. If the utility is defined using the ELM metric
then the functional optimality criterion $u(\boldpi)$ for a strategy
profile $\boldpi$ can be defined as
$u(\boldpi)=\mbox{Op}_p(u^p(\boldpi))$, where $u^p(\boldpi)$ is the
utility of player $p$ defined using
equation~(\ref{limitOfTheMeans}). In the latter equation,
$\mbox{Op}$ denotes a certain mathematical operator. For a given
problem, it needs to be replaced by $\max$, $\sum$, $\times$ or any
required function.
%Notice that in the above equation, $u(\boldpi)$ does not have index
%$p$ and, thus, functional optimality criteria can be viewed as
%characterizing a \emph{global} utility of a MAS.

%We should mention here that we are not the first to focus on
%functional optimality criteria. This principle was used by
%Nash~\cite{nashjr1950bp} in his axiomatic analysis of bargaining,
%where he proposed to choose the solution point maximizing the
%product of individual values of players. From the computer science
%perspective, Littman~\cite{littman2005ptn} adapted Nash's idea to
%choose the best solution point in their algorithm computing Nash
%equilibrium in repeated games. For our part, we extend these ideas
%to the \emph{learning} in self-play. Another related work is
%discussed in Section~\ref{sec:related}.

\subsection{Self-play}
We \emph{explicitly} focus on the self-play setting; and this is a
\emph{controlled} self-play, not an accidental coincidence of
learning algorithms of agents. The latter property differs our
approach from the main body of modern multiagent learning research
proposing algorithms whose \emph{behavior is justified for} (or
\emph{examined in}) self-play. Recall that by definition, self-play
is a MAS setting in which \emph{all} agents are \emph{identical}.
Until now, it has been typically assumed that agents'
\emph{algorithms}, or, in other words, rules of strategy update when
learning, are identical. Other properties that can also be
identical, such as (i)~{initial knowledge} of agents, (ii)~their
utility metrics and (iii)~optimality criteria, have escaped the
attention of researchers. In this paper, we aim to fill this gap.

More precisely, in our controlled self-play scenario, which we call
CSPMAS, we assume that both players, (1) \emph{use the same learning
algorithm}, (2) \emph{have internal variables initialized with the
values known to both players}, (3) \emph{use the same utility
metric} and (4) \emph{optimize the same functional criterion}. We
claim that in any \emph{controlled} self-play scenario, Assumptions
2--4 are as well natural as Assumption 1, which is made in many
previous multiagent learning
papers~\cite{claus-boutilier:1998,bowling-veloso:2002,hu-wellman:2003,greenwald2003cql,banerjee2004pbr}.
In particular, this means that in any SPMAS,
\begin{center}
Assumption (1) can intentionally be satisfied $\Longleftrightarrow$
Assumptions (2--4) can intentionally be satisfied.
\end{center}

Also, we assume that players can observe each other's actions and
their own rewards after a joint action is executed. This is as well
a common assumption for many of MAL
algorithms~\cite{claus-boutilier:1998,hu-wellman:2003,banerjee2004pbr,crandall2005lcc}.
To stay as much general as possible, in our approach we assume that
the reward observed by an agent $p$, $\forall (p,q)\in
\{(1,2),(2,1)\}$, at iteration $i$ after playing a joint action
$\veca_i$, is not necessarily deterministic. We only suppose that
$\forall\veca\in A$, the reward $R_i^p(\veca)$ observed after
playing a joint action $\veca$ is an instantiation of a random
variable with certain mean and variance that do not change with
time.

\subsection{Information and communication}
%Two important aspects of any MAS is (i) what is known by the agents
%about the environment and (ii) whether the agents can share the
%information acquired during learning. When the model of a MAS is a
%repeated game, the first aspect transforms into a question whether
%the agents know their own reward function and the reward function of
%the other agent. The second aspect, in turn, can be viewed as a
%question whether communication between agents is available.

Two important questions characterizing any MAS are (i)~whether the
agents know their own reward function and the reward function of the
other agent, and (ii)~whether communication between agents is
available during learning. In this paper, we assume that the answer
to both questions is \emph{No}. Indeed, an affirmative answer to the
first question makes the learning unnecessary, since the agents can
compute an optimal joint strategy using the reward matrices.
%(For
%example, this can be done in a manner described in the paper
%of~\cite{littman2005ptn}.)
Accordingly, if the agents can communicate, the simplest scenario is
to explore the reward structure of the game by executing joint
actions one by one. Then, using communication, agents are able to
share the acquired data.
%Finally,
%agents can to compute the optimal joint strategy just like in the
%previous case, i.e., when the reward functions of both agents are
%known.
This, again, will make a further learning unnecessary.

\section{Extended strategies} \label{subsec:extended-strategies}
To present our new algorithm, we first need to discuss one important
implication of using the product criterion: emerging of strategies
extended in time, or simply ``extended strategies''. These
non-stationary strategies are known to be able to maximize the
product of players' individual utilities to a greater extent than
any stationary strategy~\cite{littman2005ptn}. As we will
demonstrate later, our Anytime Self-play Learner algorithm is able
to learn and execute extended strategies.

When two players $p$ and $q$ play a joint action $\veca=(a^p,a^q)$
their rewards can be visualized as a point
$\vecx=(x^p,x^q)=(R^p(a^p,a^q),R^q(a^p,a^q))$ in a two-dimensional
space.\footnote{In this subsection, we use a simplified notation
introduced by Littman~\cite{littman2005ptn}. According to it, $\vecx
= (x^p,x^q)$ and $\vecy = (y^p,y^q)$ denote the vectors of players'
rewards for two different joint actions viewed as points in a
two-dimensional space.} Let the set $X$ contain all such points: $X
= \{(R^p(a^p,a^q),R^q(a^p,a^q)): a^p\leq M^p, a^q\leq M^q)\}$.
Players can achieve any point in $X$ as their ELM values by playing
the corresponding joint action at every iteration. The convex hull
of the set $X$ contains all points that can be obtained as a linear
combination of a subset of points of $X$. It is easily observable
that the points laying on the boundary of the convex hull are always
constructed as a linear combination of only two points of $X$. In
terms of players' strategies, a point $\vecz$ on the boundary
(recall that a point in $X$ is a vector of players' ELM values) can
be achieved by the players by playing a joint action, corresponding
to a certain point $\vecx$, a $w$-fraction of all iterations, and by
playing another joint action, corresponding to a point $\vecy$, the
$(1-w)$-fraction of all iterations (where $w$, $0 \leq w \leq 1$,
defines the coefficient of linear combination).

\begin{definition}
\label{EJA} Given $l\in\mathbb{N}^+$, $0 \leq w \leq 1$, $\veca \in
A$ and $\vecb \in A$, an Extended Joint Action (EJA) is a joint
strategy in which players play $\veca$ during the first $k=\lceil l
\cdot w \rceil$ iterations and $\vecb$ during the following $l - k$
iterations.
\end{definition}
\begin{definition}
\label{EJS} An Extended Joint Strategy (EJS) is an EJA repeated
infinitely often.
\end{definition}
We call $l$ the \emph{length} of an EJA and $k$ its \emph{switch
point}. Notice that for each $\vecz$ obtained as a combination of
two points $\vecx$ and $\vecy$ from $X$, $\exists$ an EJS with
certain $\veca$, $\vecb$, $l$ and $w$.

When the product criterion is used, the boundary of the convex hull
is of a particular interest because the point $\vecz$ maximizing
this criterion is always found on the boundary~\cite{nashjr1950bp}.
For two given points of $X$, $\vecx=(x^p,x^q)$ and
$\vecy=(y^p,y^q)$, forming an edge of the boundary, the value of $w$
maximizing the product criterion on this edge can be computed as
follows~\cite{littman2005ptn},
\begin{equation}
\label{w}%
w = \frac{-y^q(x^p-y^p)-y^p(x^q-y^q)}{2(x^q-y^q)(x^p-y^p)}
\end{equation}
If $w<0$ or $w>1$, the maximum is achieved at respectively $\vecx$
or $\vecy$. To find $w^*$ maximizing the product criterion, it is
only required go over all pairs of points of $X$, compute $w$ using
Equation (\ref{w}) and then pick a pair $\vecx^*$ and $\vecy^*$ of
points for which $w$ is maximized.

As one can note, an EJS will achieve the optimal ELM value defined
by $w^*$, $\vecx^*$ and $\vecy^*$ only when $l\rightarrow\infty$.
Let us show that as $l\rightarrow\infty$ the error induced by using
a finite value of $l$ rapidly decreases.
\begin{proposition}
\label{theorem-about-l}%
Let $R$ denote the ELM value of an optimal point $\vecz$ on the
boundary of $X$ defined by the values $w^*$, $\vecx^*$ and $\vecy^*$
found as described above. Let $l$ be the length of an EJA defined
for two joint actions $\veca$ and $\vecb$ from $A$ corresponding to
the points $\vecx^*$ and $\vecy^*$ from $X$. Let $\tilde{R}$ denote
the ELM of this EJA. Let $\epsilon=\tilde{R}-R$ define the error of
using $l<\infty$ in this EJA. Then $\epsilon \rightarrow 0$ as $l
\rightarrow \infty$.
\end{proposition}
\begin{proof}
%Available in the extended version.
We have $l^2R=(lwx^p+(l-lw)y^p)(lwx^q+(l-lw)y^q)$ and
$l^2\tilde{R}=(\lceil lw \rceil x^p+(l-\lceil lw \rceil)y^p)(\lceil
lw \rceil x^q + (l-\lceil lw \rceil)y^q)$. We know that for any
natural $x$, $\lceil x \rceil < x + 1$. Thus, we can write that
$l^2\tilde{R}<((lw+1) x^p+(l-(lw+1))y^p)((lw+1) x^q +
(l-(lw+1))y^q)$. The difference between $l^2\tilde{R}$ and $l^2R$ is
then bounded as follows:
$l^2\tilde{R}-l^2R<l(x^p-y^p)(x^q-y^q)(2w-1)+2x^px^q-x^py^q-y^px^q$.
Since $l>1$, the error $\epsilon=\tilde{R}-R$ is bounded as follows:
$\epsilon<\frac{(x^p-y^p)(x^q-y^q)(2w-1)}{l}+\frac{2x^px^q-x^py^q-y^px^q}{l^2}$.

Therefore, as $l$ tends to $\infty$, $\epsilon$ tends to $0$ with a
rate inversely proportional to $l$.
\end{proof}

When $l$ and $w^*$ are known to the players (i.e., defined by the
designer of the MAS before to start learning) they are able to
construct the EJS maximizing, to the extent of the error induced by
using a finite value of $l$, the product criterion.

\section{Anytime Self-play Learner}
In this section, we present our new algorithm called Anytime
Self-play Learner (ASPL). Its main steps are given in
Algorithm~\ref{alg:AJSL-steps}.
\begin{algorithm}[!htb]%
\caption{Main steps of Anytime Self-play Learner.\label{alg:AJSL-steps}}{%
\small
\begin{enumerate}
\setlength{\itemsep}{-\parsep}
  \item While exploring
    \begin{enumerate}
    \setlength{\itemsep}{-\parsep}
      \item Play an exploration action,
      \item Observe the reward $R$,
      \item Replay the same action proportionally to $R$,
      \item Update counters of the other player's play.
    \end{enumerate}
  \item While exploiting
    \begin{enumerate}
    \setlength{\itemsep}{-\parsep}
      \item Optimize according to the criterion and counters,
      \item Play optimally.
    \end{enumerate}
\end{enumerate}
\normalsize
}%
\end{algorithm}%.
%The main purpose of this algorithm is to
%learn in SPMAS a strategy profile whose ELM value is close to the
%optimal one according to any given functional optimality criterion.

\subsection{Internal variables}
Our algorithm has one internal variable that needs to be initialized
to all agents with the same value before the learning is started.
This variable, called $R_{max}$, reflects the maximum utility that
an agent can obtain in the game. In many practical tasks, this value
can be set by the designer depending on how the utility is defined.
E.g., for floor cleaning robots this value can be set based on the
maximum possible surface one robot can clean given the initial
volume of detergent in its tank.
%Or, for robot
%gathering soil samples, $R_{max}$ can be based on the maximum
%carrying capacity of one robot.
It is assumed that $R_{max}\geq R^p(a^p,a^q)$ for any player $p$ and
for all $a^p \leq M^p$ and $a^q \leq M^q$. I.e., $R_{max}$ does not
underestimate any of the rewards of players.

During learning, an ASPL agent $p$ also maintains several other
variables. The variables $K^p(a^p,a^q)$, $\forall a^p\leq M^p,
a^q\leq M^q$, reflect the number of times a particular joint action
$(a^p,a^q)$ has been played. The variables $L^p(a^p,a^q)$, $\forall
a^p\leq M^p, a^q\leq M^q$, reflect the number of times that the
action $a^q$ has been played by $q$ at the iteration $i+1$ following
an iteration $i$ at which players were playing $(a^p,a^q)$.

\subsection{Exploring} To exhibit a good joint behavior,
players obviously need to explore the game they play. More
specifically, an agent not only needs to learn its own rewards for
joint actions, which, as we noticed, can be an instantiation of an
unknown random variable. Also, in order to optimize the functional
criterion, it needs to have ``an idea'' of the reward function of
the other agent.
%(Recall that we assume that only
%own rewards can be observed by a player, and there is no
%communication between players.)

For this purpose, the algorithm proceeds as follows. Both ASPL
players are explicitly synchronized (this is an advantage of
self-play). At each odd iteration~$i$, an ASPL player $p$ randomly
uniformly plays an action $a^p_{i}$, and observes its own reward
$R^p_{i}$ and the action $a^{q}_{i}$ played by the other player.
Then it updates its estimate $\tilde{R}^p(\veca_i)$ of the reward
$R^p(\veca_i)$ for the joint
action $\veca_i=(a^p_i,a^q_i)$ as follows:%
\begin{equation}
\label{eq:my-reward-update}
\tilde{R}^p(\veca_i)=\tilde{R}^p(\veca_i)+\frac{1}{k_{\veca_i}+1}\left(R^p_{i}-\tilde{R}^p(\veca_i)\right)
\end{equation}
\noindent where $k_{\veca_i}$ represents the number of times the
joint action $\veca_i$ has been played so far. Finally, player $p$
increments its counter~$K^p(\veca_i)$.

At the next iteration,~$i+1$, player $p$ replays the action
$a^p_{i}$ with probability $\delta=R^p_{i}/R_{max}$. Otherwise, with
probability $(1-\delta)$ player $p$ plays a random action different
from $a^{p}_{i}$ and picked uniformly from the remaining actions.
Player $p$ then observes the action played by player $q$, updates
again its reward estimate for the played joint action using Equation
(\ref{eq:my-reward-update}), and, finally, updates its counter
$L^p(\cdot)$ accordingly.

\subsection{Exploiting} As soon as when exploring both players
follow the same procedure, therefore, at any moment of time, player
$p$ can assume for any joint action $(a^p,a^q)\in A$ that
$\frac{L^p(a^p,a^q)}{K^p(a^p,a^q)}$ is an unbiased estimator of the
unknown reward function of player $q$. More precisely, it can
believe that,
$$
\frac{R^q(a^p,a^q)}{R_{max}} \approx
\frac{L^p(a^p,a^q)}{K^p(a^p,a^q)}
$$
Indeed, since the value $R_{max}$ is the same and is known to both
players, and as the players replayed their action $a^p_i$, played on
the previous iteration $i$, according to the proportion
$R^p(a^p_i,a^q_i)/R_{max}$, the values of counters $L^p(a^p,a^q)$
and $K^p(a^p,a^q)$ can give to player $p$ a good estimate of the
real value of $R^q(a^p,a^q)$. More precisely, player $p$ can compute
an estimate of the other player rewards as follows,
\begin{equation}
\label{reward-estimate}%
\tilde{R}^q(a^p,a^q)=\frac{L^p(a^p,a^q)R_{max}}{K^p(a^p,a^q)}
\end{equation}
By so doing, it becomes possible to compute the strategy maximizing
any given functional criterion and to execute this strategy
thereafter. For example, if the functional criterion is $sum$, the
optimal strategy can be computed by the players as, \small
\begin{equation}
\label{leader-sum}%
\pi^p_i = \argmax_{a^p:(a^p,a^q)\in
A}\left(\tilde{R}^q(a^p,a^q)+\tilde{R}^p(a^p,a^q)\right)\ \forall i
\end{equation}
\normalsize
%If the functional criterion is $max$, the optimal
%strategy can be computed similarly.
Similarly, if the functional criterion is $max$, the optimal
strategy can be computed as, \small
\begin{equation}
\label{leader-max}%
\pi^p_i = \argmax_{a^p:(a^p,a^q)\in
A}\left(\max(\tilde{R}^q(a^p,a^q),\tilde{R}^p(a^p,a^q))\right)\
\forall i
\end{equation}
\normalsize Finally, if the functional criterion is $product$, the
optimal strategy can be computed as shown in
Algorithm~\ref{leader-product}.
\begin{algorithm}[!htb]%
\caption{Procedure to find the optimal strategy for the $product$ criterion.\label{leader-product}}{%
\small
\begin{enumerate}
  \setlength{\itemsep}{-\parsep}
  \item For all pairs of points $\vecx$, $\vecy$ from the set $X$, such
  that,
$\vecx=(\tilde{R}^p(a^p,a^q),\tilde{R}^q(a^p,a^q))$ and
$\vecy=(\tilde{R}^p(b^p,b^q),\tilde{R}^q(b^p,b^q))$ (where $a^p, b^p
\leq M^p$ and $a^q, b^q \leq M^q$) compute $w$ using
Equation~(\ref{w}) and construct the corresponding EJS using
Definitions \ref{EJA}--\ref{EJS}.
  \item Pick the EJS having the highest ELM value (according to the
  $product$ functional optimality criterion).
\end{enumerate}
\normalsize
}%
\end{algorithm}%.
\section{Explore, exploit and coordinate} As one could remark, ASPL can be viewed as an
anytime algorithm. This means that every two iterations the agents
improve their estimates of the reward functions. If the learning
(exploring) is stopped after a certain iteration, the players are
able to choose the best strategy as yet and to play on it.
%As we will
%see in the next section, in many games, after only a relatively
%small number of learning iterations, both players can use
%Equations~(\ref{leader-sum}-\ref{leader-max}) or the procedure of
%Algorithm~\ref{leader-product} to construct an optimal joint
%strategy.
However, in a general case two important issues need to be resolved
in order to assure a good joint performance. These can be formulated
as two questions: (1) when to stop exploring and start exploiting
(known as the exploration-exploitation
dilemma~\cite{sutton-barto:1998}) and (2) how to choose a
coordinated joint strategy (i.e., the coordination
problem~\cite{claus-boutilier:1998}).

While the exploration-exploitation dilemma is a well-known problem
in machine learning, several words need to be said about the
coordination problem in MAS. Let suppose we have a game as follows,
$$
R^{1,2}=\left(
          \begin{array}{cc}
            1,2 & 0,0 \\
            0,0 & 2,1 \\
          \end{array}
        \right)
$$
After a certain number of exploration iterations, players have
certain estimates of their reward functions. Two points, $(1,2)$ and
$(2,1)$, in $X$ have the same ELM value. However, as the number of
exploration iterations is always finite, the players have an error
in estimates of their own and each other's rewards. Therefore, the
strategies computed by the players independently can belong to
different joint strategies. For example, player $1$ can decide that
the optimal strategy is to play the row $1$, expecting to see the
outcome $(1,2)$, but player $2$ will play the column $2$ foreseeing
the outcome $(2,1)$. As the result, they will collect the suboptimal
outcome $(0,0)$.

In practice, the designer of CSPMAS can sufficiently know the
environment in order to be able to apply the
``explore-then-exploit'' principle~\cite{defarias2005eet}. More
precisely, this means to separate the learning process into two
phases (exploration and exploitation) and to fix the length of the
exploration phase before the learning starts. For example, the room
to clean by two robots can be the same, but the positions of chairs
and tables can change. In this case, the designer can know that the
agents need to continuously explore during the first $T$ time steps,
and then they can synchronously switch to exploit. The coordination
problem can also be easily solved then. For instance, one agent can
be assigned to play the role of \emph{leader}, i.e., to choose the
best joint strategy. The second agent, in turn, will act as
\emph{follower}, i.e., it will observe the strategy followed by the
leader at the previous iteration and adapt to it. Such roles can be
assigned at random since the ELM value of a joint strategy does not
depend on a particular choice of leader and follower.

\subsection{Mixed exploring and exploiting}
On the other hand, if the designer is not able to fix in advance the
length of the exploration phase, he can prefer to mix exploration
and exploitation in a certain way, and let agents ``decide'' online.
One technique to do this involves using a GLIE (for ``greedy in the
limit with infinite exploration'') learning strategy. An example of
such a strategy is Boltzmann exploration strategy:
$$
\pi^p_i(a^p)=\frac{e^{\beta_i Q_i(a^p)}}{\sum_{b^p\leq
M^p}e^{\beta_i Q_i(a^p)}}
$$
\noindent where $\pi^p_i(a^p)$ denotes the probability with which
player $p$ chooses to play the action $a^p$ at each odd iteration
$i$, $\beta_i$ is an exploration factor slowly increasing with time
(Singh et al.~\cite{singh2000crs} show how it can be defined in
order to assure convergence in the limit). $Q_i$ can be viewed as a
certain current preference of agent $p$ over its actions. In our
experiments, to solve the coordination problem, we compute
$Q_i(a^p)$ at each odd iteration using a heuristic called Combined
Optimistic Boltzmann (COB) proposed by Claus and
Boutilier~\cite{claus-boutilier:1998}. It consists of assigning
higher values to the ``promising'' strategies weighed by the
likelihood to be simultaneously chosen by the other player. As the
exploration decreases (with the increasing factor $\beta$) this
heuristics permits the agents to effectively coordinate on the same
joint strategy and to play on it most of the time. Notice that there
exist more efficient methods (in terms of exploration time and cost)
to mix exploration and exploitation, such as a Bayesian
approach~\cite{chalkiadakis-boutilier:2003}.

\section{Experimental results}
It is only fair to compare a new algorithm with the existing ones if
it uses the same or relaxed assumptions and is searching for the
same kind of solution. In our case, there is no other algorithm
capable of learning strategies optimizing functional criteria in MAS
(two exceptions and their limitations are discussed in
Section~\ref{sec:related}). On the other hand, there exist a number
of MAL algorithms, as those cited above, which, while using
different assumptions, converge to the same kinds of relational
solutions like Pareto-efficient or Nash equilibrium. So, in our case
we will indirectly compare our algorithm with all these algorithms
by comparing the ELM value of the solution found by ASPL with the
corresponding values (according to the same criterion) of different
relational solutions. The goal of this comparison is to demonstrate
that when the goal of the designer is to satisfy a given functional
optimality criterion, ASPL is the best choice.

We empirically tested ASPL on two different testbeds. The first
series of testbeds, called ``Random Games M'' (or, RGs M, for
short), contains randomly generated two-player repeated games with
the number of player actions, $M=M^p=M^q$, equal respectively to
$2$, $3$, $5$ and $10$. In each game from Random Games M, the
rewards of players are integer values uniformly distributed between
$0$ and $100$, and new values are generated each time a game is
started.

The second testbed, called ``Conflict Games'' (CGs), contains $57$
games listed by Brams~\cite{brams1993tm}. These are two-player
two-action repeated games whose rewards are integer values between
$1$ and $4$. These games were called ``conflict'' because contain no
outcome that simultaneously maximizes the ELM value of both players.
%\footnote{We also programmed a testbed contained $12$
%two-player games widely explored in both game theoretical and CS
%learning context. Among them, there were such games as ``Battle of
%the Sexes'',``Chicken'', ``Matching Pennies'', ``Prisoner's
%Dilemma'', ``Rock, Paper, Scissors'', and others. We do not present
%these games and the obtained positive results due to a limited
%space.}.
Conflict Games are especially suitable to make a comparison
of solutions computed by ASPL for different functional criteria with
other possible solutions usually found by other MAL algorithms in
self-play (e.g., Nash equilibrium and Pareto-efficient solution).

%for Both Conflict and Main
%Stream Games are especially suitable
%to make a comparison of solutions computed by ASPL for different
%functional criteria with other possible solutions usually found by
%other MAL algorithms in self-play (e.g., Nash equilibrium and
%Pareto-efficient solution).
%\begin{table}[!ht]
%\caption{Main Stream Games.} % title of Table
%\centering % used for centering table
%\resizebox{\columnwidth}{!}{\begin{tabular}{c c c}
%  \hline\hline
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%  Pure Coordination Game (PCG) & Battle of the Sexes (BoS)\\
%  $R^{1,2}=\left(
%          \begin{array}{cc}
%            4,4 & 0,0 \\
%            0,0 & 2,2 \\
%          \end{array}
%        \right)$ &
%$R^{1,2}=\left(
%          \begin{array}{cc}
%            3,2 & 1,1 \\
%            0,2 & 0,3 \\
%          \end{array}
%        \right)$\\
%  Minimum Effort Game (MEG) & Stag Hunt (SH)\\
%$R^{1,2}=\left(
%          \begin{array}{cc}
%            2,2 & 2,0 \\
%            0,2 & 4,4 \\
%          \end{array}
%        \right)$ &
%$R^{1,2}=\left(
%          \begin{array}{cc}
%            4,4 & 0,3 \\
%            3,0 & 3,3 \\
%          \end{array}
%        \right)$\\
%  Shapley's Game (SG) & Chicken (CG)\\
%$R^{1,2}=\left(
%          \begin{array}{ccc}
%            0,0 & 2,0 & 0,2 \\
%            0,2 & 0,0 & 2,0 \\
%            2,0 & 0,2 & 0,0 \\
%          \end{array}
%        \right)$ &
%$R^{1,2}=\left(
%          \begin{array}{cc}
%            0,0 & 4,1 \\
%            1,4 & 3,3 \\
%          \end{array}
%        \right)$ \\
%  Rock, Paper, Scissors (RPS) & Prisoner's Dilemma (PD)\\
%$R^{1,2}=\left(
%          \begin{array}{ccc}
%            1,1 & 2,0 & 0,2 \\
%            0,2 & 1,1 & 2,0 \\
%            2,0 & 0,2 & 1,1 \\
%          \end{array}
%        \right)$ &
%$R^{1,2}=\left(
%          \begin{array}{cc}
%            3,3 & 0,5 \\
%            5,0 & 2,2 \\
%          \end{array}
%        \right)$ \\
%  Grab the Dollar (GD) & Matching Pennies (MP)\\
%$R^{1,2}=\left(
%          \begin{array}{cc}
%            1,1 & 4,3 \\
%            3,4 & 1,1 \\
%          \end{array}
%        \right)$ &
%$R^{1,2}=\left(
%          \begin{array}{cc}
%            2,0 & 0,2 \\
%            0,2 & 2,0 \\
%          \end{array}
%        \right)$ \\
%  Traveler's Dilemma (TD) & Majority Voting (MV)\\
%$R^{1,2}=\left(
%          \begin{array}{cc}
%            0,0 & 4,0 \\
%            0,4 & 4,4 \\
%          \end{array}
%        \right)$ &
%$R^{1,2}=\left(
%          \begin{array}{cc}
%            0,1 & 0,1 \\
%            0,1 & 4,3 \\
%          \end{array}
%        \right)$ \\
%  \hline
%\end{tabular}}
%\label{table:games}
%\renewcommand\arraystretch{1.0}
%\end{table}

We conducted our experiments in the following way. From each
testbed, a game was randomly picked and played during $100,000$
iterations. This process (called an \emph{experiment}) was repeated
$100$ times and then the obtained data were averaged. Table
\ref{table:averages} presents the ELM values of the strategies to
which ASPL players converge in different games. The alternative
values are respectively (APE column) the average utility (in terms
of the corresponding ELM value) of all pure stationary
Pareto-efficient solutions and (ANE column) the average utility of
all stationary Nash equilibria found by the Lemke-Howson algorithm.
%(The tables only contain data for
%games in which the ELM value achieved by ASPL is different from the
%values of other solutions.)
We did not compare the ASPL's solution with non-stationary
Pareto-efficient solutions because there are no algorithms whose
convergence to such kind of solution was proved in a non-special
case (one exception is discussed in Section~ \ref{sec:related}).
\begin{table*}[!htb]
\renewcommand\arraystretch{1.1}
\caption{Utility of ASPL for different function optimality criteria
compared to the utilities of other solutions.
% (according to the same functional criteria)
} % title of Table
\centering % used for centering table
\resizebox{.31\textwidth}{40pt}{
\begin{tabular}{l r@{.}l r@{.}l r@{.}l}
  \multicolumn{7}{c}{$max$}\\
  \hline\hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
   & \multicolumn{2}{c}{\textbf{ASPL}~} & \multicolumn{2}{c}{\textbf{APE}~} & \multicolumn{2}{c}{\textbf{ANE}}\\
  \hline
  CGs~~~~~~~~~~~~~& $\mathbf{4}$&$\mathbf{00}$ & ~~$3$&$62$ & ~~$3$&$44$\\
  \hline
  RGs 2 & $\mathbf{88}$&$\mathbf{71}$ & $82$&$11$ & $80$&$02$\\
  RGs 3 & $\mathbf{94}$&$\mathbf{68}$ & $88$&$85$ & $84$&$19$\\
  RGs 5 & $\mathbf{98}$&$\mathbf{18}$ & $94$&$29$ & $87$&$83$\\
  RGs 10 & $\mathbf{99}$&$\mathbf{46}$ & $96$&$60$ & $92$&$68$\\
  \hline
\end{tabular}
} \resizebox{.33\textwidth}{40pt}{
\begin{tabular}{l r@{.}l r@{.}l r@{.}l}
  \multicolumn{7}{c}{$sum$}\\
  \hline\hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
   & \multicolumn{2}{c}{\textbf{ASPL}} & \multicolumn{2}{c}{\textbf{APE}} & \multicolumn{2}{c}{\textbf{ANE}}\\
  \hline
  CGs~~~~~~~~~~~& $\mathbf{6}$&$\mathbf{41}$ & ~~$6$&$29$ & ~~$6$&$02$\\
  \hline
  RGs 2 & $\mathbf{140}$&$\mathbf{73}$ & $126$&$88$ & $128$&$10$\\
  RGs 3 & $\mathbf{161}$&$\mathbf{14}$ & $151$&$02$ & $150$&$34$\\
  RGs 5 & $\mathbf{174}$&$\mathbf{05}$ & $162$&$14$ & $157$&$98$\\
  RGs 10 & $\mathbf{187}$&$\mathbf{15}$ & $182$&$09$ & $175$&$93$\\
  \hline
\end{tabular}
} \resizebox{.34\textwidth}{40pt}{
\begin{tabular}{l r@{.}l r@{.}l r@{.}l}
  \multicolumn{7}{c}{$product$}\\
  \hline\hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
   & \multicolumn{2}{c}{\textbf{ASPL}} & \multicolumn{2}{c}{\textbf{APE}} & \multicolumn{2}{c}{\textbf{ANE}}\\
  \hline
  CGs & $\mathbf{10}$&$\mathbf{36}$ & ~~$8$&$29$ & ~~$9$&$09$\\
  \hline
  CGs 2 & $\mathbf{5179}$&$\mathbf{85}$ & $4512$&$07$ & $4537$&$66$\\
  CGs 3 & $\mathbf{6555}$&$\mathbf{84}$ & $4190$&$74$ & $4672$&$07$\\
  CGs 5 & $\mathbf{7715}$&$\mathbf{53}$ & $5432$&$45$ & $5652$&$87$\\
  CGs 10 & $\mathbf{8745}$&$\mathbf{05}$ & $6466$&$64$ & $6305$&$67$\\
  \hline
\end{tabular}
} \label{table:averages}
\renewcommand\arraystretch{1.0}
\end{table*}
As one can see, in both testbeds the solution found by ASPL
outperforms all other solutions of those games.
%In the remaining games, it is not worse than the
%Pareto-efficient solution but is better than a Nash equilibrium.
The advantage of ASPL is especially pronounced if the functional
optimality criterion is $product$. In this case, ASPL often
converges to an extended strategy, which is typically more effective
in optimizing this criterion.

The curves of Figures \ref{fig:dynamics} (a and b) reflect the
evolution of the ELM value during learning in games from Random
Games M. For each learning iteration, the curves present the current
ELM value\footnote{These values were averaged over $100$
experiments.} according to the $sum$ and $product$ functional
criteria (the curves for $max$ look similar and were omitted due to
the space limits). We can observe that for each functional
optimality criterion, the ELM value of ASPL becomes close to the
optimal one after a reasonably small number of learning iterations.
%More precisely, Table
%\ref{table:5percent} presents the smallest iteration numbers, after
%which the ELM value of ASPL becomes $5\%$-close to the optimal value.
%Here, we call \emph{optimal} the value to which the algorithm
%converges after $100,000$ iterations.
%
%Notice that ASPL is an any-time algorithm. This means that the
%learning process can be stopped after any predefined number of
%iterations. Then, the current best strategy of players can be
%executed. The value of this strategy, as we have just seen, becomes
%close to the optimal one after only a small number of learning
%iterations.

Both ``explore-then-exploit'' and ``mixed exploring-exploiting''
strategies of exploration/coordination performed well in our
experiments. The only concern about the latter strategy is that GLIE
principle guarantees the convergence to an optimal behavior only in
the limit. Further, since COB is a heuristic, in a relatively small
number of runs agents could coordinate on a suboptimal strategy.
However, we observed that even in such rare cases, agents still
chose a joint strategy ``close'' to an optimal one and never the
worst one.

\begin{figure}[!tb]
  \begin{minipage}[t]{.5\textwidth}
    \begin{center}
      \includegraphics[scale=0.6]{graphs/SumRandom}
    \end{center}
  \end{minipage}
  \begin{minipage}[t]{.5\textwidth}
    \begin{center}
      \includegraphics[scale=0.6]{graphs/ProductRandom}
    \end{center}
  \end{minipage}
    \caption{The evolution of ELM value of the learned policy in Random Games M according to different functional criteria: (a)~$sum$ and (b)~$product$. The X axis represents learning iterations ($\times10^3$); the Y axis represents ELM value.}
    \label{fig:dynamics}
\end{figure}

%\begin{table}[ht]
%\renewcommand\arraystretch{1.1}
%\caption{The smallest iteration numbers, after which the value of ASPL becomes $5\%$-close the the optimal ELM value in Random Games M.} % title of Table
%\centering % used for centering table
%\begin{tabular}{l r r r}
%  \multicolumn{4}{c}{~}\\
%  \hline\hline
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%   & \multicolumn{3}{c}{Criterion}\\
%   & $~~~~max$ & $~~~~sum$ & $product$\\
%  \hline
%  RGs 2 & $40$ & $20$ & $40$\\
%  RGs 3 & $110$ & $50$ & $130$\\
%  RGs 5 & $450$ & $260$ & $320$\\
%  RGs 10 & $2550$ & $1060$ & $1600$\\
%  \hline
%\end{tabular}
%\label{table:5percent}
%\renewcommand\arraystretch{1.0}
%\end{table}
%\section{Discussions}\label{discussions}
%So far, we have seen that ASPL is effective in repeated games.
%It permits a learning of a strategy whose
%value maximizes a given functional optimality criterion. As we
%observed, this value is often higher than the corresponding values
%of solutions found according to relational optimality criteria such
%as Nash equilibrium or Pareto-efficient solution.
%In this section, we talk about the extensions of ASPL to more
%complex settings, such as $n$-player ($n>2$) repeated games and
%multistate environments (such as stochastic
%games~\cite{hu-wellman:2003}).
%
%If ``explore-then-exploit'' principle is adopted, one of possible
%extensions of ASPL to $n$-player repeated games is quite
%straightforward. Instead of two roles -- leader and follower --
%there will be $n$ roles, one per player. For example, player $1$
%assigned with the role $1$ will behave as leader. Any other player
%$p$ assigned with a role $1 < p \leq n$ will behave as follower
%whose leader is player $p-1$. On the other hand, if ``mixed
%exploring-exploiting'' principle is used, no special modifications
%are required: the COB heuristic, for example, is naturally
%extendable to $n$-player case. Obviously, in both cases each player
%$1 \leq p \leq n$ needs to maintain the counters $L^q$ and $K^q$ for
%all other players.

%A good strategy at time step $t$ in state $s$ for an agent $p$
%acting in an environment having multiple states must take into
%account the transitions to other states and the decisions the agent
%can take in these states at times $t'=t+1,t+2,\ldots$. The problem
%is much more complicated when, in the same environment, there are
%more than one player whose joint actions trigger state transitions
%and rewards. If players' rewards are not identical in all states,
%such problems are typically modeled as stochastic games. However, no
%efficient algorithms to compute a solution (given environment's
%model) for a stochastic game exist\footnote{One recent exception is
%a polynomial-time planning algorithm, by Munoz de Cote and
%Littman~\cite{Munoz-de-Cote-Littman:2008}, for a special case of
%two-player repeated stochastic games.}. Further, there are no
%generally applicable and efficient MAL algorithms for these
%problems.

%To make an extension of ASPL to multistate environments, one could
%once again take advantage of the self-play setting. Depending on the
%nature of the environment, agents can use a certain (known to all
%agents) algorithm to compute a set of strategies for a given
%environment. For example, for a multi-robot motion coordination
%problem~\cite{hu-wellman:2003}, these strategies can be possible
%trajectories of a robot. To each of these strategies robots can
%associate an action of a top level repeated game $\Gamma$. Then, a
%joint-action in the game $\Gamma$ is a pair of trajectories in the
%original multistate environment, and the corresponding reward is the
%cumulative reward of players after simultaneously executing this
%pair of trajectories.
%By repeatedly playing the game $\Gamma$, the robots can
%learn the best combination of trajectories for the original
%environment.

\section{Related Work}
\label{sec:related} Here, we would emphasize two related works. In
the first one, by Greenwald~\cite{greenwald2003cql}, the desired
solution of the learning problem is correlated equilibrium. When
several equilibria are possible, the author proposes to choose a
unique one by using an ``objective function'', an analog of our
functional criterion. However, this implies that agents have two
opposite goals: (1) to be selfish (inclination to equilibrium
solution implies the agents to be selfish) and (2) to want to
sacrifice, by selecting, using the objective function, an
equilibrium, which is probably sub-optimal to itself. Generally, if
the agents are supposed to want to sacrifice, there is no need in
seeking after an equilibrium solution.

In the second work, Crandall and Goodrich~\cite{crandall2005lcc}
propose an approach to the learning of multi-step strategies,
analogous to our extended strategies. When the length~$l$ of an
extended joint action is fixed to $1$ (the only value used in their
experiments), this yields in a relatively small number of learning
iterations. However, by increasing~$l$ (to allow more complex
extended joint actions and thereby obtain other values inside the
convex hull) the number of joint strategies to explore becomes
exponentially large, but only a (very) small number of them is
really interesting. In our approach, we find the best extended joint
strategies directly, i.e., without enumeration of all pairs of
action sequences of length~$l$. Besides, the approach of Crandall
and Goodrich does not permit satisfying a given functional
criterion.

\section{Conclusions}
In this paper, we presented a novel approach to learning in
self-play. We argued that when the learning problem is a controlled
self-play, a good learning algorithm should get additional benefit
from this. E.g., the agents can have internal variables initialized
with the same values, use the same utility metric and optimize the
same function. We then presented the notion of functional optimality
criterion, as opposed to relational optimality criteria such as Nash
equilibrium. We pointed out that the solution of a problem found by
an algorithm seeking to satisfy a relational criterion can be
suboptimal if a functional optimality criterion needs to be
satisfied. We demonstrated that in such problems, our algorithm is a
better choice than the classical algorithms for self-play.
%We also
%presented the notion of extended strategy and showed how it can be
%learned.
%These
%non-stationary strategies are especially effective in satisfying the
%product optimality criterion.
%In our future work, we will explore in more detail the questions
%discussed in Section \ref{discussions}, namely the extension of ASPL
%to multiplayer and multistate environments for solving a number of
%interesting practical tasks, such as the learning of efficient
%multirobot navigation strategies, multiagent perimeter control, and
%others.

%\small
\bibliographystyle{splncs}
\bibliography{burkov}
\end{document}
