\documentstyle[jair,twoside,11pt,theapa,epic,eepic]{article}


\jairheading{2}{1995}{475-500}{10/94}{5/95}
\ShortHeadings{Adaptive Load Balancing: A Study in Multi-Agent Learning}%
{Schaerf, Shoham, \& Tennenholtz}
\firstpageno{475}


%% macros for the graphs 	
\newcommand{\plotcharms}{\makebox(0,0){$\otimes$}}
\newcommand{\plotcharscs}{\circle{0.15}}
\newcommand{\plotcharcs}{\makebox(0,0){$\diamond$}}
%%%

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}


\begin{document}

\title{Adaptive Load Balancing: A Study in Multi-Agent Learning}
\author{\name Andrea Schaerf
        \email aschaerf@dis.uniroma1.it\\
        \addr Dipartimento  di Informatica e Sistemistica\\ 
            Universit\`a di Roma ``La Sapienza'', Via Salaria 113, 
            I-00198 Roma, Italy
        \AND
        \name Yoav Shoham
        \email shoham@flamingo.stanford.edu\\
        \addr Robotics Laboratory, Computer Science Department\\
              Stanford University, Stanford, CA 94305, USA
        \AND
        \name Moshe Tennenholtz
        \email moshet@ie.technion.ac.il\\
        \addr Faculty of Industrial Engineering and Management\\
              Technion, Haifa 32000, Israel
}

\maketitle

\begin{abstract}
  We study the process of multi-agent reinforcement learning in the context of
  load balancing in a distributed system, without use of either central
  coordination or explicit communication.  We first define a precise framework
  in which to study adaptive load balancing, important features of which are its
  stochastic nature and the purely local information available to individual
  agents.  Given this framework, we show illuminating results on the interplay
  between basic adaptive behavior parameters and their effect on system
  efficiency.  We then investigate the properties of adaptive load balancing in
  heterogeneous populations, and address the issue of exploration vs.\ 
  exploitation in that context.  Finally, we show that naive use of
  communication may not improve, and might even harm system efficiency.
\end{abstract}

\section{Introduction}\label{intro}

This article investigates multi-agent reinforcement learning in the context of a
concrete problem of undisputed importance -- load balancing.  Real life provides
us with many examples of emergent, uncoordinated load balancing: traffic on
alternative highways tends to even out over time; members of the computer
science department tend to use the most powerful of the networked workstations,
but eventually find the lower load on other machines more inviting; and so on.
We would like to understand the dynamics of such emergent load-balancing
systems and apply the lesson to the design of multi-agent systems.

We define a formal yet concrete framework in which to study the issues, called a
{\em multi-agent multi-resource stochastic\/} system, which involves a set of
agents, a set of resources, probabilistically changing resource capacities,
probabilistic assignment of new jobs to agents, and probabilistic job sizes. An
agent must select a resource for each new job, and the efficiency with which the
resource handles the job depends on the capacity of the resource over the
lifetime of the job as well as the number of other jobs handled by the resource
over that period of time.  Our performance measure for the system aims at
globally optimizing the resource usage in the system while ensuring fairness
(that is, a system shouldn't be made efficient at the expense of any particular
agent), two common criteria for load balancing.

How should an agent choose an appropriate resource in order to optimize
these measures?  Here we make an important assumption, in the spirit of
reinforcement learning \cite{ReadReinfor}: The information available to the
agent is only its prior experience. In particular, the agent does not
necessarily know the past, present, or future capacities of the
resources,\footnote{In many applications the capacities of the resources are
  known, at least to some extent. This point will be discussed later. Basically,
  in this paper we wish to investigate how far one can go using only purely
  local feedback and without the use of any global information
  \cite{Kaelbling,ReadReinfor}.} and is unaware of past, current, or future jobs
submitted by the various agents, not even the relevant probability
distributions.  The goal of each agent is thus to adapt its resource-selection
behavior to the behavior of the other agents as well as to the changing
capacities of the resources and to the changing load, without explicitly knowing
what they are.

We are interested in several basic questions: 

\begin{itemize} 
\item What are good resource-selection rules?
\item How does the fact that different agents may use different
  resource-selection rules affect the system behavior?
\item Can communication among agents improve the system efficiency?
\end{itemize}

In the following sections we show illuminating answers to these questions. The
contribution of this paper is therefore twofold. We apply multi-agent
reinforcement learning to the domain of adaptive load balancing and we use this
basic domain in order to demonstrate basic phenomena in multi-agent
reinforcement learning.


The structure of this paper is as follows.  In Section~\ref{general-setting} we
discuss our general setting. The objective of this section is to motivate our
study and point to its impact.  The formal framework is defined and
discussed in Section~\ref{setting}. Section~\ref{selection-rules} completes the
discussion of this framework by introducing the resource selection rule and its
parameters, which function as the ``control knobs'' of the adaptive process.  In
Section~\ref{results} we present experimental results on adaptive behavior
within our framework and show how various parameters affect the efficiency of
adaptive behavior.  The case of heterogeneous populations is investigated in
Section~\ref{sec-heterogeneity}, and the case of communicating populations is
discussed in Section~\ref{sec-communication}.  In Section~\ref{discussion} we
discuss the impact of our results.  In
Section~\ref{related-work} we put our work in the perspective of related work.
Finally, in Section~\ref{conclusions} we conclude with a brief summary.


\section{The General Setting} \label{general-setting}

This paper applies reinforcement learning to the domain of adaptive load
balancing. However, before presenting the model we use and our detailed study,
we need to clarify several points about our general setting. In particular, we
need to explain the interpretation of reinforcement learning and the
interpretation of load balancing we adopt.

Much work has been devoted in the recent years to distributed and adaptive load
balancing. One can find related work in the field of distributed computer
systems \cite<e.g.,>{PuTS88,MirStan,BilPas,GloPas,MirTowStan,Zhou,ELZ86}, in
organization theory and management science \cite<e.g.,>{Malone}, and in
distributed AI \cite<e.g.,>{BG}.  Although some motivations of the
above-mentioned lines of research are similar, the settings discussed have some
essential differences.

Work on distributed computer systems adopts the view of a set of computers each
of which controls certain resources, has an autonomous decision-making
capability, and jobs arrive to it in a dynamic fashion. The decision-making
agents of the different computers (also called nodes) try to share the system
load and coordinate their activities by means of communication.  The actual
action to be performed, based on the information received from other computers,
may be controlled in various ways.  One of the ways adopted to control the
related decisions is through learning automata \cite{NarTha}.

In the above-mentioned work each agent is associated with a set of resources,
where both the agent and the related resources are associated with a node in the
distributed system.  Much work in management science and in distributed AI
adopts a somewhat complementary view. In difference to classical work in
distributed operating systems, an agent is not associated with a set of
resources that it controls.  The agents are autonomous entities which negotiate
among themselves \cite{ZR,KW} on the use of shared resources.  Alternatively,
the agents (called managers in this case) may negotiate the task to be executed
with the processors which may execute it \cite{Malone}.

The model we adopt has the flavor of models used in distributed AI and
organization theory. We assume a strict separation between agents and resources.
Jobs arrive to agents who make decisions about where to execute them. The
resources are passive (i.e., do not make decisions).  A typical example of such
a setting in a computerized framework is a set of PCs, each of which is
controlled by a different user and submits jobs to be executed on one of several
workstations. The workstations are assumed to be independent of each other and
shared among all the users.  The above example is a real-life situation which
motivated our study and the terminology we adopt is taken from such a
framework. However, there are other real-life situations related to our model in
areas different from classical distributed computer systems.


A canonical problem related to our model is the following one \cite{Arthur}: An
agent, embedded in a multi-agent system, has to select among a set of bars (or a
set of restaurants). Each agent makes an autonomous decision but the performance
of the bar (and therefore of the agents that use it) is a function of its
capacity and of the number of agents that use it.  The decision of going to a
bar is a stochastic process but the decision of which bar to use is an
autonomous decision of the respective agent.  A similar situation arises when a
product manager decides which processor to use in order to perform a particular
task. The model we present in Section~\ref{setting} is a general model where
such situations can be investigated.  In these situations a job arrives to an
agent (rather than to a node consisting of particular resources) who decides
upon the resource (e.g., restaurant) where his job should be executed; there is
a-priori no association between agents and resources.

We now discuss the way the agents behave in such a framework.  The common theme
among the above-mentioned lines of research is that load-balancing is achieved
by means of communication among active agents or active resources (through the
related decision-making agents). In our study we adopt a complementary view.  We
consider agents who act in a {\em purely local\/} fashion, based on {\em purely
  local information\/} as described in the recent reinforcement learning
literature.  As we mentioned, learning automata were used in the field of
distributed computer systems in order to perform adaptive load balancing.
Nevertheless, the related learning procedures rely heavily on communication
among agents (or among decision-making agents of autonomous computers).  Our
work applies recent work on reinforcement learning in AI where the information
the agent gets is purely local.  Hence, an agent will know how efficient the
service in a restaurant has been only by choosing it as a place to eat. We don't
assume that agents may be informed by other agents about the load in other
restaurants or that the restaurants will announce their current load. This makes
our work strictly different from other work applying reinforcement learning to
adaptive load balancing.

The above features make our model and study both basic and general.  Moreover,
the above discussion raises the question of whether reinforcement learning
(based on purely local information and feedback) can guarantee useful load
balancing.  The combination of the model we use and our perspective on
reinforcement learning makes our contribution novel.  Nevertheless, as we
mentioned above (and as we discuss in Section~\ref{related-work}) the model we
use is not original to us and captures many known problems and situations in
distributed load balancing.  We apply reinforcement learning, as discussed in
the recent AI literature, to that model and investigate the properties of the
related process.

\section{The Multi-Agent Multi-Resource Stochastic System}\label{setting}

In this section we define the concrete framework in which we study dynamic load
balancing.  The model we present captures adaptive load balancing in the general
setting mentioned in Section~\ref{general-setting}.  We restrict the discussion
to discrete, synchronous systems (and thus the definition below will refer to
$\cal N$, the natural numbers); similar definitions are possible in the
continuous case. We concentrate on the case where a job can be executed using
any of the resources.  Although somewhat restricting, this is a common practice
in much work in distributed systems \cite{MirStan}.

\begin{definition}
  A {\em multi-agent multi-resource stochastic system\/} is a $6$-tuple $\langle
  {\cal A},{\cal R},{\cal P},{\cal D},{\cal C},$ $SR \rangle$, where ${\cal
    A}=\{a_1,\ldots, a_N\}$ is a set of {\em agents}, ${\cal
    R}=\{r_1,\ldots,r_M\}$ is a set of {\em resources}, ${\cal P}: {\cal
    A}\times {\cal N} \rightarrow [0,1]$ is a {\em job submission function},
  ${\cal D}:{\cal A}\times {\cal N}\rightarrow \Re$ is a probabilistic {\em job
    size function}, ${\cal C}:{\cal R}\times {\cal N} \rightarrow \Re$ is a
  probabilistic {\em capacity function}, and $SR$ is a resource-selection rule.
\end{definition}

The intuitive interpretation of the system is as follows.  Each of the resources
has a certain capacity, which is a real number; this capacity changes over time,
as determined by the function ${\cal C}$.  At each time point each agent is
either idle or engaged.  If it is idle, it may submit a new job with probability
given by ${\cal P}$.  Each job has a certain size which is also a real number.
The size of any submitted job is determined by the function ${\cal D}$. (We will
use the unit {\em token\/} where referring to job sizes and resource capacities,
but we do not mean that tokens come only in integer quantities.)  For each new
job the agent selects one of the resources.  This choice is made according to
the rule SR; since there is much to say about this rule, we discuss it
separately in the next section.

In our model, any job may run on any resource. Furthermore, there is no limit on
the number of jobs served simultaneously by a given resource (and thus no
queuing occurs).  However, the quality of the service provided by a resource at
a given time deteriorates with the number of agents using it at that time.
Specifically, at every time point the resource distributes its current capacity
(i.e., its tokens) equally among the jobs being served by it. The size of each
job is reduced by this amount and, if it drops to (or below) zero, the job is
completed, the agent is notified of this, and becomes idle again.  Thus, the
execution time of a job $j$ depends on its size, on the capacity over time of
the resource processing it, and on the number of other agents using that
resource during the execution of $j$.

Our measure of the system's performance will be twofold: We aim to minimize
time-per-token, averaged over all jobs, as well as to minimize the standard
deviation of this random variable.  Minimizing both quantities will ensure
overall system efficiency as well as fairness. The question is which selection
rules yield efficient behavior; so we turn next to the definition of these
rules.

\section{Adaptive Resource-Selection Rules}\label{selection-rules}

The rule by which agents select a resource for a new job, the {\em selection
  rule\/} (SR), is the heart of our adaptive scheme and the topic of this
section.  Throughout this section and the following one we make an assumption of
homogeneity.  Namely, we assume that all the agents use the same SR\@. Notice
that although the system is homogeneous, each agent will act based only on its
local information.  In Sections~\ref{sec-heterogeneity}
and~\ref{sec-communication} we relax the homogeneity assumption and discuss
heterogeneous and communicating populations.

As we have already emphasized, among all possible adaptive SRs we are interested
in purely local SRs, ones that have access only to the experience of the
particular agent. In our setting this experience consists of results of previous
job submissions; for each job submitted by the agent and already completed, the
agent knows the name $r$ of the resource used, the point in time, $t_{start}$,
the job started, the point in time, $t_{stop}$, the job was finished, and the
job size $S$.  Therefore, the input to the SR is, in principle, a list of
elements in the form $(r,t_{start},t_{stop},S)$. Notice that this type
of input captures the general type of systems we are interested in. Basically,
we wish to assume as little as possible about the information available to an
agent in order to capture real loosely-coupled systems where more global
information is unavailable.


Whenever agent $i$ selects a resource for its job execution, $i$ may get its
feedback after non-negligible time, where this feedback may depend on decisions
made by other agents before and after agent $i$'s decision.  This forces the
agent to rely on a non-trivial portion of its history and makes the problem
much harder.

There are uncountably many possible adaptive SRs and our aim is not to gain
exhaustive understanding of them. Rather, we have experimented with a family of
intuitive and relatively simple SRs and have compared them with some
non-adaptive ones.  The motivation for choosing our particular family of SRs is
partially due to observations made by cognitive psychologists on how people tend
to behave in multi-agent stochastic and recurrent situations.  In principle, our
set of SRs captures the two most robust aspects of these observations: ``The law
of effect'' \cite{Thronkide} and the ``Power law of practice''
\cite{Blackburn}.  In our family of rules, called $\Omega$, which partially
resembles the learning rules discussed in the learning automata literature
\cite{NarTha}, and partially resembles the interval estimation algorithm
\cite{Kaelbling}, agents do not maintain complete history of their experience.
Instead, each agent, $A$, condenses this history into a vector, called the {\em
  efficiency estimator}, and denoted by $ee_A$.  The length of this vector is
the number of resources, and the $i$'th entry in the vector represents the
agent's evaluation of the current efficiency of resource $i$ (specifically,
$ee_A(R)$ is a positive real number). This vector can be seen as the state of a
learning automaton.  In addition to $ee_A$, agent $A$ keeps a vector $jd_A$,
which stores the number of completed jobs which were submitted by agent $A$ to
each of the resources, since the beginning of time.  Thus, within $\Omega$, we
need only specify two elements:
\begin{enumerate}
\item How agent $A$ updates $ee_A$ when a job is completed
\item How agent $A$ selects a resource for a new job, given $ee_A$ and $jd_A$ 
\end{enumerate}

Loosely speaking, $ee_A$ will be maintained as a weighted sum of the new
feedback and the previous value of $ee_A$, and the resource selected will most
probably be the one with highest $ee_A$ entry except that with low probability
some other resource will be chosen.  These two steps are explained more
precisely in the following two subsections.


\subsection{Updating the Efficiency Estimator} 

We take the function updating $ee_A$ to be
%
$$ee_A(R) :=   W T + (1 - W) ee_A(R)$$
%
where $T$ represents the time-per-token of the newly completed job and is
computed from the feedback $(R,t_{start},t_{stop},S)$ in the following
way:\footnote{Using parallel processing terminology, $T$ can be viewed as a {\em
    stretch factor}, which quantifies the stretching of a program's
processing time due to multiprogramming \cite{FerSerZei}.}
%
$$T = (t_{stop} - t_{start})/S$$
%
We take $W$ to be a real value in the interval $[0,1]$, whose actual value
depends on $jd_A(R)$. This means that we take a weighted average between the new
feedback value and the old value of the efficiency estimator, where $W$
determines the weights given to these pieces of information. The
value of $W$ is obtained from the following function:
%
$$W = w + (1 - w)/jd_A(R)$$
%
In the above formula $w$ is a real-valued constant.  The term $(1 - w)/jd_A(R)$
is a correcting factor, which has a major effect only when $jd_A(R)$ is low;
when $jd_A(R)$ increases, reaching a value of several hundreds, this term
becomes negligible with respect to $w$.

\subsection{Selecting the Resource}

The second ingredient of adaptive SRs in $\Omega$ is a function $pd_A$ selecting
the resource for a new job based on $ee_A$ and $jd_A$.  This function is
probabilistic. We first define the following function
%
\[
pd'_A(R) :=
\left\{
\begin{array}{l}
ee_A(R)^{-n} ~~~~~{\rm if}~~ jd_A(R) > 0\\
E[ee_A]^{-n} ~~~~~{\rm if}~~ jd_A(R) = 0
\end{array}
\right.
\]
%
where $n$ is a positive real-valued parameter and $E[ee_A]$ represents the
average of the values of $ee_A(R)$ over all resources satisfying $jd_A(R) > 0$.
To turn this into a probability function, we define the
$pd_A$ as the normalized version of $pd'_A$:
%
\[
pd_A(R) := pd'_A(R)/\sigma
\]
%
where $\sigma = \Sigma_R pd'_A(R)$ is a normalization factor.\footnote{If for
  all $R$ we have $jd_A(R) = 0$, (i.e., if the agent is going to submit its very
  first job), then we assume the agent chooses a resource randomly (with a
  uniform probability distribution).}

The function $pd_A$ clearly biases the selection towards resources that have
performed well in the past. The strength of the bias depends on $n$; the larger
the value of $n$, the stronger the bias.  In extreme cases, where the value of
$n$ is very high (e.g., $\geq 20$), the agent will always choose the resource
with the best record. This strategy of ``always choosing the best'', although
perhaps intuitively appealing, is in general not a good one; it does not allow
the agent to exploit improvements in the capacity or load on other resources. We
discuss this SR in the following subsection, and expand on the issue of
exploration versus exploitation in Sections~\ref{sec-heterogeneity}
and~\ref{sec-communication}.

To summarize, we have defined a general setting in which to investigate emergent
load balancing.  In particular, we have defined a family of adaptive
resource-selection rules, parameterized by a pair $(w,n)$. These parameters
serve as knobs with which we tune the system so as to optimize its performance.
In the next section we turn to experimental results obtained with this system.


\subsection{The Best Choice SR (BCSR)}

The Best Choice SR (BCSR) is a learning rule that assumes a high value of $n$,
i.e, which always chooses the best resource in a given point.  We will assume
$w$ is fixed to a given value while discussing BCSR\@.  In our previous work
\cite{STCONV,STCOLEARN}, we showed that learning rules that strongly resemble
BCSR are useful for several natural multi-agent learning settings.  This
suggests that we need to carefully study it in the case of adaptive load
balancing. As we will demonstrate, BCSR is not always useful in the load
balancing setting.

The difference between BCSR and a learning rule where the value of $n$ is low,
is that in the latter case the agent gives relatively high probability for the
selection of a resource that didn't give the best results in the past. In that
case the agent might be able to notice that the behavior of one of the resources
has been improved due to changes in the system.

Note that the exploration of ``non-best'' resources is crucial when the dynamics
of the system includes changes in the capacities of the resources.  In such
cases, the agent could not take advantage of possible increases in the capacity
of resources if it uses the BCSR\@.  One might wonder, however, whether in cases
where the main dynamic changes of the system stem from load changes, relying on
BCSR is sufficient.  If the latter is true, we will be able to ignore the
parameter $n$ and to concentrate only on the BCSR, in systems where the capacity
of resources is fixed.  In order to clarify this point, we consider the
following example.

Suppose there are only two resources, $R_1$ and $R_2$, whose respective (fixed)
capacities, $c_{R_1}$ and $c_{R_2}$, satisfy the equality $c_{R_1} = 2 c_{R_2}$.
Assume now that the load of the system varies between a certain low value and a
certain high one.

If the system's load is low and the agents adopt BCSR, then the system will
evolve in a way where almost all of the agents would be preferring $R_1$ to
$R_2$. This is due to the fact that, in the case of low load, there are only few
overlaps of jobs, hence $R_1$ is much more efficient.  On the other hand,
when the system's load is high, $R_1$ could be very busy and some of the agents
would then prefer $R_2$, since the performance obtained using the less crowded
resource $R_2$ could be better than the one obtained using the overly crowded
resource $R_1$. In the extreme case of a very high load, we expect the agents to
use $R_2$ one third of the time.

Assume now that the load of the system starts from a low level, then increases
to a high value, and then decreases to reach its original value. When the load
increases, the agents, that were mostly using $R_1$, will start observing that
$R_1$'s performance is becoming worse and, therefore, following the BCSR they
will start using $R_2$ too.  Now, when the load decreases, the agents which were
using $R_2$ will observe an improvement in the performance of $R_2$, but the
value they have stored for $R_1$ (i.e., $ee_A(1)$), will still reflect the
previous situation. Hence, the agents will keep on using $R_2$, ignoring the
possibility of obtaining much better results if they moved back to $R_1$.  In
this situation, the randomized selection makes the agents able to use $R_1$
(with a certain probability) and therefore some of them may discover that the
performance of $R_1$ is better than that of $R_2$ and switch back to $R_1$. This
will improve the system's efficiency in a significant manner.

The above example shows that the BCSR is, in the general case, not a good
choice. This is in general true when the value of $n$ is too high.

In the above discussion we have assumed that the changes in the load are
unforeseen. If we are able to predict the changes in the load, the agents can
simply use the BCSR while the load is fixed and then use a low value of $n$
during the changes. In our case, instead, without even realizing that the system
has changed in some way, the agents would need to (and, as we will see, would be
able to) adapt to dynamic changes as well as to each other.

\section{Experimental Results}\label{results}
In this section we compare SRs in $\Omega$ to each another, as well as to some
non-adaptive, benchmark selection rules.

The non-adaptive SRs we consider in this paper are those in which the agents
partition themselves according to the capacities and the load of the system in a
fixed predetermined manner and each agent uses always the same resource.  Later
in the paper, a SR of this kind is identified by a {\em configuration\/} vector,
which specifies, for each resource, how many agents use it.  When we test our
adaptive SRs, we compare the performance against the non-adaptive SRs that
perform best on the particular problem. This creates a highly competitive set of
benchmarks for our adaptive SRs.

In addition, we compare our adaptive SRs to the {\em load-querying\/} SR which
is defined as follows: Each agent, when it has a new job, asks all the resources
how busy they are and always chooses the less crowded one.

\subsection{An Experimental Setting}\label{exp-setting}

We now introduce a particular experimental setting, in which many of the results
described below were obtained. We present it in order to be concrete about the
experiments; however, the qualitative results of our experiments were observed
in a variety of other experimental settings.

One motivation of our particular setting stems from the PCs and workstations
problem mentioned in Section~\ref{general-setting}.  For example, part of our
study is related to a set of computers located at a single site. These computers
have relatively high load with some peak hours during the day and a low load at
night (i.e., the chances a user of a PC submits a job is higher during the day
time of the week days than at night and on weekend).  Another part of our study
is related to a set of computers split all around the world, where the load has
quite random structure (i.e., due to difference in time zones, users may use PCs
in unpredictable hours).

Another motivation of our particular setting stems from the restaurant problem
mentioned in Section~\ref{general-setting} \cite<for discussion on the related
``bar problem'' see>{Arthur}.  For example, we can consider a set of snack bars
located at an industrial park. These snack bars have relatively high loads with
some peak hours during the day and low load at night (i.e., the chances an
employee will choose to go to a snack-bar is higher during the day because there
are more employees present during the day).  Conversely, we can assume a set of
bars near an airport where the load has quite random structure (i.e., the
airport employees may like to use these snack-bars in quite unpredicted hours).

Although these are particular real-situations, we would like to emphasize the
general motivation of our study and the fact that the related phenomena have
been observed in various different settings.

We take $N$, the number of agents, to be $100$, and $M$, the number of
resources, to be $5$. In the first set of experiments we take the capacities of
the resources to be fixed. In particular, we take them to be
$c_1=40,~c_2=20,~c_3=20,~c_4=10,~c_5=10$.  We assume that all agents have the
same probability of submitting a new job.  We also assume that all agents have
the same distribution over the size of jobs they submit; specifically, we assume
it to be a uniform distribution over the integers in the range [50,150].

For ease of exposition, we will assume that each point in time corresponds to a
second, and we consequently count the time in minutes, hours, days, and weeks.
The hour is our main point of reference; we assume, for simplicity, that the
changes in the system (i.e., load change and capacity change) happen only at the
beginning of a new hour.  The probability of submitting a job at each second,
which corresponds to the load of the system, can vary over time; this is the
crucial factor to which the agents must adapt. Note that agents can submit jobs
at any second, but the probability of such submission may change.  In particular
we concentrate on three different values of this quantity, called
$L_{lo},L_{hi}$ and $L_{peak}$, and we assume that the system load switches
between those values.  The actual values of $L_{lo},L_{hi}$ and $L_{peak}$ in
the following quantitative results are $0.1\%$, $0.3\%$ and $1\%$, which roughly
correspond to each agent submitting 3.6, 10.8, and 36 jobs per hour (per agent)
respectively.

In the following, when measuring success, we will refer only to the average
time-per-token.\footnote{In the data shown later we refer, for convenience, to
  the time for 1000 tokens.} However, the adaptive SRs that give the best
average time-per-token were also found to be fair.

\subsection{Fixed Load}

We start with the case in which the load is fixed. This case is not the most
interesting for adaptive behavior; however, a satisfactory SR should show
reasonably efficient behavior in that basic case, in order to be useful when the
system stabilizes.

We start by showing the behavior of non-adaptive benchmark SRs in the case of
fixed load.\footnote{The non-adaptive SRs are human-designed SRs that are used
  as benchmarks; they assume knowledge of the load and capacity, which is not
  available for the adaptive SRs we design.} Figure~\ref{table1} shows those
that give the best results, for each of the three loads.

\begin{figure} 
\begin{center}
\begin{tabular}{|c||c|c|}\hline
load 		&	configuration		& 	time-per-token	\\  \hline\hline
$L_{lo}$	& 	$\{100,0,0,0,0\}$	&	38.935	\\  \hline
$L_{hi}$	& 	$\{66,16,16,1,1\}$	&	60.768	\\  \hline
$L_{peak}$	& 	$\{40,20,20,10,10\}$ 	&	196.908	\\  \hline
\end{tabular}
\end{center}
\caption{Best non-adaptive SRs for fixed load \label{table1}}
\end{figure}

As we can see, there is a big difference between the three loads mentioned
above. When the load is particularly high, the agents should scatter around all
the resources at a rate proportional to their capacities; when the load is low
they should all use the best resource. Given the above, it is easy to see that
an adaptive SR can be effective only if it enables moving quickly from one
configuration to the other.

In a static setting such as this, we can expect the best non-adaptive SRs to
perform better than adaptive ones, since the information gained by the
exploration of the adaptive SRs can be built-in in the non-adaptive ones.  The
experimental results confirm this intuition, as shown in Figure~\ref{fixed-load}
for $L_{hi}$. The figure shows the performance obtained by the population when
the value of $n$ varies between 2 to 10 and for three values of $w$: 0.1, 0.3,
and 0.5. Note that for the values of $(n,w)$ that are good choices in the
dynamic cases (see later in the paper, values in the intervals $[3,5]$ and
$[0.1,0.5]$, respectively), the deterioration in the performance of the adaptive
SRs with respect to the non-adaptive ones is small.  This is an encouraging
result, since adaptive SRs are meant to be particularly suitable for dynamic
systems. In the following subsections we see that indeed they are.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[t]
\begin{center}
\unitlength = 1cm

\begin{picture}(12,10)(1,59)

\linethickness{0.4mm}

\put(1,60){\vector(1,0){10}}
\put(1,60){\vector(0,1){8}}

\thicklines

\multiput(1,61)(0,1){7}{\line(1,0){0.1}}
\multiput(2,60)(1,0){9}{\line(0,1){0.1}}
\multiputlist(2,59.7)(1,0){2,3,4,5,6,7,8,9,10} %number along X-axis
\multiputlist(0.7,61)(0,1)[r]{61,62,63,64,65,66,67} %number along Y-axis
\put(6,59){\makebox(0,0) {Exponent of the Randomization Function: $n$}}
\put(-.3,64){\makebox(0,0) {\shortstack{%
A\\v\\e\\r\\a\\g\\e\\ \\ \\T\\i\\m\\e\\ \\  \\p\\e\\r\\ \\ \\T\\o\\k\\e\\n}}} 

\thinlines

\put(4,67){\makebox(0,0)[tl]{\fbox{\shortstack[l]{%
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharms}}} Weight: w = 0.5\\[0.5mm]
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharscs}}} Weight: w = 0.3\\[0.5mm]
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharcs}}} Weight: w = 0.1\\[0.5mm]
{\makebox(2,0)[b]{}}
}}}}

\begin{dottedjoin}{0.1}
\thicklines
\jput(2,67.312){\plotcharms}
\jput(2.5,65.131){\plotcharms}
\jput(3,63.831){\plotcharms}
\jput(3.5,63.175){\plotcharms}
\jput(4,62.548){\plotcharms}
\jput(4.5,62.198){\plotcharms}
\jput(5,62.058){\plotcharms}
\jput(6,61.682){\plotcharms}
\jput(7,61.532){\plotcharms}
\jput(8,61.434){\plotcharms}
\jput(9,61.298){\plotcharms}
\jput(10,61.270){\plotcharms}
\end{dottedjoin}

\begin{dashjoin}{0.1}
\thicklines
\jput(2,67.148){\plotcharscs}
\jput(2.5,64.973){\plotcharscs}
\jput(3,63.665){\plotcharscs}
\jput(3.5,62.815){\plotcharscs}
\jput(4,62.363){\plotcharscs}
\jput(4.5,62.081){\plotcharscs}
\jput(5,61.896){\plotcharscs}
\jput(6,61.569){\plotcharscs}
\jput(7,61.496){\plotcharscs}
\jput(8,61.454){\plotcharscs}
\jput(9,61.330){\plotcharscs}
\jput(10,61.163){\plotcharscs}
\end{dashjoin}

\begin{drawjoin}
\thicklines
\jput(2,67.033){\plotcharcs}
\jput(2.5,64.816){\plotcharcs}
\jput(3,63.482){\plotcharcs}
\jput(3.5,62.594){\plotcharcs}
\jput(4,62.207){\plotcharcs}
\jput(4.5,61.887){\plotcharcs}
\jput(5,61.777){\plotcharcs}
\jput(6,61.590){\plotcharcs}
\jput(7,61.600){\plotcharcs}
\jput(8,61.685){\plotcharcs}
\jput(9,61.718){\plotcharcs}
\jput(10,61.757){\plotcharcs}
\end{drawjoin}
%
\end{picture}
\end{center}
\caption{Performance of the adaptive Selection Rules for fixed load\label{fixed-load}}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Changing Load}\label{sec-random-load}

We now begin to explore more dynamic settings. Here we consider the case in
which the load on the system (that is, the probability of agents submitting a
job at any time) changes over time.  In this paper we present two dynamic
settings: One in which the load changes according to a fixed pattern with only a
few random perturbations and another in which the load varies in some random
fashion. Specifically, in the first case we fix the load to be $L_{hi}$ for ten
consecutive hours, for five days a week, with two randomly chosen hours in which
it is $L_{peak}$, and to be $L_{lo}$ for the rest of the week.  In the second
case, we fix the number of hours in a week for each load as in the first case,
and we distribute them completely randomly in a week.

The results obtained for the two cases are similar.  Figure~\ref{random-load}
shows the results obtained by the adaptive SRs in the case of random load. The
best non-adaptive deterministic SR gives the time-per-token value of $69.201$
obtained with the configuration (partition of agents) $\{52,22,22,2,2\}$; the
adaptive SRs are superior. The load-querying SR instead gets the time-per-token
value of $48.116$, which is obviously better, but is not so far from the
performances of the adaptive SRs.

We also observe the following phenomenon: Given a fixed $n$ (resp.\ a fixed $w$)
the average time-per-token is non-monotonic in $w$ (resp.\ in $n$). This
phenomenon is strongly related to the issue of exploration versus exploitation
mentioned before and to phenomena observed in the study of Q-learning
\cite{Watkins}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[t]
\begin{center}
\unitlength = 1cm
\begin{picture}(12,10)(1,63)

\linethickness{0.4mm}
\put(1,64){\vector(1,0){10}}
\put(1,64){\vector(0,1){8}}

\thicklines

\multiput(1,65)(0,1){7}{\line(1,0){0.1}}
\multiput(2,64)(1,0){9}{\line(0,1){0.1}}
\multiputlist(2,63.7)(1,0){2,3,4,5,6,7,8,9,10} %number along X-axis
\multiputlist(0.7,65)(0,1)[r]{65,66,67,68,69,70,71} %number along Y-axis
\put(6,63){\makebox(0,0) {Exponent of the Randomization Function: $n$}}
\put(-.3,68){\makebox(0,0) {\shortstack{%
A\\v\\e\\r\\a\\g\\e\\ \\ \\T\\i\\m\\e\\ \\  \\p\\e\\r\\ \\ \\T\\o\\k\\e\\n}}} 

\thinlines

\put(3,71){\makebox(0,0)[tl]{\fbox{\shortstack[l]{%
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharms}}} Weight: w = 0.5\\[0.5mm]
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharscs}}} Weight: w = 0.3\\[0.5mm]
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharcs}}} Weight: w = 0.1\\[0.5mm]
{\makebox(2,0)[b]{}}
}}}}

\begin{dottedjoin}{0.1}
\thicklines
\jput(2,69.196){\plotcharms}
\jput(2.5,66.543){\plotcharms}
\jput(3,65.507){\plotcharms}
\jput(3.5,64.683){\plotcharms}
\jput(4,64.814){\plotcharms}
\jput(4.5,64.849){\plotcharms}
\jput(5,65.383){\plotcharms}
\jput(6,66.317){\plotcharms}
\jput(7,68.308){\plotcharms}
\jput(8,69.730){\plotcharms}
\jput(9,70.177){\plotcharms}
\jput(10,70.663){\plotcharms}
\end{dottedjoin}

\begin{dashjoin}{0.1}
\thicklines
\jput(2,69.117){\plotcharscs}
\jput(2.5,66.541){\plotcharscs}
\jput(3,65.299){\plotcharscs}
\jput(3.5,64.864){\plotcharscs}
\jput(4,64.413){\plotcharscs}
\jput(4.5,64.330){\plotcharscs}
\jput(5,64.854){\plotcharscs}
\jput(6,65.611){\plotcharscs}
\jput(7,66.900){\plotcharscs}
\jput(8,68.641){\plotcharscs}
\jput(9,69.382){\plotcharscs}
\jput(10,70.427){\plotcharscs}
\end{dashjoin}

\begin{drawjoin}
\thicklines
\jput(2,69.646){\plotcharcs}
\jput(2.5,67.339){\plotcharcs}
\jput(3,66.396){\plotcharcs}
\jput(3.5,65.793){\plotcharcs}
\jput(4,65.731){\plotcharcs}
\jput(4.5,65.672){\plotcharcs}
\jput(5,65.664){\plotcharcs}
\jput(6,65.127){\plotcharcs}
\jput(7,65.139){\plotcharcs}
\jput(8,66.310){\plotcharcs}
\jput(9,66.826){\plotcharcs}
\jput(10,67.205){\plotcharcs}
\end{drawjoin}
%
\end{picture}
\end{center}
\caption{Performance of the adaptive Selection Rules for random load
\label{random-load}}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We also notice how the two parameters $n$ and $w$ interplay. In fact, for each
value of $w$ the minimum of the time per token value is obtained with a
different value of $n$. More precisely, the higher $w$ is the lower $n$ must be
in order to obtain the best results. This means that, in order to obtain high
performance, highly exploratory activity (low $n$) should be matched with giving
greater weight to the more recent experience (high $w$).  This ``parameter
matching'' can be intuitively explained in the following qualitative way: The
exploration activity pays because it allows the agent to detect changes in the
system.  However, it is more effective if, when a change is detected, it can
significantly affect the efficiency estimator (i.e., if $w$ is high).
Otherwise, the cost of the exploration activity is greater than its gain.


\subsection{Changing Capacities}

We now consider the case in which the capacity of the resources can vary over
time. In particular, we will demonstrate our results in the case of the
previously mentioned setting.  We will assume the capacities rotate randomly
among the resources and, in five consecutive days, each resource gets the
capacity of 40 for one day, 20 for 2 days, and 10 for the other 2
days.\footnote{Usually the capacities will change in a less dramatic fashion.
  We use the above-mentioned setting in order to demonstrate the applicability
  of our approach under severe conditions.} The load also varies randomly.

The results of this experiment are shown in Figure~\ref{change-capacity}.  The
best non-adaptive SR in this case gives the time-per-token value of $118.561$
obtained with the configuration $\{20,20,20,20,20\}$.\footnote{The load-querying
  SR gives the same results as in the case of fixed capacities, because such SR
  is obviously not influenced by the change.} The adaptive SRs give much better
results, which are only slightly worse than in the case of fixed capacities.
The phenomena we mentioned before are visible in this case too.  See for example
how a weight of $0.1$ mismatches with the low values of $n$.


\begin{figure}[t]
\begin{center}
\unitlength = 0.4cm
\begin{picture}(30,25)(1,72.5)

\linethickness{0.4mm}
\put(1,75){\vector(1,0){22}}
\put(1,75){\vector(0,1){20}}

\thicklines

\multiput(1,77.5)(0,2.5){7}{\line(1,0){0.1}}
\multiput(2,75)(2.5,0){9}{\line(0,1){0.1}}
\multiputlist(2,74.25)(2.5,0){2,3,4,5,6,7,8,9,10} %number along X-axis
\multiputlist(0.7,77.5)(0,2.5)[r]{77.5,80,82.5,85,87.5,90,92.5} %number along Y-axis
\put(12,72.5){\makebox(0,0) {Exponent of the Randomization Function: $n$}}
\put(-2,85){\makebox(0,0) {\shortstack{%
A\\v\\e\\r\\a\\g\\e\\ \\ \\T\\i\\m\\e\\ \\  \\p\\e\\r\\ \\ \\T\\o\\k\\e\\n}}} 

\thinlines

\put(12,82.5){\makebox(0,0)[tl]{\fbox{\shortstack[l]{%
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharms}}}  Weight: w = 0.5\\[0.5mm]
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharscs}}}  Weight: w = 0.3\\[0.5mm]
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharcs}}}  Weight: w = 0.1\\[0.5mm]
{\makebox(2,0)[b]{}}
}}}}
v
\begin{dottedjoin}{0.25}
\thicklines
\jput(2,76.395){\plotcharms}  		%2
\jput(3.25,75.234){\plotcharms} 	%2.5
\jput(4.5,75.811){\plotcharms} 		%3
\jput(5.75,76.951){\plotcharms} 	%3.5
\jput(7,79.865){\plotcharms} 		%4
\jput(8.25,82.345){\plotcharms} 	%4.5
\jput(9.5,84.819){\plotcharms} 		%5
\jput(12,90.455){\plotcharms} 		%6
\jput(14.5,93.821){\plotcharms} 	%7
%\jput(17,97.622){\plotcharms} 		%8
%\jput(19.5,99.919){\plotcharms} 	%9
%\jput(22,101.68){\plotcharms} 		%10
\end{dottedjoin}

\begin{dashjoin}{0.25}
\thicklines
\jput(2,78.341){\plotcharscs} 		%2
\jput(3.25,77.082){\plotcharscs} 	%2.5
\jput(4.5,76.725){\plotcharscs} 	%3
\jput(5.75,77.872){\plotcharscs} 	%3.5
\jput(7,79.321){\plotcharscs} 		%4
\jput(8.25,80.008){\plotcharscs} 	%4.5
\jput(9.5,83.920){\plotcharscs} 	%5
\jput(12,87.452){\plotcharscs} 		%6
\jput(14.5,91.739){\plotcharscs} 	%7
%\jput(17,94.503){\plotcharscs} 	%8
%\jput(19.5,97.609){\plotcharscs} 	%9
%\jput(22,99.959){\plotcharscs} 	%10
\end{dashjoin}


\begin{drawjoin}
\thicklines
\jput(2,87.868){\plotcharcs} 		%2
\jput(3.25,85.689){\plotcharcs} 	%2.5
\jput(4.5,84.635){\plotcharcs} 		%3
\jput(5.75,84.066){\plotcharcs} 	%3.5
\jput(7,84.243){\plotcharcs} 		%4
\jput(8.25,84.025){\plotcharcs} 	%4.5
\jput(9.5,85.408){\plotcharcs} 		%5
\jput(12,88.024){\plotcharcs} 		%6
\jput(14.5,91.228){\plotcharcs} 	%7
%\jput(17,92.221){\plotcharcs} 		%8
%\jput(19.5,97.982){\plotcharcs} 	%9
%\jput(22,100.058){\plotcharcs} 	%10
\end{drawjoin}
%

\end{picture}
\end{center}
\caption{Performance of the adaptive Selection Rules for changing capacities
\label{change-capacity}}
\end{figure}



\section{Heterogeneous Populations}
\label{sec-heterogeneity}

Throughout the previous section we have assumed that all the agents use the same
SR, i.e. Homogeneity Assumption.  Such assumption models the situation in which
there is a sort of centralized {\em off-line\/} controller which, in the
beginning, tells the agents how to behave and then leaves the agents to make
their own decisions.

The situation described above is very different from having an {\em on-line\/}
centralized controller which makes every decision.  However, we would like now
to move even further from that and investigate the situation in which each
agent is able to make its own decision about which strategy to use and, maybe,
adjust it over time.

As a step toward the study of systems of this kind, we drop the Homogeneity
Assumption and consider the situation in which part of the population uses one
SR and the other part uses a second one.

In the first set of experiments, we consider the setting discussed in
Subsection~\ref{exp-setting} and we confront one with the other, two
populations (called 1 and 2) of the same size (50 agents each). Each population
uses a different SR in $\Omega$. The SR of population $i$ (for $i=1,2$) will be
determined by the pair of parameters $(w_i,n_i)$. The measure of success of
population $i$ will be defined as the average time-per-token of its members, and
will be denoted by $T_i$.

Figure~\ref{hetero-pop1} shows the result obtained for $w_1 = w_2 = 0.3$, and
$n_1 = 4$, and for different values of $n_2$, in the case of randomly varying
load.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[t]
\begin{center}
\unitlength = 1cm

\begin{picture}(12,10)(1,59)

\linethickness{0.4mm}

\put(1,60){\vector(1,0){10}}
\put(1,60){\vector(0,1){8}}

\thicklines

\multiput(1,61)(0,1){7}{\line(1,0){0.1}}
\multiput(2,60)(1,0){9}{\line(0,1){0.1}}
\multiputlist(2,59.7)(1,0){2,3,4,5,6,7,8,9,10} %number along X-axis
\multiputlist(0.7,61)(0,1)[r]{61,62,63,64,65,66,67} %number along Y-axis
\put(6,59){\makebox(0,0) {Exponent of the Randomization Function ($n_2$)}}
\put(-.3,64){\makebox(0,0) {\shortstack{%
A\\v\\e\\r\\a\\g\\e\\ \\ \\T\\i\\m\\e\\ \\  \\p\\e\\r\\ \\ \\T\\o\\k\\e\\n}}} 

\thinlines

\put(4,67){\makebox(0,0)[tl]{\fbox{\shortstack[l]{%
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharms}}}: $T_1$\\[0.5mm]
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharcs}}}: $T_2$\\[0.5mm]
{\makebox(2,0)[b]{}}
}}}}

\begin{dottedjoin}{0.1}
\thicklines
%\jput(2,59.840){\plotcharms}
\jput(2.5,61.250){\plotcharms}
\jput(3,63.004){\plotcharms}
\jput(3.5,63.973){\plotcharms}
\jput(4,64.602){\plotcharms}
\jput(4.5,64.724){\plotcharms}
\jput(5,65.151){\plotcharms}
\jput(6,64.726){\plotcharms}
\jput(7,64.732){\plotcharms}
\jput(8,64.675){\plotcharms}
\jput(9,64.546){\plotcharms}
\jput(10,64.780){\plotcharms}
\end{dottedjoin}


\begin{drawjoin}
\thicklines
%\jput(2,72.550){\plotcharcs}
\jput(2.5,69.447){\plotcharcs}
\jput(3,66.990){\plotcharcs}
\jput(3.5,65.561){\plotcharcs}
\jput(4,64.583){\plotcharcs}
\jput(4.5,64.224){\plotcharcs}
\jput(5,63.954){\plotcharcs}
\jput(6,64.559){\plotcharcs}
\jput(7,65.097){\plotcharcs}
\jput(8,65.577){\plotcharcs}
\jput(9,65.778){\plotcharcs}
\jput(10,65.402){\plotcharcs}
\end{drawjoin}
%
\end{picture}
\end{center}
\caption{Performance of 2 populations of 50 agents with $n_1=4$ and $w_1=w_2=0.3$\label{hetero-pop1}}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Our results expose the following phenomenon: The two populations obtain
different outcomes from the ones they obtain in the homogeneous case.  More
specifically, for $ 4 \leq n_2 \leq 6$ , the results obtained by the agents
which use $n_2$ are generally better than the results obtained by the ones which
use $n_1$, despite the fact that an homogeneous population which uses $n_1$ gets
better results than an homogeneous population which uses $n_2$.

The phenomenon described above has the following intuitive explanation.  For
$n_2$ in the above-mentioned range, the population which uses $n_2$ is less
``exploring'' (i.e.,\ more ``exploiting'') than the other one, and when it is
left on its own it might not be able to adapt to the changes in a satisfactory
manner.  However, when it is joined with the other population, it gets the
advantages of the experimental activity of agents in that population, without
paying for it. In fact, the more exploring agents, in trying to unload the most
crowded resources, make a service to the other agents as well.

It is worth observing in Figure~\ref{hetero-pop1} that when $n_2$ is low (e.g.,
$n_2 \leq 3$) the agents that use $n_2$ take the role of explorers and lose a
lot, while the agents that use $n_1$ gain from that situation.  Conversely, for
high values of $n_2$ (e.g., $n_2\geq 7$) the performances of the exploiters,
which use $n_2$, deteriorate. This means that if the exploiters are too static,
then they hinder each other, and the explorers can take advantage of it.

For a better understanding of the phenomena involved, we have experimented with
an asymmetric population, composed of one large group and one small one, instead
of two groups of similar size.  Figure~\ref{hetero-pop2} shows the results
obtained using a setting similar to the one above, but where population 1 is
composed of 90 members while population 2 consists of only 10 members.  In this
case, for every value of $n_2 \geq 4$, the exploiters do better than the
explorers. The experiments also show that in this case, the higher $n_2$ is the
better $T_2$ is, i.e.\ the more the exploiters exploit, the more they gain.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[t]
\begin{center}
\unitlength = 1cm

\begin{picture}(12,10)(1,59)

\linethickness{0.4mm}

\put(1,60){\vector(1,0){10}}
\put(1,60){\vector(0,1){8}}

\thicklines

\multiput(1,61)(0,1){7}{\line(1,0){0.1}}
\multiput(2,60)(1,0){9}{\line(0,1){0.1}}
\multiputlist(2,59.7)(1,0){2,3,4,5,6,7,8,9,10} %number along X-axis
\multiputlist(0.7,61)(0,1)[r]{61,62,63,64,65,66,67} %number along Y-axis
\put(6,59){\makebox(0,0) {Exponent of the Randomization Function: $n_2$}}
\put(-.3,64){\makebox(0,0) {\shortstack{%
A\\v\\e\\r\\a\\g\\e\\ \\ \\T\\i\\m\\e\\ \\  \\p\\e\\r\\ \\ \\T\\o\\k\\e\\n}}} 

\thinlines

\put(4,67){\makebox(0,0)[tl]{\fbox{\shortstack[l]{%
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharms}}}: $T_1$\\[0.5mm]
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharcs}}}: $T_2$\\[0.5mm]
{\makebox(2,0)[b]{}}
}}}}

\begin{dottedjoin}{0.1}
\thicklines
%\jput(2,63.890){\plotcharms}
%\jput(2.5,64.003){\plotcharms}
\jput(3,64.371){\plotcharms}
\jput(3.5,64.501){\plotcharms}
\jput(4,64.633){\plotcharms}
\jput(4.5,64.803){\plotcharms}
\jput(5,64.711){\plotcharms}
\jput(6,64.517){\plotcharms}
\jput(7,65.011){\plotcharms}
\jput(8,64.764){\plotcharms}
\jput(9,64.980){\plotcharms}
\jput(10,64.849){\plotcharms}
\end{dottedjoin}


\begin{drawjoin}
\thicklines
%\jput(2,74.511){\plotcharcs}
%\jput(2.5,70.860){\plotcharcs}
\jput(3,68.050){\plotcharcs}
\jput(3.5,65.856){\plotcharcs}
\jput(4,64.787){\plotcharcs}
\jput(4.5,64.250){\plotcharcs}
\jput(5,63.608){\plotcharcs}
\jput(6,63.072){\plotcharcs}
\jput(7,62.360){\plotcharcs}
\jput(8,62.041){\plotcharcs}
\jput(9,61.360){\plotcharcs}
\jput(10,61.150){\plotcharcs}
\end{drawjoin}
%
\end{picture}
\end{center}
\caption{Performance of 2 populations of 90/10 agents with $n_1=4$ and $w_1=w_2=0.3$\label{hetero-pop2}}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The above results suggest that a single agent gets the best results for itself
by being non-cooperative and always adopting the resource with the best
performance (i.e., use BCSR), given that the rest of the agents use an adaptive
(i.e., cooperative) SR\@.  However, if all of the agents are non-cooperative
then all of them will lose.\footnote{This is in fact an illuminating instance of
  the well-known prisoners dilemma \cite{Axelrod}.} In conclusion, the selfish
interest of an agent does not match with the interest of the population.  This
is contrary to results obtained in other basic contexts of multi-agent learning
\cite{STCONV}.

What we have shown is how, for a fixed value of $w$, coexisting populations
adopting different values of $n$ interact. Similar results are obtained when we
fix the value of $n$ and use two different values for $w$.  In such cases, the
agents adopting the lower value of $w$ are in general the winners, as shown in
Figure~\ref{hetero-pop3} for $n_1 = n_2 = 4$ and $w_1=0.3$.  When $w$ is very
low then the corresponding agents get poor results and they are no longer the
winners, as in the case of very high $n$ in Figure~\ref{hetero-pop1}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[t]
\begin{center}
\unitlength = 1cm

\begin{picture}(12,10)(1,59)

\linethickness{0.4mm}

\put(1,60){\vector(1,0){10}}
\put(1,60){\vector(0,1){8}}

\thicklines

\multiput(1,61)(0,1){7}{\line(1,0){0.1}}
\multiput(2,60)(1,0){9}{\line(0,1){0.1}}
\multiputlist(2,59.7)(1,0){0.01,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1} %number along X-axis
\multiputlist(0.7,61)(0,1)[r]{61,62,63,64,65,66,67} %number along Y-axis
\put(6,59){\makebox(0,0) {Weight of the estimator parameter ($w_2$)}}
\put(-.3,64){\makebox(0,0) {\shortstack{%
A\\v\\e\\r\\a\\g\\e\\ \\ \\T\\i\\m\\e\\ \\  \\p\\e\\r\\ \\ \\T\\o\\k\\e\\n}}} 

\thinlines

\put(4,67){\makebox(0,0)[tl]{\fbox{\shortstack[l]{%
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharms}}}: $T_1$\\[0.5mm]
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharcs}}}: $T_2$\\[0.5mm]
{\makebox(2,0)[b]{}}
}}}}

\begin{dottedjoin}{0.1}
\thicklines
\jput(2,64.515){\plotcharms} 	%0.01
\jput(3,65.001){\plotcharms} 	%0.1
\jput(4,65.010){\plotcharms}	%0.2
\jput(5,64.582){\plotcharms}	%0.3
\jput(6,64.363){\plotcharms}	%0.4
\jput(7,64.086){\plotcharms}	%0.5
\jput(8,63.764){\plotcharms}	%0.6
\jput(9,63.802){\plotcharms}	%0.7
\jput(10,62.925){\plotcharms}	%0.8
\jput(11,62.910){\plotcharms}	%0.9
\jput(12,62.851){\plotcharms}	%1
\end{dottedjoin}


\begin{drawjoin}
\thicklines
\jput(2,66.759){\plotcharcs}	%0.01
\jput(3,64.716){\plotcharcs}	%0.1
\jput(4,64.790){\plotcharcs}	%0.2
\jput(5,64.608){\plotcharcs}	%0.3
\jput(6,64.620){\plotcharcs}	%0.4
\jput(7,65.144){\plotcharcs}	%0.5
\jput(8,65.309){\plotcharcs}	%0.6
\jput(9,65.734){\plotcharcs}	%0.7
\jput(10,66.356){\plotcharcs}	%0.8
\jput(11,66.493){\plotcharcs}	%0.9
\jput(12,66.573){\plotcharcs}	%1
\end{drawjoin}
%
\end{picture}
\end{center}
\caption{Performance of 2 populations of 50 agents with $n_1=n_2=4$ and $w_1=0.3$\label{hetero-pop3}}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Another interesting phenomenon is obtained when confronting adaptive agents with
{\em load-querying\/} agents. Load-querying agents are agents who are able to
consult the resources about where they should submit their jobs.  A
load-querying agent will submit its job to the most unloaded resource at the
given point.  When confronting load-querying agents with adaptive ones, the
results obtained by the adaptive agents are obviously worse than the results
obtained by the load-querying ones, but are better than the results obtained by
a complete population of adaptive agents.  This means that load-querying agents
do not play the role of ``parasites'', as the above-mentioned ``exploiters'';
the load-querying agents help in maintaining the load balancing among the
resources, and therefore help the rest of the agents.  Another result we obtain
is that agents who adopt deterministic SRs may behave as parasites and worsen
the performance of adaptive agents.

These assertions are supported by the experiments described in
Figure~\ref{table4}, where a population of 90 agents, each of which uses an
adaptive SR with parameters $(n,w)$, is faced with a minority of 10 agents which
use different SRs, as stated above.  In particular, in the four cases we
consider, the minority behaves in the following ways: $(i)$ they choose the
resource which gave best results, $(ii)$ they are very conservative in updating
the history, $(iii)$ they are load-querying agents, $(iiii)$ they all use
deterministically the resource with capacity 40 (in our basic experimental
setting).

\begin{figure}
\begin{center}
\begin{tabular}{|c|c||c|c|}\hline
	90 agents 	& 10 agents	&	$T_1$	&	$T_2$	\\  \hline\hline
	(.3,4)		& (.3,20)	&	65.161	&	59.713	\\  \hline
	(.3,4)		& (.1,4)	&	64.630	&	63.818	\\  \hline
	(.3,4)		& Load-querying	&	62.320	&	47.236	\\  \hline
	(.3,4)		& Using Res. 0	&	65.499	&	55.818	\\  \hline
\end{tabular}
\end{center}
\caption{Performance of 2 populations of 90/10 agents with various SRs
\label{table4} }
\end{figure}

\section{Communication among Agents}\label{sec-communication}

Up to this point, we have assumed that there is no direct communication among
the agents. The motivation for this was that we considered situations in which
there were absolutely no transmission channels and protocols. This assumption is
in agreement with the idea of multi-agent reinforcement learning. In systems
where massive communication is feasible we are not so much concerned with
multiple agent adaptation, and the problem reduces to supplying satisfactory
communication mechanisms.  Multi-agent reinforcement learning is most
interesting where real life forces agents to act without a-priori arranged
communication channels and we must rely on action-feedback mechanisms.  However,
it is of interest to understand the effects of communication on the system
efficiency \cite<as in>{STCONV,Tan93}, where the agents are augmented with some
sort of communication capabilities.  Our study of this extension led to some
illuminating results, which we will now present.

We assume that each agent can communicate only with some of the other agents,
which we call its {\em neighbors}. We therefore consider a relation {\em
  neighbor-of\/} and assume it is reflexive, symmetric and transitive. As a
consequence, the relation neighbor-of partitions the population into equivalence
classes, that we call {\em neighborhoods}.

The form of communication we consider is based on the idea that the efficiency
estimators of agents within a neighborhood will be shared among them when a
decision is made (i.e., when an agent chooses a resource).  The reader should
notice that this is a naive form of communication and that more sophisticated
types of communication are possible. However, the above form of communication is
most natural when we concentrate on agents that update their behavior based only
on past information.  In particular, this type of communication is similar to
the ones used in the above-mentioned work on incorporating communication into
the framework of multi-agent reinforcement learning.

We suppose that different SRs may be used by different agents in the same
population, but we impose the condition that within a single neighborhood, the
same SR is used by all its members.

We also assume that each agent keeps its own history and updates it by itself
in the usual way. The choice, instead, is based not only on the agent efficiency
estimator, but on the average of the efficiency estimators of the agents in the
corresponding neighborhood.  Such average is called the {\em neighborhood
  efficiency estimator}.  The neighborhood efficiency estimator has no physical
storage: Its value is recalculated each time a member needs it.

In order to compare the behavior of communicating agents and non-communicating
ones, we assume that in a single population there might be, aside from the
neighborhoods defined above, also some neighborhoods that do not allow the
sharing of efficiency estimators among its members. The members of these
neighborhoods behave as described in the previous sections, i.e., each agent
relies only on its own history. The only thing that is common among the members
of such a neighborhood is that all its members use the same SR.

We call {\em communicating neighborhood\/} (CN), a neighborhood in which the
efficiency estimators are shared when a decision is taken and {\em
  non-communicating neighborhood\/} (NCN), a neighborhood in which this is not
done.

The first set of experiments we ran, regards a population composed of only CNs,
all of the same size. In particular, we considered CNs of various sizes,
starting from 50 CNs of size 2, going to 5 CNs of size 20. The load profile
exploited is the random load change defined in Subsection~\ref{sec-random-load},
the value of $w$ is taken to be $0.3$, and $n$ is taken to have various values.
The results obtained are shown in Figure~\ref{communication-figure}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}
\begin{center}
\unitlength = 1cm
\begin{picture}(12,10)(1,63)

\linethickness{0.4mm}
\put(1,64){\vector(1,0){10}}
\put(1,64){\vector(0,1){8}}

\thicklines

\multiput(1,65)(0,1){7}{\line(1,0){0.1}}
\multiput(2,64)(1,0){9}{\line(0,1){0.1}}
\multiputlist(2,63.7)(1,0){2,3,4,5,6,7,8,9,10} %number along X-axis
\multiputlist(0.7,65)(0,1)[r]{65,66,67,68,69,70,71} %number along Y-axis
\put(6,63){\makebox(0,0) {Exponent of the Randomization Function: $n$}}
\put(-.3,68){\makebox(0,0) {\shortstack{%
A\\v\\e\\r\\a\\g\\e\\ \\ \\T\\i\\m\\e\\ \\  \\p\\e\\r\\ \\ \\T\\o\\k\\e\\n}}} 

\thinlines

\put(8,67){\makebox(0,0)[tl]{\fbox{\shortstack[l]{%
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharms}}}: 5 CNs of 20 agents\\[0.5mm]
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharscs}}}: 20 CNs of 5 agents\\[0.5mm]
{\makebox(0.4,0.3)[lb]{\put(0.2,0.1){\plotcharcs}}}: 50 CNs of 2 agents\\[0.5mm]
{\makebox(2,0)[b]{}}
}}}}

\begin{dottedjoin}{0.1}
\thicklines
\jput(2,70.262){\plotcharms}
\jput(2.5,68.092){\plotcharms}
\jput(3,68.063){\plotcharms}
\jput(3.5,69.094){\plotcharms}
\jput(4,70.212){\plotcharms}
\jput(4.5,70.142){\plotcharms}
\jput(5,70.836){\plotcharms}
\jput(6,71.966){\plotcharms}
\jput(7,71.143){\plotcharms}
\jput(8,72.384){\plotcharms}
\jput(9,70.409){\plotcharms}
\jput(10,71.475){\plotcharms}
\end{dottedjoin}

\begin{dashjoin}{0.1}
\thicklines
\jput(2,70.344){\plotcharscs}
\jput(2.5,67.876){\plotcharscs}
\jput(3,66.488){\plotcharscs}
\jput(3.5,66.915){\plotcharscs}
\jput(4,66.360){\plotcharscs}
\jput(4.5,67.025){\plotcharscs}
\jput(5,67.205){\plotcharscs}
\jput(6,67.398){\plotcharscs}
\jput(7,67.937){\plotcharscs}
\jput(8,69.191){\plotcharscs}
\jput(9,70.620){\plotcharscs}
\jput(10,71.051){\plotcharscs}
\end{dashjoin}

\begin{drawjoin}
\thicklines
\jput(2,69.760){\plotcharcs}
\jput(2.5,66.974){\plotcharcs}
\jput(3,65.810){\plotcharcs}
\jput(3.5,65.619){\plotcharcs}
\jput(4,65.201){\plotcharcs}
\jput(4.5,65.358){\plotcharcs}
\jput(5,65.412){\plotcharcs}
\jput(6,66.142){\plotcharcs}
\jput(7,66.879){\plotcharcs}
\jput(8,68.486){\plotcharcs}
\jput(9,69.378){\plotcharcs}
\jput(10,70.532){\plotcharcs}
\end{drawjoin}
%
\end{picture}
\end{center}
\caption{Performance of the adaptive Selection Rules for random 
load profile for communicating agents\label{communication-figure}}
\end{figure}

The results show that such communicating populations do not get good results.
The reason for this is that members of a CN tend to be very conservative, in the
sense that they mostly use the best resource. In fact, since they rely on an
average of several agents, the picture they have of the system tends to be much
more static. In particular, the bigger is the CN the more conservative its
members tend to be. For example, consider the values of ($n,w$) that give the best
results for non-communicating agents, those values give quite bad performance
for CNs since they turn to be too conservative.

Using more adaptive values of ($n,w$), the behavior of a communicating
population improves and reaches a performance that is just slightly worse than
the performance of a non-communicating population. Tuning the parameters using a
finer grain, it is possible to obtain a performance that is equal to the one
obtained by a non-communicating population. However, it seems clear that no
obvious gain is achieved from this form of communication capability. The
intuitive explanation is that there are two opposite effects caused by the
communication.  On the one hand, the agents get a fairer picture of the system
which prevents them from using bad resources and therefore getting bad
performance. On the other hand, since all of the agents in a CN have a
``better'' picture of the system, they all tend to use the best resources and
thus they all compete for them. In fact, the agents behave selfishly and their
selfish interest may not agree with the interest of the population as a whole.

The interesting message that we get is that the fact that some agents may have a
``distorted'' picture of the system (which is typical for non-communicating
populations), turns out to be an advantage for the population as a whole.

Sharing the data among agents leads to poorer performances also because in this
case the agents have common views of loads and target jobs toward the same
(lightly loaded) resources, which quickly become overloaded. In order to
profitably use the shared data, we should allow for some form of reasoning about
the fact that the data is shared.  This problem however is out of the scope of
this paper \cite<see e.g.,>{Less91}.

In order to understand the behavior of the system when CNs and NCNs face each
other, we consider an NCN of 80 agents together with a set of CNs of equal size,
for different values of that size. The results of the corresponding experiments
are shown in Figure~\ref{cn-vs-nn}. The members of the CNs, being more inclined
to use the best resources, behave as parasites in the sense explained in
Section~\ref{sec-heterogeneity}. They exploit the adaptiveness of the rest of
the population to obtain good performance from the best resources.  For this
reason they get better results than the rest of the population, as shown by the
experimental results.

It it interesting to observe that when the NCN uses a very conservative
selection rule, the CNs obtain even better results.  The intuitive explanation
for this behavior is that although all groups, i.e.,\ both the communicating
ones and the one with high value of $n$, tend to be conservative, the
communicating ones ``win'' because they are conservative in a more ``clever''
way, that is making use of a better picture of the situation.

\begin{figure}
\begin{center}
\begin{tabular}{|c|c||c|c|}\hline
	80 agents  	& 20 agents	&	$T_1$	&	$T_2$	\\  \hline\hline
	(.3,4)	1 NCN	& (.3,4) 1 CN	& 65.287	& 	63.054	\\  \hline
	(.3,4) 1 NCN	& (.3,4) 2 CNs	& 65.069	&	63.307	\\  \hline
	(.3,4) 1 NCN	& (.3,4) 5 CNs	& 65.091	&	62.809	\\  \hline
	(.3,4) 1 NCN	& (.3,4) 10 CNs	& 64.895	&	63.840	\\  \hline\hline
	(.3,10) 1 NCN	& (.3,4) 1 CN	& 68.419	&	60.018	\\  \hline
	(.3,10) 1 NCN	& (.3,4) 2 CNs	& 68.319	&	59.512	\\  \hline
	(.3,10)	1 NCN	& (.3,4) 5 CNs	& 68.529	&	60.674	\\  \hline
	(.3,10) 1 NCN	& (.3,4) 10 CNs	& 68.351	&	61.711	\\  \hline
\end{tabular}
\end{center}
\caption{Performance of CNs and NCNs together\label{cn-vs-nn} }
\end{figure}

The conclusion we draw in this section is that the proposed form of
communication between agents may not provide useful means to improve the
performance of a population in our setting.  However, we do not claim that
communication between agents is completely useless.  Nevertheless, we have
observed that it does not provide a straightforward significant improvement.
Our results support the claim that the sole past history of an agent is a
reasonable information on which to base its decision, assuming we do not
consider available any kind of real-time information (e.g.,\ current load of the
resources).


\section{Discussion} \label{discussion}

The previous sections were devoted to a report on our experimental study.  We
now synthesize our observations in view of our motivation, as discussed in
Sections~\ref{intro} and~\ref{general-setting}.

As we mentioned, our model is a general model where active autonomous agents
have to select among several resources in a dynamic fashion and based on local
information. The fact that the agents use only local information makes the
possibility of efficient load-balancing questionable. However, we showed that
adaptive load balancing based on purely local feedback is a feasible task.
Hence, our results are complementary to the ones obtained in the distributed
computer systems literature. As \citeA{MirStan} put it: ``\ldots what is
significant about our work is that we have illustrated that is possible to
design a learning controller that is able to dynamically acquire relevant job
scheduling information by a process of trial and error, and use that information
to provide good performance.'' The study presented in our paper supplies a
complementary contribution where we are able to show that useful adaptive load
balancing can be obtained using {\em purely local information\/} and in the
framework of a general organizational-theoretic model.

In our study we identified various parameters of the adaptive process and
investigated how they affect the efficiency of adaptive load balancing. This
part of our study supplies useful guidelines for a systems designer who may
force all the agents to work based on a common selection rule.  Our
observations, although somewhat related to previous observations made in other
contexts and models \cite{HuHo}, enable to demonstrate aspects of purely local
adaptive behavior in a non-trivial model.

Our results about the disagreement between selfish interest of agents and the
common interest of the population is in sharp contrast to previous work on
multi-agent learning \cite{STCONV,STCOLEARN} and to the dynamic programming
perspective of earlier work on distributed systems \cite{BerTsi}. Moreover, we
explore how the interaction between different agent types affects the system's
efficiency as well as the individual agent's efficiency. The related results can
be also interpreted as guidelines for a designer who may have only partial
control of a system.

The synthesis of the above observations teaches us about adaptive load balancing
when one adopts a reinforcement learning perspective where the agents rely only
on their local information and activity.  An additional step we performed
attempts to bridge some of the gap between our local view and previous work on
adaptive load balancing by communicating agents, whose decisions may be
controlled by learning automata or by other means. We therefore rule out the
possibility of communication about the current status of resources and of joint
decision-making, but enable a limited sharing of previous history. We show that
such limited communication may not help, and even deteriorate system efficiency.
This leaves us with a major gap between previous work where communication among
agents is the basic tool for adaptive load balancing and our work.  Much is
left to be done in attempting to bridge this gap. We see this as a major
challenge for further research.

\section{Related Work}\label{related-work}

In Section~\ref{general-setting} we mentioned some related work in the field of
distributed computer systems \cite{MirStan,BilPas,GloPas,MirTowStan,Zhou,ELZ86}.
A typical example of such work is the paper by \citeA{MirStan}.  In this work
learning automata are used in order to decide on the action to be taken.
However, the suggested algorithms heavily rely on communication and information
sharing among agents. This is in sharp contrast to our work. In addition, there
are differences between the type of model we use and the model presented in the
above-mentioned work and in other work on distributed computer systems.

Applications of learning algorithms to load balancing problems are given by
\citeA{Mehr92,MeWa93}. However, in that work as well, the agents (sites, in the
authors' terminology) have the ability to communicate and to exchange workload
values, even though such values are subject to uncertainty due to delays.  In
addition, differently from our work, the learning activity is done off-line. In
particular, in the learning phase the whole system is dedicated to the
acquisition of workload indices. Such load indices are then used in the running
phase as threshold values for job migration between different sites.

In spite of the differences, there are some similarities between our work and the
above-mentioned work. One important similarity is the use of learning
procedures.  This is in difference from the more classical work on parallel and
distributed computation \cite{BerTsi} which applies numerical and iterative
methods to the solution of problems in network flow and parallel computing.
Other similarities are related to our study of the division of the society into
groups. This somewhat resembles work on group formation \cite{BilPas} in
distributed computer systems.  The information sharing we allow in
Section~\ref{sec-communication} is similar to the limited communication
discussed by \citeA{Tan93}.  In the classification of load-balancing problems
given by \citeA{Ferr85}, our work falls into the category of {\em
  load-independent and non-preemptive pure load-balancing}.  The problems we
investigate can be also seen as {\em sender-initiated\/} problems, although in
our case the sender is the agent and not the (overloaded) resource.

One may wonder how our work differs from other work on adaptive load balancing
in Operations Research (OR) \cite<e.g., queuing theory>{BDKLK90}.  Indeed, there
are some commonalities. In both OR and our work, individual decisions are made
locally, based on information obtained dynamically during runtime. And in both
cases the systems constructed are sufficiently complex that the most interesting
results tend to be obtained experimentally. However, a careful look at the
relevant OR literature reveals an essential difference between the perspective
of OR on the topic and our reinforcement-learning perspective: OR permits free
communication within the system, and thus there is no significant element of
uncertainty in that framework. In particular, the issue of exploration versus
exploitation, which lies at the heart of our approach, is completely absent from
work in OR.

Some work on adaptive load balancing and related topics has been carried out
also by the Artificial Intelligence community \cite<see
e.g.,>{Koso93,GmDW91,Well93}. This work too, however, tends to be based on some
form of communication among the agents, whereas in our case the load balancing
is obtained purely from a learning activity.

This article is related to our previous work on {\em co-learning}
\cite{STCONV,STCOLEARN}.  The framework of co-learning is a framework for
multi-agent learning, which differs from other frameworks discussed in
multi-agent reinforcement learning \cite{NarTha,Tan93,YanStei93,SeSH94} due to
the fact that it considers the case of {\em stochastic\/} interactions among
{\em subsets\/} of the agents, where there is purely local feedback revealed to
the agents based on these interactions.  The framework of co-learning is similar
in some respects to a number of dynamic frameworks in economics
\cite{KanMaiRob91}, physics \cite{KinSnell}, computational ecologies
\cite{HuHo}, and biology \cite{AltFel}.  Our study of adaptive load balancing
can be treated as a study in co-learning.

Relevant to our work is also the literature in the field of {\em Learning
  Automata\/} \cite<see>{NarTha}. In fact, an agent in our setting can be seen
as a learning automaton.  Therefore, one may hope that theoretical results on
interconnected automata and N-player games \cite<see
e.g.,>{ElFa80,AbFa83,NaWh83,WhNa85} could be imported in our framework.
Unfortunately, due to the stochastic nature of job submissions (i.e., agent
interactions) and the real-valued (instead of binary) feedback, our problem does
not fit completely in to the theoretical framework of learning automata. Hence,
results concerning optimality, convergence or expediency of learning rules such
as Linear Reward-Penalty or Linear Reward-Inaction, can not be easily adapted
into our setting.  The fact that we use a stochastic model for the interaction
among agents, makes our work closely related to the above-mentioned work on
co-learning.  Nevertheless, our work is largely influenced by learning automata
theory and our resource-selection rules closely resemble reinforcement schemes
for learning automata.

Last but not least, our work is related to work applying organization theory and
management techniques to the field of Distributed AI \cite{Fox,Malone,DLC}.  Our
model is closely related to models of decision-making in management and
organization theory \cite<e.g.,>{Malone} and applies a reinforcement learning
perspective to that context.  This makes our work related to psychological
models of decision-making \cite{Arthur}.

\section{Summary}\label{conclusions}

This work applies the idea of multi-agent reinforcement learning to the problem
of load balancing in a loosely-coupled multi-agent system, in which agents need
to adapt to one another as well as to a changing environment.  We have
demonstrated that adaptive behavior is useful for efficient load balancing in
this context and identified a pair of parameters that affect that efficiency in
a non-trivial fashion.  Each parameter, holding the other parameter to be fixed,
gives rise to a certain tradeoff, and the two parameters interplay in a
non-trivial and illuminating way.  We have also exposed illuminating results
regarding heterogeneous populations, such as how a group of parasitic less
adaptive agents can gain from the flexibility of other agents. In addition, we
showed that naive use of communication may not improve, and might even
deteriorate, the system efficiency.

\section*{Acknowledgments}
We thank the anonymous reviewers and Steve Minton, whose stimulating comments
helped us in improving on an earlier version of this paper.

%\bibliography{paper}
%\bibliographystyle{theapa}

\begin{thebibliography}{}

\bibitem[\protect\BCAY{Abdel-{F}attah}{Abdel-{F}attah}{1983}]{AbFa83}
Abdel-{F}attah, Y.~M. \BBOP1983\BBCP.
\newblock \BBOQ Stochastic automata modeling of certain problems of collective
  behavior\BBCQ\
\newblock {\Bem {IEEE} Transactions on Systems, Man, and Cybernetics}, {\Bem
  13\/}(3), 236--241.

\bibitem[\protect\BCAY{Altenberg \BBA\ Feldman}{Altenberg \BBA\
  Feldman}{1987}]{AltFel}
Altenberg, L.\BBACOMMA\  \BBA\ Feldman, M.~W. \BBOP1987\BBCP.
\newblock \BBOQ Selection, generalized transmission, and the evolution of
  modifier genes. {I}. {T}he reduction principle\BBCQ\
\newblock {\Bem Genetics}, {\Bem 117}, 559--572.

\bibitem[\protect\BCAY{Arthur}{Arthur}{1994}]{Arthur}
Arthur, W. \BBOP1994\BBCP.
\newblock \BBOQ Inductive reasoning, bounded rationality and the bar
  problem\BBCQ\
\newblock \BTR\ 94-03-014 (working paper), Santa Fe Institute.
\newblock Appeared also in American Economic Review 84.

\bibitem[\protect\BCAY{Axelrod}{Axelrod}{1984}]{Axelrod}
Axelrod, R. \BBOP1984\BBCP.
\newblock {\Bem The Evolution of Cooperation}.
\newblock New York: Basic Books.

\bibitem[\protect\BCAY{Bertsekas \BBA\ Tsitsiklis}{Bertsekas \BBA\
  Tsitsiklis}{1989}]{BerTsi}
Bertsekas, D.\BBACOMMA\  \BBA\ Tsitsiklis, J. \BBOP1989\BBCP.
\newblock {\Bem Parallel and Distributed Computation: Numerical Methods}.
\newblock Prentice Hall.

\bibitem[\protect\BCAY{Billard \BBA\ Pasquale}{Billard \BBA\
  Pasquale}{1993}]{BilPas}
Billard, E.\BBACOMMA\  \BBA\ Pasquale, J. \BBOP1993\BBCP.
\newblock \BBOQ Effects of delayed communication in dynamic group
  formation\BBCQ\
\newblock {\Bem {IEEE} Transactions on Systems, Man, and Cybernetics}, {\Bem
  23\/}(5), 1265--1275.

\bibitem[\protect\BCAY{Blackburn}{Blackburn}{1936}]{Blackburn}
Blackburn, J.~M. \BBOP1936\BBCP.
\newblock \BBOQ Acquisition to skill: An analysis of learning curves\BBCQ\
\newblock IHRB Report No. 73.

\bibitem[\protect\BCAY{Bond \BBA\ Gasser}{Bond \BBA\ Gasser}{1988}]{BG}
Bond, A.~H.\BBACOMMA\  \BBA\ Gasser, L. \BBOP1988\BBCP.
\newblock {\Bem Readings in Distributed Artificial Intelligence}.
\newblock Ablex Publishing Corporation.

\bibitem[\protect\BCAY{Bonomi, Doshi, Kaufmann, Lee, \BBA\ Kumar}{Bonomi
  et~al.}{1990}]{BDKLK90}
Bonomi, F., Doshi, B., Kaufmann, J., Lee, T., \BBA\ Kumar, A. \BBOP1990\BBCP.
\newblock \BBOQ A case study of adaptive load balancing algorithm\BBCQ\
\newblock {\Bem Queuing Systems}, {\Bem 7}, 23--49.

\bibitem[\protect\BCAY{Durfee, Lesser, \BBA\ Corkill}{Durfee
  et~al.}{1987}]{DLC}
Durfee, E.~H., Lesser, V.~R., \BBA\ Corkill, D.~D. \BBOP1987\BBCP.
\newblock \BBOQ Coherent cooperation among communicating problem solvers\BBCQ\
\newblock {\Bem IEEE Transactions on Computers}, {\Bem 36}, 1275--1291.

\bibitem[\protect\BCAY{Eager, Lazowska, \BBA\ Zahorjan}{Eager
  et~al.}{1986}]{ELZ86}
Eager, D., Lazowska, E., \BBA\ Zahorjan, J. \BBOP1986\BBCP.
\newblock \BBOQ Adaptive load sharing in homogeneous distributed systems\BBCQ\
\newblock {\Bem IEEE Transactions on Software Engineering}, {\Bem 12\/}(5),
  662--675.

\bibitem[\protect\BCAY{El-{F}attah}{El-{F}attah}{1980}]{ElFa80}
El-{F}attah, Y.~M. \BBOP1980\BBCP.
\newblock \BBOQ Stochastic automata modeling of certain problems of collective
  behavior\BBCQ\
\newblock {\Bem {IEEE} Transactions on Systems, Man, and Cybernetics}, {\Bem
  10\/}(6), 304--314.

\bibitem[\protect\BCAY{Ferrari}{Ferrari}{1985}]{Ferr85}
Ferrari, D. \BBOP1985\BBCP.
\newblock \BBOQ A study of load indices for load balancing schemes\BBCQ\
\newblock \BTR\ Ucb/CSD 86/262, Computer Science Division (EECS), Univ. of
  California, Berkeley.

\bibitem[\protect\BCAY{Ferrari, Serazzi, \BBA\ Zeigner}{Ferrari
  et~al.}{1983}]{FerSerZei}
Ferrari, D., Serazzi, G., \BBA\ Zeigner, A. \BBOP1983\BBCP.
\newblock {\Bem Measurement and Tuning of Computer Systems}.
\newblock Prentice Hall.

\bibitem[\protect\BCAY{Fox}{Fox}{1981}]{Fox}
Fox, M.~S. \BBOP1981\BBCP.
\newblock \BBOQ An organizational view of distributed systems\BBCQ\
\newblock {\Bem {IEEE} Transactions on Systems, Man, and Cybernetics}, {\Bem
  11}, 70--80.

\bibitem[\protect\BCAY{Glockner \BBA\ Pasquale}{Glockner \BBA\
  Pasquale}{1993}]{GloPas}
Glockner, A.\BBACOMMA\  \BBA\ Pasquale, J. \BBOP1993\BBCP.
\newblock \BBOQ Coadaptive behavior in a simple distributed job scheduling
  system\BBCQ\
\newblock {\Bem IEEE Transactions on Systems, Man, and Cybernetics}, {\Bem
  23\/}(3), 902--907.

\bibitem[\protect\BCAY{Gmytrasiewicz, Durfee, \BBA\ Wehe}{Gmytrasiewicz
  et~al.}{1991}]{GmDW91}
Gmytrasiewicz, P., Durfee, E., \BBA\ Wehe, D. \BBOP1991\BBCP.
\newblock \BBOQ The utility of communication in coordinating intelligent
  agents\BBCQ\
\newblock In {\Bem Proc.\ of the 9th Nat.\ Conf.\ on Artificial Intelligence
  (AAAI-91)}, \BPGS\ 166--172.

\bibitem[\protect\BCAY{Huberman \BBA\ Hogg}{Huberman \BBA\ Hogg}{1988}]{HuHo}
Huberman, B.~A.\BBACOMMA\  \BBA\ Hogg, T. \BBOP1988\BBCP.
\newblock \BBOQ The behavior of computational ecologies\BBCQ\
\newblock In Huberman, B.~A.\BED, {\Bem The Ecology of Computation}. Elsevier
  Science.

\bibitem[\protect\BCAY{Kaelbling}{Kaelbling}{1993}]{Kaelbling}
Kaelbling, L. \BBOP1993\BBCP.
\newblock {\Bem Learning in Embedded Systems}.
\newblock MIT Press.

\bibitem[\protect\BCAY{Kandori, Mailath, \BBA\ Rob}{Kandori
  et~al.}{1991}]{KanMaiRob91}
Kandori, M., Mailath, G., \BBA\ Rob, R. \BBOP1991\BBCP.
\newblock \BBOQ Learning, mutation and long equilibria in games\BBCQ\
\newblock Mimeo. University of Pennsylvania.

\bibitem[\protect\BCAY{Kinderman \BBA\ Snell}{Kinderman \BBA\
  Snell}{1980}]{KinSnell}
Kinderman, R.\BBACOMMA\  \BBA\ Snell, S.~L. \BBOP1980\BBCP.
\newblock {\Bem Markov Random Fields and their Applications}.
\newblock American Mathematical Society.

\bibitem[\protect\BCAY{Kosoresow}{Kosoresow}{1993}]{Koso93}
Kosoresow, A.~P. \BBOP1993\BBCP.
\newblock \BBOQ A fast first-cut protocol for agent coordination\BBCQ\
\newblock In {\Bem Proc.\ of the 11th Nat.\ Conf.\ on Artificial Intelligence
  (AAAI-93)}, \BPGS\ 237--242.

\bibitem[\protect\BCAY{Kraus \BBA\ Wilkenfeld}{Kraus \BBA\
  Wilkenfeld}{1991}]{KW}
Kraus, S.\BBACOMMA\  \BBA\ Wilkenfeld, J. \BBOP1991\BBCP.
\newblock \BBOQ The function of time in cooperative negotiations\BBCQ\
\newblock In {\Bem Proc.\ of the 9th Nat.\ Conf.\ on Artificial Intelligence
  (AAAI-91)}, \BPGS\ 179--184.

\bibitem[\protect\BCAY{Lesser}{Lesser}{1991}]{Less91}
Lesser, V.~R. \BBOP1991\BBCP.
\newblock \BBOQ A retrospective view of {FA/C} distributed problem
  solving\BBCQ\
\newblock {\Bem {IEEE} Transactions on Systems, Man, and Cybernetics}, {\Bem
  21\/}(6), 1347--1362.

\bibitem[\protect\BCAY{Malone}{Malone}{1987}]{Malone}
Malone, T.~W. \BBOP1987\BBCP.
\newblock \BBOQ Modeling coordination in organizations and markets\BBCQ\
\newblock {\Bem Management Science}, {\Bem 33\/}(10), 1317--1332.

\bibitem[\protect\BCAY{Mehra}{Mehra}{1992}]{Mehr92}
Mehra, P. \BBOP1992\BBCP.
\newblock {\Bem Automated Learning of Load-Balancing Strategies For A
  Distributed Computer System}.
\newblock Ph.D.\ thesis, Department of Electrical and Computer Engineering,
  University of Illinois at Urbana-Champaign.

\bibitem[\protect\BCAY{Mehra \BBA\ Wah}{Mehra \BBA\ Wah}{1993}]{MeWa93}
Mehra, P.\BBACOMMA\  \BBA\ Wah, B.~W. \BBOP1993\BBCP.
\newblock \BBOQ Population-based learning of load balancing policies for a
  distributed computer system\BBCQ\
\newblock In {\Bem Proceedings of Computing in Aerospace 9 Conference, AIAA},
  \BPGS\ 1120--1130.

\bibitem[\protect\BCAY{Mirchandaney \BBA\ Stankovic}{Mirchandaney \BBA\
  Stankovic}{1986}]{MirStan}
Mirchandaney, R.\BBACOMMA\  \BBA\ Stankovic, J. \BBOP1986\BBCP.
\newblock \BBOQ Using stochastic learning automata for job scheduling in
  distributed processing systems\BBCQ\
\newblock {\Bem Journal of Parallel and Distributed Computing}, {\Bem 3},
  527--552.

\bibitem[\protect\BCAY{Mirchandaney, Towsley, \BBA\ Stankovic}{Mirchandaney
  et~al.}{1989}]{MirTowStan}
Mirchandaney, R., Towsley, D., \BBA\ Stankovic, J. \BBOP1989\BBCP.
\newblock \BBOQ Analysis of the effects of delays on load sharing\BBCQ\
\newblock {\Bem IEEE Transactions on Computers}, {\Bem 38\/}(11), 1513--1525.

\bibitem[\protect\BCAY{Narendra \BBA\ Thathachar}{Narendra \BBA\
  Thathachar}{1989}]{NarTha}
Narendra, K.\BBACOMMA\  \BBA\ Thathachar, M. A.~L. \BBOP1989\BBCP.
\newblock {\Bem Learning Automata: An Introduction}.
\newblock Prentice Hall.

\bibitem[\protect\BCAY{Narendra \BBA\ Wheeler~Jr.}{Narendra \BBA\
  Wheeler~Jr.}{1983}]{NaWh83}
Narendra, K.\BBACOMMA\  \BBA\ Wheeler~Jr., R.~M. \BBOP1983\BBCP.
\newblock \BBOQ An {N}-player sequential stochastic game with identical
  payoffs\BBCQ\
\newblock {\Bem {IEEE} Transactions on Systems, Man, and Cybernetics}, {\Bem
  13\/}(6), 1154--1158.

\bibitem[\protect\BCAY{Pulidas, Towsley, \BBA\ Stankovic}{Pulidas
  et~al.}{1988}]{PuTS88}
Pulidas, S., Towsley, D., \BBA\ Stankovic, J. \BBOP1988\BBCP.
\newblock \BBOQ Imbedding gradient estimators in load balancing
  algorithms\BBCQ\
\newblock In {\Bem Proceedings of the 8th International Conference on
  Distributed Computer Systems, IEEE}, \BPGS\ 482--489.

\bibitem[\protect\BCAY{Sen, Sekaran, \BBA\ Hale}{Sen et~al.}{1994}]{SeSH94}
Sen, S., Sekaran, M., \BBA\ Hale, J. \BBOP1994\BBCP.
\newblock \BBOQ Learning to coordinate without sharing information\BBCQ\
\newblock In {\Bem Proc.\ of the 12th Nat.\ Conf.\ on Artificial Intelligence
  (AAAI-94)}.

\bibitem[\protect\BCAY{Shoham \BBA\ Tennenholtz}{Shoham \BBA\
  Tennenholtz}{1992}]{STCONV}
Shoham, Y.\BBACOMMA\  \BBA\ Tennenholtz, M. \BBOP1992\BBCP.
\newblock \BBOQ Emergent conventions in multi-agent systems: initial
  experimental results and observations\BBCQ\
\newblock In {\Bem Proc. of the 3rd Int.\ Conf.\ on Principles of Knowledge
  Representation and Reasoning (KR-92)}, \BPGS\ 225--231.

\bibitem[\protect\BCAY{Shoham \BBA\ Tennenholtz}{Shoham \BBA\
  Tennenholtz}{1994}]{STCOLEARN}
Shoham, Y.\BBACOMMA\  \BBA\ Tennenholtz, M. \BBOP1994\BBCP.
\newblock \BBOQ Co-learning and the evolution of social activity\BBCQ\
\newblock \BTR\ STAN-CS-TR-94-1511, Dept. of Computer Science, Stanford
  University.

\bibitem[\protect\BCAY{Sutton}{Sutton}{1992}]{ReadReinfor}
Sutton, R. \BBOP1992\BBCP.
\newblock \BBOQ Special issue on reinforcement learning\BBCQ\
\newblock {\Bem Machine Learning}, {\Bem 8\/}(3--4).

\bibitem[\protect\BCAY{Tan}{Tan}{1993}]{Tan93}
Tan, M. \BBOP1993\BBCP.
\newblock \BBOQ Multi-agent reinforcement learning: Independent vs. cooperative
  agents\BBCQ\
\newblock In {\Bem Proceedings of the 10th International Conference on Machine
  Learning}.

\bibitem[\protect\BCAY{Thronkide}{Thronkide}{1898}]{Thronkide}
Thronkide, E.~L. \BBOP1898\BBCP.
\newblock \BBOQ Animal intelligence: An experimental study of the associative
  processes in animals\BBCQ\
\newblock {\Bem Psychological Monographs}, {\Bem 2}.

\bibitem[\protect\BCAY{Watkins}{Watkins}{1989}]{Watkins}
Watkins, C. \BBOP1989\BBCP.
\newblock {\Bem Learning With Delayed Rewards}.
\newblock Ph.D.\ thesis, Cambridge University.

\bibitem[\protect\BCAY{Wellman}{Wellman}{1993}]{Well93}
Wellman, M.~P. \BBOP1993\BBCP.
\newblock \BBOQ A market-oriented programming environment and its application
  to distributed multicommodity flow problems\BBCQ\
\newblock {\Bem Journal of Artificial Intelligence Research}, {\Bem 1}, 1--23.

\bibitem[\protect\BCAY{Wheeler~Jr. \BBA\ Narendra}{Wheeler~Jr. \BBA\
  Narendra}{1985}]{WhNa85}
Wheeler~Jr., R.~M.\BBACOMMA\  \BBA\ Narendra, K. \BBOP1985\BBCP.
\newblock \BBOQ Learning models for decentralized decision making\BBCQ\
\newblock {\Bem Automatica}, {\Bem 21\/}(4), 479--484.

\bibitem[\protect\BCAY{Yanco \BBA\ Stein}{Yanco \BBA\ Stein}{1993}]{YanStei93}
Yanco, H.\BBACOMMA\  \BBA\ Stein, L. \BBOP1993\BBCP.
\newblock \BBOQ An adaptive communication protocol for cooperating mobile
  robots\BBCQ\
\newblock In {\Bem From Animals to Animats: Proceedings of the Second
  International Conference on the Simulation of Adaptive Behavior}, \BPGS\
  478--485.

\bibitem[\protect\BCAY{Zhou}{Zhou}{1988}]{Zhou}
Zhou, S. \BBOP1988\BBCP.
\newblock \BBOQ A trace-driven simulation study of dynamic load balancing\BBCQ\
\newblock {\Bem IEEE Transactions on Software Engineering}, {\Bem 14\/}(9),
  1327--1341.

\bibitem[\protect\BCAY{Zlotkin \BBA\ Rosenschein}{Zlotkin \BBA\
  Rosenschein}{1993}]{ZR}
Zlotkin, G.\BBACOMMA\  \BBA\ Rosenschein, J.~S. \BBOP1993\BBCP.
\newblock \BBOQ A domain theory for task oriented negotiation\BBCQ\
\newblock In {\Bem Proc.\ of the 13th Int.\ Joint Conf.\ on Artificial
  Intelligence (IJCAI-93)}, \BPGS\ 416--422.

\end{thebibliography}


\end{document}







